Try to automatically resolve unsatisfied dependency constraints by specifying dependency version

5 files changed, 1925 insertions, 625 deletions

diff --git a/bpkg/package-query.cxx b/bpkg/package-query.cxx
index 871b4fb..a90cdef 100644
--- a/bpkg/package-query.cxx
+++ b/bpkg/package-query.cxx
@@ -249,7 +249,7 @@ namespace bpkg
           // prerequisites? I'd say not.
           //
           if (shared_ptr<repository_fragment> r =
-              find (fr.fragment.load (), ap, chain, false))
+              find (fr.fragment.load (), ap, chain, false /* prereq */))
             return r;
         }
       }
@@ -264,7 +264,7 @@ namespace bpkg
           for (const auto& fr: pr.load ()->fragments)
           {
             if (shared_ptr<repository_fragment> r =
-                find (fr.fragment.load (), ap, chain, false))
+                find (fr.fragment.load (), ap, chain, false /* prereq */))
               return r;
           }
         }
diff --git a/bpkg/pkg-build-collect.cxx b/bpkg/pkg-build-collect.cxx
index ff6547f..6f5f864 100644
--- a/bpkg/pkg-build-collect.cxx
+++ b/bpkg/pkg-build-collect.cxx
@@ -353,6 +353,17 @@ namespace bpkg
     else
       constraints = move (p.constraints);
 
+    // Copy upgrade flag if "stronger" (existing wins over non-existing and
+    // upgrade wins over patch).
+    //
+    if (upgrade < p.upgrade)
+      upgrade = p.upgrade;
+
+    // Copy deorphan flag if greater.
+    //
+    if (p.deorphan)
+      deorphan = true;
+
     // Copy hold_* flags if they are "stronger".
     //
     if (!hold_package || (p.hold_package && *p.hold_package > *hold_package))
@@ -2409,6 +2420,18 @@ namespace bpkg
       // the specified diag record. In the dry-run mode don't change the
       // packages collection state (postponed_repo set, etc).
       //
+      // If an alternative dependency package is specified as a dependency
+      // with a version constraint on the command line, then overwrite the
+      // dependent's constraint with the command line's constraint, if the
+      // latter is a subset of former. If it is not a subset, then bail out
+      // indicating that the alternative dependencies cannot be resolved
+      // (builds is nullopt), unless ignore_unsatisfactory_dep_spec argument
+      // is true. In the latter case continue precollecting as if no
+      // constraint is specified on the command line for this dependency. That
+      // will likely result in the unsatisfied dependent problem, which will
+      // be either resolved or end up with the failure (see
+      // unsatisfied_dependents for details).
+      //
       // Note that rather than considering an alternative as unsatisfactory
       // (returning no pre-builds) the function can fail in some cases
       // (multiple possible configurations for a build-time dependency, orphan
@@ -2498,6 +2521,7 @@ namespace bpkg
          bool buildtime,
          const package_prerequisites* prereqs,
          bool check_constraints,
+         bool ignore_unsatisfactory_dep_spec,
          diag_record* dr = nullptr,
          bool dry_run = false) -> precollect_result
         {
@@ -2577,55 +2601,59 @@ namespace bpkg
                   //
                   // The version constraint is specified,
                   //
-                  bp.hold_version && *bp.hold_version)
+                  !bp.constraints.empty ())
               {
                 assert (bp.constraints.size () == 1);
 
                 const build_package::constraint_type& c (bp.constraints[0]);
 
-                dep_constr = &c.value;
-                system = bp.system;
-
                 // If the user-specified dependency constraint is the wildcard
                 // version, then it satisfies any dependency constraint.
                 //
-                if (!wildcard (*dep_constr) &&
-                    !satisfies (*dep_constr, dp.constraint))
+                if (!wildcard (c.value) && !satisfies (c.value, dp.constraint))
                 {
                   // 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 (!ignore_unsatisfactory_dep_spec)
                   {
-                    //             "  info: ..."
-                    string indent ("          ");
+                    if (dr != nullptr)
+                    {
+                      //             "  info: ..."
+                      string indent ("          ");
 
-                    *dr << error << "unable to satisfy constraints on package "
-                        << dn <<
-                      info << nm << pdb << " depends on (" << dn << ' '
-                           << *dp.constraint << ')';
+                      *dr << error << "unable to satisfy constraints on package "
+                          << dn <<
+                        info << nm << pdb << " depends on (" << dn << ' '
+                          << *dp.constraint << ')';
 
-                    {
-                      set<package_key> printed;
-                      print_constraints (*dr, pkg, indent, printed);
-                    }
+                      {
+                        set<package_key> printed;
+                        print_constraints (*dr, pkg, indent, printed);
+                      }
 
-                    *dr << info << c.dependent << " depends on (" << dn << ' '
-                                << c.value << ')';
+                      *dr << info << c.dependent << " depends on (" << dn << ' '
+                          << c.value << ')';
 
-                    if (const build_package* d = dependent_build (c))
-                    {
-                      set<package_key> printed;
-                      print_constraints (*dr, *d, indent, printed);
+                      if (const build_package* d = dependent_build (c))
+                      {
+                        set<package_key> printed;
+                        print_constraints (*dr, *d, indent, printed);
+                      }
+
+                      *dr << info << "specify " << dn << " version to satisfy "
+                          << nm << " constraint";
                     }
 
-                    *dr << info << "specify " << dn << " version to satisfy "
-                                << nm << " constraint";
+                    return precollect_result (false /* postpone */);
                   }
-
-                  return precollect_result (false /* postpone */);
+                }
+                else
+                {
+                  dep_constr = &c.value;
+                  system = bp.system;
                 }
               }
             }
@@ -3417,7 +3445,8 @@ namespace bpkg
          size_t dai,
          prebuilds&& bs,
          const package_prerequisites* prereqs,
-         bool check_constraints)
+         bool check_constraints,
+         bool ignore_unsatisfactory_dep_spec)
         {
           // Dependency alternative position.
           //
@@ -3468,6 +3497,8 @@ namespace bpkg
               nullopt,                    // Checkout root.
               false,                      // Checkout purge.
               strings (),                 // Configuration variables.
+              nullopt,                    // Upgrade.
+              false,                      // Deorphan.
               {pvk},                      // Required by (dependent).
               true,                       // Required by dependents.
               0};                         // State flags.
@@ -3884,12 +3915,14 @@ namespace bpkg
 
                 const dependency_alternative& a (edas[i].first);
 
-                precollect_result r (precollect (a,
-                                                 das.buildtime,
-                                                 prereqs,
-                                                 check_constraints,
-                                                 nullptr /* diag_record */,
-                                                 true /* dry_run */));
+                precollect_result r (
+                  precollect (a,
+                              das.buildtime,
+                              prereqs,
+                              check_constraints,
+                              ignore_unsatisfactory_dep_spec,
+                              nullptr /* diag_record */,
+                              true /* dry_run */));
 
                 if (r.builds && r.reused)
                 {
@@ -3918,12 +3951,14 @@ namespace bpkg
 
                   if (&a != &da) // Skip the current dependency alternative.
                   {
-                    precollect_result r (precollect (a,
-                                                     das.buildtime,
-                                                     nullptr /* prereqs */,
-                                                     check_constraints,
-                                                     nullptr /* diag_record */,
-                                                     true /* dry_run */));
+                    precollect_result r (
+                      precollect (a,
+                                  das.buildtime,
+                                  nullptr /* prereqs */,
+                                  check_constraints,
+                                  ignore_unsatisfactory_dep_spec,
+                                  nullptr /* diag_record */,
+                                  true /* dry_run */));
 
                     if (r.builds && r.reused)
                     {
@@ -3940,8 +3975,11 @@ namespace bpkg
               // If there are none and we are in the "check constraints" mode,
               // then repeat the search with this mode off.
               //
+              bool cc (check_constraints);
               if (!has_alt && check_constraints && unsatisfactory)
               {
+                cc = false;
+
                 for (i = 0; i != edas.size (); ++i)
                 {
                   if (unacceptable ())
@@ -3956,6 +3994,36 @@ namespace bpkg
                                   das.buildtime,
                                   nullptr /* prereqs */,
                                   false /* check_constraints */,
+                                  ignore_unsatisfactory_dep_spec,
+                                  nullptr /* diag_record */,
+                                  true /* dry_run */));
+
+                    if (r.builds && r.reused)
+                    {
+                      has_alt = true;
+                      break;
+                    }
+                  }
+                }
+              }
+
+              if (!has_alt && !ignore_unsatisfactory_dep_spec)
+              {
+                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 */,
+                                  cc,
+                                  true /* ignore_unsatisfactory_dep_spec */,
                                   nullptr /* diag_record */,
                                   true /* dry_run */));
 
@@ -4626,6 +4694,20 @@ namespace bpkg
       //
       bool check_constraints (true);
 
+      // Initially don't ignore the unsatisfactory user-specified dependency
+      // specs, considering the dependency alternative as unsatisfactory if
+      // there are any. Failed that, re-try but this time ignore such specs,
+      // so that the unsatisfactory dependency can later be handled by
+      // collect_build() (which can fail, postpone failure, etc; see its
+      // implementation for details).
+      //
+      // The thinking here is that we don't ignore the unsatisfactory
+      // dependency specs initially to skip the alternatives which are
+      // unresolvable for that reason and prefer alternatives which satisfy
+      // the command line constraints.
+      //
+      bool ignore_unsatisfactory_dep_spec (false);
+
       for (bool unacceptable (false);;)
       {
         // The index and pre-collection result of the first satisfactory
@@ -4691,7 +4773,11 @@ namespace bpkg
           const dependency_alternative& da (edas[i].first);
 
           precollect_result pcr (
-            precollect (da, das.buildtime, prereqs, check_constraints));
+            precollect (da,
+                        das.buildtime,
+                        prereqs,
+                        check_constraints,
+                        ignore_unsatisfactory_dep_spec));
 
           // If we didn't come up with satisfactory dependency builds, then
           // skip this alternative and try the next one, unless the collecting
@@ -4757,6 +4843,7 @@ namespace bpkg
                              di,
                              &prereqs,
                              &check_constraints,
+                             &ignore_unsatisfactory_dep_spec,
                              pre_reeval,
                              reeval,
                              &trace,
@@ -4817,7 +4904,8 @@ namespace bpkg
                                  dai,
                                  move (*pcr.builds),
                                  prereqs,
-                                 check_constraints))
+                                 check_constraints,
+                                 ignore_unsatisfactory_dep_spec))
               {
                 postpone (nullptr); // Already inserted into postponed_cfgs.
                 return true;
@@ -4904,7 +4992,8 @@ namespace bpkg
                                dai,
                                move (*pcr.builds),
                                prereqs,
-                               check_constraints))
+                               check_constraints,
+                               ignore_unsatisfactory_dep_spec))
             {
               postpone (nullptr); // Already inserted into postponed_cfgs.
               break;
@@ -4956,6 +5045,12 @@ namespace bpkg
           continue;
         }
 
+        if (!ignore_unsatisfactory_dep_spec)
+        {
+          ignore_unsatisfactory_dep_spec = true;
+          continue;
+        }
+
         // Otherwise we would have thrown/failed earlier.
         //
         assert (!pre_reeval && !reeval);
@@ -4976,7 +5071,8 @@ namespace bpkg
             precollect (da.first,
                         das.buildtime,
                         nullptr /* prereqs */,
-                        false /* check_constraints */,
+                        true /* check_constraints */,
+                        false /* ignore_unsatisfactory_dep_spec */,
                         &dr);
           }
 
@@ -5017,10 +5113,17 @@ namespace bpkg
 
         for (const auto& da: edas)
         {
-          precollect_result r (precollect (da.first,
-                                           das.buildtime,
-                                           nullptr /* prereqs */,
-                                           false /* check_constraints */));
+          // Note that we pass false as the check_constraints argument to make
+          // sure that the alternatives are always saved into
+          // precollect_result::builds rather than into
+          // precollect_result::unsatisfactory.
+          //
+          precollect_result r (
+            precollect (da.first,
+                        das.buildtime,
+                        nullptr /* prereqs */,
+                        false /* check_constraints */,
+                        true /* ignore_unsatisfactory_dep_spec */));
 
           if (r.builds)
           {
@@ -5049,10 +5152,12 @@ namespace bpkg
 
           for (const auto& da: edas)
           {
-            precollect_result r (precollect (da.first,
-                                             das.buildtime,
-                                             nullptr /* prereqs */,
-                                             true /* check_constraints */));
+            precollect_result r (
+              precollect (da.first,
+                          das.buildtime,
+                          nullptr /* prereqs */,
+                          true /* check_constraints */,
+                          false /* ignore_unsatisfactory_dep_spec */));
 
             if (r.reused && r.unsatisfactory)
             {
@@ -5069,6 +5174,7 @@ namespace bpkg
                           das.buildtime,
                           nullptr /* prereqs */,
                           true /* check_constraints */,
+                          false /* ignore_unsatisfactory_dep_spec */,
                           &dr);
             }
           }
@@ -5272,6 +5378,8 @@ namespace bpkg
         nullopt,                    // Checkout root.
         false,                      // Checkout purge.
         strings (),                 // Configuration variables.
+        nullopt,                    // Upgrade.
+        false,                      // Deorphan.
         move (required_by),         // Required by (dependencies).
         false,                      // Required by dependents.
         build_package::adjust_reconfigure | build_package::build_repoint};
@@ -5400,6 +5508,8 @@ namespace bpkg
       nullopt,    // Checkout root.
       false,      // Checkout purge.
       strings (), // Configuration variables.
+      nullopt,    // Upgrade.
+      false,      // Deorphan.
       {},         // Required by.
       false,      // Required by dependents.
       0};         // State flags.
