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

Tue Jun 22 10:52:43 PDT 2010

I don't think static constructors are required in .di files.  Without that bit of info, I don't think the cycle detection can be done until runtime.

I still hope that a cycle detection algorithm can be used that's quicker than O(n^3), hopefully something like O(n^2) as the current flawed algorithm is.

-Steve

----- Original Message ----
> From: Sean Kelly <sean at invisibleduck.org>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Tue, June 22, 2010 1:40:02 PM
> Subject: Re: [phobos] Proposed feature: print cycle when a module cyclic dependency is detected
> 
> Yeah, it makes sense to have the cycle detection only run on startup.  It 
> should probably be extracted from _moduleCtor2() and _moduleTlsCtor() and just 
> run as a unit before the ctors are called on program startup.  It would be 
> even better if cycle detection could be done by the compiler at build time, but 
> perhaps this is an instance where build speed should be favored over startup 
> speed.

On Jun 22, 2010, at 9: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.
> 
> 
> 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 <
> 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: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:
> ymailto="mailto:schveiguy at yahoo.com" 
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com" 
>> 
> href="mailto:
> 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: 
> 
>> 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>
>> 
> 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:
> ymailto="mailto:schveiguy at yahoo.com" 
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com" 
>> 
> href="mailto:
> 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">
>> 
> ymailto="mailto:
> href="mailto:schveiguy at yahoo.com">schveiguy at yahoo.com" 
>> 
> href="mailto:
> 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:
> 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">
>> 
> 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>
>> 
> 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:
> 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" 
>> 
> 
>> href="mailto:
>> 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">
>> 
> 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:
> 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
> 
>> 
> href="
> >http://lists.puremagic.com/mailman/listinfo/phobos" target=_blank 
> 
>>> 
> target=_blank >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

_______________________________________________
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