aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bpkg/package-configuration.cxx140
-rw-r--r--bpkg/package-configuration.hxx50
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