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é

    • Swift

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.