Resolvedeps rework

I divided resolvedeps into 2 functions. The new _alpm_resolvedep function
will resolve one dependency, for example the 'foo>=1.0-1' dependency.  It
can be useful in sync_addtarget refactoring.

The resolvedeps parameters were changed, to be coherent with recursedeps:
* the target-list is an alpm_list* instead of alpm_list**. This is OK,
  because alpm_list_add == alpm_list_add_last
* syncpkg param was removed. list contains the to-be-installed packages,
  resolvedeps will add the required dependencies into this list
* trans param was removed, it was used in QUESTION() only, which can be used
  on the main (handle->trans) transaction only (because the front-end cannot
  access our pseudo-transactions at all!).

The patch fixes some wrong dynamic pmdepmissing_t usage.

I did a behavior change (and sync1003.py was modified accordingly), which
needs some explanation: The old resolvedeps didn't elect packages from
'remove' list. I've dropped this because I don't want that 2nd excluding
list param. In fact, in real life, we ~never need this rule. Resolvedeps is
called before checkconflicts, so only -Su's %REPLACES% packages are sitting
in 'remove' list. This means, that we have the replacement packages in our
target list. Usually "foo replaces bar" means, that bar isn't in our repos
any more, so resolvedeps *cannot* elect it; but usually it won't try it at
all, because foo is in the target list, and it is expected to satisfy
'bar>=1.0-1'-like dependencies too. Since checkdeps and checkconflicts is
done after resolvedeps, this cannot cause any harm.

Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Signed-off-by: Dan McGee <dan@archlinux.org>

4 files changed, 92 insertions, 132 deletions

diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index cd154070..ab027074 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -534,137 +534,106 @@ void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int include_explicit)
 	}
 }
 
-/* populates *list with packages that need to be installed to satisfy all
- * dependencies (recursive) for syncpkg
+/* helper function for resolvedeps: search for dep satisfier in dbs */
+pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs, alpm_list_t *excluding, pmpkg_t *tpkg)
+{
+	alpm_list_t *i, *j;
+	/* 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(_alpm_pkg_should_ignore(pkg)) {
+				int install;
+				QUESTION(handle->trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, pkg,
+			                 tpkg, NULL, &install);
+				if(!install) {
+					continue;
+				}
+			}
+			return(pkg);
+		}
+	}
+	/* 2. satisfiers (skip literals here) */
+	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) &&
+			             !_alpm_pkg_find(excluding, pkg->name)) {
+				if(_alpm_pkg_should_ignore(pkg)) {
+					int install;
+					QUESTION(handle->trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, pkg,
+				                 tpkg, NULL, &install);
+					if(!install) {
+						continue;
+					}
+				}
+				return(pkg);
+			}
+		}
+	}
+	return(NULL);
+}
+
+/* populates list with packages that need to be installed to satisfy all
+ * dependencies of packages in list
  *
  * @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 *remove, pmtrans_t *trans, alpm_list_t **data)
+int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t *list,
+                      alpm_list_t *remove, alpm_list_t **data)
 {
-	alpm_list_t *i, *j, *k;
+	alpm_list_t *i, *j;
 	alpm_list_t *targ;
 	alpm_list_t *deps = NULL;
 
 	ALPM_LOG_FUNC;
 
-	if(local == NULL || dbs_sync == NULL || syncpkg == NULL || list == NULL) {
+	if(local == NULL || dbs_sync == NULL) {
 		return(-1);
 	}
 
 	_alpm_log(PM_LOG_DEBUG, "started resolving dependencies\n");
-	targ = alpm_list_add(NULL, syncpkg);
-	deps = alpm_checkdeps(local, 0, remove, targ);
-	alpm_list_free(targ);
-
-	if(deps == NULL) {
-		return(0);
-	}
-
-	for(i = deps; i; i = i->next) {
-		int found = 0;
-		pmdepmissing_t *miss = i->data;
-		pmdepend_t *missdep = alpm_miss_get_dep(miss);
-		pmpkg_t *sync = NULL;
-
-		/* 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_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;
-			}
-		}
-		if(found) {
-			continue;
-		}
-
-		/* find the package in one of the repositories */
-		/* check literals */
-		for(j = dbs_sync; j && !found; j = j->next) {
-			sync = _alpm_db_get_pkgfromcache(j->data, missdep->name);
-			if(!sync) {
+	for(i = list; i; i = i->next) {
+		pmpkg_t *tpkg = i->data;
+		targ = alpm_list_add(NULL, tpkg);
+		deps = alpm_checkdeps(local, 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 list already satisfies this dependency */
+			if(_alpm_find_dep_satisfier(list, missdep)) {
 				continue;
 			}
-			found = alpm_depcmp(sync, missdep) && !_alpm_pkg_find(remove, alpm_pkg_get_name(sync))
-				&& !_alpm_pkg_find(*list, alpm_pkg_get_name(sync));
-			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();
-				STRDUP(dummypkg->name, miss->target, RET_ERR(PM_ERR_MEMORY, -1));
-				QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, sync, dummypkg, NULL, &found);
-				_alpm_pkg_free(dummypkg);
-			}
-		}
-		/*TODO this autoresolves the first 'satisfier' package... we should fix this
-		 * somehow */
-		/* check provides */
-		/* we don't check literals again to avoid duplicated PM_TRANS_CONV_INSTALL_IGNOREPKG messages */
-		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) && strcmp(sync->name, missdep->name)
-					&& !_alpm_pkg_find(remove, alpm_pkg_get_name(sync))
-					&& !_alpm_pkg_find(*list, alpm_pkg_get_name(sync));
-				if(!found) {
-					continue;
-				}
-				if(_alpm_pkg_should_ignore(sync)) {
-					pmpkg_t *dummypkg = _alpm_pkg_new();
-					STRDUP(dummypkg->name, miss->target, RET_ERR(PM_ERR_MEMORY, -1));
-					QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, sync, dummypkg, NULL, &found);
-					_alpm_pkg_free(dummypkg);
-				}
-			}
-		}
-
-		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) {
-				MALLOC(miss, sizeof(pmdepmissing_t),/*nothing*/);
-				if(!miss) {
-					pm_errno = PM_ERR_MEMORY;
-					FREELIST(*data);
-					goto error;
+			/* find a satisfier package in the given repositories */
+			pmpkg_t *spkg = _alpm_resolvedep(missdep, dbs_sync, list, tpkg);
+			if(!spkg) {
+				pm_errno = PM_ERR_UNSATISFIED_DEPS;
+				char *missdepstring = alpm_dep_get_string(missdep);
+				_alpm_log(PM_LOG_ERROR, _("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);
+					}
 				}
-				*miss = *(pmdepmissing_t *)i->data;
-				*data = alpm_list_add(*data, miss);
-			}
-			pm_errno = PM_ERR_UNSATISFIED_DEPS;
-			goto error;
-		} 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;
+				alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
+				alpm_list_free(deps);
+				return(-1);
+			}  else {
+				_alpm_log(PM_LOG_DEBUG, "pulling dependency %s (needed by %s)\n",
+					  alpm_pkg_get_name(spkg), alpm_pkg_get_name(tpkg));
+				list = alpm_list_add(list, spkg);
 			}
 		}
