Compilation is all about tree rewriting. In functional languages where all data is tree shaped, tree rewriting is facilitated by pattern matching, but data immutability leads to copying for each update. In object-oriented languages like Java or C++, a standard approach is to use the visitor pattern, which increases modularization but also adds indirection and introduces boilerplate code. In this paper, we introduce a middle ground in the form of Trieste – a novel tree-rewriting DSL implemented in C++. Trieste combines the power of C++ with the expressivity of pattern matching.

A Trieste toolchain consists of one or more sequences of rewrite passes. Each pass rewrites an abstract syntax tree (AST) in place using subtree pattern matching, where the result is dynamically checked for well-formedness. Sequences of Trieste passes can be used to read a file to produce an AST, convert from one AST to another, or write an AST to disk. The well-formedness specification, in addition to checking the shape of trees, can be used for scoped name binding as well as generating random well-formed trees for fuzz testing.

Trieste has been used to build fully compliant parsers for YAML and JSON, a transpiler from YAML to JSON, and a compiler and interpreter for the policy language Rego.