@@ -5525,6 +5635,8 @@ namespace bpkg
         nullopt,       // Checkout root.
         false,         // Checkout purge.
         strings (),    // Configuration variables.
+        nullopt,       // Upgrade.
+        false,         // Deorphan.
         {},            // Required by.
         false,         // Required by dependents.
         build_package::adjust_unhold};
@@ -7320,6 +7432,8 @@ namespace bpkg
             nullopt,                   // Checkout root.
             false,                     // Checkout purge.
             strings (),                // Configuration variables.
+            nullopt,                   // Upgrade.
+            false,                     // Deorphan.
             {move (pvk)},              // Required by (dependency).
             false,                     // Required by dependents.
             build_package::adjust_reconfigure};
@@ -7382,7 +7496,7 @@ namespace bpkg
                        [&c] (const constraint_type& v)
                        {
                          return v.dependent == c.dependent &&
-                                v.value == c.value;
+                                v.value     == c.value;
                        }) == p.constraints.end ())
           {
             p.constraints.emplace_back (move (c));
@@ -7698,6 +7812,8 @@ namespace bpkg
             nullopt,                    // Checkout root.
             false,                      // Checkout purge.
             strings (),                 // Configuration variables.
+            nullopt,                    // Upgrade.
+            false,                      // Deorphan.
             {},                         // Required by (dependency).
             false,                      // Required by dependents.
             0};                         // State flags.
@@ -7808,28 +7924,30 @@ namespace bpkg
 
     build_package p {
       build_package::build,
-        dep.db,
-        move (sp),
-        move (rp.first),
-        move (rp.second),
-        nullopt,                    // Dependencies.
-        nullopt,                    // Dependencies alternatives.
-        nullopt,                    // Package skeleton.
-        nullopt,                    // Postponed dependency alternatives.
-        false,                      // Recursive collection.
-        nullopt,                    // Hold package.
-        nullopt,                    // Hold version.
-        {},                         // Constraints.
-        system,                     // System.
-        false,                      // Keep output directory.
-        false,                      // Disfigure (from-scratch reconf).
-        false,                      // Configure-only.
-        nullopt,                    // Checkout root.
-        false,                      // Checkout purge.
-        strings (),                 // Configuration variables.
-        {dpt},                      // Required by (dependent).
-        true,                       // Required by dependents.
-        0};                         // State flags.
+      dep.db,
+      move (sp),
+      move (rp.first),
+      move (rp.second),
+      nullopt,                    // Dependencies.
+      nullopt,                    // Dependencies alternatives.
+      nullopt,                    // Package skeleton.
+      nullopt,                    // Postponed dependency alternatives.
+      false,                      // Recursive collection.
+      nullopt,                    // Hold package.
+      nullopt,                    // Hold version.
+      {},                         // Constraints.
+      system,                     // System.
+      false,                      // Keep output directory.
+      false,                      // Disfigure (from-scratch reconf).
+      false,                      // Configure-only.
+      nullopt,                    // Checkout root.
+      false,                      // Checkout purge.
+      strings (),                 // Configuration variables.
+      nullopt,                    // Upgrade.
+      false,                      // Deorphan.
+      {dpt},                      // Required by (dependent).
+      true,                       // Required by dependents.
+      0};                         // State flags.
 
     // Add constraints, if present.
     //
@@ -7893,6 +8011,8 @@ namespace bpkg
       nullopt,                            // Checkout root.
       false,                              // Checkout purge.
       strings (),                         // Configuration variables.
+      nullopt,                            // Upgrade.
+      false,                              // Deorphan.
       move (rb),                          // Required by (dependency).
       false,                              // Required by dependents.
       build_package::build_reevaluate};
@@ -7955,6 +8075,8 @@ namespace bpkg
       nullopt,                     // Checkout root.
       false,                       // Checkout purge.
       strings (),                  // Configuration variables.
+      nullopt,                     // Upgrade.
+      false,                       // Deorphan.
       move (rb),                   // Required by (dependency).
       false,                       // Required by dependents.
       flags};
diff --git a/bpkg/pkg-build-collect.hxx b/bpkg/pkg-build-collect.hxx
index 122ed22..6cb155d 100644
--- a/bpkg/pkg-build-collect.hxx
+++ b/bpkg/pkg-build-collect.hxx
@@ -190,10 +190,19 @@ namespace bpkg
     bool
     recursive_collection_postponed () const;
 
-    // Hold flags. Note that we only "increase" the hold_package value that is
-    // already in the selected package.
+    // Hold flags.
+    //
+    // Note that we only "increase" the hold_package value that is already in
+    // the selected package, unless the adjust_unhold flag is set (see below).
     //
     optional<bool> hold_package;
+
+    // Note that it is perfectly valid for the hold_version flag to be false
+    // while the command line constraint is present in the constraints list
+    // (see below). This may happen if the package build is collected by the
+    // unsatisfied dependency constraints resolution logic (see
+    // try_replace_dependency() in pkg-build.cxx for details).
+    //
     optional<bool> hold_version;
 
     // Constraint value plus, normally, the dependent package name/version
@@ -291,6 +300,21 @@ namespace bpkg
     //
     strings config_vars;
 
+    // If present, then the package is requested to be upgraded (true) or
+    // patched (false). Can only be present if the package is already
+    // selected. Can only be false if the selected package version is
+    // patchable. Used by the unsatisfied dependency constraints resolution
+    // logic (see try_replace_dependency() in pkg-build.cxx for details).
+    //
+    optional<bool> upgrade;
+
+    // If true, then this package is requested to be deorphaned. Can only be
+    // true if the package is already selected and is orphaned. Used by the
+    // unsatisfied dependency constraints resolution logic (see
+    // try_replace_dependency() in pkg-build.cxx for details).
+    //
+    bool deorphan;
+
     // Set of packages (dependents or dependencies but not a mix) that caused
     // this package to be built or adjusted. The 'command line' name signifies
     // user selection and can be present regardless of the
@@ -298,7 +322,9 @@ namespace bpkg
     //
     // Note that if this is a package name, then this package is expected to
     // be collected (present in the map), potentially just pre-entered if
-    // required_by_dependents is false.
+    // required_by_dependents is false. If required_by_dependents is true,
+    // then the packages in the set are all expected to be collected as builds
+    // (action is build, available is not NULL, etc).
     //
     // Also note that if required_by_dependents is true, then all the
     // dependent package versions in the required_by set are expected to be
@@ -763,15 +789,26 @@ namespace bpkg
   // problems will be resolved naturally as a result of the execution plan
   // refinement.
   //
+  // And yet, if these problems do not resolve naturally, then we still try to
+  // resolve them by finding dependency versions which satisfy all the imposed
+  // constraints.
+  //
   // Specifically, we cache such unsatisfied dependents/constraints, pretend
   // that the dependents don't impose them and proceed with the remaining
   // collecting/ordering, simulating the plan execution, and evaluating the
   // dependency versions. After that, if scratch_collection exception has not
   // been thrown, we check if the execution plan is finalized or a further
-  // refinement is required. In the former case we report the first
-  // encountered unsatisfied (and ignored) dependency constraint and
-  // fail. Otherwise, we drop the cache and proceed with the next iteration of
-  // the execution plan refinement which may resolve these problems naturally.
+  // refinement is required. In the latter case we drop the cache and proceed
+  // with the next iteration of the execution plan refinement which may
+  // resolve these problems naturally. Otherwise, we pick the first collected
+  // unsatisfactory dependency and try to find the best available version,
+  // considering all the constraints imposed by the user (explicit version
+  // constraint, --patch and/or --deorphan options, etc) as well as by its new
+  // and existing dependents. If the search succeeds, we update an existing
+  // package spec or add the new one to the command line and recollect from
+  // the very beginning. Note that we always add a new spec with the
+  // hold_version flag set to false. If the search fails, we report the first
+  // encountered unsatisfied (and ignored) dependency constraint and fail.
   //
   struct unsatisfied_constraint
   {
diff --git a/bpkg/pkg-build.cxx b/bpkg/pkg-build.cxx
index 51e1fb1..755d9d9 100644
--- a/bpkg/pkg-build.cxx
+++ b/bpkg/pkg-build.cxx
@@ -293,6 +293,11 @@ namespace bpkg
     database*                    db;            // Can only be NULL if system.
     package_name                 name;
     optional<version_constraint> constraint;    // nullopt if unspecified.
+
+    // Can only be true if constraint is specified.
+    //
+    bool                         hold_version;
+
     shared_ptr<selected_package> selected;
     bool                         system;
     bool                         existing;      // Build as archive or directory.
@@ -364,8 +369,8 @@ namespace bpkg
   //
   struct evaluate_result
   {
-    // The system, existing, and orphan members are meaningless if the unused
-    // flag is true.
+    // The system, existing, upgrade, and orphan members are meaningless if
+    // the unused flag is true.
     //
     reference_wrapper<database>                db;
     shared_ptr<available_package>              available;
@@ -373,6 +378,7 @@ namespace bpkg
     bool                                       unused;
     bool                                       system;
     bool                                       existing;
+    optional<bool>                             upgrade;
 
     // Original orphan version which needs to be deorphaned. May only be
     // present for the deorphan mode.
@@ -443,6 +449,7 @@ namespace bpkg
                               false   /* unused */,
                               false   /* system */,
                               false   /* existing */,
+                              nullopt /* upgrade */,
                               nullopt /* orphan */};
     };
 
@@ -580,6 +587,7 @@ namespace bpkg
                               true    /* unused */,
                               false   /* system */,
                               false   /* existing */,
+                              nullopt /* upgrade */,
                               nullopt /* orphan */};
     }
 
@@ -709,6 +717,7 @@ namespace bpkg
                               false   /* unused */,
                               false   /* system */,
                               false   /* existing */,
+                              nullopt /* upgrade */,
                               nullopt /* orphan */};
     };
 
@@ -826,8 +835,9 @@ namespace bpkg
     // function description for details). Collect (and sort) unsatisfied
     // dependents per the unsatisfiable version in case we need to print them.
     //
-    // NOTE: don't forget to update the find_orphan_match() lambda if changing
-    // anything deorphan-related here.
+    // NOTE: don't forget to update the find_orphan_match() lambda and the
+    // try_replace_dependency() function if changing anything deorphan-related
+    // here.
     //
     using sp_set = set<config_selected_package>;
 
@@ -883,6 +893,7 @@ namespace bpkg
                             dsys,
                             deorphaned, dov,
                             existing,
+                            upgrade,
                             &no_change,
                             &trace] (available&& a, const char* what)
     {
@@ -901,6 +912,7 @@ namespace bpkg
         false /* unused */,
         dsys,
         existing,
+        upgrade,
         *dov};
     };
 
@@ -1026,7 +1038,7 @@ namespace bpkg
         // Save the latest available package version.
         //
         if (deorphan_latest_available.first == nullptr)
-          deorphan_latest_available = af;
+          deorphan_latest_available = move (af);
 
         // If the available package version is less then the orphan revision
         // then we can bail out from the loop, since all the versions from the
@@ -1081,27 +1093,31 @@ namespace bpkg
           false /* unused */,
           dsys,
           existing,
+          upgrade,
           nullopt /* orphan */};
       }
     }
 
-    if (deorphan_latest_iteration.first != nullptr)
-      return deorphan_result (move (deorphan_latest_iteration),
-                              "latest iteration");
+    if (orphan_best_match)
+    {
+      if (deorphan_latest_iteration.first != nullptr)
+        return deorphan_result (move (deorphan_latest_iteration),
+                                "latest iteration");
 
-    if (deorphan_later_revision.first != nullptr)
-      return deorphan_result (move (deorphan_later_revision),
-                              "later revision");
+      if (deorphan_later_revision.first != nullptr)
+        return deorphan_result (move (deorphan_later_revision),
+                                "later revision");
 
-    if (deorphan_later_patch.first != nullptr)
-      return deorphan_result (move (deorphan_later_patch), "later patch");
+      if (deorphan_later_patch.first != nullptr)
+        return deorphan_result (move (deorphan_later_patch), "later patch");
 
-    if (deorphan_later_minor.first != nullptr)
-      return deorphan_result (move (deorphan_later_minor), "later minor");
+      if (deorphan_later_minor.first != nullptr)
+        return deorphan_result (move (deorphan_later_minor), "later minor");
 
-    if (deorphan_latest_available.first != nullptr)
-      return deorphan_result (move (deorphan_latest_available),
-                              "latest available");
+      if (deorphan_latest_available.first != nullptr)
+        return deorphan_result (move (deorphan_latest_available),
+                                "latest available");
+    }
 
     // If we aim to upgrade to the latest version, then what we currently have
     // is the only thing that we can get, and so returning the "no change"
@@ -1187,6 +1203,9 @@ namespace bpkg
       size_t i (0), n (ps.size ());
       for (auto p (ps.begin ()); i != n; ++p)
       {
+        // It would probably be nice to also print the unsatisfied constraint
+        // here, but let's keep it simple for now.
+        //
         dr << (i == 0 ? " " : ", ") << *p->package << p->db;
 
         if (++i == 5 && n != 6) // Printing 'and 1 more' looks stupid.
@@ -1440,6 +1459,609 @@ namespace bpkg
     return r && r->available == nullptr ? nullopt : r;
   }
 
