How to create self-referential AST in Rust?-CodePudding

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?

CodePudding user response：

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),
    }],
});