In pkg-build make sure that reconfiguring dependent doesn't change current dependency selection

Also fix the dependency alternative selection so that if the dependency
package of a different version is already being built, then make sure that one
of them is satisfactory for all the dependents and don't consider this
alternative if that's not the case.

7 files changed, 666 insertions, 237 deletions

diff --git a/bpkg/pkg-build.cxx b/bpkg/pkg-build.cxx
index 4821099..6d90ff9 100644
--- a/bpkg/pkg-build.cxx
+++ b/bpkg/pkg-build.cxx
@@ -1285,9 +1285,14 @@ namespace bpkg
       // Bail out if this is a configured non-system package and no
       // up/down-grade nor collecting prerequisite replacements are required.
       //
-      if (sp != nullptr                            &&
-          sp->state == package_state::configured   &&
-          sp->substate != package_substate::system)
+      // NOTE: remember to update the check condition in
+      // collect_order_dependents() if changing anything here.
+      //
+      bool src_conf (sp != nullptr &&
+                     sp->state == package_state::configured &&
+                     sp->substate != package_substate::system);
+
+      if (src_conf)
       {
         ud = sp->version != pkg.available_version ();
 
@@ -1435,7 +1440,7 @@ namespace bpkg
           shared_ptr<available_package>              available;
           lazy_shared_ptr<bpkg::repository_fragment> repository_fragment;
           bool                                       system;
-          bool                                       specified;
+          bool                                       specified_dependency;
           bool                                       force;
 
           // True if the dependency package is either selected in the
@@ -1488,6 +1493,7 @@ namespace bpkg
                            this]
                           (const dependency_alternative& da,
                            bool buildtime,
+                           const package_prerequisites* prereqs,
                            diag_record* dr = nullptr)
           -> precollect_result
         {
@@ -1609,6 +1615,15 @@ namespace bpkg
 
             shared_ptr<selected_package>& dsp (spd.first);
 
+            if (prereqs != nullptr &&
+                (dsp == nullptr ||
+                 find_if (prereqs->begin (), prereqs->end (),
+                          [&dsp] (const auto& v)
+                          {
+                            return v.first.object_id () == dsp->name;
+                          }) == prereqs->end ()))
+              return precollect_result (false /* postpone */);
+
             pair<shared_ptr<available_package>,
                  lazy_shared_ptr<repository_fragment>> rp;
 
@@ -2072,6 +2087,70 @@ namespace bpkg
               }
             }
 
+            // If the dependency package of a different version is already
+            // being built, then we also need to make sure that we will be
+            // able to choose one of them (either existing or new) which
+            // satisfies all the dependents.
+            //
+            // Note that collect_build() also performs this check but
+            // postponing it till then can end up in failing instead of
+            // selecting some other dependency alternative.
+            //
+            assert (dap != nullptr); // Otherwise we would fail earlier.
+
+            if (i != map_.end () && d.constraint)
+            {
+              const build_package& bp (i->second.package);
+
+              if (bp.action && *bp.action == build_package::build)
+              {
+                const version& v1 (system
+                                   ? *dap->system_version (*ddb)
+                                   : dap->version);
+
+                const version& v2 (bp.available_version ());
+
+                if (v1 != v2)
+                {
+                  using constraint_type = build_package::constraint_type;
+
+                  constraint_type c1 {
+                    pkg.db, pkg.name ().string (), *d.constraint};
+
+                  if (!satisfies (v2, c1.value))
+                  {
+                    for (const constraint_type& c2: bp.constraints)
+                    {
+                      if (!satisfies (v1, c2.value))
+                      {
+                        if (dr != nullptr)
+                        {
+                          const package_name& n  (d.name);
+                          const string&       d1 (c1.dependent);
+                          const string&       d2 (c2.dependent);
+
+                          *dr << error << "unable to satisfy constraints on "
+                                       << "package " << n <<
+                            info << d2 << c2.db << " depends on (" << n << ' '
+                                 << c2.value << ")" <<
+                            info << d1 << c1.db << " depends on (" << n << ' '
+                                 << c1.value << ")" <<
+                            info << "available "
+                                 << bp.available_name_version () <<
+                            info << "available "
+                                 << package_string (n, v1, system) <<
+                            info << "explicitly specify " << n << " version "
+                                 << "to manually satisfy both constraints";
+                        }
+
+                        return precollect_result (false /* postpone */);
+                      }
+                    }
+                  }
+                }
+              }
+            }
+
             bool ru (i != map_.end () || dsp != nullptr);
 
             if (!ru)
@@ -2115,7 +2194,7 @@ namespace bpkg
               move (b.repository_fragment),
               nullopt,                             // Dependencies.
               nullopt,                             // Package skeleton.
-              nullopt,                             // Enabled dependency alternatives.
+              nullopt,                             // Postponed dependency alternatives.
               nullopt,                             // Hold package.
               nullopt,                             // Hold version.
               {},                                  // Constraints.
@@ -2175,7 +2254,7 @@ namespace bpkg
                              postponed_alts,
                              &dep_chain));
 
