1 files changed, 177 insertions, 98 deletions

diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index 26f9b16d..ea579cda 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -1,7 +1,7 @@
 /*
  *  deps.c
  *
- *  Copyright (c) 2006-2010 Pacman Development Team <pacman-dev@archlinux.org>
+ *  Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org>
  *  Copyright (c) 2002-2006 by Judd Vinet <jvinet@zeroflux.org>
  *  Copyright (c) 2005 by Aurelien Foret <orelien@chez.com>
  *  Copyright (c) 2005, 2006 by Miklos Vajna <vmiklos@frugalware.org>
@@ -34,7 +34,6 @@
 #include "graph.h"
 #include "package.h"
 #include "db.h"
-#include "cache.h"
 #include "handle.h"
 
 void _alpm_dep_free(pmdepend_t *dep)
@@ -140,8 +139,8 @@ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, int reverse)
 		vertex->state = -1;
 		int found = 0;
 		while(vertex->childptr && !found) {
-			pmgraph_t *nextchild = (vertex->childptr)->data;
-			vertex->childptr = (vertex->childptr)->next;
+			pmgraph_t *nextchild = vertex->childptr->data;
+			vertex->childptr = vertex->childptr->next;
 			if (nextchild->state == 0) {
 				found = 1;
 				nextchild->parent = vertex;
@@ -150,12 +149,15 @@ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, int reverse)
 			else if(nextchild->state == -1) {
 				pmpkg_t *vertexpkg = vertex->data;
 				pmpkg_t *childpkg = nextchild->data;
+				const char *message;
+
 				_alpm_log(PM_LOG_WARNING, _("dependency cycle detected:\n"));
 				if(reverse) {
-					_alpm_log(PM_LOG_WARNING, _("%s will be removed after its %s dependency\n"), vertexpkg->name, childpkg->name);
+					message =_("%s will be removed after its %s dependency\n");
 				} else {
-					_alpm_log(PM_LOG_WARNING, _("%s will be installed before its %s dependency\n"), vertexpkg->name, childpkg->name);
+					message =_("%s will be installed before its %s dependency\n");
 				}
+				_alpm_log(PM_LOG_WARNING, message, vertexpkg->name, childpkg->name);
 			}
 		}
 		if(!found) {
@@ -196,36 +198,25 @@ pmpkg_t *_alpm_find_dep_satisfier(alpm_list_t *pkgs, pmdepend_t *dep)
 
 	for(i = pkgs; i; i = alpm_list_next(i)) {
 		pmpkg_t *pkg = i->data;
-		if(alpm_depcmp(pkg, dep)) {
+		if(_alpm_depcmp_tolerant(pkg, dep)) {
 			return(pkg);
 		}
 	}
 	return(NULL);
 }
 
-/** 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 targets an alpm_list_t* of dependencies strings to satisfy
- * @return an alpm_list_t* of missing dependencies strings
+/** Find a package satisfying a specified dependency.
+ * The dependency can include versions with depmod operators.
+ * @param pkgs an alpm_list_t* of pmpkg_t where the satisfier will be searched
+ * @param depstring package or provision name, versioned or not
+ * @return a pmpkg_t* satisfying depstring
  */
-alpm_list_t SYMEXPORT *alpm_deptest(pmdb_t *db, alpm_list_t *targets)
+pmpkg_t SYMEXPORT *alpm_find_satisfier(alpm_list_t *pkgs, const char *depstring)
 {
-	alpm_list_t *i, *ret = NULL;
-
-	for(i = targets; i; i = alpm_list_next(i)) {
-		pmdepend_t *dep;
-		char *target;
-
-		target = alpm_list_getdata(i);
-		dep = _alpm_splitdep(target);
-
-		if(!_alpm_find_dep_satisfier(_alpm_db_get_pkgcache(db), dep)) {
-			ret = alpm_list_add(ret, target);
-		}
-		_alpm_dep_free(dep);
-	}
-	return(ret);
+	pmdepend_t *dep = _alpm_splitdep(depstring);
+	pmpkg_t *pkg = _alpm_find_dep_satisfier(pkgs, dep);
+	_alpm_dep_free(dep);
+	return(pkg);
 }
 
 /** Checks dependencies and returns missing ones in a list.
@@ -234,7 +225,7 @@ alpm_list_t SYMEXPORT *alpm_deptest(pmdb_t *db, alpm_list_t *targets)
  * @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.
+ * @return an alpm_list_t* of pmpkg_t* of pmdepmissing_t pointers.
  */
 alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_list_t *pkglist, int reversedeps,
 		alpm_list_t *remove, alpm_list_t *upgrade)
