4 The first pass first pass data structure
8 is changed a little and some structures have been added.
22 This line number is used for some warnings.
28 selector is extended with the members
38 member did exist already, but was only used for code generation.
39 This usage is eliminated so it can be used by
41 The meaning of these members should be clear.
45 Lint_stack_entry descriptor
48 struct lint_stack_entry {
49 struct lint_stack_entry *next;
50 struct lint_stack_entry *previous;
53 struct state *ls_current;
57 struct switch_states switch_state;
63 Structure to simulate a stacking mechanism.
65 Pointer to the entry on top of this one.
67 Pointer to the entry beneath this one.
69 The class of statement this entry belongs to.
70 Possible classes are \f(CWIF\fP, \f(CWWHILE\fP, \f(CWDO\fP,
71 \f(CWFOR\fP, \f(CWSWITCH\fP and \f(CWCASE\fP.
73 The level the corresponding statement is nested.
74 .IP \f(CWls_current\fP
75 A pointer to the state descriptor which describes the state
76 of the function (the state of the automatic variables, if the next
77 statement can be reached, et cetera) if control passes the
78 flow of control to the part of the program currently parsed.
79 The initialization of this state is as follows
82 If \f(CWls_class\fP in [\f(CWIF\fP, \f(CWSWITCH\fP] the state
83 after parsing the conditional expression.
85 If \f(CWls_class\fP in [\f(CWWHILE\fP, \f(CWFOR\fP] the state
86 after parsing the code between the brackets.
88 If \f(CWls_class\fP in [\f(CWDO\fP, \f(CWCASE\fP] the state at
89 entrance of the statement after the \f(CWDO\fP or \f(CWCASE\fP
92 .IP \f(CWls_states\fP 15
93 Union of pointers to state descriptors containing different information
94 for different values of \f(CWls_class\fP.
97 If \f(CWls_class\fP is \f(CWIF\fP and in case of parsing an else part,
98 \f(CWls_states.S_if\fP points to the state that is reached after the
101 If \f(CWls_class\fP in [\f(CWWHILE\fP, \f(CWFOR\fP, \f(CWDO\fP]
102 then \f(CWls_states.S_end\fP contains a conservative description
103 of the state of the program after `jumping'
104 to the end of the statement after the \f(CWWHILE\fP, \f(CWDO\fP
105 or \f(CWFOR\fP token.
106 I.e. the state at reaching a break (not inside a switch) or
109 If ls_class is \f(CWSWITCH\fP, \f(CWls_states\fP is used as a structure
112 struct switch_states {
114 struct state S_break;
118 containing two pointers to state descriptors.
119 \f(CWls_states.switch_state.S_case\fP contains
120 a conservative description
121 of the state of the program after \f(CWcase ... case\fP
123 \f(CWls_states.switch_state.S_break\fP the state after parsing
124 all the \f(CWcase ... break\fP parts.
125 The reason for \f(CWls_states.switch_state.default_met\fP should be
128 In case \f(CWls_class\fP is \f(CWCASE\fP, \f(CWls_states\fP is not used.
136 struct auto_def *st_auto_list;
142 .IP \f(CWst_auto_list\fP 15
143 Pointer to a list of definitions of the automatic variables whose
144 scope contain the current position in the program.
146 True if the next statement can't be reached.
147 .IP \f(CWst_warned\fP
148 True if a warning has already been given.
154 struct auto_def *next;
164 Points to the next auto_definition of the list.
166 Pointer to the idf descriptor associated with this auto_definition.
168 Ditto for def descriptor.
170 Indicates the state of this automatic variable.
171 Ditto for \f(CWad_set\fP and \f(CWad_maybe_set\fP.
172 Only one of \f(CWad_set\fP and \f(CWad_maybe_set\fP may be true.
174 Expr_state descriptor
178 struct expr_state *next;
187 This structure is introduced to keep track of which variables,
188 array entries and structure members (union members) are set
189 and/or used in evaluating an expression.
191 Pointer to the next descriptor of this list.
193 Pointer to the idf descriptor this descriptor belongs to.
194 .IP \f(CWes_offset\fP
195 In case of an array, a structure or union, this member contains
196 the offset the compiler would generate for locating the array
197 entry or structure/union member.
199 True if the indicated memory location is used in evaluating the
211 unsigned int od_line;
213 struct tp_entry *od_entry;
215 struct type *od_type;
220 As structures of this type are not allocated dynamically by a
221 storage allocator, it contains no next member.
222 An outdef can be given to to \f(CWoutput_def()\fP to be passed to the
224 Basically this forms the interface with the second pass.
225 .IP \f(CWod_class\fP 15
226 Indicates what kind of definition it is.
227 Possible classes are \f(CWEFDF\fP, \f(CWEVDF\fP, \f(CWSFDF\fP,
228 \f(CWSVDF\fP, \f(CWLFDF\fP, \f(CWLVDF\fP,
229 \f(CWEFDC\fP, \f(CWEVDC\fP, \f(CWIFDC\fP, \f(CWFC\fP, \f(CWVU\fP.
230 ([\f(CWE\fPxternal, \f(CWS\fPtatic, \f(CWL\fPibrary, \f(CWI\fPmplicit]
231 [\f(CWF\fPunction, \f(CWV\fPariable]
232 [\f(CWD\fPe\f(CWF\fPinition, \f(CWD\fPe\f(CWC\fPlaration,
233 \f(CWC\fPall, \f(CWU\fPsage])
235 The name of the function or variable.
237 The file this definition comes from.
238 .IP \f(CWod_nrargs\fP
239 If \f(CWod_class\fP is one of \f(CWEFDF\fP, \f(CWSFDF\fP or
240 \f(CWLFDF\fP, this member contains the
241 number of arguments this function has.
242 If the function was preceded by the pseudocomment
243 \f(CW/*\ VARARGS\ */\fP,
244 \f(CWod_nrargs\fP gets the value \f(CW-1-n\fP.
246 A pointer to a list of \f(CWod_nrargs\fP cells, each containing a
247 pointer to the type descriptor of an argument. (\f(CW-1-od_nrargs\fP
249 \f(CWod_nrargs < 0\fP.)
250 \f(CWTp_entry\fP is defined as
254 struct tp_entry *next; /* pointer to next cell */
255 struct type *te_type; /* an argument type */
259 .IP \f(CWod_returns\fP 15
260 For classes \f(CWEFDF\fP, \f(CWSFDF\fP and \f(CWLFDF\fP this
261 member tells if the function returns an expression or not.
262 In case \f(CWod_class\fP is \f(CWFC\fP it is true if the value
263 of the function is used, false otherwise.
264 For other classes this member is not used.
266 A pointer to the type of the function or variable defined or
268 Not used for classes \f(CWFC\fP and \f(CWVU\fP.
270 The first pass checking mechanism
272 In the description of the implementation of the pass one
273 warnings, it is assumed that the reader is familiar with the
274 \fILLgen\fP parser generator, as described in [6].
276 Used and/or set variables
278 To be able to give warnings like
284 %s set but not used in function %s
286 , there needs to be a way to keep track of the state of a variable.
287 A first approach to do this was by adding two fields to the
296 While parsing the program, each time an expression was met
297 this expression was analyzed and the fields of each \fIdef\fP
298 selector were possibly set during this analysis.
299 This analysis was done by passing each expression to a
304 , which walks the expression tree in a way similar to the function
305 \f(CWEVAL\fP in the file \fIeval.c\fP of the original
310 This approach has one big disadvantage: it is impossible to keep
311 track of the flow of control of the program.
312 No warning will be given for the program fragment of figure 3.
323 use(i); /* i may be used before set */
333 It is clear that it would be nice having
335 warn for this construction.
337 This was done in the second approach.
338 When there was a choice between two statements, each statement
339 was parsed with its own copy of the state at entrance of the
343 A state consisted of the state of the automatic variables
344 (including register variables).
345 In addition to the possibilities of being used and set,
346 a variable could be \fImaybe set\fP.
347 These states were passed between the statement parsing routines
348 using the \fILLgen\fP parameter mechanism.
349 At the end of a choosing statement, the two states were merged
350 into one state, which became the state after this statement.
351 The construction of figure 4 was now detected, but switch
352 statements still gave problems and continue and break statements
354 The main problem of a switch statement is, that the closing bracket
355 (`\f(CW)\fP') has to be followed by a \fIstatement\fP.
356 The syntax shows no choice of statements, as is the case with
357 if, while, do and for statements.
358 Using the \fILLgen\fP parameter mechanism, it is not a trivial
359 task to parse the different case parts of a switch statement
360 with the same initial state and to merge the results into one
362 This observation led to the third and final approach, as described
365 Instead of passing the state of the program through the statements
366 parsing routines using the \fILLgen\fP parameters, a special stack is
369 When a choosing statement is parsed, an entry is pushed on the stack
370 containing the information that is needed to keep track of the
371 state of the program.
372 Each entry contains a description of the
374 state of the program and a field that indicates what part of the
375 program the parser is currently parsing.
376 For all the possible choosing statements I describe the actions
379 At entrance of an if statement, an entry is pushed on the stack
380 with the current state being a copy of the current state of the
381 stack element one below.
382 The class of this entry is \f(CWIF\fP.
383 At reaching the else part, the current state is moved to
384 another place in this stack entry (to \f(CWS_IF\fP), and a new copy
385 of the current state at entrance of this if statement is made.
386 At the end of the else part, the two states are merged into
387 one state, the new current state, and the \f(CWIF\fP entry is
388 popped from the stack.
389 If there is no else part, then the state that is reached after
390 parsing the if part is merged with the current state at entrance
391 of the if statement into the new current state.
393 At entrance of a while statement a \f(CWWHILE\fP entry is pushed
394 on the stack containing a copy of the current state.
395 If a continue or break statement is met in the while statement,
396 the state at reaching this continue or break statement is
397 merged with a special state in the \f(CWWHILE\fP entry, called
399 (If \f(CWS_END\fP did not yet contain a state, the state is copied
401 At the end of the while statement this \f(CWS_END\fP is merged with the
402 current state, which result is merged with the state at entrance
403 of the while statement into the new current state.
405 A for statement is treated similarly.
406 A do statement is treated the same way too, except that \f(CWS_END\fP
407 isn't merged with the state at entrance of the do statement,
408 but becomes the new current state.
410 For switch statements a \f(CWSWITCH\fP entry is pushed on the stack.
411 Apart from the current state, this entry contains two other
412 states, \f(CWS_BREAK\fP and \f(CWS_CASE\fP.
413 \f(CWS_BREAK\fP initially contains no state, \f(CWS_CASE\fP
415 copy of the current state at entrance of the switch statement.
416 After parsing a case label, a \f(CWCASE\fP entry is pushed on the stack,
417 containing a copy of the current state.
418 If, after zero or more statements, we meet another case label,
419 the state at reaching this case label is merged with \f(CWS_CASE\fP
420 of the \f(CWSWITCH\fP entry below and a new copy of the state
422 of the switch statement is put in the \f(CWCASE\fP entry.
423 If we meet a break statement, we merge the current state with
424 \f(CWS_BREAK\fP of the \f(CWSWITCH\fP entry below and pop the
426 In addition to this, the occurrence of a default statement
427 inside the switch statement is recorded in the \f(CWSWITCH\fP entry.
428 At the end of the switch statement we check if we have met a
430 If not, \f(CWS_BREAK\fP is merged with the current state at entrance
431 of the switch statement. (Because it is possible that no case
432 label will be chosen.)
433 Next the \f(CWS_CASE\fP is `special_merged' with \f(CWS_BREAK\fP
434 into the new current state.
435 For more details about these merge functions see the sources.
437 With the approach described above,
440 of control in the program.
441 There still are some doubtful constructions
443 will not detect and there are some constructions (although rare)
446 gives an incorrect warning (see figure 4).
460 /* lint warns: maybe i used before set
461 * although the fragment is correct
472 A nice advantage of the method is, that the parser stays clear,
473 i.e. it isn't extended with extra parameters which must pass the
475 In this way the parser still is very readable and we have a nice
478 using function calls.
480 Undefined evaluation orders
482 In expressions the values of some variables are used and some
484 Of course, the same holds for subexpressions.
485 The compiler is allowed to choose the order of evaluation of
486 subexpressions involving a commutative and associative operator
487 (\f(CW*\fP, \f(CW+\fP, \f(CW&\fP, \f(CW|\fP, \f(CW^\fP),
488 the comma in a parameter list or an assignment operator.
489 In section 3.4 it is made clear that this will lead to
490 statements with ambiguous semantics.
492 The way these constructs are detected is rather straight forward.
493 The function which parses an expression (\f(CWlint_expr\fP)
495 list containing information telling which variables are set and
496 which variables are used.
497 A variable is indicated by its
501 This offset is needed for discriminating entries of the same
502 array and members of the same structure or union, so it is
503 possible to warn about the statement
507 When \f(CWlint_expr\fP meets a commutative operator (with respect to the
508 evaluation order), it calls itself recursively with the operands
509 of the operator as expression.
510 The returned results are checked for undefined evaluation orders
511 and are put together.
512 This is done by the function \f(CWcheck_and_merge\fP.
516 Statements which compute a value that is not used,
517 are said to have a \fInull effect\fP.
518 Examples are \f(CWx = 2, 3;\fP, \f(CWf() + g();\fP and
520 (\f(CW*\fP and \f(CW++\fP have the same precedence and associate
523 A conditional expression computes a value too.
524 If this value isn't used, it is better to use an if-else
535 it warns \f(CWuse if-else construction\fP.
537 Not-reachable statements
539 The algorithm to detect not-reachable statements (including not
540 reachable initializations) is as follows.
541 Statements after a label and a case statement and the compound
542 statement of a function are always reachable.
543 Other statements are not-reachable after:
557 an endless loop (a while, do or for loop with a conditional
558 which always evaluates to true and without a break statement)
560 an if-else statement of which both if part and else part
561 end up in a not-reachable state
563 a switch statement of which all \f(CWcase ... break\fP parts
565 a \f(CWdefault ... break\fP part) end up in a not-reachable state
567 the pseudocomment \f(CW/*\ NOTREACHED\ */\fP
571 The algorithm is easily implemented using the \f(CWst_nrchd\fP selector
575 The \f(CWst_warned\fP selector is used to prevent superfluous warnings.
576 To detect an endless loop, after a while (<true>), for (..;<true>;..)
577 and do part the current state of the stack entry beneath the top one
578 is set to not reached.
579 If, in the statement following, a break statement is met, this same
580 state is set to reached.
581 If the while (<cond>) part of the do statement is met, this state
582 is set to reached if <cond> doesn't evaluates to true.
583 The detection of not-reachable statements after a switch statement
584 is done in a similar way.
585 In addition it is checked if a default statement isn't met, in
586 which case the statement after the switch statement can be reached.
587 The warning \f(CWstatement not reached\fP is not given for compound
591 did, it would warn for the compound statement in a switch statement,
592 which would be incorrect.
594 Not-reachable statements are still interpreted by
598 warns that some statement can't be reached, it assumes this is
599 not what the programmer really wants and it ignores this fact.
600 In this way a lot of useless warnings are prevented in the case of
601 a not-reachable statement.
610 /* A loop in which the programmer
611 * forgot to introduce a conditional
613 * Suppose i is not used in this part.
616 /* some more code in which i is used */
618 /* The warning "statement not reached" highlights the bug.
619 * An additional warning "i unused in function %s" is
620 * formally correct, but doesn't provide the programmer
621 * with useful information.
630 Functions returning expressions and just returning
632 Each time a return statement is met,
634 checks if an expression is returned or not.
635 If a function has a return with expression and a return without
640 function %s has return(e); and return;.
642 If the flow of control can
646 the end of the compound statement of a function, this indicates
647 an implicit return statement without an expression.
648 If the end of the compound statement of the function can be reached,
650 introduces this implicit return statement without expression.
652 Sometimes the programmer knows for sure that all case parts inside
653 a switch statement include all possible cases, so he doesn't
654 introduce a default statement.
655 This can lead to an incorrect warning.
656 Figure 6 shows how to prevent this warning.
668 /* no warning: "function func has return(e); and return; */
676 The pseudocomment \f(CW/*\ NOTREACHED\ */\fP can also be used to tell
678 that some function doesn't return. See figure 7.
687 default: error(); /* calls exit or abort */
691 /* no warning: "function func has return(e); and return;" */
699 Output definitions for the second pass
701 The first pass can only process one program file.
702 To be able to process a program that spreads over more than one file,
703 the first pass outputs definitions that are processed by a second
705 The format of such a definition is different for different classes:
707 For class in {EFDF, SFDF, LFDF}
709 <name>:<class>:<file>:<line>:<nr of args>:<type of args>:<returns value>:<type>
712 A negative \fInr of args\fP indicates that the function can be called with
713 a varying number of arguments.
717 <name>:<class>:<file>:<line>:<value is used>:<type>
720 The \fIvalue is used\fP part can have three meanings:
721 the value of the function is ignored;
722 the value of the function is used;
723 the value of the function is cast to type \fIvoid\fP.
727 <name>:<class>:<file>:<line>:<type>
730 Definitions of class VU (Variable Usage) are only output for \fIused\fP
733 Structure and union types that are output to the intermediate file
735 (The following occurrences of \fIstructure\fP should be
736 read as \fIstructure or union\fP and \fIstruct\fP as \fIstruct or
738 Structures that are identified by a \fIstructure tag\fP are output
739 to the intermediate file as \f(CWstruct <tag>\fP.
740 Structures without a structure tag are output as
741 \f(CWstruct {<mems>}\fP with \f(CW<mems>\fP a semicolon-separated
742 list of types of the members of this structure.
743 An alternative way would be to output the complete structure definition.
744 However, this gives practical problems.
745 It is allowed to define some object of a structure type with a
746 structure tag, without this structure being defined at that place.
747 The first approach leaves errors, such as in figure 8, undetected.
753 struct str { struct str {
768 To be able to detect these errors, the first pass should also output
769 definitions of structure tags.
770 The example of figure 8 would then get a warning like
772 structure str defined inconsistently
775 More information on these definitions in section 4.3 and 4.4.
780 knows the library `-lc', `-lm' and `-lcurses'.
781 If a program uses some other library, it is possible to generate
782 a corresponding \fIlint library\fP.
783 To do this, precede all the C source files of this library by
784 the pseudocomment \f(CW/*\ LINTLIBRARY\ */\fP.
785 Then feed these files one by one to the first pass of
787 collecting the standard output in a file and ignoring the warnings.
788 The resulting file contains library definitions of the functions
789 and external variables defined in the library sources, and not more
791 If this file is called `llib-l\fIname\fP.ln
793 can be told to search the library by passing it as argument in
794 the command line `-llib-l\fIname\fP.ln.
795 The implementation of this feature is simple.
797 As soon as the pseudocomment \f(CW/*\ LINTLIBRARY\ */\fP is met,
798 only function and variable definitions are output with class LFDF
799 and LVDF respectively.
800 Other definitions, which otherwise would have been output, are
803 Instead of generating a special lint library file, one can make a
804 file containing the library definitions and starting with
805 \f(CW/* LINTLIBRARY */\fP.
806 This file can then be passed to
809 This method isn't as efficient as the first one.
811 Interpreting the pseudocomments
813 The interpretation of the pseudocomments is done by the lexical
814 analyzer, because this part of the program already took care of the
816 At first sight this seems very easy: as soon as some pseudocomment
817 is met, raise the corresponding flag.
818 Unfortunately this doesn't work.
819 The lexical analyzer is a \fIone token look ahead scanner\fP.
820 This causes the above procedure to raise the flags one token too
822 A solution to get the right effect is to reserve two flags per
824 The first is set as soon as the corresponding pseudocomment is
826 At the returning of each token this flag is moved to the second flag.
827 The delay in this way achieved makes the pseudocomments have effect
828 at the correct place.
830 The second pass data structure
836 struct inp_def *next;
838 char id_name[NAMESIZE];
839 char id_file[FNAMESIZE];
840 unsigned int id_line;
842 char argtps[ARGSTPSSIZE];
844 char id_type[TYPESIZE];
853 This description is almost similar to the \fIoutdef\fP descriptor as
854 described in 4.1.2.5.
855 There are some differences too.
857 As structures of this type are allocated dynamically, this field
858 is added so the same memory allocator as used in the first pass can be
866 .IP \f(CWid_voided\fP 15
867 Some additional fields only used for function definitions.Their
868 meaning should be clear.
870 The other fields have the same meaning as the corresponding fields
871 in the \fIoutdef\fP descriptor.
872 Some attention should be paid to \f(CWid_argtps\fP and \f(CWid_type\fP.
873 These members have type \f(CWarray of char\fP, in contrast to
874 their counterparts in the \fIoutdef\fP descriptor.
875 The only operation performed on types is a check on equality.
876 Types are output by the first pass as a string describing the type.
877 The type of \f(CWi\fP in \f(CWint *i();\fP e.g. is output as
879 Such a string is best put in an \f(CWarray of char\fP to be compared
882 The second pass checking mechanism
884 After all the definitions that are output by the first pass are
885 sorted by name, the definitions belonging to one name are ordered
904 The main program of the second pass is easily explained.
905 For all different names, do the following.
906 First read the definitions.
907 If there is more than one definition, check for conflicts.
908 Then read the declarations, function calls and variable usages and
909 check them against the definitions.
910 After having processed all the declarations, function calls and
911 variable usages, check the definitions to see if they are used
913 The next three paragraphs will explain the three most important
914 functions of the program.
918 This function reads all definitions belonging to the same name.
919 Only one external definition is allowed, so if there are more, a
921 In different files it is allowed to define static functions or
922 variables with the same name.
923 So if a static function is read, \f(CWread_defs\fP checks if there isn't
924 already an external definition, and if not it puts the static
925 definition in the list of static definitions, to be used later.
926 If no external or static definitions are met, a library definition is
928 If a function or a variable is defined with the same name as a function
929 or a variable in a library (which is allowed)
932 Of course it is also possible that there is no definition at all.
933 In that case \f(CWcheck\fP will warn.
937 \f(CWCheck\fP verifies declarations, function calls and variable
938 usages against the definitions.
939 For each of these entries the corresponding definition is looked up.
940 As there may be more than one static definition, first a static
941 definition from the same file as the entry is searched.
942 If not present, the external definition (which may be a library
943 definition) is taken as definition.
944 If no definition can be found and the current entry is an external
948 However in the case of an implicit function declaration
950 will not warn, because
951 we will get a warning \f(CW%s used but not defined\fP later on.
952 Next a check is done if the declarations are consistent with their
954 After the declarations, the function calls and variable usages are
955 verified against their corresponding definitions.
956 If no definition exists,
959 Else the field \f(CWid_called\fP is set to 1.
960 (For variable definitions this should be interpreted as \fIused\fP.)
961 For variable usages this will be all.
962 If we are processing a function call we also check the number and types
963 of the arguments and we warn for function values which are used from
964 functions that don't return a value.
965 For each function call we administrate if a function value is used,
970 Checks if the external definition and static definitions are used
972 If a function or variable is defined but never used,
974 warns, except for library definitions.
975 Functions, which return a value but whose value is always or
976 sometimes ignored, get a warning.
977 (A function value which is voided (cast to void) is not ignored,
978 but it isn't used either.)