//! Declaration for an n-keyed list type, allowing access to each of its members by each of N

//! different keys.

// Re-export dependencies that we use to make this macro work.

#[doc(hidden)]

pub mod deps {

    pub use paste::paste;

    pub use slab::Slab;

    pub use smallvec::SmallVec;

}

/// Declare a structure that can hold elements with multiple unique keys.

///

/// Each element can be looked up by any of its keys. The keys themselves can be any type that

/// supports `Hash`, `Eq`, and `Clone`. Elements can have multiple keys of the same type: for

/// example, a person can have a username `String` and an irc_handle `String`.

///

/// Multiple values can be stored for a given key: a lookup of one key returns all elements with

/// that key.

///

/// Keys may be accessed from elements either by field access or by an accessor function.

///

/// Keys may be optional. If all keys are optional, then we require additionally that every element

/// must have at least one key.

///

/// # Examples

///

/// ```

/// use tor_basic_utils::n_key_list;

///

/// // We declare a person struct with several different fields.

/// pub struct Person {

///     username: String,

///     irc_handle: String,

///     student_id: Option<u64>,

///     favorite_joke: Option<String>,

/// }

///

/// n_key_list! {

///     pub struct PersonList for Person {

///         // See note on "Key syntax" below.  The ".foo" syntax

///         // here means that the value for the key is returned

///         // by accessing a given field.

///         username: String { .username },

///         irc_handle: String { .irc_handle },

///         (Option) student_id: u64 { .student_id }

///     }

/// }

///

/// let mut people = PersonList::new();

/// people.insert(Person {

///     username: "mina".into(),

///     irc_handle: "pashMina".into(),

///     student_id: None,

///     favorite_joke: None,

/// });

/// assert_eq!(people.by_username("mina").len(), 1);

/// assert_eq!(people.by_irc_handle("pashMina").len(), 1);

/// ```

///

/// # Key syntax

///

/// You can tell the map to access the keys of an element in any of several ways.

///

/// * `name : type { func() }` - A key whose name is `name` and type is `type`, that can be accessed

///   from a given element by calling `element.func()`.

/// * `name : type { .field }` - A key whose name is `name` and type is `type`, that can be accessed

///   from a given element by calling `&element.field`.

/// * `name : type` - Short for as `name : type { name() }`.

///

/// If a key declaration is preceded with `(Option)`, then the key is treated as optional, and

/// accessor functions are expected to return `Option<&Type>`.

///

/// # Additional features

///

/// You can put generic parameters and `where` constraints on your structure. The `where` clause (if

/// present) must be wrapped in square brackets.

///

/// If you need to use const generics or lifetimes in your structure, you need to use square

/// brackets instead of angle brackets, and specify both the generic parameters *and* the type that

/// you are implementing. (This is due to limitations in the Rust macro system.)  For example:

///

/// ```

/// # use tor_basic_utils::n_key_list;

/// n_key_list!{

///     struct['a, T, const N: usize] ArrayMap2['a, T, N] for (String, [&'a T;N])

///         [ where T: Clone + 'a ]

///     {

///          name: String { .0 }

///     }

/// }

/// ```

#[macro_export]

