adds property-based tests for diffing

hyperfiddle · Jul 8, 2024 · ee339df · ee339df
1 parent 3517e4b
commit ee339df
Show file tree

Hide file tree

Showing 3 changed files with 78 additions and 44 deletions.
diff --git a/deps.edn b/deps.edn
@@ -11,6 +11,7 @@
          org.clojure/tools.logging      {:mvn/version "1.2.4"}
          borkdude/edamame               {:mvn/version "1.4.25"}
          net.cgrand/xforms              {:mvn/version "0.19.6"}
+         org.clojure/test.check         {:mvn/version "1.1.1"}
          }
 
  :aliases {:dev  {:extra-paths ["src-dev" "src-docs" "test" "scratch" "resources-demo"] ; for clj command

diff --git a/src/hyperfiddle/incseq.cljc b/src/hyperfiddle/incseq.cljc
@@ -135,6 +135,45 @@ Reconstructs the permutation defined by given set of disjoint cycles.
 Return the empty diff for `n`-item collection.
 " d/empty-diff)
 
+(defn ->seq-differ [kf]
+  (let [state (doto (object-array 2) (aset 0 []) (aset 1 {}))]
+    (fn
+      ([]
+       (let [degree (count (aget state 0))]
+         (aset state 0 nil)
+         (aset state 1 nil)
+         {:grow 0 :shrink 0 :permutation {} :change {} :degree degree :freeze (set (range degree))}))
+      ([xs]
+       (let [prev-vec (aget state 0)
+             prev-idx (aget state 1)
+             _ (aset state 0 [])
+             _ (aset state 1 {})
+             size-before (count prev-vec)
+             [degree permutation change]
+             (reduce
+               (fn [[degree permutation change] x]
+                 (let [curr-vec (aget state 0)
+                       curr-idx (aget state 1)
+                       i (count curr-vec)
+                       k (kf x)
+                       [d y j]
+                       (or (some
+                             (fn [n]
+                               (let [j (permutation n n)]
+                                 (when-not (< j i)
+                                   [degree (nth prev-vec n) j])))
+                             (prev-idx k)) [(inc degree) state degree])]
+                   (aset state 0 (conj curr-vec x))
+                   (aset state 1 (assoc curr-idx k (conj (curr-idx k []) i)))
+                   [d (compose permutation (rotation i j))
+                    (if (= x y) change (assoc change i x))]))
+               [size-before {} {}] xs)
+             size-after (count (aget state 0))]
+         (assoc (empty-diff degree)
+           :grow (unchecked-subtract-int degree size-before)
+           :shrink (unchecked-subtract-int degree size-after)
+           :permutation (inverse permutation)
+           :change change))))))
 
 (def ^{:doc "
 Returns a flow producing the successive diffs of given continuous flow of collections, stabilized by given key function.
@@ -195,49 +234,8 @@ Returns a flow producing the successive diffs of given continuous flow of collec
                     (flow #(ready state)
                       #(do (aset state slot-done true)
                            (ready state))))
-                  (->Ps state cancel transfer))))
-            (differ [kf]
-              #(let [state (doto (object-array 2)
-                             (aset 0 [])
-                             (aset 1 {}))]
-                 (fn
-                   ([]
-                    (let [degree (count (aget state 0))]
-                      (aset state 0 nil)
-                      (aset state 1 nil)
-                      {:grow 0 :shrink 0 :permutation {} :change {} :degree degree :freeze (set (range degree))}))
-                   ([xs]
-                    (let [prev-vec (aget state 0)
-                          prev-idx (aget state 1)
-                          _ (aset state 0 [])
-                          _ (aset state 1 {})
-                          size-before (count prev-vec)
-                          [degree permutation change]
-                          (reduce
-                            (fn [[degree permutation change] x]
-                              (let [curr-vec (aget state 0)
-                                    curr-idx (aget state 1)
-                                    i (count curr-vec)
-                                    k (kf x)
-                                    [d y j]
-                                    (or (some
-                                          (fn [n]
-                                            (let [j (permutation n n)]
-                                              (when-not (< j i)
-                                                [degree (nth prev-vec n) j])))
-                                          (prev-idx k)) [(inc degree) state degree])]
-                                (aset state 0 (conj curr-vec x))
-                                (aset state 1 (assoc curr-idx k (conj (curr-idx k []) i)))
-                                [d (compose permutation (rotation i j))
-                                 (if (= x y) change (assoc change i x))]))
-                            [size-before {} {}] xs)
-                          size-after (count (aget state 0))]
-                      (assoc (empty-diff degree)
-                        :grow (unchecked-subtract-int degree size-before)
-                        :shrink (unchecked-subtract-int degree size-after)
-                        :permutation (inverse permutation)
-                        :change change))))))]
-      (fn [kf flow] (scan (differ kf) flow)))))
+                  (->Ps state cancel transfer))))]
+      (fn [kf flow] (scan #(->seq-differ kf) flow)))))
 
 
 (def ^{:doc "

diff --git a/test/hyperfiddle/incseq/diff_impl_test.cljc b/test/hyperfiddle/incseq/diff_impl_test.cljc
@@ -1,7 +1,12 @@
 (ns hyperfiddle.incseq.diff-impl-test
   (:require [hyperfiddle.incseq.diff-impl :as d]
             [hyperfiddle.incseq.perm-impl :as p]
-            [clojure.test :refer [deftest is]]))
+            [hyperfiddle.incseq :as i]
+            [clojure.test :refer [deftest is]]
+            [clojure.test.check :as tc]
+            [clojure.test.check.properties :as tc-prop]
+            [clojure.test.check.generators :as tc-gen]
+            [clojure.test.check.clojure-test :as tct]))
 
 (deftest combine-simple
   (is (= (d/combine
@@ -75,3 +80,33 @@
            {:degree 4, :grow 0, :shrink 0, :permutation {},                   :change {}, :freeze #{}}
            {:degree 4, :grow 0, :shrink 3, :permutation {1 0, 2 1, 3 2, 0 3}, :change {}, :freeze #{}})
         {:degree 4, :permutation {0 3, 3 0}, :grow 0, :shrink 3, :change {}, :freeze #{}})))
+
+(def patch-vecing-differ-result-returns-same-vector
+  (tc-prop/for-all [a (tc-gen/fmap vec (tc-gen/set tc-gen/small-integer))
+                    b (tc-gen/fmap vec (tc-gen/set tc-gen/small-integer))]
+    (let [a (into [] (distinct) a), b (into [] (distinct) b)
+          diff-seq (i/->seq-differ identity)]
+      (= b (d/patch-vec a (do (diff-seq a) (diff-seq b)))))))
+
+(tct/defspec patch-vecing-differ-result-returns-same-vector-spec 100 patch-vecing-differ-result-returns-same-vector)
+
+(def d-combine
+  (tc-prop/for-all [a (tc-gen/fmap vec (tc-gen/set tc-gen/small-integer))
+                    b (tc-gen/fmap vec (tc-gen/set tc-gen/small-integer))
+                    c (tc-gen/fmap vec (tc-gen/set tc-gen/small-integer))]
+    (let [a (into [] (distinct) a), b (into [] (distinct) b), c (into [] (distinct) c)
+          diff-seq (i/->seq-differ identity)
+          _ (diff-seq a), a->b (diff-seq b), b->c (diff-seq c)]
+      (= c (d/patch-vec a (d/combine a->b b->c))))))
+
+(comment
+  (let [a [], b [0 1], c []
+        diff-seq (i/->seq-differ identity)
+        _ (diff-seq a), a->b (diff-seq b), b->c (diff-seq c), a->c (d/combine a->b b->c)]
+    (prn :a->b a->b)
+    (prn :b->c b->c)
+    (prn :combined a->c)
+    (= c (d/patch-vec a a->c)))
+  )
+
+(tct/defspec d-combine-spec 100 d-combine)