Make formula expand deterministic.

4 files changed, 58 insertions, 33 deletions

diff --git a/pyecsca/ec/formula/expand.py b/pyecsca/ec/formula/expand.py
index 2f631f7..eff227d 100644
--- a/pyecsca/ec/formula/expand.py
+++ b/pyecsca/ec/formula/expand.py
@@ -1,29 +1,46 @@
 """Provides a formula expansion function."""
-from typing import Set, Callable, Any
+
+from typing import Set, Callable, Any, List, Iterable
 from public import public
+from operator import attrgetter
+from functools import lru_cache
 
 from pyecsca.ec.formula.base import Formula
 from pyecsca.ec.formula.efd import EFDFormula
 from pyecsca.ec.formula.fliparoo import recursive_fliparoo
 from pyecsca.ec.formula.metrics import ivs_norm
-from pyecsca.ec.formula.partitions import reduce_all_adds, expand_all_muls, expand_all_nopower2_muls
+from pyecsca.ec.formula.partitions import (
+    reduce_all_adds,
+    expand_all_muls,
+    expand_all_nopower2_muls,
+)
 from pyecsca.ec.formula.switch_sign import generate_switched_formulas
 
 
 def reduce_with_similarity(
-    formulas: Set[Formula], norm: Callable[[Formula], Any]
-) -> Set[Formula]:
-    reduced = set(filter(lambda x: isinstance(x, EFDFormula), formulas))
+    formulas: List[Formula], norm: Callable[[Formula], Any]
+) -> List[Formula]:
+    reduced = list(filter(lambda x: isinstance(x, EFDFormula), formulas))
     similarities = list(map(norm, reduced))
     for formula in formulas:
         n = norm(formula)
         if n in similarities:
             continue
         similarities.append(n)
-        reduced.add(formula)
+        reduced.append(formula)
     return reduced
 
 
