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
31char *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
42char *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
55void free_string(char *str)
56{
57	free(str);
58}
59
60void 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
75struct 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
88struct 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
97struct 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
106struct 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
123void 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 */
133struct 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
150struct 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
175static 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
381struct expr_str_cache_results {
382	struct expression *expr;
383	char str[VAR_LEN];
384	struct symbol *sym;
385	int complicated;
386};
387
388static 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
431char *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
450char *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 */
460char *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
484char *expr_to_var(struct expression *expr)
485{
486	return expr_to_var_sym(expr, NULL);
487}
488
489struct 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
499int 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
535struct 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);
554free:
555	free_string(left);
556	free_string(right);
557
558	return ret;
559}
560
561char *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
611char *expr_to_known_chunk_sym(struct expression *expr, struct symbol **sym)
612{
613	return expr_to_chunk_helper(expr, sym, NULL);
614}
615
616char *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
621int 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
632int 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
641int 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
667struct 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
679struct 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
691const char *show_state(struct smatch_state *state)
692{
693	if (!state)
694		return NULL;
695	return state->name;
696}
697
698struct 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
715struct 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
733static 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
806struct expression *strip_expr(struct expression *expr)
807{
808	return strip_expr_helper(expr, false);
809}
810
811struct expression *strip_expr_set_parent(struct expression *expr)
812{
813	return strip_expr_helper(expr, true);
814}
815
816static void delete_state_tracker(struct tracker *t)
817{
818	delete_state(t->owner, t->name, t->sym);
819	__free_tracker(t);
820}
821
822void 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
830int 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
861int 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
878int 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
901char *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
971int 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
992int 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
1003struct 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
1022struct 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
1035struct 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
1062int 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
1094int 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
1108struct 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
1124int 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
1135int 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
1146int 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);
1157free:
1158	free_string(var);
1159	return ret;
1160}
1161
1162int 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
1181int 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
1209int 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;
1241free:
1242	free_string(one_name);
1243	free_string(two_name);
1244	return ret;
1245}
1246
1247void 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
1262int 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