/*
* deps.c
*
- * Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org>
+ * Copyright (c) 2006-2013 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>
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include "config.h"
-
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
{
FREE(dep->name);
FREE(dep->version);
+ FREE(dep->desc);
FREE(dep);
}
FREE(miss);
}
-/* Does pkg1 depend on pkg2, ie. does pkg2 satisfy a dependency of pkg1? */
-static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2)
+/** Check if pkg2 satisfies a dependency of pkg1 */
+static int _alpm_pkg_depends_on(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2)
{
alpm_list_t *i;
for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) {
return 0;
}
+static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep)
+{
+ alpm_list_t *i;
+
+ for(i = pkgs; i; i = i->next) {
+ alpm_pkg_t *pkg = i->data;
+ if(_alpm_depcmp(pkg, dep)) {
+ return pkg;
+ }
+ }
+ return NULL;
+}
+
+/** Check if pkg2 is anywhere in pkg1's dependency tree.
+ * @param pkg1
+ * @param pkg2
+ * @param targets if a package in this list is an intermediate dependency
+ * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be
+ * reported
+ * @param ignore packages which should not be recursively checked for
+ * intermediate dependencies. Used internally for state to avoid
+ * getting stuck on cyclic dependencies.
+ * @return 1 if pkg2 is found in pkg1's dependency tree
+ */
+static int _alpm_pkg_in_dep_tree(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2,
+ alpm_list_t *targets, alpm_list_t **ignore)
+{
+ alpm_list_t *i, *pkgs = alpm_db_get_pkgcache(pkg1->handle->db_local);
+
+ if(_alpm_pkg_depends_on(pkg1, pkg2)) {
+ return 1;
+ }
+
+ *ignore = alpm_list_add(*ignore, pkg1);
+
+ /* pkg1 does not directly depend on pkg2, but if this is an upgrade
+ * operation there may be an indirect dependency through an installed
+ * dependency not part of the current transaction */
+ for(i = alpm_pkg_get_depends(pkg1); i; i = i->next) {
+ alpm_depend_t *dep = i->data;
+ alpm_pkg_t *lpkg = find_dep_satisfier(pkgs, dep);
+
+ if(!lpkg) {
+ continue;
+ } else if(alpm_list_find(targets, lpkg, _alpm_pkg_cmp)) {
+ /* lpkg's upgrade is part of the transaction, any dependency will be
+ * detected separately as pkg1 -> lpkg and lpkg -> pkg2 */
+ continue;
+ } else if(alpm_list_find(*ignore, lpkg, _alpm_pkg_cmp)) {
+ /* we've already checked lpkg, move on */
+ continue;
+ } else if(_alpm_pkg_in_dep_tree(lpkg, pkg2, targets, ignore)) {
+ /* we have an indirect dependency: pkg1 -> lpkg -> ... -> pkg2 */
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+/** Check if pkg2 is anywhere in pkg1's dependency tree.
+ * Wrapper for _alpm_pkg_in_dep_tree to handle creating and destroying state.
+ * @param pkg1
+ * @param pkg2
+ * @param targets if a package in this list is an intermediate dependency
+ * between pkg1 and pkg2, the pkg1 -> pkg2 dependency will not be
+ * reported
+ * @return 1 if pkg2 is found in pkg1's dependency tree
+ */
+static int _alpm_dep_edge(alpm_pkg_t *pkg1, alpm_pkg_t *pkg2,
+ alpm_list_t *targets)
+{
+ alpm_list_t *ignore = NULL;
+ int ret = _alpm_pkg_in_dep_tree(pkg1, pkg2, targets, &ignore);
+ alpm_list_free(ignore);
+ return ret;
+}
+
/* Convert a list of alpm_pkg_t * to a graph structure,
* with a edge for each dependency.
* Returns a list of vertices (one vertex = one package)
for(j = vertices; j; j = j->next) {
alpm_graph_t *vertex_j = j->data;
alpm_pkg_t *p_j = vertex_j->data;
- if(_alpm_dep_edge(p_i, p_j)) {
+ if(_alpm_dep_edge(p_i, p_j, targets)) {
vertex_i->children =
alpm_list_add(vertex_i->children, vertex_j);
}
else if(nextchild->state == -1) {
alpm_pkg_t *vertexpkg = vertex->data;
alpm_pkg_t *childpkg = nextchild->data;
- const char *message;
_alpm_log(handle, ALPM_LOG_WARNING, _("dependency cycle detected:\n"));
if(reverse) {
- message =_("%s will be removed after its %s dependency\n");
+ _alpm_log(handle, ALPM_LOG_WARNING,
+ _("%s will be removed after its %s dependency\n"),
+ vertexpkg->name, childpkg->name);
} else {
- message =_("%s will be installed before its %s dependency\n");
+ _alpm_log(handle, ALPM_LOG_WARNING,
+ _("%s will be installed before its %s dependency\n"),
+ vertexpkg->name, childpkg->name);
}
- _alpm_log(handle, ALPM_LOG_WARNING, message, vertexpkg->name, childpkg->name);
}
}
if(!found) {
static int no_dep_version(alpm_handle_t *handle)
{
- int flags = alpm_trans_get_flags(handle);
- return flags != -1 && (flags & ALPM_TRANS_FLAG_NODEPVERSION);
+ if(!handle->trans) {
+ return 0;
+ }
+ return (handle->trans->flags & ALPM_TRANS_FLAG_NODEPVERSION);
}
static alpm_depend_t *filtered_depend(alpm_depend_t *dep, int nodepversion)
}
}
-static alpm_pkg_t *find_dep_satisfier(alpm_list_t *pkgs, alpm_depend_t *dep)
-{
- alpm_list_t *i;
-
- for(i = pkgs; i; i = i->next) {
- alpm_pkg_t *pkg = i->data;
- if(_alpm_depcmp(pkg, dep)) {
- return pkg;
- }
- }
- return NULL;
-}
-
/** Find a package satisfying a specified dependency.
* The dependency can include versions with depmod operators.
* @param pkgs an alpm_list_t* of alpm_pkg_t where the satisfier will be searched
* @return an alpm_list_t* of alpm_depmissing_t pointers.
*/
alpm_list_t SYMEXPORT *alpm_checkdeps(alpm_handle_t *handle,
- alpm_list_t *pkglist, alpm_list_t *remove, alpm_list_t *upgrade,
+ alpm_list_t *pkglist, alpm_list_t *rem, alpm_list_t *upgrade,
int reversedeps)
{
alpm_list_t *i, *j;
for(i = pkglist; i; i = i->next) {
alpm_pkg_t *pkg = i->data;
- if(_alpm_pkg_find(remove, pkg->name) || _alpm_pkg_find(upgrade, pkg->name)) {
+ if(alpm_pkg_find(rem, pkg->name) || alpm_pkg_find(upgrade, pkg->name)) {
modified = alpm_list_add(modified, pkg);
} else {
dblist = alpm_list_add(dblist, pkg);
/* any version will satisfy the requirement */
satisfy = (provision->name_hash == dep->name_hash
&& strcmp(provision->name, dep->name) == 0);
- } else if (provision->mod == ALPM_DEP_MOD_EQ) {
+ } else if(provision->mod == ALPM_DEP_MOD_EQ) {
/* provision specifies a version, so try it out */
satisfy = (provision->name_hash == dep->name_hash
&& strcmp(provision->name, dep->name) == 0
alpm_depend_t *_alpm_splitdep(const char *depstring)
{
alpm_depend_t *depend;
- const char *ptr, *version;
+ const char *ptr, *version, *desc;
size_t deplen;
if(depstring == NULL) {
}
MALLOC(depend, sizeof(alpm_depend_t), return NULL);
- deplen = strlen(depstring);
+
+ /* Note the extra space in ": " to avoid matching the epoch */
+ if((desc = strstr(depstring, ": ")) != NULL) {
+ STRDUP(depend->desc, desc + 2, return NULL);
+ deplen = desc - depstring;
+ } else {
+ /* no description- point desc at NULL at end of string for later use */
+ depend->desc = NULL;
+ deplen = strlen(depstring);
+ desc = depstring + deplen;
+ }
/* 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. */
depend->mod = ALPM_DEP_MOD_EQ;
version = ptr + 1;
} else {
- /* no version specified, leave ptr NULL and set version to NULL */
+ /* no version specified, set ptr to end of string and version to NULL */
+ ptr = depstring + deplen;
depend->mod = ALPM_DEP_MOD_ANY;
depend->version = NULL;
version = NULL;
}
/* copy the right parts to the right places */
- if(ptr) {
- STRNDUP(depend->name, depstring, ptr - depstring, return NULL);
- } else {
- STRDUP(depend->name, depstring, return NULL);
- }
+ STRNDUP(depend->name, depstring, ptr - depstring, return NULL);
depend->name_hash = _alpm_hash_sdbm(depend->name);
if(version) {
- STRDUP(depend->version, version, return NULL);
+ STRNDUP(depend->version, version, desc - version, return NULL);
}
return depend;
CALLOC(newdep, 1, sizeof(alpm_depend_t), return NULL);
STRDUP(newdep->name, dep->name, return NULL);
- newdep->name_hash = dep->name_hash;
STRDUP(newdep->version, dep->version, return NULL);
+ STRDUP(newdep->desc, dep->desc, return NULL);
+ newdep->name_hash = dep->name_hash;
newdep->mod = dep->mod;
return newdep;
/* 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
+ * target list, or if the package was explicitly installed and
* include_explicit == 0 */
static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg,
alpm_list_t *targets, int include_explicit)
{
alpm_list_t *i;
- if(_alpm_pkg_find(targets, pkg->name)) {
+ if(alpm_pkg_find(targets, pkg->name)) {
return 0;
}
/* see if other packages need it */
for(i = _alpm_db_get_pkgcache(db); i; i = i->next) {
alpm_pkg_t *lpkg = i->data;
- if(_alpm_dep_edge(lpkg, pkg) && !_alpm_pkg_find(targets, lpkg->name)) {
+ if(_alpm_pkg_depends_on(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) {
return 0;
}
}
alpm_pkg_t *pkg = i->data;
for(j = _alpm_db_get_pkgcache(db); j; j = j->next) {
alpm_pkg_t *deppkg = j->data;
- if(_alpm_dep_edge(pkg, deppkg)
+ if(_alpm_pkg_depends_on(pkg, deppkg)
&& can_remove_package(db, deppkg, targs, include_explicit)) {
alpm_pkg_t *copy;
_alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n",
/* 1. literals */
for(i = dbs; i; i = i->next) {
- alpm_pkg_t *pkg = _alpm_db_get_pkgfromcache(i->data, dep->name);
+ alpm_pkg_t *pkg;
+ alpm_db_t *db = i->data;
+
+ if(!(db->usage & (ALPM_DB_USAGE_INSTALL|ALPM_DB_USAGE_UPGRADE))) {
+ continue;
+ }
+
+ pkg = _alpm_db_get_pkgfromcache(db, dep->name);
if(pkg && _alpm_depcmp_literal(pkg, dep)
- && !_alpm_pkg_find(excluding, pkg->name)) {
+ && !alpm_pkg_find(excluding, pkg->name)) {
if(_alpm_pkg_should_ignore(handle, pkg)) {
int install = 0;
if(prompt) {
}
/* 2. satisfiers (skip literals here) */
for(i = dbs; i; i = i->next) {
- for(j = _alpm_db_get_pkgcache(i->data); j; j = j->next) {
+ alpm_db_t *db = i->data;
+ if(!(db->usage & (ALPM_DB_USAGE_INSTALL|ALPM_DB_USAGE_UPGRADE))) {
+ continue;
+ }
+ for(j = _alpm_db_get_pkgcache(db); j; j = j->next) {
alpm_pkg_t *pkg = j->data;
/* with hash != hash, we can even skip the strcmp() as we know they can't
* possibly be the same string */
if(pkg->name_hash != dep->name_hash && _alpm_depcmp(pkg, dep)
- && !_alpm_pkg_find(excluding, pkg->name)) {
+ && !alpm_pkg_find(excluding, pkg->name)) {
if(_alpm_pkg_should_ignore(handle, pkg)) {
int install = 0;
if(prompt) {
count = alpm_list_count(providers);
if(count >= 1) {
/* default to first provider if there is no QUESTION callback */
- int index = 0;
+ int idx = 0;
if(count > 1) {
/* if there is more than one provider, we ask the user */
QUESTION(handle, ALPM_QUESTION_SELECT_PROVIDER,
- providers, dep, NULL, &index);
+ providers, dep, NULL, &idx);
}
- if(index >= 0 && index < count) {
- alpm_list_t *nth = alpm_list_nth(providers, index);
+ if(idx >= 0 && idx < count) {
+ alpm_list_t *nth = alpm_list_nth(providers, idx);
alpm_pkg_t *pkg = nth->data;
alpm_list_free(providers);
return pkg;
*/
int _alpm_resolvedeps(alpm_handle_t *handle, alpm_list_t *localpkgs,
alpm_pkg_t *pkg, alpm_list_t *preferred, alpm_list_t **packages,
- alpm_list_t *remove, alpm_list_t **data)
+ alpm_list_t *rem, alpm_list_t **data)
{
int ret = 0;
- alpm_list_t *i, *j;
+ alpm_list_t *j;
alpm_list_t *targ;
alpm_list_t *deps = NULL;
alpm_list_t *packages_copy;
- if(_alpm_pkg_find(*packages, pkg->name) != NULL) {
+ if(alpm_pkg_find(*packages, pkg->name) != NULL) {
return 0;
}
- if(handle->trans->flags & ALPM_TRANS_FLAG_RECURSE) {
- /* removing local packages from the equation causes the entire dep chain to
- * get pulled for each target- e.g., pactree -u output */
- localpkgs = NULL;
- }
-
/* Create a copy of the packages list, so that it can be restored
on error */
packages_copy = alpm_list_copy(*packages);
*packages = alpm_list_add(*packages, pkg);
_alpm_log(handle, ALPM_LOG_DEBUG, "started resolving dependencies\n");
- for(i = alpm_list_last(*packages); i; i = i->next) {
- alpm_pkg_t *tpkg = i->data;
- targ = alpm_list_add(NULL, tpkg);
- deps = alpm_checkdeps(handle, localpkgs, remove, targ, 0);
- alpm_list_free(targ);
-
- for(j = deps; j; j = j->next) {
- alpm_depmissing_t *miss = j->data;
- alpm_depend_t *missdep = miss->depend;
- /* check if one of the packages in the [*packages] list already satisfies
- * this dependency */
- if(find_dep_satisfier(*packages, missdep)) {
- _alpm_depmiss_free(miss);
- continue;
- }
- /* check if one of the packages in the [preferred] list already satisfies
- * this dependency */
- alpm_pkg_t *spkg = find_dep_satisfier(preferred, missdep);
- if(!spkg) {
- /* find a satisfier package in the given repositories */
- spkg = resolvedep(handle, missdep, handle->dbs_sync, *packages, 0);
- }
- if(!spkg) {
- handle->pm_errno = ALPM_ERR_UNSATISFIED_DEPS;
- char *missdepstring = alpm_dep_compute_string(missdep);
- _alpm_log(handle, ALPM_LOG_WARNING,
- _("cannot resolve \"%s\", a dependency of \"%s\"\n"),
- missdepstring, tpkg->name);
- free(missdepstring);
- if(data) {
- *data = alpm_list_add(*data, miss);
- }
- ret = -1;
- } else {
- _alpm_log(handle, ALPM_LOG_DEBUG,
- "pulling dependency %s (needed by %s)\n",
- spkg->name, tpkg->name);
- *packages = alpm_list_add(*packages, spkg);
- _alpm_depmiss_free(miss);
- }
+ targ = alpm_list_add(NULL, pkg);
+ deps = alpm_checkdeps(handle, localpkgs, rem, targ, 0);
+ alpm_list_free(targ);
+ targ = NULL;
+
+ for(j = deps; j; j = j->next) {
+ alpm_depmissing_t *miss = j->data;
+ alpm_depend_t *missdep = miss->depend;
+ /* check if one of the packages in the [*packages] list already satisfies
+ * this dependency */
+ if(find_dep_satisfier(*packages, missdep)) {
+ _alpm_depmiss_free(miss);
+ continue;
+ }
+ /* check if one of the packages in the [preferred] list already satisfies
+ * this dependency */
+ alpm_pkg_t *spkg = find_dep_satisfier(preferred, missdep);
+ if(!spkg) {
+ /* find a satisfier package in the given repositories */
+ spkg = resolvedep(handle, missdep, handle->dbs_sync, *packages, 0);
}
- alpm_list_free(deps);
- }
-
- if(handle->trans->flags & ALPM_TRANS_FLAG_NEEDED) {
- /* remove any deps that were pulled that match installed version */
- /* odd loop syntax so we can modify the list as we iterate */
- i = *packages;
- while(i) {
- alpm_pkg_t *tpkg = i->data;
- alpm_pkg_t *local = _alpm_db_get_pkgfromcache(
- handle->db_local, tpkg->name);
- if(local && _alpm_pkg_compare_versions(tpkg, local) == 0) {
- /* with the NEEDED flag, packages up to date are not reinstalled */
- _alpm_log(handle, ALPM_LOG_DEBUG,
- "not adding dep %s-%s as it is not needed, same version\n",
- local->name, local->version);
- j = i;
- i = i->next;
- *packages = alpm_list_remove_item(*packages, j);
- free(j);
- } else {
- i = i->next;
+ if(spkg && _alpm_resolvedeps(handle, localpkgs, spkg, preferred, packages, rem, data) == 0) {
+ _alpm_log(handle, ALPM_LOG_DEBUG,
+ "pulling dependency %s (needed by %s)\n",
+ spkg->name, pkg->name);
+ _alpm_depmiss_free(miss);
+ } else if(resolvedep(handle, missdep, (targ = alpm_list_add(NULL, handle->db_local)), rem, 0)) {
+ _alpm_depmiss_free(miss);
+ } else {
+ handle->pm_errno = ALPM_ERR_UNSATISFIED_DEPS;
+ char *missdepstring = alpm_dep_compute_string(missdep);
+ _alpm_log(handle, ALPM_LOG_WARNING,
+ _("cannot resolve \"%s\", a dependency of \"%s\"\n"),
+ missdepstring, pkg->name);
+ free(missdepstring);
+ if(data) {
+ *data = alpm_list_add(*data, miss);
}
+ ret = -1;
}
}
+ alpm_list_free(targ);
+ alpm_list_free(deps);
if(ret != 0) {
alpm_list_free(*packages);
*/
char SYMEXPORT *alpm_dep_compute_string(const alpm_depend_t *dep)
{
- const char *name, *opr, *ver;
+ const char *name, *opr, *ver, *desc_delim, *desc;
char *str;
size_t len;
ver = "";
}
+ if(dep->desc) {
+ desc_delim = ": ";
+ desc = dep->desc;
+ } else {
+ desc_delim = "";
+ desc = "";
+ }
+
/* we can always compute len and print the string like this because opr
* and ver will be empty when ALPM_DEP_MOD_ANY is the depend type. the
* reassignments above also ensure we do not do a strlen(NULL). */
- len = strlen(name) + strlen(opr) + strlen(ver) + 1;
+ len = strlen(name) + strlen(opr) + strlen(ver)
+ + strlen(desc_delim) + strlen(desc) + 1;
MALLOC(str, len, return NULL);
- snprintf(str, len, "%s%s%s", name, opr, ver);
+ snprintf(str, len, "%s%s%s%s%s", name, opr, ver, desc_delim, desc);
return str;
}