Jesse Ruderman Reporter
	Description • 14 years ago

###!!! ASSERTION: Null out-of-flow for placeholder?: 'outOfFlow', file nsPlaceholderFrame.h, line 200

###!!! ASSERTION: no out-of-flow frame: 'outOfFlow', file layout/base/nsFrameManager.cpp, line 778

Crash [@ nsFrameManager::ReparentStyleContext]

	Jesse Ruderman Reporter
	Comment 1 • 14 years ago

Sometimes preceded by:

###!!! ASSERTION: Placeholder relationship should have been torn down already; this might mean we have a stray placeholder in the tree.: '!placeholder || nsLayoutUtils::IsProperAncestorFrame(aDestructRoot, placeholder)', file layout/generic/nsFrame.cpp, line 443

	Jesse Ruderman Reporter
	Comment 2 • 14 years ago

cf bug 588237

	Jesse Ruderman Reporter
	Comment 4 • 14 years ago

Before the assertions in comments 0 & 1, I now get the freshly added assertions from bug 619021 patch 1 (rev dfa73f7b1acf):

###!!! ASSERTION: frame tree not empty, but caller reported complete status: 'aSubtreeRoot->GetPrevInFlow()', file layout/base/nsLayoutUtils.cpp, line 3831

###!!! ASSERTION: frame tree not empty, but caller reported complete status: 'start == end || IsInLetterFrame(aSubtreeRoot)', file layout/base/nsLayoutUtils.cpp, line 3845

	Martijn Wargers (dead)
	Comment 5 • 14 years ago

http://crash-stats.mozilla.com/report/index/c104f2bb-ec3d-4f4d-bace-65b622110112
0 	xul.dll 	nsFrameManager::ReparentStyleContext 	layout/base/nsFrameManager.cpp:774
1 	xul.dll 	nsFrameManager::ReparentStyleContext 	layout/base/nsFrameManager.cpp:780
2 	xul.dll 	nsFrameManager::ReparentStyleContext 	layout/base/nsFrameManager.cpp:908
3 	xul.dll 	nsFirstLineFrame::PullOneFrame 	layout/generic/nsInlineFrame.cpp:998
4 	xul.dll 	nsFirstLineFrame::Reflow 	layout/generic/nsInlineFrame.cpp:1069
5 	xul.dll 	nsLineLayout::ReflowFrame 	layout/generic/nsLineLayout.cpp:850
6 	xul.dll 	nsBlockFrame::ReflowInlineFrame 	layout/generic/nsBlockFrame.cpp:3794
7 	xul.dll 	nsBlockFrame::DoReflowInlineFrames 	layout/generic/nsBlockFrame.cpp:3590
8 	xul.dll 	nsBlockFrame::ReflowInlineFrames 	layout/generic/nsBlockFrame.cpp:3449
9 	xul.dll 	nsBlockFrame::ReflowLine 	layout/generic/nsBlockFrame.cpp:2545
10 	xul.dll 	nsBlockFrame::ReflowDirtyLines 	layout/generic/nsBlockFrame.cpp:1982
11 	xul.dll 	nsBlockFrame::Reflow 	layout/generic/nsBlockFrame.cpp:1059
12 	xul.dll 	nsBlockReflowContext::ReflowBlock 	layout/generic/nsBlockReflowContext.cpp:297
13 	xul.dll 	nsBlockFrame::ReflowBlockFrame 	layout/generic/nsBlockFrame.cpp:3167
14 	xul.dll 	nsBlockFrame::ReflowLine 	layout/generic/nsBlockFrame.cpp:2489
15 	xul.dll 	nsBlockFrame::ReflowDirtyLines 	
16 		@0x34c53ff

	Jesse Ruderman Reporter
	Comment 6 • 12 years ago

Still happens on mozilla-central.

	Scott Johnson (:jwir3) Assignee
	Comment 7 • 12 years ago

As Jesse mentioned in comment 2, this is fairly similar to bug 588237. I'm attaching a frame tree dump from just before the nsContainerFrame::DeleteNextInFlowChild() call in nsContainerFrame::ReflowChild. It looks from this like the first child of the column set has the placeholder frame, but the second continuation of this has the floats hanging off of it. 

I'm doing some more debugging to see if I can find out more about why this is happening. I'm not seeing it yet...

	Scott Johnson (:jwir3) Assignee
	Comment 8 • 12 years ago

I think I understand what's happening now. When we split into multiple columns, we have a series of pushed floats in one column that get pushed to that column's next in flow. When that block is reflowed, it drains the pushed floats from the previous column, and reflows them. This clears the NS_BLOCK_HAS_PUSHED_FLOATS flag in the first block. 

At some time later, when we reflow again with a different column height, the first column is reflowed, returns NS_FRAME_COMPLETE, and then it's parent decides to remove its next in flow. It doesn't realize that there are still pushed floats, since the NS_BLOCK_HAS_PUSHED_FLOATS flag isn't set correctly any longer (it's temporary).

Perhaps what we need to do is before a block performs a reflow, we should suck all of the floats that are set with NS_BLOCK_IS_PUSHED_FLOAT from the frame's next in flow into our float list, reflow, and then push the floats back out that we can't fit...

	Scott Johnson (:jwir3) Assignee
	Comment 9 • 12 years ago

Alright, I thought I would post my findings thus far, as well as my thoughts on a solution, and see whether this seems reasonable.

My hypothesis is that the problem we're having stems from having an nsBlockFrame with a next continuation that's empty except for floats that were pushed to it from a previous continuation. This leads to a situation where, once we've reflown the nsBlockFrame that doesn't have the floats, and all content fits within the available height of that frame, we decide that we can remove any next continuations that we have, thus deleting the floats, but not their placeholder (since they are pushed floats, the placeholder frame is in a previous continuation).

