Pccts/antlr/mrhoist.c

/*
 * mrhoist.c
 *
 * SOFTWARE RIGHTS
 *
 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
 * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
 * company may do whatever they wish with source code distributed with
 * PCCTS or the code generated by PCCTS, including the incorporation of
 * PCCTS, or its output, into commerical software.
 *
 * We encourage users to develop software with PCCTS.  However, we do ask
 * that credit is given to us for developing PCCTS.  By "credit",
 * we mean that if you incorporate our source code into one of your
 * programs (commercial product, research project, or otherwise) that you
 * acknowledge this fact somewhere in the documentation, research report,
 * etc...  If you like PCCTS and have developed a nice tool with the
 * output, please mention that you developed it using PCCTS.  In
 * addition, we ask that this header remain intact in our source code.
 * As long as these guidelines are kept, we expect to continue enhancing
 * this system and expect to make other tools available as they are
 * completed.
 *
 * ANTLR 1.33MR10
 *
 */

#include <stdio.h>

#include "pcctscfg.h"

#include "set.h"
#include "syn.h"
#include "hash.h"
#include "generic.h"
#include "dlgdef.h"
#include <ctype.h>

#ifdef __USE_PROTOS
void dumppred(Predicate *);
#else
void dumppred();
#endif

/*
  Try to determine whether predicate "first" is true for
    all cases where "second" is true.  Comparison takes place
    without regard to context.
  Assumes that predicate symbols have been expanded.
  Assumes that there are no NAND or NOR nodes

*/

#ifdef __USE_PROTOS
int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)
#else
int MR_secondPredicateUnreachable(first,second)
  Predicate     *first;
  Predicate     *second;
#endif
{
  Predicate     *f;
  Predicate     *s;

  if (first == NULL) {
    return 1;
  } else if (second == NULL) {
    return 0;
  } else if (first->down == NULL && second->down == NULL) {
    if (first->source == second->source &&
        first->inverted == second->inverted) {
      return 1; /* look identical - will never reach alt2 */
    } else {
      return 0; /* look different */
    };
  } else if (first->down == NULL && second->down != NULL) {

    if (second->expr == PRED_AND_LIST) {

      /* unreachable if first covers any child of second */

      for (s=second->down; s != NULL; s=s->right) {
        if (MR_secondPredicateUnreachable(first,s)) {
          return 1;
        };
      };
      return 0;
    } else if (second->expr == PRED_OR_LIST) {

      /* unreachable if first covers every child of second */

      for (s=second->down; s != NULL; s=s->right) {
        if (!MR_secondPredicateUnreachable(first,s)) {
          return 0;
        };
      };
      return 1;
    } else {
      require (0,"Illegal pred->expr");
      return 0; /* MR20 Make compiler happy */
    };
  } else if (first->down != NULL && second->down == NULL) {
    if (first->expr == PRED_AND_LIST) {

      /* unreachable if every child of first covers second */

      for (f=first->down; f != NULL; f=f->right) {
        if (!MR_secondPredicateUnreachable(f,second)) {
          return 0;
        };
      };
      return 1;
    } else if (first->expr == PRED_OR_LIST) {

      /* unreachable if any child of first covers second */

      for (f=first->down; f != NULL; f=f->right) {
        if (MR_secondPredicateUnreachable(f,second)) {
          return 1;
        };
      };
      return 0;
    } else {
      require (0,"Illegal predicate->expr");
      return 0; /* MR20 Make compiler happy */
    };
  } else {

    if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) {

      /* unreachable if each child of first covers at least one child of second */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;
        };
        return 0;
A_next_f:
        continue;
      };
      return 1;

    } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) {

      /* unreachable if each child of first covers ALL of second's children */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (!MR_secondPredicateUnreachable(f,s)) return 0;
        };
      };
      return 1;

    } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) {

      /* unreachable if any child of second is covered by any child of first */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (MR_secondPredicateUnreachable(f,s)) return 1;
        };
      };
      return 0;

    } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) {

      /* unreachable if every child of second is covered by some child of first */

      for (f=first->down; f != NULL ; f=f->right) {
        for (s=second->down; s != NULL ; s=s->right) {
          if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;
        };
        return 0;
B_next_f:
       continue;
      };
      return 1;

    } else {
      require (0,"Illegal predicate->expr");
      return 0; /* MR20 Make compiler happy */
    };
  };
  return 0; /* MR20 MSVC 5.0 complains about missing return statement */
}

#ifdef __USE_PROTOS
void MR_xxxIndent(FILE *f,int depth)
#else
void MR_xxxIndent(f,depth)
  FILE  *f;
  int   depth;
#endif
{
  int   i;

  for (i=0; i<depth ; i++) {
    fprintf(f,"  ");
  };
}

#ifdef __USE_PROTOS
void MR_stderrIndent(int depth)
#else
void MR_stderrIndent(depth)
  int   depth;
#endif
{
  MR_xxxIndent(stderr,depth);
}

#ifdef __USE_PROTOS
void MR_outputIndent(int depth)
#else
void MR_outputIndent(depth)
  int   depth;
#endif
{
  MR_xxxIndent(output,depth);
}

#ifdef __USE_PROTOS
void MR_set_reuse(set *s)
#else
void MR_set_reuse(s)
  set   *s;
#endif
{
  set_free(*s);
  *s=empty;
}

#ifdef __USE_PROTOS
void MR_dumpPredRuleRefStack(FILE *iounit,int indent)
#else
void MR_dumpPredRuleRefStack(iounit,indent)
  FILE  *iounit;
  int   indent;
#endif
{
    int             i;
    int             j;
    int             count=MR_PredRuleRefStack.count;
    RuleRefNode     *rrn=NULL;
    Junction        *lastOne;

    if (count == 0) {
      fprintf(iounit,"empty\n");
      return;
    };
    for (i=0; i < count; i++) {
      rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i];
      for (j=0; j<indent; j++) fprintf(iounit," ");
      fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n",
            i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text);
    };
    lastOne=MR_ruleReferenced(rrn);
    if (lastOne != NULL) {
      for (j=0; j<indent; j++) fprintf(iounit," ");
      fprintf(iounit,"#%-2d in rule %s (line %d %s)\n",
        count,lastOne->rname,lastOne->line,FileStr[lastOne->file]);
    };
}

#ifdef __USE_PROTOS
void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)
#else
void MR_dumpTreeF(f,depth,tree,across)
  FILE  *f;
  Tree  *tree;
  int   depth;
  int   across;
#endif
{
    int     newAcross=across;

	if (tree == NULL ) return;
	if (tree->down != NULL ) {
      fprintf(output,"\n");
      MR_outputIndent(depth);
      fprintf(output, "(root =");
    };
	if (tree->token == ALT ) {
      fprintf(output," %-16s","Alt");
	} else if (tree->token==EpToken ) {
      fprintf(output,"(%d)%13s",tree->v.rk," ");
	} else {
      fprintf(output," %-16s",TerminalString(tree->token));
    };
    if (tree->down != NULL) {
      fprintf(output,"\n");
      MR_outputIndent(depth+1);
      MR_dumpTreeF(f,depth+1,tree->down,1);
      newAcross=0;
      fprintf(output,"\n");
      MR_outputIndent(depth);
      fprintf(output,")");
    };
    if (newAcross > 3) {
      fprintf(output,"\n");
      MR_outputIndent(depth);
      newAcross=0;
    };
    MR_dumpTreeF(f,depth,tree->right,newAcross+1);
}

#ifdef __USE_PROTOS
void MR_dumpTreeX(int depth,Tree *tree,int across)
#else
void MR_dumpTreeX(depth,tree,across)
  Tree  *tree;
  int   depth;
  int   across;
#endif
{
  MR_dumpTreeF(output,depth,tree,across);
}

#ifdef __USE_PROTOS
void MR_dumpTokenSet(FILE *f,int depth,set s)
#else
void MR_dumpTokenSet(f,depth,s)
  FILE  *f;
  int   depth;
  set   s;
#endif
{
    int     i;
    int     j;

    unsigned  *pdq;

    if (set_nil(s)) {
      fprintf(f,"\n");
      MR_xxxIndent(f,depth+1);
      fprintf(f,"nil\n");
      return;
    };

    pdq=set_pdq(s);
    require(pdq != NULL,"set_pdq failed");
    i=0;
    for (i=0 ; ; i=i+4) {
      fprintf(f,"\n");
      MR_xxxIndent(f,depth+1);
      for (j=0; j < 4 ; j++) {
        if (pdq[i+j] == nil) break;
        fprintf(f," %-16s",TerminalString(pdq[i+j]));
      };
      if (pdq[i+j] == nil) break;
    };
    fprintf(f,"\n");
    free( (char *) pdq);
}

#ifdef __USE_PROTOS
void MR_dumpPred1(int depth,Predicate *p,int withContext)
#else
void MR_dumpPred1(depth,p,withContext)
  int           depth;
  Predicate     *p;
  int           withContext;
#endif
{
  unsigned      k;

  if (p == NULL) {
    MR_outputIndent(depth);
    fprintf(output,"The predicate is empty (or always true)\n\n");
    return;
  };
  if (p->down != NULL) {
    MR_outputIndent(depth);
    if (p->inverted) {

        /* MR14a Left out print expression in fprintf
                 Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)
        */

      if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr);
      if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr);
    } else {
      fprintf(output,"%s expr\n\n",p->expr);
    };
  } else {
    MR_outputIndent(depth);
    fprintf(output,"pred %s <<%s>>?\n",
            (p->inverted ? " *not*" : ""),
            (p->expr == NULL ? "null expr" : p->expr));
    MR_outputIndent(depth+1);
    fprintf(output,"              ");
    fprintf(output,"  depth=k=%d",p->k);
    if (p->source != NULL && p->source->guardpred) {
      fprintf(output,"  (\"=>\" guard)");
    }
    if (p->source != NULL && p->source->ampersandPred != NULL) {
      fprintf(output,"  (\"&&\" guard)");
    };
    k=set_int(p->completionSet);
    if (k != nil) {
      fprintf(output," Incomplete Set at k=%d !",k);
    };
    k=set_int(p->completionTree);
    if (k != nil) {
      fprintf(output," Incomplete Tree at k=%d !",k);
    };
    if (p->source != NULL) {
      fprintf(output,"  rule %s  line %d  %s",
                    p->source->rname,p->source->line,FileStr[p->source->file]);
    };
    fprintf(output,"\n");
    if (withContext &&
            (HoistPredicateContext ||
             ! set_nil(p->scontext[1]) ||
             p->tcontext != NULL)) {
      if (p->k == 1) {
        MR_outputIndent(depth+1);
        fprintf(output,"set context: ");
        MR_dumpTokenSet(output,depth+1,p->scontext[1]);
      }
      if (p->k != 1) {
        MR_outputIndent(depth+1);
        fprintf(output,"tree context:");
        if (p->tcontext == NULL) {
          fprintf(output," null");
        } else {
          MR_dumpTreeX(depth+2,p->tcontext,0);
        };
        fprintf(output,"\n");
      };
    };
    fprintf(output,"\n");
  };
  if (p->down != NULL) {
    MR_dumpPred1(depth+1,p->down,withContext);
  };
  if (p->right != NULL) {
    MR_dumpPred1(depth,p->right,withContext);
  };
}

