Rust can't infer appropriate generics for function when it should

[TheRawMeatball]

I was working on some generic code when I hit this bug, so I made this MRE:

use std::borrow::Borrow;

trait TraitA<'a> {
    type Return;
    fn get(&'a self) -> Self::Return;
}
trait TraitB<T>
where
    for<'a> <Self::TrA as TraitA<'a>>::Return: Borrow<T>,
{
    type TrA: for<'a> TraitA<'a>;
}
fn takes_trait_b<T: TraitB<String>>(x: T)
where
    for<'a> <T::TrA as TraitA<'a>>::Return: Borrow<String>,
{
}

impl<T: 'static> TraitB<T> for T {
    type TrA = Returner<T>;
}

struct Returner<T>(T);
impl<'a, T: 'static> TraitA<'a> for Returner<T> {
    type Return = &'a T;

    fn get(&'a self) -> Self::Return {
        &self.0
    }
}

fn test() {
    takes_trait_b::<String>(String::new());
    takes_trait_b(String::new());
}

(playground link: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=ce2ea68678f61b329a6cec59310c1aea)

I'd expect both calls to takes_trait_b to succeed, but the second call doesn't as rust seemingly tries to uphold the where clause for any possible T

This has been observed on rustc 1.57.0-nightly (aa8f2d432 2021-09-18)

Adding two extra where clauses makes both calls compile on stable, but this example still fails on nightly: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=aaa115e139635787f9b033a1418c7f06

Seems like a regression.

[Mark-Simulacrum]

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=aaa115e139635787f9b033a1418c7f06 is failing on beta but working on stable, so tagging as a beta regression.

[camelid]

Seems like it could be related to #85499, so cc @jackh726.

[jackh726]

Looking into this. From what I can tell, the version of this without the where clause doesn't compile on stable nor nightly (though the error is slightly different). However, while the version with the where clauses does compile on stable, it's actually not callable (because we can prove the where clause). On nightly, we just get a more eager error.

This is still a bug (and I'm looking into it), but I don't think it's strictly a regression. You can't actually use any less code than before.

[Mark-Simulacrum]

This is still a bug (and I'm looking into it), but I don't think it's strictly a regression. You can't actually use any less code than before.

I think this certainly mitigates the likely impact of the regression, but it wouldn't surprise me too much if there exists "real world" code that is just uncallable (and not tested, so not discovered yet).

I think if we can fix the regression on nightly and backport it, that would be ideal.

[jackh726]

Okay, so I investigated this a bit. It's kind of rough.

My work-through

• We start by checking the expr takes_trait_b(()) with NoExpectation
• Because the function takes one generic, we create a new variable _#0t
• We then add the required obligations:
  • We care about Binder(TraitPredicate(<<<_#0t as TraitB<()>>::TrA as TraitA<ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a) })>>::Return as std::borrow::Borrow<()>>), [Region(BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a))])
  • We normalize this, generating Binder(TraitPredicate(<<_#2t as TraitA<ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a) })>>::Return as std::borrow::Borrow<()>>), [Region(BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a))])
    • And the following obligations:
      • Binder(ProjectionPredicate(ProjectionTy { substs: [_#0t, ()], item_def_id: DefId(0:12 ~ issue_89242[81f3]::TraitB::TrA) }, _#1t), []) (this one is unused, I think)
      • Binder(ProjectionPredicate(ProjectionTy { substs: [_#0t, ()], item_def_id: DefId(0:12 ~ issue_89242[81f3]::TraitB::TrA) }, _#2t), [])
      • Importantly, we can't replace <_#2t as TraitA<ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a) })>>::Return with an inference var + obligation, because we reference a late-bound region
• We find that the type of the expr is fn(_#0t) {takes_trait_b::<_#0t>}
• We then try to get the expr type, by calling structurally_resolved_type
  • That calls resolve_vars_with_obligations
  • Which calls select_obligations_where_possible
• We try to select Binder(TraitPredicate(<<_#2t as TraitA<ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a) })>>::Return as std::borrow::Borrow<()>>), [Region(BrNamed(DefId(0:16 ~ issue_89242[81f3]::takes_trait_b::'a), 'a))])
  • "failed eq_trait_refs due to expected associated type, found &mut _#3t``"
  • "failed eq_trait_refs due to expected (), found associated type"
  • "failed eq_trait_refs due to expected associated type, found &_#3t``"
• None of these are ambiguous, so we say that this trait is unimplemented
  • We then error
• Normally, we just wouldn't make progress and then in confirm_builtin_call we would call check_argument_types, which then we relate the inputs
  • We then could make progress because we would set _#2t to ()

Basically, are potentially four ways forward

1. Revert Normalize projections under binders #85499. Imo, this is a non-starter. That PR solves a lot of issues and the severity of this issue is imo low or medium, given that I don't think usable code could be created before anyways.
2. Lazy normalization. One aspect of the problem essentially boils down to us trying to equate a projection with something else. I'll put "being able to be defer projecting a projection when there a bound vars i.e. using an inference var" under this, since I think ultimately lazy normalization will solve both issues.
3. Make structurally_resolved_type not need to select obligations where possible, or otherwise just skip Unimplemented. Not sure this will work. Just commenting out select_where_possible doesn't build core.
4. Rearrange the type checking code here to be able to subtype the input args with the new substs of the expr. Again, not sure if this is possible. The current code is set up in such a way that we can do autoderef first before doing expectation.

[apiraino]

Discussed during the T-compiler triage meetings here and here. Consensus seems to be that it can be let slip.

@rustbot label -I-nominated

[jackh726]

Stumbled across this again. This is basically #89196, because we try to prove the bound before we complete function resolution. It's a little different though, so I'll mark this to get included as a known-bug.