From 4100c42bc6a64597abf81cd9dddc2773f0932f6e Mon Sep 17 00:00:00 2001
From: Mattias Andrée <maandree@operamail.com>
Date: Fri, 28 Nov 2014 18:01:28 +0100
Subject: mds-kbdc: simplification of unordered subseq:s
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Signed-off-by: Mattias Andrée <maandree@operamail.com>
---
doc/info/mds.texinfo | 19 +++++
src/mds-kbdc/simplify-tree.c | 170 +++++++++++++++++++++++++++++++++++++------
src/mds-kbdc/tree.c | 3 +
3 files changed, 168 insertions(+), 24 deletions(-)
diff --git a/doc/info/mds.texinfo b/doc/info/mds.texinfo
index 6f5e5f5..a4bb672 100644
--- a/doc/info/mds.texinfo
+++ b/doc/info/mds.texinfo
@@ -5461,6 +5461,25 @@ may however choose to discourage unordered
subsequence inside unordered subsequence
because of readability issues.
+Unordered subsequences longer than 5 elements
+cannot compile under normal circumstances. This
+is eliminiation of unordered subsequences grows
+superexponentially, and thus is probably an error
+than can cause memory exhaustion and unrealistic
+compilation-time. Therefore, if an unordered
+subsequences longer than 5 elements is used the
+compiler required that the @option{--force} flag
+is used and that the unordered subsequences uses
+double brackets:
+
+@example
+<dead compose> ("1" "2" "3" "4" "5") : "120"
+<dead compose> (("1" "2" "3" "4" "5" "6")) : "720"
+<dead compose> (("1" "2" "3" "4" "5" "6" "7")) : "5040"
+<dead compose> (("1" "2" "3" "4" "5" "6" "7" "8")) : "40320"
+<dead compose> (("1" "2" "3" "4" "5" "6" "7" "8" "9")) : "362880"
+@end example
+
@node Keyboard Layout Identification
diff --git a/src/mds-kbdc/simplify-tree.c b/src/mds-kbdc/simplify-tree.c
index 3cd97b8..851c219 100644
--- a/src/mds-kbdc/simplify-tree.c
+++ b/src/mds-kbdc/simplify-tree.c
@@ -16,18 +16,26 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include "simplify-tree.h"
+#include "globals.h"
#include <stdlib.h>
#include <string.h>
#include <alloca.h>
+
/**
* This processes value for `mds_kbdc_tree_t.processed`
*/
#define PROCESS_LEVEL 2
+/**
+ * Tree type constant shortener
+ */
+#define C(TYPE) MDS_KBDC_TREE_TYPE_##TYPE
+
+
/**
* Add an error the to error list
*
@@ -100,10 +108,10 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
/* Remove ‘.’:s. */
processed = tree->processed, tree->processed = PROCESS_LEVEL;
for (here = &(tree->arguments); *here;)
- if ((*here)->type != MDS_KBDC_TREE_TYPE_NOTHING)
+ if ((*here)->type != C(NOTHING))
here = &((*here)->next);
else
- while (*here && (*here)->type == MDS_KBDC_TREE_TYPE_NOTHING)
+ while (*here && (*here)->type == C(NOTHING))
{
argument = (*here)->next, (*here)->next = NULL;
if ((processed != PROCESS_LEVEL) && ((*here)->processed != PROCESS_LEVEL))
@@ -121,7 +129,7 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
/* Eliminate alterations. */
for (argument = dup_argument; argument; argument = argument->next, argument_index++)
{
- if (argument->type != MDS_KBDC_TREE_TYPE_ALTERNATION)
+ if (argument->type != C(ALTERNATION))
continue;
/* Detach next statement, we do not want to duplicate all following statements. */
@@ -264,7 +272,7 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
if (tree->inner == NULL)
{
NEW_ERROR(tree, ERROR, "empty alternation");
- tree->type = MDS_KBDC_TREE_TYPE_NOTHING;
+ tree->type = C(NOTHING);
tree->processed = PROCESS_LEVEL;
return 0;
}
@@ -281,7 +289,7 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
/* Simplify. */
for (here = &(tree->inner); (argument = *here); redo ? (redo = 0) : (here = &(argument->next), 0))
- if ((argument->type == MDS_KBDC_TREE_TYPE_NOTHING) && (argument->processed != PROCESS_LEVEL))
+ if ((argument->type == C(NOTHING)) && (argument->processed != PROCESS_LEVEL))
{
/* Test multiple nothings. */
if (first_nothing == NULL)
@@ -292,14 +300,14 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
NEW_ERROR(first_nothing, NOTE, "first ‘.’ was here");
}
}
- else if (argument->type == MDS_KBDC_TREE_TYPE_ALTERNATION)
+ else if (argument->type == C(ALTERNATION))
{
/* Alternation nesting. */
if (argument->processed != PROCESS_LEVEL)
NEW_ERROR(argument, WARNING, "alternation inside alternation is unnessary");
if (simplify_alternation(&(argument->alternation)))
return -1;
- if (argument->type == MDS_KBDC_TREE_TYPE_ALTERNATION)
+ if (argument->type == C(ALTERNATION))
{
/* Remember the alternation and the argument that follows it. */
eliminated_argument = argument;
@@ -319,14 +327,13 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
}
redo = 1;
}
- else if (argument->type == MDS_KBDC_TREE_TYPE_UNORDERED)
+ else if (argument->type == C(UNORDERED))
{
/* Nesting unordered subsequence,
simplifies to alternation of ordered subsequence, or simpler. */
- NEW_ERROR(argument, WARNING, "unorderd subsequence inside alternation is discouraged");
+ NEW_ERROR(argument, WARNING, "unordered subsequence inside alternation is discouraged");
if (simplify_unordered(&(argument->unordered)))
return -1;
- argument->processed = PROCESS_LEVEL;
redo = 1;
}
@@ -336,6 +343,73 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
}
+/**
+ * Create a chain of ordered subsequence covering all
+ * permutations of a set of subtrees
+ *
+ * @param elements The subtrees, chained
+ * @return Chain of ordered subsequence, `NULL` on error
+ */
+static mds_kbdc_tree_t* create_permutations(mds_kbdc_tree_t* elements)
+{
+ mds_kbdc_tree_t* first = NULL;
+ mds_kbdc_tree_t** here = &first;
+ mds_kbdc_tree_t** previous_next = &elements;
+ mds_kbdc_tree_t* argument;
+ mds_kbdc_tree_t* temp;
+ mds_kbdc_tree_t* subperms = NULL;
+ mds_kbdc_tree_t* perm;
+ mds_kbdc_tree_t ordered;
+ int saved_errno, no_perms;
+
+ for (previous_next = &elements; (argument = *previous_next); previous_next = &((*previous_next)->next))
+ {
+ /* Created ordered alternative for a permutation prototype. */
+ mds_kbdc_tree_initialise(&ordered, C(ORDERED));
+ /* Select the first element. */
+ temp = argument->next, argument->next = NULL;
+ ordered.ordered.inner = mds_kbdc_tree_dup(argument);
+ argument->next = temp;
+ fail_if (ordered.ordered.inner == NULL);
+ /* Create subpermutations. */
+ *previous_next = argument->next;
+ argument->next = NULL;
+ no_perms = (elements == NULL);
+ subperms = create_permutations(elements);
+ argument->next = *previous_next;
+ *previous_next = argument;
+ fail_if (no_perms ? 0 : subperms == NULL);
+ /* Join first element with subpermutations. */
+ while (subperms)
+ {
+ /* Join. */
+ fail_if ((perm = mds_kbdc_tree_dup(&ordered), perm == NULL));
+ perm->ordered.inner = subperms->ordered.inner;
+ /* Add the permutation to the chain. */
+ *here = perm;
+ here = &(perm->next);
+ /* Select next permutation. */
+ temp = subperms;
+ subperms = subperms->next;
+ temp->next = NULL;
+ mds_kbdc_tree_free(temp);
+ }
+ /* Destroy prototype. */
+ mds_kbdc_tree_destroy(&ordered);
+ }
+
+ return first;
+
+ pfail:
+ saved_errno = errno;
+ mds_kbdc_tree_free(first);
+ mds_kbdc_tree_free(subperms);
+ mds_kbdc_tree_destroy(&ordered);
+ errno = saved_errno;
+ return NULL;
+}
+
+
/**
* Simplify an unordered subsequence-subtree
*
@@ -344,15 +418,29 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
*/
static int simplify_unordered(mds_kbdc_tree_unordered_t* restrict tree)
{
+ mds_kbdc_tree_t* arguments;
mds_kbdc_tree_t* argument;
mds_kbdc_tree_t* temp;
mds_kbdc_tree_t** here;
+ int allow_long = 0;
+ size_t argument_count;
+ int argv_force = 0; /* TODO globals.h */
+
+ /* Test for ‘(( ))’. */
+ if (tree->inner && (tree->inner->next == NULL) && (tree->inner->type == C(UNORDERED)))
+ {
+ temp = tree->inner;
+ tree->inner = tree->inner->unordered.inner;
+ temp->unordered.inner = NULL;
+ mds_kbdc_tree_free(temp);
+ allow_long = 1;
+ }
/* Test emptyness. */
if (tree->inner == NULL)
{
NEW_ERROR(tree, ERROR, "empty unordered subsequence");
- tree->type = MDS_KBDC_TREE_TYPE_NOTHING;
+ tree->type = C(NOTHING);
tree->processed = PROCESS_LEVEL;
return 0;
}
@@ -369,10 +457,10 @@ static int simplify_unordered(mds_kbdc_tree_unordered_t* restrict tree)
/* Remove ‘.’:s. */
for (here = &(tree->inner); *here;)
- if ((*here)->type != MDS_KBDC_TREE_TYPE_NOTHING)
+ if ((*here)->type != C(NOTHING))
here = &((*here)->next);
else
- while (*here && (*here)->type == MDS_KBDC_TREE_TYPE_NOTHING)
+ while (*here && (*here)->type == C(NOTHING))
{
argument = (*here)->next, (*here)->next = NULL;
NEW_ERROR(*here, WARNING, "‘.’ inside unordered subsequences has no effect");
@@ -380,7 +468,40 @@ static int simplify_unordered(mds_kbdc_tree_unordered_t* restrict tree)
*here = argument;
}
- /* TODO alternation, unordered (warn: unreadable) */
+ /* Simplify. */
+ for (argument = tree->inner, argument_count = 0; argument; argument = argument->next, argument_count++)
+ if (argument->type == C(ALTERNATION))
+ {
+ if (simplify_alternation(&(argument->alternation)))
+ return -1;
+ argument->processed = PROCESS_LEVEL;
+ }
+ else if (argument->type == C(UNORDERED))
+ {
+ NEW_ERROR(argument, WARNING, "unordered subsequence inside unordered subsequence is discouraged");
+ if (simplify_unordered(&(argument->unordered)))
+ return -1;
+ argument->processed = PROCESS_LEVEL;
+ }
+
+ /* Check the size of the subsequence. */
+ if ((argument_count > 5) && (allow_long * argv_force == 0))
+ {
+ if (allow_long == 0)
+ NEW_ERROR(argument, ERROR, "unordered subsequence longer than 5 elements need double brackets");
+ else if (argv_force == 0)
+ NEW_ERROR(argument, ERROR, "unordered subsequence of size %zu found, requires ‘--force’ to compile",
+ argument_count);
+ return 0;
+ }
+
+ /* Generate permutations. */
+ tree->type = C(ALTERNATION);
+ tree->processed = PROCESS_LEVEL;
+ arguments = tree->inner;
+ if (tree->inner = create_permutations(arguments), tree->inner == NULL)
+ return tree->inner = arguments, -1;
+ mds_kbdc_tree_free(arguments);
return 0;
pfail:
@@ -405,16 +526,16 @@ static int simplify(mds_kbdc_tree_t* restrict tree)
switch (tree->type)
{
- case MDS_KBDC_TREE_TYPE_INFORMATION: s (information.inner); break;
- case MDS_KBDC_TREE_TYPE_FUNCTION: s (function.inner); break;
- case MDS_KBDC_TREE_TYPE_MACRO: s (macro.inner); break;
- case MDS_KBDC_TREE_TYPE_ASSUMPTION: s (assumption.inner); break;
- case MDS_KBDC_TREE_TYPE_FOR: s (for_.inner); break;
- case MDS_KBDC_TREE_TYPE_IF: s (if_.inner); s (if_.otherwise); break;
- case MDS_KBDC_TREE_TYPE_MAP: /* TODO */ break;
- case MDS_KBDC_TREE_TYPE_ALTERNATION: S (alternation); break;
- case MDS_KBDC_TREE_TYPE_UNORDERED: S (unordered); break;
- case MDS_KBDC_TREE_TYPE_MACRO_CALL: S (macro_call); break;
+ case C(INFORMATION): s (information.inner); break;
+ case C(FUNCTION): s (function.inner); break;
+ case C(MACRO): s (macro.inner); break;
+ case C(ASSUMPTION): s (assumption.inner); break;
+ case C(FOR): s (for_.inner); break;
+ case C(IF): s (if_.inner); s (if_.otherwise); break;
+ case C(MAP): /* TODO */ break;
+ case C(ALTERNATION): S (alternation); break;
+ case C(UNORDERED): S (unordered); break;
+ case C(MACRO_CALL): S (macro_call); break;
default:
break;
}
@@ -441,5 +562,6 @@ int simplify_tree(mds_kbdc_parsed_t* restrict result_)
#undef NEW_ERROR
+#undef C
#undef PROCESS_LEVEL
diff --git a/src/mds-kbdc/tree.c b/src/mds-kbdc/tree.c
index 1e7dc07..a107408 100644
--- a/src/mds-kbdc/tree.c
+++ b/src/mds-kbdc/tree.c
@@ -23,6 +23,9 @@
+/**
+ * Tree type constant shortener
+ */
#define C(t) MDS_KBDC_TREE_TYPE_##t
--
cgit v1.2.3-70-g09d2