5

Every now and then, I run into the same issue with borrowing (or not borrowing) mutable variables inside a loop, and I finally sat down and compiled a minimal example. As a result, the code is a little silly, but it is the shortest version that I could come up with that highlights the problem:

struct Association {
    used: bool,
    key: usize,
    value: String,
}

impl Association {
    fn new(key: usize, value: &str) -> Self {
        Association{used: false, key: key, value: value.to_string()}
    }
}

fn find_unused<'a>(data: &'a mut Vec<Association>) -> Option<&'a String> {
    for k in 0.. {
        for a in data {
            if a.key == k && !a.used {
                a.used = true;
                return Some(&a.value);
            }
        }
    }
    None
}

fn main() {
    let mut assoc = vec![
        Association::new(7, "Hello"),
        Association::new(9, "World")
    ];

    println!("{}", find_unused(&mut assoc).unwrap());
    println!("{}", find_unused(&mut assoc).unwrap());
}

This will fail with an error because data was moved before. If I borrow it instead, it will fail because it was borrowed before. I would like to understand exactly what is happening and how to solve it in general. In particular, I do not want to change the structure of the code, even if it is silly. I do not want to implement a workaround, because this is just a minimal example: Please assume that the nesting of the loops is the "right" way to do it, even if it is utterly silly here, which it definitely is.

I would only like to know how to communicate to the borrow checker that what is happening here is actually ok. I know of one way to do this:

fn find_unused<'a>(data: &'a mut Vec<Association>) -> Option<&'a String> {
    for k in 0.. {
        for j in 0..data.len() {
            if data[j].key == k && !data[j].used {
                data[j].used = true;
                return Some(&data[j].value);
            }
        }
    }
    None
}

This compiles without error and works as intended. In my naïve understanding, there should be a way to express the above with iterators instead of indexing, and I would like to know how that would be done.

5
  • better code play.integer32.com/…
    – Stargateur
    Dec 4, 2021 at 18:57
  • 2
    Dear @Stargateur, please note my disclaimer and assume that code restructuring is not the solution, even if it absolutely works for the minimal example. Understand that this is not actually the code I am writing, and restructuring in this fashion will not always be feasible. I did play around with non-lexical lifetime support enabled on the nightly channel, but at least I can't make it work with that feature enabled either. Dec 4, 2021 at 19:14
  • you are already using NLL, read twice the answer of shepmaster, it's a current limitation of the current NLL implementation. Try -Zpolonius. On the solution I give it was just to help you there is a way using iterator, you can't complain if you didn't create a minimal reproducible example that really show your use case. I'm not a magician.
    – Stargateur
    Dec 4, 2021 at 19:21
  • @JeskoHüttenhain I'm not sure enough to post an answer, but I had a similar situation recently and stumbled across: github.com/rust-lang/rust/issues/51526 which matched my code well enough. Seems like conditionally returning a borrow from a loop is specifically the issue, it doesn't know to end the loop's borrow. (And I would guess the indexing version works since data is not held borrowed.) But, ultimately I don't know NLL enough to say for sure.
    – GManNickG
    Dec 5, 2021 at 7:02

1 Answer 1

0

The behavior you want is possible if you:

Keeping the rest of your code the same and focussing on this part, but with the return commented out:

fn find_unused<'a>(data: &'a mut Vec<Association>) -> Option<&'a String> {
    for k in 0.. {
        for a in data { // Error - but rustc says what to do here
            if a.key == k && !a.used {
                a.used = true;
                // return Some(&a.value);
            }
        }
    }
    None
}

The error messages from rustc say what to do and why. The mutable borrow in the parameters is moved (used up) by the call to into_iter() in for a in data.

rustc recommends a mutable re-borrow. This way we don't try to borrow something that has already been moved. Making that change (and keeping the return commented-out for now), the following now type-checks:

fn find_unused<'a>(data: &'a mut Vec<Association>) -> Option<&'a String> {
    for k in 0.. {
        for a in &mut *data { // we took rustc's suggestion
            if a.key == k && !a.used {
                a.used = true;
                // return Some(&a.value);
            }
        }
    }
    None
}

If we un-comment the return, we get an error saying that the lifetime of the value we're returning doesn't match 'a.

But if we run with cargo +nightly rustc -- -Z polonius, the code type-checks.

@stargateur suggested trying polonius in a comment

Here's my guess as to why Polonius helps:

  • For the current rustc borrow-checker, lifetimes in function signatures are treated in a relatively coarse and simplistic way within the body of the function. I think what's happening here is that 'a is supposed to span the entire function body, but the fresh mutable borrow for a only spans part of the function body, so Rust doesn't unify them.
  • Polonius tracks origins of borrows in types. So it knows that the lifetime of &a.value comes from a, which comes from data, which has lifetime 'a, so Polonius knows the return is OK.

I'm basing this on The Polonius Talk but The Book is probably more up-to-date

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.