Skip to main content

ic_db/
types.rs

1//! Finite compiled named-type graph. No persisted catalog or materialized value tree.
2use crate::{
3    Error, FieldSchema, FieldType,
4    codec::{Decoder, Encoder},
5    schema::{MAX_FIELDS, encode_type, name},
6};
7use std::collections::{BTreeMap, BTreeSet};
8
9pub(crate) const MAX_DEPTH: usize = 32;
10pub(crate) const MAX_NODES: usize = 256;
11pub(crate) const MAX_COLLECTION_ITEMS: usize = 256;
12
13/// Compiler-resolved link. Names carry identity; the function breaks constant cycles.
14#[derive(Clone, Copy, Debug)]
15pub struct TypeLink {
16    /// Logical name under the stored contract.
17    pub name: &'static str,
18    /// Resolve the compiled definition, never stored or dynamically loaded code.
19    pub definition: fn() -> &'static TypeSchema,
20}
21impl PartialEq for TypeLink {
22    fn eq(&self, other: &Self) -> bool {
23        self.name == other.name
24    }
25}
26impl Eq for TypeLink {}
27
28/// Named schema; its links are shallow so recursive graphs never expand on comparison.
29#[derive(Debug, PartialEq, Eq)]
30pub struct TypeSchema {
31    /// Logical type identity.
32    pub name: &'static str,
33    /// The complete named value shape, including any wrapped type and its bounds.
34    pub body: TypeBody,
35}
36/// A compiled named type; record/enum members use canonical name order.
37#[derive(Debug, PartialEq, Eq)]
38pub enum TypeBody {
39    /// Named wrapper around a primitive or a bounded ordered list.
40    Wrapped(FieldType),
41    /// Canonical map with scalar/unit-enum keys and arbitrary admitted value shapes.
42    Map {
43        /// Required primitive, scalar newtype or unit-enum key.
44        key: FieldType,
45        /// Value type and optionality, independent of map presence.
46        value: ValueSchema,
47        /// Maximum entries, sharing the enclosing row's collection budget.
48        max_items: u32,
49    },
50    /// Canonical scalar/unit-enum set. Stored elements must be strictly increasing.
51    Set {
52        /// Primitive, scalar newtype or unit enum with a strict logical order.
53        item: FieldType,
54        /// Maximum entries, also subject to the enclosing row's shared budget.
55        max_items: u32,
56    },
57    /// Stored fields; nested entity references are not supported.
58    Record(&'static [FieldSchema]),
59    /// Named alternatives, each with at most one typed payload.
60    Enum(&'static [VariantSchema]),
61}
62/// One unit or payload variant.
63#[derive(Debug, PartialEq, Eq)]
64pub struct VariantSchema {
65    /// Logical variant identity.
66    pub name: &'static str,
67    /// None means a unit variant, distinct from an optional absent payload.
68    pub payload: Option<ValueSchema>,
69}
70
71// Ordered capability belongs to the complete enum, including unused variants.
72// Bound unchecked operand definitions before comparing them with admitted metadata.
73pub(crate) fn unit_enum_len(definition: &TypeSchema) -> Option<usize> {
74    let TypeBody::Enum(variants) = &definition.body else {
75        return None;
76    };
77    (!definition.name.is_empty()
78        && definition.name.len() <= 64
79        && !variants.is_empty()
80        && variants.len() <= 64
81        && variants
82            .iter()
83            .all(|v| v.payload.is_none() && !v.name.is_empty() && v.name.len() <= 64)
84        && variants.windows(2).all(|w| w[0].name < w[1].name))
85    .then_some(variants.len())
86}
87/// Payload shape, shared with the field type/optionality rules.
88#[derive(Clone, Copy, Debug, PartialEq, Eq)]
89pub struct ValueSchema {
90    /// Exact scalar, bounded list or compiler-resolved named type.
91    pub value: FieldType,
92    /// Whether the payload carries an explicit presence byte.
93    pub optional: bool,
94}
95/// Codec boundary generated by named-type macros; handwritten implementations are unsupported.
96pub trait Value: Sized {
97    /// Logical name; independent of source path and declaration order.
98    const NAME: &'static str;
99    /// Compiled descriptor, including recursive links.
100    fn definition() -> &'static TypeSchema;
101
102    /// Append a value within the enclosing row's shared budget.
103    /// # Errors
104    /// Refuses field, byte, depth or node bounds.
105    #[doc(hidden)]
106    fn encode_into(&self, writer: &mut Encoder) -> Result<(), Error>;
107
108    /// Decode within the enclosing row's shared budget.
109    /// # Errors
110    /// Refuses malformed values and exceeded bounds.
111    #[doc(hidden)]
112    fn decode_from(reader: &mut Decoder<'_>) -> Result<Self, Error>;
113}
114
115#[derive(Clone, Default)]
116pub(crate) struct TypeGraph {
117    definitions: BTreeMap<&'static str, &'static TypeSchema>,
118    // Addresses only terminate traversal of compiler-emitted static nodes; they
119    // are never identities, persisted bytes or function-pointer comparisons.
120    visited: Vec<&'static TypeSchema>,
121}
122impl TypeGraph {
123    pub fn include(&mut self, value: FieldType) -> Result<(), Error> {
124        let value = if let FieldType::List { item, max_items } = value {
125            if max_items > MAX_COLLECTION_ITEMS as u32 || matches!(item, FieldType::List { .. }) {
126                return Err(Error::InvalidSchema);
127            }
128            *item
129        } else {
130            value
131        };
132        let FieldType::Named(link) = value else {
133            return Ok(());
134        };
135        let definition = (link.definition)();
136        if definition.name != link.name {
137            return Err(Error::InvalidSchema);
138        }
139        if self
140            .visited
141            .iter()
142            .any(|seen| std::ptr::eq(*seen, definition))
143        {
144            return Ok(());
145        }
146        if self.visited.len() >= 64 {
147            return Err(Error::InvalidSchema);
148        }
149        self.visited.push(definition);
150        if self
151            .definitions
152            .insert(link.name, definition)
153            .is_some_and(|old| old != definition)
154            || self.definitions.len() > 32
155        {
156            return Err(Error::InvalidSchema);
157        }
158        match &definition.body {
159            TypeBody::Wrapped(FieldType::Named(_)) => return Err(Error::InvalidSchema),
160            TypeBody::Wrapped(value) => self.include(*value)?,
161            TypeBody::Map {
162                key,
163                value,
164                max_items,
165            } => {
166                if *max_items > MAX_COLLECTION_ITEMS as u32 {
167                    return Err(Error::InvalidSchema);
168                }
169                self.include_ordered(*key)?;
170                self.include(value.value)?;
171            }
172            TypeBody::Set { item, max_items } => {
173                if *max_items > MAX_COLLECTION_ITEMS as u32 {
174                    return Err(Error::InvalidSchema);
175                }
176                self.include_ordered(*item)?;
177            }
178            TypeBody::Record(fields) => {
179                if fields.len() > MAX_FIELDS {
180                    return Err(Error::InvalidSchema);
181                }
182                for field in *fields {
183                    self.include(field.value)?;
184                }
185            }
186            TypeBody::Enum(variants) => {
187                if variants.len() > 64 {
188                    return Err(Error::InvalidSchema);
189                }
190                for variant in *variants {
191                    if let Some(payload) = variant.payload {
192                        self.include(payload.value)?;
193                    }
194                }
195            }
196        }
197        Ok(())
198    }
199
200    fn include_ordered(&mut self, value: FieldType) -> Result<(), Error> {
201        match crate::key::operand_type(value) {
202            FieldType::List { .. } => return Err(Error::InvalidSchema),
203            FieldType::Named(link) if unit_enum_len((link.definition)()).is_none() => {
204                return Err(Error::InvalidSchema);
205            }
206            _ => {}
207        }
208        self.include(value)
209    }
210
211    pub fn definitions(&self) -> impl Iterator<Item = &'static TypeSchema> + '_ {
212        self.definitions.values().copied()
213    }
214
215    pub fn contains(&self, other: &Self) -> bool {
216        other
217            .definitions
218            .iter()
219            .all(|(name, definition)| self.definitions.get(name) == Some(definition))
220    }
221
222    pub fn encode(&mut self, bytes: &mut Vec<u8>) -> Result<(), Error> {
223        if self.definitions.is_empty() {
224            return Ok(());
225        }
226        bytes.extend(b"ICDBTY02");
227        bytes.extend((MAX_DEPTH as u32).to_le_bytes());
228        bytes.extend((MAX_NODES as u32).to_le_bytes());
229        bytes.extend((self.definitions.len() as u32).to_le_bytes());
230        for definition in self.definitions.values() {
231            let (kind, count) = match &definition.body {
232                TypeBody::Enum(v) => (1, v.len()),
233                TypeBody::Record(f) => (2, f.len()),
234                TypeBody::Set { .. } => (3, 1),
235                TypeBody::Map { .. } => (4, 2),
236                TypeBody::Wrapped(_) => (5, 1),
237            };
238            bytes.push(kind);
239            name(bytes, definition.name)?;
240            bytes.extend((count as u32).to_le_bytes());
241            match &definition.body {
242                TypeBody::Wrapped(value) => encode_type(bytes, *value, false, false)?,
243                TypeBody::Map {
244                    key,
245                    value,
246                    max_items,
247                } => {
248                    bytes.extend(max_items.to_le_bytes());
249                    bytes.extend((MAX_COLLECTION_ITEMS as u32).to_le_bytes());
250                    encode_type(bytes, *key, false, false)?;
251                    encode_type(bytes, value.value, value.optional, false)?;
252                }
253                TypeBody::Set { item, max_items } => {
254                    bytes.extend(max_items.to_le_bytes());
255                    bytes.extend((MAX_COLLECTION_ITEMS as u32).to_le_bytes());
256                    encode_type(bytes, *item, false, false)?;
257                }
258                TypeBody::Enum(variants) => {
259                    if variants.is_empty()
260                        || variants.len() > 64
261                        || variants.windows(2).any(|w| w[0].name >= w[1].name)
262                    {
263                        return Err(Error::InvalidSchema);
264                    }
265                    for variant in *variants {
266                        name(bytes, variant.name)?;
267                        bytes.push(u8::from(variant.payload.is_some()));
268                        if let Some(payload) = variant.payload {
269                            encode_type(bytes, payload.value, payload.optional, false)?;
270                        }
271                    }
272                }
273                TypeBody::Record(fields) => {
274                    if fields.len() > MAX_FIELDS
275                        || fields.windows(2).any(|w| w[0].name >= w[1].name)
276                    {
277                        return Err(Error::InvalidSchema);
278                    }
279                    for field in *fields {
280                        if field.reference.is_some()
281                            || field.default.is_some()
282                            || field.managed.is_some()
283                        {
284                            return Err(Error::InvalidSchema);
285                        }
286                        name(bytes, field.name)?;
287                        encode_type(bytes, field.value, field.optional, false)?;
288                    }
289                }
290            }
291        }
292        // Least fixed point: an optional/list edge or unit alternative is a finite
293        // constructor; a required cycle without a base case never becomes viable.
294        let mut finite = BTreeSet::new();
295        for _ in 0..self.definitions.len() {
296            for (name, definition) in &self.definitions {
297                let viable = |value, optional| {
298                    optional
299                        || match value {
300                            FieldType::Named(link) => finite.contains(link.name),
301                            _ => true,
302                        }
303                };
304                let has_value = match &definition.body {
305                    TypeBody::Wrapped(_) | TypeBody::Set { .. } | TypeBody::Map { .. } => true,
306                    TypeBody::Record(fields) => fields.iter().all(|f| viable(f.value, f.optional)),
307                    TypeBody::Enum(variants) => variants
308                        .iter()
309                        .any(|v| v.payload.is_none_or(|p| viable(p.value, p.optional))),
310                };
311                if has_value {
312                    finite.insert(*name);
313                }
314            }
315        }
316        if finite.len() != self.definitions.len() {
317            return Err(Error::InvalidSchema);
318        }
319        self.visited = Vec::new();
320        Ok(())
321    }
322}