+  // Try to replace a collected package which is unsatisfactory for some of
+  // its new and/or existing dependents with a satisfactory available version.
+  //
+  // Specifically, try to find the best available package version considering
+  // all the imposed constraints as per unsatisfied_dependents description. If
+  // succeed, update/add the respective entry to hold_pkgs or dep_pkgs and
+  // return true.
+  //
+  // Notes:
+  //
+  // - Expected to be called after the execution plan is fully refined. That,
+  //   in particular, means that all the existing dependents are also
+  //   collected and thus the constraints they impose are already in their
+  //   dependencies' constraints lists.
+  //
+  // - The replacement is denied in the following cases:
+  //
+  //   - If it turns out that the package have been specified on the command
+  //     line (by the user or by us on some previous iteration) with an exact
+  //     version constraint, then we cannot try any other version.
+  //
+  //   - If the dependency is system, then it is either specified with the
+  //     wildcard version or its exact version have been specified by the user
+  //     or have been deduced by the system package manager. In the former
+  //     case we actually won't be calling this function for this package
+  //     since the wildcard version satisfies any constraint. Thus, an exact
+  //     version has been specified/deduced for this dependency and so we
+  //     cannot try any other version.
+  //
+  //   - If the dependency is being built as an existing archive/directory,
+  //     then its version is determined and so we cannot try any other
+  //     version.
+  //
+  //   - If the package is already configured with the version held and the
+  //     user didn't specify this package on the command line and it is not
+  //     requested to be upgraded, patched, and/or deorphaned, then we
+  //     shouldn't be silently up/down-grading it.
+  //
+  bool
+  try_replace_dependency (const common_options& o,
+                          const build_package& p,
+                          const build_packages& pkgs,
+                          vector<build_package>& hold_pkgs,
+                          dependency_packages& dep_pkgs)
+  {
+    tracer trace ("try_replace_dependency");
+
+    // Bail out for the system package build.
+    //
+    if (p.system)
+    {
+      l4 ([&]{trace << "replacement of unsatisfactory package version "
+                    << p.available_name_version_db () << " is denied "
+                    << "since it is being configured as system";});
+
+      return false;
+    }
+
+    // Bail out for an existing package archive/directory.
+    //
+    database& db (p.db);
+    const package_name& nm (p.name ());
+
+    if (find_existing (db,
+                       nm,
+                       nullopt /* version_constraint */).first != nullptr)
+    {
+      l4 ([&]{trace << "replacement of unsatisfactory package version "
+                    << p.available_name_version_db () << " is denied since "
+                    << "it is being built as existing archive/directory";});
+
+      return false;
+    }
+
+    // Find the package command line entry and stash the reference to its
+    // version constraint, if any. Bail out if the constraint is specified as
+    // an exact package version.
+    //
+    build_package*      hold_pkg   (nullptr);
+    dependency_package* dep_pkg    (nullptr);
+    version_constraint* constraint (nullptr);
+
+    for (build_package& hp: hold_pkgs)
+    {
+      if (hp.name () == nm && hp.db == db)
+      {
+        hold_pkg = &hp;
+
+        if (!hp.constraints.empty ())
+        {
+          // Can only contain the user-specified constraint.
+          //
+          assert (hp.constraints.size () == 1);
+
+          version_constraint& c (hp.constraints[0].value);
+
+          if (c.min_version == c.max_version)
+          {
+            l4 ([&]{trace << "replacement of unsatisfactory package version "
+                          << p.available_name_version_db () << " is denied "
+                          << "since it is specified on command line as '"
+                          << nm << ' ' << c << "'";});
+
+            return false;
+          }
+          else
+            constraint = &c;
+        }
+
+        break;
+      }
+    }
+
+    if (hold_pkg == nullptr)
+    {
+      for (dependency_package& dp: dep_pkgs)
+      {
+        if (dp.name == nm && dp.db != nullptr && *dp.db == db)
+        {
+          dep_pkg = &dp;
+
+          if (dp.constraint)
+          {
+            version_constraint& c (*dp.constraint);
+
+            if (c.min_version == c.max_version)
+            {
+              l4 ([&]{trace << "replacement of unsatisfactory package version "
+                            << p.available_name_version_db () << " is denied "
+                            << "since it is specified on command line as '?"
+                            << nm << ' ' << c << "'";});
+
+              return false;
+            }
+            else
+              constraint = &c;
+          }
+
+          break;
+        }
+      }
+    }
+
+    // Bail out if the selected package version is held and the package is not
+    // specified on the command line nor is being upgraded/deorphaned via its
+    // dependents recursively.
+    //
+    const shared_ptr<selected_package>& sp (p.selected);
+
+    if (sp != nullptr && sp->hold_version         &&
+        hold_pkg == nullptr && dep_pkg == nullptr &&
+        !p.upgrade && !p.deorphan)
+    {
+      l4 ([&]{trace << "replacement of unsatisfactory package version "
+                    << p.available_name_version_db () << " is denied since "
+                    << "it is not specified on command line nor is being "
+                    << "upgraded or deorphaned";});
+
+      return false;
+    }
+
+    transaction t (db);
+
+    assert (!p.constraints.empty ()); // Must contain unsatisfied constraints.
+
+    // Collect the repository fragments to search the available packages in.
+    //
+    config_repo_fragments rfs;
+
+    // Add a repository fragment to the specified list, suppressing duplicates.
+    //
+    auto add = [] (shared_ptr<repository_fragment>&& rf,
+                   vector<shared_ptr<repository_fragment>>& rfs)
+    {
+      if (find (rfs.begin (), rfs.end (), rf) == rfs.end ())
+        rfs.push_back (move (rf));
+    };
+
+    // If the package is specified as build-to-hold on the command line, then
+    // collect the root repository fragment from its database. Otherwise,
+    // collect the repository fragments its dependent packages come from.
+    //
+    if (hold_pkg != nullptr)
+    {
+      add (db.find<repository_fragment> (empty_string), rfs[db]);
+    }
+    else
+    {
+      // Collect the repository fragments the new dependents come from.
+      //
+      if (p.required_by_dependents)
+      {
+        for (const package_version_key& dvk: p.required_by)
+        {
+          if (dvk.version) // Real package?
+          {
+            const build_package* d (pkgs.entered_build (dvk.db, dvk.name));
+
+            // Must be collected as a package build (see
+            // build_package::required_by for details).
+            //
+            assert (d != nullptr                       &&
+                    d->action                          &&
+                    *d->action == build_package::build &&
+                    d->available != nullptr);
+
+            for (const package_location& pl: d->available->locations)
+            {
+              const lazy_shared_ptr<repository_fragment>& lrf (
+                pl.repository_fragment);
+
+              // Note that here we also handle dependents fetched/unpacked
+              // using the existing archive/directory adding the root
+              // repository fragments from their configurations.
+              //
+              if (!rep_masked_fragment (lrf))
+                add (lrf.load (), rfs[lrf.database ()]);
+            }
+          }
+        }
+      }
+
+      // Collect the repository fragments the existing dependents come from.
+      //
+      // Note that all the existing dependents are already in the map (since
+      // collect_dependents() has already been called) and are either
+      // reconfigure adjustments or non-collected recursively builds.
+      //
+      if (sp != nullptr)
+      {
+        for (database& ddb: db.dependent_configs ())
+        {
+          for (auto& pd: query_dependents (ddb, nm, db))
+          {
+            const build_package* d (pkgs.entered_build (ddb, pd.name));
+
+            // See collect_dependents() for details.
+            //
+            assert (d != nullptr && d->action);
+
+            if ((*d->action == build_package::adjust &&
+                 (d->flags & build_package::adjust_reconfigure) != 0) ||
+                (*d->action == build_package::build && !d->dependencies))
+            {
+              shared_ptr<selected_package> p (
+                ddb.load<selected_package> (pd.name));
+
+              add_dependent_repo_fragments (ddb, p, rfs);
+            }
+          }
+        }
+      }
+    }
+
+    // Query the dependency available packages from all the collected
+    // repository fragments and select the most appropriate one. Note that
+    // this code is inspired by the evaluate_dependency() function
+    // implementation, which documents the below logic in great detail.
+    //
+    optional<version_constraint> c (constraint != nullptr
+                                    ? *constraint
+                                    : optional<version_constraint> ());
+
+    if (!c && p.upgrade && !*p.upgrade)
+    {
+      assert (sp != nullptr); // See build_package::upgrade.
+
+      c = patch_constraint (sp);
+
+      assert (c); // See build_package::upgrade.
+    }
+
+    available_packages afs (find_available (nm, c, rfs));
+
+    using available = pair<shared_ptr<available_package>,
+                           lazy_shared_ptr<repository_fragment>>;
+
+    available r;
+
+    // Version to deorphan.
+    //
+    const version* dov (p.deorphan ? &sp->version : nullptr);
+
+    optional<version_constraint> dopc; // Patch constraint for the above.
+    optional<version_constraint> domc; // Minor constraint for the above.
+
+    bool orphan_best_match (p.deorphan && constraint == nullptr && !p.upgrade);
+
+    if (orphan_best_match)
+    {
+      // Note that non-zero iteration makes a version non-standard, so we
+      // reset it to 0 to produce the patch/minor constraints.
+      //
+      version v (dov->epoch,
+                 dov->upstream,
+                 dov->release,
+                 dov->revision,
+                 0 /* iteration */);
+
+      dopc = patch_constraint (nm, v, true /* quiet */);
+      domc = minor_constraint (nm, v, true /* quiet */);
+    }
+
+    available deorphan_latest_iteration;
+    available deorphan_later_revision;
+    available deorphan_later_patch;
+    available deorphan_later_minor;
+    available deorphan_latest_available;
+
+    // Return true if a version satisfy all the dependency constraints.
+    //
+    auto satisfactory = [&p] (const version& v)
+    {
+      for (const auto& c: p.constraints)
+      {
+        if (!satisfies (v, c.value))
+          return false;
+      }
+
+      return true;
+    };
+
+    for (available& af: afs)
+    {
+      shared_ptr<available_package>& ap (af.first);
+
+      if (ap->stub ())
+        continue;
+
+      const version& av (ap->version);
+
+      // If we aim to upgrade to the latest version and it tends to be less
+      // then the selected one, then what we currently have is the best that
+      // we can get. Thus, we use the selected version as a replacement,
+      // unless it doesn't satisfy all the constraints or we are deorphaning.
+      //
+      if (constraint == nullptr && sp != nullptr && av < sp->version)
+      {
+        if (!sp->system () && !p.deorphan && satisfactory (sp->version))
+        {
+          r = make_available_fragment (o, db, sp);
+          break;
+        }
+      }
+
+      // Skip if the available package version doesn't satisfy all the
+      // constraints.
+      //
+      if (!satisfactory (av))
+        continue;
+
+      if (orphan_best_match)
+      {
+        if (av == *dov)
+        {
+          r = move (af);
+          break;
+        }
+
+        if (deorphan_latest_iteration.first == nullptr &&
+            av.compare (*dov, false /* revision */, true /* iteration */) == 0)
+          deorphan_latest_iteration = af;
+
+        if (deorphan_later_revision.first == nullptr    &&
+            av.compare (*dov, true /* revision */) == 0 &&
+            av.compare (*dov, false /* revision */, true /* iteration */) > 0)
+          deorphan_later_revision = af;
+
+        if (deorphan_later_patch.first == nullptr &&
+            dopc && satisfies (av, *dopc)         &&
+            av.compare (*dov, true /* revision */) > 0) // Patch is greater?
+          deorphan_later_patch = af;
+
+        if (deorphan_later_minor.first == nullptr      &&
+            domc && satisfies (av, *domc)              &&
+            av.compare (*dov, true /* revision */) > 0 &&
+            deorphan_later_patch.first == nullptr)
+          deorphan_later_minor = af;
+
+        if (deorphan_latest_available.first == nullptr)
+          deorphan_latest_available = move (af);
+
+        if (av.compare (*dov, false /* revision */, true /* iteration */) < 0)
+        {
+          assert (deorphan_latest_iteration.first != nullptr ||
+                  deorphan_later_revision.first != nullptr   ||
+                  deorphan_later_patch.first != nullptr      ||
+                  deorphan_later_minor.first != nullptr      ||
+                  deorphan_latest_available.first != nullptr);
+
+          break;
+        }
+      }
+      else
+      {
+        r = move (af);
+        break;
+      }
+    }
+
+    shared_ptr<available_package>& rap (r.first);
+
+    if (rap == nullptr && orphan_best_match)
+    {
+      if (deorphan_latest_iteration.first != nullptr)
+        r = move (deorphan_latest_iteration);
+      else if (deorphan_later_revision.first != nullptr)
+        r = move (deorphan_later_revision);
+      else if (deorphan_later_patch.first != nullptr)
+        r = move (deorphan_later_patch);
+      else if (deorphan_later_minor.first != nullptr)
+        r = move (deorphan_later_minor);
+      else if (deorphan_latest_available.first != nullptr)
+        r = move (deorphan_latest_available);
+    }
+
+    t.commit ();
+
+    if (rap == nullptr)
+      return false;
+
+    // Now, as the replacement is found, punch the respective spec to the
+    // command line.
+    //
+    lazy_shared_ptr<repository_fragment>& raf (r.second);
+
+    // Should we use a different special name for the package specs we
+    // amend/add? Probably that would only make sense if some diagnostics
+    // becomes confusing. Let's wait and see and hopefully that won't be
+    // necessary.
+    //
+    package_version_key cmd_line (db.main_database (), "command line");
+
+    // If the package is present on the command line, then update its
+    // constraint, if present, and add the constraint otherwise. Otherwise,
+    // add the new package spec.
+    //
+    version_constraint vc (rap->version);
+
+    if (hold_pkg != nullptr || dep_pkg != nullptr)
+    {
+      if (hold_pkg != nullptr)
+      {
+        if (constraint != nullptr)
+        {
+          l4 ([&]{trace << "replace unsatisfactory package version "
+                        << p.available_name_version_db () << " with "
+                        << rap->version << " by overwriting constraint '"
+                        << nm << ' ' << *constraint << "' by '" << nm << ' '
+                        << vc << "' on command line";});
+        }
+        else
+        {
+          l4 ([&]{trace << "replace unsatisfactory package version "
+                        << p.available_name_version_db () << " with "
+                        << rap->version << " by overwriting spec '" << nm
+                        << "' by '" << nm << ' ' << vc << "' on command line";});
+
+          hold_pkg->constraints.emplace_back (move (vc),
+                                              cmd_line.db,
+                                              cmd_line.name.string ());
+        }
+
+        hold_pkg->available = move (rap);
+        hold_pkg->repository_fragment = move (raf);
+      }
+      else // dep_pkg != nullptr
+      {
+        if (constraint != nullptr)
+        {
+          l4 ([&]{trace << "replace unsatisfactory package version "
+                        << p.available_name_version_db () << " with "
+                        << rap->version << " by overwriting constraint '?"
+                        << nm << ' ' << *constraint << "' by '?" << nm << ' '
+                        << vc << "' on command line";});
+        }
+        else
+        {
+          // It feels like this case may never happen, since for a dependency
+          // specified without version constraint on the command line the
+          // dependency evaluation machinery will pick the best available
+          // version in pretty much the same way as we do in this
+          // function. This is in contrast to a dependency specified with a
+          // version constraint which will not be upgraded if the configured
+          // dependency satisfies this constraint (see evaluate_dependency()
+          // for details). Let's, however, handle this case, for good measure.
+          //
+          dep_pkg->constraint = move (vc);
+        }
+      }
+
+      if (constraint != nullptr)
+        *constraint = move (vc);
+    }
+    else // The package is not specified on the command line.
+    {
+      // If the package is configured as system, then since it is not
+      // specified by the user (both hold_pkg and dep_pkg are NULL) we may
+      // only build it as system. Thus we wouldn't be here (see above).
+      //
+      assert (sp == nullptr || !sp->system ());
+
+      // Similar to the collect lambda in collect_build_prerequisites(), issue
+      // the warning if we are forcing an up/down-grade.
+      //
+      if (sp != nullptr && (sp->hold_package || verb >= 2))
+      {
+        const version& av (rap->version);
+        const version& sv (sp->version);
+
+        int ud (sv.compare (av));
+
+        if (ud != 0)
+        {
+          for (const auto& c: p.constraints)
+          {
+            if (c.dependent.version && !satisfies (sv, c.value))
+            {
+              warn << "package " << c.dependent << " dependency on ("
+                   << nm << ' ' << c.value << ") is forcing "
+                   << (ud < 0 ? "up" : "down") << "grade of " << *sp << db
+                   << " to " << av;
+
+              break;
+            }
+          }
+        }
+      }
+
+      // For the selected built-to-hold package create the build-to-hold
+      // package spec and the dependency spec otherwise.
+      //
+      if (sp != nullptr && sp->hold_package)
+      {
+        l4 ([&]{trace << "replace unsatisfactory package version "
+                      << p.available_name_version_db () << " with "
+                      << rap->version << " by adding package spec '" << nm
+                      << ' ' << vc << "' to command line";});
+
+        build_package hp {
+          build_package::build,
+          db,
+          sp,
+          move (rap),
+          move (raf),
+          nullopt,                    // Dependencies.
+          nullopt,                    // Dependencies alternatives.
+          nullopt,                    // Package skeleton.
+          nullopt,                    // Postponed dependency alternatives.
+          false,                      // Recursive collection.
+          true,                       // Hold package.
+          false,                      // Hold version.
+          {},                         // Constraints.
+          false,                      // System.
+          false,                      // Keep output directory.
+          false,                      // Disfigure (from-scratch reconf).
+          false,                      // Configure-only.
+          nullopt,                    // Checkout root.
+          false,                      // Checkout purge.
+          strings (),                 // Configuration variables.
+          p.upgrade,
+          p.deorphan,
+          {cmd_line},                 // Required by (command line).
+          false,                      // Required by dependents.
+          (p.deorphan
+           ? build_package::build_replace
+           : uint16_t (0))};
+
+        hp.constraints.emplace_back (move (vc),
+                                     cmd_line.db,
+                                     cmd_line.name.string ());
+
+        hold_pkgs.push_back (move (hp));
+      }
+      else
+      {
+        l4 ([&]{trace << "replace unsatisfactory package version "
+                      << p.available_name_version_db () << " with "
+                      << rap->version << " by adding package spec '?" << nm
+                      << ' ' << vc << "' to command line";});
+
+        dep_pkgs.push_back (
+          dependency_package {&db,
+                              nm,
+                              move (vc),
+                              false /* hold_version */,
+                              sp,
+                              false /* system */,
+                              false /* existing */,
+                              p.upgrade,
+                              p.deorphan,
+                              false /* keep_out */,
+                              false /* disfigure */,
+                              nullopt /* checkout_root */,
+                              false /* checkout_purge */,
+                              strings () /* config_vars */,
+                              nullptr /* system_status */});
+      }
+    }
+
+    return true;
+  }
+
   // Return false if the plan execution was noop. If unsatisfied dependents
   // are specified then we are in the simulation mode.
   //
