Multiline unquoted indented strings and "Collect combinator making no progress" woes

[airstrike]

Hey all,

I'd love to figure this out on my own but it's been days and my head is sore from banging it against the monitor... I'm trying to write a parser for a "simple" markup language which describes nested containers in a layout, such as the following (abbreviated) example:

# Any container can be one of vsplit, hsplit or block, identified `likeso::`.
vsplit::
    # Containers have optional titles, subtitles and footers.
    title:: This vsplit has a title.
    subtitle:: It also has a subtitle, but no footer.

    # Other than those three optional fields, everything that
    # follows in a vsplit or hsplit are children containers.
    # The simplest container is a block, which has no children other than a single String.
    block:: This is the first child of the vsplit. It is just one string of text.

    # But blocks themselves can also have titles, subtitles and footers.
    block::
        title:: This block has a title.
        # The only thing that can follow the three optionals (title, subtitle, footer)
        # is a single string, which may extend over multiple lines.
        This string extends over multiple lines. We can keep track of it
        by making sure its indentation is consistent.
        
        It can even have empty lines, although I was forced to make these
        empty lines also have the same amount of indentation, otherwise they break :(

    hsplit::
        block:: The third element in this vsplit is an hsplit with two blocks.
        block:: Inline strings like this one are syntactic sugar for very simple blocks.

I'll probably rename vsplit and hsplit into column and row, but for now that's what they're called.

I can speak to the motivation behind the markup if anyone's curious, but onto the actual issue: I can't seem to find a way to consistently parse multiline strings, inline strings, and indents without them getting in the way of each other or running into Collect combinator making no progress... I've gone through the tutorial and examples and don't know what else to try.

MRE: Given the following input:

    let input = r#"
vsplit::
    title:: This is a vsplit title
    block::
        Some multiline block here.
        Continues on the second line.
    hsplit::
        block:: A single line block.
        block:: 
            A multiline block
            Has more than one line.
"#;

I'm lexing/parsing in a way similar to the nano_rust example:

    let (tokens, errs) = parser::lexer().parse(input).into_output_errors();

    let parse_errs = if let Some(tokens) = &tokens {
        let (output, errors) = parser::parser()
            // .map_with(|ast, e| (ast, e.span()))
            .parse(tokens.as_slice().spanned((input.len()..input.len()).into()))
            .into_output_errors();
            // ...

But I get stuck on the collect combinator, with the output below after littering my lexer with print statements. I would immensely appreciate any help figuring out this lexer.

(I realize this current iteration isn't even parsing Text as a multiline string joined by \n. Earlier attempts were successful in managing that, but broke other issues and I feel like this is closer to the answer than what I had before.)

>> lexer: VSplit 1..9
>> lexer: Title 14..22
>> lexer: Text("This is a vsplit title") 22..44
>> lexer: Block 49..56
>> lexer: Text("Some multiline block here.") 65..91
>> lexer: Text("Continues on the second line.") 100..129
>> lexer: HSplit 134..142
>> lexer: Block 151..159
>> lexer: Text("A single line block.") 159..179
>> lexer: Block 188..196
>> lexer: Text("A multiline block") 209..226
>> lexer: Text("Has more than one line.") 239..262
>> lexer: Text("") 263..263
thread 'main' panicked at /Users/andy/.cargo/git/checkouts/chumsky-651fb76526ac39e3/9031baf/src/combinator.rs:1942:21:
found Collect combinator making no progress at src/parser.rs:85:18

where line 85 is at the end of

// parser.rs
use crate::ast::*;
use chumsky::prelude::*;
pub type Span = SimpleSpan<usize>;
pub type Spanned<T> = (T, Span);

#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    Block,
    VSplit,
    HSplit,
    Title,
    Subtitle,
    Footer,
    Ident(String),
    Text(String),
}

pub fn lexer<'src>() -> impl Parser<
    'src,
    &'src str,
    Vec<(Token, Span)>,
    extra::Err<Rich<'src, char, Span>>,
> {
    let line = any()
        .and_is(just('\n').not())
        .repeated()
        .collect::<String>()
        .labelled("Line");

    let multi_line = {
        let indent = just('\n')
            .ignore_then(just(' ').repeated().configure(
                |cfg, parent_indent| {
                    eprintln!(">> multi  parent: {:?}", parent_indent);
                    cfg.exactly(*parent_indent)
                },
            ))
            .labelled("INDENT");

        text::whitespace()
            .count()
            .ignore_with_ctx(
                line.clone().separated_by(indent).collect::<Vec<String>>(),
            )
            .map(|lines| lines.join("\n"))
            .labelled("Multi line")
    };

    let text = line.or(multi_line).map(Token::Text);

    let comment = just("#")
        .then(any().and_is(just('\n').not()).repeated())
        .padded();

    let ident = text::ascii::ident()
        .then_ignore(just("::").ignore_then(just(' ').or_not()))
        .map(|ident: &str| match ident {
            "block" => Token::Block,
            "vsplit" => Token::VSplit,
            "hsplit" => Token::HSplit,
            "title" => Token::Title,
            "subtitle" => Token::Subtitle,
            "footer" => Token::Footer,
            _ => {
                eprintln!(">> Uncaught ident: {:?}", ident);
                Token::Ident(ident.to_string())
            }
        });

    let token = ident.or(text);

    text::whitespace()
        .ignore_then(
            token
                .map_with(|tok, e| {
                    eprintln!(">> lexer: {:?} {:?}", tok, e.span());
                    (tok, e.span())
                })
                .padded_by(comment.repeated())
                .padded()
                // If we encounter an error, skip and attempt to lex the next character as a token instead
                .recover_with(skip_then_retry_until(any().ignored(), end()))
                .repeated()
                .collect(), // <-- line 85
        )
        .with_ctx(0)
}

I also have defined a parser which compiles, but I have been unable to test it since I can't get the lexer to conclude... Below are the current AST and the remainder of parser.rs although they are not really relevant right now unless it's giving allergic reactions and you tell me I should also change it.

// ast.rs
#[derive(Debug, Clone, PartialEq)]
pub struct Container<T> {
    pub title: Option<Box<Expr>>,    // Optional title
    pub subtitle: Option<Box<Expr>>, // Optional subtitle
    pub footer: Option<Box<Expr>>,   // Optional footer
    pub body: T,                     // Some container content
}

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Value(Value),
    Block(Box<Container<Self>>),  // Single body of text
    VSplit(Container<Vec<Self>>), // Column
    HSplit(Container<Vec<Self>>), // Row
}

#[derive(Debug, Clone, PartialEq)]
pub enum Value {
    Text(String),
}

// rest of parser.rs
type ParserInput<'tokens, 'src> =
    chumsky::input::SpannedInput<Token, Span, &'tokens [(Token, Span)]>;

pub fn parser<'tokens, 'src: 'tokens>() -> impl Parser<
    'tokens,
    ParserInput<'tokens, 'src>,
    Spanned<Expr>,
    extra::Err<Rich<'tokens, Token, Span>>,
> + Clone {
    let val = select! {
        Token::Text(t) => Expr::Value(Value::Text(t)),
    }
    .labelled("value");

    let title = just(Token::Title).ignore_then(val).or_not();
    let subtitle = just(Token::Subtitle).ignore_then(val).or_not();
    let footer = just(Token::Footer).ignore_then(val).or_not();
    let optionals = title
        .clone()
        .then(subtitle.clone())
        .then(footer.clone())
        .boxed();

    let component = recursive(|expr| {
        let block = just(Token::Block)
            .ignore_then(optionals.clone())
            .then(val.clone())
            .map(|(((title, subtitle), footer), body)| Container {
                title: title.map_or(None, |v| Some(Box::new(v))),
                subtitle: subtitle.map_or(None, |v| Some(Box::new(v))),
                footer: footer.map_or(None, |v| Some(Box::new(v))),
                body: body,
            })
            .map(|expr| Expr::Block(Box::new(expr)));

        let vsplit = just(Token::VSplit)
            .ignore_then(optionals.clone())
            .then(expr.clone().repeated().collect::<Vec<Expr>>())
            .map(|(((title, subtitle), footer), items)| Container {
                title: title.map_or(None, |v| Some(Box::new(v))),
                subtitle: subtitle.map_or(None, |v| Some(Box::new(v))),
                footer: footer.map_or(None, |v| Some(Box::new(v))),
                body: items,
            })
            .map(Expr::VSplit);

        let hsplit = just(Token::HSplit)
            .ignore_then(optionals.clone())
            .then(expr.clone().repeated().collect::<Vec<Expr>>())
            .map(|(((title, subtitle), footer), items)| Container {
                title: title.map_or(None, |v| Some(Box::new(v))),
                subtitle: subtitle.map_or(None, |v| Some(Box::new(v))),
                footer: footer.map_or(None, |v| Some(Box::new(v))),
                body: items,
            })
            .map(Expr::HSplit);

        choice((block, vsplit, hsplit)).boxed()
    });

    component
        .clone()
        .map_with(|expr, e| (expr, e.span()))
        .recover_with(skip_then_retry_until(any().ignored(), end()))
}

impl std::fmt::Display for Token {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            Token::Block => write!(f, "block"),
            Token::VSplit => write!(f, "vsplit"),
            Token::HSplit => write!(f, "hsplit"),
            Token::Title => write!(f, "title"),
            Token::Subtitle => write!(f, "subtitle"),
            Token::Footer => write!(f, "footer"),
            Token::Text(t) => write!(f, "{}", t),
            Token::Ident(t) => write!(f, "{}", t),
        }
    }
}

