00001 /*******************************************************/ 00002 /* "C" Language Integrated Production System */ 00003 /* */ 00004 /* CLIPS Version 6.20 01/31/02 */ 00005 /* */ 00006 /* MULTIPLE INHERITANCE PARSER MODULE */ 00007 /*******************************************************/ 00008 00009 /**************************************************************/ 00010 /* Purpose: Parsing Routines for Multiple Inheritance */ 00011 /* */ 00012 /* Principal Programmer(s): */ 00013 /* Brian L. Dantes */ 00014 /* */ 00015 /* Contributing Programmer(s): */ 00016 /* */ 00017 /* Revision History: */ 00018 /* */ 00019 /**************************************************************/ 00020 00021 /* ========================================= 00022 ***************************************** 00023 EXTERNAL DEFINITIONS 00024 ========================================= 00025 ***************************************** */ 00026 #include "setup.h" 00027 00028 #if OBJECT_SYSTEM && (! BLOAD_ONLY) && (! RUN_TIME) 00029 00030 #include "classcom.h" 00031 #include "classfun.h" 00032 #include "envrnmnt.h" 00033 #include "memalloc.h" 00034 #include "modulutl.h" 00035 #include "router.h" 00036 #include "scanner.h" 00037 00038 #define _INHERPSR_SOURCE_ 00039 #include "inherpsr.h" 00040 00041 /* ========================================= 00042 ***************************************** 00043 MACROS AND TYPES 00044 ========================================= 00045 ***************************************** */ 00046 typedef struct partialOrder PARTIAL_ORDER; 00047 typedef struct successor SUCCESSOR; 00048 00049 struct partialOrder 00050 { 00051 DEFCLASS *cls; 00052 unsigned pre; 00053 SUCCESSOR *suc; 00054 struct partialOrder *nxt; 00055 }; 00056 00057 struct successor 00058 { 00059 PARTIAL_ORDER *po; 00060 struct successor *nxt; 00061 }; 00062 00063 /* ========================================= 00064 ***************************************** 00065 INTERNALLY VISIBLE FUNCTION HEADERS 00066 ========================================= 00067 ***************************************** */ 00068 00069 static PARTIAL_ORDER *InitializePartialOrderTable(void *,PARTIAL_ORDER *,PACKED_CLASS_LINKS *); 00070 static void RecordPartialOrders(void *,PARTIAL_ORDER *,DEFCLASS *,PACKED_CLASS_LINKS *,long); 00071 static PARTIAL_ORDER *FindPartialOrder(PARTIAL_ORDER *,DEFCLASS *); 00072 static void PrintPartialOrderLoop(void *,PARTIAL_ORDER *); 00073 static void PrintClassLinks(void *,char *,char *,CLASS_LINK *); 00074 00075 /* ========================================= 00076 ***************************************** 00077 EXTERNALLY VISIBLE FUNCTIONS 00078 ========================================= 00079 ***************************************** */ 00080 00081 /************************************************************** 00082 NAME : ParseSuperclasses 00083 DESCRIPTION : Parses the (is-a <superclass>+) portion of 00084 the (defclass ...) construct and returns 00085 a list of direct superclasses. The 00086 class "standard-class" is the precedence list 00087 for classes with no direct superclasses. 00088 The final precedence list (not calculated here) 00089 will have the class in question first followed 00090 by the merged precedence lists of its direct 00091 superclasses. 00092 INPUTS : 1) The logical name of the input source 00093 2) The symbolic name of the new class 00094 RETURNS : The address of the superclass list 00095 or NULL if there was an error 00096 SIDE EFFECTS : None 00097 NOTES : Assumes "(defclass <name> [<comment>] (" 00098 has already been scanned. 00099 00100 All superclasses must be defined before 00101 their subclasses. Duplicates in the (is-a 00102 ...) list are are not allowed (a class may only 00103 inherits from a superclass once). 00104 00105 This routine also checks the class-precedence 00106 lists of each of the direct superclasses for 00107 an occurrence of the new class - i.e. cycles! 00108 This can only happen when a class is redefined 00109 (a new class cannot have an unspecified 00110 superclass). 00111 00112 This routine allocates the space for the list 00113 ***************************************************************/ 00114 globle PACKED_CLASS_LINKS *ParseSuperclasses( 00115 void *theEnv, 00116 char *readSource, 00117 SYMBOL_HN *newClassName) 00118 { 00119 CLASS_LINK *clink = NULL,*cbot = NULL,*ctmp; 00120 DEFCLASS *sclass; 00121 PACKED_CLASS_LINKS *plinks; 00122 00123 if (GetType(DefclassData(theEnv)->ObjectParseToken) != LPAREN) 00124 { 00125 SyntaxErrorMessage(theEnv,"defclass inheritance"); 00126 return(NULL); 00127 } 00128 GetToken(theEnv,readSource,&DefclassData(theEnv)->ObjectParseToken); 00129 if ((GetType(DefclassData(theEnv)->ObjectParseToken) != SYMBOL) ? TRUE : 00130 (DefclassData(theEnv)->ObjectParseToken.value != (void *) DefclassData(theEnv)->ISA_SYMBOL)) 00131 { 00132 SyntaxErrorMessage(theEnv,"defclass inheritance"); 00133 return(NULL); 00134 } 00135 SavePPBuffer(theEnv," "); 00136 GetToken(theEnv,readSource,&DefclassData(theEnv)->ObjectParseToken); 00137 while (GetType(DefclassData(theEnv)->ObjectParseToken) != RPAREN) 00138 { 00139 if (GetType(DefclassData(theEnv)->ObjectParseToken) != SYMBOL) 00140 { 00141 SyntaxErrorMessage(theEnv,"defclass"); 00142 goto SuperclassParseError; 00143 } 00144 if (FindModuleSeparator(ValueToString(newClassName))) 00145 { 00146 IllegalModuleSpecifierMessage(theEnv); 00147 goto SuperclassParseError; 00148 } 00149 if (GetValue(DefclassData(theEnv)->ObjectParseToken) == (void *) newClassName) 00150 { 00151 PrintErrorID(theEnv,"INHERPSR",1,FALSE); 00152 EnvPrintRouter(theEnv,WERROR,"A class may not have itself as a superclass.\n"); 00153 goto SuperclassParseError; 00154 } 00155 for (ctmp = clink ; ctmp != NULL ; ctmp = ctmp->nxt) 00156 { 00157 if (GetValue(DefclassData(theEnv)->ObjectParseToken) == (void *) ctmp->cls->header.name) 00158 { 00159 PrintErrorID(theEnv,"INHERPSR",2,FALSE); 00160 EnvPrintRouter(theEnv,WERROR,"A class may inherit from a superclass only once.\n"); 00161 goto SuperclassParseError; 00162 } 00163 } 00164 sclass = LookupDefclassInScope(theEnv,ValueToString(GetValue(DefclassData(theEnv)->ObjectParseToken))); 00165 if (sclass == NULL) 00166 { 00167 PrintErrorID(theEnv,"INHERPSR",3,FALSE); 00168 EnvPrintRouter(theEnv,WERROR,"A class must be defined after all its superclasses.\n"); 00169 goto SuperclassParseError; 00170 } 00171 if ((sclass == DefclassData(theEnv)->PrimitiveClassMap[INSTANCE_NAME]) || 00172 (sclass == DefclassData(theEnv)->PrimitiveClassMap[INSTANCE_ADDRESS]) || 00173 (sclass == DefclassData(theEnv)->PrimitiveClassMap[INSTANCE_NAME]->directSuperclasses.classArray[0])) 00174 { 00175 PrintErrorID(theEnv,"INHERPSR",6,FALSE); 00176 EnvPrintRouter(theEnv,WERROR,"A user-defined class cannot be a subclass of "); 00177 EnvPrintRouter(theEnv,WERROR,EnvGetDefclassName(theEnv,(void *) sclass)); 00178 EnvPrintRouter(theEnv,WERROR,".\n"); 00179 goto SuperclassParseError; 00180 } 00181 ctmp = get_struct(theEnv,classLink); 00182 ctmp->cls = sclass; 00183 if (clink == NULL) 00184 clink = ctmp; 00185 else 00186 cbot->nxt = ctmp; 00187 ctmp->nxt = NULL; 00188 cbot = ctmp; 00189 00190 SavePPBuffer(theEnv," "); 00191 GetToken(theEnv,readSource,&DefclassData(theEnv)->ObjectParseToken); 00192 } 00193 if (clink == NULL) 00194 { 00195 PrintErrorID(theEnv,"INHERPSR",4,FALSE); 00196 EnvPrintRouter(theEnv,WERROR,"Must have at least one superclass.\n"); 00197 return(NULL); 00198 } 00199 PPBackup(theEnv); 00200 PPBackup(theEnv); 00201 SavePPBuffer(theEnv,")"); 00202 plinks = get_struct(theEnv,packedClassLinks); 00203 PackClassLinks(theEnv,plinks,clink); 00204 return(plinks); 00205 00206 SuperclassParseError: 00207 DeleteClassLinks(theEnv,clink); 00208 return(NULL); 00209 } 00210 00211 /*************************************************************************** 00212 NAME : FindPrecedenceList 00213 DESCRIPTION : A complete class precedence list is obtained from the 00214 list of direct superclasses as follows : 00215 00216 Each class and its direct superclasses are recursively 00217 entered in order to a list called the partial order table. 00218 A class is only entered once. The order reflects a pre-order 00219 depth-first traversal of the classes, and this order will be 00220 followed as closely as possible to preserve the "family" 00221 heuristic when constructing the class precedence list. 00222 00223 Attached to each node is a count indicating the number of 00224 classes which must precede this class and a list of classes 00225 which must succeed this class (attached via the suc field and 00226 linked via nxt fields). These predecessor counts 00227 and successor lists indicate the partial orderings given 00228 by the rules of multiple inheritance for the classes: 00229 1) a class must precede all its superclasses, and 2) a 00230 class determines the precedence of its immediate superclasses. 00231 00232 For example, the following class definitions 00233 00234 (defclass A (is-a USER)) 00235 (defclass B (is-a USER)) 00236 (defclass C (is-a A B)) 00237 00238 would give the following partial orders: 00239 00240 C < A by Rule 1 00241 C < B by Rule 1 00242 A < B by Rule 2 00243 B < USER by Rule 1 00244 A < USER by Rule 1 00245 USER < OBJECT by Rule 1 00246 00247 In turn, these partial orders would be recorded in a 00248 sequence table: 00249 00250 C A USER OBJECT B 00251 Predecessor Count 0 1 2 1 2 00252 Successor List A,B B,USER OBJECT <NIL> USER 00253 00254 To generate a precedence list for C, we pick the first 00255 class with a predecessor count of 0, append it to the 00256 precedence list, and decrement the counts of all its 00257 successors. We continue scanning for a 0 from where 00258 we left off. If we ever scan completely through the 00259 table without finding a 0, then we know there is an 00260 error. 00261 00262 Shown below is the table above after each class is 00263 entered onto the precedence list: 00264 00265 Precedence list: C 00266 A USER OBJECT B 00267 Predecessor Count 0 2 1 1 00268 Successor List B,USER OBJECT <NIL> USER 00269 00270 Precedence list: C A 00271 USER OBJECT B 00272 Predecessor Count 1 1 0 00273 Successor List OBJECT <NIL> USER 00274 00275 Precedence list: C A B 00276 USER OBJECT 00277 Predecessor Count 0 1 00278 Successor List OBJECT <NIL> 00279 00280 Precedence list: C A B USER 00281 OBJECT 00282 Predecessor Count 0 00283 Successor List <NIL> 00284 00285 Precedence List: C A B USER OBJECT 00286 00287 And since the table is now empty we are done! 00288 INPUTS : 1) The old class definition (NULL if it is new) 00289 2) The list of direct superclasses 00290 RETURNS : The address of the precedence list if successful, 00291 NULL otherwise 00292 SIDE EFFECTS : Precedence list allocated 00293 NOTES : WARNING!! - This routine assumes that there are no 00294 cyclic dependencies in the given superclass list, i.e. 00295 none of the superclasses inherit from the class for 00296 which the precedence list is being defined. (This 00297 is verified in ParseDefclasses() in CLASSCOM.C) 00298 00299 Every class-precedence list has the class itself on it 00300 (implicitly) and a built-in system class on it explicitly 00301 (except for the built-in classes). 00302 00303 The precedence determination algorithm is a variation on 00304 the topological sorting algorithm given in The Art of 00305 Computer Programming - Vol. I (Fundamental Algorithms) by 00306 Donald Knuth. 00307 ***************************************************************************/ 00308 globle PACKED_CLASS_LINKS *FindPrecedenceList( 00309 void *theEnv, 00310 DEFCLASS *cls, 00311 PACKED_CLASS_LINKS *supers) 00312 { 00313 PARTIAL_ORDER *po_table = NULL,*start,*pop,*poprv,*potmp; 00314 SUCCESSOR *stmp; 00315 CLASS_LINK *ptop,*pbot,*ptmp; 00316 PACKED_CLASS_LINKS *plinks; 00317 long i; 00318 00319 /* ===================================================================== 00320 Recursively add all superclasses in a pre-order depth-first traversal 00321 to the partial order table. There should be only one node per class. 00322 ===================================================================== */ 00323 po_table = InitializePartialOrderTable(theEnv,po_table,supers); 00324 00325 /* ============================================================= 00326 If the class already exists, record the rule 1 partial orders 00327 with the new superclass lists. This is so that cyclic 00328 dependencies can be detected. 00329 ============================================================= */ 00330 if (cls != NULL) 00331 { 00332 pop = get_struct(theEnv,partialOrder); 00333 pop->cls = cls; 00334 pop->pre = 0; 00335 pop->suc = NULL; 00336 pop->nxt = po_table; 00337 po_table = pop; 00338 pop = po_table->nxt; 00339 RecordPartialOrders(theEnv,po_table,cls,supers,0); 00340 } 00341 else 00342 pop = po_table; 00343 00344 /* ================================================================== 00345 Record the rule 1 and rule 2 partial orders given by the direct 00346 superclass lists of the classes in the table. There is no need to 00347 recurse since all possible classes have been entered already. 00348 00349 Be sure to skip the class itself if it was added to the front of 00350 the table. 00351 ================================================================== */ 00352 for ( ; pop != NULL ; pop = pop->nxt) 00353 { 00354 RecordPartialOrders(theEnv,po_table,pop->cls,&pop->cls->directSuperclasses,0); 00355 for (i = 0 ; i < pop->cls->directSuperclasses.classCount ; i++) 00356 RecordPartialOrders(theEnv,po_table,pop->cls->directSuperclasses.classArray[i], 00357 &pop->cls->directSuperclasses,i+1); 00358 } 00359 00360 /* ============================================================= 00361 Record the rule 2 partial orders given by the superclass list 00362 ============================================================= */ 00363 for (i = 0 ; i < supers->classCount ; i++) 00364 RecordPartialOrders(theEnv,po_table,supers->classArray[i],supers,i+1); 00365 00366 start = NULL; 00367 poprv = NULL; 00368 pop = po_table; 00369 ptop = pbot = NULL; 00370 while (pop != start) 00371 { 00372 /* ============================================================== 00373 Allow wraparound - happens when the search for a 0 node begins 00374 somewhere in the middle of the sequence table 00375 ============================================================== */ 00376 if (pop == NULL) 00377 { 00378 poprv = NULL; 00379 pop = po_table; 00380 start = start->nxt; 00381 } 00382 00383 /* ========================================================= 00384 Search for the first class with no remaining predecessors 00385 ========================================================= */ 00386 if (pop->pre == 0) 00387 { 00388 /* ================================================= 00389 Decrement the predecessor count for all the 00390 successors of this class and delete the list. 00391 00392 This is the variation on Knuth's algorithm which 00393 allows us to preserve the "family" heuristic. 00394 Since we will pick up scanning for 0's from 00395 this point, we will be able to keep "family" 00396 trees together, if possible. BuildPartialOrders() 00397 entered the classes into the sequence table 00398 in a pre-order depth traversal order. 00399 ================================================= */ 00400 while (pop->suc != NULL) 00401 { 00402 stmp = pop->suc; 00403 pop->suc = stmp->nxt; 00404 stmp->po->pre--; 00405 rtn_struct(theEnv,successor,stmp); 00406 } 00407 00408 /* ============================================= 00409 Append the class to the precedence list and 00410 remove its entry from the partial order table 00411 ============================================= */ 00412 potmp = pop; 00413 if (poprv == NULL) 00414 po_table = pop->nxt; 00415 else 00416 poprv->nxt = pop->nxt; 00417 pop = pop->nxt; 00418 start = poprv; 00419 ptmp = get_struct(theEnv,classLink); 00420 ptmp->cls = potmp->cls; 00421 ptmp->nxt = NULL; 00422 rtn_struct(theEnv,partialOrder,potmp); 00423 if (ptop == NULL) 00424 ptop = ptmp; 00425 else 00426 pbot->nxt = ptmp; 00427 pbot = ptmp; 00428 } 00429 else 00430 { 00431 poprv = pop; 00432 pop = pop->nxt; 00433 } 00434 } 00435 00436 /* ====================================================================== 00437 If the table of partial orders is not empty and we were unable to find 00438 a class with no predecessors, then there is no solution! Print out the 00439 precedence loop in the partial orders. Delete the remaining partial 00440 order table and the partial precedence list. 00441 ====================================================================== */ 00442 if (po_table != NULL) 00443 { 00444 PrintErrorID(theEnv,"INHERPSR",5,FALSE); 00445 PrintClassLinks(theEnv,WERROR,"Partial precedence list formed:",ptop); 00446 PrintPartialOrderLoop(theEnv,po_table); 00447 while (po_table != NULL) 00448 { 00449 while (po_table->suc != NULL) 00450 { 00451 stmp = po_table->suc; 00452 po_table->suc = stmp->nxt; 00453 rtn_struct(theEnv,successor,stmp); 00454 } 00455 potmp = po_table; 00456 po_table = po_table->nxt; 00457 rtn_struct(theEnv,partialOrder,potmp); 00458 } 00459 DeleteClassLinks(theEnv,ptop); 00460 return(NULL); 00461 } 00462 00463 /* ============================================================================= 00464 If the class already existed, be sure and remove it from its own precedence 00465 list. Remember that we stuck it on the table artificially to catch cycles. 00466 It was first in the table, and, since it started with a predecessor count 00467 of zero (given that there were no loops), it is first in the precedence list. 00468 00469 We will leave the dummy node there so that functions which wish to iterate 00470 over a class and its superclasses may easily do so. 00471 ============================================================================= */ 00472 if (cls == NULL) 00473 { 00474 ptmp = get_struct(theEnv,classLink); 00475 ptmp->nxt = ptop; 00476 ptop = ptmp; 00477 } 00478 00479 /* ============================================================ 00480 The class pointer will be filled in later by ParseDefclass() 00481 ============================================================ */ 00482 ptop->cls = NULL; 00483 00484 plinks = get_struct(theEnv,packedClassLinks); 00485 PackClassLinks(theEnv,plinks,ptop); 00486 return(plinks); 00487 } 00488 00489 /*************************************************** 00490 NAME : PackClassLinks 00491 DESCRIPTION : Writes a list of class links into 00492 a contiguous section of memory to 00493 reduce overhead (the original list 00494 is deleted) 00495 INPUTS : 1) The packed list structure to use 00496 2) The top of the original list 00497 RETURNS : Nothing useful 00498 SIDE EFFECTS : Packed list allocated and old list 00499 deleted 00500 NOTES : None 00501 ***************************************************/ 00502 globle void PackClassLinks( 00503 void *theEnv, 00504 PACKED_CLASS_LINKS *plinks, 00505 CLASS_LINK *lptop) 00506 { 00507 register unsigned count; 00508 register CLASS_LINK *lp; 00509 00510 for (count = 0 , lp = lptop ; lp != NULL ; lp = lp->nxt) 00511 count++; 00512 if (count > 0) 00513 plinks->classArray = (DEFCLASS **) gm2(theEnv,(sizeof(DEFCLASS *) * count)); 00514 else 00515 plinks->classArray = NULL; 00516 for (count = 0 , lp = lptop ; lp != NULL ; lp = lp->nxt , count++) 00517 plinks->classArray[count] = lp->cls; 00518 DeleteClassLinks(theEnv,lptop); 00519 plinks->classCount = (unsigned short) count; 00520 } 00521 00522 /* ========================================= 00523 ***************************************** 00524 INTERNALLY VISIBLE FUNCTIONS 00525 ========================================= 00526 ***************************************** */ 00527 00528 /************************************************************************** 00529 NAME : InitializePartialOrderTable 00530 DESCRIPTION : This function recursively enters the classes 00531 that will be used in a precedence list 00532 determination in depth-first pre-order traversal. 00533 The predecessor counts and successor list are initialized. 00534 00535 INPUTS : 1) The partial order table 00536 2) A list of direct superclasses 00537 3) The class for which a precedence class is being 00538 determined (NULL for new class) 00539 4) The class which superclass list is being processed 00540 RETURNS : The top of partial order table 00541 SIDE EFFECTS : The partial order table is initialized. 00542 NOTES : None 00543 **************************************************************************/ 00544 static PARTIAL_ORDER *InitializePartialOrderTable( 00545 void *theEnv, 00546 PARTIAL_ORDER *po_table, 00547 PACKED_CLASS_LINKS *supers) 00548 { 00549 register PARTIAL_ORDER *pop,*poprv; 00550 long i; 00551 00552 for (i = 0 ; i < supers->classCount ; i++) 00553 { 00554 /* ================================================= 00555 Append this class at the end of the partial order 00556 table only if it is not already present 00557 ================================================= */ 00558 poprv = NULL; 00559 for (pop = po_table ; pop != NULL ; pop = pop->nxt) 00560 { 00561 if (pop->cls == supers->classArray[i]) 00562 break; 00563 poprv = pop; 00564 } 00565 if (pop == NULL) 00566 { 00567 pop = get_struct(theEnv,partialOrder); 00568 pop->cls = supers->classArray[i]; 00569 pop->nxt = NULL; 00570 pop->suc = NULL; 00571 pop->pre = 0; 00572 if (poprv == NULL) 00573 po_table = pop; 00574 else 00575 poprv->nxt = pop; 00576 00577 /* ============================================================= 00578 Recursively append all its superclasses immediately after it. 00579 This order will allow us to preserve the "family" heuristic 00580 in the precedence list. 00581 ============================================================= */ 00582 po_table = InitializePartialOrderTable(theEnv,po_table, 00583 &supers->classArray[i]->directSuperclasses); 00584 } 00585 } 00586 return(po_table); 00587 } 00588 00589 /*********************************************************************************** 00590 NAME : RecordPartialOrders 00591 DESCRIPTION : Given a predecessor class and a list of successor classes, this 00592 function enters a number of partial orders into the table equaling 00593 the number of successor classes. 00594 INPUTS : 1) The partial order table 00595 2) The predecessor class 00596 3) An array of successor classes 00597 4) A starting index for the successor classes 00598 RETURNS : The top of sequence table 00599 SIDE EFFECTS : The sequence table is built, e.g.: 00600 00601 CLASS1 < CLASS2 , CLASS3 00602 00603 would be recorded as: 00604 00605 PO_TABLE -> NXT -> NXT -> NXT -> <NIL> 00606 <CLASS1> <CLASS2> <CLASS3> 00607 SUC SUC SUC 00608 | | | 00609 V V V 00610 <CLASS2> <NIL> <NIL> 00611 NXT 00612 | 00613 V 00614 <CLASS3> 00615 NXT 00616 | 00617 V 00618 <NIL> 00619 00620 The predecessor counts would be 0, 1 and 1 for CLASS1, CLASS2 00621 and CLASS3 respectively. 00622 NOTES : None 00623 ***********************************************************************************/ 00624 static void RecordPartialOrders( 00625 void *theEnv, 00626 PARTIAL_ORDER *po_table, 00627 DEFCLASS *cls, 00628 PACKED_CLASS_LINKS *successors, 00629 long starti) 00630 { 00631 register PARTIAL_ORDER *clspo; 00632 register SUCCESSOR *stmp; 00633 00634 clspo = FindPartialOrder(po_table,cls); 00635 while (starti < successors->classCount) 00636 { 00637 stmp = get_struct(theEnv,successor); 00638 stmp->po = FindPartialOrder(po_table,successors->classArray[starti]); 00639 stmp->nxt = clspo->suc; 00640 clspo->suc = stmp; 00641 stmp->po->pre++; 00642 starti++; 00643 } 00644 } 00645 00646 /*************************************************** 00647 NAME : FindPartialOrder 00648 DESCRIPTION : Finds a partial order node 00649 INPUTS : 1) The partial order table 00650 2) The class to look up 00651 RETURNS : The partial order node address 00652 SIDE EFFECTS : None 00653 NOTES : None 00654 ***************************************************/ 00655 static PARTIAL_ORDER *FindPartialOrder( 00656 PARTIAL_ORDER *po_table, 00657 DEFCLASS *cls) 00658 { 00659 while (po_table != NULL) 00660 { 00661 if (po_table->cls == cls) 00662 break; 00663 po_table = po_table->nxt; 00664 } 00665 return(po_table); 00666 } 00667 00668 /************************************************************************** 00669 NAME : PrintPartialOrderLoop 00670 DESCRIPTION : This routine prints a conflicting loop (there may be more 00671 than one) in the given sequence table of partial orders. 00672 00673 The algorithm works as follows: 00674 00675 Given the following class definitions, 00676 00677 (defclass A (is-a USER)) 00678 (defclass B (is-a USER)) 00679 (defclass C (is-a A B)) 00680 (defclass D (is-a B A)) 00681 (defclass E (is-a C D)) 00682 00683 the partial order table will look as follows after as many 00684 classes as possible have been entered onto the precedence 00685 list: 00686 00687 A USER OBJECT B 00688 Predecessor Count 1 2 1 1 00689 Successor List B,USER OBJECT <NIL> A,USER 00690 00691 Construct a new table where each class is linked to one 00692 of its predecessors. For the example above one would be: 00693 00694 Class: A USER OBJECT B 00695 Predecessor: B A USER A 00696 00697 This table is actually implemnted using the original 00698 partial order table (see the code below for specifics). 00699 Now using this table, start with the first node, and visit 00700 successive nodes by following the predecessor links. Mark 00701 each node as "visited". When a previously visited node is 00702 encountered, the loop has been found. 00703 00704 In the case above, we start with A, goto B and then goto A 00705 again which we have already seen. So starting from where 00706 we found the loop (A) we follow the links again, printing 00707 the nodes as we go, until we're back where we started: 00708 A B A. Notice that this loop reflects the Rule 2 conflicts 00709 between Class C and Class D in Class E's precedence list. 00710 00711 INPUTS : The remaining partial order table of conflicting partial 00712 orders 00713 RETURNS : Nothing useful 00714 SIDE EFFECTS : The predecessor counts and successor lists are modified to 00715 implement the loop detection. 00716 NOTES : This algorithm is adopted from one given in Donald 00717 Knuth's The Art of Computer Programming - Vol. I 00718 (Fundamental Algorithms). 00719 **************************************************************************/ 00720 static void PrintPartialOrderLoop( 00721 void *theEnv, 00722 PARTIAL_ORDER *po_table) 00723 { 00724 register PARTIAL_ORDER *pop1,*pop2; 00725 SUCCESSOR *prc,*stmp; 00726 00727 /* ==================================================== 00728 Set the predecessor count of every node to 0 so that 00729 this field can be used as a marker 00730 ==================================================== */ 00731 for (pop1 = po_table ; pop1 != NULL ; pop1 = pop1->nxt) 00732 pop1->pre = 0; 00733 00734 /* ======================================================= 00735 Mark each node in the partial order table with one of 00736 its predecessors. If the class has already been marked 00737 (predecessor count > 0), don't bother. This is 00738 accomplished by adding a node to the front of its 00739 successors' successor lists. 00740 00741 When the process is finished, all nodes will have one 00742 predecessor chained to them by their 'suc' field. 00743 (If any nodes had had no predecessors, they would not 00744 still be in the table.) 00745 ======================================================= */ 00746 for (pop1 = po_table ; pop1 != NULL ; pop1 = pop1->nxt) 00747 { 00748 if (pop1->pre == 0) 00749 { 00750 prc = pop1->suc; 00751 pop1->suc = NULL; 00752 } 00753 else 00754 { 00755 prc = pop1->suc->nxt; 00756 pop1->suc->nxt = NULL; 00757 } 00758 while (prc != NULL) 00759 { 00760 pop2 = FindPartialOrder(po_table,prc->po->cls); 00761 if (pop2->pre == 0) 00762 { 00763 stmp = get_struct(theEnv,successor); 00764 stmp->po = pop1; 00765 stmp->nxt = pop2->suc; 00766 pop2->suc = stmp; 00767 pop2->pre = 1; 00768 } 00769 stmp = prc; 00770 prc = prc->nxt; 00771 rtn_struct(theEnv,successor,stmp); 00772 } 00773 } 00774 00775 /* ================================================= 00776 Set the predecessor count of every node back to 0 00777 so that this field can be used as a marker again 00778 ================================================= */ 00779 for (pop1 = po_table ; pop1 != NULL ; pop1 = pop1->nxt) 00780 pop1->pre = 0; 00781 00782 /* ========================================================= 00783 Now start with the first node in the partial order table, 00784 and follow the predecessor links, marking the 00785 nodes as they are visited. When we reach a node 00786 we have been before, we have found a loop! 00787 Follow all the marked nodes again starting from the 00788 CURRENT position to print the loop. 00789 ========================================================= */ 00790 pop1 = po_table; 00791 while (pop1->pre == 0) 00792 { 00793 pop1->pre = 1; 00794 pop1 = pop1->suc->po; 00795 } 00796 00797 EnvPrintRouter(theEnv,WERROR,"Precedence loop in superclasses:"); 00798 while (pop1->pre == 1) 00799 { 00800 EnvPrintRouter(theEnv,WERROR," "); 00801 PrintClassName(theEnv,WERROR,pop1->cls,FALSE); 00802 pop1->pre = 0; 00803 pop1 = pop1->suc->po; 00804 } 00805 EnvPrintRouter(theEnv,WERROR," "); 00806 PrintClassName(theEnv,WERROR,pop1->cls,TRUE); 00807 } 00808 00809 /*************************************************** 00810 NAME : PrintClassLinks 00811 DESCRIPTION : Displays the names of classes in 00812 a list with a title 00813 INPUTS : 1) The logical name of the output 00814 2) Title string 00815 3) List of class links 00816 RETURNS : Nothing useful 00817 SIDE EFFECTS : None 00818 NOTES : None 00819 ***************************************************/ 00820 static void PrintClassLinks( 00821 void *theEnv, 00822 char *logicalName, 00823 char *title, 00824 CLASS_LINK *clink) 00825 { 00826 if (title != NULL) 00827 EnvPrintRouter(theEnv,logicalName,title); 00828 while (clink != NULL) 00829 { 00830 EnvPrintRouter(theEnv,logicalName," "); 00831 PrintClassName(theEnv,logicalName,clink->cls,FALSE); 00832 clink = clink->nxt; 00833 } 00834 EnvPrintRouter(theEnv,logicalName,"\n"); 00835 } 00836 00837 #endif 00838
1.5.6