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

Issue:
`Env` needs resetting after `Lambda` calls and `BlockValue`
A change that was introduced in v0.25 was in the `Evaluable` trait where `fn eval` now takes a mutable reference to `Env`. This introduces errors when lambdas are called and `BlockValues` are evaluated. Consider the diff between v0.24 and v0.25 for `Coll.exists`:
<img width="1162" alt="image" src="https://github.com/ergoplatform/sigma-rust/assets/791016/d96100fb-f2f6-4446-b12c-143ac76e0876">

We used to clone the `Env`, add the arg, then evaluate the function body. Now with mutable `Env`, the arg persists in the `Env` instance for subsequent `eval` calls. This will break validation since lambas are built by the interpreter like
```
val v15 = {
        (v15: Coll[Byte]) => 
          if (upcast(v15(0)) < 0) Coll[Coll[Byte]](, 0).append(v15) else v15
        }
```
See how `v15` is reused as an arg for the lambda which is already associated with `v15`. A subsequent use of `v15` will error because it will try to `Apply` on a `Coll[Byte]`.

------
I ran across this issue when trying to validate this [contract](https://github.com/spectrum-finance/spectrum/blob/b04ea4834635a15c28a37a4f18e6f27f5a714e83/spectrum-ergo-connector/contracts/signature_verification.sc#L254) which makes heavy use of lambdas. It validated perfectly for v0.24.1 and with the `sigmastate-interpreter`. PR #728 will resolve it.


Discussion / hints:

Fix patch:
diff --git a/ergotree-interpreter/Cargo.toml b/ergotree-interpreter/Cargo.toml
index d4f17b88a..75d873c69 100644
--- a/ergotree-interpreter/Cargo.toml
+++ b/ergotree-interpreter/Cargo.toml
@@ -37,6 +37,7 @@ proptest = { workspace = true, optional = true }
 scorex_crypto_avltree = "0.1.0"
 gf2_192 = { version = "^0.25.0", path = "../gf2_192" }
 miette = { workspace = true }
+hashbrown = "0.14.1"
 
 [features]
 default = ["json"]
diff --git a/ergotree-interpreter/src/eval/apply.rs b/ergotree-interpreter/src/eval/apply.rs
index 9a3c93352..0bcb7392f 100644
--- a/ergotree-interpreter/src/eval/apply.rs
+++ b/ergotree-interpreter/src/eval/apply.rs
@@ -1,6 +1,7 @@
 use ergotree_ir::mir::apply::Apply;
 use ergotree_ir::mir::val_def::ValId;
 use ergotree_ir::mir::value::Value;
+use hashbrown::HashMap;
 
 use crate::eval::env::Env;
 use crate::eval::EvalContext;
@@ -16,10 +17,27 @@ impl Evaluable for Apply {
         match func_v {
             Value::Lambda(fv) => {
                 let arg_ids: Vec<ValId> = fv.args.iter().map(|a| a.idx).collect();
+                let mut existing_variables = HashMap::new();
+                let mut new_variables = vec![];
                 arg_ids.iter().zip(args_v).for_each(|(idx, arg_v)| {
+                    if let Some(old_val) = env.get(*idx) {
+                        existing_variables.insert(idx, old_val.clone());
+                    } else {
+                        new_variables.push(*idx);
+                    }
                     env.insert(*idx, arg_v);
                 });
-                fv.body.eval(env, ctx)
+                let res = fv.body.eval(env, ctx);
+                new_variables.into_iter().for_each(|idx| {
+                    env.remove(&idx);
+                });
+                existing_variables
+                    .into_iter()
+                    .for_each(|(idx, orig_value)| {
+                        env.insert(*idx, orig_value);
+                    });
+
+                res
             }
             _ => Err(EvalError::UnexpectedValue(format!(
                 "expected func_v to be Value::FuncValue got: {0:?}",
diff --git a/ergotree-interpreter/src/eval/block.rs b/ergotree-interpreter/src/eval/block.rs
index dfe5b3c21..265b51f49 100644
--- a/ergotree-interpreter/src/eval/block.rs
+++ b/ergotree-interpreter/src/eval/block.rs
@@ -3,6 +3,7 @@ use ergotree_ir::mir::constant::TryExtractInto;
 use ergotree_ir::mir::val_def::ValDef;
 use ergotree_ir::mir::value::Value;
 use ergotree_ir::source_span::Spanned;
+use hashbrown::HashMap;
 
 use crate::eval::env::Env;
 use crate::eval::EvalContext;
@@ -11,14 +12,48 @@ use crate::eval::Evaluable;
 
 impl Evaluable for BlockValue {
     fn eval(&self, env: &mut Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
-        for i in &self.items {
-            // TODO: new try_extract_spanned_into?
-            let spanned_val_def = &i.clone().try_extract_into::<Spanned<ValDef>>()?;
-            let val_def = spanned_val_def.expr();
-            let v: Value = val_def.rhs.eval(env, ctx)?;
-            env.insert(val_def.id, v);
+        // The start of the top-level block of statements does not contain any
+        // pre-existing `ValDef`s.
+        let is_top_level_block = env.is_empty();
+
+        if is_top_level_block {
+            for i in &self.items {
+                // TODO: new try_extract_spanned_into?
+                let spanned_val_def = &i.clone().try_extract_into::<Spanned<ValDef>>()?;
+                let val_def = spanned_val_def.expr();
+                let v: Value = val_def.rhs.eval(env, ctx)?;
+                env.insert(val_def.id, v);
+            }
+            // Keep all `ValDef`s introduced in this block
+            self.result.eval(env, ctx)
+        } else {
+            let mut existing_variables = HashMap::new();
+            let mut new_variables = vec![];
+
+            for i in &self.items {
+                // TODO: new try_extract_spanned_into?
+                let spanned_val_def = &i.clone().try_extract_into::<Spanned<ValDef>>()?;
+                let val_def = spanned_val_def.expr();
+                let idx = val_def.id;
+                let v: Value = val_def.rhs.eval(env, ctx)?;
+                if let Some(old_val) = env.get(idx) {
+                    existing_variables.insert(idx, old_val.clone());
+                } else {
+                    new_variables.push(idx);
+                }
+                env.insert(idx, v);
+            }
+            let res = self.result.eval(env, ctx);
+            new_variables.into_iter().for_each(|idx| {
+                env.remove(&idx);
+            });
+            existing_variables
+                .into_iter()
+                .for_each(|(idx, orig_value)| {
+                    env.insert(idx, orig_value);
+                });
+            res
         }
-        self.result.eval(env, ctx)
     }
 }
 
diff --git a/ergotree-interpreter/src/eval/coll_exists.rs b/ergotree-interpreter/src/eval/coll_exists.rs
index 2a97500c2..ee5260499 100644
--- a/ergotree-interpreter/src/eval/coll_exists.rs
+++ b/ergotree-interpreter/src/eval/coll_exists.rs
@@ -19,8 +19,15 @@ impl Evaluable for Exists {
                         "Exists: evaluated condition has empty arguments list".to_string(),
                     )
                 })?;
+                let orig_val = env.get(func_arg.idx).cloned();
                 env.insert(func_arg.idx, arg);
-                func_value.body.eval(env, ctx)
+                let res = func_value.body.eval(env, ctx);
+                if let Some(orig_val) = orig_val {
+                    env.insert(func_arg.idx, orig_val);
+                } else {
+                    env.remove(&func_arg.idx);
+                }
+                res
             }
             _ => Err(EvalError::UnexpectedValue(format!(
                 "expected Exists::condition to be Value::FuncValue got: {0:?}",
diff --git a/ergotree-interpreter/src/eval/coll_filter.rs b/ergotree-interpreter/src/eval/coll_filter.rs
index 951adaf63..932efb293 100644
--- a/ergotree-interpreter/src/eval/coll_filter.rs
+++ b/ergotree-interpreter/src/eval/coll_filter.rs
@@ -20,8 +20,15 @@ impl Evaluable for Filter {
                         "Filter: evaluated condition has empty arguments list".to_string(),
                     )
                 })?;
+                let orig_val = env.get(func_arg.idx).cloned();
                 env.insert(func_arg.idx, arg);
-                func_value.body.eval(env, ctx)
+                let res = func_value.body.eval(env, ctx);
+                if let Some(orig_val) = orig_val {
+                    env.insert(func_arg.idx, orig_val);
+                } else {
+                    env.remove(&func_arg.idx);
+                }
+                res
             }
             _ => Err(EvalError::UnexpectedValue(format!(
                 "expected Filter::condition to be Value::FuncValue got: {0:?}",
diff --git a/ergotree-interpreter/src/eval/coll_fold.rs b/ergotree-interpreter/src/eval/coll_fold.rs
index 385870eaa..7bf20e453 100644
--- a/ergotree-interpreter/src/eval/coll_fold.rs
+++ b/ergotree-interpreter/src/eval/coll_fold.rs
@@ -20,8 +20,15 @@ impl Evaluable for Fold {
                     .args
                     .first()
                     .ok_or_else(|| EvalError::NotFound("empty argument for fold op".to_string()))?;
+                let orig_val = env.get(func_arg.idx).cloned();
                 env.insert(func_arg.idx, arg);
-                func_value.body.eval(env, ctx)
+                let res = func_value.body.eval(env, ctx);
+                if let Some(orig_val) = orig_val {
+                    env.insert(func_arg.idx, orig_val);
+                } else {
+                    env.remove(&func_arg.idx);
+                }
+                res
             }
             _ => Err(EvalError::UnexpectedValue(format!(
                 "expected fold_op to be Value::FuncValue got: {0:?}",
diff --git a/ergotree-interpreter/src/eval/coll_forall.rs b/ergotree-interpreter/src/eval/coll_forall.rs
index 0dec1520a..9dfb815b0 100644
--- a/ergotree-interpreter/src/eval/coll_forall.rs
+++ b/ergotree-interpreter/src/eval/coll_forall.rs
@@ -19,8 +19,15 @@ impl Evaluable for ForAll {
                         "ForAll: evaluated condition has empty arguments list".to_string(),
                     )
                 })?;
+                let orig_val = env.get(func_arg.idx).cloned();
                 env.insert(func_arg.idx, arg);
-                func_value.body.eval(env, ctx)
+                let res = func_value.body.eval(env, ctx);
+                if let Some(orig_val) = orig_val {
+                    env.insert(func_arg.idx, orig_val);
+                } else {
+                    env.remove(&func_arg.idx);
+                }
+                res
             }
             _ => Err(EvalError::UnexpectedValue(format!(
                 "expected ForAll::condition to be Value::FuncValue got: {0:?}",
diff --git a/ergotree-interpreter/src/eval/coll_map.rs b/ergotree-interpreter/src/eval/coll_map.rs
index 6745d08f3..384a6771b 100644
--- a/ergotree-interpreter/src/eval/coll_map.rs
+++ b/ergotree-interpreter/src/eval/coll_map.rs
@@ -19,8 +19,15 @@ impl Evaluable for Map {
                         "Map: evaluated mapper has empty arguments list".to_string(),
                     )
                 })?;
+                let orig_val = env.get(func_arg.idx).cloned();
                 env.insert(func_arg.idx, arg);
-                func_value.body.eval(env, ctx)
+                let res = func_value.body.eval(env, ctx);
+                if let Some(orig_val) = orig_val {
+                    env.insert(func_arg.idx, orig_val);
+                } else {
+                    env.remove(&func_arg.idx);
+                }
+                res
             }
             _ => Err(EvalError::UnexpectedValue(format!(
                 "expected mapper to be Value::FuncValue got: {0:?}",
diff --git a/ergotree-interpreter/src/eval/env.rs b/ergotree-interpreter/src/eval/env.rs
index b859d0476..78aba5259 100644
--- a/ergotree-interpreter/src/eval/env.rs
+++ b/ergotree-interpreter/src/eval/env.rs
@@ -18,6 +18,11 @@ impl Env {
         }
     }
 
+    /// Returns `true` if the environment is empty
+    pub fn is_empty(&self) -> bool {
+        self.store.is_empty()
+    }
+
     /// Extend this environment (create new) with added element
     pub fn extend(&self, idx: ValId, v: Value) -> Env {
         let mut new_store = self.store.clone();
@@ -30,6 +35,11 @@ impl Env {
         self.store.insert(idx, v);
     }
 
+    /// Remove a Value for the given ValId
+    pub fn remove(&mut self, idx: &ValId) {
+        self.store.remove(idx);
+    }
+
     /// Get an element
     pub fn get(&self, idx: ValId) -> Option<&Value> {
         self.store.get(&idx)
diff --git a/ergotree-interpreter/src/eval/scoll.rs b/ergotree-interpreter/src/eval/scoll.rs
index 4e1f0c625..e94f38c41 100644
--- a/ergotree-interpreter/src/eval/scoll.rs
+++ b/ergotree-interpreter/src/eval/scoll.rs
@@ -75,8 +75,15 @@ pub(crate) static FLATMAP_EVAL_FN: EvalFn = |env, ctx, obj, args| {
         let func_arg = lambda.args.first().ok_or_else(|| {
             EvalError::NotFound("flatmap: lambda has empty arguments list".to_string())
         })?;
+        let orig_val = env.get(func_arg.idx).cloned();
         env.insert(func_arg.idx, arg);
-        lambda.body.eval(env, ctx)
+        let res = lambda.body.eval(env, ctx);
+        if let Some(orig_val) = orig_val {
+            env.insert(func_arg.idx, orig_val);
+        } else {
+            env.remove(&func_arg.idx);
+        }
+        res
     };
     let mapper_input_tpe = lambda
         .args
diff --git a/ergotree-interpreter/src/eval/soption.rs b/ergotree-interpreter/src/eval/soption.rs
index f981f1444..1ff27b50b 100644
--- a/ergotree-interpreter/src/eval/soption.rs
+++ b/ergotree-interpreter/src/eval/soption.rs
@@ -23,8 +23,15 @@ pub(crate) static MAP_EVAL_FN: EvalFn = |env, ctx, obj, args| {
         let func_arg = lambda.args.first().ok_or_else(|| {
             EvalError::NotFound("map: lambda has empty arguments list".to_string())
         })?;
+        let orig_val = env.get(func_arg.idx).cloned();
         env.insert(func_arg.idx, arg);
-        lambda.body.eval(env, ctx)
+        let res = lambda.body.eval(env, ctx);
+        if let Some(orig_val) = orig_val {
+            env.insert(func_arg.idx, orig_val);
+        } else {
+            env.remove(&func_arg.idx);
+        }
+        res
     };
     let normalized_input_val: Option<Value> = match input_v {
         Value::Opt(opt) => Ok(*opt),
@@ -58,8 +65,15 @@ pub(crate) static FILTER_EVAL_FN: EvalFn = |env, ctx, obj, args| {
         let func_arg = lambda.args.first().ok_or_else(|| {
             EvalError::NotFound("filter: lambda has empty arguments list".to_string())
         })?;
+        let orig_val = env.get(func_arg.idx).cloned();
         env.insert(func_arg.idx, arg);
-        lambda.body.eval(env, ctx)
+        let res = lambda.body.eval(env, ctx);
+        if let Some(orig_val) = orig_val {
+            env.insert(func_arg.idx, orig_val);
+        } else {
+            env.remove(&func_arg.idx);
+        }
+        res
     };
     let normalized_input_val: Option<Value> = match input_v {
         Value::Opt(opt) => Ok(*opt),


Test patch: