Bi-direction relationships a'la Roslyn Red/Green trees

[nathanwinder]

This is a pretty big feature. Is this something you would consider? I've spent a fair amount of time studying the implementation and reproducing more generic versions of it and would be willing to make some contributions if this is a direction the project is heading.

[AArnott]

Yes, I've wanted that as well. This project already offers this, but in a slightly different way that produces much less GC pressure: it uses structs for the red tree. This comes with some trade-offs (e.g. no automatic polymorphism) but we use the code generation to make conversion between types super easy. You can check out the ProjectTree tests that demonstrate this.

What do you think?

At the time I wrote this feature, I talked to the Roslyn folks about it. They mentioned they had (IIRC) 3 different varieties of red/green trees, and this was one of them. Again IIRC, they chose to have 3 varieties both because of evolution of thought and because they each have their own pros/cons so different answers apply to unique scenarios.

[nathanwinder]

Ok, so if I'm following this all ancestor access is relative a common ancestor or "root". Rooting a node makes that node the common ancestor "embedding" it so that you can traverse down and back up without having to maintain a reference to the root. But traversing the ancestors is computationally "heavy" as it either descends the tree from the root or uses the roots look-up table. To reduce the computational load you probably want to scope operations by Rooting at an appropriate level in the tree to avoid scanning a huge tree if you only need to manage a small scope. You use WithRoot to move the scope back to a broader or original root scope. Any time a rooted node is mutated the "Red" spine is rebuilt for you so you don't have to manage the unzip/rezip of the ancestors. You can then use the Root property to get to the new root. You can move back and forth between rooted and un-rooted depending on the operations you are performing and how you want them to affect the tree. This requires that the developer have a pretty solid grasp on the impact of operations in these two modes to get the best performance and use out of the pattern. Probably a steep learning curve for the average .NET developer. Is my assessment of this implementation correct?

[AArnott]

That sounds about right. Except I wouldn't typically worry to operate at a smaller scope (i.e. subtree). The full tree's lookup dictionary should be allowed to be built up, and is purged incrementally (IIRC) as you modify the tree, just like a sub-tree would. Except that by operating at the full tree, when you're done, the cache is already built up.
There are of course cases where you can make things extremely efficient by working from leaf to root, for example, even before you attach the Rooted structure. But I would make such optimizations only when you have a pretty good idea that it will matter.