aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2015-03-13 14:34:24 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2015-03-13 14:34:24 +0200
commitca41ca8f9a6b21588248e5fee1a013363f3f52a8 (patch)
tree6e791ddac1c6f794273a9701c0c7f1bc9ec3d000
parent0cee33621a93d3348a1bf19a0c94441b717cbcbc (diff)
Add support for "first" and "last" execution modes
-rw-r--r--build/algorithm5
-rw-r--r--build/algorithm.cxx21
-rw-r--r--build/algorithm.ixx12
-rw-r--r--build/b.cxx14
-rw-r--r--build/context7
-rw-r--r--build/context.cxx3
-rw-r--r--build/key-set18
-rw-r--r--build/operation67
-rw-r--r--build/path3
-rw-r--r--build/rule1
-rw-r--r--build/rule.cxx8
-rw-r--r--build/target9
-rw-r--r--build/target.cxx17
-rw-r--r--build/utility106
-rw-r--r--build/variable1
-rw-r--r--buildfile4
16 files changed, 252 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>
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