Reported on Twitter https://twitter.com/Wasquen/status/1276906414833758208?s=20

Awesome! Good job! I'm working on a small library using Parsica I'd like to open source.

I'm facing some performance issues.

How would you parse efficiently ordered file paths to build a tree?

[
  "/a/b/c/file1",
  "/a/b/c/file2",
  "/a/b/c/file3",
  "/a/b/file4"
]

I'd like to avoid to parse "/a/b/c/" many times.

It's hard to do anything dodgy because I don't have access to remainder/input.

Hi there. Thanks for great project!

I have a quesion. I need to validate AST which I build inside map(...) functions. But I don't know how to keep track of current position whie generating AST nodes to print meaningful messages. Is it possible to pass current position to map() function so it can be saved into AST node?

this PR does 2 things

• use mb_* functions only, when the string beeing streamed contains multibyte chars. that way we can use way faster non mb-string functions on non-multibyte strings
• use full-qualified call to string and multibyte-string functions, which allows the php parser to apply compile time optimizations when strings are known (e.g. string literals)

inspired by your blackfire session on twitch yesterday, I took a stab at improving performance on parsica.

https://blackfire.io/profiles/compare/554e2a9c-1726-43a1-b626-95aa2a230949/graph

using static function instead of function reduces overhead of php in callables, because the runtime does not need to introduce a $this object for each function.

Hi! ✋ This library looks great and I would like to take a closer look.

Let's say I would like to practice on annotations.

/**
* @foo Simple line
* @bar Advanced line with !@#$%^&*()
* @baz Multi line
*            with extra line
*/

Could you please point me how to start with it? :-)

Thank you, Felix

I have simple math expression defined like this

$arithmeticExpression->recurse(expression(
    $parens($arithmeticExpression)->or($token($term)),
    [
        leftAssoc(
            binaryOperator($token(string("-")), fn($l, $r) => new MinusOperator($l, $r))
        ),
        leftAssoc(
            binaryOperator($token(string("+")), fn($l, $r) => new PlusOperator($l, $r))
        ),
    ]
));

But this parser succeeds when only term provided. F.e. it parses inputs like 123 + 321 and just 123

Hot to prevent it succeed parsing without any operator?

remove calls to gettype() which is the most expensive operation within appendSuccess

before

staabm@staabm_laptop MINGW64 /c/xampp7.3/htdocs/redaxo/redaxo/src/addons/parsica (simplify-type)
$ /c/xampp7.4.2/php/php /c/dev/composer/vendor/bin/phpbench run benchmarks --report=aggregate  --retry-threshold=5
PHPBench @git_tag@ running benchmarks...
with configuration file: C:\xampp7.3\htdocs\redaxo\redaxo\src\addons\parsica/phpbench.json
with PHP version 7.4.1, xdebug ❌, opcache ❌

\JSONBench

    bench_json_encode.......................I2 ✔ Mo13.241μs (±1.899%)
    bench_Parsica_JSON......................I2 ✔ Mo21,338.523μs (±1.071%)
    bench_basemax_jpophp....................I2 ✔ Mo1,375.314μs (±0.654%)

⅀T: 67,812.200μs μSD/r 78.783μs μRSD/r: 1.208%

