rns_core/transport/

pathfinder.rs

use super::tables::{PathEntry, PathSet};
use crate::constants;

/// Extract emission timestamp from bytes [5:10] of a random_blob (big-endian u64).
pub fn timebase_from_random_blob(blob: &[u8; 10]) -> u64 {
    let mut bytes = [0u8; 8];
    bytes[3..8].copy_from_slice(&blob[5..10]);
    u64::from_be_bytes(bytes)
}

/// Maximum emission timestamp across all random blobs.
pub fn timebase_from_random_blobs(blobs: &[[u8; 10]]) -> u64 {
    let mut timebase: u64 = 0;
    for blob in blobs {
        let emitted = timebase_from_random_blob(blob);
        if emitted > timebase {
            timebase = emitted;
        }
    }
    timebase
}

/// Extract the random_blob from announce packet data.
///
/// Located at offset `KEYSIZE/8 + NAME_HASH_LENGTH/8` = 64 + 10 = 74,
/// length 10 bytes.
pub fn extract_random_blob(packet_data: &[u8]) -> Option<[u8; 10]> {
    let offset = constants::KEYSIZE / 8 + constants::NAME_HASH_LENGTH / 8;
    if packet_data.len() < offset + 10 {
        return None;
    }
    let mut blob = [0u8; 10];
    blob.copy_from_slice(&packet_data[offset..offset + 10]);
    Some(blob)
}

#[derive(Debug, PartialEq, Eq)]
pub enum PathDecision {
    Add,
    Reject,
}

/// Full path update decision tree from Transport.py:1604-1686.
///
/// Determines whether an incoming announce should update the path table.
pub fn should_update_path(
    existing: Option<&PathEntry>,
    announce_hops: u8,
    announce_emitted_ts: u64,
    random_blob: &[u8; 10],
    path_is_unresponsive: bool,
    now: f64,
    prefer_shorter_path: bool,
) -> PathDecision {
    // Hop limit
    if announce_hops > constants::PATHFINDER_M {
        return PathDecision::Reject;
    }

    let existing = match existing {
        None => return PathDecision::Add,
        Some(e) => e,
    };

    let path_timebase = timebase_from_random_blobs(&existing.random_blobs);
    let blob_is_new = !existing.random_blobs.contains(random_blob);

    if announce_hops <= existing.hops {
        // Accept strictly shorter path even with duplicate blob
        if prefer_shorter_path && announce_hops < existing.hops {
            return PathDecision::Add;
        }
        // Equal or fewer hops: accept if new blob AND newer emission
        if blob_is_new && announce_emitted_ts > path_timebase {
            return PathDecision::Add;
        }
        // Same emission + unresponsive path: accept for path recovery
        if announce_emitted_ts == path_timebase && path_is_unresponsive {
            return PathDecision::Add;
        }
        PathDecision::Reject
    } else {
        // More hops than existing path
        let path_expired = now >= existing.expires;

        if path_expired && blob_is_new {
            return PathDecision::Add;
        }

        if announce_emitted_ts > path_timebase && blob_is_new {
            return PathDecision::Add;
        }

        if announce_emitted_ts == path_timebase && path_is_unresponsive {
            return PathDecision::Add;
        }

        PathDecision::Reject
    }
}

/// Decision for multi-path announce processing.
#[derive(Debug, PartialEq, Eq)]
pub enum MultiPathDecision {
    /// Replace/update the primary path (or the path with the same next_hop).
    ReplacePrimary,
    /// Accept as an alternative path via a new next_hop.
    AddAlternative,
    /// Reject this announce.
    Reject,
}

