//! IPv4 port policy summarisation - approximate algorithm

//!

//! <https://spec.torproject.org/dir-spec/computing-microdescriptors.html#item:p>

//!

//! Contrast precise summaries, in `tor-netdoc/src/types/policy/summary.rs`.

use super::*;

// These are very specific to this area; let's not have them in the crate prelude.

use tor_netdoc::types::policy::{

    AddrPolicy, AddrPortPattern, IpPattern, PortPolicy, PortRange, RuleKind,

};

/// How many rejected IPv4 addresses are allowed before we consider the port closed

///

/// Has the same value as [`tor_netdoc::types::policy::PortSummaryThresholds::v4`].

/// But we recapitulate it here, because we mustn't change the output of *this* algorithm

/// without a consensus method change.

///

/// I.e., changing this requires a consensus method change.

const MAX_REJECTED: u32 = 1 << 25;

/// Allows us to write the private ranges in CIDR-like format

macro_rules! ipnet_consts { { $( $a:literal $( , $bcd:literal )* / $p:literal; )* } => {

    &[ $(

        Ipv4Net::new_assert(Ipv4Addr::new($a $(, $bcd)*), $p),

    )* ]

} }

/// Private networks, disregarded for counting rejected number of addresses

///

/// Cut and paste from the spec, with light formatting editing:

/// add semicolon separators; change `.` to `,`; use `//` for comments.

// (We can't use `.` because bits of the input IPv4 addresses end up looking like float literals!)

///

/// <https://spec.torproject.org/dir-spec/computing-microdescriptors.html#item:p:public-ipv4>

///

/// Changing this requires a consensus method change.

/// If we ever do that, we may want to mark these entries with consensus method(s)

/// that they're used in, or have multiple lists, or something.

const PRIVATE_NETWORKS: &[Ipv4Net] = ipnet_consts![

    0,0,0,0/8; // This Network, RFC791 3.2

    10,0,0,0/8; 172,16,0,0/12; 192,168,0,0/16; // Private-Use, RFC1918

    100,64,0,0/10; // Shared Address Space, RFC6598

    127,0,0,0/8; // Loopback, RFC1122 3.2.1.3

    169,254,0,0/16; // Link Local, RFC3927

    192,0,0,0/24; // IETF Protocol Assignments, RFC6890

    192,0,2,0/24; 198,51,100,0/24; 203,0,113,0/24; // Documentation (TEST-NET-[123]), RFC5737

    198,18,0,0/15; // Benchmarking, RFC2544

    192,31,196,0/24; // AS112-v4 (reverse lookup for private addrs) RFC7535

    192,175,48,0/24; // Direct Delegation AS112 RFC5734

    255,255,255,255/32; // “Limited Broadcast”, RFC8190, RFC919 s7

];

/// Port resolution algorithm, main state

///

/// We implement the algorithm specified in

/// <https://spec.torproject.org/dir-spec/consensus-formats.html#item:p>.

///

/// As noted there, we perform the algorithm in parallel, and independently, for each port.

/// But, we use a rangemap so that we can deal with ranges rather than individual ports.

///

/// We loop over all the rules, once, in `summarise_policy_v4_approximate`.

/// This is done in *forward* order; we handle the summarisation algorithm's early exit

/// by having an explicit `Stopped` state in the per-port state.

///

/// We interpret each rule, in `ResolutionState::apply_rule`.

/// That decides what effect the rule has on the relevant ports,

/// and calls `ResolutionState::update_for_ports` to make the appropriate state change.

#[derive(Debug)]

struct ResolutionState {

    /// State of the algorithm for each port

    ///

    /// This always contains *some* entry for 1..65535, but nothing for 0.

    port_map: RangeInclusiveMap<u16, PortState>,

    /// How many ports we have resolve (ie, are in state `Stopped`)

    ///

    /// When this reaches 2^16-1, *all* our parallel loops have stopped,

    /// and we can skip processing the rest of the rules.

    total_resolved: u16,

}

/// The state of the algorithm for any one port.

///

/// (Actually, one of these is stored for a *range* of ports.

/// They are split up and joined as necessary by `rangemap_mutate_range`

/// and `RangeInclusiveMap`.)

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

enum PortState {

    /// The algorithm for this port has stopped, yielding `RuleKind`

    Stopped(RuleKind),

    /// The algorithm for this port is continuing

    Running(PortStateRunning),

}

use PortState as PS;

/// State of the still-running algorithm for any one port

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

struct PortStateRunning {

    /// Rejected address count (saturating)

    rejected: u32,

}

/// "Error" thrown by algorithm computations

#[derive(Debug, derive_more::From)]

enum EarlyTermination {

    /// Pseudo-error, thrown to stop the algorithm early when every port has been decided

