pathmap/
ring.rs

1
2use std::collections::{HashMap, HashSet};
3use std::hash::Hash;
4
5/// The result of an algebraic operation on elements in a partial lattice
6///
7/// NOTE: For some operations, it is conceptually valid for both `Identity` and `None` results to be
8/// simultaneously appropriate, for example `None.pmeet(Some)`. In these situations, `None` should take precedence
9/// over `Identity`, but either of the results can be considered correct so your code must behave correctly in
10/// either case.
11///
12/// NOTE 2: The following conditions for the Identity bitmask must be respected or the implementation may panic or
13/// produce logically invalid results.
14/// - The bit mask must be non-zero
15/// - Bits beyond the number of operation arguments must not be set.  e.g. an arity-2 operation may only set bit 0
16///     and bit 1, but never any additional bits.
17/// - Setting two or more bits simultaneously asserts the arguments are identities of each other, so this must be
18///     true in fact.
19/// - The inverse of the above does not hold.  E.g. if multiple bits are not set, it may **not** be assumed that 
20///     the arguments are not identities of each other.
21/// - Non-commutative operations, such as [DistributiveLattice::psubtract], must never set bits beyond bit 0 ([SELF_IDENT])
22#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
23pub enum AlgebraicResult<V> {
24    /// A result indicating the input values perfectly annhilate and the output should be removed and discarded
25    #[default]
26    None,
27    /// A result indicating the output element is identical to the input element(s) identified by the bit mask
28    ///
29    /// NOTE: The constants [SELF_IDENT] and [COUNTER_IDENT] can be used as conveniences when specifying the bitmask.
30    Identity(u64),
31    /// A new result element
32    Element(V),
33}
34
35/// A bitmask value to `or` into the [AlgebraicResult::Identity] argument to specify the result is the identity of `self`
36pub const SELF_IDENT: u64 = 0x1;
37
38/// A bitmask value to `or` into the [AlgebraicResult::Identity] argument to specify the result is the identity of `other`
39pub const COUNTER_IDENT: u64 = 0x2;
40
41impl<V> AlgebraicResult<V> {
42    /// Returns `true` is `self` is [AlgebraicResult::None], otherwise returns `false`
43    #[inline]
44    pub fn is_none(&self) -> bool {
45        matches!(self, AlgebraicResult::None)
46    }
47    /// Returns `true` is `self` is [AlgebraicResult::Identity], otherwise returns `false`
48    #[inline]
49    pub fn is_identity(&self) -> bool {
50        matches!(self, AlgebraicResult::Identity(_))
51    }
52    /// Returns `true` is `self` is [AlgebraicResult::Element], otherwise returns `false`
53    #[inline]
54    pub fn is_element(&self) -> bool {
55        matches!(self, AlgebraicResult::Element(_))
56    }
57    /// Returns the identity mask from a [AlgebraicResult::Identity], otherwise returns `None`
58    #[inline]
59    pub fn identity_mask(&self) -> Option<u64> {
60        match self {
61            Self::None => None,
62            Self::Identity(mask) => Some(*mask),
63            Self::Element(_) => None,
64        }
65    }
66    /// Swaps the mask bits in an [AlgebraicResult::Identity] result, for an arity-2 operation, such that
67    /// the [SELF_IDENT] bit becomes the [COUNTER_IDENT] bit, and vise-versa
68    ///
69    /// Removes identity mask bits higher than 2
70    #[inline]
71    pub fn invert_identity(self) -> Self {
72        match self {
73            Self::None => AlgebraicResult::None,
74            Self::Identity(mask) => {
75                let new_mask = ((mask & SELF_IDENT) << 1) | ((mask & COUNTER_IDENT) >> 1);
76                AlgebraicResult::Identity(new_mask)
77            },
78            Self::Element(v) => AlgebraicResult::Element(v),
79        }
80    }
81    /// Maps a `AlgebraicResult<V>` to `AlgebraicResult<U>` by applying a function to a contained value, if
82    /// self is `AlgebraicResult::Element(V)`.  Otherwise returns the value of `self`
83    #[inline]
84    pub fn map<U, F>(self, f: F) -> AlgebraicResult<U>
85        where F: FnOnce(V) -> U,
86    {
87        match self {
88            Self::None => AlgebraicResult::None,
89            Self::Identity(mask) => AlgebraicResult::Identity(mask),
90            Self::Element(v) => AlgebraicResult::Element(f(v)),
91        }
92    }
93    /// Converts from `&AlgebraicResult<V>` to `AlgebraicResult<&V>`
94    #[inline]
95    pub fn as_ref(&self) -> AlgebraicResult<&V> {
96        match *self {
97            Self::Element(ref v) => AlgebraicResult::Element(v),
98            Self::None => AlgebraicResult::None,
99            Self::Identity(mask) => AlgebraicResult::Identity(mask),
100        }
101    }
102    /// Returns an option containing the `Element` value, substituting the result of the `ident_f` closure
103    /// if `self` is [Identity](AlgebraicResult::Identity)
104    ///
105    /// The index of the first identity argument is passed to the closure.  E.g. `0` for self, etc.
106    #[inline]
107    pub fn map_into_option<IdentF>(self, ident_f: IdentF) -> Option<V>
108        where IdentF: FnOnce(usize) -> Option<V>
109    {
110        match self {
111            Self::Element(v) => Some(v),
112            Self::None => None,
113            Self::Identity(mask) => ident_f(mask.trailing_zeros() as usize),
114        }
115    }
116    /// Returns an option containing the `Element` value, substituting the result from the corresponding
117    /// index in the `idents` table if `self` is [Identity](AlgebraicResult::Identity)
118    #[inline]
119    pub fn into_option<I: AsRef<[VRef]>, VRef: std::borrow::Borrow<V>>(self, idents: I) -> Option<V>
120        where V: Clone
121    {
122        match self {
123            Self::Element(v) => Some(v),
124            Self::None => None,
125            Self::Identity(mask) => {
126                let idents = idents.as_ref();
127                Some(idents[mask.trailing_zeros() as usize].borrow().clone())
128            },
129        }
130    }
131
132    /// Returns the contained `Element` value or an identity value from the `idents` table.  Panics if `self`
133    /// is [AlgebraicResult::None]
134    #[inline]
135    pub fn unwrap<I: AsRef<[VRef]>, VRef: std::borrow::Borrow<V>>(self, idents: I) -> V
136        where V: Clone
137    {
138        match self {
139            Self::Element(v) => v,
140            Self::None => panic!(),
141            Self::Identity(mask) => {
142                let idents = idents.as_ref();
143                idents[mask.trailing_zeros() as usize].borrow().clone()
144            },
145        }
146    }
147    /// Returns the contained `Element` value or runs one of the provided closures
148    ///
149    /// This is the most straightforward way to turn a partial lattice result into a complete lattice element
150    #[inline]
151    pub fn unwrap_or_else<IdentF, NoneF>(self, ident_f: IdentF, none_f: NoneF) -> V
152        where
153        IdentF: FnOnce(usize) -> V,
154        NoneF: FnOnce() -> V
155    {
156        match self {
157            Self::Element(v) => v,
158            Self::None => none_f(),
159            Self::Identity(mask) => ident_f(mask.trailing_zeros() as usize),
160        }
161    }
162    /// Returns the contained `Element` value or one of the provided default values
163    #[inline]
164    pub fn unwrap_or<I: AsRef<[VRef]>, VRef: std::borrow::Borrow<V>>(self, idents: I, none: V) -> V
165        where V: Clone
166    {
167        match self {
168            Self::Element(v) => v,
169            Self::None => none,
170            Self::Identity(mask) => {
171                let idents = idents.as_ref();
172                idents[mask.trailing_zeros() as usize].borrow().clone()
173            },
174        }
175    }
176    /// Merges two `AlgebraicResult`s into a combined `AlgebraicResult<U>`.  This method is useful to compose a
177    /// result for an operation on whole type arguments, from the results of separate operations on each field
178    /// of the arguments.
179    ///
180    /// NOTE: Take care when implementing the `meet` operation across heterogeneous items (e.g. abstracted sets),
181    /// because one set may be a superset of the other.  simply merging the `AlgebraicResult`s from individual
182    /// `meet` operations on the overlapping elements will lead to a false `Identity` result for one of the sets.
183    ///
184    /// ```
185    /// use pathmap::ring::{Lattice, AlgebraicResult};
186    /// 
187    /// struct Composed {
188    ///     field0: bool,
189    ///     field1: bool,
190    /// }
191    ///
192    /// fn pjoin(a: &Composed, b: &Composed) -> AlgebraicResult<Composed> {
193    ///     let result0 = a.field0.pjoin(&b.field0);
194    ///     let result1 = a.field1.pjoin(&b.field1);
195    ///     result0.merge(result1, |which_arg| {
196    ///         match which_arg {
197    ///             0 => Some(a.field0),
198    ///             1 => Some(b.field0),
199    ///             _ => unreachable!()
200    ///         }
201    ///     }, |which_arg| {
202    ///         match which_arg {
203    ///             0 => Some(a.field1),
204    ///             1 => Some(b.field1),
205    ///             _ => unreachable!()
206    ///         }
207    ///     }, |field0, field1| {
208    ///         AlgebraicResult::Element(Composed{
209    ///             field0: field0.unwrap(),
210    ///             field1: field1.unwrap()
211    ///         })
212    ///     })
213    /// }
214    /// ```
215    #[inline]
216    pub fn merge<BV, U, MergeF, AIdent, BIdent>(self, b: AlgebraicResult<BV>, self_idents: AIdent, b_idents: BIdent, merge_f: MergeF) -> AlgebraicResult<U>
217        where
218        MergeF: FnOnce(Option<V>, Option<BV>) -> AlgebraicResult<U>,
219        AIdent: FnOnce(usize) -> Option<V>,
220        BIdent: FnOnce(usize) -> Option<BV>,
221    {
222        match self {
223            Self::None => {
224                match b {
225                    AlgebraicResult::None => AlgebraicResult::None,
226                    AlgebraicResult::Element(b_v) => merge_f(None, Some(b_v)),
227                    AlgebraicResult::Identity(b_mask) => {
228                        let self_ident = self_idents(0);
229                        if self_ident.is_none() {
230                            AlgebraicResult::Identity(b_mask)
231                        } else {
232                            let b_v = b_idents(b_mask.trailing_zeros() as usize);
233                            merge_f(None, b_v)
234                        }
235                    },
236                }
237            },
238            Self::Identity(self_mask) => {
239                match b {
240                    AlgebraicResult::None => {
241                        let b_ident = b_idents(0);
242                        if b_ident.is_none() {
243                            AlgebraicResult::Identity(self_mask)
244                        } else {
245                            let self_v = self_idents(self_mask.trailing_zeros() as usize);
246                            merge_f(self_v, None)
247                        }
248                    },
249                    AlgebraicResult::Element(b_v) => {
250                        let self_v = self_idents(self_mask.trailing_zeros() as usize);
251                        merge_f(self_v, Some(b_v))
252                    },
253                    AlgebraicResult::Identity(b_mask) => {
254                        let combined_mask = self_mask & b_mask;
255                        if combined_mask > 0 {
256                            AlgebraicResult::Identity(combined_mask)
257                        } else {
258                            let self_v = self_idents(self_mask.trailing_zeros() as usize);
259                            let b_v = b_idents(b_mask.trailing_zeros() as usize);
260                            merge_f(self_v, b_v)
261                        }
262                    }
263                }
264            },
265            Self::Element(self_v) => {
266                match b {
267                    AlgebraicResult::None => merge_f(Some(self_v), None),
268                    AlgebraicResult::Element(b_v) => merge_f(Some(self_v), Some(b_v)),
269                    AlgebraicResult::Identity(b_mask) => {
270                        let b_v = b_idents(b_mask.trailing_zeros() as usize);
271                        merge_f(Some(self_v), b_v)
272                    }
273                }
274            }
275        }
276    }
277    /// Creates a new `AlgebraicResult` from an [AlgebraicStatus], and a method to create the element value
278    #[inline]
279    pub fn from_status<F>(status: AlgebraicStatus, element_f: F) -> Self
280        where F: FnOnce() -> V
281    {
282        match status {
283            AlgebraicStatus::None => Self::None,
284            AlgebraicStatus::Identity => Self::Identity(SELF_IDENT),
285            AlgebraicStatus::Element => Self::Element(element_f())
286        }
287    }
288    /// Returns an [AlgebraicStatus] associated with the `AlgebraicResult`
289    #[inline]
290    pub fn status(&self) -> AlgebraicStatus {
291        match self {
292            AlgebraicResult::None => AlgebraicStatus::None,
293            AlgebraicResult::Element(_) => AlgebraicStatus::Element,
294            AlgebraicResult::Identity(mask) => {
295                if mask & SELF_IDENT > 0 {
296                    AlgebraicStatus::Identity
297                } else {
298                    AlgebraicStatus::Element
299                }
300            }
301        }
302    }
303}
304
305impl<V> AlgebraicResult<Option<V>> {
306    /// Flattens a nested `Option<V>` inside an `AlgebraicResult<V>`, converting `AlgebraicResult::Element(None)`
307    /// into `AlgebraicResult::None`
308    #[inline]
309    pub fn flatten(self) -> AlgebraicResult<V> {
310        match self {
311            Self::Element(v) => {
312                match v {
313                    Some(v) => AlgebraicResult::Element(v),
314                    None => AlgebraicResult::None
315                }
316            },
317            Self::None => AlgebraicResult::None,
318            Self::Identity(mask) => AlgebraicResult::Identity(mask),
319        }
320    }
321}
322
323/// Status result that is returned from an in-place algebraic operation (a method that takes `&mut self`)
324///
325/// NOTE: `AlgebraicStatus` values are ordered, with `Element` being the lowest value and `None` being the
326/// highest.  Higher values make stronger guarantees about the results of the operation, but a lower values
327/// are still correct and your code must behave appropriately.
328///
329/// For example, for example `Empty.join(Empty)` would result in Empty, but also leave the original value
330/// unmodified, therefore both `Identity` and `None` are conceptually valid in that case.
331///
332/// In general, `AlgebraicStatus` return values are a valid signal for loop termination, but should not be
333/// strictly relied upon for other kinds of branching.  For example, `Element` might be returned by
334/// [ZipperWriting::join](crate::zipper::ZipperWriting::join) instead of `Identity` if the internal representation was changed by the method,
335/// however the next call to `join` ought to return `Identity` if nothing new is added.
336///
337/// This type mirrors [AlgebraicResult]
338#[derive(Clone, Copy, Default, Debug, PartialEq, Eq, PartialOrd, Ord)]
339pub enum AlgebraicStatus {
340    /// A result indicating `self` contains the operation's output
341    #[default]
342    Element,
343    /// A result indicating `self` was unmodified by the operation
344    Identity,
345    /// A result indicating `self` was completely annhilated and is now empty
346    None,
347}
348
349impl AlgebraicStatus {
350    /// Returns `true` if the status is [AlgebraicStatus::None], otherwise returns `false`
351    #[inline]
352    pub fn is_none(&self) -> bool {
353        matches!(self, Self::None)
354    }
355    /// Returns `true` if the status is [AlgebraicStatus::Identity], otherwise returns `false`
356    #[inline]
357    pub fn is_identity(&self) -> bool {
358        matches!(self, Self::Identity)
359    }
360    /// Returns `true` if the status is [AlgebraicStatus::Element], otherwise returns `false`
361    #[inline]
362    pub fn is_element(&self) -> bool {
363        matches!(self, Self::Element)
364    }
365    /// Merges two `AlgebraicStatus` values into one.  Useful when composing the status from operations on individual fields
366    ///
367    /// The `self_none` and `b_none` args indicate whether the `self` and `b` args, respectively, correspond to `None`
368    /// values prior to the operation.  Pass `true` if the existing values were already `none` or `false` if they
369    /// were made `None` by the operation.  For operations that cannot convert a non-`None` value to `None`,
370    /// (such as join) it is safe to pass (`true`, `true`) regardless of the actual original values.
371    ///
372    /// See [AlgebraicResult::merge].
373    #[inline]
374    pub fn merge(self, b: Self, self_none: bool, b_none: bool) -> AlgebraicStatus {
375        match self {
376            Self::None => match b {
377                Self::None => Self::None,
378                Self::Element => Self::Element,
379                Self::Identity => if self_none {
380                    Self::Identity
381                } else {
382                    Self::Element
383                },
384            },
385            Self::Identity => match b {
386                Self::Element => Self::Element,
387                Self::Identity => Self::Identity,
388                Self::None => if b_none {
389                    Self::Identity
390                } else {
391                    Self::Element
392                },
393            },
394            Self::Element => Self::Element
395        }
396    }
397}
398
399impl<V> From<FatAlgebraicResult<V>> for AlgebraicResult<V> {
400    #[inline]
401    fn from(src: FatAlgebraicResult<V>) -> Self {
402        if src.identity_mask > 0 {
403            AlgebraicResult::Identity(src.identity_mask)
404        } else {
405            match src.element {
406                Some(element) => AlgebraicResult::Element(element),
407                None => AlgebraicResult::None
408            }
409        }
410    }
411}
412
413/// Internal result type that can be down-converted to an [AlgebraicResult], but carries additional information
414#[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
415pub(crate) struct FatAlgebraicResult<V> {
416    /// An identity mask that maps to the [AlgebraicResult::Identity] value, or 0 if the result is not an identity
417    pub identity_mask: u64,
418    /// Carries the element value, irrespective of the identity information.  It is the discretion of the code using
419    /// this struct as to whether or not to populate this field in the case of an identity result
420    pub element: Option<V>,
421}
422
423impl<V> FatAlgebraicResult<V> {
424    #[inline(always)]
425    pub(crate) const fn new(identity_mask: u64, element: Option<V>) -> Self {
426        Self {identity_mask, element}
427    }
428    /// Converts an [AlgebraicResult] into a `FatAlgebraicResult`, assuming the source `result` was the
429    /// output of a binary operation (two arguments).
430    #[inline]
431    pub(crate) fn from_binary_op_result(result: AlgebraicResult<V>, a: &V, b: &V) -> Self
432        where V: Clone
433    {
434        match result {
435            AlgebraicResult::None => FatAlgebraicResult::none(),
436            AlgebraicResult::Element(v) => FatAlgebraicResult::element(v),
437            AlgebraicResult::Identity(mask) => {
438                debug_assert!(mask <= (SELF_IDENT | COUNTER_IDENT));
439                if mask & SELF_IDENT > 0 {
440                    FatAlgebraicResult::new(mask, Some(a.clone()))
441                } else {
442                    debug_assert_eq!(mask, COUNTER_IDENT);
443                    FatAlgebraicResult::new(mask, Some(b.clone()))
444                }
445            }
446        }
447    }
448    /// Maps a `FatAlgebraicResult<V>` to `FatAlgebraicResult<U>` by applying a function to a contained value
449    #[inline]
450    pub fn map<U, F>(self, f: F) -> FatAlgebraicResult<U>
451        where F: FnOnce(V) -> U,
452    {
453        FatAlgebraicResult::<U> {
454            identity_mask: self.identity_mask,
455            element: self.element.map(f)
456        }
457    }
458    /// The result of an operation between non-none arguments that results in None
459    #[inline(always)]
460    pub(crate) const fn none() -> Self {
461        Self {identity_mask: 0, element: None}
462    }
463    /// The result of an operation that generated a brand new result
464    #[inline(always)]
465    pub(crate) fn element(e: V) -> Self {
466        Self {identity_mask: 0, element: Some(e)}
467    }
468    //GOAT, currently unused although implemented and working
469    // /// Merges two `FatAlgebraicResult<V>`s into an `AlgebraicResult<U>`.  See [AlgebraicResult::merge]
470    // #[inline]
471    // pub fn merge_and_convert<U, F>(self, other: Self, merge_f: F) -> AlgebraicResult<U>
472    //     where F: FnOnce(Option<V>, Option<V>) -> AlgebraicResult<U>,
473    // {
474    //     if self.element.is_none() && other.element.is_none() {
475    //         return AlgebraicResult::None
476    //     }
477    //     let combined_mask = self.identity_mask & other.identity_mask;
478    //     if combined_mask > 0 {
479    //         return AlgebraicResult::Identity(combined_mask)
480    //     }
481    //     merge_f(self.element, other.element)
482    // }
483    //GOAT, currently unused, but fully implemented and working
484    // /// Intersects arg with the contents of self, and sets the arg_idx bit in the case of an identity result
485    // pub fn meet(self, arg: &V, arg_idx: usize) -> Self where V: Lattice + Clone {
486    //     match self.element {
487    //         None => {
488    //             debug_assert_eq!(self.identity_mask, 0);
489    //             Self::new(self.identity_mask, None)
490    //         },
491    //         Some(self_element) => match self_element.pmeet(arg) {
492    //             AlgebraicResult::None => Self::none(),
493    //             AlgebraicResult::Element(e) => Self::element(e),
494    //             AlgebraicResult::Identity(mask) => {
495    //                 if mask & SELF_IDENT > 0 {
496    //                     let new_mask = self.identity_mask | ((mask & COUNTER_IDENT) << (arg_idx-1));
497    //                     Self::new(new_mask, Some(self_element))
498    //                 } else {
499    //                     debug_assert!(mask & COUNTER_IDENT > 0);
500    //                     let new_mask = (mask & COUNTER_IDENT) << (arg_idx-1);
501    //                     Self::new(new_mask, Some(arg.clone()))
502    //                 }
503    //             }
504    //         }
505    //     }
506    // }
507    /// Unions arg with the contents of self, and sets the arg_idx bit in the case of an identity result
508    pub fn join(self, arg: &V, arg_idx: usize) -> Self where V: Lattice + Clone {
509        match self.element {
510            None => {
511                Self::new(self.identity_mask | 1 << arg_idx, Some(arg.clone()))
512            },
513            Some(self_element) => match self_element.pjoin(&arg) {
514                AlgebraicResult::None => Self::none(),
515                AlgebraicResult::Element(e) => Self::element(e),
516                AlgebraicResult::Identity(mask) => {
517                    if mask & SELF_IDENT > 0 {
518                        let new_mask = self.identity_mask | ((mask & COUNTER_IDENT) << (arg_idx-1));
519                        Self::new(new_mask, Some(self_element))
520                    } else {
521                        debug_assert!(mask & COUNTER_IDENT > 0);
522                        let new_mask = (mask & COUNTER_IDENT) << (arg_idx-1);
523                        Self::new(new_mask, Some(arg.clone()))
524                    }
525                }
526            }
527        }
528    }
529}
530
531/// Implements basic algebraic behavior (union & intersection) for a type
532pub trait Lattice {
533    /// Implements the union operation between two instances of a type in a partial lattice, resulting in
534    /// the creation of a new result instance
535    fn pjoin(&self, other: &Self) -> AlgebraicResult<Self> where Self: Sized;
536
537    /// Implements the union operation between two instances of a type, consuming the `other` input operand,
538    /// and modifying `self` to become the joined type
539    fn join_into(&mut self, other: Self) -> AlgebraicStatus where Self: Sized {
540        let result = self.pjoin(&other);
541        //NOTE: pedantically, the `default_f` ought to assign the `&mut s` to `Self::bottom()`, however there is
542        // no way for a join to get to an empty result except by starting with an empty result, so leaving the
543        // arg alone is functionally the same.
544        in_place_default_impl(result, self, other, |_s| {}, |e| e)
545    }
546
547    /// Implements the intersection operation between two instances of a type in a partial lattice
548    fn pmeet(&self, other: &Self) -> AlgebraicResult<Self> where Self: Sized;
549
550    //GOAT, we want a meet_into, that has the same semantics as join_into, e.g. mutating in-place.  I
551    // don't think there is any benefit to consuming `other`, however, so we can still take `other: &Self`
552
553    //GOAT, this should be temporarily deprecated until we work out the correct function prototype
554    fn join_all<S: AsRef<Self>, Args: AsRef<[S]>>(xs: Args) -> AlgebraicResult<Self> where Self: Sized + Clone {
555        let mut iter = xs.as_ref().into_iter().enumerate();
556        let mut result = match iter.next() {
557            None => return AlgebraicResult::None,
558            Some((_, first)) => FatAlgebraicResult::new(SELF_IDENT, Some(first.as_ref().clone())),
559        };
560        for (i, next) in iter {
561            result = result.join(next.as_ref(), i);
562        }
563        result.into()
564    }
565}
566
567/// Internal function to implement the default behavior of `join_into`, `meet_into`, etc. in terms of `pjoin`, `pmeet`, etc.
568fn in_place_default_impl<SelfT, OtherT, ConvertF, DefaultF>(result: AlgebraicResult<SelfT>, self_ref: &mut SelfT, other: OtherT, default_f: DefaultF, convert_f: ConvertF) -> AlgebraicStatus
569    where
570    DefaultF: FnOnce(&mut SelfT),
571    ConvertF: Fn(OtherT) -> SelfT
572{
573    match result {
574        AlgebraicResult::None => {
575            default_f(self_ref);
576            AlgebraicStatus::None
577        },
578        AlgebraicResult::Element(v) => {
579            *self_ref = v;
580            AlgebraicStatus::Element
581        },
582        AlgebraicResult::Identity(mask) => {
583            if mask & SELF_IDENT > 0 {
584                AlgebraicStatus::Identity
585            } else {
586                *self_ref = convert_f(other);
587                AlgebraicStatus::Element
588            }
589        },
590    }
591}
592
593/// Implements algebraic behavior on a reference to a [Lattice] type, such as a smart pointer that can't
594/// hold ownership
595pub trait LatticeRef {
596    type T;
597    fn pjoin(&self, other: &Self) -> AlgebraicResult<Self::T>;
598    fn pmeet(&self, other: &Self) -> AlgebraicResult<Self::T>;
599}
600
601/// Implements subtract behavior for a type
602pub trait DistributiveLattice {
603    /// Implements the partial subtract operation
604    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> where Self: Sized;
605
606    //GOAT, We want a psubtract_from (subtract_into??) that operates on a `&mut self`
607}
608
609/// Implements subtract behavior on a reference to a [DistributiveLattice] type
610pub trait DistributiveLatticeRef {
611    /// The type that is referenced
612    type T;
613
614    /// Implements the partial subtract operation on the referenced values, resulting in the potential
615    /// creation of a new value
616    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self::T>;
617}
618
619// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
620// Private traits
621// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
622
623/// Used to implement restrict operation.  TODO, come up with a better math-explanation about how this
624/// is a quantale
625///
626/// Currently this trait isn't exposed because it's unclear what we degrees of felxibility really want
627/// from restrict, and what performance we are willing to trade to get them
628pub(crate) trait Quantale {
629    /// TODO: Document this (currently internal-only)
630    fn prestrict(&self, other: &Self) -> AlgebraicResult<Self> where Self: Sized;
631}
632
633/// An internal mirror of the [Lattice] trait, where the `self` and `other` types don't need to be
634/// exactly the same type, in order to permit blanket implementations
635pub(crate) trait HeteroLattice<OtherT> {
636    fn pjoin(&self, other: &OtherT) -> AlgebraicResult<Self> where Self: Sized;
637    fn join_into(&mut self, other: OtherT) -> AlgebraicStatus where Self: Sized {
638        let result = self.pjoin(&other);
639        //NOTE: See comment on [Lattice::join_into] default impl, regarding using `Self::bottom` for `default_f`
640        in_place_default_impl(result, self, other, |_s| {}, |e| Self::convert(e))
641    }
642    fn pmeet(&self, other: &OtherT) -> AlgebraicResult<Self> where Self: Sized;
643    // fn join_all(xs: &[&Self]) -> Self where Self: Sized; //HeteroLattice will entirely disappear with the policy refactor, so it's not worth worying about this anymore
644    fn convert(other: OtherT) -> Self;
645}
646
647/// An internal mirror of the [DistributiveLattice] trait, where the `self` and `other` types
648/// don't need to be exactly the same type, to facilitate blanket impls
649pub(crate) trait HeteroDistributiveLattice<OtherT> {
650    fn psubtract(&self, other: &OtherT) -> AlgebraicResult<Self> where Self: Sized;
651}
652
653/// Internal mirror for [Quantale] See discussion on [HeteroLattice].
654pub(crate) trait HeteroQuantale<OtherT> {
655    fn prestrict(&self, other: &OtherT) -> AlgebraicResult<Self> where Self: Sized;
656}
657
658// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
659// impls on primitive & std types
660// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
661
662// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
663// =-*   `Option<V>`                                                                                  *-=
664
665impl<V: Lattice + Clone> Lattice for Option<V> {
666    fn pjoin(&self, other: &Option<V>) -> AlgebraicResult<Self> {
667        match self {
668            None => match other {
669                None => { AlgebraicResult::None }
670                Some(_) => { AlgebraicResult::Identity(COUNTER_IDENT) }
671            },
672            Some(l) => match other {
673                None => { AlgebraicResult::Identity(SELF_IDENT) }
674                Some(r) => { l.pjoin(r).map(|result| Some(result)) }
675            }
676        }
677    }
678    fn join_into(&mut self, other: Self) -> AlgebraicStatus {
679        match self {
680            None => { match other {
681                None => AlgebraicStatus::None,
682                Some(r) => {
683                    *self = Some(r);
684                    AlgebraicStatus::Element
685                }
686            } }
687            Some(l) => match other {
688                None => AlgebraicStatus::Identity,
689                Some(r) => {
690                    l.join_into(r)
691                }
692            }
693        }
694    }
695    fn pmeet(&self, other: &Option<V>) -> AlgebraicResult<Option<V>> {
696        match self {
697            None => { AlgebraicResult::None }
698            Some(l) => {
699                match other {
700                    None => { AlgebraicResult::None }
701                    Some(r) => l.pmeet(r).map(|result| Some(result))
702                }
703            }
704        }
705    }
706}
707
708impl<V: DistributiveLattice + Clone> DistributiveLattice for Option<V> {
709    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> {
710        match self {
711            None => { AlgebraicResult::None }
712            Some(s) => {
713                match other {
714                    None => { AlgebraicResult::Identity(SELF_IDENT) }
715                    Some(o) => { s.psubtract(o).map(|v| Some(v)) }
716                }
717            }
718        }
719    }
720}
721
722#[test]
723fn option_subtract_test() {
724    assert_eq!(Some(()).psubtract(&Some(())), AlgebraicResult::None);
725    assert_eq!(Some(()).psubtract(&None), AlgebraicResult::Identity(SELF_IDENT));
726    assert_eq!(Some(Some(())).psubtract(&Some(Some(()))), AlgebraicResult::None);
727    assert_eq!(Some(Some(())).psubtract(&None), AlgebraicResult::Identity(SELF_IDENT));
728    assert_eq!(Some(Some(())).psubtract(&Some(None)), AlgebraicResult::Identity(SELF_IDENT));
729    assert_eq!(Some(Some(Some(()))).psubtract(&Some(Some(None))), AlgebraicResult::Identity(SELF_IDENT));
730    assert_eq!(Some(Some(Some(()))).psubtract(&Some(Some(Some(())))), AlgebraicResult::None);
731}
732
733// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
734// =-*   `Option<&V>`                                                                                 *-=
735
736impl<V: Lattice + Clone> LatticeRef for Option<&V> {
737    type T = Option<V>;
738    fn pjoin(&self, other: &Self) -> AlgebraicResult<Self::T> {
739        match self {
740            None => { match other {
741                None => { AlgebraicResult::None }
742                Some(_) => { AlgebraicResult::Identity(COUNTER_IDENT) }
743            } }
744            Some(l) => match other {
745                None => { AlgebraicResult::Identity(SELF_IDENT) }
746                Some(r) => { l.pjoin(r).map(|result| Some(result)) }
747            }
748        }
749    }
750    fn pmeet(&self, other: &Option<&V>) -> AlgebraicResult<Option<V>> {
751        match self {
752            None => { AlgebraicResult::None }
753            Some(l) => {
754                match other {
755                    None => { AlgebraicResult::None }
756                    Some(r) => l.pmeet(r).map(|result| Some(result))
757                }
758            }
759        }
760    }
761}
762
763impl<V: DistributiveLattice + Clone> DistributiveLatticeRef for Option<&V> {
764    type T = Option<V>;
765    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self::T> {
766        match self {
767            None => { AlgebraicResult::None }
768            Some(s) => {
769                match other {
770                    None => { AlgebraicResult::Identity(SELF_IDENT) }
771                    Some(o) => { s.psubtract(o).map(|v| Some(v)) }
772                }
773            }
774        }
775    }
776}
777
778// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
779// =-*   `Box<V>`                                                                                     *-=
780
781impl <V: Lattice> Lattice for Box<V> {
782    fn pjoin(&self, other: &Self) -> AlgebraicResult<Self> {
783        self.as_ref().pjoin(other.as_ref()).map(|result| Box::new(result))
784    }
785    fn pmeet(&self, other: &Self) -> AlgebraicResult<Self> {
786        self.as_ref().pmeet(other.as_ref()).map(|result| Box::new(result))
787    }
788}
789
790impl<V: DistributiveLattice> DistributiveLattice for Box<V> {
791    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> {
792        self.as_ref().psubtract(other.as_ref()).map(|result| Box::new(result))
793    }
794}
795
796// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
797// =-*   `&V`                                                                                         *-=
798
799impl <V: Lattice> LatticeRef for &V {
800    type T = V;
801    fn pjoin(&self, other: &Self) -> AlgebraicResult<Self::T> {
802        (**self).pjoin(other)
803    }
804    fn pmeet(&self, other: &Self) -> AlgebraicResult<Self::T> {
805        (**self).pmeet(other)
806    }
807}
808
809impl<V: DistributiveLattice> DistributiveLatticeRef for &V {
810    type T = V;
811    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self::T> {
812        (**self).psubtract(other)
813    }
814}
815
816// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
817// =-*  `()`, aka unit                                                                                *-=
818
819impl DistributiveLattice for () {
820    fn psubtract(&self, _other: &Self) -> AlgebraicResult<Self> where Self: Sized {
821        AlgebraicResult::None
822    }
823}
824
825impl Lattice for () {
826    fn pjoin(&self, _other: &Self) -> AlgebraicResult<Self> { AlgebraicResult::Identity(SELF_IDENT | COUNTER_IDENT) }
827    fn pmeet(&self, _other: &Self) -> AlgebraicResult<Self> { AlgebraicResult::Identity(SELF_IDENT | COUNTER_IDENT) }
828}
829
830//GOAT trash
831impl Lattice for usize {
832    fn pjoin(&self, _other: &usize) -> AlgebraicResult<usize> { AlgebraicResult::Identity(SELF_IDENT) }
833    fn pmeet(&self, _other: &usize) -> AlgebraicResult<usize> { AlgebraicResult::Identity(SELF_IDENT) }
834}
835
836//GOAT trash
837impl Lattice for u64 {
838    fn pjoin(&self, _other: &u64) -> AlgebraicResult<u64> { AlgebraicResult::Identity(SELF_IDENT) }
839    fn pmeet(&self, _other: &u64) -> AlgebraicResult<u64> { AlgebraicResult::Identity(SELF_IDENT) }
840}
841
842//GOAT trash
843impl DistributiveLattice for u64 {
844    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> where Self: Sized {
845        if self == other { AlgebraicResult::None }
846        else { AlgebraicResult::Element(*self) }
847    }
848}
849
850//GOAT trash
851impl Lattice for u32 {
852    fn pjoin(&self, _other: &u32) -> AlgebraicResult<u32> { AlgebraicResult::Identity(SELF_IDENT) }
853    fn pmeet(&self, _other: &u32) -> AlgebraicResult<u32> { AlgebraicResult::Identity(SELF_IDENT) }
854}
855
856//GOAT trash
857impl Lattice for u16 {
858    fn pjoin(&self, _other: &u16) -> AlgebraicResult<u16> { AlgebraicResult::Identity(SELF_IDENT) }
859    fn pmeet(&self, _other: &u16) -> AlgebraicResult<u16> { AlgebraicResult::Identity(SELF_IDENT) }
860}
861
862//GOAT trash
863impl DistributiveLattice for u16 {
864    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> {
865        if self == other { AlgebraicResult::None }
866        else { AlgebraicResult::Element(*self) }
867    }
868}
869
870//GOAT trash
871impl Lattice for u8 {
872    fn pjoin(&self, _other: &u8) -> AlgebraicResult<u8> { AlgebraicResult::Identity(SELF_IDENT) }
873    fn pmeet(&self, _other: &u8) -> AlgebraicResult<u8> { AlgebraicResult::Identity(SELF_IDENT) }
874}
875
876// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
877// =-*   `bool`                                                                                       *-=
878// NOTE: There is a default impl for `bool` and not for other primitives because there are fewer states,
879// and therefore fewer meanings for a `bool`.
880
881impl DistributiveLattice for bool {
882    fn psubtract(&self, other: &bool) -> AlgebraicResult<Self> {
883        if *self == *other {
884            AlgebraicResult::None
885        } else {
886            AlgebraicResult::Identity(SELF_IDENT)
887        }
888    }
889}
890
891impl Lattice for bool {
892    fn pjoin(&self, other: &bool) -> AlgebraicResult<bool> {
893        if !*self && *other {
894            AlgebraicResult::Identity(COUNTER_IDENT) //result is true
895        } else {
896            AlgebraicResult::Identity(SELF_IDENT)
897        }
898    }
899    fn pmeet(&self, other: &bool) -> AlgebraicResult<bool> {
900        if *self && !*other {
901            AlgebraicResult::Identity(COUNTER_IDENT) //result is false
902        } else {
903            AlgebraicResult::Identity(SELF_IDENT)
904        }
905    }
906}
907
908// =-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-==-**-=
909// =-*   `SetLattice<K>`, including `HashMap<K, V>`, `HashSet<K>`, etc.                               *-=
910
911/// Implemented on an unordered set type, (e.g. [HashMap], [HashSet], etc.) to get automatic implementations
912/// of the [Lattice] and [DistributiveLattice] traits on the set type with the [set_lattice](crate::set_lattice) and
913/// [set_dist_lattice](crate::set_dist_lattice) macros
914///
915/// BEWARE: The `Lattice` and `DistributiveLattice` impls that are derived from the `SetLattice` impl treat
916/// an empty set as equivalent to a nonexistent set.  Therefore, if your arguments contain empty sets, those
917/// sets may or may not be collapsed.  Your code must be aware of this.
918pub trait SetLattice {
919    /// A key type that uniquely identifies an element within the set
920    type K: Clone + Eq;
921
922    /// A payload value type that can be associated with a key in the set
923    type V: Clone;
924
925    /// An [Iterator] type over the contents of the set
926    type Iter<'a>: Iterator<Item=(&'a Self::K, &'a Self::V)> where Self: 'a, Self::V: 'a, Self::K: 'a;
927
928    /// Returns a new empty set with the specified capacity preallocated
929    fn with_capacity(capacity: usize) -> Self;
930
931    /// Returns the number of items in the set
932    fn len(&self) -> usize;
933
934    /// Returns `true` is the set is empty (`len() == 0`), otherwise returns `false`
935    fn is_empty(&self) -> bool;
936
937    /// Returns `true` if the set contains the key, otherwise `false`
938    fn contains_key(&self, key: &Self::K) -> bool;
939
940    /// Inserts a new (key, value) pair, replacing the item at `key` if it already existed
941    fn insert(&mut self, key: Self::K, val: Self::V);
942
943    /// Removes the element at `key` from the set
944    fn remove(&mut self, key: &Self::K);
945
946    /// Returns a reference to the element in the set, or None if the element is not contained within the set
947    fn get(&self, key: &Self::K) -> Option<&Self::V>;
948
949    /// Replaces the element at `key` with the new value `val`.  Will never be called for a non-existent key
950    fn replace(&mut self, key: &Self::K, val: Self::V);
951
952    /// Return a `Self::Iter` in order to iterate the set
953    fn iter<'a>(&'a self) -> Self::Iter<'a>;
954
955    /// An opportunity to free unused space in the set container, if appropriate
956    fn shrink_to_fit(&mut self);
957}
958
959/// A macro to emit the [Lattice] implementation for a type that implements [SetLattice]
960#[macro_export]
961macro_rules! set_lattice {
962    ( $type_ident:ident $(< $( $lt:tt $( : $clt:tt $(+ $dlt:tt )* )? ),+ >)? ) => {
963        impl $(< $( $lt $( : $clt $(+ $dlt )* )? ),+ >)? $crate::ring::Lattice for $type_ident $(< $( $lt ),+ >)? where Self: $crate::ring::SetLattice, <Self as $crate::ring::SetLattice>::V: $crate::ring::Lattice {
964            fn pjoin(&self, other: &Self) -> $crate::ring::AlgebraicResult<Self> {
965                let self_len = $crate::ring::SetLattice::len(self);
966                let other_len = $crate::ring::SetLattice::len(other);
967                let mut result = <Self as $crate::ring::SetLattice>::with_capacity(self_len.max(other_len));
968                let mut is_ident = self_len >= other_len;
969                let mut is_counter_ident = self_len <= other_len;
970                for (key, self_val) in $crate::ring::SetLattice::iter(self) {
971                    if let Some(other_val) = $crate::ring::SetLattice::get(other, key) {
972                        // A key in both sets
973                        let inner_result = self_val.pjoin(other_val);
974                        $crate::ring::set_lattice_update_ident_flags_with_result(
975                            &mut result, inner_result, key, self_val, other_val, &mut is_ident, &mut is_counter_ident
976                        );
977                    } else {
978                        // A key in self, but not in other
979                        $crate::ring::SetLattice::insert(&mut result, key.clone(), self_val.clone());
980                        is_counter_ident = false;
981                    }
982                }
983                for (key, value) in SetLattice::iter(other) {
984                    if !$crate::ring::SetLattice::contains_key(self, key) {
985                        // A key in other, but not in self
986                        $crate::ring::SetLattice::insert(&mut result, key.clone(), value.clone());
987                        is_ident = false;
988                    }
989                }
990                $crate::ring::set_lattice_integrate_into_result(result, is_ident, is_counter_ident, self_len, other_len)
991            }
992            fn pmeet(&self, other: &Self) -> $crate::ring::AlgebraicResult<Self> {
993                let mut result = <Self as $crate::ring::SetLattice>::with_capacity(0);
994                let mut is_ident = true;
995                let mut is_counter_ident = true;
996                let (smaller, larger, switch) = if $crate::ring::SetLattice::len(self) < $crate::ring::SetLattice::len(other) {
997                    (self, other, false)
998                } else {
999                    (other, self, true)
1000                };
1001                for (key, self_val) in $crate::ring::SetLattice::iter(smaller) {
1002                    if let Some(other_val) = $crate::ring::SetLattice::get(larger, key) {
1003                        let inner_result = self_val.pmeet(other_val);
1004                        $crate::ring::set_lattice_update_ident_flags_with_result(
1005                            &mut result, inner_result, key, self_val, other_val, &mut is_ident, &mut is_counter_ident
1006                        );
1007                    } else {
1008                        is_ident = false;
1009                    }
1010                }
1011                if switch {
1012                    core::mem::swap(&mut is_ident, &mut is_counter_ident);
1013                }
1014                $crate::ring::set_lattice_integrate_into_result(result, is_ident, is_counter_ident, self.len(), other.len())
1015            }
1016        }
1017    }
1018}
1019
1020/// Internal function to integrate an `AlgebraicResult` from an element in a set into the set's own overall result
1021#[inline]
1022#[doc(hidden)]
1023pub fn set_lattice_update_ident_flags_with_result<S: SetLattice>(
1024    result_set: &mut S,
1025    result: AlgebraicResult<S::V>,
1026    key: &S::K,
1027    self_val: &S::V,
1028    other_val: &S::V,
1029    is_ident: &mut bool,
1030    is_counter_ident: &mut bool
1031) {
1032    match result {
1033        AlgebraicResult::None => {
1034            *is_ident = false;
1035            *is_counter_ident = false;
1036        },
1037        AlgebraicResult::Element(new_val) => {
1038            *is_ident = false;
1039            *is_counter_ident = false;
1040            result_set.insert(key.clone(), new_val);
1041        },
1042        AlgebraicResult::Identity(mask) => {
1043            if mask & SELF_IDENT > 0 {
1044                result_set.insert(key.clone(), self_val.clone());
1045            } else {
1046                *is_ident = false;
1047            }
1048            if mask & COUNTER_IDENT > 0 {
1049                if mask & SELF_IDENT == 0 {
1050                    result_set.insert(key.clone(), other_val.clone());
1051                }
1052            } else {
1053                *is_counter_ident = false;
1054            }
1055        }
1056    }
1057}
1058
1059/// Internal function to make an `AlgebraicResult` from a new result set and flags
1060#[inline]
1061#[doc(hidden)]
1062pub fn set_lattice_integrate_into_result<S: SetLattice>(
1063    result_set: S,
1064    is_ident: bool,
1065    is_counter_ident: bool,
1066    self_set_len: usize,
1067    other_set_len: usize,
1068) -> AlgebraicResult<S> {
1069    let result_len = result_set.len();
1070    if result_len == 0 {
1071        AlgebraicResult::None
1072    } else {
1073        let mut ident_mask = 0;
1074        if is_ident && self_set_len == result_len {
1075            ident_mask |= SELF_IDENT;
1076        }
1077        if is_counter_ident && other_set_len == result_len {
1078            ident_mask |= COUNTER_IDENT;
1079        }
1080        if ident_mask > 0 {
1081            AlgebraicResult::Identity(ident_mask)
1082        } else {
1083            AlgebraicResult::Element(result_set)
1084        }
1085    }
1086}
1087
1088/// A macro to emit the [DistributiveLattice] implementation for a type that implements [SetLattice]
1089#[macro_export]
1090macro_rules! set_dist_lattice {
1091    ( $type_ident:ident $(< $( $lt:tt $( : $clt:tt $(+ $dlt:tt )* )? ),+ >)? ) => {
1092        impl $(< $( $lt $( : $clt $(+ $dlt )* )? ),+ >)? $crate::ring::DistributiveLattice for $type_ident $(< $( $lt ),+ >)? where Self: $crate::ring::SetLattice + Clone, <Self as $crate::ring::SetLattice>::V: $crate::ring::DistributiveLattice {
1093            fn psubtract(&self, other: &Self) -> $crate::ring::AlgebraicResult<Self> {
1094                let mut is_ident = true;
1095                let mut result = self.clone();
1096                //Two code paths, so that we only iterate over the smaller set
1097                if $crate::ring::SetLattice::len(self) > $crate::ring::SetLattice::len(other) {
1098                    for (key, other_val) in $crate::ring::SetLattice::iter(other) {
1099                        if let Some(self_val) = $crate::ring::SetLattice::get(self, key) {
1100                            set_lattice_subtract_element(&mut result, key, self_val, other_val, &mut is_ident)
1101                        }
1102                    }
1103                } else {
1104                    for (key, self_val) in $crate::ring::SetLattice::iter(self) {
1105                        if let Some(other_val) = $crate::ring::SetLattice::get(other, key) {
1106                            set_lattice_subtract_element(&mut result, key, self_val, other_val, &mut is_ident)
1107                        }
1108                    }
1109                }
1110                if $crate::ring::SetLattice::len(&result) == 0 {
1111                    $crate::ring::AlgebraicResult::None
1112                } else if is_ident {
1113                    $crate::ring::AlgebraicResult::Identity(SELF_IDENT)
1114                } else {
1115                    $crate::ring::SetLattice::shrink_to_fit(&mut result);
1116                    $crate::ring::AlgebraicResult::Element(result)
1117                }
1118            }
1119        }
1120    }
1121}
1122
1123/// Internal function to subtract set elements and integrate the results
1124#[inline]
1125fn set_lattice_subtract_element<S: SetLattice>(
1126    result_set: &mut S,
1127    key: &S::K,
1128    self_val: &S::V,
1129    other_val: &S::V,
1130    is_ident: &mut bool,
1131) where S::V: DistributiveLattice {
1132    match self_val.psubtract(other_val) {
1133        AlgebraicResult::Element(new_val) => {
1134            SetLattice::replace(result_set, key, new_val);
1135            *is_ident = false;
1136        },
1137        AlgebraicResult::Identity(mask) => {
1138            debug_assert_eq!(mask, SELF_IDENT);
1139        },
1140        AlgebraicResult::None => {
1141            SetLattice::remove(result_set, key);
1142            *is_ident = false;
1143        }
1144    }
1145}
1146
1147impl<K: Clone + Eq + Hash, V: Clone + Lattice> SetLattice for HashMap<K, V> {
1148    type K = K;
1149    type V = V;
1150    type Iter<'a> = std::collections::hash_map::Iter<'a, K, V> where K: 'a, V: 'a;
1151    fn with_capacity(capacity: usize) -> Self { Self::with_capacity(capacity) }
1152    fn len(&self) -> usize { self.len() }
1153    fn is_empty(&self) -> bool { self.is_empty() }
1154    fn contains_key(&self, key: &Self::K) -> bool { self.contains_key(key) }
1155    fn insert(&mut self, key: Self::K, val: Self::V) { self.insert(key, val); }
1156    fn get(&self, key: &Self::K) -> Option<&Self::V> { self.get(key) }
1157    fn replace(&mut self, key: &Self::K, val: Self::V) { *self.get_mut(key).unwrap() = val }
1158    fn remove(&mut self, key: &Self::K) { self.remove(key); }
1159    fn iter<'a>(&'a self) -> Self::Iter<'a> { self.iter() }
1160    fn shrink_to_fit(&mut self) { self.shrink_to_fit(); }
1161}
1162
1163set_lattice!(HashMap<K, V>);
1164set_dist_lattice!(HashMap<K, V>);
1165
1166impl<K: Clone + Eq + Hash> SetLattice for HashSet<K> {
1167    type K = K;
1168    type V = ();
1169    type Iter<'a> = HashSetIterWrapper<'a, K> where K: 'a;
1170    fn with_capacity(capacity: usize) -> Self { Self::with_capacity(capacity) }
1171    fn len(&self) -> usize { self.len() }
1172    fn is_empty(&self) -> bool { self.is_empty() }
1173    fn contains_key(&self, key: &Self::K) -> bool { self.contains(key) }
1174    fn insert(&mut self, key: Self::K, _val: Self::V) { self.insert(key); }
1175    fn get(&self, key: &Self::K) -> Option<&Self::V> { self.get(key).map(|_| &()) }
1176    fn replace(&mut self, key: &Self::K, _val: Self::V) { debug_assert!(self.contains(key)); /* a noop since we can assume the key already exists */ }
1177    fn remove(&mut self, key: &Self::K) { self.remove(key); }
1178    fn iter<'a>(&'a self) -> Self::Iter<'a> { HashSetIterWrapper(self.iter()) }
1179    fn shrink_to_fit(&mut self) { self.shrink_to_fit(); }
1180}
1181
1182pub struct HashSetIterWrapper<'a, K> (std::collections::hash_set::Iter<'a, K>);
1183
1184impl<'a, K> Iterator for HashSetIterWrapper<'a, K> {
1185    type Item = (&'a K, &'a());
1186    fn next(&mut self) -> Option<(&'a K, &'a())> {
1187        self.0.next().map(|key| (key, &()))
1188    }
1189}
1190
1191set_lattice!(HashSet<K>);
1192set_dist_lattice!(HashSet<K>);
1193
1194#[cfg(test)]
1195mod tests {
1196    use std::collections::{HashSet, HashMap};
1197    use crate::ring::Lattice;
1198    use super::{AlgebraicResult, SetLattice, SELF_IDENT, COUNTER_IDENT};
1199
1200    #[test]
1201    fn set_lattice_join_test1() {
1202        let mut a = HashSet::new();
1203        let mut b = HashSet::new();
1204
1205        //Test None result
1206        let joined_result = a.pjoin(&b);
1207        assert_eq!(joined_result, AlgebraicResult::None);
1208
1209        //Straightforward join
1210        a.insert("A");
1211        b.insert("B");
1212        let joined_result = a.pjoin(&b);
1213        assert!(joined_result.is_element());
1214        let joined = joined_result.unwrap([&a, &b]);
1215        assert_eq!(joined.len(), 2);
1216        assert!(joined.get("A").is_some());
1217        assert!(joined.get("B").is_some());
1218
1219        //Make "self" contain more entries
1220        a.insert("C");
1221        let joined_result = a.pjoin(&b);
1222        assert!(joined_result.is_element());
1223        let joined = joined_result.unwrap([&a, &b]);
1224        assert_eq!(joined.len(), 3);
1225
1226        //Make "other" contain more entries
1227        b.insert("D");
1228        b.insert("F");
1229        b.insert("H");
1230        let joined_result = a.pjoin(&b);
1231        assert!(joined_result.is_element());
1232        let joined = joined_result.unwrap([&a, &b]);
1233        assert_eq!(joined.len(), 6);
1234
1235        //Test identity with self arg
1236        let joined_result = joined.pjoin(&b);
1237        assert_eq!(joined_result, AlgebraicResult::Identity(SELF_IDENT));
1238
1239        //Test identity with other arg
1240        let joined_result = b.pjoin(&joined);
1241        assert_eq!(joined_result, AlgebraicResult::Identity(COUNTER_IDENT));
1242
1243        //Test mutual identity
1244        let joined_result = joined.pjoin(&joined);
1245        assert_eq!(joined_result, AlgebraicResult::Identity(SELF_IDENT | COUNTER_IDENT));
1246    }
1247
1248    #[test]
1249    fn set_lattice_meet_test1() {
1250        let mut a = HashSet::new();
1251        let mut b = HashSet::new();
1252
1253        //Test disjoint result
1254        a.insert("A");
1255        b.insert("B");
1256        let meet_result = a.pmeet(&b);
1257        assert_eq!(meet_result, AlgebraicResult::None);
1258
1259        //Straightforward meet
1260        a.insert("A");
1261        a.insert("C");
1262        b.insert("B");
1263        b.insert("C");
1264        let meet_result = a.pmeet(&b);
1265        assert!(meet_result.is_element());
1266        let meet = meet_result.unwrap([&a, &b]);
1267        assert_eq!(meet.len(), 1);
1268        assert!(meet.get("A").is_none());
1269        assert!(meet.get("B").is_none());
1270        assert!(meet.get("C").is_some());
1271
1272        //Make "self" contain more entries
1273        a.insert("D");
1274        let meet_result = a.pmeet(&b);
1275        assert!(meet_result.is_element());
1276        let meet = meet_result.unwrap([&a, &b]);
1277        assert_eq!(meet.len(), 1);
1278
1279        //Make "other" contain more entries
1280        b.insert("D");
1281        b.insert("E");
1282        b.insert("F");
1283        let meet_result = a.pmeet(&b);
1284        assert!(meet_result.is_element());
1285        let meet = meet_result.unwrap([&a, &b]);
1286        assert_eq!(meet.len(), 2);
1287
1288        //Test identity with self arg
1289        let meet_result = meet.pmeet(&b);
1290        assert_eq!(meet_result, AlgebraicResult::Identity(SELF_IDENT));
1291
1292        //Test identity with other arg
1293        let meet_result = b.pmeet(&meet);
1294        assert_eq!(meet_result, AlgebraicResult::Identity(COUNTER_IDENT));
1295
1296        //Test mutual identity
1297        let meet_result = meet.pmeet(&meet);
1298        assert_eq!(meet_result, AlgebraicResult::Identity(SELF_IDENT | COUNTER_IDENT));
1299    }
1300
1301    /// Used in [set_lattice_join_test2] and [set_lattice_meet_test2]
1302    #[derive(Clone, Debug)]
1303    struct Map<'a>(HashMap::<&'a str, HashMap<&'a str, ()>>);// TODO, should be struct Map<'a>(HashMap::<&'a str, Map<'a>>); see comment above about chalk
1304    impl<'a> SetLattice for Map<'a> {
1305        type K = &'a str;
1306        type V = HashMap<&'a str, ()>; //Option<Box<Map<'a>>>; TODO, see comment above about chalk
1307        type Iter<'it> = std::collections::hash_map::Iter<'it, Self::K, Self::V> where Self: 'it, Self::K: 'it, Self::V: 'it;
1308        fn with_capacity(capacity: usize) -> Self { Map(HashMap::with_capacity(capacity)) }
1309        fn len(&self) -> usize { self.0.len() }
1310        fn is_empty(&self) -> bool { self.0.is_empty() }
1311        fn contains_key(&self, key: &Self::K) -> bool { self.0.contains_key(key) }
1312        fn insert(&mut self, key: Self::K, val: Self::V) { self.0.insert(key, val); }
1313        fn get(&self, key: &Self::K) -> Option<&Self::V> { self.0.get(key) }
1314        fn replace(&mut self, key: &Self::K, val: Self::V) { self.0.replace(key, val) }
1315        fn remove(&mut self, key: &Self::K) { self.0.remove(key); }
1316        fn iter<'it>(&'it self) -> Self::Iter<'it> { self.0.iter() }
1317        fn shrink_to_fit(&mut self) { self.0.shrink_to_fit(); }
1318    }
1319    set_lattice!(Map<'a>);
1320
1321    #[test]
1322    /// Tests a HashMap containing more HashMaps
1323    //TODO: When the [chalk trait solver](https://github.com/rust-lang/chalk) lands in stable rust, it would be nice
1324    // to promote this test to sample code and implement an arbitrarily deep recursive structure.  But currently
1325    // that's not worth the complexity due to limits in the stable rust trait sovler.
1326    fn set_lattice_join_test2() {
1327        let mut a = Map::with_capacity(1);
1328        let mut b = Map::with_capacity(1);
1329
1330        // Top level join
1331        let mut inner_map_1 = HashMap::with_capacity(1);
1332        inner_map_1.insert("1", ());
1333        a.0.insert("A", inner_map_1.clone());
1334        b.0.insert("B", inner_map_1);
1335        // b.0.insert("C", HashMap::new()); TODO: We might want to test collapse of empty items using the is_bottom() method
1336        let joined_result = a.pjoin(&b);
1337        assert!(joined_result.is_element());
1338        let joined = joined_result.unwrap([&a, &b]);
1339        assert_eq!(joined.len(), 2);
1340        assert!(joined.get(&"A").is_some());
1341        assert!(joined.get(&"B").is_some());
1342        assert!(joined.get(&"C").is_none()); //Empty sub-sets should not be merged
1343
1344        // Two level join, results should be Element even though the key existed in both args, because the values joined
1345        let mut inner_map_2 = HashMap::with_capacity(1);
1346        inner_map_2.insert("2", ());
1347        b.0.remove("B");
1348        b.0.insert("A", inner_map_2);
1349        let joined_result = a.pjoin(&b);
1350        assert!(joined_result.is_element());
1351        let joined = joined_result.unwrap([&a, &b]);
1352        assert_eq!(joined.len(), 1);
1353        let joined_inner = joined.get(&"A").unwrap();
1354        assert_eq!(joined_inner.len(), 2);
1355        assert!(joined_inner.get(&"1").is_some());
1356        assert!(joined_inner.get(&"2").is_some());
1357
1358        // Redoing the join should yield Identity
1359        let joined_result = joined.pjoin(&a);
1360        assert_eq!(joined_result.identity_mask().unwrap(), SELF_IDENT);
1361        let joined_result = b.pjoin(&joined);
1362        assert_eq!(joined_result.identity_mask().unwrap(), COUNTER_IDENT);
1363    }
1364
1365    #[test]
1366    /// Tests a HashMap containing more HashMaps.  See comments on [set_lattice_join_test2]
1367    fn set_lattice_meet_test2() {
1368        let mut a = Map::with_capacity(1);
1369        let mut b = Map::with_capacity(1);
1370
1371        let mut inner_map_a = HashMap::new();
1372        inner_map_a.insert("a", ());
1373        let mut inner_map_b = HashMap::new();
1374        inner_map_b.insert("b", ());
1375        let mut inner_map_c = HashMap::new();
1376        inner_map_c.insert("c", ());
1377
1378        // One level meet
1379        a.0.insert("A", inner_map_a.clone());
1380        a.0.insert("C", inner_map_c.clone());
1381        b.0.insert("B", inner_map_b.clone());
1382        b.0.insert("C", inner_map_c.clone());
1383        let meet_result = a.pmeet(&b);
1384        assert!(meet_result.is_element());
1385        let meet = meet_result.unwrap([&a, &b]);
1386        assert_eq!(meet.len(), 1);
1387        assert!(meet.get(&"A").is_none());
1388        assert!(meet.get(&"B").is_none());
1389        assert!(meet.get(&"C").is_some());
1390
1391        // Two level meet, results should be None even though the key existed in both args, because the inner values don't overlap
1392        let mut inner_map_1 = HashMap::with_capacity(1);
1393        inner_map_1.insert("1", ());
1394        a.0.insert("A", inner_map_1);
1395        let mut inner_map_2 = HashMap::with_capacity(1);
1396        inner_map_2.insert("2", ());
1397        b.0.remove("B");
1398        b.0.remove("C");
1399        b.0.insert("A", inner_map_2.clone());
1400        let meet_result = a.pmeet(&b);
1401        assert!(meet_result.is_none());
1402
1403        // Two level meet, now should return Element, because the values have some overlap
1404        inner_map_2.insert("1", ());
1405        b.0.insert("A", inner_map_2);
1406        let meet_result = a.pmeet(&b);
1407        assert!(meet_result.is_element());
1408        let meet = meet_result.unwrap([&a, &b]);
1409        assert_eq!(meet.len(), 1);
1410        let meet_inner = meet.get(&"A").unwrap();
1411        assert_eq!(meet_inner.len(), 1);
1412        assert!(meet_inner.get(&"1").is_some());
1413        assert!(meet_inner.get(&"2").is_none());
1414
1415        // Redoing the meet should yield Identity
1416        let meet_result = meet.pmeet(&a);
1417        assert_eq!(meet_result.identity_mask().unwrap(), SELF_IDENT);
1418        let meet_result = b.pmeet(&meet);
1419        assert_eq!(meet_result.identity_mask().unwrap(), COUNTER_IDENT);
1420    }
1421}
1422
1423//GOAT, do a test for the HashMap impl of psubtract
1424//GOAT, do an impl of SetLattice for Vec as an indexed set
1425
1426
1427//GOAT, LatticeCounter and LatticeBitfield should be traits.
1428// BitfieldLattice should be implemented on bool
1429// Make monad types that can implement these traits on all prim types
1430// Make a "convertable_to" trait across all prim types
1431
1432// GOAT, TEST TODO:  A fuzz test for some of the algebraic operations (join, meet, subtract) across all
1433// different path configurations and operation orderings.
1434
1435// Envisioned Implementation:
1436// 1. Create `set_a` of N values (e.g. integers 0..100) and assign a pseudorandom path to each element
1437// 2. Create `set_b` of M values and assign a different pseudorandom path to each element
1438// 3. Compose pseudorandom subsets of `set_a` and `set_b` and put them into HashSets
1439// 4. Put corresponding concatenated paths (Cartesian product) into PathMaps.
1440// 5. Select an operation to perform, and do the same operation to both the HashSets contining simple
1441//   indices and to the PathMaps.  And validate the results match
1442// 6. Loop back to 3, continuing to choose additional subsets to perform additional operations.
1443
1444// The reason behind the cartesian product (concatenated paths) is because the chances of getting overlap
1445//  beyond the first couple bytes of a random path are very slim.  So the Cartesian product appraoch
1446//  means we are likely to get large common prefixes followed by splits deep in the trie, which will
1447//  exercise the code more thoroughly.
pathmap/ring.rs

pathmap/
ring.rs
