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