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