Why type inference fails with generic trait restrictions?

Sorry if the title is a bit vague, but I wouldn't know how to phrase it precisely. Also, this question might have been discussed already, but once again I don't know what to search for exactly, so I couldn't find anything related. So, the following code compiles:

use std::fs::File;
use std::io::{self,Read,BufReader,Error,ErrorKind};

// IO

trait ReadNumeric<T> {
    fn read_numeric(&mut self) -> io::Result<T>;
}

// Specialized for i32
impl<R: Read> ReadNumeric<usize> for BufReader<R> {
    fn read_numeric(&mut self) -> io::Result<usize> {
        let mut buf = [0; 4];
        self.read_exact(&mut buf)?;
        let x = usize::try_from(u32::from_ne_bytes(buf));
        x.map_err(|e| Error::new(ErrorKind::InvalidData, e))
    }
}

impl<R: Read> ReadNumeric<f64> for BufReader<R> {
    fn read_numeric(&mut self) -> io::Result<f64> {
        let mut buf = [0; 8];
        self.read_exact(&mut buf)?;
        Ok(f64::from_ne_bytes(buf))
    }
}

trait ReadVector<T> {
    fn read_vector(&mut self, n: usize) -> io::Result<Vec<T>>;
}

impl<T, R: ReadNumeric<T>> ReadVector<T> for R {
    fn read_vector(&mut self, n: usize) -> io::Result<Vec<T>> {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            v.push(self.read_numeric()?);
        }
        Ok(v)
    }
}

// Sparse matrices

struct Matrix<T> {
    data: Vec<T>,
    indices: Vec<usize>,
    indptr: Vec<usize>,
    shape: (usize, usize),
}


impl<T> Matrix<T> {
    fn read(path: &str) -> io::Result<Self>
        where BufReader<File>: ReadNumeric<usize> + ReadNumeric<T>
    {
        let mut f = BufReader::new(File::open(path)?);
        let rows = ReadNumeric::<usize>::read_numeric(&mut f)?;
        let cols = ReadNumeric::<usize>::read_numeric(&mut f)?;
        let nnz = ReadNumeric::<usize>::read_numeric(&mut f)?;
        Ok(Matrix {
            data: f.read_vector(nnz)?,
            indices: ReadVector::<usize>::read_vector(&mut f, nnz)?,
            indptr: ReadVector::<usize>::read_vector(&mut f, rows + 1)?,
            shape: (rows, cols),
        })
    }
}

fn main() {
    let _m = Matrix::<f64>::read("matrix.dat");
}

While if I drop the fully qualified syntax, the code does not compile any more (whether stable, or nightly):

impl<T> Matrix<T> {
    fn read(path: &str) -> io::Result<Self>
        where BufReader<File>: ReadNumeric<usize> + ReadNumeric<T>
    {
        let mut f = BufReader::new(File::open(path)?);
        let rows = f.read_numeric()?;
        let cols = f.read_numeric()?;
        let nnz = f.read_numeric()?;
        Ok(Matrix {
            data: f.read_vector(nnz)?,
            indices: f.read_vector(nnz)?,
            indptr: f.read_vector(rows + 1)?,
            shape: (rows, cols),
        })
    }
}

The compiler cannot deduce that it should use read_numeric<usize> for rows, cols, nnz, etc., albeit there is no ambiguity what types they should be. Say, (rows, cols) is used in the shape field, which has type (usize, usize). Is automatic type inference in this case something that can be added to the compiler, or are there design reason for why that can't be done?

Actually the problem happens when you have conflicting requirements.

I have changed your example a bit to show the difference between when it works and when it doesn't.

Make sure you have one restriction, not many
use std::fs::File;
use std::io::{self,Read,BufReader,Error,ErrorKind};

// IO

trait ReadNumeric<T> {
    fn read_numeric(&mut self) -> io::Result<T>;
}

// Specialized for i32
impl<R: Read> ReadNumeric<usize> for BufReader<R> {
    fn read_numeric(&mut self) -> io::Result<usize> {
        let mut buf = [0; 4];
        self.read_exact(&mut buf)?;
        let x = usize::try_from(u32::from_ne_bytes(buf));
        x.map_err(|e| Error::new(ErrorKind::InvalidData, e))
    }
}

impl<R: Read> ReadNumeric<f64> for BufReader<R> {
    fn read_numeric(&mut self) -> io::Result<f64> {
        let mut buf = [0; 8];
        self.read_exact(&mut buf)?;
        Ok(f64::from_ne_bytes(buf))
    }
}

trait ReadVector<T> {
    fn read_vector(&mut self, n: usize) -> io::Result<Vec<T>>;
}

