191448 - space manager too limited for handling floats

Status: VERIFIED FIXED

(Core :: Layout: Floats, defect)

Description

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

I'm filing this as a meta-bug for problems with the space manager (which is just
one part of the way we handle floats).  In particular, treating floats as just a
bunch of rectangles taking up space (which is an oversimplification of what the
space manager does, but it probably tends too much in that direction) doesn't
seem sufficient for some purposes.  I admit I haven't looked at the code closely
enough to know how deep the design problems are, but when I do get a chance to
look at it I want a list of all the relevant issues that I've noticed.

Comment 1

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

...and it's also much more general than it needs to be, in many ways.

I think we should probably just toss it out and write an nsFloatManager designed to manage floats.  (Thinking about fixing things like bug 25888 is quite hard right now.)

Comment 2

[Boris Zbarsky [:bzbarsky]]

I swear I thought roc made that comment until I loaded the bug. ;)  See bug 270392 comment 15 and bug 270392 comment 16.

Comment 3

[Eli Friedman]

My thoughts (I thought it would be an interesting exercise to figure out how to put this together, so here it is.  I haven't done any coding on this, and I don't know if I will.):

The simplest implementation would be something like bug 270392 comment 16: two linked lists detailing the boundaries of the left and right floats, i.e. the left float edge is -Infinity until 100 pixels, then 150px until 200 pixels, etc., plus a similar list for right floats.  I believe this is sufficient to completely represent all the state we need to keep about floats.

Normal cost to generate is about O(N) in the number of floats.  I think if we cache the topmost region appended floats can be inserted into (which is just the top of the last float inserted), it ends up being O(N) in general for float appends even in extreme cases like bug 371885 because of the CSS rule that a later float can't begin above an earlier float. The structure would probably be thrown out and regenerated for operations other than appends because the state needed would be complicated to keep around otherwise. Memory cost per float is at most 24 bytes, but probably more like 12 bytes or less per float in most float-intense cases (approaching 0 bytes per float in extreme cases). An nsFloatManager would probably be 24 bytes: for each of left and right, a pointer to the float insertion point, a pointer to the beginning of the list, and the y-coordinate of the bottom of the last region (we could pull some circular linked list trickery, but it's probably not worth bothering).

Overall, it's cheap enough that it wouldn't be an issue to keep around, and it would be a significant performance win for incremental document construction if we kept it around because it would eliminate the need to call RecoverFloats in the append case.  Also, since we're going to throw out the float manager for operations other than appends, we can throw out the state for floats above the last line reflowed, leading to a small memory footprint in most cases.

Another advantage of this approach is that it would be basically a drop-in replacement for the current space manager, with very few changes to other code needed.

We could possibly do something more complicated, but I can't think of any real-world cases where it would be a benefit, and it would be difficult to make O(N) in general.

It'll be a pain to implement Push/PopState efficiently, though... probably the best way would be through some sort of delegation scheme, where regions can refer to regions in the parent instead of storing their own data, plus a merge function.  I think that'll end up leading to some ugly code involving a union and storing a flag in a pointer so as not the bloat the list elements; however, it is cheap and algorithmically simple.

Comment 4

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

