reorder.c

NASA 开发使用的一个专家系统

   /*******************************************************/
   /*      "C" Language Integrated Production System      */
   /*                                                     */
   /*             CLIPS Version 6.05  04/09/97            */
   /*                                                     */
   /*                    REORDER MODULE                   */
   /*******************************************************/

/*************************************************************/
/* Purpose: Provides routines necessary for converting the   */
/*   the LHS of a rule into an appropriate form suitable for */
/*   the CLIPS Rete topology. This includes transforming the */
/*   LHS so there is at most one "or" CE (and this is the    */
/*   first CE of the LHS if it is used), adding initial      */
/*   patterns to the LHS (if no LHS is specified or a "test" */
/*   or "not" CE is the first pattern within an "and" CE),   */
/*   removing redundant CEs, and determining appropriate     */
/*   information on nesting for implementing joins from the  */
/*   right.                                                  */
/*                                                           */
/* Principal Programmer(s):                                  */
/*      Gary D. Riley                                        */
/*                                                           */
/* Contributing Programmer(s):                               */
/*                                                           */
/* Revision History:                                         */
/*                                                           */
/*************************************************************/

#define _REORDER_SOURCE_

#include "setup.h"

#if (! RUN_TIME) && (! BLOAD_ONLY) && DEFRULE_CONSTRUCT

#include <stdio.h>
#define _CLIPS_STDIO_

#include "clipsmem.h"
#include "cstrnutl.h"
#include "pattern.h"
#include "extnfunc.h"
#include "rulelhs.h"
#include "prntutil.h"
#include "router.h"

#include "reorder.h"

#if ANSI_COMPILER
   static struct lhsParseNode    *ReverseAndOr(struct lhsParseNode *,struct lhsParseNode *,int);
   static struct lhsParseNode    *PerformReorder1(struct lhsParseNode *,int *);
   static struct lhsParseNode    *PerformReorder2(struct lhsParseNode *,int *);
   static struct lhsParseNode    *CompressCEs(struct lhsParseNode *,int *);
   static VOID                    IncrementNandDepth(struct lhsParseNode *,int);
   static struct lhsParseNode    *CreateInitialPattern(struct patternParser *);
   static struct lhsParseNode    *ReorderDriver(struct lhsParseNode *,int *,int);
   static VOID                    AddRemainingInitialPatterns(struct lhsParseNode *,struct patternParser *);
   static VOID                    PrintNodes(char *,struct lhsParseNode *);
   static struct lhsParseNode    *AssignPatternIndices(struct lhsParseNode *,int);
   static VOID                    PropagateIndexSlotPatternValues(struct lhsParseNode *,
                                                                  int,int,
                                                                  struct symbolHashNode *,
                                                                  int);
#else
   static struct lhsParseNode    *ReverseAndOr();
   static struct lhsParseNode    *PerformReorder1();
   static struct lhsParseNode    *PerformReorder2();
   static struct lhsParseNode    *CompressCEs();
   static VOID                    IncrementNandDepth();
   static struct lhsParseNode    *CreateInitialPattern();
   static struct lhsParseNode    *ReorderDriver();
   static VOID                    AddRemainingInitialPatterns();
   static VOID                    PrintNodes();
   static struct lhsParseNode    *AssignPatternIndices();
   static VOID                    PropagateIndexSlotPatternValues();
#endif

