Type derivation problem


#1

I can’t get the following to compile — the compiler won’t resolve rng.gen() to bool in the first use. Interestingly if the where bound is removed the compiler can resolve this use of gen, but obviously the second use is invalid without the where bound.

Playground link

/// Uniform value distribution
pub struct Uniform;

/// A random number generator.
pub trait Rng {
    fn gen<T>(&mut self) -> T where Self: Sized, Uniform: Distribution<T> {
        Uniform.sample(self)
    }
}

/// Types (distributions) that can be used to create a random instance of `T`.
pub trait Distribution<T> {
    /// Generate a random value of `T`, using `rng` as the
    /// source of randomness.
    fn sample<R: Rng>(&self, rng: &mut R) -> T;
}

impl Distribution<bool> for Uniform {
    fn sample<R: Rng>(&self, rng: &mut R) -> bool {
        // omitted for brevity
        unimplemented!()
    }
}

impl<T> Distribution<Option<T>> for Uniform where Uniform: Distribution<T> {
    fn sample<R: Rng>(&self, rng: &mut R) -> Option<T> {
        // Compiler can't resolve T==bool here, unless the
        // Uniform: Distribution<T> constraint is removed
        // (in which case the second use of gen() fails).
        if rng.gen() {
            Some(rng.gen())
        } else {
            None
        }
    }
}

#2

You can type hint the gen call in the if statement so type inference selects the right target:

