Bug 103327 – [CSS Exclusions] Add support for computing the first included interval position.

• Component: CSS
• Status: RESOLVED FIXED

[Hans Muller]

The first step towards completing the patch for https://bugs.webkit.org/show_bug.cgi?id=96813 is to add a ExclusionShape method for finding the first included interval position, create stub implementations, and then use it in RenderBlockLineLayout::layoutRunsAndFloatsInRange().

[Hans Muller]

Created attachment 176122 [details]
Patch

Added ExclusionShape::firstIncludedIntervalPosition(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, FloatPoint& result)

The new virtual method computes the topmost/leftmost location where an line segment with the specified minLogicalIntervalSize will fit within the exclusion shape.  The result is additionally constrained to be at or below minLogicalIntervalTop.  If the segment will not fit anywhere within the shape, then false is returned.

During layout, minLogicalIntervalTop is the nominal top of the line being laid out within the exclusion shape. 

Currently the implementations of firstIncludedIntervalPosition() are stubs which behave in the same way as the current excluions implementation.  If a segment of minLogicalIntervalSize will fit within the shape's logical bounding box, then the returned point's Y coordinate is just minLogicalIntervalTop.

This patch also includes one minor cleanup: the protected ExclusionShape inlines, like minYForLogicalLine(), now use isFlippedBlocksWritingMode() instead of testing for RightToLeftWritingMode directly.  This changeimproves consistency with the rest of WebKit and will work correctly if "horizontal-bt" writing-mode support is ever added.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/rendering/ExclusionPolygon...." exit_code: 1
Source/WebCore/rendering/ExclusionShapeInsideInfo.h:60:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Source/WebCore/rendering/RenderBlockLineLayout.cpp:1453:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 2 in 8 files


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

[Hans Muller]

Created attachment 176125 [details]
Patch

Fixed a whitespace-o.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/rendering/ExclusionPolygon...." exit_code: 1
Source/WebCore/rendering/RenderBlockLineLayout.cpp:1453:  One line control clauses should not use braces.  [whitespace/braces] [4]
Total errors found: 1 in 8 files


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

[Hans Muller]

Created attachment 176126 [details]
Patch

Removed extraneous braces.

[Bem Jones-Bey]

Comment on attachment 176126 [details]
Patch

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

> Source/WebCore/rendering/ExclusionPolygon.cpp:381
> +    // FIXME: This is just a stub, it will be replaced: TBD BUGID.

The BugID is still missing.

> Source/WebCore/rendering/ExclusionRectangle.cpp:118
> +bool ExclusionRectangle::firstIncludedIntervalPosition(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, FloatPoint& result) const

The logic in this method is identical to that in ExclusionPolygon::firstIncludedIntervalPosition. Since it's already virtual, can we move it to ExclusionShape and have it call methods to get x, y, and maxY?

> Source/WebCore/rendering/ExclusionRectangle.cpp:120
> +    // FIXME: This is just a stub, it will be replaced: TBD BUGID.

The BugID is still missing.

[Hans Muller]

