cadmpeg_codec_step/
parse.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Generic Part 21 record-graph parser.
3//!
4//! The parser accepts only source deviations whose value remains unambiguous:
5//! the deviation must be recoverable without guessing, observed in a real
6//! producer, represented by its own diagnostic kind, and rejectable by strict
7//! decode policy. Ambiguous records and duplicate names remain parse errors.
8
9use std::collections::{BTreeMap, HashMap};
10use std::ops::Range;
11use std::sync::OnceLock;
12
13use crate::lex::{lex, BinaryValue, LexError, Token, TokenKind};
14
15/// One parsed Part 21 parameter value.
16#[derive(Debug, Clone, PartialEq)]
17pub enum Value {
18    /// Reference to a DATA entity instance.
19    Reference(u64),
20    /// Signed integer value.
21    Integer(i64),
22    /// Real value.
23    Real(f64),
24    /// Enumeration or logical name without delimiter dots.
25    Enumeration(String),
26    /// Raw string-token bytes before Part 21 escape decoding.
27    String(Vec<u8>),
28    /// Decoded binary literal and final-byte significant-bit boundary.
29    Binary(BinaryValue),
30    /// Edition-3 resource value.
31    Resource(String),
32    /// Omitted optional value `$`.
33    Omitted,
34    /// Derived value `*`.
35    Derived,
36    /// Ordered aggregate values.
37    List(Vec<Value>),
38    /// Type name and its single wrapped parameter.
39    Typed(String, Box<Value>),
40}
41
42/// One simple entity leaf within an entity instance.
43#[derive(Debug, Clone, PartialEq)]
44pub struct PartialRecord {
45    /// Uppercase entity name.
46    pub name: String,
47    /// Explicit external-mapping parameters.
48    pub parameters: Vec<Value>,
49}
50
51/// One DATA entity instance with its exact source extent.
52#[derive(Debug, Clone, PartialEq)]
53pub struct RawRecord {
54    /// Numeric entity-instance name without `#`.
55    pub id: u64,
56    /// One leaf for a simple instance or all leaves for a complex instance.
57    pub partials: Vec<PartialRecord>,
58    /// Half-open byte range from instance name through semicolon.
59    pub span: Range<usize>,
60}
61
62/// One entity-like record in the HEADER section.
63#[derive(Debug, Clone, PartialEq)]
64pub struct HeaderRecord {
65    /// Header record name.
66    pub name: String,
67    /// Header record parameters.
68    pub parameters: Vec<Value>,
69}
70
71/// One DATA section and its ordered population.
72#[derive(Debug, Clone, PartialEq)]
73pub struct DataSection {
74    /// Edition-3 DATA section parameters.
75    pub parameters: Vec<Value>,
76    /// Entity-instance names in source order.
77    pub records: Vec<u64>,
78}
79
80/// One edition-3 ANCHOR binding.
81#[derive(Debug, Clone, PartialEq)]
82pub struct AnchorEntry {
83    /// Local resource name.
84    pub name: String,
85    /// Value bound to the resource name.
86    pub value: Value,
87}
88
89/// One edition-3 external REFERENCE binding.
90#[derive(Debug, Clone, PartialEq, Eq)]
91pub struct ReferenceEntry {
92    /// Local resource name.
93    pub name: String,
94    /// External resource URI.
95    pub uri: String,
96}
97
98/// Parsed exchange structure and global DATA record graph.
99#[derive(Debug, Clone, PartialEq)]
100pub struct Exchange {
101    /// HEADER records in source order.
102    pub header: Vec<HeaderRecord>,
103    /// ANCHOR bindings in source order.
104    pub anchors: Vec<AnchorEntry>,
105    /// REFERENCE bindings in source order.
106    pub references: Vec<ReferenceEntry>,
107    /// DATA sections in source order.
108    pub data: Vec<DataSection>,
109    /// Complete SIGNATURE section byte range when present.
110    pub signature: Option<Range<usize>>,
111    /// DATA instances indexed across every DATA section.
112    pub records: BTreeMap<u64, RawRecord>,
113    entity_ids: EntityIndex,
114}
115
116#[derive(Debug, Default)]
117struct EntityIndex(OnceLock<HashMap<String, Vec<u64>>>);
118
119impl Clone for EntityIndex {
120    fn clone(&self) -> Self {
121        Self::default()
122    }
123}
124
125impl PartialEq for EntityIndex {
126    fn eq(&self, _other: &Self) -> bool {
127        true
128    }
129}
130
131impl Exchange {
132    fn entity_ids(&self) -> &HashMap<String, Vec<u64>> {
133        self.entity_ids.0.get_or_init(|| {
134            let mut entity_ids = HashMap::<String, Vec<u64>>::new();
135            for (&id, record) in &self.records {
136                for partial in &record.partials {
137                    if let Some(ids) = entity_ids.get_mut(partial.name.as_str()) {
138                        ids.push(id);
139                    } else {
140                        entity_ids.insert(partial.name.clone(), vec![id]);
141                    }
142                }
143            }
144            entity_ids
145        })
146    }
147
148    pub(crate) fn entities(&self, name: &str) -> impl Iterator<Item = (u64, &RawRecord)> {
149        self.entity_ids()
150            .get(name)
151            .into_iter()
152            .flatten()
153            .filter_map(|id| self.records.get(id).map(|record| (*id, record)))
154    }
155
156    pub(crate) fn entities_any<'a>(
157        &'a self,
158        names: &[&str],
159    ) -> impl Iterator<Item = (u64, &'a RawRecord)> {
160        let mut ids = names
161            .iter()
162            .filter_map(|name| self.entity_ids().get(*name))
163            .flatten()
164            .copied()
165            .collect::<Vec<_>>();
166        ids.sort_unstable();
167        ids.dedup();
168        ids.into_iter()
169            .filter_map(|id| self.records.get(&id).map(|record| (id, record)))
170    }
171}
172
173/// Structural or lexical exchange failure.
174#[derive(Debug, thiserror::Error)]
175pub enum ParseError {
176    /// Tokenization failed.
177    #[error(transparent)]
178    Lex(#[from] LexError),
179    /// Token sequence violates the exchange grammar.
180    #[error("{message} at byte {offset}")]
181    Syntax {
182        /// Byte offset of the unexpected token or end of input.
183        offset: usize,
184        /// Violated grammar invariant.
185        message: String,
186    },
187}
188
189/// A recoverable deviation from canonical Part 21 source syntax.
190#[derive(Debug, Clone, Copy, PartialEq, Eq)]
191#[non_exhaustive]
192pub enum ParseDiagnosticKind {
193    /// Complex-entity partials are not in their canonical alphabetical order.
194    ComplexPartialsNotAlphabetical,
195}
196
197/// One attributable parser diagnostic that does not prevent recovery.
198#[derive(Debug, Clone, PartialEq, Eq)]
199pub struct ParseDiagnostic {
200    /// Byte offset of the containing complex entity instance.
201    pub offset: usize,
202    /// Stable diagnostic classification.
203    pub kind: ParseDiagnosticKind,
204    /// Human-readable explanation, including the observed and canonical order.
205    pub message: String,
206}
207
208/// Parse one complete clear-text exchange structure and resolve DATA references.
209pub fn parse(input: &[u8]) -> Result<(Exchange, Vec<ParseDiagnostic>), ParseError> {
210    Parser {
211        tokens: lex(input)?,
212        at: 0,
213        depth: 0,
214        diagnostics: Vec::new(),
215    }
216    .exchange()
217}
218
219struct Parser {
220    tokens: Vec<Token>,
221    at: usize,
222    depth: usize,
223    diagnostics: Vec<ParseDiagnostic>,
224}
225
226impl Parser {
227    fn exchange(mut self) -> Result<(Exchange, Vec<ParseDiagnostic>), ParseError> {
228        self.name("ISO-10303-21")?;
229        self.punct(&TokenKind::Semicolon)?;
230        self.name("HEADER")?;
231        self.punct(&TokenKind::Semicolon)?;
232        let mut header = Vec::new();
233        while !self.peek_name("ENDSEC") {
234            let name = self.take_name()?;
235            let parameters = self.parameters()?;
236            self.punct(&TokenKind::Semicolon)?;
237            header.push(HeaderRecord { name, parameters });
238        }
239        self.name("ENDSEC")?;
240        self.punct(&TokenKind::Semicolon)?;
241        let mut anchors = Vec::new();
242        if self.peek_name("ANCHOR") {
243            self.at += 1;
244            self.punct(&TokenKind::Semicolon)?;
245            while !self.peek_name("ENDSEC") {
246                let TokenKind::Resource(name) = self.next_kind()? else {
247                    return self.err("expected anchor name");
248                };
249                self.punct(&TokenKind::Equals)?;
250                let value = self.value()?;
251                self.punct(&TokenKind::Semicolon)?;
252                anchors.push(AnchorEntry { name, value });
253            }
254            self.at += 1;
255            self.punct(&TokenKind::Semicolon)?;
256        }
257        let mut reference_entries = Vec::new();
258        if self.peek_name("REFERENCE") {
259            self.at += 1;
260            self.punct(&TokenKind::Semicolon)?;
261            while !self.peek_name("ENDSEC") {
262                let TokenKind::Resource(name) = self.next_kind()? else {
263                    return self.err("expected reference name");
264                };
265                self.punct(&TokenKind::Equals)?;
266                let TokenKind::Resource(uri) = self.next_kind()? else {
267                    return self.err("expected reference URI");
268                };
269                self.punct(&TokenKind::Semicolon)?;
270                reference_entries.push(ReferenceEntry { name, uri });
271            }
272            self.at += 1;
273            self.punct(&TokenKind::Semicolon)?;
274        }
275        let mut data = Vec::new();
276        let mut records = BTreeMap::new();
277        while self.peek_name("DATA") {
278            self.at += 1;
279            let parameters = if self.peek(&TokenKind::LParen) {
280                self.parameters()?
281            } else {
282                Vec::new()
283            };
284            self.punct(&TokenKind::Semicolon)?;
285            let mut ids = Vec::new();
286            while !self.peek_name("ENDSEC") {
287                let record = self.record()?;
288                let id = record.id;
289                if records.insert(id, record).is_some() {
290                    return self.err("duplicate instance name");
291                }
292                ids.push(id);
293            }
294            self.name("ENDSEC")?;
295            self.punct(&TokenKind::Semicolon)?;
296            data.push(DataSection {
297                parameters,
298                records: ids,
299            });
300        }
301        let signature = if self.peek_name("SIGNATURE") {
302            let start = self.current_offset();
303            self.at += 1;
304            self.punct(&TokenKind::Semicolon)?;
305            while !self.peek_name("ENDSEC") {
306                self.at += 1;
307                if self.at >= self.tokens.len() {
308                    return self.err("unterminated SIGNATURE section");
309                }
310            }
311            self.at += 1;
312            self.punct(&TokenKind::Semicolon)?;
313            Some(start..self.previous_end())
314        } else {
315            None
316        };
317        self.name("END-ISO-10303-21")?;
318        self.punct(&TokenKind::Semicolon)?;
319        if self.at != self.tokens.len() {
320            return self.err("tokens after exchange terminator");
321        }
322        let anchor_bindings = anchors
323            .iter()
324            .map(|anchor| (anchor.name.clone(), anchor.value.clone()))
325            .collect::<BTreeMap<_, _>>();
326        if anchor_bindings.len() != anchors.len() {
327            return self.err("duplicate anchor name");
328        }
329        let mut resolver = AnchorResolver::new(&anchor_bindings);
330        for anchor in &mut anchors {
331            anchor.value = resolver
332                .resolve_root(&anchor.value)
333                .map_err(|message| ParseError::Syntax { offset: 0, message })?;
334        }
335        for record in records.values_mut() {
336            for partial in &mut record.partials {
337                for value in &mut partial.parameters {
338                    *value =
339                        resolver
340                            .resolve_root(value)
341                            .map_err(|message| ParseError::Syntax {
342                                offset: record.span.start,
343                                message,
344                            })?;
345                }
346            }
347        }
348        for anchor in &anchors {
349            let mut refs = Vec::new();
350            references(&anchor.value, &mut refs);
351            if refs.into_iter().any(|id| !records.contains_key(&id)) {
352                return self.err("unresolved instance reference in anchor binding");
353            }
354        }
355        for record in records.values() {
356            let mut refs = Vec::new();
357            for partial in &record.partials {
358                for value in &partial.parameters {
359                    references(value, &mut refs);
360                }
361            }
362            if refs.into_iter().any(|id| !records.contains_key(&id)) {
363                return Self::err_at(record.span.start, "unresolved instance reference");
364            }
365        }
366        Ok((
367            Exchange {
368                header,
369                anchors,
370                references: reference_entries,
371                data,
372                signature,
373                records,
374                entity_ids: EntityIndex::default(),
375            },
376            self.diagnostics,
377        ))
378    }
379
380    fn record(&mut self) -> Result<RawRecord, ParseError> {
381        let start = self.current_offset();
382        let TokenKind::Instance(id) = self.next_kind()? else {
383            return self.err("expected instance name");
384        };
385        self.punct(&TokenKind::Equals)?;
386        let partials = if self.peek(&TokenKind::LParen) {
387            self.at += 1;
388            let mut parts = Vec::new();
389            while !self.peek(&TokenKind::RParen) {
390                parts.push(self.partial()?);
391            }
392            self.at += 1;
393            let mut canonical_names = parts
394                .iter()
395                .map(|part| part.name.clone())
396                .collect::<Vec<_>>();
397            canonical_names.sort_unstable();
398            if canonical_names
399                .windows(2)
400                .any(|window| window[0] == window[1])
401            {
402                return Self::err_at(start, "duplicate complex partial name");
403            }
404            if !parts
405                .windows(2)
406                .all(|window| window[0].name < window[1].name)
407            {
408                let observed = parts
409                    .iter()
410                    .map(|part| part.name.as_str())
411                    .collect::<Vec<_>>()
412                    .join(", ");
413                self.diagnostics.push(ParseDiagnostic {
414                    offset: start,
415                    kind: ParseDiagnosticKind::ComplexPartialsNotAlphabetical,
416                    message: format!(
417                        "complex partial records are not alphabetical: observed ({observed}), expected ({})",
418                        canonical_names.join(", ")
419                    ),
420                });
421            }
422            parts
423        } else {
424            vec![self.partial()?]
425        };
426        self.punct(&TokenKind::Semicolon)?;
427        Ok(RawRecord {
428            id,
429            partials,
430            span: start..self.previous_end(),
431        })
432    }
433
434    fn partial(&mut self) -> Result<PartialRecord, ParseError> {
435        let name = self.take_name()?;
436        let parameters = self.parameters()?;
437        Ok(PartialRecord { name, parameters })
438    }
439
440    fn parameters(&mut self) -> Result<Vec<Value>, ParseError> {
441        const MAX_VALUE_DEPTH: usize = 256;
442        if self.depth >= MAX_VALUE_DEPTH {
443            return self.err("parameter nesting exceeds 256 levels");
444        }
445        self.depth += 1;
446        let result = self.parameters_inner();
447        self.depth -= 1;
448        result
449    }
450
451    fn parameters_inner(&mut self) -> Result<Vec<Value>, ParseError> {
452        self.punct(&TokenKind::LParen)?;
453        let mut values = Vec::new();
454        if self.peek(&TokenKind::RParen) {
455            self.at += 1;
456            return Ok(values);
457        }
458        loop {
459            values.push(self.value()?);
460            if self.peek(&TokenKind::Comma) {
461                self.at += 1;
462            } else {
463                break;
464            }
465        }
466        self.punct(&TokenKind::RParen)?;
467        Ok(values)
468    }
469
470    fn value(&mut self) -> Result<Value, ParseError> {
471        match self.next_kind()? {
472            TokenKind::Instance(v) => Ok(Value::Reference(v)),
473            TokenKind::Integer(v) => Ok(Value::Integer(v)),
474            TokenKind::Real(v) => Ok(Value::Real(v)),
475            TokenKind::Enumeration(v) => Ok(Value::Enumeration(v)),
476            TokenKind::String(v) => Ok(Value::String(v)),
477            TokenKind::Binary(v) => Ok(Value::Binary(v)),
478            TokenKind::Resource(v) => Ok(Value::Resource(v)),
479            TokenKind::Omitted => Ok(Value::Omitted),
480            TokenKind::Derived => Ok(Value::Derived),
481            TokenKind::LParen => {
482                self.at -= 1;
483                Ok(Value::List(self.parameters()?))
484            }
485            TokenKind::Name(name) => {
486                let parameters = self.parameters()?;
487                if parameters.len() != 1 {
488                    return self.err("typed parameter requires one value");
489                }
490                Ok(Value::Typed(
491                    name,
492                    Box::new(
493                        parameters
494                            .into_iter()
495                            .next()
496                            .expect("parameter count was checked"),
497                    ),
498                ))
499            }
500            _ => self.err("expected parameter value"),
501        }
502    }
503
504    fn take_name(&mut self) -> Result<String, ParseError> {
505        match self.next_kind()? {
506            TokenKind::Name(name) => Ok(name),
507            _ => self.err("expected name"),
508        }
509    }
510    fn name(&mut self, expected: &str) -> Result<(), ParseError> {
511        let actual = self.take_name()?;
512        if actual == expected {
513            Ok(())
514        } else {
515            self.err(&format!("expected {expected}, found {actual}"))
516        }
517    }
518    fn punct(&mut self, expected: &TokenKind) -> Result<(), ParseError> {
519        let actual = self.next_kind()?;
520        if std::mem::discriminant(&actual) == std::mem::discriminant(expected) {
521            Ok(())
522        } else {
523            self.err("unexpected token")
524        }
525    }
526    fn peek(&self, expected: &TokenKind) -> bool {
527        self.tokens
528            .get(self.at)
529            .is_some_and(|t| std::mem::discriminant(&t.kind) == std::mem::discriminant(expected))
530    }
531    fn peek_name(&self, expected: &str) -> bool {
532        matches!(self.tokens.get(self.at).map(|t| &t.kind), Some(TokenKind::Name(name)) if name == expected)
533    }
534    fn next_kind(&mut self) -> Result<TokenKind, ParseError> {
535        let Some(token) = self.tokens.get(self.at) else {
536            return self.err("unexpected end of input");
537        };
538        self.at += 1;
539        Ok(token.kind.clone())
540    }
541    fn current_offset(&self) -> usize {
542        self.tokens
543            .get(self.at)
544            .map_or_else(|| self.previous_end(), |t| t.span.start)
545    }
546    fn previous_end(&self) -> usize {
547        self.at
548            .checked_sub(1)
549            .and_then(|i| self.tokens.get(i))
550            .map_or(0, |t| t.span.end)
551    }
552    fn err<T>(&self, message: &str) -> Result<T, ParseError> {
553        Self::err_at(self.current_offset(), message)
554    }
555    fn err_at<T>(offset: usize, message: &str) -> Result<T, ParseError> {
556        Err(ParseError::Syntax {
557            offset,
558            message: message.into(),
559        })
560    }
561}
562
563struct AnchorResolver<'a> {
564    anchors: &'a BTreeMap<String, Value>,
565    memo: BTreeMap<String, (Value, usize)>,
566    remaining_nodes: usize,
567}
568
569impl<'a> AnchorResolver<'a> {
570    const MAX_EXPANDED_NODES: usize = 1_000_000;
571    const MAX_REFERENCE_DEPTH: usize = 256;
572
573    fn new(anchors: &'a BTreeMap<String, Value>) -> Self {
574        Self {
575            anchors,
576            memo: BTreeMap::new(),
577            remaining_nodes: Self::MAX_EXPANDED_NODES,
578        }
579    }
580
581    fn resolve_root(&mut self, value: &Value) -> Result<Value, String> {
582        let (value, _, expanded_nodes) =
583            self.resolve(value, &mut Vec::new(), self.remaining_nodes, 0)?;
584        self.remaining_nodes = self
585            .remaining_nodes
586            .checked_sub(expanded_nodes)
587            .ok_or_else(|| "aggregate expanded anchor graph exceeds 1000000 nodes".to_string())?;
588        Ok(value)
589    }
590
591    fn resolve(
592        &mut self,
593        value: &Value,
594        stack: &mut Vec<String>,
595        budget: usize,
596        depth: usize,
597    ) -> Result<(Value, usize, usize), String> {
598        if depth >= Self::MAX_REFERENCE_DEPTH {
599            return Err("expanded anchor graph exceeds its node or depth limit".into());
600        }
601        match value {
602            Value::Resource(name) if self.anchors.contains_key(name) => {
603                if let Some((value, nodes)) = self.memo.get(name) {
604                    if *nodes > budget {
605                        return Err("expanded anchor value exceeds 1000000 nodes".into());
606                    }
607                    return Ok((value.clone(), *nodes, *nodes));
608                }
609                if stack.contains(name) {
610                    return Err(format!("cyclic anchor binding <{name}>"));
611                }
612                stack.push(name.clone());
613                let source = self.anchors[name].clone();
614                let resolved = self.resolve(&source, stack, budget, depth + 1);
615                stack.pop();
616                let (value, nodes, _) = resolved?;
617                if nodes > budget {
618                    return Err("expanded anchor value exceeds 1000000 nodes".into());
619                }
620                self.memo.insert(name.clone(), (value.clone(), nodes));
621                Ok((value, nodes, nodes))
622            }
623            Value::List(values) => {
624                let mut nodes = 1usize;
625                let mut expanded_nodes = 0usize;
626                let mut resolved = Vec::with_capacity(values.len());
627                for value in values {
628                    let remaining = budget
629                        .checked_sub(expanded_nodes)
630                        .ok_or_else(|| "expanded anchor value exceeds 1000000 nodes".to_string())?;
631                    let (value, child_nodes, child_expanded_nodes) =
632                        self.resolve(value, stack, remaining, depth + 1)?;
633                    nodes = nodes
634                        .checked_add(child_nodes)
635                        .ok_or_else(|| "expanded anchor value exceeds 1000000 nodes".to_string())?;
636                    expanded_nodes = expanded_nodes
637                        .checked_add(child_expanded_nodes)
638                        .ok_or_else(|| "expanded anchor value exceeds 1000000 nodes".to_string())?;
639                    resolved.push(value);
640                }
641                Ok((Value::List(resolved), nodes, expanded_nodes))
642            }
643            Value::Typed(name, value) => {
644                let (value, nodes, expanded_nodes) =
645                    self.resolve(value, stack, budget, depth + 1)?;
646                Ok((
647                    Value::Typed(name.clone(), Box::new(value)),
648                    nodes + 1,
649                    expanded_nodes,
650                ))
651            }
652            value => Ok((value.clone(), 1, 0)),
653        }
654    }
655}
656
657fn references(value: &Value, out: &mut Vec<u64>) {
658    let mut pending = vec![value];
659    while let Some(value) = pending.pop() {
660        match value {
661            Value::Reference(id) => out.push(*id),
662            Value::List(values) => pending.extend(values.iter().rev()),
663            Value::Typed(_, value) => pending.push(value),
664            _ => {}
665        }
666    }
667}
668
669#[cfg(test)]
670mod tests {
671    use super::{parse, AnchorResolver, BTreeMap, Value};
672
673    #[test]
674    fn entity_index_is_not_part_of_exchange_equality() {
675        let source = b"ISO-10303-21;HEADER;ENDSEC;DATA;#1=POINT();ENDSEC;END-ISO-10303-21;";
676        let (indexed, _) = parse(source).expect("required invariant");
677        let (untouched, _) = parse(source).expect("required invariant");
678        assert_eq!(indexed.entities("POINT").count(), 1);
679        assert_eq!(indexed, untouched);
680    }
681
682    #[test]
683    fn anchor_budget_charges_only_resource_expansion() {
684        let anchors = BTreeMap::new();
685        let mut resolver = AnchorResolver::new(&anchors);
686        resolver.remaining_nodes = 0;
687
688        let ordinary = Value::List((0..1024).map(Value::Integer).collect());
689        assert_eq!(resolver.resolve_root(&ordinary), Ok(ordinary));
690        assert_eq!(resolver.remaining_nodes, 0);
691    }
692
693    #[test]
694    fn anchor_budget_still_bounds_resource_materialization() {
695        let anchors = BTreeMap::from([(
696            "a".to_string(),
697            Value::List(vec![Value::Integer(1), Value::Integer(2)]),
698        )]);
699        let mut resolver = AnchorResolver::new(&anchors);
700        resolver.remaining_nodes = 2;
701
702        assert!(resolver
703            .resolve_root(&Value::Resource("a".to_string()))
704            .is_err());
705    }
706}
cadmpeg_codec_step/parse.rs

cadmpeg_codec_step/
parse.rs