@@ -3387,10 +4009,13 @@ namespace bpkg
             pkg_confs.emplace_back (*pdb, pa.name);
           }
 
+          bool hold_version (pa.constraint.has_value ());
+
           dep_pkgs.push_back (
             dependency_package {pdb,
                                 move (pa.name),
                                 move (pa.constraint),
+                                hold_version,
                                 move (sp),
                                 sys,
                                 existing,
@@ -3587,6 +4212,12 @@ namespace bpkg
 
         // Finally add this package to the list.
         //
+        optional<bool> upgrade (sp != nullptr  &&
+                                !pa.constraint &&
+                                (pa.options.upgrade () || pa.options.patch ())
+                                ? pa.options.upgrade ()
+                                : optional<bool> ());
+
         // @@ Pass pa.configure_only() when support for package-specific
         //    --configure-only is added.
         //
@@ -3613,6 +4244,8 @@ namespace bpkg
            : optional<dir_path> ()),
           pa.options.checkout_purge (),
           move (pa.config_vars),
+          upgrade,
+          deorphan,
           {cmd_line},                 // Required by (command line).
           false,                      // Required by dependents.
           replace ? build_package::build_replace : uint16_t (0)};
@@ -3726,28 +4359,32 @@ namespace bpkg
             //
             build_package p {
               build_package::build,
-                cdb,
-                move (sp),
-                move (ap),
-                move (apr.second),
-                nullopt,                 // Dependencies.
-                nullopt,                 // Dependencies alternatives.
-                nullopt,                 // Package skeleton.
-                nullopt,                 // Postponed dependency alternatives.
-                false,                   // Recursive collection.
-                true,                    // Hold package.
-                false,                   // Hold version.
-                {},                      // Constraints.
-                false,                   // System package.
-                keep_out,
-                o.disfigure (),
-                false,                   // Configure-only.
-                nullopt,                 // Checkout root.
-                false,                   // Checkout purge.
-                strings (),              // Configuration variables.
-                {cmd_line},              // Required by (command line).
-                false,                   // Required by dependents.
-                deorphan ? build_package::build_replace : uint16_t (0)};
+              cdb,
+              move (sp),
+              move (ap),
+              move (apr.second),
+              nullopt,                      // Dependencies.
+              nullopt,                      // Dependencies alternatives.
+              nullopt,                      // Package skeleton.
+              nullopt,                      // Postponed dependency alternatives.
+              false,                        // Recursive collection.
+              true,                         // Hold package.
+              false,                        // Hold version.
+              {},                           // Constraints.
+              false,                        // System package.
+              keep_out,
+              o.disfigure (),
+              false,                        // Configure-only.
+              nullopt,                      // Checkout root.
+              false,                        // Checkout purge.
+              strings (),                   // Configuration variables.
+              (o.upgrade () || o.patch ()
+               ? o.upgrade ()
+               : optional<bool> ()),
+              deorphan,
+              {cmd_line},                   // Required by (command line).
+              false,                        // Required by dependents.
+              deorphan ? build_package::build_replace : uint16_t (0)};
 
             l4 ([&]{trace << "stash held package "
                           << p.available_name_version_db ();});
@@ -3890,9 +4527,10 @@ namespace bpkg
         shared_ptr<available_package>              available;
         lazy_shared_ptr<bpkg::repository_fragment> repository_fragment;
 
-        bool system;
-        bool existing; // Build as an existing archive or directory.
-        bool deorphan;
+        bool           system;
+        bool           existing; // Build as an existing archive or directory.
+        optional<bool> upgrade;
+        bool           deorphan;
       };
       vector<dep> deps;
       existing_dependencies   existing_deps;
@@ -4089,6 +4727,14 @@ namespace bpkg
         auto enter = [&pkgs, &cmd_line] (database& db,
                                          const dependency_package& p)
         {
+          // Note that we don't set the upgrade and deorphan flags based on
+          // the --upgrade, --patch, and --deorphan options since an option
+          // presense doesn't necessarily means that the respective flag needs
+          // to be set (the package may not be selected, may not be patchable
+          // and/or an orphan, etc). The proper flags will be provided by
+          // evaluate_dependency() if/when any upgrade/deorphan recommendation
+          // is given.
+          //
           build_package bp {
             nullopt,                    // Action.
             db,
@@ -4101,7 +4747,7 @@ namespace bpkg
             nullopt,                    // Postponed dependency alternatives.
             false,                      // Recursive collection.
             false,                      // Hold package.
-            p.constraint.has_value (),  // Hold version.
+            p.hold_version,
             {},                         // Constraints.
             p.system,
             p.keep_out,
@@ -4110,6 +4756,8 @@ namespace bpkg
             p.checkout_root,
             p.checkout_purge,
             p.config_vars,
+            nullopt,                    // Upgrade.
+            false,                      // Deorphan.
             {cmd_line},                 // Required by (command line).
             false,                      // Required by dependents.
             0};                         // State flags.
@@ -4411,6 +5059,8 @@ namespace bpkg
                 nullopt,                 // Checkout root.
                 false,                   // Checkout purge.
                 strings (),              // Configuration variables.
+                d.upgrade,
+                d.deorphan,
                 {cmd_line},              // Required by (command line).
                 false,                   // Required by dependents.
                 (d.existing || d.deorphan
@@ -4933,6 +5583,7 @@ namespace bpkg
                                          move (er->repository_fragment),
                                          er->system,
                                          er->existing,
+                                         er->upgrade,
                                          er->orphan.has_value ()});
 
                     if (er->existing)
@@ -5352,11 +6003,49 @@ namespace bpkg
         }
 
         // Issue diagnostics and fail if the execution plan is finalized and
-        // any existing dependents are not satisfied with their
-        // dependencies.
+        // any existing dependents are not satisfied with their dependencies.
+        //
+        // But first, try to resolve the first encountered unsatisfied
+        // constraint by replacing the collected unsatisfactory dependency
+        // with some other available package version which, while not being
+        // the best possible choice, is satisfactory for all the new and
+        // existing dependents. If succeed, punch the replacement version into
+        // the command line and recollect from the very beginning. Note that
+        // at the moment there is no backtracking and so the once selected
+        // package version may not be reconsidered.
+        //
+        // @@ What if a new dependent appears after the recollection for which
+        //    the new dependency is also unsatisfactory and which we could
+        //    solve by picking yet another different version? We could
+        //    probably support this by marking this entry as amenable to
+        //    change. But we will also need to keep track of what we have
+        //    tried before in order not to yo-yo.
         //
         if (!refine && !unsatisfied_depts.empty ())
+        {
+          const unsatisfied_dependent& dpt (unsatisfied_depts.front ());
+
+          assert (!dpt.ignored_constraints.empty ());
+
+          const ignored_constraint& ic (dpt.ignored_constraints.front ());
+
+          const build_package* p (pkgs.entered_build (ic.dependency));
+          assert (p != nullptr); // The dependency must be collected.
+
+          if (try_replace_dependency (o, *p, pkgs, hold_pkgs, dep_pkgs))
+          {
+            refine = true;
+            scratch_exe = true;
+
+            deps.clear ();
+            existing_deps.clear ();
+            deorphaned_deps.clear ();
+
+            continue;
+          }
+
           unsatisfied_depts.diag (pkgs);
+        }
       }
     }
 
diff --git a/tests/pkg-build.testscript b/tests/pkg-build.testscript
index bc435f2..b982734 100644
--- a/tests/pkg-build.testscript
+++ b/tests/pkg-build.testscript
@@ -1352,17 +1352,17 @@ test.arguments += --sys-no-query
 
       : unable-satisfy-dependency
       :
-      : As above but specify libfoo as a dependency.
+      : Similar to the above, but specify libfoo as a dependency.
       :
       {
         $clone_cfg;
 
-        $* libbar ?libfoo/1.0.0 2>>EOE != 0
-          error: unable to satisfy constraints on package libfoo
-            info: libbar depends on (libfoo == 1.1.0)
-            info: command line depends on (libfoo == 1.0.0)
-            info: specify libfoo version to satisfy libbar constraint
-          info: while satisfying libbar/1.1.0
+        # Add libbaz, so that libfoo package is available from its dependents
+        # (libbaz) repositories.
+        #
+        $* libbar ?libfoo/1.0.0 libbaz 2>>EOE != 0
+          error: package libfoo doesn't satisfy its dependents
+            info: libfoo/1.0.0 doesn't satisfy libbar/1.1.0
           EOE
       }
     }
@@ -2658,9 +2658,12 @@ test.arguments += --sys-no-query
       %error: package sys:libhello/2\.0 is not found in .+t0a%
       EOE
 
