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::*;
46
47/// A sort (type) in the e-graph that defines values in egglog. Sorts are user-extensible (e.g., [`prelude::BaseSort`]).
48pub trait Sort: Any + Send + Sync + Debug {
49    /// Returns the name of this sort.
50    fn name(&self) -> &str;
51
52    /// Returns the backend-specific column type. See [`ColumnTy`].
53    fn column_ty(&self, backend: &egglog_bridge::EGraph) -> ColumnTy;
54
55    /// return the inner sorts if a container sort
56    /// remember that containers can contain containers
57    /// and this only unfolds one level
58    fn inner_sorts(&self) -> Vec<ArcSort> {
59        if self.is_container_sort() {
60            todo!("inner_sorts: {}", self.name());
61        } else {
62            panic!("inner_sort called on non-container sort: {}", self.name());
63        }
64    }
65
66    fn register_type(&self, backend: &mut egglog_bridge::EGraph);
67
68    fn as_arc_any(self: Arc<Self>) -> Arc<dyn Any + Send + Sync + 'static>;
69
70    fn is_eq_sort(&self) -> bool {
71        false
72    }
73
74    // return true if it is a container sort.
75    fn is_container_sort(&self) -> bool {
76        false
77    }
78
79    // return true if it is a container sort that contains ids.
80    // only eq_sort and eq_container_sort need to be canonicalized.
81    fn is_eq_container_sort(&self) -> bool {
82        false
83    }
84
85    /// Return the serialized name of the sort
86    ///
87    /// Only used for container sorts, which cannot be serialized with make_expr so need an explicit name
88    fn serialized_name(&self, _container_values: &ContainerValues, _value: Value) -> String {
89        self.name().to_owned()
90    }
91
92    /// Return the inner values and sorts.
93    /// Only container sort need to implement this method,
94    fn inner_values(
95        &self,
96        container_values: &ContainerValues,
97        value: Value,
98    ) -> Vec<(ArcSort, Value)> {
99        debug_assert!(!self.is_container_sort());
100        let _ = value;
101        let _ = container_values;
102        vec![]
103    }
104
105    /// Return the type id of values that this sort represents.
106    ///
107    /// Every non-EqSort sort should return Some(TypeId).
108    fn value_type(&self) -> Option<TypeId>;
109
110    fn register_primitives(self: Arc<Self>, eg: &mut EGraph) {
111        let _ = eg;
112    }
113
114    /// Reconstruct a container value in a TermDag
115    fn reconstruct_termdag_container(
116        &self,
117        container_values: &ContainerValues,
118        value: Value,
119        termdag: &mut TermDag,
120        element_terms: Vec<Term>,
121    ) -> Term {
122        let _container_values = container_values;
123        let _value = value;
124        let _termdag = termdag;
125        let _element_terms = element_terms;
126        todo!("reconstruct_termdag_container: {}", self.name());
127    }
128
129    /// Reconstruct a leaf primitive value in a TermDag
130    fn reconstruct_termdag_base(
131        &self,
132        base_values: &BaseValues,
133        value: Value,
134        termdag: &mut TermDag,
135    ) -> Term {
136        let _base_values = base_values;
137        let _value = value;
138        let _termdag = termdag;
139        todo!("reconstruct_termdag_leaf: {}", self.name());
140    }
141}
142
143// Note: this trait is currently intended to be implemented on the
144// same struct as `Sort`. If in the future we have dynamic presorts
145// (for example, we want to add partial application) we should revisit
146// this and make the methods take a `self` parameter.
147pub trait Presort {
148    fn presort_name() -> &'static str;
149    fn reserved_primitives() -> Vec<&'static str>;
150    fn make_sort(
151        typeinfo: &mut TypeInfo,
152        name: String,
153        args: &[Expr],
154    ) -> Result<ArcSort, TypeError>;
155}
156
157pub type MkSort = fn(&mut TypeInfo, String, &[Expr]) -> Result<ArcSort, TypeError>;
158
159#[derive(Debug)]
160pub struct EqSort {
161    pub name: String,
162}
163
164impl Sort for EqSort {
165    fn name(&self) -> &str {
166        &self.name
167    }
168
169    fn column_ty(&self, _backend: &egglog_bridge::EGraph) -> ColumnTy {
170        ColumnTy::Id
171    }
172
173    fn register_type(&self, _backend: &mut egglog_bridge::EGraph) {}
174
175    fn as_arc_any(self: Arc<Self>) -> Arc<dyn Any + Send + Sync + 'static> {
176        self
177    }
178
179    fn is_eq_sort(&self) -> bool {
180        true
181    }
182
183    fn value_type(&self) -> Option<TypeId> {
184        None
185    }
186}
187
188pub fn literal_sort(lit: &Literal) -> ArcSort {
189    match lit {
190        Literal::Int(_) => I64Sort.to_arcsort(),
191        Literal::Float(_) => F64Sort.to_arcsort(),
192        Literal::String(_) => StringSort.to_arcsort(),
193        Literal::Bool(_) => BoolSort.to_arcsort(),
194        Literal::Unit => UnitSort.to_arcsort(),
195    }
196}
egglog/sort/mod.rs

egglog/sort/
mod.rs
