Overflow evaluating the requirement in a Iterator

help
1

I have a Block that parses Elements from chars: impl LikeIter:

pub trait LikeIter: Iterator<Item = (usize, char)> + Clone + Debug {}
impl<T: Iterator<Item<Item = (usize, char)> + Clone + Debug> LikeIter for T {}

that is, from any iterator that has Item = (usize, char)

Elements contains a Vec<Element> within it
Element has different variant constructions, including Block:

#[derive(Debug, PartialEq)]
pub enum Element {
    Block(Block),
    AssignExpr(AssignExpr),
    Ident(Ident),
}

When Elements is parsed, a Block is also parsed inside it, where its inner Elements is parsed.
Recursion occurs and since the LikeIter type may contain a type with lifetime, an error occurs:


error[E0275]: overflow evaluating the requirement Enumerate<Chars<'_>>: Iterator
  |
  = help: consider increasing the recursion limit by adding a #![recursion_limit = "20"] attribute to your crate (abstract_)
  = note: required for TakeWhile<Enumerate<Chars<'_>>, ...> to implement Iterator
  = note: 9 redundant requirements hidden
  = note: required for TakeWhile<TakeWhile<..., ...>, ...> to implement Iterator
  = note: required for TakeWhile<TakeWhile<..., ...>, ...> to implement IntoIterator
  = note: the full name for the type has been written to 'C:\Users\letif\VS Code Projects\rust\abstract\target\debug\deps\abstract_-c86ab7040e388b79.long-type-13391386737842869171.txt'
  = note: consider using --verbose to print the full type name to the console
  = note: the full name for the type has been written to 'C:\Users\letif\VS Code Projects\rust\abstract\target\debug\deps\abstract_-c86ab7040e388b79.long-type-5479745382517321328.txt'
  = note: consider using --verbose to print the full type name to the console

error[E0275]: overflow evaluating the requirement Chars<'_>: Sized      
  |
  = help: consider increasing the recursion limit by adding a #![recursion_limit = "20"] attribute to your crate (abstract_)
  = note: required for Enumerate<Chars<'_>> to implement Iterator      
  = note: 9 redundant requirements hidden
  = note: required for TakeWhile<TakeWhile<..., ...>, ...> to implement Iterator
  = note: required for TakeWhile<TakeWhile<..., ...>, ...> to implement IntoIterator
  = note: the full name for the type has been written to 'C:\Users\letif\VS Code Projects\rust\abstract\target\debug\deps\abstract_-c86ab7040e388b79.long-type-15616929496332024509.txt'
  = note: consider using --verbose to print the full type name to the console
  = note: the full name for the type has been written to 'C:\Users\letif\VS Code Projects\rust\abstract\target\debug\deps\abstract_-c86ab7040e388b79.long-type-15616929496332024509.txt'
  = note: consider using --verbose to print the full type name to the console

For more information about this error, try rustc --explain E0275.       
warning: abstract_ (lib test) generated 11 warnings (5 duplicates)      
error: could not compile abstract_ (lib test) due to 2 previous errors; 11 warnings emitted

How to solve it? How to get around it if it can't be solved? What I know for sure: the recursion_limit attribute will not solve the problem.

Full code:

#[derive(PartialEq, Debug)]
pub struct Block(Elements);

impl Parse for Block {
    fn parse(chars: impl LikeIter) -> Option<Self> {
        let [mut start, mut end] = [{ None }; 2];

        for (i, char) in chars.clone() {
            if char == ' ' {
                continue;
            }
            if char == '{' {
                start = Some(i);
                break;
            }
            return None;
        }
        let start = start?;

        let chars = chars.clone().take_while(|&(i, _)| i < start);
        let el = Elements::parse(chars.clone()).unwrap();
        if !el.is_empty() {
            end = Some(el.get_end());
        }

        for (i, char) in chars.take_while(|&(i, _)| i <= end.unwrap_or_default()) {
            if char == ' ' {
                continue;
            }
            if char == '}' {
                end = Some(i);
                break;
            }
            return None;
        }

        Some(Self(el))
    }
}

