Rust does not allow narrowing the mutable references

[uzytkownik]

Currently rust does allow to narrow the immutable references as long as the don't appear in contravariant position:

// This compiles
struct Foo1<'a> {
    a: &'a Fn(&'static str) -> u32
}

fn foo1<'a : 'b, 'b>(foo: Foo1<'a>) -> Foo1<'b> {
    foo
}

// This, correctly, does not compile
struct Foo2<'a> {
    a: &'a Fn(&'a str) -> u32
}


fn foo2<'a : 'b, 'b>(foo: Foo2<'a>) -> Foo1<'b> {
    foo
}

It seems that if I have a mutable reference for 'a lifetime I should be able to turn it into mutable reference for 'b lifetime as long as the 'b is narrower then 'a however the following code is not allowed in Rust:

struct Foo3<'a> {
    a: &'a mut Fn(&'static str) -> u32
}

fn foo3<'a : 'b, 'b>(foo: Foo3<'a>) -> Foo3<'b> {
    foo
}

[Gankra]

Variant &muts are not sound:

fn overwrite<T: Copy>(input: &mut T, new: &mut T) {
    *input = *new;
}

fn main() {
    let mut forever_str: &'static str = "hello";
    {
        let string = String::from("world");
        overwrite(&mut forever_str, &mut &*string);
    }
    // Oops, printing free'd memory
    println!("{}", forever_str);
}

[uzytkownik]

@gankro You're right - I haven't thought about that. Correct me if I'm wrong, however, but this is only when the &'a mut reference outlives &'b mut reference. I was thinking about 'moving' the reference so once the cast is done in line 9 the forever_str would not be allowed to be accessed outside overwrite.

---

To explain why - I've tried to create a mutable zipper. Effectively it is a recursive structure where each element refers to one created in parent structure and they all go out of scope

[steveklabnik]

/cc @nikomatsakis @aturon , is @gankro correct that this is unsound? if so, it should be closed.

[Gankra]

Discussed this more on IRC. I had originally only skimmed the details and had snapped "&'a mut T is invariant in T" to "&mut is invariant in all args", but this isn't actually necessary. The 'a: 'b constraint prevents you from getting into any trouble (the input lifetime is forced to outlive output lifetime, which is all you really want for a foo<'a>(x: &'a mut X) -> &'a mut T).

Also this works:

type Test<'a> = &'a mut Fn(&'static str) -> u32;

fn matched_lifetimes<'a>(_: &'a u8, _: Test<'a>) {}

fn main() {
    let x: Test<'static> = panic!();
    {
        let y: u8 = 0;
        let z = &y;
        matched_lifetimes(z, x);
    }
}

which suggests we already support this in a limited way.

So yes, I think this is a legit bug.

[arielb1]

I don't see the unsoundness here (in making &'a mut T be variant in 'a). cc @pnkfelix too.

[arielb1]

For the record, you can ATM create a &mut zipper with trait objects.

enum BL<'a> {
    Root,
    Link(&'a mut BLLike, &'a mut u32)
}

trait BLLike {
    fn val(&mut self) -> BL;
}

impl<'a> BLLike for BL<'a> {
    fn val(&mut self) -> BL {
        match self {
            &mut BL::Root => BL::Root,
            &mut BL::Link(ref mut cdr, ref mut car) => BL::Link(*cdr, car)
        }
    }

}

fn traverse<'a>(mut u: u32, mut l: BL) {
    if u > 0 {
        traverse(u-1, BL::Link(&mut l, &mut u))
    } else {
        while let BL::Link(cdr, car) = l {
            println!("u={:?}", car);
            l = cdr.val();
        }
    }
}

fn main() {
    traverse(14, BL::Root);
}

[nikomatsakis]

I'm surprised by this, I expect &'a mut T <: &'b mut T if 'a: 'b. I'll have to look briefly at the code to see why that is not the case. At first glance, I didn't see what was going on.

[nikomatsakis]

Oh, wait. I see what it is.

[nikomatsakis]

The situation is caused by the defaulting rules around trait object lifetimes. Specifically, the fullly expanded version of the struct in question is:

struct Foo3<'a> {
    a: &'a mut (Fn(&'static str) -> u32 + 'a)
}

While it is true that &'a mut T <: &'b mut T if 'a:'b, we do require that the two types be equal (iow, &'a mut T is contravar. w/r/t 'a, but invariant w/r/t T). In this case, the reason the subtyping is failing is because of the (implicit) 'a bound. For example, this test works http://is.gd/w2c9Df.

