Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!

Bug 147766

Summary: [PATCH] Build up a full depgraph
Product: Portage Development Reporter: Jason Stubbs (RETIRED) <jstubbs>
Component: Core - DependenciesAssignee: 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) gentoo-dev 2006-09-15 22:28:59 UTC
While this patch series won't solve all circular dependency issues, it'll solve the common ones, give a correct build order in many more cases and provide all the information needed for parallel building.

Not certain as to the number of patches yet. At this stage I have a rewritten digraph which I'll post in a minute. Next will be adjusting emerge to use the new hard-dep/soft-dep feature. Thirdly, which I only found was required by rewriting digraph, will be a reimplementation of --tree. --tree won't be today. ;)
Comment 1 Jason Stubbs (RETIRED) gentoo-dev 2006-09-15 22:32:13 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.
Comment 2 Jason Stubbs (RETIRED) gentoo-dev 2006-09-15 23:09:58 UTC
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().
Comment 3 Jason Stubbs (RETIRED) gentoo-dev 2006-09-16 00:48:06 UTC
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...
Comment 4 Zac Medico gentoo-dev 2006-09-16 14:12:21 UTC
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.
Comment 5 Alec Warner (RETIRED) archtester gentoo-dev Security 2006-09-16 15:48:25 UTC
/me would prefer delnode returning T/F or throwing; depending on whether the node exists or not.
Comment 6 Zac Medico gentoo-dev 2006-09-16 18:18:00 UTC
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. :)
Comment 7 Zac Medico gentoo-dev 2006-09-17 00:45:34 UTC
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.
Comment 8 Jason Stubbs (RETIRED) gentoo-dev 2006-09-17 00:51:30 UTC
`emerge <already_installed_app>` wasn't working without it. Will follow up on the other bits a bit later.
Comment 9 Zac Medico gentoo-dev 2006-09-17 18:38:49 UTC
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.
Comment 10 Jason Stubbs (RETIRED) gentoo-dev 2006-09-17 23:27:05 UTC
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.
Comment 11 Jason Stubbs (RETIRED) gentoo-dev 2006-09-17 23:32:18 UTC
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.
Comment 12 Jason Stubbs (RETIRED) gentoo-dev 2006-09-17 23:33:01 UTC
Created attachment 97307 [details, diff]
Rolling up the above two patches

Patch against 2.1.2_pre1
Comment 13 Zac Medico gentoo-dev 2006-09-18 01:33:53 UTC
Thanks!  This is in svn r4472.
Comment 14 Jason Stubbs (RETIRED) gentoo-dev 2006-09-18 02:13:43 UTC
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.
Comment 15 Zac Medico gentoo-dev 2006-09-18 03:21:28 UTC
Thanks again. That's in svn r4473.
Comment 16 Jason Stubbs (RETIRED) gentoo-dev 2006-09-18 03:29:02 UTC
There's still the --tree patch to come... Having a little bit of difficulty trying to do it without touching too much stuff.
Comment 17 Jason Stubbs (RETIRED) gentoo-dev 2006-09-18 04:23:45 UTC
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?
Comment 18 Jason Stubbs (RETIRED) gentoo-dev 2006-09-18 05:41:01 UTC
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).
Comment 19 Jason Stubbs (RETIRED) gentoo-dev 2006-09-18 07:05:17 UTC
Created attachment 97336 [details, diff]
Tree implementation take 3

Somehow managed to post the same tree patch twice :/
Comment 20 Zac Medico gentoo-dev 2006-09-18 23:49:46 UTC
That's in svn r4479.  Are we done yet? ;)
Comment 21 Jason Stubbs (RETIRED) gentoo-dev 2006-09-19 08:11:42 UTC
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. ;)
Comment 22 Zac Medico gentoo-dev 2006-09-22 19:24:57 UTC
This has been released in 2.1.2_pre1-r1.
Comment 23 Zac Medico gentoo-dev 2006-09-26 02:19:08 UTC
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.
Comment 24 Jason Stubbs (RETIRED) gentoo-dev 2006-09-26 05:42:54 UTC
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"

Comment 25 Jason Stubbs (RETIRED) gentoo-dev 2006-09-26 08:31:19 UTC
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.
Comment 26 Jason Stubbs (RETIRED) gentoo-dev 2006-09-26 08:40:45 UTC
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
Comment 27 Zac Medico gentoo-dev 2006-09-26 11:09:10 UTC
Created attachment 98153 [details]
debug log for qt double merge
Comment 28 Zac Medico gentoo-dev 2006-09-26 11:41:30 UTC
(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.
Comment 29 Zac Medico gentoo-dev 2006-09-26 16:07:06 UTC
(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.
Comment 30 Zac Medico gentoo-dev 2006-09-26 21:23:25 UTC
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.
Comment 31 Jason Stubbs (RETIRED) gentoo-dev 2006-09-27 07:13:05 UTC
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'.
Comment 32 Zac Medico gentoo-dev 2006-09-27 09:59:49 UTC
(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.
Comment 33 Zac Medico gentoo-dev 2006-09-27 13:45:06 UTC
This is fixed in svn r4543 and has been released in 2.1.2_pre1-r4.
Comment 34 Jason Stubbs (RETIRED) gentoo-dev 2006-09-29 07:14:40 UTC
(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 || ( ).
Comment 35 Jason Stubbs (RETIRED) gentoo-dev 2006-09-29 07:18:04 UTC
Ignore the last comment. I just saw what you committed and you're right. I need to code slower. ;)
Comment 36 Zac Medico gentoo-dev 2007-01-20 20:15:50 UTC
*** Bug 162973 has been marked as a duplicate of this bug. ***
Comment 37 Zac Medico gentoo-dev 2007-06-29 05:19:14 UTC
*** Bug 180045 has been marked as a duplicate of this bug. ***