Some way to cache the parsed results?

[jbham]

Hello,

First of all, thanks for the great library!

I am trying to create an Excel like formula expression language using winnow and my prototype seems to be working. However, it has some serious downsides when the expression is long and deeeeeeply nested.

Example 1:

Function1(ToDate("SomeDate", "DateFormat"), GetSomeThing(Argument1) < GetThisThing(Argument1))

Since I can't right know right off the bat whether "Function1" is a binary operand OR one of the other possible operands like unary, function call, literal, etc, I have to literally try parsing "Function1" (or any other expression) as binary expression first and then other things.

For instance, I could have had above expression written differently as follows:

Example 2:
Function1(ToDate("SomeDate", "DateFormat"), GetSomeThing(Argument1) < GetThisThing(Argument1)) == true

In this case, I would use the parsed results from Function 1 to compare against true

So, the problem is that I have to parse the same thing multiple times.

This approach works great for small to mid expressions and im getting my expected result. But, as you can probably tell, if the expression is deeply deeply nested then performance is going to be bad, and, in my case, the evaluation doesn't even complete.

To mitigate this issue, I was thinking about passing a hashmap to the parser using winnow::stream::Stateful<&'a mut &'b [Token], State<'a>> where State<'a> will contain a hashmap. If during binary expression parsing step, I come across a function call which turns out not to be a binary expression related, then i would cache the parsed result and when I actually parse the same function as the function_call then I can simply get the already parsed expression from the map.

But, after much struggle, it seems to me that only simple values can be passed to the StateFul struct.

Maybe I need to change my approach altogether? Any recommendations/helpful would be greatly appreciated!

My background: Noob in parsing

[jbham]

Seems like its related to this #480?

[epage]

Yes, packrat parsing would help with how you are parsing but my hope is that there are other ways to improve things.

For example, if you split up lexing and parsing, then the cost of re-parsing a section in an alt will be dramatically lower. Unsure if pratt parsing (#131) reduces the number of passes in handling each expression.

[jbham]

My lexer and parser are separated. But I believe the problem will still persist even if I do more on the lexing side because I wont know how deep I need to go into a function before determining whether its a binary expression or a function call.

Anyway to use Stateful and pass in a hashmap/vec? I really wanted to do something like below but use HashMap or Vec instead of u32:
https://docs.rs/winnow/latest/winnow/stream/struct.Stateful.html
This way, I can update the map/vec with the things I have parsed and utilize it wherever I need.

Another plus with this approach would be that winnow wouldn't have to worry about the packrat storage. The user get to decide whether a storage is required and if it is required then at what step it is actually needed to be used because it wouldnt make sense to use it across all parsers. Thoughts?

[epage]

My lexer and parser are separated. But I believe the problem will still persist even if I do more on the lexing side because I wont know how deep I need to go into a function before determining whether its a binary expression or a function call.

I'm assuming the cost of throwing away parsing of tokens is a lot less than throwing away the parsing of bytes, which is why I called it out.

Is this something that an end-user benchmark has identified is a problem in a user-noticeable way?

Anyway to use Stateful and pass in a hashmap/vec? I

Yes, you can. The current docs use Cell but for those types you likely want RefCell.

except

You don't need Cell / RefCell at all except to use Parser::parse due to a trait bound that is no longer needed. This wasn't found because before 0.5, Cell/RefCell was needed anyways.

This is now fixed in #566 and was released in 0.6.14 and the docs now show just using a &mut directly

[jbham]

Is this something that an end-user benchmark has identified is a problem in a user-noticeable way?

Yes, this came up after trying to test a user facing expression which is a 16 levels of deeply nested If-else-then expression which also contains other functions and binary operations within it. At 7 levels, it took 1:30 minutes to complete. At level 9, it stopped completing :|. See sample expression below:

If(
    And(
        Or(
            Column("ColumnName1") == "ColumnValue1",
            Column("ColumnName1") == "ColumnValue2",
            Column("ColumnName1") == "ColumnValue3"
        ),
        Or(
            Column("ColumnName2") == "ColumnValue21", Column("ColumnName2") == "ColumnValue22", Column("ColumnName2") == "ColumnValue23",
            Column("ColumnName2") == "ColumnValue24", Column("ColumnName2") == "ColumnValue25", Column("ColumnName2") == "ColumnValue26"
        ),
        Column("ColumnName3") == false,
        Column("ColumnName4") != 3,
        Column("ColumnName4") != 5,
        Column("ColumnName5") != "New",
        Column("ColumnName5") != "Old"
    ),
    Column("ColumnName6"), // condition 1

    If(
        And(
            Or(
                Column("ColumnName1") == "ColumnValue1",
                Column("ColumnName1") == "ColumnValue2",
                Column("ColumnName1") == "ColumnValue3"
            ),
            Or(
                Column("ColumnName2") == "ColumnValue21", Column("ColumnName2") == "ColumnValue22", Column("ColumnName2") == "ColumnValue23",
                Column("ColumnName2") == "ColumnValue24", Column("ColumnName2") == "ColumnValue25", Column("ColumnName2") == "ColumnValue26"
            ),
            Column("ColumnName3") == true,
            Column("ColumnName4") != 3,
            Column("ColumnName4") != 5,
            Column("ColumnName5") != "New",
            Column("ColumnName5") != "Old"
        ),
        Column("ColumnName6") + 56, // condition 2
        ....and so on
        )
    )
)

