mds-kbdc: fix nesting inside unordered

Signed-off-by: Mattias Andrée <maandree@operamail.com>

3 files changed, 199 insertions, 22 deletions

diff --git a/src/mds-kbdc/simplify-tree.c b/src/mds-kbdc/simplify-tree.c
index a6b4247..b9a5d7a 100644
--- a/src/mds-kbdc/simplify-tree.c
+++ b/src/mds-kbdc/simplify-tree.c
@@ -381,8 +381,8 @@ static int simplify_map(mds_kbdc_tree_map_t* restrict tree)
   mds_kbdc_tree_t** here;
   mds_kbdc_tree_t* dup_sequence = NULL;
   mds_kbdc_tree_t* temp;
-  size_t argument_index = 0;
-  int redo = 0, saved_errno;
+  size_t argument_index;
+  int redo = 0, need_reelimination, saved_errno;
   
   /* Check for bad things in the result. */
   for (argument = tree->result; argument; argument = argument->next)
@@ -425,24 +425,32 @@ static int simplify_map(mds_kbdc_tree_map_t* restrict tree)
   /* Remove ‘.’:s. */
   REMOVE_NOTHING(sequence);
   
-  /* Copy sequence. */
-  fail_if ((dup_sequence = mds_kbdc_tree_dup(tree->sequence), dup_sequence == NULL));
-  
-  /* Eliminate alterations, remember, unordered subsequences have
-     been simplified to alternations of ordered subsequences. */
-  for (argument = dup_sequence; argument; argument = argument->next, argument_index++)
-    if (argument->type == C(ALTERNATION))
-      fail_if (eliminate_alternation((mds_kbdc_tree_t*)tree, argument, argument_index));
-  
-  mds_kbdc_tree_free(dup_sequence), dup_sequence = NULL;
-  
-  /* Eliminated ordered subsequences. */
-  for (here = &(tree->sequence); (argument = *here); redo ? (redo = 0) : (here = &(argument->next), 0))
-    if (argument->type == C(ORDERED))
-      {
-	FLATTEN(argument);
-	redo = 1;
-      }
+  /* Because unordered are simplified to alternations of ordered subsequences, which
+     in turn can contain alternations, possibiled from simplification of nested
+     unordered sequenceses, we need to reeliminated until there are not alternations. */
+  for (need_reelimination = 1; need_reelimination ? (need_reelimination = 0, 1) : 0; redo = 0)
+    {
+      /* Copy sequence. */
+      fail_if ((dup_sequence = mds_kbdc_tree_dup(tree->sequence), dup_sequence == NULL));
+      
+      /* Eliminate alterations, remember, unordered subsequences have
+	 been simplified to alternations of ordered subsequences. */
+      for (argument_index = 0, argument = dup_sequence; argument; argument = argument->next, argument_index++)
+	if (argument->type == C(ALTERNATION))
+	  fail_if (eliminate_alternation((mds_kbdc_tree_t*)tree, argument, argument_index));
+      
+      mds_kbdc_tree_free(dup_sequence), dup_sequence = NULL;
+      
+      /* Eliminated ordered subsequences. */
+      for (here = &(tree->sequence); (argument = *here); redo ? (redo = 0) : (here = &(argument->next), 0))
+	if (argument->type == C(ORDERED))
+	  {
+	    FLATTEN(argument);
+	    redo = 1;
+	  }
+	else if (argument->type == C(ALTERNATION))
+	  need_reelimination = 1;
+    }
   
   /* Valid value properties. */
   if (tree->result == NULL)
diff --git a/test-files/mds-kbdc/simplify-tree/valid/alternation_inside_unordered b/test-files/mds-kbdc/simplify-tree/valid/alternation_inside_unordered
index da3d3d2..b1a9524 100644
--- a/test-files/mds-kbdc/simplify-tree/valid/alternation_inside_unordered
+++ b/test-files/mds-kbdc/simplify-tree/valid/alternation_inside_unordered
@@ -1,4 +1,39 @@
 (1 [2 3]) : 0
 
-# TODO
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 4-5) ‘2’)
+#   )
+#   (.result
+#     (string (@ 1 12-13) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 6-7) ‘3’)
+#   )
+#   (.result
+#     (string (@ 1 12-13) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 4-5) ‘2’)
+#     (string (@ 1 1-2) ‘1’)
+#   )
+#   (.result
+#     (string (@ 1 12-13) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 1-2) ‘1’)
+#   )
+#   (.result
+#     (string (@ 1 12-13) ‘0’)
+#   )
+# )
 
diff --git a/test-files/mds-kbdc/simplify-tree/valid/unordered_inside_unordered b/test-files/mds-kbdc/simplify-tree/valid/unordered_inside_unordered
index ce999a2..e312725 100644
--- a/test-files/mds-kbdc/simplify-tree/valid/unordered_inside_unordered
+++ b/test-files/mds-kbdc/simplify-tree/valid/unordered_inside_unordered
@@ -1,4 +1,138 @@
 (1 2 (3 4)) : 0
 
-# TODO
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 8-9) ‘4’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 6-7) ‘3’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 3-4) ‘2’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 3-4) ‘2’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 8-9) ‘4’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 6-7) ‘3’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 1-2) ‘1’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 1-2) ‘1’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 3-4) ‘2’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 1-2) ‘1’)
+#     (string (@ 1 3-4) ‘2’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 1-2) ‘1’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# (map (@ 1 0-0)
+#   (.sequence
+#     (string (@ 1 8-9) ‘4’)
+#     (string (@ 1 6-7) ‘3’)
+#     (string (@ 1 3-4) ‘2’)
+#     (string (@ 1 1-2) ‘1’)
+#   )
+#   (.result
+#     (string (@ 1 14-15) ‘0’)
+#   )
+# )
+# :1:5–6: warning: unordered subsequence inside unordered subsequence is discouraged
+#  (1 2 (3 4)) : 0
+#       ^