scripts/minikconf.py

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