Bug 201905 – shape-outside should support path() syntax

• Component: CSS
• Status: NEW

[Dirk Schulze]

shape-outside will support the path() syntax after a recent resolution of the CSS WG (link follows). Should be added to shape-outside similar as it was added to clip-path. We can use the logic from getTotalLengthOfSVGPathByteStream in SVGPathUtilities (with a different mode for PathTraversal for instance) to transform a path into a polygon. With this polygon, we can use the existing layout code w/o any modifications.

[Dirk Schulze]

Created attachment 382672 [details]
Crashes WebKit: shape-outside with path()

[Dirk Schulze]

Created attachment 382673 [details]
Patch

[Dirk Schulze]

This patch does not address multiple sub-paths that are possible with path(). For now, everything would be one shape. Sub-paths are connected with a path from the last point of a sub-path with the first point of the next sub-path.

That should be good enough for now but we should address multiple sub-paths by supporting multiple shapes or ask the CSS WG to just support one sub-path in general. I'd suggest opening a new bug for sub-paths.

[Simon Fraser (smfr)]

I don't understand the CRASH prefix. Is this causing assertions now?

[Dirk Schulze]

The test crashes the browser window. The patch fixes it by implementing the missing path() support.

[Simon Fraser (smfr)]

Comment on attachment 382673 [details]
Patch

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

> Source/WebCore/ChangeLog:3
> +        CRASH shape-outside should support path() syntax

Let's call this "Fix crash/assertion by implementing the path() syntax on shape-outside

> Source/WebCore/ChangeLog:17
> +        Tests: css3/shapes/spec-examples/shape-outside-020.html
> +               css3/shapes/spec-examples/shape-outside-021.html

I imported WPT into imported/w3c/web-platform-tests/css/css-shapes recently. Do these not test the path() syntax?

> Source/WebCore/platform/graphics/PathTraversalState.h:91
> +    Vector<FloatPoint> m_points;

Can we reserveCapacity() on this vector somewhere to improve performance?

> Source/WebCore/rendering/shapes/Shape.cpp:147
> +        // TODO: Currently, WebCoree just supports single shapes. Path syntax may have multiple sub-paths.

WebCoree!

> Source/WebCore/rendering/shapes/Shape.cpp:153
> +        std::unique_ptr<Vector<FloatPoint>> vertices = makeUnique<Vector<FloatPoint>>(valuesSize);
> +        for (unsigned i = 0; i < valuesSize; ++i)
> +            (*vertices)[i] = physicalPointToLogical(values[i], logicalBoxSize.height(), writingMode);

This could be far more efficient in the common case (isHorizontalWritingMode) because it could just copy the vector.

> Source/WebCore/rendering/style/BasicShapes.cpp:353
> +    buildLengthVectorFromByteStream(*m_byteStream, m_values, 3.f);

What is 3.f? Put into a named constant.

> Source/WebCore/svg/SVGPathUtilities.cpp:251
> +    points = WTFMove(builder.pointsList());

Make Vector<FloatPoint> the return value of this function?

[Said Abou-Hallawa]

Comment on attachment 382673 [details]
Patch

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

> Source/WebCore/platform/graphics/PathTraversalState.cpp:211
> +    m_totalLength += curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), m_previous, m_current, m_points, m_pathSegmentLengthTolerance);

It is weird that we pass *this as const to curveLength() but also we pass m_current and m_point as non-const as part of the output of this function. It will be nice if this function have symmetry with the above ones. If we make curveLength() returns std::pair<float, Vector<FloatPoint>>, this function can be written like this:

auto result = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), m_previous, m_pathSegmentLengthTolerance);
m_totalLength += result .first;
m_current = result.second.last();
m_points.appendVector(result.second);

By doing that curveLength() will have no effect this PathTraversalState and all its output will returned in the std::pair.

>> Source/WebCore/rendering/shapes/Shape.cpp:147
>> +        // TODO: Currently, WebCoree just supports single shapes. Path syntax may have multiple sub-paths.
> 
> WebCoree!

Also we use FIXME.

> Source/WebCore/svg/SVGPathUtilities.h:52
> +void buildLengthVectorFromByteStream(const SVGPathByteStream&, Vector<FloatPoint>&, float pathSegmentLengthTolerance = 0);

It is weird to set the default of pathSegmentLengthTolerance to 0 here and check if (pathSegmentLengthTolerance) before calling setPathSegmentLengthTolerance() in buildLengthVectorFromByteStream(). Can't we just set the default to kPathSegmentLengthTolerance since 0 is an invalid value?

