Add support for "first" and "last" execution modes

15 files changed, 248 insertions, 44 deletions

diff --git a/build/algorithm b/build/algorithm
index fa74769..a272a4c 100644
--- a/build/algorithm
+++ b/build/algorithm
@@ -53,6 +53,11 @@ namespace build
   target_state
   execute_prerequisites (action, target&);
 
+  // As above but iterates over the prerequisites in reverse.
+  //
+  target_state
+  reverse_execute_prerequisites (action, target&);
+
   // A version of the above that also determines whether the action
   // needs to be executed on the target based on the passed timestamp.
   //
diff --git a/build/algorithm.cxx b/build/algorithm.cxx
index 776ea3e..109f456 100644
--- a/build/algorithm.cxx
+++ b/build/algorithm.cxx
@@ -223,6 +223,25 @@ namespace build
     return ts;
   }
 
+  target_state
+  reverse_execute_prerequisites (action a, target& t)
+  {
+    target_state ts (target_state::unchanged);
+
+    for (const prerequisite& p: reverse_iterate (t.prerequisites))
+    {
+      if (p.target == nullptr) // Skip ignored.
+        continue;
+
+      target& pt (*p.target);
+
+      if (execute (a, pt) == target_state::changed)
+        ts = target_state::changed;
+    }
+
+    return ts;
+  }
+
   bool
   execute_prerequisites (action a, target& t, const timestamp& mt)
   {
@@ -314,7 +333,7 @@ namespace build
     target_state ts (target_state::unchanged);
 
     if (!t.prerequisites.empty ())
-      ts = execute_prerequisites (a, t);
+      ts = reverse_execute_prerequisites (a, t);
 
     return rs == rmfile_status::success ? target_state::changed : ts;
   }
diff --git a/build/algorithm.ixx b/build/algorithm.ixx
index 340789e..3bc4632 100644
--- a/build/algorithm.ixx
+++ b/build/algorithm.ixx
@@ -2,6 +2,8 @@
 // copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
 // license   : MIT; see accompanying LICENSE file
 
+#include <build/context>
+
 namespace build
 {
   target&
@@ -37,7 +39,15 @@ namespace build
     {
     case target_state::unchanged:
     case target_state::changed: return t.state;
-    default: return execute_impl (a, t);
+    default:
+      {
+        // Handle the "last" execution mode.
+        //
+        if (current_mode == execution_mode::last && t.dependents != 0)
+          return (t.state = target_state::postponed);
+
+        return execute_impl (a, t);
+      }
     }
   }
 }
diff --git a/build/b.cxx b/build/b.cxx
index 5096bc2..6bd1d86 100644
--- a/build/b.cxx
+++ b/build/b.cxx
@@ -109,12 +109,12 @@ main (int argc, char* argv[])
     // see <operation> for details. Loading of the buildfiles can result
     // in additional names being added (via module loading).
     //
-    meta_operations.insert ("perform"); // Default.
-    meta_operations.insert ("configure");
-    meta_operations.insert ("disfigure");
+    meta_operations.insert (meta_operation_info {"perform"});
+    meta_operations.insert (meta_operation_info {"configure"});
+    meta_operations.insert (meta_operation_info {"disfigure"});
 
-    operations.insert ("update"); // Default.
-    operations.insert ("clean");
+    operations.insert (operation_info {"update", execution_mode::first});
+    operations.insert (operation_info {"clean", execution_mode::last});
 
     // Figure out work and home directories.
     //
