OCaml has been pretty common tool to write parsers for many years. Not a bad choice.
I've written parsers professionally with Rust for two companies now. I have to say the issues you had with the borrow checker are just in the beginning. After working with Rust a bit you realize it works miracles for parsers. Especially if you need to do runtime parsing in a network service serving large traffic. There are some good strategies we've found out to keep the borrow checker happy and at the same time writing the fastest possible code to serve our customers.
I highly recommend taking a look how flat vectors for the AST and using typed vector indices work. E.g. you have vector for types as `Vec<Type>` and fields in types as `Vec<(TypeId, Field)>`. Keep these sorted, so you can implement lookups with a binary search, which works quite well with CPU caches and is definitely faster than a hashmap lookup.
The other cool thing with writing parsers with Rust is how there are great high level libraries for things like lexing:
https://crates.io/crates/logos
The cool thing with Logos is it keeps the source data as a string under the surface, and just refers to a specific locations in it. Now use these tokens as a basis for your AST tree, which is all flat data structures and IDs. Simplify the usage with a type:
#[Clone, Copy]
struct Walker<'a, Id> {
pub id: Id,
pub ast: &'a Ast,
}
impl<'a, Id> Walker<'a, Id> {
pub fn walk<T>(self, other_id: T) -> Walker<'a, T> {
Walker { id: other_id, ast: self.ast }
}
}
Now you can specialize these with type aliases:
type TypeWalker<'a> = Walker<'a, TypeId>;
And implement methods:
impl<'a> TypeWalker<'a> {
fn as_ref(&self) -> &'a Type {
&self.ast[self.id]
}
fn name(&self) -> &'a str {
&self.as_ref().name
}
}
From here you can introduce string interning if needed, it's easy to extend. What I like about this design is how all the IDs and Walkers are Copy, so you can pass them around as you like. There's also no reference counting needed anywhere, so you don't need to play the dance with Arc/Weak.
I understand Rust feels hard especially in the beginning. You need to program more like you write C++, but with Rust you are enforced to play safe. I would say an amazing strategy is to first write a prototype with Ocaml, it's really good for that. Then, if you need to be faster, do a rewrite in Rust.