[splint.git] / src / sRefSet.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
*/
/*
** sRefSet.c
**
** based on set_template.c
**
** where T has T_equal (or change this) and T_unparse
*/

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

sRefSet
sRefSet_new ()
{
  return sRefSet_undefined;
}

static /*@notnull@*/ /*@only@*/ sRefSet
sRefSet_newEmpty (void)
{
  sRefSet s = (sRefSet) dmalloc (sizeof (*s));
  
  s->entries = 0;
  s->nspace = sRefSetBASESIZE;
  s->elements = (sRef *) dmalloc (sizeof (*s->elements) * sRefSetBASESIZE);

  return (s);
}

/*@only@*/ sRefSet
sRefSet_single (/*@exposed@*/ sRef sr)
{
  sRefSet s = (sRefSet) dmalloc (sizeof (*s));
  
  s->entries = 1;
  s->nspace = sRefSetBASESIZE - 1;
  s->elements = (sRef *) dmalloc (sizeof (*s->elements) * sRefSetBASESIZE);
  s->elements[0] = sr;

    return (s);
}

static void
sRefSet_grow (/*@notnull@*/ sRefSet s)
{
  int i;
  sRef *newelements; 

  s->nspace = sRefSetBASESIZE;
  newelements = (sRef *) dmalloc (sizeof (*newelements) * (s->entries + s->nspace));

  for (i = 0; i < s->entries; i++)
    {
      newelements[i] = s->elements[i];
    }

  sfree (s->elements);
  s->elements = newelements;
}

sRefSet
sRefSet_insert (sRefSet s, /*@exposed@*/ sRef el)
{
  if (sRefSet_isUndefined (s))
    {
      s = sRefSet_newEmpty ();
    }

  
  if (!sRefSet_isSameMember (s, el))
    {
      
      if (s->nspace <= 0)
	sRefSet_grow (s);

      s->nspace--;

      llassert (s->elements != NULL);
      s->elements[s->entries] = el;

            s->entries++;
    }
  else
    {
          }

  return s;
}

void
sRefSet_clear (sRefSet s)
{
  if (sRefSet_isDefined (s))
    {
      s->nspace += s->entries;
      s->entries = 0;
    }
}

/*
** slow algorithm...but it doesn't matter
*/

void
sRefSet_clearStatics (sRefSet s)
{
  if (sRefSet_isDefined (s))
    {
      int i;

      for (i = 0; i < s->entries; i++)
	{
	  sRef current = s->elements[i];
	  
	  if (sRef_isFileStatic (sRef_getRootBase (current)))
	    {
	      int j;
	      
	      for (j = i; j < s->entries - 1; j++)
		{
		  s->elements[j] = s->elements[j+1];
		}
	      
	      s->entries--;
	      s->nspace++;
	      i--;
	    }
	}
    }
}

bool
sRefSet_delete (sRefSet s, sRef el)
{
  int i;

  if (sRefSet_isUndefined (s)) return FALSE;

  if (s->elements != NULL)
    {
      for (i = 0; i < s->entries; i++)
	{
	  sRef current = s->elements[i];
	  
	  if (sRef_realSame (el, current))
	    {
	      int j;

	      for (j = i; j < s->entries - 1; j++)
		{
		  s->elements[j] = s->elements[j+1];
		}
	      
	      s->entries--;
	      s->nspace++;
	      return TRUE;
	    }
	}
    }

  return FALSE;
}

/*@exposed@*/ sRef
sRefSet_choose (sRefSet s)
{
  llassert (sRefSet_isDefined (s));
  llassert (s->entries > 0);
  llassert (s->elements != NULL);

  return (s->elements[0]);
}

sRef
sRefSet_mergeIntoOne (sRefSet s)
{
  sRef res;
  int i;

  if (sRefSet_isUndefined (s)) return sRef_undefined;
  if (s->entries == 0) return sRef_undefined;

  llassert (s->elements != NULL);

  res = s->elements[0];

  for (i = 1; i < s->entries; i++)
    {
      sRef tmp;

            tmp = sRef_makeConj (res, s->elements[i]);
            res = tmp;
    }

  return res;
}

/*
** this is really yucky...but it works...
*/

bool
sRefSet_deleteBase (sRefSet s, sRef base)
{
  int i = 0;
  int offset = 0;

  if (sRefSet_isUndefined (s) || (s->elements == NULL))
    {
      return FALSE;
    } ;

  while (i + offset < s->entries)
    {
      sRef current = s->elements[i + offset];

      while (sRef_includedBy (current, base))
	{
	  	  offset++;
	  if (i + offset >= s->entries) goto doneLoop;
	  current = s->elements [i + offset];
	}
      
      if (offset > 0)
	{
	  	  s->elements [i] = current;
	}
      
      i++;
    }

 doneLoop:
  s->entries -= offset;
  s->nspace += offset;

  return (offset > 0);
}

/*
** modifies *s1
*/

sRefSet
sRefSet_unionFree (/*@returned@*/ sRefSet s1, sRefSet s2)
{
  sRefSet res = sRefSet_union (s1, s2);

  sRefSet_free (s2);
  return res;
}

sRefSet
sRefSet_union (/*@returned@*/ sRefSet s1, sRefSet s2)
{
  if (s1 == s2) 
    {
      return s1;
    }

  if (sRefSet_isEmpty (s1))
    {
      s1 = sRefSet_copy (s1, s2);
    }
  else
    {
      sRefSet_allElements (s2, el)
	{
	  s1 = sRefSet_insert (s1, el);
	} end_sRefSet_allElements;
    }

  return s1;
}

/*
** s1 <- s1 U (s2 - ex - params)
*/