[Dirk Schulze]

(In reply to Simon Fraser (smfr) from comment #6)
> Comment on attachment 382673 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=382673&action=review
> 
> > Source/WebCore/ChangeLog:3
> > +        CRASH shape-outside should support path() syntax
> 
> Let's call this "Fix crash/assertion by implementing the path() syntax on
> shape-outside
This is just the bug title. I can rename the bug title but CRASH was meant as a prefix like REGRESSION.


> 
> > Source/WebCore/ChangeLog:17
> > +        Tests: css3/shapes/spec-examples/shape-outside-020.html
> > +               css3/shapes/spec-examples/shape-outside-021.html
> 
> I imported WPT into imported/w3c/web-platform-tests/css/css-shapes recently.
> Do these not test the path() syntax?
No. path() has been added to the spec recently. I intent to commit the tests to WPT as well.

> 
> > Source/WebCore/platform/graphics/PathTraversalState.h:91
> > +    Vector<FloatPoint> m_points;
> 
> Can we reserveCapacity() on this vector somewhere to improve performance?
We don't know the size of the vector up-front. The size depends on the length of the curve which we compute on the fly.

> 
> > Source/WebCore/rendering/shapes/Shape.cpp:147
> > +        // TODO: Currently, WebCoree just supports single shapes. Path syntax may have multiple sub-paths.
> 
> WebCoree!
:P

> 
> > Source/WebCore/rendering/shapes/Shape.cpp:153
> > +        std::unique_ptr<Vector<FloatPoint>> vertices = makeUnique<Vector<FloatPoint>>(valuesSize);
> > +        for (unsigned i = 0; i < valuesSize; ++i)
> > +            (*vertices)[i] = physicalPointToLogical(values[i], logicalBoxSize.height(), writingMode);
> 
> This could be far more efficient in the common case
> (isHorizontalWritingMode) because it could just copy the vector.
What do you suggest?

physicalRectToLogical does return the passed rect if isHorizontalWritingMode is true.
 
> 
> > Source/WebCore/rendering/style/BasicShapes.cpp:353
> > +    buildLengthVectorFromByteStream(*m_byteStream, m_values, 3.f);
> 
> What is 3.f? Put into a named constant.

Named it kPathToleranceLevelForShapePoints.


> 
> > Source/WebCore/svg/SVGPathUtilities.cpp:251
> > +    points = WTFMove(builder.pointsList());
> 
> Make Vector<FloatPoint> the return value of this function?

Done.

[Dirk Schulze]

(In reply to Said Abou-Hallawa from comment #7)
> Comment on attachment 382673 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=382673&action=review
> 
> > Source/WebCore/platform/graphics/PathTraversalState.cpp:211
> > +    m_totalLength += curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), m_previous, m_current, m_points, m_pathSegmentLengthTolerance);
> 
> It is weird that we pass *this as const to curveLength() but also we pass
> m_current and m_point as non-const as part of the output of this function.
> It will be nice if this function have symmetry with the above ones. If we
> make curveLength() returns std::pair<float, Vector<FloatPoint>>, this
> function can be written like this:
> 
> auto result = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current,
> newControl, newEnd), m_previous, m_pathSegmentLengthTolerance);
> m_totalLength += result .first;
> m_current = result.second.last();
> m_points.appendVector(result.second);

I don't understand the benefit. Readability? Performance wise it seems to make more sense to pass a reference rather than the copy operations of FloatPoint.

> 
> By doing that curveLength() will have no effect this PathTraversalState and
> all its output will returned in the std::pair.
> 
> >> Source/WebCore/rendering/shapes/Shape.cpp:147
> >> +        // TODO: Currently, WebCoree just supports single shapes. Path syntax may have multiple sub-paths.
> > 
> > WebCoree!
> 
> Also we use FIXME.

It is not really a FIXME IMO but removed the TODO.

> 
> > Source/WebCore/svg/SVGPathUtilities.h:52
> > +void buildLengthVectorFromByteStream(const SVGPathByteStream&, Vector<FloatPoint>&, float pathSegmentLengthTolerance = 0);
> 
> It is weird to set the default of pathSegmentLengthTolerance to 0 here and
> check if (pathSegmentLengthTolerance) before calling
> setPathSegmentLengthTolerance() in buildLengthVectorFromByteStream(). Can't
> we just set the default to kPathSegmentLengthTolerance since 0 is an invalid
> value?

