beta and nightly regression: type inference in closure

[gui1117]

on nightly and beta my code doesn't compile because the type of a value is unknown:

error: the type of this value must be known in this context
   --> app.rs:110:80
    |
110 |                 collision = collision.map_or(Some(c.clone()), |mut collision| {collision.push(c); Some(collision)});
    |                       

But it compiles on stable.

stable: rustc 1.17.0 (56124ba 2017-04-24)
beta: rustc 1.18.0-beta.1 (4dce672 2017-04-25)
nightly: rustc 1.19.0-nightly (6a5fc9e 2017-05-02)

[nagisa]

Quite likely to be XID – we allow ourselves to break code that relies of inference, because otherwise it would be impossible to add new trait implementations.

Still tagging as regression so the the cause could be confirmed.

[TimNN]

@nagisa: Out of curiosity, what does XID mean in this context?

Also, could this be a duplicate of #41677?

[nagisa]

@TimNN inference “breaking” due to new implementation(s) of trait(s).

EDIT: of course I typoed it, it is XIB.

[brson]

XIB = "expected impl breakage"

[nikomatsakis]

triage: P-high

We have to figure out the real cause here. Will investigate.

[nikomatsakis]

Based on a quick inspection of the code, I would guess that this is fallout from my PR #40570.

[nikomatsakis]

Minimal reproduction:

fn main() {
    let mut collision = None;
    collision = collision.map_or(Some(22_u32), |c| Some(c.saturating_add(1)));
}

Not yet sure which PR is at fault, but #40570 still seems like a likely candidate. Note that the inference here is extremely fragile; removing the collision = collision.map_or... line and just changing to collision.map_or(...) breaks it, for example. So it could be that we changed the order of unifying the return types or something else.

@thiolliere -- btw, you probably figured this out, but a workaround for now would be to label the type of collision explicitly as Option<Collision>.

[nikomatsakis]

OK, so, I think the problem is specifically due to me fixing #18653 (as part of #40570). I believe what's happening is that, when we call map_or, we have an expected result of Option<?A>. We deduce an expected type for the first argument of Option<?B> -- I suspect we used to deduce Option<?A>. In any case, the type of Some(22_u32) doesn't wind up constraining collision.

It may be that the problem is that, in expected_inputs_for_expected_output(), we return without creating a "subtyping" relationship between ?A and ?B. (We just drop the subtyping predicate on the ground, I think.) But I'm not sure if modifying that routine is the right thing to do.

[nikomatsakis]

OK, I did a build before #40570, and my hypothesis is correct: expected_inputs_for_expected_output() was (incorrectly) forcing the return type to be equal to the input type. However, the current behavior seems a bit looser than it has to be, too. If we preserved the subtyping predicates, then this example would work again. But somehow that makes me nervous. Trying to put my finger on why.

[arielb1]

@nikomatsakis

I think we had that discussion on the PR - "this function is already a total hack, but I'm afraid this makes behavior depend on the mood of the union-find algorithm: if a set of (possibly-preexisting) type variables is equated and returned, we'll return one of them "at random""

[nikomatsakis]

TL;DR -- I'm inclined to call this a "not fix". It is a result of fixing #18653, which was a bug where inference would not give itself the required "degrees of freedom" in some cases to find a correct solution. As a result of this, we were able to (correctly, in this case, but not in general) propagate type information from the return value to the expected input types more aggressively in the older compiler than we do now.

It is plausible that we could reproduce the "subtyping" or coercion relationship between the type of the output and the first argument -- and of course we will enforce it eventually, the question is how early we do so (i.e., do we enforce it before we type-checking the closure). But this is a non-trivial problem, I think. When figuring out the "expected input types for output type", we'd have to figure out what portion of the general trait obligations to propagate forward, and it's not obvious that these are limited to subtypes. I'm not very comfortable with doing that without more refactorings making it clear what the longer term plan is.

[nikomatsakis]

Per the previous comment, I'm going to close this issue as "working as expected". @thiolliere, I apologize for the regression and appreciate the bug report. (I see you've already patched your master branch, otherwise I'd open a PR with the fix.)