use crate::Error;
use core::marker::PhantomData;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Diagnostic {
    pub graph: u64,
    pub held: u64,
    pub requested: u64,
}
pub struct Context<const H: usize> {
    held: [u64; H],
    len: usize,
    _local: PhantomData<*mut ()>,
}
impl<const H: usize> Default for Context<H> {
    fn default() -> Self {
        Self {
            held: [0; H],
            len: 0,
            _local: PhantomData,
        }
    }
}
impl<const H: usize> Context<H> {
    pub fn held(&self) -> &[u64] {
        &self.held[..self.len]
    }
}

/// Serialized debug acquisition graph. It protects ordering metadata, not the
/// payload of the registered locks. Trusted kernel integration keeps its guard
/// alive until the corresponding actual lock guard has been released.
pub struct Graph<const N: usize, const H: usize> {
    id: u64,
    ids: [u64; N],
    len: usize,
    edges: [u64; N],
    last: Option<Diagnostic>,
}
impl<const N: usize, const H: usize> Graph<N, H> {
    pub fn new(id: u64) -> Result<Self, Error> {
        if id == 0 || N == 0 || N > 64 || H == 0 {
            return Err(Error::Invalid);
        }
        Ok(Self {
            id,
            ids: [0; N],
            len: 0,
            edges: [0; N],
            last: None,
        })
    }
    pub fn register(&mut self, id: u64) -> Result<(), Error> {
        if id == 0 {
            return Err(Error::Invalid);
        }
        if self.ids[..self.len].contains(&id) {
            return Err(Error::Recursive);
        }
        if self.len == N {
            return Err(Error::Capacity);
        }
        self.ids[self.len] = id;
        self.len += 1;
        Ok(())
    }
    fn index(&self, id: u64) -> Result<usize, Error> {
        self.ids[..self.len]
            .iter()
            .position(|&v| v == id)
            .ok_or(Error::Invalid)
    }
    fn reaches(&self, from: usize, to: usize) -> bool {
        let mut pending = 1u64 << from;
        let mut visited = 0;
        while pending != 0 {
            let index = pending.trailing_zeros() as usize;
            pending &= !(1u64 << index);
            if index == to {
                return true;
            }
            if visited & (1u64 << index) == 0 {
                visited |= 1u64 << index;
                pending |= self.edges[index] & !visited;
            }
        }
        false
    }
    /// All graph capacity/cycle checks precede the actual acquisition callback.
    /// A failed actual acquisition publishes neither an edge nor a held record.
    pub fn acquire<'a, R>(
        &'a mut self,
        ctx: &'a mut Context<H>,
        id: u64,
        actual: impl FnOnce() -> Result<R, Error>,
    ) -> Result<(Guard<'a, N, H>, R), Error> {
        let target = self.index(id)?;
        if ctx.len == H {
            return Err(Error::Capacity);
        }
        if ctx.held[..ctx.len].contains(&id) {
            return Err(Error::Recursive);
        }
        let mut sources = 0u64;
        for &held in &ctx.held[..ctx.len] {
            let source = self.index(held)?;
            if self.reaches(target, source) {
                self.last = Some(Diagnostic {
                    graph: self.id,
                    held,
                    requested: id,
                });
                return Err(Error::Cycle);
            }
            self.edges[source] |= 1u64 << target; sources |= 1u64 << source;
        }
        let resource = actual()?;
        for source in 0..self.len {
            if sources & (1u64 << source) != 0 {
                self.edges[source] |= 1u64 << target;
            }
        }
        ctx.held[ctx.len] = id;
        ctx.len += 1;
        Ok((
            Guard {
                graph: self,
                context: ctx,
                id,
                _local: PhantomData,
            },
            resource,
        ))
    }
    pub fn edges(&self) -> [u64; N] {
        self.edges
    }
    pub fn last_diagnostic(&self) -> Option<Diagnostic> {
        self.last
    }
}
pub struct Guard<'a, const N: usize, const H: usize> {
    graph: &'a mut Graph<N, H>,
    context: &'a mut Context<H>,
    id: u64,
    _local: PhantomData<*mut ()>,
}
impl<const N: usize, const H: usize> Guard<'_, N, H> {
    pub fn acquire<'a, R>(
        &'a mut self,
        id: u64,
        actual: impl FnOnce() -> Result<R, Error>,
    ) -> Result<(Guard<'a, N, H>, R), Error> {
        self.graph.acquire(self.context, id, actual)
    }
    pub fn held(&self) -> &[u64] {
        self.context.held()
    }
    pub fn edges(&self) -> [u64; N] {
        self.graph.edges()
    }
    pub fn last_diagnostic(&self) -> Option<Diagnostic> {
        self.graph.last_diagnostic()
    }
}
impl<const N: usize, const H: usize> Drop for Guard<'_, N, H> {
    fn drop(&mut self) {
        // Borrowed guards enforce LIFO destruction, including panic unwinding.
        debug_assert!(self.context.len != 0 && self.context.held[self.context.len - 1] == self.id);
        self.context.len -= 1;
        self.context.held[self.context.len] = 0;
    }
}