Yeah. I wanted to avoid copying the definitions. kPathSegmentLengthTolerance would be defined in 2 places. However, the compiler would be able to optimise the constexpr. Though there is still the issue of having the definition in 2 places. Creating a new header that gets included by all resources seems to be an overkill.

[Dirk Schulze]

Created attachment 382832 [details]
Patch

[Said Abou-Hallawa]

Comment on attachment 382673 [details]
Patch

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

>>> Source/WebCore/platform/graphics/PathTraversalState.cpp:211
>>> +    m_totalLength += curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), m_previous, m_current, m_points, m_pathSegmentLengthTolerance);
>> 
>> It is weird that we pass *this as const to curveLength() but also we pass m_current and m_point as non-const as part of the output of this function. It will be nice if this function have symmetry with the above ones. If we make curveLength() returns std::pair<float, Vector<FloatPoint>>, this function can be written like this:
>> 
>> auto result = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), m_previous, m_pathSegmentLengthTolerance);
>> m_totalLength += result .first;
>> m_current = result.second.last();
>> m_points.appendVector(result.second);
>> 
>> By doing that curveLength() will have no effect this PathTraversalState and all its output will returned in the std::pair.
> 
> I don't understand the benefit. Readability? Performance wise it seems to make more sense to pass a reference rather than the copy operations of FloatPoint.

Readability?
Yes. What is the point in passing a "const PathTraversalState&" and at the same time passing "FloatPoint&, FloatPoint&, Vector<FloatPoint>&, float" from the same PathTraversalState? 

-- So I think the least we can do is to change the prototype of curveLength() to look like this:
    static float curveLength(PathTraversalState& traversalState, const CurveType& originalCurve)
I think this would make more sense. There is no need to pass m_previous, m_current, m_points, m_pathSegmentLengthTolerance to curveLength() since they can be accessed/modified through the argument PathTraversalState&.

-- Another approach is to make curveLength() a member of PathTraversalState.

Performance?
I am not sure which approach is faster:

1. Passing m_points to curveLength() and keep appending points to it multiple times.
2. Or make curveLength() create a new Vector and keep appending points to it multiple times. Return the new Vector to quadraticBezierTo() which is a move operation. Then quadraticBezierTo() will call appendVector() to copy the returned Vector into m_points.

I think m_points can grow significantly while a new Vector created by curveLength() should not be that large. So the multiple append() to  m_points can be more costly than the multiple append() to a new Vector.  And I think there is much performance difference between Vector::append() and Vector::appendVector() in this case because appendVector() expands the capacity only once.

Do you think approach 1 is faster than 2 even when m_points gets larger?

[Dirk Schulze]

Created attachment 382907 [details]
Patch

[Dirk Schulze]

Ping

[Said Abou-Hallawa]

Comment on attachment 382907 [details]
Patch

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

> Source/WebCore/ChangeLog:3
> +        CRASH shape-outside should support path() syntax

Does WebKit crashes in the release build? Or does it just assert in debug build because of the unhandled BasicShapePath?

> Source/WebCore/platform/graphics/PathTraversalState.cpp:151
> +    Vector<FloatPoint> pointsOfCurve;

All the PathTraversalState clients do not use pointsOfCurve. Should not we scope the memory and CPU cost to the traverse we do in buildLengthVectorFromByteStream()?

> Source/WebCore/platform/graphics/PathTraversalState.cpp:177
>          curveStack.removeLast();

curve = curveStack.takeLast()?

> Source/WebCore/platform/graphics/PathTraversalState.cpp:187
> +    m_points.appendVector(pointsOfCurve);
> +    m_points.append(curve.end);

Should be the order reversed since pointsOfCurve is smaller?

pointsOfCurve.append(curve.end);
m_points.appendVector(pointsOfCurve);

> Source/WebCore/platform/graphics/PathTraversalState.h:62
> +    Vector<FloatPoint>& points() { return m_points; }

const Vector<FloatPoint>& points() const { return m_points; }

> Source/WebCore/rendering/shapes/Shape.cpp:150
> +        // the desired behavior.

In what level do the sub-paths are connected: CSS parser or the layout?

> Source/WebCore/rendering/shapes/Shape.cpp:155
> +        shape = createPolygonShape(WTFMove(vertices), path.windRule());

I understand it is very difficult to deal with a Path during layout. And it is convenient to convert the path to a polygon here. But I think it is very inefficient to convert the sub-paths to a polygon and let PolygonShape::buildDisplayPaths() convert the points back to a path again. I think it will make more sense in this case to return the original Path instead of building it from the points. Should not we have a class named PathShape which is derived from PolygonShape? Similar to BasicShapePath, this class will store also the SVGPathByteStream and in its buildDisplayPaths() it will return buildPathFromByteStream(*m_byteStream).

