diff options
| -rw-r--r-- | bpkg/package-configuration.cxx | 140 | ||||
| -rw-r--r-- | bpkg/package-configuration.hxx | 50 |
2 files changed, 157 insertions, 33 deletions
diff --git a/bpkg/package-configuration.cxx b/bpkg/package-configuration.cxx index e74be64..3ddf68e 100644 --- a/bpkg/package-configuration.cxx +++ b/bpkg/package-configuration.cxx @@ -92,6 +92,10 @@ namespace bpkg // 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<size_t> n (0); // Number of unchanged. @@ -109,19 +113,35 @@ namespace bpkg return v.name == o.name; })); - if (i == old_cfgs.end () || - i->value != v.value || - i->dependent != *v.dependent) + if (i != old_cfgs.end ()) { - n = nullopt; - break; + if (i->value == v.value) + { + // If the value hasn't change, so shouldn't the originating + // dependent. + // + assert (i->dependent == *v.dependent); + + if (n) + ++*n; + + continue; + } + else + { + assert (i->dependent != *v.dependent); + cycle = true; + } } - ++*n; + n = nullopt; + + if (cycle) + break; } } - if (!n) + if (!n && cycle) break; } @@ -132,16 +152,108 @@ namespace bpkg 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.key]); + + 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; + }; - // @@ TODO: look for cycles in change history. - // @@ TODO: save in change history. + 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. // - /* - dependent_config_variable_values new_cfgs; // @@ TODO. + 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) + { + // @@ TODO + // + // Here we can analyze the O->N change history and determine the other + // problematic dependent(s). Do we actually know for sure they are all + // problematic? Well, they repeatedly changed the values so I guess so. + // + fail << "unable to negotiate acceptable configuration (cycle)"; + } - old_cfgs.sort (); - new_cfgs.sort (); - */ + change_history.push_back (move (old_cfgs)); + change_history.push_back (move (new_cfgs)); return true; } diff --git a/bpkg/package-configuration.hxx b/bpkg/package-configuration.hxx index 84f5256..80ededb 100644 --- a/bpkg/package-configuration.hxx +++ b/bpkg/package-configuration.hxx @@ -48,6 +48,23 @@ namespace bpkg optional<package_key> dependent; }; + // A subset of config_variable_value for variable values set by the + // dependents (origin is buildfile). Used to track change history. + // + struct dependent_config_variable_value + { + string name; + optional<build2::names> value; + package_key dependent; + }; + + inline bool + operator== (const dependent_config_variable_value& x, + const dependent_config_variable_value& y) + { + return x.name == y.name && x.value == y.value && x.dependent == y.dependent; + } + class package_configuration: public vector<config_variable_value> { public: @@ -79,6 +96,9 @@ namespace bpkg } }; + using dependent_config_variable_values = + small_vector<dependent_config_variable_value, 1>; + class package_configurations: public small_vector<package_configuration, 1> { public: @@ -96,28 +116,20 @@ namespace bpkg push_back (package_configuration (p)); return back (); } - }; + void + clear () + { + small_vector<package_configuration, 1>::clear (); + change_history_.clear (); + } - // A subset of config_variable_value for variable values set by the - // dependents (origin is buildfile). Used to track change history. - // - struct dependent_config_variable_value - { - string name; - optional<build2::names> value; - package_key dependent; - }; - - class dependent_config_variable_values: - public small_vector<dependent_config_variable_value, 1> - { + // Implementation details. + // public: - /* - @@ - void - sort (); - */ + // Note: dependent_config_variable_values must be sorted by name. + // + small_vector<dependent_config_variable_values, 2> change_history_; }; // Up-negotiate the configuration for the specified dependencies of the |