|
|
DescriptionAdd 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 #
Dependent Patchsets: Messages
Total messages: 81 (41 generated)
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
rlanday@chromium.org changed reviewers: + xiaochengh@chromium.org, yosin@chromium.org
rlanday@chromium.org changed reviewers: + kouhei@chromium.org
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: Vector<std::pair<Node*, DocumentMarker*>> kouhei@: Is it safe to return a Vector of std::pairs of pointers to Oilpan-allocated types?
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:395: for (Node& node : range.Nodes()) { nit: s/Node&/const Node&/ https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:396: MarkerLists* markers = markers_.at(&node); nit: s/MarkerLists*/const MarkerLists* const/ https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:405: unsigned start_offset = nit: s/unsigned/const unsigned/ https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:406: (node == range_start_container ? range_start_offset : 0); nit: No need to have parenthesis. https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:407: unsigned end_offset = nit: s/unsigned/const unsigned/ https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:408: (node == range_end_container ? range_end_offset nit: No need to have parenthesis.
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp:341: // Add a grammar marker on "456" s/grammar/text match/
Updated https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:395: for (Node& node : range.Nodes()) { On 2017/06/22 at 03:13:40, yosin_UTC9 wrote: > nit: s/Node&/const Node&/ This needs to be non-const since we return a non-const pointer to it https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:396: MarkerLists* markers = markers_.at(&node); On 2017/06/22 at 03:13:40, yosin_UTC9 wrote: > nit: s/MarkerLists*/const MarkerLists* const/ ListForType() only works with a non-const pointer
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... 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@: Is it safe to return a Vector of std::pairs of pointers to > Oilpan-allocated types? No. Please use HeapVector<pair<Member<Node>, Member<DocumentMarker>>> https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:394: Vector<std::pair<Node*, DocumentMarker*>> node_marker_pairs; also here
On 2017/06/22 at 03:31:49, kouhei wrote: > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... > 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@: Is it safe to return a Vector of std::pairs of pointers to > > Oilpan-allocated types? > > No. > Please use HeapVector<pair<Member<Node>, Member<DocumentMarker>>> > > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:394: Vector<std::pair<Node*, DocumentMarker*>> node_marker_pairs; > also here std::pair knows how to trace its contents? How does that work? If I were to implement my own pair class: struct my_pair { Member<Node> node_; Member<DocumentMarker> marker_; } would that work the same way in a HeapVector?
https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... 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) wrote: > On 2017/06/22 02:16:04, rlanday wrote: > > kouhei@: Is it safe to return a Vector of std::pairs of pointers to > > Oilpan-allocated types? > > No. > Please use HeapVector<pair<Member<Node>, Member<DocumentMarker>>> For my curiosity: The lifetime of the returned vector is scoped within some function body. Can Oilpan GC run when the vector is alive? What's the thread affinity of Oilpan GC?
On 2017/06/22 03:35:04, rlanday wrote: > On 2017/06/22 at 03:31:49, kouhei wrote: > > > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... > > File > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp > (right): > > > > > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... > > > 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@: Is it safe to return a Vector of std::pairs of pointers to > > > Oilpan-allocated types? > > > > No. > > Please use HeapVector<pair<Member<Node>, Member<DocumentMarker>>> > > > > > https://codereview.chromium.org/2948133004/diff/1/third_party/WebKit/Source/c... > > > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:394: > Vector<std::pair<Node*, DocumentMarker*>> node_marker_pairs; > > also here > > std::pair knows how to trace its contents? How does that work? If I were to > implement my own pair class: > > struct my_pair { > Member<Node> node_; > Member<DocumentMarker> marker_; > } > > would that work the same way in a HeapVector? std::pair knows how to trace its contents. see: TraceTrait<std::pair<T, U>>
> For my curiosity: The lifetime of the returned vector is scoped within some > function body. Can Oilpan GC run when the vector is alive? What's the thread > affinity of Oilpan GC? Oilpan GC scans stack, but not std::vector or WTF::Vector heap, as it is not managed by Oilpan. If you put Vector<GCObj*>, the Vector instance is on the stack but the contents of the vector is on unmanaged heap. Thus, you need to use HeapVector<Member<GCObj>> to be Oilpan friendly Oilpan GC can run at any timing you try to allocate new obj from Oilpan heap. re: thread affinity, please refer to BlinkGCDesign.md #Threading model
On 2017/06/22 at 03:50:34, kouhei wrote: > > For my curiosity: The lifetime of the returned vector is scoped within some > > function body. Can Oilpan GC run when the vector is alive? What's the thread > > affinity of Oilpan GC? > Oilpan GC scans stack, but not std::vector or WTF::Vector heap, as it is not managed by Oilpan. > If you put Vector<GCObj*>, the Vector instance is on the stack but the contents of the vector is on unmanaged heap. > Thus, you need to use HeapVector<Member<GCObj>> to be Oilpan friendly > > Oilpan GC can run at any timing you try to allocate new obj from Oilpan heap. > > re: thread affinity, please refer to BlinkGCDesign.md #Threading model Thanks!
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:99: Vector<std::pair<Node*, DocumentMarker*>> MarkersIntersectingRange( According kohei@'s comment, we need to use |HeapVector<std::pair<Node*, DocumentMarker*>>
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
On 2017/06/22 at 09:17:39, yosin wrote: > https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Sour... > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): > > https://codereview.chromium.org/2948133004/diff/20001/third_party/WebKit/Sour... > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:99: Vector<std::pair<Node*, DocumentMarker*>> MarkersIntersectingRange( > According kohei@'s comment, we need to use |HeapVector<std::pair<Node*, DocumentMarker*>> Updated
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> Can the return type be changed to HeapVector<std::pair<Member<cost Node>, Member<const DocumentMarker>>> so that we can use const references in the function body?
On 2017/06/22 at 18:08:15, xiaochengh wrote: > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> > Can the return type be changed to > > HeapVector<std::pair<Member<cost Node>, Member<const DocumentMarker>>> > > so that we can use const references in the function body? I think that might be problematic depending what callers want to do with the result. E.g. once we have suggestion markers, we'll have a caller that wants to mutate the list of suggestions on the SuggestionMarker. It also doesn't seem unreasonable to me that a caller might want to mutate the Node.
On 2017/06/22 at 18:09:54, rlanday wrote: > On 2017/06/22 at 18:08:15, xiaochengh wrote: > > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... > > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > > > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... > > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:382: HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> > > Can the return type be changed to > > > > HeapVector<std::pair<Member<cost Node>, Member<const DocumentMarker>>> > > > > so that we can use const references in the function body? > > I think that might be problematic depending what callers want to do with the result. E.g. once we have suggestion markers, we'll have a caller that wants to mutate the list of suggestions on the SuggestionMarker. It also doesn't seem unreasonable to me that a caller might want to mutate the Node. All right, lgtm then.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:100: MarkersIntersectingRange(const EphemeralRange&, DocumentMarker::MarkerTypes); Would it make sense to also have a version of this for EphemeralRangeInFlatTree? I'm wondering if this would be useful when we get the VisiblePositionInFlatTree from SelectionController and want to create a range that includes one character before and one after.
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
On 2017/06/22 at 23:33:06, rlanday wrote: > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): > > https://codereview.chromium.org/2948133004/diff/40001/third_party/WebKit/Sour... > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:100: MarkersIntersectingRange(const EphemeralRange&, DocumentMarker::MarkerTypes); > Would it make sense to also have a version of this for EphemeralRangeInFlatTree? I'm wondering if this would be useful when we get the VisiblePositionInFlatTree from SelectionController and want to create a range that includes one character before and one after. I've updated this with the template as it does seem useful to have the EphemeralRangeInFlatTree version to efficiently implement HandlePotentialTextSuggestionTap().
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... 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 const ref) or just const auto results The original code will result in undefined behavior.
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerControllerTest.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... 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, kouhei (in TOK) wrote: > use HeapVector<std::pair<Member<Node>, Member<DocumentMarker>>> (non const ref) or just const auto results > The original code will result in undefined behavior. Can you please clarify? I think taking a const reference to a temporary is usually safe.
yosin@chromium.org changed reviewers: + tkent@chromium.org
+tkent@ for second eye. https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:387: Node* const range_start_container = Note: |range_start_offset| is valid only if |range_start_container| is |Text| node. https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:397: MarkerLists* const markers = markers_.at(&node); Note: |node| is always |Text| node. HashMap<T>::at(Key) is shorthand.
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... 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 wrote: > Note: |range_start_offset| is valid only if |range_start_container| is |Text| node. Really? Can't a range also be relative to a non-Text node, and have an offset counting which child node it starts at? https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:397: MarkerLists* const markers = markers_.at(&node); On 2017/06/23 at 01:37:02, yosin_UTC9 wrote: > HashMap<T>::at(Key) is shorthand. What is it shorthand for?
https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:387: Node* const range_start_container = On 2017/06/23 at 01:41:54, rlanday wrote: > On 2017/06/23 at 01:37:02, yosin_UTC9 wrote: > > Note: |range_start_offset| is valid only if |range_start_container| is |Text| node. > > Really? Can't a range also be relative to a non-Text node, and have an offset counting which child node it starts at? I mean "valid" for comparison against marker offset. https://codereview.chromium.org/2948133004/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp:397: MarkerLists* const markers = markers_.at(&node); On 2017/06/23 at 01:41:54, rlanday wrote: > On 2017/06/23 at 01:37:02, yosin_UTC9 wrote: > > HashMap<T>::at(Key) is shorthand. > > What is it shorthand for? Compare to std::unordered_map()'s. With std::unordered_map(), we could write: const auto& it = map.find(key); auto* value = it == map.end() ? nullptr : *it; Since at() in std::unordered_map(), and std::vector throws an exception, we may be surprised when see using at().
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
Updated with a comment and test case about the behavior for an empty range
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Added PossiblyHasMarkers()
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Sou... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Sou... 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 fix the Windows builds
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
On 2017/06/24 at 01:08:29, rlanday wrote: > https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Sou... > File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp (right): > > https://codereview.chromium.org/2948133004/diff/120001/third_party/WebKit/Sou... > 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 fix the Windows builds Actually what I needed to do was explicitly define two non-templated versions of the method in the header. Updated
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
I think we need a more systematic approach if we want to handle shadow-crossing ranges in DMC. In the current code base, the public functions dealing with ranges only take DOM EphemeralRanges, and they are inconsistent that: - AddFooMarker: These functions do not crash on shadow-crossing ranges because they use TextIterator. I'm not sure about TI's behavior when the input range crosses shadow boundary, but at least it stops when reaching the end of the document. - RemoveMarkersInRange: Same as above. - SetTextMatchMarkersActive(EphemeralRange, bool): It crashes when given a shadow-crossing range, as it iterates nodes in the input range with EphemeralRange::Nodes() So we need to figure out: 1. Do we really need to support shadow-crossing ranges? I guess yes since you gave an example last time. 2. What are the sources passing shadow-crossing ranges to DMC? 3. What is the correct way to iterate nodes in the input range? I'm not a fan of TI. Maybe we should introduce two versions for each function, just like what you are trying in this patch. 4. A greater topic is, which of the range-like classes (Range, EphemeralRange, SelectionInDOMTree, VisibleSelection) can cross shadow boundary and which cannot? Should we prioritize and generalize http://crbug.com/466483? https://codereview.chromium.org/2948133004/diff/140001/third_party/WebKit/Sou... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/140001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:104: MarkersIntersectingRange(const EphemeralRangeInFlatTree&, Please add a unit test for this function to confirm that it works on ranges crossing shadow boundaries.
On 2017/06/26 at 22:13:04, xiaochengh wrote: > https://codereview.chromium.org/2948133004/diff/140001/third_party/WebKit/Sou... > third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:104: MarkersIntersectingRange(const EphemeralRangeInFlatTree&, > Please add a unit test for this function to confirm that it works on ranges crossing shadow boundaries. I've added a test case. I based it on the problem I saw the other day on the chrome://tracing page. We have markup that looks like this (minimized): <div>not shadow</div> <div> (shadow DOM host) #shadow-root <div>shadow1</div> <div>shadow2</div> If you try to create an EphemeralRange with one character on either side of an insertion point at the end of "not shadow," you get a start position in the "not shadow" text and an end position in a shadow element, and range.Nodes() eventually returns a null pointer, which causes a crash. The test verifies that this case works using the EphemeralRangeInFlatTree version of the method. Waiting for yosin@'s feedback on the design questions
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
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_...)
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Who does use DMC::MarkersIntersectingRange()? ContextMenu and SpellChecker::ReplaceMisspelledRange() should use FirstMarkesInRange().
On 2017/06/29 at 01:26:52, yosin wrote: > Who does use DMC::MarkersIntersectingRange()? > > ContextMenu and SpellChecker::ReplaceMisspelledRange() should use FirstMarkesInRange(). I was going to use it in TextSuggestionController when we make the range containing one character on either side of the selection to find markers touching the insertion point (where we may have to search two different markers). That was before we decided to add DMC::FirstMarkerInRange() though. We can almost implement MarkersIntersectingRange() in TextSuggestionController on top of DMC::FirstMarkerInRange(), except that once we have suggestion markers, we'll want to get more than one marker touching the selection (and performance will still be a concern).
On 2017/06/29 at 02:33:05, rlanday wrote: > On 2017/06/29 at 01:26:52, yosin wrote: > > Who does use DMC::MarkersIntersectingRange()? > > > > ContextMenu and SpellChecker::ReplaceMisspelledRange() should use FirstMarkesInRange(). > > I was going to use it in TextSuggestionController when we make the range containing one character on either side of the selection to find markers touching the insertion point (where we may have to search two different markers). > > That was before we decided to add DMC::FirstMarkerInRange() though. We can almost implement MarkersIntersectingRange() in TextSuggestionController on top of DMC::FirstMarkerInRange(), except that once we have suggestion markers, we'll want to get more than one marker touching the selection (and performance will still be a concern). yosin@: can you please clarify how you think I should implement TextSuggestionController::HandlePotentialMisspelledWordTap()?
https://codereview.chromium.org/2948133004/diff/200001/third_party/WebKit/Sou... File third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h (right): https://codereview.chromium.org/2948133004/diff/200001/third_party/WebKit/Sou... third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.h:139: MarkersIntersectingRangeHelper(const EphemeralRangeTemplate<Strategy>&, Can we have flat tree version only? I think we don't need to have DOM tree version.
On 2017/07/03 at 16:47:40, rlanday wrote: > On 2017/06/29 at 02:33:05, rlanday wrote: > > On 2017/06/29 at 01:26:52, yosin wrote: > > > Who does use DMC::MarkersIntersectingRange()? > > > > > > ContextMenu and SpellChecker::ReplaceMisspelledRange() should use FirstMarkesInRange(). > > > > I was going to use it in TextSuggestionController when we make the range containing one character on either side of the selection to find markers touching the insertion point (where we may have to search two different markers). > > > > That was before we decided to add DMC::FirstMarkerInRange() though. We can almost implement MarkersIntersectingRange() in TextSuggestionController on top of DMC::FirstMarkerInRange(), except that once we have suggestion markers, we'll want to get more than one marker touching the selection (and performance will still be a concern). > > yosin@: can you please clarify how you think I should implement TextSuggestionController::HandlePotentialMisspelledWordTap()? HandlePotentialMisspelledWordTap() should check 1. touch position is content editable 2. DMC has spelling markers then start suggestion menu timer. Both checks are cheap. Once timer is fired, get spelling markers around touch position. For spell checking is is OK for once. For voice, we may want to have markers for a sentence, words in sentence; I'm not sure whether voice IME support paragraph or not.
I think you're right that we only need the flat tree version. I will update the CL. On 2017/07/05 at 04:59:05, yosin wrote: > HandlePotentialMisspelledWordTap() should check > 1. touch position is content editable > 2. DMC has spelling markers > then start suggestion menu timer. > Both checks are cheap. > > Once timer is fired, get spelling markers around touch position. > For spell checking is is OK for once. > For voice, we may want to have markers for a sentence, words in sentence; I'm not sure whether voice IME support paragraph or not. When we get a touch event, we only need to find if at least one spelling or suggestion marker is present. We don't need to find all of them until the timer fires. What purpose would having separate markers for words and sentences serve? This doesn't really match the API Android uses (it just specifies a range for each SuggestionSpan). Would this be more efficient somehow? I think if efficiency ends up being an issue, the way to improve it would be to store the markers in some sort of data structure that allows for efficient range queries even if the markers overlap (e.g. an interval tree).
On 2017/07/05 at 05:08:46, rlanday wrote: > I think you're right that we only need the flat tree version. I will update the CL. > > On 2017/07/05 at 04:59:05, yosin wrote: > > HandlePotentialMisspelledWordTap() should check > > 1. touch position is content editable > > 2. DMC has spelling markers > > then start suggestion menu timer. > > Both checks are cheap. > > > > Once timer is fired, get spelling markers around touch position. > > For spell checking is is OK for once. > > For voice, we may want to have markers for a sentence, words in sentence; I'm not sure whether voice IME support paragraph or not. > > When we get a touch event, we only need to find if at least one spelling or suggestion marker is present. We don't need to find all of them until the timer fires. What purpose would having separate markers for words and sentences serve? This doesn't really match the API Android uses (it just specifies a range for each SuggestionSpan). Would this be more efficient somehow? I think if efficiency ends up being an issue, the way to improve it would be to store the markers in some sort of data structure that allows for efficient range queries even if the markers overlap (e.g. an interval tree). Sorry for confusion, my mention about voice IME is just guessing. The main point of my opinion is - HandlePotentialMisspelledWordTap() does cheap checking - Show context menu does expensive operation I don't think we don't need to make checking faster. Duration between starting timer and firing timer can change DOM tree and markers somehow. Thus, context menu preparation should check markers around position, node at position can be changed. BTW, I think we should have unique id in spelling marker, e.g. uint64_t counter, to make SpellChecker::RepalceMisspelledWord() robdus.
I've updated the CL so it only has the flat tree version now. On 2017/07/05 at 05:25:23, yosin wrote: > BTW, I think we should have unique id in spelling marker, e.g. uint64_t counter, to make SpellChecker::RepalceMisspelledWord() robdus. If the text is edited while the menu opens and gets re-spellchecked, the IDs will change and the replacement will fail, right? Or do we not care about that case?
The CQ bit was checked by rlanday@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: ios-simulator on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)
On 2017/07/05 at 17:47:33, rlanday wrote: > I've updated the CL so it only has the flat tree version now. > > On 2017/07/05 at 05:25:23, yosin wrote: > > BTW, I think we should have unique id in spelling marker, e.g. uint64_t counter, to make SpellChecker::RepalceMisspelledWord() robdus. > > If the text is edited while the menu opens and gets re-spellchecked, the IDs will change and the replacement will fail, right? Or do we not care about that case? We don't care about such case. Since page author doesn't want to fix misspelled word, e.g. move word under selection to another place. Here is typical scenario of replacing misspell word with context menu. 1. User clicks right-mouse button at middle of a word with red wave 2. Blink picks up first misspelling marker 3. Blink assembles context menu data with replacement suggestions to show as menu items in context menu ~~IPC~~ 4. Browser shows context menu 5. User chooses one of suggested text 6. Browser ask Blink to replace misspelled word ~~IPC~~ 7. SpellChecker::ReplaceMisspelledWord() with user's choice. During IPC, Blink can change DOM tree somehow, e.g. running JS by timer, service worker, context menu event handler, etc. Note: context menu grabs mouse and keyboard, user's interaction can't change DOM tree. Using misspell word is yet another id, but it may work what user wants, e.g. User attempts to fix misspelled word "foo" with suggested word "bar", JS change "foo" to "<b>foo</b>", then Blink change "<b>foo</b>" to "<b>bar</b>". If we use uint64_t as id, id of "foo" is lost when move "foo" inside B. When we use misspelled word "foo" as id, we can replace it. There may be counter examples. We should study way to implement of misspell word fixing. 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.
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.
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. |