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.
(cherry picked from commit 2728ac7ecd663c4a60f94fe7ab7679a9e83ebcd0)

diff --git a/ChangeLog b/ChangeLog
index 5b3011e561773c09173a508c3cf963d2138996f6..1fa4f8f41c45f77b029029fdac52d9086e60bd15 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -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.
 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 a603102af9d9c4c6b34fa21409262ec9db555bfe..d756f5d2e42cd7f2d57acc4947b9ad6a7aa1ad1a 100644 (file)
--- 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:
  *   - 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.
  *     - 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;
     {
       int cmp = 0;
       ContributionIndex ci;

-      if (self->inadequacyNode < (*node)->inadequacyNode)
+      if (self->inadequacyNode->id < (*node)->inadequacyNode->id)

         cmp = 1;
         cmp = 1;

-      else if ((*node)->inadequacyNode < self->inadequacyNode)
+      else if ((*node)->inadequacyNode->id < self->inadequacyNode->id)

         cmp = -1;
       else
         for (ci = 0;
         cmp = -1;
       else
         for (ci = 0;


@@ -408,18 +407,14 @@ AnnotationList__computePredecessorAnnotations (AnnotationList *self, state *s,
 }
 
 void
 }
 
 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;
 {
   bitsetv all_lookaheads;
   bitset shift_tokens;


@@ -530,8 +525,9 @@ AnnotationList__compute_from_inadequacies (state *s,
             }
           {
             InadequacyList *conflict_node =
             }
           {
             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
             actions = NULL;
             annotation_node->inadequacyNode = conflict_node;
             if (ContributionIndex__none

diff --git a/src/AnnotationList.h b/src/AnnotationList.h
index 02d4a2be760cada038741a3cd422ed7452f3b173..a9876e168a5d82afbb50be76d15f3f3cda58277b 100644 (file)
--- 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.
  *     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.
  * \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
  *     \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
 
 /**
  * \pre

diff --git a/src/InadequacyList.c b/src/InadequacyList.c
index edf3a0f585b11158c6ba2319a70ccbf3aebd4941..a79233e4e705801d3a5d2dd6907f1e48511ddb9b 100644 (file)
--- 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,
 
 InadequacyList *
 InadequacyList__new_conflict (state *manifesting_state, symbol *token,

-                              bitset actions)
+                              bitset actions,
+                              InadequacyListNodeCount *node_count)

 {
   InadequacyList *result = xmalloc (sizeof *result);
 {
   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);
   result->next = NULL;
   result->manifestingState = manifesting_state;
   result->contributionCount = bitset_count (actions);

diff --git a/src/InadequacyList.h b/src/InadequacyList.h
index 5770f994e220d88d276eb887e6a205513d9ceb8f..9ec8a29b725e2e484894203b378bac715c66d64f 100644 (file)
--- a/src/InadequacyList.h
+++ b/src/InadequacyList.h
@@ -25,6 +25,14 @@
 #include "state.h"
 #include "symtab.h"
 
 #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
 /**
  * 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


@@ -66,6 +74,7 @@ typedef struct {
  */
 typedef struct InadequacyList {
   struct InadequacyList *next;
  */
 typedef struct InadequacyList {
   struct InadequacyList *next;

+  InadequacyListNodeCount id;

   state *manifestingState;
   ContributionIndex contributionCount;
   union {
   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>.
  *   - \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:
  * \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.
  *       <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.
  */
  *   - \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
 
 /**
  * \post

diff --git a/src/ielr.c b/src/ielr.c
index e47c02026747de43ed751c766c6d1f318b1b718b..c5aed0c665c9a4b4da6bb30e1d68f932f1e7f6c8 100644 (file)
--- 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;
     }
       (*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)
     {
   *max_annotationsp = 0;
   for (i = 0; i < nstates; ++i)
     {