1#!/usr/bin/env python3 2# 3# Mini-Kconfig parser 4# 5# Copyright (c) 2015 Red Hat Inc. 6# 7# Authors: 8# Paolo Bonzini <pbonzini@redhat.com> 9# 10# This work is licensed under the terms of the GNU GPL, version 2 11# or, at your option, any later version. See the COPYING file in 12# the top-level directory. 13 14from __future__ import print_function 15import os 16import sys 17import re 18import random 19 20__all__ = [ 'KconfigDataError', 'KconfigParserError', 21 'KconfigData', 'KconfigParser' , 22 'defconfig', 'allyesconfig', 'allnoconfig', 'randconfig' ] 23 24def debug_print(*args): 25 #print('# ' + (' '.join(str(x) for x in args))) 26 pass 27 28# ------------------------------------------- 29# KconfigData implements the Kconfig semantics. For now it can only 30# detect undefined symbols, i.e. symbols that were referenced in 31# assignments or dependencies but were not declared with "config FOO". 32# 33# Semantic actions are represented by methods called do_*. The do_var 34# method return the semantic value of a variable (which right now is 35# just its name). 36# ------------------------------------------- 37 38class KconfigDataError(Exception): 39 def __init__(self, msg): 40 self.msg = msg 41 42 def __str__(self): 43 return self.msg 44 45allyesconfig = lambda x: True 46allnoconfig = lambda x: False 47defconfig = lambda x: x 48randconfig = lambda x: random.randint(0, 1) == 1 49 50class KconfigData: 51 class Expr: 52 def __and__(self, rhs): 53 return KconfigData.AND(self, rhs) 54 def __or__(self, rhs): 55 return KconfigData.OR(self, rhs) 56 def __invert__(self): 57 return KconfigData.NOT(self) 58 59 # Abstract methods 60 def add_edges_to(self, var): 61 pass 62 def evaluate(self): 63 assert False 64 65 class AND(Expr): 66 def __init__(self, lhs, rhs): 67 self.lhs = lhs 68 self.rhs = rhs 69 def __str__(self): 70 return "(%s && %s)" % (self.lhs, self.rhs) 71 72 def add_edges_to(self, var): 73 self.lhs.add_edges_to(var) 74 self.rhs.add_edges_to(var) 75 def evaluate(self): 76 return self.lhs.evaluate() and self.rhs.evaluate() 77 78 class OR(Expr): 79 def __init__(self, lhs, rhs): 80 self.lhs = lhs 81 self.rhs = rhs 82 def __str__(self): 83 return "(%s || %s)" % (self.lhs, self.rhs) 84 85 def add_edges_to(self, var): 86 self.lhs.add_edges_to(var) 87 self.rhs.add_edges_to(var) 88 def evaluate(self): 89 return self.lhs.evaluate() or self.rhs.evaluate() 90 91 class NOT(Expr): 92 def __init__(self, lhs): 93 self.lhs = lhs 94 def __str__(self): 95 return "!%s" % (self.lhs) 96 97 def add_edges_to(self, var): 98 self.lhs.add_edges_to(var) 99 def evaluate(self): 100 return not self.lhs.evaluate() 101 102 class Var(Expr): 103 def __init__(self, name): 104 self.name = name 105 self.value = None 106 self.outgoing = set() 107 self.clauses_for_var = list() 108 def __str__(self): 109 return self.name 110 111 def has_value(self): 112 return not (self.value is None) 113 def set_value(self, val, clause): 114 self.clauses_for_var.append(clause) 115 if self.has_value() and self.value != val: 116 print("The following clauses were found for " + self.name) 117 for i in self.clauses_for_var: 118 print(" " + str(i), file=sys.stderr) 119 raise KconfigDataError('contradiction between clauses when setting %s' % self) 120 debug_print("=> %s is now %s" % (self.name, val)) 121 self.value = val 122 123 # depth first search of the dependency graph 124 def dfs(self, visited, f): 125 if self in visited: 126 return 127 visited.add(self) 128 for v in self.outgoing: 129 v.dfs(visited, f) 130 f(self) 131 132 def add_edges_to(self, var): 133 self.outgoing.add(var) 134 def evaluate(self): 135 if not self.has_value(): 136 raise KconfigDataError('cycle found including %s' % self) 137 return self.value 138 139 class Clause: 140 def __init__(self, dest): 141 self.dest = dest 142 def priority(self): 143 return 0 144 def process(self): 145 pass 146 147 class AssignmentClause(Clause): 148 def __init__(self, dest, value): 149 KconfigData.Clause.__init__(self, dest) 150 self.value = value 151 def __str__(self): 152 return "CONFIG_%s=%s" % (self.dest, 'y' if self.value else 'n') 153 154 def process(self): 155 self.dest.set_value(self.value, self) 156 157 class DefaultClause(Clause): 158 def __init__(self, dest, value, cond=None): 159 KconfigData.Clause.__init__(self, dest) 160 self.value = value 161 self.cond = cond 162 if not (self.cond is None): 163 self.cond.add_edges_to(self.dest) 164 def __str__(self): 165 value = 'y' if self.value else 'n' 166 if self.cond is None: 167 return "config %s default %s" % (self.dest, value) 168 else: 169 return "config %s default %s if %s" % (self.dest, value, self.cond) 170 171 def priority(self): 172 # Defaults are processed just before leaving the variable 173 return -1 174 def process(self): 175 if not self.dest.has_value() and \ 176 (self.cond is None or self.cond.evaluate()): 177 self.dest.set_value(self.value, self) 178 179 class DependsOnClause(Clause): 180 def __init__(self, dest, expr): 181 KconfigData.Clause.__init__(self, dest) 182 self.expr = expr 183 self.expr.add_edges_to(self.dest) 184 def __str__(self): 185 return "config %s depends on %s" % (self.dest, self.expr) 186 187 def process(self): 188 if not self.expr.evaluate(): 189 self.dest.set_value(False, self) 190 191 class SelectClause(Clause): 192 def __init__(self, dest, cond): 193 KconfigData.Clause.__init__(self, dest) 194 self.cond = cond 195 self.cond.add_edges_to(self.dest) 196 def __str__(self): 197 return "select %s if %s" % (self.dest, self.cond) 198 199 def process(self): 200 if self.cond.evaluate(): 201 self.dest.set_value(True, self) 202 203 def __init__(self, value_mangler=defconfig): 204 self.value_mangler = value_mangler 205 self.previously_included = [] 206 self.incl_info = None 207 self.defined_vars = set() 208 self.referenced_vars = dict() 209 self.clauses = list() 210 211 # semantic analysis ------------- 212 213 def check_undefined(self): 214 undef = False 215 for i in self.referenced_vars: 216 if not (i in self.defined_vars): 217 print("undefined symbol %s" % (i), file=sys.stderr) 218 undef = True 219 return undef 220 221 def compute_config(self): 222 if self.check_undefined(): 223 raise KconfigDataError("there were undefined symbols") 224 return None 225 226 debug_print("Input:") 227 for clause in self.clauses: 228 debug_print(clause) 229 230 debug_print("\nDependency graph:") 231 for i in self.referenced_vars: 232 debug_print(i, "->", [str(x) for x in self.referenced_vars[i].outgoing]) 233 234 # The reverse of the depth-first order is the topological sort 235 dfo = dict() 236 visited = set() 237 debug_print("\n") 238 def visit_fn(var): 239 debug_print(var, "has DFS number", len(dfo)) 240 dfo[var] = len(dfo) 241 242 for name, v in self.referenced_vars.items(): 243 self.do_default(v, False) 244 v.dfs(visited, visit_fn) 245 246 # Put higher DFS numbers and higher priorities first. This 247 # places the clauses in topological order and places defaults 248 # after assignments and dependencies. 249 self.clauses.sort(key=lambda x: (-dfo[x.dest], -x.priority())) 250 251 debug_print("\nSorted clauses:") 252 for clause in self.clauses: 253 debug_print(clause) 254 clause.process() 255 256 debug_print("") 257 values = dict() 258 for name, v in self.referenced_vars.items(): 259 debug_print("Evaluating", name) 260 values[name] = v.evaluate() 261 262 return values 263 264 # semantic actions ------------- 265 266 def do_declaration(self, var): 267 if (var in self.defined_vars): 268 raise KconfigDataError('variable "' + var + '" defined twice') 269 270 self.defined_vars.add(var.name) 271 272 # var is a string with the variable's name. 273 def do_var(self, var): 274 if (var in self.referenced_vars): 275 return self.referenced_vars[var] 276 277 var_obj = self.referenced_vars[var] = KconfigData.Var(var) 278 return var_obj 279 280 def do_assignment(self, var, val): 281 self.clauses.append(KconfigData.AssignmentClause(var, val)) 282 283 def do_default(self, var, val, cond=None): 284 val = self.value_mangler(val) 285 self.clauses.append(KconfigData.DefaultClause(var, val, cond)) 286 287 def do_depends_on(self, var, expr): 288 self.clauses.append(KconfigData.DependsOnClause(var, expr)) 289 290 def do_select(self, var, symbol, cond=None): 291 cond = (cond & var) if cond is not None else var 292 self.clauses.append(KconfigData.SelectClause(symbol, cond)) 293 294 def do_imply(self, var, symbol, cond=None): 295 # "config X imply Y [if COND]" is the same as 296 # "config Y default y if X [&& COND]" 297 cond = (cond & var) if cond is not None else var 298 self.do_default(symbol, True, cond) 299 300# ------------------------------------------- 301# KconfigParser implements a recursive descent parser for (simplified) 302# Kconfig syntax. 303# ------------------------------------------- 304 305# tokens table 306TOKENS = {} 307TOK_NONE = -1 308TOK_LPAREN = 0; TOKENS[TOK_LPAREN] = '"("'; 309TOK_RPAREN = 1; TOKENS[TOK_RPAREN] = '")"'; 310TOK_EQUAL = 2; TOKENS[TOK_EQUAL] = '"="'; 311TOK_AND = 3; TOKENS[TOK_AND] = '"&&"'; 312TOK_OR = 4; TOKENS[TOK_OR] = '"||"'; 313TOK_NOT = 5; TOKENS[TOK_NOT] = '"!"'; 314TOK_DEPENDS = 6; TOKENS[TOK_DEPENDS] = '"depends"'; 315TOK_ON = 7; TOKENS[TOK_ON] = '"on"'; 316TOK_SELECT = 8; TOKENS[TOK_SELECT] = '"select"'; 317TOK_IMPLY = 9; TOKENS[TOK_IMPLY] = '"imply"'; 318TOK_CONFIG = 10; TOKENS[TOK_CONFIG] = '"config"'; 319TOK_DEFAULT = 11; TOKENS[TOK_DEFAULT] = '"default"'; 320TOK_Y = 12; TOKENS[TOK_Y] = '"y"'; 321TOK_N = 13; TOKENS[TOK_N] = '"n"'; 322TOK_SOURCE = 14; TOKENS[TOK_SOURCE] = '"source"'; 323TOK_BOOL = 15; TOKENS[TOK_BOOL] = '"bool"'; 324TOK_IF = 16; TOKENS[TOK_IF] = '"if"'; 325TOK_ID = 17; TOKENS[TOK_ID] = 'identifier'; 326TOK_EOF = 18; TOKENS[TOK_EOF] = 'end of file'; 327 328class KconfigParserError(Exception): 329 def __init__(self, parser, msg, tok=None): 330 self.loc = parser.location() 331 tok = tok or parser.tok 332 if tok != TOK_NONE: 333 location = TOKENS.get(tok, None) or ('"%s"' % tok) 334 msg = '%s before %s' % (msg, location) 335 self.msg = msg 336 337 def __str__(self): 338 return "%s: %s" % (self.loc, self.msg) 339 340class KconfigParser: 341 342 @classmethod 343 def parse(self, fp, mode=None): 344 data = KconfigData(mode or KconfigParser.defconfig) 345 parser = KconfigParser(data) 346 parser.parse_file(fp) 347 return data 348 349 def __init__(self, data): 350 self.data = data 351 352 def parse_file(self, fp): 353 self.abs_fname = os.path.abspath(fp.name) 354 self.fname = fp.name 355 self.data.previously_included.append(self.abs_fname) 356 self.src = fp.read() 357 if self.src == '' or self.src[-1] != '\n': 358 self.src += '\n' 359 self.cursor = 0 360 self.line = 1 361 self.line_pos = 0 362 self.get_token() 363 self.parse_config() 364 365 def do_assignment(self, var, val): 366 if not var.startswith("CONFIG_"): 367 raise Error('assigned variable should start with CONFIG_') 368 var = self.data.do_var(var[7:]) 369 self.data.do_assignment(var, val) 370 371 # file management ----- 372 373 def error_path(self): 374 inf = self.data.incl_info 375 res = "" 376 while inf: 377 res = ("In file included from %s:%d:\n" % (inf['file'], 378 inf['line'])) + res 379 inf = inf['parent'] 380 return res 381 382 def location(self): 383 col = 1 384 for ch in self.src[self.line_pos:self.pos]: 385 if ch == '\t': 386 col += 8 - ((col - 1) % 8) 387 else: 388 col += 1 389 return '%s%s:%d:%d' %(self.error_path(), self.fname, self.line, col) 390 391 def do_include(self, include): 392 incl_abs_fname = os.path.join(os.path.dirname(self.abs_fname), 393 include) 394 # catch inclusion cycle 395 inf = self.data.incl_info 396 while inf: 397 if incl_abs_fname == os.path.abspath(inf['file']): 398 raise KconfigParserError(self, "Inclusion loop for %s" 399 % include) 400 inf = inf['parent'] 401 402 # skip multiple include of the same file 403 if incl_abs_fname in self.data.previously_included: 404 return 405 try: 406 fp = open(incl_abs_fname, 'r') 407 except IOError as e: 408 raise KconfigParserError(self, 409 '%s: %s' % (e.strerror, include)) 410 411 inf = self.data.incl_info 412 self.data.incl_info = { 'file': self.fname, 'line': self.line, 413 'parent': inf } 414 KconfigParser(self.data).parse_file(fp) 415 self.data.incl_info = inf 416 417 # recursive descent parser ----- 418 419 # y_or_n: Y | N 420 def parse_y_or_n(self): 421 if self.tok == TOK_Y: 422 self.get_token() 423 return True 424 if self.tok == TOK_N: 425 self.get_token() 426 return False 427 raise KconfigParserError(self, 'Expected "y" or "n"') 428 429 # var: ID 430 def parse_var(self): 431 if self.tok == TOK_ID: 432 val = self.val 433 self.get_token() 434 return self.data.do_var(val) 435 else: 436 raise KconfigParserError(self, 'Expected identifier') 437 438 # assignment_var: ID (starting with "CONFIG_") 439 def parse_assignment_var(self): 440 if self.tok == TOK_ID: 441 val = self.val 442 if not val.startswith("CONFIG_"): 443 raise KconfigParserError(self, 444 'Expected identifier starting with "CONFIG_"', TOK_NONE) 445 self.get_token() 446 return self.data.do_var(val[7:]) 447 else: 448 raise KconfigParserError(self, 'Expected identifier') 449 450 # assignment: var EQUAL y_or_n 451 def parse_assignment(self): 452 var = self.parse_assignment_var() 453 if self.tok != TOK_EQUAL: 454 raise KconfigParserError(self, 'Expected "="') 455 self.get_token() 456 self.data.do_assignment(var, self.parse_y_or_n()) 457 458 # primary: NOT primary 459 # | LPAREN expr RPAREN 460 # | var 461 def parse_primary(self): 462 if self.tok == TOK_NOT: 463 self.get_token() 464 val = ~self.parse_primary() 465 elif self.tok == TOK_LPAREN: 466 self.get_token() 467 val = self.parse_expr() 468 if self.tok != TOK_RPAREN: 469 raise KconfigParserError(self, 'Expected ")"') 470 self.get_token() 471 elif self.tok == TOK_ID: 472 val = self.parse_var() 473 else: 474 raise KconfigParserError(self, 'Expected "!" or "(" or identifier') 475 return val 476 477 # disj: primary (OR primary)* 478 def parse_disj(self): 479 lhs = self.parse_primary() 480 while self.tok == TOK_OR: 481 self.get_token() 482 lhs = lhs | self.parse_primary() 483 return lhs 484 485 # expr: disj (AND disj)* 486 def parse_expr(self): 487 lhs = self.parse_disj() 488 while self.tok == TOK_AND: 489 self.get_token() 490 lhs = lhs & self.parse_disj() 491 return lhs 492 493 # condition: IF expr 494 # | empty 495 def parse_condition(self): 496 if self.tok == TOK_IF: 497 self.get_token() 498 return self.parse_expr() 499 else: 500 return None 501 502 # property: DEFAULT y_or_n condition 503 # | DEPENDS ON expr 504 # | SELECT var condition 505 # | BOOL 506 def parse_property(self, var): 507 if self.tok == TOK_DEFAULT: 508 self.get_token() 509 val = self.parse_y_or_n() 510 cond = self.parse_condition() 511 self.data.do_default(var, val, cond) 512 elif self.tok == TOK_DEPENDS: 513 self.get_token() 514 if self.tok != TOK_ON: 515 raise KconfigParserError(self, 'Expected "on"') 516 self.get_token() 517 self.data.do_depends_on(var, self.parse_expr()) 518 elif self.tok == TOK_SELECT: 519 self.get_token() 520 symbol = self.parse_var() 521 cond = self.parse_condition() 522 self.data.do_select(var, symbol, cond) 523 elif self.tok == TOK_IMPLY: 524 self.get_token() 525 symbol = self.parse_var() 526 cond = self.parse_condition() 527 self.data.do_imply(var, symbol, cond) 528 elif self.tok == TOK_BOOL: 529 self.get_token() 530 else: 531 raise KconfigParserError(self, 'Error in recursive descent?') 532 533 # properties: properties property 534 # | /* empty */ 535 def parse_properties(self, var): 536 had_default = False 537 while self.tok == TOK_DEFAULT or self.tok == TOK_DEPENDS or \ 538 self.tok == TOK_SELECT or self.tok == TOK_BOOL or \ 539 self.tok == TOK_IMPLY: 540 self.parse_property(var) 541 542 # for nicer error message 543 if self.tok != TOK_SOURCE and self.tok != TOK_CONFIG and \ 544 self.tok != TOK_ID and self.tok != TOK_EOF: 545 raise KconfigParserError(self, 'expected "source", "config", identifier, ' 546 + '"default", "depends on", "imply" or "select"') 547 548 # declaration: config var properties 549 def parse_declaration(self): 550 if self.tok == TOK_CONFIG: 551 self.get_token() 552 var = self.parse_var() 553 self.data.do_declaration(var) 554 self.parse_properties(var) 555 else: 556 raise KconfigParserError(self, 'Error in recursive descent?') 557 558 # clause: SOURCE 559 # | declaration 560 # | assignment 561 def parse_clause(self): 562 if self.tok == TOK_SOURCE: 563 val = self.val 564 self.get_token() 565 self.do_include(val) 566 elif self.tok == TOK_CONFIG: 567 self.parse_declaration() 568 elif self.tok == TOK_ID: 569 self.parse_assignment() 570 else: 571 raise KconfigParserError(self, 'expected "source", "config" or identifier') 572 573 # config: clause+ EOF 574 def parse_config(self): 575 while self.tok != TOK_EOF: 576 self.parse_clause() 577 return self.data 578 579 # scanner ----- 580 581 def get_token(self): 582 while True: 583 self.tok = self.src[self.cursor] 584 self.pos = self.cursor 585 self.cursor += 1 586 587 self.val = None 588 self.tok = self.scan_token() 589 if self.tok is not None: 590 return 591 592 def check_keyword(self, rest): 593 if not self.src.startswith(rest, self.cursor): 594 return False 595 length = len(rest) 596 if self.src[self.cursor + length].isalnum() or self.src[self.cursor + length] == '_': 597 return False 598 self.cursor += length 599 return True 600 601 def scan_token(self): 602 if self.tok == '#': 603 self.cursor = self.src.find('\n', self.cursor) 604 return None 605 elif self.tok == '=': 606 return TOK_EQUAL 607 elif self.tok == '(': 608 return TOK_LPAREN 609 elif self.tok == ')': 610 return TOK_RPAREN 611 elif self.tok == '&' and self.src[self.pos+1] == '&': 612 self.cursor += 1 613 return TOK_AND 614 elif self.tok == '|' and self.src[self.pos+1] == '|': 615 self.cursor += 1 616 return TOK_OR 617 elif self.tok == '!': 618 return TOK_NOT 619 elif self.tok == 'd' and self.check_keyword("epends"): 620 return TOK_DEPENDS 621 elif self.tok == 'o' and self.check_keyword("n"): 622 return TOK_ON 623 elif self.tok == 's' and self.check_keyword("elect"): 624 return TOK_SELECT 625 elif self.tok == 'i' and self.check_keyword("mply"): 626 return TOK_IMPLY 627 elif self.tok == 'c' and self.check_keyword("onfig"): 628 return TOK_CONFIG 629 elif self.tok == 'd' and self.check_keyword("efault"): 630 return TOK_DEFAULT 631 elif self.tok == 'b' and self.check_keyword("ool"): 632 return TOK_BOOL 633 elif self.tok == 'i' and self.check_keyword("f"): 634 return TOK_IF 635 elif self.tok == 'y' and self.check_keyword(""): 636 return TOK_Y 637 elif self.tok == 'n' and self.check_keyword(""): 638 return TOK_N 639 elif (self.tok == 's' and self.check_keyword("ource")) or \ 640 self.tok == 'i' and self.check_keyword("nclude"): 641 # source FILENAME 642 # include FILENAME 643 while self.src[self.cursor].isspace(): 644 self.cursor += 1 645 start = self.cursor 646 self.cursor = self.src.find('\n', self.cursor) 647 self.val = self.src[start:self.cursor] 648 return TOK_SOURCE 649 elif self.tok.isalpha(): 650 # identifier 651 while self.src[self.cursor].isalnum() or self.src[self.cursor] == '_': 652 self.cursor += 1 653 self.val = self.src[self.pos:self.cursor] 654 return TOK_ID 655 elif self.tok == '\n': 656 if self.cursor == len(self.src): 657 return TOK_EOF 658 self.line += 1 659 self.line_pos = self.cursor 660 elif not self.tok.isspace(): 661 raise KconfigParserError(self, 'invalid input') 662 663 return None 664 665if __name__ == '__main__': 666 argv = sys.argv 667 mode = defconfig 668 if len(sys.argv) > 1: 669 if argv[1] == '--defconfig': 670 del argv[1] 671 elif argv[1] == '--randconfig': 672 random.seed() 673 mode = randconfig 674 del argv[1] 675 elif argv[1] == '--allyesconfig': 676 mode = allyesconfig 677 del argv[1] 678 elif argv[1] == '--allnoconfig': 679 mode = allnoconfig 680 del argv[1] 681 682 if len(argv) == 1: 683 print ("%s: at least one argument is required" % argv[0], file=sys.stderr) 684 sys.exit(1) 685 686 if argv[1].startswith('-'): 687 print ("%s: invalid option %s" % (argv[0], argv[1]), file=sys.stderr) 688 sys.exit(1) 689 690 data = KconfigData(mode) 691 parser = KconfigParser(data) 692 external_vars = set() 693 for arg in argv[3:]: 694 m = re.match(r'^(CONFIG_[A-Z0-9_]+)=([yn]?)$', arg) 695 if m is not None: 696 name, value = m.groups() 697 parser.do_assignment(name, value == 'y') 698 external_vars.add(name[7:]) 699 else: 700 fp = open(arg, 'r') 701 parser.parse_file(fp) 702 fp.close() 703 704 config = data.compute_config() 705 for key in sorted(config.keys()): 706 if key not in external_vars and config[key]: 707 print ('CONFIG_%s=y' % key) 708 709 deps = open(argv[2], 'w') 710 for fname in data.previously_included: 711 print ('%s: %s' % (argv[1], fname), file=deps) 712 deps.close() 713