Now, it is true that you can assign &'a mut (Trait+'a) to &'b mut (Trait+'b) if 'a:'b -- but that is not due to subtyping, but rather coercion. In particular, we permit an unsizing coercion from Trait+'a to Trait+'b if 'a:'b.

So I would say the current behavior is Working As Designed.

[nikomatsakis]

To be clear, I'd love to overcome have the original code work, but it'd require a fairly subtle typing rule to make it sound. I guess we could add a rule for subtyping of &mut T that is specific to the case where T is a trait object, but that doesn't feel very nice. (Not that I support this, but it's interesting to note that something like &uniq T, where you have uniqueness but not mutability, would of course be covariant.)

[uzytkownik]

@nikomatsakis Initally I didn't have traits at all - it was closer to:

enum Tree<T> {
   Bin(*mut Tree<T>, T, *mut Tree<T>),
   Leaf
}

enum TreeZipper<'a, T : 'a> {
    Top,
    Left(&'a mut TreeZipper<'a, T>, T, Tree<T>),
    Right(Tree<T>, T, &'a mut TreeZipper<'a, T>)
}

fn cast<'a : 'b, 'b, T : 'a>(foo: TreeZipper<'a, T>) -> TreeZipper<'b, T> {
    foo
}

@arielb1 This still does no compile:

enum BL<'a> {
    Root,
    Link(&'a mut BLLike, &'a mut u32)
}

trait BLLike {
    fn val(&mut self) -> BL;
}

fn cast<'a : 'b, 'b>(foo: BL<'a>) -> BL<'b> {foo}

[nikomatsakis]

It is not a question of traits (in fact, my point was that traits are not special cased, which is why you get an error here). The point is that you have the reference to 'a inside the referent type in both cases (that is, the type that the &mut points at). That makes it "invariant", meaning it cannot be shortened (or else the language would be unsound). In the trait case however this is less obvious because it appears due to the implicit lifetime bound. 

Niko

-------- Original message --------

From: Maciej Piechotka notifications@github.com

Date:07/18/2015 01:58 (GMT-05:00)

To: rust-lang/rust rust@noreply.github.com

Cc: Niko Matsakis niko@alum.mit.edu

Subject: Re: [rust] Rust does not allow narrowing the mutable references (#27031)

@nikomatsakis Initally I didn't have traits at all - it was closer to:

enum Tree {
Bin(*mut Tree, T, *mut Tree),
Leaf
}

enum TreeZipper<'a, T : 'a> {
Top,
Left(&'a mut TreeZipper<'a, T>, T, Tree),
Right(Tree, T, &'a mut TreeZipper<'a, T>)
}

fn cast<'a : 'b, 'b, T : 'a>(foo: TreeZipper<'a, T>) -> TreeZipper<'b, T> {
foo
}
@arielb1 This still does no compile:

enum BL<'a> {
Root,
Link(&'a mut BLLike, &'a mut u32)
}

trait BLLike {
fn val(&mut self) -> BL;
}

fn cast<'a : 'b, 'b>(foo: BL<'a>) -> BL<'b> {foo}
—
Reply to this email directly or view it on GitHub.

[arielb1]

Anyway, you can bypass this by restructuring:

struct Foo3<'a> {
    a: &'a mut Fn(&'static str) -> u32 + 'a
}

fn foo3<'a : 'b, 'b>(foo: Foo3<'a>) -> Foo3<'b> {
    match foo { Foo3 { a } => Foo3 { a: a }} 
}

fn main() {}

In the BL case:

enum BL<'a> {
    Root,
    Link(&'a mut BLLike, &'a mut u32)
}

trait BLLike {
    fn val(&mut self) -> BL;
}

fn cast<'a : 'b, 'b>(foo: BL<'a>) -> BL<'b> {
    match foo { BL::Root => BL::Root, BL::Link(a,b) => BL::Link(a,b) }
}

[arielb1]

Anyway, this may be a reason to have &uniq, or equivalently use-site variance, so we don't need trait objects for this.

[steveklabnik]

So, years later: I think this ticket is basically not actionable, right? I would imagine something like

I'd love to overcome have the original code work, but it'd require a fairly subtle typing rule to make it sound. I guess we could add a rule for subtyping of &mut T that is specific to the case where T is a trait object, but that doesn't feel very nice.

Would be RFC territory. Maybe not. I dunno.

[nikomatsakis]

I think we should close this. It's a...quirk of the type system. =)