eqlog 0.9.0

Datalog with equality
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

use itertools::Itertools;
use std::collections::BTreeSet;

use super::ast::*;

#[derive(Copy, Clone, PartialEq, Eq)]
struct IfStmtGoodness {
    is_equal: bool,
    age: QueryAge,
    new_variables: usize,
    restrained_variables: usize,
}

impl Default for IfStmtGoodness {
    fn default() -> Self {
        IfStmtGoodness {
            is_equal: false,
            age: QueryAge::All,
            new_variables: 0,
            restrained_variables: 0,
        }
    }
}

fn cmp_age_goodness(lhs: QueryAge, rhs: QueryAge) -> std::cmp::Ordering {
    let lhs_is_new = matches!(lhs, QueryAge::New);
    let rhs_is_new = matches!(rhs, QueryAge::New);
    lhs_is_new.cmp(&rhs_is_new)
}

impl Ord for IfStmtGoodness {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // True is better than false.
        let is_equal = self.is_equal.cmp(&other.is_equal);
        // True is better than false.
        let age_goodness = cmp_age_goodness(self.age, other.age);
        // Smaller is better than greater.
        let new_variables = self.new_variables.cmp(&other.new_variables).reverse();
        // Greater is better than smaller.
        let restrained_variables = self.restrained_variables.cmp(&other.restrained_variables);

        is_equal
            .then(age_goodness)
            .then(new_variables)
            .then(restrained_variables)
    }
}

impl PartialOrd for IfStmtGoodness {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

#[test]
fn equal_is_better() {
    let is_equal = IfStmtGoodness {
        is_equal: true,
        new_variables: 2,
        ..IfStmtGoodness::default()
    };
    let is_not_equal = IfStmtGoodness {
        is_equal: false,
        ..IfStmtGoodness::default()
    };
    assert!(is_equal > is_not_equal);
}

#[test]
fn only_dirty_is_better() {
    let only_dirty = IfStmtGoodness {
        age: QueryAge::New,
        new_variables: 2,
        ..IfStmtGoodness::default()
    };
    let arbitrary = IfStmtGoodness {
        age: QueryAge::All,
        ..IfStmtGoodness::default()
    };
    assert!(only_dirty > arbitrary);
}

#[test]
fn less_new_variables_is_better() {
    let few_vars = IfStmtGoodness {
        new_variables: 2,
        ..IfStmtGoodness::default()
    };
    let many_vars = IfStmtGoodness {
        new_variables: 3,
        ..IfStmtGoodness::default()
    };
    assert!(few_vars > many_vars);
}

#[test]
fn more_restrained_variables_is_better() {
    let few_vars = IfStmtGoodness {
        restrained_variables: 2,
        ..IfStmtGoodness::default()
    };
    let many_vars = IfStmtGoodness {
        restrained_variables: 3,
        ..IfStmtGoodness::default()
    };
    assert!(many_vars > few_vars);
}

fn if_stmt_goodness(stmt: &FlatIfStmt, fixed_vars: &BTreeSet<FlatVar>) -> IfStmtGoodness {
    let is_equal = match stmt.rel {
        FlatInRel::Equality(_) => true,
        FlatInRel::Rel(_) | FlatInRel::TypeSet(_) | FlatInRel::RelWithDiagonals { .. } => false,
    };
    let age = stmt.age;
    let new_variables = stmt
        .args
        .iter()
        .unique()
        .filter(|var| !fixed_vars.contains(var))
        .count();
    let restrained_variables = stmt
        .args
        .iter()
        .unique()
        .filter(|var| fixed_vars.contains(var))
        .count();
    IfStmtGoodness {
        is_equal,
        age,
        new_variables,
        restrained_variables,
    }
}

fn find_best_index(stmts: &[FlatIfStmt], fixed_vars: &BTreeSet<FlatVar>) -> Option<usize> {
    (0..stmts.len()).max_by_key(|i| if_stmt_goodness(&stmts[*i], fixed_vars))
}

/// A pass that optimizes the order of [FlatIfStmt]s in the premise of a [FlatRule].
pub fn sort_premise<'a>(rule: &mut FlatRule) {
    let premise = &mut rule.premise;
    let mut fixed_vars: BTreeSet<FlatVar> = BTreeSet::new();
    for sorted_until in 0..premise.len() {
        let best_index = sorted_until
            + find_best_index(&premise[sorted_until..], &fixed_vars)
                .expect("a non-empty slice of if statements should have a best element");
        fixed_vars.extend(premise[best_index].args.iter().cloned());
        premise.swap(sorted_until, best_index);
    }
}