diff options
| -rw-r--r-- | bpkg/pkg-build.cxx | 389 | ||||
| -rw-r--r-- | bpkg/types.hxx | 2 | ||||
| -rw-r--r-- | bpkg/utility.txx | 4 | ||||
| -rw-r--r-- | tests/pkg-build.testscript | 93 |
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 : { |