Traversing Shadow DOM Tree

This page explains how to use ​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 ​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