meta-language 1.0.0

//! The Rust emitter: writes a checked program as Rust with its translation contract.
//!
//! Naturals and integers are `ml::Big`, an unbounded integer the translation
//! carries in its own prelude, so no value is ever narrowed; machine integers
//! stay Rust machine integers with checked arithmetic, which panics exactly
//! where the source aborts; a JavaScript Number is an `f64`, printed by
//! `ml_number::js_number` exactly as JavaScript prints it. Data types are enums
//! whose data-typed fields are boxed. Every value is owned: a variable is cloned where it is consumed.
//! Theorems cannot be proved in Rust: each becomes an executable property,
//! checked over a bounded domain by `--ml-check-theorems`, while the proof
//! stays discharged by the source kernel.
//!
//! Mirrors `js/src/translation/emit-rust.js`.

use std::collections::BTreeSet;
use std::fmt::Write as _;

use super::Language;
use super::decimal::Decimal;
use super::diagnostics::{Result, unsupported};
use super::emit_common::{CtorStyle, EmitOptions, EmitState, Emitted};
use super::ir::{
    Binder, ByZero, Decl, Effect, Expr, LitValue, Node, Pattern, Program, Prop, Semantics,
    rename_function, rename_main, rename_theorem, tail_loop,
};
use super::surface::{BinaryOp, Flavor, Rounding, UnaryOp};
use super::types::Type;

mod arrays;
mod declarations;
mod expressions;
mod math;
mod number_prelude;

use self::arrays::ARRAY_PRELUDE;
use self::math::MATH_PRELUDE;
use self::number_prelude::NUMBER_PRELUDE;

const KEYWORDS: &[&str] = &[
    "as",
    "break",
    "const",
    "continue",
    "crate",
    "else",
    "enum",
    "extern",
    "false",
    "fn",
    "for",
    "if",
    "impl",
    "in",
    "let",
    "loop",
    "match",
    "mod",
    "move",
    "mut",
    "pub",
    "ref",
    "return",
    "self",
    "Self",
    "static",
    "struct",
    "super",
    "trait",
    "true",
    "type",
    "unsafe",
    "use",
    "where",
    "while",
    "async",
    "await",
    "dyn",
    "abstract",
    "become",
    "box",
    "do",
    "final",
    "macro",
    "override",
    "priv",
    "typeof",
    "unsized",
    "virtual",
    "yield",
    "try",
    "gen",
    "union",
    "raw",
    // Names the emitted code relies on.
    "ml",
    "main",
    "std",
    "core",
    "alloc",
    "String",
    "Vec",
    "Box",
    "Option",
    "Some",
    "None",
    "Ok",
    "Err",
    "Result",
    "bool",
    "str",
    "char",
    "u8",
    "u16",
    "u32",
    "u64",
    "u128",
    "usize",
    "i8",
    "i16",
    "i32",
    "i64",
    "i128",
    "isize",
    "f32",
    "f64",
    "Big",
    "Clone",
    "Debug",
    "PartialEq",
    "Eq",
    "ToString",
    "ml_main",
    "ml_check_theorems",
    "ml_number",
];

const PRELUDE: &str = r#"/// Unbounded integers for the portable core's naturals and integers.
pub mod ml {
    use std::cmp::Ordering;
    use std::fmt;

    /// Sign and magnitude; the magnitude is little-endian base 2^32 without
    /// leading zero limbs, and zero is never negative.
    #[derive(Clone, Debug, PartialEq, Eq, Hash)]
    pub struct Big {
        negative: bool,
        magnitude: Vec<u32>,
    }

    fn trim(mut magnitude: Vec<u32>) -> Vec<u32> {
        while magnitude.last() == Some(&0) {
            magnitude.pop();
        }
        magnitude
    }

    fn compare_magnitude(a: &[u32], b: &[u32]) -> Ordering {
        a.len().cmp(&b.len()).then_with(|| a.iter().rev().cmp(b.iter().rev()))
    }

