5 # include <ctype.h> /* for isdigit */
6 # include "lclintMacros.nf"
9 # include "cgrammar_tokens.h"
11 # include "exprChecks.h"
12 # include "aliasChecks.h"
13 # include "exprNodeSList.h"
14 # include "exprData.i"
17 /*@notnull@*/ constraintList constraintList_new () {
20 ret = dmalloc ( sizeof (constraintList_) );
21 llassert ( ret != NULL);
22 ret->numconstraints = 0;
25 bool checkrestriction (int value, arithType at, exprNode expr2)
29 case LT: return (value < multiVal_forceInt ( expr2->val) );
30 case LTE: return (value <= multiVal_forceInt ( expr2->val) );
31 case GT: return (value > multiVal_forceInt ( expr2->val) );
32 case GTE: return (value >= multiVal_forceInt ( expr2->val) );
33 case EQ: return (value == multiVal_forceInt ( expr2->val) );
34 case NONNEGATIVE: return (value >= 0);
35 case POSITIVE: return (value > 0);
36 default: llassert (FALSE);
39 bool numericalResolve (constraint c)
45 if (c.expr1 && c.expr1->sref)
46 return checkrestriction (c.expr1->sref->bufinfo.size, c.restriction, c.expr2);
50 if (c.expr1 && c.expr1->sref)
51 return checkrestriction (c.expr1->sref->bufinfo.len, c.restriction, c.expr2);
54 case VALUE: return checkrestriction (multiVal_forceInt (c.expr1->val), c.restriction, c.expr2);
55 case CALLSAFE: printf("NOt IMplemented !!!");
56 default: llassert(FALSE);
61 cstring parse_restriction (arithType at)
66 case LTE: return "<=";
68 case GTE: return ">=";
70 case NONNEGATIVE: return " >= 0";
71 case POSITIVE: return " > 0";
72 default: return "unknown";
75 cstring constraint_parseKind (constraintType kind)
79 case BUFFSIZE: return "BufferSize";
80 case STRINGLEN: return "StringLength";
81 case VALUE: return "value";
82 case CALLSAFE: return "call safe";
83 default: return "unknown";
87 void constraintList_debugPrint ( char * s )
92 void constraint_print (constraint c)
97 snprintf (temp, sizeof(temp),"Location:%s \n Constraint: %s of %s %s %s\n",
98 fileloc_unparse(exprNode_getfileloc (c.expr1 ) ),
99 constraint_parseKind (c.kind),
100 exprNode_unparse(c.expr1), parse_restriction(c.restriction), exprNode_unparse(c.expr2) );
102 constraintList_debugPrint (temp);
105 void constraintList_print (constraintList cl)
109 if (constraintList_isUndefined (cl) )
111 constraintList_debugPrint("Constraint List undefined\n");
114 for (i = 0; i < cl->numconstraints; i++)
116 constraint_print (cl->constraints[i]);
121 bool constraint_resolve (constraint c)
123 if (c.kind == CALLSAFE)
126 constraintList_debugPrint("can't resolve\n");
131 return numericalResolve (c);
134 void constraintList_resolve (constraintList cl)
137 if (constraintList_isUndefined (cl) )
139 constraintList_debugPrint("Constraint List empty \n");
142 for (i = 0; i < cl->numconstraints; i++)
144 constraintList_debugPrint("Trying to resolve:\n");
145 constraint_print (cl->constraints[i]);
146 if ( constraint_resolve (cl->constraints[i] ) )
147 constraintList_debugPrint ("resolve sucessfully\n");
149 constraintList_debugPrint ("not resolved sucessfully\n");
153 constraint constraint_create (exprNode e1, exprNode e2, arithType restriction, constraintType kind)
158 ret.restriction = restriction;
163 constraintList constraintList_get (exprNode e1 )
165 return e1->constraints;
168 constraintList constraintList_exprNodemerge (exprNode e1, exprNode e2)
171 if ( (e1 != NULL) && (e2 != NULL) )
173 ret = constraintList_merge (e1->constraints, e2->constraints);
175 else if ( (e1 == NULL) && (e2 == NULL) )
176 ret = constraintList_merge ( (constraintList)NULL, (constraintList)NULL );
178 ret = constraintList_merge ( (constraintList)NULL, e2->constraints);
180 ret = constraintList_merge (e1->constraints, (constraintList)NULL );
185 constraintList constraintList_merge (constraintList cl1, constraintList cl2)
189 ret = constraintList_undefined;
190 if (constraintList_isDefined (cl1) )
192 for (i = 0; i < cl1->numconstraints; i++)
194 ret = constraintList_add (ret, cl1->constraints[i]);
197 if (constraintList_isDefined (cl2) )
199 for (i = 0; i < cl2->numconstraints; i++)
201 ret = constraintList_add (ret, cl2->constraints[i]);
209 constraintList constraintList_add (constraintList constraints, constraint newconstr)
213 if ( constraintList_isUndefined(constraints) )
215 ret = constraintList_new ();
221 llassert (constraintList_isDefined (ret) );
222 llassert (ret->numconstraints < max_constraints);
223 ret->constraints[ret->numconstraints] = newconstr;
224 ret->numconstraints++;
228 cstring exprNode_generateConstraints (exprNode e)
233 ret = exprNode_findConstraints(e);
236 ret = exprNode_justUnparse (e);
238 llassert(ret != NULL);
240 exprNode_constraintPropagateUp(e);
243 /* handels multiple statements */
247 static cstring exprNode_findConstraints ( exprNode e)
252 if (exprNode_isError (e))
254 static /*@only@*/ cstring error = cstring_undefined;
256 if (!cstring_isDefined (error))
258 error = cstring_makeLiteral ("<error>");
269 ret = message ("%s(%q)",
270 exprNode_generateConstraints (exprData_getFcn (data)),
271 exprNodeList_unparse (exprData_getArgs (data)));
272 constraintList_debugPrint(ret);
273 e->constraints = constraintList_add (e->constraints, constraint_create (e,exprNode_undefined, GT, CALLSAFE ) );
276 ret = message ("%s[%s]", exprNode_generateConstraints (exprData_getPairA (data)),
277 exprNode_generateConstraints (exprData_getPairB (data)));
279 e->constraints = constraintList_add (e->constraints, constraint_create (exprData_getPairA (data),exprData_getPairB (data) , GT, BUFFSIZE ) );
280 e->constraints = constraintList_add (e->constraints, constraint_create (exprData_getPairB (data), exprNode_undefined, NONNEGATIVE, VALUE) );
281 /* crude test to see if this is an lvalue */
282 if ( sRefSet_isEmpty(e->sets) )
284 /* if its not an lvalue we assume it's an rvalue*/
285 /* of course if its am lvalue we assume its not an rvalue
286 should put in a more accurate test sometime...*/
288 // printf("Making constraint that length %s > %s\n",exprNode_generateConstraints (exprData_getPairA (data)),
289 // exprNode_generateConstraints (exprData_getPairB (data)));
290 e->constraints = constraintList_add (e->constraints, constraint_create (exprData_getPairA (data),exprData_getPairB (data) , GT, STRINGLEN ) );
294 ret = message ("%s%s",
295 lltok_unparse (exprData_getUopTok (data)),
296 exprNode_generateConstraints (exprData_getUopNode (data)));
297 /* store old constraints */
298 e->constraints = constraintList_exprNodemerge (exprData_getUopNode (e->edata), exprNode_undefined);
299 /*handle * pointer access */
300 if (lltok_isMult( exprData_getUopTok (data) ) )
302 e->constraints = constraintList_add (e->constraints, constraint_create (exprData_getUopNode (data), exprNode_undefined, POSITIVE, BUFFSIZE ) );
303 /* crude test to see if this is an lvalue */
304 if ( sRefSet_isEmpty(e->sets) )
306 /* if its not an lvalue we assume it's an rvalue*/
307 /* of course if its am lvalue we assume its not an rvalue
308 should put in a more accurate test sometime...*/
309 e->constraints = constraintList_add (e->constraints, constraint_create (exprData_getUopNode (data), exprNode_undefined, POSITIVE, STRINGLEN ) );
315 ret = message ("%s%s",
316 exprNode_generateConstraints (exprData_getUopNode (data)),
317 lltok_unparse (exprData_getUopTok (data)));
318 e->constraints = constraintList_exprNodemerge (exprData_getUopNode (e->edata), exprNode_undefined);
319 if (lltok_isInc_Op (exprData_getUopTok (data) ) )
321 TPRINTF(("++ -- will be implemented later"));
322 // e->constraints = constraintList_add( e->constraints,
323 // constraint_makeInc_Op (exprData_getUopNode (data) ) );
327 TPRINTF(("no special constraint generation"));
334 cstring exprNode_handleError( exprNode e)
336 if (exprNode_isError (e))
338 static /*@only@*/ cstring error = cstring_undefined;
340 if (!cstring_isDefined (error))
342 error = cstring_makeLiteral ("<error>");
350 cstring exprNode_multiStatement (exprNode e)
356 if (exprNode_handleError (e))
358 return exprNode_handleError(e);
367 ret = message ("%s %s",
368 exprNode_generateConstraints (exprData_getPairA (data)),
369 exprNode_generateConstraints (exprData_getPairB (data)));
373 ret = message ("for (%s; %s; %s)",
374 exprNode_generateConstraints (exprData_getTripleInit (data)),
375 exprNode_generateConstraints (exprData_getTripleTest (data)),
376 exprNode_generateConstraints (exprData_getTripleInc (data)));
382 cstring exprNode_exprParse (exprNode e)
388 if (exprNode_handleError (e))
390 return exprNode_handleError(e);
398 ret = message ("(%s)", exprNode_generateConstraints (exprData_getUopNode (e->edata)));
399 e->constraints = constraintList_exprNodemerge (exprData_getUopNode (e->edata), exprNode_undefined);
402 ret = message ("%s %s %s",
403 exprNode_generateConstraints (exprData_getOpA (data)),
404 lltok_unparse (exprData_getOpTok (data)),
405 exprNode_generateConstraints (exprData_getOpB (data)));
406 e->constraints = constraintList_exprNodemerge (exprData_getOpA (data), exprData_getOpB (data) );
409 ret = message ("(%s)", exprNode_generateConstraints (exprData_getUopNode (e->edata)));
410 e->constraints = constraintList_exprNodemerge (exprData_getUopNode (e->edata), exprNode_undefined);
413 ret = message ("%s %s %s",
414 exprNode_generateConstraints (exprData_getOpA (data)),
415 lltok_unparse (exprData_getOpTok (data)),
416 exprNode_generateConstraints (exprData_getOpB (data)));
417 e->constraints = constraintList_exprNodemerge (exprData_getOpA (data), exprData_getOpB (data));
420 ret = message ("sizeof(%s)", ctype_unparse (qtype_getType (exprData_getType (data))));
424 ret = message ("sizeof(%s)", exprNode_generateConstraints (exprData_getSingle (data)));
425 e->constraints = constraintList_exprNodemerge (exprData_getSingle (e->edata), exprNode_undefined);
431 cstring exprNode_justUnparse (exprNode e)
437 if (exprNode_isError (e))
439 static /*@only@*/ cstring error = cstring_undefined;
441 if (!cstring_isDefined (error))
443 error = cstring_makeLiteral ("<error>");
454 ret = message ("%s(%q)",
455 exprNode_generateConstraints (exprData_getFcn (data)),
456 exprNodeList_unparse (exprData_getArgs (data)));
457 constraintList_debugPrint(ret);
458 e->constraints = constraintList_add (e->constraints, constraint_create (e,exprNode_undefined, GT, CALLSAFE ) );
461 ret = message ("Not Handled");
464 ret = message ("Not Handled");
467 ret = message ("%s:", exprData_getId (data));
471 ret = cstring_copy (exprData_getId (data));
474 ret = message ("Not handled");
498 ret = message ("goto %s", exprData_getLiteral (data));
502 ret = cstring_makeLiteral ("continue");
506 ret = cstring_makeLiteral ("break");
510 ret = message ("return %s", exprNode_generateConstraints (exprData_getSingle (data)));
514 ret = cstring_makeLiteral ("return");
518 ret = message ("%s, %s",
519 exprNode_generateConstraints (exprData_getPairA (data)),
520 exprNode_generateConstraints (exprData_getPairB (data)));
524 ret = message ("%s ? %s : %s",
525 exprNode_generateConstraints (exprData_getTriplePred (data)),
526 exprNode_generateConstraints (exprData_getTripleTrue (data)),
527 exprNode_generateConstraints (exprData_getTripleFalse (data)));
530 ret = message ("if (%s) %s",
531 exprNode_generateConstraints (exprData_getPairA (data)),
532 exprNode_generateConstraints (exprData_getPairB (data)));
533 e->constraints = constraintList_exprNodemerge (exprData_getPairA (data),exprData_getPairB(data));
537 ret = message ("if (%s) %s else %s",
538 exprNode_generateConstraints (exprData_getTriplePred (data)),
539 exprNode_generateConstraints (exprData_getTripleTrue (data)),
540 exprNode_generateConstraints (exprData_getTripleFalse (data)));
543 ret = message ("while (%s) %s",
544 exprNode_generateConstraints (exprData_getPairA (data)),
545 exprNode_generateConstraints (exprData_getPairB (data)));
546 e->constraints = constraintList_exprNodemerge (exprData_getPairA (data), exprData_getPairB (data) );
550 ret = cstring_copy (exprNode_generateConstraints (exprData_getSingle (data)));
554 ret = cstring_copy (lltok_unparse (exprData_getTok (data)));
558 ret = message ("do { %s } while (%s)",
559 exprNode_generateConstraints (exprData_getPairB (data)),
560 exprNode_generateConstraints (exprData_getPairA (data)));
564 ret = message ("{ %s }", exprNode_generateConstraints (exprData_getSingle (data)));
565 e->constraints = (exprData_getSingle (data))->constraints;
569 ret = cstring_copy (exprNode_generateConstraints (exprData_getSingle (data)));
570 e->constraints = (exprData_getSingle (data))->constraints;
574 ret = message ("%s; %s",
575 exprNode_generateConstraints (exprData_getPairA (data)),
576 exprNode_generateConstraints (exprData_getPairB (data)));
577 e->constraints = constraintList_exprNodemerge (exprData_getPairA (data), exprData_getPairB (data) );
582 ret = cstring_makeLiteral ("default:");
586 ret = message ("switch (%s) %s",
587 exprNode_generateConstraints (exprData_getPairA (data)),
588 exprNode_generateConstraints (exprData_getPairB (data)));
593 ret = message ("case %s:",
594 exprNode_generateConstraints (exprData_getSingle (data)));
598 ret = message ("%s = %s",
599 idDecl_getName (exprData_getInitId (data)),
600 exprNode_generateConstraints (exprData_getInitNode (data)));
604 ret = message ("%s.%s",
605 exprNode_generateConstraints (exprData_getFieldNode (data)),
606 exprData_getFieldName (data));
610 ret = message ("%s->%s",
611 exprNode_generateConstraints (exprData_getFieldNode (data)),
612 exprData_getFieldName (data));
615 case XPR_STRINGLITERAL:
616 ret = cstring_copy (exprData_getLiteral (data));
620 ret = cstring_copy (exprData_getLiteral (data));
624 ret = cstring_makeLiteral ("<node>");
631 void exprNode_constraintPropagateUp (exprNode e)
637 if (exprNode_isError (e))
639 static /*@only@*/ cstring error = cstring_undefined;
641 if (!cstring_isDefined (error))
643 error = cstring_makeLiteral ("<error>");
654 e->constraints = constraintList_exprNodemerge (exprData_getUopNode (e->edata), exprNode_undefined);
657 e->constraints = constraintList_exprNodemerge (exprData_getOpA (data), exprData_getOpB (data) );
660 e->constraints = constraintList_add (e->constraints, constraint_create (e,exprNode_undefined, GT, CALLSAFE ) );
663 //ret = message ("{ %q }", exprNodeList_unparse (exprData_getArgs (data)));
664 // e->constraints = constraintList_exprNodemerge (exprData_getArgs (data), exprData_getOpB (data) );
668 ret = message ("%s %s %s",
669 exprNode_generateConstraints (exprData_getOpA (data)),
670 lltok_unparse (exprData_getOpTok (data)),
671 exprNode_generateConstraints (exprData_getOpB (data)));
672 e->constraints = constraintList_exprNodemerge (exprData_getOpA (data), exprData_getOpB (data));
676 e->constraints = constraintList_exprNodemerge (exprData_getSingle (e->edata), exprNode_undefined);
680 e->constraints = constraintList_exprNodemerge (exprData_getCastNode (data), exprNode_undefined);
684 // ret = message ("%q(%q)",
685 // uentry_getName (exprData_getIterCallIter (data)),
686 // exprNodeList_unparse (exprData_getIterCallArgs (data)));
687 //// e->constraints = constraintList_exprNodemerge (exprData_getIterCallArgs (data), exprNode_undefined);
690 TPRINTF(("XPR_ITER NOT IMPLEMENTED" ));
691 /* ret = message ("%q(%q) %s %q", */
692 /* uentry_getName (exprData_getIterSname (data)), */
693 /* exprNodeList_unparse (exprData_getIterAlist (data)), */
694 /* exprNode_generateConstraints (exprData_getIterBody (data)), */
695 /* uentry_getName (exprData_getIterEname (data))); */
698 e->constraints = constraintList_exprNodemerge (exprData_getCastNode (data), exprNode_undefined);
702 TPRINTF(("NOT Currently IMplemented"));
708 /* ret = message ("%s %s", */
709 /* exprNode_generateConstraints (exprData_getPairA (data)), */
710 /* exprNode_generateConstraints (exprData_getPairB (data))); */
713 /* case XPR_FORPRED: */
714 /* ret = message ("for (%s; %s; %s)", */
715 /* exprNode_generateConstraints (exprData_getTripleInit (data)), */
716 /* exprNode_generateConstraints (exprData_getTripleTest (data)), */
717 /* exprNode_generateConstraints (exprData_getTripleInc (data))); */
721 /* ret = message ("goto %s", exprData_getLiteral (data)); */
724 /* case XPR_CONTINUE: */
725 /* ret = cstring_makeLiteral ("continue"); */
728 /* case XPR_BREAK: */
729 /* ret = cstring_makeLiteral ("break"); */
732 /* case XPR_RETURN: */
733 /* ret = message ("return %s", exprNode_generateConstraints (exprData_getSingle (data))); */
736 /* case XPR_NULLRETURN: */
737 /* ret = cstring_makeLiteral ("return"); */
740 /* case XPR_COMMA: */
741 /* ret = message ("%s, %s", */
742 /* exprNode_generateConstraints (exprData_getPairA (data)), */
743 /* exprNode_generateConstraints (exprData_getPairB (data))); */
747 /* ret = message ("%s ? %s : %s", */
748 /* exprNode_generateConstraints (exprData_getTriplePred (data)), */
749 /* exprNode_generateConstraints (exprData_getTripleTrue (data)), */
750 /* exprNode_generateConstraints (exprData_getTripleFalse (data))); */
753 /* ret = message ("if (%s) %s", */
754 /* exprNode_generateConstraints (exprData_getPairA (data)), */
755 /* exprNode_generateConstraints (exprData_getPairB (data))); */
756 /* e->constraints = constraintList_exprNodemerge (exprData_getPairA (data),exprData_getPairB(data)); */
759 /* case XPR_IFELSE: */
760 /* ret = message ("if (%s) %s else %s", */
761 /* exprNode_generateConstraints (exprData_getTriplePred (data)), */
762 /* exprNode_generateConstraints (exprData_getTripleTrue (data)), */
763 /* exprNode_generateConstraints (exprData_getTripleFalse (data))); */
765 /* case XPR_WHILE: */
766 /* ret = message ("while (%s) %s", */
767 /* exprNode_generateConstraints (exprData_getPairA (data)), */
768 /* exprNode_generateConstraints (exprData_getPairB (data))); */
769 /* e->constraints = constraintList_exprNodemerge (exprData_getPairA (data), exprData_getPairB (data) ); */
772 /* case XPR_WHILEPRED: */
773 /* ret = cstring_copy (exprNode_generateConstraints (exprData_getSingle (data))); */
777 /* ret = cstring_copy (lltok_unparse (exprData_getTok (data))); */
780 /* case XPR_DOWHILE: */
781 /* ret = message ("do { %s } while (%s)", */
782 /* exprNode_generateConstraints (exprData_getPairB (data)), */
783 /* exprNode_generateConstraints (exprData_getPairA (data))); */
786 /* case XPR_BLOCK: */
787 /* ret = message ("{ %s }", exprNode_generateConstraints (exprData_getSingle (data))); */
788 /* e->constraints = (exprData_getSingle (data))->constraints; */
792 /* ret = cstring_copy (exprNode_generateConstraints (exprData_getSingle (data))); */
793 /* e->constraints = (exprData_getSingle (data))->constraints; */
796 /* case XPR_STMTLIST: */
797 /* ret = message ("%s; %s", */
798 /* exprNode_generateConstraints (exprData_getPairA (data)), */
799 /* exprNode_generateConstraints (exprData_getPairB (data))); */
800 /* e->constraints = constraintList_exprNodemerge (exprData_getPairA (data), exprData_getPairB (data) ); */
803 /* case XPR_FTDEFAULT: */
804 /* case XPR_DEFAULT: */
805 /* ret = cstring_makeLiteral ("default:"); */
808 /* case XPR_SWITCH: */
809 /* ret = message ("switch (%s) %s", */
810 /* exprNode_generateConstraints (exprData_getPairA (data)), */
811 /* exprNode_generateConstraints (exprData_getPairB (data))); */
814 /* case XPR_FTCASE: */
816 /* ret = message ("case %s:", */
817 /* exprNode_generateConstraints (exprData_getSingle (data))); */
821 /* ret = message ("%s = %s", */
822 /* idDecl_getName (exprData_getInitId (data)), */
823 /* exprNode_generateConstraints (exprData_getInitNode (data))); */
826 /* case XPR_FACCESS: */
827 /* ret = message ("%s.%s", */
828 /* exprNode_generateConstraints (exprData_getFieldNode (data)), */
829 /* exprData_getFieldName (data)); */
832 /* case XPR_ARROW: */
833 /* ret = message ("%s->%s", */
834 /* exprNode_generateConstraints (exprData_getFieldNode (data)), */
835 /* exprData_getFieldName (data)); */
838 /* case XPR_STRINGLITERAL: */
839 /* ret = cstring_copy (exprData_getLiteral (data)); */
842 /* case XPR_NUMLIT: */
843 /* ret = cstring_copy (exprData_getLiteral (data)); */
847 /* ret = cstring_makeLiteral ("<node>"); */