reorder.c

clips源代码

   /*******************************************************/
   /*      "C" Language Integrated Production System      */
   /*                                                     */
   /*             CLIPS Version 6.30  10/19/06            */
   /*                                                     */
   /*                    REORDER MODULE                   */
   /*******************************************************/

/*************************************************************/
/* Purpose: Provides routines necessary for converting the   */
/*   the LHS of a rule into an appropriate form suitable for */
/*   the KB 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:                                         */
/*                                                           */
/*      6.30: Added support for hashed alpha memories.       */
/*                                                           */
/*************************************************************/

#define _REORDER_SOURCE_

#include "setup.h"

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

#include <stdio.h>
#define _STDIO_INCLUDED_

#include "cstrnutl.h"
#include "envrnmnt.h"
#include "extnfunc.h"
#include "memalloc.h"
#include "pattern.h"
#include "prntutil.h"
#include "router.h"
#include "rulelhs.h"

#include "reorder.h"

struct variableReference
   { 
    struct symbolHashNode *name;
    int depth;
    struct variableReference *next;
   };
 
struct groupReference
   { 
    struct lhsParseNode *theGroup;
    int depth;
    struct groupReference *next;
   };
     
/***************************************/
/* LOCAL INTERNAL FUNCTION DEFINITIONS */
/***************************************/

   static struct lhsParseNode    *ReverseAndOr(void *,struct lhsParseNode *,struct lhsParseNode *,int);
   static struct lhsParseNode    *PerformReorder1(void *,struct lhsParseNode *,int *);
   static struct lhsParseNode    *PerformReorder2(void *,struct lhsParseNode *,int *);
   static struct lhsParseNode    *CompressCEs(void *,struct lhsParseNode *,int *);
   static void                    IncrementNandDepth(void *,struct lhsParseNode *,int);
   static struct lhsParseNode    *CreateInitialPattern(void *);
   static struct lhsParseNode    *ReorderDriver(void *,struct lhsParseNode *,int *,int);
   static struct lhsParseNode    *AddRemainingInitialPatterns(void *,struct lhsParseNode *);
   static void                    PrintNodes(void *,char *,struct lhsParseNode *);
   static struct lhsParseNode    *AssignPatternIndices(struct lhsParseNode *,short,int);
   static void                    PropagateIndexSlotPatternValues(struct lhsParseNode *,
                                                                  short,short,
                                                                  struct symbolHashNode *,
                                                                  short);
   static void                    PropagateJoinDepth(struct lhsParseNode *,short);
   static void                    PropagateNandDepth(struct lhsParseNode *,int,int);
   static void                    PropagateNandDepth2( struct lhsParseNode *,int,int);
   static intBool                 AddNandPatterns(void *,int,struct lhsParseNode *,struct lhsParseNode *,
                                                  struct lhsParseNode *,struct variableReference *,
                                                  struct groupReference *);
   static int                     VariableDepth(void *,struct variableReference *);
   static void                    InsertNandPatterns(void *,struct lhsParseNode *,struct lhsParseNode *,
                                                     struct lhsParseNode *,int);
   static void                    MarkExistsNands(struct lhsParseNode *);
   static intBool                 AddNandPatternsForTestCE(int,struct lhsParseNode *,struct variableReference *);
   
