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.

[michaelwoerister]

Maybe it calls meth::get_vtable_methods with different parameters for some reason?

[michaelwoerister]

Hm, it seems that cannot reproduce the issue at all (with or without collector) with the current HEAD of master. Is it possible that this is fixed already? With the latest nightly from rustup (ad7fe65 2016-06-23) it does crash.

[arielb1]

This was fixed between 7d8e6dd3bfdec0b0a6f47b10966673f88a9242f5 and ea0dc9297283daff6486807f43e190b4eb561412.

[pnkfelix]

(I can't believe I forgot to update my copy of master before I spent yesterday afternoon investigating...)

Thanks @arielb1 for narrowing it down!

I did further bisection this morning, and determined it was introduced between
af2fe63 (which still ICE'd) and
b42884f (which no longer ICE's).

The one that no longer ICE's is the merge of #34419

---

In hindsight, its clear why #34419 fixes this this case: Iterator::max (and Iterator::min) both take self by value, so they end up having Self: Sized prerequisites.

(My suspicion is that we should be able to come up with a similar bit of code that exposes the old ICE that I was investigating. But in the meantime, my recommendation is that we beta-nominate #34419 since that seems like a really safe PR to backport to beta.)

[pnkfelix]

Yes I have managed to make a new test case that continues to expose the bug:

https://play.rust-lang.org/?gist=9398442e3b7aaeb387e5b3630fd0c8d3&version=nightly&backtrace=0

I'll update the description to use this variant instead.

(I know the playpen is using a version of nightly that predates #34419; I verified this against a local build of rustc that has #34419 incorporated, and it still ICE's there.)

@michaelwoerister could you look into how your item-collection-disabled branch behaves against the above gist of code?

[pnkfelix]

(Note @eddyb has predicted that trans itself will fail during vtable construction even if item-collection were disabled; nonetheless, its worth verifying that prediction.)

[michaelwoerister]

@pnkfelix Disabling the collector makes the ICE go away. Things do not fail later during vtable construction. Which is interesting, since the code really looks very similar.

EDIT: Note that the above applies to the updated version of the code under test.

[eddyb]

@michaelwoerister On IRC @arielb1 said he'd found the bug in the obligation "forest" handling of nested obligations which have already failed and that he's working on a fix.

[eddyb]

@michaelwoerister Maybe without the collector the obligation that poisons the cache is never tested?
That is, (PackedNode, Option<PackedNode>): Ord (which fails, but also leaves Option<PackedNode>: Ord in the cache, wrongly).

[michaelwoerister]

Maybe without the collector the obligation that poisons the cache is never tested?

Oh, so this would be a mutable state problem? I know little about how obligation caches work (I should probably start learning more about that part of the compiler).

[michaelwoerister]

Just FYI, if you want to test with the collector disabled: It suffices to replace the body rustc_trans::collector::collect_crate_translation_items() with return (FnvHashSet(), InliningMap::new());. Subsequent stages of trans can handle the set of translation items being empty.

[eddyb]

@michaelwoerister The cache is global with a simple check that the obligation has no inference variables. Once that mistakenly successful Option<PackedNode>: Ord gets into the cache, it succeeds forever, even if PackedNode: Ord still doesn't succeed and neither of them can be selected.

[eddyb]

@michaelwoerister Intuitively constructed reproduction: https://play.rust-lang.org/?gist=95f6ad7e16621d718490d4f81e8eec23&version=nightly&backtrace=0.

You can try to add things that would fail but cause some sub-obligations to succeed, like duplicating the foo method or having more traits like this, etc.