aboutsummaryrefslogtreecommitdiff
path: root/build2/algorithm.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'build2/algorithm.cxx')
-rw-r--r--build2/algorithm.cxx504
1 files changed, 504 insertions, 0 deletions
diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx
new file mode 100644
index 0000000..243519e
--- /dev/null
+++ b/build2/algorithm.cxx
@@ -0,0 +1,504 @@
+// file : build2/algorithm.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
+// license : MIT; see accompanying LICENSE file
+
+#include <build2/algorithm>
+
+#include <memory> // unique_ptr
+#include <cstddef> // size_t
+#include <utility> // move
+#include <cassert>
+
+#include <butl/utility> // reverse_iterate
+
+#include <build2/scope>
+#include <build2/target>
+#include <build2/prerequisite>
+#include <build2/rule>
+#include <build2/file> // import()
+#include <build2/search>
+#include <build2/context>
+#include <build2/utility>
+#include <build2/diagnostics>
+
+using namespace std;
+using namespace butl;
+
+namespace build2
+{
+ target&
+ search (const prerequisite_key& pk)
+ {
+ // If this is a project-qualified prerequisite, then this
+ // is import's business.
+ //
+ if (pk.proj != nullptr)
+ return import (pk);
+
+ if (target* t = pk.tk.type->search (pk))
+ return *t;
+
+ return create_new_target (pk);
+ }
+
+ target&
+ search (name n, scope& s)
+ {
+ const string* e;
+ const target_type* tt (s.find_target_type (n, e));
+
+ if (tt == nullptr)
+ fail << "unknown target type " << n.type << " in name " << n;
+
+ n.dir.normalize ();
+
+ return search (*tt, move (n.dir), move (n.value), e, &s);
+ }
+
+ pair<const rule*, match_result>
+ match_impl (action a, target& t, bool apply)
+ {
+ pair<const rule*, match_result> r;
+
+ // By default, clear the resolved targets list before calling
+ // match(). The rule is free to modify this list in match()
+ // (provided that it matches) in order to, for example, prepare
+ // it for apply().
+ //
+ t.reset (a);
+
+ // If this is a nested operation, first try the outer operation.
+ // This allows a rule to implement a "precise match", that is,
+ // both inner and outer operations match.
+ //
+ for (operation_id oo (a.outer_operation ()), io (a.operation ()),
+ o (oo != 0 ? oo : io); o != 0; o = (oo != 0 ? io : 0))
+ {
+ // Adjust action for recipe: on the first iteration we want it
+ // {inner, outer} (which is the same as 'a') while on the second
+ // -- {inner, 0}. Note that {inner, 0} is the same or "stronger"
+ // (i.e., overrides; see action::operator<()) than 'a'. This
+ // allows "unconditional inner" to override "inner for outer"
+ // recipes.
+ //
+ action ra (a.meta_operation (), io, o != oo ? 0 : oo);
+
+ scope& bs (t.base_scope ());
+
+ for (auto tt (&t.type ()); tt != nullptr; tt = tt->base)
+ {
+ // Search scopes outwards, stopping at the project root.
+ //
+ for (const scope* s (&bs);
+ s != nullptr;
+ s = s->root () ? global_scope : s->parent_scope ())
+ {
+ const operation_rule_map* om (s->rules[a.meta_operation ()]);
+
+ if (om == nullptr)
+ continue; // No entry for this meta-operation id.
+
+ // First try the map for the actual operation. If that
+ // doesn't yeld anything, try the wildcard map.
+ //
+ for (size_t oi (o), oip (o); oip != 0; oip = oi, oi = 0)
+ {
+ const target_type_rule_map* ttm ((*om)[oi]);
+
+ if (ttm == nullptr)
+ continue; // No entry for this operation id.
+
+ if (ttm->empty ())
+ continue; // Empty map for this operation id.
+
+ auto i (ttm->find (tt));
+
+ if (i == ttm->end () || i->second.empty ())
+ continue; // No rules registered for this target type.
+
+ const auto& rules (i->second); // Hint map.
+
+ // @@ TODO
+ //
+ // Different rules can be used for different operations (update
+ // vs test is a good example). So, at some point, we will probably
+ // have to support a list of hints or even an operation-hint map
+ // (e.g., 'hint=cxx test=foo' if cxx supports the test operation
+ // but we want the foo rule instead). This is also the place where
+ // the '{build clean}=cxx' construct (which we currently do not
+ // support) can come handy.
+ //
+ // Also, ignore the hint (that is most likely ment for a different
+ // operation) if this is a unique match.
+ //
+ string hint;
+ auto rs (rules.size () == 1
+ ? make_pair (rules.begin (), rules.end ())
+ : rules.find_prefix (hint));
+
+ for (auto i (rs.first); i != rs.second; ++i)
+ {
+ const string& n (i->first);
+ const rule& ru (i->second);
+
+ match_result m;
+ {
+ auto g (
+ make_exception_guard (
+ [ra, &t, &n]()
+ {
+ info << "while matching rule " << n << " to "
+ << diag_do (ra, t);
+ }));
+
+ if (!(m = ru.match (ra, t, hint)))
+ continue;
+
+ if (!m.recipe_action.valid ())
+ m.recipe_action = ra; // Default, if not set.
+ }
+
+ // Do the ambiguity test.
+ //
+ bool ambig (false);
+
+ diag_record dr;
+
+ for (++i; i != rs.second; ++i)
+ {
+ const string& n1 (i->first);
+ const rule& ru1 (i->second);
+
+ {
+ auto g (
+ make_exception_guard (
+ [ra, &t, &n1]()
+ {
+ info << "while matching rule " << n1 << " to "
+ << diag_do (ra, t);
+ }));
+
+ if (!ru1.match (ra, t, hint))
+ continue;
+ }
+
+ if (!ambig)
+ {
+ dr << fail << "multiple rules matching "
+ << diag_doing (ra, t)
+ << info << "rule " << n << " matches";
+ ambig = true;
+ }
+
+ dr << info << "rule " << n1 << " also matches";
+ }
+
+ if (!ambig)
+ {
+ ra = m.recipe_action; // Use custom, if set.
+
+ if (apply)
+ {
+ auto g (
+ make_exception_guard (
+ [ra, &t, &n]()
+ {
+ info << "while applying rule " << n << " to "
+ << diag_do (ra, t);
+ }));
+
+ // @@ We could also allow the rule to change the recipe
+ // action in apply(). Could be useful with delegates.
+ //
+ t.recipe (ra, ru.apply (ra, t, m));
+ }
+ else
+ {
+ r.first = &ru;
+ r.second = move (m);
+ }
+
+ return r;
+ }
+ else
+ dr << info << "use rule hint to disambiguate this match";
+ }
+ }
+ }
+ }
+ }
+
+ diag_record dr;
+ dr << fail << "no rule to " << diag_do (a, t);
+
+ if (verb < 4)
+ dr << info << "re-run with --verbose 4 for more information";
+
+ return r;
+ }
+
+ group_view
+ resolve_group_members_impl (action a, target& g)
+ {
+ group_view r;
+
+ // Unless we already have a recipe, try matching the target to
+ // the rule.
+ //
+ if (!g.recipe (a))
+ {
+ auto rp (match_impl (a, g, false));
+
+ r = g.group_members (a);
+ if (r.members != nullptr)
+ return r;
+
+ // That didn't help, so apply the rule and go to the building
+ // phase.
+ //
+ const match_result& mr (rp.second);
+ g.recipe (mr.recipe_action, rp.first->apply (mr.recipe_action, g, mr));
+ }
+
+ // Note that we use execute_direct() rather than execute() here to
+ // sidestep the dependents count logic. In this context, this is by
+ // definition the first attempt to execute this rule (otherwise we
+ // would have already known the members list) and we really do need
+ // to execute it now.
+ //
+ execute_direct (a, g);
+
+ r = g.group_members (a);
+ return r; // Might still be unresolved.
+ }
+
+ void
+ search_and_match_prerequisites (action a, target& t, const dir_path& d)
+ {
+ const bool e (d.empty ());
+
+ for (prerequisite p: group_prerequisites (t))
+ {
+ target& pt (search (p));
+
+ if (e || pt.dir.sub (d))
+ {
+ match (a, pt);
+ t.prerequisite_targets.push_back (&pt);
+ }
+ }
+ }
+
+ void
+ search_and_match_prerequisite_members (action a,
+ target& t,
+ const dir_path& d)
+ {
+ const bool e (d.empty ());
+
+ for (prerequisite_member p: group_prerequisite_members (a, t))
+ {
+ target& pt (p.search ());
+
+ if (e || pt.dir.sub (d))
+ {
+ match (a, pt);
+ t.prerequisite_targets.push_back (&pt);
+ }
+ }
+ }
+
+ void
+ inject_parent_fsdir (action a, target& t)
+ {
+ tracer trace ("inject_parent_fsdir");
+
+ scope& s (t.base_scope ());
+ scope* rs (s.root_scope ());
+
+ if (rs == nullptr) // Could be outside any project.
+ return;
+
+ const dir_path& out_root (rs->out_path ());
+
+ // If t is a directory (name is empty), say foo/bar/, then
+ // t is bar and its parent directory is foo/.
+ //
+ const dir_path& d (t.name.empty () ? t.dir.directory () : t.dir);
+
+ if (!d.sub (out_root) || d == out_root)
+ return;
+
+ level6 ([&]{trace << "for " << t;});
+
+ fsdir& dt (search<fsdir> (d, string (), nullptr, &s));
+ match (a, dt);
+ t.prerequisite_targets.emplace_back (&dt);
+ }
+
+ target_state
+ execute_impl (action a, target& t)
+ {
+ // Implementation with some multi-threading ideas in mind.
+ //
+ switch (t.raw_state)
+ {
+ case target_state::group: // Means group's state is unknown.
+ case target_state::unknown:
+ case target_state::postponed:
+ {
+ auto g (
+ make_exception_guard (
+ [a, &t]()
+ {
+ t.raw_state = target_state::failed;
+ info << "while " << diag_doing (a, t);
+ }));
+
+ target_state ts (t.recipe (a) (a, t));
+ assert (ts != target_state::unknown && ts != target_state::failed);
+
+ // Set the target's state unless it should be the group's state.
+ //
+ if (t.raw_state != target_state::group)
+ t.raw_state = ts;
+
+ return ts;
+ }
+ case target_state::unchanged:
+ case target_state::changed:
+ // Should have been handled by inline execute().
+ assert (false);
+ case target_state::failed:
+ break;
+ }
+
+ throw failed ();
+ }
+
+ target_state
+ execute_prerequisites (action a, target& t)
+ {
+ target_state r (target_state::unchanged);
+
+ for (target* pt: t.prerequisite_targets)
+ {
+ if (pt == nullptr) // Skipped.
+ continue;
+
+ r |= execute (a, *pt);
+ }
+
+ return r;
+ }
+
+ target_state
+ reverse_execute_prerequisites (action a, target& t)
+ {
+ target_state r (target_state::unchanged);
+
+ for (target* pt: reverse_iterate (t.prerequisite_targets))
+ {
+ if (pt == nullptr) // Skipped.
+ continue;
+
+ r |= execute (a, *pt);
+ }
+
+ return r;
+ }
+
+ bool
+ execute_prerequisites (action a, target& t, const timestamp& mt)
+ {
+ bool e (mt == timestamp_nonexistent);
+
+ for (target* pt: t.prerequisite_targets)
+ {
+ if (pt == nullptr) // Skipped.
+ continue;
+
+ target_state ts (execute (a, *pt));
+
+ if (!e)
+ {
+ // If this is an mtime-based target, then compare timestamps.
+ //
+ if (auto mpt = dynamic_cast<const mtime_target*> (pt))
+ {
+ timestamp mp (mpt->mtime ());
+
+ // What do we do if timestamps are equal? This can happen, for
+ // example, on filesystems that don't have subsecond resolution.
+ // There is not much we can do here except detect the case where
+ // the prerequisite was changed in this run which means the
+ // action must be executed on the target as well.
+ //
+ if (mt < mp || (mt == mp && ts == target_state::changed))
+ e = true;
+ }
+ else
+ {
+ // Otherwise we assume the prerequisite is newer if it was changed.
+ //
+ if (ts == target_state::changed)
+ e = true;
+ }
+ }
+ }
+
+ return e;
+ }
+
+ target_state
+ noop_action (action, target&)
+ {
+ assert (false); // We shouldn't be called, see target::recipe().
+ return target_state::unchanged;
+ }
+
+ target_state
+ group_action (action a, target& t)
+ {
+ target_state r (execute (a, *t.group));
+
+ // Indicate to the standard execute() logic that this target's
+ // state comes from the group.
+ //
+ t.raw_state = target_state::group;
+
+ return r;
+ }
+
+ target_state
+ default_action (action a, target& t)
+ {
+ return current_mode == execution_mode::first
+ ? execute_prerequisites (a, t)
+ : reverse_execute_prerequisites (a, t);
+ }
+
+ target_state
+ perform_clean (action a, target& t)
+ {
+ // The reverse order of update: first delete the file, then clean
+ // prerequisites.
+ //
+ file& ft (dynamic_cast<file&> (t));
+
+ target_state r (rmfile (ft.path (), ft)
+ ? target_state::changed
+ : target_state::unchanged);
+
+ // Update timestamp in case there are operations after us that
+ // could use the information.
+ //
+ ft.mtime (timestamp_nonexistent);
+
+ // Clean prerequisites.
+ //
+ r |= reverse_execute_prerequisites (a, t);
+
+ return r;
+ }
+}