Thank you once again in advance for any help

[zesterer]

I think the problem here is that line can accept zero characters (repeated is permitted to accept nothing), and then line is directly used in token, which is then fed into another repeated on line 84. What you're effectively telling the parser to accept is "an infinite number of zero-length elements" which of course means the parser just keeps spinning round and round doing nothing.

You probably want to add a .at_least(1) or something to the line parser's repeated, although I haven't looked closely enough at your syntax to tell if this is right.

As an aside: counting the indentation levels might not necessarily be what you want. Consider something like this instead, where the indentation string itself gets passed back as context:

let multi_line = {
        let indent = just('\n')
            .ignore_then(just("").configure(
                |cfg, parent_indent| {
                    eprintln!(">> multi  parent: {:?}", parent_indent);
                    cfg.seq(*parent_indent)
                },
            ))
            .labelled("INDENT");

        text::whitespace()
            .ignore_with_ctx(
                line.clone().separated_by(indent).collect::<Vec<String>>(),
            )
            .map(|lines| lines.join("\n"))
            .labelled("Multi line")
    };

That way, <tab><space> doesn't get confused with <space><tab>.

[airstrike]

Thanks, this is super helpful. Combined with other things I've learned since the original post, I'm making a few edits and will follow up with an update (or hopefully a final answer) once it's out of the oven. But I hadn't appreciated that repeated() could accept zero repetitions, which I guess was a massive oversight. Thanks a million

