From 5b769bbb457a0222b58b738a9b8be7a67e10dd34 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Fri, 28 Nov 2014 10:00:37 +0100 Subject: mds-kbdc: simplification of alternations MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/mds-kbdc/simplify-tree.c | 91 +++++++++++++++++++++- .../invalid/macro_call_with_empty_alternation | 8 ++ .../valid/macro_call_with_singleton_alternation | 10 +++ .../multiple_nothing_alternation_in_macro_call | 34 ++++++++ .../valid/nested_alternations_in_macro_call | 29 +++++++ 5 files changed, 169 insertions(+), 3 deletions(-) create mode 100644 test-files/mds-kbdc/simplify-tree/invalid/macro_call_with_empty_alternation create mode 100644 test-files/mds-kbdc/simplify-tree/valid/macro_call_with_singleton_alternation create mode 100644 test-files/mds-kbdc/simplify-tree/valid/multiple_nothing_alternation_in_macro_call create mode 100644 test-files/mds-kbdc/simplify-tree/valid/nested_alternations_in_macro_call diff --git a/src/mds-kbdc/simplify-tree.c b/src/mds-kbdc/simplify-tree.c index 1dd5a00..7ba6ee2 100644 --- a/src/mds-kbdc/simplify-tree.c +++ b/src/mds-kbdc/simplify-tree.c @@ -22,6 +22,11 @@ #include +/** + * This processes value for `mds_kbdc_tree_t.processed` + */ +#define PROCESS_LEVEL 2 + /** * Add an error the to error list @@ -84,7 +89,7 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree) simplify(argument); /* Remove ‘.’:s. */ - processed = tree->processed, tree->processed = 2; + processed = tree->processed, tree->processed = PROCESS_LEVEL; for (here = &(tree->arguments); *here;) if ((*here)->type != MDS_KBDC_TREE_TYPE_NOTHING) here = &((*here)->next); @@ -92,7 +97,7 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree) while (*here && (*here)->type == MDS_KBDC_TREE_TYPE_NOTHING) { argument = (*here)->next, (*here)->next = NULL; - if (processed != 2) + if ((processed != PROCESS_LEVEL) && ((*here)->processed != PROCESS_LEVEL)) NEW_ERROR(*here, WARNING, "‘.’ outside alternation has no effect"); mds_kbdc_tree_free(*here); *here = argument; @@ -224,6 +229,84 @@ static int simplify_macro_call(mds_kbdc_tree_macro_call_t* restrict tree) } +/** + * Simplify an alternation-subtree + * + * @param tree The alternation-subtree + * @return Zero on success, -1 on error + */ +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; + int redo = 0; + + /* Test emptyness. */ + if (tree->inner == NULL) + { + NEW_ERROR(tree, ERROR, "empty alternation"); + tree->type = MDS_KBDC_TREE_TYPE_NOTHING; + tree->processed = PROCESS_LEVEL; + return 0; + } + + /* Test singletonness. */ + if (tree->inner->next == NULL) + { + temp = tree->inner; + NEW_ERROR(tree, WARNING, "singleton alternation"); + memcpy(tree, temp, sizeof(mds_kbdc_tree_t)); + free(temp); + return simplify((mds_kbdc_tree_t*)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)) + { + /* Test multiple nothings. */ + if (first_nothing == NULL) + first_nothing = argument; + else + { + NEW_ERROR(argument, WARNING, "multiple ‘.’ inside an alternation"); + NEW_ERROR(first_nothing, NOTE, "first ‘.’ was here"); + } + } + else if (argument->type == MDS_KBDC_TREE_TYPE_ALTERNATION) + { + /* Alternation nesting. */ + temp = argument->next; + NEW_ERROR(argument, WARNING, "alternation inside alternation is unnecessary"); + if (simplify_alternation(&(argument->alternation))) + return -1; + *here = argument, redo = 1; + if (argument->type != MDS_KBDC_TREE_TYPE_ALTERNATION) + argument->next = temp; + else + { + eliminated_argument = argument; + for (argument->next = argument->alternation.inner; argument->next;) + argument = argument->next; + argument->next = temp; + eliminated_argument->alternation.inner = NULL; + *here = eliminated_argument->next; + eliminated_argument->next = NULL; + mds_kbdc_tree_free(eliminated_argument); + } + } + + /* TODO find unordered */ + + return 0; + pfail: + return -1; +} + + /** * Simplify a subtree * @@ -255,7 +338,8 @@ static int simplify(mds_kbdc_tree_t* restrict tree) break; case MDS_KBDC_TREE_TYPE_ALTERNATION: - /* TODO find alternation and unordered, find singletons, multiple nothings, error if empty */ + if ((r = simplify_alternation(&(tree->alternation)))) + return r; break; case MDS_KBDC_TREE_TYPE_UNORDERED: @@ -292,4 +376,5 @@ int simplify_tree(mds_kbdc_parsed_t* restrict result_) #undef NEW_ERROR +#undef PROCESS_LEVEL diff --git a/test-files/mds-kbdc/simplify-tree/invalid/macro_call_with_empty_alternation b/test-files/mds-kbdc/simplify-tree/invalid/macro_call_with_empty_alternation new file mode 100644 index 0000000..5532b22 --- /dev/null +++ b/test-files/mds-kbdc/simplify-tree/invalid/macro_call_with_empty_alternation @@ -0,0 +1,8 @@ +my_macro([]) + +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments nil) +# ) +# :1:9–10: error: empty alternation +# my_macro([]) + diff --git a/test-files/mds-kbdc/simplify-tree/valid/macro_call_with_singleton_alternation b/test-files/mds-kbdc/simplify-tree/valid/macro_call_with_singleton_alternation new file mode 100644 index 0000000..c005dea --- /dev/null +++ b/test-files/mds-kbdc/simplify-tree/valid/macro_call_with_singleton_alternation @@ -0,0 +1,10 @@ +my_macro([1]) + +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 10-11) ‘1’) +# ) +# ) +# :1:9–10: warning: singleton alternation +# my_macro([1]) + diff --git a/test-files/mds-kbdc/simplify-tree/valid/multiple_nothing_alternation_in_macro_call b/test-files/mds-kbdc/simplify-tree/valid/multiple_nothing_alternation_in_macro_call new file mode 100644 index 0000000..ef35cea --- /dev/null +++ b/test-files/mds-kbdc/simplify-tree/valid/multiple_nothing_alternation_in_macro_call @@ -0,0 +1,34 @@ +my_macro([1 . . . 2]) + +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 10-11) ‘1’) +# ) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments nil) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments nil) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments nil) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 18-19) ‘2’) +# ) +# ) +# :1:14–15: warning: multiple ‘.’ inside an alternation +# my_macro([1 . . . 2]) +# ^ +# :1:12–13: note: first ‘.’ was here +# my_macro([1 . . . 2]) +# ^ +# :1:16–17: warning: multiple ‘.’ inside an alternation +# my_macro([1 . . . 2]) +# ^ +# :1:12–13: note: first ‘.’ was here +# my_macro([1 . . . 2]) +# ^ + diff --git a/test-files/mds-kbdc/simplify-tree/valid/nested_alternations_in_macro_call b/test-files/mds-kbdc/simplify-tree/valid/nested_alternations_in_macro_call new file mode 100644 index 0000000..d40a68d --- /dev/null +++ b/test-files/mds-kbdc/simplify-tree/valid/nested_alternations_in_macro_call @@ -0,0 +1,29 @@ +my_macro([[1 2] [3 4]]) + +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 11-12) ‘1’) +# ) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 13-14) ‘2’) +# ) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 17-18) ‘3’) +# ) +# ) +# (macro_call (@ 1 0-8) ‘my_macro’ +# (.arguments +# (string (@ 1 19-20) ‘4’) +# ) +# ) +# :1:10–11: warning: alternation inside alternation is unnecessary +# my_macro([[1 2] [3 4]]) +# ^ +# :1:16–17: warning: alternation inside alternation is unnecessary +# my_macro([[1 2] [3 4]]) +# ^ + -- cgit v1.2.3-70-g09d2