From 2728ac7ecd663c4a60f94fe7ab7679a9e83ebcd0 Mon Sep 17 00:00:00 2001 From: "Joel E. Denny" Date: Tue, 29 Dec 2009 12:43:26 -0500 Subject: [PATCH] portability: `<' and `>' are not always defined on addresses. Specifically, don't sort objects by their memory addresses when they're not allocated in the same array or other object. Though I haven't found a test case where that fails on my platform, C says the behavior is undefined. * src/AnnotationList.c (AnnotationList__insertInto): Remove FIXME. Use new id field of InadequacyList nodes rather than their memory addresses when sorting. (AnnotationList__compute_from_inadequacies): Add inadequacy_list_node_count argument to pass to InadequacyList__new_conflict. * src/AnnotationList.h (AnnotationList__compute_from_inadequacies): Update prototype and documentation for new argument. * src/InadequacyList.c (InadequacyList__new_conflict): Add node_count argument and use it to assign a unique ID. * src/InadequacyList.h (InadequacyListNodeCount): New typedef. (InadequacyList): Add id field. (InadequacyList__new_conflict): Update prototype and documentation for new argument. * src/ielr.c (ielr_compute_annotation_lists): Update AnnotationList__compute_from_inadequacies invocation. --- ChangeLog | 25 +++++++++++++++++++++++++ src/AnnotationList.c | 40 ++++++++++++++++++---------------------- src/AnnotationList.h | 29 +++++++++++++++++------------ src/InadequacyList.c | 5 ++++- src/InadequacyList.h | 25 +++++++++++++++++++++++-- src/ielr.c | 18 +++++++++--------- 6 files changed, 96 insertions(+), 46 deletions(-) diff --git a/ChangeLog b/ChangeLog index ec11063..16d12a5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,28 @@ +2009-12-29 Joel E. Denny + + portability: `<' and `>' are not always defined on addresses. + Specifically, don't sort objects by their memory addresses when + they're not allocated in the same array or other object. Though + I haven't found a test case where that fails on my platform, C + says the behavior is undefined. + * src/AnnotationList.c (AnnotationList__insertInto): Remove + FIXME. Use new id field of InadequacyList nodes rather than + their memory addresses when sorting. + (AnnotationList__compute_from_inadequacies): Add + inadequacy_list_node_count argument to pass to + InadequacyList__new_conflict. + * src/AnnotationList.h + (AnnotationList__compute_from_inadequacies): Update prototype + and documentation for new argument. + * src/InadequacyList.c (InadequacyList__new_conflict): Add + node_count argument and use it to assign a unique ID. + * src/InadequacyList.h (InadequacyListNodeCount): New typedef. + (InadequacyList): Add id field. + (InadequacyList__new_conflict): Update prototype and + documentation for new argument. + * src/ielr.c (ielr_compute_annotation_lists): Update + AnnotationList__compute_from_inadequacies invocation. + 2009-12-20 Joel E. Denny Fix handling of yychar manipulation in user semantic actions. diff --git a/src/AnnotationList.c b/src/AnnotationList.c index a603102..d756f5d 100644 --- a/src/AnnotationList.c +++ b/src/AnnotationList.c @@ -77,12 +77,11 @@ AnnotationList__isContributionAlways (AnnotationList const *self, * - Otherwise, \c list now contains the node \c self, \c result is true, and * \c list assumes responsibility for the memory of \c self. * - The sort in \c list is: - * - Sort in reverse order on memory address of the associated inadequacy - * node. Because memory is usually allocated in ascending order (FIXME: - * Is this true enough? Should we keep some sort of global index to - * guarantee it?), this should mean that the insertion position within an - * annotation list is usually near the beginning with other annotations - * associated with the same inadequacy. + * - Sort in reverse order on the unique ID of the associated + * inadequacy node. Because these IDs are assigned in ascending + * order, this should mean that the insertion position within an + * annotation list is usually near the beginning with other + * annotations associated with the same inadequacy. * - Next, sort on the first contribution that is different as follows: * - Sort an always-contribution before a never-contribution before a * potential-contribution. @@ -104,9 +103,9 @@ AnnotationList__insertInto (AnnotationList *self, AnnotationList **list, { int cmp = 0; ContributionIndex ci; - if (self->inadequacyNode < (*node)->inadequacyNode) + if (self->inadequacyNode->id < (*node)->inadequacyNode->id) cmp = 1; - else if ((*node)->inadequacyNode < self->inadequacyNode) + else if ((*node)->inadequacyNode->id < self->inadequacyNode->id) cmp = -1; else for (ci = 0; @@ -408,18 +407,14 @@ AnnotationList__computePredecessorAnnotations (AnnotationList *self, state *s, } void -AnnotationList__compute_from_inadequacies (state *s, - bitsetv follow_kernel_items, - bitsetv always_follows, - state ***predecessors, - bitset **item_lookahead_sets, - InadequacyList **inadequacy_lists, - AnnotationList **annotation_lists, - AnnotationIndex *annotation_counts, - ContributionIndex - *max_contributionsp, - struct obstack - *annotations_obstackp) +AnnotationList__compute_from_inadequacies ( + state *s, bitsetv follow_kernel_items, bitsetv always_follows, + state ***predecessors, bitset **item_lookahead_sets, + InadequacyList **inadequacy_lists, AnnotationList **annotation_lists, + AnnotationIndex *annotation_counts, + ContributionIndex *max_contributionsp, + struct obstack *annotations_obstackp, + InadequacyListNodeCount *inadequacy_list_node_count) { bitsetv all_lookaheads; bitset shift_tokens; @@ -530,8 +525,9 @@ AnnotationList__compute_from_inadequacies (state *s, } { InadequacyList *conflict_node = - InadequacyList__new_conflict (s, symbols[conflicted_token], - actions); + InadequacyList__new_conflict ( + s, symbols[conflicted_token], actions, + inadequacy_list_node_count); actions = NULL; annotation_node->inadequacyNode = conflict_node; if (ContributionIndex__none diff --git a/src/AnnotationList.h b/src/AnnotationList.h index 02d4a2b..a9876e1 100644 --- a/src/AnnotationList.h +++ b/src/AnnotationList.h @@ -82,6 +82,15 @@ typedef struct AnnotationList * computed by \c ielr_compute_auxiliary_tables. * - The size of each of \c annotation_lists and \c annotation_counts is * \c ::nstates. + * - If no \c InadequacyList nodes are currently allocated for the + * parser tables to which \c s belongs, then it is best if + * *inadequacy_list_node_count is zero to avoid overflow. + * Otherwise, *inadequacy_list_node_count has not been + * modified by any function except + * \c AnnotationList__compute_from_inadequacies since the invocation + * of \c AnnotationList__compute_from_inadequacies that constructed + * the first of the \c InadequacyList nodes currently allocated for + * those parser tables. * \post * - inadequacy_lists[s->number] now describes all inadequacies that * manifest in \c s. @@ -97,18 +106,14 @@ typedef struct AnnotationList * \c annotations_obstackp. */ void -AnnotationList__compute_from_inadequacies (state *s, - bitsetv follow_kernel_items, - bitsetv always_follows, - state ***predecessors, - bitset **item_lookahead_sets, - InadequacyList **inadequacy_lists, - AnnotationList **annotation_lists, - AnnotationIndex *annotation_counts, - ContributionIndex - *max_contributionsp, - struct obstack - *annotations_obstackp); +AnnotationList__compute_from_inadequacies ( + state *s, bitsetv follow_kernel_items, bitsetv always_follows, + state ***predecessors, bitset **item_lookahead_sets, + InadequacyList **inadequacy_lists, AnnotationList **annotation_lists, + AnnotationIndex *annotation_counts, + ContributionIndex *max_contributionsp, + struct obstack *annotations_obstackp, + InadequacyListNodeCount *inadequacy_list_node_count); /** * \pre diff --git a/src/InadequacyList.c b/src/InadequacyList.c index edf3a0f..a79233e 100644 --- a/src/InadequacyList.c +++ b/src/InadequacyList.c @@ -27,9 +27,12 @@ ContributionIndex const ContributionIndex__error_action = -2; InadequacyList * InadequacyList__new_conflict (state *manifesting_state, symbol *token, - bitset actions) + bitset actions, + InadequacyListNodeCount *node_count) { InadequacyList *result = xmalloc (sizeof *result); + result->id = (*node_count)++; + aver (*node_count != 0); result->next = NULL; result->manifestingState = manifesting_state; result->contributionCount = bitset_count (actions); diff --git a/src/InadequacyList.h b/src/InadequacyList.h index 5770f99..9ec8a29 100644 --- a/src/InadequacyList.h +++ b/src/InadequacyList.h @@ -26,6 +26,14 @@ #include "symtab.h" /** + * A unique ID assigned to every \c InadequacyList node. + * + * This must remain unsigned so that the overflow check in + * \c InadequacyList__new_conflict works properly. + */ +typedef unsigned long long int InadequacyListNodeCount; + +/** * For a conflict, each rule in the grammar can have at most one contributing * reduction except that rule 0 cannot have any because the reduction on rule 0 * cannot have lookaheads. For a conflict, exactly one shift can contribute. @@ -66,6 +74,7 @@ typedef struct { */ typedef struct InadequacyList { struct InadequacyList *next; + InadequacyListNodeCount id; state *manifestingState; ContributionIndex contributionCount; union { @@ -79,6 +88,14 @@ typedef struct InadequacyList { * - \c token is a token. * - The size of \c actions is * manifesting_state->reductions->num + 1. + * - If the set of all \c InadequacyList nodes with which the new + * \c InadequacyList node might be compared is currently empty, then + * it is best if *node_count is zero so that the node count + * does not eventually overflow. However, if that set is not + * currently empty, then *node_count has not been modified + * by any function except \c InadequacyList__new_conflict since the + * invocation of \c InadequacyList__new_conflict that constructed + * the first existing member of that set. * \post * - \c result is a new \c InadequacyList with one node indicating that, in * \c manifesting_state, the following actions are in conflict on \c token: @@ -88,10 +105,14 @@ typedef struct InadequacyList { * 0 <= i < manifesting_state->reductions->num, the reduction * for the rule manifesting_state->reductions->rules[i] iff * actions[i] is set. + * - Given any node \c n from the set of all existing + * \c InadequacyList nodes with which \c result might be compared + * such that n != result, then n->id < result->id. * - \c result assumes responsibility for the memory of \c actions. */ -InadequacyList *InadequacyList__new_conflict (state *manifesting_state, - symbol *token, bitset actions); +InadequacyList *InadequacyList__new_conflict ( + state *manifesting_state, symbol *token, bitset actions, + InadequacyListNodeCount *node_count); /** * \post diff --git a/src/ielr.c b/src/ielr.c index e47c020..c5aed0c 100644 --- a/src/ielr.c +++ b/src/ielr.c @@ -504,15 +504,15 @@ ielr_compute_annotation_lists (bitsetv follow_kernel_items, (*annotation_listsp)[i] = NULL; annotation_counts[i] = 0; } - for (i = 0; i < nstates; ++i) - AnnotationList__compute_from_inadequacies (states[i], follow_kernel_items, - always_follows, predecessors, - item_lookahead_sets, - *inadequacy_listsp, - *annotation_listsp, - annotation_counts, - &max_contributions, - annotations_obstackp); + { + InadequacyListNodeCount inadequacy_list_node_count = 0; + for (i = 0; i < nstates; ++i) + AnnotationList__compute_from_inadequacies ( + states[i], follow_kernel_items, always_follows, predecessors, + item_lookahead_sets, *inadequacy_listsp, *annotation_listsp, + annotation_counts, &max_contributions, annotations_obstackp, + &inadequacy_list_node_count); + } *max_annotationsp = 0; for (i = 0; i < nstates; ++i) { -- 2.7.4