-    $* libfoo '?sys:libhello/0.1' 2>>~%EOE% != 0;
+    $* libfoo '?sys:libhello/0.1' 2>>EOE != 0;
       error: unable to satisfy constraints on package libhello
-      %.+
+        info: libfoo depends on (libhello >= 1.0)
+        info: command line depends on (libhello == 0.1)
+        info: specify libhello version to satisfy libfoo constraint
+      info: while satisfying libfoo/1.1.0
       EOE
 
     $* libfoo '?sys:libhello/*' 2>>~%EOE%;
@@ -2881,22 +2884,33 @@ test.arguments += --sys-no-query
       $clone_root_cfg;
       $rep_fetch $rep/t0a $rep/t0b;
 
+      # Note that before we have implemented the unsatisfied constraints
+      # resolution this command has failed as follows:
+      #
+      # error: unable to satisfy constraints on package libbaz
+      #   info: libbar depends on (libbaz == 0.0.1)
+      #           command line requires (libbar == 0.0.1)
+      #   info: command line depends on (libbaz == 0.0.2)
+      #   info: specify libbaz version to satisfy libbar constraint
+      # info: while satisfying libbar/0.0.1
+      #
       $* libbar/0.0.1 ?libbaz/0.0.2 2>>EOE != 0;
-        error: unable to satisfy constraints on package libbaz
-          info: libbar depends on (libbaz == 0.0.1)
-                  command line requires (libbar == 0.0.1)
-          info: command line depends on (libbaz == 0.0.2)
-          info: specify libbaz version to satisfy libbar constraint
-        info: while satisfying libbar/0.0.1
+        error: libbaz/0.0.2 is not available from its dependents' repositories
         EOE
 
+      # Note that before we have implemented the unsatisfied constraints
+      # resolution this command has failed as follows:
+      #
+      # error: unable to satisfy constraints on package libbaz
+      #   info: libbar depends on (libbaz == 0.0.1)
+      #           command line requires (libbar == 0.0.1)
+      #   info: command line depends on (libbaz >= 0.0.2)
+      #   info: specify libbaz version to satisfy libbar constraint
+      # info: while satisfying libbar/0.0.1
+      #
       $* -- libbar/0.0.1 '?libbaz>=0.0.2' 2>>EOE != 0
-        error: unable to satisfy constraints on package libbaz
-          info: libbar depends on (libbaz == 0.0.1)
-                  command line requires (libbar == 0.0.1)
-          info: command line depends on (libbaz >= 0.0.2)
-          info: specify libbaz version to satisfy libbar constraint
-        info: while satisfying libbar/0.0.1
+        error: package libbaz doesn't satisfy its dependents
+          info: libbaz/0.0.3 doesn't satisfy libbar/0.0.1
         EOE
     }
 
@@ -2907,39 +2921,59 @@ test.arguments += --sys-no-query
       :
       : Test resolving a conflict when libfix and libbiz have selected such
       : versions of their dependency libbaz, that do not satisfy each other
-      : constraints. We resolve the conflict explicitly specifying
+      : constraints. We resolve the conflict automatically as if by specifying
       : ?libbaz/0.0.3 on the command line, which satisfies both constraints.
       :
       {
         $clone_root_cfg;
         $rep_fetch $rep/t0b $rep/t0c;
 
-        $* libfix libbiz 2>>EOE != 0;
-          error: unable to satisfy constraints on package libbaz
-            info: libfix/0.0.3 depends on (libbaz >= 0.0.3)
-            info: libbiz/0.0.2 depends on (libbaz <= 0.0.3)
-            info: available libbaz/0.1.0
-            info: available libbaz/0.0.2
-            info: while satisfying libbiz/0.0.2
-            info: explicitly specify libbaz version to manually satisfy both constraints
-          EOE
-
-        $* libfix libbiz ?libbaz/0.0.3 2>>EOE;
-          fetched libfoo/1.0.0
-          unpacked libfoo/1.0.0
-          fetched libbaz/0.0.3
-          unpacked libbaz/0.0.3
-          fetched libfix/0.0.3
-          unpacked libfix/0.0.3
-          fetched libbiz/0.0.2
-          unpacked libbiz/0.0.2
-          configured libfoo/1.0.0
-          configured libbaz/0.0.3
-          configured libfix/0.0.3
-          configured libbiz/0.0.2
+        $* libfix libbiz --plan '' --verbose 5 2>>~%EOE%;
+          %.*
+          trace: pkg_build: refine package collection/plan execution from scratch
+          trace: collect_build: add libfix/0.0.3
+          trace: collect_build: add libbiz/0.0.2
+          trace: collect_build_prerequisites: begin libfix/0.0.3
+          trace: collect_build: add libbaz/0.1.0
+          trace: collect_build_prerequisites: no cfg-clause for dependency libbaz/0.1.0 of dependent libfix/0.0.3
+          trace: collect_build_prerequisites: begin libbaz/0.1.0
+          trace: collect_build_prerequisites: end libbaz/0.1.0
+          trace: collect_build_prerequisites: end libfix/0.0.3
+          trace: collect_build_prerequisites: begin libbiz/0.0.2
+          trace: collect_build: postpone failure for dependent libbiz unsatisfied with dependency libbaz/0.1.0 (<= 0.0.3)
+          trace: collect_build: pick libbaz/0.1.0 over libbaz/0.0.2
+          trace: collect_build_prerequisites: no cfg-clause for dependency libbaz/0.1.0 of dependent libbiz/0.0.2
+          trace: collect_build_prerequisites: end libbiz/0.0.2
+          trace: execute_plan: simulate: yes
+          %.*
+          trace: try_replace_dependency: replace unsatisfactory package version libbaz/0.1.0 with 0.0.3 by adding package spec '?libbaz == 0.0.3' to command line
+          trace: pkg_build: refine package collection/plan execution from scratch
+          trace: collect_build: add libfix/0.0.3
+          trace: collect_build: add libbiz/0.0.2
+          trace: collect_build_prerequisites: begin libfix/0.0.3
+          trace: collect_build_prerequisites: no cfg-clause for dependency libbaz/0.0.3 of dependent libfix/0.0.3
+          trace: collect_build_prerequisites: begin libbaz/0.0.3
+          trace: collect_build: add libfoo/1.0.0
+          trace: collect_build_prerequisites: no cfg-clause for dependency libfoo/1.0.0 of dependent libbaz/0.0.3
+          trace: collect_build_prerequisites: begin libfoo/1.0.0
+          trace: collect_build_prerequisites: end libfoo/1.0.0
+          trace: collect_build_prerequisites: end libbaz/0.0.3
+          trace: collect_build_prerequisites: end libfix/0.0.3
+          trace: collect_build_prerequisites: begin libbiz/0.0.2
+          trace: collect_build: pick libbaz/0.0.3 over libbaz/0.0.2
+          trace: collect_build_prerequisites: no cfg-clause for dependency libbaz/0.0.3 of dependent libbiz/0.0.2
+          trace: collect_build_prerequisites: end libbiz/0.0.2
+          trace: execute_plan: simulate: yes
+          %.*
+            new libfoo/1.0.0 (required by libbaz)
+            new libbaz/0.0.3 (required by libbiz, libfix)
+            new libfix/0.0.3
+            new libbiz/0.0.2
+          trace: execute_plan: simulate: no
+          %.*
           EOE
 
-        $pkg_status libbaz >'libbaz configured !0.0.3 available 0.1.0 0.0.4';
+        $pkg_status libbaz >'libbaz configured 0.0.3 available 0.1.0 0.0.4';
 
         $pkg_drop libbiz libfix
       }
@@ -3624,12 +3658,9 @@ test.arguments += --sys-no-query
 
         $pkg_status libbaz >'libbaz configured 0.0.1 available 0.1.0 0.0.4 0.0.3';
 
-        $* ?libbaz/0.0.3 +{ --config-id 1 } 2>>EOE != 0;
-          error: unable to satisfy constraints on package libbaz
-            info: libbar depends on (libbaz == 0.0.1)
-            info: command line depends on (libbaz == 0.0.3)
-            info: specify libbaz version to satisfy libbar constraint
-          info: while satisfying libbar/0.0.1
+        $* ?libbaz/0.0.3 +{ --config-id 1 } 2>>~%EOE% != 0;
+          %error: package libbaz \[cfg2.\] doesn't satisfy its dependents%
+            info: libbaz/0.0.3 doesn't satisfy libbar/0.0.1
           EOE
 
         $pkg_status libbaz >'libbaz configured 0.0.1 available 0.1.0 0.0.4 0.0.3';
@@ -4199,474 +4230,909 @@ test.arguments += --sys-no-query
       +$clone_root_cfg
       +$rep_add $rep/t4f && $rep_fetch
 
+      test.arguments += --plan "" --verbose 5
+
       : replace-dependent
       :
-      : This test demonstrates a case when the dependency resolution machinery
-      : fails to resolve unsatisfied dependency constraints by replacing an
-      : unsatisfied dependent version with a satisfied one.
-      :
       {
-        $clone_cfg;
+        +$clone_cfg
 
-        $* libfoo libfix --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libfoo/2.0.0
-          trace: collect_build: add libfix/1.0.0
-          trace: collect_build_prerequisites: begin libfoo/2.0.0
-          trace: collect_build: add libbar/1.2.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfoo/2.0.0
-          trace: collect_build_prerequisites: begin libbar/1.2.0
-          trace: collect_build_prerequisites: end libbar/1.2.0
-          trace: collect_build_prerequisites: end libfoo/2.0.0
-          trace: collect_build_prerequisites: begin libfix/1.0.0
-          trace: collect_build: add libfox/2.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libfox/2.0.0 of dependent libfix/1.0.0
-          trace: collect_build_prerequisites: begin libfox/2.0.0
-          trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/1.2.0 (>= 2.0.0)
-          trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/2.0.0
-          trace: collect_build_prerequisites: end libfox/2.0.0
-          trace: collect_build_prerequisites: end libfix/1.0.0
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to satisfy constraints on package libbar
-            info: libfox/2.0.0 depends on (libbar >= 2.0.0)
-            info: libfoo/2.0.0 depends on (libbar == 1.2.0)
-            info: available libbar/2.1.0
-            info: available libbar/1.2.0
-            info: while satisfying libfox/2.0.0
-            info: while satisfying libfix/1.0.0
-            info: explicitly specify libbar version to manually satisfy both constraints
-          %.*
-          EOE
+        : basics
+        :
+        : This test demonstrates a case when the dependency resolution machinery
+        : fails to resolve unsatisfied dependency constraints by replacing an
+        : unsatisfied dependent version with a satisfied one.
+        :
+        {
+          $clone_cfg;
 
-        $* libfoo libfix ?libfox/1.1.0 2>>EOE;
-          fetched libbar/1.2.0
-          unpacked libbar/1.2.0
-          fetched libfoo/2.0.0
-          unpacked libfoo/2.0.0
-          fetched libfox/1.1.0
-          unpacked libfox/1.1.0
-          fetched libfix/1.0.0
-          unpacked libfix/1.0.0
-          configured libbar/1.2.0
-          configured libfoo/2.0.0
-          configured libfox/1.1.0
-          configured libfix/1.0.0
-          EOE
+          $* libfoo libfix 2>>~%EOE% != 0;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfoo/2.0.0
+            trace: collect_build: add libfix/1.0.0
+            trace: collect_build_prerequisites: begin libfoo/2.0.0
+            trace: collect_build: add libbar/1.2.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfoo/2.0.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libfoo/2.0.0
+            trace: collect_build_prerequisites: begin libfix/1.0.0
+            trace: collect_build: add libfox/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libfox/2.0.0 of dependent libfix/1.0.0
+            trace: collect_build_prerequisites: begin libfox/2.0.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/1.2.0 (>= 2.0.0)
+            trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/2.0.0
+            trace: collect_build_prerequisites: end libfox/2.0.0
+            trace: collect_build_prerequisites: end libfix/1.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            error: unable to satisfy constraints on package libbar
+              info: libfox/2.0.0 depends on (libbar >= 2.0.0)
+              info: libfoo/2.0.0 depends on (libbar == 1.2.0)
+              info: available libbar/2.1.0
+              info: available libbar/1.2.0
+              info: while satisfying libfox/2.0.0
+              info: while satisfying libfix/1.0.0
+              info: explicitly specify libbar version to manually satisfy both constraints
+            %.*
+            EOE
 
-        $pkg_status -ar >>EOO;
-          libbar configured 1.2.0 available 2.1.0
-          !libfoo configured 2.0.0
-            libbar configured 1.2.0 available 2.1.0
-          libfox configured !1.1.0 available 2.0.0
+          $* libfoo libfix ?libfox/1.1.0 --verbose 1 2>>EOE;
+              new libbar/1.2.0 (required by libfoo, libfox)
+              new libfoo/2.0.0
+              new libfox/1.1.0 (required by libfix)
+              new libfix/1.0.0
+            fetched libbar/1.2.0
+            unpacked libbar/1.2.0
+            fetched libfoo/2.0.0
+            unpacked libfoo/2.0.0
+            fetched libfox/1.1.0
+            unpacked libfox/1.1.0
+            fetched libfix/1.0.0
+            unpacked libfix/1.0.0
+            configured libbar/1.2.0
+            configured libfoo/2.0.0
+            configured libfox/1.1.0
+            configured libfix/1.0.0
+            EOE
+
+          $pkg_status -ar >>EOO;
             libbar configured 1.2.0 available 2.1.0
-          !libfix configured 1.0.0
+            !libfoo configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
             libfox configured !1.1.0 available 2.0.0
               libbar configured 1.2.0 available 2.1.0
-          EOO
+            !libfix configured 1.0.0
+              libfox configured !1.1.0 available 2.0.0
+                libbar configured 1.2.0 available 2.1.0
+            EOO
 
-        $pkg_drop libfoo libfix
-      }
+          $pkg_drop libfoo libfix
+        }
 
