[gentoo-portage-dev] building dependency tree

[gentoo-portage-dev] building dependency tree

[Andrew Gaffney]

I am writing a Perl program that does the same thing as 'emerge'. Yes, I started 
a thread about this on -dev about 6 months back, but I'm better prepared to do 
this now. I've already written functions that:

   * Build a list of USE flags from /etc/make.profile/make.defaults, 
/etc/make.conf, and $ENV{USE}
   * Build a list of masked packages from /etc/make.profile/package.(un)mask and 
/etc/portage/package.(un)mask
   * Build a list of matching ebuild versions from a '>category/package-version' 
type string taking masked packages into account
   * Extract the DEPEND line from a particular ebuild
   * Parse a DEPEND line using active USE flags and build a list of needed packages

I'm starting work on the code that generates the actual dependency tree and then 
the list of packages to be installed. I don't have any Python skill, so I don't 
think that reading the code will help me much. Can anyone who deals with the 
Portage code a lot give me a general breakdown of the way that 'emerge' 
generates the dependency tree and then the list of packages to emerge?

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Pieter Van den Abeele]

On 12 May 2004, at 05:02, Andrew Gaffney wrote:

> and then the list of packages to emerge

A topological ordering on the relevant digraph.

The relevant digraph as computed by portage is a 'tree' (note: cycles 
filtered) which is created by performing a (series of) walk(s) in the 
graph (portage "tree"). Dependencies = edges, for each ebuild there are 
2^n (where n = number of USE flags in the ebuilds IUSE) choice nodes in 
the graph.

I believe a DFS and BFS strategy have been suggested for the walk on 
this list, each having their own advantages and disadvantages. The main 
issue with the search strategy used by portage is that the runtime 
complexity explodes when you try to implement stuff like 'package foo 
conflicts with package bar' (the best we can do is without causing the 
explosion is: package foo version X conflicts with package foo version 
Y (same package - different version - 'slot' functionality). Of course 
there are solutions to this problem, but those fall outside the scope 
of your question :-)

Best regards,

Pieter Van den Abeele


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Andrew Gaffney]

Pieter Van den Abeele wrote:
> On 12 May 2004, at 05:02, Andrew Gaffney wrote:
> 
>> and then the list of packages to emerge
> 
> 
> A topological ordering on the relevant digraph.
> 
> The relevant digraph as computed by portage is a 'tree' (note: cycles 
> filtered) which is created by performing a (series of) walk(s) in the 
> graph (portage "tree"). Dependencies = edges, for each ebuild there are 
> 2^n (where n = number of USE flags in the ebuilds IUSE) choice nodes in 
> the graph.
> 
> I believe a DFS and BFS strategy have been suggested for the walk on 
> this list, each having their own advantages and disadvantages. The main 
> issue with the search strategy used by portage is that the runtime 
> complexity explodes when you try to implement stuff like 'package foo 
> conflicts with package bar' (the best we can do is without causing the 
> explosion is: package foo version X conflicts with package foo version Y 
> (same package - different version - 'slot' functionality). Of course 
> there are solutions to this problem, but those fall outside the scope of 
> your question :-)

I didn't understand much of what you said, but I think I'm getting somewhere 
anyway ;) In my program, I currently filter any DEPEND entries that contain a 
'$' or '*' or start with '!' or 'virtual' since those functionalities aren't 
implemented yet. A quick run shows the following. My program doesn't filter out 
duplicates yet so I ran it through 'sort -u'. I think it shows promise.

agaffney@kagome dev $ ./portage.pl x11-base/xfree | sort -u
app-arch/cabextract-0.6
app-arch/unzip-5.50-r2
app-crypt/hashalot-0.2.0
dev-lang/perl-5.8.4
dev-libs/expat-1.95.7
media-libs/fontconfig-2.2.2
media-libs/freetype-2.1.5-r1
media-libs/libpng-1.2.5-r5
sys-apps/baselayout-1.9.1
sys-apps/ed-0.2-r3
sys-apps/groff-1.19
sys-apps/pam-login-3.14
sys-apps/portage-2.0.50-r6
sys-apps/sed-4.0.9
sys-apps/shadow-4.0.4.1-r1
sys-apps/texinfo-4.6
sys-apps/util-linux-2.12-r4
sys-devel/autoconf-2.59-r3
sys-devel/automake-1.8.3
sys-devel/flex-2.5.4a-r5
sys-devel/gcc-config-1.3.5-r1
sys-devel/gettext-0.12.1-r1
sys-devel/libtool-1.5.2-r5
sys-devel/patch-2.5.9
sys-libs/cracklib-2.7-r9
sys-libs/db-1.85-r1
sys-libs/db-4.0.14-r3
sys-libs/gdbm-1.8.0-r5
sys-libs/ncurses-5.4-r1
sys-libs/pam-0.77-r1
sys-libs/zlib-1.2.1-r2
x11-base/opengl-update-1.6
x11-base/xfree-4.3.0-r5
x11-misc/ttmkfdir-3.0.9-r1

That's pretty darn close to:

agaffney@kagome agaffney $ emerge -ep x11-base/xfree

These are the packages that I would merge, in order:

