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

[Steve Schveighoffer]

FYI, I posted this bug so this issue isn't forgotten.  I assume the code is the same for D1 also:

http://d.puremagic.com/issues/show_bug.cgi?id=4384

-Steve



----- Original Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>
> To: Phobos <phobos at puremagic.com>
> Sent: Tue, June 22, 2010 4:47:10 PM
> Subject: [phobos] Fw: Proposed feature: print cycle when a module cyclic dependency is detected
> 
> Sorry, this got sent just to Andrei

-Steve



----- Forwarded 
> Message ----
> From: Steve Schveighoffer <
> ymailto="mailto:schveiguy at yahoo.com" 
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com>
> To: Andrei 
> Alexandrescu <
> href="mailto:andrei at erdani.com">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:
> ymailto="mailto:andrei at erdani.com" 
> href="mailto:andrei at erdani.com">andrei at erdani.com">
> ymailto="mailto:andrei at erdani.com" 
> href="mailto:andrei at erdani.com">andrei at erdani.com>
> To: Discuss 
> 
> the phobos library for D <
> href="mailto:
> ymailto="mailto:phobos at puremagic.com" 
> href="mailto:phobos at puremagic.com">phobos at puremagic.com">
> ymailto="mailto:phobos at puremagic.com" 
> href="mailto:phobos at puremagic.com">phobos at puremagic.com>
> Cc: 
> 
> Steve Schveighoffer <
> href="mailto:
> ymailto="mailto:schveiguy at yahoo.com" 
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com">
> ymailto="mailto:schveiguy at yahoo.com" 
> 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


      
> 
_______________________________________________
phobos mailing list

> ymailto="mailto:phobos at puremagic.com" 
> href="mailto:phobos at puremagic.com">phobos at puremagic.com
http://lists.puremagic.com/mailman/listinfo/phobos