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

Tue Jun 22 09:24:41 PDT 2010

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.

The thing about it is, once the order of executing the static constructors is decided, it will never change.  So potentially, we can determine order of static constructor/destructor execution at the beginning of the runtime startup, and then simply run through the order when creating/destroying a thread.

I'm not exactly convinced that we can't find some quicker way, but so far, I'm not finding it.  The problem is for "forwarding modules", or modules that contain no constructors, but have dependencies on other modules that do.  The example I gave is probably a minimal example of the problem.  The current runtime short-circuits itself by not running any dependencies of such modules more than once.  But this leads to not detecting cycles where the forwarding modules are used more than once.

Whatever the cycle detection algorithm, I'm *absolutely* convinced the running of the constructors/destructors themselves should be separate from the cycle detection.  We shouldn't be detecting cycles on every thread start in an unchanging graph.

-Steve

----- Original Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Tue, June 22, 2010 9:57:41 AM
> Subject: Re: [phobos] Proposed feature: print cycle when a module cyclic dependency is detected
> 
> OK, I found a bug in the cycle detection.

For some reason, the module 
> cycle detection has a weird rule where if a module has no static ctors/dtors, it 
> skips cycle detection on its immediate dependencies.  Here is a test case 
> where the cycle detection fails, and the results:

mod1.d:

public 
> import mod2;
public import mod3;
private import std.stdio;

void 
> main()
{
   writefln("x = %d, y = %d", x, 
> y);
}

mod2.d:
import mod1;

__gshared int x;

static 
> this()
{
   version(xfirst)
      x = 1;

> else
      x = y;
}

mod3.d:
import 
> mod1;

__gshared int y;

static this()
{

> version(xfirst)
      y = x;
   else

>   y = 1;
}

the results:
[steves at steveslaptop testmodules]$ dmd 
> -version=xfirst mod1.d mod2.d mod3.d -ofxfirst
[steves at steveslaptop 
> testmodules]$ dmd mod1.d mod2.d mod3.d -ofyfirst
[steves at steveslaptop 
> testmodules]$ ./xfirst
x = 1, y = 1
[steves at steveslaptop testmodules]$ 
> ./yfirst
x = 0, y = 1

And yes, I did apply Don's fix to the module 
> constructor.  What I'm trying to understand is the logic behind the "skip" 
> flag that implements this "feature".  There seems to be no explanation for 
> it.

Also, while I have your attention on this, what triggers the compiler 
> to set the MIstandalone flag?

I don't mind fixing these problems, but I 
> want to understand the logic behind it first.

-Steve

----- 
> Original Message ----
> From: Steve Schveighoffer <
> ymailto="mailto:schveiguy at yahoo.com" 
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com>
> To: 
> Discuss the phobos library for D <
> href="mailto:phobos at puremagic.com">phobos at puremagic.com>
> Sent: 
> Tue, June 22, 2010 9:24:54 AM
> Subject: Re: [phobos] Proposed feature: 
> print cycle when a module cyclic dependency is detected
> 
> I just 
> realized that this patch isn't good enough (it does not print modules 
> 
> which have no constructors/destructors but which import other modules), I'm 
> 
> working on a better one.

But it's definitely possible.  So 
> assume I 
> will have a patch shortly, does the concept seem 
> 
> worthy?

-Steve

----- Original Message ----
> From: 
> 
> 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>
> To: Phobos 
> 
> <
> href="mailto:
> 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>
> Sent: 
> 
> Tue, June 22, 2010 8:59:23 AM
> Subject: [phobos] Proposed 
> feature: print 
> cycle when a module cyclic dependency is 
> detected
> 
> Hi 
> all,

Recently, I had an issue when 
> developing std.process.  I 
> 
> inadvertently caused a cyclic 
> dependency in modules.  However, the 
> error 
> was not enough 
> to find the problem:

object.Exception: 
> Cyclic dependency 
> 
> in module std.stdio

The problem is, this is 
> the *end* 
> of the cycle, not 
> the source.  I actually hadn't changed 
> 
> the imports of std.stdio.

So 
> I improved the module constructor 
> 
> function to automatically print all modules 
> involved in the 
> cycle, in 
> the order they were imported.  Attached is the 
> 
> patch.  The 
> function should not adversely affect the runtime in 
> normal 
> operation, 
> since the changes I made only occur when a 
> terminating exception is 
> 
> about to be thrown anyways.  Do 
> people agree this is a worthy improvement 
> 
> to the 
> runtime?  Anyone see any issues with the patch? If everyone 
> likes, 
> 
> I'll commit.

-Steve

> 
> 
_______________________________________________
phobos mailing 
> list

> ymailto="mailto:
> href="mailto:phobos at puremagic.com">phobos at puremagic.com" 
> 
> href="mailto:
> 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
http://lists.puremagic.com/mailman/listinfo/phobos

>     
_______________________________________________
phobos 
> mailing list

> href="mailto:phobos at puremagic.com">phobos at puremagic.com

> href="http://lists.puremagic.com/mailman/listinfo/phobos" target=_blank 
> >http://lists.puremagic.com/mailman/listinfo/phobos