Generate Soufflé Datalog types, relations, and facts that represent ASTs from a variety of programming languages.

Overview

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:

  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.

Unfortunately, the Java-related binaries are not yet available on crates.io.

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":

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:

  • Create new directories treeedb-<LANG> and treeedbgen-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
You might also like...
Turbine is a toy CLI app for converting Rails schema declarations into equivalent type declarations in other languages.

Turbine Turbine is a toy CLI app for converting Rails schema declarations into equivalent type declarations in other languages. It’s described as a to

🎄 Advent of Code written in various languages. (2015-2022)

🎄 Advent of Code This repository contains my solutions to the Advent of Code puzzles. Every year, I will try to solve the puzzles in a different lang

Trying to solve Advent of Code 2022 in 25 different languages (1 day = 1 language)

Advent of Code 2022: 15/25 langs I’ll try to solve this Advent of Code using different language for each day. Any programs needed to run the code will

An AST viewer UI for languages with an AST.

AST Viewer UI This project was inspired by "Zoom Out": The missing feature of IDEs. I want to create a GUI with text fields, boxes, arrows, etc. and g

Advent of Code, this year I will attempt the 25 different languages challenge

Advent of Code 2022 As this is my third year doing Advent of Code, this time I will try the 25 Different Languages Challenge, which is solving the pro

MidenIR for compiling to Miden Assembly from higher-level languages

Miden IR This repository provides a compiler for the Miden VM, specifically for Miden Assembly. It does this by lowering from a higher-level intermedi

Demo app duplicated in 5 languages (Go/JavaScript/Python/Ruby/Rust) showing how to go from source code to container image using melange+apko

hello-melange-apko 💫 This repo contains an example app duplicated across 5 languages showing how to: Package source code into APKs using melange Buil

Devices can use this SDK to connect to the Spotflow IoT Platform. Supported languages: Rust, Python, C.

Device SDK for Spotflow IoT Platform Languages | Features | Architecture | Building and Testing | License Devices can use this SDK to connect to the S

An Interpreter for Brainfuck programming language implemented in the Rust programming language with zero dependencies.

Brainfuck Hello, Visitor! Hey there, welcome to my project showcase website! It's great to have you here. I hope you're ready to check out some awesom

Comments
  • Publish v0.1.0 to crates.io

    Publish v0.1.0 to crates.io

    Only release candidates are available at the moment becase I kept hitting the rate limit, which appears to only allow 10 crates to be uploaded at once: https://github.com/rust-lang/crates.io/pull/1596. I think I'll modify scripts/publish.sh to just wait for 30s-1min in between each upload. I may also email to ask for the ability to publish more crates at once.

    opened by langston-barrett 0
  • gen/souffle: Accessors for more node fields

    gen/souffle: Accessors for more node fields

    There's an inline node_text relation that retrieves a node's text based on its ID. There should be one such relation for each field in the node table.

    opened by langston-barrett 0
  • Attach source file names to nodes

    Attach source file names to nodes

    If you feed treeedb-<LANG> multiple source files, all of their syntax nodes will be mixed together in the output fact files. They should have source file names attached so that they can be differentiated.

    opened by langston-barrett 0
  • gen/souffle: Configurable field suffix

    gen/souffle: Configurable field suffix

    To avoid name collisions, the Souffle generator suffixes field relations with _f. This can and should be configurable - and it should be left off in grammars that don't have such collisions.

    opened by langston-barrett 0
Owner
Langston Barrett
Researcher with experience in functional programming, formal methods, programming languages, and security.
Langston Barrett
Programming language made by me to learn other people how to make programming languages :3

Spectra programming language Programming language made for my tutorial videos (my youtube channel): Syntax Declaring a variable: var a = 3; Function

Adi Salimgereyev 3 Jul 25, 2023
A general-purpose, transactional, relational database that uses Datalog and focuses on graph data and algorithms

cozo A general-purpose, transactional, relational database that uses Datalog for query and focuses on graph data and algorithms. Features Relational d

null 1.9k Jan 9, 2023
tmplt is a command-line interface tool that allows you to quickly and easily set up project templates for various programming languages and frameworks

tmplt A User Friendly CLI Tool For Creating New Projects With Templates About tmplt is a command-line tool that lets users quickly create new projects

Humble Penguin 35 Apr 8, 2023
A CLI for analyzing the programming languages and how much code written in a project.

projlyzer A CLI for analyzing the programming languages and how much code written in a project. New features are on the way... Example Screenshot Buil

null 10 Apr 10, 2022
Cloc - cloc counts blank lines, comment lines, and physical lines of source code in many programming languages.

cloc Count Lines of Code cloc counts blank lines, comment lines, and physical lines of source code in many programming languages. Latest release: v1.9

null 15.3k Jan 8, 2023
⚙️ A curated list of static analysis (SAST) tools for all programming languages, config files, build tools, and more.

This repository lists static analysis tools for all programming languages, build tools, config files and more. The official website, analysis-tools.de

Analysis Tools 10.7k Jan 2, 2023
Run code from many programming languages!

Langbot Creating an image Install podman Build an image: podman build -t langbot . Running a language Run podman run --rm -i langbot ./scripts/run.sh

Martin Dørum 14 Jun 9, 2022
Growing languages with interpreters and staging.

language-greenhouse This is a small collection of interpreters/compilers focused on the technique of compilation by staging. For more information, ple

McCoy R. Becker 3 Jun 5, 2022
Striving to create a great Application with full functions of learning languages by ChatGPT, TTS, STT and other awesome AI models

Striving to create a great Application with full functions of learning languages by ChatGPT, TTS, STT and other awesome AI models, supports talking, speaking assessment, memorizing words with contexts, Listening test, so on.

null 155 Apr 20, 2023
Code implementation of DDIA, primarily using Rust and Go languages.

Let's implement DDIA in rust and golang (with some Java and Cpp). This repository contains code implementations for 'Designing Data-Intensive Applicat

Arthur.Zhang 4 Apr 21, 2023