meta_language/translation/
emit_rust.rs

1//! The Rust emitter: writes a checked program as Rust with its translation contract.
2//!
3//! Naturals and integers are `ml::Big`, an unbounded integer the translation
4//! carries in its own prelude, so no value is ever narrowed; machine integers
5//! stay Rust machine integers with checked arithmetic, which panics exactly
6//! where the source aborts; a JavaScript Number is an `f64`, printed by
7//! `ml_number::js_number` exactly as JavaScript prints it. Data types are enums
8//! whose data-typed fields are boxed. Every value is owned: a variable is cloned where it is consumed.
9//! Theorems cannot be proved in Rust: each becomes an executable property,
10//! checked over a bounded domain by `--ml-check-theorems`, while the proof
11//! stays discharged by the source kernel.
12//!
13//! Mirrors `js/src/translation/emit-rust.js`.
14
15use std::collections::BTreeSet;
16use std::fmt::Write as _;
17
18use super::Language;
19use super::decimal::Decimal;
20use super::diagnostics::{Result, unsupported};
21use super::emit_common::{CtorStyle, EmitOptions, EmitState, Emitted};
22use super::ir::{
23    Binder, ByZero, Decl, Effect, Expr, LitValue, Node, Pattern, Program, Prop, Semantics,
24    rename_function, rename_main, rename_theorem, tail_loop,
25};
26use super::surface::{BinaryOp, Flavor, Rounding, UnaryOp};
27use super::types::Type;
28
29mod arrays;
30mod declarations;
31mod expressions;
32mod math;
33mod number_prelude;
34
35use self::arrays::ARRAY_PRELUDE;
36use self::math::MATH_PRELUDE;
37use self::number_prelude::NUMBER_PRELUDE;
38
39const KEYWORDS: &[&str] = &[
40    "as",
41    "break",
42    "const",
43    "continue",
44    "crate",
45    "else",
46    "enum",
47    "extern",
48    "false",
49    "fn",
50    "for",
51    "if",
52    "impl",
53    "in",
54    "let",
55    "loop",
56    "match",
57    "mod",
58    "move",
59    "mut",
60    "pub",
61    "ref",
62    "return",
63    "self",
64    "Self",
65    "static",
66    "struct",
67    "super",
68    "trait",
69    "true",
70    "type",
71    "unsafe",
72    "use",
73    "where",
74    "while",
75    "async",
76    "await",
77    "dyn",
78    "abstract",
79    "become",
80    "box",
81    "do",
82    "final",
83    "macro",
84    "override",
85    "priv",
86    "typeof",
87    "unsized",
88    "virtual",
89    "yield",
90    "try",
91    "gen",
92    "union",
93    "raw",
94    // Names the emitted code relies on.
95    "ml",
96    "main",
97    "std",
98    "core",
99    "alloc",
100    "String",
101    "Vec",
102    "Box",
103    "Option",
104    "Some",
105    "None",
106    "Ok",
107    "Err",
108    "Result",
109    "bool",
110    "str",
111    "char",
112    "u8",
113    "u16",
114    "u32",
115    "u64",
116    "u128",
117    "usize",
118    "i8",
119    "i16",
120    "i32",
121    "i64",
122    "i128",
123    "isize",
124    "f32",
125    "f64",
126    "Big",
127    "Clone",
128    "Debug",
129    "PartialEq",
130    "Eq",
131    "ToString",
132    "ml_main",
133    "ml_check_theorems",
134    "ml_number",
135];
136
137const PRELUDE: &str = r#"/// Unbounded integers for the portable core's naturals and integers.
138pub mod ml {
139    use std::cmp::Ordering;
140    use std::fmt;
141
142    /// Sign and magnitude; the magnitude is little-endian base 2^32 without
143    /// leading zero limbs, and zero is never negative.
144    #[derive(Clone, Debug, PartialEq, Eq, Hash)]
145    pub struct Big {
146        negative: bool,
147        magnitude: Vec<u32>,
148    }
149
150    fn trim(mut magnitude: Vec<u32>) -> Vec<u32> {
151        while magnitude.last() == Some(&0) {
152            magnitude.pop();
153        }
154        magnitude
155    }
156
157    fn compare_magnitude(a: &[u32], b: &[u32]) -> Ordering {
158        a.len().cmp(&b.len()).then_with(|| a.iter().rev().cmp(b.iter().rev()))
159    }
160
161    fn add_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
162        let mut out = Vec::with_capacity(a.len().max(b.len()) + 1);
163        let mut carry = 0u64;
164        for index in 0..a.len().max(b.len()) {
165            let sum = u64::from(*a.get(index).unwrap_or(&0)) + u64::from(*b.get(index).unwrap_or(&0)) + carry;
166            out.push(sum as u32);
167            carry = sum >> 32;
168        }
169        if carry > 0 {
170            out.push(carry as u32);
171        }
172        out
173    }
174
175    /// |a| - |b| where |a| >= |b|.
176    fn sub_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
177        let mut out = Vec::with_capacity(a.len());
178        let mut borrow = 0i64;
179        for (index, limb) in a.iter().enumerate() {
180            let mut difference = i64::from(*limb) - i64::from(*b.get(index).unwrap_or(&0)) - borrow;
181            borrow = 0;
182            if difference < 0 {
183                difference += 1 << 32;
184                borrow = 1;
185            }
186            out.push(difference as u32);
187        }
188        trim(out)
189    }
190
191    fn mul_magnitude(a: &[u32], b: &[u32]) -> Vec<u32> {
192        let mut out = vec![0u32; a.len() + b.len()];
193        for (i, x) in a.iter().enumerate() {
194            let mut carry = 0u64;
195            for (j, y) in b.iter().enumerate() {
196                let product = u64::from(out[i + j]) + u64::from(*x) * u64::from(*y) + carry;
197                out[i + j] = product as u32;
198                carry = product >> 32;
199            }
200            let mut index = i + b.len();
201            while carry > 0 {
202                let sum = u64::from(out[index]) + carry;
203                out[index] = sum as u32;
204                carry = sum >> 32;
205                index += 1;
206            }
207        }
208        trim(out)
209    }
210
211    /// Quotient and remainder of magnitudes; the divisor is not zero.
212    fn divmod_magnitude(a: &[u32], b: &[u32]) -> (Vec<u32>, Vec<u32>) {
213        let mut quotient = vec![0u32; a.len()];
214        if b.len() == 1 {
215            let divisor = u64::from(b[0]);
216            let mut remainder = 0u64;
217            for index in (0..a.len()).rev() {
218                let current = (remainder << 32) | u64::from(a[index]);
219                quotient[index] = (current / divisor) as u32;
220                remainder = current % divisor;
221            }
222            return (trim(quotient), trim(vec![remainder as u32]));
223        }
224        let mut remainder: Vec<u32> = Vec::new();
225        for bit in (0..a.len() * 32).rev() {
226            let mut carry = (a[bit / 32] >> (bit % 32)) & 1;
227            for limb in remainder.iter_mut() {
228                let next = *limb >> 31;
229                *limb = (*limb << 1) | carry;
230                carry = next;
231            }
232            if carry != 0 {
233                remainder.push(carry);
234            }
235            if compare_magnitude(&remainder, b) != Ordering::Less {
236                remainder = sub_magnitude(&remainder, b);
237                quotient[bit / 32] |= 1 << (bit % 32);
238            }
239        }
240        (trim(quotient), remainder)
241    }
242
243    impl Big {
244        fn from_parts(negative: bool, magnitude: Vec<u32>) -> Self {
245            let magnitude = trim(magnitude);
246            Self { negative: negative && !magnitude.is_empty(), magnitude }
247        }
248
249        pub fn zero() -> Self {
250            Self::from_parts(false, Vec::new())
251        }
252
253        pub fn from_i128(value: i128) -> Self {
254            let mut big = Self::from_u128(value.unsigned_abs());
255            big.negative = value < 0;
256            big
257        }
258
259        pub fn from_u128(mut value: u128) -> Self {
260            let mut magnitude = Vec::new();
261            while value > 0 {
262                magnitude.push(value as u32);
263                value >>= 32;
264            }
265            Self::from_parts(false, magnitude)
266        }
267
268        /// A decimal literal with an optional leading minus sign.
269        pub fn parse(text: &str) -> Self {
270            let (negative, digits) = match text.strip_prefix('-') {
271                Some(rest) => (true, rest),
272                None => (false, text),
273            };
274            let ten = Self::from_i128(10);
275            let mut value = Self::zero();
276            for digit in digits.chars() {
277                let digit = digit.to_digit(10).expect("decimal literal");
278                value = value.mul(&ten).add(&Self::from_i128(i128::from(digit)));
279            }
280            if negative { value.neg() } else { value }
281        }
282
283        pub fn is_zero(&self) -> bool {
284            self.magnitude.is_empty()
285        }
286
287        pub fn is_negative(&self) -> bool {
288            self.negative
289        }
290
291        /// The array index this names, if it is one.
292        pub fn to_index(&self) -> Option<usize> {
293            if self.negative || self.magnitude.len() > 2 {
294                return None;
295            }
296            let value = self.magnitude.iter().rev().fold(0u64, |acc, &digit| (acc << 32) | u64::from(digit));
297            usize::try_from(value).ok()
298        }
299
300        pub fn neg(&self) -> Self {
301            Self::from_parts(!self.negative, self.magnitude.clone())
302        }
303
304        pub fn add(&self, other: &Self) -> Self {
305            if self.negative == other.negative {
306                return Self::from_parts(self.negative, add_magnitude(&self.magnitude, &other.magnitude));
307            }
308            match compare_magnitude(&self.magnitude, &other.magnitude) {
309                Ordering::Less => Self::from_parts(other.negative, sub_magnitude(&other.magnitude, &self.magnitude)),
310                _ => Self::from_parts(self.negative, sub_magnitude(&self.magnitude, &other.magnitude)),
311            }
312        }
313
314        pub fn sub(&self, other: &Self) -> Self {
315            self.add(&other.neg())
316        }
317
318        pub fn mul(&self, other: &Self) -> Self {
319            Self::from_parts(self.negative != other.negative, mul_magnitude(&self.magnitude, &other.magnitude))
320        }
321
322        /// Division rounding toward zero; the divisor is not zero.
323        pub fn divmod_trunc(&self, other: &Self) -> (Self, Self) {
324            let (quotient, remainder) = divmod_magnitude(&self.magnitude, &other.magnitude);
325            (
326                Self::from_parts(self.negative != other.negative, quotient),
327                Self::from_parts(self.negative, remainder),
328            )
329        }
330    }
331
332    impl Ord for Big {
333        fn cmp(&self, other: &Self) -> Ordering {
334            match (self.negative, other.negative) {
335                (false, true) => Ordering::Greater,
336                (true, false) => Ordering::Less,
337                (false, false) => compare_magnitude(&self.magnitude, &other.magnitude),
338                (true, true) => compare_magnitude(&other.magnitude, &self.magnitude),
339            }
340        }
341    }
342
343    impl PartialOrd for Big {
344        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
345            Some(self.cmp(other))
346        }
347    }
348
349    impl fmt::Display for Big {
350        fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
351            if self.is_zero() {
352                return formatter.write_str("0");
353            }
354            let billion = [1_000_000_000u32];
355            let mut chunks = Vec::new();
356            let mut rest = self.magnitude.clone();
357            while !rest.is_empty() {
358                let (quotient, remainder) = divmod_magnitude(&rest, &billion);
359                chunks.push(remainder.first().copied().unwrap_or(0));
360                rest = quotient;
361            }
362            let mut text = String::new();
363            if self.negative {
364                text.push('-');
365            }
366            text.push_str(&chunks.pop().unwrap_or(0).to_string());
367            for chunk in chunks.iter().rev() {
368                text.push_str(&format!("{chunk:09}"));
369            }
370            formatter.write_str(&text)
371        }
372    }
373
374    /// Natural subtraction: truncated at zero.
375    pub fn nat_sub(a: &Big, b: &Big) -> Big {
376        if a > b { a.sub(b) } else { Big::zero() }
377    }
378
379    pub fn pred(a: &Big) -> Big {
380        a.sub(&Big::from_i128(1))
381    }
382
383    /// Integer division with the source's rounding ("trunc", "floor" or
384    /// "euclid"); by zero it aborts with the source's message or is total
385    /// (x / 0 = 0, x % 0 = x).
386    pub fn divide(a: &Big, b: &Big, rounding: &str, by_zero: Option<&str>, remainder: bool) -> Big {
387        if b.is_zero() {
388            if let Some(message) = by_zero {
389                panic!("{message}");
390            }
391            return if remainder { a.clone() } else { Big::zero() };
392        }
393        let one = Big::from_i128(1);
394        let (mut quotient, rest) = a.divmod_trunc(b);
395        if !rest.is_zero() {
396            if rounding == "floor" && rest.is_negative() != b.is_negative() {
397                quotient = quotient.sub(&one);
398            }
399            if rounding == "euclid" && rest.is_negative() {
400                quotient = if b.is_negative() { quotient.add(&one) } else { quotient.sub(&one) };
401            }
402        }
403        if remainder { a.sub(&quotient.mul(b)) } else { quotient }
404    }
405
406    pub fn to_nat_checked(value: Big, message: &str) -> Big {
407        if value.is_negative() {
408            panic!("{message}");
409        }
410        value
411    }
412
413    pub fn clamp_nat(value: Big) -> Big {
414        if value.is_negative() { Big::zero() } else { value }
415    }
416
417    /// Bounded domains for executable theorem checks.
418    pub fn range(low: i128, high: i128) -> Vec<Big> {
419        (low..=high).map(Big::from_i128).collect()
420    }
421}"#;
422
423/// A legal Rust identifier for a source name.
424fn ident(name: &str) -> String {
425    let mut result: String = name
426        .chars()
427        .map(|char| {
428            if char.is_ascii_alphanumeric() || char == '_' {
429                char
430            } else {
431                '_'
432            }
433        })
434        .collect();
435    if result.starts_with(|char: char| char.is_ascii_digit())
436        || result.starts_with("__")
437        || result == "_"
438        || result.is_empty()
439    {
440        result = format!("x{result}");
441    }
442    if KEYWORDS.contains(&result.as_str()) {
443        result.push('_');
444    }
445    result
446}
447
448/// `camelCase` and `HTTPServer` split into `camel_case` and `http_server`.
449fn snake(name: &str) -> String {
450    // `/([a-z0-9])([A-Z])/g` inserts `_` between a lower-case letter or digit and a capital.
451    let chars: Vec<char> = name.chars().collect();
452    let mut first = Vec::with_capacity(chars.len());
453    let mut index = 0;
454    while index < chars.len() {
455        let char = chars[index];
456        let next = chars.get(index + 1).copied();
457        if (char.is_ascii_lowercase() || char.is_ascii_digit())
458            && next.is_some_and(|next| next.is_ascii_uppercase())
459        {
460            first.extend([char, '_', next.unwrap_or(char)]);
461            index += 2;
462        } else {
463            first.push(char);
464            index += 1;
465        }
466    }
467    // `/([A-Z]+)([A-Z][a-z])/g` splits a run of capitals before its last one
468    // when a lower-case letter follows.
469    let mut second = String::with_capacity(first.len() + 4);
470    let mut index = 0;
471    while index < first.len() {
472        let run = first[index..]
473            .iter()
474            .take_while(|char| char.is_ascii_uppercase())
475            .count();
476        let after = first.get(index + run).copied();
477        if run >= 2 && after.is_some_and(|after| after.is_ascii_lowercase()) {
478            second.extend(&first[index..index + run - 1]);
479            second.push('_');
480            second.extend(&first[index + run - 1..=index + run]);
481            index += run + 1;
482        } else {
483            second.push(first[index]);
484            index += 1;
485        }
486    }
487    ident(&second.to_lowercase())
488}
489
490/// `my_type` and `my-type` become `MyType`.
491fn camel(name: &str) -> String {
492    let joined: String = name
493        .split(|char: char| !char.is_ascii_alphanumeric())
494        .filter(|part| !part.is_empty())
495        .map(|part| {
496            let mut chars = part.chars();
497            chars.next().map_or_else(String::new, |first| {
498                let mut part = first.to_uppercase().to_string();
499                part.extend(chars);
500                part
501            })
502        })
503        .collect();
504    ident(if joined.is_empty() { "T" } else { &joined })
505}
506
507/// Emits a checked program as Rust.
508///
509/// # Errors
510/// On constructs the target cannot express faithfully.
511pub fn emit_rust(program: &Program) -> Result<Emitted> {
512    let state = EmitState::new(
513        program,
514        Language::Rust,
515        snake,
516        KEYWORDS,
517        EmitOptions {
518            ctor_style: CtorStyle::Data,
519            type_name: Some(camel),
520            value_name: Some(snake),
521            ctor_name: Some(camel),
522            module_segment: Some(snake),
523            type_space: true,
524            modules_share_type_space: true,
525            ..EmitOptions::default()
526        },
527    );
528    RustEmitter {
529        program,
530        state,
531        temporaries: 0,
532        theorem_checks: Vec::new(),
533        preludes: BTreeSet::new(),
534        loop_params: None,
535    }
536    .file()
537}
538
539/// Declarations grouped by source module, in declaration order.
540#[derive(Default)]
541struct ModuleTree<'p> {
542    items: Vec<&'p Decl>,
543    modules: Vec<(String, Self)>,
544}
545
546/// A theorem the `--ml-check-theorems` runner evaluates.
547#[derive(Clone)]
548struct TheoremCheck {
549    reference: String,
550    binders: Vec<Binder>,
551    source: String,
552}
553
554/// A generated module, in the order the file lists the ones it uses.
555#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
556enum Prelude {
557    Big,
558    Number,
559    Math,
560    Array,
561}
562
563struct RustEmitter<'p> {
564    program: &'p Program,
565    state: EmitState<'p>,
566    temporaries: usize,
567    theorem_checks: Vec<TheoremCheck>,
568    /// The generated modules the program uses.
569    preludes: BTreeSet<Prelude>,
570    /// The lifted loop being emitted as a loop, and its parameters, which
571    /// each call to it assigns before the next iteration.
572    loop_params: Option<(String, Vec<String>)>,
573}
574
575const fn is_copy(ty: &Type) -> bool {
576    matches!(
577        ty,
578        Type::Bool | Type::Fixed { .. } | Type::Float | Type::Unit
579    )
580}
581
582const fn comparison_operator(op: BinaryOp) -> &'static str {
583    match op {
584        BinaryOp::Eq => "==",
585        BinaryOp::Ne => "!=",
586        BinaryOp::Lt => "<",
587        BinaryOp::Le => "<=",
588        BinaryOp::Gt => ">",
589        _ => ">=",
590    }
591}
592
593/// The rounding as the JavaScript runtime interpolates it.
594const fn rounding_text(rounding: Option<Rounding>) -> &'static str {
595    match rounding {
596        Some(Rounding::Trunc) => "trunc",
597        Some(Rounding::Euclid) => "euclid",
598        Some(Rounding::Floor) => "floor",
599        None => "undefined",
600    }
601}
602
603impl RustEmitter<'_> {}
604
605/// An owned copy of a variable.
606fn own(name: &str, ty: &Type) -> String {
607    if is_copy(ty) {
608        name.to_owned()
609    } else {
610        format!("{name}.clone()")
611    }
612}
613
614fn block(text: &str) -> String {
615    format!("{{\n{}\n}}", indent(text, 1))
616}
617
618fn rust_escape(text: &str) -> String {
619    let mut out = String::with_capacity(text.len());
620    for char in text.chars() {
621        match char {
622            '"' | '\\' => {
623                out.push('\\');
624                out.push(char);
625            }
626            '\n' => out.push_str("\\n"),
627            '\r' => out.push_str("\\r"),
628            '\t' => out.push_str("\\t"),
629            _ if (char as u32) < 0x20 || char as u32 == 0x7f => {
630                let _ = write!(out, "\\u{{{:x}}}", char as u32);
631            }
632            _ => out.push(char),
633        }
634    }
635    out
636}
637
638/// Text inside a `format!`-style literal, where braces are doubled.
639fn format_escape(text: &str) -> String {
640    rust_escape(text).replace('{', "{{").replace('}', "}}")
641}
642
643fn rust_string(text: &str) -> String {
644    format!("\"{}\"", rust_escape(text))
645}
646
647fn indent(text: &str, depth: usize) -> String {
648    let pad = "    ".repeat(depth);
649    text.split('\n')
650        .map(|line| {
651            if line.is_empty() {
652                line.to_owned()
653            } else {
654                format!("{pad}{line}")
655            }
656        })
657        .collect::<Vec<_>>()
658        .join("\n")
659}
meta_language/translation/emit_rust.rs

meta_language/translation/
emit_rust.rs