/// Multi-path aware announce decision.
///
/// Determines whether an incoming announce should update the primary path,
/// be stored as an alternative, or be rejected.
///
/// - No existing `PathSet` → `ReplacePrimary` (first path for this dest)
/// - Same `next_hop` exists in the set → delegate to `should_update_path`
///   against **that** specific path entry
/// - New `next_hop` → accept as `AddAlternative` if the blob is genuinely
///   new (not in any stored path's blobs) and emission timestamp is valid
#[allow(clippy::too_many_arguments)]
pub fn decide_announce_multipath(
    existing_set: Option<&PathSet>,
    announce_hops: u8,
    announce_emitted_ts: u64,
    random_blob: &[u8; 10],
    next_hop: &[u8; 16],
    path_is_unresponsive: bool,
    now: f64,
    prefer_shorter_path: bool,
) -> MultiPathDecision {
    decide_announce_multipath_with_gravity(
        existing_set,
        announce_hops,
        announce_emitted_ts,
        random_blob,
        next_hop,
        path_is_unresponsive,
        now,
        prefer_shorter_path,
        None,
        None,
    )
}

/// Multi-path announce decision with interface gravity context.
#[allow(clippy::too_many_arguments)]
pub fn decide_announce_multipath_with_gravity(
    existing_set: Option<&PathSet>,
    announce_hops: u8,
    announce_emitted_ts: u64,
    random_blob: &[u8; 10],
    next_hop: &[u8; 16],
    path_is_unresponsive: bool,
    now: f64,
    prefer_shorter_path: bool,
    current_gravity: Option<i64>,
    announce_gravity: Option<i64>,
) -> MultiPathDecision {
    // Hop limit
    if announce_hops > constants::PATHFINDER_M {
        return MultiPathDecision::Reject;
    }

    let path_set = match existing_set {
        None => return MultiPathDecision::ReplacePrimary,
        Some(ps) if ps.is_empty() => return MultiPathDecision::ReplacePrimary,
        Some(ps) => ps,
    };

    if is_higher_gravity_replacement(
        path_set,
        announce_hops,
        announce_emitted_ts,
        current_gravity,
        announce_gravity,
    ) {
        return MultiPathDecision::ReplacePrimary;
    }

    // Check if there's already a path with the same next_hop
    if let Some(existing_path) = path_set.find_by_next_hop(next_hop) {
        let decision = should_update_path(
            Some(existing_path),
            announce_hops,
            announce_emitted_ts,
            random_blob,
            path_is_unresponsive,
            now,
            prefer_shorter_path,
        );
        match decision {
            PathDecision::Add => MultiPathDecision::ReplacePrimary,
            PathDecision::Reject => MultiPathDecision::Reject,
        }
    } else {
        // New next_hop — check if blob is genuinely new across all paths
        let all_blobs = path_set.all_random_blobs();
        let blob_is_new = !all_blobs.contains(random_blob);

        if !blob_is_new {
            return MultiPathDecision::Reject;
        }

        let max_timebase = timebase_from_random_blobs(&all_blobs);
        if announce_emitted_ts >= max_timebase {
            MultiPathDecision::AddAlternative
        } else {
            MultiPathDecision::Reject
        }
    }
}

/// Whether a same-emission announce should replace the primary path solely
/// because it arrived on an interface with higher gravity.
pub fn is_higher_gravity_replacement(
    path_set: &PathSet,
    announce_hops: u8,
    announce_emitted_ts: u64,
    current_gravity: Option<i64>,
    announce_gravity: Option<i64>,
) -> bool {
    let (Some(primary), Some(current_gravity), Some(announce_gravity)) =
        (path_set.primary(), current_gravity, announce_gravity)
    else {
        return false;
    };
    announce_hops <= primary.hops
        && announce_emitted_ts == timebase_from_random_blobs(&primary.random_blobs)
        && announce_gravity > current_gravity
}

#[cfg(test)]
mod tests {
    use super::super::types::InterfaceId;
    use super::*;

    fn make_blob(timebase: u64) -> [u8; 10] {
        let mut blob = [0u8; 10];
        let bytes = timebase.to_be_bytes();
        // timebase is stored in blob[5..10] = last 5 bytes of u64
        blob[5..10].copy_from_slice(&bytes[3..8]);
        blob
    }

