RIFT Auto-EVPN

use std::cell::{RefCell, RefMut};
use std::cmp::{max, min};
use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::fmt::Debug;
use std::net::{Ipv4Addr, Ipv6Addr};
use std::str::FromStr;
use itertools::interleave;
use itertools::Itertools;
use rayon::slice::ParallelSliceMut;

use foundation::models::common::{FabricIDType, IPv6PrefixType};
use foundation::models::common::LevelType;
use foundation::models::common::HierarchyIndications;
use foundation::models::common::IPPrefixType;
use foundation::models::common::IPv4Address;
use foundation::models::common::IPv4PrefixType;
use foundation::models::common::IPv6Address;
use foundation::models::common::LEAF_LEVEL;
use foundation::models::common_services::ServiceErrorType;
use foundation::models::common_evpn::{DEFAULT_EVIS, DEFAULT_VLANS_PER_EVI,
                                          DEFAULT_EVPNZTP_STARTUP_DELAY, DEFAULT_FABRIC_ID, DEFAULT_INTERFACE_CE_DELAY,
                                          DEFAULT_LEAF_DELAY, EVPNAnyRole, EVPNLeafRole,
                                          EVPNRoles, EVPNRRRole, UnitType};
use foundation::models::common_evpn::CEInterfaceType;
use foundation::models::common_evpn::CommunityType;
use foundation::models::common_evpn::EVPNEVI;
use foundation::models::common_evpn::IRBType;
use foundation::models::common_evpn::MACVRFNumberType;
use foundation::models::common_evpn::PartialEVPNEVI;
use foundation::models::common_evpn::RTDistinguisherType;
use foundation::models::common_evpn::VLANIDType;
use foundation::models::common_evpn::VLANType;
use foundation::models::common_evpn::VNIType;
use ILLEGAL_SYSTEM_I_D;
use NodeCapabilities;
use UnsignedSystemID;

/// indicates how many RRs we're computing in EVPN ZTP
pub const MAX_AUTO_EVPN_RRS: usize = 3;
/// indicates the fabric has no ID, used in computations to omit effects of fabric ID
pub const NO_FABRIC_ID: FabricIDType = 0;
/// invalid MACVRF number, MACVRFs start from 1
pub const NO_MACVRF: MACVRFNumberType = 0;

/// unique v6 prefix for all nodes starts with this
pub const AUTO_EVPN_V6PREF: &str = "FD00:A1";
/// how many bytes in a v6pref for RRs
pub const AUTO_EVPN_V6PREFLEN: usize = 8 * 3;
/// unique v6 prefix for route reflector purposes starts like this
pub const AUTO_EVPN_V6RRPREF: &str = "FD00:A2";
/// unique v6 prefix for type-5 purposes starts like this
pub const AUTO_EVPN_V6T5PREF: &str = "FD00:A3";
/// unique v6 prefix for IRB prefix purposes
pub const AUTO_EVPN_V6IRBPREF: &str = "FD00";
/// unique v6 prefix first byte for v6 IRB prefix purposes
pub const AUTO_EVPN_V6IRBPREFFIRSTBYTE: u8 = 0xA4;
/// unique v4 prefix for IRB purposes
pub const AUTO_EVPN_V4IRBPREF: &str = "10";
/// 3 bytes of prefix type and then we have fabric ID after that
pub const AUTO_EVPN_V6_FABPREFIXLEN: usize = 8 + 8 + 8 + 16;

/// per RFC magic
const RT_TARGET_HIGH: CommunityType = 0;
const RT_TARGET_LOW: CommunityType = 0;

/// first available VLAN number
pub const FIRST_VLAN: VLANIDType = 1;
// maximum vlan number one less than maximum to use as bitmask
pub const MAX_VLAN: VLANIDType = 4095;
/// constant VLAN shift
pub const FIRST_VLAN_SHIFT: VLANIDType = 16;
/// NATIVE VLAN number
pub const NATIVE_VLAN: VLANIDType = 1;