Calculating dependencies ...done!
[ebuild  N    ] app-crypt/hashalot-0.2.0
[ebuild  N    ] sys-devel/patch-2.5.9
[ebuild  N    ] sys-devel/gnuconfig-20040214
[ebuild  N    ] sys-apps/sed-4.0.9
[ebuild  N    ] sys-apps/texinfo-4.6
[ebuild  N    ] sys-libs/zlib-1.2.1-r2
[ebuild  N    ] dev-python/python-fchksum-1.7.1
[ebuild  N    ] app-shells/bash-2.05b-r9
[ebuild  N    ] sys-libs/readline-4.3-r5
[ebuild  N    ] sys-devel/flex-2.5.4a-r5
[ebuild  N    ] app-arch/bzip2-1.0.2-r3
[ebuild  N    ] sys-devel/automake-1.8.3
[ebuild  N    ] sys-apps/help2man-1.33.1
[ebuild  N    ] sys-apps/coreutils-5.2.0-r2
[ebuild  N    ] sys-apps/debianutils-1.16.7-r4
[ebuild  N    ] sys-apps/portage-2.0.50-r6
*** Please update portage to the above version before proceeding.
     Failure to do so may result in failed or improper merges.
     A simple 'emerge -u portage' is sufficient.

[ebuild  N    ] sys-devel/bc-1.06-r5
[ebuild  N    ] dev-libs/openssl-0.9.7d
[ebuild  N    ] dev-lang/tcl-8.4.6
[ebuild  N    ] dev-lang/tk-8.4.6
[ebuild  N    ] sys-libs/db-1.85-r1
[ebuild  N    ] sys-libs/gdbm-1.8.0-r5
[ebuild  N    ] dev-libs/expat-1.95.7
[ebuild  N    ] dev-lang/python-2.3.3-r1
[ebuild  N    ] dev-java/java-config-1.2.6
[ebuild  N    ] dev-java/blackdown-jdk-1.4.1
[ebuild  N    ] sys-libs/db-4.1.25_p1-r3
[ebuild  N    ] sys-apps/groff-1.19
[ebuild  N    ] sys-devel/libperl-5.8.4
[ebuild  N    ] dev-lang/perl-5.8.4
[ebuild  N    ] sys-devel/autoconf-2.59-r3
[ebuild  N    ] sys-devel/libtool-1.5.2-r5
[ebuild  N    ] sys-devel/m4-1.4-r1
[ebuild  N    ] sys-devel/bison-1.875
[ebuild  N    ] sys-apps/cronbase-0.2.1-r3
[ebuild  N    ] sys-apps/man-1.5m-r1
[ebuild  N    ] sys-devel/gcc-config-1.3.5-r1
[ebuild  N    ] sys-devel/binutils-2.14.90.0.8-r1
[ebuild  N    ] sys-devel/gcc-3.3.3-r3
[ebuild  N    ] sys-apps/gawk-3.1.3-r1
[ebuild  N    ] sys-kernel/linux-headers-2.4.22
[ebuild  N    ] sys-apps/baselayout-1.9.1
[ebuild  N    ] sys-libs/glibc-2.3.3_pre20040420
[ebuild  N    ] sys-libs/ncurses-5.4-r1
[ebuild  N    ] dev-libs/glib-1.2.10-r5
[ebuild  N    ] sys-apps/miscfiles-1.3-r1
[ebuild  N    ] sys-libs/cracklib-2.7-r9
[ebuild  N    ] sys-libs/pam-0.77-r1
[ebuild  N    ] sys-apps/shadow-4.0.4.1-r1
[ebuild  N    ] sys-apps/pam-login-3.14
[ebuild  N    ] sys-apps/util-linux-2.12-r4
[ebuild  N    ] media-libs/libpng-1.2.5-r5
[ebuild  N    ] sys-apps/ed-0.2-r3
[ebuild  N    ] media-libs/freetype-2.1.5-r1
[ebuild  N    ] media-libs/fontconfig-2.2.2
[ebuild  N    ] x11-base/opengl-update-1.6
[ebuild  N    ] x11-misc/ttmkfdir-3.0.9-r1
[ebuild  N    ] app-arch/unzip-5.50-r2
[ebuild  N    ] app-arch/cabextract-0.6
[ebuild  N    ] x11-base/xfree-4.3.0-r5
-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Pieter Van den Abeele]

On 12 May 2004, at 08:42, Andrew Gaffney wrote:

> agaffney@kagome dev $ ./portage.pl x11-base/xfree | sort -u

> x11-base/xfree-4.3.0-r5
> x11-misc/ttmkfdir-3.0.9-r1

ttmkfdir is an xfree compile time dependency, so it has to be installed 
before xfree and not after :-)

Best regards,

Pieter Van den Abeele


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Andrew Gaffney]

Pieter Van den Abeele wrote:
> On 12 May 2004, at 08:42, Andrew Gaffney wrote:
> 
>> agaffney@kagome dev $ ./portage.pl x11-base/xfree | sort -u
> 
> 
>> x11-base/xfree-4.3.0-r5
>> x11-misc/ttmkfdir-3.0.9-r1
> 
> 
> ttmkfdir is an xfree compile time dependency, so it has to be installed 
> before xfree and not after :-)

I know. Like I said, my program currently only prints dependencies instead of 
tracking them in an array or hash, so it can't eliminate duplicates. Because of 
this, I ran the output through 'sort -u' which put them in alphabetical order 
instead of dependency order.

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Pieter Van den Abeele]

On 12 May 2004, at 16:43, Andrew Gaffney wrote:

> Pieter Van den Abeele wrote:
>> On 12 May 2004, at 08:42, Andrew Gaffney wrote:
>>> agaffney@kagome dev $ ./portage.pl x11-base/xfree | sort -u
>>> x11-base/xfree-4.3.0-r5
>>> x11-misc/ttmkfdir-3.0.9-r1
>> ttmkfdir is an xfree compile time dependency, so it has to be 
>> installed before xfree and not after :-)
>
> I know. Like I said, my program currently only prints dependencies 
> instead of tracking them in an array or hash, so it can't eliminate 
> duplicates. Because of this, I ran the output through 'sort -u' which 
> put them in alphabetical order instead of dependency order.