macro_rules! n_key_list {

{

    $(#[$meta:meta])*

    $vis:vis struct $mapname:ident $(<$($P:ident),*>)? for $V:ty

    $( where [ $($constr:tt)+ ] )?

    {

        $($body:tt)+

    }

} => {

n_key_list!{

    $(#[$meta])*

    $vis struct [$($($P),*)?] $mapname [$($($P),*)?] for $V

    $( [ where $($constr)+ ] )?

    {

        $( $body )+

    }

}

};

{

    $(#[$meta:meta])*

    $vis:vis struct [$($($G:tt)+)?] $mapname:ident [$($($P:tt)+)?] for $V:ty

    $( [ where $($constr:tt)+ ])?

    {

        $( $(( $($flag:ident)+ ))? $key:ident : $KEY:ty $({ $($source:tt)+ })? ),+

        $(,)?

    }

} => {

$crate::n_key_list::deps::paste!{

    $( #[$meta] )*

    /// # General information

    ///

    #[doc = concat!(

        "A list of elements of type `", stringify!($V), "` whose members can be accessed by multiple keys."

    )]

    ///

    /// The keys are:

    ///

    #[doc = $( "- `" $key "` (`" $KEY "`)" $(" (" $($flag)+ ")\n" )? )+]

    ///

    /// Each element has a value for *each* required key, and up to one value for *each* optional

    /// key. There can be many elements for a given key value.

    ///

    /// ## Requirements

    ///

    /// Key types must have consistent `Hash` and `Eq` implementations, as they will be used as keys

    /// in a `HashMap`.

    ///

    /// If all keys are optional, then every element inserted must have at least one non-`None` key.

    ///

    /// An element must not change its keys over time through interior mutability.

    ///

    /// <div class='warning'>

    ///

    /// If *any* of these rules is violated, the consequences are unspecified, and could include

    /// panics or wrong answers (but not memory-unsafety).

    ///

    /// </div>

        {

            }

        /// Re-index all the values in this map, so that the map can use a more compact

        /// representation.

        ///

        /// This should be done infrequently; it's expensive.

        /// Assert that this list appears to be in an internally consistent state.

        ///

        /// This method can be very expensive, and it should never fail unless your code has a bug.

        ///

        /// # Panics

        ///

        /// Panics if it finds bugs in this object, or constraint violations in its elements. See

        /// the (type documentation)[Self#Requirements] for a list of constraints.

        // it would be nice to run this after every operation that mutates internal state in debug

        // builds, but this function is way too slow for that

            // ensure each value is in exactly the correct maps

                $(

                        // check that it exists in the set that it should be in

                        // check that it does not exist in any set that it should not be in

                        }

                    } else {

                        // check that it does not exist in any set

                        }

                    }

                )*

            }

            $(

                    // ensure no sets have dangling idxs

                    }

                    // ensure no sets have duplicate idxs

                    }

                    // ensure no sets are empty

                }

            )*

            // ensure that if a value is in a key's map, then the value really has that key

            $(

                    }

                }

            )*

    }

    impl $(<$($G)*>)? Default for $mapname $(<$($P)*>)?

    where

        $( $KEY : std::hash::Hash + Eq + Clone , )+

        $($($constr)+)?

    {

    }

    impl $(<$($G)*>)? std::iter::FromIterator<$V> for $mapname $(<$($P)*>)?

    where

        $( $KEY : std::hash::Hash + Eq + Clone , )*

        $($($constr)+)?

    {

        {

    }

    #[doc = "An iterator for [`" $mapname "`](" $mapname ")."]

    $vis struct [<$mapname Iter>] <'a, T> {

        iter: std::slice::Iter<'a, usize>,

        values: &'a $crate::n_key_list::deps::Slab<T>,

    }

    impl<'a, T> std::iter::Iterator for [<$mapname Iter>] <'a, T> {

        type Item = &'a T;

        #[inline]

    }

    impl<'a, T> std::iter::ExactSizeIterator for [<$mapname Iter>] <'a, T>

    where

        // no harm in specifying it here, even though it should always be true

        std::slice::Iter<'a, usize>: std::iter::ExactSizeIterator,

    {

        #[inline]

    }

    impl<'a, T> std::default::Default for [<$mapname Iter>] <'a, T> {

            [<$mapname Iter>] {

                values: const { &$crate::n_key_list::deps::Slab::new() },

            }

    }

}

};

// Helper: Generate an expression to access a specific key and return an `Option<&TYPE>` for that

// key. This is the part of the macro that parses key descriptions.

{ @access($ex:expr, (Option) $key:ident : $t:ty ) } => {

    $ex.key()

};

{ @access($ex:expr, () $key:ident : $t:ty) } => {

    Some($ex.key())

};

{ @access($ex:expr, (Option) $key:ident : $t:ty { . $field:tt } ) } => {

    $ex.$field.as_ref()

};

{ @access($ex:expr, () $key:ident : $t:ty { . $field:tt } ) } => {

   Some(&$ex.$field)

};

{ @access($ex:expr, (Option) $key:ident : $t:ty { $func:ident () } ) } => {

    $ex.$func()

};

{ @access($ex:expr, () $key:ident : $t:ty { $func:ident () } ) } => {

    Some($ex.$func())

};

}

/// An error returned from an operation on an [`n_key_list`].

#[derive(Clone, Debug, thiserror::Error)]

#[non_exhaustive]

pub enum Error {

    /// We tried to insert a value into a set where all keys were optional, but every key on that

    /// value was `None`.

    #[error("Tried to insert a value with no keys")]

    NoKeys,

}

#[cfg(test)]

mod test {

    // @@ begin test lint list maintained by maint/add_warning @@

    #![allow(clippy::bool_assert_comparison)]

    #![allow(clippy::clone_on_copy)]

    #![allow(clippy::dbg_macro)]

    #![allow(clippy::mixed_attributes_style)]

    #![allow(clippy::print_stderr)]

    #![allow(clippy::print_stdout)]

    #![allow(clippy::single_char_pattern)]

    #![allow(clippy::unwrap_used)]

    #![allow(clippy::unchecked_time_subtraction)]

    #![allow(clippy::useless_vec)]

    #![allow(clippy::needless_pass_by_value)]

    #![allow(clippy::string_slice)] // See arti#2571

    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->

    fn sort<T: std::cmp::Ord>(i: impl Iterator<Item = T>) -> Vec<T> {

        let mut v: Vec<_> = i.collect();

        v.sort();

        v

    }

    n_key_list! {

        #[derive(Clone, Debug)]

        struct Tuple2List<A,B> for (A,B) {

            first: A { .0 },

            second: B { .1 },

        }

    }

    #[test]

