treeedb

treeedb makes it easier to start writing a source-level program analysis in Soufflé Datalog. First, treeedb generates Soufflé types and relations that represent a program's AST. Then, treeedb parses source code and emits facts that populate those relations.

treeedb currently supports analysis of these languages:

treeedb's parsers and ASTs are based on tree-sitter grammars, and it's very easy to add support for any language with a tree-sitter grammar.

The name treeedb is a portmanteau of "tree-sitter" with "EDB", where EDB stands for "extensional database" and refers to the set of facts in a Datalog program.

Installation

You'll need two artifacts for each programming language you want to analyze:

  1. A Soufflé file with the types and relations defining the AST
  2. The executable that parses that language and emits facts

For instance, for Java these are called treeedb-java.dl and treeedb-java, respectively.

To actually analyze some code, you'll also need to install Soufflé.

Install From a Release

Navigate to the most recent release on the releases page and download the artifacts related to the language you want to analyze. The pre-built executables are statically linked, but are currently only available for Linux.

Build From crates.io

You can build a released version from crates.io. You'll need the Rust compiler and the Cargo build tool. rustup makes it very easy to obtain these. Then, to install the tools for the language <LANG>, run:

cargo install treeedb-<LANG> treeedbgen-souffle-<LANG>

This will install binaries to ~/.cargo/bin. To generate the Datalog file, run the treeedbgen-souffle-<LANG> binary.

Build From Source

To build from source, you'll need the Rust compiler and the Cargo build tool. rustup makes it very easy to obtain these.

Then, get the source:

bash git clone https://github.com/langston-barrett/treeedb cd treeedb

Finally, build everything:

bash cargo build --release

You can find the treeedb-<LANG> binaries in target/release. To generate the Datalog file, run the corresponding treeedbgen-souffle-<LANG> binary.

Example: Analyzing Java Code

To follow along with this example, follow the installation instructions for Java. Then, create a Java file named Main.java:

java class Main { public static void main(String[] args) { int x = 2 + 2; } }

(The files shown in this section are also available in examples/java/.)

Create a Datalog file named const-binop.dl that includes treeedb-java.dl and has a rule to find constant-valued binary expressions:

```souffle

include "treeedb-java.dl"

.decl const_binop(expr: JavaBinaryExpression)

constbinop(expr) :- javabinaryexpression(expr), javabinaryexpressionleftf(expr, l), javabinaryexpressionrightf(expr, r), javadecimalintegerliteral(l), javadecimalinteger_literal(r).

.decl showconstbinop(text: JavaNodeText)

showconstbinop(text) :- constbinop(expr), javanode_text(expr, text).

.output constbinop(IO=stdout) .output showconst_binop(IO=stdout) ```

Generate the input files (node.csv and field.csv):

bash treeedb-java Main.java

Finally, run the analysis with Soufflé:

bash souffle const-binop.dl

You'll see something like this:

```

const_binop

94001952741472

showconstbinop

2 + 2

```

Digging Deeper

To see what type and relation names are available, look at treeedb-<LANGUAGE>.dl. If it's not evident which part of the language a given type or relation corresponds to, take a look at the tree-sitter grammar (e.g. grammar.js in the tree-sitter-java repo for Java).

Motivation and Comparison to Other Tools

Before writing a program analysis in Datalog, you need to figure out (1) how to represent the program as relations, and (2) how to ingest programs into that representation. State-of-the-art Datalog projects do all this "by hand":

Writing these representations and ingestion tools takes up valuable time and distracts from the work of writing analyses. treeedb aims to automate it, fitting in the same niche as these tools.

Repository Structure

Contributing

Thank you for your interest in treeedb! We welcome and appreciate all kinds of contributions. Please feel free to file and issue or open a pull request.

Adding a Language

As explained in Installation, there are two tools involved in supporting analysis of each programming language: One to generate Soufflé types and relations (e.g., treeedbgen-souffle-c), and another to parse the language being analyzed and emit facts (e.g., treeedb-c).

To add a new language:

See PR #9 for a complete example.

The script ./scripts/add-language.sh automates a few of these steps - but it is not necessarily a turn-key solution. Usage example:

bash bash scripts/add-language.sh python Python