-            if (p != nullptr && b.force && !b.specified)
+            if (p != nullptr && b.force && !b.specified_dependency)
             {
               // Fail if the version is held. Otherwise, warn if the package is
               // held.
@@ -2268,141 +2347,169 @@ namespace bpkg
         // Iterate over the enabled dependencies and try to select a
         // satisfactory alternative.
         //
-        // The index and pre-collection result of the first satisfactory
-        // alternative.
+        // If the package is already configured as source and is not
+        // up/downgraded, then we will try to resolve its dependencies to the
+        // current prerequisites. To achieve this we will first try to select
+        // an alternative in the "recreate dependency decisions" mode,
+        // filtering out all the alternatives where dependencies do not all
+        // belong to the list of current prerequisites. If we end up with no
+        // alternative selected, then we retry in the "make dependency
+        // decisions" mode and select the alternative ignoring the current
+        // prerequisites.
         //
-        optional<pair<size_t, precollect_result>> first_alt;
+        const package_prerequisites* prereqs (src_conf && !ud
+                                              ? &sp->prerequisites
+                                              : nullptr);
 
-        // The number of satisfactory alternatives.
-        //
-        size_t alts_num (0);
-
-        for (size_t i (0); i != edas.size (); ++i)
+        for (;;)
         {
-          const dependency_alternative& da (edas[i]);
-
-          precollect_result r (precollect (da, das.buildtime));
-
-          // If we didn't come up with satisfactory dependency builds, then
-          // skip this alternative and try the next one, unless the collecting
-          // is postponed in which case just bail out.
-          //
-          // Should we skip alternatives for which we are unable to satisfy
-          // the constraint? On one hand, this could be a user error: there is
-          // no package available from dependent's repositories that satisfies
-          // the constraint. On the other hand, it could be that it's other
-          // dependent's constraints that we cannot satisfy together with
-          // others. And in this case we may want some other alternative.
-          // Consider, as an example, something like this:
+          // The index and pre-collection result of the first satisfactory
+          // alternative.
           //
-          // depends: libfoo >= 2.0.0 | libfoo >= 1.0.0 libbar
+          optional<pair<size_t, precollect_result>> first_alt;
+
+          // The number of satisfactory alternatives.
           //
-          if (!r.builds)
+          size_t alts_num (0);
+
+          for (size_t i (0); i != edas.size (); ++i)
           {
-            if (r.repo_postpone)
-            {
-              postpone (nullptr); // Already inserted into postponed_repo.
-              break;
-            }
+            const dependency_alternative& da (edas[i]);
 
-            continue;
-          }
+            precollect_result r (precollect (da, das.buildtime, prereqs));
+
+            // If we didn't come up with satisfactory dependency builds, then
+            // skip this alternative and try the next one, unless the
+            // collecting is postponed in which case just bail out.
+            //
+            // Should we skip alternatives for which we are unable to satisfy
+            // the constraint? On one hand, this could be a user error: there
+            // is no package available from dependent's repositories that
+            // satisfies the constraint. On the other hand, it could be that
+            // it's other dependent's constraints that we cannot satisfy
+            // together with others. And in this case we may want some other
+            // alternative.  Consider, as an example, something like this:
+            //
+            // depends: libfoo >= 2.0.0 | libfoo >= 1.0.0 libbar
+            //
+            if (!r.builds)
+            {
+              if (r.repo_postpone)
+              {
+                postpone (nullptr); // Already inserted into postponed_repo.
+                break;
+              }
 
-          ++alts_num;
+              continue;
+            }
 
-          // Note that when we see the first satisfactory alternative, we
-          // don't know yet if it is a single alternative or the first of the
-          // (multiple) true alternatives (those are handled differently).
-          // Thus, we postpone its processing until the second satisfactory
-          // alternative is encountered or the end of the alternatives list is
-          // reached.
-          //
-          if (!first_alt)
-          {
-            first_alt = make_pair (i, move (r));
-            continue;
-          }
+            ++alts_num;
 
-          // Try to select a true alternative, returning true if the
-          // alternative is selected or the selection is postponed. Return
-          // false if the alternative is ignored (not postponed and not all of
-          // it dependencies are reused).
-          //
-          auto try_select = [postponed_alts, &max_alt_index,
-                             &edas,
-                             &postpone, &select]
-                             (size_t index, precollect_result&& r)
-          {
-            // Postpone the collection if the alternatives maximum index is
-            // reached.
+            // Note that when we see the first satisfactory alternative, we
+            // don't know yet if it is a single alternative or the first of
+            // the (multiple) true alternatives (those are handled
+            // differently).  Thus, we postpone its processing until the
+            // second satisfactory alternative is encountered or the end of
+            // the alternatives list is reached.
             //
-            if (postponed_alts != nullptr && index >= max_alt_index)
+            if (!first_alt)
             {
-              postpone (postponed_alts);
-              return true;
+              first_alt = make_pair (i, move (r));
+              continue;
             }
 
-            // Select this alternative if all its dependencies are reused and
-            // do nothing about it otherwise.
+            // Try to select a true alternative, returning true if the
+            // alternative is selected or the selection is postponed. Return
+            // false if the alternative is ignored (not postponed and not all
+            // of it dependencies are reused).
             //
-            if (r.reused)
+            auto try_select = [postponed_alts, &max_alt_index,
+                               &edas,
+                               &postpone, &select]
+                               (size_t index, precollect_result&& r)
             {
-              // On the diagnostics run there shouldn't be any alternatives
-              // that we could potentially select.
+              // Postpone the collection if the alternatives maximum index is
+              // reached.
               //
-              assert (postponed_alts != nullptr);
-
-              select (edas[index], move (*r.builds));
+              if (postponed_alts != nullptr && index >= max_alt_index)
+              {
+                postpone (postponed_alts);
+                return true;
+              }
 
-              // Make sure no more true alternatives are selected during this
-              // function call.
+              // Select this alternative if all its dependencies are reused
+              // and do nothing about it otherwise.
               //
-              max_alt_index = 0;
-              return true;
-            }
-            else
-              return false;
-          };
+              if (r.reused)
+              {
+                // On the diagnostics run there shouldn't be any alternatives
+                // that we could potentially select.
+                //
+                assert (postponed_alts != nullptr);
 
-          // If we encountered the second satisfactory alternative, then this
-          // is the `multiple true alternatives` case. In this case we also
-          // need to process the first satisfactory alternative, which
-          // processing was delayed.
-          //
-          if (alts_num == 2)
-          {
-            assert (first_alt);
+                select (edas[index], move (*r.builds));
+
+                // Make sure no more true alternatives are selected during
+                // this function call.
+                //
+                max_alt_index = 0;
+                return true;
+              }
+              else
+                return false;
+            };
+
+            // If we encountered the second satisfactory alternative, then
+            // this is the "multiple true alternatives" case. In this case we
+            // also need to process the first satisfactory alternative, which
+            // processing was delayed.
+            //
+            if (alts_num == 2)
+            {
+              assert (first_alt);
+
+              if (try_select (first_alt->first, move (first_alt->second)))
+                break;
+            }
 
-            if (try_select (first_alt->first, move (first_alt->second)))
+            if (try_select (i, move (r)))
               break;
+
+            // Not all of the alternative dependencies are reused, so go to
+            // the next alternative.
           }
 
-          if (try_select (i, move (r)))
+          // Bail out if the collection is postponed for any reason.
+          //
+          if (postponed)
             break;
 
-          // Not all of the alternative dependencies are reused, so go to the
-          // next alternative.
-        }
+          // Select the single satisfactory alternative (regardless of its
+          // dependencies reuse).
+          //
+          if (!selected && alts_num == 1)
+          {
+            assert (first_alt && first_alt->second.builds);
 
-        // Bail out if the collection is postponed for any reason.
-        //
-        if (postponed)
-          break;
+            select (edas[first_alt->first], move (*first_alt->second.builds));
+          }
 
