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
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

use crate::{util::HashMap, *};

#[derive(Clone, Debug, Default)]
pub(crate) struct Names {
    seen: HashMap<String, Span>,
    global_aliases: HashMap<String, (String, Span)>,
}

impl Names {
    fn check(&mut self, name: String, new: Span) -> Result<(), Error> {
        if let Some(old) = self.seen.get(&name) {
            Err(Error::Shadowing(name, old.clone(), new))
        } else {
            self.seen.insert(name, new);
            Ok(())
        }
    }

    fn track_global_alias(&mut self, name: &str, span: &Span) {
        if let Some(stripped) = name.strip_prefix(GLOBAL_NAME_PREFIX) {
            self.global_aliases
                .insert(stripped.to_owned(), (name.to_owned(), span.clone()));
        }
    }

    fn check_pattern_name(&mut self, name: &str, span: &Span) -> Result<(), Error> {
        let canonical = name
            .strip_prefix(GLOBAL_NAME_PREFIX)
            .unwrap_or(name)
            .to_owned();
        if let Some((global_name, global_span)) = self.global_aliases.get(&canonical) {
            return Err(Error::Shadowing(
                format!(
                    "pattern variable `{}` conflicts with global `{}`",
                    name, global_name
                ),
                global_span.clone(),
                span.clone(),
            ));
        }
        self.check(name.to_owned(), span.clone())
    }

    /// WARNING: this function does not handle `push` and `pop`.
    /// Because `Names` is contained on the `EGraph`, this will
    /// work correctly when executed from `process_command`, but
    /// a unit test that called this function multiple times without
    /// changing the `EGraph` will be wrong.
    pub(crate) fn check_shadowing(&mut self, command: &ResolvedNCommand) -> Result<(), Error> {
        match command {
            ResolvedNCommand::Sort(span, name, _args) => self.check(name.clone(), span.clone()),
            ResolvedNCommand::Function(decl) => {
                self.check(decl.name.clone(), decl.span.clone())?;
                if decl.let_binding {
                    self.track_global_alias(&decl.name, &decl.span);
                }
                Ok(())
            }
            ResolvedNCommand::AddRuleset(span, name) => self.check(name.clone(), span.clone()),
            ResolvedNCommand::UnstableCombinedRuleset(span, name, _args) => {
                self.check(name.clone(), span.clone())
            }
            ResolvedNCommand::NormRule { rule, .. } => {
                let mut inner = self.clone();
                inner.check_shadowing_query(&rule.body)?;
                for action in rule.head.iter() {
                    inner.check_shadowing_action(action)?;
                }
                Ok(())
            }
            ResolvedNCommand::CoreAction(action) => self.check_shadowing_action(action),
            ResolvedNCommand::Check(_span, query) => {
                let mut inner = self.clone();
                inner.check_shadowing_query(query)
            }
            ResolvedNCommand::Fail(_span, command) => {
                let mut inner = self.clone();
                inner.check_shadowing(command)
            }
            ResolvedNCommand::Extract(..) => Ok(()),
            ResolvedNCommand::RunSchedule(..) => Ok(()),
            ResolvedNCommand::PrintOverallStatistics(..) => Ok(()),
            ResolvedNCommand::PrintFunction(..) => Ok(()),
            ResolvedNCommand::PrintSize(..) => Ok(()),
            ResolvedNCommand::Input { .. } => Ok(()),
            ResolvedNCommand::Output { .. } => Ok(()),
            ResolvedNCommand::Push(..) => Ok(()),
            ResolvedNCommand::Pop(..) => Ok(()),
            ResolvedNCommand::UserDefined(..) => Ok(()),
        }
    }

    fn check_shadowing_query(&mut self, query: &[ResolvedFact]) -> Result<(), Error> {
        // we want to allow names in queries to shadow each other, so we first collect
        // all of the variable names, and then we check each of those names once
        fn collect_expr_names(expr: &ResolvedExpr, out: &mut HashMap<String, Span>) {
            match expr {
                ResolvedExpr::Lit(..) => {}
                ResolvedExpr::Var(span, name) => {
                    out.entry(name.name.clone()).or_insert_with(|| span.clone());
                }
                ResolvedExpr::Call(_span, _func, args) => {
                    args.iter().for_each(|e| collect_expr_names(e, out));
                }
            }
        }

        let mut collected = HashMap::default();

        for fact in query {
            match fact {
                ResolvedFact::Eq(_span, e1, e2) => {
                    collect_expr_names(e1, &mut collected);
                    collect_expr_names(e2, &mut collected);
                }
                ResolvedFact::Fact(e) => collect_expr_names(e, &mut collected),
            }
        }

        for (name, span) in collected {
            self.check_pattern_name(&name, &span)?;
        }

        Ok(())
    }

    fn check_shadowing_action(&mut self, action: &ResolvedAction) -> Result<(), Error> {
        if let ResolvedAction::Let(span, name, _args) = action {
            self.check_pattern_name(&name.name, span)
        } else {
            Ok(())
        }
    }
}