AST-based randomized testing of Tact parser/pretty-printer

[anton-trunov]

Summary

We generate random Tact ASTs and test the following property:

• pretty-printed AST when parsed should provide the original AST.

One more property would be nice to test:

• the pretty-printer produces text with the minimum possible parentheses.

Some pointers for testing Tact expressions

Goal: implement automated tests to ensure the correctness of the Tact pretty-printer for expressions using the property-based randomized testing approach, also known as quickchecking.

The idea here is to randomly generate abstract syntax trees (AST) that represent Tact language constructions after parsing.

The fully blown implementation would start with generating abstract Tact AST modules, essentially generating a Tact file with multiple structures/messages, top-level functions, contracts and traits. But this is a pretty large task, so we just would like to do it for a small subset of Tact, namely expressions.

As a property based testing framework we could recommend using fast-check.

The approach here is as follows:

• generate a random AST for expression,
• pretty-print it, i.e. convert it to plain text representation,
• parse it, turning again into an AST,
• compare the originally generated AST and the parsed one: those must be the same, otherwise there is a bug (most likely in the pretty-printer),
• if the ASTs are the same, repeat the process.

More formally, for every generated Tact expression AST ast you need to check the following property:

parseExpression(prettyPrint(ast)) = ast

Note that you cannot use the builtin TS equality ===, because Tact ASTs contain the location information loc and AST identifiers id, so you will most likely need to implement your own equality comparison operation which would ignore that information.

Note that often times the generated counter-example is too large for a human to understand where the bug is, so if you implement a shrinker which tries to minimize the counter-example, that gives bonus points, but it's not strictly necessary for this test assignment.

Useful links

• The Tact AST for expressions:

  tact/src/grammar/ast.ts

  Line 380 in fbabf31

  export type AstExpression =

• The pretty-printer entry point:

  tact/src/prettyPrinter.ts

  Line 892 in fbabf31

  export const prettyPrint = (node: A.AstNode): string =>

• The Tact expression parser:

  tact/src/grammar/grammar.ts

  Line 1515 in fbabf31

  export function parseExpression(sourceCode: string): AstExpression {

• The description of the Tact repository: https://github.com/tact-lang/tact/blob/main/CONTRIBUTING.md