-      : replace-dependent-reorder
-      :
-      : Similar to the above, but the unsatisfied dependent which needs to be
-      : replaced differs from the one added to the unsatisfied dependents list.
-      :
-      {
-        $clone_cfg;
+        : reorder
+        :
+        : Similar to the above, but the unsatisfied dependent which needs to be
+        : replaced differs from the one added to the unsatisfied dependents list.
+        :
+        {
+          $clone_cfg;
 
-        $* libfix libfoo --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libfix/1.0.0
-          trace: collect_build: add libfoo/2.0.0
-          trace: collect_build_prerequisites: begin libfix/1.0.0
-          trace: collect_build: add libfox/2.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libfox/2.0.0 of dependent libfix/1.0.0
-          trace: collect_build_prerequisites: begin libfox/2.0.0
-          trace: collect_build: add libbar/2.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/2.0.0
-          trace: collect_build_prerequisites: begin libbar/2.1.0
-          trace: collect_build: add libbox/2.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
-          trace: collect_build_prerequisites: begin libbox/2.0.0
-          trace: collect_build: add libbax/1.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
-          trace: collect_build_prerequisites: begin libbax/1.0.0
-          trace: collect_build_prerequisites: end libbax/1.0.0
-          trace: collect_build_prerequisites: end libbox/2.0.0
-          trace: collect_build_prerequisites: end libbar/2.1.0
-          trace: collect_build_prerequisites: end libfox/2.0.0
-          trace: collect_build_prerequisites: end libfix/1.0.0
-          trace: collect_build_prerequisites: begin libfoo/2.0.0
-          trace: collect_build: postpone failure for dependent libfoo unsatisfied with dependency libbar/2.1.0 (== 1.2.0)
-          trace: collect_build: pick libbar/2.1.0 over libbar/1.2.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfoo/2.0.0
-          trace: collect_build_prerequisites: end libfoo/2.0.0
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to satisfy constraints on package libbar
-            info: libfox/2.0.0 depends on (libbar >= 2.0.0)
-            info: libfoo/2.0.0 depends on (libbar == 1.2.0)
-            info: available libbar/2.1.0
-            info: available libbar/1.2.0
-            info: while satisfying libfoo/2.0.0
-            info: explicitly specify libbar version to manually satisfy both constraints
-          %.*
-          EOE
+          $* libfix libfoo 2>>~%EOE% != 0;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfix/1.0.0
+            trace: collect_build: add libfoo/2.0.0
+            trace: collect_build_prerequisites: begin libfix/1.0.0
+            trace: collect_build: add libfox/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libfox/2.0.0 of dependent libfix/1.0.0
+            trace: collect_build_prerequisites: begin libfox/2.0.0
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/2.0.0
+            trace: collect_build_prerequisites: begin libbar/2.1.0
+            trace: collect_build: add libbox/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
+            trace: collect_build_prerequisites: begin libbox/2.0.0
+            trace: collect_build: add libbax/1.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
+            trace: collect_build_prerequisites: begin libbax/1.0.0
+            trace: collect_build_prerequisites: end libbax/1.0.0
+            trace: collect_build_prerequisites: end libbox/2.0.0
+            trace: collect_build_prerequisites: end libbar/2.1.0
+            trace: collect_build_prerequisites: end libfox/2.0.0
+            trace: collect_build_prerequisites: end libfix/1.0.0
+            trace: collect_build_prerequisites: begin libfoo/2.0.0
+            trace: collect_build: postpone failure for dependent libfoo unsatisfied with dependency libbar/2.1.0 (== 1.2.0)
+            trace: collect_build: pick libbar/2.1.0 over libbar/1.2.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfoo/2.0.0
+            trace: collect_build_prerequisites: end libfoo/2.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            error: unable to satisfy constraints on package libbar
+              info: libfox/2.0.0 depends on (libbar >= 2.0.0)
+              info: libfoo/2.0.0 depends on (libbar == 1.2.0)
+              info: available libbar/2.1.0
+              info: available libbar/1.2.0
+              info: while satisfying libfoo/2.0.0
+              info: explicitly specify libbar version to manually satisfy both constraints
+            %.*
+            EOE
 
-        $* libfix libfoo ?libfox/1.1.0 2>>EOE;
-          fetched libbar/1.2.0
-          unpacked libbar/1.2.0
-          fetched libfox/1.1.0
-          unpacked libfox/1.1.0
-          fetched libfix/1.0.0
-          unpacked libfix/1.0.0
-          fetched libfoo/2.0.0
-          unpacked libfoo/2.0.0
-          configured libbar/1.2.0
-          configured libfox/1.1.0
-          configured libfix/1.0.0
-          configured libfoo/2.0.0
-          EOE
+          $* libfix libfoo ?libfox/1.1.0 --verbose 1 2>>EOE;
+              new libbar/1.2.0 (required by libfoo, libfox)
+              new libfox/1.1.0 (required by libfix)
+              new libfix/1.0.0
+              new libfoo/2.0.0
+            fetched libbar/1.2.0
+            unpacked libbar/1.2.0
+            fetched libfox/1.1.0
+            unpacked libfox/1.1.0
+            fetched libfix/1.0.0
+            unpacked libfix/1.0.0
+            fetched libfoo/2.0.0
+            unpacked libfoo/2.0.0
+            configured libbar/1.2.0
+            configured libfox/1.1.0
+            configured libfix/1.0.0
+            configured libfoo/2.0.0
+            EOE
 
-        $pkg_status -ar >>EOO;
-          libbar configured 1.2.0 available 2.1.0
-          libfox configured !1.1.0 available 2.0.0
+          $pkg_status -ar >>EOO;
             libbar configured 1.2.0 available 2.1.0
-          !libfix configured 1.0.0
             libfox configured !1.1.0 available 2.0.0
               libbar configured 1.2.0 available 2.1.0
-          !libfoo configured 2.0.0
-            libbar configured 1.2.0 available 2.1.0
-          EOO
+            !libfix configured 1.0.0
+              libfox configured !1.1.0 available 2.0.0
+                libbar configured 1.2.0 available 2.1.0
+            !libfoo configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
 
-        $pkg_drop libfoo libfix
-      }
+          $pkg_drop libfoo libfix
+        }
 
-      : replace-dependent-to-hold
-      :
-      : Similar to the replace-dependent test, but the unsatisfied dependent
-      : is being built to hold rather than as a dependency.
-      :
-      {
-        $clone_cfg;
+        : to-hold
+        :
+        : Similar to the replace-dependent test, but the unsatisfied dependent
+        : is being built to hold rather than as a dependency.
+        :
+        {
+          $clone_cfg;
 
-        $* libfoo libfox --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libfoo/2.0.0
-          trace: collect_build: add libfox/2.0.0
-          trace: collect_build_prerequisites: begin libfoo/2.0.0
-          trace: collect_build: add libbar/1.2.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfoo/2.0.0
-          trace: collect_build_prerequisites: begin libbar/1.2.0
-          trace: collect_build_prerequisites: end libbar/1.2.0
-          trace: collect_build_prerequisites: end libfoo/2.0.0
-          trace: collect_build_prerequisites: begin libfox/2.0.0
-          trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/1.2.0 (>= 2.0.0)
-          trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/2.0.0
-          trace: collect_build_prerequisites: end libfox/2.0.0
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to satisfy constraints on package libbar
-            info: libfox/2.0.0 depends on (libbar >= 2.0.0)
-            info: libfoo/2.0.0 depends on (libbar == 1.2.0)
-            info: available libbar/2.1.0
-            info: available libbar/1.2.0
-            info: while satisfying libfox/2.0.0
-            info: explicitly specify libbar version to manually satisfy both constraints
-          %.*
-          EOE
+          $* libfoo libfox 2>>~%EOE% != 0;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfoo/2.0.0
+            trace: collect_build: add libfox/2.0.0
+            trace: collect_build_prerequisites: begin libfoo/2.0.0
+            trace: collect_build: add libbar/1.2.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfoo/2.0.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libfoo/2.0.0
+            trace: collect_build_prerequisites: begin libfox/2.0.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/1.2.0 (>= 2.0.0)
+            trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/2.0.0
+            trace: collect_build_prerequisites: end libfox/2.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            error: unable to satisfy constraints on package libbar
+              info: libfox/2.0.0 depends on (libbar >= 2.0.0)
+              info: libfoo/2.0.0 depends on (libbar == 1.2.0)
+              info: available libbar/2.1.0
+              info: available libbar/1.2.0
+              info: while satisfying libfox/2.0.0
+              info: explicitly specify libbar version to manually satisfy both constraints
+            %.*
+            EOE
 
-        $* libfoo libfox/1.1.0 2>>EOE;
-          fetched libbar/1.2.0
-          unpacked libbar/1.2.0
-          fetched libfoo/2.0.0
-          unpacked libfoo/2.0.0
-          fetched libfox/1.1.0
-          unpacked libfox/1.1.0
-          configured libbar/1.2.0
-          configured libfoo/2.0.0
-          configured libfox/1.1.0
-          EOE
+          $* libfoo libfox/1.1.0 --verbose 1 2>>EOE;
+              new libbar/1.2.0 (required by libfoo, libfox)
+              new libfoo/2.0.0
+              new libfox/1.1.0
+            fetched libbar/1.2.0
+            unpacked libbar/1.2.0
+            fetched libfoo/2.0.0
+            unpacked libfoo/2.0.0
+            fetched libfox/1.1.0
+            unpacked libfox/1.1.0
+            configured libbar/1.2.0
+            configured libfoo/2.0.0
+            configured libfox/1.1.0
+            EOE
 
-        $pkg_status -ar >>EOO;
-          libbar configured 1.2.0 available 2.1.0
-          !libfoo configured 2.0.0
+          $pkg_status -ar >>EOO;
             libbar configured 1.2.0 available 2.1.0
-          !libfox configured !1.1.0 available 2.0.0
+            !libfoo configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
+
+          $pkg_drop libfoo libfox
+        }
+
+        : to-hold-reorder
+        :
+        : Similar to the above, but the unsatisfied dependent which needs to be
+        : replaced differs from the one added to the unsatisfied dependents list.
+        :
+        {
+          $clone_cfg;
+
+          $* libfox libfoo 2>>~%EOE% != 0;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfox/2.0.0
+            trace: collect_build: add libfoo/2.0.0
+            trace: collect_build_prerequisites: begin libfox/2.0.0
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/2.0.0
+            trace: collect_build_prerequisites: begin libbar/2.1.0
+            trace: collect_build: add libbox/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
+            trace: collect_build_prerequisites: begin libbox/2.0.0
+            trace: collect_build: add libbax/1.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
+            trace: collect_build_prerequisites: begin libbax/1.0.0
+            trace: collect_build_prerequisites: end libbax/1.0.0
+            trace: collect_build_prerequisites: end libbox/2.0.0
+            trace: collect_build_prerequisites: end libbar/2.1.0
+            trace: collect_build_prerequisites: end libfox/2.0.0
+            trace: collect_build_prerequisites: begin libfoo/2.0.0
+            trace: collect_build: postpone failure for dependent libfoo unsatisfied with dependency libbar/2.1.0 (== 1.2.0)
+            trace: collect_build: pick libbar/2.1.0 over libbar/1.2.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfoo/2.0.0
+            trace: collect_build_prerequisites: end libfoo/2.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            error: unable to satisfy constraints on package libbar
+              info: libfox/2.0.0 depends on (libbar >= 2.0.0)
+              info: libfoo/2.0.0 depends on (libbar == 1.2.0)
+              info: available libbar/2.1.0
+              info: available libbar/1.2.0
+              info: while satisfying libfoo/2.0.0
+              info: explicitly specify libbar version to manually satisfy both constraints
+            %.*
+            EOE
+
+          $* libfox/1.1.0 libfoo --verbose 1 2>>EOE;
+              new libbar/1.2.0 (required by libfoo, libfox)
+              new libfox/1.1.0
+              new libfoo/2.0.0
+            fetched libbar/1.2.0
+            unpacked libbar/1.2.0
+            fetched libfox/1.1.0
+            unpacked libfox/1.1.0
+            fetched libfoo/2.0.0
+            unpacked libfoo/2.0.0
+            configured libbar/1.2.0
+            configured libfox/1.1.0
+            configured libfoo/2.0.0
+            EOE
+
+          $pkg_status -ar >>EOO;
             libbar configured 1.2.0 available 2.1.0
-          EOO
+            !libfox configured !1.1.0 available 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            !libfoo configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
 
-        $pkg_drop libfoo libfox
+          $pkg_drop libfoo libfox
+        }
+
+        : unsatisfied-dependent
+        :
+        : This test demonstrates a case when the dependency resolution machinery
+        : fails to complete successfully as noop.
+        :
+        : Note that there is no version constraints are specified on the command
+        : line, the request is to upgrade all packages to the latest possible
+        : versions, and thus noop in this case would be an appropriate outcome.
+        :
+        {
+          $clone_cfg;
+
+          $* libbox ?libbix/1.0.0 libbux 2>!;
+
+          $pkg_status -ar >>EOO;
+            libbax configured 1.0.0 available 2.0.0
+            !libbox configured 2.0.0
+              libbax configured 1.0.0 available 2.0.0
+            libbix configured !1.0.0 available 2.0.0
+              libbax configured 1.0.0 available 2.0.0
+            !libbux configured 1.0.0
+              libbix configured !1.0.0 available 2.0.0
+                libbax configured 1.0.0 available 2.0.0
+            EOO
+
+          $* --upgrade --recursive 2>>~%EOE% != 0;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbox/2.0.0
+            trace: collect_build: add libbux/1.0.0
+            trace: collect_build_prerequisites: skip configured libbox/2.0.0
+            trace: collect_build_prerequisites: skip configured libbux/1.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: evaluate_dependency: libbix/1.0.0: update to libbix/2.0.0
+            %.*
+            trace: pkg_build: refine package collection/plan execution
+            trace: collect_build: add libbix/2.0.0
+            trace: collect_build_prerequisites: pre-reeval libbux/1.0.0
+            trace: collect_build_prerequisites: pre-reevaluated libbux/1.0.0: end reached
+            trace: collect_build_prerequisites: begin libbix/2.0.0
+            trace: collect_build: add libbax/2.0.0
+            info: package libbix dependency on (libbax == 2.0.0) is forcing upgrade of libbax/1.0.0 to 2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbax/2.0.0 of dependent libbix/2.0.0
+            trace: collect_build_prerequisites: skip unsatisfied existing dependent libbox of dependency libbax/2.0.0 due to constraint (libbax == 1.0.0)
+            trace: collect_build_prerequisites: skip being built existing dependent libbix of dependency libbax
+            trace: collect_build_prerequisites: begin libbax/2.0.0
+            trace: collect_build_prerequisites: end libbax/2.0.0
+            trace: collect_build_prerequisites: end libbix/2.0.0
+            trace: collect_dependents: postpone failure for existing dependent libbox unsatisfied with dependency libbax/2.0.0 (== 1.0.0)
+            trace: execute_plan: simulate: yes
+            %.*
+            error: unable to upgrade package libbax/1.0.0 to 2.0.0
+              info: because configured package libbox/2.0.0 depends on (libbax == 1.0.0)
+              info: package libbax/2.0.0 required by
+                      libbix/2.0.0 (libbax == 2.0.0)
+              info: consider re-trying with --upgrade|-u potentially combined with --recursive|-r
+              info: or explicitly request up/downgrade of package libbox
+              info: or explicitly specify package libbax version to manually satisfy these constraints
+            %.*
+            EOE
+
+          $pkg_drop libbox libbux
+        }
       }
 
