cbor_ld/

processor.rs

use cbor2::Value;
use cbor2::value::Integer;
use std::collections::{BTreeMap, BTreeSet};

use crate::constants::{
    CBOR_LD_TAG, DEFAULT_REGISTRY_ENTRY_ID, FIRST_CUSTOM_TERM_ID, SECURITY_MULTIBASE, XSD_DATE,
    XSD_DATETIME, keywords_table,
};
use crate::error::{Error, Result};
use crate::table::{ReverseTypeTable, TableKey, TypeTable};

/// Options for JSON-LD to CBOR-LD encoding.
#[derive(Clone, Copy, Debug)]
pub struct EncodeOptions<'a> {
    /// The CBOR-LD registry entry ID. `0` disables semantic compression.
    pub registry_entry_id: u64,
    /// Registry type table material. Required for compressed IDs other than
    /// `1`; ID `1` uses an empty default table.
    pub type_table: Option<&'a TypeTable>,
    /// Whether to use cbor2 deterministic/canonical serialization.
    pub canonical: bool,
}

impl Default for EncodeOptions<'_> {
    fn default() -> Self {
        Self {
            registry_entry_id: 0,
            type_table: None,
            canonical: true,
        }
    }
}

impl<'a> EncodeOptions<'a> {
    /// Creates uncompressed CBOR-LD options using registry entry ID `0`.
    pub fn uncompressed() -> Self {
        Self::default()
    }

    /// Creates compressed CBOR-LD options.
    pub fn compressed(registry_entry_id: u64, type_table: &'a TypeTable) -> Self {
        Self {
            registry_entry_id,
            type_table: Some(type_table),
            canonical: true,
        }
    }
}

/// Options for CBOR-LD to JSON-LD decoding.
#[derive(Clone, Copy, Debug, Default)]
pub struct DecodeOptions<'a> {
    /// Registry type table material. Required for compressed IDs other than
    /// `1`; ID `1` uses an empty default table.
    pub type_table: Option<&'a TypeTable>,
}

/// Encodes a JSON-LD document as CBOR-LD.
///
/// This helper works without a document loader and is sufficient for
/// uncompressed documents or compressed documents that only use inline
/// contexts. Use [`encode_with_loader`] when remote context URLs are present.
pub fn encode(jsonld_document: &Value, options: EncodeOptions<'_>) -> Result<Vec<u8>> {
    encode_with_loader(jsonld_document, options, |url| {
        Err(Error::DocumentLoader(format!(
            "no document loader configured for {url:?}"
        )))
    })
}

/// Encodes a JSON-LD document as CBOR-LD with a document loader.
///
/// The loader receives a context URL and must return the loaded JSON-LD
/// document as a [`Value`] containing an `@context` entry.
pub fn encode_with_loader<F>(
    jsonld_document: &Value,
    options: EncodeOptions<'_>,
    document_loader: F,
) -> Result<Vec<u8>>
where
    F: FnMut(&str) -> Result<Value>,
{
    let registry_entry_id = options.registry_entry_id;
    let payload = if registry_entry_id == 0 {
        jsonld_document.clone()
    } else {
        let type_table = table_for_registry(registry_entry_id, options.type_table)?;
        let mut converter = Converter::new_compression(type_table, document_loader);
        converter.convert(jsonld_document)?
    };

    let tagged = Value::Tag(
        CBOR_LD_TAG,
        Box::new(Value::Array(vec![
            integer(registry_entry_id.into()),
            payload,
        ])),
    );
    if options.canonical {
        cbor2::to_canonical_vec(&tagged).map_err(|e| Error::Cbor(e.to_string()))
    } else {
        cbor2::to_vec(&tagged).map_err(|e| Error::Cbor(e.to_string()))
    }
}

/// Decodes CBOR-LD bytes into a JSON-LD document.
///
/// This helper works without a document loader and is sufficient for
/// uncompressed documents or compressed documents that only use inline
/// contexts. Use [`decode_with_loader`] when remote context URLs are present.
pub fn decode(cborld_bytes: &[u8], options: DecodeOptions<'_>) -> Result<Value> {
    decode_with_loader(cborld_bytes, options, |url| {
        Err(Error::DocumentLoader(format!(
            "no document loader configured for {url:?}"
        )))
    })
}

/// Decodes CBOR-LD bytes into a JSON-LD document with a document loader.
pub fn decode_with_loader<F>(
    cborld_bytes: &[u8],
    options: DecodeOptions<'_>,
    document_loader: F,
) -> Result<Value>
where
    F: FnMut(&str) -> Result<Value>,
{
    cbor2::validate(cborld_bytes).map_err(|e| Error::Cbor(e.to_string()))?;
    let value: Value = cbor2::from_slice(cborld_bytes).map_err(|e| Error::Cbor(e.to_string()))?;
    let (registry_entry_id, payload) = parse_cborld_tag(value)?;
    if registry_entry_id == 0 {
        return Ok(payload);
    }

    let type_table = table_for_registry(registry_entry_id, options.type_table)?;
    let mut converter = Converter::new_decompression(type_table, document_loader);
    converter.convert(&payload)
}

fn table_for_registry(registry_entry_id: u64, type_table: Option<&TypeTable>) -> Result<TypeTable> {
    match (registry_entry_id, type_table) {
        (DEFAULT_REGISTRY_ENTRY_ID, None) => TypeTable::new().normalized(),
        (_, Some(table)) => table.normalized(),
        (id, None) => Err(Error::NoTypeTable(id)),
    }
}

