region/type inference bug with method

[thestinger]

Update: I can confirm this is definitely related to regions. An iterator without region annotations doesn't run into this problem.

Update two: I've added a much simpler test case in a comment below.

I'll see if I can cut this down to a simpler test case later. For now, here's a snippet I added to treemap.rs:

pub trait Iterator<T> {
    fn next(iter: &mut Self) -> Option<T>;
}

impl<'self, K, V> Iterator<(&'self K, &'self V)> for TreeMapIterator<'self, K, V> {
    fn next(iter: &mut TreeMapIterator<'self, K, V>) -> Option<(&'self K, &'self V)> {
        map_next(iter)
    }
}

impl<'self, T> Iterator<&'self T> for TreeSetIterator<'self, T> {
    fn next<'r>(iter: &mut TreeSetIterator<'r, T>) -> Option<&'r T> {
        set_next(iter)
    }
}

pub struct ZipIterator<T, U> {
    priv a: T,
    priv b: U
}

pub impl<A, B, T: Iterator<A>, U: Iterator<B>> ZipIterator<T, U> {
    fn new(a: T, b: U) -> ZipIterator<T, U> {
        ZipIterator{a: a, b: b}
    }
}

impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for ZipIterator<T, U> {
    fn next(iter: &mut ZipIterator<T, U>) -> Option<(A, B)> {
        let x = Iterator::next(&mut iter.a);
        let y = Iterator::next(&mut iter.b);
        match (x, y) {
            (Some(a), Some(b)) => Some((a, b)),
            _ => None
        }
    }
}

and a test case (which compiles and works as it is here):

#[test]
fn test_zip() {
    let mut x = TreeSet::new();
    x.insert(5u);
    x.insert(12u);
    x.insert(11u);

    let mut y = TreeSet::new();
    y.insert("foo");
    y.insert("bar");

    let x = x;
    let y = y;
    let mut z = ZipIterator::new(x.iter(), y.iter());

    // this needs a type hint to compile...
    let result: Option<(&uint, & &'static str)> = Iterator::next(&mut z);
    assert!(result.unwrap() == (&5, & &"bar"));

    let result: Option<(&uint, & &'static str)> = Iterator::next(&mut z);
    assert!(result.unwrap() == (&11, & &"foo"));

    let result: Option<(&uint, & &'static str)> = Iterator::next(&mut z);
    assert!(result.is_none());
}

Removing the type hint from result causes this integer literal inference error:

treemap.rs:1274:21: 1274:35 error: expected Iterator<&int>, but found Iterator<&uint> (expected int but found uint)
treemap.rs:1274         let result = Iterator::next(&mut z);
                                     ^~~~~~~~~~~~~~
treemap.rs:1274:21: 1274:35 error: expected Iterator<&uint>, but found Iterator<&int> (expected uint but found int)
treemap.rs:1274         let result = Iterator::next(&mut z);
                                     ^~~~~~~~~~~~~~
error: aborting due to 2 previous errors

So I tried a workaround like this:

    let result = Iterator::next(&mut z);
    assert!(result.unwrap() == (&5u, & &"bar"));

which hits what appears to be a borrow checking bug:

treemap.rs:1275:37: 1275:39 error: illegal borrow: borrowed value does not live long enough
treemap.rs:1275         assert!(result.unwrap() == (&5u, & &"bar"));
                                                     ^~
<core-macros>:46:4: 57:5 note: in expansion of assert!
treemap.rs:1275:8: 1275:52 note: expansion site
treemap.rs:1259:18: 1282:5 note: borrowed pointer must be valid for the block at 1259:18...
treemap.rs:1259     fn test_zip() {
treemap.rs:1260         let mut x = TreeSet::new();
treemap.rs:1261         x.insert(5u);
treemap.rs:1262         x.insert(12u);
treemap.rs:1263         x.insert(11u);
treemap.rs:1264 
                ...
treemap.rs:1275:8: 1275:52 note: ...but borrowed value is only valid for the statement at 1275:8
treemap.rs:1275         assert!(result.unwrap() == (&5u, & &"bar"));
                        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treemap.rs:1275:43: 1275:49 error: illegal borrow: borrowed value does not live long enough
treemap.rs:1275         assert!(result.unwrap() == (&5u, & &"bar"));
                                                           ^~~~~~
<core-macros>:46:4: 57:5 note: in expansion of assert!
treemap.rs:1275:8: 1275:52 note: expansion site
treemap.rs:1259:18: 1282:5 note: borrowed pointer must be valid for the block at 1259:18...
treemap.rs:1259     fn test_zip() {
treemap.rs:1260         let mut x = TreeSet::new();
treemap.rs:1261         x.insert(5u);
treemap.rs:1262         x.insert(12u);
treemap.rs:1263         x.insert(11u);
treemap.rs:1264 
                ...
treemap.rs:1275:8: 1275:52 note: ...but borrowed value is only valid for the statement at 1275:8
treemap.rs:1275         assert!(result.unwrap() == (&5u, & &"bar"));
                        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 2 previous errors
zsh: exit 101   ~/projects/rust/x86_64-unknown-linux-gnu/stage2/bin/rustc --test treemap.rs

I thought this might be related to == being broken in some ways, but yet another error happens with match, unless the explicit type hint is used:

    let result = Iterator::next(&mut z);

    match result.unwrap() {
        (&5u, & &"bar") => (),
        _ => fail!()
    }

treemap.rs:1278:13: 1278:17 error: the type of this value must be known in this context
treemap.rs:1278             (&5u, & &"bar") => (),
                             ^~~~
treemap.rs:1278:13: 1278:17 error: mismatched types: expected `[type error]` found borrowed pointer
treemap.rs:1278             (&5u, & &"bar") => (),
                             ^~~~

@nikomatsakis

[jdm]

Paging @catamorphism for derived type error.

[catamorphism]

Thanks for flagging me! In this case, the derived error message is because of #5658

[thestinger]

This still occurs now that &mut self can be used, so it's not just with static methods. I added a FIXME to the test in that pull request so it's easy to find.

[thestinger]

pub fn all<T>(predicate: &fn(T) -> bool, iter: &fn(f: &fn(T) -> bool)) -> bool {
    for iter |x| {
        if !predicate(x) {
            return false
        }
    }
    true
}

fn main() {
    all(|x: uint| x < 6, |f| std::uint::range(1, 6, f));
}

Much simpler test case, but possibly a different bug.

[emberian]

@thestinger The reduced test case now runs, but I can't get the treemap snippet to compile (because of the snippet itself, not bugs).

[thestinger]

@cmr: the error happens when you remove the type hint on the closure parameter.

[msullivan]

The reduced test case fails due to a known limitation in our type inference without an obvious easy fix. It is bug #912, which was closed.

[recrack]

No more bugs. I think we should close.
See: https://gist.github.com/recrack/a06f2a0d966ff8a2c00f

* Rust test verion
- rustc 0.9-pre (f27dfa0 2013-10-23 21:46:03 -0700)
- host: x86_64-unknown-linux-gnu

[alexcrichton]

This bug seems to be quite out of date, and there don't seem to be any standalone examples to test on today's compiler.

Closing as likely fixed or needs an up-to-date example to make progress.