    EveryPortResolved,

    /// Bug, "crash" - we don't want to panic, ever

    Bug(#[from] Bug),

}

/// Return the number of hosts in this network, clamped to `u32::MAX`

///

/// Very like `Net::host_count_saturating` in tor-netdoc `summary.rs`,

/// but that returns `u128` and isn't public (and maybe doesn't want to be),

/// and takes less care to avoid impossible panics,

/// whereas this is simpler because it can be IPv4-specific.

impl ResolutionState {

    /// Update the state, for those of the relevant ports which are still running

    ///

    /// For each port in `ports` that hasn't `Stopped`, calls `update`.

    /// `update` should return the new state, which might be `Running` or `Stopped`.

    ///

    /// Updates `total_resolved`, and throws `EveryPortResolved` if appropriate.

        // Silently disregard port 0 as per the spec

        //  https://spec.torproject.org/dir-spec/computing-consensus.html#exit-summary:semantics

        } else {

        };

            // important that we shadow `ports` here

                };

                    // Fine points, that make this correct:

                    //

                    // We were Running before, and now we're Stopped, so all these ports

                    // are indeed *newly* Stopped.

                    //

                    // If we return `Err`, the update we make to *this* port range

                    // will indeed be applied (see docs for rangemap_mutate_range),

                    // so we don't lose *this* port range's store.

                    //

                    // And, in that case ranges overlapping with the outer ports

                    // will not be processed, but that's OK because we only throw Err

                    // if we know they've already been made Stopped.

                    //

                    // Use checked arithmetic to avoid panics, and an IEFE to catch the Nones.

                                // start is always >0, so this is at most u16::MAX, OK

                        )

                    })()

                    // Compare with 65535, not 65536, since we never add anything for port 0

                    #[allow(clippy::absurd_extreme_comparisons)] // clippy wants ==, urgh

        )

    /// Perform one step of the resolution/summarisation algorithm: apply one rule

    ///

    /// This applies the rule, in parallel, to all the ports it applies to.

    /// Ports where the algorithm has already stopped are skipped

    /// (this is done by code in `update_for_ports`).

        use IpPattern as IPP;

        // This code is fairly specific to the fact that we're doing this only for IPv4.

        // To support IPv6 generically, we'd need a whole panoply of v4/v6 generics

        // for IpNet, the private address nets, the max rejected, and so on.

        //

        // I think we probably won't ever want to do exit summarisation in dirauths for v6.

        // Having the relay do its own summary is fine.

        //

        // But, anyway here are some notes for how to support V6:

        //  - Expose the Net trait from tor-netdoc's summariser.

        //    Under some other name, presumably, and maybe it should be implemented

        //    for IpvXAddr rather IpvXNet.

        //  - In each match below, use those trait methods.

        //    To avoid missing one, maybe call a trait function on pat.addrs

        //    and match on the return value instead.

        //    Or maybe reuse the code in tor-netdoc's `Summariser::apply_rule`.

        //  - Make our own subtrait of Net, and

        //    make MAX_REJECTED and PRIVATE_NETWORKS trait constants in it

        //  - Make PortStateRunning.rejected big enough for v6

        //    (this might mean adding generics to PortState)

        //  - `grep -i ipv` this file to see what you missed

        //  - consider calculating v4 and v6 in parallel

            // From the spec:

            //

            // "* Disregard items whose addrspec matches no IPv4 addresses"

                // "* Disregard `reject`s whose addrspec is an IPv4 subnet

                //    completely contained within a private network (see below)."

                //

                // (As per the spec's suggested approximation, we treat partially-private

                // rejects as public, rather than counting the addresses precisely.)

                {

                // "* For other `reject` lines, add the size of the subnet

                //    to the "rejected address count"."

                    // Avoid overflow; if we saturate, we'll treat it as rejected - fine.

                        // * If the "rejected address count" exceeds the 2^25 limit,

                        //   stop and list the port as closed.

                    } else {

                    }

            }

            (RuleKind::Reject, IPP::All) => {

                // This is an "other `reject` line" - but we didn't handle it above.

                // It necessarily blows the limit.

                    //

            }

            // "* For an `accept` item which matches all IPv4 addresses,

            //    stop and list the port as open."

            (RuleKind::Accept, IPP::All) => {

                // All-addresses patterns

                    //

            }

                    // IPv4-only patterns matching all IPv4 addresses

                } else {

                    // Ignore IPv4 accepts which don't accept every address.

                }

            }

        }

}

/// IPv4 port policy summarisation, for use by dirauths

///

/// <https://spec.torproject.org/dir-spec/computing-microdescriptors.html#item:p>

///

/// This is an approximate algorithm.

///

/// It is for use by directory authorities when processing routerdescs into

/// microdescs.

