furtif_core/structs/structures/lattice/
powerset.rs

1use std::{ 
2    collections::{ HashMap, BTreeMap, hash_map, }, vec,
3};
4use core::fmt::Debug;
5
6use hashed_type_def::{ HashedTypeDef, add_hash_fnv1a, };
7// #[cfg(feature = "silx-types")] use silx_types::{ u128slx, IntoSlx, SlxInto, f64slx, };
8// #[cfg(not(feature = "silx-types"))] use crate::fake_slx::{ f64slx, u128slx, FakeSlx, };
9
10use crate::types::{ u128slx, f64slx, SlxInto, IntoSlx, };
11
12
13#[cfg(feature = "serde")] use serde::{Serialize as SerdeSerialize, Deserialize as SerdeDeserialize};
14#[cfg(feature = "rkyv")] use rkyv::{Archive, Serialize as RkyvSerialize, Deserialize as RkyvDeserialize};
15// This program is free software: you can redistribute it and/or modify
16// it under the terms of the Lesser GNU General Public License as published
17// by the Free Software Foundation, either version 3 of the License, or
18// (at your option) any later version.
19
20// This program is distributed in the hope that it will be useful,
21// but WITHOUT ANY WARRANTY; without even the implied warranty of
22// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23// Lesser GNU General Public License for more details.
24
25// You should have received a copy of the Lesser GNU General Public License
26// along with this program.  If not, see <https://www.gnu.org/licenses/>.
27
28// Copyright 2024 Frederic Dambreville, Jean Dezert Developers.
29
30
31use rand::prelude::*;
32
33use crate::{
34    traits::{ Lattice, ComplementedLattice, IterableLattice, LatticeWithLeaves }, 
35    structs::SafeElement,
36};
37
38const DEFAULT_MAX_ITER_LEN : usize = 1024;
39
40#[derive(Clone, Debug, HashedTypeDef)]
41#[cfg_attr(feature = "rkyv", derive(Archive,RkyvSerialize,RkyvDeserialize))]
42/// Powerset lattice
43pub struct Powerset {
44    max_iter_len: u128slx,
45    top: SafeElement<u128slx>,
46    bottom: SafeElement<u128slx>,
47    tags: BTreeMap<u128slx,String,>,
48    untags: HashMap<String,u128slx,>,
49    leaves: Vec<u128slx>,
50    weighted_leaves: HashMap<u128slx,f64slx>,
51    bottom_to_top: Option<Vec<u128slx>>,
52}
53
54// implementation of Serde serialization
55#[cfg(feature = "serde")] mod serding {
56    // #[cfg(feature = "silx-types")] use silx_types::SlxInto;
57    // #[cfg(not(feature = "silx-types"))] use crate::fake_slx::FakeSlx;
58
59    use super::{ 
60        Powerset as SerdingPowerset, SerdeSerialize, SerdeDeserialize, SlxInto,
61    };
62    #[derive(SerdeSerialize,SerdeDeserialize)]
63    pub struct Powerset {
64        nb_leaves: usize, max_iter_len: usize,
65    }
66    impl<'de> SerdeDeserialize<'de> for SerdingPowerset {
67        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
68        where D: serde::Deserializer<'de> {
69            let Powerset { nb_leaves, max_iter_len } = Powerset::deserialize(deserializer)?;
70            match SerdingPowerset::new(nb_leaves, max_iter_len) {
71                Ok(p) => Ok(p),
72                Err(_) => Ok(Self::empty()),
73            }
74        }
75    }
76    impl SerdeSerialize for SerdingPowerset {
77        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
78        where S: serde::Serializer {
79            let SerdingPowerset { max_iter_len, leaves, .. } = self;
80            let nb_leaves = leaves.len();
81            let max_iter_len = (*max_iter_len).unslx() as usize;
82            let powerset = Powerset { nb_leaves, max_iter_len };
83            powerset.serialize(serializer)
84        }
85    }
86}
87
88impl Powerset {
89    /// Powerset constructor
90    /// * Leaves labels are generated automatically
91    /// * `nb_leaves: usize` : number of leaves
92    /// * `max_iter_len: usize` : maximal size for an iterator on the powerset
93    /// * Output: the powerset or an error, when the number of leaves exceeds 128
94    pub fn new(nb_leaves: usize, max_iter_len: usize,) -> Result<Powerset,String> {
95        let leaves_names = (0..nb_leaves).map(|u| format!("U{u}")).collect::<Vec<_>>();
96        Self::new_with_label(&leaves_names, max_iter_len)
97    }
98    /// Powerset constructor with predefined leaves labels
99    /// * Leaves labels are provided
100    ///   * The labels should be different: if this condition is not met, this should not affect the computations, but it would make the results less readable
101    /// * `leaves_names: &[String]` : list of leaves described by their names
102    /// * `max_iter_len: usize` : maximal size for an iterator on the powerset
103    /// * Output: the powerset or an error, when the number of leaves exceeds 128
104    pub fn new_with_label(leaves_names: &[String], max_iter_len: usize,) -> Result<Powerset,String> {
105        let nb_leaves = leaves_names.len();
106        let s = std::mem::size_of::<u128>() << 3; // number of bits of usize
107        let top = match nb_leaves { //
108            m if m > s     => Err(format!("Number of leaves cannot excess {s}")), // nb of bits of u128 is exceeded
109            m if m == s    => Ok(u128::MAX.slx()),
110            m              => Ok(((1u128 << m)-1u128).slx()),
111        };
112        top.map(|top| {
113            let leaves: Vec<u128slx> = (0..nb_leaves).map(|rank|(1u128 << rank).slx()).collect::<Vec<_>>();
114            let (tags,untags) = leaves_names.iter().enumerate()
115                .map(|(rank,label)| ((leaves[rank],label.clone()),(label.clone(),leaves[rank])))
116                .unzip::<_,_,BTreeMap<_,_>,HashMap<_,_>>();
117            let unif: f64slx = (nb_leaves as f64).recip().slx();
118            let weighted_leaves = leaves.iter().map(|k| (*k,unif)).collect::<HashMap<_,_>>();
119            let mut sorted_tags = tags.iter().map(
120                |(u,s)| ((*u).unslx(),s)
121            ).collect::<Vec<_>>(); sorted_tags.sort_by_key(|(k,_)| *k);
122            let mut sorted_leaves = weighted_leaves.iter().map(
123                |(u,w)| ((*u).unslx(),(*w).unslx())
124            ).collect::<Vec<_>>(); sorted_leaves.sort_by_key(|(k,_)| *k);
125            let lattice_hash = {
126                let mut lattice_hash = Powerset::TYPE_HASH_NATIVE;
127                lattice_hash = add_hash_fnv1a(&nb_leaves.to_le_bytes(), lattice_hash);
128                for (u,s) in &sorted_tags {
129                    lattice_hash = add_hash_fnv1a(&(*u).to_le_bytes(), lattice_hash);
130                    lattice_hash = add_hash_fnv1a(s.as_bytes(), lattice_hash);
131                }
132                for (u,w) in &sorted_leaves {
133                    lattice_hash = add_hash_fnv1a(&(*u).to_le_bytes(), lattice_hash);
134                    lattice_hash = add_hash_fnv1a(&(*w).to_le_bytes(), lattice_hash);
135                }
136                lattice_hash.slx()
137            };
138            let max_iter_len = (max_iter_len as u128).slx();
139            let bottom = SafeElement { code: 0u128.slx(), lattice_hash, };
140            let top = SafeElement { code: top, lattice_hash, };
141            Powerset { bottom, top, leaves, weighted_leaves, tags, untags, max_iter_len, bottom_to_top: None, }
142        })
143    }
144
145    #[cfg(feature = "serde")] 
146    /// Internal use for serde: empty Powerset
147    fn empty() -> Powerset {
148        let zero = 0u128.slx();
149        let top = SafeElement{ code: zero, lattice_hash: zero };
150        let bottom = top;
151        Powerset {
152            max_iter_len: zero, top, bottom, tags: BTreeMap::new(), untags: HashMap::new(), 
153            leaves: Vec::new(), weighted_leaves: HashMap::new(), bottom_to_top: None,
154        }
155    }
156
157    /// Internal use: for building interator
158    fn build_double_sequence_up(&self) -> Vec<Vec<u128slx>> {
159        // sequence for nb_usize == 0 --> degenerated powerset
160        let mut double_sequence = vec![vec![0u128.slx()]];
161        for (n,(leaf,_)) in self.weighted_leaves.iter().enumerate() {
162            let mut next_ds = Vec::with_capacity(n+1);
163            next_ds.push(vec![0u128.slx()]);
164            for k in 0..n {
165                next_ds.push(double_sequence[k+1].iter().copied().chain(
166                    double_sequence[k].iter().copied().map(|u| u | *leaf)
167                ).collect());
168            }
169            next_ds.push(vec![double_sequence[n][0] | *leaf]);
170            double_sequence = next_ds;
171        }
172        double_sequence
173    }
174
175    /// Implement powerset iterators with a view to use methods `IterableLattice::unsafe_bottom_to_top` and `IterableLattice::unsafe_top_to_bottom`
176    /// * These iterators are not defined by the powerset constructor due to the amount of resources required for some large powersets
177    /// * Output: powerset implementing the iterators
178    pub fn set_iterators(mut self) -> Self {
179        if self.top.code < self.max_iter_len && self.bottom_to_top.is_none() {
180            self.bottom_to_top = Some(
181                self.build_double_sequence_up().into_iter().flat_map(|v|v).collect()
182            );
183        } self
184    }
185}
186
187impl Lattice for Powerset {
188    type Item = u128slx;
189
190    fn rand_lattice<R: Rng>(rng: &mut R) -> Self {
191        let nb_leaves = rng.gen_range(1..=(std::mem::size_of::<u128>() << 3));
192        Self::new(nb_leaves,DEFAULT_MAX_ITER_LEN).expect("unexpected: None returned")
193    }
194
195    fn rand_element<R: Rng>(&self, rng: &mut R) -> SafeElement<Self::Item> {
196        let SafeElement { code: top, lattice_hash } = self.top;
197        let top = top.unslx();
198        let element = rng.gen_range(0..=top).slx();
199        SafeElement { code: element, lattice_hash }
200    }
201
202    fn ref_lattice_hash(&self) -> &u128slx { &self.bottom.lattice_hash }
203
204    fn contains(&self, element: &Self::Item) -> bool { element <= &self.top.code }
205
206    fn ref_bottom(&self) -> &SafeElement<Self::Item> { &self.bottom }
207
208    fn ref_top(&self) -> &SafeElement<Self::Item> { &self.top }
209
210    unsafe fn unsafe_meet(&self, element_left: &Self::Item, element_right: &Self::Item) -> Self::Item {
211        *element_left & *element_right
212    }
213
214    unsafe fn unsafe_join(&self, element_left: &Self::Item, element_right: &Self::Item) -> Self::Item {
215        *element_left | *element_right
216    }
217
218    fn from_str(&self, s: &str) -> Result<SafeElement<Self::Item>,String> {
219        let tokens = s.split('|')
220                .map(|s| s.split_whitespace().fold(String::new(),|acc,u| {
221            if acc.is_empty() { u.to_string() } else { format!("{acc} {u}") }
222        }));
223        let SafeElement { code: mut element, lattice_hash } = self.bottom;
224        for token in tokens {
225            match (&token == "\u{22A5}",&token == "\u{22A4}") {
226                (true, true) => panic!("unexpected error: \u{22A5} == \u{22A4}"),
227                (true, false) => (), // case where token is bottom
228                (false, true) => element = self.top.code, // case where token is top
229                (false, false) => match self.untags.get(&token) {
230                    Some(l) => element |= *l,
231                    None => return Err(format!("leaf {token} is unknown")),
232                },
233            }
234        }
235        Ok(SafeElement { code: element, lattice_hash })
236    }
237
238    fn to_string(&self, element: &SafeElement<Self::Item>) -> Result<String,String> {
239        let SafeElement { code: element, lattice_hash } = element;
240        let element = *element;
241        if lattice_hash == &self.bottom.lattice_hash {
242            match (element == self.bottom.code,element == self.top.code) {
243                (true, true) => panic!("unexpected error: \u{22A5} == \u{22A4}"),
244                (true, false) => Ok("\u{22A5}".to_string()),
245                (false, true) => Ok("\u{22A4}".to_string()),
246                (false, false) => {
247                    Ok(self.tags.iter().filter(|(l,_)| { let l = **l; (element & l) == l } )
248                            .fold(String::new(), |acc,(_,s)| {
249                        if acc.is_empty() { s.to_string() } else { format!("{acc} | {s}") }
250                    }))
251                },
252            }
253        } else { Err("lattice does not contain element".to_string()) }
254    }
255}
256
257impl ComplementedLattice for Powerset {
258    unsafe fn unsafe_not(&self, element: &Self::Item) -> Self::Item { self.top.code ^ *element }
259}
260
261impl IterableLattice for Powerset {
262    type IntoIterUp = vec::IntoIter<u128slx>;
263
264    type IntoIterDown = vec::IntoIter<u128slx>;
265
266    unsafe fn unsafe_bottom_to_top(&self) -> Result<Self::IntoIterUp,String> {
267        match &self.bottom_to_top {
268            Some(btt) => Ok(btt.clone().into_iter()),
269            None => Err("Iterator is not set or is exceeding allowed size".to_string()),            
270        }
271    }
272
273    unsafe fn unsafe_top_to_bottom(&self) -> Result<Self::IntoIterDown,String> {
274        match &self.bottom_to_top {
275            Some(btt) => Ok(btt.iter().copied().rev().collect::<Vec<_>>().into_iter()),
276            None => Err("Iterator is not set or is exceeding allowed size".to_string()),            
277        }
278    }
279
280}
281
282impl LatticeWithLeaves for Powerset {
283    type IntoIterLeaves = hash_map::IntoIter<Self::Item, f64slx>;
284
285    unsafe fn unsafe_leaves(&self) -> Result<Self::IntoIterLeaves,String> {
286        let len_slx: u128slx = (self.weighted_leaves.len() as u128).slx();
287        if len_slx >= self.max_iter_len {
288            Err("Iterator is exceeding allowed size".to_string())
289        } else {
290            Ok(self.weighted_leaves.clone().into_iter())
291        }
292    }
293
294    unsafe fn unsafe_leaf(&self, u: usize) -> Result<&Self::Item,String> {
295        match self.leaves.get(u) {
296            Some(x) => Ok(x),
297            None => Err(format!("Leaf of index {u} is not found within lattice")),
298        }
299    }
300
301    unsafe fn unsafe_weighted_leaf(&self, u: usize) -> Result<(&Self::Item,&f64slx),String> {
302        let leaf = self.unsafe_leaf(u)?;
303        Ok((leaf,&self.weighted_leaves[leaf]))
304    }
305}
furtif_core/structs/structures/lattice/powerset.rs

furtif_core/structs/structures/lattice/
powerset.rs
