Several people (including myself) have complained about pkg_chk's rather
  poor handling of complex dependency graphs, that in practice results in
  packages bieng repeatedly rebuilt during an update.

  I spent the afternoon trying to hack pkg_chk to tsort the update/install
  list. The result looks so ugly, I don't even want to use it myself. 

I have thought about tsort as well.

I have had a notion (but not enough time to code it) of keeping track
of 'unsafe make replace' operations, or more precisely those packages
which are in an unsafe state.  With that, and a way to do subsequent
replaces of packages in an unsafe state, an entire update operation
could be done with make replace, with a safe endpoint.

Define a package to have a safe state when it is originally built.  By
safe, I mean that one knows that the bits it depends on match the
build-time bits.

When one does 'make replace', mark any package that depends on the
package being replaced as 'unsafe'.  This should not be recursive.

An update procedure would then

1. Find all packages that need updating, and mark them as 'needs
   update'
  
2. Take the union of all 'needs update' and 'unsafe' packages, and
   tsort them.  (Or, have a tsort of all packages, using Frederick's
   code, and find the earliest of the union set in the list.)

3. Do 'make replace' on the head of the list.

4. Goto 2.  (It is likely that a package will be newly marked 'unsafe'.)


This has the advantages that each package should only be rebuilt once,
and that except for packages that are both unsafe and broken (many
'unsafe' upgrades are of course really ok) the system is pretty usable
throughout.

A further enhancement would be to add enough information so that some
replace operations could safely decline to mark depending packages
unsafe.  For example, a bugfix release of a library with the same
major/minor numbers and the same PLIST is pretty clearly safe (absent
incorrect changes by the library maintainer).

I hope my rambling is useful.

-- 
        Greg Troxel <gdt@ir.bbn.com>