wai-quantum 0.4.0

//! The JSON a WQC container's contract and measurement sections are read as
//! (extensions/quantum-sim §2): I-JSON (RFC 7493), with every rule decided here
//! from the section's text.
//!
//! A general JSON parser leaves some of these rules to its build: whether a
//! number near the largest double is in range, for one, can depend on which
//! float parser was compiled in, and a float parser may stop reading a long
//! exponent. A conformance verdict must not, so this reader keeps each number's
//! literal text and decides each rule itself, the range rule on the digits.

use std::collections::BTreeSet;
use std::fmt;

/// The deepest nesting of arrays and objects a section may hold, the outermost
/// counted as the first.
pub(crate) const MAX_DEPTH: usize = 127;

/// 2^1024 − 2^970 in decimal: the least magnitude that rounds to an infinite
/// double, rounding to nearest with ties to even. A number of this magnitude or
/// more is out of range (extensions/quantum-sim §2).
pub(crate) const RANGE_LIMIT: &str = "179769313486231580793728971405303415079934132710037826936173778980444968292764750946649017977587207096330286416692887910946555547851940402630657488671505820681908902000708383676273854845817711531764475730270069855571366959622842914819860834936475292719074168444365510704342711559699508093042880177904174497792";

/// A JSON value as the sections need it. A number keeps its literal text: the
/// sections read only unsigned integers, and the range rule is decided on the
/// text.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) enum Json {
    Null,
    Bool(bool),
    Number(String),
    String(String),
    Array(Vec<Json>),
    Object(Vec<(String, Json)>),
}

impl Json {
    /// The member `name` of an object; `None` for a missing member or a value
    /// that is not an object.
    pub(crate) fn get(&self, name: &str) -> Option<&Json> {
        match self {
            Json::Object(members) => members.iter().find(|(k, _)| k == name).map(|(_, v)| v),
            _ => None,
        }
    }

    pub(crate) fn as_str(&self) -> Option<&str> {
        match self {
            Json::String(s) => Some(s),
            _ => None,
        }
    }

    /// The value of an unsigned JSON integer that fits a `u64`: a number written
    /// with no sign, fraction or exponent. `-0`, `2.0` and `2e0` are not one.
    pub(crate) fn as_u64(&self) -> Option<u64> {
        match self {
            Json::Number(t) if t.bytes().all(|b| b.is_ascii_digit()) => t.parse().ok(),
            _ => None,
        }
    }
}

impl fmt::Display for Json {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Json::Null => f.write_str("null"),
            Json::Bool(b) => write!(f, "{b}"),
            Json::Number(t) => f.write_str(t),
            Json::String(s) => write!(f, "{s:?}"),
            Json::Array(items) => {
                f.write_str("[")?;
                for (i, v) in items.iter().enumerate() {
                    if i > 0 {
                        f.write_str(",")?;
                    }
                    write!(f, "{v}")?;
                }
                f.write_str("]")
            }
            Json::Object(members) => {
                f.write_str("{")?;
                for (i, (k, v)) in members.iter().enumerate() {
                    if i > 0 {
                        f.write_str(",")?;
                    }
                    write!(f, "{k:?}:{v}")?;
                }
                f.write_str("}")
            }
        }
    }
}

/// Why a section is not I-JSON: the rule it breaks, and the byte offset where
/// the reader found it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct NotIJson {
    /// One of `utf-8`, `syntax`, `depth`, `duplicate member`, `surrogate`,
    /// `noncharacter` and `number range`.
    pub(crate) rule: &'static str,
    pub(crate) at: usize,
}

impl fmt::Display for NotIJson {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} at byte {}", self.rule, self.at)
    }
}

/// `raw` read as one I-JSON value, with whitespace allowed around it.
pub(crate) fn parse(raw: &[u8]) -> Result<Json, NotIJson> {
    let text = std::str::from_utf8(raw).map_err(|e| NotIJson { rule: "utf-8", at: e.valid_up_to() })?;
    let mut p = Parser { s: text.as_bytes(), text, i: 0 };
    p.ws();
    let v = p.value(0)?;
    p.ws();
    if p.i != p.s.len() {
        return Err(p.err("syntax"));
    }
    Ok(v)
}

