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