tutorial - predicatebuilder c# example



Os Sintaxe de Roslyn são reutilizados? (1)

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

Ótima pergunta. Debatemos as questões que você levanta há muito, muito tempo.

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

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

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

Agora, quando você tenta colocar todas essas cinco coisas em uma estrutura de dados, imediatamente se depara com 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 torna persistente? Você não pode reutilizar um nó filho em um pai diferente, pois 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ó que é mapeado para uma posição após esse ponto é alterada. Isso torna muito difícil criar uma estrutura de dados persistente, porque qualquer edição pode alterar os trechos da maioria dos nós!

Mas no time da Roslyn nós 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 tem referências aos pais, é 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 é tipicamente sobre O (log n) do total de nós de análise na árvore.

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

Você, o usuário, só 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.

Incidentalmente, eles são chamados de "árvores vermelhas / verdes" porque eram as cores dos marcadores de 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 dos 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.

Eu estive dando uma olhada no Roslyn CTP e, enquanto ele resolve um problema semelhante à API da árvore de expressões , ambos são imutáveis, mas Roslyn faz isso de uma maneira bem diferente:

  • Expression nós de Expression não têm referência ao nó pai, são modificados usando um ExpressionVisitor e é por isso que as peças grandes podem ser reutilizadas.

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

Onde isso termina? Document ? Project ? ISolution ? A API promove uma mudança 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 tal escolha? Existe algum truque interessante que estou perdendo?





roslyn