Bug 116033 – Column balancing support in the region based multicol implementation

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

[Morten Stenshorne]

The region based multicol implementation [1] doesn't support column balancing (nothing is rendered, typically).

[1] The one that kicks in when Document::regionBasedColumnsEnabled() returns true.

[Morten Stenshorne]

Created attachment 201566 [details]
Test case

[Morten Stenshorne]

Created attachment 201567 [details]
Patch

[Build Bot]

Comment on attachment 201567 [details]
Patch

Attachment 201567 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/460729

[Morten Stenshorne]

Created attachment 201626 [details]
Patch

[Morten Stenshorne]

New patch: Attempt to fix compilation problems on Mac.

[Build Bot]

Comment on attachment 201626 [details]
Patch

Attachment 201626 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/460892

New failing tests:
fast/multicol/newmulticol/balance6.html

[Build Bot]

Created attachment 201662 [details]
Archive of layout-test-results from webkit-ews-09 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-09  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.2

[Build Bot]

Comment on attachment 201626 [details]
Patch

Attachment 201626 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/451976

New failing tests:
fast/multicol/newmulticol/balance6.html

[Build Bot]

Created attachment 201664 [details]
Archive of layout-test-results from webkit-ews-06 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-06  Port: mac-mountainlion  Platform: Mac OS X 10.8.2

[Morten Stenshorne]

Created attachment 201694 [details]
Patch

[Morten Stenshorne]

New patch: attempting to make a test pass on Mac

[Build Bot]

Comment on attachment 201694 [details]
Patch

Attachment 201694 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/468496

New failing tests:
media/video-zoom.html
svg/batik/paints/patternPreserveAspectRatioA.svg
fast/multicol/newmulticol/balance6.html

[Build Bot]

Created attachment 201724 [details]
Archive of layout-test-results from webkit-ews-06 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-06  Port: mac-mountainlion  Platform: Mac OS X 10.8.2

[Build Bot]

Comment on attachment 201694 [details]
Patch

Attachment 201694 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/466632

New failing tests:
fast/multicol/newmulticol/balance6.html

[Build Bot]

Created attachment 201730 [details]
Archive of layout-test-results from webkit-ews-09 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-09  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.2

[Morten Stenshorne]

Created attachment 201734 [details]
Patch

[Morten Stenshorne]

New patch:

Ceil differently to see if it helps on Mac.
    
Also updated the ..expected.txt file this time.

[Build Bot]

Comment on attachment 201734 [details]
Patch

Attachment 201734 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/475306

New failing tests:
fast/multicol/newmulticol/balance6.html

[Build Bot]

Created attachment 201772 [details]
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-05  Port: mac-mountainlion  Platform: Mac OS X 10.8.2

[Build Bot]

Comment on attachment 201734 [details]
Patch

Attachment 201734 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/479279

New failing tests:
fast/multicol/newmulticol/balance6.html

[Build Bot]

Created attachment 201785 [details]
Archive of layout-test-results from webkit-ews-14 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-14  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.2

[Morten Stenshorne]

Created attachment 201804 [details]
Patch

[Morten Stenshorne]

New patch:

Use floating point division to make it work in configurations without subpixel layout.

[Dave Hyatt]

Comment on attachment 201804 [details]
Patch

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

This patch is awesome!

One comment on tests. You can in fact make reftests that compare the old columns with the new columns. You can see examples of that in the newmulticol subdirectory of fast/multicol. I understand your balancing algorithm may be different, though, and it may lead to slightly different results, but maybe you could take a look at a few balancing tests and see if you happen to match.

> Source/WebCore/rendering/RenderBlock.cpp:7525
> +    if (!style()->hasAutoOrphans() || !style()->hasAutoWidows()) {
> +        // We require a certain minimum number of lines per page in order to satisfy orphans and
> +        // widows, so we may need to report a larger minimum page height because of that.
> +        int lineCount = max<int>(style()->hasAutoOrphans() ? 1 : style()->orphans(), style()->hasAutoWidows() ? 1 : style()->widows());
> +        RootInlineBox* line = lineBox;
> +        for (int i = lineCount - 1; i > 0 && line->prevRootBox(); i--)
> +            line = line->prevRootBox();
> +        LayoutRect overflow = line->logicalVisualOverflowRect(line->lineTop(), line->lineBottom());
> +        minPageHeight = logicalBottom - min(line->lineTopWithLeading(), overflow.y());
> +    }

Let's push this into a little helper function (even just a static would be nice).

> Source/WebCore/rendering/RenderFlowThread.h:105
> +    virtual void setPageBreak(LayoutUnit /*offset*/, LayoutUnit /*spaceShortage*/) { }
> +
> +    virtual void updateMinimumPageHeight(LayoutUnit /*offset*/, LayoutUnit /*minHeight*/) { }

Add the OVERRIDE keyword to these functions please. I don't think you need a blank line between them either.

> Source/WebCore/rendering/RenderMultiColumnBlock.cpp:44
>      , m_requiresBalancing(false)

