factbld.c

clips源代码

   *nodeBeforeMatch = NULL;
   
   if (constantSelector)
     { compareTest = thePattern->constantValue; }
   else if (thePattern->constantSelector != NULL)
     { compareTest = thePattern->constantSelector; }
   else
     { compareTest = thePattern->networkTest; }

   /*==========================================================*/
   /* Loop through the nodes at the given level in the pattern */
   /* network looking for a node that can be reused (shared)?  */
   /*==========================================================*/

   while (listOfNodes != NULL)
     {
      /*==========================================================*/
      /* If the type of the pattern node and the expression being */
      /* tested by the pattern node are the same as the type and  */
      /* expression for the pattern field being added, then       */
      /* return the pattern node because it can be shared with    */
      /* the pattern field being added.                           */
      /*==========================================================*/

      if ((thePattern->type == SF_WILDCARD) || (thePattern->type == SF_VARIABLE))
        {
         if ((listOfNodes->header.singlefieldNode) &&
             (listOfNodes->header.endSlot == endSlot) &&
             (listOfNodes->whichField == thePattern->index) &&
             (listOfNodes->whichSlot == (thePattern->slotNumber - 1)) &&
             IdenticalExpression(listOfNodes->networkTest,compareTest) &&
             IdenticalExpression(listOfNodes->header.rightHash,thePattern->rightHash))
           { return(listOfNodes); }
        }
      else if ((thePattern->type == MF_WILDCARD) || (thePattern->type == MF_VARIABLE))
        {
         if ((listOfNodes->header.multifieldNode) &&
             (listOfNodes->header.endSlot == endSlot) &&
             (listOfNodes->leaveFields == thePattern->singleFieldsAfter) &&
             (listOfNodes->whichField == thePattern->index) &&
             (listOfNodes->whichSlot == (thePattern->slotNumber - 1)) &&
             IdenticalExpression(listOfNodes->networkTest,compareTest) &&
             IdenticalExpression(listOfNodes->header.rightHash,thePattern->rightHash))
           { return(listOfNodes); }
        }

      /*==================================*/
      /* Move on to the next node at this */
      /* level in the pattern network.    */
      /*==================================*/

      *nodeBeforeMatch = listOfNodes;
      listOfNodes = listOfNodes->rightNode;
     }

   /*==============================================*/
   /* A shareable pattern node could not be found. */
   /*==============================================*/

   return(NULL);
  }

