Macro crepe::crepe

crepe!() { /* proc-macro */ }

The main macro, which lets you write a Datalog program declaratively.

Example

A program to calculate transitive closure might be written as:

mod datalog {
    use crepe::crepe;

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

        @output
        struct Tc(i32, i32);

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

    pub fn run(edges: &[(i32, i32)]) -> Vec<(i32, i32)> {
        let mut runtime = Crepe::new();
        runtime.extend(edges.iter().map(|&(a, b)| Edge(a, b)));
        let (tc,) = runtime.run();
        tc.into_iter().map(|Tc(a, b)| (a, b)).collect()
    }
}

Generated Code

Each struct in the program is turned into a Datalog relation, while each line of the form goal <- clause1, clause2, ...; or fact; defines a logic programming rule that is used to derive new relations.

In addition to the relation structs, the macro also defines a Crepe struct representing the runtime. This is the primary way that you interact with Crepe. It provides a couple methods and traits (here Rel is a placeholder for the name of your relation):

• Crepe::new(): construct a new runtime
• Implements std::iter::Extend<Rel> for each @input struct.
  • Crepe::extend(&mut self, iter: impl IntoIterator<Item = Rel>)
• Implements std::iter::Extend<&'a Rel> for each @input struct.
  • Crepe::extend(&mut self, iter: impl IntoIterator<Item = &'a Rel>)
• Crepe::run(self): evaluates the Datalog program on the given inputs, consuming the runtime object, and returns a tuple of HashSet<Rel>s containing the final derived @output structs.

In order for the engine to work, all relations must be tuple structs, and they automatically derive the Eq, PartialEq, Hash, Copy, and Clone traits. This is necessary in order to create efficient indices that are used in Datalog evaluation. If you want to use Crepe with types that do not implement Copy, consider passing references instead.

Datalog Syntax Extensions

This library supports arbitrary Rust expression syntax within rules for constructing new relations, as well as Boolean expressions that are evaluated directly as clauses in rules. Basically, this gives you seamless Rust interoperability within your Datalog programs.

For instance, here is a program that calculates the first 25 Fibonacci numbers using arithmetic functors:

crepe! {
    @output
    struct Fib(u32, u32);

    Fib(0, 0) <- (true);
    Fib(1, 1); // shorthand for `Fib(1, 1) <- (true);`

    Fib(n + 2, x + y) <- Fib(n, x), Fib(n + 1, y), (n + 2 <= 25);
}

Note that all Boolean conditions within the clauses of rules are evaluated in-place, and they must be surrounded by parentheses.

We also support let-bindings in rules, including bindings that destructure their arguments conditionally. See tests/test_destructure.rs for an example of this.

Evaluation Mode

All generated code uses semi-naive evaluation (see Chapter 3 of Datalog and Recursive Query Processing), and it is split into multiple strata to enable stratified negation. For example, we can extend the code above to also compute the complement of transitive closure in a graph:

mod datalog {
    use crepe::crepe;

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

        @output
        struct Tc(i32, i32);

        struct Node(i32);

        @output
        struct NotTc(i32, i32);

        Tc(x, y) <- Edge(x, y);
        Tc(x, z) <- Edge(x, y), Tc(y, z);

        Node(x) <- Edge(x, _);
        Node(x) <- Edge(_, x);
        NotTc(x, y) <- Node(x), Node(y), !Tc(x, y);
    }

    pub fn run(edges: &[(i32, i32)]) -> (Vec<(i32, i32)>, Vec<(i32, i32)>) {
        let mut runtime = Crepe::new();
        runtime.extend(edges.iter().map(|&(a, b)| Edge(a, b)));
        let (tc, not_tc) = runtime.run();
        (
            tc.into_iter().map(|Tc(a, b)| (a, b)).collect(),
            not_tc.into_iter().map(|NotTc(a, b)| (a, b)).collect(),
        )
    }
}

Hygiene

In addition to the relation structs, this macro generates implementations of a private struct named Crepe for the runtime. Therefore, it is recommended to place each Datalog program within its own module, to prevent name collisions.