Repository: stellar/rs-soroban-env
Pull request #387 (2022-08-29 18:06:20)

Add hostfns to find an element in a vec
### What

Resolves https://github.com/stellar/rs-soroban-env/issues/317.
- `vec_first_index_of`
- `vec_last_index_of`
- `vec_binary_search`

### Why

[TODO: Why this change is being made. Include any context required to understand the why.]

### Known limitations

[TODO or N/A]



Patch:
diff --git a/soroban-env-common/src/env.rs b/soroban-env-common/src/env.rs
index 03f22d5f..0652a2a6 100644
--- a/soroban-env-common/src/env.rs
+++ b/soroban-env-common/src/env.rs
@@ -243,6 +243,19 @@ macro_rules! call_macro_with_all_host_functions {
                 /// Copy the elements from `start` index until `end` index, exclusive, in the vector and create a new vector from it.
                 /// Return the new vector. Traps if the index is out of bound.
                 {"A", fn vec_slice(v:Object, start:RawVal, end:RawVal) -> Object}
+                /// Get the index of the first occurrence of a given element in the vector.
+                /// Returns the u32 index of the value if it's there. Otherwise, it returns `ScStatic::Void`.
+                {"B", fn vec_first_index_of(v:Object, x:RawVal) -> RawVal}
+                /// Get the index of the last occurrence of a given element in the vector.
+                /// Returns the u32 index of the value if it's there. Otherwise, it returns `ScStatic::Void`.
+                {"C", fn vec_last_index_of(v:Object, x:RawVal) -> RawVal}
+                /// Binary search a sorted vector for a given element.
+                /// If it exists, the high-32 bits of the return value is 0x0001 and the low-32 bits
+                /// contain the u32 index of the element.
+                /// If it does not exist, the high-32 bits of the return value is 0x0000 and the low-32 bits
+                /// contain the u32 index at which the element would need to be inserted into the vector to
+                /// maintain sorted order.
+                {"D", fn vec_binary_search(v:Object, x:RawVal) -> u64}
             }
 
             mod ledger "l" {
diff --git a/soroban-env-common/src/meta.rs b/soroban-env-common/src/meta.rs
index c970c732..88ca0b8a 100644
--- a/soroban-env-common/src/meta.rs
+++ b/soroban-env-common/src/meta.rs
@@ -56,5 +56,5 @@
 // implementations over a long period of time.
 
 soroban_env_macros::generate_env_meta_consts!(
-    interface_version: 7,
+    interface_version: 8,
 );
diff --git a/soroban-env-host/src/host.rs b/soroban-env-host/src/host.rs
index 964b1333..6f793e25 100644
--- a/soroban-env-host/src/host.rs
+++ b/soroban-env-host/src/host.rs
@@ -1236,6 +1236,34 @@ impl CheckedEnv for Host {
         Ok(self.add_host_object(vnew)?.into())
     }
 
+    fn vec_first_index_of(&self, v: Object, x: RawVal) -> Result<RawVal, Self::Error> {
+        let x = self.associate_raw_val(x);
+        self.visit_obj(v, |hv: &HostVec| {
+            Ok(match hv.first_index_of(&x)? {
+                Some(u) => self.usize_to_rawval_u32(u)?,
+                None => RawVal::from_void(),
+            })
+        })
+    }
+
+    fn vec_last_index_of(&self, v: Object, x: RawVal) -> Result<RawVal, Self::Error> {
+        let x = self.associate_raw_val(x);
+        self.visit_obj(v, |hv: &HostVec| {
+            Ok(match hv.last_index_of(&x)? {
+                Some(u) => self.usize_to_rawval_u32(u)?,
+                None => RawVal::from_void(),
+            })
+        })
+    }
+
+    fn vec_binary_search(&self, v: Object, x: RawVal) -> Result<u64, Self::Error> {
+        let x = self.associate_raw_val(x);
+        self.visit_obj(v, |hv: &HostVec| {
+            let res = hv.binary_search(&x)?;
+            self.u64_from_binary_search_result(res)
+        })
+    }
+
     // Notes on metering: covered by components
     fn put_contract_data(&self, k: RawVal, v: RawVal) -> Result<RawVal, HostError> {
         let key = self.contract_data_key_from_rawval(k)?;
diff --git a/soroban-env-host/src/host/conversion.rs b/soroban-env-host/src/host/conversion.rs
index bde53aa8..4eacf140 100644
--- a/soroban-env-host/src/host/conversion.rs
+++ b/soroban-env-host/src/host/conversion.rs
@@ -294,4 +294,27 @@ impl Host {
             )),
         }
     }
