mrhoist.c

来自「SRI international 发布的OAA框架软件」· C语言 代码 · 共 2,360 行 · 第 1/5 页

                       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.
 *