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 ;-)

(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.

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

Created attachment 100394 [details] Patch

(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?

(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?

Comment on attachment 100394 [details] Patch ok.

Comment on attachment 100394 [details] Patch Thanks! landing...

Comment on attachment 100394 [details] Patch Clearing flags on attachment: 100394 Committed r90888: <http://trac.webkit.org/changeset/90888>

All reviewed patches have been landed. Closing bug.