Bug 64252 – [ShadowContentElement] forwarded node list should be a linked-list.

• Component: DOM
• Status: RESOLVED FIXED

[Hajime Morrita]

under bug 64251: Turns ShadowContentElement::m_inclusion array to a linked list.

[Hajime Morrita]

Hi Dimitri, could you take a look?

My plan is to maintain a Node* -> ShadowContentElement* table on ShadowRoot,
which allows us to traverse from forwarded node to its including ShadowContentElement*.
In my understanding, the design is closer to your original thought than current one ;-)

[Dimitri Glazkov (Google)]

(In reply to comment #1)
> Hi Dimitri, could you take a look?
> 
> My plan is to maintain a Node* -> ShadowContentElement* table on ShadowRoot,
> which allows us to traverse from forwarded node to its including ShadowContentElement*.
> In my understanding, the design is closer to your original thought than current one ;-)

Yes! Good idea.

[Hajime Morrita]

Ooops! I thought I upload the patch before going home...

[Hajime Morrita]

Created attachment 100394 [details]
Patch

[Dimitri Glazkov (Google)]

(In reply to comment #4)
> Created an attachment (id=100394) [details]
> Patch

Can you tell me more about the overall design you're thinking of. This patch makes the double-linked list the storage facility, and I don't necessarily understand exactly why this is the best choice.

The items in the list aren't stored outside of the ShadowContentElement, and we only need the linkage to traverse in search of renderers.

So It seems we could go with a map of inclusions so that you can do O(1) find. Then each inclusion has previous/next ptrs, forming a double-linked list. Since they are never destroyed separately, the map owns inclusions, and the maintenance of the double-linked list integrity is simple.

So you have fast find and fast next/previous renderer search. Right?

[Hajime Morrita]

(In reply to comment #5)
> (In reply to comment #4)
> > Created an attachment (id=100394) [details] [details]
> > Patch
> 
> Can you tell me more about the overall design you're thinking of. This patch makes the double-linked list the storage facility, and I don't necessarily understand exactly why this is the best choice.
> 
> The items in the list aren't stored outside of the ShadowContentElement, and we only need the linkage to traverse in search of renderers.
> 
> So It seems we could go with a map of inclusions so that you can do O(1) find. Then each inclusion has previous/next ptrs, forming a double-linked list. Since they are never destroyed separately, the map owns inclusions, and the maintenance of the double-linked list integrity is simple.
> 
> So you have fast find and fast next/previous renderer search. Right?

Hi Dimitri, thanks for taking a look!
And I'm sorry for the short of explanation.

> So you have fast find and fast next/previous renderer search. Right?

Yes. What TreeIterator will need is
- nextSibling() - This is what ShadowInclusion::m_next is for
- previousSibling() - Ditto for m_previous
- parent() - Ditto for m_includer.

Here is a plan:
As a next step, I'll introduce a HashSet on ShadowRoot, which will maintain ShadowInclusion instances as entries.
The hash-value will be computed from ShadowInclusion::m_content.
(HashTranslator allows this kind of trick.)

The hash set is used essentially as same way as ElementRareData (aka. O(1) find.)
But because ElementRareData is different lifetime and usage pattern,
I think it's better to have a separate table.

With this hash set, we can determine the element is forwarded to a content element or not.
This forwarded-child-to-content traversal is the primary goal of this change.

Does this make sense?

[Dimitri Glazkov (Google)]

Comment on attachment 100394 [details]
Patch

ok.

[Hajime Morrita]

Comment on attachment 100394 [details]
Patch

Thanks! landing...

[WebKit Review Bot]

Comment on attachment 100394 [details]
Patch

Clearing flags on attachment: 100394

Committed r90888: <http://trac.webkit.org/changeset/90888>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.