//! Registry-owned stage1 tables. New chains remain unreachable until their last
//! parent store. Removed translations complete hardware invalidation before any
//! page is returned. Shared kernel tables are borrowed and never reclaimed here.
use crate::descriptor::{self, Descriptor, Geometry, Memory, Permissions, Reader, Translation};

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
    Descriptor(descriptor::Error),
    Capacity,
    NoMemory,
    Backend,
    Foreign,
    Stale,
    AlreadyMapped,
    Unmapped,
    Shared,
    ActiveRoot,
    Mapped,
    Generation,
    Retained,
    AliasPermissions,
    Quiescent,
}
impl From<descriptor::Error> for Error {
    fn from(value: descriptor::Error) -> Self {
        Self::Descriptor(value)
    }
}

/// Handles must come from the existing page metadata Registry. The backend
/// owns that Registry and its frame-authority borrow. Writes are atomic: an
/// error leaves the entry unchanged. invalidate completes DSB/TLBI/DSB/ISB;
/// select_root performs the corresponding control-register synchronization.
/// Shared validation uses a separate immutable kernel table ownership set and
/// checks every reachable table/block/page denies EL0 access. Legacy kernel
/// block descriptors are validated by that adapter, never imported as private
/// baseline descriptors. Selecting an unchanged geometry with a distinct ASID
/// does not require global invalidation; recycling an ASID requires its own
/// completed targeted invalidation before select_root is called.
pub trait Backend {
    type Handle: Copy + Eq;
    fn allocate_zeroed(&mut self) -> Result<Self::Handle, Error>;
    fn address(&self, handle: Self::Handle) -> u64;
    fn validate(&self, handle: Self::Handle) -> Result<(), Error>;
    fn release(&mut self, handle: Self::Handle) -> Result<(), Error>;
    fn entry(&self, handle: Self::Handle, index: usize) -> Result<u64, Error>;
    fn write_entry(&mut self, handle: Self::Handle, index: usize, value: u64) -> Result<(), Error>;
    fn validate_shared_table(&self, address: u64) -> Result<(), Error>;
    fn validate_shared_page(&self, address: u64) -> Result<(), Error>;
    fn shared_entry(&self, address: u64, index: usize) -> Result<u64, Error>;
    fn active_root(&self) -> u64;
    fn invalidate(&mut self, root: u64, virtual_address: Option<u64>);
    fn select_root(&mut self, root: u64, geometry: Geometry, asid: u16);
}

