Bug 121619 - [CSS Shapes] add shape-margin support for image valued shapes
Summary: [CSS Shapes] add shape-margin support for image valued shapes
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Hans Muller
URL:
Keywords:
Depends on:
Blocks: 116348 122601
  Show dependency treegraph
 
Reported: 2013-09-19 10:54 PDT by Hans Muller
Modified: 2013-10-10 08:34 PDT (History)
9 users (show)

See Also:


Attachments
Patch (14.68 KB, patch)
2013-09-23 13:43 PDT, Hans Muller
buildbot: commit-queue-
Details | Formatted Diff | Diff
Patch (14.68 KB, patch)
2013-09-23 15:36 PDT, Hans Muller
achicu: review-
buildbot: commit-queue-
Details | Formatted Diff | Diff
Patch (15.64 KB, patch)
2013-09-27 09:31 PDT, Hans Muller
buildbot: commit-queue-
Details | Formatted Diff | Diff
Archive of layout-test-results from webkit-ews-16 for mac-mountainlion-wk2 (978.13 KB, application/zip)
2013-09-27 10:27 PDT, Build Bot
no flags Details
Patch (15.55 KB, patch)
2013-09-27 19:28 PDT, Hans Muller
buildbot: commit-queue-
Details | Formatted Diff | Diff
Patch (15.64 KB, patch)
2013-09-30 08:03 PDT, Hans Muller
achicu: review-
Details | Formatted Diff | Diff
Patch (18.77 KB, patch)
2013-10-01 16:46 PDT, Hans Muller
no flags Details | Formatted Diff | Diff
Patch (18.80 KB, patch)
2013-10-01 17:09 PDT, Hans Muller
no flags Details | Formatted Diff | Diff
Patch (6.17 MB, patch)
2013-10-03 09:24 PDT, Hans Muller
no flags Details | Formatted Diff | Diff
Patch (18.86 KB, patch)
2013-10-03 09:28 PDT, Hans Muller
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Hans Muller 2013-09-19 10:54:35 PDT
Currently shape-margin is ignored for image valued shapes.
Comment 1 Hans Muller 2013-09-23 13:43:04 PDT
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.
Comment 2 Build Bot 2013-09-23 14:21:58 PDT
Comment on attachment 212386 [details]
Patch

Attachment 212386 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/1966485
Comment 3 Hans Muller 2013-09-23 15:36:29 PDT
Created attachment 212398 [details]
Patch

Resync'd to get past the windows EWS build problem - which seems to be unrelated to this patch.
Comment 4 Build Bot 2013-09-23 17:14:50 PDT
Comment on attachment 212398 [details]
Patch

Attachment 212398 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/2096053
Comment 5 Alexandru Chiculita 2013-09-26 09:48:46 PDT
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.
Comment 6 Hans Muller 2013-09-26 09:57:17 PDT
(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.
Comment 7 Alexandru Chiculita 2013-09-26 10:14:28 PDT
(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.
Comment 8 Hans Muller 2013-09-27 09:27:10 PDT
(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.
Comment 9 Hans Muller 2013-09-27 09:31:53 PDT
Created attachment 212815 [details]
Patch

Made the suggested changes.
Comment 10 Build Bot 2013-09-27 10:27:16 PDT
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
Comment 11 Build Bot 2013-09-27 10:27:18 PDT
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
Comment 12 Build Bot 2013-09-27 17:48:28 PDT
Comment on attachment 212815 [details]
Patch

Attachment 212815 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/2657286
Comment 13 Hans Muller 2013-09-27 19:28:40 PDT
Created attachment 212871 [details]
Patch

EWS bot test failure doesn't appear to have anything to do with this patch.  Resync'd.
Comment 14 Build Bot 2013-09-27 21:43:11 PDT
Comment on attachment 212871 [details]
Patch

Attachment 212871 [details] did not pass win-ews (win):
Output: http://webkit-queues.appspot.com/results/2660363
Comment 15 Hans Muller 2013-09-30 08:03:55 PDT
Created attachment 212995 [details]
Patch

Avoid Win32 compile problems by casting sqrt's argument.
Comment 16 Alexandru Chiculita 2013-10-01 10:01:13 PDT
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.
Comment 17 Hans Muller 2013-10-01 16:45:50 PDT
(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.
Comment 18 Hans Muller 2013-10-01 16:46:23 PDT
Created attachment 213131 [details]
Patch

Made the suggested changes.
Comment 19 WebKit Commit Bot 2013-10-01 16:48:54 PDT
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.
Comment 20 Hans Muller 2013-10-01 17:09:09 PDT
Created attachment 213133 [details]
Patch

Fixed a CL typo.
Comment 21 Hans Muller 2013-10-03 09:24:16 PDT
Created attachment 213267 [details]
Patch

RasterShapeIntervals::computeShapeMarginIntervals' margin parameter is now unsigned.
Comment 22 Hans Muller 2013-10-03 09:28:53 PDT
Created attachment 213268 [details]
Patch

Resync'd the previous patch.
Comment 23 Alexandru Chiculita 2013-10-03 09:49:17 PDT
Comment on attachment 213268 [details]
Patch

Thanks Hans!
Comment 24 WebKit Commit Bot 2013-10-03 10:18:44 PDT
Comment on attachment 213268 [details]
Patch

Clearing flags on attachment: 213268

Committed r156838: <http://trac.webkit.org/changeset/156838>
Comment 25 WebKit Commit Bot 2013-10-03 10:18:48 PDT
All reviewed patches have been landed.  Closing bug.