Merge remote-tracking branch 'aosp/upstream' into master

* aosp/upstream:
  Fix typo in regen_dump.cc
  Optimize findleaves regen check
  Remove "out" special case handling from FindEmulator
  Add a tool to export a kati stamp file to other tools
  Fix typo in comment.
  Turn CHECK failure that depends on file system state into an error message and include what failed in the error.

Test: Upstream tests pass
Change-Id: I00479b65666d3b5fb6dd923f74d39eeea8462d08

7 files changed, 180 insertions, 46 deletions

diff --git a/Android.bp b/Android.bp
index 5dd8ef5..bd45daa 100644
--- a/Android.bp
+++ b/Android.bp
@@ -12,8 +12,24 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
+cc_defaults {
+    name: "ckati_defaults",
+    cflags: [
+        "-W",
+        "-Wall",
+        "-Werror",
+        "-DNOLOG",
+    ],
+    target: {
+        linux: {
+            host_ldlibs: ["-lrt", "-lpthread"],
+        },
+    },
+}
+
 cc_library_host_static {
     name: "libckati",
+    defaults: ["ckati_defaults"],
     srcs: [
         "affinity.cc",
         "command.cc",
@@ -44,25 +60,25 @@ cc_library_host_static {
         "var.cc",
         "version_unknown.cc",
     ],
-    cflags: ["-W", "-Wall", "-DNOLOG"],
 }
 
 cc_binary_host {
     name: "ckati",
-    srcs: [
-        "main.cc",
-    ],
+    defaults: ["ckati_defaults"],
+    srcs: ["main.cc"],
+    whole_static_libs: ["libckati"],
+}
+
+cc_binary_host {
+    name: "ckati_stamp_dump",
+    defaults: ["ckati_defaults"],
+    srcs: ["regen_dump.cc"],
     whole_static_libs: ["libckati"],
-    cflags: ["-W", "-Wall", "-DNOLOG"],
-    target: {
-        linux: {
-            host_ldlibs: ["-lrt", "-lpthread"],
-        },
-    },
 }
 
 cc_test_host {
     name: "ckati_test",
+    defaults: ["ckati_defaults"],
     test_per_src: true,
     srcs: [
         "find_test.cc",
@@ -73,22 +89,13 @@ cc_test_host {
     ],
     gtest: false,
     whole_static_libs: ["libckati"],
-    target: {
-        linux: {
-            host_ldlibs: ["-lrt", "-lpthread"],
-        },
-    },
 }
 
 cc_benchmark_host {
     name: "ckati_fileutil_bench",
+    defaults: ["ckati_defaults"],
     srcs: [
         "fileutil_bench.cc",
     ],
     whole_static_libs: ["libckati"],
-    target: {
-        linux: {
-            host_ldlibs: ["-lrt", "-lpthread"],
-        },
-    },
 }
diff --git a/eval.cc b/eval.cc
index 115d3dd..4b56f1f 100644
--- a/eval.cc
+++ b/eval.cc
@@ -276,7 +276,9 @@ void Evaluator::EvalIf(const IfStmt* stmt) {
 
 void Evaluator::DoInclude(const string& fname) {
   Makefile* mk = MakefileCacheManager::Get()->ReadMakefile(fname);
-  CHECK(mk->Exists());
+  if (!mk->Exists()) {
+    Error(StringPrintf("%s does not exist", fname.c_str()));
+  }
 
   Var* var_list = LookupVar(Intern("MAKEFILE_LIST"));
   var_list->AppendVar(this, NewLiteral(Intern(TrimLeadingCurdir(fname)).str()));
@@ -298,7 +300,7 @@ void Evaluator::EvalInclude(const IncludeStmt* stmt) {
 
     if (stmt->should_exist) {
       if (files->empty()) {
-        // TOOD: Kati does not support building a missing include file.
+        // TODO: Kati does not support building a missing include file.
         Error(StringPrintf("%s: %s", pat.data(), strerror(errno)));
       }
     }
diff --git a/find.cc b/find.cc
index 2539212..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_) {
@@ -726,8 +771,7 @@ class FindEmulatorImpl : public FindEmulator {
     return (!HasPrefix(s, "../") &&
             !HasPrefix(s, "/") &&
             !HasPrefix(s, ".repo") &&
-            !HasPrefix(s, ".git") &&
-            !HasPrefix(s, "out"));
+            !HasPrefix(s, ".git"));
   }
 
   const DirentNode* FindDir(StringPiece d, bool* should_fallback) {
@@ -787,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;
       }
 
@@ -802,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) {
@@ -815,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");
@@ -874,8 +926,7 @@ class FindEmulatorImpl : public FindEmulator {
       if (!strcmp(ent->d_name, ".") ||
           !strcmp(ent->d_name, "..") ||
           !strcmp(ent->d_name, ".repo") ||
-          !strcmp(ent->d_name, ".git") ||
-          !strcmp(ent->d_name, "out"))
+          !strcmp(ent->d_name, ".git"))
         continue;
 
       string npath = path;
@@ -965,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.
diff --git a/regen_dump.cc b/regen_dump.cc
new file mode 100644
index 0000000..7a515f5
--- /dev/null
+++ b/regen_dump.cc
@@ -0,0 +1,57 @@
+// Copyright 2016 Google Inc. All rights reserved
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// +build ignore
+
+// This command will dump the contents of a kati stamp file into a more portable
+// format for use by other tools. For now, it just exports the files read.
+// Later, this will be expanded to include the Glob and Shell commands, but
+// those require a more complicated output format.
+
+#include <stdio.h>
+
+#include <string>
+
+#include "io.h"
+#include "log.h"
+#include "strutil.h"
+
+int main(int argc, char* argv[]) {
+  if (argc == 1) {
+    fprintf(stderr, "Usage: ckati_stamp_dump <stamp>\n");
+    return 1;
+  }
+
+  FILE *fp = fopen(argv[1], "rb");
+  if(!fp)
+    PERROR("fopen");
+
+  ScopedFile sfp(fp);
+  double gen_time;
+  size_t r = fread(&gen_time, sizeof(gen_time), 1, fp);
+  if (r != 1)
+    ERROR("Incomplete stamp file");
+
+  int num_files = LoadInt(fp);
+  if (num_files < 0)
+    ERROR("Incomplete stamp file");
+  for (int i = 0; i < num_files; i++) {
+    string s;
+    if (!LoadString(fp, &s))
+      ERROR("Incomplete stamp file");
+    printf("%s\n", s.c_str());
+  }
+
+  return 0;
+}