summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/libalpm/deps.c155
-rw-r--r--lib/libalpm/deps.h3
-rw-r--r--lib/libalpm/remove.c2
-rw-r--r--lib/libalpm/sync.c9
4 files changed, 80 insertions, 89 deletions
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index cf7605ee..9761b2cb 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -90,69 +90,9 @@ static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep)
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)
+static int ptr_cmp(const void *p, const void *q)
{
- alpm_list_t *ignore = NULL;
- int ret = _alpm_pkg_in_dep_tree(pkg1, pkg2, targets, &ignore);
- alpm_list_free(ignore);
- return ret;
+ return (p != q);
}
/* Convert a list of alpm_pkg_t * to a graph structure,
@@ -160,10 +100,14 @@ static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2,
* Returns a list of vertices (one vertex = one package)
* (used by alpm_sortbydeps)
*/
-static alpm_list_t *dep_graph_init(alpm_list_t *targets)
+static alpm_list_t *dep_graph_init(alpm_handle_t *handle,
+ alpm_list_t *targets, alpm_list_t *ignore)
{
alpm_list_t *i, *j;
alpm_list_t *vertices = NULL;
+ alpm_list_t *localpkgs = alpm_list_diff(
+ alpm_db_get_pkgcache(handle->db_local), ignore, ptr_cmp);
+
/* We create the vertices */
for(i = targets; i; i = i->next) {
alpm_graph_t *vertex = _alpm_graph_new();
@@ -179,13 +123,32 @@ 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, targets)) {
+ if(_alpm_pkg_depends_on(p_i, p_j)) {
+ vertex_i->children =
+ alpm_list_add(vertex_i->children, vertex_j);
+ }
+ }
+
+ /* lazily add local packages to the dep graph so they don't
+ * get resolved unnecessarily */
+ j = localpkgs;
+ while(j) {
+ alpm_list_t *next = j->next;
+ if(_alpm_pkg_depends_on(p_i, j->data)) {
+ alpm_graph_t *vertex_j = _alpm_graph_new();
+ vertex_j->data = (void *)j->data;
+ vertices = alpm_list_add(vertices, vertex_j);
vertex_i->children =
alpm_list_add(vertex_i->children, vertex_j);
+ localpkgs = alpm_list_remove_item(localpkgs, j);
+ free(j);
}
+ j = next;
}
+
vertex_i->childptr = vertex_i->children;
}
+ alpm_list_free(localpkgs);
return vertices;
}
@@ -198,13 +161,15 @@ static alpm_list_t *dep_graph_init(alpm_list_t *targets)
*
* Should be re-ordered to C,A,B,D
*
+ * packages listed in ignore will not be used to detect indirect dependencies
+ *
* if reverse is > 0, the dependency order will be reversed.
*
* This function returns the new alpm_list_t* target list.
*
*/
alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle,
- alpm_list_t *targets, int reverse)
+ alpm_list_t *targets, alpm_list_t *ignore, int reverse)
{
alpm_list_t *newtargs = NULL;
alpm_list_t *vertices = NULL;
@@ -217,7 +182,7 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle,
_alpm_log(handle, ALPM_LOG_DEBUG, "started sorting dependencies\n");
- vertices = dep_graph_init(targets);
+ vertices = dep_graph_init(handle, targets, ignore);
vptr = vertices;
vertex = vertices->data;
@@ -232,34 +197,56 @@ alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle,
found = 1;
nextchild->parent = vertex;
vertex = nextchild;
- }
- else if(nextchild->state == -1) {
- alpm_pkg_t *vertexpkg = vertex->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"),
- vertexpkg->name, childpkg->name);
+ } else if(nextchild->state == -1) {
+ /* child is an ancestor of vertex */
+ alpm_graph_t *transvertex = vertex;
+
+ if(!alpm_list_find(targets, nextchild->data, ptr_cmp)) {
+ /* 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(targets, transvertex->data, ptr_cmp)) {
+ 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_log(handle, ALPM_LOG_WARNING,
- _("%s will be installed before its %s dependency\n"),
- vertexpkg->name, childpkg->name);
+ 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);
+ }
}
}
}
if(!found) {
- newtargs = alpm_list_add(newtargs, vertex->data);
+ if(alpm_list_find(targets, vertex->data, ptr_cmp)) {
+ newtargs = alpm_list_add(newtargs, vertex->data);
+ }
/* mark that we've left this vertex */
vertex->state = 1;
vertex = vertex->parent;
if(!vertex) {
- vptr = vptr->next;
- while(vptr) {
+ /* 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) break;
- vptr = vptr->next;
+ if(vertex->state == 0) {
+ break;
+ }
}
}
}
diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h
index 1fbeff95..8cf5ad22 100644
--- a/lib/libalpm/deps.h
+++ b/lib/libalpm/deps.h
@@ -30,7 +30,8 @@
void _alpm_dep_free(alpm_depend_t *dep);
alpm_depend_t *_alpm_dep_dup(const alpm_depend_t *dep);
void _alpm_depmiss_free(alpm_depmissing_t *miss);
-alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle, alpm_list_t *targets, int reverse);
+alpm_list_t *_alpm_sortbydeps(alpm_handle_t *handle,
+ alpm_list_t *targets, alpm_list_t *ignore, int reverse);
int _alpm_recursedeps(alpm_db_t *db, alpm_list_t *targs, int include_explicit);
int _alpm_resolvedeps(alpm_handle_t *handle, alpm_list_t *localpkgs, alpm_pkg_t *pkg,
alpm_list_t *preferred, alpm_list_t **packages, alpm_list_t *remove,
diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c
index 7cb86ff6..2e728521 100644
--- a/lib/libalpm/remove.c
+++ b/lib/libalpm/remove.c
@@ -242,7 +242,7 @@ int _alpm_remove_prepare(alpm_handle_t *handle, alpm_list_t **data)
/* re-order w.r.t. dependencies */
_alpm_log(handle, ALPM_LOG_DEBUG, "sorting by dependencies\n");
- lp = _alpm_sortbydeps(handle, trans->remove, 1);
+ lp = _alpm_sortbydeps(handle, trans->remove, NULL, 1);
/* free the old alltargs */
alpm_list_free(trans->remove);
trans->remove = lp;
diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c
index 066f1f22..551f9269 100644
--- a/lib/libalpm/sync.c
+++ b/lib/libalpm/sync.c
@@ -471,10 +471,8 @@ int _alpm_sync_prepare(alpm_handle_t *handle, alpm_list_t **data)
* holds to package objects. */
trans->unresolvable = unresolvable;
- /* re-order w.r.t. dependencies */
alpm_list_free(trans->add);
- trans->add = _alpm_sortbydeps(handle, resolved, 0);
- alpm_list_free(resolved);
+ trans->add = resolved;
EVENT(handle, ALPM_EVENT_RESOLVEDEPS_DONE, NULL, NULL);
}
@@ -628,6 +626,11 @@ int _alpm_sync_prepare(alpm_handle_t *handle, alpm_list_t **data)
}
goto cleanup;
}
+
+ /* re-order w.r.t. dependencies */
+ alpm_list_t *add_orig = trans->add;
+ trans->add = _alpm_sortbydeps(handle, add_orig, trans->remove, 0);
+ alpm_list_free(add_orig);
}
for(i = trans->add; i; i = i->next) {
/* update download size field */
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-25 10:04:02 +0000