egglog_ast/
generic_ast.rs

1use std::fmt::Display;
2use std::hash::Hash;
3
4use ordered_float::OrderedFloat;
5
6use crate::span::Span;
7
8#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
9pub enum Literal {
10    Int(i64),
11    Float(OrderedFloat<f64>),
12    String(String),
13    Bool(bool),
14    Unit,
15}
16
17#[derive(Clone, Debug, PartialEq, Eq, Hash)]
18pub enum GenericExpr<Head, Leaf> {
19    Var(Span, Leaf),
20    Call(Span, Head, Vec<GenericExpr<Head, Leaf>>),
21    Lit(Span, Literal),
22}
23
24/// Facts are the left-hand side of a [`Command::Rule`].
25/// They represent a part of a database query.
26/// Facts can be expressions or equality constraints between expressions.
27///
28/// Note that primitives such as  `!=` are partial.
29/// When two things are equal, it returns nothing and the query does not match.
30/// For example, the following egglog code runs:
31/// ```text
32/// (fail (check (!= 1 1)))
33/// ```
34#[derive(Clone, Debug, PartialEq, Eq, Hash)]
35pub enum GenericFact<Head, Leaf> {
36    Eq(Span, GenericExpr<Head, Leaf>, GenericExpr<Head, Leaf>),
37    Fact(GenericExpr<Head, Leaf>),
38}
39
40#[derive(Clone, Debug, PartialEq, Eq, Hash)]
41pub struct GenericActions<Head: Clone + Display, Leaf: Clone + PartialEq + Eq + Display + Hash>(
42    pub Vec<GenericAction<Head, Leaf>>,
43);
44
45#[derive(Clone, Debug, PartialEq, Eq, Hash)]
46pub enum GenericAction<Head, Leaf>
47where
48    Head: Clone + Display,
49    Leaf: Clone + PartialEq + Eq + Display + Hash,
50{
51    /// Bind a variable to a particular datatype or primitive.
52    /// At the top level (in a [`Command::Action`]), this defines a global variable.
53    /// In a [`Command::Rule`], this defines a local variable in the actions.
54    Let(Span, Leaf, GenericExpr<Head, Leaf>),
55    /// `set` a function to a particular result.
56    /// `set` should not be used on datatypes-
57    /// instead, use `union`.
58    Set(
59        Span,
60        Head,
61        Vec<GenericExpr<Head, Leaf>>,
62        GenericExpr<Head, Leaf>,
63    ),
64    /// Delete or subsume (mark as hidden from future rewrites and unextractable) an entry from a function.
65    Change(Span, Change, Head, Vec<GenericExpr<Head, Leaf>>),
66    /// `union` two datatypes, making them equal
67    /// in the implicit, global equality relation
68    /// of egglog.
69    /// All rules match modulo this equality relation.
70    ///
71    /// Example:
72    /// ```text
73    /// (datatype Math (Num i64))
74    /// (union (Num 1) (Num 2)); Define that Num 1 and Num 2 are equivalent
75    /// (extract (Num 1)); Extracts Num 1
76    /// (extract (Num 2)); Extracts Num 1
77    /// ```
78    Union(Span, GenericExpr<Head, Leaf>, GenericExpr<Head, Leaf>),
79    Panic(Span, String),
80    Expr(Span, GenericExpr<Head, Leaf>),
81}
82
83/// How a rule is evaluated. The three modes are mutually exclusive, so they
84/// share one field on [`GenericRule`].
85#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
86pub enum RuleEvalMode {
87    /// Default: seminaive (delta) evaluation with restrictive `Pure`/`Write`
88    /// primitive contexts (no database reads in the RHS).
89    #[default]
90    Seminaive,
91    /// `:naive`: match the whole database every iteration, with permissive
92    /// `Read`/`Full` contexts so the RHS may read the database.
93    Naive,
94    /// `:unsafe-seminaive`: like `:naive`'s `Read`/`Full` contexts (the RHS may
95    /// read the database) but keeps delta evaluation. **Unsafe**: an RHS read
96    /// observes the database mid-iteration and isn't re-evaluated if it changes.
97    UnsafeSeminaive,
98}
99
100impl RuleEvalMode {
101    /// `:naive` — disables seminaive evaluation (unlike `:unsafe-seminaive`).
102    pub fn is_naive(self) -> bool {
103        matches!(self, RuleEvalMode::Naive)
104    }
105}
106
107#[derive(Clone, Debug, PartialEq, Eq, Hash)]
108pub struct GenericRule<Head, Leaf>
109where
110    Head: Clone + Display,
111    Leaf: Clone + PartialEq + Eq + Display + Hash,
112{
113    pub span: Span,
114    pub head: GenericActions<Head, Leaf>,
115    pub body: Vec<GenericFact<Head, Leaf>>,
116    /// A globally unique name for this rule in the EGraph.
117    pub name: String,
118    /// The ruleset this rule belongs to. Defaults to `""`.
119    pub ruleset: String,
120    /// How this rule is evaluated; set by `:naive` / `:unsafe-seminaive`.
121    pub eval_mode: RuleEvalMode,
122    /// If `true`, this rule skips tree-decomposition during query
123    /// planning and evaluate rules as a single-bag (without decomposing
124    /// it into smaller queries). Set via the `:no-decomp` rule option.
125    pub no_decomp: bool,
126    /// If `true`, table atoms in this rule match subsumed rows as well as
127    /// live rows. This is intended for internal maintenance rules, not
128    /// ordinary user rewrites.
129    pub include_subsumed: bool,
130}
131
132/// Change a function entry.
133#[derive(Clone, Debug, Copy, PartialEq, Eq, Hash)]
134pub enum Change {
135    /// `delete` this entry from a function.
136    /// Be wary! Only delete entries that are guaranteed to be not useful.
137    Delete,
138    /// `subsume` this entry so that it cannot be queried or extracted, but still can be checked.
139    /// Note that this is currently forbidden for functions with custom merges.
140    Subsume,
141}
egglog_ast/generic_ast.rs

egglog_ast/
generic_ast.rs
