Ninja
graph.h
Go to the documentation of this file.
00001 // Copyright 2011 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_GRAPH_H_
00016 #define NINJA_GRAPH_H_
00017 
00018 #include <string>
00019 #include <vector>
00020 using namespace std;
00021 
00022 #include "eval_env.h"
00023 #include "timestamp.h"
00024 
00025 struct BuildLog;
00026 struct DiskInterface;
00027 struct DepsLog;
00028 struct Edge;
00029 struct Node;
00030 struct Pool;
00031 struct State;
00032 
00033 /// Information about a node in the dependency graph: the file, whether
00034 /// it's dirty, mtime, etc.
00035 struct Node {
00036   explicit Node(const string& path)
00037       : path_(path),
00038         mtime_(-1),
00039         dirty_(false),
00040         in_edge_(NULL),
00041         id_(-1) {}
00042 
00043   /// Return true if the file exists (mtime_ got a value).
00044   bool Stat(DiskInterface* disk_interface);
00045 
00046   /// Return true if we needed to stat.
00047   bool StatIfNecessary(DiskInterface* disk_interface) {
00048     if (status_known())
00049       return false;
00050     Stat(disk_interface);
00051     return true;
00052   }
00053 
00054   /// Mark as not-yet-stat()ed and not dirty.
00055   void ResetState() {
00056     mtime_ = -1;
00057     dirty_ = false;
00058   }
00059 
00060   /// Mark the Node as already-stat()ed and missing.
00061   void MarkMissing() {
00062     mtime_ = 0;
00063   }
00064 
00065   bool exists() const {
00066     return mtime_ != 0;
00067   }
00068 
00069   bool status_known() const {
00070     return mtime_ != -1;
00071   }
00072 
00073   const string& path() const { return path_; }
00074   TimeStamp mtime() const { return mtime_; }
00075 
00076   bool dirty() const { return dirty_; }
00077   void set_dirty(bool dirty) { dirty_ = dirty; }
00078   void MarkDirty() { dirty_ = true; }
00079 
00080   Edge* in_edge() const { return in_edge_; }
00081   void set_in_edge(Edge* edge) { in_edge_ = edge; }
00082 
00083   int id() const { return id_; }
00084   void set_id(int id) { id_ = id; }
00085 
00086   const vector<Edge*>& out_edges() const { return out_edges_; }
00087   void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); }
00088 
00089   void Dump(const char* prefix="") const;
00090 
00091 private:
00092   string path_;
00093   /// Possible values of mtime_:
00094   ///   -1: file hasn't been examined
00095   ///   0:  we looked, and file doesn't exist
00096   ///   >0: actual file's mtime
00097   TimeStamp mtime_;
00098 
00099   /// Dirty is true when the underlying file is out-of-date.
00100   /// But note that Edge::outputs_ready_ is also used in judging which
00101   /// edges to build.
00102   bool dirty_;
00103 
00104   /// The Edge that produces this Node, or NULL when there is no
00105   /// known edge to produce it.
00106   Edge* in_edge_;
00107 
00108   /// All Edges that use this Node as an input.
00109   vector<Edge*> out_edges_;
00110 
00111   /// A dense integer id for the node, assigned and used by DepsLog.
00112   int id_;
00113 };
00114 
00115 /// An invokable build command and associated metadata (description, etc.).
00116 struct Rule {
00117   explicit Rule(const string& name) : name_(name) {}
00118 
00119   const string& name() const { return name_; }
00120 
00121   typedef map<string, EvalString> Bindings;
00122   void AddBinding(const string& key, const EvalString& val);
00123 
00124   static bool IsReservedBinding(const string& var);
00125 
00126   const EvalString* GetBinding(const string& key) const;
00127 
00128  private:
00129   // Allow the parsers to reach into this object and fill out its fields.
00130   friend struct ManifestParser;
00131 
00132   string name_;
00133   map<string, EvalString> bindings_;
00134 };
00135 
00136 /// An edge in the dependency graph; links between Nodes using Rules.
00137 struct Edge {
00138   Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), deps_missing_(false),
00139            implicit_deps_(0), order_only_deps_(0) {}
00140 
00141   /// Return true if all inputs' in-edges are ready.
00142   bool AllInputsReady() const;
00143 
00144   /// Expand all variables in a command and return it as a string.
00145   /// If incl_rsp_file is enabled, the string will also contain the
00146   /// full contents of a response file (if applicable)
00147   string EvaluateCommand(bool incl_rsp_file = false);
00148 
00149   string GetBinding(const string& key);
00150   bool GetBindingBool(const string& key);
00151 
00152   void Dump(const char* prefix="") const;
00153 
00154   const Rule* rule_;
00155   Pool* pool_;
00156   vector<Node*> inputs_;
00157   vector<Node*> outputs_;
00158   BindingEnv* env_;
00159   bool outputs_ready_;
00160   bool deps_missing_;
00161 
00162   const Rule& rule() const { return *rule_; }
00163   Pool* pool() const { return pool_; }
00164   int weight() const { return 1; }
00165   bool outputs_ready() const { return outputs_ready_; }
00166 
00167   // There are three types of inputs.
00168   // 1) explicit deps, which show up as $in on the command line;
00169   // 2) implicit deps, which the target depends on implicitly (e.g. C headers),
00170   //                   and changes in them cause the target to rebuild;
00171   // 3) order-only deps, which are needed before the target builds but which
00172   //                     don't cause the target to rebuild.
00173   // These are stored in inputs_ in that order, and we keep counts of
00174   // #2 and #3 when we need to access the various subsets.
00175   int implicit_deps_;
00176   int order_only_deps_;
00177   bool is_implicit(size_t index) {
00178     return index >= inputs_.size() - order_only_deps_ - implicit_deps_ &&
00179         !is_order_only(index);
00180   }
00181   bool is_order_only(size_t index) {
00182     return index >= inputs_.size() - order_only_deps_;
00183   }
00184 
00185   bool is_phony() const;
00186 };
00187 
00188 
00189 /// ImplicitDepLoader loads implicit dependencies, as referenced via the
00190 /// "depfile" attribute in build files.
00191 struct ImplicitDepLoader {
00192   ImplicitDepLoader(State* state, DepsLog* deps_log,
00193                     DiskInterface* disk_interface)
00194       : state_(state), disk_interface_(disk_interface), deps_log_(deps_log) {}
00195 
00196   /// Load implicit dependencies for \a edge.
00197   /// @return false on error (without filling \a err if info is just missing
00198   //                          or out of date).
00199   bool LoadDeps(Edge* edge, string* err);
00200 
00201   DepsLog* deps_log() const {
00202     return deps_log_;
00203   }
00204 
00205  private:
00206   /// Load implicit dependencies for \a edge from a depfile attribute.
00207   /// @return false on error (without filling \a err if info is just missing).
00208   bool LoadDepFile(Edge* edge, const string& path, string* err);
00209 
00210   /// Load implicit dependencies for \a edge from the DepsLog.
00211   /// @return false on error (without filling \a err if info is just missing).
00212   bool LoadDepsFromLog(Edge* edge, string* err);
00213 
00214   /// Preallocate \a count spaces in the input array on \a edge, returning
00215   /// an iterator pointing at the first new space.
00216   vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
00217 
00218   /// If we don't have a edge that generates this input already,
00219   /// create one; this makes us not abort if the input is missing,
00220   /// but instead will rebuild in that circumstance.
00221   void CreatePhonyInEdge(Node* node);
00222 
00223   State* state_;
00224   DiskInterface* disk_interface_;
00225   DepsLog* deps_log_;
00226 };
00227 
00228 
00229 /// DependencyScan manages the process of scanning the files in a graph
00230 /// and updating the dirty/outputs_ready state of all the nodes and edges.
00231 struct DependencyScan {
00232   DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log,
00233                  DiskInterface* disk_interface)
00234       : build_log_(build_log),
00235         disk_interface_(disk_interface),
00236         dep_loader_(state, deps_log, disk_interface) {}
00237 
00238   /// Examine inputs, outputs, and command lines to judge whether an edge
00239   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
00240   /// state accordingly.
00241   /// Returns false on failure.
00242   bool RecomputeDirty(Edge* edge, string* err);
00243 
00244   /// Recompute whether any output of the edge is dirty.
00245   /// Returns true if so.
00246   bool RecomputeOutputsDirty(Edge* edge, Node* most_recent_input);
00247 
00248   BuildLog* build_log() const {
00249     return build_log_;
00250   }
00251   void set_build_log(BuildLog* log) {
00252     build_log_ = log;
00253   }
00254 
00255   DepsLog* deps_log() const {
00256     return dep_loader_.deps_log();
00257   }
00258 
00259  private:
00260   /// Recompute whether a given single output should be marked dirty.
00261   /// Returns true if so.
00262   bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,
00263                             const string& command, Node* output);
00264 
00265   BuildLog* build_log_;
00266   DiskInterface* disk_interface_;
00267   ImplicitDepLoader dep_loader_;
00268 };
00269 
00270 #endif  // NINJA_GRAPH_H_