#ifdef __USE_PROTOS
void MR_dumpPred(Predicate *p,int withContext)
#else
void MR_dumpPred(p,withContext)
  Predicate     *p;
  int           withContext;
#endif
{
  MR_dumpPred1(0,p,withContext);
}

#ifdef __USE_PROTOS
Tree * MR_make_tree_from_set(set s)
#else
Tree * MR_make_tree_from_set(s)
  set   s;
#endif
{
  Tree  *t=NULL;
  Tree  *node;
  Tree  **tp=&t;
  int   i;

  unsigned *pdq=set_pdq(s);

  if (pdq != NULL) {
    for (i=0 ; pdq[i] != nil ; i++) {
      node=tnode( (int) pdq[i]);
      *tp=node;
      tp=&(node->right);
    };
    *tp=NULL;
    free ( (char *) pdq);
  };
  return t;
}

#ifdef __USE_PROTOS
void MR_check_pred_too_long(Predicate *p,set completion)
#else
void MR_check_pred_too_long(p,completion)
  Predicate     *p;
  set           completion;
#endif
{
  if (p != NULL &&
      p->source != NULL &&
      ! p->source->predTooLong) {
    if ( !set_nil(completion)) {
      p->source->predTooLong=1;
warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",
                                FileStr[p->source->file],p->source->line);
    };
  };
}

#ifdef __USE_PROTOS
int MR_predicate_context_completed(Predicate *p)
#else
int MR_predicate_context_completed(p)
  Predicate     *p;
#endif
{
  if (p == NULL) return 1;
  if (p->expr != PRED_AND_LIST &&
      p->expr != PRED_OR_LIST) {
    if ( ! set_nil(p->completionSet)) return 0;
    if ( ! set_nil(p->completionTree)) return 0;
  };
  return MR_predicate_context_completed(p->down) &
         MR_predicate_context_completed(p->right);
}

#ifdef __USE_PROTOS
Node * MR_advance(Node *n)
#else
Node * MR_advance(n)
  Node  *n;
#endif
{
    if (n == NULL) return NULL;
    switch (n->ntype) {
      case nJunction:   return ((Junction *)n)->p1;
      case nToken:      return ((TokNode *)n)->next;
      case nRuleRef:    return ((RuleRefNode *)n)->next;
      case nAction:     return ((ActionNode *)n)->next;
      default:          return NULL;
    };
  return NULL; /* MSVC 5.0 complains about missing return statement */
}

#ifdef __USE_PROTOS
Junction * MR_find_endRule(Node *n)
#else
Junction * MR_find_endRule(n)
  Node  *n;
#endif
{
    Node    *next;
    if (n == NULL) return NULL;
    for (next=n; next != NULL; next=MR_advance(next)) {
      if (next->ntype == nJunction &&
            ( (Junction *) next)->jtype == EndRule) {
        break;
      };
    };
    return (Junction *)next;
}

/*
   Intersection:  a branch which is shorter is chosen
   over one which is longer: (A B C) intersect (A B) yields (A B).

   AND: a branch which is longer is chosen over the one
   which is shorter: (A B C) AND (A B) yields (A B C)

*/

#ifdef __USE_PROTOS
Tree *MR_computeTreeIntersection(Tree *l,Tree *r)
#else
Tree *MR_computeTreeIntersection(l,r)
    Tree    *l;
    Tree    *r;
#endif
{
    Tree    *result=NULL;
    Tree    **tail;
    Tree    *p;
    Tree    *q;
    Tree    *match;

    if (l == NULL || r == NULL) return NULL;
    for (p=l; p != NULL; p=p->right) {
      require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n");
      require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n");
    };
    for (q=r; q != NULL; q=q->right) {
      require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n");
      require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n");
    };

    result=tnode(ALT);
    tail=&(result->down);

    for (p=l; p != NULL ; p=p->right) {
      for (q=r; q != NULL ; q=q->right) {
        if (p->token == q->token) {
          match=tnode(p->token);
          match->down=MR_computeTreeIntersection(p->down,q->down);
          *tail=match;
          tail=&(match->right);
        };
      };
    };

    *tail=NULL;
    result=tshrink(result);
    result=tflatten( result );
    result=tleft_factor( result );
    return result;
}

/* the predicates which are ANDed together have a common
   context:  they must all have common roots.  Thus the
   AND operation is more like an OR operation because
   branches which are longer are grafted onto shorter
   branches of the AND tree.  For instance combining
   (A B C) with (A B C D) gives (A B C D).  There
   should never be a case of (A B C) and (A B D) because
   they have the same context.

   Actually, this may not be true once one throws in
   guard predicates which are defined by the user, not
   the context.
*/

/* requires input trees to be in "canonical" format */

#ifdef __USE_PROTOS
Tree *MR_computeTreeAND(Tree *l,Tree *r)
#else
Tree *MR_computeTreeAND(l,r)
    Tree    *l;
    Tree    *r;
#endif
{
    Tree    *result=NULL;
    Tree    **tail;
    Tree    *p;
    Tree    *q;
    Tree    *match;

    if (l == NULL) return tdup(r);
    if (r == NULL) return tdup(l);

    for (p=l; p != NULL; p=p->right) {
/**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/
      require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n");
    };
    for (q=r; q != NULL; q=q->right) {
/**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/
      require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n");
    };

    result=tnode(ALT);
    tail=&(result->down);

    for (p=l; p != NULL ; p=p->right) {
      for (q=r; q != NULL ; q=q->right) {
        if (p->token == q->token) {
          match=tnode(p->token);
          match->down=MR_computeTreeAND(p->down,q->down);
          *tail=match;
          tail=&(match->right);
        };
      };
    };

    *tail=NULL;
    result=tshrink(result);
    result=tflatten( result );
    result=tleft_factor( result );
    return result;
}

#ifdef __USE_PROTOS
void MR_union_plain_sets1(Predicate *p,set *theUnion)
#else
void MR_union_plain_sets1(p,theUnion)
  Predicate     *p;
  set           *theUnion;
#endif
{
  if (p == NULL) return;
  MR_union_plain_sets1(p->down,theUnion);
  MR_union_plain_sets1(p->right,theUnion);
  set_orin(theUnion,p->plainSet);
  return;
}

#ifdef __USE_PROTOS
set MR_union_plain_sets(Predicate *p)
#else
set MR_union_plain_sets(p)
  Predicate     *p;
#endif
{
  set   theUnion;

  theUnion=empty;

  MR_union_plain_sets1(p,&theUnion);
  return theUnion;
}

/* does NOT left factor: do not want to merge
     (A B) with (A) to get (A B)
   in fact the opposite: (A B) with (A) gives (A)
*/

#ifdef __USE_PROTOS
Tree *MR_compute_pred_tree_ctxXX(Predicate *p)
#else
Tree *MR_compute_pred_tree_ctxXX(p)
  Predicate     *p;
#endif
{
    Tree        *result=NULL;
    Predicate   *q;
    Tree        *t;

    if (p == NULL) return NULL;

/* this appears strange: why do we OR the context
   of and AND predicate ?  It is because of the way
   that predicates are evaluated: if the context is
   wrong then it's the same as if the predicate was
   true.  That means that even when one leg of an
   AND has unmatched context, if the other leg has
   matched context and is true then the predicate
   succeeds.  It's only when all the legs have unmatched
   context that this one can skip evaluation of the
   predicates.
*/
    if (p->expr == PRED_OR_LIST ||
        p->expr == PRED_AND_LIST) {
      for (q=p->down; q != NULL ; q=q->right) {
        t=MR_compute_pred_tree_ctxXX(q);
        result=tappend(result,t);
        t=NULL;
      };

      result=tshrink(result);
      result=tflatten( result );

/* does NOT left factor: do not want to merge
     (A B) with (A) to get (A B)
   in fact the opposite: (A B) with (A) gives (A)
*/

/**** result=tleft_factor( result ); ****/
      return result;
    };

#if 0
**    if (p->expr == PRED_AND_LIST) {
**
**      Predicate     *l;
**      Predicate     *r;
**      Tree          *l1;
**      Tree          *r1;
**      Tree          *prevl1;
**
**      l=p->down;
**      require (l->right != NULL,"MR_compute_pred_tree - AND has only one child");
**
**/* l1 and r1 should already be in "canonical" format */
**
**      l1=MR_compute_pred_tree(l);
**      for (r=l->right; r != NULL; r=r->right) {
**        r1=MR_compute_pred_tree(r);
**        prevl1=l1;
**        l1=MR_computeTreeAND(l1,r1);
**        Tfree(r1);
**        Tfree(prevl1);
**      };
**
**/* result from computeTreeAND should be in "canonical" format */
**
**      result=l1;
**
**/* result of MR_computeTreeAND should be in "canonical" format */
**
**      return result;
**    };
#endif

    if (p->k == 1) {
      result=MR_make_tree_from_set(p->scontext[1]);
    } else {
      result=tdup(p->tcontext);
      result=MR_remove_epsilon_from_tree(result);
      result=tshrink(result);
      result=tflatten(result);
      result=tleft_factor(result);
    };
    return result;
}

#ifdef __USE_PROTOS
void MR_pred_depth(Predicate *p,int *maxDepth)
#else
void MR_pred_depth(p,maxDepth)
  Predicate     *p;
  int           *maxDepth;
#endif
{
  if (p == NULL) return;
  if (p->expr != PRED_OR_LIST &&
      p->expr != PRED_AND_LIST) {
    if (p->k > *maxDepth) *maxDepth=p->k;
  };
  MR_pred_depth(p->down,maxDepth);
  MR_pred_depth(p->right,maxDepth);
}

/* this computes the OR of all the contexts */

#ifdef __USE_PROTOS
set MR_compute_pred_set(Predicate *p)
#else
set MR_compute_pred_set(p)
  Predicate     *p;
#endif
{
    set         result;
    Predicate   *q;

    result=empty;

    if (p == NULL) return empty;

    if (p->expr == PRED_OR_LIST ||
        p->expr == PRED_AND_LIST) {         /* yes, I do mean PRED_AND_LIST !   */
                                            /* remember: r1: (A)? => <<p>>? r2; */
                                            /*           r2: (B)? => <<q>>? r3; */
      set   t;

      t=empty;
      result=empty;

      for (q=p->down; q != NULL; q=q->right) {
        t=MR_compute_pred_set(q);
        set_orin(&result,t);
        set_free(t);
      };
      return result;
    } else if (p->k > 1) {
      return empty;
    } else {
      return set_dup(p->scontext[1]);
    };
}

#ifdef __USE_PROTOS
set MR_First(int ck,Junction *j,set *incomplete)
#else
set MR_First(ck,j,incomplete)
  int       ck;
  Junction  *j;
  set       *incomplete;
#endif
{
    Junction    *p;
    set         tokensUsed;

    tokensUsed=empty;

	require(j->ntype==nJunction, "MR_First: non junction passed");

	p = analysis_point((Junction *)j->p1);

	REACH(p,ck,incomplete,tokensUsed);

    return tokensUsed;
}

#ifdef __USE_PROTOS
void MR_cleanup_pred_trees(Predicate *p)
#else
void MR_cleanup_pred_trees(p)
  Predicate     *p;
#endif
{
  Tree      *t;

  if (p == NULL) return;
  if (p->expr != PRED_OR_LIST &&
      p->expr != PRED_AND_LIST) {
    t=p->tcontext;
    t=tshrink(t);
    t=tflatten(t);
    t=tleft_factor(t);
    p->tcontext=t;
  };
  MR_cleanup_pred_trees(p->down);
  MR_cleanup_pred_trees(p->right);
}

/* does NOT return canonical tree */

#ifdef __USE_PROTOS
Tree * MR_remove_epsilon_from_tree(Tree *t)
#else
Tree * MR_remove_epsilon_from_tree(t)
  Tree  *t;
#endif
{
  if (t == NULL) return NULL;

  /* I think ALT can be ignored as a special case */

  if (t->token != EpToken) {
    t->down=MR_remove_epsilon_from_tree(t->down);
    t->right=MR_remove_epsilon_from_tree(t->right);
    return t;
  } else {
    Tree    *u;
    u=MR_remove_epsilon_from_tree(t->right);
    t->right=NULL;
    Tfree(t);
    return u;
  };
}

#ifdef __USE_PROTOS
void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)
#else
void MR_complete_set(predDepth,tokensUsed,incomplete)
  int       predDepth;
  set       *tokensUsed;
  set       *incomplete;
#endif
{
    int             i;
    RuleRefNode     *ruleRef;
	set             rk2;
    set             b;
	int             k2;
    Junction        *save_MR_RuleBlkWithHalt;

    if (set_int(*incomplete) > (unsigned) predDepth) {
      return;
    };

    require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
                "RuleRefStack and RuleBlkWithHaltStack not same size");

    require(MR_RuleBlkWithHalt == NULL ||
         (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
                     "RuleBlkWithHalt has no halt set");

    save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;

    if (MR_RuleBlkWithHalt != NULL) {
      MR_RuleBlkWithHalt->end->halt=FALSE;
    };

    for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
      ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
      if (ruleRef == NULL) continue;

      MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
      if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;

      rk2=empty;
      b=empty;

      while ( !set_nil(*incomplete) ) {
		k2=set_int(*incomplete);
        if (k2 > predDepth) break;                    /* <=== another exit from loop */
		set_rm(k2,*incomplete);
        REACH(ruleRef->next,k2,&rk2,b);
		set_orin(tokensUsed,b);
		set_free(b);
      };

      if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;

	  set_orin(incomplete,rk2);                       /* remember what we couldn't do */
      set_free(rk2);
	  if (set_int(*incomplete) > (unsigned) predDepth) break;    /* <=== another exit from loop */
    };

    MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
    if (MR_RuleBlkWithHalt != NULL) {
      MR_RuleBlkWithHalt->end->halt=TRUE;
    };
}

