inherpsr.c

clips源代码

         if (pop->cls == supers->classArray[i])
           break;
         poprv = pop;
        }
      if (pop == NULL)
        {
         pop = get_struct(theEnv,partialOrder);
         pop->cls = supers->classArray[i];
         pop->nxt = NULL;
         pop->suc = NULL;
         pop->pre = 0;
         if (poprv == NULL)
           po_table = pop;
         else
           poprv->nxt = pop;

         /* =============================================================
            Recursively append all its superclasses immediately after it.
            This order will allow us to preserve the "family" heuristic
            in the precedence list.
            ============================================================= */
         po_table = InitializePartialOrderTable(theEnv,po_table,
                     &supers->classArray[i]->directSuperclasses);
        }
     }
   return(po_table);
  }

/***********************************************************************************
  NAME         : RecordPartialOrders
  DESCRIPTION  : Given a predecessor class and a list of successor classes, this
                 function enters a number of partial orders into the table equaling
                 the number of successor classes.
  INPUTS       : 1) The partial order table
                 2) The predecessor class
                 3) An array of successor classes
                 4) A starting index for the successor classes
  RETURNS      : The top of sequence table
  SIDE EFFECTS : The sequence table is built, e.g.:

                 CLASS1 < CLASS2 , CLASS3

                 would be recorded as:

                 PO_TABLE -> NXT     -> NXT       -> NXT ->   <NIL>
                             <CLASS1>   <CLASS2>     <CLASS3>
                             SUC        SUC          SUC
                              |          |            |
                              V          V            V
                             <CLASS2>   <NIL>        <NIL>
                             NXT
                              |
                              V
                             <CLASS3>
                             NXT
                              |
                              V
                             <NIL>

                 The predecessor counts would be 0, 1 and 1 for CLASS1, CLASS2
                 and CLASS3 respectively.
  NOTES        : None
 ***********************************************************************************/
static void RecordPartialOrders(
  void *theEnv,
  PARTIAL_ORDER *po_table,
  DEFCLASS *cls,
  PACKED_CLASS_LINKS *successors,
  long starti)
  {
   register PARTIAL_ORDER *clspo;
   register SUCCESSOR *stmp;

   clspo = FindPartialOrder(po_table,cls);
   while (starti < successors->classCount)
     {
      stmp = get_struct(theEnv,successor);
      stmp->po = FindPartialOrder(po_table,successors->classArray[starti]);
      stmp->nxt = clspo->suc;
      clspo->suc = stmp;
      stmp->po->pre++;
      starti++;
     }
  }

/***************************************************
  NAME         : FindPartialOrder
  DESCRIPTION  : Finds a partial order node
  INPUTS       : 1) The partial order table
                 2) The class to look up
  RETURNS      : The partial order node address
  SIDE EFFECTS : None
  NOTES        : None
 ***************************************************/
static PARTIAL_ORDER *FindPartialOrder(
  PARTIAL_ORDER *po_table,
  DEFCLASS *cls)
  {
   while (po_table != NULL)
     {
      if (po_table->cls == cls)
        break;
      po_table = po_table->nxt;
     }
   return(po_table);
  }

/**************************************************************************
  NAME         : PrintPartialOrderLoop
  DESCRIPTION  : This routine prints a conflicting loop (there may be more
                 than one) in the given sequence table of partial orders.

                 The algorithm works as follows:

                 Given the following class definitions,

                 (defclass A (is-a USER))
                 (defclass B (is-a USER))
                 (defclass C (is-a A B))
                 (defclass D (is-a B A))
                 (defclass E (is-a C D))

                 the partial order table will look as follows after as many
                 classes as possible have been entered onto the precedence
                 list:

                                      A      USER    OBJECT   B
                 Predecessor Count    1       2        1      1
                 Successor List     B,USER  OBJECT   <NIL>   A,USER

                 Construct a new table where each class is linked to one
                 of its predecessors.  For the example above one would be:

                 Class:            A    USER    OBJECT    B
                 Predecessor:      B      A      USER     A

                 This table is actually implemnted using the original
                 partial order table (see the code below for specifics).
                 Now using this table, start with the first node, and visit
                 successive nodes by following the predecessor links.  Mark
                 each node as "visited".  When a previously visited node is
                 encountered, the loop has been found.

                 In the case above, we start with A, goto B and then goto A
                 again which we have already seen.  So starting from where
                 we found the loop (A) we follow the links again, printing
                 the nodes as we go, until we're back where we started:
                 A B A.  Notice that this loop reflects the Rule 2 conflicts
                 between Class C and Class D in Class E's precedence list.

  INPUTS       : The remaining partial order table of conflicting partial
                 orders
  RETURNS      : Nothing useful
  SIDE EFFECTS : The predecessor counts and successor lists are modified to
                 implement the loop detection.
  NOTES        : This algorithm is adopted from one  given in Donald
                 Knuth's The Art of Computer Programming - Vol. I
                 (Fundamental Algorithms).
 **************************************************************************/
