diff options
Diffstat (limited to 'lib/libalpm/deps.c')
-rw-r--r-- | lib/libalpm/deps.c | 106 |
1 files changed, 55 insertions, 51 deletions
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index ae5d60bc..96f91739 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -1,7 +1,7 @@ /* * deps.c * - * Copyright (c) 2006-2016 Pacman Development Team <pacman-dev@archlinux.org> + * Copyright (c) 2006-2017 Pacman Development Team <pacman-dev@archlinux.org> * Copyright (c) 2002-2006 by Judd Vinet <jvinet@zeroflux.org> * Copyright (c) 2005 by Aurelien Foret <orelien@chez.com> * Copyright (c) 2005, 2006 by Miklos Vajna <vmiklos@frugalware.org> @@ -152,12 +152,48 @@ static alpm_list_t *dep_graph_init(alpm_handle_t *handle, j = next; } - vertex_i->childptr = vertex_i->children; + vertex_i->iterator = vertex_i->children; } alpm_list_free(localpkgs); return vertices; } +static void _alpm_warn_dep_cycle(alpm_handle_t *handle, alpm_list_t *targets, + alpm_graph_t *ancestor, alpm_graph_t *vertex, int reverse) +{ + /* vertex depends on and is required by ancestor */ + if(!alpm_list_find_ptr(targets, vertex->data)) { + /* child is not part of the transaction, not a problem */ + return; + } + + /* find the nearest ancestor that's part of the transaction */ + while(ancestor) { + if(alpm_list_find_ptr(targets, ancestor->data)) { + break; + } + ancestor = ancestor->parent; + } + + if(!ancestor || ancestor == vertex) { + /* no transaction package in our ancestry or the package has + * a circular dependency with itself, not a problem */ + } else { + alpm_pkg_t *ancestorpkg = ancestor->data; + alpm_pkg_t *childpkg = vertex->data; + _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); + if(reverse) { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be removed after its %s dependency\n"), + ancestorpkg->name, childpkg->name); + } else { + _alpm_log(handle, ALPM_LOG_WARNING, + _("%s will be installed before its %s dependency\n"), + ancestorpkg->name, childpkg->name); + } + } +} + /* Re-order a list of target packages with respect to their dependencies. * * Example (reverse == 0): @@ -179,7 +215,7 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, { alpm_list_t *newtargs = NULL; alpm_list_t *vertices = NULL; - alpm_list_t *vptr; + alpm_list_t *i; alpm_graph_t *vertex; if(targets == NULL) { @@ -190,67 +226,35 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, vertices = dep_graph_init(handle, targets, ignore); - vptr = vertices; + i = vertices; vertex = vertices->data; - while(vptr) { + while(i) { /* mark that we touched the vertex */ - vertex->state = -1; - int found = 0; - while(vertex->childptr && !found) { - alpm_graph_t *nextchild = vertex->childptr->data; - vertex->childptr = vertex->childptr->next; - if(nextchild->state == 0) { - found = 1; + vertex->state = ALPM_GRAPH_STATE_PROCESSING; + int switched_to_child = 0; + while(vertex->iterator && !switched_to_child) { + alpm_graph_t *nextchild = vertex->iterator->data; + vertex->iterator = vertex->iterator->next; + if(nextchild->state == ALPM_GRAPH_STATE_UNPROCESSED) { + switched_to_child = 1; nextchild->parent = vertex; vertex = nextchild; - } else if(nextchild->state == -1) { - /* child is an ancestor of vertex */ - alpm_graph_t *transvertex = vertex; - - if(!alpm_list_find_ptr(targets, nextchild->data)) { - /* child is not part of the transaction, not a problem */ - continue; - } - - /* find the nearest parent that's part of the transaction */ - while(transvertex) { - if(alpm_list_find_ptr(targets, transvertex->data)) { - break; - } - transvertex = transvertex->parent; - } - - if(!transvertex || transvertex == nextchild) { - /* no transaction package in our ancestry or the package has - * a circular dependency with itself, not a problem */ - } else { - alpm_pkg_t *transpkg = transvertex->data; - alpm_pkg_t *childpkg = nextchild->data; - _alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n")); - if(reverse) { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be removed after its %s dependency\n"), - transpkg->name, childpkg->name); - } else { - _alpm_log(handle, ALPM_LOG_WARNING, - _("%s will be installed before its %s dependency\n"), - transpkg->name, childpkg->name); - } - } + } else if(nextchild->state == ALPM_GRAPH_STATE_PROCESSING) { + _alpm_warn_dep_cycle(handle, targets, vertex, nextchild, reverse); } } - if(!found) { + if(!switched_to_child) { if(alpm_list_find_ptr(targets, vertex->data)) { newtargs = alpm_list_add(newtargs, vertex->data); } /* mark that we've left this vertex */ - vertex->state = 1; + vertex->state = ALPM_GRAPH_STATE_PROCESSED; vertex = vertex->parent; if(!vertex) { /* top level vertex reached, move to the next unprocessed vertex */ - for( vptr = vptr->next; vptr; vptr = vptr->next) { - vertex = vptr->data; - if(vertex->state == 0) { + for(i = i->next; i; i = i->next) { + vertex = i->data; + if(vertex->state == ALPM_GRAPH_STATE_UNPROCESSED) { break; } } |