    fn add_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
        let mut out = Vec::with_capacity(a.len().max(b.len()) + 1);
        let mut carry = 0u64;
        for index in 0..a.len().max(b.len()) {
            let sum = u64::from(*a.get(index).unwrap_or(&0)) + u64::from(*b.get(index).unwrap_or(&0)) + carry;
            out.push(sum as u32);
            carry = sum >> 32;
        }
        if carry > 0 {
            out.push(carry as u32);
        }
        out
    }

    /// |a| - |b| where |a| >= |b|.
    fn sub_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
        let mut out = Vec::with_capacity(a.len());
        let mut borrow = 0i64;
        for (index, limb) in a.iter().enumerate() {
            let mut difference = i64::from(*limb) - i64::from(*b.get(index).unwrap_or(&0)) - borrow;
            borrow = 0;
            if difference < 0 {
                difference += 1 << 32;
                borrow = 1;
            }
            out.push(difference as u32);
        }
        trim(out)
    }

    fn mul_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
        let mut out = vec![0u32; a.len() + b.len()];
        for (i, x) in a.iter().enumerate() {
            let mut carry = 0u64;
            for (j, y) in b.iter().enumerate() {
                let product = u64::from(out[i + j]) + u64::from(*x) * u64::from(*y) + carry;
                out[i + j] = product as u32;
                carry = product >> 32;
            }
            let mut index = i + b.len();
            while carry > 0 {
                let sum = u64::from(out[index]) + carry;
                out[index] = sum as u32;
                carry = sum >> 32;
                index += 1;
            }
        }
        trim(out)
    }

    /// Quotient and remainder of magnitudes; the divisor is not zero.
    fn divmod_magnitude(a: &[u32], b: &[u32]) -> (Vec<u32>, Vec<u32>) {
        let mut quotient = vec![0u32; a.len()];
        if b.len() == 1 {
            let divisor = u64::from(b[0]);
            let mut remainder = 0u64;
            for index in (0..a.len()).rev() {
                let current = (remainder << 32) | u64::from(a[index]);
                quotient[index] = (current / divisor) as u32;
                remainder = current % divisor;
            }
            return (trim(quotient), trim(vec![remainder as u32]));
        }
        let mut remainder: Vec<u32> = Vec::new();
        for bit in (0..a.len() * 32).rev() {
            let mut carry = (a[bit / 32] >> (bit % 32)) & 1;
            for limb in remainder.iter_mut() {
                let next = *limb >> 31;
                *limb = (*limb << 1) | carry;
                carry = next;
            }
            if carry != 0 {
                remainder.push(carry);
            }
            if compare_magnitude(&remainder, b) != Ordering::Less {
                remainder = sub_magnitude(&remainder, b);
                quotient[bit / 32] |= 1 << (bit % 32);
            }
        }
        (trim(quotient), remainder)
    }

    impl Big {
        fn from_parts(negative: bool, magnitude: Vec<u32>) -> Self {
            let magnitude = trim(magnitude);
            Self { negative: negative && !magnitude.is_empty(), magnitude }
        }

        pub fn zero() -> Self {
            Self::from_parts(false, Vec::new())
        }

        pub fn from_i128(value: i128) -> Self {
            let mut big = Self::from_u128(value.unsigned_abs());
            big.negative = value < 0;
            big
        }

        pub fn from_u128(mut value: u128) -> Self {
            let mut magnitude = Vec::new();
            while value > 0 {
                magnitude.push(value as u32);
                value >>= 32;
            }
            Self::from_parts(false, magnitude)
        }

        /// A decimal literal with an optional leading minus sign.
        pub fn parse(text: &str) -> Self {
            let (negative, digits) = match text.strip_prefix('-') {
                Some(rest) => (true, rest),
                None => (false, text),
            };
            let ten = Self::from_i128(10);
            let mut value = Self::zero();
            for digit in digits.chars() {
                let digit = digit.to_digit(10).expect("decimal literal");
                value = value.mul(&ten).add(&Self::from_i128(i128::from(digit)));
            }
            if negative { value.neg() } else { value }
        }

        pub fn is_zero(&self) -> bool {
            self.magnitude.is_empty()
        }

        pub fn is_negative(&self) -> bool {
            self.negative
        }

        /// The array index this names, if it is one.
        pub fn to_index(&self) -> Option<usize> {
            if self.negative || self.magnitude.len() > 2 {
                return None;
            }
            let value = self.magnitude.iter().rev().fold(0u64, |acc, &digit| (acc << 32) | u64::from(digit));
            usize::try_from(value).ok()
        }

        pub fn neg(&self) -> Self {
            Self::from_parts(!self.negative, self.magnitude.clone())
        }

        pub fn add(&self, other: &Self) -> Self {
            if self.negative == other.negative {
                return Self::from_parts(self.negative, add_magnitude(&self.magnitude, &other.magnitude));
            }
            match compare_magnitude(&self.magnitude, &other.magnitude) {
                Ordering::Less => Self::from_parts(other.negative, sub_magnitude(&other.magnitude, &self.magnitude)),
                _ => Self::from_parts(self.negative, sub_magnitude(&self.magnitude, &other.magnitude)),
            }
        }

        pub fn sub(&self, other: &Self) -> Self {
            self.add(&other.neg())
        }

        pub fn mul(&self, other: &Self) -> Self {
            Self::from_parts(self.negative != other.negative, mul_magnitude(&self.magnitude, &other.magnitude))
        }

        /// Division rounding toward zero; the divisor is not zero.
        pub fn divmod_trunc(&self, other: &Self) -> (Self, Self) {
            let (quotient, remainder) = divmod_magnitude(&self.magnitude, &other.magnitude);
            (
                Self::from_parts(self.negative != other.negative, quotient),
                Self::from_parts(self.negative, remainder),
            )
        }
    }

    impl Ord for Big {
        fn cmp(&self, other: &Self) -> Ordering {
            match (self.negative, other.negative) {
                (false, true) => Ordering::Greater,
                (true, false) => Ordering::Less,
                (false, false) => compare_magnitude(&self.magnitude, &other.magnitude),
                (true, true) => compare_magnitude(&other.magnitude, &self.magnitude),
            }
        }
    }

    impl PartialOrd for Big {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            Some(self.cmp(other))
        }
    }

    impl fmt::Display for Big {
        fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
            if self.is_zero() {
                return formatter.write_str("0");
            }
            let billion = [1_000_000_000u32];
            let mut chunks = Vec::new();
            let mut rest = self.magnitude.clone();
            while !rest.is_empty() {
                let (quotient, remainder) = divmod_magnitude(&rest, &billion);
                chunks.push(remainder.first().copied().unwrap_or(0));
                rest = quotient;
            }
            let mut text = String::new();
            if self.negative {
                text.push('-');
            }
            text.push_str(&chunks.pop().unwrap_or(0).to_string());
            for chunk in chunks.iter().rev() {
                text.push_str(&format!("{chunk:09}"));
            }
            formatter.write_str(&text)
        }
    }

    /// Natural subtraction: truncated at zero.
    pub fn nat_sub(a: &Big, b: &Big) -> Big {
        if a > b { a.sub(b) } else { Big::zero() }
    }

    pub fn pred(a: &Big) -> Big {
        a.sub(&Big::from_i128(1))
    }

    /// Integer division with the source's rounding ("trunc", "floor" or
    /// "euclid"); by zero it aborts with the source's message or is total
    /// (x / 0 = 0, x % 0 = x).
    pub fn divide(a: &Big, b: &Big, rounding: &str, by_zero: Option<&str>, remainder: bool) -> Big {
        if b.is_zero() {
            if let Some(message) = by_zero {
                panic!("{message}");
            }
            return if remainder { a.clone() } else { Big::zero() };
        }
        let one = Big::from_i128(1);
        let (mut quotient, rest) = a.divmod_trunc(b);
        if !rest.is_zero() {
            if rounding == "floor" && rest.is_negative() != b.is_negative() {
                quotient = quotient.sub(&one);
            }
            if rounding == "euclid" && rest.is_negative() {
                quotient = if b.is_negative() { quotient.add(&one) } else { quotient.sub(&one) };
            }
        }
        if remainder { a.sub(&quotient.mul(b)) } else { quotient }
    }

    pub fn to_nat_checked(value: Big, message: &str) -> Big {
        if value.is_negative() {
            panic!("{message}");
        }
        value
    }

    pub fn clamp_nat(value: Big) -> Big {
        if value.is_negative() { Big::zero() } else { value }
    }

    /// Bounded domains for executable theorem checks.
    pub fn range(low: i128, high: i128) -> Vec<Big> {
        (low..=high).map(Big::from_i128).collect()
    }
}"#;

