Initial dependency satisfaction implementation

1 files changed, 562 insertions, 52 deletions

diff --git a/bpkg/build.cxx b/bpkg/build.cxx
index d2ec9e8..a518000 100644
--- a/bpkg/build.cxx
+++ b/bpkg/build.cxx
@@ -4,7 +4,12 @@
 
 #include <bpkg/build>
 
-#include <vector>
+#include <map>
+#include <list>
+#include <iterator>   // make_move_iterator()
+#include <functional> // reference_wrapper
+
+#include <butl/utility> // reverse_iterate()
 
 #include <bpkg/types>
 #include <bpkg/package>
@@ -12,8 +17,11 @@
 #include <bpkg/utility>
 #include <bpkg/database>
 #include <bpkg/diagnostics>
+#include <bpkg/satisfaction>
 #include <bpkg/manifest-utility>
 
+#include <bpkg/common-options>
+
 #include <bpkg/pkg-verify>
 
 using namespace std;
@@ -21,15 +29,479 @@ using namespace butl;
 
 namespace bpkg
 {
+  // @@ TODO
+  //
+  //    - User-selected vs auto-selected packages.
+  //
+
+  // Try to find a package that optionally satisfies the specified
+  // version constraint. Look in the specified repository, its
+  // prerequisite repositories, and their complements, recursively
+  // (note: recursivity applies to complements, not prerequisites).
+  // Return the package and the repository in which it was found or
+  // NULL for both if not found.
+  //
+  std::pair<shared_ptr<available_package>, shared_ptr<repository>>
+  find_available (database& db,
+                  const string& name,
+                  const shared_ptr<repository>& r,
+                  const optional<dependency_constraint>& c)
+  {
+    using query = query<available_package>;
+
+    query q (query::id.name == name);
+    const auto& vm (query::id.version);
+
+    // If there is a constraint, then translate it to the query. Otherwise,
+    // get the latest version.
+    //
+    bool order (true);
+    if (c)
+    {
+      const version& v (c->version);
+
+      // Note that the constraint's version is always rhs (libfoo >= 1.2.3).
+      //
+      switch (c->operation)
+      {
+      case comparison::eq: q = q && vm == v; order = false; break;
+      case comparison::lt: q = q && vm <  v; break;
+      case comparison::gt: q = q && vm >  v; break;
+      case comparison::le: q = q && vm <= v; break;
+      case comparison::ge: q = q && vm >= v; break;
+      }
+    }
+
+    if (order)
+      q += order_by_version_desc (vm);
+
+    // Filter the result based on the repository to which each version
+    // belongs.
+    //
+    return filter_one (r, db.query<available_package> (q));
+  }
+
+  // Create a transient (or fake, if you prefer) available_package
+  // object corresponding to the specified selected object. Note
+  // that the package locations list is left empty and that the
+  // returned repository could be NULL if the package is an orphan.
+  //
+  std::pair<shared_ptr<available_package>, shared_ptr<repository>>
+  make_available (const common_options& options,
+                  database& db,
+                  const shared_ptr<selected_package>& sp)
+  {
+    assert (sp != nullptr && sp->state != package_state::broken);
+
+    // First see if we can find its repository.
+    //
+    shared_ptr<repository> ar (
+      db.find<repository> (
+        sp->repository.canonical_name ()));
+
+    // The package is in at least fetched state, which means we should
+    // be able to get its manifest.
+    //
+    shared_ptr<available_package> ap (make_shared<available_package> (
+      sp->state == package_state::fetched
+      ? pkg_verify (options, *sp->archive)
+      : pkg_verify (*sp->src_root)));
+
+    return make_pair (move (ap), move (ar));
+  }
+
+  // A "dependency-ordered" list of packages and their prerequisites.
+  // That is, every package on the list only possibly depending on the
+  // ones after it. In a nutshell, the usage is as follows: we first
+  // add one or more packages (the "initial selection"; for example, a
+  // list of packages the user wants built). The list then satisfies all
+  // the prerequisites of the packages that were added, recursively. At
+  // the end of this process we have an ordered list of all the packages
+  // that we have to build, from last to first, in order to build our
+  // initial selection.
+  //
+  // This process is split into two phases: satisfaction of all the
+  // dependencies (the collect() function) and ordering of the list
+  // (the order() function).
+  //
+  // During the satisfaction phase, we collect all the packages, their
+  // prerequisites (and so on, recursively) in a map trying to satisfy
+  // any dependency constraints. Specifically, during this step, we may
+  // "upgrade" or "downgrade" a package that is already in a map as a
+  // result of another package depending on it and, for example requiring
+  // a different version. One notable side-effect of this process is that
+  // we may end up with a lot more packages in the map than we will have
+  // on the list. This is because some of the prerequisites of upgraded
+  // or downgraded packages may no longer need to be built.
+  //
+  // Note also that we don't try to do exhaustive constraint satisfaction
+  // (i.e., there is no backtracking). Specifically, if we have two
+  // candidate packages each satisfying a constraint of its dependent
+  // package, then if neither of them satisfy both constraints, then we
+  // give up and ask the user to resolve this manually by explicitly
+  // specifying the version that will satisfy both constraints.
+  //
+  //
   struct satisfied_package
   {
-    shared_ptr<available_package> ap; // Note: might be transient.
+    shared_ptr<selected_package>  selected;   // NULL if not selected.
+    shared_ptr<available_package> available;  // Can be fake/transient.
+    shared_ptr<bpkg::repository>  repository; // Can be NULL (orphan) or root.
+
+    // Constraint value plus, normally, the dependent package name that
+    // placed this constraint but can also be some other name for the
+    // initial selection (e.g., package version specified by the user
+    // on the command line).
+    //
+    struct constraint_type
+    {
+      string dependent;
+      dependency_constraint value;
+
+      constraint_type () = default;
+      constraint_type (string d, dependency_constraint v)
+          : dependent (move (d)), value (move (v)) {}
+    };
 
-    optional<path> archive;
-    optional<dir_path> directory;
+    vector<constraint_type> constraints;
   };
 
-  using packages = vector<satisfied_package>;
+  // Now that we have collected all the package versions that we need
+  // to build, arrange them in the "dependency order", that is, with
+  // every package on the list only possibly depending on the ones
+  // after it. Iterate over the names we have collected on the previous
+  // step in reverse so that when we iterate over the packages (also in
+  // reverse), things will be built as close as possible to the order
+  // specified by the user (it may still get altered if there are
+  // dependencies between the specified packages).
+  //
+  struct satisfied_packages
+  {
+    using list_type = list<reference_wrapper<const satisfied_package>>;
+
+    using iterator = list_type::iterator;
+    using reverse_iterator = list_type::const_reverse_iterator;
+
+    reverse_iterator rbegin () const {return list_.rbegin ();}
+    reverse_iterator rend () const {return list_.rend ();}
+
+    // Collect the package. Return true if this package version was,
+    // in fact, added to the map and false if it was already there
+    // or the existing version was preferred.
+    //
+    bool
+    collect (const common_options& options,
+             database& db,
+             satisfied_package&& pkg)
+    {
+      auto i (map_.find (pkg.available->id.name));
+
+      // If we already have an entry for this package name, then we
+      // have to pick one over the other.
+      //
+      if (i != map_.end ())
+      {
+        // At the end we want p1 to point to the object that we keep
+        // and p2 to the object whose constraints we should copy.
+        //
+        satisfied_package* p1 (&i->second.package);
+        satisfied_package* p2 (&pkg);
+
+        // If versions are the same, then all we have to do is copy the
+        // constraint (p1/p2 already point to where we would want them to).
+        //
+        if (p1->available->version != p2->available->version)
+        {
+          using constraint_type = satisfied_package::constraint_type;
+
+          // If the versions differ, we have to pick one. Start with the
+          // newest version since if both satisfy, then that's the one we
+          // should prefer. So get the first to try into p1 and the second
+          // to try -- into p2.
+          //
+          if (p2->available->version > p1->available->version)
+            swap (p1, p2);
+
+          // See if pv's version satisfies pc's constraints. Return the
+          // pointer to the unsatisfied constraint or NULL if all are
+          // satisfied.
+          //
+          auto test = [] (satisfied_package* pv, satisfied_package* pc)
+            -> const constraint_type*
+          {
+            for (const constraint_type& c: pc->constraints)
+              if (!satisfies (pv->available->version, c.value))
+                return &c;
+
+            return nullptr;
+          };
+
+          // First see if p1 satisfies p2's constraints.
+          //
+          if (auto c2 = test (p1, p2))
+          {
+            // If not, try the other way around.
+            //
+            if (auto c1 = test (p2, p1))
+            {
+              const string& n (i->first);
+              const string& d1 (c1->dependent);
+              const string& d2 (c2->dependent);
+
+              fail << "unable to satisfy package " << n << " constraints" <<
+                info << d1 << " depends on (" << n << " " << c1->value << ")" <<
+                info << d2 << " depends on (" << n << " " << c2->value << ")" <<
+                info << "available " << n << " " << p1->available->version <<
+                info << "available " << n << " " << p2->available->version <<
+                info << "explicitly specify " << n << " version to manually "
+                   << "satisfy both constraints";
+            }
+            else
+              swap (p1, p2);
+          }
+        }
+
+        // See if we are replacing the object. If not, then we don't
+        // need to collect its prerequisites since that should have
+        // already been done. Remember, p1 points to the object we
+        // want to keep.
+        //
+        bool replace (p1 != &i->second.package);
+
+        if (replace)
+        {
+          swap (*p1, *p2);
+          swap (p1, p2); // Setup for constraints copying below.
+        }
+
+        p1->constraints.insert (p1->constraints.end (),
+                                make_move_iterator (p2->constraints.begin ()),
+                                make_move_iterator (p2->constraints.end ()));
+
+        if (!replace)
+          return false;
+      }
+      else
+      {
+        string n (pkg.available->id.name); // Note: copy; see emplace() below.
+
+        // This is the first time we are adding this package name to the
+        // map. If it is already selected, then we need to make sure that
+        // packages that already depend on it (called dependents) are ok
+        // with the up/downgrade. We will also have to keep doing this
+        // every time we choose a new available package above. So what
+        // we are going to do is copy the dependents' constrains over to
+        // our constraint list; this way they will be automatically taken
+        // into account by the rest of the logic.
+        //
+        const shared_ptr<selected_package>& sp (pkg.selected);
+        const shared_ptr<available_package>& ap (pkg.available);
+
+        int r;
+        if (sp != nullptr &&
+            sp->state == package_state::configured &&
+            (r = sp->version.compare (ap->version)) != 0)
+        {
+          using query = query<package_dependent>;
+
+          for (const auto& pd: db.query<package_dependent> (query::name == n))
+          {
+            if (!pd.constraint)
+              continue;
+
+            const version& v (ap->version);
+            const dependency_constraint& c (*pd.constraint);
+
+            if (satisfies (v, c))
+            {
+              pkg.constraints.emplace_back (pd.name, c);
+              continue;
+            }
+
+            const char* a (r < 0 ? "upgrade" : "downgrade");
+
+            fail << "unable to " << a << " package " << n << " to " << v <<
+              info << pd.name << " depends on (" << n << " " << c << ")" <<
+              info << "explicitly specify " << n << " version to manually "
+                 << "satisfy this constraint";
+          }
+        }
+
+        i = map_.emplace (move (n),
+                          data_type {list_.end (), move (pkg)}).first;
+      }
+
+      // Now collect all the prerequisites recursively. But first "prune"
+      // this process if the package is already configured since that would
+      // mean all its prerequisites are configured as well. Note that this
+      // is not merely an optimization: the package could be an orphan in
+      // which case the below logic will fail. By skipping the prerequisite
+      // check we are able to gracefully handle configured orphans.
+      //
+      const satisfied_package& p (i->second.package);
+      const shared_ptr<selected_package>& sp (p.selected);
+      const shared_ptr<available_package>& ap (p.available);
+
+      if (sp != nullptr &&
+          sp->version == ap->version &&
+          sp->state == package_state::configured)
+        return true;
+
+      const shared_ptr<repository>& ar (p.repository);
+      const string& name (ap->id.name);
+
+      // Show how we got here if things go wrong while recursively
+      // collecting prerequisites.
+      //
+      auto g (
+        make_exception_guard (
+          [&ap] ()
+          {
+            info << "while satisfying " << ap->id.name << " " << ap->version;
+          }));
+
+      for (const dependency_alternatives& da: ap->dependencies)
+      {
+        if (da.conditional) // @@ TODO
+          fail << "conditional dependencies are not yet supported";
+
+        if (da.size () != 1) // @@ TODO
+          fail << "multiple dependency alternatives not yet supported";
+
+        const dependency& d (da.front ());
+
+        // The first step is to always find the available package even
+        // if, in the end, it won't be the one we select. If we cannot
+        // find the package then that means the repository is broken.
+        // And if we have no repository to look in, then that means the
+        // package is an orphan (we delay this check until we actually
+        // need the repository to allow orphans without prerequisites).
+        //
+        if (ar == nullptr)
+          fail << "package " << name << " " << ap->version << " is orphaned" <<
+            info << "explicitly upgrade it to a new version";
+
+        auto rp (find_available (db, d.name, ar, d.constraint));
+
+        if (rp.first == nullptr)
+          fail << "unknown prerequisite " << d << " of package " << name <<
+            info << "repository " << ar->location << " appears to be broken";
+
+        // Next see if this package is already selected. If we already
+        // have it in the configuraion and it satisfies our dependency
+        // constraint, then we don't want to be forcing its upgrade (or,
+        // worse, downgrade).
+        //
+        bool force (false);
+        shared_ptr<selected_package> dsp (db.find<selected_package> (d.name));
+        if (dsp != nullptr)
+        {
+          if (dsp->state == package_state::broken)
+            fail << "unable to build broken package " << d.name <<
+              info << "use 'pkg-purge --force' to remove";
+
+          if (satisfies (dsp->version, d.constraint))
+            rp = make_available (options, db, dsp);
+          else
+            // Remember that we may be forcing up/downgrade; we will deal
+            // with it below.
+            //
+            force = true;
+        }
+
+        satisfied_package dp {dsp, rp.first, rp.second, {}};
+
+        // Add our constraint, if we have one.
+        //
+        if (d.constraint)
+          dp.constraints.emplace_back (name, *d.constraint);
+
+        // Now collect this prerequisite. If it was actually collected
+        // (i.e., it wasn't already there) and we are forcing an upgrade,
+        // then warn. Downgrade -- outright refuse.
+        //
+        if (collect (options, db, move (dp)) && force)
+        {
+          const version& v (rp.first->version);
+
+          if (v > dsp->version)
+            warn << "package " << name << " dependency " << d << " is forcing "
+                 << "upgrade of " << d.name << " to " << v;
+          else
+            fail << "package " << name << " dependency " << d << " is forcing "
+                 << "downgrade of " << d.name << " to " << v <<
+              info << "explicitly request downgraded version to continue";
+        }
+      }
+
+      return true;
+    }
+
+    // Order the previously-collected package with the specified name
+    // returning its positions.
+    //
+    iterator
+    order (const string& name)
+    {
+      // Every package that we order should have already be collected.
+      //
+      auto mi (map_.find (name));
+      assert (mi != map_.end ());
+
+      // If this package is already in the list, then that would also
+      // mean all its prerequisites are in the list and we can just
+      // return its position.
+      //
+      if (mi->second.position != list_.end ())
+        return mi->second.position;
+
+      const satisfied_package& p (mi->second.package);
+
+      // Unless this package needs something to be before it, add it to
+      // the end of the list.
+      //
+      iterator i (list_.end ());
+
+      // Order all the prerequisites of this package and compute the
+      // position of its "earliest" prerequisite -- this is where it
+      // will be inserted. Similar to collect(), prune if configured
+      // package (we don't have its prerequisites in the map).
+      //
+      if (p.selected == nullptr ||
+          p.selected->version != p.available->version ||
+          p.selected->state != package_state::configured)
+      {
+        for (const dependency_alternatives& da: p.available->dependencies)
+        {
+          assert (!da.conditional && da.size () == 1); // @@ TODO
+          const dependency& d (da.front ());
+
+          iterator j (order (d.name));
+
+          // Figure out if j is before i, in which case set i to j. The
+          // goal here is to find the position of our first prerequisite.
+          //
+          for (iterator k (j); i != j && k != list_.end ();)
+            if (++k == i)
+              i = j;
+        }
+      }
+
+      return mi->second.position = list_.insert (i, p);
+    }
+
+  private:
+    struct data_type
+    {
+      iterator position;         // Note: can be end(), see collect().
+      satisfied_package package;
+    };
+
+    using map_type = map<string, data_type>;
+
+    list_type list_;
+    map_type map_;
+  };
 
   void
   build (const build_options& o, cli::scanner& args)
@@ -49,24 +521,24 @@ namespace bpkg
 
     shared_ptr<repository> root (db.load<repository> (""));
 
-    // Start assembling the list of packages we will need to build
-    // by first collecting the user's selection.
+    // Start assembling the list of packages we will need to build by
+    // first collecting the user's selection and its prerequisites.
     //
-    packages pkgs;
+    satisfied_packages pkgs;
+    vector<string> names;
 
     while (args.more ())
     {
       const char* s (args.next ());
 
-      satisfied_package pkg;
-
-      // Reduce all the potential variations (archive, directory,
-      // package, package version) to the single available_package
-      // object.
+      // Reduce all the potential variations (archive, directory, package
+      // name, package name/version) to a single available_package object.
       //
       string n;
       version v;
-      shared_ptr<available_package>& ap (pkg.ap);
+
+      shared_ptr<repository> ar;
+      shared_ptr<available_package> ap;
 
       // Is this a package archive?
       //
@@ -83,8 +555,9 @@ namespace bpkg
           level4 ([&]{trace << "archive " << a;});
           n = m.name;
           v = m.version;
+          ar = root;
           ap = make_shared<available_package> (move (m));
-          pkg.archive = move (a);
+          ap->locations.push_back (package_location {root, move (a)});
         }
       }
       catch (const invalid_path&)
