Skip to main content

kernel/graph/
navigation_check.rs

1// Copyright 2026 Mark Alan Boykin
2// This Source Code Form is subject to the terms of the Mozilla Public
3// License, v. 2.0. If a copy of the MPL was not distributed with this
4// file, You can obtain one at https://mozilla.org/MPL/2.0/.
5// SPDX-License-Identifier: MPL-2.0
6
7//! The one bounds check on a navigation snapshot's cross-references.
8//!
9//! Stemma hydration indexes its columns without checking, so any snapshot
10//! load that installs a decoded [`SharedNavigationMemory`] runs this first.
11
12use std::fmt;
13
14use super::history::SharedNavigationMemory;
15
16/// An index in the navigation snapshot that names no row of its column.
17#[derive(Debug, Clone, PartialEq, Eq)]
18pub struct NavigationIndexError {
19    /// The referring column, for example `visits.parent`.
20    pub field: &'static str,
21    /// The row of that column holding the index.
22    pub at: usize,
23    pub index: usize,
24    /// How many rows the referenced column has.
25    pub len: usize,
26}
27
28impl fmt::Display for NavigationIndexError {
29    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
30        let Self {
31            field,
32            at,
33            index,
34            len,
35        } = self;
36        write!(
37            f,
38            "navigation {field}[{at}] names row {index} of {len} rows"
39        )
40    }
41}
42
43impl SharedNavigationMemory {
44    /// Refuse a snapshot whose entry, visit or owner indices leave their column.
45    pub fn check_indices(&self) -> Result<(), NavigationIndexError> {
46        let snapshot = self.snapshot();
47        let (entries, visits, owners) = (
48            snapshot.entries.len(),
49            snapshot.visits.len(),
50            snapshot.owners.len(),
51        );
52        let within = |field, at, index: usize, len| {
53            if index < len {
54                return Ok(());
55            }
56            Err(NavigationIndexError {
57                field,
58                at,
59                index,
60                len,
61            })
62        };
63        let optional = |field, at, index: Option<usize>, len| {
64            index.map_or(Ok(()), |index| within(field, at, index, len))
65        };
66        for (at, visit) in snapshot.visits.iter().enumerate() {
67            within("visits.entry", at, visit.entry, entries)?;
68            optional("visits.parent", at, visit.parent, visits)?;
69            for child in &visit.children {
70                within("visits.children", at, *child, visits)?;
71            }
72            for binding in &visit.bindings {
73                within("visits.bindings.owner", at, binding.owner, owners)?;
74                optional(
75                    "visits.bindings.forward_child",
76                    at,
77                    binding.forward_child,
78                    visits,
79                )?;
80            }
81        }
82        for (at, owner) in snapshot.owners.iter().enumerate() {
83            optional("owners.origin", at, owner.origin, visits)?;
84            optional("owners.current", at, owner.current, visits)?;
85            optional(
86                "owners.pending_origin_parent",
87                at,
88                owner.pending_origin_parent,
89                visits,
90            )?;
91            optional("owners.creator", at, owner.creator, owners)?;
92            for visit in &owner.owned_visits {
93                within("owners.owned_visits", at, *visit, visits)?;
94            }
95        }
96        Ok(())
97    }
98}