diff options
| -rw-r--r-- | ChangeLog | 25 | ||||
| -rw-r--r-- | src/AnnotationList.c | 40 | ||||
| -rw-r--r-- | src/AnnotationList.h | 29 | ||||
| -rw-r--r-- | src/InadequacyList.c | 5 | ||||
| -rw-r--r-- | src/InadequacyList.h | 25 | ||||
| -rw-r--r-- | src/ielr.c | 18 |
6 files changed, 96 insertions, 46 deletions
@@ -1,3 +1,28 @@ +2009-12-29 Joel E. Denny <jdenny@clemson.edu> + + 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 <jdenny@clemson.edu> Fix handling of yychar manipulation in user semantic actions. diff --git a/src/AnnotationList.c b/src/AnnotationList.c index a603102a..d756f5d2 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 02d4a2be..a9876e16 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 + * <tt>*inadequacy_list_node_count</tt> is zero to avoid overflow. + * Otherwise, <tt>*inadequacy_list_node_count</tt> 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 * - <tt>inadequacy_lists[s->number]</tt> 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 edf3a0f5..a79233e4 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 5770f994..9ec8a29b 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 * <tt>manifesting_state->reductions->num + 1</tt>. + * - 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 <tt>*node_count</t> is zero so that the node count + * does not eventually overflow. However, if that set is not + * currently empty, then <tt>*node_count</tt> 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 { * <tt>0 <= i < manifesting_state->reductions->num</tt>, the reduction * for the rule <tt>manifesting_state->reductions->rules[i]</tt> iff * <tt>actions[i]</tt> 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 <tt>n != result</tt>, then <tt>n->id < result->id</tt>. * - \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 @@ -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) { |