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_