Summary: | [PATCH] Build up a full depgraph | ||
---|---|---|---|
Product: | Portage Development | Reporter: | Jason Stubbs (RETIRED) <jstubbs> |
Component: | Core - Dependencies | Assignee: | Portage team <dev-portage> |
Status: | RESOLVED FIXED | ||
Severity: | normal | CC: | dberkholz, gent_bz, nico-mahlo |
Priority: | High | Keywords: | InVCS |
Version: | 2.1 | ||
Hardware: | All | ||
OS: | Linux | ||
Whiteboard: | |||
Package list: | Runtime testing required: | --- | |
Bug Depends on: | |||
Bug Blocks: | 155723, 16365, 147007 | ||
Attachments: |
New digraph
New digraph v2 Alterations to emerge to build a full depgraph New digraph v2 leaf_nodes fix full depgraph fix for package.provided use arg= instead of force_merge= Rolled up patches thus far More modifications... Rolling up the above two patches Add PDEPEND info to the graph New --tree implementation to kill off digraph.depth() Fixes bug in previous --tree reimplementation Tree implementation take 3 Fix for logic error with dep_zapdeps debug log for qt double merge use fakedbapi with slot support for blockers and dep_zapdeps |
Description
Jason Stubbs (RETIRED)
2006-09-15 22:28:59 UTC
Created attachment 97111 [details, diff]
New digraph
Rewritten digraph that allows deleting nodes that still have dependencies without breaking internal consistency. Also adds a feature that allows dependencies to be distinguished between hard and soft. This feature will make more sense with the next patch. This patch contains a small change to emerge where it was playing with digraph internals directly - there may be more of these type of changes to come.
Created attachment 97113 [details, diff]
New digraph v2
Bit quick to upload a patch. ;)
This just cleans up a the API and adds other functions that will be needed later. Forget to mention earlier that the previous API shouldn't break whatsoever except in the case of depth().
Created attachment 97122 [details, diff]
Alterations to emerge to build a full depgraph
As promised, patch #2. A full graph is now built. Packages that are already installed or are only required due to being R/PDEPENDs are added as soft deps. If there are no packages in the graph that have no children, an arbitrary package with only soft deps is chosen after which installing packages with no deps at all is tried again.
The hard/soft dep stuff seems to be working properly and --emptytree, --update, [no opts], --noreplace, etc seem to be working properly but I haven't tested too much yet. With this patch, the "can't install due to circular dependencies" should work again now but I have not tested a situation where there are circular dependencies between DEPENDs and installed packages can't satisfy any of the atoms.
This patch will likely get a v2 as well. It's not as clean as it could be. I've only gone as far as to get it working. The basics are all there though...
Created attachment 97180 [details]
New digraph v2 leaf_nodes fix
This patch applies on top of "New digraph v2" and fixes a few issues so that it can behave exactly like the original digraph class:
1) Gather leaf nodes in order of self.order (formerly self.okeys).
2) Fix incorrect leaf node identification logic (with include_soft_deps=False, it incorrectly idendified *all* nodes as leaf nodes).
3) Use include_soft_deps=True when calling leaf_nodes from firstzero, since nodes that truely have no deps should be prefered over those that have soft deps.
/me would prefer delnode returning T/F or throwing; depending on whether the node exists or not. Created attachment 97190 [details, diff]
full depgraph fix for package.provided
This patch applies on top of the "full depgraph" patch and fixes select_dep to ignore deps returned by dep_check if they are matched by something in package.provided. It also inverts include_soft_deps in the altlist leaf_nodes call so that it's consistent with the digraph patch that I've attached earlier. The way that my patches are written, include_soft_deps should probably be renamed to ignore_soft_deps. Anyway, with the addition of my two patches, the whole thing seems to work correctly for me. :)
I'm what the purpose is of the force_merge variable and "selective" in the initial myparams. After removing those parts of the patch, it still seems to behave well for me. `emerge <already_installed_app>` wasn't working without it. Will follow up on the other bits a bit later. Created attachment 97292 [details, diff] use arg= instead of force_merge= (In reply to comment #8) > `emerge <already_installed_app>` wasn't working without it. I see that now. This new patch (applies on top of all the others) replaces the force_merge= parameter with the preexisting arg= parameter. It seems like this might be a bit cleaner, since there is overlap between the meaning of the two parameters. This patch seems to behave correctly in my tests. Created attachment 97305 [details, diff]
Rolled up patches thus far
I thought the changes to use the new digraph would be bigger, but the combined patch is not overly big so rolling it up.
Created attachment 97306 [details, diff]
More modifications...
* Change hard_dep method parameters to soft_dep for conformity
* Change remove() to throw a KeyError when the node doesn't exist
* Change include_soft_deps to ignore_soft_deps for intuitiveness
* Document undocumented digraph methods
* Clarify childless nodes in debug_print()
* Remove redundant additions of "selective"
* Remove unneeded separate paths for "/" and $ROOT
With your changes related to include_soft_deps of leaf_nodes(), your goal was the same as mine - I just incredibly fumbled the implementation. To reiterate, leaf_nodes() by default should only return nodes that have no deps rather than return nodes that have only hard deps. I think the other changes should be pretty self-explanatory but let me know if there any questions.
Created attachment 97307 [details, diff]
Rolling up the above two patches
Patch against 2.1.2_pre1
Thanks! This is in svn r4472. Created attachment 97312 [details, diff]
Add PDEPEND info to the graph
PDEPEND being added without any parent only works because there was an implicit guarantee that any package selected after the PDEPEND that depends on the PDEPEND parent will also have its dep info thrown away. That implicit guarantee is no longer true so the ordering info needs to be added to the graph. This patch adds yet another parameter "rev_dep(s)" on select_dep and create which causes create to switch the parent/child relationship when adding to the graph.
Thanks again. That's in svn r4473. There's still the --tree patch to come... Having a little bit of difficulty trying to do it without touching too much stuff. Created attachment 97324 [details, diff]
New --tree implementation to kill off digraph.depth()
Hopefully not too hard to read.. Using root_nodes() gets a more accurate tree representation. However, the packages listed don't come out in strictly reverse order. Perhaps the heading text needs to be changed as well?
Created attachment 97329 [details, diff]
Fixes bug in previous --tree reimplementation
Nodes in the graph / merge list only have three parts for blockers. Check whether it's nomerge by indexing at [-1] instead of at [3] (as was being done previously).
Created attachment 97336 [details, diff]
Tree implementation take 3
Somehow managed to post the same tree patch twice :/
That's in svn r4479. Are we done yet? ;) Except for any other latent bugs like that --buildpkgonly one you found, that's pretty much it. :) There's a patch on 16365 if you're interested in reviewing something else. ;) This has been released in 2.1.2_pre1-r1. There is one recursive call to dep_zapdeps that doesn't yet pass in the return_all_deps parameter, meaning that the depgraph still isn't complete. In order to handle that case correctly, we can pass in something like a fakedbapi instance and use that instead of the vardb. This issue was brought to my attention by a user that reported these two lines in the same emerge -DupN command: [ebuild R ] x11-libs/qt-3.3.6-r1 USE="cups gif opengl -debug -doc -examples (-firebird) -immqt -immqt-bc -ipv6* -mysql -nas -nis -odbc -postgres -sqlite -xinerama" 0 kB [ebuild U ] x11-libs/qt-3.3.6-r2 [3.3.6-r1] USE="cups gif opengl -debug -doc -examples (-firebird) -immqt -immqt-bc -ipv6* -mysql -nas -nis -odbc -postgres -sqlite -xinerama" 0 kB Inside dep_zapdeps, it selected qt-3.3.6-r1 because it was already installed, even though qt-3.3.6-r2 had already been added to the digraph. I can reproduce the lack of upgrading with the following ebuilds (test-b-1.0 installed) but can't reproduce the reinstallation issue. I'll look at the upgrade issue for the time being. Can anyone else reproduce the reinstallation issue? # for x in app-portage/test*/test*.ebuild; do echo $x; cat $x; done app-portage/testa/testa-1.0.ebuild KEYWORDS="~x86" DEPEND="|| ( =app-portage/testb-1.1 =app-portage/testb-1.0 )" app-portage/testb/testb-1.0.ebuild KEYWORDS="~x86" app-portage/testb/testb-1.1.ebuild KEYWORDS="~x86" Created attachment 98131 [details, diff]
Fix for logic error with dep_zapdeps
Sorry about the missing return_deps param, but it's unlikely to cause this bug. It would only apply to the "( a b )" in "|| ( ( a b ) c )" type constructs. I've rolled it into the patch anyway. Further handling by passing a fakedbapi instance or whatnot shouldn't be required as emerge already starts with an empty fakedbapi when updating...
The lack of upgrading problem comes from a logic error in dep_zapdeps - apologies again. Whereas the code should have been checking if any package of the atom's key is installed (in the actual vdb) when preferencing atoms, it was only checking if the specific atom is installed. The bulk of the patch fixes this. (By the way, isn't there a cleaner/pythonic way of my usage of unique_array() there?)
As for the installed package appearing as a reinstall as well as the upgrade appearing, I'm guessing that's purely due to --newuse being specified in combination with qt being in world (as well as the or dep). Will check and report back.
Nope... Would need a --debug log to be sure, but it's likely a long standing bug that happens regardless of the dep_zapdeps bug. For example, if some package specifically requires a later version than that which is installed but the installed version has already been added. A demonstrative case: # cat app-portage/testc/testc-1.0.ebuild KEYWORDS="~x86" DEPEND="=app-portage/testb-1.0" # cat app-portage/testb/testb-1.1.ebuild KEYWORDS="~x86" IUSE="blah" # cat app-portage/testb/testb-1.0.ebuild KEYWORDS="~x86" IUSE="blah" # emerge -uNvp testb testc | grep test [ebuild U ] app-portage/testb-1.1 [1.0] USE="-blah%" 0 kB [ebuild R ] app-portage/testb-1.0 USE="-blah%" 0 kB [ebuild N ] app-portage/testc-1.0 0 kB Created attachment 98153 [details]
debug log for qt double merge
(In reply to comment #25) > Further handling by passing a fakedbapi > instance or whatnot shouldn't be required as emerge already starts with an > empty fakedbapi when updating... I was thinking that passing in a fakedbapi instance would allow dep_zapdeps to see that qt-3.3.6-r2 had been added to the graph, and prefer it over qt-3.3.6-r1 which happens to be installed. > The lack of upgrading problem comes from a logic error in dep_zapdeps - > apologies again. Whereas the code should have been checking if any package of > the atom's key is installed (in the actual vdb) when preferencing atoms, it > was only checking if the specific atom is installed. That won't necessarily preference specific atoms correctly though, qt-3.3.6-r1 and qt-3.3.6-r2 being a perfect example: || ( =x11-libs/qt-3.3.6-r2 =x11-libs/qt-3.3.6-r1 ... ) > The bulk of the patch fixes > this. (By the way, isn't there a cleaner/pythonic way of my usage of > unique_array() there?) set() > As for the installed package appearing as a reinstall as well as the upgrade > appearing, I'm guessing that's purely due to --newuse being specified in > combination with qt being in world (as well as the or dep). Will check and > report back. The debug log shows that qt-3.3.6-r1 was incorrectly selected because it happened to be installed. (In reply to comment #25) > Further handling by passing a fakedbapi > instance or whatnot shouldn't be required as emerge already starts with an > empty fakedbapi when updating... I should have mentioned that the debug log from comment #27 was created with portage-2.1.2_pre1-r3. In that version, the "empty" depgraph parameter is only implied by --emptytree. I changed it because the "empty" parameter seemed like it was overloaded too much, making the depgraph logic confusing. Now that I think about it some more though, that can cause the fakedbapi to contain multiple packages of the same slot, which isn't desireable. Created attachment 98186 [details, diff]
use fakedbapi with slot support for blockers and dep_zapdeps
This patch adds slot support (including aux_get) to fakedbapi and uses it for both depgraph blocker validation and for preference selection in dep_zapdeps. It seems to be working fine in my tests thus far.
The logic error from comment 25 is still an error though. Consider the case where qt is not in world and the only qt deps from all packages are in the form of: || ( =x11-libs/qt-3.3.6-r2 =x11-libs/qt-3.3.6-r1 ... ) Without the patch, qt will never be upgraded to -r2 if -r1 is installed. As for your patch from comment 30, it looks fine except for two things. Overloading the meaning of return_all_deps to also mean choosing between the passed dbapi and vardb is confusing as the why can only be deduced by looking at each caller. I'm looking at 2.1.2_pre1-r1 and there is only one call from depgraph and one call from depclean so I might be wrong, but.. When using --emptytree, preferences from installed packages won't be taken into account. This means that with "|| ( a b )" where b is installed, an --emptytree will install 'a' even though it should choose 'b'. (In reply to comment #31) > The logic error from comment 25 is still an error though. Consider the case > where qt is not in world and the only qt deps from all packages are in the form > of: > > || ( =x11-libs/qt-3.3.6-r2 =x11-libs/qt-3.3.6-r1 ... ) > > Without the patch, qt will never be upgraded to -r2 if -r1 is installed. > > As for your patch from comment 30, it looks fine except for two things. > Overloading the meaning of return_all_deps to also mean choosing between the > passed dbapi and vardb is confusing as the why can only be deduced by looking > at each caller. > > I'm looking at 2.1.2_pre1-r1 and there is only one call from depgraph and one > call from depclean so I might be wrong, but.. When using --emptytree, > preferences from installed packages won't be taken into account. This means > that with "|| ( a b )" where b is installed, an --emptytree will install 'a' > even though it should choose 'b'. Thanks, those are all good points. So, no fakedbapi in dep_zapdeps, and we're using the package name for an initial rough match against installed packages. I've kept the exact match for the match against available packages though, since it would be appropriate for that. This is fixed in svn r4543 and has been released in 2.1.2_pre1-r4. (In reply to comment #32) > I've kept the exact match for the match against available packages though, > since it would be appropriate for that. I can't find the original bug (if there ever was one) but this is a regression. The main problem is that kde-meta users won't get fixes to libraries as most of the kde deps are in the form of || ( ). Ignore the last comment. I just saw what you committed and you're right. I need to code slower. ;) *** Bug 162973 has been marked as a duplicate of this bug. *** *** Bug 180045 has been marked as a duplicate of this bug. *** |