[splint.git] / src / rangeTable.c

/*
** LCLint - annotation-assisted static program checker
** Copyright (C) 1994-2000 University of Virginia,
**         Massachusetts Institute of Technology
**
** This program is free software; you can redistribute it and/or modify it
** under the terms of the GNU General Public License as published by the
** Free Software Foundation; either version 2 of the License, or (at your
** option) any later version.
** 
** This program is distributed in the hope that it will be useful, but
** WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** General Public License for more details.
** 
** The GNU General Public License is available from http://www.gnu.org/ or
** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
** MA 02111-1307, USA.
**
** For information on lclint: lclint-request@cs.virginia.edu
** To report a bug: lclint-bug@cs.virginia.edu
** For more information: http://lclint.cs.virginia.edu
*/
/*
** rangeTable.c
*/

# include "lclintMacros.nf"
# include "basic.h"

/*@constant int ATINVALID; @*/
# define ATINVALID -1

static sRefSet
  rangeTable_canRangeAux (rangeTable p_s, sRef p_sr, int p_lim) /*@*/ ;
static sRefSet
  rangeTable_aliasedByLimit (rangeTable p_s, sRef p_sr, int p_lim) /*@*/ ;
static sRefSet 
  rangeTable_aliasedByAux (rangeTable p_s, sRef p_sr, int p_lim) /*@*/ ;

rangeTable
rangeTable_new ()
{
  return (rangeTable_undefined);
}

static /*@only@*/ /*@notnull@*/ rangeTable
rangeTable_newEmpty (void)
{
  rangeTable s = (rangeTable) dmalloc (sizeof (*s));
  
  s->nelements = 0;
  s->nspace = rangeTableBASESIZE;
  s->keys     = (sRef *) dmalloc (sizeof (*s->keys) * rangeTableBASESIZE);
  s->values   = (sRefSet *) dmalloc (sizeof (*s->values) * rangeTableBASESIZE);
  s->ranges    = (sRefSet *) dmalloc (sizeof (*s->ranges) * rangeTableBASESIZE);
  return (s);
}

static void
rangeTable_grow (/*@notnull@*/ rangeTable s)
{
  int i;
  o_sRefSet *oldvalues = s->values;
  sRef    *oldkeys = s->keys;
  RangeAt *oldranges = s->ranges;
  
  s->nspace += rangeTableBASESIZE; 

  s->values = (sRefSet *) dmalloc (sizeof (*s->values)
				   * (s->nelements + s->nspace));
  s->keys = (sRef *) dmalloc (sizeof (*s->keys) * (s->nelements + rangeTableBASESIZE));

  s->ranges = (sRef *) dmalloc (sizeof (*s->ranges) * (s->nelements + rangeTableBASESIZE));

  
  if (s->keys == (sRef *) 0 || s->values == (sRefSet *)0 || s->ranges = (range_At*) 0 )
    {
      llfatalerror (cstring_makeLiteral ("rangeTable_grow: out of memory!"));
    }

  for (i = 0; i < s->nelements; i++)
    {
      s->values[i] = oldvalues[i];
      s->keys[i] = oldkeys[i];
      s->ranges[i] = oldranges[i];
    }
  
  sfree (oldvalues);
  sfree (oldkeys);
}

static int rangeTable_lookupRefs (/*@notnull@*/ rangeTable s, sRef sr)
{
  int i;

  
  for (i = 0; i < rangeTable_size (s); i++)
    {
      if (sRef_same (sr, s->keys[i])) 
	{
	  return i;
	}
    }

  return ATINVALID;
}

/*
** sr rangees al (and anything al rangees!)
*/

rangeTable
rangeTable_addMustRange (/*@returned@*/ rangeTable s,
			 /*@exposed@*/ sRef sr,
			 sRef al)
{
  int ind;
  sRefSet ss;
  
  llassert (NORANGE (sr, al));

  if (rangeTable_isUndefined (s))
    {
      s = rangeTable_newEmpty ();
      ind = ATINVALID;
    }
  else
    {
      ind = rangeTable_lookupRefs (s, sr);
    }
  
  ss = rangeTable_canRange (s, al); 
  
  
  if (ind == ATINVALID)
    {
      if (s->nspace <= 0) {
	rangeTable_grow (s);
      }

      s->nspace--;
      s->keys[s->nelements] = sr;
      s->values[s->nelements] = sRefSet_single (al); 
      ind = s->nelements;
      s->nelements++;      
    }
  else
    {
      s->values[ind] = sRefSet_insert (s->values[ind], al); 
    }
  
  s->values[ind] = sRefSet_unionExcept (s->values[ind], ss, s->keys[ind]); 

  sRefSet_free (ss);
  return s;
}

static rangeTable 
  rangeTable_addSet (/*@returned@*/ rangeTable s,
		     /*@exposed@*/ sRef key, /*@only@*/ sRefSet value)
{
  if (!sRefSet_isEmpty (value))
    {
      if (rangeTable_isUndefined (s))
	{
	  s = rangeTable_newEmpty ();
	}
      else
	{
	  if (s->nspace <= 0)
	    {
	      rangeTable_grow (s);
	    }
	}

      s->nspace--;
      s->keys[s->nelements] = key;
      s->values[s->nelements] = value;
      s->nelements++;      
    }
  else
    {
      sRefSet_free (value);
    }

  return s;
}

/*
** When rangees are cleared:
**
**    o remove all entries for sr
**    o replace all rangees for things which range sr with sr's rangees
**
** Clear rangees for sr; if sr is a direct param reference, clear its rangees too.
*/