One of the many things I observed about this is that from the first continuation (where the placeholder frame is), we don't have access to the pushed floats. The pushed floats are stored on a list within a given frame until the next continuation is reflown, at which time they are taken off the pushed float list of that frame and placed at the beginning of the mFloats list of the continuing frame. When a frame is going to push floats to a next continuation (that is, it has the pushed floats in its pushed floats list), we set a bit on the frame state called NS_BLOCK_HAS_PUSHED_FLOATS. On all of the frames that are to be pushed, we set NS_FRAME_IS_PUSHED_FLOAT. Once the floats are cleared from the prev-in-flow and added to the next-in-flow's mFloats list, we clear the NS_BLOCK_HAS_PUSHED_FLOATS flag on our prev-in-flow, but we don't clear the NS_FRAME_IS_PUSHED_FLOAT on the individual frames we add to the mFloats list.

The reason the above paragraph is important is that, when we've completed reflow of a block frame, and we determine that we're complete, I've used a method that I wrote on nsBlockFrame called HasPushedFloatsFromPrevInFlow() to verify that the next-in-flow does indeed have these floats that were pushed from a previous in flow when we're about to delete this next-in-flow. This is obvious from the frame tree dump, but I wanted to verify that this indeed the problem by skipping the deletion of the next-in-flow if this is the case. This strategy worked to eliminate the crash, but it isn't ideal as a solution to the problem. 

Instead, I'd like to propose the following solution:

Create a new method on nsBlockFrame, called PullPushedFloatsBack(). This method will, for each float in our next-in-flow that has NS_FRAME_IS_PUSHED_FLOAT set on it, 
  1. Remove that frame from the next-in-flow's mFloats list.
  2. Clear the NS_BLOCK_IS_PUSHED_FLOAT flag on the frame that we're going to pull back.
  3. Append the frame to our mFloats list.

There are a couple of places where I think we could conceivably call this method:
1) In nsBlockFrame::Reflow(), right before the call to DrainPushedFloats(). This has the advantage that it would happen before reflow of the dirty lines (and thus the rest of the frame). It has the disadvantage that it might be an unexpected state for the frame to be in (although, I'm not sure about this, since it seems like this would be the same state we'd be in if we didn't have a next continuation).

2) Only in situations where we've detected that the frame is complete, but we have a next-in-flow. This has the advantage that it will happen in much fewer cases, and thus does something special to handle what seems to be an exceptional case. It has two disadvantages, though: one is that it happens after the reflow of the dirty lines of the current frame, meaning that the dirty lines would have to be re-reflown. This could cause us to get into a loop of some kind, where we're constantly pushing floats forward and pulling them back again, not to mention that it's fairly inefficient. The other disadvantage is that it will make the code more cluttered and unpredictable, since we're adding special cases.

Does this seem like a reasonable approach?

	David Baron :dbaron:
	Comment 10 • 12 years ago

