cregit-Linux how code gets into the kernel

Release 4.15 scripts/kconfig/expr.c

Directory: scripts/kconfig
/*
 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
 * Released under the terms of the GNU GPL v2.0.
 */

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

#include "lkc.h"


#define DEBUG_EXPR	0

static int expr_eq(struct expr *e1, struct expr *e2);
static struct expr *expr_eliminate_yn(struct expr *e);


struct expr *expr_alloc_symbol(struct symbol *sym) { struct expr *e = xcalloc(1, sizeof(*e)); e->type = E_SYMBOL; e->left.sym = sym; return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel4293.33%133.33%
Arnaud Lacombe24.44%133.33%
Alan Cox12.22%133.33%
Total45100.00%3100.00%


struct expr *expr_alloc_one(enum expr_type type, struct expr *ce) { struct expr *e = xcalloc(1, sizeof(*e)); e->type = type; e->left.expr = ce; return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel4693.88%133.33%
Arnaud Lacombe24.08%133.33%
Alan Cox12.04%133.33%
Total49100.00%3100.00%


struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2) { struct expr *e = xcalloc(1, sizeof(*e)); e->type = type; e->left.expr = e1; e->right.expr = e2; return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel5995.16%133.33%
Arnaud Lacombe23.23%133.33%
Alan Cox11.61%133.33%
Total62100.00%3100.00%


struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2) { struct expr *e = xcalloc(1, sizeof(*e)); e->type = type; e->left.sym = s1; e->right.sym = s2; return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel5995.16%133.33%
Arnaud Lacombe23.23%133.33%
Alan Cox11.61%133.33%
Total62100.00%3100.00%


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; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel39100.00%1100.00%
Total39100.00%1100.00%


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; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel39100.00%1100.00%
Total39100.00%1100.00%


struct expr *expr_copy(const struct expr *org) { struct expr *e; if (!org) return NULL; e = xmalloc(sizeof(*org)); memcpy(e, org, sizeof(*org)); switch (org->type) { case E_SYMBOL: e->left = org->left; break; case E_NOT: e->left.expr = expr_copy(org->left.expr); break; case E_EQUAL: case E_GEQ: case E_GTH: case E_LEQ: case E_LTH: case E_UNEQUAL: e->left.sym = org->left.sym; e->right.sym = org->right.sym; break; case E_AND: case E_OR: case E_LIST: e->left.expr = expr_copy(org->left.expr); e->right.expr = expr_copy(org->right.expr); break; default: printf("can't copy type %d\n", e->type); free(e); e = NULL; break; } return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel18192.82%240.00%
Jan Beulich126.15%120.00%
Michal Marek10.51%120.00%
Alan Cox10.51%120.00%
Total195100.00%5100.00%


void expr_free(struct expr *e) { if (!e) return; switch (e->type) { case E_SYMBOL: break; case E_NOT: expr_free(e->left.expr); return; case E_EQUAL: case E_GEQ: case E_GTH: case E_LEQ: case E_LTH: case E_UNEQUAL: break; case E_OR: case E_AND: expr_free(e->left.expr); expr_free(e->right.expr); break; default: printf("how to free type %d?\n", e->type); break; } free(e); }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel8988.12%150.00%
Jan Beulich1211.88%150.00%
Total101100.00%2100.00%

static int trans_count; #define e1 (*ep1) #define e2 (*ep2)
static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2) { if (e1->type == type) { __expr_eliminate_eq(type, &e1->left.expr, &e2); __expr_eliminate_eq(type, &e1->right.expr, &e2); return; } if (e2->type == type) { __expr_eliminate_eq(type, &e1, &e2->left.expr); __expr_eliminate_eq(type, &e1, &e2->right.expr); return; } if (e1->type == E_SYMBOL && e2->type == E_SYMBOL && e1->left.sym == e2->left.sym && (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no)) return; if (!expr_eq(e1, e2)) return; trans_count++; expr_free(e1); expr_free(e2); switch (type) { case E_OR: e1 = expr_alloc_symbol(&symbol_no); e2 = expr_alloc_symbol(&symbol_no); break; case E_AND: e1 = expr_alloc_symbol(&symbol_yes); e2 = expr_alloc_symbol(&symbol_yes); break; default: ; } }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel223100.00%2100.00%
Total223100.00%2100.00%


void expr_eliminate_eq(struct expr **ep1, struct expr **ep2) { if (!e1 || !e2) return; switch (e1->type) { case E_OR: case E_AND: __expr_eliminate_eq(e1->type, ep1, ep2); default: ; } if (e1->type != e2->type) switch (e2->type) { case E_OR: case E_AND: __expr_eliminate_eq(e2->type, ep1, ep2); default: ; } e1 = expr_eliminate_yn(e1); e2 = expr_eliminate_yn(e2); }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel104100.00%2100.00%
Total104100.00%2100.00%

#undef e1 #undef e2
static int expr_eq(struct expr *e1, struct expr *e2) { int res, old_count; if (e1->type != e2->type) return 0; switch (e1->type) { case E_EQUAL: case E_GEQ: case E_GTH: case E_LEQ: case E_LTH: case E_UNEQUAL: return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym; case E_SYMBOL: return e1->left.sym == e2->left.sym; case E_NOT: return expr_eq(e1->left.expr, e2->left.expr); case E_AND: case E_OR: e1 = expr_copy(e1); e2 = expr_copy(e2); old_count = trans_count; expr_eliminate_eq(&e1, &e2); res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL && e1->left.sym == e2->left.sym); expr_free(e1); expr_free(e2); trans_count = old_count; return res; case E_LIST: case E_RANGE: case E_NONE: /* panic */; } if (DEBUG_EXPR) { expr_fprint(e1, stdout); printf(" = "); expr_fprint(e2, stdout); printf(" ?\n"); } return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel21990.50%350.00%
Jan Beulich124.96%116.67%
Andrew Morton104.13%116.67%
Michal Marek10.41%116.67%
Total242100.00%6100.00%


static struct expr *expr_eliminate_yn(struct expr *e) { struct expr *tmp; if (e) switch (e->type) { case E_AND: e->left.expr = expr_eliminate_yn(e->left.expr); e->right.expr = expr_eliminate_yn(e->right.expr); if (e->left.expr->type == E_SYMBOL) { if (e->left.expr->left.sym == &symbol_no) { expr_free(e->left.expr); expr_free(e->right.expr); e->type = E_SYMBOL; e->left.sym = &symbol_no; e->right.expr = NULL; return e; } else if (e->left.expr->left.sym == &symbol_yes) { free(e->left.expr); tmp = e->right.expr; *e = *(e->right.expr); free(tmp); return e; } } if (e->right.expr->type == E_SYMBOL) { if (e->right.expr->left.sym == &symbol_no) { expr_free(e->left.expr); expr_free(e->right.expr); e->type = E_SYMBOL; e->left.sym = &symbol_no; e->right.expr = NULL; return e; } else if (e->right.expr->left.sym == &symbol_yes) { free(e->right.expr); tmp = e->left.expr; *e = *(e->left.expr); free(tmp); return e; } } break; case E_OR: e->left.expr = expr_eliminate_yn(e->left.expr); e->right.expr = expr_eliminate_yn(e->right.expr); if (e->left.expr->type == E_SYMBOL) { if (e->left.expr->left.sym == &symbol_no) { free(e->left.expr); tmp = e->right.expr; *e = *(e->right.expr); free(tmp); return e; } else if (e->left.expr->left.sym == &symbol_yes) { expr_free(e->left.expr); expr_free(e->right.expr); e->type = E_SYMBOL; e->left.sym = &symbol_yes; e->right.expr = NULL; return e; } } if (e->right.expr->type == E_SYMBOL) { if (e->right.expr->left.sym == &symbol_no) { free(e->right.expr); tmp = e->left.expr; *e = *(e->left.expr); free(tmp); return e; } else if (e->right.expr->left.sym == &symbol_yes) { expr_free(e->left.expr); expr_free(e->right.expr); e->type = E_SYMBOL; e->left.sym = &symbol_yes; e->right.expr = NULL; return e; } } break; default: ; } return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel62299.84%150.00%
Michal Marek10.16%150.00%
Total623100.00%2100.00%

/* * bool FOO!=n => FOO */
struct expr *expr_trans_bool(struct expr *e) { if (!e) return NULL; switch (e->type) { case E_AND: case E_OR: case E_NOT: e->left.expr = expr_trans_bool(e->left.expr); e->right.expr = expr_trans_bool(e->right.expr); break; case E_UNEQUAL: // FOO!=n -> FOO if (e->left.sym->type == S_TRISTATE) { if (e->right.sym == &symbol_no) { e->type = E_SYMBOL; e->right.sym = NULL; } } break; default: ; } return e; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel119100.00%1100.00%
Total119100.00%1100.00%

/* * e1 || e2 -> ? */
static struct expr *expr_join_or(struct expr *e1, struct expr *e2) { struct expr *tmp; struct symbol *sym1, *sym2; if (expr_eq(e1, e2)) return expr_copy(e1); if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) return NULL; if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) return NULL; if (e1->type == E_NOT) { tmp = e1->left.expr; if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) return NULL; sym1 = tmp->left.sym; } else sym1 = e1->left.sym; if (e2->type == E_NOT) { if (e2->left.expr->type != E_SYMBOL) return NULL; sym2 = e2->left.expr->left.sym; } else sym2 = e2->left.sym; if (sym1 != sym2) return NULL; if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) return NULL; if (sym1->type == S_TRISTATE) { if (e1->type == E_EQUAL && e2->type == E_EQUAL && ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) || (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) { // (a='y') || (a='m') -> (a!='n') return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no); } if (e1->type == E_EQUAL && e2->type == E_EQUAL && ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) || (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) { // (a='y') || (a='n') -> (a!='m') return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod); } if (e1->type == E_EQUAL && e2->type == E_EQUAL && ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) || (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) { // (a='m') || (a='n') -> (a!='y') return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes); } } if (sym1->type == S_BOOLEAN && sym1 == sym2) { if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) || (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL)) return expr_alloc_symbol(&symbol_yes); } if (DEBUG_EXPR) { printf("optimize ("); expr_fprint(e1, stdout); printf(") || ("); expr_fprint(e2, stdout); printf(")?\n"); } return NULL; }

Contributors

PersonTokensPropCommitsCommitProp
Roman Zippel54997.51%133.33%
Andrew Morton132.31%133.33%
Trevor Keith10.18%133.33%
Total563100.00%3100.00%


static struct expr *expr_join_and(struct expr *e1, struct expr *e2) { struct expr *tmp; struct symbol *sym1, *sym2; if (expr_eq(e1, e2)) return expr_copy(e1); if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT) return NULL; if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT) return NULL; if (e1->type == E_NOT) { tmp = e1->left.expr; if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL) return NULL; sym1 = tmp->left.sym; } else sym1 = e1->left.sym; if (e2->type == E_NOT) { if (e2->left.expr->type != E_SYMBOL) return NULL; sym2 = e2->left.expr->left.sym; } else sym2 = e2->left.sym; if (sym1 != sym2) return NULL; if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE) return NULL; if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) || (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes)) // (a) && (a='y') -> (a='y') return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes); if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) || (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no)) // (a) && (a!='n') -> (a) return expr_alloc_symbol(sym1); if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) || (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->