ok, that's what happens when you write email late in the morning :-)

Pieter

> -- 
> Andrew Gaffney
> Network Administrator
> Skyline Aeronautics, LLC.
> 636-357-1548
>
>
> --
> gentoo-portage-dev@gentoo.org mailing list
>


--
gentoo-portage-dev@gentoo.org mailing list

[gentoo-portage-dev] /etc/make.profile/use.defaults (was: building dependency tree)

[Andrew Gaffney]

Pieter Van den Abeele wrote:
> 
> On 12 May 2004, at 16:43, Andrew Gaffney wrote:
> 
>> Pieter Van den Abeele wrote:
>>
>>> On 12 May 2004, at 08:42, Andrew Gaffney wrote:
>>>
>>>> agaffney@kagome dev $ ./portage.pl x11-base/xfree | sort -u
>>>> x11-base/xfree-4.3.0-r5
>>>> x11-misc/ttmkfdir-3.0.9-r1
>>>
>>> ttmkfdir is an xfree compile time dependency, so it has to be 
>>> installed before xfree and not after :-)
>>
>>
>> I know. Like I said, my program currently only prints dependencies 
>> instead of tracking them in an array or hash, so it can't eliminate 
>> duplicates. Because of this, I ran the output through 'sort -u' which 
>> put them in alphabetical order instead of dependency order.
> 
> 
> ok, that's what happens when you write email late in the morning :-)

I've come across another issue. 'emerge -epvt xfree' shows that python wants to 
install tcl and tk because of the 'tcltk' USE flag where my program doesn't. 
That USE flag is not defined in my /etc/make.profile/make.defaults or 
/etc/make.conf. 'ufed' shows that it is defined in 
/etc/make.profile/use.defaults. I've never come across this file before. What 
does it do?

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Andrew Gaffney]

Andrew Gaffney wrote:
> Pieter Van den Abeele wrote:
> 
>>
>> On 12 May 2004, at 16:43, Andrew Gaffney wrote:
>>
>>> Pieter Van den Abeele wrote:
>>>
>>>> On 12 May 2004, at 08:42, Andrew Gaffney wrote:
>>>>
>>>>> agaffney@kagome dev $ ./portage.pl x11-base/xfree | sort -u
>>>>> x11-base/xfree-4.3.0-r5
>>>>> x11-misc/ttmkfdir-3.0.9-r1
>>>>
>>>>
>>>> ttmkfdir is an xfree compile time dependency, so it has to be 
>>>> installed before xfree and not after :-)
>>>
>>>
>>>
>>> I know. Like I said, my program currently only prints dependencies 
>>> instead of tracking them in an array or hash, so it can't eliminate 
>>> duplicates. Because of this, I ran the output through 'sort -u' which 
>>> put them in alphabetical order instead of dependency order.
>>
>>
>>
>> ok, that's what happens when you write email late in the morning :-)
> 
> 
> I've come across another issue. 'emerge -epvt xfree' shows that python 
> wants to install tcl and tk because of the 'tcltk' USE flag where my 
> program doesn't. That USE flag is not defined in my 
> /etc/make.profile/make.defaults or /etc/make.conf. 'ufed' shows that it 
> is defined in /etc/make.profile/use.defaults. I've never come across 
> this file before. What does it do?

Nevermind. From 'man portage':

use.defaults
     Here  we  DO  NOT  define  the  default  USE flags, but the so-called
     auto-USE flags.  This rather unknown portage feature activates a USE
     flag if a specific package is installed and the flag  was  not  explicitly
     deactivated.  This file contains the associations between USE flags and
     packages that trigger the auto-USE feature.

     In other words, if we never put "sdl" or "-sdl" into our USE, but we have
     media-libs/libsdl emerged, then portage automagically sticks "sdl" into our
     USE for us.

     Format:
     - comments begin with #
     - one USE flag per line with a list of DEPEND atom bases

     Example:
     # media-libs/libsdl will activate "sdl"
     sdl        media-libs/libsdl
     # activate tcltk only if we have both
     # dev-lang/tcl and dev-lang/tk
     tcltk      dev-lang/tcl   dev-lang/tk

That makes sense, but shouldn't Portage not use these when operating with the 
'--emptytree' flag since it pretends that nothing is installed?

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Pieter Van den Abeele]

On 12 May 2004, at 17:19, Andrew Gaffney wrote:

>> I've come across another issue. 'emerge -epvt xfree' shows that 
>> python wants to install tcl and tk because of the 'tcltk' USE flag 
>> where my program doesn't. That USE flag is not defined in my 
>> /etc/make.profile/make.defaults or /etc/make.conf. 'ufed' shows that 
>> it is defined in /etc/make.profile/use.defaults. I've never come 
>> across this file before. What does it do?
>
> Nevermind. From 'man portage':
>
> use.defaults
>     Here  we  DO  NOT  define  the  default  USE flags, but the 
> so-called
>     auto-USE flags.  This rather unknown portage feature activates a 
> USE
>     flag if a specific package is installed and the flag  was  not  
> explicitly
>     deactivated.  This file contains the associations between USE 
> flags and
>     packages that trigger the auto-USE feature.
>
>     In other words, if we never put "sdl" or "-sdl" into our USE, but 
> we have
>     media-libs/libsdl emerged, then portage automagically sticks "sdl" 
> into our
>     USE for us.
>
>     Format:
>     - comments begin with #
>     - one USE flag per line with a list of DEPEND atom bases
>
>     Example:
>     # media-libs/libsdl will activate "sdl"
>     sdl        media-libs/libsdl
>     # activate tcltk only if we have both
>     # dev-lang/tcl and dev-lang/tk
>     tcltk      dev-lang/tcl   dev-lang/tk
>
> That makes sense, but shouldn't Portage not use these when operating 
> with the '--emptytree' flag since it pretends that nothing is 
> installed?

