How to write recursively structured data

I have an fltk-rs Tree which I'm trying to write out as text.

Given, a tree that looks like this:

Group1
    Child1
    Child2
    Group1.1
        Child4
Group2
Group3
    Child5

I am trying to populate a collection of Values like this (each Value is either a Value::List or Value::Table):

List1:List
   Group1:Table
      List2:List
         Child1:Table
         Child2:Table
      Group1.1:Table
         List3:List
            Child4:Table
   Group2:Table
   Group3:Table
      List4:List
         Child5:Table

In Python this is easy using a stack and recursive functions since Python uses object references so saying 'append to the last item on the stack' and 'push the current item (i.e., an object reference to the current item)' onto the stack are easy.

But in Rust, I'm stuck.

It's perfectly fine and possible to create recursive functions and data structures in Rust. Do you have some concrete code that you tried and didn't work?

I know Rust supports recursion, but the problem I have is maintaining a stack of Values which I want to be in effect references to the actual values so that given a root List and a stack with that root as its first item, I want to say add a new item to the List referred to by the last item on the stack. And also to put that last item itself on the stack. I've tried & and Rc but to no avail.

I still don't understand what you mean. Please share actual code. You don't generally need either references (at least not shared references) or Rc for building a collection if it's a tree (i.e. there are no cycles or multiple parents for a given child).

Here's an example of recursively building up a data structure, but I really don't know what exactly you are looking for.

1 Like

It is true that a type (e.g. List) cannot have fields or alternativies that of that same type or of types that contains that same type, since that would lead to infinite recursion giving an infinitely large type. But they can contain owernship of a separately allocated List, e.g. a Box<List> or a Vec<List>. It is also possible to contain a borrowed reference (e.g. &List), but then your type is a referencing type and you need to keep track of lifetimes (and something else has to own the things you borrow).

What I do in Python and which I can't figure out how to do in Rust is essentially this:

stack = [] # a stack is just a list
stack.append(stack) # now its first element is itself
# stack == [stack]
if len(stack) == 0:
    parent = stack
else:
    parent = stack[-1] # last one
lst = []
parent.append(lst)
# stack == [stack[lst]]
stack.append(lst)
# stack == [stack[lst], lst]

And at the end I have a stack with one item which contains all the others.

You need to use Box. Here it is described at length, how to make recursive data structures in Rust Box<T> Points to Data on the Heap and Has a Known Size - The Rust Programming Language

You need interior mutability (e.g. RefCell) and reference counting (e.g. Rc) for creating such a self-referential, multiple ownership structure. But it doesn't look like you need all of this for simply creating a tree. Is there a reason you are creating an explicit stack and push it onto itself? There are far simpler approaches (both recursive and iterative) for building up a tree of objects.

E.g., here is a literal translation of your code, but as it's predictable, it's very non-idiomatic:

#[derive(Clone)]
enum Value {
    Leaf,
    List(Rc<RefCell<Vec<Value>>>),
}

impl Value {
    fn new_leaf() -> Value {
        Value::Leaf
    }
    
    fn new_list() -> Value {
        Value::List(Rc::new(RefCell::new(Vec::new())))
    }
    
    fn push(&self, child: Value) {
        if let Value::List(list) = self {
            list.borrow_mut().push(child);
        }
    }
    
    fn last(&self) -> Option<Value> {
        if let Value::List(list) = self {
            list.borrow().last().cloned()
        } else {
            None
        }
    }
}

fn main() {
    let stack = Value::new_list();
    stack.push(stack.clone());
    
    let parent = stack.last().unwrap_or_else(|| stack.clone());
    let lst = Value::new_list();
    
    parent.push(lst.clone());
    stack.push(lst);
}
3 Likes

Thanks for your help and ideas.

I finally solved it by getting rid of the stack entirely, and passing the list down recursively.

This did lead to one problem. When I did: parent_lst.push(track) in a loop, I built this structure track by track: [], [(T 1)], [(T 1) (T 2)], [(T 1) (T 2) (T 3)], etc. I solved it by adding a push_or_combine() method to the underlying collection's API. So now the calls are parent_lst.push_or_combine(track) and this builds: [], [(T 1)], [(T 1 2)], [(T 1 2 3)], etc.

Here's the relevant code:

fn save_uxf(&mut self) -> Result<()> {
    let (group_tclass, track_tclass, history_tclass) = make_tclasses();
    let mut uxo = uxf::Uxf::new("TLM 2", "");
    uxo.add_tclass(group_tclass.clone());
    uxo.add_tclass(track_tclass.clone());
    uxo.add_tclass(history_tclass.clone());
    let parent_lst = uxo.value_mut();
    if let Some(item) = self.track_tree.first() {
        self.write_tree_uxf(parent_lst, &item, &group_tclass, &track_tclass);
    }
    // elided lines saving history
    uxo.write_format(&self.filename.to_string_lossy(), &uxf::Format::new(2, 240, Some(3)))
}

fn write_tree_uxf(&mut self, parent_lst: &mut uxf::Value, item: &fltk::tree::TreeItem, group_tclass: &uxf::TClass, track_tclass: &uxf::TClass) {
    for i in 0..item.children() {
        if let Some(child) = item.child(i) {
            let tid = unsafe { child.user_data::<TrackID>() };
            if let Some(tid) = tid { // Track
                if let Some(track_item) = self.track_for_tid.get(&tid) {
                    let filename: uxf::Value = track_item .filename .to_string_lossy() .to_string().into();
                    let secs: uxf::Value = track_item.secs.into();
                    let mut track = uxf::Value::new_table(track_tclass.clone());
                    track.push(filename).unwrap();
                    track.push(secs).unwrap();
                    parent_lst.push_or_combine(track).unwrap();
                }
            } else { // Group
                let label = child.label().unwrap();
                let mut group = uxf::Value::new_table(group_tclass.clone());
                group.push(label.into()).unwrap();
                let mut child_lst = uxf::Value::new_list();
                self.write_tree_uxf(&mut child_lst, &child, group_tclass, track_tclass);
                group.push(child_lst).unwrap();
                parent_lst.push(group).unwrap();
            }
        }
    }
}