comet.sh
An Elixir implementation of AT Protocol-flavoured Merkle Search Trees (MST)
ovyerus.com
1defmodule MST.DiffTest do
2 use ExUnit.Case, async: true
3
4 doctest MST.Diff
5
6 alias DASL.CID
7 alias MST.{Diff, Tree}
8
9 defp new_tree, do: Tree.new(MST.Store.Memory.new())
10 defp val(s), do: CID.compute(s, :raw)
11
12 describe "compute/2" do
13 test "two empty trees produce empty diff" do
14 assert {:ok, diff} = Diff.compute(new_tree(), new_tree())
15 assert MapSet.size(diff.created_nodes) == 0
16 assert MapSet.size(diff.deleted_nodes) == 0
17 assert diff.record_ops == []
18 end
19
20 test "empty → non-empty: all keys are creates" do
21 v = val("v")
22 {:ok, tree_b} = Tree.put(new_tree(), "col/a", v)
23 assert {:ok, diff} = Diff.compute(new_tree(), tree_b)
24 assert length(diff.record_ops) == 1
25 op = hd(diff.record_ops)
26 assert op.key == "col/a"
27 assert op.old_value == nil
28 assert op.new_value == v
29 end
30
31 test "non-empty → empty: all keys are deletes" do
32 v = val("v")
33 {:ok, tree_a} = Tree.put(new_tree(), "col/a", v)
34 assert {:ok, diff} = Diff.compute(tree_a, new_tree())
35 assert length(diff.record_ops) == 1
36 op = hd(diff.record_ops)
37 assert op.key == "col/a"
38 assert op.old_value == v
39 assert op.new_value == nil
40 end
41
42 test "identical trees produce empty diff" do
43 v = val("v")
44 {:ok, tree} = Tree.put(new_tree(), "col/a", v)
45 assert {:ok, diff} = Diff.compute(tree, tree)
46 assert diff.record_ops == []
47 assert MapSet.size(diff.created_nodes) == 0
48 assert MapSet.size(diff.deleted_nodes) == 0
49 end
50
51 test "update: same key, different value" do
52 v1 = val("v1")
53 v2 = val("v2")
54 {:ok, tree_a} = Tree.put(new_tree(), "col/a", v1)
55 {:ok, tree_b} = Tree.put(new_tree(), "col/a", v2)
56 assert {:ok, diff} = Diff.compute(tree_a, tree_b)
57 assert length(diff.record_ops) == 1
58 op = hd(diff.record_ops)
59 assert op.old_value == v1
60 assert op.new_value == v2
61 end
62
63 test "no-op: same key, same value, different surrounding context" do
64 v = val("v")
65 v2 = val("v2")
66 {:ok, tree_a} = Tree.put(new_tree(), "col/a", v)
67 {:ok, tree_a} = Tree.put(tree_a, "col/b", v2)
68 {:ok, tree_b} = Tree.put(new_tree(), "col/a", v)
69 {:ok, tree_b} = Tree.put(tree_b, "col/c", v2)
70 assert {:ok, diff} = Diff.compute(tree_a, tree_b)
71 keys = Enum.map(diff.record_ops, & &1.key)
72 refute "col/a" in keys
73 assert "col/b" in keys
74 assert "col/c" in keys
75 end
76
77 test "record_ops are sorted by key" do
78 v = val("v")
79
80 {:ok, tree_b} =
81 Enum.reduce(["col/z", "col/a", "col/m"], new_tree(), fn k, acc ->
82 {:ok, t} = Tree.put(acc, k, v)
83 t
84 end)
85 |> then(&{:ok, &1})
86
87 assert {:ok, diff} = Diff.compute(new_tree(), tree_b)
88 keys = Enum.map(diff.record_ops, & &1.key)
89 assert keys == Enum.sort(keys)
90 end
91
92 test "created_nodes and deleted_nodes are non-overlapping for insert" do
93 v = val("v")
94 {:ok, tree_b} = Tree.put(new_tree(), "col/a", v)
95 assert {:ok, diff} = Diff.compute(new_tree(), tree_b)
96 assert MapSet.disjoint?(diff.created_nodes, diff.deleted_nodes)
97 end
98
99 test "multi-key add and remove" do
100 v = val("v")
101 va = val("va")
102
103 {:ok, base} = Tree.put(new_tree(), "col/keep", v)
104 {:ok, tree_a} = Tree.put(base, "col/remove", v)
105 {:ok, tree_b} = Tree.put(base, "col/add", va)
106
107 assert {:ok, diff} = Diff.compute(tree_a, tree_b)
108
109 op_keys = Enum.map(diff.record_ops, & &1.key) |> MapSet.new()
110 assert MapSet.member?(op_keys, "col/remove")
111 assert MapSet.member?(op_keys, "col/add")
112 refute MapSet.member?(op_keys, "col/keep")
113 end
114 end
115end