Bug 121619 – [CSS Shapes] add shape-margin support for image valued shapes

• Component: CSS
• Status: RESOLVED FIXED

[Hans Muller]

Currently shape-margin is ignored for image valued shapes.

[Hans Muller]

Created attachment 212386 [details]
Patch

Add support for computing the shape-margin boundary for a shape-outside whose value is an image. The current implementation is correct but suboptimal.

[Build Bot]

Comment on attachment 212386 [details]
Patch

Attachment 212386 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/1966485

[Hans Muller]

Created attachment 212398 [details]
Patch

Resync'd to get past the windows EWS build problem - which seems to be unrelated to this patch.

[Build Bot]

Comment on attachment 212398 [details]
Patch

Attachment 212398 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/2096053

[Alexandru Chiculita]

Comment on attachment 212398 [details]
Patch

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

> Source/WebCore/ChangeLog:9
> +        value is an image. The current implementation is correct but suboptimal.

Is there a bug that will improve it? Why not just do the optimal version now :) ?

Is it correct to ignore the empty intervals inside the shape?

> Source/WebCore/rendering/shapes/RasterShape.cpp:56
> +    m_xIntercepts.resize(radius + 1);

I'm not sure if it is worth caching these values. And if you don't need the cache, then you don't really need the Generator class at all.

> Source/WebCore/rendering/shapes/RasterShape.cpp:87
> +    ASSERT(m_intervalLists[y].size() <= 1);

It seems like you are going to need more than one interval. Seems like ShapeInterval::uniteShapeIntervals does very similar things.

> Source/WebCore/rendering/shapes/RasterShape.cpp:233
> +        intervalGenerator.set(y, intervalsAtY[0].x1(), intervalsAtY.last().x2());

Isn't this going to ignore the intervals inside? Why are you not doing the traversal for each interval?

> Source/WebCore/rendering/shapes/RasterShape.cpp:234
> +        for (int marginY = marginY0; marginY <= marginY1; ++marginY)

You can generate all the intervals for one line and then use ShapeInterval::uniteShapeIntervals to unite it.

[Hans Muller]