#ifdef __USE_PROTOS
void MR_complete_tree(int predDepth,Tree **t,set *incomplete)
#else
void MR_complete_tree(predDepth,t,incomplete)
  int       predDepth;
  Tree      **t;
  set       *incomplete;
#endif
{
    int             i;
    RuleRefNode     *ruleRef;
	set             rk2;
    Tree            *u;
	unsigned        k2;
    Junction        *save_MR_RuleBlkWithHalt;
    int             saveConstrainSearch;

    if (set_int(*incomplete) > (unsigned) predDepth) {
      return;
    };

    require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
                "RuleRefStack and RuleBlkWithHaltStack not same size");

    require(MR_RuleBlkWithHalt == NULL ||
         (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
                     "RuleBlkWithHalt has no halt set");

    save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
    saveConstrainSearch=ConstrainSearch;
    ConstrainSearch=0;

    if (MR_RuleBlkWithHalt != NULL) {
      MR_RuleBlkWithHalt->end->halt=FALSE;
    };

    for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
      ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
      if (ruleRef == NULL) continue;

      MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];

      if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;

      rk2=empty;

      while ( !set_nil(*incomplete) ) {
		k2 = set_int(*incomplete);
        if (k2 > (unsigned) predDepth) break;       /* <=== another exit from loop */
		set_rm(k2,*incomplete);
		u = NULL;

        TRAV(ruleRef->next,k2,&rk2,u);

			/* any subtrees missing k2 tokens, add u onto end */

		*t=tlink(*t,u,k2);
        Tfree(u);
      }

	  set_orin(incomplete,rk2);         /* remember what we couldn't do */
      set_free(rk2);

      if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;

	  if (set_int(*incomplete) > (unsigned) predDepth) break;    /* <=== another exit from loop */
    };

    MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;

    if (MR_RuleBlkWithHalt != NULL) {
      MR_RuleBlkWithHalt->end->halt=TRUE;
    };
    ConstrainSearch=saveConstrainSearch;
}

#ifdef __USE_PROTOS
void MR_complete_predicates(int predDepth,Predicate *pred)
#else
void MR_complete_predicates(predDepth,pred)
  int           predDepth;
  Predicate     *pred;
#endif
{
  if (pred == NULL) return;
  if (pred->expr != PRED_AND_LIST &&
      pred->expr != PRED_OR_LIST) {
    MR_complete_set(predDepth,&(pred->scontext[1]),&(pred->completionSet));
    MR_complete_tree(predDepth,&(pred->tcontext),&(pred->completionTree));
  };
  MR_complete_predicates(predDepth,pred->down);
  MR_complete_predicates(predDepth,pred->right);
}

#ifdef __USE_PROTOS
Junction * MR_junctionWithoutP2(Junction *j)
#else
Junction * MR_junctionWithoutP2(j)
  Junction  *j;
#endif
{
  Junction  *thisAlt;

/* don't want to follow p2 to the next alternative of this rule */
/* insert a generic node with null p2 if necessary              */
/* however FIRST requires a junction                            */

  thisAlt=j;
  if (thisAlt->p2 != NULL) {
    if (thisAlt->p1->ntype == nJunction) {
      thisAlt=(Junction *) thisAlt->p1;
    } else {
      thisAlt=newJunction();
      thisAlt->p1=j->p1;
      thisAlt->rname=j->rname;
      thisAlt->file=j->file;
      thisAlt->line=j->line;
      j->p1=(Node *)thisAlt;
    };
  };
  return thisAlt;
}