+
+    /// Converts a binary search result into a u64. `res` is `Some(index)`
+    /// if the value was found at `index`, or `Err(index)` if the value was not found
+    /// and would've needed to be inserted at `index`.
+    /// Returns a Some(res_u64) where :
+    /// - the high-32 bits is 0x0001 if element existed or 0x0000 if it didn't
+    /// - the low-32 bits contains the u32 representation of the `index`
+    /// Err(_) if the `index` fails to be converted to an u32.
+    pub(crate) fn u64_from_binary_search_result(
+        &self,
+        res: Result<usize, usize>,
+    ) -> Result<u64, HostError> {
+        match res {
+            Ok(u) => {
+                let v = self.usize_to_u32(u, "outside range")?;
+                Ok(u64::from(v) | (1 << u32::BITS))
+            }
+            Err(u) => {
+                let v = self.usize_to_u32(u, "outside range")?;
+                Ok(u64::from(v))
+            }
+        }
+    }
 }
diff --git a/soroban-env-host/src/host/metered_vector.rs b/soroban-env-host/src/host/metered_vector.rs
index d95beb3b..06973c31 100644
--- a/soroban-env-host/src/host/metered_vector.rs
+++ b/soroban-env-host/src/host/metered_vector.rs
@@ -122,6 +122,38 @@ impl<A: Clone> MeteredVector<A> {
         })
     }
 
+    /// Time: O(n)
+    pub fn first_index_of(&self, value: &A) -> Result<Option<usize>, HostError>
+    where
+        A: PartialEq,
+    {
+        self.charge_immut_access(self.len() as u64)?;
+        Ok(self.vec.index_of(value))
+    }
+
+    /// Time: O(n)
+    pub fn last_index_of(&self, value: &A) -> Result<Option<usize>, HostError>
+    where
+        A: PartialEq,
+    {
+        self.charge_immut_access(self.len() as u64)?;
+        for (index, item) in self.vec.iter().rev().enumerate() {
+            if value == item {
+                return Ok(Some(self.len() - 1 - index));
+            }
+        }
+        Ok(None)
+    }
+
+    /// Time: O(log n)
+    pub fn binary_search(&self, value: &A) -> Result<Result<usize, usize>, HostError>
+    where
+        A: Ord,
+    {
+        self.charge_immut_access(self.len() as u64)?;
+        Ok(self.vec.binary_search(value))
+    }
+
     /// Time: O(1)
     #[inline]
     pub fn iter(&self) -> Iter<'_, A> {


Test patch:
diff --git a/soroban-env-host/src/test/vec.rs b/soroban-env-host/src/test/vec.rs
index 6629bc8c..2f88c839 100644
--- a/soroban-env-host/src/test/vec.rs
+++ b/soroban-env-host/src/test/vec.rs
@@ -290,3 +290,35 @@ fn vec_append_empty() -> Result<(), HostError> {
     assert_eq!(host.obj_cmp(obj0.into(), obj1.into())?, 0);
     Ok(())
 }
+
+#[test]
+fn vec_index_of() -> Result<(), HostError> {
+    let host = Host::default();
+    let obj0 = host.test_vec_obj::<u32>(&[3, 4, 2, 2, 2, 5])?;
+    let mut idx = host.vec_first_index_of(obj0.val, 2u32.into())?;
+    assert_eq!(idx.get_payload(), RawVal::from(2u32).get_payload());
+    idx = host.vec_last_index_of(obj0.val, 2u32.into())?;
+    assert_eq!(idx.get_payload(), RawVal::from(4u32).get_payload());
+    idx = host.vec_first_index_of(obj0.val, 1u32.into())?;
+    assert_eq!(idx.get_payload(), RawVal::from_void().get_payload());
+    idx = host.vec_last_index_of(obj0.val, 1u32.into())?;
+    assert_eq!(idx.get_payload(), RawVal::from_void().get_payload());
+    Ok(())
+}
+
+#[test]
+fn vec_binary_search() -> Result<(), HostError> {
+    let host = Host::default();
+    let obj0 = host.test_vec_obj::<u32>(&[1, 2, 4, 5, 7, 9])?;
+    let mut res = host.vec_binary_search(obj0.val, 7u32.into())?;
+    let exp: u64 = 4 | (1 << 32);
+    assert_eq!(res, exp);
+    res = host.vec_binary_search(obj0.val, 4u32.into())?;
+    let exp: u64 = 2 | (1 << 32);
+    assert_eq!(res, exp);
+    res = host.vec_binary_search(obj0.val, 3u32.into())?;
+    assert_eq!(u64::from(2u32), res);
+    res = host.vec_binary_search(obj0.val, 6u32.into())?;
+    assert_eq!(u64::from(4u32), res);
+    Ok(())
+}