static void rangeTable_clearRangeesAux (/*@notnull@*/ rangeTable p_s, sRef p_sr)
   /*@modifies p_s@*/ ;

void rangeTable_clearRangees (rangeTable s, sRef sr)
{
  if (rangeTable_isUndefined (s))
    {
      return;
    }
  else
    {
      sRef rb = sRef_getRootBase (sr);

            
      if (!sRef_isCvar (sr) && sRef_isLocalVar (rb))
	{
	  int ind = rangeTable_lookupRefs (s, rb);
	  
	  if (ind != ATINVALID)
	    {
	      sRefSet al = s->values[ind];
	      
	      	      
	      sRefSet_realElements (al, el)
		{
		  		  
		  if (sRef_isParam (el))
		    {
		      if (sRef_sameName (el, rb))
			{
			  sRef fb = sRef_fixBase (sr, el); 

			  rangeTable_clearRangeesAux (s, fb); 
			}
		    }
		} end_sRefSet_realElements ;
	    }
	}
      
      rangeTable_clearRangeesAux (s, sr); 
    }  
}

static
void rangeTable_clearRangeesAux (/*@notnull@*/ rangeTable s, sRef sr)
{
  int i;
  
  for (i = 0; i < s->nelements; i++)
    {
      sRef key = s->keys[i];
      
      if (sRef_includedBy (key, sr))
	{
	  sRefSet_clear (s->values[i]);
	}
      else
	{
	  (void) sRefSet_deleteBase (s->values[i], sr);   
	}
    }
}

/*
** returns set of all sRefs that must range sr (but are different from sr)
*/

static /*@only@*/ sRefSet rangeTable_rangeedByAux (rangeTable s, sRef sr, int lim)
{
  static bool hadWarning = FALSE;
  sRefSet res = sRefSet_undefined;
  int i;

  llassert (!sRef_isConj (sr));
  
  
  if (rangeTable_isUndefined (s) || lim >= RANGESEARCHLIMIT)
    {
      if (lim >= RANGESEARCHLIMIT && !hadWarning)
	{
	  llquietbug
	    (message ("Range search limit exceeded, checking %q. "
		      "This either means there is a variable with at least "
		      "%d indirections, or there is a bug in LCLint.",
		      sRef_unparse (sr),
		      RANGESEARCHLIMIT));
	  
	  hadWarning = TRUE;
	}

      return sRefSet_undefined;
    }
  else
    {
      sRefSet abl;

      if (sRef_isPointer (sr))
	{
	  abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
	  res = sRefSet_addIndirection (abl);
	}
      else if (sRef_isAddress (sr))
	{
	  abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
	  res = sRefSet_removeIndirection (abl);
	}
      else if (sRef_isField (sr))
	{
	  abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
	  res = sRefSet_accessField (abl, sRef_getField (sr));
	}
      else if (sRef_isArrayFetch (sr))
	{
	  abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);

	  if (sRef_isIndexKnown (sr))
	    {
	      int idx = sRef_getIndex (sr);
	      
	      res = sRefSet_fetchKnown (abl, idx);
	    }
	  else
	    {
	      res = sRefSet_fetchUnknown (abl);
	    }
	}
      else
	{
	  abl = sRefSet_undefined;
	}

      sRefSet_free (abl);
    }

  for (i = 0; i < s->nelements; i++)
    {
      sRef elem = s->keys[i];
      
      if (!sRef_same (sr, elem)) /* was sameName */
	{
	  	  
	  sRefSet_realElements (s->values[i], current)
	    {
	      	      
	      if (sRef_similar (sr, current))
		{
		  		  		  res = sRefSet_insert (res, sRef_fixOuterRef (elem));
		  /*@innerbreak@*/ break;
		}
	    } end_sRefSet_realElements;
	} 
    }
  
    return res;
}

static /*@only@*/ sRefSet rangeTable_rangeedByLimit (rangeTable s, sRef sr, int lim)
{
  sRefSet res;
  
  
  if (sRef_isConj (sr))
    {
      res = sRefSet_unionFree (rangeTable_rangeedByLimit (s, sRef_getConjA (sr), lim),
			       rangeTable_rangeedByLimit (s, sRef_getConjB (sr), lim));
    }
  else
    {
      res = rangeTable_rangeedByAux (s, sr, lim + 1);
    }
  
    return res;
}

/*@only@*/ sRefSet rangeTable_rangeedBy (rangeTable s, sRef sr)
{ 
  if (sRef_isConj (sr))
    {
      return (sRefSet_unionFree (rangeTable_rangeedBy (s, sRef_getConjA (sr)),
				 rangeTable_rangeedBy (s, sRef_getConjB (sr))));
    }

  return (rangeTable_rangeedByAux (s, sr, 0));
}

/*@only@*/ sRefSet rangeTable_canRange (rangeTable s, sRef sr)
{
  sRefSet res;

    
  if (sRef_isConj (sr))
    {
      res = sRefSet_unionFree (rangeTable_canRange (s, sRef_getConjA (sr)),
			       rangeTable_canRange (s, sRef_getConjB (sr)));
    }
  else
    {
      res = rangeTable_canRangeAux (s, sr, 0);
          }

    return res;
}

/*
** need to limit the depth of rangeing searches 
*/

static /*@only@*/ sRefSet rangeTable_canRangeLimit (rangeTable s, sRef sr, int lim)
{
  sRefSet res;
  
  if (sRef_isConj (sr))
    {
      sRefSet a = rangeTable_canRangeLimit (s, sRef_getConjA (sr), lim);
      sRefSet b = rangeTable_canRangeLimit (s, sRef_getConjB (sr), lim);

      res = sRefSet_unionFree (a, b);
    }
  else
    {
      res = rangeTable_canRangeAux (s, sr, lim + 1);
    }
  
  return res;
}

