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)); ... } }
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.
Created attachment 210172 [details] Patch Renamed the ShapeIntervals fooVectors() methods to fooShapeIntervals().
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.
Created attachment 210401 [details] Patch Made the suggested changes.
Created attachment 210402 [details] Patch Resync
Created attachment 210403 [details] Patch
Comment on attachment 210403 [details] Patch Looks good!
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.
Comment on attachment 210403 [details] Patch Clearing flags on attachment: 210403 Committed r155043: <http://trac.webkit.org/changeset/155043>
All reviewed patches have been landed. Closing bug.