(In reply to Scott Johnson (:jwir3) from comment #8)
> I think I understand what's happening now. When we split into multiple
> columns, we have a series of pushed floats in one column that get pushed to
> that column's next in flow. When that block is reflowed, it drains the
> pushed floats from the previous column, and reflows them. This clears the
> NS_BLOCK_HAS_PUSHED_FLOATS flag in the first block. 
> 
> At some time later, when we reflow again with a different column height, the
> first column is reflowed, returns NS_FRAME_COMPLETE, and then it's parent
> decides to remove its next in flow. It doesn't realize that there are still
> pushed floats, since the NS_BLOCK_HAS_PUSHED_FLOATS flag isn't set correctly
> any longer (it's temporary).

Indeed, NS_BLOCK_HAS_PUSHED_FLOATS is temporary; it is just a bit to indicate whether a block has a list of pushed floats that need to be pulled into its next continuation.  That's intentional -- it's a bit to guard the frame property, so that we only do the slow access to that property when there is actually something there.

> Perhaps what we need to do is before a block performs a reflow, we should
> suck all of the floats that are set with NS_BLOCK_IS_PUSHED_FLOAT from the
> frame's next in flow into our float list, reflow, and then push the floats
> back out that we can't fit...

So in theory, that should already be happening, since we should pull the float back when we reflow its placeholder.  A little bit ugly, I admit, and not all that great in terms of how it interacts with resizing optimizations.  But that is what's supposed to be happening.

See, for example, this bit of nsBlockFrame::ReflowDirtyLines:

    // If we have a constrained height (i.e., breaking columns/pages),
    // and the distance to the bottom might have changed, then we need
    // to reflow any line that might have floats in it, both because the
    // breakpoints within those floats may have changed and because we
    // might have to push/pull the floats in their entirety.
    // FIXME: What about a deltaY or height change that forces us to
    // push lines?  Why does that work?
    if (!line->IsDirty() &&
        aState.mReflowState.availableHeight != NS_UNCONSTRAINEDSIZE &&
        (deltaY != 0 || aState.mReflowState.mFlags.mVResize) &&
        (line->IsBlock() || line->HasFloats() || line->HadFloatPushed())) {
      line->MarkDirty();
    }

It's possible something isn't doing that, and thus leading to this bug, though.

(In reply to Scott Johnson (:jwir3) from comment #9)
> My hypothesis is that the problem we're having stems from having an
> nsBlockFrame with a next continuation that's empty except for floats that
> were pushed to it from a previous continuation. This leads to a situation
> where, once we've reflown the nsBlockFrame that doesn't have the floats, and
> all content fits within the available height of that frame, we decide that
> we can remove any next continuations that we have, thus deleting the floats,
> but not their placeholder (since they are pushed floats, the placeholder
> frame is in a previous continuation).

That certainly seems to be something that can lead to a crash.

Though I wonder if there's something we ought to do to make it so it doesn't lead to a crash (maybe asserts instead, though).  For example, we could check that a later continuation doesn't have any floats before returning that a block is complete.  (We should probably still assert in that case, since it's a mistake.)

In other words, this is the sort of bug that we might want to fix in more than one way -- that's often a good thing to do for crashes, especially crashes of the exploitable (or exploitable but for frame poisoning) sort, which in most cases shouldn't happen unless multiple things go wrong.

> One of the many things I observed about this is that from the first
> continuation (where the placeholder frame is), we don't have access to the
> pushed floats. The pushed floats are stored on a list within a given frame
> until the next continuation is reflown, at which time they are taken off the
> pushed float list of that frame and placed at the beginning of the mFloats
> list of the continuing frame. When a frame is going to push floats to a next
> continuation (that is, it has the pushed floats in its pushed floats list),
> we set a bit on the frame state called NS_BLOCK_HAS_PUSHED_FLOATS. On all of
> the frames that are to be pushed, we set NS_FRAME_IS_PUSHED_FLOAT. Once the
> floats are cleared from the prev-in-flow and added to the next-in-flow's
> mFloats list, we clear the NS_BLOCK_HAS_PUSHED_FLOATS flag on our
> prev-in-flow, but we don't clear the NS_FRAME_IS_PUSHED_FLOAT on the
> individual frames we add to the mFloats list.

As I mentioned above, you should look at NS_BLOCK_HAS_PUSHED_FLOATS as simply a performance optimization wrapping the frame property (which is the *temporary* pushed floats frame list, used to hold floats that are in the middle of being pushed from one block to its continuation).

The NS_FRAME_IS_PUSHED_FLOAT bit is intended to be a permanent bit marking any float that was pushed from a previous continuation of its containing block.

> The reason the above paragraph is important is that, when we've completed
> reflow of a block frame, and we determine that we're complete, I've used a
> method that I wrote on nsBlockFrame called HasPushedFloatsFromPrevInFlow()
> to verify that the next-in-flow does indeed have these floats that were
> pushed from a previous in flow when we're about to delete this next-in-flow.
> This is obvious from the frame tree dump, but I wanted to verify that this
> indeed the problem by skipping the deletion of the next-in-flow if this is
> the case. This strategy worked to eliminate the crash, but it isn't ideal as
> a solution to the problem. 

I think it may well be something we want to commit as a *second*, belt-and-braces, solution to the problem, with an assertion that fires whenever it kicks in.

> Instead, I'd like to propose the following solution:
> 
> Create a new method on nsBlockFrame, called PullPushedFloatsBack(). This
> method will, for each float in our next-in-flow that has
> NS_FRAME_IS_PUSHED_FLOAT set on it, 
>   1. Remove that frame from the next-in-flow's mFloats list.
>   2. Clear the NS_BLOCK_IS_PUSHED_FLOAT flag on the frame that we're going
> to pull back.
>   3. Append the frame to our mFloats list.

This isn't supposed to be necessary because we're supposed to reflow any floats through their placeholders.  I'd like to avoid making a change of this magnitude.  It also seems likely to risk getting the floats out of order and thus laying them out correctly.


I think it's worth figuring out why we don't reflow the float through its placeholder and pull it back.  That's supposed to happen through the call sequence nsBlockFrame::Reflow -> nsBlockFrame::ReflowDirtyLines -> (see the code I cited above which should force the line to be dirty) nsBlockFrame::ReflowLine -> nsBlockFrame::ReflowInlineFrames -> nsBlockFrame::DoReflowInlineFrames -> nsBlockFrame::ReflowInlineFrame 
> nsLineLayout::ReflowFrame (which potentially recurses through any number of occurrences, to handle any nesting within inlines, of -> nsInlineFrame::Reflow -> nsInlineFrame::ReflowFrames -> nsInlineFrame::ReflowInlineFrame -> nsLineLayout::ReflowFrame) -> nsLineLayout::AddFloat -> nsBlockReflowState::AddFloat, which pulls the frame back and unmarks it as a pushed float.

	David Baron :dbaron:
	Comment 11 • 12 years ago

Er, last line there got mangled because I forgot a dash and it looked like a quote:

-> nsLineLayout::ReflowFrame (which potentially recurses through any number of occurrences, to handle any nesting within inlines, of -> nsInlineFrame::Reflow -> nsInlineFrame::ReflowFrames -> nsInlineFrame::ReflowInlineFrame -> nsLineLayout::ReflowFrame) -> nsLineLayout::AddFloat -> nsBlockReflowState::AddFloat, which pulls the frame back and unmarks it as a pushed float.

	Scott Johnson (:jwir3) Assignee
	Comment 12 • 11 years ago

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #10)
> So in theory, that should already be happening, since we should pull the
> float back when we reflow its placeholder.  A little bit ugly, I admit, and
> not all that great in terms of how it interacts with resizing optimizations.
> But that is what's supposed to be happening.

Yeah, so that makes a lot of sense. I didn't see it right away. Thanks for pointing this out to me.

> See, for example, this bit of nsBlockFrame::ReflowDirtyLines:
> 
>     // If we have a constrained height (i.e., breaking columns/pages),
>     // and the distance to the bottom might have changed, then we need
>     // to reflow any line that might have floats in it, both because the
>     // breakpoints within those floats may have changed and because we
>     // might have to push/pull the floats in their entirety.
>     // FIXME: What about a deltaY or height change that forces us to
>     // push lines?  Why does that work?
>     if (!line->IsDirty() &&
>         aState.mReflowState.availableHeight != NS_UNCONSTRAINEDSIZE &&
>         (deltaY != 0 || aState.mReflowState.mFlags.mVResize) &&
>         (line->IsBlock() || line->HasFloats() || line->HadFloatPushed())) {
>       line->MarkDirty();
>     }

Ok, so what is happening is that nsColumnSetFrame doesn't automatically
mark it's children as dirty. More specifically, it doesn't mark it's //first// child as dirty automatically. Moreover, sometimes, what happens is that the  column set frame will reflow with a certain column height, and then it will reflow again at that same column height. So, for example, this can happen when we had a column height, and then we sort-of manually generate a reflow (which is why it didn't happen until the javascript is run that seems to manually cause this reflow), the column set reflows with the last known column height of its children. Since the column set doesn't set
its first child dirty explicitly, since reflowNext is what controls this, and it's initially set to false), we get into a state where our first child's first line is what contains the placeholder. Since it's the first line of a block, deltaY is going to be 0. Similarly, since we don't set the mVResize (the available height didn't change), this part of the above code resolves to false, meaning that we don't mark the line containing the placeholder as dirty.

There's a couple of approaches we could take to fix this. One would be to explicitly reflow the first child of the column set frame (i.e. mark it dirty during every pass). I think this would be somewhat inefficient, though, as it's not always going to be the case that this child needs to be reflown, and the case we're dealing with here is (I think) a fairly rare case. 

Another option would be to explicitly set the mVResize on each child of the column set frame. This would propagate to all its children, and cause all of the lines with placeholder frames to pull back their corresponding floats. Again, I think this is somewhat inefficient, because in this circumstance, we already know, based on the previous reflow, that we're going to need to push the floats to the next continuation, so there's no need to pull them back, only to push them again. 

Finally, the approach I took was simply to return a reflow status of NS_FRAME_NOT_COMPLETE when we detect that we have a next continuation 
that has floats that were pushed from the block we're currently reflowing.

> (In reply to Scott Johnson (:jwir3) from comment #9)
> > My hypothesis is that the problem we're having stems from having an
> > nsBlockFrame with a next continuation that's empty except for floats that
> > were pushed to it from a previous continuation. This leads to a situation
> > where, once we've reflown the nsBlockFrame that doesn't have the floats, and
> > all content fits within the available height of that frame, we decide that
> > we can remove any next continuations that we have, thus deleting the floats,
> > but not their placeholder (since they are pushed floats, the placeholder
> > frame is in a previous continuation).
> 
> That certainly seems to be something that can lead to a crash.
> 
> Though I wonder if there's something we ought to do to make it so it doesn't
> lead to a crash (maybe asserts instead, though).  For example, we could
> check that a later continuation doesn't have any floats before returning
> that a block is complete.  (We should probably still assert in that case,
> since it's a mistake.)

I added an assertion re: the "belt-and-braces" approach (see below), but I can add another one when we run into the situation described above, if you think that's a good idea. I just didn't know how many assertions we really need for the same mistake situation.

> I think it may well be something we want to commit as a *second*,
> belt-and-braces, solution to the problem, with an assertion that fires
> whenever it kicks in.

I added this, as well as an assertion when this happens. It should also
trigger an assertion in nsColumnSetFrame: e.g. "our next in flow should
have been deleted" if it happens.

> I think it's worth figuring out why we don't reflow the float through its
> placeholder and pull it back.  That's supposed to happen through the call
> sequence nsBlockFrame::Reflow -> nsBlockFrame::ReflowDirtyLines -> (see the
> code I cited above which should force the line to be dirty)
> nsBlockFrame::ReflowLine -> nsBlockFrame::ReflowInlineFrames ->
> nsBlockFrame::DoReflowInlineFrames -> nsBlockFrame::ReflowInlineFrame 
> -> nsLineLayout::ReflowFrame (which potentially recurses through any number of occurrences, to handle any nesting within inlines, of -> nsInlineFrame::Reflow -> nsInlineFrame::ReflowFrames -> nsInlineFrame::ReflowInlineFrame -> nsLineLayout::ReflowFrame) -> nsLineLayout::AddFloat -> nsBlockReflowState::AddFloat, which pulls the frame back and unmarks it as a pushed float.

Thanks. This clue helped a lot in determining what was causing the problem.

	Scott Johnson (:jwir3) Assignee
	Comment 13 • 11 years ago

Pushed to try:
https://tbpl.mozilla.org/?tree=Try&rev=f60f8aa8726d

	David Baron :dbaron:
	Comment 14 • 11 years ago

Why do you need to handle this both inside and outside of reflow?  Shouldn't one (probably inside reflow, since the code is simpler) be enough?

	David Baron :dbaron:
	Comment 15 • 11 years ago

(And I'm still not convinced about the idea that we should only fix this by handling what happens when we don't reflow the placeholders rather than also ensuring that we do reflow them.  I need to look into that more.)

	Scott Johnson (:jwir3) Assignee
	Comment 16 • 11 years ago

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #14)
> Why do you need to handle this both inside and outside of reflow?  Shouldn't
> one (probably inside reflow, since the code is simpler) be enough?

Do you mean why do I handle the problem in both nsBlockFrame::Reflow and nsContainerFrame::ReflowChild? The former solution, as you pointed out, is simpler, and probably better, but the latter one just adds a check to verify that we aren't violating the constraint that we should never delete a next-in-flow child that has pushed floats. Mostly, it's the concept of fixing the problem in more than one way, as discussed in comment 10. Since we know that it's an error condition to delete a next-in-flow child that has floats that were previously pushed from a prev-in-flow, I felt as though we might as well call this situation out and identify it.

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #15)
> (And I'm still not convinced about the idea that we should only fix this by
> handling what happens when we don't reflow the placeholders rather than also
> ensuring that we do reflow them.  I need to look into that more.)

The conditions required for this crash to happen are:

 1) We're reflowing a column set frame (or any other dynamic pagination that we create in the future)
 2) We initiate a reflow of the children of the column set, but don't change their available height
 3) There is at least one child of the column set frame that has floats on its float list where the placeholder frame for those floats is in a previous continuation, and has nothing else in it

If these conditions are all met, then we will be in this exceptional case. My patch handles this by simply detecting if we have pushed floats in a next-in-flow, and if so, returns NS_FRAME_NOT_COMPLETE. I chose this because I felt that forcing a reflow of a set of children when the height of the column set hasn't changed doesn't seem like an efficient thing to do. I did consider detecting whether or not a child of the column set frame has a placeholder within its subtree, and, if so, then set the VResize bit to true, which would force at least the line with the placeholder to be re-reflowed. 

I can change the patch if you think this is a better fix.

	Scott Johnson (:jwir3) Assignee
	Comment 17 • 11 years ago

(In reply to Scott Johnson (:jwir3) from comment #16)
> placeholder within its subtree, and, if so, then set the VResize bit to
> true, which would force at least the line with the placeholder to be
> re-reflowed. 

I meant "set the VResize bit on the child frame", which would force the line with the placeholder to be marked dirty, causing the floats to be sucked back from the next-in-flow.

	David Baron :dbaron:
	Comment 18 • 11 years ago

(In reply to Scott Johnson (:jwir3) from comment #16)
> (In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from
> comment #14)
> > Why do you need to handle this both inside and outside of reflow?  Shouldn't
> > one (probably inside reflow, since the code is simpler) be enough?
> 
> Do you mean why do I handle the problem in both nsBlockFrame::Reflow and
> nsContainerFrame::ReflowChild? The former solution, as you pointed out, is
> simpler, and probably better, but the latter one just adds a check to verify
> that we aren't violating the constraint that we should never delete a
> next-in-flow child that has pushed floats. Mostly, it's the concept of
> fixing the problem in more than one way, as discussed in comment 10.

That wasn't at all what I meant by fixing the problem in more than one way -- that counts as a single way, since it's two changes addressing the same issue.

> Since
> we know that it's an error condition to delete a next-in-flow child that has
> floats that were previously pushed from a prev-in-flow, I felt as though we
> might as well call this situation out and identify it.

Doing that in one place should be sufficient, though.

> I did
> consider detecting whether or not a child of the column set frame has a
> placeholder within its subtree, and, if so, then set the VResize bit to
> true, which would force at least the line with the placeholder to be
> re-reflowed. 

So basically we have the problem that this bit of nsBlockFrame::ReflowDirtyLines (which is already a pretty significant de-optimization) is enough to fix layout of split floats, but isn't sufficient for restoring the breaking state for those floats.
    // If we have a constrained height (i.e., breaking columns/pages),
    // and the distance to the bottom might have changed, then we need
    // to reflow any line that might have floats in it, both because the
    // breakpoints within those floats may have changed and because we
    // might have to push/pull the floats in their entirety.
    // FIXME: What about a deltaY or height change that forces us to
    // push lines?  Why does that work?
    if (!line->IsDirty() &&
        aState.mReflowState.availableHeight != NS_UNCONSTRAINEDSIZE &&
        (deltaY != 0 || aState.mReflowState.mFlags.mVResize) &&
        (line->IsBlock() || line->HasFloats() || line->HadFloatPushed())) {
      line->MarkDirty();
    }
In other words, even if we have a reflow that isn't changing layout, we still need to reflow the floats to restore any continuation state.

A second fix might be something like adding float break state recovery that traverses any blocks or lines that aren't being reflowed in ReflowDirtyLines, finds their placeholders, and reflows the floats.  This might be preferable to trying to do everything that would be needed to make the layout correct, which includes the work that nsBlockFrame::SplitFloat or nsBlockReflowState::PushFloatPastBreak do, which can affect the layout of later floats.  (In other words, I think the failure to reflow the floats is also covering up layout bugs, which reflowing the floats would fix.)  For example, suppose that due to a dynamic change inside of a column, we reflowed a column that had two floats in it.  The first float, due to its size and where the first breakpoint within it was, needed to be pushed past the break.  The second float gets pushed past the break only because the first one was, and we honor the rule about not placing later floats prior to earlier ones (in other words, if the first float wasn't there, the second float would fit in the column).  Now suppose there's a dynamic change to a line in between the lines containing the placeholders of these floats -- one that doesn't change the above situation, but does change the height of that line slightly.  Given the current code, it seems like in the reflow to handle that dynamic change, we'd move the second float into the first column because we didn't reflow the first float at all (and thus call PushFloatPastBreak).

While it might seem admirable to try to fix this without doing the extra work, it requires a nontrivial amount of code that probably won't be correct on the first pass.  I think it's better to get correct behavior here first and worry about optimization later.

	Scott Johnson (:jwir3) Assignee
	Comment 19 • 11 years ago

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #18)
> That wasn't at all what I meant by fixing the problem in more than one way
> -- that counts as a single way, since it's two changes addressing the same
> issue.

Ah, my apologies. I misunderstood and thought you meant "check that the assertion is true in multiple places", rather than "solve the problem in more than one way". I'll remove the stuff that's not in reflow.

> So basically we have the problem that this bit of
> nsBlockFrame::ReflowDirtyLines (which is already a pretty significant
> de-optimization) is enough to fix layout of split floats, but isn't
> sufficient for restoring the breaking state for those floats.
>     // If we have a constrained height (i.e., breaking columns/pages),
>     // and the distance to the bottom might have changed, then we need
>     // to reflow any line that might have floats in it, both because the
>     // breakpoints within those floats may have changed and because we
>     // might have to push/pull the floats in their entirety.
>     // FIXME: What about a deltaY or height change that forces us to
>     // push lines?  Why does that work?
>     if (!line->IsDirty() &&
>         aState.mReflowState.availableHeight != NS_UNCONSTRAINEDSIZE &&
>         (deltaY != 0 || aState.mReflowState.mFlags.mVResize) &&
>         (line->IsBlock() || line->HasFloats() || line->HadFloatPushed())) {
>       line->MarkDirty();
>     }
> In other words, even if we have a reflow that isn't changing layout, we
> still need to reflow the floats to restore any continuation state.

I agree. It sounds like you would like this to be part of the patch for the current crash, is that correct?

> 
> A second fix might be something like adding float break state recovery that
> traverses any blocks or lines that aren't being reflowed in
> ReflowDirtyLines, finds their placeholders, and reflows the floats.  This
> might be preferable to trying to do everything that would be needed to make
> the layout correct, which includes the work that nsBlockFrame::SplitFloat or
> nsBlockReflowState::PushFloatPastBreak do, which can affect the layout of
> later floats.  (In other words, I think the failure to reflow the floats is
> also covering up layout bugs, which reflowing the floats would fix.)

> For example, suppose that due to a dynamic change inside of a column, we
> reflowed a column that had two floats in it.  The first float, due to its
> size and where the first breakpoint within it was, needed to be pushed past
> the break.  The second float gets pushed past the break only because the
> first one was, and we honor the rule about not placing later floats prior to
> earlier ones (in other words, if the first float wasn't there, the second
> float would fit in the column).  Now suppose there's a dynamic change to a
> line in between the lines containing the placeholders of these floats -- one
> that doesn't change the above situation, but does change the height of that
> line slightly.  Given the current code, it seems like in the reflow to
> handle that dynamic change, we'd move the second float into the first column
> because we didn't reflow the first float at all (and thus call
> PushFloatPastBreak).

This example makes a lot of sense. I appreciate you making this problem more concrete.

> While it might seem admirable to try to fix this without doing the extra
> work, it requires a nontrivial amount of code that probably won't be correct
> on the first pass.  I think it's better to get correct behavior here first
> and worry about optimization later.

It sounds to me like you're advocating that we fix this crash (i.e. the patch I submitted, minus the stuff that was happening outside of reflow, plus the changes to make sure floats get reflowed even if we don't have layout changes), and then create a new bug to fix float breaking issues (the work described under "As a second fix..." above).

Am I interpreting this correctly?

	David Baron :dbaron:
	Comment 20 • 11 years ago

(In reply to Scott Johnson (:jwir3) from comment #19)
> I agree. It sounds like you would like this to be part of the patch for the
> current crash, is that correct?

I don't think we should hold up getting one of the fixes in in order to get the other in, but I think it is worth trying to fix in both ways.

> > While it might seem admirable to try to fix this without doing the extra
> > work, it requires a nontrivial amount of code that probably won't be correct
> > on the first pass.  I think it's better to get correct behavior here first
> > and worry about optimization later.
> 
> It sounds to me like you're advocating that we fix this crash (i.e. the
> patch I submitted, minus the stuff that was happening outside of reflow,
> plus the changes to make sure floats get reflowed even if we don't have
> layout changes), and then create a new bug to fix float breaking issues (the
> work described under "As a second fix..." above).
> 
> Am I interpreting this correctly?

That's fine, though I wasn't attempting to express an opinion about what goes in what bug.

	Scott Johnson (:jwir3) Assignee
	Comment 21 • 11 years ago

Added bug 851629 to track the work of fixing float breaking issues.

	Scott Johnson (:jwir3) Assignee
	Comment 22 • 11 years ago

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #20)
> I don't think we should hold up getting one of the fixes in in order to get
> the other in, but I think it is worth trying to fix in both ways.

I attached the first part of these two fixes. I'm still working on the second part.

	David Baron :dbaron:
	Comment 23 • 11 years ago

Comment on attachment 725672 [details] [diff] [review]
b600100-part1

>+  // If we have a next-in-flow, and that next-in-flow has pushed floats from
>+  // this frame from a previous iteration of reflow, then we should not return
>+  // a status of NS_COMPLETE, since we actually have overflow, it's just already
>+  // been handled.

I think this comment should:
 (1) make it clear this is a safety precaution to handle something that actually shouldn't happen
 (2) NS_COMPLETE -> NS_FRAME_COMPLETE

>+  nsBlockFrame* nif = static_cast<nsBlockFrame*>(GetNextInFlow());
>+  if (nif && nif->HasPushedFloatsFromPrevContinuation()) {
>+    NS_MergeReflowStatusInto(&state.mReflowStatus, NS_FRAME_NOT_COMPLETE);
>+  }

So I'm a little concerned that this might not be sufficient -- what if the floats got pushed not just to a next-in-flow, but even further, to its next-in-flow?

That said, we wouldn't want to loop over all the continuations in every reflow.

So unless you have an explanation for why you only need to check one next-in-flow and not all of them, I think you should:
 * only enter this code when NS_FRAME_IS_COMPLETE(state.mReflowStatus)
 * make it loop over next-in-flows

>diff --git a/layout/generic/nsBlockFrame.h b/layout/generic/nsBlockFrame.h
>--- a/layout/generic/nsBlockFrame.h
>+++ b/layout/generic/nsBlockFrame.h
>@@ -465,16 +465,34 @@ public:
>   /** Load all of aFrame's floats into the float manager iff aFrame is not a
>    *  block formatting context. Handles all necessary float manager translations;
>    *  assumes float manager is in aFrame's parent's coord system.
>    *  Safe to call on non-blocks (does nothing).
>    */
>   static void RecoverFloatsFor(nsIFrame*       aFrame,
>                                nsFloatManager& aFloatManager);
> 
>+  /**
>+   * Determine if we have any pushed floats from a previous continuation.
>+   *
>+   * @returns true, if any of the floats at the beginning of our mFloats list
>+   *          have the NS_FRAME_IS_PUSHED_FLOAT bit set; false otherwise.
>+   */
>+  bool HasPushedFloatsFromPrevContinuation() const {
>+    if (!mFloats.IsEmpty()) {
>+      for (int32_t i = 0; i < mFloats.GetLength(); i++) {
>+        if (mFloats.FrameAt(i)->GetStateBits() & NS_FRAME_IS_PUSHED_FLOAT) {
>+          return true;
>+        }
>+      }
>+    }
>+
>+    return false;
>+  }

This doesn't need to loop; pushed floats are always at the beginning of the floats list, so you should only need to check the first float.  (It might be worth asserting, #ifdef DEBUG, that this is the case.  But it shouldn't be necessary to loop for the functional part.)


