BUG: apt dpkg failures on heavy installs: tsort(1) uses discussion

["John D. Hendrickson and Sara Darnell" <johnandsara2@cox.net>]

Hi, I'm not a maintainer.

I'm hoping someone will discuss this.  Very much hoping a maintainer of apt or dpkg will discuss / 
question validity that ordering of pkgs by dependency (right before preinst) may not be done as 
first though, may help, and is non intrusive to any policy or expectation.

I'm saying: a list off all packages sorted in dependency order will allow dpkg more stability but is 
unused (explained below).

I'm NOT saying dpkg doesn't check dependency nor that it can't make a list of all deps if it were 
used that way.  I'm talking about the results of doing so, how to best use it; why it would make 
dpkg run more successfully and maybe far faster in the worst situations (ex, upgrade time, changing 
from kde to gnome and back, etc).

ex of deterioration of process: during "apt upgrade", which will ends up needing to be restarted 
after some error, BEFORE essentials are installed: I end up with 500 pkgs in dpkg install list and 
unpacking (NOT what "upgrade" orig. asked), gnome fluff are listed before essentials in the list 
dpkg puts on stdout, it will fail on many things, apt-get won't restart until I fix it.  And it's 
slow slow - took days on a pentium machine (all said and done) to install not much more than base 
(no desktop on that machine).

========== why does it do that ? ===========

guess:
	(a) apt is letting in new pkg in list only by virtue of "half-configured"
	(b) nothing is ordering pkgs in dependency order at any time
	    that is: with the extended list they are tried in polish notation order ?
	    (ordering between pkgs that don't depend on each other incl.)
	    (can be night and day as to which may cause upgrade problems)

I. yes, apt "checks dependency per ea. then orders pkg list by grading".

	(1) I see nothing in apt or dpkg source
            that orders ea. non-dep against each other

	    apt's method is excellent for making alternate lists it presents
       	    (all poss deps list combos would be time expensive and listy)

		yes, if pkg A deps B, it orders B A
		!! though not after half-config errors !!
		BUT if dep A is met, dep B is met: orderless
		thing is: during upgrade they could be night & day diff.

	(2) I worry recursively checking a package's depends "current only"
	    may not always reveal all depends or mistake them.  HOW?

	    (a) CERTAINLY it's not all possible runtime deps over dpkg "runs".
	    An OR limits deps. but after errors you might get both
	    sides on your system that try to configure.  Also meaning
	    deps already accepted for pkg A earlier become wrong later
	    when pkg B take the other side of an OR.  "anything in limbo?"

	    (b) a single pkg's deps list, recursively trace, may not lead to
		a list of all deps if there is any short Depends anywhere traced
		(where as a total list by tsort(1) would do better not perfect)

========== HOW ? preliminary work toward SIMPLE aid ===========

HOW?  I think an additional check that orders which preinst dpkgs tries first will help.  It 
shouldn't effect anything but it should make progress faster and success more frequent.  It won't 
effect triggers either.

(1) A "super list" of all packages sorted by dependency.  tsort(1) seems to work.

	1) fast sanity check, check order of any sublist against super list is easy
	2) it's important to know making the list takes longer than most will want to wait
	   (making it per run should be avoided)

(1a) tsort can be helpful in other ways (ie, include status in the fray, arch too, and 
cross-calculations), though I don't have that prepared to show / not an issue / preliminary

I have a working example of what to do that and already posted it.  Note it's preliminary - just to 
show what the big list looks like - it's not meant to include every feature wished.

Anyhow just trying to help :)


Thanks,

	john hendrickson

P.S.
	(from my guess of one cause of deteriorating process above)

	I also suggest dpkg not unpack nor pre-inst dependants of a half-configure, especially
	not during upgrade, unless user DOUBLE --forces it :)

	I suggest apt not notate half-installs as able to add dependants (when making dpkg list).
	not even for --configure --pending (they aren't deps if they parent does not exist, period,
	and proof of that is packages that error out on parents yet with missing files)

	It may be thought this is already true but I think there are loopholes yet, here or there.