Subjects: 3, Assertions: 0, Failures: 0, Errors: 0
suite: 134628a77f5b70ee8034abd04114ab3247c4f4cd, date: 2021-03-14, stime: 21:27:10
+-----------+----------------------+-----+------+-----+------------+--------------+--------------+--------------+--------------+-----------+--------+-----------+
| benchmark | subject              | set | revs | its | mem_peak   | best         | mean         | mode         | worst        | stdev     | rstdev | diff      |
+-----------+----------------------+-----+------+-----+------------+--------------+--------------+--------------+--------------+-----------+--------+-----------+
| JSONBench | bench_json_encode    | 0   | 5    | 3   | 1,666,776b | 12.800μs     | 13.133μs     | 13.241μs     | 13.400μs     | 0.249μs   | 1.90%  | 1.00x     |
| JSONBench | bench_Parsica_JSON   | 0   | 5    | 3   | 2,182,400b | 20,891.400μs | 21,210.467μs | 21,338.523μs | 21,401.400μs | 227.066μs | 1.07%  | 1,615.01x |
| JSONBench | bench_basemax_jpophp | 0   | 5    | 3   | 1,867,520b | 1,373.200μs  | 1,380.467μs  | 1,375.314μs  | 1,393.200μs  | 9.034μs   | 0.65%  | 105.11x   |
+-----------+----------------------+-----+------+-----+------------+--------------+--------------+--------------+--------------+-----------+--------+-----------+

after

staabm@staabm_laptop MINGW64 /c/xampp7.3/htdocs/redaxo/redaxo/src/addons/parsica (simplify-type)
$ /c/xampp7.4.2/php/php /c/dev/composer/vendor/bin/phpbench run benchmarks --report=aggregate  --retry-threshold=5
PHPBench @git_tag@ running benchmarks...
with configuration file: C:\xampp7.3\htdocs\redaxo\redaxo\src\addons\parsica/phpbench.json
with PHP version 7.4.1, xdebug ❌, opcache ❌

\JSONBench

    bench_json_encode.......................I2 ✔ Mo13.436μs (±2.08%)
    bench_Parsica_JSON......................I2 ✔ Mo20,541.307μs (±2.514%)
    bench_basemax_jpophp....................R3 I2 ✔ Mo1,366.153μs (±1.837%)

⅀T: 66,626.400μs μSD/r 182.998μs μRSD/r: 2.143%

Subjects: 3, Assertions: 0, Failures: 0, Errors: 0
suite: 134628ae7cb50c4018c4881c0c020c1f4335617d, date: 2021-03-14, stime: 21:26:40
+-----------+----------------------+-----+------+-----+------------+--------------+--------------+--------------+--------------+-----------+--------+-----------+
| benchmark | subject              | set | revs | its | mem_peak   | best         | mean         | mode         | worst        | stdev     | rstdev | diff      |
+-----------+----------------------+-----+------+-----+------------+--------------+--------------+--------------+--------------+-----------+--------+-----------+
| JSONBench | bench_json_encode    | 0   | 5    | 3   | 1,666,792b | 13.400μs     | 13.600μs     | 13.436μs     | 14.000μs     | 0.283μs   | 2.08%  | 1.00x     |
| JSONBench | bench_Parsica_JSON   | 0   | 5    | 3   | 2,180,704b | 20,411.200μs | 20,840.067μs | 20,541.307μs | 21,577.600μs | 523.818μs | 2.51%  | 1,532.36x |
| JSONBench | bench_basemax_jpophp | 0   | 5    | 3   | 1,867,520b | 1,321.800μs  | 1,355.133μs  | 1,366.153μs  | 1,381.600μs  | 24.891μs  | 1.84%  | 99.64x    |
+-----------+----------------------+-----+------+-----+------------+--------------+--------------+--------------+--------------+-----------+--------+-----------+

To find EOF, we just want to know if the length of the remaining string is 0. We don't need to use mb_strlen() for that, because in an empty string, there shouldn't be any multibyte characters anyway.

See also #32

Co-authored-by: Markus Staab [email protected]

While testing some things in the JSON parser benchmarks when writing this, i found these:

⚡️ Write character parsers instead of string parsers

Since we're looking for a backslash, followed by a character from a list of special escaped characters, we can make this a simpler parse than looking for the explicit combinations as strings. This makes us backtrack less.

This results in a x3 speed improvement for parsing strings.

⚡️ Using takeWhile(f) is faster than zeroOrMore(satisfy(f)) combo

