This code should have no effect on the pacman runtime until a future
commit which will enable the logic paths that actually remove ignored
packages. In the meantime, all pactest tests pass without any modification.
Signed-off-by: Bryan Ischo <[email protected]>
---
lib/libalpm/deps.c | 247
+++++++++++++++++++++++++++++++++++++++++++++++-----
lib/libalpm/deps.h | 4 +-
lib/libalpm/sync.c | 11 ++-
3 files changed, 231 insertions(+), 31 deletions(-)
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index 96c971a..cc20e40 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -546,17 +546,108 @@ pmpkg_t *_alpm_resolvedep(pmdepend_t *dep, alpm_list_t *dbs, alpm_list_t *exclud
return(NULL);
}
+typedef struct __pkginfo_t
+{
+ /* The package for which this info is being kept */
+ pmpkg_t *pkg;
+ /* 0 if this package has been determined to be unresolvable, meaning that
+ it has dependencies that cannot be resolved, nonzero otherwise */
+ int unresolvable;
+ /* 0 if this package was not pulled, nonzero if this package was pulled */
+ int pulled;
+ /* Packages that are immediately dependent on this package. */
+ alpm_list_t *dependents;
+ /* This marker is used to detect when a dependency cycle exists */
+ int marker;
+} pkginfo_t;
+
+
+static pkginfo_t *findinfo(alpm_list_t *list, pmpkg_t *pkg)
+{
+ alpm_list_t *i;
+
+ for (i = list; i; i = i->next) {
+ pkginfo_t *info = (pkginfo_t *) i->data;
+ if (info->pkg == pkg) {
+ return info;
+ }
+ }
+
+ return NULL;
+}
+
+
+static void mark_unresolvable(alpm_list_t *list, pkginfo_t *info)
+{
+ alpm_list_t *i;
+
+ if (info->unresolvable) {
+ return;
+ }
+
+ info->unresolvable = 1;
+
+ for (i = info->dependents; i; i = i->next) {
+ mark_unresolvable(list, findinfo(list, ((pmpkg_t *) i->data)));
+ }
+}
+
+static void info_free(pkginfo_t *info)
+{
+ alpm_list_free(info->dependents);
+ free(info);
+}
+
+
+static int is_needed(alpm_list_t *infolist, pkginfo_t *info, int marker)
+{
+ if (info->unresolvable) {
+ /* Obviously if it's already been marked unresolvable, it is not
+ needed */
+ return(0);
+ } else if (!info->pulled) {
+ /* If it's top-level (not pulled), then it's needed */
+ return(1);
+ } else {
+ /* Now, if all of the top-level packages which depend on it are
+ unresolvable, then it is unneeded */
+ alpm_list_t *i;
+ for (i = info->dependents; i; i = i->next) {
+ pmpkg_t *deppkg = (pmpkg_t *) i->data;
+ if (info->marker == marker) {
+ /* This means that a dependency loop has been detected; we've
+ already marked this package meaning that it's already been
+ seen this time through. So ignore this dependency. */
+ continue;
+ }
+
+ info->marker = marker;
+
+ if (is_needed(infolist, findinfo(infolist, deppkg), marker)) {
+ return(1);
+ }
+ }
+
+ return(0);
+ }
+}
+
+
/* populates list with packages that need to be installed to satisfy all
* dependencies of packages in list
*
* @param remove contains packages elected for removal
*/
-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_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t **list,
+ alpm_list_t **pulled, alpm_list_t *remove, alpm_list_t **data)
{
+ int marker = 0;
+ int ret = 0;
alpm_list_t *i, *j;
alpm_list_t *targ;
alpm_list_t *deps = NULL;
+ alpm_list_t *info = NULL;
+ alpm_list_t *unresolvable = NULL;
ALPM_LOG_FUNC;
@@ -565,8 +656,30 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t *list,
}
_alpm_log(PM_LOG_DEBUG, "started resolving dependencies\n");
- for(i = list; i; i = i->next) {
+
+ /* Build up a list of pkginfo_t structures describing the root level
+ packages */
+ for(i = *list; i; i = i->next) {
+ pkginfo_t *thisinfo;
+ thisinfo = (pkginfo_t *) malloc(sizeof(pkginfo_t));
+ if (thisinfo == NULL) {
+ pm_errno = PM_ERR_MEMORY;
+ ret = -1;
+ goto cleanup;
+ }
+ thisinfo->pkg = i->data;
+ thisinfo->unresolvable = 0;
+ thisinfo->pulled = 0;
+ thisinfo->dependents = NULL;
+ thisinfo->marker = 0;
+ info = alpm_list_add(info, thisinfo);
+ }
+
+ /* Now resolve */
+ for(i = *list; i; i = i->next) {
pmpkg_t *tpkg = i->data;
+ /* Find the info for tpkg */
+ pkginfo_t *tinfo = findinfo(info, tpkg);
targ = alpm_list_add(NULL, tpkg);
deps = alpm_checkdeps(_alpm_db_get_pkgcache(local), 0, remove, targ);
alpm_list_free(targ);
@@ -574,38 +687,124 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t *list,
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)) {
+ pmpkg_t *spkg = _alpm_find_dep_satisfier(*list, missdep);
+ if(spkg != NULL) {
+ /* Check spkg to make sure that it was not unresolvable; if it is, mark tpkg as
+ unresolvable also */
+ pkginfo_t *sinfo = findinfo(info, spkg);
+ if (sinfo->unresolvable) {
+ mark_unresolvable(info, tinfo);
+ /* No need to do any further dependency
+ checking for tpkg, even if it has other
+ dependencies, tpkg will not be installed
+ because it is not resolvable */
+ break;
+ }
+ sinfo->dependents = alpm_list_add(sinfo->dependents, tpkg);
continue;
}
/* 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);
- }
- }
- alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
- alpm_list_free(deps);
- return(-1);
- } else {
+ spkg = _alpm_resolvedep(missdep, dbs_sync, *list, tpkg);
+ if(spkg != NULL) {
_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);
+ *list = alpm_list_add(*list, spkg);
+ pkginfo_t *sinfo;
+ sinfo = (pkginfo_t *) malloc(sizeof(pkginfo_t));
+ if (sinfo == NULL) {
+ pm_errno = PM_ERR_MEMORY;
+ ret = -1;
+ goto cleanup;
+ }
+ sinfo->pkg = spkg;
+ sinfo->unresolvable = 0;
+ sinfo->pulled = 1;
+ sinfo->dependents = alpm_list_add(NULL, tpkg);
+ info = alpm_list_add(info, sinfo);
+ } else {
+ /* tpkg is not resolvable, so mark it and all of
+ its dependents as such */
+ mark_unresolvable(info, tinfo);
}
}
alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
alpm_list_free(deps);
+ deps = NULL;
+ }
+
+ /* Build up a list of unresolvable top-level packages, so that they
+ can be queried about */
+ for(i = info; i; i = i->next) {
+ pkginfo_t *info = (pkginfo_t *) i->data;
+ if (info->unresolvable && !info->pulled) {
+ unresolvable = alpm_list_add(unresolvable, info->pkg);
+ }
+ }
+
+ /* If there were unresolvable packages, query the user to see if they
+ should be removed from the transaction */
+ if(unresolvable != NULL) {
+ int remove_unresolved = 0;
+ /* Assume for the time being that the user does not want to remove
+ the unresolved packages. A prompt to allow the user to specify
+ that they should be removed will be added in a future change. */
+ if (remove_unresolved) {
+ /* Need to remove all packages which are:
+ - unresolvable, OR
+ - are pulled elements whose entire list of top-level
+ dependents are unresolvable */
+ for (i = info; i; i = i->next) {
+ pkginfo_t *thisinfo = (pkginfo_t *) i->data;
+ if (!is_needed(info, thisinfo, ++marker)) {
+ *list = alpm_list_remove(*list, thisinfo->pkg, _alpm_pkg_cmp, NULL);
+ }
+ }
+ } else {
+ alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
+ alpm_list_free(deps);
+ deps = NULL;
+ pm_errno = PM_ERR_UNSATISFIED_DEPS;
+ _alpm_log(PM_LOG_ERROR, _("cannot resolve dependencies for:\n"));
+ for (i = unresolvable; i; i = i->next) {
+ _alpm_log(PM_LOG_ERROR, _("\t%s\n"), alpm_pkg_get_name((pmpkg_t *) i->data));
+ if (data) {
+ alpm_list_t *targ = alpm_list_add(NULL, i->data);
+ deps = alpm_checkdeps(_alpm_db_get_pkgcache(local), 0, remove, targ);
+ alpm_list_free(targ);
+ }
+ }
+ for(i = deps; i; i = i->next) {
+ pmdepmissing_t *miss = i->data;
+ pmdepmissing_t *missd = _alpm_depmiss_new(miss->target, miss->depend, miss->causingpkg);
+ if(missd) {
+ *data = alpm_list_add(*data, missd);
+ }
+ }
+ ret = -1;
+ }
}
+
+ /* Set pulled to be the last top-level item in the list */
+ *pulled = NULL;
+ for(i = *list; i; i = i->next) {
+ pkginfo_t *thisinfo = findinfo(info, i->data);
+ if (thisinfo->pulled) {
+ *pulled = i;
+ break;
+ }
+ }
+
+ cleanup:
+
+ alpm_list_free_inner(deps, (alpm_list_fn_free)_alpm_depmiss_free);
+ alpm_list_free(deps);
+ alpm_list_free_inner(info, (alpm_list_fn_free)info_free);
+ alpm_list_free(info);
+ alpm_list_free(unresolvable);
+
_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? */
diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h
index 2f3c450..f281452 100644
--- a/lib/libalpm/deps.h
+++ b/lib/libalpm/deps.h
@@ -48,8 +48,8 @@ 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);
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_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, alpm_list_t **list,
+ alpm_list_t **pulled, 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 b458874..5741262 100644
--- a/lib/libalpm/sync.c
+++ b/lib/libalpm/sync.c
@@ -417,9 +417,10 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync
}
if(!(trans->flags & PM_TRANS_FLAG_NODEPS)) {
- /* store a pointer to the last original target so we can tell what was
- * pulled by resolvedeps */
- alpm_list_t *pulled = alpm_list_last(list);
+ /* resolvedeps returns a pointer to the first element of the
+ * list which is a pulled element, and all elements after that
+ * are pulled as well */
+ alpm_list_t *pulled;
/* Resolve targets dependencies */
EVENT(trans, PM_TRANS_EVT_RESOLVEDEPS_START, NULL, NULL);
_alpm_log(PM_LOG_DEBUG, "resolving target's dependencies\n");
@@ -432,13 +433,13 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync
}
}
- if(_alpm_resolvedeps(db_local, dbs_sync, list, remove, data) == -1) {
+ if(_alpm_resolvedeps(db_local, dbs_sync, &list, &pulled, remove, data) == -1) {
/* pm_errno is set by resolvedeps */
ret = -1;
goto cleanup;
}
- for(i = pulled->next; i; i = i->next) {
+ for(i = pulled; i; i = i->next) {
pmpkg_t *spkg = i->data;
pmsyncpkg_t *sync = _alpm_sync_new(PM_PKG_REASON_DEPEND, spkg, NULL);
if(sync == NULL) {
_______________________________________________
pacman-dev mailing list
[email protected]
http://archlinux.org/mailman/listinfo/pacman-dev