@@ -112,7 +585,8 @@ namespace bpkg
           n = m.name;
           v = m.version;
           ap = make_shared<available_package> (move (m));
-          pkg.directory = move (d);
+          ar = root;
+          ap->locations.push_back (package_location {root, move (d)});
         }
       }
       catch (const invalid_path&)
@@ -132,24 +606,16 @@ namespace bpkg
         v = parse_package_version (s);
         level4 ([&]{trace << "package " << n << "; version " << v;});
 
-        // Find the available package, if any.
-        //
-        using query = query<available_package>;
-
-        query q (query::id.name == n);
-
         // Either get the user-specified version or the latest.
         //
-        if (!v.empty ())
-          q = q && query::id.version == v;
-        else
-          q += order_by_version_desc (query::id.version);
-
-        // Only consider packages that are in repositories that were
-        // explicitly added to the configuration and their complements,
-        // recursively.
-        //
-        ap = filter_one (root, db.query<available_package> (q)).first;
+        auto rp (
+          v.empty ()
+          ? find_available (db, n, root, nullopt)
+          : find_available (db, n, root,
+                            dependency_constraint {comparison::eq, v}));
+
+        ap = rp.first;
+        ar = rp.second;
       }
 
       // Load the package that may have already been selected and
@@ -158,14 +624,14 @@ namespace bpkg
       // package that we will be building (which may or may not be
       // the same as the selected package).
       //
