diff options
Diffstat (limited to 'lib/libalpm/deps.c')
| -rw-r--r-- | lib/libalpm/deps.c | 858 |
1 files changed, 401 insertions, 457 deletions
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 9295fabe..7529ec98 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -1,10 +1,10 @@ /* * deps.c - * + * * 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> - * + * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or @@ -17,7 +17,7 @@ * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, * USA. */ @@ -26,11 +26,6 @@ #include <stdlib.h> #include <stdio.h> #include <string.h> -#ifdef __sun__ -#include <strings.h> -#endif -#include <libintl.h> -#include <math.h> /* libalpm */ #include "deps.h" @@ -41,32 +36,45 @@ #include "package.h" #include "db.h" #include "cache.h" -#include "provide.h" -#include "versioncmp.h" #include "handle.h" -extern pmhandle_t *handle; +static pmgraph_t *_alpm_graph_new(void) +{ + pmgraph_t *graph = NULL; + + MALLOC(graph, sizeof(pmgraph_t), RET_ERR(PM_ERR_MEMORY, NULL)); + + if(graph) { + graph->state = 0; + graph->data = NULL; + graph->parent = NULL; + graph->children = NULL; + graph->childptr = NULL; + } + return(graph); +} + +static void _alpm_graph_free(void *data) +{ + pmgraph_t *graph = data; + alpm_list_free(graph->children); + free(graph); +} -pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type, - pmdepmod_t depmod, const char *depname, - const char *depversion) +pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdepmod_t depmod, + const char *depname, const char *depversion) { pmdepmissing_t *miss; ALPM_LOG_FUNC; - miss = (pmdepmissing_t *)malloc(sizeof(pmdepmissing_t)); - if(miss == NULL) { - _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepmissing_t)); - RET_ERR(PM_ERR_MEMORY, NULL); - } + MALLOC(miss, sizeof(pmdepmissing_t), RET_ERR(PM_ERR_MEMORY, NULL)); - STRNCPY(miss->target, target, PKG_NAME_LEN); - miss->type = type; + strncpy(miss->target, target, PKG_NAME_LEN); miss->depend.mod = depmod; - STRNCPY(miss->depend.name, depname, PKG_NAME_LEN); + strncpy(miss->depend.name, depname, PKG_NAME_LEN); if(depversion) { - STRNCPY(miss->depend.version, depversion, PKG_VERSION_LEN); + strncpy(miss->depend.version, depversion, PKG_VERSION_LEN); } else { miss->depend.version[0] = 0; } @@ -74,21 +82,43 @@ pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type, return(miss); } -int _alpm_depmiss_isin(pmdepmissing_t *needle, alpm_list_t *haystack) +/* Convert a list of pmpkg_t * to a graph structure, + * with a edge for each dependency. + * Returns a list of vertices (one vertex = one package) + * (used by alpm_sortbydeps) + */ +static alpm_list_t *_alpm_graph_init(alpm_list_t *targets) { - alpm_list_t *i; - - ALPM_LOG_FUNC; + alpm_list_t *i, *j, *k; + alpm_list_t *vertices = NULL; + /* We create the vertices */ + for(i = targets; i; i = i->next) { + pmgraph_t *vertex = _alpm_graph_new(); + vertex->data = (void *)i->data; + vertices = alpm_list_add(vertices, vertex); + } - for(i = haystack; i; i = i->next) { - pmdepmissing_t *miss = i->data; - if(!memcmp(needle, miss, sizeof(pmdepmissing_t)) - && !memcmp(&needle->depend, &miss->depend, sizeof(pmdepend_t))) { - return(1); + /* We compute the edges */ + for(i = vertices; i; i = i->next) { + pmgraph_t *vertex_i = i->data; + pmpkg_t *p_i = vertex_i->data; + /* TODO this should be somehow combined with alpm_checkdeps */ + for(j = vertices; j; j = j->next) { + pmgraph_t *vertex_j = j->data; + pmpkg_t *p_j = vertex_j->data; + int child = 0; + for(k = alpm_pkg_get_depends(p_i); k && !child; k = k->next) { + pmdepend_t *depend = k->data; + child = alpm_depcmp(p_j, depend); + } + if(child) { + vertex_i->children = + alpm_list_add(vertex_i->children, vertex_j); + } } + vertex_i->childptr = vertex_i->children; } - - return(0); + return(vertices); } /* Re-order a list of target packages with respect to their dependencies. @@ -99,21 +129,19 @@ int _alpm_depmiss_isin(pmdepmissing_t *needle, alpm_list_t *haystack) * Target order is A,B,C,D * * Should be re-ordered to C,A,B,D - * + * * mode should be either PM_TRANS_TYPE_ADD or PM_TRANS_TYPE_REMOVE. This * affects the dependency order sortbydeps() will use. * * This function returns the new alpm_list_t* target list. * - */ + */ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode) { alpm_list_t *newtargs = NULL; - alpm_list_t *i, *j, *k, *l; - int change = 1; - int numscans = 0; - int numtargs = 0; - int maxscans; + alpm_list_t *vertices = NULL; + alpm_list_t *vptr; + pmgraph_t *vertex; ALPM_LOG_FUNC; @@ -121,90 +149,86 @@ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode) return(NULL); } - for(i = targets; i; i = i->next) { - newtargs = alpm_list_add(newtargs, i->data); - numtargs++; - } + _alpm_log(PM_LOG_DEBUG, "started sorting dependencies\n"); - maxscans = (int)sqrt(numtargs); + vertices = _alpm_graph_init(targets); - _alpm_log(PM_LOG_DEBUG, _("started sorting dependencies")); - while(change) { - alpm_list_t *tmptargs = NULL; - change = 0; - if(numscans > maxscans) { - _alpm_log(PM_LOG_DEBUG, _("possible dependency cycle detected")); - continue; - } - numscans++; - /* run thru targets, moving up packages as necessary */ - for(i = newtargs; i; i = i->next) { - pmpkg_t *p = i->data; - _alpm_log(PM_LOG_DEBUG, " sorting %s", alpm_pkg_get_name(p)); - for(j = alpm_pkg_get_depends(p); j; j = j->next) { - pmdepend_t *depend = alpm_splitdep(j->data); - pmpkg_t *q = NULL; - if(depend == NULL) { - continue; - } - /* look for depend->name -- if it's farther down in the list, then - * move it up above p - */ - for(k = i->next; k; k = k->next) { - q = k->data; - const char *qname = alpm_pkg_get_name(q); - if(!strcmp(depend->name, qname)) { - if(!_alpm_pkg_find(qname, tmptargs)) { - change = 1; - tmptargs = alpm_list_add(tmptargs, q); - } - break; - } - for(l = alpm_pkg_get_provides(q); l; l = l->next) { - const char *provname = l->data; - if(!strcmp(depend->name, provname)) { - if(!_alpm_pkg_find(qname, tmptargs)) { - change = 1; - tmptargs = alpm_list_add(tmptargs, q); - } - break; - } - } + vptr = vertices; + vertex = vertices->data; + while(vptr) { + /* mark that we touched the vertex */ + vertex->state = -1; + int found = 0; + while(vertex->childptr && !found) { + pmgraph_t *nextchild = (vertex->childptr)->data; + vertex->childptr = (vertex->childptr)->next; + if (nextchild->state == 0) { + found = 1; + nextchild->parent = vertex; + vertex = nextchild; + } + else if(nextchild->state == -1) { + pmpkg_t *vertexpkg = vertex->data; + pmpkg_t *childpkg = nextchild->data; + _alpm_log(PM_LOG_WARNING, _("dependency cycle detected:\n")); + if(mode == PM_TRANS_TYPE_REMOVE) { + _alpm_log(PM_LOG_WARNING, _("%s will be removed after its %s dependency\n"), vertexpkg->name, childpkg->name); + } else { + _alpm_log(PM_LOG_WARNING, _("%s will be installed before its %s dependency\n"), vertexpkg->name, childpkg->name); } - free(depend); } - if(!_alpm_pkg_find(alpm_pkg_get_name(p), tmptargs)) { - tmptargs = alpm_list_add(tmptargs, p); + } + if(!found) { + 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) { + vertex = vptr->data; + if (vertex->state == 0) break; + vptr = vptr->next; + } } } - FREELISTPTR(newtargs); - newtargs = tmptargs; } - _alpm_log(PM_LOG_DEBUG, _("sorting dependencies finished")); + + _alpm_log(PM_LOG_DEBUG, "sorting dependencies finished\n"); if(mode == PM_TRANS_TYPE_REMOVE) { /* we're removing packages, so reverse the order */ alpm_list_t *tmptargs = alpm_list_reverse(newtargs); /* free the old one */ - FREELISTPTR(newtargs); + alpm_list_free(newtargs); newtargs = tmptargs; } + alpm_list_free_inner(vertices, _alpm_graph_free); + alpm_list_free(vertices); + return(newtargs); } -/** Checks dependencies and returns missing ones in a list. Dependencies can include versions with depmod operators. - * @param trans pointer to the transaction object +/* Little helper function for alpm_list_find */ +static int satisfycmp(const void *pkg, const void *depend) +{ + return(!alpm_depcmp((pmpkg_t*) pkg, (pmdepend_t*) depend)); +} + +/** Checks dependencies and returns missing ones in a list. + * Dependencies can include versions with depmod operators. * @param db pointer to the local package database - * @param op transaction type - * @param packages an alpm_list_t* of packages to be checked - * @return an alpm_list_t* of missing_t pointers. + * @param reversedeps handles the backward dependencies + * @param remove an alpm_list_t* of packages to be removed + * @param upgrade an alpm_list_t* of packages to be upgraded (remove-then-upgrade) + * @return an alpm_list_t* of pmpkg_t* of missing_t pointers. */ -alpm_list_t *_alpm_checkdeps(pmtrans_t *trans, pmdb_t *db, pmtranstype_t op, - alpm_list_t *packages) +alpm_list_t SYMEXPORT *alpm_checkdeps(pmdb_t *db, int reversedeps, + alpm_list_t *remove, alpm_list_t *upgrade) { - alpm_list_t *i, *j, *k, *l; - int found = 0; + alpm_list_t *i, *j; + alpm_list_t *joined, *dblist; alpm_list_t *baddeps = NULL; pmdepmissing_t *miss = NULL; @@ -214,376 +238,271 @@ alpm_list_t *_alpm_checkdeps(pmtrans_t *trans, pmdb_t *db, pmtranstype_t op, return(NULL); } - if(op == PM_TRANS_TYPE_UPGRADE) { - /* PM_TRANS_TYPE_UPGRADE handles the backwards dependencies, ie, the packages - * listed in the requiredby field. - */ - for(i = packages; i; i = i->next) { - pmpkg_t *newpkg = i->data; - pmpkg_t *oldpkg; - if(newpkg == NULL) { - _alpm_log(PM_LOG_DEBUG, _("null package found in package list")); - continue; + joined = alpm_list_join(alpm_list_copy(remove), alpm_list_copy(upgrade)); + dblist = alpm_list_diff(_alpm_db_get_pkgcache(db), joined, _alpm_pkg_cmp); + alpm_list_free(joined); + + /* look for unsatisfied dependencies of the upgrade list */ + for(i = upgrade; i; i = i->next) { + pmpkg_t *tp = i->data; + _alpm_log(PM_LOG_DEBUG, "checkdeps: package %s-%s\n", + alpm_pkg_get_name(tp), alpm_pkg_get_version(tp)); + + for(j = alpm_pkg_get_depends(tp); j; j = j->next) { + pmdepend_t *depend = j->data; + /* 1. we check the upgrade list */ + /* 2. we check database for untouched satisfying packages */ + if(!alpm_list_find(upgrade, depend, satisfycmp) && + !alpm_list_find(dblist, depend, satisfycmp)) { + /* Unsatisfied dependency in the upgrade list */ + char *missdepstring = alpm_dep_get_string(depend); + _alpm_log(PM_LOG_DEBUG, "checkdeps: missing dependency '%s' for package '%s'\n", + missdepstring, alpm_pkg_get_name(tp)); + free(missdepstring); + miss = _alpm_depmiss_new(alpm_pkg_get_name(tp), depend->mod, + depend->name, depend->version); + baddeps = alpm_list_add(baddeps, miss); } + } + } - if((oldpkg = _alpm_db_get_pkgfromcache(db, alpm_pkg_get_name(newpkg))) == NULL) { - _alpm_log(PM_LOG_DEBUG, _("cannot find package installed '%s'"), - alpm_pkg_get_name(newpkg)); - continue; - } - for(j = alpm_pkg_get_requiredby(oldpkg); j; j = j->next) { - pmpkg_t *p; - found = 0; - if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) { - /* hmmm... package isn't installed.. */ - continue; - } - if(_alpm_pkg_find(alpm_pkg_get_name(p), packages)) { - /* this package also in the upgrade list, so don't worry about it */ - continue; - } - for(k = alpm_pkg_get_depends(p); k; k = k->next) { - /* don't break any existing dependencies (possible provides) */ - pmdepend_t *depend = alpm_splitdep(k->data); - if(depend == NULL) { - continue; - } - - /* if oldpkg satisfied this dep, and newpkg doesn't */ - if(alpm_depcmp(oldpkg, depend) && !alpm_depcmp(newpkg, depend)) { - /* we've found a dep that was removed... see if any other package - * still contains/provides the dep */ - int satisfied = 0; - for(l = packages; l; l = l->next) { - pmpkg_t *pkg = l->data; - - if(alpm_depcmp(pkg, depend)) { - _alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' has moved from '%s' to '%s'"), - depend->name, alpm_pkg_get_name(oldpkg), alpm_pkg_get_name(pkg)); - satisfied = 1; - break; - } - } - - if(!satisfied) { - /* worst case... check installed packages to see if anything else - * satisfies this... */ - for(l = _alpm_db_get_pkgcache(db); l; l = l->next) { - pmpkg_t *pkg = l->data; - - if(strcmp(alpm_pkg_get_name(pkg), alpm_pkg_get_name(oldpkg)) == 0) { - /* well, we know this one succeeds, but we're removing it... skip it */ - continue; - } - - if(alpm_depcmp(pkg, depend)) { - _alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' satisfied by installed package '%s'"), - depend->name, alpm_pkg_get_name(pkg)); - satisfied = 1; - break; - } - } - } - - if(!satisfied) { - _alpm_log(PM_LOG_DEBUG, _("checkdeps: updated '%s' won't satisfy a dependency of '%s'"), - alpm_pkg_get_name(oldpkg), alpm_pkg_get_name(p)); - miss = _alpm_depmiss_new(p->name, PM_DEP_TYPE_DEPEND, depend->mod, - depend->name, depend->version); - if(!_alpm_depmiss_isin(miss, baddeps)) { - baddeps = alpm_list_add(baddeps, miss); - } else { - FREE(miss); - } - } - } - free(depend); + if(reversedeps) { + /* reversedeps handles the backwards dependencies, ie, + * the packages listed in the requiredby field. */ + + alpm_list_t *modified = alpm_list_diff(_alpm_db_get_pkgcache(db), dblist, _alpm_pkg_cmp); + + for(i = dblist; i; i = i->next) { + pmpkg_t *lp = i->data; + for(j = alpm_pkg_get_depends(lp); j; j = j->next) { + pmdepend_t *depend = j->data; + /* we won't break this depend, if it is already broken, we ignore it */ + /* 1. check upgrade list for satisfiers */ + /* 2. check dblist for satisfiers */ + if(alpm_list_find(modified, depend, satisfycmp) && + !alpm_list_find(upgrade, depend, satisfycmp) && + !alpm_list_find(dblist, depend, satisfycmp)) { + char *missdepstring = alpm_dep_get_string(depend); + _alpm_log(PM_LOG_DEBUG, "checkdeps: transaction would break '%s' dependency of '%s'\n", + missdepstring, alpm_pkg_get_name(lp)); + free(missdepstring); + miss = _alpm_depmiss_new(lp->name, depend->mod, + depend->name, depend->version); + baddeps = alpm_list_add(baddeps, miss); } } } + alpm_list_free(modified); } - if(op == PM_TRANS_TYPE_ADD || op == PM_TRANS_TYPE_UPGRADE) { - /* DEPENDENCIES -- look for unsatisfied dependencies */ - for(i = packages; i; i = i->next) { - pmpkg_t *tp = i->data; - if(tp == NULL) { - _alpm_log(PM_LOG_DEBUG, _("null package found in package list")); - continue; - } + alpm_list_free(dblist); - for(j = alpm_pkg_get_depends(tp); j; j = j->next) { - /* split into name/version pairs */ - pmdepend_t *depend = alpm_splitdep((char*)j->data); - if(depend == NULL) { - continue; - } - - found = 0; - /* check database for literal packages */ - for(k = _alpm_db_get_pkgcache(db); k && !found; k = k->next) { - pmpkg_t *p = (pmpkg_t *)k->data; - found = alpm_depcmp(p, depend); - } - /* check database for provides matches */ - if(!found) { - alpm_list_t *m; - for(m = _alpm_db_whatprovides(db, depend->name); m && !found; m = m->next) { - /* look for a match that isn't one of the packages we're trying - * to install. this way, if we match against a to-be-installed - * package, we'll defer to the NEW one, not the one already - * installed. */ - pmpkg_t *p = m->data; - alpm_list_t *n; - int skip = 0; - for(n = packages; n && !skip; n = n->next) { - pmpkg_t *ptp = n->data; - if(strcmp(alpm_pkg_get_name(ptp), alpm_pkg_get_name(p)) == 0) { - skip = 1; - } - } - if(skip) { - continue; - } - - found = alpm_depcmp(p, depend); - } - FREELISTPTR(k); - } - /* check other targets */ - for(k = packages; k && !found; k = k->next) { - pmpkg_t *p = k->data; - found = alpm_depcmp(p, depend); - } - /* else if still not found... */ - if(!found) { - _alpm_log(PM_LOG_DEBUG, _("missing dependency '%s' for package '%s'"), - depend->name, alpm_pkg_get_name(tp)); - miss = _alpm_depmiss_new(alpm_pkg_get_name(tp), PM_DEP_TYPE_DEPEND, depend->mod, - depend->name, depend->version); - if(!_alpm_depmiss_isin(miss, baddeps)) { - baddeps = alpm_list_add(baddeps, miss); - } else { - FREE(miss); - } - } - free(depend); - } + return(baddeps); +} + +static int dep_vercmp(const char *version1, pmdepmod_t mod, + const char *version2) +{ + int equal = 0; + + if(mod == PM_DEP_MOD_ANY) { + equal = 1; + } else { + int cmp = _alpm_versioncmp(version1, version2); + switch(mod) { + case PM_DEP_MOD_EQ: equal = (cmp == 0); break; + case PM_DEP_MOD_GE: equal = (cmp >= 0); break; + case PM_DEP_MOD_LE: equal = (cmp <= 0); break; + default: equal = 1; break; } - } else if(op == PM_TRANS_TYPE_REMOVE) { - /* check requiredby fields */ - for(i = packages; i; i = i->next) { - pmpkg_t *tp = i->data; - if(tp == NULL) { - continue; - } + } + return(equal); +} - found=0; - for(j = alpm_pkg_get_requiredby(tp); j; j = j->next) { - /* Search for 'reqname' in packages for removal */ - char *reqname = j->data; - alpm_list_t *x = NULL; - for(x = packages; x; x = x->next) { - pmpkg_t *xp = x->data; - if(strcmp(reqname, alpm_pkg_get_name(xp)) == 0) { - found = 1; - break; - } - } - if(!found) { - /* check if a package in trans->packages provides this package */ - for(k = trans->packages; !found && k; k=k->next) { - pmpkg_t *spkg = NULL; - if(trans->type == PM_TRANS_TYPE_SYNC) { - pmsyncpkg_t *sync = k->data; - spkg = sync->pkg; - } else { - spkg = k->data; - } - if(spkg) { - if(alpm_list_find_str(alpm_pkg_get_provides(spkg), tp->name)) { - found = 1; - } - } - } - if(!found) { - _alpm_log(PM_LOG_DEBUG, _("checkdeps: found %s as required by %s"), - reqname, alpm_pkg_get_name(tp)); - miss = _alpm_depmiss_new(alpm_pkg_get_name(tp), PM_DEP_TYPE_DEPEND, - PM_DEP_MOD_ANY, j->data, NULL); - if(!_alpm_depmiss_isin(miss, baddeps)) { - baddeps = alpm_list_add(baddeps, miss); - } else { - FREE(miss); - } - } - } - } +int SYMEXPORT alpm_depcmp(pmpkg_t *pkg, pmdepend_t *dep) +{ + alpm_list_t *i; + + ALPM_LOG_FUNC; + + const char *pkgname = alpm_pkg_get_name(pkg); + const char *pkgversion = alpm_pkg_get_version(pkg); + int satisfy = 0; + + /* check (pkg->name, pkg->version) */ + satisfy = (strcmp(pkgname, dep->name) == 0 + && dep_vercmp(pkgversion, dep->mod, dep->version)); + + /* check provisions, format : "name version" */ + for(i = alpm_pkg_get_provides(pkg); i && !satisfy; i = i->next) { + char *provname = strdup(i->data); + char *provver = strchr(provname, ' '); + + if(provver == NULL) { /* no provision version */ + satisfy = (dep->mod == PM_DEP_MOD_ANY + && strcmp(provname, dep->name) == 0); + } else { + /* replace the space with a NULL byte, and advance ptr the version */ + *provver = '\0'; + provver += 1; + satisfy = (strcmp(provname, dep->name) == 0 + && dep_vercmp(provver, dep->mod, dep->version)); } + free(provname); } - return(baddeps); + return(satisfy); } pmdepend_t SYMEXPORT *alpm_splitdep(const char *depstring) { pmdepend_t *depend; char *ptr = NULL; + char *newstr = NULL; if(depstring == NULL) { return(NULL); } - - depend = (pmdepend_t *)malloc(sizeof(pmdepend_t)); - if(depend == NULL) { - _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepend_t)); - return(NULL); - } + newstr = strdup(depstring); + + MALLOC(depend, sizeof(pmdepend_t), return(NULL)); /* Find a version comparator if one exists. If it does, set the type and * increment the ptr accordingly so we can copy the right strings. */ - if((ptr = strstr(depstring, ">="))) { + if((ptr = strstr(newstr, ">="))) { depend->mod = PM_DEP_MOD_GE; *ptr = '\0'; ptr += 2; - } else if((ptr = strstr(depstring, "<="))) { + } else if((ptr = strstr(newstr, "<="))) { depend->mod = PM_DEP_MOD_LE; *ptr = '\0'; ptr += 2; - } else if((ptr = strstr(depstring, "="))) { + } else if((ptr = strstr(newstr, "="))) { depend->mod = PM_DEP_MOD_EQ; *ptr = '\0'; ptr += 1; } else { /* no version specified - copy in the name and return it */ depend->mod = PM_DEP_MOD_ANY; - strncpy(depend->name, depstring, PKG_NAME_LEN); + strncpy(depend->name, newstr, PKG_NAME_LEN); depend->version[0] = '\0'; + free(newstr); return(depend); } /* if we get here, we have a version comparator, copy the right parts * to the right places */ - strncpy(depend->name, depstring, PKG_NAME_LEN); + strncpy(depend->name, newstr, PKG_NAME_LEN); strncpy(depend->version, ptr, PKG_VERSION_LEN); + free(newstr); return(depend); } -/* These parameters are messy. We check if this package, given a list of - * targets (and a db), is safe to remove. We do NOT remove it if it is in the - * target list */ -static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets) +/* These parameters are messy. We check if this package, given a list of + * targets and a db is safe to remove. We do NOT remove it if it is in the + * target list, or if if the package was explictly installed and + * include_explicit == 0 */ +static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets, + int include_explicit) { - alpm_list_t *i; + alpm_list_t *i, *requiredby; if(_alpm_pkg_find(alpm_pkg_get_name(pkg), targets)) { return(0); } - /* see if it was explicitly installed */ - if(alpm_pkg_get_reason(pkg) == PM_PKG_REASON_EXPLICIT) { - _alpm_log(PM_LOG_DEBUG, _("excluding %s -- explicitly installed"), alpm_pkg_get_name(pkg)); - return(0); + if(!include_explicit) { + /* see if it was explicitly installed */ + if(alpm_pkg_get_reason(pkg) == PM_PKG_REASON_EXPLICIT) { + _alpm_log(PM_LOG_DEBUG, "excluding %s -- explicitly installed\n", + alpm_pkg_get_name(pkg)); + return(0); + } } + /* TODO: checkdeps could be used here, it handles multiple providers + * better, but that also makes it slower. + * Also this would require to first add the package to the targets list, + * then call checkdeps with it, then remove the package from the targets list + * if checkdeps detected it would break something */ + /* see if other packages need it */ - for(i = alpm_pkg_get_requiredby(pkg); i; i = i->next) { + requiredby = alpm_pkg_compute_requiredby(pkg); + for(i = requiredby; i; i = i->next) { pmpkg_t *reqpkg = _alpm_db_get_pkgfromcache(db, i->data); if(reqpkg && !_alpm_pkg_find(alpm_pkg_get_name(reqpkg), targets)) { + FREELIST(requiredby); return(0); } } + FREELIST(requiredby); /* it's ok to remove */ return(1); } -/* return a new alpm_list_t target list containing all packages in the original - * target list, as well as all their un-needed dependencies. By un-needed, - * I mean dependencies that are *only* required for packages in the target - * list, so they can be safely removed. This function is recursive. +/** + * @brief Adds unneeded dependencies to an existing list of packages. + * By unneeded, we mean dependencies that are only required by packages in the + * target list, so they can be safely removed. + * If the input list was topo sorted, the output list will be topo sorted too. + * + * @param db package database to do dependency tracing in + * @param *targs pointer to a list of packages + * @param include_explicit if 0, explicitly installed packages are not included */ -alpm_list_t *_alpm_removedeps(pmdb_t *db, alpm_list_t *targs) +void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int include_explicit) { alpm_list_t *i, *j, *k; - alpm_list_t *newtargs = targs; ALPM_LOG_FUNC; - if(db == NULL) { - return(newtargs); + if(db == NULL || targs == NULL) { + return; } for(i = targs; i; i = i->next) { pmpkg_t *pkg = i->data; for(j = alpm_pkg_get_depends(pkg); j; j = j->next) { - pmdepend_t *depend = alpm_splitdep(j->data); - pmpkg_t *deppkg; - if(depend == NULL) { - continue; - } - - deppkg = _alpm_db_get_pkgfromcache(db, depend->name); - if(deppkg == NULL) { - /* package not found... look for a provision instead */ - alpm_list_t *provides = _alpm_db_whatprovides(db, depend->name); - if(!provides) { - /* Not found, that's fine, carry on */ - _alpm_log(PM_LOG_DEBUG, _("cannot find package \"%s\" or anything that provides it!"), depend->name); - continue; - } - for(k = provides; k; k = k->next) { - pmpkg_t *provpkg = k->data; - if(can_remove_package(db, provpkg, newtargs)) { - pmpkg_t *pkg = _alpm_pkg_dup(provpkg); - - _alpm_log(PM_LOG_DEBUG, _("adding '%s' to the targets"), alpm_pkg_get_name(pkg)); - + pmdepend_t *depend = j->data; + + for(k = _alpm_db_get_pkgcache(db); k; k = k->next) { + pmpkg_t *deppkg = k->data; + if(alpm_depcmp(deppkg,depend) + && can_remove_package(db, deppkg, targs, include_explicit)) { + _alpm_log(PM_LOG_DEBUG, "adding '%s' to the targets\n", + alpm_pkg_get_name(deppkg)); /* add it to the target list */ - newtargs = alpm_list_add(newtargs, pkg); - newtargs = _alpm_removedeps(db, newtargs); - } + targs = alpm_list_add(targs, _alpm_pkg_dup(deppkg)); } - FREELISTPTR(provides); - } else if(can_remove_package(db, deppkg, newtargs)) { - pmpkg_t *pkg = _alpm_pkg_dup(deppkg); - - _alpm_log(PM_LOG_DEBUG, _("adding '%s' to the targets"), alpm_pkg_get_name(pkg)); - - /* add it to the target list */ - newtargs = alpm_list_add(newtargs, pkg); - newtargs = _alpm_removedeps(db, newtargs); } - free(depend); } } - - return(newtargs); } /* populates *list with packages that need to be installed to satisfy all * dependencies (recursive) for syncpkg * - * make sure *list and *trail are already initialized + * @param remove contains packages elected for removal + * make sure **list is already initialized */ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, - alpm_list_t *list, alpm_list_t *trail, pmtrans_t *trans, - alpm_list_t **data) + alpm_list_t **list, alpm_list_t *remove, pmtrans_t *trans, alpm_list_t **data) { - alpm_list_t *i, *j; + alpm_list_t *i, *j, *k; alpm_list_t *targ; alpm_list_t *deps = NULL; ALPM_LOG_FUNC; - if(local == NULL || dbs_sync == NULL || syncpkg == NULL) { + if(local == NULL || dbs_sync == NULL || syncpkg == NULL || list == NULL) { return(-1); } - _alpm_log(PM_LOG_DEBUG, _("started resolving dependencies")); + _alpm_log(PM_LOG_DEBUG, "started resolving dependencies\n"); targ = alpm_list_add(NULL, syncpkg); - deps = _alpm_checkdeps(trans, local, PM_TRANS_TYPE_ADD, targ); - FREELISTPTR(targ); + deps = alpm_checkdeps(local, 0, remove, targ); + alpm_list_free(targ); if(deps == NULL) { return(0); @@ -592,14 +511,17 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, for(i = deps; i; i = i->next) { int found = 0; pmdepmissing_t *miss = i->data; + pmdepend_t *missdep = &(miss->depend); pmpkg_t *sync = NULL; - /* check if one of the packages in *list already provides this dependency */ - for(j = list; j && !found; j = j->next) { + /* check if one of the packages in *list already satisfies this dependency */ + for(j = *list; j && !found; j = j->next) { pmpkg_t *sp = j->data; - if(alpm_list_find_str(alpm_pkg_get_provides(sp), miss->depend.name)) { - _alpm_log(PM_LOG_DEBUG, _("%s provides dependency %s -- skipping"), - alpm_pkg_get_name(sp), miss->depend.name); + if(alpm_depcmp(sp, missdep)) { + char *missdepstring = alpm_dep_get_string(missdep); + _alpm_log(PM_LOG_DEBUG, "%s satisfies dependency %s -- skipping\n", + alpm_pkg_get_name(sp), missdepstring); + free(missdepstring); found = 1; } } @@ -609,31 +531,53 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, /* find the package in one of the repositories */ /* check literals */ - for(j = dbs_sync; !sync && j; j = j->next) { - sync = _alpm_db_get_pkgfromcache(j->data, miss->depend.name); + for(j = dbs_sync; j && !found; j = j->next) { + sync = _alpm_db_get_pkgfromcache(j->data, missdep->name); + if(!sync) { + continue; + } + found = alpm_depcmp(sync, missdep) && !_alpm_pkg_find(alpm_pkg_get_name(sync), remove); + if(!found) { + continue; + } + /* If package is in the ignorepkg list, ask before we pull it */ + if(_alpm_pkg_should_ignore(sync)) { + pmpkg_t *dummypkg = _alpm_pkg_new(miss->target, NULL); + QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, dummypkg, sync, NULL, &found); + _alpm_pkg_free(dummypkg); + } } - /*TODO this autoresolves the first 'provides' package... we should fix this + /*TODO this autoresolves the first 'satisfier' package... we should fix this * somehow */ /* check provides */ - if(!sync) { - for(j = dbs_sync; !sync && j; j = j->next) { - alpm_list_t *provides; - provides = _alpm_db_whatprovides(j->data, miss->depend.name); - if(provides) { - sync = provides->data; + for(j = dbs_sync; j && !found; j = j->next) { + for(k = _alpm_db_get_pkgcache(j->data); k && !found; k = k->next) { + sync = k->data; + if(!sync) { + continue; + } + found = alpm_depcmp(sync, missdep) && !_alpm_pkg_find(alpm_pkg_get_name(sync), remove); + if(!found) { + continue; + } + if(_alpm_pkg_should_ignore(sync)) { + pmpkg_t *dummypkg = _alpm_pkg_new(miss->target, NULL); + QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, dummypkg, sync, NULL, &found); + _alpm_pkg_free(dummypkg); } - FREELISTPTR(provides); } } - if(!sync) { - _alpm_log(PM_LOG_ERROR, _("cannot resolve dependencies for \"%s\" (\"%s\" is not in the package set)"), - miss->target, miss->depend.name); + if(!found) { + char *missdepstring = alpm_dep_get_string(missdep); + _alpm_log(PM_LOG_ERROR, _("cannot resolve \"%s\", a dependency of \"%s\"\n"), + missdepstring, miss->target); + free(missdepstring); if(data) { - if((miss = (pmdepmissing_t *)malloc(sizeof(pmdepmissing_t))) == NULL) { - _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepmissing_t)); - FREELIST(*data); + MALLOC(miss, sizeof(pmdepmissing_t),/*nothing*/); + if(!miss) { pm_errno = PM_ERR_MEMORY; + FREELIST(*data); goto error; } *miss = *(pmdepmissing_t *)i->data; @@ -641,54 +585,17 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, } pm_errno = PM_ERR_UNSATISFIED_DEPS; goto error; - } - if(_alpm_pkg_find(alpm_pkg_get_name(sync), list)) { - /* this dep is already in the target list */ - _alpm_log(PM_LOG_DEBUG, _("dependency %s is already in the target list -- skipping"), - alpm_pkg_get_name(sync)); - continue; - } - - if(!_alpm_pkg_find(alpm_pkg_get_name(sync), trail)) { - /* check pmo_ignorepkg and pmo_s_ignore to make sure we haven't pulled in - * something we're not supposed to. - */ - int usedep = 1; - if(alpm_list_find_str(handle->ignorepkg, alpm_pkg_get_name(sync))) { - pmpkg_t *dummypkg = _alpm_pkg_new(miss->target, NULL); - QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, dummypkg, sync, NULL, &usedep); - FREEPKG(dummypkg); - } - if(usedep) { - trail = alpm_list_add(trail, sync); - if(_alpm_resolvedeps(local, dbs_sync, sync, list, trail, trans, data)) { - goto error; - } - _alpm_log(PM_LOG_DEBUG, _("pulling dependency %s (needed by %s)"), - alpm_pkg_get_name(sync), alpm_pkg_get_name(syncpkg)); - list = alpm_list_add(list, sync); - } else { - _alpm_log(PM_LOG_ERROR, _("cannot resolve dependencies for \"%s\""), miss->target); - if(data) { - if((miss = (pmdepmissing_t *)malloc(sizeof(pmdepmissing_t))) == NULL) { - _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepmissing_t)); - FREELIST(*data); - pm_errno = PM_ERR_MEMORY; - goto error; - } - *miss = *(pmdepmissing_t *)i->data; - *data = alpm_list_add(*data, miss); - } - pm_errno = PM_ERR_UNSATISFIED_DEPS; + } else { + _alpm_log(PM_LOG_DEBUG, "pulling dependency %s (needed by %s)\n", + alpm_pkg_get_name(sync), alpm_pkg_get_name(syncpkg)); + *list = alpm_list_add(*list, sync); + if(_alpm_resolvedeps(local, dbs_sync, sync, list, remove, trans, data)) { goto error; } - } else { - /* cycle detected -- skip it */ - _alpm_log(PM_LOG_DEBUG, _("dependency cycle detected: %s"), sync->name); } } - - _alpm_log(PM_LOG_DEBUG, _("finished resolving dependencies")); + + _alpm_log(PM_LOG_DEBUG, "finished resolving dependencies\n"); FREELIST(deps); @@ -699,58 +606,95 @@ error: return(-1); } -const char SYMEXPORT *alpm_dep_get_target(pmdepmissing_t *miss) +const char SYMEXPORT *alpm_miss_get_target(const pmdepmissing_t *miss) { ALPM_LOG_FUNC; /* Sanity checks */ - ASSERT(handle != NULL, return(NULL)); ASSERT(miss != NULL, return(NULL)); return miss->target; } -pmdeptype_t SYMEXPORT alpm_dep_get_type(pmdepmissing_t *miss) +pmdepend_t SYMEXPORT *alpm_miss_get_dep(pmdepmissing_t *miss) { ALPM_LOG_FUNC; /* Sanity checks */ - ASSERT(handle != NULL, return(-1)); - ASSERT(miss != NULL, return(-1)); + ASSERT(miss != NULL, return(NULL)); - return miss->type; + return &(miss->depend); } -pmdepmod_t SYMEXPORT alpm_dep_get_mod(pmdepmissing_t *miss) +pmdepmod_t SYMEXPORT alpm_dep_get_mod(const pmdepend_t *dep) { ALPM_LOG_FUNC; /* Sanity checks */ - ASSERT(handle != NULL, return(-1)); - ASSERT(miss != NULL, return(-1)); + ASSERT(dep != NULL, return(-1)); - return miss->depend.mod; + return dep->mod; } -const char SYMEXPORT *alpm_dep_get_name(pmdepmissing_t *miss) +const char SYMEXPORT *alpm_dep_get_name(const pmdepend_t *dep) { ALPM_LOG_FUNC; /* Sanity checks */ - ASSERT(handle != NULL, return(NULL)); - ASSERT(miss != NULL, return(NULL)); + ASSERT(dep != NULL, return(NULL)); - return miss->depend.name; + return dep->name; } -const char SYMEXPORT *alpm_dep_get_version(pmdepmissing_t *miss) +const char SYMEXPORT *alpm_dep_get_version(const pmdepend_t *dep) { ALPM_LOG_FUNC; /* Sanity checks */ - ASSERT(handle != NULL, return(NULL)); - ASSERT(miss != NULL, return(NULL)); + ASSERT(dep != NULL, return(NULL)); + + return dep->version; +} + +/** Reverse of splitdep; make a dep string from a pmdepend_t struct. + * The string must be freed! + * @param dep the depend to turn into a string + * @return a string-formatted dependency with operator if necessary + */ +char SYMEXPORT *alpm_dep_get_string(const pmdepend_t *dep) +{ + char *opr, *str = NULL; + size_t len; + + ALPM_LOG_FUNC; + + /* Sanity checks */ + ASSERT(dep != NULL, return(NULL)); + + switch(dep->mod) { + case PM_DEP_MOD_ANY: + opr = ""; + break; + case PM_DEP_MOD_GE: + opr = ">="; + break; + case PM_DEP_MOD_LE: + opr = "<="; + break; + case PM_DEP_MOD_EQ: + opr = "="; + break; + default: + opr = ""; + break; + } + + /* we can always compute len and print the string like this because opr + * and ver will be empty when PM_DEP_MOD_ANY is the depend type */ + len = strlen(dep->name) + strlen(opr) + strlen(dep->version) + 1; + MALLOC(str, len, RET_ERR(PM_ERR_MEMORY, NULL)); + snprintf(str, len, "%s%s%s", dep->name, opr, dep->version); - return miss->depend.version; + return(str); } /* vim: set ts=2 sw=2 noet: */ |