Bug 72294

Includes a unit test to verify its functionality.

Created attachment 114998 [details] Patch

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

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

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

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 .

misclick.. "... to compute."

(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;

(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.

(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.

Created attachment 115062 [details] Patch

(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?

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.

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

(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?

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.

(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.

(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.

Created attachment 115172 [details] Patch

Uses intersection and operator== to test contains.

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.

Created attachment 115199 [details] Patch

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.

Created attachment 115212 [details] Patch

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.

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.

(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); } }:

Created attachment 115406 [details] Patch

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.

(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.

Created attachment 115410 [details] Patch

Created attachment 115812 [details] Patch

(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!

Created attachment 115818 [details] fixed ChangeLog

Created attachment 124767 [details] Patch rebased and removed the != operators as they are no longer needed, and not exposed externally.

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.

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.

Created attachment 124822 [details] Patch comments addressed. added an operator== for Region with early-out check on the bounds, and using that for contains()

Comment on attachment 124822 [details] Patch Clearing flags on attachment: 124822 Committed r106408: <http://trac.webkit.org/changeset/106408>

All reviewed patches have been landed. Closing bug.

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

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.

Created attachment 125714 [details] Patch for landing

unresolving for CQ

Comment on attachment 125714 [details] Patch for landing Rejecting attachment 125714 [details] from commit-queue. danakj@chromium.org 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.

Comment on attachment 125714 [details] Patch for landing Clearing flags on attachment: 125714 Committed r106893: <http://trac.webkit.org/changeset/106893>

All reviewed patches have been landed. Closing bug.