1 /*
2  * Copyright (C) 2006 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  * Miscellaneous helper functions.
20  */
21 
22 #include <stdlib.h>
23 #include <stdio.h>
24 #include "allocate.h"
25 #include "smatch.h"
26 #include "smatch_extra.h"
27 #include "smatch_slist.h"
28 
29 #define VAR_LEN 512
30 
alloc_string(const char * str)31 char *alloc_string(const char *str)
32 {
33 	char *tmp;
34 
35 	if (!str)
36 		return NULL;
37 	tmp = malloc(strlen(str) + 1);
38 	strcpy(tmp, str);
39 	return tmp;
40 }
41 
alloc_string_newline(const char * str)42 char *alloc_string_newline(const char *str)
43 {
44 	char *tmp;
45 	int len;
46 
47 	if (!str)
48 		return NULL;
49 	len = strlen(str);
50 	tmp = malloc(len + 2);
51 	snprintf(tmp, len + 2, "%s\n", str);
52 	return tmp;
53 }
54 
free_string(char * str)55 void free_string(char *str)
56 {
57 	free(str);
58 }
59 
remove_parens(char * str)60 void remove_parens(char *str)
61 {
62 	char *src, *dst;
63 
64 	dst = src = str;
65 	while (*src != '\0') {
66 		if (*src == '(' || *src == ')') {
67 			src++;
68 			continue;
69 		}
70 		*dst++ = *src++;
71 	}
72 	*dst = *src;
73 }
74 
alloc_state_num(int num)75 struct smatch_state *alloc_state_num(int num)
76 {
77 	struct smatch_state *state;
78 	static char buff[256];
79 
80 	state = __alloc_smatch_state(0);
81 	snprintf(buff, 255, "%d", num);
82 	buff[255] = '\0';
83 	state->name = alloc_string(buff);
84 	state->data = INT_PTR(num);
85 	return state;
86 }
87 
alloc_state_str(const char * name)88 struct smatch_state *alloc_state_str(const char *name)
89 {
90 	struct smatch_state *state;
91 
92 	state = __alloc_smatch_state(0);
93 	state->name = alloc_string(name);
94 	return state;
95 }
96 
merge_str_state(struct smatch_state * s1,struct smatch_state * s2)97 struct smatch_state *merge_str_state(struct smatch_state *s1, struct smatch_state *s2)
98 {
99 	if (!s1->name || !s2->name)
100 		return &merged;
101 	if (strcmp(s1->name, s2->name) == 0)
102 		return s1;
103 	return &merged;
104 }
105 
alloc_state_expr(struct expression * expr)106 struct smatch_state *alloc_state_expr(struct expression *expr)
107 {
108 	struct smatch_state *state;
109 	char *name;
110 
111 	expr = strip_expr(expr);
112 	name = expr_to_str(expr);
113 	if (!name)
114 		return NULL;
115 
116 	state = __alloc_smatch_state(0);
117 	state->name = alloc_sname(name);
118 	free_string(name);
119 	state->data = expr;
120 	return state;
121 }
122 
append(char * dest,const char * data,int buff_len)123 void append(char *dest, const char *data, int buff_len)
124 {
125 	strncat(dest, data, buff_len - strlen(dest) - 1);
126 }
127 
128 /*
129  * If you have "foo(a, b, 1);" then use
130  * get_argument_from_call_expr(expr, 0) to return the expression for
131  * a.  Yes, it does start counting from 0.
132  */
get_argument_from_call_expr(struct expression_list * args,int num)133 struct expression *get_argument_from_call_expr(struct expression_list *args,
134 					       int num)
135 {
136 	struct expression *expr;
137 	int i = 0;
138 
139 	if (!args)
140 		return NULL;
141 
142 	FOR_EACH_PTR(args, expr) {
143 		if (i == num)
144 			return expr;
145 		i++;
146 	} END_FOR_EACH_PTR(expr);
147 	return NULL;
148 }
149 
get_array_expr(struct expression * expr)150 struct expression *get_array_expr(struct expression *expr)
151 {
152 	struct expression *parent;
153 	struct symbol *type;
154 
155 	if (expr->type != EXPR_BINOP || expr->op != '+')
156 		return NULL;
157 
158 	type = get_type(expr->left);
159 	if (!type)
160 		return NULL;
161 	if (type->type == SYM_ARRAY)
162 		return expr->left;
163 	if (type->type != SYM_PTR)
164 		return NULL;
165 
166 	parent = expr_get_parent_expr(expr);
167 	if (!parent)  /* Sometimes we haven't set up the ->parent yet. FIXME!! */
168 		return expr->left;
169 	if (parent->type == EXPR_PREOP && parent->op == '*')
170 		return expr->left;
171 
172 	return NULL;
173 }
174 
__get_variable_from_expr(struct symbol ** sym_ptr,char * buf,struct expression * expr,int len,int * complicated)175 static void __get_variable_from_expr(struct symbol **sym_ptr, char *buf,
176 				     struct expression *expr, int len,
177 				     int *complicated)
178 {
179 	if (!expr) {
180 		/* can't happen on valid code */
181 		*complicated = 1;
182 		return;
183 	}
184 
185 	switch (expr->type) {
186 	case EXPR_DEREF: {
187 		struct expression *deref;
188 		int op;
189 
190 		deref = expr->deref;
191 		op = deref->op;
192 		if (deref->type == EXPR_PREOP && op == '*') {
193 			struct expression *unop = strip_expr(deref->unop);
194 
195 			if (unop->type == EXPR_PREOP && unop->op == '&') {
196 				deref = unop->unop;
197 				op = '.';
198 			} else {
199 				if (!is_pointer(deref) && !is_pointer(deref->unop))
200 					op = '.';
201 				deref = deref->unop;
202 			}
203 		}
204 
205 		__get_variable_from_expr(sym_ptr, buf, deref, len, complicated);
206 
207 		if (op == '*')
208 			append(buf, "->", len);
209 		else
210 			append(buf, ".", len);
211 
212 		if (expr->member)
213 			append(buf, expr->member->name, len);
214 		else
215 			append(buf, "unknown_member", len);
216 
217 		return;
218 	}
219 	case EXPR_SYMBOL:
220 		if (expr->symbol_name)
221 			append(buf, expr->symbol_name->name, len);
222 		if (sym_ptr) {
223 			if (*sym_ptr)
224 				*complicated = 1;
225 			*sym_ptr = expr->symbol;
226 		}
227 		return;
228 	case EXPR_PREOP: {
229 		const char *tmp;
230 
231 		if (get_expression_statement(expr)) {
232 			*complicated = 2;
233 			return;
234 		}
235 
236 		if (expr->op == '(') {
237 			if (expr->unop->type != EXPR_SYMBOL)
238 				append(buf, "(", len);
239 		} else if (expr->op != '*' || !get_array_expr(expr->unop)) {
240 			tmp = show_special(expr->op);
241 			append(buf, tmp, len);
242 		}
243 		__get_variable_from_expr(sym_ptr, buf, expr->unop,
244 						 len, complicated);
245 
246 		if (expr->op == '(' && expr->unop->type != EXPR_SYMBOL)
247 			append(buf, ")", len);
248 
249 		if (expr->op == SPECIAL_DECREMENT ||
250 		    expr->op == SPECIAL_INCREMENT)
251 			*complicated = 1;
252 
253 		return;
254 	}
255 	case EXPR_POSTOP: {
256 		const char *tmp;
257 
258 		__get_variable_from_expr(sym_ptr, buf, expr->unop,
259 						 len, complicated);
260 		tmp = show_special(expr->op);
261 		append(buf, tmp, len);
262 
263 		if (expr->op == SPECIAL_DECREMENT || expr->op == SPECIAL_INCREMENT)
264 			*complicated = 1;
265 		return;
266 	}
267 	case EXPR_ASSIGNMENT:
268 	case EXPR_COMPARE:
269 	case EXPR_LOGICAL:
270 	case EXPR_BINOP: {
271 		char tmp[10];
272 		struct expression *array_expr;
273 
274 		*complicated = 1;
275 		array_expr = get_array_expr(expr);
276 		if (array_expr) {
277 			__get_variable_from_expr(sym_ptr, buf, array_expr, len, complicated);
278 			append(buf, "[", len);
279 		} else {
280 			__get_variable_from_expr(sym_ptr, buf, expr->left, len, complicated);
281 			snprintf(tmp, sizeof(tmp), " %s ", show_special(expr->op));
282 			append(buf, tmp, len);
283 		}
284 		__get_variable_from_expr(NULL, buf, expr->right, len, complicated);
285 		if (array_expr)
286 			append(buf, "]", len);
287 		return;
288 	}
289 	case EXPR_VALUE: {
290 		sval_t sval = {};
291 		char tmp[25];
292 
293 		*complicated = 1;
294 		if (!get_value(expr, &sval))
295 			return;
296 		snprintf(tmp, 25, "%s", sval_to_numstr(sval));
297 		append(buf, tmp, len);
298 		return;
299 	}
300 	case EXPR_FVALUE: {
301 		sval_t sval = {};
302 		char tmp[25];
303 
304 		*complicated = 1;
305 		if (!get_value(expr, &sval))
306 			return;
307 		snprintf(tmp, 25, "%s", sval_to_numstr(sval));
308 		append(buf, tmp, len);
309 		return;
310 	}
311 	case EXPR_STRING:
312 		append(buf, "\"", len);
313 		if (expr->string)
314 			append(buf, expr->string->data, len);
315 		append(buf, "\"", len);
316 		return;
317 	case EXPR_CALL: {
318 		struct expression *tmp;
319 		int i;
320 
321 		*complicated = 1;
322 		__get_variable_from_expr(NULL, buf, expr->fn, len, complicated);
323 		append(buf, "(", len);
324 		i = 0;
325 		FOR_EACH_PTR(expr->args, tmp) {
326 			if (i++)
327 				append(buf, ", ", len);
328 			__get_variable_from_expr(NULL, buf, tmp, len, complicated);
329 		} END_FOR_EACH_PTR(tmp);
330 		append(buf, ")", len);
331 		return;
332 	}
333 	case EXPR_CAST:
334 	case EXPR_FORCE_CAST:
335 		__get_variable_from_expr(sym_ptr, buf,
336 					 expr->cast_expression, len,
337 					 complicated);
338 		return;
339 	case EXPR_SIZEOF: {
340 		sval_t sval;
341 		int size;
342 		char tmp[25];
343 
344 		if (expr->cast_type && get_base_type(expr->cast_type)) {
345 			size = type_bytes(get_base_type(expr->cast_type));
346 			snprintf(tmp, 25, "%d", size);
347 			append(buf, tmp, len);
348 		} else if (get_value(expr, &sval)) {
349 			snprintf(tmp, 25, "%s", sval_to_str(sval));
350 			append(buf, tmp, len);
351 		}
352 		return;
353 	}
354 	case EXPR_IDENTIFIER:
355 		*complicated = 1;
356 		if (expr->expr_ident)
357 			append(buf, expr->expr_ident->name, len);
358 		return;
359 	case EXPR_SELECT:
360 	case EXPR_CONDITIONAL:
361 		*complicated = 1;
362 		append(buf, "(", len);
363 		__get_variable_from_expr(NULL, buf, expr->conditional, len, complicated);
364 		append(buf, ") ?", len);
365 		if (expr->cond_true)
366 			__get_variable_from_expr(NULL, buf, expr->cond_true, len, complicated);
367 		append(buf, ":", len);
368 		__get_variable_from_expr(NULL, buf, expr->cond_false, len, complicated);
369 		return;
370 	default: {
371 			char tmp[64];
372 
373 			snprintf(tmp, sizeof(tmp), "$expr_%p(%d)", expr, expr->type);
374 			append(buf, tmp, len);
375 			*complicated = 1;
376 		}
377 		return;
378 	}
379 }
380 
381 struct expr_str_cache_results {
382 	struct expression *expr;
383 	char str[VAR_LEN];
384 	struct symbol *sym;
385 	int complicated;
386 };
387 
get_variable_from_expr(struct symbol ** sym_ptr,char * buf,struct expression * expr,int len,int * complicated)388 static void get_variable_from_expr(struct symbol **sym_ptr, char *buf,
389 				     struct expression *expr, int len,
390 				     int *complicated)
391 {
392 	static struct expr_str_cache_results cached[8];
393 	struct symbol *tmp_sym = NULL;
394 	static int idx;
395 	int i;
396 
397 	for (i = 0; i < ARRAY_SIZE(cached); i++) {
398 		if (expr == cached[i].expr) {
399 			strncpy(buf, cached[i].str, len);
400 			if (sym_ptr)
401 				*sym_ptr = cached[i].sym;
402 			*complicated = cached[i].complicated;
403 			return;
404 		}
405 	}
406 
407 	__get_variable_from_expr(&tmp_sym, buf, expr, len, complicated);
408 	if (sym_ptr)
409 		*sym_ptr = tmp_sym;
410 
411 	if (expr->smatch_flags & Tmp)
412 		return;
413 
414 	cached[idx].expr = expr;
415 	strncpy(cached[idx].str, buf, VAR_LEN);
416 	cached[idx].sym = tmp_sym;
417 	cached[idx].complicated = *complicated;
418 
419 	idx = (idx + 1) % ARRAY_SIZE(cached);
420 }
421 
422 /*
423  * This is returns a stylized "c looking" representation of the
424  * variable name.
425  *
426  * It uses the same buffer every time so you have to save the result
427  * yourself if you want to keep it.
428  *
429  */
430 
expr_to_str_sym(struct expression * expr,struct symbol ** sym_ptr)431 char *expr_to_str_sym(struct expression *expr, struct symbol **sym_ptr)
432 {
433 	static char var_name[VAR_LEN];
434 	int complicated = 0;
435 
436 	if (sym_ptr)
437 		*sym_ptr = NULL;
438 	var_name[0] = '\0';
439 
440 	if (!expr)
441 		return NULL;
442 	get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
443 			       &complicated);
444 	if (complicated < 2)
445 		return alloc_string(var_name);
446 	else
447 		return NULL;
448 }
449 
expr_to_str(struct expression * expr)450 char *expr_to_str(struct expression *expr)
451 {
452 	return expr_to_str_sym(expr, NULL);
453 }
454 
455 /*
456  * get_variable_from_expr_simple() only returns simple variables.
457  * If it's a complicated variable like a->foo[x] instead of just 'a->foo'
458  * then it returns NULL.
459  */
expr_to_var_sym(struct expression * expr,struct symbol ** sym_ptr)460 char *expr_to_var_sym(struct expression *expr,
461 				    struct symbol **sym_ptr)
462 {
463 	static char var_name[VAR_LEN];
464 	int complicated = 0;
465 
466 	if (sym_ptr)
467 		*sym_ptr = NULL;
468 	var_name[0] = '\0';
469 
470 	if (!expr)
471 		return NULL;
472 	expr = strip_expr(expr);
473 	get_variable_from_expr(sym_ptr, var_name, expr, sizeof(var_name),
474 			       &complicated);
475 
476 	if (complicated) {
477 		if (sym_ptr)
478 			*sym_ptr = NULL;
479 		return NULL;
480 	}
481 	return alloc_string(var_name);
482 }
483 
expr_to_var(struct expression * expr)484 char *expr_to_var(struct expression *expr)
485 {
486 	return expr_to_var_sym(expr, NULL);
487 }
488 
expr_to_sym(struct expression * expr)489 struct symbol *expr_to_sym(struct expression *expr)
490 {
491 	struct symbol *sym;
492 	char *name;
493 
494 	name = expr_to_var_sym(expr, &sym);
495 	free_string(name);
496 	return sym;
497 }
498 
get_complication_score(struct expression * expr)499 int get_complication_score(struct expression *expr)
500 {
501 	expr = strip_expr(expr);
502 
503 	/*
504 	 * Don't forget to keep get_complication_score() and store_all_links()
505 	 * in sync.
506 	 *
507 	 */
508 
509 	if (!expr)
510 		return 990;
511 
512 	switch (expr->type) {
513 	case EXPR_CALL:
514 		return 991;
515 	case EXPR_COMPARE:
516 	case EXPR_BINOP:
517 		return get_complication_score(expr->left) +
518 		       get_complication_score(expr->right);
519 	case EXPR_SYMBOL:
520 		return 1;
521 	case EXPR_PREOP:
522 		if (expr->op == '*' || expr->op == '(')
523 			return get_complication_score(expr->unop);
524 		return 993;
525 	case EXPR_DEREF:
526 		return get_complication_score(expr->deref);
527 	case EXPR_VALUE:
528 	case EXPR_SIZEOF:
529 		return 0;
530 	default:
531 		return 994;
532 	}
533 }
534 
reorder_expr_alphabetically(struct expression * expr)535 struct expression *reorder_expr_alphabetically(struct expression *expr)
536 {
537 	struct expression *ret;
538 	char *left, *right;
539 
540 	if (expr->type != EXPR_BINOP)
541 		return expr;
542 	if (expr->op != '+' && expr->op != '*')
543 		return expr;
544 
545 	left = expr_to_var(expr->left);
546 	right = expr_to_var(expr->right);
547 	ret = expr;
548 	if (!left || !right)
549 		goto free;
550 	if (strcmp(left, right) <= 0)
551 		goto free;
552 
553 	ret = binop_expression(expr->right, expr->op, expr->left);
554 free:
555 	free_string(left);
556 	free_string(right);
557 
558 	return ret;
559 }
560 
expr_to_chunk_helper(struct expression * expr,struct symbol ** sym,struct var_sym_list ** vsl)561 char *expr_to_chunk_helper(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
562 {
563 	struct var_sym_list *tmp_vsl;
564 	char *name;
565 	struct symbol *tmp;
566 	int score;
567 
568 	if (vsl)
569 		*vsl = NULL;
570 	if (sym)
571 		*sym = NULL;
572 
573 	expr = strip_parens(expr);
574 	if (!expr)
575 		return NULL;
576 
577 	name = expr_to_var_sym(expr, &tmp);
578 	if (name && tmp) {
579 		if (sym)
580 			*sym = tmp;
581 		if (vsl)
582 			add_var_sym(vsl, name, tmp);
583 		return name;
584 	}
585 	free_string(name);
586 
587 	score = get_complication_score(expr);
588 	if (score <= 0 || score > 2)
589 		return NULL;
590 
591 	tmp_vsl = expr_to_vsl(expr);
592 	if (vsl) {
593 		*vsl = tmp_vsl;
594 		if (!*vsl)
595 			return NULL;
596 	}
597 	if (sym) {
598 		if (ptr_list_size((struct ptr_list *)tmp_vsl) == 1) {
599 			struct var_sym *vs;
600 
601 			vs = first_ptr_list((struct ptr_list *)tmp_vsl);
602 			*sym = vs->sym;
603 		}
604 	}
605 
606 	expr = reorder_expr_alphabetically(expr);
607 
608 	return expr_to_str(expr);
609 }
610 
expr_to_known_chunk_sym(struct expression * expr,struct symbol ** sym)611 char *expr_to_known_chunk_sym(struct expression *expr, struct symbol **sym)
612 {
613 	return expr_to_chunk_helper(expr, sym, NULL);
614 }
615 
expr_to_chunk_sym_vsl(struct expression * expr,struct symbol ** sym,struct var_sym_list ** vsl)616 char *expr_to_chunk_sym_vsl(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
617 {
618 	return expr_to_chunk_helper(expr, sym, vsl);
619 }
620 
sym_name_is(const char * name,struct expression * expr)621 int sym_name_is(const char *name, struct expression *expr)
622 {
623 	if (!expr)
624 		return 0;
625 	if (expr->type != EXPR_SYMBOL)
626 		return 0;
627 	if (!strcmp(expr->symbol_name->name, name))
628 		return 1;
629 	return 0;
630 }
631 
expr_is_zero(struct expression * expr)632 int expr_is_zero(struct expression *expr)
633 {
634 	sval_t sval;
635 
636 	if (get_value(expr, &sval) && sval.value == 0)
637 		return 1;
638 	return 0;
639 }
640 
is_array(struct expression * expr)641 int is_array(struct expression *expr)
642 {
643 	struct symbol *type;
644 
645 	expr = strip_expr(expr);
646 	if (!expr)
647 		return 0;
648 
649 	if (expr->type == EXPR_PREOP && expr->op == '*') {
650 		expr = strip_expr(expr->unop);
651 		if (!expr)
652 			return 0;
653 		if (expr->type == EXPR_BINOP && expr->op == '+')
654 			return 1;
655 	}
656 
657 	if (expr->type != EXPR_BINOP || expr->op != '+')
658 		return 0;
659 
660 	type = get_type(expr->left);
661 	if (!type || type->type != SYM_ARRAY)
662 		return 0;
663 
664 	return 1;
665 }
666 
get_array_base(struct expression * expr)667 struct expression *get_array_base(struct expression *expr)
668 {
669 	if (!is_array(expr))
670 		return NULL;
671 	expr = strip_expr(expr);
672 	if (expr->type == EXPR_PREOP && expr->op == '*')
673 		expr = strip_expr(expr->unop);
674 	if (expr->type != EXPR_BINOP || expr->op != '+')
675 		return NULL;
676 	return strip_parens(expr->left);
677 }
678 
get_array_offset(struct expression * expr)679 struct expression *get_array_offset(struct expression *expr)
680 {
681 	if (!is_array(expr))
682 		return NULL;
683 	expr = strip_expr(expr);
684 	if (expr->type == EXPR_PREOP && expr->op == '*')
685 		expr = strip_expr(expr->unop);
686 	if (expr->type != EXPR_BINOP || expr->op != '+')
687 		return NULL;
688 	return strip_parens(expr->right);
689 }
690 
show_state(struct smatch_state * state)691 const char *show_state(struct smatch_state *state)
692 {
693 	if (!state)
694 		return NULL;
695 	return state->name;
696 }
697 
get_expression_statement(struct expression * expr)698 struct statement *get_expression_statement(struct expression *expr)
699 {
700 	/* What are those things called? if (({....; ret;})) { ...*/
701 
702 	if (expr->type != EXPR_PREOP)
703 		return NULL;
704 	if (expr->op != '(')
705 		return NULL;
706 	if (!expr->unop)
707 		return NULL;
708 	if (expr->unop->type != EXPR_STATEMENT)
709 		return NULL;
710 	if (expr->unop->statement->type != STMT_COMPOUND)
711 		return NULL;
712 	return expr->unop->statement;
713 }
714 
strip_parens(struct expression * expr)715 struct expression *strip_parens(struct expression *expr)
716 {
717 	if (!expr)
718 		return NULL;
719 
720 	if (expr->type == EXPR_PREOP) {
721 		if (!expr->unop)
722 			return expr;  /* parsing invalid code */
723 
724 		if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
725 			expr->unop->statement->type == STMT_COMPOUND)
726 			return expr;
727 		if (expr->op == '(')
728 			return strip_parens(expr->unop);
729 	}
730 	return expr;
731 }
732 
strip_expr_helper(struct expression * expr,bool set_parent)733 static struct expression *strip_expr_helper(struct expression *expr, bool set_parent)
734 {
735 	if (!expr)
736 		return NULL;
737 
738 	switch (expr->type) {
739 	case EXPR_FORCE_CAST:
740 	case EXPR_CAST:
741 		if (set_parent)
742 			expr_set_parent_expr(expr->cast_expression, expr);
743 
744 		if (!expr->cast_expression)
745 			return expr;
746 		return strip_expr_helper(expr->cast_expression, set_parent);
747 	case EXPR_PREOP: {
748 		struct expression *unop;
749 
750 		if (!expr->unop)  /* parsing invalid code */
751 			return expr;
752 		if (set_parent)
753 			expr_set_parent_expr(expr->unop, expr);
754 
755 
756 		if (expr->op == '(' && expr->unop->type == EXPR_STATEMENT &&
757 			expr->unop->statement->type == STMT_COMPOUND)
758 			return expr;
759 
760 		unop = strip_expr_helper(expr->unop, set_parent);
761 
762 		if (expr->op == '*' && unop &&
763 		    unop->type == EXPR_PREOP && unop->op == '&') {
764 			struct symbol *type = get_type(unop->unop);
765 
766 			if (type && type->type == SYM_ARRAY)
767 				return expr;
768 			return strip_expr_helper(unop->unop, set_parent);
769 		}
770 
771 		if (expr->op == '(')
772 			return unop;
773 
774 		return expr;
775 	}
776 	case EXPR_CONDITIONAL:
777 		if (known_condition_true(expr->conditional)) {
778 			if (expr->cond_true) {
779 				if (set_parent)
780 					expr_set_parent_expr(expr->cond_true, expr);
781 				return strip_expr_helper(expr->cond_true, set_parent);
782 			}
783 			if (set_parent)
784 				expr_set_parent_expr(expr->conditional, expr);
785 			return strip_expr_helper(expr->conditional, set_parent);
786 		}
787 		if (known_condition_false(expr->conditional)) {
788 			if (set_parent)
789 				expr_set_parent_expr(expr->cond_false, expr);
790 			return strip_expr_helper(expr->cond_false, set_parent);
791 		}
792 		return expr;
793 	case EXPR_CALL:
794 		if (sym_name_is("__builtin_expect", expr->fn) ||
795 		    sym_name_is("__builtin_bswap16", expr->fn) ||
796 		    sym_name_is("__builtin_bswap32", expr->fn) ||
797 		    sym_name_is("__builtin_bswap64", expr->fn)) {
798 			expr = get_argument_from_call_expr(expr->args, 0);
799 			return strip_expr_helper(expr, set_parent);
800 		}
801 		return expr;
802 	}
803 	return expr;
804 }
805 
strip_expr(struct expression * expr)806 struct expression *strip_expr(struct expression *expr)
807 {
808 	return strip_expr_helper(expr, false);
809 }
810 
strip_expr_set_parent(struct expression * expr)811 struct expression *strip_expr_set_parent(struct expression *expr)
812 {
813 	return strip_expr_helper(expr, true);
814 }
815 
delete_state_tracker(struct tracker * t)816 static void delete_state_tracker(struct tracker *t)
817 {
818 	delete_state(t->owner, t->name, t->sym);
819 	__free_tracker(t);
820 }
821 
scoped_state(int my_id,const char * name,struct symbol * sym)822 void scoped_state(int my_id, const char *name, struct symbol *sym)
823 {
824 	struct tracker *t;
825 
826 	t = alloc_tracker(my_id, name, sym);
827 	add_scope_hook((scope_hook *)&delete_state_tracker, t);
828 }
829 
is_error_return(struct expression * expr)830 int is_error_return(struct expression *expr)
831 {
832 	struct symbol *cur_func = cur_func_sym;
833 	struct range_list *rl;
834 	sval_t sval;
835 
836 	if (!expr)
837 		return 0;
838 	if (cur_func->type != SYM_NODE)
839 		return 0;
840 	cur_func = get_base_type(cur_func);
841 	if (cur_func->type != SYM_FN)
842 		return 0;
843 	cur_func = get_base_type(cur_func);
844 	if (cur_func == &void_ctype)
845 		return 0;
846 	if (option_project == PROJ_KERNEL &&
847 	    get_implied_rl(expr, &rl) &&
848 	    rl_type(rl) == &int_ctype &&
849 	    sval_is_negative(rl_min(rl)) &&
850 	    rl_max(rl).value == -1)
851 		return 1;
852 	if (!get_implied_value(expr, &sval))
853 		return 0;
854 	if (sval.value < 0)
855 		return 1;
856 	if (cur_func->type == SYM_PTR && sval.value == 0)
857 		return 1;
858 	return 0;
859 }
860 
getting_address(struct expression * expr)861 int getting_address(struct expression *expr)
862 {
863 	int deref_count = 0;
864 
865 	while ((expr = expr_get_parent_expr(expr))) {
866 		if (expr->type == EXPR_PREOP && expr->op == '*') {
867 			/* &foo->bar->baz dereferences "foo->bar" */
868 			if (deref_count == 0)
869 				deref_count++;
870 			return false;
871 		}
872 		if (expr->type == EXPR_PREOP && expr->op == '&')
873 			return true;
874 	}
875 	return false;
876 }
877 
get_struct_and_member(struct expression * expr,const char ** type,const char ** member)878 int get_struct_and_member(struct expression *expr, const char **type, const char **member)
879 {
880 	struct symbol *sym;
881 
882 	expr = strip_expr(expr);
883 	if (expr->type != EXPR_DEREF)
884 		return 0;
885 	if (!expr->member)
886 		return 0;
887 
888 	sym = get_type(expr->deref);
889 	if (!sym)
890 		return 0;
891 	if (sym->type == SYM_UNION)
892 		return 0;
893 	if (!sym->ident)
894 		return 0;
895 
896 	*type = sym->ident->name;
897 	*member = expr->member->name;
898 	return 1;
899 }
900 
get_member_name(struct expression * expr)901 char *get_member_name(struct expression *expr)
902 {
903 	char buf[256];
904 	struct symbol *sym;
905 
906 	expr = strip_expr(expr);
907 	if (!expr || expr->type != EXPR_DEREF)
908 		return NULL;
909 	if (!expr->member)
910 		return NULL;
911 
912 	sym = get_type(expr->deref);
913 	if (!sym)
914 		return NULL;
915 	if (sym->type == SYM_UNION) {
916 		snprintf(buf, sizeof(buf), "(union %s)->%s",
917 			 sym->ident ? sym->ident->name : "anonymous",
918 			 expr->member->name);
919 		return alloc_string(buf);
920 	}
921 	if (!sym->ident) {
922 		struct expression *deref;
923 		char *full, *outer;
924 		int len;
925 
926 		/*
927 		 * If we're in an anonymous struct then maybe we can find an
928 		 * outer struct name to use as a name.  This code should be
929 		 * recursive and cleaner.  I am not very proud of it.
930 		 *
931 		 */
932 
933 		deref = expr->deref;
934 		if (deref->type != EXPR_DEREF || !deref->member)
935 			return NULL;
936 		sym = get_type(deref->deref);
937 		if (!sym || sym->type != SYM_STRUCT || !sym->ident)
938 			return NULL;
939 
940 		full = expr_to_str(expr);
941 		if (!full)
942 			return NULL;
943 		deref = deref->deref;
944 		if (deref->type == EXPR_PREOP && deref->op == '*')
945 			deref = deref->unop;
946 		outer = expr_to_str(deref);
947 		if (!outer) {
948 			free_string(full);
949 			return NULL;
950 		}
951 		len = strlen(outer);
952 		if (strncmp(outer, full, len) != 0) {
953 			free_string(full);
954 			free_string(outer);
955 			return NULL;
956 		}
957 		if (full[len] == '-' && full[len + 1] == '>')
958 			len += 2;
959 		if (full[len] == '.')
960 			len++;
961 		snprintf(buf, sizeof(buf), "(struct %s)->%s", sym->ident->name, full + len);
962 		free_string(outer);
963 		free_string(full);
964 
965 		return alloc_string(buf);
966 	}
967 	snprintf(buf, sizeof(buf), "(struct %s)->%s", sym->ident->name, expr->member->name);
968 	return alloc_string(buf);
969 }
970 
cmp_pos(struct position pos1,struct position pos2)971 int cmp_pos(struct position pos1, struct position pos2)
972 {
973 	/* the stream position is ... */
974 	if (pos1.stream > pos2.stream)
975 		return -1;
976 	if (pos1.stream < pos2.stream)
977 		return 1;
978 
979 	if (pos1.line < pos2.line)
980 		return -1;
981 	if (pos1.line > pos2.line)
982 		return 1;
983 
984 	if (pos1.pos < pos2.pos)
985 		return -1;
986 	if (pos1.pos > pos2.pos)
987 		return 1;
988 
989 	return 0;
990 }
991 
positions_eq(struct position pos1,struct position pos2)992 int positions_eq(struct position pos1, struct position pos2)
993 {
994 	if (pos1.line != pos2.line)
995 		return 0;
996 	if (pos1.pos != pos2.pos)
997 		return 0;
998 	if (pos1.stream != pos2.stream)
999 		return 0;
1000 	return 1;
1001 }
1002 
get_current_statement(void)1003 struct statement *get_current_statement(void)
1004 {
1005 	struct statement *prev, *tmp;
1006 
1007 	prev = last_ptr_list((struct ptr_list *)big_statement_stack);
1008 
1009 	if (!prev || !get_macro_name(prev->pos))
1010 		return prev;
1011 
1012 	FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
1013 		if (positions_eq(tmp->pos, prev->pos))
1014 			continue;
1015 		if (prev->pos.line > tmp->pos.line)
1016 			return prev;
1017 		return tmp;
1018 	} END_FOR_EACH_PTR_REVERSE(tmp);
1019 	return prev;
1020 }
1021 
get_prev_statement(void)1022 struct statement *get_prev_statement(void)
1023 {
1024 	struct statement *tmp;
1025 	int i;
1026 
1027 	i = 0;
1028 	FOR_EACH_PTR_REVERSE(big_statement_stack, tmp) {
1029 		if (i++ == 1)
1030 			return tmp;
1031 	} END_FOR_EACH_PTR_REVERSE(tmp);
1032 	return NULL;
1033 }
1034 
get_last_expr_from_expression_stmt(struct expression * expr)1035 struct expression *get_last_expr_from_expression_stmt(struct expression *expr)
1036 {
1037 	struct statement *stmt;
1038 	struct statement *last_stmt;
1039 
1040 	while (expr->type == EXPR_PREOP && expr->op == '(')
1041 		expr = expr->unop;
1042 	if (expr->type != EXPR_STATEMENT)
1043 		return NULL;
1044 	stmt = expr->statement;
1045 	if (!stmt)
1046 		return NULL;
1047 	if (stmt->type == STMT_COMPOUND) {
1048 		last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
1049 		if (!last_stmt)
1050 			return NULL;
1051 		if (last_stmt->type == STMT_LABEL)
1052 			last_stmt = last_stmt->label_statement;
1053 		if (last_stmt->type != STMT_EXPRESSION)
1054 			return NULL;
1055 		return last_stmt->expression;
1056 	}
1057 	if (stmt->type == STMT_EXPRESSION)
1058 		return stmt->expression;
1059 	return NULL;
1060 }
1061 
get_param_num_from_sym(struct symbol * sym)1062 int get_param_num_from_sym(struct symbol *sym)
1063 {
1064 	struct symbol *tmp;
1065 	int i;
1066 
1067 	if (!sym)
1068 		return UNKNOWN_SCOPE;
1069 
1070 	if (sym->ctype.modifiers & MOD_TOPLEVEL) {
1071 		if (sym->ctype.modifiers & MOD_STATIC)
1072 			return FILE_SCOPE;
1073 		return GLOBAL_SCOPE;
1074 	}
1075 
1076 	if (!cur_func_sym) {
1077 		if (!parse_error) {
1078 			sm_msg("warn: internal.  problem with scope:  %s",
1079 			       sym->ident ? sym->ident->name : "<anon var>");
1080 		}
1081 		return GLOBAL_SCOPE;
1082 	}
1083 
1084 
1085 	i = 0;
1086 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, tmp) {
1087 		if (tmp == sym)
1088 			return i;
1089 		i++;
1090 	} END_FOR_EACH_PTR(tmp);
1091 	return LOCAL_SCOPE;
1092 }
1093 
get_param_num(struct expression * expr)1094 int get_param_num(struct expression *expr)
1095 {
1096 	struct symbol *sym;
1097 	char *name;
1098 
1099 	if (!cur_func_sym)
1100 		return UNKNOWN_SCOPE;
1101 	name = expr_to_var_sym(expr, &sym);
1102 	free_string(name);
1103 	if (!sym)
1104 		return UNKNOWN_SCOPE;
1105 	return get_param_num_from_sym(sym);
1106 }
1107 
get_param_sym_from_num(int num)1108 struct symbol *get_param_sym_from_num(int num)
1109 {
1110 	struct symbol *sym;
1111 	int i;
1112 
1113 	if (!cur_func_sym)
1114 		return NULL;
1115 
1116 	i = 0;
1117 	FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, sym) {
1118 		if (i++ == num)
1119 			return sym;
1120 	} END_FOR_EACH_PTR(sym);
1121 	return NULL;
1122 }
1123 
ms_since(struct timeval * start)1124 int ms_since(struct timeval *start)
1125 {
1126 	struct timeval end;
1127 	double diff;
1128 
1129 	gettimeofday(&end, NULL);
1130 	diff = (end.tv_sec - start->tv_sec) * 1000.0;
1131 	diff += (end.tv_usec - start->tv_usec) / 1000.0;
1132 	return (int)diff;
1133 }
1134 
parent_is_gone_var_sym(const char * name,struct symbol * sym)1135 int parent_is_gone_var_sym(const char *name, struct symbol *sym)
1136 {
1137 	if (!name || !sym)
1138 		return 0;
1139 
1140 	if (parent_is_null_var_sym(name, sym) ||
1141 	    parent_is_free_var_sym(name, sym))
1142 		return 1;
1143 	return 0;
1144 }
1145 
parent_is_gone(struct expression * expr)1146 int parent_is_gone(struct expression *expr)
1147 {
1148 	struct symbol *sym;
1149 	char *var;
1150 	int ret = 0;
1151 
1152 	expr = strip_expr(expr);
1153 	var = expr_to_var_sym(expr, &sym);
1154 	if (!var || !sym)
1155 		goto free;
1156 	ret = parent_is_gone_var_sym(var, sym);
1157 free:
1158 	free_string(var);
1159 	return ret;
1160 }
1161 
invert_op(int op)1162 int invert_op(int op)
1163 {
1164 	switch (op) {
1165 	case '*':
1166 		return '/';
1167 	case '/':
1168 		return '*';
1169 	case '+':
1170 		return '-';
1171 	case '-':
1172 		return '+';
1173 	case SPECIAL_LEFTSHIFT:
1174 		return SPECIAL_RIGHTSHIFT;
1175 	case SPECIAL_RIGHTSHIFT:
1176 		return SPECIAL_LEFTSHIFT;
1177 	}
1178 	return 0;
1179 }
1180 
op_remove_assign(int op)1181 int op_remove_assign(int op)
1182 {
1183 	switch (op) {
1184 	case SPECIAL_ADD_ASSIGN:
1185 		return '+';
1186 	case SPECIAL_SUB_ASSIGN:
1187 		return '-';
1188 	case SPECIAL_MUL_ASSIGN:
1189 		return '*';
1190 	case SPECIAL_DIV_ASSIGN:
1191 		return '/';
1192 	case SPECIAL_MOD_ASSIGN:
1193 		return '%';
1194 	case SPECIAL_AND_ASSIGN:
1195 		return '&';
1196 	case SPECIAL_OR_ASSIGN:
1197 		return '|';
1198 	case SPECIAL_XOR_ASSIGN:
1199 		return '^';
1200 	case SPECIAL_SHL_ASSIGN:
1201 		return SPECIAL_LEFTSHIFT;
1202 	case SPECIAL_SHR_ASSIGN:
1203 		return SPECIAL_RIGHTSHIFT;
1204 	default:
1205 		return op;
1206 	}
1207 }
1208 
expr_equiv(struct expression * one,struct expression * two)1209 int expr_equiv(struct expression *one, struct expression *two)
1210 {
1211 	struct symbol *one_sym = NULL;
1212 	struct symbol *two_sym = NULL;
1213 	char *one_name = NULL;
1214 	char *two_name = NULL;
1215 	int ret = 0;
1216 
1217 	if (!one || !two)
1218 		return 0;
1219 	if (one->type != two->type)
1220 		return 0;
1221 	if (is_fake_call(one) || is_fake_call(two))
1222 		return 0;
1223 
1224 	one_name = expr_to_str_sym(one, &one_sym);
1225 	if (!one_name)
1226 		goto free;
1227 	two_name = expr_to_str_sym(two, &two_sym);
1228 	if (!two_name)
1229 		goto free;
1230 	if (one_sym != two_sym)
1231 		goto free;
1232 	/*
1233 	 * This is a terrible hack because expr_to_str() sometimes gives up in
1234 	 * the middle and just returns what it has.  If you see a () you know
1235 	 * the string is bogus.
1236 	 */
1237 	if (strstr(one_name, "()"))
1238 		goto free;
1239 	if (strcmp(one_name, two_name) == 0)
1240 		ret = 1;
1241 free:
1242 	free_string(one_name);
1243 	free_string(two_name);
1244 	return ret;
1245 }
1246 
push_int(struct int_stack ** stack,int num)1247 void push_int(struct int_stack **stack, int num)
1248 {
1249 	int *munged;
1250 
1251 	/*
1252 	 * Just put the int on directly instead of a pointer to the int.
1253 	 * Shift it to the left because Sparse uses the last two bits.
1254 	 * This is sort of a dirty hack, yes.
1255 	 */
1256 
1257 	munged = INT_PTR(num << 2);
1258 
1259 	add_ptr_list(stack, munged);
1260 }
1261 
pop_int(struct int_stack ** stack)1262 int pop_int(struct int_stack **stack)
1263 {
1264 	int *num;
1265 
1266 	num = last_ptr_list((struct ptr_list *)*stack);
1267 	delete_ptr_list_last((struct ptr_list **)stack);
1268 
1269 	return PTR_INT(num) >> 2;
1270 }
1271