npm package: @statedelta-actions/graph
Description: Dependency graph with cycle detection, topological sort and propagators
Author: Anderson D. Rosa
Latest version: 0.3.0

# 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`](./docs/ARCHITECTURE.md).
> Para decisões arquiteturais, ver [`docs/DECISIONS.md`](./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`:

```typescript
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:

```typescript
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>`:

```typescript
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.

```typescript
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.

```typescript
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:

```typescript
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

```typescript
// 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

```typescript
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

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

### Lookup

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

### Dependency Queries

```typescript
// 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)

```typescript
// 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

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

### Dirty Tracking

```typescript
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

```typescript
graph.getStats(): GraphStats

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

### Iteration

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

### Results

```typescript
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;
}
```