Specifying type of recursive FlatMap

help
1

I am trying to create an enum to return from a function.
My input is a wrapped Vec (there are other properties, but they are irrelevant).
Types are as follows (simplified, I am actually using ecow::EcoStrings instead of Strings):

enum Part {
    Static(String),
    Field(FieldDefinition),
    OptionalGroup(String, Vec<Part>)
}
struct FieldDefinition {
    name: String,
    pattern: String,
    // ...other irrelevant fields
}

I am trying to create an implementation to convert my Vec<Part> into an Iterator<Item = String> with the following logic:

impl Part {
    fn pattern_segments(&self) -> PatternSegmentIterator<'_> {
        match self {
            Part::Static(s) => PatternSegmentIter::Single(regex::escape(s).to_owned()),
            Part::Field(def) => {
                PatternSegmentIter::Single(format!("(?P<{}>{})", def.name, def.pattern))
            }
            Part::OptionalGroup(key, subparts) => PatternSegmentIter::Prefixed {
                prefix: match key {
                    Some(k) => format!("(?P<{k}>").into(),
                    None => "(?:".into(),
                },
                subparts,
                suffix: ")?".into(),
            },
        }
    }
}

My issue is with the type of PatternSegmentIter:

enum PatternSegmentIter<'a> {
    Empty,
    Single(String),
    Prefixed {
        prefix: String,
        subparts: &'a Vec<Part>,
        suffix: String,
    },
    Subparts {
        iter: std::iter::FlatMap<
            std::slice::Iter<'a, Part>,
            PatternSegmentIter<'a>,
            fn(&'a Part) -> Self,
        >,
        suffix: String,
    },
}
impl<'a> Iterator for PatternSegmentIter<'a> {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        match core::mem::replace(self, Self::Empty) {
            PatternSegmentIter::Empty => None,
            PatternSegmentIter::Single(s) => Some(s),
            PatternSegmentIter::Prefixed {
                prefix,
                subparts,
                suffix,
            } => {
                *self = Self::Subparts {
                    iter: subparts.iter().flat_map(Part::pattern_segments),
                    suffix,
                };
                Some(prefix)
            }
            PatternSegmentIter::Subparts { mut iter, suffix } => match iter.next() {
                Some(item) => {
                    *self = Self::Subparts { iter, suffix };
                    Some(item)
                }
                None => Some(suffix),
            },
        }
    }
}

My issue is that the PatternSegmentIter Subparts iterator type is cyclical.
I tried to add the iterator type as a type parameter (I: Iterator<Item = String>) my build hung when attempting to specify the return type of pattern_segments as impl Iterator<Item = String>, and requiring the Iterator type to be specified is impossible (PatternSegmentIterator<'_, PatternSegmentIterator<'_, ...>>).

Is there any solution to this or do I need to switch to dynamic dispatch (return Box<dyn Iterator<Item = String> and get rid of PatternSegmentIterator)? I assumed (perhaps naiively) that creating an iterator enum would be better than just returning a boxed iterator, but maybe I'm wrong about that?

2

You don't need dynamic dispatch. You do need Box, because every recursive data structure must have a heap allocation so it isn't of infinite static size.

        iter: std::iter::FlatMap<
            std::slice::Iter<'a, Part>,
            Box<PatternSegmentIter<'a>>,
            fn(&'a Part) -> Self,
        >,
2 Likes
3

That isn't quite correct. The fn(&'a Part) -> Self needs to now return Box<Self> which causes errors due to the box lifetime, and the fact it isn't a boxed trait means I can't just make it Box<Self + 'a>.

4

Thanks for the pointer, I solved the issue by Boxing the whole FlatMap object.

5

If you don't mind, please mark their reply as the solution by checking the box at the bottom of their reply. That way, others can easily find the solution and will see that your question has been answered. I see you're new to the forum so I thought you'd want to know.

1 Like
6

Sorry for the mistake. I'm not sure what you mean about a lifetime error, though; this compiles (when I also fix an unrelated type error inside pattern_segments()):

...
    Subparts {
        iter: std::iter::FlatMap<
            std::slice::Iter<'a, Part>,
            Box<Self>,
            fn(&'a Part) -> Box<Self>,
        >,
        suffix: String,
    },
...
                *self = Self::Subparts {
                    iter: subparts.iter().flat_map(|p| Box::new(p.pattern_segments())),
                    suffix,
                };
...
2 Likes
7

Yes, I'm not actually able to reproduce my earlier issue, and cannot remember the exact issue.
Thank you for your assistance.