BTW I added this variable on the assumption you might use it to set if a column set needs balancing. If it turns out you don't need it, you could just take it out.

> Source/WebCore/rendering/RenderMultiColumnSet.cpp:73
> +    unsigned columnIndex = columnIndexAtOffset(offset, true);

We dislike raw booleans, since what they mean is not discernible from the call site. Please change this to use an enum instead of a boolean.

> Source/WebCore/rendering/RenderMultiColumnSet.cpp:244
> +unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset, bool buildingColumns) const

Use an enum instead of a boolean.

> Source/WebCore/rendering/RenderMultiColumnSet.h:85
> +    // Calculate the column height when contents is supposed to be balanced. If 'initial' is set,

Should be "when the contents are supposed to be balanced."

> Source/WebCore/rendering/RenderMultiColumnSet.h:143
>      bool m_requiresBalancing; // Whether or not the columns in the column set have to be balanced, i.e., made to be similar logical heights.

May as well ditch the member too, right? If you're not going to need it, dump it.

[Morten Stenshorne]

Comment on attachment 201804 [details]
Patch

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

>> Source/WebCore/rendering/RenderFlowThread.h:105
>> +    virtual void updateMinimumPageHeight(LayoutUnit /*offset*/, LayoutUnit /*minHeight*/) { }
> 
> Add the OVERRIDE keyword to these functions please. I don't think you need a blank line between them either.

But these don't override virtual methods, so I shouldn't use OVERRIDE then, should I?

[Morten Stenshorne]

Created attachment 202431 [details]
Patch

[Morten Stenshorne]

The patch I just uploaded should address all issues raised, except the one mentioned in comment #25.

Changes:

Add some reftests that compare against the old multicol implementation.

Report page breaks when blocks cross fragmentainer boundaries. If no lines cross the boundaries, we need to report where blocks cross instead, so that the column balancer knows how much to stretch columns if necessary. Test: balance-images.html

Need to reset space shortage before every layout pass.

Address issue raised by hyatt: Correct English grammar.

Address issue raised by hyatt: Use dedicated enum rather than bool.

Address issues raised by hyatt: remove m_requiresBalancing members.

Address issue raised by hyatt: remove blank line between method declarations.

Address issue raised by hyatt: make static helper function for orphans and widows stuff.

[Dave Hyatt]

Comment on attachment 202431 [details]
Patch

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

Looks really good! A few more suggestions.

> Source/WebCore/rendering/RenderBlock.cpp:7480
> +void RenderBlock::setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage)
> +{
> +    if (RenderFlowThread* flowThread = flowThreadContainingBlock())
> +        flowThread->setPageBreak(offsetFromLogicalTopOfFirstPage() + offset, spaceShortage);
> +}

Since this isn't about flow threads and is really just about multicolumn, I would make setPageBreak virtual and empty in RenderBlock and make a setPageBreak override in RenderMultiColumnBlock do this work.

> Source/WebCore/rendering/RenderBlock.cpp:7488
> +void RenderBlock::updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight)
> +{
> +    if (RenderFlowThread* flowThread = flowThreadContainingBlock())
> +        flowThread->updateMinimumPageHeight(offsetFromLogicalTopOfFirstPage() + offset, minHeight);
> +    else if (ColumnInfo* colInfo = view()->layoutState()->m_columnInfo)
> +        colInfo->updateMinimumColumnHeight(minHeight);
> +}

If you made this virtual (like I mentioned with setPageBreak above), then the base class could do the columnInfo version, and the override in RenderMultiColumnBlock could handle the flow thread case.

> Source/WebCore/rendering/RenderBlock.cpp:7494
> +    int lineCount = max<int>(renderStyle->hasAutoOrphans() ? 1 : renderStyle->orphans(), renderStyle->hasAutoWidows() ? 1 : renderStyle->widows());

Should be unsigned right?

> Source/WebCore/rendering/RenderBlock.cpp:7497
> +        for (int i = lineCount - 1; i > 0 && line->prevRootBox(); i--)

Unsigned.

> Source/WebCore/rendering/RenderBlock.cpp:7501
> +        LayoutRect overflow = line->logicalVisualOverflowRect(line->lineTop(), line->lineBottom());
> +        lineTop = min(line->lineTopWithLeading(), overflow.y());

You should probably put a FIXME here (similar to the FIXME in the calling function) about how we don't like that we're paginating using overflow.

> Source/WebCore/rendering/RenderBlock.cpp:7606
> +            // The child crosses a fragmentainer boundary. Something inside it may have reported a break

Just my own opinion, but I hate the term fragmentainer, even in a comment. It sounds like this is about column balancing, so you could just say "column boundary." :)

> Source/WebCore/rendering/RenderBlock.h:1114
> +    // A page break is required at some offset due to space shortage in the current fragmentainer.
> +    void setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage);
> +
> +    // Update minimum page height required to avoid fragmentation where it shouldn't occur (inside
> +    // unbreakable content, between orphans and widows, etc.). This will be used as a hint to the
> +    // column balancer to help set a good minimum column height.
> +    void updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight);

