Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

46.7 KB
Raw Blame
//! Kiwi, the binary format Figma documents are written in.
//!
//! Every file carries its own schema, so documents written by any version of
//! Figma decode the same way: fields are looked up by name, and fields this
//! engine does not use are skipped without being materialized. A message is a
//! sequence of `(field id, value)` pairs ending in id 0; a struct is its
//! fields in order; integers are LEB128 varints (zigzag for signed); floats
//! are their IEEE bits rotated so small values encode in one byte.

use crate::error::{Result, corrupt};
use std::cell::Cell;
use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hasher};
use std::sync::Arc;

mod flat;
pub use flat::{Flat, FlatShared};
use flat::{FlatVal, Shared};

/// FxHash: field names are short and trusted-shape, so a multiply-rotate
/// hash beats SipHash several times over on the lookups decoding does.
#[derive(Default)]
struct FxHasher(u64);

impl Hasher for FxHasher {
    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        const K: u64 = 0x51_7c_c1_b7_27_22_0a_95;
        let mut chunks = bytes.chunks_exact(8);
        for c in &mut chunks {
            let v = u64::from_le_bytes(c.try_into().unwrap_or_default());
            self.0 = (self.0.rotate_left(5) ^ v).wrapping_mul(K);
        }
        for &b in chunks.remainder() {
            self.0 = (self.0.rotate_left(5) ^ u64::from(b)).wrapping_mul(K);
        }
    }

    #[inline]
    fn finish(&self) -> u64 {
        self.0
    }
}

type FxMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
type FxSet<K> = std::collections::HashSet<K, BuildHasherDefault<FxHasher>>;

/// Ids below this are looked up in a dense table; Figma's are all small.
const DENSE_IDS: u32 = 2048;
const NO_FIELD: u16 = u16::MAX;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Ty {
    Bool,
    Byte,
    Int,
    Uint,
    Float,
    String,
    Int64,
    Uint64,
    Def(u32),
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Kind {
    Enum,
    Struct,
    Message,
}

#[derive(Debug)]
pub struct Field {
    pub name: String,
    pub ty: Ty,
    pub array: bool,
    /// The field id in messages, the value in enums.
    pub id: u32,
    keep: bool,
    /// `ty` with definitions resolved to their kind.
    wire: Wire,
}

/// How a value is laid out: a field's type with the kind of definition it
/// names looked up once, when the schema is read.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Wire {
    Bool,
    Byte,
    Int,
    Uint,
    Float,
    String,
    Int64,
    Uint64,
    Enum(u32),
    Struct(u32),
    Message(u32),
}

#[derive(Debug)]
pub struct Def {
    pub name: String,
    pub kind: Kind,
    pub fields: Vec<Field>,
    /// Message field id (or enum value) → index into `fields`, dense for
    /// small ids, with `sparse_ids` for the rest.
    dense_ids: Vec<u16>,
    sparse_ids: HashMap<u32, u16>,
    by_name: FxMap<Box<str>, u16>,
    /// How many fields decoding keeps (bounds a message's field count).
    kept: u16,
}

#[derive(Debug)]
pub struct Schema {
    pub defs: Vec<Def>,
    by_name: HashMap<String, u32>,
    name_cache: Box<[Cell<NameCacheEntry>]>,
}

/// `((name address, name length, def), field index)`.
type NameCacheEntry = ((usize, usize, u32), Option<u16>);
const NAME_CACHE: usize = 4096;
/// Slots tried before a lookup gives up on the table.
const NAME_PROBES: usize = 8;

/// A bounds-checked cursor over kiwi bytes.
pub struct Reader<'a> {
    pub bytes: &'a [u8],
    pub at: usize,
}

impl<'a> Reader<'a> {
    pub fn new(bytes: &'a [u8]) -> Self {
        Self { bytes, at: 0 }
    }

    #[inline]
    pub fn byte(&mut self) -> Result<u8> {
        let b = *self
            .bytes
            .get(self.at)
            .ok_or_else(|| corrupt("kiwi: unexpected end of data"))?;
        self.at += 1;
        Ok(b)
    }

    #[inline]
    pub fn var_uint(&mut self) -> Result<u32> {
        // Most varints (field ids, lengths, small values) are one byte.
        if let Some(&b) = self.bytes.get(self.at)
            && b < 128
        {
            self.at += 1;
            return Ok(u32::from(b));
        }
        self.var_uint_long()
    }

    fn var_uint_long(&mut self) -> Result<u32> {
        let mut shift = 0;
        let mut result: u32 = 0;
        loop {
            let byte = self.byte()?;
            result |= u32::from(byte & 127).wrapping_shl(shift);
            shift += 7;
            if byte & 128 == 0 || shift >= 35 {
                return Ok(result);
            }
        }
    }

    #[inline]
    pub fn var_int(&mut self) -> Result<i32> {
        let v = self.var_uint()?;
        Ok(((v >> 1) as i32) ^ -((v & 1) as i32))
    }

    #[inline]
    pub fn var_uint64(&mut self) -> Result<u64> {
        let mut shift = 0;
        let mut result: u64 = 0;
        loop {
            let byte = self.byte()?;
            result |= u64::from(byte & 127).wrapping_shl(shift);
            shift += 7;
            if byte & 128 == 0 || shift >= 70 {
                return Ok(result);
            }
        }
    }

    #[inline]
    pub fn float(&mut self) -> Result<f32> {
        let first = self.byte()?;
        if first == 0 {
            return Ok(0.0);
        }
        let rest = self
            .bytes
            .get(self.at..self.at + 3)
            .ok_or_else(|| corrupt("kiwi: truncated float"))?;
        self.at += 3;
        let bits = u32::from(first)
            | (u32::from(rest[0]) << 8)
            | (u32::from(rest[1]) << 16)
            | (u32::from(rest[2]) << 24);
        Ok(f32::from_bits(bits.rotate_left(23)))
    }

