Optimize findleaves regen check

If we've found all possible files in a leaf directory, we don't need to
re-run findleaves every time the leaf directory's timestamp changes, we
just need to make sure the file(s) that we found still exist.  This
saves a few seconds every time an atomic write is done in a source
directory next to an Android.mk file. (Atomic writes use renames, so
they always change the directory's timestamp)

With the last commit that finds out/Android.mk and out/CleanSpec.mk, it
turns out that the output directory's timestamp was changing every
build, causing the global Android.mk & CleanSpec.mk findleaves.py
command to be executed every regen check.

TEST_FIND_EMULATOR still passes after this change.

4 files changed, 90 insertions, 20 deletions

diff --git a/find.cc b/find.cc
index 1d9252f..5d9cab6 100644
--- a/find.cc
+++ b/find.cc
@@ -23,6 +23,7 @@
 #include <sys/types.h>
 #include <unistd.h>
 
+#include <algorithm>
 #include <memory>
 #include <vector>
 
@@ -38,6 +39,8 @@ class FindCond {
  public:
   virtual ~FindCond() = default;
   virtual bool IsTrue(const string& path, unsigned char type) const = 0;
+  virtual bool Countable() const = 0;
+  virtual unsigned Count() const = 0;
  protected:
   FindCond() = default;
 };
@@ -48,12 +51,20 @@ class NameCond : public FindCond {
  public:
   explicit NameCond(const string& n)
       : name_(n) {
+    has_wildcard_ = (n.find_first_of("?*[") != string::npos);
   }
   virtual bool IsTrue(const string& path, unsigned char) const override {
     return fnmatch(name_.c_str(), Basename(path).data(), 0) == 0;
   }
+  virtual bool Countable() const override {
+    return !has_wildcard_;
+  }
+  virtual unsigned Count() const override {
+    return 1;
+  }
  private:
   string name_;
+  bool has_wildcard_;
 };
 
 class TypeCond : public FindCond {
@@ -64,6 +75,12 @@ class TypeCond : public FindCond {
   virtual bool IsTrue(const string&, unsigned char type) const override {
     return type == type_;
   }
+  virtual bool Countable() const override {
+    return false;
+  }
+  virtual unsigned Count() const override {
+    return 0;
+  }
  private:
   unsigned char type_;
 };
@@ -76,6 +93,12 @@ class NotCond : public FindCond {
   virtual bool IsTrue(const string& path, unsigned char type) const override {
     return !c_->IsTrue(path, type);
   }
+  virtual bool Countable() const override {
+    return false;
+  }
+  virtual unsigned Count() const override {
+    return 0;
+  }
  private:
   unique_ptr<FindCond> c_;
 };
@@ -90,6 +113,12 @@ class AndCond : public FindCond {
       return c2_->IsTrue(path, type);
     return false;
   }
+  virtual bool Countable() const override {
+    return false;
+  }
+  virtual unsigned Count() const override {
+    return 0;
+  }
  private:
   unique_ptr<FindCond> c1_, c2_;
 };
@@ -104,6 +133,12 @@ class OrCond : public FindCond {
       return c2_->IsTrue(path, type);
     return true;
   }
+  virtual bool Countable() const override {
+    return c1_->Countable() && c2_->Countable();;
+  }
+  virtual unsigned Count() const override {
+    return c1_->Count() + c2_->Count();
+  }
  private:
   unique_ptr<FindCond> c1_, c2_;
 };
@@ -118,7 +153,7 @@ class DirentNode {
   virtual bool RunFind(const FindCommand& fc, int d,
                        string* path,
                        unordered_map<const DirentNode*, string>* cur_read_dirs,
-                       string* out) const = 0;
+                       vector<string>& out) const = 0;
 
   virtual bool IsDirectory() const = 0;
 