(In reply to comment #6)
> (From update of attachment 176126 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=176126&action=review

> > Source/WebCore/rendering/ExclusionRectangle.cpp:118
> > +bool ExclusionRectangle::firstIncludedIntervalPosition(float minLogicalIntervalTop, const FloatSize& minLogicalIntervalSize, FloatPoint& result) const
> 
> The logic in this method is identical to that in ExclusionPolygon::firstIncludedIntervalPosition. Since it's already virtual, can we move it to ExclusionShape and have it call methods to get x, y, and maxY?

Refactoring a temporary stub and adding ephemeral structure doesn't seem like a good idea to me.

> > Source/WebCore/rendering/ExclusionRectangle.cpp:120
> > +    // FIXME: This is just a stub, it will be replaced: TBD BUGID.
> 
> The BugID is still missing.

I've added the BugIDs:

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

[Hans Muller]

Created attachment 176300 [details]
Patch

Fixed FIXMEs, added a ChangeLog entry.

[Bear Travis]

Comment on attachment 176300 [details]
Patch

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

> Source/WebCore/rendering/ExclusionShape.h:75
> +    float minYForLogicalLine(float logicalTop, float logicalHeight) const { return isFlippedBlocksWritingMode(m_writingMode) ? m_logicalBoxHeight - logicalTop - logicalHeight : logicalTop; }
> +    float maxYForLogicalLine(float logicalTop, float logicalHeight) const { return  isFlippedBlocksWritingMode(m_writingMode) ? m_logicalBoxHeight - logicalTop : logicalTop + logicalHeight; }
> +    FloatRect internalToLogicalBoundingBox(const FloatRect& r) const { return isFlippedBlocksWritingMode(m_writingMode) ? FloatRect(r.x(), m_logicalBoxHeight - r.maxY(), r.width(), r.height()) : r; }

Should these be in a separate patch, as they will require test case cleanup?

> Source/WebCore/rendering/ExclusionShapeInsideInfo.cpp:128
> +        LayoutUnit newLineTop = LayoutUnit::fromFloatCeil(intervalPosition.y());

It seems like we have a general problem of correctly transforming to & from floats. Should we have another bug to factor out some helper methods?

> Source/WebCore/rendering/ExclusionShapeInsideInfo.cpp:131
> +        return true;

I think this can be simplified to return true only when the line changes.

> Source/WebCore/rendering/RenderBlockLineLayout.cpp:1452
> +        if (exclusionShapeInsideInfo && wordMeasurements.size() > 0 && exclusionShapeInsideInfo->adjustSegmentsForLine(wordMeasurements[0].width))
> +            setLogicalHeight(exclusionShapeInsideInfo->lineLogicalTop() - absoluteLogicalTop);

After making this adjustment, you will need to reset & re-run nextLineBreak, as there may be room for additional text. You can see paginated layout doing something similar below this in layoutRunsAndFloatsInRange, so we may want to follow that example (they are slightly different, so it isn't a copy-paste).

[Bear Travis]

A general, high level comment. I think this patch may be hard to review because there isn't anything to test, especially since it is modifying layout code.

I know bug 103427 separately logs fixing first-fit for rounded rectangles, but would it be possible to combine these two, such that fixing the rounded rectangle case adds a simple stub for polygon?

[Bear Travis]

Comment on attachment 176300 [details]
Patch

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

>> Source/WebCore/rendering/ExclusionShape.h:75
>> +    FloatRect internalToLogicalBoundingBox(const FloatRect& r) const { return isFlippedBlocksWritingMode(m_writingMode) ? FloatRect(r.x(), m_logicalBoxHeight - r.maxY(), r.width(), r.height()) : r; }
> 
> Should these be in a separate patch, as they will require test case cleanup?

You can ignore my comment on these lines, I just confused this with a previous modification.

[Hans Muller]

(In reply to comment #10)
> A general, high level comment. I think this patch may be hard to review because there isn't anything to test, especially since it is modifying layout code.
> 
> I know bug 103427 separately logs fixing first-fit for rounded rectangles, but would it be possible to combine these two, such that fixing the rounded rectangle case adds a simple stub for polygon?

Doing so will grow the patch quite a bit, but I agree that it's probably necessary.

[Hans Muller]

(In reply to comment #9)
> (From update of attachment 176300 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=176300&action=review

> > Source/WebCore/rendering/ExclusionShapeInsideInfo.cpp:128
> > +        LayoutUnit newLineTop = LayoutUnit::fromFloatCeil(intervalPosition.y());
> 
> It seems like we have a general problem of correctly transforming to & from floats. Should we have another bug to factor out some helper methods?

I've filed [CSS Exclusions] Add helper functions for converting floats to LayoutUnits - https://bugs.webkit.org/show_bug.cgi?id=103450
> 
> > Source/WebCore/rendering/ExclusionShapeInsideInfo.cpp:131
> > +        return true;
> 
> I think this can be simplified to return true only when the line changes.

Yes.   In fact, since I'm going to restart the 'while (!end.atEnd())' loop in this case, a call to computeSegmentsForLine() will happen anyway, so doing as much in adjustSegmentsForLine() isn't necessary.  Which makes adjustSegmentsForLine() a misnomer.  I've changed the name to adjustLineLogicalTop().

> 
> > Source/WebCore/rendering/RenderBlockLineLayout.cpp:1452
> > +        if (exclusionShapeInsideInfo && wordMeasurements.size() > 0 && exclusionShapeInsideInfo->adjustSegmentsForLine(wordMeasurements[0].width))
> > +            setLogicalHeight(exclusionShapeInsideInfo->lineLogicalTop() - absoluteLogicalTop);
> 
> After making this adjustment, you will need to reset & re-run nextLineBreak, as there may be room for additional text. You can see paginated layout doing something similar below this in layoutRunsAndFloatsInRange, so we may want to follow that example (they are slightly different, so it isn't a copy-paste).

The exclusions contribution to this loop is now:

        if (exclusionShapeInsideInfo && wordMeasurements.size() && exclusionShapeInsideInfo->adjustLogicalLineTop(wordMeasurements[0].width)) {
            removeFloatingObjectsBelow(lastFloatFromPreviousLine, logicalHeight());
            resolver.setPositionIgnoringNestedIsolates(oldEnd);
            end = oldEnd;
            setLogicalHeight(exclusionShapeInsideInfo->lineLogicalTop() - absoluteLogicalTop);
            continue;
        }

[Hans Muller]

Created attachment 176359 [details]
Patch

Made the changes suggested by reviewers.

[Hans Muller]

Created attachment 176650 [details]
Patch

Added support for rounded rectangles.

[Hans Muller]

Created attachment 177804 [details]
Patch

Removed the ExclusionShape.h cleanup that's been addressed by https://bugs.webkit.org/show_bug.cgi?id=103939.  Now this patch is slightly smaller.

[Levi Weintraub]

Comment on attachment 177804 [details]
Patch

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

> LayoutTests/fast/exclusions/shape-inside/shape-inside-rounded-rectangle-fit-002-expected.html:33
> +    top: 29.2893219px;
> +    left: 29.2893219px;
> +    width: 200px;
> +    height: 200px;
> +    font: 141.421356px/1 Ahem, sans-serif;

Can you help me understand where these numbers came from?

> Source/WebCore/rendering/ExclusionPolygon.cpp:381
> +    // FIXME: This is just a temporary stub, https://bugs.webkit.org/show_bug.cgi?id=103429

This makes me a sad panda :(

> Source/WebCore/rendering/ExclusionRectangle.cpp:148
> +        float xi = (m_width - minLogicalIntervalSize.width()) / 2;
> +        float yi = m_ry - ellipseYIntercept(m_rx - xi, m_rx, m_ry);

So sometimes we calculate these twice? This seems a bit inefficient, and at a minimum it seems the code could be shared.

> Source/WebCore/rendering/RenderBlockLineLayout.cpp:1456
> +            removeFloatingObjectsBelow(lastFloatFromPreviousLine, logicalHeight());
> +            resolver.setPositionIgnoringNestedIsolates(oldEnd);
> +            end = oldEnd;
> +            setLogicalHeight(exclusionShapeInsideInfo->logicalLineTop() - absoluteLogicalTop);
> +            continue;

It isn't obvious at all by looking at this what this is doing, and this is code that's duplicated elsewhere in this loop. Please extract it into a descriptive inline function.

[Hans Muller]

Created attachment 177911 [details]
Patch

Made the changes suggested by Levi.

[Hans Muller]

(In reply to comment #17)
> (From update of attachment 177804 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=177804&action=review
> 
> > LayoutTests/fast/exclusions/shape-inside/shape-inside-rounded-rectangle-fit-002-expected.html:33
> > +    top: 29.2893219px;
> > +    left: 29.2893219px;
> > +    width: 200px;
> > +    height: 200px;
> > +    font: 141.421356px/1 Ahem, sans-serif;
> 
> Can you help me understand where these numbers came from?

I've added comments to the tests:

In this test the shape-inside shape is a rounded rectangle configured as a circle with radius of 100px. The shape-inside element contains a single square Ahem font character that just fits wthin the circle. That means that the character's size is sqrt(2)*100px, which is 141.41356px.

The x and y coordinates of the points at which the square intersects the circle are half of the  difference between circle's diameter and the size of the square: (200px - sqrt(2)*100px) / 2 = 29.2893219px.


> 
> > Source/WebCore/rendering/ExclusionPolygon.cpp:381
> > +    // FIXME: This is just a temporary stub, https://bugs.webkit.org/show_bug.cgi?id=103429
> 
> This makes me a sad panda :(

I left this part out to keep the patch small (smaller).  

The polygon first fit algorithm is more complicated and will make a big patch all on its own.  There's more about the polygon algorithm here if you're curious - http://hansmuller-webkit.blogspot.com/2012/08/revised-algorithm-for-finding-first.html.

> 
> > Source/WebCore/rendering/ExclusionRectangle.cpp:148
> > +        float xi = (m_width - minLogicalIntervalSize.width()) / 2;
> > +        float yi = m_ry - ellipseYIntercept(m_rx - xi, m_rx, m_ry);
> 
> So sometimes we calculate these twice? This seems a bit inefficient, and at a minimum it seems the code could be shared.

I moved the common code into a help method and hoisted the call up, so that it only runs once.

This code could probably be tightened further, for example sometimes this intercept computation can be avoided altogether.  If it's OK, I'd like to defer such refinements to another patch.  

> 
> > Source/WebCore/rendering/RenderBlockLineLayout.cpp:1456
> > +            removeFloatingObjectsBelow(lastFloatFromPreviousLine, logicalHeight());
> > +            resolver.setPositionIgnoringNestedIsolates(oldEnd);
> > +            end = oldEnd;
> > +            setLogicalHeight(exclusionShapeInsideInfo->logicalLineTop() - absoluteLogicalTop);
> > +            continue;
> 
> It isn't obvious at all by looking at this what this is doing, and this is code that's duplicated elsewhere in this loop. Please extract it into a descriptive inline function.

I refactored the code as you've suggested and called the new method "restartLayoutRunsAndFloatsInRange" to emphasize its connection to layoutRunsAndFloatsInRange().

[Levi Weintraub]

Comment on attachment 177911 [details]
Patch

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

Okay.

> Source/WebCore/rendering/RenderBlockLineLayout.cpp:1468
> +// Before restarting the layout loop with a new logicalHeight, remove all floats that were added and reset the resolver.
> +inline const InlineIterator& RenderBlock::restartLayoutRunsAndFloatsInRange(LayoutUnit oldLogicalHeight, LayoutUnit newLogicalHeight,  FloatingObject* lastFloatFromPreviousLine, InlineBidiResolver& resolver,  const InlineIterator& oldEnd)

So much better to see this functionality get a descriptive name.

[WebKit Review Bot]

Comment on attachment 177911 [details]
Patch

Clearing flags on attachment: 177911

Committed r136857: <http://trac.webkit.org/changeset/136857>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[János Badics]

A test (fast/exclusions/shape-inside/shape-inside-rounded-rectangle-fit-002.html)
fails on Qt and GTK since it has been introduced in r136857.
You can see details about the fail at
https://bugs.webkit.org/show_bug.cgi?id=104351

I will skip this test on Qt. Please unskip it with the proper fix.

[Hans Muller]

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