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