I think that with 'installed' in this case they also include 'scheduled 
for installation' (although I'm not 100% sure). For instance If portage 
schedules tcl and tk in an emptytree, then the tcltk useflag will be 
enabled for packages having IUSE="tcltk" that are added to the schedule 
afterwards.

Pieter 


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Andrew Gaffney]

Pieter Van den Abeele wrote:
> 
> On 12 May 2004, at 17:19, Andrew Gaffney wrote:
> 
>>> I've come across another issue. 'emerge -epvt xfree' shows that 
>>> python wants to install tcl and tk because of the 'tcltk' USE flag 
>>> where my program doesn't. That USE flag is not defined in my 
>>> /etc/make.profile/make.defaults or /etc/make.conf. 'ufed' shows that 
>>> it is defined in /etc/make.profile/use.defaults. I've never come 
>>> across this file before. What does it do?
>>
>>
>> Nevermind. From 'man portage':
>>
>> use.defaults
>>     Here  we  DO  NOT  define  the  default  USE flags, but the so-called
>>     auto-USE flags.  This rather unknown portage feature activates a USE
>>     flag if a specific package is installed and the flag  was  not  
>> explicitly
>>     deactivated.  This file contains the associations between USE 
>> flags and
>>     packages that trigger the auto-USE feature.
>>
>>     In other words, if we never put "sdl" or "-sdl" into our USE, but 
>> we have
>>     media-libs/libsdl emerged, then portage automagically sticks "sdl" 
>> into our
>>     USE for us.
>>
>>     Format:
>>     - comments begin with #
>>     - one USE flag per line with a list of DEPEND atom bases
>>
>>     Example:
>>     # media-libs/libsdl will activate "sdl"
>>     sdl        media-libs/libsdl
>>     # activate tcltk only if we have both
>>     # dev-lang/tcl and dev-lang/tk
>>     tcltk      dev-lang/tcl   dev-lang/tk
>>
>> That makes sense, but shouldn't Portage not use these when operating 
>> with the '--emptytree' flag since it pretends that nothing is installed?
> 
> I think that with 'installed' in this case they also include 'scheduled 
> for installation' (although I'm not 100% sure). For instance If portage 
> schedules tcl and tk in an emptytree, then the tcltk useflag will be 
> enabled for packages having IUSE="tcltk" that are added to the schedule 
> afterwards.

But they are only 'scheduled for installation' if the USE flag is activated. The 
'--emptytree' flag gets emerge in some weird 'chicken and egg' situation. With 
'--emptytree' set, emerge should assume nothing is installed. If nothing is 
installed, then tcl and tk aren't installed and the 'tcltk' USE flag shouldn't 
be auto-activated.

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Pieter Van den Abeele]

On 12 May 2004, at 17:44, Andrew Gaffney wrote:

> But they are only 'scheduled for installation' if the USE flag is 
> activated. The '--emptytree' flag gets emerge in some weird 'chicken 
> and egg' situation. With '--emptytree' set, emerge should assume 
> nothing is installed. If nothing is installed, then tcl and tk aren't 
> installed and the 'tcltk' USE flag shouldn't be auto-activated.

true, unless of course tcl and tk are in the world file, or some other 
installed package depends on both, and therefore causes the tcltk use 
flag to be triggered.
but it should certainly not auto-enable the USE flag (if it isn't 
enabled specifically) because the current system has it enabled. 
--emptytree should assume nothing is installed

Pieter


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Andrew Gaffney]

Pieter Van den Abeele wrote:
> 
> On 12 May 2004, at 17:44, Andrew Gaffney wrote:
> 
>> But they are only 'scheduled for installation' if the USE flag is 
>> activated. The '--emptytree' flag gets emerge in some weird 'chicken 
>> and egg' situation. With '--emptytree' set, emerge should assume 
>> nothing is installed. If nothing is installed, then tcl and tk aren't 
>> installed and the 'tcltk' USE flag shouldn't be auto-activated.
> 
> 
> true, unless of course tcl and tk are in the world file, or some other 
> installed package depends on both, and therefore causes the tcltk use 
> flag to be triggered.
> but it should certainly not auto-enable the USE flag (if it isn't 
> enabled specifically) because the current system has it enabled. 
> --emptytree should assume nothing is installed

I don't think tcl or tk being in the world file would/should affect anything 
while '--emptytree' is in use. Also, I think that the only thing that depends on 
tcl or tk in the xfree dependency tree is python, and that's with the 'tcltk' 
USE flag. I believe this is a Portage bug.

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Jason Stubbs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 12 May 2004 12:02, Andrew Gaffney wrote:
> I am writing a Perl program that does the same thing as 'emerge'. Yes, I
> started a thread about this on -dev about 6 months back, but I'm better
> prepared to do this now. I've already written functions that:
>
>    * Build a list of USE flags from /etc/make.profile/make.defaults,
> /etc/make.conf, and $ENV{USE}
>    * Build a list of masked packages from
> /etc/make.profile/package.(un)mask and /etc/portage/package.(un)mask
>    * Build a list of matching ebuild versions from a
> '>category/package-version' type string taking masked packages into account
>    * Extract the DEPEND line from a particular ebuild
>    * Parse a DEPEND line using active USE flags and build a list of needed
> packages
>
> I'm starting work on the code that generates the actual dependency tree and
> then the list of packages to be installed. I don't have any Python skill,
> so I don't think that reading the code will help me much. Can anyone who
> deals with the Portage code a lot give me a general breakdown of the way
> that 'emerge' generates the dependency tree and then the list of packages
> to emerge?

