egglog 3.0.0

egglog is a language that combines the benefits of equality saturation and datalog. It can be used for analysis, optimization, and synthesis of programs. It is the successor to the popular rust library egg.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

use egglog::EGraph;
use std::fmt;

#[global_allocator]
static GLOBAL: mimalloc::MiMalloc = mimalloc::MiMalloc;

pub fn run_example(filename: &str, program: &str, proof_testing: bool) {
    let mut egraph = if proof_testing {
        EGraph::new_with_proofs().with_proof_testing()
    } else {
        EGraph::default()
    };
    egraph
        .parse_and_run_program(Some(filename.to_owned()), program)
        .unwrap();
    // test performance of serialization as well
    egraph.serialize(egglog::SerializeConfig::default());
    // We don't destruct the e-graph in CLI mode.
    std::mem::forget(egraph);
}

#[derive(Clone)]
pub struct BenchCase {
    pub name: String,
    pub filename: String,
    pub program: String,
    pub proof_testing: bool,
}

impl fmt::Display for BenchCase {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.write_str(&self.name)
    }
}

pub fn bench_cases(glob: &str) -> Vec<BenchCase> {
    let mut cases = Vec::new();

    // Add regular test cases
    let regular_cases = glob::glob(glob)
        .unwrap()
        .filter_map(Result::ok)
        .filter(|path| !path.to_string_lossy().contains("fail-typecheck"))
        .filter(|path| !path.to_string_lossy().contains("proofs"))
        .map(|path| {
            let filename = path.to_string_lossy().to_string();
            let program = std::fs::read_to_string(&filename).unwrap();
            // CodSpeed filters by substring, so the normal web-demo math shard
            // needs a name that does not also match proof_testing_math or
            // math-microbenchmark.
            let name = if path.ends_with("tests/web-demo/math.egg") {
                "math_normal".to_string()
            } else {
                path.file_stem().unwrap().to_string_lossy().to_string()
            };

            BenchCase {
                name,
                filename,
                program,
                proof_testing: false,
            }
        });
    cases.extend(regular_cases);

    // Add proof testing cases
    cases.extend(bench_cases_proof_testing(glob));

    cases
}

const PROOF_UNSUPPORTED_FILES: &[&str] = &[
    "math-microbenchmark.egg",
    "rectangle.egg",
    "subsume.egg",
    "subsume-relation.egg",
];

pub fn bench_cases_proof_testing(glob: &str) -> Vec<BenchCase> {
    glob::glob(glob)
        .unwrap()
        .filter_map(Result::ok)
        .filter(|path| !path.to_string_lossy().contains("fail-typecheck"))
        .filter(|path| proof_benchmark_supported(path))
        .filter(|path| !PROOF_UNSUPPORTED_FILES.iter().any(|f| path.ends_with(f)))
        .map(|path| {
            let filename = path.to_string_lossy().to_string();
            let program = std::fs::read_to_string(&filename).unwrap();
            let stem = path.file_stem().unwrap().to_string_lossy().to_string();
            let name = format!("proof_testing_{stem}");

            BenchCase {
                name,
                filename,
                program,
                proof_testing: true,
            }
        })
        .collect()
}

fn proof_benchmark_supported(path: &std::path::Path) -> bool {
    // `math.egg` runs in release proof-testing mode, which is what CodSpeed uses,
    // even though the conservative support probe rejects it.
    path.ends_with("tests/web-demo/math.egg") || egglog::file_supports_proofs(path)
}

pub fn bench_case(case: &BenchCase) {
    run_example(&case.filename, &case.program, case.proof_testing);
}