1use super::interner::CodeGenInterner;
2use crate::{
3 ast::{Constant, Data, Name, NamedDeBruijn, Program, Term, Type},
4 builder::{CONSTR_FIELDS_EXPOSER, CONSTR_INDEX_EXPOSER, INDICES_CONVERTER},
5 builtins::DefaultFunction,
6 machine::{cost_model::ExBudget, runtime::Compressable, value::from_pallas_bigint},
7};
8use blst::{blst_p1, blst_p2};
9use indexmap::IndexMap;
10use itertools::{FoldWhile, Itertools};
11use pallas_primitives::conway::{BigInt, PlutusData};
12use std::{cmp::Ordering, iter, ops::Neg, rc::Rc};
13use strum::IntoEnumIterator;
14
15#[derive(Eq, Hash, PartialEq, Clone, Debug, PartialOrd)]
16pub enum ScopePath {
17 FUNC,
18 ARG,
19}
20
21#[derive(Eq, Hash, PartialEq, Clone, Debug, Default, PartialOrd)]
22pub struct Scope {
23 scope: Vec<ScopePath>,
24}
25
26impl Scope {
27 pub fn new() -> Self {
28 Self { scope: vec![] }
29 }
30
31 pub fn push(&self, path: ScopePath) -> Self {
32 let mut new_scope = self.scope.clone();
33 new_scope.push(path);
34 Self { scope: new_scope }
35 }
36
37 pub fn pop(&self) -> Self {
38 let mut new_scope = self.scope.clone();
39 new_scope.pop();
40 Self { scope: new_scope }
41 }
42
43 pub fn common_ancestor(&self, other: &Scope) -> Self {
44 Self {
45 scope: self
46 .scope
47 .iter()
48 .zip(other.scope.iter())
49 .map_while(|(a, b)| if a == b { Some(a) } else { None })
50 .cloned()
51 .collect_vec(),
52 }
53 }
54
55 pub fn is_common_ancestor(&self, other: &Scope) -> bool {
56 self == &self.common_ancestor(other)
57 }
58}
59
60pub struct IdGen {
61 id: usize,
62}
63
64impl IdGen {
65 pub fn new() -> Self {
66 Self { id: 0 }
67 }
68
69 pub fn next_id(&mut self) -> usize {
70 self.id += 1;
71 self.id
72 }
73}
74
75impl Default for IdGen {
76 fn default() -> Self {
77 Self::new()
78 }
79}
80
81pub const NO_INLINE: &str = "__no_inline__";
82
83#[derive(PartialEq, PartialOrd, Default, Debug, Clone)]
84pub struct VarLookup {
85 found: bool,
86 occurrences: usize,
87 delays: usize,
88 no_inline: bool,
89}
90
91impl VarLookup {
92 pub fn new() -> Self {
93 Self {
94 found: false,
95 occurrences: 0,
96 delays: 0,
97 no_inline: false,
98 }
99 }
100
101 pub fn new_found() -> Self {
102 Self {
103 found: true,
104 occurrences: 1,
105 delays: 0,
106 no_inline: false,
107 }
108 }
109
110 pub fn combine(self, other: Self) -> Self {
111 Self {
112 found: self.found || other.found,
113 occurrences: self.occurrences + other.occurrences,
114 delays: self.delays + other.delays,
115 no_inline: self.no_inline || other.no_inline,
116 }
117 }
118
119 pub fn delay_if_found(self, delay_amount: usize) -> Self {
120 if self.found {
121 Self {
122 found: self.found,
123 occurrences: self.occurrences,
124 delays: self.delays + delay_amount,
125 no_inline: self.no_inline,
126 }
127 } else {
128 self
129 }
130 }
131
132 pub fn no_inline_if_found(self) -> Self {
133 if self.found {
134 Self {
135 found: self.found,
136 occurrences: self.occurrences,
137 delays: self.delays,
138 no_inline: true,
139 }
140 } else {
141 self
142 }
143 }
144}
145
146impl DefaultFunction {
147 pub fn is_order_agnostic_builtin(self) -> bool {
148 matches!(
149 self,
150 DefaultFunction::AddInteger
151 | DefaultFunction::MultiplyInteger
152 | DefaultFunction::EqualsInteger
153 | DefaultFunction::EqualsByteString
154 | DefaultFunction::EqualsString
155 | DefaultFunction::EqualsData
156 | DefaultFunction::Bls12_381_G1_Equal
157 | DefaultFunction::Bls12_381_G2_Equal
158 | DefaultFunction::Bls12_381_G1_Add
159 | DefaultFunction::Bls12_381_G2_Add
160 )
161 }
162 pub fn can_curry_builtin(self) -> bool {
165 matches!(
166 self,
167 DefaultFunction::AddInteger
168 | DefaultFunction::SubtractInteger
169 | DefaultFunction::MultiplyInteger
170 | DefaultFunction::DivideInteger
171 | DefaultFunction::ModInteger
172 | DefaultFunction::QuotientInteger
173 | DefaultFunction::RemainderInteger
174 | DefaultFunction::EqualsInteger
175 | DefaultFunction::EqualsByteString
176 | DefaultFunction::EqualsString
177 | DefaultFunction::EqualsData
178 | DefaultFunction::Bls12_381_G1_Equal
179 | DefaultFunction::Bls12_381_G2_Equal
180 | DefaultFunction::LessThanInteger
181 | DefaultFunction::LessThanEqualsInteger
182 | DefaultFunction::AppendByteString
183 | DefaultFunction::ConsByteString
184 | DefaultFunction::SliceByteString
185 | DefaultFunction::IndexByteString
186 | DefaultFunction::LessThanEqualsByteString
187 | DefaultFunction::LessThanByteString
188 | DefaultFunction::AppendString
189 | DefaultFunction::Bls12_381_G1_Add
190 | DefaultFunction::Bls12_381_G2_Add
191 | DefaultFunction::ConstrData
192 )
193 }
194
195 pub fn is_error_safe(self, arg_stack: &[&Term<Name>]) -> bool {
196 match self {
197 DefaultFunction::AddInteger
198 | DefaultFunction::SubtractInteger
199 | DefaultFunction::MultiplyInteger
200 | DefaultFunction::EqualsInteger
201 | DefaultFunction::LessThanInteger
202 | DefaultFunction::LessThanEqualsInteger
203 | DefaultFunction::IData => arg_stack.iter().all(|arg| {
204 if let Term::Constant(c) = arg {
205 matches!(c.as_ref(), Constant::Integer(_))
206 } else {
207 false
208 }
209 }),
210 DefaultFunction::DivideInteger
211 | DefaultFunction::ModInteger
212 | DefaultFunction::QuotientInteger
213 | DefaultFunction::RemainderInteger => arg_stack.iter().all(|arg| {
214 if let Term::Constant(c) = arg {
215 if let Constant::Integer(i) = c.as_ref() {
216 *i != 0.into()
217 } else {
218 false
219 }
220 } else {
221 false
222 }
223 }),
224 DefaultFunction::LengthOfByteString
225 | DefaultFunction::EqualsByteString
226 | DefaultFunction::AppendByteString
227 | DefaultFunction::LessThanEqualsByteString
228 | DefaultFunction::LessThanByteString
229 | DefaultFunction::BData => arg_stack.iter().all(|arg| {
230 if let Term::Constant(c) = arg {
231 matches!(c.as_ref(), Constant::ByteString(_))
232 } else {
233 false
234 }
235 }),
236
237 DefaultFunction::ConsByteString => {
238 if let (Term::Constant(c), Term::Constant(c2)) = (&arg_stack[0], &arg_stack[1]) {
239 if let (Constant::Integer(i), Constant::ByteString(_)) =
240 (c.as_ref(), c2.as_ref())
241 {
242 i >= &0.into() && i < &256.into()
243 } else {
244 false
245 }
246 } else {
247 false
248 }
249 }
250
251 DefaultFunction::SliceByteString => {
252 if let (Term::Constant(c), Term::Constant(c2), Term::Constant(c3)) =
253 (&arg_stack[0], &arg_stack[1], &arg_stack[2])
254 {
255 matches!(
256 (c.as_ref(), c2.as_ref(), c3.as_ref()),
257 (
258 Constant::Integer(_),
259 Constant::Integer(_),
260 Constant::ByteString(_)
261 )
262 )
263 } else {
264 false
265 }
266 }
267
268 DefaultFunction::IndexByteString => {
269 if let (Term::Constant(c), Term::Constant(c2)) = (&arg_stack[0], &arg_stack[1]) {
270 if let (Constant::ByteString(bs), Constant::Integer(i)) =
271 (c.as_ref(), c2.as_ref())
272 {
273 i >= &0.into() && i < &bs.len().into()
274 } else {
275 false
276 }
277 } else {
278 false
279 }
280 }
281
282 DefaultFunction::EqualsString
283 | DefaultFunction::AppendString
284 | DefaultFunction::EncodeUtf8 => arg_stack.iter().all(|arg| {
285 if let Term::Constant(c) = arg {
286 matches!(c.as_ref(), Constant::String(_))
287 } else {
288 false
289 }
290 }),
291
292 DefaultFunction::EqualsData | DefaultFunction::SerialiseData => {
293 arg_stack.iter().all(|arg| {
294 if let Term::Constant(c) = arg {
295 matches!(c.as_ref(), Constant::Data(_))
296 } else {
297 false
298 }
299 })
300 }
301
302 DefaultFunction::Bls12_381_G1_Equal | DefaultFunction::Bls12_381_G1_Add => {
303 arg_stack.iter().all(|arg| {
304 if let Term::Constant(c) = arg {
305 matches!(c.as_ref(), Constant::Bls12_381G1Element(_))
306 } else {
307 false
308 }
309 })
310 }
311
312 DefaultFunction::Bls12_381_G2_Equal | DefaultFunction::Bls12_381_G2_Add => {
313 arg_stack.iter().all(|arg| {
314 if let Term::Constant(c) = arg {
315 matches!(c.as_ref(), Constant::Bls12_381G2Element(_))
316 } else {
317 false
318 }
319 })
320 }
321
322 DefaultFunction::ConstrData => {
323 if let (Term::Constant(c), Term::Constant(c2)) = (&arg_stack[0], &arg_stack[1]) {
324 if let (Constant::Integer(i), Constant::ProtoList(Type::Data, _)) =
325 (c.as_ref(), c2.as_ref())
326 {
327 i >= &0.into()
328 } else {
329 false
330 }
331 } else {
332 false
333 }
334 }
335
336 _ => false,
337 }
338 }
339
340 pub fn wrapped_name(self) -> String {
341 format!("__{}_wrapped", self.aiken_name())
342 }
343}
344pub fn forceable_wrapped_names() -> Vec<String> {
345 DefaultFunction::iter()
346 .filter(|df| df.force_count() > 0)
347 .map(|df| df.wrapped_name())
348 .collect_vec()
349}
350
351#[derive(PartialEq, Clone, Debug)]
352pub enum BuiltinArgs {
353 TwoArgs {
354 fst: (usize, Term<Name>),
355 snd: Option<(usize, Term<Name>)>,
356 },
357 ThreeArgs {
358 fst: (usize, Term<Name>),
359 snd: Option<(usize, Term<Name>)>,
360 thd: Option<(usize, Term<Name>)>,
361 },
362 TwoArgsAnyOrder {
363 fst: (usize, Term<Name>),
364 snd: Option<(usize, Term<Name>)>,
365 },
366}
367
368impl BuiltinArgs {
369 fn args_from_arg_stack(stack: Vec<(usize, Term<Name>)>, func: DefaultFunction) -> Self {
370 let error_safe = false;
371
372 let mut ordered_arg_stack = stack.into_iter().sorted_by(|(_, arg1), (_, arg2)| {
373 if func.is_order_agnostic_builtin() {
375 if matches!(arg1, Term::Constant(_)) == matches!(arg2, Term::Constant(_)) {
376 Ordering::Equal
377 } else if matches!(arg1, Term::Constant(_)) {
378 Ordering::Less
379 } else {
380 Ordering::Greater
381 }
382 } else {
383 Ordering::Equal
384 }
385 });
386
387 if ordered_arg_stack.len() == 2 && func.is_order_agnostic_builtin() {
388 BuiltinArgs::TwoArgsAnyOrder {
391 fst: ordered_arg_stack.next().unwrap(),
392 snd: if error_safe {
393 ordered_arg_stack.next()
394 } else {
395 None
396 },
397 }
398 } else if ordered_arg_stack.len() == 2 {
399 BuiltinArgs::TwoArgs {
400 fst: ordered_arg_stack.next().unwrap(),
401 snd: if error_safe {
402 ordered_arg_stack.next()
403 } else {
404 None
405 },
406 }
407 } else {
408 BuiltinArgs::ThreeArgs {
409 fst: ordered_arg_stack.next().unwrap(),
410 snd: ordered_arg_stack.next(),
411 thd: if error_safe {
412 ordered_arg_stack.next()
413 } else {
414 None
415 },
416 }
417 }
418 }
419
420 fn args_to_curried_args(self, builtin: DefaultFunction) -> CurriedBuiltin {
421 let args = match self {
422 BuiltinArgs::TwoArgs { fst, snd } | BuiltinArgs::TwoArgsAnyOrder { fst, snd } => {
423 CurriedArgs::TwoArgs {
424 fst_args: vec![CurriedNode {
425 id: fst.0,
426 term: fst.1,
427 }],
428 snd_args: snd
429 .into_iter()
430 .map(|item| CurriedNode {
431 id: item.0,
432 term: item.1,
433 })
434 .collect_vec(),
435 }
436 }
437 BuiltinArgs::ThreeArgs { fst, snd, thd } => CurriedArgs::ThreeArgs {
438 fst_args: vec![CurriedNode {
439 id: fst.0,
440 term: fst.1,
441 }],
442 snd_args: snd
443 .into_iter()
444 .map(|item| CurriedNode {
445 id: item.0,
446 term: item.1,
447 })
448 .collect_vec(),
449 thd_args: thd
450 .into_iter()
451 .map(|item| CurriedNode {
452 id: item.0,
453 term: item.1,
454 })
455 .collect_vec(),
456 },
457 };
458
459 CurriedBuiltin {
460 func: builtin,
461 args,
462 }
463 }
464
465 pub fn get_id_args(self) -> Vec<UplcNode> {
466 match self {
467 BuiltinArgs::TwoArgs { fst, snd } | BuiltinArgs::TwoArgsAnyOrder { fst, snd } => {
468 iter::once(fst)
469 .chain(snd)
470 .map(|item| UplcNode {
471 applied_id: item.0,
472 curried_id: item.0,
473 term: item.1,
474 })
475 .collect_vec()
476 }
477 BuiltinArgs::ThreeArgs { fst, snd, thd } => iter::once(fst)
478 .chain(snd)
479 .chain(thd)
480 .map(|item| UplcNode {
481 applied_id: item.0,
482 curried_id: item.0,
483 term: item.1,
484 })
485 .collect_vec(),
486 }
487 }
488}
489
490#[derive(PartialEq, Clone, Debug)]
491pub struct CurriedNode {
492 id: usize,
493 term: Term<Name>,
494}
495
496#[derive(PartialEq, Clone, Debug)]
497pub struct UplcNode {
498 applied_id: usize,
499 curried_id: usize,
500 term: Term<Name>,
501}
502
503#[derive(Eq, Hash, PartialEq, Clone, Debug)]
504pub struct CurriedName {
505 func_name: String,
506 id_vec: Vec<usize>,
507}
508
509impl CurriedName {
510 pub fn len(&self) -> usize {
511 self.id_vec.len()
512 }
513
514 pub fn is_empty(&self) -> bool {
515 self.len() == 0
516 }
517}
518
519#[derive(PartialEq, Clone, Debug)]
520pub enum CurriedArgs {
521 TwoArgs {
522 fst_args: Vec<CurriedNode>,
523 snd_args: Vec<CurriedNode>,
524 },
525 ThreeArgs {
526 fst_args: Vec<CurriedNode>,
527 snd_args: Vec<CurriedNode>,
528 thd_args: Vec<CurriedNode>,
529 },
530}
531
532impl CurriedArgs {
533 pub fn merge_node_by_path(self, path: BuiltinArgs) -> Self {
534 match (self, path) {
535 (
536 CurriedArgs::TwoArgs {
537 mut fst_args,
538 mut snd_args,
539 },
540 BuiltinArgs::TwoArgs { fst, snd },
541 ) => {
542 let fst_args = match fst_args.iter_mut().find(|item| item.term == fst.1) {
543 None => {
544 fst_args.push(CurriedNode {
545 id: fst.0,
546 term: fst.1,
547 });
548 fst_args
549 }
550 _ => fst_args,
551 };
552
553 let snd_args = match snd_args.iter_mut().find(|item| match &snd {
554 Some(snd) => item.term == snd.1,
555 None => false,
556 }) {
557 None => snd_args
558 .into_iter()
559 .chain(snd.into_iter().map(|item| CurriedNode {
560 id: item.0,
561 term: item.1,
562 }))
563 .collect_vec(),
564 _ => snd_args,
565 };
566
567 CurriedArgs::TwoArgs { fst_args, snd_args }
568 }
569 (
570 CurriedArgs::TwoArgs {
571 mut fst_args,
572 mut snd_args,
573 },
574 BuiltinArgs::TwoArgsAnyOrder { mut fst, snd },
575 ) => {
576 let (switched, fst_args) = if fst_args.iter_mut().any(|item| item.term == fst.1) {
577 (false, fst_args)
578 } else if fst_args.iter_mut().any(|item| match &snd {
579 Some(snd) => item.term == snd.1,
580 None => false,
581 }) {
582 (true, fst_args)
583 } else {
584 fst_args.push(CurriedNode {
585 id: fst.0,
586 term: std::mem::replace(&mut fst.1, Term::Error.force()),
591 });
592
593 (false, fst_args)
594 };
595
596 let snd_args = if switched {
598 assert!(fst.1 != Term::Error.force());
599
600 if snd_args.iter_mut().any(|item| item.term == fst.1) {
601 snd_args
602 } else {
603 snd_args.push(CurriedNode {
604 id: fst.0,
605 term: fst.1,
606 });
607 snd_args
608 }
609 } else if snd_args.iter_mut().any(|item| match &snd {
610 Some(snd) => item.term == snd.1,
611 None => false,
612 }) {
613 snd_args
614 } else {
615 snd_args
616 .into_iter()
617 .chain(snd.into_iter().map(|item| CurriedNode {
618 id: item.0,
619 term: item.1,
620 }))
621 .collect_vec()
622 };
623
624 CurriedArgs::TwoArgs { fst_args, snd_args }
625 }
626 (
627 CurriedArgs::ThreeArgs {
628 mut fst_args,
629 mut snd_args,
630 mut thd_args,
631 },
632 BuiltinArgs::ThreeArgs { fst, snd, thd },
633 ) => {
634 let fst_args = match fst_args.iter_mut().find(|item| item.term == fst.1) {
635 None => {
636 fst_args.push(CurriedNode {
637 id: fst.0,
638 term: fst.1,
639 });
640 fst_args
641 }
642 _ => fst_args,
643 };
644
645 let snd_args = match snd_args.iter_mut().find(|item| match &snd {
646 Some(snd) => item.term == snd.1,
647 None => false,
648 }) {
649 None => snd_args
650 .into_iter()
651 .chain(snd.into_iter().map(|item| CurriedNode {
652 id: item.0,
653 term: item.1,
654 }))
655 .collect_vec(),
656
657 _ => snd_args,
658 };
659
660 let thd_args = match thd_args.iter_mut().find(|item| match &thd {
661 Some(thd) => item.term == thd.1,
662 None => false,
663 }) {
664 None => thd_args
665 .into_iter()
666 .chain(thd.into_iter().map(|item| CurriedNode {
667 id: item.0,
668 term: item.1,
669 }))
670 .collect_vec(),
671
672 _ => thd_args,
673 };
674
675 CurriedArgs::ThreeArgs {
676 fst_args,
677 snd_args,
678 thd_args,
679 }
680 }
681 _ => unreachable!(),
682 }
683 }
684
685 fn get_id_args(&self, path: BuiltinArgs) -> Option<Vec<UplcNode>> {
687 match (self, path) {
688 (CurriedArgs::TwoArgs { fst_args, snd_args }, BuiltinArgs::TwoArgs { fst, snd }) => {
689 let arg = fst_args.iter().find(|item| fst.1 == item.term)?;
690
691 let Some(arg2) = snd_args.iter().find(|item| match &snd {
692 Some(snd) => item.term == snd.1,
693 None => false,
694 }) else {
695 return Some(vec![UplcNode {
696 applied_id: fst.0,
697 curried_id: arg.id,
698 term: arg.term.clone(),
699 }]);
700 };
701
702 Some(vec![
703 UplcNode {
704 applied_id: fst.0,
705 curried_id: arg.id,
706 term: arg.term.clone(),
707 },
708 UplcNode {
709 applied_id: snd.as_ref().unwrap().0,
710 curried_id: arg2.id,
711 term: arg2.term.clone(),
712 },
713 ])
714 }
715 (
716 CurriedArgs::TwoArgs { fst_args, snd_args },
717 BuiltinArgs::TwoArgsAnyOrder { fst, snd },
718 ) => {
719 let mut id_vec = vec![];
720
721 if let Some(arg) = fst_args.iter().find(|item| item.term == fst.1) {
722 id_vec.push(UplcNode {
723 applied_id: fst.0,
724 curried_id: arg.id,
725 term: arg.term.clone(),
726 });
727
728 let Some(arg2) = snd_args.iter().find(|item| match &snd {
729 Some(snd) => snd.1 == item.term,
730 None => false,
731 }) else {
732 return Some(id_vec);
733 };
734
735 id_vec.push(UplcNode {
736 applied_id: snd.as_ref().unwrap().0,
737 curried_id: arg2.id,
738 term: arg2.term.clone(),
739 });
740
741 Some(id_vec)
742 } else if let Some(arg) = fst_args.iter().find(|item| match &snd {
743 Some(snd) => item.term == snd.1,
744 None => false,
745 }) {
746 id_vec.push(UplcNode {
747 applied_id: snd.as_ref().unwrap().0,
748 curried_id: arg.id,
749 term: arg.term.clone(),
750 });
751
752 let Some(arg2) = snd_args.iter().find(|item| item.term == fst.1) else {
753 return Some(id_vec);
754 };
755
756 id_vec.push(UplcNode {
757 applied_id: fst.0,
758 curried_id: arg2.id,
759 term: arg2.term.clone(),
760 });
761
762 Some(id_vec)
763 } else {
764 None
765 }
766 }
767
768 (
769 CurriedArgs::ThreeArgs {
770 fst_args,
771 snd_args,
772 thd_args,
773 },
774 BuiltinArgs::ThreeArgs { fst, snd, thd },
775 ) => {
776 let arg = fst_args.iter().find(|item| fst.1 == item.term)?;
777
778 let Some(arg2) = snd_args.iter().find(|item| match &snd {
779 Some(snd) => item.term == snd.1,
780 None => false,
781 }) else {
782 return Some(vec![UplcNode {
783 applied_id: fst.0,
784 curried_id: arg.id,
785 term: arg.term.clone(),
786 }]);
787 };
788
789 let Some(arg3) = thd_args.iter().find(|item| match &thd {
790 Some(thd) => item.term == thd.1,
791 None => false,
792 }) else {
793 return Some(vec![
794 UplcNode {
795 applied_id: fst.0,
796 curried_id: arg.id,
797 term: arg.term.clone(),
798 },
799 UplcNode {
800 applied_id: snd.as_ref().unwrap().0,
801 curried_id: arg2.id,
802 term: arg2.term.clone(),
803 },
804 ]);
805 };
806
807 Some(vec![
808 UplcNode {
809 applied_id: fst.0,
810 curried_id: arg.id,
811 term: arg.term.clone(),
812 },
813 UplcNode {
814 applied_id: snd.as_ref().unwrap().0,
815 curried_id: arg2.id,
816 term: arg2.term.clone(),
817 },
818 UplcNode {
819 applied_id: thd.as_ref().unwrap().0,
820 curried_id: arg3.id,
821 term: arg3.term.clone(),
822 },
823 ])
824 }
825 _ => unreachable!(),
826 }
827 }
828
829 fn is_flipped(&self, path: &BuiltinArgs) -> bool {
830 match (self, path) {
831 (CurriedArgs::TwoArgs { fst_args, .. }, BuiltinArgs::TwoArgsAnyOrder { fst, snd }) => {
832 if fst_args.iter().any(|item| item.term == fst.1) {
833 false
834 } else {
835 fst_args.iter().any(|item| match &snd {
836 Some(snd) => item.term == snd.1,
837 None => false,
838 })
839 }
840 }
841 _ => false,
842 }
843 }
844}
845#[derive(PartialEq, Clone, Debug)]
846pub struct CurriedBuiltin {
847 pub func: DefaultFunction,
848 pub args: CurriedArgs,
851}
852
853impl CurriedBuiltin {
854 pub fn merge_node_by_path(self, path: BuiltinArgs) -> Self {
855 Self {
856 func: self.func,
857 args: self.args.merge_node_by_path(path),
858 }
859 }
860
861 pub fn get_id_args(&self, path: BuiltinArgs) -> Option<Vec<UplcNode>> {
862 self.args.get_id_args(path)
863 }
864
865 pub fn is_flipped(&self, path: &BuiltinArgs) -> bool {
866 self.args.is_flipped(path)
867 }
868}
869
870#[derive(Debug, Clone)]
871pub struct Context {
872 pub inlined_apply_ids: Vec<usize>,
873 pub constants_to_flip: Vec<usize>,
874 pub write_bits_indices_arg: Vec<usize>,
875 pub builtins_map: IndexMap<DefaultFunction, ()>,
876 pub blst_p1_list: Vec<blst_p1>,
877 pub blst_p2_list: Vec<blst_p2>,
878 pub write_bits_convert: bool,
879 pub node_count: usize,
880}
881
882#[derive(Clone, Debug)]
883pub enum Args {
884 Force(usize),
885 Apply(usize, Term<Name>),
886}
887
888impl Term<Name> {
889 fn traverse_uplc_with_helper(
890 &mut self,
891 scope: &Scope,
892 mut arg_stack: Vec<Args>,
893 id_gen: &mut IdGen,
894 with: &mut impl FnMut(Option<usize>, &mut Term<Name>, Vec<Args>, &Scope, &mut Context),
895 context: &mut Context,
896 inline_lambda: bool,
897 ) {
898 match self {
899 Term::Apply { function, argument } => {
900 let arg = Rc::make_mut(argument);
901
902 arg.traverse_uplc_with_helper(
903 &scope.push(ScopePath::ARG),
904 vec![],
905 id_gen,
906 with,
907 context,
908 inline_lambda,
909 );
910 let apply_id = id_gen.next_id();
911
912 arg_stack.push(Args::Apply(apply_id, arg.clone()));
914
915 let func = Rc::make_mut(function);
916
917 func.traverse_uplc_with_helper(
918 &scope.push(ScopePath::FUNC),
919 arg_stack,
920 id_gen,
921 with,
922 context,
923 inline_lambda,
924 );
925
926 with(Some(apply_id), self, vec![], scope, context);
927 }
928 Term::Force(f) => {
929 let f = Rc::make_mut(f);
930 let force_id = id_gen.next_id();
931
932 arg_stack.push(Args::Force(force_id));
933
934 f.traverse_uplc_with_helper(scope, arg_stack, id_gen, with, context, inline_lambda);
935
936 with(Some(force_id), self, vec![], scope, context);
937 }
938 Term::Delay(d) => {
939 let d = Rc::make_mut(d);
940 let delay_arg = arg_stack
941 .pop()
942 .map(|arg| {
943 assert!(matches!(arg, Args::Force(_)));
944 vec![arg]
945 })
946 .unwrap_or_default();
947
948 d.traverse_uplc_with_helper(scope, arg_stack, id_gen, with, context, inline_lambda);
949
950 with(None, self, delay_arg, scope, context);
951 }
952 Term::Lambda {
953 parameter_name,
954 body,
955 } => {
956 let p = parameter_name.clone();
957
958 let args = if parameter_name.text == NO_INLINE {
961 vec![]
962 } else {
963 arg_stack
964 .pop()
965 .map(|arg| {
966 assert!(matches!(arg, Args::Apply(_, _)));
967 vec![arg]
968 })
969 .unwrap_or_default()
970 };
971
972 if inline_lambda {
973 with(None, self, args, scope, context);
977
978 match self {
979 Term::Lambda {
980 parameter_name,
981 body,
982 } if *parameter_name == p => {
983 let body = Rc::make_mut(body);
984 body.traverse_uplc_with_helper(
985 scope,
986 arg_stack,
987 id_gen,
988 with,
989 context,
990 inline_lambda,
991 );
992 }
993 other => other.traverse_uplc_with_helper(
994 scope,
995 arg_stack,
996 id_gen,
997 with,
998 context,
999 inline_lambda,
1000 ),
1001 }
1002 } else {
1003 let body = Rc::make_mut(body);
1004
1005 body.traverse_uplc_with_helper(
1006 scope,
1007 arg_stack,
1008 id_gen,
1009 with,
1010 context,
1011 inline_lambda,
1012 );
1013
1014 with(None, self, args, scope, context);
1015 }
1016 }
1017
1018 Term::Case { constr, branches } => {
1019 let constr = Rc::make_mut(constr);
1020 constr.traverse_uplc_with_helper(
1021 scope,
1022 vec![],
1023 id_gen,
1024 with,
1025 context,
1026 inline_lambda,
1027 );
1028
1029 if branches.len() == 1 {
1030 branches[0].traverse_uplc_with_helper(
1033 scope,
1034 arg_stack,
1035 id_gen,
1036 with,
1037 context,
1038 inline_lambda,
1039 );
1040 } else {
1041 for branch in branches {
1042 branch.traverse_uplc_with_helper(
1043 scope,
1044 arg_stack.clone(),
1045 id_gen,
1046 with,
1047 context,
1048 inline_lambda,
1049 );
1050 }
1051 }
1052 }
1053 Term::Constr { fields, .. } => {
1054 for field in fields {
1055 field.traverse_uplc_with_helper(
1056 scope,
1057 vec![],
1058 id_gen,
1059 with,
1060 context,
1061 inline_lambda,
1062 );
1063 }
1064 }
1065
1066 Term::Builtin(func) => {
1067 let mut args = vec![];
1068
1069 for _ in 0..(func.arity() + usize::try_from(func.force_count()).unwrap()) {
1070 if let Some(arg) = arg_stack.pop() {
1071 args.push(arg);
1072 }
1073 }
1074 with(None, self, args, scope, context);
1076 }
1077 term => {
1078 with(None, term, vec![], scope, context);
1079 }
1080 }
1081 context.node_count += 1;
1082 }
1083
1084 fn substitute_var(&mut self, original: Rc<Name>, replace_with: &Term<Name>) {
1085 match self {
1086 Term::Var(name) if *name == original => {
1087 *self = replace_with.clone();
1088 }
1089 Term::Delay(body) => Rc::make_mut(body).substitute_var(original, replace_with),
1090 Term::Lambda {
1091 parameter_name,
1092 body,
1093 } if *parameter_name != original => {
1094 Rc::make_mut(body).substitute_var(original, replace_with);
1095 }
1096 Term::Apply { function, argument } => {
1097 Rc::make_mut(function).substitute_var(original.clone(), replace_with);
1098 Rc::make_mut(argument).substitute_var(original, replace_with);
1099 }
1100 Term::Force(f) => {
1101 Rc::make_mut(f).substitute_var(original, replace_with);
1102 }
1103 Term::Case { .. } => todo!(),
1104 Term::Constr { .. } => todo!(),
1105 _ => (),
1106 }
1107 }
1108
1109 fn replace_identity_usage(&mut self, original: Rc<Name>) {
1110 match self {
1111 Term::Delay(body) => {
1112 Rc::make_mut(body).replace_identity_usage(original.clone());
1113 }
1114 Term::Lambda {
1115 parameter_name,
1116 body,
1117 } => {
1118 if *parameter_name != original {
1119 Rc::make_mut(body).replace_identity_usage(original.clone());
1120 }
1121 }
1122 Term::Apply { function, argument } => {
1123 let func = Rc::make_mut(function);
1124 let arg = Rc::make_mut(argument);
1125
1126 func.replace_identity_usage(original.clone());
1127 arg.replace_identity_usage(original.clone());
1128
1129 let Term::Var(name) = &func else {
1130 return;
1131 };
1132
1133 if *name == original {
1134 *self = std::mem::replace(arg, Term::Error.force());
1135 }
1136 }
1137 Term::Force(f) => {
1138 Rc::make_mut(f).replace_identity_usage(original.clone());
1139 }
1140 Term::Case { .. } => todo!(),
1141 Term::Constr { .. } => todo!(),
1142 _ => (),
1143 }
1144 }
1145
1146 fn var_occurrences(
1147 &self,
1148 search_for: Rc<Name>,
1149 mut arg_stack: Vec<()>,
1150 mut force_stack: Vec<()>,
1151 ) -> VarLookup {
1152 match self {
1153 Term::Var(name) => {
1154 if *name == search_for {
1155 VarLookup::new_found()
1156 } else {
1157 VarLookup::new()
1158 }
1159 }
1160 Term::Delay(body) => {
1161 let not_forced = usize::from(force_stack.pop().is_none());
1162
1163 body.var_occurrences(search_for, arg_stack, force_stack)
1164 .delay_if_found(not_forced)
1165 }
1166 Term::Lambda {
1167 parameter_name,
1168 body,
1169 } => {
1170 if parameter_name.text == NO_INLINE {
1171 body.var_occurrences(search_for, arg_stack, force_stack)
1172 .no_inline_if_found()
1173 } else if *parameter_name == search_for {
1174 VarLookup::new()
1175 } else {
1176 let not_applied = usize::from(arg_stack.pop().is_none());
1177 body.var_occurrences(search_for, arg_stack, force_stack)
1178 .delay_if_found(not_applied)
1179 }
1180 }
1181 Term::Apply { function, argument } => {
1182 arg_stack.push(());
1184
1185 let apply_var_occurrence_stack = |term: &Term<Name>, arg_stack: Vec<()>| {
1186 term.var_occurrences(search_for.clone(), arg_stack, force_stack)
1187 };
1188
1189 let apply_var_occurrence_no_stack =
1190 |term: &Term<Name>| term.var_occurrences(search_for.clone(), vec![], vec![]);
1191
1192 if let Term::Apply {
1193 function: next_func,
1194 argument: next_arg,
1195 } = function.as_ref()
1196 {
1197 arg_stack.push(());
1199 next_func.carry_args_to_branch(
1200 next_arg,
1201 argument,
1202 arg_stack,
1203 apply_var_occurrence_stack,
1204 apply_var_occurrence_no_stack,
1205 )
1206 } else {
1207 apply_var_occurrence_stack(function, arg_stack)
1208 .combine(apply_var_occurrence_no_stack(argument))
1209 }
1210 }
1211 Term::Force(x) => {
1212 force_stack.push(());
1213 x.var_occurrences(search_for, arg_stack, force_stack)
1214 }
1215 Term::Case { .. } => todo!(),
1216 Term::Constr { .. } => todo!(),
1217 _ => VarLookup::new(),
1218 }
1219 }
1220
1221 fn carry_args_to_branch(
1226 &self,
1227 then_arg: &Rc<Term<Name>>,
1228 else_arg: &Rc<Term<Name>>,
1229 mut arg_stack: Vec<()>,
1230 var_occurrence_stack: impl FnOnce(&Term<Name>, Vec<()>) -> VarLookup,
1231 var_occurrence_no_stack: impl Fn(&Term<Name>) -> VarLookup,
1232 ) -> VarLookup {
1233 let Term::Apply {
1234 function: builtin,
1235 argument: condition,
1236 } = self
1237 else {
1238 return var_occurrence_stack(self, arg_stack)
1239 .combine(var_occurrence_no_stack(then_arg))
1240 .combine(var_occurrence_no_stack(else_arg));
1241 };
1242
1243 arg_stack.push(());
1245
1246 let Term::Delay(else_arg) = else_arg.as_ref() else {
1247 return var_occurrence_stack(builtin, arg_stack)
1248 .combine(var_occurrence_no_stack(condition))
1249 .combine(var_occurrence_no_stack(then_arg))
1250 .combine(var_occurrence_no_stack(else_arg));
1251 };
1252
1253 let Term::Delay(then_arg) = then_arg.as_ref() else {
1254 return var_occurrence_stack(builtin, arg_stack)
1255 .combine(var_occurrence_no_stack(condition))
1256 .combine(var_occurrence_no_stack(then_arg))
1257 .combine(var_occurrence_no_stack(else_arg));
1258 };
1259
1260 match builtin.as_ref() {
1261 Term::Var(a)
1262 if a.text == DefaultFunction::IfThenElse.wrapped_name()
1263 || a.text == DefaultFunction::ChooseList.wrapped_name() =>
1264 {
1265 if matches!(else_arg.as_ref(), Term::Error) {
1266 arg_stack.pop();
1268 arg_stack.pop();
1269 arg_stack.pop();
1270
1271 var_occurrence_no_stack(condition)
1272 .combine(var_occurrence_stack(then_arg, arg_stack))
1273 } else if matches!(then_arg.as_ref(), Term::Error) {
1274 arg_stack.pop();
1276 arg_stack.pop();
1277 arg_stack.pop();
1278
1279 var_occurrence_no_stack(condition)
1280 .combine(var_occurrence_stack(else_arg, arg_stack))
1281 } else {
1282 var_occurrence_stack(builtin, arg_stack)
1283 .combine(var_occurrence_no_stack(condition))
1284 .combine(var_occurrence_no_stack(then_arg))
1285 .combine(var_occurrence_no_stack(else_arg))
1286 }
1287 }
1288
1289 _ => var_occurrence_stack(builtin, arg_stack)
1290 .combine(var_occurrence_no_stack(condition))
1291 .combine(var_occurrence_no_stack(then_arg))
1292 .combine(var_occurrence_no_stack(else_arg)),
1293 }
1294 }
1295
1296 fn lambda_reducer(
1297 &mut self,
1298 _id: Option<usize>,
1299 mut arg_stack: Vec<Args>,
1300 _scope: &Scope,
1301 context: &mut Context,
1302 ) -> bool {
1303 let mut changed = false;
1304 match self {
1305 Term::Lambda {
1306 parameter_name,
1307 body,
1308 } => {
1309 if let Some(Args::Apply(arg_id, arg_term)) = arg_stack.pop() {
1311 let replace = match &arg_term {
1312 Term::Constant(c) if matches!(c.as_ref(), Constant::String(_)) => false,
1314 Term::Delay(e) if matches!(e.as_ref(), Term::Error) => true,
1317 Term::Lambda { .. } => arg_term.is_a_builtin_wrapper(),
1319 Term::Constant(_) | Term::Var(_) | Term::Builtin(_) => true,
1321
1322 _ => false,
1323 };
1324 changed = replace;
1325
1326 if replace {
1327 let body = Rc::make_mut(body);
1328 context.inlined_apply_ids.push(arg_id);
1329
1330 body.substitute_var(
1331 parameter_name.clone(),
1332 arg_term.pierce_no_inlines_ref(),
1333 );
1334 *self = std::mem::replace(body, Term::Error.force());
1336 }
1337 }
1338 }
1339
1340 Term::Case { .. } => todo!(),
1341 Term::Constr { .. } => todo!(),
1342 _ => (),
1343 };
1344
1345 changed
1346 }
1347
1348 fn builtin_force_reducer(
1350 &mut self,
1351 _id: Option<usize>,
1352 mut arg_stack: Vec<Args>,
1353 _scope: &Scope,
1354 context: &mut Context,
1355 ) {
1356 if let Term::Builtin(func) = self {
1357 arg_stack.reverse();
1358 let has_forces = func.force_count() > 0;
1359 while let Some(Args::Force(id)) = arg_stack.pop() {
1360 context.inlined_apply_ids.push(id);
1361 }
1362
1363 if has_forces {
1364 context.builtins_map.insert(*func, ());
1365 *self = Term::var(func.wrapped_name());
1366 }
1367 }
1368 }
1369
1370 fn bls381_compressor(
1372 &mut self,
1373 _id: Option<usize>,
1374 _arg_stack: Vec<Args>,
1375 _scope: &Scope,
1376 context: &mut Context,
1377 ) {
1378 if let Term::Constant(con) = self {
1379 match con.as_ref() {
1380 Constant::Bls12_381G1Element(blst_p1) => {
1381 if let Some(index) = context
1382 .blst_p1_list
1383 .iter()
1384 .position(|item| item == blst_p1.as_ref())
1385 {
1386 *self = Term::var(format!("blst_p1_index_{index}"));
1387 } else {
1388 context.blst_p1_list.push(*blst_p1.as_ref());
1389 *self =
1390 Term::var(format!("blst_p1_index_{}", context.blst_p1_list.len() - 1));
1391 }
1392 }
1393 Constant::Bls12_381G2Element(blst_p2) => {
1394 if let Some(index) = context
1395 .blst_p2_list
1396 .iter()
1397 .position(|item| item == blst_p2.as_ref())
1398 {
1399 *self = Term::var(format!("blst_p2_index_{index}"));
1400 } else {
1401 context.blst_p2_list.push(*blst_p2.as_ref());
1402 *self =
1403 Term::var(format!("blst_p2_index_{}", context.blst_p2_list.len() - 1));
1404 }
1405 }
1406 _ => (),
1407 }
1408 }
1409 }
1410
1411 fn split_body_lambda(&mut self) {
1416 let mut arg_stack = vec![];
1417 let mut current_term = &mut std::mem::replace(self, Term::Error.force());
1418 let mut unsat_lams = vec![];
1419
1420 let mut function_groups = vec![vec![]];
1421 let mut function_dependencies = vec![vec![]];
1422
1423 loop {
1424 match current_term {
1425 Term::Apply { function, argument } => {
1426 current_term = Rc::make_mut(function);
1427
1428 let arg = Rc::make_mut(argument);
1429
1430 arg.split_body_lambda();
1431
1432 arg_stack.push(Args::Apply(0, std::mem::replace(arg, Term::Error.force())));
1433 }
1434 Term::Lambda {
1435 parameter_name,
1436 body,
1437 } => {
1438 current_term = Rc::make_mut(body);
1439
1440 if let Some(Args::Apply(_, arg)) = arg_stack.pop() {
1441 let names = arg.get_var_names();
1442
1443 let func = (parameter_name.clone(), arg);
1444
1445 if let Some((position, _)) =
1446 function_groups.iter().enumerate().rfind(|named_functions| {
1447 named_functions
1448 .1
1449 .iter()
1450 .any(|(name, _)| names.contains(name))
1451 })
1452 {
1453 let insert_position = position + 1;
1454 if insert_position == function_groups.len() {
1455 function_groups.push(vec![func]);
1456 function_dependencies.push(names);
1457 } else {
1458 function_groups[insert_position].push(func);
1459 function_dependencies[insert_position].extend(names);
1460 }
1461 } else {
1462 function_groups[0].push(func);
1463 function_dependencies[0].extend(names);
1464 }
1465 } else {
1466 unsat_lams.push(parameter_name.clone());
1467 }
1468 }
1469 Term::Force(term) => {
1470 current_term = Rc::make_mut(term);
1471
1472 arg_stack.push(Args::Force(0));
1473 }
1474 Term::Delay(term) => {
1475 Rc::make_mut(term).split_body_lambda();
1476 break;
1477 }
1478 Term::Case { .. } => todo!(),
1479 Term::Constr { .. } => todo!(),
1480 _ => break,
1481 }
1482 }
1483 let mut swap_postions = vec![];
1484
1485 function_groups
1486 .iter()
1487 .enumerate()
1488 .for_each(|(group_index, group)| {
1489 if group.len() <= 3 {
1490 group
1491 .iter()
1492 .enumerate()
1493 .rev()
1494 .for_each(|(item_index, (item_name, _))| {
1495 let current_eligible_position = function_dependencies
1496 .iter()
1497 .enumerate()
1498 .fold_while(group_index, |acc, (new_position, dependencies)| {
1499 if dependencies.contains(item_name) {
1500 FoldWhile::Done(acc)
1501 } else {
1502 FoldWhile::Continue(new_position)
1503 }
1504 })
1505 .into_inner();
1506
1507 if current_eligible_position > group_index {
1508 swap_postions.push((
1509 group_index,
1510 item_index,
1511 current_eligible_position,
1512 ));
1513 }
1514 });
1515 }
1516 });
1517
1518 for (group_index, item_index, swap_index) in swap_postions {
1519 let item = function_groups[group_index].remove(item_index);
1520
1521 function_groups[swap_index].push(item);
1522 }
1523
1524 let term_to_build_on = std::mem::replace(current_term, Term::Error.force());
1525
1526 let term = arg_stack
1528 .into_iter()
1529 .rfold(term_to_build_on, |term, arg| match arg {
1530 Args::Force(_) => term.force(),
1531 Args::Apply(_, arg) => term.apply(arg),
1532 });
1533
1534 let term = function_groups.into_iter().rfold(term, |term, group| {
1535 let term = group.iter().rfold(term, |term, (name, _)| Term::Lambda {
1536 parameter_name: name.clone(),
1537 body: term.into(),
1538 });
1539
1540 group
1541 .into_iter()
1542 .fold(term, |term, (_, arg)| term.apply(arg))
1543 });
1544
1545 let term = unsat_lams
1546 .into_iter()
1547 .rfold(term, |term, name| Term::Lambda {
1548 parameter_name: name.clone(),
1549 body: term.into(),
1550 });
1551
1552 *self = term;
1553 }
1554
1555 fn get_var_names(&self) -> Vec<Rc<Name>> {
1556 let mut names = vec![];
1557
1558 let mut term = self;
1559
1560 loop {
1561 match term {
1562 Term::Apply { function, argument } => {
1563 let arg_names = argument.get_var_names();
1564
1565 names.extend(arg_names);
1566
1567 term = function;
1568 }
1569 Term::Var(name) => {
1570 names.push(name.clone());
1571 break;
1572 }
1573 Term::Delay(t) => {
1574 term = t;
1575 }
1576 Term::Lambda { body, .. } => {
1577 term = body;
1578 }
1579 Term::Constant(_) | Term::Error | Term::Builtin(_) => {
1580 break;
1581 }
1582 Term::Force(t) => {
1583 term = t;
1584 }
1585 Term::Constr { .. } => todo!(),
1586 Term::Case { .. } => todo!(),
1587 }
1588 }
1589
1590 names
1591 }
1592
1593 fn case_constr_apply_reducer(
1595 &mut self,
1596 _id: Option<usize>,
1597 _arg_stack: Vec<Args>,
1598 _scope: &Scope,
1599 _context: &mut Context,
1600 ) {
1601 let mut term = &mut std::mem::replace(self, Term::Error.force());
1602
1603 let mut arg_vec = vec![];
1604
1605 while let Term::Apply { function, argument } = term {
1606 arg_vec.push(Rc::make_mut(argument));
1607
1608 term = Rc::make_mut(function);
1609 }
1610
1611 arg_vec.reverse();
1612
1613 match term {
1614 Term::Case { constr, branches }
1615 if branches.len() == 1 && matches!(constr.as_ref(), Term::Constr { .. }) =>
1616 {
1617 let Term::Constr { fields, .. } = Rc::make_mut(constr) else {
1618 unreachable!();
1619 };
1620
1621 for arg in arg_vec {
1622 fields.push(std::mem::replace(arg, Term::Error.force()));
1623 }
1624
1625 *self = std::mem::replace(term, Term::Error.force());
1626 }
1627 _ => {
1628 if arg_vec.len() > 2 {
1629 let mut fields = vec![];
1630
1631 for arg in arg_vec {
1632 fields.push(std::mem::replace(arg, Term::Error.force()));
1633 }
1634
1635 *self = Term::constr(0, fields)
1636 .case(vec![std::mem::replace(term, Term::Error.force())]);
1637 } else {
1638 for arg in arg_vec {
1639 *term = (std::mem::replace(term, Term::Error.force()))
1640 .apply(std::mem::replace(arg, Term::Error.force()));
1641 }
1642
1643 *self = std::mem::replace(term, Term::Error.force());
1644 }
1645 }
1646 }
1647 }
1648 fn write_bits_convert_arg(
1652 &mut self,
1653 id: Option<usize>,
1654 mut arg_stack: Vec<Args>,
1655 _scope: &Scope,
1656 context: &mut Context,
1657 ) {
1658 match self {
1659 Term::Apply { argument, .. } => {
1660 let id = id.unwrap();
1661
1662 if context.write_bits_indices_arg.contains(&id) {
1663 match Rc::make_mut(argument) {
1664 Term::Constant(constant) => {
1665 let Constant::ProtoList(tipo, items) = Rc::make_mut(constant) else {
1666 unreachable!();
1667 };
1668
1669 assert!(*tipo == Type::Data);
1670 *tipo = Type::Integer;
1671
1672 for item in items {
1673 let Constant::Data(PlutusData::BigInt(i)) = item else {
1674 unreachable!();
1675 };
1676
1677 *item = Constant::Integer(from_pallas_bigint(i));
1678 }
1679 }
1680 arg => {
1681 context.write_bits_convert = true;
1682
1683 *arg = Term::var(INDICES_CONVERTER)
1684 .apply(std::mem::replace(arg, Term::Error.force()));
1685 }
1686 }
1687 }
1688 }
1689
1690 Term::Builtin(DefaultFunction::WriteBits) => {
1691 if arg_stack.is_empty() {
1692 context.write_bits_convert = true;
1693
1694 *self = Term::write_bits()
1695 .apply(Term::var("__arg_1"))
1696 .apply(Term::var(INDICES_CONVERTER).apply(Term::var("__arg_2")))
1697 .apply(Term::var("__arg_3"))
1698 .lambda("__arg_3")
1699 .lambda("__arg_2")
1700 .lambda("__arg_1")
1701 } else {
1702 arg_stack.pop();
1704
1705 let Some(Args::Apply(arg_id, _)) = arg_stack.pop() else {
1706 return;
1707 };
1708
1709 context.write_bits_indices_arg.push(arg_id);
1710 }
1711 }
1712 _ => (),
1713 }
1714 }
1715
1716 fn identity_reducer(
1717 &mut self,
1718 _id: Option<usize>,
1719 mut arg_stack: Vec<Args>,
1720 _scope: &Scope,
1721 context: &mut Context,
1722 ) -> bool {
1723 let mut changed = false;
1724
1725 match self {
1726 Term::Lambda {
1727 parameter_name,
1728 body,
1729 } => {
1730 let body = Rc::make_mut(body);
1731 let Some(Args::Apply(arg_id, identity_func)) = arg_stack.pop() else {
1734 return false;
1735 };
1736
1737 let Term::Lambda {
1738 parameter_name: identity_name,
1739 body: identity_body,
1740 } = identity_func.pierce_no_inlines()
1741 else {
1742 return false;
1743 };
1744
1745 let Term::Var(identity_var) = identity_body.as_ref() else {
1746 return false;
1747 };
1748
1749 if *identity_var == identity_name {
1750 body.replace_identity_usage(parameter_name.clone());
1752 if !body
1755 .var_occurrences(parameter_name.clone(), vec![], vec![])
1756 .found
1757 {
1758 changed = true;
1759 context.inlined_apply_ids.push(arg_id);
1760 *self = std::mem::replace(body, Term::Error.force());
1761 }
1762 }
1763 }
1764 Term::Constr { .. } => todo!(),
1765 Term::Case { .. } => todo!(),
1766 _ => (),
1767 };
1768
1769 changed
1770 }
1771
1772 fn inline_reducer(
1773 &mut self,
1774 _id: Option<usize>,
1775 mut arg_stack: Vec<Args>,
1776 _scope: &Scope,
1777 context: &mut Context,
1778 ) -> bool {
1779 let mut changed = false;
1780
1781 match self {
1782 Term::Lambda {
1783 parameter_name,
1784 body,
1785 } => {
1786 let Some(Args::Apply(arg_id, arg_term)) = arg_stack.pop() else {
1788 return false;
1789 };
1790
1791 let arg_term = arg_term.pierce_no_inlines_ref();
1792
1793 let body = Rc::make_mut(body);
1794
1795 let var_lookup = body.var_occurrences(parameter_name.clone(), vec![], vec![]);
1796
1797 let must_execute_condition = var_lookup.delays == 0 && !var_lookup.no_inline;
1798
1799 let cant_throw_condition = matches!(
1800 arg_term,
1801 Term::Var(_)
1802 | Term::Constant(_)
1803 | Term::Delay(_)
1804 | Term::Lambda { .. }
1805 | Term::Builtin(_),
1806 );
1807
1808 let force_wrapped_builtin = context
1809 .builtins_map
1810 .keys()
1811 .any(|b| b.wrapped_name() == parameter_name.text);
1812
1813 if !force_wrapped_builtin
1816 && var_lookup.occurrences == 1
1817 && (must_execute_condition || cant_throw_condition)
1818 {
1819 changed = true;
1820 body.substitute_var(parameter_name.clone(), arg_term);
1821
1822 context.inlined_apply_ids.push(arg_id);
1823 *self = std::mem::replace(body, Term::Error.force());
1824
1825 } else if !var_lookup.found && (cant_throw_condition || force_wrapped_builtin) {
1827 changed = true;
1828 context.inlined_apply_ids.push(arg_id);
1829 *self = std::mem::replace(body, Term::Error.force());
1830 }
1831 }
1832
1833 Term::Constr { .. } => todo!(),
1834 Term::Case { .. } => todo!(),
1835 _ => {}
1836 };
1837 changed
1838 }
1839
1840 fn force_delay_reducer(
1841 &mut self,
1842 _id: Option<usize>,
1843 mut arg_stack: Vec<Args>,
1844 _scope: &Scope,
1845 context: &mut Context,
1846 ) -> bool {
1847 let mut changed = false;
1848 if let Term::Delay(d) = self {
1849 if let Some(Args::Force(id)) = arg_stack.pop() {
1850 changed = true;
1851 context.inlined_apply_ids.push(id);
1852 *self = std::mem::replace(Rc::make_mut(d), Term::Error.force())
1853 } else if let Term::Force(var) = d.as_ref() {
1854 if let Term::Var(_) = var.as_ref() {
1855 changed = true;
1856 *self = var.as_ref().clone();
1857 }
1858 }
1859 }
1860 changed
1861 }
1862
1863 fn remove_no_inlines(
1864 &mut self,
1865 _id: Option<usize>,
1866 _arg_stack: Vec<Args>,
1867 _scope: &Scope,
1868 _context: &mut Context,
1869 ) {
1870 match self {
1871 Term::Lambda {
1872 parameter_name,
1873 body,
1874 } if parameter_name.text == NO_INLINE => {
1875 *self = std::mem::replace(Rc::make_mut(body), Term::Error.force());
1876 }
1877 _ => (),
1878 }
1879 }
1880
1881 fn inline_constr_ops(
1883 &mut self,
1884 _id: Option<usize>,
1885 _arg_stack: Vec<Args>,
1886 _scope: &Scope,
1887 _context: &mut Context,
1888 ) {
1889 if let Term::Apply { function, argument } = self {
1890 if let Term::Var(name) = function.as_ref() {
1891 let arg = Rc::make_mut(argument);
1892 if name.text == CONSTR_FIELDS_EXPOSER {
1893 *self = Term::snd_pair().apply(
1894 Term::unconstr_data().apply(std::mem::replace(arg, Term::Error.force())),
1895 )
1896 } else if name.text == CONSTR_INDEX_EXPOSER {
1897 *self = Term::fst_pair().apply(
1898 Term::unconstr_data().apply(std::mem::replace(arg, Term::Error.force())),
1899 )
1900 }
1901 } else if let Term::Lambda {
1902 parameter_name,
1903 body,
1904 } = Rc::make_mut(function)
1905 {
1906 if parameter_name.text == CONSTR_INDEX_EXPOSER
1907 || parameter_name.text == CONSTR_FIELDS_EXPOSER
1908 {
1909 let body = Rc::make_mut(body);
1910 *self = std::mem::replace(body, Term::Error)
1911 }
1912 }
1913 }
1914 }
1915
1916 fn cast_data_reducer(
1917 &mut self,
1918 _id: Option<usize>,
1919 mut arg_stack: Vec<Args>,
1920 _scope: &Scope,
1921 context: &mut Context,
1922 ) -> bool {
1923 let mut changed = false;
1924
1925 match self {
1926 Term::Builtin(first_function) => {
1927 let Some(Args::Apply(arg_id, mut arg_term)) = arg_stack.pop() else {
1928 return false;
1929 };
1930
1931 match &mut arg_term {
1932 Term::Apply { function, argument } => {
1933 if let Term::Builtin(second_function) = function.as_ref() {
1934 match (first_function, second_function) {
1935 (DefaultFunction::UnIData, DefaultFunction::IData)
1936 | (DefaultFunction::IData, DefaultFunction::UnIData)
1937 | (DefaultFunction::BData, DefaultFunction::UnBData)
1938 | (DefaultFunction::UnBData, DefaultFunction::BData)
1939 | (DefaultFunction::ListData, DefaultFunction::UnListData)
1940 | (DefaultFunction::UnListData, DefaultFunction::ListData)
1941 | (DefaultFunction::MapData, DefaultFunction::UnMapData)
1942 | (DefaultFunction::UnMapData, DefaultFunction::MapData) => {
1943 changed = true;
1944 context.inlined_apply_ids.push(arg_id);
1945 *self = std::mem::replace(
1946 Rc::make_mut(argument),
1947 Term::Error.force(),
1948 );
1949 }
1950 _ => {}
1951 }
1952 }
1953 }
1954 Term::Constant(c) => match (first_function, c.as_ref()) {
1955 (
1956 DefaultFunction::UnIData,
1957 Constant::Data(PlutusData::BigInt(BigInt::Int(i))),
1958 ) => {
1959 changed = true;
1960 context.inlined_apply_ids.push(arg_id);
1961 *self = Term::integer(i128::from(*i).into());
1962 }
1963 (DefaultFunction::IData, Constant::Integer(i)) => {
1964 changed = true;
1965 context.inlined_apply_ids.push(arg_id);
1966 *self = Term::data(Data::integer(i.clone()));
1967 }
1968 (DefaultFunction::UnBData, Constant::Data(PlutusData::BoundedBytes(b))) => {
1969 changed = true;
1970 context.inlined_apply_ids.push(arg_id);
1971 *self = Term::byte_string(b.clone().into());
1972 }
1973 (DefaultFunction::BData, Constant::ByteString(b)) => {
1974 changed = true;
1975 context.inlined_apply_ids.push(arg_id);
1976 *self = Term::data(Data::bytestring(b.clone()));
1977 }
1978 (DefaultFunction::UnListData, Constant::Data(PlutusData::Array(l))) => {
1979 changed = true;
1980 context.inlined_apply_ids.push(arg_id);
1981 *self = Term::list_values(
1982 l.iter()
1983 .map(|item| Constant::Data(item.clone()))
1984 .collect_vec(),
1985 );
1986 }
1987 (DefaultFunction::ListData, Constant::ProtoList(_, l)) => {
1988 changed = true;
1989 context.inlined_apply_ids.push(arg_id);
1990 *self = Term::data(Data::list(
1991 l.iter()
1992 .map(|item| match item {
1993 Constant::Data(d) => d.clone(),
1994 _ => unreachable!(),
1995 })
1996 .collect_vec(),
1997 ));
1998 }
1999 (DefaultFunction::MapData, Constant::ProtoList(_, m)) => {
2000 changed = true;
2001 context.inlined_apply_ids.push(arg_id);
2002 *self = Term::data(Data::map(
2003 m.iter()
2004 .map(|m| match m {
2005 Constant::ProtoPair(_, _, f, s) => {
2006 match (f.as_ref(), s.as_ref()) {
2007 (Constant::Data(d), Constant::Data(d2)) => {
2008 (d.clone(), d2.clone())
2009 }
2010 _ => unreachable!(),
2011 }
2012 }
2013 _ => unreachable!(),
2014 })
2015 .collect_vec(),
2016 ));
2017 }
2018 (DefaultFunction::UnMapData, Constant::Data(PlutusData::Map(m))) => {
2019 changed = true;
2020 context.inlined_apply_ids.push(arg_id);
2021 *self = Term::map_values(
2022 m.iter()
2023 .map(|item| {
2024 Constant::ProtoPair(
2025 Type::Data,
2026 Type::Data,
2027 Constant::Data(item.0.clone()).into(),
2028 Constant::Data(item.1.clone()).into(),
2029 )
2030 })
2031 .collect_vec(),
2032 );
2033 }
2034 _ => {}
2035 },
2036 _ => {}
2037 }
2038 }
2039 Term::Constr { .. } => todo!(),
2040 Term::Case { .. } => todo!(),
2041 _ => {}
2042 }
2043 changed
2044 }
2045
2046 fn convert_arithmetic_ops(
2048 &mut self,
2049 _id: Option<usize>,
2050 arg_stack: Vec<Args>,
2051 _scope: &Scope,
2052 context: &mut Context,
2053 ) -> bool {
2054 let mut changed = false;
2055 match self {
2056 Term::Builtin(d @ DefaultFunction::SubtractInteger) => {
2057 if arg_stack.len() == d.arity() {
2058 let Some(Args::Apply(apply_id, Term::Constant(_))) = arg_stack.last() else {
2059 return false;
2060 };
2061 changed = true;
2062 context.constants_to_flip.push(*apply_id);
2063
2064 *self = Term::Builtin(DefaultFunction::AddInteger);
2065 }
2066 }
2067 Term::Constr { .. } => todo!(),
2068 Term::Case { .. } => todo!(),
2069 _ => {}
2070 }
2071 changed
2072 }
2073
2074 fn builtin_eval_reducer(
2075 &mut self,
2076 _id: Option<usize>,
2077 mut arg_stack: Vec<Args>,
2078 _scope: &Scope,
2079 context: &mut Context,
2080 ) -> bool {
2081 let mut changed = false;
2082
2083 match self {
2084 Term::Builtin(func) => {
2085 arg_stack = arg_stack
2086 .into_iter()
2087 .filter(|args| matches!(args, Args::Apply(_, _)))
2088 .collect_vec();
2089
2090 let args = arg_stack
2091 .iter()
2092 .map(|args| {
2093 let Args::Apply(_, term) = args else {
2094 unreachable!()
2095 };
2096
2097 term.pierce_no_inlines_ref()
2098 })
2099 .collect_vec();
2100 if arg_stack.len() == func.arity() && func.is_error_safe(&args) {
2101 changed = true;
2102 let applied_term =
2103 arg_stack
2104 .into_iter()
2105 .fold(Term::Builtin(*func), |acc, item| {
2106 let Args::Apply(arg_id, arg) = item else {
2107 unreachable!()
2108 };
2109
2110 context.inlined_apply_ids.push(arg_id);
2111 acc.apply(arg.pierce_no_inlines().clone())
2112 });
2113
2114 let eval_term: Term<Name> = Program {
2116 version: (1, 0, 0),
2117 term: applied_term,
2118 }
2119 .to_named_debruijn()
2120 .unwrap()
2121 .eval(ExBudget::default())
2122 .result()
2123 .unwrap()
2124 .try_into()
2125 .unwrap();
2126
2127 *self = eval_term;
2128 }
2129 }
2130 Term::Constr { .. } => todo!(),
2131 Term::Case { .. } => todo!(),
2132 _ => (),
2133 }
2134 changed
2135 }
2136
2137 fn remove_inlined_ids(
2138 &mut self,
2139 id: Option<usize>,
2140 _arg_stack: Vec<Args>,
2141 _scope: &Scope,
2142 context: &mut Context,
2143 ) {
2144 match self {
2145 Term::Apply { function, .. } | Term::Force(function) => {
2146 let Some(id) = id else {
2148 return;
2149 };
2150
2151 if context.inlined_apply_ids.contains(&id) {
2152 let func = Rc::make_mut(function);
2153 *self = std::mem::replace(func, Term::Error.force());
2154 }
2155 }
2156 _ => (),
2157 }
2158 }
2159
2160 fn flip_constants(
2161 &mut self,
2162 id: Option<usize>,
2163 _arg_stack: Vec<Args>,
2164 _scope: &Scope,
2165 context: &mut Context,
2166 ) {
2167 if let Term::Apply { argument, .. } = self {
2168 let Some(id) = id else {
2169 return;
2170 };
2171
2172 if context.constants_to_flip.contains(&id) {
2173 let Term::Constant(c) = Rc::make_mut(argument) else {
2174 unreachable!();
2175 };
2176
2177 let Constant::Integer(i) = c.as_ref() else {
2178 unreachable!();
2179 };
2180
2181 *c = Constant::Integer(i.neg()).into();
2182 }
2183 }
2184 }
2185
2186 pub fn pierce_no_inlines_ref(&self) -> &Self {
2187 let mut term = self;
2188
2189 while let Term::Lambda {
2190 parameter_name,
2191 body,
2192 } = term
2193 {
2194 if parameter_name.as_ref().text == NO_INLINE {
2195 term = body;
2196 } else {
2197 break;
2198 }
2199 }
2200
2201 term
2202 }
2203
2204 fn pierce_no_inlines(mut self) -> Self {
2205 let term = &mut self;
2206
2207 while let Term::Lambda {
2208 parameter_name,
2209 body,
2210 } = term
2211 {
2212 if parameter_name.as_ref().text == NO_INLINE {
2213 *term = std::mem::replace(Rc::make_mut(body), Term::Error.force());
2214 } else {
2215 break;
2216 }
2217 }
2218
2219 std::mem::replace(term, Term::Error.force())
2220 }
2221
2222 fn is_a_builtin_wrapper(&self) -> bool {
2223 let (names, term) = self.pop_lambdas_and_get_names();
2224
2225 let mut arg_names = vec![];
2226
2227 let mut term = term;
2228
2229 while let Term::Apply { function, argument } = term {
2230 match argument.as_ref() {
2231 Term::Var(name) => arg_names.push(format!("{}_{}", name.text, name.unique)),
2232
2233 Term::Constant(_) => {}
2234 _ => {
2235 return false;
2237 }
2238 }
2239 term = function.as_ref();
2240 }
2241
2242 let func_is_builtin = match term {
2243 Term::Var(name) => forceable_wrapped_names().contains(&name.text),
2244 Term::Builtin(_) => true,
2245 _ => false,
2246 };
2247
2248 arg_names.iter().all(|item| names.contains(item)) && func_is_builtin
2249 }
2250
2251 fn pop_lambdas_and_get_names(&self) -> (Vec<String>, &Term<Name>) {
2252 let mut names = vec![];
2253
2254 let mut term = self;
2255
2256 while let Term::Lambda {
2257 parameter_name,
2258 body,
2259 } = term
2260 {
2261 if parameter_name.text != NO_INLINE {
2262 names.push(format!("{}_{}", parameter_name.text, parameter_name.unique));
2263 }
2264 term = body.as_ref();
2265 }
2266
2267 (names, term)
2268 }
2269}
2270
2271impl Program<Name> {
2272 fn traverse_uplc_with(
2273 self,
2274 inline_lambda: bool,
2275 with: &mut impl FnMut(Option<usize>, &mut Term<Name>, Vec<Args>, &Scope, &mut Context),
2276 ) -> (Self, Context) {
2277 let mut term = self.term;
2278 let scope = Scope::new();
2279 let arg_stack = vec![];
2280 let mut id_gen = IdGen::new();
2281
2282 let mut context = Context {
2283 inlined_apply_ids: vec![],
2284 constants_to_flip: vec![],
2285 write_bits_indices_arg: vec![],
2286 builtins_map: IndexMap::new(),
2287 blst_p1_list: vec![],
2288 blst_p2_list: vec![],
2289 write_bits_convert: false,
2290 node_count: 0,
2291 };
2292
2293 term.traverse_uplc_with_helper(
2294 &scope,
2295 arg_stack,
2296 &mut id_gen,
2297 with,
2298 &mut context,
2299 inline_lambda,
2300 );
2301 (
2302 Program {
2303 version: self.version,
2304 term,
2305 },
2306 context,
2307 )
2308 }
2309 pub fn run_once_pass(self) -> Self {
2311 let (program, context) = self
2314 .traverse_uplc_with(false, &mut |id, term, _arg_stack, scope, context| {
2315 term.inline_constr_ops(id, vec![], scope, context);
2316 })
2317 .0
2318 .traverse_uplc_with(false, &mut |id, term, arg_stack, scope, context| {
2319 term.bls381_compressor(id, vec![], scope, context);
2320 term.builtin_force_reducer(id, arg_stack, scope, context);
2321 term.remove_inlined_ids(id, vec![], scope, context);
2322 });
2323
2324 let mut term = program.term;
2325
2326 for (index, blst_p1) in context.blst_p1_list.into_iter().enumerate() {
2327 let compressed = blst_p1.compress();
2328
2329 term = term
2330 .lambda(format!("blst_p1_index_{index}"))
2331 .apply(Term::bls12_381_g1_uncompress().apply(Term::byte_string(compressed)));
2332 }
2333
2334 for (index, blst_p2) in context.blst_p2_list.into_iter().enumerate() {
2335 let compressed = blst_p2.compress();
2336
2337 term = term
2338 .lambda(format!("blst_p2_index_{index}"))
2339 .apply(Term::bls12_381_g2_uncompress().apply(Term::byte_string(compressed)));
2340 }
2341
2342 for default_func in context.builtins_map.keys().sorted().cloned() {
2343 term = term.lambda(default_func.wrapped_name());
2344 }
2345
2346 for default_func in context.builtins_map.keys().sorted().cloned().rev() {
2347 term = term.apply(if default_func.force_count() == 1 {
2348 Term::Builtin(default_func).force()
2349 } else {
2350 Term::Builtin(default_func).force().force()
2351 });
2352 }
2353
2354 let mut program = Program {
2355 version: program.version,
2356 term,
2357 };
2358
2359 let mut interner = CodeGenInterner::new();
2360
2361 interner.program(&mut program);
2362
2363 let program = Program::<NamedDeBruijn>::try_from(program).unwrap();
2364
2365 Program::<Name>::try_from(program).unwrap()
2366 }
2367
2368 pub fn multi_pass(self) -> (Self, Context) {
2369 self.traverse_uplc_with(true, &mut |id, term, arg_stack, scope, context| {
2370 let false = term.lambda_reducer(id, arg_stack.clone(), scope, context) else {
2371 term.remove_inlined_ids(id, vec![], scope, context);
2372 return;
2373 };
2374
2375 let false = term.identity_reducer(id, arg_stack.clone(), scope, context) else {
2376 term.remove_inlined_ids(id, vec![], scope, context);
2377 return;
2378 };
2379
2380 let false = term.inline_reducer(id, arg_stack.clone(), scope, context) else {
2381 term.remove_inlined_ids(id, vec![], scope, context);
2382 return;
2383 };
2384
2385 let false = term.force_delay_reducer(id, arg_stack.clone(), scope, context) else {
2386 term.remove_inlined_ids(id, vec![], scope, context);
2387 return;
2388 };
2389
2390 let false = term.cast_data_reducer(id, arg_stack.clone(), scope, context) else {
2391 term.remove_inlined_ids(id, vec![], scope, context);
2392 return;
2393 };
2394
2395 let false = term.builtin_eval_reducer(id, arg_stack.clone(), scope, context) else {
2396 term.remove_inlined_ids(id, vec![], scope, context);
2397 return;
2398 };
2399
2400 term.convert_arithmetic_ops(id, arg_stack, scope, context);
2401 term.flip_constants(id, vec![], scope, context);
2402 term.remove_inlined_ids(id, vec![], scope, context);
2403 })
2404 }
2405
2406 pub fn run_one_opt(
2407 self,
2408 inline_lambda: bool,
2409 with: &mut impl FnMut(Option<usize>, &mut Term<Name>, Vec<Args>, &Scope, &mut Context),
2410 ) -> Self {
2411 let (mut program, context) =
2412 self.traverse_uplc_with(inline_lambda, &mut |id, term, arg_stack, scope, context| {
2413 with(id, term, arg_stack, scope, context);
2414 term.flip_constants(id, vec![], scope, context);
2415 term.remove_inlined_ids(id, vec![], scope, context);
2416 });
2417
2418 if context.write_bits_convert {
2419 program.term = program.term.data_list_to_integer_list();
2420 }
2421
2422 program
2423 }
2424
2425 pub fn clean_up_no_inlines(self) -> Self {
2426 self.traverse_uplc_with(true, &mut |id, term, _arg_stack, scope, context| {
2427 term.remove_no_inlines(id, vec![], scope, context);
2428 })
2429 .0
2430 }
2431
2432 pub fn afterwards(self) -> Self {
2433 let (mut program, context) =
2434 self.traverse_uplc_with(true, &mut |id, term, arg_stack, scope, context| {
2435 term.write_bits_convert_arg(id, arg_stack, scope, context);
2436 });
2437
2438 program = program
2439 .split_body_lambda_reducer()
2440 .traverse_uplc_with(true, &mut |id, term, _arg_stack, scope, context| {
2441 term.case_constr_apply_reducer(id, vec![], scope, context);
2442 })
2443 .0;
2444
2445 if context.write_bits_convert {
2446 program.term = program.term.data_list_to_integer_list();
2447 }
2448
2449 let mut interner = CodeGenInterner::new();
2450
2451 interner.program(&mut program);
2452
2453 let program = Program::<NamedDeBruijn>::try_from(program).unwrap();
2454
2455 Program::<Name>::try_from(program).unwrap()
2456 }
2457
2458 pub fn builtin_curry_reducer(self) -> Self {
2460 let mut curried_terms = vec![];
2461 let mut id_mapped_curry_terms: IndexMap<CurriedName, (Scope, Term<Name>, usize)> =
2462 IndexMap::new();
2463 let mut curry_applied_ids = vec![];
2464 let mut scope_mapped_to_term: IndexMap<Scope, Vec<(CurriedName, Term<Name>)>> =
2465 IndexMap::new();
2466
2467 let mut flipped_terms: IndexMap<Scope, bool> = IndexMap::new();
2468
2469 let mut final_ids: IndexMap<Vec<usize>, ()> = IndexMap::new();
2470
2471 let (step_a, _) = self.traverse_uplc_with(
2472 false,
2473 &mut |_id, term, arg_stack, scope, _context| match term {
2474 Term::Builtin(func) => {
2475 if func.can_curry_builtin() && arg_stack.len() == func.arity() {
2476 let arg_stack = arg_stack
2477 .into_iter()
2478 .map(|item| {
2479 let Args::Apply(arg_id, arg) = item else {
2480 unreachable!()
2481 };
2482 (arg_id, arg)
2483 })
2484 .collect_vec();
2485 let builtin_args = BuiltinArgs::args_from_arg_stack(arg_stack, *func);
2489
2490 let mut id_vec = if let Some((index, _)) =
2492 curried_terms.iter_mut().find_position(
2493 |curried_term: &&mut CurriedBuiltin| curried_term.func == *func,
2494 ) {
2495 let curried_builtin = curried_terms.swap_remove(index);
2498
2499 let curried_builtin =
2500 curried_builtin.merge_node_by_path(builtin_args.clone());
2501
2502 flipped_terms
2503 .insert(scope.clone(), curried_builtin.is_flipped(&builtin_args));
2504
2505 let Some(id_vec) = curried_builtin.get_id_args(builtin_args) else {
2506 unreachable!();
2507 };
2508
2509 curried_terms.push(curried_builtin);
2510
2511 id_vec
2512 } else {
2513 let curried_builtin = builtin_args.clone().args_to_curried_args(*func);
2515
2516 let Some(id_vec) = curried_builtin.get_id_args(builtin_args) else {
2517 unreachable!();
2518 };
2519
2520 curried_terms.push(curried_builtin);
2521
2522 id_vec
2523 };
2524
2525 while let Some(node) = id_vec.pop() {
2526 let mut id_only_vec =
2527 id_vec.iter().map(|item| item.curried_id).collect_vec();
2528
2529 id_only_vec.push(node.curried_id);
2530
2531 let curry_name = CurriedName {
2532 func_name: func.aiken_name(),
2533 id_vec: id_only_vec,
2534 };
2535
2536 if let Some((map_scope, _, occurrences)) =
2537 id_mapped_curry_terms.get_mut(&curry_name)
2538 {
2539 *map_scope = map_scope.common_ancestor(scope);
2540 *occurrences += 1;
2541 } else if id_vec.is_empty() {
2542 id_mapped_curry_terms.insert(
2543 curry_name,
2544 (scope.clone(), Term::Builtin(*func).apply(node.term), 1),
2545 );
2546 } else {
2547 let var_name = id_vec_function_to_var(
2548 &func.aiken_name(),
2549 &id_vec.iter().map(|item| item.curried_id).collect_vec(),
2550 );
2551
2552 id_mapped_curry_terms.insert(
2553 curry_name,
2554 (scope.clone(), Term::var(var_name).apply(node.term), 1),
2555 );
2556 }
2557 }
2558 }
2559 }
2560 Term::Constr { .. } => todo!(),
2561 Term::Case { .. } => todo!(),
2562 _ => {}
2563 },
2564 );
2565
2566 id_mapped_curry_terms
2567 .into_iter()
2568 .filter(|(_, (_, _, occurrences))| *occurrences > 2)
2570 .for_each(|(key, val)| {
2571 final_ids.insert(key.id_vec.clone(), ());
2572
2573 match scope_mapped_to_term.get_mut(&val.0) {
2574 Some(list) => {
2575 let insert_position = list
2576 .iter()
2577 .position(|(list_key, _)| key.len() <= list_key.len())
2578 .unwrap_or(list.len());
2579
2580 list.insert(insert_position, (key, val.1));
2581 }
2582 None => {
2583 scope_mapped_to_term.insert(val.0, vec![(key, val.1)]);
2584 }
2585 }
2586 });
2587
2588 let (mut step_b, _) = step_a.traverse_uplc_with(
2589 false,
2590 &mut |id, term, arg_stack, scope, _context| match term {
2591 Term::Builtin(func) => {
2592 if func.can_curry_builtin() && arg_stack.len() == func.arity() {
2593 let mut arg_stack = arg_stack
2594 .into_iter()
2595 .map(|item| {
2596 let Args::Apply(arg_id, arg) = item else {
2597 unreachable!()
2598 };
2599 (arg_id, arg)
2600 })
2601 .collect_vec();
2602
2603 let Some(curried_builtin) =
2604 curried_terms.iter().find(|curry| curry.func == *func)
2605 else {
2606 return;
2607 };
2608
2609 if let Some(true) = flipped_terms.get(scope) {
2610 arg_stack.reverse();
2611 }
2612
2613 let builtin_args = BuiltinArgs::args_from_arg_stack(arg_stack, *func);
2614
2615 let Some(mut id_vec) = curried_builtin.get_id_args(builtin_args) else {
2616 return;
2617 };
2618
2619 while !id_vec.is_empty() {
2620 let id_lookup = id_vec.iter().map(|item| item.curried_id).collect_vec();
2621
2622 if final_ids.contains_key(&id_lookup) {
2623 break;
2624 }
2625 id_vec.pop();
2626 }
2627
2628 if id_vec.is_empty() {
2629 return;
2630 }
2631
2632 let name = id_vec_function_to_var(
2633 &func.aiken_name(),
2634 &id_vec.iter().map(|item| item.curried_id).collect_vec(),
2635 );
2636
2637 id_vec.iter().for_each(|item| {
2638 curry_applied_ids.push(item.applied_id);
2639 });
2640
2641 *term = Term::var(name);
2642 }
2643 }
2644 Term::Apply { function, .. } => {
2645 let id = id.unwrap();
2646
2647 if curry_applied_ids.contains(&id) {
2648 *term = function.as_ref().clone();
2649 }
2650
2651 if let Some(insert_list) = scope_mapped_to_term.remove(scope) {
2652 for (key, val) in insert_list.into_iter().rev() {
2653 let name = id_vec_function_to_var(&key.func_name, &key.id_vec);
2654
2655 if term
2656 .var_occurrences(Name::text(&name).into(), vec![], vec![])
2657 .found
2658 {
2659 *term = term.clone().lambda(name).apply(val);
2660 }
2661 }
2662 }
2663 }
2664 Term::Constr { .. } => todo!(),
2665 Term::Case { .. } => todo!(),
2666 _ => {
2667 if let Some(insert_list) = scope_mapped_to_term.remove(scope) {
2668 for (key, val) in insert_list.into_iter().rev() {
2669 let name = id_vec_function_to_var(&key.func_name, &key.id_vec);
2670
2671 if term
2672 .var_occurrences(Name::text(&name).into(), vec![], vec![])
2673 .found
2674 {
2675 *term = term.clone().lambda(name).apply(val);
2676 }
2677 }
2678 }
2679 }
2680 },
2681 );
2682
2683 let mut interner = CodeGenInterner::new();
2684
2685 interner.program(&mut step_b);
2686
2687 step_b
2688 }
2689
2690 pub fn split_body_lambda_reducer(mut self) -> Self {
2691 self.term.split_body_lambda();
2692
2693 self
2694 }
2695}
2696
2697fn id_vec_function_to_var(func_name: &str, id_vec: &[usize]) -> String {
2698 format!(
2699 "__{}_{}_curried",
2700 func_name,
2701 id_vec
2702 .iter()
2703 .map(|item| item.to_string())
2704 .collect::<Vec<String>>()
2705 .join("_")
2706 )
2707}
2708
2709#[cfg(test)]
2710mod tests {
2711 use super::NO_INLINE;
2712 use crate::{
2713 ast::{Constant, Data, Name, NamedDeBruijn, Program, Term},
2714 builder::{CONSTR_FIELDS_EXPOSER, CONSTR_INDEX_EXPOSER},
2715 builtins::DefaultFunction,
2716 optimize::interner::CodeGenInterner,
2717 };
2718 use pallas_primitives::conway::{BigInt, PlutusData};
2719 use pretty_assertions::assert_eq;
2720
2721 fn compare_optimization(
2722 mut expected: Program<Name>,
2723 mut program: Program<Name>,
2724 optimization: fn(Program<Name>) -> Program<Name>,
2725 ) {
2726 let mut interner = CodeGenInterner::new();
2727
2728 interner.program(&mut program);
2729
2730 let mut interner = CodeGenInterner::new();
2731
2732 interner.program(&mut expected);
2733
2734 let expected: Program<NamedDeBruijn> = expected.try_into().unwrap();
2735 let actual = optimization(program);
2736
2737 let actual: Program<NamedDeBruijn> = actual.try_into().unwrap();
2738
2739 assert_eq!(actual, expected);
2740 }
2741
2742 #[test]
2743 fn lambda_reduce_var() {
2744 let program = Program {
2745 version: (1, 0, 0),
2746 term: Term::var("bar")
2747 .lambda("bar")
2748 .apply(Term::var("foo"))
2749 .lambda("foo")
2750 .apply(
2751 Term::constr_data()
2752 .apply(Term::integer(3.into()))
2753 .apply(Term::list_values(vec![])),
2754 ),
2755 };
2756
2757 let expected = Program {
2758 version: (1, 0, 0),
2759 term: Term::var("foo").lambda("foo").apply(
2760 Term::constr_data()
2761 .apply(Term::integer(3.into()))
2762 .apply(Term::list_values(vec![])),
2763 ),
2764 };
2765
2766 compare_optimization(expected, program, |p| {
2767 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
2768 term.lambda_reducer(id, arg_stack, scope, context);
2769 })
2770 });
2771 }
2772
2773 #[test]
2774 fn lambda_reduce_constant() {
2775 let program = Program {
2776 version: (1, 0, 0),
2777 term: Term::var("foo")
2778 .lambda("foo")
2779 .apply(Term::integer(6.into())),
2780 };
2781
2782 let expected: Program<Name> = Program {
2783 version: (1, 0, 0),
2784 term: Term::integer(6.into()),
2785 };
2786
2787 compare_optimization(expected, program, |p| {
2788 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
2789 term.lambda_reducer(id, arg_stack, scope, context);
2790 })
2791 });
2792 }
2793
2794 #[test]
2795 fn lambda_reduce_builtin() {
2796 let program = Program {
2797 version: (1, 0, 0),
2798 term: Term::var("foo").lambda("foo").apply(Term::add_integer()),
2799 };
2800
2801 let expected: Program<Name> = Program {
2802 version: (1, 0, 0),
2803 term: Term::add_integer(),
2804 };
2805
2806 compare_optimization(expected, program, |p| {
2807 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
2808 term.lambda_reducer(id, arg_stack, scope, context);
2809 })
2810 });
2811 }
2812
2813 #[test]
2814 fn lambda_reduce_force_delay_error_lam() {
2815 let program: Program<Name> = Program {
2816 version: (1, 0, 0),
2817 term: Term::var("foo")
2818 .apply(Term::var("bar"))
2819 .apply(Term::var("baz"))
2820 .apply(Term::var("bat"))
2821 .lambda("foo")
2822 .apply(Term::snd_pair())
2823 .lambda("bar")
2824 .apply(Term::integer(1.into()).delay())
2825 .lambda("baz")
2826 .apply(Term::Error)
2827 .lambda("bat")
2828 .apply(Term::bool(false).lambda("x")),
2829 };
2830
2831 let expected = Program {
2832 version: (1, 0, 0),
2833 term: Term::var("foo")
2834 .apply(Term::var("bar"))
2835 .apply(Term::var("baz"))
2836 .apply(Term::var("bat"))
2837 .lambda("foo")
2838 .apply(Term::snd_pair())
2839 .lambda("bar")
2840 .apply(Term::integer(1.into()).delay())
2841 .lambda("baz")
2842 .apply(Term::Error)
2843 .lambda("bat")
2844 .apply(Term::bool(false).lambda("x")),
2845 };
2846
2847 compare_optimization(expected, program, |p| {
2848 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
2849 term.lambda_reducer(id, arg_stack, scope, context);
2850 })
2851 });
2852 }
2853
2854 #[test]
2855 fn builtin_force_reduce_list_builtins() {
2856 let program: Program<Name> = Program {
2857 version: (1, 0, 0),
2858 term: Term::mk_cons()
2859 .apply(Term::var("x"))
2860 .apply(Term::tail_list().apply(Term::head_list().apply(Term::var("y"))))
2861 .lambda("x")
2862 .lambda("y"),
2863 };
2864
2865 let expected = Program {
2866 version: (1, 0, 0),
2867 term: Term::var("__cons_list_wrapped")
2868 .apply(Term::var("x"))
2869 .apply(
2870 Term::var("__tail_list_wrapped")
2871 .apply(Term::var("__head_list_wrapped").apply(Term::var("y"))),
2872 )
2873 .lambda("x")
2874 .lambda("y")
2875 .lambda("__cons_list_wrapped")
2877 .lambda("__head_list_wrapped")
2878 .lambda("__tail_list_wrapped")
2879 .apply(Term::tail_list())
2880 .apply(Term::head_list())
2881 .apply(Term::mk_cons()),
2882 };
2883
2884 compare_optimization(expected, program, |p| p.run_once_pass());
2885 }
2886
2887 #[test]
2888 fn builtin_force_reduce_if_builtin() {
2889 let program: Program<Name> = Program {
2890 version: (1, 0, 0),
2891 term: Term::equals_integer()
2892 .apply(Term::var("x"))
2893 .apply(
2894 Term::add_integer()
2895 .apply(Term::integer(2.into()))
2896 .apply(Term::var("y")),
2897 )
2898 .delayed_if_then_else(
2899 Term::length_of_bytearray().apply(Term::byte_string(vec![])),
2900 Term::Error,
2901 )
2902 .lambda("x")
2903 .lambda("y"),
2904 };
2905
2906 let expected = Program {
2907 version: (1, 0, 0),
2908 term: Term::var("__if_then_else_wrapped")
2909 .apply(
2910 Term::equals_integer().apply(Term::var("x")).apply(
2911 Term::add_integer()
2912 .apply(Term::integer(2.into()))
2913 .apply(Term::var("y")),
2914 ),
2915 )
2916 .apply(
2917 Term::length_of_bytearray()
2918 .apply(Term::byte_string(vec![]))
2919 .delay(),
2920 )
2921 .apply(Term::Error.delay())
2922 .force()
2923 .lambda("x")
2924 .lambda("y")
2925 .lambda("__if_then_else_wrapped")
2926 .apply(Term::Builtin(DefaultFunction::IfThenElse).force()),
2927 };
2928
2929 compare_optimization(expected, program, |p| p.run_once_pass());
2930 }
2931
2932 #[test]
2933 fn builtin_force_reduce_pair_builtins() {
2934 let program: Program<Name> = Program {
2935 version: (1, 0, 0),
2936 term: Term::add_integer()
2937 .apply(Term::un_i_data().apply(Term::fst_pair().apply(Term::var("__pair"))))
2938 .apply(Term::un_i_data().apply(Term::snd_pair().apply(Term::var("__pair"))))
2939 .lambda("__pair")
2940 .apply(
2941 Term::mk_pair_data()
2942 .apply(Term::data(Data::integer(1.into())))
2943 .apply(Term::data(Data::integer(5.into()))),
2944 ),
2945 };
2946
2947 let expected = Program {
2948 version: (1, 0, 0),
2949 term: Term::add_integer()
2950 .apply(
2951 Term::un_i_data()
2952 .apply(Term::var("__fst_pair_wrapped").apply(Term::var("__pair"))),
2953 )
2954 .apply(
2955 Term::un_i_data()
2956 .apply(Term::var("__snd_pair_wrapped").apply(Term::var("__pair"))),
2957 )
2958 .lambda("__pair")
2959 .apply(
2960 Term::mk_pair_data()
2961 .apply(Term::data(Data::integer(1.into())))
2962 .apply(Term::data(Data::integer(5.into()))),
2963 )
2964 .lambda("__fst_pair_wrapped")
2965 .lambda("__snd_pair_wrapped")
2966 .apply(Term::snd_pair())
2967 .apply(Term::fst_pair()),
2968 };
2969
2970 compare_optimization(expected, program, |p| p.run_once_pass());
2971 }
2972
2973 #[test]
2974 fn identity_reduce_usage() {
2975 let program: Program<Name> = Program {
2976 version: (1, 0, 0),
2977 term: Term::sha2_256()
2978 .apply(Term::var("identity").apply(Term::var("x")))
2979 .lambda("x")
2980 .apply(Term::byte_string(vec![]).delay())
2981 .lambda("identity")
2982 .apply(Term::var("y").lambda("y")),
2983 };
2984
2985 let expected = Program {
2986 version: (1, 0, 0),
2987 term: Term::sha2_256()
2988 .apply(Term::var("x"))
2989 .lambda("x")
2990 .apply(Term::byte_string(vec![]).delay()),
2991 };
2992
2993 compare_optimization(expected, program, |p| {
2994 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
2995 term.identity_reducer(id, arg_stack, scope, context);
2996 })
2997 });
2998 }
2999
3000 #[test]
3001 fn identity_reduce_0_occurrence() {
3002 let program: Program<Name> = Program {
3003 version: (1, 0, 0),
3004 term: Term::sha2_256()
3005 .apply(Term::var("x"))
3006 .lambda("x")
3007 .apply(Term::byte_string(vec![]).delay())
3008 .lambda("identity")
3009 .apply(Term::var("y").lambda("y")),
3010 };
3011
3012 let expected = Program {
3013 version: (1, 0, 0),
3014 term: Term::sha2_256()
3015 .apply(Term::var("x"))
3016 .lambda("x")
3017 .apply(Term::byte_string(vec![]).delay()),
3018 };
3019
3020 compare_optimization(expected, program, |p| {
3021 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3022 term.identity_reducer(id, arg_stack, scope, context);
3023 })
3024 });
3025 }
3026
3027 #[test]
3028 fn identity_reduce_param() {
3029 let program: Program<Name> = Program {
3030 version: (1, 0, 0),
3031 term: Term::sha2_256()
3032 .apply(
3033 Term::var("f")
3034 .apply(Term::var("x"))
3035 .apply(Term::var("identity")),
3036 )
3037 .lambda("x")
3038 .apply(Term::byte_string(vec![]).delay())
3039 .lambda("identity")
3040 .apply(Term::var("y").lambda("y"))
3041 .lambda("f")
3042 .apply(
3043 Term::var("with")
3044 .apply(Term::var("x"))
3045 .lambda("with")
3046 .lambda("x"),
3047 ),
3048 };
3049
3050 let expected = Program {
3051 version: (1, 0, 0),
3052 term: Term::sha2_256()
3053 .apply(
3054 Term::var("f")
3055 .apply(Term::var("x"))
3056 .apply(Term::var("identity")),
3057 )
3058 .lambda("x")
3059 .apply(Term::byte_string(vec![]).delay())
3060 .lambda("identity")
3061 .apply(Term::var("y").lambda("y"))
3062 .lambda("f")
3063 .apply(
3064 Term::var("with")
3065 .apply(Term::var("x"))
3066 .lambda("with")
3067 .lambda("x"),
3068 ),
3069 };
3070
3071 compare_optimization(expected, program, |p| {
3072 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3073 term.identity_reducer(id, arg_stack, scope, context);
3074 })
3075 });
3076 }
3077
3078 #[test]
3079 fn identity_reduce_no_inline() {
3080 let program: Program<Name> = Program {
3081 version: (1, 0, 0),
3082 term: Term::sha2_256()
3083 .apply(Term::var("identity").apply(Term::var("x")))
3084 .lambda("x")
3085 .apply(Term::byte_string(vec![]).delay())
3086 .lambda("identity")
3087 .apply(Term::var("y").lambda("y").lambda(NO_INLINE)),
3088 };
3089
3090 let expected = Program {
3091 version: (1, 0, 0),
3092 term: Term::sha2_256()
3093 .apply(Term::var("x"))
3094 .lambda("x")
3095 .apply(Term::byte_string(vec![]).delay()),
3096 };
3097
3098 compare_optimization(expected, program, |p| {
3099 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3100 term.identity_reducer(id, arg_stack, scope, context);
3101 })
3102 });
3103 }
3104
3105 #[test]
3106 fn identity_reduce_no_inline_2() {
3107 let program: Program<Name> = Program {
3108 version: (1, 0, 0),
3109 term: Term::sha2_256()
3110 .apply(Term::var("identity").apply(Term::var("x")))
3111 .lambda("x")
3112 .apply(Term::byte_string(vec![]).delay())
3113 .lambda(NO_INLINE)
3114 .lambda("identity")
3115 .apply(Term::var("y").lambda("y").lambda(NO_INLINE)),
3116 };
3117
3118 let expected = Program {
3119 version: (1, 0, 0),
3120 term: Term::sha2_256()
3121 .apply(Term::var("x"))
3122 .lambda("x")
3123 .apply(Term::byte_string(vec![]).delay())
3124 .lambda(NO_INLINE),
3125 };
3126
3127 compare_optimization(expected, program, |p| {
3128 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3129 term.identity_reducer(id, arg_stack, scope, context);
3130 })
3131 });
3132 }
3133
3134 #[test]
3135 fn inline_reduce_delay_sha() {
3136 let program: Program<Name> = Program {
3137 version: (1, 0, 0),
3138 term: Term::sha2_256()
3139 .apply(Term::var("x"))
3140 .lambda("x")
3141 .apply(Term::byte_string(vec![]).delay()),
3142 };
3143
3144 let expected = Program {
3145 version: (1, 0, 0),
3146 term: Term::sha2_256().apply(Term::byte_string(vec![]).delay()),
3147 };
3148
3149 compare_optimization(expected, program, |p| {
3150 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3151 term.inline_reducer(id, arg_stack, scope, context);
3152 })
3153 });
3154 }
3155
3156 #[test]
3157 fn inline_reduce_if_then_else_then() {
3158 let program: Program<Name> = Program {
3159 version: (1, 0, 0),
3160 term: Term::var("__if_then_else_wrapped")
3161 .apply(Term::bool(true))
3162 .apply(Term::sha3_256().apply(Term::var("x")).delay())
3163 .apply(Term::Error.delay())
3164 .force()
3165 .lambda("x")
3166 .apply(Term::sha3_256().apply(Term::byte_string(vec![])))
3167 .lambda("__if_then_else_wrapped")
3168 .apply(Term::Builtin(DefaultFunction::IfThenElse).force()),
3169 };
3170
3171 let expected = Program {
3172 version: (1, 0, 0),
3173 term: Term::var("__if_then_else_wrapped")
3174 .apply(Term::bool(true))
3175 .apply(
3176 Term::sha3_256()
3177 .apply(Term::sha3_256().apply(Term::byte_string(vec![])))
3178 .delay(),
3179 )
3180 .apply(Term::Error.delay())
3181 .force()
3182 .lambda("__if_then_else_wrapped")
3183 .apply(Term::Builtin(DefaultFunction::IfThenElse).force()),
3184 };
3185
3186 compare_optimization(expected, program, |p| {
3187 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3188 term.inline_reducer(id, arg_stack, scope, context);
3189 })
3190 });
3191 }
3192
3193 #[test]
3194 fn inline_reduce_if_then_else_else() {
3195 let program: Program<Name> = Program {
3196 version: (1, 0, 0),
3197 term: Term::var("__if_then_else_wrapped")
3198 .apply(Term::bool(true))
3199 .apply(Term::Error.delay())
3200 .apply(Term::sha3_256().apply(Term::var("x")).delay())
3201 .force()
3202 .lambda("x")
3203 .apply(Term::sha3_256().apply(Term::byte_string(vec![])))
3204 .lambda("__if_then_else_wrapped")
3205 .apply(Term::Builtin(DefaultFunction::IfThenElse).force()),
3206 };
3207
3208 let expected = Program {
3209 version: (1, 0, 0),
3210 term: Term::var("__if_then_else_wrapped")
3211 .apply(Term::bool(true))
3212 .apply(Term::Error.delay())
3213 .apply(
3214 Term::sha3_256()
3215 .apply(Term::sha3_256().apply(Term::byte_string(vec![])))
3216 .delay(),
3217 )
3218 .force()
3219 .lambda("__if_then_else_wrapped")
3220 .apply(Term::Builtin(DefaultFunction::IfThenElse).force()),
3221 };
3222
3223 compare_optimization(expected, program, |p| {
3224 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3225 term.inline_reducer(id, arg_stack, scope, context);
3226 })
3227 });
3228 }
3229
3230 #[test]
3231 fn inline_reduce_0_occurrence() {
3232 let program: Program<Name> = Program {
3233 version: (1, 0, 0),
3234 term: Term::sha2_256()
3235 .lambda("x")
3236 .apply(Term::byte_string(vec![]).delay()),
3237 };
3238
3239 let expected = Program {
3240 version: (1, 0, 0),
3241 term: Term::sha2_256(),
3242 };
3243
3244 compare_optimization(expected, program, |p| {
3245 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3246 term.inline_reducer(id, arg_stack, scope, context);
3247 })
3248 });
3249 }
3250
3251 #[test]
3252 fn wrap_data_reduce_i_data() {
3253 let program: Program<Name> = Program {
3254 version: (1, 0, 0),
3255 term: Term::equals_data()
3256 .apply(Term::i_data().apply(Term::un_i_data().apply(Term::Constant(
3257 Constant::Data(PlutusData::BigInt(BigInt::Int(5.into()))).into(),
3258 ))))
3259 .apply(Term::i_data().apply(Term::integer(1.into())))
3260 .lambda("x"),
3261 };
3262
3263 let expected = Program {
3264 version: (1, 0, 0),
3265 term: Term::equals_data()
3266 .apply(Term::Constant(
3267 Constant::Data(PlutusData::BigInt(BigInt::Int(5.into()))).into(),
3268 ))
3269 .apply(Term::data(Data::integer(1.into())))
3270 .lambda("x"),
3271 };
3272
3273 compare_optimization(expected, program, |p| {
3274 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3275 term.cast_data_reducer(id, arg_stack, scope, context);
3276 })
3277 });
3278 }
3279
3280 #[test]
3281 fn wrap_data_reduce_un_i_data() {
3282 let program: Program<Name> = Program {
3283 version: (1, 0, 0),
3284 term: Term::equals_integer()
3285 .apply(Term::un_i_data().apply(Term::i_data().apply(Term::integer(1.into()))))
3286 .apply(Term::un_i_data().apply(Term::Constant(
3287 Constant::Data(PlutusData::BigInt(BigInt::Int(5.into()))).into(),
3288 )))
3289 .lambda("x"),
3290 };
3291
3292 let expected = Program {
3293 version: (1, 0, 0),
3294 term: Term::equals_integer()
3295 .apply(Term::integer(1.into()))
3296 .apply(Term::integer(5.into()))
3297 .lambda("x"),
3298 };
3299
3300 compare_optimization(expected, program, |p| {
3301 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3302 term.cast_data_reducer(id, arg_stack, scope, context);
3303 })
3304 });
3305 }
3306
3307 #[test]
3308 fn curry_reducer_test_1() {
3309 let program: Program<Name> = Program {
3310 version: (1, 0, 0),
3311 term: Term::add_integer()
3312 .apply(Term::var("x"))
3313 .apply(Term::integer(1.into()))
3314 .lambda("x")
3315 .apply(
3316 Term::add_integer()
3317 .apply(Term::integer(1.into()))
3318 .apply(Term::var("y")),
3319 )
3320 .lambda("y")
3321 .apply(
3322 Term::add_integer()
3323 .apply(Term::var("g"))
3324 .apply(Term::integer(1.into())),
3325 )
3326 .lambda("g"),
3327 };
3328
3329 let expected = Program {
3330 version: (1, 0, 0),
3331 term: Term::var("add_one_curried")
3332 .apply(Term::var("x"))
3333 .lambda("x")
3334 .apply(Term::var("add_one_curried").apply(Term::var("y")))
3335 .lambda("y")
3336 .apply(Term::var("add_one_curried").apply(Term::var("g")))
3337 .lambda("add_one_curried")
3338 .apply(Term::add_integer().apply(Term::integer(1.into())))
3339 .lambda("g"),
3340 };
3341
3342 compare_optimization(expected, program, |p| p.builtin_curry_reducer());
3343 }
3344
3345 #[test]
3346 fn curry_reducer_test_2() {
3347 let program: Program<Name> = Program {
3348 version: (1, 0, 0),
3349 term: Term::add_integer()
3350 .apply(Term::var("x"))
3351 .apply(Term::integer(1.into()))
3352 .lambda("x")
3353 .apply(
3354 Term::add_integer()
3355 .apply(Term::integer(1.into()))
3356 .apply(Term::var("y")),
3357 )
3358 .lambda("y")
3359 .apply(Term::integer(5.into())),
3360 };
3361
3362 let expected = Program {
3363 version: (1, 0, 0),
3364 term: Term::add_integer()
3365 .apply(Term::var("x"))
3366 .apply(Term::integer(1.into()))
3367 .lambda("x")
3368 .apply(
3369 Term::add_integer()
3370 .apply(Term::integer(1.into()))
3371 .apply(Term::var("y")),
3372 )
3373 .lambda("y")
3374 .apply(Term::integer(5.into())),
3375 };
3376
3377 compare_optimization(expected, program, |p| p.builtin_curry_reducer());
3378 }
3379
3380 #[test]
3381 fn curry_reducer_test_3() {
3382 let program: Program<Name> = Program {
3383 version: (1, 0, 0),
3384 term: Term::var("equivalence")
3385 .lambda("equivalence")
3386 .apply(
3387 Term::equals_integer()
3388 .apply(Term::integer(0.into()))
3389 .apply(Term::var(CONSTR_INDEX_EXPOSER).apply(Term::var("tuple_index_0")))
3390 .if_then_else(
3391 Term::equals_integer()
3392 .apply(Term::integer(0.into()))
3393 .apply(
3394 Term::var(CONSTR_INDEX_EXPOSER)
3395 .apply(Term::var("tuple_index_1")),
3396 )
3397 .if_then_else(
3398 Term::equals_integer()
3399 .apply(
3400 Term::subtract_integer()
3401 .apply(Term::var("x2"))
3402 .apply(Term::var("x1")),
3403 )
3404 .apply(Term::integer(0.into()))
3405 .delayed_if_then_else(
3406 Term::equals_integer()
3407 .apply(
3408 Term::subtract_integer()
3409 .apply(Term::var("y2"))
3410 .apply(Term::var("y1")),
3411 )
3412 .apply(Term::integer(0.into())),
3413 Term::bool(false),
3414 )
3415 .lambda("x2")
3416 .apply(Term::un_i_data().apply(
3417 Term::fst_pair().apply(Term::var("field_0_pair")),
3418 ))
3419 .lambda("y2")
3420 .apply(Term::un_i_data().apply(
3421 Term::snd_pair().apply(Term::var("field_0_pair")),
3422 ))
3423 .lambda("field_0_pair")
3424 .apply(
3425 Term::mk_pair_data()
3426 .apply(
3427 Term::head_list()
3428 .apply(Term::var("__list_data")),
3429 )
3430 .apply(Term::head_list().apply(Term::var("__tail")))
3431 .lambda("__tail")
3432 .apply(
3433 Term::tail_list()
3434 .apply(Term::var("__list_data")),
3435 )
3436 .lambda("__list_data")
3437 .apply(
3438 Term::unlist_data().apply(
3439 Term::head_list().apply(Term::var(
3440 "tuple_index_1_fields",
3441 )),
3442 ),
3443 ),
3444 )
3445 .lambda("tuple_index_1_fields")
3446 .apply(
3447 Term::var(CONSTR_FIELDS_EXPOSER)
3448 .apply(Term::var("tuple_index_1")),
3449 )
3450 .delay(),
3451 Term::var("clauses_delayed"),
3452 )
3453 .force()
3454 .lambda("x1")
3455 .apply(
3456 Term::un_i_data()
3457 .apply(Term::fst_pair().apply(Term::var("field_0_pair"))),
3458 )
3459 .lambda("y1")
3460 .apply(
3461 Term::un_i_data()
3462 .apply(Term::snd_pair().apply(Term::var("field_0_pair"))),
3463 )
3464 .lambda("field_0_pair")
3465 .apply(
3466 Term::mk_pair_data()
3467 .apply(Term::head_list().apply(Term::var("__list_data")))
3468 .apply(Term::head_list().apply(Term::var("__tail")))
3469 .lambda("__tail")
3470 .apply(Term::tail_list().apply(Term::var("__list_data")))
3471 .lambda("__list_data")
3472 .apply(
3473 Term::unlist_data().apply(
3474 Term::head_list()
3475 .apply(Term::var("tuple_index_0_fields")),
3476 ),
3477 ),
3478 )
3479 .lambda("tuple_index_0_fields")
3480 .apply(
3481 Term::var(CONSTR_FIELDS_EXPOSER)
3482 .apply(Term::var("tuple_index_0")),
3483 )
3484 .delay(),
3485 Term::var("clauses_delayed"),
3486 )
3487 .force()
3488 .lambda("clauses_delayed")
3489 .apply(
3490 Term::equals_integer()
3491 .apply(Term::integer(1.into()))
3492 .apply(
3493 Term::var(CONSTR_INDEX_EXPOSER)
3494 .apply(Term::var("tuple_index_0")),
3495 )
3496 .if_then_else(
3497 Term::equals_integer()
3498 .apply(Term::integer(1.into()))
3499 .apply(
3500 Term::var(CONSTR_INDEX_EXPOSER)
3501 .apply(Term::var("tuple_index_1")),
3502 )
3503 .if_then_else(
3504 Term::bool(true).delay(),
3505 Term::var("clauses_delayed"),
3506 )
3507 .force()
3508 .delay(),
3509 Term::var("clauses_delayed"),
3510 )
3511 .force()
3512 .lambda("clauses_delayed")
3513 .apply(
3514 Term::equals_integer()
3515 .apply(Term::integer(1.into()))
3516 .apply(
3517 Term::var(CONSTR_INDEX_EXPOSER)
3518 .apply(Term::var("tuple_index_0")),
3519 )
3520 .if_then_else(
3521 Term::equals_integer()
3522 .apply(Term::integer(0.into()))
3523 .apply(
3524 Term::var(CONSTR_INDEX_EXPOSER)
3525 .apply(Term::var("tuple_index_1")),
3526 )
3527 .if_then_else(
3528 Term::bool(false).delay(),
3529 Term::var("clauses_delayed"),
3530 )
3531 .force()
3532 .delay(),
3533 Term::var("clauses_delayed"),
3534 )
3535 .force()
3536 .lambda("clauses_delayed")
3537 .apply(Term::bool(false).delay())
3538 .delay(),
3539 )
3540 .delay(),
3541 )
3542 .lambda("tuple_index_0")
3543 .apply(Term::fst_pair().apply(Term::var("input")))
3544 .lambda("tuple_index_1")
3545 .apply(Term::snd_pair().apply(Term::var("input")))
3546 .lambda("input")
3547 .apply(
3548 Term::mk_pair_data()
3549 .apply(Term::var("ec1"))
3550 .apply(Term::var("ec2")),
3551 )
3552 .lambda("ec2")
3553 .lambda("ec1"),
3554 )
3555 .apply(Term::data(Data::constr(1, vec![])))
3556 .apply(Term::data(Data::constr(1, vec![])))
3557 .delayed_if_then_else(
3558 Term::bool(true),
3559 Term::bool(true).if_then_else(Term::bool(false), Term::bool(true)),
3560 )
3561 .constr_index_exposer()
3562 .constr_fields_exposer(),
3563 };
3564
3565 let expected = Program {
3566 version: (1, 0, 0),
3567 term: Term::var("equivalence")
3568 .lambda("equivalence")
3569 .apply(
3570 Term::var("equals_integer_0_curried")
3571 .apply(Term::var(CONSTR_INDEX_EXPOSER).apply(Term::var("tuple_index_0")))
3572 .if_then_else(
3573 Term::var("equals_integer_0_curried")
3574 .apply(
3575 Term::var(CONSTR_INDEX_EXPOSER)
3576 .apply(Term::var("tuple_index_1")),
3577 )
3578 .if_then_else(
3579 Term::var("equals_integer_0_curried")
3580 .apply(
3581 Term::subtract_integer()
3582 .apply(Term::var("x2"))
3583 .apply(Term::var("x1")),
3584 )
3585 .delayed_if_then_else(
3586 Term::var("equals_integer_0_curried").apply(
3587 Term::subtract_integer()
3588 .apply(Term::var("y2"))
3589 .apply(Term::var("y1")),
3590 ),
3591 Term::bool(false),
3592 )
3593 .lambda("x2")
3594 .apply(Term::un_i_data().apply(
3595 Term::fst_pair().apply(Term::var("field_0_pair")),
3596 ))
3597 .lambda("y2")
3598 .apply(Term::un_i_data().apply(
3599 Term::snd_pair().apply(Term::var("field_0_pair")),
3600 ))
3601 .lambda("field_0_pair")
3602 .apply(
3603 Term::mk_pair_data()
3604 .apply(
3605 Term::head_list()
3606 .apply(Term::var("__list_data")),
3607 )
3608 .apply(Term::head_list().apply(Term::var("__tail")))
3609 .lambda("__tail")
3610 .apply(
3611 Term::tail_list()
3612 .apply(Term::var("__list_data")),
3613 )
3614 .lambda("__list_data")
3615 .apply(
3616 Term::unlist_data().apply(
3617 Term::head_list().apply(Term::var(
3618 "tuple_index_1_fields",
3619 )),
3620 ),
3621 ),
3622 )
3623 .lambda("tuple_index_1_fields")
3624 .apply(
3625 Term::var(CONSTR_FIELDS_EXPOSER)
3626 .apply(Term::var("tuple_index_1")),
3627 )
3628 .delay(),
3629 Term::var("clauses_delayed"),
3630 )
3631 .force()
3632 .lambda("x1")
3633 .apply(
3634 Term::un_i_data()
3635 .apply(Term::fst_pair().apply(Term::var("field_0_pair"))),
3636 )
3637 .lambda("y1")
3638 .apply(
3639 Term::un_i_data()
3640 .apply(Term::snd_pair().apply(Term::var("field_0_pair"))),
3641 )
3642 .lambda("field_0_pair")
3643 .apply(
3644 Term::mk_pair_data()
3645 .apply(Term::head_list().apply(Term::var("__list_data")))
3646 .apply(Term::head_list().apply(Term::var("__tail")))
3647 .lambda("__tail")
3648 .apply(Term::tail_list().apply(Term::var("__list_data")))
3649 .lambda("__list_data")
3650 .apply(
3651 Term::unlist_data().apply(
3652 Term::head_list()
3653 .apply(Term::var("tuple_index_0_fields")),
3654 ),
3655 ),
3656 )
3657 .lambda("tuple_index_0_fields")
3658 .apply(
3659 Term::var(CONSTR_FIELDS_EXPOSER)
3660 .apply(Term::var("tuple_index_0")),
3661 )
3662 .delay(),
3663 Term::var("clauses_delayed"),
3664 )
3665 .force()
3666 .lambda("clauses_delayed")
3667 .apply(
3668 Term::var("equals_integer_1_curried")
3669 .apply(
3670 Term::var(CONSTR_INDEX_EXPOSER)
3671 .apply(Term::var("tuple_index_0")),
3672 )
3673 .if_then_else(
3674 Term::var("equals_integer_1_curried")
3675 .apply(
3676 Term::var(CONSTR_INDEX_EXPOSER)
3677 .apply(Term::var("tuple_index_1")),
3678 )
3679 .if_then_else(
3680 Term::bool(true).delay(),
3681 Term::var("clauses_delayed"),
3682 )
3683 .force()
3684 .delay(),
3685 Term::var("clauses_delayed"),
3686 )
3687 .force()
3688 .lambda("clauses_delayed")
3689 .apply(
3690 Term::var("equals_integer_1_curried")
3691 .apply(
3692 Term::var(CONSTR_INDEX_EXPOSER)
3693 .apply(Term::var("tuple_index_0")),
3694 )
3695 .if_then_else(
3696 Term::var("equals_integer_0_curried")
3697 .apply(
3698 Term::var(CONSTR_INDEX_EXPOSER)
3699 .apply(Term::var("tuple_index_1")),
3700 )
3701 .if_then_else(
3702 Term::bool(false).delay(),
3703 Term::var("clauses_delayed"),
3704 )
3705 .force()
3706 .delay(),
3707 Term::var("clauses_delayed"),
3708 )
3709 .force()
3710 .lambda("clauses_delayed")
3711 .apply(Term::bool(false).delay())
3712 .delay(),
3713 )
3714 .lambda("equals_integer_1_curried")
3715 .apply(Term::equals_integer().apply(Term::integer(1.into())))
3716 .delay(),
3717 )
3718 .lambda("equals_integer_0_curried")
3719 .apply(Term::equals_integer().apply(Term::integer(0.into())))
3720 .lambda("tuple_index_0")
3721 .apply(Term::fst_pair().apply(Term::var("input")))
3722 .lambda("tuple_index_1")
3723 .apply(Term::snd_pair().apply(Term::var("input")))
3724 .lambda("input")
3725 .apply(
3726 Term::mk_pair_data()
3727 .apply(Term::var("ec1"))
3728 .apply(Term::var("ec2")),
3729 )
3730 .lambda("ec2")
3731 .lambda("ec1"),
3732 )
3733 .apply(Term::data(Data::constr(1, vec![])))
3734 .apply(Term::data(Data::constr(1, vec![])))
3735 .delayed_if_then_else(
3736 Term::bool(true),
3737 Term::bool(true).if_then_else(Term::bool(false), Term::bool(true)),
3738 )
3739 .constr_index_exposer()
3740 .constr_fields_exposer(),
3741 };
3742
3743 compare_optimization(expected, program, |p| p.builtin_curry_reducer());
3744 }
3745
3746 #[test]
3747 fn curry_reducer_test_4() {
3748 let program: Program<Name> = Program {
3749 version: (1, 0, 0),
3750 term: Term::bool(true)
3751 .delayed_if_then_else(
3752 Term::integer(2.into()),
3753 Term::add_integer()
3754 .apply(
3755 Term::add_integer()
3756 .apply(Term::var("x"))
3757 .apply(Term::var("y")),
3758 )
3759 .apply(Term::var("z"))
3760 .lambda("z")
3761 .apply(
3762 Term::index_bytearray()
3763 .apply(Term::byte_string(vec![
3764 1, 2, 4, 8, 16, 32, 64, 128, 255, 255,
3765 ]))
3766 .apply(Term::integer(35.into())),
3767 )
3768 .lambda("y")
3769 .apply(
3770 Term::index_bytearray()
3771 .apply(Term::byte_string(vec![
3772 1, 2, 4, 8, 16, 32, 64, 128, 255, 255,
3773 ]))
3774 .apply(Term::integer(35.into())),
3775 ),
3776 )
3777 .lambda("x")
3778 .apply(
3779 Term::bool(true).delayed_if_then_else(
3780 Term::integer(1.into()),
3781 Term::index_bytearray()
3782 .apply(Term::byte_string(vec![
3783 1, 2, 4, 8, 16, 32, 64, 128, 255, 255,
3784 ]))
3785 .apply(Term::integer(35.into())),
3786 ),
3787 ),
3788 };
3789
3790 let expected = Program {
3791 version: (1, 0, 0),
3792 term: Term::bool(true)
3793 .delayed_if_then_else(
3794 Term::integer(2.into()),
3795 Term::add_integer()
3796 .apply(
3797 Term::add_integer()
3798 .apply(Term::var("x"))
3799 .apply(Term::var("y")),
3800 )
3801 .apply(Term::var("z"))
3802 .lambda("z")
3803 .apply(Term::var("good_curry").apply(Term::integer(35.into())))
3804 .lambda("y")
3805 .apply(Term::var("good_curry").apply(Term::integer(35.into()))),
3806 )
3807 .lambda("x")
3808 .apply(Term::bool(true).delayed_if_then_else(
3809 Term::integer(1.into()),
3810 Term::var("good_curry").apply(Term::integer(35.into())),
3811 ))
3812 .lambda("good_curry")
3813 .apply(Term::index_bytearray().apply(Term::byte_string(vec![
3814 1, 2, 4, 8, 16, 32, 64, 128, 255, 255,
3815 ]))),
3816 };
3817
3818 compare_optimization(expected, program, |p| p.builtin_curry_reducer());
3819 }
3820
3821 #[test]
3822 fn case_constr_apply_test_1() {
3823 let program: Program<Name> = Program {
3824 version: (1, 1, 0),
3825 term: Term::add_integer()
3826 .apply(Term::integer(0.into()))
3827 .apply(Term::integer(0.into()))
3828 .apply(Term::integer(0.into()))
3829 .apply(Term::integer(0.into()))
3830 .apply(Term::integer(0.into()))
3831 .apply(Term::integer(0.into())),
3832 };
3833
3834 let expected = Program {
3835 version: (1, 1, 0),
3836 term: Term::constr(
3837 0,
3838 vec![
3839 Term::integer(0.into()),
3840 Term::integer(0.into()),
3841 Term::integer(0.into()),
3842 Term::integer(0.into()),
3843 Term::integer(0.into()),
3844 Term::integer(0.into()),
3845 ],
3846 )
3847 .case(vec![Term::add_integer()]),
3848 };
3849
3850 compare_optimization(expected, program, |p| {
3851 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3852 term.case_constr_apply_reducer(id, arg_stack, scope, context);
3853 })
3854 });
3855 }
3856
3857 #[test]
3858 fn case_constr_apply_test_2() {
3859 let program: Program<Name> = Program {
3860 version: (1, 1, 0),
3861 term: Term::add_integer()
3862 .apply(Term::integer(0.into()))
3863 .apply(Term::integer(0.into())),
3864 };
3865
3866 let expected = Program {
3867 version: (1, 1, 0),
3868 term: Term::add_integer()
3869 .apply(Term::integer(0.into()))
3870 .apply(Term::integer(0.into())),
3871 };
3872
3873 compare_optimization(expected, program, |p| {
3874 p.run_one_opt(true, &mut |id, term, arg_stack, scope, context| {
3875 term.case_constr_apply_reducer(id, arg_stack, scope, context);
3876 })
3877 });
3878 }
3879}