Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[build] Add grammar coverage tool. #3365

Closed
kaby76 opened this issue May 4, 2023 · 2 comments · Fixed by #3511
Closed

[build] Add grammar coverage tool. #3365

kaby76 opened this issue May 4, 2023 · 2 comments · Fixed by #3511

Comments

@kaby76
Copy link
Contributor

kaby76 commented May 4, 2023 •
edited
Loading

I have a new that I've been working on the last few days called trcover. It analyzes grammars and input files, the determines the "hotspots" in the grammar, finally outputting a HTML-marked up version of the grammar for quick visualization of just what we are testing. I think I can output some other stats like percent of the grammar tested, which might be a good thing to add to the build and to help people write tests for there grammars.

I just did a test of the java8 grammar, and the visualization shows huge amounts of the grammar not be tested at all! The following zip contains an html file, which can be opened in a browser. Right now, I mark up symbols that are parsed at least one time with the same color. (There may be of course errors in my code!!)

cover.zip
@KvanTTT
Copy link
Member

KvanTTT commented May 4, 2023 •
edited
Loading

Thanks, but java8 grammar is outdated and very slow (because it quite strictly follows formal documentation). Also, java8 grammar has very small number of examples. I recommend using more advanced and faster java grammar.

@kaby76
Copy link
Contributor Author

kaby76 commented May 7, 2023

If a grammar is provided, it should be tested with a set of inputs that exercise a "reasonable" amount of the grammar. Unfortunately, some grammars have under 50% of the rules actually tested. The recently added Ada grammars are ~20%. Plsql, used by many, only tests ~60%. The Hive grammars are ~20%. That's really awful. It means that one could write a grammar for hive that is just 20% of the current grammar(s) each, and declare that it parses all of hive.

Providing a test suite is as hard as writing the grammar, if not more so. But, people should be encouraged to write quality code.

The trcover utility itself is rather slow because the regular expression automaton is an NFA with lots of epsilon transitions. It was stack-based until it ran into stack overflow issues for some grammars. It should be sped up before inserting in a build.

