Postpone 'unable to satisfy constraints' failure similar to what we do in collect_order_dependents()

9 files changed, 591 insertions, 269 deletions

diff --git a/bpkg/pkg-build-collect.cxx b/bpkg/pkg-build-collect.cxx
index 5827d6d..67357f8 100644
--- a/bpkg/pkg-build-collect.cxx
+++ b/bpkg/pkg-build-collect.cxx
@@ -430,6 +430,33 @@ namespace bpkg
 
   // unsatisfied_dependents
   //
+  void unsatisfied_dependents::
+  add (const package_key& dpt,
+       const build_package* dep,
+       const version_constraint& c)
+  {
+    if (unsatisfied_dependent* ud = find_dependent (dpt))
+    {
+      vector<pair<const build_package*, version_constraint>>& deps (
+        ud->dependencies);
+
+      // Skip the dependency if it is already in the list.
+      //
+      // It feels that it may already be present in the list with a different
+      // constraint (think of multiple depends clauses with the same
+      // dependency), in which case we leave it unchanged.
+      //
+      if (find_if (deps.begin (), deps.end (),
+                   [dep] (const auto& v) {return v.first == dep;}) ==
+          deps.end ())
+      {
+        deps.push_back (make_pair (dep, c));
+      }
+    }
+    else
+      push_back (unsatisfied_dependent {dpt, {make_pair (dep, c)}});
+  }
+
   unsatisfied_dependent* unsatisfied_dependents::
   find_dependent (const package_key& dk)
   {
@@ -451,21 +478,25 @@ namespace bpkg
     assert (!dpt.dependencies.empty ());
 
     const package_key& dk (dpt.dependent);
-    build_package& p (*dpt.dependencies.front ().first);
+    const build_package& p (*dpt.dependencies.front ().first);
     const version_constraint& c (dpt.dependencies.front ().second);
 
     database& pdb (p.db);
     const shared_ptr<selected_package>& sp (p.selected);
 
     const package_name& n (sp->name);
+
+    // Otherwise, this would be a dependency adjustment (not an
+    // up/down-grade), and thus the dependent must be satisfied with the
+    // already configured dependency.
+    //
+    assert (p.available != nullptr);
+
     const version& av (p.available_version ());
 
-    // See if we are up/downgrading this package. In particular, the available
-    // package could be NULL meaning we are just adjusting.
+    // See if we are upgrading or downgrading this package.
     //
-    int ud (p.available != nullptr
-            ? sp->version.compare (p.available_version ())
-            : 0);
+    int ud (sp->version.compare (av));
 
     // Otherwise, the dependent must be satisfied with the already configured
     // dependency.
@@ -473,7 +504,6 @@ namespace bpkg
     assert (ud != 0);
 
     diag_record dr (fail);
-
     dr << "unable to " << (ud < 0 ? "up" : "down") << "grade "
        << "package " << *sp << pdb << " to ";
 
@@ -485,8 +515,8 @@ namespace bpkg
     else
       dr << av; // Can't be the wildcard otherwise would satisfy.
 
-    dr << info << "because package " << dk << " depends on (" << n << " "
-       << c << ")";
+    dr << info << "because package " << dk << " depends on (" << n << ' '
+               << c << ')';
 
     {
       //             "  info: ..."
@@ -504,7 +534,7 @@ namespace bpkg
 
     if (!rb.empty ())
       dr << info << "package " << p.available_name_version ()
-         << " required by" << rb;
+                 << " required by" << rb;
 
     dr << info << "consider re-trying with --upgrade|-u potentially combined "
                << "with --recursive|-r" <<
@@ -1172,6 +1202,28 @@ namespace bpkg
     return *this;
   }
 
+  const build_package* build_packages::
+  dependent_build (const build_package::constraint_type& c) const
+  {
+    const build_package* r (nullptr);
+    const string& d (c.dependent);
+
+    if (d != "command line")
+    try
+    {
+      r = entered_build (c.db, package_name (d));
+      assert (r != nullptr); // Expected to be collected.
+    }
+    catch (const invalid_argument&)
+    {
+      // Must be a package name, unless it is 'command line'.
+      //
+      assert (false);
+    }
+
+    return r;
+  }
+
   void build_packages::
   enter (package_name name, build_package pkg)
   {
@@ -1189,6 +1241,7 @@ namespace bpkg
                  build_package pkg,
                  replaced_versions& replaced_vers,
                  postponed_configurations& postponed_cfgs,
+                 unsatisfied_dependents& unsatisfied_depts,
                  build_package_refs* dep_chain,
                  const function<find_database_function>& fdb,
                  const function<add_priv_cfg_function>& apc,
@@ -1334,64 +1387,129 @@ namespace bpkg
         // If the versions differ, pick the satisfactory one and if both are
         // satisfactory, then keep the preferred.
         //
+        // If neither of the versions is satisfactory, then ignore those
+        // unsatisfied constraints which are imposed by the existing
+        // dependents which are not being up/downgraded and record them in
+        // unsatisfied_depts in the hope that the problem will resolve
+        // naturally (see unsatisfied_dependents for details). Fail if neither
+        // of the versions is still satisfactory after that.
+        //
         if (p1->available_version () != p2->available_version ())
         {
           using constraint_type = build_package::constraint_type;
 
-          // See if pv's version satisfies pc's constraints. Return the
-          // pointer to the unsatisfied constraint or NULL if all are
-          // satisfied.
+          // See if pv's version satisfies pc's constraints, skipping those
+          // which are meant to be ignored (ics). Return the pointer to the
+          // unsatisfied constraint or NULL if all are satisfied.
           //
-          auto test = [] (build_package* pv,
-                          build_package* pc) -> const constraint_type*
+          vector<const constraint_type*> ics;
+
+          auto test = [&ics] (build_package* pv, build_package* pc)
+            -> const constraint_type*
           {
             for (const constraint_type& c: pc->constraints)
             {
-              if (!satisfies (pv->available_version (), c.value))
+              if (find (ics.begin (), ics.end (), &c) == ics.end () &&
+                  !satisfies (pv->available_version (), c.value))
                 return &c;
             }
 
             return nullptr;
           };
 
-          // First see if p1 satisfies p2's constraints.
+          // Iterate until some of the version becomes satisfactory due to
+          // ignoring some of the constraints or until there is nothing more
+          // to ignore, in which case we fail.
           //
-          if (auto c2 = test (p1, p2))
+          for (;;)
           {
-            // If not, try the other way around.
+            // First see if p1 satisfies p2's constraints.
             //
-            if (auto c1 = test (p2, p1))
+            if (auto c2 = test (p1, p2))
             {
-              const package_name& n (i->first.name);
+              // If not, try the other way around.
+              //
+              if (auto c1 = test (p2, p1))
+              {
+                // Return true if a constraint is imposed by a being
+                // reconfigured (not being up/downgraded) dependent.
+                //
+                auto existing_dependent = [this] (const constraint_type& c)
+                {
+                  const build_package* p (dependent_build (c));
+                  return p != nullptr           &&
+                         p->selected != nullptr &&
+                         (p->available == nullptr ||
+                          p->selected->version.compare (
+                            p->available_version ()) == 0);
+                };
 
-              //             "  info: ..."
-              string indent ("          ");
+                // Add a constraint to the igrore-list and the dependent to
+                // the unsatisfied-list.
+                //
+                auto ignore_constraint = [&ics,
+                                          &bp,
+                                          &unsatisfied_depts,
+                                          this] (const constraint_type& c)
+                {
+                  ics.push_back (&c);
 
-              diag_record dr (fail);
-              dr << "unable to satisfy constraints on package " << n <<
-                info << c1->dependent << c1->db << " depends on (" << n << ' '
-                     << c1->value << ")";
+                  const build_package* p (dependent_build (c));
+                  assert (p != nullptr);
 
-              {
-                set<package_key> printed;
-                print_constraints (dr, *c1, indent, printed);
-              }
+                  unsatisfied_depts.add (package_key (p->db, p->name ()),
+                                         &bp,
+                                         c.value);
+                };
 
-              dr << info << c2->dependent << c2->db << " depends on (" << n
-                         << ' ' << c2->value << ")";
+                if (existing_dependent (*c2))
+                {
+                  ignore_constraint (*c2);
+                  continue;
+                }
 
-              {
-                set<package_key> printed;
-                print_constraints (dr, *c2, indent, printed);
-              }
+                if (existing_dependent (*c1))
+                {
+                  ignore_constraint (*c1);
+                  swap (p1, p2);
+                  continue;
+                }
+
+                const package_name& n (i->first.name);
+
+                //             "  info: ..."
+                string indent ("          ");
+
+                diag_record dr (fail);
+                dr << "unable to satisfy constraints on package " << n <<
+                  info << c1->dependent << c1->db << " depends on (" << n
+                       << ' ' << c1->value << ")";
+
+                if (const build_package* d = dependent_build (*c1))
+                {
+                  set<package_key> printed;
+                  print_constraints (dr, *d, indent, printed);
+                }
+
+                dr << info << c2->dependent << c2->db << " depends on (" << n
+                           << ' ' << c2->value << ")";
+
+                if (const build_package* d = dependent_build (*c2))
+                {
+                  set<package_key> printed;
+                  print_constraints (dr, *d, indent, printed);
+                }
 
-              dr << info << "available " << p1->available_name_version () <<
-                    info << "available " << p2->available_name_version () <<
-                    info << "explicitly specify " << n << " version to "
-                         << "manually satisfy both constraints";
+                dr << info << "available " << p1->available_name_version () <<
+                      info << "available " << p2->available_name_version () <<
+                      info << "explicitly specify " << n << " version to "
+                           << "manually satisfy both constraints";
+              }
+              else
+                swap (p1, p2);
             }
-            else
-              swap (p1, p2);
+
+            break;
           }
 
           l4 ([&]{trace << "pick " << p1->available_name_version_db ()
@@ -1444,15 +1562,21 @@ namespace bpkg
             //
             // An update: it turned out that just the absence of dependencies
             // is not the only condition that causes a package to be replaced
-            // in place. It must also not participate in any configuration
-            // negotiation on the dependency side (otherwise we could have
-            // missed collecting its existing dependents). Also, we need to
-            // make sure that the package up/downgrade doesn't cause the
-            // selection of a different dependency alternative for any of its
-            // dependents (see postponed_packages for possible outcomes). This
-            // all sounds quite hairy at the moment, so we won't be replacing
-            // in place for now (which is an optimization).
+            // in place. The following conditions must also be met:
+            //
+            // - The package must not participate in any configuration
+            //   negotiation on the dependency side (otherwise we could have
+            //   missed collecting its existing dependents).
             //
+            // - The package up/downgrade doesn't cause the selection of a
+            //   different dependency alternative for any of its dependents
+            //   (see postponed_packages for possible outcomes).
+            //
+            // - The package must not be added to unsatisfied_depts on the
+            //   dependency side.
+            //
+            // This all sounds quite hairy at the moment, so we won't be
+            // replacing in place for now (which is an optimization).
 #if 0
             if (!has_dependencies (options, p2->available->dependencies))
               scratch = false;
@@ -1528,7 +1652,8 @@ namespace bpkg
                                    *postponed_edeps,
                                    *postponed_deps,
                                    postponed_cfgs,
-                                   *unacceptable_alts);
+                                   *unacceptable_alts,
+                                   unsatisfied_depts);
 
     return &p;
   }
@@ -1549,6 +1674,7 @@ namespace bpkg
                                postponed_dependencies& postponed_deps,
                                postponed_configurations& postponed_cfgs,
                                unacceptable_alternatives& unacceptable_alts,
+                               unsatisfied_dependents& unsatisfied_depts,
                                optional<pair<size_t, size_t>> reeval_pos,
                                const optional<package_key>& orig_dep)
   {
@@ -1638,7 +1764,8 @@ namespace bpkg
               bp = collect_existing_dependent_dependency (options,
                                                           ed,
                                                           replaced_vers,
-                                                          postponed_cfgs);
+                                                          postponed_cfgs,
+                                                          unsatisfied_depts);
 
             // If the dependency collection has already been postponed, then
             // indicate that the dependent with configuration clauses is also
@@ -1693,7 +1820,8 @@ namespace bpkg
                                         ed,
                                         {pk},
                                         replaced_vers,
-                                        postponed_cfgs);
+                                        postponed_cfgs,
+                                        unsatisfied_depts);
 
             // Only add this dependent/dependency to the newly created cluster
             // if this dependency doesn't belong to any cluster yet, which may