sRefSet
sRefSet_unionExcept (/*@returned@*/ sRefSet s1, sRefSet s2, sRef ex)
{
  if (s1 == s2) return s1;

  sRefSet_allElements (s2, el)
    {
      if (sRef_same (el, ex))
	{
	  	}
      else
	{
	  s1 = sRefSet_insert (s1, el);
	}
    } end_sRefSet_allElements;
  
  return s1;
}

/*@only@*/ sRefSet
sRefSet_realNewUnion (sRefSet s1, sRefSet s2)
{
  llassert (NOALIAS (s1, s2));

  if (sRefSet_isUndefined (s1))
    {
      return (sRefSet_newCopy (s2));
    }
  else
    {
      sRefSet ret = sRefSet_newCopy (s1);
      
      sRefSet_allElements (s2, el)
	{
	  ret = sRefSet_insert (ret, el);
	} end_sRefSet_allElements;
      
      return ret;
    }
}

/* slow! */

/*@only@*/ sRefSet
sRefSet_intersect (sRefSet s1, sRefSet s2)
{
  sRefSet s = sRefSet_new ();

  llassert (NOALIAS (s1, s2));

  sRefSet_allElements (s1, el)
    {
      if (sRefSet_member (s2, el))
	{
	  s = sRefSet_insert (s, el);
	}
    } end_sRefSet_allElements;
  
    return s;
}

sRefSet
sRefSet_levelUnion (/*@returned@*/ sRefSet sr, sRefSet s, int lexlevel)
{
  llassert (NOALIAS (sr, s));

  sRefSet_allElements (s, el)
    {
      if (sRef_lexLevel (el) <= lexlevel)
	{
	  sr = sRefSet_insert (sr, el);
	}
    } end_sRefSet_allElements;

  return sr;
}

void
sRefSet_levelPrune (sRefSet s, int lexlevel)
{
  if (sRefSet_isDefined (s))
    {
      int i;
      int backcount = sRefSet_size (s) - 1;
      
      for (i = 0; i <= backcount; i++)
	{
	  sRef el = s->elements[i]; 
	  
	  if (sRef_lexLevel (el) > lexlevel)
	    {
	      int j;
	      
	      
	      for (j = backcount; j > i; j--)
		{
		  backcount--;
		  s->entries--;
		  s->nspace++;
		  
		  if (sRef_lexLevel (s->elements[j]) <= lexlevel)
		    {
		      s->elements[i] = s->elements[j];
		      
		      if (backcount == i) s->entries++;
		      /*@innerbreak@*/ break;
		    }
		}

	      if (backcount == i)
		{
		  s->entries--;
		}
	    }
	}
    }
}

/*
** s1 <- s2
*/

sRefSet
  sRefSet_copy (/*@returned@*/ sRefSet s1, /*@exposed@*/ sRefSet s2)
{
  int origentries;
  
  llassert (NOALIAS (s1, s2));
  
  if (sRefSet_isUndefined (s1))
    {
      if (sRefSet_isEmpty (s2))
	{
	  return s1;
	}
      else
	{
	  s1 = sRefSet_newEmpty ();
	}
    } 

  origentries = s1->entries;

  s1->nspace = s1->entries + s1->nspace;
  s1->entries = 0;

  sRefSet_allElements (s2, el)
    {
      if (s1->nspace == 0)
	{
	  sRefSet_grow (s1);
	}

      s1->elements[s1->entries] = el; 
      s1->nspace--;
      s1->entries++;
    } end_sRefSet_allElements;

  return s1;
}

/*@only@*/ sRefSet
  sRefSet_newCopy (/*@exposed@*/ sRefSet s)
{
  if (sRefSet_isEmpty (s))
    {
      return sRefSet_undefined;
    }
  else
    {
      sRefSet r = (sRefSet) dmalloc (sizeof (*r));
      int i;
      
      r->entries = s->entries;
      r->nspace = s->nspace;
      r->elements = (sRef *) dmalloc (sizeof (*r->elements) * (s->entries + s->nspace));
      
      for (i = 0; i < s->entries; i++)
	{
	  r->elements[i] = s->elements[i]; 
	}  
      
      return r;
    }
}

/*@only@*/ sRefSet
sRefSet_levelCopy (/*@exposed@*/ sRefSet s, int lexlevel)
{
  if (sRefSet_isEmpty (s))
    {
      return sRefSet_undefined;
    }
  else
    {
      sRefSet r = (sRefSet) dmalloc (sizeof (*r));
      int i;
      
      r->nspace = s->entries;
      r->entries = 0;
      r->elements = (sRef *) dmalloc (sizeof (*r->elements) * (s->entries)); 

      for (i = 0; i < s->entries; i++)
	{
	  if (sRef_lexLevel (s->elements[i]) <= lexlevel)
	    {
	      r->elements[r->entries] = s->elements[i];
	      r->entries++;
	      r->nspace--;
	    }
	}  
      
      return r;
    }
}

/*@only@*/ sRefSet
sRefSet_newDeepCopy (sRefSet s)
{
  if (sRefSet_isUndefined (s))
    {
      return sRefSet_newEmpty ();
    }
  else
    {
      sRefSet r = (sRefSet) dmalloc (sizeof (*r));
      int i;
      
      r->entries = s->entries;
      r->nspace = s->nspace;
      r->elements = (sRef *) dmalloc (sizeof (*r->elements) * (s->entries + s->nspace));
      
      for (i = 0; i < s->entries; i++)
	{
	  r->elements[i] = sRef_copy (s->elements[i]);
	}  
      
      return r;
    }
}

static bool
sRefSet_isElementCompare (bool (*test)(sRef, sRef), sRefSet s, sRef el)
{
  sRefSet_allElements (s, e)
    {
      if ((test)(el, e))
	{
	  return TRUE;
	}
    } end_sRefSet_allElements;

  return FALSE;
}

