how the tree transformations works?

Question

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

Answer 1

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".

Answer 2

Sorry my ascii art looked soo good before it got hosed by the formatter :-/

Answer 3

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

Answer 4

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.

You can read more about this in these answers on Stack Overflow by Eric Lippert:

• Code diff using Roslyn CTP API
• Circular reference in same assembly a bad thing?

An interesting consequence of this is that, in extreme, you could have something like O(2^n) of red nodes for just n green nodes (assuming a binary tree). But I think that's not a very likely situation in Roslyn.