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

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

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