yaml_rt_core/
semantic.rs

1use crate::{
2    CollectionStyle, Diagnostic, DiagnosticKind, NodeId, Span, YamlError, YamlEventKind,
3    YamlScalarStyle,
4};
5
6const NO_SEMANTIC_NODE: u32 = u32::MAX;
7const NO_PROPERTIES: u32 = u32::MAX;
8const EXPLICIT_START: u8 = 1 << 0;
9const EXPLICIT_END: u8 = 1 << 1;
10
11/// Semantic interpretation attached to a lossless CST node.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum SemanticKind {
14    /// YAML document.
15    Document,
16    /// YAML mapping with its presentation style.
17    Mapping {
18        /// Block or flow spelling.
19        style: CollectionStyle,
20    },
21    /// YAML sequence with its presentation style.
22    Sequence {
23        /// Block or flow spelling.
24        style: CollectionStyle,
25    },
26    /// Scalar with presentation style.
27    Scalar {
28        /// Scalar spelling style.
29        style: YamlScalarStyle,
30    },
31    /// Alias reference.
32    Alias,
33}
34
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub(crate) struct SemanticNode {
37    pub(crate) kind: SemanticKind,
38    flags: u8,
39    padding: u8,
40    pub(crate) span_start: u32,
41    pub(crate) end_offset: u32,
42    property: u32,
43}
44
45#[derive(Debug, Clone, Copy, PartialEq, Eq)]
46pub(crate) struct SemanticProperties {
47    pub(crate) tag: Option<Span>,
48    pub(crate) anchor: Option<Span>,
49    pub(crate) alias: Option<Span>,
50    pub(crate) content_indent: Option<u32>,
51}
52
53impl SemanticProperties {
54    pub(crate) const NONE: Self = Self {
55        tag: None,
56        anchor: None,
57        alias: None,
58        content_indent: None,
59    };
60
61    fn is_empty(self) -> bool {
62        self == Self::NONE
63    }
64}
65
66#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67struct PropertyRecord {
68    properties: SemanticProperties,
69    document: NodeId,
70}
71
72#[derive(Debug, Clone, Copy, PartialEq, Eq)]
73struct AnchorBinding {
74    name: Span,
75    target: NodeId,
76    document: NodeId,
77}
78
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
80struct TagDirectiveBinding {
81    handle: Span,
82    prefix: Span,
83    document: NodeId,
84}
85
86/// Compact semantic side arena indexed through CST `NodeId`s.
87#[derive(Debug, Clone, PartialEq, Eq)]
88pub(crate) struct SemanticStore {
89    slots: Vec<u32>,
90    nodes: Vec<SemanticNode>,
91    properties: Vec<PropertyRecord>,
92    anchors: Vec<AnchorBinding>,
93    tag_directives: Vec<TagDirectiveBinding>,
94    pub(crate) documents: Vec<NodeId>,
95}
96
97impl SemanticStore {
98    fn insert(&mut self, cst: NodeId, node: SemanticNode) {
99        if self.slots.len() <= cst.as_usize() {
100            self.slots
101                .resize(cst.as_usize().saturating_add(1), NO_SEMANTIC_NODE);
102        }
103        let index = u32::try_from(self.nodes.len()).expect("semantic arena exceeds u32 capacity");
104        self.slots[cst.as_usize()] = index;
105        self.nodes.push(node);
106    }
107
108    fn close(&mut self, cst: NodeId, span: Span, explicit: Option<bool>) {
109        let index = self.slots[cst.as_usize()] as usize;
110        self.nodes[index].end_offset = span.end;
111        if let Some(explicit) = explicit {
112            self.nodes[index].set_flag(EXPLICIT_END, explicit);
113        }
114    }
115
116    pub(crate) fn get(&self, cst: NodeId) -> Option<&SemanticNode> {
117        let index = *self.slots.get(cst.as_usize())?;
118        (index != NO_SEMANTIC_NODE).then(|| &self.nodes[index as usize])
119    }
120
121    pub(crate) fn properties(&self, cst: NodeId) -> Option<SemanticProperties> {
122        let node = self.get(cst)?;
123        (node.property != NO_PROPERTIES).then(|| self.properties[node.property as usize].properties)
124    }
125
126    pub(crate) fn clear_tag(&mut self, cst: NodeId) {
127        let Some(property) = self.get(cst).map(|node| node.property) else {
128            return;
129        };
130        if property != NO_PROPERTIES {
131            self.properties[property as usize].properties.tag = None;
132        }
133    }
134
135    pub(crate) fn property_document(&self, cst: NodeId) -> Option<NodeId> {
136        let node = self.get(cst)?;
137        (node.property != NO_PROPERTIES).then(|| self.properties[node.property as usize].document)
138    }
139
140    pub(crate) fn anchors(&self) -> impl DoubleEndedIterator<Item = (Span, NodeId, NodeId)> + '_ {
141        self.anchors
142            .iter()
143            .map(|binding| (binding.name, binding.target, binding.document))
144    }
145
146    pub(crate) fn tag_directives(
147        &self,
148        document: NodeId,
149    ) -> impl Iterator<Item = (Span, Span)> + '_ {
150        self.tag_directives
151            .iter()
152            .filter(move |binding| binding.document == document)
153            .map(|binding| (binding.handle, binding.prefix))
154    }
155}
156
157pub(crate) struct SemanticBuilder {
158    store: SemanticStore,
159    open: Vec<OpenNode>,
160    error: Option<YamlError>,
161}
162
163impl SemanticBuilder {
164    pub(crate) fn with_capacity(cst_capacity: usize, semantic_capacity: usize) -> Self {
165        Self {
166            store: SemanticStore {
167                slots: Vec::with_capacity(cst_capacity),
168                nodes: Vec::with_capacity(semantic_capacity),
169                properties: Vec::new(),
170                anchors: Vec::new(),
171                tag_directives: Vec::new(),
172                documents: Vec::with_capacity(1),
173            },
174            open: Vec::with_capacity(8),
175            error: None,
176        }
177    }
178
179    pub(crate) fn push(
180        &mut self,
181        kind: YamlEventKind,
182        span: Span,
183        cst: Option<NodeId>,
184        properties: SemanticProperties,
185    ) {
186        if self.error.is_some() {
187            return;
188        }
189        let result = self.try_push(&kind, span, cst, properties);
190        drop(kind);
191        if let Err(error) = result {
192            self.error = Some(error);
193        }
194    }
195
196    pub(crate) fn register_cst_node(&mut self) {
197        self.store.slots.push(NO_SEMANTIC_NODE);
198    }
199
200    pub(crate) fn push_property_free_plain_scalar(&mut self, cst: NodeId, span: Span) {
201        if self.error.is_some() {
202            return;
203        }
204        self.store.insert(
205            cst,
206            SemanticNode::new(
207                SemanticKind::Scalar {
208                    style: YamlScalarStyle::Plain,
209                },
210                span,
211                false,
212                NO_PROPERTIES,
213            ),
214        );
215        if let Err(error) = self.attach_child(cst, span) {
216            self.error = Some(error);
217        }
218    }
219
220    pub(crate) fn push_collection_start(
221        &mut self,
222        cst: NodeId,
223        span: Span,
224        style: CollectionStyle,
225        mapping: bool,
226        properties: SemanticProperties,
227    ) {
228        if self.error.is_some() {
229            return;
230        }
231        let property = self.insert_properties(cst, properties);
232        let kind = if mapping {
233            SemanticKind::Mapping { style }
234        } else {
235            SemanticKind::Sequence { style }
236        };
237        self.store
238            .insert(cst, SemanticNode::new(kind, span, false, property));
239        if mapping {
240            self.open.push(OpenNode::Mapping {
241                cst,
242                waiting_for_value: false,
243            });
244        } else {
245            self.open.push(OpenNode::Sequence { cst });
246        }
247    }
248
249    pub(crate) fn push_collection_end(&mut self, span: Span, mapping: bool) {
250        if self.error.is_some() {
251            return;
252        }
253        let result = if mapping {
254            let Some(OpenNode::Mapping {
255                cst,
256                waiting_for_value,
257            }) = self.open.pop()
258            else {
259                self.error = Some(structure_error("mismatched mapping end event", span));
260                return;
261            };
262            if waiting_for_value {
263                self.error = Some(structure_error(
264                    "mapping entry does not contain a value",
265                    span,
266                ));
267                return;
268            }
269            self.store.close(cst, span, None);
270            self.attach_child(cst, span)
271        } else {
272            let Some(OpenNode::Sequence { cst }) = self.open.pop() else {
273                self.error = Some(structure_error("mismatched sequence end event", span));
274                return;
275            };
276            self.store.close(cst, span, None);
277            self.attach_child(cst, span)
278        };
279        if let Err(error) = result {
280            self.error = Some(error);
281        }
282    }
283
284    #[expect(
285        clippy::too_many_lines,
286        reason = "one exhaustive match maintains semantic transitions for every event kind"
287    )]
288    fn try_push(
289        &mut self,
290        kind: &YamlEventKind,
291        span: Span,
292        cst: Option<NodeId>,
293        properties: SemanticProperties,
294    ) -> Result<(), YamlError> {
295        match kind {
296            YamlEventKind::StreamStart | YamlEventKind::StreamEnd => Ok(()),
297            YamlEventKind::DocumentStart { explicit } => {
298                let cst = required_cst(cst, span)?;
299                for directive in self
300                    .store
301                    .tag_directives
302                    .iter_mut()
303                    .rev()
304                    .take_while(|directive| directive.document == NodeId(u32::MAX))
305                {
306                    directive.document = cst;
307                }
308                self.store.documents.push(cst);
309                let property = self.insert_properties(cst, properties);
310                self.store.insert(
311                    cst,
312                    SemanticNode::new(SemanticKind::Document, span, *explicit, property),
313                );
314                self.open.push(OpenNode::Document { cst, children: 0 });
315                Ok(())
316            }
317            YamlEventKind::MappingStart { style, .. } => {
318                let cst = required_cst(cst, span)?;
319                let property = self.insert_properties(cst, properties);
320                self.store.insert(
321                    cst,
322                    SemanticNode::new(
323                        SemanticKind::Mapping { style: *style },
324                        span,
325                        false,
326                        property,
327                    ),
328                );
329                self.open.push(OpenNode::Mapping {
330                    cst,
331                    waiting_for_value: false,
332                });
333                Ok(())
334            }
335            YamlEventKind::SequenceStart { style, .. } => {
336                let cst = required_cst(cst, span)?;
337                let property = self.insert_properties(cst, properties);
338                self.store.insert(
339                    cst,
340                    SemanticNode::new(
341                        SemanticKind::Sequence { style: *style },
342                        span,
343                        false,
344                        property,
345                    ),
346                );
347                self.open.push(OpenNode::Sequence { cst });
348                Ok(())
349            }
350            YamlEventKind::Scalar { style, .. } => {
351                let cst = required_cst(cst, span)?;
352                let property = self.insert_properties(cst, properties);
353                self.store.insert(
354                    cst,
355                    SemanticNode::new(
356                        SemanticKind::Scalar { style: *style },
357                        span,
358                        false,
359                        property,
360                    ),
361                );
362                self.attach_child(cst, span)
363            }
364            YamlEventKind::Alias { .. } => {
365                let cst = required_cst(cst, span)?;
366                let property = self.insert_properties(cst, properties);
367                self.store.insert(
368                    cst,
369                    SemanticNode::new(SemanticKind::Alias, span, false, property),
370                );
371                self.attach_child(cst, span)
372            }
373            YamlEventKind::MappingEnd => {
374                let Some(OpenNode::Mapping {
375                    cst,
376                    waiting_for_value,
377                }) = self.open.pop()
378                else {
379                    return Err(structure_error("mismatched mapping end event", span));
380                };
381                if waiting_for_value {
382                    return Err(structure_error(
383                        "mapping entry does not contain a value",
384                        span,
385                    ));
386                }
387                self.store.close(cst, span, None);
388                self.attach_child(cst, span)
389            }
390            YamlEventKind::SequenceEnd => {
391                let Some(OpenNode::Sequence { cst }) = self.open.pop() else {
392                    return Err(structure_error("mismatched sequence end event", span));
393                };
394                self.store.close(cst, span, None);
395                self.attach_child(cst, span)
396            }
397            YamlEventKind::DocumentEnd { explicit } => {
398                let Some(OpenNode::Document { cst, .. }) = self.open.pop() else {
399                    return Err(structure_error("mismatched document end event", span));
400                };
401                self.store.close(cst, span, Some(*explicit));
402                Ok(())
403            }
404        }
405    }
406
407    pub(crate) fn push_tag_directive(&mut self, handle: Span, prefix: Span) {
408        self.store.tag_directives.push(TagDirectiveBinding {
409            handle,
410            prefix,
411            document: NodeId(u32::MAX),
412        });
413    }
414
415    fn insert_properties(&mut self, target: NodeId, properties: SemanticProperties) -> u32 {
416        if properties.is_empty() {
417            return NO_PROPERTIES;
418        }
419        let document = self
420            .open
421            .iter()
422            .find_map(|node| match node {
423                OpenNode::Document { cst, .. } => Some(*cst),
424                _ => None,
425            })
426            .unwrap_or(target);
427        let index = u32::try_from(self.store.properties.len())
428            .expect("semantic property arena exceeds u32 capacity");
429        self.store.properties.push(PropertyRecord {
430            properties,
431            document,
432        });
433        if let Some(name) = properties.anchor {
434            self.store.anchors.push(AnchorBinding {
435                name,
436                target,
437                document,
438            });
439        }
440        index
441    }
442
443    fn attach_child(&mut self, _child: NodeId, span: Span) -> Result<(), YamlError> {
444        let Some(parent) = self.open.last_mut() else {
445            return Ok(());
446        };
447        match parent {
448            OpenNode::Document { children, .. } => {
449                *children += 1;
450                if *children > 1 {
451                    return Err(structure_error(
452                        "document contains multiple root nodes",
453                        span,
454                    ));
455                }
456            }
457            OpenNode::Mapping {
458                waiting_for_value, ..
459            } => {
460                *waiting_for_value = !*waiting_for_value;
461            }
462            OpenNode::Sequence { .. } => {}
463        }
464        Ok(())
465    }
466
467    pub(crate) fn finish(mut self, cst_len: usize) -> Result<SemanticStore, YamlError> {
468        if let Some(error) = self.error {
469            return Err(error);
470        }
471        if !self.open.is_empty() {
472            return Err(structure_error("unclosed semantic node", Span::empty(0)));
473        }
474        self.store.slots.resize(cst_len, NO_SEMANTIC_NODE);
475        Ok(self.store)
476    }
477}
478
479impl SemanticNode {
480    fn new(kind: SemanticKind, span: Span, explicit_start: bool, property: u32) -> Self {
481        Self {
482            kind,
483            flags: u8::from(explicit_start) * EXPLICIT_START,
484            padding: 0,
485            span_start: span.start,
486            end_offset: span.end,
487            property,
488        }
489    }
490
491    pub(crate) const fn explicit_start(self) -> bool {
492        self.flags & EXPLICIT_START != 0
493    }
494
495    pub(crate) const fn explicit_end(self) -> bool {
496        self.flags & EXPLICIT_END != 0
497    }
498
499    fn set_flag(&mut self, flag: u8, value: bool) {
500        if value {
501            self.flags |= flag;
502        } else {
503            self.flags &= !flag;
504        }
505    }
506}
507
508fn required_cst(cst: Option<NodeId>, span: Span) -> Result<NodeId, YamlError> {
509    cst.ok_or_else(|| structure_error("semantic node is missing its CST origin", span))
510}
511
512#[derive(Clone, Copy)]
513enum OpenNode {
514    Document {
515        cst: NodeId,
516        children: usize,
517    },
518    Mapping {
519        cst: NodeId,
520        waiting_for_value: bool,
521    },
522    Sequence {
523        cst: NodeId,
524    },
525}
526
527fn structure_error(message: &str, span: Span) -> YamlError {
528    YamlError::new(Diagnostic::new(DiagnosticKind::Semantic, message, span))
529}
530
531#[cfg(test)]
532mod tests {
533    use super::{SemanticBuilder, SemanticNode, SemanticProperties};
534    use crate::{CollectionStyle, NodeId, Span, YamlEventKind, YamlScalarStyle};
535
536    #[test]
537    fn direct_builder_rejects_dangling_mapping_value() {
538        let mut builder = SemanticBuilder::with_capacity(4, 4);
539        builder.push(
540            YamlEventKind::DocumentStart { explicit: false },
541            Span::empty(0),
542            Some(NodeId(0)),
543            SemanticProperties::NONE,
544        );
545        builder.push(
546            YamlEventKind::MappingStart {
547                style: CollectionStyle::Block,
548                tag: None,
549                anchor: None,
550            },
551            Span::empty(0),
552            Some(NodeId(1)),
553            SemanticProperties::NONE,
554        );
555        builder.push(
556            YamlEventKind::Scalar {
557                style: YamlScalarStyle::Plain,
558                value: String::new(),
559                tag: None,
560                anchor: None,
561            },
562            Span::empty(0),
563            Some(NodeId(2)),
564            SemanticProperties::NONE,
565        );
566        builder.push(
567            YamlEventKind::MappingEnd,
568            Span::empty(0),
569            None,
570            SemanticProperties::NONE,
571        );
572
573        let error = builder.finish(3).expect_err("mapping value is required");
574        assert!(error.to_string().contains("does not contain a value"));
575    }
576
577    #[test]
578    fn direct_builder_rejects_mismatched_collection_end() {
579        let mut builder = SemanticBuilder::with_capacity(2, 2);
580        builder.push(
581            YamlEventKind::SequenceStart {
582                style: CollectionStyle::Flow,
583                tag: None,
584                anchor: None,
585            },
586            Span::empty(0),
587            Some(NodeId(0)),
588            SemanticProperties::NONE,
589        );
590        builder.push(
591            YamlEventKind::MappingEnd,
592            Span::empty(1),
593            None,
594            SemanticProperties::NONE,
595        );
596
597        let error = builder.finish(1).expect_err("collection ends must match");
598        assert!(error.to_string().contains("mismatched mapping end"));
599    }
600
601    #[test]
602    fn direct_builder_rejects_multiple_document_roots() {
603        let mut builder = SemanticBuilder::with_capacity(3, 3);
604        builder.push(
605            YamlEventKind::DocumentStart { explicit: false },
606            Span::empty(0),
607            Some(NodeId(0)),
608            SemanticProperties::NONE,
609        );
610        for cst in [NodeId(1), NodeId(2)] {
611            builder.push(
612                YamlEventKind::Scalar {
613                    style: YamlScalarStyle::Plain,
614                    value: String::new(),
615                    tag: None,
616                    anchor: None,
617                },
618                Span::empty(0),
619                Some(cst),
620                SemanticProperties::NONE,
621            );
622        }
623
624        let error = builder.finish(3).expect_err("documents have one root");
625        assert!(error.to_string().contains("multiple root nodes"));
626    }
627
628    #[test]
629    fn semantic_record_is_at_most_sixteen_bytes() {
630        assert!(std::mem::size_of::<SemanticNode>() <= 16);
631    }
632
633    #[test]
634    fn undecorated_nodes_do_not_populate_sparse_arenas() {
635        let mut builder = SemanticBuilder::with_capacity(2, 2);
636        builder.push(
637            YamlEventKind::DocumentStart { explicit: false },
638            Span::empty(0),
639            Some(NodeId(0)),
640            SemanticProperties::NONE,
641        );
642        builder.push(
643            YamlEventKind::Scalar {
644                style: YamlScalarStyle::Plain,
645                value: String::new(),
646                tag: None,
647                anchor: None,
648            },
649            Span::empty(0),
650            Some(NodeId(1)),
651            SemanticProperties::NONE,
652        );
653        builder.push(
654            YamlEventKind::DocumentEnd { explicit: false },
655            Span::empty(0),
656            None,
657            SemanticProperties::NONE,
658        );
659
660        let store = builder.finish(2).expect("semantic structure closes");
661        assert!(store.properties.is_empty());
662        assert!(store.anchors.is_empty());
663        assert!(store.tag_directives.is_empty());
664    }
665}
yaml_rt_core/semantic.rs

yaml_rt_core/
semantic.rs
