[pacman-dev] [patch] resolvedeps cleanup + pactest
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 This patch fails with sync022, but that pactest is broken IMHO. Bye, ngaba PS: the patch was created with diff -Naur, sry. ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On 7/10/07, ngaba@petra.hos.u-szeged.hu <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
This patch fails with sync022, but that pactest is broken IMHO.
Bye, ngaba
PS: the patch was created with diff -Naur, sry.
Any reason the patch seems to have double line spacing? By the way, creating a patch with GIT is pretty simple and formats it quite nicely without having to struggle with diff options. -Dan
Any reason the patch seems to have double line spacing?
By the way, creating a patch with GIT is pretty simple and formats it quite nicely without having to struggle with diff options. Sorry, I have no net at home, no git/any useable app here (this is a windows machine). Probably this stupid webmail client inserted extra lines, sorry, please delete them (I can compress them + resend, if needed)
Back to pacman: There is a problem with the old/new resolvedeps: this is not deterministic (multiple provision) and sometimes one choice is better than an other one: for example "choice A" induces a package conflict, and choice B would solve the problem and would install the required package (and its dependencies) but pacman is not clever enough to find "choice B"... Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Tue, Jul 10, 2007 at 08:56:05PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Hi!
This patch fails with sync022, but that pactest is broken IMHO.
I already mentioned this recently again : http://www.archlinux.org/pipermail/pacman-dev/2007-July/008761.html I guess this is more a feature request than a bug, the problem is you can have unresolvable conflicts. The idea was to use the "replaces" flag as a hint for resolving a conflict, so in the case of 2 conflicting packages, pacman would choose by default the one replacing the other. But the replaces flag currently has a total different meaning (it's only used in sysupgrade context, ie pacman -Su). Anyway, this is just the behavior an user expected, we can consider it as invalid, and remove that sync022 pactest, and maybe find another better way to solve this problem.
On Tue, Jul 10, 2007 at 09:15:12PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Any reason the patch seems to have double line spacing?
By the way, creating a patch with GIT is pretty simple and formats it quite nicely without having to struggle with diff options. Sorry, I have no net at home, no git/any useable app here (this is a windows machine). Probably this stupid webmail client inserted extra lines, sorry, please delete them (I can compress them + resend, if needed)
ah too bad, I find it pretty hard to read the patch with these extra new lines.
Back to pacman: There is a problem with the old/new resolvedeps: this is not deterministic (multiple provision) and sometimes one choice is better than an other one: for example "choice A" induces a package conflict, and choice B would solve the problem and would install the required package (and its dependencies) but pacman is not clever enough to find "choice B"... Bye, ngaba
I guess this is a reference to : 628 /*TODO this autoresolves the first 'provides' package... we should fix this 629 * somehow */ Looks like pacman could indeed be smarter in the case you describe :)
I guess this is a reference to : 628 /*TODO this autoresolves the first 'provides' package... we should fix this 629 * somehow */
Looks like pacman could indeed be smarter in the case you describe :)
Yes:-P But you should see, that this is not just a feature request, because there are some rare cases when one resolving leads to a conflict, while an other one doesn't; and pacman should do an "error-free" resolving (if it exists) in these cases. I hope, that it's clear now, what I wanted to say ;-) (Sorry for my bad English) Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Tue, Jul 10, 2007 at 03:03:23PM -0400, Dan McGee wrote:
Any reason the patch seems to have double line spacing?
Offtopic : Actually, I'm curious, what's the easiest way to fix this automatically ? (delete all odd number lines) Not sure which tool could be used for that, so I wrote 5 lines in C which does it, but I want to know the other ways :)
On Tue, Jul 10, 2007 at 10:56:09PM +0200, Xavier wrote:
On Tue, Jul 10, 2007 at 03:03:23PM -0400, Dan McGee wrote:
Any reason the patch seems to have double line spacing?
Offtopic : Actually, I'm curious, what's the easiest way to fix this automatically ? (delete all odd number lines) Not sure which tool could be used for that, so I wrote 5 lines in C which does it, but I want to know the other ways :)
Well, I kept googling a bit, and found the magical sed line : sed 'n;d' resolvedeps.diff sorry for the noise ;)
Well, I kept googling a bit, and found the magical sed line : sed 'n;d' resolvedeps.diff
Or an alternative method: tr -s '\n' :-P bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
Hm, that one seems to remove all blank lines, not exactly what we want ;) OK, you are right, but in a .diff file there is no empty line... ;) Bye
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Wed, Jul 11, 2007 at 09:25:58PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Hm, that one seems to remove all blank lines, not exactly what we want ;) OK, you are right, but in a .diff file there is no empty line... ;)
Your own patch has 11 empty lines. I removed a few of them to check, and it resulted in a malformed patch, eheh. Oh well, I shouldn't have asked this question, now I messed up your thread :d
Your own patch has 11 empty lines. I removed a few of them to check, and it resulted in a malformed patch, eheh. Oh well, I shouldn't have asked this question, now I messed up your thread :d Well, the .diff file has no empty line (it may contain at least one space), and the .py file contains 6 empty lines :-P
I try to save the thread now :-D: As you noticed, here we must assume again, that alpm_list_add adds entry to the end of the list. You suggested earlier (http://www.archlinux.org/pipermail/pacman-dev/2007-June/008543.html <- and then you can remove the ready variable from that patch), that we should use alpm_list_add_last or similar to be perfect. I like your idea, and an O(1) alpm_list_add_first also would be useful (I mentioned here: http://www.archlinux.org/pipermail/pacman-dev/2007-April/008202.html) Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Wed, Jul 11, 2007 at 09:55:01PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Your own patch has 11 empty lines. I removed a few of them to check, and it resulted in a malformed patch, eheh. Oh well, I shouldn't have asked this question, now I messed up your thread :d Well, the .diff file has no empty line (it may contain at least one space), and the .py file contains 6 empty lines :-P
I try to save the thread now :-D: As you noticed, here we must assume again, that alpm_list_add adds entry to the end of the list. You suggested earlier (http://www.archlinux.org/pipermail/pacman-dev/2007-June/008543.html <- and then you can remove the ready variable from that patch), that we should use alpm_list_add_last or similar to be perfect. I like your idea, and an O(1) alpm_list_add_first also would be useful (I mentioned here: http://www.archlinux.org/pipermail/pacman-dev/2007-April/008202.html)
I agree, I don't see why the current list implementation couldn't be improved a bit (without major changes everywhere around the code), even if the goal is to eventualy move to kernel list, which would probably require much larger change. The first discussion about this stuff I found is 4 months old already : http://www.archlinux.org/pipermail/pacman-dev/2007-March/007374.html But maybe that move to kernel list could be done quicker than I think, I actually don't really know.
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
I started looking at the current resolvedeps, and there was a part I didn't understand, it only looked at provides and not at the name of the package itself (there was the same mistake in other parts of the code), so I just used alpm_depcmp as you always recommend and that one line change fix your pactest :) diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 591e5a8..3137f8b 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -613,7 +613,7 @@ int _alpm_resolvedeps(pmdb_t *local, alpm_list_t *dbs_sync, pmpkg_t *syncpkg, /* check if one of the packages in *list already provides 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)) { + if(alpm_depcmp(sp, &miss->depend)) { _alpm_log(PM_LOG_DEBUG, "%s provides dependency %s -- skipping", alpm_pkg_get_name(sp), miss->depend.name); found = 1; Of course that change is already in your patch ;) The other changes look nice too at first sight, but I need to have a closer look at them, hopefully tomorrow.
On Tue, Jul 10, 2007 at 09:15:12PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Back to pacman: There is a problem with the old/new resolvedeps: this is not deterministic (multiple provision) and sometimes one choice is better than an other one: for example "choice A" induces a package conflict, and choice B would solve the problem and would install the required package (and its dependencies) but pacman is not clever enough to find "choice B"...
Hmm, the old way was already not good, but after your patch, it's worse imo, because we lose the simple hint of trying the actual package name first. I think that's what we want in most cases when we let pacman auto resolve the dependencies for us. One example : I install acidrip which depends on mplayer, I most likely want mplayer to be pulled, not mplayer-svn. If pacman has to make one blind choice, I think it should rather try the actual package first. But well, that's already what you wanted to do for speed concern : http://www.archlinux.org/pipermail/pacman-dev/2007-June/008539.html
On Wed, Jul 11, 2007 at 09:55:01PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
As you noticed, here we must assume again, that alpm_list_add adds entry to the end of the list.
I noticed you added that comment in the code, but I really don't understand why.. Either before or after your patch, I don't see why this assumption is needed. Or maybe it isn't needed for that resolvedeps function itself, but for the code which use the result of resolvedeps ?
I install acidrip which depends on mplayer, I most likely want mplayer to be pulled, not mplayer-svn. OK, I understand this, and you are right, but I think, there is no definition for package "priority", if you _define_ that provide is not as "strong" as the "canonical" package, I will follow that rule. (Anyway, I think only one mplayer version should be exist in repos)
Let me explain an other (theoretical) example: Suppose that there is two kernel package in the sync repos: "vanilla" and "beyond" (RIP). And there are module packages compiled for them, such as nvidia-vanilla and nvidia-beyond, both provides nvidia. User does "pacman -S nvidia-utils" (which depends on nvidia). User has the beyond kernel installed, but pacman decides that it will install nvidia-vanilla and thus the kernel vanilla... probably the user doesn't want this. We can minimize the number of installed dependencies in alpm_resolvedeps or minimize the needed disk space etc. etc. but that wouldn't worth our effort. A bit off, for package maintainers: Personally I like the way, that I described above, and sometimes this "binary gentooish" packaging way would be nice. I mean, sometimes there are some very interesting but mutual ./configure options; in these cases multiple binary packages can be very helpful (-alsa, -oss, -gtk1, -gtk2, ...) and user could choose. These packages can be "identical" through provide. Any idea for this? flags? (special) groups (beyond and vanilla in our example) which helps pacman in the decision? [pacman must choose from nvidia-vanilla and nvidia-beyond and if these packages "flagged" by the groups vanilla and beyond, pacman can do a "-Qg vanilla" and "-Qg beyond" and it will see, that the installed vanilla group is empty, so probably the user wants to install a beyond package] Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
I noticed you added that comment in the code, but I really don't understand why.. Either before or after your patch, I don't see why this assumption is needed. Or maybe it isn't needed for that resolvedeps function itself, but for the code which use the result of resolvedeps ?
Just to be quick: It can be seen from function definition: alpm_list_t *list is used instead of **list. Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Thu, Jul 12, 2007 at 08:57:08PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
I noticed you added that comment in the code, but I really don't understand why.. Either before or after your patch, I don't see why this assumption is needed. Or maybe it isn't needed for that resolvedeps function itself, but for the code which use the result of resolvedeps ?
Just to be quick: It can be seen from function definition: alpm_list_t *list is used instead of **list.
Hm I see, but isn't that weird ? Wouldn't it be better to use **list instead then ? Or having resolvedeps return this list ?
Wouldn't it be better to use **list instead then ? AFAIK, if we'd use **list, that assumption could be dropped. Bye, ngaba
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Thu, Jul 12, 2007 at 08:52:45PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
I install acidrip which depends on mplayer, I most likely want mplayer to be pulled, not mplayer-svn. OK, I understand this, and you are right, but I think, there is no definition for package "priority", if you _define_ that provide is not as "strong" as the "canonical" package, I will follow that rule. (Anyway, I think only one mplayer version should be exist in repos)
Well it's not obvious indeed, but I still think it's safer to keep it that way, at least for now.
Let me explain an other (theoretical) example: Suppose that there is two kernel package in the sync repos: "vanilla" and "beyond" (RIP). And there are module packages compiled for them, such as nvidia-vanilla and nvidia-beyond, both provides nvidia. User does "pacman -S nvidia-utils" (which depends on nvidia). User has the beyond kernel installed, but pacman decides that it will install nvidia-vanilla and thus the kernel vanilla... probably the user doesn't want this. We can minimize the number of installed dependencies in alpm_resolvedeps or minimize the needed disk space etc. etc. but that wouldn't worth our effort. A bit off, for package maintainers: Personally I like the way, that I described above, and sometimes this "binary gentooish" packaging way would be nice. I mean, sometimes there are some very interesting but mutual ./configure options; in these cases multiple binary packages can be very helpful (-alsa, -oss, -gtk1, -gtk2, ...) and user could choose. These packages can be "identical" through provide. Any idea for this? flags? (special) groups (beyond and vanilla in our example) which helps pacman in the decision? [pacman must choose from nvidia-vanilla and nvidia-beyond and if these packages "flagged" by the groups vanilla and beyond, pacman can do a "-Qg vanilla" and "-Qg beyond" and it will see, that the installed vanilla group is empty, so probably the user wants to install a beyond package]
It looks like handling these cases would add a lot of complexity, while it doesn't seem to involve a lot of work from the user. For example in this case, just do pacman -S nvidia-beyond first. I think that's realistic, and other cases like this one should be easily solvable too, but I could be wrong.
It looks like handling these cases would add a lot of complexity, while it doesn't seem to involve a lot of work from the user. For example in this case, just do pacman -S nvidia-beyond first. Of course, you are right, but this is a simple example; and user doesn't (and of course he can't) get any warning message or anything which he should know from that something is "not optimal" here... And in my "dream" packaging scheme (as I described) this is a common case (and the user shouldn't know much about -alsa, -oss and provisions at all ;-) Bye, ngaba
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Thu, Jul 12, 2007 at 09:09:41PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Wouldn't it be better to use **list instead then ? AFAIK, if we'd use **list, that assumption could be dropped. Bye, ngaba
I see, that's also the problem you had with your previous patch for removedeps. I took it back, and made a few changes, including usage of **targs instead of targs. I also renamed removedeps to recursedeps, added an include_explicit argument, and added some comments. Does this look ok to you ?
From e9ec64516957efb3eba4a9226ac52131636fa013 Mon Sep 17 00:00:00 2001 From: Chantry Xavier <shiningxc@gmail.com> Date: Fri, 13 Jul 2007 15:30:37 +0200 Subject: [PATCH] libalpm/deps.c : fix for remove044 pactest.
Patch from Nagy that makes removedeps use alpm_depcmp. I also renamed removedeps to recursedeps, as it can have a more general usage, and added an include_explicit argument, so we can control if packages explictly installed are added or not. Signed-off-by: Chantry Xavier <shiningxc@gmail.com> --- lib/libalpm/deps.c | 100 +++++++++++++++++++++++-------------------------- lib/libalpm/deps.h | 2 +- lib/libalpm/remove.c | 10 ++-- 3 files changed, 53 insertions(+), 59 deletions(-) diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c index 591e5a8..fa99630 100644 --- a/lib/libalpm/deps.c +++ b/lib/libalpm/deps.c @@ -484,8 +484,10 @@ pmdepend_t SYMEXPORT *alpm_splitdep(const char *depstring) /* 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 */ -static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets) + * target list. We do not remove it either if the package was + * explictly installed, and include_explicit == 0 */ +static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets, + int include_explicit) { alpm_list_t *i; @@ -493,13 +495,21 @@ static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets) return(0); } - /* see if it was explicitly installed */ - if(alpm_pkg_get_reason(pkg) == PM_PKG_REASON_EXPLICIT) { - _alpm_log(PM_LOG_DEBUG, "excluding %s -- explicitly installed", - alpm_pkg_get_name(pkg)); - return(0); + if(!include_explicit) { + /* see if it was explicitly installed */ + if(alpm_pkg_get_reason(pkg) == PM_PKG_REASON_EXPLICIT) { + _alpm_log(PM_LOG_DEBUG, "excluding %s -- explicitly installed", + alpm_pkg_get_name(pkg)); + return(0); + } } + /* TODO: checkdeps could be used there, it handles multiple providers + * better, but that also makes it slower. + * Also this would require to first add the package to the targets list, + * then call checkdeps with it, then remove the package from the targets list + * if checkdeps detected it would break something */ + /* see if other packages need it */ for(i = alpm_pkg_get_requiredby(pkg); i; i = i->next) { pmpkg_t *reqpkg = _alpm_db_get_pkgfromcache(db, i->data); @@ -512,71 +522,55 @@ 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. +/* Adds un-needed dependencies in a list of packages + * By un-needed, I mean dependencies that are *only* required for packages in the target + * list, so they can be safely removed. + * @param targs pointer to a list of packages + * @param include_explicit if set to 0, then explictly installed packages are not added */ -alpm_list_t *_alpm_removedeps(pmdb_t *db, alpm_list_t *targs) +void _alpm_recursedeps(pmdb_t *db, alpm_list_t **targs, int include_explicit) { alpm_list_t *i, *j, *k; - alpm_list_t *newtargs = targs; ALPM_LOG_FUNC; - if(db == NULL) { - return(newtargs); + if(db == NULL || targs == NULL) { + 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); + /* TODO: the while loop should be removed if we can assume + * that alpm_list_add (or another function) adds to the end of the list, + * and that the target list is topo sorted (by _alpm_sortbydeps()). + */ + 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, include_explicit)) { + _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 * diff --git a/lib/libalpm/deps.h b/lib/libalpm/deps.h index 2edbb50..f11a19a 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(pmdb_t *db, pmtranstype_t op, alpm_list_t *packages); -alpm_list_t *_alpm_removedeps(pmdb_t *db, alpm_list_t *targs); +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); diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c index 57e452d..9876f41 100644 --- a/lib/libalpm/remove.c +++ b/lib/libalpm/remove.c @@ -131,11 +131,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); @@ -143,6 +138,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_recursedeps(db, &trans->packages, 0); + } + EVENT(trans, PM_TRANS_EVT_CHECKDEPS_DONE, NULL, NULL); } -- 1.5.2.2
But maybe that move to kernel list could be done quicker than I think, I actually don't really know. Well, to tell the truth, I'm not impressed by the kernel list, what are its benefits? It's not clear to me, how can we easily reuse some allocated memory (such as a pmpkg_t entry) in a new list. Bye, ngaba
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
Hi! I think *targs can be used instead of **targs in recursedeps; the assumption is needed for speed efficiency only and keeping topo sort. (So be careful when patching remove.c, this assumption is used!). Anyway, the topo-sorted invariancy should be mentioned in the description of recursedeps, IMHO. I like your include_explicit variable :-P Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Fri, Jul 13, 2007 at 10:11:02PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Hi! I think *targs can be used instead of **targs in recursedeps; the assumption is needed for speed efficiency only and keeping topo sort.
This is a line from your original patch there : http://www.archlinux.org/pipermail/pacman-dev/2007-June/008539.html + * assumptions: alpm_list_add adds new member to the end of the list, so we can reuse the list pointer IMO it isn't necessarily the end, as long as it adds after the first element. I think this assumption is needed now with the way you changed the function (adding the new elements to the list passed in argument, instead of returning a new list). But when using **targs, we don't need that. For keeping toposort however, we do need a function that explicitly add to the end of the list, which we don't have now.
(So be careful when patching remove.c, this assumption is used!).
What do you mean there ? If we remove the while(!ready) loop, we will indeed need to sort the list before. I applied this part of your patch anyway, even if it isn't used now, it might be used later, if we remove that while loop.
Anyway, the topo-sorted invariancy should be mentioned in the description of recursedeps, IMHO.
This isn't needed currently, but I marked it as a TODO. That's why I removed it from the description. It should obviously be added back when we have a alpm_list_add_last or something, which would allow us to kill this TODO :)
I like your include_explicit variable :-P
hm, really? :d
This is a line from your original patch there : http://www.archlinux.org/pipermail/pacman-dev/2007-June/008539.html + * assumptions: alpm_list_add adds new member to the end of the list, so we can reuse the list pointer Well, then I wasn't clear here (or I changed the function and forgot about this comment, I don't remember yet;-).
IMO it isn't necessarily the end, as long as it adds after the first element. I think this assumption is needed now with the way you changed the function (adding the new elements to the list passed in argument, instead of returning a new list). But when using **targs, we don't need that. Oh, I see, you are right, similarly for alpm_resolvedeps (we talked about this yesterday):-P
What do you mean there ? I put the removedeps call after topo sort for efficiency, so this should be rejected until the topo-sort invariancy is not guaranteed.
If we remove the while(!ready) loop, we will indeed need to sort the list before. IMHO no :-P
Bye, ngaba. ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Fri, Jul 13, 2007 at 10:37:41PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
What do you mean there ? I put the removedeps call after topo sort for efficiency, so this should be rejected until the topo-sort invariancy is not guaranteed.
oh sorry, you're right, silly me, I shouldn't have moved this part (that should be done only when the TODO is done, sorry).
If we remove the while(!ready) loop, we will indeed need to sort the list before. IMHO no :-P
What do you mean, no ? :) You are the one who said that, and I think you're right. The while(!ready) loop could be removed if the list is initially sorted, and if we keep it sorted, by adding to the end of the list.
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
What do you mean, no ? :) You are the one who said that, and I think you're right. The while(!ready) loop could be removed if the list is initially sorted, and if we keep it sorted, by adding to the end of the list.
I said (or I wanted to say) that while(!ready) can be removed if alpm_list_add == alpm_list_add_last. The initial topo sort is needed if we want to keep the topo sort (of course). Bye, ngaba ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Fri, Jul 13, 2007 at 11:33:06PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
What do you mean, no ? :) You are the one who said that, and I think you're right. The while(!ready) loop could be removed if the list is initially sorted, and if we keep it sorted, by adding to the end of the list.
I said (or I wanted to say) that while(!ready) can be removed if alpm_list_add == alpm_list_add_last. The initial topo sort is needed if we want to keep the topo sort (of course).
ok, we're all clear then :)
+ sync = _alpm_db_get_pkgfromcache(j->data, missdep->name); + found = alpm_depcmp(sync, missdep); Hi! Since sync can be NULL here (if not found), if (sync = _alpm_db_get_pkgfromcache(j->data, missdep->name)) found = alpm_depcmp(sync, missdep); would be better imho. Bye, ngaba
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On 7/14/07, ngaba@petra.hos.u-szeged.hu <ngaba@petra.hos.u-szeged.hu> wrote:
+ sync = _alpm_db_get_pkgfromcache(j->data, missdep->name); + found = alpm_depcmp(sync, missdep); Hi! Since sync can be NULL here (if not found), if (sync = _alpm_db_get_pkgfromcache(j->data, missdep->name)) found = alpm_depcmp(sync, missdep); would be better imho. Bye, ngaba
I'm glad you are so willing to help us improve pacman, but I really just groan when I see something like the above. Even if it isn't a patch, can you at least try to using spacing and line breaks properly? This goes for both code and discussion. Thanks. -Dan
On Sat, Jul 14, 2007 at 09:40:37PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
+ sync = _alpm_db_get_pkgfromcache(j->data, missdep->name); + found = alpm_depcmp(sync, missdep); Hi! Since sync can be NULL here (if not found), if (sync = _alpm_db_get_pkgfromcache(j->data, missdep->name)) found = alpm_depcmp(sync, missdep); would be better imho.
Oops, you're perfectly right, thanks. I fixed it. Otherwise, it looks ok ?
Otherwise, it looks ok ? Yes.
---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.
On Sat, Jul 14, 2007 at 10:11:44PM +0200, ngaba@petra.hos.u-szeged.hu wrote:
Otherwise, it looks ok ? Yes.
Ok, thanks :) Btw, I think it didn't matter at all in this case that you didn't provide a patch, since it was rather a patch of my own patch, and a silly mistake from me. A patch might have been nicer (cleanly written code, references to functions and line numbers etc), but it was already very clear this way. Though in many other cases, a patch is indeed much more helpful and clear, so I'll still have to agree with Dan.
participants (3)
-
Dan McGee
-
ngaba＠petra.hos.u-szeged.hu
-
Xavier