[phobos] Proposed feature: print cycle when a module cyclic dependency is detected

[Andrei Alexandrescu]

On 06/22/2010 11:24 AM, Steve Schveighoffer wrote:
> Hm... this is turning out to be quite an interesting problem.
>
> I'm thinking a full cycle detection algorithm might be required, like
> Floyd-Warshall, but that's O(n^3), so it would be painful to run on
> the start of every thread.  100 modules == 1,000,000 iterations.

I agree with saving the result of the ordering!

Wouldn't a topological sort suffice for our needs?

For all modules with constructors:

1. Assign r=0 to all modules

2. Assign r=1 to modules that don't depend on other modules. If no such 
modules, fail.

3. For each child of parent modules, assign r+1 to its rank if it's 
zero. If it's not zero and is not r+1, cycle detected.

Then constructor execution will be in increasing order of rank. For 
modules of the same rank the order is not important.

I might be way off :o).


Andrei