- Um processo de criar a própria estrutura de dados de texto para fazer um editor de texto próprio.
- Editores de texto são muito difíceis de estruturar por causa de recursos variados, como editar arquivos enormes, múltiplos cursores e desfazer/refazer.
- Por isso, as funcionalidades exigidas da estrutura de dados são as seguintes.
- inserção/remoção eficientes
- desfazer/refazer eficientes
- suporte ao encoding UTF-8
- edição eficiente com múltiplos cursores
- O Gap Buffer é simples de implementar, mas é muito difícil implementar recursos de desfazer e múltiplos cursores.
- Rope é eficiente porque permite modificar arquivos grandes dividindo-os em partes menores, mas para o recurso de desfazer o overhead é grande e o uso de memória pode aumentar mais do que o esperado.
- Piece Table é uma estrutura eficiente a ponto de ter sido usada no Microsoft Word, mas se houver muitas edições o desempenho pode cair e o uso de memória pode aumentar por causa do desfazer.
- Piece Tree é a melhor estrutura de dados para editores de texto, implementada pela equipe do VSCode para resolver todas as desvantagens acima.
- Ela foi implementada escolhendo apenas as vantagens de Rope e Piece Table.
- Como usa uma RB Tree para conectar os fragmentos, continua eficiente mesmo com muitas edições.
- Porém, a versão implementada pela equipe do VSCode não é uma estrutura de dados imutável, então há uma pequena ineficiência no recurso de desfazer.
- Foi decidido implementar uma nova Piece Tree que resolve todos os problemas adicionando imutabilidade à estrutura de dados.
- Como uma RB Tree tradicional não pode receber imutabilidade, a implementação começou usando como referência a RB Tree imutável implementada por Bartosz Milewski.
- As diferenças em relação à estrutura implementada pela equipe do VSCode são as seguintes.
- Como há poucos casos em que o editor precisa considerar caracteres Carriage Return, não se registra CRLF separadamente.
- Foi adicionada uma API que permite inspecionar o buffer inteiro em um formato semelhante a um iterador para depuração.
- Como a estrutura de dados é imutável, desfazer/refazer fica muito simples.
- Implementar o recurso de remoção foi o mais difícil, mas no fim deu certo.
- A nova estrutura de dados foi publicada com o nome de fredbuf.
2 comentários
Oh! Obrigado. Que informação preciosa! Desde que comecei a usar o Emacs de verdade, passei a me interessar muito pelo próprio editor de texto. Também vou ler o original com calma! :-)
Obrigado pelo resumo detalhado. Eu já tinha me perguntado pelo menos uma vez como a estrutura de dados de um editor de texto é implementada, e então é esse tipo de estrutura de dados que é usado.