I'm trying to learn Rust by just reading the book and working through the problems in Advent of Code (the 2024 edition). Just to make it harder, I decided to practice TDD while I do it.
To test a function that reads from stdin and writes to stdout, I did it using generic types and traits, and when I got to test it against several inputs, I ended up writing a lot of redundant code.
Abstracting the problem details, I sketched an MVE that looks like what I wrote:
use std::io::{BufRead, Write};
pub fn count_lines<R, W>(reader: R, mut writer: W)
where
R: BufRead,
W: Write,
{
let mut count: u64 = 0;
for _ in reader.lines() {
count = count + 1;
}
write!(&mut writer, "{count}").expect("Couldn't write.");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn count_lines_gives_zero_on_empty_input() {
let input = b"";
let mut output = Vec::new();
count_lines(&input[..], &mut output);
let output = String::from_utf8(output).expect("Output was not in UTF-8");
let parsed: u64 = output.trim().parse().expect("Output should be a number.");
assert_eq!(parsed, 0);
}
#[test]
fn count_lines_gives_one_on_single_char() {
let input = b"a";
let mut output = Vec::new();
count_lines(&input[..], &mut output);
let output = String::from_utf8(output).expect("Output was not in UTF-8");
let parsed: u64 = output.trim().parse().expect("Output should be a number.");
assert_eq!(parsed, 1);
}
}
(just imagine a lot more test cases)
When I tried abstracting away the repeated code, I started facing some lifetime errors. This code:
use std::io::{BufRead, Write};
pub fn count_lines<R, W>(reader: R, mut writer: W)
where
R: BufRead,
W: Write,
{
let mut count: u64 = 0;
for _ in reader.lines() {
count = count + 1;
}
write!(&mut writer, "{count}").expect("Couldn't write.");
}
#[cfg(test)]
mod tests {
use super::*;
fn test_case<F>(input: &[u8], function: F, result: u64)
where
F: Fn(&[u8], &mut Vec<u8>),
{
let mut output = Vec::new();
function(input, &mut output);
let output = String::from_utf8(output).expect("Output was not in UTF-8.");
let parsed: u64 = output.trim().parse().expect("Output should be a number.");
assert_eq!(parsed, result);
}
#[test]
fn count_lines_gives_zero_on_empty_input() {
test_case(b"", count_lines, 0);
}
#[test]
fn count_lines_gives_one_on_single_char() {
test_case(b"a", count_lines, 1);
}
}
Gives the following errors on cargo test (the file is at src/lib.rs with the rest of the files unmodified from cargo init --lib .):
Compiling tryingrust v0.1.0 (/home/juan/downloads/tryingrust)
error: implementation of `Fn` is not general enough
--> src/lib.rs:27:6
|
27 | test_case(b"", count_lines, 0);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `Fn` is not general enough
|
= note: `fn(&'2 [u8], &mut Vec<u8>) {count_lines::<&'2 [u8], &mut Vec<u8>>}` must implement `Fn<(&'1 [u8], &mut Vec<u8>)>`, for any lifetime `'1`...
= note: ...but it actually implements `Fn<(&'2 [u8], &mut Vec<u8>)>`, for some specific lifetime `'2`
error: implementation of `Fn` is not general enough
--> src/lib.rs:27:6
|
27 | test_case(b"", count_lines, 0);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `Fn` is not general enough
|
= note: `fn(&[u8], &'2 mut Vec<u8>) {count_lines::<&[u8], &'2 mut Vec<u8>>}` must implement `Fn<(&[u8], &'1 mut Vec<u8>)>`, for any lifetime `'1`...
= note: ...but it actually implements `Fn<(&[u8], &'2 mut Vec<u8>)>`, for some specific lifetime `'2`
error: implementation of `FnOnce` is not general enough
--> src/lib.rs:27:6
|
27 | test_case(b"", count_lines, 0);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
|
= note: `fn(&'2 [u8], &mut Vec<u8>) {count_lines::<&'2 [u8], &mut Vec<u8>>}` must implement `FnOnce<(&'1 [u8], &mut Vec<u8>)>`, for any lifetime `'1`...
= note: ...but it actually implements `FnOnce<(&'2 [u8], &mut Vec<u8>)>`, for some specific lifetime `'2`
error: implementation of `FnOnce` is not general enough
--> src/lib.rs:27:6
|
27 | test_case(b"", count_lines, 0);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `FnOnce` is not general enough
|
= note: `fn(&[u8], &'2 mut Vec<u8>) {count_lines::<&[u8], &'2 mut Vec<u8>>}` must implement `FnOnce<(&[u8], &'1 mut Vec<u8>)>`, for any lifetime `'1`...
= note: ...but it actually implements `FnOnce<(&[u8], &'2 mut Vec<u8>)>`, for some specific lifetime `'2`
[…]
error: could not compile `tryingrust` (lib test) due to 8 previous errors
$
Note that I have ommited the four errors related to the second call of the test_case function, as they look the same as the previous four.
Question: how can I solve this error in this example? Ideally, I wouldn't need to change the function being tested count_lines, only test_case.
What I think I understand is that by leaving lifetimes unspecified (because I have no idea how they work), the compiler (or borrow-checker) just assumes the default, which is too generic. The function begin tested is not so generic, whatever that means.
Furthermore, the errors lead me to believe the problem relates to the lifetime of the writer parameter (equivalently, the output argument). But I don't understand what is the issue. Both values should live long enough to be used throughout the program.
To demonstrate the problem you're seeing more clearly, I'm going to use the following cut-down example, which hits the same problem as your code for the same reason:
fn f<T>(_t: T) {}
fn g<T: FnOnce(&u32)>(_t: T) {}
fn main() {
g(f);
}
This gives the same error that you're seeing, "error: implementation of FnOnce is not general enough", and complains that f implements FnOnce only for one lifetime whereas g requires it to implement it for all possible lifetimes.
It's easier to see what's going on by writing out some of the generics more explicitly:
fn f<T>(_t: T) {}
fn g<T: for<'b> FnOnce(&'b u32)>(_t: T) {}
fn main() {
g(f::<&u32>);
}
g's signature implies that it needs to be able to call a T using any lifetime of &u32 (that's what FnOnce(&u32) means – it's short for for<'b> FnOnce(&'b u32), i.e. "something that works with any reference to a u32, with any lifetime). But, f is a generic function, and in order to convert f to a function pointer, Rust needs to pick some specific value for its generics. That explains what the problem is, but it's interesting to look at why.
It's obvious that Rust would need to pick a specific value for a function's type generics in order to convert it to a function pointer – the compiler would have to generate different code for each possible type, so the function would have to point to a different block of code in memory and thus the pointer would need to be different. For lifetime generics, the issue is less obvious (because Rust implements lifetime generics using erasure: code that's identical apart from the lifetimes compiles to the same sequence of machine code, so only one implementation of the function body is used even if it's instantiated multiple times with different lifetime generics). One step towards undertanding the cause is to notice that the function pointer type would itself need to be generic for the code to work without picking a specific value for the lifetime, so the code would essentially end up equivalent to this:
fn f<T>(_t: T) {}
fn g(_t: for<'b> fn(&'b u32)) {}
fn main() {
g(f);
}
Running this produces the following error:
error[E0308]: mismatched types
--> src/main.rs:5:7
|
5 | g(f);
| - ^ one type is more general than the other
| |
| arguments to this function are incorrect
|
= note: expected fn pointer `for<'b> fn(&'b u32)`
found fn item `fn(_) {f::<_>}`
The relevant part of the Rust Reference specifies that a generic function item can't be coerced to a function pointer without specifying the value of its type generics and "early-bound" lifetime generics – and the error message is effectively saying that the coercion doesn't work because the generic isn't being specified (it even writes out f::<_> in the error message, demonstrating that it was looking for a value for the generic).
So the question boils down to "why is this particular lifetime early-bound", which raises the question of what the difference between an early- and late-bound lifetimes is. The distinction is hardly documented in most sources on Rust – the best official source I know of is this page in the Rust compiler internals documentation. A basic summary is that for soundness reasons, a lifetime has to be early-bound (i.e. specified when coercing the function item to a function pointer) unless it's constrained by the type of the function's arguments: otherwise, the function pointer type would be 'static (because it's a function pointer), but its output (which is an associated type of the function) would be a non-'static type, and implementing a non-'static associated type on a 'static type is unsound. (I'm not necessarily sure that it theoretically has to be unsound to do that – but the Rust type checker assumes that it will never happen, and starts inferring things incorrectly if it ever does happen, leading to soundness holes and segfaults.)
In this situation, the lifetime part of the generic does actually happen to be constrained by the argument type – but the Rust type checker is unable to make use of that fact, because the function doesn't actually have a lifetime generic (it's a type generic), and the Rust compiler is unable to "refine" the (always early-bound) type generic into an early-bound type generic portion and late-bound lifetime generic portion. If you constrain the function to mention the lifetime explicitly, everything works (here, I changed the type of f to work only on shared references, not on all T, so that the two generics could be bound separately):
fn f<'a, T>(_t: &'a T) {}
fn g<T: FnOnce(&u32)>(_t: T) {}
fn main() {
g(f);
}
In any case, the problem is easy to work around by converting the function item to a closure that captures nothing (writing |x| f(x)), rather than directly a function pointer (which is what happens if you write just f):
fn f<T>(_t: T) {}
fn g<T: FnOnce(&u32)>(_t: T) {}
// or fn g(_t: for<'b> fn(&'b u32)) {}
fn main() {
g(|x| f(x));
}
Adding the closure gets around tbe problem because although the generic argument on the function is a type argument T, Rust knows that the closure operates only on &u32, so the closure ends up having a non-generic type that has a generic implementation of Fn and FnOnce, and thus there are no generics that need to be bound in order to use it.