1use alloc::{boxed::Box, rc::Rc, string::String, vec::Vec};
2
3use crate::uplc::ast::{Constant, NamedDeBruijn, Term, Type};
4
5pub mod cost_model;
6mod discharge;
7mod error;
8pub mod eval_result;
9pub mod runtime;
10pub mod value;
11
12use crate::pallas_primitives::conway::Language;
13use cost_model::{ExBudget, StepKind};
14pub use error::Error;
15
16use self::{
17 cost_model::CostModel,
18 runtime::BuiltinRuntime,
19 value::{Env, Value},
20};
21
22enum MachineState {
23 Return(Context, Value),
24 Compute(Context, Env, Term<NamedDeBruijn>),
25 Done(Term<NamedDeBruijn>),
26}
27
28#[derive(Clone)]
29enum Context {
30 FrameAwaitArg(Value, Box<Context>),
31 FrameAwaitFunTerm(Env, Term<NamedDeBruijn>, Box<Context>),
32 FrameAwaitFunValue(Value, Box<Context>),
33 FrameForce(Box<Context>),
34 FrameConstr(
35 Env,
36 usize,
37 Vec<Term<NamedDeBruijn>>,
38 Vec<Value>,
39 Box<Context>,
40 ),
41 FrameCases(Env, Vec<Term<NamedDeBruijn>>, Box<Context>),
42 NoFrame,
43}
44
45pub struct Machine {
46 costs: CostModel,
47 pub ex_budget: ExBudget,
48 slippage: u32,
49 unbudgeted_steps: [u32; 10],
50 pub logs: Vec<String>,
51 version: Language,
52}
53
54impl Machine {
55 pub fn new(
56 version: Language,
57 costs: CostModel,
58 initial_budget: ExBudget,
59 slippage: u32,
60 ) -> Machine {
61 Machine {
62 costs,
63 ex_budget: initial_budget,
64 slippage,
65 unbudgeted_steps: [0; 10],
66 logs: vec![],
67 version,
68 }
69 }
70
71 pub fn run(&mut self, term: Term<NamedDeBruijn>) -> Result<Term<NamedDeBruijn>, Error> {
72 use MachineState::*;
73
74 let startup_budget = self.costs.machine_costs.get(StepKind::StartUp);
75
76 self.spend_budget(startup_budget)?;
77
78 let mut state = Compute(Context::NoFrame, Rc::new(vec![]), term);
79
80 loop {
81 state = match state {
82 Compute(context, env, t) => self.compute(context, env, t)?,
83 Return(context, value) => self.return_compute(context, value)?,
84 Done(t) => {
85 return Ok(t);
86 }
87 };
88 }
89 }
90
91 fn compute(
92 &mut self,
93 context: Context,
94 env: Env,
95 term: Term<NamedDeBruijn>,
96 ) -> Result<MachineState, Error> {
97 match term {
98 Term::Var(name) => {
99 self.step_and_maybe_spend(StepKind::Var)?;
100
101 let val = self.lookup_var(name.as_ref(), &env)?;
102
103 Ok(MachineState::Return(context, val))
104 }
105 Term::Delay(body) => {
106 self.step_and_maybe_spend(StepKind::Delay)?;
107
108 Ok(MachineState::Return(context, Value::Delay(body, env)))
109 }
110 Term::Lambda {
111 parameter_name,
112 body,
113 } => {
114 self.step_and_maybe_spend(StepKind::Lambda)?;
115
116 Ok(MachineState::Return(
117 context,
118 Value::Lambda {
119 parameter_name,
120 body,
121 env,
122 },
123 ))
124 }
125 Term::Apply { function, argument } => {
126 self.step_and_maybe_spend(StepKind::Apply)?;
127
128 Ok(MachineState::Compute(
129 Context::FrameAwaitFunTerm(
130 env.clone(),
131 argument.as_ref().clone(),
132 context.into(),
133 ),
134 env,
135 function.as_ref().clone(),
136 ))
137 }
138 Term::Constant(x) => {
139 self.step_and_maybe_spend(StepKind::Constant)?;
140
141 Ok(MachineState::Return(context, Value::Con(x)))
142 }
143 Term::Force(body) => {
144 self.step_and_maybe_spend(StepKind::Force)?;
145
146 Ok(MachineState::Compute(
147 Context::FrameForce(context.into()),
148 env,
149 body.as_ref().clone(),
150 ))
151 }
152 Term::Error => Err(Error::EvaluationFailure),
153 Term::Builtin(fun) => {
154 self.step_and_maybe_spend(StepKind::Builtin)?;
155
156 let runtime: BuiltinRuntime = fun.into();
157
158 Ok(MachineState::Return(
159 context,
160 Value::Builtin { fun, runtime },
161 ))
162 }
163 Term::Constr { tag, mut fields } => {
164 self.step_and_maybe_spend(StepKind::Constr)?;
165
166 fields.reverse();
167
168 if !fields.is_empty() {
169 let popped_field = fields.pop().unwrap();
170
171 Ok(MachineState::Compute(
172 Context::FrameConstr(env.clone(), tag, fields, vec![], context.into()),
173 env,
174 popped_field,
175 ))
176 } else {
177 Ok(MachineState::Return(
178 context,
179 Value::Constr {
180 tag,
181 fields: vec![],
182 },
183 ))
184 }
185 }
186 Term::Case { constr, branches } => {
187 self.step_and_maybe_spend(StepKind::Case)?;
188
189 Ok(MachineState::Compute(
190 Context::FrameCases(env.clone(), branches, context.into()),
191 env,
192 constr.as_ref().clone(),
193 ))
194 }
195 }
196 }
197
198 fn return_compute(&mut self, context: Context, value: Value) -> Result<MachineState, Error> {
199 match context {
200 Context::NoFrame => {
201 if self.unbudgeted_steps[9] > 0 {
202 self.spend_unbudgeted_steps()?;
203 }
204
205 let term = discharge::value_as_term(value);
206
207 Ok(MachineState::Done(term))
208 }
209 Context::FrameForce(ctx) => self.force_evaluate(*ctx, value),
210 Context::FrameAwaitFunTerm(arg_env, arg, ctx) => Ok(MachineState::Compute(
211 Context::FrameAwaitArg(value, ctx),
212 arg_env,
213 arg,
214 )),
215 Context::FrameAwaitArg(fun, ctx) => self.apply_evaluate(*ctx, fun, value),
216 Context::FrameAwaitFunValue(arg, ctx) => self.apply_evaluate(*ctx, value, arg),
217 Context::FrameConstr(env, tag, mut fields, mut resolved_fields, ctx) => {
218 resolved_fields.push(value);
219
220 if !fields.is_empty() {
221 let popped_field = fields.pop().unwrap();
222
223 Ok(MachineState::Compute(
224 Context::FrameConstr(env.clone(), tag, fields, resolved_fields, ctx),
225 env,
226 popped_field,
227 ))
228 } else {
229 Ok(MachineState::Return(
230 *ctx,
231 Value::Constr {
232 tag,
233 fields: resolved_fields,
234 },
235 ))
236 }
237 }
238 Context::FrameCases(env, branches, ctx) => match value {
239 Value::Constr { tag, fields } => match branches.get(tag) {
240 Some(t) => Ok(MachineState::Compute(
241 transfer_arg_stack(fields, *ctx),
242 env,
243 t.clone(),
244 )),
245 None => Err(Error::MissingCaseBranch(
246 branches,
247 Value::Constr { tag, fields },
248 )),
249 },
250 v => Err(Error::NonConstrScrutinized(v)),
251 },
252 }
253 }
254
255 fn force_evaluate(&mut self, context: Context, value: Value) -> Result<MachineState, Error> {
256 match value {
257 Value::Delay(body, env) => {
258 Ok(MachineState::Compute(context, env, body.as_ref().clone()))
259 }
260 Value::Builtin { fun, mut runtime } => {
261 if runtime.needs_force() {
262 runtime.consume_force();
263
264 let res = if runtime.is_ready() {
265 self.eval_builtin_app(runtime)?
266 } else {
267 Value::Builtin { fun, runtime }
268 };
269
270 Ok(MachineState::Return(context, res))
271 } else {
272 let term = discharge::value_as_term(Value::Builtin { fun, runtime });
273
274 Err(Error::BuiltinTermArgumentExpected(term))
275 }
276 }
277 rest => Err(Error::NonPolymorphicInstantiation(rest)),
278 }
279 }
280
281 fn apply_evaluate(
282 &mut self,
283 context: Context,
284 function: Value,
285 argument: Value,
286 ) -> Result<MachineState, Error> {
287 match function {
288 Value::Lambda { body, mut env, .. } => {
289 let e = Rc::make_mut(&mut env);
290
291 e.push(argument);
292
293 Ok(MachineState::Compute(
294 context,
295 Rc::new(e.clone()),
296 body.as_ref().clone(),
297 ))
298 }
299 Value::Builtin { fun, runtime } => {
300 if runtime.is_arrow() && !runtime.needs_force() {
301 let mut runtime = runtime;
302
303 runtime.push(argument)?;
304
305 let res = if runtime.is_ready() {
306 self.eval_builtin_app(runtime)?
307 } else {
308 Value::Builtin { fun, runtime }
309 };
310
311 Ok(MachineState::Return(context, res))
312 } else {
313 let term = discharge::value_as_term(Value::Builtin { fun, runtime });
314
315 Err(Error::UnexpectedBuiltinTermArgument(term))
316 }
317 }
318 rest => Err(Error::NonFunctionalApplication(rest, argument)),
319 }
320 }
321
322 fn eval_builtin_app(&mut self, runtime: BuiltinRuntime) -> Result<Value, Error> {
323 let cost = runtime.to_ex_budget(&self.costs.builtin_costs)?;
324
325 self.spend_budget(cost)?;
326
327 runtime.call(&self.version, &mut self.logs)
328 }
329
330 fn lookup_var(&mut self, name: &NamedDeBruijn, env: &[Value]) -> Result<Value, Error> {
331 env.get::<usize>(env.len() - usize::from(name.index))
332 .cloned()
333 .ok_or_else(|| Error::OpenTermEvaluated(Term::Var(name.clone().into())))
334 }
335
336 fn step_and_maybe_spend(&mut self, step: StepKind) -> Result<(), Error> {
337 let index = step as u8;
338 self.unbudgeted_steps[index as usize] += 1;
339 self.unbudgeted_steps[9] += 1;
340
341 if self.unbudgeted_steps[9] >= self.slippage {
342 self.spend_unbudgeted_steps()?;
343 }
344
345 Ok(())
346 }
347
348 fn spend_unbudgeted_steps(&mut self) -> Result<(), Error> {
349 for i in 0..self.unbudgeted_steps.len() - 1 {
350 let mut unspent_step_budget =
351 self.costs.machine_costs.get(StepKind::try_from(i as u8)?);
352
353 unspent_step_budget.occurrences(self.unbudgeted_steps[i] as i64);
354
355 self.spend_budget(unspent_step_budget)?;
356
357 self.unbudgeted_steps[i] = 0;
358 }
359
360 self.unbudgeted_steps[9] = 0;
361
362 Ok(())
363 }
364
365 fn spend_budget(&mut self, spend_budget: ExBudget) -> Result<(), Error> {
366 self.ex_budget.mem -= spend_budget.mem;
367 self.ex_budget.cpu -= spend_budget.cpu;
368
369 if self.ex_budget.mem < 0 || self.ex_budget.cpu < 0 {
370 Err(Error::OutOfExError(self.ex_budget))
371 } else {
372 Ok(())
373 }
374 }
375}
376
377fn transfer_arg_stack(mut args: Vec<Value>, ctx: Context) -> Context {
378 if args.is_empty() {
379 ctx
380 } else {
381 let popped_field = args.pop().unwrap();
382
383 transfer_arg_stack(args, Context::FrameAwaitFunValue(popped_field, ctx.into()))
384 }
385}
386
387impl From<&Constant> for Type {
388 fn from(constant: &Constant) -> Self {
389 match constant {
390 Constant::Integer(_) => Type::Integer,
391 Constant::ByteString(_) => Type::ByteString,
392 Constant::String(_) => Type::String,
393 Constant::Unit => Type::Unit,
394 Constant::Bool(_) => Type::Bool,
395 Constant::ProtoList(t, _) => Type::List(Rc::new(t.clone())),
396 Constant::ProtoPair(t1, t2, _, _) => {
397 Type::Pair(Rc::new(t1.clone()), Rc::new(t2.clone()))
398 }
399 Constant::Data(_) => Type::Data,
400 Constant::Bls12_381G1Element(_) => Type::Bls12_381G1Element,
401 Constant::Bls12_381G2Element(_) => Type::Bls12_381G2Element,
402 Constant::Bls12_381MlResult(_) => Type::Bls12_381MlResult,
403 }
404 }
405}
406
407#[cfg(test)]
408mod tests {
409 use num_bigint::BigInt;
410
411 use super::{cost_model::ExBudget, runtime::Compressable};
412 use crate::uplc::{
413 ast::{Constant, NamedDeBruijn, Program, Term},
414 builtins::DefaultFunction,
415 };
416
417 #[test]
418 fn add_big_ints() {
419 let program: Program<NamedDeBruijn> = Program {
420 version: (0, 0, 0),
421 term: Term::Apply {
422 function: Term::Apply {
423 function: Term::Builtin(DefaultFunction::AddInteger).into(),
424 argument: Term::Constant(Constant::Integer(i128::MAX.into()).into()).into(),
425 }
426 .into(),
427 argument: Term::Constant(Constant::Integer(i128::MAX.into()).into()).into(),
428 },
429 };
430
431 let eval_result = program.eval(ExBudget::default());
432
433 let term = eval_result.result().unwrap();
434
435 assert_eq!(
436 term,
437 Term::Constant(
438 Constant::Integer(
439 Into::<BigInt>::into(i128::MAX) + Into::<BigInt>::into(i128::MAX)
440 )
441 .into()
442 )
443 );
444 }
445
446 #[test]
447 fn divide_integer() {
448 let make_program = |fun: DefaultFunction, n: i32, m: i32| Program::<NamedDeBruijn> {
449 version: (0, 0, 0),
450 term: Term::Apply {
451 function: Term::Apply {
452 function: Term::Builtin(fun).into(),
453 argument: Term::Constant(Constant::Integer(n.into()).into()).into(),
454 }
455 .into(),
456 argument: Term::Constant(Constant::Integer(m.into()).into()).into(),
457 },
458 };
459
460 let test_data = vec![
461 (DefaultFunction::DivideInteger, 8, 3, 2),
462 (DefaultFunction::DivideInteger, 8, -3, -3),
463 (DefaultFunction::DivideInteger, -8, 3, -3),
464 (DefaultFunction::DivideInteger, -8, -3, 2),
465 (DefaultFunction::QuotientInteger, 8, 3, 2),
466 (DefaultFunction::QuotientInteger, 8, -3, -2),
467 (DefaultFunction::QuotientInteger, -8, 3, -2),
468 (DefaultFunction::QuotientInteger, -8, -3, 2),
469 (DefaultFunction::RemainderInteger, 8, 3, 2),
470 (DefaultFunction::RemainderInteger, 8, -3, 2),
471 (DefaultFunction::RemainderInteger, -8, 3, -2),
472 (DefaultFunction::RemainderInteger, -8, -3, -2),
473 (DefaultFunction::ModInteger, 8, 3, 2),
474 (DefaultFunction::ModInteger, 8, -3, -1),
475 (DefaultFunction::ModInteger, -8, 3, 1),
476 (DefaultFunction::ModInteger, -8, -3, -2),
477 ];
478
479 for (fun, n, m, result) in test_data {
480 let eval_result = make_program(fun, n, m).eval(ExBudget::default());
481
482 assert_eq!(
483 eval_result.result().unwrap(),
484 Term::Constant(Constant::Integer(result.into()).into())
485 );
486 }
487 }
488
489 #[test]
490 fn case_constr_case_0() {
491 let make_program =
492 |fun: DefaultFunction, tag: usize, n: i32, m: i32| Program::<NamedDeBruijn> {
493 version: (0, 0, 0),
494 term: Term::Case {
495 constr: Term::Constr {
496 tag,
497 fields: vec![
498 Term::Constant(Constant::Integer(n.into()).into()),
499 Term::Constant(Constant::Integer(m.into()).into()),
500 ],
501 }
502 .into(),
503 branches: vec![Term::Builtin(fun), Term::subtract_integer()],
504 },
505 };
506
507 let test_data = vec![
508 (DefaultFunction::AddInteger, 0, 8, 3, 11),
509 (DefaultFunction::AddInteger, 1, 8, 3, 5),
510 ];
511
512 for (fun, tag, n, m, result) in test_data {
513 let eval_result = make_program(fun, tag, n, m).eval(ExBudget::max());
514
515 assert_eq!(
516 eval_result.result().unwrap(),
517 Term::Constant(Constant::Integer(result.into()).into())
518 );
519 }
520 }
521
522 #[test]
523 fn case_constr_case_1() {
524 let make_program = |tag: usize| Program::<NamedDeBruijn> {
525 version: (0, 0, 0),
526 term: Term::Case {
527 constr: Term::Constr {
528 tag,
529 fields: vec![],
530 }
531 .into(),
532 branches: vec![
533 Term::integer(5.into()),
534 Term::integer(10.into()),
535 Term::integer(15.into()),
536 ],
537 },
538 };
539
540 let test_data = vec![(0, 5), (1, 10), (2, 15)];
541
542 for (tag, result) in test_data {
543 let eval_result = make_program(tag).eval(ExBudget::max());
544
545 assert_eq!(
546 eval_result.result().unwrap(),
547 Term::Constant(Constant::Integer(result.into()).into())
548 );
549 }
550 }
551
552 #[test]
553 fn bls_g1_add_associative() {
554 let a = blst::blst_p1::uncompress(&[
555 0xab, 0xd6, 0x18, 0x64, 0xf5, 0x19, 0x74, 0x80, 0x32, 0x55, 0x1e, 0x42, 0xe0, 0xac,
556 0x41, 0x7f, 0xd8, 0x28, 0xf0, 0x79, 0x45, 0x4e, 0x3e, 0x3c, 0x98, 0x91, 0xc5, 0xc2,
557 0x9e, 0xd7, 0xf1, 0x0b, 0xde, 0xcc, 0x04, 0x68, 0x54, 0xe3, 0x93, 0x1c, 0xb7, 0x00,
558 0x27, 0x79, 0xbd, 0x76, 0xd7, 0x1f,
559 ])
560 .unwrap();
561
562 let b = blst::blst_p1::uncompress(&[
563 0x95, 0x0d, 0xfd, 0x33, 0xda, 0x26, 0x82, 0x26, 0x0c, 0x76, 0x03, 0x8d, 0xfb, 0x8b,
564 0xad, 0x6e, 0x84, 0xae, 0x9d, 0x59, 0x9a, 0x3c, 0x15, 0x18, 0x15, 0x94, 0x5a, 0xc1,
565 0xe6, 0xef, 0x6b, 0x10, 0x27, 0xcd, 0x91, 0x7f, 0x39, 0x07, 0x47, 0x9d, 0x20, 0xd6,
566 0x36, 0xce, 0x43, 0x7a, 0x41, 0xf5,
567 ])
568 .unwrap();
569
570 let c = blst::blst_p1::uncompress(&[
571 0xb9, 0x62, 0xfd, 0x0c, 0xc8, 0x10, 0x48, 0xe0, 0xcf, 0x75, 0x57, 0xbf, 0x3e, 0x4b,
572 0x6e, 0xdc, 0x5a, 0xb4, 0xbf, 0xb3, 0xdc, 0x87, 0xf8, 0x3a, 0xf4, 0x28, 0xb6, 0x30,
573 0x07, 0x27, 0xb1, 0x39, 0xc4, 0x04, 0xab, 0x15, 0x9b, 0xdf, 0x2e, 0xae, 0xa3, 0xf6,
574 0x49, 0x90, 0x34, 0x21, 0x53, 0x7f,
575 ])
576 .unwrap();
577
578 let term: Term<NamedDeBruijn> = Term::bls12_381_g1_equal()
579 .apply(
580 Term::bls12_381_g1_add().apply(Term::bls12_381_g1(a)).apply(
581 Term::bls12_381_g1_add()
582 .apply(Term::bls12_381_g1(b))
583 .apply(Term::bls12_381_g1(c)),
584 ),
585 )
586 .apply(
587 Term::bls12_381_g1_add()
588 .apply(
589 Term::bls12_381_g1_add()
590 .apply(Term::bls12_381_g1(a))
591 .apply(Term::bls12_381_g1(b)),
592 )
593 .apply(Term::bls12_381_g1(c)),
594 );
595
596 let program = Program {
597 version: (1, 0, 0),
598 term,
599 };
600
601 let eval_result = program.eval(Default::default());
602
603 let final_term = eval_result.result().unwrap();
604
605 assert_eq!(final_term, Term::bool(true))
606 }
607
608 #[test]
609 fn bls_g2_add_associative() {
610 let a = blst::blst_p1::uncompress(&[
611 0xab, 0xd6, 0x18, 0x64, 0xf5, 0x19, 0x74, 0x80, 0x32, 0x55, 0x1e, 0x42, 0xe0, 0xac,
612 0x41, 0x7f, 0xd8, 0x28, 0xf0, 0x79, 0x45, 0x4e, 0x3e, 0x3c, 0x98, 0x91, 0xc5, 0xc2,
613 0x9e, 0xd7, 0xf1, 0x0b, 0xde, 0xcc, 0x04, 0x68, 0x54, 0xe3, 0x93, 0x1c, 0xb7, 0x00,
614 0x27, 0x79, 0xbd, 0x76, 0xd7, 0x1f,
615 ])
616 .unwrap();
617
618 let b = blst::blst_p1::uncompress(&[
619 0x95, 0x0d, 0xfd, 0x33, 0xda, 0x26, 0x82, 0x26, 0x0c, 0x76, 0x03, 0x8d, 0xfb, 0x8b,
620 0xad, 0x6e, 0x84, 0xae, 0x9d, 0x59, 0x9a, 0x3c, 0x15, 0x18, 0x15, 0x94, 0x5a, 0xc1,
621 0xe6, 0xef, 0x6b, 0x10, 0x27, 0xcd, 0x91, 0x7f, 0x39, 0x07, 0x47, 0x9d, 0x20, 0xd6,
622 0x36, 0xce, 0x43, 0x7a, 0x41, 0xf5,
623 ])
624 .unwrap();
625
626 let c = blst::blst_p1::uncompress(&[
627 0xb9, 0x62, 0xfd, 0x0c, 0xc8, 0x10, 0x48, 0xe0, 0xcf, 0x75, 0x57, 0xbf, 0x3e, 0x4b,
628 0x6e, 0xdc, 0x5a, 0xb4, 0xbf, 0xb3, 0xdc, 0x87, 0xf8, 0x3a, 0xf4, 0x28, 0xb6, 0x30,
629 0x07, 0x27, 0xb1, 0x39, 0xc4, 0x04, 0xab, 0x15, 0x9b, 0xdf, 0x2e, 0xae, 0xa3, 0xf6,
630 0x49, 0x90, 0x34, 0x21, 0x53, 0x7f,
631 ])
632 .unwrap();
633
634 let term: Term<NamedDeBruijn> = Term::bls12_381_g1_equal()
635 .apply(
636 Term::bls12_381_g1_add().apply(Term::bls12_381_g1(a)).apply(
637 Term::bls12_381_g1_add()
638 .apply(Term::bls12_381_g1(b))
639 .apply(Term::bls12_381_g1(c)),
640 ),
641 )
642 .apply(
643 Term::bls12_381_g1_add()
644 .apply(
645 Term::bls12_381_g1_add()
646 .apply(Term::bls12_381_g1(a))
647 .apply(Term::bls12_381_g1(b)),
648 )
649 .apply(Term::bls12_381_g1(c)),
650 );
651
652 let program = Program {
653 version: (1, 0, 0),
654 term,
655 };
656
657 let eval_result = program.eval(Default::default());
658
659 let final_term = eval_result.result().unwrap();
660
661 assert_eq!(final_term, Term::bool(true))
662 }
663}