282173 - Remove BuildFloatList

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It is time. I have a patch that seems to work for regular pages with floats,
print/print preview, and columns (in columns, only as long as the float doesn't
break, but float breaking in columns is already stuffed). I'm looking at the
bugs that Boris labelled as issues...

Comment 1

[Boris Zbarsky [:bzbarsky]]

roc, do you still have that patch around?

Comment 2

[Robert O'Callahan (:roc) (email my personal email if necessary)]

No. But I'll recreate it tomorrow.

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: fix

Here's the patch.

I've tested it on a set of my evil float tests, with success. But this code is hellacious so it will need more testing before it can land on branch. I think most or all of my paginated-float fixes landed for FF1.5 so hopefully this will apply there.

As far as performance goes, for non-paginated context this should be a clear win.

Comment 4

[Boris Zbarsky [:bzbarsky]]

So...  Should CollectFloats() be testing IsBlockLevel() or IsFloatContainingBlock()?  It might not matter either way, I guess...

Also, won't the use of the float cache in CheckFloats() lead to asserts any time BuildFloatList() was buggy?  After all, a bug in BuildFloatList() exactly means that a float didn't end up in the float cache, for whatever reason.

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #4)
> So...  Should CollectFloats() be testing IsBlockLevel() or
> IsFloatContainingBlock()?  It might not matter either way, I guess...

I think it should be calling IsFloatContainingBlock(), yeah. Assume that change :-).

> Also, won't the use of the float cache in CheckFloats() lead to asserts any
> time BuildFloatList() was buggy?  After all, a bug in BuildFloatList()
> exactly means that a float didn't end up in the float cache, for whatever
> reason.

Yes. This is incredibly useful for my debugging. Should I make it DEBUG_roc?

Comment 6

[Boris Zbarsky [:bzbarsky]]

Oh, so CheckFloats() is checking the correctness of the float cache rather than the correctness of our code that builds the mFloats frame list?

If so, as-is is probably fine, though there are non-exceptional circumstances that will guarantee asserts (eg a too-deep frame tree where we never reflow the float placeholder).

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

It's a consistency check. They can legitimately become inconsistent, but any such situation is at least unusual, if not exceptional, and therefore interesting to know about if one is debugging...

Comment 8

[Boris Zbarsky [:bzbarsky]]

In that case we may want to make it DEBUG_something (including both of us at least, and dbaron if he wants to?).  That way people doing fuzz-testing on the sorts of testcases this bug blocks won't hit the asserts.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

how about we make it NS_WARNING?

Comment 10

[Boris Zbarsky [:bzbarsky]]

Sure, if it won't get lost in the warning noise we have.  :(

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #3)
> I've tested it on a set of my evil float tests, with success.

Presumably those tests include lots of pagination / columns tests, right?

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 214142 [details] [diff] [review]
fix

>   // All continuation placeholders need to be moved to the front of
>   // our line list. We also need to maintain the invariant that at


...


>   // Placeholders for continuation out-of-flow frames that need to
>-  // move to our next in flow are placed here during reflow.
>+  // move to our next in flow are placed here during reflow. At the end of reflow
>+  // they move to the end of the overflow lines.
>+  // Their out-of-flows are not in any child list during reflow, but are added
>+  // to the overflow-out-of-flow list when the placeholders are appended to
>+  // the overflow lines.
>   nsFrameList mOverflowPlaceholders;

Why the end of the overflow lines?  It seems like the beginning might make more sense, and be more consistent with the previous comment, although maybe I'm not understanding the terms correctly.  Aren't overflow placeholders placeholders for floats (or split parts thereof) that have been pushed to the next page/column even though their anchor point has not been?  I'd think they ought to be before any placeholders that really are the anchor point, since the anchor points are earlier.