    pub fn string(&mut self) -> Result<&'a str> {
        let len = self.bytes[self.at..]
            .iter()
            .position(|&b| b == 0)
            .ok_or_else(|| corrupt("kiwi: unterminated string"))?;
        let s = &self.bytes[self.at..self.at + len];
        self.at += len + 1;
        // Figma writes UTF-8; anything else is replaced rather than rejected.
        Ok(std::str::from_utf8(s).unwrap_or("\u{fffd}"))
    }

    /// [`Reader::var_uint`] without an error value (for skipping).
    #[inline]
    fn var_uint_fast(&mut self) -> Option<u32> {
        if let Some(&b) = self.bytes.get(self.at)
            && b < 128
        {
            self.at += 1;
            return Some(u32::from(b));
        }
        self.var_uint_long().ok()
    }

    /// Steps over a varint of at most `max` bytes; whether there was one.
    #[inline]
    fn skip_var_fast(&mut self, max: usize) -> bool {
        match self.bytes.get(self.at) {
            Some(&b) if b < 128 => {
                self.at += 1;
                true
            }
            Some(_) => self.skip_var(max).is_ok(),
            None => false,
        }
    }

    /// Steps over a float (one byte for zero, else four).
    #[inline]
    fn skip_float(&mut self) -> bool {
        match self.bytes.get(self.at) {
            Some(0) => {
                self.at += 1;
                true
            }
            Some(_) if self.at + 4 <= self.bytes.len() => {
                self.at += 4;
                true
            }
            _ => false,
        }
    }

    /// Steps over a varint of at most `max` bytes.
    #[inline]
    fn skip_var(&mut self, max: usize) -> Result<()> {
        let rest = &self.bytes[self.at.min(self.bytes.len())..];
        match rest.iter().take(max).position(|&b| b < 128) {
            Some(i) => {
                self.at += i + 1;
                Ok(())
            }
            None if rest.len() >= max => {
                self.at += max;
                Ok(())
            }
            None => Err(corrupt("kiwi: unexpected end of data")),
        }
    }

    #[inline]
    fn advance(&mut self, len: usize) -> Result<()> {
        if len > self.bytes.len() - self.at.min(self.bytes.len()) {
            return Err(corrupt("kiwi: unexpected end of data"));
        }
        self.at += len;
        Ok(())
    }

    fn skip_string(&mut self) -> Result<()> {
        let len = self.bytes[self.at..]
            .iter()
            .position(|&b| b == 0)
            .ok_or_else(|| corrupt("kiwi: unterminated string"))?;
        self.at += len + 1;
        Ok(())
    }

    pub fn take(&mut self, len: usize) -> Result<&'a [u8]> {
        let s = self
            .bytes
            .get(self.at..self.at + len)
            .ok_or_else(|| corrupt("kiwi: truncated byte array"))?;
        self.at += len;
        Ok(s)
    }
}

impl Def {
    fn new(name: String, kind: Kind, fields: Vec<Field>) -> Def {
        let mut dense_ids = Vec::new();
        let mut sparse_ids = HashMap::new();
        let mut by_name = FxMap::default();
        for (i, f) in fields.iter().enumerate() {
            if f.id < DENSE_IDS {
                let at = f.id as usize;
                if dense_ids.len() <= at {
                    dense_ids.resize(at + 1, NO_FIELD);
                }
                dense_ids[at] = i as u16;
            } else {
                sparse_ids.insert(f.id, i as u16);
            }
            by_name.entry(f.name.as_str().into()).or_insert(i as u16);
        }
        let kept = fields.len().min(usize::from(u16::MAX)) as u16;
        Def {
            name,
            kind,
            fields,
            dense_ids,
            sparse_ids,
            by_name,
            kept,
        }
    }

    /// The index of the field with wire id (or enum value) `id`.
    #[inline]
    fn index_of_id(&self, id: u32) -> Option<u16> {
        if id < DENSE_IDS {
            match self.dense_ids.get(id as usize) {
                Some(&i) if i != NO_FIELD => Some(i),
                _ => None,
            }
        } else {
            self.sparse_ids.get(&id).copied()
        }
    }

    /// The index of the field named `name`.
    #[inline]
    pub fn index_of(&self, name: &str) -> Option<u16> {
        self.by_name.get(name).copied()
    }

    /// The message field with wire id `id`.
    pub fn field_by_id(&self, id: u32) -> Option<&Field> {
        self.index_of_id(id).map(|i| &self.fields[i as usize])
    }
}

impl Schema {
    /// Reads a binary kiwi schema.
    pub fn decode(bytes: &[u8]) -> Result<Schema> {
        let mut r = Reader::new(bytes);
        let count = r.var_uint()? as usize;
        let mut defs = Vec::with_capacity(count.min(4096));
        for _ in 0..count {
            let name = r.string()?.to_owned();
            let kind = match r.byte()? {
                0 => Kind::Enum,
                1 => Kind::Struct,
                2 => Kind::Message,
                k => return Err(corrupt(format!("kiwi: unknown definition kind {k}"))),
            };
            let field_count = r.var_uint()? as usize;
            let mut fields = Vec::with_capacity(field_count.min(1024));
            for _ in 0..field_count {
                let name = r.string()?.to_owned();
                let ty = match r.var_int()? {
                    -1 => Ty::Bool,
                    -2 => Ty::Byte,
                    -3 => Ty::Int,
                    -4 => Ty::Uint,
                    -5 => Ty::Float,
                    -6 => Ty::String,
                    -7 => Ty::Int64,
                    -8 => Ty::Uint64,
                    i if i >= 0 => Ty::Def(i as u32),
                    i => return Err(corrupt(format!("kiwi: unknown type {i}"))),
                };
                let array = r.byte()? != 0;
                let id = r.var_uint()?;
                fields.push(Field {
                    name,
                    ty,
                    array,
                    id,
                    keep: true,
                    wire: Wire::Bool,
                });
            }
            defs.push(Def::new(name, kind, fields));
        }
        let kinds: Vec<Kind> = defs.iter().map(|d| d.kind).collect();
        for def in &mut defs {
            for field in &mut def.fields {
                field.wire = match field.ty {
                    Ty::Bool => Wire::Bool,
                    Ty::Byte => Wire::Byte,
                    Ty::Int => Wire::Int,
                    Ty::Uint => Wire::Uint,
                    Ty::Float => Wire::Float,
                    Ty::String => Wire::String,
                    Ty::Int64 => Wire::Int64,
                    Ty::Uint64 => Wire::Uint64,
                    Ty::Def(i) => match kinds.get(i as usize) {
                        Some(Kind::Enum) => Wire::Enum(i),
                        Some(Kind::Struct) => Wire::Struct(i),
                        Some(Kind::Message) => Wire::Message(i),
                        None => {
                            return Err(corrupt(format!(
                                "kiwi: {}.{} refers to a missing type",
                                def.name, field.name
                            )));
                        }
                    },
                };
            }
        }
        let by_name = defs
            .iter()
            .enumerate()
            .map(|(i, d)| (d.name.clone(), i as u32))
            .collect();
        let name_cache = (0..NAME_CACHE)
            .map(|_| Cell::new(((0, 0, u32::MAX), None)))
            .collect();
        Ok(Schema {
            defs,
            by_name,
            name_cache,
        })
    }

