Repository files navigation

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

• 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

The program below computes the transitive closure of a directed graph. Notethe use of thecrepe! macro.

use crepe::crepe;crepe!{    @inputstructEdge(i32,i32);    @outputstructReachable(i32,i32);Reachable(x, y) <-Edge(x, y);Reachable(x, z) <-Edge(x, y),Reachable(y, z);}fnmain(){letmut runtime =Crepe::new();    runtime.extend([Edge(1,2),Edge(2,3),Edge(3,4),Edge(2,5)]);let(reachable,) = runtime.run();forReachable(x, y)in reachable{println!("node {} can reach node {}", x, y);}}

Output:

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

You can do much more with Crepe. The next example shows how you can usestratified negation, Rust expression syntax, and semi-naive evaluation to findall paths in a weighted graph with length at mostMAX_PATH_LEN.

use crepe::crepe;constMAX_PATH_LEN:u32 =20;crepe!{    @inputstructEdge(i32,i32,u32);    @outputstructWalk(i32,i32,u32);    @outputstructNoWalk(i32,i32);structNode(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, _);}fnmain(){let n =256;letmut edges =Vec::new();for iin0..n{for jin0..n{if rand::random::<f32>() <0.02{                edges.push(Edge(i, j,5));}}}letmut runtime =Crepe::new();    runtime.extend(edges);let(walk, nowalk) = runtime.run();println!("Walk: {}", walk.len());println!("NoWalk: {}", nowalk.len());}

Output:

Walk: 89203NoWalk: 8207

From initial testing, the generated code is very fast. Variants of transitiveclosure for large graphs (~10⁶ relations) run at comparable speed tocompiledSouffle, and use a fraction of thecompilation time.

For benchmarks, see thebenches/ directory.The benchmarks can be run usingcargo bench.

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

This project was heavily inspired bySouffleandFormulog, which both use similarmodels of Datalog compilation for static analysis.