On Tue, Jul 10, 2007 at 08:56:05PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Hi!
I attached a cleanup patch for resolvedeps + a pathologic pactest file to demonstrate, that the old version was negligent. See my notes about alpm_depcmp's speed here: http://www.archlinux.org/pipermail/pacman-dev/2007-June/008539.html
here is a slightly reworked patch, with the 2 comments I made : - usage of **list instead of *list - keeps the old way of checking for actual package name first, and then only look for providers if needed.
From d64ba5a500474d02640d733aac4122303e886eb0 Mon Sep 17 00:00:00 2001 From: Nagy Gabor <ngaba@petra.hos.u-szeged.hu> Date: Fri, 13 Jul 2007 23:03:23 +0200 Subject: [PATCH] libalpm/deps.c : cleanup + little fix for resolvedeps.
The resolvedeps function was a bit negligent, as showed by the sync011 pactest. Reference : http://www.archlinux.org/pipermail/pacman-dev/2007-July/008782.html Signed-off-by: Chantry Xavier <shiningxc@gmail.com> --- lib/libalpm/deps.c | 106 +++++++++++++++++++-------------------------- lib/libalpm/deps.h | 3 +- lib/libalpm/sync.c | 7 +-- pactest/tests/sync011.py | 20 +++++++++ 4 files changed, 68 insertions(+), 68 deletions(-) create mode 100644 pactest/tests/sync011.py diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index a2d60dd..be5a2a9 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -614,19 +614,18 @@ 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 * - * make sure *list and *trail are already initialized + * 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 *trail, pmtrans_t *trans, - alpm_list_t **data) + alpm_list_t **list, pmtrans_t *trans, alpm_list_t **data) { - alpm_list_t *i, *j; + alpm_list_t *i, *j, *k; alpm_list_t *targ; alpm_list_t *deps = NULL; ALPM_LOG_FUNC; - if(local == NULL || dbs_sync == NULL || syncpkg == NULL) { + if(local == NULL || dbs_sync == NULL || syncpkg == NULL || list == NULL) { return(-1); } @@ -642,14 +641,15 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, for(i = deps; i; i = i->next) { int found = 0; pmdepmissing_t *miss = i->data; + pmdepend_t *missdep = &(miss->depend); pmpkg_t *sync = NULL; - /* check if one of the packages in *list already provides this dependency */ - for(j = list; j && !found; j = j->next) { + /* 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_list_find_str(alpm_pkg_get_provides(sp), miss->depend.name)) { - _alpm_log(PM_LOG_DEBUG, "%s provides dependency %s -- skipping", - alpm_pkg_get_name(sp), miss->depend.name); + if(alpm_depcmp(sp, missdep)) { + _alpm_log(PM_LOG_DEBUG, "%s satisfies dependency %s -- skipping", + alpm_pkg_get_name(sp), missdep->name); found = 1; } } @@ -659,26 +659,23 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, /* find the package in one of the repositories */ /* check literals */ - for(j = dbs_sync; !sync && j; j = j->next) { - sync = _alpm_db_get_pkgfromcache(j->data, miss->depend.name); + for(j = dbs_sync; j && !found; j = j->next) { + sync = _alpm_db_get_pkgfromcache(j->data, missdep->name); + found = alpm_depcmp(sync, missdep); } - /*TODO this autoresolves the first 'provides' package... we should fix this + /*TODO this autoresolves the first 'satisfier' package... we should fix this * somehow */ /* check provides */ - if(!sync) { - for(j = dbs_sync; !sync && j; j = j->next) { - alpm_list_t *provides; - provides = _alpm_db_whatprovides(j->data, miss->depend.name); - if(provides) { - sync = provides->data; - } - alpm_list_free(provides); + 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; + found = alpm_depcmp(sync, missdep); } } - if(!sync) { + if(!found) { _alpm_log(PM_LOG_ERROR, _("cannot resolve dependencies for \"%s\" (\"%s\" is not in the package set)"), - miss->target, miss->depend.name); + miss->target, missdep->name); if(data) { if((miss = malloc(sizeof(pmdepmissing_t))) == NULL) { _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepmissing_t)); @@ -692,49 +689,36 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, pm_errno = PM_ERR_UNSATISFIED_DEPS; goto error; } - if(_alpm_pkg_find(alpm_pkg_get_name(sync), list)) { - /* this dep is already in the target list */ - _alpm_log(PM_LOG_DEBUG, "dependency %s is already in the target list -- skipping", - alpm_pkg_get_name(sync)); - continue; + /* check pmo_ignorepkg and pmo_s_ignore to make sure we haven't pulled in + * something we're not supposed to. + */ + int usedep = 1; + if(alpm_list_find_str(handle->ignorepkg, alpm_pkg_get_name(sync))) { + pmpkg_t *dummypkg = _alpm_pkg_new(miss->target, NULL); + QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, dummypkg, sync, NULL, &usedep); + _alpm_pkg_free(dummypkg); } - - if(!_alpm_pkg_find(alpm_pkg_get_name(sync), trail)) { - /* check pmo_ignorepkg and pmo_s_ignore to make sure we haven't pulled in - * something we're not supposed to. - */ - int usedep = 1; - if(alpm_list_find_str(handle->ignorepkg, alpm_pkg_get_name(sync))) { - pmpkg_t *dummypkg = _alpm_pkg_new(miss->target, NULL); - QUESTION(trans, PM_TRANS_CONV_INSTALL_IGNOREPKG, dummypkg, sync, NULL, &usedep); - _alpm_pkg_free(dummypkg); + if(usedep) { + _alpm_log(PM_LOG_DEBUG, "pulling dependency %s (needed by %s)", + alpm_pkg_get_name(sync), alpm_pkg_get_name(syncpkg)); + *list = alpm_list_add(*list, sync); + if(_alpm_resolvedeps(local, dbs_sync, sync, list, trans, data)) { + goto error; } - if(usedep) { - trail = alpm_list_add(trail, sync); - if(_alpm_resolvedeps(local, dbs_sync, sync, list, trail, trans, data)) { + } else { + _alpm_log(PM_LOG_ERROR, _("cannot resolve dependencies for \"%s\""), miss->target); + if(data) { + if((miss = malloc(sizeof(pmdepmissing_t))) == NULL) { + _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepmissing_t)); + FREELIST(*data); + pm_errno = PM_ERR_MEMORY; goto error; } - _alpm_log(PM_LOG_DEBUG, "pulling dependency %s (needed by %s)", - alpm_pkg_get_name(sync), alpm_pkg_get_name(syncpkg)); - list = alpm_list_add(list, sync); - } else { - _alpm_log(PM_LOG_ERROR, _("cannot resolve dependencies for \"%s\""), miss->target); - if(data) { - if((miss = malloc(sizeof(pmdepmissing_t))) == NULL) { - _alpm_log(PM_LOG_ERROR, _("malloc failure: could not allocate %d bytes"), sizeof(pmdepmissing_t)); - FREELIST(*data); - pm_errno = PM_ERR_MEMORY; - goto error; - } - *miss = *(pmdepmissing_t *)i->data; - *data = alpm_list_add(*data, miss); - } - pm_errno = PM_ERR_UNSATISFIED_DEPS; - goto error; + *miss = *(pmdepmissing_t *)i->data; + *data = alpm_list_add(*data, miss); } - } else { - /* cycle detected -- skip it */ - _alpm_log(PM_LOG_DEBUG, "dependency cycle detected: %s", sync->name); + pm_errno = PM_ERR_UNSATISFIED_DEPS; + goto error; } } diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h index f11a19a..59b2630 100644 --- a/lib/libalpm/deps.h +++ b/lib/libalpm/deps.h @@ -60,8 +60,7 @@ alpm_list_t *_alpm_checkdeps(pmdb_t *db, pmtranstype_t op, alpm_list_t *packages); 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 *trail, pmtrans_t *trans, - alpm_list_t **data); + alpm_list_t **list, pmtrans_t *trans, alpm_list_t **data); #endif /* _ALPM_DEPS_H */ diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c index 9c3884f..2075984 100644 --- a/lib/libalpm/sync.c +++ b/lib/libalpm/sync.c @@ -380,7 +380,6 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync { alpm_list_t *deps = NULL; alpm_list_t *list = NULL; /* allow checkdeps usage with trans->packages */ - alpm_list_t *trail = NULL; /* breadcrumb list to avoid running in circles */ alpm_list_t *i, *j; int ret = 0; @@ -404,8 +403,8 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync _alpm_log(PM_LOG_DEBUG, "resolving target's dependencies"); 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, - trail, trans, data) == -1) { + if(_alpm_resolvedeps(db_local, dbs_sync, spkg, &list, + trans, data) == -1) { /* pm_errno is set by resolvedeps */ ret = -1; goto cleanup; @@ -474,7 +473,6 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync goto cleanup; } - alpm_list_free(trail); } /* We don't care about conflicts if we're just printing uris */ @@ -710,7 +708,6 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync cleanup: alpm_list_free(list); - alpm_list_free(trail); return(ret); } diff --git a/pactest/tests/sync011.py b/pactest/tests/sync011.py new file mode 100644 index 0000000..f5b1943 --- /dev/null +++ b/pactest/tests/sync011.py @@ -0,0 +1,20 @@ +self.description = "Install a package from a sync db with cascaded dependencies + provides" + +sp1 = pmpkg("dummy", "1.0-2") +sp1.depends = ["dep1", "dep2=1.0-2"] + +sp2 = pmpkg("dep1") +sp2.files = ["bin/dep1"] +sp2.provides = ["dep2"] + +sp3 = pmpkg("dep2", "1.0-2") + +for p in sp1, sp2, sp3: + self.addpkg2db("sync", p); + +self.args = "-S %s" % sp1.name + +self.addrule("PACMAN_RETCODE=0") +self.addrule("PKG_VERSION=dummy|1.0-2") +self.addrule("PKG_EXIST=dep1") +self.addrule("PKG_EXIST=dep2") -- 1.5.2.2