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)
commit793155f9f3b7cbdff02cae5eb421371346aa45cd
tree60988c7de409a20625725a06b28d1fb5d1dc66c8
parentb1dc770d157cdad8699e1b27a18530862b056575
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 <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