-      : replace-dependent-to-hold-reorder
-      :
-      : Similar to the above, but the unsatisfied dependent which needs to be
-      : replaced differs from the one added to the unsatisfied dependents list.
+      : replace-dependency
       :
       {
-        $clone_cfg;
+        +$clone_cfg
+        +$rep_add $rep/t4i && $rep_fetch
 
-        $* libfox libfoo --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libfox/2.0.0
-          trace: collect_build: add libfoo/2.0.0
-          trace: collect_build_prerequisites: begin libfox/2.0.0
-          trace: collect_build: add libbar/2.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/2.0.0
-          trace: collect_build_prerequisites: begin libbar/2.1.0
-          trace: collect_build: add libbox/2.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
-          trace: collect_build_prerequisites: begin libbox/2.0.0
-          trace: collect_build: add libbax/1.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
-          trace: collect_build_prerequisites: begin libbax/1.0.0
-          trace: collect_build_prerequisites: end libbax/1.0.0
-          trace: collect_build_prerequisites: end libbox/2.0.0
-          trace: collect_build_prerequisites: end libbar/2.1.0
-          trace: collect_build_prerequisites: end libfox/2.0.0
-          trace: collect_build_prerequisites: begin libfoo/2.0.0
-          trace: collect_build: postpone failure for dependent libfoo unsatisfied with dependency libbar/2.1.0 (== 1.2.0)
-          trace: collect_build: pick libbar/2.1.0 over libbar/1.2.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfoo/2.0.0
-          trace: collect_build_prerequisites: end libfoo/2.0.0
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to satisfy constraints on package libbar
-            info: libfox/2.0.0 depends on (libbar >= 2.0.0)
-            info: libfoo/2.0.0 depends on (libbar == 1.2.0)
-            info: available libbar/2.1.0
-            info: available libbar/1.2.0
-            info: while satisfying libfoo/2.0.0
-            info: explicitly specify libbar version to manually satisfy both constraints
-          %.*
-          EOE
+        : basics
+        :
+        : This test demonstrates a case when the dependency resolution machinery
+        : resolves unsatisfied dependency constraints by adding the package spec
+        : to the command line for an unsatisfactory dependency version.
+        :
+        {
+          $clone_cfg;
 
-        $* libfox/1.1.0 libfoo 2>>EOE;
-          fetched libbar/1.2.0
-          unpacked libbar/1.2.0
-          fetched libfox/1.1.0
-          unpacked libfox/1.1.0
-          fetched libfoo/2.0.0
-          unpacked libfoo/2.0.0
-          configured libbar/1.2.0
-          configured libfox/1.1.0
-          configured libfoo/2.0.0
-          EOE
+          $* libfox/1.1.0 libbaz 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbar/2.1.0
+            trace: collect_build: add libbox/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
+            trace: collect_build_prerequisites: begin libbox/2.0.0
+            trace: collect_build: add libbax/1.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
+            trace: collect_build_prerequisites: begin libbax/1.0.0
+            trace: collect_build_prerequisites: end libbax/1.0.0
+            trace: collect_build_prerequisites: end libbox/2.0.0
+            trace: collect_build_prerequisites: end libbar/2.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: postpone failure for dependent libbaz unsatisfied with dependency libbar/2.1.0 (< 2.1.0)
+            trace: collect_build: pick libbar/2.1.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/2.1.0 with 1.2.0 by adding package spec '?libbar == 1.2.0' to command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
 
-        $pkg_status -ar >>EOO;
-          libbar configured 1.2.0 available 2.1.0
-          !libfox configured !1.1.0 available 2.0.0
+          $pkg_status -ar >>EOO;
             libbar configured 1.2.0 available 2.1.0
-          !libfoo configured 2.0.0
+            !libfox configured !1.1.0 available 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            !libbaz configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
+
+          $pkg_drop libfox libbaz
+        }
+
+        : reorder
+        :
+        : Similar to the above, but the order of the dependents on the command
+        : line is swapped.
+        :
+        {
+          $clone_cfg;
+
+          $* libbaz libfox/1.1.0 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: add libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/0.1.0 with 1.2.0 by adding package spec '?libbar == 1.2.0' to command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: rep-postpone dependent libbaz/2.0.0 due to dependency libbar < 2.1.0 and user-specified constraint == 1.2.0
+            trace: collect_build_prerequisites: postpone libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_postponed (0): begin
+            trace: collect_build_postponed (0): collect rep-postponed libbaz/2.0.0
+            trace: collect_build_prerequisites: resume libbaz/2.0.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_postponed (0): end
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
+
+          $pkg_status -ar >>EOO;
             libbar configured 1.2.0 available 2.1.0
-          EOO
+            !libbaz configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
 
-        $pkg_drop libfoo libfox
-      }
+          $pkg_drop libfox libbaz
+        }
 
-      : replace-dependency
-      :
-      : This test demonstrates a case when the dependency resolution machinery
-      : fails to resolve unsatisfied dependency constraints by replacing the
-      : unsatisfactory dependency versions with a satisfactory one.
-      :
-      {
-        $clone_cfg;
-        $rep_add $rep/t4i && $rep_fetch;
+        : dependency
+        :
+        : Similar to the above, but the dependency is also specified on the
+        : command line.
+        :
+        {
+          $clone_cfg;
 
-        $* libfox/1.1.0 libbaz --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libfox/1.1.0
-          trace: collect_build: add libbaz/2.0.0
-          trace: collect_build_prerequisites: begin libfox/1.1.0
-          trace: collect_build: add libbar/2.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/1.1.0
-          trace: collect_build_prerequisites: begin libbar/2.1.0
-          trace: collect_build: add libbox/2.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
-          trace: collect_build_prerequisites: begin libbox/2.0.0
-          trace: collect_build: add libbax/1.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
-          trace: collect_build_prerequisites: begin libbax/1.0.0
-          trace: collect_build_prerequisites: end libbax/1.0.0
-          trace: collect_build_prerequisites: end libbox/2.0.0
-          trace: collect_build_prerequisites: end libbar/2.1.0
-          trace: collect_build_prerequisites: end libfox/1.1.0
-          trace: collect_build_prerequisites: begin libbaz/2.0.0
-          trace: collect_build: postpone failure for dependent libbaz unsatisfied with dependency libbar/2.1.0 (< 2.1.0)
-          trace: collect_build: pick libbar/2.1.0 over libbar/0.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libbaz/2.0.0
-          trace: collect_build_prerequisites: end libbaz/2.0.0
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to satisfy constraints on package libbar
-            info: libfox/1.1.0 depends on (libbar >= 1.0.0)
-                    command line requires (libfox == 1.1.0)
-            info: libbaz/2.0.0 depends on (libbar < 2.1.0)
-            info: available libbar/2.1.0
-            info: available libbar/0.1.0
-            info: while satisfying libbaz/2.0.0
-            info: explicitly specify libbar version to manually satisfy both constraints
-          %.*
-          EOE
+          $* libbaz libfox/1.1.0 '?libbar' 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: evaluate_dependency: libbar/0.1.0: update to libbar/1.2.0
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build: libbar/0.1.0 package version needs to be replaced with libbar/1.2.0
+            trace: pkg_build: collection failed due to package version replacement, retry from scratch
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: apply version replacement for libbar/0.1.0
+            trace: collect_build: replacement: libbar/1.2.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: execute_plan: simulate: yes
+            %.*
+              new libbar/1.2.0 (required by libbaz, libfox)
+              new libbaz/2.0.0
+              new libfox/1.1.0
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
 
-        $* libfox/1.1.0 libbaz ?libbar/1.2.0 2>>EOE;
-          fetched libbar/1.2.0
-          unpacked libbar/1.2.0
-          fetched libfox/1.1.0
-          unpacked libfox/1.1.0
-          fetched libbaz/2.0.0
-          unpacked libbaz/2.0.0
-          configured libbar/1.2.0
-          configured libfox/1.1.0
-          configured libbaz/2.0.0
-          EOE
+          $pkg_status -ar >>EOO;
+            libbar configured 1.2.0 available 2.1.0
+            !libbaz configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
 
-        $pkg_status -ar >>EOO;
-          libbar configured !1.2.0 available 2.1.0
-          !libfox configured !1.1.0 available 2.0.0
-            libbar configured !1.2.0 available 2.1.0
-          !libbaz configured 2.0.0
+          $pkg_drop libfox libbaz libbar
+        }
+
+        : dependency-constr
+        :
+        : Similar to the above, but also specify the version constraint.
+        :
+        {
+          $clone_cfg;
+
+          $* libbaz libfox/1.1.0 '?libbar < 3.0.0' 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/0.1.0 with 1.2.0 by overwriting constraint '?libbar < 3.0.0' by '?libbar == 1.2.0' on command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: rep-postpone dependent libbaz/2.0.0 due to dependency libbar < 2.1.0 and user-specified constraint == 1.2.0
+            trace: collect_build_prerequisites: postpone libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_postponed (0): begin
+            trace: collect_build_postponed (0): collect rep-postponed libbaz/2.0.0
+            trace: collect_build_prerequisites: resume libbaz/2.0.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_postponed (0): end
+            trace: execute_plan: simulate: yes
+            %.*
+              new libbar/1.2.0 (required by libbaz, libfox)
+              new libbaz/2.0.0
+              new libfox/1.1.0
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
+
+          $pkg_status -ar >>EOO;
             libbar configured !1.2.0 available 2.1.0
-          EOO
+            !libbaz configured 2.0.0
+              libbar configured !1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              libbar configured !1.2.0 available 2.1.0
+            EOO
 
-        $pkg_drop libfox libbaz
-      }
+          $pkg_drop libfox libbaz libbar
+        }
 
