Works in Python; (im)?possible in Rust? How to populate a nested struct with a stack?

I have two programs, the first in Rust
(rust playground) and shown below, and the second in Python shown at the end with the output that both are expected to produce. The Python program works fine and shows what I'm trying to achieve -- and how I want to achieve it; the Rust program won't compile.

Rust version (won't compile):

use anyhow::Result;
use std::{cell::RefCell, fmt, rc::Rc};

const B: i64 = -1; // list begin
const E: i64 = -2; // list end

fn main() -> Result<()> {
    let tokens = vec![
        B, 1, 2, B, 30, 40, B, 500, B, E, E, 70, B, 800, 900, E, E, 1000, E,
    ];
    assert_eq!(
        tokens.iter().filter(|&x| *x == B).count(),
        tokens.iter().filter(|&x| *x == E).count()
    );
    let expected = get_expected()?;
    let actual = parse(tokens)?;
    println!("Actual   {}", actual);
    println!("Expected {}", expected);
    assert_eq!(actual.to_string(), expected.to_string());
    Ok(())
}

fn parse(tokens: Vec<i64>) -> Result<Value> {
    let mut root: Value = 0.into(); // fake root to be overwritten
    let mut stack = vec![];
    for token in tokens {
        if token == B {
            let lst = Value::from(List::new()?);
            if root.is_int() {
                root = lst;
                stack.push(Rc::new(RefCell::new(lst)));
            } else {
                let top = stack.last().unwrap().borrow_mut();
                if let Some(sublst) = top.as_list() {
                    let mut sublst = sublst.borrow_mut();
                    sublst.push(lst); // add new list to current list
                }
                stack.push(Rc::new(RefCell::new(lst))) // make new list the current list
            }
        } else if token == E {
            stack.pop();
        } else {
            let top = stack.last().unwrap().borrow_mut();
            if let Some(sublst) = top.as_list() {
                let mut sublst = sublst.borrow_mut();
                sublst.push(token.into());
            }
        }
    }
    Ok(Value::from(root))
}

fn get_expected() -> Result<Value> {
    let mut lst = List::new()?;
    lst.push(1.into());
    lst.push(2.into());
    lst.push(Value::from(List::new()?));
    if let Some(sublst) = lst.inner().last().unwrap().as_list() {
        let mut sublst = sublst.borrow_mut();
        sublst.push(30.into());
        sublst.push(40.into());
        sublst.push(Value::from(List::new()?));
        if let Some(subsublst) = sublst.inner().last().unwrap().as_list() {
            let mut subsublst = subsublst.borrow_mut();
            subsublst.push(500.into());
            subsublst.push(Value::from(List::new()?));
        }
        sublst.push(70.into());
        sublst.push(Value::from(List::new()?));
        if let Some(subsublst) = sublst.inner().last().unwrap().as_list() {
            let mut subsublst = subsublst.borrow_mut();
            subsublst.push(800.into());
            subsublst.push(900.into());
        }
        sublst.push(1000.into());
    }
    lst.push(1100.into());
    Ok(Value::from(lst))
}

pub type Values = Vec<Value>; // For Lists

#[derive(Clone, Debug)]
pub enum Value { // The full Value has other scalar & collection types
    Int(i64),
    List(Rc<RefCell<List>>),
}

impl Value {
    pub fn as_list(&self) -> Option<Rc<RefCell<List>>> {
        if let Value::List(value) = self {
            Some(Rc::clone(value))
        } else {
            None
        }
    }

    pub fn is_int(&self) -> bool {
        matches!(self, Value::Int(_))
    }
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                Value::Int(i) => i.to_string(),
                Value::List(lst) => lst.borrow().to_string(),
            }
        )
    }
}

impl From<i64> for Value {
    fn from(i: i64) -> Self {
        Value::Int(i)
    }
}

impl From<List> for Value {
    fn from(lst: List) -> Self {
        Value::List(Rc::new(RefCell::new(lst)))
    }
}

#[derive(Clone, Debug)]
pub struct List {
    values: Values,
}

impl List {
    pub fn new() -> Result<Self> {
        Ok(List { values: Values::new() })
    }

    pub fn push(&mut self, value: Value) {
        self.values.push(value);
    }

