Suggestion for algorithm improvement

[Erik Søe Sørensen]

Hi all.

'lunar update' took so long time on my machine that I thought something 
looped.  I found that it was sort_by_dependency() that consumed much 
time, and my first thought (after having done some tracing) was that 
there was some cyclic dependencies.

I didn't find any of those, but I did find that the algorithm revisited 
parts of the dependency graph - some parts are revisited *many* times 
(perl, m4 and automake for instance) because of the simple depth-first 
traversal the function does.
The algorithm had exponential complexity.

By keeping track of what parts of the graph has already been visited, 
though, the complexity could be improved.

The following version does this (lines with '#NEW' are new):

# function : sort_by_dependency
# usage    : LIST=$(sort_by_dependency $LIST)
# purpose  : return a LIST sorted by dependency
sort_by_dependency() {
   debug_msg "sort_by_dependency ($@)"

   included="" #NEW

   recurse() {
     debug_msg "Recurse $*"
     for MOD in $* ; do
       if echo "$included" | grep -qFx "$MOD" ; then #NEW
         debug_msg "Cutoff: $MOD"                  #NEW
       else                                        #NEW
       LIST=$(grep ^$MOD: $DEPENDS_STATUS | grep ":on:" | cut -d: -f2)
       for DEP in $LIST ; do
         echo $MOD $DEP
       done
       included=$included$'\n'$MOD  #NEW
       recurse $LIST
     fi  #NEW
     done
   }

   ALL=$(recurse $* | tsort | tac)
   for DEP in $ALL ; do
     if echo " $* " | grep -q " $DEP " ; then
       echo $DEP
     fi
   done
}

Opinions?

/Erik