-        // Select the single satisfactory alternative (regardless of its
-        // dependencies reuse).
-        //
-        if (!selected && alts_num == 1)
-        {
-          assert (first_alt && first_alt->second.builds);
+          // If an alternative is selected, then we are done.
+          //
+          if (selected)
+            break;
 
-          select (edas[first_alt->first], move (*first_alt->second.builds));
-        }
+          // Fail or postpone the collection if no alternative is selected,
+          // unless we are in the "recreate dependency decisions" mode. In the
+          // latter case fall back to the "make dependency decisions" mode and
+          // retry.
+          //
+          if (prereqs != nullptr)
+          {
+            prereqs = nullptr;
+            continue;
+          }
 
-        // Fail or postpone the collection if no alternative is selected.
-        //
-        if (!selected)
-        {
           // Issue diagnostics and fail if there are no satisfactory
           // alternatives.
           //
@@ -2410,7 +2517,7 @@ namespace bpkg
           {
             diag_record dr;
             for (const dependency_alternative& da: edas)
-              precollect (da, das.buildtime, &dr);
+              precollect (da, das.buildtime, nullptr /* prereqs */, &dr);
 
             assert (!dr.empty ());
 
@@ -2438,7 +2545,8 @@ namespace bpkg
 
           for (const dependency_alternative& da: edas)
           {
-            precollect_result r (precollect (da, das.buildtime));
+            precollect_result r (
+              precollect (da, das.buildtime, nullptr /* prereqs */));
 
             if (r.builds)
             {
@@ -2457,6 +2565,9 @@ namespace bpkg
             }
           }
         }
+
+        if (postponed)
+          break;
       }
 
       dep_chain.pop_back ();
@@ -2526,7 +2637,7 @@ namespace bpkg
           move (rp.second),
           nullopt,                    // Dependencies.
           nullopt,                    // Package skeleton.
-          nullopt,                    // Enabled dependency alternatives.
+          nullopt,                    // Postponed dependency alternatives.
           nullopt,                    // Hold package.
           nullopt,                    // Hold version.
           {},                         // Constraints.
@@ -2571,7 +2682,7 @@ namespace bpkg
         nullptr,
         nullopt,    // Dependencies.
         nullopt,    // Package skeleton.
-        nullopt,    // Enable dependency alternatives.
+        nullopt,    // Postponed dependency alternatives.
         nullopt,    // Hold package.
         nullopt,    // Hold version.
         {},         // Constraints.
@@ -2625,7 +2736,7 @@ namespace bpkg
           nullptr,
           nullopt,    // Dependencies.
           nullopt,    // Package skeleton.
-          nullopt,    // Enabled dependency alternatives.
+          nullopt,    // Postponed dependency alternatives.
           nullopt,    // Hold package.
           nullopt,    // Hold version.
           {},         // Constraints.
@@ -2996,7 +3107,10 @@ namespace bpkg
             {
               check = dp.available == nullptr ||
                       (dsp->system () == dp.system &&
-                       dsp->version == dp.available_version ());
+                       dsp->version == dp.available_version () &&
+                       (dp.system               ||
+                        dp.config_vars.empty () ||
+                        !has_buildfile_clause (dp.available->dependencies)));
             }
           }
 
@@ -3060,7 +3174,7 @@ namespace bpkg
                 nullptr,
                 nullopt,                   // Dependencies.
                 nullopt,                   // Package skeleton.
-                nullopt,                   // Enabled dependency alternatives.
+                nullopt,                   // Postponed dependency alternatives.
                 nullopt,                   // Hold package.
                 nullopt,                   // Hold version.
                 {},                        // Constraints.
@@ -6033,7 +6147,7 @@ namespace bpkg
           move (af),
           nullopt,                    // Dependencies.
           nullopt,                    // Package skeleton.
