From 029b5ef0b8004f659078329cbbd3f2827a60c4de Mon Sep 17 00:00:00 2001 From: Dan Willemsen Date: Tue, 7 Apr 2020 12:07:50 -0700 Subject: 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 --- find.cc | 36 ++++++++++++++++++++++++------------ find_test.cc | 13 +++++++++++++ strutil.cc | 2 +- strutil_test.cc | 13 +++++++++++++ 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> 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 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); } -- cgit v1.2.3