/// abstract description of VLAN properties for a derived VLAN
pub struct VLANDescription {
    pub vlan_id: VLANIDType,
    pub name: String,
    /// can this VLAN be stretched across multiple fabrics
    pub stretchable: bool,
    pub native: bool,
}

/// maximum number of VLANs per MACVRF
pub const MAX_VLANS_PER_EVI: usize = 15;

pub type VLANStretchableType = bool;
pub type VLANNativeType = bool;

pub const EXTRATYPE5_RD_DISTINGUISHER: u32 = 0xffff_ffff;

/// high bits of type 5 VNI
const TYPE5VNIHIGH: VNIType = 0x0080_0000;
/// bitmask for type 2 VNI
const TYPE2VNIMASK: VNIType = 0x00ff_ffff ^ TYPE5VNIHIGH;

/// random seeds used in several algorithms to increase entropy
pub const RANDOMSEEDS: [u64; 4] = [
    27008318799u64,
    67438371571,
    37087353685,
    88675895388,
];

pub(crate) fn auto_evpn_sids2rrs(mut v: Vec<UnsignedSystemID>) -> Vec<UnsignedSystemID> {
    v.par_sort_unstable();
    let r = if v.len() > 2 {
        let mut s = v.split_off(v.len() / 2);
        s.reverse();
        interleave(v.into_iter(), s.into_iter()).collect()
    } else {
        v
    };

    r
}

pub(crate) fn auto_evpn_v62octets(a: Ipv6Addr) -> Vec<u8> {
    a.octets().iter().cloned().collect()
}

/// fabric prefixes derived instead of advertising default on the fabric to allow
/// for default route on ToF or leaves
pub fn auto_evpn_fid2fabric_prefixes(fid: FabricIDType) -> Result<Vec<IPPrefixType>, ServiceErrorType> {
    vec![
        (auto_evpn_fidsidv6loopback(fid, ILLEGAL_SYSTEM_I_D as _), AUTO_EVPN_V6PREFLEN),
        (auto_evpn_fidrrpref2rrloopback(fid, ILLEGAL_SYSTEM_I_D as _), AUTO_EVPN_V6PREFLEN),
    ]
        .into_iter()
        .map(|(p, _)|
            match p {
                Ok(_) => Ok(
                    IPPrefixType::Ipv6prefix(
                        IPv6PrefixType {
                            address: auto_evpn_v62octets(p?),
                            prefixlen: AUTO_EVPN_V6PREFLEN as _,
                        })),
                Err(e) => Err(e),
            }
        )
        .collect::<Result<Vec<_>, _>>()
}

/// local address with encoded fabric ID and system ID for collision free identifiers. Basis
/// for several different prefixes.
pub fn auto_evpn_v6prefixfidsid2loopback(v6pref: &str, fid: FabricIDType,
                                         sid: UnsignedSystemID) -> Result<Ipv6Addr, ServiceErrorType> {
    assert!(fid != 0);
    let a = format!("{}{:02X}::{}",
                    v6pref,
                    fid as u16,
                    sid.to_ne_bytes()
                        .iter()
                        .chunks(2)
                        .into_iter()
                        .map(|chunk|
                            chunk.fold(0u16, |v, n| (v << 8) | *n as u16))
                        .map(|v| format!("{:04X}", v))
                        .collect::<Vec<_>>()
                        .into_iter()
                        .join(":")
    );

    Ipv6Addr::from_str(&a)
        .map_err(|_| ServiceErrorType::INTERNALRIFTERROR)
}

/// auto evpn V6 loopback for RRs
pub fn auto_evpn_fidrrpref2rrloopback(fid: FabricIDType,
                                      preference: u8) -> Result<Ipv6Addr, ServiceErrorType> {
    auto_evpn_v6prefixfidsid2loopback(AUTO_EVPN_V6RRPREF, fid, (1 + preference) as _)
}

