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

yaml_rt_core/
semantic.rs