/// Whether `c` is a Unicode noncharacter: U+FDD0 to U+FDEF, and the last two
/// code points of every plane.
pub(crate) fn is_noncharacter(c: char) -> bool {
    let c = u32::from(c);
    (0xFDD0..=0xFDEF).contains(&c) || c & 0xFFFE == 0xFFFE
}

/// Whether a JSON number's magnitude is [`RANGE_LIMIT`] or more, decided on
/// its digits. Written as `0.D × 10^k`, with `D` its significant digits, the
/// number is out of range when `k` exceeds the limit's 309 digits, and when `k`
/// equals it and `D` is at least the limit's digits.
fn out_of_range(literal: &str) -> bool {
    let unsigned = literal.strip_prefix('-').unwrap_or(literal);
    let (mantissa, exponent) = unsigned.split_once(['e', 'E']).unwrap_or((unsigned, ""));
    let (whole, frac) = mantissa.split_once('.').unwrap_or((mantissa, ""));
    let digits: Vec<u8> = whole.bytes().chain(frac.bytes()).collect();
    let lead = digits.iter().take_while(|&&d| d == b'0').count();
    let Some(last) = digits.iter().rposition(|&d| d != b'0') else {
        return false; // zero
    };
    let significant = &digits[lead..=last];
    let (negative, e) = match exponent.as_bytes().first() {
        Some(b'-') => (true, &exponent[1..]),
        Some(b'+') => (false, &exponent[1..]),
        _ => (false, exponent),
    };
    let e = e.trim_start_matches('0');
    // A section holds at most u32::MAX digits, so an exponent past 10^18 decides
    // the rule by its sign alone.
    if e.len() > 18 {
        return !negative;
    }
    let e: i64 = if e.is_empty() { 0 } else { e.parse().expect("at most 18 decimal digits") };
    let k = whole.len() as i64 - lead as i64 + if negative { -e } else { e };
    let limit = RANGE_LIMIT.as_bytes();
    if k != limit.len() as i64 {
        return k > limit.len() as i64;
    }
    for i in 0..significant.len().max(limit.len()) {
        let (a, b) = (significant.get(i).copied().unwrap_or(b'0'), limit.get(i).copied().unwrap_or(b'0'));
        if a != b {
            return a > b;
        }
    }
    true
}

struct Parser<'a> {
    s: &'a [u8],
    text: &'a str,
    i: usize,
}