/// auto evpn BGP router ID
pub fn auto_evpn_sidfid2bgpid(fid: FabricIDType, sid: UnsignedSystemID) -> u32 {
    assert!(fid != 0);
    let hs: u32 = ((sid & 0xffff_ffff_0000_0000) >> 32) as _;
    let mut ls: u32 = (sid & 0xffff_ffff) as _;
    ls = ls.rotate_right(7) ^ (fid as u32).rotate_right(13);
    max(1, hs ^ ls) // never a 0
}

/// route target bytes are type0/0 and then add EVI
pub fn auto_evpn_evi2rt(evi: MACVRFNumberType) -> CommunityType {
    let wideevi = (evi + 1) as CommunityType;

    (RT_TARGET_HIGH << (64 - 8)) | (RT_TARGET_LOW << 64 - 16) |
        ((wideevi) << 17) |
        ((wideevi))
}

/// type-5 VNI for an EVI
pub fn auto_evpn_fidevi2type5vni(fid: FabricIDType, evi: MACVRFNumberType) -> VNIType {
    TYPE5VNIHIGH | auto_evpn_fidevivid2vni(fid, evi, 0)
}

/// type-2 VNI for a specific VLAN
pub fn auto_evpn_fidevivid2vni(fid: FabricIDType, evi: MACVRFNumberType, vlanid: VLANIDType) -> VNIType {
    let rfid = fid as i32;
    let revi = evi as i32;
    let rvlan = vlanid as i32;
// mask out high bits, VNI is only 24 bits
    TYPE2VNIMASK &
        (
            rfid.rotate_left(16) ^
                revi.rotate_left(12) ^
                rvlan
        )
}

/// maximum VLANs per EVI supported by auto evpn when deriving
pub fn auto_evpn_vlan_description_table<'a>(vlans: usize)
                                            -> Result<&'a [(VLANIDType, VLANStretchableType, VLANNativeType)], ServiceErrorType> {
    // up to 15 vlans can be activated
    const VLANSARRAY: [(i16, bool, bool); MAX_VLANS_PER_EVI] = [
        (NATIVE_VLAN, true, true, ),
        (FIRST_VLAN_SHIFT, true, false, ),
        (FIRST_VLAN_SHIFT + 1, true, false, ),
        (FIRST_VLAN_SHIFT + 2, true, false, ),
        (FIRST_VLAN_SHIFT + 3, false, false, ),
        (FIRST_VLAN_SHIFT + 4, false, false, ),
        (FIRST_VLAN_SHIFT + 5, false, false, ),
        (FIRST_VLAN_SHIFT + 6, false, false, ),
        (FIRST_VLAN_SHIFT + 7, false, false, ),
        (FIRST_VLAN_SHIFT + 8, false, false, ),
        (FIRST_VLAN_SHIFT + 9, false, false, ),
        (FIRST_VLAN_SHIFT +10, false, false, ),
        (FIRST_VLAN_SHIFT +11, false, false, ),
        (FIRST_VLAN_SHIFT +12, false, false, ),
        (FIRST_VLAN_SHIFT +13, false, false, ),
    ];

    if vlans > VLANSARRAY.len() {
        return Err(ServiceErrorType::INVALIDPARAMETERVALUE)
    }

    Ok(&VLANSARRAY[..vlans])
}

