Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(50)

Issue 2948133004: [MarkersIntersectingRange #2] Add DocumentMarkerController::MarkersIntersectingRange() (Closed)

Created:
3 years, 6 months ago by rlanday
Modified:
3 years, 5 months ago
CC:
blink-reviews, chromium-reviews
Target Ref:
refs/heads/master
Project:
chromium
Visibility:
Public.

Description

Add DocumentMarkerController::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 introduces a DocumentMarkerController::MarkersIntersectingRange() method which allows us to perform this operation much more efficiently. BUG=715365

Patch Set 1 #

Total comments: 13

Patch Set 2 : Respond to comments #

Total comments: 1

Patch Set 3 : Use HeapVector #

Total comments: 2

Patch Set 4 : Templatize the method so it can also take an EphemeralRangeInFlatTree #

Total comments: 8

Patch Set 5 : Clarify behavior for empty range #

Patch Set 6 : Add PossiblyHasMarkers() #

Patch Set 7 : Update comment, Empty => Collapsed #

Total comments: 1

Patch Set 8 : Attempt to fix templates #

Total comments: 1

Patch Set 9 : Add test case for shadow DOM #

Patch Set 10 : Remove unnecessary calls to UpdateStyleAndLayout() #

Patch Set 11 : Remove logging code (call to ShowMarkers()) #

Total comments: 1

Patch Set 12 : Remove DOM tree version #

Patch Set 13 : Remove MarkersIntersectingRangeHelper() from header file #

Unified diffs Side-by-side diffs Delta from patch set Stats (+136 lines, -0 lines) Patch
M third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h View 1 2 3 4 5 6 7 8 9 10 11 12 1 chunk +7 lines, -0 lines 0 comments Download
M third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp View 1 2 3 4 5 6 7 8 9 10 11 1 chunk +42 lines, -0 lines 0 comments Download
M third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp View 1 2 3 4 5 6 7 8 9 10 11 1 chunk +87 lines, -0 lines 0 comments Download

Dependent Patchsets:

Messages

Total messages: 81 (41 generated)
rlanday
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode382 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: Vector<std::pair<Node*, DocumentMarker*>> kouhei@: Is it safe to return a ...
3 years, 6 months ago (2017-06-22 02:16:04 UTC) #5
yosin_UTC9
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode395 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:395: for (Node& node : range.Nodes()) { nit: s/Node&/const Node&/ ...
3 years, 6 months ago (2017-06-22 03:13:41 UTC) #6
Xiaocheng
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp#newcode341 third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp:341: // Add a grammar marker on "456" s/grammar/text match/
3 years, 6 months ago (2017-06-22 03:25:10 UTC) #7
rlanday
Updated https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode395 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:395: for (Node& node : range.Nodes()) { On 2017/06/22 ...
3 years, 6 months ago (2017-06-22 03:27:10 UTC) #8
kouhei (in TOK)
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode382 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: Vector<std::pair<Node*, DocumentMarker*>> On 2017/06/22 02:16:04, rlanday wrote: > kouhei@: ...
3 years, 6 months ago (2017-06-22 03:31:49 UTC) #11
rlanday
On 2017/06/22 at 03:31:49, kouhei wrote: > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode382 ...
3 years, 6 months ago (2017-06-22 03:35:04 UTC) #12
Xiaocheng
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode382 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: Vector<std::pair<Node*, DocumentMarker*>> On 2017/06/22 at 03:31:49, kouhei (in TOK) ...
3 years, 6 months ago (2017-06-22 03:39:09 UTC) #13
kouhei (in TOK)
On 2017/06/22 03:35:04, rlanday wrote: > On 2017/06/22 at 03:31:49, kouhei wrote: > > > ...
3 years, 6 months ago (2017-06-22 03:46:41 UTC) #14
kouhei (in TOK)
> For my curiosity: The lifetime of the returned vector is scoped within some > ...
3 years, 6 months ago (2017-06-22 03:50:34 UTC) #15
Xiaocheng
On 2017/06/22 at 03:50:34, kouhei wrote: > > For my curiosity: The lifetime of the ...
3 years, 6 months ago (2017-06-22 03:55:26 UTC) #16
yosin_UTC9
https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h#newcode99 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:99: Vector<std::pair<Node*, DocumentMarker*>> MarkersIntersectingRange( According kohei@'s comment, we need to ...
3 years, 6 months ago (2017-06-22 09:17:39 UTC) #19
rlanday
On 2017/06/22 at 09:17:39, yosin wrote: > https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): > > https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h#newcode99 ...
3 years, 6 months ago (2017-06-22 17:57:48 UTC) #21
Xiaocheng
https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode382 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> Can the return type be changed to ...
3 years, 6 months ago (2017-06-22 18:08:15 UTC) #23
rlanday
On 2017/06/22 at 18:08:15, xiaochengh wrote: > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode382 ...
3 years, 6 months ago (2017-06-22 18:09:54 UTC) #24
Xiaocheng
On 2017/06/22 at 18:09:54, rlanday wrote: > On 2017/06/22 at 18:08:15, xiaochengh wrote: > > ...
3 years, 6 months ago (2017-06-22 18:15:01 UTC) #25
rlanday
https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h#newcode100 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:100: MarkersIntersectingRange(const EphemeralRange&, DocumentMarker::MarkerTypes); Would it make sense to also ...
3 years, 6 months ago (2017-06-22 23:33:06 UTC) #28
rlanday
On 2017/06/22 at 23:33:06, rlanday wrote: > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): > > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h#newcode100 ...
3 years, 6 months ago (2017-06-23 01:09:24 UTC) #31
kouhei (in TOK)
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp#newcode351 third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp:351: const HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>>& results = use HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> (non ...
3 years, 6 months ago (2017-06-23 01:20:59 UTC) #32
rlanday
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp#newcode351 third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp:351: const HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>>& results = On 2017/06/23 at 01:20:59, ...
3 years, 6 months ago (2017-06-23 01:30:23 UTC) #33
yosin_UTC9
+tkent@ for second eye. https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode387 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:387: Node* const range_start_container = Note: ...
3 years, 6 months ago (2017-06-23 01:37:03 UTC) #35
rlanday
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode387 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:387: Node* const range_start_container = On 2017/06/23 at 01:37:02, yosin_UTC9 ...
3 years, 6 months ago (2017-06-23 01:41:55 UTC) #36
rlanday
3 years, 6 months ago (2017-06-23 01:41:58 UTC) #37
yosin_UTC9
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode387 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:387: Node* const range_start_container = On 2017/06/23 at 01:41:54, rlanday ...
3 years, 6 months ago (2017-06-23 02:03:47 UTC) #38
rlanday
Updated with a comment and test case about the behavior for an empty range
3 years, 6 months ago (2017-06-23 19:26:06 UTC) #41
rlanday
Added PossiblyHasMarkers()
3 years, 6 months ago (2017-06-23 20:58:39 UTC) #44
rlanday
https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode425 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:425: template HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> I probably need CORE_TEMPLATE_EXPORT here to ...
3 years, 6 months ago (2017-06-24 01:08:29 UTC) #51
rlanday
On 2017/06/24 at 01:08:29, rlanday wrote: > https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp#newcode425 ...
3 years, 5 months ago (2017-06-26 20:56:34 UTC) #54
Xiaocheng
I think we need a more systematic approach if we want to handle shadow-crossing ranges ...
3 years, 5 months ago (2017-06-26 22:13:04 UTC) #57
rlanday
On 2017/06/26 at 22:13:04, xiaochengh wrote: > https://codereview.chromium.org/2948133004/diff/140001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h#newcode104 > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:104: MarkersIntersectingRange(const EphemeralRangeInFlatTree&, > Please add ...
3 years, 5 months ago (2017-06-27 22:11:10 UTC) #58
yosin_UTC9
Who does use DMC::MarkersIntersectingRange()? ContextMenu and SpellChecker::ReplaceMisspelledRange() should use FirstMarkesInRange().
3 years, 5 months ago (2017-06-29 01:26:52 UTC) #67
rlanday
On 2017/06/29 at 01:26:52, yosin wrote: > Who does use DMC::MarkersIntersectingRange()? > > ContextMenu and ...
3 years, 5 months ago (2017-06-29 02:33:05 UTC) #68
rlanday
On 2017/06/29 at 02:33:05, rlanday wrote: > On 2017/06/29 at 01:26:52, yosin wrote: > > ...
3 years, 5 months ago (2017-07-03 16:47:40 UTC) #69
yosin_UTC9
https://codereview.chromium.org/2948133004/diff/200001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/200001/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h#newcode139 third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:139: MarkersIntersectingRangeHelper(const EphemeralRangeTemplate<Strategy>&, Can we have flat tree version only? ...
3 years, 5 months ago (2017-07-05 04:51:37 UTC) #70
yosin_UTC9
On 2017/07/03 at 16:47:40, rlanday wrote: > On 2017/06/29 at 02:33:05, rlanday wrote: > > ...
3 years, 5 months ago (2017-07-05 04:59:05 UTC) #71
rlanday
I think you're right that we only need the flat tree version. I will update ...
3 years, 5 months ago (2017-07-05 05:08:46 UTC) #72
yosin_UTC9
On 2017/07/05 at 05:08:46, rlanday wrote: > I think you're right that we only need ...
3 years, 5 months ago (2017-07-05 05:25:23 UTC) #73
rlanday
I've updated the CL so it only has the flat tree version now. On 2017/07/05 ...
3 years, 5 months ago (2017-07-05 17:47:33 UTC) #74
yosin_UTC9
On 2017/07/05 at 17:47:33, rlanday wrote: > I've updated the CL so it only has ...
3 years, 5 months ago (2017-07-06 01:28:05 UTC) #79
rlanday
On 2017/07/06 at 01:28:05, yosin wrote: > Could you compare context menu misspell replacement and ...
3 years, 5 months ago (2017-07-06 01:36:23 UTC) #80
rlanday
3 years, 5 months ago (2017-07-06 20:34:00 UTC) #81
On 2017/07/06 at 01:36:23, rlanday wrote:
> On 2017/07/06 at 01:28:05, yosin wrote:
> > Could you compare context menu misspell replacement and TextSuggetion
misspell in design doc of TextSuggetion?
> > I would like to know difference of them to understand why TextSuggesion
needs makers of range even if context menu
> > needs a first marker at position.
> 
> It's basically because we can pull suggestions from multiple suggestion
markers to show in the same menu. So we need all of the spans touching the
cursor, not just one.
> 
> I'll update the design doc tomorrow.

I've updated the design doc:
https://docs.google.com/document/d/1IQQTZS3T0QdP8eb9tOea2HNhbjOJxmRDiWJAHMzdm78

I've added some information about how we can show the menu for both spell check
and suggestion markers.

Relevant section:

> Note: we only need to show spell check suggestions from at most one spell
check marker (even if the cursor is right between two spell check markers, we
only highlight one marker and show suggestions for that marker). However, we can
pull suggestions from multiple suggestion markers, and highlight a range that’s
the union of multiple markers. This means we need to be able to get all the
suggestion markers from DocumentMarkerController intersecting the two-character
range surrounding the insertion caret.

Powered by Google App Engine
This is Rietveld 408576698