berblom 0.1.0

use wot_network::{Certificate, Delegation as WotDelegation, TrustDepth};

use crate::types::certification::Certification;
#[cfg(doc)]
use crate::types::path::Path;

/// The representation of all possible edge types in the residual graph.
pub(crate) enum Edge {
    Certification(Certification),
    Delegation(Delegation),
    ReverseEdge(ReverseEdge),
}

#[derive(Debug, Clone, Copy)]
pub enum UsedEdge {
    Certification(usize),
    Delegation(usize),
    ReverseEdge { index: usize, path_id: usize },
}

impl UsedEdge {
    /// Returns true if `self` is a [`UsedEdge::ReverseEdge`].
    pub fn is_reverse_edge(&self) -> bool {
        matches!(self, UsedEdge::ReverseEdge { .. })
    }
}

/// The representation of a reverse edge used in our Ford-Fulkerson variant.
///
/// This edge type enables backtracking within a trust network.
/// When a valid path `A` with a trust amount `X` has been found in the network, two things happen:
/// 1. The amount `X` is subtracted from the capacity of all forward edges in that path.
/// 2. Along all edges of path `A`, reverse (backflow) edges with the trust amount `X` are created,
///    effectively creating a reverse path `A'`.
///
/// Additionally to the trust amount, the reverse edges also keep track of the current
/// [`TrustDepth`]. The edge points to a [`Certificate`].
#[derive(Debug, Clone, Eq, Hash, PartialEq)]
pub(crate) struct ReverseEdge {
    pub issuer: Certificate,
    pub target: Certificate,
    // See TODO where forward edges are adjusted on usage of reverse edges.
    // /// When a reverse edge is used, we need to adjust the counterpart delegation that was
    // /// used when this reverse edge was created.
    // /// To pick the correct delegation, we save its array index.
    // pub(crate) delegation_index: usize,
    pub trust_amount: u8,
    /// The trust depth that will be checked against when searching for a path.
    ///
    /// The trust depth on a reverse edge must/will be the same as the computed trust depth on the
    /// `issuer` node on the path that created this `ReverseEdge`.
    ///
    /// This is used to "simulate" the redirection of flow on the path that created this reverse
    /// edge. While simulating this redirection, we have to uphold the trust depth constraints
    /// along the old and the "new" path.
    /// It's used to answer the following question:
    ///
    /// There is a path `A`, which created this `ReverseEdge`.
    /// Would it be a valid operation to redirect flow from the target anchor of Path `A` along the
    /// new path I just found?
    ///
    /// Read `002_Flow_Computation/003_Calculation_of_Reverse_Trust_Depth.md` for more detailed
    /// information.
    pub trust_depth: TrustDepth,

    /// Reverse edges are created for every forward edge along a valid path `A`.
    /// To enable backtracking at a later step, while upholding delegation depth constraints,
    /// the remaining steps towards the target binding along every step of path `A` must be stored.
    ///
    /// It's used to answer a question in the following scenario:
    ///
    /// There is path `A`, which created this `ReverseEdge`.
    /// We're currently searching for a new path `B`, but we are still in the middle of the search.
    /// If we were to traverse this ReverseEdge during pathfinding, we would know that we can
    /// redirect the flow from the anchor of `A` along the intermediate path of `B` via
    /// the `issuer` node of this very `ReverseEdge`. (This is guaranteed via
    /// [`Self::trust_depth`]).
    ///
    /// Once we traversed this reverse edge, we no longer look at the path length of `B` (as we
    /// just redirected the flow), but instead we must consider the remaining length of `A` (on
    /// which some flow has just theoretically been cleared).
    /// Can we find a path forward towards any anchor where delegations allow depths that are equal
    /// or larger than the remaining part of path `A`?
    pub remaining_path_length: usize,

    /// The internal id of the path this reverse edge belongs to.
    ///
    /// The value is practically the nth path that was discovered.
    /// This is necessary to determine which successive reverse edge to pick, if there are multiple
    /// to choose from.
    ///
    /// Read the `001_Path_Finding/002_Traversing_Reverse_Edges.md` for more information.
    pub path_id: usize,
}

/// A wrapper around a [`wot_network::Delegation`] to keep track of any used trust capacity during
/// the Berblom algorithm.
#[derive(Debug, Clone, Eq, Hash, PartialEq)]
pub(crate) struct Delegation {
    pub inner: WotDelegation,
    pub used_amount: u8,
}

impl Delegation {
    pub fn new(inner: WotDelegation) -> Self {
        Self {
            inner,
            used_amount: 0,
        }
    }

    /// Returns the issuer certificate of the delegation.
    pub fn issuer(&self) -> &Certificate {
        &self.inner.issuer
    }

    /// Returns the target certificate of the delegation.
    pub fn target(&self) -> &Certificate {
        &self.inner.target
    }

    /// Returns the trust amount of the delegation.
    pub fn trust_amount(&self) -> u8 {
        self.inner.trust_amount
    }

    /// Returns the trust depth of the delegation.
    pub fn trust_depth(&self) -> TrustDepth {
        self.inner.trust_depth
    }

    /// Returns a reference to the regexes of the delegation.
    pub fn regexes(&self) -> &Vec<wot_network::Regex> {
        &self.inner.regexes
    }

    /// Returns the remaining trust capacity that can be directed through this delegation.
    pub fn available_amount(&self) -> u8 {
        self.inner.trust_amount.saturating_sub(self.used_amount)
    }
}

/// Represents a single step along the graph.
///
/// This type is used in the crate's [`Path`] representation, which allows traversal on reverse
/// edges. [`wot_network`] expects resolved paths with [`Delegation`]s only and has no
/// representation of reverse edges.
///
/// Unlike the [`Edge`] enum, this does not contain a certification, as certifications only appear
/// as the final step in path finding. All other edges along the path must be reverse edges or
/// delegations.
#[derive(Debug, Clone, Eq, Hash, PartialEq)]
pub(crate) enum PathEdge {
    ReverseEdge(ReverseEdge),
    ForwardEdge(Delegation),
}

impl PathEdge {
    /// Returns a reference to the contained ReverseEdge if this is a ReverseEdge variant.
    pub fn reverse(&self) -> Option<&ReverseEdge> {
        match self {
            PathEdge::ReverseEdge(edge) => Some(edge),
            _ => None,
        }
    }

    /// Returns a reference to the contained Delegation if this is a ForwardEdge variant.
    pub fn delegation(&self) -> Option<&Delegation> {
        match self {
            PathEdge::ForwardEdge(delegation) => Some(delegation),
            _ => None,
        }
    }

    pub fn issuer(&self) -> &Certificate {
        match self {
            PathEdge::ReverseEdge(edge) => &edge.issuer,
            PathEdge::ForwardEdge(delegation) => delegation.issuer(),
        }
    }
}