/// delivers the vlan description that can be used to generate vlans for a
/// specific fabric ID and a MACVRF number
pub fn auto_evpn_fidevivlansvlans2desc(fid: FabricIDType, macvrf: MACVRFNumberType,
                                       vlans: usize) -> Vec<VLANDescription> {

    assert!(NO_MACVRF != macvrf);

    // abstract description of derived VLANs
    let vlan_table = auto_evpn_vlan_description_table(vlans)
        .expect("vlan table in AUTO EVPN incorrect");

    let vlanshift = vlan_table
        .iter()
        .map(|(vl, _, _)| *vl as usize)
        .max()
        .expect("vlan table in AUTO EVPN incorrect")
        .checked_next_power_of_two()
        .expect("vlan table in AUTO EVPN incorrect");

    assert!(vlan_table.len() < FIRST_VLAN_SHIFT as _);

    vlan_table
        .iter()
        .map(move |(vid, stretch, native_)| {
            let stretchedfid = if !stretch {
                fid
            } else {
                NO_FABRIC_ID
            };

            let mut vlan_id = *vid ^ stretchedfid
                .rotate_left(max(16, vlanshift as u32 + 8)) as VLANIDType;
            // leave space for VLANs in the encoding
            vlan_id ^= macvrf.rotate_left(vlanshift as _) as VLANIDType;

            vlan_id %= MAX_VLAN;
            vlan_id = max(1, vlan_id);

            VLANDescription {
                vlan_id: vlan_id as _,
                name: format!("V{}", vlan_id),
                stretchable: *stretch,
                native: *native_,
            }
        })
        .collect()
}

/// IRB interface number.
/// fid/evi combination shifted up to not interfere with the VLAN-ID
/// and then add the VLAN-ID
pub fn auto_evpn_fidevivid2irb(fid: FabricIDType, evi: MACVRFNumberType, vid: VLANIDType) -> UnitType {

    assert!(NO_MACVRF != evi);

    let mut v = (fid as UnitType ^ evi.rotate_left(4) as UnitType) << (16 - FIRST_VLAN.leading_zeros());

    v = 1 + v.wrapping_add(vid) % MAX_VLAN;
    v % (UnitType::MAX - 1)
}

/// route distinguisher derivation
pub fn auto_evpn_sidfid2rd(sid: UnsignedSystemID, fid: FabricIDType, extra: u32) -> RTDistinguisherType {
    // generate type 0 route distinguisher, first 2 bytes 0 and then 6 bytes
    assert!(fid != NO_FABRIC_ID);
    // shift the 2 bytes we loose
    let convsid = sid as RTDistinguisherType;
    let hs = ((sid & 0xffff_0000_0000_0000) >> 32) as RTDistinguisherType;
    let mut ls: RTDistinguisherType = convsid & 0x0000_ffff_ffff_ffff;
    ls ^= hs;
    ls ^= (fid as RTDistinguisherType).rotate_left(16);
    ls ^= extra as RTDistinguisherType;
    ls
}

/// v4 subnet derivation
pub fn auto_evpn_v4prefixfidevividsid2v4subnet(v4pref: &str, fid: FabricIDType,
                                               evi: MACVRFNumberType, vid: VLANIDType,
                                               sid: UnsignedSystemID) -> Result<IPv4PrefixType, ServiceErrorType> {

    assert!(NO_MACVRF != evi);

    // fid can be 0 for stretched v4subnets
    let mut sub = evi.to_ne_bytes().iter()
        .fold((RANDOMSEEDS[0] & 0xff) as u8, |r, e| r.rotate_left(1) ^ e.rotate_right(1));
    sub ^= fid.to_ne_bytes().iter()
        .fold((RANDOMSEEDS[1] & 0xff) as u8, |r, e| r.rotate_left(2) ^ e.rotate_right(1));
    sub ^= vid.to_ne_bytes().iter()
        .fold((RANDOMSEEDS[2] & 0xff) as u8, |r, e| r.rotate_left(3) ^ e.rotate_right(1));

    let subnet = sub % 254; // make sure we don't show multicast subnet

    let _host = sid.to_ne_bytes().iter()
        .fold(0u16, |r, e| r.rotate_left(3) ^ e.rotate_right(3) as u16);

    let a = format!("{}.{}.{}.{}",
                    v4pref,
                    subnet,
                    0,
                    1,
    );

    Ok(
        IPv4PrefixType {
            address: Ipv4Addr::from_str(&a)
                .map_err(|_| {
                    ServiceErrorType::INTERNALRIFTERROR
                })?
                .octets()
                .iter()
                .fold(0u32, |v, nv| v << 8 | (*nv as u32)) as IPv4Address
            ,
            prefixlen: 16,
        }
    )
}

