Element-level dependency edges for indexed access (static per-key dataflow)

[shunichironomura]

Warning

This content was written by an AI agent and must be verified by a human developer. After human verification, this alert may be removed.

Summary

Dependency tracking, scheduling, cycle detection, and graphcal graph all work at declaration granularity: an @ reference from a to w is one edge, even when both are indexed and the body only reads @w[t] for the current t. The language already distinguishes static keys (labels, loop variables, key(Fin(N), c), Fin-key arithmetic i + c) from runtime keys, and docs/language/indexes.md ("Evaluation granularity") describes static-key access as keeping per-element edges. This issue proposes making that distinction real as a static, element-level dependency relation that refines the declaration-level graph, exposed through graphcal dump / graphcal graph, without changing evaluation semantics.

Motivation

The driving use case is decision models under uncertainty (XLRM / robust decision making) where a .gcl model is served to Tenax. Such a model has uncertainty inputs w_k, stage-indexed action nodes a[t], and an information structure: the action at stage t may depend on w_k only if w_k has been observed by stage t. That constraint should be checkable from the DAG alone. Today the graph says action → w1 for the whole action declaration, so a checker cannot tell whether action[S0] (before the observation) reads w1.

index Stage = { S0, S1 };
index Mine = { One, Two };

param w1: Dimensionless(min: 0.0, max: 40.0) = 20.0;
param w2: Dimensionless(min: 2.0, max: 34.0) = 18.0;
param threshold: Dimensionless = 18.0;

// w1 is observed after stage 0 and may only influence stage 1.
node action: Key<Mine>[Stage] = for t: Stage {
    match t {
        Stage#S0 => Mine#One,
        Stage#S1 => if @w1 >= @threshold { Mine#One } else { Mine#Two },
    }
};

Today: one edge w1 → action. Desired: w1 → action[S1] only, so "no element of action at stage t reads an input revealed after t" is a structural property.

The same granularity gap is the "per-(node, t) dependency granularity decision" listed as untracked in internals/vensim-parity.md (§4.1, A[t] → B[t-1] cross-references). This issue only covers the analysis side; it does not change scheduling or cycle detection.

Current behaviour (as far as I can tell)

