Changes between Initial Version and Version 1 of TraversingShadowDOMTree

Timestamp:

May 8, 2012 6:05:44 PM (12 years ago)

Author:

hayato@chromium.org

Comment:

--

TraversingShadowDOMTree

@@ +1 @@
+
+= Traversing Shadow DOM Tree =
+
+This page explains how to use [https://trac.webkit.org/browser/trunk/Source/WebCore/dom/ComposedShadowTreeWalker.cpp ComposedShadowTreeWalker] ComposedShadowTreeWalker class, which enables you to traverse nodes in composed shadow tree order.
+
+= Background =
+
+A composed shadow tree is a result of applying a node distribution algorithm described in [http://dvcs.w3.org/hg/webcomponents/raw-file/tip/spec/shadow/index.html#shadow-dom-subtrees Shadow DOM spec]. That’s ‘one big tree’ used in rendering. There are some use cases other than rendering where we want to traverse nodes in composed shadow tree order, not original DOM tree order. To achieve that, instead of creating composed shadow tree in memory physically, I’ve decided to provide APIs which enable you to traverse nodes in composed shadow tree order as if that were physically constructed in memory. You don’t have to know any background structure of composed shadow tree as long as you use the APIs.
+
+= Examples =
+
+Suppose we are given the following DOM tree:
+
+{{{
+A
+└──B─────[SR1]
+   ├─C     └──G──────────────[SR2]
+   │ └─D      ├─<H select=C>    ├─<K select=H,J>
+   └─E        ├─I               ├─L
+     └─F      └─J               └─<M select=None>
+                                   └─N
+
+  [SR]: ShadowRoot
+  <X select=Y>: InsertionPoint, called X, which selects Y.
+}}}
+
+Applying a node distribution algorithm to the given DOM tree, a composed shadow tree would be:
+
+{{{
+A
+└──B
+   │
+  [SR1]
+   │
+   └─G 
+     │
+    [SR2]
+     │
+     ├─C
+     │ └─D
+     ├─J
+     ├─L
+     └─N
+}}}
+
+
+= API Usage =
+
+If you want to traverse nodes in composed shadow tree order, starting node A, use the following idiom:
+
+{{{
+for (ComposedShadowDOMTreeWalker walker(nodeA); walker.get(); walker.next()) {
+    printNode(walker.get())
+}
+}}}
+
+This will print nodes in the following order: A, B, G, C, D, J, L, N
+
+ComposedShadowTreeWalker receives a starting node in its constructor. Other than next() member function, ComposedShadowTreeWalker provides other traversal functions such as:
+
+  * walker.previous()
+  * walker.parent()
+  * walker.nextSibling()
+  * walker.previousSibling()
+  * walker.firstChild()
+  * walker.lastChild()
+
+These provide similar functionality to functions defined in WebCore::Node, but will traverse  composed shadow tree order, not original DOM tree order.
+These function doesn’t return the result node. All returns ‘void’. Instead, these will update the walker’s internal state, a current visited node. You can get the current visited node by walker.get() function.
+
+The following is the example of traversing.
+
+
+||  || A  ||   B ||  C ||  E ||  G ||  I ||  J ||  L ||  N ||
+||next() || B ||  G ||  D ||  F ||  C ||  null ||   L ||  N ||  null ||
+||previous() || null ||   A ||  null ||   null ||    B ||  null ||   D ||  J ||  L ||
+||firstChild() ||  B ||  G  ||   D ||   F ||  C  ||  null || null || null ||  null ||
+||parent() ||           null   ||         A   ||    G ||  null ||   B  ||     null ||   G   ||    G ||  G ||
+||nextSibling()  ||      null  ||          null ||   J ||  null ||   null ||   null ||   L  ||     N ||  null ||
+
+
+Notes:
+1. Some nodes (E, F and I) do not participate in the composed shadow tree because they are children (or descendants) of shadow host, but are not distributed. These nodes are treated as separated ‘islands’. e.g. E’s parent() is null, not B.
+2. You could not pass an active InsertionPoint (H, K and M) or a ShadowRoot as a starting node. That should trigger an assertion error.
+
+
+= Traverse Policy = 
+
+There are some use cases where we want to disallow walker to cross an upper shadow boundary. We can change ‘traversing policy’ by passing Policy to ComposedShadowTreeWalker’s constructor. For example, if we want to traverse composed shadow tree, resolving InsertionPoints automatically, but don’t want to cross upper boundary, you can create a walker like this:
+
+{{{
+ComposedShadowTreeWalker walker(startingNode, ComposedShadowTreeWalker::DoNotCrossUpperBoundary)
+}}}
+
+If a walker is constructed with a policy of DoNotCrossUpperBoundary, youngest ShadowRoots will be also a candidate of visiting nodes and won’t be skipped. Youngest ShadowRoots will act as a top-most node in scope, like a Document node in original DOM tree.
+
+The following is the result in case of DoNotCrossUpperBoundary policy:
+
+||  || B  || SR1 ||  G || SR2 || C ||
+|| firstChild() || null ||  G ||  null ||   C ||  D ||
+|| parent() ||     A  ||    null  ||     SR1 || null ||   SR2 ||
+|| next()   ||     null ||  G   ||       null  ||      C ||  D ||
+|| previous() ||   A  ||    null ||      SR1   ||      null ||   SR2 ||
+
+= Hosting Multiple Shadow Roots = 
+
+Although I omitted the hosting multiple shadow roots case from the example, ComposedShadowTreeWalker supports multiple shadow roots. <shadow> elements are resolved transparently.
+
+= Error cases =
+
+* In Policy of CrossBounary (default):
+You cannot pass an active InsertionPoint or ShadowRoot as a starting node.
+
+* In Policy of DoNotCrossUpperBoundary
+You cannot pass an active InsertionPoint or non-youngest ShadowRoot as a starting node.
+
+You cannot call any traversal functions if the current visited node is null.
+
+= Performance = 
+
+To be compared to Node::traverseNextNode() function, walker::next() is about 6 times slower. The result of a micro benchmark is here:
+https://bugs.webkit.org/show_bug.cgi?id=79197#c33
+* The result is based on old APIs. The current walker is a bit faster than old APIs.
+I am going to improve the performance here: https://bugs.webkit.org/show_bug.cgi?id=82702
+
+= Actual Clients = 
+
+== Focus Controller ==
+
+FocusController (*1) started to use ComposedShadowTreeWalker to traverse composed shadow DOM tree. That’s good example about how to use APIs. That also uses DoNotCrossUpperBoundary policy since Focus navigation should be scoped in each Shadow DOM subtree according to the current Shadow DOM spec. Although FocusNavigation is complex since it should consider each shadow DOM subteee as a ‘scope’, the APIs made implementations much easier since much complex works are done within APIs.
+
+*1: https://trac.webkit.org/browser/trunk/Source/WebCore/page/FocusController.cpp
+
+== Event Dispatcher == 
+
+EventDispatcher will be the next client of the APIs. Work-in-progress patch is here:
+https://bugs.webkit.org/show_bug.cgi?id=78586