From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1EE15C433F5 for ; Wed, 20 Oct 2021 09:43:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DC136611C6 for ; Wed, 20 Oct 2021 09:43:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229632AbhJTJpW (ORCPT ); Wed, 20 Oct 2021 05:45:22 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:41830 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229570AbhJTJpV (ORCPT ); Wed, 20 Oct 2021 05:45:21 -0400 Received: from out3.mail.ruhr-uni-bochum.de (out3.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:8:1001::8693:359b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A77D5C06161C for ; Wed, 20 Oct 2021 02:43:06 -0700 (PDT) Received: from mx3.mail.ruhr-uni-bochum.de (localhost [127.0.0.1]) by out3.mail.ruhr-uni-bochum.de (Postfix mo-ext) with ESMTP id 4HZ5JT2sfhz8SFg; Wed, 20 Oct 2021 11:43:05 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rub.de; s=mail-2017; t=1634722985; bh=5aOcVbLbB16UnueR64SouTRjcbgfk/VdJycpNeD3RFQ=; h=Date:Subject:From:To:Cc:References:In-Reply-To:From; b=oSNdUl6m0/OmSrCZgl0pkQqNF0E7g45JbV4Cm5Ofw8THnLX/+2TcAs6ZbnZT0JCG1 TjIZAgj2wegZZ2LTd8jv2A/Zois95zQE7ldGpP+COv6rnxcncAvPHne5Nlyizn/hca NBBQl9kQMAnzYp/BSnS5QImubnEmKYkAyGhn9q30= Received: from out3.mail.ruhr-uni-bochum.de (localhost [127.0.0.1]) by mx3.mail.ruhr-uni-bochum.de (Postfix idis) with ESMTP id 4HZ5JT1fx0z8SDH; Wed, 20 Oct 2021 11:43:05 +0200 (CEST) X-RUB-Notes: Internal origin=IPv6:2a05:3e00:c:1001::8693:2aec X-Envelope-Sender: Received: from mail2.mail.ruhr-uni-bochum.de (mail2.mail.ruhr-uni-bochum.de [IPv6:2a05:3e00:c:1001::8693:2aec]) by out3.mail.ruhr-uni-bochum.de (Postfix mi-int) with ESMTP id 4HZ5JS6w9fz8SFZ; Wed, 20 Oct 2021 11:43:04 +0200 (CEST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.1 at mx3.mail.ruhr-uni-bochum.de Received: from [192.168.188.22] (unknown [5.63.49.65]) by mail2.mail.ruhr-uni-bochum.de (Postfix) with ESMTPSA id 4HZ5JS3gVJzDgyr; Wed, 20 Oct 2021 11:43:04 +0200 (CEST) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.0 at mail2.mail.ruhr-uni-bochum.de Message-ID: Date: Wed, 20 Oct 2021 11:43:03 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.2.0 Subject: [RFC 07/12] Add files for handling expressions Content-Language: en-US From: Thorsten Berger To: linux-kbuild@vger.kernel.org Cc: "Luis R. Rodriguez" , deltaone@debian.org, phayax@gmail.com, Eugene Groshev , Sarah Nadi , Mel Gorman , "Luis R. Rodriguez" References: In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Precedence: bulk List-ID: X-Mailing-List: linux-kbuild@vger.kernel.org Co-developed-by: Patrick Franz Signed-off-by: Patrick Franz Co-developed-by: Ibrahim Fayaz Signed-off-by: Ibrahim Fayaz Reviewed-by: Luis Chamberlain Tested-by: Evgeny Groshev Suggested-by: Sarah Nadi Suggested-by: Thorsten Berger Signed-off-by: Thorsten Berger ---  scripts/kconfig/cf_expr.c | 2146 +++++++++++++++++++++++++++++++++++++  scripts/kconfig/cf_expr.h |  237 ++++  2 files changed, 2383 insertions(+)  create mode 100644 scripts/kconfig/cf_expr.c  create mode 100644 scripts/kconfig/cf_expr.h diff --git a/scripts/kconfig/cf_expr.c b/scripts/kconfig/cf_expr.c new file mode 100644 index 000000000000..7ca0ff4bc6ad --- /dev/null +++ b/scripts/kconfig/cf_expr.c @@ -0,0 +1,2146 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * Copyright (C) 2021 Patrick Franz + */ + +#define _GNU_SOURCE +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "configfix.h" + +static void create_fexpr_bool(struct symbol *sym); +static void create_fexpr_nonbool(struct symbol *sym); +static void create_fexpr_unknown(struct symbol *sym); +static void create_fexpr_choice(struct symbol *sym); + +static void pexpr_print_util(struct pexpr *e, int prevtoken); + +static int trans_count; + + +/* + *  create a fexpr + */ +struct fexpr * fexpr_create(int satval, enum fexpr_type type, char *name) +{ +    struct fexpr *e = xcalloc(1, sizeof(*e)); +    e->satval = satval; +    e->type = type; +    e->name = str_new(); +    e->assumption = false; +    str_append(&e->name, name); + +    return e; +} + +/* + * create the fexpr for a symbol + */ +void sym_create_fexpr(struct symbol *sym) +{ +    if (sym_is_choice(sym)) +        create_fexpr_choice(sym); +    else if (sym_is_boolean(sym)) +        create_fexpr_bool(sym); +    else if (sym_is_nonboolean(sym)) +        create_fexpr_nonbool(sym); +    else +        create_fexpr_unknown(sym); +} + +/* + * create the fexpr for symbols with reverse dependencies + */ +static void create_fexpr_selected(struct symbol *sym) +{ +    /* fexpr_sel_y */ +    struct fexpr *fexpr_sel_y = fexpr_create(sat_variable_nr++, FE_SELECT, sym->name); +    str_append(&fexpr_sel_y->name, "_sel_y"); +    fexpr_sel_y->sym = sym; +    fexpr_add_to_satmap(fexpr_sel_y); + +    sym->fexpr_sel_y = fexpr_sel_y; + +    /* fexpr_sel_m */ +    if (sym->type == S_BOOLEAN) +        return; +    struct fexpr *fexpr_sel_m = fexpr_create(sat_variable_nr++, FE_SELECT, sym->name); +    str_append(&fexpr_sel_m->name, "_sel_m"); +    fexpr_sel_m->sym = sym; +    fexpr_add_to_satmap(fexpr_sel_m); + +    sym->fexpr_sel_m = fexpr_sel_m; +} + +/* + * create the fexpr for a boolean/tristate symbol + */ +static void create_fexpr_bool(struct symbol *sym) +{ +    struct fexpr *fexpr_y = fexpr_create(sat_variable_nr++, FE_SYMBOL, sym->name); +    fexpr_y->sym = sym; +    fexpr_y->tri = yes; +    fexpr_add_to_satmap(fexpr_y); + +    sym->fexpr_y = fexpr_y; + +    struct fexpr *fexpr_m; +    if (sym->type == S_TRISTATE) { +        fexpr_m = fexpr_create(sat_variable_nr++, FE_SYMBOL, sym->name); +        str_append(&fexpr_m->name, "_MODULE"); +        fexpr_m->sym = sym; +        fexpr_m->tri = mod; +        fexpr_add_to_satmap(fexpr_m); +    } else { +        fexpr_m = const_false; +    } + +    sym->fexpr_m = fexpr_m; + +    if (sym->rev_dep.expr) +        create_fexpr_selected(sym); +} + +/* + * create the fexpr for a non-boolean symbol + */ +static void create_fexpr_nonbool(struct symbol *sym) +{ +    sym->fexpr_y = const_false; +    sym->fexpr_m = const_false; +    sym->nb_vals = fexpr_list_init(); + +    /* default values */ +    char int_values[][2] = {"n", "0", "1"}; +    char hex_values[][4] = {"n", "0x0", "0x1"}; +    char string_values[][9] = {"n", "", "nonempty"}; + +    int i; +    for (i = 0; i < 3; i++) { +        struct fexpr *e = fexpr_create(sat_variable_nr++, FE_NONBOOL, sym->name); +        e->sym = sym; +        str_append(&e->name, "="); +        e->nb_val = str_new(); + +        switch (sym->type) { +        case S_INT: +            str_append(&e->name, int_values[i]); +            str_append(&e->nb_val, int_values[i]); +            break; +        case S_HEX: +            str_append(&e->name, hex_values[i]); +            str_append(&e->nb_val, hex_values[i]); +            break; +        case S_STRING: +            str_append(&e->name, string_values[i]); +            str_append(&e->nb_val, string_values[i]); +            break; +        default: +            break; +        } + +        fexpr_list_add(sym->nb_vals, e); +        fexpr_add_to_satmap(e); +    } +} + + +/* + * set fexpr_y and fexpr_m simply to False + */ +static void create_fexpr_unknown(struct symbol *sym) +{ +    sym->fexpr_y = const_false; +    sym->fexpr_m = const_false; +} + + +/* + * create the fexpr for a choice symbol + */ +static void create_fexpr_choice(struct symbol *sym) +{ +    if (!sym_is_boolean(sym)) +        return; + +    struct property *prompt = sym_get_prompt(sym); +    if (prompt == NULL) { +        perror("Choice symbol should have a prompt."); +        return; +    } + +    char *name = strdup(prompt->text); + +    /* remove spaces */ +    char *write = name, *read = name; +    do { +        if (*read != ' ') +            *write++ = *read; +    } while (*read++); + +    struct fexpr *fexpr_y = fexpr_create(sat_variable_nr++, FE_CHOICE, "Choice_"); +    str_append(&fexpr_y->name, name); +    fexpr_y->sym = sym; +    fexpr_y->tri = yes; +    fexpr_add_to_satmap(fexpr_y); + +    sym->fexpr_y = fexpr_y; + +    struct fexpr *fexpr_m; +    if (sym->type == S_TRISTATE) { +        fexpr_m = fexpr_create(sat_variable_nr++, FE_CHOICE, "Choice_"); +        str_append(&fexpr_m->name, name); +        str_append(&fexpr_m->name, "_MODULE"); +        fexpr_m->sym = sym; +        fexpr_m->tri = mod; +        fexpr_add_to_satmap(fexpr_m); +    } else { +        fexpr_m = const_false; +    } +    sym->fexpr_m = fexpr_m; +} + +/* + * evaluate an unequality between a non-Boolean symbol and a constant + */ +static struct pexpr * expr_eval_unequal_nonbool_const(struct symbol *sym, struct symbol *compval, enum expr_type type) +{ +    if (!sym || !compval) +        return pexf(const_false); + +    int base = 0; +    switch (sym->type) { +    case S_INT: +        base = 10; +        break; +    case S_HEX: +        base = 16; +        break; +    default: +        break; +    } + +    struct pexpr *c = pexf(const_false); +    long val = strtol(compval->name, NULL, base); + +    struct fexpr_node *node; +    struct fexpr *fe; +    for (node = sym->nb_vals->head->next; node != NULL; node = node->next) { +        fe = node->elem; +        long symval = strtol(str_get(&fe->nb_val), NULL, base); + +        switch (type) { +        case E_LTH: +            if (symval < val) +                c = pexpr_or(c, pexf(fe)); +            break; +        case E_LEQ: +            if (symval <= val) +                c = pexpr_or(c, pexf(fe)); +            break; +        case E_GTH: +            if (symval > val) +                c = pexpr_or(c, pexf(fe)); +            break; +        case E_GEQ: +            if (symval >= val) +                c = pexpr_or(c, pexf(fe)); +            break; +        default: +            perror("Illegal unequal."); +        } +    } + +    return c; +} + +/* + * evaluate an unequality between 2 Boolean symbols + */ +static struct pexpr * expr_eval_unequal_bool(struct symbol *left, struct symbol *right, enum expr_type type) +{ +    if (!left || !right) +        return pexf(const_false); + +    if (!sym_is_boolean(left) || !sym_is_boolean(right)) { +        perror("Comparing 2 symbols that should be boolean."); +        return pexf(const_false); +    } + +    struct pexpr *c = pexf(const_false); +    switch (type) { +    case E_LTH: +        c = pexpr_and( +            pexpr_not(sym_get_fexpr_both(left)), +            sym_get_fexpr_both(right)); +        if (left->type == S_TRISTATE) +            c = pexpr_or(c, +                pexpr_and +                    (pexf(left->fexpr_m), +                     pexf(right->fexpr_y))); +        break; +    case E_LEQ: +        c = pexpr_and(pexf(left->fexpr_y), pexf(right->fexpr_y)); +        if (left->type == S_TRISTATE) +            c = pexpr_or(c, +                pexpr_and( +                    pexf(left->fexpr_m), +                    sym_get_fexpr_both(right))); +        c = pexpr_or(c, pexpr_not(sym_get_fexpr_both(left))); +        break; +    case E_GTH: +        c = pexpr_and( +            sym_get_fexpr_both(left), +            pexpr_not(sym_get_fexpr_both(right))); +        if (right->type == S_TRISTATE) +            c = pexpr_or(c, +                pexpr_and +                    (pexf(left->fexpr_y), +                     pexf(right->fexpr_m))); +        break; +    case E_GEQ: +        c = pexpr_and(pexf(left->fexpr_y), pexf(right->fexpr_y)); +        if (right->type == S_TRISTATE) +            c = pexpr_or(c, +                pexpr_and( +                    sym_get_fexpr_both(left), +                    pexf(right->fexpr_m))); +        c = pexpr_or(c, pexpr_not(sym_get_fexpr_both(right))); +        break; +    default: +        perror("Wrong type in expr_eval_unequal_bool."); +    } + +    return c; +} +/* + * calculate, when expr will evaluate to yes or mod + */ +struct pexpr * expr_calculate_pexpr_both(struct expr *e) +{ +    if (!e) +        return pexf(const_false); + +    if (!expr_can_evaluate_to_mod(e)) +        return expr_calculate_pexpr_y(e); + +    switch (e->type) { +    case E_SYMBOL: +        return pexpr_or(expr_calculate_pexpr_m(e), expr_calculate_pexpr_y(e)); +    case E_AND: +        return expr_calculate_pexpr_both_and(e->left.expr, e->right.expr); +    case E_OR: +        return expr_calculate_pexpr_both_or(e->left.expr, e->right.expr); +    case E_NOT: +        return pexpr_or(expr_calculate_pexpr_m(e), expr_calculate_pexpr_y(e)); +    case E_EQUAL: +        return expr_calculate_pexpr_y_equals(e); +    case E_UNEQUAL: +        return expr_calculate_pexpr_y_unequals(e); +    case E_LTH: +    case E_LEQ: +    case E_GTH: +    case E_GEQ: +        return expr_calculate_pexpr_y_comp(e); +    default: +        // TODO +        perror("Unhandled type - expr_calculate_pexpr_both"); +        return NULL; +    } +} + +/* + * calculate, when expr will evaluate to yes + */ +struct pexpr * expr_calculate_pexpr_y(struct expr *e){ +    if (!e) +        return NULL; + +    switch (e->type) { +    case E_SYMBOL: +        return pexf(e->left.sym->fexpr_y); +    case E_AND: +        return expr_calculate_pexpr_y_and(e->left.expr, e->right.expr); +    case E_OR: +        return expr_calculate_pexpr_y_or(e->left.expr, e->right.expr); +    case E_NOT: +        return expr_calculate_pexpr_y_not(e->left.expr); +    case E_EQUAL: +        return expr_calculate_pexpr_y_equals(e); +    case E_UNEQUAL: +        return expr_calculate_pexpr_y_unequals(e); +    case E_LTH: +    case E_LEQ: +    case E_GTH: +    case E_GEQ: +        return expr_calculate_pexpr_y_comp(e); +    default: +        perror("Unhandled type - expr_calculate_pexpr_y"); +        return NULL; +    } +} + +/* + * calculate, when expr will evaluate to mod + */ +struct pexpr * expr_calculate_pexpr_m(struct expr *e){ +    if (!e) +        return NULL; + +    if (!expr_can_evaluate_to_mod(e)) +        return pexf(const_false); + +    switch (e->type) { +    case E_SYMBOL: +        return pexf(e->left.sym->fexpr_m); +    case E_AND: +        return expr_calculate_pexpr_m_and(e->left.expr, e->right.expr); +    case E_OR: +        return expr_calculate_pexpr_m_or(e->left.expr, e->right.expr); +    case E_NOT: +        return expr_calculate_pexpr_m_not(e->left.expr); +    default: +        perror("Trying to evaluate to mod."); +        return NULL; +    } +} + +/* + * calculate, when expr of type AND will evaluate to yes + * A && B + */ +struct pexpr * expr_calculate_pexpr_y_and(struct expr *a, struct expr *b) +{ +    return pexpr_and(expr_calculate_pexpr_y(a), expr_calculate_pexpr_y(b)); +} + +/* + * calculate, when expr of type AND will evaluate to mod + * (A || A_m) && (B || B_m) && !(A && B) + */ +struct pexpr * expr_calculate_pexpr_m_and(struct expr *a, struct expr *b) +{ +    struct pexpr *topright = pexpr_not(pexpr_and(expr_calculate_pexpr_y(a), expr_calculate_pexpr_y(b))); +    struct pexpr *ll_left = pexpr_or(expr_calculate_pexpr_y(a), expr_calculate_pexpr_m(a)); +    struct pexpr *ll_right = pexpr_or(expr_calculate_pexpr_y(b), expr_calculate_pexpr_m(b)); +    struct pexpr *topleft = pexpr_and(ll_left, ll_right); + +    return pexpr_and(topleft, topright); +} + +/* + * calculate, when expr of type AND will evaluate to mod or yes + * (A || A_m) && (B || B_m) + */ +struct pexpr * expr_calculate_pexpr_both_and(struct expr *a, struct expr *b) +{ +    struct pexpr *left = pexpr_or(expr_calculate_pexpr_y(a), expr_calculate_pexpr_m(a)); +    struct pexpr *right = pexpr_or(expr_calculate_pexpr_y(b), expr_calculate_pexpr_m(b)); +    return pexpr_and(left, right); +} + +/* + * calculate, when expr of type OR will evaluate to yes + * A || B + */ +struct pexpr * expr_calculate_pexpr_y_or(struct expr *a, struct expr *b) +{ +    return pexpr_or(expr_calculate_pexpr_y(a), expr_calculate_pexpr_y(b)); +} + +/* + * calculate, when expr of type OR will evaluate to mod + * (A_m || B_m) && !A && !B + */ +struct pexpr * expr_calculate_pexpr_m_or(struct expr *a, struct expr *b) +{ +    struct pexpr *topright = pexpr_not(expr_calculate_pexpr_y(b)); +    struct pexpr *lowerleft = pexpr_or(expr_calculate_pexpr_m(a), expr_calculate_pexpr_m(b)); +    struct pexpr *topleft = pexpr_and(lowerleft, pexpr_not(expr_calculate_pexpr_y(a))); + +    return pexpr_and(topleft, topright); +} + +/* + * calculate, when expr of type OR will evaluate to mod or yes + * (A_m || A || B_m || B) + */ +struct pexpr * expr_calculate_pexpr_both_or(struct expr *a, struct expr *b) +{ +    struct pexpr *left = pexpr_or(expr_calculate_pexpr_y(a), expr_calculate_pexpr_m(a)); +    struct pexpr *right = pexpr_or(expr_calculate_pexpr_y(b), expr_calculate_pexpr_m(b)); +    return pexpr_or(left, right); +} + +/* + * calculate, when expr of type NOT will evaluate to yes + * !(A || A_m) + */ +struct pexpr * expr_calculate_pexpr_y_not(struct expr * e) +{ +    return pexpr_not(pexpr_or(expr_calculate_pexpr_y(e), expr_calculate_pexpr_m(e))); +} + +/* + * calculate, when expr of type NOT will evaluate to mod + * A_m + */ +struct pexpr * expr_calculate_pexpr_m_not(struct expr * e) +{ +    return expr_calculate_pexpr_m(e); +} + +static struct pexpr * equiv_pexpr(struct pexpr *a, struct pexpr *b) +{ +    struct pexpr *yes = pexpr_and(a, b); +    struct pexpr *not = pexpr_and(pexpr_not(a), pexpr_not(b)); + +    return pexpr_or(yes, not); +} + +/* + * create the fexpr of a non-boolean symbol for a specific value + */ +struct fexpr * sym_create_nonbool_fexpr(struct symbol *sym, char *value) +{ + +    if (!strcmp(value, "")) { +        if (sym->type == S_STRING) +            return sym->nb_vals->head->next->elem; +        else +            return sym->nb_vals->head->elem; +    } + +    struct fexpr *e = sym_get_nonbool_fexpr(sym, value); + +    /* fexpr already exists */ +    if (e != NULL) +        return e; + +    char *s = value; +    if (sym->type == S_INT && !string_is_number(value)) { +        struct symbol *tmp = sym_find(value); + +        if (tmp != NULL) +            s = (char *) tmp->curr.val; +    } else if (sym->type == S_HEX && !string_is_hex(value)) { +        struct symbol *tmp = sym_find(value); + +        if (tmp != NULL) +            s = (char *) tmp->curr.val; +    } else if (sym->type == S_STRING) { +        struct symbol *tmp = sym_find(value); + +        if (tmp != NULL) +            s = (char *) tmp->curr.val; +    } + +    if (!strcmp(s, "")) { +        if (sym->type == S_STRING) +            return sym->nb_vals->head->next->elem; +        else +            return sym->nb_vals->head->elem; +    } + +    e = sym_get_nonbool_fexpr(sym, s); +    if (e != NULL) +        return e; + +    e = fexpr_create(sat_variable_nr++, FE_NONBOOL, sym->name); +    e->sym = sym; +    str_append(&e->name, "="); +    str_append(&e->name, s); +    e->nb_val = str_new(); +    str_append(&e->nb_val, s); + +    fexpr_list_add(sym->nb_vals, e); +    fexpr_add_to_satmap(e); + +    return e; +} + +/* + * return the fexpr of a non-boolean symbol for a specific value, NULL if non-existent + */ +struct fexpr * sym_get_nonbool_fexpr(struct symbol *sym, char *value) +{ +    struct fexpr_node *e; +    fexpr_list_for_each(e, sym->nb_vals) { +        if (strcmp(str_get(&e->elem->nb_val), value) == 0) +            return e->elem; +    } + +    return NULL; +} + +/* + * return the fexpr of a non-boolean symbol for a specific value, if it exists + * otherwise create it + */ +struct fexpr * sym_get_or_create_nonbool_fexpr(struct symbol *sym, char *value) +{ +    struct fexpr *e = sym_get_nonbool_fexpr(sym, value); + +    if (e != NULL) +        return e; +    else +        return sym_create_nonbool_fexpr(sym, value); +} + +/* + * calculate, when expr of type EQUAL will evaluate to yes + */ +struct pexpr * expr_calculate_pexpr_y_equals(struct expr *e) +{ +    /* comparing 2 tristate constants */ +    if (sym_is_tristate_constant(e->left.sym) && sym_is_tristate_constant(e->right.sym)) +        return e->left.sym == e->right.sym ? pexf(const_true) : pexf(const_false); + +    /* comparing 2 nonboolean constants */ +    if (sym_is_nonbool_constant(e->left.sym) && sym_is_nonbool_constant(e->right.sym)) +        return strcmp(e->left.sym->name, e->right.sym->name) == 0 ? pexf(const_true) : pexf(const_false); + +    /* comparing 2 boolean/tristate incl. yes/mod/no constants */ +    if (sym_is_bool_or_triconst(e->left.sym) && sym_is_bool_or_triconst(e->right.sym)) { +        struct pexpr *yes = equiv_pexpr(pexf(e->left.sym->fexpr_y), pexf(e->right.sym->fexpr_y)); +        struct pexpr *mod = equiv_pexpr(pexf(e->left.sym->fexpr_m), pexf(e->right.sym->fexpr_m)); + +        return pexpr_and(yes, mod); +    } + +    /* comparing nonboolean with a constant */ +    if (sym_is_nonboolean(e->left.sym) && sym_is_nonbool_constant(e->right.sym)) { +        return pexf(sym_get_or_create_nonbool_fexpr(e->left.sym, e->right.sym->name)); +    } +    if (sym_is_nonbool_constant(e->left.sym) && sym_is_nonboolean(e->right.sym)) +        return pexf(sym_get_or_create_nonbool_fexpr(e->right.sym, e->left.sym->name)); + +    /* comparing nonboolean with tristate constant, will never be true */ +    if (sym_is_nonboolean(e->left.sym) && sym_is_tristate_constant(e->right.sym)) +        return pexf(const_false); +    if (sym_is_tristate_constant(e->left.sym) && sym_is_nonboolean(e->right.sym)) +        return pexf(const_false); + +    /* comparing 2 nonboolean symbols */ +    if (sym_is_nonboolean(e->left.sym) && sym_is_nonboolean(e->right.sym)) { +        struct pexpr *c = pexf(const_false); +        struct fexpr_node *node1, *node2; +        struct fexpr *e1, *e2; +        for (node1 = e->left.sym->nb_vals->head->next; node1 != NULL; node1 = node1->next) { +            e1 = node1->elem; +            for (node2 = e->right.sym->nb_vals->head->next; node2 != NULL; node2 = node2->next) { +                e2 = node2->elem; +                if (!strcmp(str_get(&e1->nb_val), str_get(&e2->nb_val))) { +                    c = pexpr_or(c, pexpr_and(pexf(e1), pexf(e2))); +                    break; +                } +            } +        } +        return c; +    } + +    /* comparing boolean item with nonboolean constant, will never be true */ +    if (sym_is_tristate_constant(e->left.sym) && sym_is_nonbool_constant(e->right.sym)) +        return pexf(const_false); +    if (sym_is_nonbool_constant(e->left.sym) && sym_is_tristate_constant(e->right.sym)) +        return pexf(const_false); + +    /* comparing symbol of type unknown with tristate constant */ +    if (e->left.sym->type == S_UNKNOWN && sym_is_tristate_constant(e->right.sym)) +        return pexf(const_false); +    if (sym_is_tristate_constant(e->left.sym) && e->right.sym->type == S_UNKNOWN) +        return pexf(const_false); + +    /* any other comparison is not supported and should not be executed */ +    perror("Unsupported equality."); +    print_expr(":", e, 0); + +    return pexf(const_false); +} + +/* + * transform an UNEQUAL into a Not(EQUAL) + */ +struct pexpr * expr_calculate_pexpr_y_unequals(struct expr *e) +{ +    return pexpr_not(expr_calculate_pexpr_y_equals(e)); +} + +struct pexpr * expr_calculate_pexpr_y_comp(struct expr *e) +{ +    if (!e) +        return NULL; + +    switch (e->type) { +    case E_LTH: +    case E_LEQ: +    case E_GTH: +    case E_GEQ: +        /* compare non-Boolean symbol with constant */ +        if (sym_is_nonboolean(e->left.sym) && +            e->right.sym->type == S_UNKNOWN && +            string_is_number(e->right.sym->name) +        ) { +            return expr_eval_unequal_nonbool_const(e->left.sym, e->right.sym, e->type); +        } +        if (sym_is_nonboolean(e->right.sym) && +            e->left.sym->type == S_UNKNOWN && +            string_is_number(e->left.sym->name) +        ) { +            return expr_eval_unequal_nonbool_const(e->right.sym, e->left.sym, e->type); +        } + +        /* compare 2 Boolean symbols */ +        if (sym_is_boolean(e->left.sym) && sym_is_boolean(e->right.sym)) +            return expr_eval_unequal_bool(e->left.sym, e->right.sym, e->type); + +        return pexf(const_false); +    default: +        perror("Unhandled type - expr_calculate_pexpr_y_comp"); +        return NULL; +    } +} + +/* + * macro to create a pexpr of type AND + */ +struct pexpr * pexpr_and(struct pexpr *a, struct pexpr *b) +{ +    /* simplifications: +     * expr && False -> False +     * expr && True  -> expr +     * expr && expr  -> expr +     */ +    if (a->type == PE_SYMBOL && a->left.fexpr == const_false) +        return a; + +    if (b->type == PE_SYMBOL && b->left.fexpr == const_false) +        return b; + +    if (a->type == PE_SYMBOL && a->left.fexpr == const_true) +        return b; + +    if (b->type == PE_SYMBOL && b->left.fexpr == const_true) +        return a; + +    /* A && A -> A */ +    if (pexpr_eq(a,b)) +        return a; + +    /* (A && B) && C -> A && B if B == C */ +    if (a->type == PE_AND && pexpr_eq(a->right.pexpr, b)) +        return a; +    /* A && (B && C) -> B && C if A == B */ +    if (b->type == PE_AND && pexpr_eq(a, b->left.pexpr)) +        return b; + +    /* (A || B) && (C || D) -> A || (B && D) if A == C */ +    if (a->type == PE_OR && b->type == PE_OR && ( +        pexpr_eq(a->left.pexpr, b->left.pexpr) +    )) +        return pexpr_or(a->left.pexpr, +                pexpr_and(a->right.pexpr, b->right.pexpr)); +    /* (A || B) && (C || D) -> B || (A && C) if B == D */ +    if (a->type == PE_OR && b->type == PE_OR && ( +        pexpr_eq(a->right.pexpr, b->right.pexpr) +    )) +        return pexpr_or(a->right.pexpr, +                pexpr_and(a->left.pexpr, b->left.pexpr)); +    /* (A || B) && (C || D) -> A || (B && C) if A == D */ +    if (a->type == PE_OR && b->type == PE_OR && ( +        pexpr_eq(a->left.pexpr, b->right.pexpr) +    )) +        return pexpr_or(a->left.pexpr, +                pexpr_and(a->right.pexpr, b->left.pexpr)); +    /* (A || B) && (C || D) -> B || (A && D) if B == C */ +    if (a->type == PE_OR && b->type == PE_OR && ( +        pexpr_eq(a->right.pexpr, b->left.pexpr) +    )) +        return pexpr_or(a->right.pexpr, +                pexpr_and(a->left.pexpr, b->right.pexpr)); + +    struct pexpr *e = xcalloc(1, sizeof(*e)); +    e->type = PE_AND; +    e->left.pexpr = a; +    e->right.pexpr = b; + +    return e; +} + +/* + * macro to create a pexpr of type OR + */ +struct pexpr * pexpr_or(struct pexpr *a, struct pexpr *b) +{ +    /* simplifications: +     * expr || False -> expr +     * expr || True  -> True +     * expr || expr  -> expr +     */ +    if (a->type == PE_SYMBOL && a->left.fexpr == const_false) +        return b; + +    if (b->type == PE_SYMBOL && b->left.fexpr == const_false) +        return a; + +    if (a->type == PE_SYMBOL && a->left.fexpr == const_true) +        return a; + +    if (b->type == PE_SYMBOL && b->left.fexpr == const_true) +        return b; + +    /* A || A -> A */ +    if (pexpr_eq(a,b)) +        return a; + +    /* A || (B && C) -> A if (A == B || A == C) */ +    if (b->type == PE_AND && ( +        pexpr_eq(a, b->left.pexpr) || pexpr_eq(a, b->right.pexpr) +    )) +        return a; +    /* (A && B) || C -> C if (A == C || B == C) */ +    if (a->type == PE_AND && ( +        pexpr_eq(a->left.pexpr, b) || pexpr_eq(a->right.pexpr, b) +    )) +        return b; + +    /* -A || B -> True if A == B */ +    if (a->type == PE_NOT && pexpr_eq(a->left.pexpr, b)) +        return pexf(const_true); +    /* A || -B -> True if A == B */ +    if (b->type == PE_NOT && pexpr_eq(a, b->left.pexpr)) +        return pexf(const_true); + +    /* (A && B) || (C && D) -> A && (B || D) if (A == C) */ +    if (a->type == PE_AND && b->type == PE_AND && +        pexpr_eq(a->left.pexpr, b->left.pexpr) +    ) +        return pexpr_and(a->left.pexpr, +                 pexpr_or(a->right.pexpr, b->right.pexpr)); +    /* (A && B) || (C && D) -> B && (A || C) if (B == D) */ +    if (a->type == PE_AND && b->type == PE_AND && +        pexpr_eq(a->right.pexpr, b->right.pexpr) +    ) +        return pexpr_and(a->right.pexpr, +                 pexpr_or(a->left.pexpr, b->left.pexpr)); +    /* (A && B) || (C && D) -> A && (B || C) if (A == D) */ +    if (a->type == PE_AND && b->type == PE_AND && +        pexpr_eq(a->left.pexpr, b->right.pexpr) +    ) +        return pexpr_and(a->left.pexpr, +                 pexpr_or(a->right.pexpr, b->left.pexpr)); +    /* (A && B) || (C && D) -> B && (A || D) if (B == C) */ +    if (a->type == PE_AND && b->type == PE_AND && +        pexpr_eq(a->right.pexpr, b->left.pexpr) +    ) +        return pexpr_and(a->right.pexpr, +                 pexpr_or(a->left.pexpr, b->right.pexpr)); + +    /* (A && B) || (C || D) -> C || D if +     * A == C || A == D || B == C || B == D */ +    if (a->type == PE_AND && b->type == PE_OR && ( +        pexpr_eq(a->left.pexpr, b->left.pexpr) || +        pexpr_eq(a->left.pexpr, b->right.pexpr) || +        pexpr_eq(a->right.pexpr, b->left.pexpr) || +        pexpr_eq(a->right.pexpr, b->right.pexpr) +    )) +        return b; +    /* (C || D) || (A && B) -> C || D if +     * A == C || A == D || B == C || B == D */ +    if (a->type == PE_OR && b->type == PE_AND && ( +        pexpr_eq(a->left.pexpr, b->left.pexpr) || +        pexpr_eq(a->left.pexpr, b->right.pexpr) || +        pexpr_eq(a->right.pexpr, b->left.pexpr) || +        pexpr_eq(a->right.pexpr, b->right.pexpr) +    )) +        return a; + +    struct pexpr *e = xcalloc(1, sizeof(*e)); +    e->type = PE_OR; +    e->left.pexpr = a; +    e->right.pexpr = b; + +    return e; +} + +/* + * macro to create a pexpr of type NOT + */ +struct pexpr * pexpr_not(struct pexpr *a) +{ +    if (a->type == PE_SYMBOL && a->left.fexpr == const_false) +        return pexf(const_true); +    if (a->type == PE_SYMBOL && a->left.fexpr == const_true) +        return pexf(const_false); + +    /* eliminate double negation */ +    if (a->type == PE_NOT) +        return a->left.pexpr; + +    /* De Morgan */ +    if (a->type == PE_AND) { +        struct pexpr *e = xcalloc(1, sizeof(*e)); +        e->type = PE_OR; +        e->left.pexpr = pexpr_not(a->left.pexpr); +        e->right.pexpr = pexpr_not(a->right.pexpr); +        return e; +    } +    if (a->type == PE_OR) { +        struct pexpr *e = xcalloc(1, sizeof(*e)); +        e->type = PE_AND; +        e->left.pexpr = pexpr_not(a->left.pexpr); +        e->right.pexpr = pexpr_not(a->right.pexpr); +        return e; +    } + +    struct pexpr *e = xcalloc(1, sizeof(*e)); +    e->type = PE_NOT; +    e->left.pexpr = a; +    return e; +} + +/* + * macro to construct a pexpr for "A implies B" + */ +struct pexpr * pexpr_implies(struct pexpr *a, struct pexpr *b) +{ +    /* A => B -> True if A == B */ +    if (pexpr_eq(a, b)) +        return pexf(const_true); + +    /* (A => B && C) -> (A => C) if A == B */ +    if (b->type == PE_AND && pexpr_eq(a, b->left.pexpr)) +        return pexpr_implies(a, b->right.pexpr); +    /* (A => B && C) -> (A => B) if A == C */ +    if (b->type == PE_AND && pexpr_eq(a, b->right.pexpr)) +        return pexpr_implies(a, b->left.pexpr); + +    /* (A => B || C) -> True if (A == B || A == C) */ +    if (b->type == PE_OR && ( +        pexpr_eq(a, b->left.pexpr) || pexpr_eq(a, b->right.pexpr) +    )) +        return pexf(const_true); + +    /* (A && B => C) -> True if (A == C || B == C) */ +    if (a->type == PE_AND && ( +        pexpr_eq(a->left.pexpr, b) || pexpr_eq(a->right.pexpr, b) +    )) +        return pexf(const_true); + +    return pexpr_or(pexpr_not(a), b); +} + +/* + * check whether a pexpr is in CNF + */ +bool pexpr_is_cnf(struct pexpr *e) +{ +    if (!e) +        return false; + +    switch (e->type) { +    case PE_SYMBOL: +        return true; +    case PE_AND: +        return false; +    case PE_OR: +        return pexpr_is_cnf(e->left.pexpr) && pexpr_is_cnf(e->right.pexpr); +    case PE_NOT: +        return e->left.pexpr->type == PE_SYMBOL; +    } + +    return false; +} + +/* + * check whether a pexpr is in NNF + */ +bool pexpr_is_nnf(struct pexpr *e) +{ +    if (!e) +        return false; + +    switch (e->type) { +    case PE_SYMBOL: +        return true; +    case PE_AND: +    case PE_OR: +        return pexpr_is_nnf(e->left.pexpr) && pexpr_is_nnf(e->right.pexpr); +    case PE_NOT: +        return e->left.pexpr->type == PE_SYMBOL; +    } + +    return false; +} + +/* + * return fexpr_both for a symbol + */ +struct pexpr * sym_get_fexpr_both(struct symbol *sym) +{ +    return sym->type == S_TRISTATE ? pexpr_or(pexf(sym->fexpr_m), pexf(sym->fexpr_y)) : pexf(sym->fexpr_y); +} + +/* + * return fexpr_sel_both for a symbol + */ +struct pexpr * sym_get_fexpr_sel_both(struct symbol *sym) +{ +    if (!sym->rev_dep.expr) +        return pexf(const_false); + +    return sym->type == S_TRISTATE ? pexpr_or(pexf(sym->fexpr_sel_m), pexf(sym->fexpr_sel_y)) : pexf(sym->fexpr_sel_y); +} + +/* + * check, if the fexpr is a symbol, a True/False-constant, a literal symbolizing a non-boolean or a choice symbol + */ +bool fexpr_is_symbol(struct fexpr *e) +{ +    return e->type == FE_SYMBOL || e->type == FE_FALSE || e->type == FE_TRUE || e->type == FE_NONBOOL || e->type == FE_CHOICE || e->type == FE_SELECT || e->type == FE_NPC; +} + +/* + * check whether a pexpr is a symbol or a negated symbol + */ +bool pexpr_is_symbol(struct pexpr *e) +{ +    return e->type == PE_SYMBOL || (e->type == PE_NOT && e->left.pexpr->type == PE_SYMBOL); +} + +/* + * check whether the fexpr is a constant (true/false) + */ +bool fexpr_is_constant(struct fexpr *e) +{ +    return e == const_true || e == const_false; +} + +/* + * add a fexpr to the satmap + */ +void fexpr_add_to_satmap(struct fexpr *e) +{ +    if (e->satval >= satmap_size) { +        satmap = xrealloc(satmap, satmap_size * 2 * sizeof(*satmap)); +        satmap_size *= 2; +    } + +    satmap[e->satval] = *e; +} + +/* + * print a fexpr + */ +void fexpr_print(char *tag, struct fexpr *e) +{ +    if (!e) +        return; + +    printf("%s: %s\n", tag, str_get(&e->name)); +} + +/* + * write an fexpr into a string (format needed for testing) + */ +void fexpr_as_char(struct fexpr *e, struct gstr *s) +{ +    if (!e) +        return; + +    switch (e->type) { +    case FE_SYMBOL: +    case FE_CHOICE: +    case FE_SELECT: +    case FE_NPC: +    case FE_NONBOOL: +        str_append(s, "definedEx("); +        str_append(s, str_get(&e->name)); +        str_append(s, ")"); +        return; +    case FE_FALSE: +        str_append(s, "0"); +        return; +    case FE_TRUE: +        str_append(s, "1"); +        return; +    default: +        return; +    } +} + +/* + * write a pexpr into a string + */ +void pexpr_as_char(struct pexpr *e, struct gstr *s, int parent) +{ +    if (!e) +        return; + +    switch (e->type) { +    case PE_SYMBOL: +        if (e->left.fexpr == const_false) { +            str_append(s, "0"); +            return; +        } +        if (e->left.fexpr == const_true) { +            str_append(s, "1"); +            return; +        } +        str_append(s, "definedEx("); +        str_append(s, str_get(&e->left.fexpr->name)); +        str_append(s, ")"); +        return; +    case PE_AND: +        /* need this hack for the FeatureExpr parser */ +        if (parent != PE_AND) +            str_append(s, "("); +        pexpr_as_char(e->left.pexpr, s, PE_AND); +        str_append(s, " && "); +        pexpr_as_char(e->right.pexpr, s, PE_AND); +        if (parent != PE_AND) +            str_append(s, ")"); +        return; +    case PE_OR: +        if (parent != PE_OR) +            str_append(s, "("); +        pexpr_as_char(e->left.pexpr, s, PE_OR); +        str_append(s, " || "); +        pexpr_as_char(e->right.pexpr, s, PE_OR); +        if (parent != PE_OR) +            str_append(s, ")"); +        return; +    case PE_NOT: +        str_append(s, "!"); +        pexpr_as_char(e->left.pexpr, s, PE_NOT); +        return; +    } +} + +/* + * write a pexpr into a string + */ +void pexpr_as_char_short(struct pexpr *e, struct gstr *s, int parent) +{ +    if (!e) +        return; + +    switch (e->type) { +    case PE_SYMBOL: +        str_append(s, str_get(&e->left.fexpr->name)); +        return; +    case PE_AND: +        /* need this hack for the FeatureExpr parser */ +        if (parent != PE_AND) +            str_append(s, "("); +        pexpr_as_char_short(e->left.pexpr, s, PE_AND); +        str_append(s, " && "); +        pexpr_as_char_short(e->right.pexpr, s, PE_AND); +        if (parent != PE_AND) +            str_append(s, ")"); +        return; +    case PE_OR: +        if (parent != PE_OR) +            str_append(s, "("); +        pexpr_as_char_short(e->left.pexpr, s, PE_OR); +        str_append(s, " || "); +        pexpr_as_char_short(e->right.pexpr, s, PE_OR); +        if (parent != PE_OR) +            str_append(s, ")"); +        return; +    case PE_NOT: +        str_append(s, "!"); +        pexpr_as_char_short(e->left.pexpr, s, PE_NOT); +        return; +    } +} + +/* + * check whether a pexpr contains a specific fexpr + */ +bool pexpr_contains_fexpr(struct pexpr *e, struct fexpr *fe) +{ +    if (!e) +        return false; + +    switch (e->type) { +    case PE_SYMBOL: +        return e->left.fexpr->satval == fe->satval; +    case PE_AND: +    case PE_OR: +        return pexpr_contains_fexpr(e->left.pexpr, fe) || +            pexpr_contains_fexpr(e->right.pexpr, fe); +    case PE_NOT: +        return e->left.pexpr->left.fexpr->satval == fe->satval; +    } + +    return false; +} + +/* + * init list of fexpr + */ +struct fexpr_list * fexpr_list_init() +{ +    struct fexpr_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of fexpr_list + */ +struct fexl_list * fexl_list_init() +{ +    struct fexl_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of pexpr + */ +struct pexpr_list * pexpr_list_init() +{ +    struct pexpr_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of symbol_fix + */ +struct sfix_list * sfix_list_init(void) +{ +    struct sfix_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of symbol_fix + */ +struct sfl_list * sfl_list_init(void) +{ +    struct sfl_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of symbol_dvalue + */ +struct sdv_list * sdv_list_init(void) +{ +    struct sdv_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of symbols + */ +struct sym_list * sym_list_init(void) +{ +    struct sym_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of default_maps + */ +struct defm_list * defm_list_init(void) +{ +    struct defm_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * init list of properties + */ +struct prop_list *prop_list_init(void) +{ +    struct prop_list *list = xcalloc(1, sizeof(*list)); +    list->head = NULL; +    list->tail = NULL; +    list->size = 0; + +    return list; +} + +/* + * add element to tail of a fexpr_list + */ +void fexpr_list_add(struct fexpr_list *list, struct fexpr *fe) +{ +    struct fexpr_node *node = xcalloc(1, sizeof(*node)); +    node->elem = fe; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a fexl_list + */ +void fexl_list_add(struct fexl_list *list, struct fexpr_list *elem) +{ +    struct fexl_node *node = xcalloc(1, sizeof(*node)); +    node->elem = elem; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a pexpr_list + */ +void pexpr_list_add(struct pexpr_list *list, struct pexpr *e) +{ +    struct pexpr_node *node = xcalloc(1, sizeof(*node)); +    node->elem = e; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a sfix_list + */ +void sfix_list_add(struct sfix_list *list, struct symbol_fix *fix) +{ +    struct sfix_node *node = xcalloc(1, sizeof(*node)); +    node->elem = fix; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a sfl_list + */ +void sfl_list_add(struct sfl_list *list, struct sfix_list *elem) +{ +    struct sfl_node *node = xcalloc(1, sizeof(*node)); +    node->elem = elem; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a sdv_list + */ +void sdv_list_add(struct sdv_list *list, struct symbol_dvalue *sdv) +{ +    struct sdv_node *node = xcalloc(1, sizeof(*node)); +    node->elem = sdv; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a sym_list + */ +void sym_list_add(struct sym_list *list, struct symbol *sym) +{ +    struct sym_node *node = xcalloc(1, sizeof(*node)); +    node->elem = sym; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a defm_list + */ +void defm_list_add(struct defm_list *list, struct default_map *map) +{ +    struct defm_node *node = xcalloc(1, sizeof(*node)); +    node->elem = map; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * add element to tail of a prop_list + */ +void prop_list_add(struct prop_list *list, struct property *prop) +{ +    struct prop_node *node = xcalloc(1, sizeof(*node)); +    node->elem = prop; + +    if (list->size == 0) { +        list->head = node; +        list->tail = node; +    } else { +        node->prev = list->tail; +        list->tail = node; +        node->prev->next = node; +    } + +    list->size++; +} + +/* + * delete an element from a fexpr_list + */ +void fexpr_list_delete(struct fexpr_list *list, struct fexpr_node *node) +{ +    if (list->size == 0 || node == NULL) +        return; + +    if (node == list->head) +        list->head = node->next; +    else +        node->prev->next = node->next; + +    if (node == list->tail) +        list->tail = node->prev; +    else +        node->next->prev = node->prev; + +    list->size--; +    free(node); +} + +/* + * delete an element from a fexpr_list + */ +void sfix_list_delete(struct sfix_list *list, struct sfix_node *node) +{ +    if (list->size == 0 || node == NULL) +        return; + +    if (node == list->head) +        list->head = node->next; +    else +        node->prev->next = node->next; + +    if (node == list->tail) +        list->tail = node->prev; +    else +        node->next->prev = node->prev; + +    list->size--; +    free(node); +} + +/* + * delete an element from a fexpr_list + */ +void pexpr_list_delete(struct pexpr_list *list, struct pexpr_node *node) +{ +    if (list->size == 0 || node == NULL) +        return; + +    if (node == list->head) +        list->head = node->next; +    else +        node->prev->next = node->next; + +    if (node == list->tail) +        list->tail = node->prev; +    else +        node->next->prev = node->prev; + +    list->size--; +    free(node); +} + +/* + * delete an element from a fexl_list + */ +void fexl_list_delete(struct fexl_list *list, struct fexl_node *node) +{ +    if (list->size == 0 || node == NULL) +        return; + +    if (node == list->head) +        list->head = node->next; +    else +        node->prev->next = node->next; + +    if (node == list->tail) +        list->tail = node->prev; +    else +        node->next->prev = node->prev; + +    list->size--; +    free(node); +} + +/* + * delete the first occurence of elem in an fexl_list + */ +void fexl_list_delete_elem(struct fexl_list *list, struct fexpr_list *elem) +{ +    struct fexl_node *node, *to_delete = NULL; +    fexl_list_for_each(node, list) { +        if (node->elem == elem) { +            to_delete = node; +            break; +        } +    } + +    if (to_delete != NULL) +        fexl_list_delete(list, to_delete); +} + +/* + * make a shallow copy of a fexpr_list + */ +struct fexpr_list * fexpr_list_copy(struct fexpr_list *list) +{ +    struct fexpr_list *ret = fexpr_list_init(); +    struct fexpr_node *node; +    fexpr_list_for_each(node, list) +        fexpr_list_add(ret, node->elem); + +    return ret; +} + +/* + * make a shallow copy of a fexl_list + */ +struct fexl_list * fexl_list_copy(struct fexl_list *list) +{ +    struct fexl_list *ret = fexl_list_init(); +    struct fexl_node *node; +    fexl_list_for_each(node, list) +        fexl_list_add(ret, node->elem); + +    return ret; +} + +/* + * make a shallow copy of a sdv_list + */ +struct sdv_list * sdv_list_copy(struct sdv_list *list) +{ +    struct sdv_list *ret = sdv_list_init(); +    struct sdv_node *node; +    sdv_list_for_each(node, list) +        sdv_list_add(ret, node->elem); + + +    return ret; +} + +/* + * make a shallow copy of a sfix_list + */ +struct sfix_list * sfix_list_copy(struct sfix_list *list) +{ +    struct sfix_list *ret = sfix_list_init(); +    struct sfix_node *node; +    sfix_list_for_each(node, list) +        sfix_list_add(ret, node->elem); + +    return ret; +} + +/* + * print a fexpr_list + */ +void fexpr_list_print(char *title, struct fexpr_list *list) +{ +    struct fexpr_node *node; +    printf("%s: [", title); + +    fexpr_list_for_each(node, list) { +        printf("%s", str_get(&node->elem->name)); +        if (node->next != NULL) +            printf(", "); +    } + +    printf("]\n"); +} + +/* + * print a fexl_list + */ +void fexl_list_print(char *title, struct fexl_list *list) +{ +    struct fexl_node *node; +    printf("%s:\n", title); + +    fexl_list_for_each(node, list) +        fexpr_list_print(":", node->elem); +} + +/* + * print a pexpr_list + */ +void pexpr_list_print(char *title, struct pexpr_list *list) +{ +    struct pexpr_node *node; +    printf("%s: [", title); + +    pexpr_list_for_each(node, list) { +        pexpr_print_util(node->elem, -1); +        if (node->next != NULL) +            printf(", "); +    } + +    printf("]\n"); +} + +/* + * free an fexpr_list + */ +void fexpr_list_free(struct fexpr_list *list) +{ +    struct fexpr_node *node = list->head, *tmp; + +    while (node != NULL) { +        tmp = node->next; +        free(node); +        node = tmp; +    } + +    free(list); +} + +/* + * free an fexl_list + */ +void fexl_list_free(struct fexl_list *list){ +    struct fexl_node *node = list->head, *tmp; + +    while (node != NULL) { +        tmp = node->next; +        free(node); +        node = tmp; +    } + +    free(list); +} + +/* + * free a sdv_list + */ +void sdv_list_free(struct sdv_list *list) +{ +    struct sdv_node *node = list->head, *tmp; + +    while (node != NULL) { +        tmp = node->next; +        free(node); +        node = tmp; +    } + +    free(list); +} + +/* + * simplify a pexpr in-place + *     pexpr && False -> False + *     pexpr && True  -> pexpr + *     pexpr || False -> pexpr + *     pexpr || True  -> True + */ +static struct pexpr * pexpr_eliminate_yn(struct pexpr *e) +{ +    struct pexpr *tmp; + +    if (e) switch (e->type) { +    case PE_AND: +        e->left.pexpr = pexpr_eliminate_yn(e->left.pexpr); +        e->right.pexpr = pexpr_eliminate_yn(e->right.pexpr); +        if (e->left.pexpr->type == PE_SYMBOL) { +            if (e->left.pexpr->left.fexpr == const_false) { +                pexpr_free(e->left.pexpr); +                pexpr_free(e->right.pexpr); +                e->type = PE_SYMBOL; +                e->left.fexpr = const_false; +                e->right.pexpr = NULL; +                return e; +            } else if (e->left.pexpr->left.fexpr == const_true) { +                free(e->left.pexpr); +                tmp = e->right.pexpr; +                *e = *(e->right.pexpr); +                free(tmp); +                return e; +            } +        } +        if (e->right.pexpr->type == PE_SYMBOL) { +            if (e->right.pexpr->left.fexpr == const_false) { +                pexpr_free(e->left.pexpr); +                pexpr_free(e->right.pexpr); +                e->type = PE_SYMBOL; +                e->left.fexpr = const_false; +                e->right.fexpr = NULL; +                return e; +            } else if (e->right.pexpr->left.fexpr == const_true) { +                free(e->right.pexpr); +                tmp = e->left.pexpr; +                *e = *(e->left.pexpr); +                free(tmp); +                return e; +            } +        } +        break; +    case PE_OR: +        e->left.pexpr = pexpr_eliminate_yn(e->left.pexpr); +        e->right.pexpr = pexpr_eliminate_yn(e->right.pexpr); +        if (e->left.pexpr->type == PE_SYMBOL) { +            if (e->left.pexpr->left.fexpr == const_false) { +                free(e->left.pexpr); +                tmp = e->right.pexpr; +                *e = *(e->right.pexpr); +                free(tmp); +                return e; +            } else if (e->left.pexpr->left.fexpr == const_true) { +                pexpr_free(e->left.pexpr); +                pexpr_free(e->right.pexpr); +                e->type = PE_SYMBOL; +                e->left.fexpr = const_true; +                e->right.pexpr = NULL; +            } +        } +        if (e->right.pexpr->type == PE_SYMBOL) { +            if (e->right.pexpr->left.fexpr == const_false) { +                free(e->right.pexpr); +                tmp = e->left.pexpr; +                *e = *(e->left.pexpr); +                free(tmp); +                return e; +            } else if (e->right.pexpr->left.fexpr == const_true) { +                pexpr_free(e->left.pexpr); +                pexpr_free(e->right.pexpr); +                e->type = PE_SYMBOL; +                e->left.fexpr = const_true; +                e->right.pexpr = NULL; +                return e; +            } +        } +    default: +        ; +    } + +    return e; +} + +/* + * copy a pexpr + */ +struct pexpr * pexpr_copy(const struct pexpr *org) +{ +    struct pexpr *e; + +    if (!org) +        return NULL; + +    e = xmalloc(sizeof(*org)); +    memcpy(e, org, sizeof(*org)); +    switch (org->type) { +    case PE_SYMBOL: +        e->left = org->left; +        break; +    case PE_AND: +    case PE_OR: +        e->left.pexpr = pexpr_copy(org->left.pexpr); +        e->right.pexpr = pexpr_copy(org->right.pexpr); +        break; +    case PE_NOT: +        e->left.pexpr = pexpr_copy(org->left.pexpr); +        break; +    } + +    return e; +} + +/* + * free a pexpr + */ +void pexpr_free(struct pexpr *e) +{ +    if (!e) +        return; + +    switch (e->type) { +    case PE_SYMBOL: +        break; +    case PE_AND: +    case PE_OR: +        pexpr_free(e->left.pexpr); +        pexpr_free(e->right.pexpr); +        break; +    case PE_NOT: +        pexpr_free(e->left.pexpr); +        break; +    } + +    free(e); +} + +#define e1 (*ep1) +#define e2 (*ep2) +/* + * pexpr_eliminate_eq() helper + */ +static void __pexpr_eliminate_eq(enum pexpr_type type, struct pexpr **ep1, struct pexpr **ep2) +{ +    /* recurse down to the leaves */ +    if (e1->type == type) { +        __pexpr_eliminate_eq(type, &e1->left.pexpr, &e2); +        __pexpr_eliminate_eq(type, &e1->right.pexpr, &e2); +        return; +    } +    if (e2->type == type) { +        __pexpr_eliminate_eq(type, &e1, &e2->left.pexpr); +        __pexpr_eliminate_eq(type, &e1, &e2->right.pexpr); +        return; +    } + +    /* e1 and e2 are leaves. Compare them. */ +    if (e1->type == PE_SYMBOL && e2->type == PE_SYMBOL && +        e1->left.fexpr->satval == e2->left.fexpr->satval && +        (e1->left.fexpr == const_true || e2->left.fexpr == const_false)) +        return; +    if (!pexpr_eq(e1, e2)) +        return; + +    /* e1 and e2 are equal leaves. Prepare them for elimination. */ +    trans_count++; +    pexpr_free(e1); +    pexpr_free(e2); +    switch (type) { +    case PE_AND: +        e1 = pexf(const_true); +        e2 = pexf(const_true); +        break; +    case PE_OR: +        e1 = pexf(const_false); +        e2 = pexf(const_false); +        break; +    default: +        ; +    } +} + +/* + * rewrite pexpr ep1 and ep2 to remove operands common to both + */ +static void pexpr_eliminate_eq(struct pexpr **ep1, struct pexpr **ep2) +{ +    if (!e1 || !e2) +        return; + +    switch (e1->type) { +    case PE_AND: +    case PE_OR: +        __pexpr_eliminate_eq(e1->type, ep1, ep2); +    default: +        ; +    } +    if (e1->type != e2->type) switch (e2->type) { +    case PE_AND: +    case PE_OR: +        __pexpr_eliminate_eq(e2->type, ep1, ep2); +    default: +        ; +    } +    e1 = pexpr_eliminate_yn(e1); +    e2 = pexpr_eliminate_yn(e2); +} +#undef e1 +#undef e2 + +/* + * check whether 2 pexpr are equal + */ +bool pexpr_eq(struct pexpr *e1, struct pexpr *e2) +{ +    bool res; +    int old_count; + +    if (!e1 || !e2) +        return false; + +    if (e1->type != e2->type) +        return false; + +    switch (e1->type) { +    case PE_SYMBOL: +        return e1->left.fexpr->satval == e2->left.fexpr->satval; +    case PE_AND: +    case PE_OR: +        e1 = pexpr_copy(e1); +        e2 = pexpr_copy(e2); +        old_count = trans_count; +        pexpr_eliminate_eq(&e1, &e2); +        res = (e1->type == PE_SYMBOL && e2->type == PE_SYMBOL && +            e1->left.fexpr->satval == e2->left.fexpr->satval); +        pexpr_free(e1); +        pexpr_free(e2); +        trans_count = old_count; +        return res; +    case PE_NOT: +        return pexpr_eq(e1->left.pexpr, e2->left.pexpr); +    } + +    return false; +} + +/* + * print a pexpr + */ +static void pexpr_print_util(struct pexpr *e, int prevtoken) +{ +    if (!e) +        return; + +    switch (e->type) { +    case PE_SYMBOL: +        printf("%s", str_get(&e->left.fexpr->name)); +        break; +    case PE_AND: +        if (prevtoken != PE_AND && prevtoken != -1) +            printf("("); +        pexpr_print_util(e->left.pexpr, PE_AND); +        printf(" && "); +        pexpr_print_util(e->right.pexpr, PE_AND); +        if (prevtoken != PE_AND && prevtoken != -1) +            printf(")"); +        break; +    case PE_OR: +        if (prevtoken != PE_OR && prevtoken != -1) +            printf("("); +        pexpr_print_util(e->left.pexpr, PE_OR); +        printf(" || "); +        pexpr_print_util(e->right.pexpr, PE_OR); +        if (prevtoken != PE_OR && prevtoken != -1) +            printf(")"); +        break; +    case PE_NOT: +        printf("!"); +        pexpr_print_util(e->left.pexpr, PE_NOT); +        break; +    } +} +void pexpr_print(char *tag, struct pexpr *e, int prevtoken) +{ +    printf("%s: ", tag); +    pexpr_print_util(e, prevtoken); +    printf("\n"); +} + +/* + * convert a fexpr to a pexpr + */ +struct pexpr * pexf(struct fexpr *fe) +{ +    struct pexpr *pe = xcalloc(1, sizeof(*pe)); +    pe->type = PE_SYMBOL; +    pe->left.fexpr = fe; +    return pe; +} + +static struct pexpr * pexpr_join_or(struct pexpr *e1, struct pexpr *e2) +{ +    if (pexpr_eq(e1, e2)) +        return pexpr_copy(e1); +    else +        return NULL; +} + +static struct pexpr * pexpr_join_and(struct pexpr *e1, struct pexpr *e2) +{ +    if (pexpr_eq(e1, e2)) +        return pexpr_copy(e1); +    else +        return NULL; +} + +/* + * pexpr_eliminate_dups() helper. + */ +static void pexpr_eliminate_dups1(enum pexpr_type type, struct pexpr **ep1, struct pexpr **ep2) +{ +#define e1 (*ep1) +#define e2 (*ep2) + +    struct pexpr *tmp; + +    /* recurse down to leaves */ +    if (e1->type == type) { +        pexpr_eliminate_dups1(type, &e1->left.pexpr, &e2); +        pexpr_eliminate_dups1(type, &e1->right.pexpr, &e2); +        return; +    } +    if (e2->type == type) { +        pexpr_eliminate_dups1(type, &e1, &e2->left.pexpr); +        pexpr_eliminate_dups1(type, &e1, &e2->right.pexpr); +        return; +    } + +    /* e1 and e2 are leaves. Compare them. */ + +    if (e1 == e2) +        return; + +    switch (e1->type) { +    case PE_AND: +    case PE_OR: +        pexpr_eliminate_dups1(e1->type, &e1, &e1); +    default: +        ; +    } + +    switch (type) { +    case PE_AND: +        tmp = pexpr_join_and(e1, e2); +        if (tmp) { +            pexpr_free(e1); +            pexpr_free(e2); +            e1 = pexf(const_true); +            e2 = tmp; +            trans_count++; +        } +        break; +    case PE_OR: +        tmp = pexpr_join_or(e1, e2); +        if (tmp) { +            pexpr_free(e1); +            pexpr_free(e2); +            e1 = pexf(const_false); +            e2 = tmp; +            trans_count++; +        } +        break; +    default: +        ; +    } + +#undef e1 +#undef e2 +} + +/* + * eliminate duplicate and redundant operands + */ +struct pexpr * pexpr_eliminate_dups(struct pexpr *e) +{ +    if (!e) +        return e; + +    int oldcount = trans_count; +    while (true) { +        trans_count = 0; +        switch (e->type) { +        case PE_AND: +        case PE_OR: +            pexpr_eliminate_dups1(e->type, &e, &e); +        default: +            ; +        } +        if (!trans_count) +            /* no simplification done in this pass. We're done. */ +            break; +        e = pexpr_eliminate_yn(e); +    } +    trans_count = oldcount; +    return e; +} diff --git a/scripts/kconfig/cf_expr.h b/scripts/kconfig/cf_expr.h new file mode 100644 index 000000000000..cc612866fed4 --- /dev/null +++ b/scripts/kconfig/cf_expr.h @@ -0,0 +1,237 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * Copyright (C) 2021 Patrick Franz + */ + +#ifndef CF_EXPR_H +#define CF_EXPR_H + +#define fexpr_list_for_each(node, list) \ +    for (node = list->head; node != NULL; node = node->next) + +#define fexl_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define pexpr_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define sdv_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define sfix_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define sfl_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define sym_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define defm_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +#define prop_list_for_each(node, list) \ +    fexpr_list_for_each(node, list) + +/* create a fexpr */ +struct fexpr * fexpr_create(int satval, enum fexpr_type type, char *name); + +/* create the fexpr for a symbol */ +void sym_create_fexpr (struct symbol *sym); + +struct pexpr * expr_calculate_pexpr_both(struct expr *e); +struct pexpr * expr_calculate_pexpr_y(struct expr *e); +struct pexpr * expr_calculate_pexpr_m(struct expr *e); +struct pexpr * expr_calculate_pexpr_y_and(struct expr *a, struct expr *b); +struct pexpr * expr_calculate_pexpr_m_and(struct expr *a, struct expr *b); +struct pexpr * expr_calculate_pexpr_both_and(struct expr *a, struct expr *b); +struct pexpr * expr_calculate_pexpr_y_or(struct expr *a, struct expr *b); +struct pexpr * expr_calculate_pexpr_m_or(struct expr *a, struct expr *b); +struct pexpr * expr_calculate_pexpr_both_or(struct expr *a, struct expr *b); +struct pexpr * expr_calculate_pexpr_y_not(struct expr * e); +struct pexpr * expr_calculate_pexpr_m_not(struct expr *e); +struct pexpr * expr_calculate_pexpr_y_equals(struct expr *e); +struct pexpr * expr_calculate_pexpr_y_unequals(struct expr *e); +struct pexpr * expr_calculate_pexpr_y_comp(struct expr *e); + +/* macro to create a pexpr of type AND */ +struct pexpr * pexpr_and(struct pexpr *a, struct pexpr *b); + +/* macro to create a pexpr of type OR */ +struct pexpr * pexpr_or(struct pexpr *a, struct pexpr *b); + +/* macro to create a pexpr of type NOT */ +struct pexpr * pexpr_not(struct pexpr *a); + +/* check whether a pexpr is in CNF */ +bool pexpr_is_cnf(struct pexpr *e); + +/* check whether a pexpr is in NNF */ +bool pexpr_is_nnf(struct pexpr *e); + +/* return fexpr_both for a symbol */ +struct pexpr * sym_get_fexpr_both(struct symbol *sym); + +/* return fexpr_sel_both for a symbol */ +struct pexpr * sym_get_fexpr_sel_both(struct symbol *sym); + +/* create the fexpr of a non-boolean symbol for a specific value */ +struct fexpr * sym_create_nonbool_fexpr(struct symbol *sym, char *value); + +/* return the fexpr of a non-boolean symbol for a specific value, NULL if non-existent */ +struct fexpr * sym_get_nonbool_fexpr(struct symbol *sym, char *value); + +/* + * return the fexpr of a non-boolean symbol for a specific value, if it exists + * otherwise create it + */ +struct fexpr * sym_get_or_create_nonbool_fexpr(struct symbol *sym, char *value); + +/* macro to construct a pexpr for "A implies B" */ +struct pexpr * pexpr_implies(struct pexpr *a, struct pexpr *b); + +/* check, if the fexpr is a symbol, a True/False-constant, a literal symbolising a non-boolean or a choice symbol */ +bool fexpr_is_symbol(struct fexpr *e); + +/* check whether a pexpr is a symbol or a negated symbol */ +bool pexpr_is_symbol(struct pexpr *e); + +/* check whether the fexpr is a constant (true/false) */ +bool fexpr_is_constant(struct fexpr *e); + +/* add a fexpr to the satmap */ +void fexpr_add_to_satmap(struct fexpr *e); + +/* print an fexpr */ +void fexpr_print(char *tag, struct fexpr *e); + +/* write an fexpr into a string (format needed for testing) */ +void fexpr_as_char(struct fexpr *e, struct gstr *s); + +/* write pn pexpr into a string */ +void pexpr_as_char_short(struct pexpr *e, struct gstr *s, int parent); + +/* write an fexpr into a string (format needed for testing) */ +void pexpr_as_char(struct pexpr *e, struct gstr *s, int parent); + +/* check whether a pexpr contains a specific fexpr */ +bool pexpr_contains_fexpr(struct pexpr *e, struct fexpr *fe); + +/* init list of fexpr */ +struct fexpr_list * fexpr_list_init(void); + +/* init list of fexpr_list */ +struct fexl_list * fexl_list_init(void); + +/* init list of pexpr */ +struct pexpr_list * pexpr_list_init(void); + +/* init list of symbol_fix */ +struct sfix_list * sfix_list_init(void); + +/* init list of sfix_list */ +struct sfl_list * sfl_list_init(void); + +/* init list of symbol_dvalue */ +struct sdv_list * sdv_list_init(void); + +/* init list of symbols */ +struct sym_list * sym_list_init(void); + +/* init list of default_maps */ +struct defm_list * defm_list_init(void); + +/* init list of properties */ +struct prop_list *prop_list_init(void); + +/* add element to tail of a fexpr_list */ +void fexpr_list_add(struct fexpr_list *list, struct fexpr *fe); + +/* add element to tail of a fexl_list */ +void fexl_list_add(struct fexl_list *list, struct fexpr_list *elem); + +/* add element to tail of a pexpr_list */ +void pexpr_list_add(struct pexpr_list *list, struct pexpr *e); + +/* add element to tail of a sfix_list */ +void sfix_list_add(struct sfix_list *list, struct symbol_fix *fix); + +/* add element to tail of a sfl_list */ +void sfl_list_add(struct sfl_list *list, struct sfix_list *elem); + +/* add element to tail of a sdv_list */ +void sdv_list_add(struct sdv_list *list, struct symbol_dvalue *sdv); + +/* add element to tail of a sym_list */ +void sym_list_add(struct sym_list *list, struct symbol *sym); + +/* add element to tail of a defm_list */ +void defm_list_add(struct defm_list *list, struct default_map *map); + +/* add element to tail of a prop_list */ +void prop_list_add(struct prop_list *list, struct property *prop); + +/* delete an element from a fexpr_list */ +void fexpr_list_delete(struct fexpr_list *list, struct fexpr_node *node); + +/* delete an element from a fexpr_list */ +void fexl_list_delete(struct fexl_list *list, struct fexl_node *node); + +/* delete the first occurence of elem in an fexl_list */ +void fexl_list_delete_elem(struct fexl_list *list, struct fexpr_list *elem); + +/* delete an element from a pexpr_list */ +void pexpr_list_delete(struct pexpr_list *list, struct pexpr_node *node); + +/* delete an element from a sfix_list */ +void sfix_list_delete(struct sfix_list *list, struct sfix_node *node); + +/* make a shallow copy of a fexpr_list */ +struct fexpr_list * fexpr_list_copy(struct fexpr_list *list); + +/* make a shallow copy of a fexpr_list */ +struct fexl_list * fexl_list_copy(struct fexl_list *list); + +/* make a shallow copy of a sdv_list */ +struct sdv_list * sdv_list_copy(struct sdv_list *list); + +/* make a shallow copy of a sfix_list */ +struct sfix_list * sfix_list_copy(struct sfix_list *list); + +/* print a fexpr_list */ +void fexpr_list_print(char *title, struct fexpr_list *list); + +/* print a fexl_list */ +void fexl_list_print(char *title, struct fexl_list *list); + +/* print a pexpr_list */ +void pexpr_list_print(char *title, struct pexpr_list *list); + +/* free an fexpr_list */ +void fexpr_list_free(struct fexpr_list *list); + +/* free an fexl_list */ +void fexl_list_free(struct fexl_list *list); + +/* free a sdv_list */ +void sdv_list_free(struct sdv_list *list); + +/* check whether 2 pexpr are equal */ +bool pexpr_eq(struct pexpr *e1, struct pexpr *e2); + +/* copy a pexpr */ +struct pexpr * pexpr_copy(const struct pexpr *org); + +/* free a pexpr */ +void pexpr_free(struct pexpr *e); + +/* print a pexpr  */ +void pexpr_print(char *tag, struct pexpr *e, int prevtoken); + +/* convert a fexpr to a pexpr */ +struct pexpr * pexf(struct fexpr *fe); + +/* eliminate duplicate and redundant operands */ +struct pexpr * pexpr_eliminate_dups(struct pexpr *e); + +#endif -- 2.33.0