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

Issue:
[100 SigmaUSD] AvlTree.contains
Implement `SMethod`(in `types::savltree`) and evaluation (in `eval::savltree`).
Reference Scala implementation - https://github.com/ScorexFoundation/sigmastate-interpreter/blob/c863a9b1a82589e47b15f76f3affdb30a475e740/sigmastate/src/main/scala/sigmastate/types.scala#L2103-L2163


Discussion / hints:
Im making a start on this one

Fix patch:
diff --git a/ergotree-interpreter/src/eval.rs b/ergotree-interpreter/src/eval.rs
index 324a0978a..0280f1da5 100644
--- a/ergotree-interpreter/src/eval.rs
+++ b/ergotree-interpreter/src/eval.rs
@@ -212,6 +212,7 @@ fn smethod_eval_fn(method: &SMethod) -> Result<EvalFn, EvalError> {
             savltree::GET_METHOD_ID => self::savltree::GET_EVAL_FN,
             savltree::GET_MANY_METHOD_ID => self::savltree::GET_MANY_EVAL_FN,
             savltree::INSERT_METHOD_ID => self::savltree::INSERT_EVAL_FN,
+            savltree::CONTAINS_METHOD_ID => self::savltree::CONTAINS_EVAL_FN,
             savltree::REMOVE_METHOD_ID => self::savltree::REMOVE_EVAL_FN,
             savltree::UPDATE_METHOD_ID => self::savltree::UPDATE_EVAL_FN,
             method_id => {
diff --git a/ergotree-interpreter/src/eval/savltree.rs b/ergotree-interpreter/src/eval/savltree.rs
index 2cda63774..812f89dee 100644
--- a/ergotree-interpreter/src/eval/savltree.rs
+++ b/ergotree-interpreter/src/eval/savltree.rs
@@ -315,6 +315,53 @@ pub(crate) static REMOVE_EVAL_FN: EvalFn =
         }
     };
 
+pub(crate) static CONTAINS_EVAL_FN: EvalFn = |_env, _ctx, obj, args| {
+    let avl_tree_data = obj.try_extract_into::<AvlTreeData>()?;
+    let key = {
+        let v = args
+            .get(0)
+            .cloned()
+            .ok_or_else(|| EvalError::AvlTree("eval is missing first arg (key)".to_string()))?;
+        Bytes::from(v.try_extract_into::<Vec<u8>>()?)
+    };
+
+    let proof = {
+        let v = args
+            .get(1)
+            .cloned()
+            .ok_or_else(|| EvalError::AvlTree("eval is missing second arg (proof)".to_string()))?;
+        Bytes::from(v.try_extract_into::<Vec<u8>>()?)
+    };
+
+    let starting_digest = Bytes::from(avl_tree_data.digest.0.to_vec());
+    let mut bv = BatchAVLVerifier::new(
+        &starting_digest,
+        &proof,
+        AVLTree::new(
+            |digest| Node::LabelOnly(NodeHeader::new(Some(*digest), None)),
+            avl_tree_data.key_length as usize,
+            avl_tree_data
+                .value_length_opt
+                .as_ref()
+                .map(|v| **v as usize),
+        ),
+        None,
+        None,
+    )
+    .map_err(map_eval_err)?;
+
+    match bv.perform_one_operation(&Operation::Lookup(key)) {
+        Ok(s) => match s {
+            Some(_e) => Ok(Value::Boolean(true)),
+            _ => Ok(Value::Boolean(false)),
+        },
+        Err(_) => Err(EvalError::AvlTree(format!(
+            "Incorrect contains call for {:?}",
+            avl_tree_data
+        ))),
+    }
+};
+
 pub(crate) static UPDATE_EVAL_FN: EvalFn =
     |_env, _ctx, obj, args| {
         let mut avl_tree_data = obj.try_extract_into::<AvlTreeData>()?;
@@ -823,6 +870,47 @@ mod tests {
         }
     }
 
