Parseo incremental: reparsear solo lo que cambió

Un compilador parsea un archivo una vez y puede permitirse tardar. Un editor parsea el mismo archivo después de cada pulsación, y tiene unos pocos milisegundos antes de que el usuario perciba el retardo. Esa diferencia de régimen, y no la calidad del algoritmo, es lo que mantuvo a los parsers fuera de los editores durante décadas. El parseo incremental es la idea que rompe el empate: si el árbol anterior sigue siendo válido casi entero, reconstruirlo entero es un desperdicio.

El presupuesto de una pulsación

A 60 fotogramas por segundo, un cuadro dura 16,6 ms. Dentro de ese margen el editor tiene que aplicar el cambio al buffer, recalcular el resaltado, mover el cursor y redibujar. Un parser que consuma la mitad del presupuesto es ya sospechoso; uno que consuma 40 ms convierte el editor en algo que se arrastra al escribir deprisa, que es exactamente cuando más molesta.

Ahora la aritmética. Parsear desde cero cuesta, en el mejor caso, tiempo lineal en el número de bytes: O(n). Para un archivo de 200 líneas eso son microsegundos y nadie lo nota. Para uno de 30.000 líneas —un fichero generado, un esquema, un módulo grande de C— son decenas de milisegundos por tecla. Y el resultado de ese trabajo es, casi siempre, un árbol idéntico al anterior salvo en la rama donde acabas de escribir un carácter.

Medirlo en tu propia máquina cuesta cinco líneas, y el resultado es más convincente que cualquier tabla ajena:

local function cronometrar(fn)
  local t0 = vim.uv.hrtime()
  fn()
  return (vim.uv.hrtime() - t0) / 1e6 -- milisegundos
end

local p = assert(vim.treesitter.get_parser(0))
print("primer parseo:", cronometrar(function() p:parse(true) end))
print("sin cambios:  ", cronometrar(function() p:parse(true) end))

Conviene además recordar que el parser no es el único inquilino de esos 16 ms. Compiten con él el redibujado, los diagnósticos del servidor de lenguaje, el autocompletado, las marcas extendidas de los plugins de Git y cualquier autocomando que hayas colgado de TextChangedI. Un componente que se coma el presupuesto entero no solo se vuelve lento él: vuelve lento todo lo demás, y el usuario lo percibe como un editor pesado sin saber a quién culpar.

Ese es el desperdicio que ataca el parseo incremental, cuya formulación moderna procede de la tesis de Tim Wagner sobre entornos de desarrollo incrementales y del uso de un parser GLR capaz de reutilizar fragmentos ya reconocidos. La promesa se enuncia en una línea: el coste del reparseo debe ser proporcional al tamaño del cambio, no al del archivo.

Editar el árbol antes de reparsearlo

El paso que casi todo el mundo pasa por alto es que, antes de reparsear, el árbol viejo se edita. Cuando escribes un carácter en la línea 500, todo lo que hay después se desplaza un byte. Los nodos del árbol guardan posiciones absolutas —desplazamiento en bytes y par fila-columna—, así que sin corregirlas el árbol antiguo dejaría de corresponderse con el texto y no serviría para nada.

La operación de edición recibe exactamente lo que un editor sabe decir: dónde empezó el cambio, qué extensión tenía antes y qué extensión tiene ahora. Neovim expone esa misma información en la capa de buffer:

-- Las coordenadas que alimentan la edicion del arbol
vim.api.nvim_buf_attach(0, false, {
  on_bytes = function(_, buf, _tick,
                      fila_ini, col_ini, byte_ini,
                      filas_viejas, cols_viejas, bytes_viejos,
                      filas_nuevas, cols_nuevas, bytes_nuevos)
    -- inicio del cambio, tamanio anterior y tamanio nuevo
    -- treesitter traduce esto a una edicion sobre el arbol
  end,
})

Con esos datos, el árbol se actualiza en dos movimientos. Los nodos posteriores al punto de edición desplazan sus posiciones sin tocar su forma: siguen siendo la misma función, solo que ahora empieza un byte más allá. Y los nodos que contienen el punto editado se marcan como sucios, desde la hoja afectada hasta la raíz. Ese camino, y solo ese, es lo que el parser deberá reconsiderar.

