pkg_depends: fix unsatisfied dependency installation order
authorPieter Smith <pieter.smith@philips.com>
Thu, 23 Feb 2017 12:54:14 +0000 (13:54 +0100)
committerJo-Philipp Wich <jo@mein.io>
Thu, 23 Feb 2017 15:42:32 +0000 (16:42 +0100)
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 <pieter.smith@philips.com>
[Jo-Philipp Wich: rebased onto opkg-lede.git]
Signed-off-by: Jo-Philipp Wich <jo@mein.io>
libopkg/pkg_depends.c

index 0072e5e..0883b4f 100644 (file)
@@ -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);