RESOLVED FIXED 121619
[CSS Shapes] add shape-margin support for image valued shapes
https://bugs.webkit.org/show_bug.cgi?id=121619
Summary [CSS Shapes] add shape-margin support for image valued shapes
Hans Muller
Reported 2013-09-19 10:54:35 PDT
Currently shape-margin is ignored for image valued shapes.
Attachments
Patch (14.68 KB, patch)
2013-09-23 13:43 PDT, Hans Muller
buildbot: commit-queue-
Patch (14.68 KB, patch)
2013-09-23 15:36 PDT, Hans Muller
achicu: review-
buildbot: commit-queue-
Patch (15.64 KB, patch)
2013-09-27 09:31 PDT, Hans Muller
buildbot: commit-queue-
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
Patch (15.55 KB, patch)
2013-09-27 19:28 PDT, Hans Muller
buildbot: commit-queue-
Patch (15.64 KB, patch)
2013-09-30 08:03 PDT, Hans Muller
achicu: review-
Patch (18.77 KB, patch)
2013-10-01 16:46 PDT, Hans Muller
no flags
Patch (18.80 KB, patch)
2013-10-01 17:09 PDT, Hans Muller
no flags
Patch (6.17 MB, patch)
2013-10-03 09:24 PDT, Hans Muller
no flags
Patch (18.86 KB, patch)
2013-10-03 09:28 PDT, Hans Muller
no flags
Hans Muller
Comment 1 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.
Build Bot
Comment 2 2013-09-23 14:21:58 PDT
Hans Muller
Comment 3 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.
Build Bot
Comment 4 2013-09-23 17:14:50 PDT
Alexandru Chiculita
Comment 5 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.
Hans Muller
Comment 6 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.
Alexandru Chiculita
Comment 7 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.
Hans Muller
Comment 8 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.
Hans Muller
Comment 9 2013-09-27 09:31:53 PDT
Created attachment 212815 [details] Patch Made the suggested changes.
Build Bot
Comment 10 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
Build Bot
Comment 11 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
Build Bot
Comment 12 2013-09-27 17:48:28 PDT
Hans Muller
Comment 13 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.
Build Bot
Comment 14 2013-09-27 21:43:11 PDT
Hans Muller
Comment 15 2013-09-30 08:03:55 PDT
Created attachment 212995 [details] Patch Avoid Win32 compile problems by casting sqrt's argument.
Alexandru Chiculita
Comment 16 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.
Hans Muller
Comment 17 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.
Hans Muller
Comment 18 2013-10-01 16:46:23 PDT
Created attachment 213131 [details] Patch Made the suggested changes.
WebKit Commit Bot
Comment 19 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.
Hans Muller
Comment 20 2013-10-01 17:09:09 PDT
Created attachment 213133 [details] Patch Fixed a CL typo.
Hans Muller
Comment 21 2013-10-03 09:24:16 PDT
Created attachment 213267 [details] Patch RasterShapeIntervals::computeShapeMarginIntervals' margin parameter is now unsigned.
Hans Muller
Comment 22 2013-10-03 09:28:53 PDT
Created attachment 213268 [details] Patch Resync'd the previous patch.
Alexandru Chiculita
Comment 23 2013-10-03 09:49:17 PDT
Comment on attachment 213268 [details] Patch Thanks Hans!
WebKit Commit Bot
Comment 24 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>
WebKit Commit Bot
Comment 25 2013-10-03 10:18:48 PDT
All reviewed patches have been landed. Closing bug.
Note You need to log in before you can comment on or make changes to this bug.