Examples of DFA

[Richard (Rikki) Andrew Cattermole]

On 23/09/2025 5:54 PM, Walter Bright wrote:
> This is what I am talking about:
> ```
> @nogc void foo() { bar(); }
> 
> void bar() { abc(); }
> 
> void abc() { bar(); }
> ```
> Both bar() and abc() are @nogc. But the forward-only checking cannot 
> deduce it, and the result is:
> 
> test.d(3): Error: `@nogc` function `test.foo` cannot call non- at nogc 
> function `test.bar`
> 
> This is the simplest version of this problem. It can be quite complex, 
> but the result is the same - it cannot be figured out without solving 
> recursive data flow equations.
> 
> Another version of the problem:
> ```
> @nogc void foo() { bar(); }
> 
> void bar() { abc(); }
> 
> void abc();
> ```
> The body of abc() is not available to the compiler, so the compiler 
> cannot deduce @nogc for abc(). So, in order to deduce attributes of 
> abc(), the compiler must have the source code available for it. To do a 
> complete job, then, requires compilation of the entire program's code 
> base. Which will require a lot of memory and time.
> 
> Adam, Rikki, if I'm wrong, please show me how.

I will assume that ``@nogc`` is lint level attribute that does not 
effect mangling, as that would be a requirement for everything to link.
If it does effect mangling, things get so much harder to solve and a lot 
less flexible, hence I am not keen on such approach for DFA attributes.

To solve this is very simple, but it does require the compiler to see 
the result of the compilation of all three functions. Attributes via the 
.di generator, or a dedicated special file containing the information 
are both valid options here.

Instead of writing ``@nogc``, we write ``@nogc iff(foo, bar, abc)``.

 From there its a simple dependency resolver either during the 
compilation of the three functions or on usage.

This is the basis for my solution to a problem Adam has proposed for 
PhobosV3, which essentially is the desire to whitelist attributes. Use 
``@localnogc`` & if the function calls are all ``@nogc``, therefore the 
function is allowed to be ``@nogc``.

```d
void foo() @nogc => bar; // dependency resolve bar&abc's @nogc iff's
void bar() @nogc iff(abc) => abc;
void abc() @nogc iff(bar) => bar;
```

```d
void foo() @nogc => bar; // dependency resolve bar&abc's @nogc iff's
void bar() @nogc iff(abc); // body is irrelevant
void abc() @nogc iff(bar); // body is irrelevant
```

This is a very simple demonstrating of whole program graph analysis with 
whole function graph representation of equations per function. As far as 
I know no production language supports this and has been left in 
experimental 90's languages.

I won't say any .net language does this, but because they are an 
application VM, they do in fact see the whole program (minus FFI). What 
they can do, and what we can do without excellent serialization 
capabilities in the compiler isn't the same.

Of course I'm not suggesting @nogc should get this particular treatment, 
in practice its "good enough" (if we ignore white listing), but as an 
example of effect analysis its a good one even if it isn't a classical 
problem like pure.

Am I right to assume that the reason you haven't presented this 
solution, is because you want attributes to be finalized when bar&abc 
complete?