1/*
2 * Copyright (C) 2008 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 * smatch_extra.c is supposed to track the value of every variable.
20 *
21 */
22
23#define _GNU_SOURCE
24#include <string.h>
25
26#include <stdlib.h>
27#include <errno.h>
28#ifndef __USE_ISOC99
29#define __USE_ISOC99
30#endif
31#include <limits.h>
32#include "parse.h"
33#include "smatch.h"
34#include "smatch_slist.h"
35#include "smatch_extra.h"
36
37static int my_id;
38static int link_id;
39extern int check_assigned_expr_id;
40
41static void match_link_modify(struct sm_state *sm, struct expression *mod_expr);
42
43struct string_list *__ignored_macros = NULL;
44int in_warn_on_macro(void)
45{
46	struct statement *stmt;
47	char *tmp;
48	char *macro;
49
50	stmt = get_current_statement();
51	if (!stmt)
52		return 0;
53	macro = get_macro_name(stmt->pos);
54	if (!macro)
55		return 0;
56
57	FOR_EACH_PTR(__ignored_macros, tmp) {
58		if (!strcmp(tmp, macro))
59			return 1;
60	} END_FOR_EACH_PTR(tmp);
61	return 0;
62}
63
64typedef void (mod_hook)(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state);
65DECLARE_PTR_LIST(void_fn_list, mod_hook *);
66static struct void_fn_list *extra_mod_hooks;
67static struct void_fn_list *extra_nomod_hooks;
68
69void add_extra_mod_hook(mod_hook *fn)
70{
71	mod_hook **p = malloc(sizeof(mod_hook *));
72	*p = fn;
73	add_ptr_list(&extra_mod_hooks, p);
74}
75
76void add_extra_nomod_hook(mod_hook *fn)
77{
78	mod_hook **p = malloc(sizeof(mod_hook *));
79	*p = fn;
80	add_ptr_list(&extra_nomod_hooks, p);
81}
82
83void call_extra_hooks(struct void_fn_list *hooks, const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
84{
85	mod_hook **fn;
86
87	FOR_EACH_PTR(hooks, fn) {
88		(*fn)(name, sym, expr, state);
89	} END_FOR_EACH_PTR(fn);
90}
91
92void call_extra_mod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
93{
94	call_extra_hooks(extra_mod_hooks, name, sym, expr, state);
95}
96
97void call_extra_nomod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
98{
99	call_extra_hooks(extra_nomod_hooks, name, sym, expr, state);
100}
101
102static void set_union_info(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
103{
104	struct symbol *type, *tmp, *inner_type, *inner, *new_type;
105	struct expression *deref, *member_expr;
106	struct smatch_state *new;
107	int offset, inner_offset;
108	static bool in_recurse;
109	char *member_name;
110
111	if (__in_fake_assign)
112		return;
113
114	if (in_recurse)
115		return;
116	in_recurse = true;
117
118	if (!expr || expr->type != EXPR_DEREF || !expr->member)
119		goto done;
120	offset = get_member_offset_from_deref(expr);
121	if (offset < 0)
122		goto done;
123
124	deref = strip_expr(expr->deref);
125	type = get_type(deref);
126	if (type_is_ptr(type))
127		type = get_real_base_type(type);
128	if (!type || type->type != SYM_STRUCT)
129		goto done;
130
131	FOR_EACH_PTR(type->symbol_list, tmp) {
132		inner_type = get_real_base_type(tmp);
133		if (!inner_type || inner_type->type != SYM_UNION)
134			continue;
135
136		inner = first_ptr_list((struct ptr_list *)inner_type->symbol_list);
137		if (!inner || !inner->ident)
138			continue;
139
140		inner_offset = get_member_offset(type, inner->ident->name);
141		if (inner_offset < offset)
142			continue;
143		if (inner_offset > offset)
144			goto done;
145
146		FOR_EACH_PTR(inner_type->symbol_list, inner) {
147			struct symbol *tmp_type;
148
149			if (!inner->ident || inner->ident == expr->member)
150				continue;
151			tmp_type = get_real_base_type(inner);
152			if (tmp_type && tmp_type->type == SYM_STRUCT)
153				continue;
154			member_expr = deref;
155			if (tmp->ident)
156				member_expr = member_expression(member_expr, '.', tmp->ident);
157			member_expr = member_expression(member_expr, expr->op, inner->ident);
158			member_name = expr_to_var(member_expr);
159			if (!member_name)
160				continue;
161			new_type = get_real_base_type(inner);
162			new = alloc_estate_rl(cast_rl(new_type, estate_rl(state)));
163			set_extra_mod_helper(member_name, sym, member_expr, new);
164			free_string(member_name);
165		} END_FOR_EACH_PTR(inner);
166	} END_FOR_EACH_PTR(tmp);
167
168done:
169	in_recurse = false;
170}
171
172static bool in_param_set;
173void set_extra_mod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
174{
175	if (!expr)
176		expr = gen_expression_from_name_sym(name, sym);
177	remove_from_equiv(name, sym);
178	set_union_info(name, sym, expr, state);
179	call_extra_mod_hooks(name, sym, expr, state);
180	update_mtag_data(expr, state);
181	if (in_param_set &&
182	    estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym))
183		return;
184	set_state(SMATCH_EXTRA, name, sym, state);
185}
186
187static void set_extra_nomod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
188{
189	call_extra_nomod_hooks(name, sym, expr, state);
190	set_state(SMATCH_EXTRA, name, sym, state);
191}
192
193static char *get_pointed_at(const char *name, struct symbol *sym, struct symbol **new_sym)
194{
195	struct expression *assigned;
196
197	/*
198	 * Imagine we have an assignment: "foo = &addr;" then the other name
199	 * of "*foo" is addr.
200	 */
201
202	if (name[0] != '*')
203		return NULL;
204	if (strcmp(name + 1, sym->ident->name) != 0)
205		return NULL;
206
207	assigned = get_assigned_expr_name_sym(sym->ident->name, sym);
208	if (!assigned)
209		return NULL;
210	assigned = strip_parens(assigned);
211	if (assigned->type != EXPR_PREOP || assigned->op != '&')
212		return NULL;
213
214	return expr_to_var_sym(assigned->unop, new_sym);
215}
216
217char *get_other_name_sym_from_chunk(const char *name, const char *chunk, int len, struct symbol *sym, struct symbol **new_sym)
218{
219	struct expression *assigned;
220	char *orig_name = NULL;
221	char buf[256];
222	char *ret;
223
224	assigned = get_assigned_expr_name_sym(chunk, sym);
225	if (!assigned)
226		return NULL;
227	if (assigned->type == EXPR_CALL)
228		return map_call_to_other_name_sym(name, sym, new_sym);
229	if (assigned->type == EXPR_PREOP && assigned->op == '&') {
230
231		orig_name = expr_to_var_sym(assigned, new_sym);
232		if (!orig_name || !*new_sym)
233			goto free;
234
235		snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + len);
236		ret = alloc_string(buf);
237		free_string(orig_name);
238		return ret;
239	}
240
241	orig_name = expr_to_var_sym(assigned, new_sym);
242	if (!orig_name || !*new_sym)
243		goto free;
244
245	snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + len);
246	ret = alloc_string(buf);
247	free_string(orig_name);
248	return ret;
249free:
250	free_string(orig_name);
251	return NULL;
252}
253
254static char *get_long_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
255{
256	struct expression *tmp;
257	struct sm_state *sm;
258	char buf[256];
259
260	/*
261	 * Just prepend the name with a different name/sym and return that.
262	 * For example, if we set "foo->bar = bar;" then the other name
263	 * for "bar->baz" is "foo->bar->baz".  Or if we have "foo = bar;" then
264	 * the other name for "bar" is "foo".  A third option is if we have
265	 * "foo = bar;" then another name for "*bar" is "*foo".
266	 */
267
268	FOR_EACH_MY_SM(check_assigned_expr_id, __get_cur_stree(), sm) {
269		tmp = sm->state->data;
270		if (!tmp || tmp->type != EXPR_SYMBOL)
271			continue;
272		if (tmp->symbol == sym)
273			goto found;
274	} END_FOR_EACH_SM(sm);
275
276	return NULL;
277
278found:
279	if (!use_stack && name[tmp->symbol->ident->len] != '-')
280		return NULL;
281
282	if (name[0] == '*' && strcmp(name + 1, tmp->symbol_name->name) == 0)
283		snprintf(buf, sizeof(buf), "*%s", sm->name);
284	else if (name[tmp->symbol->ident->len] == '-' ||
285		 name[tmp->symbol->ident->len] == '.')
286		snprintf(buf, sizeof(buf), "%s%s", sm->name, name + tmp->symbol->ident->len);
287	else if (strcmp(name, tmp->symbol_name->name) == 0)
288		snprintf(buf, sizeof(buf), "%s", sm->name);
289	else
290		return NULL;
291
292	*new_sym = sm->sym;
293	return alloc_string(buf);
294}
295
296char *get_other_name_sym_helper(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
297{
298	char buf[256];
299	char *ret;
300	int len;
301
302	*new_sym = NULL;
303
304	if (!sym || !sym->ident)
305		return NULL;
306
307	ret = get_pointed_at(name, sym, new_sym);
308	if (ret)
309		return ret;
310
311	ret = map_long_to_short_name_sym(name, sym, new_sym, use_stack);
312	if (ret)
313		return ret;
314
315	len = snprintf(buf, sizeof(buf), "%s", name);
316	if (len >= sizeof(buf) - 2)
317		return NULL;
318
319	while (use_stack && len >= 1) {
320		if (buf[len] == '>' && buf[len - 1] == '-') {
321			len--;
322			buf[len] = '\0';
323			ret = get_other_name_sym_from_chunk(name, buf, len + 2, sym, new_sym);
324			if (ret)
325				return ret;
326		}
327		len--;
328	}
329
330	ret = get_long_name_sym(name, sym, new_sym, use_stack);
331	if (ret)
332		return ret;
333
334	return NULL;
335}
336
337char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym)
338{
339	return get_other_name_sym_helper(name, sym, new_sym, true);
340}
341
342char *get_other_name_sym_nostack(const char *name, struct symbol *sym, struct symbol **new_sym)
343{
344	return get_other_name_sym_helper(name, sym, new_sym, false);
345}
346
347void set_extra_mod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
348{
349	char *new_name;
350	struct symbol *new_sym;
351
352	set_extra_mod_helper(name, sym, expr, state);
353	new_name = get_other_name_sym_nostack(name, sym, &new_sym);
354	if (new_name && new_sym)
355		set_extra_mod_helper(new_name, new_sym, NULL, state);
356	free_string(new_name);
357}
358
359static struct expression *chunk_get_array_base(struct expression *expr)
360{
361	/*
362	 * The problem with is_array() is that it only returns true for things
363	 * like foo[1] but not for foo[1].bar.
364	 *
365	 */
366	expr = strip_expr(expr);
367	while (expr && expr->type == EXPR_DEREF)
368		expr = strip_expr(expr->deref);
369	return get_array_base(expr);
370}
371
372static int chunk_has_array(struct expression *expr)
373{
374	return !!chunk_get_array_base(expr);
375}
376
377static void clear_array_states(struct expression *array)
378{
379	struct sm_state *sm;
380
381	sm = get_sm_state_expr(link_id, array);
382	if (sm)
383		match_link_modify(sm, NULL);
384}
385
386static void set_extra_array_mod(struct expression *expr, struct smatch_state *state)
387{
388	struct expression *array;
389	struct var_sym_list *vsl;
390	struct var_sym *vs;
391	char *name;
392	struct symbol *sym;
393
394	array = chunk_get_array_base(expr);
395
396	name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
397	if (!name || !vsl) {
398		clear_array_states(array);
399		goto free;
400	}
401
402	FOR_EACH_PTR(vsl, vs) {
403		store_link(link_id, vs->var, vs->sym, name, sym);
404	} END_FOR_EACH_PTR(vs);
405
406	call_extra_mod_hooks(name, sym, expr, state);
407	set_state(SMATCH_EXTRA, name, sym, state);
408free:
409	free_string(name);
410}
411
412void set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
413{
414	struct symbol *sym;
415	char *name;
416
417	if (chunk_has_array(expr)) {
418		set_extra_array_mod(expr, state);
419		return;
420	}
421
422	expr = strip_expr(expr);
423	name = expr_to_var_sym(expr, &sym);
424	if (!name || !sym)
425		goto free;
426	set_extra_mod(name, sym, expr, state);
427free:
428	free_string(name);
429}
430
431void set_extra_nomod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
432{
433	char *new_name;
434	struct symbol *new_sym;
435	struct relation *rel;
436	struct smatch_state *orig_state;
437
438	orig_state = get_state(SMATCH_EXTRA, name, sym);
439
440	/* don't save unknown states if leaving it blank is the same */
441	if (!orig_state && estate_is_unknown(state))
442		return;
443
444	new_name = get_other_name_sym(name, sym, &new_sym);
445	if (new_name && new_sym)
446		set_extra_nomod_helper(new_name, new_sym, expr, state);
447	free_string(new_name);
448
449	if (!estate_related(orig_state)) {
450		set_extra_nomod_helper(name, sym, expr, state);
451		return;
452	}
453
454	set_related(state, estate_related(orig_state));
455	FOR_EACH_PTR(estate_related(orig_state), rel) {
456		struct smatch_state *estate;
457
458		estate = get_state(SMATCH_EXTRA, rel->name, rel->sym);
459		if (!estate)
460			continue;
461		set_extra_nomod_helper(rel->name, rel->sym, expr, clone_estate_cast(estate_type(estate), state));
462	} END_FOR_EACH_PTR(rel);
463}
464
465void set_extra_nomod_vsl(const char *name, struct symbol *sym, struct var_sym_list *vsl, struct expression *expr, struct smatch_state *state)
466{
467	struct var_sym *vs;
468
469	FOR_EACH_PTR(vsl, vs) {
470		store_link(link_id, vs->var, vs->sym, name, sym);
471	} END_FOR_EACH_PTR(vs);
472
473	set_extra_nomod(name, sym, expr, state);
474}
475
476/*
477 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
478 */
479void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state)
480{
481	struct var_sym_list *vsl;
482	struct var_sym *vs;
483	char *name;
484	struct symbol *sym;
485
486	name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
487	if (!name || !vsl)
488		goto free;
489	FOR_EACH_PTR(vsl, vs) {
490		store_link(link_id, vs->var, vs->sym, name, sym);
491	} END_FOR_EACH_PTR(vs);
492
493	set_extra_nomod(name, sym, expr, state);
494free:
495	free_string(name);
496}
497
498static void set_extra_true_false(const char *name, struct symbol *sym,
499			struct smatch_state *true_state,
500			struct smatch_state *false_state)
501{
502	char *new_name;
503	struct symbol *new_sym;
504	struct relation *rel;
505	struct smatch_state *orig_state;
506
507	if (!true_state && !false_state)
508		return;
509
510	if (in_warn_on_macro())
511		return;
512
513	new_name = get_other_name_sym(name, sym, &new_sym);
514	if (new_name && new_sym)
515		set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state);
516	free_string(new_name);
517
518	orig_state = get_state(SMATCH_EXTRA, name, sym);
519
520	if (!estate_related(orig_state)) {
521		set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
522		return;
523	}
524
525	if (true_state)
526		set_related(true_state, estate_related(orig_state));
527	if (false_state)
528		set_related(false_state, estate_related(orig_state));
529
530	FOR_EACH_PTR(estate_related(orig_state), rel) {
531		set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym,
532				true_state, false_state);
533	} END_FOR_EACH_PTR(rel);
534}
535
536static void set_extra_chunk_true_false(struct expression *expr,
537				       struct smatch_state *true_state,
538				       struct smatch_state *false_state)
539{
540	struct var_sym_list *vsl;
541	struct var_sym *vs;
542	struct symbol *type;
543	char *name;
544	struct symbol *sym;
545
546	if (in_warn_on_macro())
547		return;
548
549	type = get_type(expr);
550	if (!type)
551		return;
552
553	name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
554	if (!name || !vsl)
555		goto free;
556	FOR_EACH_PTR(vsl, vs) {
557		store_link(link_id, vs->var, vs->sym, name, sym);
558	} END_FOR_EACH_PTR(vs);
559
560	set_true_false_states(SMATCH_EXTRA, name, sym,
561			      clone_estate(true_state),
562			      clone_estate(false_state));
563free:
564	free_string(name);
565}
566
567static void set_extra_expr_true_false(struct expression *expr,
568		struct smatch_state *true_state,
569		struct smatch_state *false_state)
570{
571	char *name;
572	struct symbol *sym;
573	sval_t sval;
574
575	if (!true_state && !false_state)
576		return;
577
578	if (get_value(expr, &sval))
579		return;
580
581	expr = strip_expr(expr);
582	name = expr_to_var_sym(expr, &sym);
583	if (!name || !sym) {
584		free_string(name);
585		set_extra_chunk_true_false(expr, true_state, false_state);
586		return;
587	}
588	set_extra_true_false(name, sym, true_state, false_state);
589	free_string(name);
590}
591
592static int get_countdown_info(struct expression *condition, struct expression **unop, int *op, sval_t *right)
593{
594	struct expression *unop_expr;
595	int comparison;
596	sval_t limit;
597
598	right->type = &int_ctype;
599	right->value = 0;
600
601	condition = strip_expr(condition);
602
603	if (condition->type == EXPR_COMPARE) {
604		comparison = remove_unsigned_from_comparison(condition->op);
605
606		if (comparison != SPECIAL_GTE && comparison != '>')
607			return 0;
608		if (!get_value(condition->right, &limit))
609			return 0;
610
611		unop_expr = condition->left;
612		if (unop_expr->type != EXPR_PREOP && unop_expr->type != EXPR_POSTOP)
613			return 0;
614		if (unop_expr->op != SPECIAL_DECREMENT)
615			return 0;
616
617		*unop = unop_expr;
618		*op = comparison;
619		*right = limit;
620
621		return 1;
622	}
623
624	if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
625		return 0;
626	if (condition->op != SPECIAL_DECREMENT)
627		return 0;
628
629	*unop = condition;
630	*op = '>';
631
632	return 1;
633}
634
635static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
636{
637	struct expression *iter_var;
638	struct expression *condition, *unop;
639	struct symbol *type;
640	struct sm_state *sm;
641	struct smatch_state *estate;
642	int op;
643	sval_t start, right;
644
645	right.type = &int_ctype;
646	right.value = 0;
647
648	condition = strip_expr(loop->iterator_pre_condition);
649	if (!condition)
650		return NULL;
651
652	if (!get_countdown_info(condition, &unop, &op, &right))
653		return NULL;
654
655	iter_var = unop->unop;
656
657	sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
658	if (!sm)
659		return NULL;
660	if (sval_cmp(estate_min(sm->state), right) < 0)
661		return NULL;
662	start = estate_max(sm->state);
663
664	type = get_type(iter_var);
665	right = sval_cast(type, right);
666	start = sval_cast(type, start);
667
668	if  (sval_cmp(start, right) <= 0)
669		return NULL;
670	if (!sval_is_max(start))
671		start.value--;
672
673	if (op == SPECIAL_GTE)
674		right.value--;
675
676	if (unop->type == EXPR_PREOP) {
677		right.value++;
678		estate = alloc_estate_range(right, start);
679		if (estate_has_hard_max(sm->state))
680			estate_set_hard_max(estate);
681		estate_copy_fuzzy_max(estate, sm->state);
682		set_extra_expr_mod(iter_var, estate);
683	}
684	if (unop->type == EXPR_POSTOP) {
685		estate = alloc_estate_range(right, start);
686		if (estate_has_hard_max(sm->state))
687			estate_set_hard_max(estate);
688		estate_copy_fuzzy_max(estate, sm->state);
689		set_extra_expr_mod(iter_var, estate);
690	}
691	return get_sm_state_expr(SMATCH_EXTRA, iter_var);
692}
693
694static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr,
695						struct expression *condition)
696{
697	struct expression *iter_var;
698	struct sm_state *sm;
699	struct smatch_state *estate;
700	sval_t start, end, max;
701	struct symbol *type;
702
703	iter_var = iter_expr->unop;
704	sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
705	if (!sm)
706		return NULL;
707	if (!estate_get_single_value(sm->state, &start))
708		return NULL;
709	if (!get_implied_value(condition->right, &end))
710		return NULL;
711
712	if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
713		return NULL;
714
715	switch (condition->op) {
716	case SPECIAL_UNSIGNED_LT:
717	case SPECIAL_NOTEQUAL:
718	case '<':
719		if (!sval_is_min(end))
720			end.value--;
721		break;
722	case SPECIAL_UNSIGNED_LTE:
723	case SPECIAL_LTE:
724		break;
725	default:
726		return NULL;
727	}
728	if (sval_cmp(end, start) < 0)
729		return NULL;
730	type = get_type(iter_var);
731	start = sval_cast(type, start);
732	end = sval_cast(type, end);
733	estate = alloc_estate_range(start, end);
734	if (get_hard_max(condition->right, &max)) {
735		if (!get_macro_name(condition->pos))
736			estate_set_hard_max(estate);
737		if (condition->op == '<' ||
738		    condition->op == SPECIAL_UNSIGNED_LT ||
739		    condition->op == SPECIAL_NOTEQUAL)
740			max.value--;
741		max = sval_cast(type, max);
742		estate_set_fuzzy_max(estate, max);
743	}
744	set_extra_expr_mod(iter_var, estate);
745	return get_sm_state_expr(SMATCH_EXTRA, iter_var);
746}
747
748static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr,
749						struct expression *condition)
750{
751	struct expression *iter_var;
752	struct sm_state *sm;
753	struct smatch_state *estate;
754	sval_t start, end;
755
756	iter_var = iter_expr->unop;
757	sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
758	if (!sm)
759		return NULL;
760	if (!estate_get_single_value(sm->state, &start))
761		return NULL;
762	if (!get_implied_min(condition->right, &end))
763		end = sval_type_min(get_type(iter_var));
764	end = sval_cast(estate_type(sm->state), end);
765	if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
766		return NULL;
767
768	switch (condition->op) {
769	case SPECIAL_NOTEQUAL:
770	case '>':
771		if (!sval_is_max(end))
772			end.value++;
773		break;
774	case SPECIAL_GTE:
775		break;
776	default:
777		return NULL;
778	}
779	if (sval_cmp(end, start) > 0)
780		return NULL;
781	estate = alloc_estate_range(end, start);
782	estate_set_hard_max(estate);
783	estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate));
784	set_extra_expr_mod(iter_var, estate);
785	return get_sm_state_expr(SMATCH_EXTRA, iter_var);
786}
787
788static struct sm_state *handle_canonical_for_loops(struct statement *loop)
789{
790	struct expression *iter_expr;
791	struct expression *condition;
792
793	if (!loop->iterator_post_statement)
794		return NULL;
795	if (loop->iterator_post_statement->type != STMT_EXPRESSION)
796		return NULL;
797	iter_expr = loop->iterator_post_statement->expression;
798	if (!loop->iterator_pre_condition)
799		return NULL;
800	if (loop->iterator_pre_condition->type != EXPR_COMPARE)
801		return NULL;
802	condition = loop->iterator_pre_condition;
803
804	if (iter_expr->op == SPECIAL_INCREMENT)
805		return handle_canonical_for_inc(iter_expr, condition);
806	if (iter_expr->op == SPECIAL_DECREMENT)
807		return handle_canonical_for_dec(iter_expr, condition);
808	return NULL;
809}
810
811struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree)
812{
813	struct sm_state *ret;
814
815	/*
816	 * Canonical loops are a hack.  The proper way to handle this is to
817	 * use two passes, but unfortunately, doing two passes makes parsing
818	 * code twice as slow.
819	 *
820	 * What we do is we set the inside state here, which overwrites whatever
821	 * __extra_match_condition() does.  Then we set the outside state in
822	 * __extra_pre_loop_hook_after().
823	 *
824	 */
825	__push_fake_cur_stree();
826	if (!loop->iterator_post_statement)
827		ret = handle_canonical_while_count_down(loop);
828	else
829		ret = handle_canonical_for_loops(loop);
830	*stree = __pop_fake_cur_stree();
831	return ret;
832}
833
834int __iterator_unchanged(struct sm_state *sm)
835{
836	if (!sm)
837		return 0;
838	if (get_sm_state(my_id, sm->name, sm->sym) == sm)
839		return 1;
840	return 0;
841}
842
843static void while_count_down_after(struct sm_state *sm, struct expression *condition)
844{
845	struct expression *unop;
846	int op;
847	sval_t limit, after_value;
848
849	if (!get_countdown_info(condition, &unop, &op, &limit))
850		return;
851	after_value = estate_min(sm->state);
852	after_value.value--;
853	set_extra_mod(sm->name, sm->sym, condition->unop, alloc_estate_sval(after_value));
854}
855
856void __extra_pre_loop_hook_after(struct sm_state *sm,
857				struct statement *iterator,
858				struct expression *condition)
859{
860	struct expression *iter_expr;
861	sval_t limit;
862	struct smatch_state *state;
863
864	if (!iterator) {
865		while_count_down_after(sm, condition);
866		return;
867	}
868
869	iter_expr = iterator->expression;
870
871	if (condition->type != EXPR_COMPARE)
872		return;
873	if (iter_expr->op == SPECIAL_INCREMENT) {
874		limit = sval_binop(estate_max(sm->state), '+',
875				   sval_type_val(estate_type(sm->state), 1));
876	} else {
877		limit = sval_binop(estate_min(sm->state), '-',
878				   sval_type_val(estate_type(sm->state), 1));
879	}
880	limit = sval_cast(estate_type(sm->state), limit);
881	if (!estate_has_hard_max(sm->state) && !__has_breaks()) {
882		if (iter_expr->op == SPECIAL_INCREMENT)
883			state = alloc_estate_range(estate_min(sm->state), limit);
884		else
885			state = alloc_estate_range(limit, estate_max(sm->state));
886	} else {
887		state = alloc_estate_sval(limit);
888	}
889	if (!estate_has_hard_max(sm->state)) {
890		estate_clear_hard_max(state);
891	}
892	if (estate_has_fuzzy_max(sm->state)) {
893		sval_t hmax = estate_get_fuzzy_max(sm->state);
894		sval_t max = estate_max(sm->state);
895
896		if (sval_cmp(hmax, max) != 0)
897			estate_clear_fuzzy_max(state);
898	} else if (!estate_has_fuzzy_max(sm->state)) {
899		estate_clear_fuzzy_max(state);
900	}
901
902	set_extra_mod(sm->name, sm->sym, iter_expr, state);
903}
904
905static bool get_global_rl(const char *name, struct symbol *sym, struct range_list **rl)
906{
907	struct expression *expr;
908
909	if (!sym || !(sym->ctype.modifiers & MOD_TOPLEVEL) || !sym->ident)
910		return false;
911	if (strcmp(sym->ident->name, name) != 0)
912		return false;
913
914	expr = symbol_expression(sym);
915	return get_implied_rl(expr, rl);
916}
917
918static struct stree *unmatched_stree;
919static struct smatch_state *unmatched_state(struct sm_state *sm)
920{
921	struct smatch_state *state;
922	struct range_list *rl;
923
924	if (unmatched_stree) {
925		state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym);
926		if (state)
927			return state;
928	}
929	if (parent_is_gone_var_sym(sm->name, sm->sym))
930		return alloc_estate_empty();
931	if (get_global_rl(sm->name, sm->sym, &rl))
932		return alloc_estate_rl(rl);
933	return alloc_estate_whole(estate_type(sm->state));
934}
935
936static void clear_the_pointed_at(struct expression *expr)
937{
938	struct stree *stree;
939	char *name;
940	struct symbol *sym;
941	struct sm_state *tmp;
942
943	name = expr_to_var_sym(expr, &sym);
944	if (!name || !sym)
945		goto free;
946
947	stree = __get_cur_stree();
948	FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) {
949		if (tmp->name[0] != '*')
950			continue;
951		if (tmp->sym != sym)
952			continue;
953		if (strcmp(tmp->name + 1, name) != 0)
954			continue;
955		set_extra_mod(tmp->name, tmp->sym, expr, alloc_estate_whole(estate_type(tmp->state)));
956	} END_FOR_EACH_SM(tmp);
957
958free:
959	free_string(name);
960}
961
962static int is_const_param(struct expression *expr, int param)
963{
964	struct symbol *type;
965
966	type = get_arg_type(expr, param);
967	if (!type)
968		return 0;
969	if (type->ctype.modifiers & MOD_CONST)
970		return 1;
971	return 0;
972}
973
974static void match_function_call(struct expression *expr)
975{
976	struct expression *arg;
977	struct expression *tmp;
978	int param = -1;
979
980	/* if we have the db this is handled in smatch_function_hooks.c */
981	if (!option_no_db)
982		return;
983	if (inlinable(expr->fn))
984		return;
985
986	FOR_EACH_PTR(expr->args, arg) {
987		param++;
988		if (is_const_param(expr->fn, param))
989			continue;
990		tmp = strip_expr(arg);
991		if (tmp->type == EXPR_PREOP && tmp->op == '&')
992			set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop)));
993		else
994			clear_the_pointed_at(tmp);
995	} END_FOR_EACH_PTR(arg);
996}
997
998int values_fit_type(struct expression *left, struct expression *right)
999{
1000	struct range_list *rl;
1001	struct symbol *type;
1002
1003	type = get_type(left);
1004	if (!type)
1005		return 0;
1006	get_absolute_rl(right, &rl);
1007	if (type == rl_type(rl))
1008		return 1;
1009	if (type_unsigned(type) && sval_is_negative(rl_min(rl)))
1010		return 0;
1011	if (sval_cmp(sval_type_min(type), rl_min(rl)) > 0)
1012		return 0;
1013	if (sval_cmp(sval_type_max(type), rl_max(rl)) < 0)
1014		return 0;
1015	return 1;
1016}
1017
1018static void save_chunk_info(struct expression *left, struct expression *right)
1019{
1020	struct var_sym_list *vsl;
1021	struct var_sym *vs;
1022	struct expression *add_expr;
1023	struct symbol *type;
1024	sval_t sval;
1025	char *name;
1026	struct symbol *sym;
1027
1028	if (right->type != EXPR_BINOP || right->op != '-')
1029		return;
1030	if (!get_value(right->left, &sval))
1031		return;
1032	if (!expr_to_sym(right->right))
1033		return;
1034
1035	add_expr = binop_expression(left, '+', right->right);
1036	type = get_type(add_expr);
1037	if (!type)
1038		return;
1039	name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl);
1040	if (!name || !vsl)
1041		goto free;
1042	FOR_EACH_PTR(vsl, vs) {
1043		store_link(link_id, vs->var, vs->sym, name, sym);
1044	} END_FOR_EACH_PTR(vs);
1045
1046	set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval)));
1047free:
1048	free_string(name);
1049}
1050
1051static void do_array_assign(struct expression *left, int op, struct expression *right)
1052{
1053	struct range_list *rl;
1054
1055	if (op == '=') {
1056		get_absolute_rl(right, &rl);
1057		rl = cast_rl(get_type(left), rl);
1058	} else {
1059		rl = alloc_whole_rl(get_type(left));
1060	}
1061
1062	set_extra_array_mod(left, alloc_estate_rl(rl));
1063}
1064
1065static void match_vanilla_assign(struct expression *left, struct expression *right)
1066{
1067	struct range_list *orig_rl = NULL;
1068	struct range_list *rl = NULL;
1069	struct symbol *right_sym;
1070	struct symbol *left_type;
1071	struct symbol *right_type;
1072	char *right_name = NULL;
1073	struct symbol *sym;
1074	char *name;
1075	sval_t sval, max;
1076	struct smatch_state *state;
1077	int comparison;
1078
1079	if (is_struct(left))
1080		return;
1081
1082	save_chunk_info(left, right);
1083
1084	name = expr_to_var_sym(left, &sym);
1085	if (!name) {
1086		if (chunk_has_array(left))
1087			do_array_assign(left, '=', right);
1088		return;
1089	}
1090
1091	left_type = get_type(left);
1092	right_type = get_type(right);
1093
1094	right_name = expr_to_var_sym(right, &right_sym);
1095
1096	if (!__in_fake_assign &&
1097	    !(right->type == EXPR_PREOP && right->op == '&') &&
1098	    right_name && right_sym &&
1099	    values_fit_type(left, strip_expr(right)) &&
1100	    !has_symbol(right, sym)) {
1101		set_equiv(left, right);
1102		goto free;
1103	}
1104
1105	if (get_implied_value(right, &sval)) {
1106		state = alloc_estate_sval(sval_cast(left_type, sval));
1107		goto done;
1108	}
1109
1110	if (__in_fake_assign) {
1111		struct smatch_state *right_state;
1112		sval_t sval;
1113
1114		if (get_value(right, &sval)) {
1115			sval = sval_cast(left_type, sval);
1116			state = alloc_estate_sval(sval);
1117			goto done;
1118		}
1119
1120		right_state = get_state(SMATCH_EXTRA, right_name, right_sym);
1121		if (right_state) {
1122			/* simple assignment */
1123			state = clone_estate(right_state);
1124			goto done;
1125		}
1126
1127		state = alloc_estate_rl(alloc_whole_rl(left_type));
1128		goto done;
1129	}
1130
1131	comparison = get_comparison_no_extra(left, right);
1132	if (comparison) {
1133		comparison = flip_comparison(comparison);
1134		get_implied_rl(left, &orig_rl);
1135	}
1136
1137	if (get_implied_rl(right, &rl)) {
1138		rl = cast_rl(left_type, rl);
1139		if (orig_rl)
1140			filter_by_comparison(&rl, comparison, orig_rl);
1141		state = alloc_estate_rl(rl);
1142		if (get_hard_max(right, &max)) {
1143			estate_set_hard_max(state);
1144			estate_set_fuzzy_max(state, max);
1145		}
1146	} else {
1147		rl = alloc_whole_rl(right_type);
1148		rl = cast_rl(left_type, rl);
1149		if (orig_rl)
1150			filter_by_comparison(&rl, comparison, orig_rl);
1151		state = alloc_estate_rl(rl);
1152	}
1153
1154done:
1155	set_extra_mod(name, sym, left, state);
1156free:
1157	free_string(right_name);
1158}
1159
1160static void match_assign(struct expression *expr)
1161{
1162	struct range_list *rl = NULL;
1163	struct expression *left;
1164	struct expression *right;
1165	struct expression *binop_expr;
1166	struct symbol *left_type;
1167	struct symbol *sym;
1168	char *name;
1169
1170	left = strip_expr(expr->left);
1171
1172	right = strip_parens(expr->right);
1173	if (right->type == EXPR_CALL && sym_name_is("__builtin_expect", right->fn))
1174		right = get_argument_from_call_expr(right->args, 0);
1175	while (right->type == EXPR_ASSIGNMENT && right->op == '=')
1176		right = strip_parens(right->left);
1177
1178	if (expr->op == '=' && is_condition(expr->right))
1179		return; /* handled in smatch_condition.c */
1180	if (expr->op == '=' && right->type == EXPR_CALL)
1181		return; /* handled in smatch_function_hooks.c */
1182	if (expr->op == '=') {
1183		match_vanilla_assign(left, right);
1184		return;
1185	}
1186
1187	name = expr_to_var_sym(left, &sym);
1188	if (!name)
1189		return;
1190
1191	left_type = get_type(left);
1192
1193	switch (expr->op) {
1194	case SPECIAL_ADD_ASSIGN:
1195	case SPECIAL_SUB_ASSIGN:
1196	case SPECIAL_AND_ASSIGN:
1197	case SPECIAL_MOD_ASSIGN:
1198	case SPECIAL_SHL_ASSIGN:
1199	case SPECIAL_SHR_ASSIGN:
1200	case SPECIAL_OR_ASSIGN:
1201	case SPECIAL_XOR_ASSIGN:
1202	case SPECIAL_MUL_ASSIGN:
1203	case SPECIAL_DIV_ASSIGN:
1204		binop_expr = binop_expression(expr->left,
1205					      op_remove_assign(expr->op),
1206					      expr->right);
1207		get_absolute_rl(binop_expr, &rl);
1208		rl = cast_rl(left_type, rl);
1209		if (inside_loop()) {
1210			if (expr->op == SPECIAL_ADD_ASSIGN)
1211				add_range(&rl, rl_max(rl), sval_type_max(rl_type(rl)));
1212
1213			if (expr->op == SPECIAL_SUB_ASSIGN &&
1214			    !sval_is_negative(rl_min(rl))) {
1215				sval_t zero = { .type = rl_type(rl) };
1216
1217				add_range(&rl, rl_min(rl), zero);
1218			}
1219		}
1220		set_extra_mod(name, sym, left, alloc_estate_rl(rl));
1221		goto free;
1222	}
1223	set_extra_mod(name, sym, left, alloc_estate_whole(left_type));
1224free:
1225	free_string(name);
1226}
1227
1228static struct smatch_state *increment_state(struct smatch_state *state)
1229{
1230	sval_t min = estate_min(state);
1231	sval_t max = estate_max(state);
1232
1233	if (!estate_rl(state))
1234		return NULL;
1235
1236	if (inside_loop())
1237		max = sval_type_max(max.type);
1238
1239	if (!sval_is_min(min) && !sval_is_max(min))
1240		min.value++;
1241	if (!sval_is_min(max) && !sval_is_max(max))
1242		max.value++;
1243	return alloc_estate_range(min, max);
1244}
1245
1246static struct smatch_state *decrement_state(struct smatch_state *state)
1247{
1248	sval_t min = estate_min(state);
1249	sval_t max = estate_max(state);
1250
1251	if (!estate_rl(state))
1252		return NULL;
1253
1254	if (inside_loop())
1255		min = sval_type_min(min.type);
1256
1257	if (!sval_is_min(min) && !sval_is_max(min))
1258		min.value--;
1259	if (!sval_is_min(max) && !sval_is_max(max))
1260		max.value--;
1261	return alloc_estate_range(min, max);
1262}
1263
1264static void clear_pointed_at_state(struct expression *expr)
1265{
1266	struct symbol *type;
1267
1268	/*
1269         * ALERT: This is sort of a mess.  If it's is a struct assigment like
1270	 * "foo = bar;", then that's handled by smatch_struct_assignment.c.
1271	 * the same thing for p++ where "p" is a struct.  Most modifications
1272	 * are handled by the assignment hook or the db.  Smatch_extra.c doesn't
1273	 * use smatch_modification.c because we have to get the ordering right
1274	 * or something.  So if you have p++ where p is a pointer to a standard
1275	 * c type then we handle that here.  What a mess.
1276	 */
1277	expr = strip_expr(expr);
1278	type = get_type(expr);
1279	if (!type || type->type != SYM_PTR)
1280		return;
1281	type = get_real_base_type(type);
1282	if (!type || type->type != SYM_BASETYPE)
1283		return;
1284	set_extra_expr_nomod(deref_expression(expr), alloc_estate_whole(type));
1285}
1286
1287static void unop_expr(struct expression *expr)
1288{
1289	struct smatch_state *state;
1290
1291	if (expr->smatch_flags & Handled)
1292		return;
1293
1294	switch (expr->op) {
1295	case SPECIAL_INCREMENT:
1296		state = get_state_expr(SMATCH_EXTRA, expr->unop);
1297		state = increment_state(state);
1298		if (!state)
1299			state = alloc_estate_whole(get_type(expr));
1300		set_extra_expr_mod(expr->unop, state);
1301		clear_pointed_at_state(expr->unop);
1302		break;
1303	case SPECIAL_DECREMENT:
1304		state = get_state_expr(SMATCH_EXTRA, expr->unop);
1305		state = decrement_state(state);
1306		if (!state)
1307			state = alloc_estate_whole(get_type(expr));
1308		set_extra_expr_mod(expr->unop, state);
1309		clear_pointed_at_state(expr->unop);
1310		break;
1311	default:
1312		return;
1313	}
1314}
1315
1316static void asm_expr(struct statement *stmt)
1317{
1318
1319	struct expression *expr;
1320	struct symbol *type;
1321
1322	FOR_EACH_PTR(stmt->asm_outputs, expr) {
1323		if (expr->type != EXPR_ASM_OPERAND) {
1324			sm_perror("unexpected asm param type %d", expr->type);
1325			continue;
1326		}
1327		type = get_type(strip_expr(expr->expr));
1328		set_extra_expr_mod(expr->expr, alloc_estate_whole(type));
1329	} END_FOR_EACH_PTR(expr);
1330}
1331
1332static void check_dereference(struct expression *expr)
1333{
1334	struct smatch_state *state;
1335
1336	if (__in_fake_assign)
1337		return;
1338	if (outside_of_function())
1339		return;
1340	state = get_extra_state(expr);
1341	if (state) {
1342		struct range_list *rl;
1343
1344		rl = rl_intersection(estate_rl(state), valid_ptr_rl);
1345		if (rl_equiv(rl, estate_rl(state)))
1346			return;
1347		set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1348	} else {
1349		struct range_list *rl;
1350
1351		if (get_mtag_rl(expr, &rl))
1352			rl = rl_intersection(rl, valid_ptr_rl);
1353		else
1354			rl = clone_rl(valid_ptr_rl);
1355
1356		set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1357	}
1358}
1359
1360static void match_dereferences(struct expression *expr)
1361{
1362	if (expr->type != EXPR_PREOP)
1363		return;
1364	if (getting_address(expr))
1365		return;
1366	/* it's saying that foo[1] = bar dereferences foo[1] */
1367	if (is_array(expr))
1368		return;
1369	check_dereference(expr->unop);
1370}
1371
1372static void match_pointer_as_array(struct expression *expr)
1373{
1374	if (!is_array(expr))
1375		return;
1376	check_dereference(get_array_base(expr));
1377}
1378
1379static void find_dereferences(struct expression *expr)
1380{
1381	while (expr->type == EXPR_PREOP) {
1382		if (expr->op == '*')
1383			check_dereference(expr->unop);
1384		expr = strip_expr(expr->unop);
1385	}
1386}
1387
1388static void set_param_dereferenced(struct expression *call, struct expression *arg, char *key, char *unused)
1389{
1390	struct symbol *sym;
1391	char *name;
1392
1393	name = get_variable_from_key(arg, key, &sym);
1394	if (name && sym) {
1395		struct smatch_state *orig, *new;
1396		struct range_list *rl;
1397
1398		orig = get_state(SMATCH_EXTRA, name, sym);
1399		if (orig) {
1400			rl = rl_intersection(estate_rl(orig),
1401					     alloc_rl(valid_ptr_min_sval,
1402						      valid_ptr_max_sval));
1403			new = alloc_estate_rl(rl);
1404		} else {
1405			new = alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval);
1406		}
1407
1408		set_extra_nomod(name, sym, NULL, new);
1409	}
1410	free_string(name);
1411
1412	find_dereferences(arg);
1413}
1414
1415static sval_t add_one(sval_t sval)
1416{
1417	sval.value++;
1418	return sval;
1419}
1420
1421static int handle_postop_inc(struct expression *left, int op, struct expression *right)
1422{
1423	struct statement *stmt;
1424	struct expression *cond;
1425	struct smatch_state *true_state, *false_state;
1426	struct symbol *type;
1427	sval_t start;
1428	sval_t limit;
1429
1430	/*
1431	 * If we're decrementing here then that's a canonical while count down
1432	 * so it's handled already.  We're only handling loops like:
1433	 * i = 0;
1434	 * do { ... } while (i++ < 3);
1435	 */
1436
1437	if (left->type != EXPR_POSTOP || left->op != SPECIAL_INCREMENT)
1438		return 0;
1439
1440	stmt = __cur_stmt->parent;
1441	if (!stmt)
1442		return 0;
1443	if (stmt->type == STMT_COMPOUND)
1444		stmt = stmt->parent;
1445	if (!stmt || stmt->type != STMT_ITERATOR || !stmt->iterator_post_condition)
1446		return 0;
1447
1448	cond = strip_expr(stmt->iterator_post_condition);
1449	if (cond->type != EXPR_COMPARE || cond->op != op)
1450		return 0;
1451	if (left != strip_expr(cond->left) || right != strip_expr(cond->right))
1452		return 0;
1453
1454	if (!get_implied_value(left->unop, &start))
1455		return 0;
1456	if (!get_implied_value(right, &limit))
1457		return 0;
1458	type = get_type(left->unop);
1459	limit = sval_cast(type, limit);
1460	if (sval_cmp(start, limit) > 0)
1461		return 0;
1462
1463	switch (op) {
1464	case '<':
1465	case SPECIAL_UNSIGNED_LT:
1466		break;
1467	case SPECIAL_LTE:
1468	case SPECIAL_UNSIGNED_LTE:
1469		limit = add_one(limit);
1470	default:
1471		return 0;
1472
1473	}
1474
1475	true_state = alloc_estate_range(add_one(start), limit);
1476	false_state = alloc_estate_range(add_one(limit), add_one(limit));
1477
1478	/* Currently we just discard the false state but when two passes is
1479	 * implimented correctly then it will use it.
1480	 */
1481
1482	set_extra_expr_true_false(left->unop, true_state, false_state);
1483
1484	return 1;
1485}
1486
1487bool is_impossible_variable(struct expression *expr)
1488{
1489	struct smatch_state *state;
1490
1491	state = get_extra_state(expr);
1492	if (state && !estate_rl(state))
1493		return true;
1494	return false;
1495}
1496
1497static bool in_macro(struct expression *left, struct expression *right)
1498{
1499	if (!left || !right)
1500		return 0;
1501	if (left->pos.line != right->pos.line || left->pos.pos != right->pos.pos)
1502		return 0;
1503	if (get_macro_name(left->pos))
1504		return 1;
1505	return 0;
1506}
1507
1508static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right)
1509{
1510	struct range_list *left_orig;
1511	struct range_list *left_true;
1512	struct range_list *left_false;
1513	struct range_list *right_orig;
1514	struct range_list *right_true;
1515	struct range_list *right_false;
1516	struct smatch_state *left_true_state;
1517	struct smatch_state *left_false_state;
1518	struct smatch_state *right_true_state;
1519	struct smatch_state *right_false_state;
1520	sval_t dummy, hard_max;
1521	int left_postop = 0;
1522	int right_postop = 0;
1523
1524	if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) {
1525		if (left->type == EXPR_POSTOP) {
1526			left->smatch_flags |= Handled;
1527			left_postop = left->op;
1528			if (handle_postop_inc(left, op, right))
1529				return;
1530		}
1531		left = strip_parens(left->unop);
1532	}
1533	while (left->type == EXPR_ASSIGNMENT)
1534		left = strip_parens(left->left);
1535
1536	if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) {
1537		if (right->type == EXPR_POSTOP) {
1538			right->smatch_flags |= Handled;
1539			right_postop = right->op;
1540		}
1541		right = strip_parens(right->unop);
1542	}
1543
1544	if (is_impossible_variable(left) || is_impossible_variable(right))
1545		return;
1546
1547	get_real_absolute_rl(left, &left_orig);
1548	left_orig = cast_rl(type, left_orig);
1549
1550	get_real_absolute_rl(right, &right_orig);
1551	right_orig = cast_rl(type, right_orig);
1552
1553	split_comparison_rl(left_orig, op, right_orig, &left_true, &left_false, &right_true, &right_false);
1554
1555	left_true = rl_truncate_cast(get_type(strip_expr(left)), left_true);
1556	left_false = rl_truncate_cast(get_type(strip_expr(left)), left_false);
1557	right_true = rl_truncate_cast(get_type(strip_expr(right)), right_true);
1558	right_false = rl_truncate_cast(get_type(strip_expr(right)), right_false);
1559
1560	if (!left_true || !left_false) {
1561		struct range_list *tmp_true, *tmp_false;
1562
1563		split_comparison_rl(alloc_whole_rl(type), op, right_orig, &tmp_true, &tmp_false, NULL, NULL);
1564		tmp_true = rl_truncate_cast(get_type(strip_expr(left)), tmp_true);
1565		tmp_false = rl_truncate_cast(get_type(strip_expr(left)), tmp_false);
1566		if (tmp_true && tmp_false)
1567			__save_imaginary_state(left, tmp_true, tmp_false);
1568	}
1569
1570	if (!right_true || !right_false) {
1571		struct range_list *tmp_true, *tmp_false;
1572
1573		split_comparison_rl(alloc_whole_rl(type), op, right_orig, NULL, NULL, &tmp_true, &tmp_false);
1574		tmp_true = rl_truncate_cast(get_type(strip_expr(right)), tmp_true);
1575		tmp_false = rl_truncate_cast(get_type(strip_expr(right)), tmp_false);
1576		if (tmp_true && tmp_false)
1577			__save_imaginary_state(right, tmp_true, tmp_false);
1578	}
1579
1580	left_true_state = alloc_estate_rl(left_true);
1581	left_false_state = alloc_estate_rl(left_false);
1582	right_true_state = alloc_estate_rl(right_true);
1583	right_false_state = alloc_estate_rl(right_false);
1584
1585	switch (op) {
1586	case '<':
1587	case SPECIAL_UNSIGNED_LT:
1588	case SPECIAL_UNSIGNED_LTE:
1589	case SPECIAL_LTE:
1590		if (get_implied_value(right, &dummy) && !in_macro(left, right))
1591			estate_set_hard_max(left_true_state);
1592		if (get_implied_value(left, &dummy) && !in_macro(left, right))
1593			estate_set_hard_max(right_false_state);
1594		break;
1595	case '>':
1596	case SPECIAL_UNSIGNED_GT:
1597	case SPECIAL_UNSIGNED_GTE:
1598	case SPECIAL_GTE:
1599		if (get_implied_value(left, &dummy) && !in_macro(left, right))
1600			estate_set_hard_max(right_true_state);
1601		if (get_implied_value(right, &dummy) && !in_macro(left, right))
1602			estate_set_hard_max(left_false_state);
1603		break;
1604	}
1605
1606	switch (op) {
1607	case '<':
1608	case SPECIAL_UNSIGNED_LT:
1609	case SPECIAL_UNSIGNED_LTE:
1610	case SPECIAL_LTE:
1611		if (get_hard_max(right, &hard_max)) {
1612			if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1613				hard_max.value--;
1614			estate_set_fuzzy_max(left_true_state, hard_max);
1615		}
1616		if (get_implied_value(right, &hard_max)) {
1617			if (op == SPECIAL_UNSIGNED_LTE ||
1618			    op == SPECIAL_LTE)
1619				hard_max.value++;
1620			estate_set_fuzzy_max(left_false_state, hard_max);
1621		}
1622		if (get_hard_max(left, &hard_max)) {
1623			if (op == SPECIAL_UNSIGNED_LTE ||
1624			    op == SPECIAL_LTE)
1625				hard_max.value--;
1626			estate_set_fuzzy_max(right_false_state, hard_max);
1627		}
1628		if (get_implied_value(left, &hard_max)) {
1629			if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1630				hard_max.value++;
1631			estate_set_fuzzy_max(right_true_state, hard_max);
1632		}
1633		break;
1634	case '>':
1635	case SPECIAL_UNSIGNED_GT:
1636	case SPECIAL_UNSIGNED_GTE:
1637	case SPECIAL_GTE:
1638		if (get_hard_max(left, &hard_max)) {
1639			if (op == '>' || op == SPECIAL_UNSIGNED_GT)
1640				hard_max.value--;
1641			estate_set_fuzzy_max(right_true_state, hard_max);
1642		}
1643		if (get_implied_value(left, &hard_max)) {
1644			if (op == SPECIAL_UNSIGNED_GTE ||
1645			    op == SPECIAL_GTE)
1646				hard_max.value++;
1647			estate_set_fuzzy_max(right_false_state, hard_max);
1648		}
1649		if (get_hard_max(right, &hard_max)) {
1650			if (op == SPECIAL_UNSIGNED_LTE ||
1651			    op == SPECIAL_LTE)
1652				hard_max.value--;
1653			estate_set_fuzzy_max(left_false_state, hard_max);
1654		}
1655		if (get_implied_value(right, &hard_max)) {
1656			if (op == '>' ||
1657			    op == SPECIAL_UNSIGNED_GT)
1658				hard_max.value++;
1659			estate_set_fuzzy_max(left_true_state, hard_max);
1660		}
1661		break;
1662	case SPECIAL_EQUAL:
1663		if (get_hard_max(left, &hard_max))
1664			estate_set_fuzzy_max(right_true_state, hard_max);
1665		if (get_hard_max(right, &hard_max))
1666			estate_set_fuzzy_max(left_true_state, hard_max);
1667		break;
1668	}
1669
1670	if (get_hard_max(left, &hard_max)) {
1671		estate_set_hard_max(left_true_state);
1672		estate_set_hard_max(left_false_state);
1673	}
1674	if (get_hard_max(right, &hard_max)) {
1675		estate_set_hard_max(right_true_state);
1676		estate_set_hard_max(right_false_state);
1677	}
1678
1679	if (left_postop == SPECIAL_INCREMENT) {
1680		left_true_state = increment_state(left_true_state);
1681		left_false_state = increment_state(left_false_state);
1682	}
1683	if (left_postop == SPECIAL_DECREMENT) {
1684		left_true_state = decrement_state(left_true_state);
1685		left_false_state = decrement_state(left_false_state);
1686	}
1687	if (right_postop == SPECIAL_INCREMENT) {
1688		right_true_state = increment_state(right_true_state);
1689		right_false_state = increment_state(right_false_state);
1690	}
1691	if (right_postop == SPECIAL_DECREMENT) {
1692		right_true_state = decrement_state(right_true_state);
1693		right_false_state = decrement_state(right_false_state);
1694	}
1695
1696	if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) {
1697		left_true_state = NULL;
1698		left_false_state = NULL;
1699	}
1700
1701	if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) {
1702		right_true_state = NULL;
1703		right_false_state = NULL;
1704	}
1705
1706	/* Don't introduce new states for known true/false conditions */
1707	if (rl_equiv(left_orig, estate_rl(left_true_state)))
1708		left_true_state = NULL;
1709	if (rl_equiv(left_orig, estate_rl(left_false_state)))
1710		left_false_state = NULL;
1711	if (rl_equiv(right_orig, estate_rl(right_true_state)))
1712		right_true_state = NULL;
1713	if (rl_equiv(right_orig, estate_rl(right_false_state)))
1714		right_false_state = NULL;
1715
1716	set_extra_expr_true_false(left, left_true_state, left_false_state);
1717	set_extra_expr_true_false(right, right_true_state, right_false_state);
1718}
1719
1720static int is_simple_math(struct expression *expr)
1721{
1722	if (!expr)
1723		return 0;
1724	if (expr->type != EXPR_BINOP)
1725		return 0;
1726	switch (expr->op) {
1727	case '+':
1728	case '-':
1729	case '*':
1730		return 1;
1731	}
1732	return 0;
1733}
1734
1735static int flip_op(int op)
1736{
1737	/* We only care about simple math */
1738	switch (op) {
1739	case '+':
1740		return '-';
1741	case '-':
1742		return '+';
1743	case '*':
1744		return '/';
1745	}
1746	return 0;
1747}
1748
1749static void move_known_to_rl(struct expression **expr_p, struct range_list **rl_p)
1750{
1751	struct expression *expr = *expr_p;
1752	struct range_list *rl = *rl_p;
1753	sval_t sval;
1754
1755	if (!is_simple_math(expr))
1756		return;
1757
1758	if (get_implied_value(expr->right, &sval)) {
1759		*expr_p = expr->left;
1760		*rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1761		move_known_to_rl(expr_p, rl_p);
1762		return;
1763	}
1764	if (expr->op == '-')
1765		return;
1766	if (get_implied_value(expr->left, &sval)) {
1767		*expr_p = expr->right;
1768		*rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1769		move_known_to_rl(expr_p, rl_p);
1770		return;
1771	}
1772}
1773
1774static void move_known_values(struct expression **left_p, struct expression **right_p)
1775{
1776	struct expression *left = *left_p;
1777	struct expression *right = *right_p;
1778	sval_t sval, dummy;
1779
1780	if (get_implied_value(left, &sval)) {
1781		if (!is_simple_math(right))
1782			return;
1783		if (get_implied_value(right, &dummy))
1784			return;
1785		if (right->op == '*') {
1786			sval_t divisor;
1787
1788			if (!get_value(right->right, &divisor))
1789				return;
1790			if (divisor.value == 0)
1791				return;
1792			*left_p = binop_expression(left, invert_op(right->op), right->right);
1793			*right_p = right->left;
1794			return;
1795		}
1796		if (right->op == '+' && get_value(right->left, &sval)) {
1797			*left_p = binop_expression(left, invert_op(right->op), right->left);
1798			*right_p = right->right;
1799			return;
1800		}
1801		if (get_value(right->right, &sval)) {
1802			*left_p = binop_expression(left, invert_op(right->op), right->right);
1803			*right_p = right->left;
1804			return;
1805		}
1806		return;
1807	}
1808	if (get_implied_value(right, &sval)) {
1809		if (!is_simple_math(left))
1810			return;
1811		if (get_implied_value(left, &dummy))
1812			return;
1813		if (left->op == '*') {
1814			sval_t divisor;
1815
1816			if (!get_value(left->right, &divisor))
1817				return;
1818			if (divisor.value == 0)
1819				return;
1820			*right_p = binop_expression(right, invert_op(left->op), left->right);
1821			*left_p = left->left;
1822			return;
1823		}
1824		if (left->op == '+' && get_value(left->left, &sval)) {
1825			*right_p = binop_expression(right, invert_op(left->op), left->left);
1826			*left_p = left->right;
1827			return;
1828		}
1829
1830		if (get_value(left->right, &sval)) {
1831			*right_p = binop_expression(right, invert_op(left->op), left->right);
1832			*left_p = left->left;
1833			return;
1834		}
1835		return;
1836	}
1837}
1838
1839/*
1840 * The reason for do_simple_algebra() is to solve things like:
1841 * if (foo > 66 || foo + bar > 64) {
1842 * "foo" is not really a known variable so it won't be handled by
1843 * move_known_variables() but it's a super common idiom.
1844 *
1845 */
1846static int do_simple_algebra(struct expression **left_p, struct expression **right_p)
1847{
1848	struct expression *left = *left_p;
1849	struct expression *right = *right_p;
1850	struct range_list *rl;
1851	sval_t tmp;
1852
1853	if (left->type != EXPR_BINOP || left->op != '+')
1854		return 0;
1855	if (can_integer_overflow(get_type(left), left))
1856		return 0;
1857	if (!get_implied_value(right, &tmp))
1858		return 0;
1859
1860	if (!get_implied_value(left->left, &tmp) &&
1861	    get_implied_rl(left->left, &rl) &&
1862	    !is_whole_rl(rl)) {
1863		*right_p = binop_expression(right, '-', left->left);
1864		*left_p = left->right;
1865		return 1;
1866	}
1867	if (!get_implied_value(left->right, &tmp) &&
1868	    get_implied_rl(left->right, &rl) &&
1869	    !is_whole_rl(rl)) {
1870		*right_p = binop_expression(right, '-', left->right);
1871		*left_p = left->left;
1872		return 1;
1873	}
1874
1875	return 0;
1876}
1877
1878static int match_func_comparison(struct expression *expr)
1879{
1880	struct expression *left = strip_expr(expr->left);
1881	struct expression *right = strip_expr(expr->right);
1882
1883	if (left->type == EXPR_CALL || right->type == EXPR_CALL) {
1884		function_comparison(left, expr->op, right);
1885		return 1;
1886	}
1887
1888	return 0;
1889}
1890
1891/* Handle conditions like "if (foo + bar < foo) {" */
1892static int handle_integer_overflow_test(struct expression *expr)
1893{
1894	struct expression *left, *right;
1895	struct symbol *type;
1896	sval_t left_min, right_min, min, max;
1897
1898	if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1899		return 0;
1900
1901	left = strip_parens(expr->left);
1902	right = strip_parens(expr->right);
1903
1904	if (left->op != '+')
1905		return 0;
1906
1907	type = get_type(expr);
1908	if (!type)
1909		return 0;
1910	if (type_positive_bits(type) == 32) {
1911		max.type = &uint_ctype;
1912		max.uvalue = (unsigned int)-1;
1913	} else if (type_positive_bits(type) == 64) {
1914		max.type = &ulong_ctype;
1915		max.value = (unsigned long long)-1;
1916	} else {
1917		return 0;
1918	}
1919
1920	if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right))
1921		return 0;
1922
1923	get_absolute_min(left->left, &left_min);
1924	get_absolute_min(left->right, &right_min);
1925	min = sval_binop(left_min, '+', right_min);
1926
1927	type = get_type(left);
1928	min = sval_cast(type, min);
1929	max = sval_cast(type, max);
1930
1931	set_extra_chunk_true_false(left, NULL, alloc_estate_range(min, max));
1932	return 1;
1933}
1934
1935static void match_comparison(struct expression *expr)
1936{
1937	struct expression *left_orig = strip_parens(expr->left);
1938	struct expression *right_orig = strip_parens(expr->right);
1939	struct expression *left, *right, *tmp;
1940	struct expression *prev;
1941	struct symbol *type;
1942	int redo, count;
1943
1944	if (match_func_comparison(expr))
1945		return;
1946
1947	type = get_type(expr);
1948	if (!type)
1949		type = &llong_ctype;
1950
1951	if (handle_integer_overflow_test(expr))
1952		return;
1953
1954	left = left_orig;
1955	right = right_orig;
1956	move_known_values(&left, &right);
1957	handle_comparison(type, left, expr->op, right);
1958
1959	left = left_orig;
1960	right = right_orig;
1961	if (do_simple_algebra(&left, &right))
1962		handle_comparison(type, left, expr->op, right);
1963
1964	prev = get_assigned_expr(left_orig);
1965	if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) {
1966		left = prev;
1967		right = right_orig;
1968		move_known_values(&left, &right);
1969		handle_comparison(type, left, expr->op, right);
1970	}
1971
1972	prev = get_assigned_expr(right_orig);
1973	if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) {
1974		left = left_orig;
1975		right = prev;
1976		move_known_values(&left, &right);
1977		handle_comparison(type, left, expr->op, right);
1978	}
1979
1980	redo = 0;
1981	left = left_orig;
1982	right = right_orig;
1983	if (get_last_expr_from_expression_stmt(left_orig)) {
1984		left = get_last_expr_from_expression_stmt(left_orig);
1985		redo = 1;
1986	}
1987	if (get_last_expr_from_expression_stmt(right_orig)) {
1988		right = get_last_expr_from_expression_stmt(right_orig);
1989		redo = 1;
1990	}
1991
1992	if (!redo)
1993		return;
1994
1995	count = 0;
1996	while ((tmp = get_assigned_expr(left))) {
1997		if (count++ > 3)
1998			break;
1999		left = strip_expr(tmp);
2000	}
2001	count = 0;
2002	while ((tmp = get_assigned_expr(right))) {
2003		if (count++ > 3)
2004			break;
2005		right = strip_expr(tmp);
2006	}
2007
2008	handle_comparison(type, left, expr->op, right);
2009}
2010
2011static sval_t get_high_mask(sval_t known)
2012{
2013	sval_t ret;
2014	int i;
2015
2016	ret = known;
2017	ret.value = 0;
2018
2019	for (i = type_bits(known.type) - 1; i >= 0; i--) {
2020		if (known.uvalue & (1ULL << i))
2021			ret.uvalue |= (1ULL << i);
2022		else
2023			return ret;
2024
2025	}
2026	return ret;
2027}
2028
2029static bool handle_bit_test(struct expression *expr)
2030{
2031	struct range_list *orig_rl, *rl;
2032	struct expression *shift, *mask, *var;
2033	struct bit_info *bit_info;
2034	sval_t sval;
2035	sval_t high = { .type = &int_ctype };
2036	sval_t low = { .type = &int_ctype };
2037
2038	shift = strip_expr(expr->right);
2039	mask = strip_expr(expr->left);
2040	if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT) {
2041		shift = strip_expr(expr->left);
2042		mask = strip_expr(expr->right);
2043		if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT)
2044			return false;
2045	}
2046	if (!get_implied_value(shift->left, &sval) || sval.value != 1)
2047		return false;
2048	var = strip_expr(shift->right);
2049
2050	bit_info = get_bit_info(mask);
2051	if (!bit_info)
2052		return false;
2053	if (!bit_info->possible)
2054		return false;
2055
2056	get_absolute_rl(var, &orig_rl);
2057	if (sval_is_negative(rl_min(orig_rl)) ||
2058	    rl_max(orig_rl).uvalue > type_bits(get_type(shift->left)))
2059		return false;
2060
2061	low.value = ffsll(bit_info->possible);
2062	high.value = sm_fls64(bit_info->possible);
2063	rl = alloc_rl(low, high);
2064	rl = cast_rl(get_type(var), rl);
2065	rl = rl_intersection(orig_rl, rl);
2066	if (!rl)
2067		return false;
2068
2069	set_extra_expr_true_false(shift->right, alloc_estate_rl(rl), NULL);
2070
2071	return true;
2072}
2073
2074static void handle_AND_op(struct expression *var, sval_t known)
2075{
2076	struct range_list *orig_rl;
2077	struct range_list *true_rl = NULL;
2078	struct range_list *false_rl = NULL;
2079	int bit;
2080	sval_t low_mask = known;
2081	sval_t high_mask;
2082	sval_t max;
2083
2084	get_absolute_rl(var, &orig_rl);
2085
2086	if (known.value > 0) {
2087		bit = ffsll(known.value) - 1;
2088		low_mask.uvalue = (1ULL << bit) - 1;
2089		true_rl = remove_range(orig_rl, sval_type_val(known.type, 0), low_mask);
2090	}
2091	high_mask = get_high_mask(known);
2092	if (high_mask.value) {
2093		bit = ffsll(high_mask.value) - 1;
2094		low_mask.uvalue = (1ULL << bit) - 1;
2095
2096		false_rl = orig_rl;
2097		if (sval_is_negative(rl_min(orig_rl)))
2098			false_rl = remove_range(false_rl, sval_type_min(known.type), sval_type_val(known.type, -1));
2099		false_rl = remove_range(false_rl, low_mask, sval_type_max(known.type));
2100		if (type_signed(high_mask.type) && type_unsigned(rl_type(false_rl))) {
2101			false_rl = remove_range(false_rl,
2102						sval_type_val(rl_type(false_rl), sval_type_max(known.type).uvalue),
2103					sval_type_val(rl_type(false_rl), -1));
2104		}
2105	} else if (known.value == 1 &&
2106		   get_hard_max(var, &max) &&
2107		   sval_cmp(max, rl_max(orig_rl)) == 0 &&
2108		   max.value & 1) {
2109		false_rl = remove_range(orig_rl, max, max);
2110	}
2111	set_extra_expr_true_false(var,
2112				  true_rl ? alloc_estate_rl(true_rl) : NULL,
2113				  false_rl ? alloc_estate_rl(false_rl) : NULL);
2114}
2115
2116static void handle_AND_condition(struct expression *expr)
2117{
2118	sval_t known;
2119
2120	if (handle_bit_test(expr))
2121		return;
2122
2123	if (get_implied_value(expr->left, &known))
2124		handle_AND_op(expr->right, known);
2125	else if (get_implied_value(expr->right, &known))
2126		handle_AND_op(expr->left, known);
2127}
2128
2129static void handle_MOD_condition(struct expression *expr)
2130{
2131	struct range_list *orig_rl;
2132	struct range_list *true_rl;
2133	struct range_list *false_rl = NULL;
2134	sval_t right;
2135	sval_t zero = { 0, };
2136
2137	if (!get_implied_value(expr->right, &right) || right.value == 0)
2138		return;
2139	get_absolute_rl(expr->left, &orig_rl);
2140
2141	zero.value = 0;
2142	zero.type = rl_type(orig_rl);
2143
2144	/* We're basically dorking around the min and max here */
2145	true_rl = remove_range(orig_rl, zero, zero);
2146	if (!sval_is_max(rl_max(true_rl)) &&
2147	    !(rl_max(true_rl).value % right.value))
2148		true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl));
2149
2150	if (rl_equiv(true_rl, orig_rl))
2151		true_rl = NULL;
2152
2153	if (sval_is_positive(rl_min(orig_rl)) &&
2154	    (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) {
2155		sval_t add;
2156		int i;
2157
2158		add = rl_min(orig_rl);
2159		add.value += right.value - (add.value % right.value);
2160		add.value -= right.value;
2161
2162		for (i = 0; i < 5; i++) {
2163			add.value += right.value;
2164			if (add.value > rl_max(orig_rl).value)
2165				break;
2166			add_range(&false_rl, add, add);
2167		}
2168	} else {
2169		if (rl_min(orig_rl).uvalue != 0 &&
2170		    rl_min(orig_rl).uvalue < right.uvalue) {
2171			sval_t chop = right;
2172			chop.value--;
2173			false_rl = remove_range(orig_rl, zero, chop);
2174		}
2175
2176		if (!sval_is_max(rl_max(orig_rl)) &&
2177		    (rl_max(orig_rl).value % right.value)) {
2178			sval_t chop = rl_max(orig_rl);
2179			chop.value -= chop.value % right.value;
2180			chop.value++;
2181			if (!false_rl)
2182				false_rl = clone_rl(orig_rl);
2183			false_rl = remove_range(false_rl, chop, rl_max(orig_rl));
2184		}
2185	}
2186
2187	set_extra_expr_true_false(expr->left,
2188				  true_rl ? alloc_estate_rl(true_rl) : NULL,
2189				  false_rl ? alloc_estate_rl(false_rl) : NULL);
2190}
2191
2192/* this is actually hooked from smatch_implied.c...  it's hacky, yes */
2193void __extra_match_condition(struct expression *expr)
2194{
2195	expr = strip_expr(expr);
2196	switch (expr->type) {
2197	case EXPR_CALL:
2198		function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr());
2199		return;
2200	case EXPR_PREOP:
2201	case EXPR_SYMBOL:
2202	case EXPR_DEREF:
2203		handle_comparison(get_type(expr), expr, SPECIAL_NOTEQUAL, zero_expr());
2204		return;
2205	case EXPR_COMPARE:
2206		match_comparison(expr);
2207		return;
2208	case EXPR_ASSIGNMENT:
2209		__extra_match_condition(expr->left);
2210		return;
2211	case EXPR_BINOP:
2212		if (expr->op == '&')
2213			handle_AND_condition(expr);
2214		if (expr->op == '%')
2215			handle_MOD_condition(expr);
2216		return;
2217	}
2218}
2219
2220static void assume_indexes_are_valid(struct expression *expr)
2221{
2222	struct expression *array_expr;
2223	int array_size;
2224	struct expression *offset;
2225	struct symbol *offset_type;
2226	struct range_list *rl_before;
2227	struct range_list *rl_after;
2228	struct range_list *filter = NULL;
2229	sval_t size;
2230
2231	expr = strip_expr(expr);
2232	if (!is_array(expr))
2233		return;
2234
2235	offset = get_array_offset(expr);
2236	offset_type = get_type(offset);
2237	if (offset_type && type_signed(offset_type)) {
2238		filter = alloc_rl(sval_type_min(offset_type),
2239				  sval_type_val(offset_type, -1));
2240	}
2241
2242	array_expr = get_array_base(expr);
2243	array_size = get_real_array_size(array_expr);
2244	if (array_size > 1) {
2245		size = sval_type_val(offset_type, array_size);
2246		add_range(&filter, size, sval_type_max(offset_type));
2247	}
2248
2249	if (!filter)
2250		return;
2251	get_absolute_rl(offset, &rl_before);
2252	rl_after = rl_filter(rl_before, filter);
2253	if (rl_equiv(rl_before, rl_after))
2254		return;
2255	set_extra_expr_nomod(offset, alloc_estate_rl(rl_after));
2256}
2257
2258/* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
2259int implied_not_equal(struct expression *expr, long long val)
2260{
2261	return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val));
2262}
2263
2264int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val)
2265{
2266	struct smatch_state *estate;
2267
2268	estate = get_state(SMATCH_EXTRA, name, sym);
2269	if (!estate)
2270		return 0;
2271	if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0)))
2272		return 1;
2273	return 0;
2274}
2275
2276int parent_is_null_var_sym(const char *name, struct symbol *sym)
2277{
2278	char buf[256];
2279	char *start;
2280	char *end;
2281	struct smatch_state *state;
2282
2283	strncpy(buf, name, sizeof(buf) - 1);
2284	buf[sizeof(buf) - 1] = '\0';
2285
2286	start = &buf[0];
2287	while (*start == '*') {
2288		start++;
2289		state = __get_state(SMATCH_EXTRA, start, sym);
2290		if (!state)
2291			continue;
2292		if (!estate_rl(state))
2293			return 1;
2294		if (estate_min(state).value == 0 &&
2295		    estate_max(state).value == 0)
2296			return 1;
2297	}
2298
2299	start = &buf[0];
2300	while (*start == '&')
2301		start++;
2302
2303	while ((end = strrchr(start, '-'))) {
2304		*end = '\0';
2305		state = __get_state(SMATCH_EXTRA, start, sym);
2306		if (!state)
2307			continue;
2308		if (estate_min(state).value == 0 &&
2309		    estate_max(state).value == 0)
2310			return 1;
2311	}
2312	return 0;
2313}
2314
2315int parent_is_null(struct expression *expr)
2316{
2317	struct symbol *sym;
2318	char *var;
2319	int ret = 0;
2320
2321	expr = strip_expr(expr);
2322	var = expr_to_var_sym(expr, &sym);
2323	if (!var || !sym)
2324		goto free;
2325	ret = parent_is_null_var_sym(var, sym);
2326free:
2327	free_string(var);
2328	return ret;
2329}
2330
2331static int param_used_callback(void *found, int argc, char **argv, char **azColName)
2332{
2333	*(int *)found = 1;
2334	return 0;
2335}
2336
2337static int is_kzalloc_info(struct sm_state *sm)
2338{
2339	sval_t sval;
2340
2341	/*
2342	 * kzalloc() information is treated as special because so there is just
2343	 * a lot of stuff initialized to zero and it makes building the database
2344	 * take hours and hours.
2345	 *
2346	 * In theory, we should just remove this line and not pass any unused
2347	 * information, but I'm not sure enough that this code works so I want
2348	 * to hold off on that for now.
2349	 */
2350	if (!estate_get_single_value(sm->state, &sval))
2351		return 0;
2352	if (sval.value != 0)
2353		return 0;
2354	return 1;
2355}
2356
2357static int is_really_long(struct sm_state *sm)
2358{
2359	const char *p;
2360	int cnt = 0;
2361
2362	p = sm->name;
2363	while ((p = strstr(p, "->"))) {
2364		p += 2;
2365		cnt++;
2366	}
2367
2368	if (cnt < 3 ||
2369	    strlen(sm->name) < 40)
2370		return 0;
2371	return 1;
2372}
2373
2374static int filter_unused_param_value_info(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2375{
2376	int found = 0;
2377
2378	/* for function pointers assume everything is used */
2379	if (call->fn->type != EXPR_SYMBOL)
2380		return 0;
2381
2382	/*
2383	 * This is to handle __builtin_mul_overflow().  In an ideal world we
2384	 * would only need this for invalid code.
2385	 *
2386	 */
2387	if (!call->fn->symbol)
2388		return 0;
2389
2390	if (!is_kzalloc_info(sm) && !is_really_long(sm))
2391		return 0;
2392
2393	run_sql(&param_used_callback, &found,
2394		"select * from return_implies where %s and type = %d and parameter = %d and key = '%s';",
2395		get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name);
2396	if (found)
2397		return 0;
2398
2399	/* If the database is not built yet, then assume everything is used */
2400	run_sql(&param_used_callback, &found,
2401		"select * from return_implies where %s and type = %d;",
2402		get_static_filter(call->fn->symbol), PARAM_USED);
2403	if (!found)
2404		return 0;
2405
2406	return 1;
2407}
2408
2409struct range_list *intersect_with_real_abs_var_sym(const char *name, struct symbol *sym, struct range_list *start)
2410{
2411	struct smatch_state *state;
2412
2413	/*
2414	 * Here is the difference between implied value and real absolute, say
2415	 * you have:
2416	 *
2417	 *	int a = (u8)x;
2418	 *
2419	 * Then you know that a is 0-255.  That's real absolute.  But you don't
2420	 * know for sure that it actually goes up to 255.  So it's not implied.
2421	 * Implied indicates a degree of certainty.
2422	 *
2423	 * But then say you cap "a" at 8.  That means you know it goes up to
2424	 * 8.  So now the implied value is s32min-8.  But you can combine it
2425	 * with the real absolute to say that actually it's 0-8.
2426	 *
2427	 * We are combining it here.  But now that I think about it, this is
2428	 * probably not the ideal place to combine it because it should proably
2429	 * be done earlier.  Oh well, this is an improvement on what was there
2430	 * before so I'm going to commit this code.
2431	 *
2432	 */
2433
2434	state = get_real_absolute_state_var_sym(name, sym);
2435	if (!state || !estate_rl(state))
2436		return start;
2437
2438	return rl_intersection(estate_rl(state), start);
2439}
2440
2441struct range_list *intersect_with_real_abs_expr(struct expression *expr, struct range_list *start)
2442{
2443	struct smatch_state *state;
2444	struct range_list *abs_rl;
2445
2446	state = get_real_absolute_state(expr);
2447	if (!state || !estate_rl(state))
2448		return start;
2449
2450	abs_rl = cast_rl(rl_type(start), estate_rl(state));
2451	return rl_intersection(abs_rl, start);
2452}
2453
2454static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2455{
2456	struct range_list *rl;
2457	sval_t dummy;
2458
2459	if (estate_is_whole(sm->state) || !estate_rl(sm->state))
2460		return;
2461	if (filter_unused_param_value_info(call, param, printed_name, sm))
2462		return;
2463	rl = estate_rl(sm->state);
2464	rl = intersect_with_real_abs_var_sym(sm->name, sm->sym, rl);
2465	if (!rl)
2466		return;
2467	sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, show_rl(rl));
2468	if (!estate_get_single_value(sm->state, &dummy)) {
2469		if (estate_has_hard_max(sm->state))
2470			sql_insert_caller_info(call, HARD_MAX, param, printed_name,
2471					       sval_to_str(estate_max(sm->state)));
2472		if (estate_has_fuzzy_max(sm->state))
2473			sql_insert_caller_info(call, FUZZY_MAX, param, printed_name,
2474					       sval_to_str(estate_get_fuzzy_max(sm->state)));
2475	}
2476}
2477
2478static void returned_struct_members(int return_id, char *return_ranges, struct expression *expr)
2479{
2480	struct symbol *returned_sym;
2481	char *returned_name;
2482	struct sm_state *sm;
2483	char *compare_str;
2484	char name_buf[256];
2485	char val_buf[256];
2486	int len;
2487
2488	// FIXME handle *$
2489
2490	if (!is_pointer(expr))
2491		return;
2492
2493	returned_name = expr_to_var_sym(expr, &returned_sym);
2494	if (!returned_name || !returned_sym)
2495		goto free;
2496	len = strlen(returned_name);
2497
2498	FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
2499		if (!estate_rl(sm->state))
2500			continue;
2501		if (returned_sym != sm->sym)
2502			continue;
2503		if (strncmp(returned_name, sm->name, len) != 0)
2504			continue;
2505		if (sm->name[len] != '-')
2506			continue;
2507
2508		snprintf(name_buf, sizeof(name_buf), "$%s", sm->name + len);
2509
2510		compare_str = name_sym_to_param_comparison(sm->name, sm->sym);
2511		if (!compare_str && estate_is_whole(sm->state))
2512			continue;
2513		snprintf(val_buf, sizeof(val_buf), "%s%s", sm->state->name, compare_str ?: "");
2514
2515		sql_insert_return_states(return_id, return_ranges, PARAM_VALUE,
2516					 -1, name_buf, val_buf);
2517	} END_FOR_EACH_SM(sm);
2518
2519free:
2520	free_string(returned_name);
2521}
2522
2523static void db_limited_before(void)
2524{
2525	unmatched_stree = clone_stree(__get_cur_stree());
2526}
2527
2528static void db_limited_after(void)
2529{
2530	free_stree(&unmatched_stree);
2531}
2532
2533static int basically_the_same(struct range_list *orig, struct range_list *new)
2534{
2535	if (rl_equiv(orig, new))
2536		return 1;
2537
2538	/*
2539	 * The whole range is essentially the same as 0,4096-27777777777 so
2540	 * don't overwrite the implications just to store that.
2541	 *
2542	 */
2543	if (rl_type(orig)->type == SYM_PTR &&
2544	    is_whole_rl(orig) &&
2545	    rl_min(new).value == 0 &&
2546	    rl_max(new).value == valid_ptr_max)
2547		return 1;
2548	return 0;
2549}
2550
2551static void db_param_limit_binops(struct expression *arg, char *key, struct range_list *rl)
2552{
2553	struct range_list *left_rl;
2554	sval_t zero = {	.type = rl_type(rl), };
2555	sval_t sval;
2556
2557	if (arg->op != '*')
2558		return;
2559	if (!get_implied_value(arg->right, &sval))
2560		return;
2561	if (can_integer_overflow(get_type(arg), arg))
2562		return;
2563
2564	left_rl = rl_binop(rl, '/', alloc_rl(sval, sval));
2565	if (!rl_has_sval(rl, zero))
2566		left_rl = remove_range(left_rl, zero, zero);
2567
2568	set_extra_expr_nomod(arg->left, alloc_estate_rl(left_rl));
2569}
2570
2571static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op)
2572{
2573	struct expression *arg;
2574	char *name;
2575	struct symbol *sym;
2576	struct var_sym_list *vsl = NULL;
2577	struct sm_state *sm;
2578	struct symbol *compare_type, *var_type;
2579	struct range_list *rl;
2580	struct range_list *limit;
2581	struct range_list *new;
2582	char *other_name;
2583	struct symbol *other_sym;
2584
2585	while (expr->type == EXPR_ASSIGNMENT)
2586		expr = strip_expr(expr->right);
2587	if (expr->type != EXPR_CALL)
2588		return;
2589
2590	arg = get_argument_from_call_expr(expr->args, param);
2591	if (!arg)
2592		return;
2593
2594	if (strcmp(key, "$") == 0)
2595		compare_type = get_arg_type(expr->fn, param);
2596	else
2597		compare_type = get_member_type_from_key(arg, key);
2598
2599	call_results_to_rl(expr, compare_type, value, &limit);
2600	if (strcmp(key, "$") == 0)
2601		move_known_to_rl(&arg, &limit);
2602	name = get_chunk_from_key(arg, key, &sym, &vsl);
2603	if (!name)
2604		return;
2605	if (op != PARAM_LIMIT && !sym)
2606		goto free;
2607
2608	sm = get_sm_state(SMATCH_EXTRA, name, sym);
2609	if (sm)
2610		rl = estate_rl(sm->state);
2611	else
2612		rl = alloc_whole_rl(compare_type);
2613
2614	if (op == PARAM_LIMIT && !rl_fits_in_type(rl, compare_type))
2615		goto free;
2616
2617	new = rl_intersection(rl, limit);
2618
2619	var_type = get_member_type_from_key(arg, key);
2620	new = cast_rl(var_type, new);
2621
2622	/* We want to preserve the implications here */
2623	if (sm && basically_the_same(rl, new))
2624		goto free;
2625	other_name = get_other_name_sym(name, sym, &other_sym);
2626
2627	if (op == PARAM_LIMIT)
2628		set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(new));
2629	else
2630		set_extra_mod(name, sym, NULL, alloc_estate_rl(new));
2631
2632	if (other_name && other_sym) {
2633		if (op == PARAM_LIMIT)
2634			set_extra_nomod_vsl(other_name, other_sym, vsl, NULL, alloc_estate_rl(new));
2635		else
2636			set_extra_mod(other_name, other_sym, NULL, alloc_estate_rl(new));
2637	}
2638
2639	if (op == PARAM_LIMIT && arg->type == EXPR_BINOP)
2640		db_param_limit_binops(arg, key, new);
2641free:
2642	free_string(name);
2643}
2644
2645static void db_param_limit(struct expression *expr, int param, char *key, char *value)
2646{
2647	db_param_limit_filter(expr, param, key, value, PARAM_LIMIT);
2648}
2649
2650static void db_param_filter(struct expression *expr, int param, char *key, char *value)
2651{
2652	db_param_limit_filter(expr, param, key, value, PARAM_FILTER);
2653}
2654
2655static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op)
2656{
2657	struct expression *arg, *gen_expr;
2658	char *name;
2659	char *other_name = NULL;
2660	struct symbol *sym, *other_sym;
2661	struct symbol *param_type, *arg_type;
2662	struct smatch_state *state;
2663	struct range_list *new = NULL;
2664	struct range_list *added = NULL;
2665
2666	while (expr->type == EXPR_ASSIGNMENT)
2667		expr = strip_expr(expr->right);
2668	if (expr->type != EXPR_CALL)
2669		return;
2670
2671	arg = get_argument_from_call_expr(expr->args, param);
2672	if (!arg)
2673		return;
2674
2675	arg_type = get_arg_type_from_key(expr->fn, param, arg, key);
2676	param_type = get_member_type_from_key(arg, key);
2677	if (param_type && param_type->type == SYM_STRUCT)
2678		return;
2679	name = get_variable_from_key(arg, key, &sym);
2680	if (!name || !sym)
2681		goto free;
2682	gen_expr = gen_expression_from_key(arg, key);
2683
2684	state = get_state(SMATCH_EXTRA, name, sym);
2685	if (state)
2686		new = estate_rl(state);
2687
2688	call_results_to_rl(expr, arg_type, value, &added);
2689	added = cast_rl(param_type, added);
2690	if (op == PARAM_SET)
2691		new = added;
2692	else
2693		new = rl_union(new, added);
2694
2695	other_name = get_other_name_sym_nostack(name, sym, &other_sym);
2696	set_extra_mod(name, sym, gen_expr, alloc_estate_rl(new));
2697	if (other_name && other_sym)
2698		set_extra_mod(other_name, other_sym, gen_expr, alloc_estate_rl(new));
2699free:
2700	free_string(other_name);
2701	free_string(name);
2702}
2703
2704static void db_param_add(struct expression *expr, int param, char *key, char *value)
2705{
2706	in_param_set = true;
2707	db_param_add_set(expr, param, key, value, PARAM_ADD);
2708	in_param_set = false;
2709}
2710
2711static void db_param_set(struct expression *expr, int param, char *key, char *value)
2712{
2713	in_param_set = true;
2714	db_param_add_set(expr, param, key, value, PARAM_SET);
2715	in_param_set = false;
2716}
2717
2718static void match_lost_param(struct expression *call, int param)
2719{
2720	struct expression *arg;
2721
2722	if (is_const_param(call->fn, param))
2723		return;
2724
2725	arg = get_argument_from_call_expr(call->args, param);
2726	if (!arg)
2727		return;
2728
2729	arg = strip_expr(arg);
2730	if (arg->type == EXPR_PREOP && arg->op == '&')
2731		set_extra_expr_mod(arg->unop, alloc_estate_whole(get_type(arg->unop)));
2732	else
2733		; /* if pointer then set struct members, maybe?*/
2734}
2735
2736static void db_param_value(struct expression *expr, int param, char *key, char *value)
2737{
2738	struct expression *call;
2739	char *name;
2740	struct symbol *sym;
2741	struct symbol *type;
2742	struct range_list *rl = NULL;
2743
2744	if (param != -1)
2745		return;
2746
2747	call = expr;
2748	while (call->type == EXPR_ASSIGNMENT)
2749		call = strip_expr(call->right);
2750	if (call->type != EXPR_CALL)
2751		return;
2752
2753	type = get_member_type_from_key(expr->left, key);
2754	name = get_variable_from_key(expr->left, key, &sym);
2755	if (!name || !sym)
2756		goto free;
2757
2758	call_results_to_rl(call, type, value, &rl);
2759
2760	set_extra_mod(name, sym, NULL, alloc_estate_rl(rl));
2761free:
2762	free_string(name);
2763}
2764
2765static void match_call_info(struct expression *expr)
2766{
2767	struct smatch_state *state;
2768	struct range_list *rl = NULL;
2769	struct expression *arg;
2770	struct symbol *type;
2771	sval_t dummy;
2772	int i = 0;
2773
2774	FOR_EACH_PTR(expr->args, arg) {
2775		type = get_arg_type(expr->fn, i);
2776
2777		get_absolute_rl(arg, &rl);
2778		rl = cast_rl(type, rl);
2779
2780		if (!is_whole_rl(rl)) {
2781			rl = intersect_with_real_abs_expr(arg, rl);
2782			sql_insert_caller_info(expr, PARAM_VALUE, i, "$", show_rl(rl));
2783		}
2784		state = get_state_expr(SMATCH_EXTRA, arg);
2785		if (!estate_get_single_value(state, &dummy) && estate_has_hard_max(state)) {
2786			sql_insert_caller_info(expr, HARD_MAX, i, "$",
2787					       sval_to_str(estate_max(state)));
2788		}
2789		if (estate_has_fuzzy_max(state)) {
2790			sql_insert_caller_info(expr, FUZZY_MAX, i, "$",
2791					       sval_to_str(estate_get_fuzzy_max(state)));
2792		}
2793		i++;
2794	} END_FOR_EACH_PTR(arg);
2795}
2796
2797static void set_param_value(const char *name, struct symbol *sym, char *key, char *value)
2798{
2799	struct expression *expr;
2800	struct range_list *rl = NULL;
2801	struct smatch_state *state;
2802	struct symbol *type;
2803	char fullname[256];
2804	char *key_orig = key;
2805	bool add_star = false;
2806	sval_t dummy;
2807
2808	if (key[0] == '*') {
2809		add_star = true;
2810		key++;
2811	}
2812
2813	snprintf(fullname, 256, "%s%s%s", add_star ? "*" : "", name, key + 1);
2814
2815	expr = symbol_expression(sym);
2816	type = get_member_type_from_key(expr, key_orig);
2817	str_to_rl(type, value, &rl);
2818	state = alloc_estate_rl(rl);
2819	if (estate_get_single_value(state, &dummy))
2820		estate_set_hard_max(state);
2821	set_state(SMATCH_EXTRA, fullname, sym, state);
2822}
2823
2824static void set_param_fuzzy_max(const char *name, struct symbol *sym, char *key, char *value)
2825{
2826	struct range_list *rl = NULL;
2827	struct smatch_state *state;
2828	struct symbol *type;
2829	char fullname[256];
2830	sval_t max;
2831
2832	if (strcmp(key, "*$") == 0)
2833		snprintf(fullname, sizeof(fullname), "*%s", name);
2834	else if (strncmp(key, "$", 1) == 0)
2835		snprintf(fullname, 256, "%s%s", name, key + 1);
2836	else
2837		return;
2838
2839	state = get_state(SMATCH_EXTRA, fullname, sym);
2840	if (!state)
2841		return;
2842	type = estate_type(state);
2843	str_to_rl(type, value, &rl);
2844	if (!rl_to_sval(rl, &max))
2845		return;
2846	estate_set_fuzzy_max(state, max);
2847}
2848
2849static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value)
2850{
2851	struct smatch_state *state;
2852	char fullname[256];
2853
2854	if (strcmp(key, "*$") == 0)
2855		snprintf(fullname, sizeof(fullname), "*%s", name);
2856	else if (strncmp(key, "$", 1) == 0)
2857		snprintf(fullname, 256, "%s%s", name, key + 1);
2858	else
2859		return;
2860
2861	state = get_state(SMATCH_EXTRA, fullname, sym);
2862	if (!state)
2863		return;
2864	estate_set_hard_max(state);
2865}
2866
2867struct sm_state *get_extra_sm_state(struct expression *expr)
2868{
2869	char *name;
2870	struct symbol *sym;
2871	struct sm_state *ret = NULL;
2872
2873	name = expr_to_known_chunk_sym(expr, &sym);
2874	if (!name)
2875		goto free;
2876
2877	ret = get_sm_state(SMATCH_EXTRA, name, sym);
2878free:
2879	free_string(name);
2880	return ret;
2881}
2882
2883struct smatch_state *get_extra_state(struct expression *expr)
2884{
2885	struct sm_state *sm;
2886
2887	sm = get_extra_sm_state(expr);
2888	if (!sm)
2889		return NULL;
2890	return sm->state;
2891}
2892
2893void register_smatch_extra(int id)
2894{
2895	my_id = id;
2896
2897	set_dynamic_states(my_id);
2898	add_merge_hook(my_id, &merge_estates);
2899	add_unmatched_state_hook(my_id, &unmatched_state);
2900	select_caller_info_hook(set_param_value, PARAM_VALUE);
2901	select_caller_info_hook(set_param_fuzzy_max, FUZZY_MAX);
2902	select_caller_info_hook(set_param_hard_max, HARD_MAX);
2903	select_return_states_before(&db_limited_before);
2904	select_return_states_hook(PARAM_LIMIT, &db_param_limit);
2905	select_return_states_hook(PARAM_FILTER, &db_param_filter);
2906	select_return_states_hook(PARAM_ADD, &db_param_add);
2907	select_return_states_hook(PARAM_SET, &db_param_set);
2908	add_lost_param_hook(&match_lost_param);
2909	select_return_states_hook(PARAM_VALUE, &db_param_value);
2910	select_return_states_after(&db_limited_after);
2911}
2912
2913static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
2914{
2915	struct var_sym_list *links;
2916	struct var_sym *tmp;
2917	struct smatch_state *state;
2918
2919	links = sm->state->data;
2920
2921	FOR_EACH_PTR(links, tmp) {
2922		if (sm->sym == tmp->sym &&
2923		    strcmp(sm->name, tmp->var) == 0)
2924			continue;
2925		state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym);
2926		if (!state)
2927			continue;
2928		set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state)));
2929	} END_FOR_EACH_PTR(tmp);
2930	set_state(link_id, sm->name, sm->sym, &undefined);
2931}
2932
2933void register_smatch_extra_links(int id)
2934{
2935	link_id = id;
2936	set_dynamic_states(link_id);
2937}
2938
2939void register_smatch_extra_late(int id)
2940{
2941	add_merge_hook(link_id, &merge_link_states);
2942	add_modification_hook(link_id, &match_link_modify);
2943	add_hook(&match_dereferences, DEREF_HOOK);
2944	add_hook(&match_pointer_as_array, OP_HOOK);
2945	select_return_implies_hook(DEREFERENCE, &set_param_dereferenced);
2946	add_hook(&match_function_call, FUNCTION_CALL_HOOK);
2947	add_hook(&match_assign, ASSIGNMENT_HOOK);
2948	add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK);
2949	add_hook(&unop_expr, OP_HOOK);
2950	add_hook(&asm_expr, ASM_HOOK);
2951
2952	add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2953	add_member_info_callback(my_id, struct_member_callback);
2954	add_split_return_callback(&returned_struct_members);
2955
2956//	add_hook(&assume_indexes_are_valid, OP_HOOK);
2957}
2958