Seriously stupid bug here!

I had an enum an static this() { } (empty, forgot why I added it) one module and an struct in another module that converted values from the enum. I imported only that enum and guess what?!?! Cycle dependency! removed the static this() { } and worked!

The cycle dependency checking code is far too ignorant. It just blindly checks without any rationale. Someone said this was because phobos had a bug in it so the cycles were checked, maybe it's time to address that issue rather than breaking code arbitrarily?

On Wednesday, 30 May 2018 at 12:09:21 UTC, DigitalDesigns wrote:
> Seriously stupid bug here!
>
> I had an enum an static this() { } (empty, forgot why I added it) one module and an struct in another module that converted values from the enum. I imported only that enum and guess what?!?! Cycle dependency! removed the static this() { } and worked!
>
> The cycle dependency checking code is far too ignorant. It just blindly checks without any rationale. Someone said this was because phobos had a bug in it so the cycles were checked, maybe it's time to address that issue rather than breaking code arbitrarily?

I think an example would be useful. Anyway, if you think there's a bug there, write a report: https://issues.dlang.org

Andrea

On 5/30/18 8:09 AM, DigitalDesigns wrote:
> Seriously stupid bug here!
> 
> I had an enum an static this() { } (empty, forgot why I added it) one module and an struct in another module that converted values from the enum. I imported only that enum and guess what?!?! Cycle dependency! removed the static this() { } and worked!
> 
> The cycle dependency checking code is far too ignorant.

It is ignorant. It only checks for the presence of static constructors, not what they do. This is as designed -- there are too many ways for dependencies to leak between modules that it's really really hard to make it check real dependencies.

> It just blindly checks without any rationale. Someone said this was because phobos had a bug in it so the cycles were checked, maybe it's time to address that issue rather than breaking code arbitrarily?
> 

I don't know what was said, but the cycle code was very broken originally. A few years ago, I fixed it, and then it was re-broken by accident, and I re-fixed it.

It should work properly now. But that has nothing to do with adding an empty static ctor, it had to do with properly detecting cycles.

The cycle detection functions as designed. You can disable it via DRT flags, but this means that there is no guarantee that they run in the proper order. The compiler would have to build a much more sophisticated dependency tree in order to do anything more clever, but I doubt it would ever be able to be perfect in detecting which things truly depend on one another.

-Steve

On Wednesday, 30 May 2018 at 13:26:53 UTC, Steven Schveighoffer wrote:
> On 5/30/18 8:09 AM, DigitalDesigns wrote:
> ... it's really really hard to make it check real dependencies.


For serious dependency checking, you could try https://github.com/funkwerk/depend.
It's used in quite large commercial projects.

On 5/30/18 11:50 AM, Stefan wrote:
> On Wednesday, 30 May 2018 at 13:26:53 UTC, Steven Schveighoffer wrote:
>> On 5/30/18 8:09 AM, DigitalDesigns wrote:
>> ... it's really really hard to make it check real dependencies.
> 
> 
> For serious dependency checking, you could try https://github.com/funkwerk/depend.
> It's used in quite large commercial projects.

OK, so a couple things:

1. The cycle checking has to be really really fast, and run in a small amount of memory. It runs on startup of EVERY D program. I would LOVE to get rid of this problem, but unless we either invent our own object/linker system, or create some tools to work on the linked binary, we have to do this.

2. The cycle algorithm is fast and works correctly, given the dependencies that the compiler has provided. It's really not the cycle algorithm that is the problem, but the determination of dependencies. In other words, the problem is the compiler not tracing all the actual dependencies and outlining that in some structure to be parsed later during program startup.

As you increase the number of dependency points, and therefore the graph size, the cycle algorithm has to take longer to figure out if there are any cycles. So even if we can fix the problem outlined here, the cost may not make it worth the effort!

There are some ideas Martin and I have fleshed out a bit, which would help reduced the cyclic dependencies, but so far, nobody has had the time and/or skills to implement. For instance:

https://issues.dlang.org/show_bug.cgi?id=16265
https://github.com/dlang/druntime/pull/1602#issuecomment-231527759

-Steve

