# Handling shadow DOM in the various tree kinds

## Flattened tree

A DOM tree may have some shadow DOM trees. A flattened tree formats all
[shadow root](#shadowroot)s are connected to each [shadow host](#shadow-host).

## Shadow host

It is an `Element` node which has a `ShadowRoot` attached to it. In the
flattened tree, its children are treated as replaced with the children of the
`ShadowRoot`. So, the children of `ShadowRoot` look like the children of the
host in the flattened tree.

`nsINode` APIs, such as `nsINode::GetChildAt<TreeKind>()`,
`nsINode::GetChildCount<TreeKind>()` and `nsINode::ComputeIndexOf<TreeKind>()`,
treat the children of a shadow host are the `ShadowRoot` children if `TreeKind`
is not [`TreeKind::DOM`](#treekinddom).

## ShadowRoot

It is a content node, inherits `DocumentFragment`. Therefore, when you print
inclusive ancestors of a node in a `ShadowRoot` with `ToString(*node).c_str()`,
you'll see `#document-fragment` as the root node.

In the flattened tree, the children of a `ShadowRoot` is formatted as children
of the [shadow host](#shadow-host) and the children of the shadow host are not
part of the flattened tree unless they are assigned to `<slot>` elements.

## HTMLSlotElement

When it appears in a shadow DOM, it may have assigned nodes which are children
of the host element. In the flattened tree, the assigned nodes of a `<slot>`
element are formatted as its children and the children of the `<slot>` are not
part of the flattened tree
([spec](https://html.spec.whatwg.org/#the-slot-element)). However, if a
`<slot>` does not have assigned node, the element is is treated as a usual
container element because they are the fallback content of the element when
there is no assigned node.

`nsINode::GetParentOrShadowHostNode<TreeKind>()` for
`TreeKind::FlatForSelection` and `TreeKind::Flat` of a `<slot>` element which
has some assigned nodes return the `<slot>` element as the parent node.
However, if in the other `TreeKind`s, it returns the parent node in the shadow
including DOM.

Similarly, `nsINode::GetChildAt<TreeKind>()`,
`nsINode::GetChildCount<TreeKind>()` and `nsINode::ComputeIndexOf<TreeKind>()`
for `TreeKind::FlatForSelection` and `TreeKind::Flat` of a `<slot>` which has
some assigned nodes treat the assigned nodes as children of the `<slot>`.

Note that the assigned nodes are not treated as in the shadow tree by
`nsINode::IsInShadowTree()`. So, it returns `false` for the assigned nodes if
they are not a descendant of a `ShadowRoot`.

## UA shadow tree

Gecko attaches internally created `ShadowRoot` to some specific elements.
For example, `<details>`, `<video>` and SVG `<use>`. You can check it with
`ShadowRoot::IsUAShadowRoot()`. Most children of the UA shadow host element
will be assigned to one or more `<slot>`s in the shadow. Therefore, they can
be selected by the user. Additionally, Selection API can specify any points in
the host element as a range boundary. However, from the shadow including DOM
point of view, children should be treated as replaced by the children of the
UA `ShadowRoot`. Therefore, when we handle selection including DOM ranges, we
need to ignore the UA shadow.

## Kinds of DOM tree

To support the shadow DOM, there are 4 kinds of DOM trees which are identified
with `TreeKind` defined in `nsINode.h`.

### TreeKind::DOM

The simplest DOM tree which do not treat `ShadowRoot` attached to an element.

`nsINode::GetChildAt<TreeKind::DOM>()`,
`nsINode::GetChildCount<TreeKind::DOM>()` and
`nsINode::ComputeIndexOf<TreeKind::DOM>()` treat the children of any nodes
as-is.

`nsINode::GetParentOrShadowHostNode<TreeKind::DOM>()` returns the parent node
as-is. If you call it of a `ShadowRoot`, it returns `nullptr`.

### TreeKind::ShadowIncludingDOM

The [shadow host element](#shadow-host) treat each `ShadowRoot` as connected
to its host. However, `<slot>` elements are not handled, they are always
treated as usual container element.

`nsINode::GetChildAt<TreeKind::ShadowIncludingDOM>()`,
`nsINode::GetChildCount<TreeKind::ShadowIncludingDOM>` and
`nsINode::ComputeIndexOf<TreeKind::ShadowIncludingDOM>()` of a
[shadow host](#shadow-host) treat the `ShadowRoot` children as the host's
children.

`nsINode::GetParentOrShadowHostNode<TreeKind::ShadowIncludingDOM>()` returns
the parent node as is. However, if the node is a `ShadowRoot`, returns its
[host](#shadow-host).

Be aware, there is a special case. When you call
`nsINode::GetParentOrShadowHostNode<TreeKind::ShadowIncludingDOM>()` of a child
of a [shadow host element](#shadow-host), you'll get the shadow host element
as-is even though the child should not be part of the flattened tree. However,
the strict behavior, returning `nullptr`, is not useful to handle the shadow
including DOM in the most cases. Therefore, returns the host element as-is.
However, if you verify the result with
`nsINode::ComputeIndexOf<TreeKind::ShadowIncludingDOM>()`, it'll return
`Nothing()`. So, you should verify it with an assertion only when you're sure
that the child is a child of a `ShadowRoot`.

Note that the [UA shadow tree](#ua-shadow-tree)s are ignored at reaching the
shadow DOM boundary. Therefore, the UA shadow host element is treated as same
as not hosting the shadow.

### TreeKind::FlatForSelection

Almost same as `TreeKind::ShadowIncludingDOM`. Additionally, the assigned
nodes of `<slot>` elements are treated as children of the `<slot>` element
(if a `<slot>` does not have assigned node, it's treated as a normal element
which may have some children).

`nsINode::GetChildAt<TreeKind::FlatForSelection>()`,
`nsINode::GetChildCount<TreeKind::FlatForSelection>()` and
`nsINode::ComputeIndexOf<TreeKind::FlatForSelection()` of a `<slot>` which has
some assigned nodes treat the assigned nodes as the children of the `<slot>`.

`nsINode::GetParentOrShadowHostNode<TreeKind::FlatForSelection>()` of an
assigned node of a `<slot>` returns the `<slot>` element.

In the other cases, these APIs for `TreeKind::FlatForSelection` work as the same
as them for `TreeKind::ShadowIncludingDOM`.

The [UA shadow tree](#ua-shadow-tree)s are ignored too. Similarly, when you
handle a `<slot>` element which has some assigned nodes, the APIs for
`TreeKind::FlatForSelection` check whether the `<slot>`'s `ShadowRoot` is a UA
one. If it's so, the `<slot>` element is treated as a usual container element.

Be aware, there are the similar points to `TreeKind::ShadowIncludingDOM`.
`nsINode::GetParentOrShadowHostNode<TreeKind::FlatForSelection>()` of
When you get the parent of a `ShadowRoot`, you'll get the host element. However,
there is a special case. When you get the parent of a child of a shadow host
element, you'll get the `ShadowRoot` instead. This is different from
`TreeKind::ShadowIncludingDOM`. Therefore, you want to verify whether the
`ShadowRoot` has the child node with
`nsINode::ComputeFlatTreeForSelectionIndexOf()`, you'll get `Nothing()`. Thus,
do not assert it unless you're sure that the child node is in the shadow tree.

When you call `nsINode::GetParentOrShadowHostNode<TreeKind::FlatForSelection>()`
of a child of a `<slot>` which has some assigned nodes, it'll return `nullptr`
since the child is replaced by the assigned nodes.

### TreeKind::Flat

Almost same as `TreeKind::FlatForSelection`. Additionally, the
[UA shadow tree](#ua-shadow-tree)s won't be ignored. Thus, you can handle all
things which you see in the content except the native anonymous nodes.

## Iterating children of a node

There is a useful template iterator class, `ChildIterBase<TreeKind>`. There
are alias names for each `TreeKind`.

| `TreeKind` | `ChildIterBase<TreeKind>` |
| ---------- | ------------------------- |
| `TreeKind::DOM` | `ChildIterator` |
| `TreeKind::ShadowIncludingDOM` | `ShadowIncludingChildIterator` |
| `TreeKind::FlatForSelection` | `FlattenedChildIteratorForSelection` |
| `TreeKind::Flat` | `FlattenedChildIterator` |

You can initialize them with a parent node.

```cpp
ChildIterBase<aKind> iter(parentNode);
```

Then, if you need to iterate from a specific child rather than from the first
child, you need to seek the child.

```cpp
if (!iter.Seek(childNode)) {
  return; // childNode is not a child of parentNode in the specified tree.
}
```

It'll return `false` if the child node is not a valid child node for the parent
node. E.g., when `TreeKind::ShadowIncludingDOM` and you specified a child of a
shadow host element.

Then, you can iterate the remaining children:
```cpp
for (nsIContent* sibling = iter.GetNextChild(); sibling;
     sibling = iter.GetNextChild()) {
  // Do something with sibling.
}
```
```cpp
for (nsIContent* sibling = iter.GetPreviousChild(); sibling;
     sibling = iter.GetPreviousChild()) {
  // Do something with sibling.
}
```
`ChildIterBase<TreeKind::FlatForSelection>` and `ChildIterBase<TreeKind::Flat>`
works with a `<slot>` which has some assigned nodes and in that case, this
iterator works faster than:

```cpp
for (nsIContent* sibling = childNode->GetNextSibling<TreeKind::Flat>(); sibling;
     sibling = sibling->GetNextSibling<TreeKind::Flat>()) {
  // This is slower than above loop!
}
```

The reason is, `ChildIterBase` needs to get the index of `childNode` in the
assigned node list/array. Then, retrieve its next/previous sibling each time.
On the other hand, `ChildIterBase` caches the index so that it can skip
computing the current index.

## Comparing points

`nsContentUtils::ComparePoints` and `nsContentUtils::ComparePointsWithIndices()`
are template methods whose template parameter is `TreeKind`.

If `TreeKind` is `DOM`, the points in different shadow trees are treated as
disconnected. Otherwise, the points are compared across the shadow DOM
boundaries.

Even if the `TreeKind` of the template method is `ShadowIncludingDOM`, the
points can be the points in the flattened tree. Similarly, even if the
`TreeKind` is `FlatForSelection`, the points can be the points in the DOM.
Using different `TreeKind` points are not recommended, but works in the most
cases. However, to prevent a bug in an edge case, you should convert the
points to `TreeKind::DOM` if you use `TreeKind::ShadowIncludingDOM` method and
convert the points to `TreeKind::FlatForSelection` or `TreeKind::Flat` when you
use the corresponding method.

Be aware about `TreeKind::ShadowIncludingDOM`. You need to use a `ShadowRoot`
as a parent of a point to refer a `ShadowRoot` even though
`nsINode::GetChildAt<TreeKind::ShadowIncludingDOM>()` of a shadow host element
returns a child of the `ShadowRoot`. This make it possible you to compare the
point in a shadow host element across shadow DOM boundaries because this is
usually required to compare 2 range boundaries. You may be confused at this
because this caused a lot of assertion failures. However, you can live with
this odd rule with using only `nsContentUtils::ComparePoints()` because the
method takes 2 `RangeBoundaryBase` instances and the `TreeKind` of
`RangeBoundaryBase` can be `TreeKind::DOM` or `TreeKind::FlatForSelection`.
Therefore, if you create a `RangeBoundaryBase` instance from a child node with
`FromChild` or `After` factory method, it computes a good parent node to use
`nsContentUtils::ComparePoints<TreeKind::ShadowIncludingDOM>()` automatically.

## Convert a point in `TreeKind::DOM` or `TreeKind::FlatForSelection` to the other

`RangeBoundaryBase` supports `TreeKind::DOM` and `TreeKind::FlatForSelection`
and it has factory methods to create the instance in those kinds of tree.
Use `AsRangeBoundaryInDOMTree()` to get a point in `TreeKind::DOM` and use
`AsRangeBoundaryInFlatTree()` to get a point in `TreeKind::FlatForSelection`.
If the referring child node has different parent in the trees, these methods
compute the proper parent automatically.

When `AsRangeBoundaryInFlatTree()` converts a `TreeKind::DOM` point, the point
may be not in the flattened tree. E.g., the referring child node may be
replaced with a shadow tree without assigned to a `<slot>`. In this case, it
converts the point to the start or end of the container because `ShadowRoot` is
treated as positioned at index 0.5.

## nsINode API list

| `TreeKind` | `nsINode::GetParentOrShadowHostNode<TreeKind>()` |
| ---------- | ------------------------------------ |
| `TreeKind::DOM` | `nsINode::GetParentNode()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetParentOrShadowHostNode()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlattenedTreeParentOrShadowHostNodeForSelection()` |
| `TreeKind::Flat` | `nsINode::GetFlattenedTreeParentOrShadowHostNode()` |

| `TreeKind` | `nsINode::GetParentNodeSkippingShadowRoot<TreeKind>()` |
| ---------- | ------------------------------------ |
| `TreeKind::DOM` | `nsINode::GetParentNode()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetParentNodeOrShadowHostNodeSkippingShadowRoot()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlattenedTreeParentNodeForSelection()` |
| `TreeKind::Flat` | `nsINode::GetFlattenedTreeParentNode()` |

| `TreeKind` | `nsINode::GetChildAt<TreeKind>()` |
| ---------- | --------------------------------- |
| `TreeKind::DOM` | `nsINode::GetChildAt_Deprecated()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetChildAtInShadowIncludingDOM()` |
| `TreeKind::FlatForSelection` | `nsINode::GetChildAtInFlatTreeForSelection()` |
| `TreeKind::Flat` | `nsINode::GetChildAtInFlatTree()` |

| `TreeKind` | `nsINode::GetFirstChild<TreeKind>()` |
| ---------- | ------------------------------------ |
| `TreeKind::DOM` | `nsINode::GetFirstChild()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetShadowIncludingFirstChild()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlattenedTreeFirstChildForSelection()` |
| `TreeKind::Flat` | `nsINode::GetFlattenedTreeFirstChild()` |

| `TreeKind` | `nsINode::GetLastChild<TreeKind>()` |
| ---------- | ----------------------------------- |
| `TreeKind::DOM` | `nsINode::GetLastChild()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetShadowIncludingLastChild()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlattenedTreeLastChildForSelection()` |
| `TreeKind::Flat` | `nsINode::GetFlattenedTreeLastChild()` |

| `TreeKind` | `nsINode::GetNextSibling<TreeKind>()` |
| ---------- | ------------------------------------- |
| `TreeKind::DOM` | `nsINode::GetNextSibling()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetNextSibling()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlattenedTreePreviousSiblingForSelection()` |
| `TreeKind::Flat` | `nsINode::GetFlattenedTreePreviousSibling()` |

| `TreeKind` | `nsINode::GetPreviousSibling<TreeKind>()` |
| ---------- | ----------------------------------------- |
| `TreeKind::DOM` | `nsINode::GetPreviousSibling()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetPreviousSibling()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlattenedTreeLastChildForSelection()` |
| `TreeKind::Flat` | `nsINode::GetFlattenedTreeLastChild()` |

| `TreeKind` | `nsINode::GetChildCount<TreeKind>()` |
| ---------- | ------------------------------------ |
| `TreeKind::DOM` | `nsINode::GetChildCount()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetShadowIncludingChildCount()` |
| `TreeKind::FlatForSelection` | `nsINode::GetFlatTreeForSelectionChildCount()` |
| `TreeKind::Flat` | `nsINode::GetFlatTreeChildCount()` |

| `TreeKind` | `nsINode::ComputeIndexOf<TreeKind>()` |
| ---------- | ------------------------------------- |
| `TreeKind::DOM` | `nsINode::ComputeIndexOf()` |
| `TreeKind::ShadowIncludingDOM` | `nsINode::ComputeShadowIncludingDOMIndexOf()` |
| `TreeKind::FlatForSelection` | `nsINode::ComputeFlatTreeForSelectionIndexOf()` |
| `TreeKind::Flat` | `nsINode::ComputeFlatTreeIndexOf()` |

| `TreeKind` | `nsINode::GetContainingShadow<TreeKind>()` |
| ---------- | ------------------------------------------ |
| `TreeKind::DOM` | N/A (The template API returns `nullptr`) |
| `TreeKind::ShadowIncludingDOM` | N/A (The template API returns `nullptr`) |
| `TreeKind::FlatForSelection` | `nsINode::GetContainingShadowForSelection()` |
| `TreeKind::Flat` | `nsINode::GetContainingShadow()` |

| `TreeKind` | `nsINode::GetShadowRoot<TreeKind>()` |
| ---------- | ------------------------------------------ |
| `TreeKind::DOM` | N/A (The template API returns `nullptr`) |
| `TreeKind::ShadowIncludingDOM` | `nsINode::GetShadowRootForSelection()` |
| `TreeKind::FlatForSelection` | `nsINode::GetShadowRootForSelection()` |
| `TreeKind::Flat` | `nsINode::GetShadowRoot()` |

## nsIContent API list

| `TreeKind` | `nsIContent::GetAssignedSlot<TreeKind>()` |
| ---------- | ------------------------------------------ |
| `TreeKind::DOM` | N/A (The template API returns `nullptr`) |
| `TreeKind::ShadowIncludingDOM` | N/A (The template API returns `nullptr`) |
| `TreeKind::FlatForSelection` | `nsIContent::GetAssignedSlotForSelection()` |
| `TreeKind::Flat` | `nsIContent::GetAssignedSlot()` |