• ResolvedDagDependencies::runtime_deps (crates/graphcal-compiler/src/tir/typed/model.rs) is HashMap<ResolvedDeclName, BTreeSet<ResolvedDeclName>>: declaration to declarations, no key information.
• combined_runtime_order_for (crates/graphcal-eval/src/exec_plan.rs) schedules and detects cycles at that granularity.
• graphcal graph documents that "every @ reference becomes a directed edge from the value being read to the declaration reading it" (docs/cli-reference.md).
• IndexArg (crates/graphcal-compiler/src/syntax/ast/value.rs) already separates Variant (label), Var (loop variable), and Expr (arbitrary expression), which is the syntactic information the analysis needs.
• The "Evaluation granularity" note in docs/language/indexes.md (added with Add first-class index keys: Key<I>, argmax/argmin, and key formers #1070) says static-key access keeps fine-grained per-element edges. I did not find a data structure that records such edges; if the note describes evaluator-internal behaviour, please point to it. Either way, nothing element-level is exposed to tooling today.

Where declaration-level edges lose information

Three distinct situations, which need different treatment:

1. Static keys. @w[Stage#S1], @w[t] under for t: Stage, @v[i + 1] under for i: Fin(N), key(Fin(N), c). The accessed element is a known function of the enclosing loop binders. Element-level edges are computable by a symbolic key map. This is the main opportunity.
2. Runtime keys. @x[@k] where k comes from argmax, fin_key, nearest_key, or a stored Key node. The element is data-dependent, so the edge is genuinely a gather over the whole declaration. This stays All unless a later extension bounds the key's possible values.
3. Conditional dependence. for t: TimeStep { if coord(t) >= @t_obs { f(@w1) } else { g() } } references @w1 in every element; whether it is live for a given t depends on a runtime predicate. A dataflow edge cannot express this. The language-level answer is to make the stage structure static: match t { Stage#S0 => ..., Stage#S1 => ... } over a named axis gives exact per-arm dependencies, and stage-specific dag blocks with explicit param lists (Strict Isolation) make the information set an interface. The analysis should treat match on a loop key as per-element, and leave if on runtime predicates as a union.

Proposal (incremental)

Step 1: element-level dependency relation in the compiler

For every edge reader → source in runtime_deps where at least one side is indexed, record a key map from the reader's axis keys to the set of source keys read. A small algebra is enough for the static forms:

Reader expression	Key map (per axis)
@src[I#L]	Const(L)
@src[t] with t a for binder over the same axis	Identity
@src[i + c] (Fin-key arithmetic)	Shift(c)
@src[key(Fin(N), c)]	Const(c)
@src[@k] with runtime k	All
sum(for m: M { @src[m] }) and other aggregations	All on the aggregated axis (a scalar reads every element)
match t { I#A => e_A, I#B => e_B } under for t: I	per-arm: element A gets deps(e_A), element B gets deps(e_B)
if p { e1 } else { e2 } with runtime p	union of both branches
scan / unfold over axis T	element t depends on source elements <= t (Prefix); state reads through prev are Prefix, reads of other indexed nodes at t are Identity
anything else	All

Multi-axis access is the product of per-axis maps. Non-indexed readers with a constant key get a single-element edge. All reproduces today's declaration-level edge exactly, so the relation is a refinement: projecting every key map to All must give back runtime_deps.

Scheduling, cycle detection, and evaluation are unchanged. The relation is analysis-only data.

Step 2: expose the relation

• graphcal dump includes the key maps next to the existing dependency information.
• graphcal graph gets an opt-in flag (name to be decided, for example --edges element) that prints one edge per (reader element, source element) pair for static maps and keeps a single labelled All edge for gathers. Output stays deterministic (sorted).

Step 3 (later, separate issue): consumers

• A check that a stage-indexed declaration does not read inputs before their declared observation stage (the decision-model use case).
• Per-(node, t) cycle detection so that A[t] → B[t-1] becomes legal (internals/vensim-parity.md §4.1, related to Design: DAG-style closure syntax for unfold/scan bodies #349 and feat: allow indexed state in unfold/scan #889). This is a semantic change and is explicitly out of scope here.

Non-goals

• No change to evaluation order, scheduling, or which programs compile.
• No attempt to bound runtime keys (argmax, fin_key, nearest_key); they stay All.
• No new surface syntax. If a way to declare an information structure is wanted, that is a follow-up.

Open questions

• Representation: is a per-axis map algebra (Const, Identity, Shift, Prefix, All) sufficient, or should the relation be materialised as explicit key sets for concrete axes (bounded by the existing 1,000,000-element limit)?
• Should param defaults participate the same way as node bodies? They are ordinary graph expressions, so presumably yes.
• Include boundaries: an include binding values: @displacement passes the whole value; inside the DAG the analysis continues per element. Is the projection across the boundary Identity on the bound axis?
• Should the docs/language/indexes.md "Evaluation granularity" note be reworded until the relation exists, so the docs do not promise per-element edges the tooling cannot show?

Acceptance criteria

• The compiler computes the element-level relation for static keys (label, loop variable, key(Fin(N), c), Fin-key i + c), per-arm match on loop keys, aggregation (All on the aggregated axis), and scan/unfold (Prefix), and falls back to All for runtime keys and runtime if.
• Projecting every key map to All reproduces runtime_deps exactly (property test).
• graphcal dump and graphcal graph (opt-in flag) expose the relation deterministically.
• Fixtures: one per key form; one two-stage decision-model fixture (as in the example above) whose exported element-level graph shows w1 → action[S1] and no edge into action[S0]; one unfold fixture showing the Prefix relation.
• Docs: indexes.md granularity note and cli-reference.md (graphcal graph, graphcal dump) updated.

Related

• Add first-class index keys: Key<I>, argmax/argmin, and key formers #1070 (index keys; introduced the granularity note)
• DAG visualizer #512 (DAG visualizer)
• Design: DAG-style closure syntax for unfold/scan bodies #349, feat: allow indexed state in unfold/scan #889 (unfold / scan body structure and indexed state; per-(node, t) granularity discussion in internals/vensim-parity.md)