Bug 79197

Summary: Implement ReifiedDOMTree traversal APIs for Shadow DOM.
Product: WebKit Reporter: Hayato Ito <hayato>
Component: DOMAssignee: Hayato Ito <hayato>
Status: RESOLVED FIXED    
Severity: Normal CC: dglazkov, dominicc, gns, morrita, rakuco, rolandsteiner, shinyak, webkit.review.bot, xan.lopez
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 78313, 78596, 80405    
Bug Blocks: 78585, 82019, 82022    
Attachments:
Description Flags
WIP
none
wip. add tests. make a separate class. needs more cleanup
none
WIP. clean-up APIs by use case driven.
none
wip
none
Reified Tree Traversal APIs. Let me know required symbols on other ports.
none
to get required symbols.
none
retry to get required symbols.
none
retry to get required symbols.
none
fix win build hopefully.
none
update
none
fix vcproj
none
fix adjustedParentNode
none
Patch for landing none

Description Hayato Ito 2012-02-21 22:34:45 PST
We need to have APIs which can traverse nodes in ReifiedDOMTree order.
Comment 1 Hayato Ito 2012-02-21 23:30:41 PST
Created attachment 128141 [details]
WIP
Comment 2 Dimitri Glazkov (Google) 2012-02-22 09:16:17 PST
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 :)
Comment 3 Hayato Ito 2012-02-22 23:17:53 PST
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 :)
Comment 4 Hayato Ito 2012-02-27 03:54:43 PST
Created attachment 129007 [details]
wip. add tests. make a separate class. needs more cleanup
Comment 5 Dimitri Glazkov (Google) 2012-02-27 10:13:01 PST
Comment on attachment 129007 [details]
wip. add tests. make a separate class. needs more cleanup

This is starting to look nice!
Comment 6 Hayato Ito 2012-02-27 19:02:50 PST
*** Bug 64072 has been marked as a duplicate of this bug. ***
Comment 7 Hayato Ito 2012-03-06 05:22:13 PST
Created attachment 130360 [details]
WIP. clean-up APIs by use case driven.
Comment 8 Hayato Ito 2012-03-06 05:23:28 PST
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.
Comment 9 Dimitri Glazkov (Google) 2012-03-06 08:51:07 PST
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?
Comment 10 Dimitri Glazkov (Google) 2012-03-06 08:54:22 PST
(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?
Comment 11 Hayato Ito 2012-03-07 04:04:03 PST
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?
Comment 12 Dimitri Glazkov (Google) 2012-03-07 09:53:19 PST
(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?
Comment 13 Hayato Ito 2012-03-15 05:10:45 PDT
Created attachment 132022 [details]
wip
Comment 14 Hayato Ito 2012-03-15 05:19:28 PDT
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.
Comment 15 Hayato Ito 2012-03-15 06:23:48 PDT
Created attachment 132033 [details]
Reified Tree Traversal APIs. Let me know required symbols on other ports.
Comment 16 Hayato Ito 2012-03-15 06:26:33 PDT
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.
Comment 17 Hayato Ito 2012-03-15 06:29:44 PDT
(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/.
Comment 18 Hayato Ito 2012-03-15 06:37:48 PDT
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/.
Comment 19 Early Warning System Bot 2012-03-15 06:38:06 PDT
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
Comment 20 Early Warning System Bot 2012-03-15 06:40:22 PDT
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
Comment 21 Build Bot 2012-03-15 06:44:13 PDT
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
Comment 22 Gyuyoung Kim 2012-03-15 06:47:10 PDT
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
Comment 23 Build Bot 2012-03-15 07:13:51 PDT
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
Comment 24 Gustavo Noronha (kov) 2012-03-15 07:42:00 PDT
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
Comment 25 Hayato Ito 2012-03-15 23:10:27 PDT
Created attachment 132207 [details]
to get required symbols.
Comment 26 Hayato Ito 2012-03-15 23:21:56 PDT
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.
Comment 27 Dimitri Glazkov (Google) 2012-03-16 09:58:27 PDT
(In reply to comment #14)

> 6) profit.

I like that last point the best.
Comment 28 Hayato Ito 2012-03-20 22:51:22 PDT
Created attachment 132975 [details]
retry to get required symbols.
Comment 29 Hayato Ito 2012-03-21 01:44:39 PDT
Created attachment 132991 [details]
retry to get required symbols.
Comment 30 Build Bot 2012-03-21 10:31:13 PDT
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
Comment 31 Hayato Ito 2012-03-21 20:40:32 PDT
Created attachment 133178 [details]
fix win build hopefully.
Comment 32 Build Bot 2012-03-21 21:01:30 PDT
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
Comment 33 Hayato Ito 2012-03-22 00:25:31 PDT
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.
Comment 34 Dimitri Glazkov (Google) 2012-03-22 10:33:50 PDT
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?
Comment 35 Hayato Ito 2012-03-22 20:48:07 PDT
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.
Comment 36 Hayato Ito 2012-03-22 20:58:16 PDT
For cursor pattern, I've filed a bug as https://bugs.webkit.org/show_bug.cgi?id=82009
Comment 37 Dimitri Glazkov (Google) 2012-03-22 21:16:23 PDT
sounds good.
Comment 38 Hayato Ito 2012-03-22 23:34:29 PDT
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.
Comment 39 Hayato Ito 2012-03-22 23:45:15 PDT
Created attachment 133434 [details]
update
Comment 40 Build Bot 2012-03-23 00:11:43 PDT
Comment on attachment 133434 [details]
update

Attachment 133434 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12122471
Comment 41 Hayato Ito 2012-03-23 00:53:08 PDT
Created attachment 133440 [details]
fix vcproj
Comment 42 Hayato Ito 2012-03-23 02:07:38 PDT
Created attachment 133447 [details]
fix adjustedParentNode
Comment 43 Dimitri Glazkov (Google) 2012-03-23 11:44:19 PDT
Comment on attachment 133447 [details]
fix adjustedParentNode

ok.
Comment 44 WebKit Review Bot 2012-03-25 21:52:58 PDT
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
Comment 45 Hayato Ito 2012-03-25 22:29:06 PDT
Created attachment 133730 [details]
Patch for landing
Comment 46 WebKit Review Bot 2012-03-25 23:44:35 PDT
Comment on attachment 133730 [details]
Patch for landing

Clearing flags on attachment: 133730

Committed r112055: <http://trac.webkit.org/changeset/112055>
Comment 47 WebKit Review Bot 2012-03-25 23:44:49 PDT
All reviewed patches have been landed.  Closing bug.