Problems with Recursion and Vectors in functions

I'm confused about the whole ownership thing. I'm trying to create a recursive function which traverses a collection of Structures looking for a path from one to another. In theory, it is simple, in practice I keep hitting various walls around Copy not being implemented for Strings in Structs. Or ownership of references.

My issue at the moment is "sector_list, value borrowed here after move" so I know this has to do with ownership, but I'm never changing the value only looking it up. I realize the compiler doesn't know this, but I don't know the syntax of the move keyword, and I can't find an example to use.

Any help or guidance would be GREATLY appreciated.

#[derive(Serialize, Deserialize, PartialEq, Debug, Clone, Default)]
pub struct Sector {
    name: String,
    beacontext: String,
    nebulae: String,
    number: i32,
    sectorwarps: [i32; MAX_WARPS_PER_SECTOR], //MAX_WARPS_PER_SECTOR
    port: i32, // only one port per sector, so this is just the port ID
    planets: [i32; MAX_PLANETS_PER_SECTOR], // MAX_PLANETS_PER_SECTOR
}

pub fn find_path_to_sector(sec_start: i32, sec_target: i32, sector_list: &mut Vec<Sector>, path: &mut Vec<i32>) -> Vec<i32>
{
    path.push(sec_start);
    if sector_list[sec_start as usize].get_number() == sector_list[sec_target as usize].get_number() 
    {
        path.push(sec_target);
        return path.to_vec();
    }

    for sect in sector_list
    {
        let scno: i32 = sect.get_number() ;
        if scno == sec_target
        {
            path.push(scno);
            return path.to_vec();
        }
        else 
        {
            return find_path_to_sector(
                scno, 
                sec_target, 
                sector_list, 
                path )
        }

    }

return path.to_vec();
}

Minimal repro example:

fn main ()
{
    let v = &mut vec![42];
    for x in v { // v (re)borrowed until ----+
        return drop(v); // <- not allowed    |
    } // <-----------------------------------+
}

This happens because of how the compiler interprets the usage of v within the body of the loop / iteration.

You can solve this "borrow checker limitation" by being more explicity about how you iterate; I expect the next generation borrow checker to no longer require so doing:

fn main ()
{
    let v = &mut vec![42];
    let mut v_iter = v.into_iter();
    while let Some(x) = v_iter.next() {
        return drop(v);
    }
}

An explicit reborrow at the start of the for loop also works:

fn main () {
    let v = &mut vec![42];
    for x in &mut *v {
        return drop(v);
    }
}

playground

The problem is that you want to temporarily borrow the vector while you iterate over it. Even though you already have a borrow, Rust tries to consume it rather than reborrowing because has to give consistent behaviour for generic operations, so it can't treat &mut specially.

In situations where the it expects a mutable reference, however, it does assume you want to reborrow, since it knows you will almost never want to move a mutable reference into a function. Thus, this will also work:

fn main () {
    let v = &mut vec![42];
    for x in v.iter_mut() {
        return drop(v);
    }
}

playground

2 Likes

Indeed! Using for ... in sugar on a mutable reference consumes that mutable reference instead of reborrowing it; the following (failing) code:

fn main ()
{
    let v = &mut vec![42];
    for _x in v {}
    drop(v);
}

unsugars to:

use ::core::iter::IntoIterator;

fn main ()
{
    let v = &mut vec![42];
    let mut iter = <_ as IntoIterator>::into_iter(v);
    while let Some(_x) = iter.next() {}
    drop(v);
}

And given how type inference works, the <T? as IntoIterator>::into_iter(v) resolves to T? = __typeof__(v) meaning v is moved into this call rather than reborrowed.

But if we replace the .into_iter() call with:

let mut iter = <&'_ mut _ as IntoIterator>::into_iter(v);

that is, by giving it two distinct "type/lifetime inference placeholders", then it gets to use its special casing of "lifetime placeholder" to make this call reborrow rather than move v, leading to no compilation error: Playground

So, since reborrowing suffices to solve this issue, using (as @jameseb7 suggests) for x in &mut *v {, to make sure it's reborrowing v rather than moving it, is, imho, the most elegant solution.

2 Likes