From d4fdccadbab5043c442b00dbf54555873c6bee7b Mon Sep 17 00:00:00 2001 From: Paolo Bonzini Date: Wed, 23 Jan 2019 14:55:56 +0800 Subject: minikconfig: add parser skeleton MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This implements a scanner and recursive descent parser for Kconfig-like configuration files. The only "action" of the parser is for now to detect undefined variables and process include files. The main differences between Kconfig and this are: * only the "bool" type is supported * variables can only be defined once * choices are not supported (but they could be added as syntactic sugar for multiple Boolean values) * menus and other graphical concepts (prompts, help text) are not supported * assignments ("CONFIG_FOO=y", "CONFIG_FOO=n") are parsed as part of the Kconfig language, not as a separate file. The idea was originally by Ákos Kovács, but I could not find his implementation so I had to redo it. Signed-off-by: Paolo Bonzini Message-Id: <20190123065618.3520-23-yang.zhong@intel.com> Signed-off-by: Paolo Bonzini --- scripts/minikconf.py | 441 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 441 insertions(+) create mode 100644 scripts/minikconf.py (limited to 'scripts/minikconf.py') diff --git a/scripts/minikconf.py b/scripts/minikconf.py new file mode 100644 index 0000000000..fd75d96c6a --- /dev/null +++ b/scripts/minikconf.py @@ -0,0 +1,441 @@ +# +# Mini-Kconfig parser +# +# Copyright (c) 2015 Red Hat Inc. +# +# Authors: +# Paolo Bonzini +# +# This work is licensed under the terms of the GNU GPL, version 2 +# or, at your option, any later version. See the COPYING file in +# the top-level directory. + +from __future__ import print_function +import os +import sys + +__all__ = [ 'KconfigParserError', 'KconfigData', 'KconfigParser' ] + +def debug_print(*args): + #print('# ' + (' '.join(str(x) for x in args))) + pass + +# ------------------------------------------- +# KconfigData implements the Kconfig semantics. For now it can only +# detect undefined symbols, i.e. symbols that were referenced in +# assignments or dependencies but were not declared with "config FOO". +# +# Semantic actions are represented by methods called do_*. The do_var +# method return the semantic value of a variable (which right now is +# just its name). +# ------------------------------------------- + +class KconfigData: + def __init__(self): + self.previously_included = [] + self.incl_info = None + self.defined_vars = set() + self.referenced_vars = set() + + # semantic analysis ------------- + + def check_undefined(self): + undef = False + for i in self.referenced_vars: + if not (i in self.defined_vars): + print("undefined symbol %s" % (i), file=sys.stderr) + undef = True + return undef + + # semantic actions ------------- + + def do_declaration(self, var): + if (var in self.defined_vars): + raise Exception('variable "' + var + '" defined twice') + + self.defined_vars.add(var) + + # var is a string with the variable's name. + # + # For now this just returns the variable's name itself. + def do_var(self, var): + self.referenced_vars.add(var) + return var + + def do_assignment(self, var, val): + pass + + def do_default(self, var, val, cond=None): + pass + + def do_depends_on(self, var, expr): + pass + + def do_select(self, var, symbol, cond=None): + pass + + def do_imply(self, var, symbol, cond=None): + pass + +# ------------------------------------------- +# KconfigParser implements a recursive descent parser for (simplified) +# Kconfig syntax. +# ------------------------------------------- + +# tokens table +TOKENS = {} +TOK_NONE = -1 +TOK_LPAREN = 0; TOKENS[TOK_LPAREN] = '"("'; +TOK_RPAREN = 1; TOKENS[TOK_RPAREN] = '")"'; +TOK_EQUAL = 2; TOKENS[TOK_EQUAL] = '"="'; +TOK_AND = 3; TOKENS[TOK_AND] = '"&&"'; +TOK_OR = 4; TOKENS[TOK_OR] = '"||"'; +TOK_NOT = 5; TOKENS[TOK_NOT] = '"!"'; +TOK_DEPENDS = 6; TOKENS[TOK_DEPENDS] = '"depends"'; +TOK_ON = 7; TOKENS[TOK_ON] = '"on"'; +TOK_SELECT = 8; TOKENS[TOK_SELECT] = '"select"'; +TOK_IMPLY = 9; TOKENS[TOK_IMPLY] = '"imply"'; +TOK_CONFIG = 10; TOKENS[TOK_CONFIG] = '"config"'; +TOK_DEFAULT = 11; TOKENS[TOK_DEFAULT] = '"default"'; +TOK_Y = 12; TOKENS[TOK_Y] = '"y"'; +TOK_N = 13; TOKENS[TOK_N] = '"n"'; +TOK_SOURCE = 14; TOKENS[TOK_SOURCE] = '"source"'; +TOK_BOOL = 15; TOKENS[TOK_BOOL] = '"bool"'; +TOK_IF = 16; TOKENS[TOK_IF] = '"if"'; +TOK_ID = 17; TOKENS[TOK_ID] = 'identifier'; +TOK_EOF = 18; TOKENS[TOK_EOF] = 'end of file'; + +class KconfigParserError(Exception): + def __init__(self, parser, msg, tok=None): + self.loc = parser.location() + tok = tok or parser.tok + if tok != TOK_NONE: + location = TOKENS.get(tok, None) or ('"%s"' % tok) + msg = '%s before %s' % (msg, location) + self.msg = msg + + def __str__(self): + return "%s: %s" % (self.loc, self.msg) + +class KconfigParser: + @classmethod + def parse(self, fp): + data = KconfigData() + parser = KconfigParser(data) + parser.parse_file(fp) + if data.check_undefined(): + raise KconfigParserError(parser, "there were undefined symbols") + + return data + + def __init__(self, data): + self.data = data + + def parse_file(self, fp): + self.abs_fname = os.path.abspath(fp.name) + self.fname = fp.name + self.data.previously_included.append(self.abs_fname) + self.src = fp.read() + if self.src == '' or self.src[-1] != '\n': + self.src += '\n' + self.cursor = 0 + self.line = 1 + self.line_pos = 0 + self.get_token() + self.parse_config() + + # file management ----- + + def error_path(self): + inf = self.data.incl_info + res = "" + while inf: + res = ("In file included from %s:%d:\n" % (inf['file'], + inf['line'])) + res + inf = inf['parent'] + return res + + def location(self): + col = 1 + for ch in self.src[self.line_pos:self.pos]: + if ch == '\t': + col += 8 - ((col - 1) % 8) + else: + col += 1 + return '%s%s:%d:%d' %(self.error_path(), self.fname, self.line, col) + + def do_include(self, include): + incl_abs_fname = os.path.join(os.path.dirname(self.abs_fname), + include) + # catch inclusion cycle + inf = self.data.incl_info + while inf: + if incl_abs_fname == os.path.abspath(inf['file']): + raise KconfigParserError(self, "Inclusion loop for %s" + % include) + inf = inf['parent'] + + # skip multiple include of the same file + if incl_abs_fname in self.data.previously_included: + return + try: + fp = open(incl_abs_fname, 'r') + except IOError as e: + raise KconfigParserError(self, + '%s: %s' % (e.strerror, include)) + + inf = self.data.incl_info + self.data.incl_info = { 'file': self.fname, 'line': self.line, + 'parent': inf } + KconfigParser(self.data).parse_file(fp) + self.data.incl_info = inf + + # recursive descent parser ----- + + # y_or_n: Y | N + def parse_y_or_n(self): + if self.tok == TOK_Y: + self.get_token() + return True + if self.tok == TOK_N: + self.get_token() + return False + raise KconfigParserError(self, 'Expected "y" or "n"') + + # var: ID + def parse_var(self): + if self.tok == TOK_ID: + val = self.val + self.get_token() + return self.data.do_var(val) + else: + raise KconfigParserError(self, 'Expected identifier') + + # assignment_var: ID (starting with "CONFIG_") + def parse_assignment_var(self): + if self.tok == TOK_ID: + val = self.val + if not val.startswith("CONFIG_"): + raise KconfigParserError(self, + 'Expected identifier starting with "CONFIG_"', TOK_NONE) + self.get_token() + return self.data.do_var(val[7:]) + else: + raise KconfigParserError(self, 'Expected identifier') + + # assignment: var EQUAL y_or_n + def parse_assignment(self): + var = self.parse_assignment_var() + if self.tok != TOK_EQUAL: + raise KconfigParserError(self, 'Expected "="') + self.get_token() + self.data.do_assignment(var, self.parse_y_or_n()) + + # primary: NOT primary + # | LPAREN expr RPAREN + # | var + def parse_primary(self): + if self.tok == TOK_NOT: + self.get_token() + self.parse_primary() + elif self.tok == TOK_LPAREN: + self.get_token() + self.parse_expr() + if self.tok != TOK_RPAREN: + raise KconfigParserError(self, 'Expected ")"') + self.get_token() + elif self.tok == TOK_ID: + self.parse_var() + else: + raise KconfigParserError(self, 'Expected "!" or "(" or identifier') + + # disj: primary (OR primary)* + def parse_disj(self): + self.parse_primary() + while self.tok == TOK_OR: + self.get_token() + self.parse_primary() + + # expr: disj (AND disj)* + def parse_expr(self): + self.parse_disj() + while self.tok == TOK_AND: + self.get_token() + self.parse_disj() + + # condition: IF expr + # | empty + def parse_condition(self): + if self.tok == TOK_IF: + self.get_token() + return self.parse_expr() + else: + return None + + # property: DEFAULT y_or_n condition + # | DEPENDS ON expr + # | SELECT var condition + # | BOOL + def parse_property(self, var): + if self.tok == TOK_DEFAULT: + self.get_token() + val = self.parse_y_or_n() + cond = self.parse_condition() + self.data.do_default(var, val, cond) + elif self.tok == TOK_DEPENDS: + self.get_token() + if self.tok != TOK_ON: + raise KconfigParserError(self, 'Expected "on"') + self.get_token() + self.data.do_depends_on(var, self.parse_expr()) + elif self.tok == TOK_SELECT: + self.get_token() + symbol = self.parse_var() + cond = self.parse_condition() + self.data.do_select(var, symbol, cond) + elif self.tok == TOK_IMPLY: + self.get_token() + symbol = self.parse_var() + cond = self.parse_condition() + self.data.do_imply(var, symbol, cond) + elif self.tok == TOK_BOOL: + self.get_token() + else: + raise KconfigParserError(self, 'Error in recursive descent?') + + # properties: properties property + # | /* empty */ + def parse_properties(self, var): + had_default = False + while self.tok == TOK_DEFAULT or self.tok == TOK_DEPENDS or \ + self.tok == TOK_SELECT or self.tok == TOK_BOOL or \ + self.tok == TOK_IMPLY: + self.parse_property(var) + self.data.do_default(var, False) + + # for nicer error message + if self.tok != TOK_SOURCE and self.tok != TOK_CONFIG and \ + self.tok != TOK_ID and self.tok != TOK_EOF: + raise KconfigParserError(self, 'expected "source", "config", identifier, ' + + '"default", "depends on", "imply" or "select"') + + # declaration: config var properties + def parse_declaration(self): + if self.tok == TOK_CONFIG: + self.get_token() + var = self.parse_var() + self.data.do_declaration(var) + self.parse_properties(var) + else: + raise KconfigParserError(self, 'Error in recursive descent?') + + # clause: SOURCE + # | declaration + # | assignment + def parse_clause(self): + if self.tok == TOK_SOURCE: + val = self.val + self.get_token() + self.do_include(val) + elif self.tok == TOK_CONFIG: + self.parse_declaration() + elif self.tok == TOK_ID: + self.parse_assignment() + else: + raise KconfigParserError(self, 'expected "source", "config" or identifier') + + # config: clause+ EOF + def parse_config(self): + while self.tok != TOK_EOF: + self.parse_clause() + return self.data + + # scanner ----- + + def get_token(self): + while True: + self.tok = self.src[self.cursor] + self.pos = self.cursor + self.cursor += 1 + + self.val = None + self.tok = self.scan_token() + if self.tok is not None: + return + + def check_keyword(self, rest): + if not self.src.startswith(rest, self.cursor): + return False + length = len(rest) + if self.src[self.cursor + length].isalnum() or self.src[self.cursor + length] == '|': + return False + self.cursor += length + return True + + def scan_token(self): + if self.tok == '#': + self.cursor = self.src.find('\n', self.cursor) + return None + elif self.tok == '=': + return TOK_EQUAL + elif self.tok == '(': + return TOK_LPAREN + elif self.tok == ')': + return TOK_RPAREN + elif self.tok == '&' and self.src[self.pos+1] == '&': + self.cursor += 1 + return TOK_AND + elif self.tok == '|' and self.src[self.pos+1] == '|': + self.cursor += 1 + return TOK_OR + elif self.tok == '!': + return TOK_NOT + elif self.tok == 'd' and self.check_keyword("epends"): + return TOK_DEPENDS + elif self.tok == 'o' and self.check_keyword("n"): + return TOK_ON + elif self.tok == 's' and self.check_keyword("elect"): + return TOK_SELECT + elif self.tok == 'i' and self.check_keyword("mply"): + return TOK_IMPLY + elif self.tok == 'c' and self.check_keyword("onfig"): + return TOK_CONFIG + elif self.tok == 'd' and self.check_keyword("efault"): + return TOK_DEFAULT + elif self.tok == 'b' and self.check_keyword("ool"): + return TOK_BOOL + elif self.tok == 'i' and self.check_keyword("f"): + return TOK_IF + elif self.tok == 'y' and self.check_keyword(""): + return TOK_Y + elif self.tok == 'n' and self.check_keyword(""): + return TOK_N + elif (self.tok == 's' and self.check_keyword("ource")) or \ + self.tok == 'i' and self.check_keyword("nclude"): + # source FILENAME + # include FILENAME + while self.src[self.cursor].isspace(): + self.cursor += 1 + start = self.cursor + self.cursor = self.src.find('\n', self.cursor) + self.val = self.src[start:self.cursor] + return TOK_SOURCE + elif self.tok.isalpha(): + # identifier + while self.src[self.cursor].isalnum() or self.src[self.cursor] == '_': + self.cursor += 1 + self.val = self.src[self.pos:self.cursor] + return TOK_ID + elif self.tok == '\n': + if self.cursor == len(self.src): + return TOK_EOF + self.line += 1 + self.line_pos = self.cursor + elif not self.tok.isspace(): + raise KconfigParserError(self, 'invalid input') + + return None + +if __name__ == '__main__': + fname = len(sys.argv) > 1 and sys.argv[1] or 'Kconfig.test' + KconfigParser.parse(open(fname, 'r')) -- cgit v1.2.3 From 53167f562693981dbc18fb0071df4667dabdf7b6 Mon Sep 17 00:00:00 2001 From: Paolo Bonzini Date: Wed, 23 Jan 2019 14:55:57 +0800 Subject: minikconfig: add AST Add Python classes that represent the Kconfig abstract syntax tree. The abstract syntax tree is stored as a list of clauses. For example: config FOO depends on BAR select BAZ is represented as three clauses: FOO depends on BAR FOO default n select BAZ if FOO Signed-off-by: Paolo Bonzini Message-Id: <20190123065618.3520-24-yang.zhong@intel.com> Signed-off-by: Paolo Bonzini --- scripts/minikconf.py | 121 +++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 102 insertions(+), 19 deletions(-) (limited to 'scripts/minikconf.py') diff --git a/scripts/minikconf.py b/scripts/minikconf.py index fd75d96c6a..f0cc3b9fb9 100644 --- a/scripts/minikconf.py +++ b/scripts/minikconf.py @@ -31,11 +31,84 @@ def debug_print(*args): # ------------------------------------------- class KconfigData: + class Expr: + def __and__(self, rhs): + return KconfigData.AND(self, rhs) + def __or__(self, rhs): + return KconfigData.OR(self, rhs) + def __invert__(self): + return KconfigData.NOT(self) + + class AND(Expr): + def __init__(self, lhs, rhs): + self.lhs = lhs + self.rhs = rhs + def __str__(self): + return "(%s && %s)" % (self.lhs, self.rhs) + + class OR(Expr): + def __init__(self, lhs, rhs): + self.lhs = lhs + self.rhs = rhs + def __str__(self): + return "(%s || %s)" % (self.lhs, self.rhs) + + class NOT(Expr): + def __init__(self, lhs): + self.lhs = lhs + def __str__(self): + return "!%s" % (self.lhs) + + class Var(Expr): + def __init__(self, name): + self.name = name + self.value = None + def __str__(self): + return self.name + + class Clause: + def __init__(self, dest): + self.dest = dest + + class AssignmentClause(Clause): + def __init__(self, dest, value): + KconfigData.Clause.__init__(self, dest) + self.value = value + def __str__(self): + return "%s=%s" % (self.dest, 'y' if self.value else 'n') + + class DefaultClause(Clause): + def __init__(self, dest, value, cond=None): + KconfigData.Clause.__init__(self, dest) + self.value = value + self.cond = cond + def __str__(self): + value = 'y' if self.value else 'n' + if self.cond is None: + return "config %s default %s" % (self.dest, value) + else: + return "config %s default %s if %s" % (self.dest, value, self.cond) + + class DependsOnClause(Clause): + def __init__(self, dest, expr): + KconfigData.Clause.__init__(self, dest) + self.expr = expr + def __str__(self): + return "config %s depends on %s" % (self.dest, self.expr) + + class SelectClause(Clause): + def __init__(self, dest, cond): + KconfigData.Clause.__init__(self, dest) + self.cond = cond + def __str__(self): + return "select %s if %s" % (self.dest, self.cond) + def __init__(self): self.previously_included = [] self.incl_info = None self.defined_vars = set() - self.referenced_vars = set() + self.referenced_vars = dict() + self.clauses = list() # semantic analysis ------------- @@ -53,29 +126,34 @@ class KconfigData: if (var in self.defined_vars): raise Exception('variable "' + var + '" defined twice') - self.defined_vars.add(var) + self.defined_vars.add(var.name) # var is a string with the variable's name. - # - # For now this just returns the variable's name itself. def do_var(self, var): - self.referenced_vars.add(var) - return var + if (var in self.referenced_vars): + return self.referenced_vars[var] + + var_obj = self.referenced_vars[var] = KconfigData.Var(var) + return var_obj def do_assignment(self, var, val): - pass + self.clauses.append(KconfigData.AssignmentClause(var, val)) def do_default(self, var, val, cond=None): - pass + self.clauses.append(KconfigData.DefaultClause(var, val, cond)) def do_depends_on(self, var, expr): - pass + self.clauses.append(KconfigData.DependsOnClause(var, expr)) def do_select(self, var, symbol, cond=None): - pass + cond = (cond & var) if cond is not None else var + self.clauses.append(KconfigData.SelectClause(symbol, cond)) def do_imply(self, var, symbol, cond=None): - pass + # "config X imply Y [if COND]" is the same as + # "config Y default y if X [&& COND]" + cond = (cond & var) if cond is not None else var + self.do_default(symbol, True, cond) # ------------------------------------------- # KconfigParser implements a recursive descent parser for (simplified) @@ -237,31 +315,34 @@ class KconfigParser: def parse_primary(self): if self.tok == TOK_NOT: self.get_token() - self.parse_primary() + val = ~self.parse_primary() elif self.tok == TOK_LPAREN: self.get_token() - self.parse_expr() + val = self.parse_expr() if self.tok != TOK_RPAREN: raise KconfigParserError(self, 'Expected ")"') self.get_token() elif self.tok == TOK_ID: - self.parse_var() + val = self.parse_var() else: raise KconfigParserError(self, 'Expected "!" or "(" or identifier') + return val # disj: primary (OR primary)* def parse_disj(self): - self.parse_primary() + lhs = self.parse_primary() while self.tok == TOK_OR: self.get_token() - self.parse_primary() + lhs = lhs | self.parse_primary() + return lhs # expr: disj (AND disj)* def parse_expr(self): - self.parse_disj() + lhs = self.parse_disj() while self.tok == TOK_AND: self.get_token() - self.parse_disj() + lhs = lhs & self.parse_disj() + return lhs # condition: IF expr # | empty @@ -438,4 +519,6 @@ class KconfigParser: if __name__ == '__main__': fname = len(sys.argv) > 1 and sys.argv[1] or 'Kconfig.test' - KconfigParser.parse(open(fname, 'r')) + data = KconfigParser.parse(open(fname, 'r')) + for i in data.clauses: + print i -- cgit v1.2.3 From f7082a9a7cb26bd6531d6cd25914e4fcc30ab0c3 Mon Sep 17 00:00:00 2001 From: Paolo Bonzini Date: Wed, 23 Jan 2019 14:55:58 +0800 Subject: minikconfig: add semantic analysis There are three parts in the semantic analysis: 1) evaluating expressions. This is done as a simple visit of the Expr nodes. 2) ordering clauses. This is done by constructing a graph of variables. There is an edge from X to Y if Y depends on X, if X selects Y, or if X appears in a conditional selection of Y; in other words, if the value of X can affect the value of Y. Each clause has a "destination" variable whose value can be affected by the clause, and clauses will be processed according to a topological sorting of their destination variables. Defaults are processed after all other clauses with the same destination. 3) deriving the value of the variables. This is done by processing the clauses in the topological order provided by the previous step. A "depends on" clause will force a variable to False, a "select" clause will force a variable to True, an assignment will force a variable to its RHS. A default will set a variable to its RHS if it has not been set before. Because all variables have a default, after visiting all clauses all variables will have been set. Signed-off-by: Paolo Bonzini Message-Id: <20190123065618.3520-25-yang.zhong@intel.com> Signed-off-by: Paolo Bonzini --- scripts/minikconf.py | 144 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 135 insertions(+), 9 deletions(-) (limited to 'scripts/minikconf.py') diff --git a/scripts/minikconf.py b/scripts/minikconf.py index f0cc3b9fb9..d89fb09271 100644 --- a/scripts/minikconf.py +++ b/scripts/minikconf.py @@ -14,7 +14,8 @@ from __future__ import print_function import os import sys -__all__ = [ 'KconfigParserError', 'KconfigData', 'KconfigParser' ] +__all__ = [ 'KconfigDataError', 'KconfigParserError', + 'KconfigData', 'KconfigParser' ] def debug_print(*args): #print('# ' + (' '.join(str(x) for x in args))) @@ -30,6 +31,13 @@ def debug_print(*args): # just its name). # ------------------------------------------- +class KconfigDataError(Exception): + def __init__(self, msg): + self.msg = msg + + def __str__(self): + return self.msg + class KconfigData: class Expr: def __and__(self, rhs): @@ -39,6 +47,12 @@ class KconfigData: def __invert__(self): return KconfigData.NOT(self) + # Abstract methods + def add_edges_to(self, var): + pass + def evaluate(self): + assert False + class AND(Expr): def __init__(self, lhs, rhs): self.lhs = lhs @@ -46,6 +60,12 @@ class KconfigData: def __str__(self): return "(%s && %s)" % (self.lhs, self.rhs) + def add_edges_to(self, var): + self.lhs.add_edges_to(var) + self.rhs.add_edges_to(var) + def evaluate(self): + return self.lhs.evaluate() and self.rhs.evaluate() + class OR(Expr): def __init__(self, lhs, rhs): self.lhs = lhs @@ -53,35 +73,85 @@ class KconfigData: def __str__(self): return "(%s || %s)" % (self.lhs, self.rhs) + def add_edges_to(self, var): + self.lhs.add_edges_to(var) + self.rhs.add_edges_to(var) + def evaluate(self): + return self.lhs.evaluate() or self.rhs.evaluate() + class NOT(Expr): def __init__(self, lhs): self.lhs = lhs def __str__(self): return "!%s" % (self.lhs) + def add_edges_to(self, var): + self.lhs.add_edges_to(var) + def evaluate(self): + return not self.lhs.evaluate() + class Var(Expr): def __init__(self, name): self.name = name self.value = None + self.outgoing = set() + self.clauses_for_var = list() def __str__(self): return self.name + def has_value(self): + return not (self.value is None) + def set_value(self, val, clause): + self.clauses_for_var.append(clause) + if self.has_value() and self.value != val: + print("The following clauses were found for " + self.name) + for i in self.clauses_for_var: + print(" " + str(i), file=sys.stderr) + raise KconfigDataError('contradiction between clauses when setting %s' % self) + debug_print("=> %s is now %s" % (self.name, val)) + self.value = val + + # depth first search of the dependency graph + def dfs(self, visited, f): + if self in visited: + return + visited.add(self) + for v in self.outgoing: + v.dfs(visited, f) + f(self) + + def add_edges_to(self, var): + self.outgoing.add(var) + def evaluate(self): + if not self.has_value(): + raise KconfigDataError('cycle found including %s' % self) + return self.value + class Clause: def __init__(self, dest): self.dest = dest + def priority(self): + return 0 + def process(self): + pass class AssignmentClause(Clause): def __init__(self, dest, value): KconfigData.Clause.__init__(self, dest) self.value = value def __str__(self): - return "%s=%s" % (self.dest, 'y' if self.value else 'n') + return "CONFIG_%s=%s" % (self.dest, 'y' if self.value else 'n') + + def process(self): + self.dest.set_value(self.value, self) class DefaultClause(Clause): def __init__(self, dest, value, cond=None): KconfigData.Clause.__init__(self, dest) self.value = value self.cond = cond + if not (self.cond is None): + self.cond.add_edges_to(self.dest) def __str__(self): value = 'y' if self.value else 'n' if self.cond is None: @@ -89,20 +159,38 @@ class KconfigData: else: return "config %s default %s if %s" % (self.dest, value, self.cond) + def priority(self): + # Defaults are processed just before leaving the variable + return -1 + def process(self): + if not self.dest.has_value() and \ + (self.cond is None or self.cond.evaluate()): + self.dest.set_value(self.value, self) + class DependsOnClause(Clause): def __init__(self, dest, expr): KconfigData.Clause.__init__(self, dest) self.expr = expr + self.expr.add_edges_to(self.dest) def __str__(self): return "config %s depends on %s" % (self.dest, self.expr) + def process(self): + if not self.expr.evaluate(): + self.dest.set_value(False, self) + class SelectClause(Clause): def __init__(self, dest, cond): KconfigData.Clause.__init__(self, dest) self.cond = cond + self.cond.add_edges_to(self.dest) def __str__(self): return "select %s if %s" % (self.dest, self.cond) + def process(self): + if self.cond.evaluate(): + self.dest.set_value(True, self) + def __init__(self): self.previously_included = [] self.incl_info = None @@ -120,11 +208,54 @@ class KconfigData: undef = True return undef + def compute_config(self): + if self.check_undefined(): + raise KconfigDataError("there were undefined symbols") + return None + + debug_print("Input:") + for clause in self.clauses: + debug_print(clause) + + debug_print("\nDependency graph:") + for i in self.referenced_vars: + debug_print(i, "->", [str(x) for x in self.referenced_vars[i].outgoing]) + + # The reverse of the depth-first order is the topological sort + dfo = dict() + visited = set() + debug_print("\n") + def visit_fn(var): + debug_print(var, "has DFS number", len(dfo)) + dfo[var] = len(dfo) + + for name, v in self.referenced_vars.items(): + self.do_default(v, False) + v.dfs(visited, visit_fn) + + # Put higher DFS numbers and higher priorities first. This + # places the clauses in topological order and places defaults + # after assignments and dependencies. + self.clauses.sort(key=lambda x: (-dfo[x.dest], -x.priority())) + + debug_print("\nSorted clauses:") + for clause in self.clauses: + debug_print(clause) + clause.process() + + debug_print("") + values = dict() + for name, v in self.referenced_vars.items(): + debug_print("Evaluating", name) + values[name] = v.evaluate() + + return values + # semantic actions ------------- def do_declaration(self, var): if (var in self.defined_vars): - raise Exception('variable "' + var + '" defined twice') + raise KconfigDataError('variable "' + var + '" defined twice') self.defined_vars.add(var.name) @@ -201,9 +332,6 @@ class KconfigParser: data = KconfigData() parser = KconfigParser(data) parser.parse_file(fp) - if data.check_undefined(): - raise KconfigParserError(parser, "there were undefined symbols") - return data def __init__(self, data): @@ -392,7 +520,6 @@ class KconfigParser: self.tok == TOK_SELECT or self.tok == TOK_BOOL or \ self.tok == TOK_IMPLY: self.parse_property(var) - self.data.do_default(var, False) # for nicer error message if self.tok != TOK_SOURCE and self.tok != TOK_CONFIG and \ @@ -520,5 +647,4 @@ class KconfigParser: if __name__ == '__main__': fname = len(sys.argv) > 1 and sys.argv[1] or 'Kconfig.test' data = KconfigParser.parse(open(fname, 'r')) - for i in data.clauses: - print i + print data.compute_config() -- cgit v1.2.3 From 82f5181777ebe04b550fd94a1d04c49dd3f012dc Mon Sep 17 00:00:00 2001 From: Paolo Bonzini Date: Wed, 23 Jan 2019 14:56:00 +0800 Subject: kconfig: introduce kconfig files The Kconfig files were generated mostly with this script: for i in `grep -ho CONFIG_[A-Z0-9_]* default-configs/* | sort -u`; do set fnord `git grep -lw $i -- 'hw/*/Makefile.objs' ` shift if test $# = 1; then cat >> $(dirname $1)/Kconfig << EOF config ${i#CONFIG_} bool EOF git add $(dirname $1)/Kconfig else echo $i $* fi done sed -i '$d' hw/*/Kconfig for i in hw/*; do if test -d $i && ! test -f $i/Kconfig; then touch $i/Kconfig git add $i/Kconfig fi done Whenever a symbol is referenced from multiple subdirectories, the script prints the list of directories that reference the symbol. These symbols have to be added manually to the Kconfig files. Kconfig.host and hw/Kconfig were created manually. Signed-off-by: Paolo Bonzini Signed-off-by: Yang Zhong Message-Id: <20190123065618.3520-27-yang.zhong@intel.com> Signed-off-by: Paolo Bonzini --- scripts/minikconf.py | 35 ++++++++++++++++++++++++++++++++--- 1 file changed, 32 insertions(+), 3 deletions(-) (limited to 'scripts/minikconf.py') diff --git a/scripts/minikconf.py b/scripts/minikconf.py index d89fb09271..6bedc5736e 100644 --- a/scripts/minikconf.py +++ b/scripts/minikconf.py @@ -13,6 +13,7 @@ from __future__ import print_function import os import sys +import re __all__ = [ 'KconfigDataError', 'KconfigParserError', 'KconfigData', 'KconfigParser' ] @@ -350,6 +351,12 @@ class KconfigParser: self.get_token() self.parse_config() + def do_assignment(self, var, val): + if not var.startswith("CONFIG_"): + raise Error('assigned variable should start with CONFIG_') + var = self.data.do_var(var[7:]) + self.data.do_assignment(var, val) + # file management ----- def error_path(self): @@ -645,6 +652,28 @@ class KconfigParser: return None if __name__ == '__main__': - fname = len(sys.argv) > 1 and sys.argv[1] or 'Kconfig.test' - data = KconfigParser.parse(open(fname, 'r')) - print data.compute_config() + argv = sys.argv + if len(argv) == 1: + print ("%s: at least one argument is required" % argv[0], file=sys.stderr) + sys.exit(1) + + data = KconfigData() + parser = KconfigParser(data) + for arg in argv[3:]: + m = re.match(r'^(CONFIG_[A-Z0-9_]+)=([yn]?)$', arg) + if m is not None: + name, value = m.groups() + parser.do_assignment(name, value == 'y') + else: + fp = open(arg, 'r') + parser.parse_file(fp) + fp.close() + + config = data.compute_config() + for key in sorted(config.keys()): + print ('CONFIG_%s=%s' % (key, ('y' if config[key] else 'n'))) + + deps = open(argv[2], 'w') + for fname in data.previously_included: + print ('%s: %s' % (argv[1], fname), file=deps) + deps.close() -- cgit v1.2.3 From f349474920d80838ecea3d421531fdb0660b8740 Mon Sep 17 00:00:00 2001 From: Paolo Bonzini Date: Wed, 23 Jan 2019 14:56:17 +0800 Subject: minikconfig: implement allnoconfig and defconfig modes Apart from defconfig (which is a no-op), allyesconfig/allnoconfig/randcondfig can be implemented simply by ignoring the RHS of assignments and "default" statements. The RHS is replaced respectively by "true", "false" or a random value. However, allyesconfig and randconfig do not quite work, because all the files for hw/ARCH/Kconfig are sourced and therefore you could end up enabling some ARM boards in x86 or things like that. This is left for future work, but I am leaving it in to help debugging minikconf itself. allnoconfig mode is tied to a new configure option, --without-default-devices. Signed-off-by: Paolo Bonzini --- scripts/minikconf.py | 39 ++++++++++++++++++++++++++++++++++----- 1 file changed, 34 insertions(+), 5 deletions(-) (limited to 'scripts/minikconf.py') diff --git a/scripts/minikconf.py b/scripts/minikconf.py index 6bedc5736e..5421db0ed0 100644 --- a/scripts/minikconf.py +++ b/scripts/minikconf.py @@ -14,9 +14,11 @@ from __future__ import print_function import os import sys import re +import random __all__ = [ 'KconfigDataError', 'KconfigParserError', - 'KconfigData', 'KconfigParser' ] + 'KconfigData', 'KconfigParser' , + 'defconfig', 'allyesconfig', 'allnoconfig', 'randconfig' ] def debug_print(*args): #print('# ' + (' '.join(str(x) for x in args))) @@ -39,6 +41,11 @@ class KconfigDataError(Exception): def __str__(self): return self.msg +allyesconfig = lambda x: True +allnoconfig = lambda x: False +defconfig = lambda x: x +randconfig = lambda x: random.randint(0, 1) == 1 + class KconfigData: class Expr: def __and__(self, rhs): @@ -192,7 +199,8 @@ class KconfigData: if self.cond.evaluate(): self.dest.set_value(True, self) - def __init__(self): + def __init__(self, value_mangler=defconfig): + self.value_mangler = value_mangler self.previously_included = [] self.incl_info = None self.defined_vars = set() @@ -272,6 +280,7 @@ class KconfigData: self.clauses.append(KconfigData.AssignmentClause(var, val)) def do_default(self, var, val, cond=None): + val = self.value_mangler(val) self.clauses.append(KconfigData.DefaultClause(var, val, cond)) def do_depends_on(self, var, expr): @@ -328,9 +337,10 @@ class KconfigParserError(Exception): return "%s: %s" % (self.loc, self.msg) class KconfigParser: + @classmethod - def parse(self, fp): - data = KconfigData() + def parse(self, fp, mode=None): + data = KconfigData(mode or KconfigParser.defconfig) parser = KconfigParser(data) parser.parse_file(fp) return data @@ -653,11 +663,30 @@ class KconfigParser: if __name__ == '__main__': argv = sys.argv + mode = defconfig + if len(sys.argv) > 1: + if argv[1] == '--defconfig': + del argv[1] + elif argv[1] == '--randconfig': + random.seed() + mode = randconfig + del argv[1] + elif argv[1] == '--allyesconfig': + mode = allyesconfig + del argv[1] + elif argv[1] == '--allnoconfig': + mode = allnoconfig + del argv[1] + if len(argv) == 1: print ("%s: at least one argument is required" % argv[0], file=sys.stderr) sys.exit(1) - data = KconfigData() + if argv[1].startswith('-'): + print ("%s: invalid option %s" % (argv[0], argv[1]), file=sys.stderr) + sys.exit(1) + + data = KconfigData(mode) parser = KconfigParser(data) for arg in argv[3:]: m = re.match(r'^(CONFIG_[A-Z0-9_]+)=([yn]?)$', arg) -- cgit v1.2.3