[splint.git] / src / aliasTable.c

/*
** Splint - annotation-assisted static program checker
** Copyright (C) 1994-2003 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 splint: info@splint.org
** To report a bug: splint-bug@splint.org
** For more information: http://www.splint.org
*/
/*
** aliasTable.c
*/

# include "splintMacros.nf"
# include "basic.h"

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

static sRefSet
  aliasTable_canAliasAux (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
static sRefSet
  aliasTable_aliasedByLimit (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
static sRefSet 
  aliasTable_aliasedByAux (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;

aliasTable
aliasTable_new ()
{
  return (aliasTable_undefined);
}

static /*@only@*/ /*@notnull@*/ aliasTable
aliasTable_newEmpty (void)
{
  aliasTable s = (aliasTable) dmalloc (sizeof (*s));
  
  s->nelements = 0;
  s->nspace = aliasTableBASESIZE;
  s->keys = (sRef *) dmalloc (sizeof (*s->keys) * aliasTableBASESIZE);
  s->values = (sRefSet *) dmalloc (sizeof (*s->values) * aliasTableBASESIZE);
  
  return (s);
}

static void
aliasTable_grow (/*@notnull@*/ aliasTable s)
{
  int i;
  o_sRefSet *oldvalues = s->values;
  sRef    *oldkeys = s->keys;
  
  s->nspace += aliasTableBASESIZE; 

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

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

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

static int aliasTable_lookupRefs (/*@notnull@*/ aliasTable s, sRef sr)
{
  int i;

  
  for (i = 0; i < aliasTable_size (s); i++)
    {
      if (sRef_same (sr, s->keys[i])) 
	{
	  DPRINTF (("sRef match: %s / %s",
		    sRef_unparseFull (sr),
		    sRef_unparseFull (s->keys[i])));
	  return i;
	}
    }

  return ATINVALID;
}

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

aliasTable
aliasTable_addMustAlias (/*@returned@*/ aliasTable s,
			 /*@exposed@*/ sRef sr,
			 /*@exposed@*/ sRef al)
{
  int ind;
  sRefSet ss;
  
  llassert (NOALIAS (sr, al));
  
  DPRINTF (("Adding alias: %s / %s", sRef_unparseFull (sr),
	    sRef_unparseFull (al)));

  if (aliasTable_isUndefined (s))
    {
      s = aliasTable_newEmpty ();
      ind = ATINVALID;
    }
  else
    {
      ind = aliasTable_lookupRefs (s, sr);
    }
  
  ss = aliasTable_canAlias (s, al); 
  DPRINTF (("Previous aliases: %s", sRefSet_unparse (ss)));
  
  if (ind == ATINVALID)
    {
      if (s->nspace <= 0) {
	aliasTable_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]); 
  DPRINTF (("New aliases: %s", sRefSet_unparse (s->values[ind])));

  sRefSet_free (ss);
  return s;
}

static aliasTable 
  aliasTable_addSet (/*@returned@*/ aliasTable s,
		     /*@exposed@*/ sRef key, /*@only@*/ sRefSet value)
{
  if (!sRefSet_isEmpty (value))
    {
      if (aliasTable_isUndefined (s))
	{
	  s = aliasTable_newEmpty ();
	}
      else
	{
	  if (s->nspace <= 0)
	    {
	      aliasTable_grow (s);
	    }
	}

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

  return s;
}

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

static void aliasTable_clearAliasesAux (/*@notnull@*/ aliasTable p_s, sRef p_sr)
   /*@modifies p_s@*/ ;

void aliasTable_clearAliases (aliasTable s, sRef sr)
{
  if (aliasTable_isUndefined (s))
    {
      return;
    }
  else
    {
      sRef rb = sRef_getRootBase (sr);

            
      if (!sRef_isCvar (sr) && sRef_isLocalVar (rb))
	{
	  int ind = aliasTable_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); 

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

static
void aliasTable_clearAliasesAux (/*@notnull@*/ aliasTable 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 alias sr (but are different from sr)
*/

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

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

      return sRefSet_undefined;
    }
  else
    {
      sRefSet abl;

      if (sRef_isPointer (sr))
	{
	  abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
	  res = sRefSet_addIndirection (abl);
	}
      else if (sRef_isAddress (sr))
	{
	  abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
	  res = sRefSet_removeIndirection (abl);
	}
      else if (sRef_isField (sr))
	{
	  abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
	  res = sRefSet_accessField (abl, sRef_getField (sr));
	}
      else if (sRef_isArrayFetch (sr))
	{
	  abl = aliasTable_aliasedByLimit (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 aliasTable_aliasedByLimit (aliasTable s, sRef sr, int lim)
{
  sRefSet res;
  
  
  if (sRef_isConj (sr))
    {
      res = sRefSet_unionFree (aliasTable_aliasedByLimit (s, sRef_getConjA (sr), lim),
			       aliasTable_aliasedByLimit (s, sRef_getConjB (sr), lim));
    }
  else
    {
      res = aliasTable_aliasedByAux (s, sr, lim + 1);
    }
  
    return res;
}

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

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

/*@only@*/ sRefSet aliasTable_canAlias (aliasTable s, sRef sr)
{
  sRefSet res;

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

    return res;
}

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

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

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

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

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

      if (sRef_isPointer (sr) || sRef_isAddress (sr) || sRef_isField (sr)
	  || sRef_isArrayFetch (sr))
	{
	  sRef base = sRef_getBase (sr);
	  sRefSet tmp = aliasTable_canAliasLimit (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]);
    }
}

aliasTable aliasTable_copy (aliasTable s)
{
  if (aliasTable_isEmpty (s))
    {
      return aliasTable_undefined;
    }
  else
    {
      aliasTable t = (aliasTable) 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
aliasTable_levelPrune (aliasTable s, int lexlevel)
{
  
  
  if (aliasTable_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".
*/

aliasTable aliasTable_levelUnionSeq (/*@returned@*/ aliasTable t1, 
				     /*@only@*/ aliasTable t2, int level)
{
  if (aliasTable_isUndefined (t2))
    {
      return t1;
    }

  if (aliasTable_isUndefined (t1))
    {
      t1 = aliasTable_newEmpty ();
    }
  else
    {
      aliasTable_levelPrune (t1, level);
    }

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

	  sRefSet_levelPrune (value, level);
	      
	  if (ind == ATINVALID)
	    {
	      /* okay, t2 is killed */
	      /*@-exposetrans@*/ /*@-dependenttrans@*/ 
	      t1 = aliasTable_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_aliasTable_elements;
  
  sfree (t2->keys);
  sfree (t2->values);
  sfree (t2);

    return t1;
}

aliasTable 
aliasTable_levelUnion (/*@returned@*/ aliasTable t1, aliasTable t2, int level)
{
  if (aliasTable_isUndefined (t1))
    {
      if (aliasTable_isUndefined (t2)) 
	{
	  return t1;
	}
      else
	{
	  t1 = aliasTable_newEmpty ();
	}
    }
  else
    {
      aliasTable_levelPrune (t1, level);
    }

  aliasTable_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 = aliasTable_lookupRefs (t1, key);
	      
	      if (ind == ATINVALID)
		{
		  t1 = aliasTable_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_aliasTable_elements;

    return t1;
}

aliasTable aliasTable_levelUnionNew (aliasTable t1, aliasTable t2, int level)
{
  aliasTable ret = aliasTable_levelUnion (aliasTable_copy (t1), t2, level);

  return ret;
}

/*@only@*/ cstring
aliasTable_unparse (aliasTable s)
{
   cstring st = cstring_undefined;

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

   aliasTable_elements (s, key, value)
     {
       st = message ("%q\t%q -> %q\n", st, sRef_unparseFull (key), 
		     sRefSet_unparseFull (value));
     } end_aliasTable_elements;

   return st;
}

/*
** bogus!
*/

void
aliasTable_fixSrefs (aliasTable s)
{
  int i;

  if (aliasTable_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
aliasTable_free (/*@only@*/ aliasTable s)
{
  int i;
  
  if (aliasTable_isUndefined (s)) return;
  
  for (i = 0; i < s->nelements; i++)
    {
      sRefSet_free (s->values[i]); 
    }
  
  sfree (s->values);
  sfree (s->keys);
  sfree (s);
}

void 
aliasTable_checkGlobs (aliasTable t)
{
  aliasTable_elements (t, key, value)
    {
      sRef root = sRef_getRootBase (key);

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

	      if (((sRef_isAliasCheckedGlobal (root) 
		    && !(sRef_similar (root, key)))
		   || sRef_isAnyParam (root))
		  && !sRef_isExposed (root))
		{
		  if (sRef_isAliasCheckedGlobal (key))
		    {
		      if (!(sRef_isShared (key) 
			    && sRef_isShared (root)))
			{
			  voptgenerror 
			    (FLG_GLOBALIAS,
			     message 
			     ("Function returns with %q variable %q aliasing %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_isAliasCheckedGlobal (root) 
		  && !sRef_isExposed (root)
		  && !sRef_isDead (key)
		  && !sRef_isShared (root))
		{
		  voptgenerror 
		    (FLG_GLOBALIAS,
		     message ("Function returns with parameter %q aliasing %q %q",
			      sRef_unparse (key),
			      cstring_makeLiteral (sRef_isRealGlobal (root) 
						   ? "global" : "file static"),
			      sRef_unparse (sr)),
		     g_currentloc);
		}
	    } end_sRefSet_realElements;
	}
      else
	{
	  ;
	}
    } end_aliasTable_elements;
}

# ifdef DEBUGSPLINT

/*
** For debugging only
*/

void aliasTable_checkValid (aliasTable t)
{
  aliasTable_elements (t, key, value)
    {
      sRef_checkCompletelyReasonable (key);

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