Bug 116033 - Column balancing support in the region based multicol implementation
Summary: Column balancing support in the region based multicol implementation
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Morten Stenshorne
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-05-13 07:33 PDT by Morten Stenshorne
Modified: 2013-06-13 07:12 PDT (History)
9 users (show)

See Also:


Attachments
Test case (352 bytes, text/html)
2013-05-13 07:34 PDT, Morten Stenshorne
no flags Details
Patch (58.12 KB, patch)
2013-05-13 07:59 PDT, Morten Stenshorne
buildbot: commit-queue-
Details | Formatted Diff | Diff
Patch (58.13 KB, patch)
2013-05-13 13:33 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from webkit-ews-09 for mac-mountainlion-wk2 (493.76 KB, application/zip)
2013-05-13 18:38 PDT, Build Bot
no flags Details
Archive of layout-test-results from webkit-ews-06 for mac-mountainlion (495.16 KB, application/zip)
2013-05-13 18:57 PDT, Build Bot
no flags Details
Patch (58.19 KB, patch)
2013-05-14 03:37 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from webkit-ews-06 for mac-mountainlion (788.60 KB, application/zip)
2013-05-14 09:06 PDT, Build Bot
no flags Details
Archive of layout-test-results from webkit-ews-09 for mac-mountainlion-wk2 (564.48 KB, application/zip)
2013-05-14 10:26 PDT, Build Bot
no flags Details
Patch (58.20 KB, patch)
2013-05-14 11:02 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion (684.39 KB, application/zip)
2013-05-14 16:59 PDT, Build Bot
no flags Details
Archive of layout-test-results from webkit-ews-14 for mac-mountainlion-wk2 (586.28 KB, application/zip)
2013-05-14 20:43 PDT, Build Bot
no flags Details
Patch (58.21 KB, patch)
2013-05-15 01:29 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Patch (77.76 KB, patch)
2013-05-21 08:14 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Patch (77.87 KB, patch)
2013-05-22 03:32 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Patch (78.13 KB, patch)
2013-05-27 07:51 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff
Patch (78.16 KB, patch)
2013-05-28 07:00 PDT, Morten Stenshorne
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Morten Stenshorne 2013-05-13 07:33:37 PDT
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.
Comment 1 Morten Stenshorne 2013-05-13 07:34:13 PDT
Created attachment 201566 [details]
Test case
Comment 2 Morten Stenshorne 2013-05-13 07:59:35 PDT
Created attachment 201567 [details]
Patch
Comment 3 Build Bot 2013-05-13 08:38:22 PDT
Comment on attachment 201567 [details]
Patch

Attachment 201567 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/460729
Comment 4 Morten Stenshorne 2013-05-13 13:33:08 PDT
Created attachment 201626 [details]
Patch
Comment 5 Morten Stenshorne 2013-05-13 13:34:25 PDT
New patch: Attempt to fix compilation problems on Mac.
Comment 6 Build Bot 2013-05-13 18:38:49 PDT
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
Comment 7 Build Bot 2013-05-13 18:38:51 PDT
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
Comment 8 Build Bot 2013-05-13 18:57:16 PDT
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
Comment 9 Build Bot 2013-05-13 18:57:18 PDT
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
Comment 10 Morten Stenshorne 2013-05-14 03:37:16 PDT
Created attachment 201694 [details]
Patch
Comment 11 Morten Stenshorne 2013-05-14 03:38:03 PDT
New patch: attempting to make a test pass on Mac
Comment 12 Build Bot 2013-05-14 09:06:28 PDT
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
Comment 13 Build Bot 2013-05-14 09:06:31 PDT
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
Comment 14 Build Bot 2013-05-14 10:26:56 PDT
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
Comment 15 Build Bot 2013-05-14 10:26:59 PDT
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
Comment 16 Morten Stenshorne 2013-05-14 11:02:35 PDT
Created attachment 201734 [details]
Patch
Comment 17 Morten Stenshorne 2013-05-14 11:04:28 PDT
New patch:

Ceil differently to see if it helps on Mac.
    
Also updated the ..expected.txt file this time.
Comment 18 Build Bot 2013-05-14 16:59:39 PDT
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
Comment 19 Build Bot 2013-05-14 16:59:42 PDT
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
Comment 20 Build Bot 2013-05-14 20:43:34 PDT
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
Comment 21 Build Bot 2013-05-14 20:43:37 PDT
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
Comment 22 Morten Stenshorne 2013-05-15 01:29:19 PDT
Created attachment 201804 [details]
Patch
Comment 23 Morten Stenshorne 2013-05-15 01:29:55 PDT
New patch:

Use floating point division to make it work in configurations without subpixel layout.
Comment 24 Dave Hyatt 2013-05-15 11:43:03 PDT
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.
Comment 25 Morten Stenshorne 2013-05-21 08:13:34 PDT
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?
Comment 26 Morten Stenshorne 2013-05-21 08:14:48 PDT
Created attachment 202431 [details]
Patch
Comment 27 Morten Stenshorne 2013-05-21 08:19:53 PDT
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.
Comment 28 Dave Hyatt 2013-05-21 11:24:08 PDT
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
Comment 29 Morten Stenshorne 2013-05-21 11:59:41 PDT
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. :/
Comment 30 Morten Stenshorne 2013-05-22 03:32:30 PDT
Created attachment 202517 [details]
Patch
Comment 31 Morten Stenshorne 2013-05-22 03:54:08 PDT
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?
Comment 32 Morten Stenshorne 2013-05-27 07:51:54 PDT
Created attachment 202984 [details]
Patch
Comment 33 Morten Stenshorne 2013-05-27 07:58:07 PDT
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.
Comment 34 Morten Stenshorne 2013-05-28 07:00:57 PDT
Created attachment 203048 [details]
Patch
Comment 35 Morten Stenshorne 2013-05-28 07:02:02 PDT
Found and fixed a mistake in RenderBlock::adjustBlockChildForPagination():    We're obviously interested in the child's height, not the container's.
Comment 36 Dave Hyatt 2013-06-12 11:42:30 PDT
Comment on attachment 203048 [details]
Patch

r=me!
Comment 37 Morten Stenshorne 2013-06-13 06:44:54 PDT
Can someone commit-queue+ this one for me, please?
Comment 38 WebKit Commit Bot 2013-06-13 07:12:19 PDT
Comment on attachment 203048 [details]
Patch

Clearing flags on attachment: 203048

Committed r151545: <http://trac.webkit.org/changeset/151545>
Comment 39 WebKit Commit Bot 2013-06-13 07:12:25 PDT
All reviewed patches have been landed.  Closing bug.