-      : replace-dependency-reorder
-      :
-      : Similar to the above, but the order of the dependents on the command
-      : line is swapped.
-      :
-      {
-        $clone_cfg;
-        $rep_add $rep/t4i && $rep_fetch;
+        : to-hold
+        :
+        : Similar to the dependency test, but the dependency is specified as
+        : build-to-hold.
+        :
+        {
+          $clone_cfg;
 
-        $* libbaz libfox/1.1.0 --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libbaz/2.0.0
-          trace: collect_build: add libfox/1.1.0
-          trace: collect_build_prerequisites: begin libbaz/2.0.0
-          trace: collect_build: add libbar/0.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
-          trace: collect_build_prerequisites: begin libbar/0.1.0
-          trace: collect_build_prerequisites: end libbar/0.1.0
-          trace: collect_build_prerequisites: end libbaz/2.0.0
-          trace: collect_build_prerequisites: begin libfox/1.1.0
-          trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
-          trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
-          trace: collect_build_prerequisites: end libfox/1.1.0
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to satisfy constraints on package libbar
-            info: libfox/1.1.0 depends on (libbar >= 1.0.0)
-                    command line requires (libfox == 1.1.0)
-            info: libbaz/2.0.0 depends on (libbar < 2.1.0)
-            info: available libbar/2.1.0
-            info: available libbar/0.1.0
-            info: while satisfying libfox/1.1.0
-            info: explicitly specify libbar version to manually satisfy both constraints
-          %.*
-          EOE
+          $* libbaz libfox/1.1.0 libbar 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build: libbar/2.1.0 package version needs to be replaced with libbar/0.1.0
+            trace: pkg_build: collection failed due to package version replacement, retry from scratch
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: apply version replacement for libbar/2.1.0
+            trace: collect_build: replacement: libbar/0.1.0
+            trace: collect_build: add libbar/0.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: resume libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/0.1.0 with 1.2.0 by overwriting spec 'libbar' by 'libbar == 1.2.0' on command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbar/1.2.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: resume libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: execute_plan: simulate: yes
+            %.*
+              new libbar/1.2.0
+              new libbaz/2.0.0
+              new libfox/1.1.0
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
 
-        $* libfox/1.1.0 libbaz ?libbar/1.2.0 2>>EOE;
-          fetched libbar/1.2.0
-          unpacked libbar/1.2.0
-          fetched libfox/1.1.0
-          unpacked libfox/1.1.0
-          fetched libbaz/2.0.0
-          unpacked libbaz/2.0.0
-          configured libbar/1.2.0
-          configured libfox/1.1.0
-          configured libbaz/2.0.0
-          EOE
+          $pkg_status -ar >>EOO;
+            !libbar configured 1.2.0 available 2.1.0
+            !libbaz configured 2.0.0
+              !libbar configured 1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              !libbar configured 1.2.0 available 2.1.0
+            EOO
 
-        $pkg_status -ar >>EOO;
-          libbar configured !1.2.0 available 2.1.0
-          !libfox configured !1.1.0 available 2.0.0
-            libbar configured !1.2.0 available 2.1.0
-          !libbaz configured 2.0.0
-            libbar configured !1.2.0 available 2.1.0
-          EOO
+          $pkg_drop libfox libbaz libbar
+        }
 
-        $pkg_drop libfox libbaz
-      }
+        : to-hold-constr
+        :
+        : Similar to the above, but also specify the version constraint.
+        :
+        {
+          $clone_cfg;
 
-      : unsatisfied-dependent
-      :
-      : This test demonstrates a case when the dependency resolution machinery
-      : fails to complete successfully as noop.
-      :
-      : Note that there is no version constraints are specified on the command
-      : line, the request is to upgrade all packages to the latest possible
-      : versions, and thus noop in this case would an appropriate outcome.
-      :
-      {
-        $clone_cfg;
+          $* libbaz libfox/1.1.0 'libbar < 3.0.0' 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build: libbar/2.1.0 package version needs to be replaced with libbar/0.1.0
+            trace: pkg_build: collection failed due to package version replacement, retry from scratch
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: apply version replacement for libbar/2.1.0
+            trace: collect_build: replacement: libbar/0.1.0
+            trace: collect_build: add libbar/0.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: postpone failure for dependent libfox unsatisfied with dependency libbar/0.1.0 (>= 1.0.0)
+            trace: collect_build: pick libbar/0.1.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/0.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: resume libbar/0.1.0
+            trace: collect_build_prerequisites: end libbar/0.1.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/0.1.0 with 1.2.0 by overwriting constraint 'libbar < 3.0.0' by 'libbar == 1.2.0' on command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbar/1.2.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: resume libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
 
-        $* libbox ?libbix/1.0.0 libbux 2>!;
+          $pkg_status -ar >>EOO;
+            !libbar configured !1.2.0 available 2.1.0
+            !libbaz configured 2.0.0
+              !libbar configured !1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              !libbar configured !1.2.0 available 2.1.0
+            EOO
 
-        $pkg_status -ar >>EOO;
-          libbax configured 1.0.0 available 2.0.0
-          !libbox configured 2.0.0
-            libbax configured 1.0.0 available 2.0.0
-          libbix configured !1.0.0 available 2.0.0
-            libbax configured 1.0.0 available 2.0.0
-          !libbux configured 1.0.0
-            libbix configured !1.0.0 available 2.0.0
-              libbax configured 1.0.0 available 2.0.0
-          EOO
+          $pkg_drop libfox libbaz libbar
+        }
 
-        $* --upgrade --recursive --verbose 5 2>>~%EOE% != 0;
-          %.*
-          trace: pkg_build: refine package collection/plan execution from scratch
-          trace: collect_build: add libbox/2.0.0
-          trace: collect_build: add libbux/1.0.0
-          trace: collect_build_prerequisites: skip configured libbox/2.0.0
-          trace: collect_build_prerequisites: skip configured libbux/1.0.0
-          trace: execute_plan: simulate: yes
-          %.*
-          trace: evaluate_dependency: libbix/1.0.0: update to libbix/2.0.0
-          %.*
-          trace: pkg_build: refine package collection/plan execution
-          trace: collect_build: add libbix/2.0.0
-          trace: collect_build_prerequisites: pre-reeval libbux/1.0.0
-          trace: collect_build_prerequisites: pre-reevaluated libbux/1.0.0: end reached
-          trace: collect_build_prerequisites: begin libbix/2.0.0
-          trace: collect_build: add libbax/2.0.0
-          info: package libbix dependency on (libbax == 2.0.0) is forcing upgrade of libbax/1.0.0 to 2.0.0
-          trace: collect_build_prerequisites: no cfg-clause for dependency libbax/2.0.0 of dependent libbix/2.0.0
-          trace: collect_build_prerequisites: skip unsatisfied existing dependent libbox of dependency libbax/2.0.0 due to constraint (libbax == 1.0.0)
-          trace: collect_build_prerequisites: skip being built existing dependent libbix of dependency libbax
-          trace: collect_build_prerequisites: begin libbax/2.0.0
-          trace: collect_build_prerequisites: end libbax/2.0.0
-          trace: collect_build_prerequisites: end libbix/2.0.0
-          trace: collect_dependents: postpone failure for existing dependent libbox unsatisfied with dependency libbax/2.0.0 (== 1.0.0)
-          trace: execute_plan: simulate: yes
-          %.*
-          error: unable to upgrade package libbax/1.0.0 to 2.0.0
-            info: because configured package libbox/2.0.0 depends on (libbax == 1.0.0)
-            info: package libbax/2.0.0 required by
-                    libbix/2.0.0 (libbax == 2.0.0)
-            info: consider re-trying with --upgrade|-u potentially combined with --recursive|-r
-            info: or explicitly request up/downgrade of package libbox
-            info: or explicitly specify package libbax version to manually satisfy these constraints
-          %.*
-          EOE
+        : configured
+        :
+        : Similar to replace-dependency but the dependency is already configured
+        : as built-to-hold.
+        :
+        {
+          $clone_cfg;
+
+          $* libbar 2>!;
+
+          $* libfox/1.1.0 libbaz 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: skip configured libbar/2.1.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: postpone failure for dependent libbaz unsatisfied with dependency libbar/2.1.0 (< 2.1.0)
+            trace: collect_build: pick libbar/2.1.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/2.1.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: execute_plan: simulate: yes
+            %.*
+            warning: package libbaz/2.0.0 dependency on (libbar < 2.1.0) is forcing downgrade of libbar/2.1.0 to 1.2.0
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/2.1.0 with 1.2.0 by adding package spec 'libbar == 1.2.0' to command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libfox/1.1.0
+            trace: collect_build: add libbaz/2.0.0
+            trace: collect_build: add libbar/1.2.0
+            trace: collect_build_prerequisites: begin libfox/1.1.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/2.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: collect_build_prerequisites: end libfox/1.1.0
+            trace: collect_build_prerequisites: begin libbaz/2.0.0
+            trace: collect_build: pick libbar/1.2.0 over libbar/0.1.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbar/1.2.0 of dependent libbaz/2.0.0
+            trace: collect_build_prerequisites: end libbaz/2.0.0
+            trace: collect_build_prerequisites: resume libbar/1.2.0
+            trace: collect_build_prerequisites: end libbar/1.2.0
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: evaluate_dependency: libbox/2.0.0: unused
+            trace: pkg_build: refine package collection/plan execution
+            trace: collect_drop: add libbox
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: evaluate_dependency: libbax/1.0.0: unused
+            trace: pkg_build: refine package collection/plan execution
+            trace: collect_drop: overwrite libbox
+            trace: collect_drop: add libbax
+            trace: execute_plan: simulate: yes
+            %.*
+              drop libbax/1.0.0 (unused)
+              drop libbox/2.0.0 (unused)
+              downgrade libbar/1.2.0
+              new libfox/1.1.0
+              new libbaz/2.0.0
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
+
+          $pkg_status -ar >>EOO;
+            !libbar configured 1.2.0 available 2.1.0
+            !libfox configured !1.1.0 available 2.0.0
+              !libbar configured 1.2.0 available 2.1.0
+            !libbaz configured 2.0.0
+              !libbar configured 1.2.0 available 2.1.0
+            EOO
+
+          $pkg_drop libfox libbaz libbar
+        }
+
+        : unsatisfied-dependent
+        :
+        : Test that not being able to upgrade a dependency to a later version
+        : which doesn't satisfy an existing dependent, we don't upgrade the
+        : dependency.
+        :
+        {
+          $clone_cfg;
 
-        $pkg_drop libbox libbux
+          $* libfoo 2>!;
+
+          $pkg_status -ar >>EOO;
+            libbar configured 1.2.0 available 2.1.0
+            !libfoo configured 2.0.0
+              libbar configured 1.2.0 available 2.1.0
+            EOO
+
+          $* libbar 2>>~%EOE%;
+            %.*
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbar/2.1.0
+            trace: collect_build_prerequisites: skip unsatisfied existing dependent libfoo of dependency libbar/2.1.0 due to constraint (libbar == 1.2.0)
+            trace: collect_build_prerequisites: begin libbar/2.1.0
+            trace: collect_build: add libbox/2.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbox/2.0.0 of dependent libbar/2.1.0
+            trace: collect_build_prerequisites: begin libbox/2.0.0
+            trace: collect_build: add libbax/1.0.0
+            trace: collect_build_prerequisites: no cfg-clause for dependency libbax/1.0.0 of dependent libbox/2.0.0
+            trace: collect_build_prerequisites: begin libbax/1.0.0
+            trace: collect_build_prerequisites: end libbax/1.0.0
+            trace: collect_build_prerequisites: end libbox/2.0.0
+            trace: collect_build_prerequisites: end libbar/2.1.0
+            trace: collect_dependents: postpone failure for existing dependent libfoo unsatisfied with dependency libbar/2.1.0 (== 1.2.0)
+            trace: execute_plan: simulate: yes
+            %.*
+            trace: try_replace_dependency: replace unsatisfactory package version libbar/2.1.0 with 1.2.0 by overwriting spec 'libbar' by 'libbar == 1.2.0' on command line
+            trace: pkg_build: refine package collection/plan execution from scratch
+            trace: collect_build: add libbar/1.2.0
+            trace: collect_build_prerequisites: skip configured libbar/1.2.0
+            trace: execute_plan: simulate: yes
+            trace: execute_plan: simulate: no
+            %.*
+            EOE
+
+          $pkg_drop libfoo libbar
+        }
       }
     }
   }
@@ -30465,12 +30931,9 @@ else
         $clone_root_cfg;
         $rep_add $rep/t4b && $rep_fetch;
 
-        $* libbar "?$src/libfoo-1.0.0.tar.gz" 2>>~%EOE% != 0
-          error: unable to satisfy constraints on package libfoo
-            info: libbar depends on (libfoo == 1.1.0)
-            info: command line depends on (libfoo == 1.0.0)
-            info: specify libfoo version to satisfy libbar constraint
-          info: while satisfying libbar/1.1.0
+        $* libbar "?$src/libfoo-1.0.0.tar.gz" 2>>EOE != 0
+          error: package libfoo doesn't satisfy its dependents
+            info: libfoo/1.0.0 doesn't satisfy libbar/1.1.0
           EOE
       }
 
@@ -30482,13 +30945,9 @@ else
         $clone_root_cfg;
         $rep_add $rep/t4a && $rep_fetch;
 
-        $* $src/libbar-1.1.0.tar.gz "?$src/libfoo-1.0.0.tar.gz" 2>>~%EOE% != 0
-          error: unable to satisfy constraints on package libfoo
-            info: libbar depends on (libfoo == 1.1.0)
-                    command line requires (libbar == 1.1.0)
-            info: command line depends on (libfoo == 1.0.0)
-            info: specify libfoo version to satisfy libbar constraint
-          info: while satisfying libbar/1.1.0
+        $* $src/libbar-1.1.0.tar.gz "?$src/libfoo-1.0.0.tar.gz" 2>>EOE != 0
+          error: package libfoo doesn't satisfy its dependents
+            info: libfoo/1.0.0 doesn't satisfy libbar/1.1.0
           EOE
       }
 
@@ -30877,12 +31336,9 @@ else
         $clone_root_cfg;
         $rep_add $rep/t4b && $rep_fetch;
 
-        $* libbar "?$d/libfoo-1.0.0/" 2>>~%EOE% != 0
-          error: unable to satisfy constraints on package libfoo
-            info: libbar depends on (libfoo == 1.1.0)
-            info: command line depends on (libfoo == 1.0.0)
-            info: specify libfoo version to satisfy libbar constraint
-          info: while satisfying libbar/1.1.0
+        $* libbar "?$d/libfoo-1.0.0/" 2>>EOE != 0
+          error: package libfoo doesn't satisfy its dependents
+            info: libfoo/1.0.0 doesn't satisfy libbar/1.1.0
           EOE
       }
 
@@ -30894,13 +31350,9 @@ else
         $clone_root_cfg;
         $rep_add $rep/t4a && $rep_fetch;
 
-        $* $d/libbar-1.1.0/ "?$d/libfoo-1.0.0/" 2>>~%EOE% != 0
-          error: unable to satisfy constraints on package libfoo
-            info: libbar depends on (libfoo == 1.1.0)
-                    command line requires (libbar == 1.1.0)
-            info: command line depends on (libfoo == 1.0.0)
-            info: specify libfoo version to satisfy libbar constraint
-          info: while satisfying libbar/1.1.0
+        $* $d/libbar-1.1.0/ "?$d/libfoo-1.0.0/" 2>>EOE != 0
+          error: package libfoo doesn't satisfy its dependents
+            info: libfoo/1.0.0 doesn't satisfy libbar/1.1.0
           EOE
       }