Merge "Add usesweightlist option"

5 files changed, 149 insertions, 4 deletions

diff --git a/src/build.cc b/src/build.cc
index f152317..26a6cda 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -16,11 +16,15 @@
 
 #include <assert.h>
 #include <errno.h>
+#include <fstream>
 #include <functional>
 #include <set>
 #include <sstream>
 #include <stdio.h>
 #include <stdlib.h>
+#include <unordered_map>
+#include <unordered_set>
+#include <variant>
 #include <vector>
 
 #ifdef _WIN32
@@ -40,6 +44,7 @@
 #include "disk_interface.h"
 #include "graph.h"
 #include "metrics.h"
+#include "parallel_map.h"
 #include "state.h"
 #include "status.h"
 #include "subprocess.h"
@@ -79,6 +84,23 @@ bool DryRunCommandRunner::WaitForCommand(Result* result) {
    return true;
 }
 
+typedef std::unordered_map<HashedStrView, int64_t> WeightDataSource;
+
+// Get weight from data source, it isn't related to Edge.weight because
+// Edge.weight is used for task distribution across pools which we don't
+// want to do that in this context.
+int64_t GetWeight(const WeightDataSource& data_source, Edge* edge) {
+  if (!edge || edge->outputs_ready()) {
+    return 0;
+  }
+  if (edge->is_phony()) {
+    return 1;
+  }
+  if (auto it = data_source.find(edge->outputs_[0]->globalPath().h); it != data_source.end()) {
+    return it->second;
+  }
+  return 1;
+}
 }  // namespace
 
 Plan::Plan(Builder* builder)
@@ -590,11 +612,100 @@ Node* Builder::AddTarget(const string& name, string* err) {
   return node;
 }
 