As of .51:

Initial startup:
* Read configuration files
* Scan system for installed packages and auto-enable use flags and virtuals
* Create master configuration

Dep calculation:
* Is blocker? No? Continue...
  * Is a matching package installed? No? Continue...
    * Make record of blocked package and continue...
* Resolve atom to package
* Has package's already been added? Yes? Continue...
* Add package and note its parent
* Copy master configuration
* Is binary package? Adjust USE flags from build-time.
* Is source package? Adjust USE flags from package.use
* Parse DEPEND and RDEPEND and resolve against USE flags
  -- deps in "|| ( foo bar )" deps get preference by being installed
* Calculate deps for each atom parsed, with parent as this package
* Parse PDEPEND and resolve against USE flags
* Calculate deps for each atom parsed, with no parent

Order resolution:
* Find first added package that has no parents
* Add package to order and remove from tree
* Continue...

There are a number of problems in this logic, some of which you and Pieter 
have noticed. The ones you have mentioned, I've fixed in a complete rewrite. 
To fix the main flaws (package only gets the parent from when it is first 
added, and PDEPENDs having no parents) is next on the agenda but is quite 
difficult.

Regards,
Jason Stubbs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQCVAwUBQKJQCFoikN4/5jfsAQLmnQP+LblJ3Af8h0E+YUwrNrexeNJjgnBKHS6s
WwrFV2fBWh3U3H7nHE4a4u6IHGrF01VQXaZ/O5FKFNfuwcY9WG5PO5N5Ce7Cd1CJ
ZxORi5cIGgmuVwyQpfzw23Koeb4FlG+03Du/WDYnkT6qoMSnWH8+mesnUiMN3e1F
KVMzF6j7U2k=
=xIE3
-----END PGP SIGNATURE-----

--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Jason Stubbs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 13 May 2004 01:03, Pieter Van den Abeele wrote:
> On 12 May 2004, at 17:44, Andrew Gaffney wrote:
> > But they are only 'scheduled for installation' if the USE flag is
> > activated. The '--emptytree' flag gets emerge in some weird 'chicken
> > and egg' situation. With '--emptytree' set, emerge should assume
> > nothing is installed. If nothing is installed, then tcl and tk aren't
> > installed and the 'tcltk' USE flag shouldn't be auto-activated.
>
> true, unless of course tcl and tk are in the world file, or some other
> installed package depends on both, and therefore causes the tcltk use
> flag to be triggered.
> but it should certainly not auto-enable the USE flag (if it isn't
> enabled specifically) because the current system has it enabled.
> --emptytree should assume nothing is installed

This one, I'm undecided on. Strictly, --emptytree should assume nothing is 
installed. In practice though, many users use it to reinstall everything. If 
- --emptytree does actually assume nothing is installed, users could find 
themselves with blocked packages overwriting each other and wonderful things 
like that.

Two options I see are:
a) Keep current behaviour
b) Make --emptytree a --pretend only option and create a new --reinstall.

Regards,
Jason Stubbs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQCVAwUBQKJR7VoikN4/5jfsAQKJHgQAlJOygVUJAukcZRgpeWZJdivNf5ZyvOJR
u+/dyXs0nPqNju0OfRm2zzRMCQIlwotrdJCCyW0oBztdHyO82q7O0wyiuZbS5MPP
68EdAbVO5G6aeLM1sHgeuZVTNi8Xaw1Xtj6yb7Sz+wP+91NT/dtdwkf3eZHjohIx
M9Pjyi0Auzc=
=Ay+c
-----END PGP SIGNATURE-----

--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Andrew Gaffney]

Jason Stubbs wrote:
> On Thursday 13 May 2004 01:03, Pieter Van den Abeele wrote:
> 
>>>On 12 May 2004, at 17:44, Andrew Gaffney wrote:
>>>
>>>>But they are only 'scheduled for installation' if the USE flag is
>>>>activated. The '--emptytree' flag gets emerge in some weird 'chicken
>>>>and egg' situation. With '--emptytree' set, emerge should assume
>>>>nothing is installed. If nothing is installed, then tcl and tk aren't
>>>>installed and the 'tcltk' USE flag shouldn't be auto-activated.
>>>
>>>true, unless of course tcl and tk are in the world file, or some other
>>>installed package depends on both, and therefore causes the tcltk use
>>>flag to be triggered.
>>>but it should certainly not auto-enable the USE flag (if it isn't
>>>enabled specifically) because the current system has it enabled.
>>>--emptytree should assume nothing is installed
> 
> 
> This one, I'm undecided on. Strictly, --emptytree should assume nothing is 
> installed. In practice though, many users use it to reinstall everything. If 
> --emptytree does actually assume nothing is installed, users could find 
> themselves with blocked packages overwriting each other and wonderful things 
> like that.
> 
> Two options I see are:
> a) Keep current behaviour
> b) Make --emptytree a --pretend only option and create a new --reinstall.

I think it is more of a consistency bug than a function bug. I don't believe it 
causes any problems in practice, and I only stumbled across is because of the 
project I'm working on. I don't think it actually affects anyone.

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] /etc/make.profile/use.defaults

