pattern.c

clips源代码

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

/*************************************************************/
/* Purpose: Provides the mechanism for recognizing and       */
/*   parsing the various types of patterns that can be used  */
/*   in the LHS of a rule. In version 6.0, the only pattern  */
/*   types provided are for deftemplate and instance         */
/*   patterns.                                               */
/*                                                           */
/* Principal Programmer(s):                                  */
/*      Gary D. Riley                                        */
/*                                                           */
/* Contributing Programmer(s):                               */
/*                                                           */
/* Revision History:                                         */
/*                                                           */
/*      6.24: Renamed BOOLEAN macro type to intBool.         */
/*                                                           */
/*      6.30: Added support for hashed alpha memories.       */
/*                                                           */
/*************************************************************/

#define _PATTERN_SOURCE_

#include "setup.h"

#include <stdio.h>
#define _STDIO_INCLUDED_
#include <stdlib.h>

#if DEFRULE_CONSTRUCT

#include "constant.h"
#include "constrnt.h"
#include "cstrnchk.h"
#include "cstrnutl.h"
#include "envrnmnt.h"
#include "exprnpsr.h"
#include "match.h"
#include "memalloc.h"
#include "reteutil.h"
#include "router.h"
#include "rulecmp.h"

#include "pattern.h"

/***************************************/
/* LOCAL INTERNAL FUNCTION DEFINITIONS */
/***************************************/

#if (! RUN_TIME) && (! BLOAD_ONLY)
   static struct lhsParseNode            *ConjuctiveRestrictionParse(void *,char *,struct token *,int *);
   static struct lhsParseNode            *LiteralRestrictionParse(void *,char *,struct token *,int *);
   static int                             CheckForVariableMixing(void *,struct lhsParseNode *);
   static void                            TallyFieldTypes(struct lhsParseNode *);
#endif
   static void                            DeallocatePatternData(void *);
   static struct patternNodeHashEntry   **CreatePatternHashTable(void *,unsigned long);
   
/*****************************************************************************/
/* InitializePatterns: Initializes the global data associated with patterns. */
/*****************************************************************************/
globle void InitializePatterns(
  void *theEnv)
  {   
   AllocateEnvironmentData(theEnv,PATTERN_DATA,sizeof(struct patternData),DeallocatePatternData);
   PatternData(theEnv)->NextPosition = 1;
   PatternData(theEnv)->PatternHashTable = CreatePatternHashTable(theEnv,SIZE_PATTERN_HASH);
   PatternData(theEnv)->PatternHashTableSize = SIZE_PATTERN_HASH;
  }

/*******************************************************************/
/* CreatePatternHashTable: Creates and initializes a fact hash table. */
/*******************************************************************/
static struct patternNodeHashEntry **CreatePatternHashTable(
   void *theEnv,
   unsigned long tableSize)
   {
    unsigned long i;
    struct patternNodeHashEntry **theTable;

    theTable = (struct patternNodeHashEntry **)
               gm3(theEnv,sizeof (struct patternNodeHashEntry *) * tableSize);

    if (theTable == NULL) EnvExitRouter(theEnv,EXIT_FAILURE);
    
    for (i = 0; i < tableSize; i++) theTable[i] = NULL;
    
    return(theTable);
   }
       
/**************************************************/
/* DeallocatePatternData: Deallocates environment */
/*    data for rule pattern registration.         */
/**************************************************/
static void DeallocatePatternData(
  void *theEnv)
  {
   struct reservedSymbol *tmpRSPtr, *nextRSPtr;
   struct patternParser *tmpPPPtr, *nextPPPtr;
   struct patternNodeHashEntry *tmpPNEPtr, *nextPNEPtr;
   unsigned long i;

   tmpRSPtr = PatternData(theEnv)->ListOfReservedPatternSymbols;
   while (tmpRSPtr != NULL)
     {
      nextRSPtr = tmpRSPtr->next;
      rtn_struct(theEnv,reservedSymbol,tmpRSPtr);
      tmpRSPtr = nextRSPtr;
     }
     
   tmpPPPtr = PatternData(theEnv)->ListOfPatternParsers;
   while (tmpPPPtr != NULL)
     {
      nextPPPtr = tmpPPPtr->next;
      rtn_struct(theEnv,patternParser,tmpPPPtr);
      tmpPPPtr = nextPPPtr;
     }
   
   for (i = 0; i < PatternData(theEnv)->PatternHashTableSize; i++) 
     {
      tmpPNEPtr = PatternData(theEnv)->PatternHashTable[i];
      
      while (tmpPNEPtr != NULL)
        {
         nextPNEPtr = tmpPNEPtr->next;
         rtn_struct(theEnv,patternNodeHashEntry,tmpPNEPtr);
         tmpPNEPtr = nextPNEPtr;
        }
     }
  
   rm3(theEnv,PatternData(theEnv)->PatternHashTable,
       sizeof(struct patternNodeHashEntry *) * PatternData(theEnv)->PatternHashTableSize);
  }

