Skip to main content

unityrs_export/ngui/
keys.rs

1//! Key templates, `safe()` and the key rules (`docs/BATCH_SPEC.md` 2.1 to
2//! 2.3; `docs/plans/extract.md` E27, E28).
3//!
4//! A [`Template`] is parsed once, refusing an unknown variable or one its
5//! kind does not allow (validation's refusal, exit 78, is the engine's). Its
6//! expansion is bytes, a plain variable written verbatim (a name's stored
7//! bytes) and a `safe_` one through [`safe_into`]; [`check`] then names the
8//! first rule of 2.3 the key breaks, or gives it back as UTF-8, and
9//! [`check_prefixed`] checks it again after the sink's prefix, as 2.3 says.
10//! An expansion stops at [`STOP`] bytes (`docs/plans/batch.md` 2.6 step 5),
11//! written into a buffer of that capacity the caller charged, each value
12//! read only as far as the room left (review round 2's S3), so a key past
13//! [`KEY_MAX`] is read no further and [`check`] decides it on what it holds
14//! (2.3's rule for a key past its bound). `prefix_conflict` and
15//! `archive_conflict` are phase 6's (4.6). [`KeyTable`] is the attempt's one
16//! key table, charged to `M_X`.
17
18use std::sync::Arc;
19
20use unityrs_core::limits::{Charge, Meter, heap_cost};
21
22use super::classify::Class;
23use super::table::{self, Set};
24
25/// An output kind a template expands for.
26#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
27pub enum TemplateKind {
28    /// `outputs.textures`' key.
29    Texture,
30    /// `outputs.sprites`' key.
31    Sprite,
32    /// `atlases.sprite_key`.
33    AtlasSprite,
34    /// `atlases.json_key`.
35    AtlasJson,
36    /// A loose prefab GLB.
37    Glb,
38}
39
40impl TemplateKind {
41    /// A `members` entry's `kind` (1.6) for this kind, as its outputs'
42    /// kind names it.
43    #[must_use]
44    pub fn name(self) -> &'static str {
45        match self {
46            Self::Texture => "texture",
47            Self::Sprite => "sprite",
48            Self::AtlasSprite => "atlas_sprite",
49            Self::AtlasJson => "atlas_json",
50            Self::Glb => "glb",
51        }
52    }
53}
54
55/// A template variable (2.1's table).
56#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
57pub enum Var {
58    /// `{input}`.
59    Input,
60    /// `{safe_input}`.
61    SafeInput,
62    /// `{type}`.
63    Type,
64    /// `{name}`.
65    Name,
66    /// `{safe_name}`.
67    SafeName,
68    /// `{path_id}`.
69    PathId,
70    /// `{atlas}`.
71    Atlas,
72    /// `{safe_atlas}`.
73    SafeAtlas,
74    /// `{sprite}`.
75    Sprite,
76    /// `{safe_sprite}`.
77    SafeSprite,
78    /// The stored container-row path.
79    ContainerPath,
80    /// The safe form of the container-row path.
81    SafeContainerPath,
82}
83
84impl Var {
85    /// A `safe_` variable's plain one.
86    #[must_use]
87    pub fn plain(self) -> Option<Self> {
88        Some(match self {
89            Self::SafeInput => Self::Input,
90            Self::SafeName => Self::Name,
91            Self::SafeAtlas => Self::Atlas,
92            Self::SafeSprite => Self::Sprite,
93            Self::SafeContainerPath => Self::ContainerPath,
94            _ => return None,
95        })
96    }
97
98    fn parse(name: &str) -> Option<Self> {
99        Some(match name {
100            "input" => Self::Input,
101            "safe_input" => Self::SafeInput,
102            "type" => Self::Type,
103            "name" => Self::Name,
104            "safe_name" => Self::SafeName,
105            "path_id" => Self::PathId,
106            "atlas" => Self::Atlas,
107            "safe_atlas" => Self::SafeAtlas,
108            "sprite" => Self::Sprite,
109            "safe_sprite" => Self::SafeSprite,
110            "container_path" => Self::ContainerPath,
111            "safe_container_path" => Self::SafeContainerPath,
112            _ => return None,
113        })
114    }
115
116    /// Whether 2.1's table allows it in a template of `kind`.
117    #[must_use]
118    pub fn allowed(self, kind: TemplateKind) -> bool {
119        match self {
120            Self::Input | Self::SafeInput | Self::PathId => true,
121            Self::Type | Self::Name | Self::SafeName => {
122                matches!(
123                    kind,
124                    TemplateKind::Texture | TemplateKind::Sprite | TemplateKind::Glb
125                )
126            }
127            Self::Atlas | Self::SafeAtlas => {
128                matches!(kind, TemplateKind::AtlasSprite | TemplateKind::AtlasJson)
129            }
130            Self::Sprite | Self::SafeSprite => kind == TemplateKind::AtlasSprite,
131            Self::ContainerPath | Self::SafeContainerPath => kind == TemplateKind::Glb,
132        }
133    }
134}
135
136#[derive(Clone, Debug, PartialEq, Eq)]
137enum Piece {
138    Lit(String),
139    Var(Var),
140}
141
142/// A parsed template.
143#[derive(Clone, Debug, PartialEq, Eq)]
144pub struct Template {
145    pieces: Vec<Piece>,
146}
147
148/// Why a template is refused.
149#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
150pub enum TemplateError {
151    /// An empty template (the grammar's `1*`).
152    #[error("an empty template")]
153    Empty,
154    /// A `{` with no `}`, or a lone `}`.
155    #[error("an unmatched brace at byte {0}")]
156    Brace(usize),
157    /// A variable 2.1 does not define.
158    #[error("unknown variable {0:?}")]
159    Unknown(String),
160    /// A variable 2.1 does not allow in this kind's templates.
161    #[error("variable {0:?} is not allowed here")]
162    NotAllowed(String),
163}
164
165/// A piece of a template's text as 2.1's grammar reads it, borrowed from
166/// the text: a run of literal characters, the one brace `{{` or `}}`
167/// writes, or a variable.
168#[derive(Clone, Copy, Debug, PartialEq, Eq)]
169pub enum Token<'t> {
170    /// Literal text, written as it is.
171    Lit(&'t str),
172    /// A variable 2.1 allows in the template's kind.
173    Var(Var),
174}
175
176/// The tokens of `text`, a template of `kind`, in order: the one reading
177/// of 2.1's grammar, which [`Template::parse`] and [`check_template`]
178/// share. It allocates nothing but an error's name, and ends after the
179/// first error. An empty text has no token (the grammar's `1*` is the
180/// caller's).
181#[must_use]
182pub fn tokens(text: &str, kind: TemplateKind) -> Tokens<'_> {
183    Tokens {
184        text,
185        kind,
186        at: 0,
187        done: false,
188    }
189}
190
191/// [`tokens`]' iterator.
192#[derive(Clone, Debug)]
193pub struct Tokens<'t> {
194    text: &'t str,
195    kind: TemplateKind,
196    at: usize,
197    done: bool,
198}
199
200impl<'t> Iterator for Tokens<'t> {
201    type Item = Result<Token<'t>, TemplateError>;
202
203    fn next(&mut self) -> Option<Self::Item> {
204        let at = self.at;
205        let rest = self.text.get(at..).unwrap_or_default();
206        if self.done || rest.is_empty() {
207            return None;
208        }
209        let token = if rest.starts_with("{{") || rest.starts_with("}}") {
210            self.at += 2;
211            Ok(Token::Lit(rest.get(..1).unwrap_or_default()))
212        } else if let Some(after) = rest.strip_prefix('{') {
213            match after.find('}') {
214                None => Err(TemplateError::Brace(at)),
215                Some(end) => {
216                    let name = after.get(..end).unwrap_or_default();
217                    self.at += end + 2;
218                    match Var::parse(name) {
219                        None => Err(TemplateError::Unknown(name.to_owned())),
220                        Some(var) if !var.allowed(self.kind) => {
221                            Err(TemplateError::NotAllowed(name.to_owned()))
222                        }
223                        Some(var) => Ok(Token::Var(var)),
224                    }
225                }
226            }
227        } else if rest.starts_with('}') {
228            Err(TemplateError::Brace(at))
229        } else {
230            let end = rest.find(['{', '}']).unwrap_or(rest.len());
231            self.at += end;
232            Ok(Token::Lit(rest.get(..end).unwrap_or_default()))
233        };
234        self.done = token.is_err();
235        Some(token)
236    }
237}
238
239impl Template {
240    #[cfg(feature = "gltf")]
241    pub(super) fn uses(&self, var: Var) -> bool {
242        self.pieces.iter().any(|piece| match piece {
243            Piece::Var(v) => *v == var || v.plain() == Some(var),
244            Piece::Lit(_) => false,
245        })
246    }
247
248    /// Parses `text` for a template of `kind` ([`tokens`]).
249    pub fn parse(text: &str, kind: TemplateKind) -> Result<Self, TemplateError> {
250        if text.is_empty() {
251            return Err(TemplateError::Empty);
252        }
253        let mut pieces = Vec::new();
254        let mut lit = String::new();
255        for token in tokens(text, kind) {
256            match token? {
257                Token::Lit(s) => lit.push_str(s),
258                Token::Var(var) => {
259                    if !lit.is_empty() {
260                        pieces.push(Piece::Lit(std::mem::take(&mut lit)));
261                    }
262                    pieces.push(Piece::Var(var));
263                }
264            }
265        }
266        if !lit.is_empty() {
267            pieces.push(Piece::Lit(lit));
268        }
269        Ok(Self { pieces })
270    }
271
272    /// The expansion into `out` (cleared first): each variable's value from
273    /// `value` (its raw bytes; a `safe_` variable's is [`safe`] of its plain
274    /// one's, made as it is written), stopping at [`STOP`] bytes: what
275    /// follows decides nothing ([`check`]), so it is never made. No value
276    /// is copied whole: each is written up to the room left, so `out` never
277    /// holds more than [`STOP`] bytes, and a caller that gave it that
278    /// capacity allocates nothing here.
279    ///
280    /// Gives how many of `out`'s last bytes are the start of a code point
281    /// the stop cut, one the whole expansion holds past the stop
282    /// ([`cut_tail`]): a text of the expansion drops them, where an invalid
283    /// byte is one code point (review round 3's P3). The code point may
284    /// span pieces: the bytes before the stop are read joined with the
285    /// expansion's next ones, of the piece cut and those after it (review
286    /// round 4's A3).
287    pub fn expand<'v>(&self, value: impl Fn(Var) -> &'v [u8], out: &mut Vec<u8>) -> usize {
288        out.clear();
289        for (k, p) in self.pieces.iter().enumerate() {
290            let room = STOP.saturating_sub(out.len());
291            if room == 0 {
292                return self.tail(out, &[], k, &value);
293            }
294            // A `safe_` value is ASCII: the stop cuts no code point of it.
295            let src = match p {
296                Piece::Lit(s) => s.as_bytes(),
297                Piece::Var(v) => match v.plain() {
298                    Some(plain) => {
299                        safe_into(value(plain), room, out);
300                        continue;
301                    }
302                    None => value(*v),
303                },
304            };
305            out.extend(src.iter().take(room));
306            if src.len() > room {
307                let rest = src.get(room..).unwrap_or_default();
308                return self.tail(out, rest, k + 1, &value);
309            }
310        }
311        0
312    }
313
314    /// [`cut_tail`] at the stop: `out`'s last three bytes joined with the
315    /// expansion's next three, `rest` of the piece cut, then the pieces from
316    /// `next` on. A `safe_` piece is ASCII, so no code point continues into
317    /// it: the bytes ahead end there.
318    fn tail<'v>(
319        &self,
320        out: &[u8],
321        rest: &[u8],
322        next: usize,
323        value: &impl Fn(Var) -> &'v [u8],
324    ) -> usize {
325        let head = out.get(out.len().saturating_sub(3)..).unwrap_or_default();
326        let later = self
327            .pieces
328            .get(next..)
329            .unwrap_or_default()
330            .iter()
331            .map_while(|p| match p {
332                Piece::Lit(s) => Some(s.as_bytes()),
333                Piece::Var(v) => v.plain().is_none().then(|| value(*v)),
334            })
335            .flatten();
336        let ahead = rest.iter().chain(later).take(3);
337        let mut window = [0u8; 6];
338        let mut len = 0;
339        for (slot, b) in window.iter_mut().zip(head.iter().chain(ahead)) {
340            *slot = *b;
341            len += 1;
342        }
343        cut_tail(window.get(..len).unwrap_or_default(), head.len())
344    }
345}
346
347/// How many of `src`'s first `at` bytes start a code point that `src`
348/// holds whole past `at`: none when `at` falls on a code point boundary,
349/// or the bytes there are no valid code point's start.
350#[must_use]
351pub fn cut_tail(src: &[u8], at: usize) -> usize {
352    let head = src.get(..at).unwrap_or_default();
353    for back in 1..=head.len().min(3) {
354        let i = head.len() - back;
355        let Some(&b) = head.get(i) else {
356            return 0;
357        };
358        if b & 0xC0 == 0x80 {
359            continue;
360        }
361        let width = match b {
362            0xC2..=0xDF => 2,
363            0xE0..=0xEF => 3,
364            0xF0..=0xF4 => 4,
365            _ => 0,
366        };
367        let whole = src
368            .get(i..i + width)
369            .is_some_and(|c| std::str::from_utf8(c).is_ok());
370        return if width > back && whole { back } else { 0 };
371    }
372    0
373}
374
375/// [`safe`] of `bytes` written into `out`, at most `room` bytes of it: the
376/// same bytes as the first `room` of [`safe`]'s, made a code point at a
377/// time, with no copy of `bytes`. A run of `.` is written only once a code
378/// point other than `.` follows it (a trailing run is stripped), and a
379/// value of nothing but `.` is `unnamed`.
380pub fn safe_into(bytes: &[u8], room: usize, out: &mut Vec<u8>) {
381    let start = out.len();
382    let lead = bytes.iter().take_while(|b| **b == b'.').count();
383    let rest = bytes.get(lead..).unwrap_or_default();
384    if rest.is_empty() {
385        out.extend(b"unnamed".iter().take(room));
386        return;
387    }
388    let mut dots = 0usize;
389    let put = |c: u8, out: &mut Vec<u8>| {
390        if out.len() - start < room {
391            out.push(c);
392            true
393        } else {
394            false
395        }
396    };
397    for chunk in rest.utf8_chunks() {
398        let valid = chunk.valid().chars().map(Some);
399        let invalid = chunk.invalid().iter().map(|_| None);
400        for c in valid.chain(invalid) {
401            let mapped = match c {
402                Some('.') => {
403                    dots += 1;
404                    continue;
405                }
406                Some(c) if c.is_ascii_alphanumeric() || matches!(c, '_' | '-') => c as u8,
407                _ => b'_',
408            };
409            // A run of `.` followed by another code point is kept.
410            for _ in 0..std::mem::take(&mut dots) {
411                if !put(b'.', out) {
412                    return;
413                }
414            }
415            if !put(mapped, out) {
416                return;
417            }
418        }
419    }
420}
421
422/// `safe()` (2.2): per code point, an invalid UTF-8 byte counting as one,
423/// every one outside `[A-Za-z0-9._-]` becomes `_`; then every leading and
424/// trailing `.` is stripped; an empty result is `unnamed`.
425#[must_use]
426pub fn safe(bytes: &[u8]) -> String {
427    let mut out = Vec::new();
428    safe_into(bytes, usize::MAX, &mut out);
429    String::from_utf8(out).unwrap_or_default()
430}
431
432/// The rules of 2.3 an attempt checks, in the table's order, which their
433/// order as values keeps.
434#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
435pub enum KeyRule {
436    /// `empty`.
437    Empty,
438    /// `not_utf8`.
439    NotUtf8,
440    /// `control_char`.
441    ControlChar,
442    /// `leading_slash`.
443    LeadingSlash,
444    /// `trailing_slash`.
445    TrailingSlash,
446    /// `empty_segment`.
447    EmptySegment,
448    /// `dot_segment`.
449    DotSegment,
450    /// `segment_too_long`.
451    SegmentTooLong,
452    /// `too_long`.
453    TooLong,
454    /// `reserved_prefix`.
455    ReservedPrefix,
456    /// `reserved_name`.
457    ReservedName,
458}
459
460impl KeyRule {
461    /// Its name in `unwritable_key(<rule>)`.
462    #[must_use]
463    pub fn name(self) -> &'static str {
464        match self {
465            Self::Empty => "empty",
466            Self::NotUtf8 => "not_utf8",
467            Self::ControlChar => "control_char",
468            Self::LeadingSlash => "leading_slash",
469            Self::TrailingSlash => "trailing_slash",
470            Self::EmptySegment => "empty_segment",
471            Self::DotSegment => "dot_segment",
472            Self::SegmentTooLong => "segment_too_long",
473            Self::TooLong => "too_long",
474            Self::ReservedPrefix => "reserved_prefix",
475            Self::ReservedName => "reserved_name",
476        }
477    }
478}
479
480/// The longest segment (`NAME_MAX`).
481pub const SEGMENT_MAX: usize = 255;
482/// The longest key.
483pub const KEY_MAX: usize = 1024;
484/// Where an expansion stops: one byte past [`KEY_MAX`], which is enough to
485/// know the key is `too_long`.
486pub const STOP: usize = KEY_MAX + 1;
487
488/// The key 2.3's `reserved_prefix` refuses, and every key under it.
489pub const RESERVED_PREFIX: &str = "_unityrs";
490/// What 2.3's `reserved_name` refuses a segment to start with.
491pub const RESERVED_NAME: &str = ".unityrs-tmp-";
492
493/// Whether 2.3's `dot_segment` refuses `segment`.
494fn dot_segment(segment: &str) -> bool {
495    segment == "." || segment == ".."
496}
497
498/// Which of 2.3's rules apply: every one to a key, all but
499/// `reserved_prefix` and `reserved_name` to an archive member path (4.7).
500#[derive(Clone, Copy, Debug, PartialEq, Eq)]
501enum Rules {
502    Key,
503    Member,
504}
505
506/// The key, or the first rule of 2.3 it breaks (but `prefix_conflict` and
507/// `archive_conflict`, which phase 6 decides).
508///
509/// Only the first [`STOP`] bytes are read. A key past [`KEY_MAX`] is
510/// `too_long` unless a rule before it in 2.3's order breaks within them;
511/// a rule that needs the key's end is not applied to it (`trailing_slash`,
512/// `dot_segment` of its last segment, and `not_utf8` of a code point the
513/// stop cuts), and a break past byte 1,025, a `control_char` among them, is
514/// not seen: the key is `too_long` (2.3). A segment's length is its bytes
515/// as read, a code point the stop cuts among them (review round 2's C4). So
516/// the answer is the same however much of the key was made.
517pub fn check(key: &[u8]) -> Result<&str, KeyRule> {
518    rules(key, Rules::Key)
519}
520
521/// An archive member path's check (4.7): [`check`] without
522/// `reserved_prefix` and `reserved_name`.
523pub fn check_member(path: &[u8]) -> Result<&str, KeyRule> {
524    rules(path, Rules::Member)
525}
526
527/// 2.3's two checks: the key as given, then after `prefix` (the sink's),
528/// the first rule either breaks naming the refusal. The two are joined in
529/// `scratch`, at most [`STOP`] bytes of them, so a `scratch` of that
530/// capacity allocates nothing.
531pub fn check_prefixed<'k>(
532    key: &'k [u8],
533    prefix: &str,
534    scratch: &mut Vec<u8>,
535) -> Result<&'k str, KeyRule> {
536    let checked = check(key)?;
537    if !prefix.is_empty() {
538        scratch.clear();
539        scratch.extend(prefix.as_bytes().iter().take(STOP));
540        let room = STOP.saturating_sub(scratch.len());
541        scratch.extend(key.iter().take(room));
542        check(scratch)?;
543    }
544    Ok(checked)
545}
546
547fn rules(key: &[u8], which: Rules) -> Result<&str, KeyRule> {
548    if key.is_empty() {
549        return Err(KeyRule::Empty);
550    }
551    let long = key.len() > KEY_MAX;
552    let read = key.get(..STOP).unwrap_or(key);
553    let text = match std::str::from_utf8(read) {
554        Ok(k) => k,
555        // A code point the stop cuts is past what is read.
556        Err(e) if long && e.error_len().is_none() => read
557            .get(..e.valid_up_to())
558            .and_then(|v| std::str::from_utf8(v).ok())
559            .ok_or(KeyRule::NotUtf8)?,
560        Err(_) => return Err(KeyRule::NotUtf8),
561    };
562    if text.chars().any(|c| c < ' ' || c == '\u{7f}') {
563        return Err(KeyRule::ControlChar);
564    }
565    if text.starts_with('/') {
566        return Err(KeyRule::LeadingSlash);
567    }
568    if !long && text.ends_with('/') {
569        return Err(KeyRule::TrailingSlash);
570    }
571    if text.contains("//") {
572        return Err(KeyRule::EmptySegment);
573    }
574    let segments = text.split('/');
575    let settled = if long {
576        segments.clone().count().saturating_sub(1)
577    } else {
578        usize::MAX
579    };
580    if segments.take(settled).any(dot_segment) {
581        return Err(KeyRule::DotSegment);
582    }
583    // Measured on the bytes read: a code point the stop cuts still counts.
584    if read.split(|b| *b == b'/').any(|s| s.len() > SEGMENT_MAX) {
585        return Err(KeyRule::SegmentTooLong);
586    }
587    if long {
588        return Err(KeyRule::TooLong);
589    }
590    if which == Rules::Key {
591        if text == RESERVED_PREFIX
592            || text
593                .strip_prefix(RESERVED_PREFIX)
594                .is_some_and(|r| r.starts_with('/'))
595        {
596            return Err(KeyRule::ReservedPrefix);
597        }
598        if text.split('/').any(|s| s.starts_with(RESERVED_NAME)) {
599            return Err(KeyRule::ReservedName);
600        }
601    }
602    Ok(text)
603}
604
605/// What one key costs its table beside the table's buckets: the string,
606/// at `heap_cost`.
607#[must_use]
608pub fn entry_cost(len: usize) -> u64 {
609    heap_cost(u64::try_from(len).unwrap_or(u64::MAX))
610}
611
612/// The attempt's key table (4.4 step 3): one for every kind's stage, the
613/// engine's to make and hand to each attempt, every key charged to `M_X`
614/// as it is taken (`docs/plans/batch.md` 2.6 step 5): its string, and the
615/// set's buckets before they grow ([`Set`]).
616#[derive(Debug)]
617pub struct KeyTable {
618    keys: Set<Box<str>>,
619    strings: Charge,
620}
621
622impl KeyTable {
623    /// An empty table charging `meter`.
624    #[must_use]
625    pub fn new(meter: &Arc<Meter>) -> Self {
626        Self {
627            keys: Set::new(meter),
628            strings: Charge::zero(meter),
629        }
630    }
631
632    /// Whether `key` is taken.
633    #[must_use]
634    pub fn contains(&self, key: &str) -> bool {
635        self.keys.contains(key)
636    }
637
638    /// Takes `key`: false when it was taken already; a refused charge (its
639    /// string's, or the set's growth) takes nothing.
640    pub fn take(&mut self, key: &str) -> Result<bool, Class> {
641        if self.keys.contains(key) {
642            return Ok(false);
643        }
644        self.keys.reserve_one()?;
645        self.strings
646            .grow(entry_cost(key.len()))
647            .map_err(|e| table::refused(&e))?;
648        self.keys.insert(Box::from(key))
649    }
650
651    /// How many keys it holds.
652    #[must_use]
653    pub fn len(&self) -> usize {
654        self.keys.len()
655    }
656
657    /// Whether it holds none.
658    #[must_use]
659    pub fn is_empty(&self) -> bool {
660        self.keys.is_empty()
661    }
662}
663
664mod literal;
665
666pub use literal::{TemplateRefusal, check_member_template, check_template};
667
668#[cfg(test)]
669mod tests;