DependencyGraph — Grafo de Dependências

Módulo: graph/ Escopo: Grafo genérico de dependências com propagação de propriedades, cycle detection e dirty tracking. Consumido pelo ActionAnalyzer para análise estática em register-time. Dependências externas: Apenas Directive de core/types (tipo genérico). Zero acoplamento com actions/.

Para arquitetura interna, pipelines e algoritmos, ver docs/ARCHITECTURE.md. Para decisões arquiteturais, ver docs/DECISIONS.md.

O que é

O DependencyGraph é uma estrutura de dados viva que modela as relações de invocação entre Actions. Quando Action A contém uma directive { type: "action", id: "B" }, existe uma aresta A→B no grafo. A depende de B.

O grafo computa metadados derivados dessa estrutura: ciclos, propriedades transitivas via propagators injetáveis (capabilities, leaf/branch, profundidade, e qualquer propriedade custom). Tudo em register-time. Invoke-time é fast path puro — O(1) lookup, zero análise.

O grafo é policy-agnostic. Ele computa fatos. Quem decide o que fazer com esses fatos (rejeitar ciclos, bloquear capabilities, limitar profundidade) é a camada acima — o ActionAnalyzer ou o consumer via policies.

Propriedades são configuração, não código. O grafo não sabe o que é "capability" ou "leaf" — sabe como propagar um valor genérico em ordem topológica. As propriedades built-in (capabilities, leaf, maxDepth) são propagators injetados via config.

Declarations são trust boundaries. O consumer pode declarar o que um nó deve ser (ex: { readonly: true }). A declaração cria uma barreira de propagação: dependentes veem o valor declarado, não o inferido. Se a inferência contradiz a declaração, o conflito é responsabilidade do nó que declarou — não dos dependentes.

Data Model

ActionNode — O que o consumer vê

Cada Action registrada vira um ActionNode:

interface ActionNode {
  // ── Dados ──
  readonly id: string;
  readonly directives: readonly Directive[];
  readonly params?: Record<string, unknown>;
  readonly metadata?: Record<string, unknown>;

  // ── Computados ──
  readonly ownCapabilities: ReadonlySet<string>;
  readonly directDependencies: ReadonlySet<string>;
  readonly inCycle: boolean;
  readonly pendingDependencies: ReadonlySet<string>;
  readonly dirty?: DirtyState;

  // ── Propriedades via Propagators ──
  readonly properties: ReadonlyMap<string, unknown>;   // Resolved (declared ?? inferred)
  readonly inferred: ReadonlyMap<string, unknown>;     // Verdade computada (ignora declarações)
  readonly declarations: ReadonlyMap<string, unknown>; // Contratos do consumer (trust boundaries)
}

Três camadas por propriedade:

| Camada | Fonte | Quem vê | |--------|-------|---------| | inferred | Computado: own + deps transitivas | O próprio nó (introspecção/debug) | | declarations | Setado pelo consumer no input | Validação interna | | properties | declared ?? inferred (resolved) | Dependentes (trust boundary) |

GraphActionInput — O que o consumer fornece

O grafo recebe dados já pré-processados:

interface GraphActionInput {
  readonly id: string;
  readonly directives: readonly Directive[];
  readonly ownCapabilities: ReadonlySet<string>;
  readonly directDependencies: ReadonlySet<string>;
  readonly tags?: ReadonlySet<string>;
  readonly params?: Record<string, unknown>;
  readonly metadata?: Record<string, unknown>;

  /**
   * Declarações — contratos públicos (trust boundaries).
   * Cada key = nome de um propagator registrado.
   * Efeitos: barreira de propagação, validação contra inferência.
   */
  readonly declarations?: Record<string, unknown>;
}

O grafo não chama handler.analyze(). O consumer (ActionAnalyzer) faz isso e passa o resultado pronto.

Propagators

O grafo propaga propriedades genéricas bottom-up via Propagator<T>:

