Bug 72294 – Add contains() test to Region

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Dana Jansens]

This adds an occludes(const IntRect&) method to the Region class which tests if the Region fully occludes a given query rectangle.

This code will be used by methods to determine opaque GraphicsLayers from the sum of their RenderObjects.

[Dana Jansens]

Includes a unit test to verify its functionality.

[Dana Jansens]

Created attachment 114998 [details]
Patch

[Early Warning System Bot]

Comment on attachment 114998 [details]
Patch

Attachment 114998 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/10487012

[Dana Jansens]

Created attachment 115009 [details]
make inner loop look like outer loop, work around qt warnings

[Anders Carlsson]

Can't this be implemented in terms of the already existing region operators?

[Dana Jansens]

It is an intersection, but
1) As I understand it, you are not guaranteed to get back just a single rect if it is fully covered, so you would need a similar check of the resulting intersection.
2) It would require building a new Region which would mean a lot of memory allocation, and thus time, to .

[Dana Jansens]

misclick..

"... to compute."

[Anders Carlsson]

(In reply to comment #7)
> misclick..
> 
> "... to compute."

That could be easily fixed by making the segment and span vectors have an inline capacity - then it'd just be stack allocation:


        // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
        Vector<int> m_segments;
        Vector<Span> m_spans;

[Dana Jansens]

(In reply to comment #8)
> (In reply to comment #7)
> > misclick..
> > 
> > "... to compute."
> 
> That could be easily fixed by making the segment and span vectors have an inline capacity - then it'd just be stack allocation:
> 
> 
>         // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
>         Vector<int> m_segments;
>         Vector<Span> m_spans;

From reading the code I don't see what you are suggesting. But please correct me where I am wrong.. If a Vector is given a size, then it will call VectorBufferBase::allocateBuffer() which calls fastMalloc() which calls malloc(). Where is there a stack allocation?

Regarding point 1), I see nothing in Region::Shape::shapeOperation() that guarantees a single rect output for the intersection in the occludes() == true case. It simply adds segments as it goes along, there is nothing more global to consider pruning/combining segments/spans there. So, as I see it, the same test done in occludes() would need to be done on the result of the intersection() - the only change would be knowing that all segments intersect the query rect.

[Anders Carlsson]

(In reply to comment #9)
> (In reply to comment #8)
> > (In reply to comment #7)
> > > misclick..
> > > 
> > > "... to compute."
> > 
> > That could be easily fixed by making the segment and span vectors have an inline capacity - then it'd just be stack allocation:
> > 
> > 
> >         // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
> >         Vector<int> m_segments;
> >         Vector<Span> m_spans;
> 
> From reading the code I don't see what you are suggesting. But please correct me where I am wrong.. If a Vector is given a size, then it will call VectorBufferBase::allocateBuffer() which calls fastMalloc() which calls malloc(). Where is there a stack allocation?

You can give Vector an inline size, like so:

Vector<int, 16> m_segments;

and unless the size of the vector is greater than 16 elements, everything will be allocated as part of the Vector (which is part of the Region).

> 
> Regarding point 1), I see nothing in Region::Shape::shapeOperation() that guarantees a single rect output for the intersection in the occludes() == true case. It simply adds segments as it goes along, there is nothing more global to consider pruning/combining segments/spans there. So, as I see it, the same test done in occludes() would need to be done on the result of the intersection() - the only change would be knowing that all segments intersect the query rect.

Region::Shape::canCoalesce has the logic for coalescing segments - but I think there's an even simpler way to do this.

Also, instead of occludes - let's call the function 'contains', because that's a more logical name. I think contains can be implemented like this:

bool Region::contains(const Region& region)
{
    Region result = intersect(*this, region);

    return result == region;
}

Which is much cleaner and reuses the already existing region operations. The region code is pretty complex as-is; let's not add more complexity to it if we can avoid it.

[Dana Jansens]

Created attachment 115062 [details]
Patch

[Dana Jansens]

(In reply to comment #10)
> (In reply to comment #9)
> > (In reply to comment #8)
> > > (In reply to comment #7)
> > > > misclick..
> > > > 
> > > > "... to compute."
> > > 
> > > That could be easily fixed by making the segment and span vectors have an inline capacity - then it'd just be stack allocation:
> > > 
> > > 
> > >         // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
> > >         Vector<int> m_segments;
> > >         Vector<Span> m_spans;
> > 
> > From reading the code I don't see what you are suggesting. But please correct me where I am wrong.. If a Vector is given a size, then it will call VectorBufferBase::allocateBuffer() which calls fastMalloc() which calls malloc(). Where is there a stack allocation?
> 
> You can give Vector an inline size, like so:
> 
> Vector<int, 16> m_segments;
> 
> and unless the size of the vector is greater than 16 elements, everything will be allocated as part of the Vector (which is part of the Region).

Okay, I see the inlineBuffer.  I have to admit I don't like increasing the size of all Region objects, when walking the segments is sufficient.  I expect Regions have very different use cases hence the lack of this magic inline size value. It's something we can consider, but see below regarding operator==.

> > 
> > Regarding point 1), I see nothing in Region::Shape::shapeOperation() that guarantees a single rect output for the intersection in the occludes() == true case. It simply adds segments as it goes along, there is nothing more global to consider pruning/combining segments/spans there. So, as I see it, the same test done in occludes() would need to be done on the result of the intersection() - the only change would be knowing that all segments intersect the query rect.
> 
> Region::Shape::canCoalesce has the logic for coalescing segments - but I think there's an even simpler way to do this.
> 
> Also, instead of occludes - let's call the function 'contains', because that's a more logical name. I think contains can be implemented like this:
>
> bool Region::contains(const Region& region)
> {
>     Region result = intersect(*this, region);
> 
>     return result == region;

Region::Shape::canCoalesce() enables some simple compression, to merge adjacent spans that have exactly the same segments.  There is no reason to believe that this will be the output of an intersection of an arbitrary region with a rectangle, though. In the contains() == true case, it will be a set of spans, where for each span, the union of segments within start at the query rect's left edge and end at its right edge. The same walk of the intersection must be done.

I also definitely don't want to make this more complex than it needs to be, but:

1) I don't see the ability to do this operator== comparison at the moment.
2) While I can implement the current contains() as operator==(), it will be slower than just doing a single walk (at least two, with possible mallocs/frees).  3) The operator==() method will be /more/ complex than the current contains() code.  It has to do a symmetric comparison rather than just testing one covering the other.

> }
> 
> Which is much cleaner and reuses the already existing region operations. The region code is pretty complex as-is; let's not add more complexity to it if we can avoid it.

The Region::Shape code is somewhat complex but well structured to match its citation cleanly, so I put this function in the Region class instead to separate it from the Region::Shape implementation.

The walk for Region::contains() is quite similar to Region::rects(), but simply looks for gaps between segments or spans that intersect with the query rectangle.  I think it can be a little more clear, and I had some unneeded variables left over from a previous implementation, so I will resubmit it.

From what I see, doing operator== will make for both a more complex and costly solution, will it not?

[Anders Carlsson]

Comment on attachment 115062 [details]
Patch

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

This is looking better, but there are still two major problems with this:

1. You should just make Region::contains take another Region - There's a Region constructor that takes a rect.
2. Please implement contains in terms of intersects() instead of writing 60 lines of code. Like I said, the region code is very complex and we should re-use the already existing region operations (union, intersection and subtraction). I'd give m_segments an inline size of 32 and m_spans a size of 16 - that should cover most types of regions. Thanks for working on this!

> Source/WebCore/platform/graphics/Region.h:44
> +    // Returns true if the rect is contained fully in the areas covered by the Region.
> +    bool contains(const IntRect&) const;

Please add a newline here.

> Source/WebKit/chromium/tests/RegionContainsTest.cpp:31
> +#include "Region.h"
> +

Extra newlines.

[Mark Rowe (bdash)]

Is there some reason why you’re adding a Chromium-specific unit test rather than to the cross-platform unit testing harness?

[Dana Jansens]

(In reply to comment #14)
> Is there some reason why you’re adding a Chromium-specific unit test rather than to the cross-platform unit testing harness?

Only because I understood there is no cross-platform unit testing.

Eg. https://lists.webkit.org/pipermail/webkit-dev/2011-April/016510.html

Where should I be looking for said harness?

[Mark Rowe (bdash)]

Tools/TestWebKitAPI contains a harness that is used on Mac, Windows and Chromium. It doesn’t yet test any WebCore functionality, but it tests WTF, WebKit, and WebKit2 so should be easily extended to work with WebCore too.

[Anders Carlsson]

(In reply to comment #12)
> (In reply to comment #10)
> > (In reply to comment #9)
> > > (In reply to comment #8)
> > > > (In reply to comment #7)
> > > > > misclick..
> > > > > 
> > > > > "... to compute."
> > > > 
> > > > That could be easily fixed by making the segment and span vectors have an inline capacity - then it'd just be stack allocation:
> > > > 
> > > > 
> > > >         // FIXME: These vectors should have inline sizes. Figure out a good optimal value.
> > > >         Vector<int> m_segments;
> > > >         Vector<Span> m_spans;
> > > 
> > > From reading the code I don't see what you are suggesting. But please correct me where I am wrong.. If a Vector is given a size, then it will call VectorBufferBase::allocateBuffer() which calls fastMalloc() which calls malloc(). Where is there a stack allocation?
> > 
> > You can give Vector an inline size, like so:
> > 
> > Vector<int, 16> m_segments;
> > 
> > and unless the size of the vector is greater than 16 elements, everything will be allocated as part of the Vector (which is part of the Region).
> 
> Okay, I see the inlineBuffer.  I have to admit I don't like increasing the size of all Region objects, when walking the segments is sufficient.  I expect Regions have very different use cases hence the lack of this magic inline size value. It's something we can consider, but see below regarding operator==.
> 

I think it's fine to increase the size of Region if it can avoid malloc traffic - Especially since regions are commonly stack-allocated.

> > > 
> > > Regarding point 1), I see nothing in Region::Shape::shapeOperation() that guarantees a single rect output for the intersection in the occludes() == true case. It simply adds segments as it goes along, there is nothing more global to consider pruning/combining segments/spans there. So, as I see it, the same test done in occludes() would need to be done on the result of the intersection() - the only change would be knowing that all segments intersect the query rect.
> > 
> > Region::Shape::canCoalesce has the logic for coalescing segments - but I think there's an even simpler way to do this.
> > 
> > Also, instead of occludes - let's call the function 'contains', because that's a more logical name. I think contains can be implemented like this:
> >
> > bool Region::contains(const Region& region)
> > {
> >     Region result = intersect(*this, region);
> > 
> >     return result == region;
> 
> Region::Shape::canCoalesce() enables some simple compression, to merge adjacent spans that have exactly the same segments.  There is no reason to believe that this will be the output of an intersection of an arbitrary region with a rectangle, though. In the contains() == true case, it will be a set of spans, where for each span, the union of segments within start at the query rect's left edge and end at its right edge. The same walk of the intersection must be done.
> 
> I also definitely don't want to make this more complex than it needs to be, but:
> 
> 1) I don't see the ability to do this operator== comparison at the moment.
> 2) While I can implement the current contains() as operator==(), it will be slower than just doing a single walk (at least two, with possible mallocs/frees).  3) The operator==() method will be /more/ complex than the current contains() code.  It has to do a symmetric comparison rather than just testing one covering the other.
> 

If two regions are equal, they will have exactly the same segments and spans, so checking for equality is as simple as a memcmp. If you can find a case where this isn't true, please file a separate bug about that.

> > }
> > 
> > Which is much cleaner and reuses the already existing region operations. The region code is pretty complex as-is; let's not add more complexity to it if we can avoid it.
> 
> The Region::Shape code is somewhat complex but well structured to match its citation cleanly, so I put this function in the Region class instead to separate it from the Region::Shape implementation.
> 
> The walk for Region::contains() is quite similar to Region::rects(), but simply looks for gaps between segments or spans that intersect with the query rectangle.  I think it can be a little more clear, and I had some unneeded variables left over from a previous implementation, so I will resubmit it.
> 
> From what I see, doing operator== will make for both a more complex and costly solution, will it not?

See my comment above.

[Dana Jansens]

(In reply to comment #17)
> (In reply to comment #12)
> > 1) I don't see the ability to do this operator== comparison at the moment.
> > 2) While I can implement the current contains() as operator==(), it will be slower than just doing a single walk (at least two, with possible mallocs/frees).  3) The operator==() method will be /more/ complex than the current contains() code.  It has to do a symmetric comparison rather than just testing one covering the other.
> > 
> 
> If two regions are equal, they will have exactly the same segments and spans, so checking for equality is as simple as a memcmp. If you can find a case where this isn't true, please file a separate bug about that.

We've been coming at this with different assumptions, mine being that the resulting intersecting region would not always have a single rect as its output if contains() was true.  It seems however that it does, so doing a simple operator== test should be feasable.

[Dana Jansens]

Created attachment 115172 [details]
Patch

[Dana Jansens]

Uses intersection and operator== to test contains.

[Anders Carlsson]

Comment on attachment 115172 [details]
Patch

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

This is looking much better! It looks like it will break the Windows build though.

> Source/WebCore/platform/graphics/Region.cpp:72
> +    Region test(subset);
> +    test.intersect(*this);
> +    return test == subset;

I think this can be written more as:

return intersect(*this, subset) == subset;

(And I'd rename subset to region).

> Source/WebCore/platform/graphics/Region.cpp:103
> +    Shape a = m_shape;
> +    Shape b = other.m_shape;
> +
> +    Shape::SpanIterator aSpan = a.spans_begin();
> +    Shape::SpanIterator bSpan = b.spans_begin();
> +    const Shape::SpanIterator aSpanEnd = a.spans_end();
> +    const Shape::SpanIterator bSpanEnd = b.spans_end();
> +
> +    if (aSpanEnd - aSpan != bSpanEnd - bSpan) // Test for equal number of spans
> +        return false;
> +
> +    for (; aSpan != aSpanEnd; ++aSpan, ++bSpan) {
> +        if (aSpan->y != bSpan->y) // Test if spans are at same position
> +            return false;
> +
> +        Shape::SegmentIterator aSegment = a.segments_begin(aSpan);
> +        Shape::SegmentIterator bSegment = b.segments_begin(bSpan);
> +        const Shape::SegmentIterator aSegmentEnd = a.segments_end(aSpan);
> +        const Shape::SegmentIterator bSegmentEnd = b.segments_end(bSpan);
> +
> +        if (aSegmentEnd - aSegment != bSegmentEnd - bSegment) // Test for equal number of segments
> +            return false;
> +        if (!std::equal(aSegment, aSegmentEnd, bSegment)) // Test if segments are at same positions
> +            return false;
> +    }
> +
> +    return true;

If you write an operator== for Shape, I think this can become much simpler.

[Dana Jansens]

Created attachment 115199 [details]
Patch

[Dana Jansens]

Hopefully this fixes the Windows build for the unit test.

Moved Region::operator== to Region::Shape::operator==. You were right as this lets us just run through the m_spans and m_segments vectors directly.

[Dana Jansens]

Created attachment 115212 [details]
Patch

[Darin Adler]

Comment on attachment 115212 [details]
Patch

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

> Source/WebCore/platform/graphics/Region.cpp:87
> +    if (m_spans.size() != other.m_spans.size())
> +        return false;
> +    if (m_segments.size() != other.m_segments.size())
> +        return false;
> +
> +    for (size_t i = 0; i < m_spans.size(); ++i)
> +        if (m_spans[i] != other.m_spans[i])
> +            return false;
> +    for (size_t i = 0; i < m_segments.size(); ++i)
> +        if (m_segments[i] != other.m_segments[i])
> +            return false;
> +
> +    return true;

Vector already handles ==. You should be able to write:

    return m_spans == other.m_spans && m_segments == other.m_segments;

If you can’t, that’s a bug in Vector.

[Darin Adler]

Comment on attachment 115212 [details]
Patch

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

> Source/WebCore/platform/graphics/Region.h:67
> +        inline bool operator!=(const Span& other) { return y != other.y || segmentIndex != other.segmentIndex; }

As a matter of style we almost always implement either neither or both of == and != and implement != by calling ==.

> Source/WebCore/platform/graphics/Region.h:93
> +        bool operator==(const Shape& other);

Ditto.

[Anders Carlsson]

(In reply to comment #26)
> (From update of attachment 115212 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=115212&action=review
> 
> > Source/WebCore/platform/graphics/Region.h:67
> > +        inline bool operator!=(const Span& other) { return y != other.y || segmentIndex != other.segmentIndex; }
> 
> As a matter of style we almost always implement either neither or both of == and != and implement != by calling ==.
> 
> > Source/WebCore/platform/graphics/Region.h:93
> > +        bool operator==(const Shape& other);
> 
> Ditto.

I also prefer the operators to be free friend functions of Region. Something like 

class Region {

...

friend bool operator==(const Region& a, const Region& b)
{
    return a.m_spans == b.m_spans && a.m_segments == b.m_segments);
}

}:

[Dana Jansens]

Created attachment 115406 [details]
Patch

[Darin Adler]

Comment on attachment 115406 [details]
Patch

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

> Source/WebCore/platform/graphics/Region.h:51
> +    bool contains(const Region&) const { return WebCore::intersect(region, *this).m_shape == region.m_shape; }

This won’t compile because the argument name, region, was omitted.

> Source/WebCore/platform/graphics/Region.h:114
> +        friend bool operator!=(const Shape&, const Shape&);

I don’t think != needs to be a friend.

[Dana Jansens]

(In reply to comment #29)
> (From update of attachment 115406 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=115406&action=review
> 
> > Source/WebCore/platform/graphics/Region.h:51
> > +    bool contains(const Region&) const { return WebCore::intersect(region, *this).m_shape == region.m_shape; }
> 
> This won’t compile because the argument name, region, was omitted.

Oh sorry, moved things last second.

> > Source/WebCore/platform/graphics/Region.h:114
> > +        friend bool operator!=(const Shape&, const Shape&);
> 
> I don’t think != needs to be a friend.

It does because Region::Shape is private, it won't compile otherwise.

[Dana Jansens]

Created attachment 115410 [details]
Patch

[Dana Jansens]

Created attachment 115812 [details]
Patch

[Dana Jansens]

(In reply to comment #30)
> > > Source/WebCore/platform/graphics/Region.h:114
> > > +        friend bool operator!=(const Shape&, const Shape&);
> > 
> > I don’t think != needs to be a friend.
> 
> It does because Region::Shape is private, it won't compile otherwise.

Sorry, it occured to me you were referring to the friend declaration inside of Shape, and you're right.

Uploading a patch with this change. Is there anything else blocking this patch?

Thanks!

[Dana Jansens]

Created attachment 115818 [details]
fixed ChangeLog

[Dana Jansens]

Created attachment 124767 [details]
Patch

rebased and removed the != operators as they are no longer needed, and not exposed externally.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/update-webkit']" exit_code: 9

Updating OpenSource
From git://git.webkit.org/WebKit
   11be23e..9fc4aeb  master     -> origin/master
Partial-rebuilding .git/svn/refs/remotes/origin/master/.rev_map.268f45cc-cd09-0410-ab3c-d52691b4dbfc ...
Currently at 106366 = 11be23e25c7011a2675e260f91a1b3cbfa7052f9
r106368 = 9fc4aeb5a25445667675b8be04139afe13128677
Done rebuilding .git/svn/refs/remotes/origin/master/.rev_map.268f45cc-cd09-0410-ab3c-d52691b4dbfc
First, rewinding head to replay your work on top of it...
Applying: Fix compilation errors on build-webkit --debug --no-workers on mac.
Using index info to reconstruct a base tree...
Falling back to patching base and 3-way merge...
Auto-merging LayoutTests/ChangeLog
CONFLICT (content): Merge conflict in LayoutTests/ChangeLog
Auto-merging LayoutTests/platform/qt/Skipped
CONFLICT (content): Merge conflict in LayoutTests/platform/qt/Skipped
Auto-merging Source/WebCore/ChangeLog
CONFLICT (content): Merge conflict in Source/WebCore/ChangeLog
Failed to merge in the changes.
Patch failed at 0001 Fix compilation errors on build-webkit --debug --no-workers on mac.

When you have resolved this problem run "git rebase --continue".
If you would prefer to skip this patch, instead run "git rebase --skip".
To restore the original branch and stop rebasing run "git rebase --abort".

rebase refs/remotes/origin/master: command returned error: 1

Died at Tools/Scripts/update-webkit line 164.


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

[Anders Carlsson]

Comment on attachment 124767 [details]
Patch

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

> Source/WebCore/platform/graphics/Region.cpp:70
> +    return WebCore::intersect(region, *this).m_shape == region.m_shape;

If you want to, you can add a Region::operator== that checks the bounds rect as well as the shape - that might be useful for other purposes as well.

> Source/WebCore/platform/graphics/Region.h:149
> +inline bool operator==(const Region::Span& a, const Region::Span& b) { return a.y == b.y && a.segmentIndex == b.segmentIndex; }
> +inline bool operator==(const Region::Shape& a, const Region::Shape& b) { return a.m_spans == b.m_spans && a.m_segments == b.m_segments; }
> +

According to our style guidelines, the { should be on a new line.

[Dana Jansens]

Created attachment 124822 [details]
Patch

comments addressed. added an operator== for Region with early-out check on the bounds, and using that for contains()

[WebKit Review Bot]

Comment on attachment 124822 [details]
Patch

Clearing flags on attachment: 124822

Committed r106408: <http://trac.webkit.org/changeset/106408>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Dana Jansens]

looks like the inline sizes break Vector and it tries to free the memory on the stack.

https://bugs.webkit.org/show_bug.cgi?id=77592

[Dana Jansens]

Created attachment 125695 [details]
Patch

I verified on a mac that giving an inline size to the Vector in Region::Shape::shapeOperation makes the stack free() problem go away.

Attached is new patch with that fix. I am not sure what the correct state for the bug should be now.

[Dana Jansens]

Created attachment 125714 [details]
Patch for landing

[Dana Jansens]

unresolving for CQ

[WebKit Review Bot]

Comment on attachment 125714 [details]
Patch for landing

Rejecting attachment 125714 [details] from commit-queue.

[e-mail] does not have committer permissions according to http://trac.webkit.org/browser/trunk/Tools/Scripts/webkitpy/common/config/committers.py.

- If you do not have committer rights please read http://webkit.org/coding/contributing.html for instructions on how to use bugzilla flags.

- If you have committer rights please correct the error in Tools/Scripts/webkitpy/common/config/committers.py by adding yourself to the file (no review needed).  The commit-queue restarts itself every 2 hours.  After restart the commit-queue will correctly respect your committer rights.

[WebKit Review Bot]

Comment on attachment 125714 [details]
Patch for landing

Clearing flags on attachment: 125714

Committed r106893: <http://trac.webkit.org/changeset/106893>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.