@@ -1729,7 +1857,8 @@ namespace bpkg
                                           ed,
                                           replaced_vers,
                                           postponed_recs,
-                                          postponed_cfgs);
+                                          postponed_cfgs,
+                                          unsatisfied_depts);
           }
 
           // Postpone the recursive collection of a dependency if the existing
@@ -2096,7 +2225,8 @@ namespace bpkg
         //
         optional<prebuilds> builds;
 
-        // If some dependency of the alternative cannot be resolved because
+        // If true is passed as the check_constraints argument to precollect()
+        // and some dependency of the alternative cannot be resolved because
         // there is no version available which can satisfy all the being built
         // dependents, then this member contains all the dependency builds
         // (which otherwise would be contained in the builds member).
@@ -2150,6 +2280,7 @@ namespace bpkg
         (const dependency_alternative& da,
          bool buildtime,
          const package_prerequisites* prereqs,
+         bool check_constraints,
          diag_record* dr = nullptr,
          bool dry_run = false) -> precollect_result
         {
@@ -2267,9 +2398,10 @@ namespace bpkg
                     *dr << info << c.dependent << c.db << " depends on (" << dn
                                 << ' ' << c.value << ")";
 
+                    if (const build_package* d = dependent_build (c))
                     {
                       set<package_key> printed;
-                      print_constraints (*dr, c, indent, printed);
+                      print_constraints (*dr, *d, indent, printed);
                     }
 
                     *dr << info << "specify " << dn << " version to satisfy "
@@ -2923,93 +3055,100 @@ namespace bpkg
                                    ru});
           }
 
-          // Now, as we have pre-collected the dependency builds, go through
-          // them and check that for those dependencies which are already
-          // being built we will be able to choose one of them (either
-          // existing or new) which satisfies all the dependents. If that's
-          // not the case, then issue the diagnostics, if requested, and
-          // return the unsatisfactory dependency builds.
+          // Now, as we have pre-collected the dependency builds, if
+          // requested, go through them and check that for those dependencies
+          // which are already being built we will be able to choose one of
+          // them (either existing or new) which satisfies all the dependents.
+          // If that's not the case, then issue the diagnostics, if requested,
+          // and return the unsatisfactory dependency builds.
           //
           // 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.
           //