/// generic v6 bytes derivation used for different purposes
pub fn auto_evpn_v6hash(fid: FabricIDType, evi: MACVRFNumberType, vid: VLANIDType, sid: UnsignedSystemID)
                        -> [u8; 8] {

    let mut sub = evi.to_ne_bytes().iter()
        .fold(RANDOMSEEDS[3], |r, e| r.rotate_left(6) ^ e.rotate_right(4) as u64);
    sub ^= fid.to_ne_bytes().iter()
        .fold(RANDOMSEEDS[0], |r, e| r.rotate_left(6) ^ e.rotate_right(4) as u64);
    sub ^= vid as u64;
    sub ^= sid;

    sub.to_ne_bytes()
}

pub fn auto_evpn_fidevividsid2v6subnet(fid: FabricIDType, evi: MACVRFNumberType,
                                       vid: VLANIDType,
                                       sid: UnsignedSystemID) -> Result<IPv6PrefixType, ServiceErrorType> {

    assert!(NO_MACVRF != evi);

    let sb = auto_evpn_v6hash(fid, evi, vid, sid);

    let a = format!("{}:{:02X}{:02X}:{:02X}{:02X}:{:02X}{:02X}::1",
                    AUTO_EVPN_V6IRBPREF,
                    AUTO_EVPN_V6IRBPREFFIRSTBYTE,
                    sb[3] ^ sb[0],
                    sb[4] ^ sb[1],
                    sb[5] ^ sb[2],
                    sb[6],
                    sb[7],
    );

    Ok(IPv6PrefixType {
        address: Ipv6Addr::from_str(
            &a)
            .map_err(|_| {
                ServiceErrorType::INTERNALRIFTERROR
            })?
            .octets()
            .to_vec(),
        prefixlen: 64,
    })
}

/// MAC address derivation for IRB
pub fn auto_evpn_fidevividsid2mac(fid: FabricIDType, evi: MACVRFNumberType,
                                  vid: VLANIDType, sid: UnsignedSystemID) -> Vec<u8> {

    let sb = auto_evpn_v6hash(fid, evi, vid, sid);

    vec![0x02,
         sb[3] ^ sb[0],
         sb[4] ^ sb[1],
         sb[5] ^ sb[2],
         sb[6],
         sb[7],
    ]
}

/// v4 loopback address derivation for every node in auto-evpn
pub fn auto_evpn_fidsid2v4loopback(fid: FabricIDType, sid: UnsignedSystemID) -> IPv4Address {
    let mut derived = sid.to_ne_bytes().iter()
        .fold(0 as IPv4Address, |p, e| (p << 4) ^ (*e as IPv4Address));
    derived ^= fid as IPv4Address;
    // use the byte we loose for entropy
    derived ^= derived >> 24;
    // and sanitize for loopback range
    derived &= 0x00ff_ffff;

    let m = ((127 as IPv4Address) << 24) | derived;
    m as _
}

/// V6 loopback derivation for every node in auto-evpn
pub fn auto_evpn_fidsidv6loopback(fid: FabricIDType,
                                  sid: UnsignedSystemID) -> Result<Ipv6Addr, ServiceErrorType> {
    auto_evpn_v6prefixfidsid2loopback(AUTO_EVPN_V6PREF, fid, sid)
}

#[allow(non_snake_case)]
pub fn auto_evpn_fid2private_AS(fid: FabricIDType) -> u32 {
    assert!(fid != NO_FABRIC_ID);
    // range 4200000000-4294967294
    const DIFF: u32 = 4_294_967_294 - 4_200_000_000;
    64496 + ((fid as u32) << 3) % DIFF
}

pub fn auto_evpn_fid2clusterid(fid: FabricIDType) -> u32 {
    auto_evpn_fid2private_AS(fid)
}