+def reduce_by_eq(formulas: Iterable[Formula]) -> List[Formula]:
+    unique = set()
+    result = []
+    for formula in formulas:
+        if formula not in unique:
+            unique.add(formula)
+            result.append(formula)
+    return result
+
+
 @public
 def expand_formula_set(
     formulas: Set[Formula], norm: Callable[[Formula], Any] = ivs_norm
@@ -38,25 +55,31 @@ def expand_formula_set(
     :param norm:
     :return:
     """
-    extended = reduce_with_similarity(formulas, norm)
+    @lru_cache(maxsize=1000)
+    def cached(formula):
+        return norm(formula)
+
+    extended = sorted(formulas, key=attrgetter("name"))
+    extended = reduce_with_similarity(extended, cached)
 
-    fliparood: Set[Formula] = set().union(*map(recursive_fliparoo, extended))
-    extended.update(fliparood)
-    extended = reduce_with_similarity(extended, norm)
+    fliparood: List[Formula] = reduce_by_eq(sum(map(lambda f: reduce_by_eq(recursive_fliparoo(f)), extended), []))
+    extended.extend(fliparood)
+    extended = reduce_with_similarity(extended, cached)
 
-    switch_signs: Set[Formula] = set().union(
-        *(set(generate_switched_formulas(f)) for f in extended)
-    )
-    extended.update(switch_signs)
-    extended = reduce_with_similarity(extended, norm)
+    switch_signs: List[Formula] = reduce_by_eq(sum(map(lambda f: reduce_by_eq(generate_switched_formulas(f)), extended), []))
+    extended.extend(switch_signs)
+    extended = reduce_with_similarity(extended, cached)
 
-    extended.update(set(map(reduce_all_adds, extended)))
-    extended = reduce_with_similarity(extended, norm)
+    add_reduced: List[Formula] = reduce_by_eq(list(map(reduce_all_adds, extended)))
+    extended.extend(add_reduced)
+    extended = reduce_with_similarity(extended, cached)
 
-    extended.update(set(map(expand_all_muls, extended)))
-    extended = reduce_with_similarity(extended, norm)
+    mul_expanded: List[Formula] = reduce_by_eq(list(map(expand_all_muls, extended)))
+    extended.extend(mul_expanded)
+    extended = reduce_with_similarity(extended, cached)
 
-    extended.update(set(map(expand_all_nopower2_muls, extended)))
-    extended = reduce_with_similarity(extended, norm)
+    np2_expanded: List[Formula] = reduce_by_eq(list(map(expand_all_nopower2_muls, extended)))
+    extended.extend(np2_expanded)
+    extended = reduce_with_similarity(extended, cached)
 
-    return extended
+    return set(reduce_by_eq(extended))
diff --git a/pyecsca/ec/formula/fliparoo.py b/pyecsca/ec/formula/fliparoo.py
index 4e1d221..fd744b5 100644
--- a/pyecsca/ec/formula/fliparoo.py
+++ b/pyecsca/ec/formula/fliparoo.py
@@ -380,19 +380,19 @@ def combine_signed_nodes(
 
 
 @public
-def recursive_fliparoo(formula: Formula, depth: int = 2) -> Set[Formula]:
-    all_fliparoos = {0: {formula}}
+def recursive_fliparoo(formula: Formula, depth: int = 2) -> List[Formula]:
+    all_fliparoos = {0: [formula]}
     counter = 0
     while depth > counter:
         prev_level = all_fliparoos[counter]
-        fliparoo_level: Set[Formula] = set()
+        fliparoo_level: List[Formula] = []
         for flipparood_formula in prev_level:
             rename = not counter  # rename ivs before the first fliparoo
             for newly_fliparood in generate_fliparood_formulas(
                 flipparood_formula, rename
             ):
-                fliparoo_level.add(newly_fliparood)
+                fliparoo_level.append(newly_fliparood)
         counter += 1
         all_fliparoos[counter] = fliparoo_level
 
-    return set().union(*all_fliparoos.values())
+    return sum(all_fliparoos.values(), [])
diff --git a/pyecsca/ec/formula/graph.py b/pyecsca/ec/formula/graph.py
index d4a79b1..6714bef 100644
--- a/pyecsca/ec/formula/graph.py
+++ b/pyecsca/ec/formula/graph.py
@@ -348,7 +348,7 @@ class FormulaGraph:
             iu = self.node_index(u)
             for v in self.output_nodes():
                 iv = self.node_index(v)
-                index_paths.extend(nx.all_simple_paths(gnx, iu, iv))
+                index_paths.extend(sorted(nx.all_simple_paths(gnx, iu, iv)))
         paths = []
         for p in index_paths:
             paths.append([self.nodes[v] for v in p])
diff --git a/pyecsca/ec/formula/switch_sign.py b/pyecsca/ec/formula/switch_sign.py
index e6397a0..01a5e4f 100644
--- a/pyecsca/ec/formula/switch_sign.py
+++ b/pyecsca/ec/formula/switch_sign.py
@@ -1,11 +1,13 @@
 from typing import Dict, Iterator, List, Any
 from ast import parse
+
+from mypy.errors import Iterable
 from public import public
 from itertools import chain, combinations
 
 from pyecsca.ec.op import OpType, CodeOp
 from pyecsca.ec.formula.base import Formula
-from pyecsca.ec.formula.graph import FormulaGraph, ConstantNode, CodeOpNode, CodeFormula
+from pyecsca.ec.formula.graph import FormulaGraph, ConstantNode, CodeOpNode, CodeFormula, Node
 from pyecsca.ec.point import Point
 from pyecsca.ec.mod import Mod, mod
 
@@ -20,14 +22,14 @@ def generate_switched_formulas(formula: Formula, rename=True) -> Iterator[CodeFo
             continue
 
 
-def subnode_lists(graph: FormulaGraph):
+def subnode_lists(graph: FormulaGraph) -> List[List[CodeOpNode]]:
     return powerlist(filter(lambda x: x not in graph.roots and x.is_sub, graph.nodes))
 
 
-def switch_sign(graph: FormulaGraph, node_combination) -> FormulaGraph:
+def switch_sign(graph: FormulaGraph, node_combination: List[CodeOpNode]) -> FormulaGraph:
     nodes_i = [graph.node_index(node) for node in node_combination]
     graph = graph.deepcopy()
-    node_combination = {graph.nodes[node_i] for node_i in nodes_i}
+    node_combination = [graph.nodes[node_i] for node_i in nodes_i]  # type: ignore
     output_signs = {out: 1 for out in graph.output_names}
 
     queue = []
@@ -131,6 +133,6 @@ def change_sides(node):
     )
 
 
-def powerlist(iterable: Iterator) -> List:
+def powerlist(iterable: Iterable) -> List:
     s = list(iterable)
     return list(chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)))