diff options
Diffstat (limited to 'libbuild2/algorithm.ixx')
| -rw-r--r-- | libbuild2/algorithm.ixx | 764 |
1 files changed, 764 insertions, 0 deletions
diff --git a/libbuild2/algorithm.ixx b/libbuild2/algorithm.ixx new file mode 100644 index 0000000..7d68611 --- /dev/null +++ b/libbuild2/algorithm.ixx @@ -0,0 +1,764 @@ +// file : libbuild2/algorithm.ixx -*- C++ -*- +// copyright : Copyright (c) 2014-2019 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#include <libbuild2/rule.hxx> +#include <libbuild2/context.hxx> + +#include <libbuild2/export.hxx> + +namespace build2 +{ + inline const target& + search (const target& t, const prerequisite& p) + { + assert (phase == run_phase::match); + + const target* r (p.target.load (memory_order_consume)); + + if (r == nullptr) + r = &search_custom (p, search (t, p.key ())); + + return *r; + } + + inline const target* + search_existing (const prerequisite& p) + { + assert (phase == run_phase::match || phase == run_phase::execute); + + const target* r (p.target.load (memory_order_consume)); + + if (r == nullptr) + { + r = search_existing (p.key ()); + + if (r != nullptr) + search_custom (p, *r); + } + + return r; + } + + inline const target& + search_custom (const prerequisite& p, const target& t) + { + assert (phase == run_phase::match || phase == run_phase::execute); + + const target* e (nullptr); + if (!p.target.compare_exchange_strong ( + e, &t, + memory_order_release, + memory_order_consume)) + assert (e == &t); + + return t; + } + + inline const target& + search (const target& t, const target_type& tt, const prerequisite_key& k) + { + return search ( + t, + prerequisite_key { + k.proj, {&tt, k.tk.dir, k.tk.out, k.tk.name, k.tk.ext}, k.scope}); + } + + inline const target& + search (const target& t, + const target_type& type, + const dir_path& dir, + const dir_path& out, + const string& name, + const string* ext, + const scope* scope, + const optional<project_name>& proj) + { + return search ( + t, + prerequisite_key { + proj, + { + &type, + &dir, &out, &name, + ext != nullptr ? optional<string> (*ext) : nullopt + }, + scope}); + } + + inline const target* + search_existing (const target_type& type, + const dir_path& dir, + const dir_path& out, + const string& name, + const string* ext, + const scope* scope, + const optional<project_name>& proj) + { + return search_existing ( + prerequisite_key { + proj, + { + &type, + &dir, &out, &name, + ext != nullptr ? optional<string> (*ext) : nullopt + }, + scope}); + } + + template <typename T> + inline const T& + search (const target& t, + const dir_path& dir, + const dir_path& out, + const string& name, + const string* ext, + const scope* scope) + { + return search ( + t, T::static_type, dir, out, name, ext, scope).template as<T> (); + } + + LIBBUILD2_SYMEXPORT target_lock + lock_impl (action, const target&, optional<scheduler::work_queue>); + + LIBBUILD2_SYMEXPORT void + unlock_impl (action, target&, size_t); + + inline target_lock:: + target_lock (action_type a, target_type* t, size_t o) + : action (a), target (t), offset (o) + { + if (target != nullptr) + prev = stack (this); + } + + inline void target_lock:: + unstack () + { + if (target != nullptr && prev != this) + { + const target_lock* cur (stack (prev)); + assert (cur == this); + prev = this; + } + } + + inline void target_lock:: + unlock () + { + if (target != nullptr) + { + unlock_impl (action, *target, offset); + + if (prev != this) + { + const target_lock* cur (stack (prev)); + assert (cur == this); + } + + target = nullptr; + } + } + + inline auto target_lock:: + release () -> data + { + data r {action, target, offset}; + + if (target != nullptr) + { + if (prev != this) + { + const target_lock* cur (stack (prev)); + assert (cur == this); + } + + target = nullptr; + } + + return r; + } + + inline target_lock:: + ~target_lock () + { + unlock (); + } + + inline target_lock:: + target_lock (target_lock&& x) + : action (x.action), target (x.target), offset (x.offset) + { + if (target != nullptr) + { + if (x.prev != &x) + { + const target_lock* cur (stack (this)); + assert (cur == &x); + prev = x.prev; + } + else + prev = this; + + x.target = nullptr; + } + } + + inline target_lock& target_lock:: + operator= (target_lock&& x) + { + if (this != &x) + { + assert (target == nullptr); + + action = x.action; + target = x.target; + offset = x.offset; + + if (target != nullptr) + { + if (x.prev != &x) + { + const target_lock* cur (stack (this)); + assert (cur == &x); + prev = x.prev; + } + else + prev = this; + + x.target = nullptr; + } + } + + return *this; + } + + inline const target_lock* + dependency_cycle (action a, const target& t) + { + const target_lock* l (target_lock::stack ()); + + for (; l != nullptr; l = l->prev) + { + if (l->action == a && l->target == &t) + break; + } + + return l; + } + + inline target_lock + lock (action a, const target& t) + { + // We don't allow locking a target that has already been matched. + // + target_lock r (lock_impl (a, t, scheduler::work_none)); + assert (!r || + r.offset == target::offset_touched || + r.offset == target::offset_tried); + return r; + } + + inline target& + add_adhoc_member (target& t, const target_type& tt, const char* e) + { + string n (t.name); + + if (e != nullptr) + { + n += '.'; + n += e; + } + + return add_adhoc_member (t, tt, t.dir, t.out, move (n)); + } + + inline target* + find_adhoc_member (target& g, const target_type& tt) + { + target* m (g.member); + for (; m != nullptr && !m->is_a (tt); m = m->member) ; + return m; + } + + inline const target* + find_adhoc_member (const target& g, const target_type& tt) + { + const target* m (g.member); + for (; m != nullptr && !m->is_a (tt); m = m->member) ; + return m; + } + + LIBBUILD2_SYMEXPORT const rule_match* + match_impl (action, target&, const rule* skip, bool try_match = false); + + LIBBUILD2_SYMEXPORT recipe + apply_impl (action, target&, const rule_match&); + + LIBBUILD2_SYMEXPORT pair<bool, target_state> + match (action, const target&, size_t, atomic_count*, bool try_match = false); + + inline void + match_inc_dependens (action a, const target& t) + { + dependency_count.fetch_add (1, memory_order_relaxed); + t[a].dependents.fetch_add (1, memory_order_release); + } + + inline target_state + match (action a, const target& t, bool fail) + { + assert (phase == run_phase::match); + + target_state r (match (a, t, 0, nullptr).second); + + if (r != target_state::failed) + match_inc_dependens (a, t); + else if (fail) + throw failed (); + + return r; + } + + inline pair<bool, target_state> + try_match (action a, const target& t, bool fail) + { + assert (phase == run_phase::match); + + pair<bool, target_state> r ( + match (a, t, 0, nullptr, true /* try_match */)); + + if (r.first) + { + if (r.second != target_state::failed) + match_inc_dependens (a, t); + else if (fail) + throw failed (); + } + + return r; + } + + inline bool + match (action a, const target& t, unmatch um) + { + assert (phase == run_phase::match); + + target_state s (match (a, t, 0, nullptr).second); + + if (s == target_state::failed) + throw failed (); + + switch (um) + { + case unmatch::none: break; + case unmatch::unchanged: + { + if (s == target_state::unchanged) + return true; + + break; + } + case unmatch::safe: + { + // Safe if unchanged or someone else is also a dependent (note that + // we never decrement this count during match so that someone else + // cannot change their mind). + // + if (s == target_state::unchanged || + t[a].dependents.load (memory_order_consume) != 0) + return true; + + break; + } + } + + match_inc_dependens (a, t); + return false; + } + + inline target_state + match_async (action a, const target& t, + size_t sc, atomic_count& tc, + bool fail) + { + assert (phase == run_phase::match); + target_state r (match (a, t, sc, &tc).second); + + if (fail && !keep_going && r == target_state::failed) + throw failed (); + + return r; + } + + inline void + set_recipe (target_lock& l, recipe&& r) + { + target::opstate& s ((*l.target)[l.action]); + + s.recipe = move (r); + + // If this is a noop recipe, then mark the target unchanged to allow for + // some optimizations. + // + recipe_function** f (s.recipe.target<recipe_function*> ()); + + if (f != nullptr && *f == &noop_action) + s.state = target_state::unchanged; + else + { + s.state = target_state::unknown; + + // This gets tricky when we start considering direct execution, etc. So + // here seems like the best place to do it. + // + // We also ignore the group recipe since group action means real recipe + // is in the group and so this feels right conceptually. + // + // We also avoid incrementing this count twice for the same target if we + // have both the inner and outer operations. In our model the outer + // operation is either noop or it must delegate to the inner. While it's + // possible the inner is noop while the outer is not, it is not very + // likely. The alternative (trying to "merge" the count keeping track of + // whether inner and/or outer is noop) gets hairy rather quickly. + // + if (l.action.inner ()) + { + if (f == nullptr || *f != &group_action) + target_count.fetch_add (1, memory_order_relaxed); + } + } + } + + inline void + match_recipe (target_lock& l, recipe r) + { + assert (phase == run_phase::match && l.target != nullptr); + + (*l.target)[l.action].rule = nullptr; // No rule. + set_recipe (l, move (r)); + l.offset = target::offset_applied; + } + + inline recipe + match_delegate (action a, target& t, const rule& dr, bool try_match) + { + assert (phase == run_phase::match); + + // Note: we don't touch any of the t[a] state since that was/will be set + // for the delegating rule. + // + const rule_match* r (match_impl (a, t, &dr, try_match)); + return r != nullptr ? apply_impl (a, t, *r) : empty_recipe; + } + + inline target_state + match_inner (action a, const target& t) + { + // In a sense this is like any other dependency. + // + assert (a.outer ()); + return match (a.inner_action (), t); + } + + inline bool + match_inner (action a, const target& t, unmatch um) + { + assert (a.outer ()); + return match (a.inner_action (), t, um); + } + + LIBBUILD2_SYMEXPORT group_view + resolve_members_impl (action, const target&, target_lock); + + inline group_view + resolve_members (action a, const target& g) + { + group_view r; + + if (a.outer ()) + a = a.inner_action (); + + // We can be called during execute though everything should have been + // already resolved. + // + switch (phase) + { + case run_phase::match: + { + // Grab a target lock to make sure the group state is synchronized. + // + target_lock l (lock_impl (a, g, scheduler::work_none)); + r = g.group_members (a); + + // If the group members are alrealy known or there is nothing else + // we can do, then unlock and return. + // + if (r.members == nullptr && l.offset != target::offset_executed) + r = resolve_members_impl (a, g, move (l)); + + break; + } + case run_phase::execute: r = g.group_members (a); break; + case run_phase::load: assert (false); + } + + return r; + } + + LIBBUILD2_SYMEXPORT void + resolve_group_impl (action, const target&, target_lock); + + inline const target* + resolve_group (action a, const target& t) + { + if (a.outer ()) + a = a.inner_action (); + + switch (phase) + { + case run_phase::match: + { + // Grab a target lock to make sure the group state is synchronized. + // + target_lock l (lock_impl (a, t, scheduler::work_none)); + + // If the group is alrealy known or there is nothing else we can do, + // then unlock and return. + // + if (t.group == nullptr && l.offset < target::offset_tried) + resolve_group_impl (a, t, move (l)); + + break; + } + case run_phase::execute: break; + case run_phase::load: assert (false); + } + + return t.group; + } + + LIBBUILD2_SYMEXPORT void + match_prerequisites (action, target&, const match_search&, const scope*); + + LIBBUILD2_SYMEXPORT void + match_prerequisite_members (action, target&, + const match_search_member&, + const scope*); + + inline void + match_prerequisites (action a, target& t, const match_search& ms) + { + match_prerequisites ( + a, + t, + ms, + (a.operation () != clean_id ? nullptr : &t.root_scope ())); + } + + inline void + match_prerequisite_members (action a, target& t, + const match_search_member& msm) + { + if (a.operation () != clean_id) + match_prerequisite_members (a, t, msm, nullptr); + else + { + // Note that here we don't iterate over members even for see-through + // groups since the group target should clean eveything up. A bit of an + // optimization. + // + match_search ms ( + msm + ? [&msm] (action a, + const target& t, + const prerequisite& p, + include_type i) + { + return msm (a, t, prerequisite_member {p, nullptr}, i); + } + : match_search ()); + + match_prerequisites (a, t, ms, &t.root_scope ()); + } + } + + inline void + match_prerequisites (action a, target& t, const scope& s) + { + match_prerequisites (a, t, nullptr, &s); + } + + inline void + match_prerequisite_members (action a, target& t, const scope& s) + { + match_prerequisite_members (a, t, nullptr, &s); + } + + LIBBUILD2_SYMEXPORT target_state + execute (action, const target&, size_t, atomic_count*); + + inline target_state + execute (action a, const target& t) + { + return execute (a, t, 0, nullptr); + } + + inline target_state + execute_wait (action a, const target& t) + { + if (execute (a, t) == target_state::busy) + sched.wait (target::count_executed (), + t[a].task_count, + scheduler::work_none); + + return t.executed_state (a); + } + + inline target_state + execute_async (action a, const target& t, + size_t sc, atomic_count& tc, + bool fail) + { + target_state r (execute (a, t, sc, &tc)); + + if (fail && !keep_going && r == target_state::failed) + throw failed (); + + return r; + } + + inline target_state + execute_delegate (const recipe& r, action a, const target& t) + { + return r (a, t); + } + + inline target_state + execute_inner (action a, const target& t) + { + assert (a.outer ()); + return execute_wait (a.inner_action (), t); + } + + inline target_state + straight_execute_prerequisites (action a, const target& t, + size_t c, size_t s) + { + auto& p (t.prerequisite_targets[a]); + return straight_execute_members (a, t, + p.data (), + c == 0 ? p.size () - s: c, + s); + } + + inline target_state + reverse_execute_prerequisites (action a, const target& t, size_t c) + { + auto& p (t.prerequisite_targets[a]); + return reverse_execute_members (a, t, + p.data (), + c == 0 ? p.size () : c, + p.size ()); + } + + inline target_state + execute_prerequisites (action a, const target& t, size_t c) + { + return current_mode == execution_mode::first + ? straight_execute_prerequisites (a, t, c) + : reverse_execute_prerequisites (a, t, c); + } + + inline target_state + straight_execute_prerequisites_inner (action a, const target& t, + size_t c, size_t s) + { + assert (a.outer ()); + auto& p (t.prerequisite_targets[a]); + return straight_execute_members (a.inner_action (), + t[a].task_count, + p.data (), + c == 0 ? p.size () - s : c, + s); + } + + inline target_state + reverse_execute_prerequisites_inner (action a, const target& t, size_t c) + { + assert (a.outer ()); + auto& p (t.prerequisite_targets[a]); + return reverse_execute_members (a.inner_action (), + t[a].task_count, + p.data (), + c == 0 ? p.size () : c, + p.size ()); + } + + inline target_state + execute_prerequisites_inner (action a, const target& t, size_t c) + { + return current_mode == execution_mode::first + ? straight_execute_prerequisites_inner (a, t, c) + : reverse_execute_prerequisites_inner (a, t, c); + } + + // If the first argument is NULL, then the result is treated as a boolean + // value. + // + LIBBUILD2_SYMEXPORT pair<optional<target_state>, const target*> + execute_prerequisites (const target_type*, + action, const target&, + const timestamp&, const execute_filter&, + size_t); + + inline optional<target_state> + execute_prerequisites (action a, const target& t, + const timestamp& mt, const execute_filter& ef, + size_t n) + { + return execute_prerequisites (nullptr, a, t, mt, ef, n).first; + } + + template <typename T> + inline pair<optional<target_state>, const T&> + execute_prerequisites (action a, const target& t, + const timestamp& mt, const execute_filter& ef, + size_t n) + { + auto p (execute_prerequisites (T::static_type, a, t, mt, ef, n)); + return pair<optional<target_state>, const T&> ( + p.first, static_cast<const T&> (p.second)); + } + + inline pair<optional<target_state>, const target&> + execute_prerequisites (const target_type& tt, + action a, const target& t, + const timestamp& mt, const execute_filter& ef, + size_t n) + { + auto p (execute_prerequisites (&tt, a, t, mt, ef, n)); + return pair<optional<target_state>, const target&> (p.first, *p.second); + } + + template <typename T> + inline pair<optional<target_state>, const T&> + execute_prerequisites (const target_type& tt, + action a, const target& t, + const timestamp& mt, const execute_filter& ef, + size_t n) + { + auto p (execute_prerequisites (tt, a, t, mt, ef, n)); + return pair<optional<target_state>, const T&> ( + p.first, static_cast<const T&> (p.second)); + } + + inline target_state + execute_members (action a, const target& t, const target* ts[], size_t n) + { + return current_mode == execution_mode::first + ? straight_execute_members (a, t, ts, n, 0) + : reverse_execute_members (a, t, ts, n, n); + } +} |