What sorts of things cause cyclic dependencies?

[Steven Schveighoffer]

On Thu, 14 Oct 2010 02:31:23 -0400, Jonathan M Davis <jmdavisProg at gmx.com>  
wrote:

> On Wednesday 13 October 2010 23:03:05 Lars T. Kyllingstad wrote:
>> On Thu, 14 Oct 2010 05:53:51 +0000, Lars T. Kyllingstad wrote:
>> > On Wed, 13 Oct 2010 21:25:15 -0700, Jonathan M Davis wrote:
>> >> Okay. in the code that I'm working on at the moment, I get an  
>> exception
>> >> saying that a cyclic dependency was detected but no information
>> >> whatsoever as to where it is or what it means. I haven't been able to
>> >> find much information on them other than some discussions of making  
>> it
>> >> so that the compiler detects them at compile time. I have yet to  
>> figure
>> >> out _what_ it is that is causes such errors. Could someone clue me  
>> in?
>> >> It's really hard to track down a bug when the error only tells you  
>> that
>> >> there's a bug and doesn't say anything about where it happens, and I
>> >> have no clue what sort of things can be cyclically dependent.
>> >
>> > Say you have two modules, a and b.  Both have static constructors,  
>> and a
>> >
>> > imports b:
>> >   // a.d
>> >   module a;
>> >   import b;
>> >   static this() { ... }
>> >
>> >   // b.d
>> >   module b;
>> >   static this() { ... }
>> >
>> > The language is then defined so that b's constructor is run before  
>> a's,
>> > since a depends on b.  But what happens if b imports a as well?  There
>> > is no way to determine which constructor to run first, so the runtime
>> > throws a "cyclic dependency" exception.
>>
>> I should mention that this can happen with larger cycles as well, i.e.  
>> "a
>> imports b, b imports c, c imports ..., ... imports a".  This can make
>> some cyclic dependencies very hard to track down.
>>
>> There was a discussion about this on the Phobos mailing list a few  
>> months
>> ago:
>>
>>   http://lists.puremagic.com/pipermail/phobos/2010-June/thread.html#949
>>
>> -Lars
>
> Well, just knowing that it involves module constructors is definitely  
> useful,
> though the error message really needs to be improved. Thanks.

I had mostly implemented a cyclic dependency improvement that actually  
printed the cycle.  However, I never committed it because I found there  
was a huge hole in the algorithm that needed to be addressed.  Essentially  
certain cycles are allowed (even today).

I think it can be done with an O(n^2) space and an O(n) algorithm, but I  
need to work on it.

BTW, there is a bug report for this problem:  
http://d.puremagic.com/issues/show_bug.cgi?id=4384

-Steve