As suggested above, it seems like these could be virtual.

> Source/WebCore/rendering/RenderFlowThread.h:104
> +    virtual void setPageBreak(LayoutUnit /*offset*/, LayoutUnit /*spaceShortage*/) { }
> +    virtual void updateMinimumPageHeight(LayoutUnit /*offset*/, LayoutUnit /*minHeight*/) { }

And now these can be removed, since the RenderMultiColumnBlock can talk directly to a RenderMultiColunFlowThread.

> Source/WebCore/rendering/RenderMultiColumnFlowThread.h:48
> +    virtual void setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage) OVERRIDE;
> +    virtual void updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight) OVERRIDE;

These can be non-virtual.

> Source/WebCore/rendering/RenderMultiColumnSet.h:-92
> -    virtual void updateLogicalHeight() OVERRIDE;
> -    

The fact that you were able to remove this means we could fix:

https://bugs.webkit.org/show_bug.cgi?id=96804

Might want to make sure to comment in that bug once this patch lands

[Morten Stenshorne]

Comment on attachment 202431 [details]
Patch

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

Here's some quick follow-up on some issues you raised that I have issues with. :) Or just comments/questions regarding. If you have time to reply today, I can go ahead and address everything tomorrow morning CET.

>> Source/WebCore/rendering/RenderBlock.cpp:7480
>> +}
> 
> Since this isn't about flow threads and is really just about multicolumn, I would make setPageBreak virtual and empty in RenderBlock and make a setPageBreak override in RenderMultiColumnBlock do this work.

Not sure if I follow. The RenderMultiColumnBlock will typically be higher up in the ancestry.

>> Source/WebCore/rendering/RenderBlock.cpp:7494
>> +    int lineCount = max<int>(renderStyle->hasAutoOrphans() ? 1 : renderStyle->orphans(), renderStyle->hasAutoWidows() ? 1 : renderStyle->widows());
> 
> Should be unsigned right?

I can do that. Then I'll just assume that orphans() and widows() return something non-negative.

>> Source/WebCore/rendering/RenderBlock.cpp:7606
>> +            // The child crosses a fragmentainer boundary. Something inside it may have reported a break
> 
> Just my own opinion, but I hate the term fragmentainer, even in a comment. It sounds like this is about column balancing, so you could just say "column boundary." :)

OK, I'll be more specific. This is really only about columns. BTW, although "fragmentainer" is no dictionary word AFAIK, the fragmentation spec actually uses that term. :)

>> Source/WebCore/rendering/RenderMultiColumnSet.h:-92
>> -    
> 
> The fact that you were able to remove this means we could fix:
> 
> https://bugs.webkit.org/show_bug.cgi?id=96804
> 
> Might want to make sure to comment in that bug once this patch lands

Unfortunately, RenderRegion overrides it too these days. :/

[Morten Stenshorne]

Created attachment 202517 [details]
Patch

[Morten Stenshorne]

New patch - changes:

Address issue raised by hyatt: use unsigned when it makes sense.

Address issue raised by hyatt: Avoid "fragmentainer"

Address issue raised by hyatt: Add FIXME regarding paginating using line overflow.


Regarding setPageBreak() & co: I kind of followed the same pattern as for RenderBlock::pageLogicalHeightForOffset() and others here. It is non-virtual in RenderBlock, and it is re-implemented (still non-virtual) in RenderFlowThread. The difference is of course that setPageBreak() is virtual in RenderFlowThread. In any case, we have RenderFlowThread which inherits from RenderBlock, then we have RenderBlock::foo() and RenderFlowThread::foo() that don't really do the same thing. The former looks for the appropriate ancestor RenderFlowThread and calls foo() on it (or falls back to the old-fashioned way with ColumnInfo etc.), while the RenderFlowThread method actually does some actual work. I find this somewhat confusing, but perhaps it is something we can and should live with until we can get rid of the old pagination code. When the old code is gone, we can just call flowThreadContainingBlock()->pageLogicalHeightForOffset() directly from methods like adjustLinePositionForPagination() and remove RenderBlock::pageLogicalHeightForOffset() & co. Or what do you think?

[Morten Stenshorne]

Created attachment 202984 [details]
Patch

[Morten Stenshorne]

Had to upload a new patch to modify a test slightly:

In Blink/content_shell the new newmulticol/single-line.html test failed here, because the font used happened to have an 'N' glyph with negative bearings, and the old multicol implementation has clipping bugs. Just add some horizontal margins to work around that.

[Morten Stenshorne]

Created attachment 203048 [details]
Patch

[Morten Stenshorne]

Found and fixed a mistake in RenderBlock::adjustBlockChildForPagination():    We're obviously interested in the child's height, not the container's.

[Dave Hyatt]

Comment on attachment 203048 [details]
Patch

r=me!

[Morten Stenshorne]

Can someone commit-queue+ this one for me, please?

[WebKit Commit Bot]

Comment on attachment 203048 [details]
Patch

Clearing flags on attachment: 203048

Committed r151545: <http://trac.webkit.org/changeset/151545>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.