Otherwise this looks good, but I'd like to look at the revisions, so marking review-.

	Scott Johnson (:jwir3) Assignee
	Comment 24 • 11 years ago

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #23)
> I think this comment should:
>  (1) make it clear this is a safety precaution to handle something that
> actually shouldn't happen
>  (2) NS_COMPLETE -> NS_FRAME_COMPLETE

Sure, I'll make those changes.

> So I'm a little concerned that this might not be sufficient -- what if the
> floats got pushed not just to a next-in-flow, but even further, to its
> next-in-flow?

Well, my thinking was that if we have pushed floats from a continuation to it's next-in-flow, which are then subsequently pushed to its next-next-in-flow, then my assumption is that it must be the case 1) that we have pushed floats on our mFloats list, and 2) that those pushed floats are the only things on the floats list.

I thought about whether we wanted to iterate over all of a given frame's continuations, and my thinking (at that time) was no. My original rationale was that I didn't think we could have a next-in-flow that had no floats, but which had pushed floats from its previous continuation. 

Now, this said, it doesn't solve the problem where we have multiple continuations that have pushed floats, but I think that returning NS_FRAME_NOT_COMPLETE would be sufficient to reflow our next-in-flow, which would then take care of its previously pushed floats.
 
> That said, we wouldn't want to loop over all the continuations in every
> reflow.