+    #[test]
+    fn eval_avl_contains() {
+        let mut prover = populate_tree(vec![
+            (vec![1u8], 10u64.to_be_bytes().to_vec()),
+            (vec![2u8], 20u64.to_be_bytes().to_vec()),
+            (vec![3u8], 30u64.to_be_bytes().to_vec()),
+        ]);
+        let digest =
+            ADDigest::sigma_parse_bytes(&prover.digest().unwrap().into_iter().collect::<Vec<_>>())
+                .unwrap();
+
+        let op = Operation::Lookup(Bytes::from(vec![2u8]));
+        prover.perform_one_operation(&op).unwrap();
+
+        let key = Constant::from(vec![2u8]);
+        let proof: Constant = prover
+            .generate_proof()
+            .into_iter()
+            .collect::<Vec<_>>()
+            .into();
+        let tree_flags = AvlTreeFlags::new(false, false, false);
+        let obj = Expr::Const(
+            AvlTreeData {
+                digest,
+                tree_flags,
+                key_length: 1,
+                value_length_opt: None,
+            }
+            .into(),
+        );
+        let expr: Expr = MethodCall::new(
+            obj,
+            savltree::CONTAINS_METHOD.clone(),
+            vec![key.into(), proof.into()],
+        )
+        .unwrap()
+        .into();
+
+        assert!(eval_out_wo_ctx::<bool>(&expr));
+    }
+
     #[test]
     fn eval_avl_remove() {
         let mut prover = populate_tree(vec![(vec![1u8], 10u64.to_be_bytes().to_vec())]);
diff --git a/ergotree-ir/src/types/savltree.rs b/ergotree-ir/src/types/savltree.rs
index 2a4a8958a..5519b8629 100644
--- a/ergotree-ir/src/types/savltree.rs
+++ b/ergotree-ir/src/types/savltree.rs
@@ -29,6 +29,8 @@ pub const IS_UPDATE_ALLOWED_METHOD_ID: MethodId = MethodId(6);
 pub const IS_REMOVE_ALLOWED_METHOD_ID: MethodId = MethodId(7);
 /// AvlTree.updateOperations property
 pub const UPDATE_OPERATIONS_METHOD_ID: MethodId = MethodId(8);
+/// AvlTree.contains property
+pub const CONTAINS_METHOD_ID: MethodId = MethodId(9);
 /// AvlTree.get property
 pub const GET_METHOD_ID: MethodId = MethodId(10);
 /// AvlTree.getMany property
@@ -54,6 +56,7 @@ lazy_static! {
             &IS_UPDATE_ALLOWED_METHOD_DESC,
             &IS_REMOVE_ALLOWED_METHOD_DESC,
             &UPDATE_OPERATIONS_METHOD_DESC,
+            &CONTAINS_METHOD_DESC,
             &GET_METHOD_DESC,
             &GET_MANY_METHOD_DESC,
             &INSERT_METHOD_DESC,
@@ -271,6 +274,25 @@ lazy_static! {
         SMethod::new(STypeCompanion::AvlTree, REMOVE_METHOD_DESC.clone(),);
 }
 
+lazy_static! {
+    static ref CONTAINS_METHOD_DESC: SMethodDesc = SMethodDesc {
+        method_id: CONTAINS_METHOD_ID,
+        name: "contains",
+        tpe: SFunc {
+            t_dom: vec![
+                SType::SAvlTree,
+                SType::SColl(Box::new(SType::SByte)),
+                SType::SColl(Box::new(SType::SByte)),
+            ],
+            t_range: SType::SBoolean.into(),
+            tpe_params: vec![],
+        },
+    };
+    /// AvlTree.contains
+    pub static ref CONTAINS_METHOD: SMethod =
+        SMethod::new(STypeCompanion::AvlTree, CONTAINS_METHOD_DESC.clone(),);
+}
+
 lazy_static! {
     static ref UPDATE_METHOD_DESC: SMethodDesc = SMethodDesc {
         method_id: UPDATE_METHOD_ID,


Test patch: