Spent more time on today's than any previous one. I of course saw it as a parser combinator problem, whereas I think most people will see it through a regex lens. So I spent a lot of time trying to make it both backtracking and error-reporting before realising the error reporting isn't part of the problem. This simplification fixed it for me then a few refactoring iterations later I've got it to the following. My solution is general for all tail-recursive sequences, not specific to the problem posed as suggested in the text. No string copies, as few Vec copies as I can get away with, and I'm actively looking into reducing the final ones as I have a similar problem in another project I'm working on and want to make as efficient as possible.
I managed to avoid most of the Vec copies by building an iterator structure for the whole thing. This means almost the whole matcher is now lazily evaluated. Just in the tail recursion part I need to iterate the results twice so there's no choice but to collect into a temporary Vec. Lots of lifetime annotations needed to make it work as it's a big old complex data structure in memory, but it's cool to see this sort of thing can be done if needed with compile time memory management.
Spent more time on today's than any previous one. I of course saw it as a parser combinator problem, whereas I think most people will see it through a regex lens. So I spent a lot of time trying to make it both backtracking and error-reporting before realising the error reporting isn't part of the problem. This simplification fixed it for me then a few refactoring iterations later I've got it to the following. My solution is general for all tail-recursive sequences, not specific to the problem posed as suggested in the text. No string copies, as few
Vec
copies as I can get away with, and I'm actively looking into reducing the final ones as I have a similar problem in another project I'm working on and want to make as efficient as possible.I managed to avoid most of the Vec copies by building an iterator structure for the whole thing. This means almost the whole matcher is now lazily evaluated. Just in the tail recursion part I need to iterate the results twice so there's no choice but to collect into a temporary Vec. Lots of lifetime annotations needed to make it work as it's a big old complex data structure in memory, but it's cool to see this sort of thing can be done if needed with compile time memory management.