Infinite recursion while resolving traits

[stepchowfun]

Hi all! I'm running into an issue that is difficult for me to describe other than by giving a simple example. I believe the following code should compile, but instead it seems like the compiler gets stuck in a loop:

use std::{
    fs::File,
    io::{Result, Write},
};

pub trait Serialize {
    fn serialize<T: Write>(&self, writer: T) -> Result<()>;
}

pub enum Tree {
    Leaf(bool),
    Parent(Vec<Tree>),
}

impl Serialize for Tree {
    fn serialize<T: Write>(&self, mut writer: T) -> Result<()> {
        match self {
            Tree::Leaf(_) => Ok(()),
            Tree::Parent(children) => {
                // let mut writer: Box<dyn Write> = Box::new(writer);

                for child in children {
                    child.serialize(writer.by_ref())?;
                }

                Ok(())
            }
        }
    }
}

fn main() -> Result<()> {
    let mut buffer = File::create("tree.txt")?;
    Tree::Parent(vec![Tree::Leaf(true)]).serialize(&mut buffer)
}

As is, the compiler gives this error when running cargo build:

$ cargo build
   Compiling example v0.1.0 (/Users/stephanboyer/Desktop/personal/projects/typical/integration-tests/rust)
error: reached the recursion limit while instantiating `<Tree as Serialize>::serialize::...t &mut &mut &mut &mut &mut File>`
  --> src/main.rs:24:21
   |
24 |                     child.serialize(writer.by_ref())?;
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: `<Tree as Serialize>::serialize` defined here
  --> src/main.rs:16:5
   |
16 |     fn serialize<T: Write>(&self, mut writer: T) -> Result<()> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: the full type name has been written to '/Users/stephanboyer/Desktop/personal/projects/typical/integration-tests/rust/target/debug/deps/example.long-type.txt'

error: could not compile `example` due to previous error

Since writer: T implements Write (as T has the trait bound), I would expect writer.by_ref() to also implement Write, per the documentation of by_ref(). But the compiler does not seem satisfied by that, and instead seems to get stuck in some kind of loop (until the recursion limit is reached).

The build succeeds if the commented line is uncommented. It seems boxing the writer into a trait object terminates the recursion. But that requires an extra allocation, so it's not a satisfying workaround.

(Strangely, cargo check succeeds on both versions and doesn't seem to run into this issue.)

Thanks for looking into this, and I apologize if this is a duplicate of another issue. I tried searching and found a few possible instances of people running into the compiler's recursion limit, but it was hard for me to tell if it was the same issue as this one.

Meta

rustc --version --verbose:

rustc 1.55.0 (c8dfcfe04 2021-09-06)
binary: rustc
commit-hash: c8dfcfe046a7680554bf4eb612bad840e7631c4b
commit-date: 2021-09-06
host: x86_64-apple-darwin
release: 1.55.0
LLVM version: 12.0.1

Backtrace

$ RUST_BACKTRACE=1 cargo build

   Compiling example v0.1.0 (/Users/stephanboyer/Desktop/personal/projects/typical/integration-tests/rust)
error: reached the recursion limit while instantiating `<Tree as Serialize>::serialize::...t &mut &mut &mut &mut &mut File>`
  --> src/main.rs:24:21
   |
24 |                     child.serialize(writer.by_ref())?;
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: `<Tree as Serialize>::serialize` defined here
  --> src/main.rs:16:5
   |
16 |     fn serialize<T: Write>(&self, mut writer: T) -> Result<()> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: the full type name has been written to '/Users/stephanboyer/Desktop/personal/projects/typical/integration-tests/rust/target/debug/deps/example.long-type.txt'

error: could not compile `example` due to previous error

[Aaron1011]

Inside your implementation of serialize, you recursively call serialize instantiated with a new type - &mut T, where T is the type you started out with. This occurs because each level of recursion is adding a new &mut reference - you initially have a &mut File, and obtain a &mut &mut File by calling by_ref on the &mut T via its Write impl.

You could either introduce a trait object (a &mut dyn Write should work as well), or change your Serialize trait to take in a &mut T, which can be directly passed to the recursive serialize call.

[stepchowfun]

I understand that my example features polymorphic recursion. But why is that forbidden? Perhaps this limitation is a consequence of monomorphization?

or change your Serialize trait to take in a &mut T, which can be directly passed to the recursive serialize call.

After a bit of exploration, I discovered that taking the writer by reference (writer: &mut T, as you suggested), I can reborrow it for the recursive calls (&mut *writer). (I originally avoided doing this because it seems to be unidiomatic to take writers by reference.) Strictly speaking, I cannot logically pass the mutable reference directly to the recursive calls in a loop, since mutable references are not Copy. But apparently the Rust compiler will implicitly do the reborrowing in some cases (including in this simple situation), giving the illusion that I can simply reuse the reference (writer). Convenient, if a little too magical for my taste.

So I can do that to work around this issue (thanks for suggesting it!), but I still find it counterintuitive that the code cannot be completely type checked before instantiating generics (which seems like a codegen concern, i.e., part of the compiler "back end").

[tavianator]

Indeed, Rust doesn't support polymorphic recursion: #4287, exactly because of monomorphization.

[fmease]

Closing as wontfix then.