impl Parser<'_> {
    fn err(&self, rule: &'static str) -> NotIJson {
        NotIJson { rule, at: self.i }
    }

    fn peek(&self) -> Option<u8> {
        self.s.get(self.i).copied()
    }

    fn ws(&mut self) {
        while matches!(self.peek(), Some(b' ' | b'\t' | b'\n' | b'\r')) {
            self.i += 1;
        }
    }

    fn eat(&mut self, b: u8) -> Result<(), NotIJson> {
        if self.peek() == Some(b) {
            self.i += 1;
            Ok(())
        } else {
            Err(self.err("syntax"))
        }
    }

    /// A value inside `depth` arrays and objects.
    fn value(&mut self, depth: usize) -> Result<Json, NotIJson> {
        match self.peek() {
            Some(b'{') => self.object(depth + 1),
            Some(b'[') => self.array(depth + 1),
            Some(b'"') => self.string().map(Json::String),
            Some(b'-' | b'0'..=b'9') => self.number(),
            Some(b't') => self.literal("true", Json::Bool(true)),
            Some(b'f') => self.literal("false", Json::Bool(false)),
            Some(b'n') => self.literal("null", Json::Null),
            _ => Err(self.err("syntax")),
        }
    }

    fn literal(&mut self, word: &str, v: Json) -> Result<Json, NotIJson> {
        if self.s[self.i..].starts_with(word.as_bytes()) {
            self.i += word.len();
            Ok(v)
        } else {
            Err(self.err("syntax"))
        }
    }

    fn object(&mut self, depth: usize) -> Result<Json, NotIJson> {
        if depth > MAX_DEPTH {
            return Err(self.err("depth"));
        }
        self.i += 1;
        let (mut members, mut seen) = (Vec::new(), BTreeSet::new());
        self.ws();
        if self.peek() == Some(b'}') {
            self.i += 1;
            return Ok(Json::Object(members));
        }
        loop {
            self.ws();
            let at = self.i;
            if self.peek() != Some(b'"') {
                return Err(self.err("syntax"));
            }
            let name = self.string()?;
            if !seen.insert(name.clone()) {
                return Err(NotIJson { rule: "duplicate member", at });
            }
            self.ws();
            self.eat(b':')?;
            self.ws();
            let v = self.value(depth)?;
            members.push((name, v));
            self.ws();
            match self.peek() {
                Some(b',') => self.i += 1,
                Some(b'}') => {
                    self.i += 1;
                    return Ok(Json::Object(members));
                }
                _ => return Err(self.err("syntax")),
            }
        }
    }

    fn array(&mut self, depth: usize) -> Result<Json, NotIJson> {
        if depth > MAX_DEPTH {
            return Err(self.err("depth"));
        }
        self.i += 1;
        let mut items = Vec::new();
        self.ws();
        if self.peek() == Some(b']') {
            self.i += 1;
            return Ok(Json::Array(items));
        }
        loop {
            self.ws();
            items.push(self.value(depth)?);
            self.ws();
            match self.peek() {
                Some(b',') => self.i += 1,
                Some(b']') => {
                    self.i += 1;
                    return Ok(Json::Array(items));
                }
                _ => return Err(self.err("syntax")),
            }
        }
    }

    /// Four hex digits after `\u`.
    fn hex4(&mut self) -> Result<u32, NotIJson> {
        let digits = self.s.get(self.i..self.i + 4).ok_or_else(|| self.err("syntax"))?;
        let mut v = 0;
        for &d in digits {
            v = v * 16 + char::from(d).to_digit(16).ok_or_else(|| self.err("syntax"))?;
        }
        self.i += 4;
        Ok(v)
    }

    /// A string, unescaped. No surrogate and no noncharacter, raw or escaped;
    /// an escaped surrogate pair is the character it encodes.
    fn string(&mut self) -> Result<String, NotIJson> {
        self.i += 1;
        let mut out = String::new();
        loop {
            let at = self.i;
            let c = match self.peek() {
                None => return Err(self.err("syntax")),
                Some(b'"') => {
                    self.i += 1;
                    return Ok(out);
                }
                Some(0..=0x1F) => return Err(self.err("syntax")),
                Some(b'\\') => {
                    self.i += 1;
                    let e = self.peek().ok_or_else(|| self.err("syntax"))?;
                    self.i += 1;
                    match e {
                        b'"' => '"',
                        b'\\' => '\\',
                        b'/' => '/',
                        b'b' => '\u{8}',
                        b'f' => '\u{c}',
                        b'n' => '\n',
                        b'r' => '\r',
                        b't' => '\t',
                        b'u' => {
                            let hi = self.hex4()?;
                            let code = match hi {
                                0xD800..=0xDBFF => {
                                    if !self.s[self.i..].starts_with(b"\\u") {
                                        return Err(NotIJson { rule: "surrogate", at });
                                    }
                                    self.i += 2;
                                    let lo = self.hex4()?;
                                    if !(0xDC00..=0xDFFF).contains(&lo) {
                                        return Err(NotIJson { rule: "surrogate", at });
                                    }
                                    0x10000 + ((hi - 0xD800) << 10) + (lo - 0xDC00)
                                }
                                0xDC00..=0xDFFF => return Err(NotIJson { rule: "surrogate", at }),
                                _ => hi,
                            };
                            char::from_u32(code).ok_or(NotIJson { rule: "surrogate", at })?
                        }
                        _ => return Err(NotIJson { rule: "syntax", at }),
                    }
                }
                Some(_) => {
                    let c = self.text[self.i..].chars().next().ok_or_else(|| self.err("syntax"))?;
                    self.i += c.len_utf8();
                    c
                }
            };
            if is_noncharacter(c) {
                return Err(NotIJson { rule: "noncharacter", at });
            }
            out.push(c);
        }
    }

    /// `-? (0 | [1-9][0-9]*) (. [0-9]+)? ([eE] [+-]? [0-9]+)?`, in range.
    fn number(&mut self) -> Result<Json, NotIJson> {
        let start = self.i;
        let digits = |p: &mut Self| {
            let from = p.i;
            while matches!(p.peek(), Some(b'0'..=b'9')) {
                p.i += 1;
            }
            p.i - from
        };
        if self.peek() == Some(b'-') {
            self.i += 1;
        }
        match self.peek() {
            Some(b'0') => self.i += 1,
            Some(b'1'..=b'9') => {
                digits(self);
            }
            _ => return Err(self.err("syntax")),
        }
        if self.peek() == Some(b'.') {
            self.i += 1;
            if digits(self) == 0 {
                return Err(self.err("syntax"));
            }
        }
        if matches!(self.peek(), Some(b'e' | b'E')) {
            self.i += 1;
            if matches!(self.peek(), Some(b'+' | b'-')) {
                self.i += 1;
            }
            if digits(self) == 0 {
                return Err(self.err("syntax"));
            }
        }
        let literal = &self.text[start..self.i];
        if out_of_range(literal) {
            return Err(NotIJson { rule: "number range", at: start });
        }
        Ok(Json::Number(literal.to_string()))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// 2^e in decimal digits, most significant first.
    fn pow2(e: u32) -> Vec<u8> {
        let mut d = vec![1u8]; // least significant first
        for _ in 0..e {
            let mut carry = 0;
            for x in d.iter_mut() {
                let v = *x * 2 + carry;
                (*x, carry) = (v % 10, v / 10);
            }
            if carry > 0 {
                d.push(carry);
            }
        }
        d.reverse();
        d
    }

    /// `a − b` for decimal digit strings with `a ≥ b`, most significant first.
    fn sub(a: &[u8], b: &[u8]) -> String {
        let (mut out, mut borrow) = (Vec::new(), 0i8);
        for i in 0..a.len() {
            let x = a[a.len() - 1 - i] as i8 - borrow - b.len().checked_sub(1 + i).map_or(0, |j| b[j] as i8);
            (borrow, out) = (i8::from(x < 0), [vec![(x + if x < 0 { 10 } else { 0 }) as u8], out].concat());
        }
        let s: String = out.iter().map(|d| char::from(b'0' + d)).collect();
        s.trim_start_matches('0').to_string()
    }

    /// The limit is 2^1024 − 2^970, derived here in decimal, and the standard
    /// library's parse, where it is exact, puts the limit in the same place.
    #[test]
    fn the_range_limit_is_2_1024_minus_2_970() {
        assert_eq!(sub(&pow2(1024), &pow2(970)), RANGE_LIMIT);
        let below = sub(RANGE_LIMIT.as_bytes().iter().map(|b| b - b'0').collect::<Vec<_>>().as_slice(), &[1]);
        assert!(RANGE_LIMIT.parse::<f64>().unwrap().is_infinite());
        assert_eq!(below.parse::<f64>().unwrap(), f64::MAX);
        for t in ["1e308", "1.7976931348623157e308", "1.7976931348623158e308", "1.7976931348623159e308", "2e308", "9e307", "1e-400", RANGE_LIMIT, &below] {
            assert_eq!(out_of_range(t), t.parse::<f64>().unwrap().is_infinite(), "{t}");
        }
    }

    fn rule(text: &str) -> Option<&'static str> {
        parse(text.as_bytes()).err().map(|e| e.rule)
    }

    /// The range rule falls exactly at 2^1024 − 2^970, written as an integer or
    /// with a fraction or exponent, and a number that underflows is in range.
    #[test]
    fn number_range_is_exact() {
        assert_eq!(RANGE_LIMIT.len(), 309);
        let below = format!("{}1", &RANGE_LIMIT[..308]); // RANGE_LIMIT − 1, its last digit 2
        assert_eq!(below.as_bytes()[308], b'1');
        assert_eq!(rule(RANGE_LIMIT), Some("number range"));
        assert_eq!(rule(&format!("-{RANGE_LIMIT}")), Some("number range"));
        assert_eq!(rule(&below), None);
        assert_eq!(rule(&format!("{}.{}e308", &RANGE_LIMIT[..1], &RANGE_LIMIT[1..])), Some("number range"));
        assert_eq!(rule(&format!("{}.{}e308", &below[..1], &below[1..])), None);
        assert_eq!(rule("1.7976931348623158e308"), None);
        assert_eq!(rule("1.7976931348623159e308"), Some("number range"));
        assert_eq!(rule("179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368"), None);
        assert_eq!(rule("1e400"), Some("number range"));
        assert_eq!(rule("1e99999999999999999999999"), Some("number range"));
        assert_eq!(rule("1e-400"), None);
        assert_eq!(rule("0e99999999999999999999999"), None);
        assert_eq!(rule("-0"), None);
        // Long literals whose exponent offsets a run of zeros, past where a
        // float parser may stop reading the exponent; and long exponents.
        let zeros = "0".repeat(655_360);
        assert_eq!(rule(&format!("1{zeros}e-655360")), None);
        assert_eq!(rule(&format!("0.{}1e655669", &zeros[1..])), Some("number range"));
        assert_eq!(rule(&format!("0.{}1e655668", &zeros[1..])), None);
        assert_eq!(rule(&format!("1e{}1", "0".repeat(4300))), None);
        assert_eq!(rule(&format!("1e{}", "9".repeat(30))), Some("number range"));
        assert_eq!(rule(&format!("1e-{}", "9".repeat(30))), None);
        assert_eq!(rule(&format!("0e{}", "9".repeat(30))), None);
    }

    /// Only a number with no sign, fraction or exponent is an unsigned integer,
    /// and only one that fits a `u64` reads as one.
    #[test]
    fn unsigned_integers() {
        let n = |t: &str| parse(t.as_bytes()).unwrap().as_u64();
        assert_eq!(n("0"), Some(0));
        assert_eq!(n("18446744073709551615"), Some(u64::MAX));
        assert_eq!(n("18446744073709551616"), None);
        for t in ["-0", "-1", "2.0", "2e0", "2E0"] {
            assert_eq!(n(t), None, "{t}");
        }
    }

    /// Each rule, refused by name; and what the rules allow.
    #[test]
    fn rules() {
        let deep = |n: usize| format!("{}{}", "[".repeat(n), "]".repeat(n));
        assert_eq!(rule(&deep(MAX_DEPTH)), None);
        assert_eq!(rule(&deep(MAX_DEPTH + 1)), Some("depth"));
        assert_eq!(rule(&format!("{{\"a\":{}}}", deep(MAX_DEPTH - 1))), None);
        assert_eq!(rule(&format!("{{\"a\":{}}}", deep(MAX_DEPTH))), Some("depth"));
        assert_eq!(rule(r#"{"a":1,"a":1}"#), Some("duplicate member"));
        assert_eq!(rule(r#"{"a":1,"\u0061":2}"#), Some("duplicate member"));
        assert_eq!(rule(r#"[{"a":1},{"a":1}]"#), None);
        assert_eq!(rule(r#"{"a":{"b":1,"b":2}}"#), Some("duplicate member"));
        assert_eq!(rule(r#""\ud800""#), Some("surrogate"));
        assert_eq!(rule(r#""\udc00""#), Some("surrogate"));
        assert_eq!(rule(r#""\ud800\u0041""#), Some("surrogate"));
        assert_eq!(rule(r#""\ud83d\ude00""#), None);
        assert_eq!(rule(r#""\ufdd0""#), Some("noncharacter"));
        assert_eq!(rule(r#""\ud83f\udffe""#), Some("noncharacter"));
        assert_eq!(rule("\"\u{ffff}\""), Some("noncharacter"));
        assert_eq!(rule(r#"{"\uffff":1}"#), Some("noncharacter"));
        assert_eq!(rule("\"\u{fffd}\u{fdcf}\u{fdf0}\""), None);
        assert_eq!(parse(b"\"\xff\"").unwrap_err(), NotIJson { rule: "utf-8", at: 1 });
        for bad in ["", "\u{feff}{}", "{} x", "NaN", "Infinity", "01", "1.", ".5", "+1", "1e", "[1,]", "{\"a\"}", "\"\x01\"", "\"\\x\"", "tru", "'a'"] {
            assert_eq!(rule(bad), Some("syntax"), "{bad:?}");
        }
        assert_eq!(parse(b" \t\n\r{ \"a\" : [ 1 , -2.5e-3 , true , false , null ] }\r\n").unwrap().get("a").map(Json::to_string).as_deref(), Some("[1,-2.5e-3,true,false,null]"));
    }
}