-      shared_ptr<selected_package> p (db.find<selected_package> (n));
+      shared_ptr<selected_package> sp (db.find<selected_package> (n));
 
-      if (p != nullptr && p->state == package_state::broken)
+      if (sp != nullptr && sp->state == package_state::broken)
         fail << "unable to build broken package " << n <<
           info << "use 'pkg-purge --force' to remove";
 
       // If the user asked for a specific version, then that's what
-      // we should be building.
+      // we ought to be building.
       //
       if (!v.empty ())
       {
@@ -177,8 +643,8 @@ namespace bpkg
           // Otherwise, our only chance is that the already selected
           // object is that exact version.
           //
-          if (p != nullptr && p->version == v)
-            break; // Set ap to p below.
+          if (sp != nullptr && sp->version == v)
+            break; // Derive ap from sp below.
 
           fail << "unknown package " << n << " " << v;
         }
@@ -190,17 +656,20 @@ namespace bpkg
       {
         if (ap != nullptr)
         {
-          // See if what we already have is newer.
+          // Even if this package is already in the configuration, should
+          // we have a newer version, we treat it as an upgrade request;
+          // otherwise, why specify the package in the first place? We just
+          // need to check if what we already have is "better" (i.e., newer).
           //
-          if (p != nullptr && ap->id.version < p->version)
-            ap = nullptr; // Set ap to p below.
+          if (sp != nullptr && ap->id.version < sp->version)
+            ap = nullptr; // Derive ap from sp below.
         }
         else
         {
-          if (p == nullptr)
+          if (sp == nullptr)
             fail << "unknown package " << n;
 
-          // Set ap to p below.
+          // Derive ap from sp below.
         }
       }
 
