Support '..' in find emulation

This was our biggest source of fallbacks out of the find emulator on
AOSP -- the number of executed shell commands dropped from 53 to 29
after this change. There are only two fallbacks left after this, both
using globs in their finddirs (which turns out to be a much more
complicated change).

I'm seeing similar ratios on our flame (Pixel 4) builds in our internal
trees.

Test: build-aosp_crosshatch.ninja is the same on AOSP master before/after
Test: build-flame.ninja in our internal master is also the same
Change-Id: Ifb0e2e2c08b73726835f832f1461e557ed3c237f

4 files changed, 51 insertions, 13 deletions

diff --git a/find.cc b/find.cc
index a31adce..4e08da9 100644
--- a/find.cc
+++ b/find.cc
@@ -221,7 +221,8 @@ struct ScopedReadDirTracker {
 
 class DirentDirNode : public DirentNode {
  public:
-  explicit DirentDirNode(const string& name) : DirentNode(name) {}
+  explicit DirentDirNode(const DirentDirNode* parent, const string& name)
+      : DirentNode(name), parent_(parent) {}
 
   ~DirentDirNode() {
     for (auto& p : children_) {
@@ -232,11 +233,19 @@ class DirentDirNode : public DirentNode {
   virtual const DirentNode* FindDir(StringPiece d) const override {
     if (d.empty() || d == ".")
       return this;
+    if (d == "..")
+      return parent_;
+
     size_t index = d.find('/');
     const string& p = d.substr(0, index).as_string();
     if (p.empty() || p == ".")
       return FindDir(d.substr(index + 1));
-    ;
+    if (p == "..") {
+      if (parent_ == NULL)
+        return NULL;
+      return parent_->FindDir(d.substr(index + 1));
+    }
+
     for (auto& child : children_) {
       if (p == child.first) {
         if (index == string::npos)
@@ -341,6 +350,7 @@ class DirentDirNode : public DirentNode {
   }
 
  private:
+  const DirentDirNode* parent_;
   vector<pair<string, DirentNode*>> children_;
 };
 
@@ -776,8 +786,8 @@ class FindEmulatorImpl : public FindEmulator {
   virtual ~FindEmulatorImpl() = default;
 
   bool CanHandle(StringPiece s) const {
-    return (!HasPrefix(s, "../") && !HasPrefix(s, "/") &&
-            !HasPrefix(s, ".repo") && !HasPrefix(s, ".git"));
+    return (!HasPrefix(s, "/") && !HasPrefix(s, ".repo") &&
+            !HasPrefix(s, ".git"));
   }
 
   const DirentNode* FindDir(StringPiece d, bool* should_fallback) {
@@ -800,7 +810,7 @@ class FindEmulatorImpl : public FindEmulator {
 
     if (!is_initialized_) {
       ScopedTimeReporter tr("init find emulator time");
-      root_.reset(ConstructDirectoryTree(""));
+      root_.reset(ConstructDirectoryTree(NULL, ""));
       if (!root_) {
         ERROR("FindEmulator: Cannot open root directory");
       }
@@ -846,8 +856,9 @@ class FindEmulatorImpl : public FindEmulator {
 
     vector<string> results;
     for (const string& finddir : fc.finddirs) {
-      if (!CanHandle(finddir)) {
-        LOG("FindEmulator: Cannot handle find dir (%s): %s", finddir.c_str(),
+      string fullpath = ConcatDir(fc.chdir, finddir);
+      if (!CanHandle(fullpath)) {
+        LOG("FindEmulator: Cannot handle find dir (%s): %s", fullpath.c_str(),
             cmd.c_str());
         return false;
       }
@@ -855,7 +866,7 @@ class FindEmulatorImpl : public FindEmulator {
       const DirentNode* base;
       base = root->FindDir(finddir);
       if (!base) {
-        if (Exists(finddir)) {
+        if (Exists(fullpath)) {
           return false;
         }
         if (!fc.redirect_to_devnull) {
@@ -925,7 +936,8 @@ class FindEmulatorImpl : public FindEmulator {
     return GetDtTypeFromStat(st);
   }
 
-  DirentNode* ConstructDirectoryTree(const string& path) {
+  DirentNode* ConstructDirectoryTree(DirentDirNode* parent,
+                                     const string& path) {
     DIR* dir = opendir(path.empty() ? "." : path.c_str());
     if (!dir) {
       if (errno == ENOENT || errno == EACCES) {
@@ -936,7 +948,7 @@ class FindEmulatorImpl : public FindEmulator {
       }
     }
 
-    DirentDirNode* n = new DirentDirNode(path);
+    DirentDirNode* n = new DirentDirNode(parent, path);
 
     struct dirent* ent;
     while ((ent = readdir(dir)) != NULL) {
@@ -956,7 +968,7 @@ class FindEmulatorImpl : public FindEmulator {
         CHECK(d_type != DT_UNKNOWN);
       }
       if (d_type == DT_DIR) {
-        c = ConstructDirectoryTree(npath);
+        c = ConstructDirectoryTree(n, npath);
         if (c == NULL) {
           continue;
         }
@@ -1012,7 +1024,7 @@ class FindEmulatorImpl : public FindEmulator {
 
       if (type == DT_DIR) {
         if (path.find('/') == string::npos) {
-          DirentNode* dir = ConstructDirectoryTree(path);
+          DirentNode* dir = ConstructDirectoryTree(NULL, path);
           if (dir != NULL) {
             s->set_to(dir);
           } else {
diff --git a/find_test.cc b/find_test.cc
index aefe38b..8928bbf 100644
--- a/find_test.cc
+++ b/find_test.cc
@@ -131,6 +131,7 @@ int FindUnitTests() {
   //  drwxr-x--- top
   //  lrwxrwxrwx top/E -> missing
   //  lrwxrwxrwx top/C -> A
+  //  lrwxrwxrwx top/F -> A/B
   //  -rw-r----- top/a
   //  drwxr-x--- top/A
   //  lrwxrwxrwx top/A/D -> B
@@ -141,6 +142,7 @@ int FindUnitTests() {
   Run("cd top && ln -s A C");
   Run("cd top/A && ln -s B D");
   Run("cd top && ln -s missing E");
+  Run("cd top && ln -s A/B F");
   Run("touch top/a top/A/b top/A/B/z");
 
   InitFindEmulator();
@@ -165,6 +167,17 @@ int FindUnitTests() {
   CompareFind("find top \\! -name 'a*'");
   CompareFind("find top \\( -name 'a*' \\)");
 
+  // Basic use of ..
+  CompareFind("cd top/C; find ../A");
+
+  // Use of .. in chdir
+  CompareFind("cd top/A/..; find .");
+
+  // .. through a symlink in chdir, should list under top/A/...
+  CompareFind("cd top/F; find ../");
+  // .. through a symlink in finddir, should do the same
+  CompareFind("cd top; find F/..");
+
   ExpectParseFailure("find top -name a\\*");
 
   return unit_test_failed ? 1 : 0;
diff --git a/strutil.cc b/strutil.cc
index a585963..797775f 100644
--- a/strutil.cc
+++ b/strutil.cc
@@ -494,7 +494,7 @@ string SortWordsInString(StringPiece s) {
 
 string ConcatDir(StringPiece b, StringPiece n) {
   string r;
-  if (!b.empty()) {
+  if (!b.empty() && (n.empty() || n[0] != '/')) {
     b.AppendToString(&r);
     r += '/';
   }
diff --git a/strutil_test.cc b/strutil_test.cc
index e83b4c3..d0db1f3 100644
--- a/strutil_test.cc
+++ b/strutil_test.cc
@@ -198,6 +198,18 @@ void TestFindEndOfLineInvalidAccess() {
   ASSERT_EQ(FindEndOfLine(CreateProtectedString("a\\"), 0, &lf_cnt), 2);
 }
 
+void TestConcatDir() {
+  ASSERT_EQ(ConcatDir("", ""), "");
+  ASSERT_EQ(ConcatDir(".", ""), "");
+  ASSERT_EQ(ConcatDir("", "."), "");
+  ASSERT_EQ(ConcatDir("a", "b"), "a/b");
+  ASSERT_EQ(ConcatDir("a/", "b"), "a/b");
+  ASSERT_EQ(ConcatDir("a", "/b"), "/b");
+  ASSERT_EQ(ConcatDir("a", ".."), "");
+  ASSERT_EQ(ConcatDir("a", "../b"), "b");
+  ASSERT_EQ(ConcatDir("a", "../../b"), "../b");
+}
+
 }  // namespace
 
 int main() {
@@ -214,5 +226,6 @@ int main() {
   TestFindEndOfLine();
   TestWordScannerInvalidAccess();
   TestFindEndOfLineInvalidAccess();
+  TestConcatDir();
   assert(!g_failed);
 }