// file : libbuild2/scope.cxx -*- C++ -*- // license : MIT; see accompanying LICENSE file #include <libbuild2/scope.hxx> #include <libbuild2/target.hxx> #include <libbuild2/context.hxx> using namespace std; namespace build2 { ostream& operator<< (ostream& os, const subprojects& sps) { for (auto b (sps.begin ()), i (b); os && i != sps.end (); ++i) { // See find_subprojects() for details. // const project_name& n ( path::traits_type::is_separator (i->first.string ().back ()) ? empty_project_name : i->first); os << (i != b ? " " : "") << n << '@' << i->second; } return os; } // scope // pair<lookup, size_t> scope:: lookup_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_type (), d); // Process target type/pattern-specific prepend/append values. // auto pre_app = [&var, this] (lookup_type& 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_type stem (s->lookup_original (var, tt, tn, gt, gn, 2).first); // Check the cache. // pair<value&, ulock> entry ( s->target_vars.cache.insert ( ctx, make_tuple (&v, tt, *tn), stem, static_cast<const variable_map::value_data&> (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<names> (v)), &var); else cv.append (names (cast<names> (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_type 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_type 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.lookup (var)); if (p.first != nullptr) return make_pair (lookup_type (*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::global: s = s->parent_scope (); break; case variable_visibility::prereq: assert (false); } } return make_pair (lookup_type (), size_t (~0)); } auto scope:: lookup_override_info (const variable& var, const pair<lookup_type, size_t> original, bool target, bool rule) const -> override_info { 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_type& 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::global: 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 lookup = [&s, &var] (const variable* o, const char* k = nullptr) -> lookup_type { if (k != nullptr && !o->override (k)) return lookup_type (); // Note: using the original as storage variable. // return lookup_type (s->vars.lookup (*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_type& 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 (lookup (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 override_info {original, orig.defined ()}; 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 = &ctx.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_type 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 (lookup (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 == &ctx.global_scope ? ctx.global_override_cache : inner_proj->root_extra->override_cache); pair<value&, ulock> entry ( cache.insert ( ctx, 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 (lookup (o, "__prefix")); auto ls (lookup (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<names> (lp)), &var); } else if (ls) { cv.append (names (cast<names> (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 override_info { make_pair (lookup_type (&cv, &var, vars), depth), orig.defined () && stem == orig}; } value& scope:: append (const variable& var) { // Note that here we want the original value without any overrides // applied. // auto l (lookup_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 { // Search the project's root scope then the global scope. // if (const scope* rs = root_scope ()) { if (const target_type* r = rs->root_extra->target_types.find (tt)) return r; } return ctx.global_target_types.find (tt); } // Find target type from file name. // static const target_type* find_target_type_file (const scope& s, const string& n) { // Pretty much the same logic as in find_target_type() above. // if (const scope* rs = s.root_scope ()) { if (const target_type* r = rs->root_extra->target_types.find_file (n)) return r; } return s.ctx.global_target_types.find_file (n); } pair<const target_type*, optional<string>> scope:: find_target_type (name& n, const location& loc) const { const target_type* tt (nullptr); optional<string> 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<dir> () || tt->is_a<fsdir> ())) { // 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_target_type_file (*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)); } pair<const target_type&, optional<string>> scope:: find_target_type (name& n, name& o, const location& loc) const { auto r (find_target_type (n, loc)); if (r.first == nullptr) fail (loc) << "unknown target type " << n.type << " in " << n; bool src (n.pair); // If out-qualified, then it is from src. if (src) { assert (n.pair == '@'); if (!o.directory ()) fail (loc) << "expected directory after '@'"; } dir_path& d (n.dir); const dir_path& sd (src_path ()); const dir_path& od (out_path ()); if (d.empty ()) d = src ? sd : od; // Already dormalized. else { if (d.relative ()) d = (src ? sd : od) / d; d.normalize (); } dir_path out; if (src && sd != od) // If in-source build, then out must be empty. { out = o.dir.relative () ? od / o.dir : move (o.dir); out.normalize (); } o.dir = move (out); // Result. return pair<const target_type&, optional<string>> ( *r.first, move (r.second)); } target_key scope:: find_target_key (names& ns, const location& loc) const { if (size_t n = ns.size ()) { if (n == (ns[0].pair ? 2 : 1)) { name dummy; return find_target_key (ns[0], n == 1 ? dummy : ns[1], loc); } } fail (loc) << "invalid target name: " << ns << endf; } pair<const target_type&, optional<string>> scope:: find_prerequisite_type (name& n, name& o, const location& loc) const { auto r (find_target_type (n, loc)); if (r.first == nullptr) fail (loc) << "unknown target type " << n.type << " in " << n; if (n.pair) // If out-qualified, then it is from src. { assert (n.pair == '@'); if (!o.directory ()) fail (loc) << "expected directory after '@'"; } if (!n.dir.empty ()) n.dir.normalize (false, true); // Current dir collapses to an empty one. if (!o.dir.empty ()) o.dir.normalize (false, true); // Ditto. return pair<const target_type&, optional<string>> ( *r.first, move (r.second)); } prerequisite_key scope:: find_prerequisite_key (names& ns, const location& loc) const { if (size_t n = ns.size ()) { if (n == (ns[0].pair ? 2 : 1)) { name dummy; return find_prerequisite_key (ns[0], n == 1 ? dummy : ns[1], loc); } } fail (loc) << "invalid prerequisite name: " << ns << endf; } static target* derived_tt_factory (context& c, 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 (c, t, move (d), move (o), move (n))); r->derived_type = &t; return r; } pair<reference_wrapper<const target_type>, bool> scope:: derive_target_type (const string& name, const target_type& base) { assert (root_scope () == this); // 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<target_type> 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> : nullptr; dt->pattern = dt->fixed_extension != nullptr ? nullptr /*&target_pattern_fix<???>*/ : dt->default_extension != nullptr ? &target_pattern_var<nullptr> : 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 root_extra->target_types.insert (name, move (dt)); } // scope_map // auto scope_map:: insert (const dir_path& k, bool root) -> iterator { scope_map_base& m (*this); auto er (m.emplace (k, scope (ctx, 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; } }