@@ -242,14 +233,13 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_list_t *pkglist, int reversedeps,
 	alpm_list_t *i, *j;
 	alpm_list_t *targets, *dblist = NULL, *modified = NULL;
 	alpm_list_t *baddeps = NULL;
-	pmdepmissing_t *miss = NULL;
 
 	ALPM_LOG_FUNC;
 
 	targets = alpm_list_join(alpm_list_copy(remove), alpm_list_copy(upgrade));
 	for(i = pkglist; i; i = i->next) {
-		void *pkg = i->data;
-		if(alpm_list_find(targets, pkg, _alpm_pkg_cmp)) {
+		pmpkg_t *pkg = i->data;
+		if(_alpm_pkg_find(targets, pkg->name)) {
 			modified = alpm_list_add(modified, pkg);
 		} else {
 			dblist = alpm_list_add(dblist, pkg);
@@ -270,6 +260,7 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_list_t *pkglist, int reversedeps,
 			if(!_alpm_find_dep_satisfier(upgrade, depend) &&
 			   !_alpm_find_dep_satisfier(dblist, depend)) {
 				/* Unsatisfied dependency in the upgrade list */
+				pmdepmissing_t *miss;
 				char *missdepstring = alpm_dep_compute_string(depend);
 				_alpm_log(PM_LOG_DEBUG, "checkdeps: missing dependency '%s' for package '%s'\n",
 						missdepstring, alpm_pkg_get_name(tp));
@@ -294,6 +285,7 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_list_t *pkglist, int reversedeps,
 				if(causingpkg &&
 				   !_alpm_find_dep_satisfier(upgrade, depend) &&
 				   !_alpm_find_dep_satisfier(dblist, depend)) {
+					pmdepmissing_t *miss;
 					char *missdepstring = alpm_dep_compute_string(depend);
 					_alpm_log(PM_LOG_DEBUG, "checkdeps: transaction would break '%s' dependency of '%s'\n",
 							missdepstring, alpm_pkg_get_name(lp));
@@ -304,6 +296,7 @@ alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_list_t *pkglist, int reversedeps,
 			}
 		}
 	}
+
 	alpm_list_free(modified);
 	alpm_list_free(dblist);
 
@@ -331,89 +324,116 @@ static int dep_vercmp(const char *version1, pmdepmod_t mod,
 	return(equal);
 }
 
-int SYMEXPORT alpm_depcmp(pmpkg_t *pkg, pmdepend_t *dep)
+/* nodepversion: skip version checking */
+static int _depcmp(pmpkg_t *pkg, pmdepend_t *dep, int nodepversion)
 {
 	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;
+	int depmod;
+
+	if(nodepversion) {
+		depmod = PM_DEP_MOD_ANY;
+	} else {
+		depmod = dep->mod;
+	}
 
 	/* check (pkg->name, pkg->version) */
-	satisfy = (strcmp(pkgname, dep->name) == 0
-			&& dep_vercmp(pkgversion, dep->mod, dep->version));
+	if(pkg->name_hash && dep->name_hash
+			&& pkg->name_hash != dep->name_hash) {
+		/* skip more expensive checks */
+	} else {
+		satisfy = (strcmp(pkg->name, dep->name) == 0
+				&& dep_vercmp(pkg->version, depmod, dep->version));
+		if(satisfy) {
+			return(satisfy);
+		}
+	}
 
 	/* 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, '=');
+		const char *provision = i->data;
+		const char *provver = strchr(provision, '=');
 
 		if(provver == NULL) { /* no provision version */
-			satisfy = (dep->mod == PM_DEP_MOD_ANY
-					&& strcmp(provname, dep->name) == 0);
+			satisfy = (depmod == PM_DEP_MOD_ANY
+					&& strcmp(provision, dep->name) == 0);
 		} else {
-			*provver = '\0';
+			/* This is a bit tricker than the old code for performance reasons. To
+			 * prevent the need to copy and duplicate strings, strncmp only the name
+			 * portion if they are the same length, since there is a version and
+			 * operator in play here. Cast is to silence sign conversion warning;
+			 * we know provver >= provision if we are here. */
+			size_t namelen = (size_t)(provver - provision);
 			provver += 1;
-			satisfy = (strcmp(provname, dep->name) == 0
-					&& dep_vercmp(provver, dep->mod, dep->version));
+			satisfy = (strlen(dep->name) == namelen
+					&& strncmp(provision, dep->name, namelen) == 0
+					&& dep_vercmp(provver, depmod, dep->version));
 		}
-		free(provname);
 	}
 
 	return(satisfy);
 }
 
