Ninja
build.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_BUILD_H_
00016 #define NINJA_BUILD_H_
00017 
00018 #include <cstdio>
00019 #include <map>
00020 #include <memory>
00021 #include <queue>
00022 #include <set>
00023 #include <string>
00024 #include <vector>
00025 
00026 #include "graph.h"  // XXX needed for DependencyScan; should rearrange.
00027 #include "exit_status.h"
00028 #include "line_printer.h"
00029 #include "metrics.h"
00030 #include "util.h"  // int64_t
00031 
00032 struct BuildLog;
00033 struct BuildStatus;
00034 struct DiskInterface;
00035 struct Edge;
00036 struct Node;
00037 struct State;
00038 
00039 /// Plan stores the state of a build plan: what we intend to build,
00040 /// which steps we're ready to execute.
00041 struct Plan {
00042   Plan();
00043 
00044   /// Add a target to our plan (including all its dependencies).
00045   /// Returns false if we don't need to build this target; may
00046   /// fill in |err| with an error message if there's a problem.
00047   bool AddTarget(Node* node, string* err);
00048 
00049   // Pop a ready edge off the queue of edges to build.
00050   // Returns NULL if there's no work to do.
00051   Edge* FindWork();
00052 
00053   /// Returns true if there's more work to be done.
00054   bool more_to_do() const { return wanted_edges_ > 0 && command_edges_ > 0; }
00055 
00056   /// Dumps the current state of the plan.
00057   void Dump();
00058 
00059   /// Mark an edge as done building.  Used internally and by
00060   /// tests.
00061   void EdgeFinished(Edge* edge);
00062 
00063   /// Clean the given node during the build.
00064   void CleanNode(DependencyScan* scan, Node* node);
00065 
00066   /// Number of edges with commands to run.
00067   int command_edge_count() const { return command_edges_; }
00068 
00069 private:
00070   bool AddSubTarget(Node* node, vector<Node*>* stack, string* err);
00071   bool CheckDependencyCycle(Node* node, vector<Node*>* stack, string* err);
00072   void NodeFinished(Node* node);
00073 
00074   /// Submits a ready edge as a candidate for execution.
00075   /// The edge may be delayed from running, for example if it's a member of a
00076   /// currently-full pool.
00077   void ScheduleWork(Edge* edge);
00078 
00079   /// Allows jobs blocking on |edge| to potentially resume.
00080   /// For example, if |edge| is a member of a pool, calling this may schedule
00081   /// previously pending jobs in that pool.
00082   void ResumeDelayedJobs(Edge* edge);
00083 
00084   /// Keep track of which edges we want to build in this plan.  If this map does
00085   /// not contain an entry for an edge, we do not want to build the entry or its
00086   /// dependents.  If an entry maps to false, we do not want to build it, but we
00087   /// might want to build one of its dependents.  If the entry maps to true, we
00088   /// want to build it.
00089   map<Edge*, bool> want_;
00090 
00091   set<Edge*> ready_;
00092 
00093   /// Total number of edges that have commands (not phony).
00094   int command_edges_;
00095 
00096   /// Total remaining number of wanted edges.
00097   int wanted_edges_;
00098 };
00099 
00100 /// CommandRunner is an interface that wraps running the build
00101 /// subcommands.  This allows tests to abstract out running commands.
00102 /// RealCommandRunner is an implementation that actually runs commands.
00103 struct CommandRunner {
00104   virtual ~CommandRunner() {}
00105   virtual bool CanRunMore() = 0;
00106   virtual bool StartCommand(Edge* edge) = 0;
00107 
00108   /// The result of waiting for a command.
00109   struct Result {
00110     Result() : edge(NULL) {}
00111     Edge* edge;
00112     ExitStatus status;
00113     string output;
00114     bool success() const { return status == ExitSuccess; }
00115   };
00116   /// Wait for a command to complete, or return false if interrupted.
00117   virtual bool WaitForCommand(Result* result) = 0;
00118 
00119   virtual vector<Edge*> GetActiveEdges() { return vector<Edge*>(); }
00120   virtual void Abort() {}
00121 };
00122 
00123 /// Options (e.g. verbosity, parallelism) passed to a build.
00124 struct BuildConfig {
00125   BuildConfig() : verbosity(NORMAL), dry_run(false), parallelism(1),
00126                   failures_allowed(1), max_load_average(-0.0f) {}
00127 
00128   enum Verbosity {
00129     NORMAL,
00130     QUIET,  // No output -- used when testing.
00131     VERBOSE
00132   };
00133   Verbosity verbosity;
00134   bool dry_run;
00135   int parallelism;
00136   int failures_allowed;
00137   /// The maximum load average we must not exceed. A negative value
00138   /// means that we do not have any limit.
00139   double max_load_average;
00140 };
00141 
00142 /// Builder wraps the build process: starting commands, updating status.
00143 struct Builder {
00144   Builder(State* state, const BuildConfig& config,
00145           BuildLog* build_log, DepsLog* deps_log,
00146           DiskInterface* disk_interface);
00147   ~Builder();
00148 
00149   /// Clean up after interrupted commands by deleting output files.
00150   void Cleanup();
00151 
00152   Node* AddTarget(const string& name, string* err);
00153 
00154   /// Add a target to the build, scanning dependencies.
00155   /// @return false on error.
00156   bool AddTarget(Node* target, string* err);
00157 
00158   /// Returns true if the build targets are already up to date.
00159   bool AlreadyUpToDate() const;
00160 
00161   /// Run the build.  Returns false on error.
00162   /// It is an error to call this function when AlreadyUpToDate() is true.
00163   bool Build(string* err);
00164 
00165   bool StartEdge(Edge* edge, string* err);
00166 
00167   /// Update status ninja logs following a command termination.
00168   /// @return false if the build can not proceed further due to a fatal error.
00169   bool FinishCommand(CommandRunner::Result* result, string* err);
00170 
00171   /// Used for tests.
00172   void SetBuildLog(BuildLog* log) {
00173     scan_.set_build_log(log);
00174   }
00175 
00176   State* state_;
00177   const BuildConfig& config_;
00178   Plan plan_;
00179   auto_ptr<CommandRunner> command_runner_;
00180   BuildStatus* status_;
00181 
00182  private:
00183   bool ExtractDeps(CommandRunner::Result* result, const string& deps_type,
00184                    vector<Node*>* deps_nodes, string* err);
00185 
00186   DiskInterface* disk_interface_;
00187   DependencyScan scan_;
00188 
00189   // Unimplemented copy ctor and operator= ensure we don't copy the auto_ptr.
00190   Builder(const Builder &other);        // DO NOT IMPLEMENT
00191   void operator=(const Builder &other); // DO NOT IMPLEMENT
00192 };
00193 
00194 /// Tracks the status of a build: completion fraction, printing updates.
00195 struct BuildStatus {
00196   explicit BuildStatus(const BuildConfig& config);
00197   void PlanHasTotalEdges(int total);
00198   void BuildEdgeStarted(Edge* edge);
00199   void BuildEdgeFinished(Edge* edge, bool success, const string& output,
00200                          int* start_time, int* end_time);
00201   void BuildFinished();
00202 
00203   /// Format the progress status string by replacing the placeholders.
00204   /// See the user manual for more information about the available
00205   /// placeholders.
00206   /// @param progress_status_format The format of the progress status.
00207   string FormatProgressStatus(const char* progress_status_format) const;
00208 
00209  private:
00210   void PrintStatus(Edge* edge);
00211 
00212   const BuildConfig& config_;
00213 
00214   /// Time the build started.
00215   int64_t start_time_millis_;
00216 
00217   int started_edges_, finished_edges_, total_edges_;
00218 
00219   /// Map of running edge to time the edge started running.
00220   typedef map<Edge*, int> RunningEdgeMap;
00221   RunningEdgeMap running_edges_;
00222 
00223   /// Prints progress output.
00224   LinePrinter printer_;
00225 
00226   /// The custom progress status format to use.
00227   const char* progress_status_format_;
00228 
00229   template<size_t S>
00230   void snprinfRate(double rate, char(&buf)[S], const char* format) const {
00231     if (rate == -1) snprintf(buf, S, "?");
00232     else            snprintf(buf, S, format, rate);
00233   }
00234 
00235   struct RateInfo {
00236     RateInfo() : rate_(-1) {}
00237 
00238     void Restart() { stopwatch_.Restart(); }
00239     double Elapsed() const { return stopwatch_.Elapsed(); }
00240     double rate() { return rate_; }
00241 
00242     void UpdateRate(int edges) {
00243       if (edges && stopwatch_.Elapsed())
00244         rate_ = edges / stopwatch_.Elapsed();
00245     }
00246 
00247   private:
00248     double rate_;
00249     Stopwatch stopwatch_;
00250   };
00251 
00252   struct SlidingRateInfo {
00253     SlidingRateInfo(int n) : rate_(-1), N(n), last_update_(-1) {}
00254 
00255     void Restart() { stopwatch_.Restart(); }
00256     double rate() { return rate_; }
00257 
00258     void UpdateRate(int update_hint) {
00259       if (update_hint == last_update_)
00260         return;
00261       last_update_ = update_hint;
00262 
00263       if (times_.size() == N)
00264         times_.pop();
00265       times_.push(stopwatch_.Elapsed());
00266       if (times_.back() != times_.front())
00267         rate_ = times_.size() / (times_.back() - times_.front());
00268     }
00269 
00270   private:
00271     double rate_;
00272     Stopwatch stopwatch_;
00273     const size_t N;
00274     queue<double> times_;
00275     int last_update_;
00276   };
00277 
00278   mutable RateInfo overall_rate_;
00279   mutable SlidingRateInfo current_rate_;
00280 };
00281 
00282 #endif  // NINJA_BUILD_H_