./abb/Generated-CSharp/cover.html:Percent rules covered 100
./abnf/Generated-CSharp/cover.html:Percent rules covered 100
./acme/Generated-CSharp/cover.html:Percent rules covered 71.17117117117117
./ada/ada2005/Generated-CSharp/cover.html:Percent rules covered 20.074349442379184
./ada/ada2012/Generated-CSharp/cover.html:Percent rules covered 18.33910034602076
./ada/ada83/Generated-CSharp/cover.html:Percent rules covered 25.31645569620253
./ada/ada95/Generated-CSharp/cover.html:Percent rules covered 20
./agc/Generated-CSharp/cover.html:Percent rules covered 87.5
./alef/Generated-CSharp/cover.html:Percent rules covered 40.98360655737705
./algol60/Generated-CSharp/cover.html:Percent rules covered 76.13636363636364
./alloy/Generated-CSharp/cover.html:Percent rules covered 68.96551724137932
./alpaca/Generated-CSharp/cover.html:Percent rules covered 56.52173913043478
./angelscript/Generated-CSharp/cover.html:Percent rules covered 15.555555555555555
./antlr/antlr2/Generated-CSharp/cover.html:Percent rules covered 78
./antlr/antlr3/Generated-CSharp/cover.html:Percent rules covered 80
./aql/Generated-CSharp/cover.html:Percent rules covered 96.7741935483871
./arithmetic/Generated-CSharp/cover.html:Percent rules covered 100
./asl/Generated-CSharp/cover.html:Percent rules covered 91.50943396226415
./asm/asm6502/Generated-CSharp/cover.html:Percent rules covered 100
./asm/asm8080/Generated-CSharp/cover.html:Percent rules covered 100
./asm/asm8086/Generated-CSharp/cover.html:Percent rules covered 100
./asm/asmMASM/Generated-CSharp/cover.html:Percent rules covered 57.4468085106383
./asm/asmZ80/Generated-CSharp/cover.html:Percent rules covered 100
./asm/pdp7/Generated-CSharp/cover.html:Percent rules covered 100
./asm/ptx/ptx-isa-1.0/Generated-CSharp/cover.html:Percent rules covered 85.71428571428571
./asm/ptx/ptx-isa-2.1/Generated-CSharp-large/cover.html:Percent rules covered 70.8108108108108
./asn/asn/Generated-CSharp/cover.html:Percent rules covered 31.292517006802722
./awk/Generated-CSharp/cover.html:Percent rules covered 70.73170731707317
./b/Generated-CSharp/cover.html:Percent rules covered 72.41379310344827
./basic/Generated-CSharp/cover.html:Percent rules covered 67.32673267326733
./bdf/Generated-CSharp/cover.html:Percent rules covered 100
./bencoding/Generated-CSharp/cover.html:Percent rules covered 100
./bibcode/Generated-CSharp/cover.html:Percent rules covered 100
./bibtex/Generated-CSharp/cover.html:Percent rules covered 38.888888888888886
./bicep/Generated-CSharp/cover.html:Percent rules covered 84.31372549019608
./bnf/Generated-CSharp/cover.html:Percent rules covered 69.23076923076923
./c/Generated-CSharp/cover.html:Percent rules covered 69.31818181818181
./calculator/Generated-CSharp/cover.html:Percent rules covered 100
./callable/Generated-CSharp/cover.html:Percent rules covered 100
./capnproto/Generated-CSharp/cover.html:Percent rules covered 100
./caql/Generated-CSharp/cover.html:Percent rules covered 14.814814814814815
./chip8/Generated-CSharp/cover.html:Percent rules covered 16.216216216216218
./clf/Generated-CSharp/cover.html:Percent rules covered 100
./clojure/Generated-CSharp/cover.html:Percent rules covered 22.5
./clu/Generated-CSharp/cover.html:Percent rules covered 42.857142857142854
./cmake/Generated-CSharp/cover.html:Percent rules covered 100
./cookie/Generated-CSharp/cover.html:Percent rules covered 77.77777777777777
./cql/Generated-CSharp/cover.html:Percent rules covered 95.83333333333333
./cql3/Generated-CSharp/cover.html:Percent rules covered 78.70036101083032
./creole/Generated-CSharp/cover.html:Percent rules covered 92.85714285714286
./css3/Generated-CSharp/cover.html:Percent rules covered 91.13924050632912
./csv/Generated-CSharp/cover.html:Percent rules covered 100
./ctl/Generated-CSharp/cover.html:Percent rules covered 100
./cto/Generated-CSharp/cover.html:Percent rules covered 97.5609756097561
./cypher/Generated-CSharp/cover.html:Percent rules covered 85.3932584269663
./dart2/Generated-CSharp/cover.html:Percent rules covered 97.10144927536231
./databank/Generated-CSharp/cover.html:Percent rules covered 85.71428571428571
./datalog/Generated-CSharp/cover.html:Percent rules covered 78.57142857142857
./dice/Generated-CSharp/cover.html:Percent rules covered 100
./dif/Generated-CSharp/cover.html:Percent rules covered 100
./doiurl/Generated-CSharp/cover.html:Percent rules covered 75
./dot/Generated-CSharp/cover.html:Percent rules covered 92.85714285714286
./edif300/Generated-CSharp/cover.html:Percent rules covered 9.615384615384615
./edn/Generated-CSharp/cover.html:Percent rules covered 100
./erlang/Generated-CSharp/cover.html:Percent rules covered 61.47540983606557
./esolang/brainflak/Generated-CSharp/cover.html:Percent rules covered 66.66666666666667
./esolang/brainfuck/Generated-CSharp/cover.html:Percent rules covered 100
./esolang/cool/Generated-CSharp/cover.html:Percent rules covered 100
./esolang/lolcode/Generated-CSharp/cover.html:Percent rules covered 17.24137931034483
./esolang/loop/Generated-CSharp/cover.html:Percent rules covered 100
./esolang/nanofuck/Generated-CSharp/cover.html:Percent rules covered 100
./esolang/sickbay/Generated-CSharp/cover.html:Percent rules covered 100
./esolang/snowball/Generated-CSharp/cover.html:Percent rules covered 43.75
./esolang/wheel/Generated-CSharp/cover.html:Percent rules covered 100
./evm-bytecode/Generated-CSharp/cover.html:Percent rules covered 100
./fasta/Generated-CSharp/cover.html:Percent rules covered 80
./fdo91/Generated-CSharp/cover.html:Percent rules covered 100
./fen/Generated-CSharp/cover.html:Percent rules covered 100
./flatbuffers/Generated-CSharp/cover.html:Percent rules covered 81.25
./flowmatic/Generated-CSharp/cover.html:Percent rules covered 100
./focal/Generated-CSharp/cover.html:Percent rules covered 95.83333333333333
./fol/Generated-CSharp/cover.html:Percent rules covered 88.88888888888889
./freedesktop/desktop-entry/Generated-CSharp/cover.html:Percent rules covered 93.75
./gdscript/Generated-CSharp/cover.html:Percent rules covered 61.36363636363637
./gedcom/Generated-CSharp/cover.html:Percent rules covered 81.25
./gff3/Generated-CSharp/cover.html:Percent rules covered 100
./gml/Generated-CSharp/cover.html:Percent rules covered 100
./golang/Generated-CSharp/cover.html:Percent rules covered 95.95959595959596
./graphstream-dgs/Generated-CSharp/cover.html:Percent rules covered 76.19047619047619
./gtin/Generated-CSharp/cover.html:Percent rules covered 97.29729729729729
./guido/Generated-CSharp/cover.html:Percent rules covered 93.10344827586206
./guitartab/Generated-CSharp/cover.html:Percent rules covered 100
./haskell/Generated-CSharp/cover.html:Percent rules covered 47.265625
./icalendar/Generated-CSharp/cover.html:Percent rules covered 11.466666666666667
./icon/Generated-CSharp/cover.html:Percent rules covered 49.056603773584904
./idl/Generated-CSharp/cover.html:Percent rules covered 50.93167701863354
./inf/Generated-CSharp/cover.html:Percent rules covered 100
./informix/Generated-CSharp/cover.html:Percent rules covered 23.5
./iri/Generated-CSharp/cover.html:Percent rules covered 38.095238095238095
./iso8601/Generated-CSharp/cover.html:Percent rules covered 75.53191489361703
./istc/Generated-CSharp/cover.html:Percent rules covered 100
./itn/Generated-CSharp/cover.html:Percent rules covered 100
./jam/Generated-CSharp/cover.html:Percent rules covered 91.66666666666667
./janus/Generated-CSharp/cover.html:Percent rules covered 66.66666666666667
./java/java/Generated-CSharp/cover.html:Percent rules covered 99.2063492063492
./java/java8/Generated-CSharp/cover.html:Percent rules covered 29.661016949152543
./java/java9/Generated-CSharp/cover.html:Percent rules covered 62.857142857142854
./javascript/javascript/Generated-CSharp/cover.html:Percent rules covered 87.01298701298701
./javascript/typescript/Generated-CSharp/cover.html:Percent rules covered 74.30555555555556
./jpa/Generated-CSharp/cover.html:Percent rules covered 10.227272727272727
./json/Generated-CSharp/cover.html:Percent rules covered 100
./json5/Generated-CSharp/cover.html:Percent rules covered 100
./karel/Generated-CSharp/cover.html:Percent rules covered 70
./kotlin/kotlin-formal/Generated-CSharp/cover.html:Percent rules covered 85.5421686746988
./kquery/Generated-CSharp/cover.html:Percent rules covered 83.78378378378379
./kuka/Generated-CSharp/cover.html:Percent rules covered 53.96825396825397
./lambda/Generated-CSharp/cover.html:Percent rules covered 100
./lark/Generated-CSharp/cover.html:Percent rules covered 100
./lcc/Generated-CSharp/cover.html:Percent rules covered 100
./less/Generated-CSharp/cover.html:Percent rules covered 37.83783783783784
./limbo/Generated-CSharp/cover.html:Percent rules covered 45.6140350877193
./lisa/Generated-CSharp/cover.html:Percent rules covered 80
./llvm-ir/Generated-CSharp/cover.html:Percent rules covered 40.90909090909091
./logo/logo/Generated-CSharp/cover.html:Percent rules covered 92.10526315789474
./lrc/Generated-CSharp/cover.html:Percent rules covered 100
./ltl/Generated-CSharp/cover.html:Percent rules covered 100
./lua/Generated-CSharp/cover.html:Percent rules covered 62.16216216216216
./lucene/Generated-CSharp/cover.html:Percent rules covered 92.85714285714286
./matlab/Generated-CSharp/cover.html:Percent rules covered 54.285714285714285
./mckeeman-form/Generated-CSharp/cover.html:Percent rules covered 85.71428571428571
./mdx/Generated-CSharp/cover.html:Percent rules covered 47.916666666666664
./memcached_protocol/Generated-CSharp/cover.html:Percent rules covered 20.512820512820515
./metamath/Generated-CSharp/cover.html:Percent rules covered 60.869565217391305
./metric/Generated-CSharp/cover.html:Percent rules covered 100
./microc/Generated-CSharp/cover.html:Percent rules covered 100
./modelica/Generated-CSharp/cover.html:Percent rules covered 82.05128205128206
./modula2pim4/Generated-CSharp/cover.html:Percent rules covered 32.432432432432435
./molecule/Generated-CSharp/cover.html:Percent rules covered 100
./moo/Generated-CSharp/cover.html:Percent rules covered 75.51020408163265
./morsecode/Generated-CSharp/cover.html:Percent rules covered 13.157894736842104
./mps/Generated-CSharp/cover.html:Percent rules covered 85
./muddb/Generated-CSharp/cover.html:Percent rules covered 100
./mumath/Generated-CSharp/cover.html:Percent rules covered 47.36842105263158
./mumps/Generated-CSharp/cover.html:Percent rules covered 74.28571428571429
./muparser/Generated-CSharp/cover.html:Percent rules covered 100
./newick/Generated-CSharp/cover.html:Percent rules covered 100
./oberon/Generated-CSharp/cover.html:Percent rules covered 42.10526315789474
./objc/Generated-CSharp/cover.html:Percent rules covered 79.16666666666667
./ocl/Generated-CSharp-expr/cover.html:Percent rules covered 23.529411764705884
./oncrpc/Generated-CSharp/cover.html:Percent rules covered 61.904761904761905
./orwell/Generated-CSharp/cover.html:Percent rules covered 41.07142857142857
./p/Generated-CSharp/cover.html:Percent rules covered 100
./parkingsign/Generated-CSharp/cover.html:Percent rules covered 97.05882352941177
./pascal/Generated-CSharp/cover.html:Percent rules covered 83.50515463917526
./pbm/Generated-CSharp/cover.html:Percent rules covered 100
./pcre/Generated-CSharp/cover.html:Percent rules covered 59.45945945945946
./pdn/Generated-CSharp/cover.html:Percent rules covered 100
./peoplecode/Generated-CSharp/cover.html:Percent rules covered 97.5
./php/Generated-CSharp/cover.html:Percent rules covered 77.53623188405797
./pii/Generated-CSharp/cover.html:Percent rules covered 83.33333333333333
./pl0/Generated-CSharp/cover.html:Percent rules covered 100
./ply/Generated-CSharp/cover.html:Percent rules covered 100
./postalcode/Generated-CSharp/cover.html:Percent rules covered 100
./powerbuilder/Generated-CSharp/cover.html:Percent rules covered 55.55555555555556
./prolog/Generated-CSharp/cover.html:Percent rules covered 75
./promql/Generated-CSharp/cover.html:Percent rules covered 85.71428571428571
./propcalc/Generated-CSharp/cover.html:Percent rules covered 87.5
./properties/Generated-CSharp/cover.html:Percent rules covered 100
./protobuf2/Generated-CSharp/cover.html:Percent rules covered 38.983050847457626
./protobuf3/Generated-CSharp/cover.html:Percent rules covered 90.56603773584905
./prov-n/Generated-CSharp/cover.html:Percent rules covered 68.62745098039215
./python/python/Generated-CSharp/cover.html:Percent rules covered 96.61016949152543
./python/python3/Generated-CSharp/cover.html:Percent rules covered 74.60317460317461
./qif/Generated-CSharp/cover.html:Percent rules covered 76.92307692307692
./quakemap/Generated-CSharp/cover.html:Percent rules covered 100
./racket-bsl/Generated-CSharp/cover.html:Percent rules covered 87.5
./racket-isl/Generated-CSharp/cover.html:Percent rules covered 70
./recfile/Generated-CSharp/cover.html:Percent rules covered 100
./redcode/Generated-CSharp/cover.html:Percent rules covered 87.5
./refal/Generated-CSharp/cover.html:Percent rules covered 78.26086956521739
./rfc1035/Generated-CSharp/cover.html:Percent rules covered 100
./rfc1960/Generated-CSharp/cover.html:Percent rules covered 88.88888888888889
./rfc822/rfc822-datetime/Generated-CSharp/cover.html:Percent rules covered 100
./rfc822/rfc822-emailaddress/Generated-CSharp/cover.html:Percent rules covered 45
./robotwars/Generated-CSharp/cover.html:Percent rules covered 100
./romannumerals/Generated-CSharp/cover.html:Percent rules covered 90.9090909090909
./ron/Generated-CSharp/cover.html:Percent rules covered 100
./rpn/Generated-CSharp/cover.html:Percent rules covered 100
./ruby/Generated-CSharp/cover.html:Percent rules covered 87.5
./rust/Generated-CSharp/cover.html:Percent rules covered 90.3061224489796
./scala/Generated-CSharp/cover.html:Percent rules covered 61.320754716981135
./scotty/Generated-CSharp/cover.html:Percent rules covered 55.55555555555556
./scss/Generated-CSharp/cover.html:Percent rules covered 97.9381443298969
./semver/Generated-CSharp/cover.html:Percent rules covered 100
./sexpression/Generated-CSharp/cover.html:Percent rules covered 100
./sgf/Generated-CSharp/cover.html:Percent rules covered 70.58823529411765
./sici/Generated-CSharp/cover.html:Percent rules covered 100
./sieve/Generated-CSharp/cover.html:Percent rules covered 71.42857142857143
./smiles/Generated-CSharp/cover.html:Percent rules covered 84.21052631578948
./smtlibv2/Generated-CSharp/cover.html:Percent rules covered 54.73684210526316
./snobol/Generated-CSharp/cover.html:Percent rules covered 28.571428571428573
./sparql/Generated-CSharp/cover.html:Percent rules covered 34.78260869565217
./spass/Generated-CSharp/cover.html:Percent rules covered 73.07692307692308
./sql/athena/Generated-CSharp/cover.html:Percent rules covered 40
./sql/derby/Generated-CSharp/cover.html:Percent rules covered 45.67901234567901
./sql/drill/Generated-CSharp/cover.html:Percent rules covered 51.80722891566265
./sql/hive/v2/Generated-CSharp/cover.html:Percent rules covered 21.024258760107816
./sql/hive/v3/Generated-CSharp/cover.html:Percent rules covered 18.37837837837838
./sql/hive/v4/Generated-CSharp/cover.html:Percent rules covered 14.257028112449799
./sql/informix-sql/Generated-CSharp/cover.html:Percent rules covered 93.75
./sql/mariadb/Generated-CSharp/cover.html:Percent rules covered 69.46778711484593
./sql/mysql/Positive-Technologies/Generated-CSharp/cover.html:Percent rules covered 67.89772727272727
./sql/phoenix/Generated-CSharp/cover.html:Percent rules covered 73.64341085271317
./sql/plsql/Generated-CSharp/cover.html:Percent rules covered 61.345987920621226
./sql/postgresql/Generated-CSharp/cover.html:Percent rules covered 79.21279212792128
./sql/snowflake/Generated-CSharp/cover.html:Percent rules covered 67.29323308270676
./sql/sqlite/Generated-CSharp/cover.html:Percent rules covered 38.05309734513274
./sql/trino/Generated-CSharp/cover.html:Percent rules covered 61.26126126126126
./sql/tsql/Generated-CSharp-0/cover.html:Percent rules covered 87.02791461412151
./star/Generated-CSharp/cover.html:Percent rules covered 100
./stellaris/Generated-CSharp/cover.html:Percent rules covered 100
./suokif/Generated-CSharp/cover.html:Percent rules covered 55.55555555555556
./swift-fin/Generated-CSharp/cover.html:Percent rules covered 100
./szf/Generated-CSharp/cover.html:Percent rules covered 100
./tcpheader/Generated-CSharp/cover.html:Percent rules covered 91.66666666666667
./teal/Generated-CSharp/cover.html:Percent rules covered 50
./telephone/Generated-CSharp/cover.html:Percent rules covered 100
./terraform/Generated-CSharp/cover.html:Percent rules covered 100
./tiny/Generated-CSharp/cover.html:Percent rules covered 100
./tinybasic/Generated-CSharp/cover.html:Percent rules covered 100
./tinyc/Generated-CSharp/cover.html:Percent rules covered 100
./tinymud/Generated-CSharp/cover.html:Percent rules covered 19.047619047619047
./tnsnames/Generated-CSharp/cover.html:Percent rules covered 69.66292134831461
./tnt/Generated-CSharp/cover.html:Percent rules covered 100
./toml/Generated-CSharp/cover.html:Percent rules covered 100
./trac/Generated-CSharp/cover.html:Percent rules covered 100
./tsv/Generated-CSharp/cover.html:Percent rules covered 100
./ttm/Generated-CSharp/cover.html:Percent rules covered 87.5
./turing/Generated-CSharp/cover.html:Percent rules covered 33.9622641509434
./turtle/Generated-CSharp/cover.html:Percent rules covered 89.47368421052632
./unicode/graphemes/Generated-CSharp/cover.html:Percent rules covered 100
./unreal_angelscript/Generated-CSharp/cover.html:Percent rules covered 44.20289855072464
./upnp/Generated-CSharp/cover.html:Percent rules covered 100
./url/Generated-CSharp/cover.html:Percent rules covered 100
./useragent/Generated-CSharp/cover.html:Percent rules covered 100
./vb6/Generated-CSharp/cover.html:Percent rules covered 79.11392405063292
./vba/Generated-CSharp/cover.html:Percent rules covered 20.408163265306122
./vhdl/Generated-CSharp/cover.html:Percent rules covered 49.01960784313726
./vmf/Generated-CSharp/cover.html:Percent rules covered 100
./wat/Generated-CSharp/cover.html:Percent rules covered 46.26865671641791
./wavefront/Generated-CSharp/cover.html:Percent rules covered 74.4186046511628
./webidl/Generated-CSharp/cover.html:Percent rules covered 53.097345132743364
./wkt/Generated-CSharp/cover.html:Percent rules covered 76.19047619047619
./wln/Generated-CSharp/cover.html:Percent rules covered 100
./wren/Generated-CSharp/cover.html:Percent rules covered 78.57142857142857
./xml/Generated-CSharp/cover.html:Percent rules covered 87.5
./xpath/xpath1/Generated-CSharp/cover.html:Percent rules covered 92.5925925925926
./xsd-regex/Generated-CSharp/cover.html:Percent rules covered 65
./xyz/Generated-CSharp/cover.html:Percent rules covered 100
./yara/Generated-CSharp/cover.html:Percent rules covered 100

It is arbitrary to say what is "low", "medium", or "high" quality testing, but here's what I suggest, including passing a build of the grammar if at least 50% of the rules are tested.

  • Low confidence that it tests full language described by grammar: < 50%
  • Medium confidence ...: < 90%
  • High confidence ...: >= 90%

archive.tar.gz

@kaby76 kaby76 changed the title New tool trcover shows many examples don't test much of the grammar! [build] Add grammar coverage tool. Jun 5, 2023
@kaby76 kaby76 mentioned this issue Jun 6, 2023
Merged
teverett pushed a commit that referenced this issue Jun 22, 2023
@kaby76
[build] Fix for #3365--Add grammar coverage tool. (#3511)
316eb6d 
* Fix for #3365

* Fix tab.

* Update to track coverage of a grammar.

* Add trcover, update versions.

* Update tools.

* Fix archive step.

* Merge in changes for coverage.

* Updates with local dotnet tools.

* Fix typo.

* Try again?

* Fix typo.

* Clean up.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[build] Fix for #3365--Add grammar coverage tool.
2 participants
@KvanTTT @kaby76