ic-db 0.23.10

Experimental embedded Internet Computer database
Documentation
//! Finite compiled named-type graph. No persisted catalog or materialized value tree.
use crate::{
    Error, FieldSchema, FieldType,
    codec::{Decoder, Encoder},
    schema::{MAX_FIELDS, encode_type, name},
};
use std::collections::{BTreeMap, BTreeSet};

pub(crate) const MAX_DEPTH: usize = 32;
pub(crate) const MAX_NODES: usize = 256;
pub(crate) const MAX_COLLECTION_ITEMS: usize = 256;

/// Compiler-resolved link. Names carry identity; the function breaks constant cycles.
#[derive(Clone, Copy, Debug)]
pub struct TypeLink {
    /// Logical name under the stored contract.
    pub name: &'static str,
    /// Resolve the compiled definition, never stored or dynamically loaded code.
    pub definition: fn() -> &'static TypeSchema,
}
impl PartialEq for TypeLink {
    fn eq(&self, other: &Self) -> bool {
        self.name == other.name
    }
}
impl Eq for TypeLink {}

/// Named schema; its links are shallow so recursive graphs never expand on comparison.
#[derive(Debug, PartialEq, Eq)]
pub struct TypeSchema {
    /// Logical type identity.
    pub name: &'static str,
    /// The complete named value shape, including any wrapped type and its bounds.
    pub body: TypeBody,
}
/// A compiled named type; record/enum members use canonical name order.
#[derive(Debug, PartialEq, Eq)]
pub enum TypeBody {
    /// Named wrapper around a primitive or a bounded ordered list.
    Wrapped(FieldType),
    /// Canonical map with scalar/unit-enum keys and arbitrary admitted value shapes.
    Map {
        /// Required primitive, scalar newtype or unit-enum key.
        key: FieldType,
        /// Value type and optionality, independent of map presence.
        value: ValueSchema,
        /// Maximum entries, sharing the enclosing row's collection budget.
        max_items: u32,
    },
    /// Canonical scalar/unit-enum set. Stored elements must be strictly increasing.
    Set {
        /// Primitive, scalar newtype or unit enum with a strict logical order.
        item: FieldType,
        /// Maximum entries, also subject to the enclosing row's shared budget.
        max_items: u32,
    },
    /// Stored fields; nested entity references are not supported.
    Record(&'static [FieldSchema]),
    /// Named alternatives, each with at most one typed payload.
    Enum(&'static [VariantSchema]),
}
/// One unit or payload variant.
#[derive(Debug, PartialEq, Eq)]
pub struct VariantSchema {
    /// Logical variant identity.
    pub name: &'static str,
    /// None means a unit variant, distinct from an optional absent payload.
    pub payload: Option<ValueSchema>,
}

// Ordered capability belongs to the complete enum, including unused variants.
// Bound unchecked operand definitions before comparing them with admitted metadata.
pub(crate) fn unit_enum_len(definition: &TypeSchema) -> Option<usize> {
    let TypeBody::Enum(variants) = &definition.body else {
        return None;
    };
    (!definition.name.is_empty()
        && definition.name.len() <= 64
        && !variants.is_empty()
        && variants.len() <= 64
        && variants
            .iter()
            .all(|v| v.payload.is_none() && !v.name.is_empty() && v.name.len() <= 64)
        && variants.windows(2).all(|w| w[0].name < w[1].name))
    .then_some(variants.len())
}
/// Payload shape, shared with the field type/optionality rules.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ValueSchema {
    /// Exact scalar, bounded list or compiler-resolved named type.
    pub value: FieldType,
    /// Whether the payload carries an explicit presence byte.
    pub optional: bool,
}
/// Codec boundary generated by named-type macros; handwritten implementations are unsupported.
pub trait Value: Sized {
    /// Logical name; independent of source path and declaration order.
    const NAME: &'static str;
    /// Compiled descriptor, including recursive links.
    fn definition() -> &'static TypeSchema;

    /// Append a value within the enclosing row's shared budget.
    /// # Errors
    /// Refuses field, byte, depth or node bounds.
    #[doc(hidden)]
    fn encode_into(&self, writer: &mut Encoder) -> Result<(), Error>;

    /// Decode within the enclosing row's shared budget.
    /// # Errors
    /// Refuses malformed values and exceeded bounds.
    #[doc(hidden)]
    fn decode_from(reader: &mut Decoder<'_>) -> Result<Self, Error>;
}

#[derive(Clone, Default)]
pub(crate) struct TypeGraph {
    definitions: BTreeMap<&'static str, &'static TypeSchema>,
    // Addresses only terminate traversal of compiler-emitted static nodes; they
    // are never identities, persisted bytes or function-pointer comparisons.
    visited: Vec<&'static TypeSchema>,
}
impl TypeGraph {
    pub fn include(&mut self, value: FieldType) -> Result<(), Error> {
        let value = if let FieldType::List { item, max_items } = value {
            if max_items > MAX_COLLECTION_ITEMS as u32 || matches!(item, FieldType::List { .. }) {
                return Err(Error::InvalidSchema);
            }
            *item
        } else {
            value
        };
        let FieldType::Named(link) = value else {
            return Ok(());
        };
        let definition = (link.definition)();
        if definition.name != link.name {
            return Err(Error::InvalidSchema);
        }
        if self
            .visited
            .iter()
            .any(|seen| std::ptr::eq(*seen, definition))
        {
            return Ok(());
        }
        if self.visited.len() >= 64 {
            return Err(Error::InvalidSchema);
        }
        self.visited.push(definition);
        if self
            .definitions
            .insert(link.name, definition)
            .is_some_and(|old| old != definition)
            || self.definitions.len() > 32
        {
            return Err(Error::InvalidSchema);
        }
        match &definition.body {
            TypeBody::Wrapped(FieldType::Named(_)) => return Err(Error::InvalidSchema),
            TypeBody::Wrapped(value) => self.include(*value)?,
            TypeBody::Map {
                key,
                value,
                max_items,
            } => {
                if *max_items > MAX_COLLECTION_ITEMS as u32 {
                    return Err(Error::InvalidSchema);
                }
                self.include_ordered(*key)?;
                self.include(value.value)?;
            }
            TypeBody::Set { item, max_items } => {
                if *max_items > MAX_COLLECTION_ITEMS as u32 {
                    return Err(Error::InvalidSchema);
                }
                self.include_ordered(*item)?;
            }
            TypeBody::Record(fields) => {
                if fields.len() > MAX_FIELDS {
                    return Err(Error::InvalidSchema);
                }
                for field in *fields {
                    self.include(field.value)?;
                }
            }
            TypeBody::Enum(variants) => {
                if variants.len() > 64 {
                    return Err(Error::InvalidSchema);
                }
                for variant in *variants {
                    if let Some(payload) = variant.payload {
                        self.include(payload.value)?;
                    }
                }
            }
        }
        Ok(())
    }