fn parse_cborld_tag(value: Value) -> Result<(u64, Value)> {
    let Value::Tag(tag, boxed) = value else {
        return Err(Error::NotCborld("missing CBOR-LD tag".to_owned()));
    };
    if tag != CBOR_LD_TAG {
        return Err(Error::NotCborld(format!(
            "unexpected tag {tag}, expected {CBOR_LD_TAG}"
        )));
    }
    let Value::Array(mut array) = *boxed else {
        return Err(Error::NotCborld(
            "tagged CBOR-LD item must be an array".to_owned(),
        ));
    };
    if array.len() != 2 {
        return Err(Error::NotCborld(
            "tagged CBOR-LD array must contain registryEntryId and payload".to_owned(),
        ));
    }
    let payload = array.pop().expect("length checked");
    let id = array.pop().expect("length checked");
    let id = non_negative_u64(&id).ok_or_else(|| {
        Error::NotCborld("registryEntryId must be a non-negative integer".to_owned())
    })?;
    Ok((id, payload))
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Strategy {
    Compression,
    Decompression,
}

struct Converter<F>
where
    F: FnMut(&str) -> Result<Value>,
{
    strategy: Strategy,
    type_table: TypeTable,
    reverse_type_table: ReverseTypeTable,
    type_table_encoded_as_bytes: BTreeSet<String>,
    context_loader: ContextLoader<F>,
}

impl<F> Converter<F>
where
    F: FnMut(&str) -> Result<Value>,
{
    fn new_compression(type_table: TypeTable, document_loader: F) -> Self {
        let context_loader = ContextLoader::new(document_loader, false);
        Self {
            strategy: Strategy::Compression,
            reverse_type_table: BTreeMap::new(),
            type_table,
            type_table_encoded_as_bytes: type_table_encoded_as_bytes(),
            context_loader,
        }
    }

    fn new_decompression(type_table: TypeTable, document_loader: F) -> Self {
        let reverse_type_table = type_table.reverse();
        let context_loader = ContextLoader::new(document_loader, true);
        Self {
            strategy: Strategy::Decompression,
            type_table,
            reverse_type_table,
            type_table_encoded_as_bytes: type_table_encoded_as_bytes(),
            context_loader,
        }
    }

    fn convert(&mut self, input: &Value) -> Result<Value> {
        let active_ctx = ActiveContext::new(BTreeMap::new(), None);
        match input {
            Value::Array(items) => items
                .iter()
                .map(|item| self.convert_one(active_ctx.clone(), item))
                .collect::<Result<Vec<_>>>()
                .map(Value::Array),
            _ => self.convert_one(active_ctx, input),
        }
    }

    fn convert_one(&mut self, mut active_ctx: ActiveContext, input: &Value) -> Result<Value> {
        let mut output = Value::Map(Vec::new());
        active_ctx = match self.strategy {
            Strategy::Compression => {
                self.convert_contexts_compression(active_ctx, input, &mut output)?
            }
            Strategy::Decompression => {
                self.convert_contexts_decompression(active_ctx, input, &mut output)?
            }
        };

        let object_types = match self.strategy {
            Strategy::Compression => self.get_object_types_compression(&active_ctx, input)?,
            Strategy::Decompression => self.get_object_types_decompression(&active_ctx, input)?,
        };
        active_ctx =
            active_ctx.apply_type_scoped_contexts(&object_types, &mut self.context_loader)?;

        let entries = match self.strategy {
            Strategy::Compression => self.get_input_entries_compression(&active_ctx, input)?,
            Strategy::Decompression => self.get_input_entries_decompression(&active_ctx, input)?,
        };

        for (term_info, value) in entries {
            let value_active_ctx = active_ctx
                .apply_property_scoped_context(&term_info.term, &mut self.context_loader)?;
            let values: Vec<&Value> = if term_info.plural {
                value
                    .as_array()
                    .ok_or_else(|| {
                        Error::InvalidInput(format!(
                            "plural term {:?} must contain an array",
                            term_info.term
                        ))
                    })?
                    .iter()
                    .collect()
            } else {
                vec![value]
            };

            let mut converted = Vec::with_capacity(values.len());
            for value in values {
                converted.push(self.convert_value(
                    value_active_ctx.clone(),
                    term_info.term_type(),
                    value,
                    &term_info,
                )?);
            }
            let output_values = if term_info.plural {
                Value::Array(converted)
            } else {
                converted.into_iter().next().unwrap_or(Value::Array(vec![]))
            };

            match self.strategy {
                Strategy::Compression => {
                    map_set(&mut output, term_info.term_id.clone(), output_values)?;
                }
                Strategy::Decompression => {
                    map_set(
                        &mut output,
                        Value::Text(term_info.term.clone()),
                        output_values,
                    )?;
                }
            }
        }

        Ok(output)
    }

    fn convert_value(
        &mut self,
        active_ctx: ActiveContext,
        term_type: Option<&str>,
        value: &Value,
        term_info: &TermInfo,
    ) -> Result<Value> {
        if matches!(value, Value::Null) {
            return Ok(Value::Null);
        }

        let converted = match self.strategy {
            Strategy::Compression => self.convert_value_compression(term_type, value, term_info)?,
            Strategy::Decompression => {
                self.convert_value_decompression(term_type, value, term_info)?
            }
        };
        if let Some(value) = converted {
            return Ok(value);
        }

        if let Value::Array(items) = value {
            return items
                .iter()
                .map(|item| self.convert_value(active_ctx.clone(), term_type, item, term_info))
                .collect::<Result<Vec<_>>>()
                .map(Value::Array);
        }

        if matches!(value, Value::Map(_)) {
            return self.convert_one(active_ctx, value);
        }

        Ok(value.clone())
    }

    fn convert_contexts_compression(
        &mut self,
        active_ctx: ActiveContext,
        input: &Value,
        output: &mut Value,
    ) -> Result<ActiveContext> {
        let active_ctx = active_ctx.apply_embedded_contexts(input, &mut self.context_loader)?;
        let Some(context) = map_get_text(input, "@context") else {
            return Ok(active_ctx);
        };

        let is_array = matches!(context, Value::Array(_));
        let contexts: Vec<&Value> = match context {
            Value::Array(items) => items.iter().collect(),
            value => vec![value],
        };
        let mut encoded_contexts = Vec::with_capacity(contexts.len());
        for value in contexts {
            encoded_contexts.push(self.encode_context(value)?);
        }
        let key = integer(if is_array { 1 } else { 0 });
        let value = if is_array {
            Value::Array(encoded_contexts)
        } else {
            encoded_contexts.into_iter().next().unwrap_or(Value::Null)
        };
        map_set(output, key, value)?;
        Ok(active_ctx)
    }

    fn convert_contexts_decompression(
        &mut self,
        active_ctx: ActiveContext,
        input: &Value,
        output: &mut Value,
    ) -> Result<ActiveContext> {
        let singular = map_get(input, &integer(0));
        let plural = map_get(input, &integer(1));
        if singular.is_some() && plural.is_some() {
            return Err(Error::InvalidInput(
                "both singular and plural context IDs were found".to_owned(),
            ));
        }

        if let Some(value) = singular {
            map_set(
                output,
                Value::Text("@context".to_owned()),
                self.decode_context(value)?,
            )?;
        } else if let Some(value) = plural {
            let items = value.as_array().ok_or_else(|| {
                Error::InvalidInput("encoded plural context value must be an array".to_owned())
            })?;
            let mut contexts = Vec::with_capacity(items.len());
            for item in items {
                contexts.push(self.decode_context(item)?);
            }
            map_set(
                output,
                Value::Text("@context".to_owned()),
                Value::Array(contexts),
            )?;
        }

        active_ctx.apply_embedded_contexts(output, &mut self.context_loader)
    }

    fn encode_context(&self, context: &Value) -> Result<Value> {
        let Value::Text(context) = context else {
            return Ok(context.clone());
        };
        if let Some(id) = self
            .type_table
            .subtable("context")
            .and_then(|table| table.get(&TableKey::Text(context.clone())))
        {
            Ok(integer((*id).into()))
        } else {
            Ok(Value::Text(context.clone()))
        }
    }

    fn decode_context(&self, value: &Value) -> Result<Value> {
        if let Some(id) = non_negative_u64(value) {
            let Some(url) = self
                .reverse_type_table
                .get("context")
                .and_then(|table| table.get(&id))
            else {
                return Err(Error::UndefinedCompressedContext(id));
            };
            return Ok(url.to_value());
        }
        Ok(map_to_json_object(value))
    }

    fn get_input_entries_compression<'a>(
        &self,
        active_ctx: &ActiveContext,
        input: &'a Value,
    ) -> Result<Vec<(TermInfo, &'a Value)>> {
        let mut entries = Vec::new();
        let map = input.as_map().ok_or_else(|| {
            Error::InvalidInput("compression input must be a JSON-LD object".to_owned())
        })?;
        let mut keyed = Vec::new();
        for (key, value) in map {
            let Some(term) = key.as_text() else {
                return Err(Error::InvalidInput(
                    "JSON-LD object keys must be text strings".to_owned(),
                ));
            };
            keyed.push((term.to_owned(), value));
        }
        keyed.sort_by(|a, b| a.0.cmp(&b.0));

        for (term, value) in keyed {
            if term == "@context" {
                continue;
            }
            let plural = matches!(value, Value::Array(_));
            let term_id = active_ctx.get_id_for_term(&term, plural, &self.context_loader);
            let def = active_ctx.get_term_definition(&term);
            entries.push((
                TermInfo {
                    term,
                    term_id,
                    plural,
                    def,
                },
                value,
            ));
        }
        Ok(entries)
    }

    fn get_input_entries_decompression<'a>(
        &self,
        active_ctx: &ActiveContext,
        input: &'a Value,
    ) -> Result<Vec<(TermInfo, &'a Value)>> {
        let mut entries = Vec::new();
        let map = input.as_map().ok_or_else(|| {
            Error::InvalidInput("decompression input must be a CBOR-LD map".to_owned())
        })?;
        for (key, value) in map {
            if key == &integer(0) || key == &integer(1) {
                continue;
            }
            let (term, plural) = self.context_loader.get_term_for_id(key)?;
            let def = active_ctx.get_term_definition(&term);
            entries.push((
                TermInfo {
                    term,
                    term_id: key.clone(),
                    plural,
                    def,
                },
                value,
            ));
        }
        entries.sort_by(|a, b| a.0.term.cmp(&b.0.term));
        Ok(entries)
    }

    fn get_object_types_compression(
        &self,
        active_ctx: &ActiveContext,
        input: &Value,
    ) -> Result<BTreeSet<String>> {
        let mut object_types = BTreeSet::new();
        for term in &active_ctx.type_terms {
            if let Some(types) = map_get_text(input, term) {
                match types {
                    Value::Array(items) => {
                        for item in items {
                            if let Some(text) = item.as_text() {
                                object_types.insert(text.to_owned());
                            }
                        }
                    }
                    Value::Text(text) => {
                        object_types.insert(text.clone());
                    }
                    _ => {}
                }
            }
        }
        Ok(object_types)
    }

    fn get_object_types_decompression(
        &mut self,
        active_ctx: &ActiveContext,
        input: &Value,
    ) -> Result<BTreeSet<String>> {
        let mut object_types = BTreeSet::new();
        for term in &active_ctx.type_terms {
            let term_id = active_ctx.get_id_for_term(term, false, &self.context_loader);
            let plural_id = non_negative_u64(&term_id).map(|id| integer((id + 1).into()));
            let Some(value) = map_get(input, &term_id).or_else(|| {
                plural_id
                    .as_ref()
                    .and_then(|plural_id| map_get(input, plural_id))
            }) else {
                continue;
            };

            let term_info = self.context_loader.term_info_for_id(&term_id, active_ctx)?;
            let values: Vec<&Value> = match value {
                Value::Array(items) => items.iter().collect(),
                value => vec![value],
            };
            for value in values {
                let decoded = self
                    .decode_value_with_table(Some("@vocab"), value, &term_info)?
                    .unwrap_or_else(|| value.clone());
                if let Value::Text(text) = decoded {
                    object_types.insert(text);
                }
            }
        }
        Ok(object_types)
    }

    fn convert_value_compression(
        &self,
        term_type: Option<&str>,
        value: &Value,
        term_info: &TermInfo,
    ) -> Result<Option<Value>> {
        if matches!(value, Value::Map(_) | Value::Array(_)) {
            return Ok(None);
        }
        self.encode_value(term_type, value, term_info).map(Some)
    }

    fn convert_value_decompression(
        &mut self,
        term_type: Option<&str>,
        value: &Value,
        term_info: &TermInfo,
    ) -> Result<Option<Value>> {
        if matches!(value, Value::Map(_)) {
            return Ok(None);
        }
        if let Some(decoded) = self.decode_value_with_table(term_type, value, term_info)? {
            return Ok(Some(decoded));
        }
        if !matches!(value, Value::Array(_)) {
            return Ok(Some(value.clone()));
        }
        Ok(None)
    }

    fn encode_value(
        &self,
        term_type: Option<&str>,
        value: &Value,
        term_info: &TermInfo,
    ) -> Result<Value> {
        let table_type = get_table_type(term_info, term_type);
        if table_type == "url" && !matches!(value, Value::Text(_)) {
            return Err(Error::UnsupportedValue(
                "URL values must be text strings".to_owned(),
            ));
        }

        if let Some(subtable) = self.type_table.subtable(&table_type) {
            let key = TableKey::from_value(value)?;
            let mut int_value = subtable.get(&key).map(|id| *id as i128);
            let mut convert_to_bytes = false;
            let mut include_sign = false;

            if int_value.is_some() {
                convert_to_bytes = self.type_table_encoded_as_bytes.contains(&table_type);
            } else if table_type != "none"
                && let Some(n) = value.as_integer()
            {
                int_value = Some(i128::from(n));
                convert_to_bytes = true;
                include_sign = true;
            }

            if let Some(int_value) = int_value {
                if convert_to_bytes {
                    let bytes = if include_sign {
                        bytes_from_int(int_value)?
                    } else {
                        bytes_from_uint(u64::try_from(int_value).map_err(|_| {
                            Error::UnsupportedValue(format!(
                                "negative table ID cannot be encoded as unsigned bytes: {int_value}"
                            ))
                        })?)?
                    };
                    return Ok(Value::Bytes(bytes));
                }
                return Ok(integer(int_value));
            }
        }

        if table_type == "url" {
            if let Some(encoded) = self.encode_url(value)? {
                return Ok(encoded);
            }
        } else if table_type == SECURITY_MULTIBASE {
            if let Some(encoded) = encode_multibase(value) {
                return Ok(encoded);
            }
        } else if table_type == XSD_DATE {
            if let Some(encoded) = encode_xsd_date(value)? {
                return Ok(encoded);
            }
        } else if table_type == XSD_DATETIME
            && let Some(encoded) = encode_xsd_datetime(value)?
        {
            return Ok(encoded);
        }

        Ok(value.clone())
    }

    fn decode_value_with_table(
        &mut self,
        term_type: Option<&str>,
        value: &Value,
        term_info: &TermInfo,
    ) -> Result<Option<Value>> {
        let table_type = get_table_type(term_info, term_type);
        if let Some(subtable) = self.reverse_type_table.get(&table_type) {
            let is_bytes = matches!(value, Value::Bytes(_));
            let table_uses_bytes = self.type_table_encoded_as_bytes.contains(&table_type);
            let mut use_table = false;
            let mut int_value = None;

            if is_bytes && table_uses_bytes {
                let bytes = value.as_bytes().expect("checked");
                use_table = true;
                int_value = Some(uint_from_bytes(bytes)?);
            } else if !table_uses_bytes {
                int_value = non_negative_u64(value);
                use_table = int_value.is_some();
            }

            if use_table {
                let id = int_value.expect("set when table is used");
                let Some(decoded) = subtable.get(&id) else {
                    return Err(Error::UnknownCompressedValue(id));
                };
                return Ok(Some(decoded.to_value()));
            }

            if is_bytes && table_type != "none" {
                let decoded = int_from_bytes(value.as_bytes().expect("checked"))?;
                return Ok(Some(integer(decoded)));
            }
        }

        if table_type == "url" {
            if let Some(decoded) = self.decode_url(value)? {
                return Ok(Some(decoded));
            }
        } else if table_type == SECURITY_MULTIBASE {
            if let Some(decoded) = decode_multibase(value) {
                return Ok(Some(decoded));
            }
        } else if table_type == XSD_DATE {
            if let Some(decoded) = decode_xsd_date(value)? {
                return Ok(Some(decoded));
            }
        } else if table_type == XSD_DATETIME
            && let Some(decoded) = decode_xsd_datetime(value)?
        {
            return Ok(Some(decoded));
        }

        Ok(None)
    }

    fn encode_url(&self, value: &Value) -> Result<Option<Value>> {
        let Value::Text(url) = value else {
            return Ok(None);
        };

        let term_id = self.context_loader.get_id_for_term(url, false);
        if !matches!(term_id, Value::Text(_)) {
            return Ok(Some(term_id));
        }

        if let Some(rest) = url.strip_prefix("https://") {
            return Ok(Some(Value::Array(vec![
                integer(2),
                Value::Text(rest.to_owned()),
            ])));
        }
        if let Some(rest) = url.strip_prefix("http://") {
            return Ok(Some(Value::Array(vec![
                integer(1),
                Value::Text(rest.to_owned()),
            ])));
        }
        if let Some(rest) = url.strip_prefix("urn:uuid:") {
            let encoded = if rest.to_ascii_lowercase() == rest {
                Value::Bytes(parse_uuid_bytes(rest)?)
            } else {
                Value::Text(rest.to_owned())
            };
            return Ok(Some(Value::Array(vec![integer(3), encoded])));
        }
        if let Some(rest) = url.strip_prefix("data:") {
            return Ok(Some(encode_data_url(rest)));
        }
        for (prefix, id) in [("did:v1:nym:", 1024u64), ("did:key:", 1025u64)] {
            if let Some(rest) = url.strip_prefix(prefix) {
                let mut split = rest.splitn(2, '#');
                let authority = split.next().unwrap_or_default();
                let fragment = split.next();
                let mut entries = vec![integer(id.into()), encode_multibase58_part(authority)];
                if let Some(fragment) = fragment {
                    entries.push(encode_multibase58_part(fragment));
                }
                return Ok(Some(Value::Array(entries)));
            }
        }

        Ok(None)
    }

    fn decode_url(&mut self, value: &Value) -> Result<Option<Value>> {
        if matches!(value, Value::Text(_)) {
            return Ok(None);
        }
        if let Value::Array(items) = value {
            let Some(scheme_id) = items.first().and_then(non_negative_u64) else {
                return Err(Error::UnknownCompressedValue(0));
            };
            return match scheme_id {
                1 | 2 => {
                    if items.len() == 2 {
                        if let Some(rest) = items[1].as_text() {
                            let prefix = if scheme_id == 1 {
                                "http://"
                            } else {
                                "https://"
                            };
                            Ok(Some(Value::Text(format!("{prefix}{rest}"))))
                        } else {
                            Err(Error::InvalidInput(
                                "compressed HTTP URL suffix must be text".to_owned(),
                            ))
                        }
                    } else {
                        Err(Error::UnknownCompressedValue(scheme_id))
                    }
                }
                3 => {
                    if items.len() != 2 {
                        return Err(Error::UnknownCompressedValue(scheme_id));
                    }
                    let rest = match &items[1] {
                        Value::Text(text) => text.clone(),
                        Value::Bytes(bytes) => format_uuid(bytes)?,
                        _ => {
                            return Err(Error::InvalidInput(
                                "compressed UUID value must be text or bytes".to_owned(),
                            ));
                        }
                    };
                    Ok(Some(Value::Text(format!("urn:uuid:{rest}"))))
                }
                4 => decode_data_url(items).map(Some),
                1024 | 1025 => decode_base58_did_url(scheme_id, items).map(Some),
                id => Err(Error::UnknownCompressedValue(id)),
            };
        }

        let (term, _) = self.context_loader.get_term_for_id(value)?;
        Ok(Some(Value::Text(term)))
    }
}

