Bug 79197 – Implement ReifiedDOMTree traversal APIs for Shadow DOM.

• Component: DOM
• Status: RESOLVED FIXED

[Hayato Ito]

We need to have APIs which can traverse nodes in ReifiedDOMTree order.

[Hayato Ito]

Created attachment 128141 [details]
WIP

[Dimitri Glazkov (Google)]

Comment on attachment 128141 [details]
WIP

I wonder if we should attempt to make a separate class to keep all these functions from being Node members. Here's a strong indicator -- you add ReifiedDOMTree suffix to all of them :)

[Hayato Ito]

Yes, that's on my rader. Let me make a separate class in following WIP patches.

(In reply to comment #2)
> (From update of attachment 128141 [details])
> I wonder if we should attempt to make a separate class to keep all these functions from being Node members. Here's a strong indicator -- you add ReifiedDOMTree suffix to all of them :)

[Hayato Ito]

Created attachment 129007 [details]
wip. add tests. make a separate class. needs more cleanup

[Dimitri Glazkov (Google)]

Comment on attachment 129007 [details]
wip. add tests. make a separate class. needs more cleanup

This is starting to look nice!

[Hayato Ito]

*** Bug 64072 has been marked as a duplicate of this bug. ***

[Hayato Ito]

Created attachment 130360 [details]
WIP. clean-up APIs by use case driven.

[Hayato Ito]

WIP. Still needs more clean-ups. The current code is messy, but some use cases are starting to work nicely. I'd like work on this patch in more use-case driven way. The current use cases on my rader are:

 - Event dispatch
 - Focus Navigation

These two use cases cover almost every APIs in ReifiedTreeTraversal.
Let me continue clean-up tanks and add more comprehensive layout tests.

We need to split this patch into several small patches for easy reviewes.

[Dimitri Glazkov (Google)]

Comment on attachment 130360 [details]
WIP. clean-up APIs by use case driven.

This is starting to look really nice. I think to land this, we'll need to split this up into smaller chunks. How about this for a plan?
1) Introduce a simpler ReifiedTreeTraversal class, which only implements adjustedParentNode
2) change EventDispatcher to use it
3) Add FocusScope
4) Add logic to ReifitedTreeTraversal to use it
5) ...
6) profit.

WDYT?

[Dimitri Glazkov (Google)]

(In reply to comment #9)
> (From update of attachment 130360 [details])
> This is starting to look really nice. I think to land this, we'll need to split this up into smaller chunks. How about this for a plan?
> 1) Introduce a simpler ReifiedTreeTraversal class, which only implements adjustedParentNode
> 2) change EventDispatcher to use it
> 3) Add FocusScope
> 4) Add logic to ReifitedTreeTraversal to use it
> 5) ...
> 6) profit.
> 
> WDYT?

Also, Morrita-san, Kawanaka-san -- the ReifiedTreeTraversal is the iterator class I had in mind on bug 80020. Does this make sense?

[Hayato Ito]

I agree. We should land the small part of ReifiedTreeTraversal at first , along with a client which uses APIs.
The first candidate is a EventDispatcher, which only requires parentNodeXXX APIs.

My biggest concern about EventDispatcher is the performance.
We need to make sure that it doesn't cause any *noticeable* performance regression.

I am not sure what is a recommended way to measure the performance regression for these types of changes in WebKit. It'd be nice to have a good benchmark tool to find any blocking issue which prevents this patch from landing.


(In reply to comment #9)
> (From update of attachment 130360 [details])
> This is starting to look really nice. I think to land this, we'll need to split this up into smaller chunks. How about this for a plan?
> 1) Introduce a simpler ReifiedTreeTraversal class, which only implements adjustedParentNode
> 2) change EventDispatcher to use it
> 3) Add FocusScope
> 4) Add logic to ReifitedTreeTraversal to use it
> 5) ...
> 6) profit.
> 
> WDYT?

[Dimitri Glazkov (Google)]