+		alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
+		alpm_list_free(deps);
 	}
-
 	_alpm_log(PM_LOG_DEBUG, "finished resolving dependencies\n");
-
-	alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
-	alpm_list_free(deps);
-
 	return(0);
-
-error:
-	FREELIST(deps);
-	return(-1);
 }
 
 /* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */
diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h
index 1e539b74..2d20bb66 100644
--- a/lib/libalpm/deps.h
+++ b/lib/libalpm/deps.h
@@ -47,9 +47,9 @@ pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdepend_t *dep,
 void _alpm_depmiss_free(pmdepmissing_t *miss);
 alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, int reverse);
 void _alpm_recursedeps(pmdb_t *db, alpm_list_t *targs, int include_explicit);
-int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg,
-		alpm_list_t **list, alpm_list_t *remove, pmtrans_t *trans, alpm_list_t
-		**data);
+pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs, alpm_list_t *excluding, pmpkg_t *tpkg);
+int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t *list,
+		      alpm_list_t *remove, alpm_list_t **data);
 int _alpm_dep_edge(pmpkg_t *pkg1, pmpkg_t *pkg2);
 pmdepend_t *_alpm_splitdep(const char *depstring);
 pmpkg_t *_alpm_find_dep_satisfier(alpm_list_t *pkgs, pmdepend_t *dep);
diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c
index 3dc54d0a..9336a2e3 100644
--- a/lib/libalpm/sync.c
+++ b/lib/libalpm/sync.c
@@ -462,14 +462,10 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync
 			}
 		}
 
-		for(i = trans->packages; i; i = i->next) {
-			pmpkg_t *spkg = ((pmsyncpkg_t *)i->data)->pkg;
-			if(_alpm_resolvedeps(db_local, dbs_sync, spkg, &list,
-						remove, trans, data) == -1) {
-				/* pm_errno is set by resolvedeps */
-				ret = -1;
-				goto cleanup;
-			}
+		if(_alpm_resolvedeps(db_local, dbs_sync, list, remove, data) == -1) {
+			/* pm_errno is set by resolvedeps */
+			ret = -1;
+			goto cleanup;
 		}
 
 		for(i = pulled->next; i; i = i->next) {
diff --git a/pactest/tests/sync1003.py b/pactest/tests/sync1003.py
index 3fd9799d..cd980637 100644
--- a/pactest/tests/sync1003.py
+++ b/pactest/tests/sync1003.py
@@ -4,23 +4,18 @@ sp1 = pmpkg("pkg1", "1.0-2")
 sp1.replaces = [ "pkg2" ]
 self.addpkg2db("sync", sp1)
 
-sp2 = pmpkg("pkg2", "1.0-2")
-self.addpkg2db("sync", sp2)
-
-sp3 = pmpkg("pkg3", "1.0-2")
-sp3.depends = ["pkg2=1.0-2"]
-self.addpkg2db("sync", sp3)
-
-lp1 = pmpkg("pkg1", "1.0-1")
-self.addpkg2db("local", lp1)
-
-lp2 = pmpkg("pkg2", "1.0-2")
+lp2 = pmpkg("pkg2", "1.0-1")
 self.addpkg2db("local", lp2)
 
 lp3 = pmpkg("pkg3", "1.0-1")
+lp3.depends = [ "pkg2=1.0" ]
 self.addpkg2db("local", lp3)
 
 self.args = "-Su"
 
 self.addrule("PACMAN_RETCODE=1")
+self.addrule("!PKG_EXIST=pkg1")
 self.addrule("PKG_EXIST=pkg2")
+self.addrule("PKG_EXIST=pkg3")
+self.addrule("PKG_VERSION=pkg2|1.0-1")
+self.addrule("PKG_VERSION=pkg3|1.0-1")