Teoria do editor de texto

Como estou sempre insatisfeito com os editores existentes, um projeto que sempre quis iniciar é o meu próprio editor de texto. No entanto, fazer edição de texto é um assunto sério.

Além de analisar o código-fonte dos editores de texto existentes, existe algum livro ou outro recurso (como trabalho acadêmico) sobre esse tópico? Estou interessado especialmente em algo que ensina como lidar com memory e como gerenciar a inserção de texto (se você tiver um arquivo de 100 MB e quiser adicionar um caractere na posição x , você não pode apenas memmove o enorme bloco de texto … ).

Dê uma olhada na descrição de Rob Pike do seu editor de texto Sam . Não deixe de navegar pela visão geral de alto nível e pela linguagem de comandos. Ele descreve as estruturas de análise, gerenciamento de memory e dados posteriormente no documento.

Além disso, dê uma olhada na implementação simples de expressão regular de Russ Cox. É fácil de seguir e pode abrir algumas portas fora das bibliotecas de expressões regulares existentes.

Ao longo dos anos, escrevi um bom número de diferentes editores de texto. Certamente a maneira mais simples é gerenciar uma longa seqüência de caracteres, onde você copia tudo para inserir qualquer caractere. Outras técnicas que usei incluem:

  • Representa o arquivo de texto como uma lista duplamente vinculada de linhas de texto.
  • Construa uma estrutura de dados em forma de tree (às vezes chamada de “corda” ) que começa como uma sequência sólida de caracteres, mas tem a capacidade de dividir, inserir e excluir blocos de texto sem ter que mover todo o resto do texto .

Muitos dos antigos livros de exemplo da Borland usavam um editor de texto como um exemplo tutorial. Você pode ocasionalmente ainda encontrar cópias destes em livrarias usadas para quase de graça.

Há um excelente tutorial disponível aqui que abrange muitos tópicos relevantes em um contexto mais moderno:

  • Design e Implementação de um Editor de Texto Win32

As outras respostas a essa pergunta cobrem o buffer de intervalo.

Outra cobertura moderna é a descrição de AvalonEdit

e detalhes extras de:

e há uma enorme quantidade de detalhes / conteúdo (sobre o SharpDevelop) no livro:

Promovido para responder por solicitação:

O antigo ” Software Tools in Pascal ” de Kernighan e Plaugher implementa o editor ed em uma linguagem sem strings nem pointers reais. Ele contém uma ótima visão geral das considerações de design subjacentes a qualquer editor de texto.

Um método antigo que ainda funciona é chamado de buffer de intervalo. A idéia básica é que você coloque o texto em um buffer, mas ao invés de colocar tudo em um bloco, você cria um “gap” no cursor, colocando todo o texto antes do cursor no início do buffer, e todo o texto texto após o cursor no final do buffer. A maioria das inserções ocorre no cursor, o que você pode fazer sem mover nada (até ou a menos que você transborde o buffer). Quando o usuário move o cursor, você move o texto apropriado de um lado da divisão para o outro.

Com controles típicos (cursor à esquerda, direita, cima, baixo, página para cima, página para baixo), o maior movimento com o qual você costuma lidar é uma página por vez, que normalmente é fácil de manusear um pouco mais rápido do que a repetição de um teclado. Pode, é claro, desacelerar um pouco se você tiver um arquivo realmente grande e um comando “goto line”, ou algo nessa ordem. Se você vai fazer muito disso, sem dúvida, há melhores estruturas para usar …

The Craft of Text Editing, de Craig Finseth, baseado em sua tese de mestrado, aborda esses tópicos. É grátis na web. OTOH é bem antigo e não menciona algumas idéias como cordas que eram menos práticas nos minúsculos computadores de antigamente.

Este documento compara muitas estruturas de dados que podem ser usadas para editores de texto, incluindo alguns já mencionados aqui (por exemplo, buffers de intervalo), bem como vários outros (por exemplo, tabelas de peças). O artigo é antigo, mas acredito que ainda abrange todas as principais escolhas, e compara-as bem em termos de desempenho, complexidade e sobrecarga de espaço.

Eu sei que as respostas do Stack Overflow não devem ser apenas links, mas essa ainda é a melhor fonte de informações que já encontrei para as informações solicitadas, e é muito tempo para resumir em uma resposta aqui. Caso o link fique obsoleto, procure por ” Estruturas de Dados para Sequências de Texto “, de Charles Crowley, da Universidade do Novo México.

O componente Scintilla usa um buffer dividido, ao longo da teoria explicada em um texto vinculado em sua página Scintilla e SciTE Related Sites .
A página vinculada é Estruturas de Dados em um Editor de Texto Mapeado por Bit .
O buffer de divisão provou que funciona bem mesmo com arquivos de megabytes. Usando estruturas secundárias (por exemplo, uma lista de partidas de linha) pode ajudar também.

Veja como “os profissionais” da Microsoft fazem isso:

O MS Word usa a estrutura de dados da tabela de peças. Uma matriz crescente de posições de caracteres é mantida em paralelo com uma matriz de estruturas maiores que contêm pointers para o arquivo original (texto carregado na carga do arquivo) ou para um buffer apenas de acréscimo de caracteres recém-adicionados.

O controle EDIT usado em todos os lugares no Windows não usa nenhuma estrutura de dados. O bloco de notas simplesmente usa um controle EDIT de várias linhas. Confira com um visualizador de pilha. O controle EDIT mantém apenas um buffer de quebras de linha e paradas de tabulação.

Se você for criar um editor de texto simples e não formatado no Windows, poderá subclassificar facilmente o controle EDIT para adicionar resources.

como gerenciar a inserção de texto (se você tiver um arquivo de 100 MB e quiser adicionar um caractere na posição x, você não pode simplesmente memorizar o enorme bloco de texto …).

Torne o arquivo de texto uma linked list, onde cada linha é uma input.

Bem, se você sabe que, em geral, as pessoas terão relativamente poucos pontos de inserção, você poderia manter uma matriz de pointers em seu buffer de texto original e quando o usuário tentar inserir dentro dele, “dividir” o buffer gerando outro ponteiro para o restante do buffer, fazendo o comprimento do primeiro ponteiro para que ele pare no ponto de inserção e adicionando um terceiro ponteiro para o texto a ser inserido no meio, como:

 long original text la la la ^ *^ | 2nd part 1st part 

E a estrela aponta para um novo buffer de texto onde você começa a adicionar o texto a ser inserido.

Quando você renderiza (ou em geral analisa) seu arquivo de texto, você faz um loop sobre a matriz de pointers e depois faz o seu trabalho em cada buffer. É claro que se o buffer é pequeno o suficiente, você pula a adição de uma nova parte do buffer, mas isso é apenas heurística, tente cada uma e tenha uma idéia de qual funciona melhor.

Você também pode considerar dividir o arquivo de texto em carga em vários buffers, digamos, a cada 1 MB ou mais, porque se você carregar o arquivo em um único buffer, precisará fazer um novo buffer para o texto inserido devido ao tamanho. Mais uma vez, esta é uma otimização heurística.

Intereting Posts