Roslyn SyntaxNodes são reutilizados?

124

Venho analisando o Roslyn CTP e, embora ele resolva um problema semelhante à API da árvore Expression , ambos são imutáveis, mas Roslyn o faz de uma maneira bem diferente:

  • Expressionnós não têm referência ao nó pai, são modificados usando ae ExpressionVisitoré por isso que grandes partes podem ser reutilizadas.

  • O Roslyn SyntaxNode, por outro lado, tem uma referência ao seu pai, então todos os nós efetivamente se tornam um bloco impossível de reutilizar. Métodos como Update, ReplaceNodeetc, são fornecidos para fazer modificações.

Onde isso termina? Document? Project? ISolution? A API promove uma alteração passo a passo da árvore (em vez de um botão para cima), mas cada etapa faz uma cópia completa?

Por que eles fizeram essa escolha? Há algum truque interessante que estou perdendo?

Olmo
fonte

Respostas:

181

ATUALIZAÇÃO: Esta pergunta foi o assunto do meu blog em 8 de junho de 2012 . Obrigado pela ótima pergunta!


Ótima pergunta. Debatemos os problemas que você levanta por muito, muito tempo.

Gostaríamos de ter uma estrutura de dados com as seguintes características:

  • Imutável.
  • A forma de uma árvore.
  • Acesso barato aos nós pai dos nós filhos.
  • É possível mapear de um nó na árvore para um deslocamento de caractere no texto.
  • Persistente .

Por persistência, quero dizer a capacidade de reutilizar a maioria dos nós existentes na árvore quando uma edição é feita no buffer de texto. Como os nós são imutáveis, não há barreira para reutilizá-los. Precisamos disso para desempenho; não podemos analisar novamente enormes wodges do arquivo toda vez que você pressiona uma tecla. Precisamos reexprimir e analisar novamente apenas as partes da árvore que foram afetadas pela edição.

Agora, quando você tenta colocar todas essas cinco coisas em uma estrutura de dados, você imediatamente encontra problemas:

  • Como você constrói um nó em primeiro lugar? O pai e o filho se referem um ao outro e são imutáveis, então qual deles é construído primeiro?
  • Supondo que você consiga resolver esse problema: como você o mantém persistente? Você não pode reutilizar um nó filho em um pai diferente, porque isso envolveria dizer ao filho que ele tem um novo pai. Mas a criança é imutável.
  • Supondo que você consiga resolver esse problema: quando você insere um novo caractere no buffer de edição, a posição absoluta de cada nó mapeado para uma posição após esse ponto muda. Isso torna muito difícil criar uma estrutura de dados persistente, porque qualquer edição pode alterar os intervalos da maioria dos nós!

Mas na equipe de Roslyn, rotineiramente fazemos coisas impossíveis. Na verdade, fazemos o impossível mantendo duas árvores de análise. A árvore "verde" é imutável, persistente, não possui referências pai, é construída "de baixo para cima" e cada nó rastreia sua largura, mas não sua posição absoluta . Quando uma edição acontece, reconstruímos apenas as partes da árvore verde que foram afetadas pela edição, que geralmente são sobre O (log n) do total de nós de análise na árvore.

A árvore "vermelha" é uma fachada imutável construída ao redor da árvore verde; é construído "de cima para baixo" sob demanda e jogado fora em todas as edições. Ele calcula as referências dos pais, fabricando-as sob demanda conforme você desce pela árvore a partir do topo . Ele fabrica posições absolutas calculando-as a partir das larguras, novamente, à medida que você desce.

Você, o usuário, apenas vê a árvore vermelha; a árvore verde é um detalhe de implementação. Se você observar o estado interno de um nó de análise, verá que há uma referência a outro nó de análise de um tipo diferente; esse é o nó da árvore verde.

Aliás, essas são chamadas de "árvores vermelhas / verdes" porque essas eram as cores dos marcadores do quadro branco que usamos para desenhar a estrutura de dados na reunião de design. Não há outro significado para as cores.

O benefício dessa estratégia é que obtemos todas essas grandes coisas: imutabilidade, persistência, referências aos pais e assim por diante. O custo é que esse sistema é complexo e pode consumir muita memória se as fachadas "vermelhas" ficarem grandes. No momento, estamos fazendo experimentos para ver se podemos reduzir alguns dos custos sem perder os benefícios.

Eric Lippert
fonte
3
E para abordar a parte de sua pergunta sobre IProjects e IDocuments: usamos um modelo semelhante na camada de serviços. Internamente, existem os tipos "DocumentState" e "ProjectState" que são moralmente equivalentes aos nós verdes da árvore de sintaxe. Os objetos IProject / IDocument que você obtém são as fachadas dos nós vermelhos. Se você observar a implementação do Roslyn.Services.Project em um descompilador, verá que quase todas as chamadas são encaminhadas para os objetos de estado interno.
Jason Malinowski
@ Eric desculpe pela observação, mas você está se contradizendo. The expense and difficulty of building a complex persistent data structure doesn't pay for itself.ref: stackoverflow.com/questions/6742923/… Se você tinha objetivos de alto desempenho, por que o tornou imutável em primeiro lugar? Existe apenas outra razão além das óbvias? por exemplo, mais fácil tornar o thread-safe, raciocinar sobre etc.
Lukasz Madon
2
@lukas Você está tirando essa citação do contexto. A frase anterior era "Porque, quando você olha para operações que normalmente são feitas em cadeias de caracteres em programas .NET, é de todo modo relevante dificilmente pior criar uma cadeia de caracteres totalmente nova". OTOH, quando você olha para operações que normalmente são feitas em uma árvore de expressão - por exemplo, digitando alguns caracteres no arquivo de origem - é significativamente pior criar uma árvore de expressão totalmente nova. Então eles constroem apenas metade disso.
Timbo
1
@lukas Meu palpite: Dado que Roslyn deve operar em threads de segundo plano, a imutabilidade permite que vários threads analisem o mesmo código fonte ao mesmo tempo, sem se preocupar com a alteração quando o usuário pressionar uma tecla. Em resposta à entrada do usuário, as árvores imutáveis ​​podem ser atualizadas sem interromper as tarefas de análise em execução. Então, imagino que o principal objetivo da imutabilidade é facilitar a escrita de Roslyn (e talvez mais fácil para os clientes usarem).
Qwertie
3
@lukas As estruturas de dados persistentes são mais eficientes do que copiar, quando a estrutura de dados é geralmente muito maior do que as alterações nela. Seu ponto, se você tiver um, está perdido em mim.
Qwertie