- Un recorrido por el proceso de crear una estructura de datos de texto propia para construir un editor de texto personalizado.
- Los editores de texto son muy difíciles de estructurar por funciones como la edición de archivos enormes, múltiples cursores, deshacer/rehacer y muchas otras.
- Por eso, las capacidades requeridas para la estructura de datos son las siguientes.
- Inserción/eliminación eficiente
- Deshacer/rehacer eficiente
- Posibilidad de usar codificación UTF-8
- Edición eficiente con múltiples cursores
- Gap Buffer es simple de implementar, pero es muy difícil implementar con él las funciones de deshacer y múltiples cursores.
- Rope es eficiente porque permite dividir archivos grandes en partes pequeñas para modificarlos, pero para soportar deshacer el overhead aumenta y el uso de memoria puede crecer más de lo esperado.
- Piece Table es una estructura tan eficiente que incluso fue usada en Microsoft Word, pero si se edita mucho el rendimiento puede degradarse y el uso de memoria puede aumentar para soportar deshacer.
- Piece Tree es la mejor estructura de datos para editores de texto implementada por el equipo de VSCode para resolver todas las desventajas anteriores.
- Está implementada tomando solo las ventajas de Rope y Piece Table.
- Como usa un RB Tree para conectar las piezas, sigue siendo eficiente incluso cuando hay muchas ediciones.
- Sin embargo, la versión implementada por el equipo de VSCode no es una estructura de datos inmutable, por lo que tiene una ligera ineficiencia en la función de deshacer.
- Se decidió implementar un nuevo Piece Tree que agrega inmutabilidad a la estructura de datos para resolver todos esos problemas.
- Como a un RB Tree tradicional no se le puede dar inmutabilidad, la implementación comenzó tomando como referencia el RB Tree inmutable creado por Bartosz Milewski.
- Las diferencias con la estructura implementada por el equipo de VSCode son las siguientes.
- Como son pocos los casos en que el editor debe considerar el carácter Carriage Return, no se registra CRLF por separado.
- Para depuración, se agregó una API que permite revisar el búfer completo en una forma similar a un iterador.
- Como la estructura de datos es inmutable, deshacer/rehacer resulta muy simple.
- Implementar la función de eliminación fue lo más difícil, pero al final se logró.
- La nueva estructura de datos fue publicada con el nombre de fredbuf.
2 comentarios
¡Oh! Gracias. ¡Qué información tan valiosa! Desde que empecé a usar Emacs en serio, me ha interesado mucho el editor de texto en sí. ¡También voy a leer el texto original con calma! :-)
Muchas gracias por resumirlo en detalle. Alguna vez me había preguntado cómo se implementan las estructuras de datos de un editor de texto, y veo que se usan este tipo de estructuras de datos.