+void Builder::RefreshPriority(const std::vector<Node*>& start_nodes) {
+  METRIC_RECORD("RefreshPriority");
+  WeightDataSource data_source;
+  // To keep HashedStrView in WeightDataSource valid.
+  std::vector<HashedStr> paths;
+  if (config_.weight_list_path) {
+    std::ifstream file(config_.weight_list_path.value());
+    std::string line;
+    while (std::getline(file, line)) {
+      if (auto pos = line.find_first_of(','); pos != string::npos) {
+        auto path = line.substr(0, pos);
+        auto raw_weight = line.substr(pos + 1);
+        char* idx;
+        int64_t weight = std::strtoll(raw_weight.c_str(), &idx, 10);
+        if (idx != nullptr) {
+          data_source[paths.emplace_back(path)] = weight;
+        }
+      }
+    }
+  } else {
+    Fatal("data_source should exist here.");
+  }
+  std::vector<std::pair<Edge*, int64_t>> todos;
+  std::unique_ptr<ThreadPool> thread_pool = CreateThreadPool();
+  for (auto* node: start_nodes) {
+    if (node && node->in_edge()) {
+      todos.emplace_back(std::make_pair(node->in_edge(), 0));
+    }
+  }
+  while (!todos.empty()) {
+    // Traverse edges in BFS manner, and update each edge's critical path based priority from
+    // accumulated weight.
+    const auto& result = ParallelMap(thread_pool.get(), todos, [&data_source] (auto& p) {
+      // the pair is composed of a visiting edge and accumulated critical path based priority.
+      auto* e = p.first;
+      auto acc = p.second;
+
+      if (!e) {
+        return std::unordered_map<Edge*, int64_t>();
+      }
+      auto run = GetWeight(data_source, e);
+      auto new_priority = run + acc;
+      // Skip if priority isn't updated
+      if (new_priority <= e->priority()) {
+        return std::unordered_map<Edge*, int64_t>();
+      }
+      e->priority_ = new_priority;
+
+      std::set<Edge*, EdgeCmp> next_edges;
+      for (auto* next_node : e->inputs_) {
+        if (!next_node) {
+          continue;
+        }
+        auto* next_e = next_node->in_edge();
+        if (next_e) {
+          next_edges.insert(next_e);
+        }
+      }
+
+      std::unordered_map<Edge*, int64_t> next_todo_map;
+      for (auto* ne : next_edges) {
+        auto next_run = GetWeight(data_source, ne);
+        if (next_run + e->priority() > ne->priority()) {
+          next_todo_map.try_emplace(ne, e->priority());
+        }
+      }
+      return next_todo_map;
+    });
+    todos.clear();
+
+    std::unordered_map<Edge*, int64_t> next_todo_map_total;
+    for (const auto& todo_map : result) {
+      for (const auto& [k, v] : todo_map) {
+        auto [it, inserted] = next_todo_map_total.try_emplace(k, v);
+          if (!inserted) {
+            it->second = std::max(it->second, v);
+          }
+      }
+    }
+    for (const auto& [key, value] : next_todo_map_total) {
+      todos.emplace_back(key, value);
+    }
+  }
+}
+
 bool Builder::AddTargets(const std::vector<Node*> &nodes, string* err) {
   std::vector<Node*> validation_nodes;
   if (!scan_.RecomputeNodesDirty(nodes, &validation_nodes, err))
     return false;
 
+  if (config_.weight_list_path) {
+    RefreshPriority(nodes);
+  }
+
   for (Node* node : nodes) {
     std::string plan_err;
     if (!plan_.AddTarget(node, &plan_err)) {
diff --git a/src/build.h b/src/build.h
index b335a7d..1283ee8 100644
--- a/src/build.h
+++ b/src/build.h
@@ -18,6 +18,7 @@
 #include <cstdio>
 #include <map>
 #include <memory>
+#include <optional>
 #include <queue>
 #include <string>
 #include <vector>
@@ -172,7 +173,8 @@ struct BuildConfig {
                   output_directory_should_err(false),
                   missing_output_file_should_err(false),
                   old_output_should_err(false),
-                  pre_remove_output_files(false) {}
+                  pre_remove_output_files(false),
+                  weight_list_path(std::nullopt) {}
 
   enum Verbosity {
     NORMAL,
@@ -221,6 +223,16 @@ struct BuildConfig {
 
   /// Whether to remove outputs before executing rule commands
   bool pre_remove_output_files;
+
+  /// A file path which includes a weight list for modules.
+  /// A priority list is a csv file format and it has two fields, output global path and weight.
+  /// Weight is proportional to execution time of an edge for a node.
+  /// And it is used to set a priority of edges by a critical path based on weight.
+  /// For example,
+  ///   out/lib/foo.so,2
+  ///   out/bin/bar,5
+  /// Note that the default weight is 1 for a module which isn't included in the list.
+  std::optional<std::string> weight_list_path;
 };
 
 /// Builder wraps the build process: starting commands, updating status.
@@ -277,6 +289,8 @@ struct Builder {
                     const string& deps_prefix, vector<Node*>* deps_nodes,
                     string* err);
 
+  void RefreshPriority(const std::vector<Node*>& nodes);
+
   /// Map of running edge to time the edge started running.
   typedef map<Edge*, int> RunningEdgeMap;
   RunningEdgeMap running_edges_;
diff --git a/src/graph.h b/src/graph.h
index 001b68d..85e9326 100644
--- a/src/graph.h
+++ b/src/graph.h
@@ -464,6 +464,7 @@ public:
   VisitMark mark_ = VisitNone;
   bool precomputed_dirtiness_ = false;
   size_t id_ = 0;
+  int64_t priority_ = 0;
   bool outputs_ready_ = false;
   bool deps_loaded_ = false;
   bool deps_missing_ = false;
@@ -474,6 +475,11 @@ public:
   const Rule& rule() const { return *rule_; }
   Pool* pool() const { return pool_; }
   int weight() const { return 1; }
+  // Priority is a value used to determine which modules should be built earlier than others.
+  // The default value is 1 and can be updated by a priority list file.
+  // After that, it is also updated from dependents.
+  // The final priority would be the sum of the critical path between this edge and the target edge.
+  int64_t priority() const { return priority_; }
   bool outputs_ready() const { return outputs_ready_; }
 
   // There are three types of inputs.
@@ -521,7 +527,13 @@ public:
 
 struct EdgeCmp {
   bool operator()(const Edge* a, const Edge* b) const {
-    return a->id_ < b->id_;
+    if (a->priority() == b->priority()) {
+      // Order by id ascending to preserve the original behavior if they have
+      // the same priority.
+      return a->id_ < b->id_;
+    }
+    // Order by priority descending to run prioritized edges earlier.
+    return a->priority() > b->priority();
   }
 };
 
diff --git a/src/ninja.cc b/src/ninja.cc
index 00372eb..19fc605 100644
--- a/src/ninja.cc
+++ b/src/ninja.cc
@@ -1307,7 +1307,8 @@ bool OptionEnable(const string& name, Options* options, BuildConfig* config) {
 "  usessymlinkoutputs={yes,no}  whether the generate uses 'symlink_outputs' so \n"
 "                             that these warnings work:\n"
 "                                undeclaredsymlinkoutputs\n"
-"  preremoveoutputs={yes,no}  whether to remove outputs before running rule\n");
+"  preremoveoutputs={yes,no}  whether to remove outputs before running rule\n"
+"  usesweightlist={<file path>,no}  whether to prioritize some rules based on weight list from file\n");
     return false;
   } else if (name == "usesphonyoutputs=yes") {
     config->uses_phony_outputs = true;
@@ -1327,6 +1328,12 @@ bool OptionEnable(const string& name, Options* options, BuildConfig* config) {
   } else if (name == "preremoveoutputs=no") {
     config->pre_remove_output_files = false;
     return true;
+  } else if (name == "usesweightlist=no") {
+    config->weight_list_path = std::nullopt;
+    return true;
+  } else if (auto n = name.find("usesweightlist=") != std::string::npos) {
+    config->weight_list_path = name.substr(n + strlen("usesweightlist=" ) - 1);
+    return true;
   } else {
     const char* suggestion =
         SpellcheckString(name.c_str(),
diff --git a/src/status.cc b/src/status.cc
index 4f8a5eb..1049312 100644
--- a/src/status.cc
+++ b/src/status.cc
@@ -345,7 +345,8 @@ void StatusSerializer::BuildEdgeStarted(Edge* edge, int64_t start_time_millis) {
     edge_started->add_outputs((*it)->globalPath().h.data());
   }
 
-  edge_started->set_desc(edge->GetBinding("description"));
+  const auto& proirity_suffix = config_.weight_list_path ? (" (priority: " + std::to_string(edge->priority()) + ")") : "";
+  edge_started->set_desc(edge->GetBinding("description") + proirity_suffix);
 
   edge_started->set_command(edge->GetBinding("command"));