//! Deterministic CBOR (RFC 8949 §4.2), as much of it as Spectra encodes:
//! unsigned integers, byte and text strings, arrays, maps with integer
//! keys, null and booleans. Shortest forms, definite lengths, map keys in
//! ascending order; the decoder refuses anything else, so one value has
//! exactly one encoding and hashing it is meaningful (spec §9.5).

use std::collections::BTreeMap;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
    Uint(u64),
    Bytes(Vec<u8>),
    Text(String),
    Array(Vec<Value>),
    Map(BTreeMap<u64, Value>),
    Bool(bool),
    Null,
}

impl Value {
    pub fn map<const N: usize>(entries: [(u64, Value); N]) -> Value {
        Value::Map(entries.into_iter().collect())
    }
    pub fn as_uint(&self) -> Option<u64> {
        match self {
            Value::Uint(u) => Some(*u),
            _ => None,
        }
    }
    pub fn as_bytes(&self) -> Option<&[u8]> {
        match self {
            Value::Bytes(b) => Some(b),
            _ => None,
        }
    }
    pub fn as_text(&self) -> Option<&str> {
        match self {
            Value::Text(t) => Some(t),
            _ => None,
        }
    }
    pub fn as_array(&self) -> Option<&[Value]> {
        match self {
            Value::Array(a) => Some(a),
            _ => None,
        }
    }
    pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
        match self {
            Value::Map(m) => Some(m),
            _ => None,
        }
    }
    pub fn is_null(&self) -> bool {
        matches!(self, Value::Null)
    }
}

fn head(out: &mut Vec<u8>, major: u8, n: u64) {
    let m = major << 5;
    match n {
        0..=23 => out.push(m | n as u8),
        24..=0xff => out.extend_from_slice(&[m | 24, n as u8]),
        0x100..=0xffff => {
            out.push(m | 25);
            out.extend_from_slice(&(n as u16).to_be_bytes());
        }
        0x1_0000..=0xffff_ffff => {
            out.push(m | 26);
            out.extend_from_slice(&(n as u32).to_be_bytes());
        }
        _ => {
            out.push(m | 27);
            out.extend_from_slice(&n.to_be_bytes());
        }
    }
}

fn put(out: &mut Vec<u8>, v: &Value) {
    match v {
        Value::Uint(n) => head(out, 0, *n),
        Value::Bytes(b) => {
            head(out, 2, b.len() as u64);
            out.extend_from_slice(b);
        }
        Value::Text(t) => {
            head(out, 3, t.len() as u64);
            out.extend_from_slice(t.as_bytes());
        }
        Value::Array(a) => {
            head(out, 4, a.len() as u64);
            for x in a {
                put(out, x);
            }
        }
        // BTreeMap iterates keys ascending, which for unsigned integers is
        // the order of their shortest encodings.
        Value::Map(m) => {
            head(out, 5, m.len() as u64);
            for (k, x) in m {
                head(out, 0, *k);
                put(out, x);
            }
        }
        Value::Bool(false) => out.push(0xf4),
        Value::Bool(true) => out.push(0xf5),
        Value::Null => out.push(0xf6),
    }
}

pub fn encode(v: &Value) -> Vec<u8> {
    let mut out = Vec::new();
    put(&mut out, v);
    out
}

/// Why bytes are not a value Spectra encodes.
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
#[error("malformed CBOR: {0}")]
pub struct Error(pub String);

struct Reader<'a> {
    b: &'a [u8],
    at: usize,
    depth: usize,
}

const MAX_DEPTH: usize = 32;