This is now fixed in #566 and was released in 0.6.14 and the docs now show just using a &mut directly

Thank you for pushing this commit. Let me play around with it and see how it comes along. I have got quite a bit of refactoring to do :)

[jbham]

Maybe it wasn't as simple as i thought it would be :(

I keep getting this error message:

error[E0277]: the trait bound `&'s mut &'i [my_expression::token::Token]: winnow::stream::Stream` is not satisfied
   --> src/my_expression/parser_impl.rs:102:34
    |
102 |         let x = one_of(TokenType::WhiteSpace).context(expected("whitespace")).parse_next(i)?;
    |                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `winnow::stream::Stream` is not implemented for `&'s mut &'i [my_expression::token::Token]`, which is required by `winnow::Stateful<&'s mut &'i [my_expression::token::Token], &'s mut [std::string::String]>: winnow::stream::Stream`
    |
    = help: the trait `winnow::stream::Stream` is implemented for `&'i [T]`
    = note: required for `winnow::Stateful<&'s mut &'i [my_expression::token::Token], &'s mut [std::string::String]>` to implement `winnow::stream::Stream`



error[E0277]: the trait bound `&'s mut &'i [my_expression::token::Token]: winnow::stream::StreamIsPartial` is not satisfied
   --> src/my_expression/parser.rs:104:34
    |
104 |         let x = one_of(TokenType::WhiteSpace).context(expected("whitespace")).parse_next(i)?;
    |                                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `winnow::stream::StreamIsPartial` is not implemented for `&'s mut &'i [my_expression::token::Token]`, which is required by `winnow::Stateful<&'s mut &'i [my_expression::token::Token], my_expression::parser::State<'s>>: winnow::stream::StreamIsPartial`
    |
    = help: the trait `winnow::stream::StreamIsPartial` is implemented for `&'a [T]`
    = note: required for `winnow::Stateful<&'s mut &'i [my_expression::token::Token], my_expression::parser::State<'s>>` to implement `winnow::stream::StreamIsPartial`
note: required by a bound in `winnow::token::one_of`
   --> /path/to/winnow-0.6.14/src/token/mod.rs:264:12
    |
262 | pub fn one_of<Input, Set, Error>(set: Set) -> impl Parser<Input, <Input as Stream>::Token, Error>
    |        ------ required by a bound in this function
263 | where
264 |     Input: StreamIsPartial + Stream,
    |            ^^^^^^^^^^^^^^^ required by this bound in `one_of`

These are my types:

type TokenSliceInner<'s, 'i> = &'s mut &'i [Token];
type TokenSliceWithStorage<'s, 'i> = winnow::stream::Stateful<TokenSliceInner<'s, 'i>, &'s mut [MyType]>;

Before the usage of Stateful, I was simply passing TokenSliceInner everywhere and it worked fine. I thought that since Stateful is already implemented with Stream and StreamPartial and I was able to use TokenSliceInner before, then I should be able to use the new TokenSliceWithStorage type, right?

Am I missing something basic or do I need to implement all the traits from here for TokenSliceInner?