impl<T, R: ReadNumeric<T>> ReadVector<T> for R {
    fn read_vector(&mut self, n: usize) -> io::Result<Vec<T>> {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            v.push(self.read_numeric()?);
        }
        Ok(v)
    }
}

// Sparse matrices

struct Matrix<T, S: Copy = usize> where usize: From<S> {
    data: Vec<T>,
    indices: Vec<S>,
    indptr: Vec<S>,
    shape: (S, S),
}


impl<T, S: Copy> Matrix<T, S> where usize: From<S> {
    fn read(path: &str) -> io::Result<Self>
        where BufReader<File>: ReadNumeric<S> + ReadNumeric<T>
    {
        let mut f = BufReader::new(File::open(path)?);
        let rows: S = f.read_numeric()?;
        let cols = f.read_numeric()?;
        let nnz = f.read_numeric()?;
        Ok(Matrix {
            data: ReadVector::<T>::read_vector(&mut f, nnz)?,
            indices: ReadVector::<S>::read_vector(&mut f, nnz)?,
            indptr: ReadVector::<S>::read_vector(&mut f, rows.into())?,
            shape: (rows, cols),
        })
    }
}

Note then when there are too many restrictions on the same variable you may still have to specify the type (rows: S in my version).

Thanks for taking a look at the code.

This I don't see. rows, cols, nnz can be one type only (in my original example), because they are used as arguments to functions or structures that require them to be usize. They are not used in any other functions with generic types. So, at first glance there is no conflict here. As far as I see, a compiler could resolve the correct type, in principle.

Good news: I have made you code compileable.

But then spent whole hour trying to understand just why it's compileable and why the original code is not compileable.

The thing which really confuses me most is difference in behavior between read_vector and read_numeric.

Somehow there are no ambiguity with read_vector, but read_numeric is ambiguous if there are two of them.

Tried to find documentation which would describe type inference rules, but failed to find anything which may explain that difference.

Eventually asked in the IRLO: maybe there someone would be able to point to the doc.

Looks like issue 41756.

Fails: where BufReader<File>: ReadNumeric<usize> + ReadNumeric<T>
Works: where BufReader<File>: ReadNumeric<T> + ReadNumeric<usize>

Yes, that's exactly it. But is that behavior documented somewhere?

You may say it's a feature, but still it's good idea to explain how one is supposed to use trait bounds.

Am I correct that you need to list the most generic ones first and then more specific?

P.S. I'm liking gccrs idea more and more. The more one plays with the Rust the more there are small yet annoying warts like that. Hopefully alternate implementation would expose them and they would, at least, be documented if not fixed.

There's no generic impl so issue 24066 might be technically more correct. See the last comment there for a bunch of examples. The last two examples fail if the order is reversed (to put the more specific ones first).

As far as I know it's not documented outside of the collection of issues... but parts of it may be in some pre-1.0 RFCs or blog posts. Apparently aspects of it can't change, but I imagine total inference failure like happened hear could be improved. (Maybe Chalk will help.) I agree that it should be properly spec'd and documented (with clarity on which parts can't change and which might).

I'm honestly not sure if that's always good advice or not.

Why? I agree that, most likely, it couldn't be changed before year 2024, but it looks to me precisely what can be changed in a new version of Rust: confusing behavior happens before monomorphization, not after, thus different rules in different crates should work.

Three years sound about right to agree on how the whole thing is supposed to actually work.

If you have code that compiles down to different types on different editions, that's a "split the ecosystem" change. #41756 illustrates how a different algorithm (reverse the where clauses) could infer a different type, but still compile. (It doesn't need to be contained to the function body; consider if it returned the result behind a dyn Trait or other erasure.)

But isn't that what happens with into_iter in Rust 2021?

I don't think going from one implementation which may pick “wrong” implementation to another which may pick another “wrong” implementation would be an improvement.

What would work is if we may detect conflicts when there are two (or more) possibilities and resolution just works if there are no conflicts.

Then it would be merely a breaking change: some code would be compileable in one edition, some in the other edition, but for the cases where both compile there are no conflict.

If this would prove out to be impossible or infeasible then it would be better to just document the behavior and explain why it works like that, of course: one confusing behavior is better than two, anyway.

Yeah, that's true. I guess the boundaries of acceptability are unclear to me.

Linus rules, I assume:

The rule is basically "we never break user space".
But the "out" to that rule is that "if nobody notices, it's not broken". In a few years? Who knows?
So breaking user space is a bit like trees falling in the forest. If there's nobody around to see it, did it really break?

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.