    fn basic() {

        let mut list = Tuple2List::new();

        assert!(list.is_empty());

        // add a single element and do some sanity checks

        list.insert((0_u32, 99_u16));

        assert_eq!(list.len(), 1);

        assert_eq!(list.contains_first(&0), true);

        assert_eq!(list.contains_second(&99), true);

        assert_eq!(list.contains_first(&99), false);

        assert_eq!(list.contains_second(&0), false);

        assert_eq!(sort(list.by_first(&0)), [&(0, 99)]);

        assert_eq!(sort(list.by_second(&99)), [&(0, 99)]);

        assert_eq!(list.by_first(&99).len(), 0);

        assert_eq!(list.by_second(&0).len(), 0);

        list.check_consistency();

        // lookup by a key that has never existed in the map

        assert_eq!(list.by_first(&1000000).len(), 0);

        // inserting the same element again should add it to the list

        assert_eq!(list.len(), 1);

        list.insert((0_u32, 99_u16));

        assert_eq!(list.len(), 2);

        list.check_consistency();

        // add two new entries

        list.insert((12, 34));

        list.insert((0, 34));

        assert_eq!(list.len(), 4);

        assert!(list.capacity() >= 4);

        assert_eq!(sort(list.by_first(&0)), [&(0, 34), &(0, 99), &(0, 99)]);

        assert_eq!(sort(list.by_first(&12)), [&(12, 34)]);

        list.check_consistency();

        // remove some elements

        assert_eq!(

            list.remove_by_first(&0, |(_, b)| *b == 99),

            vec![(0, 99), (0, 99)]

        );

        assert_eq!(list.remove_by_first(&0, |_| true), vec![(0, 34)]);

        assert_eq!(list.len(), 1);

        list.check_consistency();

        // test adding an element again

        assert_eq!(sort(list.by_first(&12)), [&(12, 34)]);

        list.insert((12, 123));

        assert_eq!(list.len(), 2);

        assert_eq!(sort(list.by_first(&12)), [&(12, 34), &(12, 123)]);

        assert_eq!(sort(list.by_second(&34)), [&(12, 34)]);

        assert_eq!(sort(list.by_second(&123)), [&(12, 123)]);

        list.check_consistency();

        // test iterators

        list.insert((56, 78));

        assert_eq!(sort(list.values()), [&(12, 34), &(12, 123), &(56, 78)]);

        assert_eq!(sort(list.into_values()), [(12, 34), (12, 123), (56, 78)]);

    }

    #[test]

    fn retain_and_compact() {

        let mut list: Tuple2List<String, String> = (1..=1000)

            .map(|idx| (format!("A={}", idx), format!("B={}", idx)))

            .collect();

        assert_eq!(list.len(), 1000);

        let cap_orig = list.capacity();

        assert!(cap_orig >= list.len());

        list.check_consistency();

        // retain only the values whose first key is 3 characters long; that's 9 values out of 1000

        list.retain(|(a, _)| a.len() <= 3);

        assert_eq!(list.len(), 9);

        // we don't shrink till we next insert

        assert_eq!(list.capacity(), cap_orig);

        list.check_consistency();

        // insert should cause the list to shrink

        list.insert(("A=0".to_string(), "B=0".to_string()));

        assert!(list.capacity() < cap_orig);

        assert_eq!(list.len(), 10);

        for idx in 0..=9 {

            assert!(list.contains_first(&format!("A={}", idx)));

        }

        list.check_consistency();

    }

    n_key_list! {

        #[derive(Clone, Debug)]

        struct AllOptional<A,B> for (Option<A>,Option<B>) {

            (Option) first: A { .0 },

            (Option) second: B { .1 },

        }

    }

    #[test]

    fn optional() {

        let mut list = AllOptional::<u8, u8>::new();

        // should be able to insert values with at least one key

        list.insert((Some(1), Some(2)));

        list.insert((None, Some(2)));

        list.insert((Some(1), None));

        list.check_consistency();

        assert_eq!(

            sort(list.by_first(&1)),

            [&(Some(1), None), &(Some(1), Some(2))],

        );

        // check that inserting a value with no keys results in an error

        assert!(matches!(

            list.try_insert((None, None)),

            Err(super::Error::NoKeys),

        ));

    }

    #[allow(dead_code)]

    struct Weekday {

        dow: u8,

        name: &'static str,

        lucky_number: Option<u16>,

    }

    #[allow(dead_code)]

    impl Weekday {

        fn dow(&self) -> &u8 {

            &self.dow

        }

        fn name(&self) -> &str {

            self.name

        }

        fn lucky_number(&self) -> Option<&u16> {

            self.lucky_number.as_ref()

        }

    }

    n_key_list! {

        struct WeekdaySet for Weekday {

            idx: u8 { dow() },

            (Option) lucky: u16 { lucky_number() },

            name: String { name() }

        }

    }

    n_key_list! {

        struct['a] ArrayMap['a] for (String, [&'a u32;10]) {

            name: String { .0 }

        }

    }

    n_key_list! {

        struct['a, const N:usize] ArrayMap2['a, N] for (String, [&'a u32;N]) {

            name: String { .0 }

        }

    }

}