Author: hayato@chromium.org, some edits by masonf@chromium.org
The renderer/core/dom
directory contains the implementation of DOM.
Basically, this directory should contain only a file which is related to DOM Standard. However, for historical reasons, renderer/core/dom
directory has been used as if it were misc directory. As a result, unfortunately, this directory contains a lot of files which are not directly related to DOM.
Please don‘t add unrelated files to this directory any more. We are trying to organize the files so that developers wouldn’t get confused at seeing this directory.
See the spreadsheet, as a rough plan to organize Source/core/dom files.
The classification in the spreadsheet might be wrong. Please update the spreadsheet, and move files if you can, if you know more appropriate places for each file.
See crbug.com/738794 for tracking our efforts.
In this README, we draw a tree in left-to-right direction in ascii-art notation. A
is the root of the tree.
A ├───B ├───C │ ├───D │ └───E └───F
Node
is a base class of all kinds of nodes in a node tree. Each Node
has following 3 pointers (but not limited to):
parent_or_shadow_host_node_
: Points to the parent (or the shadow host if it is a shadow root; explained later)previous_
: Points to the previous siblingnext_
: Points to the next siblingContainerNode
, from which Element
extends, has additional pointers for its child:
first_child_
: The meaning is obvious.last_child_
: Nit.That means:
Further info:
Node
, ContainerNode
You can traverse a tree manually:
// In C++ // Traverse a children. for (Node* child = parent.firstChild(); child; child = child->nextSibling()) { ... } // ... // Traverse nodes in tree order, depth-first traversal. void foo(const Node& node) { ... for (Node* child = node.firstChild(); child; child = child->nextSibling()) { foo(*child); // Recursively } }
Tree order is:
However, traversing a tree in this way might be error-prone. Instead, you can use NodeTraversal
and ElementTraversal
. They provides a C++11's range-based for loops, such as:
// In C++ for (Node& child : NodeTraversal::childrenOf(parent) { ... }
e.g. Given a parent A, this traverses B, C, and F in this order.
// In C++ for (Node& node : NodeTraversal::startsAt(root)) { ... }
e.g. Given the root A, this traverses A, B, C, D, E, and F in this order.There are several other useful range-based for loops for each purpose. The cost of using range-based for loops is zero because everything can be inlined.
Further info:
NodeTraversal
and ElementTraversal
(more type-safe version)A shadow tree is a node tree whose root is a ShadowRoot
. From web developer's perspective, a shadow root can be created by calling element.attachShadow{ ... }
API. The element here is called a shadow host, or just a host if the context is clear.
For example, given the example node tree:
A ├───B ├───C │ ├───D │ └───E └───F
Web developers can create a shadow root, and manipulate the shadow tree in the following way:
// In JavaScript const b = document.querySelector('#B'); const shadowRoot = b.attachShadow({ mode: 'open' }); const sb = document.createElement('div'); shadowRoot.appendChild(sb);
The resulting shadow tree would be:
shadowRoot └── sb
The shadowRoot has one child, sb. This shadow tree is being attached to B:
A └── B ├──/shadowRoot │ └── sb ├── C │ ├── D │ └── E └── F
In this README, a notation (──/
) is used to represent a shadowhost-shadowroot relationship, in a composed tree. A composed tree will be explained later. A shadowhost-shadowroot is 1:1 relationship.
Though a shadow root has always a corresponding shadow host element, a light tree and a shadow tree should be considered separately, from a node tree's perspective. (──/
) is NOT a parent-child relationship in a node tree.
For example, even though B hosts the shadow tree, shadowRoot is not considered as a child of B. The means the following traversal:
// In C++ for (Node& node : NodeTraversal::startsAt(A)) { ... }
traverses only A, B, C, D, E and F nodes. It never visits shadowRoot nor sb. NodeTraversal never cross a shadow boundary, ──/
.
Further info:
ShadowRoot
Element#attachShadow
Document
and ShadowRoot
are always the root of a node tree. BothDocument
and ShadowRoot
implements TreeScope
.
TreeScope
maintains a lot of information about the underlying tree for efficiency. For example, TreeScope has a id-to-element mapping, as TreeOrderedMap
, so that querySelector('#foo')
can find an element whose id attribute is “foo” in O(1). In other words, root.querySelector('#foo')
can be slow if that is used in a node tree whose root is not TreeScope
.
Each Node
has tree_scope_
pointer, which points to:
The means tree_scope_
pointer is always non-null (except for while in a DOM mutation), but it doesn‘t always point to the node’s root.
Since each node doesn't have a pointer which always points to the root, Node::getRootNode(...)
may take O(N) if the node is neither in a document tree nor in a shadow tree. If the node is in TreeScope (Node#IsInTreeScope()
can tell it), we can get the root in O(1).
Each node has flags, which is updated in DOM mutation, so that we can tell whether the node is in a document tree, in a shadow tree, or in none of them, by using Node::IsInDocumentTree()
and/or Node::IsInShadowTree()
.
If you want to add new features to Document
, Document
might be a wrong place to add. Instead, please consider to add functionality to TreeScope
. We want to treat a document tree and a shadow tree equally as much as possible.
document └── a1 ├──/shadowRoot1 │ └── s1 └── a2 └── a3 document-fragment └── b1 ├──/shadowRoot2 │ └── t2 └── b2 └── b3
document.createElement(...)
(except for Document and ShadowRoot). That means each node's owner document is document.node | node's root | node's _tree_scope points to: |
---|---|---|
document | document (self) | document (self) |
a1 | document | document |
a2 | document | document |
a3 | document | document |
shadowRoot1 | shadowRoot1 (self) | shadowRoot1 (self) |
s1 | shadowRoot1 | shadowRoot1 |
document-fragment | document-fragment (self) | document |
b1 | document-fragment | document |
b2 | document-fragment | document |
b3 | document-fragment | document |
shadowRoot2 | shadowRoot2 (self) | shadowRoot2 (self) |
t1 | shadowRoot2 | shadowRoot2 |
Further Info:
tree_scope.h
, tree_scope.cc
Node#GetTreeScope()
, Node#ContainingTreeScope()
, Node#IsInTreeScope()
In the previous picture, you might think that more than one node trees, a document tree and a shadow tree, were connected to each other. That is true in some sense. We call this super tree as composed tree, which is a tree of trees.
The following is a complex example:
document ├── a1 (host) │ ├──/shadowRoot1 │ │ └── b1 │ └── a2 (host) │ ├──/shadowRoot2 │ │ ├── c1 │ │ │ ├── c2 │ │ │ └── c3 │ │ └── c4 │ ├── a3 │ └── a4 └── a5 └── a6 (host) └──/shadowRoot3 └── d1 ├── d2 ├── d3 (host) │ └──/shadowRoot4 │ ├── e1 │ └── e2 └── d4 (host) └──/shadowRoot5 ├── f1 └── f2
If you see this carefully, you can notice that this composed tree is composed of 6 node trees; 1 document tree and 5 shadow trees:
document tree
document ├── a1 (host) │ └── a2 (host) │ ├── a3 │ └── a4 └── a5 └── a6 (host)
shadow tree 1
shadowRoot1 └── b1
shadow tree 2
shadowRoot2 ├── c1 │ ├── c2 │ └── c3 └── c4
shadow tree 3
shadowRoot3 └── d1 ├── d2 ├── d3 (host) └── d4 (host)
shadow tree 4
shadowRoot4 ├── e1 └── e2
shadow tree 5
shadowRoot5 ├── f1 └── f2
If we consider each node tree as node of a super-tree, we can draw a super-tree as such:
document ├── shadowRoot1 ├── shadowRoot2 └── shadowRoot3 ├── shadowRoot4 └── shadowRoot5
Here, a root node is used as a representative of each node tree; A root node and a node tree itself can be sometimes exchangeable in explanations.
We call this kind of a super-tree (a tree of node trees) a composed tree. The concept of a composed tree is very useful to understand how Shadow DOM's encapsulation works.
DOM Standard defines the following terminologies:
For example,
To honor Shadow DOM's encapsulation, we have a concept of visibility relationship between two nodes.
In the following table, “-
” means that “node A is visible from node B”.
A \ B | document | a1 | a2 | b1 | c1 | d1 | d2 | e1 | f1 |
---|---|---|---|---|---|---|---|---|---|
document | - | - | - | - | - | - | - | - | - |
a1 | - | - | - | - | - | - | - | - | - |
a2 | - | - | - | - | - | - | - | - | - |
b1 | hidden | hidden | hidden | - | hidden | hidden | hidden | hidden | hidden |
c1 | hidden | hidden | hidden | hidden | - | hidden | hidden | hidden | hidden |
d1 | hidden | hidden | hidden | hidden | hidden | - | - | - | - |
d2 | hidden | hidden | hidden | hidden | hidden | - | - | - | - |
e1 | hidden | hidden | hidden | hidden | hidden | hidden | hidden | - | hidden |
f1 | hidden | hidden | hidden | hidden | hidden | hidden | hidden | hidden | - |
For example, document is visible from any nodes.
To understand visibility relationship easily, here is a rule of thumb:
──/
) ( shadowhost-shadowroot relationship) is one-directional:In other words, a node in an inner tree can see a node in an outer tree in a composed tree, but the opposite is not true.
We have designed (or re-designed) a bunch of Web-facing APIs to honor this basic principle. If you add a new API to the web platform and Blink, please consider this rule and don't leak a node which should be hidden to web developers.
Warning: Unfortunately, a composed tree had a different meaning in the past; it was used to specify a flat tree (which will be explained later). If you find a wrong usage of a composed tree in Blink, please fix it.
Further Info:
A composed tree itself can‘t be rendered as is. From the rendering’s perspective, Blink has to construct a layout tree, which would be used as an input to the paint phase. A layout tree is a tree whose node is LayoutObject
, which points to Node
in a node tree, plus additional calculated layout information.
Before the Web Platform got Shadow DOM, the structure of a layout tree is almost similar to the structure of a document tree; where only one node tree, document tree, is being involved there.
Since the Web Platform got Shadow DOM, we now have a composed tree which is composed of multiple node trees, instead of a single node tree. That means We have to flatten the composed tree to the one node tree, called a flat tree, from which a layout tree is constructed.
For example, given the following composed tree,
document ├── a1 (host) │ ├──/shadowRoot1 │ │ └── b1 │ └── a2 (host) │ ├──/shadowRoot2 │ │ ├── c1 │ │ │ ├── c2 │ │ │ └── c3 │ │ └── c4 │ ├── a3 │ └── a4 └── a5 └── a6 (host) └──/shadowRoot3 └── d1 ├── d2 ├── d3 (host) │ └──/shadowRoot4 │ ├── e1 │ └── e2 └── d4 (host) └──/shadowRoot5 ├── f1 └── f2
This composed tree would be flattened into the following flat tree (assuming there are not <slot>
elements there):
document ├── a1 (host) │ └── b1 └── a5 └── a6 (host) └── d1 ├── d2 ├── d3 (host) │ ├── e1 │ └── e2 └── d4 (host) ├── f1 └── f2
We can't explain the exact algorithm how to flatten a composed tree into a flat tree until I explain the concept of slots and slot assignment If we are ignoring the effect of <slot>
, we can have the following simple definition. A flat tree can be defined as:
Please see this nice article how <slot>
elements work in general.
Slots are placeholders inside your component that users can fill with their own markup.
Here, I'll show some examples.
Given the following composed tree and slot assignments,
Composed tree:
A ├──/shadowRoot1 │ ├── slot1 │ └── slot2 ├── B └── C
Slot Assignments:
slot | slot's assigned nodes |
---|---|
slot1 | [C] |
slot2 | [B] |
The flat tree would be:
A ├── slot1 │ └── C └── slot2 └── B
More complex example is here.
Composed tree:
A ├──/shadowRoot1 │ ├── B │ │ └── slot1 │ ├── slot2 │ │ └── C │ ├── D │ └── slot3 │ ├── E │ └── F ├── G ├── H ├── I └── J
Slot Assignments:
slot | slot's assigned nodes |
---|---|
slot1 | [H] |
slot2 | [G, I] |
slot3 | [] (nothing is assigned) |
The flat tree would be:
A ├── B │ └── slot1 │ └── H ├── slot2 │ ├── G │ └── I ├── D └── slot3 ├── E └── F
slot2
's child, C
, is not shown in this flat tree because slot2
has non-empty assigned nodes, [G, I]
, which are used as slot2
's children in the flat tree.slot3
s children in the flat tree are E
and F
.J
A slot itself can be assigned to another slot.
For example, if we attach a shadow root to B
, and put a <slot>
, slot4
, inside of the shadow tree.
A ├──/shadowRoot1 │ ├── B │ │ ├──/shadowRoot2 │ │ │ └── K │ │ │ └── slot4 │ │ └── slot1 │ ├── slot2 │ │ └── C │ ├── D │ └── slot3 │ ├── E │ └── F ├── G ├── H ├── I └── J
slot | slot's assigned nodes |
---|---|
slot1 | [H] |
slot2 | [G, I] |
slot3 | [] (nothing is assigned) |
slot4 | [slot1] |
The flat tree would be:
A ├── B │ └── K │ └── slot4 │ └── slot1 │ └── H ├── slot2 │ ├── G │ └── I ├── D └── slot3 ├── E └── F
Please see Incremental Shadow DOM to know how assignments are recalc-ed.
Blink doesn't store nor maintain a flat tree data structure in the memory. Instead, Blink provides a utility class, FlatTreeTraversal
, which traverses a composed tree in a flat tree order.
e.g. in the above example 3,
FlatTreeTraversal::firstChild(slot1)
returns H
FlatTreeTraversal::parent(H)
returns slot1
FlatTreeTraversal::nextSibling(G)
returns I
FlatTreeTraversal::previousSibling(I)
returns G
The APIs which FlatTreeTraversal
provides are very similar to ones other traversal utility classes provide, such as NodeTraversal
and ElementTraversal
.
DOM Standard defines how an event should be dispatched here, including how event path should be calculated, however, I wouldn't be surprised if the steps described there might look a kind of cryptogram to you.
In this README, I'll explain how an event is dispatched and how its event path is calculated briefly by using some relatively-understandable examples.
Basically, an event is dispatched across shadow trees.
Let me show more complex example composed tree, involving a slot:
A └── B ├──/shadowroot-C │ └── D │ ├──/shadowroot-E │ │ └── F │ │ └── slot-G │ └── H │ └── I │ ├──/shadowroot-J │ │ └── K │ │ ├──/shadowroot-L │ │ │ └── M │ │ │ ├──/shadowroot-N │ │ │ │ └── slot-O │ │ │ └── slot-P │ │ └── Q │ │ └── slot-R │ └── slot-S └── T └── U
Slot Assignments:
slot | slot's assigned nodes |
---|---|
slot-G | [H] |
slot-O | [slot-P] |
slot-P | [Q] |
slot-R | [slot-S] |
slot-S | [T] |
Given that, suppose that an event is fired on U
, an event path would be (in reverse order):
[U => T => slot-S => slot-R => Q => slot-P => slot-O => shadowroot-N => M => shadowroot-L => K => shadowroot-J => I => H => slot-G => F => shadowroot-E => D => shadowroot-C => B => A]
Roughly speaking, an event's parent (the next node in event path) is calculated as follows:
In the above case, event.target
, U
, doesn't change in its lifetime because U
can be seen from every nodes there. However, if an event is fired on node Q
, for example, event.target
would be adjusted for some nodes in event path to honer encapsulation. That is called event re-targeting.
Here is an event path for an event which is fired on Q
:
event.currenttarget | (re-targeted) event.target |
---|---|
Q | Q |
slot-P | Q |
slot-O | Q |
shadowroot-N | Q |
M | Q |
shadowroot-L | Q |
K | Q |
shadowroot-J | Q |
I | I |
H | I |
slot-G | I |
F | I |
shadowroot-E | I |
D | I |
shadowroot-C | I |
B | B |
A | B |
TODO(hayato): Explain.
TODO(hayato): Explain.
TODO(hayato): Explain.
TODO(hayato): Explain.
TODO(hayato): Explain.