Function parameter type resolution incorrect when multiple generics used

[ambaxter]

I tried this code:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9788298bae9b348de0833cd9b125c70e

use smallvec::SmallVec;
use std::iter::repeat_n;
use std::iter::RepeatN;
use std::ops::Index;

#[derive(Debug, Copy, Clone)]
pub enum EndMasks {
    L(u8),
    R(u8),
    BOTH(u8, u8),
}

#[derive(Debug, Copy, Clone)]
pub struct FindResults {
    index: usize,
    end_masks: EndMasks,
}

pub enum FindEnds<F>
where
    F: Fn(u8, u8) -> Option<(u8, u8)>,
{
    Either(u8, u8),
    Both(F),
}

pub trait LenTrait {
    fn len(&self) -> usize;
}

impl LenTrait for [u8] {
    fn len(&self) -> usize {
        self.len()
    }
}

impl LenTrait for Vec<u8> {
    fn len(&self) -> usize {
        self.len()
    }
}

#[derive(Debug, Clone, Copy)]
pub struct BMRepeatPattern {
    byte: u8,
    len: usize,
}

impl BMRepeatPattern {
    #[inline]
    pub fn new(byte: u8, len: usize) -> BMRepeatPattern {
        BMRepeatPattern { byte, len }
    }
}

impl LenTrait for BMRepeatPattern {
    #[inline]
    fn len(&self) -> usize {
        self.len
    }
}

impl Index<usize> for BMRepeatPattern {
    type Output = u8;
    #[inline]
    fn index(&self, idx: usize) -> &u8 {
        assert!(idx < self.len);
        &self.byte
    }
}

impl<'a> IntoIterator for &'a BMRepeatPattern {
    type Item = &'a u8;
    type IntoIter = RepeatN<&'a u8>;

    fn into_iter(self) -> Self::IntoIter {
        repeat_n(&self.byte, self.len)
    }
}

#[derive(Debug, Clone, Copy)]
pub struct BMRepeatBadCharShiftMap {
    pattern: BMRepeatPattern,
}

impl BMRepeatBadCharShiftMap {
    #[inline]
    pub fn new(pattern: BMRepeatPattern) -> Self {
        Self { pattern }
    }
}

impl Index<u8> for BMRepeatBadCharShiftMap {
    type Output = usize;

    fn index(&self, index: u8) -> &Self::Output {
        if self.pattern.byte == index {
            &0
        } else {
            &self.pattern.len
        }
    }
}

#[derive(Debug)]
pub struct BMRepeat {
    bad_char_shift_map: BMRepeatBadCharShiftMap,
    pattern: BMRepeatPattern,
}

impl BMRepeat {
    pub fn new(byte: u8, len: usize) -> BMRepeat {
        let pattern = BMRepeatPattern::new(byte, len);
        let bad_char_shift_map = BMRepeatBadCharShiftMap { pattern };
        BMRepeat {
            bad_char_shift_map,
            pattern,
        }
    }
}


impl BMRepeat {
    pub fn find_first_in<'a, T, F>(&'a self, text: &'a T, e: FindEnds<F>) -> Option<FindResults>
    where
        T: Index<usize, Output = u8> + LenTrait + ?Sized,
        &'a T: IntoIterator<Item = &'a u8>,
        <&'a T as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
        F: Fn(u8, u8) -> Option<(u8, u8)>,
    {
        find_spec(text, &self.pattern, &self.bad_char_shift_map, 1, e)
            .first()
            .copied()
    }
}

pub fn find_spec<'a, TT: 'a, TP: 'a, F>(
    text: &'a TT,
    pattern: &'a TP,
    bad_char_shift_map: &BMRepeatBadCharShiftMap,
    limit: usize,
    e: FindEnds<F>,
) -> SmallVec<[FindResults; 1]>
where
    TT: Index<usize, Output = u8> + LenTrait + ?Sized,
    &'a TT: IntoIterator<Item = &'a u8>,
    <&'a TT as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
    TP: Index<usize, Output = u8> + LenTrait + ?Sized,
    &'a TP: IntoIterator<Item = &'a u8>,
    <&'a TP as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
    F: Fn(u8, u8) -> Option<(u8, u8)>,
{
    unimplemented!()
}

fn main() {
    
}

I expected to see this happen:

Compiler correctly identifies the types used in the function

Instead, this happened:

error[E0308]: mismatched types
   --> src/main.rs:136:25
    |
129 |     pub fn find_first_in<'a, T, F>(&'a self, text: &'a T, e: FindEnds<F>) -> Option<FindResults>
    |                              - expected this type parameter
...
136 |         find_spec(text, &self.pattern, &self.bad_char_shift_map, 1, e)
    |         ---------       ^^^^^^^^^^^^^ expected `&T`, found `&BMRepeatPattern`
    |         |
    |         arguments to this function are incorrect
    |
    = note: expected reference `&T`
               found reference `&BMRepeatPattern`
note: function defined here
   --> src/main.rs:142:8
    |
