Date: Sun, 20 Apr 2003 18:05:24 -0700 From: Kris Kennaway <kris@obsecurity.org> To: Maxim Sobolev <sobomax@portaone.com> Cc: Kris Kennaway <kris@obsecurity.org> Subject: Re: [kris@freebsd.org: cvs commit: ports/Mk bsd.port.mk] Message-ID: <20030421010524.GA79899@rot13.obsecurity.org> In-Reply-To: <20030420235156.GA47321@vega.vega.com> References: <000b01c3074d$d189c890$0a2da8c0@sem> <20030420215832.GC78660@rot13.obsecurity.org> <20030420235156.GA47321@vega.vega.com>
next in thread | previous in thread | raw e-mail | index | archive | help
--FCuugMFkClbJLl1L
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Mon, Apr 21, 2003 at 02:51:56AM +0300, Maxim Sobolev wrote:
> > I gave it a try, but the recursive-upgrade target is not so easy. I
> > wrote a modified ALL-DEPENDS-LIST that recurses into children and
> > sorts their dependencies in topological order, but it is very slow
> > (~10 minutes for gnome2).
>=20
> Maybe I am missing something, but what's wrong with make package-depends
> target? It does this in a reasonable time even for packages with very long
> dependency lists.
You implicitly answered that in your next sentence.
> I think that it should be fairly easy to make it
> printing not only raw list, but to sort it in a dependency order
This is the part that makes it take longer. ALL-DEPENDS-LIST doesn't
recurse into children it has already seen, because we only care about
the list of dependencies and not the relationship between them. But
in order to get the topological order (required for upgrading packages
in the right order), you need to recurse into the child for every
package that references it, otherwise you miss linkages in the graph
and you don't get the right sorting order.
e.g.
A
/|\
|B C
|| \
|| D
\E--/
|=20
F=20
ALL-DEPENDS would visit in the order
A__
|\ \
E B C
| |
F D
This of course misses the essential structure of the graph.
TOP-DEPENDS cannot do this because it needs to traverse every link on
the graph. So it could do
A__
|\ \=20
E B C
| | |
F E D
| |
F E
|
F
Of course, this traverses some links multiple times, but it's more
difficult to optimize it in a recursion-based approach (how
ALL-DEPENDS currently works) because one branch of the recursion needs
to know if another branch has already seen this node, and this
non-local information is simply not present. This extra recursion is
what kills complex packages like gnome.
> by
> propagating some number into the recursion process, which will be
> printed along with the name of dependency and will be increased on each
> recursion level. Then you will be able to tell that packages with
> the same numbers doesn't depend on each other, wile those with greater
> numbers are dependencies for those with smaller ones - see the graph
> below:
I'm not sure this is going to help avoid the extra recursion, but
maybe I just haven't thought about it enough. You're very welcome to
try.
> > Instead the way to do this would be to
> > parse the dependencies listed in INDEX, which is what portupgrade does
> > (like portupgrade, this would assume you have an up-to-date INDEX).
>=20
> I think you are mistaken here. portupgrade uses INDEX only in the
> case when it has trouble finding root of the installed package using
> ORIGIN feature. Past experience suggests that INDEX is very poor source
> of dependency information due to its stale-most-of-the-time nature.
OK, I've not read the source code, so I may be missing something.
> Hm, execuse me my sarcasm, but do we really need the second portupgrade
> in C???
Well, what are the other possibilities for a base system tool? I can
easily imagine that a shell script implementation would quickly become
a nightmare, because sh is a very poor language for structured or
modular programming.
Kris
--FCuugMFkClbJLl1L
Content-Type: application/pgp-signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (FreeBSD)
iD8DBQE+o0PUWry0BWjoQKURAl4vAJ9p0NEJcX7J00ThQlKlFzgmlWAhLwCg8De4
oU6KH1ma6/4RZkkJAOLA6AY=
=sOZU
-----END PGP SIGNATURE-----
--FCuugMFkClbJLl1L--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030421010524.GA79899>