[airstrike]

First of all, thanks again for such a great library and for the help figuring this out.

I've fixed the issue and I can parse my little markup language with no (real) issues, woot! 🎉

Unfortunately my code is still very repetitive as every time I made it more generic I ran into issues that were hard to debug. I ended up having to create a helper second parser function block_parser() which includes the recursive block and I still had to duplicate a lot of extra code for mapping the parsed expressions into a Component type.

I wouldn't mind the helper function as much if it didn't force me to redefine parsers like lines, title, subtitle and footer. Those last 3 are themselves pretty duplicative since they behave identically but I've left them like that for now.

Maybe it's obvious to others why I need that Expr::List variant but it feels unnecessary as that kind of behavior should be handled by Expr::Row and Expr::Column directly... but because the recursive block was basically forcing me into collecting into a Vec I had no alternative but to create a wrapper around that, so to speak... which in turn forced me to create the Component struct twice: inside and outside the recursive block 😖😖😖 and it's done twice for Expr::Row and Expr::Column + the one time for Expr::Single so I have nearly identical code in 5 different places...

Finally, I ended up not using tokens at all for now because they were (a) getting in the way and (b) not really adding much clarity/conciseness. I will try to use the code now in the actual application for which I developed this and will work on optimizing the parser after that.

As promised, the code ended up looking like the below, with some helper functions and fn main() omitted for brevity. Apologies in advance as it is very rough...

I've placed the full code in a repo here for now but might take it offline in a few weeks.

