Bug 38402 – Paginate and column-break at layout time rather than when painting

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

<rdar://problem/7928898>

The current paint-time implementation of pagination and columns is limited by its inability to move objects around or resize them for pagination. Perform pagination and breaking into columns during layout instead of when painting.

A couple of notable limitations in the current paint-time solution:
- when lines’ vertical visual overflow areas overlap (such as with certain text shadow parameters), lines get split in the middle
- objects in layers (positioned elements, media) don’t respect column layout

[Simon Fraser (smfr)]

> - objects in layers (positioned elements, media) don’t respect column layout

This is fixed now.

[Dave Hyatt]

*** Bug 45497 has been marked as a duplicate of this bug. ***

[Dave Hyatt]

Created attachment 67226 [details]
Implement internal pagination of floats

There are two big remaining issues with this patch:

(1) Being willing to insert a "strut" between the top of a block and its first line box creates really ugly visual artifacts, especially if the block has a border or background.  Similar to how margins can collapse out through the top of a block, we need to push pagination info for first lines out through block ancestors, so that all of those blocks move to the next page/column instead.  This is a very complicated problem, but I think solving it is essential to treating drop caps floats as unsplittable (because the line and the rest of the block go together).  As a first pass I may only push through to the immediate enclosing block.

(2) There is no pagination of unsplittable floats yet.  Those need to push down to the next page when they don't fit, and they need to bring the line they are on along with them.

I don't expect (2) to be all that difficult, but (1) is going to be a monster.  Once these problems are solved, though, I'll be in a position to land, since all the multicol tests will be passing.

[Dave Hyatt]

Created attachment 67248 [details]
This patch propagates first line pagination info outwards

Here's what is left:

(1) Make floats honor the pagination strut that gets pushed outwards and move themselves down.
(2) Make floats move down when they are unsplittable also.
(3) Move lines down when a float moves down as a result of (1) or (2), as long as there is no higher float on the line already.  Basically make the line be at the min y-position of all the floats that occur on that line.
(4) There are minor 1px glitches with placement at the top of columns on Roc's blog.
(5) Margins aren't collapsing away like they should in one specific entry on Roc's blog (something to do with lists).
(6) Columns still end up a bit too tall. The balancing algorithm needs some more smarts.

[Dave Hyatt]

(7) Table cell vertical alignment can throw off pagination.  I have to figure something out there.

[Dave Hyatt]

Created attachment 67289 [details]
This patch moves floats to the next page correctly.

This patch gets floats moved.  Now to handle moving lines as a result of a float moving.

[Dave Hyatt]

