HomePhabricator

[SyntaxTree] Add reverse links to syntax Nodes.

Authored by eduucaldas on Oct 27 2020, 8:14 AM.

Description

[SyntaxTree] Add reverse links to syntax Nodes.

Rationale:
Children of a syntax tree had forward links only, because there was no
need for reverse links.

This need appeared when we started mutating the syntax tree.
On a forward list, to remove a target node in O(1) we need a pointer to the node before the target. If we don't have this "before" pointer, we have to find it, and that requires O(n).
So in order to remove a syntax node from a tree, we would similarly need to find the node before to then remove. This is both not ergonomic nor does it have a good complexity.

Differential Revision: https://reviews.llvm.org/D90240

Details

Committed
eduucaldasNov 5 2020, 1:33 AM
Differential Revision
D90240: [SyntaxTree] Add reverse links to syntax Nodes.
Parents
rGb715fa330dfa: [mlir] Restructure C API tests for IR
Branches
Unknown
Tags
Unknown