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