Borrow problem with trait object

Hi,

could you please help me to understand cause of this problem? I have this code:

        let mut buf = [0u8; 4096];
        let checker: Box<dyn Checksum<&[u8]>> = Box::new(Crc16Fast::new());//create_checker!(alg, &[u8]);
        let mut out_file = fs::File::create(fname).unwrap();
        
        loop {
            let r = read_block(&mut f, &mut buf).unwrap();
            if r == 0 {
                break;
            }
            let cs = checker.calc(&buf[..r]);
            out_file.write_all(&cs).unwrap();
        }

which gives me this error:

error[E0502]: cannot borrow `buf` as mutable because it is also borrowed as immutable
   --> src/bin/cs.rs:152:40
    |
152 |             let r = read_block(&mut f, &mut buf).unwrap();
    |                                        ^^^^^^^^ mutable borrow occurs here
...
156 |             let cs = checker.calc(&buf[..r]);
    |                      -------       --- immutable borrow occurs here
    |                      |
    |                      immutable borrow later used here

Now problem is with trait object - if checker is created as regular struct, code compiles. I do not understand how trait object gets into picture - why and how buf borrow is later used in checker object , when it's just input param to calc function?

Thanks.

What is the signature of the read_block and calc functions?

fn read_block<R:Read>(mut stream:R, buf: &mut [u8]) -> io::Result<usize>;

pub trait Checksum<R: Read> {
    fn calc(&self, r: R) -> Vec<u8>;
    // ... more methods
}

The difference is that Crc16Fast has an impl block like this:

impl<'a> Checksum<&'a [u8]> for Crc16Fast

This means that regardless of which lifetime 'a you pick, the trait Crc16Fast will implement Checksum with that lifetime.

However Box<dyn Checksum<&[u8]>> isn't something that implements the trait object for any lifetime 'a, but for some specific and elided lifetime. Therefore the lifetime used in every call to calc must be the same lifetime, which means that the reference passed to calc must live until the next call to calc in the next iteration.

But in the second iteration of the loop, we already gave a borrow of buf to calc, which must still live because we're going to reach calc again later in the loop. This is why it is immutably borrowed when you reach the mutable borrow.

Note that the issue disappears if you have no loop, as the immutable borrow happens after the mutable borrow.

In order to fix the issue, simply claim that the box implements the trait for every lifetime:

let checker: Box<dyn for<'a> Checksum<&'a [u8]>> = Box::new(Crc16Fast::new());

@alice Thanks, but now I'm trying to generalize, so
Trait:


pub trait Checksum<'a, R: Read+'a> {
    fn calc(&self, r: R) -> Vec<u8>;
    // more methods ...
}

impl:

impl<'a, R: Read+'a> Checksum<'a, R> for Crc16Fast {
    
    fn calc(&self, mut r: R) -> Vec<u8> {
     unimplemented!()
    }

And now I create checker like this:

macro_rules! create_checker {
    ($alg:expr, $t:ty) => {
        {
        let checker: Box<dyn for<'a> Checksum<'a, $t>> = match $alg {
        "xor" => Box::new(Xor),
        "fletcher" => Box::new(Fletcher),
        "crc16-slow" => Box::new(Crc16),
        "crc16" => Box::new(Crc16Fast::new()),
        _ => unreachable!("Invalid algorithm"),
        };
        checker
        }
    };
}

But I'm getting same error and plus this one :

error[E0597]: `buf` does not live long enough
   --> src/bin/cs.rs:156:36
    |
115 |         "xor" => Box::new(Xor),
    |                  ------------- cast requires that `buf` is borrowed for `'static`
...
156 |             let cs = checker.calc(&buf[..r]);
    |                                    ^^^ borrowed value does not live long enough
