1 /*
2 ** Splint - annotation-assisted static program checker
3 ** Copyright (C) 1994-2003 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 splint: info@splint.org
21 ** To report a bug: splint-bug@splint.org
22 ** For more information: http://www.splint.org
23 */
24 /*
25 ** uentryList.c (from slist_template.c)
26 */
27
28 # include "splintMacros.nf"
29 # include "basic.h"
30
31 /*@only@*/ /*@notnull@*/ uentryList
uentryList_new()32 uentryList_new ()
33 {
34 uentryList s = (uentryList) dmalloc (sizeof (*s));
35
36 s->nelements = 0;
37 s->nspace = uentryListBASESIZE;
38 s->elements = (uentry *)
39 dmalloc (sizeof (*s->elements) * uentryListBASESIZE);
40 s->current = 0;
41
42 return (s);
43 }
44
45 /*@only@*/ uentryList
uentryList_single(uentry el)46 uentryList_single (/*@keep@*/ uentry el)
47 {
48 uentryList s = (uentryList) dmalloc (sizeof (*s));
49
50 s->nelements = 1;
51 s->nspace = uentryListBASESIZE - 1;
52 s->elements = (uentry *) dmalloc (sizeof (*s->elements) * uentryListBASESIZE);
53
54 s->elements[0] = el;
55 s->current = 0;
56
57 return (s);
58 }
59
60 static void
uentryList_grow(uentryList s)61 uentryList_grow (uentryList s)
62 {
63 int i;
64 uentry *newelements;
65
66 llassert (!uentryList_isUndefined (s));
67
68 s->nspace += uentryListBASESIZE;
69
70 newelements = (uentry *) dmalloc (sizeof (*newelements)
71 * (s->nelements + s->nspace));
72
73 for (i = 0; i < s->nelements; i++)
74 {
75 newelements[i] = s->elements[i];
76 }
77
78 sfree (s->elements);
79 s->elements = newelements;
80 }
81
uentryList_clear(uentryList s)82 void uentryList_clear (uentryList s)
83 {
84 if (uentryList_isUndefined (s))
85 {
86 ;
87 }
88 else
89 {
90 s->nspace += s->nelements;
91 s->nelements = 0;
92 }
93 }
94
uentryList_add(uentryList s,uentry el)95 uentryList uentryList_add (uentryList s, /*@keep@*/ uentry el)
96 {
97 if (uentryList_isUndefined (s))
98 {
99 s = uentryList_new ();
100 }
101
102 if (s->nspace <= 0)
103 uentryList_grow (s);
104
105 s->nspace--;
106 s->elements[s->nelements] = el;
107 s->nelements++;
108
109 return s;
110 }
111
112 /*@only@*/ cstring
uentryList_unparse(uentryList s)113 uentryList_unparse (uentryList s)
114 {
115 cstring st = cstring_undefined;
116 int i;
117
118 if (uentryList_isDefined (s))
119 {
120 for (i = 0; i < uentryList_size (s); i++)
121 {
122 if (i == 0)
123 {
124 st = message ("%q;", uentry_unparse (s->elements[i]));
125 }
126 else
127 st = message ("%q %q;", st, uentry_unparse (s->elements[i]));
128 }
129 }
130
131 return (st);
132 }
133
134 /*@unused@*/ /*@only@*/ cstring
uentryList_unparseFull(uentryList s)135 uentryList_unparseFull (uentryList s)
136 {
137 cstring st = cstring_undefined;
138 int i;
139
140 if (uentryList_isDefined (s))
141 {
142 for (i = 0; i < uentryList_size (s); i++)
143 {
144 if (i == 0)
145 {
146 st = message ("%q;", uentry_unparseFull (s->elements[i]));
147 }
148 else
149 {
150 st = message ("%q %q;", st, uentry_unparseFull (s->elements[i]));
151 }
152 }
153 }
154
155 return (st);
156 }
157
uentryList_unparseParams(uentryList s)158 cstring uentryList_unparseParams (uentryList s)
159 {
160 int i;
161 cstring st = cstring_undefined;
162
163
164 if (uentryList_isUndefined (s))
165 {
166 return st;
167 }
168 else if (uentryList_isVoid (s))
169 {
170 return (cstring_makeLiteral ("void"));
171 }
172 else
173 {
174 for (i = 0; i < uentryList_size (s); i++)
175 {
176 if (i == 0)
177 {
178 st = message ("%s", ctype_unparse (uentry_getType (s->elements[i])));
179 }
180 else
181 {
182 st = message ("%q, %s", st, ctype_unparse (uentry_getType (s->elements[i])));
183 }
184 }
185
186 return st;
187 }
188 }
189
uentryList_matchParams(uentryList p1,uentryList p2,bool force,bool arg)190 bool uentryList_matchParams (uentryList p1, uentryList p2, bool force, bool arg)
191 {
192 int sz1 = uentryList_size (p1);
193 int sz2 = uentryList_size (p2);
194 int i;
195
196 if (p1 == p2) return TRUE;
197
198 if (uentryList_isMissingParams (p1) || uentryList_isMissingParams (p2))
199 {
200 return TRUE;
201 }
202
203 if (sz1 != sz2)
204 return FALSE;
205
206 for (i = 0; i < sz1; i++)
207 {
208 if (!ctype_genMatch (uentry_getType (p1->elements[i]),
209 uentry_getType (p2->elements[i]),
210 force, arg, FALSE, FALSE))
211 {
212 return FALSE;
213 }
214 }
215
216 return TRUE;
217 }
218
219 /*@only@*/ cstring
uentryList_unparseAbbrev(uentryList p)220 uentryList_unparseAbbrev (uentryList p)
221 {
222 bool first = TRUE;
223 cstring s = cstring_undefined;
224 int i = 0;
225
226 if (uentryList_isUndefined (p))
227 return s;
228
229 if (uentryList_size (p) == 0)
230 return cstring_makeLiteral ("void");
231
232 for (i = 0; i < p->nelements && i < uentryList_abbrevBreadth; i++)
233 {
234 if (first)
235 {
236 s = message ("%q;", uentry_unparseAbbrev (p->elements[i]));
237 first = FALSE;
238 }
239 else
240 {
241 s = message ("%q %q;", s, uentry_unparseAbbrev (p->elements[i]));
242 }
243 }
244
245 if (i != uentryList_size (p))
246 s = message ("%q, ...", s);
247
248 return (s);
249 }
250
251 static int
uentryList_lookupDirectName(uentryList s,cstring name)252 uentryList_lookupDirectName (uentryList s, cstring name)
253 {
254 if (uentryList_isDefined (s))
255 {
256 int i;
257
258 for (i = 0; i < uentryList_size (s); i++)
259 {
260 if (cstring_equal (name, uentry_rawName (s->elements[i])))
261 {
262 return i;
263 }
264 }
265 }
266
267 return -1;
268 }
269
270 int
uentryList_lookupRealName(uentryList s,cstring name)271 uentryList_lookupRealName (uentryList s, cstring name)
272 {
273 if (uentryList_isDefined (s))
274 {
275 int i;
276
277 for (i = 0; i < uentryList_size (s); i++)
278 {
279 cstring uname = uentry_getName (s->elements[i]);
280
281 if (cstring_equal (name, uname))
282 {
283 cstring_free (uname);
284 return i;
285 }
286
287 cstring_free (uname);
288 }
289 }
290
291 return -1;
292 }
293
uentryList_copy(uentryList s)294 uentryList uentryList_copy (uentryList s)
295 {
296 if (uentryList_isDefined (s))
297 {
298 uentryList t = (uentryList) dmalloc (sizeof (*t));
299 int i;
300
301 t->nelements = s->nelements;
302 t->nspace = 0;
303 t->current = s->current;
304
305 if (s->nelements > 0)
306 {
307 t->elements = (uentry *) dmalloc (sizeof (*t->elements) * t->nelements);
308
309 for (i = 0; i < s->nelements; i++)
310 {
311 t->elements[i] = uentry_copy (s->elements[i]);
312 }
313 }
314 else
315 {
316 t->elements = NULL;
317 }
318
319 return t;
320 }
321 else
322 {
323 return uentryList_undefined;
324 }
325 }
326
327 void
uentryList_free(uentryList s)328 uentryList_free (uentryList s)
329 {
330 if (!uentryList_isUndefined (s))
331 {
332 int i;
333
334 for (i = 0; i < s->nelements; i++)
335 {
336 uentry_free (s->elements[i]);
337 }
338
339 sfree (s->elements);
340 sfree (s);
341 }
342 }
343
344 void
uentryList_freeShallow(uentryList s)345 uentryList_freeShallow (uentryList s)
346 {
347 if (!uentryList_isUndefined (s))
348 {
349 /*@-mustfree@*/ /* free shallow does not free the element */
350 sfree (s->elements);
351 /*@=mustfree@*/
352 sfree (s);
353 }
354 }
355
356 bool
uentryList_isVoid(uentryList cl)357 uentryList_isVoid (uentryList cl)
358 {
359 if (cl != NULL && cl->nelements == 1)
360 {
361 return (ctype_isVoid (ctype_realType (uentry_getType (cl->elements[0]))));
362 }
363
364 return FALSE;
365 }
366
367 /*@exposed@*/ uentry
uentryList_getN(uentryList p,int n)368 uentryList_getN (uentryList p, int n)
369 {
370 llassert (uentryList_isDefined (p));
371
372 if (n < 0 || (n >= uentryList_size (p)))
373 {
374 llcontbug (message ("uentryList_getN: out of range: %d (size %d)",
375 n, uentryList_size (p)));
376 return uentry_undefined;
377 }
378
379 return (p->elements[n]);
380 }
381
uentryList_fixMissingNames(uentryList cl)382 void uentryList_fixMissingNames (uentryList cl)
383 {
384 uentryList_elements (cl, ce)
385 {
386 if (!uentry_hasRealName (ce))
387 {
388 ctype ct = uentry_getType (ce);
389
390 if (ctype_isUA (ct))
391 {
392 uentry_setName (ce, usymtab_getTypeEntryName (ctype_typeId (ct)));
393 }
394 else
395 {
396 llbug (message ("uentryList_fixMissingNames: not UA: %s",
397 ctype_unparse (ct)));
398 }
399
400 uentry_setType (ce, ctype_int);
401 }
402 } end_uentryList_elements;
403 }
404
uentryList_fixImpParams(uentryList cl)405 void uentryList_fixImpParams (uentryList cl)
406 {
407
408 if (context_getFlag (FLG_PARAMIMPTEMP))
409 {
410 uentryList_elements (cl, ce)
411 {
412 sRef s = uentry_getSref (ce);
413 alkind ak = sRef_getAliasKind (s);
414
415 if (alkind_isUnknown (ak) || alkind_isImplicit (ak))
416 {
417 exkind ek = sRef_getExKind (s);
418
419 if (exkind_isKnown (ek))
420 {
421 sRef_setAliasKind (s, AK_IMPDEPENDENT, fileloc_undefined);
422 }
423 else
424 {
425 sRef_setAliasKind (s, AK_IMPTEMP, fileloc_undefined);
426 }
427 }
428 else
429 {
430 }
431 } end_uentryList_elements;
432 }
433 }
434
435 int
uentryList_compareParams(uentryList s,uentryList t)436 uentryList_compareParams (uentryList s, uentryList t)
437 {
438 int i, sz;
439
440 if (s == t) return 0;
441
442 if (uentryList_isUndefined (s)) return 1;
443 if (uentryList_isUndefined (t)) return -1;
444
445 sz = uentryList_size (s);
446
447 INTCOMPARERETURN (uentryList_size (t), sz);
448
449 for (i = 0; i < sz; i++)
450 {
451 COMPARERETURN (uentry_compare (s->elements[i], t->elements[i]));
452 }
453
454 return 0;
455 }
456
457 int
uentryList_compareStrict(uentryList s,uentryList t)458 uentryList_compareStrict (uentryList s, uentryList t)
459 {
460 int i, sz;
461
462 if (s == t)
463 {
464 return 0;
465 }
466
467 if (uentryList_isMissingParams (s))
468 {
469 if (uentryList_isMissingParams (t))
470 {
471 return 0;
472 }
473 else
474 {
475 return 1;
476 }
477 }
478 else
479 {
480 if (uentryList_isMissingParams (t))
481 {
482 return -1;
483 }
484 else
485 {
486 sz = uentryList_size (s);
487
488 INTCOMPARERETURN (uentryList_size (t), sz);
489
490 for (i = 0; i < sz; i++)
491 {
492 COMPARERETURN (uentry_compareStrict (s->elements[i], t->elements[i]));
493 }
494
495 return 0;
496 }
497 }
498 }
499
500 int
uentryList_compareFields(uentryList s,uentryList t)501 uentryList_compareFields (uentryList s, uentryList t)
502 {
503 int i, sz;
504
505 if (s == t) return 0;
506
507 if (uentryList_isUndefined (s))
508 return 1;
509 if (uentryList_isUndefined (t))
510 return -1;
511
512 sz = uentryList_size (s);
513
514 if (uentryList_size (t) != sz)
515 {
516 return (int_compare (sz, uentryList_size (t)));
517 }
518
519 for (i = 0; i < sz; i++)
520 {
521 uentry se = s->elements[i];
522 uentry te = t->elements[i];
523 int namecmp = cstring_compare (uentry_rawName (se), uentry_rawName (te));
524
525 if (namecmp == 0)
526 {
527 int uc = uentry_compare (s->elements[i], t->elements[i]);
528
529 if (uc != 0)
530 {
531 DPRINTF (("Bad compare: %s / %s",
532 uentry_unparseFull (s->elements [i]),
533 uentry_unparseFull (t->elements [i])));
534
535 return uc;
536 }
537 }
538 else
539 {
540 return (namecmp);
541 }
542 }
543
544 return 0;
545 }
546
547 /*@exposed@*/ uentry
uentryList_current(uentryList s)548 uentryList_current (uentryList s)
549 {
550 llassert (uentryList_isDefined (s));
551 llassert (!(s->current < 0 || (s->current >= s->nelements)));
552 return (s->elements[s->current]);
553 }
554
555 cstring
uentryList_dumpParams(uentryList s)556 uentryList_dumpParams (uentryList s)
557 {
558 cstring st = cstring_undefined;
559
560 if (uentryList_isUndefined (s)) return st;
561
562 uentryList_elements (s, current)
563 {
564 DPRINTF (("Dump param: %s", uentry_unparse (current)));
565 st = message ("%q%q,", st, uentry_dumpParam (current));
566 } end_uentryList_elements;
567
568 return st;
569 }
570
571 /*@only@*/ cstring
uentryList_dumpFields(uentryList s)572 uentryList_dumpFields (uentryList s)
573 {
574 cstring st = cstring_undefined;
575
576 if (uentryList_isUndefined (s)) return st;
577
578 uentryList_elements (s, current)
579 {
580 if (!uentry_isVariable (current))
581 {
582 llassert (uentry_isFunction (current));
583 DPRINTF (("Dump field: %s", uentry_unparse (current)));
584 st = message ("%q!%q,", st, uentry_dump (current));
585 }
586 else
587 {
588 DPRINTF (("Dump field: %s", uentry_unparse (current)));
589 st = message ("%q%q,", st, uentry_dump (current));
590 }
591 } end_uentryList_elements;
592
593 return st;
594 }
595
596 /*@only@*/ uentryList
uentryList_undumpFields(char ** s,fileloc loc)597 uentryList_undumpFields (char **s, fileloc loc)
598 {
599 uentryList ul = uentryList_new ();
600
601 while (**s != '\0' && **s != '}')
602 {
603 if (**s == '!')
604 {
605 reader_checkChar (s, '!');
606 ul = uentryList_add (ul, uentry_undump (ekind_function, loc, s));
607 }
608 else
609 {
610 ul = uentryList_add (ul, uentry_undump (ekind_variable, loc, s));
611 }
612 reader_checkChar (s, ',');
613 }
614
615 reader_checkChar (s, '}');
616 return ul;
617 }
618
619 /*@only@*/ uentryList
uentryList_undump(char ** s)620 uentryList_undump (char **s)
621 {
622 char c;
623 uentryList pn = uentryList_new ();
624 int paramno = 0;
625
626 c = **s;
627
628 while (c != '#' && c != '@' && c != ')')
629 {
630 uentry ue = uentry_undump (ekind_variable, g_currentloc, s);
631
632
633 if (!uentry_isUndefined (ue))
634 {
635 pn = uentryList_add (pn, ue);
636 }
637 else
638 {
639 uentry_free (ue);
640 }
641
642 reader_checkChar (s, ',');
643 c = **s;
644 paramno++;
645 }
646
647 reader_checkChar (s, ')');
648 return pn;
649 }
650
651 void
uentryList_reset(uentryList s)652 uentryList_reset (uentryList s)
653 {
654 if (uentryList_isUndefined (s)) return;
655 s->current = 0;
656 }
657
658 bool
uentryList_isFinished(uentryList s)659 uentryList_isFinished (uentryList s)
660 {
661 if (uentryList_isUndefined (s)) return TRUE;
662 return (s->current > s->nelements - 1);
663 }
664
665 void
uentryList_advanceSafe(uentryList s)666 uentryList_advanceSafe (uentryList s)
667 {
668 if (uentryList_isUndefined (s)) return;
669
670 s->current++;
671
672 if (s->current > s->nelements)
673 {
674 s->current = s->nelements;
675 }
676 }
677
678 int
uentryList_size(uentryList s)679 uentryList_size (uentryList s)
680 {
681 if (uentryList_isUndefined (s)) return 0;
682
683 if (uentryList_isVoid (s))
684 return 0;
685
686 return s->nelements;
687 }
688
689 bool
uentryList_isMissingParams(uentryList s)690 uentryList_isMissingParams (uentryList s)
691 {
692 return (uentryList_isUndefined (s) || s->nelements == 0);
693 }
694
uentryList_hasReturned(uentryList ul)695 bool uentryList_hasReturned (uentryList ul)
696 {
697 uentryList_elements (ul, current)
698 {
699 if (uentry_isReturned (current)) return TRUE;
700 } end_uentryList_elements;
701
702 return FALSE;
703 }
704
705 /*@exposed@*/ uentry
uentryList_lookupField(uentryList f,cstring name)706 uentryList_lookupField (uentryList f, cstring name)
707 {
708 int i = uentryList_lookupDirectName (f, name);
709
710 if (i >= 0)
711 {
712 return (uentryList_getN (f, i));
713 }
714 else
715 {
716 uentryList_elements (f, el)
717 {
718 if (uentry_isUnnamedVariable (el))
719 {
720 ctype ct = uentry_getType (el);
721
722 if (ctype_isStruct (ct) || ctype_isUnion (ct))
723 {
724 uentryList fields = ctype_getFields (ct);
725 uentry ue = uentryList_lookupField (fields, name);
726
727 if (uentry_isValid (ue))
728 {
729 return ue;
730 }
731 }
732 }
733 }
734 end_uentryList_elements ;
735
736 return uentry_undefined;
737 }
738 }
739
740 /*@only@*/ uentryList
uentryList_mergeFields(uentryList f1,uentryList f2)741 uentryList_mergeFields (/*@only@*/ uentryList f1, /*@only@*/ uentryList f2)
742 {
743 DPRINTF (("Merge: %s + %s", uentryList_unparse (f1), uentryList_unparse (f2)));
744
745 if (uentryList_isUndefined (f1))
746 {
747 return (f2);
748 }
749
750 if (uentryList_isDefined (f2))
751 {
752 uentryList_elements (f2, current)
753 {
754 uentry old = uentryList_lookupField (f1, uentry_rawName (current));
755
756 if (uentry_isValid (old))
757 {
758 voptgenerror
759 (FLG_SYNTAX,
760 message ("Field name reused: %s", uentry_rawName (current)),
761 uentry_whereDefined (current));
762 llgenmsg (message ("Previous use of %s", uentry_rawName (current)),
763 uentry_whereDefined (old));
764 }
765
766 /* okay to use exposed current since f2 is killed */
767 /*@-exposetrans@*/ /*@-dependenttrans@*/
768 f1 = uentryList_add (f1, current);
769 /*@=exposetrans@*/ /*@=dependenttrans@*/
770
771 } end_uentryList_elements;
772
773 sfree (f2->elements);
774 sfree (f2);
775 }
776
777 return (f1);
778 }
779
780 void
uentryList_showFieldDifference(uentryList p1,uentryList p2)781 uentryList_showFieldDifference (uentryList p1, uentryList p2)
782 {
783 uentry cp1, cp2;
784 int index;
785
786 llassert (NOALIAS (p1, p2));
787 llassert (uentryList_isDefined (p1));
788 llassert (uentryList_isDefined (p2));
789
790 for (index = 0; index < p1->nelements; index++)
791 {
792 cp1 = p1->elements[index];
793
794 if (index == p2->nelements)
795 {
796 llgenindentmsg
797 (message ("Field present in %s, missing in %rdeclaration: %q",
798 uentry_specDeclName (cp1),
799 uentry_isDeclared (cp1),
800 uentry_unparse (cp1)),
801 uentry_whereEither (cp1));
802 return;
803 }
804
805 cp2 = p2->elements[index];
806
807 if (!(cstring_equal (uentry_rawName (cp1), uentry_rawName (cp2))))
808 {
809 llgenindentmsg
810 (message ("Field %s in %s corresponds to %s in %rdeclaration",
811 uentry_rawName (cp1),
812 uentry_specOrDefName (cp1),
813 uentry_rawName (cp2),
814 uentry_isCodeDefined (cp1)),
815 uentry_whereDefined (cp2));
816 uentry_showWhereLastPlain (cp1);
817 return;
818 }
819 else
820 {
821 /* evs 2000-07-25 was ctype_match, should match uentryList_matchFields */
822
823 if (!ctype_almostEqual (uentry_getType (cp1), uentry_getType (cp2)))
824 {
825 llgenindentmsg
826 (message ("Field %s %rdeclared as %s, %s as %s",
827 uentry_rawName (cp2),
828 uentry_isCodeDefined (cp1),
829 ctype_unparse (uentry_getType (cp1)),
830 uentry_specOrDefName (cp2),
831 ctype_unparse (uentry_getType (cp2))),
832 uentry_whereDefined (cp2));
833 uentry_showWhereLastPlain (cp1);
834 return;
835 }
836 }
837 }
838
839 if (index != p2->nelements)
840 {
841 cp2 = p2->elements[index];
842
843 llgenindentmsg
844 (message ("Extra field in new declaration: %q",
845 uentry_unparse (cp2)),
846 uentry_whereEither (cp2));
847
848 return;
849 }
850
851 llbug (message ("uentryList_showFieldDifference: match: %q / %q",
852 uentryList_unparse (p1), uentryList_unparse (p2)));
853 }
854
855 bool
uentryList_equivFields(uentryList p1,uentryList p2)856 uentryList_equivFields (uentryList p1, uentryList p2)
857 {
858 return (uentryList_compareFields (p1, p2) == 0);
859 }
860
861 bool
uentryList_matchFields(uentryList p1,uentryList p2)862 uentryList_matchFields (uentryList p1, uentryList p2)
863 {
864 int index;
865 uentry cp1, cp2;
866
867 if (p1 == p2)
868 {
869 return (TRUE);
870 }
871
872 if (uentryList_isEmpty (p1) || uentryList_isEmpty (p2))
873 {
874 return (TRUE);
875 }
876
877 if (uentryList_size (p1) != uentryList_size (p2))
878 {
879 return FALSE;
880 }
881
882 for (index = 0; index < p1->nelements; index++)
883 {
884 cp1 = p1->elements[index];
885 cp2 = p2->elements[index];
886
887 /*
888 ** Should compare uentry's --- need to fix report errors too.
889 */
890
891 if (!(cstring_equal (uentry_rawName (cp1), uentry_rawName (cp2))
892 && (ctype_almostEqual (uentry_getType (cp1), uentry_getType (cp2)))))
893 {
894 return FALSE;
895 }
896 }
897
898 return TRUE;
899 }
900