(In reply to comment #5)
> (From update of attachment 212398 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=212398&action=review
> 
> > Source/WebCore/ChangeLog:9
> > +        value is an image. The current implementation is correct but suboptimal.
> 
> Is there a bug that will improve it? Why not just do the optimal version now :) ?

Because I'd like to lock down the correct behavior before adding optimizations.  The performance of the current implementation is actually OK.
 
> Is it correct to ignore the empty intervals inside the shape?

Yes.

> 
> > Source/WebCore/rendering/shapes/RasterShape.cpp:56
> > +    m_xIntercepts.resize(radius + 1);
> 
> I'm not sure if it is worth caching these values. And if you don't need the cache, then you don't really need the Generator class at all.

This is not just a cache, although avoiding a sqrt()  per interval is worthwhile.  The other motivation for the Generator class is to factor out of the code that computes margin boundary for a single interval.

> 
> > Source/WebCore/rendering/shapes/RasterShape.cpp:87
> > +    ASSERT(m_intervalLists[y].size() <= 1);
> 
> It seems like you are going to need more than one interval. Seems like ShapeInterval::uniteShapeIntervals does very similar things.

Only one interval is needed - the outermost limits - because the margin boundary is for shape-outside.


> 
> > Source/WebCore/rendering/shapes/RasterShape.cpp:233
> > +        intervalGenerator.set(y, intervalsAtY[0].x1(), intervalsAtY.last().x2());
> 
> Isn't this going to ignore the intervals inside? Why are you not doing the traversal for each interval?

See above.

> 
> > Source/WebCore/rendering/shapes/RasterShape.cpp:234
> > +        for (int marginY = marginY0; marginY <= marginY1; ++marginY)
> 
> You can generate all the intervals for one line and then use ShapeInterval::uniteShapeIntervals to unite it.

See above.

[Alexandru Chiculita]

(In reply to comment #6)
> (In reply to comment #5)
> > (From update of attachment 212398 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=212398&action=review
> > 
> > > Source/WebCore/ChangeLog:9
> > > +        value is an image. The current implementation is correct but suboptimal.
> > 
> > Is there a bug that will improve it? Why not just do the optimal version now :) ?
> 
> Because I'd like to lock down the correct behavior before adding optimizations.  The performance of the current implementation is actually OK.
How different is the optimization going to be from the current code? Suboptimal means there is another algorithm that will do it with a better O() complexity. If you don't think there's one now, you may want to remove that phrase. 

Anyway, if you already have an optimization in mind for the current algorithm implementation, please add a tracking bug and reference it from the changelog. Make sure the bug reflects your thoughts.

> 
> > Is it correct to ignore the empty intervals inside the shape?
> 
> Yes.
It's correct for now, but just because we only support shape-outside on floats. Exclusions are not going to work with this implementation. I think the code would not be a lot more complicated if you did it right from the begining. Please make it work in that case too.

> 
> > 
> > > Source/WebCore/rendering/shapes/RasterShape.cpp:56
> > > +    m_xIntercepts.resize(radius + 1);
> > 
> > I'm not sure if it is worth caching these values. And if you don't need the cache, then you don't really need the Generator class at all.
> 
> This is not just a cache, although avoiding a sqrt()  per interval is worthwhile.  The other motivation for the Generator class is to factor out of the code that computes margin boundary for a single interval.
While the image size is not expected to be too large, making an arbitrary large vector based on a CSS value doesn't seem reasonable to me. You can just provide a large margin and crash the allocator.

> 
> > 
> > > Source/WebCore/rendering/shapes/RasterShape.cpp:87
> > > +    ASSERT(m_intervalLists[y].size() <= 1);
> > 
> > It seems like you are going to need more than one interval. Seems like ShapeInterval::uniteShapeIntervals does very similar things.
> 
> Only one interval is needed - the outermost limits - because the margin boundary is for shape-outside.
See above.
> 
> 
> > 
> > > Source/WebCore/rendering/shapes/RasterShape.cpp:233
> > > +        intervalGenerator.set(y, intervalsAtY[0].x1(), intervalsAtY.last().x2());
> > 
> > Isn't this going to ignore the intervals inside? Why are you not doing the traversal for each interval?
> 
> See above.
> 
> > 
> > > Source/WebCore/rendering/shapes/RasterShape.cpp:234
> > > +        for (int marginY = marginY0; marginY <= marginY1; ++marginY)
> > 
> > You can generate all the intervals for one line and then use ShapeInterval::uniteShapeIntervals to unite it.
> 
> See above.

[Hans Muller]

(In reply to comment #7)
> (In reply to comment #6)
> > (In reply to comment #5)
> > > (From update of attachment 212398 [details] [details] [details])
> > > View in context: https://bugs.webkit.org/attachment.cgi?id=212398&action=review
> > > 
> > > > Source/WebCore/ChangeLog:9
> > > > +        value is an image. The current implementation is correct but suboptimal.
> > > 
> > > Is there a bug that will improve it? Why not just do the optimal version now :) ?
> > 
> > Because I'd like to lock down the correct behavior before adding optimizations.  The performance of the current implementation is actually OK.
> How different is the optimization going to be from the current code? Suboptimal means there is another algorithm that will do it with a better O() complexity. If you don't think there's one now, you may want to remove that phrase. 
> 
> Anyway, if you already have an optimization in mind for the current algorithm implementation, please add a tracking bug and reference it from the changelog. Make sure the bug reflects your thoughts.

Since the point about "suboptimal" seems to be misleading, I've removed it.

> 
> > 
> > > Is it correct to ignore the empty intervals inside the shape?
> > 
> > Yes.
> It's correct for now, but just because we only support shape-outside on floats. Exclusions are not going to work with this implementation. I think the code would not be a lot more complicated if you did it right from the begining. Please make it work in that case too.

Even when we add support for exclusions this code will just become an important special case. It makes the cost of computing the margin boundary proportional to the number of  lines that contain above-threshold pixels, instead of that and the number of above-threshold intervals per line.

> > > > Source/WebCore/rendering/shapes/RasterShape.cpp:56
> > > > +    m_xIntercepts.resize(radius + 1);
> > > 
> > > I'm not sure if it is worth caching these values. And if you don't need the cache, then you don't really need the Generator class at all.
> > 
> > This is not just a cache, although avoiding a sqrt()  per interval is worthwhile.  The other motivation for the Generator class is to factor out of the code that computes margin boundary for a single interval.
> While the image size is not expected to be too large, making an arbitrary large vector based on a CSS value doesn't seem reasonable to me. You can just provide a large margin and crash the allocator.

I've changed the code to limit this value to the maximum width,height of the image.  Doing so doesn't affect the correctness of the implementation and it prevents the problem you've pointed out.

[Hans Muller]

Created attachment 212815 [details]
Patch

Made the suggested changes.

[Build Bot]

Comment on attachment 212815 [details]
Patch

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

New failing tests:
media/track/track-cue-rendering-vertical.html

[Build Bot]

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

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

[Build Bot]

Comment on attachment 212815 [details]
Patch

Attachment 212815 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/2657286

[Hans Muller]

Created attachment 212871 [details]
Patch

EWS bot test failure doesn't appear to have anything to do with this patch.  Resync'd.

[Build Bot]

Comment on attachment 212871 [details]
Patch

Attachment 212871 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/2660363

[Hans Muller]

Created attachment 212995 [details]
Patch

Avoid Win32 compile problems by casting sqrt's argument.

[Alexandru Chiculita]

Comment on attachment 212995 [details]
Patch

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

Thanks! I think that another round will make it perfect :)

> LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-002.html:36
> +        -webkit-shape-margin: 50px;

We should have negative testing as well, so please add "-webkit-shape-margin: 0px" and "-webkit-shape-margin: -100px" as well as "-webkit-shape-margin: -1000000px"

> Source/WebCore/rendering/shapes/RasterShape.cpp:55
> +    ASSERT(radius >= 0);

Use unsigned.

> Source/WebCore/rendering/shapes/RasterShape.cpp:56
> +    m_xIntercepts.resize(radius + 1);

Is there any limit defined for the radius?

> Source/WebCore/rendering/shapes/RasterShape.cpp:87
> +    ASSERT(m_intervalLists[y].size() <= 1);

You need a comment explaining what happened when this assert fails.

> Source/WebCore/rendering/shapes/RasterShape.cpp:233
> +        intervalGenerator.set(y, intervalsAtY[0].x1(), intervalsAtY.last().x2());

This is still not addressing the previous review comments, so it's not going to work with non-floats exclusions that have empty spaces in the middle. 

Can you at least add a comment saying that we will need to revisit and rewrite this function? Add a bug for it and reference it from the comments.

> Source/WebCore/rendering/shapes/RasterShape.cpp:247
> +    int marginBoundaryRadius = std::min(clampToInteger(shapeMargin()), std::max(m_imageSize.width(), m_imageSize.height()));

Replace clampToInteger() with clampTo<unsigned>(). Look in "template<> inline CSSPrimitiveValue::operator unsigned() const" for another example. Might be usefull to add a function to MathExtras.h.

I suppose you need to ceil() the margin, so that 5.5px will be considered 6px instead.

[Hans Muller]

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

> > LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-002.html:36
> > +        -webkit-shape-margin: 50px;
> 
> We should have negative testing as well, so please add "-webkit-shape-margin: 0px" and "-webkit-shape-margin: -100px" as well as "-webkit-shape-margin: -1000000px"

Negative shape-margin values are just truncated to zero. The existing tests in fast/shapes/parsing/script-tests/parsing-shape-margin.js check this.

I added a test that verifies that specifying "-webkit-shape-margin: 0px" does what you'd expect.

> > Source/WebCore/rendering/shapes/RasterShape.cpp:56
> > +    m_xIntercepts.resize(radius + 1);
> 
> Is there any limit defined for the radius?

Yes. RasterShape::marginIntervals() limits it to the max of the image's width and height.

[Hans Muller]

Created attachment 213131 [details]
Patch

Made the suggested changes.

[WebKit Commit Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-001-expected.txt', u'LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-001.html', u'LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-002-expected.txt', u'LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-002.html', u'LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-003-expected.html', u'LayoutTests/fast/shapes/shape-outside-floats/shape-outside-floats-image-margin-003.html', u'Source/WTF/wtf/MathExtras.h', u'Source/WebCore/ChangeLog', u'Source/WebCore/rendering/shapes/RasterShape.cpp', u'Source/WebCore/rendering/shapes/RasterShape.h', u'Source/WebCore/rendering/shapes/Shape.cpp']" exit_code: 1
Source/WebCore/ChangeLog:27:  Need whitespace between colon and description  [changelog/filechangedescriptionwhitespace] [5]
Total errors found: 1 in 12 files


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

[Hans Muller]

Created attachment 213133 [details]
Patch

Fixed a CL typo.

[Hans Muller]

Created attachment 213267 [details]
Patch

RasterShapeIntervals::computeShapeMarginIntervals' margin parameter is now unsigned.

[Hans Muller]

Created attachment 213268 [details]
Patch

Resync'd the previous patch.

[Alexandru Chiculita]

Comment on attachment 213268 [details]
Patch

Thanks Hans!

[WebKit Commit Bot]

Comment on attachment 213268 [details]
Patch

Clearing flags on attachment: 213268

Committed r156838: <http://trac.webkit.org/changeset/156838>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.