    pub fn def_index(&self, name: &str) -> Option<u32> {
        self.by_name.get(name).copied()
    }

    pub fn def(&self, index: u32) -> &Def {
        &self.defs[index as usize]
    }

    /// Decodes only the named fields of messages of type `def_name`; the
    /// rest are skipped. Unknown names are ignored, so one allowlist serves
    /// every schema version.
    pub fn keep_only(&mut self, def_name: &str, keep: &[&str]) {
        if let Some(&i) = self.by_name.get(def_name) {
            let def = &mut self.defs[i as usize];
            for field in &mut def.fields {
                field.keep = keep.contains(&field.name.as_str());
            }
            def.kept = def.fields.iter().filter(|f| f.keep).count() as u16;
        }
    }

    /// The index of `def`'s field named `name`. Callers pass the same
    /// literal names over and over, so a table keyed by the name's address
    /// answers most lookups without hashing the name: open addressing, so
    /// names used together never evict each other.
    #[inline]
    pub fn field_index(&self, def: u32, name: &'static str) -> Option<u16> {
        let key = (name.as_ptr() as usize, name.len(), def);
        // Short literals sit a byte apart (`"x"`, `"y"`), so every bit of the
        // address counts: a multiplicative hash, top bits.
        let h = (key.0 as u64 ^ (u64::from(def) << 40) ^ ((key.1 as u64) << 56))
            .wrapping_mul(0x9e37_79b9_7f4a_7c15);
        let first = (h >> (64 - NAME_CACHE.trailing_zeros())) as usize;
        // Static names are never freed, so an address and length name one
        // string: a hit (or a known miss) needs no comparison.
        let cached = self.name_cache[first].get();
        if cached.0 == key {
            return cached.1;
        }
        self.field_index_slow(key, first, name)
    }

    #[cold]
    #[inline(never)]
    fn field_index_slow(
        &self,
        key: (usize, usize, u32),
        first: usize,
        name: &'static str,
    ) -> Option<u16> {
        for probe in 0..NAME_PROBES {
            let slot = &self.name_cache[(first + probe) % NAME_CACHE];
            let cached = slot.get();
            if cached.0 == key {
                return cached.1;
            }
            if cached.0.0 == 0 {
                let index = self.defs[key.2 as usize].index_of(name);
                slot.set((key, index));
                return index;
            }
        }
        self.defs[key.2 as usize].index_of(name)
    }

    /// The name of an enum value, if the schema defines it.
    pub fn enum_name(&self, def: u32, value: u32) -> Option<&str> {
        let def = &self.defs[def as usize];
        def.index_of_id(value)
            .map(|i| def.fields[i as usize].name.as_str())
    }
}

/// A decoded kiwi value. Messages keep only the fields the schema keeps.
#[derive(Debug, Clone)]
pub enum Value {
    Bool(bool),
    Uint(u32),
    Int(i32),
    Float(f32),
    Uint64(u64),
    Int64(i64),
    Str(Box<str>),
    Bytes(Box<[u8]>),
    Enum(u32, u32),
    Msg(Box<Msg>),
    List(Vec<Value>),
    Floats(Box<[f32]>),
    Uints(Box<[u32]>),
}

#[derive(Debug, Clone)]
pub struct Msg {
    pub def: u32,
    /// `(index into the definition's fields, value)`, sorted by index.
    pub fields: Vec<(u16, Value)>,
    /// Bit `index % 128` is set for every field present: most lookups are
    /// for absent fields, and this answers them without touching `fields`.
    present: u128,
}

impl Msg {
    /// An empty message (or struct) of type `def`.
    pub fn new(def: u32) -> Msg {
        Msg {
            def,
            fields: Vec::new(),
            present: 0,
        }
    }

    #[inline]
    fn may_have(&self, index: u16) -> bool {
        self.present & (1u128 << (index & 127)) != 0
    }

    fn refresh_present(&mut self) {
        self.present = self
            .fields
            .iter()
            .fold(0u128, |bits, (i, _)| bits | (1u128 << (i & 127)));
    }

    /// Sets the field named `name`, replacing any value it had. Returns
    /// `false` when the type has no such field (older schemas).
    pub fn set(&mut self, schema: &Schema, name: &str, value: Value) -> bool {
        let Some(index) = schema.def(self.def).index_of(name) else {
            return false;
        };
        match self.fields.binary_search_by_key(&index, |(i, _)| *i) {
            Ok(at) => self.fields[at].1 = value,
            Err(at) => self.fields.insert(at, (index, value)),
        }
        self.refresh_present();
        true
    }

    /// Removes the field named `name`.
    pub fn remove(&mut self, schema: &Schema, name: &str) {
        if let Some(index) = schema.def(self.def).index_of(name) {
            self.fields.retain(|(i, _)| *i != index);
            self.refresh_present();
        }
    }