Because it doesn't have to run the parser completely, every time. It can just rely on the stream implementation. This results in a ± x1.25 speed improvement according to some benchmarks I did.

⚡️ Accept any character in JSON Strings instead of the special ones first

Instead of looking for special characters first, and backtracking if we don't find them, look for the accepted ones first, and parse the special ones only if that fails.

This results in a x1.35 speed improvement in the benchmarks I did.

The function call is very very fast and very little differences will have a large effect on rel. comparision to parsica. Try to make it more stable.

Motivation: in https://github.com/parsica-php/parsica/pull/45#issue-602130996 the benchmark went from 12.533μs (before-mean) to 13.333μs (after-mean) which is a diff of ~ 10% without other modifications

• Added a benchmark which encapsulates the old implementation and compares to the new implementation
• Created the new implementation based on a while loop

This is 4 times faster than the old many in some basic tests...

Subjects: 5, Assertions: 0, Failures: 0, Errors: 0
suite: 134628ad035def57f08210ae05b1eb88c2d8ce07, date: 2021-03-14, stime: 22:26:52
+-----------+----------------------+-----+------+-----+------------+-----------+-----------+-----------+-----------+----------+--------+-------+
| benchmark | subject              | set | revs | its | mem_peak   | best      | mean      | mode      | worst     | stdev    | rstdev | diff  |
+-----------+----------------------+-----+------+-----+------------+-----------+-----------+-----------+-----------+----------+--------+-------+
| ManyBench | bench_takeWhile      | 0   | 10   | 10  | 1,825,752b | 97.400μs  | 109.530μs | 106.858μs | 133.200μs | 10.392μs | 9.49%  | 1.00x |
| ManyBench | bench_manySatisfy    | 0   | 10   | 10  | 1,862,264b | 208.700μs | 244.190μs | 225.526μs | 352.000μs | 41.893μs | 17.16% | 2.23x |
| ManyBench | bench_manyChar       | 0   | 10   | 10  | 1,863,008b | 232.100μs | 244.510μs | 237.852μs | 262.400μs | 9.926μs  | 4.06%  | 2.23x |
| ManyBench | bench_oldManySatisfy | 0   | 10   | 10  | 2,959,440b | 712.800μs | 765.140μs | 740.255μs | 910.400μs | 56.543μs | 7.39%  | 6.99x |
| ManyBench | bench_oldManyChar    | 0   | 10   | 10  | 2,960,192b | 733.100μs | 781.460μs | 757.570μs | 878.500μs | 48.064μs | 6.15%  | 7.13x |
+-----------+----------------------+-----+------+-----+------------+-----------+-----------+-----------+-----------+----------+--------+-------+

I am sorry to read about the passing of the maintainer of this library.

I just recently learned about this library and think it's definitely keeping alive in one form or another. mathiasverraes (intentionally not yet pinging you) you mentioned there is no maintainer, what kind of maintenance are you looking for exactly? Are you able / willing to review PRs, or just able to hand over appropriate permissions to a new maintainer or new maintainer(s)?

From what I can see the library is well tested and merging in at least some of the PRs should be pretty safe. While I don't have a lot of time to maintain the library I am interesting in helping out, the first things I would do:

• Update CI to enforce code style (ecs)
• Update CI to enforce commit messages
• Update CI to automate releases based on commit messages
• Set up git hooks (captainhook) to automate the above for contributors

These steps should make it relatively painless to accept small iterative improvements.

If people want to (help) in maintaining this library please respond here, if mathias doesn't respond in a few days I'll consider pinging him and hopefully he can guide us forward a bit.

Curious, I am trying to extend your expression example, by allowing variable names with "." separators:

        $identifier = atLeastOne(alphaChar());
        $identifierDot = many($identifier->optional()->append(char('.')));

This isn't working, so I'm clearly not understanding how this library works. What am I missing? I'm stuck trying to think of the problem in terms of a regex solution.

