rust-analyzer / rowan

Apache License 2.0
697 stars 57 forks source link

Use variable length encoding variable length array for GreenNode #33

Closed CAD97 closed 4 years ago

CAD97 commented 4 years ago
ArcGreenNode      8
GreenToken        32
OwnedGreenElement 40
GreenElementRef   16

SyntaxNode    8
SyntaxToken   16
SyntaxElement 24

The layout of a GreenNode:

// align(u64)
head: {
    text_len: TextUnit (u32)
    kind: SyntaxKind (u16)
    child_count: u16
}
tail: [u64; dyn]
// 0usize, ArcGreenNode (1 usize tag (padded to u64), 1 usize data (padded to u64))
// 1usize, GreenToken (1 usize tag (padded to u64), 4 u64 data)

ArcGreenNode is required so that Drop does the right thing for GreenNode. GreenNode is currently Sized according to rustc, and should probably be made ?Sized via making the tail an extern type once that is stable.

The code quality is very proof-of-concept. I'm fairly confident it does the right thing, but it could use some review and proper organization before production use.

CAD97 commented 4 years ago

TL;DR: this is even messier than #32 but has a better chance at improving memory usage at least.

CAD97 commented 4 years ago

I put TODOs inline for where I mentioned maybe switching to direct FAM indexing. I also added a silly workaround for the reverse iteration to restore functionality without changing the interface.

CAD97 commented 4 years ago

I hooked this up to ra and got

test result: FAILED. 2 passed; 198 failed; 0 ignored; 0 measured; 0 filtered out

so something's messed up, obviously.

CAD97 commented 4 years ago

I don't really have the resources to debug this, and the boxed/deduped tokens approach will hopefully make this unnecessary, so I'm going to let this PR sit idle for a bit while I try out that approach.

CAD97 commented 4 years ago

Closing this as the approach of boxing tokens makes this code much simpler and less error-prone.