Yes, this is what I was really concerned about - adding another potentially O(n) loop to the reflow.

> So unless you have an explanation for why you only need to check one
> next-in-flow and not all of them, I think you should:
>  * only enter this code when NS_FRAME_IS_COMPLETE(state.mReflowStatus)
>  * make it loop over next-in-flows

I think this is a reasonable safeguard/compromise. I'll implement it this way and re-post for review.

> This doesn't need to loop; pushed floats are always at the beginning of the
> floats list, so you should only need to check the first float.  (It might be
> worth asserting, #ifdef DEBUG, that this is the case.  But it shouldn't be
> necessary to loop for the functional part.)

Ah, right. So, I was worried that the floats might somehow get out of order, but, provided we maintain that invariant, it should be fine. I'll add the assert in a #ifdef DEBUG statement.

	Scott Johnson (:jwir3) Assignee
	Comment 25 • 11 years ago

New patch with review comments addressed.

	Scott Johnson (:jwir3) Assignee
	Comment 26 • 11 years ago

As for part 2, I think there are two approaches to this problem: 

1) (I've been working on this one first, and I have a solution, but I think maybe option 2 is more efficient) Add a method within nsLayoutUtils that will check, given a frame that is at the root of the subtree, whether or not that subtree has a placeholder frame within it. We'll use this check at the check in nsBlockFrame::ReflowDirtyLines() mentioned in comment 18, and if a line has a placeholder frame within it, then we'll mark that line dirty.

Note that for this, I believe we'll have to search through the principal child list, the overflow containers list, the excess overflow containers list, and the popup list (this last one I'm not 100% sure about, as I don't know exactly what goes into the popup list). I'm also making the assumption that the 'colgroup' list is simply a different ordering of frames already on the principal child list. If this isn't the case, then we'd have to probably search through that list, as well.

2) Add a frame state bit, NS_FRAME_HAS_PLACEHOLDER_CHILDREN, which indicates that this frame is an ancestor of a placeholder frame. The bit will be set on all the ancestors of a placeholder frame whenever its parent is set. We'll check for this bit in the same area as discussed in #1.

