Adding `dedup` to `array` (#1738)

2 files changed, 33 insertions, 0 deletions

diff --git a/crates/typst/src/eval/array.rs b/crates/typst/src/eval/array.rs
index a7a1387b..5d5fdcdb 100644
--- a/crates/typst/src/eval/array.rs
+++ b/crates/typst/src/eval/array.rs
@@ -398,6 +398,38 @@ impl Array {
             .map(|(i, value)| array![i, value.clone()].into_value())
             .collect()
     }
+
+    /// Deduplicates all items in the array.
+    pub fn dedup(&self, vm: &mut Vm, key: Option<Func>) -> SourceResult<Self> {
+        let mut out = EcoVec::with_capacity(self.0.len());
+        let mut key_of = |x: Value| match &key {
+            // NOTE: We are relying on `comemo`'s memoization of function
+            // evaluation to not excessively reevaluate the `key`.
+            Some(f) => f.call_vm(vm, Args::new(f.span(), [x])),
+            None => Ok(x),
+        };
+
+        // This algorithm is O(N^2) because we cannot rely on `HashSet` since:
+        // 1. We would like to preserve the order of the elements.
+        // 2. We cannot hash arbitrary `Value`.
+        'outer: for value in self.iter() {
+            let key = key_of(value.clone())?;
+            if out.is_empty() {
+                out.push(value.clone());
+                continue;
+            }
+
+            for second in out.iter() {
+                if typst::eval::ops::equal(&key, &key_of(second.clone())?) {
+                    continue 'outer;
+                }
+            }
+
+            out.push(value.clone());
+        }
+
+        Ok(Self(out))
+    }
 }
 
 impl Debug for Array {
diff --git a/crates/typst/src/eval/methods.rs b/crates/typst/src/eval/methods.rs
index a7368426..bf47b7aa 100644
--- a/crates/typst/src/eval/methods.rs
+++ b/crates/typst/src/eval/methods.rs
@@ -147,6 +147,7 @@ pub fn call(
             "sorted" => array.sorted(vm, span, args.named("key")?)?.into_value(),
             "zip" => array.zip(args.expect("other")?).into_value(),
             "enumerate" => array.enumerate().into_value(),
+            "dedup" => array.dedup(vm, args.named("key")?)?.into_value(),
             _ => return missing(),
         },