1 unstable release
0.1.0-rc.5 | Oct 29, 2022 |
---|
#901 in Programming languages
34KB
293 lines
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:
- C
- C#
- Java
- JavaScript
- Rust
- Soufflé
- Swift
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:
- A Soufflé file with the types and relations defining the AST
- 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:
git clone https://github.com/langston-barrett/treeedb
cd treeedb
Finally, build everything:
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
:
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:
#include "treeedb-java.dl"
.decl const_binop(expr: JavaBinaryExpression)
const_binop(expr) :-
java_binary_expression(expr),
java_binary_expression_left_f(expr, l),
java_binary_expression_right_f(expr, r),
java_decimal_integer_literal(l),
java_decimal_integer_literal(r).
.decl show_const_binop(text: JavaNodeText)
show_const_binop(text) :-
const_binop(expr),
java_node_text(expr, text).
.output const_binop(IO=stdout)
.output show_const_binop(IO=stdout)
Generate the input files (node.csv
and field.csv
):
treeedb-java Main.java
Finally, run the analysis with Soufflé:
souffle const-binop.dl
You'll see something like this:
---------------
const_binop
===============
94001952741472
===============
---------------
show_const_binop
===============
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":
- cclyzer++ has a "schema" directory (1) and the FactGenerator (2).
- Doop has a big imports.dl file (1) and a variety of generators (2).
- ddisasm has the gtirb-decoder (2).
- securify has
analysis-input.dl
(1).
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
treeedb
: Generate Datalog facts from tree-sitter parse treestreeedb-c
: Generate Datalog facts from C source codetreeedb-csharp
: Generate Datalog facts from C# source codetreeedbgen
: Parse node-types.json from a tree-sitter grammartreeedbgen-souffle
: Generate Soufflé types and relations from tree-sitter grammarstreeedbgen-souffle-c
: Generate Soufflé types and relations from the C tree-sitter grammartreeedbgen-souffle-csharp
: Generate Soufflé types and relations from the C# tree-sitter grammartreeedbgen-souffle-java
: Generate Soufflé types and relations from the Java tree-sitter grammartreeedbgen-souffle-javascript
: Generate Soufflé types and relations from the JavaScript tree-sitter grammartreeedbgen-souffle-rust
: Generate Soufflé types and relations from the Rust tree-sitter grammartreeedbgen-souffle-souffle
: Generate Soufflé types and relations from the Soufflé tree-sitter grammartreeedbgen-souffle-swift
: Generate Soufflé types and relations from the Swift tree-sitter grammartreeedb-java
: Generate Datalog facts from Java source codetreeedb-javascript
: Generate Datalog facts from JavaScript source codetreeedb-rust
: Generate Datalog facts from Rust source codetreeedb-souffle
: Generate Datalog facts from Soufflé source codetreeedb-swift
: Generate Datalog facts from Swift source code
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:
- Create new directories
treeedb-<LANG>
andtreeedbgen-souffle-<LANG>
with the same structure as an existing one (it might be easiest to just recursively copy existing ones). - Add the new directories to the top-level
Cargo.toml
. - Add the language to
.github/workflows/release.yml
by copying and modifying existing lines for other languages.
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 scripts/add-language.sh python Python
Dependencies
~5–7MB
~142K SLoC