Resolve dependencies

1 files changed, 131 insertions, 34 deletions

diff --git a/xmake.cpp b/xmake.cpp
index 4c6fdbe..a1831e8 100644
--- a/xmake.cpp
+++ b/xmake.cpp
@@ -6,9 +6,11 @@
 #include <iostream>
 #include <iterator>
 #include <sstream>
+#include <stack>
 #include <stdexcept>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include <boost/property_tree/ptree.hpp>
@@ -61,11 +63,12 @@ namespace {
   return t_p < t_other;
  }
 
+ // outdated according to dependency file list, non-recursively
  bool is_outdated(const fs::path& p, const std::vector<fs::path> &dependencies) {
   if (!fs::exists(p))
    return true;
 
-  for (auto& dep: dependencies) {
+  for (const auto& dep: dependencies) {
    if (!exists(dep) || is_older(p, dep)) {
     return true;
    }
@@ -74,6 +77,33 @@ namespace {
   return false;
  }
 
+ std::vector<fs::path> dependencies_of(const fs::path& p, const std::unordered_map<fs::path, std::vector<fs::path>> &dependencies) {
+  try {
+   return dependencies.at(p);
+  } catch (const std::out_of_range& ex) {
+   return {}; // empty by default
+  }
+ }
+
+ // outdated according to dependency tree, recursively
+ bool is_outdated(const fs::path& p, const std::unordered_map<fs::path, std::vector<fs::path>> &dependencies) {
+  if (!fs::exists(p))
+   return true;
+
+  std::vector<fs::path> deps{dependencies_of(p, dependencies)};
+  for (const auto& dep: deps) {
+   if (!exists(dep) || is_older(p, dep)) {
+    return true;
+   }
+
+   if (is_outdated(dep, dependencies)) {
+    return true;
+   }
+  }
+
+  return false;
+ }
+
  std::vector<fs::path> deps_from_depfile(const fs::path& path) {
   std::string depfile_content{Reichwein::File::getFile(path)};
   std::vector<std::string> parts {Reichwein::Stringhelper::split(depfile_content, ":\r\n")};
@@ -105,6 +135,82 @@ namespace {
   return deps_from_depfile(depfile);
  }
 
+ // type of file can be built from dependencies
+ bool is_buildable_by_extension(const fs::path& p) {
+  fs::path ext{p.extension()};
+  return ext.empty() || ext == ".o";
+ }
+
+ // build 1 file
+ void build(const fs::path& p, const std::unordered_map<fs::path, std::vector<fs::path>> &dependencies) {
+  std::string command;
+
+  if (p.extension() == ".o") {
+    // compile
+    fs::path cppfile{p};
+    cppfile.replace_extension("cpp");
+    command = fmt::format("g++ -std=c++17 -c {} -o {}", cppfile.string(), p.string());
+  } else {
+   // link
+   command = "g++";
+   std::vector<fs::path> objects{dependencies_of(p, dependencies)};
+   for (auto &i: objects) {
+    command += fmt::format(" {}", i.string());
+   }
+   command += " -lfmt -lreichwein";
+   command += fmt::format(" -o {}", p.string());
+  }
+
+  std::cout << command << std::endl;
+  int result{system(command.c_str())};
+  if (result != 0) {
+   throw std::runtime_error(fmt::format("Error {}", result));
+  }
+ }
+
+ // build list of files
+ // eats up input
+ void build(std::unordered_set<fs::path>& buildlist, const std::unordered_map<fs::path, std::vector<fs::path>> &dependencies) {
+  std::unordered_set<fs::path> activelist; // currently building
+  std::unordered_set<fs::path> donelist; // build done
+
+  if (buildlist.empty()) {
+   std::cout << "Everything up to date." << std::endl;
+  } else {
+   std::cout << "Running commands: " << std::endl;
+  }
+
+  while (!buildlist.empty()) {
+   // find file which can be built directly since its build dependencies are up to date
+   // this holds for either any member of the set (e.g. at begin()), or any of its direct or indirect dependencies
+   fs::path current {*buildlist.begin()};
+
+   bool found_outdated{}; // outdated dependencies
+
+   do {
+    found_outdated = false;
+    std::vector<fs::path> deps{dependencies_of(current, dependencies)};
+    for (auto& i: deps) {
+     if (activelist.find(i) == activelist.end() && is_outdated(i, dependencies)) {
+      found_outdated = true;
+      current = i;
+      break;
+     }
+    }
+   } while (found_outdated);
+
+   buildlist.erase(current);
+
+   activelist.insert(current);
+   // TODO: build in background
+   build(current, dependencies);
+   activelist.erase(current);
+
+   donelist.insert(current);
+  }
+ }
+
+ // build everything according to specified configuration
  void build(const pt::ptree& ptree) {
   fs::path target{get_target(ptree)};
   std::vector<fs::path> objects{get_objects(ptree)};
@@ -127,44 +233,31 @@ namespace {
    dependencies.emplace(p_obj, deps);
   }
 
-  std::vector<std::string> commands;
-  // compile
-  for (auto &p: sources) {
-   fs::path p_obj{p};
-   p_obj.replace_extension("o");
-   if (is_outdated(p_obj, std::vector<fs::path>{p})) {
-    commands.push_back(fmt::format("g++ -std=c++17 -c {} -o {}", p.string(), p_obj.string()));
+  // create build list by depth-first search
+  std::cout << "Calculating build list..." << std::endl;
+  std::unordered_set<fs::path> buildlist;
+  std::stack<fs::path> container; // temporary container for search algorithm
+  container.push(target);
+  while (!container.empty()) {
+   fs::path current{container.top()};
+   container.pop();
+
+   std::vector<fs::path> deps{dependencies_of(current, dependencies)};
+   for (auto &i: deps) {
+    container.push(i);
    }
-  }
-  // link
-  std::vector<fs::path> deps{sources};
-  if (is_outdated(target, deps)) {
-   std::string link_command{"g++"};
-   for (auto &i: objects) {
-    link_command += fmt::format(" {}", i.string());
+
+   if (is_outdated(current, dependencies) && is_buildable_by_extension(current)) {
+    buildlist.insert(current);
    }
-   link_command += " -lfmt -lreichwein";
-   link_command += fmt::format(" -o {}", target.string());
-   commands.push_back(link_command);
   }
 
-  std::cout << "Commands: " << std::endl;
-  for (auto &i: commands) {
+  std::cout << "Build list:" << std::endl;
+  for (auto &i: buildlist) {
    std::cout << "  " << i << std::endl;
   }
 
-  if (commands.size() == 0) {
-   std::cout << "Everything up to date." << std::endl;
-  } else {
-   std::cout << "Running commands: " << std::endl;
-   for (auto &i: commands) {
-    std::cout << i << std::endl;
-    int result{system(i.c_str())};
-    if (result != 0) {
-     throw std::runtime_error(fmt::format("Error {}", result));
-    }
-   }
-  }
+  build(buildlist, dependencies);
  }
 
  void clean(const pt::ptree& ptree) {
@@ -173,10 +266,14 @@ namespace {
 
   std::vector<std::string> commands;
   for (auto &i: cleanlist) {
-   commands.push_back(fmt::format("rm -f {}", i.string()));
+   if (fs::exists(i)) {
+    commands.push_back(fmt::format("rm -f {}", i.string()));
+   }
    fs::path dep{i};
    dep.replace_extension("d");
-   commands.push_back(fmt::format("rm -f {}", dep.string()));
+   if (fs::exists(dep)) {
+    commands.push_back(fmt::format("rm -f {}", dep.string()));
+   }
   }
 
   std::cout << "Running commands: " << std::endl;