-          nullopt,                    // Enabled dependency alternatives.
+          nullopt,                    // Postponed dependency alternatives.
           true,                       // Hold package.
           pa.constraint.has_value (), // Hold version.
           {},                         // Constraints.
@@ -6144,7 +6258,7 @@ namespace bpkg
                 move (apr.second),
                 nullopt,                    // Dependencies.
                 nullopt,                    // Package skeleton.
-                nullopt,                    // Enabled dependency alternatives.
+                nullopt,                    // Postponed dependency alternatives.
                 true,                       // Hold package.
                 false,                      // Hold version.
                 {},                         // Constraints.
@@ -6425,7 +6539,7 @@ namespace bpkg
             nullptr,
             nullopt,                    // Dependencies.
             nullopt,                    // Package skeleton.
-            nullopt,                    // Enabled dependency alternatives.
+            nullopt,                    // Postponed dependency alternatives.
             false,                      // Hold package.
             p.constraint.has_value (),  // Hold version.
             {},                         // Constraints.
@@ -6639,7 +6753,7 @@ namespace bpkg
               d.repository_fragment,
               nullopt,                    // Dependencies.
               nullopt,                    // Package skeleton.
-              nullopt,                    // Enabled dependency alternatives.
+              nullopt,                    // Postponed dependency alternatives.
               nullopt,                    // Hold package.
               nullopt,                    // Hold version.
               {},                         // Constraints.
@@ -7728,6 +7842,15 @@ namespace bpkg
       prog_percent = 100;
     }
 
+    // On the package reconfiguration we will try to resolve dependencies to
+    // the same prerequisites (see pkg_configure() for details). For that, we
+    // will save prerequisites before disfiguring the dependents. Note,
+    // though, that this is not required for dependents with the collected
+    // prerequisites builds since the dependency alternatives are already
+    // selected for them.
+    //
+    map<const build_package*, vector<package_name>> previous_prerequisites;
+
     for (build_package& p: build_pkgs)
     {
       assert (p.action);
@@ -7758,6 +7881,18 @@ namespace bpkg
           p.keep_out = false;
       }
 
+      if (*p.action != build_package::drop &&
+          !p.skeleton                      &&
+          !sp->prerequisites.empty ())
+      {
+        vector<package_name>& ps (previous_prerequisites[&p]);
+
+        ps.reserve (sp->prerequisites.size ());
+
+        for (const auto& pp: sp->prerequisites)
+          ps.push_back (pp.first.object_id ());
+      }
+
       // For an external package being replaced with another external, keep
       // the configuration unless requested not to with --disfigure.
       //
@@ -8162,6 +8297,12 @@ namespace bpkg
             info << "while configuring " << p.name () << p.db;
           }));
 
+      auto prereqs = [&p, &previous_prerequisites] ()
+      {
+        auto i (previous_prerequisites.find (&p));
+        return i != previous_prerequisites.end () ? &i->second : nullptr;
+      };
+
       // Note that pkg_configure() commits the transaction.
       //
       if (p.system)
@@ -8202,6 +8343,7 @@ namespace bpkg
                          sp,
                          *p.dependencies,
                          move (*p.skeleton),
+                         nullptr /* previous_prerequisites */,
                          simulate,
                          fdb);
         }
@@ -8227,6 +8369,7 @@ namespace bpkg
                                            move (p.config_vars),
                                            move (src_root),
                                            move (out_root)),
+                         prereqs (),
                          simulate,
                          fdb);
         }
@@ -8286,6 +8429,7 @@ namespace bpkg
                                          move (p.config_vars),
                                          move (src_root),
                                          move (out_root)),
+                       prereqs (),
                        simulate,
                        fdb);
       }
diff --git a/bpkg/pkg-configure.cxx b/bpkg/pkg-configure.cxx
index 0519f7c..1392545 100644
--- a/bpkg/pkg-configure.cxx
+++ b/bpkg/pkg-configure.cxx
@@ -49,6 +49,7 @@ namespace bpkg
                                transaction&,
                                const dependencies& deps,
                                package_skeleton&& ps,
