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 property_document(&self, cst: NodeId) -> Option<NodeId> {
127        let node = self.get(cst)?;
128        (node.property != NO_PROPERTIES).then(|| self.properties[node.property as usize].document)
129    }
130
131    pub(crate) fn anchors(&self) -> impl DoubleEndedIterator<Item = (Span, NodeId, NodeId)> + '_ {
132        self.anchors
133            .iter()
134            .map(|binding| (binding.name, binding.target, binding.document))
135    }
136
137    pub(crate) fn tag_directives(
138        &self,
139        document: NodeId,
140    ) -> impl Iterator<Item = (Span, Span)> + '_ {
141        self.tag_directives
142            .iter()
143            .filter(move |binding| binding.document == document)
144            .map(|binding| (binding.handle, binding.prefix))
145    }
146}
147
148pub(crate) struct SemanticBuilder {
149    store: SemanticStore,
150    open: Vec<OpenNode>,
151    error: Option<YamlError>,
152}
153
154impl SemanticBuilder {
155    pub(crate) fn with_capacity(cst_capacity: usize, semantic_capacity: usize) -> Self {
156        Self {
157            store: SemanticStore {
158                slots: Vec::with_capacity(cst_capacity),
159                nodes: Vec::with_capacity(semantic_capacity),
160                properties: Vec::new(),
161                anchors: Vec::new(),
162                tag_directives: Vec::new(),
163                documents: Vec::with_capacity(1),
164            },
165            open: Vec::with_capacity(8),
166            error: None,
167        }
168    }
169
170    pub(crate) fn push(
171        &mut self,
172        kind: YamlEventKind,
173        span: Span,
174        cst: Option<NodeId>,
175        properties: SemanticProperties,
176    ) {
177        if self.error.is_some() {
178            return;
179        }
180        if let Err(error) = self.try_push(kind, span, cst, properties) {
181            self.error = Some(error);
182        }
183    }
184
185    fn try_push(
186        &mut self,
187        kind: YamlEventKind,
188        span: Span,
189        cst: Option<NodeId>,
190        properties: SemanticProperties,
191    ) -> Result<(), YamlError> {
192        match kind {
193            YamlEventKind::StreamStart | YamlEventKind::StreamEnd => Ok(()),
194            YamlEventKind::DocumentStart { explicit } => {
195                let cst = required_cst(cst, span)?;
196                for directive in self
197                    .store
198                    .tag_directives
199                    .iter_mut()
200                    .rev()
201                    .take_while(|directive| directive.document == NodeId(u32::MAX))
202                {
203                    directive.document = cst;
204                }
205                self.store.documents.push(cst);
206                let property = self.insert_properties(cst, properties);
207                self.store.insert(
208                    cst,
209                    SemanticNode::new(SemanticKind::Document, span, explicit, property),
210                );
211                self.open.push(OpenNode::Document { cst, children: 0 });
212                Ok(())
213            }
214            YamlEventKind::MappingStart { style, .. } => {
215                let cst = required_cst(cst, span)?;
216                let property = self.insert_properties(cst, properties);
217                self.store.insert(
218                    cst,
219                    SemanticNode::new(SemanticKind::Mapping { style }, span, false, property),
220                );
221                self.open.push(OpenNode::Mapping {
222                    cst,
223                    waiting_for_value: false,
224                });
225                Ok(())
226            }
227            YamlEventKind::SequenceStart { style, .. } => {
228                let cst = required_cst(cst, span)?;
229                let property = self.insert_properties(cst, properties);
230                self.store.insert(
231                    cst,
232                    SemanticNode::new(SemanticKind::Sequence { style }, span, false, property),
233                );
234                self.open.push(OpenNode::Sequence { cst });
235                Ok(())
236            }
237            YamlEventKind::Scalar { style, .. } => {
238                let cst = required_cst(cst, span)?;
239                let property = self.insert_properties(cst, properties);
240                self.store.insert(
241                    cst,
242                    SemanticNode::new(SemanticKind::Scalar { style }, span, false, property),
243                );
244                self.attach_child(cst, span)
245            }
246            YamlEventKind::Alias { .. } => {
247                let cst = required_cst(cst, span)?;
248                let property = self.insert_properties(cst, properties);
249                self.store.insert(
250                    cst,
251                    SemanticNode::new(SemanticKind::Alias, span, false, property),
252                );
253                self.attach_child(cst, span)
254            }
255            YamlEventKind::MappingEnd => {
256                let Some(OpenNode::Mapping {
257                    cst,
258                    waiting_for_value,
259                }) = self.open.pop()
260                else {
261                    return Err(structure_error("mismatched mapping end event", span));
262                };
263                if waiting_for_value {
264                    return Err(structure_error(
265                        "mapping entry does not contain a value",
266                        span,
267                    ));
268                }
269                self.store.close(cst, span, None);
270                self.attach_child(cst, span)
271            }
272            YamlEventKind::SequenceEnd => {
273                let Some(OpenNode::Sequence { cst }) = self.open.pop() else {
274                    return Err(structure_error("mismatched sequence end event", span));
275                };
276                self.store.close(cst, span, None);
277                self.attach_child(cst, span)
278            }
279            YamlEventKind::DocumentEnd { explicit } => {
280                let Some(OpenNode::Document { cst, .. }) = self.open.pop() else {
281                    return Err(structure_error("mismatched document end event", span));
282                };
283                self.store.close(cst, span, Some(explicit));
284                Ok(())
285            }
286        }
287    }
288
289    pub(crate) fn push_tag_directive(&mut self, handle: Span, prefix: Span) {
290        self.store.tag_directives.push(TagDirectiveBinding {
291            handle,
292            prefix,
293            document: NodeId(u32::MAX),
294        });
295    }
296
297    fn insert_properties(&mut self, target: NodeId, properties: SemanticProperties) -> u32 {
298        if properties.is_empty() {
299            return NO_PROPERTIES;
300        }
301        let document = self
302            .open
303            .iter()
304            .find_map(|node| match node {
305                OpenNode::Document { cst, .. } => Some(*cst),
306                _ => None,
307            })
308            .unwrap_or(target);
309        let index = u32::try_from(self.store.properties.len())
310            .expect("semantic property arena exceeds u32 capacity");
311        self.store.properties.push(PropertyRecord {
312            properties,
313            document,
314        });
315        if let Some(name) = properties.anchor {
316            self.store.anchors.push(AnchorBinding {
317                name,
318                target,
319                document,
320            });
321        }
322        index
323    }
324
325    fn attach_child(&mut self, _child: NodeId, span: Span) -> Result<(), YamlError> {
326        let Some(parent) = self.open.last_mut() else {
327            return Ok(());
328        };
329        match parent {
330            OpenNode::Document { children, .. } => {
331                *children += 1;
332                if *children > 1 {
333                    return Err(structure_error(
334                        "document contains multiple root nodes",
335                        span,
336                    ));
337                }
338            }
339            OpenNode::Mapping {
340                waiting_for_value, ..
341            } => {
342                *waiting_for_value = !*waiting_for_value;
343            }
344            OpenNode::Sequence { .. } => {}
345        }
346        Ok(())
347    }
348
349    pub(crate) fn finish(mut self, cst_len: usize) -> Result<SemanticStore, YamlError> {
350        if let Some(error) = self.error {
351            return Err(error);
352        }
353        if !self.open.is_empty() {
354            return Err(structure_error("unclosed semantic node", Span::empty(0)));
355        }
356        self.store.slots.resize(cst_len, NO_SEMANTIC_NODE);
357        Ok(self.store)
358    }
359}
360
361impl SemanticNode {
362    fn new(kind: SemanticKind, span: Span, explicit_start: bool, property: u32) -> Self {
363        Self {
364            kind,
365            flags: u8::from(explicit_start) * EXPLICIT_START,
366            padding: 0,
367            span_start: span.start,
368            end_offset: span.end,
369            property,
370        }
371    }
372
373    pub(crate) const fn explicit_start(self) -> bool {
374        self.flags & EXPLICIT_START != 0
375    }
376
377    pub(crate) const fn explicit_end(self) -> bool {
378        self.flags & EXPLICIT_END != 0
379    }
380
381    fn set_flag(&mut self, flag: u8, value: bool) {
382        if value {
383            self.flags |= flag;
384        } else {
385            self.flags &= !flag;
386        }
387    }
388}
389
390fn required_cst(cst: Option<NodeId>, span: Span) -> Result<NodeId, YamlError> {
391    cst.ok_or_else(|| structure_error("semantic node is missing its CST origin", span))
392}
393
394#[derive(Clone, Copy)]
395enum OpenNode {
396    Document {
397        cst: NodeId,
398        children: usize,
399    },
400    Mapping {
401        cst: NodeId,
402        waiting_for_value: bool,
403    },
404    Sequence {
405        cst: NodeId,
406    },
407}
408
409fn structure_error(message: &str, span: Span) -> YamlError {
410    YamlError::new(Diagnostic::new(DiagnosticKind::Semantic, message, span))
411}
412
413#[cfg(test)]
414mod tests {
415    use super::{SemanticBuilder, SemanticNode, SemanticProperties};
416    use crate::{CollectionStyle, NodeId, Span, YamlEventKind, YamlScalarStyle};
417
418    #[test]
419    fn direct_builder_rejects_dangling_mapping_value() {
420        let mut builder = SemanticBuilder::with_capacity(4, 4);
421        builder.push(
422            YamlEventKind::DocumentStart { explicit: false },
423            Span::empty(0),
424            Some(NodeId(0)),
425            SemanticProperties::NONE,
426        );
427        builder.push(
428            YamlEventKind::MappingStart {
429                style: CollectionStyle::Block,
430                tag: None,
431                anchor: None,
432            },
433            Span::empty(0),
434            Some(NodeId(1)),
435            SemanticProperties::NONE,
436        );
437        builder.push(
438            YamlEventKind::Scalar {
439                style: YamlScalarStyle::Plain,
440                value: String::new(),
441                tag: None,
442                anchor: None,
443            },
444            Span::empty(0),
445            Some(NodeId(2)),
446            SemanticProperties::NONE,
447        );
448        builder.push(
449            YamlEventKind::MappingEnd,
450            Span::empty(0),
451            None,
452            SemanticProperties::NONE,
453        );
454
455        let error = builder.finish(3).expect_err("mapping value is required");
456        assert!(error.to_string().contains("does not contain a value"));
457    }
458
459    #[test]
460    fn direct_builder_rejects_mismatched_collection_end() {
461        let mut builder = SemanticBuilder::with_capacity(2, 2);
462        builder.push(
463            YamlEventKind::SequenceStart {
464                style: CollectionStyle::Flow,
465                tag: None,
466                anchor: None,
467            },
468            Span::empty(0),
469            Some(NodeId(0)),
470            SemanticProperties::NONE,
471        );
472        builder.push(
473            YamlEventKind::MappingEnd,
474            Span::empty(1),
475            None,
476            SemanticProperties::NONE,
477        );
478
479        let error = builder.finish(1).expect_err("collection ends must match");
480        assert!(error.to_string().contains("mismatched mapping end"));
481    }
482
483    #[test]
484    fn direct_builder_rejects_multiple_document_roots() {
485        let mut builder = SemanticBuilder::with_capacity(3, 3);
486        builder.push(
487            YamlEventKind::DocumentStart { explicit: false },
488            Span::empty(0),
489            Some(NodeId(0)),
490            SemanticProperties::NONE,
491        );
492        for cst in [NodeId(1), NodeId(2)] {
493            builder.push(
494                YamlEventKind::Scalar {
495                    style: YamlScalarStyle::Plain,
496                    value: String::new(),
497                    tag: None,
498                    anchor: None,
499                },
500                Span::empty(0),
501                Some(cst),
502                SemanticProperties::NONE,
503            );
504        }
505
506        let error = builder.finish(3).expect_err("documents have one root");
507        assert!(error.to_string().contains("multiple root nodes"));
508    }
509
510    #[test]
511    fn semantic_record_is_at_most_sixteen_bytes() {
512        assert!(std::mem::size_of::<SemanticNode>() <= 16);
513    }
514
515    #[test]
516    fn undecorated_nodes_do_not_populate_sparse_arenas() {
517        let mut builder = SemanticBuilder::with_capacity(2, 2);
518        builder.push(
519            YamlEventKind::DocumentStart { explicit: false },
520            Span::empty(0),
521            Some(NodeId(0)),
522            SemanticProperties::NONE,
523        );
524        builder.push(
525            YamlEventKind::Scalar {
526                style: YamlScalarStyle::Plain,
527                value: String::new(),
528                tag: None,
529                anchor: None,
530            },
531            Span::empty(0),
532            Some(NodeId(1)),
533            SemanticProperties::NONE,
534        );
535        builder.push(
536            YamlEventKind::DocumentEnd { explicit: false },
537            Span::empty(0),
538            None,
539            SemanticProperties::NONE,
540        );
541
542        let store = builder.finish(2).expect("semantic structure closes");
543        assert!(store.properties.is_empty());
544        assert!(store.anchors.is_empty());
545        assert!(store.tag_directives.is_empty());
546    }
547}
yaml_rt_core/semantic.rs

yaml_rt_core/
semantic.rs