#[derive(Clone, Debug)]
struct ActiveContext {
    term_map: BTreeMap<String, TermDef>,
    previous: Option<Box<ActiveContext>>,
    type_terms: Vec<String>,
}

impl ActiveContext {
    fn new(term_map: BTreeMap<String, TermDef>, previous: Option<ActiveContext>) -> Self {
        let mut type_terms = vec!["@type".to_owned()];
        for (term, def) in &term_map {
            if def.id.as_deref() == Some("@type") {
                type_terms.push(term.clone());
            }
        }
        Self {
            term_map,
            previous: previous.map(Box::new),
            type_terms,
        }
    }

    fn apply_embedded_contexts<F>(
        &self,
        input: &Value,
        loader: &mut ContextLoader<F>,
    ) -> Result<Self>
    where
        F: FnMut(&str) -> Result<Value>,
    {
        let term_map = update_term_map(
            self.term_map.clone(),
            map_get_text(input, "@context"),
            loader,
            false,
            false,
        )?;
        Ok(Self::new(term_map, Some(self.clone())))
    }

    fn apply_property_scoped_context<F>(
        &self,
        term: &str,
        loader: &mut ContextLoader<F>,
    ) -> Result<Self>
    where
        F: FnMut(&str) -> Result<Value>,
    {
        let reverted = self.revert_term_map();
        let contexts = self.term_map.get(term).and_then(|def| def.context.as_ref());
        let term_map = update_term_map(reverted, contexts, loader, true, false)?;
        Ok(Self::new(term_map, Some(self.clone())))
    }