On Wednesday, 30 May 2018 at 18:49:40 UTC, Steven Schveighoffer wrote:
> On 5/30/18 11:50 AM, Stefan wrote:
>> On Wednesday, 30 May 2018 at 13:26:53 UTC, Steven Schveighoffer wrote:
>>> On 5/30/18 8:09 AM, DigitalDesigns wrote:
>>> ... it's really really hard to make it check real dependencies.
>> 
>> 
>> For serious dependency checking, you could try https://github.com/funkwerk/depend.
>> It's used in quite large commercial projects.
>
> OK, so a couple things:
>
> 1. The cycle checking has to be really really fast, and run in a small amount of memory. It runs on startup of EVERY D program. I would LOVE to get rid of this problem, but unless we either invent our own object/linker system, or create some tools to work on the linked binary, we have to do this.
>
> 2. The cycle algorithm is fast and works correctly, given the dependencies that the compiler has provided. It's really not the cycle algorithm that is the problem, but the determination of dependencies. In other words, the problem is the compiler not tracing all the actual dependencies and outlining that in some structure to be parsed later during program startup.
>
> As you increase the number of dependency points, and therefore the graph size, the cycle algorithm has to take longer to figure out if there are any cycles. So even if we can fix the problem outlined here, the cost may not make it worth the effort!
>
> There are some ideas Martin and I have fleshed out a bit, which would help reduced the cyclic dependencies, but so far, nobody has had the time and/or skills to implement. For instance:
>
> https://issues.dlang.org/show_bug.cgi?id=16265
> https://github.com/dlang/druntime/pull/1602#issuecomment-231527759
>
> -Steve

Why is this a runtime issue? It is not as if the execution of static this are non-deterministic. The compiler and linker must order the calls in some way. Maybe this is what you mean by own object/linker?  But even then, they would only have to be checked once so why check every time the exe is ran when once it is ran it must remain statically oriented for all future.

two exe's could be produced, one with only the static this code which is ran after linking and verified, if doesn't pass then a linker error is thrown.

These methods could be used for better alternatives but the real issue is dependencies of static constructors.

How bout instead require the user to deal with it? The user can specify the order to run and the compiler just blindly obeys.

pragma(cycle, 1)
static this()
{

}


...

pragma(cycle, 2)
static this()
{

}

It could require cycle to be unique or just share and let the compiler do what it wants(assumes no cycles).

This gives the programmer a fix but doesn't assume there are cycles, which most times there are not.

Later on, more intelligent cycle detecting code can be created and added and then can give a warning in which the user can go back and add the pragmas.

Alternatively, only require the pragmas on modules that cyclically import each other. Even if their is no cycle, the programmer just adds a pragma to satisfy the compiler/linker/rt.

On Wednesday, 30 May 2018 at 20:57:32 UTC, DigitalDesigns wrote:
> Why is this a runtime issue? It is not as if the execution of static this are non-deterministic. The compiler and linker must order the calls in some way. Maybe this is what you mean by own object/linker?  But even then, they would only have to be checked once so why check every time the exe is ran when once it is ran it must remain statically oriented for all future.

Because of separate compilation, the compiler can't do it. Because the generic linker doesn't do that sort of thing, the linker can't do it.

The first part is essentially intractable - e.g. module A's static this uses a global variable in module B that's set by module C. Module A may be compiled separately from module C, so the compiler can't see the dependency.

If the linker is to do it, the compiler needs to encode the information in the object file, and the linker must be made specially to support this. Maybe this could be put in some optional section in the object file, and linkers that don't support it would just ignore the information. If a non-compliant linker is used, the runtime needs to have a fallback, so even this won't get us entirely out of the woods. Only supporting special linkers comes with its own set of problems.

--
  Simen

On 5/31/18 2:14 AM, Simen Kjærås wrote:
> On Wednesday, 30 May 2018 at 20:57:32 UTC, DigitalDesigns wrote:
>> Why is this a runtime issue? It is not as if the execution of static this are non-deterministic. The compiler and linker must order the calls in some way. Maybe this is what you mean by own object/linker?  But even then, they would only have to be checked once so why check every time the exe is ran when once it is ran it must remain statically oriented for all future.
> 
> Because of separate compilation, the compiler can't do it. Because the generic linker doesn't do that sort of thing, the linker can't do it.
> 
> The first part is essentially intractable - e.g. module A's static this uses a global variable in module B that's set by module C. Module A may be compiled separately from module C, so the compiler can't see the dependency.
> 
> If the linker is to do it, the compiler needs to encode the information in the object file, and the linker must be made specially to support this. Maybe this could be put in some optional section in the object file, and linkers that don't support it would just ignore the information. If a non-compliant linker is used, the runtime needs to have a fallback, so even this won't get us entirely out of the woods. Only supporting special linkers comes with its own set of problems.
> 

Yes, this is really the crux of it.

I want to stress that the cycle detection is not really for the sake of detecting cycles, it's because you need to sort the modules in the order their static ctors should be called. When you can't sort them in an order, you have to call them in an arbitrary order (probably just in the order they were linked).

It is really a shame we have to do this at runtime, but that's due to the compilation model we are stuck with, and the linker tools we deal with.