[Jason Stubbs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 13 May 2004 01:39, Andrew Gaffney wrote:
> Jason Stubbs wrote:
> > On Thursday 13 May 2004 01:03, Pieter Van den Abeele wrote:
> >>>On 12 May 2004, at 17:44, Andrew Gaffney wrote:
> >>>>But they are only 'scheduled for installation' if the USE flag is
> >>>>activated. The '--emptytree' flag gets emerge in some weird 'chicken
> >>>>and egg' situation. With '--emptytree' set, emerge should assume
> >>>>nothing is installed. If nothing is installed, then tcl and tk aren't
> >>>>installed and the 'tcltk' USE flag shouldn't be auto-activated.
> >>>
> >>>true, unless of course tcl and tk are in the world file, or some other
> >>>installed package depends on both, and therefore causes the tcltk use
> >>>flag to be triggered.
> >>>but it should certainly not auto-enable the USE flag (if it isn't
> >>>enabled specifically) because the current system has it enabled.
> >>>--emptytree should assume nothing is installed
> >
> > This one, I'm undecided on. Strictly, --emptytree should assume nothing
> > is installed. In practice though, many users use it to reinstall
> > everything. If --emptytree does actually assume nothing is installed,
> > users could find themselves with blocked packages overwriting each other
> > and wonderful things like that.
> >
> > Two options I see are:
> > a) Keep current behaviour
> > b) Make --emptytree a --pretend only option and create a new --reinstall.
>
> I think it is more of a consistency bug than a function bug. I don't
> believe it causes any problems in practice, and I only stumbled across is
> because of the project I'm working on. I don't think it actually affects
> anyone.

But if the current behaviour was changed, there would be many that notice. 
Jump into #gentoo or post on gentoo-user@g.o and ask how to reinstall 
everything. You'll get many answers of emerge -e world and a few saying that 
it's not enough and that you'll have to emerge $(qpkg -I).

Regards,
Jason Stubbs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQCVAwUBQKJeuVoikN4/5jfsAQLr9wP/UFqMXFz3bfvmHL/l4EDJ3wgqBl45Y7ps
Q3GxzZYWT67rCD2fCHkFE+qUAY9ZZf2TsbTWp6KUI9MFI7ebAnfWb1KsJJ4cRz/v
Bh1inr/lhsLS/Vq8C3Wkf8zIHh652q22HygI/neIOGhi6KhzdZpldYwl7Ok26Zf2
0BKmrak0VjA=
=fMF3
-----END PGP SIGNATURE-----

--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Andrew Gaffney]

Jason Stubbs wrote:
> On Wednesday 12 May 2004 12:02, Andrew Gaffney wrote:
> 
>>>I am writing a Perl program that does the same thing as 'emerge'. Yes, I
>>>started a thread about this on -dev about 6 months back, but I'm better
>>>prepared to do this now. I've already written functions that:
>>>
>>>   * Build a list of USE flags from /etc/make.profile/make.defaults,
>>>/etc/make.conf, and $ENV{USE}
>>>   * Build a list of masked packages from
>>>/etc/make.profile/package.(un)mask and /etc/portage/package.(un)mask
>>>   * Build a list of matching ebuild versions from a
>>>'>category/package-version' type string taking masked packages into account
>>>   * Extract the DEPEND line from a particular ebuild
>>>   * Parse a DEPEND line using active USE flags and build a list of needed
>>>packages
>>>
>>>I'm starting work on the code that generates the actual dependency tree and
>>>then the list of packages to be installed. I don't have any Python skill,
>>>so I don't think that reading the code will help me much. Can anyone who
>>>deals with the Portage code a lot give me a general breakdown of the way
>>>that 'emerge' generates the dependency tree and then the list of packages
>>>to emerge?
> 
> 
> As of .51:
> 
> Initial startup:
> * Read configuration files
> * Scan system for installed packages and auto-enable use flags and virtuals
> * Create master configuration
> 
> Dep calculation:
> * Is blocker? No? Continue...
>   * Is a matching package installed? No? Continue...
>     * Make record of blocked package and continue...
> * Resolve atom to package
> * Has package's already been added? Yes? Continue...
> * Add package and note its parent
> * Copy master configuration
> * Is binary package? Adjust USE flags from build-time.
> * Is source package? Adjust USE flags from package.use
> * Parse DEPEND and RDEPEND and resolve against USE flags
>   -- deps in "|| ( foo bar )" deps get preference by being installed
> * Calculate deps for each atom parsed, with parent as this package
> * Parse PDEPEND and resolve against USE flags
> * Calculate deps for each atom parsed, with no parent
> 
> Order resolution:
> * Find first added package that has no parents
> * Add package to order and remove from tree
> * Continue...
> 
> There are a number of problems in this logic, some of which you and Pieter 
> have noticed. The ones you have mentioned, I've fixed in a complete rewrite. 
> To fix the main flaws (package only gets the parent from when it is first 
> added, and PDEPENDs having no parents) is next on the agenda but is quite 
> difficult.

