1*1f5207b7SJohn Levon /*
2*1f5207b7SJohn Levon * Copyright (C) 2009 Dan Carpenter.
3*1f5207b7SJohn Levon *
4*1f5207b7SJohn Levon * This program is free software; you can redistribute it and/or
5*1f5207b7SJohn Levon * modify it under the terms of the GNU General Public License
6*1f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2
7*1f5207b7SJohn Levon * of the License, or (at your option) any later version.
8*1f5207b7SJohn Levon *
9*1f5207b7SJohn Levon * This program is distributed in the hope that it will be useful,
10*1f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of
11*1f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12*1f5207b7SJohn Levon * GNU General Public License for more details.
13*1f5207b7SJohn Levon *
14*1f5207b7SJohn Levon * You should have received a copy of the GNU General Public License
15*1f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16*1f5207b7SJohn Levon */
17*1f5207b7SJohn Levon
18*1f5207b7SJohn Levon /*
19*1f5207b7SJohn Levon * Check for things which are signed but probably should be unsigned.
20*1f5207b7SJohn Levon *
21*1f5207b7SJohn Levon * Hm... It seems like at this point in the processing, sparse makes all
22*1f5207b7SJohn Levon * bitfields unsigned. Which is logical but not what GCC does.
23*1f5207b7SJohn Levon *
24*1f5207b7SJohn Levon */
25*1f5207b7SJohn Levon
26*1f5207b7SJohn Levon #include "smatch.h"
27*1f5207b7SJohn Levon #include "smatch_extra.h"
28*1f5207b7SJohn Levon
29*1f5207b7SJohn Levon static int my_id;
30*1f5207b7SJohn Levon
31*1f5207b7SJohn Levon #define VAR_ON_RIGHT 0
32*1f5207b7SJohn Levon #define VAR_ON_LEFT 1
33*1f5207b7SJohn Levon
match_assign(struct expression * expr)34*1f5207b7SJohn Levon static void match_assign(struct expression *expr)
35*1f5207b7SJohn Levon {
36*1f5207b7SJohn Levon struct symbol *sym;
37*1f5207b7SJohn Levon sval_t sval;
38*1f5207b7SJohn Levon sval_t max;
39*1f5207b7SJohn Levon sval_t min;
40*1f5207b7SJohn Levon char *left_name, *right_name;
41*1f5207b7SJohn Levon
42*1f5207b7SJohn Levon if (__in_fake_assign)
43*1f5207b7SJohn Levon return;
44*1f5207b7SJohn Levon if (expr->op == SPECIAL_AND_ASSIGN || expr->op == SPECIAL_OR_ASSIGN)
45*1f5207b7SJohn Levon return;
46*1f5207b7SJohn Levon
47*1f5207b7SJohn Levon sym = get_type(expr->left);
48*1f5207b7SJohn Levon if (!sym || sym->type != SYM_BASETYPE) {
49*1f5207b7SJohn Levon //sm_msg("could not get type");
50*1f5207b7SJohn Levon return;
51*1f5207b7SJohn Levon }
52*1f5207b7SJohn Levon if (type_bits(sym) < 0 || type_bits(sym) >= 32) /* max_val limits this */
53*1f5207b7SJohn Levon return;
54*1f5207b7SJohn Levon if (!get_implied_value(expr->right, &sval))
55*1f5207b7SJohn Levon return;
56*1f5207b7SJohn Levon max = sval_type_max(sym);
57*1f5207b7SJohn Levon if (sym != &bool_ctype && sym != &uchar_ctype &&
58*1f5207b7SJohn Levon sval_cmp(max, sval) < 0 &&
59*1f5207b7SJohn Levon !(sval.value < 256 && max.value == 127)) {
60*1f5207b7SJohn Levon left_name = expr_to_str(expr->left);
61*1f5207b7SJohn Levon right_name = expr_to_str(expr->right);
62*1f5207b7SJohn Levon sm_warning("'%s' %s can't fit into %s '%s'",
63*1f5207b7SJohn Levon right_name, sval_to_numstr(sval), sval_to_numstr(max), left_name);
64*1f5207b7SJohn Levon free_string(left_name);
65*1f5207b7SJohn Levon }
66*1f5207b7SJohn Levon min = sval_type_min(sym);
67*1f5207b7SJohn Levon if (sval_cmp_t(&llong_ctype, min, sval) > 0) {
68*1f5207b7SJohn Levon if (min.value == 0 && sval.value == -1) /* assigning -1 to unsigned variables is idiomatic */
69*1f5207b7SJohn Levon return;
70*1f5207b7SJohn Levon if (expr->right->type == EXPR_PREOP && expr->right->op == '~')
71*1f5207b7SJohn Levon return;
72*1f5207b7SJohn Levon if (expr->op == SPECIAL_SUB_ASSIGN || expr->op == SPECIAL_ADD_ASSIGN)
73*1f5207b7SJohn Levon return;
74*1f5207b7SJohn Levon if (sval_positive_bits(sval) == 7)
75*1f5207b7SJohn Levon return;
76*1f5207b7SJohn Levon left_name = expr_to_str(expr->left);
77*1f5207b7SJohn Levon if (min.value == 0) {
78*1f5207b7SJohn Levon sm_warning("assigning %s to unsigned variable '%s'",
79*1f5207b7SJohn Levon sval_to_str(sval), left_name);
80*1f5207b7SJohn Levon } else {
81*1f5207b7SJohn Levon sm_warning("value %s can't fit into %s '%s'",
82*1f5207b7SJohn Levon sval_to_str(sval), sval_to_str(min), left_name);
83*1f5207b7SJohn Levon }
84*1f5207b7SJohn Levon free_string(left_name);
85*1f5207b7SJohn Levon }
86*1f5207b7SJohn Levon }
87*1f5207b7SJohn Levon
cap_gt_zero_and_lt(struct expression * expr)88*1f5207b7SJohn Levon static int cap_gt_zero_and_lt(struct expression *expr)
89*1f5207b7SJohn Levon {
90*1f5207b7SJohn Levon
91*1f5207b7SJohn Levon struct expression *var = expr->left;
92*1f5207b7SJohn Levon struct expression *tmp;
93*1f5207b7SJohn Levon char *name1 = NULL;
94*1f5207b7SJohn Levon char *name2 = NULL;
95*1f5207b7SJohn Levon sval_t known;
96*1f5207b7SJohn Levon int ret = 0;
97*1f5207b7SJohn Levon int i;
98*1f5207b7SJohn Levon
99*1f5207b7SJohn Levon if (!get_value(expr->right, &known) || known.value != 0)
100*1f5207b7SJohn Levon return 0;
101*1f5207b7SJohn Levon
102*1f5207b7SJohn Levon i = 0;
103*1f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
104*1f5207b7SJohn Levon if (!i++)
105*1f5207b7SJohn Levon continue;
106*1f5207b7SJohn Levon if (tmp->op == SPECIAL_LOGICAL_AND) {
107*1f5207b7SJohn Levon struct expression *right = strip_expr(tmp->right);
108*1f5207b7SJohn Levon
109*1f5207b7SJohn Levon if (right->op != '<' &&
110*1f5207b7SJohn Levon right->op != SPECIAL_UNSIGNED_LT &&
111*1f5207b7SJohn Levon right->op != SPECIAL_LTE &&
112*1f5207b7SJohn Levon right->op != SPECIAL_UNSIGNED_LTE)
113*1f5207b7SJohn Levon return 0;
114*1f5207b7SJohn Levon
115*1f5207b7SJohn Levon name1 = expr_to_str(var);
116*1f5207b7SJohn Levon if (!name1)
117*1f5207b7SJohn Levon goto free;
118*1f5207b7SJohn Levon
119*1f5207b7SJohn Levon name2 = expr_to_str(right->left);
120*1f5207b7SJohn Levon if (!name2)
121*1f5207b7SJohn Levon goto free;
122*1f5207b7SJohn Levon if (!strcmp(name1, name2))
123*1f5207b7SJohn Levon ret = 1;
124*1f5207b7SJohn Levon goto free;
125*1f5207b7SJohn Levon
126*1f5207b7SJohn Levon }
127*1f5207b7SJohn Levon return 0;
128*1f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(tmp);
129*1f5207b7SJohn Levon
130*1f5207b7SJohn Levon free:
131*1f5207b7SJohn Levon free_string(name1);
132*1f5207b7SJohn Levon free_string(name2);
133*1f5207b7SJohn Levon return ret;
134*1f5207b7SJohn Levon }
135*1f5207b7SJohn Levon
cap_lt_zero_or_gt(struct expression * expr)136*1f5207b7SJohn Levon static int cap_lt_zero_or_gt(struct expression *expr)
137*1f5207b7SJohn Levon {
138*1f5207b7SJohn Levon
139*1f5207b7SJohn Levon struct expression *var = expr->left;
140*1f5207b7SJohn Levon struct expression *tmp;
141*1f5207b7SJohn Levon char *name1 = NULL;
142*1f5207b7SJohn Levon char *name2 = NULL;
143*1f5207b7SJohn Levon sval_t known;
144*1f5207b7SJohn Levon int ret = 0;
145*1f5207b7SJohn Levon int i;
146*1f5207b7SJohn Levon
147*1f5207b7SJohn Levon if (!get_value(expr->right, &known) || known.value != 0)
148*1f5207b7SJohn Levon return 0;
149*1f5207b7SJohn Levon
150*1f5207b7SJohn Levon i = 0;
151*1f5207b7SJohn Levon FOR_EACH_PTR_REVERSE(big_expression_stack, tmp) {
152*1f5207b7SJohn Levon if (!i++)
153*1f5207b7SJohn Levon continue;
154*1f5207b7SJohn Levon if (tmp->op == SPECIAL_LOGICAL_OR) {
155*1f5207b7SJohn Levon struct expression *right = strip_expr(tmp->right);
156*1f5207b7SJohn Levon
157*1f5207b7SJohn Levon if (right->op != '>' &&
158*1f5207b7SJohn Levon right->op != SPECIAL_UNSIGNED_GT &&
159*1f5207b7SJohn Levon right->op != SPECIAL_GTE &&
160*1f5207b7SJohn Levon right->op != SPECIAL_UNSIGNED_GTE)
161*1f5207b7SJohn Levon return 0;
162*1f5207b7SJohn Levon
163*1f5207b7SJohn Levon name1 = expr_to_str(var);
164*1f5207b7SJohn Levon if (!name1)
165*1f5207b7SJohn Levon goto free;
166*1f5207b7SJohn Levon
167*1f5207b7SJohn Levon name2 = expr_to_str(right->left);
168*1f5207b7SJohn Levon if (!name2)
169*1f5207b7SJohn Levon goto free;
170*1f5207b7SJohn Levon if (!strcmp(name1, name2))
171*1f5207b7SJohn Levon ret = 1;
172*1f5207b7SJohn Levon goto free;
173*1f5207b7SJohn Levon
174*1f5207b7SJohn Levon }
175*1f5207b7SJohn Levon return 0;
176*1f5207b7SJohn Levon } END_FOR_EACH_PTR_REVERSE(tmp);
177*1f5207b7SJohn Levon
178*1f5207b7SJohn Levon free:
179*1f5207b7SJohn Levon free_string(name1);
180*1f5207b7SJohn Levon free_string(name2);
181*1f5207b7SJohn Levon return ret;
182*1f5207b7SJohn Levon }
183*1f5207b7SJohn Levon
cap_both_sides(struct expression * expr)184*1f5207b7SJohn Levon static int cap_both_sides(struct expression *expr)
185*1f5207b7SJohn Levon {
186*1f5207b7SJohn Levon switch (expr->op) {
187*1f5207b7SJohn Levon case '<':
188*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LT:
189*1f5207b7SJohn Levon case SPECIAL_LTE:
190*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_LTE:
191*1f5207b7SJohn Levon return cap_lt_zero_or_gt(expr);
192*1f5207b7SJohn Levon case '>':
193*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_GT:
194*1f5207b7SJohn Levon case SPECIAL_GTE:
195*1f5207b7SJohn Levon case SPECIAL_UNSIGNED_GTE:
196*1f5207b7SJohn Levon return cap_gt_zero_and_lt(expr);
197*1f5207b7SJohn Levon }
198*1f5207b7SJohn Levon return 0;
199*1f5207b7SJohn Levon }
200*1f5207b7SJohn Levon
compare_against_macro(struct expression * expr)201*1f5207b7SJohn Levon static int compare_against_macro(struct expression *expr)
202*1f5207b7SJohn Levon {
203*1f5207b7SJohn Levon sval_t known;
204*1f5207b7SJohn Levon
205*1f5207b7SJohn Levon if (expr->op != SPECIAL_UNSIGNED_LT)
206*1f5207b7SJohn Levon return 0;
207*1f5207b7SJohn Levon
208*1f5207b7SJohn Levon if (!get_value(expr->right, &known) || known.value != 0)
209*1f5207b7SJohn Levon return 0;
210*1f5207b7SJohn Levon return !!get_macro_name(expr->right->pos);
211*1f5207b7SJohn Levon }
212*1f5207b7SJohn Levon
print_unsigned_never_less_than_zero(struct expression * expr)213*1f5207b7SJohn Levon static int print_unsigned_never_less_than_zero(struct expression *expr)
214*1f5207b7SJohn Levon {
215*1f5207b7SJohn Levon sval_t known;
216*1f5207b7SJohn Levon char *name;
217*1f5207b7SJohn Levon
218*1f5207b7SJohn Levon if (expr->op != SPECIAL_UNSIGNED_LT)
219*1f5207b7SJohn Levon return 0;
220*1f5207b7SJohn Levon
221*1f5207b7SJohn Levon if (!get_value(expr->right, &known) || known.value != 0)
222*1f5207b7SJohn Levon return 0;
223*1f5207b7SJohn Levon
224*1f5207b7SJohn Levon name = expr_to_str(expr->left);
225*1f5207b7SJohn Levon sm_warning("unsigned '%s' is never less than zero.", name);
226*1f5207b7SJohn Levon free_string(name);
227*1f5207b7SJohn Levon return 1;
228*1f5207b7SJohn Levon }
229*1f5207b7SJohn Levon
match_condition(struct expression * expr)230*1f5207b7SJohn Levon static void match_condition(struct expression *expr)
231*1f5207b7SJohn Levon {
232*1f5207b7SJohn Levon struct symbol *type;
233*1f5207b7SJohn Levon sval_t known;
234*1f5207b7SJohn Levon sval_t min, max;
235*1f5207b7SJohn Levon struct range_list *rl_left_orig, *rl_right_orig;
236*1f5207b7SJohn Levon struct range_list *rl_left, *rl_right;
237*1f5207b7SJohn Levon
238*1f5207b7SJohn Levon if (expr->type != EXPR_COMPARE)
239*1f5207b7SJohn Levon return;
240*1f5207b7SJohn Levon
241*1f5207b7SJohn Levon type = get_type(expr);
242*1f5207b7SJohn Levon if (!type)
243*1f5207b7SJohn Levon return;
244*1f5207b7SJohn Levon
245*1f5207b7SJohn Levon /* screw it. I am writing this to mark yoda code as buggy.
246*1f5207b7SJohn Levon * Valid comparisons between an unsigned and zero are:
247*1f5207b7SJohn Levon * 1) inside a macro.
248*1f5207b7SJohn Levon * 2) foo < LOWER_BOUND where LOWER_BOUND is a macro.
249*1f5207b7SJohn Levon * 3) foo < 0 || foo > X in exactly this format. No Yoda.
250*1f5207b7SJohn Levon * 4) foo >= 0 && foo < X
251*1f5207b7SJohn Levon */
252*1f5207b7SJohn Levon if (get_macro_name(expr->pos))
253*1f5207b7SJohn Levon return;
254*1f5207b7SJohn Levon if (compare_against_macro(expr))
255*1f5207b7SJohn Levon return;
256*1f5207b7SJohn Levon if (cap_both_sides(expr))
257*1f5207b7SJohn Levon return;
258*1f5207b7SJohn Levon
259*1f5207b7SJohn Levon /* This is a special case for the common error */
260*1f5207b7SJohn Levon if (print_unsigned_never_less_than_zero(expr))
261*1f5207b7SJohn Levon return;
262*1f5207b7SJohn Levon
263*1f5207b7SJohn Levon /* check that one and only one side is known */
264*1f5207b7SJohn Levon if (get_value(expr->left, &known)) {
265*1f5207b7SJohn Levon if (get_value(expr->right, &known))
266*1f5207b7SJohn Levon return;
267*1f5207b7SJohn Levon rl_left_orig = alloc_rl(known, known);
268*1f5207b7SJohn Levon rl_left = cast_rl(type, rl_left_orig);
269*1f5207b7SJohn Levon
270*1f5207b7SJohn Levon min = sval_type_min(get_type(expr->right));
271*1f5207b7SJohn Levon max = sval_type_max(get_type(expr->right));
272*1f5207b7SJohn Levon rl_right_orig = alloc_rl(min, max);
273*1f5207b7SJohn Levon rl_right = cast_rl(type, rl_right_orig);
274*1f5207b7SJohn Levon } else if (get_value(expr->right, &known)) {
275*1f5207b7SJohn Levon rl_right_orig = alloc_rl(known, known);
276*1f5207b7SJohn Levon rl_right = cast_rl(type, rl_right_orig);
277*1f5207b7SJohn Levon
278*1f5207b7SJohn Levon min = sval_type_min(get_type(expr->left));
279*1f5207b7SJohn Levon max = sval_type_max(get_type(expr->left));
280*1f5207b7SJohn Levon rl_left_orig = alloc_rl(min, max);
281*1f5207b7SJohn Levon rl_left = cast_rl(type, rl_left_orig);
282*1f5207b7SJohn Levon } else {
283*1f5207b7SJohn Levon return;
284*1f5207b7SJohn Levon }
285*1f5207b7SJohn Levon
286*1f5207b7SJohn Levon if (!possibly_true_rl(rl_left, expr->op, rl_right)) {
287*1f5207b7SJohn Levon char *name = expr_to_str(expr);
288*1f5207b7SJohn Levon
289*1f5207b7SJohn Levon sm_warning("impossible condition '(%s) => (%s %s %s)'", name,
290*1f5207b7SJohn Levon show_rl(rl_left), show_special(expr->op),
291*1f5207b7SJohn Levon show_rl(rl_right));
292*1f5207b7SJohn Levon free_string(name);
293*1f5207b7SJohn Levon }
294*1f5207b7SJohn Levon
295*1f5207b7SJohn Levon if (!possibly_false_rl(rl_left, expr->op, rl_right)) {
296*1f5207b7SJohn Levon char *name = expr_to_str(expr);
297*1f5207b7SJohn Levon
298*1f5207b7SJohn Levon sm_warning("always true condition '(%s) => (%s %s %s)'", name,
299*1f5207b7SJohn Levon show_rl(rl_left_orig), show_special(expr->op),
300*1f5207b7SJohn Levon show_rl(rl_right_orig));
301*1f5207b7SJohn Levon free_string(name);
302*1f5207b7SJohn Levon }
303*1f5207b7SJohn Levon }
304*1f5207b7SJohn Levon
check_signed(int id)305*1f5207b7SJohn Levon void check_signed(int id)
306*1f5207b7SJohn Levon {
307*1f5207b7SJohn Levon my_id = id;
308*1f5207b7SJohn Levon
309*1f5207b7SJohn Levon add_hook(&match_assign, ASSIGNMENT_HOOK);
310*1f5207b7SJohn Levon add_hook(&match_condition, CONDITION_HOOK);
311*1f5207b7SJohn Levon }
312