-          for (const prebuild& b: r)
+          if (check_constraints)
           {
-            const shared_ptr<available_package>& dap (b.available);
-
-            assert (dap != nullptr); // Otherwise we would have failed earlier.
+            for (const prebuild& b: r)
+            {
+              const shared_ptr<available_package>& dap (b.available);
 
-            const dependency& d (b.dependency);
+              // Otherwise we would have failed earlier.
+              //
+              assert (dap != nullptr);
 
-            auto i (map_.find (b.db, d.name));
+              const dependency& d (b.dependency);
 
-            if (i != map_.end () && d.constraint)
-            {
-              const build_package& bp (i->second.package);
+              auto i (map_.find (b.db, d.name));
 
-              if (bp.action && *bp.action == build_package::build)
+              if (i != map_.end () && d.constraint)
               {
-                const version& v1 (b.system
-                                   ? *dap->system_version (b.db)
-                                   : dap->version);
-
-                const version& v2 (bp.available_version ());
+                const build_package& bp (i->second.package);
 
-                if (v1 != v2)
+                if (bp.action && *bp.action == build_package::build)
                 {
-                  using constraint_type = build_package::constraint_type;
+                  const version& v1 (b.system
+                                     ? *dap->system_version (b.db)
+                                     : dap->version);
 
-                  constraint_type c1 {pdb, nm.string (), *d.constraint};
+                  const version& v2 (bp.available_version ());
 
-                  if (!satisfies (v2, c1.value))
+                  if (v1 != v2)
                   {
-                    for (const constraint_type& c2: bp.constraints)
+                    using constraint_type = build_package::constraint_type;
+
+                    constraint_type c1 {pdb, nm.string (), *d.constraint};
+
+                    if (!satisfies (v2, c1.value))
                     {
-                      if (!satisfies (v1, c2.value))
+                      for (const constraint_type& c2: bp.constraints)
                       {
-                        // We should end up throwing reevaluation_deviated
-                        // exception before the diagnostics run in the
-                        // pre-reevaluation mode.
-                        //
-                        assert (!pre_reeval || dr == nullptr);
-
-                        if (dr != nullptr)
+                        if (!satisfies (v1, c2.value))
                         {
-                          const package_name& n (d.name);
-
-                          //             "  info: ..."
-                          string indent ("          ");
-
-                          *dr << error << "unable to satisfy constraints on "
-                              << "package " << n <<
-                            info << c2.dependent << c2.db << " depends on ("
-                                 << n << ' ' << c2.value << ")";
+                          // We should end up throwing reevaluation_deviated
+                          // exception before the diagnostics run in the
+                          // pre-reevaluation mode.
+                          //
+                          assert (!pre_reeval || dr == nullptr);
 
+                          if (dr != nullptr)
                           {
-                            set<package_key> printed;
-                            print_constraints (*dr, c2, indent, printed);
+                            const package_name& n (d.name);
+
+                            //             "  info: ..."
+                            string indent ("          ");
+
+                            *dr << error << "unable to satisfy constraints on "
+                                << "package " << n <<
+                              info << c2.dependent << c2.db << " depends on ("
+                                   << n << ' ' << c2.value << ")";
+
+                            if (const build_package* d = dependent_build (c2))
+                            {
+                              set<package_key> printed;
+                              print_constraints (*dr, *d, indent, printed);
+                            }
+
+                            *dr << info << c1.dependent << c1.db
+                                << " depends on (" << n << ' '
+                                << c1.value << ")";
+
+                            if (const build_package* d = dependent_build (c1))
+                            {
+                              set<package_key> printed;
+                              print_constraints (*dr, *d, indent, printed);
+                            }
+
+                            *dr << info << "available "
+                                << bp.available_name_version () <<
+                              info << "available "
+                                   << package_string (n, v1, b.system) <<
+                              info << "explicitly specify " << n
+                                   << " version to manually satisfy both "
+                                   << "constraints";
                           }
 
-                          *dr << info << c1.dependent << c1.db
-                                      << " depends on (" << n << ' '
-                                      << c1.value << ")";
-
-                          {
-                            set<package_key> printed;
-                            print_constraints (*dr, c1, indent, printed);
-                          }
-
-                          *dr << info << "available "
-                                      << bp.available_name_version () <<
-                                 info << "available "
-                                      << package_string (n, v1, b.system) <<
-                                 info << "explicitly specify " << n
-                                      << " version to manually satisfy both "
-                                      << "constraints";
+                          return precollect_result (reused, move (r));
                         }
-
-                        return precollect_result (reused, move (r));
                       }
                     }
                   }
@@ -3043,6 +3182,7 @@ namespace bpkg
                       &postponed_deps,
                       &postponed_cfgs,
                       &unacceptable_alts,
+                      &unsatisfied_depts,
                       &di,
                       reeval,
                       &reeval_pos,
@@ -3056,7 +3196,8 @@ namespace bpkg
         (const dependency_alternative& da,
          size_t dai,
          prebuilds&& bs,
-         const package_prerequisites* prereqs)
+         const package_prerequisites* prereqs,
+         bool check_constraints)
         {
           // Dependency alternative position.
           //
@@ -3229,6 +3370,7 @@ namespace bpkg
                              move (bpk),
                              replaced_vers,
                              postponed_cfgs,
+                             unsatisfied_depts,
                              nullptr /* dep_chain */,
                              nullptr /* fdb */,
                              nullptr /* apc */,
@@ -3442,7 +3584,8 @@ namespace bpkg
                                            postponed_edeps,
                                            postponed_deps,
                                            postponed_cfgs,
-                                           unacceptable_alts);
+                                           unacceptable_alts,
+                                           unsatisfied_depts);
           }
 
           // If this dependent has any dependencies with configurations
@@ -3499,6 +3642,8 @@ namespace bpkg
               // Note that this is parallel to the alternative selection
               // logic.
               //
+              bool unsatisfactory (false);
+
               for (++i; i != edas.size (); ++i)
               {
                 if (unacceptable ())
@@ -3509,6 +3654,7 @@ namespace bpkg
                 precollect_result r (precollect (a,
                                                  das.buildtime,
                                                  prereqs,
+                                                 check_constraints,
                                                  nullptr /* diag_record */,
                                                  true /* dry_run */));
 
@@ -3517,6 +3663,9 @@ namespace bpkg
                   has_alt = true;
                   break;
                 }
+
+                if (r.unsatisfactory)
+                  unsatisfactory = true;
               }
 
               // If there are none and we are in the "recreate dependency
@@ -3525,6 +3674,8 @@ namespace bpkg
               //
               if (!has_alt && prereqs != nullptr)
               {
+                unsatisfactory = false;
+
                 for (i = 0; i != edas.size (); ++i)
                 {
                   if (unacceptable ())
@@ -3537,6 +3688,7 @@ namespace bpkg
                     precollect_result r (precollect (a,
                                                      das.buildtime,
                                                      nullptr /* prereqs */,
+                                                     check_constraints,
                                                      nullptr /* diag_record */,
                                                      true /* dry_run */));
 
@@ -3545,6 +3697,40 @@ namespace bpkg
                       has_alt = true;
                       break;
                     }
+
+                    if (r.unsatisfactory)
+                      unsatisfactory = true;
+                  }
+                }
+              }
+
+              // If there are none and we are in the "check constraints" mode,
+              // then repeat the search with this mode off.
+              //
+              if (!has_alt && check_constraints && unsatisfactory)
+              {
+                for (i = 0; i != edas.size (); ++i)
+                {
+                  if (unacceptable ())
+                    continue;
+
+                  const dependency_alternative& a (edas[i].first);
+
+                  if (&a != &da) // Skip the current dependency alternative.
+                  {
+                    precollect_result r (
+                      precollect (a,
+                                  das.buildtime,
+                                  nullptr /* prereqs */,
+                                  false /* check_constraints */,
+                                  nullptr /* diag_record */,
+                                  true /* dry_run */));
+
+                    if (r.builds && r.reused)
+                    {
+                      has_alt = true;
+                      break;
+                    }
                   }
                 }
               }
@@ -4014,7 +4200,8 @@ namespace bpkg
                                                postponed_edeps,
                                                postponed_deps,
                                                postponed_cfgs,
-                                               unacceptable_alts);
+                                               unacceptable_alts,
+                                               unsatisfied_depts);
                 }
                 else
                   l5 ([&]{trace << "dependency "
@@ -4183,6 +4370,15 @@ namespace bpkg
       //
       assert ((!reeval && !pre_reeval) || prereqs != nullptr);
 
+      // Initially try to select an alternative checking that all the
+      // constraints imposed by the being built dependents of the dependencies
+      // in the alternative are satisfied. Failed that, re-try but this time
+      // disable this check so that the unsatisfactory dependency can be
+      // properly handled by collect_build() (which can fail, postpone
+      // failure, etc; see its implementation for details).
+      //
+      bool check_constraints (true);
+
       for (bool unacceptable (false);;)
       {
         // The index and pre-collection result of the first satisfactory
@@ -4214,6 +4410,13 @@ namespace bpkg
         //
         bool reused_only (false);
 
+        // If true, then some alternatives with unsatisfactory dependencies
+        // are detected and, unless the alternative is selected or the
+        // selection is postponed, we should re-try with the constraints check
+        // disabled (see above for details).
+        //
+        bool unsatisfactory (false);
+
         for (size_t i (0); i != edas.size (); ++i)
         {
           // Skip the unacceptable alternatives.
@@ -4240,7 +4443,8 @@ namespace bpkg
 
           const dependency_alternative& da (edas[i].first);
 
-          precollect_result pcr (precollect (da, das.buildtime, prereqs));
+          precollect_result pcr (
+            precollect (da, das.buildtime, prereqs, check_constraints));
 
           // If we didn't come up with satisfactory dependency builds, then
           // skip this alternative and try the next one, unless the collecting
@@ -4270,8 +4474,13 @@ namespace bpkg
             // If this alternative is reused but is not satisfactory, then
             // switch to the reused-only mode.
             //
-            if (pcr.reused && pcr.unsatisfactory)
-              reused_only = true;
+            if (pcr.unsatisfactory)
+            {
+              unsatisfactory = true;
+
+              if (pcr.reused)
+                reused_only = true;
+            }
 
             continue;
           }
@@ -4299,7 +4508,8 @@ namespace bpkg
           auto try_select = [postponed_alts, &max_alt_index,
                              &edas, &pkg,
                              di,
-                             prereqs,
+                             &prereqs,
+                             &check_constraints,
                              pre_reeval,
                              reeval,
                              &trace,
@@ -4356,7 +4566,11 @@ namespace bpkg
                   throw reevaluation_deviated ();
                 }
               }
-              else if (!collect (da, dai, move (*pcr.builds), prereqs))
+              else if (!collect (da,
+                                 dai,
+                                 move (*pcr.builds),
+                                 prereqs,
+                                 check_constraints))
               {
                 postpone (nullptr); // Already inserted into postponed_cfgs.
                 return true;
@@ -4439,7 +4653,11 @@ namespace bpkg
                   throw reevaluation_deviated ();
               }
             }
-            else if (!collect (da, dai, move (*pcr.builds), prereqs))
+            else if (!collect (da,
+                               dai,
+                               move (*pcr.builds),
+                               prereqs,
+                               check_constraints))
             {
               postpone (nullptr); // Already inserted into postponed_cfgs.
               break;
@@ -4482,6 +4700,15 @@ namespace bpkg
           continue;
         }
 
+        // Retry with the constraints check disabled, if an alternative with
+        // the unsatisfactory dependencies is detected.
+        //
+        if (check_constraints && unsatisfactory)
+        {
+          check_constraints = false;
+          continue;
+        }
+
         // Otherwise we would have thrown/failed earlier.
         //
         assert (!pre_reeval && !reeval);
@@ -4498,7 +4725,13 @@ namespace bpkg
         {
           diag_record dr;
           for (const auto& da: edas)
-            precollect (da.first, das.buildtime, nullptr /* prereqs */, &dr);
+          {
+            precollect (da.first,
+                        das.buildtime,
+                        nullptr /* prereqs */,
+                        false /* check_constraints */,
+                        &dr);
+          }
 
           assert (!dr.empty ());
 
@@ -4530,7 +4763,6 @@ namespace bpkg
         }
 
         diag_record dr (fail);
-
         dr << "unable to select dependency alternative for package "
            << pkg.available_name_version_db () <<
           info << "explicitly specify dependency packages to manually "
@@ -4538,8 +4770,10 @@ namespace bpkg
 
         for (const auto& da: edas)
         {
-          precollect_result r (
-            precollect (da.first, das.buildtime, nullptr /* prereqs */));
+          precollect_result r (precollect (da.first,
+                                           das.buildtime,
+                                           nullptr /* prereqs */,
+                                           false /* check_constraints */));
 
           if (r.builds)
           {
@@ -4568,8 +4802,10 @@ namespace bpkg
 
           for (const auto& da: edas)
           {
-            precollect_result r (
-              precollect (da.first, das.buildtime, nullptr /* prereqs */));
+            precollect_result r (precollect (da.first,
+                                             das.buildtime,
+                                             nullptr /* prereqs */,
+                                             true /* check_constraints */));
 
             if (r.reused && r.unsatisfactory)
             {
@@ -4582,7 +4818,11 @@ namespace bpkg
 
               // Print the reason.
               //
-              precollect (da.first, das.buildtime, nullptr /* prereqs */, &dr);
+              precollect (da.first,
+                          das.buildtime,
+                          nullptr /* prereqs */,
+                          true /* check_constraints */,
+                          &dr);
             }
           }
         }
@@ -4673,7 +4913,8 @@ namespace bpkg
                                postponed_existing_dependencies& postponed_edeps,
                                postponed_dependencies& postponed_deps,
                                postponed_configurations& postponed_cfgs,
-                               unacceptable_alternatives& unacceptable_alts)
+                               unacceptable_alternatives& unacceptable_alts,
+                               unsatisfied_dependents& unsatisfied_depts)
   {
     auto mi (map_.find (db, name));
     assert (mi != map_.end ());
@@ -4694,7 +4935,8 @@ namespace bpkg
                                  postponed_edeps,
                                  postponed_deps,
                                  postponed_cfgs,
-                                 unacceptable_alts);
+                                 unacceptable_alts,
+                                 unsatisfied_depts);
   }
 
   void build_packages::
@@ -4709,6 +4951,7 @@ namespace bpkg
     postponed_dependencies& postponed_deps,
     postponed_configurations& postponed_cfgs,
     unacceptable_alternatives& unacceptable_alts,
