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

datumesh_core/
lexical.rs
