Ninja
deps_log.h
Go to the documentation of this file.
00001 // Copyright 2012 Google Inc. All Rights Reserved.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //     http://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #ifndef NINJA_DEPS_LOG_H_
00016 #define NINJA_DEPS_LOG_H_
00017 
00018 #include <string>
00019 #include <vector>
00020 using namespace std;
00021 
00022 #include <stdio.h>
00023 
00024 #include "timestamp.h"
00025 
00026 struct Node;
00027 struct State;
00028 
00029 /// As build commands run they can output extra dependency information
00030 /// (e.g. header dependencies for C source) dynamically.  DepsLog collects
00031 /// that information at build time and uses it for subsequent builds.
00032 ///
00033 /// The on-disk format is based on two primary design constraints:
00034 /// - it must be written to as a stream (during the build, which may be
00035 ///   interrupted);
00036 /// - it can be read all at once on startup.  (Alternative designs, where
00037 ///   it contains indexing information, were considered and discarded as
00038 ///   too complicated to implement; if the file is small than reading it
00039 ///   fully on startup is acceptable.)
00040 /// Here are some stats from the Windows Chrome dependency files, to
00041 /// help guide the design space.  The total text in the files sums to
00042 /// 90mb so some compression is warranted to keep load-time fast.
00043 /// There's about 10k files worth of dependencies that reference about
00044 /// 40k total paths totalling 2mb of unique strings.
00045 ///
00046 /// Based on these stats, here's the current design.
00047 /// The file is structured as version header followed by a sequence of records.
00048 /// Each record is either a path string or a dependency list.
00049 /// Numbering the path strings in file order gives them dense integer ids.
00050 /// A dependency list maps an output id to a list of input ids.
00051 ///
00052 /// Concretely, a record is:
00053 ///    two bytes record length, high bit indicates record type
00054 ///      (implies max record length 32k)
00055 ///    path records contain just the string name of the path
00056 ///    dependency records are an array of 4-byte integers
00057 ///      [output path id, output path mtime, input path id, input path id...]
00058 ///      (The mtime is compared against the on-disk output path mtime
00059 ///      to verify the stored data is up-to-date.)
00060 /// If two records reference the same output the latter one in the file
00061 /// wins, allowing updates to just be appended to the file.  A separate
00062 /// repacking step can run occasionally to remove dead records.
00063 struct DepsLog {
00064   DepsLog() : needs_recompaction_(false), file_(NULL) {}
00065   ~DepsLog();
00066 
00067   // Writing (build-time) interface.
00068   bool OpenForWrite(const string& path, string* err);
00069   bool RecordDeps(Node* node, TimeStamp mtime, const vector<Node*>& nodes);
00070   bool RecordDeps(Node* node, TimeStamp mtime, int node_count, Node** nodes);
00071   void Close();
00072 
00073   // Reading (startup-time) interface.
00074   struct Deps {
00075     Deps(int mtime, int node_count)
00076         : mtime(mtime), node_count(node_count), nodes(new Node*[node_count]) {}
00077     ~Deps() { delete [] nodes; }
00078     int mtime;
00079     int node_count;
00080     Node** nodes;
00081   };
00082   bool Load(const string& path, State* state, string* err);
00083   Deps* GetDeps(Node* node);
00084 
00085   /// Rewrite the known log entries, throwing away old data.
00086   bool Recompact(const string& path, string* err);
00087 
00088   /// Used for tests.
00089   const vector<Node*>& nodes() const { return nodes_; }
00090   const vector<Deps*>& deps() const { return deps_; }
00091 
00092  private:
00093   // Updates the in-memory representation.  Takes ownership of |deps|.
00094   // Returns true if a prior deps record was deleted.
00095   bool UpdateDeps(int out_id, Deps* deps);
00096   // Write a node name record, assigning it an id.
00097   bool RecordId(Node* node);
00098 
00099   bool needs_recompaction_;
00100   FILE* file_;
00101 
00102   /// Maps id -> Node.
00103   vector<Node*> nodes_;
00104   /// Maps id -> deps of that id.
00105   vector<Deps*> deps_;
00106 
00107   friend struct DepsLogTest;
00108 };
00109 
00110 #endif  // NINJA_DEPS_LOG_H_