/********************************************/
/* ReorderPatterns: Reorders a group of CEs */     
/*   to accommodate KB Rete topology.       */
/********************************************/
globle struct lhsParseNode *ReorderPatterns(
  void *theEnv,
  struct lhsParseNode *theLHS,
  int *anyChange)
  {
   struct lhsParseNode *newLHS, *patternPtr, *tempLHS, *lastLHS;
   unsigned int whichCE;

   /*=============================================*/
   /* If the LHS of the rule was left unspecified */
   /* (e.g., (defrule x => ...)), then nothing    */
   /* more needs to be done.                      */
   /*=============================================*/

   if (theLHS == NULL) return(theLHS);
   
   /*===========================================================*/
   /* The LHS of a rule is enclosed within an implied "and" CE. */
   /*===========================================================*/

   newLHS = GetLHSParseNode(theEnv);
   newLHS->type = AND_CE;
   newLHS->right = theLHS;

   /*=======================================================*/
   /* Reorder the patterns to support the KB Rete topology. */
   /*=======================================================*/

   newLHS = ReorderDriver(theEnv,newLHS,anyChange,1);
   newLHS = ReorderDriver(theEnv,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(theEnv);
            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(theEnv);
      newLHS->type = AND_CE;
      newLHS->right = theLHS;
     }

   /*==============================================*/
   /* Add patterns if necessary to not/and groups. */
   /*==============================================*/

   if (newLHS->type == OR_CE)
     {
      for (theLHS = newLHS->right;
           theLHS != NULL;
           theLHS = theLHS->bottom)
        { 
         MarkExistsNands(theLHS->right);
         AddNandPatterns(theEnv,1,NULL,theLHS->right,theLHS->right,NULL,NULL); 
        }
     }
   else
     {
      MarkExistsNands(newLHS->right); 
      AddNandPatterns(theEnv,1,NULL,newLHS->right,newLHS->right,NULL,NULL);
     }

   /*=====================================================*/
   /* Add initial patterns where needed (such as before a */
   /* "test" CE or "not" CE which is the first CE within  */
   /* an "and" CE).                                       */
   /*=====================================================*/

   AddInitialPatterns(theEnv,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,1);
     }

   /*===========================*/
   /* Return the processed LHS. */
   /*===========================*/

   return(newLHS);
  }

/******************************************/
/* ReorderDriver: Reorders a group of CEs */
/*   to accommodate KB Rete topology.     */
/******************************************/
static struct lhsParseNode *ReorderDriver(
  void *theEnv,
  struct lhsParseNode *theLHS,
  int *anyChange,
  int pass)
  {
   struct lhsParseNode *argPtr;
   struct lhsParseNode *before, *save;
   int change, newChange;
   *anyChange = FALSE;

   /*===================================*/
   /* Continue processing the LHS until */
   /* no more changes have been made.   */
   /*===================================*/

   change = TRUE;
   while (change)
     {
      /*==================================*/
      /* No change yet on this iteration. */
      /*==================================*/

      change = 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(theEnv,theLHS,&newChange);
         else theLHS = PerformReorder2(theEnv,theLHS,&newChange);

         if (newChange)
           {
            *anyChange = TRUE;
            change = TRUE;
           }

         theLHS = CompressCEs(theEnv,theLHS,&newChange);

         if (newChange)
           {
            *anyChange = TRUE;
            change = 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(theEnv,argPtr,&newChange,pass);
               theLHS->right->bottom = save;
               before = theLHS->right;
              }
            else
              {
               argPtr->bottom = NULL;
               before->bottom = ReorderDriver(theEnv,argPtr,&newChange,pass);
               before->bottom->bottom = save;
               before = before->bottom;
              }

            if (newChange)
              {
               *anyChange = TRUE;
               change = TRUE;
              }
           }
         else
           { before = argPtr; }

         /*====================================*/
         /* Move on to the next CE to reorder. */
         /*====================================*/

         argPtr = save;
        }
     }

   /*===========================*/
   /* Return the reordered LHS. */
   /*===========================*/

   return(theLHS);
  }

/*************************************************************/
/* MarkExistsNands:                */
/*************************************************************/
static void MarkExistsNands(
  struct lhsParseNode *theLHS)
  {      
   int currentDepth = 1;
   struct lhsParseNode *tmpLHS;
    
   while (theLHS != NULL)
     {
      if (IsExistsSubjoin(theLHS,currentDepth))
        {
         theLHS->existsNand = TRUE;
         
         for (tmpLHS = theLHS;
              tmpLHS != NULL;
              tmpLHS = tmpLHS->bottom)
           {
            tmpLHS->beginNandDepth--;
            if (tmpLHS->endNandDepth <= currentDepth)
              { break; }
            else
              { tmpLHS->endNandDepth--; }
           }
        }