furtif_core/traits/structures/lattice/
mod.rs

1// This program is free software: you can redistribute it and/or modify
2// it under the terms of the Lesser GNU General Public License as published
3// by the Free Software Foundation, either version 3 of the License, or
4// (at your option) any later version.
5
6// This program is distributed in the hope that it will be useful,
7// but WITHOUT ANY WARRANTY; without even the implied warranty of
8// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
9// Lesser GNU General Public License for more details.
10
11// You should have received a copy of the Lesser GNU General Public License
12// along with this program.  If not, see <https://www.gnu.org/licenses/>.
13
14// Copyright 2024 Frederic Dambreville, Jean Dezert Developers.
15
16
17use std::{ rc::Rc, sync::Arc, hash::Hash, collections::HashMap, };
18use hashed_type_def::HashedTypeDef;
19use rand::prelude::*;
20// #[cfg(not(feature = "silx-types"))] use crate::fake_slx::{u128slx, FakeSlx};
21// #[cfg(feature = "silx-types")] use silx_types::{ u128slx, IntoSlx, Float, };
22
23#[cfg(feature = "silx-types")] use silx_types::Float;
24
25use crate::{ 
26    types::{ u128slx, IntoSlx, },
27    structs::{
28        SafeElement, AssignmentBuilder, Assignment, hidden, 
29        ASSIGNMENT_EPSILON, one_f64slx, zero_f64slx, 
30    }, 
31    traits::CollectionFamily1, 
32};
33
34/// General trait for lattices
35pub trait Lattice: Sized {
36    /// Type for encoding lattice elements: 
37    ///   * type `Self::Item` may contain element which are not in the lattice
38    ///   * type `SafeElement<Self::Item>` contains both the element and the hash of lattice in order to assert its origin:
39    ///     * `SafeElement<Self::Item>` is only produced by method `check_safe` which control if raw element is within the lattice
40    ///     * `SafeElement<Self::Item>`  or `SafeCollection<Self::Item,I>` contains checked elements; 
41    ///     * Safe elements are helper, but in last ressort, the user is responsible to ensure the data validity
42    type Item: Clone + Eq + HashedTypeDef; 
43
44    /// Random lattice generator (for tests)
45    /// * `rng: &mut R` : random number generator
46    /// * `R: Rng` : type of random number generator
47    /// * Output: random lattice
48    fn rand_lattice<R: Rng>(rng: &mut R) -> Self;
49
50    /// Random element generator (for tests); elements are built safe
51    /// * `rng: &mut R` : random number generator
52    /// * `R: Rng` : type of random number generator
53    /// * Output: random element
54    fn rand_element<R: Rng>(&self, rng: &mut R) -> SafeElement<Self::Item>;
55
56    /// Reference to lattice hash
57    fn ref_lattice_hash(&self) -> &u128slx;
58
59    /// Test if element is from lattice
60    /// * this is necessary since type Self::Item may contain more potential elements than the lattice 
61    /// * `element: &Self::Item` : element to be tested
62    /// * Output: boolean
63    fn contains(&self, element: &Self::Item) -> bool;
64
65    /// Reference to least element of the lattice
66    /// * Output: reference to least element
67    fn ref_bottom(&self) -> &SafeElement<Self::Item>;
68
69    /// Reference to greatest element of the lattice
70    /// * Output: reference to greatest element
71    fn ref_top(&self) -> &SafeElement<Self::Item>;
72        
73    /// Unsafe greatest lower bound
74    /// * values are not tested to be within lattice.
75    /// * contract: operator should be associative
76    /// * `element_left: &Self::Item` : left operand
77    /// * `element_right: &Self::Item` : right operand
78    /// * Output: unsafe greatest lower bound
79    unsafe fn unsafe_meet(&self, element_left: &Self::Item, element_right: &Self::Item) -> Self::Item;
80
81    /// Unsafe least upper bound
82    /// * values are not tested to be within lattice.
83    /// * contract: operator should be associative!
84    /// * `element_left: &Self::Item` : left operand
85    /// * `element_right: &Self::Item` : right operand
86    /// * Output: unsafe least upper bound
87    unsafe fn unsafe_join(&self, element_left: &Self::Item, element_right: &Self::Item) -> Self::Item;
88
89    /// Parse safe element from str
90    /// * `s: &str` : string to be parsed
91    /// * Output: parsed safe element or error
92    fn from_str(&self, s: &str) -> Result<SafeElement<Self::Item>,String>;
93
94    /// Format safe element into String
95    /// * `element: &SafeElement<Self::Item>` : safe element to be formated into string
96    /// * Output: formated string or error
97    fn to_string(&self, element: &SafeElement<Self::Item>) -> Result<String,String>; 
98    
99    /// Lattice hash
100    /// * Output: lattice hash
101    fn lattice_hash(&self) -> u128slx { *self.ref_lattice_hash() }
102
103    /// Least element of the lattice
104    /// * Output: least element of the lattice
105    fn bottom(&self) -> SafeElement<Self::Item> { self.ref_bottom().clone() }
106
107    /// Greatest element of the lattice
108    /// * Output: greatest element of the lattice
109    fn top(&self) -> SafeElement<Self::Item> { self.ref_top().clone() }
110
111    /// Is safe element the least element of the lattice?
112    /// * `safe_element: &SafeElement<Self::Item>` : safe element
113    /// * Output: boolean or error
114    fn is_bottom(&self, safe_element: &SafeElement<Self::Item>) -> Result<bool, String> {
115        match (safe_element,self.ref_bottom()) {
116            (
117                SafeElement { code: element, lattice_hash },
118                SafeElement { code: bottom, lattice_hash: self_hash }
119            ) if lattice_hash == self_hash => Ok(element == bottom),
120            _ => Err("element is not within lattice".to_string()),
121        }
122    }
123
124    /// Is safe element the greatest element of the lattice?
125    /// * `safe_element: &SafeElement<Self::Item>` : safe element
126    /// * Output: boolean or error
127    fn is_top(&self, safe_element: &SafeElement<Self::Item>) -> Result<bool, String> {
128        match (safe_element,self.ref_top()) {
129            (
130                SafeElement { code: element, lattice_hash },
131                SafeElement { code: top, lattice_hash: self_hash }
132            ) if lattice_hash == self_hash => Ok(element == top),
133            _ => Err("element is not within lattice".to_string()),
134        }
135    }
136    
137    /// Is unsafe element the least element of the lattice?
138    /// * `element: &Self::Item` : unsafe element
139    /// * Output: boolean or error
140    unsafe fn unsafe_is_bottom(&self, element: &Self::Item) -> bool {
141        element == &self.ref_bottom().code
142    }
143
144    /// Is unsafe element the greatest element of the lattice?
145    /// * `element: &Self::Item` : unsafe element
146    /// * Output: boolean or error
147    unsafe fn unsafe_is_top(&self, element: &Self::Item) -> bool {
148        element == &self.ref_top().code
149    }
150    
151    /// Greatest lower bound
152    /// * `left: &SafeElement<Self::Item>` : left operand
153    /// * `right: &SafeElement<Self::Item>` : right operand
154    /// * Output: greatest lower bound or error
155    #[inline] fn meet(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<SafeElement<Self::Item>, String> {
156        let SafeElement { code: element_left, lattice_hash: lattice_hash_left, } = left;
157        let SafeElement { code: element_right, lattice_hash: lattice_hash_right, } = right;
158        let lattice_hash = self.ref_lattice_hash();
159        match (lattice_hash_left == lattice_hash, lattice_hash_right == lattice_hash) {
160            (true,true) => Ok(
161                SafeElement { code: unsafe { self.unsafe_meet(element_left,element_right) }, lattice_hash: *lattice_hash, }
162            ),
163            (false,true) => Err("left is not within lattice".to_string()),
164            (true,false) => Err("right is not within lattice".to_string()),
165            (false,false) => Err("entries are not within lattice".to_string()),
166        }
167    }
168
169    /// Greatest lower bound of a collection
170    /// * `it: I` : collection of safe elements
171    /// * `I` : type of collection
172    /// * Output: greatest lower bound or error
173    #[inline] fn meet_some<'a, I>(&self, it: I) -> Result<SafeElement<Self::Item>, String>
174                                    where I: IntoIterator<Item=&'a SafeElement<Self::Item>>, Self: 'a {
175        let SafeElement { code: mut cumul, lattice_hash: self_hash } = self.top();
176        for (idx,SafeElement { code: element, lattice_hash }) in it.into_iter().enumerate() {
177            if *lattice_hash == self_hash {
178                cumul = unsafe { self.unsafe_meet(&cumul,element) };
179            } else { return Err(format!("element at index {idx} is not within lattice")); }
180        }
181        Ok(SafeElement { code: cumul, lattice_hash: self_hash })
182    }
183
184    /// Least upper bound
185    /// * `left: &SafeElement<Self::Item>` : left operand
186    /// * `right: &SafeElement<Self::Item>` : right operand
187    /// * Output: least upper bound or error
188    fn join(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<SafeElement<Self::Item>, String> {
189        let SafeElement { code: element_left, lattice_hash: lattice_hash_left, } = left;
190        let SafeElement { code: element_right, lattice_hash: lattice_hash_right, } = right;
191        let lattice_hash = self.ref_lattice_hash();
192        match (lattice_hash_left == lattice_hash, lattice_hash_right == lattice_hash) {
193            (true,true) => Ok(
194                SafeElement { code: unsafe { self.unsafe_join(element_left,element_right) }, lattice_hash: *lattice_hash, }
195            ),
196            (false,true) => Err("left is not within lattice".to_string()),
197            (true,false) => Err("right is not within lattice".to_string()),
198            (false,false) => Err("entries are not within lattice".to_string()),
199        }
200    }
201
202    /// Least upper bound of a collection
203    /// * `it: I` : collection of safe elements
204    /// * `I` : type of collection
205    /// * Output: least upper bound or error
206    fn join_some<'a, I>(&self, it: I) -> Result<SafeElement<Self::Item>, String>
207                            where I: IntoIterator<Item=&'a SafeElement<Self::Item>>, Self: 'a {
208        let SafeElement { code: mut cumul, lattice_hash: self_hash } = self.bottom();
209        for (idx,SafeElement { code: element, lattice_hash }) in it.into_iter().enumerate() {
210            if *lattice_hash == self_hash {
211                cumul = unsafe { self.unsafe_join(&cumul,element) };
212            } else { return Err(format!("element at index {idx} is not within lattice")); }
213        }
214        Ok(SafeElement { code: cumul, lattice_hash: self_hash })
215    }
216
217    /// Check if unsafe element is in lattice and then build safe element
218    /// * `element: T` : unsafe element
219    /// * `T` : type of unsafe element; actually any type which implement `Into<Self::Item>`
220    /// * Output: safe element or error
221    fn check_safe<T>(&self, element: T) -> Result<SafeElement<Self::Item>, String> where T: Into<Self::Item> {
222        let element: Self::Item = element.into();
223        if self.contains(&element) { 
224            Ok(SafeElement { code: element, lattice_hash: self.lattice_hash(), }) 
225        } else { Err("lattice does not contain element".to_string()) }
226    }
227
228    /// Elements collection generator (for tests); elements are built safe
229    /// * `len: usize` : size of the collection
230    /// * `rng: &mut R` : random number generator
231    /// * `R: Rng` : type of random number generator
232    /// * `I` : type of collection
233    /// * Output: collection of random safe elements 
234    fn rand_elements<R: Rng,I>(&self, len: usize, rng: &mut R) -> I::Type<SafeElement<Self::Item>> where I: CollectionFamily1 {
235        (0..len).map(|_| self.rand_element(rng)).collect()
236    }
237
238    /// Init a new assignment builder
239    /// * Output: empty assignment builder
240    fn assignment(&self,) -> AssignmentBuilder<Self::Item> where Self::Item: Eq + Ord + Hash, {
241        let elements = hidden::OrdMap::new();
242        AssignmentBuilder { elements, lattice_hash: self.lattice_hash(), length_mid: u32::MAX.slx(), length_max: u32::MAX.slx() }
243    }
244
245    /// Init a new assignment builder with capacity
246    /// * `capacity: usize` : capacity
247    /// * Output: empty assignment builder with capacity `capacity`
248    fn assignment_with_capacity(&self, capacity: usize) -> AssignmentBuilder<Self::Item> where Self::Item: Eq + Ord + Hash, {
249        let elements = hidden::OrdMap::with_capacity(capacity);
250        AssignmentBuilder { elements, lattice_hash: self.lattice_hash(), length_mid: u32::MAX.slx(), length_max: u32::MAX.slx() }
251    }
252
253    /// Init a new prunable assignment builder
254    /// * `length_mid: u32slx` : max size of pruned assignment
255    /// * `length_max: u32slx` : max size of assignment
256    /// * Output: empty assignment builder
257    fn prunable(&self, length_mid: u32, length_max: u32,) -> AssignmentBuilder<Self::Item> where Self::Item: Eq + Ord + Hash, {
258        let elements = hidden::OrdMap::new();
259        AssignmentBuilder { elements, lattice_hash: self.lattice_hash(), length_mid: length_mid.slx(), length_max: length_max.slx() }
260    }
261
262    /// Init a new prunable assignment builder with capacity
263    /// * `length_mid: u32slx` : max size of pruned assignment
264    /// * `length_max: u32slx` : max size of assignment
265    /// * `capacity: usize` : capacity
266    /// * Output: empty assignment builder with capacity `capacity`
267    fn prunable_with_capacity(&self, length_mid: u32, length_max: u32, capacity: usize)
268                                                                -> AssignmentBuilder<Self::Item> where Self::Item: Eq + Ord + Hash, {
269        let elements = hidden::OrdMap::with_capacity(capacity);
270        AssignmentBuilder { elements, lattice_hash: self.lattice_hash(), length_mid: length_mid.slx(), length_max: length_max.slx() }
271    }
272
273    /// Unsafe test if left and right cover top, ie. union of left and right is top
274    /// * `left: &Self::Item` : left operand
275    /// * `right: &Self::Item` : right operand
276    /// * Output: boolean
277    #[inline] unsafe fn unsafe_cover(&self, left: &Self::Item, right: &Self::Item) -> bool {
278        &self.unsafe_join(left,right) == &self.ref_top().code
279    }
280
281    /// Unsafe test if left and right are disjoint
282    /// * `left: &Self::Item` : left operand
283    /// * `right: &Self::Item` : right operand
284    /// * Output: boolean
285    #[inline] unsafe fn unsafe_disjoint(&self, left: &Self::Item, right: &Self::Item) -> bool {
286        &self.unsafe_meet(left,right) == &self.ref_bottom().code
287    }
288
289    /// Unsafe test if left implies (i.e. is contained by) right
290    /// * should be equivalent to implies_meet
291    /// * `left: &Self::Item` : left operand
292    /// * `right: &Self::Item` : right operand
293    /// * Output: boolean
294    #[inline] unsafe fn unsafe_implies_join(&self, left: &Self::Item, right: &Self::Item) -> bool {
295        &self.unsafe_join(left,right) == right
296    }
297
298    /// Unsafe test if left is implied by (i.e. contains) right
299    /// * should be equivalent to implied_meet
300    /// * `left: &Self::Item` : left operand
301    /// * `right: &Self::Item` : right operand
302    /// * Output: boolean
303    #[inline] unsafe fn unsafe_implied_join(&self, left: &Self::Item, right: &Self::Item) -> bool {
304        &self.unsafe_join(left,right) == left
305    }
306    
307    /// Unsafe test if left implies (i.e. is contained by) right
308    /// * should be equivalent to implies_join
309    /// * `left: &Self::Item` : left operand
310    /// * `right: &Self::Item` : right operand
311    /// * Output: boolean
312    #[inline] unsafe fn unsafe_implies_meet(&self, left: &Self::Item, right: &Self::Item) -> bool {
313        &self.unsafe_meet(left,right) == left
314    }
315
316    /// Unsafe test if left is implied by (i.e. contains) right
317    /// * should be equivalent to implied_joint
318    /// * `left: &Self::Item` : left operand
319    /// * `right: &Self::Item` : right operand
320    /// * Output: boolean
321    #[inline] unsafe fn unsafe_implied_meet(&self, left: &Self::Item, right: &Self::Item) -> bool {
322        &self.unsafe_meet(left,right) == right
323    }
324
325    /// Test if left and right cover top, ie. union of left and right is top
326    /// * `left: &SafeElement<Self::Item>` : left operand
327    /// * `right: &SafeElement<Self::Item>` : right operand
328    /// * Output: boolean or error
329    #[inline] fn cover(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<bool, String> {
330        Ok(&self.join(left,right)? == self.ref_top())
331    }
332
333    /// Test if left and right are disjoint
334    /// * `left: &SafeElement<Self::Item>` : left operand
335    /// * `right: &SafeElement<Self::Item>` : right operand
336    /// * Output: boolean or error
337    #[inline] fn disjoint(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<bool, String> {
338        Ok(&self.meet(left,right)? == self.ref_bottom())
339    }
340
341    /// Test if left implies (i.e. is contained by) right
342    /// * should be equivalent to implies_meet
343    /// * `left: &SafeElement<Self::Item>` : left operand
344    /// * `right: &SafeElement<Self::Item>` : right operand
345    /// * Output: boolean or error
346    #[inline] fn implies_join(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<bool, String> {
347        Ok(&self.join(left,right)? == right)
348    }
349
350    /// Test if left is implied by (i.e. contains) right
351    /// * should be equivalent to implied_meet
352    /// * `left: &SafeElement<Self::Item>` : left operand
353    /// * `right: &SafeElement<Self::Item>` : right operand
354    /// * Output: boolean or error
355    #[inline] fn implied_join(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<bool, String> {
356        Ok(&self.join(left,right)? == left)
357    }
358    
359    /// Test if left implies (i.e. is contained by) right
360    /// * should be equivalent to implies_join
361    /// * `left: &SafeElement<Self::Item>` : left operand
362    /// * `right: &SafeElement<Self::Item>` : right operand
363    /// * Output: boolean or error
364    #[inline] fn implies_meet(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<bool, String> {
365        Ok(&self.meet(left,right)? == left)
366    }
367
368    /// Test if left is implied by (i.e. contains) right
369    /// * should be equivalent to implied_joint
370    /// * `left: &SafeElement<Self::Item>` : left operand
371    /// * `right: &SafeElement<Self::Item>` : right operand
372    /// * Output: boolean or error
373    #[inline] fn implied_meet(&self, left: &SafeElement<Self::Item>, right: &SafeElement<Self::Item>) -> Result<bool, String> {
374        Ok(&self.meet(left,right)? == right)
375    }
376}
377
378/// General trait for complemented lattices
379/// * such lattices have logical negation
380pub trait ComplementedLattice: Lattice {
381    /// Unsafe logical negation
382    /// * contract: not has to be bijective, be equal to its inverse, and has to check de Morgan's law
383    /// * i.e. double not is identity and not of meet is join of not
384    /// * this is unsafe: value is not tested to be within lattice
385    /// * `element: &Self::Item` : unsafe element
386    /// * Output: logical negation of unsafe element
387    unsafe fn unsafe_not(&self, element: &Self::Item) -> Self::Item;
388
389    /// Logical negation
390    /// * `safe_element: &SafeElement<Self::Item>` : safe element
391    /// * Output: logical negation of safe element
392    fn not(&self, safe_element: &SafeElement<Self::Item>) -> Result<SafeElement<Self::Item>, String> {
393        let SafeElement { code: element, lattice_hash, } = safe_element;
394        let lattice_hash = * lattice_hash;
395        if self.lattice_hash() == lattice_hash { 
396            Ok(SafeElement { code: unsafe { self.unsafe_not(element) }, lattice_hash, }) 
397        } else { Err("element is not within lattice".to_string()) }
398    }
399
400    /// Compute the co-assignment of an assignment
401    /// * The following computation is done on the weighted elements of the assignment: `(e,w) -> (e.not(), 1 - w)`
402    /// * `assignment: &Assignment<Self::Item>` : assigment
403    /// * Output: co-assignment
404    fn co_assignment(&self, assignment: &Assignment<Self::Item>) -> Result<Assignment<Self::Item>, String> 
405                                                                                        where Self::Item: Ord + Hash, {
406        let Assignment { lattice_hash, .. } = *assignment;
407        let Assignment { elements, .. } = assignment;
408        if self.lattice_hash() == lattice_hash {
409            let eps = ASSIGNMENT_EPSILON.slx();
410            let one = *one_f64slx();
411            let zero = *zero_f64slx();
412            let mut co_assignment = HashMap::with_capacity(elements.len());
413            for (element, weight) in elements {
414                if *weight - one > eps { return Err(format!("assigned weight {weight} is greater than 1.0")); }
415                co_assignment.insert(unsafe { self.unsafe_not(element) }, (one - *weight).max(zero));
416            }    
417            Ok(Assignment { elements: co_assignment, lattice_hash }) 
418        } else { Err("assignment is not within lattice".to_string()) }
419    }
420}
421
422macro_rules! impl_as_ref {
423    ($($ty: ident,)*) => {
424        $(
425            impl<L> Lattice for $ty<L> where L: Lattice, {
426                type Item = L::Item;
427                fn rand_lattice<R: Rng>(rng: &mut R) -> Self { $ty::new(L::rand_lattice(rng)) }
428                fn rand_element<R: Rng>(&self, rng: &mut R) -> SafeElement<Self::Item> { 
429                    let SafeElement { code, lattice_hash } = self.as_ref().rand_element(rng);
430                    SafeElement { code, lattice_hash, }
431                }
432                fn ref_lattice_hash(&self) -> &u128slx { self.as_ref().ref_lattice_hash() }
433                fn contains(&self, element: &Self::Item) -> bool { self.as_ref().contains(element) }
434                fn ref_bottom(&self) -> &SafeElement<Self::Item> { self.as_ref().ref_bottom() }
435                fn ref_top(&self) -> &SafeElement<Self::Item> { self.as_ref().ref_top() }
436                unsafe fn unsafe_meet(&self, element_left: &Self::Item, element_right: &Self::Item) -> Self::Item {
437                    self.as_ref().unsafe_meet(element_left, element_right)
438                }
439                unsafe fn unsafe_join(&self, element_left: &Self::Item, element_right: &Self::Item) -> Self::Item {
440                    self.as_ref().unsafe_join(element_left, element_right)
441                }
442                fn from_str(&self, s: &str) -> Result<SafeElement<Self::Item>,String> {
443                    self.as_ref().from_str(s)
444                }
445                fn to_string(&self, element: &SafeElement<Self::Item>,) -> Result<String,String> {
446                    self.as_ref().to_string(element,)
447                } 
448            }
449        )*
450    };
451}
452
453impl_as_ref!(Arc,Rc,Box,);
furtif_core/traits/structures/lattice/mod.rs

furtif_core/traits/structures/lattice/
mod.rs
