cycle dependencies

[Steven Schveighoffer]

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