OK, so I've built a correct cycle detection algorithm (see http://d.puremagic.com/issues/show_bug.cgi?id=4384), that runs in O(n^2) time, just like the current, and uses as little stack space as possible (on the order of O(n^2) but with a lot of heuristics).  It also prints out the cycle that was detected.

I would check it in, but it found a cycle in phobos.  Here is the printout (note that this isn't necessarly the smallest cycle, just a cycle):

Cyclic dependency in module std.encoding imported from std.string imported from std.dateparse imported from std.date imported from std.file imported from std.stdio imported from std.functional imported from std.range imported from std.exception imported from std.conv imported from std.array imported from std.algorithm imported from std.random * imported from std.range imported from std.exception imported from std.conv imported from std.array imported from std.algorithm imported from std.string imported from std.encoding * object.Exception: Aborting due to cycle between (*) elements with module ctors/dtors

So what this is saying, is std.encoding indirectly imports std.random, which indirectly imports std.encoding, and both of these modules contain shared module ctors.  I manually verified the cycle path, and that shared ctors exist, so it is a real cycle.

My problem now is, I want to commit this, but as soon as I do, it will break phobos.

So what to do?

Note that this is the first cycle detected from building make -f posix.mak unittest.  There may be more, I can post them all here if need be.

-Steve

I moved encoding to the last module, so all the others would test first, encoding appears to be the only cycle.

Anyone want to try and figure out how to fix it?

-Steve



----- Original Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>

> Note that this is the first cycle detected from building make -f  posix.mak unittest.  There may be more, I can post them all here if  need be.

Hm... I just realized, this doesn't jive correctly yet because random should also fail...

There definitely is a cycle though, that much is sure.

-Steve



----- Original Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Fri, November 5, 2010 11:13:24 AM
> Subject: Re: [phobos] improved module cycle detection algorithm finds existing
>cycle in phobos, what to do?
> 
> I moved encoding to the last module, so all the others would test first, encoding appears to be the only cycle.
> 
> Anyone want to try and figure  out how to fix it?
> 
> -Steve
> 
> 
> 
> ----- Original Message  ----
> > From: Steve Schveighoffer <schveiguy at yahoo.com>
> 
> > Note  that this is the first cycle detected from building make -f  posix.mak

> > unittest.  There may be more, I can post them all here if   need be.
> 
> 
> 
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
> 

Well, I don't think my algorithm's broken, I think the compiler is doing something strange.

When building the unit test for std.encoding, the module std.encoding is listed as having shared ctors/dtors, and is not marked as standalone.

When building the unit test for std.random, the module std.encoding is listed as *not* having shared ctors/dtors.  However, there are 6 modules named like:

encoding.64
encoding.65
encoding.66
encoding.67
encoding.68
encoding.69

Which are all marked as having shared ctors/dtors, *but* also marked as standalone.

Why is the compiler doing something different if you are compiling unit tests for a given module?  And to me, it looks like the module should have non-standalone ctors/dtors (it has 6 classes which have a shared static this).

Any clues?

-Steve

When encountering a similar problem I defined stdiobase.d to break the dependency cycle.

This is great work. I'd love to see the cycle shown even clearer.


Andrei

On 11/5/10 10:15 AM, Steve Schveighoffer wrote:
> Hm... I just realized, this doesn't jive correctly yet because random should also fail...
>
> There definitely is a cycle though, that much is sure.
>
> -Steve
>
>
>
> ----- Original Message ----
>> From: Steve Schveighoffer<schveiguy at yahoo.com>
>> To: Discuss the phobos library for D<phobos at puremagic.com>
>> Sent: Fri, November 5, 2010 11:13:24 AM
>> Subject: Re: [phobos] improved module cycle detection algorithm finds existing
>> cycle in phobos, what to do?
>>
>> I moved encoding to the last module, so all the others would test first, encoding appears to be the only cycle.
>>
>> Anyone want to try and figure  out how to fix it?
>>
>> -Steve
>>
>>
>>
>> ----- Original Message  ----
>>> From: Steve Schveighoffer<schveiguy at yahoo.com>
>>
>>> Note  that this is the first cycle detected from building make -f  posix.mak
>
>>> unittest.  There may be more, I can post them all here if   need be.
>>
>>
>>
>> _______________________________________________
>> 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

I don't know enough about std.random and std.encoding to know what to do with them.  Does anyone own these?

I think the cycle as I print it is pretty clear.  What do you find unclear about it?

-Steve



----- Original Message ----
> From: Andrei Alexandrescu <andrei at erdani.com>
>
> When encountering a similar problem I defined stdiobase.d to break the dependency cycle.
> 
> This is great work. I'd love to see the cycle shown  even clearer.
> 
> 
> Andrei

On 11/5/10 11:21 AM, Steve Schveighoffer wrote:
> I don't know enough about std.random and std.encoding to know what to do with them.  Does anyone own these?

Janice wrote std.encoding and I wrote (most of) std.random. Anyway, both are now "Phobos owned" :o).

