El problema: la recomputación está en todos lados

Considerar qué sucede al escribir un carácter en un IDE. El language server necesita:

  1. Re-lexear el archivo modificado (o al menos la región modificada)
  2. Re-parsear los nodos del syntax tree afectados
  3. Re-resolver nombres en el scope modificado
  4. Re-typecheckear expresiones que dependen de tipos que cambiaron
  5. Regenerar diagnósticos, completions, hover info

Para una implementación ingenua, cada pulsación de tecla dispara una ejecución completa del pipeline. En un codebase de 100K líneas con type inference complejo, eso implica fácilmente 2-5 segundos. Los usuarios notan cualquier demora por encima de 100ms. Algo tiene que ceder.

La respuesta tradicional es "almacenar todo en caché e invalidar con cuidado." Pero la invalidación manual de caché en un pipeline de compilador es una pesadilla. Las dependencias son profundas, circulares, y cambian de forma dependiendo del input. Si se omite un edge de invalidación, quedan resultados obsoletos. Si se sobre-invalida, se vuelve a recomputación completa.

Los frameworks de computación incremental automatizan este proceso. Se describe la computación como un grafo de queries, el framework rastrea dependencias en runtime, y cuando un input cambia, recomputa exactamente lo necesario, nada más.

Salsa: computación incremental demand-driven

Salsa es un framework de Rust desarrollado por el equipo de rust-analyzer (originalmente por Niko Matsakis). Implementa computación incremental demand-driven con rastreo automático de dependencias.

El modelo central tiene tres conceptos:

  1. Inputs, valores mutables que se establecen desde fuera (contenido de archivos, configuración)
  2. Funciones tracked, computaciones puras que leen inputs y otras funciones tracked
  3. La database, mantiene todos los inputs, resultados almacenados en caché y metadatos de dependencias

A continuación se muestra un ejemplo mínimo, un sistema que analiza archivos y computa un índice de símbolos:

#[salsa::input]
pub struct SourceFile {
 #[return_ref]
 pub name: String,
 #[return_ref]
 pub contents: String,
}

#[salsa::tracked]
pub struct ParsedFile<'db> {
 #[return_ref]
 pub ast: Ast,
 #[return_ref]
 pub errors: Vec<ParseError>,
}

#[salsa::tracked]
fn parse_file<'db>(db: &'db dyn Db, file: SourceFile) -> ParsedFile<'db> {
 let contents = file.contents(db);
 let (ast, errors) = parser::parse(&contents);
 ParsedFile::new(db, ast, errors)
}

#[salsa::tracked]
fn file_symbols<'db>(db: &'db dyn Db, file: SourceFile) -> Vec<Symbol> {
 let parsed = parse_file(db, file);
 let ast = parsed.ast(db);
 extract_symbols(ast)
}

#[salsa::tracked]
fn all_symbols<'db>(db: &'db dyn Db, files: &[SourceFile]) -> SymbolIndex {
 let mut index = SymbolIndex::new();
 for &file in files {
 for symbol in file_symbols(db, file) {
 index.insert(symbol);
 }
 }
 index
}

Al invocar all_symbols, Salsa ejecuta la computación completa y registra que all_symbols depende de file_symbols para cada archivo, que depende de parse_file, que depende del input contents del archivo.

Al cambiar el contenido de un archivo y realizar la siguiente llamada a all_symbols, Salsa:

  1. Nota que el input contents cambió para un archivo
  2. Verifica si el resultado de parse_file realmente cambió (quizá solo se modificó un comentario)
  3. Si el resultado del parse cambió, verifica si file_symbols cambió
  4. Solo recomputa all_symbols si la lista real de símbolos de ese archivo cambió

Este es el insight clave: early cutoff. Incluso si un input cambia, si el resultado intermedio es igual al anterior, las computaciones downstream no necesitan re-correrse. En la práctica, esto significa que cambiar el cuerpo de una función no invalida el índice de símbolos, los símbolos no cambiaron.

El contador de revisiones