static /*@only@*/ sRefSet 
  rangeTable_canRangeAux (rangeTable s, sRef sr, int lim)
{
  static bool hadWarning = FALSE;
  llassert (!sRef_isConj (sr));
  
  
  if (rangeTable_isUndefined (s) || lim >= RANGESEARCHLIMIT)
    {
      if (lim >= RANGESEARCHLIMIT && !hadWarning)
	{
	  llquietbug
	    (message ("Range search limit exceeded, checking %q. "
		      "This either means there is a variable with at least "
		      "%d indirections, or there is a bug in LCLint.",
		      sRef_unparse (sr),
		      RANGESEARCHLIMIT));
	  
	  hadWarning = TRUE;
	}

      return sRefSet_undefined;
    }
  else
    {
      int ind = rangeTable_lookupRefs (s, sr);

      if (sRef_isPointer (sr) || sRef_isAddress (sr) || sRef_isField (sr)
	  || sRef_isArrayFetch (sr))
	{
	  sRef base = sRef_getBase (sr);
	  sRefSet tmp = rangeTable_canRangeLimit (s, base, lim);
	  sRefSet ret;

	  if (sRef_isPointer (sr))
	    {
	      ret = sRefSet_addIndirection (tmp); 
	    }
	  else if (sRef_isAddress (sr))
	    {
	      ret = sRefSet_removeIndirection (tmp);
	    }
	  else if (sRef_isField (sr))
	    {
	      ret = sRefSet_accessField (tmp, sRef_getField (sr));
	    }
	  else if (sRef_isArrayFetch (sr))
	    {
	      if (sRef_isIndexKnown (sr))
		{
		  ret = sRefSet_fetchKnown (tmp, sRef_getIndex (sr));
		}
	      else
		{
		  ret = sRefSet_fetchUnknown (tmp);
		}
	    }
	  else
	    {
	      BADBRANCH;
	    }

	  if (ind != ATINVALID)
	    {
	      ret = sRefSet_union (ret, s->values[ind]);
	    }

	  sRefSet_free (tmp);
	  	  return ret;
	}
      
      if (ind == ATINVALID) return sRefSet_undefined;      
      
      return sRefSet_newCopy (s->values[ind]);
    }
}

rangeTable rangeTable_copy (rangeTable s)
{
  if (rangeTable_isEmpty (s))
    {
      return rangeTable_undefined;
    }
  else
    {
      rangeTable t = (rangeTable) dmalloc (sizeof (*s));
      int i;

      t->nelements = s->nelements;
      t->nspace = 0;
      t->keys = (sRef *) dmalloc (sizeof (*s->keys) * s->nelements);
      t->values = (sRefSet *) dmalloc (sizeof (*s->values) * t->nelements);
        
      for (i = 0; i < s->nelements; i++)
	{
	  t->keys[i] = s->keys[i];
	  t->values[i] = sRefSet_newCopy (s->values[i]);
	}

      return t;
    }
}

static void
rangeTable_levelPrune (rangeTable s, int lexlevel)
{
  
  
  if (rangeTable_isEmpty (s))
    {
      return;
    }
  else
    {
      int i;
      int backcount = s->nelements - 1;
      
      for (i = 0; i <= backcount; i++)
	{
	  sRef key = s->keys[i];
	  
	  if (sRef_lexLevel (key) > lexlevel)
	    {
	      int j;
	      for (j = backcount; j > i; j--)
		{
		  backcount--;
		  s->nelements--;
		  s->nspace++;
		  
		  if (sRef_lexLevel (s->keys[j]) <= lexlevel)
		    {
		      s->keys[i] = s->keys[j];
		      s->values[i] = s->values[j];
		      sRefSet_levelPrune (s->values[i], lexlevel);
		      /*@innerbreak@*/ break;
		    }
		}
	      if (backcount == i)
		s->nelements--;
	    }
	  else
	    {
	      sRefSet_levelPrune (s->values[i], lexlevel);
	    }
	}
    }
}

/*
** levelUnionSeq
**
**    like level union, but know that t2 was executed after t1.  So if
**    t1 has x -> { a, b } and t2 has x -> { a }, then result has x -> { a }.
**
** NOTE: t2 is "only".
*/

rangeTable rangeTable_levelUnionSeq (/*@returned@*/ rangeTable t1, 
				     /*@only@*/ rangeTable t2, int level)
{
  if (rangeTable_isUndefined (t2))
    {
      return t1;
    }

  if (rangeTable_isUndefined (t1))
    {
      t1 = rangeTable_newEmpty ();
    }
  else
    {
      rangeTable_levelPrune (t1, level);
    }

  rangeTable_elements (t2, key, value)
    {
      if (sRef_lexLevel (key) <= level)
	{
	  int ind = rangeTable_lookupRefs (t1, key);

	  sRefSet_levelPrune (value, level);
	      
	  if (ind == ATINVALID)
	    {
	      /* okay, t2 is killed */
	      /*@-exposetrans@*/ /*@-dependenttrans@*/ 
	      t1 = rangeTable_addSet (t1, key, value);
	      /*@=exposetrans@*/ /*@=dependenttrans@*/ 
	    }
	  else
	    {
	      sRefSet_free (t1->values[ind]);

	      /*@-dependenttrans@*/ /* okay, t2 is killed */
	      t1->values[ind] = value;
	      /*@=dependenttrans@*/
	    } 
	}
      else
	{
	  /*@-exposetrans@*/ /*@-dependenttrans@*/ 
	  sRefSet_free (value);
	  /*@=exposetrans@*/ /*@=dependenttrans@*/ 
	}

    } end_rangeTable_elements;
  
  sfree (t2->keys);
  sfree (t2->values);
  sfree (t2);

    return t1;
}

