lattices/ght/
lattice.rs

1//! Lattice traits for GHT
2
3use core::cmp::Ordering::{Equal, Greater, Less};
4use std::cmp::Ordering;
5use std::collections::HashMap;
6use std::hash::Hash;
7
8use variadics::variadic_collections::VariadicSet;
9use variadics::{CloneVariadic, PartialEqVariadic, SplitBySuffix, VariadicExt, var_expr, var_type};
10
11use crate::ght::{GeneralizedHashTrieNode, GhtGet, GhtInner, GhtLeaf};
12use crate::{IsBot, IsTop, LatticeBimorphism, LatticeOrd, Merge};
13
14impl<Head, Node> Merge<GhtInner<Head, Node>> for GhtInner<Head, Node>
15where
16    Node: GeneralizedHashTrieNode + Merge<Node>,
17    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
18    Self: GeneralizedHashTrieNode,
19    Head: Hash + Eq + Clone,
20{
21    fn merge(&mut self, other: GhtInner<Head, Node>) -> bool {
22        let mut changed = false;
23
24        for (k, v) in other.children {
25            match self.children.entry(k) {
26                std::collections::hash_map::Entry::Occupied(mut occupied) => {
27                    changed |= occupied.get_mut().merge_node(v);
28                }
29                std::collections::hash_map::Entry::Vacant(vacant) => {
30                    vacant.insert(v);
31                    changed = true;
32                }
33            }
34        }
35        changed
36    }
37}
38
39impl<Schema, ValType, Storage> Merge<GhtLeaf<Schema, ValType, Storage>>
40    for GhtLeaf<Schema, ValType, Storage>
41where
42    Schema: Eq + Hash,
43    Storage: VariadicSet<Schema = Schema> + Extend<Schema> + IntoIterator<Item = Schema>,
44{
45    fn merge(&mut self, other: GhtLeaf<Schema, ValType, Storage>) -> bool {
46        let old_len = self.elements.len();
47        self.elements.extend(other.elements);
48        self.elements.len() > old_len
49    }
50}
51
52impl<Head, Node> PartialEq<GhtInner<Head, Node>> for GhtInner<Head, Node>
53where
54    Head: Hash + Eq + 'static + Clone,
55    Node: GeneralizedHashTrieNode + 'static + PartialEq,
56    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
57    Node::Schema: SplitBySuffix<var_type!(Head, ...Node::SuffixSchema)>,
58    GhtInner<Head, Node>: GhtGet,
59    <GhtInner<Head, Node> as GhtGet>::Get: PartialEq,
60{
61    fn eq(&self, other: &GhtInner<Head, Node>) -> bool {
62        if self.children.len() != other.children.len() {
63            return false;
64        }
65
66        for head in self.iter() {
67            let other_node = other.get(&head);
68            if other_node.is_none() {
69                return false;
70            }
71            let this_node = self.get(&head);
72            if this_node.is_none() {
73                return false;
74            }
75            if this_node.unwrap() != other_node.unwrap() {
76                return false;
77            }
78        }
79        true
80    }
81}
82
83impl<Head, Node> PartialOrd<GhtInner<Head, Node>> for GhtInner<Head, Node>
84where
85    Head: Hash + Eq + 'static + Clone,
86    Node: 'static + GeneralizedHashTrieNode + PartialEq + PartialOrd,
87    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
88    Node::Schema: SplitBySuffix<var_type!(Head, ...Node::SuffixSchema)>,
89{
90    fn partial_cmp(&self, other: &GhtInner<Head, Node>) -> Option<Ordering> {
91        let mut self_any_greater = false;
92        let mut other_any_greater = false;
93        if self.children.is_empty() && other.children.is_empty() {
94            Some(Equal)
95        } else {
96            #[expect(
97                clippy::disallowed_methods,
98                reason = "nondeterministic iteration order, TODO(mingwei)"
99            )]
100            for k in self.children.keys().chain(other.children.keys()) {
101                match (self.children.get(k), other.children.get(k)) {
102                    (Some(self_value), Some(other_value)) => {
103                        match self_value.partial_cmp(other_value)? {
104                            Greater => {
105                                self_any_greater = true;
106                            }
107                            Less => {
108                                other_any_greater = true;
109                            }
110                            Equal => {}
111                        }
112                    }
113                    (Some(_), None) => {
114                        self_any_greater = true;
115                    }
116                    (None, Some(_)) => {
117                        other_any_greater = true;
118                    }
119                    (None, None) => unreachable!(),
120                }
121            }
122            match (self_any_greater, other_any_greater) {
123                (true, false) => Some(Greater),
124                (false, true) => Some(Less),
125                (false, false) => Some(Equal),
126                (true, true) => unreachable!(),
127            }
128        }
129    }
130}
131
132impl<Schema, SuffixSchema, Storage> PartialOrd<GhtLeaf<Schema, SuffixSchema, Storage>>
133    for GhtLeaf<Schema, SuffixSchema, Storage>
134where
135    Schema: Eq + Hash + PartialEqVariadic,
136    SuffixSchema: Eq + Hash,
137    Storage: VariadicSet<Schema = Schema> + PartialEq,
138{
139    fn partial_cmp(&self, other: &GhtLeaf<Schema, SuffixSchema, Storage>) -> Option<Ordering> {
140        match self.elements.len().cmp(&other.elements.len()) {
141            Greater => {
142                if other.elements.iter().all(|tup| self.elements.contains(tup)) {
143                    Some(Greater)
144                } else {
145                    None
146                }
147            }
148            Equal => {
149                if self
150                    .elements
151                    .iter()
152                    .all(|head| other.elements.contains(head))
153                {
154                    Some(Equal)
155                } else {
156                    None
157                }
158            }
159            Less => {
160                if self
161                    .elements
162                    .iter()
163                    .all(|head| other.elements.contains(head))
164                {
165                    Some(Less)
166                } else {
167                    None
168                }
169            }
170        }
171    }
172}
173
174impl<Head, Node> LatticeOrd<GhtInner<Head, Node>> for GhtInner<Head, Node>
175where
176    Self: PartialOrd<GhtInner<Head, Node>>,
177    Head: Clone,
178    Node: GeneralizedHashTrieNode,
179    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
180{
181}
182impl<Schema, SuffixSchema, Storage> LatticeOrd<GhtLeaf<Schema, SuffixSchema, Storage>>
183    for GhtLeaf<Schema, SuffixSchema, Storage>
184where
185    Schema: Eq + Hash + PartialEqVariadic,
186    SuffixSchema: Eq + Hash,
187    Storage: VariadicSet<Schema = Schema> + PartialEq,
188{
189}
190
191impl<Head, Node> IsBot for GhtInner<Head, Node>
192where
193    Head: Clone,
194    Node: GeneralizedHashTrieNode + IsBot,
195{
196    fn is_bot(&self) -> bool {
197        #[expect(
198            clippy::disallowed_methods,
199            reason = "nondeterministic iteration order, TODO(mingwei)"
200        )]
201        self.children.iter().all(|(_, v)| v.is_bot())
202    }
203}
204
205impl<Schema, SuffixSchema, Storage> IsBot for GhtLeaf<Schema, SuffixSchema, Storage>
206where
207    Schema: Eq + Hash,
208    SuffixSchema: Eq + Hash,
209    Storage: VariadicSet<Schema = Schema>,
210{
211    fn is_bot(&self) -> bool {
212        self.elements.is_empty()
213    }
214}
215
216impl<Head, Node> IsTop for GhtInner<Head, Node>
217where
218    Head: Clone,
219    Node: GeneralizedHashTrieNode,
220    Node::Storage: VariadicSet<Schema = Node::Schema>, // multiset is not a lattice!
221{
222    fn is_top(&self) -> bool {
223        false
224    }
225}
226
227impl<Schema, SuffixSchema, Storage> IsTop for GhtLeaf<Schema, SuffixSchema, Storage>
228where
229    Schema: Eq + Hash,
230    SuffixSchema: Eq + Hash,
231    Storage: VariadicSet<Schema = Schema>,
232{
233    fn is_top(&self) -> bool {
234        false
235    }
236}
237
238//////////////////////////
239// BiMorphisms for GHT
240//
241
242/// Bimorphism for the cartesian product of two GHT *subtries*.
243///
244/// Output is a set of all possible pairs of
245/// *suffixes* from the two subtries. If you use this at the root of a GHT, it's a full cross-product.
246/// If you use this at an internal node, it provides a 'factorized' representation with only the suffix
247/// cross-products expanded.
248pub struct GhtCartesianProductBimorphism<GhtOut> {
249    _phantom: std::marker::PhantomData<fn() -> GhtOut>,
250}
251impl<GhtOut> Default for GhtCartesianProductBimorphism<GhtOut> {
252    fn default() -> Self {
253        Self {
254            _phantom: Default::default(),
255        }
256    }
257}
258impl<'a, 'b, GhtA, GhtB, GhtOut> LatticeBimorphism<&'a GhtA, &'b GhtB>
259    for GhtCartesianProductBimorphism<GhtOut>
260where
261    GhtA: GeneralizedHashTrieNode,
262    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
263    GhtB: GeneralizedHashTrieNode,
264    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
265    GhtOut: FromIterator<var_type!(...GhtA::SuffixSchema, ...GhtB::SuffixSchema)>,
266    GhtA::SuffixSchema: CloneVariadic,
267    GhtB::SuffixSchema: CloneVariadic,
268{
269    type Output = GhtOut;
270
271    fn call(&mut self, ght_a: &'a GhtA, ght_b: &'b GhtB) -> Self::Output {
272        ght_a.recursive_iter().flat_map(|a| {
273            let (_a_prefix, a_suffix) = <GhtA::Schema as SplitBySuffix<GhtA::SuffixSchema>>::split_by_suffix_ref(a);
274            ght_b
275                .recursive_iter()
276                .map(move |b| {
277                    let (_b_prefix, b_suffix) = <GhtB::Schema as SplitBySuffix<GhtB::SuffixSchema>>::split_by_suffix_ref(b);
278                    var_expr!(...<GhtA::SuffixSchema as CloneVariadic>::clone_ref_var(a_suffix), ...<GhtB::SuffixSchema as CloneVariadic>::clone_ref_var(b_suffix))
279                })
280        }).collect()
281    }
282}
283
284/// Forms the cartesian product of the ValTypes only
285/// Used on GhtLeaf nodes to implement DeepJoinLatticeBimorphism
286pub struct GhtValTypeProductBimorphism<GhtOut> {
287    _phantom: std::marker::PhantomData<fn() -> GhtOut>,
288}
289impl<GhtOut> Default for GhtValTypeProductBimorphism<GhtOut> {
290    fn default() -> Self {
291        Self {
292            _phantom: Default::default(),
293        }
294    }
295}
296impl<'a, 'b, GhtA, GhtB, GhtOut> LatticeBimorphism<&'a GhtA, &'b GhtB>
297    for GhtValTypeProductBimorphism<GhtOut>
298where
299    GhtA: GeneralizedHashTrieNode,
300    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
301    GhtB: GeneralizedHashTrieNode,
302    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
303    GhtOut: FromIterator<var_type!(...GhtA::Schema, ...GhtB::ValType)>,
304    GhtA::Schema: Eq + Hash + CloneVariadic,
305    GhtB::Schema: Eq + Hash + SplitBySuffix<GhtB::ValType>,
306    GhtB::ValType: CloneVariadic,
307{
308    type Output = GhtOut;
309
310    fn call(&mut self, ght_a: &'a GhtA, ght_b: &'b GhtB) -> Self::Output {
311        ght_a.recursive_iter().flat_map(|a| {
312            ght_b
313                .recursive_iter()
314                .map(move |b| {
315                    let (_prefix_b, suffix_b)
316                        = <GhtB::Schema as SplitBySuffix<GhtB::ValType>>::split_by_suffix_ref(b);
317                    var_expr!(...<GhtA::Schema as CloneVariadic>::clone_ref_var(a), ...<GhtB::ValType as CloneVariadic>::clone_ref_var(suffix_b))
318                }
319            )
320        }).collect()
321    }
322}
323
324/// Composable bimorphism, wraps an existing morphism by partitioning it per key.
325///
326/// For example, `GhtKeyedBimorphism<..., GhtCartesianProduct<...>>` is a join.
327#[derive(Default)]
328pub struct GhtBimorphism<Bimorphism> {
329    bimorphism: Bimorphism,
330    // _phantom: std::marker::PhantomData<fn() -> MapOut>,
331}
332impl<Bimorphism> GhtBimorphism<Bimorphism> {
333    /// Create a `KeyedBimorphism` using `bimorphism` for handling values.
334    pub fn new(bimorphism: Bimorphism) -> Self {
335        Self {
336            bimorphism,
337            // _phantom: std::marker::PhantomData,
338        }
339    }
340}
341
342impl<GhtA, GhtB, ValFunc, GhtOut> LatticeBimorphism<GhtA, GhtB> for GhtBimorphism<ValFunc>
343where
344    GhtA: GeneralizedHashTrieNode,
345    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
346    GhtB: GeneralizedHashTrieNode,
347    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
348    GhtOut: GeneralizedHashTrieNode, // FromIterator<var_type!(...GhtA::Schema, ...GhtB::ValType)>,
349    for<'a, 'b> ValFunc: LatticeBimorphism<&'a GhtA, &'b GhtB, Output = GhtOut>,
350{
351    type Output = GhtOut;
352
353    fn call(&mut self, ght_a: GhtA, ght_b: GhtB) -> Self::Output {
354        let node_bim = &mut self.bimorphism; // GhtNodeKeyedBimorphism::<ValFunc>::new(self.bimorphism);
355        node_bim.call(&ght_a, &ght_b)
356    }
357}
358
359#[derive(Default)]
360/// bimorphism trait for equijoining Ght Nodes
361pub struct GhtNodeKeyedBimorphism<Bimorphism> {
362    bimorphism: Bimorphism,
363}
364/// bimorphism implementation for equijoining Ght Nodes
365impl<Bimorphism> GhtNodeKeyedBimorphism<Bimorphism> {
366    /// initialize bimorphism
367    pub fn new(bimorphism: Bimorphism) -> Self {
368        Self { bimorphism }
369    }
370}
371/// bimorphism implementation for equijoining Ght Nodes
372impl<'a, 'b, Head, GhtA, GhtB, ValFunc> LatticeBimorphism<&'a GhtA, &'b GhtB>
373    for GhtNodeKeyedBimorphism<ValFunc>
374where
375    Head: Clone + Hash + Eq,
376    ValFunc: LatticeBimorphism<&'a GhtA::Get, &'b GhtB::Get>,
377    ValFunc::Output: GeneralizedHashTrieNode,
378    GhtA: GeneralizedHashTrieNode<Head = Head> + GhtGet,
379    GhtB: GeneralizedHashTrieNode<Head = Head, Schema = GhtA::Schema> + GhtGet,
380    GhtA::Storage: VariadicSet<Schema = GhtA::Schema>, // multiset is not a lattice!
381    GhtB::Storage: VariadicSet<Schema = GhtB::Schema>, // multiset is not a lattice!
382    <GhtA::SuffixSchema as VariadicExt>::AsRefVar<'a>: CloneVariadic,
383    <GhtB::SuffixSchema as VariadicExt>::AsRefVar<'b>: CloneVariadic,
384{
385    type Output = GhtInner<Head, ValFunc::Output>; // HashMap<Head, ValFunc::Output>; // GhtOut;
386
387    fn call(&mut self, ght_a: &'a GhtA, ght_b: &'b GhtB) -> Self::Output {
388        let mut children = HashMap::<Head, ValFunc::Output>::new();
389        // for head in ght_b.iter_keys() {
390        for head in ght_b.iter() {
391            if let Some(get_a) = ght_a.get(&head) {
392                let get_b = ght_b.get(&head).unwrap();
393                let val = self.bimorphism.call(get_a, get_b);
394                children.insert(head.clone(), val);
395            }
396        }
397        GhtInner { children }
398    }
399}
400
401/// bimorphism trait for equijoin on full tuple (keys in all GhtInner nodes)
402pub trait DeepJoinLatticeBimorphism<Storage> {
403    /// bimorphism type for equijoin on full tuple (keys in all GhtInner nodes)
404    type DeepJoinLatticeBimorphism;
405}
406/// bimorphism implementation for equijoin on full tuple (keys in all GhtInner nodes)
407impl<Head, NodeA, NodeB, Storage> DeepJoinLatticeBimorphism<Storage>
408    for (GhtInner<Head, NodeA>, GhtInner<Head, NodeB>)
409where
410    Head: 'static + Hash + Eq + Clone,
411    NodeA: 'static + GeneralizedHashTrieNode,
412    NodeB: 'static + GeneralizedHashTrieNode,
413    NodeA::Storage: VariadicSet<Schema = NodeA::Schema>, // multiset is not a lattice!
414    NodeB::Storage: VariadicSet<Schema = NodeB::Schema>, // multiset is not a lattice!
415    (NodeA, NodeB): DeepJoinLatticeBimorphism<Storage>,
416    Storage: VariadicSet<Schema = var_type!(...NodeA::Schema, ...NodeB::ValType)>,
417{
418    type DeepJoinLatticeBimorphism = GhtNodeKeyedBimorphism<
419        <(NodeA, NodeB) as DeepJoinLatticeBimorphism<Storage>>::DeepJoinLatticeBimorphism,
420    >;
421}
422impl<SchemaA, ValTypeA, StorageA, SchemaB, ValTypeB, StorageB, StorageOut>
423    DeepJoinLatticeBimorphism<StorageOut>
424    for (
425        GhtLeaf<SchemaA, ValTypeA, StorageA>,
426        GhtLeaf<SchemaB, ValTypeB, StorageB>,
427    )
428where
429    SchemaA: 'static + VariadicExt + Eq + Hash + SplitBySuffix<ValTypeA>, /* + AsRefVariadicPartialEq */
430    ValTypeA: 'static + VariadicExt + Eq + Hash, // + AsRefVariadicPartialEq
431    SchemaB: 'static + VariadicExt + Eq + Hash + SplitBySuffix<ValTypeB>, /* + AsRefVariadicPartialEq */
432    ValTypeB: 'static + VariadicExt + Eq + Hash, // + AsRefVariadicPartialEq
433    StorageA: VariadicSet<Schema = SchemaA>,
434    StorageB: VariadicSet<Schema = SchemaB>,
435    StorageOut: VariadicSet<Schema = var_type!(...SchemaA, ...ValTypeB)>,
436    for<'x> SchemaA::AsRefVar<'x>: CloneVariadic,
437    for<'x> SchemaB::AsRefVar<'x>: CloneVariadic,
438    var_type!(...SchemaA, ...ValTypeB): Eq + Hash,
439{
440    type DeepJoinLatticeBimorphism = GhtValTypeProductBimorphism<
441        GhtLeaf<
442            var_type!(...SchemaA, ...ValTypeB),
443            var_type!(...ValTypeA, ...ValTypeB),
444            StorageOut,
445        >,
446    >;
447}
lattices/ght/lattice.rs

lattices/ght/
lattice.rs