@@ -473,9 +473,11 @@ main (int argc, char* argv[])
     {
       for (opspec& os: ms)
       {
-        current_rules = &rules[os.name];
         action act (meta_operations.find (ms.name), operations.find (os.name));
 
+        current_mode = operations[act.operation ()].mode;
+        current_rules = &rules[os.name];
+
         level4 ([&]{trace << ms.name << " " << os.name << " " << act;});
 
         // Multiple targets in the same operation can be done in parallel.
diff --git a/build/context b/build/context
index 7c7421d..2e3209a 100644
--- a/build/context
+++ b/build/context
@@ -9,6 +9,8 @@
 #include <ostream>
 
 #include <build/path>
+#include <build/rule>
+#include <build/operation>
 
 namespace build
 {
@@ -17,6 +19,11 @@ namespace build
   extern path work;
   extern path home;
 
+  // Current action (meta/operation).
+  //
+  extern execution_mode current_mode;
+  extern const target_rule_map* current_rules;
+
   // Return the src/out directory corresponding to the given out/src. The
   // passed directory should be a sub-directory of out/src_root.
   //
diff --git a/build/context.cxx b/build/context.cxx
index 6c37e38..e9434f7 100644
--- a/build/context.cxx
+++ b/build/context.cxx
@@ -16,6 +16,9 @@ namespace build
   path work;
   path home;
 
+  execution_mode current_mode;
+  const target_rule_map* current_rules;
+
   path
   src_out (const path& out, scope& s)
   {
diff --git a/build/key-set b/build/key-set
index 8c197b8..1d0b532 100644
--- a/build/key-set
+++ b/build/key-set
@@ -5,6 +5,9 @@
 #ifndef BUILD_KEY_SET
 #define BUILD_KEY_SET
 
+#include <utility>    // declval()
+#include <functional> // hash
+
 namespace build
 {
   // Google the "Emulating Boost.MultiIndex with Standard Containers" blog
@@ -18,6 +21,7 @@ namespace build
 
     set_key (const T* v = 0): p (v) {}
     bool operator< (const set_key& x) const {return *p < *x.p;}
+    bool operator== (const set_key& x) const {return *p == *x.p;}
   };
 
   template <typename I>
@@ -38,4 +42,18 @@ namespace build
   };
 }
 
+namespace std
+{
+  template <typename T>
+  struct hash<build::set_key<T>>: hash<T>
+  {
+    size_t
+    operator() (build::set_key<T> x) const
+      noexcept (noexcept (declval<hash<T>> () (*x.p)))
+    {
+      return hash<T>::operator() (*x.p);
+    }
+  };
+}
+
 #endif // BUILD_KEY_SET
diff --git a/build/operation b/build/operation
index 3398f32..743458a 100644
--- a/build/operation
+++ b/build/operation
@@ -58,10 +58,71 @@ namespace build
   const action_id perform_update_id = (perform_id << 4) | update_id;
   const action_id perform_clean_id  = (perform_id << 4) | clean_id;
 
-  // Meta/operation id tables.
+  // Recipe execution mode.
   //
-  using meta_operation_table = string_table<meta_operation_id>;
-  using operation_table = string_table<operation_id>;
+  // When a target is a prerequisite of another target, its recipe can be
+  // executed before the dependent's recipe (the normal case) or after.
+  // We will call these "front" and "back" execution modes, respectively
+  // (think "the prerequisite is 'front-running' the dependent").
+  //
+  // There could also be several dependent targets and the prerequisite's
+  // recipe can be execute as part of the first dependent (the normal
+  // case) or last (or for all/some of them; see the recipe execution
+  // protocol in <target>). We will call these "first" and "last"
+  // execution modes, respectively.
+  //
+  // Now you may be having a hard time imagining where a mode other than
+  // the normal one (first/front) could be useful. An the answer is,
+  // compensating or inverse operations such as clean, uninstall, etc.
+  // If we use the last/back mode for, say, clean, then we will remove
+  // targets in the order inverse to the way they were updated. While
+  // this sounds like an elegant idea, are there any practical benefits
+  // of doing it this way. As it turns out there is (at least) one: when
+  // we are removing a directory (see fsdir{}), we want to do it after
+  // all the targets that depend on it (such as files, sub-directories)
+  // were removed. If we do it before, then the directory won't be empty
+  // yet.
+  //
+  // It appears that this execution mode is dictated by the essence of
+  // the operation. Constructive operations (those that "do") seem to
+  // naturally use the first/front mode. That is, we need to "do" the
+  // prerequisite first before we can "do" the dependent. While the
+  // destructive ones (those that "undo") seem to need last/back. That
+  // is, we need to "undo" all the dependents before we can "undo" the
+  // prerequisite (say, we need to remove all the files before we can
+  // remove their directory).
+  //
+  // If you noticed the parallel with the way C++ construction and
+  // destruction works for base/derived object then you earned a gold
+  // star!
+  //
+  // Note that the front/back mode is realized in the dependen's recipe
+  // (which is another indication that it is a property of the operation).
+  //
+  enum class execution_mode {first, last};
+
+  // Meta/operation tables.
+  //
+  struct meta_operation_info
+  {
+    const std::string name;
+
+    const std::string&
+    key () const {return name;} // string_table interface.
+  };
+
+  struct operation_info
+  {
+    const std::string name;
+    const execution_mode mode;
+
+    const std::string&
+    key () const {return name;} // string_table interface.
+  };
+
+  using meta_operation_table = string_table<meta_operation_id,
+                                            meta_operation_info>;
+  using operation_table = string_table<operation_id, operation_info>;
 
   extern meta_operation_table meta_operations;
   extern operation_table operations;
diff --git a/build/path b/build/path
index 9644b6a..5c492f7 100644
--- a/build/path
+++ b/build/path
@@ -7,8 +7,9 @@
 
 #include <string>
 #include <ostream>
-#include <utility> // move
+#include <utility>    // move
 #include <exception>
+#include <functional> // hash
 
 namespace build
 {
diff --git a/build/rule b/build/rule
index 7501f7d..8eb6b26 100644
--- a/build/rule
+++ b/build/rule
@@ -33,7 +33,6 @@ namespace build
   using operation_rule_map = std::unordered_map<std::string, target_rule_map>;
 
   extern operation_rule_map rules;
-  extern const target_rule_map* current_rules; // Rules for current operation.
 
   // Fallback rule that on update verifies that the path exists and is
   // not older than any of its prerequisites.
diff --git a/build/rule.cxx b/build/rule.cxx
index eb7f5b4..c6bfe7a 100644
--- a/build/rule.cxx
+++ b/build/rule.cxx
@@ -18,7 +18,6 @@ using namespace std;
 namespace build
 {
   operation_rule_map rules;
-  const target_rule_map* current_rules;
 
   // path_rule
   //
@@ -247,11 +246,6 @@ namespace build
   target_state fsdir_rule::
   perform_clean (action a, target& t)
   {
-    // Wait until the last dependent to get an empty directory.
-    //
-    if (t.dependents != 0)
-      return target_state::postponed;
-
     // The reverse order of update: first delete this directory,
     // then clean prerequisites (e.g., delete parent directories).
     //
@@ -306,7 +300,7 @@ namespace build
     target_state ts (target_state::unchanged);
 
     if (!t.prerequisites.empty ())
-      ts = execute_prerequisites (a, t);
+      ts = reverse_execute_prerequisites (a, t);
 
     // If we couldn't remove the directory, return postponed meaning
     // that the operation could not be performed at this time.
diff --git a/build/target b/build/target
index 3d395d4..4405104 100644
--- a/build/target
+++ b/build/target
@@ -56,8 +56,11 @@ namespace build
   using recipe = std::function<recipe_function>;
 
   // Commonly-used recipes. The default recipe executes the action
-  // on all the prerequisites in a loop, skipping ignored (see the
-  // execute_prerequisites() in <algorithm> for details).
+  // on all the prerequisites in a loop, skipping ignored. Specially,
+  // for actions with the "first" execution mode, it calls
+  // execute_prerequisites() while for those with the "last" mode --
+  // reverse_execute_prerequisites(); see <operation>, <algorithm>
+  // for details.
   //
   extern const recipe empty_recipe;
   extern const recipe noop_recipe;
@@ -110,7 +113,7 @@ namespace build
     // action. It is incremented during the match phase and then decremented
     // during execution, before running the recipe. As a result, the recipe
     // can detect the last chance (i.e., last dependent) to execute the
-    // command (see alsoe first/last execution modes in <operation>).
+    // command (see also the first/last execution modes in <operation>).
     //
     // Note that setting a new recipe (which happens when we match the rule
     // and which in turn is triggered by the first dependent) clears this
diff --git a/build/target.cxx b/build/target.cxx
index 15d57ca..347a382 100644
--- a/build/target.cxx
+++ b/build/target.cxx
@@ -16,11 +16,6 @@ namespace build
 {
   // recipe
   //
-  const recipe empty_recipe;
-  const recipe noop_recipe (&noop_recipe_function);
-  const recipe default_recipe (
-    static_cast<recipe_function*> (&execute_prerequisites));
-
   target_state
   noop_recipe_function (action, target&)
   {
@@ -28,6 +23,18 @@ namespace build
     return target_state::unchanged;
   }
 
+  static target_state
+  default_recipe_function (action a, target& t)
+  {
+    return current_mode == execution_mode::first
+      ? execute_prerequisites (a, t)
+      : reverse_execute_prerequisites (a, t);
+  }
+
+  const recipe empty_recipe;
+  const recipe noop_recipe (&noop_recipe_function);
+  const recipe default_recipe (&default_recipe_function);
+
   // target
   //
   ostream&
diff --git a/build/utility b/build/utility
index 93fb441..cd0d8ad 100644
--- a/build/utility
+++ b/build/utility
@@ -16,6 +16,7 @@
 #include <unordered_set>
 #include <unordered_map>
 
+#include <build/key-set>
 #include <build/path>
 
 namespace build
@@ -41,6 +42,36 @@ namespace build
     bool operator() (const P& x, const P& y) const {return *x < *y;}
   };
 
+  // Support for reverse iteration using range-based for-loop:
+  //
+  // for (... : reverse_iterate (x)) ...
+  //
+  template <typename T>
+  class reverse_range
+  {
+    T& x_;
+
+  public:
+    reverse_range (T& x): x_ (x) {}
+
+    auto begin () const -> decltype (this->x_.rbegin ())
+    {
+      return x_.rbegin ();
+    }
+
+    auto end () const -> decltype (this->x_.rend ())
+    {
+      return x_.rend ();
+    }
+  };
+
+  template <typename T>
+  inline reverse_range<T>
+  reverse_iterate (T& x)
+  {
+    return reverse_range<T> (x);
+  }
+
   // Call a function if there is an exception.
   //
 
@@ -99,51 +130,94 @@ namespace build
 
   extern string_pool extension_pool;
 
-  // A pool of strings in which each string is assigned an individual
-  // index (or id) of type I (e.g., uint8_t, uint16_t, etc., depending
-  // on how many entries are expected). Index value 0 is reserved to
-  // indicate the no entry condition.
+  // A pool of strings and, optionally, other accompanying data in which
+  // each entry is assigned an individual index (or id) of type I (e.g.,
+  // uint8_t, uint16_t, etc., depending on how many entries are expected).
+  // Index value 0 is reserved to indicate the no entry condition.
   //
+  template <typename I, typename D>
+  struct string_table_element
+  {
+    const I i;
+    const D d;
+  };
+
   template <typename I>
+  struct string_table_element<I, std::string>
+  {
+    const I i;
+    const std::string d;
+  };
+
+  template <typename D>
+  struct string_table_traits
+  {
+    // By default, look for the key() function in D. But you can
+    // also specialize this class template.
+    //
+    static const std::string&
+    key (const D& d) {return d.key ();}
+  };
+
+  template <>
+  struct string_table_traits<std::string>
+  {
+    static const std::string&
+    key (const std::string& d) {return d;}
+  };
+
+  template <typename I, typename D = std::string>
   struct string_table
   {
-    // Find existing or insert new.
+    // Insert new entry unless one already exists.
     //
     I
-    insert (const std::string& s)
+    insert (const D& d)
     {
       std::size_t i (vec_.size () + 1);
-      auto r (map_.emplace (s, static_cast<I> (i)));
+
+      // Note: move(d) would be tricky since key still points to it.
+      //
+      auto r (map_.emplace (
+                key_type (&traits::key (d)),
+                value_type {static_cast<I> (i), d}));
 
       if (r.second)
       {
         assert (i <= std::numeric_limits<I>::max ());
-        vec_.push_back (&r.first->first);
+
+        r.first->first.p = &traits::key (r.first->second.d); // Update key.
+        vec_.push_back (r.first);
       }
 
-      return r.first->second;
+      return r.first->second.i;
     }
 
     // Find existing.
     //
     I
-    find (const std::string& s) const
+    find (const std::string& k) const
     {
-      auto i (map_.find (s));
-      return i != map_.end () ? i->second : 0;
+      auto i (map_.find (key_type (&k)));
+      return i != map_.end () ? i->second.i : 0;
     }
 
     // Reverse lookup.
     //
-    const std::string&
-    operator[] (I i) const {assert (i > 0); return *vec_[i - 1];}
+    const D&
+    operator[] (I i) const {assert (i > 0); return vec_[i - 1]->second.d;}
 
     I
     size () const {return static_cast<I> (vec_.size ());}
 
   private:
-    std::unordered_map<std::string, I> map_;
-    std::vector<const std::string*> vec_;
+    using key_type = set_key<std::string>;
+    using value_type = string_table_element<I, D>;
+    using map_type = std::unordered_map<key_type, value_type>;
+    using traits = string_table_traits<D>;
+
+    map_type map_;
+    std::vector<typename map_type::const_iterator> vec_;
   };
 }
 
diff --git a/build/variable b/build/variable
index ae4c7b3..901f5c8 100644
--- a/build/variable
+++ b/build/variable
@@ -9,6 +9,7 @@
 #include <memory>        // unique_ptr
 #include <utility>       // move()
 #include <cassert>
+#include <functional>    // hash
 #include <typeindex>
 #include <unordered_set>