recursionrustabstract-syntax-treeself-referencerecursive-datastructures

How to create self-referential AST in Rust?


Let's imagine we have a very simple AST for programming language with only functions and calls

use std::sync::Arc;

struct Function {
    pub body: Vec<Call>
}

struct Call {
    pub function: Arc<Function> 
}

Now we want to recursively call functions:

let f = Arc::new(Function { body: vec![Call {function: f.clone()}] }) 
// Doesn't work, as we haven't created Arc yet
let mut f = Arc::new(Function { body: vec![] });
f.body.push(Call { function: f.clone() })
// Doesn't work, because Arc has immutable data

The problem can be solved using Arc<Mutex<_>> or Arc<RwLock<_>> in Call:

use std::sync::{Arc, RwLock}

struct Call {
    pub function: Arc<RwLock<Function>> 
}

And then creating with:

let f = Arc::new(RwLock::new(Function { body: vec![] }));
f.write().unwrap().body.push(Call { function: f.clone() })

But now you need to always write f.write().unwrap() or f.read().unwrap() everywhere, even though function is mutable only on construction.

Can you do something better than this?


Solution

  • Use Weak for the parent pointer. You need to do that anyway to allow for proper destruction. Then use Arc::new_cyclic():

    use std::sync::{Arc, Weak};
    
    struct Function {
        pub body: Vec<Call>,
    }
    
    struct Call {
        pub function: Weak<Function>,
    }
    
    let f = Arc::new_cyclic(|f| Function {
        body: vec![Call {
            function: Weak::clone(f),
        }],
    });