Handle overflow, underflow in XPath substring position, length.

third_party/WebKit/Source/core/xml/XPathFunctions.cpp

Index: third_party/WebKit/Source/core/xml/XPathFunctions.cpp
diff --git a/third_party/WebKit/Source/core/xml/XPathFunctions.cpp b/third_party/WebKit/Source/core/xml/XPathFunctions.cpp
index 8fe6c2a563024496d1667ab559ea5a7ff1642203..3daff8125fceb66d020dbdfe64c0083e6c747506 100644
--- a/third_party/WebKit/Source/core/xml/XPathFunctions.cpp
+++ b/third_party/WebKit/Source/core/xml/XPathFunctions.cpp
@@ -37,6 +37,8 @@
 #include "wtf/MathExtras.h"
 #include "wtf/text/StringBuilder.h"
 
+#include <limits>
+
 namespace blink {
 namespace XPath {
 
@@ -530,34 +532,50 @@ Value FunSubstringAfter::evaluate(EvaluationContext& context) const {
   return s1.substring(i + s2.length());
 }
 
-Value FunSubstring::evaluate(EvaluationContext& context) const {
-  String s = arg(0)->evaluate(context).toString();
-  double doublePos = arg(1)->evaluate(context).toNumber();
-  if (std::isnan(doublePos))
-    return "";
-  long pos = static_cast<long>(FunRound::round(doublePos));
-  bool haveLength = argCount() == 3;
-  long len = -1;
-  if (haveLength) {
-    double doubleLen = arg(2)->evaluate(context).toNumber();
-    if (std::isnan(doubleLen))
-      return "";
-    len = static_cast<long>(FunRound::round(doubleLen));
+static unsigned findSubstringStartIndex(unsigned lo, unsigned hi, double pos) {
+  while (lo != hi) {
+    unsigned mid = lo + (hi - lo) / 2;
+    if (mid >= pos)
+      hi = mid;
+    else
+      lo = mid + 1;

[yosin_UTC9, 2016/10/17 03:56:00]

Note: When |pos| is NaN, |mid >= pos| is false. So, this clause is executed.
findSubstringStartIndex(1, 2, NaN) => 2

[dominicc (has gone to gerrit), 2016/10/21 05:28:45]

What's wrong with that?

[yosin_UTC9, 2016/10/21 05:52:03]

Sorry for confusion. This is my notes.

   }
-
-  if (pos > long(s.length()))
-    return "";
-
-  if (pos < 1) {
-    if (haveLength) {
-      len -= 1 - pos;
-      if (len < 1)
-        return "";
-    }
-    pos = 1;
+  return lo;
+}
+
+// This function may seem redundant given findSubstringStartIndex, but
+// it is different. substring's bounds calculations are designed to
+// work with NaN, and mid >= pos is different to !(mid < pos) when pos
+// is NaN.
+static unsigned findSubstringEndIndex(unsigned lo, unsigned hi, double pos) {
+  while (lo != hi) {
+    unsigned mid = lo + (hi - lo) / 2;
+    if (mid < pos)
+      lo = mid + 1;
+    else
+      hi = mid;
   }
+  return lo;
+}
 
-  return s.substring(pos - 1, len);
+// substring(string, number pos, number? len)
+//
+// Characters in string are indexed from 1. Numbers are doubles and
+// substring is specified to work with IEEE-754 infinity, NaN, and
+// XPath's bespoke rounding function, round.
+//
+// <https://www.w3.org/TR/xpath/#function-substring>
+Value FunSubstring::evaluate(EvaluationContext& context) const {
+  String s = arg(0)->evaluate(context).toString();

[yosin_UTC9, 2016/10/17 03:56:00]

nit: It is better to avoid using one letter variable name.

+  double pos = FunRound::round(arg(1)->evaluate(context).toNumber());
+  double len = argCount() == 3
+                   ? FunRound::round(arg(2)->evaluate(context).toNumber())
+                   : std::numeric_limits<double>::infinity();
+  unsigned start = findSubstringStartIndex(1, s.length() + 1, pos);

[yosin_UTC9, 2016/10/17 03:56:00]

WDYT? Explicit handling of NaN and Infinity?
In this way, we don't need to remember result of numeric comparison with NaN,
e.g. 1 > NaN, 2 < NaN, Inifity < NaN,

// |pos| and |len| can be NaN, +Inifity/-Infinity
// |length| should be a finite number.
std::pair<double, dobule> computeStartEnd(pos, len, length) {
  DCHECK(std::isfinite(length)) << length;
  const double posend = pos + len;
  if (std::isnnan(pos) && std::isnan(posend))
    return std::make_pair(1, 1);
  if (std::isnan(pos))
    return std::make_pair(1, std::max(1, std::min(posend, length));
  if (std::isnan(posend))
    return std::make_pair(1, 1);
  return std::make_pair(std::min(std::max(1, pos), length);
}

[dominicc (has gone to gerrit), 2016/10/21 05:28:45]

I don't think this works. If pos is -inf and end is inf, then XPath says you
should return the whole string but you will return the empty string.

I've written the version that handles these cases explicitly. It's very complex.
Searching for the bounds is simpler. The spec is defined in terms of < and >= so
the implementation which searches is in some sense more direct.

[yosin_UTC9, 2016/10/21 05:52:03]

OK. Simpler code is better.

+  unsigned end = findSubstringEndIndex(1, s.length() + 1, pos + len);
+  if (end <= start)
+    return "";
+  return s.substring(start - 1, end - start);
 }
 
 Value FunStringLength::evaluate(EvaluationContext& context) const {