(8) Dirty tables properly as part of markDescendantBlocksAndLines.
(9) Make lines account for varying line widths when they paginate (need more dirtying and relayout instead of just moving).
(10) Make block children call markDescendantBlocksAndLines if their y positions change (tricky, don't O(n^2) it somehow, might need new kind of layout flag).

[Dave Hyatt]

Created attachment 67332 [details]
Improve line layout pagination

This patch improves line layout pagination.  It makes sure that the start/end position lines that are clean re-paginate by removing their pagination spacing.  It allow markDescendantBlocksAndLines to not have to trigger a full line layout, which helps performance a bit.

[Dave Hyatt]

More notes:

Don't use markDescendantBlocksAndLines except when page height changes.  Instead cache the page offset for all RenderBlocks (rename MaxMargin struct to RenderBlockRareData and put it in there).  If that changes then just do setChildNeedsLayout).

When a line doesn't fit vertically, need to check available line width.  If it's different have to rewind line layout by 1 line and re-run it.  Make sure floats encountered a second time don't mess up (they should already be inserted/positioned).

Need to fix the yPosEstimate issue with <body><p>.  It's just going to be too painful if the entire document lays out at the wrong vertical position and then has to relayout again.  We need to just get that right on the first layout.

[Dave Hyatt]

Created attachment 67448 [details]
Improve dirtying when objects in a pagination context move

This change cuts down on relayout when paginated objects move.  It doesn't try to relayout if your overall absolute position relative to the first page top doesn't change.

Here are the big remaining issues that block review:

(1) Floats need to bring lines along with them when they move to the next page.  The exact circumstances under which they should do this are debatable.  I'm still trying to decide when this should happen.
(2) When a line paginates, I have to re-run line layout on that line if the line width at the new position is different.
(3) Tables and flexible boxes are still unpatched.  They need to setPageY on themselves in their layout methods.  They both need to handle dirtying their children if their pageYs are different.
(4) Tables need to do something about movement of cells, e.g., when a row grows to take over remaining space, shoving other rows down.  Vertical alignment is also problematic, since the cell contents shift in that case too.
(5) Column breaks need to just be disabled for non-normal-flow content for now.
(6) The column balancing algorithm needs to be smart about tracking page breaks and not trying to grow column heights if forced page breaks have already given you too many columns. It also needs to balance around the size of the contents between the forced breaks.

[Dave Hyatt]

Created attachment 67583 [details]
This patch makes floats move lines they are anchored to when needed.

[Dave Hyatt]

No new issues, so down to (2)-(6) on the last posted list.

[Dave Hyatt]

Created attachment 67609 [details]
Make line layout rewind by 1 line when a line paginates.

This patch fixes line layout so that if the line width changes after a line paginates, we rewind line layout the proper amount and re-run it.  We keep floats positioned properly that were above the unpaginated top of the line.

Down to only the following issues now:

(1) Tables and flexible boxes are still unpatched.  They need to setPageY on themselves in their layout methods.  They both need to handle dirtying their children if their pageYs are different.
(2) Tables need to do something about movement of cells, e.g., when a row grows to take over remaining space, shoving other rows down.  Vertical alignment is also problematic, since the cell contents shift in that case too.
(3) Column breaks need to just be disabled for non-normal-flow content for now.
(4) The column balancing algorithm needs to be smart about tracking page breaks and not trying to grow column heights if forced page breaks have already given you too many columns. It also needs to balance around the size of the contents between the forced breaks.

[Dave Hyatt]

Created attachment 67612 [details]
Make table vertical alignment and growth do something vaguely sensible

Down to just fixing up dirtying and setPageY stuff and then fixing column breaks.

[Dave Hyatt]

Created attachment 67613 [details]
Incorporate the layout tests I've written so far into the patch.

[Dave Hyatt]

Created attachment 67691 [details]
Fix pageY dirtying / checking for positioned objects and tables and flexible boxes

Down now to:

(1) Column breaks need to just be disabled for non-normal-flow content for now.
(2) The column balancing algorithm needs to be smart about tracking page breaks and not trying to grow column heights if forced page breaks have already given you too many columns. It also needs to balance around the size of the contents between the forced breaks.
(3) Improve the yPosEstimate check to handle <!doctype html><body><p> without having to relayout the world.

[Dave Hyatt]

Created attachment 67713 [details]
Patch (excluding layout test results, which are too big to attach)

[WebKit Review Bot]

Attachment 67713 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style']" exit_code: 1
WebCore/rendering/LayoutState.h:77:  One space before end of line comments  [whitespace/comments] [5]
WebCore/rendering/LayoutState.h:78:  One space before end of line comments  [whitespace/comments] [5]
WebCore/rendering/LayoutState.h:83:  One space before end of line comments  [whitespace/comments] [5]
WebCore/rendering/LayoutState.h:84:  One space before end of line comments  [whitespace/comments] [5]
WebCore/rendering/LayoutState.h:85:  One space before end of line comments  [whitespace/comments] [5]
WebCore/rendering/RenderBlock.cpp:3895:  One line control clauses should not use braces.  [whitespace/braces] [4]
WebCore/rendering/RenderBlock.cpp:5601:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/RenderBlock.cpp:5611:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
WebCore/rendering/ColumnInfo.h:32:  Use 'using namespace std;' instead of 'using std::max;'.  [build/using_std] [4]
WebCore/rendering/ColumnInfo.h:83:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Total errors found: 10 in 36 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Dave Hyatt]