+                               const vector<package_name>* prev_prereqs,
                                bool simulate,
                                const function<find_database_function>& fdb)
   {
@@ -58,150 +59,189 @@ namespace bpkg
 
     for (size_t di (0); di != deps.size (); ++di)
     {
+      // Skip the toolchain build-time dependencies and dependencies without
+      // enabled alternatives.
+      //
       const dependency_alternatives_ex& das (deps[di]);
 
       if (das.empty () || toolchain_buildtime_dependency (o, das, ps.name ()))
         continue;
 
-      // Pick the first alternative with dependencies that can all be resolved
-      // to the configured packages, satisfying the respective constraints.
-      //
-      bool satisfied (false);
-      bool enabled   (false); // True if there is an enabled alternative.
+      small_vector<reference_wrapper<const dependency_alternative>, 2> edas;
+
       for (const dependency_alternative& da: das)
       {
-        if (da.enable && !ps.evaluate_enable (*da.enable, di))
-          continue;
-
-        enabled = true;
-
-        // Cache the selected packages which correspond to the alternative
-        // dependencies, pairing them with the respective constraints. If the
-        // alternative turns out to be fully resolvable, we will add the
-        // cached packages into the dependent's prerequisites map.
-        //
-        small_vector<
-          pair<lazy_shared_ptr<selected_package>,
-               const optional<version_constraint>&>, 1> prerequisites;
-
-        dependency_alternative::const_iterator b (da.begin ());
-        dependency_alternative::const_iterator i (b);
-        dependency_alternative::const_iterator e (da.end ());
+        if (!da.enable || ps.evaluate_enable (*da.enable, di))
+          edas.push_back (da);
+      }
 
-        assert (b != e);
+      if (edas.empty ())
+        continue;
 
-        for (; i != e; ++i)
+      // Pick the first alternative with dependencies that can all be resolved
+      // to the configured packages, satisfying the respective constraints.
+      //
+      // If the list of the former prerequisites is specified, then first try
+      // to select an alternative in the "recreate dependency decisions" mode,
+      // filtering out alternatives where dependencies do not all belong to
+      // this list. If we end up with no alternative selected, then retry in
+      // the "make dependency decisions" mode and select the alternative
+      // regardless of the former prerequisites.
+      //
+      for (const vector<package_name>* pps (prev_prereqs);;)
+      {
+        bool satisfied (false);
+        for (const dependency_alternative& da: edas)
         {
-          const dependency&   d (*i);
-          const package_name& n (d.name);
-
-          database* ddb (fdb ? fdb (db, n, das.buildtime) : nullptr);
+          // Cache the selected packages which correspond to the alternative
+          // dependencies, pairing them with the respective constraints. If
+          // the alternative turns out to be fully resolvable, we will add the
+          // cached packages into the dependent's prerequisites map.
+          //
+          small_vector<
+            pair<lazy_shared_ptr<selected_package>,
+                 const optional<version_constraint>&>, 1> prerequisites;
 
-          pair<shared_ptr<selected_package>, database*> spd (
-            ddb != nullptr
-            ? make_pair (ddb->find<selected_package> (n), ddb)
-            : find_dependency (db, n, das.buildtime));
+          dependency_alternative::const_iterator b (da.begin ());
+          dependency_alternative::const_iterator i (b);
+          dependency_alternative::const_iterator e (da.end ());
 
-          const shared_ptr<selected_package>& dp (spd.first);
+          assert (b != e);
 
-          if (dp == nullptr                          ||
-              dp->state != package_state::configured ||
-              !satisfies (dp->version, d.constraint))
-            break;
+          for (; i != e; ++i)
+          {
+            const dependency&   d (*i);
+            const package_name& n (d.name);
+
+            database* ddb (fdb ? fdb (db, n, das.buildtime) : nullptr);
+
+            pair<shared_ptr<selected_package>, database*> spd (
+              ddb != nullptr
+              ? make_pair (ddb->find<selected_package> (n), ddb)
+              : find_dependency (db, n, das.buildtime));
+
+            const shared_ptr<selected_package>& dp (spd.first);
+
+            if (dp == nullptr                          ||
+                dp->state != package_state::configured ||
+                !satisfies (dp->version, d.constraint) ||
+                (pps != nullptr &&
+                 find (pps->begin (), pps->end (), dp->name) == pps->end ()))
+              break;
+
+            // See the package_prerequisites definition for details on
+            // creating the map keys with the database passed.
+            //
+            prerequisites.emplace_back (
+              lazy_shared_ptr<selected_package> (*spd.second, dp),
+              d.constraint);
+          }
 
-          // See the package_prerequisites definition for details on creating
-          // the map keys with the database passed.
+          // Try the next alternative if there are unresolved dependencies for
+          // this alternative.
           //
-          prerequisites.emplace_back (
-            lazy_shared_ptr<selected_package> (*spd.second, dp),
-            d.constraint);
-        }
+          if (i != e)
+            continue;
 
-        // Try the next alternative if there are unresolved dependencies for
-        // this alternative.
-        //
-        if (i != e)
-          continue;
-
-        // Now add the selected packages resolved for the alternative into the
-        // dependent's prerequisites map and skip the remaining alternatives.
-        //
-        for (auto& pr: prerequisites)
-        {
-          const package_name& pn (pr.first.object_id ());
-          const optional<version_constraint>& pc (pr.second);
-
-          auto p (prereqs.emplace (pr.first, pc));
-
-          // Currently we can only capture a single constraint, so if we
-          // already have a dependency on this package and one constraint is
-          // not a subset of the other, complain.
+          // Now add the selected packages resolved for the alternative into
+          // the dependent's prerequisites map and skip the remaining
+          // alternatives.
           //
-          if (!p.second)
+          for (auto& pr: prerequisites)
           {
-            auto& c (p.first->second);
+            const package_name& pn (pr.first.object_id ());
+            const optional<version_constraint>& pc (pr.second);
 
-            bool s1 (satisfies (c, pc));
-            bool s2 (satisfies (pc, c));
+            auto p (prereqs.emplace (pr.first, pc));
 
-            if (!s1 && !s2)
-              fail << "multiple dependencies on package " << pn <<
-                info << pn << " " << *c <<
-                info << pn << " " << *pc;
+            // Currently we can only capture a single constraint, so if we
+            // already have a dependency on this package and one constraint is
+            // not a subset of the other, complain.
+            //
+            if (!p.second)
+            {
+              auto& c (p.first->second);
 
-            if (s2 && !s1)
-              c = pc;
-          }
+              bool s1 (satisfies (c, pc));
+              bool s2 (satisfies (pc, c));
 
-          // If the prerequisite is configured in the linked configuration,
-          // then add the respective config.import.* variable.
-          //
-          if (!simulate)
-          {
-            database& pdb (pr.first.database ());
+              if (!s1 && !s2)
+                fail << "multiple dependencies on package " << pn <<
+                  info << pn << " " << *c <<
+                  info << pn << " " << *pc;
+
+              if (s2 && !s1)
+                c = pc;
+            }
 
-            if (pdb != db)
+            // If the prerequisite is configured in the linked configuration,
+            // then add the respective config.import.* variable.
+            //
+            if (!simulate)
             {
-              shared_ptr<selected_package> sp (pr.first.load ());
+              database& pdb (pr.first.database ());
 
-              if (!sp->system ())
+              if (pdb != db)
               {
-                // @@ Note that this doesn't work for build2 modules that
-                //    require bootstrap. For their dependents we need to
-                //    specify the import variable as a global override,
-                //    whenever required (configure, update, etc).
-                //
-                //    This, in particular, means that if we build a package
-                //    that doesn't have direct build2 module dependencies but
-                //    some of its (potentially indirect) dependencies do, then
-                //    we still need to specify the !config.import.* global
-                //    overrides for all of the involved build2
-                //    modules. Implementation of that feels too hairy at the
-                //    moment, so let's handle all the build2 modules uniformly
-                //    for now.
-                //
-                //    Also note that such modules are marked with `requires:
-                //    bootstrap` in their manifest.
-                //
-                dir_path od (sp->effective_out_root (pdb.config));
-                vars.push_back ("config.import." + sp->name.variable () +
-                                "='" + od.representation () + "'");
+                shared_ptr<selected_package> sp (pr.first.load ());
+
+                if (!sp->system ())
+                {
+                  // @@ Note that this doesn't work for build2 modules that
+                  //    require bootstrap. For their dependents we need to
+                  //    specify the import variable as a global override,
+                  //    whenever required (configure, update, etc).
+                  //
+                  //    This, in particular, means that if we build a package
+                  //    that doesn't have direct build2 module dependencies
+                  //    but some of its (potentially indirect) dependencies
+                  //    do, then we still need to specify the !config.import.*
+                  //    global overrides for all of the involved build2
+                  //    modules. Implementation of that feels too hairy at the
+                  //    moment, so let's handle all the build2 modules
+                  //    uniformly for now.
+                  //
+                  //    Also note that such modules are marked with `requires:
+                  //    bootstrap` in their manifest.
+                  //
+                  dir_path od (sp->effective_out_root (pdb.config));
+                  vars.push_back ("config.import." + sp->name.variable () +
+                                  "='" + od.representation () + "'");
+                }
               }
             }
           }
+
+          // Evaluate the dependency alternative reflect clause, if present.
+          //
+          if (da.reflect)
+            ps.evaluate_reflect (*da.reflect, di);
+
+          satisfied = true;
+          break;
         }
 
-        // Evaluate the dependency alternative reflect clause, if present.
+        // Fail if no dependency alternative is selected, unless we are in the
+        // "recreate dependency decisions" mode. In the latter case fall back
+        // to the "make dependency decisions" mode and retry.
         //
-        if (da.reflect)
-          ps.evaluate_reflect (*da.reflect, di);
+        if (!satisfied)
+        {
+          if (pps != nullptr)
+          {
+            pps = nullptr;
+            continue;
+          }
+
+          fail << "unable to satisfy dependency on " << das;
+        }
 
-        satisfied = true;
+        // The dependency alternative is selected and its dependencies are
+        // resolved to the selected packages. So proceed to the next depends
+        // value.
+        //
         break;
       }
-
-      if (enabled && !satisfied)
-        fail << "unable to satisfy dependency on " << das;
     }
 
     // Add the configuration variables collected from the reflect clauses, if
@@ -248,6 +288,7 @@ namespace bpkg
                  const shared_ptr<selected_package>& p,
                  const dependencies& deps,
                  package_skeleton&& ps,
+                 const vector<package_name>* pps,
                  bool simulate,
                  const function<find_database_function>& fdb)
   {
@@ -282,6 +323,7 @@ namespace bpkg
                                    t,
                                    deps,
                                    move (ps),
+                                   pps,
                                    simulate,
                                    fdb));
 
