src/constraintResolve.c

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