Bug 96811

Created attachment 165870 [details] Patch No tests yet. Checking to see if the various build changes are correct.

Attachment 165870 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/CMakeLists.txt', u'Source/W..." exit_code: 1 Source/WebCore/rendering/ExclusionPolygon.cpp:289: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] Source/WebCore/rendering/ExclusionPolygon.cpp:358: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] Source/WebCore/rendering/ExclusionPolygon.cpp:359: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] Source/WebCore/rendering/ExclusionPolygon.cpp:382: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] Source/WebCore/rendering/ExclusionPolygon.cpp:383: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3] Total errors found: 5 in 9 files If any of these errors are false positives, please file a bug against check-webkit-style.

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

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

Created attachment 165877 [details] Patch

Comment on attachment 165877 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=165877&action=review Looking good. The geometry is a bit difficult to grok, but seems ok. I'm sure we'll know more once you add tests :) In general, I think the variable names could be more descriptive, particularly the single letter ones ("i" and "e"). http://www.webkit.org/coding/coding-style.html#names-full-words > Source/WebCore/rendering/ExclusionPolygon.cpp:1 > + /* Extra leading space > Source/WebCore/rendering/ExclusionPolygon.cpp:51 > +struct MaxEdgeYComparator { Maybe EdgeMaxYComparator instead? Since you are comparing Edge::maxY. > Source/WebCore/rendering/ExclusionPolygon.cpp:63 > +struct MinEdgeYComparator { Ditto for minY. > Source/WebCore/rendering/ExclusionPolygon.cpp:171 > + minX = std::min(x, minX); There is one extra round of comparisons here, since minX/y, maxX/Y are initialized to getX/YAt(0). Not sure it's worth breaking it into two loops to solve the problem, but thought I'd point it out. > Source/WebCore/rendering/ExclusionPolygon.cpp:188 > + std::sort(sortedEdgesMinY.begin(), sortedEdgesMinY.end(), MinEdgeYComparator()); It seems a little odd to me that the vector called sortedEdgesMinY is not actually sorted until near the end of its scope. > Source/WebCore/rendering/ExclusionPolygon.cpp:268 > + const EdgeIntersection& thisInt = intersections[index]; May just be me, but I kept confusing "Int" with "Integer" in the code below. Is there another name? What about intersection & nextIntersection? > Source/WebCore/rendering/ExclusionPolygon.cpp:298 > + int vi = (getYAt(thisEdge.i2) > getYAt(thisEdge.i1)) ? thisEdge.i2 : thisEdge.i1; I think at least one of "vertex" or "index" should be expanded, possibly both. > Source/WebCore/rendering/ExclusionPolygon.cpp:311 > + m_edgeTree->findEdgesThatOverlapInterval(y1, y2, overlappingEdges); Here the parameters are y1, y2, but findEdgesThatOverlapInterval expects yMin, yMax. Should these be yMin/yMax as well? > Source/WebCore/rendering/ExclusionPolygon.h:97 > + // FIXME: minSubtreeSize - don't bother creating subtrees for less than N edges The comment is a little confusing (I only get it now that I read the rest of the code). Perhaps file a more detailed bug and reference it here? > Source/WebCore/rendering/ExclusionShape.cpp:96 > + ? createExclusionRectangle(FloatRect(x, y, width, height), FloatSize(radiusX, radiusY)) Inserted extra space here and on the line below. > Source/WebCore/rendering/ExclusionShape.cpp:108 > + ? createExclusionCircle(FloatPoint(centerX, centerY), radius) Ditto. > Source/WebCore/rendering/ExclusionShape.cpp:121 > + ? createExclusionEllipse(FloatPoint(centerX, centerY), FloatSize(radiusX, radiusY)) Ditto. > Source/WebCore/rendering/ExclusionShape.cpp:130 > + Vector<float>* cv = new Vector<float>(valuesSize); What does cv stand for? > Source/WebCore/rendering/ExclusionShapeInsideInfo.h:-57 > - LayoutUnit shapeLogicalTop() const There was an extra space here and on the line below. The removal is good, but does show up in the diff.