flowchart TD
E[Pulsacion en la linea 500] --> B[on bytes entrega inicio y extensiones]
B --> D[Edicion del arbol viejo]
D --> S[Nodos posteriores desplazan su posicion]
D --> M[Camino de la raiz al nodo tocado marcado como sucio]
S --> R[Reparseo]
M --> R
R --> V[Subarboles limpios reutilizados tal cual]
R --> N[Solo lo sucio se vuelve a reconocer]
V --> T[Arbol nuevo]
N --> T
style M fill:#f38ba8,color:#11111b
style V fill:#a6e3a1,color:#11111b
style T fill:#89b4fa,color:#11111b

Reutilizar subárboles con seguridad

Durante el reparseo, el parser recorre la entrada con su pila de estados y, cada vez que llega a una posición donde el árbol viejo tenía un subárbol intacto, se pregunta si puede engancharlo entero en lugar de volver a reconocer sus bytes. La respuesta es sí bajo dos condiciones: que el subárbol no solape con la región editada y que el estado del parser al llegar a él coincida con el estado que tenía la primera vez.

Esa segunda condición es la sutil. Un mismo fragmento de texto puede analizarse de formas distintas según el contexto: escribir una comilla o abrir una llave cambia el estado con el que se llega a todo lo que viene después, y entonces los subárboles siguientes dejan de ser reutilizables aunque su texto no haya cambiado ni un byte. Es la explicación exacta de un fenómeno que ya has visto: borrar una comilla al principio del archivo tiñe todo lo demás, porque el cambio no es local aunque la pulsación lo parezca.

Merece la pena ver el mecanismo con precisión. El analizador avanza con una pila de estados: en cada paso decide entre desplazar el siguiente token o reducir varios símbolos de la cima a un nodo. Cuando la gramática es ambigua en ese punto, el enfoque GLR no se rinde: bifurca la exploración y sigue varias interpretaciones a la vez, descartando las que mueren al no poder continuar. La reutilización se engancha en ese bucle: antes de leer el siguiente token, el analizador comprueba si en esa posición el árbol viejo ofrece un subárbol compatible con el estado actual de la pila, y si lo hay lo desplaza como si fuese un único token gigante. Reutilizar un subárbol de mil nodos cuesta, literalmente, lo mismo que consumir un token.

El lexer se trata igual: mantiene su propio estado, y la reutilización de tokens exige que ese estado también coincida. Cuando no coincide, el parser vuelve a leer bytes hasta reencontrar un punto donde el árbol viejo encaja de nuevo, y a partir de ahí retoma la reutilización.

local parser = assert(vim.treesitter.get_parser(0))
parser:parse()          -- solo las regiones de rango vacio: tipicamente la raiz
parser:parse(true)      -- forzar el buffer entero, puede ser lento
parser:parse({ 0, 200 })-- un rango concreto, o una lista de rangos ordenada

-- Con callback: asincrono. El primer argumento es el error, el segundo los arboles.
parser:parse(true, function(err, arboles)
  if err then return end
  vim.notify("arbol listo: " .. #arboles)
end)

Cuando la incrementalidad no ayuda

La promesa tiene letra pequeña, y conocerla explica los pocos casos en los que Treesitter sigue costando caro.

El primer caso es el cambio grande. Pegar diez mil líneas o aplicar un formateador que reescribe el archivo entero invalida casi todo el árbol: no hay nada que reutilizar y el coste vuelve a ser el de un parseo completo. Lo mismo ocurre al deshacer una operación masiva. No es un defecto, es la definición: el coste es proporcional al cambio, y ahí el cambio es todo.

El segundo es el cambio pequeño con efecto global. Ya lo has visto: abrir una comilla o borrar una llave al principio del archivo altera el estado con el que se llega a todo lo posterior. Un byte editado, un árbol entero por rehacer. Por eso la latencia de escritura no depende solo de cuánto escribes, sino de qué escribes y dónde.

El tercero son las inyecciones. Cuando un buffer contiene varios lenguajes —Markdown con bloques de código, HTML con CSS y JavaScript dentro—, Neovim no gestiona un árbol sino un árbol de árboles a través de LanguageTree. Cada región inyectada tiene su propio parser y su propio ciclo incremental, y un cambio que altere los límites de una región obliga a recalcular esa región completa. El detalle fino es que el escáner externo, si lo hay, debe serializar y restaurar su estado para que la reutilización siga siendo correcta: sin eso, un heredoc o una cadena cruda quedarían mal reconocidos tras una edición incremental.

-- Recorrer los arboles de un buffer con inyecciones.
-- for_each_tree entrega el TSTree y el LanguageTree al que pertenece.
local lt = assert(vim.treesitter.get_parser(0))
lt:parse(true)
lt:for_each_tree(function(arbol, subparser)
  local r = arbol:root()
  print(subparser:lang(), r:start(), r:end_())
end)