add DepsLog, a new data structure for dependency information

DepsLog is a compact serialization of dependency information.
It can be used to replace depfiles for faster loading.

1 files changed, 91 insertions, 0 deletions

diff --git a/src/deps_log.h b/src/deps_log.h
new file mode 100644
index 0000000..45d2cea
--- /dev/null
+++ b/src/deps_log.h
@@ -0,0 +1,91 @@
+// Copyright 2012 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.
+
+#ifndef NINJA_DEPS_LOG_H_
+#define NINJA_DEPS_LOG_H_
+
+#include <string>
+#include <vector>
+using namespace std;
+
+#include <stdio.h>
+
+#include "timestamp.h"
+
+struct Node;
+struct State;
+
+/// As build commands run they can output extra dependency information
+/// (e.g. header dependencies for C source) via a pipe.  DepsLog collects
+/// that information at build time and reloads it at startup.
+///
+/// The on-disk format is based on two primary constraints:
+/// - it must be written to as a stream (during the build, which may be
+///   interrupted);
+/// - it can be read all at once on startup.  (Alternative designs, where
+///   it contains indexing information, were considered and discarded as
+///   too complicated to implement; if the file is small than reading it
+///   fully on startup is acceptable.)
+/// Here are some stats from the Windows Chrome dependency files, to
+/// help guide the design space.  The total text in the files sums to
+/// 90mb so some compression is warranted to keep load-time fast.
+/// There's about 10k files worth of dependencies that reference about
+/// 40k total paths totalling 2mb of unique strings.
+///
+/// Based on these above, the file is structured as a sequence of records.
+/// Each record is either a path string or a dependency list.
+/// Numbering the path strings in file order gives them dense integer ids.
+/// A dependency list maps an output id to a list of input ids.
+///
+/// Concretely, a record is:
+///    two bytes record length, high bit indicates record type
+///      (implies max record length 32k)
+///    path records contain just the string name of the path
+///    dependency records are an array of 4-byte integers
+///      [output path id, output path mtime, input path id, input path id...]
+///      (The mtime is compared against the on-disk output path mtime
+///      to verify the stored data is up-to-date.)
+/// If two records reference the same output the latter one in the file
+/// wins, allowing updates to just be appended to the file.  A separate
+/// repacking step can run occasionally to remove dead records.
+struct DepsLog {
+
+  // Writing (build-time) interface.
+  bool OpenForWrite(const string& path, string* err);
+  bool RecordDeps(Node* node, TimeStamp mtime, const vector<Node*>& nodes);
+  void Close();
+
+  // Reading (startup-time) interface.
+  bool Load(const string& path, State* state, string* err);
+
+ private:
+  // Write a node name record, assigning it an id.
+  bool RecordId(Node* node);
+
+  struct Deps {
+    Deps() : mtime(-1), node_count(0), nodes(NULL) {}
+    ~Deps() { delete [] nodes; }
+    int mtime;
+    int node_count;
+    Node** nodes;
+  };
+
+  FILE* file_;
+  vector<Node*> nodes_;
+  vector<Deps*> deps_;
+
+  friend struct DepsLogTest;
+};
+
+#endif  // NINJA_DEPS_LOG_H_