fulfillment error involving quickcheck `Testable` trait on `fn` types (and tuples?)

[pnkfelix]

spawned off of #33723

This code (playpen) causes an ICE in the beta and nightly compilers:

// Heavily reduced version of `quickcheck` with an `fn main`that ICE's the compiler.
//
// This is for issues #33723 and #34503

// This provides a modified version of the `Iterator` trait whose
// `fn max` method does not have a `Self: Sized` bound. This is
// to isolate the distinct bug underlying #33723 (which was sidestepped
// by PR #34419).
use self::my_iter::Iterator;
mod my_iter {
    pub trait Iterator {
        type Item;
        fn next(&mut self) -> Option<Self::Item>;
        fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
            where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option<B>,
        {
            Scan{iter: self, f: f, state: initial_state}
        }

        // This version of `fn max` takes `&self` rather than `self` to sidestep
        // the vtable Self: Sized fix from PR #34419
        fn max(&self) -> Option<Self::Item> where Self::Item: Ord
        {
            return select_fold1(self,
                                |_| (),
                                // switch to y even if it is only equal, to preserve
                                // stability.
                                |_, x, _, y| *x <= *y)
                .map(|(_, x)| x);

            fn select_fold1<I: ?Sized,B, FProj, FCmp>(mut _it: &I,
                                                      mut _f_proj: FProj,
                                                      mut _f_cmp: FCmp) -> Option<(B, I::Item)>
                where I: Iterator, FProj: FnMut(&I::Item) -> B, FCmp: FnMut(&B, &I::Item, &B, &I::Item) -> bool
            {
                unimplemented!()
            }
        }
    }

    #[derive(Clone)]
    pub struct Scan<I, St, F> {
        iter: I,
        f: F,
        state: St,
    }

    impl<B, I, St, F> Iterator for Scan<I, St, F> where
        I: Iterator,
    F: FnMut(&mut St, I::Item) -> Option<B>,
    {
        type Item = B;

        #[inline]
        fn next(&mut self) -> Option<B> {
            self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
        }
    }

    impl<I: Iterator + ?Sized> Iterator for Box<I> {
        type Item = I::Item;
        fn next(&mut self) -> Option<I::Item> {
            (**self).next()
        }
    }
}

pub trait Arbitrary : Clone + 'static {
    fn arbitrary<G>() -> Self { unimplemented! () }
    fn shrink(&self) -> Box<Iterator<Item=Self>> { unimplemented!() }
}

impl<A: Arbitrary> Arbitrary for Option<A> { }

impl<A: Arbitrary> Arbitrary for (A,)
{
    fn shrink(&self) -> Box<Iterator<Item=(A,)>> {
        let (ref a, ) = *self;
        let srest = a
            .shrink()
            .scan((), |_, _| unimplemented!());
        Box::new(srest)
    }
}

impl<A: Arbitrary, B: Arbitrary> Arbitrary for (A, B,)
{
    fn shrink(&self) -> Box<Iterator<Item=(A, B)>> {
        let (ref a, ref b) = *self;
        let srest = (b.clone(),) // <--- use of unary tuple is key to reproducing bug
            .shrink()
            .scan(a.clone(), |_, _| unimplemented!());
        Box::new(srest)
    }
}

pub fn quickcheck<A: Testable>(f: A) {
    f.result::<A>();
}

pub trait Testable : Send + 'static {
    fn result<G>(&self) { unimplemented!() }
}

impl Testable for () { }

impl<T: Testable, A: Arbitrary, B: Arbitrary> Testable for fn(A, B) -> T
{
    fn result<G_>(&self) {
        let a: (A, B) = Arbitrary::arbitrary::<G_>();
        a.shrink();
    }
}

#[derive(Clone, Debug)]
struct PackedNode;
impl Arbitrary for PackedNode { }

fn main() {
    fn with_nodes(_: PackedNode, _: Option<PackedNode>) { unimplemented!() }
    quickcheck(with_nodes as fn(PackedNode, Option<PackedNode>));
}

here is the compiler ICE message:

error: internal compiler error: ../src/librustc/infer/mod.rs:681: Encountered errors `[FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<PackedNode as std::cmp::PartialEq>)),depth=2),Unimplemented), FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<PackedNode as std::cmp::PartialOrd>)),depth=2),Unimplemented)]` resolving bounds after type-checking
note: the compiler unexpectedly panicked. this is a bug.

