tor_basic_utils/
n_key_list.rs

1//! Declaration for an n-keyed list type, allowing access to each of its members by each of N
2//! different keys.
3
4// Re-export dependencies that we use to make this macro work.
5#[doc(hidden)]
6pub mod deps {
7    pub use paste::paste;
8    pub use slab::Slab;
9    pub use smallvec::SmallVec;
10}
11
12/// Declare a structure that can hold elements with multiple unique keys.
13///
14/// Each element can be looked up by any of its keys. The keys themselves can be any type that
15/// supports `Hash`, `Eq`, and `Clone`. Elements can have multiple keys of the same type: for
16/// example, a person can have a username `String` and an irc_handle `String`.
17///
18/// Multiple values can be stored for a given key: a lookup of one key returns all elements with
19/// that key.
20///
21/// Keys may be accessed from elements either by field access or by an accessor function.
22///
23/// Keys may be optional. If all keys are optional, then we require additionally that every element
24/// must have at least one key.
25///
26/// # Examples
27///
28/// ```
29/// use tor_basic_utils::n_key_list;
30///
31/// // We declare a person struct with several different fields.
32/// pub struct Person {
33///     username: String,
34///     irc_handle: String,
35///     student_id: Option<u64>,
36///     favorite_joke: Option<String>,
37/// }
38///
39/// n_key_list! {
40///     pub struct PersonList for Person {
41///         // See note on "Key syntax" below.  The ".foo" syntax
42///         // here means that the value for the key is returned
43///         // by accessing a given field.
44///         username: String { .username },
45///         irc_handle: String { .irc_handle },
46///         (Option) student_id: u64 { .student_id }
47///     }
48/// }
49///
50/// let mut people = PersonList::new();
51/// people.insert(Person {
52///     username: "mina".into(),
53///     irc_handle: "pashMina".into(),
54///     student_id: None,
55///     favorite_joke: None,
56/// });
57/// assert_eq!(people.by_username("mina").len(), 1);
58/// assert_eq!(people.by_irc_handle("pashMina").len(), 1);
59/// ```
60///
61/// # Key syntax
62///
63/// You can tell the map to access the keys of an element in any of several ways.
64///
65/// * `name : type { func() }` - A key whose name is `name` and type is `type`, that can be accessed
66///   from a given element by calling `element.func()`.
67/// * `name : type { .field }` - A key whose name is `name` and type is `type`, that can be accessed
68///   from a given element by calling `&element.field`.
69/// * `name : type` - Short for as `name : type { name() }`.
70///
71/// If a key declaration is preceded with `(Option)`, then the key is treated as optional, and
72/// accessor functions are expected to return `Option<&Type>`.
73///
74/// # Additional features
75///
76/// You can put generic parameters and `where` constraints on your structure. The `where` clause (if
77/// present) must be wrapped in square brackets.
78///
79/// If you need to use const generics or lifetimes in your structure, you need to use square
80/// brackets instead of angle brackets, and specify both the generic parameters *and* the type that
81/// you are implementing. (This is due to limitations in the Rust macro system.)  For example:
82///
83/// ```
84/// # use tor_basic_utils::n_key_list;
85/// n_key_list!{
86///     struct['a, T, const N: usize] ArrayMap2['a, T, N] for (String, [&'a T;N])
87///         [ where T: Clone + 'a ]
88///     {
89///          name: String { .0 }
90///     }
91/// }
92/// ```
93#[macro_export]
94macro_rules! n_key_list {
95{
96    $(#[$meta:meta])*
97    $vis:vis struct $mapname:ident $(<$($P:ident),*>)? for $V:ty
98    $( where [ $($constr:tt)+ ] )?
99    {
100        $($body:tt)+
101    }
102} => {
103n_key_list!{
104    $(#[$meta])*
105    $vis struct [$($($P),*)?] $mapname [$($($P),*)?] for $V
106    $( [ where $($constr)+ ] )?
107    {
108        $( $body )+
109    }
110}
111};
112{
113    $(#[$meta:meta])*
114    $vis:vis struct [$($($G:tt)+)?] $mapname:ident [$($($P:tt)+)?] for $V:ty
115    $( [ where $($constr:tt)+ ])?
116    {
117        $( $(( $($flag:ident)+ ))? $key:ident : $KEY:ty $({ $($source:tt)+ })? ),+
118        $(,)?
119    }
120} => {
121$crate::n_key_list::deps::paste!{
122    $( #[$meta] )*
123    /// # General information
124    ///
125    #[doc = concat!(
126        "A list of elements of type `", stringify!($V), "` whose members can be accessed by multiple keys."
127    )]
128    ///
129    /// The keys are:
130    ///
131    #[doc = $( "- `" $key "` (`" $KEY "`)" $(" (" $($flag)+ ")\n" )? )+]
132    ///
133    /// Each element has a value for *each* required key, and up to one value for *each* optional
134    /// key. There can be many elements for a given key value.
135    ///
136    /// ## Requirements
137    ///
138    /// Key types must have consistent `Hash` and `Eq` implementations, as they will be used as keys
139    /// in a `HashMap`.
140    ///
141    /// If all keys are optional, then every element inserted must have at least one non-`None` key.
142    ///
143    /// An element must not change its keys over time through interior mutability.
144    ///
145    /// <div class='warning'>
146    ///
147    /// If *any* of these rules is violated, the consequences are unspecified, and could include
148    /// panics or wrong answers (but not memory-unsafety).
149    ///
150    /// </div>
151    $vis struct $mapname $(<$($G)*>)?
152    where
153        $( $KEY : std::hash::Hash + Eq + Clone , )+
154        $($($constr)+, )?
155    {
156        /// The $key fields here are a set of maps from each of the key values to the lists of the
157        /// positions of values with the same key within the Slab.
158        ///
159        /// Invariants:
160        ///   - There is an entry K=>idx in the map `$key` if and only if values[idx].$accessor() ==
161        ///     K.
162        ///   - Every value in `values` has at least one key.
163        ///   - A list should never be empty.
164        ///
165        /// The map values (the lists) are effectively a set, but using an inline vec should have
166        /// better cache performance than something like HashSet.
167        ///
168        /// The SmallVec size of 4 was chosen arbitrarily under the assumption that a given key will
169        /// have a small number of values on average. The exact constant probably won't matter, but
170        /// inlining most of the lists should be good even if some spill into separate memory
171        /// allocations. It's not worth exposing this level of internal detail to the macro caller
172        /// unless there's a reason we need to.
173        $([<$key _map>]: std::collections::HashMap<$KEY, $crate::n_key_list::deps::SmallVec<[usize; 4]>> , )+
174
175        /// A map from the indices to the values.
176        values: $crate::n_key_list::deps::Slab<$V>,
177    }
178
179    #[allow(dead_code)] // may be needed if this is not public
180    impl $(<$($G)*>)? $mapname $(<$($P)*>)?
181    where
182        $( $KEY : std::hash::Hash + Eq + Clone , )+
183        $($($constr)+)?
184    {
185        #[doc = "Construct a new [`" $mapname "`](Self)."]
186        $vis fn new() -> Self {
187            Self::with_capacity(0)
188        }
189
190        #[doc = "Construct a new [`" $mapname "`](Self) with a given capacity."]
191        $vis fn with_capacity(n: usize) -> Self {
192            Self {
193                $([<$key _map>]: std::collections::HashMap::with_capacity(n),)*
194                values: $crate::n_key_list::deps::Slab::with_capacity(n),
195            }
196        }
197
198        // for each key type
199        $(
200        #[doc = "Return an iterator of the elements whose `" $key "` is `key`."]
201        ///
202        /// The iteration order is arbitrary.
203        $vis fn [<by_ $key>] <BorrowAsKey_>(&self, key: &BorrowAsKey_) -> [<$mapname Iter>] <'_, $V>
204        where
205            $KEY : std::borrow::Borrow<BorrowAsKey_>,
206            BorrowAsKey_: std::hash::Hash + Eq + ?Sized,
207        {
208            [<$mapname Iter>] {
209                iter: self.[<$key _map>].get(key).map(|set| set.iter()).unwrap_or([].iter()),
210                values: &self.values,
211            }
212        }
213
214        #[doc = "Return `true` if this list contains an element whose `" $key "` is `key`."]
215        $vis fn [<contains_ $key>] <BorrowAsKey_>(&mut self, key: &BorrowAsKey_) -> bool
216        where
217            $KEY : std::borrow::Borrow<BorrowAsKey_>,
218            BorrowAsKey_: std::hash::Hash + Eq + ?Sized,
219        {
220            let Some(list) = self.[<$key _map>].get(key) else {
221                return false;
222            };
223
224            if list.is_empty() {
225                // we're not supposed to let this happen, so panic in debug builds
226                #[cfg(debug_assertions)]
227                panic!("Should not have an empty list");
228                #[cfg(not(debug_assertions))]
229                return false;
230            }
231
232            true
233        }
234
235        #[doc = "Remove and return the elements whose `" $key "` is `key`"]
236        /// and where `filter` returns `true`.
237        $vis fn [<remove_by_ $key>] <BorrowAsKey_>(
238            &mut self,
239            key: &BorrowAsKey_,
240            mut filter: impl FnMut(&$V) -> bool,
241        ) -> Vec<$V>
242        where
243            $KEY : std::borrow::Borrow<BorrowAsKey_>,
244            BorrowAsKey_: std::hash::Hash + Eq + ?Sized,
245        {
246            let idx_list: Vec<usize> = {
247                let Some(set) = self.[<$key _map>].get(key) else {
248                    return Vec::new();
249                };
250
251                set
252                    .iter()
253                    .filter(|&&idx| filter(self.values.get(idx).expect("inconsistent state")))
254                    .copied()
255                    .collect()
256            };
257
258            let mut removed = Vec::with_capacity(idx_list.len());
259            for idx in idx_list {
260                removed.push(self.remove_at(idx).expect("inconsistent state"));
261            }
262
263            removed
264        }
265        )+
266
267        fn remove_at(&mut self, idx: usize) -> Option<$V> {
268            if let Some(removed) = self.values.try_remove(idx) {
269                $(
270                let $key = $crate::n_key_list!( @access(removed, ($($($flag)+)?) $key : $KEY $({$($source)+})?) );
271                if let Some($key) = $key {
272                    let set = self.[<$key _map>].get_mut($key).expect("inconsistent state");
273
274                    #[cfg(debug_assertions)]
275                    let size_before_remove = set.len();
276
277                    // a `swap_retain` if it existed might be nice here, but the set should be small
278                    // so shifting all later elements should be fine
279                    set.retain(|x| *x != idx);
280
281                    #[cfg(debug_assertions)]
282                    assert_ne!(set.len(), size_before_remove, "should have removed at least one element");
283
284                    // don't leave entries around with empty lists
285                    if set.is_empty() {
286                        self.[<$key _map>].remove($key);
287                    }
288                }
289                )*
290                Some(removed)
291            } else {
292                None
293            }
294        }
295
296        /// Return an iterator over the elements in this container.
297        $vis fn values(&self) -> impl Iterator<Item=&$V> + '_ {
298            self.values.iter().map(|(_, v)| v)
299        }
300
301        /// Consume this container and return an iterator of its values.
302        $vis fn into_values(self) -> impl Iterator<Item=$V> {
303            self.values.into_iter().map(|(_, v)| v)
304        }
305
306        /// Try to insert `value`.
307        ///
308        /// Return `Error::NoKeys` if all the keys are optional, and `value` has no keys at all.
309        $vis fn try_insert(&mut self, value: $V) -> Result<(), $crate::n_key_list::Error> {
310            if self.capacity() > 32 && self.len() < self.capacity() / 4 {
311                // we have the opportunity to free up a fair amount of space; let's take it
312                self.compact()
313            }
314
315            let mut some_key_found = false;
316
317            $(
318            let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) );
319            some_key_found |= $key.is_some();
320            )*
321
322            if !some_key_found {
323                // exit early before we add it to `values`
324                return Err($crate::n_key_list::Error::NoKeys);
325            }
326
327            let idx = self.values.insert(value);
328            let value = self.values.get(idx).expect("inconsistent state");
329
330            $(
331            let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) );
332            if let Some($key) = $key {
333                let set = self.[<$key _map>].entry($key.to_owned()).or_default();
334                set.push(idx);
335
336                // we don't want the list's capacity to grow unbounded, so in the (hopefully) rare
337                // case that the list grows large and then small again, try to free some of the
338                // memory
339                if set.capacity() > 64 && set.len() < set.capacity() / 4 {
340                    set.shrink_to_fit();
341                }
342
343                // TODO: would it be beneficial to aggressively shrink the list if `len()` is
344                // smaller than `inline_size()`?
345            }
346            )*
347
348            Ok(())
349        }
350
351        /// See [`try_insert`](Self::try_insert). Panicks on errors.
352        $vis fn insert(&mut self, value: $V) {
353            self.try_insert(value)
354                .expect("tried to add a value with no key")
355        }
356
357        /// Return the number of elements in this container.
358        $vis fn len(&self) -> usize {
359            self.values.len()
360        }
361
362        /// Return `true` if there are no elements in this container.
363        $vis fn is_empty(&self) -> bool {
364            let is_empty = self.len() == 0;
365
366            #[cfg(debug_assertions)]
367            if is_empty {
368                $(assert!(self.[<$key _map>].is_empty());)*
369            }
370
371            is_empty
372        }
373
374        /// Return the number of elements for which this container has allocated storage.
375        $vis fn capacity(&self) -> usize {
376            self.values.capacity()
377        }
378
379        /// Remove every element that does not satisfy the predicate `pred`.
380        $vis fn retain<F>(&mut self, mut pred: F)
381        where
382            F: FnMut(&$V) -> bool,
383        {
384            for idx in 0..self.values.capacity() {
385                if self.values.get(idx).map(&mut pred) == Some(false) {
386                    self.remove_at(idx);
387                }
388            }
389        }
390
391        /// Re-index all the values in this map, so that the map can use a more compact
392        /// representation.
393        ///
394        /// This should be done infrequently; it's expensive.
395        fn compact(&mut self) {
396            let old_value = std::mem::replace(self, Self::with_capacity(self.len()));
397            for item in old_value.into_values() {
398                self.insert(item);
399            }
400        }
401
402        /// Assert that this list appears to be in an internally consistent state.
403        ///
404        /// This method can be very expensive, and it should never fail unless your code has a bug.
405        ///
406        /// # Panics
407        ///
408        /// Panics if it finds bugs in this object, or constraint violations in its elements. See
409        /// the (type documentation)[Self#Requirements] for a list of constraints.
410        // it would be nice to run this after every operation that mutates internal state in debug
411        // builds, but this function is way too slow for that
412        fn check_consistency(&self) {
413            // ensure each value is in exactly the correct maps
414            for (idx, value) in &self.values {
415                $(
416                    let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) );
417                    if let Some($key) = $key {
418                        // check that it exists in the set that it should be in
419                        let set = self.[<$key _map>].get($key).expect("inconsistent state");
420                        assert!(set.contains(&idx));
421                        // check that it does not exist in any set that it should not be in
422                        for (_key, set) in self.[<$key _map>].iter().filter(|(key, _)| *key != $key) {
423                            assert!(!set.contains(&idx));
424                        }
425                    } else {
426                        // check that it does not exist in any set
427                        for set in self.[<$key _map>].values() {
428                            assert!(!set.contains(&idx));
429                        }
430                    }
431                )*
432            }
433
434            $(
435                for set in self.[<$key _map>].values() {
436                    // ensure no sets have dangling idxs
437                    for idx in set {
438                        assert!(self.values.contains(*idx));
439                    }
440
441                    // ensure no sets have duplicate idxs
442                    let mut set_iter = set.iter();
443                    while let Some(idx) = set_iter.next() {
444                        assert!(!set_iter.clone().any(|x| x == idx));
445                    }
446
447                    // ensure no sets are empty
448                    assert!(!set.is_empty());
449                }
450            )*
451
452            // ensure that if a value is in a key's map, then the value really has that key
453            $(
454                for (key, set) in &self.[<$key _map>] {
455                    for idx in set {
456                        let value = self.values.get(*idx).expect("inconsistent state");
457                        let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) );
458                        let $key = $key.expect("inconsistent state");
459                        assert!(key == $key);
460                    }
461                }
462            )*
463        }
464    }
465
466    impl $(<$($G)*>)? Default for $mapname $(<$($P)*>)?
467    where
468        $( $KEY : std::hash::Hash + Eq + Clone , )+
469        $($($constr)+)?
470    {
471        fn default() -> Self {
472            $mapname::new()
473        }
474    }
475
476    impl $(<$($G)*>)? std::iter::FromIterator<$V> for $mapname $(<$($P)*>)?
477    where
478        $( $KEY : std::hash::Hash + Eq + Clone , )*
479        $($($constr)+)?
480    {
481        fn from_iter<IntoIter_>(iter: IntoIter_) -> Self
482        where
483            IntoIter_: std::iter::IntoIterator<Item = $V>,
484        {
485            let iter = iter.into_iter();
486            let mut list = Self::with_capacity(iter.size_hint().0);
487            for value in iter {
488                list.insert(value);
489            }
490            list
491        }
492    }
493
494    #[doc = "An iterator for [`" $mapname "`](" $mapname ")."]
495    $vis struct [<$mapname Iter>] <'a, T> {
496        iter: std::slice::Iter<'a, usize>,
497        values: &'a $crate::n_key_list::deps::Slab<T>,
498    }
499
500    impl<'a, T> std::iter::Iterator for [<$mapname Iter>] <'a, T> {
501        type Item = &'a T;
502
503        fn next(&mut self) -> std::option::Option<Self::Item> {
504            self.iter.next().map(|idx| self.values.get(*idx).expect("inconsistent state"))
505        }
506
507        #[inline]
508        fn size_hint(&self) -> (usize, std::option::Option<usize>) {
509            self.iter.size_hint()
510        }
511    }
512
513    impl<'a, T> std::iter::ExactSizeIterator for [<$mapname Iter>] <'a, T>
514    where
515        // no harm in specifying it here, even though it should always be true
516        std::slice::Iter<'a, usize>: std::iter::ExactSizeIterator,
517    {
518        #[inline]
519        fn len(&self) -> usize {
520            self.iter.len()
521        }
522    }
523
524    impl<'a, T> std::default::Default for [<$mapname Iter>] <'a, T> {
525        fn default() -> Self {
526            [<$mapname Iter>] {
527                iter: [].iter(),
528                values: const { &$crate::n_key_list::deps::Slab::new() },
529            }
530        }
531    }
532}
533};
534
535// Helper: Generate an expression to access a specific key and return an `Option<&TYPE>` for that
536// key. This is the part of the macro that parses key descriptions.
537
538{ @access($ex:expr, (Option) $key:ident : $t:ty ) } => {
539    $ex.key()
540};
541{ @access($ex:expr, () $key:ident : $t:ty) } => {
542    Some($ex.key())
543};
544{ @access($ex:expr, (Option) $key:ident : $t:ty { . $field:tt } ) } => {
545    $ex.$field.as_ref()
546};
547{ @access($ex:expr, () $key:ident : $t:ty { . $field:tt } ) } => {
548   Some(&$ex.$field)
549};
550{ @access($ex:expr, (Option) $key:ident : $t:ty { $func:ident () } ) } => {
551    $ex.$func()
552};
553{ @access($ex:expr, () $key:ident : $t:ty { $func:ident () } ) } => {
554    Some($ex.$func())
555};
556}
557
558/// An error returned from an operation on an [`n_key_list`].
559#[derive(Clone, Debug, thiserror::Error)]
560#[non_exhaustive]
561pub enum Error {
562    /// We tried to insert a value into a set where all keys were optional, but every key on that
563    /// value was `None`.
564    #[error("Tried to insert a value with no keys")]
565    NoKeys,
566}
567
568#[cfg(test)]
569mod test {
570    // @@ begin test lint list maintained by maint/add_warning @@
571    #![allow(clippy::bool_assert_comparison)]
572    #![allow(clippy::clone_on_copy)]
573    #![allow(clippy::dbg_macro)]
574    #![allow(clippy::mixed_attributes_style)]
575    #![allow(clippy::print_stderr)]
576    #![allow(clippy::print_stdout)]
577    #![allow(clippy::single_char_pattern)]
578    #![allow(clippy::unwrap_used)]
579    #![allow(clippy::unchecked_duration_subtraction)]
580    #![allow(clippy::useless_vec)]
581    #![allow(clippy::needless_pass_by_value)]
582    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
583
584    fn sort<T: std::cmp::Ord>(i: impl Iterator<Item = T>) -> Vec<T> {
585        let mut v: Vec<_> = i.collect();
586        v.sort();
587        v
588    }
589
590    n_key_list! {
591        #[derive(Clone, Debug)]
592        struct Tuple2List<A,B> for (A,B) {
593            first: A { .0 },
594            second: B { .1 },
595        }
596    }
597
598    #[test]
599    #[allow(clippy::cognitive_complexity)]
600    fn basic() {
601        let mut list = Tuple2List::new();
602        assert!(list.is_empty());
603
604        // add a single element and do some sanity checks
605        list.insert((0_u32, 99_u16));
606        assert_eq!(list.len(), 1);
607        assert_eq!(list.contains_first(&0), true);
608        assert_eq!(list.contains_second(&99), true);
609        assert_eq!(list.contains_first(&99), false);
610        assert_eq!(list.contains_second(&0), false);
611        assert_eq!(sort(list.by_first(&0)), [&(0, 99)]);
612        assert_eq!(sort(list.by_second(&99)), [&(0, 99)]);
613        assert_eq!(list.by_first(&99).len(), 0);
614        assert_eq!(list.by_second(&0).len(), 0);
615        list.check_consistency();
616
617        // lookup by a key that has never existed in the map
618        assert_eq!(list.by_first(&1000000).len(), 0);
619
620        // inserting the same element again should add it to the list
621        assert_eq!(list.len(), 1);
622        list.insert((0_u32, 99_u16));
623        assert_eq!(list.len(), 2);
624        list.check_consistency();
625
626        // add two new entries
627        list.insert((12, 34));
628        list.insert((0, 34));
629        assert_eq!(list.len(), 4);
630        assert!(list.capacity() >= 4);
631        assert_eq!(sort(list.by_first(&0)), [&(0, 34), &(0, 99), &(0, 99)]);
632        assert_eq!(sort(list.by_first(&12)), [&(12, 34)]);
633        list.check_consistency();
634
635        // remove some elements
636        assert_eq!(
637            list.remove_by_first(&0, |(_, b)| *b == 99),
638            vec![(0, 99), (0, 99)]
639        );
640        assert_eq!(list.remove_by_first(&0, |_| true), vec![(0, 34)]);
641        assert_eq!(list.len(), 1);
642        list.check_consistency();
643
644        // test adding an element again
645        assert_eq!(sort(list.by_first(&12)), [&(12, 34)]);
646        list.insert((12, 123));
647        assert_eq!(list.len(), 2);
648        assert_eq!(sort(list.by_first(&12)), [&(12, 34), &(12, 123)]);
649        assert_eq!(sort(list.by_second(&34)), [&(12, 34)]);
650        assert_eq!(sort(list.by_second(&123)), [&(12, 123)]);
651        list.check_consistency();
652
653        // test iterators
654        list.insert((56, 78));
655        assert_eq!(sort(list.values()), [&(12, 34), &(12, 123), &(56, 78)]);
656        assert_eq!(sort(list.into_values()), [(12, 34), (12, 123), (56, 78)]);
657    }
658
659    #[test]
660    fn retain_and_compact() {
661        let mut list: Tuple2List<String, String> = (1..=1000)
662            .map(|idx| (format!("A={}", idx), format!("B={}", idx)))
663            .collect();
664
665        assert_eq!(list.len(), 1000);
666        let cap_orig = list.capacity();
667        assert!(cap_orig >= list.len());
668        list.check_consistency();
669
670        // retain only the values whose first key is 3 characters long; that's 9 values out of 1000
671        list.retain(|(a, _)| a.len() <= 3);
672        assert_eq!(list.len(), 9);
673        // we don't shrink till we next insert
674        assert_eq!(list.capacity(), cap_orig);
675        list.check_consistency();
676
677        // insert should cause the list to shrink
678        list.insert(("A=0".to_string(), "B=0".to_string()));
679        assert!(list.capacity() < cap_orig);
680        assert_eq!(list.len(), 10);
681        for idx in 0..=9 {
682            assert!(list.contains_first(&format!("A={}", idx)));
683        }
684        list.check_consistency();
685    }
686
687    n_key_list! {
688        #[derive(Clone, Debug)]
689        struct AllOptional<A,B> for (Option<A>,Option<B>) {
690            (Option) first: A { .0 },
691            (Option) second: B { .1 },
692        }
693    }
694
695    #[test]
696    fn optional() {
697        let mut list = AllOptional::<u8, u8>::new();
698
699        // should be able to insert values with at least one key
700        list.insert((Some(1), Some(2)));
701        list.insert((None, Some(2)));
702        list.insert((Some(1), None));
703        list.check_consistency();
704
705        assert_eq!(
706            sort(list.by_first(&1)),
707            [&(Some(1), None), &(Some(1), Some(2))],
708        );
709
710        // check that inserting a value with no keys results in an error
711        assert!(matches!(
712            list.try_insert((None, None)),
713            Err(super::Error::NoKeys),
714        ));
715    }
716
717    #[allow(dead_code)]
718    struct Weekday {
719        dow: u8,
720        name: &'static str,
721        lucky_number: Option<u16>,
722    }
723    #[allow(dead_code)]
724    impl Weekday {
725        fn dow(&self) -> &u8 {
726            &self.dow
727        }
728        fn name(&self) -> &str {
729            self.name
730        }
731        fn lucky_number(&self) -> Option<&u16> {
732            self.lucky_number.as_ref()
733        }
734    }
735    n_key_list! {
736        struct WeekdaySet for Weekday {
737            idx: u8 { dow() },
738            (Option) lucky: u16 { lucky_number() },
739            name: String { name() }
740        }
741    }
742
743    n_key_list! {
744        struct['a] ArrayMap['a] for (String, [&'a u32;10]) {
745            name: String { .0 }
746        }
747    }
748
749    n_key_list! {
750        struct['a, const N:usize] ArrayMap2['a, N] for (String, [&'a u32;N]) {
751            name: String { .0 }
752        }
753    }
754}
tor_basic_utils/n_key_list.rs

tor_basic_utils/
n_key_list.rs