static bool
sRefSet_isElementTest (bool (*test)(sRef), sRefSet s)
{
  sRefSet_allElements (s, e)
    {
      if ((test)(e))
	{
	  return TRUE;
	}
    } end_sRefSet_allElements;

  return FALSE;
}

bool
sRefSet_hasRealElement (sRefSet s)
{
  sRefSet_allElements (s, e)
    {
      if (sRef_isMeaningful (e) && !sRef_isUnconstrained (e))
	{
	  return TRUE;
	}
    } end_sRefSet_allElements;

  return FALSE;
}

bool
sRefSet_isSameMember (sRefSet s, sRef el)
{
  return (sRefSet_isElementCompare (sRef_realSame, s, el));
}

bool
sRefSet_isSameNameMember (sRefSet s, sRef el)
{
  return (sRefSet_isElementCompare (sRef_sameName, s, el));
}

bool
sRefSet_member (sRefSet s, sRef el)
{
  return (sRefSet_isElementCompare (sRef_similar, s, el));
}

bool
sRefSet_hasStatic (sRefSet s)
{
  return (sRefSet_isElementTest (sRef_isFileStatic, s));
}

bool
sRefSet_hasUnconstrained (sRefSet s)
{
  return (sRefSet_isElementTest (sRef_isUnconstrained, s));
}

cstring
  sRefSet_unparseUnconstrained (sRefSet s)
{
  int num = 0;
  cstring res = cstring_undefined;
  
  sRefSet_allElements (s, el)
    {
      if (sRef_isUnconstrained (el))
	{
	  if (cstring_isUndefined (res))
	    {
	      res = cstring_copy (sRef_unconstrainedName (el));
	    }
	  else
	    {
	      res = message ("%q, %s", res, sRef_unconstrainedName (el));
	    }
	  
	  num++;
	}
    } end_sRefSet_allElements ;
  
  if (num == 0)
    {
      llassert (cstring_isUndefined (res));
      return (cstring_makeLiteral ("<ERROR: no unconstrained calls>"));
    }
  else if (num == 1)
    {
      return (message ("unconstrained function %q", res));
    }
  else
    {
      return (message ("unconstrained functions %q", res));
    }
}

cstring
sRefSet_unparseUnconstrainedPlain (sRefSet s)
{
  cstring res = cstring_undefined;

  sRefSet_allElements (s, el)
    {
      if (sRef_isUnconstrained (el))
	{
	  if (cstring_isUndefined (res))
	    {
	      res = cstring_copy (sRef_unconstrainedName (el));
	    }
	  else
	    {
	      res = message ("%q, %s", res, sRef_unconstrainedName (el));
	    }
	}
    } end_sRefSet_allElements ;

  return res;
}
      
bool
sRefSet_modifyMember (sRefSet s, sRef m)
{
  bool ret = FALSE;

  sRefSet_allElements (s, e)
    {
      if (sRef_similar (m, e))
	{
	  sRef_setModified (e);
	  ret = TRUE;
	}
    } end_sRefSet_allElements;

  
  return ret;
}

/*@exposed@*/ sRef
sRefSet_lookupMember (sRefSet s, sRef el)
{
  sRefSet_allElements (s, e)
    {
      if (sRef_similar (el, e))
	{
	  return e;
	}
    } end_sRefSet_allElements;
  
  return sRef_undefined;
}

int sRefSet_size (sRefSet s)
{
  if (sRefSet_isUndefined (s)) return 0;
  return s->entries;
}

/*@only@*/ cstring
sRefSet_unparse (sRefSet s)
{
  int i;
  cstring st = cstring_makeLiteral ("{");

  if (sRefSet_isDefined (s))
    {
      for (i = 0; i < sRefSet_size (s); i++)
	{
	  if (i == 0)
	    st = message ("%q %q", st, sRef_unparse (s->elements[i]));
	  else
	    st = message ("%q, %q", st, sRef_unparse (s->elements[i]));
	}
    }
  
  st = message ("%q }", st);
  return st;
}

cstring sRefSet_unparsePlain (sRefSet s)
{
  int i;
  cstring st = cstring_undefined;

  if (sRefSet_isDefined (s))
    {
      for (i = 0; i < sRefSet_size (s); i++)
	{
	  if (i == 0)
	    st = sRef_unparse (s->elements[i]);
	  else
	    st = message ("%q, %q", st, sRef_unparse (s->elements[i]));
	}
    }
  
  return st;
}

cstring
sRefSet_unparseDebug (sRefSet s)
{
  int i;
  cstring st = cstring_makeLiteral ("{");

  if (sRefSet_isDefined (s))
    {
      for (i = 0; i < sRefSet_size (s); i++)
	{
	  if (i == 0)
	    {
	      st = message ("%q %q", st, sRef_unparseDebug (s->elements[i]));
	    }
	  else
	    {
	      st = message ("%q, %q", st, sRef_unparseDebug (s->elements[i]));
	    }
	}
    }
  
  st = message ("%q }", st);
  return st;
}