rangeTable 
rangeTable_levelUnion (/*@returned@*/ rangeTable t1, rangeTable t2, int level)
{
  if (rangeTable_isUndefined (t1))
    {
      if (rangeTable_isUndefined (t2)) 
	{
	  return t1;
	}
      else
	{
	  t1 = rangeTable_newEmpty ();
	}
    }
  else
    {
      rangeTable_levelPrune (t1, level);
    }

  rangeTable_elements (t2, key, cvalue)
    {
      sRefSet value = sRefSet_newCopy (cvalue);

      if (sRef_lexLevel (key) <= level)
	{
	  sRefSet_levelPrune (value, level);

	  if (sRefSet_size (value) > 0)
	    {
	      int ind = rangeTable_lookupRefs (t1, key);
	      
	      if (ind == ATINVALID)
		{
		  t1 = rangeTable_addSet (t1, key, value);
		}
	      else
		{
		  t1->values[ind] = sRefSet_union (t1->values[ind], value);
		  sRefSet_free (value);
		}
	    }
	  else
	    {
	      sRefSet_free (value); 
	    }
	}
      else
	{
	  sRefSet_free (value); 
	}
    } end_rangeTable_elements;

    return t1;
}

rangeTable rangeTable_levelUnionNew (rangeTable t1, rangeTable t2, int level)
{
  rangeTable ret = rangeTable_levelUnion (rangeTable_copy (t1), t2, level);

  return ret;
}

/*@only@*/ cstring
rangeTable_unparse (rangeTable s)
{
   cstring st = cstring_undefined;

   if (rangeTable_isUndefined (s)) return (cstring_makeLiteral ("<NULL>"));

   rangeTable_elements (s, key, value)
     {
       st = message ("%q\t%q -> %q\n", st, sRef_unparse (key), 
		     sRefSet_unparse (value));
     } end_rangeTable_elements;

   return st;
}

/*
** bogus!
*/

void
rangeTable_fixSrefs (rangeTable s)
{
  int i;

  if (rangeTable_isUndefined (s)) return;

  for (i = 0; i < s->nelements; i++)
    {
      sRef old = s->keys[i];

      if (sRef_isLocalVar (old))
	{
	  s->keys[i] = uentry_getSref (sRef_getUentry (old));
	}

      sRefSet_fixSrefs (s->values[i]);
    }
}

void
rangeTable_free (/*@only@*/ rangeTable s)
{
  int i;
  
  if (rangeTable_isUndefined (s)) return;
  
  for (i = 0; i < s->nelements; i++)
    {
      sRefSet_free (s->values[i]); 
    }
  
  sfree (s->values);
  sfree (s->keys);
  sfree (s);
}

