Examples of DFA

[Dennis]

On Tuesday, 23 September 2025 at 05:54:00 UTC, Walter Bright 
wrote:
> 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.

I think there's a simpler way. You can model this as a graph 
reachability problem, with vertices for each function, directed 
edges for function calls, and a 'gc' node representing possible 
GC operations such as `new`, closures, extern function without 
`@nogc` etc.
Then all you need is a graph search starting from the gc node, 
and every node you don't find is @nogc.

Below is a D implementation you can toy with. If you find a case 
where this fails where solving data flow equations would succeed, 
let me know.

N.b. the reason dmd can't do this (or the data flow approach) 
currently is because `@nogc`-ness needs to be determined before 
the call graph is complete, see 
https://forum.dlang.org/post/ydemnavvtzytjkmibwvz@forum.dlang.org

If we remove @nogc from a function's type/mangle in a next 
edition (which I'm all for) it can work.

---


```D
import std;

class Func
{
     string name;
     Func[] calledFrom;
     bool isNogc = true;
     bool isVisited = false;

     this(string name) { this.name = name; }
     void call(Func f) { f.calledFrom ~= this; }
}

void computeNogc(Func gc)
{
     Func[] stack = [gc];

     while (!stack.empty)
     {
         auto node = stack[$ - 1];
         stack.length--;
         node.isNogc = false;
         node.isVisited = true;

         foreach (f; node.calledFrom.filter!(x => !x.isVisited))
             stack ~= f;
     }
}

void main()
{
     auto foo = new Func("foo");
     auto bar = new Func("bar");
     auto abc = new Func("abc");

     // pseudo function representing `new`, closures, anything 
that allocates
     auto gc = new Func("gc");

     // Add your function calls here:
     foo.call(bar);
     bar.call(abc);
     abc.call(bar);

     abc.call(gc); // abc() does something that allocates

     computeNogc(gc);

     // Print results
     foreach (a; [foo, bar, abc])
         writeln(a.name, ". at nogc = ", a.isNogc);
}
```