[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

dep-trace v. tsort (dpkg, source, bsd, reason)

Hi.  I'd like to make sure i mentioned this.  Bug yes, not needing fix today, a look ahead.

SUBJECT: lack of dependency sorting; untangling dependency in dpkg lists
OBJECT: http://www.sourceforge.net/projects/dep-trace  (see below)

Debian [easily] installs 850 pkgs at a time: each having dependencies. Dependencies are resolved to to build the list: BUT the order to install / configure is un-ordered. If the list were optionally dependency sorted (non-mandatory) success is more likely. $cat list | dep-trce # (sort it)

(If a stop occurs in the long process this can leave problems. Some postinst sh incorrectly assume order.)

What of source package builds?  see below, it does have some discrete usefulness.

Example. FreeBSD and Apple use tsort(1) during "portage" (checks 1st depends list, downloads all, check new lists. Then chain compiles). How is tsort(1) used? Tsort yeilds the order to compile in. When? Port A says it needs B and C compiled first. But B and C also have requirements not known until fetched ! A can't know, doesn't say. Thus tsort is used AFTER it downloads and has all sublists.

OOPS! topological sorting isn't right all the time. (i.e., "loop detected - bailing out ...", or "libxxx ... compiling ... failed ... lib yyy not yet installed") (what a pain!) Why? tsort does vector graphics ordering (arrows pointing to objectives, see wikipedia) and compilers simply can't do that. Compilation does requires order.

/bin/dep-trace is a small speedy sorter, operates like sort(1), using regular math rules rather than "value added" ones. It has no dependencies itself. It may have other uses in ordering lists.

Thanks all, and I hope it's not a bother having this in debian-dpkg list once,


Further details...

#### misc note

make(1) orders compiling (dependency) yes, but make language and it's stat file checking isn't conducive to ports/pkg install as being done today (see below for more)

###  complicated ###  Debian builds ###

Source packages.  Build may fail, or possibly have side-effects, if compiled in the wrong order.

And there are THREE plausible for using sorted depends lists.

Weakest first: (please correct if I'm wrong). Same as install of dpkg list: un-ordered. If dpkg gets a source pkg LIST it may try the LIST in the wrong order (it guesses you are building one .dsc per say).

A second circumstance is if Build-Depends: [list] If Build-Depends list within pkg X list is not well ordered (or aged) or not processed in same order. (or just plain mistakes)

The third: discrete circumstance. If build X says package A B C must be pre-built: but due to changes package B it must be built before A. (restating that: while dpkg-checkbuilddeps(1) may prevent B from being built, dpkg-buildpackage(1) won't double back to do A after B. Why? This is because package X doesn't know the dependency structure of A or B nor does it sort them - not until Build-Depends is edited manually - dot your t's cross your eyes, is ordered thus FIXED :)

(comparison, remembering BSD/apple above - if you [use an ability] to chain download and compile like bsd ports (pre-fetched or not) do you can't assume to know the depends of A and B (maybe upstream changed?) Developer may perfectly not care if attempting many ports if they build to begin with is a nice start right?)


dpkg-buildpackage acts like make(1) in that it checks for file existence, all or none (which is required and good). However, like make dbp isn't going to double back: you won't know what the right dep order is until it fails and you manually trace the A B C order somehow to find X doesn't know B comes before A.


dep-trace is not amazing as to upgrade of .dsc: but rethinking "the usual confusion involved" it does. Also if there is confusion caused by deps it can show why (if X's idea of dep lists in A and B is out of date).

Reply to: