//! Bounded read-only directory tree and path traversal.

pub const NAME_BYTES: usize = 16;
pub const MAX_NODES: usize = 16;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
    BadRoot,
    TooManyNodes,
    InvalidInode,
    DuplicateInode,
    InvalidName,
    DuplicateName,
    ParentMissing,
    NotDirectory,
    Loop,
    InvalidPath,
    NoEntry,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Kind { Directory, Regular }

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Node {
    pub inode: u64,
    pub parent: u64,
    pub kind: Kind,
    pub name_len: u8,
    pub name: [u8; NAME_BYTES],
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Directory<const N: usize> { nodes: [Node; N] }

impl<const N: usize> Directory<N> {
    pub fn validate(nodes: [Node; N]) -> Result<Self, Error> {
        if N == 0 || nodes[0].inode != 1 || nodes[0].parent != 0
            || nodes[0].kind != Kind::Directory || nodes[0].name_len != 0 {
            return Err(Error::BadRoot);
        }
        if N > MAX_NODES { return Err(Error::TooManyNodes); }
        for (index, node) in nodes.iter().enumerate() {
            if node.inode == 0 { return Err(Error::InvalidInode); }
            if nodes[..index].iter().any(|other| other.inode == node.inode) {
                return Err(Error::DuplicateInode);
            }
            if index == 0 { continue; }
            let name = &node.name[..usize::from(node.name_len).min(NAME_BYTES)];
            if node.name_len == 0 || usize::from(node.name_len) > NAME_BYTES
                || !name.iter().all(|byte| byte.is_ascii_alphanumeric()
                    || matches!(*byte, b'_' | b'-')) {
                return Err(Error::InvalidName);
            }
            if nodes[..index].iter().any(|other| other.parent == node.parent
                && other.name_len == node.name_len
                && other.name[..usize::from(other.name_len).min(NAME_BYTES)] == *name) {
                return Err(Error::DuplicateName);
            }
            let mut parent = node.parent;
            let mut hops = 0;
            while parent != 1 {
                if parent == node.inode || hops >= N { break; }
                let ancestor = nodes.iter().find(|candidate| candidate.inode == parent)
                    .ok_or(Error::ParentMissing)?;
                if ancestor.kind != Kind::Directory { return Err(Error::NotDirectory); }
                parent = ancestor.parent;
                hops += 1;
            }
            if nodes[0].kind != Kind::Directory { return Err(Error::BadRoot); }
        }
        Ok(Self { nodes })
    }

    pub fn lookup(&self, path: &[u8]) -> Result<Node, Error> {
        if path == b"/" { return Ok(self.nodes[0]); }
        if path.len() < 2 || path[0] != b'/' { return Err(Error::InvalidPath); }
        let mut current = self.nodes[0];
        for component in path[1..].split(|byte| *byte == b'/') {
            if component.is_empty() || component.len() > NAME_BYTES
                || !component.iter().all(|byte| byte.is_ascii_alphanumeric()
                    || matches!(*byte, b'_' | b'-')) {
                return Err(Error::InvalidPath);
            }
            if current.kind != Kind::Directory { return Err(Error::NotDirectory); }
            current = self.nodes.iter().copied().find(|node|
                node.parent == current.inode
                && usize::from(node.name_len) == component.len()
                && &node.name[..component.len()] == component)
                .ok_or(Error::NoEntry)?;
        }
        Ok(current)
    }

    pub const fn node_count(&self) -> usize { N }
}