chappi_syntax/

canonical.rs

use std::cmp::Ordering;

use sha2::{Digest, Sha256};
use unicode_normalization::UnicodeNormalization;

use crate::{Atom, Document, Form, FormKind};

/// Serializes a document as deterministic, UTF-8 canonical S-expressions.
pub fn canonicalize(document: &Document) -> Vec<u8> {
    let mut forms = document.forms.iter().collect::<Vec<_>>();
    if forms
        .iter()
        .any(|form| head_symbol(form) == Some("chappi-patch"))
    {
        forms.sort_by_key(|form| u8::from(head_symbol(form) != Some("chappi-patch")));
    } else {
        forms.sort_by(|left, right| compare_forms(left, right));
    }

    let mut output = String::new();
    for form in forms {
        write_form(&mut output, form);
        output.push('\n');
    }
    output.into_bytes()
}

/// Returns the SHA-256 digest of [`canonicalize`]'s bytes.
pub fn canonical_hash(document: &Document) -> [u8; 32] {
    Sha256::digest(canonicalize(document)).into()
}

/// Returns whether text is already in the NFC form used by canonical output.
pub fn is_canonical_text(value: &str) -> bool {
    value.nfc().eq(value.chars())
}

/// Returns whether a value canonically parses back as the same symbol atom.
pub fn is_canonical_symbol(value: &str) -> bool {
    is_canonical_text(value)
        && is_symbol_literal(value)
        && !is_integer_literal(value)
        && !is_decimal_literal(value)
}

/// Returns whether an integer literal already has its canonical spelling.
pub fn is_canonical_integer(value: &str) -> bool {
    is_integer_literal(value) && normalize_integer(value) == value
}

/// Returns whether a decimal literal already has its canonical spelling.
pub fn is_canonical_decimal(value: &str) -> bool {
    is_decimal_literal(value) && normalize_decimal(value) == value
}

/// Returns whether canonical serialization and reparsing preserve this atom exactly.
pub fn atom_is_canonical(atom: &Atom) -> bool {
    match atom {
        Atom::Symbol(value) => is_canonical_symbol(value),
        Atom::String(value) => is_canonical_text(value),
        Atom::Integer(value) => is_canonical_integer(value),
        Atom::Decimal(value) => is_canonical_decimal(value),
    }
}

fn compare_forms(left: &Form, right: &Form) -> Ordering {
    let rank = form_rank(left).cmp(&form_rank(right));
    if rank != Ordering::Equal {
        return rank;
    }

    let specific = match form_rank(left) {
        1 => canonical_child(left, 1).cmp(&canonical_child(right, 1)),
        2 => canonical_child(left, 1).cmp(&canonical_child(right, 1)),
        3 => canonical_form(left).cmp(&canonical_form(right)),
        4 => compare_focus(left, right),
        _ => Ordering::Equal,
    };
    if specific == Ordering::Equal {
        canonical_form(left).cmp(&canonical_form(right))
    } else {
        specific
    }
}

fn form_rank(form: &Form) -> u8 {
    match head_symbol(form) {
        Some("chappi") => 0,
        Some(head) if is_node_head(head) => 1,
        Some("revision") => 2,
        Some("rel") => 3,
        Some("focus") => 4,
        _ => 5,
    }
}

fn is_node_head(head: &str) -> bool {
    matches!(
        head,
        "entity"
            | "claim"
            | "evidence"
            | "goal"
            | "constraint"
            | "question"
            | "relationship"
            | "desire"
            | "attention"
            | "association"
            | "tension"
            | "prediction"
            | "perspective"
            | "affect"
            | "metacognition"
    )
}

fn head_symbol(form: &Form) -> Option<&str> {
    let FormKind::List(items) = &form.kind else {
        return None;
    };
    let Some(Form {
        kind: FormKind::Atom(Atom::Symbol(symbol)),
        ..
    }) = items.first()
    else {
        return None;
    };
    Some(symbol)
}

fn canonical_child(form: &Form, index: usize) -> Vec<u8> {
    match &form.kind {
        FormKind::List(items) => items.get(index).map(canonical_form).unwrap_or_default(),
        FormKind::Atom(_) => Vec::new(),
    }
}

fn compare_focus(left: &Form, right: &Form) -> Ordering {
    let stream = canonical_child(left, 1).cmp(&canonical_child(right, 1));
    if stream != Ordering::Equal {
        return stream;
    }
    let sequence = focus_sequence(left);
    let other_sequence = focus_sequence(right);
    compare_integer_literals(sequence.as_deref(), other_sequence.as_deref())
}

fn focus_sequence(form: &Form) -> Option<String> {
    let FormKind::List(items) = &form.kind else {
        return None;
    };
    match items.get(2).map(|form| &form.kind) {
        Some(FormKind::Atom(Atom::Integer(value))) => Some(normalize_integer(value)),
        _ => None,
    }
}

fn compare_integer_literals(left: Option<&str>, right: Option<&str>) -> Ordering {
    match (left, right) {
        (Some(left), Some(right)) => compare_normalized_integers(left, right),
        (Some(_), None) => Ordering::Less,
        (None, Some(_)) => Ordering::Greater,
        (None, None) => Ordering::Equal,
    }
}

