aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/mds-kbdc/simplify-tree.c251
1 files changed, 192 insertions, 59 deletions
diff --git a/src/mds-kbdc/simplify-tree.c b/src/mds-kbdc/simplify-tree.c
index 851c219..c684285 100644
--- a/src/mds-kbdc/simplify-tree.c
+++ b/src/mds-kbdc/simplify-tree.c
@@ -51,6 +51,68 @@
/**
+ * Remove ‘.’:s
+ *
+ * @param START:identifier The member of `tree` that is cleaned from ‘.’:s
+ * @scope tree:mds_kbdc_tree_t* The tree from where the ‘.’:s are being removed
+ * @scope here:mds_kbdc_tree_t** Help variable that must be available for use
+ * @scope argument:mds_kbdc_tree_t* Help variable that must be available for use
+ */
+#define REMOVE_NOTHING(START) \
+ do \
+ { \
+ long processed = tree->processed; \
+ tree->processed = PROCESS_LEVEL; \
+ for (here = &(tree->START); *here;) \
+ if ((*here)->type != C(NOTHING)) \
+ here = &((*here)->next); \
+ else \
+ while (*here && (*here)->type == C(NOTHING)) \
+ { \
+ argument = (*here)->next, (*here)->next = NULL; \
+ if ((processed != PROCESS_LEVEL) && ((*here)->processed != PROCESS_LEVEL)) \
+ NEW_ERROR(*here, WARNING, "‘.’ outside alternation has no effect"); \
+ mds_kbdc_tree_free(*here); \
+ *here = argument; \
+ } \
+ } \
+ while (0)
+
+
+
+/**
+ * Flatten an alternation of orderered subsequence, that is,
+ * insert its interior in place of it and move its next
+ * sibling to the next of the interior
+ *
+ * @param argument:mds_kbdc_tree_t* The argument to flatten
+ * @scope here:mds_kbdc_tree_t** Pointer to the space where the argument was found
+ * @scope temp:mds_kbdc_tree_t* Help variable that must be available for use
+ */
+#define FLATTEN(argument) \
+ do \
+ { \
+ /* Remember the alternation/subsequence and the argument that follows it. */ \
+ mds_kbdc_tree_t* eliminated_argument = argument; \
+ temp = argument->next; \
+ /* Find the last alternative/element. */ \
+ for (argument->next = argument->ordered.inner; argument->next;) \
+ argument = argument->next; \
+ /* Attach the argument that was after the alternation/subsequence to the */ \
+ /* end of the alternation/subsequence, that is, flatten the right side. */ \
+ argument->next = temp; \
+ /* Flatten the left side. */ \
+ *here = eliminated_argument->next; \
+ /* Free the memory of the alternation/subsequence. */ \
+ eliminated_argument->ordered.inner = NULL; \
+ eliminated_argument->next = NULL; \
+ mds_kbdc_tree_free(eliminated_argument); \
+ } \
+ while (0)
+
+
+
+/**
* Variable whether the latest created error is stored
*/
static mds_kbdc_parse_error_t* error;
@@ -96,38 +158,24 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
mds_kbdc_tree_t* last;
mds_kbdc_tree_t* new_tree;
mds_kbdc_tree_t* new_argument;
- mds_kbdc_tree_t* dup_argument;
+ mds_kbdc_tree_t* dup_arguments;
mds_kbdc_tree_t** here;
size_t i, argument_index = 0;
- long processed;
/* Simplify arguments. */
for (argument = tree->arguments; argument; argument = argument->next)
- simplify(argument);
+ fail_if (simplify(argument));
/* Remove ‘.’:s. */
- processed = tree->processed, tree->processed = PROCESS_LEVEL;
- for (here = &(tree->arguments); *here;)
- if ((*here)->type != C(NOTHING))
- here = &((*here)->next);
- else
- while (*here && (*here)->type == C(NOTHING))
- {
- argument = (*here)->next, (*here)->next = NULL;
- if ((processed != PROCESS_LEVEL) && ((*here)->processed != PROCESS_LEVEL))
- NEW_ERROR(*here, WARNING, "‘.’ outside alternation has no effect");
- mds_kbdc_tree_free(*here);
- *here = argument;
- }
+ REMOVE_NOTHING(arguments);
/* Copy arguments. */
if (tree->arguments == NULL)
return 0;
- if (dup_argument = mds_kbdc_tree_dup(tree->arguments), dup_argument == NULL)
- return -1;
+ fail_if ((dup_arguments = mds_kbdc_tree_dup(tree->arguments), dup_arguments == NULL));
/* Eliminate alterations. */
- for (argument = dup_argument; argument; argument = argument->next, argument_index++)
+ for (argument = dup_arguments; argument; argument = argument->next, argument_index++)
{
if (argument->type != C(ALTERNATION))
continue;
@@ -146,7 +194,7 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
int saved_errno = errno;
argument->alternation.inner = alternative;
tree->next = next_statement;
- mds_kbdc_tree_free(dup_argument);
+ mds_kbdc_tree_free(dup_arguments);
return errno = saved_errno, -1;
}
/* Join trees. */
@@ -175,7 +223,7 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
last->next = next_statement;
}
- mds_kbdc_tree_free(dup_argument);
+ mds_kbdc_tree_free(dup_arguments);
/* Example of what will happend:
*
@@ -254,6 +302,120 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
/**
+ * Simplify a mapping-subtree
+ *
+ * @param tree The mapping-subtree
+ * @return Zero on success, -1 on error
+ */
+static int simplify_map(mds_kbdc_tree_map_t* restrict tree)
+{
+ mds_kbdc_tree_t* argument;
+ mds_kbdc_tree_t** here;
+ mds_kbdc_tree_t* dup_sequence;
+ mds_kbdc_tree_t* temp;
+ int redo = 0;
+
+ /* Check for bad things in the result. */
+ for (argument = tree->result; argument; argument = argument->next)
+ if ((argument->type != C(KEYS)) && (argument->type != C(STRING)))
+ NEW_ERROR(argument, ERROR, "not allowed in mapping output");
+
+ /* Simplify sequence. */
+ for (argument = tree->sequence; argument; argument = argument->next)
+ fail_if (simplify(argument));
+
+ /* Remove ‘.’:s. */
+ REMOVE_NOTHING(sequence);
+
+ /* Copy sequence. */
+ if (tree->sequence == NULL)
+ return 0;
+ 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. */
+ /* TODO */
+
+ mds_kbdc_tree_free(dup_sequence);
+
+ /* 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;
+ }
+
+ /* Mapping statements are simplified in a manner similar
+ * to how macro calls are simplified. However mapping
+ * statements can also contain unordered subsequences,
+ * there are translated into alternations of ordered
+ * subsequences. Thus after the elimination of alternations,
+ * ordered subsequences are eliminated too.
+ *
+ * Example of what will happen, ‘{ }’ presents an
+ * ordered subsequence:
+ *
+ * (1 2) (3 4) : 0 ## mapping 1
+ *
+ * simplify_map on mapping 1
+ * after simplification
+ * [{1 2} {2 1}] [{3 4} {4 3}] ## mapping 1
+ * after alternation elimination on argument 1
+ * {1 2} [{3 4} {4 3}] ## mapping 1
+ * {2 1} [{3 4} {4 3}] ## mapping 3
+ * after alternation elimination on argument 2
+ * {1 2} {3 4} ## mapping 1
+ * {1 2} {4 3} ## mapping 2
+ * {2 1} [{3 4} {4 3}] ## mapping 3
+ * after ordered subsequence elimination
+ * 1 2 3 4 ## mapping 1
+ * {1 2} {4 3} ## mapping 2
+ * {2 1} [{3 4} {4 3}] ## mapping 3
+ *
+ * simplify_map on mapping 2
+ * no difference after simplification
+ * no difference after alternation elimination on argument 1
+ * no difference after alternation elimination on argument 2
+ * after ordered subsequence elimination
+ * 1 2 3 4 ## (mapping 1)
+ * 1 2 4 3 ## mapping 2
+ * {2 1} [{3 4} {4 3}] ## mapping 3
+ *
+ * simplify_map on mapping 3
+ * no difference after simplification
+ * no difference after alternation elimination on argument 1
+ * after alternation elimination on argument 2
+ * 1 2 3 4 ## (mapping 1)
+ * 1 2 4 3 ## (mapping 2)
+ * {2 1} {3 4} ## mapping 3
+ * {2 1} {4 3} ## mapping 4
+ * after ordered subsequence elimination
+ * 1 2 3 4 ## (mapping 1)
+ * 1 2 4 3 ## (mapping 2)
+ * 2 1 3 4 ## mapping 3
+ * {2 1} {4 3} ## mapping 4
+ *
+ * simplify_map on mapping 4
+ * no difference after simplification
+ * no difference after alternation elimination on argument 1
+ * no difference after alternation elimination on argument 2
+ * after ordered subsequence elimination
+ * 1 2 3 4 ## (mapping 1)
+ * 1 2 4 3 ## (mapping 2)
+ * 2 1 3 4 ## (mapping 3)
+ * 2 1 4 3 ## mapping 4
+ *
+ * Nothings (‘.’) are removed before processing the alternations.
+ */
+
+ return 0;
+ pfail:
+ return -1;
+}
+
+
+/**
* Simplify an alternation-subtree
*
* @param tree The alternation-subtree
@@ -262,7 +424,6 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
{
mds_kbdc_tree_t* argument;
- mds_kbdc_tree_t* eliminated_argument;
mds_kbdc_tree_t* first_nothing = NULL;
mds_kbdc_tree_t* temp;
mds_kbdc_tree_t** here;
@@ -305,26 +466,9 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
/* Alternation nesting. */
if (argument->processed != PROCESS_LEVEL)
NEW_ERROR(argument, WARNING, "alternation inside alternation is unnessary");
- if (simplify_alternation(&(argument->alternation)))
- return -1;
+ fail_if (simplify_alternation(&(argument->alternation)));
if (argument->type == C(ALTERNATION))
- {
- /* Remember the alternation and the argument that follows it. */
- eliminated_argument = argument;
- temp = argument->next;
- /* Find the last alternative. */
- for (argument->next = argument->alternation.inner; argument->next;)
- argument = argument->next;
- /* Attach the argument that was after the alternation to the end of the alternation,
- that is, flatten the right side. */
- argument->next = temp;
- /* Flatten the left side. */
- *here = eliminated_argument->next;
- /* Free the memory of the alternation. */
- eliminated_argument->alternation.inner = NULL;
- eliminated_argument->next = NULL;
- mds_kbdc_tree_free(eliminated_argument);
- }
+ FLATTEN(argument);
redo = 1;
}
else if (argument->type == C(UNORDERED))
@@ -332,8 +476,7 @@ static int simplify_alternation(mds_kbdc_tree_alternation_t* restrict tree)
/* Nesting unordered subsequence,
simplifies to alternation of ordered subsequence, or simpler. */
NEW_ERROR(argument, WARNING, "unordered subsequence inside alternation is discouraged");
- if (simplify_unordered(&(argument->unordered)))
- return -1;
+ fail_if (simplify_unordered(&(argument->unordered)));
redo = 1;
}
@@ -456,31 +599,19 @@ static int simplify_unordered(mds_kbdc_tree_unordered_t* restrict tree)
}
/* Remove ‘.’:s. */
- for (here = &(tree->inner); *here;)
- if ((*here)->type != C(NOTHING))
- here = &((*here)->next);
- else
- while (*here && (*here)->type == C(NOTHING))
- {
- argument = (*here)->next, (*here)->next = NULL;
- NEW_ERROR(*here, WARNING, "‘.’ inside unordered subsequences has no effect");
- mds_kbdc_tree_free(*here);
- *here = argument;
- }
+ REMOVE_NOTHING(inner);
/* 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;
+ fail_if (simplify_alternation(&(argument->alternation)));
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;
+ fail_if (simplify_unordered(&(argument->unordered)));
argument->processed = PROCESS_LEVEL;
}
@@ -532,7 +663,7 @@ static int simplify(mds_kbdc_tree_t* restrict tree)
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(MAP): S (map); break;
case C(ALTERNATION): S (alternation); break;
case C(UNORDERED): S (unordered); break;
case C(MACRO_CALL): S (macro_call); break;
@@ -561,6 +692,8 @@ int simplify_tree(mds_kbdc_parsed_t* restrict result_)
+#undef FLATTEN
+#undef REMOVE_NOTHING
#undef NEW_ERROR
#undef C
#undef PROCESS_LEVEL
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-20 13:22:11 +0000