How to do grammar rule coverage?

[michael-brade]

Hi, when I write a large grammar I usually also try to write unit tests that cover all the grammar rules. However, it is not so easy to find out if actually all the possibilities are tested. Since PEGTL rules are basically just C++ type declarations, gcov doesn't show them at all.

Do you have any methods or tricks of how to find out about how many rules a parser run covered?

[ColinH]

The heavily templated nature of the PEGTL in general, and the way that parsing rules are defined in particular, indeed render gcov hard to use, or even pretty useless. We don't really have a ready solution, our usual approach can best be described as "write a lot of testcases while you still remember everything about the grammar", and that works well if you are thorough.

If I were to try and build some kind of grammar-rule-coverage I would probably start with the tracer in tao/pegtl/contrib/tracer.hh and adapt it to fill out a data structure with information on which rules were attempted to match, and whether they ever succeeded and failed. Of course that doesn't give you a list of all rules in the grammar, but at least it's something.

Generating a list of all (sub-)rules of a grammar might be possible using the analysis_t type member of the rules. Starting with the starting rule it can be used to obtain a list of sub-rules to recursively walk the whole grammar. It doesn't give all the details about the rules, but for your use case it should be enough just to know which rules exist.

[michael-brade]

Thank you for this quick response! Yes, your first paragraph is also my usual approach :-)
I really like your suggestion with the tracer, though, and I'll try that.

[ColinH]

Let us know how it goes, would be interesting to see what you manage to put together, you won't be the only person wanting a rule coverage test!

[ColinH]

@michael-brade Did you manage to get something up-and-running? Do you need any help?

[michael-brade]

thanks for asking, but no, I did not get the time to do so yet... crazy current situation! I did not forget, though.

[ColinH]

Right, sorry, I forgot the most important thing: Stay healthy!

[michael-brade]

😆 no problem, I'm not worried about the virus at all. It's what they make out of it that is the problem....

[ColinH]

The new meta branch contains an example for how to do a simple grammar coverage with the new infrastructure that should, if all goes well, be merged into master soon. It's not pretty or finished yet, just to show what your question set in motion :-)

[ColinH]

The meta branch has now been merged into master, and the coverage() function further enhanced, the only thing missing is fiddling around with the states so that it also works for grammars that require states during parsing.

[michael-brade]

I had a look at it yesterday and I am impressed! :-) So little code for so much functionality. The day just didn't have enough hours for me to test it on my project. Thanks for your quick solution, I hope I'll get to it today.

[ColinH]

We have further improved and refined the implementation, most importantly making it fully compatible with custom controls, actions and states.

I will close this issue for now, but please feel free to ask any further questions, or reopen the issue, if something does not work for you.

And thank you for asking about rule coverage; we hadn't planned this refactoring, but it was a good opportunity and we like the result :-)

[michael-brade]

Wow, really great work! And again, it took longer than expected -- I'm not even done yet, partly because I had to migrate to 3.0 first :-D

But I do already have a little bit of feedback. Let me suggest to expand the migration guide for 3.0.0:

• tao/pegtl/contrib/tracer.hpp is now tao/pegtl/contrib/trace.hpp
• tao::pegtl::tracer -> tao::pegtl::trace_control
• demangle(typeid(RuleName).name()) -> demangle<RuleName>()

parse_tree:

• node->name() -> node->type, and it now returns a std::string_view
• node->content() -> string() and string_view()

The Parse-Tree.md doc needs updating as well, it still refers to name() ;-)

When I'm done with all of it, I'll let you know about the coverage part.

[d-frey]

Thanks! I implemented almost all of those suggestions, only the tracer part is still missing as Colin and me are going to work on that a little bit more.

[michael-brade]

Very nice again! I have now gotten the coverage to work. It looks good with exactly the required information!

One question/suggestion: my unit tests consist of many different calls to parse, each testing a certain subset of rules, some start at the root rule but not all. The PEGTL api right now gives me coverage for each individual call but not the overall coverage of all unit tests, and it is not possible to pass the previous coverage object to the following coverage call.

So what about a new function like

tao::pegtl::coverage_result
tao::pegtl::merge_coverage(std::initializer_list<tao::pegtl::coverage_result>)

to merge individual coverage result objects?

[michael-brade]

And another issue: tao::pegtl::coverage<Rule>(source) fails if Rule throws a parse_error. I just get map::at, I cannot seem to get a backtrace in gdb (yet).

[ColinH]

So you are trying to get coverage information for a parsing run that failed with an exception, and the exception was produced by what, an action rather than a rule?

PS: We are working on the merge.

[ColinH]

We reduced the coverage_result to a type-alias for the result map, and changed the interface to the coverage() function to take such a map by mutable-reference, that way you should be able to fill one map over multiple parsing runs.

[michael-brade]

So you are trying to get coverage information for a parsing run that failed with an exception,

Yes, exactly.

and the exception was produced by what, an action rather than a rule?

good question, I don't know yet :-) Will check after I updated to your new code.

[ColinH]

I'm assuming everything is working for now, otherwise, as usual, feel free to come back here with any question and/or reopen this issue.

[michael-brade]

Yes, I will. Again, I am behind with a TODO list that is too long. I will get back to this probably next week.