Good morning,

I've studied the source code for tsort a bit and think I've found a flaw.
Basically, the way tsort works is as follows:

1) Construct a graph from the input data
2) Remove all nodes which no other nodes depend on.
3) If still any nodes left there is a cycle in the graph.  Remove a node
that's part of a cycle.  Goto 2.

Now, the flaw is in the find_cycle part of the program.  The current
algorithm tries to find the longest cycle that a node is part of.  This is
an NP-complete problem and with approx 50 nodes and more than 1000 edges in
the graph (as is the case for libgcc1.a) this *do* take some time.....  And
moreover, the result of this traversal is only used for printing out on
stderr which nodes are part of this cycle, not for determining what node to
remove from the cycle.  I therefore modified the cycle finding algorithm to
just detect a cycle, print it and then remove the node.  This made my
building of the libgcc1.a tractable. (The cycle detecting algorithm is now
O(#nodes*#edges) instead of exponential order.)

I have reports from other people using netbsd-current that this fix works.
As the subject says, it is a quick and dirty fix.  Feel free to improve it.

					-jarle

(This patch was also posted to current-users some hours ago)

================================================================
*** /usr/src/usr.bin/tsort/tsort.c	Wed Nov 17 15:25:40 1993
--- tsort.c	Wed Nov 24 17:30:32 1993
***************
*** 278,282 ****
  tsort()
  {
! 	register NODE *n, *next;
  	register int cnt;
  
--- 278,282 ----
  tsort()
  {
! 	register NODE *n, *m, *next;
  	register int cnt;
  
***************
*** 317,320 ****
--- 317,322 ----
  		for (n = graph; n; n = n->n_next)
  			if (!(n->n_flags & NF_ACYCLIC)) {
+ 				for (m=graph; m; m=m->n_next)
+ 					m->n_flags &= ~NF_MARK;
  				if (cnt = find_cycle(n, n, 0, 0)) {
  					register int i;
***************
*** 357,361 ****
  }
  
! /* look for the longest cycle from node from to node to. */
  find_cycle(from, to, longest_len, depth)
  	NODE *from, *to;
--- 359,363 ----
  }
  
! /* look for a path from node from to node to. */
  find_cycle(from, to, longest_len, depth)
  	NODE *from, *to;
***************
*** 384,392 ****
  		} else {
  			len = find_cycle(*np, to, longest_len, depth + 1);
! 			if (len > longest_len)
  				longest_len = len;
  		}
  	}
- 	from->n_flags &= ~NF_MARK;
  	return(longest_len);
  }
--- 386,395 ----
  		} else {
  			len = find_cycle(*np, to, longest_len, depth + 1);
! 			if (len > longest_len) {
  				longest_len = len;
+ 				break;
+ 			}
  		}
  	}
  	return(longest_len);
  }

================================================================

"Don't get suckered in by the comments -- they can be terribly
 misleading. Debug only code."
				-- Dave Storer

------------------------------------------------------------------------------