yaml_rt_core/
value.rs

1use std::collections::{BTreeMap, HashSet};
2use std::fmt;
3
4use crate::{CollectionStyle, NodeId, SemanticKind, YamlDoc, YamlScalarStyle};
5
6const NULL_TAG: &str = "tag:yaml.org,2002:null";
7const BOOL_TAG: &str = "tag:yaml.org,2002:bool";
8const INT_TAG: &str = "tag:yaml.org,2002:int";
9const FLOAT_TAG: &str = "tag:yaml.org,2002:float";
10const STR_TAG: &str = "tag:yaml.org,2002:str";
11const SEQ_TAG: &str = "tag:yaml.org,2002:seq";
12const MAP_TAG: &str = "tag:yaml.org,2002:map";
13
14/// An exact, finite YAML number normalized for semantic comparison.
15#[derive(Debug, Clone)]
16pub struct YamlNumber {
17    negative: bool,
18    digits: String,
19    exponent: i64,
20    integer_syntax: bool,
21}
22
23impl YamlNumber {
24    /// Returns whether the source used YAML integer rather than float syntax.
25    #[must_use]
26    pub const fn has_integer_syntax(&self) -> bool {
27        self.integer_syntax
28    }
29
30    /// Converts an integer-syntax number to `i128` when it fits.
31    #[must_use]
32    pub fn as_i128(&self) -> Option<i128> {
33        if !self.integer_syntax || self.exponent < 0 {
34            return None;
35        }
36        let mut text = self.digits.clone();
37        text.extend(std::iter::repeat_n(
38            '0',
39            usize::try_from(self.exponent).ok()?,
40        ));
41        if self.negative {
42            text.insert(0, '-');
43        }
44        text.parse().ok()
45    }
46
47    /// Converts a non-negative integer-syntax number to `u128` when it fits.
48    #[must_use]
49    pub fn as_u128(&self) -> Option<u128> {
50        if self.negative || !self.integer_syntax || self.exponent < 0 {
51            return None;
52        }
53        let mut text = self.digits.clone();
54        text.extend(std::iter::repeat_n(
55            '0',
56            usize::try_from(self.exponent).ok()?,
57        ));
58        text.parse().ok()
59    }
60
61    /// Converts this finite number to an `f64`.
62    #[must_use]
63    pub fn as_f64(&self) -> Option<f64> {
64        let sign = if self.negative { "-" } else { "" };
65        format!("{sign}{}e{}", self.digits, self.exponent)
66            .parse()
67            .ok()
68    }
69}
70
71impl PartialEq for YamlNumber {
72    fn eq(&self, other: &Self) -> bool {
73        self.negative == other.negative
74            && self.digits == other.digits
75            && self.exponent == other.exponent
76    }
77}
78
79impl Eq for YamlNumber {}
80
81/// A non-finite YAML float, which is outside the JSON-compatible data model.
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub enum NonFiniteFloat {
84    /// Positive infinity.
85    PositiveInfinity,
86    /// Negative infinity.
87    NegativeInfinity,
88    /// Not a number.
89    NaN,
90}
91
92/// YAML 1.2 core-schema interpretation of a scalar.
93#[derive(Debug, Clone, PartialEq, Eq)]
94pub enum ResolvedScalar {
95    /// YAML null.
96    Null,
97    /// YAML boolean.
98    Bool(bool),
99    /// A finite integer or float.
100    Number(YamlNumber),
101    /// A YAML infinity or NaN spelling.
102    NonFinite(NonFiniteFloat),
103    /// A string scalar.
104    String,
105}
106
107/// Failure to resolve a scalar according to the YAML core schema.
108#[derive(Debug, Clone, PartialEq, Eq)]
109pub struct ScalarResolveError {
110    message: String,
111}
112
113impl ScalarResolveError {
114    fn new(message: impl Into<String>) -> Self {
115        Self {
116            message: message.into(),
117        }
118    }
119}
120
121impl fmt::Display for ScalarResolveError {
122    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
123        formatter.write_str(&self.message)
124    }
125}
126
127impl std::error::Error for ScalarResolveError {}
128
129/// Resolves a decoded scalar value using the YAML 1.2 core schema.
130pub fn resolve_scalar(
131    value: &str,
132    style: YamlScalarStyle,
133    tag: Option<&str>,
134) -> Result<ResolvedScalar, ScalarResolveError> {
135    if tag == Some(STR_TAG) {
136        return Ok(ResolvedScalar::String);
137    }
138    if let Some(tag) = tag
139        && !matches!(tag, NULL_TAG | BOOL_TAG | INT_TAG | FLOAT_TAG)
140    {
141        return Err(ScalarResolveError::new(format!(
142            "unsupported scalar tag `{tag}`"
143        )));
144    }
145    if style != YamlScalarStyle::Plain && tag.is_none() {
146        return Ok(ResolvedScalar::String);
147    }
148    if tag == Some(NULL_TAG)
149        || tag.is_none() && matches!(value, "" | "~" | "null" | "Null" | "NULL")
150    {
151        return if matches!(value, "" | "~" | "null" | "Null" | "NULL") {
152            Ok(ResolvedScalar::Null)
153        } else {
154            Err(ScalarResolveError::new("invalid null scalar"))
155        };
156    }
157    if tag == Some(BOOL_TAG) || tag.is_none() {
158        match value {
159            "true" | "True" | "TRUE" => return Ok(ResolvedScalar::Bool(true)),
160            "false" | "False" | "FALSE" => return Ok(ResolvedScalar::Bool(false)),
161            _ if tag == Some(BOOL_TAG) => {
162                return Err(ScalarResolveError::new("invalid boolean scalar"));
163            }
164            _ => {}
165        }
166    }
167    if tag == Some(INT_TAG) || tag.is_none() {
168        if let Some(number) = parse_integer(value) {
169            return Ok(ResolvedScalar::Number(number));
170        }
171        if tag == Some(INT_TAG) {
172            return Err(ScalarResolveError::new("invalid integer scalar"));
173        }
174    }
175    if tag == Some(FLOAT_TAG) || tag.is_none() && looks_like_float(value) {
176        if let Some(special) = parse_non_finite(value) {
177            return Ok(ResolvedScalar::NonFinite(special));
178        }
179        if let Some(number) = parse_decimal(value, false) {
180            return Ok(ResolvedScalar::Number(number));
181        }
182        if tag == Some(FLOAT_TAG) {
183            return Err(ScalarResolveError::new("invalid float scalar"));
184        }
185    }
186    Ok(ResolvedScalar::String)
187}
188
189fn parse_integer(value: &str) -> Option<YamlNumber> {
190    let normalized = value.replace('_', "");
191    let (negative, unsigned) = strip_sign(&normalized);
192    let (radix, digits) = if let Some(rest) = unsigned.strip_prefix("0x") {
193        (16, rest)
194    } else if let Some(rest) = unsigned.strip_prefix("0o") {
195        (8, rest)
196    } else if let Some(rest) = unsigned.strip_prefix("0b") {
197        (2, rest)
198    } else {
199        (10, unsigned)
200    };
201    if digits.is_empty()
202        || !digits.chars().all(|character| character.is_digit(radix))
203        || radix == 10 && digits.len() > 1 && digits.starts_with('0')
204    {
205        return None;
206    }
207    let decimal = if radix == 10 {
208        digits.to_owned()
209    } else {
210        radix_to_decimal(digits, radix)?
211    };
212    normalize_number(negative, decimal, 0, true)
213}
214
215fn radix_to_decimal(digits: &str, radix: u32) -> Option<String> {
216    let mut decimal = vec![0_u8];
217    for character in digits.chars() {
218        let digit = character.to_digit(radix)?;
219        let mut carry = digit;
220        for value in decimal.iter_mut().rev() {
221            let next = u32::from(*value) * radix + carry;
222            *value = u8::try_from(next % 10).ok()?;
223            carry = next / 10;
224        }
225        while carry > 0 {
226            decimal.insert(0, u8::try_from(carry % 10).ok()?);
227            carry /= 10;
228        }
229    }
230    Some(
231        decimal
232            .into_iter()
233            .map(|digit| char::from(b'0' + digit))
234            .collect(),
235    )
236}
237
238fn parse_decimal(value: &str, integer_syntax: bool) -> Option<YamlNumber> {
239    let normalized = value.replace('_', "");
240    let (negative, unsigned) = strip_sign(&normalized);
241    let (mantissa, exponent) = match unsigned.find(['e', 'E']) {
242        Some(index) => {
243            let exponent = unsigned[index + 1..].parse::<i64>().ok()?;
244            (&unsigned[..index], exponent)
245        }
246        None => (unsigned, 0),
247    };
248    let (whole, fraction) = match mantissa.split_once('.') {
249        Some(parts) => parts,
250        None => (mantissa, ""),
251    };
252    if whole.is_empty() && fraction.is_empty()
253        || !whole.chars().all(|character| character.is_ascii_digit())
254        || !fraction.chars().all(|character| character.is_ascii_digit())
255    {
256        return None;
257    }
258    let digits = format!("{whole}{fraction}");
259    let exponent = exponent.checked_sub(i64::try_from(fraction.len()).ok()?)?;
260    normalize_number(negative, digits, exponent, integer_syntax)
261}
262
263fn normalize_number(
264    mut negative: bool,
265    digits: String,
266    mut exponent: i64,
267    integer_syntax: bool,
268) -> Option<YamlNumber> {
269    let mut digits = digits.trim_start_matches('0').to_owned();
270    if digits.is_empty() {
271        negative = false;
272        digits.push('0');
273        exponent = 0;
274    } else {
275        while digits.ends_with('0') {
276            digits.pop();
277            exponent = exponent.checked_add(1)?;
278        }
279    }
280    Some(YamlNumber {
281        negative,
282        digits,
283        exponent,
284        integer_syntax,
285    })
286}
287
288fn strip_sign(value: &str) -> (bool, &str) {
289    if let Some(rest) = value.strip_prefix('-') {
290        (true, rest)
291    } else {
292        (false, value.strip_prefix('+').unwrap_or(value))
293    }
294}
295
296fn looks_like_float(value: &str) -> bool {
297    value.contains(['.', 'e', 'E'])
298}
299
300fn parse_non_finite(value: &str) -> Option<NonFiniteFloat> {
301    match value {
302        ".inf" | ".Inf" | ".INF" | "+.inf" | "+.Inf" | "+.INF" => {
303            Some(NonFiniteFloat::PositiveInfinity)
304        }
305        "-.inf" | "-.Inf" | "-.INF" => Some(NonFiniteFloat::NegativeInfinity),
306        ".nan" | ".NaN" | ".NAN" => Some(NonFiniteFloat::NaN),
307        _ => None,
308    }
309}
310
311/// Failure while projecting YAML nodes into the JSON-compatible data model.
312#[derive(Debug, Clone, PartialEq, Eq)]
313pub struct SemanticValueError {
314    message: String,
315}
316
317impl SemanticValueError {
318    pub(crate) fn new(message: impl Into<String>) -> Self {
319        Self {
320            message: message.into(),
321        }
322    }
323}
324
325impl fmt::Display for SemanticValueError {
326    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
327        formatter.write_str(&self.message)
328    }
329}
330
331impl std::error::Error for SemanticValueError {}
332
333/// Compares two YAML nodes using RFC 6902 JSON-value equality.
334pub fn semantically_equal(
335    left_doc: &YamlDoc,
336    left: NodeId,
337    right_doc: &YamlDoc,
338    right: NodeId,
339) -> Result<bool, SemanticValueError> {
340    let mut active = HashSet::new();
341    compare_nodes(left_doc, left, right_doc, right, &mut active, 0)
342}
343
344fn compare_nodes(
345    left_doc: &YamlDoc,
346    left: NodeId,
347    right_doc: &YamlDoc,
348    right: NodeId,
349    active: &mut HashSet<(NodeId, NodeId)>,
350    depth: usize,
351) -> Result<bool, SemanticValueError> {
352    if depth > 1024 {
353        return Err(SemanticValueError::new(
354            "semantic comparison recursion limit exceeded",
355        ));
356    }
357    let left = resolve_alias_chain(left_doc, left)?;
358    let right = resolve_alias_chain(right_doc, right)?;
359    if !active.insert((left, right)) {
360        return Err(SemanticValueError::new(
361            "cyclic YAML values are not JSON-compatible",
362        ));
363    }
364    let result = compare_resolved(left_doc, left, right_doc, right, active, depth);
365    active.remove(&(left, right));
366    result
367}
368
369fn compare_resolved(
370    left_doc: &YamlDoc,
371    left: NodeId,
372    right_doc: &YamlDoc,
373    right: NodeId,
374    active: &mut HashSet<(NodeId, NodeId)>,
375    depth: usize,
376) -> Result<bool, SemanticValueError> {
377    match (left_doc.semantic_kind(left), right_doc.semantic_kind(right)) {
378        (
379            Some(SemanticKind::Scalar { style: left_style }),
380            Some(SemanticKind::Scalar { style: right_style }),
381        ) => {
382            let left = resolved_scalar_at(left_doc, left, left_style)?;
383            let right = resolved_scalar_at(right_doc, right, right_style)?;
384            if matches!(left, ResolvedScalar::NonFinite(_))
385                || matches!(right, ResolvedScalar::NonFinite(_))
386            {
387                return Err(SemanticValueError::new(
388                    "infinities and NaN are not JSON-compatible",
389                ));
390            }
391            Ok(left == right)
392        }
393        (
394            Some(SemanticKind::Sequence { style: left_style }),
395            Some(SemanticKind::Sequence { style: right_style }),
396        ) => {
397            validate_collection_tag(left_doc, left, left_style, false)?;
398            validate_collection_tag(right_doc, right, right_style, false)?;
399            let left_items = left_doc.sequence_items(left).collect::<Vec<_>>();
400            let right_items = right_doc.sequence_items(right).collect::<Vec<_>>();
401            if left_items.len() != right_items.len() {
402                return Ok(false);
403            }
404            for (left_item, right_item) in left_items.into_iter().zip(right_items) {
405                if !compare_nodes(
406                    left_doc,
407                    left_item,
408                    right_doc,
409                    right_item,
410                    active,
411                    depth + 1,
412                )? {
413                    return Ok(false);
414                }
415            }
416            Ok(true)
417        }
418        (
419            Some(SemanticKind::Mapping { style: left_style }),
420            Some(SemanticKind::Mapping { style: right_style }),
421        ) => {
422            validate_collection_tag(left_doc, left, left_style, true)?;
423            validate_collection_tag(right_doc, right, right_style, true)?;
424            let left_entries = json_mapping(left_doc, left)?;
425            let right_entries = json_mapping(right_doc, right)?;
426            if left_entries.len() != right_entries.len() {
427                return Ok(false);
428            }
429            for (key, left_value) in left_entries {
430                let Some(right_value) = right_entries.get(&key).copied() else {
431                    return Ok(false);
432                };
433                if !compare_nodes(
434                    left_doc,
435                    left_value,
436                    right_doc,
437                    right_value,
438                    active,
439                    depth + 1,
440                )? {
441                    return Ok(false);
442                }
443            }
444            Ok(true)
445        }
446        (Some(SemanticKind::Alias), _) | (_, Some(SemanticKind::Alias)) => {
447            unreachable!("aliases are resolved before comparison")
448        }
449        (Some(_), Some(_)) => Ok(false),
450        _ => Err(SemanticValueError::new("unknown semantic YAML node")),
451    }
452}
453
454fn resolved_scalar_at(
455    doc: &YamlDoc,
456    node: NodeId,
457    style: YamlScalarStyle,
458) -> Result<ResolvedScalar, SemanticValueError> {
459    let value = doc
460        .scalar_value(node)
461        .map_err(|error| SemanticValueError::new(error.to_string()))?;
462    let tag = doc
463        .resolved_tag(node)
464        .map_err(|error| SemanticValueError::new(error.to_string()))?;
465    resolve_scalar(&value, style, tag.as_deref())
466        .map_err(|error| SemanticValueError::new(error.to_string()))
467}
468
469fn resolve_alias_chain(doc: &YamlDoc, mut node: NodeId) -> Result<NodeId, SemanticValueError> {
470    let mut seen = HashSet::new();
471    while matches!(doc.semantic_kind(node), Some(SemanticKind::Alias)) {
472        if !seen.insert(node) {
473            return Err(SemanticValueError::new("cyclic alias chain"));
474        }
475        node = doc.resolve_alias(node).ok_or_else(|| {
476            SemanticValueError::new(format!(
477                "unresolved alias `*{}`",
478                doc.alias_name(node).unwrap_or_default()
479            ))
480        })?;
481    }
482    Ok(node)
483}
484
485fn json_mapping(
486    doc: &YamlDoc,
487    mapping: NodeId,
488) -> Result<BTreeMap<String, NodeId>, SemanticValueError> {
489    let mut entries = BTreeMap::new();
490    for (key, value) in doc.mapping_entries(mapping) {
491        let key = resolve_alias_chain(doc, key)?;
492        let Some(SemanticKind::Scalar { style }) = doc.semantic_kind(key) else {
493            return Err(SemanticValueError::new("mapping contains a non-string key"));
494        };
495        if resolved_scalar_at(doc, key, style)? != ResolvedScalar::String {
496            return Err(SemanticValueError::new("mapping contains a non-string key"));
497        }
498        let key = doc
499            .scalar_value(key)
500            .map_err(|error| SemanticValueError::new(error.to_string()))?
501            .into_owned();
502        if entries.insert(key.clone(), value).is_some() {
503            return Err(SemanticValueError::new(format!(
504                "mapping contains duplicate key `{key}`"
505            )));
506        }
507    }
508    Ok(entries)
509}
510
511fn validate_collection_tag(
512    doc: &YamlDoc,
513    node: NodeId,
514    _style: CollectionStyle,
515    mapping: bool,
516) -> Result<(), SemanticValueError> {
517    let tag = doc
518        .resolved_tag(node)
519        .map_err(|error| SemanticValueError::new(error.to_string()))?;
520    let expected = if mapping { MAP_TAG } else { SEQ_TAG };
521    if tag.as_deref().is_some_and(|tag| tag != expected) {
522        return Err(SemanticValueError::new(format!(
523            "custom-tagged collections are not JSON-compatible: `{}`",
524            tag.as_deref().unwrap_or_default()
525        )));
526    }
527    Ok(())
528}
529
530#[cfg(test)]
531mod tests {
532    use super::*;
533
534    #[test]
535    fn exact_numbers_compare_across_yaml_spellings() {
536        let values = ["1", "1.0", "1e0", "0x1"];
537        let numbers = values
538            .into_iter()
539            .map(|value| {
540                let ResolvedScalar::Number(number) =
541                    resolve_scalar(value, YamlScalarStyle::Plain, None).unwrap()
542                else {
543                    panic!("expected number");
544                };
545                number
546            })
547            .collect::<Vec<_>>();
548        assert!(numbers.windows(2).all(|pair| pair[0] == pair[1]));
549    }
550
551    #[test]
552    fn semantic_equality_ignores_presentation_and_mapping_order() {
553        let left = YamlDoc::parse("a: 1\nb: ['x', true]\n").unwrap();
554        let right = YamlDoc::parse("{b: [x, TRUE], a: 1.0}\n").unwrap();
555        assert!(
556            semantically_equal(
557                &left,
558                left.document_root(0).unwrap().unwrap(),
559                &right,
560                right.document_root(0).unwrap().unwrap()
561            )
562            .unwrap()
563        );
564    }
565
566    #[test]
567    fn semantic_equality_rejects_non_string_keys() {
568        let left = YamlDoc::parse("1: value\n").unwrap();
569        let right = YamlDoc::parse("'1': value\n").unwrap();
570        assert!(
571            semantically_equal(
572                &left,
573                left.document_root(0).unwrap().unwrap(),
574                &right,
575                right.document_root(0).unwrap().unwrap()
576            )
577            .unwrap_err()
578            .to_string()
579            .contains("non-string")
580        );
581    }
582}
yaml_rt_core/value.rs

yaml_rt_core/
value.rs
