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