check_signed.c

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