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

[Steve Schveighoffer]

Sorry, this got sent just to Andrei

-Steve



----- Forwarded Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>
> To: Andrei Alexandrescu <andrei at erdani.com>
> Sent: Tue, June 22, 2010 3:25:46 PM
> Subject: Re: [phobos] Proposed feature: print cycle when a module cyclic dependency is detected
> 
> Yes, that would be great, but it's not so straightforward :)

The graph 
> *can* contain cycles, just not ones between modules that have static 
> ctors/dtors.  For example, this should be valid code:
--------------- 
> mod1.d:
import mod2;

static this()
{}

--------------- 
> mod2.d:
import mod3;

--------------- mod3.d:
import mod2; // valid 
> cycle!

static this()
{}

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

So we have to 
> almost prune the graph of these "ghost nodes" before doing the sort.  
> Essentially, mod2 should not play a role in the topo-sort, but it defines the 
> link between mod1 and mod3.

Can we do the pruning in-situ without 
> affecting the ModuleInfo tables and without allocation?  I don't 
> know.  Maybe there is a way...

I think now looking at it from this 
> perspective, I can see that Floyd-Warshall is not required, this should be an 
> O(V + E) algorithm.  At worst we need a temporary NxN table to run the node 
> removal algorithm.

-Steve



----- Original Message 
> ----
> From: Andrei Alexandrescu <
> href="mailto:andrei at erdani.com">andrei at erdani.com>
> To: Discuss 
> the phobos library for D <
> href="mailto:phobos at puremagic.com">phobos at puremagic.com>
> Cc: 
> Steve Schveighoffer <
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com>
> Sent: Tue, 
> June 22, 2010 2:38:15 PM
> Subject: Re: [phobos] Proposed feature: print 
> cycle when a module cyclic dependency is detected
> 
> 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