Package ordering update: Handling Pre-dependencies

[Manoj Srivastava <srivasta@datasync.com>]

Hi guys,

        Andy Mortimer pointed out to me that merely ordering the
 packages is not quite good enough when pre-dependencies are involved,
 since the pre-depended upon packages have to be installed and
 configured before the dependent package can be installed. He
 suggested splitting into equivalence classes by pre-dependency, and
 then ordering within each class on the dependecies, but this may be
 hairy in practice. The following example explains the problem (and
 the current solution proposed).

 Suppose we have new packages A, B, C, D, E, F, G, H and X . 
                 C     Depends on A
                 D     Depends on B
                 E Pre-Depends on C
                 F Pre-Depends on D
                 G     Depends on E
                 H     Depends on F

        There maybe other dependencies, but they are not relevant to
 this discussion. Suppose the pkg order system orders them so:
             A B C D X E F G H. 
 However, E will not install unless C is installed and configured, and
 similarily F will cause an error until D is installed and
 configured. 

        Initially I proposed a method which involved post-processing
 the list produced by the topograhical sort algorithms (which are not
 influenced by the *kind* of dependency). 

        If we could mark all new packages that are pre-depended
 upon (C and D), then we could could post process the list and break
 it at the right places, which is easier than pre-splitting and having
 to worry about satisfying dependencies.

        This method *would* work in all cases, but, as Andy pointed
 out astutely, introduces an extra break, since it suggests 
             A B C <break> D <break> X E F G H.  
 number of passes = 1 + number of *new* packages that are predepended on. 

        I started implementing this, since correct behaviour is a
 minimal requirement (we could make it more efficient later). I
 generalized it, marking the *targets* of pre-dependencies,
 dependencies, conflicts, et al,  and append this information to the
 package list (this could make a nice report -- a reverse dependency
 listing). 

        *However*, I came up with the following this morning (while
 doing something quite different at work): Suppose we mark all
 packages which are targets as before, but we also store the dependent
 new packages (already implemented). Then, as we come across packages
 which are targets of the pre-dependency (C first, then D) we
 accumulate the dependents of these packages in a list (E and F). From
 this point on we watch all packages. The first time we come across
 these dependent packages (E), we insert a break, and clear out the
 dependants list. This gives the sequence: 
            A B C D X <break> E F G H

        Voila! One break, which is the minimal required. 
        ====== === ====== ===== == === ======= ========

        Another scenario: suppose the natural order were:
            A B C X E Y D Z F G H
 where X Y and Z are some random packages, then the first method
 gives:
            A B C <break> X E Y D <break> Z F G H 
 And the second method gives:
            A B C X <break> E Y D Z <break> F G H
 Both sets of sequences are correct.

        I have the underpinning (the marking and data gathering steps)
 in place, I still have to write the post processing routine (which is
 not a major undertaking). I think I'm about ready to move it out of
 experimental, and into unstable.

        Does anyone have any improvements to suggest?

                manoj

-- 
 Heisenberg might have been here.
Manoj Srivastava               <url:mailto:srivasta@acm.org>
Mobile, Alabama USA            <url:http://www.datasync.com/%7Esrivasta/>


--
TO UNSUBSCRIBE FROM THIS MAILING LIST: e-mail the word "unsubscribe" to
debian-devel-request@lists.debian.org . 
Trouble?  e-mail to templin@bucknell.edu .