    /// The value of the field named `name`.
    pub fn get(&self, schema: &Schema, name: &str) -> Option<&Value> {
        let index = schema.def(self.def).index_of(name)?;
        self.fields
            .binary_search_by_key(&index, |(i, _)| *i)
            .ok()
            .map(|at| &self.fields[at].1)
    }
}

/// Writes kiwi primitives.
#[derive(Default)]
pub struct Writer {
    pub bytes: Vec<u8>,
}

impl Writer {
    pub fn byte(&mut self, b: u8) {
        self.bytes.push(b);
    }

    pub fn var_uint(&mut self, mut v: u32) {
        loop {
            let byte = (v & 127) as u8;
            v >>= 7;
            if v == 0 {
                self.byte(byte);
                return;
            }
            self.byte(byte | 128);
        }
    }

    pub fn var_uint64(&mut self, mut v: u64) {
        loop {
            let byte = (v & 127) as u8;
            v >>= 7;
            if v == 0 {
                self.byte(byte);
                return;
            }
            self.byte(byte | 128);
        }
    }

    pub fn var_int(&mut self, v: i32) {
        self.var_uint(((v << 1) ^ (v >> 31)) as u32);
    }

    pub fn float(&mut self, v: f32) {
        // The exponent lands in the low byte; a zero exponent (zero and
        // denormals) is written as a single zero byte, as kiwi does.
        let bits = v.to_bits().rotate_right(23);
        if bits & 255 == 0 {
            self.byte(0);
            return;
        }
        self.bytes.extend_from_slice(&bits.to_le_bytes());
    }

    pub fn string(&mut self, s: &str) {
        // Kiwi strings end at a zero byte, so one cannot contain it.
        self.bytes.extend(s.bytes().filter(|&b| b != 0));
        self.byte(0);
    }
}

impl Schema {
    /// Writes `msg` (a message or struct) in this schema.
    pub fn encode(&self, msg: &Msg, w: &mut Writer) {
        let def = self.def(msg.def);
        match def.kind {
            Kind::Struct => {
                for (i, field) in def.fields.iter().enumerate() {
                    match msg.fields.binary_search_by_key(&(i as u16), |(f, _)| *f) {
                        Ok(at) => self.encode_field(field, &msg.fields[at].1, w),
                        Err(_) => self.encode_zero(field, w),
                    }
                }
            }
            Kind::Message => {
                for (i, value) in &msg.fields {
                    let field = &def.fields[*i as usize];
                    w.var_uint(field.id);
                    self.encode_field(field, value, w);
                }
                w.var_uint(0);
            }
            Kind::Enum => {}
        }
    }

    fn encode_field(&self, field: &Field, value: &Value, w: &mut Writer) {
        if !field.array {
            self.encode_value(field.ty, value, w);
            return;
        }
        match value {
            Value::Bytes(b) => {
                w.var_uint(b.len() as u32);
                w.bytes.extend_from_slice(b);
            }
            Value::Floats(v) => {
                w.var_uint(v.len() as u32);
                for &f in v.iter() {
                    w.float(f);
                }
            }
            Value::Uints(v) => {
                w.var_uint(v.len() as u32);
                for &u in v.iter() {
                    w.var_uint(u);
                }
            }
            Value::List(items) => {
                w.var_uint(items.len() as u32);
                for item in items {
                    self.encode_value(field.ty, item, w);
                }
            }
            _ => w.var_uint(0),
        }
    }

    fn encode_value(&self, ty: Ty, value: &Value, w: &mut Writer) {
        match (ty, value) {
            (Ty::Bool, Value::Bool(b)) => w.byte(u8::from(*b)),
            (Ty::Byte, Value::Uint(v)) => w.byte(*v as u8),
            (Ty::Int, Value::Int(v)) => w.var_int(*v),
            (Ty::Uint, Value::Uint(v)) => w.var_uint(*v),
            (Ty::Float, Value::Float(v)) => w.float(*v),
            (Ty::String, Value::Str(s)) => w.string(s),
            (Ty::Int64, Value::Int64(v)) => w.var_uint64(((v << 1) ^ (v >> 63)) as u64),
            (Ty::Uint64, Value::Uint64(v)) => w.var_uint64(*v),
            (Ty::Def(_), Value::Enum(_, v)) => w.var_uint(*v),
            (Ty::Def(_), Value::Msg(m)) => self.encode(m, w),
            // A value of the wrong shape (a caller bug) writes as zero so
            // the stream stays well formed.
            (ty, _) => self.encode_zero_ty(ty, w),
        }
    }

    fn encode_zero(&self, field: &Field, w: &mut Writer) {
        if field.array {
            w.var_uint(0);
        } else {
            self.encode_zero_ty(field.ty, w);
        }
    }

    fn encode_zero_ty(&self, ty: Ty, w: &mut Writer) {
        match ty {
            Ty::Bool | Ty::Byte | Ty::Float | Ty::String => w.byte(0),
            Ty::Int | Ty::Uint | Ty::Int64 | Ty::Uint64 => w.var_uint(0),
            Ty::Def(i) => match self.def(i).kind {
                Kind::Enum => w.var_uint(0),
                _ => self.encode(&Msg::new(i), w),
            },
        }
    }

    /// An enum value by name, if `def_name` defines it.
    pub fn enum_value(&self, def_name: &str, value: &str) -> Option<Value> {
        let def = self.def_index(def_name)?;
        let field = self.def(def).fields.iter().find(|f| f.name == value)?;
        Some(Value::Enum(def, field.id))
    }

    /// The type of the field `name` of `def` (for building nested values).
    pub fn field_def(&self, def: u32, name: &str) -> Option<u32> {
        let i = self.def(def).index_of(name)?;
        match self.def(def).fields[i as usize].ty {
            Ty::Def(d) => Some(d),
            _ => None,
        }
    }

    /// Encodes the schema itself, in kiwi's binary schema format.
    pub fn encode_schema(&self) -> Vec<u8> {
        let mut w = Writer::default();
        w.var_uint(self.defs.len() as u32);
        for d in &self.defs {
            w.string(&d.name);
            w.byte(match d.kind {
                Kind::Enum => 0,
                Kind::Struct => 1,
                Kind::Message => 2,
            });
            w.var_uint(d.fields.len() as u32);
            for f in &d.fields {
                w.string(&f.name);
                w.var_int(match f.ty {
                    Ty::Bool => -1,
                    Ty::Byte => -2,
                    Ty::Int => -3,
                    Ty::Uint => -4,
                    Ty::Float => -5,
                    Ty::String => -6,
                    Ty::Int64 => -7,
                    Ty::Uint64 => -8,
                    Ty::Def(i) => i as i32,
                });
                w.byte(u8::from(f.array));
                w.var_uint(f.id);
            }
        }
        w.bytes
    }
}

/// Nesting deeper than this is treated as corruption (it would otherwise
/// overflow the stack on hostile input).
const MAX_DEPTH: u32 = 256;

pub struct Decoder<'s> {
    pub schema: &'s Schema,
}

impl<'s> Decoder<'s> {
    pub fn new(schema: &'s Schema) -> Self {
        Self { schema }
    }

    /// Decodes a struct or message of type `def`.
    pub fn decode(&self, r: &mut Reader, def: u32) -> Result<Msg> {
        self.decode_at(r, def, 0)
    }

    fn decode_at(&self, r: &mut Reader, def_index: u32, depth: u32) -> Result<Msg> {
        if depth > MAX_DEPTH {
            return Err(corrupt("kiwi: nesting too deep"));
        }
        let def = self.schema.def(def_index);
        // Most messages set a handful of their fields; start near that.
        let mut fields = Vec::with_capacity(usize::from(def.kept).min(12));
        match def.kind {
            Kind::Struct => {
                for (i, field) in def.fields.iter().enumerate() {
                    if field.keep {
                        fields.push((i as u16, self.field(r, field, depth)?));
                    } else {
                        self.skip_field(r, field, depth)?;
                    }
                }
            }
            Kind::Message => loop {
                let id = r.var_uint()?;
                if id == 0 {
                    break;
                }
                let index = def
                    .index_of_id(id)
                    .ok_or_else(|| corrupt(format!("kiwi: {} has no field {id}", def.name)))?;
                let field = &def.fields[index as usize];
                if field.keep {
                    fields.push((index, self.field(r, field, depth)?));
                } else {
                    self.skip_field(r, field, depth)?;
                }
            },
            Kind::Enum => return Err(corrupt("kiwi: an enum is not a message")),
        }
        // Lookups binary-search by field index. Writers emit fields in
        // declaration order, so this is almost always already true.
        if !fields.is_sorted_by_key(|(i, _)| *i) {
            fields.sort_by_key(|(i, _)| *i);
        }
        let present = fields
            .iter()
            .fold(0u128, |bits, (i, _)| bits | (1u128 << (i & 127)));
        Ok(Msg {
            def: def_index,
            fields,
            present,
        })
    }

    pub fn field(&self, r: &mut Reader, field: &Field, depth: u32) -> Result<Value> {
        if !field.array {
            return self.value(r, field.ty, depth);
        }
        let len = r.var_uint()? as usize;
        match field.ty {
            Ty::Byte => Ok(Value::Bytes(r.take(len)?.into())),
            Ty::Float => {
                let mut v = Vec::with_capacity(len.min(r.bytes.len()));
                for _ in 0..len {
                    v.push(r.float()?);
                }
                Ok(Value::Floats(v.into()))
            }
            Ty::Uint => {
                let mut v = Vec::with_capacity(len.min(r.bytes.len()));
                for _ in 0..len {
                    v.push(r.var_uint()?);
                }
                Ok(Value::Uints(v.into()))
            }
            ty => {
                let mut v = Vec::with_capacity(len.min(r.bytes.len()));
                for _ in 0..len {
                    v.push(self.value(r, ty, depth)?);
                }
                Ok(Value::List(v))
            }
        }
    }

    fn value(&self, r: &mut Reader, ty: Ty, depth: u32) -> Result<Value> {
        Ok(match ty {
            Ty::Bool => Value::Bool(r.byte()? != 0),
            Ty::Byte => Value::Uint(u32::from(r.byte()?)),
            Ty::Int => Value::Int(r.var_int()?),
            Ty::Uint => Value::Uint(r.var_uint()?),
            Ty::Float => Value::Float(r.float()?),
            Ty::String => Value::Str(r.string()?.into()),
            Ty::Int64 => {
                let v = r.var_uint64()?;
                Value::Int64(((v >> 1) as i64) ^ -((v & 1) as i64))
            }
            Ty::Uint64 => Value::Uint64(r.var_uint64()?),
            Ty::Def(i) => match self.schema.def(i).kind {
                Kind::Enum => Value::Enum(i, r.var_uint()?),
                _ => Value::Msg(Box::new(self.decode_at(r, i, depth + 1)?)),
            },
        })
    }

    pub fn skip_field(&self, r: &mut Reader, field: &Field, depth: u32) -> Result<()> {
        if self.skip_field_fast(r, field, depth) {
            Ok(())
        } else {
            Err(corrupt("kiwi: a skipped field is truncated or unknown"))
        }
    }

    pub fn skip(&self, r: &mut Reader, ty: Ty, depth: u32) -> Result<()> {
        let wire = match ty {
            Ty::Bool => Wire::Bool,
            Ty::Byte => Wire::Byte,
            Ty::Int => Wire::Int,
            Ty::Uint => Wire::Uint,
            Ty::Float => Wire::Float,
            Ty::String => Wire::String,
            Ty::Int64 => Wire::Int64,
            Ty::Uint64 => Wire::Uint64,
            Ty::Def(i) => match self.schema.def(i).kind {
                Kind::Enum => Wire::Enum(i),
                Kind::Struct => Wire::Struct(i),
                Kind::Message => Wire::Message(i),
            },
        };
        if self.skip_wire(r, wire, depth) {
            Ok(())
        } else {
            Err(corrupt("kiwi: a skipped value is truncated or unknown"))
        }
    }

    // Skipping walks most of a file's bytes (every field decoding does not
    // keep), so it answers only whether it got through: no error values on
    // the way, and the common one-byte cases first.

    #[inline(always)]
    fn skip_field_fast(&self, r: &mut Reader, field: &Field, depth: u32) -> bool {
        if !field.array {
            return self.skip_wire(r, field.wire, depth);
        }
        let Some(len) = r.var_uint_fast() else {
            return false;
        };
        let len = len as usize;
        match field.wire {
            Wire::Bool | Wire::Byte => r.advance(len).is_ok(),
            Wire::Int | Wire::Uint | Wire::Enum(_) => (0..len).all(|_| r.skip_var_fast(5)),
            Wire::Float => (0..len).all(|_| r.skip_float()),
            wire => (0..len).all(|_| self.skip_wire(r, wire, depth)),
        }
    }

    /// Scalars here; nested values call [`Decoder::skip_def`], so only
    /// those pay for a call (and this inlines into it).
    #[inline(always)]
    fn skip_wire(&self, r: &mut Reader, wire: Wire, depth: u32) -> bool {
        match wire {
            Wire::Bool | Wire::Byte => r.advance(1).is_ok(),
            Wire::Int | Wire::Uint | Wire::Enum(_) => r.skip_var_fast(5),
            Wire::Int64 | Wire::Uint64 => r.skip_var_fast(10),
            Wire::Float => r.skip_float(),
            Wire::String => r.skip_string().is_ok(),
            Wire::Struct(i) => self.skip_def(r, i, false, depth),
            Wire::Message(i) => self.skip_def(r, i, true, depth),
        }
    }

    fn skip_def(&self, r: &mut Reader, i: u32, message: bool, depth: u32) -> bool {
        if depth > MAX_DEPTH {
            return false;
        }
        let def = self.schema.def(i);
        if !message {
            return def
                .fields
                .iter()
                .all(|field| self.skip_field_fast(r, field, depth + 1));
        }
        loop {
            let Some(id) = r.var_uint_fast() else {
                return false;
            };
            if id == 0 {
                return true;
            }
            let Some(index) = def.index_of_id(id) else {
                return false;
            };
            if !self.skip_field_fast(r, &def.fields[index as usize], depth + 1) {
                return false;
            }
        }
    }
}

/// Typed, by-name access to a decoded message: an owned [`Msg`] or one in a
/// [`Flat`] table.
#[derive(Clone, Copy)]
pub struct MsgRef<'a> {
    pub schema: &'a Schema,
    src: Src<'a>,
}

#[derive(Clone, Copy)]
enum Src<'a> {
    Owned(&'a Msg),
    Flat(&'a Flat<'a>, u32),
}

/// A value together with the schema needed to interpret it.
#[derive(Clone, Copy)]
pub struct ValRef<'a> {
    pub schema: &'a Schema,
    value: Val<'a>,
}

#[derive(Clone, Copy)]
enum Val<'a> {
    Owned(&'a Value),
    Flat(&'a Flat<'a>, FlatVal<'a>),
}

/// The items of a list field.
pub struct ListIter<'a> {
    schema: &'a Schema,
    items: Items<'a>,
}

enum Items<'a> {
    Owned(std::slice::Iter<'a, Value>),
    Flat(&'a Flat<'a>, std::slice::Iter<'a, FlatVal<'a>>),
}

impl<'a> Iterator for ListIter<'a> {
    type Item = ValRef<'a>;

    #[inline]
    fn next(&mut self) -> Option<ValRef<'a>> {
        let value = match &mut self.items {
            Items::Owned(it) => Val::Owned(it.next()?),
            Items::Flat(flat, it) => Val::Flat(flat, *it.next()?),
        };
        Some(ValRef {
            schema: self.schema,
            value,
        })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        match &self.items {
            Items::Owned(it) => it.size_hint(),
            Items::Flat(_, it) => it.size_hint(),
        }
    }
}

impl ExactSizeIterator for ListIter<'_> {}

impl<'a> MsgRef<'a> {
    pub fn new(schema: &'a Schema, msg: &'a Msg) -> Self {
        Self {
            schema,
            src: Src::Owned(msg),
        }
    }

    /// Message `slot` of `flat` (from [`Flat::decode`]).
    pub fn flat(schema: &'a Schema, flat: &'a Flat<'a>, slot: u32) -> Self {
        Self {
            schema,
            src: Src::Flat(flat, slot),
        }
    }

    fn def(&self) -> u32 {
        match self.src {
            Src::Owned(m) => m.def,
            Src::Flat(flat, slot) => flat.msgs[slot as usize].def,
        }
    }

    #[inline]
    pub fn get(&self, name: &'static str) -> Option<ValRef<'a>> {
        match self.src {
            Src::Flat(flat, slot) => {
                // Most lookups are for absent fields: answer those from the
                // presence bits before touching the fields.
                let m = &flat.msgs[slot as usize];
                if m.present == 0 {
                    return None;
                }
                let index = self.schema.field_index(m.def, name)?;
                if m.present & (1u128 << (index & 127)) == 0 {
                    return None;
                }
                let fields = &flat.fields[m.start as usize..(m.start + m.len) as usize];
                let at = fields.binary_search_by_key(&index, |f| f.index).ok()?;
                Some(ValRef {
                    schema: self.schema,
                    value: Val::Flat(flat, fields[at].value),
                })
            }
            Src::Owned(msg) => self.get_owned(msg, name),
        }
    }

    fn get_owned(&self, msg: &'a Msg, name: &'static str) -> Option<ValRef<'a>> {
        if msg.fields.is_empty() {
            return None;
        }
        let index = self.schema.field_index(msg.def, name)?;
        if !msg.may_have(index) {
            return None;
        }
        let fields = &msg.fields;
        let at = fields.binary_search_by_key(&index, |(i, _)| *i).ok()?;
        Some(ValRef {
            schema: self.schema,
            value: Val::Owned(&fields[at].1),
        })
    }

    pub fn has(&self, name: &'static str) -> bool {
        self.get(name).is_some()
    }

    pub fn def_name(&self) -> &'a str {
        &self.schema.def(self.def()).name
    }

    pub fn msg(&self, name: &'static str) -> Option<MsgRef<'a>> {
        self.get(name).and_then(|v| v.as_msg())
    }

    pub fn f32(&self, name: &'static str) -> Option<f32> {
        self.get(name).and_then(|v| v.as_f32())
    }

    pub fn u32(&self, name: &'static str) -> Option<u32> {
        self.get(name).and_then(|v| v.as_u32())
    }

    pub fn i32(&self, name: &'static str) -> Option<i32> {
        self.get(name).and_then(|v| v.as_i32())
    }

    pub fn bool(&self, name: &'static str) -> Option<bool> {
        self.get(name).and_then(|v| v.as_bool())
    }

    pub fn str(&self, name: &'static str) -> Option<&'a str> {
        self.get(name).and_then(|v| v.as_str())
    }

    pub fn enum_name(&self, name: &'static str) -> Option<&'a str> {
        self.get(name).and_then(|v| v.as_enum())
    }

    /// `s` as a shared string: messages decoded into one [`Flat`] get one
    /// allocation per distinct string (enum names, mostly) rather than one
    /// per use.
    pub fn intern(&self, s: &str) -> Arc<str> {
        let Src::Flat(flat, _) = self.src else {
            return s.into();
        };
        if let Some(shared) = flat.strings.borrow().get(s) {
            return Arc::clone(shared);
        }
        let shared: Arc<str> = s.into();
        flat.strings.borrow_mut().insert(Arc::clone(&shared));
        shared
    }

    pub fn bytes(&self, name: &'static str) -> Option<&'a [u8]> {
        self.get(name).and_then(|v| v.as_bytes())
    }

    pub fn list(&self, name: &'static str) -> ListIter<'a> {
        match self.get(name) {
            Some(v) => v.as_list(),
            None => ListIter {
                schema: self.schema,
                items: Items::Owned([].iter()),
            },
        }
    }

    pub fn msgs(&self, name: &'static str) -> impl Iterator<Item = MsgRef<'a>> + 'a {
        self.list(name).filter_map(|v| v.as_msg())
    }

    /// `f` of each message in the list `name`, collected straight into one
    /// allocation (a filtered iterator would collect into a `Vec` first and
    /// copy it).
    pub fn collect_msgs<T>(
        &self,
        name: &'static str,
        mut f: impl FnMut(MsgRef<'a>) -> T,
    ) -> Arc<[T]> {
        let schema = self.schema;
        match self.get(name).map(|v| v.value) {
            Some(Val::Owned(Value::List(items)))
                if items.iter().all(|v| matches!(v, Value::Msg(_))) =>
            {
                items
                    .iter()
                    .map(|v| match v {
                        Value::Msg(msg) => f(MsgRef::new(schema, msg)),
                        _ => unreachable!("checked above"),
                    })
                    .collect()
            }
            Some(Val::Flat(flat, FlatVal::List(start, len))) => {
                let items = &flat.items[start as usize..(start + len) as usize];
                if items.iter().all(|v| matches!(v, FlatVal::Msg(_))) {
                    items
                        .iter()
                        .map(|v| match *v {
                            FlatVal::Msg(slot) => f(MsgRef::flat(schema, flat, slot)),
                            _ => unreachable!("checked above"),
                        })
                        .collect()
                } else {
                    self.msgs(name).map(f).collect()
                }
            }
            _ => self.msgs(name).map(f).collect(),
        }
    }

    /// `f()`, which builds something from the field `name` alone, shared
    /// with every other message of this type whose field is encoded the
    /// same (when decoded into a [`Flat`]); `None` when the field is absent.
    /// `f` must depend on nothing but the field's value: it is told apart
    /// from other builders of the same field only by the type it returns.
    pub fn shared<R: Clone + 'static>(
        &self,
        name: &'static str,
        f: impl FnOnce() -> R,
    ) -> Option<R> {
        let (flat, slot) = match self.src {
            Src::Owned(_) => return self.has(name).then(f),
            Src::Flat(flat, slot) => (flat, slot),
        };
        let def = flat.msgs[slot as usize].def;
        let index = self.schema.field_index(def, name)?;
        let span = flat.field_of(slot, index)?.span;
        let key = Shared::key::<R>(def, index, &flat.data[span.0 as usize..span.1 as usize]);
        if let Some(v) = flat.shared.borrow().get(key, def, index, flat.data, span) {
            return Some(v);
        }
        // Built without holding the table: `f` may share nested fields.
        let v = f();
        flat.shared
            .borrow_mut()
            .insert(key, def, index, span, v.clone());
        Some(v)
    }

    pub fn floats(&self, name: &'static str) -> Option<&'a [f32]> {
        match self.get(name)?.value {
            Val::Owned(Value::Floats(v)) => Some(v),
            Val::Flat(flat, FlatVal::Floats(start, len)) => {
                Some(&flat.floats[start as usize..(start + len) as usize])
            }
            _ => None,
        }
    }

    pub fn uints(&self, name: &'static str) -> Option<&'a [u32]> {
        match self.get(name)?.value {
            Val::Owned(Value::Uints(v)) => Some(v),
            Val::Flat(flat, FlatVal::Uints(start, len)) => {
                Some(&flat.uints[start as usize..(start + len) as usize])
            }
            _ => None,
        }
    }
}

impl<'a> ValRef<'a> {
    /// An owned value.
    pub fn new(schema: &'a Schema, value: &'a Value) -> Self {
        Self {
            schema,
            value: Val::Owned(value),
        }
    }

    pub fn as_msg(&self) -> Option<MsgRef<'a>> {
        match self.value {
            Val::Owned(Value::Msg(m)) => Some(MsgRef::new(self.schema, m)),
            Val::Flat(flat, FlatVal::Msg(slot)) => Some(MsgRef::flat(self.schema, flat, slot)),
            _ => None,
        }
    }

    /// The items of a list value (none for other values).
    pub fn as_list(&self) -> ListIter<'a> {
        let items = match self.value {
            Val::Owned(Value::List(items)) => Items::Owned(items.iter()),
            Val::Flat(flat, FlatVal::List(start, len)) => Items::Flat(
                flat,
                flat.items[start as usize..(start + len) as usize].iter(),
            ),
            _ => Items::Owned([].iter()),
        };
        ListIter {
            schema: self.schema,
            items,
        }
    }

    pub fn as_f32(&self) -> Option<f32> {
        match self.value {
            Val::Owned(&Value::Float(f)) | Val::Flat(_, FlatVal::Float(f)) => Some(f),
            Val::Owned(&Value::Int(i)) | Val::Flat(_, FlatVal::Int(i)) => Some(i as f32),
            Val::Owned(&Value::Uint(u)) | Val::Flat(_, FlatVal::Uint(u)) => Some(u as f32),
            _ => None,
        }
    }

    pub fn as_u32(&self) -> Option<u32> {
        match self.value {
            Val::Owned(&Value::Uint(u)) | Val::Flat(_, FlatVal::Uint(u)) => Some(u),
            Val::Owned(&Value::Int(i)) | Val::Flat(_, FlatVal::Int(i)) if i >= 0 => Some(i as u32),
            Val::Owned(&Value::Enum(_, v)) | Val::Flat(_, FlatVal::Enum(_, v)) => Some(v),
            _ => None,
        }
    }

    pub fn as_i32(&self) -> Option<i32> {
        match self.value {
            Val::Owned(&Value::Int(i)) | Val::Flat(_, FlatVal::Int(i)) => Some(i),
            Val::Owned(&Value::Uint(u)) | Val::Flat(_, FlatVal::Uint(u)) => i32::try_from(u).ok(),
            _ => None,
        }
    }

    pub fn as_u64(&self) -> Option<u64> {
        match self.value {
            Val::Owned(&Value::Uint64(u)) | Val::Flat(_, FlatVal::Uint64(u)) => Some(u),
            Val::Owned(&Value::Uint(u)) | Val::Flat(_, FlatVal::Uint(u)) => Some(u64::from(u)),
            _ => None,
        }
    }

    pub fn as_i64(&self) -> Option<i64> {
        match self.value {
            Val::Owned(&Value::Int64(i)) | Val::Flat(_, FlatVal::Int64(i)) => Some(i),
            Val::Owned(&Value::Int(i)) | Val::Flat(_, FlatVal::Int(i)) => Some(i64::from(i)),
            _ => None,
        }
    }

    pub fn as_bool(&self) -> Option<bool> {
        match self.value {
            Val::Owned(&Value::Bool(b)) | Val::Flat(_, FlatVal::Bool(b)) => Some(b),
            _ => None,
        }
    }

    pub fn as_str(&self) -> Option<&'a str> {
        match self.value {
            Val::Owned(Value::Str(s)) => Some(s),
            Val::Flat(_, FlatVal::Str(s)) => Some(s),
            _ => None,
        }
    }

    pub fn as_enum(&self) -> Option<&'a str> {
        match self.value {
            Val::Owned(&Value::Enum(def, v)) | Val::Flat(_, FlatVal::Enum(def, v)) => {
                self.schema.enum_name(def, v)
            }
            _ => None,
        }
    }

    pub fn as_bytes(&self) -> Option<&'a [u8]> {
        match self.value {
            Val::Owned(Value::Bytes(b)) => Some(b),
            Val::Flat(_, FlatVal::Bytes(b)) => Some(b),
            _ => None,
        }
    }
}

struct DefSpec {
    name: String,
    kind: Kind,
    fields: Vec<(String, String, bool)>,
}

fn parse_spec(text: &str) -> Vec<DefSpec> {
    text.lines()
        .filter(|l| !l.trim().is_empty())
        .map(|line| {
            let mut words = line.split_whitespace();
            let kind = match words.next() {
                Some("enum") => Kind::Enum,
                Some("struct") => Kind::Struct,
                _ => Kind::Message,
            };
            let name = words.next().unwrap_or_default().to_owned();
            let fields = words
                .map(|w| match w.split_once(':') {
                    Some((field, ty)) => {
                        let array = ty.ends_with("[]");
                        (
                            field.to_owned(),
                            ty.trim_end_matches("[]").to_owned(),
                            array,
                        )
                    }
                    None => (w.to_owned(), String::new(), false),
                })
                .collect();
            DefSpec { name, kind, fields }
        })
        .collect()
}

/// Encodes a schema written in a compact text form, one type per line:
/// `enum Name A B C`, `struct Name field:type …`, or `message Name
/// field:type[] …`, where types are kiwi primitives or other type names.
pub fn schema_from_text(text: &str) -> Vec<u8> {
    let specs = parse_spec(text);
    let index = |name: &str| {
        specs
            .iter()
            .position(|d| d.name == name)
            .unwrap_or_else(|| panic!("unknown type {name}")) as i32
    };
    let mut w = Writer::default();
    w.var_uint(specs.len() as u32);
    for d in &specs {
        w.string(&d.name);
        w.byte(match d.kind {
            Kind::Enum => 0,
            Kind::Struct => 1,
            Kind::Message => 2,
        });
        w.var_uint(d.fields.len() as u32);
        for (i, (name, ty, array)) in d.fields.iter().enumerate() {
            w.string(name);
            w.var_int(match ty.as_str() {
                "" => 0,
                "bool" => -1,
                "byte" => -2,
                "int" => -3,
                "uint" => -4,
                "float" => -5,
                "string" => -6,
                "int64" => -7,
                "uint64" => -8,
                other => index(other),
            });
            w.byte(u8::from(*array));
            // Message field ids start at 1; enum values at 0.
            w.var_uint(if d.kind == Kind::Enum {
                i as u32
            } else {
                i as u32 + 1
            });
        }
    }
    w.bytes
}

#[cfg(test)]
mod test;