# Mutable Syntax Tree Discussion

Attedees: Lukas Wirth, Wilfred Hughes, David Richey, and David Barsky

Main issues:
- Iteration invalidation issues (can't iterate while mutating things)
- Usage today: iterate to find all the things you want, pluck out the things you want to modify into a `Vec`, and reinsert. Usability sucks; requires more iteration than needed.
- The mutable syntax tree stuff forces a doubly-linked list into Rowan, which is wildly slow.
- By default, all syntax tree are immutable.
- https://docs.rs/rowan/latest/rowan/cursor/struct.SyntaxNode.html#method.clone_for_update causes a full, deep clone of the syntax tree, marks it as mutable, and diffs. We then reparse into to a immutable syntax tree.
- In theory, it should be possible to do this without mutation.
- everything that has `clone_for_update` needs to go.

Downsides of current Rowan:
- all access is `O(syntax_tree_length)`, BiomeJS's rowan fork as `O(1)`
- BiomeJS's (Rome) has proper slots with a better trivia model as well

What should we move to?

- Someone moved to the snippet handling to the mutable syntax tree in the assist code.
- Currently, use the `make` API until everything we need in the assists. Longer-term,

Discussions on prior approaches:
- https://hackmd.io/@ddbits/Bkuj3SmwR (more relevant for syntax tree replacement: one approach to replace the mutable syntax tree).
- Not all usages of the mutable syntax tree today can be handled by the `make` API.
- https://hackmd.io/@ddbits/SkTGq1vp6

Things needed to fully replace Rowan:
- Change the grammer, as there are constraints on what a syntax node might look like.
- Biome has ~four kinds (list node, general nodes with very specific layouts)
- Adjust the parser to handle the new biome-esque parser.
- Fixing up the code generation

# Takeways on Required Work

Complaints:
- Mutable syntax tree is the root of all evil because it forces a double-linked list.
- fixing trivia model would be nice, but a thing that can happen more easily *after*.

Work to fix the current state:
- First, try to remove all usage of `clone_for_update`, try and move usage to the `make` API. For things that can't be moved over to `clone_for_update`, consider the approach in https://hackmd.io/@ddbits/Bkuj3SmwR as the "more powerful" approach.
- Once this is done, we can replace rowan with either Biome's fork or whatever.

## Aside on event-based Parsers

https://rust-lang.zulipchat.com/#narrow/stream/185405-t-compiler.2Frust-analyzer/topic/parse.20design/near/452015675

## Macro Expansion

- Currently quadratic, but worse in rust-analyzer.
- When macros are expanded, there's a special token tree that is just the input. when we do exapnsion, we start consuming this token tree. whenever we have a macro fragment, we take the remaining token tree buffer into a parser input. constantly reparse for every fragment.
- if we fail, backout, try again. the tokenization of token tree happens on every branch. constantly chip away at the token tree buffer.
- this causes decl macro expansion to be really expensive and slow. requires changing the interface.
- macro expansion needs a bunch of cleanup, on Lukas' roadmap.
- https://github.com/rust-lang/rust-analyzer/blob/d32e60467f4be004a30b52c6c7de73463e9a64ea/crates/mbe/src/lib.rs#L357-L414

## New Trait Solver

New trait solver

- https://github.com/rust-lang/rust/blob/master/compiler/rustc_type_ir/src/interner.rs
- `SliceLike` is problematic
- If salsa can clean up `Copy` intern values, it should be fine.
- Today, rust-analyzer does Arc-based interning for chalk's type-ir which requires `Clone` for interned things.
- The new trait solver appears to require *Copy* for interned values (e.g., references) and slice-likes
- New Salsa needs to be able to handle interned value and hand out references to said interned values and somehow do garbage collection.
- Alternatively, the copy requirements on interned things for the new trait solver needs to go away.
- https://github.com/salsa-rs/salsa/blob/master/tests/tracked_fn_on_interned.rs