> Source/WebCore/rendering/style/BasicShapes.cpp:50
> +constexpr float kPathToleranceLevelForShapePoints { 3.f };

PathTraversalState stores the tolerance in member named m_pathSegmentLengthTolerance. So should we stick with one prefix for all the tolerances?

constexpr float kPathSegmentLengthToleranceForLength { 0.00001f };
constexpr float kPathSegmentLengthToleranceForShapePoints { 3.f };

Or the other way around.

> Source/WebCore/rendering/style/BasicShapes.cpp:354
> +    // We may need to reduce the path tolerance level in the future.

Should we calculate the tolerance based on the number and the types of the segments of the path?

> Source/WebCore/svg/SVGPathTraversalStateBuilder.cpp:74
> +Vector<FloatPoint>& SVGPathTraversalStateBuilder::pointsList()

Why the name here is pointsList() while it is points() in PathTraversalState although they both return Vector<FloatPoint>&?

> Source/WebCore/svg/SVGPathTraversalStateBuilder.h:38
> +    Vector<FloatPoint>& pointsList();

const Vector<FloatPoint>& pointsList() const;

> Source/WebCore/svg/SVGPathUtilities.cpp:238
> +Vector<FloatPoint> buildLengthVectorFromByteStream(const SVGPathByteStream& stream, float pathSegmentLengthTolerance)

Why it's named buildLengthVectorFromByteStream()? It does not return a Vector<Length>. Should not its name be something like buildPointVectorFromByteStream(), buildPointListFromByteStream() or buildPolygonPointsFromByteStream()?

> Source/WebCore/svg/SVGPathUtilities.h:54
> +Vector<FloatPoint> buildLengthVectorFromByteStream(const SVGPathByteStream&, float pathSegmentLengthTolerance = kPathSegmentLengthTolerance);

I think using kPathSegmentLengthTolerance which 0.00001f as the default value for generating the points of the polygon is inappropriate. If it is used, it will generate a huge number of points needlessly. So I think either change the default value to something a lot bigger than kPathSegmentLengthTolerance or delete the default value for the tolerance argument.

> LayoutTests/css3/shapes/spec-examples/shape-outside-020.html:8
> +    <link rel="match" href="reference/shape-outside-020-ref.html"/>

This is not needed but at least we can change it to <link rel="match" href="shape-outside-020-expected.html"/>

[Said Abou-Hallawa]

Comment on attachment 382907 [details]
Patch

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

> Source/WebCore/platform/graphics/PathTraversalState.cpp:144
> +float PathTraversalState::curveLength(const CurveType& originalCurve)

curveLength() is not a good name anymore since this function may process the curve to generate equivalent points. It looks like PathTraversalState has to make a distinction from the beginning regarding the purpose of scanning: finding the length or generating the points.

[Simon Fraser (smfr)]

I'm still looking for a better title too :)

[Tim Nguyen (:ntim)]

I'm not seeing any crash.

[Tim Nguyen (:ntim)]

Looks like this commit fixed the crash: bug 207399 (https://github.com/WebKit/WebKit/commit/11200b769e9edf57ba466ebcb8118ac7d369a154)

[Tim Nguyen (:ntim)]

Comment on attachment 382907 [details]
Patch

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

The part disabling the path() function needs to be undone: https://github.com/WebKit/WebKit/commit/11200b769e9edf57ba466ebcb8118ac7d369a154

> LayoutTests/ChangeLog:15
> +        * css3/shapes/spec-examples/shape-outside-020-expected.html: Added.
> +        * css3/shapes/spec-examples/shape-outside-020.html: Added.
> +        * css3/shapes/spec-examples/shape-outside-021-expected.html: Added.
> +        * css3/shapes/spec-examples/shape-outside-021.html: Added.

These should be committed to WPT now. This directory no longer exists in WebKit.

[Radar WebKit Bug Importer]

<rdar://problem/93178320>

[Sebastian Zartner]

> shape-outside will support the path() syntax after a recent resolution of the CSS WG (link follows).

For what it's worth, here's the link to the resolution:
https://github.com/w3c/csswg-drafts/issues/4270#issuecomment-531669816

And the related spec. link is this one:
https://drafts.csswg.org/css-shapes-1/#funcdef-basic-shape-path

Sebastian