fn block_parse<'src>(
) -> impl Parser<'src, &'src str, Spanned<Expr>, extra::Err<Rich<'src, char, Span>>>
{
    let ident = text::ascii::ident()
        .then_ignore(just("::").ignore_then(just(' ').repeated()))
        .map(|z: &str| z.to_string());

    let title_ = just("title::").ignore_then(just(' ').repeated());
    let subtitle_ = just("subtitle::").ignore_then(just(' ').repeated());
    let footer_ = just("footer::").ignore_then(just(' ').repeated());

    let single_ident = just("box::").then_ignore(text::inline_whitespace());

    let col_ = just("column::").then_ignore(text::inline_whitespace());
    let row_ = just("row::").then_ignore(text::inline_whitespace());
    let many_ident = choice((col_, row_)).boxed();

    let lines = any()
        .and_is(ident.not())
        .and_is(just('\n').not())
        .repeated()
        .at_least(1)
        .collect::<String>()
        .repeated()
        .collect::<Vec<String>>()
        .map(|lines| lines.join("\n"))
        .map(|s| Expr::Text(s.trim().to_string()))
        .labelled("Line")
        .then_ignore(text::newline())
        .map_with(|x, e| (x, e.span()));

    let raw_lines = any()
        .and_is(ident.not())
        .and_is(just('\n').not())
        .repeated()
        .at_least(1)
        .collect::<String>()
        .map(|s| match s.trim().to_string() {
            s if s.is_empty() => "\n".to_string(),
            s => s,
        })
        .separated_by(text::newline())
        .allow_trailing()
        .collect::<Vec<String>>()
        .map(|lines| lines.join(" "))
        .map(|s| s.trim().to_string())
        .labelled("Line")
        .map_with(|x, e| (Expr::Text(x), e.span()));

    let title = title_
        .ignore_then(text::newline().not())
        .ignore_then(lines.padded())
        .map(|content| Expr::Title(Box::new(content)))
        .map_with(|tok, e| (tok, e.span()));

    let subtitle = subtitle_
        .ignore_then(text::newline().not())
        .ignore_then(lines.padded())
        .map(|content| Expr::Subtitle(Box::new(content)))
        .map_with(|tok, e| (tok, e.span()));

    let footer = footer_
        .ignore_then(text::newline().not())
        .ignore_then(lines.padded())
        .map(|content| Expr::Footer(Box::new(content)))
        .map_with(|tok, e| (tok, e.span()));

    let single = single_ident
        .clone()
        .ignore_then(text::newline())
        .ignore_then(title.padded().or_not())
        .then(subtitle.padded().or_not())
        .then(footer.padded().or_not())
        .then(raw_lines.clone())
        .boxed()
        .map_with(|(((title, subtitle), footer), lines), e| {
            (
                Expr::Single(Box::new(Component {
                    title: match title {
                        Some(title) => Some(Box::new(title)),
                        None => None,
                    },
                    subtitle: match subtitle {
                        Some(subtitle) => Some(Box::new(subtitle)),
                        None => None,
                    },
                    footer: match footer {
                        Some(footer) => Some(Box::new(footer)),
                        None => None,
                    },
                    body: lines,
                })),
                e.span(),
            )
        });

    let block = recursive(|block| {
        let indent = just(' ')
            .repeated()
            .configure(|cfg, parent_indent| cfg.exactly(*parent_indent));

        let many = many_ident
            .clone()
            .then_ignore(text::newline())
            .then(title.padded().or_not())
            .then(subtitle.padded().or_not())
            .then(footer.padded().or_not())
            .then(block.clone())
            .boxed()
            .map(|((((id, title), subtitle), footer), body)| match id {
                "column::" => Expr::Column(Component {
                    title: match title {
                        Some(title) => Some(Box::new(title)),
                        None => None,
                    },
                    subtitle: match subtitle {
                        Some(subtitle) => Some(Box::new(subtitle)),
                        None => None,
                    },
                    footer: match footer {
                        Some(footer) => Some(Box::new(footer)),
                        None => None,
                    },
                    body,
                }),
                "row::" => Expr::Row(Component {
                    title: match title {
                        Some(title) => Some(Box::new(title)),
                        None => None,
                    },
                    subtitle: match subtitle {
                        Some(subtitle) => Some(Box::new(subtitle)),
                        None => None,
                    },
                    footer: match footer {
                        Some(footer) => Some(Box::new(footer)),
                        None => None,
                    },
                    body,
                }),
                _ => {
                    eprintln!("> Unreachable: {id:?}");
                    unreachable!()
                }
            })
            .map_with(|x, e| (x, e.span()));

        let stmt = single
            .clone()
            .or(many)
            .boxed()
            .repeated()
            .at_least(1)
            .collect::<Vec<_>>()
            .map_with(|body, e| (Expr::List(body), e.span()));

        text::whitespace()
            .count()
            .ignore_with_ctx(stmt.separated_by(indent).collect::<Vec<_>>())
    });

    let many = many_ident
        .then_ignore(text::newline())
        .then(title.padded().or_not())
        .then(subtitle.padded().or_not())
        .then(footer.padded().or_not())
        .then(block)
        .boxed()
        .map_with(|((((id, title), subtitle), footer), body), e| {
            (
                match id {
                    "column::" => Expr::Column(Component {
                        title: match title {
                            Some(title) => Some(Box::new(title)),
                            None => None,
                        },
                        subtitle: match subtitle {
                            Some(subtitle) => Some(Box::new(subtitle)),
                            None => None,
                        },
                        footer: match footer {
                            Some(footer) => Some(Box::new(footer)),
                            None => None,
                        },
                        body,
                    }),
                    "row::" => Expr::Row(Component {
                        title: match title {
                            Some(title) => Some(Box::new(title)),
                            None => None,
                        },
                        subtitle: match subtitle {
                            Some(subtitle) => Some(Box::new(subtitle)),
                            None => None,
                        },
                        footer: match footer {
                            Some(footer) => Some(Box::new(footer)),
                            None => None,
                        },
                        body,
                    }),
                    _ => {
                        eprintln!("> Unreachable: {id:?}");
                        unreachable!()
                    }
                },
                e.span(),
            )
        });

    many.or(single).with_ctx(0)
}