static void PrintPartialOrderLoop(
  void *theEnv,
  PARTIAL_ORDER *po_table)
  {
   register PARTIAL_ORDER *pop1,*pop2;
   SUCCESSOR *prc,*stmp;

   /* ====================================================
      Set the predecessor count of every node to 0 so that
      this field can be used as a marker
      ==================================================== */
   for (pop1 = po_table ; pop1 != NULL ; pop1 = pop1->nxt)
     pop1->pre = 0;

   /* =======================================================
      Mark each node in the partial order table with one of
      its predecessors.  If the class has already been marked
      (predecessor count > 0), don't bother.  This is
      accomplished by adding a node to the front of its
      successors' successor lists.

      When the process is finished, all nodes will have one
      predecessor chained to them by their 'suc' field.
      (If any nodes had had no predecessors, they would not
       still be in the table.)
      ======================================================= */
   for (pop1 = po_table ; pop1 != NULL ; pop1 = pop1->nxt)
     {
      if (pop1->pre == 0)
        {
         prc = pop1->suc;
         pop1->suc = NULL;
        }
      else
        {
         prc = pop1->suc->nxt;
         pop1->suc->nxt = NULL;
        }
      while (prc != NULL)
        {
         pop2 = FindPartialOrder(po_table,prc->po->cls);
         if (pop2->pre == 0)
           {
            stmp = get_struct(theEnv,successor);
            stmp->po = pop1;
            stmp->nxt = pop2->suc;
            pop2->suc = stmp;
            pop2->pre = 1;
           }
         stmp = prc;
         prc = prc->nxt;
         rtn_struct(theEnv,successor,stmp);
        }
     }

   /* =================================================
      Set the predecessor count of every node back to 0
      so that this field can be used as a marker again
      ================================================= */
   for (pop1 = po_table ; pop1 != NULL ; pop1 = pop1->nxt)
     pop1->pre = 0;

   /* =========================================================
      Now start with the first node in the partial order table,
      and follow the predecessor links, marking the
      nodes as they are visited.  When we reach a node
      we have been before, we have found a loop!
      Follow all the marked nodes again  starting from the
      CURRENT position to print the loop.
      ========================================================= */
   pop1 = po_table;
   while (pop1->pre == 0)
     {
      pop1->pre = 1;
      pop1 = pop1->suc->po;
     }

   EnvPrintRouter(theEnv,WERROR,"Precedence loop in superclasses:");
   while (pop1->pre == 1)
     {
      EnvPrintRouter(theEnv,WERROR," ");
      PrintClassName(theEnv,WERROR,pop1->cls,FALSE);
      pop1->pre = 0;
      pop1 = pop1->suc->po;
     }
   EnvPrintRouter(theEnv,WERROR," ");
   PrintClassName(theEnv,WERROR,pop1->cls,TRUE);
  }

/***************************************************
  NAME         : PrintClassLinks
  DESCRIPTION  : Displays the names of classes in
                 a list with a title
  INPUTS       : 1) The logical name of the output
                 2) Title string
                 3) List of class links
  RETURNS      : Nothing useful
  SIDE EFFECTS : None
  NOTES        : None
 ***************************************************/
static void PrintClassLinks(
  void *theEnv,
  char *logicalName,
  char *title,
  CLASS_LINK *clink)
  {
   if (title != NULL)
     EnvPrintRouter(theEnv,logicalName,title);
   while (clink != NULL)
     {
      EnvPrintRouter(theEnv,logicalName," ");
      PrintClassName(theEnv,logicalName,clink->cls,FALSE);
      clink = clink->nxt;
     }
   EnvPrintRouter(theEnv,logicalName,"\n");
  }

#endif