142 | pub fn find_spec<'a, TT: 'a, TP: 'a, F>(
    |        ^^^^^^^^^
143 |     text: &'a TT,
144 |     pattern: &'a TP,
    |     ---------------

This error is fixed if I explicitly set the function types

    pub fn find_first_in<'a, T, F>(&'a self, text: &'a T, e: FindEnds<F>) -> Option<FindResults>
    where
        T: Index<usize, Output = u8> + LenTrait + ?Sized,
        &'a T: IntoIterator<Item = &'a u8>,
        <&'a T as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
        F: Fn(u8, u8) -> Option<(u8, u8)>,
    {
        find_spec::<T, BMRepeatPattern, F>(text, &self.pattern, &self.bad_char_shift_map, 1, e)
            .first()
            .copied()
    }

Meta

rustc --version --verbose:

rustc --version --verbose
rustc 1.83.0 (90b35a623 2024-11-26)
binary: rustc
commit-hash: 90b35a6239c3d8bdabc530a6a0816f7ff89a0aaf
commit-date: 2024-11-26
host: aarch64-apple-darwin
release: 1.83.0
LLVM version: 19.1.1

This behavior also exists in Beta and Nightly.

[ambaxter]

I was able to shrink down the example to something closer to an mcve

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=4761ecef545a68203c282d7ccf8b0600

use std::ops::Index;

struct Reproducer {
    pattern: &'static [u8],
    bad_char_shift_map: Vec<u8>,
}

impl Reproducer {
    pub fn find_first_in<'a, T, F>(&'a self, text: &'a T, e: F)
    where
        T: Index<usize, Output = u8> + ?Sized,
        &'a T: IntoIterator<Item = &'a u8>,
        <&'a T as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
        F: Fn(u8, u8) -> Option<(u8, u8)>,
    {
        // This works
        //find_spec::<T, [u8], F>(text, self.pattern, &self.bad_char_shift_map, 1, e)
        find_spec(text, self.pattern, &self.bad_char_shift_map, 1, e)
    }
}

pub fn find_spec<'a, TT: 'a, TP: 'a, F>(
    _text: &'a TT,
    _pattern: &'a TP,
    _bad_char_shift_map: &Vec<u8>,
    _limit: usize,
    _e: F,
) where
    TT: Index<usize, Output = u8> + ?Sized,
    &'a TT: IntoIterator<Item = &'a u8>,
    <&'a TT as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
    TP: Index<usize, Output = u8> + ?Sized,
    &'a TP: IntoIterator<Item = &'a u8>,
    <&'a TP as IntoIterator>::IntoIter: Sized + DoubleEndedIterator + ExactSizeIterator,
    F: Fn(u8, u8) -> Option<(u8, u8)>,
{
    unimplemented!()
}

fn main() {}

[ambaxter]

I think this is the smallest I can make it
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=06a59cd54429fe1b6293229db27a41cf

pub fn r0<'a, T>(p0: &'a T, p1: &'a [u8])
    where
        &'a T: IntoIterator<Item = &'a u8>,
    {
        // This works
        //r1::<T, [u8]>(p0, p1)
        r1(p0, p1)
    }

pub fn r1<'a, TT: 'a, TP: 'a>(
    _tt: &'a TT,
    _tp: &'a TP,
) where
    &'a TT: IntoIterator<Item = &'a u8>,
    &'a TP: IntoIterator<Item = &'a u8>,
{
    unimplemented!()
}

The error is currently:

error[E0308]: mismatched types
  --> src/lib.rs:7:16
   |
1  | pub fn r0<'a, T>(p0: &'a T, p1: &'a [u8])
   |               - expected this type parameter
...
7  |         r1(p0, p1)
   |         --     ^^ expected `&T`, found `&[u8]`
   |         |
   |         arguments to this function are incorrect
   |
   = note: expected reference `&T`
              found reference `&'a [u8]`
note: function defined here
  --> src/lib.rs:10:8
   |
10 | pub fn r1<'a, TT: 'a, TP: 'a>(
   |        ^^
11 |     _tt: &'a TT,
12 |     _tp: &'a TP,
   |     -----------

For more information about this error, try `rustc --explain E0308`.

[ambaxter]

@jieyouxu is there anything else needed?

[adwinwhite]

Simpler.

pub struct Wrap<T>(T);
pub trait MyTrait {}
impl MyTrait for Wrap<u8> {}

pub fn parent<T>(_a: T, b: u8)
where
    Wrap<T>: MyTrait,
{
    child(b)
    // child::<u8>(b) // this compiles.
}

pub fn child<U>(b: U)
where
    Wrap<U>: MyTrait,
{
    unimplemented!()
}

The cause is that the type parameter of child is resolved to T from caller bounds during solving its trait predicates.
Normally, the type parameter shouldn't be resolved until argument coercions.

I believe this is a duplicate of #134854.

[adwinwhite]

More fundamentally, the problem is that ParamCandidate is always preferred over ImplCandidate in winnowing, and once ParamCandidate is found, subsequent candidates are ignored.

This is an old issue #24066.