+/* tolerant : respects NODEPVERSION flag */
+int _alpm_depcmp_tolerant(pmpkg_t *pkg, pmdepend_t *dep)
+{
+	int nodepversion = 0;
+	int flags = alpm_trans_get_flags();
+
+	if (flags != -1) {
+		nodepversion = flags & PM_TRANS_FLAG_NODEPVERSION;
+	}
+
+	return(_depcmp(pkg, dep, nodepversion));
+}
+
+/* strict : ignores NODEPVERSION flag */
+int _alpm_depcmp(pmpkg_t *pkg, pmdepend_t *dep)
+{
+	return(_depcmp(pkg, dep, 0));
+}
+
 pmdepend_t *_alpm_splitdep(const char *depstring)
 {
 	pmdepend_t *depend;
-	char *ptr = NULL;
-	char *newstr = NULL;
+	const char *ptr, *version = NULL;
 
 	if(depstring == NULL) {
 		return(NULL);
 	}
-	STRDUP(newstr, depstring, RET_ERR(PM_ERR_MEMORY, NULL));
 
 	CALLOC(depend, 1, sizeof(pmdepend_t), RET_ERR(PM_ERR_MEMORY, 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(newstr, ">="))) {
+	if((ptr = strstr(depstring, ">="))) {
 		depend->mod = PM_DEP_MOD_GE;
-		*ptr = '\0';
-		ptr += 2;
-	} else if((ptr = strstr(newstr, "<="))) {
+		version = ptr + 2;
+	} else if((ptr = strstr(depstring, "<="))) {
 		depend->mod = PM_DEP_MOD_LE;
-		*ptr = '\0';
-		ptr += 2;
-	} else if((ptr = strstr(newstr, "="))) { /* Note: we must do =,<,> checks after <=, >= checks */
+		version = ptr + 2;
+	} else if((ptr = strstr(depstring, "="))) {
+		/* Note: we must do =,<,> checks after <=, >= checks */
 		depend->mod = PM_DEP_MOD_EQ;
-		*ptr = '\0';
-		ptr += 1;
-	} else if((ptr = strstr(newstr, "<"))) {
+		version = ptr + 1;
+	} else if((ptr = strstr(depstring, "<"))) {
 		depend->mod = PM_DEP_MOD_LT;
-		*ptr = '\0';
-		ptr += 1;
-	} else if((ptr = strstr(newstr, ">"))) {
+		version = ptr + 1;
+	} else if((ptr = strstr(depstring, ">"))) {
 		depend->mod = PM_DEP_MOD_GT;
-		*ptr = '\0';
-		ptr += 1;
+		version = ptr + 1;
 	} else {
-		/* no version specified - copy the name and return it */
+		/* no version specified, leave version and ptr NULL */
 		depend->mod = PM_DEP_MOD_ANY;
-		STRDUP(depend->name, newstr, RET_ERR(PM_ERR_MEMORY, NULL));
-		depend->version = NULL;
-		free(newstr);
-		return(depend);
 	}
 
-	/* if we get here, we have a version comparator, copy the right parts
-	 * to the right places */
-	STRDUP(depend->name, newstr, RET_ERR(PM_ERR_MEMORY, NULL));
-	STRDUP(depend->version, ptr, RET_ERR(PM_ERR_MEMORY, NULL));
-	free(newstr);
+	/* copy the right parts to the right places */
+	STRNDUP(depend->name, depstring, ptr - depstring,
+			RET_ERR(PM_ERR_MEMORY, NULL));
+	depend->name_hash = _alpm_hash_sdbm(depend->name);
+	if(version) {
+		STRDUP(depend->version, version, RET_ERR(PM_ERR_MEMORY, NULL));
+	}
 
 	return(depend);
 }
@@ -424,6 +444,7 @@ pmdepend_t *_alpm_dep_dup(const pmdepend_t *dep)
 	CALLOC(newdep, 1, sizeof(pmdepend_t), RET_ERR(PM_ERR_MEMORY, NULL));
 
 	STRDUP(newdep->name, dep->name, RET_ERR(PM_ERR_MEMORY, NULL));
+	newdep->name_hash = dep->name_hash;
 	STRDUP(newdep->version, dep->version, RET_ERR(PM_ERR_MEMORY, NULL));
 	newdep->mod = dep->mod;
 
@@ -505,6 +526,28 @@ void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int include_explicit)
 	}
 }
 