Comment 13

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #11)
> (In reply to comment #3)
> > I've tested it on a set of my evil float tests, with success.
> 
> Presumably those tests include lots of pagination / columns tests, right?

Columns, yes. I tested a few print-preview testcases from float-related bugs.

(In reply to comment #12)
> (From update of attachment 214142 [details] [diff] [review] [edit])
> >   // All continuation placeholders need to be moved to the front of
> >   // our line list. We also need to maintain the invariant that at
> 
> 
> ...
> 
> 
> >   // Placeholders for continuation out-of-flow frames that need to
> >-  // move to our next in flow are placed here during reflow.
> >+  // move to our next in flow are placed here during reflow. At the end of reflow
> >+  // they move to the end of the overflow lines.
> >+  // Their out-of-flows are not in any child list during reflow, but are added
> >+  // to the overflow-out-of-flow list when the placeholders are appended to
> >+  // the overflow lines.
> >   nsFrameList mOverflowPlaceholders;
> 
> Why the end of the overflow lines?  It seems like the beginning might make
> more sense, and be more consistent with the previous comment, although maybe
> I'm not understanding the terms correctly.  Aren't overflow placeholders
> placeholders for floats (or split parts thereof) that have been pushed to the
> next page/column even though their anchor point has not been?  I'd think they
> ought to be before any placeholders that really are the anchor point, since
> the anchor points are earlier.

I believe these comments are correct and consistent if properly interpreted :-) (which isn't easy, I know). These overflow placeholders are placeholders for the next-in-flows of floats in this block, where the next-in-flow is also in this block for some reason.

Perhaps some examples will help:

Suppose we have a block with two frames in its flow-list: B1 and B2. Suppose B1 contains a float F1, with placeholder P1 on a normal line of B1. Suppose we reflow B1 and F1 needs to break. We create F1's next-in-flow F2, with placeholder P2; P2 goes on B1's mOverflowPlaceholders, F2 dangles. When we finish reflowing B1, P2 gets appended to the end of B1's overflow lines, and F2 goes onto the overflow-out-of-flow list. When we start reflowing B2, we call DrainOverflowLines, which puts P2 as the first frame in B2's first line (as it should be, since we want F2 to be the first thing in B2) and makes F2 a child of B2.

Here's another example. As before, but suppose that after creating F2 and P2, something else happens during B1's reflow that means we decide the line containing P1 must be pushed to overflow after all. Now P1 is in the overflow lines and F1 is in the overflow-out-of-flows list. When we finish reflowing B1, we move P2 from mOverflowPlaceholders to the end of the overflow-out-of-flows list and F2 to the end of the overflow-out-of-flows list. This is where we depend on mOverflowPlaceholders's contents going to the end of the overflow lines; if they went elsewhere, say the beginning, then we'd have P2 before P1 and then we're doomed.

Does this help?

Comment 14

[Robert O'Callahan (:roc) (email my personal email if necessary)]

> we move P2 from mOverflowPlaceholders to the end of the overflow-out-of-flows

Of course I meant

we move P2 from mOverflowPlaceholders to the end of the overflow lines

Comment 15

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #13)
> placeholder P2; P2 goes on B1's mOverflowPlaceholders, F2 dangles. When we
> finish reflowing B1, P2 gets appended to the end of B1's overflow lines, and F2
> goes onto the overflow-out-of-flow list. When we start reflowing B2, we call
> DrainOverflowLines, which puts P2 as the first frame in B2's first line (as it
> should be, since we want F2 to be the first thing in B2) and makes F2 a child
> of B2.

OK, so we're putting P2 at the end of the overflow lines so that DrainOverflowLines reverses the order and puts it at the beginning?  I agree things will end up right, but it seems like it would be less confusing if we could avoid the reversing.

Comment 16

[Robert O'Callahan (:roc) (email my personal email if necessary)]

We could create yet another overflow list(In reply to comment #15)
> OK, so we're putting P2 at the end of the overflow lines so that
> DrainOverflowLines reverses the order and puts it at the beginning?

In my second example, when DrainOverflowLines examines F2, it discovers that it already has a frame for that float (F1) in this block (B2). It therefore pushes F2 directly to the block's mOverflowPlaceholders. So it's not really "reversing" ... the way the code is written, and the way I like to think about it, is that DrainOverflowLines simply collects all float continuation placeholders (from the prev-in-flow overflow lines, this block's normal lines, and this block's overflow lines) and sends them all to their right places (which is either the front of this block's normal line list, or the block's mOverflowPlaceholders).

> I agree things will end up right, but it seems like it would be less
> confusing if we could avoid the reversing.

The only alternative that springs to mind is to create yet another kind of overflow list and put them on it. Probably this means taking mOverflowPlaceholders out of nsBlockReflowState and making it always a real child list of the block. I can do this, but I'm not sure it's a net decrease in confusion. If you think it is, I will do it.

Comment 17

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 214142 [details] [diff] [review]
fix

r+sr=dbaron, although I couldn't force myself to look all that closely, despite that you want this for the branch.

There are some random whitespace changes in the patch, in both directions (adding and removing trailing whitespace).  Could you tend towards removing trailing whitespace?

Also, could you make the printf in CheckFloats say something like "FLOAT LIST OUT OF SYNC!", so it's obvious why it's printing stuff?

I hate the way we do breaking -- I wish we split frames more immediately rather than propagating status out -- that would also give us the ability to push floats to a continuation of the space-manager-causing frame without reparenting them, which is ugly and probably causes a bunch of bugs.

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #17)
> I hate the way we do breaking -- I wish we split frames more immediately rather
> than propagating status out -- that would also give us the ability to push
> floats to a continuation of the space-manager-causing frame without reparenting
> them, which is ugly and probably causes a bunch of bugs.

I'm not sure what you mean.

What should happen to float continuations when the space-manager-causing frame has copmleted is at least partly a CSS spec question.

Comment 19

[Robert O'Callahan (:roc) (email my personal email if necessary)]

checked in.

Comment 20

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #18)
> What should happen to float continuations when the space-manager-causing frame
> has copmleted is at least partly a CSS spec question.

When such a frame has an intrinsic height, it generally expands to contain floats.  Then again, there's the case where it has a specified height that doesn't cross the page/column boundary.

Comment 21

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #20)
> When such a frame has an intrinsic height, it generally expands to contain
> floats.  Then again, there's the case where it has a specified height that
> doesn't cross the page/column boundary.

... or doesn't cross as many boundaries as its floats.

This is related to a specification problem I raised with the WG a while ago, namely, what happens when an element with specified height ends before a page or column boundary, but whose in-flow children cross the boundary.

Comment 22

[Jesse Ruderman]

Thanks, roc!

Of the 8 bugs blocked by this one, 4 were fixed by this change and 2 were already WFM :)

Bug 322436 and bug 330998 remain open.

Comment 23

[Daniel Veditz [:dveditz]]

Is this patch acceptable for the 1.8/1.8.0 branches? Doesn't seem to mangle any API's and fixes some crashes we'd really like fixed.

Comment 24

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Remarkably, no regressions have been attributed to this patch. I think we should go for branch.

Comment 25

[Mike Schroepfer]

Does this impact visual layout in any way - i.e. any risk of web-compat bustage here on the branch?

Comment 26

[Robert O'Callahan (:roc) (email my personal email if necessary)]

No.

Comment 27

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Fixed on 1.8 branch

Comment 28

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: branch patch

Comment 29

[Daniel Veditz [:dveditz]]

Comment on attachment 229199 [details] [diff] [review]
branch patch

approved for 1.8.0 branch, a=dveditz for drivers

Comment 30

[Steve Snyder]

The branch patch won't build on 1.8.0.6 due to naming errors.  The new routine is defined as CheckFloatList() but there are instead 3 references to CheckFloats() in the code.

That's not good.

Comment 31

[Steve Snyder]

Oops.  Typed too quickly.  Should have written:

Branch patch won't build because routine is defined as CheckFloatList() in the header file and CheckFloats() in the source file.

Ahem.

Comment 32

[Daniel Veditz [:dveditz]]

You're right, and the bustage is fixed:
http://tinderbox.mozilla.org/bonsai/cvslog.cgi?file=mozilla/layout/generic/nsBlockFrame.h&rev=MOZILLA_1_8_0_BRANCH&root=/cvsroot

For bugs that are fixed always verify the patch against what was actually checked-in: minor merging fixes like this are not uncommon.