    fn apply_type_scoped_contexts<F>(
        &self,
        object_types: &BTreeSet<String>,
        loader: &mut ContextLoader<F>,
    ) -> Result<Self>
    where
        F: FnMut(&str) -> Result<Value>,
    {
        let mut term_map = self.term_map.clone();
        for object_type in object_types {
            let contexts = term_map
                .get(object_type)
                .and_then(|def| def.context.as_ref())
                .cloned();
            term_map = update_term_map(term_map, contexts.as_ref(), loader, false, true)?;
        }
        Ok(Self::new(term_map, Some(self.clone())))
    }

    fn revert_term_map(&self) -> BTreeMap<String, TermDef> {
        let mut new_term_map = BTreeMap::new();
        let mut non_propagating = Vec::new();
        for (term, def) in &self.term_map {
            if def.propagate {
                new_term_map.insert(term.clone(), def.clone());
            } else {
                non_propagating.push(term.clone());
            }
        }

        for term in non_propagating {
            let mut current = self.previous.as_deref();
            while let Some(ctx) = current {
                match ctx.term_map.get(&term) {
                    Some(def) if !def.propagate => {
                        current = ctx.previous.as_deref();
                    }
                    Some(def) => {
                        new_term_map.insert(term.clone(), def.clone());
                        break;
                    }
                    None => break,
                }
            }
        }

        new_term_map
    }

    fn get_id_for_term<F>(&self, term: &str, plural: bool, loader: &ContextLoader<F>) -> Value
    where
        F: FnMut(&str) -> Result<Value>,
    {
        loader.get_id_for_term(term, plural)
    }

    fn get_term_definition(&self, term: &str) -> TermDef {
        self.term_map.get(term).cloned().unwrap_or_default()
    }
}

fn update_term_map<F>(
    mut active_term_map: BTreeMap<String, TermDef>,
    contexts: Option<&Value>,
    loader: &mut ContextLoader<F>,
    property_scope: bool,
    type_scope: bool,
) -> Result<BTreeMap<String, TermDef>>
where
    F: FnMut(&str) -> Result<Value>,
{
    let context_values: Vec<Value> = match contexts {
        Some(Value::Array(items)) => items.clone(),
        Some(value) => vec![value.clone()],
        None => return Ok(active_term_map),
    };

    let allow_protected_override = property_scope;
    let propagate_default = !type_scope;

    for context_value in context_values {
        let entry = loader.load(&context_value)?;
        let context_obj = object_to_string_map(&entry.context)?;
        let propagate = context_obj
            .get("@propagate")
            .and_then(Value::as_bool)
            .unwrap_or(propagate_default);

        let mut new_term_map = entry.term_map.clone();
        for def in new_term_map.values_mut() {
            def.propagate = propagate;
        }

        resolve_curies(&active_term_map, &context_obj, &mut new_term_map)?;

        for (term, active_def) in &active_term_map {
            if let Some(def) = new_term_map.get_mut(term) {
                if active_def.protected {
                    if !allow_protected_override && def.value != active_def.value {
                        return Err(Error::ProtectedTermRedefinition(term.clone()));
                    }
                    let mut protected = active_def.clone();
                    protected.propagate = def.propagate;
                    *def = protected;
                }
            } else if !matches!(context_obj.get(term), Some(Value::Null)) {
                new_term_map.insert(term.clone(), active_def.clone());
            }
        }

        active_term_map = new_term_map;
    }

    Ok(active_term_map)
}