+/** Find a package satisfying a specified dependency.
+ * First look for a literal, going through each db one by one. Then look for
+ * providers. The first satisfier found is returned.
+ * The dependency can include versions with depmod operators.
+ * @param dbs an alpm_list_t* of pmdb_t where the satisfier will be searched
+ * @param depstring package or provision name, versioned or not
+ * @return a pmpkg_t* satisfying depstring
+ */
+pmpkg_t SYMEXPORT *alpm_find_dbs_satisfier(alpm_list_t *dbs, const char *depstring)
+{
+	pmdepend_t *dep;
+	pmpkg_t *pkg;
+
+	ASSERT(dbs, return(NULL));
+
+	dep = _alpm_splitdep(depstring);
+	ASSERT(dep, return(NULL));
+	pkg = _alpm_resolvedep(dep, dbs, NULL, 1);
+	_alpm_dep_free(dep);
+	return(pkg);
+}
+
 /**
  * helper function for resolvedeps: search for dep satisfier in dbs
  *
@@ -522,10 +565,14 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs,
 {
 	alpm_list_t *i, *j;
 	int ignored = 0;
+
+	alpm_list_t *providers = NULL;
+	int count;
+
 	/* 1. literals */
 	for(i = dbs; i; i = i->next) {
 		pmpkg_t *pkg = _alpm_db_get_pkgfromcache(i->data, dep->name);
-		if(pkg && alpm_depcmp(pkg, dep) && !_alpm_pkg_find(excluding, pkg->name)) {
+		if(pkg && _alpm_depcmp_tolerant(pkg, dep) && !_alpm_pkg_find(excluding, pkg->name)) {
 			if(_alpm_pkg_should_ignore(pkg)) {
 				int install = 0;
 				if (prompt) {
@@ -546,7 +593,7 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs,
 	for(i = dbs; i; i = i->next) {
 		for(j = _alpm_db_get_pkgcache(i->data); j; j = j->next) {
 			pmpkg_t *pkg = j->data;
-			if(alpm_depcmp(pkg, dep) && strcmp(pkg->name, dep->name) &&
+			if(_alpm_depcmp_tolerant(pkg, dep) && strcmp(pkg->name, dep->name) != 0 &&
 			             !_alpm_pkg_find(excluding, pkg->name)) {
 				if(_alpm_pkg_should_ignore(pkg)) {
 					int install = 0;
@@ -561,12 +608,40 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs,
 						continue;
 					}
 				}
-				_alpm_log(PM_LOG_WARNING, _("provider package was selected (%s provides %s)\n"),
-				                         pkg->name, dep->name);
-				return(pkg);
+				_alpm_log(PM_LOG_DEBUG, "provider found (%s provides %s)\n",
+						pkg->name, dep->name);
+				providers = alpm_list_add(providers, pkg);
+				/* keep looking for other providers in the all dbs */
 			}
 		}
 	}
+
+	/* first check if one provider is already installed locally */
+	for(i = providers; i; i = i->next) {
+		pmpkg_t *pkg = i->data;
+		if (_alpm_pkghash_find(_alpm_db_get_pkgcache_hash(handle->db_local), pkg->name)) {
+			alpm_list_free(providers);
+			return(pkg);
+		}
+	}
+	count = alpm_list_count(providers);
+	if (count >= 1) {
+		/* default to first provider if there is no QUESTION callback */
+		int index = 0;
+		if(count > 1) {
+			/* if there is more than one provider, we ask the user */
+			QUESTION(handle->trans, PM_TRANS_CONV_SELECT_PROVIDER,
+					providers, dep, NULL, &index);
+		}
+		if(index >= 0 && index < count) {
+			pmpkg_t *pkg = alpm_list_getdata(alpm_list_nth(providers, index));
+			alpm_list_free(providers);
+			return(pkg);
+		}
+		alpm_list_free(providers);
+		providers = NULL;
+	}
+
 	if(ignored) { /* resolvedeps will override these */
 		pm_errno = PM_ERR_PKG_IGNORED;
 	} else {
@@ -598,6 +673,7 @@ int _alpm_resolvedeps(alpm_list_t *localpkgs, alpm_list_t *dbs_sync, pmpkg_t *pk
                       alpm_list_t *preferred, alpm_list_t **packages,
                       alpm_list_t *remove, alpm_list_t **data)
 {
+	int ret = 0;
 	alpm_list_t *i, *j;
 	alpm_list_t *targ;
 	alpm_list_t *deps = NULL;
@@ -622,14 +698,18 @@ int _alpm_resolvedeps(alpm_list_t *localpkgs, alpm_list_t *dbs_sync, pmpkg_t *pk
 		targ = alpm_list_add(NULL, tpkg);
 		deps = alpm_checkdeps(localpkgs, 0, remove, targ);
 		alpm_list_free(targ);
+
 		for(j = deps; j; j = j->next) {
 			pmdepmissing_t *miss = j->data;
 			pmdepend_t *missdep = alpm_miss_get_dep(miss);
-			/* check if one of the packages in the [*packages] list already satisfies this dependency */
+			/* check if one of the packages in the [*packages] list already satisfies
+			 * this dependency */
 			if(_alpm_find_dep_satisfier(*packages, missdep)) {
+				_alpm_depmiss_free(miss);
 				continue;
 			}
-			/* check if one of the packages in the [preferred] list already satisfies this dependency */
+			/* check if one of the packages in the [preferred] list already satisfies
+			 * this dependency */
 			pmpkg_t *spkg = _alpm_find_dep_satisfier(preferred, missdep);
 			if(!spkg) {
 				/* find a satisfier package in the given repositories */
@@ -638,33 +718,32 @@ int _alpm_resolvedeps(alpm_list_t *localpkgs, alpm_list_t *dbs_sync, pmpkg_t *pk
 			if(!spkg) {
 				pm_errno = PM_ERR_UNSATISFIED_DEPS;
 				char *missdepstring = alpm_dep_compute_string(missdep);
-				_alpm_log(PM_LOG_WARNING, _("cannot resolve \"%s\", a dependency of \"%s\"\n"),
+				_alpm_log(PM_LOG_WARNING,
+						_("cannot resolve \"%s\", a dependency of \"%s\"\n"),
 						missdepstring, tpkg->name);
 				free(missdepstring);
 				if(data) {
-					pmdepmissing_t *missd = _alpm_depmiss_new(miss->target,
-							miss->depend, miss->causingpkg);
-					if(missd) {
-						*data = alpm_list_add(*data, missd);
-					}
+					*data = alpm_list_add(*data, miss);
 				}
-				alpm_list_free(*packages);
-				*packages = packages_copy;
-				alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
-				alpm_list_free(deps);
-				return(-1);
+				ret = -1;
 			} else {
 				_alpm_log(PM_LOG_DEBUG, "pulling dependency %s (needed by %s)\n",
 						alpm_pkg_get_name(spkg), alpm_pkg_get_name(tpkg));
 				*packages = alpm_list_add(*packages, spkg);
+				_alpm_depmiss_free(miss);
 			}
 		}
-		alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
 		alpm_list_free(deps);
 	}
-	alpm_list_free(packages_copy);
+
+	if(ret != 0) {
+		alpm_list_free(*packages);
+		*packages = packages_copy;
+	} else {
+		alpm_list_free(packages_copy);
+	}
 	_alpm_log(PM_LOG_DEBUG, "finished resolving dependencies\n");
-	return(0);
+	return(ret);
 }
 
 /* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */
@@ -672,7 +751,7 @@ int _alpm_dep_edge(pmpkg_t *pkg1, pmpkg_t *pkg2)
 {
 	alpm_list_t *i;
 	for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) {
-		if(alpm_depcmp(pkg2, i->data)) {
+		if(_alpm_depcmp_tolerant(pkg2, i->data)) {
 			return(1);
 		}
 	}