egglog/sort/
mod.rs

1use num::traits::{CheckedAdd, CheckedDiv, CheckedMul, CheckedSub, One, Signed, ToPrimitive, Zero};
2use num::{BigInt, BigRational};
3pub use ordered_float::OrderedFloat;
4use std::any::TypeId;
5use std::fmt::Debug;
6use std::ops::{Shl, Shr};
7use std::{any::Any, sync::Arc};
8
9use crate::core_relations;
10pub use core_relations::{
11    BaseValues, Boxed, ContainerValue, ContainerValues, ExecutionState, Rebuilder,
12};
13pub use egglog_bridge::ColumnTy;
14
15use crate::*;
16
17pub type Z = core_relations::Boxed<BigInt>;
18pub type Q = core_relations::Boxed<BigRational>;
19pub type F = core_relations::Boxed<OrderedFloat<f64>>;
20pub type S = core_relations::Boxed<String>;
21
22mod bigint;
23pub use bigint::*;
24mod bigrat;
25pub use bigrat::*;
26mod bool;
27pub use self::bool::*;
28mod string;
29pub use string::*;
30mod unit;
31pub use unit::*;
32mod i64;
33pub use self::i64::*;
34mod f64;
35pub use self::f64::*;
36mod map;
37pub use map::*;
38mod set;
39pub use set::*;
40mod vec;
41pub use vec::*;
42mod r#fn;
43pub use r#fn::*;
44mod multiset;
45pub use multiset::*;
46mod pair;
47pub use pair::*;
48
49/// A sort (type) in the e-graph that defines values in egglog. Sorts are user-extensible (e.g., [`prelude::BaseSort`]).
50pub trait Sort: Any + Send + Sync + Debug {
51    /// Returns the name of this sort.
52    fn name(&self) -> &str;
53
54    /// Returns the backend-specific column type. See [`ColumnTy`].
55    fn column_ty(&self, backend: &egglog_bridge::EGraph) -> ColumnTy;
56
57    /// return the inner sorts if a container sort
58    /// remember that containers can contain containers
59    /// and this only unfolds one level
60    fn inner_sorts(&self) -> Vec<ArcSort> {
61        if self.is_container_sort() {
62            todo!("inner_sorts: {}", self.name());
63        } else {
64            panic!("inner_sort called on non-container sort: {}", self.name());
65        }
66    }
67
68    fn register_type(&self, backend: &mut egglog_bridge::EGraph);
69
70    fn as_arc_any(self: Arc<Self>) -> Arc<dyn Any + Send + Sync + 'static>;
71
72    fn is_eq_sort(&self) -> bool {
73        false
74    }
75
76    // return true if it is a container sort.
77    fn is_container_sort(&self) -> bool {
78        false
79    }
80
81    // return true if it is a container sort that contains ids or other container sorts that contain ids.
82    // only eq_sort and eq_container_sort need to be canonicalized.
83    fn is_eq_container_sort(&self) -> bool {
84        false
85    }
86
87    /// Return the serialized name of the sort
88    ///
89    /// Only used for container sorts, which cannot be serialized with make_expr so need an explicit name
90    fn serialized_name(&self, _container_values: &ContainerValues, _value: Value) -> String {
91        self.name().to_owned()
92    }
93
94    /// Return the inner values and sorts.
95    /// Only container sort need to implement this method,
96    fn inner_values(
97        &self,
98        container_values: &ContainerValues,
99        value: Value,
100    ) -> Vec<(ArcSort, Value)> {
101        debug_assert!(!self.is_container_sort());
102        let _ = value;
103        let _ = container_values;
104        vec![]
105    }
106
107    /// Return the type id of values that this sort represents.
108    ///
109    /// Every non-EqSort sort should return Some(TypeId).
110    fn value_type(&self) -> Option<TypeId>;
111
112    fn register_primitives(self: Arc<Self>, eg: &mut EGraph) {
113        let _ = eg;
114    }
115
116    /// Reconstruct a container value in a TermDag
117    fn reconstruct_termdag_container(
118        &self,
119        container_values: &ContainerValues,
120        value: Value,
121        termdag: &mut TermDag,
122        element_terms: Vec<TermId>,
123    ) -> TermId {
124        let _container_values = container_values;
125        let _value = value;
126        let _termdag = termdag;
127        let _element_terms = element_terms;
128        todo!("reconstruct_termdag_container: {}", self.name());
129    }
130
131    /// Reconstruct a leaf primitive value in a TermDag
132    fn reconstruct_termdag_base(
133        &self,
134        base_values: &BaseValues,
135        value: Value,
136        termdag: &mut TermDag,
137    ) -> TermId {
138        let _base_values = base_values;
139        let _value = value;
140        let _termdag = termdag;
141        todo!("reconstruct_termdag_leaf: {}", self.name());
142    }
143}
144
145// Note: this trait is currently intended to be implemented on the
146// same struct as `Sort`. If in the future we have dynamic presorts
147// (for example, we want to add partial application) we should revisit
148// this and make the methods take a `self` parameter.
149pub trait Presort {
150    fn presort_name() -> &'static str;
151    fn reserved_primitives() -> Vec<&'static str>;
152    fn make_sort(
153        typeinfo: &mut TypeInfo,
154        name: String,
155        args: &[Expr],
156    ) -> Result<ArcSort, TypeError>;
157}
158
159pub type MkSort = fn(&mut TypeInfo, String, &[Expr]) -> Result<ArcSort, TypeError>;
160
161#[derive(Debug)]
162pub struct EqSort {
163    pub name: String,
164}
165
166impl Sort for EqSort {
167    fn name(&self) -> &str {
168        &self.name
169    }
170
171    fn column_ty(&self, _backend: &egglog_bridge::EGraph) -> ColumnTy {
172        ColumnTy::Id
173    }
174
175    fn register_type(&self, _backend: &mut egglog_bridge::EGraph) {}
176
177    fn as_arc_any(self: Arc<Self>) -> Arc<dyn Any + Send + Sync + 'static> {
178        self
179    }
180
181    fn is_eq_sort(&self) -> bool {
182        true
183    }
184
185    fn value_type(&self) -> Option<TypeId> {
186        None
187    }
188}
189
190pub fn literal_sort(lit: &Literal) -> ArcSort {
191    match lit {
192        Literal::Int(_) => I64Sort.to_arcsort(),
193        Literal::Float(_) => F64Sort.to_arcsort(),
194        Literal::String(_) => StringSort.to_arcsort(),
195        Literal::Bool(_) => BoolSort.to_arcsort(),
196        Literal::Unit => UnitSort.to_arcsort(),
197    }
198}
egglog/sort/mod.rs

egglog/sort/
mod.rs
