Generic io::Write in loop ends in recursion overflow

The following code is a simplified version of my use case. What I'm trying to do is to use a bunch of configurable encoders to serialize a set of values.

use std::io::Write;
use anyhow::Result;

pub enum Value {
    Int(u8),
    Array(Vec<Value>),
}

pub trait Encoder {
    fn encode<W>(&self, target: W, value: &Value) -> Result<usize>
    where
        W: Write;
}

pub struct ArrayEncoder {
    // Actually contains additional information how to encode an array.
    element_encoder: DataEncoder,
}

impl Encoder for ArrayEncoder {
    fn encode<W>(&self, target: W, value: &Value) -> Result<usize> 
    where
        W: Write,
    {
        let mut target = target;
        let value = if let Value::Array(vec) = value {
            vec
        } else {
            unimplemented!("Proper error handling")
        };
        
        let mut written = 0;
        for v in value.iter() {
            written += self.element_encoder.encode(&mut target, v)?;
        }
        Ok(written)
    }
}

// Actually contains additional information how to encode an integer.
pub struct IntEncoder;

impl Encoder for IntEncoder {
    fn encode<W>(&self, target: W, value: &Value) -> Result<usize>
    where
        W: Write,
    {
        let mut target = target;
        let value = if let Value::Int(i) = value {
            i
        } else {
            unimplemented!("Proper error handling")
        };
        
        target.write(&[*value]).map_err(Into::into)
    }
}

pub enum DataEncoder {
    Array(Box<ArrayEncoder>),
    Int(IntEncoder),
}

impl Encoder for DataEncoder {
    fn encode<W>(&self, target: W, value: &Value) -> Result<usize>
    where
        W: Write
    {
        match self {
            DataEncoder::Array(enc) => enc.encode(target, value),
            DataEncoder::Int(enc) => enc.encode(target, value),
        }
    }
}

fn main() -> Result<()> {
    let value = Value::Array(vec![Value::Int(1), Value::Int(2), Value::Int(3)]);
    let encoder = ArrayEncoder { element_encoder: DataEncoder::Int(IntEncoder), };
    let mut target = vec![];
    
    encoder.encode(&mut target, &value)?;
    
    Ok(())
}

Playground

As you can see the values and encoders might be nested arrays. This means that both values and encoders are potentially infinitely nested which leads to the above code failing to compile. On the type level this is not problem as Vec and Box introduce the necessary indirection (when main() is removed the code compiles fine).

However, in the ArrayEncoder's encode() method I'm required to re-borrow the target writer for each item/loop iteration. If the element encoder is again an ArrayEncoder it adds another mutable borrow and so on which leads to the recursion overflow of rustc when evaluating the code.

So I understand my problem but I don't know how to solve it. Has anyone an idea?

You could borrow the target in encode signature, like so:

use anyhow::Result;
use std::io::Write;

pub enum Value {
    Int(u8),
    Array(Vec<Value>),
}

pub trait Encoder {
    fn encode<W>(&self, target: &mut W, value: &Value) -> Result<usize>
    where
        W: Write;
}

pub struct ArrayEncoder {
    // Actually contains additional information how to encode an array.
    element_encoder: DataEncoder,
}

impl Encoder for ArrayEncoder {
    fn encode<W>(&self, target: &mut W, value: &Value) -> Result<usize>
    where
        W: Write,
    {
        let value = if let Value::Array(vec) = value {
            vec
        } else {
            unimplemented!("Proper error handling")
        };

        let mut written = 0;
        for v in value.iter() {
            written += self.element_encoder.encode(target, v)?;
        }
        Ok(written)
    }
}

// Actually contains additional information how to encode an integer.
pub struct IntEncoder;

impl Encoder for IntEncoder {
    fn encode<W>(&self, target: &mut W, value: &Value) -> Result<usize>
    where
        W: Write,
    {
        let value = if let Value::Int(i) = value {
            i
        } else {
            unimplemented!("Proper error handling")
        };

        target.write(&[*value]).map_err(Into::into)
    }
}

pub enum DataEncoder {
    Array(Box<ArrayEncoder>),
    Int(IntEncoder),
}

impl Encoder for DataEncoder {
    fn encode<W>(&self, target: &mut W, value: &Value) -> Result<usize>
    where
        W: Write,
    {
        match self {
            DataEncoder::Array(enc) => enc.encode(target, value),
            DataEncoder::Int(enc) => enc.encode(target, value),
        }
    }
}

fn main() -> Result<()> {
    let value = Value::Array(vec![Value::Int(1), Value::Int(2), Value::Int(3)]);
    let encoder = ArrayEncoder {
        element_encoder: DataEncoder::Int(IntEncoder),
    };
    let mut target = vec![];

    encoder.encode(&mut target, &value)?;

    Ok(())
}

Note how now encode takes a &mut W rather than W, avoiding the need for reborrow.

1 Like

Thank you for your response. I already thought about this solution. It works but there is a case where it is unpleasant to look at.

io::Write is only implemented for &mut [u8]. So if I pass an array like [u8; 3] as target I first need to borrow it as mutable slice to have an io::Write and then re-borrow it mutably to match the signature of encode(), i.e. main looks as follows:

fn main() -> Result<()> {
    let value = Value::Array(vec![Value::Int(1), Value::Int(2), Value::Int(3)]);
    let encoder = ArrayEncoder {
        element_encoder: DataEncoder::Int(IntEncoder),
    };
    let mut target = [0, 0, 0];

    encoder.encode(&mut target.as_mut(), &value)?;

    Ok(())
}

Even with const generics this would only simplify to &mut &mut target...

However, I guess this is the way to go. I mark your suggestion as answer as long as no one comes up with another version.