From: Pieter Smith Date: Thu, 23 Feb 2017 12:54:14 +0000 (+0100) Subject: pkg_depends: fix unsatisfied dependency installation order X-Git-Url: http://git.openwrt.org/?p=project%2Fopkg-lede.git;a=commitdiff_plain;h=793155f9f3b7cbdff02cae5eb421371346aa45cd pkg_depends: fix unsatisfied dependency installation order Unsatisfied dependencies are not being installed in the correct order. The algorithm is not crawling down the dependency chain first when inserting unsatisfied dependencies, resulting in a correct installation order only for the first layer of dependencies. This patch changes the unsatisfied dependency insertion order to first add leaf dependencies, then move up the chain. The result is a list of unsatisfied dependencies ordered most-dependent-first. An example that resulted in the incorrect installation order was: A -> B A -> C B -> D Without the fix, a most-dependent-first installation order was not guaranteed more than one layer deep, resulting in an installation order where B is incorrectly installed before D: B, D, C, A After the fix, the installation order follows most-dependent first irrespective of the number of layers: D, B, C, A Signed-off-by: Pieter Smith [Jo-Philipp Wich: rebased onto opkg-lede.git] Signed-off-by: Jo-Philipp Wich --- diff --git a/libopkg/pkg_depends.c b/libopkg/pkg_depends.c index 0072e5e..0883b4f 100644 --- a/libopkg/pkg_depends.c +++ b/libopkg/pkg_depends.c @@ -250,9 +250,9 @@ pkg_hash_fetch_unsatisfied_dependencies(pkg_t * pkg, pkg_vec_t * unsatisfied, if (satisfier_entry_pkg != pkg && !is_pkg_in_pkg_vec(unsatisfied, satisfier_entry_pkg)) { - pkg_vec_insert(unsatisfied, satisfier_entry_pkg); pkg_hash_fetch_unsatisfied_dependencies( satisfier_entry_pkg, unsatisfied, &newstuff); + pkg_vec_insert(unsatisfied, satisfier_entry_pkg); the_lost = merge_unresolved(the_lost, newstuff); if (newstuff) free(newstuff);