interface Propagator<TValue> {
  extract(input: GraphActionInput): TValue;                    // Valor próprio do nó
  merge(own: TValue, depValues: Iterable<TValue>): TValue;    // Merge com deps
  cycleValue(own: TValue): TValue;                            // Valor pra nós cíclicos
  fixpoint?: boolean;                                          // Fixpoint iteration pra ciclos?
  equals?: (a: TValue, b: TValue) => boolean;                 // Comparação customizada
}

Built-in: capabilities (Set<string>)

Union transitiva. Fixpoint pra ciclos (nós cíclicos compartilham tudo).

Action "heal":     own: {write}  → capabilities: {write}
Action "combat":   own: {invoke, emit}, deps: {heal} → capabilities: {invoke, emit, write}

Built-in: leaf (boolean)

Contagion: qualquer dep em ciclo → branch.

A (leaf) → sem deps
B (leaf) → deps: [A]       ✓ todas leaf
X↔Y      → ciclo = branch
C        → deps: [X]       ← contágio = branch

Built-in: maxDepth (number)

Max das deps + 1. Ciclo = Infinity.

Opt-in: readonly (boolean)

Contagion: qualquer dep effectful (write/emit) → effectful.

import { readonlyPropagator, DEFAULT_PROPAGATORS } from "@statedelta-actions/graph";

const graph = new DependencyGraph({
  propagators: { ...DEFAULT_PROPAGATORS, readonly: readonlyPropagator },
});

Opt-in: tier (number | undefined)

Nível numérico propagado via Math.max. Restrição hierárquica de invocação.

Action "heal":       tier: 500 (declarado)
Action "combat":     deps: [heal, damage(tier: 200)]  → tier inferido: 500
Action "rule:low":   tier: 300 (declarado), deps: [combat]
                     → inferred: 500, declared: 300 → DECLARATION_CONFLICT

Nodes sem tier (undefined) não impõem restrição — apenas propagam o max das deps.

import { tierPropagator, DEFAULT_PROPAGATORS } from "@statedelta-actions/graph";

const graph = new DependencyGraph({
  propagators: { ...DEFAULT_PROPAGATORS, tier: tierPropagator },
});

createBooleanPropagator — Helper

A maioria das propriedades booleanas segue o padrão de contagion:

const myPropagator = createBooleanPropagator({
  extract: (input) => !input.ownCapabilities.has("write"),
  // cycleValue: false (default)
  // contagion: "any_false" (default) — qualquer dep false → resultado false
});

Suporta contagion: "any_true" para o pattern inverso.

Declarations (Trust Boundaries)

O Conceito

Inferência — O que o grafo computa a partir do comportamento observável e das dependências transitivas. É a verdade computada. Nunca pode ser silenciada.

Declaração — O que o consumer afirma que a Action é. É um contrato público. Dependentes confiam nesse contrato. Se a inferência contradiz, o conflito é responsabilidade do nó que declarou.

Declarar NÃO sobrescreve a inferência.
Declarar é assinar um contrato público.
O grafo SEMPRE infere (a verdade não muda).
Se inferência ≠ declaração → DECLARATION_CONFLICT no nó que declarou.
Dependentes veem o valor DECLARADO, não o inferido.

Barreira de Propagação

A → B → C

Cenário 1 — Sem declarações:
  C: write, B: write (propagado), A: write (propagado)

Cenário 2 — B declara readonly:
  C: write, B: inferred=write, declared=readonly → CONFLITO em B
  A: readonly (vê a DECLARAÇÃO de B, não a inferência)

A não sabe que C é write. A confia no contrato de B. O conflito é responsabilidade de B.

Resolved Value

inferred  = propagator.merge(own, depResolvedValues)  — verdade computada
declared  = input.declarations[propName]               — contrato do consumer
resolved  = declared ?? inferred                       — valor público (o que deps veem)

Exemplo

Action "safeHeal":
  directives: [{ type: "action", id: "heal" }]   (heal tem write)
  declarations: { readonly: true }
  → inferred: readonly=false (heal é write)
  → declared: readonly=true
  → CONFLITO: inferred ≠ declared
  → resolved: readonly=true (BARREIRA)

Action "report":
  directives: [{ type: "action", id: "safeHeal" }]
  → vê safeHeal.resolved=true (barreira) → readonly=true ✓