(In reply to comment #11)
> I agree. We should land the small part of ReifiedTreeTraversal at first , along with a client which uses APIs.
> The first candidate is a EventDispatcher, which only requires parentNodeXXX APIs.
> 
> My biggest concern about EventDispatcher is the performance.
> We need to make sure that it doesn't cause any *noticeable* performance regression.
> 
> I am not sure what is a recommended way to measure the performance regression for these types of changes in WebKit. It'd be nice to have a good benchmark tool to find any blocking issue which prevents this patch from landing.

Event dispatch is easy to benchmark, since there aren't too many branches. You can write one fairly easily. Build a DOM tree that's N nodes deep and then run the benchmark for increasing N. Repeat for all branches where you make the code changes. Record before and after. Post benchmark and results in the patch. I wrote a bunch of microbenchmarks like this for various bits when refactoring shadow DOM.

> 
> 
> (In reply to comment #9)
> > (From update of attachment 130360 [details] [details])
> > This is starting to look really nice. I think to land this, we'll need to split this up into smaller chunks. How about this for a plan?
> > 1) Introduce a simpler ReifiedTreeTraversal class, which only implements adjustedParentNode
> > 2) change EventDispatcher to use it
> > 3) Add FocusScope
> > 4) Add logic to ReifitedTreeTraversal to use it
> > 5) ...
> > 6) profit.
> > 
> > WDYT?

[Hayato Ito]

Created attachment 132022 [details]
wip

[Hayato Ito]

I've changed the plan. Let me split this up into smaller chunks as follows:

A plan:
1) Land ReifiedTreeTraversal class and test.
2) Land updated FocusController, which follows shadow DOM navigation order, using ReifiedTreeTraversal.
3) Land EventDispatcher (and benchmark), which follows new Shadow DOM spec.
4)
5) ...
6) profit.

[Hayato Ito]

Created attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

[Hayato Ito]

The first one has come, which contains only Reified Tree Traversal APIs and its test.

Although I've updated the patch so that we can build this on other platforms, I think the patch is ready for review.

[Hayato Ito]

