[MarkersIntersectingRange #1] Add DocumentMarkerList::MarkersIntersectingRange()

Add DocumentMarkerList::MarkersIntersectingRange()

Currently, the only way to find the list of markers intersecting a range is to
iterate through the nodes the range contains, and get the complete list of nodes
for each range from DocumentMarkerController, and do a linear search through the
list. This is inefficient if we have a text node with a lot of markers, since we
could be doing a binary search instead of a linear scan.

This CL prepares us to add a
DocumentMarkerController::MarkersIntersectingRange() method by supporting the
necessary operation on the DocumentMarkerLists for each type (this is necessary
because DocumentMarkerController shouldn't be making any assumptions about how
each list is stored).

BUG=715365
Review-Url: https://codereview.chromium.org/2952953002
Cr-Commit-Position: refs/heads/master@{#481588}
Committed: https://chromium.googlesource.com/chromium/src/+/6c17fd58d40e84744ce40192a457888de8334a54

[rlanday, 2017-06-22 01:58:13]

Description was changed from

==========
dere# Enter a description of the change.
Add DocumentMarkerList::MarkersIntersectingRange()

Currently, the only way to find the list of markers intersecting a range is to
iterate through the nodes the range contains, and get the complete list of nodes
for each range from DocumentMarkerController, and do a linear search through the
list. This is inefficient if we have a text node with a lot of markers, since we
could be doing a binary search instead of a linear scan.

This CL prepares us to add a
DocumentMarkerController::MarkersIntersectingRange() method by supporting the
necessary operation on the DocumentMarkerLists for each type (this is necessary
because DocumentMarkerController shouldn't be making any assumptions about how
each list is stored).

BUG=715365
==========

to

==========
Add DocumentMarkerList::MarkersIntersectingRange()

Currently, the only way to find the list of markers intersecting a range is to
iterate through the nodes the range contains, and get the complete list of nodes
for each range from DocumentMarkerController, and do a linear search through the
list. This is inefficient if we have a text node with a lot of markers, since we
could be doing a binary search instead of a linear scan.

This CL prepares us to add a
DocumentMarkerController::MarkersIntersectingRange() method by supporting the
necessary operation on the DocumentMarkerLists for each type (this is necessary
because DocumentMarkerController shouldn't be making any assumptions about how
each list is stored).

BUG=715365
==========

[rlanday, 2017-06-22 01:58:13]

rlanday@chromium.org changed reviewers:
+ xiaochengh@chromium.org, yosin@chromium.org

[rlanday, 2017-06-22 01:59:37]

https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h
(right):

https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h:49:
static HeapVector<Member<DocumentMarker>> MarkersIntersectingRange(
This isn't actually an editing method, but I wasn't sure where else to put this.

I propose we rename this class to something like SortedDocumentMarkerListUtils.
All of the methods in this class only work with DocumentMarkerList
implementations that store non-overlapping markers in sorted order, which isn't
otherwise clear, and we have this non-editing method we need to put somewhere.

[rlanday, 2017-06-22 02:13:58]

The CQ bit was checked by rlanday@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-06-22 02:14:16]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[yosin_UTC9, 2017-06-22 02:28:20]

lgtm

https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h
(right):

https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h:49:
static HeapVector<Member<DocumentMarker>> MarkersIntersectingRange(
On 2017/06/22 at 01:59:37, rlanday wrote:
> This isn't actually an editing method, but I wasn't sure where else to put
this.
> 
> I propose we rename this class to something like
SortedDocumentMarkerListUtils. All of the methods in this class only work with
DocumentMarkerList implementations that store non-overlapping markers in sorted
order, which isn't otherwise clear, and we have this non-editing method we need
to put somewhere.

I think "Editor" is better than "Utils", actually it should be "Utilities" due
by non-abbreviation rule in Blink, with 
 - Editor can do non-modification operation, e.g. find, move cursor, select,
etc.
 - Editor is shorter than "Utilities".

[Xiaocheng, 2017-06-22 03:06:06]

https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h
(right):

https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h:49:
static HeapVector<Member<DocumentMarker>> MarkersIntersectingRange(
On 2017/06/22 at 02:28:20, yosin_UTC9 wrote:
> On 2017/06/22 at 01:59:37, rlanday wrote:
> > This isn't actually an editing method, but I wasn't sure where else to put
this.
> > 
> > I propose we rename this class to something like
SortedDocumentMarkerListUtils. All of the methods in this class only work with
DocumentMarkerList implementations that store non-overlapping markers in sorted
order, which isn't otherwise clear, and we have this non-editing method we need
to put somewhere.
> 
> I think "Editor" is better than "Utils", actually it should be "Utilities" due
by non-abbreviation rule in Blink, with 
>  - Editor can do non-modification operation, e.g. find, move cursor, select,
etc.
>  - Editor is shorter than "Utilities".

I'm a little skeptical about this function returning a new vector instead of a
range in the existing vector.

Too bad that WTF::Vector doesn't have a subrange class...

Should we add one?

[rlanday, 2017-06-22 03:19:00]

On 2017/06/22 at 03:06:06, xiaochengh wrote:
>
https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
> File third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h
(right):
> 
>
https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
> third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h:49:
static HeapVector<Member<DocumentMarker>> MarkersIntersectingRange(
> On 2017/06/22 at 02:28:20, yosin_UTC9 wrote:
> > On 2017/06/22 at 01:59:37, rlanday wrote:
> > > This isn't actually an editing method, but I wasn't sure where else to put
this.
> > > 
> > > I propose we rename this class to something like
SortedDocumentMarkerListUtils. All of the methods in this class only work with
DocumentMarkerList implementations that store non-overlapping markers in sorted
order, which isn't otherwise clear, and we have this non-editing method we need
to put somewhere.
> > 
> > I think "Editor" is better than "Utils", actually it should be "Utilities"
due by non-abbreviation rule in Blink, with 
> >  - Editor can do non-modification operation, e.g. find, move cursor, select,
etc.
> >  - Editor is shorter than "Utilities".
> 
> I'm a little skeptical about this function returning a new vector instead of a
range in the existing vector.
> 
> Too bad that WTF::Vector doesn't have a subrange class...
> 
> Should we add one?

That's an interesting idea, but note that once we have suggestion markers, they
will not be stored in sorted order, so this idea will no longer work.

[commit-bot: I haz the power, 2017-06-22 04:13:43]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-06-22 04:13:44]

Dry run: This issue passed the CQ dry run.

[yosin_UTC9, 2017-06-22 04:34:16]

On 2017/06/22 at 03:19:00, rlanday wrote:
> On 2017/06/22 at 03:06:06, xiaochengh wrote:
> >
https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
> > File
third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h
(right):
> > 
> >
https://codereview.chromium.org/2952953002/diff/1/third_party/WebKit/Source/c...
> >
third_party/WebKit/Source/core/editing/markers/DocumentMarkerListEditor.h:49:
static HeapVector<Member<DocumentMarker>> MarkersIntersectingRange(
> > On 2017/06/22 at 02:28:20, yosin_UTC9 wrote:
> > > On 2017/06/22 at 01:59:37, rlanday wrote:
> > > > This isn't actually an editing method, but I wasn't sure where else to
put this.
> > > > 
> > > > I propose we rename this class to something like
SortedDocumentMarkerListUtils. All of the methods in this class only work with
DocumentMarkerList implementations that store non-overlapping markers in sorted
order, which isn't otherwise clear, and we have this non-editing method we need
to put somewhere.
> > > 
> > > I think "Editor" is better than "Utils", actually it should be "Utilities"
due by non-abbreviation rule in Blink, with 
> > >  - Editor can do non-modification operation, e.g. find, move cursor,
select, etc.
> > >  - Editor is shorter than "Utilities".
> > 
> > I'm a little skeptical about this function returning a new vector instead of
a range in the existing vector.
> > 
> > Too bad that WTF::Vector doesn't have a subrange class...
> > 
> > Should we add one?
> 
> That's an interesting idea, but note that once we have suggestion markers,
they will not be stored in sorted order, so this idea will no longer work.

In general, exposing subrange introduces complexity of lifetime and mutability.
When returning subrange, we should not change original vector during
subrange alive.

[rlanday, 2017-06-22 17:38:13]

The CQ bit was checked by rlanday@chromium.org

[commit-bot: I haz the power, 2017-06-22 17:38:29]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-06-22 17:43:47]

CQ is committing da patch.

Bot data: {"patchset_id": 1, "attempt_start_ts": 1498153093814110, "parent_rev":
"80652679e79f0b1e2974168acce69b347795d688", "commit_rev":
"6c17fd58d40e84744ce40192a457888de8334a54"}

[commit-bot: I haz the power, 2017-06-22 17:44:01]

Description was changed from

==========
Add DocumentMarkerList::MarkersIntersectingRange()

Currently, the only way to find the list of markers intersecting a range is to
iterate through the nodes the range contains, and get the complete list of nodes
for each range from DocumentMarkerController, and do a linear search through the
list. This is inefficient if we have a text node with a lot of markers, since we
could be doing a binary search instead of a linear scan.

This CL prepares us to add a
DocumentMarkerController::MarkersIntersectingRange() method by supporting the
necessary operation on the DocumentMarkerLists for each type (this is necessary
because DocumentMarkerController shouldn't be making any assumptions about how
each list is stored).

BUG=715365
==========

to

==========
Add DocumentMarkerList::MarkersIntersectingRange()

Currently, the only way to find the list of markers intersecting a range is to
iterate through the nodes the range contains, and get the complete list of nodes
for each range from DocumentMarkerController, and do a linear search through the
list. This is inefficient if we have a text node with a lot of markers, since we
could be doing a binary search instead of a linear scan.

This CL prepares us to add a
DocumentMarkerController::MarkersIntersectingRange() method by supporting the
necessary operation on the DocumentMarkerLists for each type (this is necessary
because DocumentMarkerController shouldn't be making any assumptions about how
each list is stored).

BUG=715365

Review-Url: https://codereview.chromium.org/2952953002
Cr-Commit-Position: refs/heads/master@{#481588}
Committed:
https://chromium.googlesource.com/chromium/src/+/6c17fd58d40e84744ce40192a457...
==========

[commit-bot: I haz the power, 2017-06-22 17:44:02]

Committed patchset #1 (id:1) as
https://chromium.googlesource.com/chromium/src/+/6c17fd58d40e84744ce40192a457...