Skip to content

Latest commit

 

History

History
63 lines (51 loc) · 2.59 KB

overview.md

File metadata and controls

63 lines (51 loc) · 2.59 KB

Overview

Features

  • Fast: treereduce uses a {doc}novel algorithm <design> for parallelized reduction of tree-shaped data, based on ideas from {ref}recent research <bib>. It has been {doc}benchmarked <benchmarks> against similar tools.

  • Effective: treereduce produces {doc}small programs <benchmarks>.

  • 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.