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

use egglog_ast::generic_ast::GenericExpr;
use std::fmt::{Display, Formatter};
use std::hash::Hash;
use std::hash::Hasher;

use crate::ast::CorrespondingVar;
use crate::core::ResolvedCall;
use crate::{ArcSort, sort};

#[derive(Debug, Clone)]
pub struct ResolvedVar {
    pub name: String,
    pub sort: ArcSort,
    /// Is this a reference to a global variable?
    /// After the `remove_globals` pass, this should be `false`.
    ///
    /// NB: we distinguish between a global reference and a global binding.
    /// The current implementation of `Eq` and `Hash` does not take this field
    /// into consideration.
    /// Overall, the definition of equality between two ResolvedVars is dicey.
    pub is_global_ref: bool,
}

impl PartialEq for ResolvedVar {
    fn eq(&self, other: &Self) -> bool {
        self.name == other.name && self.sort.name() == other.sort.name()
    }
}

impl Eq for ResolvedVar {}

impl Hash for ResolvedVar {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.name.hash(state);
        self.sort.name().hash(state);
    }
}

impl Display for ResolvedVar {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        let display_name = crate::util::sanitize_internal_name(&self.name);
        write!(f, "{}", display_name)
    }
}

pub type Expr = GenericExpr<String, String>;
/// A generated expression is an expression that is generated by the system
/// and does not have annotations.
pub type ResolvedExpr = GenericExpr<ResolvedCall, ResolvedVar>;
/// A [`MappedExpr`] arises naturally when you want a mapping between an expression
/// and its flattened form. It records this mapping by annotating each `Head`
/// with a `Leaf`, which it maps to in the flattened form.
/// A useful operation on `MappedExpr`s is [`MappedExprExt::get_corresponding_var_or_lit``].
pub(crate) type MappedExpr<Head, Leaf> = GenericExpr<CorrespondingVar<Head, Leaf>, Leaf>;

pub(crate) trait ResolvedExprExt {
    fn output_type(&self) -> ArcSort;
    fn get_global_var(&self) -> Option<ResolvedVar>;
}

impl ResolvedExprExt for ResolvedExpr {
    fn output_type(&self) -> ArcSort {
        match self {
            ResolvedExpr::Lit(_, lit) => sort::literal_sort(lit),
            ResolvedExpr::Var(_, resolved_var) => resolved_var.sort.clone(),
            ResolvedExpr::Call(_, resolved_call, _) => resolved_call.output().clone(),
        }
    }

    fn get_global_var(&self) -> Option<ResolvedVar> {
        match self {
            ResolvedExpr::Var(_, v) if v.is_global_ref => Some(v.clone()),
            _ => None,
        }
    }
}

#[macro_export]
macro_rules! call {
    ($func:expr, $args:expr) => {
        $crate::ast::GenericExpr::Call($crate::span!(), $func.into(), $args.into_iter().collect())
    };
}

#[macro_export]
macro_rules! lit {
    ($lit:expr) => {
        $crate::ast::GenericExpr::Lit($crate::span!(), $lit.into())
    };
}

#[macro_export]
macro_rules! var {
    ($var:expr) => {
        $crate::ast::GenericExpr::Var($crate::span!(), $var.into())
    };
}

// Rust macro annoyance; see stackoverflow.com/questions/26731243/how-do-i-use-a-macro-across-module-files
pub use {call, lit, var};