@@ -523,6 +565,7 @@ namespace bpkg
                                        move (vars),
                                        move (src_root),
                                        move (out_root)),
+                     nullptr /* prerequisites */,
                      false /* simulate */);
     }
 
diff --git a/bpkg/pkg-configure.hxx b/bpkg/pkg-configure.hxx
index 5d6b2eb..23dab83 100644
--- a/bpkg/pkg-configure.hxx
+++ b/bpkg/pkg-configure.hxx
@@ -37,6 +37,12 @@ namespace bpkg
   // dependency alternatives lists are allowed and are ignored (see pkg-build
   // for the use-case).
   //
+  // If prerequisites corresponding to the previous configured state of the
+  // package are specified, then for each depends value try to select an
+  // alternative where dependencies all belong to this list (the "recreate
+  // dependency decisions" mode). Failed that, select an alternative as if no
+  // prerequisites are specified (the "make dependency decisions" mode).
+  //
   void
   pkg_configure (const common_options&,
                  database&,
@@ -44,6 +50,7 @@ namespace bpkg
                  const shared_ptr<selected_package>&,
                  const dependencies&,
                  package_skeleton&&,
+                 const vector<package_name>* prerequisites,
                  bool simulate,
                  const function<find_database_function>& = {});
 
diff --git a/tests/common/dependency-alternatives/t8a/box-1.0.0.tar.gz b/tests/common/dependency-alternatives/t8a/box-1.0.0.tar.gz
new file mode 100644
index 0000000..babc96c
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/box-1.0.0.tar.gz
diff --git a/tests/common/dependency-alternatives/t8a/libbox-0.1.0.tar.gz b/tests/common/dependency-alternatives/t8a/libbox-0.1.0.tar.gz
new file mode 100644
index 0000000..0d4c32d
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/libbox-0.1.0.tar.gz
diff --git a/tests/common/dependency-alternatives/t8a/libbox-0.1.1.tar.gz b/tests/common/dependency-alternatives/t8a/libbox-0.1.1.tar.gz
new file mode 100644
index 0000000..a14d55a
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/libbox-0.1.1.tar.gz
diff --git a/tests/pkg-build.testscript b/tests/pkg-build.testscript
index 8ee0ee1..74fbb67 100644
--- a/tests/pkg-build.testscript
+++ b/tests/pkg-build.testscript
@@ -142,6 +142,8 @@
 # |   |-- libbaz-1.1.0.tar.gz
 # |   |-- libbiz-0.1.0.tar.gz
 # |   |-- libbiz-1.0.0.tar.gz
