Mutable Reference Lifetime issue in recursive algorithm (and a little discussion of string comparison)

[jpangia]

New Rust programmer here,

I'm writing an algorithm in Rust to pull a mutable reference to a particular node of an AST. I'm using the syn crate for AST processing. The algorithm is looking for a function defined within a series of nested modules, whose order and names are specified by the keys parameter. I'm currently implementing it recursively. However, because I need the returned reference to be mutable, Rust's rules allow only one mutable reference to an object at a time, so the algorithm won't compile.

code:

/// walk the syntax tree of the contracts specified vector of items
/// side-effect: `keys` contains the remaining tokens of the contract's summary key that 
///              need definition
fn find_next_module<'a>(items: &'a mut Vec<Item>, keys: &mut Vec<&str>) -> Option<&'a mut Vec<Item>>
{
    let key = keys.pop().expect("should not be called on an empty keys");
    println!("processing key {}", key);
    println!("keys: {:?}", keys);
    for item in items.iter_mut() 
    {
        println!("processing item {:?}", item);
        if keys.is_empty() && 
            is_contract_definition(item.clone(), key)
        {
            //we found the last level of the key, and it is present.
            // so we don't need to do anything
            return None; 
        }
        else if let Item::Mod(modl) = item.borrow_mut()
        {
            if format!("{}", modl.ident) == key
            {
                if let Some((_, cont))= modl.content.borrow_mut()
                {
                    return find_next_module(cont, keys);
                }
            }
        }
    }

    //we didn't find the next key. return this set of items to insert the contract into
    keys.push(key);
    return Some(items);
}

compile error:

error[E0499]: cannot borrow `*items` as mutable more than once at a time
  --> src/main.rs:91:17
   |
62 | fn find_next_module<'a>(items: &'a mut Vec<Item>, keys: &mut Vec<&str>) -> Option<&'a mut Vec<Item>>
   |                     -- lifetime `'a` defined here
...
67 |     for item in items.iter_mut() 
   |                 ----- first mutable borrow occurs here
...
83 |                     return find_next_module(cont, keys);
   |                            ---------------------------- returning this value requires that `*items` is borrowed for `'a`
...
91 |     return Some(items);
   |                 ^^^^^ second mutable borrow occurs here

For more information about this error, try `rustc --explain E0499`.
error: could not compile `gen_contracts` (bin "gen_contracts") due to 1 previous error

I'm pretty sure that the problem is that the recursive call pushes a new mutable reference to the same object to the call stack, without deleting the existing mutable reference, causing the Rust borrow rules to be violated. I've tried using RefCells, but didn't have success there. I'm pretty sure there's something I'm not understanding about using RefCells.

How would one work around this? Is there a way to make the lifetime more granular so that the mut references in the recursive calls don't overlap?

Thank you!

[paramagnetic]

I believe this is this long-standing limitation in borrowck. The code is fine. You'll have to use some workaround (eg. Polonius the crab).

[steffahn]

This is indeed running into limitations of the borrow checker.

One workaround that can work here is to retrace the steps of creating the borrow, from the “top” inside the conditional branch that needs to have that longer-lived borrow to return. E.g. using this code snippet instead of the current format!("{}", modl.ident) == key statement:

if format!("{}", modl.ident) == key {
    if let Some((_, _cont)) = &mut modl.content {
        // retrace out steps to `cont` to avoid pre-polonius borrowck error
        let Item::Mod(modl) = &mut items[i] else { unreachable!() };
        let cont = &mut modl.content.as_mut().unwrap().1;
        return find_next_module(cont, keys);
    }
}

[jpangia]

Thank you! I will test this when I get the chance (may be a couple days from now)

(Also I was not aware of the let-else syntax, so thanks for introducing me to that)

[jpangia]

Sorry for the delay. "A few days" turned into three weeks. Yeesh, the life of a grad student.

Yes @steffahn , that suggested change did work. Thank you!

for anybody who comes back to this later, here's the fixed code:

/// walk the syntax tree of the contracts specified vector of items
/// side-effect: `keys` contains the remaining tokens of the contract's summary key that 
///              need definition
fn find_next_module<'a>(items: &'a mut Vec<Item>, keys: &mut Vec<&str>) -> Option<&'a mut Vec<Item>>
{
    let key = keys.pop().expect("should not be called on an empty keys");
    println!("processing key {}", key);
    println!("keys: {:?}", keys);
    for (i, item) in items.iter_mut().enumerate() //FIX: need enumerate to avoid using `item`
    {
        println!("processing item {:?}", item);
        if keys.is_empty() && 
            is_contract_definition(item.clone(), key)
        {
            //we found the last level of the key, and it is present.
            // so we don't need to do anything
            return None; 
        }
        else if let Item::Mod(modl) = item.borrow_mut()
        {
            if format!("{}", modl.ident) == key
            {
                if let Some((_, _cont)) = &mut modl.content
                {
                    // FIX: get a reference to the next list of module contents without using 
                    //  `item` so the borrow checker is happy
                    let Item::Mod(modl) = &mut items[i] else { unreachable!() };
                    let cont = &mut modl.content.as_mut().unwrap().1;
                    return find_next_module(cont, keys);
                }
            }
        }
    }

    //we didn't find the next key. return this set of items to insert the contract into
    keys.push(key);
    return Some(items);
}

[paramagnetic]

Unrelated to the issue, but what's up with the format!(…) == key dance? It seems unnecessary to allocate a new string for every comparison – shouldn't the type of modl.ident (whatever it is) implement PartialEq<str> instead?

And if it is indeed needed for some reason, you should be using modl.content.to_string() instead; there's nothing to "format" here, so that macro is unnecessary.

[jpangia]

It was a noob mistake. I didn't see that the syn::Ident type implemented PartialEq<str>, or to_string(), but I knew it implemented Display, so I took the working solution and moved on.
...
reading the Display trait docs a bit more, I see that implementing Display automatically implements ToString as well, so you get a to_string() method automatically. Today I Learned. Thanks!