Datalog compiler in Rust as a procedural macro
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.
@inputrelations
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)
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 4You 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) () < 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: 8207Notes
From initial testing, the generated code is very fast. Variants of transitive closure for large graphs (~1000 nodes) run at comparable speed to compiled Souffle, and at a fraction of the compilation time.
benches/directory. The benchmarks can be run usingcargo bench.This macro generates a
Crepestruct 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.