//! Logic for filtering and selecting channels in order to find suitable channels for a target.

use crate::mgr::state::{ChannelState, OpenEntry, PendingEntry};

use crate::mgr::AbstractChannel;

use tor_linkspec::{HasRelayIds, RelayIds};

/// Returns `true` if the open channel is allowed to be used for a new channel request to the

/// target.

/// Returns `true` if the pending channel could possibly be used for a new channel request to the

/// target. You still need to verify the final built channel with [`open_channel_is_allowed`] before

/// using it.

    /// An empty [`RelayIds`].

    const EMPTY_IDS: RelayIds = RelayIds::empty();

    // TODO RELAY: The comments and behaviour below assume that it's better to create a new channel

    // than to wait around for a channel which may or may not end up being usable for `target`. This

    // has the benefit that malicious circuit extension requests won't delay legitimate circuit

    // extension requests, but also means that we could end up creating more channels than

    // necessary. This is different from C-tor, which will wait for a channel even if that channel

    // might not end up being usable for `target`. For example in tor's `channel_get_for_extend`,

    // tor will wait for an "in progress" channel if all of the following are true:

    //

    // - The requested ids are a subset of the channel's ids. (Note that in the comments below we

    //   require it to be a superset, not a subset.)

    // - The requested IPv4 or IPv6 address matches either the channel's IPv4 or IPv6 address. (Note

    //   that in the comments below, we require `target`s addresses to exactly match.)

    //

    // It might be good to re-evaluate what behaviour we want as we implement more channel code.

    //

    // NOTE (opara): It has been decided that C-tor's approach would be better. See the thread at:

    // https://gitlab.torproject.org/tpo/core/arti/-/merge_requests/2544#note_3094696

    // We want to avoid returning pending channels that were initially created from malicious

    // channel requests (for example from malicious relay-extend requests) that build channels which

    // will never complete successfully. Two cases where this can happen are:

    // 1. A malicious channel request asks us to build a channel to a target with a correct relay id

    //    and address, but also an additional incorrect relay id. Later when the target sends its

    //    CERTS cell, all of the relay ids won't match and the channel will fail to build. We don't

    //    want to assign non-malicious channel requests to this pending channel that will eventually

    //    fail to build.

    // 2. A malicious channel request asks us to build a channel to a target with an incorrect

    //    address. This pending channel may stall. We don't want to assign non-malicious channel

    //    requests to this pending channel that will stall for potentially a long time.

/// Returns the best channel for `target`.

// TODO: remove me when the below TODOs are implemented

#[allow(clippy::only_used_in_recursion)]

    use std::cmp::Ordering;

    use ChannelState::*;

    /// Compare two channels to determine the better channel for `target`.

            // if the open channel is not usable, prefer the pending channel

            // otherwise prefer the open channel

            // the logic above, but reversed

            // not much info to help choose when both channels are pending, but this should be rare

            // both channels are open

            }

        }

    // preferred channels will be ordered higher, and we choose the max

/// Similar to [`Ordering`](std::cmp::Ordering), but is easier to reason about when comparing two

/// objects that don't have a numeric sense of ordering (ex: returning `Greater` is confusing if the

/// ordering isn't numeric).

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]

enum Choice {

    /// Choose the first.

    First,

    /// Choose the second.

    Second,

    /// Choose either.

    Either,

}

impl Choice {

    /// Reverses the `Choice`.

    ///

    /// - `First` becomes `Second`.

    /// - `Second` becomes `First`.

    /// - `Either` becomes `Either`.

        }

}

