cadmpeg_step/
parse.rs

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

cadmpeg_step/
parse.rs