#ifdef __USE_PROTOS
int MR_tree_equ(Tree *big, Tree *small) {
#else
int MR_tree_equ(big,small)
  Tree  *big;
  Tree  *small;
{
#endif

  Tree      *b;
  Tree      *s;
  int       bcount=0;
  int       scount=0;

  if (small == NULL && big == NULL) return 1;
  if (small == NULL) return 0;
  if (big == NULL) return 0;

  if (small->token == ALT) {
    require(small->right == NULL,
                "MR_tree_equ: small: ALT node has siblings");
    return MR_tree_equ(big,small->down);
  };
  if (big->token == ALT) {
    require(big->right == NULL,
                "MR_tree_equ: big: ALT node has siblings");
    return MR_tree_equ(big->down,small);
  };
  for (s=small; s != NULL; s=s->right) {
    scount++;
    require(s->token != EpToken,"MR_tree_equ: s->EpToken unexpected\n");
  };
  for (b=big; b != NULL; b=b->right) {
    bcount++;
    require(b->token != EpToken,"MR_tree_equ: b->EpToken unexpected\n");
  };

  if (bcount != scount) return 0;

  for (s=small; s != NULL; s=s->right) {
    for (b=big; b!= NULL; b=b->right) {
      if (s->token == b->token) {
        if (MR_tree_equ(b->down,s->down)) goto next_s;
      };
    };
    return 0;
next_s:
    continue;
  };
  return 1;
}

/* this does not compare sources - only contexts ! */

#ifdef __USE_PROTOS
int MR_identicalContext(Predicate *p,Predicate *q)
#else
int MR_identicalContext(p,q)
  Predicate     *p;
  Predicate     *q;
#endif
{
  if (p->k != q->k) return 0;
  require ( (p->tcontext == NULL) == (q->tcontext == NULL),
        "tcontext inconsistent");
  if (p->k == 1) {
    return set_equ(p->scontext[1],q->scontext[1]);
  } else {
    return MR_tree_equ(p->tcontext,q->tcontext);
  };
}

#ifdef __USE_PROTOS
void MR_reportSetSuppression(int predDepth,
            set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p)
#else
void MR_reportSetSuppression(predDepth,predSet,plainSet,jPred,jPlain,p)
  int       predDepth;
  set       predSet;
  set       plainSet;
  Junction  *jPred;
  Junction  *jPlain;
  Predicate *p;
#endif
{
  if (InfoP) {
    fprintf(output,"\n#if 0\n\n");
    fprintf(output,"Hoisting of predicate suppressed by alternative without predicate.\n");
    fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n");
    fprintf(output,"   WITH predicate: line %d  %s\n",jPred->line,FileStr[jPred->file]);
    if (jPlain != NULL) {
      fprintf(output,"   WITHOUT predicate: line %d  %s\n",jPlain->line,FileStr[jPlain->file]);
    } else {
      fprintf(output,"   WITHOUT predicate: all alternatives without predicates (combined)\n");
    };
    if (predDepth == 1) {
      fprintf(output,"\nThe context set for the predicate:\n");
      MR_dumpTokenSet(output,1,predSet);
    };
    fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
    MR_dumpTokenSet(output,1,plainSet);
    fprintf(output,"\nThe predicate:\n\n");
    MR_dumpPred1(1,p,1);
    fprintf(output,"Chain of referenced rules:\n\n");
    MR_dumpPredRuleRefStack(output,4);
    fprintf(output,"\n#endif\n");
  };
}

#ifdef __USE_PROTOS
void MR_reportSetRestriction(int predDepth,set predSet,set plainSet,
            Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred)
#else
void MR_reportSetRestriction(predDepth,predSet,plainSet,jPred,jPlain,origPred,newPred)
  int       predDepth;
  set       predSet;
  set       plainSet;
  Junction  *jPred;
  Junction  *jPlain;
  Predicate *origPred;
  Predicate *newPred;
#endif
{
  set       intersect;

  intersect=empty;

  if (! InfoP) return;
  fprintf(output,"\n#if 0\n\n");
  fprintf(output,"Restricting the context of a predicate because of overlap in the lookahead set\n");
  fprintf(output,"  between the alternative with the semantic predicate and one without\n");
  fprintf(output,"Without this restriction the alternative without the predicate could not\n");
  fprintf(output,"  be reached when input matched the context of the predicate and the predicate\n");
  fprintf(output,"  was false.\n\n");

  fprintf(output,"   WITH predicate: line %d  %s\n",jPred->line,FileStr[jPred->file]);
  if (jPlain != NULL) {
    fprintf(output,"   WITHOUT predicate: line %d  %s\n",jPlain->line,FileStr[jPlain->file]);
  } else {
    fprintf(output,"   WITHOUT predicate: all alternatives without predicates (combined)\n");
  };
  if (predDepth == 1) {
    fprintf(output,"\nThe original context set for the predicate:\n");
    MR_dumpTokenSet(output,1,predSet);
  };
  fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
  MR_dumpTokenSet(output,1,plainSet);
  if (predDepth == 1) {
    fprintf(output,"\nThe intersection of the two sets\n");
    intersect=set_and(predSet,plainSet);
    MR_dumpTokenSet(output,1,intersect);
    set_free(intersect);
  };
  fprintf(output,"\nThe original predicate:\n\n");
  MR_dumpPred1(1,origPred,1);
  fprintf(output,"The new (modified) form of the predicate:\n\n");
  MR_dumpPred1(1,newPred,1);
  fprintf(output,"#endif\n");
}

/* don't use Pass3 by itself unless you know that inverted is not important */

#ifdef __USE_PROTOS
Predicate * MR_removeRedundantPredPass3(Predicate *p)
#else
Predicate * MR_removeRedundantPredPass3(p)
  Predicate *p;
#endif
{
  Predicate     *q;

  if (p == NULL) return NULL;
  p->right=MR_removeRedundantPredPass3(p->right);
  p->down=MR_removeRedundantPredPass3(p->down);
  if (p->redundant) {
    q=p->right;
    p->right=NULL;
    predicate_free(p);
    return q;
  };
  if (p->expr == PRED_AND_LIST ||
      p->expr == PRED_OR_LIST) {
    if (p->down == NULL) {
      q=p->right;
      p->right=NULL;
      predicate_free(p);
      return q;
    };
    if (p->down != NULL && p->down->right == NULL) {
      q=p->down;
      q->right=p->right;
      p->right=NULL;
      p->down=NULL;
      return q;
    };
  };
  return p;
}

#ifdef __USE_PROTOS
void MR_removeRedundantPredPass2(Predicate *p)
#else
void MR_removeRedundantPredPass2(p)
  Predicate *p;
#endif
{
  Predicate     *q;

  if (p == NULL) return;

  if (p->expr == PRED_AND_LIST) {
    for (q=p->down ; q != NULL ; q=q->right) {
      MR_removeRedundantPredPass2(q);
      if (q->isConst) {
        if (q->constValue == 0) {
          p->isConst=1;
          p->constValue=0;
          return;
        } else {
          q->redundant=1;
        };
      };
    };
  };

  if (p->expr == PRED_OR_LIST) {
    for (q=p->down ; q != NULL ; q=q->right) {
      MR_removeRedundantPredPass2(q);
      if (q->isConst) {
        if (q->constValue == 0) {
          q->redundant=1;
        } else {
          p->isConst=1;
          p->constValue=1;
          return;
        };
      };
    };
  };

  return;
}

#if 0
   this totally ignores the implications of guarded predicates
     in which the part after the guard could possibly cover a predicate.
   that would be much harder:

        rule : (A)? => <<p>>? sub1;     /* 1 */
             | (B)? => <<r>>? sub2      /* 2 */
        sub1 : (A)? => <<q>>? A B       /* 3 */
             | B                        /* 4 - suppresses line 2 */
             ;
#endif

#ifdef __USE_PROTOS
void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed)
#else
void MR_apply_restriction1(pred,plainSet,changed)
  Predicate     *pred;
  set           *plainSet;
  int           *changed;
#endif
{
  if (pred == NULL) return;
  MR_apply_restriction1(pred->right,plainSet,changed);
  if (pred->down != NULL) {
    MR_apply_restriction1(pred->down,plainSet,changed);
  } else {
    set     t;
    if (pred->k == 1) {
      t=set_dif(pred->scontext[1],*plainSet);
      if (*changed == 0 &&
          !set_equ(t,pred->scontext[1])) {
        *changed=1;
      };
      if (set_nil(t)) {
        pred->redundant=1;
      };
      set_free(pred->scontext[1]);
      pred->scontext[1]=t;
    };
  };
}

#ifdef __USE_PROTOS
void MR_orin_plainSet(Predicate *p,set plainSet)
#else
void MR_orin_plainSet(p,plainSet)
  Predicate     *p;
  set           plainSet;
#endif
{
  if (p == NULL) return;
  MR_orin_plainSet(p->down,plainSet);
  MR_orin_plainSet(p->right,plainSet);
  set_orin(&p->plainSet,plainSet);
}

Predicate   *PRED_SUPPRESS;

#ifdef __USE_PROTOS
Predicate * MR_find_in_aSubBlk(Junction *alt)
#else
Predicate * MR_find_in_aSubBlk(alt)
  Junction  *alt;
#endif
{
    Predicate       *root=NULL;
    Predicate       **tail=NULL;

	Junction        *p;

    int             nAlts=0;
    Junction        **jList;
    Predicate       **predList;
    int             *matchList;
    set             predSet;
    int             i;
    int             j;
    int             m;
    int             predDepth;
    set             incomplete;
    set             union_plainSet;
    set             setChange;
    int             changed;
    Predicate       *newPred;
    set             setDif;
    Predicate       *origPred;
    int             depth1=1;             /* const int */
    set             *plainContext;
    set             plainSet;

    predSet=empty;
    incomplete=empty;
    union_plainSet=empty;
    setChange=empty;
    setDif=empty;
    plainSet=empty;

    if (PRED_SUPPRESS == NULL) {
      PRED_SUPPRESS=new_pred();
      PRED_SUPPRESS->expr="Predicate Suppressed";
    };

    /* this section just counts the number of "interesting" alternatives  */
    /*   in order to allocate arrays                                      */

	for (p=alt; p!=NULL; p=(Junction *)p->p2) {
	  /* ignore empty alts */
	  if ( p->p1->ntype != nJunction ||
	        ((Junction *)p->p1)->jtype != EndBlk )	{
        nAlts++;
      };
    };

    /* if this is a (...)+ block then don't count the last alt because
       it can't be taken until at least one time through the block.
       In other words it isn't a real choice until the (...)+ is entered
         at which point the hoisting issue is moot.
       Maybe look at "ignore" instead ?
    */

    if (alt->jtype == aPlusBlk) {
      nAlts--;
    };

    jList=(Junction **)calloc(nAlts,sizeof(Junction *));
    require(jList!=NULL,"cannot allocate MR_find_in_aSubBlk jList");

    plainContext=(set *)calloc(nAlts,sizeof(set));
    require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext");
    for (m=0; m < nAlts; m++) plainContext[m]=empty;

    predList=(Predicate **)calloc(nAlts,sizeof(Predicate *));
    require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList");

    matchList=(int *)calloc(nAlts,sizeof(int));
    require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList");

    /* this section just fills in the arrays previously allocated       */
    /* the most interesting one is matchList[]                          */
    /*                                                                  */
    /*   bit 0 => this alt has a semantic pred which is "covered"       */
    /*              by an alt without a semantic pred.  Don't hoist.    */

	for (i=0,p=alt;
         p!=NULL && i<nAlts;
         i++,p=(Junction *)p->p2) {

	  /* ignore empty alts */

	  if ( p->p1->ntype != nJunction ||
	        ((Junction *)p->p1)->jtype != EndBlk )	{
        jList[i]=MR_junctionWithoutP2(p);
        predList[i]=find_predicates(p->p1);      /* should be jList ????? */
        if (predList[i] != NULL) {
          MR_cleanup_pred_trees(predList[i]);    /* flatten & left factor */
          plainContext[i]=MR_union_plain_sets(predList[i]);
        } else {
          MR_set_reuse(&plainSet);
          MR_set_reuse(&incomplete);
          plainSet=MR_First(depth1,jList[i],&incomplete);
          MR_complete_set(depth1,&plainSet,&incomplete);
          require(set_nil(incomplete),"couldn't complete k=1");
          plainContext[i]=plainSet;
          plainSet=empty;
        };
        set_orin(&union_plainSet,plainContext[i]);
      };
    };

    if (nAlts == 1) {
      goto EXIT_SIMPLE;
    };

/*
 *  Looking for cases where alt i has a semantic pred and alt j does not.
 *  Don't care about cases where lookahead for semantic predicates overlap
 *    because normal predicate hoisting does the correct thing automatically.
 *  Don't care about cases where lookahead for alts without semantic predicates
 *    overlap because normal prediction does the correct thing automatically.
 *
 *  When we find such a case check for one of three subcases:
 *
 *      1.  if lookahead for alt i is contained in the lookahead for any
 *          alt j then ignore semantic predicate of alt i
 *      2.  if lookahead for alt i is not contained in the lookahead for
 *          any alt j then add add predicate i to the OR list to be hoisted
 *      3.  if lookahead for alt i overlaps the lookahead for some alt j then
 *          add a dummy semantic predicate for alt j
 *
 *  There is an implicit assumption that the context of all alternatives following
 *  the rule being processed here are identical (but may vary from hoist to
 *  hoist depending on the place where the rule was invoked that led to hoisting
 *  these predicates.  In othere words in the fragment:
 *
 *            ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )
 *
 *  both a3 and b3 have the same follow sets  because they are both at the end of
 *  alternatives in the same block.
 */

    for (i=0; i < nAlts; i++) {
      if (jList[i] == NULL) continue;
      if (predList[i] == NULL) continue;

        /* if the predicate depth turns out to be one token only */
        /*   then it is can be easily represented as a set and   */
        /*   compared to the junction set create by MR_First()   */

      predDepth=0;
      MR_pred_depth(predList[i],&predDepth);
      require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1");
      require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k");

        /* complete predicates to predDepth
           If completed to depth=1 then the context would be incomplete.
           The context would be truncated and the predicate simplify routine
             would have incomplete information.  It would lead to
             either false matches of failure to find true matches.
        */

      MR_complete_predicates(predDepth,predList[i]);

      if (predList[i] != NULL) {
        MR_cleanup_pred_trees(predList[i]);    /* flatten & left factor */
      };

      /* If the predicate depth is 1 then it is possible to suppress
           a predicate completely using a single plain alt.  Check for suppression
           by a single plain alt first because it gives better messages.  If that
           fails try the union of all the plain alts.
      */

      if (predDepth == 1) {

        MR_set_reuse(&predSet);
        predSet=MR_compute_pred_set(predList[i]);   /* ignores k>1 predicates */

        for (j=0; j < nAlts; j++) {
          if (jList[j] == NULL) continue;
          if (j == i) continue;

          MR_set_reuse(&setDif);
          setDif=set_dif(predSet,plainContext[j]);
          if (set_nil(setDif)) {
            matchList[i] |= 1;
            MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]);
            predicate_free(predList[i]);
            predList[i]=PRED_SUPPRESS;
            goto next_i;
          };

        }; /* end loop on j */

        changed=0;

        /* predicate_dup is only to give good error messages */
        /* remember to do a predicate_free()                 */

        origPred=predicate_dup(predList[i]);
        MR_apply_restriction1(predList[i],&union_plainSet,&changed);
        if (changed) {

          /* don't use Pass3 by itself unless you know that inverted is not important */

          newPred=MR_removeRedundantPredPass3(predList[i]);
          newPred=MR_predSimplifyALL(newPred);
          if (newPred == NULL) {
            matchList[i] |= 1;
            MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
                                                            NULL,origPred);
            predList[i]=PRED_SUPPRESS;
          } else {
            MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
                                                    NULL,origPred,newPred);
            predList[i]=newPred;
          };
        };
        predicate_free(origPred);
        origPred=NULL;
      };

      /*
         If the predicate depth is > 1 then it can't be suppressed completely
           because the code doesn't support inspection of such things.  They're
           much messier than k=1 sets.
      */

      if (predDepth > 1 ) {

        changed=0;

        /* predicate_dup is only to give good error messages */
        /* remember to do a predicate_free()                 */

        origPred=predicate_dup(predList[i]);
        MR_apply_restriction1(predList[i],&union_plainSet,&changed);
        if (changed) {
          newPred=MR_removeRedundantPredPass3(predList[i]);
          newPred=MR_predSimplifyALL(newPred);
          if (newPred == NULL) {
            matchList[i] |= 1;
            MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
                                                            NULL,origPred);
            predList[i]=PRED_SUPPRESS;
          } else {
            MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
                                                    NULL,origPred,newPred);
            predList[i]=newPred;
          };
        };
        predicate_free(origPred);
        origPred=NULL;
      };