void 
rangeTable_checkGlobs (rangeTable t)
{
  rangeTable_elements (t, key, value)
    {
      sRef root = sRef_getRootBase (key);

      if (sRef_isRangeCheckedGlobal (root))
	{
	  sRefSet_realElements (value, sr)
	    {
	      root = sRef_getRootBase (sr);

	      if (((sRef_isRangeCheckedGlobal (root) 
		    && !(sRef_similar (root, key)))
		   || sRef_isAnyParam (root))
		  && !sRef_isExposed (root))
		{
		  if (sRef_isRangeCheckedGlobal (key))
		    {
		      if (!(sRef_isShared (key) 
			    && sRef_isShared (root)))
			{
			  voptgenerror 
			    (FLG_GLOBRANGE,
			     message 
			     ("Function returns with %q variable %q rangeing %q %q",
			      cstring_makeLiteral (sRef_isRealGlobal (key) 
						   ? "global" : "file static"),
			      sRef_unparse (key),
			      cstring_makeLiteral (sRef_isAnyParam (root) 
						   ? "parameter" : "global"),
			      sRef_unparse (sr)),
			     g_currentloc);
			}
		    }

		}
	    } end_sRefSet_realElements;
	}
      else if (sRef_isAnyParam (key) || sRef_isAnyParam (root))
	{
	  sRefSet_realElements (value, sr)
	    {
	      root = sRef_getRootBase (sr);
	      
	      if (sRef_isRangeCheckedGlobal (root) 
		  && !sRef_isExposed (root)
		  && !sRef_isDead (key)
		  && !sRef_isShared (root))
		{
		  voptgenerror 
		    (FLG_GLOBRANGE,
		     message ("Function returns with parameter %q rangeing %q %q",
			      sRef_unparse (key),
			      cstring_makeLiteral (sRef_isRealGlobal (root) 
						   ? "global" : "file static"),
			      sRef_unparse (sr)),
		     g_currentloc);
		}
	    } end_sRefSet_realElements;
	}
      else
	{
	  ;
	}
    } end_rangeTable_elements;
}
Commit	Line	Data
d0e5b01f	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	** rangeTable.c
	26	*/
	27
	28	# include "lclintMacros.nf"
	29	# include "basic.h"
	30
	31	/@constant int ATINVALID; @/
	32	# define ATINVALID -1
	33
	34	static sRefSet
	35	rangeTable_canRangeAux (rangeTable p_s, sRef p_sr, int p_lim) /@/ ;
	36	static sRefSet
	37	rangeTable_aliasedByLimit (rangeTable p_s, sRef p_sr, int p_lim) /@/ ;
	38	static sRefSet
	39	rangeTable_aliasedByAux (rangeTable p_s, sRef p_sr, int p_lim) /@/ ;
	40
	41	rangeTable
	42	rangeTable_new ()
	43	{
	44	return (rangeTable_undefined);
	45	}
	46
	47	static /@only@/ /@notnull@/ rangeTable
	48	rangeTable_newEmpty (void)
	49	{
	50	rangeTable s = (rangeTable) dmalloc (sizeof (*s));
	51
	52	s->nelements = 0;
	53	s->nspace = rangeTableBASESIZE;
	54	s->keys = (sRef ) dmalloc (sizeof (s->keys) * rangeTableBASESIZE);
	55	s->values = (sRefSet ) dmalloc (sizeof (s->values) * rangeTableBASESIZE);
	56	s->ranges = (sRefSet ) dmalloc (sizeof (s->ranges) * rangeTableBASESIZE);
	57	return (s);
	58	}
	59
	60	static void
	61	rangeTable_grow (/@notnull@/ rangeTable s)
	62	{
	63	int i;
	64	o_sRefSet *oldvalues = s->values;
65	sRef *oldkeys = s->keys;
66	RangeAt *oldranges = s->ranges;
67
68	s->nspace += rangeTableBASESIZE;
69
70	s->values = (sRefSet ) dmalloc (sizeof (s->values)
71	* (s->nelements + s->nspace));
72	s->keys = (sRef ) dmalloc (sizeof (s->keys) * (s->nelements + rangeTableBASESIZE));
73
74	s->ranges = (sRef ) dmalloc (sizeof (s->ranges) * (s->nelements + rangeTableBASESIZE));
75
76
77	if (s->keys == (sRef ) 0 \|\| s->values == (sRefSet )0 \|\| s->ranges = (range_At*) 0 )
78	{
79	llfatalerror (cstring_makeLiteral ("rangeTable_grow: out of memory!"));
80	}
81
82	for (i = 0; i < s->nelements; i++)
83	{
84	s->values[i] = oldvalues[i];
85	s->keys[i] = oldkeys[i];
86	s->ranges[i] = oldranges[i];
87	}
88
89	sfree (oldvalues);
90	sfree (oldkeys);
91	}
92
93	static int rangeTable_lookupRefs (/@notnull@/ rangeTable s, sRef sr)
94	{
95	int i;
96
97
98	for (i = 0; i < rangeTable_size (s); i++)
99	{
100	if (sRef_same (sr, s->keys[i]))
101	{
102	return i;
103	}
104	}
105
106	return ATINVALID;
107	}
108
109	/*
110	** sr rangees al (and anything al rangees!)
111	*/
112
113	rangeTable
114	rangeTable_addMustRange (/@returned@/ rangeTable s,
115	/@exposed@/ sRef sr,
116	sRef al)
117	{
118	int ind;
119	sRefSet ss;
120
121	llassert (NORANGE (sr, al));
122
123	if (rangeTable_isUndefined (s))
124	{
125	s = rangeTable_newEmpty ();
126	ind = ATINVALID;
127	}
128	else
129	{
130	ind = rangeTable_lookupRefs (s, sr);
131	}
132
133	ss = rangeTable_canRange (s, al);
134
135
136	if (ind == ATINVALID)
137	{
138	if (s->nspace <= 0) {
139	rangeTable_grow (s);
140	}
141
142	s->nspace--;
143	s->keys[s->nelements] = sr;
144	s->values[s->nelements] = sRefSet_single (al);
145	ind = s->nelements;
146	s->nelements++;
147	}
148	else
149	{
150	s->values[ind] = sRefSet_insert (s->values[ind], al);
151	}
152
153	s->values[ind] = sRefSet_unionExcept (s->values[ind], ss, s->keys[ind]);
154
155	sRefSet_free (ss);
156	return s;
157	}
158
159	static rangeTable
160	rangeTable_addSet (/@returned@/ rangeTable s,
161	/@exposed@/ sRef key, /@only@/ sRefSet value)
162	{
163	if (!sRefSet_isEmpty (value))
164	{
165	if (rangeTable_isUndefined (s))
166	{
167	s = rangeTable_newEmpty ();
168	}
169	else
170	{
171	if (s->nspace <= 0)
172	{
173	rangeTable_grow (s);
174	}
175	}
176
177	s->nspace--;
178	s->keys[s->nelements] = key;
179	s->values[s->nelements] = value;
180	s->nelements++;
181	}
182	else
183	{
184	sRefSet_free (value);
185	}
186
187	return s;
188	}
189
190	/*
191	** When rangees are cleared:
192	**
193	** o remove all entries for sr
194	** o replace all rangees for things which range sr with sr's rangees
195	**
196	** Clear rangees for sr; if sr is a direct param reference, clear its rangees too.
197	*/
198
199	static void rangeTable_clearRangeesAux (/@notnull@/ rangeTable p_s, sRef p_sr)
200	/@modifies p_s@/ ;
201
202	void rangeTable_clearRangees (rangeTable s, sRef sr)
203	{
204	if (rangeTable_isUndefined (s))
205	{
206	return;
207	}
208	else
209	{
210	sRef rb = sRef_getRootBase (sr);
211
212
213	if (!sRef_isCvar (sr) && sRef_isLocalVar (rb))
214	{
215	int ind = rangeTable_lookupRefs (s, rb);
216
217	if (ind != ATINVALID)
218	{
219	sRefSet al = s->values[ind];
220
221
222	sRefSet_realElements (al, el)
223	{
224
225	if (sRef_isParam (el))
226	{
227	if (sRef_sameName (el, rb))
228	{
229	sRef fb = sRef_fixBase (sr, el);
230
231	rangeTable_clearRangeesAux (s, fb);
232	}
233	}
234	} end_sRefSet_realElements ;
235	}
236	}
237
238	rangeTable_clearRangeesAux (s, sr);
239	}
240	}
241
242	static
243	void rangeTable_clearRangeesAux (/@notnull@/ rangeTable s, sRef sr)
244	{
245	int i;
246
247	for (i = 0; i < s->nelements; i++)
248	{
249	sRef key = s->keys[i];
250
251	if (sRef_includedBy (key, sr))
252	{
253	sRefSet_clear (s->values[i]);
254	}
255	else
256	{
257	(void) sRefSet_deleteBase (s->values[i], sr);
258	}
259	}
260	}
261
262	/*
263	** returns set of all sRefs that must range sr (but are different from sr)
264	*/
265
266	static /@only@/ sRefSet rangeTable_rangeedByAux (rangeTable s, sRef sr, int lim)
267	{
268	static bool hadWarning = FALSE;
269	sRefSet res = sRefSet_undefined;
270	int i;
271
272	llassert (!sRef_isConj (sr));
273
274
275	if (rangeTable_isUndefined (s) \|\| lim >= RANGESEARCHLIMIT)
276	{
277	if (lim >= RANGESEARCHLIMIT && !hadWarning)
278	{
279	llquietbug
280	(message ("Range search limit exceeded, checking %q. "
281	"This either means there is a variable with at least "
282	"%d indirections, or there is a bug in LCLint.",
283	sRef_unparse (sr),
284	RANGESEARCHLIMIT));
285
286	hadWarning = TRUE;
287	}
288
289	return sRefSet_undefined;
290	}
291	else
292	{
293	sRefSet abl;
294
295	if (sRef_isPointer (sr))
296	{
297	abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
298	res = sRefSet_addIndirection (abl);
299	}
300	else if (sRef_isAddress (sr))
301	{
302	abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
303	res = sRefSet_removeIndirection (abl);
304	}
305	else if (sRef_isField (sr))
306	{
307	abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
308	res = sRefSet_accessField (abl, sRef_getField (sr));
309	}
310	else if (sRef_isArrayFetch (sr))
311	{
312	abl = rangeTable_rangeedByLimit (s, sRef_getBase (sr), lim);
313
314	if (sRef_isIndexKnown (sr))
315	{
316	int idx = sRef_getIndex (sr);
317
318	res = sRefSet_fetchKnown (abl, idx);
319	}
320	else
321	{
322	res = sRefSet_fetchUnknown (abl);
323	}
324	}
325	else
326	{
327	abl = sRefSet_undefined;
328	}
329
330	sRefSet_free (abl);
331	}
332
333	for (i = 0; i < s->nelements; i++)
334	{
335	sRef elem = s->keys[i];
336
337	if (!sRef_same (sr, elem)) /* was sameName */
338	{
339
340	sRefSet_realElements (s->values[i], current)
341	{
342
343	if (sRef_similar (sr, current))
344	{
345	res = sRefSet_insert (res, sRef_fixOuterRef (elem));
346	/@innerbreak@/ break;
347	}
348	} end_sRefSet_realElements;
349	}
350	}
351
352	return res;
353	}
354
355	static /@only@/ sRefSet rangeTable_rangeedByLimit (rangeTable s, sRef sr, int lim)
356	{
357	sRefSet res;
358
359
360	if (sRef_isConj (sr))
361	{
362	res = sRefSet_unionFree (rangeTable_rangeedByLimit (s, sRef_getConjA (sr), lim),
363	rangeTable_rangeedByLimit (s, sRef_getConjB (sr), lim));
364	}
365	else
366	{
367	res = rangeTable_rangeedByAux (s, sr, lim + 1);
368	}
369
370	return res;
371	}
372
373	/@only@/ sRefSet rangeTable_rangeedBy (rangeTable s, sRef sr)
374	{
375	if (sRef_isConj (sr))
376	{
377	return (sRefSet_unionFree (rangeTable_rangeedBy (s, sRef_getConjA (sr)),
378	rangeTable_rangeedBy (s, sRef_getConjB (sr))));
379	}
380
381	return (rangeTable_rangeedByAux (s, sr, 0));
382	}
383
384	/@only@/ sRefSet rangeTable_canRange (rangeTable s, sRef sr)
385	{
386	sRefSet res;
387
388
389	if (sRef_isConj (sr))
390	{
391	res = sRefSet_unionFree (rangeTable_canRange (s, sRef_getConjA (sr)),
392	rangeTable_canRange (s, sRef_getConjB (sr)));
393	}
394	else
395	{
396	res = rangeTable_canRangeAux (s, sr, 0);
397	}
398
399	return res;
400	}
401
402	/*
403	** need to limit the depth of rangeing searches
404	*/
405
406	static /@only@/ sRefSet rangeTable_canRangeLimit (rangeTable s, sRef sr, int lim)
407	{
408	sRefSet res;
409
410	if (sRef_isConj (sr))
411	{
412	sRefSet a = rangeTable_canRangeLimit (s, sRef_getConjA (sr), lim);
413	sRefSet b = rangeTable_canRangeLimit (s, sRef_getConjB (sr), lim);
414
415	res = sRefSet_unionFree (a, b);
416	}
417	else
418	{
419	res = rangeTable_canRangeAux (s, sr, lim + 1);
420	}
421
422	return res;
423	}
424
425	static /@only@/ sRefSet
426	rangeTable_canRangeAux (rangeTable s, sRef sr, int lim)
427	{
428	static bool hadWarning = FALSE;
429	llassert (!sRef_isConj (sr));
430
431
432	if (rangeTable_isUndefined (s) \|\| lim >= RANGESEARCHLIMIT)
433	{
434	if (lim >= RANGESEARCHLIMIT && !hadWarning)
435	{
436	llquietbug
437	(message ("Range search limit exceeded, checking %q. "
438	"This either means there is a variable with at least "
439	"%d indirections, or there is a bug in LCLint.",
440	sRef_unparse (sr),
441	RANGESEARCHLIMIT));
442
443	hadWarning = TRUE;
444	}
445
446	return sRefSet_undefined;
447	}
448	else
449	{
450	int ind = rangeTable_lookupRefs (s, sr);
451
452	if (sRef_isPointer (sr) \|\| sRef_isAddress (sr) \|\| sRef_isField (sr)
453	\|\| sRef_isArrayFetch (sr))
454	{
455	sRef base = sRef_getBase (sr);
456	sRefSet tmp = rangeTable_canRangeLimit (s, base, lim);
457	sRefSet ret;
458
459	if (sRef_isPointer (sr))
460	{
461	ret = sRefSet_addIndirection (tmp);
462	}
463	else if (sRef_isAddress (sr))
464	{
465	ret = sRefSet_removeIndirection (tmp);
466	}
467	else if (sRef_isField (sr))
468	{
469	ret = sRefSet_accessField (tmp, sRef_getField (sr));
470	}
471	else if (sRef_isArrayFetch (sr))
472	{
473	if (sRef_isIndexKnown (sr))
474	{
475	ret = sRefSet_fetchKnown (tmp, sRef_getIndex (sr));
476	}
477	else
478	{
479	ret = sRefSet_fetchUnknown (tmp);
480	}
481	}
482	else
483	{
484	BADBRANCH;
485	}
486
487	if (ind != ATINVALID)
488	{
489	ret = sRefSet_union (ret, s->values[ind]);
490	}
491
492	sRefSet_free (tmp);
493	return ret;
494	}
495
496	if (ind == ATINVALID) return sRefSet_undefined;
497
498	return sRefSet_newCopy (s->values[ind]);
499	}
500	}
501
502	rangeTable rangeTable_copy (rangeTable s)
503	{
504	if (rangeTable_isEmpty (s))
505	{
506	return rangeTable_undefined;
507	}
508	else
509	{
510	rangeTable t = (rangeTable) dmalloc (sizeof (*s));
511	int i;
512
513	t->nelements = s->nelements;
514	t->nspace = 0;
515	t->keys = (sRef ) dmalloc (sizeof (s->keys) * s->nelements);
516	t->values = (sRefSet ) dmalloc (sizeof (s->values) * t->nelements);
517
518	for (i = 0; i < s->nelements; i++)
519	{
520	t->keys[i] = s->keys[i];
521	t->values[i] = sRefSet_newCopy (s->values[i]);
522	}
523
524	return t;
525	}
526	}
527
528	static void
529	rangeTable_levelPrune (rangeTable s, int lexlevel)
530	{
531
532
533	if (rangeTable_isEmpty (s))
534	{
535	return;
536	}
537	else
538	{
539	int i;
540	int backcount = s->nelements - 1;
541
542	for (i = 0; i <= backcount; i++)
543	{
544	sRef key = s->keys[i];
545
546	if (sRef_lexLevel (key) > lexlevel)
547	{
548	int j;
549	for (j = backcount; j > i; j--)
550	{
551	backcount--;
552	s->nelements--;
553	s->nspace++;
554
555	if (sRef_lexLevel (s->keys[j]) <= lexlevel)
556	{
557	s->keys[i] = s->keys[j];
558	s->values[i] = s->values[j];
559	sRefSet_levelPrune (s->values[i], lexlevel);
560	/@innerbreak@/ break;
561	}
562	}
563	if (backcount == i)
564	s->nelements--;
565	}
566	else
567	{
568	sRefSet_levelPrune (s->values[i], lexlevel);
569	}
570	}
571	}
572	}
573
574	/*
575	** levelUnionSeq
576	**
577	** like level union, but know that t2 was executed after t1. So if
578	** t1 has x -> { a, b } and t2 has x -> { a }, then result has x -> { a }.
579	**
580	** NOTE: t2 is "only".
581	*/
582
583	rangeTable rangeTable_levelUnionSeq (/@returned@/ rangeTable t1,
584	/@only@/ rangeTable t2, int level)
585	{
586	if (rangeTable_isUndefined (t2))
587	{
588	return t1;
589	}
590
591	if (rangeTable_isUndefined (t1))
592	{
593	t1 = rangeTable_newEmpty ();
594	}
595	else
596	{
597	rangeTable_levelPrune (t1, level);
598	}
599
600	rangeTable_elements (t2, key, value)
601	{
602	if (sRef_lexLevel (key) <= level)
603	{
604	int ind = rangeTable_lookupRefs (t1, key);
605
606	sRefSet_levelPrune (value, level);
607
608	if (ind == ATINVALID)
609	{
610	/* okay, t2 is killed */
611	/@-exposetrans@/ /@-dependenttrans@/
612	t1 = rangeTable_addSet (t1, key, value);
613	/@=exposetrans@/ /@=dependenttrans@/
614	}
615	else
616	{
617	sRefSet_free (t1->values[ind]);
618
619	/@-dependenttrans@/ /* okay, t2 is killed */
620	t1->values[ind] = value;
621	/@=dependenttrans@/
622	}
623	}
624	else
625	{
626	/@-exposetrans@/ /@-dependenttrans@/
627	sRefSet_free (value);
628	/@=exposetrans@/ /@=dependenttrans@/
629	}
630
631	} end_rangeTable_elements;
632
633	sfree (t2->keys);
634	sfree (t2->values);
635	sfree (t2);
636
637	return t1;
638	}
639
640	rangeTable
641	rangeTable_levelUnion (/@returned@/ rangeTable t1, rangeTable t2, int level)
642	{
643	if (rangeTable_isUndefined (t1))
644	{
645	if (rangeTable_isUndefined (t2))
646	{
647	return t1;
648	}
649	else
650	{
651	t1 = rangeTable_newEmpty ();
652	}
653	}
654	else
655	{
656	rangeTable_levelPrune (t1, level);
657	}
658
659	rangeTable_elements (t2, key, cvalue)
660	{
661	sRefSet value = sRefSet_newCopy (cvalue);
662
663	if (sRef_lexLevel (key) <= level)
664	{
665	sRefSet_levelPrune (value, level);
666
667	if (sRefSet_size (value) > 0)
668	{
669	int ind = rangeTable_lookupRefs (t1, key);
670
671	if (ind == ATINVALID)
672	{
673	t1 = rangeTable_addSet (t1, key, value);
674	}
675	else
676	{
677	t1->values[ind] = sRefSet_union (t1->values[ind], value);
678	sRefSet_free (value);
679	}
680	}
681	else
682	{
683	sRefSet_free (value);
684	}
685	}
686	else
687	{
688	sRefSet_free (value);
689	}
690	} end_rangeTable_elements;
691
692	return t1;
693	}
694
695	rangeTable rangeTable_levelUnionNew (rangeTable t1, rangeTable t2, int level)
696	{
697	rangeTable ret = rangeTable_levelUnion (rangeTable_copy (t1), t2, level);
698
699	return ret;
700	}
701
702	/@only@/ cstring
703	rangeTable_unparse (rangeTable s)
704	{
705	cstring st = cstring_undefined;
706
707	if (rangeTable_isUndefined (s)) return (cstring_makeLiteral ("<NULL>"));
708
709	rangeTable_elements (s, key, value)
710	{
711	st = message ("%q\t%q -> %q\n", st, sRef_unparse (key),
712	sRefSet_unparse (value));
713	} end_rangeTable_elements;
714
715	return st;
716	}
717
718	/*
719	** bogus!
720	*/
721
722	void
723	rangeTable_fixSrefs (rangeTable s)
724	{
725	int i;
726
727	if (rangeTable_isUndefined (s)) return;
728
729	for (i = 0; i < s->nelements; i++)
730	{
731	sRef old = s->keys[i];
732
733	if (sRef_isLocalVar (old))
734	{
735	s->keys[i] = uentry_getSref (sRef_getUentry (old));
736	}
737
738	sRefSet_fixSrefs (s->values[i]);
739	}
740	}
741
742	void
743	rangeTable_free (/@only@/ rangeTable s)
744	{
745	int i;
746
747	if (rangeTable_isUndefined (s)) return;
748
749	for (i = 0; i < s->nelements; i++)
750	{
751	sRefSet_free (s->values[i]);
752	}
753
754	sfree (s->values);
755	sfree (s->keys);
756	sfree (s);
757	}
758
759	void
760	rangeTable_checkGlobs (rangeTable t)
761	{
762	rangeTable_elements (t, key, value)
763	{
764	sRef root = sRef_getRootBase (key);
765
766	if (sRef_isRangeCheckedGlobal (root))
767	{
768	sRefSet_realElements (value, sr)
769	{
770	root = sRef_getRootBase (sr);
771
772	if (((sRef_isRangeCheckedGlobal (root)
773	&& !(sRef_similar (root, key)))
774	\|\| sRef_isAnyParam (root))
775	&& !sRef_isExposed (root))
776	{
777	if (sRef_isRangeCheckedGlobal (key))
778	{
779	if (!(sRef_isShared (key)
780	&& sRef_isShared (root)))
781	{
782	voptgenerror
783	(FLG_GLOBRANGE,
784	message
785	("Function returns with %q variable %q rangeing %q %q",
786	cstring_makeLiteral (sRef_isRealGlobal (key)
787	? "global" : "file static"),
788	sRef_unparse (key),
789	cstring_makeLiteral (sRef_isAnyParam (root)
790	? "parameter" : "global"),
791	sRef_unparse (sr)),
792	g_currentloc);
793	}
794	}
795
796	}
797	} end_sRefSet_realElements;
798	}
799	else if (sRef_isAnyParam (key) \|\| sRef_isAnyParam (root))
800	{
801	sRefSet_realElements (value, sr)
802	{
803	root = sRef_getRootBase (sr);
804
805	if (sRef_isRangeCheckedGlobal (root)
806	&& !sRef_isExposed (root)
807	&& !sRef_isDead (key)
808	&& !sRef_isShared (root))
809	{
810	voptgenerror
811	(FLG_GLOBRANGE,
812	message ("Function returns with parameter %q rangeing %q %q",
813	sRef_unparse (key),
814	cstring_makeLiteral (sRef_isRealGlobal (root)
815	? "global" : "file static"),
816	sRef_unparse (sr)),
817	g_currentloc);
818	}
819	} end_sRefSet_realElements;
820	}
821	else
822	{
823	;
824	}
825	} end_rangeTable_elements;
826	}
827
828
829