path: root/scripts/kconfig/expr.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
 */

#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <hash.h>
#include <xalloc.h>
#include "internal.h"
#include "lkc.h"

#define DEBUG_EXPR	0

HASHTABLE_DEFINE(expr_hashtable, EXPR_HASHSIZE);

static struct expr *expr_eliminate_yn(struct expr *e);

/**
 * expr_lookup - return the expression with the given type and sub-nodes
 * This looks up an expression with the specified type and sub-nodes. If such
 * an expression is found in the hash table, it is returned. Otherwise, a new
 * expression node is allocated and added to the hash table.
 * @type: expression type
 * @l: left node
 * @r: right node
 * return: expression
 */
static struct expr *expr_lookup(enum expr_type type, void *l, void *r)
{
	struct expr *e;
	int hash;

	hash = hash_32((unsigned int)type ^ hash_ptr(l) ^ hash_ptr(r));

	hash_for_each_possible(expr_hashtable, e, node, hash) {
		if (e->type == type && e->left._initdata == l &&
		    e->right._initdata == r)
			return e;
	}

	e = xmalloc(sizeof(*e));
	e->type = type;
	e->left._initdata = l;
	e->right._initdata = r;
	e->val_is_valid = false;

	hash_add(expr_hashtable, &e->node, hash);

	return e;
}

struct expr *expr_alloc_symbol(struct symbol *sym)
{
	return expr_lookup(E_SYMBOL, sym, NULL);
}

struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
{
	return expr_lookup(type, ce, NULL);
}

struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
{
	return expr_lookup(type, e1, e2);
}

struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
{
	return expr_lookup(type, s1, s2);
}

struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
{
	if (!e1)
		return e2;
	return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
}

struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
{
	if (!e1)
		return e2;
	return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
}

static int trans_count;

/*
 * expr_eliminate_eq() helper.
 *
 * Walks the two expression trees given in 'ep1' and 'ep2'. Any node that does
 * not have type 'type' (E_OR/E_AND) is considered a leaf, and is compared
 * against all other leaves. Two equal leaves are both replaced with either 'y'
 * or 'n' as appropriate for 'type', to be eliminated later.
 */
static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
{
	struct expr *l, *r;

	/* Recurse down to leaves */

	if ((*ep1)->type == type) {
		l = (*ep1)->left.expr;
		r = (*ep1)->right.expr;
		__expr_eliminate_eq(type, &l, ep2);
		__expr_eliminate_eq(type, &r, ep2);
		*ep1 = expr_alloc_two(type, l, r);
		return;
	}
	if ((*ep2)->type == type) {
		l = (*ep2)->left.expr;
		r = (*ep2)->right.expr;
		__expr_eliminate_eq(type, ep1, &l);
		__expr_eliminate_eq(type, ep1, &r);
		*ep2 = expr_alloc_two(type, l, r);
		return;
	}

	/* *ep1 and *ep2 are leaves. Compare them. */

	if ((*ep1)->type == E_SYMBOL && (*ep2)->type == E_SYMBOL &&
	    (*ep1)