How to implement IntoIterator from nested map calls in Rust?

I am having trouble specifying the IntoIterator's IntoIter associated type's type when implementing IntoIterator for a custom struct. Because the into_iter function calls a map that itself returns a map, and because if I remember correctly closures infer a new lifetime by default (or something like that) I am drowning in a generic soup that I just can't seem to figure out. This sounds contraptious already so I am gonna post the code snippet instead, and try to explain the expected behavior.

Note that I am quite confused on what's happening, so the question I asked might not be appropriate or could be better formulated, feel free to suggest a better one so I can update it.

In this code, we have a struct (SubstitutionBlock) that represents many substitutions (many SubstitutionEntry) in a concise manner. The need here is to "split" that concise representation (SubstitutionBlock) into an iteration of individual entries (multiple SubstitutionEntry). I am trying to implement IntoIterator for SubstitutionBlock, to yield SubstitutionEntry objects, but like I said, I just cannot figure out how.

After spending a whole afternoon on that, I am more interested in the solution to that code than in a workaround/alternative logic, but by all means, if you do think there is a better way to achieve that, feel free to post it.

I am posting a snippet for completness' sake but I believe a playground link is more useful :

Playground Link

use std::{collections::HashMap, iter::Map};

#[derive(Debug)]
pub struct SubstitutionBlock {
    pub id: String,
    pub aliases: HashMap<String, Vec<String>>,
    pub format: Option<String>,
    pub parents: Option<Vec<String>>,
}


#[derive(Debug)]
struct SubstitutionEntry {
    id: String,
    alias: String,
    value: String,
    format: Option<String>,
}

impl IntoIterator for SubstitutionBlock {
    type Item = SubstitutionEntry;
    
    /// HERE IS WHERE I STRUGGLE
    // type IntoIter<'a> = Map<HashMap<String, Vec<String>>, fn((&'a String, &'a Vec<String>)) -> Map<&'a Vec<String>, fn(&String) -> SubstitutionEntry>>;
    type IntoIter = Map<HashMap<String, Vec<String>>, fn((&String, &Vec<String>)) -> Map<&Vec<String>, fn(&String) -> SubstitutionEntry>>;

    fn into_iter(self) -> Self::IntoIter {

        self.aliases
        .into_iter()
        .map(
            |(value, aliases)| aliases.into_iter().map(
                |alias| SubstitutionEntry{
                    id: self.id.to_owned(),
                    alias: alias.to_owned(),
                    value: value.to_owned(),
                    format: self.format.to_owned(),
                }
            )
        )

    }

}


fn main() {
    
    let sb = SubstitutionBlock{
        id: String::from("id0"),
        aliases: HashMap::from([
            ("value0", vec!["alias0, alias1, alias2"]),
        ]),
        format: None,
        parents: None,
    };
    
    for entry in sb.into_iter() {
        println!("{:?}", entry);
    }
    
}

Solution

What you are trying to do is slightly impossible.

First, here is the body of the function fixed so that it compiles as a free-standing function. None of your closures need lifetimes since they all take owned values.

fn into_iter(block: SubstitutionBlock) -> impl Iterator<Item = SubstitutionEntry> {
    block.aliases.into_iter().flat_map(move |(value, aliases)| {
        let id = block.id.clone();
        let format = block.format.clone();

        aliases.into_iter().map(move |alias| SubstitutionEntry {
            id: id.clone(),
            alias,
            value: value.clone(),
            format: format.clone(),
        })
    })
}

The impossible part is that you can't return an opaque type from a trait method. You can replace impl Iterator<Item = SubstitutionEntry> with nearly the full type, but when you get to the closure type on Map, you will be stuck using impl FnMut, an opaque type. The best solution right now is to box them. You can box the closures, but I've boxed the entire thing since it's simpler.

type IntoIter = Box<dyn Iterator<Item = SubstitutionEntry>>;

fn into_iter(self) -> Self::IntoIter {
    let iter = into_iter(self);
    Box::new(iter)
}

This is what async-trait does.

Another way to get around this on a case-by-case basis is to create a struct that implements Iterator and have your logic inside of its next method instead of using map. It's a bit tedious to recreate the logic of flat_map, but this method of replacing a series of iterator adapters with a custom struct is always possible.

use std::collections::hash_map::IntoIter as HashIter;
use std::vec::IntoIter as VecIter;

pub struct SubstitutionIter {
    id: String,
    aliases: HashIter<String, Vec<String>>,
    format: Option<String>,
    current: Option<(String, VecIter<String>)>,
}

impl SubstitutionIter {
    fn new(sub: SubstitutionBlock) -> Self {
        let mut aliases = sub.aliases.into_iter();
        let current = aliases.next().map(|(k, v)| (k, v.into_iter()));

        Self {
            id: sub.id,
            aliases,
            format: sub.format,
            current,
        }
    }
}

impl Iterator for SubstitutionIter {
    type Item = SubstitutionEntry;

    fn next(&mut self) -> Option<Self::Item> {
        let Some((alias, values)) = &mut self.current else {
            return None;
        };

        let next = Some(SubstitutionEntry {
            id: self.id.clone(),
            alias: alias.clone(),
            value: values.next().unwrap(),
            format: self.format.clone(),
        });

        if values.len() == 0 {
            self.current = self.aliases.next().map(|(k, v)| (k, v.into_iter()));
        }

        next
    }
}

impl IntoIterator for SubstitutionBlock {
    type Item = SubstitutionEntry;
    type IntoIter = SubstitutionIter;

    fn into_iter(self) -> Self::IntoIter {
        SubstitutionIter::new(self)
    }
}

All of this in playground