Ninja
|
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_