Today, Rowan's logical tree shape is identical to the physical shape of the tree data structure. That's natural (you might even wonder what is the other option), but is not necessary optimal. In particular, natural tree sometimes have very wide nodes with hundreds of children. Traversing or modifying such nodes sometimes is O(len(children)), which might give poor worst-case complexity.
An alternative is to make sure that the physical shape of the data structure is always a ballaned tree. For example, we can introduce a TRANSPARENTSyntaxKind, and represent long sequences as deep, balanced trees with TRANSPARENT internal nodes.
Today, Rowan's logical tree shape is identical to the physical shape of the tree data structure. That's natural (you might even wonder what is the other option), but is not necessary optimal. In particular, natural tree sometimes have very wide nodes with hundreds of children. Traversing or modifying such nodes sometimes is
O(len(children))
, which might give poor worst-case complexity.An alternative is to make sure that the physical shape of the data structure is always a ballaned tree. For example, we can introduce a
TRANSPARENT
SyntaxKind
, and represent long sequences as deep, balanced trees withTRANSPARENT
internal nodes.