Overview

Features

• Fast: treereduce uses a novel algorithm for parallelized reduction of tree-shaped data, based on ideas from recent research. It has been benchmarked against similar tools.

• Effective: treereduce produces small programs.

• Robust: treereduce is based on tree-sitter grammars, which are robust to parse errors. This means you can reduce syntactically invalid inputs, and each grammar doesn’t need to be 100% perfect to work for all programs.

• Easy to set up: treereduce reducers are distributed as static binaries.

• Multi-language: treereduce currently supports the following languages:

  • C

  • Java

  • JavaScript

  • Lua

  • Rust

  • Soufflé

Comparison to Other Tools

Test-case reduction tools form a spectrum: tools that are completely agnostic to the input format (e.g., Halfempty) are applicable in more situations, but will likely perform worse than highly-specialized tools (e.g., C-reduce). treereduce is somewhere in the middle: it is aware of the syntax of inputs, and works on a variety of different languages.

Perses and Picireny are also syntax-aware; they use ANTLR rather than tree- sitter grammars (making them unable to mutate malformed inputs). The goal of treereduce is to be faster and/or easier to use than these tools.

The following table lists several test-case reduction tools:

Tool	Input	Grammar	Parallel
comby-reducer	C-like	n/a
C-Reduce	C	n/a	✅
GTR	not sure	not sure	?
Halfempty	any	n/a	✅
Perses	[note]	ANTLR	?
Picireny	any	ANTLR	✅
treereduce	[note]	tree-sitter	✅

[note]: Perses supports the following languages:

• C

• Rust

• Java 8

• Go

• System Verilog

treereduce currently supports the languages listed above.