[Webkit-unassigned] [Bug 149997] Implement iterator for traversing composed DOM

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=149997

--- Comment #9 from Antti Koivisto <koivisto at iki.fi> ---
> > Not sure what you mean. In general case there is no way to know if there is
> > a trip to shadow tree between a node and its ancestor without walking the
> > parent chain.
> 
> You do. If you only move into a slot if the slot is the next node, or if the
> next node is assigned into a slot. Since a node can only be assigned into a
> slot inside shadow DOM of its parent node, you just need to do:
> if (auto parent = node->parentElement()) {
>   if (auto shadowRoot = parent->shadowRoot()) {
>     slot = shadowRoot->findAssignedSlot(this)
>   }
> }

Right. And if you have a node and an ancestor you need to walk the parent chain between them to see if this condition happens to know if there are trip to a shadow tree there. That's what I meant.

> For moving out of a slot, you find the assigned slot in O(1) as shown above,
> and check whether you're the last one in the assigned nodes list or not.  If

Yeah. That's what the patch does.

> you're the last assigned node, then just move to the next node from the
> slot. If the slot from which you're moving out is assigned to another slot,
> then you into that slot's next assigned node. If we're the last slot

I'm maintaining the shadow stack to cache the assigned node index within the current slot. This allows moving to the slot's next assigned node in O(1).

A way to sort-of do this stacklessly (though I'm not sure if that is what you are arguing for) would be to walk the real siblings of the current slot assignee and find the next one in the same slot. This is much slower since we are doing hash lookups vs indexing to array. It also has bad worst case if nodes are assigned to mixed slots (like ABCABCABC.

If we are maintaining a stack and want to support arbitrary starting state for the iterator then we need to have function to synthesize the stack without traversing the tree. That's what initializeShadowStack() is about.

Note that it doesn't get called at all if you use shadowTreeDescendants() and is almost never called for shadowTreeChildren() (since there is a fast path that avoids it).

> assigned to another slot, then we recursively move out of slot as long as
> the slot we just moved out is the last assigned node in the containing slot.
> 
> Does that make sense?

-- 
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-unassigned/attachments/20151013/aa2e4347/attachment-0001.html>