+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.
* - 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.
{
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;
}
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;
}
{
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
* 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.
* \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
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);
#include "state.h"
#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
*/
typedef struct InadequacyList {
struct InadequacyList *next;
+ InadequacyListNodeCount id;
state *manifestingState;
ContributionIndex contributionCount;
union {
* - \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:
* <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
(*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)
{
projects / bison.git / commitdiff
