aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKaren Arutyunov <karen@codesynthesis.com>2019-05-17 23:00:18 +0300
committerKaren Arutyunov <karen@codesynthesis.com>2019-05-21 11:39:30 +0300
commit2383d8e0a38e2c07cf0418436d1476c3f9b6ab97 (patch)
tree1897bde475b729fd16eb3ef11ad641900fed069b
parent314a2ce11e16763a6a60726e724890dca772716c (diff)
Detect and complain about dependency cycle in pkg-build
-rw-r--r--bpkg/pkg-build.cxx389
-rw-r--r--bpkg/types.hxx2
-rw-r--r--bpkg/utility.txx4
-rw-r--r--tests/pkg-build.testscript93
4 files changed, 329 insertions, 159 deletions
diff --git a/bpkg/pkg-build.cxx b/bpkg/pkg-build.cxx
index f9c84ef..1f14f65 100644
--- a/bpkg/pkg-build.cxx
+++ b/bpkg/pkg-build.cxx
@@ -41,14 +41,12 @@ namespace bpkg
{
// @@ Overall TODO:
//
- // - Detect and complain about dependency cycles.
- //
// - Configuration vars (both passed and preserved)
//
// Query the available packages that optionally satisfy the specified version
- // version constraint and return them in the version descending order. Note
- // that a stub satisfies any constraint.
+ // constraint and return them in the version descending order. Note that a
+ // stub satisfies any constraint.
//
odb::result<available_package>
query_available (database& db,
@@ -551,15 +549,17 @@ namespace bpkg
// pointer to the unsatisfied constraint or NULL if all are
// satisfied.
//
- auto test = [] (build_package* pv, build_package* pc)
- -> const constraint_type*
+ auto test = [] (build_package* pv,
+ build_package* pc) -> const constraint_type*
+ {
+ for (const constraint_type& c: pc->constraints)
{
- for (const constraint_type& c: pc->constraints)
- if (!satisfies (pv->available_version (), c.value))
- return &c;
+ if (!satisfies (pv->available_version (), c.value))
+ return &c;
+ }
- return nullptr;
- };
+ return nullptr;
+ };
// First see if p1 satisfies p2's constraints.
//
@@ -633,6 +633,26 @@ namespace bpkg
build_package& p (i->second.package);
+ // Recursively collect build prerequisites, if requested.
+ //
+ // Note that detecting dependency cycles during the satisfaction phase
+ // would be premature since they may not be present in the final package
+ // list. Instead we check for them during the ordering phase.
+ //
+ // The question, of course, is whether we can still end up with an
+ // infinite recursion here? Note that for an existing map entry we only
+ // recurse after the entry replacement. The infinite recursion would
+ // mean that we may replace a package in the map with the same version
+ // multiple times:
+ //
+ // ... p1 -> p2 -> ... p1
+ //
+ // Every replacement increases the entry version and/or tightens the
+ // constraints the next replacement will need to satisfy. It feels
+ // impossible that a package version can "return" into the map being
+ // replaced once. So let's wait until some real use case proves this
+ // reasoning wrong.
+ //
if (recursively != nullptr)
collect_build_prerequisites (options, cd, db, p, recursively);
@@ -1150,153 +1170,16 @@ namespace bpkg
}
// Order the previously-collected package with the specified name
- // returning its positions. If reorder is true, then reorder this
- // package to be considered as "early" as possible.
+ // returning its positions. Recursively order the package dependencies
+ // being ordered failing if a dependency cycle is detected. If reorder is
+ // true, then reorder this package to be considered as "early" as
+ // possible.
//
iterator
order (const package_name& name, bool reorder = true)
{
- // Every package that we order should have already been collected.
- //
- auto mi (map_.find (name));
- assert (mi != map_.end ());
-
- build_package& p (mi->second.package);
-
- assert (p.action); // Can't order just a pre-entered package.
-
- // 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. Unless we want it reordered.
- //
- iterator& pos (mi->second.position);
- if (pos != end ())
- {
- if (reorder)
- erase (pos);
- else
- return pos;
- }
-
- // Order all the prerequisites of this package and compute the
- // position of its "earliest" prerequisite -- this is where it
- // will be inserted.
- //
- const shared_ptr<selected_package>& sp (p.selected);
- const shared_ptr<available_package>& ap (p.available);
-
- bool build (*p.action == build_package::build);
-
- // Package build must always have the available package associated.
- //
- assert (!build || ap != nullptr);
-
- // Unless this package needs something to be before it, add it to
- // the end of the list.
- //
- iterator i (end ());
-
- // Figure out if j is before i, in which case set i to j. The goal
- // here is to find the position of our "earliest" prerequisite.
- //
- auto update = [this, &i] (iterator j)
- {
- for (iterator k (j); i != j && k != end ();)
- if (++k == i)
- i = j;
- };
-
- // Similar to collect_build(), we can prune if the package is already
- // configured, right? While in collect_build() we didn't need to add
- // prerequisites of such a package, it doesn't mean that they actually
- // never ended up in the map via another dependency path. For example,
- // some can be a part of the initial selection. And in that case we must
- // order things properly.
- //
- // Also, if the package we are ordering is not a system one and needs to
- // be disfigured during the plan execution, then we must order its
- // (current) dependencies that also need to be disfigured.
- //
- bool src_conf (sp != nullptr &&
- sp->state == package_state::configured &&
- sp->substate != package_substate::system);
-
- auto disfigure = [] (const build_package& p)
- {
- return p.action && (*p.action == build_package::drop ||
- p.reconfigure ());
- };
-
- bool order_disfigured (src_conf && disfigure (p));
-
- // Order the build dependencies.
- //
- if (build && !p.system)
- {
- // So here we are going to do things differently depending on
- // whether the package is already configured or not. If it is and
- // not as a system package, then that means we can use its
- // prerequisites list. Otherwise, we use the manifest data.
- //
- if (src_conf && sp->version == p.available_version ())
- {
- for (const auto& p: sp->prerequisites)
- {
- const package_name& name (p.first.object_id ());
-
- // The prerequisites may not necessarily be in the map.
- //
- auto i (map_.find (name));
- if (i != map_.end () && i->second.package.action)
- update (order (name, false));
- }
-
- // We just ordered them among other prerequisites.
- //
- order_disfigured = false;
- }
- else
- {
- // We are iterating in reverse so that when we iterate over
- // the dependency list (also in reverse), prerequisites will
- // be built in the order that is as close to the manifest as
- // possible.
- //
- for (const dependency_alternatives& da:
- reverse_iterate (ap->dependencies))
- {
- assert (!da.conditional && da.size () == 1); // @@ TODO
- const dependency& d (da.front ());
- const package_name& dn (d.name);
-
- // Skip special names.
- //
- if (da.buildtime && (dn == "build2" || dn == "bpkg"))
- continue;
-
- update (order (d.name, false));
- }
- }
- }
-
- // Order the dependencies being disfigured.
- //
- if (order_disfigured)
- {
- for (const auto& p: sp->prerequisites)
- {
- const package_name& name (p.first.object_id ());
-
- // The prerequisites may not necessarily be in the map.
- //
- auto i (map_.find (name));
-
- if (i != map_.end () && disfigure (i->second.package))
- update (order (name, false));
- }
- }
-
- return pos = insert (i, p);
+ package_names chain;
+ return order (name, chain, reorder);
}
// If a configured package is being up/down-graded then that means
@@ -1510,7 +1393,11 @@ namespace bpkg
i->second.position = insert (pos, i->second.package);
}
- // Collect our own dependents inserting them before us.
+ // Recursively collect our own dependents inserting them before us.
+ //
+ // Note that we cannot end up with an infinite recursion for
+ // configured packages due to a dependency cycle (see order() for
+ // details).
//
collect_order_dependents (db, i->second.position);
}
@@ -1533,6 +1420,193 @@ namespace bpkg
}
private:
+ using package_names = small_vector<reference_wrapper<const package_name>,
+ 16>;
+
+ iterator
+ order (const package_name& name, package_names& chain, bool reorder)
+ {
+ // Every package that we order should have already been collected.
+ //
+ auto mi (map_.find (name));
+ assert (mi != map_.end ());
+
+ build_package& p (mi->second.package);
+
+ assert (p.action); // Can't order just a pre-entered package.
+
+ // Make sure there is no dependency cycle.
+ //
+ {
+ auto i (find (chain.begin (), chain.end (), name));
+
+ if (i != chain.end ())
+ {
+ diag_record dr (fail);
+ dr << "dependency cycle detected involving package " << name;
+
+ auto nv = [this] (const package_name& name)
+ {
+ auto mi (map_.find (name));
+ assert (mi != map_.end ());
+
+ build_package& p (mi->second.package);
+
+ assert (p.action); // See above.
+
+ // We cannot end up with a dependency cycle for actions other than
+ // build since these packages are configured and we would fail on
+ // a previous run while building them.
+ //
+ assert (p.available != nullptr);
+
+ return p.available_name_version ();
+ };
+
+ for (chain.push_back (name); i != chain.end () - 1; ++i)
+ dr << info << nv (*i) << " depends on " << nv (*(i + 1));
+ }
+ }
+
+ // 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. Unless we want it reordered.
+ //
+ iterator& pos (mi->second.position);
+ if (pos != end ())
+ {
+ if (reorder)
+ erase (pos);
+ else
+ return pos;
+ }
+
+ // Order all the prerequisites of this package and compute the
+ // position of its "earliest" prerequisite -- this is where it
+ // will be inserted.
+ //
+ const shared_ptr<selected_package>& sp (p.selected);
+ const shared_ptr<available_package>& ap (p.available);
+
+ bool build (*p.action == build_package::build);
+
+ // Package build must always have the available package associated.
+ //
+ assert (!build || ap != nullptr);
+
+ // Unless this package needs something to be before it, add it to
+ // the end of the list.
+ //
+ iterator i (end ());
+
+ // Figure out if j is before i, in which case set i to j. The goal
+ // here is to find the position of our "earliest" prerequisite.
+ //
+ auto update = [this, &i] (iterator j)
+ {
+ for (iterator k (j); i != j && k != end ();)
+ if (++k == i)
+ i = j;
+ };
+
+ // Similar to collect_build(), we can prune if the package is already
+ // configured, right? While in collect_build() we didn't need to add
+ // prerequisites of such a package, it doesn't mean that they actually
+ // never ended up in the map via another dependency path. For example,
+ // some can be a part of the initial selection. And in that case we must
+ // order things properly.
+ //
+ // Also, if the package we are ordering is not a system one and needs to
+ // be disfigured during the plan execution, then we must order its
+ // (current) dependencies that also need to be disfigured.
+ //
+ bool src_conf (sp != nullptr &&
+ sp->state == package_state::configured &&
+ sp->substate != package_substate::system);
+
+ auto disfigure = [] (const build_package& p)
+ {
+ return p.action && (*p.action == build_package::drop ||
+ p.reconfigure ());
+ };
+
+ bool order_disfigured (src_conf && disfigure (p));
+
+ chain.push_back (name);
+
+ // Order the build dependencies.
+ //
+ if (build && !p.system)
+ {
+ // So here we are going to do things differently depending on
+ // whether the package is already configured or not. If it is and
+ // not as a system package, then that means we can use its
+ // prerequisites list. Otherwise, we use the manifest data.
+ //
+ if (src_conf && sp->version == p.available_version ())
+ {
+ for (const auto& p: sp->prerequisites)
+ {
+ const package_name& name (p.first.object_id ());
+
+ // The prerequisites may not necessarily be in the map.
+ //
+ auto i (map_.find (name));
+ if (i != map_.end () && i->second.package.action)
+ update (order (name, chain, false /* reorder */));
+ }
+
+ // We just ordered them among other prerequisites.
+ //
+ order_disfigured = false;
+ }
+ else
+ {
+ // We are iterating in reverse so that when we iterate over
+ // the dependency list (also in reverse), prerequisites will
+ // be built in the order that is as close to the manifest as
+ // possible.
+ //
+ for (const dependency_alternatives& da:
+ reverse_iterate (ap->dependencies))
+ {
+ assert (!da.conditional && da.size () == 1); // @@ TODO
+ const dependency& d (da.front ());
+ const package_name& dn (d.name);
+
+ // Skip special names.
+ //
+ if (da.buildtime && (dn == "build2" || dn == "bpkg"))
+ continue;
+
+ update (order (d.name, chain, false /* reorder */));
+ }
+ }
+ }
+
+ // Order the dependencies being disfigured.
+ //
+ if (order_disfigured)
+ {
+ for (const auto& p: sp->prerequisites)
+ {
+ const package_name& name (p.first.object_id ());
+
+ // The prerequisites may not necessarily be in the map.
+ //
+ auto i (map_.find (name));
+
+ if (i != map_.end () && disfigure (i->second.package))
+ update (order (name, chain, false /* reorder */));
+ }
+ }
+
+ chain.pop_back ();
+
+ return pos = insert (i, p);
+ }
+
+ private:
struct data_type
{
iterator position; // Note: can be end(), see collect_build().
@@ -2040,6 +2114,9 @@ namespace bpkg
for (const auto& pd: db.query<package_dependent> (
query<package_dependent>::name == nm))
{
+ // Note that we cannot end up with an infinite recursion for configured
+ // packages due to a dependency cycle (see order() for details).
+ //
if (optional<bool> u = upgrade_dependencies (db, pd.name, recs, true))
{
if (!r || *r < *u) // Upgrade wins patch.
@@ -3691,7 +3768,7 @@ namespace bpkg
for (const dependency_package& p: dep_pkgs)
{
if (p.selected != nullptr && p.selected->hold_package)
- pkgs.order (p.name, false);
+ pkgs.order (p.name, false /* reorder */);
}
// We are about to execute the plan on the database (but not on the
diff --git a/bpkg/types.hxx b/bpkg/types.hxx
index 84a0d00..f36a33c 100644
--- a/bpkg/types.hxx
+++ b/bpkg/types.hxx
@@ -27,6 +27,7 @@
#include <libbutl/utility.mxx> // compare_reference_target
#include <libbutl/optional.mxx>
#include <libbutl/fdstream.mxx>
+#include <libbutl/small-vector.mxx>
namespace bpkg
{
@@ -50,6 +51,7 @@ namespace bpkg
using std::weak_ptr;
using std::vector;
+ using butl::small_vector; // <libbutl/small-vector.mxx>
using strings = vector<string>;
using cstrings = vector<const char*>;
diff --git a/bpkg/utility.txx b/bpkg/utility.txx
index 71701bc..0e71e13 100644
--- a/bpkg/utility.txx
+++ b/bpkg/utility.txx
@@ -2,8 +2,6 @@
// copyright : Copyright (c) 2014-2019 Code Synthesis Ltd
// license : MIT; see accompanying LICENSE file
-#include <libbutl/small-vector.mxx>
-
#include <bpkg/diagnostics.hxx>
namespace bpkg
@@ -29,7 +27,7 @@ namespace bpkg
//
process_path pp (process::path_search (b, exec_dir));
- butl::small_vector<const char*, 1> ops;
+ small_vector<const char*, 1> ops;
// Map verbosity level. If we are running quiet or at level 1,
// then run build2 quiet. Otherwise, run it at the same level
diff --git a/tests/pkg-build.testscript b/tests/pkg-build.testscript
index cbcd35f..fdedc0c 100644
--- a/tests/pkg-build.testscript
+++ b/tests/pkg-build.testscript
@@ -2562,6 +2562,99 @@ test.options += --no-progress
}
}
+: dependency-cycle
+:
+{
+ test.arguments += --yes
+
+ : direct
+ :
+ {
+ $clone_root_cfg;
+
+ cp -r $src/libfoo-1.1.0/ libfoo;
+ echo "depends: libfoo" >+ libfoo/manifest;
+ $rep_add libfoo --type dir;
+
+ $rep_fetch;
+
+ $* libfoo 2>>EOE != 0
+ error: dependency cycle detected involving package libfoo
+ info: libfoo/1.1.0 depends on libfoo/1.1.0
+ EOE
+ }
+
+ : indirect
+ :
+ {
+ : new
+ :
+ {
+ $clone_root_cfg;
+
+ cp -r $src/libfoo-1.1.0/ libfoo;
+ echo "depends: libbar" >+ libfoo/manifest;
+
+ cat <<"EOI" >=libfoo/repositories.manifest;
+ : 1
+ summary: libfoo project repository
+
+ :
+ role: prerequisite
+ location: $rep/t0b
+ EOI
+
+ $rep_add libfoo --type dir;
+
+ $rep_fetch;
+
+ $* libfoo 2>>EOE != 0
+ error: dependency cycle detected involving package libfoo
+ info: libfoo/1.1.0 depends on libbar/0.0.2
+ info: libbar/0.0.2 depends on libbaz/0.0.2
+ info: libbaz/0.0.2 depends on libfoo/1.1.0
+ EOE
+ }
+
+ : upgrade
+ :
+ {
+ $clone_root_cfg;
+
+ cp -r $src/libfoo-1.1.0/ libfoo;
+ $rep_add libfoo --type dir;
+
+ cp -r $src/libhello-1.0.0/ libhello;
+ echo "depends: libfoo" >+ libhello/manifest;
+ $rep_add libhello --type dir;
+
+ $rep_fetch;
+
+ $* libhello 2>>~%EOE%;
+ using libfoo/1.1.0 (external)
+ configured libfoo/1.1.0
+ using libhello/1.0.0 (external)
+ configured libhello/1.0.0
+ %(mkdir|c\+\+|ld|ar) .+%{8}
+ updated libhello/1.0.0
+ EOE
+
+ echo "depends: libhello" >+ libfoo/manifest;
+ sed -i -e 's/(version: 1.1).0/\1.1/' libfoo/manifest;
+
+ $rep_fetch;
+
+ $* ?libfoo 2>>EOE != 0;
+ error: dependency cycle detected involving package libfoo
+ info: libfoo/1.1.1 depends on libhello/1.0.0
+ info: libhello/1.0.0 depends on libfoo/1.1.1
+ EOE
+
+ $pkg_drop libhello
+ }
+ }
+}
+
: config-vars
:
{