#[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_duration_subtraction)]

    #![allow(clippy::useless_vec)]

    #![allow(clippy::needless_pass_by_value)]

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

    use super::*;

    use std::sync::Arc;

    use std::time::Duration;

    use tor_linkspec::RelayIds;

    use tor_llcrypto::pk::ed25519::Ed25519Identity;

    use tor_llcrypto::pk::rsa::RsaIdentity;

    use tor_proto::channel::kist::KistParams;

    use tor_proto::channel::ChannelPaddingInstructionsUpdates;

    #[derive(Debug)]

    struct FakeChannel {

        usable: bool,

        ids: RelayIds,

    }

    impl AbstractChannel for FakeChannel {

        fn is_usable(&self) -> bool {

            self.usable

        }

        fn duration_unused(&self) -> Option<Duration> {

            None

        }

        fn reparameterize(

            &self,

            _updates: Arc<ChannelPaddingInstructionsUpdates>,

        ) -> tor_proto::Result<()> {

            Ok(())

        }

        fn reparameterize_kist(&self, _kist_params: KistParams) -> tor_proto::Result<()> {

            Ok(())

        }

        fn engage_padding_activities(&self) {}

    }

    impl HasRelayIds for FakeChannel {

        fn identity(

            &self,

            key_type: tor_linkspec::RelayIdType,

        ) -> Option<tor_linkspec::RelayIdRef<'_>> {

            self.ids.identity(key_type)

        }

    }

    #[derive(Clone, Debug)]

    struct FakeBuildSpec {

        ids: RelayIds,

    }

    impl FakeBuildSpec {

        fn new(ids: RelayIds) -> Self {

            Self { ids }

        }

    }

    impl HasRelayIds for FakeBuildSpec {

        fn identity(

            &self,

            key_type: tor_linkspec::RelayIdType,

        ) -> Option<tor_linkspec::RelayIdRef<'_>> {

            self.ids.identity(key_type)

        }

    }

    /// Assert that two `Option<&T>` point to the same data.

    macro_rules! assert_opt_ptr_eq {

        ($a:expr, $b:expr) => {

            assert_opt_ptr_eq!($a, $b,);

        };

        ($a:expr, $b:expr, $($x:tt)*) => {

            assert_eq!($a.map(std::ptr::from_ref), $b.map(std::ptr::from_ref), $($x)*);

        };

    }

    /// Calls `f` with every permutation of `list`. Don't use with large lists :)

    fn with_permutations<T>(list: &[T], mut f: impl FnMut(Vec<&T>)) {

        use itertools::Itertools;

        for new_list in list.iter().permutations(list.len()) {

            f(new_list);

        }

    }

    /// Helper to make a fake Ed identity from some bytes.

    fn ed(a: &[u8]) -> Ed25519Identity {

        let mut bytes = [0; 32];

        bytes[0..a.len()].copy_from_slice(a);

        bytes.into()

    }

    /// Helper to make a fake rsa identity from some bytes.

    fn rsa(a: &[u8]) -> RsaIdentity {

        let mut bytes = [0; 20];

        bytes[0..a.len()].copy_from_slice(a);

        bytes.into()

    }

    /// Helper to build a `RelayIds` to make tests shorter.

    fn ids(

        rsa: impl Into<Option<RsaIdentity>>,

        ed: impl Into<Option<Ed25519Identity>>,

    ) -> RelayIds {

        let mut ids = tor_linkspec::RelayIdsBuilder::default();

        if let Some(rsa) = rsa.into() {

            ids.rsa_identity(rsa);

        }

        if let Some(ed) = ed.into() {

            ids.ed_identity(ed);

        }

        ids.build().unwrap()

    }

    /// Create an open channel entry.

    fn open_channel<C>(chan: C) -> OpenEntry<C> {

        OpenEntry {

            channel: Arc::new(chan),

            max_unused_duration: Duration::from_secs(0),

        }

    }

    /// Create a pending channel entry with the given IDs.

    fn pending_channel(ids: RelayIds) -> PendingEntry {

        use crate::mgr::state::UniqPendingChanId;

        use futures::FutureExt;

        use oneshot_fused_workaround as oneshot;

        PendingEntry {

            ids,

            pending: oneshot::channel().1.shared(),

            unique_id: UniqPendingChanId::new(),

        }

    }

    #[test]

    fn best_channel_usable_unusable() {

        // two channels where only the first is usable

        let channels = [

            ChannelState::Open(open_channel(FakeChannel {

                usable: true,

                ids: ids(None, ed(b"A")),

            })),

            ChannelState::Open(open_channel(FakeChannel {

                usable: false,

                ids: ids(None, ed(b"A")),

            })),

        ];

        // should return the usable channel

        let target = FakeBuildSpec::new(ids(None, ed(b"A")));

        with_permutations(&channels, |x| {

            assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[0]));

        });

    }

    #[test]

    fn best_channel_open_pending() {

        // a usable open channel and a pending channel

        let channels = [

            ChannelState::Open(open_channel(FakeChannel {

                usable: true,

                ids: ids(None, ed(b"A")),

            })),

            ChannelState::Building(pending_channel(ids(None, ed(b"A")))),

        ];

        // should return the open channel

        let target = FakeBuildSpec::new(ids(None, ed(b"A")));

        with_permutations(&channels, |x| {

            assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[0]));

        });

        // an unusable open channel and a pending channel

        let channels = [

            ChannelState::Open(open_channel(FakeChannel {

                usable: false,

                ids: ids(None, ed(b"A")),

            })),

            ChannelState::Building(pending_channel(ids(None, ed(b"A")))),

        ];

        // should return the pending channel

        let target = FakeBuildSpec::new(ids(None, ed(b"A")));

        with_permutations(&channels, |x| {

            assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[1]));

        });

    }

    #[test]

    fn best_channel_many() {

        // some misc channels (as we make `choose_best_channel` more complex, hopeful we can add

        // more channels here)

        let channels = [

            ChannelState::Open(open_channel(FakeChannel {

                usable: false,

                ids: ids(None, ed(b"A")),

            })),

            ChannelState::Open(open_channel(FakeChannel {

                usable: true,

                ids: ids(None, ed(b"A")),

            })),

            ChannelState::Building(pending_channel(ids(None, ed(b"A")))),

            ChannelState::Building(pending_channel(ids(None, None))),

        ];

        // should return the open+usable channel

        let target = FakeBuildSpec::new(ids(None, ed(b"A")));

        with_permutations(&channels, |x| {

            assert_opt_ptr_eq!(choose_best_channel(x, &target), Some(&channels[1]));

        });

    }

    #[test]

    fn test_open_channel_is_allowed() {

        // target with an ed relay id

        let target = FakeBuildSpec::new(ids(None, ed(b"A")));

        // not allowed: unusable channel

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: false,

                ids: ids(None, ed(b"A")),

            }),

            &target,

        ));

        // allowed: usable channel with correct relay id

        assert!(open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(None, ed(b"A")),

            }),

            &target,

        ));

        // not allowed: usable channel with incorrect relay id

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(None, ed(b"B")),

            }),

            &target,

        ));

        // not allowed: usable channel with no relay ids

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(None, None),

            }),

            &target,

        ));

        // allowed: usable channel with additional relay id

        assert!(open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(rsa(b"X"), ed(b"A")),

            }),

            &target,

        ));

        // not allowed: usable channel with missing ed relay id

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(rsa(b"X"), None),

            }),

            &target,

        ));

        // target with no relay id

        let target = FakeBuildSpec::new(ids(None, None));

        // not allowed: unusable channel

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: false,

                ids: ids(None, None),

            }),

            &target,

        ));

        // allowed: usable channel with no relay ids

        assert!(open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(None, None),

            }),

            &target,

        ));

        // target with multiple relay ids

        let target = FakeBuildSpec::new(ids(rsa(b"X"), ed(b"A")));

        // not allowed: unusable channel

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: false,

                ids: ids(rsa(b"X"), ed(b"A")),

            }),

            &target,

        ));

        // allowed: usable channel with correct relay ids

        assert!(open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(rsa(b"X"), ed(b"A")),

            }),

            &target,

        ));

        // not allowed: usable channel with partial relay ids

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(None, ed(b"A")),

            }),

            &target,

        ));

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(rsa(b"X"), None),

            }),

            &target,

        ));

        // not allowed: usable channel with one incorrect relay id

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(rsa(b"X"), ed(b"B")),

            }),

            &target,

        ));

        assert!(!open_channel_is_allowed(

            &open_channel(FakeChannel {

                usable: true,

                ids: ids(rsa(b"Y"), ed(b"A")),

            }),

            &target,

        ));

    }

    #[test]

    fn test_pending_channel_maybe_allowed() {

        // target with an ed relay id

        let target = FakeBuildSpec::new(ids(None, ed(b"A")));

        // allowed: channel with same relay id

        assert!(pending_channel_maybe_allowed(

            &pending_channel(ids(None, ed(b"A"))),

            &target,

        ));

        // not allowed: channel with additional relay id

        assert!(!pending_channel_maybe_allowed(

            &pending_channel(ids(rsa(b"X"), ed(b"A"))),

            &target,

        ));

        // target with multiple relay ids

        let target = FakeBuildSpec::new(ids(rsa(b"X"), ed(b"A")));

        // allowed: channel with same relay ids

        assert!(pending_channel_maybe_allowed(

            &pending_channel(ids(rsa(b"X"), ed(b"A"))),

            &target,

        ));

        // allowed: channel with fewer relay ids

        assert!(pending_channel_maybe_allowed(

            &pending_channel(ids(None, ed(b"A"))),

            &target,

        ));

        assert!(pending_channel_maybe_allowed(

            &pending_channel(ids(rsa(b"X"), None)),

            &target,

        ));

        // not allowed: channel with no relay ids

        assert!(!pending_channel_maybe_allowed(

            &pending_channel(ids(None, None)),

            &target,

        ));

        // target with no relay ids

        let target = FakeBuildSpec::new(ids(None, None));

        // not allowed: channel with a relay id

        assert!(!pending_channel_maybe_allowed(

            &pending_channel(ids(None, ed(b"A"))),

            &target,

        ));

        // not allowed: channel with no relay ids

        assert!(!pending_channel_maybe_allowed(

            &pending_channel(ids(None, None)),

            &target,

        ));

    }

}