#[derive(Clone, Debug)]
struct ContextEntry {
    context: Value,
    term_map: BTreeMap<String, TermDef>,
}

struct ContextLoader<F>
where
    F: FnMut(&str) -> Result<Value>,
{
    document_loader: F,
    context_map: BTreeMap<String, ContextEntry>,
    next_term_id: u64,
    term_to_id: BTreeMap<String, u64>,
    id_to_term: BTreeMap<u64, String>,
    build_reverse_map: bool,
}

impl<F> ContextLoader<F>
where
    F: FnMut(&str) -> Result<Value>,
{
    fn new(document_loader: F, build_reverse_map: bool) -> Self {
        let term_to_id = keywords_table();
        let id_to_term = if build_reverse_map {
            term_to_id.iter().map(|(k, v)| (*v, k.clone())).collect()
        } else {
            BTreeMap::new()
        };
        Self {
            document_loader,
            context_map: BTreeMap::new(),
            next_term_id: FIRST_CUSTOM_TERM_ID,
            term_to_id,
            id_to_term,
            build_reverse_map,
        }
    }

    fn get_id_for_term(&self, term: &str, plural: bool) -> Value {
        match self.term_to_id.get(term) {
            Some(id) => integer((id + u64::from(plural)).into()),
            None => Value::Text(term.to_owned()),
        }
    }

    fn get_term_for_id(&self, id: &Value) -> Result<(String, bool)> {
        if let Some(term) = id.as_text() {
            return Ok((term.to_owned(), false));
        }
        let Some(id) = non_negative_u64(id) else {
            return Err(Error::InvalidInput(
                "term ID must be text or integer".to_owned(),
            ));
        };
        let plural = (id & 1) == 1;
        let base_id = if plural { id - 1 } else { id };
        let Some(term) = self.id_to_term.get(&base_id) else {
            return Err(Error::UnknownTermId(id));
        };
        Ok((term.clone(), plural))
    }

    fn term_info_for_id(&self, id: &Value, active_ctx: &ActiveContext) -> Result<TermInfo> {
        let (term, plural) = self.get_term_for_id(id)?;
        let def = active_ctx.get_term_definition(&term);
        Ok(TermInfo {
            term,
            term_id: id.clone(),
            plural,
            def,
        })
    }

    fn load(&mut self, context: &Value) -> Result<ContextEntry> {
        match context {
            Value::Text(url) => {
                if let Some(entry) = self.context_map.get(url) {
                    return Ok(entry.clone());
                }
                let document = (self.document_loader)(url)?;
                let loaded_context = map_get_text(&document, "@context").ok_or_else(|| {
                    Error::DocumentLoader(format!(
                        "loaded document for {url:?} does not contain @context"
                    ))
                })?;
                let entry = self.add_context(loaded_context.clone(), Some(url.clone()))?;
                Ok(entry)
            }
            Value::Null => self.add_context(Value::Map(Vec::new()), None),
            Value::Map(_) => self.add_context(context.clone(), None),
            other => Err(Error::InvalidTermDefinition(format!(
                "context must be a URL, object, array item, or null; got {other}"
            ))),
        }
    }

    fn add_context(
        &mut self,
        mut context: Value,
        context_url: Option<String>,
    ) -> Result<ContextEntry> {
        let mut context_obj = object_to_string_map(&context)?;

        if let Some(Value::Text(import_url)) = context_obj.get("@import") {
            let import_entry = if let Some(entry) = self.context_map.get(import_url) {
                entry.clone()
            } else {
                let document = (self.document_loader)(import_url)?;
                let import_context = map_get_text(&document, "@context").ok_or_else(|| {
                    Error::DocumentLoader(format!(
                        "imported document for {import_url:?} does not contain @context"
                    ))
                })?;
                self.add_context(import_context.clone(), Some(import_url.clone()))?
            };
            let mut merged = object_to_string_map(&import_entry.context)?;
            merged.extend(context_obj);
            context = string_map_to_value(merged.clone());
            context_obj = merged;
        }

        let mut term_map = BTreeMap::new();
        let is_protected = context_obj
            .get("@protected")
            .and_then(Value::as_bool)
            .unwrap_or(false);
        let mut keys: Vec<_> = context_obj.keys().cloned().collect();
        keys.sort();
        let keywords = keywords_table();
        for key in keys {
            if keywords.contains_key(&key) || key == "@import" {
                continue;
            }
            let Some(def_value) = context_obj.get(&key) else {
                continue;
            };
            if matches!(def_value, Value::Null) {
                continue;
            }
            let def = TermDef::from_context_value(&key, def_value, is_protected)?;
            term_map.insert(key.clone(), def);

            if !self.term_to_id.contains_key(&key) {
                let id = self.next_term_id;
                self.next_term_id += 2;
                self.term_to_id.insert(key.clone(), id);
                if self.build_reverse_map {
                    self.id_to_term.insert(id, key);
                }
            }
        }

        let entry = ContextEntry { context, term_map };
        if let Some(url) = context_url {
            self.context_map.insert(url, entry.clone());
        }
        Ok(entry)
    }
}

#[derive(Clone, Debug)]
struct TermInfo {
    term: String,
    term_id: Value,
    plural: bool,
    def: TermDef,
}

impl TermInfo {
    fn term_type(&self) -> Option<&str> {
        self.def.type_.as_deref()
    }
}

#[derive(Clone, Debug, Default)]
struct TermDef {
    value: BTreeMap<String, Value>,
    id: Option<String>,
    type_: Option<String>,
    context: Option<Value>,
    protected: bool,
    propagate: bool,
}

impl TermDef {
    fn from_context_value(term: &str, value: &Value, protected: bool) -> Result<Self> {
        let mut object = match value {
            Value::Text(id) => {
                let mut object = BTreeMap::new();
                object.insert("@id".to_owned(), Value::Text(id.clone()));
                object
            }
            Value::Map(_) => object_to_string_map(value)?,
            _ => {
                return Err(Error::InvalidTermDefinition(format!(
                    "term {term:?} must be a string or object"
                )));
            }
        };
        let id = object
            .get("@id")
            .and_then(Value::as_text)
            .map(str::to_owned);
        let type_ = object
            .get("@type")
            .and_then(Value::as_text)
            .map(str::to_owned);
        let context = object.get("@context").cloned();
        object.insert("protected".to_owned(), Value::Bool(protected));
        Ok(Self {
            value: object,
            id,
            type_,
            context,
            protected,
            propagate: true,
        })
    }

    fn set_id(&mut self, id: String) {
        self.id = Some(id.clone());
        self.value.insert("@id".to_owned(), Value::Text(id));
    }

    fn set_type(&mut self, type_: String) {
        self.type_ = Some(type_.clone());
        self.value.insert("@type".to_owned(), Value::Text(type_));
    }
}