if rng.gen::<bool>() {
    Some(rng.gen())

#3

Sounds like you’re running into a known limitation of type inference, which is that it tries very aggressively to use the existing where bounds when inferring type parameters. There are links to issues describing this effect here.


#4

I don’t really see an issue with compiler’s complaints here. The single method is calling gen() twice, with two different contexts and target types (once for the if check and another for the return value). I don’t have an issue with it asking to be explicit if we want to target different types there.


#5

I don’t see this argument. I call the same method with different inferred type parameters all the time. The way type inference crumbles on gen() in that method is the exception, not the rule.

trait Arbitrary {
    fn arbitrary() -> Self;
}

fn arby<T: Arbitrary>() -> T { Arbitrary::arbitrary() }

//------------------------------------------

struct Bee;
struct Cee;
struct Ay(Bee, Cee);

impl Arbitrary for Bee { fn arbitrary() -> Self { Bee } }
impl Arbitrary for Cee { fn arbitrary() -> Self { Cee } }
impl Arbitrary for Ay {
    fn arbitrary() -> Self {
        // compiler has no problem understanding
        // that this is 'Ay(arby::<Bee>(), arby::<Cee>())'
        Ay(arby(), arby())
    }
}

#6

This example is different because Ay has clear type targets: Bee and Cee. Unless you’re suggesting the compiler should always infer bool if a method call is part of if statement?


#7

Unless you’re suggesting the compiler should always infer bool if a method call is part of if statement?

Yes. What is the issue with this? Rust does not have polymorphic if.

The following still compiles fine.

struct Bee;
struct Cee;
struct Ay(Bee, Cee);

impl Arbitrary for bool { fn arbitrary() -> Self { true } }
impl Arbitrary for Bee { fn arbitrary() -> Self { Bee } }
impl Arbitrary for Cee { fn arbitrary() -> Self { Cee } }
impl Arbitrary for Ay {
    fn arbitrary() -> Self {
        if arby() {
            Ay(arby(), arby())
        } else { unreachable!() }
    }
}

#8

Explicitness - maybe you didn’t intend to do that? Rust is all about being explicit (even widening casts require explicit opt-in) and I don’t see such a big deal with this, personally.


#9

Okay, but it seems to me that you and the compiler have completely different reasons for finding it disagreeable.

Given this:

// The trait is written this way so that the problem actually surfaces;
// stuff like `where A: Arbitrary, B: Arbitrary` doesn't cause issues for
// inferring `A`.  You need something like `where T: Arbitrary<A>`.
trait Arbitrary<A> {
    fn arbitrary() -> A;
}

struct Bee;
struct Cee;

impl Arbitrary<bool> for () { fn arbitrary() -> bool { true } }
impl Arbitrary<Bee> for () { fn arbitrary() -> Bee { Bee } }
impl Arbitrary<Cee> for () { fn arbitrary() -> Cee { Cee } }

fn arby<T>() -> T where (): Arbitrary<T> { <() as Arbitrary<_>>::arbitrary() }

and the following body:

if arby() {
    // do nothing
}

Ay(arby(), arby())   // these might be monomorphic or generic types

Everything is fine when Ay has no generics:

struct Ay(Bee, Cee);

impl Arbitrary<Ay> for () {
    fn arbitrary() -> Ay {
        if arby() {}       // okay
        Ay(arby(), arby()) // okay
    }
}

Everything is fine when Ay has two generics:

struct Ay<B, C>(B, C);

impl<B, C> Arbitrary<Ay<B, C>> for ()
    where (): Arbitrary<B>, (): Arbitrary<C>,
{
    fn arbitrary() -> Ay<B, C> {
        if arby() {}       // okay
        Ay(arby(), arby()) // okay
    }
}

But everything goes kaboom when Ay has one generic:

struct Ay<C>(Bee, C);

impl<C> Arbitrary<Ay<C>> for ()
    where (): Arbitrary<C>,
{
    fn arbitrary() -> Ay<C> {
        if arby() {}       // expected bool, found type parameter
        Ay(arby(), arby()) // expected struct `Bee`, found type parameter
    }
}

play


#10

Very possible. AFAIK, there’s no spec on how type inference actually works so it’s hard to say what is supposed to happen. As your examples demonstrate, it seems somewhat arbitrary (how fitting!) which of them work and which don’t.

Is there an explanation for why the example with a single generic doesn’t work? Is it a bug? Is it a limitation?


#11

See the discussion starting from Bluss’ post here: https://github.com/rust-lang/rust/pull/33108#issuecomment-212874598

(you can follow the github cross-references to other pages, but discussion on this issue is sparse…)

Birds-eye view from what I gather:

  • Type inference uses where A: Trait<T> bounds very agressively when trying to infer T.
  • This is necessary to make Into nice.
  • ???

Actually, I was surprised to see the two-generic case work. From my prior encounters with this problem, I figured it would arbitrarily pick one of the two where bounds and then fail like the one-generic case.


#12

Thanks for the suggestion to specify the type; that works — but this seems like a compiler bug to me. I didn’t know how to describe it precisely enough to open a bug report however.

Rust has always been about explicitness where required and auto-deduction where not. Since the type of an if condition is well-defined that code is no different than let cond: bool = rng.gen(); as far as I can see.


#13

Thanks. After skimming that discussion I have to say I also find it odd that the 2 generics case works. I actually find this issue somewhat frustrating - there’s virtually zero chance that one can look at these variations and know if they’ll compile or not; that’s not a good place to be.

Should this be brought up on Rust internals? I wonder if there’s any more recent thinking/analysis of this by the compiler folks (there appeared to be disagreement between them in that thread above).


#14

Well it does look like this bug report (linked under @ExpHP’s first link) is the same issue, so I don’t think another report is needed: https://github.com/rust-lang/rust/issues/24066


#15

Yeah I agree now after seeing @ExpHP’s examples and the discussion he linked. I occasionally run into cases where I need to type hint and I just do that without thinking about it too much, mostly because I don’t have a good idea of how inference actually works (or rather, supposed to work). Right now, beyond trivial cases, it seems like black magic - some stuff works, some doesn’t and you can’t tell if it’s a bug, limitation in the impl, or a principled design/restriction.


#16

That’s another 2 yr old issue. But I was suggesting a Rust internals forum thread, not another github issue.


#17

As I understand it most development happens on GitHub. If you want to get involved yourself I’d recommend either dig into the code or ask on IRC, but I don’t have the time myself.


#18

I think it’d be good to have that discussion. I’ve been worrying about it myself, wondering how a second implementation of the rust language could ever come into existence with how arbitrary type inference feels…

Right now, beyond trivial cases, it seems like black magic - some stuff works, some doesn’t and you can’t tell if it’s a bug, limitation in the impl, or a principled design/restriction.

I share these feelings precisely.


#19

If you are referring to the limits of the type solver, Matsakis’ blog posts (especially those on Chalk) may be of interest.