how the tree transformations works?

# how the tree transformations works?

• lundi 5 mars 2012 18:50

in the project overview says that in tree modifications, underlying nodes are reused but how exactly does this works.

when one modify a tree, lets say replacing a node, the root of the resulting tree must be non Equal to the original root, because it's the root of a different tree, and the children of the original root must be different from the children of the new root because they are children of differents parents and, recursively, all nodes of the original tree must be different from the new one.

i suppose that "reuse" doesn't mean share, so i'd like to know what it means

### Toutes les réponses

• mardi 6 mars 2012 20:35

Well the tree's are immutable in Roslyn, which means that none of their values or references can change. So when you modify an immutable structure you're usually actually creating a new one. But when you create a new tree you only need to create the new node itself and all of it's parents (O(logN)). All other leafs and branches of that tree can be the exact same instance and therefore "reused".

For example:

```      A           (A)
/ \          / \
B   C  ->   (B)  C
/            / \
D            D  (E)
```

If you insert a new node E as a child of B you must create threw new nodes, E, B and A. Where B and A are identical except for their new children. C and D are "reused".

• mardi 6 mars 2012 20:39

Sorry my ascii art looked soo good before it got hosed by the formatter :-/
• mercredi 7 mars 2012 00:46

i think you are forgetting that all nodes have a parent reference. if c were the same on both trees, then it would have two differents parents: A and (A).

when i read the project overview i thought exactly the same, but as i started to use the api's i saw that all syntax nodes had a parent reference so this could not work. that's the reason of this question. thanks anyways. if you find something  out about this please let me know.

Ernesto

• vendredi 9 mars 2012 15:32

I think Justin is not forgetting that, that's how the code actually looks. But what he didn't tell you is that the nodes that you see when working with Roslyn are actually just a thin wrapper around another set of nodes.

So, you have one set of nodes (called “green”) that don't have any references to their parents and so they are reusable. Then there is another set of nodes (“red”), that are wrappers around the green nodes and they contain the Parent references. And because of that, they are not reusable.