fn resolve_curies(
    active_term_map: &BTreeMap<String, TermDef>,
    context: &BTreeMap<String, Value>,
    new_term_map: &mut BTreeMap<String, TermDef>,
) -> Result<()> {
    let terms: Vec<_> = new_term_map.keys().cloned().collect();
    for term in terms {
        let def = new_term_map
            .get_mut(&term)
            .expect("term came from map keys");
        if let Some(id) = def.id.clone() {
            def.set_id(resolve_curie(active_term_map, context, &id));
        } else {
            let resolved = resolve_curie(active_term_map, context, &term);
            if resolved.contains(':') {
                def.set_id(resolved);
            }
        }
        if let Some(type_) = def.type_.clone() {
            def.set_type(resolve_curie(active_term_map, context, &type_));
        }
        if def.id.is_none() {
            return Err(Error::InvalidTermDefinition(format!(
                "the @id value for term {term:?} could not be determined"
            )));
        }
    }
    Ok(())
}

fn resolve_curie(
    active_term_map: &BTreeMap<String, TermDef>,
    context: &BTreeMap<String, Value>,
    possible_curie: &str,
) -> String {
    let Some((prefix, suffix)) = possible_curie.split_once(':') else {
        return possible_curie.to_owned();
    };

    let prefix_id = match context.get(prefix) {
        Some(Value::Text(id)) => Some(id.clone()),
        Some(Value::Map(_)) => object_to_string_map(context.get(prefix).expect("checked"))
            .ok()
            .and_then(|obj| obj.get("@id").and_then(Value::as_text).map(str::to_owned)),
        _ => active_term_map.get(prefix).and_then(|def| def.id.clone()),
    };

    let Some(prefix_id) = prefix_id else {
        return possible_curie.to_owned();
    };
    let resolved = format!("{prefix_id}{suffix}");
    if resolved == possible_curie {
        resolved
    } else {
        resolve_curie(active_term_map, context, &resolved)
    }
}

fn get_table_type(term_info: &TermInfo, term_type: Option<&str>) -> String {
    if term_info.term == "@id"
        || term_info.term == "@type"
        || term_info.def.id.as_deref() == Some("@id")
        || term_info.def.id.as_deref() == Some("@type")
        || term_type == Some("@id")
        || term_type == Some("@vocab")
    {
        "url".to_owned()
    } else {
        term_type.unwrap_or("none").to_owned()
    }
}

fn type_table_encoded_as_bytes() -> BTreeSet<String> {
    ["none", XSD_DATE, XSD_DATETIME, "url"]
        .into_iter()
        .map(str::to_owned)
        .collect()
}

fn bytes_from_uint(int_value: u64) -> Result<Vec<u8>> {
    if int_value < 0xff {
        Ok(vec![int_value as u8])
    } else if int_value < 0xffff {
        Ok((int_value as u16).to_be_bytes().to_vec())
    } else if int_value < 0xffff_ffff {
        Ok((int_value as u32).to_be_bytes().to_vec())
    } else {
        Ok(int_value.to_be_bytes().to_vec())
    }
}

fn bytes_from_int(int_value: i128) -> Result<Vec<u8>> {
    if (-128..0x7f).contains(&int_value) {
        Ok((int_value as i8).to_be_bytes().to_vec())
    } else if (i16::MIN as i128..0x7fff).contains(&int_value) {
        Ok((int_value as i16).to_be_bytes().to_vec())
    } else if (i32::MIN as i128..0x7fff_ffff).contains(&int_value) {
        Ok((int_value as i32).to_be_bytes().to_vec())
    } else if (i64::MIN as i128..=i64::MAX as i128).contains(&int_value) {
        Ok((int_value as i64).to_be_bytes().to_vec())
    } else {
        Err(Error::UnsupportedValue(format!(
            "compression value {int_value} too large"
        )))
    }
}

fn uint_from_bytes(bytes: &[u8]) -> Result<u64> {
    match bytes.len() {
        1 => Ok(bytes[0].into()),
        2 => Ok(u16::from_be_bytes([bytes[0], bytes[1]]).into()),
        4 => Ok(u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]).into()),
        8 => Ok(u64::from_be_bytes([
            bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7],
        ])),
        _ => Err(Error::UnrecognizedBytes(format!("{bytes:?}"))),
    }
}

fn int_from_bytes(bytes: &[u8]) -> Result<i128> {
    match bytes.len() {
        1 => Ok(i8::from_be_bytes([bytes[0]]).into()),
        2 => Ok(i16::from_be_bytes([bytes[0], bytes[1]]).into()),
        4 => Ok(i32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]).into()),
        8 => Ok(i64::from_be_bytes([
            bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7],
        ])
        .into()),
        _ => Err(Error::UnrecognizedBytes(format!("{bytes:?}"))),
    }
}

fn encode_multibase(value: &Value) -> Option<Value> {
    let Value::Text(text) = value else {
        return None;
    };
    let (prefix, suffix) = match text.as_bytes().first().copied() {
        Some(b'z') => (b'z', base58_decode(&text[1..])?),
        Some(b'u') => (b'u', base64url_decode(&text[1..])?),
        Some(b'M') => (b'M', base64_decode_standard(&text[1..])?),
        _ => return None,
    };
    let mut bytes = Vec::with_capacity(1 + suffix.len());
    bytes.push(prefix);
    bytes.extend(suffix);
    Some(Value::Bytes(bytes))
}

fn decode_multibase(value: &Value) -> Option<Value> {
    let Value::Bytes(bytes) = value else {
        return None;
    };
    let (&prefix, suffix) = bytes.split_first()?;
    let text = match prefix {
        b'z' => format!("z{}", base58_encode(suffix)),
        b'u' => format!("u{}", base64url_encode(suffix)),
        b'M' => format!("M{}", base64_encode_standard(suffix)),
        _ => return None,
    };
    Some(Value::Text(text))
}

fn encode_data_url(rest: &str) -> Value {
    if let Some((mediatype, data)) = parse_data_base64(rest)
        && let Some(bytes) = base64_decode_standard(data)
        && base64_encode_standard(&bytes) == data
    {
        return Value::Array(vec![
            integer(4),
            Value::Text(mediatype.to_owned()),
            Value::Bytes(bytes),
        ]);
    }
    Value::Array(vec![integer(4), Value::Text(rest.to_owned())])
}

fn parse_data_base64(rest: &str) -> Option<(&str, &str)> {
    let marker = ";base64,";
    let idx = rest.find(marker)?;
    Some((&rest[..idx], &rest[idx + marker.len()..]))
}

fn decode_data_url(items: &[Value]) -> Result<Value> {
    match items {
        [_, Value::Text(rest)] => Ok(Value::Text(format!("data:{rest}"))),
        [_, Value::Text(mediatype), Value::Bytes(bytes)] => Ok(Value::Text(format!(
            "data:{mediatype};base64,{}",
            base64_encode_standard(bytes)
        ))),
        _ => Err(Error::UnknownCompressedValue(4)),
    }
}

fn encode_multibase58_part(value: &str) -> Value {
    if let Some(rest) = value.strip_prefix('z')
        && let Some(bytes) = base58_decode(rest)
    {
        return Value::Bytes(bytes);
    }
    Value::Text(value.to_owned())
}

fn decode_base58_did_url(scheme_id: u64, items: &[Value]) -> Result<Value> {
    if !(2..=3).contains(&items.len()) {
        return Err(Error::UnknownCompressedValue(scheme_id));
    }
    let prefix = match scheme_id {
        1024 => "did:v1:nym:",
        1025 => "did:key:",
        _ => return Err(Error::UnknownCompressedValue(scheme_id)),
    };
    let mut url = prefix.to_owned();
    url.push_str(&decode_base58_part(&items[1])?);
    if let Some(fragment) = items.get(2) {
        url.push('#');
        url.push_str(&decode_base58_part(fragment)?);
    }
    Ok(Value::Text(url))
}

