src/constraintResolve.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2003 University of Virginia,
   4 **         Massachusetts Institute of Technology
   5 **
   6 ** This program is free software; you can redistribute it and/or modify it
   7 ** under the terms of the GNU General Public License as published by the
   8 ** Free Software Foundation; either version 2 of the License, or (at your
   9 ** option) any later version.
  10 **
  11 ** This program is distributed in the hope that it will be useful, but
  12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 ** General Public License for more details.
  15 **
  16 ** The GNU General Public License is available from http://www.gnu.org/ or
  17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  18 ** MA 02111-1307, USA.
  19 **
  20 ** For information on splint: info@splint.org
  21 ** To report a bug: splint-bug@splint.org
  22 ** For more information: http://www.splint.org
  23 */
  24
  25 /*
  26 *
  27 ** constraintResolve.c
  28 */
  29
  30 /* #define DEBUGPRINT 1 */
  31
  32 # include <ctype.h> /* for isdigit */
  33 # include "splintMacros.nf"
  34 # include "basic.h"
  35 # include "cgrammar.h"
  36 # include "cgrammar_tokens.h"
  37
  38 # include "exprChecks.h"
  39 # include "exprNodeSList.h"
  40
  41
  42 /*@access constraint, exprNode @*/ /*!!! NO! Don't do this so recklessly - design your code more carefully so you don't need to! */
  43
  44 /*@-nullderef@*/ /* !!! DRL needs to fix this code! */
  45 /*@-nullstate@*/ /* !!! DRL needs to fix this code! */
  46 /*@-nullpass@*/ /* !!! DRL needs to fix this code! */
  47 /*@-temptrans@*/ /* !!! DRL needs to fix this code! */
  48
  49
  50
  51 static constraint  inequalitySubstitute  (/*@returned@*/ constraint p_c, constraintList p_p);
  52
  53
  54 static bool rangeCheck (arithType p_ar1, /*@observer@*/ constraintExpr p_expr1, arithType p_ar2, /*@observer@*/ constraintExpr p_expr2);
  55
  56 static constraint  inequalitySubstituteUnsound  (/*@returned@*/ constraint p_c, constraintList p_p);
  57
  58 static constraint  inequalitySubstituteStrong  (/*@returned@*/ constraint p_c, constraintList p_p);
  59
  60 static constraint constraint_searchandreplace (/*@returned@*/ constraint p_c, constraintExpr p_old, constraintExpr p_newExpr);
  61
  62
  63 static constraint constraint_addOr (/*@returned@*/ constraint p_orig, /*@observer@*/ constraint p_orConstr);
  64
  65 static bool resolveOr (/*@temp@*/constraint p_c, /*@observer@*/ /*@temp@*/ constraintList p_list);
  66
  67 static /*@only@*/ constraintList reflectChangesEnsuresFree1 (/*@only@*/ constraintList p_pre2, constraintList p_post1);
  68
  69 /*********************************************/
  70
  71
  72
  73
  74 /*@only@*/ constraintList constraintList_mergeEnsuresFreeFirst (constraintList list1, constraintList list2)
  75 {
  76   constraintList ret;
  77
  78   ret = constraintList_mergeEnsures (list1, list2);
  79
  80   constraintList_free(list1);
  81   return ret;
  82 }
  83
  84 /*@only@*/ constraintList constraintList_mergeEnsures (constraintList list1, constraintList list2)
  85 {
  86   constraintList ret;
  87   constraintList temp;
  88
  89   llassert(constraintList_isDefined(list1) );
  90   llassert(constraintList_isDefined(list2) );
  91
  92   DPRINTF(( message ("constraintList_mergeEnsures: list1 %s list2 %s",
  93                      constraintList_print(list1), constraintList_print(list2)
  94                      )));
  95
  96   ret = constraintList_fixConflicts (list1, list2);
  97   ret = reflectChangesEnsuresFree1 (ret, list2);
  98   temp = constraintList_subsumeEnsures (ret, list2);
  99   constraintList_free(ret);
 100   ret = temp;
 101
 102   temp = constraintList_subsumeEnsures (list2, ret);
 103
 104   temp = constraintList_addList (temp, ret);
 105   constraintList_free(ret);
 106
 107   DPRINTF(( message ("constraintList_mergeEnsures: returning %s ",
 108                      constraintList_print(temp) )
 109                      ));
 110
 111
 112   return temp;
 113 }
 114
 115
 116 /*@only@*/ constraintList constraintList_mergeRequiresFreeFirst (/*@only@*/ constraintList list1, constraintList list2)
 117 {
 118   constraintList ret;
 119
 120   ret = constraintList_mergeRequires(list1, list2);
 121
 122   constraintList_free(list1);
 123
 124   return ret;
 125 }
 126
 127 /*@only@*/ constraintList constraintList_mergeRequires (constraintList list1, constraintList list2)
 128 {
 129   constraintList ret;
 130   constraintList temp;
 131
 132   DPRINTF((message ("constraintList_mergeRequires: merging  %s and %s ", constraintList_print (list1), constraintList_print(list2) ) ) );
 133
 134   if (context_getFlag (FLG_REDUNDANTCONSTRAINTS) )
 135     {
 136       ret = constraintList_copy(list1);
 137       ret = constraintList_addList(ret, list2);
 138       return ret;
 139     }
 140
 141   /* get constraints in list1 not satified by list2 */
 142   temp = constraintList_reflectChanges(list1, list2);
 143   DPRINTF((message ("constraintList_mergeRequires: temp = %s", constraintList_print(temp) ) ) );
 144
 145 /*get constraints in list2 not satified by temp*/
 146   ret = constraintList_reflectChanges(list2, temp);
 147
 148   DPRINTF((message ("constraintList_mergeRequires: ret =  %s", constraintList_print(ret) ) ) );
 149
 150   ret = constraintList_addListFree (ret, temp);
 151
 152   DPRINTF((message ("constraintList_mergeRequires: returning  %s", constraintList_print(ret) ) ) );
 153
 154   return ret;
 155 }
 156
 157 /* old name mergeResolve renamed for czech naming convention */
 158 void exprNode_mergeResolve (exprNode parent, exprNode child1, exprNode child2)
 159 {
 160   constraintList temp, temp2;
 161
 162   DPRINTF((message ("magically merging constraint into parent:%s for", exprNode_unparse (parent) )) );
 163
 164   DPRINTF((message (" children:  %s and %s", exprNode_unparse (child1), exprNode_unparse(child2) ) ) );
 165
 166   if (exprNode_isError (child1)  || exprNode_isError(child2) )
 167     {
 168       if (exprNode_isError (child1) && !exprNode_isError(child2) )
 169          {
 170            constraintList_free(parent->requiresConstraints);
 171
 172            parent->requiresConstraints = constraintList_copy (child2->requiresConstraints);
 173            constraintList_free(parent->ensuresConstraints);
 174
 175            parent->ensuresConstraints = constraintList_copy (child2->ensuresConstraints);
 176            DPRINTF((message ("Copied child constraints: pre: %s and post: %s",
 177                              constraintList_print( child2->requiresConstraints),
 178                              constraintList_print (child2->ensuresConstraints)
 179                              )
 180                     ));
 181            return;
 182          }
 183        else
 184          {
 185            llassert(exprNode_isError(child2) );
 186            return;
 187          }
 188      }
 189
 190    llassert(!exprNode_isError (child1)  && ! exprNode_isError(child2) );
 191
 192    DPRINTF((message ("Child constraints are %s %s and %s %s",
 193                      constraintList_print (child1->requiresConstraints),
 194                      constraintList_print (child1->ensuresConstraints),
 195                      constraintList_print (child2->requiresConstraints),
 196                      constraintList_print (child2->ensuresConstraints)
 197                      ) ) );
 198
 199
 200    constraintList_free(parent->requiresConstraints);
 201
 202   parent->requiresConstraints = constraintList_copy (child1->requiresConstraints);
 203
 204   if ( context_getFlag (FLG_ORCONSTRAINT) )
 205     temp = constraintList_reflectChangesOr (child2->requiresConstraints, child1->ensuresConstraints);
 206   else
 207     temp = constraintList_reflectChanges(child2->requiresConstraints, child1->ensuresConstraints);
 208
 209   temp2 = constraintList_mergeRequires (parent->requiresConstraints, temp);
 210   constraintList_free(parent->requiresConstraints);
 211   constraintList_free(temp);
 212
 213   parent->requiresConstraints = temp2;
 214
 215   DPRINTF((message ("Parent requires constraints are %s  ",
 216                      constraintList_print (parent->requiresConstraints)
 217                      ) ) );
 218
 219    constraintList_free(parent->ensuresConstraints);
 220
 221   parent->ensuresConstraints = constraintList_mergeEnsures(child1->ensuresConstraints,
 222                                                            child2->ensuresConstraints);
 223
 224
 225   DPRINTF((message ("Parent constraints are %s and %s ",
 226                      constraintList_print (parent->requiresConstraints),
 227                      constraintList_print (parent->ensuresConstraints)
 228                      ) ) );
 229
 230 }
 231
 232
 233
 234
 235 /*@only@*/ constraintList constraintList_subsumeEnsures (constraintList list1, constraintList list2)
 236 {
 237   constraintList ret;
 238   ret = constraintList_makeNew();
 239   constraintList_elements (list1, el)
 240     {
 241
 242       DPRINTF ((message ("Examining %s", constraint_print (el) ) ) );
 243       if (!constraintList_resolve (el, list2) )
 244         {
 245           constraint temp;
 246           temp = constraint_copy(el);
 247           ret = constraintList_add (ret, temp);
 248         }
 249       else
 250         {
 251           DPRINTF ((message ("Subsuming %s", constraint_print (el) ) ) );
 252         }
 253     } end_constraintList_elements;
 254
 255     return ret;
 256 }
 257
 258
 259
 260 /*used to be reflectChangesFreePre  renamed for Czech naming conventino*/
 261 /* tries to resolve constraints in list pre2 using post1 */
 262 /*@only@*/ constraintList constraintList_reflectChangesFreePre (/*@only@*/ constraintList pre2, /*@observer@*/ constraintList post1)
 263 {
 264   constraintList ret;
 265
 266   ret = constraintList_reflectChanges(pre2, post1);
 267
 268   constraintList_free (pre2);
 269
 270   return ret;
 271 }
 272
 273
 274
 275 /* tries to resolve constraints in list pre2 using post1 */
 276
 277 static /*@only@*/ constraintList reflectChangesNoOr (/*@observer@*/ /*@temp@*/ constraintList pre2, /*@observer@*/ /*@temp@*/ constraintList post1)
 278 {
 279
 280   constraintList ret;
 281   constraint temp;
 282   constraint temp2;
 283
 284   llassert  (! context_getFlag (FLG_ORCONSTRAINT) );
 285
 286   ret = constraintList_makeNew();
 287   DPRINTF((message ("reflectChanges: lists %s and %s", constraintList_print(pre2), constraintList_print(post1) )));
 288
 289   constraintList_elements (pre2, el)
 290     {
 291       if (!constraintList_resolve (el, post1) )
 292         {
 293           temp = constraint_substitute (el, post1);
 294           if (!constraintList_resolve (temp, post1) )
 295             {
 296               /* try inequality substitution
 297                  the inequality substitution may cause us to lose information
 298                  so we don't want to store the result but we do it anyway
 299               */
 300               temp2 = constraint_copy (temp);
 301               temp2 = inequalitySubstitute (temp2, post1);
 302               if (!constraintList_resolve (temp2, post1) )
 303                 {
 304                   temp2 = inequalitySubstituteUnsound (temp2, post1);
 305                   if (!constraintList_resolve (temp2, post1) )
 306                     ret = constraintList_add (ret, temp2);
 307                   else
 308                     constraint_free(temp2);
 309                 }
 310               else
 311                 {
 312                   constraint_free(temp2);
 313                 }
 314             }
 315           constraint_free(temp);
 316         }
 317     } end_constraintList_elements;
 318
 319     DPRINTF((message ("reflectChanges: returning %s", constraintList_print(ret) ) ) );
 320     return ret;
 321 }
 322
 323 /* tries to resolve constraints in list pre2 using post1 */
 324 /*@only@*/ constraintList constraintList_reflectChanges(/*@observer@*/ constraintList pre2, /*@observer@*/ constraintList post1)
 325 {
 326   constraintList temp;
 327
 328   if ( context_getFlag (FLG_ORCONSTRAINT) )
 329
 330     temp = constraintList_reflectChangesOr (pre2, post1);
 331   else
 332     temp = reflectChangesNoOr(pre2, post1);
 333
 334   return temp;
 335 }
 336
 337 static constraint constraint_addOr (/*@returned@*/ constraint orig, /*@observer@*/ constraint orConstr)
 338 {
 339   constraint c;
 340   c = orig;
 341
 342   DPRINTF((message("constraint_addor: oring %s onto %s", constraint_printOr(orConstr), constraint_printOr(orig) ) ));
 343
 344   while (c->or != NULL)
 345     {
 346       c = c->or;
 347     }
 348
 349   c->or = constraint_copy(orConstr);
 350
 351   DPRINTF((message("constraint_addor: returning %s",constraint_printOr(orig) ) ));
 352
 353   return orig;
 354 }
 355
 356
 357 static bool resolveOr ( /*@temp@*/ constraint c, /*@observer@*/ /*@temp@*/ constraintList list)
 358 {
 359   constraint temp;
 360
 361   int numberOr;
 362
 363   numberOr = 0;
 364   DPRINTF(( message("resolveOr: constraint %s and list %s", constraint_printOr(c), constraintList_print(list) ) ));
 365   temp = c;
 366
 367   do
 368     {
 369       if (constraintList_resolve (temp, list) )
 370         return TRUE;
 371       temp = temp->or;
 372       numberOr++;
 373       llassert(numberOr <= 10);
 374     }
 375   while (constraint_isDefined(temp));
 376
 377   return FALSE;
 378 }
 379
 380 /*This is a "helper" function for doResolveOr */
 381
 382 static /*@only@*/ constraint doResolve (/*@only@*/ constraint c, constraintList post1, bool * resolved)
 383 {
 384   constraint temp;
 385
 386   llassert(constraint_isUndefined (c->or ) );
 387
 388   DPRINTF((message("doResolve:: call on constraint c = : %q and constraintList %q",
 389                    constraint_printOr(c), constraintList_print(post1)
 390                    )
 391            ));
 392
 393   if (!resolveOr (c, post1) )
 394     {
 395
 396       temp = constraint_substitute (c, post1);
 397
 398       DPRINTF((message("doResolve:: after substitute temp is %q",
 399                    constraint_printOr(temp)
 400                        )
 401                ));
 402
 403       if (!resolveOr (temp, post1) )
 404         {
 405           /* try inequality substitution */
 406           constraint temp2;
 407
 408           /* the inequality substitution may cause us to lose information
 409              so we don't want to store the result but we do  anyway
 410           */
 411           temp2 = constraint_copy (c);
 412           temp2 = inequalitySubstitute (temp2, post1);
 413
 414           if (!resolveOr (temp2, post1) )
 415             {
 416               constraint temp3;
 417               temp3 = constraint_copy(temp2);
 418
 419               temp3 = inequalitySubstituteStrong (temp3, post1);
 420               if (!resolveOr (temp3, post1) )
 421                 {
 422                   temp2 = inequalitySubstituteUnsound (temp2, post1);
 423                   if (!resolveOr (temp2, post1) )
 424                     {
 425                       if (!constraint_same (temp, temp2) )
 426                         {
 427                           /* drl added 8/28/2002*/
 428                           /*make sure that the information from
 429                             a post condition like i = i + 1 is transfered
 430                           */
 431                           constraint tempSub;
 432                           tempSub = constraint_substitute (temp2, post1);
 433
 434                           DPRINTF((
 435                                    message("doResolve: adding %s ",
 436                                            constraint_printOr(tempSub)
 437                                            )
 438                                    ));
 439
 440                           DPRINTF((
 441                                    message("doResolve: not adding %s ",
 442                                            constraint_printOr(temp2)
 443                                            )
 444                                    ));
 445
 446                           temp = constraint_addOr (temp, tempSub);
 447                           constraint_free(tempSub);
 448
 449                         }
 450                       if (!constraint_same (temp, temp3) && !constraint_same (temp3, temp2) )
 451                         {
 452                          /* drl added 8/28/2002*/
 453                           /*make sure that the information from
 454                             a post condition like i = i + 1 is transfered
 455                           */
 456                           constraint tempSub;
 457
 458                           tempSub = constraint_substitute (temp3, post1);
 459
 460                           DPRINTF((
 461                                    message("doResolve: adding %s ",
 462                                            constraint_printOr(tempSub)
 463                                            )
 464                                    ));
 465
 466
 467                           DPRINTF((
 468                                    message("doResolve: not adding %s ",
 469                                            constraint_printOr(temp3)
 470                                            )
 471                                    ));
 472
 473                           temp = constraint_addOr (temp, tempSub);
 474
 475                           constraint_free(tempSub);
 476                         }
 477                       *resolved = FALSE;
 478
 479                       constraint_free(temp2);
 480                       constraint_free(temp3);
 481                       constraint_free(c);
 482
 483                       return temp;
 484                     }
 485                   constraint_free(temp2);
 486                   constraint_free(temp3);
 487                 }
 488               else
 489                 {
 490                   constraint_free(temp2);
 491                   constraint_free(temp3);
 492                 }
 493             }
 494           else
 495             {
 496               constraint_free(temp2);
 497             }
 498
 499         }
 500       constraint_free(temp);
 501     }
 502   constraint_free(c);
 503
 504   /*drl bee: pbr*/ *resolved = TRUE;
 505   return NULL;
 506 }
 507
 508 static /*@only@*/ constraint doResolveOr (/*@observer@*/ /*@temp@*/ constraint c, constraintList post1, /*@out@*/bool * resolved)
 509 {
 510   constraint ret;
 511   constraint next;
 512   constraint curr;
 513
 514
 515   DPRINTF(( message("doResolveOr: constraint %s and list %s", constraint_printOr(c), constraintList_print(post1) ) ));
 516
 517
 518
 519    /*drl bee: pbr*/ *resolved = FALSE;
 520
 521
 522   ret = constraint_copy(c);
 523
 524   if (constraintList_isEmpty(post1) )
 525     {
 526       return ret;
 527     }
 528
 529   next = ret->or;
 530   ret->or = NULL;
 531
 532   ret = doResolve (ret, post1, resolved);
 533
 534   if (*resolved)
 535     {
 536       if (next != NULL)
 537         constraint_free(next);
 538
 539       /*we don't need to free ret when resolved is false because ret is null*/
 540       llassert(ret == NULL);
 541
 542       return NULL;
 543     }
 544
 545   while (next != NULL)
 546     {
 547       curr = next;
 548       next = curr->or;
 549       curr->or = NULL;
 550
 551       curr = doResolve (curr, post1, resolved);
 552
 553     /*drl bee: pbr*/    if (*resolved)
 554         {
 555           /* curr is null so we don't try to free it*/
 556           llassert(curr == NULL);
 557
 558           if (next != NULL)
 559             constraint_free(next);
 560
 561           constraint_free(ret);
 562           return NULL;
 563         }
 564       ret = constraint_addOr (ret, curr);
 565       constraint_free(curr);
 566     }
 567   return ret;
 568 }
 569
 570 /* tries to resolve constraints in list pr2 using post1 */
 571 /*@only@*/ constraintList constraintList_reflectChangesOr (constraintList pre2, constraintList post1)
 572 {
 573   bool resolved;
 574   constraintList ret;
 575   constraint temp;
 576   ret = constraintList_makeNew();
 577   DPRINTF((message ("constraintList_reflectChangesOr: lists %s and %s", constraintList_print(pre2), constraintList_print(post1) )));
 578
 579   constraintList_elements (pre2, el)
 580     {
 581       temp = doResolveOr (el, post1, &resolved);
 582
 583       if (!resolved)
 584         {
 585           ret = constraintList_add(ret, temp);
 586         }
 587       else
 588         {
 589      /* we don't need to free temp when
 590         resolved is false because temp is null */
 591           llassert(temp == NULL);
 592         }
 593
 594     } end_constraintList_elements;
 595
 596   DPRINTF((message ("constraintList_reflectChangesOr: returning %s", constraintList_print(ret) ) ) );
 597     return ret;
 598 }
 599
 600 static /*@only@*/ constraintList reflectChangesEnsures (/*@observer@*/ constraintList pre2, constraintList post1)
 601 {
 602   constraintList ret;
 603   constraint temp;
 604   ret = constraintList_makeNew();
 605   constraintList_elements (pre2, el)
 606     {
 607       if (!constraintList_resolve (el, post1) )
 608         {
 609           temp = constraint_substitute (el, post1);
 610           llassert (temp != NULL);
 611
 612           if (!constraintList_resolve (temp, post1) )
 613             ret = constraintList_add (ret, temp);
 614           else
 615             constraint_free(temp);
 616         }
 617       else
 618         {
 619           DPRINTF ((message ("Resolved away %s ", constraint_print(el) ) ) );
 620         }
 621     } end_constraintList_elements;
 622
 623     return ret;
 624 }
 625
 626
 627 static /*@only@*/ constraintList reflectChangesEnsuresFree1 (/*@only@*/ constraintList pre2, constraintList post1)
 628 {
 629   constraintList ret;
 630
 631   ret = reflectChangesEnsures (pre2, post1);
 632
 633   constraintList_free(pre2);
 634
 635   return ret;
 636 }
 637
 638
 639 static bool constraint_conflict (constraint c1, constraint c2)
 640 {
 641
 642   if (constraintExpr_similar(c1->lexpr, c2->lexpr) )
 643     {
 644       if (c1->ar == EQ)
 645         if (c1->ar == c2->ar)
 646           {
 647             DPRINTF ((message ("%s conflicts with %s ", constraint_print (c1), constraint_print(c2) ) ) );
 648             return TRUE;
 649           }
 650     }
 651
 652   /* This is a slight kludg to prevent circular constraints like
 653      strlen(str) == maxRead(s) + strlen(str);
 654   */
 655
 656   /*@i324234*/ /* clean this up */
 657
 658   if (c1->ar == EQ)
 659     if (c1->ar == c2->ar)
 660       {
 661         if (constraintExpr_search (c1->lexpr, c2->expr) )
 662           if (constraintExpr_isTerm(c1->lexpr) )
 663             {
 664               constraintTerm term;
 665
 666               term = constraintExpr_getTerm(c1->lexpr);
 667
 668               if (constraintTerm_isExprNode(term) )
 669                 {
 670                   DPRINTF ((message ("%s conflicts with %s ", constraint_print (c1), constraint_print(c2) ) ) );
 671                   return TRUE;
 672                 }
 673             }
 674       }
 675
 676   if (constraint_tooDeep(c1) || constraint_tooDeep(c2) )
 677         {
 678           DPRINTF ((message ("%s conflicts with %s (constraint is too deep", constraint_print (c1), constraint_print(c2) ) ) );
 679           return TRUE;
 680         }
 681
 682   DPRINTF ((message ("%s doesn't conflict with %s ", constraint_print (c1), constraint_print(c2) ) ) );
 683
 684   return FALSE;
 685
 686 }
 687
 688 static void constraint_fixConflict (/*@temp@*/ constraint good, /*@temp@*/ /*@observer@*/ constraint conflicting) /*@modifies good@*/
 689 {
 690   if (conflicting->ar ==EQ )
 691     {
 692       good->expr = constraintExpr_searchandreplace (good->expr, conflicting->lexpr, conflicting->expr);
 693       good = constraint_simplify (good);
 694     }
 695
 696
 697 }
 698
 699 static bool conflict (constraint c, constraintList list)
 700 {
 701
 702   constraintList_elements (list, el)
 703     {
 704       if ( constraint_conflict(el, c) )
 705         {
 706           constraint_fixConflict (el, c);
 707           return TRUE;
 708         }
 709     } end_constraintList_elements;
 710
 711     return FALSE;
 712
 713 }
 714
 715 /*
 716   check if constraint in list1 conflicts with constraints in List2.  If so we
 717   remove form list1 and change list2.
 718 */
 719
 720 constraintList constraintList_fixConflicts (constraintList list1, constraintList list2)
 721 {
 722   constraintList ret;
 723   ret = constraintList_makeNew();
 724   llassert(constraintList_isDefined(list1) );
 725   constraintList_elements (list1, el)
 726     {
 727       if (! conflict (el, list2) )
 728         {
 729           constraint temp;
 730           temp = constraint_copy(el);
 731           ret = constraintList_add (ret, temp);
 732         }
 733     } end_constraintList_elements;
 734
 735     return ret;
 736 }
 737
 738 /*returns true if constraint post satifies cosntriant pre */
 739 static bool satifies (constraint pre, constraint post)
 740 {
 741   if (constraint_isAlwaysTrue (pre)  )
 742     return TRUE;
 743
 744   if (!constraintExpr_similar (pre->lexpr, post->lexpr) )
 745     {
 746       return FALSE;
 747     }
 748   if (constraintExpr_isUndefined(post->expr))
 749     {
 750       llassert(FALSE);
 751       return FALSE;
 752     }
 753
 754   return rangeCheck (pre->ar, pre->expr, post->ar, post->expr);
 755 }
 756
 757
 758 bool constraintList_resolve (/*@temp@*/ /*@observer@*/ constraint c, /*@temp@*/ /*@observer@*/ constraintList p)
 759 {
 760   constraintList_elements (p, el)
 761     {
 762       if ( satifies (c, el) )
 763         {
 764           DPRINTF ((message ("\n%s Satifies %s\n ", constraint_print(el), constraint_print(c) ) ) );
 765           return TRUE;
 766         }
 767         DPRINTF ((message ("\n%s does not satify %s\n ", constraint_print(el), constraint_print(c) ) ) );
 768     }
 769   end_constraintList_elements;
 770   DPRINTF ((message ("no constraints satify %s", constraint_print(c) ) ));
 771   return FALSE;
 772 }
 773
 774 static bool arithType_canResolve (arithType ar1, arithType ar2)
 775 {
 776   switch (ar1)
 777     {
 778     case GTE:
 779     case GT:
 780       if ((ar2 == GT) || (ar2 == GTE) || (ar2 == EQ) )
 781         {
 782           return TRUE;
 783         }
 784       break;
 785
 786     case EQ:
 787       if (ar2 == EQ)
 788         return TRUE;
 789       break;
 790
 791     case LT:
 792     case LTE:
 793       if ((ar2 == LT) || (ar2 == LTE) || (ar2 == EQ) )
 794         return TRUE;
 795       break;
 796     default:
 797       return FALSE;
 798     }
 799   return FALSE;
 800 }
 801
 802 /*checks for the case expr2 == sizeof buf1  and buf1 is a fixed array*/
 803 static bool  sizeofBufComp(constraintExpr buf1, constraintExpr expr2)
 804 {
 805   constraintTerm ct;
 806   exprNode e, t;
 807   sRef s1, s2;
 808   /*@access constraintExpr@*/
 809
 810   if ((expr2->kind != term) && (buf1->kind != term) )
 811     return FALSE;
 812
 813
 814   ct = constraintExprData_termGetTerm(expr2->data);
 815
 816   if (!constraintTerm_isExprNode(ct) )
 817     return FALSE;
 818
 819   e = constraintTerm_getExprNode(ct);
 820
 821   if (e->kind != XPR_SIZEOF)
 822     return FALSE;
 823
 824   t = exprData_getSingle (e->edata);
 825   s1 = exprNode_getSref (t);
 826
 827   s2 = constraintTerm_getsRef(constraintExprData_termGetTerm(buf1->data) );
 828
 829   /*@i223@*/ /*this may be the wronge thing to test for */
 830   if (sRef_similarRelaxed(s1, s2)   || sRef_sameName (s1, s2) )
 831     {
 832       /*@i22*/ /* get rid of this test of now */
 833       /* if (ctype_isFixedArray (sRef_getType (s2) ) ) */
 834         return TRUE;
 835     }
 836   return FALSE;
 837 }
 838
 839 /* look for the special case of
 840    maxSet(buf) >= sizeof(buf) - 1
 841 */
 842
 843 /*@i223@*/ /*need to add some type checking */
 844 static bool sizeOfMaxSet( /*@observer@*/ /*@temp@*/ constraint c)
 845 {
 846   constraintExpr l, r, buf1, buf2, con;
 847
 848   DPRINTF(( message("sizeOfMaxSet: checking %s ", constraint_print(c) )
 849             ));
 850
 851   l = c->lexpr;
 852   r = c->expr;
 853
 854   if (!((c->ar == EQ) || (c->ar == GTE) || (c->ar == LTE) ) )
 855     return FALSE;
 856
 857   /*check if the constraintExpr is MaxSet(buf) */
 858   if (l->kind == unaryExpr)
 859     {
 860       if (constraintExprData_unaryExprGetOp(l->data) == MAXSET)
 861         {
 862           buf1 = constraintExprData_unaryExprGetExpr(l->data);
 863         }
 864       else
 865         return FALSE;
 866     }
 867   else
 868     return FALSE;
 869
 870
 871   if (r->kind != binaryexpr)
 872     return FALSE;
 873
 874   buf2 = constraintExprData_binaryExprGetExpr1(r->data);
 875   con = constraintExprData_binaryExprGetExpr2(r->data);
 876
 877   if (constraintExprData_binaryExprGetOp(r->data) == BINARYOP_MINUS)
 878     {
 879       if (constraintExpr_canGetValue(con) )
 880         {
 881           long i;
 882
 883           i = constraintExpr_getValue(con);
 884           if (i != 1)
 885             {
 886               return FALSE;
 887             }
 888         }
 889       else
 890         return FALSE;
 891     }
 892
 893   if (constraintExprData_binaryExprGetOp(r->data) == BINARYOP_PLUS)
 894     {
 895       if (constraintExpr_canGetValue(con) )
 896         {
 897           long i;
 898
 899           i = constraintExpr_getValue(con);
 900           if (i != -1)
 901             {
 902               return FALSE;
 903             }
 904         }
 905       else
 906         return FALSE;
 907     }
 908
 909   if (sizeofBufComp(buf1, buf2))
 910     {
 911       return TRUE;
 912     }
 913   else
 914     {
 915      return FALSE;
 916     }
 917
 918
 919 }
 920 /*@noaccess constraintExpr@*/
 921
 922 /* We look for constraint which are tautologies */
 923
 924 bool constraint_isAlwaysTrue (/*@observer@*/ /*@temp@*/ constraint c)
 925 {
 926   constraintExpr l, r;
 927   bool rHasConstant;
 928   int rConstant;
 929
 930   l = c->lexpr;
 931   r = c->expr;
 932
 933   DPRINTF(( message("constraint_IsAlwaysTrue:examining %s", constraint_print(c) ) ));
 934
 935   if (sizeOfMaxSet(c) )
 936     return TRUE;
 937
 938   if (constraintExpr_canGetValue(l) && constraintExpr_canGetValue(r) )
 939     {
 940       int cmp;
 941       cmp = constraintExpr_compare (l, r);
 942       switch (c->ar)
 943         {
 944         case EQ:
 945           return (cmp == 0);
 946         case GT:
 947           return (cmp > 0);
 948         case GTE:
 949           return (cmp >= 0);
 950         case LTE:
 951           return (cmp <= 0);
 952         case LT:
 953           return (cmp < 0);
 954
 955         default:
 956           BADEXIT;
 957           /*@notreached@*/
 958           break;
 959         }
 960     }
 961
 962   if (constraintExpr_similar (l,r) )
 963     {
 964       switch (c->ar)
 965         {
 966         case EQ:
 967         case GTE:
 968         case LTE:
 969           return TRUE;
 970
 971         case GT:
 972         case LT:
 973           break;
 974         default:
 975           BADEXIT;
 976           /*@notreached@*/
 977           break;
 978         }
 979     }
 980
 981   l = constraintExpr_copy (c->lexpr);
 982   r = constraintExpr_copy (c->expr);
 983
 984   r = constraintExpr_propagateConstants (r, &rHasConstant, &rConstant);
 985
 986   if (constraintExpr_similar (l,r) && (rHasConstant ) )
 987     {
 988       DPRINTF(( message("constraint_IsAlwaysTrue: after removing constants  %s and %s are similar", constraintExpr_unparse(l), constraintExpr_unparse(r) ) ));
 989       DPRINTF(( message("constraint_IsAlwaysTrue: rconstant is  %d", rConstant ) ));
 990
 991       constraintExpr_free(l);
 992       constraintExpr_free(r);
 993
 994       switch (c->ar)
 995         {
 996         case EQ:
 997           return (rConstant == 0);
 998         case LT:
 999           return (rConstant > 0);
1000         case LTE:
1001           return (rConstant >= 0);
1002         case GTE:
1003           return (rConstant <= 0);
1004         case GT:
1005           return (rConstant < 0);
1006
1007         default:
1008           BADEXIT;
1009           /*@notreached@*/
1010           break;
1011         }
1012     }
1013       else
1014       {
1015         constraintExpr_free(l);
1016         constraintExpr_free(r);
1017         DPRINTF(( message("Constraint %s is not always true", constraint_print(c) ) ));
1018         return FALSE;
1019       }
1020
1021   BADEXIT;
1022 }
1023
1024 static bool rangeCheck (arithType ar1, /*@observer@*/ constraintExpr expr1, arithType ar2, /*@observer@*/ constraintExpr expr2)
1025
1026 {
1027   DPRINTF ((message ("Doing Range CHECK %s and %s", constraintExpr_unparse(expr1), constraintExpr_unparse(expr2) ) ));
1028
1029   if (! arithType_canResolve (ar1, ar2) )
1030     return FALSE;
1031
1032   switch (ar1)
1033  {
1034  case GTE:
1035        if (constraintExpr_similar (expr1, expr2) )
1036           return TRUE;
1037        /*@fallthrough@*/
1038   case GT:
1039     if (!  (constraintExpr_canGetValue (expr1) &&
1040                constraintExpr_canGetValue (expr2) ) )
1041            {
1042                   constraintExpr e1, e2;
1043                   bool p1, p2;
1044                   int const1, const2;
1045
1046                   e1 = constraintExpr_copy(expr1);
1047                   e2 = constraintExpr_copy(expr2);
1048
1049                   e1 = constraintExpr_propagateConstants (e1, &p1, &const1);
1050
1051                   e2 = constraintExpr_propagateConstants (e2, &p2, &const2);
1052
1053                   if (p1 || p2)
1054                      {
1055                       if (!p1)
1056                            const1 = 0;
1057
1058                       if (!p2)
1059                            const2 = 0;
1060
1061                       if (const1 <= const2)
1062                            if (constraintExpr_similar (e1, e2) )
1063                                   {
1064                                          constraintExpr_free(e1);
1065                                          constraintExpr_free(e2);
1066                                          return TRUE;
1067                                        }
1068                       }
1069                   DPRINTF(("Can't Get value"));
1070
1071                   constraintExpr_free(e1);
1072                   constraintExpr_free(e2);
1073                   return FALSE;
1074                 }
1075
1076     if (constraintExpr_compare (expr2, expr1) >= 0)
1077            return TRUE;
1078
1079    return FALSE;
1080   case EQ:
1081     if (constraintExpr_similar (expr1, expr2) )
1082        return TRUE;
1083
1084     return FALSE;
1085   case LTE:
1086     if (constraintExpr_similar (expr1, expr2) )
1087        return TRUE;
1088     /*@fallthrough@*/
1089   case LT:
1090      if (!  (constraintExpr_canGetValue (expr1) &&
1091                 constraintExpr_canGetValue (expr2) ) )
1092             {
1093                   constraintExpr e1, e2;
1094                    bool p1, p2;
1095                    int const1, const2;
1096
1097                    e1 = constraintExpr_copy(expr1);
1098                    e2 = constraintExpr_copy(expr2);
1099
1100                    e1 = constraintExpr_propagateConstants (e1, &p1, &const1);
1101
1102                    e2 = constraintExpr_propagateConstants (e2, &p2, &const2);
1103
1104                    if (p1 || p2)
1105                       {
1106                        if (!p1)
1107                             const1 = 0;
1108
1109                        if (!p2)
1110                             const2 = 0;
1111
1112                        if (const1 >= const2)
1113                             if (constraintExpr_similar (e1, e2) )
1114                                    {
1115                                           constraintExpr_free(e1);
1116                                           constraintExpr_free(e2);
1117                                           return TRUE;
1118                                         }
1119                        }
1120                    constraintExpr_free(e1);
1121                    constraintExpr_free(e2);
1122
1123                    DPRINTF(("Can't Get value"));
1124                    return FALSE;
1125                  }
1126
1127     if (constraintExpr_compare (expr2, expr1) <= 0)
1128            return TRUE;
1129
1130     return FALSE;
1131
1132   default:
1133       llcontbug((message("Unhandled case in switch: %q", arithType_print(ar1) ) ) );
1134   }
1135   BADEXIT;
1136 }
1137
1138 static constraint constraint_searchandreplace (/*@returned@*/ constraint c, constraintExpr old, constraintExpr newExpr)
1139 {
1140   DPRINTF (("Doing replace for lexpr") );
1141   c->lexpr = constraintExpr_searchandreplace (c->lexpr, old, newExpr);
1142   DPRINTF (("Doing replace for expr") );
1143   c->expr = constraintExpr_searchandreplace (c->expr, old, newExpr);
1144   return c;
1145 }
1146
1147 bool constraint_search (constraint c, constraintExpr old) /*@*/
1148 {
1149   bool ret;
1150   ret = FALSE;
1151
1152   ret  = constraintExpr_search (c->lexpr, old);
1153   ret = ret || constraintExpr_search (c->expr, old);
1154   return ret;
1155 }
1156
1157 /* adjust file locs and stuff */
1158 static constraint constraint_adjust (/*@returned@*/ constraint substitute, /*@observer@*/ constraint old)
1159 {
1160   fileloc loc1, loc2, loc3;
1161
1162   DPRINTF ((message("Start adjust on %s and %s", constraint_print(substitute),
1163                      constraint_print(old))
1164                    ));
1165
1166   loc1 = constraint_getFileloc (old);
1167   loc2 = constraintExpr_getFileloc (substitute->lexpr);
1168   loc3 = constraintExpr_getFileloc (substitute->expr);
1169
1170   /* special case of an equality that "contains itself" */
1171   if (constraintExpr_search (substitute->expr, substitute->lexpr) )
1172       if (fileloc_closer (loc1, loc3, loc2))
1173       {
1174         constraintExpr temp;
1175         DPRINTF ((message("Doing adjust on %s", constraint_print(substitute) )
1176                    ));
1177         temp = substitute->lexpr;
1178         substitute->lexpr = substitute->expr;
1179         substitute->expr  = temp;
1180         substitute = constraint_simplify(substitute);
1181       }
1182
1183   fileloc_free (loc1);
1184   fileloc_free (loc2);
1185   fileloc_free (loc3);
1186
1187   return substitute;
1188
1189 }
1190
1191 /* If function preforms substitutes based on inequality
1192
1193    It uses the rule x >= y && b < y  ===> x >= b + 1
1194
1195    Warning this is sound but throws out information
1196  */
1197
1198 constraint  inequalitySubstitute  (/*@returned@*/ constraint c, constraintList p)
1199 {
1200   if (c->ar != GTE)
1201     return c;
1202
1203   constraintList_elements (p, el)
1204     {
1205       if ((el->ar == LT )  )
1206         /* if (!constraint_conflict (c, el) ) */ /*@i523 explain this! */
1207            {
1208              constraintExpr  temp2;
1209
1210              /*@i22*/
1211
1212              if (constraintExpr_same (el->expr, c->expr) )
1213                {
1214                  DPRINTF((message ("inequalitySubstitute Replacing %q in %q with  %q",
1215                                    constraintExpr_print (c->expr),
1216                                    constraint_print (c),
1217                                    constraintExpr_print (el->expr) )
1218                           ));
1219                  temp2   = constraintExpr_copy (el->lexpr);
1220                  constraintExpr_free(c->expr);
1221                  c->expr =  constraintExpr_makeIncConstraintExpr (temp2);
1222
1223                }
1224
1225            }
1226     }
1227   end_constraintList_elements;
1228
1229   c = constraint_simplify(c);
1230   return c;
1231 }
1232
1233
1234 /* drl7x 7/26/001
1235
1236    THis function is like inequalitySubstitute but it adds the rule
1237    added the rules x >= y &&  y <= b  ===> x >= b
1238     x >= y &&  y < b  ===> x >= b + 1
1239
1240    This is sound but sonce it throws out additional information it should only one used
1241    if we're oring constraints.
1242  */
1243
1244 static constraint  inequalitySubstituteStrong  (/*@returned@*/ constraint c, constraintList p)
1245 {
1246   DPRINTF (( message ("inequalitySubstituteStrong examining substituting for %q", constraint_print(c) ) ));
1247
1248   if (c->ar != GTE)
1249     return c;
1250
1251   DPRINTF (( message ("inequalitySubstituteStrong examining substituting for %q with %q",
1252                       constraint_print(c), constraintList_print(p) ) ));
1253   constraintList_elements (p, el)
1254     {
1255       DPRINTF (( message ("inequalitySubstituteStrong examining substituting %s on %s", constraint_print(el), constraint_print(c) ) ));
1256
1257       if ((el->ar == LT ) ||  (el->ar == LTE )  )
1258         /* if (!constraint_conflict (c, el) ) */ /*@i523@*/
1259            {
1260              constraintExpr  temp2;
1261
1262              /*@i22*/
1263
1264              if (constraintExpr_same (el->lexpr, c->expr) )
1265                {
1266                  DPRINTF((message ("inequalitySubstitute Replacing %s in %s with  %s",
1267                                    constraintExpr_print (c->expr),
1268                                    constraint_print (c),
1269                                    constraintExpr_print (el->expr) )
1270                           ));
1271                  temp2   = constraintExpr_copy (el->expr);
1272                  constraintExpr_free(c->expr);
1273                  if ((el->ar == LTE ) )
1274                    {
1275                      c->expr = temp2;
1276                    }
1277                  else
1278                    {
1279                      c->expr =  constraintExpr_makeIncConstraintExpr (temp2);
1280                    }
1281                }
1282
1283            }
1284     }
1285   end_constraintList_elements;
1286
1287   c = constraint_simplify(c);
1288   return c;
1289 }
1290
1291
1292 /* This function performs substitutions based on the rule:
1293    for a constraint of the form expr1 >= expr2;   a < b =>
1294    a = b -1 for all a in expr1.  This will work in most cases.
1295
1296    Like inequalitySubstitute we're throwing away some information
1297 */
1298
1299 static constraint  inequalitySubstituteUnsound  (/*@returned@*/ constraint c, constraintList p)
1300 {
1301   DPRINTF (( message ("Doing inequalitySubstituteUnsound " ) ));
1302
1303   if (c->ar != GTE)
1304     return c;
1305
1306   constraintList_elements (p, el)
1307     {
1308   DPRINTF (( message ("inequalitySubstituteUnsound examining substituting %s on %s", constraint_print(el), constraint_print(c) ) ));
1309        if (( el->ar == LTE) || (el->ar == LT) )
1310          /* if (!constraint_conflict (c, el) ) */ /*@i532@*/
1311            {
1312              constraintExpr  temp2;
1313
1314              temp2   = constraintExpr_copy (el->expr);
1315
1316              if (el->ar == LT)
1317                temp2  =  constraintExpr_makeDecConstraintExpr (temp2);
1318
1319              DPRINTF((message ("Replacing %s in %s with  %s",
1320                                constraintExpr_print (el->lexpr),
1321                                constraintExpr_print (c->lexpr),
1322                                constraintExpr_print (temp2) ) ));
1323
1324              c->lexpr = constraintExpr_searchandreplace (c->lexpr, el->lexpr, temp2);
1325              constraintExpr_free(temp2);
1326            }
1327     }
1328   end_constraintList_elements;
1329
1330   c = constraint_simplify(c);
1331   return c;
1332 }
1333
1334 /*@only@*/ constraint constraint_substitute (/*@observer@*/ /*@temp@*/ constraint c, constraintList p)
1335 {
1336   constraint ret;
1337
1338   ret = constraint_copy(c);
1339   constraintList_elements (p, el)
1340     {
1341        if ( el->ar == EQ)
1342          if (!constraint_conflict (ret, el) )
1343
1344            {
1345              constraint temp;
1346
1347              temp = constraint_copy(el);
1348
1349              temp = constraint_adjust(temp, ret);
1350
1351              DPRINTF((message ("constraint_substitute :: Substituting in %s using %s",
1352                                constraint_print (ret), constraint_print (temp)
1353                                ) ) );
1354
1355
1356              ret = constraint_searchandreplace (ret, temp->lexpr, temp->expr);
1357              DPRINTF(( message (" constraint_substitute :: The new constraint is %s", constraint_print (ret) ) ));
1358              constraint_free(temp);
1359            }
1360     }
1361   end_constraintList_elements;
1362
1363   ret = constraint_simplify(ret);
1364
1365   DPRINTF(( message (" constraint_substitute :: The final new constraint is %s", constraint_print (ret) ) ));
1366
1367   return ret;
1368 }
1369
1370
1371 /*@only@*/ constraintList constraintList_substituteFreeTarget (/*@only@*/ constraintList target, /*@observer@*/ constraintList subList)
1372 {
1373 constraintList ret;
1374
1375 ret = constraintList_substitute (target, subList);
1376
1377 constraintList_free(target);
1378
1379 return ret;
1380 }
1381
1382 /* we try to do substitutions on each constraint in target using the constraint in sublist*/
1383
1384 /*@only@*/ constraintList constraintList_substitute (constraintList target,/*2observer@*/  constraintList subList)
1385 {
1386
1387   constraintList ret;
1388
1389   ret = constraintList_makeNew();
1390
1391   constraintList_elements(target, el)
1392   {
1393     constraint temp;
1394     /* drl possible problem : warning make sure that a side effect is not expected */
1395
1396     temp = constraint_substitute(el, subList);
1397     ret = constraintList_add (ret, temp);
1398   }
1399   end_constraintList_elements;
1400
1401   return ret;
1402 }
1403
1404 static constraint constraint_solve (/*@returned@*/ constraint c)
1405 {
1406   DPRINTF((message ("Solving %s\n", constraint_print(c) ) ) );
1407   c->expr = constraintExpr_solveBinaryExpr (c->lexpr, c->expr);
1408   DPRINTF((message ("Solved and got %s\n", constraint_print(c) ) ) );
1409
1410   return c;
1411 }
1412
1413 static arithType flipAr (arithType ar)
1414 {
1415   switch (ar)
1416     {
1417     case LT:
1418       return GT;
1419     case LTE:
1420       return GTE;
1421     case EQ:
1422       return EQ;
1423     case GT:
1424       return LT;
1425     case GTE:
1426       return LTE;
1427     default:
1428       llcontbug (message("unexpected value: case not handled"));
1429     }
1430   BADEXIT;
1431 }
1432
1433 static constraint  constraint_swapLeftRight (/*@returned@*/ constraint c)
1434 {
1435   constraintExpr temp;
1436   c->ar = flipAr (c->ar);
1437   temp = c->lexpr;
1438   c->lexpr = c->expr;
1439   c->expr = temp;
1440   DPRINTF(("Swaped left and right sides of constraint"));
1441   return c;
1442 }
1443
1444
1445
1446 constraint constraint_simplify ( /*@returned@*/ constraint c)
1447 {
1448
1449   DPRINTF(( message("constraint_simplify on %q ", constraint_print(c) ) ));
1450
1451   if (constraint_tooDeep(c))
1452     {
1453         DPRINTF(( message("constraint_simplify: constraint to complex aborting %q ", constraint_print(c) ) ));
1454       return c;
1455
1456     }
1457
1458   c->lexpr = constraintExpr_simplify (c->lexpr);
1459   c->expr  = constraintExpr_simplify (c->expr);
1460
1461   if (constraintExpr_isBinaryExpr (c->lexpr) )
1462     {
1463       c = constraint_solve (c);
1464
1465       c->lexpr = constraintExpr_simplify (c->lexpr);
1466       c->expr  = constraintExpr_simplify (c->expr);
1467     }
1468
1469   if (constraintExpr_isLit(c->lexpr) && (!constraintExpr_isLit(c->expr) ) )
1470     {
1471       c = constraint_swapLeftRight(c);
1472       /*I don't think this will be an infinate loop*/
1473       c = constraint_simplify(c);
1474     }
1475
1476   DPRINTF(( message("constraint_simplify returning  %q ", constraint_print(c) ) ));
1477
1478   return c;
1479 }
1480
1481
1482
1483
1484 /* returns true  if fileloc for term1 is closer to file for term2 than term3*/
1485
1486 bool fileloc_closer (fileloc  loc1, fileloc  loc2, fileloc  loc3)
1487 {
1488
1489   if  (!fileloc_isDefined (loc1) )
1490     return FALSE;
1491
1492   if  (!fileloc_isDefined (loc2) )
1493     return FALSE;
1494
1495   if  (!fileloc_isDefined (loc3) )
1496     return TRUE;
1497
1498
1499
1500
1501   if (fileloc_equal (loc2, loc3) )
1502     return FALSE;
1503
1504   if (fileloc_equal (loc1, loc2) )
1505     return TRUE;
1506
1507     if (fileloc_equal (loc1, loc3) )
1508     return FALSE;
1509
1510    if ( fileloc_lessthan (loc1, loc2) )
1511      {
1512        if (fileloc_lessthan (loc2, loc3) )
1513          {
1514            llassert (fileloc_lessthan (loc1, loc3) );
1515            return TRUE;
1516          }
1517        else
1518          {
1519            return FALSE;
1520          }
1521      }
1522
1523    if ( !fileloc_lessthan (loc1, loc2) )
1524      {
1525        if (!fileloc_lessthan (loc2, loc3) )
1526          {
1527            llassert (!fileloc_lessthan (loc1, loc3) );
1528            return TRUE;
1529          }
1530        else
1531          {
1532            return FALSE;
1533          }
1534      }
1535
1536    llassert(FALSE);
1537    return FALSE;
1538 }
1539
1540