[pacman-dev] [PATCH] Resolvedeps rework

4 Jul 2008

From 08ea7d37ae38f26d24ba2d3aba5f7272dee2ab73 Mon Sep 17 00:00:00 2001
From: Nagy Gabor <ngaba@bibl.u-szeged.hu>
Date: Fri, 4 Jul 2008 20:18:00 +0200
Subject: [PATCH] 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.

sync1003.py now fails. This is not a bug, but a behavior change, which needs some explanation:
The old resolvedeps didn't elect packages from 'remove' list. I've dropped this (but can be
reimplemented trivially by adding a 2nd excluding list param to _alpm_resolvedep), 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. In exotic cases this is not true
(like in sync1003.py), then resolvedeps elect bar (new version). Since checkdeps and checkconflicts is done
after resolvedeps, this cannot cause any harm. (In sync1003.py pacman simply removes and reinstalls pkg2 now.)

Signed-off-by: Nagy Gabor <ngaba@bibl.u-szeged.hu>
---
 lib/libalpm/deps.c |  189 ++++++++++++++++++++++------------------------------
 lib/libalpm/deps.h |    6 +-
 lib/libalpm/sync.c |   12 +--
 3 files changed, 86 insertions(+), 121 deletions(-)

diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index e67b008..1a6da96 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, tpkg,
+			                 pkg, 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, tpkg,
+				                 pkg, 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, dummypkg, sync, 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, dummypkg, sync, 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 1e539b7..2997ab6 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 3dc54d0..9336a2e 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) {
-- 
1.5.6.1

    