fn decode_base58_part(value: &Value) -> Result<String> {
    match value {
        Value::Text(text) => Ok(text.clone()),
        Value::Bytes(bytes) => Ok(format!("z{}", base58_encode(bytes))),
        _ => Err(Error::InvalidInput(
            "DID URL component must be text or bytes".to_owned(),
        )),
    }
}

fn encode_xsd_date(value: &Value) -> Result<Option<Value>> {
    let Value::Text(text) = value else {
        return Ok(None);
    };
    if text.contains('T') {
        return Ok(None);
    }
    let Some((year, month, day)) = parse_date(text) else {
        return Ok(None);
    };
    let seconds = days_from_civil(year, month, day) * 86_400;
    if format_date_from_seconds(seconds)? != *text {
        return Ok(Some(Value::Text(text.clone())));
    }
    Ok(Some(integer(seconds.into())))
}

fn decode_xsd_date(value: &Value) -> Result<Option<Value>> {
    let Some(seconds) = integer_i64(value) else {
        return Ok(None);
    };
    Ok(Some(Value::Text(format_date_from_seconds(seconds)?)))
}

fn encode_xsd_datetime(value: &Value) -> Result<Option<Value>> {
    let Value::Text(text) = value else {
        return Ok(None);
    };
    if !text.contains('T') {
        return Ok(None);
    }
    let Some(parsed) = parse_datetime(text) else {
        return Ok(None);
    };
    let seconds = parsed.seconds;
    if parsed.millis == 0 && !parsed.had_millis {
        if format_datetime(seconds, 0, false)? != *text {
            return Ok(Some(Value::Text(text.clone())));
        }
        return Ok(Some(integer(seconds.into())));
    }
    if format_datetime(seconds, parsed.millis, true)? != *text {
        return Ok(Some(Value::Text(text.clone())));
    }
    Ok(Some(Value::Array(vec![
        integer(seconds.into()),
        integer(parsed.millis.into()),
    ])))
}

fn decode_xsd_datetime(value: &Value) -> Result<Option<Value>> {
    if let Some(seconds) = integer_i64(value) {
        return Ok(Some(Value::Text(format_datetime(seconds, 0, false)?)));
    }
    if let Value::Array(items) = value
        && items.len() == 2
        && let (Some(seconds), Some(millis)) = (integer_i64(&items[0]), non_negative_u64(&items[1]))
    {
        return Ok(Some(Value::Text(format_datetime(
            seconds,
            u16::try_from(millis).map_err(|_| {
                Error::InvalidInput("dateTime millisecond value too large".to_owned())
            })?,
            true,
        )?)));
    }
    Ok(None)
}

#[derive(Clone, Copy)]
struct ParsedDateTime {
    seconds: i64,
    millis: u16,
    had_millis: bool,
}

fn parse_date(text: &str) -> Option<(i32, u32, u32)> {
    if text.len() != 10 {
        return None;
    }
    let year = text[0..4].parse().ok()?;
    let month = text[5..7].parse().ok()?;
    let day = text[8..10].parse().ok()?;
    if &text[4..5] != "-" || &text[7..8] != "-" {
        return None;
    }
    if !(1..=12).contains(&month) || !(1..=days_in_month(year, month)).contains(&day) {
        return None;
    }
    Some((year, month, day))
}

fn parse_datetime(text: &str) -> Option<ParsedDateTime> {
    if !text.ends_with('Z') || text.len() < 20 {
        return None;
    }
    let (date, time) = text[..text.len() - 1].split_once('T')?;
    let (year, month, day) = parse_date(date)?;
    let hour: u32 = time[0..2].parse().ok()?;
    let minute: u32 = time[3..5].parse().ok()?;
    let second: u32 = time[6..8].parse().ok()?;
    if &time[2..3] != ":" || &time[5..6] != ":" {
        return None;
    }
    if hour > 23 || minute > 59 || second > 59 {
        return None;
    }
    let (millis, had_millis) = if time.len() == 8 {
        (0, false)
    } else if time.len() == 12 && &time[8..9] == "." {
        (time[9..12].parse().ok()?, true)
    } else {
        return None;
    };
    let days = days_from_civil(year, month, day);
    let seconds = days * 86_400 + i64::from(hour * 3600 + minute * 60 + second);
    Some(ParsedDateTime {
        seconds,
        millis,
        had_millis,
    })
}

fn format_date_from_seconds(seconds: i64) -> Result<String> {
    if seconds % 86_400 != 0 {
        return Err(Error::InvalidInput(
            "xsd:date seconds are not aligned to midnight UTC".to_owned(),
        ));
    }
    let (year, month, day) = civil_from_days(seconds.div_euclid(86_400));
    Ok(format!("{year:04}-{month:02}-{day:02}"))
}

fn format_datetime(seconds: i64, millis: u16, include_millis: bool) -> Result<String> {
    if millis > 999 {
        return Err(Error::InvalidInput(
            "dateTime millisecond value must be <= 999".to_owned(),
        ));
    }
    let days = seconds.div_euclid(86_400);
    let seconds_of_day = seconds.rem_euclid(86_400);
    let (year, month, day) = civil_from_days(days);
    let hour = seconds_of_day / 3600;
    let minute = (seconds_of_day % 3600) / 60;
    let second = seconds_of_day % 60;
    if include_millis {
        Ok(format!(
            "{year:04}-{month:02}-{day:02}T{hour:02}:{minute:02}:{second:02}.{millis:03}Z"
        ))
    } else {
        Ok(format!(
            "{year:04}-{month:02}-{day:02}T{hour:02}:{minute:02}:{second:02}Z"
        ))
    }
}

fn days_in_month(year: i32, month: u32) -> u32 {
    match month {
        1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
        4 | 6 | 9 | 11 => 30,
        2 if is_leap_year(year) => 29,
        2 => 28,
        _ => 0,
    }
}