The downside to #1 is that it's inefficient. I thought about doing #2 first, but I was concerned that we might be cluttering up the amount of frame state bits that we have with small additions like this. On the other hand, I might be able to compromise by adding a reflow state bit, instead of a global frame state bit. We'd have to do the searching through the tree probably at least once per reflow, in order to build the frame state bits initially.

	David Baron :dbaron:
	Comment 27 • 11 years ago

Comment on attachment 726163 [details] [diff] [review]
b600100-part1 (v2)

r=dbaron

	David Baron :dbaron:
	Comment 28 • 11 years ago

Hmmm.  Both of the options in comment 26 seem a bit like overkill.  I'm wondering if maybe the aState.mReflowState.mFlags.mVResize condition in:

    // If we have a constrained height (i.e., breaking columns/pages),
    // and the distance to the bottom might have changed, then we need
    // to reflow any line that might have floats in it, both because the
    // breakpoints within those floats may have changed and because we
    // might have to push/pull the floats in their entirety.
    // FIXME: What about a deltaY or height change that forces us to
    // push lines?  Why does that work?
    if (!line->IsDirty() &&
        aState.mReflowState.availableHeight != NS_UNCONSTRAINEDSIZE &&
        (deltaY != 0 || aState.mReflowState.mFlags.mVResize) &&
        (line->IsBlock() || line->HasFloats() || line->HadFloatPushed())) {
      line->MarkDirty();
    }