+    unsatisfied_dependents& unsatisfied_depts,
     const function<find_database_function>& fdb,
     const function<add_priv_cfg_function>& apc)
   {
@@ -4784,6 +5027,7 @@ namespace bpkg
                      move (p),
                      replaced_vers,
                      postponed_cfgs,
+                     unsatisfied_depts,
                      &dep_chain,
                      fdb,
                      apc,
@@ -4808,7 +5052,7 @@ namespace bpkg
     package_key pk (db, sp->name);
 
     // If there is an entry for building specific version of the package (the
-    // available member is not NULL), then it wasn't created to prevent out
+    // available member is not NULL), then it wasn't created to prevent our
     // drop (see replaced_versions for details). This rather mean that the
     // replacement version is not being built anymore due to the plan
     // refinement. Thus, just erase the entry in this case and continue.
@@ -4881,11 +5125,18 @@ namespace bpkg
         // common.
         //
         // An update: it turned out that just absence of dependencies is not
-        // the only condition that causes a package to be dropped in place. It
-        // must also not participate in any configuration negotiation on the
-        // dependency side (otherwise it could have been added to a cluster as
-        // a dependency). This feels quite hairy at the moment, so we won't be
-        // dropping in place for now.
+        // the only condition that causes a package to be dropped in place.
+        // The following conditions must also be met:
+        //
+        // - The package must also not participate in any configuration
+        //   negotiation on the dependency side (otherwise it could have been
+        //   added to a cluster as a dependency).
+        //
+        // - The package must not be added to unsatisfied_depts on the
+        //   dependency side.
+        //
+        // This feels quite hairy at the moment, so we won't be dropping in
+        // place for now.
         //
 #if 0
         if (!has_dependencies (options, bp.available->dependencies))
@@ -4978,6 +5229,7 @@ namespace bpkg
                            postponed_configurations& postponed_cfgs,
                            strings& postponed_cfgs_history,
                            unacceptable_alternatives& unacceptable_alts,
+                           unsatisfied_dependents& unsatisfied_depts,
                            const function<find_database_function>& fdb,
                            const repointed_dependents& rpt_depts,
                            const function<add_priv_cfg_function>& apc,
@@ -5210,7 +5462,8 @@ namespace bpkg
                     collect_existing_dependent_dependency (o,
                                                            ed,
                                                            replaced_vers,
-                                                           postponed_cfgs);
+                                                           postponed_cfgs,
+                                                           unsatisfied_depts);
 
                   i = dependents.emplace (
                     move (pk), existing_dependent_ex (move (ed))).first;
@@ -5240,7 +5493,8 @@ namespace bpkg
                                               ed,
                                               replaced_vers,
                                               postponed_recs,
-                                              postponed_cfgs);
+                                              postponed_cfgs,
+                                              unsatisfied_depts);
               }
             }
           }
@@ -5274,7 +5528,8 @@ namespace bpkg
                                           ed,
                                           move (ed.dependencies),
                                           replaced_vers,
-                                          postponed_cfgs);
+                                          postponed_cfgs,
+                                          unsatisfied_depts);
 
               build_package* b (entered_build (d.first));
               assert (b != nullptr);
@@ -5301,6 +5556,7 @@ namespace bpkg
                                              postponed_deps,
                                              postponed_cfgs,
                                              unacceptable_alts,
+                                             unsatisfied_depts,
                                              ed.dependency_position);
               }
               catch (const merge_configuration_cycle& e)
@@ -5549,7 +5805,8 @@ namespace bpkg
                                        postponed_edeps,
                                        postponed_deps,
                                        postponed_cfgs,
-                                       unacceptable_alts);
+                                       unacceptable_alts,
+                                       unsatisfied_depts);
         }
         else
           l5 ([&]{trace << "dependency " << b->available_name_version_db ()
@@ -5697,7 +5954,8 @@ namespace bpkg
                                      postponed_edeps,
                                      postponed_deps,
                                      postponed_cfgs,
-                                     unacceptable_alts);
+                                     unacceptable_alts,
+                                     unsatisfied_depts);
       }
 
       // Negotiated (so can only be rolled back).
@@ -5794,7 +6052,8 @@ namespace bpkg
                                        postponed_edeps,
                                        postponed_deps,
                                        postponed_cfgs,
-                                       unacceptable_alts);
+                                       unacceptable_alts,
+                                       unsatisfied_depts);
 
           // Note that the existing dependent collection can be postponed
           // due to it's own existing dependents.
@@ -5849,7 +6108,8 @@ namespace bpkg
                                      postponed_edeps,
                                      postponed_deps,
                                      postponed_cfgs,
-                                     unacceptable_alts);
+                                     unacceptable_alts,
+                                     unsatisfied_depts);
       }
 
       // Save the potential new dependency alternative-related postponements.
@@ -5917,6 +6177,7 @@ namespace bpkg
                                      postponed_cfgs,
                                      postponed_cfgs_history,
                                      unacceptable_alts,
+                                     unsatisfied_depts,
                                      fdb,
                                      rpt_depts,
                                      apc,
@@ -6118,7 +6379,8 @@ namespace bpkg
                                             ed,
                                             replaced_vers,
                                             postponed_recs,
-                                            postponed_cfgs);
+                                            postponed_cfgs,
+                                            unsatisfied_depts);
             }
           }
         }
@@ -6211,7 +6473,8 @@ namespace bpkg
                                          postponed_edeps,
                                          postponed_deps,
                                          postponed_cfgs,
-                                         unacceptable_alts);
+                                         unacceptable_alts,
+                                         unsatisfied_depts);
 
             prog = (pas.find (p) == pas.end () ||
                     ndep != p->dependencies->size ());
@@ -6292,7 +6555,8 @@ namespace bpkg
                                           ed,
                                           replaced_vers,
                                           postponed_recs,
-                                          postponed_cfgs);
+                                          postponed_cfgs,
+                                          unsatisfied_depts);
             prog = true;
             break;
           }
@@ -6466,7 +6730,8 @@ namespace bpkg
                                    postponed_edeps,
                                    postponed_deps,
                                    postponed_cfgs,
-                                   unacceptable_alts);
+                                   unacceptable_alts,
+                                   unsatisfied_depts);
 
       assert (false); // Can't be here.
     }
@@ -6489,7 +6754,8 @@ namespace bpkg
                                    postponed_edeps,
                                    postponed_deps,
                                    postponed_cfgs,
-                                   unacceptable_alts);
+                                   unacceptable_alts,
+                                   unsatisfied_depts);
 
       assert (false); // Can't be here.
     }
@@ -6647,39 +6913,7 @@ namespace bpkg
           // up/downgraded, etc; see unsatisfied_dependents for details).
           //
           if (!satisfies (av, c))
-          {
-            package_key dk (ddb, dn);
-            unsatisfied_dependent* ud (unsatisfied_depts.find_dependent (dk));
-
-            if (ud != nullptr)
-            {
-              vector<pair<build_package*, version_constraint>>& deps (
-                ud->dependencies);
-
-              auto i (find_if (deps.begin (), deps.end (),
-                               [&p] (const auto& v) {return v.first == &p;}));
-
-              // Skip the dependency if it is already in the list.
-              //
-              // Note that we can be adding the same unsatisfactory dependency
-              // multiple times via different dependency paths. For example:
-              //
-              // 1. libboost-core    -> libboost-mpl -> libboost-regex
-              // 2. libboost-utility -> libboost-mpl -> libboost-regex
-              //
-              // In this case, however, the constraint should be the same.
-              //
-              assert (i == deps.end () || i->second == c);
-
-              if (i == deps.end ())
-                deps.push_back (make_pair (&p, c));
-            }
-            else
-            {
-              unsatisfied_depts.push_back (
-                unsatisfied_dependent {move (dk), {make_pair (&p, c)}});
-            }
-          }
+            unsatisfied_depts.add (package_key (ddb, dn), &p, c);
         }
 
         auto adjustment = [&dn, &ddb, &n, &pdb] () -> build_package