You've already done a complete rewrite of the dependency resolver?

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Jason Stubbs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 15 May 2004 13:12, Andrew Gaffney wrote:
> Jason Stubbs wrote:
> > On Wednesday 12 May 2004 12:02, Andrew Gaffney wrote:
> >>>I am writing a Perl program that does the same thing as 'emerge'. Yes, I
> >>>started a thread about this on -dev about 6 months back, but I'm better
> >>>prepared to do this now. I've already written functions that:
> >>>
> >>>   * Build a list of USE flags from /etc/make.profile/make.defaults,
> >>>/etc/make.conf, and $ENV{USE}
> >>>   * Build a list of masked packages from
> >>>/etc/make.profile/package.(un)mask and /etc/portage/package.(un)mask
> >>>   * Build a list of matching ebuild versions from a
> >>>'>category/package-version' type string taking masked packages into
> >>> account * Extract the DEPEND line from a particular ebuild
> >>>   * Parse a DEPEND line using active USE flags and build a list of
> >>> needed packages
> >>>
> >>>I'm starting work on the code that generates the actual dependency tree
> >>> and then the list of packages to be installed. I don't have any Python
> >>> skill, so I don't think that reading the code will help me much. Can
> >>> anyone who deals with the Portage code a lot give me a general
> >>> breakdown of the way that 'emerge' generates the dependency tree and
> >>> then the list of packages to emerge?
> >
> > As of .51:
> >
> > Initial startup:
> > * Read configuration files
> > * Scan system for installed packages and auto-enable use flags and
> > virtuals * Create master configuration
> >
> > Dep calculation:
> > * Is blocker? No? Continue...
> >   * Is a matching package installed? No? Continue...
> >     * Make record of blocked package and continue...
> > * Resolve atom to package
> > * Has package's already been added? Yes? Continue...
> > * Add package and note its parent
> > * Copy master configuration
> > * Is binary package? Adjust USE flags from build-time.
> > * Is source package? Adjust USE flags from package.use
> > * Parse DEPEND and RDEPEND and resolve against USE flags
> >   -- deps in "|| ( foo bar )" deps get preference by being installed
> > * Calculate deps for each atom parsed, with parent as this package
> > * Parse PDEPEND and resolve against USE flags
> > * Calculate deps for each atom parsed, with no parent
> >
> > Order resolution:
> > * Find first added package that has no parents
> > * Add package to order and remove from tree
> > * Continue...
> >
> > There are a number of problems in this logic, some of which you and
> > Pieter have noticed. The ones you have mentioned, I've fixed in a
> > complete rewrite. To fix the main flaws (package only gets the parent
> > from when it is first added, and PDEPENDs having no parents) is next on
> > the agenda but is quite difficult.
>
> You've already done a complete rewrite of the dependency resolver?

Yes and no. I started from scratch but used almost exactly the same logic. I 
guess you could almost call it refactoring. Have a look at:
http://www.gentoo.org/cgi-bin/viewcvs.cgi/portage-mod/portageapi/?root=gentoo-src

Of interest to you, will probably be dep.py. Even if you do not understand 
python, the logic should be fairly clear (I hope!). The only real change from 
the above logic is that installed packages (including their original USE 
flags and *DEPENDs) are also taken into account.

Regards,
Jason Stubbs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQCVAwUBQKW1P1oikN4/5jfsAQLrNgQArwpCmI3DQUHcLhDygRmX7WSl7d55KcQb
jo/F6f+lROsQHYz6xFhktiUpvP8j6QalRDtF0c5zpdnUaSGzUZPBqd2Oqh1bjl78
tQbC5IbEw2myFLDNu1/DauSr//IsReFI86wDapjpGOkk6vmqE9LrZZW9TLCgA9UY
dvdy3eWMj6c=
=o4F2
-----END PGP SIGNATURE-----

--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Andrew Gaffney]

Jason Stubbs wrote:
> On Saturday 15 May 2004 13:12, Andrew Gaffney wrote:
> 
>>>Jason Stubbs wrote:
>>>
>>>>On Wednesday 12 May 2004 12:02, Andrew Gaffney wrote:
>>>>
>>>>>>I am writing a Perl program that does the same thing as 'emerge'. Yes, I
>>>>>>started a thread about this on -dev about 6 months back, but I'm better
>>>>>>prepared to do this now. I've already written functions that:
>>>>>>
>>>>>>  * Build a list of USE flags from /etc/make.profile/make.defaults,
>>>>>>/etc/make.conf, and $ENV{USE}
>>>>>>  * Build a list of masked packages from
>>>>>>/etc/make.profile/package.(un)mask and /etc/portage/package.(un)mask
>>>>>>  * Build a list of matching ebuild versions from a
>>>>>>'>category/package-version' type string taking masked packages into
>>>>>>account * Extract the DEPEND line from a particular ebuild
>>>>>>  * Parse a DEPEND line using active USE flags and build a list of
>>>>>>needed packages
>>>>>>
>>>>>>I'm starting work on the code that generates the actual dependency tree
>>>>>>and then the list of packages to be installed. I don't have any Python
>>>>>>skill, so I don't think that reading the code will help me much. Can
>>>>>>anyone who deals with the Portage code a lot give me a general
>>>>>>breakdown of the way that 'emerge' generates the dependency tree and
>>>>>>then the list of packages to emerge?
>>>>
>>>>As of .51:
>>>>
>>>>Initial startup:
>>>>* Read configuration files
>>>>* Scan system for installed packages and auto-enable use flags and
>>>>virtuals * Create master configuration
>>>>
>>>>Dep calculation:
>>>>* Is blocker? No? Continue...
>>>>  * Is a matching package installed? No? Continue...
>>>>    * Make record of blocked package and continue...
>>>>* Resolve atom to package
>>>>* Has package's already been added? Yes? Continue...
>>>>* Add package and note its parent
>>>>* Copy master configuration
>>>>* Is binary package? Adjust USE flags from build-time.
>>>>* Is source package? Adjust USE flags from package.use
>>>>* Parse DEPEND and RDEPEND and resolve against USE flags
>>>>  -- deps in "|| ( foo bar )" deps get preference by being installed
>>>>* Calculate deps for each atom parsed, with parent as this package
>>>>* Parse PDEPEND and resolve against USE flags
>>>>* Calculate deps for each atom parsed, with no parent
>>>>
>>>>Order resolution:
>>>>* Find first added package that has no parents
>>>>* Add package to order and remove from tree
>>>>* Continue...
>>>>
>>>>There are a number of problems in this logic, some of which you and
>>>>Pieter have noticed. The ones you have mentioned, I've fixed in a
>>>>complete rewrite. To fix the main flaws (package only gets the parent
>>>>from when it is first added, and PDEPENDs having no parents) is next on
>>>>the agenda but is quite difficult.
>>>
>>>You've already done a complete rewrite of the dependency resolver?
> 
> 
> Yes and no. I started from scratch but used almost exactly the same logic. I 
> guess you could almost call it refactoring. Have a look at:
> http://www.gentoo.org/cgi-bin/viewcvs.cgi/portage-mod/portageapi/?root=gentoo-src
> 
> Of interest to you, will probably be dep.py. Even if you do not understand 
> python, the logic should be fairly clear (I hope!). The only real change from 
> the above logic is that installed packages (including their original USE 
> flags and *DEPENDs) are also taken into account.

