1 /*******************************************************/
2 /* "C" Language Integrated Production System */
3 /* */
4 /* CLIPS Version 6.30 01/13/15 */
5 /* */
6 /* OBJECT PATTERN MATCHER MODULE */
7 /*******************************************************/
8
9 /*************************************************************/
10 /* Purpose: RETE Network Parsing Interface for Objects */
11 /* */
12 /* Principal Programmer(s): */
13 /* Brian L. Dantes */
14 /* */
15 /* Contributing Programmer(s): */
16 /* */
17 /* Revision History: */
18 /* */
19 /* 6.24: Removed INCREMENTAL_RESET compilation flag. */
20 /* */
21 /* Converted INSTANCE_PATTERN_MATCHING to */
22 /* DEFRULE_CONSTRUCT. */
23 /* */
24 /* Renamed BOOLEAN macro type to intBool. */
25 /* */
26 /* 6.30: Changed integer type/precision. */
27 /* */
28 /* Removed conditional code for unsupported */
29 /* compilers/operating systems (IBM_MCW, */
30 /* MAC_MCW, and IBM_TBC). */
31 /* */
32 /* Support for long long integers. */
33 /* */
34 /* Added support for hashed comparisons to */
35 /* constants. */
36 /* */
37 /* Added support for hashed alpha memories. */
38 /* */
39 /* Added const qualifiers to remove C++ */
40 /* deprecation warnings. */
41 /* */
42 /*************************************************************/
43 /* =========================================
44 *****************************************
45 EXTERNAL DEFINITIONS
46 =========================================
47 ***************************************** */
48 #include "setup.h"
49
50 #if DEFRULE_CONSTRUCT && OBJECT_SYSTEM
51
52 #if (! BLOAD_ONLY) && (! RUN_TIME)
53
54 #include <string.h>
55 #include <stdlib.h>
56
57 #include "classcom.h"
58 #include "classfun.h"
59 #include "cstrnutl.h"
60 #include "constrnt.h"
61 #include "cstrnchk.h"
62 #include "cstrnops.h"
63 #include "drive.h"
64 #include "envrnmnt.h"
65 #include "exprnpsr.h"
66 #include "inscom.h"
67 #include "insfun.h"
68 #include "insmngr.h"
69 #include "memalloc.h"
70 #include "network.h"
71 #include "object.h"
72 #include "pattern.h"
73 #include "reteutil.h"
74 #include "ruledef.h"
75 #include "rulepsr.h"
76 #include "scanner.h"
77 #include "symbol.h"
78 #include "utility.h"
79
80 #endif
81
82 #include "constrct.h"
83 #include "objrtmch.h"
84 #include "objrtgen.h"
85 #include "objrtfnx.h"
86 #include "reorder.h"
87 #include "router.h"
88
89 #if CONSTRUCT_COMPILER && (! RUN_TIME)
90 #include "objrtcmp.h"
91 #endif
92
93 #if BLOAD_AND_BSAVE || BLOAD || BLOAD_ONLY
94 #include "objrtbin.h"
95 #endif
96
97 #define _OBJRTBLD_SOURCE_
98 #include "objrtbld.h"
99
100 #if ! DEFINSTANCES_CONSTRUCT
101 #include "extnfunc.h"
102 #include "classfun.h"
103 #include "classcom.h"
104 #endif
105
106 #if (! BLOAD_ONLY) && (! RUN_TIME)
107
108 /* =========================================
109 *****************************************
110 CONSTANTS
111 =========================================
112 ***************************************** */
113 #define OBJECT_PATTERN_INDICATOR "object"
114
115 /* =========================================
116 *****************************************
117 INTERNALLY VISIBLE FUNCTION HEADERS
118 =========================================
119 ***************************************** */
120
121 static intBool PatternParserFind(SYMBOL_HN *);
122 static struct lhsParseNode *ObjectLHSParse(void *,const char *,struct token *);
123 static intBool ReorderAndAnalyzeObjectPattern(void *,struct lhsParseNode *);
124 static struct patternNodeHeader *PlaceObjectPattern(void *,struct lhsParseNode *);
125 static OBJECT_PATTERN_NODE *FindObjectPatternNode(OBJECT_PATTERN_NODE *,struct lhsParseNode *,
126 OBJECT_PATTERN_NODE **,unsigned,unsigned);
127 static OBJECT_PATTERN_NODE *CreateNewObjectPatternNode(void *,struct lhsParseNode *,OBJECT_PATTERN_NODE *,
128 OBJECT_PATTERN_NODE *,unsigned,unsigned);
129 static void DetachObjectPattern(void *,struct patternNodeHeader *);
130 static void ClearObjectPatternMatches(void *,OBJECT_ALPHA_NODE *);
131 static void RemoveObjectPartialMatches(void *,INSTANCE_TYPE *,struct patternNodeHeader *);
132 static intBool CheckDuplicateSlots(void *,struct lhsParseNode *,SYMBOL_HN *);
133 static struct lhsParseNode *ParseClassRestriction(void *,const char *,struct token *);
134 static struct lhsParseNode *ParseNameRestriction(void *,const char *,struct token *);
135 static struct lhsParseNode *ParseSlotRestriction(void *,const char *,struct token *,CONSTRAINT_RECORD *,int);
136 static CLASS_BITMAP *NewClassBitMap(void *,int,int);
137 static void InitializeClassBitMap(void *,CLASS_BITMAP *,int);
138 static void DeleteIntermediateClassBitMap(void *,CLASS_BITMAP *);
139 static void *CopyClassBitMap(void *,void *);
140 static void DeleteClassBitMap(void *,void *);
141 static void MarkBitMapClassesBusy(void *,BITMAP_HN *,int);
142 static intBool EmptyClassBitMap(CLASS_BITMAP *);
143 static intBool IdenticalClassBitMap(CLASS_BITMAP *,CLASS_BITMAP *);
144 static intBool ProcessClassRestriction(void *,CLASS_BITMAP *,struct lhsParseNode **,int);
145 static CONSTRAINT_RECORD *ProcessSlotRestriction(void *,CLASS_BITMAP *,SYMBOL_HN *,int *);
146 static void IntersectClassBitMaps(CLASS_BITMAP *,CLASS_BITMAP *);
147 static void UnionClassBitMaps(CLASS_BITMAP *,CLASS_BITMAP *);
148 static CLASS_BITMAP *PackClassBitMap(void *,CLASS_BITMAP *);
149 static struct lhsParseNode *FilterObjectPattern(void *,struct patternParser *,
150 struct lhsParseNode *,struct lhsParseNode **,
151 struct lhsParseNode **,struct lhsParseNode **);
152 static BITMAP_HN *FormSlotBitMap(void *,struct lhsParseNode *);
153 static struct lhsParseNode *RemoveSlotExistenceTests(void *,struct lhsParseNode *,BITMAP_HN **);
154 static struct lhsParseNode *CreateInitialObjectPattern(void *);
155 static EXPRESSION *ObjectMatchDelayParse(void *,EXPRESSION *,const char *);
156 static void MarkObjectPtnIncrementalReset(void *,struct patternNodeHeader *,int);
157 static void ObjectIncrementalReset(void *);
158
159 #endif
160
161 #if ! DEFINSTANCES_CONSTRUCT
162 static void ResetInitialObject(void *);
163 #endif
164
165 /* =========================================
166 *****************************************
167 EXTERNALLY VISIBLE FUNCTIONS
168 =========================================
169 ***************************************** */
170
171 /********************************************************
172 NAME : SetupObjectPatternStuff
173 DESCRIPTION : Installs the parsers and other items
174 necessary for recognizing and processing
175 object patterns in defrules
176 INPUTS : None
177 RETURNS : Nothing useful
178 SIDE EFFECTS : Rete network interfaces for objects
179 initialized
180 NOTES : None
181 ********************************************************/
SetupObjectPatternStuff(void * theEnv)182 globle void SetupObjectPatternStuff(
183 void *theEnv)
184 {
185 #if (! BLOAD_ONLY) && (! RUN_TIME)
186 struct patternParser *newPtr;
187
188 if (ReservedPatternSymbol(theEnv,"object",NULL) == TRUE)
189 {
190 SystemError(theEnv,"OBJRTBLD",1);
191 EnvExitRouter(theEnv,EXIT_FAILURE);
192 }
193 AddReservedPatternSymbol(theEnv,"object",NULL);
194
195 /* ===========================================================================
196 The object pattern parser needs to have a higher priority than deftemplates
197 or regular facts so that the "object" keyword is always recognized first
198 =========================================================================== */
199
200 newPtr = get_struct(theEnv,patternParser);
201
202 newPtr->name = "objects";
203 newPtr->priority = 20;
204 newPtr->entityType = &InstanceData(theEnv)->InstanceInfo;
205
206 newPtr->recognizeFunction = PatternParserFind;
207 newPtr->parseFunction = ObjectLHSParse;
208 newPtr->postAnalysisFunction = ReorderAndAnalyzeObjectPattern;
209 newPtr->addPatternFunction = PlaceObjectPattern;
210 newPtr->removePatternFunction = DetachObjectPattern;
211 newPtr->genJNConstantFunction = NULL;
212 newPtr->replaceGetJNValueFunction = ReplaceGetJNObjectValue;
213 newPtr->genGetJNValueFunction = GenGetJNObjectValue;
214 newPtr->genCompareJNValuesFunction = ObjectJNVariableComparison;
215 newPtr->genPNConstantFunction = GenObjectPNConstantCompare;
216 newPtr->replaceGetPNValueFunction = ReplaceGetPNObjectValue;
217 newPtr->genGetPNValueFunction = GenGetPNObjectValue;
218 newPtr->genComparePNValuesFunction = ObjectPNVariableComparison;
219 newPtr->returnUserDataFunction = DeleteClassBitMap;
220 newPtr->copyUserDataFunction = CopyClassBitMap;
221
222 newPtr->markIRPatternFunction = MarkObjectPtnIncrementalReset;
223 newPtr->incrementalResetFunction = ObjectIncrementalReset;
224
225 newPtr->initialPatternFunction = CreateInitialObjectPattern;
226
227 #if CONSTRUCT_COMPILER && (! RUN_TIME)
228 newPtr->codeReferenceFunction = ObjectPatternNodeReference;
229 #else
230 newPtr->codeReferenceFunction = NULL;
231 #endif
232
233 AddPatternParser(theEnv,newPtr);
234
235 EnvDefineFunction2(theEnv,"object-pattern-match-delay",'u',
236 PTIEF ObjectMatchDelay,"ObjectMatchDelay",NULL);
237
238 AddFunctionParser(theEnv,"object-pattern-match-delay",ObjectMatchDelayParse);
239 FuncSeqOvlFlags(theEnv,"object-pattern-match-delay",FALSE,FALSE);
240
241 #endif
242
243 InstallObjectPrimitives(theEnv);
244
245 #if CONSTRUCT_COMPILER && (! RUN_TIME)
246 ObjectPatternsCompilerSetup(theEnv);
247 #endif
248
249 #if ! DEFINSTANCES_CONSTRUCT
250 EnvAddResetFunction(theEnv,"reset-initial-object",ResetInitialObject,0);
251 #endif
252
253
254 #if BLOAD_AND_BSAVE || BLOAD || BLOAD_ONLY
255 SetupObjectPatternsBload(theEnv);
256 #endif
257 }
258
259 /* =========================================
260 *****************************************
261 INTERNALLY VISIBLE FUNCTIONS
262 =========================================
263 ***************************************** */
264
265 #if ! DEFINSTANCES_CONSTRUCT
266
ResetInitialObject(void * theEnv)267 static void ResetInitialObject(
268 void *theEnv)
269 {
270 EXPRESSION *tmp;
271 DATA_OBJECT rtn;
272
273 tmp = GenConstant(theEnv,FCALL,(void *) FindFunction(theEnv,"make-instance"));
274 tmp->argList = GenConstant(theEnv,INSTANCE_NAME,(void *) DefclassData(theEnv)->INITIAL_OBJECT_SYMBOL);
275 tmp->argList->nextArg =
276 GenConstant(theEnv,DEFCLASS_PTR,(void *) LookupDefclassInScope(theEnv,INITIAL_OBJECT_CLASS_NAME));
277 EvaluateExpression(theEnv,tmp,&rtn);
278 ReturnExpression(theEnv,tmp);
279 }
280
281 #endif
282
283 #if (! BLOAD_ONLY) && (! RUN_TIME)
284
285 /*****************************************************
286 NAME : PatternParserFind
287 DESCRIPTION : Determines if a pattern CE is an
288 object pattern (i.e. the first field
289 is the constant symbol "object")
290 INPUTS : 1) The type of the first field
291 2) The value of the first field
292 RETURNS : TRUE if it is an object pattern,
293 FALSE otherwise
294 SIDE EFFECTS : None
295 NOTES : Used by AddPatternParser()
296 *****************************************************/
PatternParserFind(SYMBOL_HN * value)297 static intBool PatternParserFind(
298 SYMBOL_HN *value)
299 {
300 if (strcmp(ValueToString(value),OBJECT_PATTERN_INDICATOR) == 0)
301 return(TRUE);
302
303 return(FALSE);
304 }
305
306 /************************************************************************************
307 NAME : ObjectLHSParse
308 DESCRIPTION : Scans and parses an object pattern for a rule
309 INPUTS : 1) The logical name of the input source
310 2) A buffer holding the last token read
311 RETURNS : The address of struct lhsParseNodes, NULL on errors
312 SIDE EFFECTS : A series of struct lhsParseNodes are created to represent
313 the intermediate parse of the pattern
314 Pretty-print form for the pattern is saved
315 NOTES : Object Pattern Syntax:
316 (object [<class-constraint>] [<name-constraint>] <slot-constraint>*)
317 <class-constraint> ::= (is-a <constraint>)
318 <name-constraint> ::= (name <constraint>)
319 <slot-constraint> ::= (<slot-name> <constraint>*)
320 ************************************************************************************/
ObjectLHSParse(void * theEnv,const char * readSource,struct token * lastToken)321 static struct lhsParseNode *ObjectLHSParse(
322 void *theEnv,
323 const char *readSource,
324 struct token *lastToken)
325 {
326 #if MAC_XCD
327 #pragma unused(lastToken)
328 #endif
329 struct token theToken;
330 struct lhsParseNode *firstNode = NULL,*lastNode = NULL,*tmpNode;
331 CLASS_BITMAP *clsset,*tmpset;
332 CONSTRAINT_RECORD *slotConstraints;
333 int ppbackupReqd = FALSE,multip;
334
335 /* ========================================================
336 Get a bitmap big enough to mark the ids of all currently
337 existing classes - and set all bits, since the initial
338 set of applicable classes is everything.
339 ======================================================== */
340 clsset = NewClassBitMap(theEnv,((int) DefclassData(theEnv)->MaxClassID) - 1,1);
341 if (EmptyClassBitMap(clsset))
342 {
343 PrintErrorID(theEnv,"OBJRTBLD",1,FALSE);
344 EnvPrintRouter(theEnv,WERROR,"No objects of existing classes can satisfy pattern.\n");
345 DeleteIntermediateClassBitMap(theEnv,clsset);
346 return(NULL);
347 }
348 tmpset = NewClassBitMap(theEnv,((int) DefclassData(theEnv)->MaxClassID) - 1,1);
349
350 IncrementIndentDepth(theEnv,7);
351
352 /* ===========================================
353 Parse the class, name and slot restrictions
354 =========================================== */
355 GetToken(theEnv,readSource,&theToken);
356 while (theToken.type != RPAREN)
357 {
358 ppbackupReqd = TRUE;
359 PPBackup(theEnv);
360 SavePPBuffer(theEnv," ");
361 SavePPBuffer(theEnv,theToken.printForm);
362 if (theToken.type != LPAREN)
363 {
364 SyntaxErrorMessage(theEnv,"object pattern");
365 goto ObjectLHSParseERROR;
366 }
367 GetToken(theEnv,readSource,&theToken);
368 if (theToken.type != SYMBOL)
369 {
370 SyntaxErrorMessage(theEnv,"object pattern");
371 goto ObjectLHSParseERROR;
372 }
373 if (CheckDuplicateSlots(theEnv,firstNode,(SYMBOL_HN *) theToken.value))
374 goto ObjectLHSParseERROR;
375 if (theToken.value == (void *) DefclassData(theEnv)->ISA_SYMBOL)
376 {
377 tmpNode = ParseClassRestriction(theEnv,readSource,&theToken);
378 if (tmpNode == NULL)
379 goto ObjectLHSParseERROR;
380 InitializeClassBitMap(theEnv,tmpset,0);
381 if (ProcessClassRestriction(theEnv,tmpset,&tmpNode->bottom,TRUE) == FALSE)
382 {
383 ReturnLHSParseNodes(theEnv,tmpNode);
384 goto ObjectLHSParseERROR;
385 }
386 IntersectClassBitMaps(clsset,tmpset);
387 }
388 else if (theToken.value == (void *) DefclassData(theEnv)->NAME_SYMBOL)
389 {
390 tmpNode = ParseNameRestriction(theEnv,readSource,&theToken);
391 if (tmpNode == NULL)
392 goto ObjectLHSParseERROR;
393 InitializeClassBitMap(theEnv,tmpset,1);
394 }
395 else
396 {
397 slotConstraints = ProcessSlotRestriction(theEnv,clsset,(SYMBOL_HN *) theToken.value,&multip);
398 if (slotConstraints != NULL)
399 {
400 InitializeClassBitMap(theEnv,tmpset,1);
401 tmpNode = ParseSlotRestriction(theEnv,readSource,&theToken,slotConstraints,multip);
402 if (tmpNode == NULL)
403 goto ObjectLHSParseERROR;
404 }
405 else
406 {
407 InitializeClassBitMap(theEnv,tmpset,0);
408 tmpNode = GetLHSParseNode(theEnv);
409 tmpNode->slot = (SYMBOL_HN *) theToken.value;
410 }
411 }
412 if (EmptyClassBitMap(tmpset))
413 {
414 PrintErrorID(theEnv,"OBJRTBLD",2,FALSE);
415 EnvPrintRouter(theEnv,WERROR,"No objects of existing classes can satisfy ");
416 EnvPrintRouter(theEnv,WERROR,ValueToString(tmpNode->slot));
417 EnvPrintRouter(theEnv,WERROR," restriction in object pattern.\n");
418 ReturnLHSParseNodes(theEnv,tmpNode);
419 goto ObjectLHSParseERROR;
420 }
421 if (EmptyClassBitMap(clsset))
422 {
423 PrintErrorID(theEnv,"OBJRTBLD",1,FALSE);
424 EnvPrintRouter(theEnv,WERROR,"No objects of existing classes can satisfy pattern.\n");
425 ReturnLHSParseNodes(theEnv,tmpNode);
426 goto ObjectLHSParseERROR;
427 }
428 if (tmpNode != NULL)
429 {
430 if (firstNode == NULL)
431 firstNode = tmpNode;
432 else
433 lastNode->right = tmpNode;
434 lastNode = tmpNode;
435 }
436 PPCRAndIndent(theEnv);
437 GetToken(theEnv,readSource,&theToken);
438 }
439 if (firstNode == NULL)
440 {
441 if (EmptyClassBitMap(clsset))
442 {
443 PrintErrorID(theEnv,"OBJRTBLD",1,FALSE);
444 EnvPrintRouter(theEnv,WERROR,"No objects of existing classes can satisfy pattern.\n");
445 goto ObjectLHSParseERROR;
446 }
447 firstNode = GetLHSParseNode(theEnv);
448 firstNode->type = SF_WILDCARD;
449 firstNode->slot = DefclassData(theEnv)->ISA_SYMBOL;
450 firstNode->slotNumber = ISA_ID;
451 firstNode->index = 1;
452 }
453 if (ppbackupReqd)
454 {
455 PPBackup(theEnv);
456 PPBackup(theEnv);
457 SavePPBuffer(theEnv,theToken.printForm);
458 }
459 DeleteIntermediateClassBitMap(theEnv,tmpset);
460 clsset = PackClassBitMap(theEnv,clsset);
461 firstNode->userData = EnvAddBitMap(theEnv,(void *) clsset,ClassBitMapSize(clsset));
462 IncrementBitMapCount(firstNode->userData);
463 DeleteIntermediateClassBitMap(theEnv,clsset);
464 DecrementIndentDepth(theEnv,7);
465 return(firstNode);
466
467 ObjectLHSParseERROR:
468 DeleteIntermediateClassBitMap(theEnv,clsset);
469 DeleteIntermediateClassBitMap(theEnv,tmpset);
470 ReturnLHSParseNodes(theEnv,firstNode);
471 DecrementIndentDepth(theEnv,7);
472 return(NULL);
473 }
474
475 /**************************************************************
476 NAME : ReorderAndAnalyzeObjectPattern
477 DESCRIPTION : This function reexamines the object pattern
478 after constraint and variable analysis info
479 has been propagated from other patterns.
480 Any slots which are no longer applicable
481 to the pattern are eliminated from the
482 class set.
483 Also, the slot names are ordered according
484 to lexical value to aid in deteterming
485 sharing between object patterns. (The is-a
486 and name restrictions are always placed
487 first regardless of symbolic hash value.)
488 INPUTS : The pattern CE lhsParseNode
489 RETURNS : FALSE if all OK, otherwise TRUE
490 (e.g. all classes are eliminated as potential
491 matching candidates for the pattern)
492 SIDE EFFECTS : Slot restrictions are reordered (if necessary)
493 NOTES : Adds a default is-a slot if one does not
494 already exist
495 **************************************************************/
ReorderAndAnalyzeObjectPattern(void * theEnv,struct lhsParseNode * topNode)496 static intBool ReorderAndAnalyzeObjectPattern(
497 void *theEnv,
498 struct lhsParseNode *topNode)
499 {
500 CLASS_BITMAP *clsset,*tmpset;
501 EXPRESSION *rexp,*tmpmin,*tmpmax;
502 DEFCLASS *cls;
503 struct lhsParseNode *tmpNode,*subNode,*bitmap_node,*isa_node,*name_node;
504 register unsigned short i;
505 SLOT_DESC *sd;
506 CONSTRAINT_RECORD *crossConstraints, *theConstraint;
507 int incompatibleConstraint,clssetChanged = FALSE;
508
509 /* ==========================================================
510 Make sure that the bitmap marking which classes of object
511 can match the pattern is attached to the class restriction
512 (which will always be present and the last restriction
513 after the sort)
514 ========================================================== */
515 topNode->right = FilterObjectPattern(theEnv,topNode->patternType,topNode->right,
516 &bitmap_node,&isa_node,&name_node);
517 if (EnvGetStaticConstraintChecking(theEnv) == FALSE)
518 return(FALSE);
519
520 /* ============================================
521 Allocate a temporary set for marking classes
522 ============================================ */
523 clsset = (CLASS_BITMAP *) ValueToBitMap(bitmap_node->userData);
524 tmpset = NewClassBitMap(theEnv,(int) clsset->maxid,0);
525
526 /* ==========================================================
527 Check the allowed-values for the constraint on the is-a
528 slot. If there are any, make sure that only the classes
529 with those values as names are marked in the bitmap.
530
531 There will only be symbols in the list because the
532 original constraint on the is-a slot allowed only symbols.
533 ========================================================== */
534 if ((isa_node == NULL) ? FALSE :
535 ((isa_node->constraints == NULL) ? FALSE :
536 (isa_node->constraints->restrictionList != NULL)))
537 {
538 rexp = isa_node->constraints->restrictionList;
539 while (rexp != NULL)
540 {
541 cls = LookupDefclassInScope(theEnv,ValueToString(rexp->value));
542 if (cls != NULL)
543 {
544 if ((cls->id <= (unsigned) clsset->maxid) ? TestBitMap(clsset->map,cls->id) : FALSE)
545 SetBitMap(tmpset->map,cls->id);
546 }
547 rexp = rexp->nextArg;
548 }
549 clssetChanged = IdenticalClassBitMap(tmpset,clsset) ? FALSE : TRUE;
550 }
551 else
552 GenCopyMemory(char,tmpset->maxid / BITS_PER_BYTE + 1,tmpset->map,clsset->map);
553
554 /* ================================================================
555 For each of the slots (excluding name and is-a), check the total
556 constraints for the slot against the individual constraints
557 for each occurrence of the slot in the classes marked in
558 the bitmap. For any slot which is not compatible with
559 the overall constraint, clear its class's bit in the bitmap.
560 ================================================================ */
561 tmpNode = topNode->right;
562 while (tmpNode != bitmap_node)
563 {
564 if ((tmpNode == isa_node) || (tmpNode == name_node))
565 {
566 tmpNode = tmpNode->right;
567 continue;
568 }
569 for (i = 0 ; i <= tmpset->maxid ; i++)
570 if (TestBitMap(tmpset->map,i))
571 {
572 cls = DefclassData(theEnv)->ClassIDMap[i];
573 sd = cls->instanceTemplate[FindInstanceTemplateSlot(theEnv,cls,tmpNode->slot)];
574
575 /* =========================================
576 Check the top-level lhsParseNode for type
577 and cardinality compatibility
578 ========================================= */
579 crossConstraints = IntersectConstraints(theEnv,tmpNode->constraints,sd->constraint);
580 incompatibleConstraint = UnmatchableConstraint(crossConstraints);
581 RemoveConstraint(theEnv,crossConstraints);
582 if (incompatibleConstraint)
583 {
584 ClearBitMap(tmpset->map,i);
585 clssetChanged = TRUE;
586 }
587 else if (tmpNode->type == MF_WILDCARD)
588 {
589 /* ==========================================
590 Check the sub-nodes for type compatibility
591 ========================================== */
592 for (subNode = tmpNode->bottom ; subNode != NULL ; subNode = subNode->right)
593 {
594 /* ========================================================
595 Temporarily reset cardinality of variables to
596 match slot so that no cardinality errors will be flagged
597 ======================================================== */
598 if ((subNode->type == MF_WILDCARD) || (subNode->type == MF_VARIABLE))
599 { theConstraint = subNode->constraints->multifield; }
600 else
601 { theConstraint = subNode->constraints; }
602
603 tmpmin = theConstraint->minFields;
604 theConstraint->minFields = sd->constraint->minFields;
605 tmpmax = theConstraint->maxFields;
606 theConstraint->maxFields = sd->constraint->maxFields;
607 crossConstraints = IntersectConstraints(theEnv,theConstraint,sd->constraint);
608 theConstraint->minFields = tmpmin;
609 theConstraint->maxFields = tmpmax;
610
611 incompatibleConstraint = UnmatchableConstraint(crossConstraints);
612 RemoveConstraint(theEnv,crossConstraints);
613 if (incompatibleConstraint)
614 {
615 ClearBitMap(tmpset->map,i);
616 clssetChanged = TRUE;
617 break;
618 }
619 }
620 }
621 }
622 tmpNode = tmpNode->right;
623 }
624
625 if (clssetChanged)
626 {
627 /* =======================================================
628 Make sure that there are still classes of objects which
629 can satisfy this pattern. Otherwise, signal an error.
630 ======================================================= */
631 if (EmptyClassBitMap(tmpset))
632 {
633 PrintErrorID(theEnv,"OBJRTBLD",3,TRUE);
634 DeleteIntermediateClassBitMap(theEnv,tmpset);
635 EnvPrintRouter(theEnv,WERROR,"No objects of existing classes can satisfy pattern #");
636 PrintLongInteger(theEnv,WERROR,(long long) topNode->pattern);
637 EnvPrintRouter(theEnv,WERROR,".\n");
638 return(TRUE);
639 }
640 clsset = PackClassBitMap(theEnv,tmpset);
641 DeleteClassBitMap(theEnv,(void *) bitmap_node->userData);
642 bitmap_node->userData = EnvAddBitMap(theEnv,(void *) clsset,ClassBitMapSize(clsset));
643 IncrementBitMapCount(bitmap_node->userData);
644 DeleteIntermediateClassBitMap(theEnv,clsset);
645 }
646 else
647 DeleteIntermediateClassBitMap(theEnv,tmpset);
648 return(FALSE);
649 }
650
651 /*****************************************************
652 NAME : PlaceObjectPattern
653 DESCRIPTION : Integrates an object pattern into the
654 object pattern network
655 INPUTS : The intermediate parse representation
656 of the pattern
657 RETURNS : The address of the new pattern
658 SIDE EFFECTS : Object pattern network updated
659 NOTES : None
660 *****************************************************/
PlaceObjectPattern(void * theEnv,struct lhsParseNode * thePattern)661 static struct patternNodeHeader *PlaceObjectPattern(
662 void *theEnv,
663 struct lhsParseNode *thePattern)
664 {
665 OBJECT_PATTERN_NODE *currentLevel,*lastLevel;
666 struct lhsParseNode *tempPattern = NULL;
667 OBJECT_PATTERN_NODE *nodeSlotGroup, *newNode;
668 OBJECT_ALPHA_NODE *newAlphaNode;
669 unsigned endSlot;
670 BITMAP_HN *newClassBitMap,*newSlotBitMap;
671 struct expr *rightHash;
672
673 /*========================================================*/
674 /* Get the top of the object pattern network and prepare */
675 /* for the traversal to look for shareable pattern nodes. */
676 /*========================================================*/
677
678 currentLevel = ObjectNetworkPointer(theEnv);
679 lastLevel = NULL;
680
681 /*====================================================*/
682 /* Remove slot existence tests from the pattern since */
683 /* these are accounted for by the class bitmap and */
684 /* find the class and slot bitmaps. */
685 /*====================================================*/
686
687 rightHash = thePattern->rightHash;
688
689 newSlotBitMap = FormSlotBitMap(theEnv,thePattern->right);
690 thePattern->right = RemoveSlotExistenceTests(theEnv,thePattern->right,&newClassBitMap);
691 thePattern = thePattern->right;
692
693 /*=========================================================*/
694 /* Loop until all fields in the pattern have been added to */
695 /* the pattern network. Process the bitmap node ONLY if it */
696 /* is the only node in the pattern. */
697 /*=========================================================*/
698
699 do
700 {
701 if (thePattern->multifieldSlot)
702 {
703 tempPattern = thePattern;
704 thePattern = thePattern->bottom;
705 }
706
707 /*============================================*/
708 /* Determine if the last pattern field within */
709 /* a multifield slot is being processed. */
710 /*============================================*/
711
712 if (((thePattern->type == MF_WILDCARD) ||
713 (thePattern->type == MF_VARIABLE)) &&
714 (thePattern->right == NULL) && (tempPattern != NULL))
715 { endSlot = TRUE; }
716 else
717 { endSlot = FALSE; }
718
719 /*========================================*/
720 /* Is there a node in the pattern network */
721 /* that can be reused (shared)? */
722 /*========================================*/
723
724 newNode = FindObjectPatternNode(currentLevel,thePattern,&nodeSlotGroup,endSlot,FALSE);
725
726 /*================================================*/
727 /* If the pattern node cannot be shared, then add */
728 /* a new pattern node to the pattern network. */
729 /*================================================*/
730
731 if (newNode == NULL)
732 { newNode = CreateNewObjectPatternNode(theEnv,thePattern,nodeSlotGroup,lastLevel,endSlot,FALSE); }
733
734 if (thePattern->constantSelector != NULL)
735 {
736 currentLevel = newNode->nextLevel;
737 lastLevel = newNode;
738 newNode = FindObjectPatternNode(currentLevel,thePattern,&nodeSlotGroup,endSlot,TRUE);
739
740 if (newNode == NULL)
741 { newNode = CreateNewObjectPatternNode(theEnv,thePattern,nodeSlotGroup,lastLevel,endSlot,TRUE); }
742 }
743
744 /*=======================================================*/
745 /* Move on to the next field in the pattern to be added. */
746 /*=======================================================*/
747
748 if ((thePattern->right == NULL) && (tempPattern != NULL))
749 {
750 thePattern = tempPattern;
751 tempPattern = NULL;
752 }
753
754 lastLevel = newNode;
755 currentLevel = newNode->nextLevel;
756 thePattern = thePattern->right;
757 }
758 while ((thePattern != NULL) ? (thePattern->userData == NULL) : FALSE);
759
760 /*==================================================*/
761 /* Return the leaf node of the newly added pattern. */
762 /*==================================================*/
763
764 newAlphaNode = lastLevel->alphaNode;
765 while (newAlphaNode != NULL)
766 {
767 if ((newClassBitMap == newAlphaNode->classbmp) &&
768 (newSlotBitMap == newAlphaNode->slotbmp) &&
769 IdenticalExpression(newAlphaNode->header.rightHash,rightHash))
770 return((struct patternNodeHeader *) newAlphaNode);
771 newAlphaNode = newAlphaNode->nxtInGroup;
772 }
773
774 newAlphaNode = get_struct(theEnv,objectAlphaNode);
775 InitializePatternHeader(theEnv,&newAlphaNode->header);
776 newAlphaNode->header.rightHash = AddHashedExpression(theEnv,rightHash);
777 newAlphaNode->matchTimeTag = 0L;
778 newAlphaNode->patternNode = lastLevel;
779 newAlphaNode->classbmp = newClassBitMap;
780 IncrementBitMapCount(newClassBitMap);
781 MarkBitMapClassesBusy(theEnv,newClassBitMap,1);
782 newAlphaNode->slotbmp = newSlotBitMap;
783 if (newSlotBitMap != NULL)
784 IncrementBitMapCount(newSlotBitMap);
785 newAlphaNode->bsaveID = 0L;
786 newAlphaNode->nxtInGroup = lastLevel->alphaNode;
787 lastLevel->alphaNode = newAlphaNode;
788 newAlphaNode->nxtTerminal = ObjectNetworkTerminalPointer(theEnv);
789 SetObjectNetworkTerminalPointer(theEnv,newAlphaNode);
790 return((struct patternNodeHeader *) newAlphaNode);
791 }
792
793 /************************************************************************
794 NAME : FindObjectPatternNode
795 DESCRIPTION : Looks for a pattern node at a specified
796 level in the pattern network that can be reused (shared)
797 with a pattern field being added to the pattern network.
798 INPUTS : 1) The current layer of nodes being examined in the
799 object pattern network
800 2) The intermediate parse representation of the pattern
801 being added
802 3) A buffer for holding the first node of a group
803 of slots with the same name as the new node
804 4) An integer code indicating if this is the last
805 fiedl in a slot pattern or not
806 RETURNS : The old pattern network node matching the new node, or
807 NULL if there is none (nodeSlotGroup will hold the
808 place where to attach a new node)
809 SIDE EFFECTS : nodeSlotGroup set
810 NOTES : None
811 ************************************************************************/
FindObjectPatternNode(OBJECT_PATTERN_NODE * listOfNodes,struct lhsParseNode * thePattern,OBJECT_PATTERN_NODE ** nodeSlotGroup,unsigned endSlot,unsigned constantSelector)812 static OBJECT_PATTERN_NODE *FindObjectPatternNode(
813 OBJECT_PATTERN_NODE *listOfNodes,
814 struct lhsParseNode *thePattern,
815 OBJECT_PATTERN_NODE **nodeSlotGroup,
816 unsigned endSlot,
817 unsigned constantSelector)
818 {
819 struct expr *compareTest;
820 *nodeSlotGroup = NULL;
821
822 if (constantSelector)
823 { compareTest = thePattern->constantValue; }
824 else if (thePattern->constantSelector != NULL)
825 { compareTest = thePattern->constantSelector; }
826 else
827 { compareTest = thePattern->networkTest; }
828
829 /*==========================================================*/
830 /* Loop through the nodes at the given level in the pattern */
831 /* network looking for a node that can be reused (shared). */
832 /*==========================================================*/
833
834 while (listOfNodes != NULL)
835 {
836 /*=========================================================*/
837 /* A object pattern node can be shared if the slot name is */
838 /* the same, the test is on the same field in the pattern, */
839 /* and the network test expressions are the same. */
840 /*=========================================================*/
841
842 if (((thePattern->type == MF_WILDCARD) || (thePattern->type == MF_VARIABLE)) ?
843 listOfNodes->multifieldNode : (listOfNodes->multifieldNode == 0))
844 {
845 if ((thePattern->slotNumber == (int) listOfNodes->slotNameID) &&
846 (thePattern->index == (int) listOfNodes->whichField) &&
847 (thePattern->singleFieldsAfter == listOfNodes->leaveFields) &&
848 (endSlot == listOfNodes->endSlot) &&
849 IdenticalExpression(listOfNodes->networkTest,compareTest))
850 return(listOfNodes);
851 }
852
853 /*===============================================*/
854 /* Find the beginning of a group of nodes with */
855 /* the same slot name testing on the same field. */
856 /*===============================================*/
857
858 if ((*nodeSlotGroup == NULL) &&
859 (thePattern->index == (int) listOfNodes->whichField) &&
860 (thePattern->slotNumber == (int) listOfNodes->slotNameID))
861 *nodeSlotGroup = listOfNodes;
862 listOfNodes = listOfNodes->rightNode;
863 }
864
865 /*==============================================*/
866 /* A shareable pattern node could not be found. */
867 /*==============================================*/
868
869 return(NULL);
870 }
871
872 /*****************************************************************
873 NAME : CreateNewObjectPatternNode
874 DESCRIPTION : Creates a new pattern node and initializes
875 all of its values.
876 INPUTS : 1) The intermediate parse representation
877 of the new pattern node
878 2) A pointer to the network node after
879 which to add the new node
880 3) A pointer to the parent node on the
881 level above to link the new node
882 4) An integer code indicating if this is the last
883 fiedl in a slot pattern or not
884 RETURNS : A pointer to the new pattern node
885 SIDE EFFECTS : Pattern node allocated, initialized and
886 attached
887 NOTES : None
888 *****************************************************************/
CreateNewObjectPatternNode(void * theEnv,struct lhsParseNode * thePattern,OBJECT_PATTERN_NODE * nodeSlotGroup,OBJECT_PATTERN_NODE * upperLevel,unsigned endSlot,unsigned constantSelector)889 static OBJECT_PATTERN_NODE *CreateNewObjectPatternNode(
890 void *theEnv,
891 struct lhsParseNode *thePattern,
892 OBJECT_PATTERN_NODE *nodeSlotGroup,
893 OBJECT_PATTERN_NODE *upperLevel,
894 unsigned endSlot,
895 unsigned constantSelector)
896 {
897 OBJECT_PATTERN_NODE *newNode,*prvNode,*curNode;
898
899 newNode = get_struct(theEnv,objectPatternNode);
900 newNode->blocked = FALSE;
901 newNode->multifieldNode = FALSE;
902 newNode->alphaNode = NULL;
903 newNode->matchTimeTag = 0L;
904 newNode->nextLevel = NULL;
905 newNode->rightNode = NULL;
906 newNode->leftNode = NULL;
907 newNode->bsaveID = 0L;
908
909 if ((thePattern->constantSelector != NULL) && (! constantSelector))
910 { newNode->selector = TRUE; }
911 else
912 { newNode->selector = FALSE; }
913
914 /*===========================================================*/
915 /* Install the expression associated with this pattern node. */
916 /*===========================================================*/
917
918 if (constantSelector)
919 { newNode->networkTest = AddHashedExpression(theEnv,thePattern->constantValue); }
920 else if (thePattern->constantSelector != NULL)
921 { newNode->networkTest = AddHashedExpression(theEnv,thePattern->constantSelector); }
922 else
923 { newNode->networkTest = AddHashedExpression(theEnv,thePattern->networkTest); }
924
925 newNode->whichField = thePattern->index;
926 newNode->leaveFields = thePattern->singleFieldsAfter;
927
928 /*=========================================*/
929 /* Install the slot name for the new node. */
930 /*=========================================*/
931
932 newNode->slotNameID = (unsigned) thePattern->slotNumber;
933 if ((thePattern->type == MF_WILDCARD) || (thePattern->type == MF_VARIABLE))
934 newNode->multifieldNode = TRUE;
935 newNode->endSlot = endSlot;
936
937 /*===============================================*/
938 /* Set the upper level pointer for the new node. */
939 /*===============================================*/
940
941 newNode->lastLevel = upperLevel;
942
943 if ((upperLevel != NULL) && (upperLevel->selector))
944 { AddHashedPatternNode(theEnv,upperLevel,newNode,newNode->networkTest->type,newNode->networkTest->value); }
945
946 /*==============================================*/
947 /* If there are no nodes with this slot name on */
948 /* this level, simply prepend it to the front. */
949 /*==============================================*/
950
951 if (nodeSlotGroup == NULL)
952 {
953 if (upperLevel == NULL)
954 {
955 newNode->rightNode = ObjectNetworkPointer(theEnv);
956 SetObjectNetworkPointer(theEnv,newNode);
957 }
958 else
959 {
960 newNode->rightNode = upperLevel->nextLevel;
961 upperLevel->nextLevel = newNode;
962 }
963 if (newNode->rightNode != NULL)
964 newNode->rightNode->leftNode = newNode;
965 return(newNode);
966 }
967
968 /* ===========================================================
969 Group this node with other nodes of the same name
970 testing on the same field in the pattern
971 on this level. This allows us to do some optimization
972 with constant tests on a particular slots. If we put
973 all constant tests for a particular slot/field group at the
974 end of that group, then when one of those test succeeds
975 during pattern-matching, we don't have to test any
976 more of the nodes with that slot/field name to the right.
977 =========================================================== */
978 prvNode = NULL;
979 curNode = nodeSlotGroup;
980 while ((curNode == NULL) ? FALSE :
981 (curNode->slotNameID == nodeSlotGroup->slotNameID) &&
982 (curNode->whichField == nodeSlotGroup->whichField))
983 {
984 if ((curNode->networkTest == NULL) ? FALSE :
985 ((curNode->networkTest->type != OBJ_PN_CONSTANT) ? FALSE :
986 ((struct ObjectCmpPNConstant *) ValueToBitMap(curNode->networkTest->value))->pass))
987 break;
988 prvNode = curNode;
989 curNode = curNode->rightNode;
990 }
991 if (curNode != NULL)
992 {
993 newNode->leftNode = curNode->leftNode;
994 newNode->rightNode = curNode;
995 if (curNode->leftNode != NULL)
996 curNode->leftNode->rightNode = newNode;
997 else if (curNode->lastLevel != NULL)
998 curNode->lastLevel->nextLevel = newNode;
999 else
1000 SetObjectNetworkPointer(theEnv,newNode);
1001 curNode->leftNode = newNode;
1002 }
1003 else
1004 {
1005 newNode->leftNode = prvNode;
1006 prvNode->rightNode = newNode;
1007 }
1008
1009 return(newNode);
1010 }
1011
1012 /********************************************************
1013 NAME : DetachObjectPattern
1014 DESCRIPTION : Removes a pattern node and all of its
1015 parent nodes from the pattern network. Nodes are only
1016 removed if they are no longer shared (i.e. a pattern
1017 node that has more than one child node is shared). A
1018 pattern from a rule is typically removed by removing
1019 the bottom most pattern node used by the pattern and
1020 then removing any parent nodes which are not shared by
1021 other patterns.
1022
1023 Example:
1024 Patterns (a b c d) and (a b e f) would be represented
1025 by the pattern net shown on the left. If (a b c d)
1026 was detached, the resultant pattern net would be the
1027 one shown on the right. The '=' represents an
1028 end-of-pattern node.
1029
1030 a a
1031 | |
1032 b b
1033 | |
1034 c--e e
1035 | | |
1036 d f f
1037 | | |
1038 = = =
1039 INPUTS : The pattern to be removed
1040 RETURNS : Nothing useful
1041 SIDE EFFECTS : All non-shared nodes associated with the
1042 pattern are removed
1043 NOTES : None
1044 ********************************************************/
DetachObjectPattern(void * theEnv,struct patternNodeHeader * thePattern)1045 static void DetachObjectPattern(
1046 void *theEnv,
1047 struct patternNodeHeader *thePattern)
1048 {
1049 OBJECT_ALPHA_NODE *alphaPtr,*prv,*terminalPtr;
1050 OBJECT_PATTERN_NODE *patternPtr,*upperLevel;
1051
1052 /*====================================================*/
1053 /* Get rid of any matches stored in the alpha memory. */
1054 /*====================================================*/
1055
1056 alphaPtr = (OBJECT_ALPHA_NODE *) thePattern;
1057 ClearObjectPatternMatches(theEnv,alphaPtr);
1058
1059 /*========================================================*/
1060 /* Unmark the classes to which the pattern is applicable */
1061 /* and unmark the class and slot id maps so that they can */
1062 /* become ephemeral. */
1063 /*========================================================*/
1064
1065 MarkBitMapClassesBusy(theEnv,alphaPtr->classbmp,-1);
1066 DeleteClassBitMap(theEnv,alphaPtr->classbmp);
1067 if (alphaPtr->slotbmp != NULL)
1068 { DecrementBitMapCount(theEnv,alphaPtr->slotbmp); }
1069
1070 /*=========================================*/
1071 /* Only continue deleting this pattern if */
1072 /* this is the last alpha memory attached. */
1073 /*=========================================*/
1074
1075 prv = NULL;
1076 terminalPtr = ObjectNetworkTerminalPointer(theEnv);
1077 while (terminalPtr != alphaPtr)
1078 {
1079 prv = terminalPtr;
1080 terminalPtr = terminalPtr->nxtTerminal;
1081 }
1082
1083 if (prv == NULL)
1084 { SetObjectNetworkTerminalPointer(theEnv,terminalPtr->nxtTerminal); }
1085 else
1086 { prv->nxtTerminal = terminalPtr->nxtTerminal; }
1087
1088 prv = NULL;
1089 terminalPtr = alphaPtr->patternNode->alphaNode;
1090 while (terminalPtr != alphaPtr)
1091 {
1092 prv = terminalPtr;
1093 terminalPtr = terminalPtr->nxtInGroup;
1094 }
1095
1096 if (prv == NULL)
1097 {
1098 if (alphaPtr->nxtInGroup != NULL)
1099 {
1100 alphaPtr->patternNode->alphaNode = alphaPtr->nxtInGroup;
1101 RemoveHashedExpression(theEnv,alphaPtr->header.rightHash);
1102 rtn_struct(theEnv,objectAlphaNode,alphaPtr);
1103 return;
1104 }
1105 }
1106 else
1107 {
1108 prv->nxtInGroup = alphaPtr->nxtInGroup;
1109 RemoveHashedExpression(theEnv,alphaPtr->header.rightHash);
1110 rtn_struct(theEnv,objectAlphaNode,alphaPtr);
1111 return;
1112 }
1113 alphaPtr->patternNode->alphaNode = NULL;
1114 RemoveHashedExpression(theEnv,alphaPtr->header.rightHash);
1115 upperLevel = alphaPtr->patternNode;
1116 rtn_struct(theEnv,objectAlphaNode,alphaPtr);
1117
1118 if (upperLevel->nextLevel != NULL)
1119 return;
1120
1121 /*==============================================================*/
1122 /* Loop until all appropriate pattern nodes have been detached. */
1123 /*==============================================================*/
1124
1125 while (upperLevel != NULL)
1126 {
1127 if ((upperLevel->leftNode == NULL) &&
1128 (upperLevel->rightNode == NULL))
1129 {
1130 /*===============================================*/
1131 /* Pattern node is the only node on this level. */
1132 /* Remove it and continue detaching other nodes */
1133 /* above this one, because no other patterns are */
1134 /* dependent upon this node. */
1135 /*===============================================*/
1136
1137 patternPtr = upperLevel;
1138 upperLevel = patternPtr->lastLevel;
1139
1140 if (upperLevel == NULL)
1141 SetObjectNetworkPointer(theEnv,NULL);
1142 else
1143 {
1144 if (upperLevel->selector)
1145 { RemoveHashedPatternNode(theEnv,upperLevel,patternPtr,patternPtr->networkTest->type,patternPtr->networkTest->value); }
1146
1147 upperLevel->nextLevel = NULL;
1148 if (upperLevel->alphaNode != NULL)
1149 upperLevel = NULL;
1150 }
1151
1152 RemoveHashedExpression(theEnv,(EXPRESSION *) patternPtr->networkTest);
1153 rtn_struct(theEnv,objectPatternNode,patternPtr);
1154 }
1155 else if (upperLevel->leftNode != NULL)
1156 {
1157 /*====================================================*/
1158 /* Pattern node has another pattern node which must */
1159 /* be checked preceding it. Remove the pattern node, */
1160 /* but do not detach any nodes above this one. */
1161 /*====================================================*/
1162
1163 patternPtr = upperLevel;
1164
1165 if ((patternPtr->lastLevel != NULL) &&
1166 (patternPtr->lastLevel->selector))
1167 { RemoveHashedPatternNode(theEnv,patternPtr->lastLevel,patternPtr,patternPtr->networkTest->type,patternPtr->networkTest->value); }
1168
1169 upperLevel->leftNode->rightNode = upperLevel->rightNode;
1170 if (upperLevel->rightNode != NULL)
1171 { upperLevel->rightNode->leftNode = upperLevel->leftNode; }
1172
1173 RemoveHashedExpression(theEnv,(EXPRESSION *) patternPtr->networkTest);
1174 rtn_struct(theEnv,objectPatternNode,patternPtr);
1175 upperLevel = NULL;
1176 }
1177 else
1178 {
1179 /*====================================================*/
1180 /* Pattern node has no pattern node preceding it, but */
1181 /* does have one succeeding it. Remove the pattern */
1182 /* node, but do not detach any nodes above this one. */
1183 /*====================================================*/
1184
1185 patternPtr = upperLevel;
1186 upperLevel = upperLevel->lastLevel;
1187 if (upperLevel == NULL)
1188 { SetObjectNetworkPointer(theEnv,patternPtr->rightNode); }
1189 else
1190 {
1191 if (upperLevel->selector)
1192 { RemoveHashedPatternNode(theEnv,upperLevel,patternPtr,patternPtr->networkTest->type,patternPtr->networkTest->value); }
1193
1194 upperLevel->nextLevel = patternPtr->rightNode;
1195 }
1196 patternPtr->rightNode->leftNode = NULL;
1197
1198 RemoveHashedExpression(theEnv,(EXPRESSION *) patternPtr->networkTest);
1199 rtn_struct(theEnv,objectPatternNode,patternPtr);
1200 upperLevel = NULL;
1201 }
1202 }
1203 }
1204
1205 /***************************************************
1206 NAME : ClearObjectPatternMatches
1207 DESCRIPTION : Removes a pattern node alpha memory
1208 from the list of partial matches
1209 on all instances (active or
1210 garbage collected)
1211 INPUTS : The pattern node to remove
1212 RETURNS : Nothing useful
1213 SIDE EFFECTS : Pattern alpha memory removed
1214 from all object partial match lists
1215 NOTES : Used when a pattern is removed
1216 ***************************************************/
ClearObjectPatternMatches(void * theEnv,OBJECT_ALPHA_NODE * alphaPtr)1217 static void ClearObjectPatternMatches(
1218 void *theEnv,
1219 OBJECT_ALPHA_NODE *alphaPtr)
1220 {
1221 INSTANCE_TYPE *ins;
1222 IGARBAGE *igrb;
1223
1224 /* =============================================
1225 Loop through every active and queued instance
1226 ============================================= */
1227 ins = InstanceData(theEnv)->InstanceList;
1228 while (ins != NULL)
1229 {
1230 RemoveObjectPartialMatches(theEnv,(INSTANCE_TYPE *) ins,(struct patternNodeHeader *) alphaPtr);
1231 ins = ins->nxtList;
1232 }
1233
1234 /* ============================
1235 Check for garbaged instances
1236 ============================ */
1237 igrb = InstanceData(theEnv)->InstanceGarbageList;
1238 while (igrb != NULL)
1239 {
1240 RemoveObjectPartialMatches(theEnv,(INSTANCE_TYPE *) igrb->ins,(struct patternNodeHeader *) alphaPtr);
1241 igrb = igrb->nxt;
1242 }
1243 }
1244
1245 /***************************************************
1246 NAME : RemoveObjectPartialMatches
1247 DESCRIPTION : Removes a partial match from a
1248 list of partial matches for
1249 an instance
1250 INPUTS : 1) The instance
1251 2) The pattern node header
1252 corresponding to the match
1253 RETURNS : Nothing useful
1254 SIDE EFFECTS : Match removed
1255 NOTES : None
1256 ***************************************************/
RemoveObjectPartialMatches(void * theEnv,INSTANCE_TYPE * ins,struct patternNodeHeader * phead)1257 static void RemoveObjectPartialMatches(
1258 void *theEnv,
1259 INSTANCE_TYPE *ins,
1260 struct patternNodeHeader *phead)
1261 {
1262 struct patternMatch *match_before, *match_ptr;
1263
1264 match_before = NULL;
1265 match_ptr = (struct patternMatch *) ins->partialMatchList;
1266
1267 /* =======================================
1268 Loop through every match for the object
1269 ======================================= */
1270 while (match_ptr != NULL)
1271 {
1272 if (match_ptr->matchingPattern == phead)
1273 {
1274 ins->busy--;
1275 if (match_before == NULL)
1276 {
1277 ins->partialMatchList = (void *) match_ptr->next;
1278 rtn_struct(theEnv,patternMatch,match_ptr);
1279 match_ptr = (struct patternMatch *) ins->partialMatchList;
1280 }
1281 else
1282 {
1283 match_before->next = match_ptr->next;
1284 rtn_struct(theEnv,patternMatch,match_ptr);
1285 match_ptr = match_before->next;
1286 }
1287 }
1288 else
1289 {
1290 match_before = match_ptr;
1291 match_ptr = match_ptr->next;
1292 }
1293 }
1294 }
1295
1296 /******************************************************
1297 NAME : CheckDuplicateSlots
1298 DESCRIPTION : Determines if a restriction has
1299 already been defined in a pattern
1300 INPUTS : The list of already built restrictions
1301 RETURNS : TRUE if a definition already
1302 exists, FALSE otherwise
1303 SIDE EFFECTS : An error message is printed if a
1304 duplicate is found
1305 NOTES : None
1306 ******************************************************/
CheckDuplicateSlots(void * theEnv,struct lhsParseNode * nodeList,SYMBOL_HN * slotName)1307 static intBool CheckDuplicateSlots(
1308 void *theEnv,
1309 struct lhsParseNode *nodeList,
1310 SYMBOL_HN *slotName)
1311 {
1312 while (nodeList != NULL)
1313 {
1314 if (nodeList->slot == slotName)
1315 {
1316 PrintErrorID(theEnv,"OBJRTBLD",4,TRUE);
1317 EnvPrintRouter(theEnv,WERROR,"Multiple restrictions on attribute ");
1318 EnvPrintRouter(theEnv,WERROR,ValueToString(slotName));
1319 EnvPrintRouter(theEnv,WERROR," not allowed.\n");
1320 return(TRUE);
1321 }
1322 nodeList = nodeList->right;
1323 }
1324 return(FALSE);
1325 }
1326
1327 /**********************************************************
1328 NAME : ParseClassRestriction
1329 DESCRIPTION : Parses the single-field constraint
1330 on the class an object pattern
1331 INPUTS : 1) The logical input source
1332 2) A buffer for tokens
1333 RETURNS : The intermediate pattern nodes
1334 representing the class constraint
1335 (NULL on errors)
1336 SIDE EFFECTS : Intermediate pattern nodes allocated
1337 NOTES : None
1338 **********************************************************/
ParseClassRestriction(void * theEnv,const char * readSource,struct token * theToken)1339 static struct lhsParseNode *ParseClassRestriction(
1340 void *theEnv,
1341 const char *readSource,
1342 struct token *theToken)
1343 {
1344 struct lhsParseNode *tmpNode;
1345 SYMBOL_HN *rln;
1346 CONSTRAINT_RECORD *rv;
1347
1348 rv = GetConstraintRecord(theEnv);
1349 rv->anyAllowed = 0;
1350 rv->symbolsAllowed = 1;
1351 rln = (SYMBOL_HN *) theToken->value;
1352 SavePPBuffer(theEnv," ");
1353 GetToken(theEnv,readSource,theToken);
1354 tmpNode = RestrictionParse(theEnv,readSource,theToken,FALSE,rln,ISA_ID,rv,0);
1355 if (tmpNode == NULL)
1356 {
1357 RemoveConstraint(theEnv,rv);
1358 return(NULL);
1359 }
1360 if ((theToken->type != RPAREN) ||
1361 (tmpNode->type == MF_WILDCARD) ||
1362 (tmpNode->type == MF_VARIABLE))
1363 {
1364 PPBackup(theEnv);
1365 if (theToken->type != RPAREN)
1366 {
1367 SavePPBuffer(theEnv," ");
1368 SavePPBuffer(theEnv,theToken->printForm);
1369 }
1370 SyntaxErrorMessage(theEnv,"class restriction in object pattern");
1371 ReturnLHSParseNodes(theEnv,tmpNode);
1372 RemoveConstraint(theEnv,rv);
1373 return(NULL);
1374 }
1375 tmpNode->derivedConstraints = 1;
1376 return(tmpNode);
1377 }
1378
1379 /**********************************************************
1380 NAME : ParseNameRestriction
1381 DESCRIPTION : Parses the single-field constraint
1382 on the name of an object pattern
1383 INPUTS : 1) The logical input source
1384 2) A buffer for tokens
1385 RETURNS : The intermediate pattern nodes
1386 representing the name constraint
1387 (NULL on errors)
1388 SIDE EFFECTS : Intermediate pattern nodes allocated
1389 NOTES : None
1390 **********************************************************/
ParseNameRestriction(void * theEnv,const char * readSource,struct token * theToken)1391 static struct lhsParseNode *ParseNameRestriction(
1392 void *theEnv,
1393 const char *readSource,
1394 struct token *theToken)
1395 {
1396 struct lhsParseNode *tmpNode;
1397 SYMBOL_HN *rln;
1398 CONSTRAINT_RECORD *rv;
1399
1400 rv = GetConstraintRecord(theEnv);
1401 rv->anyAllowed = 0;
1402 rv->instanceNamesAllowed = 1;
1403 rln = (SYMBOL_HN *) theToken->value;
1404 SavePPBuffer(theEnv," ");
1405 GetToken(theEnv,readSource,theToken);
1406 tmpNode = RestrictionParse(theEnv,readSource,theToken,FALSE,rln,NAME_ID,rv,0);
1407 if (tmpNode == NULL)
1408 {
1409 RemoveConstraint(theEnv,rv);
1410 return(NULL);
1411 }
1412 if ((theToken->type != RPAREN) ||
1413 (tmpNode->type == MF_WILDCARD) ||
1414 (tmpNode->type == MF_VARIABLE))
1415 {
1416 PPBackup(theEnv);
1417 if (theToken->type != RPAREN)
1418 {
1419 SavePPBuffer(theEnv," ");
1420 SavePPBuffer(theEnv,theToken->printForm);
1421 }
1422 SyntaxErrorMessage(theEnv,"name restriction in object pattern");
1423 ReturnLHSParseNodes(theEnv,tmpNode);
1424 RemoveConstraint(theEnv,rv);
1425 return(NULL);
1426 }
1427
1428 tmpNode->derivedConstraints = 1;
1429 return(tmpNode);
1430 }
1431
1432 /***************************************************
1433 NAME : ParseSlotRestriction
1434 DESCRIPTION : Parses the field constraint(s)
1435 on a slot of an object pattern
1436 INPUTS : 1) The logical input source
1437 2) A buffer for tokens
1438 3) Constraint record holding the
1439 unioned constraints of all the
1440 slots which could match the
1441 slot pattern
1442 4) A flag indicating if any
1443 multifield slots match the name
1444 RETURNS : The intermediate pattern nodes
1445 representing the slot constraint(s)
1446 (NULL on errors)
1447 SIDE EFFECTS : Intermediate pattern nodes
1448 allocated
1449 NOTES : None
1450 ***************************************************/
ParseSlotRestriction(void * theEnv,const char * readSource,struct token * theToken,CONSTRAINT_RECORD * slotConstraints,int multip)1451 static struct lhsParseNode *ParseSlotRestriction(
1452 void *theEnv,
1453 const char *readSource,
1454 struct token *theToken,
1455 CONSTRAINT_RECORD *slotConstraints,
1456 int multip)
1457 {
1458 struct lhsParseNode *tmpNode;
1459 SYMBOL_HN *slotName;
1460
1461 slotName = (SYMBOL_HN *) theToken->value;
1462 SavePPBuffer(theEnv," ");
1463 GetToken(theEnv,readSource,theToken);
1464 tmpNode = RestrictionParse(theEnv,readSource,theToken,multip,slotName,FindSlotNameID(theEnv,slotName),
1465 slotConstraints,1);
1466 if (tmpNode == NULL)
1467 {
1468 RemoveConstraint(theEnv,slotConstraints);
1469 return(NULL);
1470 }
1471 if (theToken->type != RPAREN)
1472 {
1473 PPBackup(theEnv);
1474 SavePPBuffer(theEnv," ");
1475 SavePPBuffer(theEnv,theToken->printForm);
1476 SyntaxErrorMessage(theEnv,"object slot pattern");
1477 ReturnLHSParseNodes(theEnv,tmpNode);
1478 RemoveConstraint(theEnv,slotConstraints);
1479 return(NULL);
1480 }
1481 if ((tmpNode->bottom == NULL) && (tmpNode->multifieldSlot))
1482 {
1483 PPBackup(theEnv);
1484 PPBackup(theEnv);
1485 SavePPBuffer(theEnv,")");
1486 }
1487 tmpNode->derivedConstraints = 1;
1488 return(tmpNode);
1489 }
1490
1491 /********************************************************
1492 NAME : NewClassBitMap
1493 DESCRIPTION : Creates a new bitmap large enough
1494 to hold all ids of classes in the
1495 system and initializes all the bits
1496 to zero or one.
1497 INPUTS : 1) The maximum id that will be set
1498 in the bitmap
1499 2) An integer code indicating if all
1500 the bits are to be set to zero or one
1501 RETURNS : The new bitmap
1502 SIDE EFFECTS : BitMap allocated and initialized
1503 NOTES : None
1504 ********************************************************/
NewClassBitMap(void * theEnv,int maxid,int set)1505 static CLASS_BITMAP *NewClassBitMap(
1506 void *theEnv,
1507 int maxid,
1508 int set)
1509 {
1510 register CLASS_BITMAP *bmp;
1511 unsigned size;
1512
1513 if (maxid == -1)
1514 maxid = 0;
1515 size = sizeof(CLASS_BITMAP) +
1516 (sizeof(char) * (maxid / BITS_PER_BYTE));
1517 bmp = (CLASS_BITMAP *) gm2(theEnv,size);
1518 ClearBitString((void *) bmp,size);
1519 bmp->maxid = (unsigned short) maxid;
1520 InitializeClassBitMap(theEnv,bmp,set);
1521 return(bmp);
1522 }
1523
1524 /***********************************************************
1525 NAME : InitializeClassBitMap
1526 DESCRIPTION : Initializes a bitmap to all zeroes or ones.
1527 INPUTS : 1) The bitmap
1528 2) An integer code indicating if all
1529 the bits are to be set to zero or one
1530 RETURNS : Nothing useful
1531 SIDE EFFECTS : The bitmap is initialized
1532 NOTES : None
1533 ***********************************************************/
InitializeClassBitMap(void * theEnv,CLASS_BITMAP * bmp,int set)1534 static void InitializeClassBitMap(
1535 void *theEnv,
1536 CLASS_BITMAP *bmp,
1537 int set)
1538 {
1539 register int i,bytes;
1540 DEFCLASS *cls;
1541 struct defmodule *currentModule;
1542
1543 bytes = bmp->maxid / BITS_PER_BYTE + 1;
1544 while (bytes > 0)
1545 {
1546 bmp->map[bytes - 1] = (char) 0;
1547 bytes--;
1548 }
1549 if (set)
1550 {
1551 currentModule = ((struct defmodule *) EnvGetCurrentModule(theEnv));
1552 for (i = 0 ; i <= (int) bmp->maxid ; i++)
1553 {
1554 cls = DefclassData(theEnv)->ClassIDMap[i];
1555 if ((cls != NULL) ? DefclassInScope(theEnv,cls,currentModule) : FALSE)
1556 {
1557 if (cls->reactive && (cls->abstract == 0))
1558 SetBitMap(bmp->map,i);
1559 }
1560 }
1561 }
1562 }
1563
1564 /********************************************
1565 NAME : DeleteIntermediateClassBitMap
1566 DESCRIPTION : Deallocates a bitmap
1567 INPUTS : The class set
1568 RETURNS : Nothing useful
1569 SIDE EFFECTS : Class set deallocated
1570 NOTES : None
1571 ********************************************/
DeleteIntermediateClassBitMap(void * theEnv,CLASS_BITMAP * bmp)1572 static void DeleteIntermediateClassBitMap(
1573 void *theEnv,
1574 CLASS_BITMAP *bmp)
1575 {
1576 rm(theEnv,(void *) bmp,ClassBitMapSize(bmp));
1577 }
1578
1579 /******************************************************
1580 NAME : CopyClassBitMap
1581 DESCRIPTION : Increments the in use count of a
1582 bitmap and returns the same pointer
1583 INPUTS : The bitmap
1584 RETURNS : The bitmap
1585 SIDE EFFECTS : Increments the in use count
1586 NOTES : Class sets are shared by multiple
1587 copies of an object pattern within an
1588 OR CE. The use count prevents having
1589 to make duplicate copies of the bitmap
1590 ******************************************************/
CopyClassBitMap(void * theEnv,void * gset)1591 static void *CopyClassBitMap(
1592 void *theEnv,
1593 void *gset)
1594 {
1595 #if MAC_XCD
1596 #pragma unused(theEnv)
1597 #endif
1598
1599 if (gset != NULL)
1600 IncrementBitMapCount(gset);
1601 return(gset);
1602 }
1603
1604 /**********************************************************
1605 NAME : DeleteClassBitMap
1606 DESCRIPTION : Deallocates a bitmap,
1607 and decrements the busy flags of the
1608 classes marked in the bitmap
1609 INPUTS : The bitmap
1610 RETURNS : Nothing useful
1611 SIDE EFFECTS : Class set deallocated and classes unmarked
1612 NOTES : None
1613 **********************************************************/
DeleteClassBitMap(void * theEnv,void * gset)1614 static void DeleteClassBitMap(
1615 void *theEnv,
1616 void *gset)
1617 {
1618 if (gset == NULL)
1619 return;
1620 DecrementBitMapCount(theEnv,(BITMAP_HN *) gset);
1621 }
1622
1623 /***************************************************
1624 NAME : MarkBitMapClassesBusy
1625 DESCRIPTION : Increments/Decrements busy counts
1626 of all classes marked in a bitmap
1627 INPUTS : 1) The bitmap hash node
1628 2) 1 or -1 (to increment or
1629 decrement class busy counts)
1630 RETURNS : Nothing useful
1631 SIDE EFFECTS : Bitmap class busy counts updated
1632 NOTES : None
1633 ***************************************************/
MarkBitMapClassesBusy(void * theEnv,BITMAP_HN * bmphn,int offset)1634 static void MarkBitMapClassesBusy(
1635 void *theEnv,
1636 BITMAP_HN *bmphn,
1637 int offset)
1638 {
1639 register CLASS_BITMAP *bmp;
1640 register unsigned short i;
1641 register DEFCLASS *cls;
1642
1643 /* ====================================
1644 If a clear is in progress, we do not
1645 have to worry about busy counts
1646 ==================================== */
1647 if (ConstructData(theEnv)->ClearInProgress)
1648 return;
1649 bmp = (CLASS_BITMAP *) ValueToBitMap(bmphn);
1650 for (i = 0 ; i <= bmp->maxid ; i++)
1651 if (TestBitMap(bmp->map,i))
1652 {
1653 cls = DefclassData(theEnv)->ClassIDMap[i];
1654 cls->busy += (unsigned int) offset;
1655 }
1656 }
1657
1658 /****************************************************
1659 NAME : EmptyClassBitMap
1660 DESCRIPTION : Determines if one or more bits
1661 are marked in a bitmap
1662 INPUTS : The bitmap
1663 RETURNS : TRUE if the set has no bits
1664 marked, FALSE otherwise
1665 SIDE EFFECTS : None
1666 NOTES : None
1667 ****************************************************/
EmptyClassBitMap(CLASS_BITMAP * bmp)1668 static intBool EmptyClassBitMap(
1669 CLASS_BITMAP *bmp)
1670 {
1671 register unsigned short bytes;
1672
1673 bytes = (unsigned short) (bmp->maxid / BITS_PER_BYTE + 1);
1674 while (bytes > 0)
1675 {
1676 if (bmp->map[bytes - 1] != (char) 0)
1677 return(FALSE);
1678 bytes--;
1679 }
1680 return(TRUE);
1681 }
1682
1683 /***************************************************
1684 NAME : IdenticalClassBitMap
1685 DESCRIPTION : Determines if two bitmaps
1686 are identical
1687 INPUTS : 1) First bitmap
1688 2) Second bitmap
1689 RETURNS : TRUE if bitmaps are the same,
1690 FALSE otherwise
1691 SIDE EFFECTS : None
1692 NOTES : None
1693 ***************************************************/
IdenticalClassBitMap(CLASS_BITMAP * cs1,CLASS_BITMAP * cs2)1694 static intBool IdenticalClassBitMap(
1695 CLASS_BITMAP *cs1,
1696 CLASS_BITMAP *cs2)
1697 {
1698 register int i;
1699
1700 if (cs1->maxid != cs2->maxid)
1701 return(FALSE);
1702 for (i = 0 ; i < (int) (cs1->maxid / BITS_PER_BYTE + 1) ; i++)
1703 if (cs1->map[i] != cs2->map[i])
1704 return(FALSE);
1705 return(TRUE);
1706 }
1707
1708 /*****************************************************************
1709 NAME : ProcessClassRestriction
1710 DESCRIPTION : Examines a class restriction and forms a bitmap
1711 corresponding to the maximal set of classes which
1712 can satisfy a static analysis of the restriction
1713 INPUTS : 1) The bitmap to mark classes in
1714 2) The lhsParseNodes of the restriction
1715 3) A flag indicating if this is the first
1716 non-recursive call or not
1717 RETURNS : TRUE if all OK, FALSE otherwise
1718 SIDE EFFECTS : Class bitmap set and lhsParseNodes corressponding
1719 to constant restrictions are removed
1720 NOTES : None
1721 *****************************************************************/
ProcessClassRestriction(void * theEnv,CLASS_BITMAP * clsset,struct lhsParseNode ** classRestrictions,int recursiveCall)1722 static intBool ProcessClassRestriction(
1723 void *theEnv,
1724 CLASS_BITMAP *clsset,
1725 struct lhsParseNode **classRestrictions,
1726 int recursiveCall)
1727 {
1728 register struct lhsParseNode *chk,**oraddr;
1729 CLASS_BITMAP *tmpset1,*tmpset2;
1730 int constant_restriction = TRUE;
1731
1732 if (*classRestrictions == NULL)
1733 {
1734 if (recursiveCall)
1735 InitializeClassBitMap(theEnv,clsset,1);
1736 return(TRUE);
1737 }
1738
1739 /* ===============================================
1740 Determine the corresponding class set and union
1741 it with the current total class set. If an AND
1742 restriction is comprised entirely of symbols,
1743 it can be removed
1744 =============================================== */
1745 tmpset1 = NewClassBitMap(theEnv,((int) DefclassData(theEnv)->MaxClassID) - 1,1);
1746 tmpset2 = NewClassBitMap(theEnv,((int) DefclassData(theEnv)->MaxClassID) - 1,0);
1747 for (chk = *classRestrictions ; chk != NULL ; chk = chk->right)
1748 {
1749 if (chk->type == SYMBOL)
1750 {
1751 //chk->value = (void *) LookupDefclassInScope(theEnv,ValueToString(chk->value));
1752 chk->value = (void *) LookupDefclassByMdlOrScope(theEnv,ValueToString(chk->value));
1753 if (chk->value == NULL)
1754 {
1755 PrintErrorID(theEnv,"OBJRTBLD",5,FALSE);
1756 EnvPrintRouter(theEnv,WERROR,"Undefined class in object pattern.\n");
1757 DeleteIntermediateClassBitMap(theEnv,tmpset1);
1758 DeleteIntermediateClassBitMap(theEnv,tmpset2);
1759 return(FALSE);
1760 }
1761 if (chk->negated)
1762 {
1763 InitializeClassBitMap(theEnv,tmpset2,1);
1764 MarkBitMapSubclasses(tmpset2->map,(DEFCLASS *) chk->value,0);
1765 }
1766 else
1767 {
1768 InitializeClassBitMap(theEnv,tmpset2,0);
1769 MarkBitMapSubclasses(tmpset2->map,(DEFCLASS *) chk->value,1);
1770 }
1771 IntersectClassBitMaps(tmpset1,tmpset2);
1772 }
1773 else
1774 constant_restriction = FALSE;
1775 }
1776 if (EmptyClassBitMap(tmpset1))
1777 {
1778 PrintErrorID(theEnv,"OBJRTBLD",2,FALSE);
1779 EnvPrintRouter(theEnv,WERROR,"No objects of existing classes can satisfy ");
1780 EnvPrintRouter(theEnv,WERROR,"is-a restriction in object pattern.\n");
1781 DeleteIntermediateClassBitMap(theEnv,tmpset1);
1782 DeleteIntermediateClassBitMap(theEnv,tmpset2);
1783 return(FALSE);
1784 }
1785 if (constant_restriction)
1786 {
1787 chk = *classRestrictions;
1788 *classRestrictions = chk->bottom;
1789 chk->bottom = NULL;
1790 ReturnLHSParseNodes(theEnv,chk);
1791 oraddr = classRestrictions;
1792 }
1793 else
1794 oraddr = &(*classRestrictions)->bottom;
1795 UnionClassBitMaps(clsset,tmpset1);
1796 DeleteIntermediateClassBitMap(theEnv,tmpset1);
1797 DeleteIntermediateClassBitMap(theEnv,tmpset2);
1798
1799 /* =====================================
1800 Process the next OR class restriction
1801 ===================================== */
1802 return(ProcessClassRestriction(theEnv,clsset,oraddr,FALSE));
1803 }
1804
1805 /****************************************************************
1806 NAME : ProcessSlotRestriction
1807 DESCRIPTION : Determines which slots could match the slot
1808 pattern and determines the union of all
1809 constraints for the pattern
1810 INPUTS : 1) The class set
1811 2) The slot name
1812 3) A buffer to hold a flag indicating if
1813 any multifield slots are found w/ this name
1814 RETURNS : A union of the constraints on all the slots
1815 which could match the slots (NULL if no
1816 slots found)
1817 SIDE EFFECTS : The class bitmap set is marked/cleared
1818 NOTES : None
1819 ****************************************************************/
ProcessSlotRestriction(void * theEnv,CLASS_BITMAP * clsset,SYMBOL_HN * slotName,int * multip)1820 static CONSTRAINT_RECORD *ProcessSlotRestriction(
1821 void *theEnv,
1822 CLASS_BITMAP *clsset,
1823 SYMBOL_HN *slotName,
1824 int *multip)
1825 {
1826 register DEFCLASS *cls;
1827 register int si;
1828 CONSTRAINT_RECORD *totalConstraints = NULL,*tmpConstraints;
1829 register unsigned i;
1830
1831 *multip = FALSE;
1832 for (i = 0 ; i < CLASS_TABLE_HASH_SIZE ; i++)
1833 for (cls = DefclassData(theEnv)->ClassTable[i] ; cls != NULL ; cls = cls->nxtHash)
1834 {
1835 if (TestBitMap(clsset->map,cls->id))
1836 {
1837 si = FindInstanceTemplateSlot(theEnv,cls,slotName);
1838 if ((si != -1) ? cls->instanceTemplate[si]->reactive : FALSE)
1839 {
1840 if (cls->instanceTemplate[si]->multiple)
1841 *multip = TRUE;
1842 tmpConstraints =
1843 UnionConstraints(theEnv,cls->instanceTemplate[si]->constraint,totalConstraints);
1844 RemoveConstraint(theEnv,totalConstraints);
1845 totalConstraints = tmpConstraints;
1846 }
1847 else
1848 ClearBitMap(clsset->map,cls->id);
1849 }
1850 }
1851 return(totalConstraints);
1852 }
1853
1854 /****************************************************
1855 NAME : IntersectClassBitMaps
1856 DESCRIPTION : Bitwise-ands two bitmaps and stores
1857 the result in the first
1858 INPUTS : The two bitmaps
1859 RETURNS : Nothing useful
1860 SIDE EFFECTS : ClassBitMaps anded
1861 NOTES : Assumes the first bitmap is at least
1862 as large as the second
1863 ****************************************************/
IntersectClassBitMaps(CLASS_BITMAP * cs1,CLASS_BITMAP * cs2)1864 static void IntersectClassBitMaps(
1865 CLASS_BITMAP *cs1,
1866 CLASS_BITMAP *cs2)
1867 {
1868 register unsigned short bytes;
1869
1870 bytes = (unsigned short) (cs2->maxid / BITS_PER_BYTE + 1);
1871 while (bytes > 0)
1872 {
1873 cs1->map[bytes - 1] &= cs2->map[bytes - 1];
1874 bytes--;
1875 }
1876 }
1877
1878 /****************************************************
1879 NAME : UnionClassBitMaps
1880 DESCRIPTION : Bitwise-ors two bitmaps and stores
1881 the result in the first
1882 INPUTS : The two bitmaps
1883 RETURNS : Nothing useful
1884 SIDE EFFECTS : ClassBitMaps ored
1885 NOTES : Assumes the first bitmap is at least
1886 as large as the second
1887 ****************************************************/
UnionClassBitMaps(CLASS_BITMAP * cs1,CLASS_BITMAP * cs2)1888 static void UnionClassBitMaps(
1889 CLASS_BITMAP *cs1,
1890 CLASS_BITMAP *cs2)
1891 {
1892 register unsigned short bytes;
1893
1894 bytes = (unsigned short) (cs2->maxid / BITS_PER_BYTE + 1);
1895 while (bytes > 0)
1896 {
1897 cs1->map[bytes - 1] |= cs2->map[bytes - 1];
1898 bytes--;
1899 }
1900 }
1901
1902 /*****************************************************
1903 NAME : PackClassBitMap
1904 DESCRIPTION : This routine packs a bitmap
1905 bitmap such that at least one of
1906 the bits in the rightmost byte is
1907 set (i.e. the bitmap takes up
1908 the smallest space possible).
1909 INPUTS : The bitmap
1910 RETURNS : The new (packed) bitmap
1911 SIDE EFFECTS : The oldset is deallocated
1912 NOTES : None
1913 *****************************************************/
PackClassBitMap(void * theEnv,CLASS_BITMAP * oldset)1914 static CLASS_BITMAP *PackClassBitMap(
1915 void *theEnv,
1916 CLASS_BITMAP *oldset)
1917 {
1918 register unsigned short newmaxid;
1919 CLASS_BITMAP *newset;
1920
1921 for (newmaxid = oldset->maxid ; newmaxid > 0 ; newmaxid--)
1922 if (TestBitMap(oldset->map,newmaxid))
1923 break;
1924 if (newmaxid != oldset->maxid)
1925 {
1926 newset = NewClassBitMap(theEnv,(int) newmaxid,0);
1927 GenCopyMemory(char,newmaxid / BITS_PER_BYTE + 1,newset->map,oldset->map);
1928 DeleteIntermediateClassBitMap(theEnv,oldset);
1929 }
1930 else
1931 newset = oldset;
1932 return(newset);
1933 }
1934
1935 /*****************************************************************
1936 NAME : FilterObjectPattern
1937 DESCRIPTION : Appends an extra node to hold the bitmap,
1938 and finds is-a and name nodes
1939 INPUTS : 1) The object pattern parser address
1940 to give to a default is-a slot
1941 2) The unfiltered slot list
1942 3) A buffer to hold the address of
1943 the class bitmap restriction node
1944 4) A buffer to hold the address of
1945 the is-a restriction node
1946 4) A buffer to hold the address of
1947 the name restriction node
1948 RETURNS : The filtered slot list
1949 SIDE EFFECTS : clsset is attached to extra slot pattern
1950 Pointers to the is-a and name slots are also
1951 stored (if they exist) for easy reference
1952 NOTES : None
1953 *****************************************************************/
FilterObjectPattern(void * theEnv,struct patternParser * selfPatternType,struct lhsParseNode * unfilteredSlots,struct lhsParseNode ** bitmap_slot,struct lhsParseNode ** isa_slot,struct lhsParseNode ** name_slot)1954 static struct lhsParseNode *FilterObjectPattern(
1955 void *theEnv,
1956 struct patternParser *selfPatternType,
1957 struct lhsParseNode *unfilteredSlots,
1958 struct lhsParseNode **bitmap_slot,
1959 struct lhsParseNode **isa_slot,
1960 struct lhsParseNode **name_slot)
1961 {
1962 struct lhsParseNode *prv,*cur;
1963
1964 *isa_slot = NULL;
1965 *name_slot = NULL;
1966
1967 /* ============================================
1968 Create a dummy node to attach to the end
1969 of the pattern which holds the class bitmap.
1970 ============================================ */
1971 *bitmap_slot = GetLHSParseNode(theEnv);
1972 (*bitmap_slot)->type = SF_WILDCARD;
1973 (*bitmap_slot)->slot = DefclassData(theEnv)->ISA_SYMBOL;
1974 (*bitmap_slot)->slotNumber = ISA_ID;
1975 (*bitmap_slot)->index = 1;
1976 (*bitmap_slot)->patternType = selfPatternType;
1977 (*bitmap_slot)->userData = unfilteredSlots->userData;
1978 unfilteredSlots->userData = NULL;
1979
1980 /* ========================
1981 Find is-a and name nodes
1982 ======================== */
1983 prv = NULL;
1984 cur = unfilteredSlots;
1985 while (cur != NULL)
1986 {
1987 if (cur->slot == DefclassData(theEnv)->ISA_SYMBOL)
1988 *isa_slot = cur;
1989 else if (cur->slot == DefclassData(theEnv)->NAME_SYMBOL)
1990 *name_slot = cur;
1991 prv = cur;
1992 cur = cur->right;
1993 }
1994
1995 /* ================================
1996 Add the class bitmap conditional
1997 element to end of pattern
1998 ================================ */
1999 if (prv == NULL)
2000 unfilteredSlots = *bitmap_slot;
2001 else
2002 prv->right = *bitmap_slot;
2003 return(unfilteredSlots);
2004 }
2005
2006 /***************************************************
2007 NAME : FormSlotBitMap
2008 DESCRIPTION : Examines an object pattern and
2009 forms a minimal bitmap marking
2010 the ids of the slots used in
2011 the pattern
2012 INPUTS : The intermediate parsed pattern
2013 RETURNS : The new slot bitmap (can be NULL)
2014 SIDE EFFECTS : Bitmap created and added to hash
2015 table - corresponding bits set
2016 for ids of slots used in pattern
2017 NOTES : None
2018 ***************************************************/
FormSlotBitMap(void * theEnv,struct lhsParseNode * thePattern)2019 static BITMAP_HN *FormSlotBitMap(
2020 void *theEnv,
2021 struct lhsParseNode *thePattern)
2022 {
2023 struct lhsParseNode *node;
2024 int maxSlotID = -1;
2025 unsigned size;
2026 SLOT_BITMAP *bmp;
2027 BITMAP_HN *hshBmp;
2028
2029 /* =======================================
2030 Find the largest slot id in the pattern
2031 ======================================= */
2032 for (node = thePattern ; node != NULL ; node = node->right)
2033 if (node->slotNumber > maxSlotID)
2034 maxSlotID = node->slotNumber;
2035
2036 /* ===================================================
2037 If the pattern contains no slot tests or only tests
2038 on the class or name (which do not change) do not
2039 store a slot bitmap
2040 =================================================== */
2041 if ((maxSlotID == ISA_ID) || (maxSlotID == NAME_ID))
2042 return(NULL);
2043
2044 /* ===================================
2045 Initialize the bitmap to all zeroes
2046 =================================== */
2047 size = (sizeof(SLOT_BITMAP) +
2048 (sizeof(char) * (maxSlotID / BITS_PER_BYTE)));
2049 bmp = (SLOT_BITMAP *) gm2(theEnv,size);
2050 ClearBitString((void *) bmp,size);
2051 bmp->maxid = (unsigned short) maxSlotID;
2052
2053 /* ============================================
2054 Add (retrieve) a bitmap to (from) the bitmap
2055 hash table which has a corresponding bit set
2056 for the id of every slot used in the pattern
2057 ============================================ */
2058 for (node = thePattern ; node != NULL ; node = node->right)
2059 SetBitMap(bmp->map,node->slotNumber);
2060 hshBmp = (BITMAP_HN *) EnvAddBitMap(theEnv,(void *) bmp,SlotBitMapSize(bmp));
2061 rm(theEnv,(void *) bmp,size);
2062 return(hshBmp);
2063 }
2064
2065 /****************************************************
2066 NAME : RemoveSlotExistenceTests
2067 DESCRIPTION : Removes slot existence test since
2068 these are accounted for by class
2069 bitmap or name slot.
2070 INPUTS : 1) The intermediate pattern nodes
2071 2) A buffer to hold the class bitmap
2072 RETURNS : The filtered list
2073 SIDE EFFECTS : Slot existence tests removed
2074 NOTES : None
2075 ****************************************************/
RemoveSlotExistenceTests(void * theEnv,struct lhsParseNode * thePattern,BITMAP_HN ** bmp)2076 static struct lhsParseNode *RemoveSlotExistenceTests(
2077 void *theEnv,
2078 struct lhsParseNode *thePattern,
2079 BITMAP_HN **bmp)
2080 {
2081 struct lhsParseNode *tempPattern = thePattern;
2082 struct lhsParseNode *lastPattern = NULL, *head = thePattern;
2083
2084 while (tempPattern != NULL)
2085 {
2086 /* ==========================================
2087 Remember the class bitmap for this pattern
2088 ========================================== */
2089 if (tempPattern->userData != NULL)
2090 {
2091 *bmp = (BITMAP_HN *) tempPattern->userData;
2092 lastPattern = tempPattern;
2093 tempPattern = tempPattern->right;
2094 }
2095
2096 /* ===========================================================
2097 A single field slot that has no pattern network expression
2098 associated with it can be removed (i.e. any value contained
2099 in this slot will satisfy the pattern being matched).
2100 =========================================================== */
2101 else if (((tempPattern->type == SF_WILDCARD) ||
2102 (tempPattern->type == SF_VARIABLE)) &&
2103 (tempPattern->networkTest == NULL))
2104 {
2105 if (lastPattern != NULL) lastPattern->right = tempPattern->right;
2106 else head = tempPattern->right;
2107
2108 tempPattern->right = NULL;
2109 ReturnLHSParseNodes(theEnv,tempPattern);
2110
2111 if (lastPattern != NULL) tempPattern = lastPattern->right;
2112 else tempPattern = head;
2113 }
2114
2115 /* =====================================================
2116 A multifield variable or wildcard within a multifield
2117 slot can be removed if there are no other multifield
2118 variables or wildcards contained in the same slot
2119 (and the multifield has no expressions which must be
2120 evaluated in the fact pattern network).
2121 ===================================================== */
2122 else if (((tempPattern->type == MF_WILDCARD) || (tempPattern->type == MF_VARIABLE)) &&
2123 (tempPattern->multifieldSlot == FALSE) &&
2124 (tempPattern->networkTest == NULL) &&
2125 (tempPattern->multiFieldsBefore == 0) &&
2126 (tempPattern->multiFieldsAfter == 0))
2127 {
2128 if (lastPattern != NULL) lastPattern->right = tempPattern->right;
2129 else head = tempPattern->right;
2130
2131 tempPattern->right = NULL;
2132 ReturnLHSParseNodes(theEnv,tempPattern);
2133
2134 if (lastPattern != NULL) tempPattern = lastPattern->right;
2135 else tempPattern = head;
2136 }
2137
2138 /* ================================================================
2139 A multifield wildcard or variable contained in a multifield slot
2140 that contains no other multifield wildcards or variables, but
2141 does have an expression that must be evaluated, can be changed
2142 to a single field pattern node with the same expression.
2143 ================================================================ */
2144 else if (((tempPattern->type == MF_WILDCARD) || (tempPattern->type == MF_VARIABLE)) &&
2145 (tempPattern->multifieldSlot == FALSE) &&
2146 (tempPattern->networkTest != NULL) &&
2147 (tempPattern->multiFieldsBefore == 0) &&
2148 (tempPattern->multiFieldsAfter == 0))
2149 {
2150 tempPattern->type = SF_WILDCARD;
2151 lastPattern = tempPattern;
2152 tempPattern = tempPattern->right;
2153 }
2154
2155 /* =======================================================
2156 If we're dealing with a multifield slot with no slot
2157 restrictions, then treat the multfield slot as a single
2158 field slot, but attach a test which verifies that the
2159 slot contains a zero length multifield value.
2160 ======================================================= */
2161 else if ((tempPattern->type == MF_WILDCARD) &&
2162 (tempPattern->multifieldSlot == TRUE) &&
2163 (tempPattern->bottom == NULL))
2164 {
2165 tempPattern->type = SF_WILDCARD;
2166 GenObjectZeroLengthTest(theEnv,tempPattern);
2167 tempPattern->multifieldSlot = FALSE;
2168 lastPattern = tempPattern;
2169 tempPattern = tempPattern->right;
2170 }
2171
2172 /* ======================================================
2173 Recursively call RemoveSlotExistenceTests for the slot
2174 restrictions contained within a multifield slot.
2175 ====================================================== */
2176 else if ((tempPattern->type == MF_WILDCARD) &&
2177 (tempPattern->multifieldSlot == TRUE))
2178 {
2179 /* =====================================================
2180 Add an expression to the first pattern restriction in
2181 the multifield slot that determines whether or not
2182 the fact's slot value contains the minimum number of
2183 required fields to satisfy the pattern restrictions
2184 for this slot. The length check is place before any
2185 other tests, so that preceeding checks do not have to
2186 determine if there are enough fields in the slot to
2187 safely retrieve a value.
2188 ===================================================== */
2189 GenObjectLengthTest(theEnv,tempPattern->bottom);
2190
2191 /* =======================================================
2192 Remove any unneeded pattern restrictions from the slot.
2193 ======================================================= */
2194 tempPattern->bottom = RemoveSlotExistenceTests(theEnv,tempPattern->bottom,bmp);
2195
2196 /* =========================================================
2197 If the slot no longer contains any restrictions, then the
2198 multifield slot can be completely removed. In any case,
2199 move on to the next slot to be examined for removal.
2200 ========================================================= */
2201 if (tempPattern->bottom == NULL)
2202 {
2203 if (lastPattern != NULL) lastPattern->right = tempPattern->right;
2204 else head = tempPattern->right;
2205
2206 tempPattern->right = NULL;
2207 ReturnLHSParseNodes(theEnv,tempPattern);
2208
2209 if (lastPattern != NULL) tempPattern = lastPattern->right;
2210 else tempPattern = head;
2211 }
2212 else
2213 {
2214 lastPattern = tempPattern;
2215 tempPattern = tempPattern->right;
2216 }
2217 }
2218
2219 /* =====================================================
2220 If none of the other tests for removing slots or slot
2221 restrictions apply, then move on to the next slot or
2222 slot restriction to be tested.
2223 ===================================================== */
2224 else
2225 {
2226 lastPattern = tempPattern;
2227 tempPattern = tempPattern->right;
2228 }
2229 }
2230
2231 /* ====================================
2232 Return the pattern with unused slots
2233 and slot restrictions removed.
2234 ==================================== */
2235 return(head);
2236 }
2237
2238 /***************************************************
2239 NAME : CreateInitialObjectPattern
2240 DESCRIPTION : Creates a default object pattern
2241 for use in defrules
2242 INPUTS : None
2243 RETURNS : The default initial pattern
2244 SIDE EFFECTS : Pattern created
2245 NOTES : The pattern created is:
2246 (object (is-a INITIAL-OBJECT)
2247 (name [initial-object]))
2248 ***************************************************/
CreateInitialObjectPattern(void * theEnv)2249 static struct lhsParseNode *CreateInitialObjectPattern(
2250 void *theEnv)
2251 {
2252 struct lhsParseNode *topNode;
2253 CLASS_BITMAP *clsset;
2254 int initialObjectClassID;
2255
2256 initialObjectClassID = LookupDefclassInScope(theEnv,INITIAL_OBJECT_CLASS_NAME)->id;
2257 clsset = NewClassBitMap(theEnv,initialObjectClassID,0);
2258 SetBitMap(clsset->map,initialObjectClassID);
2259 clsset = PackClassBitMap(theEnv,clsset);
2260
2261 topNode = GetLHSParseNode(theEnv);
2262 topNode->userData = EnvAddBitMap(theEnv,(void *) clsset,ClassBitMapSize(clsset));
2263 IncrementBitMapCount(topNode->userData);
2264 DeleteIntermediateClassBitMap(theEnv,clsset);
2265 topNode->type = SF_WILDCARD;
2266 topNode->index = 1;
2267 topNode->slot = DefclassData(theEnv)->NAME_SYMBOL;
2268 topNode->slotNumber = NAME_ID;
2269
2270 topNode->bottom = GetLHSParseNode(theEnv);
2271 topNode->bottom->type = INSTANCE_NAME;
2272 topNode->bottom->value = (void *) DefclassData(theEnv)->INITIAL_OBJECT_SYMBOL;
2273
2274 return(topNode);
2275 }
2276
2277 /**************************************************************
2278 NAME : ObjectMatchDelayParse
2279 DESCRIPTION : Parses the object-pattern-match-delay function
2280 INPUTS : 1) The function call expression
2281 2) The logical name of the input source
2282 RETURNS : The top expression with the other
2283 action expressions attached
2284 SIDE EFFECTS : Parses the function call and attaches
2285 the appropriate arguments to the
2286 top node
2287 NOTES : None
2288 **************************************************************/
ObjectMatchDelayParse(void * theEnv,struct expr * top,const char * infile)2289 static EXPRESSION *ObjectMatchDelayParse(
2290 void *theEnv,
2291 struct expr *top,
2292 const char *infile)
2293 {
2294 struct token tkn;
2295
2296 IncrementIndentDepth(theEnv,3);
2297 PPCRAndIndent(theEnv);
2298 top->argList = GroupActions(theEnv,infile,&tkn,TRUE,NULL,FALSE);
2299 PPBackup(theEnv);
2300 PPBackup(theEnv);
2301 SavePPBuffer(theEnv,tkn.printForm);
2302 DecrementIndentDepth(theEnv,3);
2303 if (top->argList == NULL)
2304 {
2305 ReturnExpression(theEnv,top);
2306 return(NULL);
2307 }
2308 return(top);
2309 }
2310
2311 /***************************************************
2312 NAME : MarkObjectPtnIncrementalReset
2313 DESCRIPTION : Marks/unmarks an object pattern for
2314 incremental reset
2315 INPUTS : 1) The object pattern alpha node
2316 2) The value to which to set the
2317 incremental reset flag
2318 RETURNS : Nothing useful
2319 SIDE EFFECTS : The pattern node is set/unset
2320 NOTES : The pattern node can only be
2321 set if it is a new node and
2322 thus marked for initialization
2323 by PlaceObjectPattern
2324 ***************************************************/
MarkObjectPtnIncrementalReset(void * theEnv,struct patternNodeHeader * thePattern,int value)2325 static void MarkObjectPtnIncrementalReset(
2326 void *theEnv,
2327 struct patternNodeHeader *thePattern,
2328 int value)
2329 {
2330 #if MAC_XCD
2331 #pragma unused(theEnv)
2332 #endif
2333
2334 if (thePattern->initialize == FALSE)
2335 return;
2336 thePattern->initialize = value;
2337 }
2338
2339 /***********************************************************
2340 NAME : ObjectIncrementalReset
2341 DESCRIPTION : Performs an assert for all instances in the
2342 system. All new patterns in the pattern
2343 network from the new rule have been marked
2344 as needing processing. Old patterns will
2345 be ignored.
2346 INPUTS : None
2347 RETURNS : Nothing useful
2348 SIDE EFFECTS : All objects driven through new patterns
2349 NOTES : None
2350 ***********************************************************/
ObjectIncrementalReset(void * theEnv)2351 static void ObjectIncrementalReset(
2352 void *theEnv)
2353 {
2354 INSTANCE_TYPE *ins;
2355
2356 for (ins = InstanceData(theEnv)->InstanceList ; ins != NULL ; ins = ins->nxtList)
2357 ObjectNetworkAction(theEnv,OBJECT_ASSERT,(INSTANCE_TYPE *) ins,-1);
2358 }
2359
2360 #endif
2361
2362 #endif
2363
2364
2365