next_i:
      continue;
    };

EXIT_SIMPLE:

    root = new_pred();
    root->expr=PRED_OR_LIST;
    tail = &(root->down);

    for (i=0 ; i< nAlts ; i++) {
      if (jList[i] == NULL) continue;

      if (predList[i] == NULL) {
        continue;
      } else if ( (matchList[i] & 1) != 0) {
        if (predList[i] != PRED_SUPPRESS) {
          predicate_free(predList[i]);
        };
        continue;
      };

      /* make an OR list of predicates */

      *tail=predList[i];
      tail=&(predList[i]->right);
    };

	/* if just one pred, remove OR root */

	if (root->down == NULL) {
      predicate_free(root);
      root=NULL;
    } else if (root->down->right == NULL) {
      Predicate     *p=root->down;
      root->down=NULL;
      predicate_free(root);
      root=p;
	}

    root=MR_predSimplifyALL(root);

    MR_orin_plainSet(root,union_plainSet);

    set_free(predSet);
    set_free(union_plainSet);
    set_free(incomplete);
    set_free(setChange);
    set_free(setDif);

    for (m=0; m < nAlts; m++) set_free(plainContext[m]);

    free ( (char *) jList);
    free ( (char *) predList);
    free ( (char *) matchList);
    free ( (char *) plainContext);

	return root;
}

#ifdef __USE_PROTOS
void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)
#else
void MR_predContextPresent(p,allHaveContext,noneHaveContext)
  Predicate     *p;
  int           *allHaveContext;
  int           *noneHaveContext;
#endif
{
  if (p == NULL) return;
  MR_predContextPresent(p->right,allHaveContext,noneHaveContext);
  if (p->expr != PRED_AND_LIST &&
      p->expr != PRED_OR_LIST) {
    if (set_nil(p->scontext[1]) == 0 ||
            (p->tcontext != NULL)) {
      *noneHaveContext=0;
    } else {
      *allHaveContext=0;
    };
  };
  MR_predContextPresent(p->down,allHaveContext,noneHaveContext);
}

#ifdef __USE_PROTOS
int MR_pointerStackPush(PointerStack *ps,void *dataPointer)
#else
int MR_pointerStackPush(ps,dataPointer)
  PointerStack  *ps;
  void          *dataPointer;
#endif
{
  void             **newStack;
  int              newSize;
  int              i;

  if (ps->count == ps->size) {
    newSize=20+ps->size*2;
    newStack=(void **)calloc(newSize,sizeof(void *));
    require (newStack != NULL,"cannot allocate PointerStack");
    for (i=0; i < ps->size; i++) {
      newStack[i]=ps->data[i];
    };
    if (ps->data != NULL) free( (char *) ps->data);
    ps->data=newStack;
    ps->size=newSize;
  };
  ps->data[ps->count]=dataPointer;
  ps->count++;
  return ps->count-1;
}

#ifdef __USE_PROTOS
void * MR_pointerStackPop(PointerStack *ps)
#else
void * MR_pointerStackPop(ps)
  PointerStack  *ps;
#endif
{
  void  *dataPointer;

  require(ps->count > 0,"MR_pointerStackPop underflow");

  dataPointer=ps->data[ps->count-1];
  ps->data[ps->count-1]=NULL;
  (ps->count)--;
  return dataPointer;
}

#ifdef __USE_PROTOS
void * MR_pointerStackTop(PointerStack *ps)
#else
void * MR_pointerStackTop(ps)
  PointerStack  *ps;
#endif
{
  require(ps->count > 0,"MR_pointerStackTop underflow");
  return ps->data[ps->count-1];
}

#ifdef __USE_PROTOS
void MR_pointerStackReset(PointerStack *ps)
#else
void MR_pointerStackReset(ps)
  PointerStack  *ps;
#endif
{
  int i;
  if (ps->data != NULL) {
    for (i=0; i < ps->count ; i++) {
       ps->data[i]=NULL;
    };
  };
  ps->count=0;
}

#ifdef __USE_PROTOS
Junction *MR_nameToRuleBlk(char *name)
#else
Junction *MR_nameToRuleBlk(name)
  char  *name;
#endif
{
    RuleEntry *q;

    require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized");

    if (name == NULL) return NULL;

    q = (RuleEntry *) hash_get(Rname,name);

	if ( q == NULL ) {
      return NULL;
    } else {
      return RulePtr[q->rulenum];
    };
}

#ifdef __USE_PROTOS
Junction * MR_ruleReferenced(RuleRefNode *rrn)
#else
Junction * MR_ruleReferenced(rrn)
  RuleRefNode   *rrn;
#endif
{
    return MR_nameToRuleBlk(rrn->text);
}

#ifdef __USE_PROTOS
void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)
#else
void MR_comparePredLeaves(me,myParent,him,hisParent)
    Predicate *me;
    Predicate *myParent;
    Predicate *him;
    Predicate *hisParent;
#endif
{
    if (me == NULL) return;
    if (me == him) {
      MR_comparePredLeaves(me->right,myParent,him,hisParent);
      return;
    } else if (me->expr == PRED_AND_LIST ||
               me->expr == PRED_OR_LIST) {
      MR_comparePredLeaves(me->down,me,him,hisParent);
      MR_comparePredLeaves(me->right,myParent,him,hisParent);
      return;
    } else {
      if (me->source != NULL) {

        /* predicate->invert can be set only in the predEntry predicates        */
        /* thus they are only visible after the predEntry predicates have been "unfolded" */

        int     sameSource=(me->source == him->source);
        int     sameInvert=1 &
                 (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted);
        int     samePredEntry=(me->source->predEntry != NULL
                                 && him->source->predEntry != NULL
                                    && me->source->predEntry == him->source->predEntry);
        if (sameInvert && (sameSource || samePredEntry)) {
          if (MR_identicalContext(me,him)) {

            /* identical predicates */

            if (hisParent->expr == PRED_OR_LIST &&
                myParent->expr == PRED_OR_LIST) {
              me->redundant=1;
            } else if (hisParent->expr == PRED_AND_LIST &&
                       myParent->expr == PRED_AND_LIST) {
              me->redundant=1;
            } else if (  (hisParent->expr == PRED_OR_LIST &&
                          myParent->expr == PRED_AND_LIST)
                       ||
                         (hisParent->expr == PRED_AND_LIST &&
                          myParent->expr == PRED_OR_LIST)
                      ) {
              myParent->redundant=1;
            } else {
              require (0,"MR_comparePredLeaves: not both PRED_LIST");
            };
          };
        };  /* end same source or same predEntrr with same invert sense */

        /* same predEntry but opposite invert sense */

        if (!sameInvert && (sameSource || samePredEntry)) {
          if (MR_identicalContext(me,him)) {
            if (hisParent->expr == PRED_OR_LIST &&
                myParent->expr == PRED_OR_LIST) {
              myParent->isConst=1;
              myParent->constValue=1;
            } else if (hisParent->expr == PRED_AND_LIST &&
                       myParent->expr == PRED_AND_LIST) {
              myParent->isConst=1;
              myParent->constValue=0;
            } else if (  (hisParent->expr == PRED_OR_LIST &&
                          myParent->expr == PRED_AND_LIST)
                       ||
                         (hisParent->expr == PRED_AND_LIST &&
                          myParent->expr == PRED_OR_LIST)
                      ) {
              me->redundant=1;
            } else {
              require (0,"MR_comparePredLeaves: not both PRED_LIST");
            };
          };
        };  /* end same predEntry with opposite invert sense */
      };

      MR_comparePredLeaves(me->right,myParent,him,hisParent);
      return;
    };
}