@@ -6834,24 +7068,8 @@ namespace bpkg
 
         for (const constraint_type& c: cs)
         {
-          if (c.dependent != "command line")
+          if (const build_package* d = dependent_build (c))
           {
-            const build_package* d;
-
-            try
-            {
-              d = entered_build (package_key (c.db,
-                                              package_name (c.dependent)));
-
-              assert (d != nullptr); // Expected to be collected.
-            }
-            catch (const invalid_argument&)
-            {
-              // Must be a package name, unless it is 'command line'.
-              //
-              assert (false);
-            }
-
             dr << '\n' << indent << c.dependent << '/';
 
             // The dependent can only be collected as a build or adjustment.
@@ -6893,28 +7111,6 @@ namespace bpkg
   }
 
   void build_packages::
-  print_constraints (diag_record& dr,
-                     const build_package::constraint_type& c,
-                     string& indent,
-                     set<package_key>& printed) const
-  {
-    const string& d (c.dependent);
-
-    if (d != "command line")
-    try
-    {
-      print_constraints (dr,
-                         package_key (c.db, package_name (d)),
-                         indent,
-                         printed);
-    }
-    catch (const invalid_argument&)
-    {
-      assert (false); // Must be a package name, unless it is 'command line'.
-    }
-  }
-
-  void build_packages::
   verify_ordering () const
   {
     for (const auto& b: map_)
@@ -7142,6 +7338,7 @@ namespace bpkg
           postponed_dependencies postponed_deps;
           postponed_configurations postponed_cfgs;
           unacceptable_alternatives unacceptable_alts;
+          unsatisfied_dependents unsatisfied_depts;
           replaced_versions replaced_vers;
 
           optional<pre_reevaluate_result> pr (
@@ -7160,6 +7357,7 @@ namespace bpkg
                                          postponed_deps,
                                          postponed_cfgs,
                                          unacceptable_alts,
+                                         unsatisfied_depts,
                                          pair<size_t, size_t> (0, 0),
                                          orig_dep));
 
@@ -7172,6 +7370,7 @@ namespace bpkg
                   postponed_deps.empty ()    &&
                   postponed_cfgs.empty ()    &&
                   unacceptable_alts.empty () &&
+                  unsatisfied_depts.empty () &&
                   replaced_vers.empty ());
 
           if (pr && (!pr->reevaluation_optional || !exclude_optional))
@@ -7216,7 +7415,8 @@ namespace bpkg
     const pkg_build_options& o,
     const existing_dependent& ed,
     replaced_versions& replaced_vers,
-    postponed_configurations& postponed_cfgs)
+    postponed_configurations& postponed_cfgs,
+    unsatisfied_dependents& unsatisfied_depts)
   {
     assert (ed.dependency); // Shouldn't be called for deviated dependents.
 
@@ -7273,7 +7473,8 @@ namespace bpkg
 
     // Note: not recursive.
     //
-    collect_build (o, move (p), replaced_vers, postponed_cfgs);
+    collect_build (
+      o, move (p), replaced_vers, postponed_cfgs, unsatisfied_depts);
 
     return entered_build (dep);
   }
@@ -7283,7 +7484,8 @@ namespace bpkg
                               const existing_dependent& ed,
                               postponed_configuration::packages&& ds,
                               replaced_versions& replaced_vers,
-                              postponed_configurations& postponed_cfgs)
+                              postponed_configurations& postponed_cfgs,
+                              unsatisfied_dependents& unsatisfied_depts)
   {
     assert (ed.dependency); // May not be a deviated existing dependent.
 
@@ -7320,7 +7522,8 @@ namespace bpkg
 
     // Note: not recursive.
     //
-    collect_build (o, move (p), replaced_vers, postponed_cfgs);
+    collect_build (
+      o, move (p), replaced_vers, postponed_cfgs, unsatisfied_depts);
   }
 
   void build_packages::
@@ -7328,7 +7531,8 @@ namespace bpkg
                                 const existing_dependent& ed,
                                 replaced_versions& replaced_vers,
                                 postponed_packages& postponed_recs,
-                                postponed_configurations& postponed_cfgs)
+                                postponed_configurations& postponed_cfgs,
+                                unsatisfied_dependents& unsatisfied_depts)
   {
     pair<shared_ptr<available_package>,
          lazy_shared_ptr<repository_fragment>> rp (
@@ -7368,7 +7572,8 @@ namespace bpkg
 
     // Note: not recursive.
     //
-    collect_build (o, move (p), replaced_vers, postponed_cfgs);
+    collect_build (
+      o, move (p), replaced_vers, postponed_cfgs, unsatisfied_depts);
 
     postponed_recs.insert (entered_build (ed.db, ed.selected->name));
   }
diff --git a/bpkg/pkg-build-collect.hxx b/bpkg/pkg-build-collect.hxx
index d1acc33..181a86e 100644
--- a/bpkg/pkg-build-collect.hxx
+++ b/bpkg/pkg-build-collect.hxx
@@ -716,6 +716,13 @@ namespace bpkg
   // dropped, dependencies will be up/downgraded to a different versions,
   // etc).
   //
+  // Also note that we may discover that a being up/downgraded dependency
+  // doesn't satisfy an existing dependent which we re-collect recursively for
+  // some reason (configuration variables are specified, etc). In this case we
+  // may also postpone the failure in the hope that the problem will resolve
+  // naturally as it is described above (see collect_build() implementation
+  // for details).
+  //
   // Specifically, we cache such unsatisfied constraints, pretend that the
   // dependents don't impose them and proceed with the remaining
   // collecting/ordering, simulating the plan execution, and evaluating the
@@ -728,7 +735,7 @@ namespace bpkg
   struct unsatisfied_dependent
   {
     package_key dependent;
-    vector<pair<build_package*, version_constraint>> dependencies;
+    vector<pair<const build_package*, version_constraint>> dependencies;
   };
 
   struct build_packages;
@@ -736,6 +743,13 @@ namespace bpkg
   class unsatisfied_dependents: public vector<unsatisfied_dependent>
   {
   public:
+    // Add a dependent together with the unsatisfied dependency constraint.
+    //
+    void
+    add (const package_key& dependent,
+         const build_package* dependency,
+         const version_constraint&);
+
     // Try to find the dependent entry and return NULL if not found.
     //
     unsatisfied_dependent*
@@ -1130,6 +1144,14 @@ namespace bpkg
       return entered_build (p.db, p.name);
     }
 
+    // Return NULL if the dependent in the constraint is not a package name
+    // (command line, etc; see build_package::constraint_type for details).
+    // Otherwise, return the dependent package build which is expected to be
+    // collected.
+    //
+    const build_package*
+    dependent_build (const build_package::constraint_type&) const;
+
     // Collect the package being built. Return its pointer if this package
     // version was, in fact, added to the map and NULL if it was already there
     // and the existing version was preferred or if the package build has been
@@ -1176,6 +1198,7 @@ namespace bpkg
                    build_package,
                    replaced_versions&,
                    postponed_configurations&,
+                   unsatisfied_dependents&,
                    build_package_refs* dep_chain = nullptr,
                    const function<find_database_function>& = nullptr,
                    const function<add_priv_cfg_function>& = nullptr,
@@ -1389,6 +1412,7 @@ namespace bpkg
                                  postponed_dependencies&,
                                  postponed_configurations&,
                                  unacceptable_alternatives&,
+                                 unsatisfied_dependents&,
                                  optional<pair<size_t, size_t>> reeval_pos = nullopt,
                                  const optional<package_key>& orig_dep = nullopt);
 
