Crepe

Crepe是一个库，允许您在Rust中使用类似Datalog的语法编写声明式逻辑程序。它提供了一个过程宏，可以生成高效、安全的代码，并且可以与Rust程序无缝交互。

功能

• 半天真评估
• 分层否定
• 自动生成关系索引
• 在Datalog规则中轻松调用Rust函数
• 安全初始化@input关系的方法
• 非常快速，直接与您的Rust代码一起编译

示例

以下程序计算有向图的传递闭包。注意使用crepe!宏。

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);
    }
}

输出

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

您可以使用Crepe做更多的事情。下一个示例展示了如何使用分层否定、Rust表达式语法和半天真评估来找到长度不超过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());
}

输出

Walk: 89203
NoWalk: 8207

注意

根据初步测试，生成的代码非常快。大型图（约10⁶个关系）的传递闭包变体与编译的Souffle具有可比的速度，并且编译时间占用更少。

有关基准测试，请参阅benches/目录。可以使用cargo bench运行基准测试。

此宏在当前模块中生成一个Crepe结构体以及所有声明的关系的结构体。这意味着要将Crepe集成到更大的程序中，您应该将其放在自己的模块中，并包含相关代码。请参阅文档以获取更多信息。

致谢

该项目深受Souffle和Formulog的启发，这两个项目都使用类似的Datalog编译模型进行静态分析。