#ifdef __USE_PROTOS
void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)
#else
void MR_removeRedundantPredPass1(me,myParent)
  Predicate     *me;
  Predicate     *myParent;
#endif
{
    if (me == NULL) return;
    if (me->redundant) {
      MR_removeRedundantPredPass1(me->right,myParent);
      return;
    };
    if (me->expr == PRED_AND_LIST ||
        me->expr == PRED_OR_LIST) {
      MR_removeRedundantPredPass1(me->down,me);
      MR_removeRedundantPredPass1(me->right,myParent);
    } else {
      require (me->source != NULL,"me->source == NULL");
      if (myParent != NULL) {
        MR_comparePredLeaves(myParent->down,myParent,me,myParent);
      };
      MR_removeRedundantPredPass1(me->right,myParent);
    };
}

/* pretty much ignores things with the inverted bit set */

#ifdef __USE_PROTOS
Predicate *MR_predFlatten(Predicate *p)
#else
Predicate *MR_predFlatten(p)
  Predicate     *p;
#endif
{
    if (p == NULL) return NULL;
    if (p->expr == PRED_OR_LIST
        || p->expr == PRED_AND_LIST) {

      Predicate     *child;
      Predicate     *gchild;
      Predicate     **tail;
      Predicate     *next;
      char          *PRED_XXX_LIST=p->expr;

      require (p->down != NULL,"MR_predFlatten AND/OR no child");


      p->down=MR_predFlatten(p->down);
      p->right=MR_predFlatten(p->right);
      child=p->down;
      if (child->right == NULL) {
        child->right=p->right;
        p->right=NULL;
        p->down=NULL;
        if (p->inverted) child->inverted=!child->inverted;
        predicate_free(p);
        return child;
      };

      /* make a single list of all children and grandchildren */

      tail=&(p->down);
      for (child=p->down; child != NULL; child=next) {
        if (child->expr != PRED_XXX_LIST
              || child->inverted
                || child->predEntry != NULL) {
          *tail=child;
          tail=&(child->right);
          next=child->right;
        } else {
          for (gchild=child->down;
               gchild != NULL;
               gchild=gchild->right) {
            *tail=gchild;
            tail=&(gchild->right);
          };
          next=child->right;
          child->right=NULL;
          child->down=NULL;
          predicate_free(child);
        };
      };
      *tail=NULL;
      return p;
    } else {
      p->right=MR_predFlatten(p->right);
      return p;
    };
}

static char *alwaysFalseWarning=NULL;

#ifdef __USE_PROTOS
Predicate *checkPredicateConflict(Predicate *p)
#else
Predicate *checkPredicateConflict(p)
  Predicate     *p;
#endif
{
  if (p->isConst) {
    if (p->constValue == 1) {
      predicate_free(p);
      return NULL;
    } else {
      if (InfoP && !p->conflictReported) {
        p->conflictReported=1;
        fprintf(output,"\n#if 0\n\n");
        fprintf(output,"The following predicate expression will always be false:\n\n");
        MR_dumpPred1(1,p,1);
        fprintf(output,"\n#endif\n");
      };

      if (alwaysFalseWarning != CurRule) {
        alwaysFalseWarning=CurRule;
        if (InfoP) {
          warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \
- see output file for more information",CurRule));
        } else {
          warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \
- use \"-info p\" for more information",CurRule));
        };
      };
    };
  };
  return p;
}


#ifdef __USE_PROTOS
int MR_countPredNodes(Predicate *p)
#else
int MR_countPredNodes(p)
  Predicate     *p;
#endif
{
  if (p == NULL) return 0;
  return 1 + MR_countPredNodes(p->down) + MR_countPredNodes(p->right);
}

#ifdef __USE_PROTOS
Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3)
#else
Predicate *MR_predSimplifyALLX(p,skipPass3)
  Predicate     *p;
  int           skipPass3;
#endif
{
  int       countBefore;
  int       countAfter;

  countAfter=MR_countPredNodes(p);

  do {
      if (p == NULL) return NULL;
      if (p->right == NULL && p->down == NULL) return p;
      countBefore=countAfter;
      MR_simplifyInverted(p,0);
      p=MR_predFlatten(p);
      MR_removeRedundantPredPass1(p,NULL);
      MR_removeRedundantPredPass2(p);
      if (! skipPass3) {
        p=checkPredicateConflict(p);
        p=MR_removeRedundantPredPass3(p);
      };
      countAfter=MR_countPredNodes(p);
  } while (countBefore != countAfter);

  return p;
}

#ifdef __USE_PROTOS
Predicate *MR_predSimplifyALL(Predicate *p)
#else
Predicate *MR_predSimplifyALL(p)
  Predicate     *p;
#endif
{
  return MR_predSimplifyALLX(p,0);
}

#ifdef __USE_PROTOS
void MR_releaseResourcesUsedInRule(Node *n)
#else
void MR_releaseResourcesUsedInRule(n)
  Node  *n;
#endif
{
   Node         *next;
   Junction     *j;
   int          i;

   if (n == NULL) return;
   if (n->ntype == nJunction) {
     j=(Junction *) n;

     if (j->predicate != NULL) {
       predicate_free(j->predicate);
       j->predicate=NULL;
     };
     for (i=0; i< CLL_k; i++) {
       set_free(j->fset[i]);
       j->fset[i]=empty;
     };
     if (j->ftree != NULL) {
       Tfree(j->ftree);
       j->ftree=NULL;
     };
     if (j->jtype == EndRule) return;
     if (j->jtype != RuleBlk && j->jtype != EndBlk) {
       if (j->p2 != NULL && !j->ignore) {   /* MR11 */
          MR_releaseResourcesUsedInRule(j->p2);
       };
     };
   };
   next=MR_advance(n);
   MR_releaseResourcesUsedInRule(next);
}

#ifdef __USE_PROTOS
int MR_allPredLeaves(Predicate *p)
#else
int MR_allPredLeaves(p)
  Predicate *p;
#endif
{
  Predicate     *q;

  if (p == NULL) return 1;

  for (q=p; q != NULL; q=q->right) {
   if (q->down != NULL) return 0;
  };
  return 1;
}

/* make sure it works for the last rule in a file */

#ifdef __USE_PROTOS
int MR_offsetFromRule(Node *n)
#else
int MR_offsetFromRule(n)
  Node      *n;
#endif
{
  Junction  *j;
  int       offset=(-1);

  for (j=SynDiag; j != NULL; j=(Junction *)j->p2) {

    require (j->ntype == nJunction && j->jtype == RuleBlk,"Not a rule block");

    if (n->file < j->file) {
      return offset;
    };
    if (n->file == j->file) {
      if (n->line < j->line) {
        return (offset < 0) ? 0 : offset;
      } else {
        offset=n->line - j->line;
        if (offset == 0) return 0;
      };
    };
  };
  return offset;
}

#define ruleNameMax 50

static char ruleNameStatic1[ruleNameMax];
static char ruleNameStatic2[ruleNameMax+10];

#ifdef __USE_PROTOS
char * MR_ruleNamePlusOffset(Node *n)
#else
char * MR_ruleNamePlusOffset(n)
  Node      *n;
#endif
{
    int     offset=MR_offsetFromRule(n);

    strncpy(ruleNameStatic1,n->rname,ruleNameMax);
    if (offset < 0) {
      sprintf(ruleNameStatic2,"%s/?",ruleNameStatic1);
    } else {
      sprintf(ruleNameStatic2,"%s/%d",ruleNameStatic1,offset+1);
    };
    return ruleNameStatic2;
}

#ifdef __USE_PROTOS
int MR_max_height_of_tree(Tree *t)
#else
int MR_max_height_of_tree(t)
  Tree  *t;
#endif
{
  int       h;
  int       height=0;
  Tree      *u;

  if (t == NULL) return 0;

  require (t->token != ALT && t->token != EpToken,"MR_max_height_of_tree ALT or EpToken");

  for (u=t; u != NULL; u=u->right) {
    h=MR_max_height_of_tree(u->down)+1;
    if (h > height) height=h;
  };
  return height;
}

#ifdef __USE_PROTOS
int MR_all_leaves_same_height(Tree *t,int depth)
#else
int MR_all_leaves_same_height(t,depth)
  Tree  *t;
  int   depth;
#endif
{
  if (t == NULL) {
    return (depth==0);
  };

  require (t->token != ALT && t->token != EpToken,"MR_all_leaves_same_height ALT or EpToken");

  if (depth == 0) {
    return 0;
  } else {
    if ( ! MR_all_leaves_same_height(t->down,depth-1)) {
      return 0;
    };
    if (t->right == NULL) {
      return 1;
    } else {
      return MR_all_leaves_same_height(t->right,depth);
    };
  };
}

#ifdef __USE_PROTOS
void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset)
#else
void MR_projectTreeOntoSet(tree,ck,ckset)
  Tree  *tree;
  int   ck;
  set   *ckset;
#endif
{
    if (tree == NULL) return;

    require(tree->token != EpToken,"MR_projectTreeOntoSet: EpToken unexpected\n");

    MR_projectTreeOntoSet(tree->right,ck,ckset);
    if (tree->token == ALT) {
      MR_projectTreeOntoSet(tree->down,ck,ckset);
    } else {
      if (ck > 1) {
        MR_projectTreeOntoSet(tree->down,ck-1,ckset);
      } else {
        set_orel(tree->token,ckset);
      };
    };
}

#ifdef __USE_PROTOS
int MR_comparePredicates(Predicate *a,Predicate *b)
#else
int MR_comparePredicates(a,b)
  Predicate     *a;
  Predicate     *b;
