[pacman-dev] [patch] alpm_removedeps bug+fix && alpm_depcmp-discussion
ngaba at petra.hos.u-szeged.hu
ngaba at petra.hos.u-szeged.hu
Mon Jun 18 10:50:50 EDT 2007
Hi!
I attached the pactest file and my patch. I also made some
modifications in alpm_removedeps' args, because the old one was a bit
messy for me. And I think that my version is faster.
can_remove_package is a bit stupid (compared to alpm_checkdeps), but I
leave it untouched, because speed is more important here than
"perfection".
As you see, this patch contains my usual "for (pkg in pkgcache)
if(alpm_depcmp(pkg, depend))..." stuff. We should discuss something now:
This method has a drawback sometimes in speed:
This method implicitly reads the pkgcache with full pkginfo, because
alpm_depcmp needs provisions. If we've already done this (or we need to
do this later) or we must collect ALL dependency satisfier in pkgcache
this is not a problem. However, for example if we just want to know if
there is ANY package in pkgcache which satisfies a dependency
(something similar to can_remove_package without using requiredby
fields), then FIRST check for package names THEN for providers is
probably faster, if the pkgcache is loaded with pkgname-pkgver info
only: because we have great chance to find a satisfier pkgname-pkgver
pair and we can stop, we can answer the question without reading the
ugly PKGINFO files for providers.
Bye, ngaba
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
-------------- next part --------------
self.description = "-Rs test"
lp1 = pmpkg("pkg1")
lp1.depends = ["pkg2=1.1-1"]
self.addpkg2db("local", lp1)
lp2 = pmpkg("pkg2", "1.0-1")
lp2.reason = 1
self.addpkg2db("local", lp2)
self.args = "-Rs %s" % lp1.name
self.addrule("PACMAN_RETCODE=0")
self.addrule("!PKG_EXIST=pkg1")
self.addrule("PKG_EXIST=pkg2")
-------------- next part --------------
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index 66b2d77..22c7347 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -508,73 +513,54 @@ static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets)
return(1);
}
-/* return a new alpm_list_t target list containing all packages in the original
- * target list, as well as all their un-needed dependencies. By un-needed,
- * I mean dependencies that are *only* required for packages in the target
- * list, so they can be safely removed. This function is recursive.
+/* @param targs list contains topo sorted _removable_ packages
+ * @return: un-needed dependencies of targs added to targs (still topo sorted)
+ * By un-needed, I mean dependencies that are *only* required for packages in the target
+ * list, so they can be safely removed.
+ * assumptions: alpm_list_add adds new member to the end of the list, so we can reuse the list pointer
+ * localdb doesn't contain a dep cicle.
*/
-alpm_list_t *_alpm_removedeps(pmdb_t *db, alpm_list_t *targs)
+void _alpm_removedeps(pmdb_t *db, alpm_list_t *targs)
{
alpm_list_t *i, *j, *k;
- alpm_list_t *newtargs = targs;
ALPM_LOG_FUNC;
if(db == NULL) {
- return(newtargs);
+ return;
}
-
- for(i = targs; i; i = i->next) {
- pmpkg_t *pkg = i->data;
- for(j = alpm_pkg_get_depends(pkg); j; j = j->next) {
- pmdepend_t *depend = alpm_splitdep(j->data);
- pmpkg_t *deppkg;
- if(depend == NULL) {
- continue;
- }
-
- deppkg = _alpm_db_get_pkgfromcache(db, depend->name);
- if(deppkg == NULL) {
- /* package not found... look for a provision instead */
- alpm_list_t *provides = _alpm_db_whatprovides(db, depend->name);
- if(!provides) {
- /* Not found, that's fine, carry on */
- _alpm_log(PM_LOG_DEBUG, _("cannot find package \"%s\" or anything that provides it!"), depend->name);
+ int ready = 0;
+ while(!ready) {
+ ready = 1;
+ for(i = targs; i; i = i->next) {
+ pmpkg_t *pkg = i->data;
+ for(j = alpm_pkg_get_depends(pkg); j; j = j->next) {
+ pmdepend_t *depend = alpm_splitdep(j->data);
+ if(depend == NULL) {
continue;
}
- for(k = provides; k; k = k->next) {
- pmpkg_t *provpkg = k->data;
- if(can_remove_package(db, provpkg, newtargs)) {
- pmpkg_t *pkg = _alpm_pkg_dup(provpkg);
- _alpm_log(PM_LOG_DEBUG, _("adding '%s' to the targets"), alpm_pkg_get_name(pkg));
+ for(k = _alpm_db_get_pkgcache(db); k; k = k->next) {
+ pmpkg_t *deppkg = k->data;
+ if(alpm_depcmp(deppkg,depend) && can_remove_package(db, deppkg, targs)) {
+ _alpm_log(PM_LOG_DEBUG, _("adding '%s' to the targets"), alpm_pkg_get_name(deppkg));
/* add it to the target list */
- newtargs = alpm_list_add(newtargs, pkg);
- newtargs = _alpm_removedeps(db, newtargs);
+ targs = alpm_list_add(targs, _alpm_pkg_dup(deppkg));
+ ready = 0;
}
}
- alpm_list_free(provides);
- } else if(can_remove_package(db, deppkg, newtargs)) {
- pmpkg_t *pkg = _alpm_pkg_dup(deppkg);
-
- _alpm_log(PM_LOG_DEBUG, _("adding '%s' to the targets"), alpm_pkg_get_name(pkg));
-
- /* add it to the target list */
- newtargs = alpm_list_add(newtargs, pkg);
- newtargs = _alpm_removedeps(db, newtargs);
+ free(depend);
}
- free(depend);
}
}
-
- return(newtargs);
}
/* populates *list with packages that need to be installed to satisfy all
* dependencies (recursive) for syncpkg
*
* make sure *list and *trail are already initialized
+ * assumption: alpm_list_add adds new member to the end of the list, so we can reuse the list pointer
*/
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,
diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h
index 132f21f..3f5e87b 100644
--- a/lib/libalpm/deps.h
+++ b/lib/libalpm/deps.h
@@ -58,7 +58,7 @@ int _alpm_depmiss_isin(pmdepmissing_t *needle, alpm_list_t *haystack);
alpm_list_t *_alpm_sortbydeps(alpm_list_t *targets, pmtranstype_t mode);
alpm_list_t *_alpm_checkdeps(pmtrans_t *trans, pmdb_t *db, pmtranstype_t op,
alpm_list_t *packages);
-alpm_list_t *_alpm_removedeps(pmdb_t *db, alpm_list_t *targs);
+void _alpm_removedeps(pmdb_t *db, alpm_list_t *targs);
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);
diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c
index 920739a..35807e4 100644
--- a/lib/libalpm/remove.c
+++ b/lib/libalpm/remove.c
@@ -137,11 +137,6 @@ int _alpm_remove_prepare(pmtrans_t *trans, pmdb_t *db, alpm_list_t **data)
}
}
- if(trans->flags & PM_TRANS_FLAG_RECURSE) {
- _alpm_log(PM_LOG_DEBUG, _("finding removable dependencies"));
- trans->packages = _alpm_removedeps(db, trans->packages);
- }
-
/* re-order w.r.t. dependencies */
_alpm_log(PM_LOG_DEBUG, _("sorting by dependencies"));
lp = _alpm_sortbydeps(trans->packages, PM_TRANS_TYPE_REMOVE);
@@ -149,6 +144,11 @@ int _alpm_remove_prepare(pmtrans_t *trans, pmdb_t *db, alpm_list_t **data)
alpm_list_free(trans->packages);
trans->packages = lp;
+ if(trans->flags & PM_TRANS_FLAG_RECURSE) {
+ _alpm_log(PM_LOG_DEBUG, _("finding removable dependencies"));
+ _alpm_removedeps(db, trans->packages);
+ }
+
EVENT(trans, PM_TRANS_EVT_CHECKDEPS_DONE, NULL, NULL);
}
More information about the pacman-dev
mailing list