From def2c2dfaf5374f139b310c4f05b0614cb99359e Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 28 Mar 2022 15:04:35 +0200 Subject: Implement dependency configuration negotiation For the detailed history see the dep-config and dep-config-neg branches. --- bpkg/package-configuration.cxx | 491 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 491 insertions(+) create mode 100644 bpkg/package-configuration.cxx (limited to 'bpkg/package-configuration.cxx') diff --git a/bpkg/package-configuration.cxx b/bpkg/package-configuration.cxx new file mode 100644 index 0000000..e8ea13a --- /dev/null +++ b/bpkg/package-configuration.cxx @@ -0,0 +1,491 @@ +// file : bpkg/package-configuration.cxx -*- C++ -*- +// license : MIT; see accompanying LICENSE file + +#include + +#include + +#include + +namespace bpkg +{ + using build2::config::variable_origin; + + string + serialize_cmdline (const string& name, const optional& value) + { + using namespace build2; + + string r (name + '='); + + if (!value) + r += "[null]"; + else + { + if (!value->empty ()) + { + // Note: we need to use command-line (effective) quoting. + // + ostringstream os; + to_stream (os, *value, quote_mode::effective, '@'); + r += os.str (); + } + } + + return r; + } + + void package_configuration:: + print (diag_record& dr, + const char* indent, + const dependent_config_variable_values* ovrs) const + { + bool first (true); + for (const config_variable_value& v: *this) + { + if (v.origin != variable_origin::buildfile && + v.origin != variable_origin::override_) + continue; + + if (first) + first = false; + else + dr << '\n'; + + dr << indent; + + if (ovrs != nullptr && v.origin == variable_origin::buildfile) + { + if (const dependent_config_variable_value* ov = ovrs->find (v.name)) + { + dr << ov->serialize_cmdline () << " (set by " << ov->dependent << ')'; + continue; + } + } + + dr << v.serialize_cmdline () << " ("; + + if (v.origin == variable_origin::buildfile) + dr << "set by " << *v.dependent; + else + dr << "user configuration"; + + dr << ')'; + } + } + + void + to_checksum (sha256& cs, const config_variable_value& v) + { + using namespace build2; + + cs.append (v.name); + cs.append (static_cast (v.origin)); + if (v.type) + cs.append (*v.type); + + if (v.origin != variable_origin::undefined) + { + if (v.value) + for (const name& n: *v.value) + to_checksum (cs, n); + + if (v.origin == variable_origin::buildfile) + { + cs.append (v.dependent->string ()); + cs.append (v.confirmed); + } + } + } + + bool + negotiate_configuration ( + package_configurations& cfgs, + package_skeleton& dept, + pair pos, + const small_vector, 1>& depcs) + { + assert (!dept.system); + + pos.first--; pos.second--; // Convert to 0-base. + + const dependency_alternative& da ( + dept.available->dependencies[pos.first][pos.second]); + + assert (da.require || da.prefer); + + // Step 1: save a snapshot of the old configuration while unsetting values + // that have this dependent as the originator and reloading the defaults. + // + // The idea behind unsetting values previously (first) set by this + // dependent is to allow it to "change its mind" based on other changes in + // the configuration (e.g., some expensive feature got enabled by another + // dependent which this dependent might as well use). + // + // This works well if the default values of configuration variables are + // independent. However, consider this example: + // + // dependency: + // + // config [bool] config.foo.x ?= false + // config [bool] config.foo.buf ?= ($config.foo.x ? 8196 : 4096) + // + // dependent: + // + // config.foo.x = true + // config.foo.buf = ($config.foo.buf < 6144 ? 6144 : $config.foo.buf) + // + // Here if we unset both x and buf to their defaults, we will get an + // incorrect result. + // + // The long-term solution here is to track dependencies between + // configuration variables (which we can do as part of the config + // directive via our parser::lookup_variable() hook and save this + // information in the config module's saved_variables list). Then, we + // "levelize" all the variables and have an inner "refinement" loop over + // these levels. Specifically, we first unset all of them. Then we unset + // all except the first level (which contains configuration variables that + // don't depend on any others). And so on. + // + // And until we implement this, we expect the dependent to take such + // configuration variable dependencies into account. For example: + // + // config.foo.x = true + // config.foo.buf = ($config.foo.buf < 6144 + // ? ($config.foo.x ? 8196 : 6144) + // : $config.foo.buf) + // + // Another issue with this "originating dependent" logic is that it will + // be tricky to scale to containers where we would need to track + // originating dependents for individual elements of a value rather than + // the whole value as we do now. As an example, consider some "set of + // enabled backends" configuration variable. Technically, this doesn't + // seem insurmountable if we make some assumptions (e.g., if a value + // contains multiple elements, then it is such a set-like value; or + // we could use actual type names). + // + // For now we recommend to use multiple bool configurations to handle such + // cases (and, in fact, we currently don't have any set/map-like types, + // which we may want to add in the future). However, one could come up + // with some open-ended configuration list that will be difficult to + // support with bool. For example, we may need to support a set of buffer + // sizes or some such. + // + // Our assumptions regarding require: + // + // - Can only set bool configuration variables and only to true. + // + // - Should not have any conditions on the state of other configuration + // variables, including their origin (but can have other conditions, + // for example on the target platform). + // + // This means that we don't need to set the default values, but will need + // the type information as well as overrides. So what we will do is only + // call reload_defaults() for the first time to load types/override. Note + // that this assumes the set of configuration variables cannot change + // based on the values of other configuration variables (we have a note + // in the manual instructing the user not to do this). + // + // The dependency could also be system in which case there could be no + // skeleton information to load the types/defaults from. In this case we + // can handle require in the "lax mode" (based on the above assumptions) + // but not prefer. + // + // While at it, also collect the configurations to pass to dependent's + // evaluate_*() calls. + // + dependent_config_variable_values old_cfgs; + package_skeleton::dependency_configurations depc_cfgs; + depc_cfgs.reserve (depcs.size ()); + + for (package_skeleton& depc: depcs) + { + package_configuration& cfg (cfgs[depc.package]); + + for (config_variable_value& v: cfg) + { + if (v.origin == variable_origin::buildfile) + { + if (*v.dependent == dept.package) + { + old_cfgs.push_back ( + dependent_config_variable_value { + v.name, move (v.value), move (*v.dependent)}); + + // Note that we will not reload it to default in case of require. + // + v.undefine (); + } + else + old_cfgs.push_back ( + dependent_config_variable_value {v.name, v.value, *v.dependent}); + } + } + + if (depc.available == nullptr) + { + assert (depc.system); + + if (da.prefer) + fail << "unable to negotiate configuration for system dependency " + << depc.package << " without configuration information" << + info << "consider specifying system dependency version that has " + << "corresponding available package" << + info << "dependent " << dept.package << " has prefer/accept clauses " + << "that cannot be evaluated without configuration information"; + + if (!cfg.system) + { + // Note that we still need the overrides. + // + depc.load_overrides (cfg); + cfg.system = true; + } + + continue; + } + else + assert (!cfg.system); + + if (da.prefer || cfg.empty ()) + depc.reload_defaults (cfg); + } + + // Note that we need to collect the dependency configurations as a + // separate loop so that the stored references are not invalidated by + // operator[] (which is really a push_back() into a vector). + // + for (package_skeleton& depc: depcs) + depc_cfgs.push_back (cfgs[depc.package]); + + // Step 2: execute the prefer/accept or requires clauses. + // + if (!(da.require + ? dept.evaluate_require (depc_cfgs, *da.require, pos) + : dept.evaluate_prefer_accept (depc_cfgs, + *da.prefer, *da.accept, pos))) + { + diag_record dr (fail); + + dr << "unable to negotiate acceptable configuration with dependent " + << dept.package << " for dependencies "; + + for (size_t i (0); i != depcs.size (); ++i) + dr << (i == 0 ? "" : ", ") << depcs[i].get ().package; + + dr << info << "configuration before negotiation:\n"; + + // Note that we won't print this dependent's values (which we have unset + // above), but that seems like a good thing since they are not the cause + // of this impasse. + // + for (const package_configuration& cfg: depc_cfgs) + cfg.print (dr, " "); // Note 4 spaces since in nested info. + } + + // Check if anything changed by comparing to entries in old_cfgs. + // + // While at it, also detect if we have any changes where one dependent + // overrides a value set by another dependent (see below). + // + bool cycle (false); + { + optional n (0); // Number of unchanged. + + for (package_skeleton& depc: depcs) + { + package_configuration& cfg (cfgs[depc.package]); + + for (config_variable_value& v: cfg) + { + if (v.origin == variable_origin::buildfile) + { + if (const dependent_config_variable_value* ov = + old_cfgs.find (v.name)) + { + if (ov->value == v.value) + { + // If the value hasn't change, so shouldn't the originating + // dependent. + // + assert (ov->dependent == *v.dependent); + + if (n) + ++*n; + + continue; + } + else + { + // Note that it's possible the same dependent overrides its + // old value (e.g., because a conditional default changed to a + // better value). + // + if (ov->dependent != *v.dependent) + cycle = true; + } + } + + n = nullopt; + + if (cycle) + break; + } + } + + if (!n && cycle) + break; + } + + // If we haven't seen any changed and we've seen the same number, then + // nothing has changed. + // + if (n && *n == old_cfgs.size ()) + return false; + } + + // Besides the dependent returning false from its accept clause, there is + // another manifestation of the inability to negotiate an acceptable + // configuration: two dependents keep changing the same configuration to + // mutually unacceptable values. To detect this, we need to look for + // negotiation cycles. + // + // Specifically, given a linear change history in the form: + // + // O->N ... O->N ... O->N + // + // We need to look for a possibility of turning it into a cycle: + // + // O->N ... O->N + // \ ... / + // + // Where O->N is a change that involves one dependent overriding a value + // set by another dependent and `...` are identical history segments. + // + if (!cycle) + return true; + + // Populate new_cfgs. + // + dependent_config_variable_values new_cfgs; + for (package_skeleton& depc: depcs) + { + package_configuration& cfg (cfgs[depc.package]); + + for (config_variable_value& v: cfg) + { + if (v.origin == variable_origin::buildfile) + { + new_cfgs.push_back ( + dependent_config_variable_value {v.name, v.value, *v.dependent}); + } + } + } + + // Sort both. + // + { + auto cmp = [] (const dependent_config_variable_value& x, + const dependent_config_variable_value& y) + { + return x.name < y.name; + }; + + sort (old_cfgs.begin (), old_cfgs.end (), cmp); + sort (new_cfgs.begin (), new_cfgs.end (), cmp); + } + + // Look backwards for identical O->N changes and see if we can come + // up with two identical segments between them. + // + cycle = false; + + auto& change_history (cfgs.change_history_); + + for (size_t n (change_history.size ()), i (n); i != 0; i -= 2) + { + if (change_history[i - 2] == old_cfgs && + change_history[i - 1] == new_cfgs) + { + size_t d (n - i); // Segment length. + + // See if there is an identical segment before this that also starts + // with O->N. + // + if (i < 2 + d + 2) + break; // Not long enough to possibly find anything. + + size_t j (i - 2 - d); // Earlier O->N. + + if (change_history[j - 2] == old_cfgs && + change_history[j - 1] == new_cfgs) + { + if (equal (change_history.begin () + j, + change_history.begin () + j + d, + change_history.begin () + i)) + { + cycle = true; + break; + } + } + + // Otherwise, keep looking for a potentially longer segment. + } + } + + if (!cycle) + { + change_history.push_back (move (old_cfgs)); + change_history.push_back (move (new_cfgs)); + + return true; + } + + diag_record dr (fail); + + dr << "unable to negotiate acceptable configuration between dependents " + << dept.package; + + // Analyze the O->N changes and determine the problematic dependent(s). + // Do we actually know for sure they are all problematic? Well, they + // repeatedly changed the values to the ones we don't like, so I guess so. + // + small_vector, 1> depts; // Duplicates. + for (const dependent_config_variable_value& nv: new_cfgs) + { + if (nv.dependent == dept.package) + { + if (const dependent_config_variable_value* ov = old_cfgs.find (nv.name)) + { + if (ov->value != nv.value && ov->dependent != nv.dependent) + { + if (find_if (depts.begin (), depts.end (), + [ov] (reference_wrapper pk) + { + return ov->dependent == pk.get (); + }) == depts.end ()) + { + dr << ", " << ov->dependent; + depts.push_back (ov->dependent); + } + } + } + } + } + + dr << " for dependencies "; + + for (size_t i (0); i != depcs.size (); ++i) + dr << (i == 0 ? "" : ", ") << depcs[i].get ().package; + + dr << info << "configuration before negotiation:\n"; + for (const package_configuration& cfg: depc_cfgs) + cfg.print (dr, " ", &old_cfgs); + + dr << info << "configuration after negotiation:\n"; + for (const package_configuration& cfg: depc_cfgs) + cfg.print (dr, " "); + + dr << endf; + } +} -- cgit v1.1