    pub fn iter(&self) -> std::slice::Iter<Value> {
        self.values.iter()
    }

    pub fn inner(&self) -> &Values {
        &self.values
    }
}

impl fmt::Display for List {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut parts = vec!["[".to_string()];
        let mut sep = "";
        for value in self.iter() {
            parts.push(sep.to_string());
            parts.push(value.to_string());
            sep = ", ";
        }
        parts.push("]".to_string());
        write!(f, "{}", parts.join(""))
    }
}

Python version (works fine):

#!/usr/bin/env python3

B = -1 # list begin
E = -2 # list end

def main():
    tokens = [B, 1, 2, B, 30, 40, B, 500, B, E, E, 70, B, 800, 900, E,
              1000, E, 1100, E]
    assert tokens.count(B) == tokens.count(E)
    expected = [1, 2, [30, 40, [500, []], 70, [800, 900], 1000], 1100]
    actual = parse(tokens)
    print('Actual  ', actual)
    print('Expected', expected)
    assert actual == expected

def parse(tokens):
    root = None
    stack = []
    for token in tokens:
        if token == B:
            lst = []
            if root is None:
                root = lst
                stack.append(root)
            else:
                top = stack[-1]
                top.append(lst) # add new list to current list
                stack.append(lst) # make new list the current list
        elif token == E:
            stack.pop()
        else:
            top = stack[-1]
            top.append(token)
    return root

if __name__ == '__main__':
    main()

Expected output (only produced by the Python version so far):

Actual   [1, 2, [30, 40, [500, []], 70, [800, 900], 1000], 1100]
Expected [1, 2, [30, 40, [500, []], 70, [800, 900], 1000], 1100]

You have to clone non-Copy types explicitly. After fixing that, there was a borrow error due to when a RefCell guard dropped, so I explicitly dropped it earlier. (Also you input didn't match your test or comment.)

 fn main() -> Result<()> {
     let tokens = vec![
-        B, 1, 2, B, 30, 40, B, 500, B, E, E, 70, B, 800, 900, E, E, 1000, E,
+        B, 1, 2, B, 30, 40, B, 500, B, E, E, 70, B, 800, 900, E, 1000, E, 1100, E
     ];
         if token == B {
             let lst = Value::from(List::new()?);
             if root.is_int() {
-                root = lst;
+                root = lst.clone();
                 stack.push(Rc::new(RefCell::new(lst)));
             } else {
                 let top = stack.last().unwrap().borrow_mut();
                 if let Some(sublst) = top.as_list() {
                     let mut sublst = sublst.borrow_mut();
-                    sublst.push(lst); // add new list to current list
+                    sublst.push(lst.clone()); // add new list to current list
                 }
+                drop(top);
                 stack.push(Rc::new(RefCell::new(lst))) // make new list the current list
             }
         } else if token == E {

Playground.

3 Likes

Yes, sorry about the test data, I changed it midway.

Your solution works: thank you!

Now I'll try to use it with my real code...

For just this parsing and construction task, there's no real need for Rc<RefCell<...>>, and including it is making things more complicated than they need to be. (Unless, of course, you need them for some other part of your program)

fn parse(tokens: Vec<i64>) -> Result<Value> {
    let mut val: Option<Value> = None;
    let mut stack:Vec<Value> = vec![];
    for token in tokens {
        if let Some(to_insert) = val.take() {
            match stack.last_mut().ok_or(anyhow!("Stack underflow"))? {
                Value::List(lst) => { lst.push(to_insert); }
                // TODO: Other container types
                _ => { panic!("Non-container value on stack"); }
            }
        }

        val =
            if token == B {
                stack.push(Value::from(List::new()?));
                None
            } else if token == E {
                Some(stack.pop().ok_or(anyhow!("Stack underflow"))?)
            } else {
                Some(token.into())
            };
    }
    match (stack.len(), val) {
        (0, Some(v)) => Ok(v),
        (0, None) => Err(anyhow!("No value produced")),
        _ => Err(anyhow!("Unclosed container"))
    }
}
5 Likes

Thank you very much :smile:
I changed your version so I could still use push (since I need that for my real code) & it works great.
And I've stripped out the Rc<RefCell<>>s from my real code & ported your code to it and so far it appears to work, although I've quite a bit more to do.

1 Like