Index: packages/path/lib/src/context.dart |
diff --git a/packages/path/lib/src/context.dart b/packages/path/lib/src/context.dart |
index db055a19b1a6ed54767ca40974d2aff6f8b93cb0..d10a29f148da84030400fb77cccfcdf4f7dcc431 100644 |
--- a/packages/path/lib/src/context.dart |
+++ b/packages/path/lib/src/context.dart |
@@ -4,6 +4,7 @@ |
library path.context; |
+import 'characters.dart' as chars; |
import 'internal_style.dart'; |
import 'style.dart'; |
import 'parsed_path.dart'; |
@@ -73,6 +74,15 @@ class Context { |
/// If [current] isn't absolute, this won't return an absolute path. |
String absolute(String part1, [String part2, String part3, String part4, |
String part5, String part6, String part7]) { |
+ _validateArgList( |
+ "absolute", [part1, part2, part3, part4, part5, part6, part7]); |
+ |
+ // If there's a single absolute path, just return it. This is a lot faster |
+ // for the common case of `p.absolute(path)`. |
+ if (part2 == null && isAbsolute(part1) && !isRootRelative(part1)) { |
+ return part1; |
+ } |
+ |
return join(current, part1, part2, part3, part4, part5, part6, part7); |
} |
@@ -295,11 +305,79 @@ class Context { |
/// |
/// context.normalize('path/./to/..//file.text'); // -> 'path/file.txt' |
String normalize(String path) { |
+ if (!_needsNormalization(path)) return path; |
+ |
var parsed = _parse(path); |
parsed.normalize(); |
return parsed.toString(); |
} |
+ /// Returns whether [path] needs to be normalized. |
+ bool _needsNormalization(String path) { |
+ var start = 0; |
+ var codeUnits = path.codeUnits; |
+ var previousPrevious; |
+ var previous; |
+ |
+ // Skip past the root before we start looking for snippets that need |
+ // normalization. We want to normalize "//", but not when it's part of |
+ // "http://". |
+ var root = style.rootLength(path); |
+ if (root != 0) { |
+ start = root; |
+ previous = chars.SLASH; |
+ |
+ // On Windows, the root still needs to be normalized if it contains a |
+ // forward slash. |
+ if (style == Style.windows) { |
+ for (var i = 0; i < root; i++) { |
+ if (codeUnits[i] == chars.SLASH) return true; |
+ } |
+ } |
+ } |
+ |
+ for (var i = start; i < codeUnits.length; i++) { |
+ var codeUnit = codeUnits[i]; |
+ if (style.isSeparator(codeUnit)) { |
+ // Forward slashes in Windows paths are normalized to backslashes. |
+ if (style == Style.windows && codeUnit == chars.SLASH) return true; |
+ |
+ // Multiple separators are normalized to single separators. |
+ if (previous != null && style.isSeparator(previous)) return true; |
+ |
+ // Single dots and double dots are normalized to directory traversals. |
+ // |
+ // This can return false positives for ".../", but that's unlikely |
+ // enough that it's probably not going to cause performance issues. |
+ if (previous == chars.PERIOD && |
+ (previousPrevious == null || |
+ previousPrevious == chars.PERIOD || |
+ style.isSeparator(previousPrevious))) { |
+ return true; |
+ } |
+ } |
+ |
+ previousPrevious = previous; |
+ previous = codeUnit; |
+ } |
+ |
+ // Empty paths are normalized to ".". |
+ if (previous == null) return true; |
+ |
+ // Trailing separators are removed. |
+ if (style.isSeparator(previous)) return true; |
+ |
+ // Single dots and double dots are normalized to directory traversals. |
+ if (previous == chars.PERIOD && |
+ (previousPrevious == null || |
+ previousPrevious == chars.SLASH || |
+ previousPrevious == chars.PERIOD)) { |
+ return true; |
+ } |
+ |
+ return false; |
+ } |
+ |
/// Attempts to convert [path] to an equivalent relative path relative to |
/// [root]. |
/// |
@@ -333,13 +411,10 @@ 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); |
- } |
+ // Avoid expensive computation if the path is already relative. |
+ if (from == null && this.isRelative(path)) return this.normalize(path); |
+ |
+ 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)) { |
@@ -425,6 +500,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); |
@@ -440,6 +540,259 @@ class Context { |
parts.first != '.'; |
} |
+ /// An optimized implementation of [isWithin] that doesn't handle a few |
+ /// complex cases. |
+ bool _isWithinFast(String parent, String child) { |
+ // 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 (parentCodeUnit == chars.PERIOD) { |
+ // If a dot comes after a separator, it may be a directory traversal |
+ // operator. To check that, we need to know if it's followed by either |
+ // "/" or "./". Otherwise, it's just a normal non-matching character. |
+ // |
+ // isWithin("foo/./bar", "foo/bar/baz") //=> true |
+ // isWithin("foo/bar/../baz", "foo/bar/.foo") //=> false |
+ if (style.isSeparator(lastCodeUnit)) { |
+ parentIndex++; |
+ |
+ // We've hit "/." at the end of the parent path, which we can ignore, |
+ // since the paths were equivalent up to this point. |
+ if (parentIndex == parent.length) break; |
+ parentCodeUnit = parentCodeUnits[parentIndex]; |
+ |
+ // We've hit "/./", which we can ignore. |
+ if (style.isSeparator(parentCodeUnit)) { |
+ parentIndex++; |
+ continue; |
+ } |
+ |
+ // We've hit "/..", which may be a directory traversal operator that |
+ // we can't handle on the fast track. |
+ if (parentCodeUnit == chars.PERIOD) { |
+ parentIndex++; |
+ if (parentIndex == parent.length || |
+ style.isSeparator(parentCodeUnits[parentIndex])) { |
+ return null; |
+ } |
+ } |
+ } |
+ |
+ // If this isn't a directory traversal, fall through so we hit the |
+ // normal handling for mismatched paths. |
+ } |
+ |
+ // This is the same logic as above, but for the child path instead of the |
+ // parent. |
+ if (childCodeUnit == chars.PERIOD) { |
+ if (style.isSeparator(lastCodeUnit)) { |
+ childIndex++; |
+ if (childIndex == child.length) break; |
+ childCodeUnit = childCodeUnits[childIndex]; |
+ |
+ if (style.isSeparator(childCodeUnit)) { |
+ childIndex++; |
+ continue; |
+ } |
+ |
+ if (childCodeUnit == chars.PERIOD) { |
+ childIndex++; |
+ if (childIndex == child.length || |
+ style.isSeparator(childCodeUnits[childIndex])) { |
+ 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]. |
+ var childDirection = _pathDirection(childCodeUnits, childIndex); |
+ if (childDirection != _PathDirection.belowRoot) return null; |
+ var parentDirection = _pathDirection(parentCodeUnits, parentIndex); |
+ if (parentDirection != _PathDirection.belowRoot) 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 direction = _pathDirection(parentCodeUnits, parentIndex); |
+ return direction == _PathDirection.aboveRoot ? 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 direction = _pathDirection(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 (direction == _PathDirection.atRoot) 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 (direction == _PathDirection.aboveRoot) 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 a [_PathDirection] describing the path represented by [codeUnits] |
+ // after [index]. |
+ // |
+ // This ignores leading separators. |
+ // |
+ // pathDirection("foo") //=> below root |
+ // pathDirection("foo/bar/../baz") //=> below root |
+ // pathDirection("//foo/bar/baz") //=> below root |
+ // pathDirection("/") //=> at root |
+ // pathDirection("foo/..") //=> at root |
+ // pathDirection("foo/../baz") //=> reaches root |
+ // pathDirection("foo/../..") //=> above root |
+ // pathDirection("foo/../../foo/bar/baz") //=> above root |
+ _PathDirection _pathDirection(List<int> codeUnits, int index) { |
+ var depth = 0; |
+ var reachedRoot = false; |
+ var i = index; |
+ while (i < codeUnits.length) { |
+ // Ignore initial separators or doubled separators. |
+ while (i < codeUnits.length && style.isSeparator(codeUnits[i])) { |
+ i++; |
+ } |
+ |
+ // If we're at the end, stop. |
+ if (i == codeUnits.length) break; |
+ |
+ // Move through the path component to the next separator. |
+ var start = i; |
+ while (i < codeUnits.length && !style.isSeparator(codeUnits[i])) { |
+ i++; |
+ } |
+ |
+ // 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 beyond the root, stop. |
+ if (depth < 0) break; |
+ |
+ // Record that we reached the root so we don't return |
+ // [_PathDirection.belowRoot]. |
+ if (depth == 0) reachedRoot = true; |
+ } else { |
+ // Step inside a directory. |
+ depth++; |
+ } |
+ |
+ // If we're at the end, stop. |
+ if (i == codeUnits.length) break; |
+ |
+ // Move past the separator. |
+ i++; |
+ } |
+ |
+ if (depth < 0) return _PathDirection.aboveRoot; |
+ if (depth == 0) return _PathDirection.atRoot; |
+ if (reachedRoot) return _PathDirection.reachesRoot; |
+ return _PathDirection.belowRoot; |
+ } |
+ |
/// Removes a trailing extension from the last part of [path]. |
/// |
/// context.withoutExtension('path/to/foo.dart'); // -> 'path/to/foo' |
@@ -572,3 +925,30 @@ _validateArgList(String method, List<String> args) { |
throw new ArgumentError(message.toString()); |
} |
} |
+ |
+/// An enum of possible return values for [Context._pathDirection]. |
+class _PathDirection { |
+ /// The path contains enough ".." components that at some point it reaches |
+ /// above its original root. |
+ /// |
+ /// Note that this applies even if the path ends beneath its original root. It |
+ /// takes precendence over any other return values that may apple. |
+ static const aboveRoot = const _PathDirection("above root"); |
+ |
+ /// The path contains enough ".." components that it ends at its original |
+ /// root. |
+ static const atRoot = const _PathDirection("at root"); |
+ |
+ /// The path contains enough ".." components that at some point it reaches its |
+ /// original root, but it ends beneath that root. |
+ static const reachesRoot = const _PathDirection("reaches root"); |
+ |
+ /// The path never reaches to or above its original root. |
+ static const belowRoot = const _PathDirection("below root"); |
+ |
+ final String name; |
+ |
+ const _PathDirection(this.name); |
+ |
+ String toString() => name; |
+} |