give_expl_lifetime_param is behaving non-deterministically

[pnkfelix]

For the input file below, the two distinct invocations of rustc (but with identical arguments) are non-deterministically deciding whether or not to prompt with the "consider using an explicit lifetime parameter" hint.

Input file (demo.rs):

use std::iter::{Range,range};

trait Itble<'r, T, I: Iterator<T>> { fn iter(&'r self) -> I; }

impl<'r> Itble<'r, uint, Range<uint>> for (uint, uint) {
    fn iter(&'r self) -> Range<uint> {
        let &(min, max) = self;
        range(min, max)
    }
}

fn check<'r, I: Iterator<uint>, T: Itble<'r, uint, I>>(cont: &T) -> bool
{
    let cont_iter = cont.iter();
    let result = cont_iter.fold(Some(0u16), |state, val| {
        state.map_or(None, |mask| {
            let bit = 1 << val;
            if mask & bit == 0 {Some(mask|bit)} else {None}
        })
    });
result.is_some()
}

fn main() {
    check((3u, 5u));
}

Transcript:

% uname -a
Darwin fklock-Oenone.local 12.5.0 Darwin Kernel Version 12.5.0: Sun Sep 29 13:33:47 PDT 2013; root:xnu-2050.48.12~1/RELEASE_X86_64 x86_64
% rustc --version
/Users/fklock/opt/rust-dbg/bin/rustc 0.10-pre (b6d5b8f 2014-03-17 00:21:59 -0700)
host: x86_64-apple-darwin
% rustc --crate-type lib /tmp/demo.rs
/tmp/demo.rs:12:1: 22:2 note: consider using an explicit lifetime parameter as shown: fn check<'a, I: Iterator<uint>, T: Itble<'r, uint, I>>(cont: &'a T) -> bool
/tmp/demo.rs:12 fn check<'r, I: Iterator<uint>, T: Itble<'r, uint, I>>(cont: &T) -> bool
/tmp/demo.rs:13 {
/tmp/demo.rs:14 let cont_iter = cont.iter();
/tmp/demo.rs:15 let result = cont_iter.fold(Some(0u16), |state, val| {
/tmp/demo.rs:16 state.map_or(None, |mask| {
/tmp/demo.rs:17 let bit = 1 << val;
...
/tmp/demo.rs:14:21: 14:32 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
/tmp/demo.rs:14 let cont_iter = cont.iter();
^~~~~~~~~~~
/tmp/demo.rs:25:11: 25:19 error: mismatched types: expected `&<generic #1>` but found `(uint,uint)` (expected &-ptr but found tuple)
/tmp/demo.rs:25 check((3u, 5u));
^~~~~~~~
/tmp/demo.rs:25:5: 25:10 error: cannot determine a type for this bounded type parameter: unconstrained type
/tmp/demo.rs:25 check((3u, 5u));
^~~~~
% rustc --crate-type lib /tmp/demo.rs
/tmp/demo.rs:14:21: 14:32 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
/tmp/demo.rs:14 let cont_iter = cont.iter();
^~~~~~~~~~~
/tmp/demo.rs:14:21: 14:25 note: first, the lifetime cannot outlive the expression at 14:20...
/tmp/demo.rs:14 let cont_iter = cont.iter();
^~~~
/tmp/demo.rs:14:21: 14:25 note: ...so that automatically reference is valid at the time of borrow
/tmp/demo.rs:14 let cont_iter = cont.iter();
^~~~
/tmp/demo.rs:14:21: 14:32 note: but, the lifetime must be valid for the method call at 14:20...
/tmp/demo.rs:14 let cont_iter = cont.iter();
^~~~~~~~~~~
/tmp/demo.rs:14:21: 14:25 note: ...so that method receiver is valid for the method call
/tmp/demo.rs:14 let cont_iter = cont.iter();
^~~~
/tmp/demo.rs:25:11: 25:19 error: mismatched types: expected `&<generic #1>` but found `(uint,uint)` (expected &-ptr but found tuple)
/tmp/demo.rs:25 check((3u, 5u));
^~~~~~~~
/tmp/demo.rs:25:5: 25:10 error: cannot determine a type for this bounded type parameter: unconstrained type
/tmp/demo.rs:25 check((3u, 5u));
^~~~~
% 

(See also #13058 for a problem with the suggestion actually provided by give_expl_lifetime_param when it chooses to actually provide one.)

[ktt3ja]

I tested it a bit, and the issue seems to be error_reporting is fed slightly different information each time. In the first case we have a SubSupConflict(ReFree, ReFree) and in the second SubSupConflict(ReScope, ReScope).

In the constraint graph for some node 'v we are trying to infer, there are multiple incoming edges and outgoing edges to and from 'v. From my understanding the compiler only picks one node from these incoming edges and one node from these outgoing edges, and it doesn't pick the same pair each time (what I don't understand is why I didn't see the SubSupConflict(ReFree, ReScope) and SubSupConflict(ReScope, ReFree) variations).

[maxsnew]

I'm getting a non-deterministic error message using the latest nightlies: https://gist.github.com/maxsnew/9d3d30b469e7e39909d0

It's non-deterministic on my Fedora 20 machine but not my OSX machine.