@@ -1407,7 +1431,8 @@ namespace bpkg
                                  postponed_existing_dependencies&,
                                  postponed_dependencies&,
                                  postponed_configurations&,
-                                 unacceptable_alternatives&);
+                                 unacceptable_alternatives&,
+                                 unsatisfied_dependents&);
 
     // Collect the repointed dependents and their replaced prerequisites,
     // recursively.
@@ -1428,6 +1453,7 @@ namespace bpkg
                                   postponed_dependencies&,
                                   postponed_configurations&,
                                   unacceptable_alternatives&,
+                                  unsatisfied_dependents&,
                                   const function<find_database_function>&,
                                   const function<add_priv_cfg_function>&);
 
@@ -1459,6 +1485,7 @@ namespace bpkg
                              postponed_configurations&,
                              strings& postponed_cfgs_history,
                              unacceptable_alternatives&,
+                             unsatisfied_dependents&,
                              const function<find_database_function>&,
                              const repointed_dependents&,
                              const function<add_priv_cfg_function>&,
@@ -1529,16 +1556,6 @@ namespace bpkg
                        string& indent,
                        std::set<package_key>& printed) const;
 
-    // Wraps the above function for the case when the package is a dependent
-    // from the dependency's constraints list. Noop if the dependent is not a
-    // package name (command line, etc; see constraint_type for details).
-    //
-    void
-    print_constraints (diag_record&,
-                       const build_package::constraint_type&,
-                       string& indent,
-                       std::set<package_key>& printed) const;
-
     // Verify that builds ordering is consistent across all the data
     // structures and the ordering expectations are fulfilled (real build
     // actions are all ordered, etc).
@@ -1610,7 +1627,8 @@ namespace bpkg
       const pkg_build_options&,
       const existing_dependent&,
       replaced_versions&,
-      postponed_configurations&);
+      postponed_configurations&,
+      unsatisfied_dependents&);
 
     // Non-recursively collect an existing non-deviated dependent previously
     // returned by the query_existing_dependents() function call for the
@@ -1622,7 +1640,8 @@ namespace bpkg
       const existing_dependent&,
       postponed_configuration::packages&& dependencies,
       replaced_versions&,
-      postponed_configurations&);
+      postponed_configurations&,
+      unsatisfied_dependents&);
 
     // Non-recursively collect an existing dependent previously returned by
     // the query_existing_dependents() function call with the
@@ -1639,7 +1658,8 @@ namespace bpkg
                                   const existing_dependent&,
                                   replaced_versions&,
                                   postponed_packages& postponed_recs,
-                                  postponed_configurations&);
+                                  postponed_configurations&,
+                                  unsatisfied_dependents&);
 
     struct package_ref
     {
diff --git a/bpkg/pkg-build.cxx b/bpkg/pkg-build.cxx
index ad1a695..9cf466c 100644
--- a/bpkg/pkg-build.cxx
+++ b/bpkg/pkg-build.cxx
@@ -4243,7 +4243,8 @@ namespace bpkg
             // specify packages on the command line does not matter).
             //
             for (const build_package& p: hold_pkgs)
-              pkgs.collect_build (o, p, replaced_vers, postponed_cfgs);
+              pkgs.collect_build (
+                o, p, replaced_vers, postponed_cfgs, unsatisfied_depts);
 
             // Collect all the prerequisites of the user selection.
             //
@@ -4294,7 +4295,8 @@ namespace bpkg
                     postponed_edeps,
                     postponed_deps,
                     postponed_cfgs,
-                    unacceptable_alts);
+                    unacceptable_alts,
+                    unsatisfied_depts);
                 }
               }
             }
@@ -4340,6 +4342,7 @@ namespace bpkg
                                                postponed_deps,
                                                postponed_cfgs,
                                                unacceptable_alts,
+                                               unsatisfied_depts,
                                                find_prereq_database,
                                                add_priv_cfg);
           }
@@ -4419,7 +4422,8 @@ namespace bpkg
 
                 // Note: not recursive.
                 //
-                pkgs.collect_build (o, move (p), replaced_vers, postponed_cfgs);
+                pkgs.collect_build (
+                  o, move (p), replaced_vers, postponed_cfgs, unsatisfied_depts);
 
                 l5 ([&]{trace << "dep-postpone user-specified dependency "
                               << pk;});