    fn make_path_entry(hops: u8, blobs: &[[u8; 10]], expires: f64) -> PathEntry {
        PathEntry {
            timestamp: 1000.0,
            next_hop: [0xAA; 16],
            hops,
            expires,
            random_blobs: blobs.to_vec(),
            receiving_interface: InterfaceId(1),
            packet_hash: [0xBB; 32],
            announce_raw: None,
        }
    }

    #[test]
    fn test_timebase_extraction() {
        let blob = make_blob(12345);
        assert_eq!(timebase_from_random_blob(&blob), 12345);
    }

    #[test]
    fn test_timebase_from_multiple_blobs() {
        let b1 = make_blob(100);
        let b2 = make_blob(200);
        let b3 = make_blob(50);
        assert_eq!(timebase_from_random_blobs(&[b1, b2, b3]), 200);
    }

    #[test]
    fn test_timebase_empty_blobs() {
        assert_eq!(timebase_from_random_blobs(&[]), 0);
    }

    #[test]
    fn test_extract_random_blob() {
        // Need at least 74 + 10 = 84 bytes
        let mut data = [0u8; 100];
        // Put a known blob at offset 74
        data[74..84].copy_from_slice(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
        let blob = extract_random_blob(&data).unwrap();
        assert_eq!(blob, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
    }

    #[test]
    fn test_extract_random_blob_too_short() {
        let data = [0u8; 80]; // too short
        assert!(extract_random_blob(&data).is_none());
    }

    // --- Decision tree tests ---

    #[test]
    fn test_no_existing_path_always_add() {
        let blob = make_blob(100);
        assert_eq!(
            should_update_path(None, 3, 100, &blob, false, 1000.0, false),
            PathDecision::Add
        );
    }

    #[test]
    fn test_hop_limit_reject() {
        let blob = make_blob(100);
        assert_eq!(
            should_update_path(None, 129, 100, &blob, false, 1000.0, false),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_fewer_hops_new_blob_newer_emission_add() {
        let old_blob = make_blob(100);
        let new_blob = make_blob(200);
        let entry = make_path_entry(5, &[old_blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 3, 200, &new_blob, false, 1000.0, false),
            PathDecision::Add
        );
    }

    #[test]
    fn test_fewer_hops_duplicate_blob_reject() {
        let blob = make_blob(100);
        let entry = make_path_entry(5, &[blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 3, 200, &blob, false, 1000.0, false),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_fewer_hops_same_emission_unresponsive_add() {
        let old_blob = make_blob(100);
        let mut different_blob = [0u8; 10];
        different_blob[0] = 0xFF;
        different_blob[5..10].copy_from_slice(&100u64.to_be_bytes()[3..8]);

        let entry = make_path_entry(5, &[old_blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 3, 100, &different_blob, true, 1000.0, false),
            PathDecision::Add
        );
    }

    #[test]
    fn test_fewer_hops_same_emission_responsive_reject() {
        let old_blob = make_blob(100);
        let mut different_blob = [0u8; 10];
        different_blob[0] = 0xFF;
        different_blob[5..10].copy_from_slice(&100u64.to_be_bytes()[3..8]);

        let entry = make_path_entry(5, &[old_blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 3, 100, &different_blob, false, 1000.0, false),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_more_hops_expired_path_new_blob_add() {
        let old_blob = make_blob(100);
        let new_blob = make_blob(50); // older emission but path expired
        let entry = make_path_entry(2, &[old_blob], 500.0); // expires at 500

        assert_eq!(
            should_update_path(Some(&entry), 5, 50, &new_blob, false, 600.0, false), // now > expires
            PathDecision::Add
        );
    }

    #[test]
    fn test_more_hops_not_expired_older_emission_reject() {
        let old_blob = make_blob(200);
        let new_blob = make_blob(100);
        let entry = make_path_entry(2, &[old_blob], 9999.0);

        assert_eq!(
            should_update_path(Some(&entry), 5, 100, &new_blob, false, 1000.0, false),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_more_hops_newer_emission_new_blob_add() {
        let old_blob = make_blob(100);
        let new_blob = make_blob(200);
        let entry = make_path_entry(2, &[old_blob], 9999.0);

        assert_eq!(
            should_update_path(Some(&entry), 5, 200, &new_blob, false, 1000.0, false),
            PathDecision::Add
        );
    }

    #[test]
    fn test_more_hops_same_emission_unresponsive_add() {
        let old_blob = make_blob(100);
        let mut different_blob = [0u8; 10];
        different_blob[0] = 0xFF;
        different_blob[5..10].copy_from_slice(&100u64.to_be_bytes()[3..8]);

        let entry = make_path_entry(2, &[old_blob], 9999.0);

        assert_eq!(
            should_update_path(Some(&entry), 5, 100, &different_blob, true, 1000.0, false),
            PathDecision::Add
        );
    }

    #[test]
    fn test_more_hops_same_emission_responsive_reject() {
        let old_blob = make_blob(100);
        let mut different_blob = [0u8; 10];
        different_blob[0] = 0xFF;
        different_blob[5..10].copy_from_slice(&100u64.to_be_bytes()[3..8]);

        let entry = make_path_entry(2, &[old_blob], 9999.0);

        assert_eq!(
            should_update_path(Some(&entry), 5, 100, &different_blob, false, 1000.0, false),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_more_hops_duplicate_blob_reject() {
        let blob = make_blob(200);
        let entry = make_path_entry(2, &[blob], 9999.0);

        assert_eq!(
            should_update_path(Some(&entry), 5, 200, &blob, false, 1000.0, false),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_equal_hops_new_blob_newer_emission_add() {
        let old_blob = make_blob(100);
        let new_blob = make_blob(200);
        let entry = make_path_entry(3, &[old_blob], 9999.0);

        assert_eq!(
            should_update_path(Some(&entry), 3, 200, &new_blob, false, 1000.0, false),
            PathDecision::Add
        );
    }

    // --- prefer_shorter_path tests ---

    #[test]
    fn test_prefer_shorter_path_strictly_fewer_hops_duplicate_blob_add() {
        let blob = make_blob(100);
        let entry = make_path_entry(5, &[blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 3, 100, &blob, false, 1000.0, true),
            PathDecision::Add
        );
    }

    #[test]
    fn test_prefer_shorter_path_equal_hops_duplicate_blob_reject() {
        // Equal hops with same blob: no benefit, still rejected
        let blob = make_blob(100);
        let entry = make_path_entry(3, &[blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 3, 100, &blob, false, 1000.0, true),
            PathDecision::Reject
        );
    }

    #[test]
    fn test_prefer_shorter_path_more_hops_duplicate_blob_reject() {
        // More hops: prefer_shorter_path does not help
        let blob = make_blob(100);
        let entry = make_path_entry(2, &[blob], 9999.0);
        assert_eq!(
            should_update_path(Some(&entry), 5, 100, &blob, false, 1000.0, true),
            PathDecision::Reject
        );
    }

    // --- MultiPathDecision tests ---

    #[test]
    fn test_multipath_no_existing_set_replace_primary() {
        let blob = make_blob(100);
        assert_eq!(
            decide_announce_multipath(None, 3, 100, &blob, &[0xBB; 16], false, 1000.0, false),
            MultiPathDecision::ReplacePrimary
        );
    }

    #[test]
    fn test_multipath_same_nexthop_update() {
        let blob_old = make_blob(100);
        let blob_new = make_blob(200);
        let entry = make_path_entry(3, &[blob_old], 9999.0);
        let ps = PathSet::from_single(entry, 3);

        // Same next_hop, newer blob → ReplacePrimary
        assert_eq!(
            decide_announce_multipath(
                Some(&ps),
                2,
                200,
                &blob_new,
                &[0xAA; 16],
                false,
                1000.0,
                false
            ),
            MultiPathDecision::ReplacePrimary
        );
    }

    #[test]
    fn test_multipath_same_nexthop_reject() {
        let blob = make_blob(100);
        let entry = make_path_entry(3, &[blob], 9999.0);
        let ps = PathSet::from_single(entry, 3);

        // Same next_hop, same blob → Reject
        assert_eq!(
            decide_announce_multipath(Some(&ps), 3, 100, &blob, &[0xAA; 16], false, 1000.0, false),
            MultiPathDecision::Reject
        );
    }

    #[test]
    fn test_multipath_new_nexthop_novel_blob_add_alternative() {
        let blob_existing = make_blob(100);
        let blob_new = make_blob(200);
        let entry = make_path_entry(3, &[blob_existing], 9999.0);
        let ps = PathSet::from_single(entry, 3);

        // Different next_hop, novel blob, newer emission → AddAlternative
        assert_eq!(
            decide_announce_multipath(
                Some(&ps),
                4,
                200,
                &blob_new,
                &[0xCC; 16],
                false,
                1000.0,
                false
            ),
            MultiPathDecision::AddAlternative
        );
    }

    #[test]
    fn test_multipath_new_nexthop_known_blob_reject() {
        let blob = make_blob(100);
        let entry = make_path_entry(3, &[blob], 9999.0);
        let ps = PathSet::from_single(entry, 3);

        // Different next_hop but blob already known → Reject
        assert_eq!(
            decide_announce_multipath(Some(&ps), 4, 100, &blob, &[0xCC; 16], false, 1000.0, false),
            MultiPathDecision::Reject
        );
    }

    #[test]
    fn test_multipath_new_nexthop_older_emission_reject() {
        let blob_existing = make_blob(200);
        let blob_new = make_blob(100); // older emission
        let entry = make_path_entry(3, &[blob_existing], 9999.0);
        let ps = PathSet::from_single(entry, 3);

        // Novel blob but older emission timestamp → Reject
        assert_eq!(
            decide_announce_multipath(
                Some(&ps),
                4,
                100,
                &blob_new,
                &[0xCC; 16],
                false,
                1000.0,
                false
            ),
            MultiPathDecision::Reject
        );
    }

    #[test]
    fn test_multipath_hop_limit_reject() {
        let blob = make_blob(100);
        assert_eq!(
            decide_announce_multipath(None, 129, 100, &blob, &[0xBB; 16], false, 1000.0, false),
            MultiPathDecision::Reject
        );
    }

    #[test]
    fn same_emission_prefers_strictly_higher_gravity() {
        let blob = make_blob(100);
        let entry = make_path_entry(3, &[blob], 9999.0);
        let ps = PathSet::from_single(entry, 3);

        let decide = |current, incoming, hops| {
            decide_announce_multipath_with_gravity(
                Some(&ps),
                hops,
                100,
                &blob,
                &[0xCC; 16],
                false,
                1000.0,
                false,
                Some(current),
                Some(incoming),
            )
        };

        assert_eq!(decide(0, 1, 3), MultiPathDecision::ReplacePrimary);
        assert_eq!(decide(-5, -2, 3), MultiPathDecision::ReplacePrimary);
        assert_eq!(decide(1, 1, 3), MultiPathDecision::Reject);
        assert_eq!(decide(2, 1, 3), MultiPathDecision::Reject);
        assert_eq!(decide(0, 1, 4), MultiPathDecision::Reject);

        assert!(is_higher_gravity_replacement(&ps, 3, 100, Some(0), Some(1)));
        assert!(!is_higher_gravity_replacement(
            &ps,
            3,
            100,
            Some(1),
            Some(1)
        ));
        assert_eq!(crate::logging::GRAVITY_UPDATE_LOG_LEVEL, log::Level::Trace);
        assert_eq!(crate::logging::PATHING_LOG_TARGET, "rns::pathing");
    }
}