...
159 |     } else if let Some(fname) = params.value_of_os("validate-blocks") {
    |     - `buf` dropped here while still borrowed

Here you are binding the lifetime in for to the first argument to the trait, and not to the type in $t, giving you the issue from before. To make it work you would have to make it expand into something like for<'a, 'b> Checksum<'a, &'b [u8]> to make the for-all also apply to the slice.

Why do you need the Checksum trait to be generic on the lifetime? Perhaps you could consider something like this instead:

pub trait Checksum {
    fn calc(&self, r: &mut dyn Read) -> Vec<u8>;
}

Note that you can't make the method generic since then the trait isn't object safe and can't be put in a box.

Alternatively don't use a macro, because injecting the lifetime into the slice is not possible as far as I can see.

@alice thanks, I think I still need more in depth insight into lifetimes.

Re: Box<dyn for<'a> Checksum<'a, $t>>
I thought when trait and impl has R:Read+'a it binds the lifetime to time? But probably in exactly opposite way - as some types have `static lifetime, then then buf is required also to have static? Is this how variance of lifetime is supposed to work?

Re: Why do you need the Checksum trait to be generic on the lifetime?
My idea was: because trait can take any type, which implements Read (and this type be either value as File or reference as &[u8]) I need some high level binding between type and it's lifetime R:Read + 'a. I thought that this lifetime will apply to the type - e.g. also to reference like &[u8].

Re: fn calc(&self, r: &mut dyn Read) -> Vec<u8>;
I was quite happy here with static dispatch here, so did not want trait object as read stream.

As I have written I think my problem is due to shallow understanding of lifetimes. I of course read the book TRPL and Programming Rust and some other articles, but I think I still do not have good mental model of lifetimes. It's not completely about lexical scope, they do behave more like types. Is there some good resource to really get correct understanding of lifetimes?

We are reaching into the topics of the for all lifetime operator. Issues with this topic does not imply a shallow understanding at all!

And yes, the problem is that although R:Read+'a does bind 'a to the elided lifetime in the slice, you only introduce a constraint of the form 'a > 'elided, so when the calls to calc force the buffer and thus 'elided to span the entire loop, the 'a lifetime is also forced to be as large as the loop.

I recommend not using the macro to do that match, just write it out completely including the slice. Or perhaps make an enum with the four cases you want and implement Checksum on the enum?

@alice thanks,

finally I made bit more macro magic :slight_smile: (as my goal was to have match with algorithms in one place only, and use it in different parts of code with various readers as File, slice, stdin ..., some are passed by value some as reference):

macro_rules! create_checker_inner {
    ($alg:expr) => {
        match $alg {
        "xor" => Box::new(Xor),
        "fletcher" => Box::new(Fletcher),
        "crc16-slow" => Box::new(Crc16),
        "crc16" => Box::new(Crc16Fast::new()),
        _ => unreachable!("Invalid algorithm"),
        }
    }
}

macro_rules! create_checker {
    ($alg:expr, $t:ty) => {
        {
            let checker: Box<dyn Checksum<$t>> = create_checker_inner!($alg);
        checker
        }
    };
    ($alg:expr, ref $t:ty) => {
        {
            let checker: Box<dyn for<'a> Checksum<&'a $t>> = create_checker_inner!($alg);
        checker
        }
    };
}

But it still feels like hack/workaround. I understand the enum solution - that will basically implement static dispatch ( each method will statically match given variant). But that's more code and definitely not DRY. So I wanted to try dynamic dispatch, especially here, where it is not problem, because calls are not so frequent, so no notable performance overhead.

Isn't there really better solution for this use case, which is basic polymorphism from OOP? I have trait/interface, which is parametric by type (in this case it takes anything that is Reader, I cannot use type parameters in methods as it's not allowed for trait objects).
Then in code I want to create trait objects for concrete implementation and parametric type (File, &[u8], stdin ...) in different places and the use them in the loops, etc.? I think from your explanations I do have some understanding of the problem, but still shallow.

The error message itself is bit confusing, because checker technically does not have reference to buf - it's just that checker.calc input param lifetime creates something like the reference in checker. It's rather confusing for me.

The compiler doesn't care if you actually store it. What matters is the signature of the method, and because of the elided lifetime, it says that it could store buf even if it doesn't in practice.

I can write some more details when I get home, am at phone atm

Ok, I looked bit more on HRTB and think I'm getting the message, let me reformulate, so I can digest it:

  1. It's not about actual references, but how borrow checker sees them, - because my trait is generic, if concrete type is reference with life time - then borrow checker needs to handle this lifetime as if type has a reference (something like phantom data).

  2. As lifetime is not provided, it must be deduced from the context, here from first occurrence of checker.calc

  3. When checker.calc(&buf[..r]) is first met in loop, borrow checker sees that it's inside the loop and thinks this reference ('phantom reference' of checker) must live through all iterations of the loop. So on next iteration when calling read_block(&mut f, &mut buf), borrow checker sees conflictbuf` is like it's borrowed by checker, but here we also need for new unique mutable borrow - so problem.

  4. On the other hand - if trait's object type parameter (referenced type) is defined for all possible lifetimes like Box<dyn for<'a> Checksum<&'a $t>>, then borrow checker does not have problem, it will work with provided lifetime - which is just for the call of checker.calc and it's different for every loop iteration.

Howgh

Sounds about right. Fundamentally the issue is that if you do not use for-all, you are telling the compiler that it only implements the trait for one particular lifetime, and because of the trait definition, this lifetime must be shared by all buffers given to calc.

So since the same lifetime is used in every iteration, the lifetime in the first iteration is still valid when we get to it in the next iteration, and since we gave it an item with a lifetime that is still valid in the next iteration, the method may store it. What matters is the signature, and it says it can store it. So since it could be stored, you can't make a mutable reference.

@alice Thanks a lot! Your comments were really usefull.

I think I have now better understanding of this topic.

Since implementation can do almost everything, compiler assumes that it can store the reference, unless told differently, that it works for all lifetimes.