+# |   |-- libbox-0.1.0.tar.gz
+# |   |-- libbox-0.1.1.tar.gz
 # |   |-- libbox-1.0.0.tar.gz
 # |   |-- foo-1.0.0.tar.gz      -> {libbar libbaz} ^1.0.0
 # |   |-- fox-1.0.0.tar.gz      -> libbar ^1.0.0 | libbaz ^1.0.0
@@ -151,6 +153,9 @@
 # |   |                            libbiz ? ($config.fax.libbiz) config.fax.extras='[b\i$z]',
 # |   |                            libbox ? ($config.fax.libbox && $config.fax.backend == libbaz && $config.fax.extras == '[b\i$z]')
 # |   |-- fux                   -> libbiz ? (!$config.fux.libbiz_old) | libbiz ^0.1.0 ? ($config.fux.libbiz_old)
+# |   |-- box                   -> libbiz ^1.0.0 config.box.backend=libbiz |
+# |   |                            libbox >= 0.1.1 config.box.backend=libbox,
+# |   |                            libbaz
 # |   `-- repositories.manifest
 # |
 # |-- t9
@@ -2309,10 +2314,10 @@ test.options += --no-progress
 
         $* libbiz 2>>EOE != 0;
           error: unable to satisfy constraints on package libfoo
-            info: libbox depends on (libfoo == 1.0.0)
             info: libfox depends on (libfoo == 0.0.1)
-            info: available libfoo/1.0.0
+            info: libbox depends on (libfoo == 1.0.0)
             info: available libfoo/0.0.1
+            info: available libfoo/1.0.0
             info: explicitly specify libfoo version to manually satisfy both constraints
           info: while satisfying libbox/0.0.2
           info: while satisfying libbiz/0.0.1