#[derive(PartialEq, Debug, Deref)]
pub struct Elements(Vec<Element>);

impl Parse for Elements {
    fn parse(chars: impl LikeIter) -> Option<Self> {
        let mut elements = Vec::new();
        let mut skip_index = 0;

        while let Some(el) = Element::parse(chars.clone().skip_while(|&(i, _)| i <= skip_index)) {
            skip_index = el.get_end();
            elements.push(el);
        }

        Some(Self(elements))
    }
}


#[derive(Debug, PartialEq)]
pub enum Element {
    Block(Block),
    AssignExpr(AssignExpr),
    Ident(Ident),
}

impl Parse for Element {
    fn parse(chars: impl LikeIter) -> Option<Self> {
        [
            Block::parse(chars.clone()).map(|v| Element::Block(v)),
            AssignExpr::parse(chars.clone()).map(|v| Self::AssignExpr(v)),
            Ident::parse(chars.clone()).map(|v| Self::Ident(v)),
        ]
        .into_iter()
        .flat_map(|v| v)
        .nth(0)
    }
}
2

A few comments:

It looks like you are writing your own parser combinator by doing lots of cloning. Have you considered using an existing crate like winnow or nom?

The "full code" is missing a lot of type definitions and even a derive macro. The errors displayed are unrelated to your question. After messing around with it for a few minutes, it compiles without error: Rust Playground. Please provide a minimal reproducible code sample.

The #![recursion_limit] attribute defaults to 128. Why would the error message suggest increasing it to 20? Have you set it to 10 for that specific error message? As far as I know, the suggestion just doubles the value at the time of error: When I set it to 2, the suggestion is increasing it to 4.

3

I apologise, I didn't think there wasn't enough information. I added a test to your Playground at the end and an error occurred

4

Thank you, that's what was missing. According to the "long-type" txt file mentioned in the error message, it points at the closure in:

impl Parse for Elements {
    fn parse(chars: impl LikeIter) -> Option<Self> {
        let mut elements = Vec::new();
        let mut skip_index = 0;

        while let Some(el) = Element::parse(chars.clone().skip_while(|&(i, _)| i <= skip_index)) {
            skip_index = el.get_end();
            elements.push(el);
        }

        Some(Self(elements))
    }
}

Which is creating an infinitely long type.

Don't start from the beginning of the iterator on every loop. Parse::parse() as defined takes ownership of the iterator, which is why you end up with so much cloning and skip/take. This is very reminiscent of Shlemiel the painter’s algorithm.

There are two ways I know of to fix this: First is by operating over &mut I where I: Iterator. That will allow Parse::parse() to advance the referenced iterator as it consumes items. It requires quite some refactoring, but here's what it looks like: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=da7ec886d0e54a84f3ae6672f91858e6. The second way is by doing stateless parsing like a parser combinator library, threading the parser position through the combinators.

There's a logic bug in Element::parse() where it doesn't consume from the original iterator. Instead, it creates a clone for each branch that it tests. It needs to advance the underlying iterator after matching. Also, it could benefit from short-circuiting to stop trying other branches when a match was found. The stateless parsing method doesn't have this problem, since it returns the first match it finds along with the position for the next combinator to continue from.

1 Like
5

What you're talking about concerns performance, but how does adding a reference affect the compiler's behavior when previously it tried to recursively compute the lifetime, which led to an error?

6

I explained that as the loop creating an infinitely long type. Switching to a reference fixes that indirectly by not cloning the iterator in the Block -> Elements -> Element -> Block cycle. That clone causes it to restart from the beginning without end.

7

And in case it wasn't clear, when you need to do lookahead you can clone the iterator. Something like this:

// let iter: &mut impl Iterator<Item = char> + Clone
let mut peek = iter.clone();
if peek.next() == Some('a') {
  *iter = peek;
  // Continue using `iter` after successful peek.
} else {
  // Continue using `iter` after failed peek.
}
8

There's Iterator::peekable for when you want to lookahead just one item. But cloning is a good tool when you need to lookahead more than one. Good suggestion!