/// A legal Rust identifier for a source name.
fn ident(name: &str) -> String {
    let mut result: String = name
        .chars()
        .map(|char| {
            if char.is_ascii_alphanumeric() || char == '_' {
                char
            } else {
                '_'
            }
        })
        .collect();
    if result.starts_with(|char: char| char.is_ascii_digit())
        || result.starts_with("__")
        || result == "_"
        || result.is_empty()
    {
        result = format!("x{result}");
    }
    if KEYWORDS.contains(&result.as_str()) {
        result.push('_');
    }
    result
}

/// `camelCase` and `HTTPServer` split into `camel_case` and `http_server`.
fn snake(name: &str) -> String {
    // `/([a-z0-9])([A-Z])/g` inserts `_` between a lower-case letter or digit and a capital.
    let chars: Vec<char> = name.chars().collect();
    let mut first = Vec::with_capacity(chars.len());
    let mut index = 0;
    while index < chars.len() {
        let char = chars[index];
        let next = chars.get(index + 1).copied();
        if (char.is_ascii_lowercase() || char.is_ascii_digit())
            && next.is_some_and(|next| next.is_ascii_uppercase())
        {
            first.extend([char, '_', next.unwrap_or(char)]);
            index += 2;
        } else {
            first.push(char);
            index += 1;
        }
    }
    // `/([A-Z]+)([A-Z][a-z])/g` splits a run of capitals before its last one
    // when a lower-case letter follows.
    let mut second = String::with_capacity(first.len() + 4);
    let mut index = 0;
    while index < first.len() {
        let run = first[index..]
            .iter()
            .take_while(|char| char.is_ascii_uppercase())
            .count();
        let after = first.get(index + run).copied();
        if run >= 2 && after.is_some_and(|after| after.is_ascii_lowercase()) {
            second.extend(&first[index..index + run - 1]);
            second.push('_');
            second.extend(&first[index + run - 1..=index + run]);
            index += run + 1;
        } else {
            second.push(first[index]);
            index += 1;
        }
    }
    ident(&second.to_lowercase())
}

