834096 - Simplify nsOverflowContinuationTracker::Insert and make it not recurse on continuations

Status: NEW

(Core :: Layout: Block and Inline, defect)

Description

[Mats Palmgren (inactive)]

nsOverflowContinuationTracker::Insert is kind of weird in that it
expects a non-NS_FRAME_IS_OVERFLOW_CONTAINER frame to not be on any
frame list and thus no StealFrame is required in that case.
http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsContainerFrame.h#590
motivates this with "StealFrame is inefficient" -- is this still true?
I'd like to understand why.

Also, it has the problem that it recurse on OVERFLOW_CONTAINER
continuations and thus can cause stack overflow.

Comment 1

[fantasai]

StealFrame walks the entire child list, making it O(N) wrt number of children. If the Insert caller is in the middle of reflow, it doesn't need to do that, making it O(1).

I suppose it might make sense to change the recursion to using a loop somehow. Don't know how important that would be: a typical web page is not going to trigger this case, and if it does, it's unlikely to trigger it for very many frames. But maybe there some security implication there?

Comment 2

[Mats Palmgren (inactive)]

> StealFrame walks the entire child list, making it O(N)

Oh right, I had suppressed my knowledge of how horrible StealFrame is ;-)
It doesn't need to be O(n), so let's fix that first in bug 838642.

Comment 3

[fantasai]

Note that nsBlockFrame::StealFrame is different, and has to consider the nsLineBoxes. That might be considerably harder to make O(1). :)