Skip to content
Snippets Groups Projects
route.rs 14 KiB
Newer Older
use arrayvec::ArrayVec;

use crate::{error::AppendNodeError, identity::Identity};
Stephen D's avatar
Stephen D committed

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Route {
    pub max_hops: u8,
    path: ArrayVec<u8, 254>,
    has_future: bool,
}

impl Route {
    pub fn new(max_hops: u8) -> Self {
        let path = ArrayVec::new();

        Self {
            max_hops,
            path,
            has_future: false,
        }
    }

    /// Returns `None` if there isn't enough space for the callsign
    /// Returns `None` if attempting to push past after future hop
    /// See the specs for more information
    #[must_use]
    pub fn push_hop(&mut self, hop: RouteHop) -> Option<()> {
        match hop {
            RouteHop::Internet => self.push_internet(),
            RouteHop::Past(past_hop) => self.push_past(past_hop),
            RouteHop::Future(ident) => self.push_future(ident),
        }
    }

    /// Returns `None` if there isn't enough space for the callsign
    /// Returns `None` if attempting to push after future hop
    /// See the specs for more information
    #[must_use]
    pub fn push_past(&mut self, past_hop: PastHop) -> Option<()> {
        let ident = past_hop.identity();
        let len = ident.callsign().as_bytes().len() + 3;
        let free_space = self.path.capacity() - self.path.len();

        if len > free_space {
            return None;
        }

        if self.has_future {
            return None;
        }

        // safe to unwrap since we already did a length check
        self.path
            .try_extend_from_slice(ident.callsign().as_bytes())
            .unwrap();
        self.path.push(0xFF);
        self.path.push(ident.ssid());
        self.path.push(past_hop.rssi);

        Some(())
    }

    /// Returns `None` if there isn't enough space for the callsign
    #[must_use]
    pub fn push_future(&mut self, ident: Identity) -> Option<()> {
        let len = ident.callsign().as_bytes().len() + 2;
        let free_space = self.path.capacity() - self.path.len();

        if len > free_space {
        self.has_future = true;

        // safe to unwrap since we already did a length check
        self.path
            .try_extend_from_slice(ident.callsign().as_bytes())
            .unwrap();
        self.path.push(0xFD);
        self.path.push(ident.ssid());

        Some(())
    }

    /// Returns `None` if there isn't enough space
    pub fn push_internet(&mut self) -> Option<()> {
        let free_space = self.path.capacity() - self.path.len();

        if free_space < 1 {
            return None;
        }

        self.path.push(0xFE);

        Some(())
    }

Stephen D's avatar
Stephen D committed
    /// Append a callsign/ssid pair to the route, intelligently.
    /// I.e. replace future node if possible
    /// Returns an Err if the route is out of space, or appending the node doesn't make logical sense
    /// (there's a future node that doesn't match)
    /// This only appends past hops.
    pub fn append_hop(&mut self, new_hop: PastHop) -> Result<(), AppendNodeError> {
Stephen D's avatar
Stephen D committed
        let mut new_route = Route::new(self.max_hops);

        let mut already_inserted = false;
        for rn in self.iter() {
            match rn {
                RouteHop::Internet => new_route
Stephen D's avatar
Stephen D committed
                    .push_internet()
                    .ok_or(AppendNodeError::RouteOverflow)?,
                RouteHop::Past(prev_past_hop) => {
                    let us = prev_past_hop.identity() == new_hop.identity();

                    if us {
                        return Err(AppendNodeError::DuplicateNode);
                    } else {
                        new_route
                            .push_past(prev_past_hop)
                            .ok_or(AppendNodeError::RouteOverflow)?;
                    }
                }
                RouteHop::Future(prev_ident) => {
                    let us = prev_ident == new_hop.identity();

                    if us {
                        if already_inserted {
                            return Err(AppendNodeError::DuplicateNode);
Stephen D's avatar
Stephen D committed
                        } else {
                            new_route
                                .push_past(new_hop)
                                .ok_or(AppendNodeError::RouteOverflow)?;
                            already_inserted = true;
Stephen D's avatar
Stephen D committed
                        }
                    } else if already_inserted {
                        new_route
                            .push_future(prev_ident)
                            .ok_or(AppendNodeError::RouteOverflow)?;
Stephen D's avatar
Stephen D committed
                    } else {
                        return Err(AppendNodeError::SetFuture);
Stephen D's avatar
Stephen D committed
                    }
                }
            }
        }

        if !already_inserted {
            new_route
                .push_past(new_hop)
                .ok_or(AppendNodeError::RouteOverflow)?;
Stephen D's avatar
Stephen D committed
        }

        if new_route.iter().count() > usize::from(new_route.max_hops) {
            return Err(AppendNodeError::HopsOverflow);
Stephen D's avatar
Stephen D committed
        }

        *self = new_route;
        Ok(())
Stephen D's avatar
Stephen D committed
    }

    pub fn iter(&'_ self) -> RouteIter<'_> {
        RouteIter::new(self)
    }

    pub fn encode<'a>(&self, buf: &'a mut [u8]) -> Option<&'a [u8]> {
        let packet_len = self.path.len() + 1;
        let buf = buf.get_mut(0..(packet_len + 1))?;
        buf[0] = packet_len.try_into().unwrap();
        buf[1] = self.max_hops;
        buf[2..(packet_len + 1)].copy_from_slice(&self.path);

        Some(buf)
    }

