[SVG] Fix infinite curveLength() loop.

Source/platform/graphics/PathTraversalState.cpp

Index: Source/platform/graphics/PathTraversalState.cpp
diff --git a/Source/platform/graphics/PathTraversalState.cpp b/Source/platform/graphics/PathTraversalState.cpp
index 406c5b180cd6a38866b28e5882f423e23e7270ef..7dba594f612262857baca8465d170bedd9072354 100644
--- a/Source/platform/graphics/PathTraversalState.cpp
+++ b/Source/platform/graphics/PathTraversalState.cpp
@@ -51,7 +51,14 @@ struct QuadraticBezier {
         return distanceLine(start, control) + distanceLine(control, end);
     }
 
-    void split(QuadraticBezier& left, QuadraticBezier& right) const
+    bool equals(const QuadraticBezier& other) const
+    {
+        return start == other.start
+            && end == other.end
+            && control == other.control;
+    }
+
+    bool split(QuadraticBezier& left, QuadraticBezier& right) const
     {
         left.control = midPoint(start, control);
         right.control = midPoint(control, end);
@@ -62,6 +69,8 @@ struct QuadraticBezier {
 
         left.start = start;
         right.end = end;
+
+        return !equals(left) && !equals(right);
     }
 
     FloatPoint start;
@@ -84,7 +93,15 @@ struct CubicBezier {
         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
     }
 
-    void split(CubicBezier& left, CubicBezier& right) const
+    bool equals(const CubicBezier& other) const
+    {
+        return start == other.start
+            && end == other.end
+            && control1 == other.control1
+            && control2 == other.control2;
+    }
+
+    bool split(CubicBezier& left, CubicBezier& right) const
     {
         FloatPoint startToControl1 = midPoint(control1, control2);
 
@@ -99,6 +116,8 @@ struct CubicBezier {
         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
         left.end = leftControl2ToRightControl1;
         right.start = leftControl2ToRightControl1;
+
+        return !equals(left) && !equals(right);
     }
 
     FloatPoint start;
@@ -122,12 +141,12 @@ static float curveLength(PathTraversalState& traversalState, CurveType curve)
     curveStack.append(curve);
 
     float totalLength = 0;
+    CurveType leftCurve, rightCurve;
     do {
         float length = curve.approximateDistance();
-        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance && curveStack.size() <= curveStackDepthLimit) {
-            CurveType leftCurve;
-            CurveType rightCurve;
-            curve.split(leftCurve, rightCurve);
+        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance

[Stephen Chennney, 2014/03/07 16:25:31]

The real problem is that tolerance is a fixed value that fails to account for
the scale of the values. You should compare fabs(((length -
distanceLine(...))/length) > kPathSegLengthTolerance. You might even be able to
adjust kPathSegLengthTolerance in that case to a higher value. 0.001 bounds your
error to 0.1%.

[f(malita), 2014/03/07 18:02:26]

I disagree: the immediate problem is that the algorithm gets stuck trying to
split curves and not making any progress. We can detect and avoid this condition
easily.

Now maybe (**) the updated tolerance test you suggest guarantees a significant
split, but it's not obvious and I would much rather have a direct check for that
condition instead of relying on inference subject to numerical stability issues.

(**) Turns out it doesn't: the issue repro still gets stuck, even with a
tolerance increased to 1%.

It's probably still a good idea to update the tolerance test (although I think
we can assert length >= distanceLine and skip fabs), but not as a replacement
for the split test. What do you think?

[f(malita), 2014/03/07 19:14:08]

Come to think of it, it's obvious this would not work as a fix: for very small
curve segments (length << 1) this is *increasing* the metric value and making us
try to split even further than before.

Case in point: splitting falls apart for [(786.879395,346.877930)
(786.879395,346.877930) (786.879395,346.877899) (786.879456,346.877899)]

because (346.877930f + 346.877899f) / 2 == 346.877930f.

We're hitting this numerical precision wall for an original metric value (length
- distanceLine(curve.start, curve.end)) of 0.000023. When switching to a metric
of fabs((length - distanceLine(curve.start, curve.end)) / length), we're going
to hit this at a much higher value: 0.254644 <- if anything, we've made things
(much) worse.

+            && curveStack.size() <= curveStackDepthLimit
+            && curve.split(leftCurve, rightCurve)) {
             curve = leftCurve;
             curveStack.append(rightCurve);
         } else {