(In reply to comment #16)
> The first one has come, which contains only Reified Tree Traversal APIs and its test.
> 
> Although I've updated the patch so that we can build this on other platforms, I think the patch is ready for review.

s/I've updated/I'll update/.

[Hayato Ito]

I am afraid that patch of ReifiedTreeTraversal APIs is a bit bigger for a review. I am happy to split this patch into small patches if it is required.

(In reply to comment #17)
> (In reply to comment #16)
> > The first one has come, which contains only Reified Tree Traversal APIs and its test.
> > 
> > Although I've updated the patch so that we can build this on other platforms, I think the patch is ready for review.
> 
> s/I've updated/I'll update/.

[Early Warning System Bot]

Comment on attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

Attachment 132033 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/11953774

[Early Warning System Bot]

Comment on attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

Attachment 132033 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/11951732

[Build Bot]

Comment on attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

Attachment 132033 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/11955597

[Gyuyoung Kim]

Comment on attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

Attachment 132033 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/11956606

[Build Bot]

Comment on attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

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

[Gustavo Noronha (kov)]

Comment on attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.

Attachment 132033 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/11955617

[Hayato Ito]

Created attachment 132207 [details]
to get required symbols.

[Hayato Ito]

I can improve the performance of APIs by making some functions inline. But as the first wave, I'd like to leave it later since there is no actual clients yet and I'd like to focus on making sure that APIs works correctly.

Later I'll work on improving performance using actual use cases, like a FocusNavigation and EventDispatcher.

(In reply to comment #25)
> Created an attachment (id=132207) [details]
> to get required symbols.

[Dimitri Glazkov (Google)]

(In reply to comment #14)

> 6) profit.

I like that last point the best.

[Hayato Ito]

Created attachment 132975 [details]
retry to get required symbols.

[Hayato Ito]

Created attachment 132991 [details]
retry to get required symbols.

[Build Bot]

Comment on attachment 132991 [details]
retry to get required symbols.

Attachment 132991 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12072481

[Hayato Ito]

Created attachment 133178 [details]
fix win build hopefully.

[Build Bot]

Comment on attachment 133178 [details]
fix win build hopefully.

Attachment 133178 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12035842

[Hayato Ito]

I've done a micro bench mark for Reified Tree Traversal APIs.
Used benchmark is here: https://bugs.webkit.org/show_bug.cgi?id=81495

The result is:

Benchmark for Reified Tree Traversal APIs.
TraverseNext in 10000000 times.

Traverse tree which contains ShadowHost:
 took 57.8ms.  with TraverseNextNode
 took 426ms. with TraverseNextNodeInReifiedTree

Traverse tree which does not contain ShadowHost:
 took 77.6ms.  with TraverseNextNode
 took 358.6ms. with TraverseNextNodeInReifiedTree


The result says that ReifiedTreeTreversal::traverseNextNode is about 8 times as slow as Node::traverseNextNode.

That's very good starting point for me. Let me improve the performance later as another bug.

[Dimitri Glazkov (Google)]

Comment on attachment 133178 [details]
fix win build hopefully.

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

This is really close to being done. A lot of awesome work, Hayato-san. I spent a lot of time staring at this code, trying to make sure you're doing the right thing. Overall, the machinery looks good. Pending a few naming/stylistic comments and build fixes, we can land this.

One question: would ReifiedTreeTraversal be better viewed as a cursor pattern device, like a Walker? Instead of all public functions being static, we give it a node in constructor, then operate on that node with the functions. WDYT? Will this be useful?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:83
> +    // FIXME: Add an assertion once InsertionPoint have isActive() function.

URL of the bug?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:90
> +    Node* child = traverseLightChildren(node, direction);
> +    return child;

Can just be return traverseLightChildren?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:101
> +Node* ReifiedTreeTraversal::traverseMe(const Node* node, ReifiedTreeTraversalDirection direction)

traverseMe -> traverseNode?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:131
> +Node* ReifiedTreeTraversal::traverseSiblingMaybeBackToInsertionPoint(const Node* node, ReifiedTreeTraversalDirection direction)

Maybe -> Or

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:155
> +Node* ReifiedTreeTraversal::traverseBackingToYoungerShadowRoot(const Node* node, ReifiedTreeTraversalDirection direction)

BackingTo -> BackTo? or BackInto?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:177
> +Node* ReifiedTreeTraversal::traverseMeEscapingFallbackContents(const Node* node, CrossedUpperBoundary& crossed)

Me -> Node

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:197
> +    // FIXME: Do not use 'unsed' parameter.

UNUSED_PARAM?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:216
> +Node* ReifiedTreeTraversal::parentNodeMaybeBackToInsertionPoint(const Node* node, CrossedUpperBoundary& crossed)

Should you set crossed = Crossed at the start?

> Source/WebCore/dom/ReifiedTreeTraversal.cpp:227
> +    if (Node* parent = node->parentNode()) {

Ditto?

> Source/WebCore/dom/ReifiedTreeTraversal.h:40
> +// FIXME: Make some functions inline to optimise the performance.

File a bug and put URL here?

> Source/WebCore/dom/ReifiedTreeTraversal.h:62
> +    // FIXME: An 'adjusted' is not good name for general use case. Rename this.

File a bug and put URL here?

[Hayato Ito]

Thank you for the review. Let me address your comments.

(In reply to comment #34)
> (From update of attachment 133178 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=133178&action=review
> 
> This is really close to being done. A lot of awesome work, Hayato-san. I spent a lot of time staring at this code, trying to make sure you're doing the right thing. Overall, the machinery looks good. Pending a few naming/stylistic comments and build fixes, we can land this.
> 
> One question: would ReifiedTreeTraversal be better viewed as a cursor pattern device, like a Walker? Instead of all public functions being static, we give it a node in constructor, then operate on that node with the functions. WDYT? Will this be useful?

Yes, we can. That's one of ideas I thought from the beginning. Actually I was tempted to do when I was forced to type a long-name static function when I used APIs in FocusController, but I gave up the idea without deep thinking since it does not make code shorter much.

Current approach:

for (Node* node = start; node; node = ReifiiedTreeTraversal::traverseNextNode(node)) {
  // ..
}

Cursor pattern:

for (ReifinedTreeAwareNode node(start); node.valid(); node.traverseNextNode()) {
  // We should use 'get()' inside of for loop to get a backing node to pass Node to another function.
  Node* n = node.get().
}

But I guess many WebKit folks prefer the latter since it looks elegant, right? Either is okay for me. I can not see any reason which causes performance regressions by making it cursor pattern.

I am happy to provide a 'cursor patten version' and get rid of current 'ugly' static function approach. That's not difficult task since there is no clients which started to use APIs except for FocusController. Before starting to work, I'd like to compare both versions and get more evidence to judge which is better. Can I work on 'cursor pattern version' as another bug? Let me file a bug for that.

[Hayato Ito]

For cursor pattern, I've filed a bug as https://bugs.webkit.org/show_bug.cgi?id=82009

[Dimitri Glazkov (Google)]

sounds good.

[Hayato Ito]

Comment on attachment 133178 [details]
fix win build hopefully.

I've addressed the comments. Let me upload the new patch.

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

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:83
>> +    // FIXME: Add an assertion once InsertionPoint have isActive() function.
> 
> URL of the bug?

Done.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:90
>> +    return child;
> 
> Can just be return traverseLightChildren?

Done.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:101
>> +Node* ReifiedTreeTraversal::traverseMe(const Node* node, ReifiedTreeTraversalDirection direction)
> 
> traverseMe -> traverseNode?

Done. 'Me' has been used since this function existed in WebCore::Node once. 'Me' is inappropriate anymore.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:131
>> +Node* ReifiedTreeTraversal::traverseSiblingMaybeBackToInsertionPoint(const Node* node, ReifiedTreeTraversalDirection direction)
> 
> Maybe -> Or

Done.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:155
>> +Node* ReifiedTreeTraversal::traverseBackingToYoungerShadowRoot(const Node* node, ReifiedTreeTraversalDirection direction)
> 
> BackingTo -> BackTo? or BackInto?

Done. I chose 'BackTo' for consistency.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:177
>> +Node* ReifiedTreeTraversal::traverseMeEscapingFallbackContents(const Node* node, CrossedUpperBoundary& crossed)
> 
> Me -> Node

Done.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:197
>> +    // FIXME: Do not use 'unsed' parameter.
> 
> UNUSED_PARAM?

Done.

>> Source/WebCore/dom/ReifiedTreeTraversal.cpp:216
>> +Node* ReifiedTreeTraversal::parentNodeMaybeBackToInsertionPoint(const Node* node, CrossedUpperBoundary& crossed)
> 
> Should you set crossed = Crossed at the start?

Yes, we should. I set crossed = NotCrossed at the start of parentNode(const Node* node, CrossedupperBoundary& crossed) and inserted ASSERT(crossed == NotCrossed) into other functions.

>> Source/WebCore/dom/ReifiedTreeTraversal.h:40
>> +// FIXME: Make some functions inline to optimise the performance.
> 
> File a bug and put URL here?

Done.

>> Source/WebCore/dom/ReifiedTreeTraversal.h:62
>> +    // FIXME: An 'adjusted' is not good name for general use case. Rename this.
> 
> File a bug and put URL here?

Done.

[Hayato Ito]

Created attachment 133434 [details]
update

[Build Bot]

Comment on attachment 133434 [details]
update

Attachment 133434 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12122471

[Hayato Ito]

Created attachment 133440 [details]
fix vcproj

[Hayato Ito]

Created attachment 133447 [details]
fix adjustedParentNode

[Dimitri Glazkov (Google)]

Comment on attachment 133447 [details]
fix adjustedParentNode

ok.

[WebKit Review Bot]

Comment on attachment 133447 [details]
fix adjustedParentNode

Rejecting attachment 133447 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 2

Last 500 characters of output:
1 succeeded at 1886 (offset -9 lines).
patching file LayoutTests/platform/qt/Skipped
patching file LayoutTests/platform/win/Skipped
Hunk #1 succeeded at 1469 (offset 1 line).
patching file LayoutTests/platform/wincairo/Skipped
patching file LayoutTests/platform/wk2/Skipped
patching file ChangeLog
Hunk #1 succeeded at 1 with fuzz 3.

Failed to run "[u'/mnt/git/webkit-commit-queue/Tools/Scripts/svn-apply', u'--force', u'--reviewer', u'Dimitri Gl..." exit_code: 1 cwd: /mnt/git/webkit-commit-queue/

Full output: http://queues.webkit.org/results/12129664

[Hayato Ito]

Created attachment 133730 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 133730 [details]
Patch for landing

Clearing flags on attachment: 133730

Committed r112055: <http://trac.webkit.org/changeset/112055>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.