Created attachment 67819 [details]
New patch

Improved estimateVerticalPosition to account for a block's paginationStrut (similar logic to how collapsedMarginTop is used inside that function).

Fixed the style errors with the previous patch.

[Darin Adler]

Comment on attachment 67819 [details]
New patch

View in context: https://bugs.webkit.org/attachment.cgi?id=67819&action=prettypatch

I reviewed a lot but I’m still not sure I read enough of the actual algorithms. I am going to say review+ but you probably want at least a bit of review from people who will read more of the layout algorithms.

> WebCore/rendering/ColumnInfo.h:60
> +    void setColumnCountAndHeight(int c, int h)

I would prefer argument names of count and height rather than c and h.

> WebCore/rendering/ColumnInfo.h:97
> +    int m_forcedBreaks; // FIXME: We will ultimately need to cache way more information to balance around forced breaks properly.

I don’t think “way more” is way better than “more” here.

I don’t know what “balance around” means, but maybe experts would know.

> WebCore/rendering/LayoutState.cpp:38
> +LayoutState::LayoutState(LayoutState* prev, RenderBox* renderer, const IntSize& offset, int pageHeight, ColumnInfo* colInfo)
> +    : m_columnInfo(colInfo)

I’d prefer “columnInfo” to “colInfo”.

> WebCore/rendering/LayoutState.cpp:88
> +        m_pageOffset = IntSize(m_layoutOffset.width() + renderer->borderLeft() + renderer->paddingLeft(),
> +                               m_layoutOffset.height() + renderer->borderTop() + renderer->paddingTop());

I know it’s pretty, but we normally don’t line up the second line with the parenthesis like this. Makes it look bad if you ever rename things.

> WebCore/rendering/LayoutState.h:66
> +    bool paginatingColumns() const { return m_columnInfo; }
> +    bool paginated() const { return m_pageHeight || m_columnInfo; }

I think these would be more readable as isPaginatingColumns and isPaginated.

> WebCore/rendering/LayoutState.h:81
> +    IntSize m_layoutDelta; // Transient offset from the final position of the object
> +                           // used to ensure that repaints happen in the correct place.
> +                           // This is a total delta accumulated from the root.

Same comment about indented lines. It’s better not to do this, so things stay good even if we rename later. I know the existing code already did it.

> WebCore/rendering/RenderBlock.cpp:1141
> +    ColumnInfo* colInfo = columnInfo();

I’d prefer columnInfo to colInfo.

> WebCore/rendering/RenderBlock.cpp:2916
> +    // Our location is irrelevant if we're unsplittable or no pagination is in effect.  Just go ahead
> +    // and lay out the float.

Would read better if you broke lines where you broke sentences.

> WebCore/rendering/RenderBlock.cpp:2956
> +void RenderBlock::removeFloatingObjects(FloatingObject* f, int y)

Instead of “f” it would be good to name this in some way that made clear what the argument is.

I think this function is confusing. It’s “remove floatingObjects after this one that are below this y coordinate”? Is there some better way to explain that in the function name?

> WebCore/rendering/RenderBlock.cpp:4442
> +                    int distanceBetweenBreaks = max(colInfo->maximumDistanceBetweenForcedBreaks(),
> +                                                    view()->layoutState()->pageY(borderTop() + paddingTop() + contentHeight()) - colInfo->forcedBreakOffset());

Better not to try to line up lines like these as I said before.

> WebCore/rendering/RenderBlock.h:606
> +    RenderBlockRareData* m_rareData;

Can we use an OwnPtr for rare data? If it’s really rare, can we use a hash map and a bit for it instead of a pointer?

> WebCore/rendering/RenderTable.h:145
> -
> +    

You should just revert the whitespace-only change to RenderTable.h.

[Dave Hyatt]

