1use crate::lcnf::{LcnfArg, LcnfExpr, LcnfFunDecl, LcnfLetValue, LcnfLit, LcnfVarId};
6
7use super::types::{
8 BinOp, CtfeConfig, CtfeContext, CtfeError, CtfeFeatureFlags, CtfeFuncEntry, CtfeInterpreter,
9 CtfePass, CtfeReport, CtfeType, CtfeValue, CtfeValueExt,
10};
11
12pub type CtfeResult = Result<CtfeValue, CtfeError>;
14pub(super) fn ctfe_value_to_arg(val: &CtfeValue) -> LcnfArg {
15 match val {
16 CtfeValue::Int(n) => {
17 if *n >= 0 {
18 LcnfArg::Lit(LcnfLit::Nat(*n as u64))
19 } else {
20 LcnfArg::Lit(LcnfLit::Nat(n.unsigned_abs()))
21 }
22 }
23 CtfeValue::String(s) => LcnfArg::Lit(LcnfLit::Str(s.clone())),
24 _ => LcnfArg::Erased,
25 }
26}
27pub(super) fn ctfe_value_to_let_value(val: CtfeValue) -> LcnfLetValue {
28 match val {
29 CtfeValue::Int(n) => LcnfLetValue::Lit(LcnfLit::Nat(if n >= 0 {
30 n as u64
31 } else {
32 n.unsigned_abs()
33 })),
34 CtfeValue::String(s) => LcnfLetValue::Lit(LcnfLit::Str(s)),
35 CtfeValue::Constructor(name, fields) => {
36 let args: Vec<LcnfArg> = fields.iter().map(ctfe_value_to_arg).collect();
37 LcnfLetValue::Ctor(name, 0, args)
38 }
39 _ => LcnfLetValue::Erased,
40 }
41}
42#[cfg(test)]
43mod tests {
44 use super::*;
45 use crate::lcnf::{LcnfFunDecl, LcnfParam, LcnfType, LcnfVarId};
46 pub(super) fn vid(n: u64) -> LcnfVarId {
47 LcnfVarId(n)
48 }
49 pub(super) fn mk_param(n: u64, name: &str) -> LcnfParam {
50 LcnfParam {
51 id: vid(n),
52 name: name.to_string(),
53 ty: LcnfType::Nat,
54 erased: false,
55 borrowed: false,
56 }
57 }
58 pub(super) fn mk_const_decl(name: &str, body: LcnfExpr) -> LcnfFunDecl {
59 LcnfFunDecl {
60 name: name.to_string(),
61 original_name: None,
62 params: vec![],
63 ret_type: LcnfType::Nat,
64 body,
65 is_recursive: false,
66 is_lifted: false,
67 inline_cost: 0,
68 }
69 }
70 pub(super) fn mk_decl_with_params(
71 name: &str,
72 params: Vec<LcnfParam>,
73 body: LcnfExpr,
74 ) -> LcnfFunDecl {
75 LcnfFunDecl {
76 name: name.to_string(),
77 original_name: None,
78 params,
79 ret_type: LcnfType::Nat,
80 body,
81 is_recursive: false,
82 is_lifted: false,
83 inline_cost: 1,
84 }
85 }
86 pub(super) fn ret_nat(n: u64) -> LcnfExpr {
87 LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Nat(n)))
88 }
89 pub(super) fn ret_str(s: &str) -> LcnfExpr {
90 LcnfExpr::Return(LcnfArg::Lit(LcnfLit::Str(s.to_string())))
91 }
92 #[test]
93 pub(super) fn ctfe_value_int_display() {
94 assert_eq!(CtfeValue::Int(42).to_string(), "42");
95 }
96 #[test]
97 pub(super) fn ctfe_value_bool_display() {
98 assert_eq!(CtfeValue::Bool(true).to_string(), "true");
99 assert_eq!(CtfeValue::Bool(false).to_string(), "false");
100 }
101 #[test]
102 pub(super) fn ctfe_value_string_display() {
103 assert_eq!(CtfeValue::String("hi".to_string()).to_string(), "\"hi\"");
104 }
105 #[test]
106 pub(super) fn ctfe_value_undef_display() {
107 assert_eq!(CtfeValue::Undef.to_string(), "undef");
108 }
109 #[test]
110 pub(super) fn ctfe_value_list_display() {
111 let v = CtfeValue::List(vec![CtfeValue::Int(1), CtfeValue::Int(2)]);
112 assert_eq!(v.to_string(), "[1, 2]");
113 }
114 #[test]
115 pub(super) fn ctfe_value_tuple_display() {
116 let v = CtfeValue::Tuple(vec![CtfeValue::Int(3), CtfeValue::Bool(true)]);
117 assert_eq!(v.to_string(), "(3, true)");
118 }
119 #[test]
120 pub(super) fn ctfe_value_constructor_display() {
121 let v = CtfeValue::Constructor(
122 "Pair".to_string(),
123 vec![CtfeValue::Int(1), CtfeValue::Int(2)],
124 );
125 assert_eq!(v.to_string(), "Pair(1, 2)");
126 }
127 #[test]
128 pub(super) fn ctfe_value_is_concrete() {
129 assert!(CtfeValue::Int(0).is_concrete());
130 assert!(!CtfeValue::Undef.is_concrete());
131 let v = CtfeValue::List(vec![CtfeValue::Int(1), CtfeValue::Undef]);
132 assert!(!v.is_concrete());
133 }
134 #[test]
135 pub(super) fn ctfe_value_as_int() {
136 assert_eq!(CtfeValue::Int(7).as_int(), Some(7));
137 assert_eq!(CtfeValue::Bool(true).as_int(), None);
138 }
139 #[test]
140 pub(super) fn ctfe_value_as_bool() {
141 assert_eq!(CtfeValue::Bool(false).as_bool(), Some(false));
142 assert_eq!(CtfeValue::Int(1).as_bool(), None);
143 }
144 #[test]
145 pub(super) fn ctfe_value_as_str() {
146 let s = CtfeValue::String("hello".to_string());
147 assert_eq!(s.as_str(), Some("hello"));
148 assert_eq!(CtfeValue::Int(0).as_str(), None);
149 }
150 #[test]
151 pub(super) fn ctfe_error_display_division_by_zero() {
152 assert_eq!(CtfeError::DivisionByZero.to_string(), "division by zero");
153 }
154 #[test]
155 pub(super) fn ctfe_error_display_index_out_of_bounds() {
156 let e = CtfeError::IndexOutOfBounds {
157 index: 5,
158 length: 3,
159 };
160 let s = e.to_string();
161 assert!(s.contains("5") && s.contains("3"));
162 }
163 #[test]
164 pub(super) fn ctfe_error_display_stack_overflow() {
165 let e = CtfeError::StackOverflow { depth: 256 };
166 assert!(e.to_string().contains("256"));
167 }
168 #[test]
169 pub(super) fn ctfe_error_display_timeout() {
170 let e = CtfeError::Timeout { fuel_used: 10000 };
171 assert!(e.to_string().contains("10000"));
172 }
173 #[test]
174 pub(super) fn binop_from_name_recognized() {
175 assert_eq!(BinOp::from_name("add"), Some(BinOp::Add));
176 assert_eq!(BinOp::from_name("+"), Some(BinOp::Add));
177 assert_eq!(BinOp::from_name("Nat.add"), Some(BinOp::Add));
178 assert_eq!(BinOp::from_name("eq"), Some(BinOp::Eq));
179 assert_eq!(BinOp::from_name("=="), Some(BinOp::Eq));
180 assert_eq!(BinOp::from_name("&&"), Some(BinOp::And));
181 }
182 #[test]
183 pub(super) fn binop_from_name_unknown() {
184 assert_eq!(BinOp::from_name("foo"), None);
185 }
186 #[test]
187 pub(super) fn eval_lit_nat() {
188 let interp = CtfeInterpreter::new(&[]);
189 assert_eq!(interp.eval_lit(&LcnfLit::Nat(42)), CtfeValue::Int(42));
190 }
191 #[test]
192 pub(super) fn eval_lit_str() {
193 let interp = CtfeInterpreter::new(&[]);
194 let v = interp.eval_lit(&LcnfLit::Str("hello".to_string()));
195 assert_eq!(v, CtfeValue::String("hello".to_string()));
196 }
197 #[test]
198 pub(super) fn eval_binop_add() {
199 let interp = CtfeInterpreter::new(&[]);
200 let r = interp.eval_binop(BinOp::Add, &CtfeValue::Int(3), &CtfeValue::Int(4));
201 assert_eq!(r, Ok(CtfeValue::Int(7)));
202 }
203 #[test]
204 pub(super) fn eval_binop_div_by_zero() {
205 let interp = CtfeInterpreter::new(&[]);
206 let r = interp.eval_binop(BinOp::Div, &CtfeValue::Int(5), &CtfeValue::Int(0));
207 assert_eq!(r, Err(CtfeError::DivisionByZero));
208 }
209 #[test]
210 pub(super) fn eval_binop_mod_by_zero() {
211 let interp = CtfeInterpreter::new(&[]);
212 let r = interp.eval_binop(BinOp::Mod, &CtfeValue::Int(5), &CtfeValue::Int(0));
213 assert_eq!(r, Err(CtfeError::DivisionByZero));
214 }
215 #[test]
216 pub(super) fn eval_binop_bool_and() {
217 let interp = CtfeInterpreter::new(&[]);
218 let r = interp.eval_binop(BinOp::And, &CtfeValue::Bool(true), &CtfeValue::Bool(false));
219 assert_eq!(r, Ok(CtfeValue::Bool(false)));
220 }
221 #[test]
222 pub(super) fn eval_binop_comparison_lt() {
223 let interp = CtfeInterpreter::new(&[]);
224 let r = interp.eval_binop(BinOp::Lt, &CtfeValue::Int(2), &CtfeValue::Int(5));
225 assert_eq!(r, Ok(CtfeValue::Bool(true)));
226 }
227 #[test]
228 pub(super) fn eval_binop_string_eq() {
229 let interp = CtfeInterpreter::new(&[]);
230 let r = interp.eval_binop(
231 BinOp::Eq,
232 &CtfeValue::String("abc".to_string()),
233 &CtfeValue::String("abc".to_string()),
234 );
235 assert_eq!(r, Ok(CtfeValue::Bool(true)));
236 }
237 #[test]
238 pub(super) fn eval_expr_return_literal() {
239 let decl = mk_const_decl("forty_two", ret_nat(42));
240 let mut interp = CtfeInterpreter::new(&[decl]);
241 let mut ctx = CtfeContext::new();
242 let r = interp.eval_expr(&mk_const_decl("", ret_nat(42)).body, &mut ctx);
243 assert_eq!(r, Ok(CtfeValue::Int(42)));
244 }
245 #[test]
246 pub(super) fn eval_expr_return_string() {
247 let mut interp = CtfeInterpreter::new(&[]);
248 let mut ctx = CtfeContext::new();
249 let body = ret_str("world");
250 let r = interp.eval_expr(&body, &mut ctx);
251 assert_eq!(r, Ok(CtfeValue::String("world".to_string())));
252 }
253 #[test]
254 pub(super) fn eval_expr_let_binding() {
255 let body = LcnfExpr::Let {
256 id: vid(1),
257 name: "x".to_string(),
258 ty: LcnfType::Nat,
259 value: LcnfLetValue::Lit(LcnfLit::Nat(10)),
260 body: Box::new(LcnfExpr::Return(LcnfArg::Var(vid(1)))),
261 };
262 let mut interp = CtfeInterpreter::new(&[]);
263 let mut ctx = CtfeContext::new();
264 assert_eq!(interp.eval_expr(&body, &mut ctx), Ok(CtfeValue::Int(10)));
265 }
266 #[test]
267 pub(super) fn eval_expr_constructor() {
268 let body = LcnfExpr::Let {
269 id: vid(5),
270 name: "p".to_string(),
271 ty: LcnfType::Nat,
272 value: LcnfLetValue::Ctor(
273 "Pair".to_string(),
274 0,
275 vec![LcnfArg::Lit(LcnfLit::Nat(1)), LcnfArg::Lit(LcnfLit::Nat(2))],
276 ),
277 body: Box::new(LcnfExpr::Return(LcnfArg::Var(vid(5)))),
278 };
279 let mut interp = CtfeInterpreter::new(&[]);
280 let mut ctx = CtfeContext::new();
281 let r = interp
282 .eval_expr(&body, &mut ctx)
283 .expect("r evaluation should succeed");
284 assert_eq!(
285 r,
286 CtfeValue::Constructor(
287 "Pair".to_string(),
288 vec![CtfeValue::Int(1), CtfeValue::Int(2)]
289 )
290 );
291 }
292 #[test]
293 pub(super) fn ctfe_context_fuel_consumption() {
294 let mut ctx = CtfeContext::with_fuel(3);
295 assert!(ctx.consume_fuel().is_ok());
296 assert!(ctx.consume_fuel().is_ok());
297 assert!(ctx.consume_fuel().is_ok());
298 assert!(ctx.consume_fuel().is_err());
299 }
300 #[test]
301 pub(super) fn ctfe_context_stack_overflow() {
302 let mut ctx = CtfeContext::new();
303 ctx.max_depth = 2;
304 assert!(ctx.push_frame().is_ok());
305 assert!(ctx.push_frame().is_ok());
306 assert!(ctx.push_frame().is_err());
307 }
308 #[test]
309 pub(super) fn ctfe_context_bind_lookup() {
310 let mut ctx = CtfeContext::new();
311 ctx.bind_local(vid(3), CtfeValue::Int(99));
312 assert_eq!(ctx.lookup_local(vid(3)), Some(&CtfeValue::Int(99)));
313 assert_eq!(ctx.lookup_local(vid(4)), None);
314 }
315 #[test]
316 pub(super) fn ctfe_pass_empty_module() {
317 let mut pass = CtfePass::default_pass();
318 let mut decls: Vec<LcnfFunDecl> = vec![];
319 pass.run(&mut decls);
320 let r = pass.report();
321 assert_eq!(r.functions_evaluated, 0);
322 assert_eq!(r.calls_replaced, 0);
323 }
324 #[test]
325 pub(super) fn ctfe_pass_evaluates_constant_function() {
326 let decl = mk_const_decl("answer", ret_nat(42));
327 let mut pass = CtfePass::default_pass();
328 let mut decls = vec![decl];
329 pass.run(&mut decls);
330 let r = pass.report();
331 assert_eq!(r.functions_evaluated, 1);
332 assert!(pass.known_constants.contains_key("answer"));
333 assert_eq!(pass.known_constants["answer"], CtfeValue::Int(42));
334 }
335 #[test]
336 pub(super) fn ctfe_pass_skips_parameterised_function() {
337 let decl = mk_decl_with_params(
338 "id_fn",
339 vec![mk_param(0, "x")],
340 LcnfExpr::Return(LcnfArg::Var(vid(0))),
341 );
342 let mut pass = CtfePass::default_pass();
343 let mut decls = vec![decl];
344 pass.run(&mut decls);
345 assert_eq!(pass.report().functions_evaluated, 0);
346 }
347 #[test]
348 pub(super) fn ctfe_pass_report_display() {
349 let r = CtfeReport {
350 functions_evaluated: 5,
351 calls_replaced: 12,
352 constants_propagated: 8,
353 fuel_exhausted_count: 1,
354 };
355 let s = r.to_string();
356 assert!(s.contains("evaluated=5"));
357 assert!(s.contains("replaced=12"));
358 }
359 #[test]
360 pub(super) fn ctfe_config_default() {
361 let cfg = CtfeConfig::default();
362 assert_eq!(cfg.fuel, 10_000);
363 assert_eq!(cfg.max_depth, 256);
364 assert!(cfg.replace_calls);
365 }
366}
367#[allow(dead_code)]
369pub fn ctfe_arith_int(op: &str, a: i64, b: i64) -> Option<CtfeValueExt> {
370 match op {
371 "add" => a.checked_add(b).map(CtfeValueExt::Int),
372 "sub" => a.checked_sub(b).map(CtfeValueExt::Int),
373 "mul" => a.checked_mul(b).map(CtfeValueExt::Int),
374 "div" => {
375 if b != 0 {
376 Some(CtfeValueExt::Int(a / b))
377 } else {
378 None
379 }
380 }
381 "rem" => {
382 if b != 0 {
383 Some(CtfeValueExt::Int(a % b))
384 } else {
385 None
386 }
387 }
388 "eq" => Some(CtfeValueExt::Bool(a == b)),
389 "ne" => Some(CtfeValueExt::Bool(a != b)),
390 "lt" => Some(CtfeValueExt::Bool(a < b)),
391 "le" => Some(CtfeValueExt::Bool(a <= b)),
392 "gt" => Some(CtfeValueExt::Bool(a > b)),
393 "ge" => Some(CtfeValueExt::Bool(a >= b)),
394 "and" => Some(CtfeValueExt::Int(a & b)),
395 "or" => Some(CtfeValueExt::Int(a | b)),
396 "xor" => Some(CtfeValueExt::Int(a ^ b)),
397 "shl" => Some(CtfeValueExt::Int(a << (b & 63))),
398 "shr" => Some(CtfeValueExt::Int(a >> (b & 63))),
399 _ => None,
400 }
401}
402#[allow(dead_code)]
403pub fn ctfe_arith_bool(op: &str, a: bool, b: bool) -> Option<CtfeValueExt> {
404 match op {
405 "and" | "&&" => Some(CtfeValueExt::Bool(a && b)),
406 "or" | "||" => Some(CtfeValueExt::Bool(a || b)),
407 "eq" => Some(CtfeValueExt::Bool(a == b)),
408 "ne" => Some(CtfeValueExt::Bool(a != b)),
409 "xor" => Some(CtfeValueExt::Bool(a ^ b)),
410 _ => None,
411 }
412}
413#[allow(dead_code)]
415pub fn ctfe_values_equal(a: &CtfeValueExt, b: &CtfeValueExt) -> bool {
416 match (a, b) {
417 (CtfeValueExt::Unit, CtfeValueExt::Unit) => true,
418 (CtfeValueExt::Bool(x), CtfeValueExt::Bool(y)) => x == y,
419 (CtfeValueExt::Int(x), CtfeValueExt::Int(y)) => x == y,
420 (CtfeValueExt::Uint(x), CtfeValueExt::Uint(y)) => x == y,
421 (CtfeValueExt::Str(x), CtfeValueExt::Str(y)) => x == y,
422 (CtfeValueExt::Tuple(xs), CtfeValueExt::Tuple(ys)) => {
423 xs.len() == ys.len()
424 && xs
425 .iter()
426 .zip(ys.iter())
427 .all(|(a, b)| ctfe_values_equal(a, b))
428 }
429 (CtfeValueExt::List(xs), CtfeValueExt::List(ys)) => {
430 xs.len() == ys.len()
431 && xs
432 .iter()
433 .zip(ys.iter())
434 .all(|(a, b)| ctfe_values_equal(a, b))
435 }
436 (CtfeValueExt::Constructor(na, va), CtfeValueExt::Constructor(nb, vb)) => {
437 na == nb
438 && va.len() == vb.len()
439 && va
440 .iter()
441 .zip(vb.iter())
442 .all(|(a, b)| ctfe_values_equal(a, b))
443 }
444 _ => false,
445 }
446}
447#[allow(dead_code)]
448pub fn ctfe_value_type(v: &CtfeValueExt) -> CtfeType {
449 match v {
450 CtfeValueExt::Unit => CtfeType::Unit,
451 CtfeValueExt::Bool(_) => CtfeType::Bool,
452 CtfeValueExt::Int(_) => CtfeType::Int,
453 CtfeValueExt::Uint(_) => CtfeType::Uint,
454 CtfeValueExt::Float(_) => CtfeType::Float,
455 CtfeValueExt::Str(_) => CtfeType::Str,
456 CtfeValueExt::Tuple(vs) => CtfeType::Tuple(vs.iter().map(ctfe_value_type).collect()),
457 CtfeValueExt::List(vs) => {
458 if vs.is_empty() {
459 CtfeType::List(Box::new(CtfeType::Unknown))
460 } else {
461 CtfeType::List(Box::new(ctfe_value_type(&vs[0])))
462 }
463 }
464 CtfeValueExt::Constructor(n, _) => CtfeType::Named(n.clone()),
465 CtfeValueExt::Closure { .. } => CtfeType::Named("Closure".to_string()),
466 CtfeValueExt::Opaque => CtfeType::Unknown,
467 }
468}
469#[allow(dead_code)]
471pub fn ctfe_should_inline(entry: &CtfeFuncEntry, depth: usize, fuel: u64) -> bool {
472 if !entry.is_pure {
473 return false;
474 }
475 if entry.is_recursive && depth > 3 {
476 return false;
477 }
478 if fuel < 100 {
479 return false;
480 }
481 true
482}
483#[allow(dead_code)]
485pub fn ctfe_default_features() -> CtfeFeatureFlags {
486 CtfeFeatureFlags {
487 fold_arithmetic: true,
488 fold_boolean: true,
489 fold_string: true,
490 partial_eval: false,
491 memoize: true,
492 }
493}
494#[allow(dead_code)]
496pub const CTFE_PASS_VERSION: &str = "1.0.0";
497#[allow(dead_code)]
499pub const CTFE_MAX_INLINE_DEPTH: usize = 32;
500#[allow(dead_code)]
502pub const CTFE_DEFAULT_STRATEGY: &str = "cbv";