puffin/algebra/
term.rs

1//! This module provides[`DYTerm`]sas well as iterators over them.
2
3use 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/// A first-order term: either a [`Variable`] or an application of an [`Function`].
28#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq, Hash)]
29#[serde(bound = "PT: ProtocolTypes")]
30pub enum DYTerm<PT: ProtocolTypes> {
31    /// A concrete but unspecified `Term` (e.g. `x`, `y`).
32    /// See [`Variable`] for more information.
33    Variable(Variable<PT>),
34    /// An [`Function`] applied to zero or more `Term`s (e.g. (`f(x, y)`, `g()`).
35    ///
36    /// A `Term` that is an application of an [`Function`] with arity 0 applied to 0 `Term`s can be
37    /// considered a constant.
38    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
47/// Trait for data we can treat as terms (either `DYTerm` or Term)
48pub 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); // remove all payloads
58    fn get(&self, path: &[usize]) -> Result<&Self, Error>;
59
60    /// Evaluate terms into `ConcreteMessage` and `EvaluatedTerm` (considering Payloads or not
61    /// depending on `with_payloads`) With `with_payloads, the returned `EvaluatedTerm` is
62    /// without payload replacements; use the `ConcreteMessage` instead.
63    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    /// Wrap `evaluate_config` with error stats and logging handling
70    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                            // we panic in debug or test mode
117                            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    /// Evaluate terms into `ConcreteMessage` (considering Payloads)
130    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    /// Evaluate terms into `ConcreteMessage` considering all sub-terms as symbolic (even those with
140    /// Payloads)
141    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    /// Evaluate terms into `EvaluatedTerm`  considering all sub-terms as symbolic (even those with
149    /// Payloads)
150    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
171/// Having the same mutator for &'a mut Term is not possible in Rust:
172/// * <https://stackoverflow.com/questions/49057270/is-there-a-way-to-iterate-over-a-mutable-tree-to-get-a-random-node>
173/// * <https://sachanganesh.com/programming/graph-tree-traversals-in-rust/>
174impl<'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
199/// `tlspuffin::term::op_impl::op_protocol_version` -> `op_protocol_version`
200/// `alloc::Vec<rustls::msgs::handshake::ServerExtension>` ->
201/// `Vec<rustls::msgs::handshake::ServerExtension>`
202pub(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/// `Term`s are `Term`s equipped with optional `Payloads` when they no longer are treated as
225/// symbolic terms.
226#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq, Hash)]
227#[serde(bound = "PT: ProtocolTypes")]
228pub struct Term<PT: ProtocolTypes> {
229    pub term: DYTerm<PT>, // initial DY term
230    pub payloads: Option<Payloads>, /* None until make_message mutation is used and fill this
231                           * with term.evaluate() */
232}
233
234impl<PT: ProtocolTypes> Term<PT> {
235    /// Height of term, considering non-symbolic terms as atoms
236    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    /// When the term starts with a list function symbol
250    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    /// When the term starts with an opaque function symbol (like encryption)
258    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    /// When the term starts with an opaque function symbol (like encryption)
266    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    /// When the term starts with a `no_bit` function symbol. We will never MakeMessage on, thus
274    /// disabling applying any of the bit-level mutations.
275    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    /// When the term starts with a `no_det` function symbol.
283    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    /// When the term has a variable as sub-term (excluding strict-sub-terms of readable)
291    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    /// When the term has a non-det sub-term (excluding strict-sub-terms of readable)
301    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    /// Whether the term is readable, i.e. whether it has a payload that will be read before
314    /// evaluating
315    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    /// Erase all payloads in a term, including those under opaque function symbol
324    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                // Not true anymore: if opaque, we keep payloads in strict sub-terms
332                for t in args {
333                    t.erase_payloads_subterms(true);
334                }
335            }
336        }
337    }
338
339    /// Add a payload at the root position and start with a new payload.payload possibly different
340    /// from payload.payload_0, erase payloads in strict sub-terms not under opaque
341    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    /// Add a payload at the root position, erase payloads in strict sub-terms not under opaque
358    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    /// Make and Add a payload at the root position, erase payloads in strict sub-terms
363    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)?; // we compute the original encoding, without payloads!
369        self.add_payload(eval_0);
370        Ok(())
371    }
372
373    /// Add a payload at the root position, erase payloads in strict sub-terms and make the payload
374    /// readable.
375    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    /// Return all payloads contains in a term, even under opaque terms.
387    /// Note that we keep the invariant that a non-symbolic term cannot have payloads in
388    /// strict-subterms, see `add_payload/make_payload`.
389    pub fn all_payloads(&self) -> Vec<&Payloads> {
390        self.into_iter()
391            .filter_map(|t| t.payloads.as_ref())
392            .collect()
393    }
394
395    /// Number of payloads in a term, without allocating (unlike `all_payloads().len()`, which
396    /// materialises a `Vec` via the `&Term` iterator). Cheap enough for the hot mutation path.
397    ///
398    /// Mirrors the iterator's traversal exactly so the count equals `all_payloads().len()`: count
399    /// this node's own payload, and recurse into sub-terms only while the node is symbolic (a
400    /// non-symbolic term keeps the invariant that it has no payloads in its strict sub-terms).
401    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    /// Return all payloads contains in a term (mutable references), even under opaque terms.
414    /// Note that we keep the invariant that a non-symbolic term cannot have payloads in
415    /// strict-subterms, see `add_payload/make_payload`.
416    pub fn all_payloads_mut(&mut self) -> Vec<&mut Payloads> {
417        // unable to implement as_iter_map for Term due to its tree structure so:
418        // do it manually instead!
419        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    /// Return all payloads contained in a term, except those under opaque or readable terms.
438    /// The deeper the first in the returned vector.
439    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    /// Return whether there is at least one payload, except those under opaque or readable terms.
461    pub fn has_payload_to_replace(&self) -> bool {
462        has_payload_to_replace_rec(self, true)
463    }
464
465    /// Return whether there is at least one payload, except those under opaque terms or readable
466    /// and at the root.
467    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    /// Evaluate terms into bitstrings and `EvaluatedTerm` (considering Payloads)
571    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 let Some(mut e) = eval {
586        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    /// size of a term, considering non-symbolic terms as atoms
612    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 // variable
634                }
635                DYTerm::Application(_, ref subterms) => {
636                    subterms.is_empty() // constant
637                }
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            // we do not display this information for now
654            match &self.term {
655                DYTerm::Variable(v) => v.typ.name,
656                DYTerm::Application(function, _) => function.name(),
657            }
658        } else {
659            // let str =
660            //     match &self.term {
661            //     Term::Variable(v) => v.typ.name,
662            //     Term::Application(function, _) => function.name(),
663            // };
664            // &format!("{}//{}", BITSTRING_NAME, str)
665            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); // true as we also want to remove payloads at top-level
683    }
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
709/// Having the same mutator for &'a mut `DYTerm` is not possible in Rust:
710/// * <https://stackoverflow.com/questions/49057270/is-there-a-way-to-iterate-over-a-mutable-tree-to-get-a-random-node>
711/// * <https://sachanganesh.com/programming/graph-tree-traversals-in-rust/>
712impl<'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    /// Finds a subterm with the same type as `term`
725    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    /// Finds a subterm in this vector
730    fn find_subterm<P: Fn(&&Term<PT>) -> bool + Copy>(&self, predicate: P) -> Option<&Term<PT>> {
731        self.iter().find(predicate)
732    }
733
734    /// Finds all grand children/subterms which match the predicate.
735    ///
736    /// A grand subterm is defined as a subterm of a term in `self`.
737    ///
738    /// Each grand subterm is returned together with its parent and the index of the parent in
739    /// `self`.
740    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}