+static /*@only@*/ constraintList reflectChangesEnsures (/*@observer@*/ constraintList pre2, constraintList post1)
+{
+ constraintList ret;
+ constraint temp;
+ ret = constraintList_makeNew();
+ constraintList_elements (pre2, el)
+ {
+ if (!constraintList_resolve (el, post1) )
+ {
+ temp = constraint_substitute (el, post1);
+ llassert (temp != NULL);
+
+ if (!constraintList_resolve (temp, post1) )
+ ret = constraintList_add (ret, temp);
+ else
+ constraint_free(temp);
+ }
+ else
+ {
+ DPRINTF ((message ("Resolved away %s ", constraint_print(el) ) ) );
+ }
+ } end_constraintList_elements;
+
+ return ret;
+}
+
+
+static /*@only@*/ constraintList reflectChangesEnsuresFree1 (/*@only@*/ constraintList pre2, constraintList post1)
+{
+ constraintList ret;
+
+ ret = reflectChangesEnsures (pre2, post1);
+
+ constraintList_free(pre2);
+
+ return ret;
+}
+
+
+static bool constraint_conflict (constraint c1, constraint c2)
+{
+
+ if (constraintExpr_similar(c1->lexpr, c2->lexpr) )
+ {
+ if (c1->ar == EQ)
+ if (c1->ar == c2->ar)
+ {
+ DPRINTF ((message ("%s conflicts with %s ", constraint_print (c1), constraint_print(c2) ) ) );
+ return TRUE;
+ }
+ }
+
+ /* This is a slight kludg to prevent circular constraints like
+ strlen(str) == maxRead(s) + strlen(str);
+ */
+
+ /*@i324234*/ /* clean this up */
+
+ if (c1->ar == EQ)
+ if (c1->ar == c2->ar)
+ {
+ if (constraintExpr_search (c1->lexpr, c2->expr) )
+ if (constraintExpr_isTerm(c1->lexpr) )
+ {
+ constraintTerm term;
+
+ term = constraintExpr_getTerm(c1->lexpr);
+
+ if (constraintTerm_isExprNode(term) )
+ {
+ DPRINTF ((message ("%s conflicts with %s ", constraint_print (c1), constraint_print(c2) ) ) );
+ return TRUE;
+ }
+ }
+ }
+
+ if (constraint_tooDeep(c1) || constraint_tooDeep(c2) )
+ {
+ DPRINTF ((message ("%s conflicts with %s (constraint is too deep", constraint_print (c1), constraint_print(c2) ) ) );
+ return TRUE;
+ }
+
+ DPRINTF ((message ("%s doesn't conflict with %s ", constraint_print (c1), constraint_print(c2) ) ) );
+
+ return FALSE;
+
+}
+
+static void constraint_fixConflict (/*@temp@*/ constraint good, /*@temp@*/ /*@observer@*/ constraint conflicting) /*@modifies good@*/
+{
+ if (conflicting->ar ==EQ )
+ {
+ good->expr = constraintExpr_searchandreplace (good->expr, conflicting->lexpr, conflicting->expr);
+ good = constraint_simplify (good);
+ }
+
+
+}
+
+static bool conflict (constraint c, constraintList list)
+{
+
+ constraintList_elements (list, el)
+ {
+ if ( constraint_conflict(el, c) )
+ {
+ constraint_fixConflict (el, c);
+ return TRUE;
+ }
+ } end_constraintList_elements;
+
+ return FALSE;
+
+}
+
+/*
+ check if constraint in list1 conflicts with constraints in List2. If so we
+ remove form list1 and change list2.
+*/
+
+constraintList constraintList_fixConflicts (constraintList list1, constraintList list2)
+{
+ constraintList ret;
+ ret = constraintList_makeNew();
+ llassert(constraintList_isDefined(list1) );
+ constraintList_elements (list1, el)
+ {
+ if (! conflict (el, list2) )
+ {
+ constraint temp;
+ temp = constraint_copy(el);
+ ret = constraintList_add (ret, temp);
+ }
+ } end_constraintList_elements;
+
+ return ret;
+}
+
+/*returns true if constraint post satifies cosntriant pre */
+static bool satifies (constraint pre, constraint post)
+{
+ if (constraint_isAlwaysTrue (pre) )
+ return TRUE;
+
+ if (!constraintExpr_similar (pre->lexpr, post->lexpr) )
+ {
+ return FALSE;
+ }
+ if (constraintExpr_isUndefined(post->expr))
+ {
+ llassert(FALSE);
+ return FALSE;
+ }
+
+ return rangeCheck (pre->ar, pre->expr, post->ar, post->expr);
+}
+
+
+bool constraintList_resolve (/*@temp@*/ /*@observer@*/ constraint c, /*@temp@*/ /*@observer@*/ constraintList p)
+{
+ constraintList_elements (p, el)
+ {
+ if ( satifies (c, el) )
+ {
+ DPRINTF ((message ("\n%s Satifies %s\n ", constraint_print(el), constraint_print(c) ) ) );
+ return TRUE;
+ }
+ DPRINTF ((message ("\n%s does not satify %s\n ", constraint_print(el), constraint_print(c) ) ) );
+ }
+ end_constraintList_elements;
+ DPRINTF ((message ("no constraints satify %s", constraint_print(c) ) ));
+ return FALSE;
+}
+
+static bool arithType_canResolve (arithType ar1, arithType ar2)
+{
+ switch (ar1)
+ {
+ case GTE:
+ case GT:
+ if ((ar2 == GT) || (ar2 == GTE) || (ar2 == EQ) )
+ {
+ return TRUE;
+ }
+ break;
+
+ case EQ:
+ if (ar2 == EQ)
+ return TRUE;
+ break;
+
+ case LT:
+ case LTE:
+ if ((ar2 == LT) || (ar2 == LTE) || (ar2 == EQ) )
+ return TRUE;
+ break;
+ default:
+ return FALSE;
+ }
+ return FALSE;
+}
+
+/*checks for the case expr2 == sizeof buf1 and buf1 is a fixed array*/
+static bool sizeofBufComp(constraintExpr buf1, constraintExpr expr2)
+{
+ constraintTerm ct;
+ exprNode e, t;
+ sRef s1, s2;
+ /*@access constraintExpr@*/
+
+ if ((expr2->kind != term) && (buf1->kind != term) )
+ return FALSE;
+
+
+ ct = constraintExprData_termGetTerm(expr2->data);
+
+ if (!constraintTerm_isExprNode(ct) )
+ return FALSE;
+
+ e = constraintTerm_getExprNode(ct);
+
+ if (e->kind != XPR_SIZEOF)
+ return FALSE;
+
+ t = exprData_getSingle (e->edata);
+ s1 = exprNode_getSref (t);
+
+ s2 = constraintTerm_getsRef(constraintExprData_termGetTerm(buf1->data) );
+
+ /*@i223@*/ /*this may be the wronge thing to test for */
+ if (sRef_similarRelaxed(s1, s2) || sRef_sameName (s1, s2) )
+ {
+ /*@i22*/ /* get rid of this test of now */
+ /* if (ctype_isFixedArray (sRef_getType (s2) ) ) */
+ return TRUE;
+ }
+ return FALSE;
+}
+
+/* look for the special case of
+ maxSet(buf) >= sizeof(buf) - 1
+*/
+
+/*@i223@*/ /*need to add some type checking */
+static bool sizeOfMaxSet( /*@observer@*/ /*@temp@*/ constraint c)
+{
+ constraintExpr l, r, buf1, buf2, con;
+
+ DPRINTF(( message("sizeOfMaxSet: checking %s ", constraint_print(c) )
+ ));
+
+ l = c->lexpr;
+ r = c->expr;
+
+ if (!((c->ar == EQ) || (c->ar == GTE) || (c->ar == LTE) ) )
+ return FALSE;
+
+ /*check if the constraintExpr is MaxSet(buf) */
+ if (l->kind == unaryExpr)
+ {
+ if (constraintExprData_unaryExprGetOp(l->data) == MAXSET)
+ {
+ buf1 = constraintExprData_unaryExprGetExpr(l->data);
+ }
+ else
+ return FALSE;
+ }
+ else
+ return FALSE;
+
+
+ if (r->kind != binaryexpr)
+ return FALSE;
+
+ buf2 = constraintExprData_binaryExprGetExpr1(r->data);
+ con = constraintExprData_binaryExprGetExpr2(r->data);
+
+ if (constraintExprData_binaryExprGetOp(r->data) == BINARYOP_MINUS)
+ {
+ if (constraintExpr_canGetValue(con) )
+ {
+ long i;
+
+ i = constraintExpr_getValue(con);
+ if (i != 1)
+ {
+ return FALSE;
+ }
+ }
+ else
+ return FALSE;
+ }
+
+ if (constraintExprData_binaryExprGetOp(r->data) == BINARYOP_PLUS)
+ {
+ if (constraintExpr_canGetValue(con) )
+ {
+ long i;
+
+ i = constraintExpr_getValue(con);
+ if (i != -1)
+ {
+ return FALSE;
+ }
+ }
+ else
+ return FALSE;
+ }
+
+ if (sizeofBufComp(buf1, buf2))
+ {
+ return TRUE;
+ }
+ else
+ {
+ return FALSE;
+ }
+
+
+}
+/*@noaccess constraintExpr@*/
+
+/* We look for constraint which are tautologies */
+
+bool constraint_isAlwaysTrue (/*@observer@*/ /*@temp@*/ constraint c)
+{
+ constraintExpr l, r;
+ bool rHasConstant;
+ int rConstant;
+
+ l = c->lexpr;
+ r = c->expr;
+
+ DPRINTF(( message("constraint_IsAlwaysTrue:examining %s", constraint_print(c) ) ));
+
+ if (sizeOfMaxSet(c) )
+ return TRUE;
+
+ if (constraintExpr_canGetValue(l) && constraintExpr_canGetValue(r) )
+ {
+ int cmp;
+ cmp = constraintExpr_compare (l, r);
+ switch (c->ar)
+ {
+ case EQ:
+ return (cmp == 0);
+ case GT:
+ return (cmp > 0);
+ case GTE:
+ return (cmp >= 0);
+ case LTE:
+ return (cmp <= 0);
+ case LT:
+ return (cmp < 0);
+
+ default:
+ BADEXIT;
+ /*@notreached@*/
+ break;
+ }
+ }
+
+ if (constraintExpr_similar (l,r) )
+ {
+ switch (c->ar)
+ {
+ case EQ:
+ case GTE:
+ case LTE:
+ return TRUE;
+
+ case GT:
+ case LT:
+ break;
+ default:
+ BADEXIT;
+ /*@notreached@*/
+ break;
+ }
+ }
+
+ l = constraintExpr_copy (c->lexpr);
+ r = constraintExpr_copy (c->expr);
+
+ r = constraintExpr_propagateConstants (r, &rHasConstant, &rConstant);
+
+ if (constraintExpr_similar (l,r) && (rHasConstant ) )
+ {
+ DPRINTF(( message("constraint_IsAlwaysTrue: after removing constants %s and %s are similar", constraintExpr_unparse(l), constraintExpr_unparse(r) ) ));
+ DPRINTF(( message("constraint_IsAlwaysTrue: rconstant is %d", rConstant ) ));
+
+ constraintExpr_free(l);
+ constraintExpr_free(r);
+
+ switch (c->ar)
+ {
+ case EQ:
+ return (rConstant == 0);
+ case LT:
+ return (rConstant > 0);
+ case LTE:
+ return (rConstant >= 0);
+ case GTE:
+ return (rConstant <= 0);
+ case GT:
+ return (rConstant < 0);
+
+ default:
+ BADEXIT;
+ /*@notreached@*/
+ break;
+ }
+ }
+ else
+ {
+ constraintExpr_free(l);
+ constraintExpr_free(r);
+ DPRINTF(( message("Constraint %s is not always true", constraint_print(c) ) ));
+ return FALSE;
+ }
+
+ BADEXIT;
+}
+
+static bool rangeCheck (arithType ar1, /*@observer@*/ constraintExpr expr1, arithType ar2, /*@observer@*/ constraintExpr expr2)
+
+{
+ DPRINTF ((message ("Doing Range CHECK %s and %s", constraintExpr_unparse(expr1), constraintExpr_unparse(expr2) ) ));
+
+ if (! arithType_canResolve (ar1, ar2) )
+ return FALSE;
+
+ switch (ar1)
+ {
+ case GTE:
+ if (constraintExpr_similar (expr1, expr2) )
+ return TRUE;
+ /*@fallthrough@*/
+ case GT:
+ if (! (constraintExpr_canGetValue (expr1) &&
+ constraintExpr_canGetValue (expr2) ) )
+ {
+ constraintExpr e1, e2;
+ bool p1, p2;
+ int const1, const2;
+
+ e1 = constraintExpr_copy(expr1);
+ e2 = constraintExpr_copy(expr2);
+
+ e1 = constraintExpr_propagateConstants (e1, &p1, &const1);
+
+ e2 = constraintExpr_propagateConstants (e2, &p2, &const2);
+
+ if (p1 || p2)
+ {
+ if (!p1)
+ const1 = 0;
+
+ if (!p2)
+ const2 = 0;
+
+ if (const1 <= const2)
+ if (constraintExpr_similar (e1, e2) )
+ {
+ constraintExpr_free(e1);
+ constraintExpr_free(e2);
+ return TRUE;
+ }
+ }
+ DPRINTF(("Can't Get value"));
+
+ constraintExpr_free(e1);
+ constraintExpr_free(e2);
+ return FALSE;
+ }
+
+ if (constraintExpr_compare (expr2, expr1) >= 0)
+ return TRUE;
+
+ return FALSE;
+ case EQ:
+ if (constraintExpr_similar (expr1, expr2) )
+ return TRUE;
+
+ return FALSE;
+ case LTE:
+ if (constraintExpr_similar (expr1, expr2) )
+ return TRUE;
+ /*@fallthrough@*/
+ case LT:
+ if (! (constraintExpr_canGetValue (expr1) &&
+ constraintExpr_canGetValue (expr2) ) )
+ {
+ constraintExpr e1, e2;
+ bool p1, p2;
+ int const1, const2;
+
+ e1 = constraintExpr_copy(expr1);
+ e2 = constraintExpr_copy(expr2);
+
+ e1 = constraintExpr_propagateConstants (e1, &p1, &const1);
+
+ e2 = constraintExpr_propagateConstants (e2, &p2, &const2);
+
+ if (p1 || p2)
+ {
+ if (!p1)
+ const1 = 0;
+
+ if (!p2)
+ const2 = 0;
+
+ if (const1 >= const2)
+ if (constraintExpr_similar (e1, e2) )
+ {
+ constraintExpr_free(e1);
+ constraintExpr_free(e2);
+ return TRUE;
+ }
+ }
+ constraintExpr_free(e1);
+ constraintExpr_free(e2);
+
+ DPRINTF(("Can't Get value"));
+ return FALSE;
+ }
+
+ if (constraintExpr_compare (expr2, expr1) <= 0)
+ return TRUE;
+
+ return FALSE;
+
+ default:
+ llcontbug((message("Unhandled case in switch: %q", arithType_print(ar1) ) ) );
+ }
+ BADEXIT;
+}
+
+static constraint constraint_searchandreplace (/*@returned@*/ constraint c, constraintExpr old, constraintExpr newExpr)
+{
+ DPRINTF (("Doing replace for lexpr") );
+ c->lexpr = constraintExpr_searchandreplace (c->lexpr, old, newExpr);
+ DPRINTF (("Doing replace for expr") );
+ c->expr = constraintExpr_searchandreplace (c->expr, old, newExpr);
+ return c;
+}
+
+bool constraint_search (constraint c, constraintExpr old) /*@*/
+{
+ bool ret;
+ ret = FALSE;
+
+ ret = constraintExpr_search (c->lexpr, old);
+ ret = ret || constraintExpr_search (c->expr, old);
+ return ret;
+}
+
+/* adjust file locs and stuff */
+static constraint constraint_adjust (/*@returned@*/ constraint substitute, /*@observer@*/ constraint old)
+{
+ fileloc loc1, loc2, loc3;
+
+ DPRINTF ((message("Start adjust on %s and %s", constraint_print(substitute),
+ constraint_print(old))
+ ));
+
+ loc1 = constraint_getFileloc (old);
+ loc2 = constraintExpr_getFileloc (substitute->lexpr);
+ loc3 = constraintExpr_getFileloc (substitute->expr);
+
+ /* special case of an equality that "contains itself" */
+ if (constraintExpr_search (substitute->expr, substitute->lexpr) )
+ if (fileloc_closer (loc1, loc3, loc2))
+ {
+ constraintExpr temp;
+ DPRINTF ((message("Doing adjust on %s", constraint_print(substitute) )
+ ));
+ temp = substitute->lexpr;
+ substitute->lexpr = substitute->expr;
+ substitute->expr = temp;
+ substitute = constraint_simplify(substitute);
+ }
+
+ fileloc_free (loc1);
+ fileloc_free (loc2);
+ fileloc_free (loc3);
+
+ return substitute;
+
+}
+
+/* If function preforms substitutes based on inequality
+
+ It uses the rule x >= y && b < y ===> x >= b + 1
+
+ Warning this is sound but throws out information
+ */
+
+constraint inequalitySubstitute (/*@returned@*/ constraint c, constraintList p)
+{
+ if (c->ar != GTE)
+ return c;
+
+ constraintList_elements (p, el)
+ {
+ if ((el->ar == LT ) )
+ /* if (!constraint_conflict (c, el) ) */ /*@i523 explain this! */
+ {
+ constraintExpr temp2;
+
+ /*@i22*/
+
+ if (constraintExpr_same (el->expr, c->expr) )
+ {
+ DPRINTF((message ("inequalitySubstitute Replacing %q in %q with %q",
+ constraintExpr_print (c->expr),
+ constraint_print (c),
+ constraintExpr_print (el->expr) )
+ ));
+ temp2 = constraintExpr_copy (el->lexpr);
+ constraintExpr_free(c->expr);
+ c->expr = constraintExpr_makeIncConstraintExpr (temp2);
+
+ }
+
+ }
+ }
+ end_constraintList_elements;
+
+ c = constraint_simplify(c);
+ return c;
+}
+
+
+/* drl7x 7/26/001
+
+ THis function is like inequalitySubstitute but it adds the rule
+ added the rules x >= y && y <= b ===> x >= b
+ x >= y && y < b ===> x >= b + 1
+
+ This is sound but sonce it throws out additional information it should only one used
+ if we're oring constraints.
+ */
+
+static constraint inequalitySubstituteStrong (/*@returned@*/ constraint c, constraintList p)
+{
+ DPRINTF (( message ("inequalitySubstituteStrong examining substituting for %q", constraint_print(c) ) ));
+
+ if (c->ar != GTE)
+ return c;
+
+ DPRINTF (( message ("inequalitySubstituteStrong examining substituting for %q with %q",
+ constraint_print(c), constraintList_print(p) ) ));
+ constraintList_elements (p, el)
+ {
+ DPRINTF (( message ("inequalitySubstituteStrong examining substituting %s on %s", constraint_print(el), constraint_print(c) ) ));
+
+ if ((el->ar == LT ) || (el->ar == LTE ) )
+ /* if (!constraint_conflict (c, el) ) */ /*@i523@*/
+ {
+ constraintExpr temp2;
+
+ /*@i22*/
+
+ if (constraintExpr_same (el->lexpr, c->expr) )
+ {
+ DPRINTF((message ("inequalitySubstitute Replacing %s in %s with %s",
+ constraintExpr_print (c->expr),
+ constraint_print (c),
+ constraintExpr_print (el->expr) )
+ ));
+ temp2 = constraintExpr_copy (el->expr);
+ constraintExpr_free(c->expr);
+ if ((el->ar == LTE ) )
+ {
+ c->expr = temp2;
+ }
+ else
+ {
+ c->expr = constraintExpr_makeIncConstraintExpr (temp2);
+ }
+ }
+
+ }
+ }
+ end_constraintList_elements;
+
+ c = constraint_simplify(c);
+ return c;
+}
+
+
+/* This function performs substitutions based on the rule:
+ for a constraint of the form expr1 >= expr2; a < b =>
+ a = b -1 for all a in expr1. This will work in most cases.
+
+ Like inequalitySubstitute we're throwing away some information
+*/
+
+static constraint inequalitySubstituteUnsound (/*@returned@*/ constraint c, constraintList p)
+{
+ DPRINTF (( message ("Doing inequalitySubstituteUnsound " ) ));
+
+ if (c->ar != GTE)
+ return c;
+
+ constraintList_elements (p, el)
+ {
+ DPRINTF (( message ("inequalitySubstituteUnsound examining substituting %s on %s", constraint_print(el), constraint_print(c) ) ));
+ if (( el->ar == LTE) || (el->ar == LT) )
+ /* if (!constraint_conflict (c, el) ) */ /*@i532@*/
+ {
+ constraintExpr temp2;
+
+ temp2 = constraintExpr_copy (el->expr);
+
+ if (el->ar == LT)
+ temp2 = constraintExpr_makeDecConstraintExpr (temp2);
+
+ DPRINTF((message ("Replacing %s in %s with %s",
+ constraintExpr_print (el->lexpr),
+ constraintExpr_print (c->lexpr),
+ constraintExpr_print (temp2) ) ));
+
+ c->lexpr = constraintExpr_searchandreplace (c->lexpr, el->lexpr, temp2);
+ constraintExpr_free(temp2);
+ }
+ }
+ end_constraintList_elements;
+
+ c = constraint_simplify(c);
+ return c;
+}
+
+/*@only@*/ constraint constraint_substitute (/*@observer@*/ /*@temp@*/ constraint c, constraintList p)
+{
+ constraint ret;
+
+ ret = constraint_copy(c);
+ constraintList_elements (p, el)
+ {
+ if ( el->ar == EQ)
+ if (!constraint_conflict (ret, el) )
+
+ {
+ constraint temp;
+
+ temp = constraint_copy(el);
+
+ temp = constraint_adjust(temp, ret);
+
+ DPRINTF((message ("constraint_substitute :: Substituting in %s using %s",
+ constraint_print (ret), constraint_print (temp)
+ ) ) );
+
+
+ ret = constraint_searchandreplace (ret, temp->lexpr, temp->expr);
+ DPRINTF(( message (" constraint_substitute :: The new constraint is %s", constraint_print (ret) ) ));
+ constraint_free(temp);
+ }
+ }
+ end_constraintList_elements;
+
+ ret = constraint_simplify(ret);
+
+ DPRINTF(( message (" constraint_substitute :: The final new constraint is %s", constraint_print (ret) ) ));
+
+ return ret;
+}
+
+
+/*@only@*/ constraintList constraintList_substituteFreeTarget (/*@only@*/ constraintList target, /*@observer@*/ constraintList subList)
+{
+constraintList ret;
+
+ret = constraintList_substitute (target, subList);
+
+constraintList_free(target);
+
+return ret;
+}
+
+/* we try to do substitutions on each constraint in target using the constraint in sublist*/
+
+/*@only@*/ constraintList constraintList_substitute (constraintList target,/*2observer@*/ constraintList subList)
+{
+
+ constraintList ret;
+
+ ret = constraintList_makeNew();
+
+ constraintList_elements(target, el)
+ {
+ constraint temp;
+ /* drl possible problem : warning make sure that a side effect is not expected */
+
+ temp = constraint_substitute(el, subList);
+ ret = constraintList_add (ret, temp);
+ }
+ end_constraintList_elements;
+
+ return ret;
+}
+
+static constraint constraint_solve (/*@returned@*/ constraint c)
+{
+ DPRINTF((message ("Solving %s\n", constraint_print(c) ) ) );
+ c->expr = constraintExpr_solveBinaryExpr (c->lexpr, c->expr);
+ DPRINTF((message ("Solved and got %s\n", constraint_print(c) ) ) );
+
+ return c;
+}
+
+static arithType flipAr (arithType ar)
+{
+ switch (ar)
+ {
+ case LT:
+ return GT;
+ case LTE:
+ return GTE;
+ case EQ:
+ return EQ;
+ case GT:
+ return LT;
+ case GTE:
+ return LTE;
+ default:
+ llcontbug (message("unexpected value: case not handled"));
+ }
+ BADEXIT;
+}
+
+static constraint constraint_swapLeftRight (/*@returned@*/ constraint c)
+{
+ constraintExpr temp;
+ c->ar = flipAr (c->ar);
+ temp = c->lexpr;
+ c->lexpr = c->expr;
+ c->expr = temp;
+ DPRINTF(("Swaped left and right sides of constraint"));
+ return c;
+}
+
+
+
+constraint constraint_simplify ( /*@returned@*/ constraint c)
+{
+
+ DPRINTF(( message("constraint_simplify on %q ", constraint_print(c) ) ));
+
+ if (constraint_tooDeep(c))
+ {
+ DPRINTF(( message("constraint_simplify: constraint to complex aborting %q ", constraint_print(c) ) ));
+ return c;
+
+ }
+