From 420d05a15b90658680b87b4d83b092768590319a Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Mon, 17 May 2010 10:15:23 -0700 Subject: [PATCH] Add test and fix bug leading to infinite recursion. The test case here is simply "#define foo foo" and "#define bar foo" and then attempting to expand "bar". Previously, our termination condition for the recursion was overly simple---just looking for the single identifier that began the expansion. We now fix this to maintain a stack of identifiers and terminate when any one of them occurs in the replacement list. --- glcpp-parse.y | 87 ++++++++++++++++++---- tests/024-define-chain-to-self-recursion.c | 3 + 2 files changed, 75 insertions(+), 15 deletions(-) create mode 100644 tests/024-define-chain-to-self-recursion.c diff --git a/glcpp-parse.y b/glcpp-parse.y index 71ea3e53439..16d2a28a007 100644 --- a/glcpp-parse.y +++ b/glcpp-parse.y @@ -76,6 +76,12 @@ _string_list_append_item (string_list_t *list, const char *str); void _string_list_append_list (string_list_t *list, string_list_t *tail); +void +_string_list_push (string_list_t *list, const char *str); + +void +_string_list_pop (string_list_t *list); + int _string_list_contains (string_list_t *list, const char *member, int *index); @@ -319,6 +325,45 @@ _string_list_append_item (string_list_t *list, const char *str) list->tail = node; } +void +_string_list_push (string_list_t *list, const char *str) +{ + string_node_t *node; + + node = xtalloc (list, string_node_t); + node->str = xtalloc_strdup (node, str); + + node->next = list->head; + + if (list->tail == NULL) { + list->tail = node; + } + + list->head = node; +} + +void +_string_list_pop (string_list_t *list) +{ + string_node_t *node; + + node = list->head; + + if (node == NULL) { + fprintf (stderr, "Internal error: _string_list_pop called on an empty list.\n"); + exit (1); + } + + list->head = node->next; + + if (list->tail == node) { + assert (node->next == NULL); + list->tail = NULL; + } + + talloc_free (node); +} + int _string_list_contains (string_list_t *list, const char *member, int *index) { @@ -330,7 +375,8 @@ _string_list_contains (string_list_t *list, const char *member, int *index) for (i = 0, node = list->head; node; i++, node = node->next) { if (strcmp (node->str, member) == 0) { - *index = i; + if (index) + *index = i; return 1; } } @@ -525,14 +571,14 @@ _define_function_macro (glcpp_parser_t *parser, static string_list_t * _expand_macro_recursive (glcpp_parser_t *parser, const char *token, - const char *orig, + string_list_t *active, string_list_t *parameters, argument_list_t *arguments); static string_list_t * _expand_string_list_recursive (glcpp_parser_t *parser, string_list_t *list, - const char *orig, + string_list_t *active, string_list_t *parameters, argument_list_t *arguments) { @@ -547,7 +593,10 @@ _expand_string_list_recursive (glcpp_parser_t *parser, for (node = list->head ; node ; node = node->next) { token = node->str; - if (strcmp (token, orig) == 0) { + /* Don't expand this macro if it's on the active + * stack, (meaning we're already in the process of + * expanding it). */ + if (_string_list_contains (active, token, NULL)) { _string_list_append_item (result, token); continue; } @@ -557,11 +606,11 @@ _expand_string_list_recursive (glcpp_parser_t *parser, argument = _argument_list_member_at (arguments, index); child = _expand_string_list_recursive (parser, argument, - orig, NULL, NULL); + active, NULL, NULL); _string_list_append_list (result, child); } else { child = _expand_macro_recursive (parser, token, - orig, parameters, + active, parameters, arguments); _string_list_append_list (result, child); } @@ -574,12 +623,18 @@ _expand_string_list_recursive (glcpp_parser_t *parser, static string_list_t * _expand_macro_recursive (glcpp_parser_t *parser, const char *token, - const char *orig, + string_list_t *active, string_list_t *parameters, argument_list_t *arguments) { macro_t *macro; string_list_t *replacements; + string_list_t *result; + + if (active == NULL) + active = _string_list_create (NULL); + + _string_list_push (active, token); macro = hash_table_find (parser->defines, token); if (macro == NULL) { @@ -592,8 +647,14 @@ _expand_macro_recursive (glcpp_parser_t *parser, replacements = macro->replacements; - return _expand_string_list_recursive (parser, replacements, - orig, parameters, arguments); + result = _expand_string_list_recursive (parser, replacements, + active, parameters, arguments); + + _string_list_pop (active); + if (_string_list_length (active) == 0) + talloc_free (active); + + return result; } string_list_t * @@ -604,7 +665,7 @@ _expand_object_macro (glcpp_parser_t *parser, const char *identifier) macro = hash_table_find (parser->defines, identifier); assert (! macro->is_function); - return _expand_macro_recursive (parser, identifier, identifier, + return _expand_macro_recursive (parser, identifier, NULL, NULL, NULL); } @@ -613,12 +674,8 @@ _expand_function_macro (glcpp_parser_t *parser, const char *identifier, argument_list_t *arguments) { - string_list_t *result; - macro_t *macro; - result = _string_list_create (parser); - macro = hash_table_find (parser->defines, identifier); assert (macro->is_function); @@ -633,6 +690,6 @@ _expand_function_macro (glcpp_parser_t *parser, return NULL; } - return _expand_macro_recursive (parser, identifier, identifier, + return _expand_macro_recursive (parser, identifier, NULL, macro->parameters, arguments); } diff --git a/tests/024-define-chain-to-self-recursion.c b/tests/024-define-chain-to-self-recursion.c new file mode 100644 index 00000000000..e788adce30c --- /dev/null +++ b/tests/024-define-chain-to-self-recursion.c @@ -0,0 +1,3 @@ +#define foo foo +#define bar foo +bar -- 2.30.2