I'll have to take a look at it. If anyone wants to take a look at my code (and 
maybe give me a few suggestions), the (almost) latest working version can be 
accessed at <http://locutus.homeip.net/dev/portage.pl>. It currently operates 
the same way 'emerge -ep' would. It doesn't generate the exact same packages to 
install as Portage, but it is pretty damn close.

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Jason Stubbs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 15 May 2004 15:50, Andrew Gaffney wrote:
> Jason Stubbs wrote:
> > On Saturday 15 May 2004 13:12, Andrew Gaffney wrote:
> >>>You've already done a complete rewrite of the dependency resolver?
> >
> > Yes and no. I started from scratch but used almost exactly the same
> > logic. I guess you could almost call it refactoring. Have a look at:
> > http://www.gentoo.org/cgi-bin/viewcvs.cgi/portage-mod/portageapi/?root=ge
> >ntoo-src
> >
> > Of interest to you, will probably be dep.py. Even if you do not
> > understand python, the logic should be fairly clear (I hope!). The only
> > real change from the above logic is that installed packages (including
> > their original USE flags and *DEPENDs) are also taken into account.
>
> I'll have to take a look at it. If anyone wants to take a look at my code
> (and maybe give me a few suggestions), the (almost) latest working version
> can be accessed at <http://locutus.homeip.net/dev/portage.pl>. It currently
> operates the same way 'emerge -ep' would. It doesn't generate the exact
> same packages to install as Portage, but it is pretty damn close.

May I ask what you are writing this for? Once the API I'm working on is 
completed, tested and integrated (<2 months?) I'll start working on wrappers 
for other languages. Is that the sort of thing you are after?

Regards,
Jason Stubbs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iQCVAwUBQKXBfFoikN4/5jfsAQKMLwP8DS8XempV3Sz8AN9+q0tT0HqjFC76BxHN
7xRcAwu0y3KkM1Bf1f7Ezs/chzzqJtNcDcWUVECtiMbMa3F2MWPyB7cn034eCxDt
02H2WruxweT6NHFdSCRhEqbBmrmvBW9Hvfdzii9JMzruEA6C/V8b0peHv0B3Fauy
nQTzlecx9Mg=
=e/X+
-----END PGP SIGNATURE-----

--
gentoo-portage-dev@gentoo.org mailing list

Re: [gentoo-portage-dev] building dependency tree

[Andrew Gaffney]

Jason Stubbs wrote:
> On Saturday 15 May 2004 15:50, Andrew Gaffney wrote:
> 
>>>Jason Stubbs wrote:
>>>
>>>>On Saturday 15 May 2004 13:12, Andrew Gaffney wrote:
>>>>
>>>>>>You've already done a complete rewrite of the dependency resolver?
>>>>
>>>>Yes and no. I started from scratch but used almost exactly the same
>>>>logic. I guess you could almost call it refactoring. Have a look at:
>>>>http://www.gentoo.org/cgi-bin/viewcvs.cgi/portage-mod/portageapi/?root=ge
>>>>ntoo-src
>>>>
>>>>Of interest to you, will probably be dep.py. Even if you do not
>>>>understand python, the logic should be fairly clear (I hope!). The only
>>>>real change from the above logic is that installed packages (including
>>>>their original USE flags and *DEPENDs) are also taken into account.
>>>
>>>I'll have to take a look at it. If anyone wants to take a look at my code
>>>(and maybe give me a few suggestions), the (almost) latest working version
>>>can be accessed at <http://locutus.homeip.net/dev/portage.pl>. It currently
>>>operates the same way 'emerge -ep' would. It doesn't generate the exact
>>>same packages to install as Portage, but it is pretty damn close.
> 
> May I ask what you are writing this for? Once the API I'm working on is 
> completed, tested and integrated (<2 months?) I'll start working on wrappers 
> for other languages. Is that the sort of thing you are after?

I'm not quite sure why I'm doing it. Partly, I wanted to see if I could write a 
program that is faster than Portage. I also like to really understand how things 
work "under the hood". Writing a Perl program that functions like Portage's has 
really helped me do this.

-- 
Andrew Gaffney
Network Administrator
Skyline Aeronautics, LLC.
636-357-1548


--
gentoo-portage-dev@gentoo.org mailing list