Commit | Line | Data |
---|---|---|
34e49164 C |
1 | // **************************************************************************** |
2 | // Prelude | |
3 | // **************************************************************************** | |
4 | ||
5 | // Note: some isomorphisms are handled in the engine directly because they | |
6 | // require special support. They can not be easily described with a | |
7 | // XX <=> YY. But some of them have names, so they can be disabled, as for | |
8 | // any other isomorphism rule. That also means that those names can not | |
9 | // be used for regular isomorphism rule. Those reserved rule names are: | |
10 | // - optional_storage | |
11 | // - optional_qualifier | |
12 | // - value_format | |
13 | // See parse_cocci.ml, pattern.ml, transformation.ml. | |
14 | ||
15 | ||
16 | // Note: the order of the rules has some importance. As we don't do a fixpoint, | |
17 | // changing the order may impact the result. For instance, if we have | |
18 | // | |
19 | // iso1 = x+y <=> y+x | |
20 | // iso2 = i++ <=> i=i+1; | |
21 | // | |
22 | // and if | |
23 | // in SP we have i++; | |
24 | // in C we have i=1+i; | |
25 | // | |
26 | // Does the SP matches the C ? | |
27 | // - Yes if iso2 precedes iso1 in this file, | |
28 | // - No otherwise. | |
29 | ||
30 | ||
31 | // **************************************************************************** | |
32 | // Standard C isomorphisms | |
33 | // **************************************************************************** | |
34 | ||
35 | // --------------------------------------------------------------------------- | |
36 | // Spacing (include comments) isomorphisms | |
37 | // --------------------------------------------------------------------------- | |
38 | // They are handled at lex time. | |
39 | ||
40 | // --------------------------------------------------------------------------- | |
41 | // Dataflow isomorphisms (copy propagation, assignments) | |
42 | // --------------------------------------------------------------------------- | |
43 | // They are handled in engine (TODO). | |
44 | ||
45 | ||
46 | // --------------------------------------------------------------------------- | |
47 | // Iso-by-absence (optional qualifier, storage, sign, cast) isomorphisms | |
48 | // --------------------------------------------------------------------------- | |
49 | // Some of them are handled in cocci_vs_c. Some of them handled here. | |
50 | ||
51 | ||
52 | // We would like that | |
53 | // chip = (ak4117_t *)snd_magic_kcalloc(ak4117_t, 0, GFP_KERNEL); | |
54 | // also matches | |
55 | // X = snd_magic_kcalloc(T, 0, C) | |
56 | // | |
57 | // For the moment because the iso is (T) E => E and not <=>, it forces | |
58 | // us to rewrite the SP as X = (T) snd_magic_kcalloc(T, 0, C) | |
59 | ||
60 | Expression | |
61 | @ drop_cast @ | |
62 | expression E; | |
63 | pure type T; | |
64 | @@ | |
65 | ||
66 | // in the following, the space at the beginning of the line is very important! | |
67 | (T)E => E | |
68 | ||
69 | Type | |
70 | @ add_signed @ | |
71 | @@ | |
72 | int => signed int | |
73 | ||
74 | Type | |
75 | @ add_int1 @ | |
76 | @@ | |
77 | unsigned => unsigned int | |
78 | ||
79 | Type | |
80 | @ add_int2 @ | |
81 | @@ | |
82 | signed => signed int | |
83 | ||
84 | ||
85 | // --------------------------------------------------------------------------- | |
86 | // Field isomorphisms | |
87 | // --------------------------------------------------------------------------- | |
88 | // Dereferences | |
89 | ||
90 | ||
91 | // Those iso were introduced for the 'generic program matching' paper, | |
92 | // with sgrep. The idea is that when we want to detect bugs, | |
93 | // we want to detect something like free(X) ... *X | |
94 | // meaning that you try to access something that have been freed. | |
95 | // But *X is not the only way to deference X, there is also | |
96 | // X->fld, hence those iso. | |
97 | ||
98 | // The following don't see like a good idea, because eg fld could be | |
99 | // instantiated in different ways in different places, meaning that the | |
100 | // two occurrences of "*E" would not refer to the same thing at all. | |
101 | // This could be addressed by making E pure, but then I think it would | |
102 | // have no purpose. | |
103 | ||
104 | // Expression | |
105 | // @@ | |
106 | // expression E; | |
107 | // identifier fld; | |
108 | // @@ | |
109 | // | |
110 | // *E => E->fld | |
111 | // | |
112 | // Expression | |
113 | // @@ | |
114 | // expression E; | |
115 | // identifier fld; | |
116 | // @@ | |
117 | // | |
118 | // *E => (E)->fld | |
119 | // | |
120 | // Expression | |
121 | // @@ | |
122 | // expression E,E1; | |
123 | // @@ | |
124 | // | |
125 | // *E => E[E1] | |
126 | ||
127 | // --------------------------------------------------------------------------- | |
128 | // Typedef isomorphisms | |
129 | // --------------------------------------------------------------------------- | |
130 | // They are handled in engine. | |
131 | ||
132 | ||
133 | // --------------------------------------------------------------------------- | |
134 | // Boolean isomorphisms | |
135 | // --------------------------------------------------------------------------- | |
136 | ||
137 | // the space at the beginning of the line is very important! | |
138 | Expression | |
139 | @ not_int1 @ | |
140 | int X; | |
141 | @@ | |
142 | !X => 0 == X | |
143 | ||
144 | // the space at the beginning of the line is very important! | |
145 | Expression | |
146 | @ not_int2 @ | |
147 | int X; | |
148 | @@ | |
149 | !X => X == 0 | |
150 | ||
151 | Expression | |
152 | @ is_zero @ | |
153 | expression X; | |
154 | @@ | |
155 | X == 0 <=> 0 == X => !X | |
156 | ||
157 | Expression | |
158 | @ isnt_zero @ | |
159 | expression X; | |
160 | @@ | |
161 | X != 0 <=> 0 != X => X | |
162 | ||
163 | Expression | |
164 | @ bitor_comm @ | |
165 | expression X,Y; | |
166 | @@ | |
167 | X | Y => Y | X | |
168 | ||
169 | Expression | |
170 | @ bitand_comm @ | |
171 | expression X,Y; | |
172 | @@ | |
173 | X & Y => Y & X | |
174 | ||
faf9a90c C |
175 | // only if side effect free in theory, perhaps makes no sense |
176 | // Expression | |
177 | // @ and_comm @ | |
178 | // expression X,Y; | |
179 | // @@ | |
180 | // X && Y => Y && X | |
34e49164 | 181 | |
faf9a90c C |
182 | // Expression |
183 | // @ or_comm @ | |
184 | // expression X,Y; | |
185 | // @@ | |
186 | // X || Y => Y || X | |
34e49164 C |
187 | |
188 | ||
189 | // --------------------------------------------------------------------------- | |
190 | // Arithmetic isomorphisms | |
191 | // --------------------------------------------------------------------------- | |
192 | //todo: require check side-effect free expression | |
193 | ||
194 | Expression | |
195 | @ plus_comm @ | |
196 | expression X, Y; | |
197 | @@ | |
198 | X + Y => Y + X | |
199 | ||
200 | ||
201 | // needed in kcalloc CE, where have a -kzalloc(c * sizeof(T), E) | |
202 | Expression | |
203 | @ mult_comm @ | |
204 | expression X, Y; | |
205 | @@ | |
206 | X * Y => Y * X | |
207 | ||
208 | Expression | |
209 | @ plus_assoc @ | |
210 | expression X, Y, Z; | |
211 | @@ | |
212 | // note space before ( | |
213 | (X + Y) + Z <=> X + Y + Z | |
214 | ||
215 | Expression | |
216 | @ minus_assoc @ | |
217 | expression X, Y, Z; | |
218 | @@ | |
219 | ||
220 | (X - Y) - Z <=> X - Y - Z | |
221 | ||
222 | Expression | |
223 | @ plus_minus_assoc1 @ | |
224 | expression X, Y, Z; | |
225 | @@ | |
226 | ||
227 | (X + Y) - Z <=> X + Y - Z | |
228 | ||
229 | Expression | |
230 | @ plus_minus_assoc2 @ | |
231 | expression X, Y, Z; | |
232 | @@ | |
233 | ||
234 | (X - Y) + Z <=> X - Y + Z | |
235 | ||
236 | Expression | |
237 | @ times_assoc @ | |
238 | expression X, Y, Z; | |
239 | @@ | |
240 | ||
241 | (X * Y) * Z <=> X * Y * Z | |
242 | ||
243 | Expression | |
244 | @ div_assoc @ | |
245 | expression X, Y, Z; | |
246 | @@ | |
247 | ||
248 | (X / Y) / Z <=> X / Y / Z | |
249 | ||
250 | Expression | |
251 | @ times_div_assoc1 @ | |
252 | expression X, Y, Z; | |
253 | @@ | |
254 | ||
255 | (X * Y) / Z <=> X * Y / Z | |
256 | ||
257 | Expression | |
258 | @ times_div_assoc2 @ | |
259 | expression X, Y, Z; | |
260 | @@ | |
261 | ||
262 | (X / Y) * Z <=> X / Y * Z | |
263 | ||
264 | // --------------------------------------------------------------------------- | |
265 | // Relational isomorphisms | |
266 | // --------------------------------------------------------------------------- | |
267 | ||
268 | Expression | |
269 | @ gtr_lss @ | |
270 | expression X, Y; | |
271 | @@ | |
272 | X < Y <=> Y > X | |
273 | ||
708f4980 C |
274 | Expression |
275 | @ gtr_lss_eq @ | |
276 | expression X, Y; | |
277 | @@ | |
278 | X <= Y <=> Y >= X | |
279 | ||
34e49164 C |
280 | // --------------------------------------------------------------------------- |
281 | // Increment isomorphisms | |
282 | // --------------------------------------------------------------------------- | |
283 | ||
284 | // equivalences between i++, +=1, etc. | |
285 | // note: there is an addition in this SP. | |
286 | Statement | |
287 | @ inc @ | |
288 | identifier i; | |
289 | @@ | |
290 | i++; <=> ++i; <=> i+=1; <=> i=i+1; | |
291 | ||
292 | // I would like to avoid the following rule, but we cant transform a ++i | |
293 | // in i++ everywhere. We can do it only when the instruction is alone, | |
294 | // such as when there is not stuff around it (not as in x = i++) That's why in | |
295 | // the previous iso, we have explicitely force the i++ do be alone with | |
296 | // the ';'. But unfortunately in the last expression of the for there is | |
297 | // no ';' so the previous rule cannot be applied, hence this special | |
298 | // case. | |
299 | ||
300 | Statement | |
301 | @ for_inc @ | |
302 | expression X, Y; | |
303 | statement S; | |
304 | identifier i; | |
305 | @@ | |
306 | for(X;Y;i++) S <=> for(X;Y;++i) S | |
307 | ||
308 | ||
7f004419 C |
309 | // **************************************************************************** |
310 | // gcc specific isomorphisms | |
311 | // **************************************************************************** | |
312 | ||
313 | // likely and unlikely are used to give hints to gcc to improve performance. | |
314 | ||
315 | Expression | |
9f8e26f4 | 316 | @ unlikely @ |
7f004419 C |
317 | expression E; |
318 | @@ | |
319 | ||
320 | unlikely(E) <=> likely(E) => E | |
321 | ||
322 | // --------------------------------------------------------------------------- | |
323 | // Parenthesis isomorphisms | |
324 | // --------------------------------------------------------------------------- | |
325 | //Expression | |
326 | //@@ expression E; @@ | |
327 | // E => (E) | |
328 | //// E => ((E)) | |
329 | ||
330 | // todo: isomorphism avec les () around ? cf sizeof 3. | |
331 | // (E) => E with some conditions. | |
332 | ||
333 | Expression | |
334 | @ paren @ | |
335 | expression E; | |
336 | @@ | |
337 | ||
338 | (E) => E | |
339 | ||
34e49164 C |
340 | // --------------------------------------------------------------------------- |
341 | // Pointer isomorphisms | |
342 | // --------------------------------------------------------------------------- | |
343 | ||
344 | // the space at the beginning of the line is very important! | |
345 | Expression | |
346 | @ not_ptr1 @ | |
347 | expression *X; | |
348 | @@ | |
349 | !X => NULL == X | |
350 | ||
351 | // the space at the beginning of the line is very important! | |
352 | Expression | |
353 | @ not_ptr2 @ | |
354 | expression *X; | |
355 | @@ | |
356 | !X => X == NULL | |
357 | ||
358 | Expression | |
359 | @ is_null @ | |
360 | expression X; | |
361 | @@ | |
362 | X == NULL <=> NULL == X => !X | |
363 | ||
364 | Expression | |
365 | @ isnt_null1 @ | |
366 | expression X; | |
367 | @@ | |
368 | X != NULL <=> NULL != X | |
369 | ||
370 | TestExpression | |
371 | @ isnt_null1 @ | |
372 | expression X; | |
373 | @@ | |
374 | NULL != X => X | |
375 | ||
376 | // pointer arithmetic equivalences | |
377 | ||
378 | // --------------------------------------------------------------------------- | |
379 | // Statement isomorphisms | |
380 | // --------------------------------------------------------------------------- | |
381 | ||
382 | // ---------------- | |
383 | // If | |
384 | // ---------------- | |
385 | ||
386 | Statement | |
387 | @ int_if_test1 @ | |
388 | int X; | |
389 | statement S1, S2; | |
390 | @@ | |
391 | if (X) S1 else S2 => if (X != 0) S1 else S2 <=> if (0 != X) S1 else S2 | |
392 | ||
393 | Statement | |
394 | @ int_if_test2 @ | |
395 | int X; | |
396 | statement S; | |
397 | @@ | |
398 | if (X) S => if (X != 0) S <=> if (0 != X) S | |
399 | ||
400 | Statement | |
401 | @ ptr_if_test1 @ | |
402 | expression *X; | |
403 | statement S1, S2; | |
404 | @@ | |
405 | if (X) S1 else S2 => if (X != NULL) S1 else S2 => if (NULL != X) S1 else S2 | |
406 | ||
407 | Statement | |
408 | @ ptr_if_test2 @ | |
409 | expression *X; | |
410 | statement S; | |
411 | @@ | |
412 | if (X) S => if (X != NULL) S <=> if (NULL != X) S | |
413 | ||
414 | // --------------------------------------------------------------------------- | |
415 | // Value isomorphisms | |
416 | // --------------------------------------------------------------------------- | |
417 | ||
418 | // There is also equal_c_int in cocci_vs_c to dealing with other | |
419 | // integer decimal/hexadecimal isomorphisms. | |
420 | // an argexpression applies only at top level, in the argument of a | |
421 | // function call, or on the right-hand side of an assignment | |
422 | ArgExpression | |
423 | @ zero_multiple_format @ | |
424 | @@ | |
425 | 0 => '\0' | |
426 | ||
34e49164 C |
427 | // **************************************************************************** |
428 | // if structure isomorphisms | |
429 | // **************************************************************************** | |
430 | ||
431 | // these after after the above so that the introduced negation will distribute | |
432 | // properly over the argument to likely/unlikely | |
433 | ||
434 | Statement | |
435 | @ neg_if @ | |
436 | expression X; | |
437 | statement S1, S2; | |
438 | @@ | |
439 | if (X) S1 else S2 => if (!X) S2 else S1 | |
440 | ||
002099fc C |
441 | Statement |
442 | @ ne_if @ | |
443 | expression E1, E2; | |
444 | statement S1, S2; | |
445 | @@ | |
446 | if (E1 != E2) S1 else S2 => if (E1 == E2) S2 else S1 | |
447 | ||
34e49164 C |
448 | Statement |
449 | @ drop_else @ | |
450 | expression E; | |
451 | statement S1; | |
452 | pure statement S2; | |
453 | @@ | |
454 | ||
455 | if (E) S1 else S2 => if (E) S1 | |
456 | ||
457 | Expression | |
458 | @ neg_if_exp @ | |
459 | expression E1, E2, E3; | |
460 | @@ | |
461 | ||
462 | E1 ? E2 : E3 => !E1 ? E3 : E2 | |
463 | ||
464 | ||
465 | // if (X) Y else Z <=> X ? Y : Z sometimes. | |
466 | ||
467 | // ---------------- | |
468 | // Loops | |
469 | // ---------------- | |
470 | ||
471 | // --------------------------------------------------------------------------- | |
472 | // Optional initializers | |
473 | // --------------------------------------------------------------------------- | |
474 | // this is not safe when the declaration is replaced | |
475 | // attempt to indicate that by requiring that Z is context | |
476 | // no optional static/extern for isos | |
477 | Declaration | |
478 | @ decl_init @ | |
479 | type T; | |
480 | context identifier Z; | |
481 | @@ | |
482 | T Z; => T Z = ...; | |
483 | ||
484 | Declaration | |
485 | @ const_decl_init @ | |
486 | type T; | |
487 | identifier Z; | |
488 | constant C; | |
489 | @@ | |
490 | T Z; => T Z = C; | |
491 | ||
492 | Declaration | |
493 | @ extern_decl_init @ | |
494 | type T; | |
495 | context identifier Z; | |
496 | @@ | |
497 | extern T Z; => extern T Z = ...; | |
498 | ||
499 | Declaration | |
500 | @ const_extern_decl_init @ | |
501 | type T; | |
502 | identifier Z; | |
503 | constant C; | |
504 | @@ | |
505 | extern T Z; => extern T Z = C; | |
506 | ||
507 | Declaration | |
508 | @ static_decl_init @ | |
509 | type T; | |
510 | context identifier Z; | |
511 | @@ | |
512 | static T Z; => static T Z = ...; | |
513 | ||
514 | Declaration | |
515 | @ const_static_decl_init @ | |
516 | type T; | |
517 | identifier Z; | |
518 | constant C; | |
519 | @@ | |
520 | static T Z; => static T Z = C; | |
521 | ||
522 | // --------------------------------------------------------------------------- | |
523 | // Branch (or compound) isomorphisms | |
524 | // --------------------------------------------------------------------------- | |
525 | // maybe a cocci patch should require something that looks like what is on | |
526 | // the left above to occur in a if or while | |
527 | ||
528 | // could worry that this has to be a simple statement, but this should work | |
529 | // better as it allows + code on S | |
530 | Statement | |
531 | @ braces1 @ | |
532 | statement S; | |
533 | @@ | |
534 | { ... S } => S | |
535 | ||
536 | Statement | |
537 | @ braces2 @ | |
538 | statement S; | |
539 | @@ | |
540 | { ... S ... } => S | |
541 | ||
542 | Statement | |
543 | @ braces3 @ | |
544 | statement S; | |
545 | @@ | |
546 | { S ... } => S | |
547 | ||
548 | Statement | |
549 | @ braces4 @ | |
550 | statement S; | |
551 | @@ | |
552 | { S } => S | |
553 | ||
554 | Statement | |
555 | @ ret @ | |
556 | @@ | |
557 | return ...; => return; | |
558 | ||
559 | ||
560 | // --------------------------------------------------------------------------- | |
561 | // Declaration isomorphisms | |
562 | // --------------------------------------------------------------------------- | |
563 | // They are handled in engine (TODO) | |
564 | ||
565 | // int i,j,k; <=> int i; int j; int k; | |
566 | ||
567 | ||
568 | // --------------------------------------------------------------------------- | |
569 | // Affectation/initialisation isomorphism | |
570 | // --------------------------------------------------------------------------- | |
571 | // They are handled in engine. | |
572 | // 'X = Y' should also match 'type X = Y'; | |
573 | ||
34e49164 C |
574 | // --------------------------------------------------------------------------- |
575 | // Pointer/Array isomorphisms | |
576 | // --------------------------------------------------------------------------- | |
577 | ||
578 | // pointer arithmetic equivalences | |
579 | // a + x <=> a[x] | |
580 | ||
581 | // --------------------------------------------------------------------------- | |
582 | // Pointer/Field isomorphisms | |
583 | // --------------------------------------------------------------------------- | |
584 | ||
585 | Expression | |
586 | @ ptr_to_array @ | |
587 | expression E1, E2; // was pure, not sure why that's needed, not good for rule27 | |
588 | identifier fld; | |
589 | @@ | |
590 | ||
591 | E1->fld => E1[E2].fld | |
592 | ||
593 | ||
594 | ||
595 | TopLevel | |
596 | @ mkinit @ | |
597 | type T; | |
598 | pure context T E; | |
599 | identifier I; | |
600 | identifier fld; | |
601 | expression E1; | |
602 | @@ | |
603 | ||
604 | E.fld = E1; => T I = { .fld = E1, }; | |
605 | ||
606 | // --------------------------------------------------------------------------- | |
607 | // more pointer field iso | |
608 | // --------------------------------------------------------------------------- | |
609 | ||
610 | // pure means that either the whole field reference expression is dropped, | |
611 | // or E is context code and has no attached + code | |
612 | // not really... pure means matches a unitary unplussed metavariable | |
613 | // but this rule doesn't work anyway | |
614 | ||
615 | Expression | |
616 | @ fld_to_ptr @ | |
617 | type T; | |
618 | pure T E; | |
619 | pure T *E1; | |
620 | identifier fld; | |
621 | @@ | |
622 | ||
623 | E.fld => E1->fld | |
624 | ||
625 | ||
626 | // --------------------------------------------------------------------------- | |
627 | // sizeof isomorphisms | |
628 | // --------------------------------------------------------------------------- | |
629 | ||
faf9a90c C |
630 | // The following is made redundant by the paren isomorphism |
631 | // Expression | |
632 | // @ sizeof_parens @ | |
633 | // expression E; | |
634 | // @@ | |
34e49164 | 635 | |
faf9a90c | 636 | // sizeof(E) => sizeof E |
34e49164 C |
637 | |
638 | ||
639 | Expression | |
640 | @ sizeof_type_expr @ | |
641 | pure type T; // pure because we drop a metavar | |
642 | T E; | |
643 | @@ | |
644 | ||
645 | sizeof(T) => sizeof(E) | |
646 | ||
485bce71 C |
647 | // Expression |
648 | // @ fld_func_call @ | |
649 | // expression list ES; | |
650 | // identifier fld; | |
651 | // expression E; | |
652 | // @@ | |
653 | // E.fld(ES) <=> (*E.fld)(ES) | |
654 | ||
34e49164 C |
655 | |
656 | // **************************************************************************** | |
657 | // Linux specific isomorphisms | |
658 | // **************************************************************************** | |
659 | ||
660 | // Examples: many functions are equivalent/related, and one SP modifying | |
661 | // such a function should also modify the equivalent/related one. | |
662 | ||
663 | ||
664 | // --------------------------------------------------------------------------- | |
665 | // in rule18, needed ? | |
666 | // --------------------------------------------------------------------------- | |
667 | // ( | |
668 | // - test_and_set_bit(ev, &bcs->event); | |
669 | // | | |
670 | // - set_bit(ev, &bcs->event); | |
671 | // | | |
672 | // - bcs->event |= 1 << ev; // the only case that is used | |
673 | ||
674 | ||
675 | // **************************************************************************** | |
676 | // Everything that is required to be in last position, for ugly reasons ... | |
677 | // **************************************************************************** |