fn parse<'src>(
) -> impl Parser<'src, &'src str, Spanned<Expr>, extra::Err<Rich<'src, char, Span>>>
{
    let ident = text::ascii::ident()
        .then_ignore(just("::").ignore_then(just(' ').or_not()))
        .map(|z: &str| z.to_string());

    let title_ = just("title::").then_ignore(just(' ').or_not()).ignored();
    let subtitle_ =
        just("subtitle::").then_ignore(just(' ').or_not()).ignored();
    let footer_ = just("footer::").then_ignore(just(' ').or_not()).ignored();

    let lines = any()
        .and_is(ident.not())
        .and_is(just('\n').not())
        .repeated()
        .at_least(1)
        .collect::<String>()
        .repeated()
        .collect::<Vec<String>>()
        .map(|lines| lines.join("\n"))
        .map(|s| Expr::Text(s.trim().to_string()))
        .labelled("Line")
        .then_ignore(text::newline())
        .map_with(|x, e| (x, e.span()));

    let title = title_
        .ignore_then(text::newline().not())
        .ignore_then(lines.padded())
        .map(|content| Expr::Title(Box::new(content)))
        .map_with(|tok, e| (tok, e.span()));

    let subtitle = subtitle_
        .ignore_then(text::newline().not())
        .ignore_then(lines.padded())
        .map(|content| Expr::Subtitle(Box::new(content)))
        .map_with(|tok, e| (tok, e.span()));

    let footer = footer_
        .ignore_then(text::newline().not())
        .ignore_then(lines.padded())
        .map(|content| Expr::Footer(Box::new(content)))
        .map_with(|tok, e| (tok, e.span()));

    let page = just("[page]")
        .padded()
        .labelled("Page")
        .ignore_then(text::newline().repeated())
        .ignore_then(title.or_not())
        .then(subtitle.or_not())
        .then(footer.or_not())
        .boxed()
        .then(block_parse())
        .boxed()
        .map(|(((title, subtitle), footer), body)| Component {
            title: match title {
                Some(title) => Some(Box::new(title)),
                None => None,
            },
            subtitle: match subtitle {
                Some(subtitle) => Some(Box::new(subtitle)),
                None => None,
            },
            footer: match footer {
                Some(footer) => Some(Box::new(footer)),
                None => None,
            },
            body,
        })
        .map_with(|c, e| (Expr::Page(Box::new(c)), e.span()));

    page.separated_by(text::newline().repeated().at_least(1))
        .collect()
        .map_with(|pages, e| (Expr::Document(pages), e.span()))
}

#[derive(Clone, Debug, PartialEq)]
pub enum Expr {
    Text(String),
    Title(Box<Spanned<Expr>>),
    Subtitle(Box<Spanned<Expr>>),
    Footer(Box<Spanned<Expr>>),
    Single(Box<Component<Spanned<Expr>>>),
    List(Vec<Spanned<Expr>>),
    Column(Component<Vec<Spanned<Expr>>>),
    Row(Component<Vec<Spanned<Expr>>>),
    Page(Box<Component<Spanned<Expr>>>),
    Document(Vec<Spanned<Expr>>),
}