egglog 2.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

use super::*;

/// Signed 64-bit integers supporting these primitives:
/// - Arithmetic: `+`, `-`, `*`, `/`, `%`
/// - Bitwise: `&`, `|`, `^`, `<<`, `>>`, `not-i64`
/// - Fallible comparisons: `<`, `>`, `<=`, `>=`
/// - Boolean comparisons: `bool-=`, `bool-<`, `bool->`, `bool-<=`, `bool->=`
/// - Other: `min`, `max`, `to-f64`, `to-string`, `log2`
///
/// Note: fallible comparisons are used at the top-level of a query.
/// For example, this rule will only match if `a` is less than `b`.
/// ```text
/// (rule (... (< a b)) (...))
/// ```
/// On the other hand, boolean comparisons will always match, and so
/// make sense to use inside expressions.
#[derive(Debug)]
pub struct I64Sort;

impl BaseSort for I64Sort {
    type Base = i64;

    fn name(&self) -> &str {
        "i64"
    }

    #[rustfmt::skip]
    fn register_primitives(&self, eg: &mut EGraph) {
        add_primitive!(eg, "+" = |a: i64, b: i64| -?> i64 { a.checked_add(b) });
        add_primitive!(eg, "-" = |a: i64, b: i64| -?> i64 { a.checked_sub(b) });
        add_primitive!(eg, "*" = |a: i64, b: i64| -?> i64 { a.checked_mul(b) });
        add_primitive!(eg, "/" = |a: i64, b: i64| -?> i64 { a.checked_div(b) });
        add_primitive!(eg, "%" = |a: i64, b: i64| -?> i64 { a.checked_rem(b) });

        add_primitive!(eg, "&" = |a: i64, b: i64| -> i64 { a & b });
        add_primitive!(eg, "|" = |a: i64, b: i64| -> i64 { a | b });
        add_primitive!(eg, "^" = |a: i64, b: i64| -> i64 { a ^ b });
        add_primitive!(eg, "<<" = |a: i64, b: i64| -?> i64 { b.try_into().ok().and_then(|b| a.checked_shl(b)) });
        add_primitive!(eg, ">>" = |a: i64, b: i64| -?> i64 { b.try_into().ok().and_then(|b| a.checked_shr(b)) });
        add_primitive!(eg, "not-i64" = |a: i64| -> i64 { !a });

        add_primitive!(eg, "log2" = |a: i64| -> i64 { a.ilog2() as i64 });

        add_primitive!(eg, "<" = |a: i64, b: i64| -?> () { (a < b).then_some(()) });
        add_primitive!(eg, ">" = |a: i64, b: i64| -?> () { (a > b).then_some(()) });
        add_primitive!(eg, "<=" = |a: i64, b: i64| -?> () { (a <= b).then_some(()) });
        add_primitive!(eg, ">=" = |a: i64, b: i64| -?> () { (a >= b).then_some(()) });

        add_primitive!(eg, "bool-=" = |a: i64, b: i64| -> bool { a == b });
        add_primitive!(eg, "bool-<" = |a: i64, b: i64| -> bool { a < b });
        add_primitive!(eg, "bool->" = |a: i64, b: i64| -> bool { a > b });
        add_primitive!(eg, "bool-<=" = |a: i64, b: i64| -> bool { a <= b });
        add_primitive!(eg, "bool->=" = |a: i64, b: i64| -> bool { a >= b });

        add_primitive!(eg, "min" = |a: i64, b: i64| -> i64 { a.min(b) });
        add_primitive!(eg, "max" = |a: i64, b: i64| -> i64 { a.max(b) });

        add_primitive!(eg, "to-string" = |a: i64| -> S { S::new(a.to_string()) });

        // Must be in the i64 sort register function because
        // the string sort is registered before the i64 sort.
        add_primitive!(eg, "count-matches" = |a: S, b: S| -> i64 {
            a.as_str().matches(b.as_str()).count() as i64
        });
    }

    fn reconstruct_termdag(
        &self,
        base_values: &BaseValues,
        value: Value,
        termdag: &mut TermDag,
    ) -> TermId {
        let i = base_values.unwrap::<i64>(value);

        termdag.lit(Literal::Int(i))
    }
}