/*************************************************************/
/* RemoveUnneededSlots: Removes fact pattern nodes that have */
/*   no effect on pattern matching. For example, given the   */
/*   following deftemplate and a pattern using it,           */
/*                                                           */
/*   (deftemplate foo (slot x) (slot y))                     */
/*                                                           */
/*   (foo (x ?x) (y ?y))                                     */
/*                                                           */
/*   The x and y slot pattern nodes can be discarded since   */
/*   all foo facts will have these two slots in the fact     */
/*   data structure used to store them.                      */
/*************************************************************/
static struct lhsParseNode *RemoveUnneededSlots(
  void *theEnv,
  struct lhsParseNode *thePattern)
  {
   struct lhsParseNode *tempPattern = thePattern;
   struct lhsParseNode *lastPattern = NULL, *head = thePattern;
   struct expr *theTest;

   while (tempPattern != NULL)
     {
      /*=============================================================*/
      /* A single field slot that has no pattern network expression  */
      /* associated with it can be removed (i.e. any value contained */
      /* in this slot will satisfy the pattern being matched).       */
      /*=============================================================*/

      if (((tempPattern->type == SF_WILDCARD) || (tempPattern->type == SF_VARIABLE)) &&
          (tempPattern->networkTest == NULL))
        {
         if (lastPattern != NULL) lastPattern->right = tempPattern->right;
         else head = tempPattern->right;

         tempPattern->right = NULL;
         ReturnLHSParseNodes(theEnv,tempPattern);

         if (lastPattern != NULL) tempPattern = lastPattern->right;
         else tempPattern = head;
        }

      /*=======================================================*/
      /* A multifield variable or wildcard within a multifield */
      /* slot can be removed if there are no other multifield  */
      /* variables or wildcards contained in the same slot     */
      /* (and the multifield has no expressions which must be  */
      /* evaluated in the fact pattern network).               */
      /*=======================================================*/

      else if (((tempPattern->type == MF_WILDCARD) || (tempPattern->type == MF_VARIABLE)) &&
               (tempPattern->multifieldSlot == FALSE) &&
               (tempPattern->networkTest == NULL) &&
               (tempPattern->multiFieldsBefore == 0) &&
               (tempPattern->multiFieldsAfter == 0))
        {
         if (lastPattern != NULL) lastPattern->right = tempPattern->right;
         else head = tempPattern->right;

         tempPattern->right = NULL;
         ReturnLHSParseNodes(theEnv,tempPattern);

         if (lastPattern != NULL) tempPattern = lastPattern->right;
         else tempPattern = head;
        }

      /*==================================================================*/
      /* A multifield wildcard or variable contained in a multifield slot */
      /* that contains no other multifield wildcards or variables, but    */
      /* does have an expression that must be evaluated, can be changed   */
      /* to a single field pattern node with the same expression.         */
      /*==================================================================*/

      else if (((tempPattern->type == MF_WILDCARD) || (tempPattern->type == MF_VARIABLE)) &&
               (tempPattern->multifieldSlot == FALSE) &&
               (tempPattern->networkTest != NULL) &&
               (tempPattern->multiFieldsBefore == 0) &&
               (tempPattern->multiFieldsAfter == 0))
        {
         tempPattern->type = SF_WILDCARD;
         lastPattern = tempPattern;
         tempPattern = tempPattern->right;
        }

      /*=========================================================*/
      /* If we're dealing with a multifield slot with no slot    */
      /* restrictions, then treat the multfield slot as a single */
      /* field slot, but attach a test which verifies that the   */
      /* slot contains a zero length multifield value.           */
      /*=========================================================*/

      else if ((tempPattern->type == MF_WILDCARD) &&
               (tempPattern->multifieldSlot == TRUE) &&
               (tempPattern->bottom == NULL))
        {
         tempPattern->type = SF_WILDCARD;
         tempPattern->networkTest = FactGenCheckZeroLength(theEnv,tempPattern->slotNumber);
         tempPattern->multifieldSlot = FALSE;
         lastPattern = tempPattern;
         tempPattern = tempPattern->right;
        }

      /*===================================================*/
      /* Recursively call RemoveUnneededSlots for the slot */
      /* restrictions contained within a multifield slot.  */
      /*===================================================*/

      else if ((tempPattern->type == MF_WILDCARD) &&
               (tempPattern->multifieldSlot == TRUE))
        {
         /*=======================================================*/
         /* Add an expression to the first pattern restriction in */
         /* the multifield slot that determines whether or not    */
         /* the fact's slot value contains the minimum number of  */
         /* required fields to satisfy the pattern restrictions   */
         /* for this slot. The length check is place before any   */
         /* other tests, so that preceeding checks do not have to */
         /* determine if there are enough fields in the slot to   */
         /* safely retrieve a value.                              */
         /*=======================================================*/

         theTest = FactGenCheckLength(theEnv,tempPattern->bottom);
         if (tempPattern->bottom->constantSelector != NULL)
           { tempPattern->bottom->constantSelector->nextArg = CopyExpression(theEnv,theTest); }
         theTest = CombineExpressions(theEnv,theTest,tempPattern->bottom->networkTest);
         tempPattern->bottom->networkTest = theTest;

         /*=========================================================*/
         /* Remove any unneeded pattern restrictions from the slot. */
         /*=========================================================*/

         tempPattern->bottom = RemoveUnneededSlots(theEnv,tempPattern->bottom);

         /*===========================================================*/
         /* If the slot no longer contains any restrictions, then the */
         /* multifield slot can be completely removed. In any case,   */
         /* move on to the next slot to be examined for removal.      */
         /*===========================================================*/

         if (tempPattern->bottom == NULL)
           {
            if (lastPattern != NULL) lastPattern->right = tempPattern->right;
            else head = tempPattern->right;

            tempPattern->right = NULL;
            ReturnLHSParseNodes(theEnv,tempPattern);

            if (lastPattern != NULL) tempPattern = lastPattern->right;
            else tempPattern = head;
           }
         else
           {
            lastPattern = tempPattern;
            tempPattern = tempPattern->right;
           }
        }

      /*=======================================================*/
      /* If none of the other tests for removing slots or slot */
      /* restrictions apply, then move on to the next slot or  */
      /* slot restriction to be tested.                        */
      /*=======================================================*/

      else
        {
         lastPattern = tempPattern;
         tempPattern = tempPattern->right;
        }
     }

   /*======================================*/
   /* Return the pattern with unused slots */
   /* and slot restrictions removed.       */
   /*======================================*/

   return(head);
  }

