egglog-core-relations 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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

use crate::numeric_id::NumericId;

use crate::{
    DisplacedTableWithProvenance, ProofStep,
    common::Value,
    table_spec::{ColumnId, Constraint, Table},
    uf::ProofReason,
};

use super::DisplacedTable;

fn v(x: usize) -> Value {
    Value::from_usize(x)
}

#[test]
fn displaced() {
    empty_execution_state!(e);
    let mut d = DisplacedTable::default();
    {
        let mut buf = d.new_buffer();
        buf.stage_insert(&[v(0), v(1), v(0)]);
        buf.stage_insert(&[v(2), v(3), v(0)]);
    }
    d.merge(&mut e);
    let all = d.all();
    let mut updates = Vec::new();
    d.scan_generic(all.as_ref(), |_, row| {
        assert_eq!(row[2], v(0));
        updates.push((row[0], row[1]))
    });
    assert_eq!(updates.len(), 2);
    assert_ne!(updates[0], updates[1]);
    let eq_fst = d.refine(
        all,
        &[Constraint::EqConst {
            col: ColumnId::new(0),
            val: updates[0].0,
        }],
    );
    let mut rows = Vec::new();
    d.scan_generic(eq_fst.as_ref(), |_, row| {
        assert_eq!(row.len(), 3);
        rows.push((row[0], row[1], row[2]))
    });
    assert_eq!(rows, vec![(updates[0].0, updates[0].1, v(0))]);

    d.new_buffer().stage_insert(&[v(1), v(3), v(1)]);
    d.merge(&mut e);

    let all = d.all();
    let mut updates_2 = Vec::new();
    d.scan_generic(all.as_ref(), |_, row| updates_2.push((row[0], row[1])));
    assert!(updates_2.windows(2).all(|x| x[0].1 == x[1].1));
}

#[test]
fn displaced_proof() {
    empty_execution_state!(e);
    let p1 = Value::new(1000);
    let p2 = p1.inc();
    let p3 = p2.inc();
    let mut d = DisplacedTableWithProvenance::default();
    d.new_buffer().stage_insert(&[v(0), v(1), v(0), p1]);
    d.new_buffer().stage_insert(&[v(2), v(3), v(0), p2]);
    d.merge(&mut e);
    let all = d.all();
    let mut updates = Vec::new();
    d.scan_generic(all.as_ref(), |_, row| {
        assert_eq!(row[2], v(0));
        updates.push((row[0], row[1]))
    });
    assert_eq!(updates.len(), 2);
    assert_ne!(updates[0], updates[1]);

    {
        let mut buf = d.new_buffer();
        buf.stage_insert(&[v(0), v(1), v(0), p1]);
        buf.stage_insert(&[v(2), v(0), v(0), p3]);
    }

    d.merge(&mut e);

    let proof = d.get_proof(v(0), v(3)).unwrap();
    assert_eq!(
        proof,
        vec![
            ProofStep {
                lhs: v(0),
                rhs: v(2),
                reason: ProofReason::Backward(p3),
            },
            ProofStep {
                lhs: v(2),
                rhs: v(3),
                reason: ProofReason::Forward(p2),
            },
        ]
    )
}