Handle overflow, underflow in XPath substring position, length.

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

 /*
  * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
  * Copyright (C) 2006, 2009 Apple Inc.
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  *
  * 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
@@ skipping 19 matching lines @@
 #include "core/XMLNames.h"
 #include "core/dom/Attr.h"
 #include "core/dom/Element.h"
 #include "core/dom/ProcessingInstruction.h"
 #include "core/dom/TreeScope.h"
 #include "core/xml/XPathUtil.h"
 #include "core/xml/XPathValue.h"
 #include "wtf/MathExtras.h"
 #include "wtf/text/StringBuilder.h"
 
+#include <limits>
+
 namespace blink {
 namespace XPath {
 
 static inline bool isWhitespace(UChar c) {
   return c == ' ' || c == '\n' || c == '\r' || c == '\t';
 }
 
 #define DEFINE_FUNCTION_CREATOR(Class) \
   static Function* create##Class() { return new Class; }
 
@@ skipping 473 matching lines @@
   String s1 = arg(0)->evaluate(context).toString();
   String s2 = arg(1)->evaluate(context).toString();
 
   size_t i = s1.find(s2);
   if (i == kNotFound)
     return "";
 
   return s1.substring(i + s2.length());
 }
 
+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.

+  }
+  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;
+}
+
+// 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 doublePos = arg(1)->evaluate(context).toNumber();
-  if (std::isnan(doublePos))
+  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 "";
-  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));
-  }
-
-  if (pos > long(s.length()))
-    return "";
-
-  if (pos < 1) {
-    if (haveLength) {
-      len -= 1 - pos;
-      if (len < 1)
-        return "";
-    }
-    pos = 1;
-  }
-
-  return s.substring(pos - 1, len);
+  return s.substring(start - 1, end - start);
 }
 
 Value FunStringLength::evaluate(EvaluationContext& context) const {
   if (!argCount())
     return Value(context.node.get()).toString().length();
   return arg(0)->evaluate(context).toString().length();
 }
 
 Value FunNormalizeSpace::evaluate(EvaluationContext& context) const {
   if (!argCount()) {
@@ skipping 179 matching lines @@
     return nullptr;
 
   Function* function = functionRec->factoryFn();
   function->setArguments(args);
   function->setName(name);
   return function;
 }
 
 }  // namespace XPath
 }  // namespace blink