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




-------------- next part --------------
A non-text attachment was scrubbed...
Name: printcycles.patch
Type: application/octet-stream
Size: 1825 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100622/5997eb8d/attachment.obj>

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 <schveiguy at yahoo.com>
> To: Phobos <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

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 <schveiguy at yahoo.com>
> To: Discuss the phobos library for D <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:schveiguy at yahoo.com">schveiguy at yahoo.com>
> To: Phobos
> <
> 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:phobos at puremagic.com" href="mailto:phobos at puremagic.com">phobos at puremagic.com
http://lists.puremagic.com/mailman/listinfo/phobos

Definitely. I find that error message frustrating as well.

Sent from my iPhone

On Jun 22, 2010, at 6:24 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:

> 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 <schveiguy at yahoo.com>
>> To: Phobos <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
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

Yes please, I've been to hell and back figuring out the mutual dependency that ultimately led to std.stdiobase.

Andrei

On 06/22/2010 09:03 AM, Sean Kelly wrote:
> Definitely. I find that error message frustrating as well.
>
> Sent from my iPhone
>
> On Jun 22, 2010, at 6:24 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:
>
>> 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 <schveiguy at yahoo.com>
>>> To: Phobos <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
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

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

For those who are interested, it was nothing that I did.  I updated the branch from trunk and somehow the new import paths caused a problem.  Although I can't say that the original branch worked, because I never got it to compile on Windows.

Lars had put a new static this() function inside process.d that really belongs in std.stdio, except that bug 3979 prevents it from working.

So I'm sorta stuck now...

*sigh*

-Steve



----- Original Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>
> To: Phobos <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

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 <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
> 
> 
> 
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

Yeah, bug 3979 is really getting on my nerves.  Again, I suggest you work around it by doing the std.process development outside of Phobos, and then we can work on incorporating it in Phobos again when it's done (and when 3979 is fixed).

When I work on it, I do so in my own lib (as ltk.process).  Then it
works fine.

-Lars



On Tue, 2010-06-22 at 10:35 -0700, Steve Schveighoffer wrote:
> For those who are interested, it was nothing that I did.  I updated the branch from trunk and somehow the new import paths caused a problem.  Although I can't say that the original branch worked, because I never got it to compile on Windows.
> 
> Lars had put a new static this() function inside process.d that really belongs in std.stdio, except that bug 3979 prevents it from working.
> 
> So I'm sorta stuck now...
> 
> *sigh*
> 
> -Steve
> 
> 
> 
> ----- Original Message ----
> > From: Steve Schveighoffer <schveiguy at yahoo.com>
> > To: Phobos <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
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

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