ICE due to ambiguity between impl and where-clause

[nikomatsakis]

Example:

use std::vec::Vec;
use std::iter::Iterator;
use std::slice::{AsSlice, Split, SliceExt};

pub struct Path {
    repr: Vec<u8>, // assumed to never be empty or contain NULs
}

pub type Components<'a> = Split<'a, u8, fn(&u8) -> bool>;

pub fn is_sep_byte(u: &u8) -> bool {
    true
}

impl Path {
    fn components<'a>(&'a self) -> Components<'a>
        where fn(&u8) -> bool : FnMut(&u8) -> bool
    {
        let v = &self.repr[1..];
        let is_sep_byte: fn(&u8) -> bool = is_sep_byte; // coerce to fn ptr
        let mut ret = v.split(is_sep_byte);
        if v.is_empty() {
            ret.next();
        }
        ret
    }
}

fn main() {
}

fails with

<anon>:21:25: 21:43 error: internal compiler error: coherence failed to report ambiguity: cannot locate the impl of the trait `for<'r> core::ops::FnMut<(&'r u8,)>` for the type `fn(&u8) -> bool`
<anon>:21         let mut ret = v.split(is_sep_byte);
                                  ^~~~~~~~~~~~~~~~~~
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: http://doc.rust-lang.org/complement-bugreport.html
note: run with `RUST_BACKTRACE=1` for a backtrace
thread 'rustc' panicked at 'Box<Any>', /home/rustbuild/src/rust-buildbot/slave/nightly-dist-rustc-linux/build/src/libsyntax/diagnostic.rs:129


playpen: application terminated with error code 101
Program ended.

This is because the compiler considers both the bridging impl from Fn to FnMut is an option and the where-clause to be valid options. Choosing between where-clauses and impls seems to be tricky.

At minimum, the code that checks for overlap between the where-clause and the impl seems to have the subtyping relationship backwards. However, I am not sure whether it's a good idea to check anything, or maybe better to simply always prefer where-clauses.

[nikomatsakis]

A more standalone version of that test:

use std::vec::Vec;
use std::iter::Iterator;
use std::slice::{AsSlice, Split, SliceExt};

struct Path;

trait Foo<A> {
    fn foo(&self, a: A);
}

impl<A,F:Fn(A)> Foo<A> for F {
    fn foo(&self, a: A) { }
}

fn baz<F:for<'a> Foo<(&'a Path,)>>(f: F) { }

impl Path {
    fn components<T>(&self, t: fn(&Path))
        where fn(&Path) : for<'a> Foo<(&'a Path,)>,
    {
        baz(t)
    }
}

fn main() {
}

[nikomatsakis]

That version only works because we don't seem to be enforcing the rules against where-clauses with no type parameters fully. This alternate version also fails to compile but obeys those rules:

use std::vec::Vec;
use std::iter::Iterator;
use std::slice::{AsSlice, Split, SliceExt};

struct Path;

trait Foo<A> {
    fn foo(&self, a: A);
}

impl<A,F:Fn(A)> Foo<A> for F {
    fn foo(&self, a: A) { }
}

fn baz<A,F:for<'a> Foo<(&'a A,)>>(f: F) { }

fn components<T,A>(t: fn(&A))
    where fn(&A) : for<'a> Foo<(&'a A,)>,
{
    baz(t)
}

fn main() {
}

but the error is different:

traits-issue-22110.rs:34:5: 34:8 error: unable to infer enough type information about `_`; type annotations required [E0282]

[nikomatsakis]

A related example:

use std::slice::Iter;

fn foo<'a,T>(v: Iter<'a,T>) -> Option<T>
    where Iter<'a,T> : Iterator
{
    v.next()
}

fn main() { }

Here the explicit where clause matches, interfering with later attempts to project the type Item, and hence we get:

<anon>:6:5: 6:13 error: mismatched types:
 expected `core::option::Option<T>`,
    found `core::option::Option<<core::slice::Iter<'a, T> as core::iter::Iterator>::Item>`
(expected type parameter,
    found associated type) [E0308]
<anon>:6     v.next()
             ^~~~~~~~
error: aborting due to previous error
playpen: application terminated with error code 101

[jroesch]

cc me

[ghost]

cc me

[nikomatsakis]

The fix in #22407 is simply to always allow where clauses to override impls. This seems like a conservative step -- everything where clauses tell you must be derived from an impl, after all. In he future, I'd like to improve the engine so that it can take advantage of impls as well to possibly glean more information than the where-clause is telling us, but it's tricky, because impls have preconditions.