#endif
{
  Predicate     *p;
  Predicate     *q;

  if (a == b) return 1;
  if (a == NULL || b == NULL ) return 0;
  if (a->down == NULL && b->down == NULL) {

    /* predicate->invert can be set only in the predEntry predicates                  */
    /* thus they are only visible after the predEntry predicates have been "unfolded" */

    int     sameSource=(a->source == b->source);
    int     sameInvert= 1 & (1 +a->inverted + b->inverted +
                                a->source->inverted + b->source->inverted);
    int     samePredEntry=(a->source->predEntry != NULL
                                 && b->source->predEntry != NULL
                                    && a->source->predEntry == b->source->predEntry);
    if (sameInvert && (sameSource || samePredEntry)) {
      if (MR_identicalContext(a,b)) {
         return 1;
      };
    };
    return 0;
  };
  if (a->down == NULL || b->down == NULL) return 0;
  if (a->expr != b->expr) return 0;

  for (p=a->down; p != NULL; p=p->right) {
    for (q=b->down; q != NULL; q=q->right) {
      if (MR_comparePredicates(p,q)) goto NEXT_P;
    };
    return 0;
NEXT_P:
    continue;
  };
  return 1;
}

/*
 *  action->inverted can be set only when a predicate symbol appears in
 *      a rule:  "rule : <<!XXX>>? X".  It cannot be set under any
 *      other circumstances.  In particular it cannot be set by
 *      "#pred NotA !A" or by "#pred Nota <<!A>>?".  The first case
 *      creates a predEntry and the predicate expression of that predEntry
 *      has inverted set.  In the second case, the code for handling "!"
 *      is only present in buildAction, which is not called by the #pred
 *      semantic routines, only when a <<...>>? is recognized as part of
 *      a rule definition.
 *
 *  predicate->inverted can only be set by a predicate created by a #pred
 *      expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or
 *      "#pred XbarY !(X && Y)".  In particular, it cannot be set by any
 *      predicate expression occurring under any other circumstances.
 *      The #pred predicate expressions are stored with in predEntry->pred
 *      and do not normally appear anywhere else until the predicates are
 *      "unfolded" in order to recognize redundancies, conflicts, and
 *      tautologies.
 *
 *  The unfold routine expands all references to #pred expressions.
 *
 *  The simplifyInvert goes through and propagates the invert bit so that
 *      all OR and AND nodes are un-inverted.
 *
 *  Note that !(A and B) => (!A or !B)
 *            !(A or B)  => (!A and !B)
 *
 *  MR_unfold() is called to expand predicate symbols by replacing predicates
 *    that reference predicate entries with the copies of the predicate entries.
 *    Each reference receives a duplicate of the original.  This is necessary
 *    because the next phase involves simplification and removal of redundant
 *    predicate nodes.  Anyway, the point I'm making is that predicate->invert
 *    should not be set in any predicate until it has been expanded.
 *
 *    This is a recursive structure, but there is no need for "recursive expansion"
 *    by which I mean a predicate symbol refers to other predicate symbols which
 *    must also be expanded.
 *
 *    Recursive expansion is *not* performed by this routine because it is not
 *    necessary.  Expansion of references is performed by predPrimary when
 *    a new predicate symbol is created by referring to others in the pred expr.
 */

#ifdef __USE_PROTOS
Predicate *MR_unfold(Predicate *pred)
#else
Predicate *MR_unfold(pred)
  Predicate     *pred;
#endif
{
  Predicate     *result;

  if (pred == NULL) return NULL;

  pred->right=MR_unfold(pred->right);

  if (pred->down == NULL) {
    if (pred->source->predEntry != NULL) {
      if (pred->source->predEntry->pred == NULL) {
        ; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */
      } else {
        result=predicate_dup_without_context(pred->source->predEntry->pred);
        if (pred->inverted) {
          result->inverted=!result->inverted;
        };
        if (pred->source->inverted) {
          result->inverted=!result->inverted;
        };
        result->right=pred->right;
        pred->right=NULL;
        predicate_free(pred);
/***    result=MR_unfold(result); *** not necessary */    /* recursive expansion */
        return result;
      };
    } else {
      ; /* do nothing */ /* an inline literal predicate */
    };
  } else {
    pred->down=MR_unfold(pred->down);
  };
  return pred;
}

/* this should be called immediately after MR_unfold() and
   at no other times
*/

#ifdef __USE_PROTOS
void MR_simplifyInverted(Predicate *pred,int inverted)
#else
void MR_simplifyInverted(pred,inverted)
  Predicate     *pred;
  int           inverted;
#endif
{
  int       newInverted;

  if (pred == NULL) return;

  MR_simplifyInverted(pred->right,inverted);

  newInverted= 1 & (inverted + pred->inverted);

  if (pred->down == NULL) {
    pred->inverted=newInverted;
  } else {
    if (newInverted != 0) {
      if (pred->expr == PRED_AND_LIST) {
        pred->expr=PRED_OR_LIST;
      } else {
        pred->expr=PRED_AND_LIST;
      };
    };
    pred->inverted=0;
    MR_simplifyInverted(pred->down,newInverted);
  };
}

/* only remove it from AND and OR nodes, not leaves */

#ifdef __USE_PROTOS
void MR_clearPredEntry(Predicate *p)
#else
void MR_clearPredEntry(p)
  Predicate     *p;
#endif
{
   if (p == NULL) return;
   MR_clearPredEntry(p->down);
   MR_clearPredEntry(p->right);
   if (p->down != NULL) p->predEntry=NULL;
}


#ifdef __USE_PROTOS
void MR_orphanRules(FILE *f)
#else
void MR_orphanRules(f)
  FILE      *f;
#endif
{
	set         a;
    Junction    *p;
    unsigned    e;
    RuleEntry   *re;

	a=empty;

    if (! InfoO) return;

	for (p=SynDiag; p!=NULL; p = (Junction *)p->p2)	{
      if ( (Junction *) (p->end)->p1 == NULL) {
        re=(RuleEntry *) hash_get(Rname,p->rname);
        require (re != NULL,"RuleEntry == NULL");
		set_orel(re->rulenum, &a);
      }
  	}

    if (set_deg(a) > 1) {
      fprintf(f,"note: Start rules: {");
      for (; !set_nil(a); set_rm(e,a)) {
        e=set_int(a);
        fprintf(f," %s",RulePtr[e]->rname);
      };
      fprintf(f," }\n");
    };
	set_free( a );
}

/*  merge (X Y) and (X) to create (X)  */

static int      *mergeChain;
static Tree     *mergeTree;

#ifdef __USE_PROTOS
Tree *MR_merge_tree_contexts_client(Tree *t,int chain[])
#else
Tree *MR_merge_tree_contexts_client(t,chain)
  Tree  *t;
  int   chain[];
#endif
{
  if (t == NULL)  return NULL;
  if (chain[0] == 0) {
    Tree    *u=t->right;
    t->right=NULL;
    Tfree(t);
    return MR_merge_tree_contexts_client(u,&chain[0]);
  }
  if (chain[0] == t->token) {
    t->down=MR_merge_tree_contexts_client(t->down,&chain[1]);
  };
  t->right=MR_merge_tree_contexts_client(t->right,&chain[0]);
  return t;
}

#ifdef __USE_PROTOS
void MR_iterateOverTreeContexts(Tree *t,int chain[])
#else
void MR_iterateOverTreeContexts(t,chain)
  Tree          *t;
  int           chain[];
#endif
{
  if (t == NULL) return;
  chain[0]=t->token;
  if (t->down != NULL) {
    MR_iterateOverTreeContexts(t->down,&chain[1]);
  } else {
    MR_merge_tree_contexts_client(mergeTree,mergeChain);
  };
  MR_iterateOverTreeContexts(t->right,&chain[0]);
  chain[0]=0;
}

#ifdef __USE_PROTOS
Tree *MR_merge_tree_contexts(Tree *t)
#else
Tree *MR_merge_tree_contexts(t)
  Tree  *t;
#endif
{
    int     h=MR_max_height_of_tree(t);

    mergeTree=t;
    mergeChain=(int *) calloc(h+1,sizeof(int));
    require (mergeChain != NULL,"MR_merge_tree_contexts: can't alloc chain");
    MR_iterateOverTreeContexts(t,mergeChain);
    t=tshrink(t);
    t=tflatten(t);
    t=tleft_factor(t);
    free ( (char *) mergeChain);
    mergeChain=NULL;
    return t;
}

#ifdef __USE_PROTOS
Tree *MR_compute_pred_tree_context(Predicate *p)
#else
Tree *MR_compute_pred_tree_context(p)
  Predicate *p;
#endif
{
  Tree  *t;

  t=MR_compute_pred_tree_ctxXX(p);
  MR_merge_tree_contexts(t);
  return t;
}

#ifdef __USE_PROTOS
void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred)
#else
void MR_guardPred_plainSet(anode,pred)
  ActionNode    *anode;
  Predicate     *pred;
#endif
{
  Junction      *j;
  Predicate     *workPred;
  set           maskSet;

  maskSet=empty;

  if (!MRhoisting) return;

  /* it doesn't really matter whether the predicate has
     depth k=1 or k>1 because we're not really looking
     at the predicate itself, just the stuff "behind"
     the predicate.
  */

  /* shouldn't have to worry about REACHing off the end
     of the rule containing the predicate because the
     Rule->end->halt should have been set already by the
     the code which handles RuleRef nodes.

     We don't want to REACH off the end of the rule because
     this would give the "global" follow context rather than
     the "local" context.

         r1a : (A)? => <<p>>? r2 (A|B)
         r1b : (A)? => <<p>>? r2 (A|C)
         r2  : ();

     For r1a we want follow of predicate = {A B}
             we want plainSet = {B}
     For r1b we want follow of predicate = {A C}
             we want plainSet = {C}
  */

  require (anode->next->ntype == nJunction,"MR_guardpred_plainSet not Junction");
  j=(Junction *)(anode->next);

  workPred=predicate_dup_without_context(pred);
  workPred->k=1;
  workPred->scontext[1]=MR_First(1,j, &(workPred->completionSet) );
  MR_complete_predicates(1,workPred);
  if (pred->k == 1) {
    maskSet=pred->scontext[1];
  } else {
    MR_projectTreeOntoSet(pred->tcontext,1,&maskSet);
  }
  pred->plainSet=set_dif(workPred->scontext[1],maskSet);
  predicate_free(workPred);
}