(In reply to comment #6) > (From update of attachment 165877 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=165877&action=review Note that many of the seemingly spurious indentation changes were required by a recent check-webkit-style patch - https://bugs.webkit.org/show_bug.cgi?id=97602

(In reply to comment #6) > (From update of attachment 165877 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=165877&action=review > > Source/WebCore/rendering/ExclusionPolygon.h:97 > > + // FIXME: minSubtreeSize - don't bother creating subtrees for less than N edges > > The comment is a little confusing (I only get it now that I read the rest of the code). Perhaps file a more detailed bug and reference it here? I've filed two bugs related to the FIXMEs in the ExclusionPolygonEdgeTree implementation: https://bugs.webkit.org/show_bug.cgi?id=97795 - [CSS Exclusions] internal polygon-edge interval tree should have subtree size limit https://bugs.webkit.org/show_bug.cgi?id=97797 - [CSS Exclusions] internal polygon-edge interval tree should sort overlapping edges lists

Created attachment 166032 [details] Patch Includes tests and ChangeLogs, factors in Bear's feedback.

Comment on attachment 166032 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=166032&action=review I gave the patch a cursory look. 39k is really too big to be landed with one test, LayoutTests are only one type of tests you can add to validate your new data structure (see the unit tests in Tools/TestWebKitAPI/Tests/). I would advise re-using existing structures as much as possible to reduce the size and also because they usually have good APIs. > Source/WebCore/rendering/ExclusionPolygon.cpp:47 > + float x; > + float y; FloatPoint > Source/WebCore/rendering/ExclusionPolygon.cpp:60 > + bool operator() (const ExclusionPolygonEdge* e, float y) const > + { > + return e->minY() < y; > + } This doesn't look like it's used? I find the comparator object to be an overkill compared to using a simple comparator function. > Source/WebCore/rendering/ExclusionPolygon.cpp:167 > + m_edges[i].i2 = (i+1) % nVertices; Style violation. > Source/WebCore/rendering/ExclusionPolygon.h:52 > + float getXAt(size_t i) const { return m_coordinates->at(i*2); } > + float getYAt(size_t i) const { return m_coordinates->at(i*2 + 1); } Coding style violation. > Source/WebCore/rendering/ExclusionPolygon.h:75 > + size_t i1; > + size_t i2; 'i' for 'index'? We usually prefer unsigned instead of size_t. Do we really need this struct which is a glorified std::pair<FloatPoint>? > Source/WebCore/rendering/ExclusionPolygon.h:87 > + ExclusionPolygonEdge() > + : polygon(0) > + , i1(0) > + , i2(0) > + { > + } > + > + float x1() const { return polygon->getXAt(i1); } > + float y1() const { return polygon->getYAt(i1); } > + float x2() const { return polygon->getXAt(i2); } > + float y2() const { return polygon->getYAt(i2); } This API makes no sense: * you are allowing polygon to be 0 but don't check it here. * an edge is supposed to be between two adjacent vertex, yet you don't ASSERT that. > Source/WebCore/rendering/ExclusionPolygon.h:95 > +// an "interval tree" We already have an interval tree in WebCore/platform/PODIntervalTree.h, why can't we reuse it here? > Source/WebCore/rendering/ExclusionPolygon.h:101 > + float center; > + Vector<ExclusionPolygonEdge*> overlapCenter; > + OwnPtr<ExclusionPolygonEdgeTree> aboveCenter; > + OwnPtr<ExclusionPolygonEdgeTree> belowCenter; Any reason why all your data structures are 'struct' even if you end up defining a constructor, without prefixing all the private data members with m_ and allow the copy constructor or assignment operator? This is also backwards, we usually put the members last. > Source/WebCore/rendering/ExclusionShape.cpp:67 > +static PassOwnPtr<ExclusionShape> createExclusionPolygon(PassOwnPtr<Vector<float> > coordinates, WindRule fillRule) > +{ > + ASSERT(!(coordinates->size() % 2)); > + return adoptPtr(new ExclusionPolygon(coordinates, fillRule)); > +} If you are going to pass ExclusionShape in OwnPtr, ExclusionShape should probably be WTF_MAKENONCOPYABLE. > Source/WebCore/rendering/ExclusionShapeInsideInfo.h:58 > + LayoutUnit shapeLogicalTop() const > + { Usually whitespace changes occurs on touched code to avoid confusing svn / git blame. On top of that the last discussion on the topic was a while ago and didn't bear any consensus (https://lists.webkit.org/pipermail/webkit-dev/2009-August/009692.html). I didn't repeat this comment to the other whitespace changes in your patch.

Created attachment 166775 [details] Patch I've made the patch somewhat smaller: - Removed the EdgeTree class, used PODIntervalTree instead - Store FloatPoint vertices instead of x,y coordinates - Replaced the comparator classes with comparator functions - Made the suggested renames, i to index, size_t to unsigned, etc. - Fixed various style violations - Added ASSERTS per the review feedback - Removed unecessary struct constructors - Use [] instead of at() for Vector element access - Various webkit-style non-conformance fixes - restored extraneous spaces ExclusionShapeInsideInfo.h I have not added additional tests although many more are needed. I was hoping to land a set of polygon exclusion shape tests in a separate patch? Notes: > ... an edge is supposed to be between two adjacent vertex, yet you don't ASSERT that. At the moment, edges span adjacent vertices, but in the long run edges will span 2 or more colinear vertices. I didn't add an assertion for the current scheme because the best I could come up with, ASSERT(index2 ? (index2 - index1) == 1 : index1 == polygon->numberVertices() - 1), didn't communicate the point very well. > ... I didn't repeat this comment to the other whitespace changes in your patch. I didn't restore the other extraneous spaces that I'd removed because leaving them there causes the style checker bot to reject the patch, see https://bugs.webkit.org/show_bug.cgi?id=96811#c2 This appears to be due to a recent check-webkit-style patch - https://bugs.webkit.org/show_bug.cgi?id=97602

Comment on attachment 166775 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=166775&action=review I have a lot of questions. > Source/WebCore/ChangeLog:41 > + (WebCore::ExclusionPolygon::ExclusionPolygon): see above for a description of this type > + (WebCore::computeXIntersection): find and classify the X intercept of a polygon edge for some Y value, if any > + (WebCore::ExclusionPolygon::rightVertexY): used to decide if a horizontal line "crosses" a vertex > + (WebCore::appendIntervalX): append the start or end X coordinates of an ExclusionInterval > + (WebCore::ExclusionPolygon::computeXIntersections): all of the intersections of a horizontal line and the polygon's edges > + (WebCore::ExclusionPolygon::computeEdgeIntersections): the X projections of the edges that overlap a horizonal rectangle > + (WebCore::ExclusionPolygon::getExcludedIntervals): X intervals within a horizontal rectangle that overlap the polygon > + (WebCore::ExclusionPolygon::getIncludedIntervals): X intervals within a horizontal rectangle that fit inside the polygon Even small comments need phrases. This is the common style in WebKit that applies to Changelogs as welll. > Source/WebCore/rendering/ExclusionPolygon.cpp:41 > + Normal = 0, > + VertexMinY = 1, > + VertexMaxY = 2, > + VertexYBoth = 3 The integer representation seems unnecessary. You start with 0 anyway. > Source/WebCore/rendering/ExclusionPolygon.cpp:47 > + float x; > + float y; No FloatPoint here? :) > Source/WebCore/rendering/ExclusionPolygon.cpp:62 > + // FIXME: handle special cases: less than 3 non-colinear vertices > + // FIXME: assuming open polygons for now Sentences please. > Source/WebCore/rendering/ExclusionPolygon.cpp:69 > + float minX = getXAt(0); > + float minY = getYAt(0); You call getXAt most of the time in combination with getYAt. Can't you use getPointAt() and also use x,y as FloatPoint representation in ExclusionPolygon? I would just agree, that FloatPoint has no good functionality to get min/max :) > Source/WebCore/rendering/ExclusionPolygon.cpp:92 > + m_boundingBox.setX(minX); > + m_boundingBox.setY(minY); > + m_boundingBox.setWidth(maxX - minX); > + m_boundingBox.setHeight(maxY - minY); It doesn't seem to be a bad idea to add a definition to FloatRect with two FloatPoints top-left, bottom-right. > Source/WebCore/rendering/ExclusionPolygon.cpp:104 > +static bool computeXIntersection(const ExclusionPolygonEdge* ep, float y, EdgeIntersection& result) > +{ > + const ExclusionPolygonEdge& e = *ep; I know you are a programmer, but can you find some nice names instead of just one or two letters please? :) > Source/WebCore/rendering/ExclusionPolygon.cpp:177 > + std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX); Can you use using namespace std; at the beginning of the file please? We usually don't use namespaces in the code itself. > Source/WebCore/rendering/ExclusionPolygon.cpp:190 > + // skip VertexMaxY,VertexMaxY and VertexMinY,VertexMinY A sentence please. > Source/WebCore/rendering/ExclusionPolygon.cpp:196 > + index += 1; index++? > Source/WebCore/rendering/ExclusionPolygon.cpp:220 > + index += 1; Ditto? > Source/WebCore/rendering/ExclusionPolygon.h:48 > +// Used by PODIntervalTree for debugging Dot at the end. :) > Source/WebCore/rendering/ExclusionPolygon.h:59 > + float getXAt(unsigned index) const { return (*m_vertices)[index].x(); } > + float getYAt(unsigned index) const { return (*m_vertices)[index].y(); } I would still like to see a returning FloatPoint& instead. Can also be const. > Source/WebCore/rendering/ExclusionPolygon.h:75 > + OwnPtr<Vector<FloatPoint> > m_vertices; Why does it need to be OwnPtr<...>? > Source/WebCore/rendering/ExclusionPolygon.h:82 > +struct ExclusionPolygonEdge { Why is the definition of this struct not on the top? Dependency reasons? > Source/WebCore/rendering/ExclusionPolygon.h:86 > + float x1() const { ASSERT(polygon); return polygon->getXAt(index1); } > + float y1() const { ASSERT(polygon); return polygon->getYAt(index1); } > + float x2() const { ASSERT(polygon); return polygon->getXAt(index2); } > + float y2() const { ASSERT(polygon); return polygon->getYAt(index2); } Please FloatPoint& :(. > Source/WebCore/rendering/ExclusionPolygon.h:91 > + float minX() const { return std::min(x1(), x2()); } > + float minY() const { return std::min(y1(), y2()); } > + float maxX() const { return std::max(x1(), x2()); } > + float maxY() const { return std::max(y1(), y2()); } How often is minX(), minY(), ... called? Might it make sense to store them? Also, point1() point2() would look so much nicer :). > Source/WebCore/rendering/ExclusionPolygon.h:95 > + const ExclusionPolygon* polygon; > + unsigned index1; > + unsigned index2; I wonder if you don't want to create a real class. Do all these information need to be exposed? > Source/WebCore/rendering/ExclusionShape.cpp:133 > + float vertexX = floatValueForLength(values.at(i), boxWidth); > + float vertexY = floatValueForLength(values.at(i + 1), boxHeight); Use FloatPoint directly and pass the FloatPoint instead. > Source/WebCore/rendering/ExclusionShape.cpp:137 > + vertices->at(vertexIndex).setX(vertexX); > + vertices->at(vertexIndex).setY(vertexY); As I said. Use FloatPoint directly. But even set(float, float) would be better. > Source/WebCore/rendering/ExclusionShape.cpp:140 > + vertices->at(vertexIndex).setY(vertexX); > + vertices->at(vertexIndex).setX(vertexY); Ditto.

(In reply to comment #10) > (From update of attachment 166032 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=166032&action=review I am sorry Julien, didn't see that you reviewed the previous patch and did not include your comments on my review.

Comment on attachment 166775 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=166775&action=review Thanks for looking at this patch Dirk, I have been busy and couldn't give it the attention it needed. >> Source/WebCore/rendering/ExclusionPolygon.cpp:177 >> + std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX); > > Can you use using namespace std; at the beginning of the file please? We usually don't use namespaces in the code itself. Actually this changed and now we shouldn't use "using" declaration in implementation files. Here is the quote from our coding style: "In C++ implementation files, do not use "using" declarations of any kind to import names in the standard template library. Directly qualify the names at the point they're used instead."

Created attachment 167367 [details] Patch I've made all of the suggested code and comment changes with just a few exceptions. To keep this patch's size manageable, I've filed a second bug to cover an additional set of tests: https://bugs.webkit.org/show_bug.cgi?id=98548

Attachment 167367 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1 Source/WebCore/rendering/ExclusionShape.cpp:135: Missing spaces around / [whitespace/operators] [3] Total errors found: 1 in 14 files If any of these errors are false positives, please file a bug against check-webkit-style.

(In reply to comment #12) > (From update of attachment 166775 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=166775&action=review > > Source/WebCore/rendering/ExclusionPolygon.h:95 > > + const ExclusionPolygon* polygon; > > + unsigned index1; > > + unsigned index2; > > I wonder if you don't want to create a real class. Do all these information need to be exposed? ExclusionPolygon uses PODIntervalTree<float, ExclusionPolygonEdge*> to make looking up edges that fall within a Y interval O(log n), where n is the number of edges. The template class assumes that the "UserData" objects it manages, can compute their interval. That's minY() and maxY() in this case. Tthe tree stores these values and the point to the edge in its own node object. The internal methods that retrieve edges from the tree rely on the edge vertex accessors and having the accessors just look their values up in the edge's polygon keeps the object simple and clearly read-only. > > Source/WebCore/rendering/ExclusionPolygon.cpp:92 > > + m_boundingBox.setX(minX); > > + m_boundingBox.setY(minY); > > + m_boundingBox.setWidth(maxX - minX); > > + m_boundingBox.setHeight(maxY - minY); > > It doesn't seem to be a bad idea to add a definition to FloatRect with two FloatPoints top-left, bottom-right. Extending FloatRect in this way could lead to some confusion. Defining the FloatRect's width and height implicitly with a second point makes dealing with a "flipped" coordinate system a little bit tricker because one must remember to swap the two points. > > Source/WebCore/rendering/ExclusionPolygon.h:75 > > + OwnPtr<Vector<FloatPoint> > m_vertices; > > Why does it need to be OwnPtr<...>? ExclusionPolygon is read-only. The vertices vector is allocated in ExclusionShape::createExclusionShape() and passed to the ExclusionPolygon constructor. The OwnPtr just ensures that the vector is deleted. > > Source/WebCore/rendering/ExclusionPolygon.h:82 > > +struct ExclusionPolygonEdge { > > Why is the definition of this struct not on the top? Dependency reasons? Yes, it has a pointer to its ExclusionPolygon.

Created attachment 167370 [details] Patch Fixed the style problem.

Comment on attachment 167370 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=167370&action=review Looks a lot better! Great work! Just some snippets left. As Julien suggested, more tests seem to be necessary. As far as I understood you, you want to upload a second patch just for the tests. I would like to review both together. > Source/WebCore/ChangeLog:16 > + Polygon edges are represented by the ExclusionPolygonEdge class, which records the indices of It is a struct, not a class, right? > Source/WebCore/ChangeLog:18 > + the last edge where index2 is 0. When a polygon edge is defined by 3 or more colinear vertices, What about a point list like this: 4,0 8,0 4,4 0,0 Would it have 3 or 4 edges? Note that the first point is between the second and last point. > Source/WebCore/rendering/ExclusionPolygon.cpp:80 > + const FloatPoint& vertex = vertexAt(i); > + float x = vertex.x(); > + float y = vertex.y(); > + > + minX = std::min(x, minX); > + maxX = std::max(x, maxX); > + minY = std::min(y, minY); > + maxY = std::max(y, maxY); .x() and .y() are inline functions, don't think that you need to define two new floats. > Source/WebCore/rendering/ExclusionPolygon.cpp:112 > + float x1 = edge.vertex1().x(); > + float y1 = edge.vertex1().y(); > + float x2 = edge.vertex2().x(); > + float y2 = edge.vertex2().y(); You are not setting x1-y2. const FloatPoint vertex1 = edge.vertex1(); and vertex.x() calls seem to be good enough. > Source/WebCore/rendering/ExclusionPolygon.cpp:143 > + const FloatPoint& vertex1 = vertexAt((index + 1) % nVertices); > + const FloatPoint& vertex2 = vertexAt((index - 1) % nVertices); Here you do it already. > Source/WebCore/rendering/ExclusionPolygon.cpp:192 > + const EdgeIntersection& nextIntersection = intersections[index +1]; s/index +1/index + 1/ > Source/WebCore/rendering/ExclusionPolygon.cpp:211 > + windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? +1 : -1; s/+1/1/ > Source/WebCore/rendering/ExclusionPolygon.cpp:238 > + float x1, x2; always new definitions. float x1; float x2; WebKit style rules. > Source/WebCore/rendering/ExclusionPolygon.h:84 > + Omit the new line.

(In reply to comment #19) > (From update of attachment 167370 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=167370&action=review > > Source/WebCore/ChangeLog:16 > > + Polygon edges are represented by the ExclusionPolygonEdge class, which records the indices of > > It is a struct, not a class, right? Yes. > > Source/WebCore/ChangeLog:18 > > + the last edge where index2 is 0. When a polygon edge is defined by 3 or more colinear vertices, > What about a point list like this: 4,0 8,0 4,4 0,0 > Would it have 3 or 4 edges? Note that the first point is between the second and last point. Yes, when this optimization is implemented, the edges would have vertex indices 3-1, 1-2, 2-3. I'll put a similar example in the ChangeLog.

Created attachment 167402 [details] Patch Made the requested changes.

(In reply to comment #19) > (From update of attachment 167370 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=167370&action=review > > As far as I understood you, you want to upload a second patch just for the tests. I would like to review both together. I've filed a second bug to cover an additional set of tests: https://bugs.webkit.org/show_bug.cgi?id=98548 Will set the review flag when the patch for 98548 is ready.

Created attachment 167540 [details] Patch Same patch, sync'd with the latest trunk changes.

Created attachment 167586 [details] Patch Added additional tests per 98548. It was easier to bundle all of the changes into one patch.

Comment on attachment 167586 [details] Patch The first test is a good start. Maybe we can make it easier. I think the patch is still good to go. r=me.

Comment on attachment 167586 [details] Patch Clearing flags on attachment: 167586 Committed r130687: <http://trac.webkit.org/changeset/130687>

All reviewed patches have been landed. Closing bug.

*** Bug 96671 has been marked as a duplicate of this bug. ***