src/constraintResolve.c

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