Imported WebKit commit cf4f8fc6f19b0629f51860cb2d4b25e139d07e00 (http://svn.webkit.org/repository/webkit/trunk@131592)

New snapshot that includes the build fixes for Mac OS X 10.6 and earlier as well
as the previously cherry-picked changes

1 files changed, 306 insertions, 0 deletions

diff --git a/Source/WebCore/rendering/ExclusionPolygon.cpp b/Source/WebCore/rendering/ExclusionPolygon.cpp
new file mode 100644
index 000000000..e704abfce
--- /dev/null
+++ b/Source/WebCore/rendering/ExclusionPolygon.cpp
@@ -0,0 +1,306 @@
+/*
+ * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer.
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "ExclusionPolygon.h"
+
+#include <wtf/MathExtras.h>
+
+namespace WebCore {
+
+enum EdgeIntersectionType {
+    Normal,
+    VertexMinY,
+    VertexMaxY,
+    VertexYBoth
+};
+
+struct EdgeIntersection {
+    const ExclusionPolygonEdge* edge;
+    FloatPoint point;
+    EdgeIntersectionType type;
+};
+
+static bool compareEdgeMinY(const ExclusionPolygonEdge* e1, const ExclusionPolygonEdge* e2)
+{
+    return e1->minY() < e2->minY();
+}
+
+ExclusionPolygon::ExclusionPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
+    : ExclusionShape()
+    , m_vertices(vertices)
+    , m_fillRule(fillRule)
+{
+    // FIXME: Handle polygons defined with less than 3 non-colinear vertices.
+
+    unsigned nVertices = numberOfVertices();
+    m_edges.resize(nVertices);
+    Vector<ExclusionPolygonEdge*> sortedEdgesMinY(nVertices);
+
+    const FloatPoint& vertex0 = vertexAt(0);
+    float minX = vertex0.x();
+    float minY = vertex0.y();
+    float maxX = minX;
+    float maxY = minY;
+
+    for (unsigned i = 0; i < nVertices; i++) {
+        const FloatPoint& vertex = vertexAt(i);
+
+        minX = std::min(vertex.x(), minX);
+        maxX = std::max(vertex.x(), maxX);
+        minY = std::min(vertex.y(), minY);
+        maxY = std::max(vertex.y(), maxY);
+
+        m_edges[i].polygon = this;
+        m_edges[i].index1 = i;
+        m_edges[i].index2 = (i + 1) % nVertices;
+
+        sortedEdgesMinY[i] = &m_edges[i];
+    }
+
+    m_boundingBox.setX(minX);
+    m_boundingBox.setY(minY);
+    m_boundingBox.setWidth(maxX - minX);
+    m_boundingBox.setHeight(maxY - minY);
+
+    std::sort(sortedEdgesMinY.begin(), sortedEdgesMinY.end(), WebCore::compareEdgeMinY);
+
+    for (unsigned i = 0; i < m_edges.size(); i++) {
+        ExclusionPolygonEdge* edge = &m_edges[i];
+        m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
+    }
+}
+
+static bool computeXIntersection(const ExclusionPolygonEdge* edgePointer, float y, EdgeIntersection& result)
+{
+    const ExclusionPolygonEdge& edge = *edgePointer;
+
+    if (edge.minY() > y || edge.maxY() < y)
+        return false;
+
+    const FloatPoint& vertex1 = edge.vertex1();
+    const FloatPoint& vertex2 = edge.vertex2();
+    float dy = vertex2.y() - vertex1.y();
+
+    float intersectionX;
+    EdgeIntersectionType intersectionType;
+
+    if (!dy) {
+        intersectionType = VertexYBoth;
+        intersectionX = edge.minX();
+    } else if (y == edge.minY()) {
+        intersectionType = VertexMinY;
+        intersectionX = (vertex1.y() < vertex2.y()) ? vertex1.x() : vertex2.x();
+    } else if (y == edge.maxY()) {
+        intersectionType = VertexMaxY;
+        intersectionX = (vertex1.y() > vertex2.y()) ? vertex1.x() : vertex2.x();
+    } else {
+        intersectionType = Normal;
+        intersectionX = ((y - vertex1.y()) * (vertex2.x() - vertex1.x()) / dy) + vertex1.x();
+    }
+
+    result.edge = edgePointer;
+    result.type = intersectionType;
+    result.point.set(intersectionX, y);
+
+    return true;
+}
+
+float ExclusionPolygon::rightVertexY(unsigned index) const
+{
+    unsigned nVertices = numberOfVertices();
+    const FloatPoint& vertex1 = vertexAt((index + 1) % nVertices);
+    const FloatPoint& vertex2 = vertexAt((index - 1) % nVertices);
+
+    if (vertex1.x() == vertex2.x())
+        return vertex1.y() > vertex2.y() ? vertex1.y() : vertex2.y();
+    return vertex1.x() > vertex2.x() ? vertex1.y() : vertex2.y();
+}
+
+static bool appendIntervalX(float x, bool inside, Vector<ExclusionInterval>& result)
+{
+    if (!inside)
+        result.append(ExclusionInterval(x));
+    else
+        result[result.size() - 1].x2 = x;
+
+    return !inside;
+}
+
+static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, const EdgeIntersection& intersection2)
+{
+    float x1 = intersection1.point.x();
+    float x2 = intersection2.point.x();
+    return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2;
+}
+
+void ExclusionPolygon::computeXIntersections(float y, Vector<ExclusionInterval>& result) const
+{
+    Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
+    m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(y, y, 0), overlappingEdges);
+
+    Vector<EdgeIntersection> intersections;
+    EdgeIntersection intersection;
+    for (unsigned i = 0; i < overlappingEdges.size(); i++) {
+        ExclusionPolygonEdge* edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
+        if (computeXIntersection(edge, y, intersection))
+            intersections.append(intersection);
+    }
+    if (intersections.size() < 2)
+        return;
+
+    std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX);
+
+    unsigned index = 0;
+    int windCount = 0;
+    bool inside = false;
+
+    while (index < intersections.size()) {
+        const EdgeIntersection& thisIntersection = intersections[index];
+
+        if (index + 1 < intersections.size()) {
+            const EdgeIntersection& nextIntersection = intersections[index + 1];
+            if ((thisIntersection.point.x() == nextIntersection.point.x()) && (thisIntersection.type == VertexMinY || thisIntersection.type == VertexMaxY)) {
+                if (thisIntersection.type == nextIntersection.type) {
+                    // Skip pairs of intersections whose types are VertexMaxY,VertexMaxY and VertexMinY,VertexMinY.
+                    index += 2;
+                } else {
+                    // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one VertexMinY intersection.
+                    if (nextIntersection.type == VertexMaxY)
+                        intersections[index + 1] = thisIntersection;
+                    index++;
+                }
+                continue;
+            }
+        }
+
+        const ExclusionPolygonEdge& thisEdge = *thisIntersection.edge;
+        bool crossing = !windCount;
+
+        if (fillRule() == RULE_EVENODD) {
+            windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
+            crossing = crossing || !windCount;
+        }
+
+        if ((thisIntersection.type == Normal) || (thisIntersection.type == VertexMinY)) {
+            if (crossing)
+                inside = appendIntervalX(thisIntersection.point.x(), inside, result);
+        } else if (thisIntersection.type == VertexMaxY) {
+            int vertexIndex = (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? thisEdge.index2 : thisEdge.index1;
+            if (crossing && rightVertexY(vertexIndex) > y)
+                inside = appendIntervalX(thisEdge.maxX(), inside, result);
+        } else if (thisIntersection.type == VertexYBoth)
+            result.append(ExclusionInterval(thisEdge.minX(), thisEdge.maxX()));
+
+        index++;
+    }
+}
+
+// Return the X projections of the edges that overlap y1,y2.
+void ExclusionPolygon::computeEdgeIntersections(float y1, float y2, Vector<ExclusionInterval>& result) const
+{
+    Vector<ExclusionPolygon::EdgeInterval> overlappingEdges;
+    m_edgeTree.allOverlaps(ExclusionPolygon::EdgeInterval(y1, y2, 0), overlappingEdges);
+
+    EdgeIntersection intersection;
+    for (unsigned i = 0; i < overlappingEdges.size(); i++) {
+        const ExclusionPolygonEdge *edge = static_cast<ExclusionPolygonEdge*>(overlappingEdges[i].data());
+        float x1;
+        float x2;
+
+        if (edge->minY() < y1) {
+            computeXIntersection(edge, y1, intersection);
+            x1 = intersection.point.x();
+        } else
+            x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
+
+        if (edge->maxY() > y2) {
+            computeXIntersection(edge, y2, intersection);
+            x2 = intersection.point.x();
+        } else
+            x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
+
+        if (x1 > x2)
+            std::swap(x1, x2);
+
+        result.append(ExclusionInterval(x1, x2));
+    }
+
+    sortExclusionIntervals(result);
+}
+
+void ExclusionPolygon::getExcludedIntervals(float logicalTop, float logicalBottom, SegmentList& result) const
+{
+    float y1 = minYForLogicalLine(logicalTop, logicalBottom);
+    float y2 = maxYForLogicalLine(logicalTop, logicalBottom);
+
+    Vector<ExclusionInterval> y1XIntervals, y2XIntervals;
+    computeXIntersections(y1, y1XIntervals);
+    computeXIntersections(y2, y2XIntervals);
+
+    Vector<ExclusionInterval> mergedIntervals;
+    mergeExclusionIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
+
+    Vector<ExclusionInterval> edgeIntervals;
+    computeEdgeIntersections(y1, y2, edgeIntervals);
+
+    Vector<ExclusionInterval> excludedIntervals;
+    mergeExclusionIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
+
+    for (unsigned i = 0; i < excludedIntervals.size(); i++) {
+        ExclusionInterval interval = excludedIntervals[i];
+        result.append(LineSegment(interval.x1, interval.x2));
+    }
+}
+
+void ExclusionPolygon::getIncludedIntervals(float logicalTop, float logicalBottom, SegmentList& result) const
+{
+    float y1 = minYForLogicalLine(logicalTop, logicalBottom);
+    float y2 = maxYForLogicalLine(logicalTop, logicalBottom);
+
+    Vector<ExclusionInterval> y1XIntervals, y2XIntervals;
+    computeXIntersections(y1, y1XIntervals);
+    computeXIntersections(y2, y2XIntervals);
+
+    Vector<ExclusionInterval> commonIntervals;
+    intersectExclusionIntervals(y1XIntervals, y2XIntervals, commonIntervals);
+
+    Vector<ExclusionInterval> edgeIntervals;
+    computeEdgeIntersections(y1, y2, edgeIntervals);
+
+    Vector<ExclusionInterval> includedIntervals;
+    subtractExclusionIntervals(commonIntervals, edgeIntervals, includedIntervals);
+
+    for (unsigned i = 0; i < includedIntervals.size(); i++) {
+        ExclusionInterval interval = includedIntervals[i];
+        result.append(LineSegment(interval.x1, interval.x2));
+    }
+}
+
+} // namespace WebCore