diff options
author | Zeno Albisser <zeno.albisser@digia.com> | 2013-08-15 21:46:11 +0200 |
---|---|---|
committer | Zeno Albisser <zeno.albisser@digia.com> | 2013-08-15 21:46:11 +0200 |
commit | 679147eead574d186ebf3069647b4c23e8ccace6 (patch) | |
tree | fc247a0ac8ff119f7c8550879ebb6d3dd8d1ff69 /ninja/src/graph.h | |
download | qtwebengine-chromium-679147eead574d186ebf3069647b4c23e8ccace6.tar.gz |
Initial import.
Diffstat (limited to 'ninja/src/graph.h')
-rw-r--r-- | ninja/src/graph.h | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/ninja/src/graph.h b/ninja/src/graph.h new file mode 100644 index 00000000000..428ba01e65d --- /dev/null +++ b/ninja/src/graph.h @@ -0,0 +1,266 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef NINJA_GRAPH_H_ +#define NINJA_GRAPH_H_ + +#include <string> +#include <vector> +using namespace std; + +#include "eval_env.h" +#include "timestamp.h" + +struct BuildLog; +struct DiskInterface; +struct DepsLog; +struct Edge; +struct Node; +struct Pool; +struct State; + +/// Information about a node in the dependency graph: the file, whether +/// it's dirty, mtime, etc. +struct Node { + explicit Node(const string& path) + : path_(path), + mtime_(-1), + dirty_(false), + in_edge_(NULL), + id_(-1) {} + + /// Return true if the file exists (mtime_ got a value). + bool Stat(DiskInterface* disk_interface); + + /// Return true if we needed to stat. + bool StatIfNecessary(DiskInterface* disk_interface) { + if (status_known()) + return false; + Stat(disk_interface); + return true; + } + + /// Mark as not-yet-stat()ed and not dirty. + void ResetState() { + mtime_ = -1; + dirty_ = false; + } + + /// Mark the Node as already-stat()ed and missing. + void MarkMissing() { + mtime_ = 0; + } + + bool exists() const { + return mtime_ != 0; + } + + bool status_known() const { + return mtime_ != -1; + } + + const string& path() const { return path_; } + TimeStamp mtime() const { return mtime_; } + + bool dirty() const { return dirty_; } + void set_dirty(bool dirty) { dirty_ = dirty; } + void MarkDirty() { dirty_ = true; } + + Edge* in_edge() const { return in_edge_; } + void set_in_edge(Edge* edge) { in_edge_ = edge; } + + int id() const { return id_; } + void set_id(int id) { id_ = id; } + + const vector<Edge*>& out_edges() const { return out_edges_; } + void AddOutEdge(Edge* edge) { out_edges_.push_back(edge); } + + void Dump(const char* prefix="") const; + +private: + string path_; + /// Possible values of mtime_: + /// -1: file hasn't been examined + /// 0: we looked, and file doesn't exist + /// >0: actual file's mtime + TimeStamp mtime_; + + /// Dirty is true when the underlying file is out-of-date. + /// But note that Edge::outputs_ready_ is also used in judging which + /// edges to build. + bool dirty_; + + /// The Edge that produces this Node, or NULL when there is no + /// known edge to produce it. + Edge* in_edge_; + + /// All Edges that use this Node as an input. + vector<Edge*> out_edges_; + + /// A dense integer id for the node, assigned and used by DepsLog. + int id_; +}; + +/// An invokable build command and associated metadata (description, etc.). +struct Rule { + explicit Rule(const string& name) : name_(name) {} + + const string& name() const { return name_; } + + typedef map<string, EvalString> Bindings; + void AddBinding(const string& key, const EvalString& val); + + static bool IsReservedBinding(const string& var); + + const EvalString* GetBinding(const string& key) const; + + private: + // Allow the parsers to reach into this object and fill out its fields. + friend struct ManifestParser; + + string name_; + map<string, EvalString> bindings_; +}; + +/// An edge in the dependency graph; links between Nodes using Rules. +struct Edge { + Edge() : rule_(NULL), env_(NULL), outputs_ready_(false), implicit_deps_(0), + order_only_deps_(0) {} + + /// Return true if all inputs' in-edges are ready. + bool AllInputsReady() const; + + /// Expand all variables in a command and return it as a string. + /// If incl_rsp_file is enabled, the string will also contain the + /// full contents of a response file (if applicable) + string EvaluateCommand(bool incl_rsp_file = false); + + string GetBinding(const string& key); + bool GetBindingBool(const string& key); + + void Dump(const char* prefix="") const; + + const Rule* rule_; + Pool* pool_; + vector<Node*> inputs_; + vector<Node*> outputs_; + BindingEnv* env_; + bool outputs_ready_; + + const Rule& rule() const { return *rule_; } + Pool* pool() const { return pool_; } + int weight() const { return 1; } + bool outputs_ready() const { return outputs_ready_; } + + // There are three types of inputs. + // 1) explicit deps, which show up as $in on the command line; + // 2) implicit deps, which the target depends on implicitly (e.g. C headers), + // and changes in them cause the target to rebuild; + // 3) order-only deps, which are needed before the target builds but which + // don't cause the target to rebuild. + // These are stored in inputs_ in that order, and we keep counts of + // #2 and #3 when we need to access the various subsets. + int implicit_deps_; + int order_only_deps_; + bool is_implicit(size_t index) { + return index >= inputs_.size() - order_only_deps_ - implicit_deps_ && + !is_order_only(index); + } + bool is_order_only(size_t index) { + return index >= inputs_.size() - order_only_deps_; + } + + bool is_phony() const; +}; + + +/// ImplicitDepLoader loads implicit dependencies, as referenced via the +/// "depfile" attribute in build files. +struct ImplicitDepLoader { + ImplicitDepLoader(State* state, DepsLog* deps_log, + DiskInterface* disk_interface) + : state_(state), disk_interface_(disk_interface), deps_log_(deps_log) {} + + /// Load implicit dependencies for \a edge. May fill in \a mtime with + /// the timestamp of the loaded information. + /// @return false on error (without filling \a err if info is just missing). + bool LoadDeps(Edge* edge, TimeStamp* mtime, string* err); + + DepsLog* deps_log() const { + return deps_log_; + } + + private: + /// Load implicit dependencies for \a edge from a depfile attribute. + /// @return false on error (without filling \a err if info is just missing). + bool LoadDepFile(Edge* edge, const string& path, string* err); + + /// Load implicit dependencies for \a edge from the DepsLog. + /// @return false on error (without filling \a err if info is just missing). + bool LoadDepsFromLog(Edge* edge, TimeStamp* mtime, string* err); + + /// Preallocate \a count spaces in the input array on \a edge, returning + /// an iterator pointing at the first new space. + vector<Node*>::iterator PreallocateSpace(Edge* edge, int count); + + /// If we don't have a edge that generates this input already, + /// create one; this makes us not abort if the input is missing, + /// but instead will rebuild in that circumstance. + void CreatePhonyInEdge(Node* node); + + State* state_; + DiskInterface* disk_interface_; + DepsLog* deps_log_; +}; + + +/// DependencyScan manages the process of scanning the files in a graph +/// and updating the dirty/outputs_ready state of all the nodes and edges. +struct DependencyScan { + DependencyScan(State* state, BuildLog* build_log, DepsLog* deps_log, + DiskInterface* disk_interface) + : build_log_(build_log), + disk_interface_(disk_interface), + dep_loader_(state, deps_log, disk_interface) {} + + /// Examine inputs, outputs, and command lines to judge whether an edge + /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_| + /// state accordingly. + /// Returns false on failure. + bool RecomputeDirty(Edge* edge, string* err); + + /// Recompute whether a given single output should be marked dirty. + /// Returns true if so. + bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input, + TimeStamp deps_mtime, + const string& command, Node* output); + + BuildLog* build_log() const { + return build_log_; + } + void set_build_log(BuildLog* log) { + build_log_ = log; + } + + DepsLog* deps_log() const { + return dep_loader_.deps_log(); + } + + private: + BuildLog* build_log_; + DiskInterface* disk_interface_; + ImplicitDepLoader dep_loader_; +}; + +#endif // NINJA_GRAPH_H_ |