So I have some work in progress in my patch queue (written today) that drastically simplifies the space manager (and renames it to float manager).  It doesn't attempt to add any functionality (e.g., ability to keep around); the idea is to start by removing all the stuff we don't need so we have something easier to work with.  (I'd also like to use the new foundation to fix bug 25888.)

http://hg.mozilla.org/users/dbaron_mozilla.com/patches/

The data structures I picked are a bit different from what Eli suggested in comment3; I'm also not all that happy about them, but it seemed like the quickest way to get something somewhat efficient working.  I suspect there are some clever ways to improve things.

I'm currently trying to get reftests passing again; I fixed a whole bunch, but now I'm failing layout/reftests/bugs/387201-1.html (although I think the new behavior may actually be correct per spec; I'm still not sure why it changed, though; perhaps there was code deep in the space manager to ignore 0-width rects), and then crashing on layout/reftests/bugs/421710-1.html.

Comment 5

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

For what it's worth, I got reftests passing again last night.  I'm still not all that confident about my PopState and RemoveTrailingRegions implementations, although I did have to rewrite the latter to fix the crash in layout/reftests/bugs/421710-1.html.

Comment 6

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

Attachment: patch 1: remove the VerifyReflow code comparing space managers

I just removed this, since I didn't see the need to reimplement this because:
 (1) I don't see the need to compare float manager state rather than just the resulting frame positions
 (2) I don't know of anybody using VerifyReflow in the past 8 years

Comment 7

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

Attachment: patch 2: remove TestSpaceManager

It hasn't been part of the build for ages anyway.

Comment 8

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

Attachment: patch 3: renaming of classes, macros, variables, comments

I tried to separate out most of the really boring part into its own patch.  Substantial parts of this patch were written with sed.  (I don't think I have any nsNameFloatManagers in it, though :-).)

The file renames are *not* in this patch; they're in the main patch.

Comment 9

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

Attachment: patch 4: replace nsSpaceManager and nsBlockBandData with nsFloatManager

Here's the main patch; holding off for now on requesting review on this one.

Comment 10

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

I think I'm going to simplify patch 4 a good bit:  as roc suggested yesterday, there's no need to have the band data structures at all.  GetBandInfo shouldn't be any more complicated without it.  (I'm not sure why I didn't see that when he said so.)  That will make PopState much simpler, since most of the complexity there is updating the bands.

Comment 11

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

Attachment: patch 4: replace nsSpaceManager and nsBlockBandData with nsFloatManager

Here's the simpler version.  GetBandInfo is a little more complicated now, but it's still just walking backwards through a list, and the rest is a lot simpler.

I'll attach nsFloatManager.h and .cpp separately as well, since they're pretty unreadable in diff form.

Comment 12

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

Attachment: new nsFloatManager.h

Comment 13

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

Attachment: new nsFloatManager.cpp

Comment 14

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

Comment on attachment 354839 [details] [diff] [review]
patch 2: remove TestSpaceManager

This is why I'm not a big fan of unit tests...

Comment 15

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

Only one substantive comment on the main patch: instead of a linked list of FloatInfos, why not just use an nsTArray<FloatInfo>? I think everything gets simpler and we'd do fewer heap allocations. SavedState would contain an array index instead of a FloatInfo*.

+  // The number of floats on the sides of mAvailSpaceRect, including
+  // floats that do not reduce mAvailSpaceRect because they are in the
+  // margins.
+  PRBool mBandHasFloats;

PRPackedBool, and move it next to something narrow if you can.

+  void GetBandInfo(nscoord aY, nscoord aMaxHeight, nscoord aContentAreaWidth,
+                   nsRect& aAvailSpace, PRBool* aHasFloats) const;

Wouldn't it be better to just call this GetBand and return aAvailSpace as a direct result?

+   * aMarginRect is relative to the current translation.  The caller
+   * must ensure aMarginRect.height >= 0.

Is aMarginRect.width < 0 allowed here? I think not. I would have assumed negative widths/heights are generally invalid without having to mention it explicitly, so mentioning the height requirement makes it sound like negative widths would be allowed...

+  struct SavedState;
+  friend struct SavedState;
   struct SavedState {

Can't you just move the friend declaration down below the definition of the struct?

+void
+nsFloatManager::GetBandInfo(nscoord       aYOffset,
+                            nscoord       aMaxHeight,
+                            nscoord       aContentAreaWidth,
+                            nsRect&       aAvailSpace,
+                            PRBool*       aHasFloats) const

Overindented parameter names

+      if (floatTop < bottom)
+        bottom = floatTop;

Aren't we supposed to put these statements in {}? Alternatively, I like
  bottom = PR_MIN(bottom, floatTop);

+  // This could be a good bit simpler if we could guarantee that the
+  // floats given were at the end of our list.  (But we can't;
+  // layout/reftests/bugs/421710-1.html crashes.)

I'm not sure what this comment means exactly, since your code (like the old code) does require that
the floats be the last floats on the list (since we stop as soon as our backward traversal finds
a float that's not in the list). I think it would be a bit clear if you wrote

+  // This could be a good bit simpler if we could guarantee that all the
+  // floats given were in our list.  (But we can't;
+  // layout/reftests/bugs/421710-1.html crashes.)

Comment 16

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

(In reply to comment #15)
> I'm not sure what this comment means exactly, since your code (like the old
> code) does require that
> the floats be the last floats on the list (since we stop as soon as our
> backward traversal finds
> a float that's not in the list). I think it would be a bit clear if you wrote

My initial implementation got rid of the hash set and just walked backwards through the FloatInfo until it found one corresponding to the frame it was given as an argument (ignoring all the next siblings), on the assumption that all of the floats in that list would have FloatInfo.  That crashed, so I put back all the nsVoidHashSet code.

Comment 17

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

(In reply to comment #15)
> +  struct SavedState;
> +  friend struct SavedState;
>    struct SavedState {
> 
> Can't you just move the friend declaration down below the definition of the
> struct?

That pattern because it provides uniformity between compilers that follow C++ 1998 strictly and those that follow the errata.  (C++ 1998 said that subclasses don't have any special access to their parent classes; this was incompatible with earlier implementations and changed in errata, but some compilers do it.)

Otherwise there's no reason for the pattern at all, but I think we may still support some compilers that follow C++ 1998 strictly.

Comment 18

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

Attachment: patch 4: replace nsSpaceManager and nsBlockBandData with nsFloatManager

I think this should address roc's comments; it also tweaks the bounds checking for bottom in nsFloatManager::GetBand.

Comment 19

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

Attachment: new nsFloatManager.h

Comment 20

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

Attachment: new nsFloatManager.cpp

Comment 21

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

I landed patches 1 and 2:
http://hg.mozilla.org/mozilla-central/rev/4a30801c7e45
http://hg.mozilla.org/mozilla-central/rev/454a4f1c98a5

Comment 22

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

Comment on attachment 355237 [details] [diff] [review]
patch 4: replace nsSpaceManager and nsBlockBandData with nsFloatManager

+  mFloats.RemoveElementsAt(newLength, mFloats.Length() - newLength);

  mFloats.SetLength(newLength);

+  mFloats.RemoveElementsAt(aState->mFloatInfoCount,
+                           mFloats.Length() - aState->mFloatInfoCount);

  mFloats.SetLength(aState->mFloatInfoCount);

My question about "friend" was not objecting to the use of "friend", I was just observing that
  struct A;
  friend struct A;
  struct A { ... };
is, AFAIK, equivalent to
  struct A { ... };
  friend struct A;

Comment 23

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

(In reply to comment #22)
> (From update of attachment 355237 [details] [diff] [review])
> +  mFloats.RemoveElementsAt(newLength, mFloats.Length() - newLength);
> 
>   mFloats.SetLength(newLength);
> 
> +  mFloats.RemoveElementsAt(aState->mFloatInfoCount,
> +                           mFloats.Length() - aState->mFloatInfoCount);
> 
>   mFloats.SetLength(aState->mFloatInfoCount);

I tried that first, but that requires that FloatInfo have a default constructor, since SetLength can make things longer or shorter.  If nsTArray had a variant of SetLength that only went shorter, I could use it.

> My question about "friend" was not objecting to the use of "friend", I was just
> observing that
>   struct A;
>   friend struct A;
>   struct A { ... };
> is, AFAIK, equivalent to
>   struct A { ... };
>   friend struct A;

Not for things inside the braces, which are a major part of what it matters for.

Comment 24

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

landed patches 3 and 4:
http://hg.mozilla.org/mozilla-central/rev/b19f0a7a3c4c
http://hg.mozilla.org/mozilla-central/rev/496e0cb5c943

(I also merged one spelling fix in nsBlockFrame.cpp that I had underneath into patch 3.)

Comment 25

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

Also landed:
http://hg.mozilla.org/mozilla-central/rev/aa32889429db
to avoid confusing refcount logging.

Comment 26

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

Attachment: patch 6: add nsTArray<E>::TruncateLength

This adds a new method to nsTArray to provide a cleaner API for solving the problem in comment 23.

Benjamin, what do you think of this?

Comment 27

[Benjamin Smedberg]

Comment on attachment 355344 [details] [diff] [review]
patch 6: add nsTArray<E>::TruncateLength

>+    void TruncateLength(size_type newLen) {
>+      size_type oldLen = Length();
>+      NS_ASSERTION(newLen <= oldLen, "caller should use SetLength instead");

Use NS_ABORT_IF_FALSE here...

Comment 28

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

Also, for what it's worth, if we decide we want to keep the space manager around between reflows (rather than recover state into it every time), we might want to convert back to a linked list (for cheaper insertion/removal in the middle).  (I suppose I should have remembered that when you suggested switching to an array...)  (If we kept it around, it would have a cursor into the list, and the things that currently work with the end of the list would instead work from the cursor.)

Comment 29

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

(In reply to comment #24)
> landed patches 3 and 4:
> http://hg.mozilla.org/mozilla-central/rev/b19f0a7a3c4c
> http://hg.mozilla.org/mozilla-central/rev/496e0cb5c943

For what it's worth, this led to:

Linux Firefox: Zdiff:-5504 (+2924/-8428)
Mac Firefox: Zdiff:-8208 (+4116/-12324) (had some other changes in it too)

Comment 30

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

(In reply to comment #28)
> Also, for what it's worth, if we decide we want to keep the space manager
> around between reflows (rather than recover state into it every time), we might
> want to convert back to a linked list (for cheaper insertion/removal in the
> middle).

Yeah, although it would be a doubly-linked list.

Comment 31

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

Landed TruncateLength:
http://hg.mozilla.org/mozilla-central/rev/63fc1585fe00

Comment 32

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

Fixed on 1.9.1 in order to fix some of the other bugs this happens to fix (esp. bug 467493, which is blocking):

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/31cbae892de7
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/4bb8dbbc3832
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/217208c67bd5
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/33091764b7ba
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/f75293f0c230
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/fde2979a4912

Comment 33

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

Note that in order to land it I also landed:
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/808c7fd368a9
before the patches above and:
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/796feafea6b8
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/3d50c726626b
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/110384dabb87
after them.

Comment 34

[Henrik Skupin [:whimboo][⌚️UTC+2]]

David, a couple of reftests have been checked in. Do you plan more tests or are those tests enough and we can set in-testsuite+?

Comment 35

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

Reftests for what?  This patch wasn't intended to change behavior; I think the tests that are checked in are tests for things that I noticed or broke along the way.  We have a bunch of existing tests to test the behavior that this code was changing, and I'm sure we could use more, though, but I don't think there's anything in particular associated with this bug that ought to be in a test suite.

Comment 36

[Henrik Skupin [:whimboo][⌚️UTC+2]]

Based on comment 35 and that all reftests don't show any problems we could mark this bug as verified.

Comment 37

[Daniel Holbert [:dholbert]]

Attachment: patch bundle: backport changesets from c32-33 & bug 432891,409331,458969 to 1.9.0.x

Here's a mercurial patch-bundle backporting this bug's patches to the 1.9.0.x branch.  I've listed all the included patches below, with their changeset IDs from the 1.9.1 branch.

The first three patches I applied were pre-requisites for later patches to apply. (They're pretty straightforward, I think -- two of them just remove dead code, and the other replaces explicit QI's with a utility method to do the same.)

> dd28fa11cb15  Bug 432891: Remove unneeded border-box and padding-box values of -moz-float-edge.
> 140ebc8ba146  Bug 409331: Instead of QIing to nsBlockFrame in various places, call an nsLayoutUtils method to do it.
> 3a4f96251014  Bug 458969: dead stuff in nsSpaceManager.


Then, I applied these changesets listed in comment 32 and comment 33:

> 808c7fd368a9  Add some reftests for float behavior.
> 31cbae892de7  Bug 191448: Remove the VerifyReflow code that checked the space manager state.
> 4bb8dbbc3832  Bug 191448: Remove TestSpaceManager.
> 217208c67bd5  Bug 191448: Rename flags and methods from space manager to float manager.
> 33091764b7ba  Bug 191448: Replace space manager with a more limited float manager.
> f75293f0c230  Bug 191448: Give nsFloatManager::FloatInfo a copy constructor to avoid confusing refcount logging.
> fde2979a4912  Bug 191448: Add nsTArray<E>::TruncateLength, which is like SetLength, except only allows shortening of the array.
> 796feafea6b8  Bug 472252: Fix tests to match what they should have been testing, and fix nsFloatManager behavior [...]
> 3d50c726626b  Bug 472218: Change code for handling out-of-nscoord-range values from NS_NOTREACHED to NS_WARNING.
> 110384dabb87  Bug 476372: Keep width of avail space rect at least 0.

(Note that the final 3 changesets mentioned above are the fixes for the three regressions from this bug -- bug 472252, Bug 472218, Bug 476372)

I had to fix some bitrot to backport some of those changesets, but it was all minor stuff in contextual code (rather than in the patched lines).

Comment 38

[Daniel Holbert [:dholbert]]

Attachment: combined patch for 1.9.0.x (from above patch bundle)

For convenience, here's a combined patch for the 1.9.0.x branch, taken from the above patch-bundle.  (If we end up landing this on the 1.9.0.x branch, though, we should still land the patches from the patch-bundle as separate patches.)

This is a non-git-style diff, because the 'patch' tool doesn't understand these git-style patch commands (which would be included in the git-style version of this patch):
 rename from layout/generic/nsSpaceManager.cpp
 rename to layout/generic/nsFloatManager.cpp
 rename from layout/generic/nsSpaceManager.h
 rename to layout/generic/nsFloatManager.h

Comment 39

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

So backporting this seems a little scary to me given the amount of Web page testing we get for branch releases.  (I'm also not sure we should be removing support for values of -moz-float-edge on a stable branch.)

I'm not sure I'd have time to write other fixes for whichever bugs led this to be blocking+ for this security release in the next week, though.  (Which bugs are those, exactly?  I remember a conversation about backporting this bug in a bug that I couldn't find in this bug's dependency list.)  Why did this bug end up as a blocker for this particular security release rather than, say, the previous one or the next one?

Comment 41

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

I'm not comfortable with backporting this just to fix a random security bug that, as far as we know, no-one else knows about. (In general I think we should fix fewer of those bugs in stable branches.)

Comment 43

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

Even with the followups, this did change behavior by fixing bug 75286 (though it wasn't intended to).

Comment 44

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

...also bug 81710.

Comment 45

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

Er, in the previous comment I meant bug 219385, not bug 81710.