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 <[email protected]> > To: Phobos <[email protected]> > 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:[email protected]"; > href="mailto:[email protected]";>[email protected]> > To: Andrei > Alexandrescu < > href="mailto:[email protected]";>[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: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > To: Discuss > > the phobos library for D < > href="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]> > Cc: > > Steve Schveighoffer < > href="mailto: > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected]"> > ymailto="mailto:[email protected]"; > 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 > ymailto="mailto:[email protected]"; > href="mailto:[email protected]";>[email protected] http://lists.puremagic.com/mailman/listinfo/phobos _______________________________________________ phobos mailing list [email protected] http://lists.puremagic.com/mailman/listinfo/phobos
