chap4 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979
  1. .NH 1
  2. How lint checks
  3. .NH 2
  4. The first pass first pass data structure
  5. .PP
  6. The data structure of
  7. .I cem
  8. is changed a little and some structures have been added.
  9. .NH 3
  10. The changes
  11. .NH 4
  12. Idf descriptor
  13. .PP
  14. A member
  15. .ft CW
  16. id_line
  17. .R
  18. is added
  19. to the
  20. .I idf
  21. selector.
  22. This line number is used for some warnings.
  23. .NH 4
  24. Def descriptor
  25. .PP
  26. The
  27. .I def
  28. selector is extended with the members
  29. .ft CW
  30. df_set
  31. .R and
  32. df_line.
  33. .R
  34. The
  35. .ft CW
  36. df_used
  37. .R
  38. member did exist already, but was only used for code generation.
  39. This usage is eliminated so it can be used by
  40. .I lint.
  41. The meaning of these members should be clear.
  42. .NH 3
  43. The additions
  44. .NH 4
  45. Lint_stack_entry descriptor
  46. .DS B
  47. .ft CW
  48. struct lint_stack_entry {
  49. struct lint_stack_entry *next;
  50. struct lint_stack_entry *previous;
  51. short ls_class;
  52. int ls_level;
  53. struct state *ls_current;
  54. union {
  55. struct state *S_if;
  56. struct state *S_end;
  57. struct switch_states switch_state;
  58. } ls_states;
  59. };
  60. .R
  61. .DE
  62. .PP
  63. Structure to simulate a stacking mechanism.
  64. .IP \f(CWnext\fP 15
  65. Pointer to the entry on top of this one.
  66. .IP \f(CWprevious\fP
  67. Pointer to the entry beneath this one.
  68. .IP \f(CWls_class\fP
  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.
  72. .IP \f(CWls_level\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
  80. .RS
  81. .IP
  82. If \f(CWls_class\fP in [\f(CWIF\fP, \f(CWSWITCH\fP] the state
  83. after parsing the conditional expression.
  84. .IP
  85. If \f(CWls_class\fP in [\f(CWWHILE\fP, \f(CWFOR\fP] the state
  86. after parsing the code between the brackets.
  87. .IP
  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
  90. token.
  91. .RE
  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.
  95. .RS
  96. .IP
  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
  99. if part.
  100. .IP
  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
  107. continue statement.
  108. .IP
  109. If ls_class is \f(CWSWITCH\fP, \f(CWls_states\fP is used as a structure
  110. .DS B
  111. .ft CW
  112. struct switch_states {
  113. struct state S_case;
  114. struct state S_break;
  115. };
  116. .R
  117. .DE
  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
  122. parts are parsed.
  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
  126. self-explanatory.
  127. .IP
  128. In case \f(CWls_class\fP is \f(CWCASE\fP, \f(CWls_states\fP is not used.
  129. .RE
  130. .NH 4
  131. State descriptor
  132. .DS B
  133. .ft CW
  134. struct state {
  135. struct state *next;
  136. struct auto_def *st_auto_list;
  137. int st_nrchd;
  138. int st_warned;
  139. };
  140. .R
  141. .DE
  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.
  145. .IP \f(CWst_nrchd\fP
  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.
  149. .NH 4
  150. Auto_def descriptor
  151. .DS B
  152. .ft CW
  153. struct auto_def {
  154. struct auto_def *next;
  155. struct idf *ad_idf;
  156. struct def *ad_def;
  157. int ad_used;
  158. int ad_set;
  159. int ad_maybe_set;
  160. };
  161. .R
  162. .DE
  163. .IP \f(CWnext\fP 15
  164. Points to the next auto_definition of the list.
  165. .IP \f(CWad_idf\fP
  166. Pointer to the idf descriptor associated with this auto_definition.
  167. .IP \f(CWad_def\fP
  168. Ditto for def descriptor.
  169. .IP \f(CWad_used\fP
  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.
  173. .NH 4
  174. Expr_state descriptor
  175. .DS B
  176. .ft CW
  177. struct expr_state {
  178. struct expr_state *next;
  179. struct idf *es_idf;
  180. arith es_offset;
  181. int es_used;
  182. int es_set;
  183. };
  184. .R
  185. .DE
  186. .PP
  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.
  190. .IP \f(CWnext\fP 15
  191. Pointer to the next descriptor of this list.
  192. .IP \f(CWes_idf\fP
  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.
  198. .IP \f(CWes_used\fP
  199. True if the indicated memory location is used in evaluating the
  200. expression.
  201. .IP \f(CWes_set\fP
  202. Ditto for set.
  203. .NH 4
  204. Outdef descriptor
  205. .DS B
  206. .ft CW
  207. struct outdef {
  208. int od_class;
  209. char *od_name;
  210. char *od_file;
  211. unsigned int od_line;
  212. int od_nrargs;
  213. struct tp_entry *od_entry;
  214. int od_returns;
  215. struct type *od_type;
  216. };
  217. .DE
  218. .R
  219. .PP
  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
  223. second pass.
  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])
  234. .IP \f(CWod_name\fP
  235. The name of the function or variable.
  236. .IP \f(CWod_file\fP
  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.
  245. .IP \f(CWod_entry\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
  248. cells if
  249. \f(CWod_nrargs < 0\fP.)
  250. \f(CWTp_entry\fP is defined as
  251. .DS B
  252. .ft CW
  253. struct tp_entry {
  254. struct tp_entry *next; /* pointer to next cell */
  255. struct type *te_type; /* an argument type */
  256. };
  257. .R
  258. .DE
  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.
  265. .IP \f(CWod_type\fP
  266. A pointer to the type of the function or variable defined or
  267. declared.
  268. Not used for classes \f(CWFC\fP and \f(CWVU\fP.
  269. .NH 2
  270. The first pass checking mechanism
  271. .PP
  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].
  275. .NH 3
  276. Used and/or set variables
  277. .PP
  278. To be able to give warnings like
  279. .ft CW
  280. %s used before set
  281. .R
  282. and
  283. .ft CW
  284. %s set but not used in function %s
  285. .R
  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
  288. \fIdef\fP selector:
  289. .ft CW
  290. df_set
  291. .R
  292. and
  293. .ft CW
  294. df_used.
  295. .R
  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
  300. function
  301. .ft CW
  302. lint_expr
  303. .R
  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
  306. .I
  307. cem
  308. .R
  309. compiler.
  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.
  313. .KF
  314. .DS B
  315. .ft CW
  316. func()
  317. {
  318. int i;
  319. if (cond)
  320. i = 0;
  321. else
  322. use(i); /* i may be used before set */
  323. }
  324. .I
  325. .DE
  326. .br
  327. .ce
  328. figure\ 3.
  329. .R
  330. .KE
  331. .PP
  332. It is clear that it would be nice having
  333. .I lint
  334. warn for this construction.
  335. .PP
  336. This was done in the second approach.
  337. When there was a choice between two statements, each statement
  338. was parsed with its own copy of the state at entrance of the
  339. .I
  340. choosing statement.
  341. .R
  342. A state consisted of the state of the automatic variables
  343. (including register variables).
  344. In addition to the possibilities of being used and set,
  345. a variable could be \fImaybe set\fP.
  346. These states were passed between the statement parsing routines
  347. using the \fILLgen\fP parameter mechanism.
  348. At the end of a choosing statement, the two states were merged
  349. into one state, which became the state after this statement.
  350. The construction of figure 4 was now detected, but switch
  351. statements still gave problems and continue and break statements
  352. were not understood.
  353. The main problem of a switch statement is, that the closing bracket
  354. (`\f(CW)\fP') has to be followed by a \fIstatement\fP.
  355. The syntax shows no choice of statements, as is the case with
  356. if, while, do and for statements.
  357. Using the \fILLgen\fP parameter mechanism, it is not a trivial
  358. task to parse the different case parts of a switch statement
  359. with the same initial state and to merge the results into one
  360. state.
  361. This observation led to the third and final approach, as described
  362. next.
  363. .PP
  364. Instead of passing the state of the program through the statements
  365. parsing routines using the \fILLgen\fP parameters, a special stack is
  366. introduced, the
  367. .I lint_stack.
  368. When a choosing statement is parsed, an entry is pushed on the stack
  369. containing the information that is needed to keep track of the
  370. state of the program.
  371. Each entry contains a description of the
  372. .I current
  373. state of the program and a field that indicates what part of the
  374. program the parser is currently parsing.
  375. For all the possible choosing statements I describe the actions
  376. to be taken.
  377. .PP
  378. At entrance of an if statement, an entry is pushed on the stack
  379. with the current state being a copy of the current state of the
  380. stack element one below.
  381. The class of this entry is \f(CWIF\fP.
  382. At reaching the else part, the current state is moved to
  383. another place in this stack entry (to \f(CWS_IF\fP), and a new copy
  384. of the current state at entrance of this if statement is made.
  385. At the end of the else part, the two states are merged into
  386. one state, the new current state, and the \f(CWIF\fP entry is
  387. popped from the stack.
  388. If there is no else part, then the state that is reached after
  389. parsing the if part is merged with the current state at entrance
  390. of the if statement into the new current state.
  391. .PP
  392. At entrance of a while statement a \f(CWWHILE\fP entry is pushed
  393. on the stack containing a copy of the current state.
  394. If a continue or break statement is met in the while statement,
  395. the state at reaching this continue or break statement is
  396. merged with a special state in the \f(CWWHILE\fP entry, called
  397. \f(CWS_END\fP.
  398. (If \f(CWS_END\fP did not yet contain a state, the state is copied
  399. to \f(CWS_END\fP.)
  400. At the end of the while statement this \f(CWS_END\fP is merged with the
  401. current state, which result is merged with the state at entrance
  402. of the while statement into the new current state.
  403. .PP
  404. A for statement is treated similarly.
  405. A do statement is treated the same way too, except that \f(CWS_END\fP
  406. isn't merged with the state at entrance of the do statement,
  407. but becomes the new current state.
  408. .PP
  409. For switch statements a \f(CWSWITCH\fP entry is pushed on the stack.
  410. Apart from the current state, this entry contains two other
  411. states, \f(CWS_BREAK\fP and \f(CWS_CASE\fP.
  412. \f(CWS_BREAK\fP initially contains no state, \f(CWS_CASE\fP
  413. initially contains a
  414. copy of the current state at entrance of the switch statement.
  415. After parsing a case label, a \f(CWCASE\fP entry is pushed on the stack,
  416. containing a copy of the current state.
  417. If, after zero or more statements, we meet another case label,
  418. the state at reaching this case label is merged with \f(CWS_CASE\fP
  419. of the \f(CWSWITCH\fP entry below and a new copy of the state
  420. at entrance
  421. of the switch statement is put in the \f(CWCASE\fP entry.
  422. If we meet a break statement, we merge the current state with
  423. \f(CWS_BREAK\fP of the \f(CWSWITCH\fP entry below and pop the
  424. \f(CWCASE\fP entry.
  425. In addition to this, the occurrence of a default statement
  426. inside the switch statement is recorded in the \f(CWSWITCH\fP entry.
  427. At the end of the switch statement we check if we have met a
  428. default statement.
  429. If not, \f(CWS_BREAK\fP is merged with the current state at entrance
  430. of the switch statement. (Because it is possible that no case
  431. label will be chosen.)
  432. Next the \f(CWS_CASE\fP is `special_merged' with \f(CWS_BREAK\fP
  433. into the new current state.
  434. For more details about these merge functions see the sources.
  435. .PP
  436. With the approach described above,
  437. .I lint
  438. is aware of the flow
  439. of control in the program.
  440. There still are some doubtful constructions
  441. .I lint
  442. will not detect and there are some constructions (although rare)
  443. for which
  444. .I lint
  445. gives an incorrect warning (see figure 4).
  446. .KF
  447. .DS B
  448. .ft CW
  449. {
  450. int i;
  451. for (;;) {
  452. if (cond) {
  453. i = 0;
  454. break;
  455. }
  456. }
  457. use(i);
  458. /* lint warns: maybe i used before set
  459. * although the fragment is correct
  460. */
  461. }
  462. .DE
  463. .br
  464. .I
  465. .ce
  466. figure\ 4.
  467. .R
  468. .KE
  469. .PP
  470. A nice advantage of the method is, that the parser stays clear,
  471. i.e. it isn't extended with extra parameters which must pass the
  472. states.
  473. In this way the parser still is very readable and we have a nice
  474. interface with
  475. .I lint
  476. using function calls.
  477. .NH 3
  478. Undefined evaluation orders
  479. .PP
  480. In expressions the values of some variables are used and some
  481. variables are set.
  482. Of course, the same holds for subexpressions.
  483. The compiler is allowed to choose the order of evaluation of
  484. subexpressions involving a commutative and associative operator
  485. (\f(CW*\fP, \f(CW+\fP, \f(CW&\fP, \f(CW|\fP, \f(CW^\fP),
  486. the comma in a parameter list or an assignment operator.
  487. In section 3.4 it is made clear that this will lead to
  488. statements with ambiguous semantics.
  489. .PP
  490. The way these constructs are detected is rather straight forward.
  491. The function which parses an expression (\f(CWlint_expr\fP)
  492. returns a linked
  493. list containing information telling which variables are set and
  494. which variables are used.
  495. A variable is indicated by its
  496. .I idf
  497. descriptor and an
  498. .I offset.
  499. This offset is needed for discriminating entries of the same
  500. array and members of the same structure or union, so it is
  501. possible to warn about the statement
  502. .ft CW
  503. a[b[0]]\ =\ b[0]++;.
  504. .R
  505. When \f(CWlint_expr\fP meets a commutative operator (with respect to the
  506. evaluation order), it calls itself recursively with the operands
  507. of the operator as expression.
  508. The returned results are checked for undefined evaluation orders
  509. and are put together.
  510. This is done by the function \f(CWcheck_and_merge\fP.
  511. .NH 3
  512. Useless statements
  513. .PP
  514. Statements which compute a value that is not used,
  515. are said to have a \fInull effect\fP.
  516. Examples are \f(CWx = 2, 3;\fP, \f(CWf() + g();\fP and
  517. \f(CW*p++;\fP.
  518. (\f(CW*\fP and \f(CW++\fP have the same precedence and associate
  519. from right to left.)
  520. .PP
  521. A conditional expression computes a value too.
  522. If this value isn't used, it is better to use an if-else
  523. statement.
  524. So, if
  525. .I lint
  526. sees
  527. .DS B
  528. .ft CW
  529. b ? f() : g();
  530. .R
  531. .DE
  532. .LP
  533. it warns \f(CWuse if-else construction\fP.
  534. .NH 3
  535. Not-reachable statements
  536. .PP
  537. The algorithm to detect not-reachable statements (including not
  538. reachable initializations) is as follows.
  539. Statements after a label and a case statement and the compound
  540. statement of a function are always reachable.
  541. Other statements are not-reachable after:
  542. .QS
  543. .RS
  544. .IP - 1
  545. a goto statement
  546. .IP -
  547. a return statement
  548. .IP -
  549. a break statement
  550. .IP -
  551. a continue statement
  552. .IP -
  553. a switch statement
  554. .IP -
  555. an endless loop (a while, do or for loop with a conditional
  556. which always evaluates to true and without a break statement)
  557. .IP -
  558. an if-else statement of which both if part and else part
  559. end up in a not-reachable state
  560. .IP -
  561. a switch statement of which all \f(CWcase ... break\fP parts
  562. (including
  563. a \f(CWdefault ... break\fP part) end up in a not-reachable state
  564. .IP -
  565. the pseudocomment \f(CW/*\ NOTREACHED\ */\fP
  566. .RE
  567. .QE
  568. .PP
  569. The algorithm is easily implemented using the \f(CWst_nrchd\fP selector
  570. in the
  571. .I state
  572. descriptor.
  573. The \f(CWst_warned\fP selector is used to prevent superfluous warnings.
  574. To detect an endless loop, after a while (<true>), for (..;<true>;..)
  575. and do part the current state of the stack entry beneath the top one
  576. is set to not reached.
  577. If, in the statement following, a break statement is met, this same
  578. state is set to reached.
  579. If the while (<cond>) part of the do statement is met, this state
  580. is set to reached if <cond> doesn't evaluates to true.
  581. The detection of not-reachable statements after a switch statement
  582. is done in a similar way.
  583. In addition it is checked if a default statement isn't met, in
  584. which case the statement after the switch statement can be reached.
  585. The warning \f(CWstatement not reached\fP is not given for compound
  586. statements.
  587. If
  588. .I lint
  589. did, it would warn for the compound statement in a switch statement,
  590. which would be incorrect.
  591. .PP
  592. Not-reachable statements are still interpreted by
  593. .I lint.
  594. I.e. when
  595. .I lint
  596. warns that some statement can't be reached, it assumes this is
  597. not what the programmer really wants and it ignores this fact.
  598. In this way a lot of useless warnings are prevented in the case of
  599. a not-reachable statement.
  600. See figure 5.
  601. .KF
  602. .DS B
  603. .ft CW
  604. {
  605. int i;
  606. for (;;) {
  607. /* A loop in which the programmer
  608. * forgot to introduce a conditional
  609. * break statement.
  610. * Suppose i is not used in this part.
  611. */
  612. }
  613. /* some more code in which i is used */
  614. }
  615. /* The warning "statement not reached" highlights the bug.
  616. * An additional warning "i unused in function %s" is
  617. * formally correct, but doesn't provide the programmer
  618. * with useful information.
  619. */
  620. .DE
  621. .I
  622. .ce
  623. figure\ 5.
  624. .R
  625. .KE
  626. .NH 3
  627. Functions returning expressions and just returning
  628. .PP
  629. Each time a return statement is met,
  630. .I lint
  631. checks if an expression is returned or not.
  632. If a function has a return with expression and a return without
  633. expression,
  634. .I lint
  635. warns
  636. .ft CW
  637. function %s has return(e); and return;.
  638. .R
  639. If the flow of control can
  640. .I
  641. fall through
  642. .R
  643. the end of the compound statement of a function, this indicates
  644. an implicit return statement without an expression.
  645. If the end of the compound statement of the function can be reached,
  646. .I lint
  647. introduces this implicit return statement without expression.
  648. .PP
  649. Sometimes the programmer knows for sure that all case parts inside
  650. a switch statement include all possible cases, so he doesn't
  651. introduce a default statement.
  652. This can lead to an incorrect warning.
  653. Figure 6 shows how to prevent this warning.
  654. .KF
  655. .DS B
  656. .ft CW
  657. func()
  658. {
  659. switch (cond) {
  660. case 0: return(e0);
  661. case 1: return(e1);
  662. }
  663. /* NOTREACHED */
  664. }
  665. /* no warning: "function func has return(e); and return; */
  666. .DE
  667. .I
  668. .ce
  669. figure\ 6.
  670. .R
  671. .KE
  672. .PP
  673. The pseudocomment \f(CW/*\ NOTREACHED\ */\fP can also be used to tell
  674. .I lint
  675. that some function doesn't return. See figure 7.
  676. .KS
  677. .DS B
  678. .ft CW
  679. func()
  680. {
  681. switch (cond) {
  682. case 0: return(e0);
  683. case 1: return(e1);
  684. default: error(); /* calls exit or abort */
  685. /* NOTREACHED */
  686. }
  687. }
  688. /* no warning: "function func has return(e); and return;" */
  689. .I
  690. .DE
  691. .ce
  692. figure\ 7.
  693. .R
  694. .KE
  695. .NH 3
  696. Output definitions for the second pass
  697. .PP
  698. The first pass can only process one program file.
  699. To be able to process a program that spreads over more than one file,
  700. the first pass outputs definitions that are processed by a second
  701. pass.
  702. The format of such a definition is different for different classes:
  703. .PP
  704. For class in {EFDF, SFDF, LFDF}
  705. .DS C
  706. <name>:<class>:<file>:<line>:<nr of args>:<type of args>:<returns value>:<type>
  707. .DE
  708. .LP
  709. A negative \fInr of args\fP indicates that the function can be called with
  710. a varying number of arguments.
  711. .PP
  712. For class = FC
  713. .DS C
  714. <name>:<class>:<file>:<line>:<value is used>:<type>
  715. .DE
  716. .LP
  717. The \fIvalue is used\fP part can have three meanings:
  718. the value of the function is ignored;
  719. the value of the function is used;
  720. the value of the function is cast to type \fIvoid\fP.
  721. .PP
  722. For other classes
  723. .DS C
  724. <name>:<class>:<file>:<line>:<type>
  725. .DE
  726. .LP
  727. Definitions of class VU (Variable Usage) are only output for \fIused\fP
  728. global variables.
  729. .PP
  730. Structure and union types that are output to the intermediate file
  731. are simplified.
  732. (The following occurrences of \fIstructure\fP should be
  733. read as \fIstructure or union\fP and \fIstruct\fP as \fIstruct or
  734. union\fP.)
  735. Structures that are identified by a \fIstructure tag\fP are output
  736. to the intermediate file as \f(CWstruct <tag>\fP.
  737. Structures without a structure tag are output as
  738. \f(CWstruct {<mems>}\fP with \f(CW<mems>\fP a semicolon-separated
  739. list of types of the members of this structure.
  740. An alternative way would be to output the complete structure definition.
  741. However, this gives practical problems.
  742. It is allowed to define some object of a structure type with a
  743. structure tag, without this structure being defined at that place.
  744. The first approach leaves errors, such as in figure 8, undetected.
  745. .KF
  746. .DS B
  747. .ft CW
  748. "a.c" "b.c"
  749. struct str { struct str {
  750. float f; int i;
  751. } s; };
  752. main() func(s)
  753. { struct str s;
  754. func(s); {}
  755. }
  756. .I
  757. .DE
  758. .ce
  759. figure\ 8.
  760. .R
  761. .KE
  762. .PP
  763. To be able to detect these errors, the first pass should also output
  764. definitions of structure tags.
  765. The example of figure 8 would then get a warning like
  766. .ft CW
  767. structure str defined inconsistently
  768. .R
  769. .PP
  770. More information on these definitions in section 4.3 and 4.4.
  771. .NH 3
  772. Generating libraries
  773. .PP
  774. .I Lint
  775. knows the library `-lc', `-lm' and `-lcurses'.
  776. If a program uses some other library, it is possible to generate
  777. a corresponding \fIlint library\fP.
  778. To do this, precede all the C source files of this library by
  779. the pseudocomment \f(CW/*\ LINTLIBRARY\ */\fP.
  780. Then feed these files one by one to the first pass of
  781. .I lint
  782. collecting the standard output in a file and ignoring the warnings.
  783. The resulting file contains library definitions of the functions
  784. and external variables defined in the library sources, and not more
  785. than that.
  786. If this file is called `llib-l\fIname\fP.ln
  787. .I lint
  788. can be told to search the library by passing it as argument in
  789. the command line `-llib-l\fIname\fP.ln.
  790. The implementation of this feature is simple.
  791. .PP
  792. As soon as the pseudocomment \f(CW/*\ LINTLIBRARY\ */\fP is met,
  793. only function and variable definitions are output with class LFDF
  794. and LVDF respectively.
  795. Other definitions, which otherwise would have been output, are
  796. discarded.
  797. .PP
  798. Instead of generating a special lint library file, one can make a
  799. file containing the library definitions and starting with
  800. \f(CW/* LINTLIBRARY */\fP.
  801. This file can then be passed to
  802. .I lint
  803. just by its name.
  804. This method isn't as efficient as the first one.
  805. .NH 3
  806. Interpreting the pseudocomments
  807. .PP
  808. The interpretation of the pseudocomments is done by the lexical
  809. analyzer, because this part of the program already took care of the
  810. comments.
  811. At first sight this seems very easy: as soon as some pseudocomment
  812. is met, raise the corresponding flag.
  813. Unfortunately this doesn't work.
  814. The lexical analyzer is a \fIone token look ahead scanner\fP.
  815. This causes the above procedure to raise the flags one token too
  816. soon.
  817. A solution to get the right effect is to reserve two flags per
  818. pseudocomment.
  819. The first is set as soon as the corresponding pseudocomment is
  820. scanned.
  821. At the returning of each token this flag is moved to the second flag.
  822. The delay in this way achieved makes the pseudocomments have effect
  823. at the correct place.
  824. .NH 2
  825. The second pass data structure
  826. .NH 3
  827. Inp_def descriptor
  828. .DS B
  829. .ft CW
  830. struct inp_def {
  831. struct inp_def *next;
  832. int id_class;
  833. char id_name[NAMESIZE];
  834. char id_file[FNAMESIZE];
  835. unsigned int id_line;
  836. int id_nrargs;
  837. char argtps[ARGSTPSSIZE];
  838. int id_returns;
  839. char id_type[TYPESIZE];
  840. int id_called;
  841. int id_used;
  842. int id_ignored;
  843. int id_voided;
  844. };
  845. .R
  846. .DE
  847. .PP
  848. This description is almost similar to the \fIoutdef\fP descriptor as
  849. described in 4.1.2.5.
  850. There are some differences too.
  851. .IP \f(CWnext\fP 15
  852. As structures of this type are allocated dynamically, this field
  853. is added so the same memory allocator as used in the first pass can be
  854. used.
  855. .LP
  856. \f(CWid_called
  857. .br
  858. id_used
  859. .br
  860. id_ignored\fP
  861. .IP \f(CWid_voided\fP 15
  862. Some additional fields only used for function definitions.Their
  863. meaning should be clear.
  864. .PP
  865. The other fields have the same meaning as the corresponding fields
  866. in the \fIoutdef\fP descriptor.
  867. Some attention should be paid to \f(CWid_argtps\fP and \f(CWid_type\fP.
  868. These members have type \f(CWarray of char\fP, in contrast to
  869. their counterparts in the \fIoutdef\fP descriptor.
  870. The only operation performed on types is a check on equality.
  871. Types are output by the first pass as a string describing the type.
  872. The type of \f(CWi\fP in \f(CWint *i();\fP e.g. is output as
  873. \f(CWint *()\fP.
  874. Such a string is best put in an \f(CWarray of char\fP to be compared
  875. easily.
  876. .NH 2
  877. The second pass checking mechanism
  878. .PP
  879. After all the definitions that are output by the first pass are
  880. sorted by name, the definitions belonging to one name are ordered
  881. as follows.
  882. .QS
  883. .RS
  884. .IP - 1
  885. external definitions
  886. .IP -
  887. static definitions
  888. .IP -
  889. library definitions
  890. .IP -
  891. declarations
  892. .IP -
  893. function calls
  894. .IP -
  895. variable usages
  896. .RE
  897. .QE
  898. .PP
  899. The main program of the second pass is easily explained.
  900. For all different names, do the following.
  901. First read the definitions.
  902. If there is more than one definition, check for conflicts.
  903. Then read the declarations, function calls and variable usages and
  904. check them against the definitions.
  905. After having processed all the declarations, function calls and
  906. variable usages, check the definitions to see if they are used
  907. correctly.
  908. The next three paragraphs will explain the three most important
  909. functions of the program.
  910. .NH 3
  911. Read_defs()
  912. .PP
  913. This function reads all definitions belonging to the same name.
  914. Only one external definition is allowed, so if there are more, a
  915. warning is given.
  916. In different files it is allowed to define static functions or
  917. variables with the same name.
  918. So if a static function is read, \f(CWread_defs\fP checks if there isn't
  919. already an external definition, and if not it puts the static
  920. definition in the list of static definitions, to be used later.
  921. If no external or static definitions are met, a library definition is
  922. taken as definition.
  923. If a function or a variable is defined with the same name as a function
  924. or a variable in a library (which is allowed)
  925. .I lint
  926. gives a warning.
  927. Of course it is also possible that there is no definition at all.
  928. In that case \f(CWcheck\fP will warn.
  929. .NH 3
  930. Check()
  931. .PP
  932. \f(CWCheck\fP verifies declarations, function calls and variable
  933. usages against the definitions.
  934. For each of these entries the corresponding definition is looked up.
  935. As there may be more than one static definition, first a static
  936. definition from the same file as the entry is searched.
  937. If not present, the external definition (which may be a library
  938. definition) is taken as definition.
  939. If no definition can be found and the current entry is an external
  940. declaration,
  941. .I lint
  942. warns.
  943. However in the case of an implicit function declaration
  944. .I lint
  945. will not warn, because
  946. we will get a warning \f(CW%s used but not defined\fP later on.
  947. Next a check is done if the declarations are consistent with their
  948. definitions.
  949. After the declarations, the function calls and variable usages are
  950. verified against their corresponding definitions.
  951. If no definition exists,
  952. .I lint
  953. warns.
  954. Else the field \f(CWid_called\fP is set to 1.
  955. (For variable definitions this should be interpreted as \fIused\fP.)
  956. For variable usages this will be all.
  957. If we are processing a function call we also check the number and types
  958. of the arguments and we warn for function values which are used from
  959. functions that don't return a value.
  960. For each function call we administrate if a function value is used,
  961. ignored or voided.
  962. .NH 3
  963. Check_usage()
  964. .PP
  965. Checks if the external definition and static definitions are used
  966. correctly.
  967. If a function or variable is defined but never used,
  968. .I lint
  969. warns, except for library definitions.
  970. Functions, which return a value but whose value is always or
  971. sometimes ignored, get a warning.
  972. (A function value which is voided (cast to void) is not ignored,
  973. but it isn't used either.)
  974. .bp