Merge pull request #697 from nico/gclogs

Remove old outputs from build log and deps log during recompaction.

11 files changed, 176 insertions, 24 deletions

diff --git a/src/build_log.cc b/src/build_log.cc
index b92a06f..3f24c16 100644
--- a/src/build_log.cc
+++ b/src/build_log.cc
@@ -108,9 +108,10 @@ BuildLog::~BuildLog() {
   Close();
 }
 
-bool BuildLog::OpenForWrite(const string& path, string* err) {
+bool BuildLog::OpenForWrite(const string& path, const BuildLogUser& user,
+                            string* err) {
   if (needs_recompaction_) {
-    if (!Recompact(path, err))
+    if (!Recompact(path, user, err))
       return false;
   }
 
@@ -350,7 +351,8 @@ bool BuildLog::WriteEntry(FILE* f, const LogEntry& entry) {
           entry.output.c_str(), entry.command_hash) > 0;
 }
 
-bool BuildLog::Recompact(const string& path, string* err) {
+bool BuildLog::Recompact(const string& path, const BuildLogUser& user,
+                         string* err) {
   METRIC_RECORD(".ninja_log recompact");
   printf("Recompacting log...\n");
 
@@ -368,7 +370,13 @@ bool BuildLog::Recompact(const string& path, string* err) {
     return false;
   }
 
+  vector<StringPiece> dead_outputs;
   for (Entries::iterator i = entries_.begin(); i != entries_.end(); ++i) {
+    if (user.IsPathDead(i->first)) {
+      dead_outputs.push_back(i->first);
+      continue;
+    }
+
     if (!WriteEntry(f, *i->second)) {
       *err = strerror(errno);
       fclose(f);
@@ -376,6 +384,9 @@ bool BuildLog::Recompact(const string& path, string* err) {
     }
   }
 
+  for (size_t i = 0; i < dead_outputs.size(); ++i)
+    entries_.erase(dead_outputs[i]);
+
   fclose(f);
   if (unlink(path.c_str()) < 0) {
     *err = strerror(errno);
diff --git a/src/build_log.h b/src/build_log.h
index eeac5b3..fe81a85 100644
--- a/src/build_log.h
+++ b/src/build_log.h
@@ -25,6 +25,13 @@ using namespace std;
 
 struct Edge;
 
+/// Can answer questions about the manifest for the BuildLog.
+struct BuildLogUser {
+  /// Return if a given output no longer part of the build manifest.
+  /// This is only called during recompaction and doesn't have to be fast.
+  virtual bool IsPathDead(StringPiece s) const = 0;
+};
+
 /// Store a log of every command ran for every build.
 /// It has a few uses:
 ///
@@ -36,7 +43,7 @@ struct BuildLog {
   BuildLog();
   ~BuildLog();
 
-  bool OpenForWrite(const string& path, string* err);
+  bool OpenForWrite(const string& path, const BuildLogUser& user, string* err);
   bool RecordCommand(Edge* edge, int start_time, int end_time,
                      TimeStamp restat_mtime = 0);
   void Close();
@@ -72,7 +79,7 @@ struct BuildLog {
   bool WriteEntry(FILE* f, const LogEntry& entry);
 
   /// Rewrite the known log entries, throwing away old data.
-  bool Recompact(const string& path, string* err);
+  bool Recompact(const string& path, const BuildLogUser& user, string* err);
 
   typedef ExternalStringHashMap<LogEntry*>::Type Entries;
   const Entries& entries() const { return entries_; }
diff --git a/src/build_log_perftest.cc b/src/build_log_perftest.cc
index a09beb8..810c065 100644
--- a/src/build_log_perftest.cc
+++ b/src/build_log_perftest.cc
@@ -28,10 +28,15 @@
 
 const char kTestFilename[] = "BuildLogPerfTest-tempfile";
 
+struct NoDeadPaths : public BuildLogUser {
+  virtual bool IsPathDead(StringPiece) const { return false; }
+};
+
 bool WriteTestData(string* err) {
   BuildLog log;
 
-  if (!log.OpenForWrite(kTestFilename, err))
+  NoDeadPaths no_dead_paths;
+  if (!log.OpenForWrite(kTestFilename, no_dead_paths, err))
     return false;
 
   /*
diff --git a/src/build_log_test.cc b/src/build_log_test.cc
index 4639bc9..6738c7b 100644
--- a/src/build_log_test.cc
+++ b/src/build_log_test.cc
@@ -30,7 +30,7 @@ namespace {
 
 const char kTestFilename[] = "BuildLogTest-tempfile";
 
-struct BuildLogTest : public StateTestWithBuiltinRules {
+struct BuildLogTest : public StateTestWithBuiltinRules, public BuildLogUser {
   virtual void SetUp() {
     // In case a crashing test left a stale file behind.
     unlink(kTestFilename);
@@ -38,6 +38,7 @@ struct BuildLogTest : public StateTestWithBuiltinRules {
   virtual void TearDown() {
     unlink(kTestFilename);
   }
+  virtual bool IsPathDead(StringPiece s) const { return false; }
 };
 
 TEST_F(BuildLogTest, WriteRead) {
@@ -47,7 +48,7 @@ TEST_F(BuildLogTest, WriteRead) {
 
   BuildLog log1;
   string err;
-  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, &err));
+  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, *this, &err));
   ASSERT_EQ("", err);
   log1.RecordCommand(state_.edges_[0], 15, 18);
   log1.RecordCommand(state_.edges_[1], 20, 25);
@@ -75,7 +76,7 @@ TEST_F(BuildLogTest, FirstWriteAddsSignature) {
   BuildLog log;
   string contents, err;
 
-  EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+  EXPECT_TRUE(log.OpenForWrite(kTestFilename, *this, &err));
   ASSERT_EQ("", err);
   log.Close();
 
@@ -86,7 +87,7 @@ TEST_F(BuildLogTest, FirstWriteAddsSignature) {
   EXPECT_EQ(kExpectedVersion, contents);
 
   // Opening the file anew shouldn't add a second version string.
-  EXPECT_TRUE(log.OpenForWrite(kTestFilename, &err));
+  EXPECT_TRUE(log.OpenForWrite(kTestFilename, *this, &err));
   ASSERT_EQ("", err);
   log.Close();
 
@@ -122,7 +123,7 @@ TEST_F(BuildLogTest, Truncate) {
 
   BuildLog log1;
   string err;
-  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, &err));
+  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, *this, &err));
   ASSERT_EQ("", err);
   log1.RecordCommand(state_.edges_[0], 15, 18);
   log1.RecordCommand(state_.edges_[1], 20, 25);
@@ -137,7 +138,7 @@ TEST_F(BuildLogTest, Truncate) {
   for (off_t size = statbuf.st_size; size > 0; --size) {
     BuildLog log2;
     string err;
-    EXPECT_TRUE(log2.OpenForWrite(kTestFilename, &err));
+    EXPECT_TRUE(log2.OpenForWrite(kTestFilename, *this, &err));
     ASSERT_EQ("", err);
     log2.RecordCommand(state_.edges_[0], 15, 18);
     log2.RecordCommand(state_.edges_[1], 20, 25);
@@ -261,4 +262,44 @@ TEST_F(BuildLogTest, MultiTargetEdge) {
   ASSERT_EQ(22, e2->end_time);
 }
 
+struct BuildLogRecompactTest : public BuildLogTest {
+  virtual bool IsPathDead(StringPiece s) const { return s == "out2"; }
+};
+
+TEST_F(BuildLogRecompactTest, Recompact) {
+  AssertParse(&state_,
+"build out: cat in\n"
+"build out2: cat in\n");
+
+  BuildLog log1;
+  string err;
+  EXPECT_TRUE(log1.OpenForWrite(kTestFilename, *this, &err));
+  ASSERT_EQ("", err);
+  // Record the same edge several times, to trigger recompaction
+  // the next time the log is opened.
+  for (int i = 0; i < 200; ++i)
+    log1.RecordCommand(state_.edges_[0], 15, 18 + i);
+  log1.RecordCommand(state_.edges_[1], 21, 22);
+  log1.Close();
+
+  // Load...
+  BuildLog log2;
+  EXPECT_TRUE(log2.Load(kTestFilename, &err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(2u, log2.entries().size());
+  ASSERT_TRUE(log2.LookupByOutput("out"));
+  ASSERT_TRUE(log2.LookupByOutput("out2"));
+  // ...and force a recompaction.
+  EXPECT_TRUE(log2.OpenForWrite(kTestFilename, *this, &err));
+  log2.Close();
+
+  // "out2" is dead, it should've been removed.
+  BuildLog log3;
+  EXPECT_TRUE(log2.Load(kTestFilename, &err));
+  ASSERT_EQ("", err);
+  ASSERT_EQ(1u, log2.entries().size());
+  ASSERT_TRUE(log2.LookupByOutput("out"));
+  ASSERT_FALSE(log2.LookupByOutput("out2"));
+}
+
 }  // anonymous namespace
diff --git a/src/build_test.cc b/src/build_test.cc
index e206cd8..86a911b 100644
--- a/src/build_test.cc
+++ b/src/build_test.cc
@@ -412,7 +412,7 @@ struct FakeCommandRunner : public CommandRunner {
   VirtualFileSystem* fs_;
 };
 
-struct BuildTest : public StateTestWithBuiltinRules {
+struct BuildTest : public StateTestWithBuiltinRules, public BuildLogUser {
   BuildTest() : config_(MakeConfig()), command_runner_(&fs_),
                 builder_(&state_, config_, NULL, NULL, &fs_),
                 status_(config_) {
@@ -435,6 +435,8 @@ struct BuildTest : public StateTestWithBuiltinRules {
     builder_.command_runner_.release();
   }
 
+  virtual bool IsPathDead(StringPiece s) const { return false; }
+
   /// Rebuild target in the 'working tree' (fs_).
   /// State of command_runner_ and logs contents (if specified) ARE MODIFIED.
   /// Handy to check for NOOP builds, and higher-level rebuild tests.
@@ -469,7 +471,7 @@ void BuildTest::RebuildTarget(const string& target, const char* manifest,
   BuildLog build_log, *pbuild_log = NULL;
   if (log_path) {
     ASSERT_TRUE(build_log.Load(log_path, &err));
-    ASSERT_TRUE(build_log.OpenForWrite(log_path, &err));
+    ASSERT_TRUE(build_log.OpenForWrite(log_path, *this, &err));
     ASSERT_EQ("", err);
     pbuild_log = &build_log;
   }
diff --git a/src/deps_log.cc b/src/deps_log.cc
index 4f1214a..61df387 100644
--- a/src/deps_log.cc
+++ b/src/deps_log.cc
@@ -325,6 +325,9 @@ bool DepsLog::Recompact(const string& path, string* err) {
     Deps* deps = deps_[old_id];
     if (!deps) continue;  // If nodes_[old_id] is a leaf, it has no deps.
 
+    if (!IsDepsEntryLiveFor(nodes_[old_id]))
+      continue;
+
     if (!new_log.RecordDeps(nodes_[old_id], deps->mtime,
                             deps->node_count, deps->nodes)) {
       new_log.Close();
@@ -351,6 +354,16 @@ bool DepsLog::Recompact(const string& path, string* err) {
   return true;
 }
 
+bool DepsLog::IsDepsEntryLiveFor(Node* node) {
+  // Skip entries that don't have in-edges or whose edges don't have a
+  // "deps" attribute. They were in the deps log from previous builds, but
+  // the the files they were for were removed from the build and their deps
+  // entries are no longer needed.
+  // (Without the check for "deps", a chain of two or more nodes that each
+  // had deps wouldn't be collected in a single recompaction.)
+  return node->in_edge() && !node->in_edge()->GetBinding("deps").empty();
+}
+
 bool DepsLog::UpdateDeps(int out_id, Deps* deps) {
   if (out_id >= (int)deps_.size())
     deps_.resize(out_id + 1);
diff --git a/src/deps_log.h b/src/deps_log.h
index babf828..cec0257 100644
--- a/src/deps_log.h
+++ b/src/deps_log.h
@@ -88,6 +88,14 @@ struct DepsLog {
   /// Rewrite the known log entries, throwing away old data.
   bool Recompact(const string& path, string* err);
 
+  /// Returns if the deps entry for a node is still reachable from the manifest.
+  ///
+  /// The deps log can contain deps entries for files that were built in the
+  /// past but are no longer part of the manifest.  This function returns if
+  /// this is the case for a given node.  This function is slow, don't call
+  /// it from code that runs on every build.
+  bool IsDepsEntryLiveFor(Node* node);
+
   /// Used for tests.
   const vector<Node*>& nodes() const { return nodes_; }
   const vector<Deps*>& deps() const { return deps_; }
diff --git a/src/deps_log_test.cc b/src/deps_log_test.cc
index 4e6cbac..e8e5138 100644
--- a/src/deps_log_test.cc
+++ b/src/deps_log_test.cc
@@ -163,10 +163,18 @@ TEST_F(DepsLogTest, DoubleEntry) {
 
 // Verify that adding the new deps works and can be compacted away.
 TEST_F(DepsLogTest, Recompact) {
+  const char kManifest[] =
+"rule cc\n"
+"  command = cc\n"
+"  deps = gcc\n"
+"build out.o: cc\n"
+"build other_out.o: cc\n";
+
   // Write some deps to the file and grab its size.
   int file_size;
   {
     State state;
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
     DepsLog log;
     string err;
     ASSERT_TRUE(log.OpenForWrite(kTestFilename, &err));
@@ -194,6 +202,7 @@ TEST_F(DepsLogTest, Recompact) {
   int file_size_2;
   {
     State state;
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
     DepsLog log;
     string err;
     ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
@@ -215,8 +224,10 @@ TEST_F(DepsLogTest, Recompact) {
 
   // Now reload the file, verify the new deps have replaced the old, then
   // recompact.
+  int file_size_3;
   {
     State state;
+    ASSERT_NO_FATAL_FAILURE(AssertParse(&state, kManifest));
     DepsLog log;
     string err;
     ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
@@ -257,9 +268,53 @@ TEST_F(DepsLogTest, Recompact) {
     // The file should have shrunk a bit for the smaller deps.
     struct stat st;
     ASSERT_EQ(0, stat(kTestFilename, &st));
-    int file_size_3 = (int)st.st_size;
+    file_size_3 = (int)st.st_size;
     ASSERT_LT(file_size_3, file_size_2);
   }
+
+  // Now reload the file and recompact with an empty manifest. The previous
+  // entries should be removed.
+  {
+    State state;
+    // Intentionally not parsing kManifest here.
+    DepsLog log;
+    string err;
+    ASSERT_TRUE(log.Load(kTestFilename, &state, &err));
+
+    Node* out = state.GetNode("out.o");
+    DepsLog::Deps* deps = log.GetDeps(out);
+    ASSERT_TRUE(deps);
+    ASSERT_EQ(1, deps->mtime);
+    ASSERT_EQ(1, deps->node_count);
+    ASSERT_EQ("foo.h", deps->nodes[0]->path());
+
+    Node* other_out = state.GetNode("other_out.o");
+    deps = log.GetDeps(other_out);
+    ASSERT_TRUE(deps);
+    ASSERT_EQ(1, deps->mtime);
+    ASSERT_EQ(2, deps->node_count);
+    ASSERT_EQ("foo.h", deps->nodes[0]->path());
+    ASSERT_EQ("baz.h", deps->nodes[1]->path());
+
+    ASSERT_TRUE(log.Recompact(kTestFilename, &err));
+
+    // The previous entries should have been removed.
+    deps = log.GetDeps(out);
+    ASSERT_FALSE(deps);
+
+    deps = log.GetDeps(other_out);
+    ASSERT_FALSE(deps);
+
+    // The .h files pulled in via deps should no longer have ids either.
+    ASSERT_EQ(-1, state.LookupNode("foo.h")->id());
+    ASSERT_EQ(-1, state.LookupNode("baz.h")->id());
+
+    // The file should have shrunk more.
+    struct stat st;
+    ASSERT_EQ(0, stat(kTestFilename, &st));
+    int file_size_4 = (int)st.st_size;
+    ASSERT_LT(file_size_4, file_size_3);
+  }
 }
 
 // Verify that invalid file headers cause a new build.
diff --git a/src/ninja.cc b/src/ninja.cc
index a313ecb..03ca83b 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -68,7 +68,7 @@ struct Options {
 
 /// The Ninja main() loads up a series of data structures; various tools need
 /// to poke into these, so store them as fields on an object.
-struct NinjaMain {
+struct NinjaMain : public BuildLogUser {
   NinjaMain(const char* ninja_command, const BuildConfig& config) :
       ninja_command_(ninja_command), config_(config) {}
 
@@ -137,6 +137,18 @@ struct NinjaMain {
 
   /// Dump the output requested by '-d stats'.
   void DumpMetrics();
+
+  virtual bool IsPathDead(StringPiece s) const {
+    Node* n = state_.LookupNode(s);
+    // Just checking n isn't enough: If an old output is both in the build log
+    // and in the deps log, it will have a Node object in state_.  (It will also
+    // have an in edge if one of its inputs is another output that's in the deps
+    // log, but having a deps edge product an output thats input to another deps
+    // edge is rare, and the first recompaction will delete all old outputs from
+    // the deps log, and then a second recompaction will clear the build log,
+    // which seems good enough for this corner case.)
+    return !n || !n->in_edge();
+  }
 };
 
 /// Subtools, accessible via "-t foo".
@@ -444,9 +456,7 @@ int NinjaMain::ToolDeps(int argc, char** argv) {
   if (argc == 0) {
     for (vector<Node*>::const_iterator ni = deps_log_.nodes().begin();
          ni != deps_log_.nodes().end(); ++ni) {
-      // Only query for targets with an incoming edge and deps
-      Edge* e = (*ni)->in_edge();
-      if (e && !e->GetBinding("deps").empty())
+      if (deps_log_.IsDepsEntryLiveFor(*ni))
         nodes.push_back(*ni);
     }
   } else {
@@ -789,14 +799,14 @@ bool NinjaMain::OpenBuildLog(bool recompact_only) {
   }
 
   if (recompact_only) {
-    bool success = build_log_.Recompact(log_path, &err);
+    bool success = build_log_.Recompact(log_path, *this, &err);
     if (!success)
       Error("failed recompaction: %s", err.c_str());
     return success;
   }
 
   if (!config_.dry_run) {
-    if (!build_log_.OpenForWrite(log_path, &err)) {
+    if (!build_log_.OpenForWrite(log_path, *this, &err)) {
       Error("opening build log: %s", err.c_str());
       return false;
     }
diff --git a/src/state.cc b/src/state.cc
index 9b6160b..33f8423 100644
--- a/src/state.cc
+++ b/src/state.cc
@@ -118,9 +118,9 @@ Node* State::GetNode(StringPiece path) {
   return node;
 }
 
-Node* State::LookupNode(StringPiece path) {
+Node* State::LookupNode(StringPiece path) const {
   METRIC_RECORD("lookup node");
-  Paths::iterator i = paths_.find(path);
+  Paths::const_iterator i = paths_.find(path);
   if (i != paths_.end())
     return i->second;
   return NULL;
diff --git a/src/state.h b/src/state.h
index bde75ff..bcb0eff 100644
--- a/src/state.h
+++ b/src/state.h
@@ -95,7 +95,7 @@ struct State {
   Edge* AddEdge(const Rule* rule);
 
   Node* GetNode(StringPiece path);
-  Node* LookupNode(StringPiece path);
+  Node* LookupNode(StringPiece path) const;
   Node* SpellcheckNode(const string& path);
 
   void AddIn(Edge* edge, StringPiece path);