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