Bug 158503 - Finding text doesn't work across shadow boundary
Summary: Finding text doesn't work across shadow boundary
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords:
Depends on: 166299 166456
Blocks: 148695
  Show dependency treegraph
 
Reported: 2016-06-07 17:26 PDT by Ryosuke Niwa
Modified: 2017-01-06 02:31 PST (History)
4 users (show)

See Also:


Attachments
Fixes the bug (49.03 KB, patch)
2017-01-04 19:03 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from ews112 for mac-elcapitan (1.64 MB, application/zip)
2017-01-05 00:25 PST, Build Bot
no flags Details
Fixed the test (49.07 KB, patch)
2017-01-05 15:00 PST, Ryosuke Niwa
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2016-06-07 17:26:35 PDT
Finding text only looks for content outside the shadow tree.
Comment 1 Antti Koivisto 2016-06-08 00:43:15 PDT
TextIterator should walk the tree with ComposedTreeIterator.
Comment 2 Ryosuke Niwa 2016-06-08 02:07:23 PDT
(In reply to comment #1)
> TextIterator should walk the tree with ComposedTreeIterator.

I don't think we can make TextIterator always use ComposedTreeIterator because a whole bunch of code depends on it, some of which doesn't expect things to cross shadow boundaries.  But yeah, we probably need to teach TextIterator how to walk across shadow boundaries with a new option.
Comment 3 Antti Koivisto 2016-06-08 02:52:36 PDT
Using ComposedTreeIterator always should be fine, we can just manually skip over shadows when entering them is not wanted.
Comment 4 Ryosuke Niwa 2016-06-08 02:55:18 PDT
(In reply to comment #3)
> Using ComposedTreeIterator always should be fine, we can just manually skip
> over shadows when entering them is not wanted.

Or a slot for that matter.
Comment 5 Antti Koivisto 2016-06-08 02:59:00 PDT
if (it->isInShadowTree()) {
   ++it;
   continue; 
}

or

if (it->shadowRoot()) {
   it.traverseNextSkippingChildren():
   continue;
}

depending what is exactly wanted, basically.
Comment 6 Ryosuke Niwa 2016-06-08 03:01:46 PDT
Perhaps it would be useful to have some sort of a helper function that does this in ComposedTreeIterator?  It would be less error prone than having to do that everywhere we use ComposedTreeIterator.
Comment 7 Antti Koivisto 2016-06-08 03:09:41 PDT
Yeah, ComposedTreeIterator could have flags to traverse what is needed.

I suppose the real difference in TextIterator is really between author and UA shadow roots.
Comment 8 Ryosuke Niwa 2017-01-04 19:03:19 PST
Created attachment 298058 [details]
Fixes the bug
Comment 9 Ryosuke Niwa 2017-01-04 19:06:14 PST
Turns out that using ComposedTreeIterator is more trouble than useful here because of the difference that it needs to avoid traversing into user agent shadow trees, and we need to support two different modes: flat tree traversal & “light” DOM traversal.

For now, I added separate helper functions we should figure out a way to share more code between these helper functions, ones in FocusController.cpp and ComposedTreeIterator.
Comment 10 Build Bot 2017-01-04 22:05:04 PST
Comment on attachment 298058 [details]
Fixes the bug

Attachment 298058 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/2836201

New failing tests:
fast/shadow-dom/slot-crash.html
Comment 11 Build Bot 2017-01-05 00:25:31 PST
Comment on attachment 298058 [details]
Fixes the bug

Attachment 298058 [details] did not pass mac-debug-ews (mac):
Output: http://webkit-queues.webkit.org/results/2836623

New failing tests:
fast/shadow-dom/slot-crash.html
Comment 12 Build Bot 2017-01-05 00:25:35 PST
Created attachment 298073 [details]
Archive of layout-test-results from ews112 for mac-elcapitan

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews112  Port: mac-elcapitan  Platform: Mac OS X 10.11.6
Comment 13 Antti Koivisto 2017-01-05 02:05:31 PST
Comment on attachment 298058 [details]
Fixes the bug

View in context: https://bugs.webkit.org/attachment.cgi?id=298058&action=review

We could for example add ComposedTreeIterator::traverseNextSkippingUserAgentShadows(). I don't think that part is difficult.
 
The problem with this approach is that it is difficult to know if these changes are really sufficient and consistent. I see bunch of direct use of lastChild() and parentNode() that you are not changing. For example in TextIterator::exitNode() has

    Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;

Why is that ok?

> Source/WebCore/editing/TextIterator.cpp:400
> +// FIXME: Use ComposedTreeIterator instead. These functions are more expensive because they might do O(n) work.

Meaning TextIterator can now be O(n^2). It is not an unrealistic case, it is easy to have a slot with lots of nodes.

> Source/WebCore/editing/TextIterator.cpp:409
> +static inline Node* firstChildInFlatTreeIgnoringUserAgentShadow(Node& node)
> +{
> +    if (auto* shadowRoot = authorShadowRoot(node))
> +        return shadowRoot->firstChild();
> +    if (is<HTMLSlotElement>(node)) {
> +        if (auto* assignedNodes = downcast<HTMLSlotElement>(node).assignedNodes())
> +            return assignedNodes->at(0);
> +    }
> +    return node.firstChild();

This means we traverse to children if UA shadow tree is present. As I understand those are not considered flat tree nodes unless slotted. This might not cause problems in practice here but is inconsistent with naming.
Comment 14 Antti Koivisto 2017-01-05 02:27:07 PST
Still, it is progress but please fix the test.
Comment 15 Ryosuke Niwa 2017-01-05 13:00:06 PST
(In reply to comment #13)
> Comment on attachment 298058 [details]
> Fixes the bug
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=298058&action=review
> 
> We could for example add
> ComposedTreeIterator::traverseNextSkippingUserAgentShadows(). I don't think
> that part is difficult.
>  
> The problem with this approach is that it is difficult to know if these
> changes are really sufficient and consistent. I see bunch of direct use of
> lastChild() and parentNode() that you are not changing. For example in
> TextIterator::exitNode() has
> 
>     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
> 
> Why is that ok?

I removed that usage in https://trac.webkit.org/changeset/210131.
Comment 16 Ryosuke Niwa 2017-01-05 14:49:09 PST
(In reply to comment #13)
> Comment on attachment 298058 [details]
> Fixes the bug
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=298058&action=review
> 
> We could for example add
> ComposedTreeIterator::traverseNextSkippingUserAgentShadows(). I don't think
> that part is difficult.

We also need a method to go up to a parent. But really, we can’t have a method like that traverses to the next node in the tree order. TextIterator does a whole bunch of other book-keeping, and I couldn’t refactor them to just rely on a traversal function like traverseNext after spending one week working on it. Changing anything in advance to something saner would result in a bunch of assertion and test failures. So we really need methods to find the first child, the next sibling, and the parent.
Comment 17 Ryosuke Niwa 2017-01-05 15:00:30 PST
Created attachment 298140 [details]
Fixed the test
Comment 18 Antti Koivisto 2017-01-05 15:43:35 PST
An alternative factoring would be to wrap ComposedTreeIterator into another iterator (AuthorFlatTreeIterator or similar). But yes, replacing m_node with an iterator is more work.
Comment 19 Ryosuke Niwa 2017-01-05 17:45:52 PST
(In reply to comment #18)
> An alternative factoring would be to wrap ComposedTreeIterator into another
> iterator (AuthorFlatTreeIterator or similar). But yes, replacing m_node with
> an iterator is more work.

I’m not sure wrapping ComposedTreeIterator would work. We also need to find out whenever we’re moving out of an element to call TextIterator::exitNode.

I’m now looking at making copy & paste work but StylizedMarkupAccumulator also needs to do a similar tree traversal. And it obviously needs to emit closing tabs when it gets out of an element.

Maybe we need another Iterator that can traverse either “light” DOM tree or flat tree, and let the user handle whenever it gets out of a node as well as when it enters a node.
Comment 20 Ryosuke Niwa 2017-01-05 19:21:56 PST
Comment on attachment 298140 [details]
Fixed the test

Thanks for the review. Let’s land this for now, and we can figure out a way to refactor these iterator code later.
Comment 21 WebKit Commit Bot 2017-01-05 19:46:14 PST
Comment on attachment 298140 [details]
Fixed the test

Clearing flags on attachment: 298140

Committed r210432: <http://trac.webkit.org/changeset/210432>
Comment 22 WebKit Commit Bot 2017-01-05 19:46:18 PST
All reviewed patches have been landed.  Closing bug.
Comment 23 Antti Koivisto 2017-01-06 02:31:47 PST
(In reply to comment #19)
> I’m not sure wrapping ComposedTreeIterator would work. We also need to find
> out whenever we’re moving out of an element to call TextIterator::exitNode.

Several existing clients require this. For a simple example check RenderTreeUpdater::tearDownRenderers.

Push/pop callbacks could be a feature of the iterator too.