Re: Ordering

[Jason Gunthorpe <jgg@gpu.srv.ualberta.ca>]

Okay!

Just before I got your email I had started reworking how the ordering was
done to include your concept of less important orders. Here is how I have
drafted it,

There is a primary VisitNode that invokes upto 3 separate (changing)
dependancy consideration functions at different points relative to the
node add and to the other functions. The rountine looks like this

Visit Node
   Bail if looping, etc

   Consider for deletion
      Visit PRIMARY depends
      Visit PRIMARY Reverse depends
      Visit PRIMARY provide reverse depends (x2 for now and install)
      Visit REVDEP reverse depends
      Visit REVDEP provide reverse depends (x2 for now and install)
      Visit SECONDARY depends
      Visit SECONDARY reverse depends
      Visit SECONDARD provide reverse depends (x2 for now and install)
   Consider for node deletion
      Visit REMOVE reverse depends
      Visit REMOVE provide reverse depends
  
   Add this node
   Visit REVDEP depends

There are also 4 Dependancy functions to choose from,
  UnPack Critical - This implements the critical unpacking rules that
                    cannot be violated. It considers predepends and
                    depends only. When it encounters a predepends it
                    switches the primary to UnPack PreDepends.
  UnPack PreDepends - This also implements the cirtical unpacking rules
                      that Critical implements but considers all
                      dependancies as being critical as well. This has
                      the effect of being able to immediately configure
                      the node in ALL CASES.
  UnPack Depends - This implements the new breakage minimizing algorithm.
                   It is ment to be placed in the REVDEP location.
  Configure - This implements depends only configure ordering. When doing
              configuration ordering it is the only algorithm and is
              Primary, when doing unpacking ordering it is a secondary
              algorithm.
 
This is an almagamtion of all known ordering algorithms. We can get the
effect that pkg-order does by ordering unpacking using Cirtical as
Primary, Configure as secondardy and RevDeps disabled.

To get the full ordering Primary is set to Critical, Secondary to
Configure and RevDep to Unpack Depends. This causes decisions made by
RevDep to be more important than those made by Configure ordering. 

I will have to examine the present algorithms (all of these already exist)
and make sure they have the proper 'holes' (ie ignore things better
handled by later checks)

This seems to be a fairly close approximation of your last message and is
easy to implement. 

Critical Loops (those detected in UnPack Critical and UnPack PreDepends)
are handled by pre-processing the loop, logging it and then post
processing. We will recognize these 2 loops ONLY, all others result in a
fatal ordering error. 
   - Remove+conflicts+depends
   - Conflicts+Predepends
I would rather not handle the second one, but it looks like perl is not
going to change.

When post processing we consider each package, look at it's predepends for
unpacked but not configured packages (if so generate a 'break') then look
at it's reverse depends for an essential package (again, break if true)
and consider itself for being essential+immediate. [1]

This -ENTIRE- thing is prefixed with a scored sorting routine that
generates an order of removals, essential, predepends, others. This is to
help cause essential packages to be processed early.

I have details on how each of the 4 dependancy visit functions work, they
are what caused me alot of greif to get them right - they all have very
explicit purposes. Reverse Dependancies are handled differently BTW
(really 8 ordering functions)

Wow!

Jason

[1] Breaking could optionaly only configure the packages required to
continue - this would have the effect of generating a small number of
configures and then a large run of configuration at the end which is
desirable.