Closures in methods can return pointers with short lifetimes

[Thiez]

fn function<A, B>(f: |&A| -> B) {}

trait Foo<A> {
    fn method<B>(&self, f: |&A| -> B);
}

struct Bar<A>;

impl<A> Bar<A> {
    fn inherent_method<B>(&self, f: |&A| -> B) {}
}

fn test<T: Foo<uint>>(x: T) {
    function::<uint, &uint>(|a| a);

    Bar::<uint>.inherent_method::<&uint>(|a| a);

    x.method::<&uint>(|a| a)
}

fn main() {}

function and the two methods are basically identical, except only function correctly gets an error (there's no lifetime connection between the returned B and the reference passed to the closure so it should be illegal to return that reference directly).

<anon>:8:33: 8:34 error: cannot infer an appropriate lifetime for automatic coercion due to conflicting requirements
<anon>:8     function::<uint, &uint>(|a| a);
                                         ^
<anon>:8:5: 8:28 note: first, the lifetime cannot outlive the expression at 8:4...
<anon>:8     function::<uint, &uint>(|a| a);
             ^~~~~~~~~~~~~~~~~~~~~~~
<anon>:8:5: 8:28 note: ...so that type parameter instantiated with `&uint`, will meet its declared lifetime bounds.
<anon>:8     function::<uint, &uint>(|a| a);
             ^~~~~~~~~~~~~~~~~~~~~~~
<anon>:8:33: 8:34 note: but, the lifetime must be valid for the expression at 8:32...
<anon>:8     function::<uint, &uint>(|a| a);
                                         ^
<anon>:8:33: 8:34 note: ...so that auto-reference is valid at the time of borrow
<anon>:8     function::<uint, &uint>(|a| a);
                                         ^

Old report:

Iterator.max_by does strange things.

Example:

fn main() {
    assert_eq!((vec![1u8,2,3]).iter().max_by(|n|n).map(|&e|e), Some(1))
}

I would really expect this asertion to fail, because the answer should be Some(3).

[asterite]

And look at this:

fn main() {
  println!("{}", vec![1i8,2,3].iter().max_by(|n| n  + 0).map(|&e|e))
}

Gives:

foo.rs:2:49: 2:54 error: binary operation `+` cannot be applied to type `&&i8`
foo.rs:2   println!("{}", vec![1i8,2,3].iter().max_by(|n|n + 0).map(|&e|e))

???

This compiles and runs fine:

fn main() {
  println!("{}", vec![1i8,2,3].iter().max_by(|n|**n + 0).map(|&e|e))
}

And your example:

fn main() {
    assert_eq!((vec![1u8,2,3]).iter().max_by(|n|**n).map(|&e|e), Some(3))
}

Works fine like that.

Hmm...

[Thiez]

Yes, that is expected because .iter() will produce &u8 and max_by then gives references to those references, giving &&u8. But since Ord is implemented on references to stuff that also implement Ord, it should work.

[Thiez]

Trying to narrow it down reveals something strange. I created a trait MaxBye and copied the max_by implementation in there, and added some good old fashioned println!() debugging.

// Defining max_by as a function appears not to work because it refuses the `|n|n` closure due to some lifetime issue
trait MaxBye<A> {
    fn max_bye<B: Ord + std::fmt::Show>(&mut self, f: |&A| -> B) -> Option<A>;
}

impl <A: std::fmt::Show, T: Iterator<A>> MaxBye<A> for T {
    fn max_bye<B: Ord + std::fmt::Show>(&mut self, f: |&A| -> B) -> Option<A> {
        self.fold(None, |max: Option<(A, B)>, x| {
                for &(_,ref b) in max.iter() { println!("Current: {}, previous: {}",&x, b); }
                let x_val = f(&x);
                match max {
                    None => Some((x, x_val)),
                    Some((y, y_val)) => {
                        if x_val > y_val {
                            Some((x, x_val))
                        } else {
                            Some((y, y_val))
                        }
                    }
                }
            }
        ).map(|(x, _)| x)
    }
}

fn main() {
    let v = vec!(1u8 , 2 , 3);
    println!("{}" , v.iter().max_bye(|n|n).map(|&e|e));
}

The above code will print

Current: 2, previous: 2
Current: 3, previous: 3
Some(1)

Which is very strange, because I would expect

Current: 2, previous: 1
Current: 3, previous: 2
Some(3)

When I change the match to:

match max {
    None => Some((x, x_val)),
    Some((y, y_val)) => {
        unsafe{
            println!("{}, {}",
            *std::mem::transmute::<&B, *const uint>(&x_val),
            *std::mem::transmute::<&B, *const uint>(&y_val));
        }
        if x_val > y_val {
            Some((x, x_val))
        } else {
            Some((y, y_val))
        }
    }
}

It indeed reveals that x_val and y_val point to the same location.

[nodakai]

Oops, I didn't follow the discussion carefully. Let me retract my old comment here.

[huonw]

you compared address values

This is not the case, Ord for &T is comparing the contents, not the addresses. (That said, even with addresses, later elements of the vector will have larger addresses, i.e. the last one should still be the maximum.)

This looks like it may be a misoptimisation (similar to #18786).

[huonw]

Ah, it's not a misoptimisation: it's rustc being bad. @Thiez correctly picked it out with:

// Defining max_by as a function appears not to work because it refuses the |n|n closure due to some lifetime issue

and

It indeed reveals that x_val and y_val point to the same location.

The lifetime issue is real, and it is entirely invalid to write |n| n since that is returning the pointer to x, on the stack let x_val = f(&x);. This pointer is then kept around "forever" (that is, long after that specific x no longer exists on the stack), resulting in the sadness we see here.

I've edited the issue & title to reflect the above.

[nodakai]

A minimal code for reproducing the bug.

struct S;

impl S {
    fn f<B: std::fmt::Show>(&self, g: |&i32| -> B) {
        let h = |x| { g(&x) };
        let r = h(10);
        /*
        let r = g(&10_i32);
        */
        println!("r == {}", r); //  r == 32767 ???
    }
}

fn main() {
    let s = S;
    s.f(|p| {
        println!("p == {}", p);
        p
    })
}

• http://is.gd/rwnohF

The above code shouln't pass the lifetime check, but it does; that is the bug.

rustc rejects the above code with the "cannot infer an appropriate lifetime" error when:

1. The type of g is changed to g: |&i32| -> &B
2. B is replaced with &i32
3. r is directly set by g w/o h
4. The closure passed to s.f() is given an explicit type annotation

Also note that println!("r == {}", r); prints an apparently correct value with --opt-level=2 or 3. But that does not mean the bug (in the type check phase) disappears.

[Thiez]

It looks very much alike but my original example is wrong for all optimization levels (at least on the playpen), so are we observing the same bug?

[nodakai]

@Thiez I think so. I updated my previous comment because my wording was misleading.

[huonw]

The bug here is the compiler letting this through at all; the consequences can manifest in different ways but they're all just (unfortunate) flow-on from the original problem of methods apparently not being checked.

Since this is all undefined behaviour, the specific details of what will go wrong at runtime are hard to predict and aren't really that "interesting" (it's undefined behaviour, so it could be anything).

[pnkfelix]

P-backcompat-lang, 1.0.

[nikomatsakis]

So the key problem is this closure:

    s.f(|p| {
        println!("p == {}", p);
        p
    })

which should not type check, as far as I can tell. The pointer p has a bound lifetime, and it should not be possible for B to be instantiated with that lifetime. There are some parts of the code that try to prevent this (see e.g. compile-fail/region*escape*rs) but clearly it's not working here. I think this is sort of a symptom of #3696 but we can fix it in a relatively smaller way.

[nikomatsakis]

I'll investigate a bit while the HRTB builds go.

[nikomatsakis]

I think the problem is that we don't do call constrain_path_type_parameters for the type parameters supplied to methods.