/******************************************************************************/
/* AddHashedPatternNode: Adds a pattern node entry to the pattern hash table. */
/******************************************************************************/
globle void AddHashedPatternNode(
  void *theEnv,
  void *parent,
  void *child,
  unsigned short keyType,
  void *keyValue)
  {
   unsigned long hashValue;
   struct patternNodeHashEntry *newhash, *temp;

   hashValue = GetAtomicHashValue(keyType,keyValue,1) + GetAtomicHashValue(EXTERNAL_ADDRESS,parent,1);

   newhash = get_struct(theEnv,patternNodeHashEntry);
   newhash->parent = parent;
   newhash->child = child;
   newhash->type = keyType;
   newhash->value = keyValue;

   hashValue = (hashValue % PatternData(theEnv)->PatternHashTableSize);
   
   temp = PatternData(theEnv)->PatternHashTable[hashValue];
   PatternData(theEnv)->PatternHashTable[hashValue] = newhash;
   newhash->next = temp;
  }

/***************************************************/
/* RemoveHashedPatternNode: Removes a pattern node */
/*   entry from the pattern node hash table.       */
/***************************************************/
globle intBool RemoveHashedPatternNode(
  void *theEnv,
  void *parent,
  void *child,
  unsigned short keyType,
  void *keyValue)
  {
   unsigned long hashValue;
   struct patternNodeHashEntry *hptr, *prev;

   hashValue = GetAtomicHashValue(keyType,keyValue,1) + GetAtomicHashValue(EXTERNAL_ADDRESS,parent,1);
   hashValue = (hashValue % PatternData(theEnv)->PatternHashTableSize);

   for (hptr = PatternData(theEnv)->PatternHashTable[hashValue], prev = NULL;
        hptr != NULL;
        hptr = hptr->next)
     {
      if (hptr->child == child)
        {
         if (prev == NULL)
           {
            PatternData(theEnv)->PatternHashTable[hashValue] = hptr->next;
            rtn_struct(theEnv,patternNodeHashEntry,hptr);
            return(1);
           }
         else
           {
            prev->next = hptr->next;
            rtn_struct(theEnv,patternNodeHashEntry,hptr);
            return(1);
           }
        }
      prev = hptr;
     }

   return(0);
  }

/***********************************************/
/* FindHashedPatternNode: Finds a pattern node */
/*   entry in the pattern node hash table.     */
/***********************************************/
globle void *FindHashedPatternNode(
  void *theEnv,
  void *parent,
  unsigned short keyType,
  void *keyValue)
  {
   unsigned long hashValue;
   struct patternNodeHashEntry *hptr;

   hashValue = GetAtomicHashValue(keyType,keyValue,1) + GetAtomicHashValue(EXTERNAL_ADDRESS,parent,1);
   hashValue = (hashValue % PatternData(theEnv)->PatternHashTableSize);

   for (hptr = PatternData(theEnv)->PatternHashTable[hashValue];
        hptr != NULL;
        hptr = hptr->next)
     {
      if ((hptr->parent == parent) &&
          (keyType == hptr->type) &&
          (keyValue == hptr->value))
        { return(hptr->child); }
     }

   return(NULL);
  }
  
/******************************************************************/
/* AddReservedPatternSymbol: Adds a symbol to the list of symbols */
/*  that are restricted for use in patterns. For example, the     */
/*  deftemplate construct cannot use the symbol "object", since   */
/*  this needs to be reserved for object patterns. Some symbols,  */
/*  such as "exists" are completely reserved and can not be used  */
/*  to start any type of pattern CE.                              */
/******************************************************************/
void AddReservedPatternSymbol(
  void *theEnv,
  char *theSymbol,
  char *reservedBy)
  {
   struct reservedSymbol *newSymbol;

   newSymbol = get_struct(theEnv,reservedSymbol);
   newSymbol->theSymbol = theSymbol;
   newSymbol->reservedBy = reservedBy;
   newSymbol->next = PatternData(theEnv)->ListOfReservedPatternSymbols;
   PatternData(theEnv)->ListOfReservedPatternSymbols = newSymbol;
  }

