From ca41ca8f9a6b21588248e5fee1a013363f3f52a8 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Fri, 13 Mar 2015 14:34:24 +0200 Subject: Add support for "first" and "last" execution modes --- build/algorithm | 5 +++ build/algorithm.cxx | 21 ++++++++++- build/algorithm.ixx | 12 +++++- build/b.cxx | 14 ++++--- build/context | 7 ++++ build/context.cxx | 3 ++ build/key-set | 18 +++++++++ build/operation | 67 +++++++++++++++++++++++++++++++-- build/path | 3 +- build/rule | 1 - build/rule.cxx | 8 +--- build/target | 9 +++-- build/target.cxx | 17 ++++++--- build/utility | 106 ++++++++++++++++++++++++++++++++++++++++++++-------- build/variable | 1 + buildfile | 4 ++ 16 files changed, 252 insertions(+), 44 deletions(-) create mode 100644 buildfile 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 + 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 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 #include +#include +#include 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 // declval() +#include // 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 @@ -38,4 +42,18 @@ namespace build }; } +namespace std +{ + template + struct hash>: hash + { + size_t + operator() (build::set_key x) const + noexcept (noexcept (declval> () (*x.p))) + { + return hash::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; - using operation_table = string_table; + // 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 ). 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; + using operation_table = string_table; 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 #include -#include // move +#include // move #include +#include // 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; 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; // Commonly-used recipes. The default recipe executes the action - // on all the prerequisites in a loop, skipping ignored (see the - // execute_prerequisites() in 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 , + // 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 ). + // command (see also the first/last execution modes in ). // // 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 (&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 #include +#include #include 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 + 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 + inline reverse_range + reverse_iterate (T& x) + { + return reverse_range (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 + struct string_table_element + { + const I i; + const D d; + }; + template + struct string_table_element + { + const I i; + const std::string d; + }; + + template + 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 + { + static const std::string& + key (const std::string& d) {return d;} + }; + + template 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))); + + // 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), d})); if (r.second) { assert (i <= std::numeric_limits::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 (vec_.size ());} private: - std::unordered_map map_; - std::vector vec_; + using key_type = set_key; + using value_type = string_table_element; + using map_type = std::unordered_map; + using traits = string_table_traits; + + map_type map_; + std::vector vec_; }; } diff --git a/build/variable b/build/variable index ae4c7b3..901f5c8 100644 --- a/build/variable +++ b/build/variable @@ -9,6 +9,7 @@ #include // unique_ptr #include // move() #include +#include // hash #include #include diff --git a/buildfile b/buildfile new file mode 100644 index 0000000..fad74af --- /dev/null +++ b/buildfile @@ -0,0 +1,4 @@ +d=build/ tests/build/ + +.: $d +include $d -- cgit v1.1