Optimize DocumentMarkerController::MarkerAtPosition()

Optimize DocumentMarkerController::MarkerAtPosition()

This method is used in some selection-related operations to look for spellcheck
markers. Now that we have DocumentMarkerList::MarkersIntersectingRange() (added
in https://codereview.chromium.org/2952953002) which uses binary search, we no
longer need to do a linear search over all the markers in the node to implement
this method.

BUG=707867
Review-Url: https://codereview.chromium.org/2949333002
Cr-Commit-Position: refs/heads/master@{#482871}
Committed: https://chromium.googlesource.com/chromium/src/+/28fc48705db361c2fd93cd302c0d15c2a1ed8da4

[rlanday, 2017-06-22 18:48:11]

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

[rlanday, 2017-06-22 18:48:19]

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

[commit-bot: I haz the power, 2017-06-22 18:48:28]

Dry run: 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 20:52:30]

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

[commit-bot: I haz the power, 2017-06-22 20:52:31]

Dry run: Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[Xiaocheng, 2017-06-23 17:44:08]

lgtm for code change

An issue about the documentation of MarkersIntersectingRange(), which says "...
non-empty overlap with the range [start_offset, end_offset]".

When |start_offset == end_offset|, which is the case in this patch, the
intersection is [offset, offset]. Is it counted as non-empty?

Note that the same issue exists when the range touches an endpoint of a marker,
in which case we may have an overlap range of, say, [start_offset,
start_offset]. The current design thinks this is empty, which contradicts with
the previous case.

Let's make the documentation more rigorous. We may say that the function
"Returns markers that have overlap with the range [start_offset, end_offset] in
their interiors. Markers touching the range at an endpoint are not returned."

[rlanday, 2017-06-23 18:39:30]

On 2017/06/23 at 17:44:08, xiaochengh wrote:
> lgtm for code change
> 
> An issue about the documentation of MarkersIntersectingRange(), which says
"... non-empty overlap with the range [start_offset, end_offset]".
> 
> When |start_offset == end_offset|, which is the case in this patch, the
intersection is [offset, offset]. Is it counted as non-empty?
> 
> Note that the same issue exists when the range touches an endpoint of a
marker, in which case we may have an overlap range of, say, [start_offset,
start_offset]. The current design thinks this is empty, which contradicts with
the previous case.
> 
> Let's make the documentation more rigorous. We may say that the function
"Returns markers that have overlap with the range [start_offset, end_offset] in
their interiors. Markers touching the range at an endpoint are not returned."

Yeah, that's a good point. I actually didn't realize it worked for the case
where start_offset == end_offset until I was halfway through writing this
method.

[rlanday, 2017-06-23 19:38:57]

On 2017/06/23 at 18:39:30, rlanday wrote:
> On 2017/06/23 at 17:44:08, xiaochengh wrote:
> > lgtm for code change
> > 
> > An issue about the documentation of MarkersIntersectingRange(), which says
"... non-empty overlap with the range [start_offset, end_offset]".
> > 
> > When |start_offset == end_offset|, which is the case in this patch, the
intersection is [offset, offset]. Is it counted as non-empty?
> > 
> > Note that the same issue exists when the range touches an endpoint of a
marker, in which case we may have an overlap range of, say, [start_offset,
start_offset]. The current design thinks this is empty, which contradicts with
the previous case.
> > 
> > Let's make the documentation more rigorous. We may say that the function
"Returns markers that have overlap with the range [start_offset, end_offset] in
their interiors. Markers touching the range at an endpoint are not returned."
> 
> Yeah, that's a good point. I actually didn't realize it worked for the case
where start_offset == end_offset until I was halfway through writing this
method.

I put up a CL to do that here:
https://codereview.chromium.org/2953183004

[yosin_UTC9, 2017-06-28 01:31:31]

lgtm

[rlanday, 2017-06-28 01:36:49]

The CQ bit was checked by rlanday@chromium.org

[commit-bot: I haz the power, 2017-06-28 01:37:16]

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-28 03:29:27]

CQ is committing da patch.

Bot data: {"patchset_id": 1, "attempt_start_ts": 1498613809656610, "parent_rev":
"2ce5f3fefd8958335fa480544794e7523625b26d", "commit_rev":
"28fc48705db361c2fd93cd302c0d15c2a1ed8da4"}

[commit-bot: I haz the power, 2017-06-28 03:29:39]

Description was changed from

==========
Optimize DocumentMarkerController::MarkerAtPosition()

This method is used in some selection-related operations to look for spellcheck
markers. Now that we have DocumentMarkerList::MarkersIntersectingRange() (added
in https://codereview.chromium.org/2952953002) which uses binary search, we no
longer need to do a linear search over all the markers in the node to implement
this method.

BUG=707867
==========

to

==========
Optimize DocumentMarkerController::MarkerAtPosition()

This method is used in some selection-related operations to look for spellcheck
markers. Now that we have DocumentMarkerList::MarkersIntersectingRange() (added
in https://codereview.chromium.org/2952953002) which uses binary search, we no
longer need to do a linear search over all the markers in the node to implement
this method.

BUG=707867

Review-Url: https://codereview.chromium.org/2949333002
Cr-Commit-Position: refs/heads/master@{#482871}
Committed:
https://chromium.googlesource.com/chromium/src/+/28fc48705db361c2fd93cd302c0d...
==========

[commit-bot: I haz the power, 2017-06-28 03:29:40]

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