Internamente, Salsa usa un contador global de revisiones. Cada vez que un input cambia, la revisión se incrementa. Cada valor almacenado en caché guarda dos cosas:

  • verified_at: la última revisión donde este valor fue confirmado válido
  • changed_at: la última revisión donde este valor realmente cambió

Al acceder a un valor almacenado, Salsa verifica si verified_at == current_revision. Si no es así, recorre el grafo de dependencias hacia atrás para determinar si algún input del que este valor depende (transitivamente) tiene changed_at > verified_at. Si ninguna dependencia cambió, el valor sigue siendo válido, se actualiza verified_at y se devuelve el resultado almacenado sin recomputar.

Revisión 1: Computación inicial
 file.contents changed_at=1
 parse_file changed_at=1 verified_at=1
 file_symbols changed_at=1 verified_at=1
 all_symbols changed_at=1 verified_at=1

Revisión 2: Editar archivo A (solo comentario)
 file_A.contents changed_at=2
 parse_file(A) → recomputar → AST idéntico → changed_at=1 verified_at=2
 file_symbols(A) → dependencia sin cambios → changed_at=1 verified_at=2
 all_symbols → dependencia sin cambios → changed_at=1 verified_at=2
 // Trabajo total: re-parseó un archivo. Todo lo demás fue gratis.

Revisión 3: Editar archivo B (agregar función)
 file_B.contents changed_at=3
 parse_file(B) → recomputar → AST diferente → changed_at=3 verified_at=3
 file_symbols(B) → recomputar → nuevo símbolo → changed_at=3 verified_at=3
 all_symbols → recomputar (una dep cambió) → changed_at=3 verified_at=3
 // parse_file(A), file_symbols(A) intactos, siguen verified_at=2, válidos.

Manejo de ciclos

Los compiladores frecuentemente tienen dependencias circulares, una implementación de trait puede referenciar un tipo que referencia al trait. Salsa maneja ciclos explícitamente:

#[salsa::tracked(cycle_fn=recover_type_cycle)]
fn infer_type<'db>(db: &'db dyn Db, expr: ExprId) -> Type {
 // ... puede llamar a infer_type en otras expresiones
}

fn recover_type_cycle<'db>(
 db: &'db dyn Db,
 _cycle: &salsa::Cycle,
 expr: ExprId,
) -> Type {
 Type::Error // Romper el ciclo con un tipo error
}

Cuando Salsa detecta un ciclo (el mismo query se invoca recursivamente con la misma key), ejecuta la función de recovery. La función de recuperación determina el comportamiento, tipos de error, iteración de punto fijo, o cualquier estrategia apropiada para el dominio.

Adapton: la base académica

Adapton precede a Salsa y provee el framework teórico. El artículo fundamental (Hammer et al., 2014) introduce "demanded computation graphs", un modelo donde las computaciones son nodos, las dependencias de datos son edges, y el sistema propaga cambios lazily a través del grafo.

La contribución clave es la distinción entre dos estrategias:

From-scratch consistency: verificar que el grafo entero es consistente antes de devolver cualquier resultado. Caro upfront pero garantiza corrección.

Demanded consistency: solo verificar las porciones del grafo que el query actual toca. Lazy, eficiente, pero requiere ordenamiento cuidadoso.

Salsa usa demanded consistency. Al consultar all_symbols, no verifica cada valor almacenado en el sistema, solo los que están en la cadena de dependencias de all_symbols.

A continuación se presenta una implementación simplificada estilo Adapton en TypeScript para concretizar los conceptos:

type CellId = number;
type ThunkId = number;

let currentRevision = 0;
let activeThunk: ThunkId | null = null;

interface Cell<T> {
 value: T;
 changedAt: number;
 dependents: Set<ThunkId>;
}

interface Thunk<T> {
 fn: () => T;
 value: T | undefined;
 verifiedAt: number;
 changedAt: number;
 dependencies: Set<CellId | ThunkId>;
 dependents: Set<ThunkId>;
}

const cells = new Map<CellId, Cell<any>>();
const thunks = new Map<ThunkId, Thunk<any>>();

function createCell<T>(value: T): CellId {
 const id = cells.size;
 cells.set(id, { value, changedAt: currentRevision, dependents: new Set() });
 return id;
}

