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: */