[phobos] improved module cycle detection algorithm finds existing cycle in phobos, what to do?

[Steve Schveighoffer]

----- Original Message ----

> From: Andrei Alexandrescu <andrei at erdani.com>
> 
> On 11/5/10 11:21 AM, Steve Schveighoffer wrote:
> > 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.

Yeah, it's an interesting problem.  Because there are all these 
"non-participating" imports between the two modules with static ctors.  You need 
to show them and the order they go in, so you can see how the imports happen 
(otherwise, you are clueless as to which import is the problem), it makes the 
list really large, even though it's technically a 2-element 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
> =============

It's printed the way it is because I'm essentially unwinding the call stack, 
printing imports as I return from the depths of the search.  So it's printed 
backwards.  I wanted to avoid allocating separate memory just to be able to 
print it, so I think it's good enough to print backwards.  Therefore, your first 
message (before the import graph) might be difficult to display.  However, I 
think I can get it to work, but it will just print after the long-form of the 
cycle, is that OK?

Also note that it's not always a 2-element cycle, it could be an N element 
cycle, where N is up to the entire number of modules in the exe.

> 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.

I like the idea of using tabs to delineate 'non-participating' modules, but I'm 
unsure if just doing this makes it clear.  Maybe if I put the non-participating 
modules in parentheses?  Anyone else have an idea of how to print it?

> 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!

Haha! will do :)

-Steve