impl<'a> Reader<'a> {
    fn take(&mut self, n: usize) -> Result<&'a [u8], Error> {
        let end = self.at.checked_add(n).filter(|e| *e <= self.b.len()).ok_or_else(|| Error("truncated".into()))?;
        let s = &self.b[self.at..end];
        self.at = end;
        Ok(s)
    }

    fn head(&mut self) -> Result<(u8, u64), Error> {
        let first = self.take(1)?[0];
        let (major, info) = (first >> 5, first & 0x1f);
        let n = match info {
            0..=23 => info as u64,
            24 => self.take(1)?[0] as u64,
            25 => u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64,
            26 => u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64,
            27 => u64::from_be_bytes(self.take(8)?.try_into().unwrap()),
            _ if major == 7 => return Ok((7, info as u64)),
            _ => return Err(Error("an indefinite length or a reserved form".into())),
        };
        let minimal = match info {
            24 => n >= 24,
            25 => n > 0xff,
            26 => n > 0xffff,
            27 => n > 0xffff_ffff,
            _ => true,
        };
        if !minimal && major != 7 {
            return Err(Error("a length or number not in its shortest form".into()));
        }
        Ok((major, n))
    }

    fn len(&mut self, n: u64) -> Result<usize, Error> {
        let n = usize::try_from(n).map_err(|_| Error("too long".into()))?;
        if n > self.b.len() - self.at {
            return Err(Error("truncated".into()));
        }
        Ok(n)
    }

    fn value(&mut self) -> Result<Value, Error> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(Error("nested too deeply".into()));
        }
        let (major, n) = self.head()?;
        let v = match major {
            0 => Value::Uint(n),
            2 => {
                let l = self.len(n)?;
                Value::Bytes(self.take(l)?.to_vec())
            }
            3 => {
                let l = self.len(n)?;
                Value::Text(String::from_utf8(self.take(l)?.to_vec()).map_err(|_| Error("text that is not UTF-8".into()))?)
            }
            4 => {
                let l = self.len(n)?;
                let mut a = Vec::with_capacity(l);
                for _ in 0..l {
                    a.push(self.value()?);
                }
                Value::Array(a)
            }
            5 => {
                let l = self.len(n)?;
                let mut m = BTreeMap::new();
                let mut last: Option<u64> = None;
                for _ in 0..l {
                    let (km, k) = self.head()?;
                    if km != 0 {
                        return Err(Error("a map key that is not an unsigned integer".into()));
                    }
                    if last.is_some_and(|p| k <= p) {
                        return Err(Error("map keys out of order or repeated".into()));
                    }
                    last = Some(k);
                    m.insert(k, self.value()?);
                }
                Value::Map(m)
            }
            7 => match n {
                20 => Value::Bool(false),
                21 => Value::Bool(true),
                22 => Value::Null,
                _ => return Err(Error("an unsupported simple value or float".into())),
            },
            _ => return Err(Error("a negative integer or a tag".into())),
        };
        self.depth -= 1;
        Ok(v)
    }
}

/// Decode exactly one value, refusing any non-canonical encoding.
pub fn decode(b: &[u8]) -> Result<Value, Error> {
    let mut r = Reader { b, at: 0, depth: 0 };
    let v = r.value()?;
    if r.at != b.len() {
        return Err(Error("bytes after the value".into()));
    }
    Ok(v)
}

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

    #[test]
    fn round_trips_and_known_encodings() {
        let v = Value::map([
            (0, Value::Uint(1)),
            (1, Value::Text("é".into())),
            (2, Value::Bytes(vec![1, 2])),
            (3, Value::Array(vec![Value::Null, Value::Bool(true), Value::Uint(500)])),
            (24, Value::Uint(u64::MAX)),
        ]);
        let b = encode(&v);
        assert_eq!(decode(&b).unwrap(), v);
        assert_eq!(encode(&Value::Uint(23)), [0x17]);
        assert_eq!(encode(&Value::Uint(24)), [0x18, 24]);
        assert_eq!(encode(&Value::Uint(1000)), [0x19, 0x03, 0xe8]);
        assert_eq!(encode(&Value::Text("a".into())), [0x61, b'a']);
    }

    #[test]
    fn refuses_what_is_not_canonical() {
        assert!(decode(&[0x18, 5]).is_err(), "5 in two bytes");
        assert!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]).is_err(), "keys out of order");
        assert!(decode(&[0x5f]).is_err(), "indefinite length");
        assert!(decode(&[0x01, 0x02]).is_err(), "trailing bytes");
        assert!(decode(&[0x5a, 0xff, 0xff, 0xff, 0xff]).is_err(), "truncated");
        assert!(decode(&[0x20]).is_err(), "negative");
        let deep = [0x81u8; 64];
        assert!(decode(&deep).is_err(), "too deep");
    }
}