summaryrefslogtreecommitdiff
path: root/lib/libalpm/deps.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libalpm/deps.c')
-rw-r--r--lib/libalpm/deps.c858
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: */