#[derive(Debug, PartialEq, Eq)]
pub struct Root {
    tree: u64,
    slot: usize,
    generation: u64,
    address: u64,
}
impl Root {
    pub const fn address(&self) -> u64 {
        self.address
    }
}
#[derive(Debug, PartialEq, Eq)]
pub struct Page {
    tree: u64,
    slot: usize,
    generation: u64,
    address: u64,
}
impl Page {
    pub const fn address(&self) -> u64 {
        self.address
    }
    pub const fn reference(&self) -> PageRef {
        PageRef {
            tree: self.tree,
            slot: self.slot,
            generation: self.generation,
            address: self.address,
        }
    }
}
/// An inert observation for preparing mappings. It cannot release a page;
/// every use checks the retained owning token's current Registry generation.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct PageRef {
    tree: u64,
    slot: usize,
    generation: u64,
    address: u64,
}
impl PageRef {
    pub const fn address(self) -> u64 {
        self.address
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Kind {
    Root,
    Table,
    Page,
    Quarantined,
}
#[derive(Clone, Copy)]
struct Record<H> {
    handle: H,
    generation: u64,
    kind: Kind,
    level: u8,
    parent: Option<(usize, usize)>,
    mappings: usize,
    activatable: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct OwnedRecord {
    pub address: u64,
    pub generation: u64,
    pub table: bool,
    pub root: bool,
    pub quarantined: bool,
    pub mappings: usize,
    pub activatable: bool,
}

/// Tree IDs are issued once by the boot's authority owner. All metadata is
/// caller bounded. Root and Page tokens cannot be cloned or fabricated.
pub struct Tree<B: Backend, const N: usize> {
    id: u64,
    geometry: Geometry,
    backend: B,
    records: [Option<Record<B::Handle>>; N],
    generation: u64,
}
impl<B: Backend, const N: usize> Tree<B, N> {
    pub fn new(id: u64, geometry: Geometry, backend: B) -> Result<Self, Error> {
        if id == 0 {
            return Err(Error::Foreign);
        }
        Ok(Self {
            id,
            geometry,
            backend,
            records: [None; N],
            generation: 0,
        })
    }
    pub const fn geometry(&self) -> Geometry {
        self.geometry
    }
    pub fn with_backend_observation<R>(&self, callback: impl FnOnce(&B) -> R) -> R {
        callback(&self.backend)
    }
    pub fn owned_records(&self) -> impl Iterator<Item = OwnedRecord> + '_ {
        self.records.iter().flatten().map(|r| OwnedRecord {
            address: self.backend.address(r.handle),
            generation: r.generation,
            table: matches!(r.kind, Kind::Root | Kind::Table),
            root: r.kind == Kind::Root,
            quarantined: r.kind == Kind::Quarantined,
            mappings: r.mappings,
            activatable: r.activatable,
        })
    }
    fn reserve(&mut self, kind: Kind, level: u8) -> Result<usize, Error> {
        let slot = self
            .records
            .iter()
            .position(Option::is_none)
            .ok_or(Error::Capacity)?;
        let generation = self.generation.checked_add(1).ok_or(Error::Generation)?;
        let handle = self.backend.allocate_zeroed()?;
        self.generation = generation;
        self.records[slot] = Some(Record {
            handle,
            generation,
            kind,
            level,
            parent: None,
            mappings: 0,
            activatable: kind == Kind::Root,
        });
        let address = self.backend.address(handle);
        if self.geometry.validate_physical_page(address).is_err()
            || self.records.iter().enumerate().any(|(i, r)| {
                i != slot && r.is_some_and(|r| self.backend.address(r.handle) == address)
            })
            || self.backend.validate(handle).is_err()
        {
            self.records[slot].as_mut().unwrap().kind = Kind::Quarantined;
            self.records[slot].as_mut().unwrap().activatable = false;
            return Err(Error::Retained);
        }
        Ok(slot)
    }
    pub fn new_root(&mut self) -> Result<Root, Error> {
        let slot = self.reserve(Kind::Root, self.geometry.start_level())?;
        let r = self.records[slot].unwrap();
        Ok(Root {
            tree: self.id,
            slot,
            generation: r.generation,
            address: self.backend.address(r.handle),
        })
    }
    /// A draft can hold mappings with replacement permissions, but cannot be
    /// installed until conflicting roots have become quiescent and publication
    /// has checked backing-wide user W-xor-X across all activatable roots.
    pub fn new_draft_root(&mut self) -> Result<Root, Error> {
        let root = self.new_root()?;
        self.records[root.slot].as_mut().unwrap().activatable = false;
        Ok(root)
    }
    pub fn allocate_page(&mut self) -> Result<Page, Error> {
        let slot = self.reserve(Kind::Page, 3)?;
        let r = self.records[slot].unwrap();
        Ok(Page {
            tree: self.id,
            slot,
            generation: r.generation,
            address: self.backend.address(r.handle),
        })
    }
    fn checked(
        &self,
        tree: u64,
        slot: usize,
        generation: u64,
        kind: Kind,
        address: u64,
    ) -> Result<Record<B::Handle>, Error> {
        if tree != self.id {
            return Err(Error::Foreign);
        }
        let r = self
            .records
            .get(slot)
            .and_then(|r| *r)
            .ok_or(Error::Stale)?;
        if r.generation != generation || r.kind != kind || self.backend.address(r.handle) != address
        {
            return Err(Error::Stale);
        }
        self.backend.validate(r.handle)?;
        Ok(r)
    }
    fn root(&self, root: &Root) -> Result<Record<B::Handle>, Error> {
        self.checked(
            root.tree,
            root.slot,
            root.generation,
            Kind::Root,
            root.address,
        )
    }
    fn page(&self, page: &Page) -> Result<Record<B::Handle>, Error> {
        self.checked(
            page.tree,
            page.slot,
            page.generation,
            Kind::Page,
            page.address,
        )
    }
    fn table_slot(&self, address: u64, level: u8, parent: (usize, usize)) -> Result<usize, Error> {
        if let Some((slot, r)) = self
            .records
            .iter()
            .enumerate()
            .filter_map(|(i, r)| r.map(|r| (i, r)))
            .find(|(_, r)| self.backend.address(r.handle) == address)
        {
            if r.kind != Kind::Table || r.level != level || r.parent != Some(parent) {
                return Err(Error::Backend);
            }
            self.backend.validate(r.handle)?;
            Ok(slot)
        } else {
            self.backend.validate_shared_table(address)?;
            Err(Error::Shared)
        }
    }
    fn rollback(&mut self, slots: &[usize]) -> bool {
        let mut retained = false;
        for &slot in slots.iter().rev() {
            let record = self.records[slot].unwrap();
            if self.backend.release(record.handle).is_ok() {
                self.records[slot] = None;
            } else {
                let r = self.records[slot].as_mut().unwrap();
                r.kind = Kind::Quarantined;
                r.parent = None;
                retained = true;
            }
        }
        retained
    }
    fn insert(&mut self, root: &Root, va: u64, target: u8, value: u64) -> Result<(), Error> {
        let root_record = self.root(root)?;
        self.geometry.validate_virtual(va)?;
        if va & (descriptor::PAGE - 1) != 0 {
            return Err(descriptor::Error::Alignment.into());
        }
        if target < self.geometry.start_level() || target > 3 {
            return Err(descriptor::Error::Level.into());
        }
        let mut parent = root.slot;
        let mut level = root_record.level;
        loop {
            let index = self.geometry.index(va, level)?;
            let r = self.records[parent].unwrap();
            let old = self.backend.entry(r.handle, index)?;
            if level == target {
                if old != 0 {
                    return Err(Error::AlreadyMapped);
                }
                self.backend.write_entry(r.handle, index, value)?;
                return Ok(());
            }
            match descriptor::decode(self.geometry, level, old)? {
                Descriptor::Empty => break,
                Descriptor::Table { address } => {
                    parent = self.table_slot(address, level + 1, (parent, index))?
                }
                _ => return Err(Error::AlreadyMapped),
            }
            level += 1;
        }
        let needed = usize::from(target - level);
        if self.records.iter().filter(|r| r.is_none()).count() < needed {
            return Err(Error::Capacity);
        }
        if self.generation.checked_add(needed as u64).is_none() {
            return Err(Error::Generation);
        }
        let mut pending = [0; 3];
        let mut len = 0;
        for child_level in level + 1..=target {
            match self.reserve(Kind::Table, child_level) {
                Ok(slot) => {
                    pending[len] = slot;
                    len += 1;
                }
                Err(error) => {
                    return Err(if self.rollback(&pending[..len]) {
                        Error::Retained
                    } else {
                        error
                    });
                }
            }
        }
        // Every child is still unreachable. Only the final parent store publishes.
        let staged = (|| {
            for i in (0..len).rev() {
                let slot = pending[i];
                let r = self.records[slot].unwrap();
                let index = self.geometry.index(va, r.level)?;
                let raw = if i + 1 == len {
                    value
                } else {
                    descriptor::table(
                        self.geometry,
                        r.level,
                        self.backend
                            .address(self.records[pending[i + 1]].unwrap().handle),
                    )?
                };
                self.backend.write_entry(r.handle, index, raw)?;
            }
            let index = self.geometry.index(va, level)?;
            let raw = descriptor::table(
                self.geometry,
                level,
                self.backend
                    .address(self.records[pending[0]].unwrap().handle),
            )?;
            self.backend
                .write_entry(self.records[parent].unwrap().handle, index, raw)?;
            Ok::<(), Error>(())
        })();
        if let Err(error) = staged {
            return Err(if self.rollback(&pending[..len]) {
                Error::Retained
            } else {
                error
            });
        }
        for (i, &slot) in pending[..len].iter().enumerate() {
            let previous = if i == 0 { parent } else { pending[i - 1] };
            let previous_level = self.records[previous].unwrap().level;
            self.records[slot].as_mut().unwrap().parent =
                Some((previous, self.geometry.index(va, previous_level)?));
        }
        Ok(())
    }
    pub fn map(
        &mut self,
        root: &Root,
        va: u64,
        page: &Page,
        memory: Memory,
        permissions: Permissions,
    ) -> Result<(), Error> {
        self.map_reference(root, va, page.reference(), memory, permissions)
    }
    pub fn map_reference(
        &mut self,
        root: &Root,
        va: u64,
        page: PageRef,
        memory: Memory,
        permissions: Permissions,
    ) -> Result<(), Error> {
        self.checked(
            page.tree,
            page.slot,
            page.generation,
            Kind::Page,
            page.address,
        )?;
        let root_record = self.root(root)?;
        if root_record.activatable {
            self.check_alias(page.address, permissions, None)?;
        }
        let count = self.records[page.slot]
            .unwrap()
            .mappings
            .checked_add(1)
            .ok_or(Error::Capacity)?;
        let raw = descriptor::page(self.geometry, page.address, memory, permissions)?;
        self.insert(root, va, 3, raw)?;
        self.records[page.slot].as_mut().unwrap().mappings = count;
        Ok(())
    }
    /// Import a table from the separately owned kernel set. The private prefix
    /// may be allocated, but the imported table and its descendants stay borrowed.
    pub fn share_table(
        &mut self,
        root: &Root,
        va: u64,
        level: u8,
        address: u64,
    ) -> Result<(), Error> {
        self.backend.validate_shared_table(address)?;
        let raw = descriptor::table(self.geometry, level, address)?;
        self.insert(root, va, level, raw)
    }
    pub fn activate(&mut self, root: &Root, asid: u16) -> Result<(), Error> {
        if false {
            return Err(Error::Quiescent);
        }
        self.backend.select_root(root.address, self.geometry, asid);
        Ok(())
    }
    pub fn quiesce(&mut self, root: &Root) -> Result<(), Error> {
        self.root(root)?;
        if self.backend.active_root() == root.address {
            return Err(Error::ActiveRoot);
        }
        self.records[root.slot].as_mut().unwrap().activatable = false;
        Ok(())
    }
    pub fn publish_root(&mut self, root: &Root) -> Result<(), Error> {
        self.root(root)?;
        if self.backend.active_root() == root.address {
            return Err(Error::ActiveRoot);
        }
        for (slot, r) in self
            .records
            .iter()
            .enumerate()
            .filter_map(|(i, r)| r.map(|r| (i, r)))
        {
            if r.kind != Kind::Table || r.level != 3 || !self.belongs_to(slot, root.slot)? {
                continue;
            }
            for index in 0..descriptor::ENTRIES {
                if let Descriptor::Page {
                    address,
                    permissions,
                    ..
                } = descriptor::decode(self.geometry, 3, self.backend.entry(r.handle, index)?)?
                {
                    self.check_alias(address, permissions, Some(root.slot))?;
                    // Draft mappings also cannot conflict with one another.
                    self.check_root_alias(root.slot, address, permissions)?;
                }
            }
        }
        self.records[root.slot].as_mut().unwrap().activatable = true;
        Ok(())
    }
    fn root_slot_of(&self, mut slot: usize) -> Result<usize, Error> {
        for _ in 0..N {
            let r = self
                .records
                .get(slot)
                .and_then(|r| *r)
                .ok_or(Error::Backend)?;
            if r.kind == Kind::Root {
                return Ok(slot);
            }
            slot = r.parent.ok_or(Error::Backend)?.0;
        }
        Err(Error::Backend)
    }
    fn incompatible(a: Permissions, b: Permissions) -> bool {
        a.user && b.user && ((a.write && b.execute) || (a.execute && b.write))
    }
    fn check_root_alias(
        &self,
        root: usize,
        address: u64,
        permissions: Permissions,
    ) -> Result<(), Error> {
        if !permissions.user {
            return Ok(());
        }
        for (slot, r) in self
            .records
            .iter()
            .enumerate()
            .filter_map(|(i, r)| r.map(|r| (i, r)))
        {
            if r.kind != Kind::Table || r.level != 3 || self.root_slot_of(slot)? != root {
                continue;
            }
            for index in 0..descriptor::ENTRIES {
                if let Descriptor::Page {
                    address: other,
                    permissions: other_permissions,
                    ..
                } = descriptor::decode(self.geometry, 3, self.backend.entry(r.handle, index)?)?
                    && other == address
                    && Self::incompatible(permissions, other_permissions)
                {
                    return Err(Error::AliasPermissions);
                }
            }
        }
        Ok(())
    }
    fn check_alias(
        &self,
        address: u64,
        permissions: Permissions,
        except: Option<usize>,
    ) -> Result<(), Error> {
        if !permissions.user {
            return Ok(());
        }
        for (slot, r) in self
            .records
            .iter()
            .enumerate()
            .filter_map(|(i, r)| r.map(|r| (i, r)))
        {
            if r.kind == Kind::Root && r.activatable && Some(slot) != except {
                self.check_root_alias(slot, address, permissions)?;
            }
        }
        Ok(())
    }
    pub fn restore_shared_root(
        &mut self,
        address: u64,
        geometry: Geometry,
        asid: u16,
    ) -> Result<(), Error> {
        geometry.validate_physical_page(address)?;
        self.backend.validate_shared_table(address)?;
        self.backend.select_root(address, geometry, asid);
        Ok(())
    }
    pub fn walk(&self, root: &Root, va: u64) -> Result<Translation, Error> {
        self.root(root)?;
        Ok(descriptor::walk(self.geometry, root.address, va, self)?)
    }
    pub fn unmap(&mut self, root: &Root, va: u64) -> Result<(), Error> {
        self.root(root)?;
        self.geometry.validate_virtual(va)?;
        if va & (descriptor::PAGE - 1) != 0 {
            return Err(descriptor::Error::Alignment.into());
        }
        let mut slot = root.slot;
        for level in self.geometry.start_level()..3 {
            let index = self.geometry.index(va, level)?;
            match descriptor::decode(
                self.geometry,
                level,
                self.backend
                    .entry(self.records[slot].unwrap().handle, index)?,
            )? {
                Descriptor::Table { address } => {
                    slot = self.table_slot(address, level + 1, (slot, index))?
                }
                _ => return Err(Error::Unmapped),
            }
        }
        let index = self.geometry.index(va, 3)?;
        let Descriptor::Page { address, .. } = descriptor::decode(
            self.geometry,
            3,
            self.backend
                .entry(self.records[slot].unwrap().handle, index)?,
        )?
        else {
            return Err(Error::Unmapped);
        };
        let page_slot = self
            .records
            .iter()
            .position(|r| {
                r.is_some_and(|r| r.kind == Kind::Page && self.backend.address(r.handle) == address)
            })
            .ok_or(Error::Backend)?;
        if self.records[page_slot].unwrap().mappings == 0 {
            return Err(Error::Backend);
        }
        self.backend
            .write_entry(self.records[slot].unwrap().handle, index, 0)?;
        self.backend.invalidate(root.address, Some(va));
        self.records[page_slot].as_mut().unwrap().mappings -= 1;
        let mut retained = false;
        while slot != root.slot {
            let r = self.records[slot].unwrap();
            let mut empty = true;
            for index in 0..descriptor::ENTRIES {
                if self.backend.entry(r.handle, index)? != 0 {
                    empty = false;
                    break;
                }
            }
            if !empty {
                break;
            }
            let (parent, index) = r.parent.ok_or(Error::Backend)?;
            self.backend
                .write_entry(self.records[parent].unwrap().handle, index, 0)?;
            self.backend.invalidate(root.address, None);
            if self.backend.release(r.handle).is_ok() {
                self.records[slot] = None;
            } else {
                let r = self.records[slot].as_mut().unwrap();
                r.kind = Kind::Quarantined;
                r.parent = None;
                retained = true;
            }
            slot = parent;
        }
        if retained {
            Err(Error::Retained)
        } else {
            Ok(())
        }
    }
    pub fn release_page(&mut self, page: Page) -> Result<(), (Error, Page)> {
        let result = (|| {
            let r = self.page(&page)?;
            if r.mappings != 0 {
                return Err(Error::Mapped);
            }
            self.backend.release(r.handle)?;
            self.records[page.slot] = None;
            Ok(())
        })();
        result.map_err(|e| (e, page))
    }
    pub fn release_root(&mut self, root: Root) -> Result<(), (Error, Root)> {
        let result = (|| {
            let r = self.root(&root)?;
            if self.backend.active_root() == root.address {
                return Err(Error::ActiveRoot);
            }
            if self
                .records
                .iter()
                .flatten()
                .any(|r| r.parent.is_some_and(|(parent, _)| parent == root.slot))
            {
                return Err(Error::Mapped);
            }
            for index in 0..descriptor::ENTRIES {
                let raw = self.backend.entry(r.handle, index)?;
                if raw != 0 {
                    let Descriptor::Table { address } =
                        descriptor::decode(self.geometry, r.level, raw)?
                    else {
                        return Err(Error::Mapped);
                    };
                    self.backend.validate_shared_table(address)?;
                }
            }
            // Inactive roots may still have cached translations under an ASID.
            self.backend.invalidate(root.address, None);
            self.backend.release(r.handle)?;
            self.records[root.slot] = None;
            Ok(())
        })();
        result.map_err(|e| (e, root))
    }
    pub fn reap_quarantine(&mut self) -> Result<usize, Error> {
        let mut count = 0;
        for slot in 0..N {
            if let Some(r) = self.records[slot].filter(|r| r.kind == Kind::Quarantined) {
                self.backend
                    .release(r.handle)
                    .map_err(|_| Error::Retained)?;
                self.records[slot] = None;
                count += 1;
            }
        }
        Ok(count)
    }
    fn belongs_to(&self, mut slot: usize, root: usize) -> Result<bool, Error> {
        for _ in 0..N {
            if slot == root {
                return Ok(true);
            }
            let r = self
                .records
                .get(slot)
                .and_then(|r| *r)
                .ok_or(Error::Backend)?;
            match r.parent {
                Some((parent, _)) => slot = parent,
                None => return Ok(false),
            }
        }
        Err(Error::Backend)
    }
    /// Detach an inactive root's private mappings and borrowed kernel entries.
    /// Data Page tokens remain owned by their caller; only intermediate tables
    /// are reclaimed. Failed releases remain observable quarantined handles.
    pub fn detach_all(&mut self, root: &Root) -> Result<(), Error> {
        self.root(root)?;
        if self.backend.active_root() == root.address {
            return Err(Error::ActiveRoot);
        }
        self.audit()?;
        let mut retained = false;
        for level in (self.geometry.start_level()..=3).rev() {
            for slot in 0..N {
                let Some(r) = self.records[slot]
                    .filter(|r| matches!(r.kind, Kind::Root | Kind::Table) && r.level == level)
                else {
                    continue;
                };
                if !self.belongs_to(slot, root.slot)? {
                    continue;
                }
                for index in 0..descriptor::ENTRIES {
                    let raw = self.backend.entry(r.handle, index)?;
                    if raw == 0 {
                        continue;
                    }
                    let decoded = descriptor::decode(self.geometry, level, raw)?;
                    self.backend.write_entry(r.handle, index, 0)?;
                    self.backend.invalidate(root.address, None);
                    if let Descriptor::Page { address, .. } = decoded {
                        let data = self
                            .records
                            .iter()
                            .position(|r| {
                                r.is_some_and(|r| {
                                    r.kind == Kind::Page
                                        && self.backend.address(r.handle) == address
                                })
                            })
                            .ok_or(Error::Backend)?;
                        self.records[data].as_mut().unwrap().mappings -= 1;
                    }
                }
                if slot != root.slot {
                    let (parent, index) = r.parent.ok_or(Error::Backend)?;
                    self.backend
                        .write_entry(self.records[parent].unwrap().handle, index, 0)?;
                    self.backend.invalidate(root.address, None);
                    if self.backend.release(r.handle).is_ok() {
                        self.records[slot] = None;
                    } else {
                        let r = self.records[slot].as_mut().unwrap();
                        r.kind = Kind::Quarantined;
                        r.parent = None;
                        retained = true;
                    }
                }
            }
        }
        if retained {
            Err(Error::Retained)
        } else {
            Ok(())
        }
    }
    pub fn audit(&self) -> Result<(), Error> {
        let mut mappings = [0usize; N];
        for (slot, r) in self
            .records
            .iter()
            .enumerate()
            .filter_map(|(i, r)| r.map(|r| (i, r)))
        {
            self.backend.validate(r.handle)?;
            let address = self.backend.address(r.handle);
            self.geometry.validate_physical_page(address)?;
            if r.generation == 0
                || r.generation > self.generation
                || self.records[..slot]
                    .iter()
                    .flatten()
                    .any(|other| self.backend.address(other.handle) == address)
            {
                return Err(Error::Backend);
            }
            if r.kind != Kind::Root && r.activatable {
                return Err(Error::Backend);
            }
            match r.kind {
                Kind::Page | Kind::Quarantined => {
                    if r.parent.is_some() {
                        return Err(Error::Backend);
                    }
                    continue;
                }
                Kind::Root => {
                    if r.parent.is_some() || r.level != self.geometry.start_level() {
                        return Err(Error::Backend);
                    }
                }
                Kind::Table => {
                    let (parent, index) = r.parent.ok_or(Error::Backend)?;
                    let p = self
                        .records
                        .get(parent)
                        .and_then(|r| *r)
                        .ok_or(Error::Backend)?;
                    if !matches!(p.kind, Kind::Root | Kind::Table)
                        || p.level + 1 != r.level
                        || index >= descriptor::ENTRIES
                        || self.backend.entry(p.handle, index)?
                            != descriptor::table(self.geometry, p.level, address)?
                    {
                        return Err(Error::Backend);
                    }
                    let mut ancestor = slot;
                    let mut found = false;
                    for _ in 0..N {
                        let a = self.records[ancestor].ok_or(Error::Backend)?;
                        if a.kind == Kind::Root {
                            found = true;
                            break;
                        }
                        ancestor = a.parent.ok_or(Error::Backend)?.0;
                        if ancestor >= N {
                            return Err(Error::Backend);
                        }
                    }
                    if !found {
                        return Err(Error::Backend);
                    }
                }
            }
            for index in 0..descriptor::ENTRIES {
                match descriptor::decode(
                    self.geometry,
                    r.level,
                    self.backend.entry(r.handle, index)?,
                )? {
                    Descriptor::Empty => {}
                    Descriptor::Table { address } => {
                        if let Some(child) = self
                            .records
                            .iter()
                            .flatten()
                            .find(|child| self.backend.address(child.handle) == address)
                        {
                            if child.kind != Kind::Table
                                || child.parent != Some((slot, index))
                                || child.level != r.level + 1
                            {
                                return Err(Error::Backend);
                            }
                        } else {
                            self.backend.validate_shared_table(address)?;
                        }
                    }
                    Descriptor::Page { address, .. } => {
                        let data = self
                            .records
                            .iter()
                            .position(|p| {
                                p.is_some_and(|p| {
                                    p.kind == Kind::Page
                                        && self.backend.address(p.handle) == address
                                })
                            })
                            .ok_or(Error::Backend)?;
                        mappings[data] = mappings[data].checked_add(1).ok_or(Error::Capacity)?;
                        let root = self.root_slot_of(slot)?;
                        if self.records[root].unwrap().activatable {
                            let Descriptor::Page { permissions, .. } = descriptor::decode(
                                self.geometry,
                                r.level,
                                self.backend.entry(r.handle, index)?,
                            )?
                            else {
                                return Err(Error::Backend);
                            };
                            self.check_alias(address, permissions, None)?;
                        }
                    }
                }
            }
        }
        for (slot, r) in self
            .records
            .iter()
            .enumerate()
            .filter_map(|(i, r)| r.map(|r| (i, r)))
        {
            if r.mappings != mappings[slot] {
                return Err(Error::Backend);
            }
        }
        Ok(())
    }
}
impl<B: Backend, const N: usize> Reader for Tree<B, N> {
    fn validate_table(&self, address: u64) -> Result<(), descriptor::Error> {
        if let Some(r) = self
            .records
            .iter()
            .flatten()
            .find(|r| self.backend.address(r.handle) == address)
        {
            if !matches!(r.kind, Kind::Root | Kind::Table) {
                return Err(descriptor::Error::Backing);
            }
            self.backend
                .validate(r.handle)
                .map_err(|_| descriptor::Error::Backing)
        } else {
            self.backend
                .validate_shared_table(address)
                .map_err(|_| descriptor::Error::Backing)
        }
    }
    fn validate_page(&self, address: u64) -> Result<(), descriptor::Error> {
        if let Some(r) = self
            .records
            .iter()
            .flatten()
            .find(|r| self.backend.address(r.handle) == address)
        {
            if r.kind != Kind::Page {
                return Err(descriptor::Error::Backing);
            }
            self.backend
                .validate(r.handle)
                .map_err(|_| descriptor::Error::Backing)
        } else {
            self.backend
                .validate_shared_page(address)
                .map_err(|_| descriptor::Error::Backing)
        }
    }
    fn entry(&self, address: u64, index: usize) -> Result<u64, descriptor::Error> {
        if index >= descriptor::ENTRIES {
            return Err(descriptor::Error::Backing);
        }
        if let Some(r) = self
            .records
            .iter()
            .flatten()
            .find(|r| self.backend.address(r.handle) == address)
        {
            self.backend
                .entry(r.handle, index)
                .map_err(|_| descriptor::Error::Backing)
        } else {
            self.backend
                .shared_entry(address, index)
                .map_err(|_| descriptor::Error::Backing)
        }
    }
}