Implement configuration negotiation cycles detection

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