Repository: ergoplatform/sigma-rust (language: rust)

Issue:
[250 SigmaUSD] `SubstConstants` IR node
Create a new struct in a separate module(file) in `mir` module and add it to `Expr` enum. Implement serialization and evaluation.

Doc comment from the reference Scala implementation (see link below):
> Transforms serialized bytes of `ErgoTree` with segregated constants by replacing constants at given positions with new values. This operation allows using serialized scripts as pre-defined templates. The typical usage is "check that output box have proposition equal to given script bytes, where `minerPk` (`constants(0)`) is replaced with `currentMinerPk`".  Each constant in the original `scriptBytes` have `SType` serialized before actual data.
> During substitution each value from `newValues` is checked to be an instance of the corresponding type.
> This means, the constants during substitution cannot change their types.


Reference Scala implementation:
https://github.com/ScorexFoundation/sigmastate-interpreter/blob/c863a9b1a82589e47b15f76f3affdb30a475e740/sigmastate/src/main/scala/sigmastate/trees.scala#L746-L799


Discussion / hints:
I've started on this one.

Fix patch:
diff --git a/ergotree-interpreter/src/eval.rs b/ergotree-interpreter/src/eval.rs
index 0e94af76d..f8dc34079 100644
--- a/ergotree-interpreter/src/eval.rs
+++ b/ergotree-interpreter/src/eval.rs
@@ -81,6 +81,7 @@ pub(crate) mod sigma_and;
 pub(crate) mod sigma_or;
 pub(crate) mod sigma_prop_bytes;
 pub(crate) mod soption;
+pub(crate) mod subst_const;
 pub(crate) mod tuple;
 pub(crate) mod upcast;
 pub(crate) mod val_use;