    fn include_ordered(&mut self, value: FieldType) -> Result<(), Error> {
        match crate::key::operand_type(value) {
            FieldType::List { .. } => return Err(Error::InvalidSchema),
            FieldType::Named(link) if unit_enum_len((link.definition)()).is_none() => {
                return Err(Error::InvalidSchema);
            }
            _ => {}
        }
        self.include(value)
    }

    pub fn definitions(&self) -> impl Iterator<Item = &'static TypeSchema> + '_ {
        self.definitions.values().copied()
    }

    pub fn contains(&self, other: &Self) -> bool {
        other
            .definitions
            .iter()
            .all(|(name, definition)| self.definitions.get(name) == Some(definition))
    }

    pub fn encode(&mut self, bytes: &mut Vec<u8>) -> Result<(), Error> {
        if self.definitions.is_empty() {
            return Ok(());
        }
        bytes.extend(b"ICDBTY02");
        bytes.extend((MAX_DEPTH as u32).to_le_bytes());
        bytes.extend((MAX_NODES as u32).to_le_bytes());
        bytes.extend((self.definitions.len() as u32).to_le_bytes());
        for definition in self.definitions.values() {
            let (kind, count) = match &definition.body {
                TypeBody::Enum(v) => (1, v.len()),
                TypeBody::Record(f) => (2, f.len()),
                TypeBody::Set { .. } => (3, 1),
                TypeBody::Map { .. } => (4, 2),
                TypeBody::Wrapped(_) => (5, 1),
            };
            bytes.push(kind);
            name(bytes, definition.name)?;
            bytes.extend((count as u32).to_le_bytes());
            match &definition.body {
                TypeBody::Wrapped(value) => encode_type(bytes, *value, false, false)?,
                TypeBody::Map {
                    key,
                    value,
                    max_items,
                } => {
                    bytes.extend(max_items.to_le_bytes());
                    bytes.extend((MAX_COLLECTION_ITEMS as u32).to_le_bytes());
                    encode_type(bytes, *key, false, false)?;
                    encode_type(bytes, value.value, value.optional, false)?;
                }
                TypeBody::Set { item, max_items } => {
                    bytes.extend(max_items.to_le_bytes());
                    bytes.extend((MAX_COLLECTION_ITEMS as u32).to_le_bytes());
                    encode_type(bytes, *item, false, false)?;
                }
                TypeBody::Enum(variants) => {
                    if variants.is_empty()
                        || variants.len() > 64
                        || variants.windows(2).any(|w| w[0].name >= w[1].name)
                    {
                        return Err(Error::InvalidSchema);
                    }
                    for variant in *variants {
                        name(bytes, variant.name)?;
                        bytes.push(u8::from(variant.payload.is_some()));
                        if let Some(payload) = variant.payload {
                            encode_type(bytes, payload.value, payload.optional, false)?;
                        }
                    }
                }
                TypeBody::Record(fields) => {
                    if fields.len() > MAX_FIELDS
                        || fields.windows(2).any(|w| w[0].name >= w[1].name)
                    {
                        return Err(Error::InvalidSchema);
                    }
                    for field in *fields {
                        if field.reference.is_some()
                            || field.default.is_some()
                            || field.managed.is_some()
                        {
                            return Err(Error::InvalidSchema);
                        }
                        name(bytes, field.name)?;
                        encode_type(bytes, field.value, field.optional, false)?;
                    }
                }
            }
        }
        // Least fixed point: an optional/list edge or unit alternative is a finite
        // constructor; a required cycle without a base case never becomes viable.
        let mut finite = BTreeSet::new();
        for _ in 0..self.definitions.len() {
            for (name, definition) in &self.definitions {
                let viable = |value, optional| {
                    optional
                        || match value {
                            FieldType::Named(link) => finite.contains(link.name),
                            _ => true,
                        }
                };
                let has_value = match &definition.body {
                    TypeBody::Wrapped(_) | TypeBody::Set { .. } | TypeBody::Map { .. } => true,
                    TypeBody::Record(fields) => fields.iter().all(|f| viable(f.value, f.optional)),
                    TypeBody::Enum(variants) => variants
                        .iter()
                        .any(|v| v.payload.is_none_or(|p| viable(p.value, p.optional))),
                };
                if has_value {
                    finite.insert(*name);
                }
            }
        }
        if finite.len() != self.definitions.len() {
            return Err(Error::InvalidSchema);
        }
        self.visited = Vec::new();
        Ok(())
    }
}