From 22b3aced03c1a243ba03fbcba5aa51f97e4f0abb Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Wed, 2 Jun 2010 15:32:03 -0700 Subject: [PATCH] Eliminate some recursion from children of _expand_token_list Previously, both _expand_node and _expand_function would always make mutually recursive calls into _expand_token_list. This was unnecessary since these functions can simply return unexpanded results, after which the outer iteration will next attempt expansion of the results. The only trick in doing this is to arrange so that the active list is popped at the appropriate time. To do this, we add a new token_node_t marker to the active stack. When pushing onto the active list, we set marker to last->next, and when the marker is seen by the token list iteration, we pop from the active stack. --- glcpp-parse.y | 159 ++++++++++++++++++++++++++++++++------------------ glcpp.h | 8 ++- 2 files changed, 110 insertions(+), 57 deletions(-) diff --git a/glcpp-parse.y b/glcpp-parse.y index a4e6559282c..1c7c84dac7a 100644 --- a/glcpp-parse.y +++ b/glcpp-parse.y @@ -52,12 +52,6 @@ _string_list_append_item (string_list_t *list, const char *str); static void _string_list_append_list (string_list_t *list, string_list_t *tail); -static void -_string_list_push (string_list_t *list, const char *str); - -static void -_string_list_pop (string_list_t *list); - static int _string_list_contains (string_list_t *list, const char *member, int *index); @@ -96,6 +90,20 @@ _token_list_append (token_list_t *list, token_t *token); static void _token_list_append_list (token_list_t *list, token_list_t *tail); +static int +_token_list_length (token_list_t *list); + +static active_list_t * +_active_list_push (active_list_t *list, + const char *identifier, + token_node_t *marker); + +static active_list_t * +_active_list_pop (active_list_t *list); + +int +_active_list_contains (active_list_t *list, const char *identifier); + static void _glcpp_parser_evaluate_defined (glcpp_parser_t *parser, token_list_t *list); @@ -468,42 +476,6 @@ _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) { @@ -716,6 +688,21 @@ _token_list_trim_trailing_space (token_list_t *list) } } +static int +_token_list_length (token_list_t *list) +{ + int length = 0; + token_node_t *node; + + if (list == NULL) + return 0; + + for (node = list->head; node; node = node->next) + length++; + + return length; +} + static void _token_print (token_t *token) { @@ -880,7 +867,7 @@ glcpp_parser_create (void) glcpp_lex_init_extra (parser, &parser->scanner); parser->defines = hash_table_ctor (32, hash_table_string_hash, hash_table_string_compare); - parser->active = _string_list_create (parser); + parser->active = NULL; parser->lexing_if = 0; parser->space_tokens = 1; parser->newline_as_space = 0; @@ -1176,10 +1163,6 @@ _glcpp_parser_expand_function (glcpp_parser_t *parser, substituted->non_space_tail = substituted->tail; - _string_list_push (parser->active, identifier); - _glcpp_parser_expand_token_list (parser, substituted); - _string_list_pop (parser->active); - return substituted; } @@ -1206,7 +1189,6 @@ _glcpp_parser_expand_node (glcpp_parser_t *parser, token_t *token = node->token; const char *identifier; macro_t *macro; - token_list_t *expansion; /* We only expand identifiers */ if (token->type != IDENTIFIER) { @@ -1231,7 +1213,7 @@ _glcpp_parser_expand_node (glcpp_parser_t *parser, /* Finally, don't expand this macro if we're already actively * expanding it, (to avoid infinite recursion). */ - if (_string_list_contains (parser->active, identifier, NULL)) { + if (_active_list_contains (parser->active, identifier)) { /* We change the token type here from IDENTIFIER to * OTHER to prevent any future expansion of this * unexpanded token. */ @@ -1254,18 +1236,63 @@ _glcpp_parser_expand_node (glcpp_parser_t *parser, if (macro->replacements == NULL) return _token_list_create (parser); - expansion = _token_list_copy (parser, macro->replacements); - - _string_list_push (parser->active, identifier); - _glcpp_parser_expand_token_list (parser, expansion); - _string_list_pop (parser->active); - - return expansion; + return _token_list_copy (parser, macro->replacements); } return _glcpp_parser_expand_function (parser, node, last); } +/* Push a new identifier onto the active list, returning the new list. + * + * Here, 'marker' is the token node that appears in the list after the + * expansion of 'identifier'. That is, when the list iterator begins + * examinging 'marker', then it is time to pop this node from the + * active stack. + */ +active_list_t * +_active_list_push (active_list_t *list, + const char *identifier, + token_node_t *marker) +{ + active_list_t *node; + + node = xtalloc (list, active_list_t); + node->identifier = xtalloc_strdup (node, identifier); + node->marker = marker; + node->next = list; + + return node; +} + +active_list_t * +_active_list_pop (active_list_t *list) +{ + active_list_t *node = list; + + if (node == NULL) + return NULL; + + node = list->next; + talloc_free (list); + + return node; +} + +int +_active_list_contains (active_list_t *list, const char *identifier) +{ + active_list_t *node; + + if (list == NULL) + return 0; + + for (node = list; node; node = node->next) + if (strcmp (node->identifier, identifier) == 0) + return 1; + + return 0; +} + /* Walk over the token list replacing nodes with their expansion. * Whenever nodes are expanded the walking will walk over the new * nodes, continuing to expand as necessary. The results are placed in @@ -1288,10 +1315,27 @@ _glcpp_parser_expand_token_list (glcpp_parser_t *parser, node = list->head; while (node) { + + while (parser->active && parser->active->marker == node) + parser->active = _active_list_pop (parser->active); + /* Find the expansion for node, which will replace all * nodes from node to last, inclusive. */ expansion = _glcpp_parser_expand_node (parser, node, &last); if (expansion) { + token_node_t *n; + + for (n = node; n != last->next; n = n->next) + while (parser->active && + parser->active->marker == n) + { + parser->active = _active_list_pop (parser->active); + } + + parser->active = _active_list_push (parser->active, + node->token->value.str, + last->next); + /* Splice expansion into list, supporting a * simple deletion if the expansion is * empty. */ @@ -1317,6 +1361,9 @@ _glcpp_parser_expand_token_list (glcpp_parser_t *parser, node = node_prev ? node_prev->next : list->head; } + while (parser->active) + parser->active = _active_list_pop (parser->active); + list->non_space_tail = list->tail; } diff --git a/glcpp.h b/glcpp.h index 41fc2043d13..4459daa4f32 100644 --- a/glcpp.h +++ b/glcpp.h @@ -123,10 +123,16 @@ typedef struct skip_node { struct skip_node *next; } skip_node_t; +typedef struct active_list { + const char *identifier; + token_node_t *marker; + struct active_list *next; +} active_list_t; + struct glcpp_parser { yyscan_t scanner; struct hash_table *defines; - string_list_t *active; + active_list_t *active; int lexing_if; int space_tokens; int newline_as_space; -- 2.30.2