However, once the binary is formed, it's possible we could *edit* the binary to hard-code the order -- at that point, everything is known. I have thrown that out there in terms of a nice project someone with the correct skills could do: https://forum.dlang.org/post/nl3du7$1as5$1@digitalmars.com

One

On Thursday, 31 May 2018 at 15:15:44 UTC, Steven Schveighoffer wrote:
> On 5/31/18 2:14 AM, Simen Kjærås wrote:
>> On Wednesday, 30 May 2018 at 20:57:32 UTC, DigitalDesigns wrote:
>>> Why is this a runtime issue? It is not as if the execution of static this are non-deterministic. The compiler and linker must order the calls in some way.
>> 
>> Because of separate compilation, the compiler can't do it. Because the generic linker doesn't do that sort of thing, the linker can't do it.
>> 
>> The first part is essentially intractable - e.g. module A's static this uses a global variable in module B that's set by module C. Module A may be compiled separately from module C, so the compiler can't see the dependency.
>
> Yes, this is really the crux of it.
>
> I want to stress that the cycle detection is not really for the sake of detecting cycles, it's because you need to sort the modules in the order their static ctors should be called. When you can't sort them in an order, you have to call them in an arbitrary order (probably just in the order they were linked).
>
> It is really a shame we have to do this at runtime, but that's due to the compilation model we are stuck with, and the linker tools we deal with.
>

Thinking about this problem for a while I can up with something that could both reduce the work the runtime had to do and allow us to remove the error in the OP.

But now I see most of it was suggested in that pull request. [1]

Would the best way to implement this be to extend ModuleInfo and include a getter that   loads the dependencies like importedModules(), or should the ctor/dtor stuff be moved to a new tables?

Also we might be able to get the compiler to insert a cluster_hash that's unique for each compiler run and a pre-ordered cluster_index. Then use this to speed up sorting in the runtime.

[1] https://github.com/dlang/druntime/pull/1602#issuecomment-231527759

On 5/31/18 5:12 PM, David Bennett wrote:
> On Thursday, 31 May 2018 at 15:15:44 UTC, Steven Schveighoffer wrote:
>> On 5/31/18 2:14 AM, Simen Kjærås wrote:
>>> On Wednesday, 30 May 2018 at 20:57:32 UTC, DigitalDesigns wrote:
>>>> Why is this a runtime issue? It is not as if the execution of static this are non-deterministic. The compiler and linker must order the calls in some way.
>>>
>>> Because of separate compilation, the compiler can't do it. Because the generic linker doesn't do that sort of thing, the linker can't do it.
>>>
>>> The first part is essentially intractable - e.g. module A's static this uses a global variable in module B that's set by module C. Module A may be compiled separately from module C, so the compiler can't see the dependency.
>>
>> Yes, this is really the crux of it.
>>
>> I want to stress that the cycle detection is not really for the sake of detecting cycles, it's because you need to sort the modules in the order their static ctors should be called. When you can't sort them in an order, you have to call them in an arbitrary order (probably just in the order they were linked).
>>
>> It is really a shame we have to do this at runtime, but that's due to the compilation model we are stuck with, and the linker tools we deal with.
>>
> 
> Thinking about this problem for a while I can up with something that could both reduce the work the runtime had to do and allow us to remove the error in the OP.
> 
> But now I see most of it was suggested in that pull request. [1]
> 
> Would the best way to implement this be to extend ModuleInfo and include a getter that   loads the dependencies like importedModules(), or should the ctor/dtor stuff be moved to a new tables?

It's really an interesting problem, probably one of the most puzzling algorithmic problems I've had to solve.

However, a lot of this is complicated because we don't do it at compile-time, but at runtime instead. We have way more time and memory and whatever we want to throw at it if we can move the sorting and cycle check to build time instead of runtime.

If we want to make the check more fine grained, we are talking metadata for every function call, and which static ctor-initialized items it may access, and which lines actually initialize them.

> Also we might be able to get the compiler to insert a cluster_hash that's unique for each compiler run and a pre-ordered cluster_index. Then use this to speed up sorting in the runtime.

Yeah, I don't think the runtime speed is a huge problem. Initializing the hash doesn't take much time at all.

Hm... I just had a crazy idea: what if D had a switch that allowed it to store a dependency graph of constructors into a json file, and then when you link, there is a wrapper which consumes all these files, runs the cycle detection and sort, and then compiles a perfectly sorted moduleinfo section to be included in the binary (obviously, written in D and compiled by the compiler).

This doesn't affect the linker, and uses all the existing tools we have to create object files and binaries.

I'll have to bring this out into its own thread so it's not buried.

-Steve