@@ -3377,6 +3382,8 @@ test.options += --no-progress
     {
       +$clone_cfg
 
+      test.arguments += --yes
+
       : ambiguity
       :
       {
@@ -3465,7 +3472,7 @@ test.options += --no-progress
 
           $pkg_fetch libbaz/1.0.0;
 
-          $* fox --yes 2>>~%EOE%;
+          $* fox 2>>~%EOE%;
             unpacked libbaz/1.0.0
             fetched fox/1.0.0
             unpacked fox/1.0.0
@@ -3489,7 +3496,7 @@ test.options += --no-progress
         {
           $clone_cfg;
 
-          $* fox foo --yes 2>>~%EOE%;
+          $* fox foo 2>>~%EOE%;
             fetched libbaz/1.1.0
             unpacked libbaz/1.1.0
             fetched libbar/1.0.0
@@ -3517,7 +3524,7 @@ test.options += --no-progress
         {
           $clone_cfg;
 
-          $* baz fox bar --yes 2>>~%EOE%;
+          $* baz fox bar 2>>~%EOE%;
             fetched libbaz/1.1.0
             unpacked libbaz/1.1.0
             fetched baz/1.0.0
@@ -3571,7 +3578,7 @@ test.options += --no-progress
           updated fox/1.0.0
           EOE
 
-        $* ?libbaz --yes 2>>~%EOE%;
+        $* ?libbaz 2>>~%EOE%;
           disfigured fox/1.0.0
           disfigured libbaz/1.0.0
           fetched libbaz/1.1.0
@@ -3592,6 +3599,234 @@ test.options += --no-progress
 
         $pkg_drop fox
       }
+
+      : recreate-decision
+      :
+      {
+        +$clone_cfg
+
+        : reevaluate-alternatives
+        :
+        {
+          +$clone_cfg
+
+          : preserve
+          :
+          : Test that the existing libbox dependency is preserved even though
+          : libbiz is more preferable as a dependency.
+          :
+          {
+            $clone_cfg;
+
+            $* box libbox 2>!;
+
+            $* box +{ config.box.extras=true } ?libbiz 2>>~%EOE%;
+              disfigured box/1.0.0
+              configured box/1.0.0
+              %info: .+box-1.0.0.+ is up to date%
+              updated box/1.0.0
+              EOE
+
+            $* box +{ config.box.extras=false } libbiz 2>>~%EOE%;
+              disfigured box/1.0.0
+              fetched libbiz/1.0.0
+              unpacked libbiz/1.0.0
+              configured box/1.0.0
+              configured libbiz/1.0.0
+              %info: .+box-1.0.0.+ is up to date%
+              %info: .+libbiz-1.0.0.+ is up to date%
+              updated box/1.0.0
+              updated libbiz/1.0.0
+              EOE
+
+            $pkg_status -r box >>EOO;
+              !box configured 1.0.0
+                libbaz configured 1.1.0
+                !libbox configured 1.0.0
+              EOO
+
+            cat cfg/box-1.0.0/build/config.build >>~%EOO%;
+              %.*
+              config.box.backend = libbox
+              EOO
+
+            $pkg_drop box;
+            $pkg_drop libbox;
+            $pkg_drop libbiz
+          }
+
+          : change-downgraded-depenency
+          :
+          : Test that libbiz is selected as a dependency since the existing
+          : dependency decision cannot be preserved (libbox is downgraded to
+          : 0.1.0 and becomes unsatisfactory for box).
+          :
+          {
+            $clone_cfg;
+
+            $* box libbox 2>!;
+
+            $* box +{ config.box.extras=true } ?libbox/0.1.0 2>>~%EOE%;
+              disfigured box/1.0.0
+              disfigured libbox/1.0.0
+              fetched libbiz/1.0.0
+              unpacked libbiz/1.0.0
+              purged libbox/1.0.0
+              configured libbiz/1.0.0
+              configured box/1.0.0
+              %info: .+box-1.0.0.+ is up to date%
+              updated box/1.0.0
+              EOE
+
+            $pkg_status -r box >>EOO;
+              !box configured 1.0.0
+                libbaz configured 1.1.0
+                libbiz configured 1.0.0
+              EOO
+
+            cat cfg/box-1.0.0/build/config.build >>~%EOO%;
+              %.*
+              config.box.backend = libbiz
+              EOO
+
+            $pkg_drop box
+          }
+
+          : change-downgraded-hold
+          :
+          : As above but libbox is downgraded to hold.
+          :
+          {
+            $clone_cfg;
+
+            $* box libbox 2>!;
+
+            $* box +{ config.box.extras=true } libbox/0.1.0 2>>~%EOE%;
+              disfigured box/1.0.0
+              disfigured libbox/1.0.0
+              fetched libbiz/1.0.0
+              unpacked libbiz/1.0.0
+              fetched libbox/0.1.0
+              unpacked libbox/0.1.0
+              configured libbiz/1.0.0
+              configured libbox/0.1.0
+              configured box/1.0.0
+              %info: .+libbox-0.1.0.+ is up to date%
+              %info: .+box-1.0.0.+ is up to date%
+              updated libbox/0.1.0
+              updated box/1.0.0
+              EOE
+
+            $pkg_status -r box >>EOO;
+              !box configured 1.0.0
+                libbaz configured 1.1.0
+                libbiz configured 1.0.0
+              EOO
+
+            cat cfg/box-1.0.0/build/config.build >>~%EOO%;
+              %.*
+              config.box.backend = libbiz
+              EOO
+
+            $pkg_drop box;
+            $pkg_drop libbox
+          }
+        }
+
+        : reconfigure
+        :
+        {
+          $clone_cfg;
+
+          $* box ?libbiz/0.1.0 2>>~%EOE%;
+            fetched libbox/1.0.0
+            unpacked libbox/1.0.0
+            fetched libbaz/1.1.0
+            unpacked libbaz/1.1.0
+            fetched box/1.0.0
+            unpacked box/1.0.0
+            configured libbox/1.0.0
+            configured libbaz/1.1.0
+            configured box/1.0.0
+            %info: .+box-1.0.0.+ is up to date%
+            updated box/1.0.0
+            EOE
+
+          $pkg_status -r >>EOO;
+            !box configured 1.0.0
+              libbaz configured 1.1.0
+              libbox configured 1.0.0
+            EOO
+
+          cat cfg/box-1.0.0/build/config.build >>~%EOO%;
+            %.*
+            config.box.backend = libbox
+            EOO
+
+          # Downgrade libbaz to reconfigure box and make sure we still keep
+          # libbox as a prerequisite of box.
+          #
+          $* libbiz ?libbaz/1.0.0 2>>~%EOE%;
+            disfigured box/1.0.0
+            disfigured libbaz/1.1.0
+            fetched libbiz/1.0.0
+            unpacked libbiz/1.0.0
+            fetched libbaz/1.0.0
+            unpacked libbaz/1.0.0
+            configured libbiz/1.0.0
+            configured libbaz/1.0.0
+            configured box/1.0.0
+            %info: .+libbiz-1.0.0.+ is up to date%
+            %info: .+libbaz-1.0.0.+ is up to date%
+            %info: .+box-1.0.0.+ is up to date%
+            updated libbiz/1.0.0
+            updated libbaz/1.0.0
+            updated box/1.0.0
+            EOE
+
+          $pkg_status -r >>EOO;
+            !box configured 1.0.0
+              libbaz configured !1.0.0 available 1.1.0
+              libbox configured 1.0.0
+            !libbiz configured 1.0.0
+            EOO
+
+          cat cfg/box-1.0.0/build/config.build >>~%EOO%;
+            %.*
+            config.box.backend = libbox
+            EOO
+
+          # Make sure the decision is hold for downgraded dependency either.
+          #
+          $* ?libbox/0.1.1 2>>~%EOE%;
+            disfigured box/1.0.0
+            disfigured libbox/1.0.0
+            fetched libbox/0.1.1
+            unpacked libbox/0.1.1
+            configured libbox/0.1.1
+            configured box/1.0.0
+            %info: .+libbox-0.1.1.+ is up to date%
+            %info: .+box-1.0.0.+ is up to date%
+            updated libbox/0.1.1
+            updated box/1.0.0
+            EOE
+
+          $pkg_status -r >>EOO;
+            !box configured 1.0.0
+              libbaz configured !1.0.0 available 1.1.0
+              libbox configured !0.1.1 available 1.0.0
+            !libbiz configured 1.0.0
+            EOO
+
+          cat cfg/box-1.0.0/build/config.build >>~%EOO%;
+            %.*
+            config.box.backend = libbox
+            EOO
+
+          $pkg_drop box;
+          $pkg_drop libbiz
+        }
+      }
     }
 
     : enable-condition