Sorry, this got sent just to Andrei -Steve
----- Forwarded Message ---- > From: Steve Schveighoffer <[email protected]> > To: Andrei Alexandrescu <[email protected]> > 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:[email protected]";>[email protected]> > To: Discuss > the phobos library for D < > href="mailto:[email protected]";>[email protected]> > Cc: > Steve Schveighoffer < > href="mailto:[email protected]";>[email protected]> > 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 [email protected] http://lists.puremagic.com/mailman/listinfo/phobos
