analysis/flowgraph: the second IR — a control-flow graph over steps (written order, `if:` skips, `switch:` arms, loop back-edges with carried state, `parallel:`/`async:` forks and joins, `call:` entries and exits) joined to #1583's def-use edges, built once per program by an analyzer others require, the `buildssa` of Flowstate
Nobody has claimed this yet.
- Dominant language
- Go
- Stars
- 9
- Forks
- 0
- Avg merge
- 3h 3m
- Merged PRs (30d)
- 509
Description
Observed behavior
Every analysis over a program needs to know two things: what runs after what, and what reads what. At dc9429d the second is answered by four walkers (#1583) and the first by none as a data structure: the validator threads a refScope through its own recursion (validate.go:817-903), the executor decides order while running (eval.go's runNodes, runForEach, runParallel), the sizing question (#1585) needs segments that nothing represents, compensation order is a rule in DSL.md's fifth round that only the executor's undo log embodies, and a "which arms are reachable" question has no graph to ask.
Go's analyzers do not each re-derive control flow: passes/ctrlflow and passes/buildssa build it once and other analyzers Require the result. A Flowfile is structured (no arbitrary jumps), so its graph is smaller than SSA and cheaper to keep correct.
Desired outcome
analysis/passes/flowgraph: an analyzer with a ResultType of *flowgraph.Program:
- nodes are IR paths (#1439's grammar) for every step, declaration, loop state, call boundary and declared output;
- control edges with a kind:
next(written order),skip(anif:that is false),arm(aswitch:case or default),loop(a back-edge, carrying thestatename),fork/join(parallel:andasync:),enter/exit(acall:),wait(a step that suspends),compensate(the reverse registration order the fifth round defines, materialized as edges so it is a query); - data edges are #1583's (consumer, producer, field, certainty);
- regions: the atomic segments
CheckAtomicBlockActivitiesreasons about, as subgraphs, so sizing reads them rather than recomputing; - deterministic, bounded by the spec's own counts, and built from the normalized program only (never from source).
Consumers: reachability (an arm no switch: value reaches, a step after an unconditional failure), compensation order as a query for flow explain and #1385's timeline record, the sizing sibling's segments and cut candidates, the LSP's references and rename, DST's choice of interleavings, the mutation sibling's equivalence check, and the validator's scope rules rewritten as graph queries.
Acceptance criteria
- For every example, the compensation order the graph reports equals the order the local driver's undo log records on a forced failure at each step, pinned by a conformance case (both drivers) that fails the step and compares.
- The graph's control edges for
examples/enterprise-incident-response(parallel evidence gathering, two gates, escalation) render as a mermaid diagram inflow explain --graphand the rendering is a golden. - A schema-walk test fails when a
Nodekind or an expression-bearing field is added without a graph rule (the #508 pattern). - Building the graph over the largest example costs under a stated bound, measured in a benchmark beside
flowfile_bench_test.go.
Constraints and dependencies
- Requires #1583 (data edges) and #1437 (the scope table) as its inputs, and #1582's callee table to represent
enter/exitonce rather than per copy. - Conservative where the program is dynamic (
items:length, a computedswitch:value): the graph carries the edge withcertainty: dynamic; no consumer may treat an unknown as absent. - Not a runtime structure: the executor is not rewritten to walk it. Both drivers stay as they are; the graph is what analysis and tooling read, and the conformance case above is what keeps it honest.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with validate.go:817-903, eval.go’s runNodes/runForEach/runParallel, DSL.md’s fifth round, and the dependency outputs from #1583, #1437, and #1582. Read the proposed analysis/passes/flowgraph shape and its acceptance criteria before designing the normalized graph. Done means conformance, Mermaid golden, schema-walk, and benchmark tests cover the specified edges, regions, dynamic certainty, and bounds.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- compilers, tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100