///

/// Should *not* be used by relays, or other entities processing reasonably-trusted

/// policy data.  Those should use [`AddrPolicy::summarise_precise`].

///

/// Only implemented for IPv4.

        //

    );

        }

        // Otherwise, on reaching the end of the exit policy items, list the port as open.

    })();

    }

                PS::Stopped(RuleKind::Accept) => Some(

                ),

                }

            })

#[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 @@ -->

    use super::*;

    use derive_deftly::Deftly;

    use tor_netdoc::parse_testcase_from_netdoc;

    use tor_netdoc::types::policy::PortSummaryThresholds;

    /// cut-down (IPv4 only) version of tor-netdoc's summary.rs version

    const REJECT_PRECISELY_ALLOWED_AMOUNT: &str = r"

                accept *:100

                reject 1.0.0.0/8:400-419

                reject 2.0.0.0/8:410-429

                reject 0.0.0.0/0:1-399

                reject 0.0.0.0/0:430-65535

    ";

    #[derive(Deftly)]

    #[derive_deftly(tor_netdoc::NetdocParseableFields)]

    struct IsPreciseTestCase {

        /// Input policy, `accept` and `reject` lines

        #[deftly(netdoc(flatten))]

        full: AddrPolicy,

    }

    fn method_for_testing() -> TrackedConsensusMethod {

        TrackedConsensusMethod::new(SupportedConsensusMethod::MAX)

    }

    /// Run one test case where the approx summary is, in fact, precise

    ///

    /// The expected output is calculated with [`AddrPolicy::summarise_precise`]

    /// (which uses a quite different implementation strategy to the code here.)

    fn chk_is_precise(input_doc: &str) {

        let case: IsPreciseTestCase = parse_testcase_from_netdoc(input_doc);

        let approx = summarise_policy_v4_approximate(

            //

            &case.full,

            &method_for_testing(),

        )

        .unwrap();

        let precise = case.full.summarise_precise(

            // if the thresholds change in a new consensus method, we'll probably need

            // to explicitly change the value here and maybe test both thresholds

            &PortSummaryThresholds::default(),

            PRIVATE_NETWORKS.iter().copied().map(IpNet::V4),

        );

        assert_eq!(approx, precise.v4);

    }

    #[test]

    fn basics() {

        chk_is_precise(r"p4 accept 1-65535");

        chk_is_precise(r"p4 reject 1-65535");

        chk_is_precise(r"p4 accept *:*");

        chk_is_precise(r"p4 reject *:25");

    }

    #[test]

    fn edge_cases() {

        chk_is_precise(REJECT_PRECISELY_ALLOWED_AMOUNT);

        // reject a private net, proving it is disregarded

        chk_is_precise(&format!(

            r"  {REJECT_PRECISELY_ALLOWED_AMOUNT}

                reject 100.64.1.0/24:* "

        ));

        // Reject one more address

        chk_is_precise(&format!(

            r"  {REJECT_PRECISELY_ALLOWED_AMOUNT}

                reject 4.0.0.0/32:415-425 "

        ));

    }

    #[derive(Deftly)]

    #[derive_deftly(tor_netdoc::NetdocParseableFields)]

    struct ImpreciseTestCase {

        /// Input policy, `accept` and `reject` lines

        #[deftly(netdoc(flatten))]

        full: AddrPolicy,

        /// Expected IPv4 summary

        p4: PortPolicy,

    }

    /// Run one test case where the approx summary is imprecise

    ///

    /// The expected output is `p4` in the test case.

    fn chk_imprecise(input_doc: &str) {

        let case: ImpreciseTestCase = parse_testcase_from_netdoc(input_doc);

        let approx = summarise_policy_v4_approximate(

            //

            &case.full,

            &method_for_testing(),

        )

        .unwrap();

        assert_eq!(approx, case.p4);

        let precise = case.full.summarise_precise(

            // if the thresholds change in a new consensus method, we'll probably need

            // to explicitly change the value here and maybe test both thresholds

            &PortSummaryThresholds::default(),

            PRIVATE_NETWORKS.iter().copied().map(IpNet::V4),

        );

        assert_ne!(approx, precise.v4);

    }

    #[test]

    fn approximations() {

        chk_imprecise(&format!(

            r"  accept 1.0.0.0/32:417 # ignored non-wildcard accept

                {REJECT_PRECISELY_ALLOWED_AMOUNT}

                reject 4.0.0.0/32:415-425

                p4 accept 100,400-414,420-429 " // 417 missing

        ));

        chk_imprecise(

            r"  reject 10.0.0.0/7:10 # reject 2^25 addresses, but they're half-private

                reject 4.0.0.0/32:10-20 # tip over the edge

                p4 reject 10 ",

        );

    }

}