datumesh_core/
lexical.rs

1//! Lexical forms: names (2), scalars (3), hex, licences, key references (9.1) and units (7.1).
2//!
3//! Every check takes the path of the value it checks, for the error it may return. Each value
4//! is checked against its lexical form first and its length limit second (SPEC 4.5).
5
6use crate::error::{err, ErrorCode, Result};
7use crate::tables;
8
9/// Limits of SPEC 4.5.
10pub mod limits {
11    /// Characters in a function name, path segment, argument name or code language.
12    pub const NAME: usize = 64;
13    /// Characters in `<namespace>/<function>`.
14    pub const FUNCTION_NAME: usize = 512;
15    /// Arguments per function or cell.
16    pub const ARGS: usize = 32;
17    /// Characters in a number.
18    pub const NUMBER: usize = 128;
19    /// UTF-8 bytes in a string value.
20    pub const STRING: usize = 1024;
21    /// UTF-8 bytes in a receipt summary.
22    pub const SUMMARY: usize = 1024;
23    /// UTF-8 bytes in a function body.
24    pub const BODY: usize = 1_048_576;
25    /// Entries in a receipt's or descriptor's `inputs`.
26    pub const INPUTS: usize = 4096;
27    /// Characters in an SPDX licence identifier.
28    pub const LICENCE_SPDX: usize = 64;
29    /// Characters in a licence URL.
30    pub const LICENCE_URL: usize = 512;
31    /// Keys in one key publication.
32    pub const KEYS: usize = 64;
33    /// Characters in a blob media type (3.7).
34    pub const MEDIA_TYPE: usize = 128;
35    /// Characters in an index unit (`units.md` 2.4).
36    pub const INDEX_UNIT: usize = 64;
37    /// The largest blob length, 2^53 - 1.
38    pub const BLOB_LENGTH: u64 = 9_007_199_254_740_991;
39    /// Values in an argument's extent (7; `spec-0.4.0`).
40    pub const EXTENT: usize = 4096;
41    /// Member receipt hashes in a slice manifest (15.13; `spec-0.4.0`).
42    pub const MEMBERS: usize = 1_048_576;
43    /// Function names in a key document's `declarations` (9.2; `spec-0.4.3`).
44    pub const DECLARATIONS: usize = 64;
45    /// Entries for one declared function name (9.2; `spec-0.4.3`).
46    pub const DECLARATION_ENTRIES: usize = 16;
47}
48
49fn is_lower_digit(c: u8) -> bool {
50    c.is_ascii_lowercase() || c.is_ascii_digit()
51}
52
53/// The grammar of 2.2 without its length limit.
54pub(crate) fn is_name_grammar(s: &str) -> bool {
55    let b = s.as_bytes();
56    match b.first() {
57        Some(c) if c.is_ascii_lowercase() => {}
58        _ => return false,
59    }
60    let mut prev_underscore = false;
61    for &c in &b[1..] {
62        if c == b'_' {
63            if prev_underscore {
64                return false;
65            }
66            prev_underscore = true;
67        } else if is_lower_digit(c) {
68            prev_underscore = false;
69        } else {
70            return false;
71        }
72    }
73    !prev_underscore
74}
75
76/// A name (2.2): function names, path segments and code languages. `E_CANON_NAME`, then `E_CANON_LIMIT`.
77pub fn check_name(s: &str, path: &str) -> Result<()> {
78    if !is_name_grammar(s) {
79        return err(ErrorCode::CanonName, path, format!("not a lowercase snake_case name: {s:?}"));
80    }
81    if s.len() > limits::NAME {
82        return err(ErrorCode::CanonLimit, path, "name longer than 64 characters");
83    }
84    Ok(())
85}
86
87/// An argument name (2.4): grammar (`E_CANON_ARG_NAME`), length (`E_CANON_LIMIT`), then reserved
88/// names (`asof`, `fn_hash` since `spec-0.4.2`, and `dm_…`).
89pub fn check_arg_name(s: &str, path: &str) -> Result<()> {
90    if !is_name_grammar(s) {
91        return err(ErrorCode::CanonArgName, path, format!("not a lowercase snake_case name: {s:?}"));
92    }
93    if s.len() > limits::NAME {
94        return err(ErrorCode::CanonLimit, path, "name longer than 64 characters");
95    }
96    // `fn_hash` reserved since spec-0.4.2: the cell URI's pin (5.1).
97    if s == "asof" || s == "fn_hash" || s.starts_with("dm_") {
98        return err(ErrorCode::CanonArgName, path, format!("reserved argument name {s:?}"));
99    }
100    Ok(())
101}
102
103/// A DNS name (2.1). Every failure is `E_CANON_NAME`.
104pub fn check_dns_name(s: &str, path: &str) -> Result<()> {
105    if s.len() > 253 {
106        return err(ErrorCode::CanonName, path, "DNS name longer than 253 characters");
107    }
108    let labels: Vec<&str> = s.split('.').collect();
109    if labels.len() < 2 {
110        return err(ErrorCode::CanonName, path, format!("DNS name needs at least two labels: {s:?}"));
111    }
112    for l in &labels {
113        let b = l.as_bytes();
114        let ok = !b.is_empty()
115            && b.len() <= 63
116            && b.iter().all(|&c| is_lower_digit(c) || c == b'-')
117            && b[0] != b'-'
118            && b[b.len() - 1] != b'-';
119        if !ok {
120            return err(ErrorCode::CanonName, path, format!("bad DNS label {l:?}"));
121        }
122    }
123    if labels.last().is_some_and(|l| l.bytes().all(|c| c.is_ascii_digit())) {
124        return err(ErrorCode::CanonName, path, "top-level label is numeric");
125    }
126    Ok(())
127}
128
129/// A namespace (2.3): a DNS name, then path segments that are names.
130pub fn check_namespace(s: &str, path: &str) -> Result<()> {
131    let mut parts = s.split('/');
132    check_dns_name(parts.next().unwrap_or(""), path)?;
133    for seg in parts {
134        check_name(seg, path)?;
135    }
136    Ok(())
137}
138
139/// The host of a namespace: its DNS name.
140pub(crate) fn host_of(namespace: &str) -> &str {
141    namespace.split('/').next().unwrap_or(namespace)
142}
143
144/// Whether a namespace or host is unrooted (2.5, `spec-0.4.3`): its host's last label is
145/// `invalid` (`local.invalid`, `agent-7.local.invalid`, `local.invalid/notes`). `.invalid` never
146/// resolves (RFC 2606, RFC 6761 6.4), so an unrooted host is never a real host; every other
147/// namespace is rooted. The name is not checked: check it with [`check_namespace`] (a namespace)
148/// or [`check_dns_name`] (a host) first; `local.invalid` passes both. A mesh refuses at define
149/// time a rooted function whose `inputs` name an unrooted one; a verifier never checks this.
150pub fn is_unrooted(name: &str) -> bool {
151    let host = name.split('/').next().unwrap_or("");
152    host.rsplit('.').next() == Some("invalid")
153}
154
155/// A fully qualified function name (2.3): namespace, `/`, name; at most 512 characters.
156pub fn check_function_name(s: &str, path: &str) -> Result<()> {
157    let Some((ns, f)) = s.rsplit_once('/') else {
158        return err(ErrorCode::CanonName, path, format!("function name has no namespace: {s:?}"));
159    };
160    check_namespace(ns, path)?;
161    check_name(f, path)?;
162    if s.len() > limits::FUNCTION_NAME {
163        return err(ErrorCode::CanonLimit, path, "function name longer than 512 characters");
164    }
165    Ok(())
166}
167
168/// Lowercase hex of exactly `digits` digits (`E_CANON_HEX`).
169pub fn check_hex(s: &str, digits: usize, path: &str) -> Result<()> {
170    if s.len() != digits || !s.bytes().all(|c| c.is_ascii_digit() || (b'a'..=b'f').contains(&c)) {
171        return err(ErrorCode::CanonHex, path, format!("expected {digits} lowercase hex digits"));
172    }
173    Ok(())
174}
175
176/// A key reference `<host>#<key id>` (9.1).
177pub fn check_key_ref(s: &str, path: &str) -> Result<()> {
178    let Some((host, id)) = s.split_once('#') else {
179        return err(ErrorCode::CanonName, path, "a key reference is <host>#<key id>");
180    };
181    check_dns_name(host, path)?;
182    check_hex(id, 16, path)
183}
184
185/// The number grammar of 3.1 without the length limit.
186pub(crate) fn is_number_grammar(s: &str) -> bool {
187    let b = s.as_bytes();
188    let mut i = 0;
189    if b.first() == Some(&b'-') {
190        i = 1;
191    }
192    match b.get(i) {
193        Some(b'0') => i += 1,
194        Some(b'1'..=b'9') => {
195            while b.get(i).is_some_and(u8::is_ascii_digit) {
196                i += 1;
197            }
198        }
199        _ => return false,
200    }
201    if b.get(i) == Some(&b'.') {
202        let frac = &b[i + 1..];
203        if frac.is_empty() || !frac.iter().all(u8::is_ascii_digit) || frac[frac.len() - 1] == b'0' {
204            return false;
205        }
206        i = b.len();
207    }
208    i == b.len() && s != "-0"
209}
210
211/// Compares two numbers in canonical form (3.1) numerically.
212pub(crate) fn cmp_numbers(a: &str, b: &str) -> core::cmp::Ordering {
213    use core::cmp::Ordering;
214    let (an, a) = a.strip_prefix('-').map_or((false, a), |x| (true, x));
215    let (bn, b) = b.strip_prefix('-').map_or((false, b), |x| (true, x));
216    // Canonical: no "-0", so a negative number is below every other.
217    let magnitude = || {
218        let (ai, af) = a.split_once('.').unwrap_or((a, ""));
219        let (bi, bf) = b.split_once('.').unwrap_or((b, ""));
220        ai.len().cmp(&bi.len()).then_with(|| ai.cmp(bi)).then_with(|| af.cmp(bf))
221    };
222    match (an, bn) {
223        (false, false) => magnitude(),
224        (true, true) => magnitude().reverse(),
225        (true, false) => Ordering::Less,
226        (false, true) => Ordering::Greater,
227    }
228}
229
230/// Whether a canonical number is an integer.
231pub(crate) fn is_integer(s: &str) -> bool {
232    !s.contains('.')
233}
234
235/// Whether `s` is an `inputs` entry of the slice form `slice:<64 hex>:<64 hex>` (8.1).
236pub(crate) fn split_slice_entry(s: &str) -> Option<(&str, &str)> {
237    let rest = s.strip_prefix("slice:")?;
238    let (id, members) = rest.split_once(':')?;
239    let hex = |h: &str| h.len() == 64 && h.bytes().all(|c| c.is_ascii_digit() || (b'a'..=b'f').contains(&c));
240    (hex(id) && hex(members)).then_some((id, members))
241}
242
243/// An `inputs` entry (8.1, 10.1 step 3): 64 lowercase hex digits, or since `spec-0.4.0` a
244/// slice entry `slice:<slice id>:<members hash>` (135 characters); `E_CANON_HEX` otherwise.
245pub fn check_input_entry(s: &str, path: &str) -> Result<()> {
246    if s.starts_with("slice:") {
247        if split_slice_entry(s).is_none() {
248            return err(ErrorCode::CanonHex, path, format!("not a slice entry slice:<64 hex>:<64 hex>: {s:?}"));
249        }
250        return Ok(());
251    }
252    check_hex(s, 64, path)
253}
254
255/// A number (3.1): `E_CANON_NUMBER`, then `E_CANON_LIMIT`.
256pub fn check_number(s: &str, path: &str) -> Result<()> {
257    if !is_number_grammar(s) {
258        return err(ErrorCode::CanonNumber, path, format!("not a canonical decimal: {s:?}"));
259    }
260    if s.len() > limits::NUMBER {
261        return err(ErrorCode::CanonLimit, path, "number longer than 128 characters");
262    }
263    Ok(())
264}
265
266fn digits(b: &[u8]) -> Option<u32> {
267    if b.is_empty() || !b.iter().all(u8::is_ascii_digit) {
268        return None;
269    }
270    Some(b.iter().fold(0u32, |a, &c| a * 10 + u32::from(c - b'0')))
271}
272
273fn days_in_month(y: u32, m: u32) -> u32 {
274    match m {
275        1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
276        4 | 6 | 9 | 11 => 30,
277        2 if (y.is_multiple_of(4) && !y.is_multiple_of(100)) || y.is_multiple_of(400) => 29,
278        2 => 28,
279        _ => 0,
280    }
281}
282
283/// `YYYY-MM-DD`, a real day in years 0001-9999.
284pub(crate) fn is_date(s: &str) -> bool {
285    let b = s.as_bytes();
286    if b.len() != 10 || b[4] != b'-' || b[7] != b'-' {
287        return false;
288    }
289    let (Some(y), Some(m), Some(d)) = (digits(&b[0..4]), digits(&b[5..7]), digits(&b[8..10])) else {
290        return false;
291    };
292    (1..=9999).contains(&y) && (1..=12).contains(&m) && d >= 1 && d <= days_in_month(y, m)
293}
294
295/// A date (3.2), `E_CANON_DATE`.
296pub fn check_date(s: &str, path: &str) -> Result<()> {
297    if !is_date(s) {
298        return err(ErrorCode::CanonDate, path, format!("not a YYYY-MM-DD calendar date: {s:?}"));
299    }
300    Ok(())
301}
302
303/// `YYYY-MM-DDTHH:MM:SS.ffffffZ`.
304pub(crate) fn is_instant(s: &str) -> bool {
305    let b = s.as_bytes();
306    if b.len() != 27 || !s.is_char_boundary(10) || !is_date(&s[..10]) {
307        return false;
308    }
309    if b[10] != b'T' || b[13] != b':' || b[16] != b':' || b[19] != b'.' || b[26] != b'Z' {
310        return false;
311    }
312    let (Some(h), Some(mi), Some(se), Some(_)) =
313        (digits(&b[11..13]), digits(&b[14..16]), digits(&b[17..19]), digits(&b[20..26]))
314    else {
315        return false;
316    };
317    h < 24 && mi < 60 && se < 60
318}
319
320/// An instant (3.3), `E_CANON_INSTANT`.
321pub fn check_instant(s: &str, path: &str) -> Result<()> {
322    if !is_instant(s) {
323        return err(ErrorCode::CanonInstant, path, format!("not YYYY-MM-DDTHH:MM:SS.ffffffZ: {s:?}"));
324    }
325    Ok(())
326}
327
328fn is_restricted_name(s: &str) -> bool {
329    let b = s.as_bytes();
330    !b.is_empty() && is_lower_digit(b[0]) && b.iter().all(|&c| is_lower_digit(c) || b"!#$&-^_.+".contains(&c))
331}
332
333/// A blob (3.7): its sha256, length and media type. Every failure is `E_CANON_BLOB`.
334pub(crate) fn parse_blob(s: &str) -> core::result::Result<([u8; 32], u64, &str), String> {
335    let mut parts = s.split(':');
336    let (Some(h), Some(len), Some(mt), None) = (parts.next(), parts.next(), parts.next(), parts.next()) else {
337        return Err("a blob is <sha256>:<length>:<media type>".into());
338    };
339    let hash = match decode_hex_lower::<32>(h) {
340        Some(x) => x,
341        None => return Err("the hash is 64 lowercase hex digits".into()),
342    };
343    let lb = len.as_bytes();
344    if lb.is_empty() || !lb.iter().all(u8::is_ascii_digit) || (lb.len() > 1 && lb[0] == b'0') || lb.len() > 16 {
345        return Err("the length is a canonical non-negative integer".into());
346    }
347    let n: u64 = len.parse().map_err(|_| String::from("bad length"))?;
348    if n > limits::BLOB_LENGTH {
349        return Err("length above 9007199254740991".into());
350    }
351    let ok_mt = match mt.split_once('/') {
352        Some((t, st)) => is_restricted_name(t) && is_restricted_name(st),
353        None => false,
354    };
355    if !ok_mt {
356        return Err(format!("not a lowercase type/subtype media type: {mt:?}"));
357    }
358    if mt.len() > limits::MEDIA_TYPE {
359        return Err("media type longer than 128 characters".into());
360    }
361    Ok((hash, n, mt))
362}
363
364/// A blob (3.7), `E_CANON_BLOB`.
365pub fn check_blob(s: &str, path: &str) -> Result<()> {
366    match parse_blob(s) {
367        Ok(_) => Ok(()),
368        Err(d) => err(ErrorCode::CanonBlob, path, d),
369    }
370}
371
372/// Decodes exactly `N` bytes of lowercase hex.
373pub(crate) fn decode_hex_lower<const N: usize>(s: &str) -> Option<[u8; N]> {
374    let b = s.as_bytes();
375    if b.len() != 2 * N {
376        return None;
377    }
378    let mut out = [0u8; N];
379    for (i, o) in out.iter_mut().enumerate() {
380        let hi = hexval(b[2 * i])?;
381        let lo = hexval(b[2 * i + 1])?;
382        *o = (hi << 4) | lo;
383    }
384    Some(out)
385}
386
387fn hexval(c: u8) -> Option<u8> {
388    match c {
389        b'0'..=b'9' => Some(c - b'0'),
390        b'a'..=b'f' => Some(c - b'a' + 10),
391        _ => None,
392    }
393}
394
395/// Lowercase hex of bytes.
396pub fn to_hex(bytes: &[u8]) -> String {
397    const HEX: &[u8; 16] = b"0123456789abcdef";
398    let mut s = String::with_capacity(bytes.len() * 2);
399    for &b in bytes {
400        s.push(char::from(HEX[usize::from(b >> 4)]));
401        s.push(char::from(HEX[usize::from(b & 0xF)]));
402    }
403    s
404}
405
406/// Whether a code point is assigned in Unicode 15.1, by the spec's own table.
407pub fn is_assigned_15_1(c: char) -> bool {
408    let cp = c as u32;
409    tables::ASSIGNED
410        .binary_search_by(|&(lo, hi)| {
411            if hi < cp {
412                core::cmp::Ordering::Less
413            } else if lo > cp {
414                core::cmp::Ordering::Greater
415            } else {
416                core::cmp::Ordering::Equal
417            }
418        })
419        .is_ok()
420}
421
422/// The string rules of 3.5 in order: characters, NFC, then the byte limit.
423/// `allow_tab_lf` relaxes the control rule for function bodies (7).
424pub(crate) fn check_text(s: &str, limit: usize, allow_tab_lf: bool, path: &str) -> Result<()> {
425    for c in s.chars() {
426        let cp = c as u32;
427        if (cp < 0x20 && !(allow_tab_lf && (c == '\t' || c == '\n'))) || (0x7F..=0x9F).contains(&cp) {
428            return err(ErrorCode::CanonString, path, format!("control character U+{cp:04X}"));
429        }
430        if !is_assigned_15_1(c) {
431            return err(ErrorCode::CanonString, path, format!("U+{cp:04X} is not assigned in Unicode 15.1"));
432        }
433    }
434    if !unicode_normalization::is_nfc(s) {
435        return err(ErrorCode::CanonString, path, "not in Normalization Form C");
436    }
437    if s.len() > limit {
438        return err(ErrorCode::CanonLimit, path, format!("longer than {limit} UTF-8 bytes"));
439    }
440    Ok(())
441}
442
443/// A string value (3.5).
444pub fn check_string(s: &str, path: &str) -> Result<()> {
445    check_text(s, limits::STRING, false, path)
446}
447
448/// A licence (8.1): grammar (`E_CANON_LICENCE`), then length (`E_CANON_LIMIT`).
449pub fn check_licence(s: &str, path: &str) -> Result<()> {
450    if let Some(rest) = s.strip_prefix("https://") {
451        if rest.is_empty() || !rest.bytes().all(|c| (0x21..=0x7E).contains(&c)) {
452            return err(ErrorCode::CanonLicence, path, "a licence URL is https:// and printable ASCII");
453        }
454        if s.len() > limits::LICENCE_URL {
455            return err(ErrorCode::CanonLimit, path, "licence URL longer than 512 characters");
456        }
457        return Ok(());
458    }
459    let b = s.as_bytes();
460    let ok = !b.is_empty()
461        && b[0].is_ascii_alphanumeric()
462        && b.iter().all(|&c| c.is_ascii_alphanumeric() || c == b'.' || c == b'+' || c == b'-');
463    if !ok {
464        return err(ErrorCode::CanonLicence, path, format!("not an SPDX identifier or https URL: {s:?}"));
465    }
466    if s.len() > limits::LICENCE_SPDX {
467        return err(ErrorCode::CanonLimit, path, "licence identifier longer than 64 characters");
468    }
469    Ok(())
470}
471
472/// Whether `s` is a currency code of `units.md` 2.1 (withdrawn codes included).
473pub fn is_currency(s: &str) -> bool {
474    tables::CURRENCIES.contains(&s)
475}
476
477/// Whether `s` is an index unit (`units.md` 2.4).
478pub fn is_index_unit(s: &str) -> bool {
479    if s.len() > limits::INDEX_UNIT {
480        return false;
481    }
482    let Some(rest) = s.strip_prefix("index:") else { return false };
483    let Some((period, value)) = rest.split_once('=') else { return false };
484    let period_ok = match period.len() {
485        4 => is_date(&format!("{period}-01-01")),
486        7 => is_date(&format!("{period}-01")),
487        10 => is_date(period),
488        _ => false,
489    };
490    // Shapes like "2015-1-01" must not slip through the padding above.
491    let shape_ok =
492        period.bytes().enumerate().all(|(i, c)| if i == 4 || i == 7 { c == b'-' } else { c.is_ascii_digit() });
493    period_ok && shape_ok && is_number_grammar(value) && !value.starts_with('-') && value != "0"
494}
495
496/// Whether `s` is a literal unit: listed in `units.md` 2.1-2.3, or an index unit.
497pub fn is_literal_unit(s: &str) -> bool {
498    is_currency(s) || tables::PHYSICAL.contains(&s) || tables::RATIOS.contains(&s) || is_index_unit(s)
499}
500
501#[cfg(test)]
502mod tests {
503    use super::*;
504
505    #[test]
506    fn names() {
507        for ok in ["fx_rate", "base", "a01", "v2_final"] {
508            assert!(is_name_grammar(ok), "{ok}");
509        }
510        for bad in ["FxRate", "_x", "x_", "a__b", "1st", ""] {
511            assert!(!is_name_grammar(bad), "{bad}");
512        }
513    }
514
515    #[test]
516    fn numbers() {
517        for ok in ["0", "-1", "1.5", "0.001", "10"] {
518            assert!(is_number_grammar(ok), "{ok}");
519        }
520        for bad in ["-0", "01", "1.", ".5", "1.50", "+1", "1e3", "", "-", "0.0"] {
521            assert!(!is_number_grammar(bad), "{bad}");
522        }
523    }
524
525    #[test]
526    fn index_units() {
527        assert!(is_index_unit("index:2015=100"));
528        assert!(is_index_unit("index:1984-01-03=1000"));
529        assert!(is_index_unit("index:2016-02-29=0.5"));
530        for bad in [
531            "index:0000=1",
532            "index:2015=0",
533            "index:2015=-1",
534            "index:2015-13=1",
535            "index:2015-02-29=1",
536            "index:2015=1.0",
537            "index:15=1",
538        ] {
539            assert!(!is_index_unit(bad), "{bad}");
540        }
541    }
542
543    #[test]
544    fn instants() {
545        assert!(is_instant("2024-03-15T16:00:00.000000Z"));
546        assert!(!is_instant("2024-03-15T24:00:00.000000Z"));
547        assert!(!is_instant("2024-03-15T23:59:60.000000Z"));
548        assert!(!is_instant("2023-02-29T00:00:00.000000Z"));
549    }
550}
datumesh_core/lexical.rs

datumesh_core/
lexical.rs
