src/constraintResolve.c

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