Hi! My patch won't fix the problem, just cuts off a needless part from the source (because depcmp takes care of provides too). This bug is similar to the previous one. But I think this is a serious one, because this occurs in case of -Su too (as bug I.), so can be very common (whenever depends changed in sync repo). ----upgrade060.py---- self.description = "Try to upgrade 2 packages which would break deps" lp1 = pmpkg("pkg1") lp1.depends = ["pkg2=1.0-1"] self.addpkg2db("local", lp1) lp2 = pmpkg("pkg2", "1.0-1") lp2.requiredby = [ "pkg1" ] self.addpkg2db("local", lp2) p1 = pmpkg("pkg1", "1.0-2") p1.depends = ["pkg2=1.0-1"] self.addpkg(p1) p2 = pmpkg("pkg2", "1.0-2") self.addpkg(p2) self.args = "-U %s" % " ".join([p.filename() for p in p1, p2]) self.addrule("PACMAN_RETCODE=1") self.addrule("PKG_VERSION=pkg1|1.0-1") self.addrule("PKG_VERSION=pkg2|1.0-1") ------------------- You find the problem here around lines 323, we don't ensure that we won't overwrite the local "satisfyer" package with a "non-satisfyer" one. This could be fixed similarly to my previous patch, but imho that would be too slow. An idea: we should temporarily attach to the old packages in the pkgcache a "pointer" which points to the "new" target (we found all old packages earlier); and this could be deleted at the end of transaction (anyway, if the transaction is successful, we always must modify that entries). The implementation is waiting for you ;-) -----patch---------- diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c --- pacman-lib/lib/libalpm/deps.c 2007-03-19 05:23:45.000000000 +0100 +++ pacman-lib.new/lib/libalpm/deps.c 2007-04-21 16:42:29.000000000 +0200 @@ -319,36 +320,12 @@ } found = 0; - /* check database for literal packages */ + /* check database for satisfying packages */ for(k = _alpm_db_get_pkgcache(db); k && !found; k = k->next) { pmpkg_t *p = (pmpkg_t *)k->data; found = alpm_depcmp(p, depend); } - /* check database for provides matches */ - if(!found) { - alpm_list_t *m; - for(m = _alpm_db_whatprovides(db, depend->name); m && !found; m = m->next) { - /* look for a match that isn't one of the packages we're trying - * to install. this way, if we match against a to-be-installed - * package, we'll defer to the NEW one, not the one already - * installed. */ - pmpkg_t *p = m->data; - alpm_list_t *n; - int skip = 0; - for(n = packages; n && !skip; n = n->next) { - pmpkg_t *ptp = n->data; - if(strcmp(alpm_pkg_get_name(ptp), alpm_pkg_get_name(p)) == 0) { - skip = 1; - } - } - if(skip) { - continue; - } - found = alpm_depcmp(p, depend); - } - FREELISTPTR(k); - } /* check other targets */ for(k = packages; k && !found; k = k->next) { pmpkg_t *p = k->data; -------------------- Bye, ngaba

Oh, this is much more plausible ;-): -------- diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c --- pacman-lib/lib/libalpm/deps.c 2007-03-19 05:23:45.000000000 +0100 +++ pacman-lib.new/lib/libalpm/deps.c 2007-04-21 20:02:07.000000000 +0200 @@ -271,12 +271,8 @@ for(l = _alpm_db_get_pkgcache(db); l; l = l->next) { pmpkg_t *pkg = l->data; - if(strcmp(alpm_pkg_get_name(pkg), alpm_pkg_get_name(oldpkg)) == 0) { - /* well, we know this one succeeds, but we're removing it... skip it */ - continue; - } - - if(alpm_depcmp(pkg, depend)) { + if(alpm_depcmp(pkg, depend) && !_alpm_pkg_find(alpm_pkg_get_name(pkg), packages)) { + /* we ignore packages that will be updated because we know that updated ones don't satisfy depend.*/ _alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' satisfied by installed package '%s'"), depend->name, alpm_pkg_get_name(pkg)); satisfied = 1; --------------------- Enjoy, ngaba

Hi! I implemented a standard topological sort algorithm. I'm not satisfied yet, because I must compute the edges in O(n^2) time (checkdeps also does this (and more), so its result should be used somehow). If my algorithm is OK, then extra contains a dep circle ;-) This is not radically faster anyway, but at least (hopefully) produces good result. Here is the patch: ------------------- diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c --- pacman-lib/lib/libalpm/deps.c 2007-04-22 14:54:33.000000000 +0200 +++ pacman-lib.new/lib/libalpm/deps.c 2007-04-22 18:34:36.000000000 +0200 @@ -30,7 +30,6 @@ #include #endif #include -#include /* libalpm */ #include "deps.h" @@ -47,6 +46,38 @@ extern pmhandle_t *handle; +pmgraph_t *_alpm_graph_new(void) +{ + pmgraph_t *graph = NULL; + + graph = (pmgraph_t *)malloc(sizeof(pmgraph_t)); + if(graph) { + graph->state = 0; + graph->data = NULL; + graph->father = NULL; + graph->sons = NULL; + graph->sonptr = NULL; + } + return(graph); +} + +void _alpm_graph_free(pmgraph_t *graph) +{ + FREELISTPTR(graph->sons); + free(graph); +} + +pmgraph_t *_alpm_graph_finduntouched(alpm_list_t *vertices) +{ + alpm_list_t *i; + pmgraph_t *found = NULL; + for (i = vertices; i && !found; i = i->next) { + pmgraph_t *vertex = i->data; + if (vertex->state == 0) found = vertex; + } + return(found); +} + pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type, pmdepmod_t depmod, const char *depname, const char *depversion) @@ -109,11 +140,9 @@ alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode) { alpm_list_t *newtargs = NULL; - alpm_list_t *i, *j, *k, *l; - int change = 1; - int numscans = 0; - int numtargs = 0; - int maxscans; + alpm_list_t *i, *j, *k; + alpm_list_t *vertices = NULL; + pmgraph_t *vertex; ALPM_LOG_FUNC; @@ -121,65 +150,64 @@ return(NULL); } - for(i = targets; i; i = i->next) { - newtargs = alpm_list_add(newtargs, i->data); - numtargs++; - } - - maxscans = (int)sqrt(numtargs); - _alpm_log(PM_LOG_DEBUG, _("started sorting dependencies")); - while(change) { - alpm_list_t *tmptargs = NULL; - change = 0; - if(numscans > maxscans) { - _alpm_log(PM_LOG_DEBUG, _("possible dependency cycle detected")); - continue; - } - numscans++; - /* run thru targets, moving up packages as necessary */ - for(i = newtargs; i; i = i->next) { - pmpkg_t *p = i->data; - _alpm_log(PM_LOG_DEBUG, " sorting %s", alpm_pkg_get_name(p)); - for(j = alpm_pkg_get_depends(p); j; j = j->next) { - pmdepend_t *depend = alpm_splitdep(j->data); - pmpkg_t *q = NULL; - if(depend == NULL) { - continue; - } - /* look for depend->name -- if it's farther down in the list, then - * move it up above p - */ - for(k = i->next; k; k = k->next) { - q = k->data; - const char *qname = alpm_pkg_get_name(q); - if(!strcmp(depend->name, qname)) { - if(!_alpm_pkg_find(qname, tmptargs)) { - change = 1; - tmptargs = alpm_list_add(tmptargs, q); - } - break; - } - for(l = alpm_pkg_get_provides(q); l; l = l->next) { - const char *provname = l->data; - if(!strcmp(depend->name, provname)) { - if(!_alpm_pkg_find(provname, tmptargs)) { - change = 1; - tmptargs = alpm_list_add(tmptargs, q); - } - break; - } - } - } + + /* We create the vertices */ + for(i = targets; i; i = i->next) { + pmgraph_t *vertex = _alpm_graph_new(); + vertex->data = (void *)i->data; + vertices = alpm_list_add(vertices, vertex); + } + + /* We compute the edges */ + for(i = vertices; i; i = i->next) { + pmgraph_t *vertex_i = i->data; + pmpkg_t *p_i = vertex_i->data; + //TODO: this should be somehow combined with _alpm_checkdeps + for(j = vertices; j; j = j->next) { + pmgraph_t *vertex_j = j->data; + pmpkg_t *p_j = vertex_j->data; + int son=0; + for(k = alpm_pkg_get_depends(p_i); k && !son; k = k->next) { + pmdepend_t *depend = alpm_splitdep(k->data); + son = alpm_depcmp(p_j, depend); free(depend); } - if(!_alpm_pkg_find(alpm_pkg_get_name(p), tmptargs)) { - tmptargs = alpm_list_add(tmptargs, p); + if(son) vertex_i->sons=alpm_list_add(vertex_i->sons, vertex_j); + } + vertex_i->sonptr=vertex_i->sons; + } + + vertex = vertices->data; + while(vertex) { + vertex->state = -1; // we touched this vertex + int found = 0; + while(vertex->sonptr && !found) { + pmgraph_t *nextson = (vertex->sonptr)->data; + vertex->sonptr = (vertex->sonptr)->next; + if (nextson->state == 0) { + found = 1; + nextson->father = vertex; + vertex = nextson; } + else if(nextson->state == -1) { + _alpm_log(PM_LOG_WARNING, _("dependency cycle detected\n")); + /* We add remaining targets */ + for(i = targets; i; i = i->next) + if(!_alpm_pkg_find(alpm_pkg_get_name(i->data), newtargs)) + newtargs = alpm_list_add(newtargs, i->data); + goto cleanup; + } + } + if(!found) { + newtargs = alpm_list_add(newtargs, vertex->data); + vertex->state = 1; //we leave this vertex + vertex = vertex->father; + if(!vertex) vertex=_alpm_graph_finduntouched(vertices); } - FREELISTPTR(newtargs); - newtargs = tmptargs; } +cleanup: + _alpm_log(PM_LOG_DEBUG, _("sorting dependencies finished")); if(mode == PM_TRANS_TYPE_REMOVE) { @@ -190,6 +218,8 @@ newtargs = tmptargs; } + _FREELIST(vertices, _alpm_graph_free); + return(newtargs); } @@ -234,12 +264,12 @@ for(j = alpm_pkg_get_requiredby(oldpkg); j; j = j->next) { pmpkg_t *p; found = 0; - if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) { - /* hmmm... package isn't installed.. */ + if(_alpm_pkg_find(j->data, packages)) { + /* this package also in the upgrade list, so don't worry about it */ continue; } - if(_alpm_pkg_find(alpm_pkg_get_name(p), packages)) { - /* this package also in the upgrade list, so don't worry about it */ + if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) { + /* hmmm... package isn't installed.. */ continue; } for(k = alpm_pkg_get_depends(p); k; k = k->next) { @@ -271,12 +301,8 @@ for(l = _alpm_db_get_pkgcache(db); l; l = l->next) { pmpkg_t *pkg = l->data; - if(strcmp(alpm_pkg_get_name(pkg), alpm_pkg_get_name(oldpkg)) == 0) { - /* well, we know this one succeeds, but we're removing it... skip it */ - continue; - } - - if(alpm_depcmp(pkg, depend)) { + if(alpm_depcmp(pkg, depend) && !_alpm_pkg_find(alpm_pkg_get_name(pkg), packages)) { + /* we ignore packages that will be updated because we know that updated ones don't satisfy depend.*/ _alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' satisfied by installed package '%s'"), depend->name, alpm_pkg_get_name(pkg)); satisfied = 1; @@ -319,36 +345,12 @@ } found = 0; - /* check database for literal packages */ + /* check database for satisfying packages */ for(k = _alpm_db_get_pkgcache(db); k && !found; k = k->next) { pmpkg_t *p = (pmpkg_t *)k->data; found = alpm_depcmp(p, depend); } - /* check database for provides matches */ - if(!found) { - alpm_list_t *m; - for(m = _alpm_db_whatprovides(db, depend->name); m && !found; m = m->next) { - /* look for a match that isn't one of the packages we're trying - * to install. this way, if we match against a to-be-installed - * package, we'll defer to the NEW one, not the one already - * installed. */ - pmpkg_t *p = m->data; - alpm_list_t *n; - int skip = 0; - for(n = packages; n && !skip; n = n->next) { - pmpkg_t *ptp = n->data; - if(strcmp(alpm_pkg_get_name(ptp), alpm_pkg_get_name(p)) == 0) { - skip = 1; - } - } - if(skip) { - continue; - } - found = alpm_depcmp(p, depend); - } - FREELISTPTR(k); - } /* check other targets */ for(k = packages; k && !found; k = k->next) { pmpkg_t *p = k->data; @@ -370,52 +372,55 @@ } } } else if(op == PM_TRANS_TYPE_REMOVE) { - /* check requiredby fields */ for(i = packages; i; i = i->next) { - pmpkg_t *tp = i->data; - if(tp == NULL) { + pmpkg_t *rempkg = i->data; + + if(rempkg == NULL) { + _alpm_log(PM_LOG_DEBUG, _("null package found in package list")); continue; } - found=0; - for(j = alpm_pkg_get_requiredby(tp); j; j = j->next) { - /* Search for 'reqname' in packages for removal */ - char *reqname = j->data; - alpm_list_t *x = NULL; - for(x = packages; x; x = x->next) { - pmpkg_t *xp = x->data; - if(strcmp(reqname, alpm_pkg_get_name(xp)) == 0) { - found = 1; - break; - } + for(j = alpm_pkg_get_requiredby(rempkg); j; j = j->next) { + pmpkg_t *p; + found = 0; + if(_alpm_pkg_find(j->data, packages)) { + /* this package also in the remove list, so don't worry about it */ + continue; } - if(!found) { - /* check if a package in trans->packages provides this package */ - for(k = trans->packages; !found && k; k=k->next) { - pmpkg_t *spkg = NULL; - if(trans->type == PM_TRANS_TYPE_SYNC) { - pmsyncpkg_t *sync = k->data; - spkg = sync->pkg; - } else { - spkg = k->data; - } - if(spkg) { - if(alpm_list_find_str(alpm_pkg_get_provides(spkg), tp->name)) { - found = 1; + if((p = _alpm_db_get_pkgfromcache(db, j->data)) == NULL) { + /* hmmm... package isn't installed.. */ + continue; + } + for(k = alpm_pkg_get_depends(p); k; k = k->next) { + pmdepend_t *depend = alpm_splitdep(k->data); + if(depend == NULL) { + continue; + } + /* if rempkg satisfied this dep, we try to find an other satisfyer (which won't be removed)*/ + if(alpm_depcmp(rempkg, depend)) { + int satisfied = 0; + for(l = _alpm_db_get_pkgcache(db); l; l = l->next) { + pmpkg_t *pkg = l->data; + if(alpm_depcmp(pkg, depend) && !_alpm_pkg_find(alpm_pkg_get_name(pkg), packages)) { + _alpm_log(PM_LOG_DEBUG, _("checkdeps: dependency '%s' satisfied by installed package '%s'"), + depend->name, alpm_pkg_get_name(pkg)); + satisfied = 1; + break; } } - } - if(!found) { - _alpm_log(PM_LOG_DEBUG, _("checkdeps: found %s as required by %s"), - reqname, alpm_pkg_get_name(tp)); - miss = _alpm_depmiss_new(alpm_pkg_get_name(tp), PM_DEP_TYPE_DEPEND, - PM_DEP_MOD_ANY, j->data, NULL); - if(!_alpm_depmiss_isin(miss, baddeps)) { - baddeps = alpm_list_add(baddeps, miss); - } else { - FREE(miss); + if(!satisfied) { + _alpm_log(PM_LOG_DEBUG, _("checkdeps: found %s as required by %s"), + alpm_pkg_get_name(rempkg), alpm_pkg_get_name(p)); + miss = _alpm_depmiss_new(p->name, PM_DEP_TYPE_DEPEND, depend->mod, + depend->name, depend->version); + if(!_alpm_depmiss_isin(miss, baddeps)) { + baddeps = alpm_list_add(baddeps, miss); + } else { + FREE(miss); + } } } + free(depend); } } } diff -Naur pacman-lib/lib/libalpm/deps.h pacman-lib.new/lib/libalpm/deps.h --- pacman-lib/lib/libalpm/deps.h 2007-04-22 14:54:33.000000000 +0200 +++ pacman-lib.new/lib/libalpm/deps.h 2007-04-22 16:59:20.000000000 +0200 @@ -42,6 +42,19 @@ pmdepend_t depend; }; +/* Graphs */ +struct __pmgraph_t { + int state; //0: untouched, -1: entered, other: leaving time + void *data; + struct __pmgraph_t *father; //where did we come from? + alpm_list_t *sons; + alpm_list_t *sonptr; // points to a son in the sons list +}; + +pmgraph_t *_alpm_graph_new(void); +void _alpm_graph_free(pmgraph_t *graph); +pmgraph_t *_alpm_graph_finduntouched(alpm_list_t *vertices); + pmdepmissing_t *_alpm_depmiss_new(const char *target, pmdeptype_t type, pmdepmod_t depmod, const char *depname, const char *depversion); @@ -53,7 +66,6 @@ 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); - #endif /* _ALPM_DEPS_H */ /* vim: set ts=2 sw=2 noet: */ diff -Naur pacman-lib/lib/libalpm/Makefile.am pacman-lib.new/lib/libalpm/Makefile.am --- pacman-lib/lib/libalpm/Makefile.am 2007-04-22 14:54:33.000000000 +0200 +++ pacman-lib.new/lib/libalpm/Makefile.am 2007-04-22 18:06:04.000000000 +0200 @@ -39,7 +39,7 @@ versioncmp.h versioncmp.c libalpm_la_LDFLAGS = -no-undefined -version-info $(LIB_VERSION_INFO) -libalpm_la_LIBADD = -larchive -ldownload -lm +libalpm_la_LIBADD = -larchive -ldownload if HAS_DOXYGEN all: doxygen.in diff -Naur pacman-lib/src/pacman/Makefile.am pacman-lib.new/src/pacman/Makefile.am --- pacman-lib/src/pacman/Makefile.am 2007-04-22 14:54:33.000000000 +0200 +++ pacman-lib.new/src/pacman/Makefile.am 2007-04-22 18:11:40.000000000 +0200 @@ -28,7 +28,7 @@ util.h util.c pacman_LDADD = $(top_builddir)/lib/libalpm/.libs/libalpm.la \ - -ldownload + -ldownload -lm pacman_static_SOURCES = $(pacman_SOURCES) pacman_static_LDFLAGS = $(LDFLAGS) -all-static ----------------------- bye, ngaba