Use a formal Topological Sort algorithm for the audio dependency graph

[austintheriot]

Resolving the audio dependency graph into a static, ordered visit-list is fundamentally a dependency resolution challenge with some interesting audio-specific nuances.

Constraints

The key constraints are:

• Nodes have dependencies
• Some nodes can have self-recursive connections, where the node's output becomes its own a parent node's input on the next frame
• We want a static, deterministic order of node processing
• Every node must have all its input dependencies resolved before it can process

Goal

The goal is a linearized list where:

• Every node appears exactly once
• All node dependencies are satisfied before the node is processed
• Circular/recursive dependencies are handled gracefully

Approach

The most natural approach here is to use a Topological Sort algorithm, specifically adapted for handling potential recursive dependencies. A classic Depth-First Search (DFS)-based topological sort won't work perfectly because of the self-referential connections.

Some things to keep in mind:

• Treat self-recursive connections as a special case of circular dependency
• Potentially introduce "delay" or "state" nodes that can break pure cyclic dependencies
• Ensure that nodes with circular dependencies are processed in a way that allows reasonable signal propagation

Possible solution

One potential algorithm structure might look like:

• Start with nodes that have no incoming dependencies
• Progressively mark nodes as "visited" or "processed"
• For nodes with self-recursion, ensure their state can be initialized and that they have a well-defined first-frame behavior
• Potentially use a "staging" mechanism where nodes with circular dependencies get special processing order

[wallabra]

In the end, circular dependencies might best be flattened by having two separate buffers for every node being rendered ("previous" and "current"), where current is moved to previous at the start of rendering, and a new, empty buffer to be written to is allocated and set in its place. This will of course lead to latency or feedback, but since it's impossible to have true zero-delay circular feedback, this is likely inevitable.