function setCell<T>(id: CellId, value: T): void {
 const cell = cells.get(id)!;
 if (Object.is(cell.value, value)) return;
 currentRevision++;
 cell.value = value;
 cell.changedAt = currentRevision;
}

function readCell<T>(id: CellId): T {
 const cell = cells.get(id)!;
 if (activeThunk !== null) {
 const thunk = thunks.get(activeThunk)!;
 thunk.dependencies.add(id);
 cell.dependents.add(activeThunk);
 }
 return cell.value;
}

function createThunk<T>(fn: () => T): ThunkId {
 const id = thunks.size + 10000;
 thunks.set(id, {
 fn,
 value: undefined,
 verifiedAt: -1,
 changedAt: -1,
 dependencies: new Set(),
 dependents: new Set(),
 });
 return id;
}

function queryThunk<T>(id: ThunkId): T {
 const thunk = thunks.get(id)!;

 if (thunk.verifiedAt === currentRevision) {
 return thunk.value!;
 }

 let needsRecompute = thunk.value === undefined;
 if (!needsRecompute) {
 for (const dep of thunk.dependencies) {
 if (dep < 10000) {
 const cell = cells.get(dep)!;
 if (cell.changedAt > thunk.verifiedAt) {
 needsRecompute = true;
 break;
 }
 } else {
 queryThunk(dep);
 const depThunk = thunks.get(dep)!;
 if (depThunk.changedAt > thunk.verifiedAt) {
 needsRecompute = true;
 break;
 }
 }
 }
 }

 if (needsRecompute) {
 thunk.dependencies.clear();
 const prevActive = activeThunk;
 activeThunk = id;
 const newValue = thunk.fn();
 activeThunk = prevActive;

 if (!Object.is(newValue, thunk.value)) {
 thunk.changedAt = currentRevision;
 thunk.value = newValue;
 }
 }

 thunk.verifiedAt = currentRevision;
 return thunk.value!;
}

Son ~80 líneas que capturan el algoritmo esencial. Los frameworks reales agregan garbage collection de entradas de cache sin usar, ejecución paralela, durabilidad y detección de ciclos apropiada, pero la idea core es tracking de dependencias más early cutoff.

Aplicando esto fuera de compiladores

Los patrones de computación incremental se aplican efectivamente en contextos no-compilador. Consideremos un dashboard que agrega datos de 15 microservicios. Cada servicio se actualiza con diferente frecuencia, algunos cada segundo, otros cada hora. El dashboard computa métricas derivadas de combinaciones de estas fuentes.

Antes: cada render fetchea las 15 fuentes y recomputa todas las métricas. Latencia: 800ms.

Después: al modelar cada fuente de datos como un input cell, cada métrica como una computación tracked, y usar un framework liviano estilo Adapton, en la mayoría de los renders solo 1-2 fuentes cambian, así que solo las métricas afectadas se recomputan. La latencia baja a 30-80ms dependiendo de qué cambió.

El patrón funciona en cualquier lugar donde tengas: inputs que cambian lento, computaciones derivadas caras, y consultas repetidas. Build systems (el grafo de acciones de Bazel), frameworks de UI reactivos (señales de Solid.js), motores de hojas de cálculo, todos usan variaciones de la misma idea.

Conclusiones prácticas

Para cualquier sistema que derive datos repetidamente de inputs que cambian, vale la pena considerar si la computación incremental encaja. La inversión upfront en modelar la computación como un grafo de queries paga dividendos cuando el dataset crece. Salsa es un punto de partida natural para proyectos Rust, y los conceptos se portan a otros lenguajes (el sketch en TypeScript de arriba sirve como punto de partida). El modelo mental, inputs, funciones tracked, grafos de dependencias, early cutoff, es la parte valiosa, no ningún framework específico.

Como ejemplo concreto, reestructurar un language server alrededor de límites apropiados de queries de Salsa llevó el autocompletado de 400ms a 8ms. La computación era la misma. La única diferencia fue definir dónde estaban los límites de queries.