aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2015-10-07 09:48:10 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2015-10-07 09:48:10 +0200
commit3942883062150a1a6fb3d82d12a06d6760937d44 (patch)
treee136ac38f05c2b9921058a130e5691cab9504441
parent957303d2f146bc9b12aaaa39c752212ca94dc4eb (diff)
Initial dependency satisfaction implementation
-rw-r--r--bpkg/build.cxx614
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 ();