[pacman-dev] [PATCH] deps.c: check for indirect deps when ordering
Allan McRae
allan at archlinux.org
Tue Jun 18 02:04:55 EDT 2013
On 19/05/13 05:53, Andrew Gregory wrote:
> On upgrades, indirect dependencies were not being detected if there was
> a dependency in between them that was not part of the transaction. For
> example, with the dependency chain: pkg1 -> pkg2 -> pkg3, if pkg1 and
> pkg3 are being upgraded but not pkg2 pacman would not order pkg1 and
> pkg3 properly.
>
> This was particularly problematic when replacements were involved
> because the replaced package(s) would be removed at the start of the
> transaction. If an install script required the replacer and lacked
> a direct dependency, it could fail.
>
> Fixes FS#32764.
>
> Partially fixes FS#23011.
>
> Signed-off-by: Andrew Gregory <andrew.gregory.8 at gmail.com>
> ---
>
> The need to keep state in order to avoid getting stuck in cyclic dependencies
> makes this a little ugly (hence the wrapper function). If anybody has a better
> idea for avoiding those loops, I'd love to clean it up.
Finally got to reviewing this... I can not immediately see a way to
avoid those loops.
Signed-off-by: Allan
> lib/libalpm/deps.c | 101 +++++++++++++++++++++++++++++++++-------
> test/pacman/tests/replace100.py | 2 -
> test/pacman/tests/upgrade100.py | 44 +++++++++++++++++
> 3 files changed, 127 insertions(+), 20 deletions(-)
> create mode 100644 test/pacman/tests/upgrade100.py
>
> diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
> index 96c49a9..adcdd3a 100644
> --- a/lib/libalpm/deps.c
> +++ b/lib/libalpm/deps.c
> @@ -65,8 +65,8 @@ void _alpm_depmiss_free(alpm_depmissing_t *miss)
> FREE(miss);
> }
>
> -/* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */
> -static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2)
> +/** Check if pkg2 satisfies a dependency of pkg1 */
> +static int _alpm_pkg_depends_on(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2)
> {
> alpm_list_t *i;
> for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) {
> @@ -77,6 +77,84 @@ static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2)
> return 0;
> }
>
> +static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep)
> +{
> + alpm_list_t *i;
> +
> + for(i = pkgs; i; i = i->next) {
> + alpm_pkg_t *pkg = i->data;
> + if(_alpm_depcmp(pkg, dep)) {
> + return pkg;
> + }
> + }
> + return NULL;
> +}
> +
> +/** Check if pkg2 is anywhere in pkg1's dependency tree.
> + * @param pkg1
> + * @param pkg2
> + * @param targets if a package in this list is an intermediate dependency
> + * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be
> + * reported
> + * @param ignore packages which should not be recursively checked for
> + * intermediate dependencies. Used internally for state to avoid
> + * getting stuck on cyclic dependencies.
> + * @return 1 if pkg2 is found in pkg1's dependency tree
> + */
> +static int _alpm_pkg_in_dep_tree(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2,
> + alpm_list_t *targets, alpm_list_t **ignore)
> +{
> + alpm_list_t *i, *pkgs = alpm_db_get_pkgcache(pkg1->handle->db_local);
> +
> + if(_alpm_pkg_depends_on(pkg1, pkg2)) {
> + return 1;
> + }
> +
> + *ignore = alpm_list_add(*ignore, pkg1);
> +
> + /* pkg1 does not directly depend on pkg2, but if this is an upgrade
> + * operation there may be an indirect dependency through an installed
> + * dependency not part of the current transaction */
> + for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) {
> + alpm_depend_t *dep = i->data;
> + alpm_pkg_t *lpkg = find_dep_satisfier(pkgs, dep);
> +
> + if(!lpkg) {
> + continue;
> + } else if(alpm_list_find(targets, lpkg, _alpm_pkg_cmp)) {
> + /* lpkg's upgrade is part of the transaction, any dependency will be
> + * detected separately as pkg1 -> lpkg and lpkg -> pkg2 */
> + continue;
> + } else if(alpm_list_find(*ignore, lpkg, _alpm_pkg_cmp)) {
> + /* we've already checked lpkg, move on */
> + continue;
> + } else if(_alpm_pkg_in_dep_tree(lpkg, pkg2, targets, ignore)) {
> + /* we have an indirect dependency: pkg1 -> lpkg -> ... -> pkg2 */
> + return 1;
> + }
> + }
> +
> + return 0;
> +}
> +
> +/** Check if pkg2 is anywhere in pkg1's dependency tree.
> + * Wrapper for _alpm_pkg_in_dep_tree to handle creating and destroying state.
> + * @param pkg1
> + * @param pkg2
> + * @param targets if a package in this list is an intermediate dependency
> + * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be
> + * reported
> + * @return 1 if pkg2 is found in pkg1's dependency tree
> + */
> +static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2,
> + alpm_list_t *targets)
> +{
> + alpm_list_t *ignore = NULL;
> + int ret = _alpm_pkg_in_dep_tree(pkg1, pkg2, targets, &ignore);
> + alpm_list_free(ignore);
> + return ret;
> +}
> +
> /* Convert a list of alpm_pkg_t * to a graph structure,
> * with a edge for each dependency.
> * Returns a list of vertices (one vertex = one package)
> @@ -101,7 +179,7 @@ static alpm_list_t *dep_graph_init(alpm_list_t *targets)
> for(j = vertices; j; j = j->next) {
> alpm_graph_t *vertex_j = j->data;
> alpm_pkg_t *p_j = vertex_j->data;
> - if(_alpm_dep_edge(p_i, p_j)) {
> + if(_alpm_dep_edge(p_i, p_j, targets)) {
> vertex_i->children =
> alpm_list_add(vertex_i->children, vertex_j);
> }
> @@ -229,19 +307,6 @@ static void release_filtered_depend(alpm_depend_t *dep, int nodepversion)
> }
> }
>
> -static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep)
> -{
> - alpm_list_t *i;
> -
> - for(i = pkgs; i; i = i->next) {
> - alpm_pkg_t *pkg = i->data;
> - if(_alpm_depcmp(pkg, dep)) {
> - return pkg;
> - }
> - }
> - return NULL;
> -}
> -
> /** Find a package satisfying a specified dependency.
> * The dependency can include versions with depmod operators.
> * @param pkgs an alpm_list_t* of alpm_pkg_t where the satisfier will be searched
> @@ -517,7 +582,7 @@ static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg,
> /* see if other packages need it */
> for(i = _alpm_db_get_pkgcache(db); i; i = i->next) {
> alpm_pkg_t *lpkg = i->data;
> - if(_alpm_dep_edge(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) {
> + if(_alpm_pkg_depends_on(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) {
> return 0;
> }
> }
> @@ -549,7 +614,7 @@ int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit)
> alpm_pkg_t *pkg = i->data;
> for(j = _alpm_db_get_pkgcache(db); j; j = j->next) {
> alpm_pkg_t *deppkg = j->data;
> - if(_alpm_dep_edge(pkg, deppkg)
> + if(_alpm_pkg_depends_on(pkg, deppkg)
> && can_remove_package(db, deppkg, targs, include_explicit)) {
> alpm_pkg_t *copy;
> _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n",
> diff --git a/test/pacman/tests/replace100.py b/test/pacman/tests/replace100.py
> index f94ca0f..dcb7111 100644
> --- a/test/pacman/tests/replace100.py
> +++ b/test/pacman/tests/replace100.py
> @@ -41,5 +41,3 @@
> self.addrule("PKG_VERSION=kernel26|2.6.37.1-1")
> self.addrule("FILE_EXIST=sbin/blkid")
> self.addrule("FILE_EXIST=foundit")
> -
> -self.expectfailure = True
> diff --git a/test/pacman/tests/upgrade100.py b/test/pacman/tests/upgrade100.py
> new file mode 100644
> index 0000000..3f7a021
> --- /dev/null
> +++ b/test/pacman/tests/upgrade100.py
> @@ -0,0 +1,44 @@
> +self.description = "Indirect dependency ordering (FS#32764)"
> +
> +lp1 = pmpkg("fcitx-gtk2", "1.0-1");
> +lp1.depends = ["gtk2"]
> +self.addpkg2db("local", lp1)
> +
> +lp2 = pmpkg("gtk2", "1.0-1");
> +lp2.depends = ["pango"]
> +self.addpkg2db("local", lp2)
> +
> +lp3 = pmpkg("pango", "1.0-1");
> +lp3.depends = ["harfbuzz"]
> +self.addpkg2db("local", lp3)
> +
> +lp4 = pmpkg("harfbuzz", "1.0-1");
> +lp4.depends = ["icu"]
> +self.addpkg2db("local", lp4)
> +
> +lp5 = pmpkg("icu", "1.0-1");
> +self.addpkg2db("local", lp5)
> +
> +sp1 = pmpkg("fcitx-gtk2", "1.0-2");
> +sp1.depends = ["gtk2"]
> +sp1.install['post_upgrade'] = "[ -f bin/harfbuzz ] && echo > found_harfbuzz"
> +self.addpkg2db("sync", sp1)
> +
> +sp4 = pmpkg("harfbuzz", "1.0-2");
> +sp4.depends = ["icu"]
> +sp4.files = ["bin/harfbuzz"]
> +sp4.install['post_upgrade'] = "[ -f bin/icu ] && echo > found_icu"
> +self.addpkg2db("sync", sp4)
> +
> +sp5 = pmpkg("icu", "1.0-2");
> +sp5.files = ["bin/icu"]
> +self.addpkg2db("sync", sp5)
> +
> +self.args = "-Su"
> +
> +self.addrule("PACMAN_RETCODE=0")
> +self.addrule("PKG_VERSION=fcitx-gtk2|1.0-2")
> +self.addrule("PKG_VERSION=harfbuzz|1.0-2")
> +self.addrule("PKG_VERSION=icu|1.0-2")
> +self.addrule("FILE_EXIST=found_harfbuzz")
> +self.addrule("FILE_EXIST=found_icu")
>
More information about the pacman-dev
mailing list