Presence of std::simd sometimes breaks type inference

[EFanZh]

I tried this code:

use std::mem;

pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
    let mut temp_cache = Vec::with_capacity(triangle.len());
    let mut cache = Vec::with_capacity(triangle.len());

    for row in triangle {
        temp_cache.resize(row.len(), 0);

        for (i, (target, source)) in temp_cache.iter_mut().zip(row).enumerate() {
            *target = match (cache.get(i.wrapping_sub(1)), cache.get(i)) {
                (None, None) => source,
                (None, Some(val)) | (Some(val), None) => source + val,
                (Some(left), Some(right)) => source + left.min(right),
            };
        }

        mem::swap(&mut cache, &mut temp_cache);
    }

    cache.into_iter().min().unwrap()
}

I expected to see this happen: The code compiles successfully.

Instead, this happened: The code failed to compile:

  --> src/lib.rs:11:36
   |
5  |     let mut cache = Vec::with_capacity(triangle.len());
   |         --------- consider giving `cache` the explicit type `Vec<T>`, where the type parameter `T` is specified
...
11 |             *target = match (cache.get(i.wrapping_sub(1)), cache.get(i)) {
   |                                    ^^^ cannot infer type for type parameter `T`
   |
   = note: type must be known at this point

For more information about this error, try `rustc --explain E0282`.
error: could not compile `playground` due to previous error

Playground link: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=446e975abb9c2a303485f483494a6512.

The code works fine with stable toolchain.

Meta

Rustc version: 1.58.0-nightly (2021-11-13 b416e38)

[SNCPlay42]

searched nightlies: from nightly-2021-10-16 to nightly-2021-11-14
regressed nightly: nightly-2021-11-14
searched commit range: e90c5fb...b416e38
regressed commit: 032dfe4

bisected with cargo-bisect-rustc v0.6.1

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo bisect-rustc --preserve --start=2021-10-16 

Bisected to #89167 - a big PR, I can't tell at a glance which addition is causing an ambiguity here.

@rustbot label regression-from-stable-to-nightly

[workingjubilee]

Yes, it's a known issue that the portable SIMD API's presence weakens type inference for some things by introducing some possible collisions. Breaking type inference is called out as not considered as backwards-incompatible change in RFC 1105.

I am still interested in seeing what breakage occurs, as it may justify adjusting what we do.

[antonok-edm]

Cross-posting another minimal example from #91378, which was bisected to #89167 as well.

This minimized code example:

fn main() -> Result<(), &'static str> {
    let a = 0usize;
    let b = &a;

    let _c: usize = {
        let d = &""
            .parse()
            .map_err(|_| "")?;
        b + d
    };

    Ok(())
}

should compile successfully.

Instead, I get the following 2 compiler errors:

error[E0277]: cannot add `&()` to `&usize`
 --> src/main.rs:9:11
  |
9 |         b + d
  |           ^ no implementation for `&usize + &()`
  |
  = help: the trait `Add<&()>` is not implemented for `&usize`

error[E0277]: the trait bound `(): FromStr` is not satisfied
    --> src/main.rs:7:14
     |
7    |             .parse()
     |              ^^^^^ the trait `FromStr` is not implemented for `()`
     |
note: required by a bound in `core::str::<impl str>::parse`
    --> /home/antonok/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/str/mod.rs:2247:21
     |
2247 |     pub fn parse<F: FromStr>(&self) -> Result<F, F::Err> {
     |                     ^^^^^^^ required by this bound in `core::str::<impl str>::parse`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `regression` due to 2 previous errors

[Mark-Simulacrum]

I'm not sure that this requires-nightly: the trait impls that affect inference are likely going to cause the same pain regardless of whether you're on nightly. The examples above also don't have any feature gates.

So I'm going to drop that label temporarily, but feel free to re-add it if we have evidence this does require nightly. In that case, it's probably not (yet) a regression and will only be one after something stabilizes(?).

[workingjubilee]

You're right, actually. I forgot that nightly is actually implicitly present and we just haven't shipped it yet (i.e. this will hit stable after the appropriate cut).

[eddyb]

Cross-posting another minimal example from #91378, which was bisected to #89167 as well.

This minimized code example:

If we allow a change of the trait involved _{(and ignore the weird () inference result - that's either an interaction with the ? operator or an unrelated bug)}, the full reduction looks like this:

fn main() {
    0usize + &Default::default();
}

Compiles on stable, ambiguous on nightly, due to the new impls allowing for multiple solutions to the usize: Add<&_> requirement.

The & is needed for it to compile at all, otherwise it was always ambiguous (or at least as far back as 1.0).

There's nothing that can be done here at the level of the operator overload impls themselves: a completely unknown type will not be narrowed now, whereas before it happened to be.

Maybe we shouldn't have let any of these examples compile before, but sadly I'm not aware of a heuristic that can tell "dangerous" cases of inference from "harmless" ones.

[eddyb]

Sorry, I forgot to look at the original example again. With this change, the error appears on stable:

- (None, Some(val)) | (Some(val), None) => source + val,
+ (None, Some(&val)) | (Some(&val), None) => source + val,

(or alternatively, dereferencing the val reference, i.e.: => source + *val)

So it's the same situation where (in this case) i32: Add<&$1> resolves to $1 = i32 because there's no other reference type you can add to an i32, on stable. The moment that changes, it goes out of the window.

---

Though the error is very misleading, because it points to the wrong part of the code that is affected - this example has enough information flowing through from source to target to infer the element types of both Vecs.

What seems to be breaking is the left.min(right) method call, which being the method call that it is, has to know the types at that moment - rewriting it to std::cmp::Ord::min(left, right) makes it compile again.
So there's a diagnostic bug there, IMO.

This is a pretty "compact" leap - the addition in one match arm makes a method call in another resolve. You can see that swapping the match arms produces the same (confusing) error again, on stable.

[workingjubilee]

This was reviewed in the T-libs-api meeting today, right now, and it was decided that we will need to land a revert of the relevant impls that follow a format roughly equivalent to

impl<const N: usize> Add<T> for Simd<T, N>
where
    T, N, Simd<T, N>, AndYourDog: ManySimdBounds, 
{
    type Output = Self;
    fn add(self, rhs: T) -> Self {
        self.add(Simd::splat(rhs))
    }
}

and, because this breakage has currently hit beta, beta backport it.

However, the backport should be deferred (not very long!) until after the next scheduled beta crater run (which is very soon to come, within a week) so we can see the amount of ecosystem breakage in play and understand the relevant mitigations we can take for landing these impls in the future, if any. Essentially, "Since we're here, we might as well see what all the broken cases actually are!" We have until January ~7, to make sure we don't miss the cut, but there will be no reason to wait that long.

Ideally we could land these in the future, but it may be a more distant one depending on the results of that and what may need to happen in order to accommodate these cases, if at all.

[workingjubilee]

Splats are dropped on nightly, at the moment.
Relevant crater run is happening in #91454

[Mark-Simulacrum]

Discussed in T-libs-api with crater results (see #91872); breakage was deemed higher than likely acceptable, so proceeding with the beta-backport and (already landed) revert on nightly makes sense.

The right replacement/API design was judged out of scope for the meeting (in particular, as it didn't have portable-simd folks in attendance :)

[m-ou-se]

This will be fixed by #91484 and its backport.

[pietroalbini]

Merged and backported, closing.