How would I parse / match a variable with arbitrary number of '.' separators? And have that returned to the AST as a complete string, not further parsed.

Any help much appreciated :)

related: #17 inspired by this regex:

/^
  "[^"\\]*              # double quoted strings with possibly escaped double quotes
    (?:
      \\.               # escaped character (quote)
      [^"\\]*           # unrolled loop following Jeffrey E.F. Friedl
    )*
  "
/x

i implemented an unrolled loop in combination with takeWhile. (the last use of the deprecated zeroOrMore was also removed) this leads to a big performance boost from ca ~250%(without xdebug) - ~330%(with xdebug) - both without opcache.

before: bench_json_encode: 4.133μs bench_Parsica_JSON: 4.109ms bench_basemax_jpophp: 432.128μs

after: bench_json_encode: 3.744μs bench_Parsica_JSON: 1.662ms bench_basemax_jpophp: 401.154μs

In response to @mathiasverraes ' tweet here:

I think the documentation is very useful and developer-friendly already. I thought of a couple of things that might be improved:

• For most developers I think the closest thing to parsing that they already know and understand is regular expressions. At times, as a user of this library I felt like "if I could just use a regex, I'd be done already". Still, I wanted to do the right thing, and I kept looking for similar concepts and found them, like atLeastOne, zeroOrMore, between. In terms of documentation, I think it would be really helpful if there would be a page that shows some simple regexes and then shows and explains the alternative using parsers.
• I think it will be interesting to have a chapter that shows alternatives for different parsers that achieve the same thing, or how some some parsers are shortcuts of others.
• The parts of the documentation that say "TODO" should be removed because they aren't useful for the reader, only for the writer/maintainer.
• The JSON parser is a great source for learning material, and I think it may deserve a full explanation in the documentation.
• It's very confusing that some parsers are marked as @deprecated; they are not in fact deprecated, it just seems they are not tested. As a user of the library it makes you feel somewhat bad about using these parsers, even though there's no alternative.

Great work on the type annotations by the way, those are really helpful, and I think it's amazing that this is now possible in PHP today.

Thanks a lot for this awesome library! It was a nice thing to dive in and get to know.

Since I use collect() to capture values that are to be fed into an AST node, it would be very helpful to use a map instead of a list. Similarly to how you can capture named groups with regular expressions. Here's an example where I parse a Markdown heading:

return collect(
            keepFirst(atLeastOne(char('#')), skipSpace1()),
            atLeastOne(satisfy(fn (string $char) => ! in_array($char, ["\n"], true))),
            self::newLineOrEof()
        )->map(fn (array $output) => new Heading(strlen($output[1]), $output[2], $output[0]));

Suggested improvement (last line)

return collect(
            keepFirst(atLeastOne(char('#')), skipSpace1()),
            atLeastOne(satisfy(fn (string $char) => ! in_array($char, ["\n"], true))),
            self::newLineOrEof()
        )->map(fn (array $output) => new Heading(strlen($output['level']), $output['title']));

One way could be to use label() for each collected parser and use the label as the array key passed to map():

return collect(
            keepFirst(atLeastOne(char('#')), skipSpace1())->label('level'),
            atLeastOne(satisfy(fn (string $char) => ! in_array($char, ["\n"], true)))->label('title'),
            self::newLineOrEof()
        )->map(fn (array $output) => new Heading(strlen($output['level']), $output['title']));

The advantage being that label() is already there and used for a similar purpose. However, this might lead to values being overwritten if you collect two parsers with the same name. Another option is to provide the map upfront:

return collect([
            'level' => keepFirst(atLeastOne(char('#')), skipSpace1()),
            'title' => atLeastOne(satisfy(fn (string $char) => ! in_array($char, ["\n"], true))),
            'eol' => self::newLineOrEof()
        ])->map(fn (array $output) => new Heading(strlen($output['level']), $output['title']));

It might be useful to have separate collectList() and collectMap() functions by the way.