All Projects → ekzhang → Crepe

ekzhang / Crepe

Datalog compiler in Rust as a procedural macro

Programming Languages

rust
11053 projects

Projects that are alternatives of or similar to Crepe

Psalm Plugin Laravel
A Psalm plugin for Laravel
Stars: ✭ 139 (-20.57%)
Mutual labels:  static-analysis
I18n Extract
Manage localization with static analysis. 🔍
Stars: ✭ 152 (-13.14%)
Mutual labels:  static-analysis
Polymer Analyzer
Moved to Polymer/tools monorepo
Stars: ✭ 162 (-7.43%)
Mutual labels:  static-analysis
Crab Llvm
Static Analyzer for LLVM bitcode based on Abstract Interpretation
Stars: ✭ 143 (-18.29%)
Mutual labels:  static-analysis
Perl Critic
The leading static analyzer for Perl. Configurable, extensible, powerful.
Stars: ✭ 149 (-14.86%)
Mutual labels:  static-analysis
Cflint
Static code analysis for CFML (a linter)
Stars: ✭ 156 (-10.86%)
Mutual labels:  static-analysis
Mutant
Automated code reviews via mutation testing - semantic code coverage.
Stars: ✭ 1,794 (+925.14%)
Mutual labels:  static-analysis
Infer
A static analyzer for Java, C, C++, and Objective-C
Stars: ✭ 12,823 (+7227.43%)
Mutual labels:  static-analysis
Ngast
Parser for Angular projects.
Stars: ✭ 152 (-13.14%)
Mutual labels:  static-analysis
Phpstan Deprecation Rules
PHPStan rules for detecting usage of deprecated classes, methods, properties, constants and traits.
Stars: ✭ 160 (-8.57%)
Mutual labels:  static-analysis
Gradle Pitest Plugin
Gradle plugin for PIT Mutation Testing
Stars: ✭ 144 (-17.71%)
Mutual labels:  static-analysis
Ts Morph
TypeScript Compiler API wrapper for static analysis and programmatic code changes.
Stars: ✭ 2,384 (+1262.29%)
Mutual labels:  static-analysis
Phpmd
PHPMD is a spin-off project of PHP Depend and aims to be a PHP equivalent of the well known Java tool PMD. PHPMD can be seen as an user friendly frontend application for the raw metrics stream measured by PHP Depend.
Stars: ✭ 1,992 (+1038.29%)
Mutual labels:  static-analysis
Soot
Soot - A Java optimization framework
Stars: ✭ 2,049 (+1070.86%)
Mutual labels:  static-analysis
R2frida Wiki
This repo aims at providing practical examples on how to use r2frida
Stars: ✭ 168 (-4%)
Mutual labels:  static-analysis
Gcc Python Plugin
GCC plugin that embeds CPython inside the compiler
Stars: ✭ 140 (-20%)
Mutual labels:  static-analysis
Apkleaks
Scanning APK file for URIs, endpoints & secrets.
Stars: ✭ 2,707 (+1446.86%)
Mutual labels:  static-analysis
Pyt
A Static Analysis Tool for Detecting Security Vulnerabilities in Python Web Applications
Stars: ✭ 2,061 (+1077.71%)
Mutual labels:  static-analysis
Jpeek
Java Code Static Metrics (Cohesion, Coupling, etc.)
Stars: ✭ 168 (-4%)
Mutual labels:  static-analysis
Bytecode Viewer
A Java 8+ Jar & Android APK Reverse Engineering Suite (Decompiler, Editor, Debugger & More)
Stars: ✭ 12,606 (+7103.43%)
Mutual labels:  static-analysis

Crepe   Latest Version

Crepe is a library that allows you to write declarative logic programs in Rust, with a Datalog-like syntax. It provides a procedural macro that generates efficient, safe code and interoperates seamlessly with Rust programs.

Features

  • Semi-naive evaluation
  • Stratified negation
  • Automatic generation of indices for relations
  • Easily call Rust functions from within Datalog rules
  • Typesafe way to initialize @input relations
  • Very fast, compiled directly with the rest of your Rust code

Example

The program below computes the transitive closure of a directed graph. Note the use of the crepe! macro.

use crepe::crepe;

crepe! {
    @input
    struct Edge(i32, i32);

    @output
    struct Reachable(i32, i32);

    Reachable(x, y) <- Edge(x, y);
    Reachable(x, z) <- Edge(x, y), Reachable(y, z);
}

fn main() {
    let mut runtime = Crepe::new();
    runtime.extend(&[Edge(1, 2), Edge(2, 3), Edge(3, 4), Edge(2, 5)]);

    let (reachable,) = runtime.run();
    for Reachable(x, y) in reachable {
        println!("node {} can reach node {}", x, y);
    }
}

Output:

node 1 can reach node 2
node 1 can reach node 3
node 1 can reach node 4
node 1 can reach node 5
node 2 can reach node 3
node 2 can reach node 4
node 2 can reach node 5
node 3 can reach node 4

You can do much more with Crepe. The next example shows how you can use stratified negation, Rust expression syntax, and semi-naive evaluation to find all paths in a weighted graph with length at most MAX_PATH_LEN.

use crepe::crepe;

const MAX_PATH_LEN: u32 = 20;

crepe! {
    @input
    struct Edge(i32, i32, u32);

    @output
    struct Walk(i32, i32, u32);

    @output
    struct NoWalk(i32, i32);

    struct Node(i32);

    Node(x) <- Edge(x, _, _);
    Node(x) <- Edge(_, x, _);

    Walk(x, x, 0) <- Node(x);
    Walk(x, z, len1 + len2) <-
        Edge(x, y, len1),
        Walk(y, z, len2),
        (len1 + len2 <= MAX_PATH_LEN);

    NoWalk(x, y) <- Node(x), Node(y), !Walk(x, y, _);
}

fn main() {
    let n = 256;
    let mut edges = Vec::new();
    for i in 0..n {
        for j in 0..n {
            if rand::random::<f32>() < 0.02 {
                edges.push(Edge(i, j, 5));
            }
        }
    }

    let mut runtime = Crepe::new();
    runtime.extend(edges);
    let (walk, nowalk) = runtime.run();
    println!("Walk: {}", walk.len());
    println!("NoWalk: {}", nowalk.len());
}

Output:

Walk: 89203
NoWalk: 8207

Notes

From initial testing, the generated code is very fast. Variants of transitive closure for large graphs (~106 relations) run at comparable speed to compiled Souffle, and use a fraction of the compilation time.

For benchmarks, see the benches/ directory. The benchmarks can be run using cargo bench.

This macro generates a Crepe struct in the current module, as well as structs for all of the declared relations. This means that to integrate Crepe inside a larger program, you should put it in its own module with related code. See the documentation for more information.

Acknowledgements

This project was heavily inspired by Souffle and Formulog, which both use similar models of Datalog compilation for static analysis.

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].