@@ -4436,7 +4440,8 @@ namespace bpkg
                   pkgs.collect_build (o,
                                       move (p),
                                       replaced_vers,
-                                      postponed_cfgs);
+                                      postponed_cfgs,
+                                      unsatisfied_depts);
 
                   l5 ([&]{trace << "dep-postpone user-specified dependency "
                                 << pk << " since already in cluster "
@@ -4452,6 +4457,7 @@ namespace bpkg
                                       move (p),
                                       replaced_vers,
                                       postponed_cfgs,
+                                      unsatisfied_depts,
                                       &dep_chain,
                                       find_prereq_database,
                                       add_priv_cfg,
@@ -4492,6 +4498,7 @@ namespace bpkg
                                           postponed_cfgs,
                                           postponed_cfgs_history,
                                           unacceptable_alts,
+                                          unsatisfied_depts,
                                           find_prereq_database,
                                           rpt_depts,
                                           add_priv_cfg);
@@ -6484,7 +6491,8 @@ namespace bpkg
                                                nullptr /* prev_prerequisites */,
                                                simulate,
                                                fdb,
-                                               configured_state);
+                                               configured_state,
+                                               unconstrain_deps ());
           }
           else
           {
diff --git a/tests/common/dependency-alternatives/t8a/bax-0.1.0.tar.gz b/tests/common/dependency-alternatives/t8a/bax-0.1.0.tar.gz
new file mode 100644
index 0000000..85a24ea
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/bax-0.1.0.tar.gz
diff --git a/tests/common/dependency-alternatives/t8a/bax-1.0.0.tar.gz b/tests/common/dependency-alternatives/t8a/bax-1.0.0.tar.gz
new file mode 100644
index 0000000..204c335
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/bax-1.0.0.tar.gz
diff --git a/tests/common/dependency-alternatives/t8a/bix-0.1.0.tar.gz b/tests/common/dependency-alternatives/t8a/bix-0.1.0.tar.gz
new file mode 100644
index 0000000..d0cc912
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/bix-0.1.0.tar.gz
diff --git a/tests/common/dependency-alternatives/t8a/bix-1.0.0.tar.gz b/tests/common/dependency-alternatives/t8a/bix-1.0.0.tar.gz
new file mode 100644
index 0000000..f1bab8d
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/bix-1.0.0.tar.gz
diff --git a/tests/common/dependency-alternatives/t8a/bux-1.0.0.tar.gz b/tests/common/dependency-alternatives/t8a/bux-1.0.0.tar.gz
new file mode 100644
index 0000000..9395a59
--- /dev/null
+++ b/tests/common/dependency-alternatives/t8a/bux-1.0.0.tar.gz
diff --git a/tests/pkg-build.testscript b/tests/pkg-build.testscript
index 600f0a8..010f703 100644
--- a/tests/pkg-build.testscript
+++ b/tests/pkg-build.testscript
@@ -150,9 +150,14 @@
 # |   |-- libfoo-2.0.0.tar.gz
 # |   |-- bar-1.0.0.tar.gz      -> libbar
 # |   |-- baz-1.0.0.tar.gz      -> libbaz
+# |   |-- bax-0.1.0.tar.gz      -> libbox config.bax.backend=libbox
+# |   |-- bax-1.0.0.tar.gz      -> libbox >= 0.1.1 config.bax.backend=libbox
+# |   |-- bix-0.1.0.tar.gz
+# |   |-- bix-1.0.0.tar.gz      -> bax == 0.1.0
 # |   |-- box-1.0.0.tar.gz      -> libbiz ^1.0.0 config.box.backend=libbiz |
 # |   |                            libbox >= 0.1.1 config.box.backend=libbox,
 # |   |                            libbaz
+# |   |-- bux-1.0.0.tar.gz      -> bix
 # |   |-- fax-1.0.0.tar.gz      -> libbar ^1.0.0 ? ($cxx.target.class == 'windows') config.fax.backend=libbar |
 # |   |                            libbaz ^1.0.0 ? ($cxx.target.class != 'windows') config.fax.backend=libbaz,
 # |   |                            libbiz ? ($config.fax.libbiz) config.fax.extras='[b\i$z]',
@@ -2785,10 +2790,10 @@ test.arguments += --sys-no-query
 
         $* libbiz 2>>EOE != 0;
           error: unable to satisfy constraints on package libfoo
-            info: libfox depends on (libfoo == 0.0.1)
             info: libbox depends on (libfoo == 1.0.0)
-            info: available libfoo/0.0.1
+            info: libfox depends on (libfoo == 0.0.1)
             info: available libfoo/1.0.0
+            info: available libfoo/0.0.1
             info: explicitly specify libfoo version to manually satisfy both constraints
           info: while satisfying libbox/0.0.2
           info: while satisfying libbiz/0.0.1
@@ -3949,7 +3954,7 @@ test.arguments += --sys-no-query
       $pkg_drop foo
     }
 
-    : multiple-alternatives
+    : multiple-alts
     :
     {
       +$clone_cfg
@@ -4206,7 +4211,7 @@ test.arguments += --sys-no-query
       {
         +$clone_cfg
 
-        : reevaluate-alternatives
+        : reevaluate-alts
         :
         {
           +$clone_cfg
@@ -4320,19 +4325,16 @@ test.arguments += --sys-no-query
             $* box libbox 2>!;
 
             # While at it, test the reused-only alternative selection mode.
+            # Also test the postponement of the 'unable to satisfy constraints
+            # on package' failure which ends up with the 'unable to downgrade
+            # package' failure.
             #
             $* box +{ config.box.extras=true } libbox/0.1.0 2>>EOE != 0;
-              error: unable to select dependency alternative for package box/1.0.0
-                info: explicitly specify dependency packages to manually select the alternative
-                info: alternative: libbiz
-                info: unsatisfactory alternative: libbox
-                error: unable to satisfy constraints on package libbox
-                info: command line depends on (libbox == 0.1.0)
-                info: box depends on (libbox >= 0.1.1)
-                info: available libbox/0.1.0
-                info: available libbox/1.0.0
-                info: explicitly specify libbox version to manually satisfy both constraints
-              info: while satisfying box/1.0.0
+              error: unable to downgrade package libbox/1.0.0 to 0.1.0
+                info: because package box depends on (libbox >= 0.1.1)
+                info: consider re-trying with --upgrade|-u potentially combined with --recursive|-r
+                info: or explicitly request up/downgrade of package box
+                info: or explicitly specify package libbox version to manually satisfy these constraints
               EOE
 
             $* box +{ config.box.extras=true } libbox/0.1.0 ?libbiz 2>>~%EOE%;
@@ -4372,6 +4374,93 @@ test.arguments += --sys-no-query
             $pkg_drop box;
             $pkg_drop libbox
           }
+
+          : postpone-unable-satisfy
+          :
+          : Similar to the above, but this time the postponement of the
+          : 'unable to satisfy constraints on package' failure ends up with
+          : downgrading of the unsatisfied dependent (bax).
+          :
+          {
+            $clone_cfg;
+
+            $* bax libbox 2>!;
+
+            $* bax +{ config.bax.extras=true } libbox/0.1.0 bix 2>>~%EOE%;
+              build plan:
+                downgrade libbox/0.1.0
+                downgrade bax/0.1.0
+                  config.bax.extras=true (user configuration)
+                  config.bax.backend=libbox (set by bax)
+                new bix/1.0.0
+              disfigured bax/1.0.0
+              disfigured libbox/1.0.0
+              fetched libbox/0.1.0
+              unpacked libbox/0.1.0
+              fetched bax/0.1.0
+              unpacked bax/0.1.0
+              fetched bix/1.0.0
+              unpacked bix/1.0.0
+              configured libbox/0.1.0
+              configured bax/0.1.0
+              configured bix/1.0.0
+              %info: .+libbox-0.1.0.+ is up to date%
+              %info: .+bax-0.1.0.+ is up to date%
+              %info: .+bix-1.0.0.+ is up to date%
+              updated libbox/0.1.0
+              updated bax/0.1.0
+              updated bix/1.0.0
+              EOE
+
+            $pkg_drop bix;
+            $pkg_drop bax;
+            $pkg_drop libbox
+          }
+
+          : postpone-unable-satisfy-dep
+          :
+          : Similar to the above, but the failure postponement ends up with
+          : downgrading on the next dependency refinement iteration.
+          :
+          {
+            $clone_cfg;
+
+            $* bax libbox bux ?bix/0.1.0 2>!;
+
+            $* bax +{ config.bax.extras=true } libbox/0.1.0 ?bix 2>>~%EOE%;
+              build plan:
+                downgrade libbox/0.1.0
+                downgrade bax/0.1.0
+                  config.bax.extras=true (user configuration)
+                  config.bax.backend=libbox (set by bax)
+                upgrade bix/1.0.0
+                reconfigure bux (dependent of bix)
+              disfigured bux/1.0.0
+              disfigured bix/0.1.0
+              disfigured bax/1.0.0
+              disfigured libbox/1.0.0
+              fetched libbox/0.1.0
+              unpacked libbox/0.1.0
+              fetched bax/0.1.0
+              unpacked bax/0.1.0
+              fetched bix/1.0.0
+              unpacked bix/1.0.0
+              configured libbox/0.1.0
+              configured bax/0.1.0
+              configured bix/1.0.0
+              configured bux/1.0.0
+              %info: .+libbox-0.1.0.+ is up to date%
+              %info: .+bax-0.1.0.+ is up to date%
+              %info: .+bux-1.0.0.+ is up to date%
+              updated libbox/0.1.0
+              updated bax/0.1.0
+              updated bux/1.0.0
+              EOE
+
+            $pkg_drop bux;
+            $pkg_drop bax;
+            $pkg_drop libbox
+          }
         }
 
         : reconfigure