1use std::fmt;
4use std::fmt::Debug;
5use std::hash::Hash;
6
7use itertools::Itertools;
8use serde::{Deserialize, Serialize};
9
10use super::atoms::{Function, Variable};
11use crate::algebra::bitstrings::{replace_payloads, EvalTree, PayloadMetadata, Payloads};
12use crate::algebra::dynamic_function::TypeShape;
13use crate::algebra::error::FnError;
14use crate::error::Error;
15use crate::fuzzer::stats_stage::{
16 ALL_TERM_EVAL, ALL_TERM_EVAL_SUCCESS, EVAL_ERR_CODEC, EVAL_ERR_FN_CODEC, EVAL_ERR_FN_CRYPTO,
17 EVAL_ERR_FN_MALFORMED, EVAL_ERR_FN_UNKNOWN, EVAL_ERR_TERM, EVAL_ERR_TERMBUG,
18};
19use crate::protocol::{EvaluatedTerm, ProtocolBehavior, ProtocolTypes};
20use crate::trace::TraceContext;
21
22const SIZE_LEAF: usize = 1;
23const BITSTRING_NAME: &str = "BITSTRING_";
24
25pub type ConcreteMessage = Vec<u8>;
26
27#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq, Hash)]
29#[serde(bound = "PT: ProtocolTypes")]
30pub enum DYTerm<PT: ProtocolTypes> {
31 Variable(Variable<PT>),
34 Application(Function<PT>, Vec<Term<PT>>),
39}
40
41impl<PT: ProtocolTypes> fmt::Display for DYTerm<PT> {
42 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
43 write!(f, "{}", display_term_at_depth(self, 0, false, false))
44 }
45}
46
47pub trait TermType<PT: ProtocolTypes>: fmt::Display + fmt::Debug + Clone {
49 fn resistant_id(&self) -> u32;
50 fn size(&self) -> usize;
51 fn is_leaf(&self) -> bool;
52 fn get_type_shape(&self) -> &TypeShape<PT>;
53 fn name(&self) -> &str;
54 fn mutate(&mut self, other: Self);
55 fn display_at_depth(&self, depth: usize) -> String;
56 fn is_symbolic(&self) -> bool;
57 fn make_symbolic(&mut self); fn get(&self, path: &[usize]) -> Result<&Self, Error>;
59
60 fn evaluate_config<PB: ProtocolBehavior<ProtocolTypes = PT>>(
64 &self,
65 context: &TraceContext<PB>,
66 with_payloads: bool,
67 ) -> Result<(ConcreteMessage, Box<dyn EvaluatedTerm<PT>>), Error>;
68
69 fn evaluate_config_wrap<PB: ProtocolBehavior<ProtocolTypes = PT>>(
71 &self,
72 context: &TraceContext<PB>,
73 with_payloads: bool,
74 ) -> Result<(ConcreteMessage, Box<dyn EvaluatedTerm<PT>>), Error> {
75 ALL_TERM_EVAL.increment();
76 match self.evaluate_config(context, with_payloads) {
77 Ok(cm) => {
78 ALL_TERM_EVAL_SUCCESS.increment();
79 Ok(cm)
80 }
81 Err(e) => {
82 match &e {
83 Error::Fn(FnError::Crypto(..)) => {
84 log::debug!("[evaluate_config_wrap] FnError::Crypto Error on\n{}\n[==>] Causes: {:?}", &self, &e);
85 EVAL_ERR_FN_CRYPTO.increment();
86 }
87 Error::Fn(FnError::Malformed(..)) => {
88 log::debug!("[evaluate_config_wrap] FnError::Malformed Error on\n{}\n[==>] Causes: {:?}", &self, &e);
89 EVAL_ERR_FN_MALFORMED.increment();
90 }
91 Error::Fn(FnError::Unknown(_fne)) => {
92 log::warn!("[evaluate_config_wrap] FnError::Unknown Error on\n{}\n[==>] Causes: {:?}", &self, &e);
93 EVAL_ERR_FN_UNKNOWN.increment();
94 }
95 Error::Fn(FnError::Codec(_fne)) => {
96 log::warn!("[evaluate_config_wrap] FnError::Codec Error on\n{}\n[==>] Causes: {:?}", &self, &e);
97 EVAL_ERR_FN_CODEC.increment();
98 }
99 Error::Term(te) => {
100 log::debug!("[evaluate_config_wrap] Term Error {}", te);
101 EVAL_ERR_TERM.increment();
102 }
103 Error::Codec(te) => {
104 log::debug!("[evaluate_config_wrap] Codec Error {}", te);
105 EVAL_ERR_CODEC.increment();
106 }
107 Error::TermBug(_) => {
108 log::error!(
109 "[evaluate_config_wrap] TermBug Error on\n{}\n[==>] Causes: {:?}",
110 &self,
111 &e
112 );
113 EVAL_ERR_TERMBUG.increment();
114 #[cfg(any(debug_assertions, feature = "debug"))]
115 {
116 panic!("[evaluate_config_wrap] Panic! {}", e);
118 }
119 }
120 _ => {
121 panic!("[evaluate] downcast error failed! {e:?}");
122 }
123 };
124 Err(e)
125 }
126 }
127 }
128
129 fn evaluate<PB: ProtocolBehavior<ProtocolTypes = PT>>(
131 &self,
132 ctx: &TraceContext<PB>,
133 ) -> Result<ConcreteMessage, Error> {
134 Ok(self
135 .evaluate_config_wrap(ctx, ctx.config_trace.with_bit_level)?
136 .0)
137 }
138
139 fn evaluate_symbolic<PB: ProtocolBehavior<ProtocolTypes = PT>>(
142 &self,
143 ctx: &TraceContext<PB>,
144 ) -> Result<ConcreteMessage, Error> {
145 Ok(self.evaluate_config_wrap(ctx, false)?.0)
146 }
147
148 fn evaluate_dy<PB: ProtocolBehavior<ProtocolTypes = PT>>(
151 &self,
152 ctx: &TraceContext<PB>,
153 ) -> Result<Box<dyn EvaluatedTerm<PT>>, Error> {
154 Ok(self.evaluate_config_wrap(ctx, false)?.1)
155 }
156}
157
158fn append<'a, PT: ProtocolTypes>(term: &'a DYTerm<PT>, v: &mut Vec<&'a DYTerm<PT>>) {
159 match *term {
160 DYTerm::Variable(_) => {}
161 DYTerm::Application(_, ref subterms) => {
162 for subterm in subterms {
163 append(&subterm.term, v);
164 }
165 }
166 }
167
168 v.push(term);
169}
170
171impl<'a, PT: ProtocolTypes> IntoIterator for &'a DYTerm<PT> {
175 type IntoIter = std::vec::IntoIter<&'a DYTerm<PT>>;
176 type Item = &'a DYTerm<PT>;
177
178 fn into_iter(self) -> Self::IntoIter {
179 let mut result = vec![];
180 append::<PT>(self, &mut result);
181 result.into_iter()
182 }
183}
184
185pub trait Subterms<PT: ProtocolTypes, T>
186where
187 T: TermType<PT>,
188{
189 fn find_subterm_same_shape(&self, term: &T) -> Option<&T>;
190
191 fn find_subterm<P: Fn(&&T) -> bool + Copy>(&self, filter: P) -> Option<&T>;
192
193 fn filter_grand_subterms<P: Fn(&T, &T) -> bool + Copy>(
194 &self,
195 predicate: P,
196 ) -> Vec<((usize, &T), &T)>;
197}
198
199pub(crate) fn remove_prefix(str: &str) -> String {
203 let split: Option<(&str, &str)> = str.split('<').collect_tuple();
204
205 if let Some((non_generic, generic)) = split {
206 let generic = &generic[0..generic.len() - 1];
207
208 if let Some(pos) = non_generic.rfind("::") {
209 non_generic[pos + 2..].to_string() + "<" + &remove_prefix(generic) + ">"
210 } else {
211 non_generic.to_string() + "<" + &remove_prefix(generic) + ">"
212 }
213 } else if let Some(pos) = str.rfind("::") {
214 str[pos + 2..].to_string()
215 } else {
216 str.to_string()
217 }
218}
219
220pub(crate) fn remove_fn_prefix(str: &str) -> String {
221 str.replace("fn_", "")
222}
223
224#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq, Hash)]
227#[serde(bound = "PT: ProtocolTypes")]
228pub struct Term<PT: ProtocolTypes> {
229 pub term: DYTerm<PT>, pub payloads: Option<Payloads>, }
233
234impl<PT: ProtocolTypes> Term<PT> {
235 pub fn height(&self) -> usize {
237 match &self.term {
238 DYTerm::Application(_, subterms) => {
239 if subterms.is_empty() || !self.is_symbolic() {
240 1
241 } else {
242 1 + subterms.iter().map(Self::height).max().unwrap()
243 }
244 }
245 _ => 1,
246 }
247 }
248
249 pub fn is_list(&self) -> bool {
251 match &self.term {
252 DYTerm::Variable(_) => false,
253 DYTerm::Application(fd, _) => fd.is_list(),
254 }
255 }
256
257 pub fn is_opaque(&self) -> bool {
259 match &self.term {
260 DYTerm::Variable(_) => false,
261 DYTerm::Application(fd, _) => fd.is_opaque(),
262 }
263 }
264
265 pub fn is_get(&self) -> bool {
267 match &self.term {
268 DYTerm::Variable(_) => false,
269 DYTerm::Application(fd, _) => fd.is_get(),
270 }
271 }
272
273 pub fn is_no_bit(&self) -> bool {
276 match &self.term {
277 DYTerm::Variable(_) => false,
278 DYTerm::Application(fd, _) => fd.no_bit(),
279 }
280 }
281
282 pub fn is_no_det(&self) -> bool {
284 match &self.term {
285 DYTerm::Variable(_) => false,
286 DYTerm::Application(fd, _) => fd.no_det(),
287 }
288 }
289
290 pub fn has_variable(&self) -> bool {
292 match &self.term {
293 DYTerm::Variable(_) => true,
294 DYTerm::Application(_, args) => {
295 !self.is_readable() && args.iter().any(|arg| arg.has_variable())
296 }
297 }
298 }
299
300 pub fn has_no_det(&self) -> bool {
302 match &self.term {
303 DYTerm::Variable(_) => false,
304 DYTerm::Application(_, args) => {
305 if self.is_no_det() {
306 return true;
307 }
308 !self.is_readable() && args.iter().any(|arg| arg.has_no_det())
309 }
310 }
311 }
312
313 pub fn is_readable(&self) -> bool {
316 if let Some(payload) = &self.payloads {
317 payload.metadata.readable
318 } else {
319 false
320 }
321 }
322
323 pub fn erase_payloads_subterms(&mut self, is_subterm: bool) {
325 if is_subterm {
326 self.payloads = None;
327 }
328 match &mut self.term {
329 DYTerm::Variable(_) => {}
330 DYTerm::Application(_, args) => {
331 for t in args {
333 t.erase_payloads_subterms(true);
334 }
335 }
336 }
337 }
338
339 pub fn add_payload_with_new(
342 &mut self,
343 payload_0: Vec<u8>,
344 payload_new: Vec<u8>,
345 with_metadata: Option<PayloadMetadata>,
346 ) {
347 self.payloads = Option::from({
348 Payloads {
349 payload_0: payload_0.into(),
350 payload: payload_new.into(),
351 metadata: with_metadata.unwrap_or_else(PayloadMetadata::default),
352 }
353 });
354 self.erase_payloads_subterms(false);
355 }
356
357 pub fn add_payload(&mut self, payload_0: Vec<u8>) {
359 self.add_payload_with_new(payload_0.clone(), payload_0, None)
360 }
361
362 pub fn make_payload<PB>(&mut self, ctx: &TraceContext<PB>) -> Result<(), Error>
364 where
365 PB: ProtocolBehavior<ProtocolTypes = PT>,
366 {
367 log::debug!("make_payload: about to symbolic evaluate to get eval_0...");
368 let eval_0 = self.evaluate_symbolic(ctx)?; self.add_payload(eval_0);
370 Ok(())
371 }
372
373 pub fn add_payload_readable(&mut self, payload: ConcreteMessage) {
376 self.add_payload_with_new(
377 payload.clone(),
378 payload,
379 Some(PayloadMetadata {
380 readable: true,
381 ..PayloadMetadata::default()
382 }),
383 );
384 }
385
386 pub fn all_payloads(&self) -> Vec<&Payloads> {
390 self.into_iter()
391 .filter_map(|t| t.payloads.as_ref())
392 .collect()
393 }
394
395 pub fn count_payloads(&self) -> usize {
402 let mut n = usize::from(self.payloads.is_some());
403 if self.is_symbolic() {
404 if let DYTerm::Application(_, subterms) = &self.term {
405 for subterm in subterms {
406 n += subterm.count_payloads();
407 }
408 }
409 }
410 n
411 }
412
413 pub fn all_payloads_mut(&mut self) -> Vec<&mut Payloads> {
417 fn rec<'a, PT: ProtocolTypes>(term: &'a mut Term<PT>, acc: &mut Vec<&'a mut Payloads>) {
420 if let Some(p) = &mut term.payloads {
421 acc.push(p);
422 }
423 match &mut term.term {
424 DYTerm::Variable(_) => {}
425 DYTerm::Application(_, sts) => {
426 for st in sts {
427 rec(st, acc);
428 }
429 }
430 }
431 }
432 let mut acc = Vec::new();
433 rec(self, &mut acc);
434 acc
435 }
436
437 pub fn payloads_to_replace(&self) -> Vec<&Payloads> {
440 pub fn rec<'a, PT: ProtocolTypes>(term: &'a Term<PT>, acc: &mut Vec<&'a Payloads>) {
441 match &term.term {
442 DYTerm::Variable(_) => {}
443 DYTerm::Application(_, args) => {
444 if !term.is_opaque() && !term.is_readable() {
445 for t in args {
446 rec(t, acc);
447 }
448 }
449 }
450 }
451 if let Some(payload) = &term.payloads {
452 acc.push(payload);
453 }
454 }
455 let mut acc = vec![];
456 rec(self, &mut acc);
457 acc
458 }
459
460 pub fn has_payload_to_replace(&self) -> bool {
462 has_payload_to_replace_rec(self, true)
463 }
464
465 pub fn has_payload_to_replace_wo_root(&self) -> bool {
468 has_payload_to_replace_rec(self, false)
469 }
470}
471
472pub fn has_payload_to_replace_rec<PT: ProtocolTypes>(term: &Term<PT>, include_root: bool) -> bool {
473 if let (Some(_), true) = (&term.payloads, include_root) {
474 return true;
475 }
476 match &term.term {
477 DYTerm::Variable(_) => {}
478 DYTerm::Application(_, args) => {
479 if !term.is_opaque() && !term.is_readable() {
480 for t in args {
481 if has_payload_to_replace_rec(t, true) {
482 return true;
483 }
484 }
485 }
486 }
487 }
488 false
489}
490
491impl<PT: ProtocolTypes> fmt::Display for Term<PT> {
492 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
493 write!(f, "{}", self.display_at_depth(0))
494 }
495}
496impl<PT: ProtocolTypes> From<DYTerm<PT>> for Term<PT> {
497 fn from(term: DYTerm<PT>) -> Self {
498 Self {
499 term,
500 payloads: None,
501 }
502 }
503}
504
505impl<PT: ProtocolTypes> From<Term<PT>> for DYTerm<PT> {
506 fn from(term: Term<PT>) -> Self {
507 term.term
508 }
509}
510
511fn display_term_at_depth<PT: ProtocolTypes>(
512 term: &DYTerm<PT>,
513 depth: usize,
514 is_bitstring: bool,
515 is_readable: bool,
516) -> String {
517 let tabs = "\t".repeat(depth);
518 let is_bitstring = if is_bitstring {
519 if is_readable {
520 "BS-READ//"
521 } else {
522 "BS//"
523 }
524 } else {
525 ""
526 };
527 match term {
528 DYTerm::Variable(ref v) => {
529 format!("{tabs}{is_bitstring}{v}")
530 }
531 DYTerm::Application(ref func, ref args) => {
532 let op_str = remove_prefix(func.name());
533 let return_type = remove_prefix(func.shape().return_type.name);
534 if args.is_empty() {
535 format!("{tabs}{is_bitstring}{op_str} -> {return_type}")
536 } else {
537 let args_str = args
538 .iter()
539 .map(|arg| {
540 display_term_at_depth(
541 &arg.term,
542 depth + 1,
543 !arg.is_symbolic(),
544 arg.is_readable(),
545 )
546 })
547 .join(",\n");
548 format!("{tabs}{is_bitstring}{op_str}(\n{args_str}\n{tabs}) -> {return_type}")
549 }
550 }
551 }
552}
553
554fn append_eval<'a, PT: ProtocolTypes>(term_eval: &'a Term<PT>, v: &mut Vec<&'a Term<PT>>) {
555 if term_eval.is_symbolic() {
556 match term_eval.term {
557 DYTerm::Variable(_) => {}
558 DYTerm::Application(_, ref subterms) => {
559 for subterm in subterms {
560 append_eval(subterm, v);
561 }
562 }
563 }
564 }
565
566 v.push(term_eval);
567}
568
569impl<PT: ProtocolTypes> TermType<PT> for Term<PT> {
570 fn evaluate_config<PB: ProtocolBehavior<ProtocolTypes = PT>>(
572 &self,
573 context: &TraceContext<PB>,
574 with_payloads: bool,
575 ) -> Result<(ConcreteMessage, Box<dyn EvaluatedTerm<PT>>), Error> {
576 log::trace!("[evaluate_config] About to evaluate term (with_payloads: {with_payloads}):\n{}\n===================================================================", &self);
577 let mut eval_tree = EvalTree::empty();
578 let (m, all_payloads) = self.eval_until_opaque(
579 &mut eval_tree,
580 context,
581 with_payloads,
582 false,
583 self.get_type_shape(),
584 )?;
585 if with_payloads && !all_payloads.is_empty() {
587 let ft = format!("[evaluate_config] About to replace for a term {}\n payloads with contexts: {}\n-------------------------------------------------------------------",
588 self, all_payloads.iter().format(","));
589 log::trace!("{}", ft);
590 let res = replace_payloads(self, &mut eval_tree, all_payloads)?;
591 log::trace!(
592 " / [payload] We successfully evaluated the root term into: {res:?}"
593 );
594 Ok((res, m))
595 } else {
596 let eval = PB::any_get_encoding(m.as_ref());
597 log::trace!(
598 " / [no_payload] We successfully evaluated the root term into: {eval:?}"
599 );
600 Ok((eval, m))
601 }
602 }
603
604 fn resistant_id(&self) -> u32 {
605 match &self.term {
606 DYTerm::Variable(v) => v.resistant_id,
607 DYTerm::Application(f, _) => f.resistant_id,
608 }
609 }
610
611 fn size(&self) -> usize {
613 if self.is_leaf() {
614 SIZE_LEAF
615 } else {
616 match &self.term {
617 DYTerm::Variable(_) => SIZE_LEAF,
618 DYTerm::Application(_, ref subterms) => {
619 if !self.is_symbolic() {
620 SIZE_LEAF
621 } else {
622 subterms.iter().map(TermType::size).sum::<usize>() + 1
623 }
624 }
625 }
626 }
627 }
628
629 fn is_leaf(&self) -> bool {
630 if self.is_symbolic() {
631 match &self.term {
632 DYTerm::Variable(_) => {
633 true }
635 DYTerm::Application(_, ref subterms) => {
636 subterms.is_empty() }
638 }
639 } else {
640 true
641 }
642 }
643
644 fn get_type_shape(&self) -> &TypeShape<PT> {
645 match &self.term {
646 DYTerm::Variable(v) => &v.typ,
647 DYTerm::Application(function, _) => &function.shape().return_type,
648 }
649 }
650
651 fn name(&self) -> &str {
652 if self.is_symbolic() {
653 match &self.term {
655 DYTerm::Variable(v) => v.typ.name,
656 DYTerm::Application(function, _) => function.name(),
657 }
658 } else {
659 BITSTRING_NAME
666 }
667 }
668
669 fn mutate(&mut self, other: Self) {
670 *self = other;
671 }
672
673 fn display_at_depth(&self, depth: usize) -> String {
674 display_term_at_depth(&self.term, depth, !self.is_symbolic(), self.is_readable())
675 }
676
677 fn is_symbolic(&self) -> bool {
678 self.payloads.is_none()
679 }
680
681 fn make_symbolic(&mut self) {
682 self.erase_payloads_subterms(true); }
684
685 fn get(&self, path: &[usize]) -> Result<&Self, Error> {
686 if path.is_empty() {
687 return Ok(self);
688 }
689 match &self.term {
690 DYTerm::Variable(_) => {
691 return Err(Error::TermBug(format!(
692 "--> [get] Should never happen! self.args.len() <= nb. Term: {self}\n, path: {path:?}"
693 )))
694 }
695 DYTerm::Application(_, args) => {
696 let nb = path[0];
697 let path = &path[1..];
698 if args.len() <= nb {
699 return Err(Error::TermBug(format!(
700 "--> [get] Should never happen! self.args.len() <= nb. Term: {self}\n, path: {path:?}"
701 )))
702 }
703 args[nb].get(path)
704 }
705 }
706 }
707}
708
709impl<'a, PT: ProtocolTypes> IntoIterator for &'a Term<PT> {
713 type IntoIter = std::vec::IntoIter<&'a Term<PT>>;
714 type Item = &'a Term<PT>;
715
716 fn into_iter(self) -> Self::IntoIter {
717 let mut result = vec![];
718 append_eval::<PT>(self, &mut result);
719 result.into_iter()
720 }
721}
722
723impl<PT: ProtocolTypes> Subterms<PT, Term<PT>> for Vec<Term<PT>> {
724 fn find_subterm_same_shape(&self, term: &Term<PT>) -> Option<&Term<PT>> {
726 self.find_subterm(|subterm| term.get_type_shape() == subterm.get_type_shape())
727 }
728
729 fn find_subterm<P: Fn(&&Term<PT>) -> bool + Copy>(&self, predicate: P) -> Option<&Term<PT>> {
731 self.iter().find(predicate)
732 }
733
734 fn filter_grand_subterms<P: Fn(&Term<PT>, &Term<PT>) -> bool + Copy>(
741 &self,
742 predicate: P,
743 ) -> Vec<((usize, &Term<PT>), &Term<PT>)> {
744 let mut found_grand_subterms = vec![];
745
746 for (i, subterm) in self.iter().enumerate() {
747 match &subterm.term {
748 DYTerm::Variable(_) => {}
749 DYTerm::Application(_, grand_subterms) => {
750 if subterm.is_symbolic() {
751 found_grand_subterms.extend(
752 grand_subterms
753 .iter()
754 .filter(|grand_subterm| predicate(subterm, grand_subterm))
755 .map(|grand_subterm| ((i, subterm), grand_subterm)),
756 );
757 }
758 }
759 };
760 }
761
762 found_grand_subterms
763 }
764}
765
766#[cfg(test)]
767mod tests {
768 use crate::algebra::remove_prefix;
769
770 #[test_log::test]
771 fn test_normal() {
772 assert_eq!(remove_prefix("test::test::Test"), "Test");
773 }
774
775 #[test_log::test]
776 fn test_generic() {
777 assert_eq!(remove_prefix("test::test::Test<Asdf>"), "Test<Asdf>");
778 }
779
780 #[test_log::test]
781 fn test_generic_recursive() {
782 assert_eq!(remove_prefix("test::test::Test<asdf::Asdf>"), "Test<Asdf>");
783 }
784}