isn't actually quite the condition we want.

Because in this case, we somehow hit a case with different break points, but without hitting that condition.  Maybe we need a condition that better reflects a change in available height rather than a change in containing block height?

	Scott Johnson (:jwir3) Assignee
	Comment 29 • 11 years ago

(In reply to David Baron [:dbaron] (don't cc:, use needinfo? instead) from comment #28)
> Hmmm.  Both of the options in comment 26 seem a bit like overkill.  I'm
> wondering if maybe the aState.mReflowState.mFlags.mVResize condition in:
> isn't actually quite the condition we want.
> Because in this case, we somehow hit a case with different break points, but
> without hitting that condition.  Maybe we need a condition that better
> reflects a change in available height rather than a change in containing
> block height?

It's probably true that we want a different condition. What we have is a situation where we've reflown at an available height (6840), which is determined to be feasible, however, we are forced to reflow the column set frame again, at the same height. Unfortunately, detecting a change in available height probably won't help us... The available height of the containing blocks doesn't change between these two reflows, which is, I believe, the problem. 

One question I have is whether we should be reflowing our children if their available height didn't change. That is, if aConfig.mColMaxHeight (the height we're currently reflowing at) == mLastBalanceHeight (the height that we last reflowed at), then perhaps we should just return early from reflow, since we don't really have anything to do?

	Scott Johnson (:jwir3) Assignee
	Comment 30 • 11 years ago

So, one thing we could do is force a vertical resize of child frames of the column set frame if the last balance height matches the current balance height. This fixes the problem, but only in the case of columns. 

Do you think we need something more general (i.e. an adjustment of the condition you pointed out in nsBlockFrame itself)?

	Scott Johnson (:jwir3) Assignee
	Comment 31 • 11 years ago

This is an option for forcing the vertical resize in the case where the column set frame didn't adjust the available height of its children (as described in comment 30).

	Scott Johnson (:jwir3) Assignee
	Comment 32 • 11 years ago

Part 1 pushed to inbound:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3b18c328b316

	Scott Johnson (:jwir3) Assignee
	Comment 33 • 11 years ago

Backed out (incorrect commit message):
https://hg.mozilla.org/integration/mozilla-inbound/rev/f33c62af87e3

and re-pushed with correct commit message:
https://hg.mozilla.org/integration/mozilla-inbound/rev/2ed966e4fa58

	Mats Palmgren (inactive)
	Comment 34 • 11 years ago

Comment on attachment 726163 [details] [diff] [review]
b600100-part1 (v2)

A couple of drive-by nits:

>+      if (mFloats.FrameAt(0)->GetStateBits() & NS_FRAME_IS_PUSHED_FLOAT) {

mFloats.FirstChild() would be more efficient.

>+#ifdef DEBUG
>+    // Double-check the above assertion that pushed floats should be at the
>+    // beginning of our floats list.
>+    for (int32_t i = 0; i < mFloats.GetLength(); i++) {
>+      NS_ASSERTION(!(mFloats.FrameAt(i)->GetStateBits() &
>+        NS_FRAME_IS_PUSHED_FLOAT),
>+        "pushed floats must be at the beginning of the float list");
>+    }
>+#endif

It's just debug code, but...
both mFloats.GetLength() and mFloats.FrameAt() are O(n).

In general, I think we shouldn't add more uses nsFrameList::FrameAt(),
IndexOf(), Length() etc, so we can remove them eventually.

The preferred way to iterate a frame list is:
for (nsFrameList::Enumerator e(mFloats); !e.AtEnd(); e.Next()) {
  nsIFrame* f = e.get();
  ...
}

	Scott Johnson (:jwir3) Assignee
	Comment 35 • 11 years ago

(In reply to Mats Palmgren [:mats] from comment #34)
> Comment on attachment 726163 [details] [diff] [review]
> b600100-part1 (v2)
> 
> A couple of drive-by nits:

Thanks, mats. I'll make these changes and push a follow-up patch for review.

	Scott Johnson (:jwir3) Assignee
	Comment 36 • 11 years ago

Followup patch to address mats' review comments.

	Mats Palmgren (inactive)
	Comment 37 • 11 years ago

Comment on attachment 726698 [details] [diff] [review]
b600100-part3

It looks like the assertion expression would fit on the same line now?
r=mats with that.

	Scott Johnson (:jwir3) Assignee
	Comment 38 • 11 years ago

(In reply to Mats Palmgren [:mats] from comment #37)
> It looks like the assertion expression would fit on the same line now?
> r=mats with that.

Fixed, and pushed to inbound:
https://hg.mozilla.org/integration/mozilla-inbound/rev/7ea4ad83da53

	Scott Johnson (:jwir3) Assignee
	Comment 39 • 11 years ago

Comment on attachment 726331 [details] [diff] [review]
b600100-part2

I'm going to post a slightly different version of this patch.

	Scott Johnson (:jwir3) Assignee
	Comment 40 • 11 years ago

Added a new nsHTMLReflowState flag to track this condition, rather than overloading the mVResize flag.

mats, I'm requesting review from you, because dbaron is gone for a few days. Basically, comment 28 explains (generally) what I'm doing here. This is just another, backup fix for this bug (it already is fixed by the patch for part1, but dbaron thought it would be good to add another fix for it, just to make sure it doesn't get into the unexpected state where a frame is complete, but its next-in-flow has pushed floats which weren't sucked back since we didn't actually do a reflow of the placeholder frame).

	Ryan VanderMeulen [:RyanVM]
	Comment 41 • 11 years ago

https://hg.mozilla.org/mozilla-central/rev/2ed966e4fa58

	Ed Morley [:emorley]
	Comment 42 • 11 years ago

https://hg.mozilla.org/mozilla-central/rev/7ea4ad83da53

	Mats Palmgren (inactive)
	Comment 43 • 11 years ago

Comment on attachment 726800 [details] [diff] [review]
b600100-part2

I haven't read all the bug comments in detail so I'm just reviewing
the code changes as such, ie. not why you need to do this in the first
place.  dbaron should probably review this when he comes back too.

>+  bool colHeightChanged = true;
>+
>   if (mLastBalanceHeight != aConfig.mColMaxHeight) {
>     mLastBalanceHeight = aConfig.mColMaxHeight;
>     // XXX Seems like this could fire if incremental reflow pushed the column set
>     // down so we reflow incrementally with a different available height.
>     // We need a way to do an incremental reflow and be sure availableHeight
>     // changes are taken account of! Right now I think block frames with absolute
>     // children might exit early.
>     //NS_ASSERTION(aKidReason != eReflowReason_Incremental,
>     //             "incremental reflow should not have changed the balance height");
>+  } else {
>+    colHeightChanged = false;
>   }

Seems clearer to write this without the 'else', like so:

const bool colHeightChanged = mLastBalanceHeight != aConfig.mColMaxHeight;
if (colHeightChanged) {
  ...
}

>+      kidReflowState.mFlags.mMustReflowPlaceholders =
>+        kidReflowState.mFlags.mMustReflowPlaceholders | !colHeightChanged;

kidReflowState was created just a few lines up so I think the flag
mMustReflowPlaceholders is zero here, so this is simpler:

>+      kidReflowState.mFlags.mMustReflowPlaceholders = !colHeightChanged;

r=mats, feel free to land it with those nits fixed, but please get dbaron
to review it later since he's more familiar with the bug details.

	Scott Johnson (:jwir3) Assignee
	Comment 44 • 11 years ago

Comment on attachment 726800 [details] [diff] [review]
b600100-part2

> r=mats, feel free to land it with those nits fixed, but please get dbaron
> to review it later since he's more familiar with the bug details.

Ok, thanks. dbaron, if you wouldn't mind looking this over and giving comments? (I'll wait to land it, since another fix for this bug has already gone in).

	Scott Johnson (:jwir3) Assignee
	Comment 45 • 11 years ago

Here's the updated patch.

	Scott Johnson (:jwir3) Assignee
	Comment 46 • 11 years ago

Comment on attachment 727242 [details] [diff] [review]
b600100-part2 (v2)

(In reply to Mats Palmgren [:mats] from comment #43)
> r=mats, feel free to land it with those nits fixed, but please get dbaron
> to review it later since he's more familiar with the bug details.

Based on this comment, I'm going to change this to feedback? and land it, since dbaron is quite busy, and it's already been reviewed. I think we want to get this fix in, as it will likely prevent crashes related to floats in column sets. 

We can always back out if it's not what we want.

	Scott Johnson (:jwir3) Assignee
	Comment 47 • 11 years ago

Part 2 inbound:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f0c903d9ade4

	Ryan VanderMeulen [:RyanVM]
	Comment 48 • 11 years ago

https://hg.mozilla.org/mozilla-central/rev/f0c903d9ade4