semantic change: allow reaching into parent directories in paths

This allows generating build files in a subdirectory of your source tree.
- Change CanonicalizePath to accept this.
- CanonicalizePath no longer has an error condition, so change it to a void
  function.

I profiled the result against Chrome and it might be ~100ms slower, but that
might just be Chrome's size working against me.  In any case I think there
are lower-hanging performance fruit elsewhere.

1 files changed, 42 insertions, 72 deletions

diff --git a/src/util.cc b/src/util.cc
index d5a8f1f..0ad470e 100644
--- a/src/util.cc
+++ b/src/util.cc
@@ -64,92 +64,62 @@ void Error(const char* msg, ...) {
   fprintf(stderr, "\n");
 }
 
-bool CanonicalizePath(string* path, string* err) {
+void CanonicalizePath(string* path) {
   // WARNING: this function is performance-critical; please benchmark
   // any changes you make to it.
 
-  // We don't want to allocate memory if necessary; a previous version
-  // of this function modified |path| as it went, which meant we
-  // needed to keep a copy of it around for including in a potential
-  // error message.
-  //
-  // Instead, we find all path components within the path, then fix
-  // them up to eliminate "foo/.." pairs and "." components.  Finally,
-  // we overwrite path with these new substrings (since the path only
-  // ever gets shorter, we can just use memmove within it).
-
   const int kMaxPathComponents = 30;
-  const char* starts[kMaxPathComponents];  // Starts of path components.
-  int lens[kMaxPathComponents];  // Lengths of path components.
-
-  int parts_count = 0;  // Number of entries in starts/lens.
-  int slash_count = 0;  // Number of components in the original path.
-  for (string::size_type start = 0; start < path->size(); ++start) {
-    string::size_type end = path->find('/', start);
-    if (end == string::npos)
-      end = path->size();
-    if (end == 0 || end > start) {
-      if (parts_count == kMaxPathComponents) {
-        *err = "can't canonicalize path '" + *path + "'; too many "
-            "path components";
-        return false;
-      }
-      starts[parts_count] = path->data() + start;
-      lens[parts_count] = end - start;
-      ++parts_count;
-    }
-    ++slash_count;
-    start = end;
+  char* components[kMaxPathComponents];
+  int component_count = 0;
+
+  char* start = &(*path)[0];
+  char* dst = start;
+  const char* src = start;
+  const char* end = start + path->size();
+
+  if (*src == '/') {
+    ++src;
+    ++dst;
   }
 
-  int i = 0;
-  while (i < parts_count) {
-    const char* start = starts[i];
-    int len = lens[i];
-    if (start[0] == '.') {
-      int strip_components = 0;
-      if (len == 1) {
-        // "."; strip this component.
-        strip_components = 1;
-      } else if (len == 2 && start[1] == '.') {
-        // ".."; strip this and the previous component.
-        if (i == 0) {
-          *err = "can't canonicalize path '" + *path + "' that reaches "
-            "above its directory";
-          return false;
-        }
-        strip_components = 2;
-        --i;
-      }
+  while (src < end) {
+    const char* sep = (const char*)memchr(src, '/', end - src);
+    if (sep == NULL)
+      sep = end;
 
-      if (strip_components) {
-        // Shift arrays backwards to remove bad path components.
-        int entries_to_move = parts_count - i - strip_components;
-        memmove(starts + i, starts + i + strip_components,
-                sizeof(starts[0]) * entries_to_move);
-        memmove(lens + i, lens + i + strip_components,
-                sizeof(lens[0]) * entries_to_move);
-        parts_count -= strip_components;
+    if (*src == '.') {
+      if (sep - src == 1) {
+        // '.' component; eliminate.
+        src += 2;
+        continue;
+      } else if (sep - src == 2 && src[1] == '.') {
+        // '..' component.  Back up if possible.
+        if (component_count > 0) {
+          dst = components[component_count - 1];
+          src += 3;
+          --component_count;
+        } else {
+          while (src <= sep)
+            *dst++ = *src++;
+        }
         continue;
       }
     }
-    ++i;
-  }
 
-  if (parts_count == slash_count)
-    return true;  // Nothing to do.
+    if (sep > src) {
+      if (component_count == kMaxPathComponents)
+        Fatal("path has too many components");
+      components[component_count] = dst;
+      ++component_count;
+      while (src <= sep) {
+        *dst++ = *src++;
+      }
+    }
 
-  char* p = (char*)path->data();
-  for (i = 0; i < parts_count; ++i) {
-    if (p > path->data())
-      *p++ = '/';
-    int len = lens[i];
-    memmove(p, starts[i], len);
-    p += len;
+    src = sep + 1;
   }
-  path->resize(p - path->data());
 
-  return true;
+  path->resize(dst - path->c_str() - 1);
 }
 
 int MakeDir(const string& path) {