/// `my_type` and `my-type` become `MyType`.
fn camel(name: &str) -> String {
    let joined: String = name
        .split(|char: char| !char.is_ascii_alphanumeric())
        .filter(|part| !part.is_empty())
        .map(|part| {
            let mut chars = part.chars();
            chars.next().map_or_else(String::new, |first| {
                let mut part = first.to_uppercase().to_string();
                part.extend(chars);
                part
            })
        })
        .collect();
    ident(if joined.is_empty() { "T" } else { &joined })
}

/// Emits a checked program as Rust.
///
/// # Errors
/// On constructs the target cannot express faithfully.
pub fn emit_rust(program: &Program) -> Result<Emitted> {
    let state = EmitState::new(
        program,
        Language::Rust,
        snake,
        KEYWORDS,
        EmitOptions {
            ctor_style: CtorStyle::Data,
            type_name: Some(camel),
            value_name: Some(snake),
            ctor_name: Some(camel),
            module_segment: Some(snake),
            type_space: true,
            modules_share_type_space: true,
            ..EmitOptions::default()
        },
    );
    RustEmitter {
        program,
        state,
        temporaries: 0,
        theorem_checks: Vec::new(),
        preludes: BTreeSet::new(),
        loop_params: None,
    }
    .file()
}

/// Declarations grouped by source module, in declaration order.
#[derive(Default)]
struct ModuleTree<'p> {
    items: Vec<&'p Decl>,
    modules: Vec<(String, Self)>,
}

/// A theorem the `--ml-check-theorems` runner evaluates.
#[derive(Clone)]
struct TheoremCheck {
    reference: String,
    binders: Vec<Binder>,
    source: String,
}

/// A generated module, in the order the file lists the ones it uses.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Prelude {
    Big,
    Number,
    Math,
    Array,
}

struct RustEmitter<'p> {
    program: &'p Program,
    state: EmitState<'p>,
    temporaries: usize,
    theorem_checks: Vec<TheoremCheck>,
    /// The generated modules the program uses.
    preludes: BTreeSet<Prelude>,
    /// The lifted loop being emitted as a loop, and its parameters, which
    /// each call to it assigns before the next iteration.
    loop_params: Option<(String, Vec<String>)>,
}

const fn is_copy(ty: &Type) -> bool {
    matches!(
        ty,
        Type::Bool | Type::Fixed { .. } | Type::Float | Type::Unit
    )
}

const fn comparison_operator(op: BinaryOp) -> &'static str {
    match op {
        BinaryOp::Eq => "==",
        BinaryOp::Ne => "!=",
        BinaryOp::Lt => "<",
        BinaryOp::Le => "<=",
        BinaryOp::Gt => ">",
        _ => ">=",
    }
}

/// The rounding as the JavaScript runtime interpolates it.
const fn rounding_text(rounding: Option<Rounding>) -> &'static str {
    match rounding {
        Some(Rounding::Trunc) => "trunc",
        Some(Rounding::Euclid) => "euclid",
        Some(Rounding::Floor) => "floor",
        None => "undefined",
    }
}

impl RustEmitter<'_> {}

/// An owned copy of a variable.
fn own(name: &str, ty: &Type) -> String {
    if is_copy(ty) {
        name.to_owned()
    } else {
        format!("{name}.clone()")
    }
}

fn block(text: &str) -> String {
    format!("{{\n{}\n}}", indent(text, 1))
}

fn rust_escape(text: &str) -> String {
    let mut out = String::with_capacity(text.len());
    for char in text.chars() {
        match char {
            '"' | '\\' => {
                out.push('\\');
                out.push(char);
            }
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            _ if (char as u32) < 0x20 || char as u32 == 0x7f => {
                let _ = write!(out, "\\u{{{:x}}}", char as u32);
            }
            _ => out.push(char),
        }
    }
    out
}

/// Text inside a `format!`-style literal, where braces are doubled.
fn format_escape(text: &str) -> String {
    rust_escape(text).replace('{', "{{").replace('}', "}}")
}

fn rust_string(text: &str) -> String {
    format!("\"{}\"", rust_escape(text))
}

fn indent(text: &str, depth: usize) -> String {
    let pad = "    ".repeat(depth);
    text.split('\n')
        .map(|line| {
            if line.is_empty() {
                line.to_owned()
            } else {
                format!("{pad}{line}")
            }
        })
        .collect::<Vec<_>>()
        .join("\n")
}