> I think the cycle as I print it is pretty clear.  What do you find unclear about it?

Well I didn't look into this closely but essentially there was this list:

Cyclic dependency in module std.encoding
imported from std.string
imported from std.dateparse
imported from std.date
imported from std.file
imported from std.stdio
imported from std.functional
imported from std.range
imported from std.exception
imported from std.conv
imported from std.array
imported from std.algorithm
imported from std.random *
imported from std.range
imported from std.exception
imported from std.conv
imported from std.array
imported from std.algorithm
imported from std.string
imported from std.encoding *
object.Exception: Aborting due to cycle between (*) elements with module
ctors/dtors

It didn't immediately give away where the problem is and what steps need to be taken to fix it. Probably that's why you were compelled to add a natural language translation:

> So what this is saying, is std.encoding indirectly imports std.random, which indirectly imports std.encoding, and both of these modules contain shared module ctors.  I manually verified the cycle path, and that shared ctors exist, so it is a real cycle.

I also find the passive tense backwards. So I guess I'd format the message as follows:

=============
Cyclic dependency: std.encoding imports std.random and vice versa, and
both define module constructors. Details ("<-" means "imports"):

std.encoding <- std.string <- std.algorithm <- ... <- std.random std.random <- std.algorithm <- ... <- std.encoding =============

Long chains can be improved by e.g. reformatting to one import per line:

std.encoding <- std.string
              <- std.algorithm
              <- ...
              <- std.random
std.random <- std.algorithm
            <- ...
            <- std.encoding

Just a thought.

One way to break a dependency chain is by defining a module that both std.encoding and std.random include.

Anyway, currently the static ctor in std.random is:

shared static this()
{
     ulong s;

     version(Win32)
     {
         QueryPerformanceCounter(&s);
     }
     version(Posix)
     {
         // time.h
         // sys/time.h

         timeval tv;
         if (gettimeofday(&tv, null))
         {   // Some error happened - try time() instead
             s = core.sys.posix.sys.time.time(null);
         }
         else
         {
             s = cast(ulong)((cast(long)tv.tv_sec << 32) + tv.tv_usec);
         }
     }
     //rand_seed(cast(uint) s, cast(uint)(s >> 32));
}

As the last line is already commented out _and_ rand_seed is deprecated anyway, you may want to simply remove the constructor!

Andrei

OK, it has something to do with the fact that a module is compiled with -lib, and with putting the shared constructor in a class.

I'll file a bug report on it.

Note, there still is a cycle, but because of the bug, the compiler isn't correctly identifying dependencies.  So we still need to fix std.encoding/std.random.

-Steve



----- Original Message ----
> From: Steve Schveighoffer <schveiguy at yahoo.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Fri, November 5, 2010 12:02:59 PM
> Subject: Re: [phobos] improved module cycle detection algorithm finds existing
>cycle in phobos, what to do?
> 
> Well, I don't think my algorithm's broken, I think the compiler is doing something strange.
> 
> When building the unit test for std.encoding, the  module std.encoding is
>listed
>
> as having shared ctors/dtors, and is not  marked as standalone.
> 
> When building the unit test for std.random, the  module std.encoding is listed
>as
>
> *not* having shared ctors/dtors.   However, there are 6 modules named  like:
> 
> encoding.64
> encoding.65
> encoding.66
> encoding.67
> encoding.68
> encoding.69
> 
> Which  are all marked as having shared ctors/dtors, *but* also marked as standalone.
> 
> Why is the compiler doing something different if you are  compiling unit tests

> for a given module?  And to me, it looks like the  module should have non-standalone ctors/dtors (it has 6 classes which have a  shared static
this).
> 
> Any clues?
> 
> -Steve
> 
> 
> 
> 
> _______________________________________________
> phobos  mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
> 

Le 2010-11-05 ? 12:03, Andrei Alexandrescu a ?crit :

> When encountering a similar problem I defined stdiobase.d to break the dependency cycle.

But then, don't you lose the assurance that stdio's static variables will be initialized before another module that depends on std.stdio is initialized? What guaranties that std.stdiobase will be initialized before my own module? Perhaps I should import std.stdiobase.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

No, the issue is, stdiobase only imports what it needs to do the static constructor.  stdio may import other things that have nothing to do with the static ctor, but may inadvertently make a cycle.

The theory goes, if there is no true dependency cycle (i.e. two independent ctors that depend on eachother to run), then you should be able to split the static ctor into its own module.

-Steve



----- Original Message ----
> From: Michel Fortin <michel.fortin at michelf.com>
> 
> Le 2010-11-05 ? 12:03, Andrei Alexandrescu a ?crit :
> 
> > When  encountering a similar problem I defined stdiobase.d to break the
>dependency  cycle.
> 
> But then, don't you lose the assurance that stdio's static  variables will be
>initialized before another module that depends on std.stdio is  initialized? What guaranties that std.stdiobase will be initialized before my  own module? Perhaps I should import std.stdiobase.
>