/********************************************/
/* ReorderPatterns: Reorders a group of CEs */
/*   to accommodate CLIPS Rete topology.    */
/********************************************/
globle struct lhsParseNode *ReorderPatterns(theLHS,anyChange)
  struct lhsParseNode *theLHS;
  int *anyChange;
  {    
   struct lhsParseNode *newLHS, *patternPtr, *tempLHS, *lastLHS;
   unsigned int whichCE;
   
   /*===========================================================*/
   /* The LHS of a rule is enclosed within an implied "and" CE. */
   /*===========================================================*/
   
   newLHS = GetLHSParseNode();
   newLHS->type = AND_CE;
   
   /*=============================================*/
   /* If the LHS of the rule was left unspecified */
   /* (e.g., (defrule x => ...)), then add an     */
   /* initial fact or instance pattern to the LHS */
   /* of the rule. Otherwise, attach the user     */
   /* specified LHS to the implied "and" Ce.      */
   /*=============================================*/
   
   if (theLHS == NULL) newLHS->right = CreateInitialPattern(NULL);
   else newLHS->right = theLHS;

   /*==========================================================*/
   /* Reorder the patterns to support the CLIPS Rete topology. */
   /*==========================================================*/
   
   newLHS = ReorderDriver(newLHS,anyChange,1);
   newLHS = ReorderDriver(newLHS,anyChange,2);

   /*===========================================*/
   /* The top level and CE may have disappeared */
   /* as a result of pattern compression.       */
   /*===========================================*/
   
   if (newLHS->type == OR_CE)
     {
      for (tempLHS = newLHS->right, lastLHS = NULL;
           tempLHS != NULL;
           lastLHS = tempLHS, tempLHS = tempLHS->bottom)
        {
         if (tempLHS->type != AND_CE)
           {
            theLHS = GetLHSParseNode();
            theLHS->type = AND_CE;
            theLHS->right = tempLHS;
            theLHS->bottom = tempLHS->bottom;
            tempLHS->bottom = NULL; 
            if (lastLHS == NULL)
              { newLHS->right = theLHS; }
            else
              { lastLHS->bottom = theLHS; }
            tempLHS = theLHS;
           } 
        }
     } 
   else if (newLHS->type != AND_CE)  
     {
      theLHS = newLHS;
      newLHS = GetLHSParseNode();
      newLHS->type = AND_CE;
      newLHS->right = theLHS;
     }
   
   /*=====================================================*/
   /* Add initial patterns where needed (such as before a */
   /* "test" CE or "not" CE which is the first CE within  */
   /* an "and" CE).                                       */
   /*=====================================================*/
   
   AddInitialPatterns(newLHS);
    
   /*===========================================================*/
   /* Number the user specified patterns. Patterns added while  */
   /* analyzing the rule (such as placing initial-fact patterns */
   /* before not CEs) are not numbered so that there is no      */
   /* confusion when an error message refers to a CE. Also      */
   /* propagate field and slot values throughout each pattern.  */
   /*===========================================================*/
   
   if (newLHS->type == OR_CE) theLHS = newLHS->right;
   else theLHS = newLHS;
   
   for (;
        theLHS != NULL;
        theLHS = theLHS->bottom)
     {
      whichCE = 1;
      for (patternPtr = theLHS->right;
           patternPtr != NULL;
           patternPtr = patternPtr->bottom)
        { if (patternPtr->userCE) patternPtr->whichCE = whichCE++; }
        
      AssignPatternIndices(theLHS->right,1);
     }
    
   /*===========================*/
   /* Return the processed LHS. */
   /*===========================*/

   return(newLHS);
  }
  
/******************************************/
/* ReorderDriver: Reorders a group of CEs */
/*   to accommodate CLIPS Rete topology.  */
/******************************************/
static struct lhsParseNode *ReorderDriver(theLHS,anyChange,pass)
  struct lhsParseNode *theLHS;
  int *anyChange;
  int pass;
  {
   struct lhsParseNode *argPtr;
   struct lhsParseNode *before, *save;
   int change, newChange;
   *anyChange = CLIPS_FALSE;
   
   /*===================================*/
   /* Continue processing the LHS until */
   /* no more changes have been made.   */
   /*===================================*/
   
   change = CLIPS_TRUE;
   while (change)
     {
      /*==================================*/
      /* No change yet on this iteration. */
      /*==================================*/
      
      change = CLIPS_FALSE;
      
      /*=======================================*/
      /* Reorder the current level of the LHS. */
      /*=======================================*/
      
      if ((theLHS->type == AND_CE) ||
          (theLHS->type == NOT_CE) ||
          (theLHS->type == OR_CE))
        {   
         if (pass == 1) theLHS = PerformReorder1(theLHS,&newChange);
         else theLHS = PerformReorder2(theLHS,&newChange);
         
         if (newChange) 
           {
            *anyChange = CLIPS_TRUE;
            change = CLIPS_TRUE;
           }
         
         theLHS = CompressCEs(theLHS,&newChange);
         
         if (newChange) 
           {
            *anyChange = CLIPS_TRUE;
            change = CLIPS_TRUE;
           }
        }
              
      /*=====================================================*/
      /* Recursively reorder CEs at lower levels in the LHS. */
      /*=====================================================*/

      before = NULL;
      argPtr = theLHS->right;

      while (argPtr != NULL)
        {
         /*==================================*/
         /* Remember the next CE to reorder. */
         /*==================================*/
         
         save = argPtr->bottom;
         
         /*============================================*/
         /* Reorder the current CE at the lower level. */
         /*============================================*/
         
         if ((argPtr->type == AND_CE) ||
             (argPtr->type == NOT_CE) ||
             (argPtr->type == OR_CE))
           {
            if (before == NULL)
              {
               argPtr->bottom = NULL;
               theLHS->right = ReorderDriver(argPtr,&newChange,pass);
               theLHS->right->bottom = save;
               before = theLHS->right;
              }
            else
              {
               argPtr->bottom = NULL;
               before->bottom = ReorderDriver(argPtr,&newChange,pass);
               before->bottom->bottom = save;
               before = before->bottom;
              }
             
            if (newChange) 
              {
               *anyChange = CLIPS_TRUE;
               change = CLIPS_TRUE;
              }
           }
         else
           { before = argPtr; }
           
         /*====================================*/
         /* Move on to the next CE to reorder. */
         /*====================================*/
         
         argPtr = save;
        }
     }
     
   /*===========================*/
   /* Return the reordered LHS. */
   /*===========================*/
   
   return(theLHS);
  }
  