@@ -209,19 +678,60 @@ namespace bpkg
       //
       if (ap == nullptr)
       {
-        assert (p != nullptr);
+        assert (sp != nullptr);
 
-        // The package is in at least fetched state, which means we
-        // can get its manifest.
-        //
-        ap = make_shared<available_package> (
-          p->state == package_state::fetched
-          ? pkg_verify (o, *p->archive)
-          : pkg_verify (*p->src_root));
+        auto rp (make_available (o, db, sp));
+        ap = rp.first;
+        ar = rp.second; // Could be NULL (orphan).
       }
 
-      level4 ([&]{trace << "building " << ap->id.name << " " << ap->version;});
-      pkgs.push_back (move (pkg));
+      // Finally add this package to the list.
+      //
+      level4 ([&]{trace << "collect " << ap->id.name << " " << ap->version;});
+
+      satisfied_package p {move (sp), move (ap), move (ar), {}};
+
+      // "Fix" the version the user asked for by adding the '==' constraint.
+      //
+      if (!v.empty ())
+        p.constraints.emplace_back (
+          "<command line>",
+          dependency_constraint {comparison::eq, v});
+
+      pkgs.collect (o, db, move (p));
+      names.push_back (n);
+    }
+
+    // Now that we have collected all the package versions that we need
+    // to build, arrange them in the "dependency order", that is, with
+    // every package on the list only possibly depending on the ones
+    // after it. Iterate over the names we have collected on the previous
+    // step in reverse so that when we iterate over the packages (also in
+    // reverse), things will be built as close as possible to the order
+    // specified by the user (it may still get altered if there are
+    // dependencies between the specified packages).
+    //
+    for (const string& n: reverse_iterate (names))
+      pkgs.order (n);
+
+    // Print what we are going to do, then ask for the user's confirmation.
+    //
+    for (const satisfied_package& p: reverse_iterate (pkgs))
+    {
+      const shared_ptr<selected_package>& sp (p.selected);
+      const shared_ptr<available_package>& ap (p.available);
+
+      const char* a;
+
+      // Even if we already have this package selected, we have to
+      // make sure it is configured and updated.
+      //
+      if (sp == nullptr || sp->version == ap->version)
+        a = "build";
+      else
+        a = sp->version < ap->version ? "upgrade" : "downgrade";
+
+      text << a << " " << ap->id.name << " " << ap->version;
     }
 
     t.commit ();