Bug 26827 – Improve InlineBox::first/lastLeafChild methods

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Roland Steiner]

The current methods have some peculiarities (the following also all apply to the corresponding lastLeafChild[BeforeBox]() method):

.) someBasePtr->firstLeafChild() may return the same node rather than a child node

.) someBasePtr->firstLeafChild[AfterBox]() may return a node outside of the subtree

.) the meaning of someBasePtr->firstLeafChildAfterBox(), i.e., without parameter, is unclear without reading the code. It's also synonymous with firstLeafChild. It's also unclear why the method would need both a 'this' pointer AND a parameter (both issues are likely just artifacts of the implementation). 

.) from an interface POV there doesn't seem to be a reason why firstLeafChildAfterBox() should be restricted to InlineFlowBox (rather than be available on InlineBox)

.) The behavior of firstLeafChild[AfterBox]() is quadratic if the remaining nodes in the tree after the given box are all just empty InlineFlowBoxes

[Roland Steiner]

Created attachment 32031 [details]
patch fixing the issues in the bug description

[Eric Seidel (no email)]

Comment on attachment 32031 [details]
patch fixing the issues in the bug description

Are any of these behavior changes testable?  If not, there should be a note in the ChangeLog explaining why not.  If they are, we should have LayoutTests.

[Roland Steiner]

Created attachment 32103 [details]
updated patch

Currently, the methods in question are called on RootInlineBox objects only, AFAICT, so there should not be any observable effects (the mentioned behavior can only happen if called on InlineFlowBox objects, basically).

Only the removal of the square runtime behavior when the remaining nodes in a tree are all empty InlineFlowBox objects could be effective, but the conditions for that are more theoretical in nature (i.e., would probably require to have a pathological case to have any measurable impact).

Updated the ChangeLog accordingly.

[Maciej Stachowiak]

Comment on attachment 32103 [details]
updated patch

Most of the refactoring looks good. One part I don't undestand.

InlineFlowBox::firstLeafChildBeforeBox looks like it used to sometimes look in the parent, if no leaf box was found:

     if (start && !leaf && parent())
         return parent()->firstLeafChildAfterBox(this);

Likewise for lastLeafChildBeforeBox. 

It's documented that these won't return nodes outside the subtree any more, but as a non-expert it's not clear to me why this is right. Explanation would be appreciated.

[Maciej Stachowiak]

Comment on attachment 32103 [details]
updated patch

Most of the refactoring looks good. One part I don't undestand.

InlineFlowBox::firstLeafChildBeforeBox looks like it used to sometimes look in the parent, if no leaf box was found:

     if (start && !leaf && parent())
         return parent()->firstLeafChildAfterBox(this);

Likewise for lastLeafChildBeforeBox. 

It's documented that these won't return nodes outside the subtree any more, but as a non-expert it's not clear to me why this is right. Explanation would be appreciated.

[Roland Steiner]

(In reply to comment #5)

[recapping our discussion on IRC]

Note: all of the following is rather theoretical, since those function currently are only called on RootInlineBox objects, while the issues would only manifest if called on InlineFlowBox objects.

From the name "firstLeafChild" it struck me as odd that the function would potentially return a node outside the current subtree, i.e., not a child of the current node.
The reason for this seems that the functions firstLeafChildAfterBox/lastLeafChildBeforeBox are mainly for implementation purposes, and used to implement both for first/lastLeafChild() and next/prevLeafChild(). For the latter it makes sense that a node outside of the current subtree can be returned, for the former not so much (IMHO).

[Maciej Stachowiak]

Comment on attachment 32103 [details]
updated patch

All right, the code looks correct, and since it doesn't fail any tests, I'm going to assume the assumptions about looking at parents (that it's accidentally there and no longer needed) are right. If not, we'll find out soon enough.

[Brent Fulgham]

Landed in http://trac.webkit.org/changeset/45702.