fn compare_normalized_integers(left: &str, right: &str) -> Ordering {
    let left_negative = left.starts_with('-');
    let right_negative = right.starts_with('-');
    match (left_negative, right_negative) {
        (true, false) => Ordering::Less,
        (false, true) => Ordering::Greater,
        _ => {
            let left_digits = left.strip_prefix('-').unwrap_or(left);
            let right_digits = right.strip_prefix('-').unwrap_or(right);
            let order = left_digits
                .len()
                .cmp(&right_digits.len())
                .then_with(|| left_digits.cmp(right_digits));
            if left_negative {
                order.reverse()
            } else {
                order
            }
        }
    }
}

fn canonical_form(form: &Form) -> Vec<u8> {
    let mut output = String::new();
    write_form(&mut output, form);
    output.into_bytes()
}

fn write_form(output: &mut String, form: &Form) {
    enum WriteItem<'a> {
        Form(&'a Form),
        Space,
        CloseList,
    }

    let mut pending = vec![WriteItem::Form(form)];
    while let Some(item) = pending.pop() {
        match item {
            WriteItem::Form(form) => match &form.kind {
                FormKind::Atom(atom) => write_atom(output, atom),
                FormKind::List(items) => {
                    output.push('(');
                    pending.push(WriteItem::CloseList);
                    for index in (0..items.len()).rev() {
                        pending.push(WriteItem::Form(&items[index]));
                        if index > 0 {
                            pending.push(WriteItem::Space);
                        }
                    }
                }
            },
            WriteItem::Space => output.push(' '),
            WriteItem::CloseList => output.push(')'),
        }
    }
}

fn write_atom(output: &mut String, atom: &Atom) {
    match atom {
        Atom::Symbol(value) => write_symbol(output, value),
        Atom::Integer(value) if is_integer_literal(value) => {
            output.push_str(&normalize_integer(value));
        }
        Atom::Decimal(value) if is_decimal_literal(value) => {
            output.push_str(&normalize_decimal(value));
        }
        Atom::Integer(value) | Atom::Decimal(value) => write_string(output, value),
        Atom::String(value) => write_string(output, value),
    }
}

fn write_symbol(output: &mut String, value: &str) {
    let value = value.nfc().collect::<String>();
    if is_symbol_literal(&value) {
        output.push_str(&value);
    } else {
        write_string(output, &value);
    }
}

fn is_symbol_literal(value: &str) -> bool {
    !value.is_empty()
        && value.chars().all(|character| {
            !character.is_control() && !matches!(character, ' ' | '\t' | '(' | ')' | '"' | ';')
        })
}

fn is_integer_literal(value: &str) -> bool {
    let digits = value.strip_prefix('-').unwrap_or(value);
    !digits.is_empty() && digits.bytes().all(|byte| byte.is_ascii_digit())
}

fn is_decimal_literal(value: &str) -> bool {
    let unsigned = value.strip_prefix('-').unwrap_or(value);
    let Some((whole, fraction)) = unsigned.split_once('.') else {
        return false;
    };
    !whole.is_empty()
        && !fraction.is_empty()
        && !fraction.contains('.')
        && whole.bytes().all(|byte| byte.is_ascii_digit())
        && fraction.bytes().all(|byte| byte.is_ascii_digit())
}

fn normalize_integer(value: &str) -> String {
    let (negative, digits) = match value.strip_prefix('-') {
        Some(digits) => (true, digits),
        None => (false, value),
    };
    let digits = digits.trim_start_matches('0');
    if digits.is_empty() {
        "0".to_owned()
    } else if negative {
        format!("-{digits}")
    } else {
        digits.to_owned()
    }
}

fn normalize_decimal(value: &str) -> String {
    let (negative, unsigned) = match value.strip_prefix('-') {
        Some(unsigned) => (true, unsigned),
        None => (false, value),
    };
    let Some((whole, fraction)) = unsigned.split_once('.') else {
        return value.to_owned();
    };
    let whole = whole.trim_start_matches('0');
    let whole = if whole.is_empty() { "0" } else { whole };
    let fraction = fraction.trim_end_matches('0');
    if fraction.is_empty() {
        return if negative && whole != "0" {
            format!("-{whole}")
        } else {
            whole.to_owned()
        };
    }
    let prefix = if negative { "-" } else { "" };
    format!("{prefix}{whole}.{fraction}")
}

fn write_string(output: &mut String, value: &str) {
    output.push('"');
    for character in value.nfc() {
        match character {
            '"' => output.push_str("\\\""),
            '\\' => output.push_str("\\\\"),
            '\n' => output.push_str("\\n"),
            '\r' => output.push_str("\\r"),
            '\t' => output.push_str("\\t"),
            character if character.is_control() => {
                use std::fmt::Write as _;
                write!(output, "\\u{{{:x}}}", character as u32)
                    .expect("writing to String cannot fail");
            }
            character => output.push(character),
        }
    }
    output.push('"');
}