void
sRefSet_fixSrefs (sRefSet s)
{
  if (sRefSet_isDefined (s))
    {
      int i;
      
      for (i = 0; i < sRefSet_size (s); i++)
	{
	  sRef current = s->elements[i];

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

void
sRefSet_free (/*@only@*/ sRefSet s)
{
  if (!sRefSet_isUndefined (s))
    {
      llassertprint (s->entries < 1000, ("sRefSet free size: %d", s->entries));

      sfree (s->elements); 
      sfree (s);
    }
}

sRefSet sRefSet_removeIndirection (sRefSet s)
{
  /*
  ** returns a NEW sRefSet containing references to all sRef's in s
  */

  sRefSet t = sRefSet_new ();
  
  
  sRefSet_allElements (s, el)
    {
      if (!sRef_isAddress (el))
	{
	  t = sRefSet_insert (t, sRef_makeAddress (el));
	}
    } end_sRefSet_allElements;

  return t;
}

sRefSet sRefSet_addIndirection (sRefSet s)
{
  /*
  ** returns a NEW sRefSet containing references to all sRef's in s
  */

  sRefSet t = sRefSet_new ();
  
  
  sRefSet_allElements (s, el)
    {
      ctype ct = ctype_realType (sRef_getType (el));

      
      if ((ctype_isArrayPtr (ct)))
	{
	  
	  sRef a = sRef_constructPointer (el);

	  t = sRefSet_insert (t, a);   
	}
    } end_sRefSet_allElements;

    return t;
}

sRefSet sRefSet_accessField (sRefSet s, /*@observer@*/ cstring f)
{
  /*
  ** returns a NEW sRefSet containing references to all sRef's in s
  */

  sRefSet t = sRefSet_new ();

  
  sRefSet_allElements (s, el)
    {
      ctype ct = ctype_realType (sRef_getType (el));

      if ((ctype_isStruct (ct) || ctype_isUnion (ct))
	  && (!uentry_isUndefined (uentryList_lookupField (ctype_getFields (ct), f))))
	{
	  t = sRefSet_insert (t, sRef_makeNCField (el, f));
	}
    } end_sRefSet_allElements;
  
    return t;
}

sRefSet sRefSet_fetchUnknown (sRefSet s)
{
  sRefSet t = sRefSet_new ();
  
  sRefSet_allElements (s, el)
    {
      ctype ct = ctype_realType (sRef_getType (el));
      
      if (ctype_isArrayPtr (ct))
	{
	  t = sRefSet_insert (t, sRef_makeArrayFetch (el));
	}
    } end_sRefSet_allElements;

  return t;
}

sRefSet sRefSet_fetchKnown (sRefSet s, int i)
{
  sRefSet t = sRefSet_new ();
  
  sRefSet_allElements (s, el)
    {
      ctype ct = ctype_realType (sRef_getType (el));
      
      if (ctype_isArrayPtr (ct))
	{
	  t = sRefSet_insert (t, sRef_makeArrayFetchKnown (el, i));
	}
    } end_sRefSet_allElements;

  return t;
}

int sRefSet_compare (sRefSet s1, sRefSet s2)
{
  sRefSet_allElements (s1, el)
    {
      if (!sRefSet_isSameMember (s2, el))
	{
	  return -1;
	}
    } end_sRefSet_allElements;

  sRefSet_allElements (s2, el)
    {
      if (!sRefSet_isSameMember (s1, el))
	{
	  return 1;
	}
    } end_sRefSet_allElements;

  return 0;
}

bool sRefSet_equal (sRefSet s1, sRefSet s2)
{
  sRefSet_allElements (s1, el)
    {
      if (!sRefSet_isSameMember (s2, el))
	{
	  return FALSE;
	}
    } end_sRefSet_allElements;

  sRefSet_allElements (s2, el)
    {
      if (!sRefSet_isSameMember (s1, el))
	{
	  return FALSE;
	}
    } end_sRefSet_allElements;

  return TRUE;
}

/*@only@*/ sRefSet
sRefSet_undump (char **s)
{
  char c;
  sRefSet sl = sRefSet_new ();

  while ((c = **s) != '#' && c != '@' && c != '$' && c != '&')
    {
      sl = sRefSet_insert (sl, sRef_undump (s));

      
      if (**s == ',')
	{
	  (*s)++;
	}
    }

    return sl;
}

/*@only@*/ cstring
sRefSet_dump (sRefSet sl)
{
  cstring st = cstring_undefined;
  bool first = TRUE;

  
  sRefSet_allElements (sl, el)
    {
      if (!first)
	{
	  st = cstring_appendChar (st, ',');
	}
      else
	{
	  first = FALSE;
	}

      st = cstring_concatFree (st, sRef_dump (el));
    } end_sRefSet_allElements;

  return st;
}
Commit	Line	Data
616915dd	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	** sRefSet.c
	26	**
	27	** based on set_template.c
	28	**
	29	** where T has T_equal (or change this) and T_unparse
	30	*/
	31
	32	# include "lclintMacros.nf"
	33	# include "basic.h"
	34
	35	sRefSet
	36	sRefSet_new ()
	37	{
	38	return sRefSet_undefined;
	39	}
	40
	41	static /@notnull@/ /@only@/ sRefSet
	42	sRefSet_newEmpty (void)
	43	{
	44	sRefSet s = (sRefSet) dmalloc (sizeof (*s));
	45
	46	s->entries = 0;
	47	s->nspace = sRefSetBASESIZE;
	48	s->elements = (sRef ) dmalloc (sizeof (s->elements) * sRefSetBASESIZE);
	49
	50	return (s);
	51	}
	52
	53	/@only@/ sRefSet
	54	sRefSet_single (/@exposed@/ sRef sr)
	55	{
	56	sRefSet s = (sRefSet) dmalloc (sizeof (*s));
	57
	58	s->entries = 1;
	59	s->nspace = sRefSetBASESIZE - 1;
	60	s->elements = (sRef ) dmalloc (sizeof (s->elements) * sRefSetBASESIZE);
	61	s->elements[0] = sr;
	62
	63	return (s);
	64	}
65
66	static void
67	sRefSet_grow (/@notnull@/ sRefSet s)
68	{
69	int i;
70	sRef *newelements;
71
72	s->nspace = sRefSetBASESIZE;
73	newelements = (sRef ) dmalloc (sizeof (newelements) * (s->entries + s->nspace));
74
75	for (i = 0; i < s->entries; i++)
76	{
77	newelements[i] = s->elements[i];
78	}
79
80	sfree (s->elements);
81	s->elements = newelements;
82	}
83
84	sRefSet
85	sRefSet_insert (sRefSet s, /@exposed@/ sRef el)
86	{
87	if (sRefSet_isUndefined (s))
88	{
89	s = sRefSet_newEmpty ();
90	}
91
92
93	if (!sRefSet_isSameMember (s, el))
94	{
95
96	if (s->nspace <= 0)
97	sRefSet_grow (s);
98
99	s->nspace--;
100
101	llassert (s->elements != NULL);
102	s->elements[s->entries] = el;
103
104	s->entries++;
105	}
106	else
107	{
108	}
109
110	return s;
111	}
112
113	void
114	sRefSet_clear (sRefSet s)
115	{
116	if (sRefSet_isDefined (s))
117	{
118	s->nspace += s->entries;
119	s->entries = 0;
120	}
121	}
122
123	/*
124	** slow algorithm...but it doesn't matter
125	*/
126
127	void
128	sRefSet_clearStatics (sRefSet s)
129	{
130	if (sRefSet_isDefined (s))
131	{
132	int i;
133
134	for (i = 0; i < s->entries; i++)
135	{
136	sRef current = s->elements[i];
137
138	if (sRef_isFileStatic (sRef_getRootBase (current)))
139	{
140	int j;
141
142	for (j = i; j < s->entries - 1; j++)
143	{
144	s->elements[j] = s->elements[j+1];
145	}
146
147	s->entries--;
148	s->nspace++;
149	i--;
150	}
151	}
152	}
153	}
154
155	bool
156	sRefSet_delete (sRefSet s, sRef el)
157	{
158	int i;
159
160	if (sRefSet_isUndefined (s)) return FALSE;
161
162	if (s->elements != NULL)
163	{
164	for (i = 0; i < s->entries; i++)
165	{
166	sRef current = s->elements[i];
167
168	if (sRef_realSame (el, current))
169	{
170	int j;
171
172	for (j = i; j < s->entries - 1; j++)
173	{
174	s->elements[j] = s->elements[j+1];
175	}
176
177	s->entries--;
178	s->nspace++;
179	return TRUE;
180	}
181	}
182	}
183
184	return FALSE;
185	}
186
187	/@exposed@/ sRef
188	sRefSet_choose (sRefSet s)
189	{
190	llassert (sRefSet_isDefined (s));
191	llassert (s->entries > 0);
192	llassert (s->elements != NULL);
193
194	return (s->elements[0]);
195	}
196
197	sRef
198	sRefSet_mergeIntoOne (sRefSet s)
199	{
200	sRef res;
201	int i;
202
203	if (sRefSet_isUndefined (s)) return sRef_undefined;
204	if (s->entries == 0) return sRef_undefined;
205
206	llassert (s->elements != NULL);
207
208	res = s->elements[0];
209
210	for (i = 1; i < s->entries; i++)
211	{
212	sRef tmp;
213
214	tmp = sRef_makeConj (res, s->elements[i]);
215	res = tmp;
216	}
217
218	return res;
219	}
220
221	/*
222	** this is really yucky...but it works...
223	*/
224
225	bool
226	sRefSet_deleteBase (sRefSet s, sRef base)
227	{
228	int i = 0;
229	int offset = 0;
230
231	if (sRefSet_isUndefined (s) \|\| (s->elements == NULL))
232	{
233	return FALSE;
234	} ;
235
236	while (i + offset < s->entries)
237	{
238	sRef current = s->elements[i + offset];
239
240	while (sRef_includedBy (current, base))
241	{
242	offset++;
243	if (i + offset >= s->entries) goto doneLoop;
244	current = s->elements [i + offset];
245	}
246
247	if (offset > 0)
248	{
249	s->elements [i] = current;
250	}
251
252	i++;
253	}
254
255	doneLoop:
256	s->entries -= offset;
257	s->nspace += offset;
258
259	return (offset > 0);
260	}
261
262	/*
263	** modifies *s1
264	*/
265
266	sRefSet
267	sRefSet_unionFree (/@returned@/ sRefSet s1, sRefSet s2)
268	{
269	sRefSet res = sRefSet_union (s1, s2);
270
271	sRefSet_free (s2);
272	return res;
273	}
274
275	sRefSet
276	sRefSet_union (/@returned@/ sRefSet s1, sRefSet s2)
277	{
278	if (s1 == s2)
279	{
280	return s1;
281	}
282
283	if (sRefSet_isEmpty (s1))
284	{
285	s1 = sRefSet_copy (s1, s2);
286	}
287	else
288	{
289	sRefSet_allElements (s2, el)
290	{
291	s1 = sRefSet_insert (s1, el);
292	} end_sRefSet_allElements;
293	}
294
295	return s1;
296	}
297
298	/*
299	** s1 <- s1 U (s2 - ex - params)
300	*/
301
302	sRefSet
303	sRefSet_unionExcept (/@returned@/ sRefSet s1, sRefSet s2, sRef ex)
304	{
305	if (s1 == s2) return s1;
306
307	sRefSet_allElements (s2, el)
308	{
309	if (sRef_same (el, ex))
310	{
311	}
312	else
313	{
314	s1 = sRefSet_insert (s1, el);
315	}
316	} end_sRefSet_allElements;
317
318	return s1;
319	}
320
321	/@only@/ sRefSet
322	sRefSet_realNewUnion (sRefSet s1, sRefSet s2)
323	{
324	llassert (NOALIAS (s1, s2));
325
326	if (sRefSet_isUndefined (s1))
327	{
328	return (sRefSet_newCopy (s2));
329	}
330	else
331	{
332	sRefSet ret = sRefSet_newCopy (s1);
333
334	sRefSet_allElements (s2, el)
335	{
336	ret = sRefSet_insert (ret, el);
337	} end_sRefSet_allElements;
338
339	return ret;
340	}
341	}
342
343	/* slow! */
344
345	/@only@/ sRefSet
346	sRefSet_intersect (sRefSet s1, sRefSet s2)
347	{
348	sRefSet s = sRefSet_new ();
349
350	llassert (NOALIAS (s1, s2));
351
352	sRefSet_allElements (s1, el)
353	{
354	if (sRefSet_member (s2, el))
355	{
356	s = sRefSet_insert (s, el);
357	}
358	} end_sRefSet_allElements;
359
360	return s;
361	}
362
363	sRefSet
364	sRefSet_levelUnion (/@returned@/ sRefSet sr, sRefSet s, int lexlevel)
365	{
366	llassert (NOALIAS (sr, s));
367
368	sRefSet_allElements (s, el)
369	{
370	if (sRef_lexLevel (el) <= lexlevel)
371	{
372	sr = sRefSet_insert (sr, el);
373	}
374	} end_sRefSet_allElements;
375
376	return sr;
377	}
378
379	void
380	sRefSet_levelPrune (sRefSet s, int lexlevel)
381	{
382	if (sRefSet_isDefined (s))
383	{
384	int i;
385	int backcount = sRefSet_size (s) - 1;
386
387	for (i = 0; i <= backcount; i++)
388	{
389	sRef el = s->elements[i];
390
391	if (sRef_lexLevel (el) > lexlevel)
392	{
393	int j;
394
395
396	for (j = backcount; j > i; j--)
397	{
398	backcount--;
399	s->entries--;
400	s->nspace++;
401
402	if (sRef_lexLevel (s->elements[j]) <= lexlevel)
403	{
404	s->elements[i] = s->elements[j];
405
406	if (backcount == i) s->entries++;
407	/@innerbreak@/ break;
408	}
409	}
410
411	if (backcount == i)
412	{
413	s->entries--;
414	}
415	}
416	}
417	}
418	}
419
420	/*
421	** s1 <- s2
422	*/
423
424	sRefSet
425	sRefSet_copy (/@returned@/ sRefSet s1, /@exposed@/ sRefSet s2)
426	{
427	int origentries;
428
429	llassert (NOALIAS (s1, s2));
430
431	if (sRefSet_isUndefined (s1))
432	{
433	if (sRefSet_isEmpty (s2))
434	{
435	return s1;
436	}
437	else
438	{
439	s1 = sRefSet_newEmpty ();
440	}
441	}
442
443	origentries = s1->entries;
444
445	s1->nspace = s1->entries + s1->nspace;
446	s1->entries = 0;
447
448	sRefSet_allElements (s2, el)
449	{
450	if (s1->nspace == 0)
451	{
452	sRefSet_grow (s1);
453	}
454
455	s1->elements[s1->entries] = el;
456	s1->nspace--;
457	s1->entries++;
458	} end_sRefSet_allElements;
459
460	return s1;
461	}
462
463	/@only@/ sRefSet
464	sRefSet_newCopy (/@exposed@/ sRefSet s)
465	{
466	if (sRefSet_isEmpty (s))
467	{
468	return sRefSet_undefined;
469	}
470	else
471	{
472	sRefSet r = (sRefSet) dmalloc (sizeof (*r));
473	int i;
474
475	r->entries = s->entries;
476	r->nspace = s->nspace;
477	r->elements = (sRef ) dmalloc (sizeof (r->elements) * (s->entries + s->nspace));
478
479	for (i = 0; i < s->entries; i++)
480	{
481	r->elements[i] = s->elements[i];
482	}
483
484	return r;
485	}
486	}
487
488	/@only@/ sRefSet
489	sRefSet_levelCopy (/@exposed@/ sRefSet s, int lexlevel)
490	{
491	if (sRefSet_isEmpty (s))
492	{
493	return sRefSet_undefined;
494	}
495	else
496	{
497	sRefSet r = (sRefSet) dmalloc (sizeof (*r));
498	int i;
499
500	r->nspace = s->entries;
501	r->entries = 0;
502	r->elements = (sRef ) dmalloc (sizeof (r->elements) * (s->entries));
503
504	for (i = 0; i < s->entries; i++)
505	{
506	if (sRef_lexLevel (s->elements[i]) <= lexlevel)
507	{
508	r->elements[r->entries] = s->elements[i];
509	r->entries++;
510	r->nspace--;
511	}
512	}
513
514	return r;
515	}
516	}
517
518	/@only@/ sRefSet
519	sRefSet_newDeepCopy (sRefSet s)
520	{
521	if (sRefSet_isUndefined (s))
522	{
523	return sRefSet_newEmpty ();
524	}
525	else
526	{
527	sRefSet r = (sRefSet) dmalloc (sizeof (*r));
528	int i;
529
530	r->entries = s->entries;
531	r->nspace = s->nspace;
532	r->elements = (sRef ) dmalloc (sizeof (r->elements) * (s->entries + s->nspace));
533
534	for (i = 0; i < s->entries; i++)
535	{
536	r->elements[i] = sRef_copy (s->elements[i]);
537	}
538
539	return r;
540	}
541	}
542
543	static bool
544	sRefSet_isElementCompare (bool (*test)(sRef, sRef), sRefSet s, sRef el)
545	{
546	sRefSet_allElements (s, e)
547	{
548	if ((test)(el, e))
549	{
550	return TRUE;
551	}
552	} end_sRefSet_allElements;
553
554	return FALSE;
555	}
556
557	static bool
558	sRefSet_isElementTest (bool (*test)(sRef), sRefSet s)
559	{
560	sRefSet_allElements (s, e)
561	{
562	if ((test)(e))
563	{
564	return TRUE;
565	}
566	} end_sRefSet_allElements;
567
568	return FALSE;
569	}
570
571	bool
572	sRefSet_hasRealElement (sRefSet s)
573	{
574	sRefSet_allElements (s, e)
575	{
576	if (sRef_isMeaningful (e) && !sRef_isUnconstrained (e))
577	{
578	return TRUE;
579	}
580	} end_sRefSet_allElements;
581
582	return FALSE;
583	}
584
585	bool
586	sRefSet_isSameMember (sRefSet s, sRef el)
587	{
588	return (sRefSet_isElementCompare (sRef_realSame, s, el));
589	}
590
591	bool
592	sRefSet_isSameNameMember (sRefSet s, sRef el)
593	{
594	return (sRefSet_isElementCompare (sRef_sameName, s, el));
595	}
596
597	bool
598	sRefSet_member (sRefSet s, sRef el)
599	{
600	return (sRefSet_isElementCompare (sRef_similar, s, el));
601	}
602
603	bool
604	sRefSet_hasStatic (sRefSet s)
605	{
606	return (sRefSet_isElementTest (sRef_isFileStatic, s));
607	}
608
609	bool
610	sRefSet_hasUnconstrained (sRefSet s)
611	{
612	return (sRefSet_isElementTest (sRef_isUnconstrained, s));
613	}
614
615	cstring
616	sRefSet_unparseUnconstrained (sRefSet s)
617	{
618	int num = 0;
619	cstring res = cstring_undefined;
620
621	sRefSet_allElements (s, el)
622	{
623	if (sRef_isUnconstrained (el))
624	{
625	if (cstring_isUndefined (res))
626	{
627	res = cstring_copy (sRef_unconstrainedName (el));
628	}
629	else
630	{
631	res = message ("%q, %s", res, sRef_unconstrainedName (el));
632	}
633
634	num++;
635	}
636	} end_sRefSet_allElements ;
637
638	if (num == 0)
639	{
640	llassert (cstring_isUndefined (res));
641	return (cstring_makeLiteral ("<ERROR: no unconstrained calls>"));
642	}
643	else if (num == 1)
644	{
645	return (message ("unconstrained function %q", res));
646	}
647	else
648	{
649	return (message ("unconstrained functions %q", res));
650	}
651	}
652
653	cstring
654	sRefSet_unparseUnconstrainedPlain (sRefSet s)
655	{
656	cstring res = cstring_undefined;
657
658	sRefSet_allElements (s, el)
659	{
660	if (sRef_isUnconstrained (el))
661	{
662	if (cstring_isUndefined (res))
663	{
664	res = cstring_copy (sRef_unconstrainedName (el));
665	}
666	else
667	{
668	res = message ("%q, %s", res, sRef_unconstrainedName (el));
669	}
670	}
671	} end_sRefSet_allElements ;
672
673	return res;
674	}
675
676	bool
677	sRefSet_modifyMember (sRefSet s, sRef m)
678	{
679	bool ret = FALSE;
680
681	sRefSet_allElements (s, e)
682	{
683	if (sRef_similar (m, e))
684	{
685	sRef_setModified (e);
686	ret = TRUE;
687	}
688	} end_sRefSet_allElements;
689
690
691	return ret;
692	}
693
694	/@exposed@/ sRef
695	sRefSet_lookupMember (sRefSet s, sRef el)
696	{
697	sRefSet_allElements (s, e)
698	{
699	if (sRef_similar (el, e))
700	{
701	return e;
702	}
703	} end_sRefSet_allElements;
704
705	return sRef_undefined;
706	}
707
708	int sRefSet_size (sRefSet s)
709	{
710	if (sRefSet_isUndefined (s)) return 0;
711	return s->entries;
712	}
713
714	/@only@/ cstring
715	sRefSet_unparse (sRefSet s)
716	{
717	int i;
718	cstring st = cstring_makeLiteral ("{");
719
720	if (sRefSet_isDefined (s))
721	{
722	for (i = 0; i < sRefSet_size (s); i++)
723	{
724	if (i == 0)
725	st = message ("%q %q", st, sRef_unparse (s->elements[i]));
726	else
727	st = message ("%q, %q", st, sRef_unparse (s->elements[i]));
728	}
729	}
730
731	st = message ("%q }", st);
732	return st;
733	}
734
735	cstring sRefSet_unparsePlain (sRefSet s)
736	{
737	int i;
738	cstring st = cstring_undefined;
739
740	if (sRefSet_isDefined (s))
741	{
742	for (i = 0; i < sRefSet_size (s); i++)
743	{
744	if (i == 0)
745	st = sRef_unparse (s->elements[i]);
746	else
747	st = message ("%q, %q", st, sRef_unparse (s->elements[i]));
748	}
749	}
750
751	return st;
752	}
753
754	cstring
755	sRefSet_unparseDebug (sRefSet s)
756	{
757	int i;
758	cstring st = cstring_makeLiteral ("{");
759
760	if (sRefSet_isDefined (s))
761	{
762	for (i = 0; i < sRefSet_size (s); i++)
763	{
764	if (i == 0)
765	{
766	st = message ("%q %q", st, sRef_unparseDebug (s->elements[i]));
767	}
768	else
769	{
770	st = message ("%q, %q", st, sRef_unparseDebug (s->elements[i]));
771	}
772	}
773	}
774
775	st = message ("%q }", st);
776	return st;
777	}
778
779	void
780	sRefSet_fixSrefs (sRefSet s)
781	{
782	if (sRefSet_isDefined (s))
783	{
784	int i;
785
786	for (i = 0; i < sRefSet_size (s); i++)
787	{
788	sRef current = s->elements[i];
789
790	if (sRef_isLocalVar (current))
791	{
792	s->elements[i] = uentry_getSref (sRef_getUentry (current));
793	}
794	}
795	}
796	}
797
798	void
799	sRefSet_free (/@only@/ sRefSet s)
800	{
801	if (!sRefSet_isUndefined (s))
802	{
803	llassertprint (s->entries < 1000, ("sRefSet free size: %d", s->entries));
804
805	sfree (s->elements);
806	sfree (s);
807	}
808	}
809
810	sRefSet sRefSet_removeIndirection (sRefSet s)
811	{
812	/*
813	** returns a NEW sRefSet containing references to all sRef's in s
814	*/
815
816	sRefSet t = sRefSet_new ();
817
818
819	sRefSet_allElements (s, el)
820	{
821	if (!sRef_isAddress (el))
822	{
823	t = sRefSet_insert (t, sRef_makeAddress (el));
824	}
825	} end_sRefSet_allElements;
826
827	return t;
828	}
829
830	sRefSet sRefSet_addIndirection (sRefSet s)
831	{
832	/*
833	** returns a NEW sRefSet containing references to all sRef's in s
834	*/
835
836	sRefSet t = sRefSet_new ();
837
838
839	sRefSet_allElements (s, el)
840	{
841	ctype ct = ctype_realType (sRef_getType (el));
842
843
844	if ((ctype_isArrayPtr (ct)))
845	{
846
847	sRef a = sRef_constructPointer (el);
848
849	t = sRefSet_insert (t, a);
850	}
851	} end_sRefSet_allElements;
852
853	return t;
854	}
855
856	sRefSet sRefSet_accessField (sRefSet s, /@observer@/ cstring f)
857	{
858	/*
859	** returns a NEW sRefSet containing references to all sRef's in s
860	*/
861
862	sRefSet t = sRefSet_new ();
863
864
865	sRefSet_allElements (s, el)
866	{
867	ctype ct = ctype_realType (sRef_getType (el));
868
869	if ((ctype_isStruct (ct) \|\| ctype_isUnion (ct))
870	&& (!uentry_isUndefined (uentryList_lookupField (ctype_getFields (ct), f))))
871	{
872	t = sRefSet_insert (t, sRef_makeNCField (el, f));
873	}
874	} end_sRefSet_allElements;
875
876	return t;
877	}
878
879	sRefSet sRefSet_fetchUnknown (sRefSet s)
880	{
881	sRefSet t = sRefSet_new ();
882
883	sRefSet_allElements (s, el)
884	{
885	ctype ct = ctype_realType (sRef_getType (el));
886
887	if (ctype_isArrayPtr (ct))
888	{
889	t = sRefSet_insert (t, sRef_makeArrayFetch (el));
890	}
891	} end_sRefSet_allElements;
892
893	return t;
894	}
895
896	sRefSet sRefSet_fetchKnown (sRefSet s, int i)
897	{
898	sRefSet t = sRefSet_new ();
899
900	sRefSet_allElements (s, el)
901	{
902	ctype ct = ctype_realType (sRef_getType (el));
903
904	if (ctype_isArrayPtr (ct))
905	{
906	t = sRefSet_insert (t, sRef_makeArrayFetchKnown (el, i));
907	}
908	} end_sRefSet_allElements;
909
910	return t;
911	}
912
913	int sRefSet_compare (sRefSet s1, sRefSet s2)
914	{
915	sRefSet_allElements (s1, el)
916	{
917	if (!sRefSet_isSameMember (s2, el))
918	{
919	return -1;
920	}
921	} end_sRefSet_allElements;
922
923	sRefSet_allElements (s2, el)
924	{
925	if (!sRefSet_isSameMember (s1, el))
926	{
927	return 1;
928	}
929	} end_sRefSet_allElements;
930
931	return 0;
932	}
933
934	bool sRefSet_equal (sRefSet s1, sRefSet s2)
935	{
936	sRefSet_allElements (s1, el)
937	{
938	if (!sRefSet_isSameMember (s2, el))
939	{
940	return FALSE;
941	}
942	} end_sRefSet_allElements;
943
944	sRefSet_allElements (s2, el)
945	{
946	if (!sRefSet_isSameMember (s1, el))
947	{
948	return FALSE;
949	}
950	} end_sRefSet_allElements;
951
952	return TRUE;
953	}
954
955	/@only@/ sRefSet
956	sRefSet_undump (char **s)
957	{
958	char c;
959	sRefSet sl = sRefSet_new ();
960
961	while ((c = **s) != '#' && c != '@' && c != '$' && c != '&')
962	{
963	sl = sRefSet_insert (sl, sRef_undump (s));
964
965
966	if (**s == ',')
967	{
968	(*s)++;
969	}
970	}
971
972	return sl;
973	}
974
975	/@only@/ cstring
976	sRefSet_dump (sRefSet sl)
977	{
978	cstring st = cstring_undefined;
979	bool first = TRUE;
980
981
982	sRefSet_allElements (sl, el)
983	{
984	if (!first)
985	{
986	st = cstring_appendChar (st, ',');
987	}
988	else
989	{
990	first = FALSE;
991	}
992
993	st = cstring_concatFree (st, sRef_dump (el));
994	} end_sRefSet_allElements;
995
996	return st;
997	}
998