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