(What follows is the original reduced test case, which stopped ICE'ing recently due to an unrelated bug fix, which prompted me to write the above revision of the code to continue demonstrating the bug in question.)

Old Description

// Heavily reduced version of `quickcheck` with an `fn main`that ICE's the compiler.
//
// This is for issue #33723.

pub trait Arbitrary : Clone + 'static {
    fn arbitrary<G>() -> Self { unimplemented! () }
    fn shrink(&self) -> Box<Iterator<Item=Self>> { unimplemented!() }
}

impl<A: Arbitrary> Arbitrary for Option<A> { }

impl<A: Arbitrary> Arbitrary for (A,)
{
    fn shrink(&self) -> Box<Iterator<Item=(A,)>> {
        let (ref a, ) = *self;
        let srest = a
            .shrink()
            .scan((), |_, _| unimplemented!());
        Box::new(srest)
    }
}

impl<A: Arbitrary, B: Arbitrary> Arbitrary for (A, B,)
{
    fn shrink(&self) -> Box<Iterator<Item=(A, B)>> {
        let (ref a, ref b) = *self;
        let srest = (b.clone(),) // <--- use of unary tuple is key to reproducing bug
            .shrink()
            .scan(a.clone(), |_, _| unimplemented!());
        Box::new(srest)
    }
}

pub fn quickcheck<A: Testable>(f: A) {
    f.result::<A>();
}

pub trait Testable : Send + 'static {
    fn result<G>(&self) { unimplemented!() }
}

impl Testable for () { }

impl<T: Testable, A: Arbitrary, B: Arbitrary> Testable for fn(A, B) -> T
{
    fn result<G_>(&self) {
        let a: (A, B) = Arbitrary::arbitrary::<G_>();
        a.shrink();
    }
}

#[derive(Clone, Debug)]
struct PackedNode;
impl Arbitrary for PackedNode { }

fn main() {
    fn with_nodes(_: PackedNode, _: Option<PackedNode>) { unimplemented!() }
    quickcheck(with_nodes as fn(PackedNode, Option<PackedNode>));
}

This is the ICE in question:

error: internal compiler error: ../src/librustc/infer/mod.rs:642: Encountered errors 
`[FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<PackedNode as std::cmp::PartialEq>)),depth=2),Unimplemented), 
  FulfillmentError(Obligation(predicate=Binder(TraitPredicate(<PackedNode as std::cmp::PartialOrd>)),depth=2),Unimplemented)]`
 resolving bounds after type-checking

[pnkfelix]

The ICE here goes away if I add derived of PartialEq and PartialOrd to the struct PackedNode.

I need to double-check if this the actually the same ICE that plagues #33723.

[pnkfelix]

(of course, AFAICT there is no reason that we should be requiring the PartialEq nor the PartialOrd traits on the struct in question, so I claim this is still a valid bug.)

[pnkfelix]

I'm going to copy over the labels from #33723 since this is at least as high priority as that bug is.

[brson]

cc @pnkfelix @rust-lang/compiler There's a release next week. Is there any hope of fixing this?

[pnkfelix]

Current investigation results:

• The item collector tries to include the Iterator::max (and Iterator::min) methods on a vtable that it is building for an Iterator whose items do not impement PartialEq nor PartialOrd (in this case, PackedNode and Option<PackedNode>). The item collector subsequently processes the bodies of the default implementations of fn max and adds a fulfillment obligation, TraitPredicate(<PackedNode as PartialEq>) and TraitPredicate(<PackedNode as PartialOrd>).
• So, I am trying to figure out why the item collector is not filtering out max/min since the Item here does not implement PartialOrd.

I don't myself know the direct way to disable item collection; I looked into it briefly but it was not obvious what parts were safe to "switch off." I hope @michaelwoerister can look at that in time for the release.

[eddyb]

As I explained on IRC, the trans item collector looks correct, and if it weren't there, building the vtable itself would fail for the same reason: meth::get_vtable_methods must be not doing what it's supposed to (filter out inapplicable methods).

[michaelwoerister]

building the vtable itself would fail for the same reason

So, I have disabled the collector on a local branch and the compiler does not crash then. Maybe trans takes additional measures to filter out methods when building vtables.

[eddyb]

@michaelwoerister That's odd, the code looks identical. But maybe I wasn't looking in the right place.