/******************************************************************/
/* ReservedPatternSymbol: Returns TRUE if the specified symbol is */
/*   a reserved pattern symbol, otherwise FALSE is returned. If   */
/*   the construct which is trying to use the symbol is the same  */
/*   construct that reserved the symbol, then FALSE is returned.  */
/******************************************************************/
intBool ReservedPatternSymbol(
  void *theEnv,
  char *theSymbol,
  char *checkedBy)
  {
   struct reservedSymbol *currentSymbol;

   for (currentSymbol = PatternData(theEnv)->ListOfReservedPatternSymbols;
        currentSymbol != NULL;
        currentSymbol = currentSymbol->next)
     {
      if (strcmp(theSymbol,currentSymbol->theSymbol) == 0)
        {
         if ((currentSymbol->reservedBy == NULL) || (checkedBy ==  NULL))
           { return(TRUE); }

         if (strcmp(checkedBy,currentSymbol->reservedBy) == 0) return(FALSE);

         return(TRUE);
        }
     }

   return(FALSE);
  }

/********************************************************/
/* ReservedPatternSymbolErrorMsg: Generic error message */
/*   for attempting to use a reserved pattern symbol.   */
/********************************************************/
void ReservedPatternSymbolErrorMsg(
  void *theEnv,
  char *theSymbol,
  char *usedFor)
  {
   PrintErrorID(theEnv,"PATTERN",1,TRUE);
   EnvPrintRouter(theEnv,WERROR,"The symbol ");
   EnvPrintRouter(theEnv,WERROR,theSymbol);
   EnvPrintRouter(theEnv,WERROR," has special meaning\n");
   EnvPrintRouter(theEnv,WERROR,"and may not be used as ");
   EnvPrintRouter(theEnv,WERROR,usedFor);
   EnvPrintRouter(theEnv,WERROR,".\n");
  }

/************************************************************/
/* GetNextEntity: Utility routine for accessing all of the  */
/*   data entities that can match patterns. Currently facts */
/*   and instances are the only data entities available.    */
/************************************************************/
globle void GetNextPatternEntity(
  void *theEnv,
  struct patternParser **theParser,
  struct patternEntity **theEntity)
  {

   /*=============================================================*/
   /* If the current parser is NULL, then we want to retrieve the */
   /* very first data entity. The traversal of entities is done   */
   /* by entity type (e.g. all facts are traversed followed by    */
   /* all instances). To get the first entity type to traverse,   */
   /* the current parser is set to the first parser on the list   */
   /* of pattern parsers.                                         */
   /*=============================================================*/

   if (*theParser == NULL)
     {
      *theParser = PatternData(theEnv)->ListOfPatternParsers;
      *theEntity = NULL;
     }

   /*================================================================*/
   /* Otherwise try to retrieve the next entity following the entity */
   /* returned by the last call to GetNextEntity. If that entity was */
   /* the last of its data type, then move on to the next pattern    */
   /* parser, otherwise return that entity as the next one.          */
   /*================================================================*/

   else if (theEntity != NULL)
     {
      *theEntity = (struct patternEntity *)
                   (*(*theParser)->entityType->base.getNextFunction)(theEnv,*theEntity);

      if ((*theEntity) != NULL) return;

      *theParser = (*theParser)->next;
     }

   /*===============================================================*/
   /* Otherwise, we encountered a situation which should not occur. */
   /* Once a NULL entity is returned from GetNextEntity, it should  */
   /* not be passed back to GetNextEntity.                          */
   /*===============================================================*/

   else
     {
      SystemError(theEnv,"PATTERN",1);
      EnvExitRouter(theEnv,EXIT_FAILURE);
     }

   /*================================================*/
   /* Keep looping through the lists of entities and */
   /* pattern parsers until an entity is found.      */
   /*================================================*/

   while ((*theEntity == NULL) && (*theParser != NULL))
     {
      *theEntity = (struct patternEntity *)
                   (*(*theParser)->entityType->base.getNextFunction)(theEnv,*theEntity);

      if (*theEntity != NULL) return;

      *theParser = (*theParser)->next;
     }

   return;
  }

/**************************************************************/
/* DetachPattern: Detaches a pattern from the pattern network */
/*   by calling the appropriate function for the data type    */
/*   associated with the pattern.                             */
/**************************************************************/
void DetachPattern(
  void *theEnv,
  int rhsType,
  struct patternNodeHeader *theHeader)
  {
   if (rhsType == 0) return;
   
   if (PatternData(theEnv)->PatternParserArray[rhsType-1] != NULL)
     {
      FlushAlphaMemory(theEnv,theHeader);
      (*PatternData(theEnv)->PatternParserArray[rhsType-1]->removePatternFunction)(theEnv,theHeader);
     }
  }

/**************************************************/
/* AddPatternParser: Adds a pattern type to the   */
/*   list of pattern parsers used to detect valid */
/*   patterns in the LHS of a rule.               */
/**************************************************/
globle intBool AddPatternParser(
  void *theEnv,
  struct patternParser *newPtr)
  {
   struct patternParser *currentPtr, *lastPtr = NULL;

   /*============================================*/
   /* Check to see that the limit for the number */