    pub fn decode(data: &[u8]) -> Option<Self> {
        let len: usize = (*data.first()?).into();
        let data = data.get(1..(len + 1))?;

        let max_hops = *data.first()?;

        let mut path = ArrayVec::new();
        path.try_extend_from_slice(&data[1..]).unwrap();

        let has_future = data[1..].iter().any(|x| *x == 0xFD);

            max_hops,
            path,
            has_future,
        if UntrustedRouteIter::new(&s).any(|v| v.is_err()) {
#[derive(Debug, Eq, PartialEq, Copy, Clone)]
pub enum RouteHop<'a> {
    Past(PastHop<'a>),
    Future(Identity<'a>),
#[derive(Debug, Eq, PartialEq, Copy, Clone)]
pub struct PastHop<'a> {
    identity: Identity<'a>,
Stephen D's avatar
Stephen D committed
    rssi: u8,
}

impl<'a> PastHop<'a> {
    pub fn new(identity: Identity<'a>, rssi: Option<f64>) -> Self {
Stephen D's avatar
Stephen D committed
        let rssi = match rssi {
            Some(rssi) => (rssi * 1.5 + 240.0).max(1.0) as u8,
            None => 0,
        };

        Self { identity, rssi }
    pub fn identity(&self) -> Identity {
        self.identity
Stephen D's avatar
Stephen D committed
    }

    pub fn rssi(&self) -> Option<f64> {
        if self.rssi == 0 {
            None
        } else {
            Some(((self.rssi as f64) - 240.0) / 1.5)
        }
    }
Stephen D's avatar
Stephen D committed
#[derive(Debug, Clone)]
    route: &'a Route,
    i: usize,
    fn new(route: &'a Route) -> Self {
    // Returns Err(()) if invalid
    fn maybe_next(&mut self) -> Result<RouteHop<'a>, ()> {
        let i_start = self.i;
        self.i += 1;

        if *self.route.path.get(i_start).ok_or(())? == 0xFE {
            return Ok(RouteHop::Internet);
        while *self.route.path.get(self.i).ok_or(())? != 0xFD && self.route.path[self.i] != 0xFF {
        let callsign = core::str::from_utf8(self.route.path.get(i_start..self.i).ok_or(())?)
            .map_err(|_| ())?;
        let is_future = *self.route.path.get(self.i).ok_or(())? == 0xFD;
        if self.seen_future && !is_future {
            // past after future - not allowed
            return Err(());
Stephen D's avatar
Stephen D committed
        let ssid = *self.route.path.get(self.i + 1).ok_or(())?;
        self.i += 2;

        if is_future {
            Ok(RouteHop::Future(Identity::new(callsign, ssid)))
        } else {
            let rssi = *self.route.path.get(self.i).ok_or(())?;
            self.i += 1;

            Ok(RouteHop::Past(PastHop {
                identity: Identity::new(callsign, ssid),
                rssi,
            }))
        }
    type Item = Result<RouteHop<'a>, ()>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.dead {
            return None;
        }

        if self.i == self.route.path.len() {
            return None;
        }

        let r = self.maybe_next();

        if r.is_err() {
            self.dead = true;
Stephen D's avatar
Stephen D committed
#[derive(Clone)]
pub struct RouteIter<'a> {
    iter: UntrustedRouteIter<'a>,
}

impl<'a> RouteIter<'a> {
    fn new(route: &'a Route) -> Self {
        Self {
            iter: UntrustedRouteIter::new(route),
        }
    }
}

impl<'a> Iterator for RouteIter<'a> {
    type Item = RouteHop<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        Some(self.iter.next()?.unwrap())
Stephen D's avatar
Stephen D committed

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

Stephen D's avatar
Stephen D committed
    #[test]
    fn route_rssi() {
        let x = -66.0;
        let r = PastHop::new(Identity::new("C0", 23), Some(x));
Stephen D's avatar
Stephen D committed
        assert_eq!(x, r.rssi().unwrap());

        let x = 10.0;
        let r = PastHop::new(Identity::new("C0", 23), Some(x));
Stephen D's avatar
Stephen D committed
        assert_eq!(x, r.rssi().unwrap());

        let x = -158.0;
        let r = PastHop::new(Identity::new("C0", 23), Some(x));
Stephen D's avatar
Stephen D committed
        assert_eq!(x, r.rssi().unwrap());

        let r = PastHop::new(Identity::new("C0", 23), None);
Stephen D's avatar
Stephen D committed
        assert_eq!(None, r.rssi());
    }

Stephen D's avatar
Stephen D committed
    #[test]
    fn append_fails_when_existing_future() {
        let mut r = Route::new(5);
        r.push_past(PastHop::new(Identity::new("C1", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_past(PastHop::new(Identity::new("C2", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_future(Identity::new("C3", 0)).unwrap();
Stephen D's avatar
Stephen D committed

        assert_eq!(
            AppendNodeError::SetFuture,
            r.append_hop(PastHop::new(Identity::new("C3", 1), None))
                .unwrap_err()
Stephen D's avatar
Stephen D committed
        );

        assert_eq!(
            AppendNodeError::SetFuture,
            r.append_hop(PastHop::new(Identity::new("C4", 0), None))
                .unwrap_err()
Stephen D's avatar
Stephen D committed
        );
    }

    #[test]
    fn append_fails_when_would_exceed_max_hops() {
        let mut r = Route::new(3);
        r.append_hop(PastHop::new(Identity::new("C1", 0), None))
            .unwrap();
        r.append_hop(PastHop::new(Identity::new("C2", 0), None))
            .unwrap();
        r.append_hop(PastHop::new(Identity::new("C2", 1), None))
            .unwrap();
Stephen D's avatar
Stephen D committed
        assert_eq!(
            AppendNodeError::HopsOverflow,
            r.append_hop(PastHop::new(Identity::new("C4", 0), None))
                .unwrap_err()
Stephen D's avatar
Stephen D committed
        );
    }

    #[test]
    fn append_fails_when_already_in_route() {
        let mut r = Route::new(3);
        r.append_hop(PastHop::new(Identity::new("C1", 0), None))
            .unwrap();
Stephen D's avatar
Stephen D committed

        assert_eq!(
            AppendNodeError::DuplicateNode,
            r.append_hop(PastHop::new(Identity::new("C1", 0), None))
                .unwrap_err()
Stephen D's avatar
Stephen D committed
        );
    }

    #[test]
    fn append_overwrites_future() {
        let mut r = Route::new(5);
        r.push_past(PastHop::new(Identity::new("C1", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_past(PastHop::new(Identity::new("C2", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_future(Identity::new("C3", 0)).unwrap();
        r.push_future(Identity::new("C4", 0)).unwrap();
Stephen D's avatar
Stephen D committed

        r.append_hop(PastHop::new(Identity::new("C3", 0), None))
            .unwrap();

        let mut iter = r.iter();
Stephen D's avatar
Stephen D committed
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(Some(RouteHop::Future(Identity::new("C4", 0))), iter.next());
        assert_eq!(None, iter.next());
    }

    #[test]
    fn append_overwrites_future_even_when_at_hop_limit() {
        let mut r = Route::new(4);
        r.push_past(PastHop::new(Identity::new("C1", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_past(PastHop::new(Identity::new("C2", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_future(Identity::new("C3", 0)).unwrap();
        r.push_future(Identity::new("C4", 0)).unwrap();
        r.append_hop(PastHop::new(Identity::new("C3", 0), None))
            .unwrap();
Stephen D's avatar
Stephen D committed

        let mut iter = r.iter();
Stephen D's avatar
Stephen D committed
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(Some(RouteHop::Future(Identity::new("C4", 0,))), iter.next());
Stephen D's avatar
Stephen D committed
        assert_eq!(None, iter.next());
    }

    #[test]
    fn append_appends_when_no_future() {
        let mut r = Route::new(5);
        r.push_past(PastHop::new(Identity::new("C1", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_past(PastHop::new(Identity::new("C2", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
        r.push_past(PastHop::new(Identity::new("C3", 0), None))
Stephen D's avatar
Stephen D committed
            .unwrap();
Stephen D's avatar
Stephen D committed

        r.append_hop(PastHop::new(Identity::new("C4", 0), None))
            .unwrap();
Stephen D's avatar
Stephen D committed

        let mut iter = r.iter();
Stephen D's avatar
Stephen D committed
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C1", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C2", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C3", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
        assert_eq!(
            Some(RouteHop::Past(PastHop::new(Identity::new("C4", 0), None))),
Stephen D's avatar
Stephen D committed
            iter.next()
        );
Stephen D's avatar
Stephen D committed
        assert_eq!(None, iter.next());
    }
}