TreeView refresh Is Broken When Nodes Are Reparented

[tsmaeder]

Bug Description:

The refresh in TreeView contributed by extensions is broken in the case of node being reparented. In order to reproduce this, you can use the test extension attached to #12088

Steps to Reproduce:

1. Open the Test DnD View as per the lined PR
2. Drag "bb" on "aaa"
3. Drag "bb" on "b"
4. Observe: Theia goes into an endless loop.

Additional Information

• Operating System:
• Theia Version:

[tsmaeder]

The trouble arises from the fact that the tree infrastructure assumes that a node with a certain ID can only exist once inside the tree. That is true most of the time, but for example when we create a TreeNode from a contributed TreeViewItem, we use the item's id as the TreeNode .id. When we now move an item "higher up" in the tree, we can have situations where we first "add" the item to the tree in the new position, then later detect that the item has been removed from the original position and then "remove" the item from the tree. So while the item is still in the tree of TreeNodes, it's not going to be found when someone does Tree.getItem(id). There are other, even worse scenarios where the parent chain is not consistent with the children relationship: you can end up with an endless loop when trying to enumerate the tree items for an update of the widget with a TreeIterator.
I believe the trouble ultimately stems from the fact that we're assuming that we can assert certain invariants, when, in fact, they are outside of our control. A "Tree" is a relationship between domain objects. That relationship can change in unexpected ways and timings, since we're updating the tree asynchronously. Just imagine this: we are asking the domain model (the "tree") for the children of a, which includes b and c. Then we ask the domain model for the children of b, and it may again include c. If you think of the "domain model" as "the file system", the user may have moved the file in between the two async calls asking for the children of a and b respectively.
Besides, there are many relationships which are not trees, which still can be still be shown in a tree widget: a DAG can be shown as a tree if we relax the requirement of a domain element only occurring once in the tree. A generalized directed graph can be shown if the tree is lazy: if there is a circle, you will just endlessly be able to expand the circular path, but the widget won't crash (JFace trees in Eclipse IDE do work like that).
All that leads me to the conclusion that we should separate the domain model tree (aka "files and directories") from the implementation of a widget that can show those domain object trees.

[tsmaeder]

That leads to a bunch of followup questions: are selections made up of domain objects or tree nodes? For "focus" it's pretty clear it has to be tree nodes, because if we should the same domain object twice, we still want keyboard actions to only work on one node.
What's the policy for preserving selections across tree updates? If we move a domain object to a different root, do we keep it selected? If the same domain object occurs more than once, how do we tell which one is the moved one and should be selected? Etc. etc.

[tsmaeder]

I also think separating the domain layer from the tree layer would reduce our use of inheritance in favor of composition. For example, we have CallHierarchyTree, SourceTree, FileTree, MarkerTree and PluginTree all extending TreeImpl. Inheritance is a form of tight coupling and makes it harder to make changes with confidence. We should reduce it if we can.

[paul-marechal]

All that leads me to the conclusion that we should separate the domain model tree (aka "files and directories") from the implementation of a widget that can show those domain object trees.

I also think separating the domain layer from the tree layer would reduce our use of inheritance in favor of composition. For example, we have CallHierarchyTree, SourceTree, FileTree, MarkerTree and PluginTree all extending TreeImpl. Inheritance is a form of tight coupling and makes it harder to make changes with confidence. We should reduce it if we can.

Something tells me working with VS Code's TreeView API has given you ideas :)

I'd be curious to understand what is required from trees in Theia compared to what an API like VS Code proposes.

I am all for a composable tree widget implementation: Behavior should be contributed via objects we pass when creating the tree, such as some TreeDataProvider<T>, DragAndDropController<T>, etc... This pattern can be extended to rendering should we want to allow developers to customize that.

[tsmaeder]

Something tells me working with VS Code's TreeView API has given you ideas :)

Well, those ideas are actually 20 years old 🤷, straight from good old Eclipse. Where do you think the VS Code folks got it from? What I did notice is that there seems to be a lot of complexity around trees which might not be necessary.

[tsmaeder]

Also related to refresh behaviour (not getting rid of stale nodes): #10404

[paul-marechal]

What I did notice is that there seems to be a lot of complexity around trees which might not be necessary.

Agreed, I've seen a fair amount of people grind their teeth against Theia's trees. I struggle with the API too to be honest.