/****************************************************/
/* CreateNewPatternNode: Creates a new pattern node */
/*   and initializes all of its values.             */
/****************************************************/
static struct factPatternNode *CreateNewPatternNode(
  void *theEnv,
  struct lhsParseNode *thePattern,
  struct factPatternNode *nodeBeforeMatch,
  struct factPatternNode *upperLevel,
  unsigned endSlot,
  unsigned constantSelector)
  {
   struct factPatternNode *newNode;

   /*========================================*/
   /* Create the pattern node and initialize */
   /* its slots to the default values.       */
   /*========================================*/

   newNode = get_struct(theEnv,factPatternNode);
   newNode->nextLevel = NULL;
   newNode->rightNode = NULL;
   newNode->leftNode = NULL;
   newNode->leaveFields = thePattern->singleFieldsAfter;
   InitializePatternHeader(theEnv,(struct patternNodeHeader *) &newNode->header);

   if (thePattern->index > 0) 
     { newNode->whichField = (unsigned short) thePattern->index; }
   else newNode->whichField = 0;

   if (thePattern->slotNumber >= 0) 
     { newNode->whichSlot = (unsigned short) (thePattern->slotNumber - 1); }
   else 
     { newNode->whichSlot = newNode->whichField; }

   if ((thePattern->constantSelector != NULL) && (! constantSelector))
     { newNode->header.selector = TRUE; }

   /*=============================================================*/
   /* Set the slot values which indicate whether the pattern node */
   /* is a single-field, multifield, or end-of-pattern node.      */
   /*=============================================================*/

   if ((thePattern->type == SF_WILDCARD) || (thePattern->type == SF_VARIABLE))
     { newNode->header.singlefieldNode = TRUE; }
   else if ((thePattern->type == MF_WILDCARD) || (thePattern->type == MF_VARIABLE))
     { newNode->header.multifieldNode = TRUE; }
   newNode->header.endSlot = endSlot;

   /*===========================================================*/
   /* Install the expression associated with this pattern node. */
   /*===========================================================*/
   
   if (constantSelector)
     { newNode->networkTest = AddHashedExpression(theEnv,thePattern->constantValue); }
   else if (thePattern->constantSelector != NULL)
     { newNode->networkTest = AddHashedExpression(theEnv,thePattern->constantSelector); }
   else
     { newNode->networkTest = AddHashedExpression(theEnv,thePattern->networkTest); }

   /*==========================================*/
   /* Add the expression used for adding alpha */
   /* matches to the alpha memory.             */
   /*==========================================*/
   
   newNode->header.rightHash = AddHashedExpression(theEnv,thePattern->rightHash);
   
   /*===============================================*/
   /* Set the upper level pointer for the new node. */
   /*===============================================*/

   newNode->lastLevel = upperLevel;
   
   if ((upperLevel != NULL) && (upperLevel->header.selector))
     { AddHashedPatternNode(theEnv,upperLevel,newNode,newNode->networkTest->type,newNode->networkTest->value); }

   /*======================================================*/
   /* If there are no nodes on this level, then attach the */
   /* new node to the child pointer of the upper level.    */
   /*======================================================*/

   if (nodeBeforeMatch == NULL)
     {
      if (upperLevel == NULL) FactData(theEnv)->CurrentDeftemplate->patternNetwork = newNode;
      else upperLevel->nextLevel = newNode;
      return(newNode);
     }

   /*=====================================================*/
   /* If there is an upper level above the new node, then */
   /* place the new node as the first child in the upper  */
   /* level's nextLevel (child) link.                     */
   /*=====================================================*/

   if (upperLevel != NULL)
     {
      newNode->rightNode = upperLevel->nextLevel;
      if (upperLevel->nextLevel != NULL)
        { upperLevel->nextLevel->leftNode = newNode; }
      upperLevel->nextLevel = newNode;
      return(newNode);
     }

   /*=====================================================*/