(In reply to comment #21)
>
> Can we use an OwnPtr for rare data? If it’s really rare, can we use a hash map and a bit for it instead of a pointer?
> 

It's not that rare.  We'd probably need to investigate to see how often it gets allocated, but it's more common than say having a continuation (which I'd target first for the hashing).

[Dave Hyatt]

(In reply to comment #21)

> I think this function is confusing. It’s “remove floatingObjects after this one that are below this y coordinate”? Is there some better way to explain that in the function name?
> 

I agree.  I struggled with some really really long names before just giving up.  I'm open to suggestions...

[Dave Hyatt]

Fixed in r67660.

[WebKit Review Bot]

http://trac.webkit.org/changeset/67660 might have broken Qt Linux Release
The following changes are on the blame list:
http://trac.webkit.org/changeset/67659
http://trac.webkit.org/changeset/67660

[Adam Barth]

28 hours later, these still seem to be broken:

fast/multicol/span/span-as-immediate-child-generated-content.html
fast/multicol/span/span-as-immediate-child-property-removal.html
fast/multicol/span/span-as-immediate-columns-child-dynamic.html
fast/multicol/span/span-as-immediate-columns-child-removal.html
fast/multicol/span/span-as-immediate-columns-child.html

Am I misreading the bots?

[Adam Barth]

Hopefully resolved in http://trac.webkit.org/changeset/67766.

Dave, can you make sure the above change is correct?  Thanks.

[Csaba Osztrogonác]

(In reply to comment #25)
> http://trac.webkit.org/changeset/67660 might have broken Qt Linux Release
> The following changes are on the blame list:
> http://trac.webkit.org/changeset/67659
> http://trac.webkit.org/changeset/67660

Qt specific expected results fix landed in http://trac.webkit.org/changeset/67842

[Jeremy Orlow]

As documented in https://bugs.webkit.org/show_bug.cgi?id=45957 it appears this change actually did break things and there's no sign of imminent fixes.  I'm preparing a revert right now for the following CLs:

http://trac.webkit.org/changeset/67660
http://trac.webkit.org/changeset/67766
http://trac.webkit.org/changeset/67842

[Simon Fraser (smfr)]

Hyatt did a huge amount of work to land this patch. Can we just hope he'll fix things up?

[Jeremy Orlow]

(In reply to comment #30)
> Hyatt did a huge amount of work to land this patch. Can we just hope he'll fix things up?

We filed this 5 days ago https://bugs.webkit.org/show_bug.cgi?id=45957 and haven't gotten any response.  Normally, I would have advocated simply reverting at that first sign of trouble, but since there had obviously been a lot of work put into landing it, we filed the bug in the hopes we could avoid that.  (In hindsight, maybe we should have posted something more obvious in this bug before now.  Sorry about that.)

But unless you have some inside information that David will probably have a chance to look at this soon, I feel like reverting is the only course of action here.  (I did take a look at the patch trying to find some easy-to-spot defect causing the issue, but I didn't see anything--though I am completely unfamiliar with this code.)

[Jeremy Orlow]

(In reply to comment #31)
> (In reply to comment #30)
> > Hyatt did a huge amount of work to land this patch. Can we just hope he'll fix things up?
> 
> We filed this 5 days ago https://bugs.webkit.org/show_bug.cgi?id=45957 and haven't gotten any response.  Normally, I would have advocated simply reverting at that first sign of trouble, but since there had obviously been a lot of work put into landing it, we filed the bug in the hopes we could avoid that.  (In hindsight, maybe we should have posted something more obvious in this bug before now.  Sorry about that.)
> 
> But unless you have some inside information that David will probably have a chance to look at this soon, I feel like reverting is the only course of action here.  (I did take a look at the patch trying to find some easy-to-spot defect causing the issue, but I didn't see anything--though I am completely unfamiliar with this code.)

Unfortunately it looks like a simple revert may not be possible.  Simon, do you have a few cycles to look at this column thing?  If not, any idea who could?  (In the future, I guess we shouldn't wait on the revert. :-(