From fec53d95fc4d7deff67379029a36d1f7b82e1517 Mon Sep 17 00:00:00 2001
From: J08nY
Date: Fri, 12 Apr 2024 14:17:11 +0200
Subject: Fix tree building with deduplicated dmaps.

---
 test/sca/test_tree.py | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)

(limited to 'test/sca')

diff --git a/test/sca/test_tree.py b/test/sca/test_tree.py
index 897ffd5..5db083c 100644
--- a/test/sca/test_tree.py
+++ b/test/sca/test_tree.py
@@ -1,4 +1,5 @@
 import random
+from collections import OrderedDict
 from copy import deepcopy
 
 from pyecsca.sca.re.tree import Tree, Map
@@ -90,6 +91,51 @@ def test_build_tree():
     tree.describe()
 
 
+def test_build_tree_dedup():
+    """Make sure that dmap deduplication does not affect the tree."""
+    cfgs = {"a", "b", "c", "d", "e", "f", "g"}
+    binary_sets = {
+        "a": {1, 2, 3},
+        "b": {2, 3, 4},
+        "c": {1, 2, 3},
+        "d": {4, 2},
+        "e": {4, 2},
+        "f": {4, 2},
+        "g": {4, 2},
+    }
+    dmap = Map.from_sets(cfgs, binary_sets)
+    original = deepcopy(dmap)
+    dmap.deduplicate()
+
+    tree = Tree.build(cfgs, original)
+    dedup = Tree.build(cfgs, dmap)
+    assert tree.describe() == dedup.describe()
+
+
+def test_build_tree_reorder():
+    """Make sure that dmap input order does not affect the tree."""
+    cfgs = {"a", "b", "c", "d", "e", "f", "g"}
+    binary_sets = {
+        "a": {1, 2, 3},
+        "b": {2, 3, 4},
+        "c": {1, 2, 3},
+        "d": {4, 2},
+        "e": {4, 2},
+        "f": {4, 2},
+        "g": {4, 2},
+    }
+    trees = set()
+    for i in range(10):
+        shuffled = list(binary_sets.items())
+        random.shuffle(shuffled)
+        bset = OrderedDict(shuffled)
+        dmap = Map.from_sets(cfgs, bset)
+        if i % 2 == 0:
+            dmap.deduplicate()
+        trees.add(Tree.build(cfgs, dmap).describe())
+    assert len(trees) == 1
+
+
 def test_expand_tree():
     cfgs = ["a", "b", "c"]
     cfg_map = pd.DataFrame([0, 1, 2], index=cfgs, columns=["vals"])
-- 
cgit v1.2.3-70-g09d2