/****************************************************************/
/* AddInitialPatterns: Add initial patterns to CEs where needed */
/*   (such as before a "test" CE or "not" CE which is the first */
/*   CE within an "and" CE).                                    */
/****************************************************************/
globle VOID AddInitialPatterns(theLHS)
  struct lhsParseNode *theLHS;
  {
   struct lhsParseNode *thePattern;
   struct patternParser *lastType;
   
   /*====================================================*/
   /* If there are multiple disjuncts for the rule, then */
   /* add initial patterns to each disjunct separately.  */
   /*====================================================*/
   
   if (theLHS->type == OR_CE)
     {
      for (thePattern = theLHS->right; 
           thePattern != NULL; 
           thePattern = thePattern->bottom)
        { AddInitialPatterns(thePattern); }
      
      return;
     }
     
   /*======================================================*/
   /* Determine what the default pattern type for the rule */
   /* should be (in case the rule begins with a test CE).  */
   /* The default pattern type is the type of the data     */
   /* entity associated with the first pattern CE found in */
   /* the LHS of the rule.                                 */
   /*======================================================*/
   
   for (lastType = NULL, thePattern = theLHS->right;
        thePattern != NULL;
        thePattern = thePattern->bottom)
     {
      if (thePattern->type == PATTERN_CE)
        { 
         lastType = thePattern->patternType;
         break;
        }
     }
        
   /*===================================================*/
   /* Add an initial pattern to the first CE of a rule  */
   /* if the CE is a "test" CE, "not" CE or a join from */
   /* the right.                                        */ 
   /*===================================================*/
   
   if ((theLHS->right->negated) ||
       (theLHS->right->type == TEST_CE) ||
       (theLHS->right->beginNandDepth > 1))
     {
      thePattern = CreateInitialPattern(lastType);
        
      thePattern->logical = (theLHS->logical || theLHS->right->logical);
      thePattern->bottom = theLHS->right;
      theLHS->right = thePattern;
     }
     
   /*================================*/
   /* Handle the remaining patterns. */
   /*================================*/
      
   AddRemainingInitialPatterns(theLHS->right,lastType);
  }
  
/***********************************************************/
/* PerformReorder1: Reorders a group of CEs to accommodate */
/*   CLIPS Rete topology. The first pass of this function  */
/*   transforms or CEs into equivalent forms.              */
/***********************************************************/
static struct lhsParseNode *PerformReorder1(theLHS,newChange)
  struct lhsParseNode *theLHS;
  int *newChange;
  {
   struct lhsParseNode *argPtr, *lastArg, *nextArg;
   struct lhsParseNode *tempArg, *newNode;
   int count;
   int change;
     
   /*======================================================*/
   /* Loop through the CEs as long as changes can be made. */
   /*======================================================*/
   
   change = CLIPS_TRUE;
   *newChange = CLIPS_FALSE;