From 977d07a3ae47ef204665d1eda2d642e5064724f3 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 24 Jun 2019 12:01:19 +0200 Subject: Split build system into library and driver --- libbuild2/scope.cxx | 911 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 911 insertions(+) create mode 100644 libbuild2/scope.cxx (limited to 'libbuild2/scope.cxx') diff --git a/libbuild2/scope.cxx b/libbuild2/scope.cxx new file mode 100644 index 0000000..1ad7455 --- /dev/null +++ b/libbuild2/scope.cxx @@ -0,0 +1,911 @@ +// file : libbuild2/scope.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2019 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#include + +#include +#include + +using namespace std; + +namespace build2 +{ + // scope + // + pair scope:: + find_original (const variable& var, + const target_type* tt, const string* tn, + const target_type* gt, const string* gn, + size_t start_d) const + { + assert (tt != nullptr || var.visibility != variable_visibility::target); + + size_t d (0); + + if (var.visibility == variable_visibility::prereq) + return make_pair (lookup (), d); + + // Process target type/pattern-specific prepend/append values. + // + auto pre_app = [&var] (lookup& l, + const scope* s, + const target_type* tt, const string* tn, + const target_type* gt, const string* gn) + { + const value& v (*l); + assert ((v.extra == 1 || v.extra == 2) && v.type == nullptr); + + // First we need to look for the stem value starting from the "next + // lookup point". That is, if we have the group, then from the + // s->target_vars (for the group), otherwise from s->vars, and then + // continuing looking in the outer scopes (for both target and group). + // Note that this may have to be repeated recursively, i.e., we may have + // prepents/appends in outer scopes. Also, if the value is for the + // group, then we shouldn't be looking for stem in the target's + // variables. In other words, once we "jump" to group, we stay there. + // + lookup stem (s->find_original (var, tt, tn, gt, gn, 2).first); + + // Check the cache. + // + pair entry ( + s->target_vars.cache.insert ( + make_tuple (&v, tt, *tn), + stem, + static_cast (v).version, + var)); + + value& cv (entry.first); + + // If cache miss/invalidation, update the value. + // + if (entry.second.owns_lock ()) + { + // Un-typify the cache. This can be necessary, for example, if we are + // changing from one value-typed stem to another. + // + // Note: very similar logic as in the override cache population code + // below. + // + if (!stem.defined () || cv.type != stem->type) + { + cv = nullptr; + cv.type = nullptr; // Un-typify. + } + + // Copy the stem. + // + if (stem.defined ()) + cv = *stem; + + // Typify the cache value in case there is no stem (we still want to + // prepend/append things in type-aware way). + // + if (cv.type == nullptr && var.type != nullptr) + typify (cv, *var.type, &var); + + // Now prepend/append the value, unless it is NULL. + // + if (v) + { + if (v.extra == 1) + cv.prepend (names (cast (v)), &var); + else + cv.append (names (cast (v)), &var); + } + } + + // Return cache as the resulting value but retain l.var/vars, so it + // looks as if the value came from s->target_vars. + // + l.value = &cv; + }; + + for (const scope* s (this); s != nullptr; ) + { + if (tt != nullptr) // This started from the target. + { + bool f (!s->target_vars.empty ()); + + // Target. + // + if (++d >= start_d) + { + if (f) + { + lookup l (s->target_vars.find (*tt, *tn, var)); + + if (l.defined ()) + { + if (l->extra != 0) // Prepend/append? + pre_app (l, s, tt, tn, gt, gn); + + return make_pair (move (l), d); + } + } + } + + // Group. + // + if (++d >= start_d) + { + if (f && gt != nullptr) + { + lookup l (s->target_vars.find (*gt, *gn, var)); + + if (l.defined ()) + { + if (l->extra != 0) // Prepend/append? + pre_app (l, s, gt, gn, nullptr, nullptr); + + return make_pair (move (l), d); + } + } + } + } + + // Note that we still increment the lookup depth so that we can compare + // depths of variables with different visibilities. + // + if (++d >= start_d && var.visibility != variable_visibility::target) + { + auto p (s->vars.find (var)); + if (p.first != nullptr) + return make_pair (lookup (*p.first, p.second, s->vars), d); + } + + switch (var.visibility) + { + case variable_visibility::scope: + s = nullptr; + break; + case variable_visibility::target: + case variable_visibility::project: + s = s->root () ? nullptr : s->parent_scope (); + break; + case variable_visibility::normal: + s = s->parent_scope (); + break; + case variable_visibility::prereq: + assert (false); + } + } + + return make_pair (lookup (), size_t (~0)); + } + + pair scope:: + find_override (const variable& var, + pair original, + bool target, + bool rule) const + { + assert (!rule || target); // Rule-specific is target-specific. + + // Normally there would be no overrides and if there are, there will only + // be a few of them. As a result, here we concentrate on keeping the logic + // as straightforward as possible without trying to optimize anything. + // + // Note also that we rely (e.g., in the config module) on the fact that if + // no overrides apply, then we return the original value and not its copy + // in the cache (this is used to detect if the value was overriden). + // + assert (var.overrides != nullptr); + + const lookup& orig (original.first); + size_t orig_depth (original.second); + + // The first step is to find out where our cache will reside. After some + // meditation you will see it should be next to the innermost (scope-wise) + // value of this variable (override or original). + // + // We also keep track of the root scope of the project from which this + // innermost value comes. This is used to decide whether a non-recursive + // project-wise override applies. And also where our variable cache is. + // + const variable_map* inner_vars (nullptr); + const scope* inner_proj (nullptr); + + // One special case is if the original is target/rule-specific, which is + // the most innermost. Or is it innermostest? + // + bool targetspec (false); + if (target) + { + targetspec = orig.defined () && (orig_depth == 1 || + orig_depth == 2 || + (rule && orig_depth == 3)); + if (targetspec) + { + inner_vars = orig.vars; + inner_proj = root_scope (); + } + } + + const scope* s; + + // Return true if the override applies to a value from vars/proj. Note + // that it expects vars and proj to be not NULL; if there is nothing "more + // inner", then any override will still be "visible". + // + auto applies = [&s] (const variable* o, + const variable_map* vars, + const scope* proj) -> bool + { + switch (o->visibility) + { + case variable_visibility::scope: + { + // Does not apply if in a different scope. + // + if (vars != &s->vars) + return false; + + break; + } + case variable_visibility::project: + { + // Does not apply if in a subproject. + // + // Note that before we used to require the same project but that + // missed values that are "visible" from the outer projects. + // + // If root scope is NULL, then we are looking at the global scope. + // + const scope* rs (s->root_scope ()); + if (rs != nullptr && rs->sub_root (*proj)) + return false; + + break; + } + case variable_visibility::normal: + break; + case variable_visibility::target: + case variable_visibility::prereq: + assert (false); + } + + return true; + }; + + // Return the override value if present in scope s and (optionally) of + // the specified kind (__override, __prefix, etc). + // + auto find = [&s, &var] (const variable* o, + const char* k = nullptr) -> lookup + { + if (k != nullptr && !o->override (k)) + return lookup (); + + // Note: using the original as storage variable. + // + return lookup (s->vars.find (*o).first, &var, &s->vars); + }; + + // Return true if a value is from this scope (either target type/pattern- + // specific or ordinary). + // + auto belongs = [&s, target] (const lookup& l) -> bool + { + if (target) + { + for (auto& p1: s->target_vars) + for (auto& p2: p1.second) + if (l.vars == &p2.second) + return true; + } + + return l.vars == &s->vars; + }; + + // While looking for the cache we also detect if none of the overrides + // apply. In this case the result is simply the original value (if any). + // + bool apply (false); + + for (s = this; s != nullptr; s = s->parent_scope ()) + { + // If we are still looking for the cache, see if the original comes from + // this scope. We check this before the overrides since it can come from + // the target type/patter-specific variables, which is "more inner" than + // normal scope variables (see find_original()). + // + if (inner_vars == nullptr && orig.defined () && belongs (orig)) + { + inner_vars = orig.vars; + inner_proj = s->root_scope (); + } + + for (const variable* o (var.overrides.get ()); + o != nullptr; + o = o->overrides.get ()) + { + if (inner_vars != nullptr && !applies (o, inner_vars, inner_proj)) + continue; + + auto l (find (o)); + + if (l.defined ()) + { + if (inner_vars == nullptr) + { + inner_vars = l.vars; + inner_proj = s->root_scope (); + } + + apply = true; + break; + } + } + + // We can stop if we found the cache and at least one override applies. + // + if (inner_vars != nullptr && apply) + break; + } + + if (!apply) + return original; + + assert (inner_vars != nullptr); + + // If for some reason we are not in a project, use the cache from the + // global scope. + // + if (inner_proj == nullptr) + inner_proj = global_scope; + + // Now find our "stem", that is, the value to which we will be appending + // suffixes and prepending prefixes. This is either the original or the + // __override, provided it applies. We may also not have either. + // + lookup stem; + size_t stem_depth (0); + const scope* stem_proj (nullptr); + const variable* stem_ovr (nullptr); // __override if found and applies. + + // Again the special case of a target/rule-specific variable. + // + if (targetspec) + { + stem = orig; + stem_depth = orig_depth; + stem_proj = root_scope (); + } + + // Depth at which we found the override (with implied target/rule-specific + // lookup counts). + // + size_t ovr_depth (target ? (rule ? 3 : 2) : 0); + + for (s = this; s != nullptr; s = s->parent_scope ()) + { + bool done (false); + + // First check if the original is from this scope. + // + if (orig.defined () && belongs (orig)) + { + stem = orig; + stem_depth = orig_depth; + stem_proj = s->root_scope (); + // Keep searching. + } + + ++ovr_depth; + + // Then look for an __override that applies. + // + // Note that the override list is in the reverse order of appearance and + // so we will naturally see the most recent override first. + // + for (const variable* o (var.overrides.get ()); + o != nullptr; + o = o->overrides.get ()) + { + // If we haven't yet found anything, then any override will still be + // "visible" even if it doesn't apply. + // + if (stem.defined () && !applies (o, stem.vars, stem_proj)) + continue; + + auto l (find (o, "__override")); + + if (l.defined ()) + { + stem = move (l); + stem_depth = ovr_depth; + stem_proj = s->root_scope (); + stem_ovr = o; + done = true; + break; + } + } + + if (done) + break; + } + + // Check the cache. + // + variable_override_cache& cache ( + inner_proj == global_scope + ? global_override_cache + : inner_proj->root_extra->override_cache); + + pair entry ( + cache.insert ( + make_pair (&var, inner_vars), + stem, + 0, // Overrides are immutable. + var)); + + value& cv (entry.first); + bool cl (entry.second.owns_lock ()); + + // If cache miss/invalidation, update the value. + // + if (cl) + { + // Note: very similar logic as in the target type/pattern specific cache + // population code above. + // + + // Un-typify the cache. This can be necessary, for example, if we are + // changing from one value-typed stem to another. + // + if (!stem.defined () || cv.type != stem->type) + { + cv = nullptr; + cv.type = nullptr; // Un-typify. + } + + if (stem.defined ()) + cv = *stem; + + // Typify the cache value. If the stem is the original, then the type + // would get propagated automatically. But the stem could also be the + // override, which is kept untyped. Or the stem might not be there at + // all while we still need to apply prefixes/suffixes in the type-aware + // way. + // + if (cv.type == nullptr && var.type != nullptr) + typify (cv, *var.type, &var); + } + + // Now apply override prefixes and suffixes (if updating the cache). Also + // calculate the vars and depth of the result, which will be those of the + // stem or prefix/suffix that applies, whichever is the innermost. + // + // Note: we could probably cache this information instead of recalculating + // it every time. + // + size_t depth (stem_depth); + const variable_map* vars (stem.vars); + const scope* proj (stem_proj); + + ovr_depth = target ? (rule ? 3 : 2) : 0; + + for (s = this; s != nullptr; s = s->parent_scope ()) + { + ++ovr_depth; + + // The override list is in the reverse order of appearance so we need to + // iterate backwards in order to apply things in the correct order. + // + // We also need to skip any append/prepend overrides that appear before + // __override (in the command line order), provided it is from this + // scope. + // + bool skip (stem_ovr != nullptr && stem_depth == ovr_depth); + + for (const variable* o (var.overrides->aliases); // Last override. + o != nullptr; + o = (o->aliases != var.overrides->aliases ? o->aliases : nullptr)) + { + if (skip) + { + if (stem_ovr == o) // Keep skipping until after we see __override. + skip = false; + + continue; + } + + // First see if this override applies. This is tricky: what if the + // stem is a "visible" override from an outer project? Shouldn't its + // overrides apply? Sure sounds logical. So we use the project of the + // stem's scope. + // + if (vars != nullptr && !applies (o, vars, proj)) + continue; + + // Note that we keep override values as untyped names even if the + // variable itself is typed. We also pass the original variable for + // diagnostics. + // + auto lp (find (o, "__prefix")); + auto ls (find (o, "__suffix")); + + if (cl) + { + // Note: if we have both, then one is already in the stem. + // + if (lp) // No sense to prepend/append if NULL. + { + cv.prepend (names (cast (lp)), &var); + } + else if (ls) + { + cv.append (names (cast (ls)), &var); + } + } + + if (lp.defined () || ls.defined ()) + { + // If we had no stem, use the first override as a surrogate stem. + // + if (vars == nullptr) + { + depth = ovr_depth; + vars = &s->vars; + proj = s->root_scope (); + } + // Otherwise, pick the innermost location between the stem and + // prefix/suffix. + // + else if (ovr_depth < depth) + { + depth = ovr_depth; + vars = &s->vars; + } + } + } + } + + // Use the location of the innermost value that contributed as the + // location of the result. + // + return make_pair (lookup (&cv, &var, vars), depth); + } + + value& scope:: + append (const variable& var) + { + // Note that here we want the original value without any overrides + // applied. + // + lookup l (find_original (var).first); + + if (l.defined () && l.belongs (*this)) // Existing var in this scope. + return vars.modify (l); // Ok since this is original. + + value& r (assign (var)); // NULL. + + if (l.defined ()) + r = *l; // Copy value (and type) from the outer scope. + + return r; + } + + const target_type* scope:: + find_target_type (const string& tt, const scope** rs) const + { + // Search scopes outwards, stopping at the project root. + // + for (const scope* s (this); + s != nullptr; + s = s->root () ? global_scope : s->parent_scope ()) + { + if (s->target_types.empty ()) + continue; + + if (const target_type* r = s->target_types.find (tt)) + { + if (rs != nullptr) + *rs = s; + + return r; + } + } + + return nullptr; + } + + // Find target type from file name. + // + static const target_type* + find_file_target_type (const scope* s, const string& n) + { + // Pretty much the same logic as in find_target_type() above. + // + for (; s != nullptr; s = s->root () ? global_scope : s->parent_scope ()) + { + if (s->target_types.empty ()) + continue; + + if (const target_type* r = s->target_types.find_file (n)) + return r; + } + + return nullptr; + } + + pair> scope:: + find_target_type (name& n, const location& loc) const + { + const target_type* tt (nullptr); + optional ext; + + string& v (n.value); + + // If the target type is specified, resolve it and bail out if not found. + // Otherwise, we know in the end it will resolve to something (if nothing + // else, either dir{} or file{}), so we can go ahead and process the name. + // + if (n.typed ()) + { + tt = find_target_type (n.type); + + if (tt == nullptr) + return make_pair (tt, move (ext)); + } + else + { + // Empty name as well as '.' and '..' signify a directory. Note that + // this logic must be consistent with other places (grep for ".."). + // + if (v.empty () || v == "." || v == "..") + tt = &dir::static_type; + } + + // Directories require special name processing. If we find that more + // targets deviate, then we should make this target type-specific. + // + if (tt != nullptr && (tt->is_a () || tt->is_a ())) + { + // The canonical representation of a directory name is with empty + // value. + // + if (!v.empty ()) + { + n.dir /= dir_path (v); // Move name value to dir. + v.clear (); + } + } + else if (!v.empty ()) + { + // Split the path into its directory part (if any) the name part, and + // the extension (if any). We cannot assume the name part is a valid + // filesystem name so we will have to do the splitting manually. + // + // See also parser::expand_name_pattern() if changing anything here. + // + size_t p (path::traits_type::rfind_separator (v)); + + if (p != string::npos) + { + try + { + n.dir /= dir_path (v, p != 0 ? p : 1); // Special case: "/". + } + catch (const invalid_path& e) + { + fail (loc) << "invalid path '" << e.path << "'"; + } + + // This is probably too general of a place to ignore multiple trailing + // slashes and treat it as a directory (e.g., we don't want to + // encourage this sloppiness in buildfiles). We could, however, do it + // for certain contexts, such as buildspec. Maybe a lax flag? + // + if (++p == v.size ()) + fail (loc) << "invalid name '" << v << "'"; + + v.erase (0, p); + } + + // Extract the extension. + // + ext = target::split_name (v, loc); + } + + // If the target type is still unknown, map it using the name/extension, + // falling back to file{}. + // + if (tt == nullptr) + { + // We only consider files without extension for file name mapping. + // + if (!ext) + tt = find_file_target_type (this, v); + + //@@ TODO: derive type from extension. + + if (tt == nullptr) + tt = &file::static_type; + } + + // If the target type does not use extensions but one was specified, + // factor it back into the name (this way we won't assert when printing + // diagnostics; see to_stream(target_key) for details). + // + if (ext && + tt->fixed_extension == nullptr && + tt->default_extension == nullptr) + { + v += '.'; + v += *ext; + ext = nullopt; + } + + return make_pair (tt, move (ext)); + } + + static target* + derived_tt_factory (const target_type& t, dir_path d, dir_path o, string n) + { + // Pass our type to the base factory so that it can detect that it is + // being called to construct a derived target. This can be used, for + // example, to decide whether to "link up" to the group. + // + // One exception: if we are derived from a derived target type, then this + // logic would lead to infinite recursion. So in this case get the + // ultimate base. + // + const target_type* bt (t.base); + for (; bt->factory == &derived_tt_factory; bt = bt->base) ; + + target* r (bt->factory (t, move (d), move (o), move (n))); + r->derived_type = &t; + return r; + } + + pair, bool> scope:: + derive_target_type (const string& name, const target_type& base) + { + // Base target type uses extensions. + // + bool ext (base.fixed_extension != nullptr || + base.default_extension != nullptr); + + // @@ Looks like we may need the ability to specify a fixed extension + // (which will be used to compare existing targets and not just + // search for existing files that is handled by the target_type:: + // extension hook). See the file_factory() for details. We will + // probably need to specify it as part of the define directive (and + // have the ability to specify empty and NULL). + // + // Currently, if we define myfile{}: file{}, then myfile{foo} and + // myfile{foo.x} are the same target. + // + unique_ptr dt (new target_type (base)); + dt->base = &base; + dt->factory = &derived_tt_factory; + + // @@ We should probably inherit the fixed extension unless overriden with + // another fixed? But then any derivation from file{} will have to specify + // (or override) the fixed extension? But what is the use of deriving from + // a fixed extension target and not overriding its extension? Some kind of + // alias. Fuzzy. + // + dt->fixed_extension = nullptr /*&target_extension_fix*/; // @@ TODO + + // Override default extension/pattern derivation function: we most likely + // don't want to use the same default as our base (think cli: file). But, + // if our base doesn't use extensions, then most likely neither do we + // (think foo: alias). + // + dt->default_extension = + ext && dt->fixed_extension == nullptr + ? &target_extension_var + : nullptr; + + dt->pattern = + dt->fixed_extension != nullptr ? nullptr /*&target_pattern_fix*/ : + dt->default_extension != nullptr ? &target_pattern_var : + nullptr; + + // There is actually a difference between "fixed fixed" (like man1{}) and + // "fixed but overridable" (like file{}). Fuzzy: feels like there are + // different kinds of "fixed" (file{} vs man{} vs man1{}). + // + dt->print = + dt->fixed_extension != nullptr + ? &target_print_0_ext_verb // Fixed extension, no use printing. + : nullptr; // Normal. + + return target_types.insert (name, move (dt)); + } + + scope* scope::global_; + scope::variable_override_cache scope::global_override_cache; + + // scope_map + // + scope_map scope_map::instance; + const scope_map& scope_map::cinstance = scope_map::instance; + const scope_map& scopes = scope_map::cinstance; + + const scope* global_scope; + + auto scope_map:: + insert (const dir_path& k, bool root) -> iterator + { + scope_map_base& m (*this); + + auto er (m.emplace (k, scope (true))); // Global. + scope& s (er.first->second); + + // If this is a new scope, update the parent chain. + // + if (er.second) + { + scope* p (nullptr); + + // Update scopes of which we are a new parent/root (unless this is the + // global scope). Also find our parent while at it. + // + if (m.size () > 1) + { + // The first entry is ourselves. + // + auto r (m.find_sub (k)); + for (++r.first; r.first != r.second; ++r.first) + { + scope& c (r.first->second); + + // The first scope of which we are a parent is the least (shortest) + // one which means there is no other scope between it and our + // parent. + // + if (p == nullptr) + p = c.parent_; + + if (root && c.root_ == p->root_) // No intermediate root. + c.root_ = &s; + + if (p == c.parent_) // No intermediate parent. + c.parent_ = &s; + } + + // We couldn't get the parent from one of its old children so we have + // to find it ourselves. + // + if (p == nullptr) + p = &find (k.directory ()); + } + + s.parent_ = p; + s.root_ = root ? &s : (p != nullptr ? p->root_ : nullptr); + } + else if (root && !s.root ()) + { + // Upgrade to root scope. + // + auto r (m.find_sub (k)); + for (++r.first; r.first != r.second; ++r.first) + { + scope& c (r.first->second); + + if (c.root_ == s.root_) // No intermediate root. + c.root_ = &s; + } + + s.root_ = &s; + } + + return er.first; + } + + scope& scope_map:: + find (const dir_path& k) + { + assert (k.normalized (false)); // Allow non-canonical dir separators. + + scope_map_base& m (*this); + auto i (m.find_sup (k)); + assert (i != m.end ()); // Should have global scope. + return i->second; + } +} -- cgit v1.1