fn is_leap_year(year: i32) -> bool {
    (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
}

fn days_from_civil(year: i32, month: u32, day: u32) -> i64 {
    let year = year - i32::from(month <= 2);
    let era = if year >= 0 { year } else { year - 399 } / 400;
    let yoe = year - era * 400;
    let month = month as i32;
    let doy = (153 * (month + if month > 2 { -3 } else { 9 }) + 2) / 5 + day as i32 - 1;
    let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
    i64::from(era * 146_097 + doe - 719_468)
}

fn civil_from_days(days: i64) -> (i32, u32, u32) {
    let z = days + 719_468;
    let era = if z >= 0 { z } else { z - 146_096 } / 146_097;
    let doe = z - era * 146_097;
    let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365;
    let mut year = yoe + era * 400;
    let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
    let mp = (5 * doy + 2) / 153;
    let day = doy - (153 * mp + 2) / 5 + 1;
    let month = mp + if mp < 10 { 3 } else { -9 };
    year += i64::from(month <= 2);
    (year as i32, month as u32, day as u32)
}

fn parse_uuid_bytes(text: &str) -> Result<Vec<u8>> {
    if text.len() != 36 {
        return Err(Error::UnsupportedValue(format!("invalid UUID {text:?}")));
    }
    for idx in [8, 13, 18, 23] {
        if text.as_bytes()[idx] != b'-' {
            return Err(Error::UnsupportedValue(format!("invalid UUID {text:?}")));
        }
    }
    let mut compact = String::with_capacity(32);
    for (idx, ch) in text.chars().enumerate() {
        if [8, 13, 18, 23].contains(&idx) {
            continue;
        }
        compact.push(ch);
    }
    let mut bytes = Vec::with_capacity(16);
    for idx in (0..32).step_by(2) {
        let byte = u8::from_str_radix(&compact[idx..idx + 2], 16)
            .map_err(|_| Error::UnsupportedValue(format!("invalid UUID {text:?}")))?;
        bytes.push(byte);
    }
    Ok(bytes)
}

fn format_uuid(bytes: &[u8]) -> Result<String> {
    if bytes.len() != 16 {
        return Err(Error::InvalidInput(
            "compressed UUID bytes must be exactly 16 bytes".to_owned(),
        ));
    }
    let hex = bytes.iter().map(|b| format!("{b:02x}")).collect::<String>();
    Ok(format!(
        "{}-{}-{}-{}-{}",
        &hex[0..8],
        &hex[8..12],
        &hex[12..16],
        &hex[16..20],
        &hex[20..32]
    ))
}

const BASE58_ALPHABET: &[u8; 58] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

fn base58_decode(text: &str) -> Option<Vec<u8>> {
    let mut bytes = vec![0u8];
    for ch in text.bytes() {
        let value = BASE58_ALPHABET.iter().position(|&b| b == ch)? as u32;
        let mut carry = value;
        for byte in bytes.iter_mut().rev() {
            let x = u32::from(*byte) * 58 + carry;
            *byte = (x & 0xff) as u8;
            carry = x >> 8;
        }
        while carry > 0 {
            bytes.insert(0, (carry & 0xff) as u8);
            carry >>= 8;
        }
    }
    for ch in text.bytes().take_while(|&b| b == b'1') {
        let _ = ch;
        bytes.insert(0, 0);
    }
    while bytes.len() > 1 && bytes[0] == 0 && !text.starts_with('1') {
        bytes.remove(0);
    }
    Some(bytes)
}

fn base58_encode(bytes: &[u8]) -> String {
    if bytes.is_empty() {
        return String::new();
    }
    let mut digits = vec![0u8];
    for byte in bytes {
        let mut carry = u32::from(*byte);
        for digit in digits.iter_mut().rev() {
            let x = u32::from(*digit) * 256 + carry;
            *digit = (x % 58) as u8;
            carry = x / 58;
        }
        while carry > 0 {
            digits.insert(0, (carry % 58) as u8);
            carry /= 58;
        }
    }
    let mut out = String::new();
    for _ in bytes.iter().take_while(|&&b| b == 0) {
        out.push('1');
    }
    for digit in digits {
        out.push(BASE58_ALPHABET[digit as usize] as char);
    }
    out
}

const BASE64_STANDARD: &[u8; 64] =
    b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
const BASE64_URL: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";

fn base64_encode_standard(bytes: &[u8]) -> String {
    base64_encode(bytes, BASE64_STANDARD, true)
}

fn base64url_encode(bytes: &[u8]) -> String {
    base64_encode(bytes, BASE64_URL, false)
}

fn base64_encode(bytes: &[u8], alphabet: &[u8; 64], pad: bool) -> String {
    let mut out = String::new();
    for chunk in bytes.chunks(3) {
        let b0 = chunk[0];
        let b1 = *chunk.get(1).unwrap_or(&0);
        let b2 = *chunk.get(2).unwrap_or(&0);
        let n = (u32::from(b0) << 16) | (u32::from(b1) << 8) | u32::from(b2);
        out.push(alphabet[((n >> 18) & 0x3f) as usize] as char);
        out.push(alphabet[((n >> 12) & 0x3f) as usize] as char);
        if chunk.len() > 1 {
            out.push(alphabet[((n >> 6) & 0x3f) as usize] as char);
        } else if pad {
            out.push('=');
        }
        if chunk.len() > 2 {
            out.push(alphabet[(n & 0x3f) as usize] as char);
        } else if pad {
            out.push('=');
        }
    }
    out
}

fn base64_decode_standard(text: &str) -> Option<Vec<u8>> {
    if !text.len().is_multiple_of(4) {
        return None;
    }
    base64_decode(text, BASE64_STANDARD, true)
}

fn base64url_decode(text: &str) -> Option<Vec<u8>> {
    base64_decode(text, BASE64_URL, false)
}

fn base64_decode(text: &str, alphabet: &[u8; 64], padded: bool) -> Option<Vec<u8>> {
    let mut values = Vec::new();
    let mut padding = 0usize;
    for (idx, ch) in text.bytes().enumerate() {
        if ch == b'=' {
            if !padded {
                return None;
            }
            padding += 1;
            if idx < text.len().saturating_sub(2) {
                return None;
            }
            values.push(0);
        } else {
            if padding > 0 {
                return None;
            }
            values.push(alphabet.iter().position(|&b| b == ch)? as u8);
        }
    }
    if !padded {
        while values.len() % 4 != 0 {
            values.push(0);
            padding += 1;
        }
    }
    if values.len() % 4 != 0 || padding > 2 {
        return None;
    }

    let mut out = Vec::new();
    for chunk in values.chunks(4) {
        let n = (u32::from(chunk[0]) << 18)
            | (u32::from(chunk[1]) << 12)
            | (u32::from(chunk[2]) << 6)
            | u32::from(chunk[3]);
        out.push(((n >> 16) & 0xff) as u8);
        out.push(((n >> 8) & 0xff) as u8);
        out.push((n & 0xff) as u8);
    }
    for _ in 0..padding {
        out.pop();
    }
    Some(out)
}

fn map_get_text<'a>(value: &'a Value, key: &str) -> Option<&'a Value> {
    map_get(value, &Value::Text(key.to_owned()))
}

fn map_get<'a>(value: &'a Value, key: &Value) -> Option<&'a Value> {
    let Value::Map(map) = value else {
        return None;
    };
    map.iter()
        .find_map(|(k, v)| if k == key { Some(v) } else { None })
}

fn map_set(map_value: &mut Value, key: Value, value: Value) -> Result<()> {
    let Value::Map(map) = map_value else {
        return Err(Error::InvalidInput("output must be a map".to_owned()));
    };
    if let Some((_, existing)) = map.iter_mut().find(|(k, _)| k == &key) {
        *existing = value;
    } else {
        map.push((key, value));
    }
    Ok(())
}

fn map_to_json_object(value: &Value) -> Value {
    match value {
        Value::Array(items) => Value::Array(items.iter().map(map_to_json_object).collect()),
        Value::Map(map) => Value::Map(
            map.iter()
                .map(|(key, value)| (map_to_json_object(key), map_to_json_object(value)))
                .collect(),
        ),
        other => other.clone(),
    }
}

fn object_to_string_map(value: &Value) -> Result<BTreeMap<String, Value>> {
    let Value::Map(map) = value else {
        return Err(Error::InvalidTermDefinition(
            "context must be an object".to_owned(),
        ));
    };
    let mut out = BTreeMap::new();
    for (key, value) in map {
        let Some(key) = key.as_text() else {
            return Err(Error::InvalidTermDefinition(
                "context keys must be text strings".to_owned(),
            ));
        };
        out.insert(key.to_owned(), value.clone());
    }
    Ok(out)
}

fn string_map_to_value(map: BTreeMap<String, Value>) -> Value {
    Value::Map(
        map.into_iter()
            .map(|(key, value)| (Value::Text(key), value))
            .collect(),
    )
}

fn integer(value: i128) -> Value {
    Value::Integer(Integer::try_from(value).expect("integer value fits CBOR major type 0/1"))
}

fn non_negative_u64(value: &Value) -> Option<u64> {
    let n = value.as_integer()?;
    u64::try_from(n).ok()
}

fn integer_i64(value: &Value) -> Option<i64> {
    let n = value.as_integer()?;
    i64::try_from(n).ok()
}