Bug 120439 – [CSS Shapes] Revise the ShapeInterval set operations' implementation

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Hans Muller]

The ShapeInterval set operation implementations aren't as efficient or straightforward as they could be. In many cases they needlessly allocate temporary Vector storage, and the implementations are a bit clumsy when it comes to Vector operations. For example the unitVector() method could be simplified as follows:

    static void uniteVectors(const ShapeIntervalVector& a, const ShapeIntervalVector& b, ShapeIntervalVector& result)
    {
        if (a.isEmpty()) {
            result.append(b);
            return;
        }

        if (b.isEmpty()) {
            result.append(a);
            return;
        }

        const_iterator aNext = a.begin();
        const_iterator bNext = b.begin();

        while(aNext != a.end() || bNext != b.end()) {
            const_iterator next = (bNext == b.end() || (aNext != a.end() && *aNext < *bNext)) ? aNext++ : bNext++;
            if (result.empty() || !result.last().overlaps(*next))
                result.append(*next);
            else 
                result.last().set(result.last().x1(), std::max<T>(result.last().x2(), next->x2()));
        }
    }

All of the ShapeInterval set operations assume that their input parameters are sorted vectors of disjoint intervals. Currently this important invariant isn't checked; but it should be.  For example:

template <typename T>
class ShapeInterval { 
public:
...
#ifndef NDEBUG
    static bool isValidVector(const IntervalVector& v)
    {
        for(int i = 1; i < v.size(); i++)
            if (v[i - 1].x2() > v[i].x1())
                return false;
        return true;
    }
#endif

...

    static void uniteVectors(const ShapeIntervalVector& a, const ShapeIntervalVector& b, ShapeIntervalVector& result)
    {
        ASSERT(isValidVector(a) && isValidVector(b));
        ...
    }
}

[Hans Muller]

Created attachment 210168 [details]
Patch

Revised the ShapeIntervals unite, intersect, and subtract operations to improve efficiency and clarity.

No new tests are required, this is just an internal refactoring.

[Hans Muller]

Created attachment 210172 [details]
Patch

Renamed the ShapeIntervals fooVectors() methods to fooShapeIntervals().

[Alexandru Chiculita]

Comment on attachment 210172 [details]
Patch

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

I would like to remove the operator< and operator > from the float intervals. I know you use it for sorting, but for that case I would rather have a separate comparator. The comparator is confusing as it could be interpreted as comparing left, right, both or just the length.

> Source/WebCore/rendering/shapes/ShapeInterval.h:90
>      {

I think we should assert that the two intervals are already sorted.

> Source/WebCore/rendering/shapes/ShapeInterval.h:129
> +            if (working->overlaps(*next)) {

This only works if the intervals in both vectors are not self-overlapping. I think we need to enforce that with an assert. Also, assert that the two are sorted.

> Source/WebCore/rendering/shapes/ShapeInterval.h:138
> +    static void subtractShapeIntervals(const ShapeIntervals& a, const ShapeIntervals& b, ShapeIntervals& result)

Assert the expectations of the function (ie. intervals are sorted and not overlapping)

> Source/WebCore/rendering/shapes/ShapeInterval.h:165
> +                if (aValue < bValue) {

I don't like using the operator < here. I think the actual members instead of the operator "<" would be less confusing. In this case it can be interpreted two ways: a) aValue.x2 < bValue.x1 or b) aValue.x1  < bValue.x1.

You've used this pattern in multiple place, please update all of them and remove the operators.

[Hans Muller]

Created attachment 210401 [details]
Patch

Made the suggested changes.

[Hans Muller]

Created attachment 210402 [details]
Patch

Resync

[Hans Muller]

Created attachment 210403 [details]
Patch

[Alexandru Chiculita]

Comment on attachment 210403 [details]
Patch

Looks good!

[Alexandru Chiculita]

Comment on attachment 210403 [details]
Patch

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

> Source/WebCore/rendering/shapes/PolygonShape.cpp:324
> +        if (thisInterval.overlaps(previousInterval)) {

nit: You can rewrite this with the ++i first to make it easier to read:
if (!thisInterval.overlaps(previousInterval)) {
    ++i;
    continue;
}
previousInterval.setX2(std::max<float>(previousInterval.x2(), thisInterval.x2()));
intervals.remove(i);

> Source/WebCore/rendering/shapes/PolygonShape.cpp:326
> +            intervals.remove(i);

nit: Depending on our use-cases, this call might end up making lots of copies. Might be useful to rewrite this to do only one truncation at the end.

[WebKit Commit Bot]

Comment on attachment 210403 [details]
Patch

Clearing flags on attachment: 210403

Committed r155043: <http://trac.webkit.org/changeset/155043>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.