/*******************************************************************************/

static Tree *       suppressTree;
static int *        suppressChain;  /* element 0 not used */
static set *        suppressSets;
static Node *       suppressNode;
static int          suppressChainLength;
int                 MR_SuppressSearch=0;
static int          suppressSucceeded;
static Predicate *  suppressPredicate;

#ifdef __USE_PROTOS
int MR_isChain(Tree *t)
#else
int MR_isChain(t)
  Tree  *t;
#endif
{
  Tree  *u;

  for (u=t; u != NULL; u=u->down) {
    if (u->right != NULL) return 0;
  }
  return 1;
}

#ifdef __USE_PROTOS
int MR_suppressK_client(Tree *tree,int tokensInChain[])
#else
int MR_suppressK_client(tree,tokensInChain)
  Tree      *tree;
  int       tokensInChain[];
#endif
{
  int       i;
  set       *save_fset;
  int       save_ConstrainSearch;
  set       incomplete;
  Tree      *t;

  suppressSucceeded=0;  /* volatile */

  if (suppressSets == NULL) {
    suppressSets=(set *) calloc (CLL_k+1,sizeof(set));
    require (suppressSets != NULL,"MR_suppressK_client: suppressSets alloc");
  };

  for (suppressChainLength=1;
       tokensInChain[suppressChainLength+1] != 0;
       suppressChainLength++) {};

  require (suppressChainLength != 0,"MR_suppressK_client: chain empty");

  for (i=1 ; i <= suppressChainLength ; i++) {
    set_clr(suppressSets[i]);
    set_orel( (unsigned) tokensInChain[i],
                              &suppressSets[i]);
  };

  save_fset=fset;
  save_ConstrainSearch=ConstrainSearch;

  fset=suppressSets;

  MR_SuppressSearch=1;
  MR_AmbSourceSearch=1;
  MR_MaintainBackTrace=1;
  ConstrainSearch=1;

  maxk = suppressChainLength;

  incomplete=empty;
  t=NULL;

/***  constrain = &(fset[1]); ***/

  MR_setConstrainPointer(&(fset[1]));	/* MR18 */

  MR_pointerStackReset(&MR_BackTraceStack);

  TRAV(suppressNode,maxk,&incomplete,t);

  Tfree(t);

  require (set_nil(incomplete),"MR_suppressK_client TRAV incomplete");
  require (MR_BackTraceStack.count == 0,
            "MR_suppressK_client: MR_BackTraceStack.count != 0");
  set_free(incomplete);

  ConstrainSearch=save_ConstrainSearch;
  fset=save_fset;

  MR_AmbSourceSearch=0;
  MR_MaintainBackTrace=0;
  MR_SuppressSearch=0;
  return suppressSucceeded;
}

#ifdef __USE_PROTOS
Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[])
#else
Tree * MR_iterateOverTreeSuppressK(t,chain)
  Tree          *t;
  int           chain[];
#endif
{
  if (t == NULL) return NULL;
  t->right=MR_iterateOverTreeSuppressK(t->right,&chain[0]);
  chain[0]=t->token;
  if (t->down != NULL) {
    t->down=MR_iterateOverTreeSuppressK(t->down,&chain[1]);
    if (t->down == NULL) {
      Tree *u=t->right;
      t->right=NULL;
      Tfree(t);
      chain[0]=0;
      return u;
    };
  } else {
    MR_suppressK_client(suppressTree,suppressChain);
    if (suppressSucceeded) {
      Tree  *u=t->right;
      t->right=NULL;
      Tfree(t);
      chain[0]=0;
      return u;
    };
  };
  chain[0]=0;
  return t;
}

/* @@@ */

#ifdef __USE_PROTOS
Predicate * MR_suppressK(Node *j,Predicate *p)
#else
Predicate * MR_suppressK(j,p)
  Node          *j;
  Predicate     *p;
#endif
{
  Predicate     *result;
  int           guardPred=0;
  int           ampersandPred=0;
  Node          *nodePrime;

  if (! MRhoistingk) {
     return p;
  }

  if (! MRhoisting) return p;
  if (CLL_k == 1) return p;

  if (suppressChain == NULL) {
    suppressChain=(int *) calloc(CLL_k+2,sizeof(int));
    require (suppressChain != NULL,"MR_suppressK: can't allocate chain");
  }

  if (p == NULL) return NULL;

  if (j->ntype == nJunction) {
    nodePrime=(Node *) MR_junctionWithoutP2( (Junction *) j);
  } else {
    nodePrime=j;
  };

  p->down=MR_suppressK(j,p->down);
  p->right=MR_suppressK(j,p->right);
  if (p->down != NULL) {
    result=p;
    goto EXIT;
  };
  if (p->k == 1) {
    result=p;
    goto EXIT;
  };

  if (p->source != NULL) {
    if (p->source->guardpred != NULL) guardPred=1;
    if (p->source->ampersandPred != NULL) ampersandPred=1;
  }

  suppressPredicate=p;
  suppressNode=nodePrime;   /* was j*/

  suppressTree=p->tcontext;

  if (guardPred || ampersandPred) {
    p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
    if (p->tcontext == NULL) {
      predicate_free(p);
      result=NULL;
      goto EXIT;
    };
  } else {
    if (MR_isChain(p->tcontext)) {
      p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
      if (p->tcontext == NULL) {
        predicate_free(p);
        result=NULL;
        goto EXIT;
      };
    }
  }
  result=p;
EXIT:
  return result;
}

#ifdef __USE_PROTOS
void MR_suppressSearchReport(void)
#else
void MR_suppressSearchReport()
#endif
{
  int       i;
  Node      *p;
  TokNode   *tn;
  int       depth;
  set       setAnd;

  /* number of tokens in back trace stack matches length of chain */

  depth=0;
  for (i=0; i < MR_BackTraceStack.count ; i++) {
    p=(Node *) MR_BackTraceStack.data[i];
    if (p->ntype == nToken) depth++;
  };

  require (depth == suppressChainLength,"depth > suppressChainLength");

  /* token codes match chain */

  depth=0;
  for (i=0; i < MR_BackTraceStack.count ; i++) {
    p=(Node *) MR_BackTraceStack.data[i];
    if (p->ntype != nToken) continue;
    tn=(TokNode *) p;
    depth++;
    if (set_nil(tn->tset)) {
      require(set_el( (unsigned) tn->token,fset[depth]),
        "MR_suppressSearchReport: no match to #token in chain");
    } else {
      setAnd=set_and(fset[depth],tn->tset);
      require(!set_nil(setAnd),
        "MR_suppressSearchReport: no match to #token set in chain");
      set_free(setAnd);
    };
  };

  /* have a match - now remove it from the predicate */

  suppressSucceeded=1;

  if (suppressSucceeded) {
    fprintf(output,"\n");
    fprintf(output,"#if 0\n");
    fprintf(output,"\n");
    fprintf(output,"Part (or all) of predicate with depth > 1 suppressed by ");
        fprintf(output,"alternative without predicate\n\n");
    MR_dumpPred(suppressPredicate,1);
    fprintf(output,"The token sequence which is suppressed:");
    fprintf(output," (");
    for (i=1; i <= suppressChainLength; i++) {
      fprintf(output," %s",TerminalString(suppressChain[i]));
    };
    fprintf(output," )\n");
    fprintf(output,"The sequence of references which generate that sequence of tokens:\n\n");

    MR_backTraceDumpItemReset();

    for (i=0; i < MR_BackTraceStack.count ; i++) {
       MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
    };
    fprintf(output,"\n");
    fprintf(output,"#endif\n");
  }
}

#ifdef __USE_PROTOS
void MR_markCompromisedRule(Node *n)
#else
void MR_markCompromisedRule(n)
  Node *n;
#endif
{
  RuleEntry     *q;
  Node          *mark=NULL;
  Junction      *j;

  if (n->ntype == nRuleRef) {
    mark=(Node *) MR_ruleReferenced( (RuleRefNode *) n);
  } else if (n->ntype == nToken) {
    mark=n;
  } else if (n->ntype == nJunction) {
    j=(Junction *)n;
    switch (j->jtype) {
      case aOptBlk:
      case aLoopBlk:
      case RuleBlk:
      case EndRule:
      case aPlusBlk:
      case aLoopBegin:
        mark=n;
        break;
      default:
        break;
    };
  }

  if (mark == NULL) return;

  require (RulePtr != NULL,"RulePtr not initialized");

  q = (RuleEntry *) hash_get(Rname,mark->rname);
  require (q != NULL,"RuleEntry not found");
  set_orel(q->rulenum,&MR_CompromisedRules);
}

#ifdef __USE_PROTOS
void MR_alphaBetaTraceReport(void)
#else
void MR_alphaBetaTraceReport()
#endif
{
  int       i;

  if (! AlphaBetaTrace) return;

  MR_AlphaBetaMessageCount++;

  fprintf(output,"\n");
  fprintf(output,"#if 0\n");
  fprintf(output,"\n");
  fprintf(output,"Trace of references leading to attempt to compute the follow set of\n");
  fprintf(output,"alpha in an \"(alpha)? beta\" block. It is not possible for antlr to\n");
  fprintf(output,"compute this follow set because it is not known what part of beta has\n");
  fprintf(output,"already been matched by alpha and what part remains to be matched.\n");
  fprintf(output,"\n");
  fprintf(output,"Rules which make use of the incorrect follow set will also be incorrect\n");
  fprintf(output,"\n");

  MR_backTraceDumpItemReset();

  for (i=0; i < MR_BackTraceStack.count ; i++) {
     MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
     if (i < MR_BackTraceStack.count-1) {
        MR_markCompromisedRule( (Node *) MR_BackTraceStack.data[i]);
     };
  };
  fprintf(output,"\n");
  fprintf(output,"#endif\n");
}

#ifdef __USE_PROTOS
void MR_dumpRuleSet(set s)
#else
void MR_dumpRuleSet(s)
  set   s;
#endif
{
    unsigned    *cursor;
    unsigned    *origin=set_pdq(s);

    require(origin != NULL,"set_pdq failed");

    if (RulePtr == NULL) {
      fprintf(stderr,"RulePtr[] not yet initialized");
    } else {
      for (cursor=origin; *cursor != nil ; cursor++) {
/****   if (cursor != origin) fprintf(stderr,","); ****/
        fprintf(stderr,"    %s",RulePtr[*cursor]->rname);
        fprintf(stderr,"\n");
      };
      free( (char *) origin);
    };
}