]>
Commit | Line | Data |
---|---|---|
d0e5b01f | 1 | /* |
2 | ** LCLint - annotation-assisted static program checker | |
3 | ** Copyright (C) 1994-2000 University of Virginia, | |
4 | ** Massachusetts Institute of Technology | |
5 | ** | |
6 | ** This program is free software; you can redistribute it and/or modify it | |
7 | ** under the terms of the GNU General Public License as published by the | |
8 | ** Free Software Foundation; either version 2 of the License, or (at your | |
9 | ** option) any later version. | |
10 | ** | |
11 | ** This program is distributed in the hope that it will be useful, but | |
12 | ** WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | ** General Public License for more details. | |
15 | ** | |
16 | ** The GNU General Public License is available from http://www.gnu.org/ or | |
17 | ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
18 | ** MA 02111-1307, USA. | |
19 | ** | |
20 | ** For information on lclint: lclint-request@cs.virginia.edu | |
21 | ** To report a bug: lclint-bug@cs.virginia.edu | |
22 | ** For more information: http://lclint.cs.virginia.edu | |
23 | */ | |
24 | /* | |
25 | ** environmentTable.c | |
26 | */ | |
27 | ||
28 | # include "lclintMacros.nf" | |
29 | # include "basic.h" | |
30 | ||
31 | //#include "environmentTable.h" | |
4cccc6ad | 32 | #include "exprData.i" |
33 | #include "exprData.h" | |
34 | //#include "exprNode.h" | |
d0e5b01f | 35 | |
4cccc6ad | 36 | /*@i777*/ |
37 | /*@-fcnuse*/ | |
38 | /*@ignore@*/ | |
d0e5b01f | 39 | /*@constant int ATINVALID; @*/ |
40 | # define ATINVALID -1 | |
41 | ||
42 | #define ENVIRONMENTSEARCHLIMIT ALIASSEARCHLIMIT | |
43 | #define FLG_GLOBENVIRONMENT FLG_GLOBALIAS | |
44 | #define NOENVIRONMENT NOALIAS | |
45 | ||
46 | static sRefSet | |
47 | environmentTable_canEnvironmentAux (environmentTable p_s, sRef p_sr, int p_lim) /*@*/ ; | |
48 | static sRefSet | |
49 | environmentTable_aliasedByLimit (environmentTable p_s, sRef p_sr, int p_lim) /*@*/ ; | |
50 | static sRefSet | |
51 | environmentTable_aliasedByAux (environmentTable p_s, sRef p_sr, int p_lim) /*@*/ ; | |
52 | ||
4cccc6ad | 53 | static /*@only@*/ sRefSet environmentTable_environmentedByLimit (environmentTable p_s, sRef p_sr, int p_lim) ; |
54 | ||
d0e5b01f | 55 | environmentTable |
56 | environmentTable_new () | |
57 | { | |
58 | return (environmentTable_undefined); | |
59 | } | |
60 | ||
4cccc6ad | 61 | environmentTable |
62 | environmentTable_insertRelativeRange (/*@returned@*/ environmentTable p_s, | |
63 | /*@exposed@*/ sRef p_sr, | |
64 | int p_min, int p_max); | |
65 | ||
66 | ||
d0e5b01f | 67 | static /*@only@*/ /*@notnull@*/ environmentTable |
68 | environmentTable_newEmpty (void) | |
69 | { | |
70 | environmentTable s = (environmentTable) dmalloc (sizeof (*s)); | |
71 | ||
72 | s->nelements = 0; | |
73 | s->nspace = environmentTableBASESIZE; | |
74 | s->keys = (sRef *) dmalloc (sizeof (*s->keys) * environmentTableBASESIZE); | |
75 | s->values = (sRefSet *) dmalloc (sizeof (*s->values) * environmentTableBASESIZE); | |
76 | s->rangeValues = (rangeAt*) dmalloc (sizeof (*s->rangeValues) * environmentTableBASESIZE); | |
77 | return (s); | |
78 | } | |
79 | ||
80 | static void | |
81 | environmentTable_grow (/*@notnull@*/ environmentTable s) | |
82 | { | |
83 | int i; | |
84 | o_sRefSet *oldvalues = s->values; | |
85 | sRef *oldkeys = s->keys; | |
86 | rangeAt *oldranges = s->rangeValues; | |
87 | ||
88 | s->nspace += environmentTableBASESIZE; | |
89 | ||
90 | s->values = (sRefSet *) dmalloc (sizeof (*s->values) | |
91 | * (s->nelements + s->nspace)); | |
92 | s->keys = (sRef *) dmalloc (sizeof (*s->keys) * (s->nelements + environmentTableBASESIZE)); | |
93 | ||
94 | s->rangeValues = (rangeAt *) dmalloc (sizeof (*s->rangeValues) * (s->nelements + environmentTableBASESIZE)); | |
95 | ||
96 | ||
97 | if (s->keys == (sRef *) 0 || s->values == (sRefSet *)0 || s->rangeValues == (rangeAt*) 0 ) | |
98 | { | |
99 | llfatalerror (cstring_makeLiteral ("environmentTable_grow: out of memory!")); | |
100 | } | |
101 | ||
102 | for (i = 0; i < s->nelements; i++) | |
103 | { | |
104 | s->values[i] = oldvalues[i]; | |
105 | s->keys[i] = oldkeys[i]; | |
106 | s->rangeValues[i] = oldranges[i]; | |
107 | } | |
108 | // s->rangeValues[i] = dmalloc (sizeof (rangeAt)); | |
109 | sfree (oldvalues); | |
110 | sfree (oldkeys); | |
111 | sfree (oldranges); | |
112 | } | |
113 | ||
114 | ||
115 | ||
116 | static int environmentTable_lookupRefs (/*@notnull@*/ environmentTable s, sRef sr) | |
117 | { | |
118 | int i; | |
119 | ||
120 | ||
121 | for (i = 0; i < environmentTable_size (s); i++) | |
122 | { | |
123 | if (sRef_same (sr, s->keys[i])) | |
124 | { | |
125 | return i; | |
126 | } | |
127 | } | |
128 | ||
129 | return ATINVALID; | |
130 | } | |
131 | ||
132 | environmentTable | |
133 | environmentTable_postOpvar (/*@returned@*/ environmentTable s, sRef sr) | |
134 | { | |
135 | int ind; | |
136 | // printf("doing postop\n"); | |
137 | if (environmentTable_isUndefined (s) ) | |
138 | { | |
139 | s = environmentTable_newEmpty(); | |
140 | } | |
141 | ||
142 | ind = environmentTable_lookupRefs (s, sr); | |
143 | if (ind == ATINVALID) | |
144 | { | |
145 | s = environmentTable_addRelativeRange (s, sr); | |
146 | ind = s->nelements; | |
147 | } | |
148 | // assume it ++ we'll do -- later | |
149 | ||
150 | s->rangeValues[ind].max++; | |
151 | s->rangeValues[ind].min++; | |
152 | ||
153 | return s; | |
154 | } | |
155 | ||
156 | environmentTable | |
157 | environmentTable_mergeEnvironments (environmentTable s1, environmentTable s2) | |
158 | { | |
159 | int i; | |
160 | environmentTable t1; | |
161 | t1 = environmentTable_copy (s1); | |
162 | if (environmentTable_isUndefined (s2) ) | |
163 | return t1; | |
164 | ||
165 | for (i = 0; i < s2->nelements; i++) | |
166 | { | |
167 | int ind = environmentTable_lookupRefs ( t1, s1->keys[i]); | |
168 | if (s2->rangeValues[i].isRelative) | |
169 | { | |
170 | if (ind == ATINVALID) | |
171 | { | |
172 | t1 = environmentTable_insertRelativeRange(t1, s2->keys[i], s2->rangeValues[i].max, s2->rangeValues[i].min); | |
173 | } | |
174 | else | |
175 | { | |
176 | t1->rangeValues[ind].min += s2->rangeValues[i].min; | |
177 | t1->rangeValues[ind].max += s2->rangeValues[i].max; | |
178 | } | |
179 | } | |
180 | else | |
181 | { | |
182 | /* we want to overwrite old value .. */ | |
183 | t1 = environmentTable_addExactValue (t1, s2->keys[i], s2->rangeValues[i].max); | |
184 | /*should fix this to do min and max ... */ | |
185 | } | |
186 | ||
187 | } | |
188 | } | |
189 | ||
190 | rangeAt | |
191 | rangeAt_createRelativeRange () | |
192 | { | |
193 | rangeAt tmp; | |
194 | tmp.isRelative = TRUE; | |
195 | tmp.unknown = FALSE; | |
196 | tmp.max = 0; | |
197 | tmp.min = 0; | |
198 | return tmp; | |
199 | } | |
200 | ||
201 | rangeAt rangeAt_createExactRange (int min, int max) | |
202 | { | |
203 | rangeAt tmp; | |
204 | tmp.isRelative = FALSE; | |
205 | tmp.unknown = FALSE; | |
206 | tmp.min = min; | |
207 | tmp.max = max; | |
208 | return tmp; | |
209 | } | |
210 | ||
211 | environmentTable | |
212 | environmentTable_addRelativeRange (/*@returned@*/ environmentTable s, | |
213 | /*@exposed@*/ sRef sr) | |
214 | { | |
215 | int ind; | |
216 | sRefSet ss; | |
217 | rangeAt range; | |
218 | ||
219 | if (environmentTable_isUndefined (s)) | |
220 | { | |
221 | s = environmentTable_newEmpty (); | |
222 | ind = ATINVALID; | |
223 | } | |
224 | else | |
225 | { | |
226 | ind = environmentTable_lookupRefs (s, sr); | |
227 | } | |
228 | ||
229 | if (ind == ATINVALID) | |
230 | { | |
231 | if (s->nspace <= 0) { | |
232 | environmentTable_grow (s); | |
233 | } | |
234 | ||
235 | s->nspace--; | |
236 | s->keys[s->nelements] = sr; | |
237 | /*fix this */ | |
238 | // s->values[s->nelements] = sRefSet_single (al); | |
239 | ind = s->nelements; | |
240 | s->nelements++; | |
241 | } | |
242 | range = rangeAt_createRelativeRange(); | |
243 | ||
244 | s->rangeValues[ind] = range; | |
245 | return s; | |
246 | } | |
247 | ||
248 | void | |
249 | environmentTable_testInRange ( environmentTable s, /*@exposed@*/ sRef sr, int index) | |
250 | { | |
251 | int ind; | |
252 | sRefSet ss; | |
253 | rangeAt range; | |
254 | if (environmentTable_isUndefined (s)) | |
255 | { | |
256 | fprintf(stderr,"environmentTable not defined\n"); | |
257 | return; | |
258 | } | |
259 | ||
260 | ind = environmentTable_lookupRefs (s, sr); | |
261 | if (ind == ATINVALID) | |
262 | { | |
263 | fprintf (stderr,"range not known\n"); | |
264 | return; | |
265 | } | |
266 | if ( &s->rangeValues[ind] ) | |
267 | { | |
268 | if ( (s->rangeValues[ind].min <= index ) && (s->rangeValues[ind].max >= index) ) | |
269 | { | |
270 | printf("The value %d is in the range for this variable \n", index); | |
271 | } | |
272 | else | |
273 | printf("The value %d is NOT in the range for this variable \n", index); | |
274 | } | |
275 | ||
276 | } | |
277 | ||
278 | ||
279 | environmentTable | |
280 | environmentTable_addExactValue (/*@returned@*/ environmentTable s, | |
281 | /*@exposed@*/ sRef sr, | |
282 | int val) | |
283 | { | |
284 | int ind; | |
285 | sRefSet ss; | |
286 | rangeAt range; | |
287 | ||
288 | if (environmentTable_isUndefined (s)) | |
289 | { | |
290 | s = environmentTable_newEmpty (); | |
291 | ind = ATINVALID; | |
292 | } | |
293 | else | |
294 | { | |
295 | ind = environmentTable_lookupRefs (s, sr); | |
296 | } | |
297 | ||
298 | if (ind == ATINVALID) | |
299 | { | |
300 | if (s->nspace <= 0) { | |
301 | environmentTable_grow (s); | |
302 | } | |
303 | ||
304 | s->nspace--; | |
305 | s->keys[s->nelements] = sr; | |
306 | /*fix this */ | |
307 | // s->values[s->nelements] = sRefSet_single (al); | |
308 | ind = s->nelements; | |
309 | s->nelements++; | |
310 | } | |
311 | ||
312 | else | |
313 | { | |
314 | /* s->values[ind] = sRefSet_insert (s->values[ind], al); */ | |
315 | } | |
316 | /* | |
317 | if ( (s->rangeValues[ind]) == 0 ) | |
318 | { | |
319 | s->rangeValues[ind] = dmalloc(sizeof(rangeAt) ); | |
320 | } | |
321 | */ | |
322 | range.min = val; | |
323 | range.max = val; | |
324 | ||
325 | s->rangeValues[ind] = range; | |
326 | return s; | |
327 | } | |
328 | ||
329 | environmentTable | |
330 | environmentTable_insertRelativeRange (/*@returned@*/ environmentTable s, | |
331 | /*@exposed@*/ sRef sr, | |
332 | int min, int max) | |
333 | { | |
334 | int ind; | |
335 | sRefSet ss; | |
336 | rangeAt range; | |
337 | ||
338 | if (environmentTable_isUndefined (s)) | |
339 | { | |
340 | s = environmentTable_newEmpty (); | |
341 | ind = ATINVALID; | |
342 | } | |
343 | else | |
344 | { | |
345 | ind = environmentTable_lookupRefs (s, sr); | |
346 | } | |
347 | ||
348 | if (ind == ATINVALID) | |
349 | { | |
350 | if (s->nspace <= 0) { | |
351 | environmentTable_grow (s); | |
352 | } | |
353 | ||
354 | s->nspace--; | |
355 | s->keys[s->nelements] = sr; | |
356 | /*fix this */ | |
357 | // s->values[s->nelements] = sRefSet_single (al); | |
358 | ind = s->nelements; | |
359 | s->nelements++; | |
360 | } | |
361 | ||
362 | range = rangeAt_createRelativeRange(); | |
363 | range.min = min; | |
364 | range.max = max; | |
365 | ||
366 | s->rangeValues[ind] = range; | |
367 | return s; | |
368 | } | |
369 | ||
370 | environmentTable | |
371 | environmentTable_addMustAlias (/*@returned@*/ environmentTable s, | |
372 | /*@exposed@*/ sRef sr, | |
373 | sRef al) | |
374 | { | |
375 | int ind; | |
376 | sRefSet ss; | |
377 | ||
378 | llassert (NOENVIRONMENT (sr, al)); | |
4cccc6ad | 379 | /*@ignore@*/ |
d0e5b01f | 380 | if (environmentTable_isUndefined (s)) |
381 | { | |
382 | s = environmentTable_newEmpty (); | |
383 | ind = ATINVALID; | |
384 | } | |
385 | else | |
386 | { | |
387 | ind = environmentTable_lookupRefs (s, sr); | |
388 | } | |
389 | ||
390 | ss = environmentTable_canEnvironment (s, al); | |
391 | ||
392 | ||
393 | if (ind == ATINVALID) | |
394 | { | |
395 | if (s->nspace <= 0) { | |
396 | environmentTable_grow (s); | |
397 | } | |
398 | ||
399 | s->nspace--; | |
400 | s->keys[s->nelements] = sr; | |
401 | s->values[s->nelements] = sRefSet_single (al); | |
402 | ind = s->nelements; | |
403 | s->nelements++; | |
404 | } | |
405 | else | |
406 | { | |
407 | s->values[ind] = sRefSet_insert (s->values[ind], al); | |
408 | } | |
409 | ||
410 | s->values[ind] = sRefSet_unionExcept (s->values[ind], ss, s->keys[ind]); | |
411 | ||
412 | sRefSet_free (ss); | |
413 | return s; | |
414 | } | |
415 | ||
416 | static environmentTable | |
417 | environmentTable_addSet (/*@returned@*/ environmentTable s, | |
418 | /*@exposed@*/ sRef key, /*@only@*/ sRefSet value) | |
419 | { | |
420 | if (!sRefSet_isEmpty (value)) | |
421 | { | |
422 | if (environmentTable_isUndefined (s)) | |
423 | { | |
424 | s = environmentTable_newEmpty (); | |
425 | } | |
426 | else | |
427 | { | |
428 | if (s->nspace <= 0) | |
429 | { | |
430 | environmentTable_grow (s); | |
431 | } | |
432 | } | |
433 | ||
434 | s->nspace--; | |
435 | s->keys[s->nelements] = key; | |
436 | s->values[s->nelements] = value; | |
437 | s->nelements++; | |
438 | } | |
439 | else | |
440 | { | |
441 | sRefSet_free (value); | |
442 | } | |
443 | ||
444 | return s; | |
445 | } | |
446 | ||
447 | /* | |
448 | ** When environmentes are cleared: | |
449 | ** | |
450 | ** o remove all entries for sr | |
451 | ** o replace all environmentes for things which environment sr with sr's environmentes | |
452 | ** | |
453 | ** Clear environmentes for sr; if sr is a direct param reference, clear its environmentes too. | |
454 | */ | |
455 | ||
456 | static void environmentTable_clearEnvironmentesAux (/*@notnull@*/ environmentTable p_s, sRef p_sr) | |
457 | /*@modifies p_s@*/ ; | |
458 | ||
459 | void environmentTable_clearEnvironmentes (environmentTable s, sRef sr) | |
460 | { | |
461 | if (environmentTable_isUndefined (s)) | |
462 | { | |
463 | return; | |
464 | } | |
465 | else | |
466 | { | |
467 | sRef rb = sRef_getRootBase (sr); | |
468 | ||
469 | ||
470 | if (!sRef_isCvar (sr) && sRef_isLocalVar (rb)) | |
471 | { | |
472 | int ind = environmentTable_lookupRefs (s, rb); | |
473 | ||
474 | if (ind != ATINVALID) | |
475 | { | |
476 | sRefSet al = s->values[ind]; | |
477 | ||
478 | ||
479 | sRefSet_realElements (al, el) | |
480 | { | |
481 | ||
482 | if (sRef_isParam (el)) | |
483 | { | |
484 | if (sRef_sameName (el, rb)) | |
485 | { | |
486 | sRef fb = sRef_fixBase (sr, el); | |
487 | ||
488 | environmentTable_clearEnvironmentesAux (s, fb); | |
489 | } | |
490 | } | |
491 | } end_sRefSet_realElements ; | |
492 | } | |
493 | } | |
494 | ||
495 | environmentTable_clearEnvironmentesAux (s, sr); | |
496 | } | |
497 | } | |
498 | ||
499 | static | |
500 | void environmentTable_clearEnvironmentesAux (/*@notnull@*/ environmentTable s, sRef sr) | |
501 | { | |
502 | int i; | |
503 | ||
504 | for (i = 0; i < s->nelements; i++) | |
505 | { | |
506 | sRef key = s->keys[i]; | |
507 | ||
508 | if (sRef_includedBy (key, sr)) | |
509 | { | |
510 | sRefSet_clear (s->values[i]); | |
511 | } | |
512 | else | |
513 | { | |
514 | (void) sRefSet_deleteBase (s->values[i], sr); | |
515 | } | |
516 | } | |
517 | } | |
518 | ||
519 | /* | |
520 | ** returns set of all sRefs that must environment sr (but are different from sr) | |
521 | */ | |
522 | ||
523 | static /*@only@*/ sRefSet environmentTable_environmentedByAux (environmentTable s, sRef sr, int lim) | |
524 | { | |
525 | static bool hadWarning = FALSE; | |
526 | sRefSet res = sRefSet_undefined; | |
527 | int i; | |
528 | ||
529 | llassert (!sRef_isConj (sr)); | |
530 | ||
531 | ||
532 | if (environmentTable_isUndefined (s) || lim >= ENVIRONMENTSEARCHLIMIT) | |
533 | { | |
534 | if (lim >= ENVIRONMENTSEARCHLIMIT && !hadWarning) | |
535 | { | |
536 | llquietbug | |
537 | (message ("Environment search limit exceeded, checking %q. " | |
538 | "This either means there is a variable with at least " | |
539 | "%d indirections, or there is a bug in LCLint.", | |
540 | sRef_unparse (sr), | |
541 | ENVIRONMENTSEARCHLIMIT)); | |
542 | ||
543 | hadWarning = TRUE; | |
544 | } | |
545 | ||
546 | return sRefSet_undefined; | |
547 | } | |
548 | else | |
549 | { | |
550 | sRefSet abl; | |
551 | ||
552 | if (sRef_isPointer (sr)) | |
553 | { | |
554 | abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim); | |
555 | res = sRefSet_addIndirection (abl); | |
556 | } | |
557 | else if (sRef_isAddress (sr)) | |
558 | { | |
559 | abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim); | |
560 | res = sRefSet_removeIndirection (abl); | |
561 | } | |
562 | else if (sRef_isField (sr)) | |
563 | { | |
564 | abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim); | |
565 | res = sRefSet_accessField (abl, sRef_getField (sr)); | |
566 | } | |
567 | else if (sRef_isArrayFetch (sr)) | |
568 | { | |
569 | abl = environmentTable_environmentedByLimit (s, sRef_getBase (sr), lim); | |
570 | ||
571 | if (sRef_isIndexKnown (sr)) | |
572 | { | |
573 | int idx = sRef_getIndex (sr); | |
574 | ||
575 | res = sRefSet_fetchKnown (abl, idx); | |
576 | } | |
577 | else | |
578 | { | |
579 | res = sRefSet_fetchUnknown (abl); | |
580 | } | |
581 | } | |
582 | else | |
583 | { | |
584 | abl = sRefSet_undefined; | |
585 | } | |
586 | ||
587 | sRefSet_free (abl); | |
588 | } | |
589 | ||
590 | for (i = 0; i < s->nelements; i++) | |
591 | { | |
592 | sRef elem = s->keys[i]; | |
593 | ||
594 | if (!sRef_same (sr, elem)) /* was sameName */ | |
595 | { | |
596 | ||
597 | sRefSet_realElements (s->values[i], current) | |
598 | { | |
599 | ||
600 | if (sRef_similar (sr, current)) | |
601 | { | |
602 | res = sRefSet_insert (res, sRef_fixOuterRef (elem)); | |
603 | /*@innerbreak@*/ break; | |
604 | } | |
605 | } end_sRefSet_realElements; | |
606 | } | |
607 | } | |
608 | ||
609 | return res; | |
610 | } | |
611 | ||
612 | static /*@only@*/ sRefSet environmentTable_environmentedByLimit (environmentTable s, sRef sr, int lim) | |
613 | { | |
614 | sRefSet res; | |
615 | ||
616 | ||
617 | if (sRef_isConj (sr)) | |
618 | { | |
619 | res = sRefSet_unionFree (environmentTable_environmentedByLimit (s, sRef_getConjA (sr), lim), | |
620 | environmentTable_environmentedByLimit (s, sRef_getConjB (sr), lim)); | |
621 | } | |
622 | else | |
623 | { | |
624 | res = environmentTable_environmentedByAux (s, sr, lim + 1); | |
625 | } | |
626 | ||
627 | return res; | |
628 | } | |
629 | ||
630 | /*@only@*/ sRefSet environmentTable_environmentedBy (environmentTable s, sRef sr) | |
631 | { | |
632 | if (sRef_isConj (sr)) | |
633 | { | |
634 | return (sRefSet_unionFree (environmentTable_environmentedBy (s, sRef_getConjA (sr)), | |
635 | environmentTable_environmentedBy (s, sRef_getConjB (sr)))); | |
636 | } | |
637 | ||
638 | return (environmentTable_environmentedByAux (s, sr, 0)); | |
639 | } | |
640 | ||
641 | /*@only@*/ sRefSet environmentTable_canEnvironment (environmentTable s, sRef sr) | |
642 | { | |
643 | sRefSet res; | |
644 | ||
645 | ||
646 | if (sRef_isConj (sr)) | |
647 | { | |
648 | res = sRefSet_unionFree (environmentTable_canEnvironment (s, sRef_getConjA (sr)), | |
649 | environmentTable_canEnvironment (s, sRef_getConjB (sr))); | |
650 | } | |
651 | else | |
652 | { | |
653 | res = environmentTable_canEnvironmentAux (s, sr, 0); | |
654 | } | |
655 | ||
656 | return res; | |
657 | } | |
658 | ||
659 | /* | |
660 | ** need to limit the depth of environmenting searches | |
661 | */ | |
662 | ||
663 | static /*@only@*/ sRefSet environmentTable_canEnvironmentLimit (environmentTable s, sRef sr, int lim) | |
664 | { | |
665 | sRefSet res; | |
666 | ||
667 | if (sRef_isConj (sr)) | |
668 | { | |
669 | sRefSet a = environmentTable_canEnvironmentLimit (s, sRef_getConjA (sr), lim); | |
670 | sRefSet b = environmentTable_canEnvironmentLimit (s, sRef_getConjB (sr), lim); | |
671 | ||
672 | res = sRefSet_unionFree (a, b); | |
673 | } | |
674 | else | |
675 | { | |
676 | res = environmentTable_canEnvironmentAux (s, sr, lim + 1); | |
677 | } | |
678 | ||
679 | return res; | |
680 | } | |
681 | ||
682 | static /*@only@*/ sRefSet | |
683 | environmentTable_canEnvironmentAux (environmentTable s, sRef sr, int lim) | |
684 | { | |
685 | static bool hadWarning = FALSE; | |
686 | llassert (!sRef_isConj (sr)); | |
687 | ||
688 | ||
689 | if (environmentTable_isUndefined (s) || lim >= ALIASSEARCHLIMIT) | |
690 | { | |
691 | if (lim >= ALIASSEARCHLIMIT && !hadWarning) | |
692 | { | |
693 | llquietbug | |
694 | (message ("Environment search limit exceeded, checking %q. " | |
695 | "This either means there is a variable with at least " | |
696 | "%d indirections, or there is a bug in LCLint.", | |
697 | sRef_unparse (sr), | |
698 | ENVIRONMENTSEARCHLIMIT)); | |
699 | ||
700 | hadWarning = TRUE; | |
701 | } | |
702 | ||
703 | return sRefSet_undefined; | |
704 | } | |
705 | else | |
706 | { | |
707 | int ind = environmentTable_lookupRefs (s, sr); | |
708 | ||
709 | if (sRef_isPointer (sr) || sRef_isAddress (sr) || sRef_isField (sr) | |
710 | || sRef_isArrayFetch (sr)) | |
711 | { | |
712 | sRef base = sRef_getBase (sr); | |
713 | sRefSet tmp = environmentTable_canEnvironmentLimit (s, base, lim); | |
714 | sRefSet ret; | |
715 | ||
716 | if (sRef_isPointer (sr)) | |
717 | { | |
718 | ret = sRefSet_addIndirection (tmp); | |
719 | } | |
720 | else if (sRef_isAddress (sr)) | |
721 | { | |
722 | ret = sRefSet_removeIndirection (tmp); | |
723 | } | |
724 | else if (sRef_isField (sr)) | |
725 | { | |
726 | ret = sRefSet_accessField (tmp, sRef_getField (sr)); | |
727 | } | |
728 | else if (sRef_isArrayFetch (sr)) | |
729 | { | |
730 | if (sRef_isIndexKnown (sr)) | |
731 | { | |
732 | ret = sRefSet_fetchKnown (tmp, sRef_getIndex (sr)); | |
733 | } | |
734 | else | |
735 | { | |
736 | ret = sRefSet_fetchUnknown (tmp); | |
737 | } | |
738 | } | |
739 | else | |
740 | { | |
741 | BADBRANCH; | |
742 | } | |
743 | ||
744 | if (ind != ATINVALID) | |
745 | { | |
746 | ret = sRefSet_union (ret, s->values[ind]); | |
747 | } | |
748 | ||
749 | sRefSet_free (tmp); | |
750 | return ret; | |
751 | } | |
752 | ||
753 | if (ind == ATINVALID) return sRefSet_undefined; | |
754 | ||
755 | return sRefSet_newCopy (s->values[ind]); | |
756 | } | |
757 | } | |
758 | ||
759 | environmentTable environmentTable_copy (environmentTable s) | |
760 | { | |
761 | if (environmentTable_isEmpty (s)) | |
762 | { | |
763 | return environmentTable_undefined; | |
764 | } | |
765 | else | |
766 | { | |
767 | environmentTable t = (environmentTable) dmalloc (sizeof (*s)); | |
768 | int i; | |
769 | ||
770 | t->nelements = s->nelements; | |
771 | t->nspace = 0; | |
772 | t->keys = (sRef *) dmalloc (sizeof (*s->keys) * s->nelements); | |
773 | t->values = (sRefSet *) dmalloc (sizeof (*s->values) * t->nelements); | |
774 | t->rangeValues = (rangeAt *) dmalloc (sizeof (*s->rangeValues) * t->nelements); | |
775 | ||
776 | for (i = 0; i < s->nelements; i++) | |
777 | { | |
778 | t->keys[i] = s->keys[i]; | |
779 | t->values[i] = sRefSet_newCopy (s->values[i]); | |
780 | t->rangeValues[i] = s->rangeValues[i]; | |
781 | } | |
782 | ||
783 | return t; | |
784 | } | |
785 | } | |
786 | ||
787 | static void | |
788 | environmentTable_levelPrune (environmentTable s, int lexlevel) | |
789 | { | |
790 | ||
791 | ||
792 | if (environmentTable_isEmpty (s)) | |
793 | { | |
794 | return; | |
795 | } | |
796 | else | |
797 | { | |
798 | int i; | |
799 | int backcount = s->nelements - 1; | |
800 | ||
801 | for (i = 0; i <= backcount; i++) | |
802 | { | |
803 | sRef key = s->keys[i]; | |
804 | ||
805 | if (sRef_lexLevel (key) > lexlevel) | |
806 | { | |
807 | int j; | |
808 | for (j = backcount; j > i; j--) | |
809 | { | |
810 | backcount--; | |
811 | s->nelements--; | |
812 | s->nspace++; | |
813 | ||
814 | if (sRef_lexLevel (s->keys[j]) <= lexlevel) | |
815 | { | |
816 | s->keys[i] = s->keys[j]; | |
817 | s->values[i] = s->values[j]; | |
818 | sRefSet_levelPrune (s->values[i], lexlevel); | |
819 | /*@innerbreak@*/ break; | |
820 | } | |
821 | } | |
822 | if (backcount == i) | |
823 | s->nelements--; | |
824 | } | |
825 | else | |
826 | { | |
827 | sRefSet_levelPrune (s->values[i], lexlevel); | |
828 | } | |
829 | } | |
830 | } | |
831 | } | |
832 | ||
833 | /* | |
834 | ** levelUnionSeq | |
835 | ** | |
836 | ** like level union, but know that t2 was executed after t1. So if | |
837 | ** t1 has x -> { a, b } and t2 has x -> { a }, then result has x -> { a }. | |
838 | ** | |
839 | ** NOTE: t2 is "only". | |
840 | */ | |
841 | ||
842 | environmentTable environmentTable_levelUnionSeq (/*@returned@*/ environmentTable t1, | |
843 | /*@only@*/ environmentTable t2, int level) | |
844 | { | |
845 | if (environmentTable_isUndefined (t2)) | |
846 | { | |
847 | return t1; | |
848 | } | |
849 | ||
850 | if (environmentTable_isUndefined (t1)) | |
851 | { | |
852 | t1 = environmentTable_newEmpty (); | |
853 | } | |
854 | else | |
855 | { | |
856 | environmentTable_levelPrune (t1, level); | |
857 | } | |
858 | ||
859 | environmentTable_elements (t2, key, value) | |
860 | { | |
861 | if (sRef_lexLevel (key) <= level) | |
862 | { | |
863 | int ind = environmentTable_lookupRefs (t1, key); | |
864 | ||
865 | sRefSet_levelPrune (value, level); | |
866 | ||
867 | if (ind == ATINVALID) | |
868 | { | |
869 | /* okay, t2 is killed */ | |
870 | /*@-exposetrans@*/ /*@-dependenttrans@*/ | |
871 | t1 = environmentTable_addSet (t1, key, value); | |
872 | /*@=exposetrans@*/ /*@=dependenttrans@*/ | |
873 | } | |
874 | else | |
875 | { | |
876 | sRefSet_free (t1->values[ind]); | |
877 | ||
878 | /*@-dependenttrans@*/ /* okay, t2 is killed */ | |
879 | t1->values[ind] = value; | |
880 | /*@=dependenttrans@*/ | |
881 | } | |
882 | } | |
883 | else | |
884 | { | |
885 | /*@-exposetrans@*/ /*@-dependenttrans@*/ | |
886 | sRefSet_free (value); | |
887 | /*@=exposetrans@*/ /*@=dependenttrans@*/ | |
888 | } | |
889 | ||
890 | } end_environmentTable_elements; | |
891 | ||
892 | sfree (t2->keys); | |
893 | sfree (t2->values); | |
894 | sfree (t2); | |
895 | ||
896 | return t1; | |
897 | } | |
898 | ||
899 | environmentTable | |
900 | environmentTable_levelUnion (/*@returned@*/ environmentTable t1, environmentTable t2, int level) | |
901 | { | |
902 | if (environmentTable_isUndefined (t1)) | |
903 | { | |
904 | if (environmentTable_isUndefined (t2)) | |
905 | { | |
906 | return t1; | |
907 | } | |
908 | else | |
909 | { | |
910 | t1 = environmentTable_newEmpty (); | |
911 | } | |
912 | } | |
913 | else | |
914 | { | |
915 | environmentTable_levelPrune (t1, level); | |
916 | } | |
917 | ||
918 | environmentTable_elements (t2, key, cvalue) | |
919 | { | |
920 | sRefSet value = sRefSet_newCopy (cvalue); | |
921 | ||
922 | if (sRef_lexLevel (key) <= level) | |
923 | { | |
924 | sRefSet_levelPrune (value, level); | |
925 | ||
926 | if (sRefSet_size (value) > 0) | |
927 | { | |
928 | int ind = environmentTable_lookupRefs (t1, key); | |
929 | ||
930 | if (ind == ATINVALID) | |
931 | { | |
932 | t1 = environmentTable_addSet (t1, key, value); | |
933 | } | |
934 | else | |
935 | { | |
936 | t1->values[ind] = sRefSet_union (t1->values[ind], value); | |
937 | sRefSet_free (value); | |
938 | } | |
939 | } | |
940 | else | |
941 | { | |
942 | sRefSet_free (value); | |
943 | } | |
944 | } | |
945 | else | |
946 | { | |
947 | sRefSet_free (value); | |
948 | } | |
949 | } end_environmentTable_elements; | |
950 | ||
951 | return t1; | |
952 | } | |
953 | ||
954 | environmentTable environmentTable_levelUnionNew (environmentTable t1, environmentTable t2, int level) | |
955 | { | |
956 | environmentTable ret = environmentTable_levelUnion (environmentTable_copy (t1), t2, level); | |
957 | ||
958 | return ret; | |
959 | } | |
960 | ||
961 | /*@only@*/ cstring | |
962 | environmentTable_unparse (environmentTable s) | |
963 | { | |
964 | cstring st = cstring_undefined; | |
965 | ||
966 | if (environmentTable_isUndefined (s)) return (cstring_makeLiteral ("<NULL>")); | |
967 | ||
968 | environmentTable_elements (s, key, value) | |
969 | { | |
970 | st = message ("%q\t%q -> %q\n", st, sRef_unparse (key), | |
971 | sRefSet_unparse (value)); | |
972 | } end_environmentTable_elements; | |
973 | ||
974 | return st; | |
975 | } | |
976 | ||
977 | /* | |
978 | ** bogus! | |
979 | */ | |
980 | ||
981 | void | |
982 | environmentTable_fixSrefs (environmentTable s) | |
983 | { | |
984 | int i; | |
985 | ||
986 | if (environmentTable_isUndefined (s)) return; | |
987 | ||
988 | for (i = 0; i < s->nelements; i++) | |
989 | { | |
990 | sRef old = s->keys[i]; | |
991 | ||
992 | if (sRef_isLocalVar (old)) | |
993 | { | |
994 | s->keys[i] = uentry_getSref (sRef_getUentry (old)); | |
995 | } | |
996 | ||
997 | sRefSet_fixSrefs (s->values[i]); | |
998 | } | |
999 | } | |
1000 | ||
1001 | void | |
1002 | environmentTable_free (/*@only@*/ environmentTable s) | |
1003 | { | |
1004 | int i; | |
1005 | ||
1006 | if (environmentTable_isUndefined (s)) return; | |
1007 | ||
1008 | for (i = 0; i < s->nelements; i++) | |
1009 | { | |
1010 | sRefSet_free (s->values[i]); | |
1011 | } | |
1012 | ||
1013 | sfree (s->values); | |
1014 | sfree (s->keys); | |
1015 | sfree (s); | |
1016 | } | |
1017 | ||
1018 | void | |
1019 | environmentTable_checkGlobs (environmentTable t) | |
1020 | { | |
1021 | environmentTable_elements (t, key, value) | |
1022 | { | |
1023 | sRef root = sRef_getRootBase (key); | |
1024 | ||
1025 | if (sRef_isAliasCheckedGlobal (root)) | |
1026 | { | |
1027 | sRefSet_realElements (value, sr) | |
1028 | { | |
1029 | root = sRef_getRootBase (sr); | |
1030 | ||
1031 | if (((sRef_isAliasCheckedGlobal (root) | |
1032 | && !(sRef_similar (root, key))) | |
1033 | || sRef_isAnyParam (root)) | |
1034 | && !sRef_isExposed (root)) | |
1035 | { | |
1036 | if (sRef_isAliasCheckedGlobal (key)) | |
1037 | { | |
1038 | if (!(sRef_isShared (key) | |
1039 | && sRef_isShared (root))) | |
1040 | { | |
1041 | voptgenerror | |
1042 | (FLG_GLOBENVIRONMENT, | |
1043 | message | |
1044 | ("Function returns with %q variable %q environmenting %q %q", | |
1045 | cstring_makeLiteral (sRef_isRealGlobal (key) | |
1046 | ? "global" : "file static"), | |
1047 | sRef_unparse (key), | |
1048 | cstring_makeLiteral (sRef_isAnyParam (root) | |
1049 | ? "parameter" : "global"), | |
1050 | sRef_unparse (sr)), | |
1051 | g_currentloc); | |
1052 | } | |
1053 | } | |
1054 | ||
1055 | } | |
1056 | } end_sRefSet_realElements; | |
1057 | } | |
1058 | else if (sRef_isAnyParam (key) || sRef_isAnyParam (root)) | |
1059 | { | |
1060 | sRefSet_realElements (value, sr) | |
1061 | { | |
1062 | root = sRef_getRootBase (sr); | |
1063 | ||
1064 | if (sRef_isAliasCheckedGlobal (root) | |
1065 | && !sRef_isExposed (root) | |
1066 | && !sRef_isDead (key) | |
1067 | && !sRef_isShared (root)) | |
1068 | { | |
1069 | voptgenerror | |
1070 | (FLG_GLOBENVIRONMENT, | |
1071 | message ("Function returns with parameter %q environmenting %q %q", | |
1072 | sRef_unparse (key), | |
1073 | cstring_makeLiteral (sRef_isRealGlobal (root) | |
1074 | ? "global" : "file static"), | |
1075 | sRef_unparse (sr)), | |
1076 | g_currentloc); | |
1077 | } | |
1078 | } end_sRefSet_realElements; | |
1079 | } | |
1080 | else | |
1081 | { | |
1082 | ; | |
1083 | } | |
1084 | } end_environmentTable_elements; | |
1085 | } | |
1086 | ||
1087 | ||
4cccc6ad | 1088 | exprNode exprNode_mergeEnvironments (exprNode ret, exprNode e1, exprNode e2) |
1089 | { | |
1090 | if (exprNode_isDefined (e1) && exprNode_isDefined (e2) ) | |
1091 | { | |
1092 | ret->environment = environmentTable_mergeEnvironments (e1->environment, e2->environment); | |
1093 | return ret; | |
1094 | } | |
1095 | if (exprNode_isUndefined(e1) && exprNode_isUndefined(e2) ) | |
1096 | { | |
1097 | ret->environment = environmentTable_undefined; | |
1098 | } | |
1099 | else | |
1100 | { | |
1101 | ret->environment = exprNode_isUndefined (e1) ? environmentTable_copy(e2->environment) | |
1102 | : environmentTable_copy (e1->environment); | |
1103 | return ret; | |
1104 | } | |
1105 | } | |
1106 | ||
1107 | ||
1108 | ||
1109 | exprNode | |
1110 | exprNode_updateForPostOp ( /*@notnull@*/ /*@returned@*/ exprNode e1) | |
1111 | { | |
1112 | e1->environment = environmentTable_postOpvar (e1->environment, e1->sref); | |
1113 | return e1; | |
1114 | } | |
1115 | ||
1116 | void updateEnvironmentForPostOp (/*@notnull@*/ exprNode e1) | |
1117 | { | |
1118 | sRef s1 = e1->sref; | |
1119 | // printf("doing updateEnvironmentForPostOp\n"); | |
1120 | e1 = exprNode_updateForPostOp (e1); | |
1121 | /*do in exprNode update exprnode*/ | |
1122 | usymtab_postopVar (s1); | |
1123 | } | |
1124 | ||
1125 | void updateEnvironment (/*@notnull@*/ exprNode e1, /*@notnull@*/ exprNode e2) | |
1126 | { | |
1127 | // printf("doing updateEnvironment\n"); | |
1128 | if (!context_inProtectVars ()) | |
1129 | { | |
1130 | /* | |
1131 | ** depends on types of e1 and e2 | |
1132 | */ | |
1133 | ||
1134 | sRef s1 = e1->sref; | |
1135 | sRef s2 = e2->sref; | |
1136 | ctype t1 = exprNode_getType (e1); | |
1137 | // printf(" for %s = %s \n", sRef_unparse(s1), sRef_unparse(s2) ); | |
1138 | // printf("type is %d\n", t1); | |
1139 | if (multiVal_isInt( e2->val) ) | |
1140 | { | |
1141 | int val = multiVal_forceInt(e2->val); | |
1142 | // printf("value is %d \n", val); | |
1143 | usymtab_addExactValue( s1, val); | |
1144 | environmentTable_addExactValue (e1->environment, s1, val); | |
1145 | } | |
1146 | ||
1147 | /* handle pointer sRefs, record fields, arrays, etc... */ | |
1148 | } | |
1149 | else | |
1150 | { | |
1151 | // printf("context_inProtectVars\n"); | |
1152 | } | |
1153 | ||
1154 | } | |
d0e5b01f | 1155 | |
4cccc6ad | 1156 | /*@=fcnuse*/ |
1157 | /*@end@*/ |