report é readonly porque confia na declaração de safeHeal. O conflito ficou em safeHeal.

API

Construction

// Default: usa DEFAULT_PROPAGATORS (capabilities, leaf, maxDepth)
const graph = new DependencyGraph();

// Custom propagators (com opt-ins)
const graph = new DependencyGraph({
  propagators: {
    ...DEFAULT_PROPAGATORS,
    readonly: readonlyPropagator,
    tier: tierPropagator,
  },
});

// Grafo puro — sem propriedades computadas
const graph = new DependencyGraph({ propagators: {} });

Registration

graph.register(input: GraphActionInput): GraphRegisterResult
graph.registerMany(inputs: readonly GraphActionInput[]): GraphBatchResult
graph.unregister(id: string): boolean

Batch resolve forward references: se A depende de B e B é registrado depois de A no mesmo batch, a edge é resolvida no endBatch.

Batch

graph.beginBatch(): void
graph.endBatch(): GraphBatchResult
// Suporta nesting — inner endBatch é no-op, outer processa tudo

Lookup

graph.has(id: string): boolean
graph.get(id: string): ActionNode | undefined
graph.size: number

Dependency Queries

// Diretas — O(1), retornam live reference
graph.dependenciesOf(id: string): ReadonlySet<string>   // quem eu invoco
graph.dependentsOf(id: string): ReadonlySet<string>      // quem me invoca

// Transitivas
graph.transitiveDependenciesOf(id: string): ReadonlySet<string>
graph.transitiveDependentsOf(id: string): ReadonlySet<string>

// Com depth limit
graph.downstream(id: string, maxDepth?: number): string[]
graph.upstream(id: string, maxDepth?: number): string[]

Properties (via Propagators)

// Resolved (declared ?? inferred) — o que dependentes veem
graph.propertyOf<T>(id: string, name: string): T | undefined

// Inferido (verdade computada, ignora declarações)
graph.inferredOf<T>(id: string, name: string): T | undefined

// Declaração (contrato público) se existir
graph.declarationOf<T>(id: string, name: string): T | undefined

// Conflitos: propriedades onde inferred ≠ declared
graph.conflictsOf(id: string): readonly DeclarationConflict[]

// Exemplos:
graph.propertyOf<boolean>("A", "leaf")              // true
graph.propertyOf<Set<string>>("A", "capabilities")  // Set(["write"])
graph.propertyOf<number>("A", "maxDepth")           // 2
graph.propertyOf<boolean>("A", "readonly")          // opt-in
graph.propertyOf<number>("A", "tier")               // opt-in

Cycle Detection

graph.inCycle(id: string): boolean
graph.wouldCreateCycle(sourceId: string, targetId: string): boolean
graph.getCycles(): ReadonlyArray<readonly string[]>
graph.getNodesInCycle(): ReadonlySet<string>

Dirty Tracking

graph.isDirty(id: string): boolean
graph.getDirtyNodes(): ReadonlySet<string>
graph.markDirty(id: string, reason: DirtyReason): number
graph.clearDirty(id: string): void
graph.clearAllDirty(): void
graph.recompute(): number

Stats

graph.getStats(): GraphStats

interface GraphStats {
  totalActions: number;
  totalEdges: number;
  leafCount: number;
  branchCount: number;
  cycleCount: number;
  maxDepth: number;
  isolatedCount: number;
}

Iteration

for (const node of graph) { ... }
graph.entries(): IterableIterator<[string, ActionNode]>
graph.ids(): IterableIterator<string>
graph.nodes(): IterableIterator<ActionNode>

Results

interface GraphRegisterResult {
  registered: readonly string[];
  warnings: readonly GraphRegisterWarning[];
  errors: readonly GraphRegisterError[];
}

interface GraphBatchResult extends GraphRegisterResult {
  cycles: ReadonlyArray<readonly string[]>;
  dirtyPropagated: number;
  recomputed: number;
}

interface DeclarationConflict {
  readonly property: string;
  readonly declared: unknown;
  readonly inferred: unknown;
}