Improve the performance of isWithin().

lib/src/context.dart

Index: lib/src/context.dart
diff --git a/lib/src/context.dart b/lib/src/context.dart
index 44bdde994ea46daec0052052e8aaea4bc176be2e..891e3fbd63d8f75a0d0c3dab9e6923a53699a1a4 100644
--- a/lib/src/context.dart
+++ b/lib/src/context.dart
@@ -411,13 +411,7 @@ class Context {
   /// "/", no path can be determined. In this case, a [PathException] will be
   /// thrown.
   String relative(String path, {String from}) {
-    // Avoid calling [current] since it is slow and calling join() when
-    // [from] is absolute does nothing.
-    if (from == null) {
-      from = current;
-    } else if (this.isRelative(from) || this.isRootRelative(from)) {
-      from = this.join(current, from);
-    }
+    from = from == null ? current : absolute(from);
 
     // We can't determine the path from a relative path to an absolute path.
     if (this.isRelative(from) && this.isAbsolute(path)) {
@@ -503,6 +497,31 @@ class Context {
   ///     path.isWithin('/root/path', '/root/other'); // -> false
   ///     path.isWithin('/root/path', '/root/path'); // -> false
   bool isWithin(String parent, String child) {
+    // Make both paths the same level of relative. We're only able to do the
+    // quick comparison if both paths are in the same format, and making a path
+    // absolute is faster than making it relative.
+    var parentIsAbsolute = isAbsolute(parent);
+    var childIsAbsolute = isAbsolute(child);
+    if (parentIsAbsolute && !childIsAbsolute) {
+      child = absolute(child);
+      if (style.isRootRelative(parent)) parent = absolute(parent);
+    } else if (childIsAbsolute && !parentIsAbsolute) {
+      parent = absolute(parent);
+      if (style.isRootRelative(child)) child = absolute(child);
+    } else if (childIsAbsolute && parentIsAbsolute) {
+      var childIsRootRelative = style.isRootRelative(child);
+      var parentIsRootRelative = style.isRootRelative(parent);
+
+      if (childIsRootRelative && !parentIsRootRelative) {
+        child = absolute(child);
+      } else if (parentIsRootRelative && !childIsRootRelative) {
+        parent = absolute(parent);
+      }
+    }
+
+    var fastResult = _isWithinFast(parent, child);
+    if (fastResult != null) return fastResult;
+
     var relative;
     try {
       relative = this.relative(child, from: parent);
@@ -518,6 +537,228 @@ class Context {
         parts.first != '.';
   }
 
+  /// An optimized implementation of [isWithin] that doesn't handle a few
+  /// complex cases.
+  bool _isWithinFast(String parent, String child) {

[Bob Nystrom, 2015/11/24 17:22:13]

Possibly dumb question. How much mileage would we get out of:

bool _isWithinReallFast(String parent, String child) {
  // Child path literally contain the parent.
  if (!child.startsWith(parent)) return null;

  // And not possibly walk back out of the parent.
  if (child.contains("..", parent.length)) return null;

  return true;
}

Are there cases where that gives a false positive? If not, I think this will hit
the very common case with things like Directory.list() where your paths all do
have the same prefix.

[nweiz, 2015/12/01 00:15:15]

That gives a false positive for isWithin("/foo/bar", "/foo/barbaz"). It's also a
lot slower than this implementation, despite its simplicity; the big cost is
iterating through the string, and your implementation does it twice instead of
once when it returns "true".

+    // Normally we just bail when we see "." path components, but we can handle
+    // a single dot easily enough.
+    if (parent == '.') parent = '';
+
+    var parentRootLength = style.rootLength(parent);
+    var childRootLength = style.rootLength(child);
+
+    // If the roots aren't the same length, we know both paths are absolute or
+    // both are root-relative, and thus that the roots are meaningfully
+    // different.
+    //
+    //     isWithin("C:/bar", "//foo/bar/baz") //=> false
+    //     isWithin("http://example.com/", "http://google.com/bar") //=> false
+    if (parentRootLength != childRootLength) return false;
+
+    var parentCodeUnits = parent.codeUnits;
+    var childCodeUnits = child.codeUnits;
+
+    // Make sure that the roots are textually the same as well.
+    //
+    //     isWithin("C:/bar", "D:/bar/baz") //=> false
+    //     isWithin("http://example.com/", "http://example.org/bar") //=> false
+    for (var i = 0; i < parentRootLength; i++) {
+      var parentCodeUnit = parentCodeUnits[i];
+      var childCodeUnit = childCodeUnits[i];
+      if (parentCodeUnit == childCodeUnit) continue;
+
+      // If both code units are separators, that's fine too.
+      //
+      //     isWithin("C:/", r"C:\foo") //=> true
+      if (!style.isSeparator(parentCodeUnit) ||
+          !style.isSeparator(childCodeUnit)) {
+        return false;
+      }
+    }
+
+    // Start by considering the last code unit as a separator, since
+    // semantically we're starting at a new path component even if we're
+    // comparing relative paths.
+    var lastCodeUnit = chars.SLASH;
+
+    // Iterate through both paths as long as they're semantically identical.
+    var parentIndex = parentRootLength;
+    var childIndex = childRootLength;
+    while (parentIndex < parent.length && childIndex < child.length) {
+      var parentCodeUnit = parentCodeUnits[parentIndex];
+      var childCodeUnit = childCodeUnits[childIndex];
+      if (parentCodeUnit == childCodeUnit) {
+        lastCodeUnit = parentCodeUnit;
+        parentIndex++;
+        childIndex++;
+        continue;
+      }
+
+      // Different separators are considered identical.
+      var parentIsSeparator = style.isSeparator(parentCodeUnit);
+      var childIsSeparator = style.isSeparator(childCodeUnit);
+      if (parentIsSeparator && childIsSeparator) {
+        lastCodeUnit = parentCodeUnit;
+        parentIndex++;
+        childIndex++;
+        continue;
+      }
+
+      // Ignore multiple separators in a row.
+      if (parentIsSeparator && style.isSeparator(lastCodeUnit)) {
+        parentIndex++;
+        continue;
+      } else if (childIsSeparator && style.isSeparator(lastCodeUnit)) {
+        childIndex++;
+        continue;
+      }
+
+      // If a dot comes after a separator or another dot, it may be a
+      // directory traversal operator. Otherwise, it's just a normal
+      // non-matching character.
+      //
+      //     isWithin("foo/./bar", "foo/bar/baz") //=> true
+      //     isWithin("foo/bar/../baz", "foo/bar/.foo") //=> false
+      //
+      // We could stay on the fast path for "/./", but that adds a lot of
+      // complexity and isn't likely to come up much in practice.
+      if ((parentCodeUnit == chars.PERIOD || childCodeUnit == chars.PERIOD) &&
+          (style.isSeparator(lastCodeUnit) || lastCodeUnit == chars.PERIOD)) {
+        return null;
+      }
+
+      // If we're here, we've hit two non-matching, non-significant characters.
+      // As long as the remainders of the two paths don't have any unresolved
+      // ".." components, we can be confident that [child] is not within
+      // [parent].
+      if (_checkRemainder(childCodeUnits, childIndex) < 1) return null;
+      if (_checkRemainder(parentCodeUnits, parentIndex) < 1) return null;
+      return false;
+    }
+
+    // If the child is shorter than the parent, it's probably not within the
+    // parent. The only exception is if the parent has some weird ".." stuff
+    // going on, in which case we do the slow check.
+    //
+    //     isWithin("foo/bar/baz", "foo/bar") //=> false
+    //     isWithin("foo/bar/baz/../..", "foo/bar") //=> true
+    if (childIndex == child.length) {
+      var result = _checkRemainder(parentCodeUnits, parentIndex);
+      return result < 0 ? null : false;
+    }
+
+    // We've reached the end of the parent path, which means it's time to make a
+    // decision. Before we do, though, we'll check the rest of the child to see
+    // what that tells us.
+    var result = _checkRemainder(childCodeUnits, childIndex);
+
+    // If there are no more components in the child, then it's the same as
+    // the parent, not within it.
+    //
+    //     isWithin("foo/bar", "foo/bar") //=> false
+    //     isWithin("foo/bar", "foo/bar//") //=> false
+    if (result == 0) return false;
+
+    // If there are unresolved ".." components in the child, no decision we make
+    // will be valid. We'll abort and do the slow check instead.
+    //
+    //     isWithin("foo/bar", "foo/bar/..") //=> false
+    //     isWithin("foo/bar", "foo/bar/baz/bang/../../..") //=> false
+    //     isWithin("foo/bar", "foo/bar/baz/bang/../../../bar/baz") //=> true
+    if (result < 0) return null;
+
+    // The child is within the parent if and only if we're on a separator
+    // boundary.
+    //
+    //     isWithin("foo/bar", "foo/bar/baz") //=> true
+    //     isWithin("foo/bar/", "foo/bar/baz") //=> true
+    //     isWithin("foo/bar", "foo/barbaz") //=> false
+    return style.isSeparator(childCodeUnits[childIndex]) ||
+        style.isSeparator(lastCodeUnit);
+  }
+
+  // Returns the information about the path represented by [codeUnits] after
+  // [index].
+  //
+  // Specifically, this returns:
+  //
+  // * A negative number if the path contains ".." components that at any point
+  //   cause the directory to go above the root.
+  //
+  // * Zero if the path has no components, or if it contains ".." that at any
+  //   point cause the directory to go back to the root (but not above it).
+  //
+  // * A positive number otherwise.
+  //
+  // This ignores leading separators.
+  //
+  //     checkRemainder("foo") //=> +
+  //     checkRemainder("foo/bar/../baz") //=> +
+  //     checkRemainder("//foo/bar/baz") //=> +
+  //     checkRemainder("/") //=> 0
+  //     checkRemainder("foo/../baz") //=> 0
+  //     checkRemainder("foo/../..") //=> -
+  //     checkRemainder("foo/../../foo/bar/baz") //=> -
+  int _checkRemainder(List<int> codeUnits, int index) {

[Bob Nystrom, 2015/11/24 17:22:13]

How about _pathDirection()? Something other than "check", which is vague, would
be nice.

[nweiz, 2015/12/01 00:15:15]

Done.

+    var depth = 0;
+
+    // We initially consider ourselves to be after an invisible root separator.
+    var afterSeparator = true;
+    for (var i = index; i < codeUnits.length; i++) {
+      var codeUnit = codeUnits[i];
+
+      if (style.isSeparator(codeUnit)) {
+        // Ignore doubled separators (and initial separators).
+        if (!afterSeparator) depth++;
+        afterSeparator = true;
+        continue;
+      }
+
+      // Ignore non-meaningful characters.
+      if (codeUnit != chars.PERIOD || !afterSeparator) {
+        afterSeparator = false;
+        continue;
+      }
+
+      // Move forward so we're positioned after "/.".
+      i++;
+
+      if (i == codeUnits.length) return depth;
+      codeUnit = codeUnits[i];
+
+      // Ignore "/./", and don't increment the depth for the trailing slash.
+      if (style.isSeparator(codeUnit)) continue;
+
+      // "/.foo" isn't anything meaningful.
+      if (codeUnit != chars.PERIOD) {
+        afterSeparator = false;
+        continue;
+      }
+
+      // Move forward again so we're positioned after "/..".
+      i++;
+
+      if (i == codeUnits.length) return depth - 1;
+      codeUnit = codeUnits[i];
+
+      // "/../" decreases depth.
+      if (style.isSeparator(codeUnit)) {
+        depth--;
+        if (depth == 0) return 0;
+        if (depth < 0) return depth;
+        continue;
+      }
+
+      // "/..foo" isn't anything meaningful.
+      afterSeparator = false;
+    }

[Bob Nystrom, 2015/11/24 17:22:13]

Instead of a for loop with a sort of state machine approach to track what you've
read, I think it may be clearer to write this more like an eager lexer that
matches and advances. Something like:

    var i = index;
    while (i < codeUnits.length) {
      // Read the next path component.
      var start = i;
      while (i < codeUnits.length && !style.isSeparator(codeUnits[i])) {
        i++;
      }

      // If we're at the end, stop.
      if (i == codeUnits.length) break;

      // See if the path component is ".", "..", or a name.
      if (i - start == 1 && codeUnits[start] == chars.PERIOD) {
        // Don't change the depth.
      } else if (i - start == 2 &&
          codeUnits[start] == chars.PERIOD &&
          codeUnits[start + 1] == chars.PERIOD) {
        // ".." backs out a directory.
        depth--;

        // If we work back to the root, stop.
        if (depth <= 0) break;
      } else {
        // Step inside a directory.
        depth++;
      }

      // Ignore doubled separators.
      while (i < codeUnits.length && style.isSeparator(codeUnits[i])) {
        i++;
      }
    }

    return depth;

(I haven't tested this at all.)

What do you think?

[nweiz, 2015/12/01 00:15:15]

Done. I also realized that there were some bugs in my logic where this was being
called, so I changed it to return a four-state enum.

+
+    // If the path didn't have a trailing separator, add another unit of depth
+    // to account for the current component. We have to do this because depth is counted

[Bob Nystrom, 2015/11/24 17:22:13]

Long line.

[nweiz, 2015/12/01 00:15:15]

Acknowledged.

+    // on each trailing separator.
+    return afterSeparator ? depth : depth + 1;
+  }
+
   /// Removes a trailing extension from the last part of [path].
   ///
   ///     context.withoutExtension('path/to/foo.dart'); // -> 'path/to/foo'