What is the best way to implement a tree that can be traversed up and down from any node?
Specifically, I'm writing a name resolution pass for a compiler, and I'm tracking scopes. I currently have a Scope struct like this:
pub struct Scope {
parent: Option<Box<Scope>>,
decls: HashMap<String, NodeId>,
}
but there are two issues with it as it is:
- The
Box<Scope>forparentmeans that each child node will have a copy of the parent from when the child was created, not a reference to one canonical parent. - I need to be able to access all the child scopes for a node from that node.
Unfortunately, this is one of the few places where in my experience Rust doesn't shine. I think the solution might involve an "arena" of scopes, which I've tried to implement as so:
#[derive(Debug, Default)]
pub struct ScopeArena {
scopes: Vec<Scope>,
}
impl ScopeArena {
pub fn new() -> Self {
Self::default()
}
pub fn new_scope(&mut self, parent: Option<ScopeId>) -> ScopeId {
let id = ScopeId(self.scopes.len());
self.scopes.push(Scope::new(id, parent));
id
}
pub fn get(&self, id: ScopeId) -> Option<&Scope> {
if id.0 < self.scopes.len() {
Some(&self.scopes[id.0])
} else {
None
}
}
pub fn get_mut(&mut self, id: ScopeId) -> Option<&mut Scope> {
if id.0 < self.scopes.len() {
Some(&mut self.scopes[id.0])
} else {
None
}
}
}
#[derive(Debug, Copy, Clone)]
pub struct ScopeId(usize);
#[derive(Debug)]
pub struct Scope {
id: ScopeId,
parent: Option<ScopeId>,
children: Vec<ScopeId>,
decls: HashMap<String, NodeId>,
}
impl Scope {
fn new(id: ScopeId, parent: Option<ScopeId>) -> Self {
Self {
id,
parent,
children: vec![],
decls: HashMap::new(),
}
}
/// **Panics if name already exists.**
pub fn put(&mut self, name: String, id: NodeId) {
assert!(self.decls.insert(name, id).is_none());
}
pub fn get(&self, arena: &ScopeArena, name: &str) -> Option<NodeId> {
match self.decls.get(name) {
Some(decl) => Some(*decl),
None => {
if let Some(parent) = self.parent {
arena.get(parent).unwrap().get(arena, name)
} else {
None
}
}
}
}
pub fn exists(&self, arena: &ScopeArena, name: &str) -> bool {
self.get(arena, name).is_some()
}
}
But I'm not sure if this is the best way to implement this. Is there a simpler way to implement this that will still satisfy the borrow checker? Thank you!
Maybe you can keep track of where you are textually, and only ever navigate from the root. Maybe you want to just treat it as a full graph and do something like 