@@ -133,13 +168,12 @@ class DirentNode {
                         const string& path,
                         unsigned char type,
                         int d,
-                        string* out) const {
+                        vector<string>& out) const {
     if (fc.print_cond && !fc.print_cond->IsTrue(path, type))
       return;
     if (d < fc.mindepth)
       return;
-    *out += path;
-    *out += ' ';
+    out.push_back(path);
   }
 
   string base_;
@@ -154,7 +188,7 @@ class DirentFileNode : public DirentNode {
   virtual bool RunFind(const FindCommand& fc, int d,
                        string* path,
                        unordered_map<const DirentNode*, string>*,
-                       string* out) const override {
+                       vector<string>& out) const override {
     PrintIfNecessary(fc, *path, type_, d, out);
     return true;
   }
@@ -224,7 +258,7 @@ class DirentDirNode : public DirentNode {
   virtual bool RunFind(const FindCommand& fc, int d,
                        string* path,
                        unordered_map<const DirentNode*, string>* cur_read_dirs,
-                       string* out) const override {
+                       vector<string>& out) const override {
     ScopedReadDirTracker srdt(this, *path, cur_read_dirs);
     if (!srdt.ok()) {
       fprintf(stderr, "FindEmulator: find: File system loop detected; `%s' is "
@@ -237,8 +271,7 @@ class DirentDirNode : public DirentNode {
 
     if (fc.prune_cond && fc.prune_cond->IsTrue(*path, DT_DIR)) {
       if (fc.type != FindCommandType::FINDLEAVES) {
-        *out += *path;
-        *out += ' ';
+        out.push_back(*path);
       }
       return true;
     }
@@ -250,7 +283,7 @@ class DirentDirNode : public DirentNode {
 
     size_t orig_path_size = path->size();
     if (fc.type == FindCommandType::FINDLEAVES) {
-      size_t orig_out_size = out->size();
+      size_t orig_out_size = out.size();
       for (const auto& p : children_) {
         DirentNode* c = p.second;
         // We will handle directories later.
@@ -265,8 +298,20 @@ class DirentDirNode : public DirentNode {
       }
 
       // Found a leaf, stop the search.
-      if (orig_out_size != out->size())
+      if (orig_out_size != out.size()) {
+        // If we've found all possible files in this directory, we don't need
+        // to add a regen dependency on the directory, we just need to ensure
+        // that the files are not removed.
+        if (fc.print_cond->Countable() &&
+            fc.print_cond->Count() == out.size() - orig_out_size) {
+          fc.read_dirs->erase(*path);
+          for (unsigned i = orig_out_size; i < out.size(); i++) {
+            fc.found_files->push_back(out[i]);
+          }
+        }
+
         return true;
+      }
 
       for (const auto& p : children_) {
         DirentNode* c = p.second;
@@ -318,7 +363,7 @@ class DirentSymlinkNode : public DirentNode {
   virtual bool RunFind(const FindCommand& fc, int d,
                        string* path,
                        unordered_map<const DirentNode*, string>* cur_read_dirs,
-                       string* out) const override {
+                       vector<string>& out) const override {
     unsigned char type = DT_LNK;
     if (fc.follows_symlinks && errno_ != ENOENT) {
       if (errno_) {
@@ -786,14 +831,13 @@ class FindEmulatorImpl : public FindEmulator {
       }
     }
 
-    const size_t orig_out_size = out->size();
+    vector<string> results;
     for (const string& finddir : fc.finddirs) {
       const string dir = ConcatDir(fc.chdir, finddir);
 
       if (!CanHandle(dir)) {
         LOG("FindEmulator: Cannot handle find dir (%s): %s",
             dir.c_str(), cmd.c_str());
-        out->resize(orig_out_size);
         return false;
       }
 
@@ -801,7 +845,6 @@ class FindEmulatorImpl : public FindEmulator {
       const DirentNode* base = FindDir(dir, &should_fallback);
       if (!base) {
         if (should_fallback) {
-          out->resize(orig_out_size);
           return false;
         }
         if (!fc.redirect_to_devnull) {
@@ -814,18 +857,28 @@ class FindEmulatorImpl : public FindEmulator {
 
       string path = finddir;
       unordered_map<const DirentNode*, string> cur_read_dirs;
-      if (!base->RunFind(fc, 0, &path, &cur_read_dirs, out)) {
+      if (!base->RunFind(fc, 0, &path, &cur_read_dirs, results)) {
         LOG("FindEmulator: RunFind failed: %s", cmd.c_str());
-        out->resize(orig_out_size);
         return false;
       }
     }
 
-    if (!out->empty() && (*out)[out->size()-1] == ' ')
-      out->resize(out->size()-1);
+    if (results.size() > 0) {
+      // Calculate and reserve necessary space in out
+      size_t new_length = 0;
+      for (const string& result : results) {
+        new_length += result.size() + 1;
+      }
+      out->reserve(out->size() + new_length - 1);
 
-    if (fc.type == FindCommandType::FINDLEAVES) {
-      *out = SortWordsInString(*out);
+      if (fc.type == FindCommandType::FINDLEAVES) {
+        sort(results.begin(), results.end());
+      }
+
+      WordWriter writer(out);
+      for (const string& result : results) {
+        writer.Write(result);
+      }
     }
 
     LOG("FindEmulator: OK");
@@ -963,6 +1016,7 @@ class FindEmulatorImpl : public FindEmulator {
 FindCommand::FindCommand()
     : follows_symlinks(false), depth(INT_MAX), mindepth(INT_MIN),
       redirect_to_devnull(false),
+      found_files(new vector<string>()),
       read_dirs(new unordered_set<string>()) {
 }
 
diff --git a/find.h b/find.h
index ab92e67..1eee1e6 100644
--- a/find.h
+++ b/find.h
@@ -49,6 +49,7 @@ struct FindCommand {
   int mindepth;
   bool redirect_to_devnull;
 
+  unique_ptr<vector<string>> found_files;
   unique_ptr<unordered_set<string>> read_dirs;
 
  private:
diff --git a/ninja.cc b/ninja.cc
index 05d0ad1..579cea3 100644
--- a/ninja.cc
+++ b/ninja.cc
@@ -754,6 +754,11 @@ class NinjaGenerator {
           DumpString(fp, d);
         }
 
+        DumpInt(fp, cr->find->found_files->size());
+        for (StringPiece s : *cr->find->found_files) {
+          DumpString(fp, ConcatDir(cr->find->chdir, s));
+        }
+
         DumpInt(fp, cr->find->read_dirs->size());
         for (StringPiece s : *cr->find->read_dirs) {
           DumpString(fp, ConcatDir(cr->find->chdir, s));
diff --git a/regen.cc b/regen.cc
index 01bacb7..137d205 100644
--- a/regen.cc
+++ b/regen.cc
@@ -59,6 +59,7 @@ class StampChecker {
     string cmd;
     string result;
     vector<string> missing_dirs;
+    vector<string> files;
     vector<string> read_dirs;
   };
 
@@ -245,6 +246,11 @@ class StampChecker {
           LOAD_STRING(fp, &s);
           sr->missing_dirs.push_back(s);
         }
+        int num_files = LOAD_INT(fp);
+        for (int j = 0; j < num_files; j++) {
+          LOAD_STRING(fp, &s);
+          sr->files.push_back(s);
+        }
         int num_read_dirs = LOAD_INT(fp);
         for (int j = 0; j < num_read_dirs; j++) {
           LOAD_STRING(fp, &s);
@@ -303,6 +309,10 @@ class StampChecker {
       if (Exists(dir))
         return true;
     }
+    for (const string& file : sr->files) {
+      if (!Exists(file))
+        return true;
+    }
     for (const string& dir : sr->read_dirs) {
       // We assume we rarely do a significant change for the top
       // directory which affects the results of find command.