Skip to content

Convert rvgen to Lark

Nam Cao linux-trace-kernel lkml 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest13 patches 4 repliesIn review
  2. v313 patches 12 repliesSuperseded
  3. v213 patches 9 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v113 patches22 repliesSuperseded

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/13verification/rvgen: Switch LTL parser to Larktools/verification/rvgen/__main__.py tools/verification/rvgen/rvgen/ltl2ba.py+82 -1250 replies
2/13verification/rvgen: Introduce a parse tree for automata using Larktools/verification/rvgen/rvgen/automata.py+186 -00 replies
3/13verification/rvgen: Implement state and transition parser based on Larktools/verification/rvgen/rvgen/automata.py+216 -00 replies
4/13verification/rvgen: Convert __fill_verify_invariants_func() to Larktools/verification/rvgen/rvgen/dot2k.py+21 -110 replies
5/13verification/rvgen: Convert __fill_setup_invariants_func() to Larktools/verification/rvgen/rvgen/dot2k.py+39 -90 replies
6/13verification/rvgen: Convert __fill_verify_guards_func() to Larktools/verification/rvgen/rvgen/dot2k.py+30 -80 replies
7/13Simplify hybrid automata monitors's clock variablesinclude/rv/ha_monitor.h kernel/trace/rv/monitors/nomiss/nomiss.c kernel/trace/rv/monitors/stall/stall.c+19 -650 replies
8/13verification/rvgen: Simplify the generation for clock variablestools/verification/rvgen/rvgen/dot2k.py+3 -930 replies
9/13verification/rvgen: Delete __parse_constraint()tools/verification/rvgen/rvgen/dot2k.py+4 -634 replies
10/13verification/rvgen: Switch __get_event_variables() to Larktools/verification/rvgen/rvgen/automata.py+19 -590 replies
11/13verification/rvgen: Switch __create_matrix() to Larktools/verification/rvgen/rvgen/automata.py tools/verification/rvgen/rvgen/dot2k.py+13 -360 replies
12/13verification/rvgen: Remove the old state variablestools/verification/rvgen/rvgen/automata.py tools/verification/rvgen/rvgen/dot2c.py tools/verification/rvgen/rvgen/dot2k.py+13 -140 replies
13/13verification/rvgen: Remove dead codetools/verification/rvgen/rvgen/automata.py tools/verification/rvgen/rvgen/dot2k.py+1 -1850 replies

Reviews trailers per patch

All 13 patches have a Reviewed-by or Acked-by.

PatchGabriele Monaco
1/13R-b
2/13R-b
3/13R-b
4/13R-b
5/13R-b
6/13R-b
7/13R-b
8/13R-b
9/13R-b
10/13R-b
11/13R-b
12/13R-b
13/13R-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH v4 00/13] rv: Convert rvgen to Lark

This series converts the linear temporal logic parser and the automata parser into using Lark.

The LTL parser has been using ply - a parsing library. However, ply was recently announced to be abandoned. Furthermore, ply does not offer the features that lark has.

On the other hand, the automata parser is mostly raw text processing which is quite fragile. For instance, by slightly deform wwnr.dot (but does not make it an invalid dot file):

digraph state_automaton {
	{node [shape = plaintext, style=invis, label=""] "__init_not_running"};
	{node [shape = ellipse]
	      "not_running"};
	{node [shape=plaintext] "not_running"};
	{node [shape = plaintext] "running"};
	"__init_not_running"
		-> "not_running";
	"not_running" [label = "not_running", color = green3];
	"not_running" ->
		      "not_running" [ label = "wakeup" ];
	"not_running" -> "running" [ label = "switch_in" ];
	"running" [label = "running"];
	"running" -> "not_running" [ label = "switch_out" ];
}

the parser would be broken. Furthermore, the code is a bit hard to follow with raw text being stored in lots of variables and sometimes it is hard to figure out what sort of text is stored in the variables while reading the code.

This motivates me to convert the automata parser as well. The plan is:

- Introduce Lark and prepare the parsed states, transitions and constraints

- Convert the parser piece by piece to the parsed results from Lark

- Delete the old code

I struggled with converting __find_inv_conflicts(). So I decided to remove the dual clock representation in the HA monitors, which allows me to delete __find_inv_conflicts() entirely. This makes the code simpler overall.

After the series, the generated HA monitors are mostly unchanged, except:

- Clock representation conversion is gone and ha_check_invariant_[ns|jiffy]() takes a new argument

- The ordering in ha_verify_guards() is changed, but still equivalent. This is because it is now sorted lexically.

The generated LTL monitors are sadly significantly different, but proved to be equivalent with runtime testing. Further work will make LTL monitor generation more consistent.

v4..v3: https://lore.kernel.org/linux-trace-kernel/[email protected]/
- fix missing operator "!=" and unit "j" in the grammar
- fix generation error when time values have units

v3..v2: https://lore.kernel.org/lkml/[email protected]/
- remove some redundant imports
- fix build failure due to passing wrong parameters to ha_invariant_passed_jiffy()

v2..v1: https://lore.kernel.org/lkml/[email protected]/
- address human's reviews and sashiko's reviews
- handle lark's exception, yielding a much better error message

Nam Cao (13):
verification/rvgen: Switch LTL parser to Lark verification/rvgen: Introduce a parse tree for automata using Lark verification/rvgen: Implement state and transition parser based on
Lark
verification/rvgen: Convert __fill_verify_invariants_func() to Lark verification/rvgen: Convert __fill_setup_invariants_func() to Lark verification/rvgen: Convert __fill_verify_guards_func() to Lark
rv: Simplify hybrid automata monitors's clock variables verification/rvgen: Simplify the generation for clock variables verification/rvgen: Delete __parse_constraint() verification/rvgen: Switch __get_event_variables() to Lark verification/rvgen: Switch __create_matrix() to Lark verification/rvgen: Remove the old state variables verification/rvgen: Remove dead code

 include/rv/ha_monitor.h                    |  64 +-
 kernel/trace/rv/monitors/nomiss/nomiss.c   |  18 +-
 kernel/trace/rv/monitors/stall/stall.c     |   2 +-
 tools/verification/rvgen/__main__.py       |   5 +-
 tools/verification/rvgen/rvgen/automata.py | 643 +++++++++++++--------
 tools/verification/rvgen/rvgen/dot2c.py    |  10 +-
 tools/verification/rvgen/rvgen/dot2k.py    | 294 +++-------
 tools/verification/rvgen/rvgen/ltl2ba.py   | 202 +++----
 8 files changed, 608 insertions(+), 630 deletions(-)
Signature · 1 line
2.47.3