src/environmentTable.c

   1 /*
   2 ** LCLint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2000 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 lclint: lclint-request@cs.virginia.edu
  21 ** To report a bug: lclint-bug@cs.virginia.edu
  22 ** For more information: http://lclint.cs.virginia.edu
  23 */
  24 /*
  25 ** environmentTable.c
  26 */
  27
  28 # include "lclintMacros.nf"
  29 # include "basic.h"
  30
  31 //#include "environmentTable.h"
  32
  33 /*@constant int ATINVALID; @*/
  34 # define ATINVALID -1
  35
  36 #define ENVIRONMENTSEARCHLIMIT ALIASSEARCHLIMIT
  37 #define  FLG_GLOBENVIRONMENT FLG_GLOBALIAS
  38 #define NOENVIRONMENT NOALIAS
  39
  40 static sRefSet
  41   environmentTable_canEnvironmentAux (environmentTable p_s, sRef p_sr, int p_lim) /*@*/ ;
  42 static sRefSet
  43   environmentTable_aliasedByLimit (environmentTable p_s, sRef p_sr, int p_lim) /*@*/ ;
  44 static sRefSet
  45   environmentTable_aliasedByAux (environmentTable p_s, sRef p_sr, int p_lim) /*@*/ ;
  46
  47 environmentTable
  48 environmentTable_new ()
  49 {
  50   return (environmentTable_undefined);
  51 }
  52
  53 static /*@only@*/ /*@notnull@*/ environmentTable
  54 environmentTable_newEmpty (void)
  55 {
  56   environmentTable s = (environmentTable) dmalloc (sizeof (*s));
  57
  58   s->nelements = 0;
  59   s->nspace = environmentTableBASESIZE;
  60   s->keys     = (sRef *) dmalloc (sizeof (*s->keys) * environmentTableBASESIZE);
  61   s->values   = (sRefSet *) dmalloc (sizeof (*s->values) * environmentTableBASESIZE);
  62   s->rangeValues    = (rangeAt*) dmalloc (sizeof (*s->rangeValues) * environmentTableBASESIZE);
  63   return (s);
  64 }
  65
  66 static void
  67 environmentTable_grow (/*@notnull@*/ environmentTable s)
  68 {
  69   int i;
  70   o_sRefSet *oldvalues = s->values;
  71   sRef    *oldkeys = s->keys;
  72   rangeAt *oldranges = s->rangeValues;
  73
  74   s->nspace += environmentTableBASESIZE;
  75
  76   s->values = (sRefSet *) dmalloc (sizeof (*s->values)
  77                                    * (s->nelements + s->nspace));
  78   s->keys = (sRef *) dmalloc (sizeof (*s->keys) * (s->nelements + environmentTableBASESIZE));
  79
  80   s->rangeValues = (rangeAt *) dmalloc (sizeof (*s->rangeValues) * (s->nelements + environmentTableBASESIZE));
  81
  82
  83   if (s->keys == (sRef *) 0 || s->values == (sRefSet *)0 || s->rangeValues == (rangeAt*) 0 )
  84     {
  85       llfatalerror (cstring_makeLiteral ("environmentTable_grow: out of memory!"));
  86     }
  87
  88   for (i = 0; i < s->nelements; i++)
  89     {
  90       s->values[i] = oldvalues[i];
  91       s->keys[i] = oldkeys[i];
  92       s->rangeValues[i] = oldranges[i];
  93     }
  94   //  s->rangeValues[i] = dmalloc (sizeof (rangeAt));
  95   sfree (oldvalues);
  96   sfree (oldkeys);
  97   sfree (oldranges);
  98 }
  99
 100
 101
 102 static int environmentTable_lookupRefs (/*@notnull@*/ environmentTable s, sRef sr)
 103 {
 104   int i;
 105
 106
 107   for (i = 0; i < environmentTable_size (s); i++)
 108     {
 109       if (sRef_same (sr, s->keys[i]))
 110         {
 111           return i;
 112         }
 113     }
 114
 115   return ATINVALID;
 116 }
 117
 118 environmentTable
 119 environmentTable_postOpvar (/*@returned@*/ environmentTable s, sRef sr)
 120 {
 121   int ind;
 122   // printf("doing postop\n");
 123   if (environmentTable_isUndefined (s) )
 124     {
 125       s = environmentTable_newEmpty();
 126     }
 127
 128   ind = environmentTable_lookupRefs (s, sr);
 129   if (ind == ATINVALID)
 130     {
 131       s = environmentTable_addRelativeRange (s, sr);
 132       ind = s->nelements;
 133     }
 134   // assume it ++ we'll do -- later
 135
 136   s->rangeValues[ind].max++;
 137   s->rangeValues[ind].min++;
 138
 139   return s;
 140 }
 141
 142 environmentTable
 143 environmentTable_mergeEnvironments (environmentTable s1, environmentTable s2)
 144 {
 145   int i;
 146   environmentTable t1;
 147   t1 = environmentTable_copy (s1);
 148   if (environmentTable_isUndefined (s2) )
 149     return t1;
 150
 151   for (i = 0; i < s2->nelements; i++)
 152     {
 153       int ind = environmentTable_lookupRefs ( t1, s1->keys[i]);
 154       if (s2->rangeValues[i].isRelative)
 155         {
 156           if (ind == ATINVALID)
 157             {
 158               t1 = environmentTable_insertRelativeRange(t1, s2->keys[i], s2->rangeValues[i].max,  s2->rangeValues[i].min);
 159             }
 160           else
 161             {
 162               t1->rangeValues[ind].min += s2->rangeValues[i].min;
 163               t1->rangeValues[ind].max += s2->rangeValues[i].max;
 164             }
 165         }
 166       else
 167         {
 168           /* we want to overwrite old value .. */
 169           t1 = environmentTable_addExactValue (t1, s2->keys[i], s2->rangeValues[i].max);
 170           /*should fix this to do min and max ... */
 171         }
 172
 173     }
 174 }
 175
 176 rangeAt
 177 rangeAt_createRelativeRange ()
 178 {
 179   rangeAt tmp;
 180   tmp.isRelative = TRUE;
 181   tmp.unknown = FALSE;
 182   tmp.max = 0;
 183   tmp.min = 0;
 184   return tmp;
 185 }
 186
 187 rangeAt rangeAt_createExactRange (int min, int max)
 188 {
 189   rangeAt tmp;
 190   tmp.isRelative = FALSE;
 191   tmp.unknown = FALSE;
 192   tmp.min = min;
 193   tmp.max = max;
 194   return tmp;
 195 }
 196
 197 environmentTable
 198 environmentTable_addRelativeRange (/*@returned@*/ environmentTable s,
 199                          /*@exposed@*/ sRef sr)
 200 {
 201   int ind;
 202   sRefSet ss;
 203   rangeAt range;
 204
 205   if (environmentTable_isUndefined (s))
 206     {
 207       s = environmentTable_newEmpty ();
 208       ind = ATINVALID;
 209     }
 210   else
 211     {
 212       ind = environmentTable_lookupRefs (s, sr);
 213     }
 214
 215   if (ind == ATINVALID)
 216     {
 217       if (s->nspace <= 0) {
 218         environmentTable_grow (s);
 219       }
 220
 221       s->nspace--;
 222       s->keys[s->nelements] = sr;
 223       /*fix this */
 224       //  s->values[s->nelements] = sRefSet_single (al);
 225       ind = s->nelements;
 226       s->nelements++;
 227     }
 228   range = rangeAt_createRelativeRange();
 229
 230   s->rangeValues[ind] = range;
 231   return s;
 232 }
 233
 234 void
 235 environmentTable_testInRange ( environmentTable s,  /*@exposed@*/ sRef sr, int index)
 236 {
 237   int ind;
 238   sRefSet ss;
 239   rangeAt range;
 240   if (environmentTable_isUndefined (s))
 241     {
 242       fprintf(stderr,"environmentTable not defined\n");
 243       return;
 244     }
 245
 246   ind = environmentTable_lookupRefs (s, sr);
 247   if (ind == ATINVALID)
 248     {
 249       fprintf (stderr,"range not known\n");
 250       return;
 251     }
 252   if ( &s->rangeValues[ind] )
 253     {
 254       if ( (s->rangeValues[ind].min <= index ) && (s->rangeValues[ind].max >= index) )
 255         {
 256           printf("The value %d is in the range for this variable \n", index);
 257         }
 258       else
 259           printf("The value %d is NOT in the range for this variable \n", index);
 260     }
 261
 262 }
 263
 264
 265 environmentTable
 266 environmentTable_addExactValue (/*@returned@*/ environmentTable s,
 267                          /*@exposed@*/ sRef sr,
 268                          int val)
 269 {
 270   int ind;
 271   sRefSet ss;
 272   rangeAt range;
 273
 274   if (environmentTable_isUndefined (s))
 275     {
 276       s = environmentTable_newEmpty ();
 277       ind = ATINVALID;
 278     }
 279   else
 280     {
 281       ind = environmentTable_lookupRefs (s, sr);
 282     }
 283
 284   if (ind == ATINVALID)
 285     {
 286       if (s->nspace <= 0) {
 287         environmentTable_grow (s);
 288       }
 289
 290       s->nspace--;
 291       s->keys[s->nelements] = sr;
 292       /*fix this */
 293       //  s->values[s->nelements] = sRefSet_single (al);
 294       ind = s->nelements;
 295       s->nelements++;
 296     }
 297
 298   else
 299     {
 300       /*   s->values[ind] = sRefSet_insert (s->values[ind], al);  */
 301     }
 302   /*
 303   if ( (s->rangeValues[ind]) == 0 )
 304     {
 305       s->rangeValues[ind] = dmalloc(sizeof(rangeAt) );
 306     }
 307   */
 308   range.min = val;
 309   range.max = val;
 310
 311   s->rangeValues[ind] = range;
 312   return s;
 313 }
 314
 315 environmentTable
 316 environmentTable_insertRelativeRange (/*@returned@*/ environmentTable s,
 317                          /*@exposed@*/ sRef sr,
 318                          int min, int max)
 319 {
 320   int ind;
 321   sRefSet ss;
 322   rangeAt range;
 323
 324   if (environmentTable_isUndefined (s))
 325     {
 326       s = environmentTable_newEmpty ();
 327       ind = ATINVALID;
 328     }
 329   else
 330     {
 331       ind = environmentTable_lookupRefs (s, sr);
 332     }
 333
 334   if (ind == ATINVALID)
 335     {
 336       if (s->nspace <= 0) {
 337         environmentTable_grow (s);
 338       }
 339
 340       s->nspace--;
 341       s->keys[s->nelements] = sr;
 342       /*fix this */
 343       //  s->values[s->nelements] = sRefSet_single (al);
 344       ind = s->nelements;
 345       s->nelements++;
 346     }
 347
 348   range = rangeAt_createRelativeRange();
 349   range.min = min;
 350   range.max = max;
 351
 352   s->rangeValues[ind] = range;
 353   return s;
 354 }
 355
 356 environmentTable
 357 environmentTable_addMustAlias (/*@returned@*/ environmentTable s,
 358                          /*@exposed@*/ sRef sr,
 359                          sRef al)
 360 {
 361   int ind;
 362   sRefSet ss;
 363
 364   llassert (NOENVIRONMENT (sr, al));
 365
 366   if (environmentTable_isUndefined (s))
 367     {
 368       s = environmentTable_newEmpty ();
 369       ind = ATINVALID;
 370     }
 371   else
 372     {
 373       ind = environmentTable_lookupRefs (s, sr);
 374     }
 375
 376   ss = environmentTable_canEnvironment (s, al);
 377
 378
 379   if (ind == ATINVALID)
 380     {
 381       if (s->nspace <= 0) {
 382         environmentTable_grow (s);
 383       }
 384
 385       s->nspace--;
 386       s->keys[s->nelements] = sr;
 387       s->values[s->nelements] = sRefSet_single (al);
 388       ind = s->nelements;
 389       s->nelements++;
 390     }
 391   else
 392     {
 393       s->values[ind] = sRefSet_insert (s->values[ind], al);
 394     }
 395
 396   s->values[ind] = sRefSet_unionExcept (s->values[ind], ss, s->keys[ind]);
 397
 398   sRefSet_free (ss);
 399   return s;
 400 }
 401
 402 static environmentTable
 403   environmentTable_addSet (/*@returned@*/ environmentTable s,
 404                      /*@exposed@*/ sRef key, /*@only@*/ sRefSet value)
 405 {
 406   if (!sRefSet_isEmpty (value))
 407     {
 408       if (environmentTable_isUndefined (s))
 409         {
 410           s = environmentTable_newEmpty ();
 411         }
 412       else
 413         {
 414           if (s->nspace <= 0)
 415             {
 416               environmentTable_grow (s);
 417             }
 418         }
 419
 420       s->nspace--;
 421       s->keys[s->nelements] = key;
 422       s->values[s->nelements] = value;
 423       s->nelements++;
 424     }
 425   else
 426     {
 427       sRefSet_free (value);
 428     }
 429
 430   return s;
 431 }
 432
 433 /*
 434 ** When environmentes are cleared:
 435 **
 436 **    o remove all entries for sr
 437 **    o replace all environmentes for things which environment sr with sr's environmentes
 438 **
 439 ** Clear environmentes for sr; if sr is a direct param reference, clear its environmentes too.
 440 */
 441
 442 static void environmentTable_clearEnvironmentesAux (/*@notnull@*/ environmentTable p_s, sRef p_sr)
 443    /*@modifies p_s@*/ ;
 444
 445 void environmentTable_clearEnvironmentes (environmentTable s, sRef sr)
 446 {
 447   if (environmentTable_isUndefined (s))
 448     {
 449       return;
 450     }
 451   else
 452     {
 453       sRef rb = sRef_getRootBase (sr);
 454
 455
 456       if (!sRef_isCvar (sr) && sRef_isLocalVar (rb))
 457         {
 458           int ind = environmentTable_lookupRefs (s, rb);
 459
 460           if (ind != ATINVALID)
 461             {
 462               sRefSet al = s->values[ind];
 463
 464
 465               sRefSet_realElements (al, el)
 466                 {
 467
 468                   if (sRef_isParam (el))
 469                     {
 470                       if (sRef_sameName (el, rb))
 471                         {
 472                           sRef fb = sRef_fixBase (sr, el);
 473
 474                           environmentTable_clearEnvironmentesAux (s, fb);
 475                         }
 476                     }
 477                 } end_sRefSet_realElements ;
 478             }
 479         }
 480
 481       environmentTable_clearEnvironmentesAux (s, sr);
 482     }
 483 }
 484
 485 static
 486 void environmentTable_clearEnvironmentesAux (/*@notnull@*/ environmentTable s, sRef sr)
 487 {
 488   int i;
 489
 490   for (i = 0; i < s->nelements; i++)
 491     {
 492       sRef key = s->keys[i];
 493
 494       if (sRef_includedBy (key, sr))
 495         {
 496           sRefSet_clear (s->values[i]);
 497         }
 498       else
 499         {
 500           (void) sRefSet_deleteBase (s->values[i], sr);
 501         }
 502     }
 503 }
 504
 505 /*
 506 ** returns set of all sRefs that must environment sr (but are different from sr)
 507 */
 508
 509 static /*@only@*/ sRefSet environmentTable_environmentedByAux (environmentTable s, sRef sr, int lim)
 510 {
 511   static bool hadWarning = FALSE;
 512   sRefSet res = sRefSet_undefined;
 513   int i;
 514
 515   llassert (!sRef_isConj (sr));
 516
 517
 518   if (environmentTable_isUndefined (s) || lim >= ENVIRONMENTSEARCHLIMIT)
 519     {
 520       if (lim >= ENVIRONMENTSEARCHLIMIT && !hadWarning)
 521         {
 522           llquietbug
 523             (message ("Environment search limit exceeded, checking %q. "
 524                       "This either means there is a variable with at least "
 525                       "%d indirections, or there is a bug in LCLint.",
 526                       sRef_unparse (sr),
 527                       ENVIRONMENTSEARCHLIMIT));
 528
 529           hadWarning = TRUE;
 530         }
 531
 532       return sRefSet_undefined;
 533     }
 534   else
 535     {
 536       sRefSet abl;
 537
 538       if (sRef_isPointer (sr))
 539         {
 540           abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim);
 541           res = sRefSet_addIndirection (abl);
 542         }
 543       else if (sRef_isAddress (sr))
 544         {
 545           abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim);
 546           res = sRefSet_removeIndirection (abl);
 547         }
 548       else if (sRef_isField (sr))
 549         {
 550           abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim);
 551           res = sRefSet_accessField (abl, sRef_getField (sr));
 552         }
 553       else if (sRef_isArrayFetch (sr))
 554         {
 555           abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim);
 556
 557           if (sRef_isIndexKnown (sr))
 558             {
 559               int idx = sRef_getIndex (sr);
 560
 561               res = sRefSet_fetchKnown (abl, idx);
 562             }
 563           else
 564             {
 565               res = sRefSet_fetchUnknown (abl);
 566             }
 567         }
 568       else
 569         {
 570           abl = sRefSet_undefined;
 571         }
 572
 573       sRefSet_free (abl);
 574     }
 575
 576   for (i = 0; i < s->nelements; i++)
 577     {
 578       sRef elem = s->keys[i];
 579
 580       if (!sRef_same (sr, elem)) /* was sameName */
 581         {
 582
 583           sRefSet_realElements (s->values[i], current)
 584             {
 585
 586               if (sRef_similar (sr, current))
 587                 {
 588                                                   res = sRefSet_insert (res, sRef_fixOuterRef (elem));
 589                   /*@innerbreak@*/ break;
 590                 }
 591             } end_sRefSet_realElements;
 592         }
 593     }
 594
 595     return res;
 596 }
 597
 598 static /*@only@*/ sRefSet environmentTable_environmentedByLimit (environmentTable s, sRef sr, int lim)
 599 {
 600   sRefSet res;
 601
 602
 603   if (sRef_isConj (sr))
 604     {
 605       res = sRefSet_unionFree (environmentTable_environmentedByLimit (s, sRef_getConjA (sr), lim),
 606                                environmentTable_environmentedByLimit (s, sRef_getConjB (sr), lim));
 607     }
 608   else
 609     {
 610       res = environmentTable_environmentedByAux (s, sr, lim + 1);
 611     }
 612
 613     return res;
 614 }
 615
 616 /*@only@*/ sRefSet environmentTable_environmentedBy (environmentTable s, sRef sr)
 617 {
 618   if (sRef_isConj (sr))
 619     {
 620       return (sRefSet_unionFree (environmentTable_environmentedBy (s, sRef_getConjA (sr)),
 621                                  environmentTable_environmentedBy (s, sRef_getConjB (sr))));
 622     }
 623
 624   return (environmentTable_environmentedByAux (s, sr, 0));
 625 }
 626
 627 /*@only@*/ sRefSet environmentTable_canEnvironment (environmentTable s, sRef sr)
 628 {
 629   sRefSet res;
 630
 631
 632   if (sRef_isConj (sr))
 633     {
 634       res = sRefSet_unionFree (environmentTable_canEnvironment (s, sRef_getConjA (sr)),
 635                                environmentTable_canEnvironment (s, sRef_getConjB (sr)));
 636     }
 637   else
 638     {
 639       res = environmentTable_canEnvironmentAux (s, sr, 0);
 640           }
 641
 642     return res;
 643 }
 644
 645 /*
 646 ** need to limit the depth of environmenting searches
 647 */
 648
 649 static /*@only@*/ sRefSet environmentTable_canEnvironmentLimit (environmentTable s, sRef sr, int lim)
 650 {
 651   sRefSet res;
 652
 653   if (sRef_isConj (sr))
 654     {
 655       sRefSet a = environmentTable_canEnvironmentLimit (s, sRef_getConjA (sr), lim);
 656       sRefSet b = environmentTable_canEnvironmentLimit (s, sRef_getConjB (sr), lim);
 657
 658       res = sRefSet_unionFree (a, b);
 659     }
 660   else
 661     {
 662       res = environmentTable_canEnvironmentAux (s, sr, lim + 1);
 663     }
 664
 665   return res;
 666 }
 667
 668 static /*@only@*/ sRefSet
 669   environmentTable_canEnvironmentAux (environmentTable s, sRef sr, int lim)
 670 {
 671   static bool hadWarning = FALSE;
 672   llassert (!sRef_isConj (sr));
 673
 674
 675   if (environmentTable_isUndefined (s) || lim >= ALIASSEARCHLIMIT)
 676     {
 677       if (lim >= ALIASSEARCHLIMIT && !hadWarning)
 678         {
 679           llquietbug
 680             (message ("Environment search limit exceeded, checking %q. "
 681                       "This either means there is a variable with at least "
 682                       "%d indirections, or there is a bug in LCLint.",
 683                       sRef_unparse (sr),
 684                       ENVIRONMENTSEARCHLIMIT));
 685
 686           hadWarning = TRUE;
 687         }
 688
 689       return sRefSet_undefined;
 690     }
 691   else
 692     {
 693       int ind = environmentTable_lookupRefs (s, sr);
 694
 695       if (sRef_isPointer (sr) || sRef_isAddress (sr) || sRef_isField (sr)
 696           || sRef_isArrayFetch (sr))
 697         {
 698           sRef base = sRef_getBase (sr);
 699           sRefSet tmp = environmentTable_canEnvironmentLimit (s, base, lim);
 700           sRefSet ret;
 701
 702           if (sRef_isPointer (sr))
 703             {
 704               ret = sRefSet_addIndirection (tmp);
 705             }
 706           else if (sRef_isAddress (sr))
 707             {
 708               ret = sRefSet_removeIndirection (tmp);
 709             }
 710           else if (sRef_isField (sr))
 711             {
 712               ret = sRefSet_accessField (tmp, sRef_getField (sr));
 713             }
 714           else if (sRef_isArrayFetch (sr))
 715             {
 716               if (sRef_isIndexKnown (sr))
 717                 {
 718                   ret = sRefSet_fetchKnown (tmp, sRef_getIndex (sr));
 719                 }
 720               else
 721                 {
 722                   ret = sRefSet_fetchUnknown (tmp);
 723                 }
 724             }
 725           else
 726             {
 727               BADBRANCH;
 728             }
 729
 730           if (ind != ATINVALID)
 731             {
 732               ret = sRefSet_union (ret, s->values[ind]);
 733             }
 734
 735           sRefSet_free (tmp);
 736                   return ret;
 737         }
 738
 739       if (ind == ATINVALID) return sRefSet_undefined;
 740
 741       return sRefSet_newCopy (s->values[ind]);
 742     }
 743 }
 744
 745 environmentTable environmentTable_copy (environmentTable s)
 746 {
 747   if (environmentTable_isEmpty (s))
 748     {
 749       return environmentTable_undefined;
 750     }
 751   else
 752     {
 753       environmentTable t = (environmentTable) dmalloc (sizeof (*s));
 754       int i;
 755
 756       t->nelements = s->nelements;
 757       t->nspace = 0;
 758       t->keys = (sRef *) dmalloc (sizeof (*s->keys) * s->nelements);
 759       t->values = (sRefSet *) dmalloc (sizeof (*s->values) * t->nelements);
 760       t->rangeValues = (rangeAt *) dmalloc (sizeof (*s->rangeValues) * t->nelements);
 761
 762       for (i = 0; i < s->nelements; i++)
 763         {
 764           t->keys[i] = s->keys[i];
 765           t->values[i] = sRefSet_newCopy (s->values[i]);
 766           t->rangeValues[i] = s->rangeValues[i];
 767         }
 768
 769       return t;
 770     }
 771 }
 772
 773 static void
 774 environmentTable_levelPrune (environmentTable s, int lexlevel)
 775 {
 776
 777
 778   if (environmentTable_isEmpty (s))
 779     {
 780       return;
 781     }
 782   else
 783     {
 784       int i;
 785       int backcount = s->nelements - 1;
 786
 787       for (i = 0; i <= backcount; i++)
 788         {
 789           sRef key = s->keys[i];
 790
 791           if (sRef_lexLevel (key) > lexlevel)
 792             {
 793               int j;
 794               for (j = backcount; j > i; j--)
 795                 {
 796                   backcount--;
 797                   s->nelements--;
 798                   s->nspace++;
 799
 800                   if (sRef_lexLevel (s->keys[j]) <= lexlevel)
 801                     {
 802                       s->keys[i] = s->keys[j];
 803                       s->values[i] = s->values[j];
 804                       sRefSet_levelPrune (s->values[i], lexlevel);
 805                       /*@innerbreak@*/ break;
 806                     }
 807                 }
 808               if (backcount == i)
 809                 s->nelements--;
 810             }
 811           else
 812             {
 813               sRefSet_levelPrune (s->values[i], lexlevel);
 814             }
 815         }
 816     }
 817 }
 818
 819 /*
 820 ** levelUnionSeq
 821 **
 822 **    like level union, but know that t2 was executed after t1.  So if
 823 **    t1 has x -> { a, b } and t2 has x -> { a }, then result has x -> { a }.
 824 **
 825 ** NOTE: t2 is "only".
 826 */
 827
 828 environmentTable environmentTable_levelUnionSeq (/*@returned@*/ environmentTable t1,
 829                                      /*@only@*/ environmentTable t2, int level)
 830 {
 831   if (environmentTable_isUndefined (t2))
 832     {
 833       return t1;
 834     }
 835
 836   if (environmentTable_isUndefined (t1))
 837     {
 838       t1 = environmentTable_newEmpty ();
 839     }
 840   else
 841     {
 842       environmentTable_levelPrune (t1, level);
 843     }
 844
 845   environmentTable_elements (t2, key, value)
 846     {
 847       if (sRef_lexLevel (key) <= level)
 848         {
 849           int ind = environmentTable_lookupRefs (t1, key);
 850
 851           sRefSet_levelPrune (value, level);
 852
 853           if (ind == ATINVALID)
 854             {
 855               /* okay, t2 is killed */
 856               /*@-exposetrans@*/ /*@-dependenttrans@*/
 857               t1 = environmentTable_addSet (t1, key, value);
 858               /*@=exposetrans@*/ /*@=dependenttrans@*/
 859             }
 860           else
 861             {
 862               sRefSet_free (t1->values[ind]);
 863
 864               /*@-dependenttrans@*/ /* okay, t2 is killed */
 865               t1->values[ind] = value;
 866               /*@=dependenttrans@*/
 867             }
 868         }
 869       else
 870         {
 871           /*@-exposetrans@*/ /*@-dependenttrans@*/
 872           sRefSet_free (value);
 873           /*@=exposetrans@*/ /*@=dependenttrans@*/
 874         }
 875
 876     } end_environmentTable_elements;
 877
 878   sfree (t2->keys);
 879   sfree (t2->values);
 880   sfree (t2);
 881
 882     return t1;
 883 }
 884
 885 environmentTable
 886 environmentTable_levelUnion (/*@returned@*/ environmentTable t1, environmentTable t2, int level)
 887 {
 888   if (environmentTable_isUndefined (t1))
 889     {
 890       if (environmentTable_isUndefined (t2))
 891         {
 892           return t1;
 893         }
 894       else
 895         {
 896           t1 = environmentTable_newEmpty ();
 897         }
 898     }
 899   else
 900     {
 901       environmentTable_levelPrune (t1, level);
 902     }
 903
 904   environmentTable_elements (t2, key, cvalue)
 905     {
 906       sRefSet value = sRefSet_newCopy (cvalue);
 907
 908       if (sRef_lexLevel (key) <= level)
 909         {
 910           sRefSet_levelPrune (value, level);
 911
 912           if (sRefSet_size (value) > 0)
 913             {
 914               int ind = environmentTable_lookupRefs (t1, key);
 915
 916               if (ind == ATINVALID)
 917                 {
 918                   t1 = environmentTable_addSet (t1, key, value);
 919                 }
 920               else
 921                 {
 922                   t1->values[ind] = sRefSet_union (t1->values[ind], value);
 923                   sRefSet_free (value);
 924                 }
 925             }
 926           else
 927             {
 928               sRefSet_free (value);
 929             }
 930         }
 931       else
 932         {
 933           sRefSet_free (value);
 934         }
 935     } end_environmentTable_elements;
 936
 937     return t1;
 938 }
 939
 940 environmentTable environmentTable_levelUnionNew (environmentTable t1, environmentTable t2, int level)
 941 {
 942   environmentTable ret = environmentTable_levelUnion (environmentTable_copy (t1), t2, level);
 943
 944   return ret;
 945 }
 946
 947 /*@only@*/ cstring
 948 environmentTable_unparse (environmentTable s)
 949 {
 950    cstring st = cstring_undefined;
 951
 952    if (environmentTable_isUndefined (s)) return (cstring_makeLiteral ("<NULL>"));
 953
 954    environmentTable_elements (s, key, value)
 955      {
 956        st = message ("%q\t%q -> %q\n", st, sRef_unparse (key),
 957                      sRefSet_unparse (value));
 958      } end_environmentTable_elements;
 959
 960    return st;
 961 }
 962
 963 /*
 964 ** bogus!
 965 */
 966
 967 void
 968 environmentTable_fixSrefs (environmentTable s)
 969 {
 970   int i;
 971
 972   if (environmentTable_isUndefined (s)) return;
 973
 974   for (i = 0; i < s->nelements; i++)
 975     {
 976       sRef old = s->keys[i];
 977
 978       if (sRef_isLocalVar (old))
 979         {
 980           s->keys[i] = uentry_getSref (sRef_getUentry (old));
 981         }
 982
 983       sRefSet_fixSrefs (s->values[i]);
 984     }
 985 }
 986
 987 void
 988 environmentTable_free (/*@only@*/ environmentTable s)
 989 {
 990   int i;
 991
 992   if (environmentTable_isUndefined (s)) return;
 993
 994   for (i = 0; i < s->nelements; i++)
 995     {
 996       sRefSet_free (s->values[i]);
 997     }
 998
 999   sfree (s->values);
1000   sfree (s->keys);
1001   sfree (s);
1002 }
1003
1004 void
1005 environmentTable_checkGlobs (environmentTable t)
1006 {
1007   environmentTable_elements (t, key, value)
1008     {
1009       sRef root = sRef_getRootBase (key);
1010
1011       if (sRef_isAliasCheckedGlobal (root))
1012         {
1013           sRefSet_realElements (value, sr)
1014             {
1015               root = sRef_getRootBase (sr);
1016
1017               if (((sRef_isAliasCheckedGlobal (root)
1018                     && !(sRef_similar (root, key)))
1019                    || sRef_isAnyParam (root))
1020                   && !sRef_isExposed (root))
1021                 {
1022                   if (sRef_isAliasCheckedGlobal (key))
1023                     {
1024                       if (!(sRef_isShared (key)
1025                             && sRef_isShared (root)))
1026                         {
1027                           voptgenerror
1028                             (FLG_GLOBENVIRONMENT,
1029                              message
1030                              ("Function returns with %q variable %q environmenting %q %q",
1031                               cstring_makeLiteral (sRef_isRealGlobal (key)
1032                                                    ? "global" : "file static"),
1033                               sRef_unparse (key),
1034                               cstring_makeLiteral (sRef_isAnyParam (root)
1035                                                    ? "parameter" : "global"),
1036                               sRef_unparse (sr)),
1037                              g_currentloc);
1038                         }
1039                     }
1040
1041                 }
1042             } end_sRefSet_realElements;
1043         }
1044       else if (sRef_isAnyParam (key) || sRef_isAnyParam (root))
1045         {
1046           sRefSet_realElements (value, sr)
1047             {
1048               root = sRef_getRootBase (sr);
1049
1050               if (sRef_isAliasCheckedGlobal (root)
1051                   && !sRef_isExposed (root)
1052                   && !sRef_isDead (key)
1053                   && !sRef_isShared (root))
1054                 {
1055                   voptgenerror
1056                     (FLG_GLOBENVIRONMENT,
1057                      message ("Function returns with parameter %q environmenting %q %q",
1058                               sRef_unparse (key),
1059                               cstring_makeLiteral (sRef_isRealGlobal (root)
1060                                                    ? "global" : "file static"),
1061                               sRef_unparse (sr)),
1062                      g_currentloc);
1063                 }
1064             } end_sRefSet_realElements;
1065         }
1066       else
1067         {
1068           ;
1069         }
1070     } end_environmentTable_elements;
1071 }
1072
1073
1074