diff --git a/ergotree-interpreter/src/eval/expr.rs b/ergotree-interpreter/src/eval/expr.rs
index 9ec795f6a..36e58a82d 100644
--- a/ergotree-interpreter/src/eval/expr.rs
+++ b/ergotree-interpreter/src/eval/expr.rs
@@ -11,7 +11,7 @@ impl Evaluable for Expr {
         ctx.cost_accum.add_cost_of(self)?;
         match self {
             Expr::Const(c) => Ok(Value::from(c.v.clone())),
-            Expr::SubstConstants(_) => Err(EvalError::NotImplementedYet("Expr::SubstConstants")),
+            Expr::SubstConstants(op) => op.eval(env, ctx),
             Expr::ByteArrayToLong(op) => op.eval(env, ctx),
             Expr::ByteArrayToBigInt(op) => op.eval(env, ctx),
             Expr::LongToByteArray(op) => op.eval(env, ctx),
diff --git a/ergotree-interpreter/src/eval/subst_const.rs b/ergotree-interpreter/src/eval/subst_const.rs
new file mode 100644
index 000000000..34dcdadd4
--- /dev/null
+++ b/ergotree-interpreter/src/eval/subst_const.rs
@@ -0,0 +1,191 @@
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+use ergotree_ir::ergo_tree::ErgoTree;
+use ergotree_ir::mir::constant::Constant;
+use ergotree_ir::mir::constant::TryExtractInto;
+use ergotree_ir::mir::subst_const::SubstConstants;
+use ergotree_ir::mir::value::CollKind;
+use ergotree_ir::mir::value::NativeColl;
+use ergotree_ir::mir::value::Value;
+use ergotree_ir::serialization::SigmaSerializable;
+use ergotree_ir::util::AsVecI8;
+use ergotree_ir::util::AsVecU8;
+use std::convert::TryFrom;
+
+impl Evaluable for SubstConstants {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let script_bytes_v = self.script_bytes.eval(env, ctx)?;
+        let positions_v = self.positions.eval(env, ctx)?;
+        let new_values_v = self.new_values.eval(env, ctx)?;
+
+        let positions: Vec<usize> = positions_v
+            .try_extract_into::<Vec<i32>>()?
+            .into_iter()
+            .map(|i| i as usize)
+            .collect();
+
+        let new_constants = if let Value::Coll(CollKind::WrappedColl { items, .. }) = new_values_v {
+            let mut items_const = vec![];
+            for v in items {
+                let c = Constant::try_from(v).map_err(EvalError::Misc)?;
+                items_const.push(c);
+            }
+            items_const
+        } else {
+            return Err(EvalError::Misc(format!(
+                "SubstConstants: expected evaluation of `new_values` be of type `Coll[_]`, got \
+                    {:?} instead",
+                new_values_v
+            )));
+        };
+
+        if new_constants.len() != positions.len() {
+            return Err(EvalError::Misc(format!(
+                "SubstConstants: `positions.len()` (== {}) and `new_values.len()` (== {}) differ",
+                positions.len(),
+                new_constants.len()
+            )));
+        }
+
+        if let Value::Coll(CollKind::NativeColl(NativeColl::CollByte(b))) = script_bytes_v {
+            // Substitue constants with repeated calls to `ErgoTree::with_constant`.
+            let mut ergo_tree = ErgoTree::sigma_parse_bytes(&b.as_vec_u8())?;
+            let num_constants = ergo_tree.constants_len().map_err(to_misc_err)?;
+            for (ix, i) in positions.iter().enumerate() {
+                if *i < num_constants {
+                    ergo_tree = ergo_tree
+                        .with_constant(*i, new_constants[ix].clone())
+                        .map_err(to_misc_err)?;
+                } else {
+                    return Err(EvalError::Misc(format!(
+                        "SubstConstants: positions[{}] == {} is an out of bound index with \
+                       respect to the serialized ErgoTree's constant list",
+                        ix, *i
+                    )));
+                }
+            }
+            Ok(Value::Coll(CollKind::NativeColl(NativeColl::CollByte(
+                ergo_tree.sigma_serialize_bytes()?.as_vec_i8(),
+            ))))
+        } else {
+            Err(EvalError::Misc(format!(
+                "SubstConstants: expected evaluation of `script_bytes` to be of type `Coll[SBytes]`, \
+                 got {:?} instead",
+                script_bytes_v
+            )))
+        }
+    }
+}
+
+fn to_misc_err<T: std::fmt::Debug>(e: T) -> EvalError {
+    EvalError::Misc(format!("{:?}", e))
+}
+
+#[cfg(test)]
+#[allow(clippy::unwrap_used)]
+#[allow(clippy::panic)]
+#[allow(clippy::expect_used)]
+mod tests {
+    use ergotree_ir::{
+        ergo_tree::{ErgoTree, ErgoTreeHeader},
+        mir::{
+            bin_op::{ArithOp, BinOp, BinOpKind},
+            expr::Expr,
+            value::StoreWrapped,
+        },
+        serialization::SigmaSerializable,
+        types::stype::LiftIntoSType,
+    };
+    use proptest::prelude::*;
+
+    use crate::eval::tests::try_eval_out_wo_ctx;
+
+    use super::*;
+    proptest! {
+
+        #[test]
+        fn eval_single_substitution(original in any::<((i32, i32), Vec<i64>)>(), new in any::<((i32, i32), Vec<i64>)>()) {
+            test_single_substitution(original, new);
+        }
+
+        #[test]
+        fn eval_3_substitutions(original in any::<(i32, i32, i32)>(), new in any::<(i32, i32, i32)>()) {
+            test_3_substitutions(original, new);
+        }
+    }
+
+    fn test_single_substitution<T: Clone + LiftIntoSType + StoreWrapped + Into<Constant>>(
+        original: T,
+        new: T,
+    ) {
+        let expr = Expr::Const(original.clone().into());
+        let ergo_tree = ErgoTree::new(ErgoTreeHeader::v0(true), &expr).unwrap();
+        assert_eq!(ergo_tree.constants_len().unwrap(), 1);
+        assert_eq!(ergo_tree.get_constant(0).unwrap().unwrap(), original.into());
+
+        let script_bytes =
+            Expr::Const(Constant::from(ergo_tree.sigma_serialize_bytes().unwrap())).into();
+        let positions = Expr::Const(Constant::from(vec![0])).into();
+        let new_values = Expr::Const(Constant::from(vec![new.clone()])).into();
+
+        let subst_const = Expr::SubstConstants(SubstConstants {
+            script_bytes,
+            positions,
+            new_values,
+        });
+
+        let x: Value = try_eval_out_wo_ctx(&subst_const).unwrap();
+        if let Value::Coll(CollKind::NativeColl(NativeColl::CollByte(b))) = x {
+            let new_ergo_tree = ErgoTree::sigma_parse_bytes(&b.as_vec_u8()).unwrap();
+            assert_eq!(new_ergo_tree.constants_len().unwrap(), 1);
+            assert_eq!(new_ergo_tree.get_constant(0).unwrap().unwrap(), new.into());
+        } else {
+            unreachable!();
+        }
+    }
+
+    fn test_3_substitutions(original: (i32, i32, i32), new: (i32, i32, i32)) {
+        let (o0, o1, o2) = original;
+        let (n0, n1, n2) = new;
+        let expr = Expr::BinOp(BinOp {
+            kind: BinOpKind::Arith(ArithOp::Plus),
+            left: Box::new(Expr::Const(o0.into())),
+            right: Box::new(Expr::BinOp(BinOp {
+                kind: BinOpKind::Arith(ArithOp::Multiply),
+                left: Box::new(Expr::Const(o1.into())),
+                right: Box::new(Expr::Const(o2.into())),
+            })),
+        });
+        let ergo_tree = ErgoTree::new(ErgoTreeHeader::v0(true), &expr).unwrap();
+        assert_eq!(ergo_tree.constants_len().unwrap(), 3);
+        assert_eq!(ergo_tree.get_constant(0).unwrap().unwrap(), o0.into());
+        assert_eq!(ergo_tree.get_constant(1).unwrap().unwrap(), o1.into());
+        assert_eq!(ergo_tree.get_constant(2).unwrap().unwrap(), o2.into());
+
+        let script_bytes =
+            Expr::Const(Constant::from(ergo_tree.sigma_serialize_bytes().unwrap())).into();
+
+        let positions = Expr::Const(Constant::from(vec![1, 2, 0])).into();
+
+        let new_values = Expr::Const(Constant::from(vec![n0, n1, n2])).into();
+
+        let subst_const = Expr::SubstConstants(SubstConstants {
+            script_bytes,
+            positions,
+            new_values,
+        });
+
+        let x: Value = try_eval_out_wo_ctx(&subst_const).unwrap();
+        if let Value::Coll(CollKind::NativeColl(NativeColl::CollByte(b))) = x {
+            let new_ergo_tree = ErgoTree::sigma_parse_bytes(&b.as_vec_u8()).unwrap();
+            assert_eq!(new_ergo_tree.constants_len().unwrap(), 3);
+            assert_eq!(new_ergo_tree.get_constant(0).unwrap().unwrap(), n2.into());
+            assert_eq!(new_ergo_tree.get_constant(1).unwrap().unwrap(), n0.into());
+            assert_eq!(new_ergo_tree.get_constant(2).unwrap().unwrap(), n1.into());
+        } else {
+            unreachable!();
+        }
+    }
+}
diff --git a/ergotree-ir/README.md b/ergotree-ir/README.md
index 1d4bef65e..d8168604e 100644
--- a/ergotree-ir/README.md
+++ b/ergotree-ir/README.md
@@ -15,7 +15,6 @@ Descriptions for the operations can be found in [ErgoTree Specification](https:/
 
 ### Predefined functions
 
-- substConstants
 - downcast
 - atLeast
 - avlTree
@@ -130,6 +129,7 @@ Descriptions for the operations can be found in [ErgoTree Specification](https:/
 - proveDlog
 - proveDHTuple
 - sigmaProp
+- substConstants
 - executeFromVar
 - executeFromSelfReg
 - getVar
diff --git a/ergotree-ir/src/ergo_tree.rs b/ergotree-ir/src/ergo_tree.rs
index 9e99ddacb..e1f8e68c8 100644
--- a/ergotree-ir/src/ergo_tree.rs
+++ b/ergotree-ir/src/ergo_tree.rs
@@ -425,8 +425,9 @@ impl ErgoTree {
             .map_err(|e| e.clone())
     }
 
-    /// Returns new ErgoTree with a new constant value for a given index in constants list (as stored in serialized ErgoTree),
-    /// or an error
+    /// Returns new ErgoTree with a new constant value for a given index in constants list (as
+    /// stored in serialized ErgoTree), or an error. Note that the type of the new constant must
+    /// coincide with that of the constant being replaced, or an error is returned too.
     pub fn with_constant(
         self,
         index: usize,
diff --git a/ergotree-ir/src/mir/constant.rs b/ergotree-ir/src/mir/constant.rs
index db6575190..4e1d4bd9d 100644
--- a/ergotree-ir/src/mir/constant.rs
+++ b/ergotree-ir/src/mir/constant.rs
@@ -7,6 +7,7 @@ use crate::sigma_protocol::sigma_boolean::SigmaBoolean;
 use crate::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
 use crate::sigma_protocol::sigma_boolean::{ProveDhTuple, ProveDlog};
 use crate::sigma_protocol::{dlog_group::EcPoint, sigma_boolean::SigmaProp};
+use crate::types::stuple::STuple;
 use crate::types::stuple::TupleItems;
 use crate::types::stype::LiftIntoSType;
 use crate::types::stype::SType;
@@ -20,6 +21,7 @@ pub use constant_placeholder::*;
 
 use super::value::NativeColl;
 use super::value::StoreWrapped;
+use super::value::Value;
 
 use thiserror::Error;
 
@@ -142,6 +144,79 @@ impl<T: LiftIntoSType + Into<Literal>> From<Option<T>> for Literal {
         Literal::Opt(Box::new(opt.map(|e| e.into())))
     }
 }
+
+impl TryFrom<Value> for Constant {
+    type Error = String;
+    #[allow(clippy::unwrap_used)]
+    fn try_from(value: Value) -> Result<Self, Self::Error> {
+        match value {
+            Value::Boolean(b) => Ok(Constant::from(b)),
+            Value::Byte(b) => Ok(Constant::from(b)),
+            Value::Short(s) => Ok(Constant::from(s)),
+            Value::Int(i) => Ok(Constant::from(i)),
+            Value::Long(l) => Ok(Constant::from(l)),
+            Value::BigInt(b) => Ok(Constant::from(b)),
+            Value::SigmaProp(s) => Ok(Constant::from(*s)),
+            Value::GroupElement(e) => Ok(Constant::from(*e)),
+            Value::CBox(i) => Ok(Constant::from(i)),
+            Value::Coll(coll) => {
+                let (v, tpe) = match coll {
+                    CollKind::NativeColl(n) => (
+                        Literal::Coll(CollKind::NativeColl(n)),
+                        SType::SColl(Box::new(SType::SByte)),
+                    ),
+                    CollKind::WrappedColl { elem_tpe, items } => {
+                        let mut new_items = Vec::with_capacity(items.len());
+                        for v in items {
+                            let c = Constant::try_from(v)?;
+                            new_items.push(c.v);
+                        }
+                        (
+                            Literal::Coll(CollKind::WrappedColl {
+                                elem_tpe: elem_tpe.clone(),
+                                items: new_items,
+                            }),
+                            SType::SColl(Box::new(elem_tpe)),
+                        )
+                    }
+                };
+                Ok(Constant { v, tpe })
+            }
+            Value::Opt(lit) => match *lit {
+                Some(v) => {
+                    let c = Constant::try_from(v)?;
+                    Ok(Constant {
+                        v: Literal::Opt(Box::new(Some(c.v))),
+                        tpe: c.tpe,
+                    })
+                }
+                None => Err("Can't convert from Value::Opt(None) to Constant".into()),
+            },
+            Value::Tup(t) => {
+                if let Ok(t) = t.try_mapped::<_, _, String>(|v| {
+                    let c = Constant::try_from(v)?;
+                    Ok((c.v, c.tpe))
+                }) {
+                    let tuple_items = t.mapped_ref(|(l, _)| l.clone());
+                    let tuple_item_types = SType::STuple(STuple {
+                        items: t.mapped(|(_, tpe)| tpe),
+                    });
+                    Ok(Constant {
+                        v: Literal::Tup(tuple_items),
+                        tpe: tuple_item_types,
+                    })
+                } else {
+                    Err("Can't convert Value:Tup element".into())
+                }
+            }
+            Value::AvlTree => Err("Cannot convert Value::AvlTree into Constant".into()),
+            Value::Context => Err("Cannot convert Value::Context into Constant".into()),
+            Value::Global => Err("Cannot convert Value::Global into Constant".into()),
+            Value::Lambda(_) => Err("Cannot convert Value::Lambda(_) into Constant".into()),
+        }
+    }
+}
+
 impl From<bool> for Constant {
     fn from(v: bool) -> Constant {
         Constant {
diff --git a/ergotree-ir/src/mir/subst_const.rs b/ergotree-ir/src/mir/subst_const.rs
index 2866ec683..142fc25d3 100644
--- a/ergotree-ir/src/mir/subst_const.rs
+++ b/ergotree-ir/src/mir/subst_const.rs
@@ -26,6 +26,26 @@ pub struct SubstConstants {
 }
 
 impl SubstConstants {
+    /// Create new object, returning error if requirements failed
+    pub fn new(
+        script_bytes: Expr,
+        positions: Expr,
+        new_values: Expr,
+    ) -> Result<Self, InvalidArgumentError> {
+        script_bytes.check_post_eval_tpe(&SType::SColl(SType::SByte.into()))?;
+        positions.check_post_eval_tpe(&SType::SColl(SType::SInt.into()))?;
+        match new_values.post_eval_tpe() {
+            SType::SColl(_) => Ok(SubstConstants {
+                script_bytes: script_bytes.into(),
+                positions: positions.into(),
+                new_values: new_values.into(),
+            }),
+            e => Err(InvalidArgumentError(format!(
+                "SubstConstants: expected new_values type to be SColl[T], got {:?}",
+                e
+            ))),
+        }
+    }
     /// Type of returned value
     pub fn tpe(&self) -> SType {
         SType::SColl(SType::SByte.into())
@@ -44,20 +64,10 @@ impl SigmaSerializable for SubstConstants {
     }
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SigmaParsingError> {
-        let script_bytes = Box::new(Expr::sigma_parse(r)?);
-        script_bytes
-            .check_post_eval_tpe(&SType::SColl(SType::SByte.into()))
-            .map_err(InvalidArgumentError::from)?;
-        let positions = Box::new(Expr::sigma_parse(r)?);
-        positions
-            .check_post_eval_tpe(&SType::SColl(SType::SInt.into()))
-            .map_err(InvalidArgumentError::from)?;
-        let new_values = Expr::sigma_parse(r)?.into();
-        Ok(Self {
-            script_bytes,
-            positions,
-            new_values,
-        })
+        let script_bytes = Expr::sigma_parse(r)?;
+        let positions = Expr::sigma_parse(r)?;
+        let new_values = Expr::sigma_parse(r)?;
+        Ok(SubstConstants::new(script_bytes, positions, new_values)?)
     }
 }
 
@@ -85,12 +95,24 @@ mod tests {
                     tpe: SType::SColl(SType::SInt.into()),
                     depth: 0,
                 }),
-                any::<Box<Expr>>(),
+                prop_oneof![
+                    Just(SType::SByte),
+                    Just(SType::SBoolean),
+                    Just(SType::SShort),
+                    Just(SType::SInt),
+                    Just(SType::SLong),
+                ]
+                .prop_flat_map(|ty| {
+                    any_with::<Expr>(ArbExprParams {
+                        tpe: SType::SColl(ty.into()),
+                        depth: 0,
+                    })
+                }),
             )
                 .prop_map(|(script_bytes, positions, new_values)| Self {
                     script_bytes: script_bytes.into(),
                     positions: positions.into(),
-                    new_values,
+                    new_values: new_values.into(),
                 })
                 .boxed()
         }
diff --git a/ergotree-ir/src/serialization/data.rs b/ergotree-ir/src/serialization/data.rs
index 19dbecebe..f8a151585 100644
--- a/ergotree-ir/src/serialization/data.rs
+++ b/ergotree-ir/src/serialization/data.rs
@@ -18,6 +18,7 @@ use crate::util::AsVecU8;
 use super::sigma_byte_writer::SigmaByteWrite;
 use std::convert::TryInto;
 
+/// Used to serialize and parse `Literal` and `Value`.
 pub struct DataSerializer {}
 
 impl DataSerializer {
@@ -73,6 +74,7 @@ impl DataSerializer {
             }
         })
     }
+
     pub fn sigma_parse<R: SigmaByteRead>(
         tpe: &SType,
         r: &mut R,


Test patch: