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   /// Returns the shell-escaped value of |key|.
00150   string GetBinding(const string& key);
00151   bool GetBindingBool(const string& key);
00152 
00153   /// Like GetBinding("depfile"), but without shell escaping.
00154   string GetUnescapedDepfile();
00155   /// Like GetBinding("rspfile"), but without shell escaping.
00156   string GetUnescapedRspfile();
00157 
00158   void Dump(const char* prefix="") const;
00159 
00160   const Rule* rule_;
00161   Pool* pool_;
00162   vector<Node*> inputs_;
00163   vector<Node*> outputs_;
00164   BindingEnv* env_;
00165   bool outputs_ready_;
00166   bool deps_missing_;
00167 
00168   const Rule& rule() const { return *rule_; }
00169   Pool* pool() const { return pool_; }
00170   int weight() const { return 1; }
00171   bool outputs_ready() const { return outputs_ready_; }
00172 
00173   // There are three types of inputs.
00174   // 1) explicit deps, which show up as $in on the command line;
00175   // 2) implicit deps, which the target depends on implicitly (e.g. C headers),
00176   //                   and changes in them cause the target to rebuild;
00177   // 3) order-only deps, which are needed before the target builds but which
00178   //                     don't cause the target to rebuild.
00179   // These are stored in inputs_ in that order, and we keep counts of
00180   // #2 and #3 when we need to access the various subsets.
00181   int implicit_deps_;
00182   int order_only_deps_;
00183   bool is_implicit(size_t index) {
00184     return index >= inputs_.size() - order_only_deps_ - implicit_deps_ &&
00185         !is_order_only(index);
00186   }
00187   bool is_order_only(size_t index) {
00188     return index >= inputs_.size() - order_only_deps_;
00189   }
00190 
00191   bool is_phony() const;
00192   bool use_console() const;
00193 };
00194 
00195 
00196 /// ImplicitDepLoader loads implicit dependencies, as referenced via the
00197 /// "depfile" attribute in build files.
00198 struct ImplicitDepLoader {
00199   ImplicitDepLoader(State* state, DepsLog* deps_log,
00200                     DiskInterface* disk_interface)
00201       : state_(state), disk_interface_(disk_interface), deps_log_(deps_log) {}
00202 
00203   /// Load implicit dependencies for \a edge.
00204   /// @return false on error (without filling \a err if info is just missing
00205   //                          or out of date).
00206   bool LoadDeps(Edge* edge, string* err);
00207 
00208   DepsLog* deps_log() const {
00209     return deps_log_;
00210   }
00211 
00212  private:
00213   /// Load implicit dependencies for \a edge from a depfile attribute.
00214   /// @return false on error (without filling \a err if info is just missing).
00215   bool LoadDepFile(Edge* edge, const string& path, string* err);
00216 
00217   /// Load implicit dependencies for \a edge from the DepsLog.
00218   /// @return false on error (without filling \a err if info is just missing).
00219   bool LoadDepsFromLog(Edge* edge, string* err);
00220 
00221   /// Preallocate \a count spaces in the input array on \a edge, returning
00222   /// an iterator pointing at the first new space.
00223   vector<Node*>::iterator PreallocateSpace(Edge* edge, int count);
00224 
00225   /// If we don't have a edge that generates this input already,
00226   /// create one; this makes us not abort if the input is missing,
00227   /// but instead will rebuild in that circumstance.
00228   void CreatePhonyInEdge(Node* node);
00229 
00230   State* state_;
00231   DiskInterface* disk_interface_;
00232   DepsLog* deps_log_;
00233 };
00234 
00235 
00236 /// DependencyScan manages the process of scanning the files in a graph
00237 /// and updating the dirty/outputs_ready state of all the nodes and edges.
00238 struct DependencyScan {
00239   DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log,
00240                  DiskInterface* disk_interface)
00241       : build_log_(build_log),
00242         disk_interface_(disk_interface),
00243         dep_loader_(state, deps_log, disk_interface) {}
00244 
00245   /// Examine inputs, outputs, and command lines to judge whether an edge
00246   /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_|
00247   /// state accordingly.
00248   /// Returns false on failure.
00249   bool RecomputeDirty(Edge* edge, string* err);
00250 
00251   /// Recompute whether any output of the edge is dirty.
00252   /// Returns true if so.
00253   bool RecomputeOutputsDirty(Edge* edge, Node* most_recent_input);
00254 
00255   BuildLog* build_log() const {
00256     return build_log_;
00257   }
00258   void set_build_log(BuildLog* log) {
00259     build_log_ = log;
00260   }
00261 
00262   DepsLog* deps_log() const {
00263     return dep_loader_.deps_log();
00264   }
00265 
00266  private:
00267   /// Recompute whether a given single output should be marked dirty.
00268   /// Returns true if so.
00269   bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input,
00270                             const string& command, Node* output);
00271 
00272   BuildLog* build_log_;
00273   DiskInterface* disk_interface_;
00274   ImplicitDepLoader dep_loader_;
00275 };
00276 
00277 #endif  // NINJA_GRAPH_H_