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    /// Append a value within the enclosing row's shared budget.
102    /// # Errors
103    /// Refuses field, byte, depth or node bounds.
104    #[doc(hidden)]
105    fn encode_into(&self, writer: &mut Encoder) -> Result<(), Error>;
106    /// Decode within the enclosing row's shared budget.
107    /// # Errors
108    /// Refuses malformed values and exceeded bounds.
109    #[doc(hidden)]
110    fn decode_from(reader: &mut Decoder<'_>) -> Result<Self, Error>;
111}
112
113#[derive(Clone, Default)]
114pub(crate) struct TypeGraph {
115    definitions: BTreeMap<&'static str, &'static TypeSchema>,
116    // Addresses only terminate traversal of compiler-emitted static nodes; they
117    // are never identities, persisted bytes or function-pointer comparisons.
118    visited: Vec<&'static TypeSchema>,
119}
120impl TypeGraph {
121    pub fn include(&mut self, value: FieldType) -> Result<(), Error> {
122        let value = if let FieldType::List { item, max_items } = value {
123            if max_items > MAX_COLLECTION_ITEMS as u32 || matches!(item, FieldType::List { .. }) {
124                return Err(Error::InvalidSchema);
125            }
126            *item
127        } else {
128            value
129        };
130        let FieldType::Named(link) = value else {
131            return Ok(());
132        };
133        let definition = (link.definition)();
134        if definition.name != link.name {
135            return Err(Error::InvalidSchema);
136        }
137        if self
138            .visited
139            .iter()
140            .any(|seen| std::ptr::eq(*seen, definition))
141        {
142            return Ok(());
143        }
144        if self.visited.len() >= 64 {
145            return Err(Error::InvalidSchema);
146        }
147        self.visited.push(definition);
148        if self
149            .definitions
150            .insert(link.name, definition)
151            .is_some_and(|old| old != definition)
152            || self.definitions.len() > 32
153        {
154            return Err(Error::InvalidSchema);
155        }
156        match &definition.body {
157            TypeBody::Wrapped(FieldType::Named(_)) => return Err(Error::InvalidSchema),
158            TypeBody::Wrapped(value) => self.include(*value)?,
159            TypeBody::Map {
160                key,
161                value,
162                max_items,
163            } => {
164                if *max_items > MAX_COLLECTION_ITEMS as u32 {
165                    return Err(Error::InvalidSchema);
166                }
167                self.include_ordered(*key)?;
168                self.include(value.value)?;
169            }
170            TypeBody::Set { item, max_items } => {
171                if *max_items > MAX_COLLECTION_ITEMS as u32 {
172                    return Err(Error::InvalidSchema);
173                }
174                self.include_ordered(*item)?;
175            }
176            TypeBody::Record(fields) => {
177                if fields.len() > MAX_FIELDS {
178                    return Err(Error::InvalidSchema);
179                }
180                for field in *fields {
181                    self.include(field.value)?;
182                }
183            }
184            TypeBody::Enum(variants) => {
185                if variants.len() > 64 {
186                    return Err(Error::InvalidSchema);
187                }
188                for variant in *variants {
189                    if let Some(payload) = variant.payload {
190                        self.include(payload.value)?;
191                    }
192                }
193            }
194        }
195        Ok(())
196    }
197    fn include_ordered(&mut self, value: FieldType) -> Result<(), Error> {
198        match crate::key::operand_type(value) {
199            FieldType::List { .. } => return Err(Error::InvalidSchema),
200            FieldType::Named(link) if unit_enum_len((link.definition)()).is_none() => {
201                return Err(Error::InvalidSchema);
202            }
203            _ => {}
204        }
205        self.include(value)
206    }
207    pub fn definitions(&self) -> impl Iterator<Item = &'static TypeSchema> + '_ {
208        self.definitions.values().copied()
209    }
210    pub fn contains(&self, other: &Self) -> bool {
211        other
212            .definitions
213            .iter()
214            .all(|(name, definition)| self.definitions.get(name) == Some(definition))
215    }
216    pub fn encode(&mut self, bytes: &mut Vec<u8>) -> Result<(), Error> {
217        if self.definitions.is_empty() {
218            return Ok(());
219        }
220        bytes.extend(b"ICDBTY02");
221        bytes.extend((MAX_DEPTH as u32).to_le_bytes());
222        bytes.extend((MAX_NODES as u32).to_le_bytes());
223        bytes.extend((self.definitions.len() as u32).to_le_bytes());
224        for definition in self.definitions.values() {
225            let (kind, count) = match &definition.body {
226                TypeBody::Enum(v) => (1, v.len()),
227                TypeBody::Record(f) => (2, f.len()),
228                TypeBody::Set { .. } => (3, 1),
229                TypeBody::Map { .. } => (4, 2),
230                TypeBody::Wrapped(_) => (5, 1),
231            };
232            bytes.push(kind);
233            name(bytes, definition.name)?;
234            bytes.extend((count as u32).to_le_bytes());
235            match &definition.body {
236                TypeBody::Wrapped(value) => encode_type(bytes, *value, false, false)?,
237                TypeBody::Map {
238                    key,
239                    value,
240                    max_items,
241                } => {
242                    bytes.extend(max_items.to_le_bytes());
243                    bytes.extend((MAX_COLLECTION_ITEMS as u32).to_le_bytes());
244                    encode_type(bytes, *key, false, false)?;
245                    encode_type(bytes, value.value, value.optional, false)?;
246                }
247                TypeBody::Set { item, max_items } => {
248                    bytes.extend(max_items.to_le_bytes());
249                    bytes.extend((MAX_COLLECTION_ITEMS as u32).to_le_bytes());
250                    encode_type(bytes, *item, false, false)?;
251                }
252                TypeBody::Enum(variants) => {
253                    if variants.is_empty()
254                        || variants.len() > 64
255                        || variants.windows(2).any(|w| w[0].name >= w[1].name)
256                    {
257                        return Err(Error::InvalidSchema);
258                    }
259                    for variant in *variants {
260                        name(bytes, variant.name)?;
261                        bytes.push(u8::from(variant.payload.is_some()));
262                        if let Some(payload) = variant.payload {
263                            encode_type(bytes, payload.value, payload.optional, false)?;
264                        }
265                    }
266                }
267                TypeBody::Record(fields) => {
268                    if fields.len() > MAX_FIELDS
269                        || fields.windows(2).any(|w| w[0].name >= w[1].name)
270                    {
271                        return Err(Error::InvalidSchema);
272                    }
273                    for field in *fields {
274                        if field.reference.is_some()
275                            || field.default.is_some()
276                            || field.managed.is_some()
277                        {
278                            return Err(Error::InvalidSchema);
279                        }
280                        name(bytes, field.name)?;
281                        encode_type(bytes, field.value, field.optional, false)?;
282                    }
283                }
284            }
285        }
286        // Least fixed point: an optional/list edge or unit alternative is a finite
287        // constructor; a required cycle without a base case never becomes viable.
288        let mut finite = BTreeSet::new();
289        for _ in 0..self.definitions.len() {
290            for (name, definition) in &self.definitions {
291                let viable = |value, optional| {
292                    optional
293                        || match value {
294                            FieldType::Named(link) => finite.contains(link.name),
295                            _ => true,
296                        }
297                };
298                let has_value = match &definition.body {
299                    TypeBody::Wrapped(_) | TypeBody::Set { .. } | TypeBody::Map { .. } => true,
300                    TypeBody::Record(fields) => fields.iter().all(|f| viable(f.value, f.optional)),
301                    TypeBody::Enum(variants) => variants
302                        .iter()
303                        .any(|v| v.payload.is_none_or(|p| viable(p.value, p.optional))),
304                };
305                if has_value {
306                    finite.insert(*name);
307                }
308            }
309        }
310        if finite.len() != self.definitions.len() {
311            return Err(Error::InvalidSchema);
312        }
313        self.visited = Vec::new();
314        Ok(())
315    }
316}