4 # Copyright (c) 2015 Red Hat Inc.
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.
13 from __future__ import print_function
19 __all__ = [ 'KconfigDataError', 'KconfigParserError',
20 'KconfigData', 'KconfigParser' ,
21 'defconfig', 'allyesconfig', 'allnoconfig', 'randconfig' ]
23 def debug_print(*args):
24 #print('# ' + (' '.join(str(x) for x in args)))
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".
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
35 # -------------------------------------------
37 class KconfigDataError(Exception):
38 def __init__(self, msg):
44 allyesconfig = lambda x: True
45 allnoconfig = lambda x: False
46 defconfig = lambda x: x
47 randconfig = lambda x: random.randint(0, 1) == 1
51 def __and__(self, rhs):
52 return KconfigData.AND(self, rhs)
53 def __or__(self, rhs):
54 return KconfigData.OR(self, rhs)
56 return KconfigData.NOT(self)
59 def add_edges_to(self, var):
65 def __init__(self, lhs, rhs):
69 return "(%s && %s)" % (self.lhs, self.rhs)
71 def add_edges_to(self, var):
72 self.lhs.add_edges_to(var)
73 self.rhs.add_edges_to(var)
75 return self.lhs.evaluate() and self.rhs.evaluate()
78 def __init__(self, lhs, rhs):
82 return "(%s || %s)" % (self.lhs, self.rhs)
84 def add_edges_to(self, var):
85 self.lhs.add_edges_to(var)
86 self.rhs.add_edges_to(var)
88 return self.lhs.evaluate() or self.rhs.evaluate()
91 def __init__(self, lhs):
94 return "!%s" % (self.lhs)
96 def add_edges_to(self, var):
97 self.lhs.add_edges_to(var)
99 return not self.lhs.evaluate()
102 def __init__(self, name):
105 self.outgoing = set()
106 self.clauses_for_var = list()
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)
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))
122 # depth first search of the dependency graph
123 def dfs(self, visited, f):
127 for v in self.outgoing:
131 def add_edges_to(self, var):
132 self.outgoing.add(var)
134 if not self.has_value():
135 raise KconfigDataError('cycle found including %s' % self)
139 def __init__(self, dest):
146 class AssignmentClause(Clause):
147 def __init__(self, dest, value):
148 KconfigData.Clause.__init__(self, dest)
151 return "CONFIG_%s=%s" % (self.dest, 'y' if self.value else 'n')
154 self.dest.set_value(self.value, self)
156 class DefaultClause(Clause):
157 def __init__(self, dest, value, cond=None):
158 KconfigData.Clause.__init__(self, dest)
161 if not (self.cond is None):
162 self.cond.add_edges_to(self.dest)
164 value = 'y' if self.value else 'n'
165 if self.cond is None:
166 return "config %s default %s" % (self.dest, value)
168 return "config %s default %s if %s" % (self.dest, value, self.cond)
171 # Defaults are processed just before leaving the variable
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)
178 class DependsOnClause(Clause):
179 def __init__(self, dest, expr):
180 KconfigData.Clause.__init__(self, dest)
182 self.expr.add_edges_to(self.dest)
184 return "config %s depends on %s" % (self.dest, self.expr)
187 if not self.expr.evaluate():
188 self.dest.set_value(False, self)
190 class SelectClause(Clause):
191 def __init__(self, dest, cond):
192 KconfigData.Clause.__init__(self, dest)
194 self.cond.add_edges_to(self.dest)
196 return "select %s if %s" % (self.dest, self.cond)
199 if self.cond.evaluate():
200 self.dest.set_value(True, self)
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()
210 # semantic analysis -------------
212 def check_undefined(self):
214 for i in self.referenced_vars:
215 if not (i in self.defined_vars):
216 print("undefined symbol %s" % (i), file=sys.stderr)
220 def compute_config(self):
221 if self.check_undefined():
222 raise KconfigDataError("there were undefined symbols")
225 debug_print("Input:")
226 for clause in self.clauses:
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])
233 # The reverse of the depth-first order is the topological sort
238 debug_print(var, "has DFS number", len(dfo))
241 for name, v in self.referenced_vars.items():
242 self.do_default(v, False)
243 v.dfs(visited, visit_fn)
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()))
250 debug_print("\nSorted clauses:")
251 for clause in self.clauses:
257 for name, v in self.referenced_vars.items():
258 debug_print("Evaluating", name)
259 values[name] = v.evaluate()
263 # semantic actions -------------
265 def do_declaration(self, var):
266 if (var in self.defined_vars):
267 raise KconfigDataError('variable "' + var + '" defined twice')
269 self.defined_vars.add(var.name)
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]
276 var_obj = self.referenced_vars[var] = KconfigData.Var(var)
279 def do_assignment(self, var, val):
280 self.clauses.append(KconfigData.AssignmentClause(var, val))
282 def do_default(self, var, val, cond=None):
283 val = self.value_mangler(val)
284 self.clauses.append(KconfigData.DefaultClause(var, val, cond))
286 def do_depends_on(self, var, expr):
287 self.clauses.append(KconfigData.DependsOnClause(var, expr))
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))
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)
299 # -------------------------------------------
300 # KconfigParser implements a recursive descent parser for (simplified)
302 # -------------------------------------------
307 TOK_LPAREN = 0; TOKENS[TOK_LPAREN] = '"("';
308 TOK_RPAREN = 1; TOKENS[TOK_RPAREN] = '")"';
309 TOK_EQUAL = 2; TOKENS[TOK_EQUAL] = '"="';
310 TOK_AND = 3; TOKENS[TOK_AND] = '"&&"';
311 TOK_OR = 4; TOKENS[TOK_OR] = '"||"';
312 TOK_NOT = 5; TOKENS[TOK_NOT] = '"!"';
313 TOK_DEPENDS = 6; TOKENS[TOK_DEPENDS] = '"depends"';
314 TOK_ON = 7; TOKENS[TOK_ON] = '"on"';
315 TOK_SELECT = 8; TOKENS[TOK_SELECT] = '"select"';
316 TOK_IMPLY = 9; TOKENS[TOK_IMPLY] = '"imply"';
317 TOK_CONFIG = 10; TOKENS[TOK_CONFIG] = '"config"';
318 TOK_DEFAULT = 11; TOKENS[TOK_DEFAULT] = '"default"';
319 TOK_Y = 12; TOKENS[TOK_Y] = '"y"';
320 TOK_N = 13; TOKENS[TOK_N] = '"n"';
321 TOK_SOURCE = 14; TOKENS[TOK_SOURCE] = '"source"';
322 TOK_BOOL = 15; TOKENS[TOK_BOOL] = '"bool"';
323 TOK_IF = 16; TOKENS[TOK_IF] = '"if"';
324 TOK_ID = 17; TOKENS[TOK_ID] = 'identifier';
325 TOK_EOF = 18; TOKENS[TOK_EOF] = 'end of file';
327 class KconfigParserError(Exception):
328 def __init__(self, parser, msg, tok=None):
329 self.loc = parser.location()
330 tok = tok or parser.tok
332 location = TOKENS.get(tok, None) or ('"%s"' % tok)
333 msg = '%s before %s' % (msg, location)
337 return "%s: %s" % (self.loc, self.msg)
342 def parse(self, fp, mode=None):
343 data = KconfigData(mode or KconfigParser.defconfig)
344 parser = KconfigParser(data)
345 parser.parse_file(fp)
348 def __init__(self, data):
351 def parse_file(self, fp):
352 self.abs_fname = os.path.abspath(fp.name)
354 self.data.previously_included.append(self.abs_fname)
356 if self.src == '' or self.src[-1] != '\n':
364 def do_assignment(self, var, val):
365 if not var.startswith("CONFIG_"):
366 raise Error('assigned variable should start with CONFIG_')
367 var = self.data.do_var(var[7:])
368 self.data.do_assignment(var, val)
370 # file management -----
372 def error_path(self):
373 inf = self.data.incl_info
376 res = ("In file included from %s:%d:\n" % (inf['file'],
383 for ch in self.src[self.line_pos:self.pos]:
385 col += 8 - ((col - 1) % 8)
388 return '%s%s:%d:%d' %(self.error_path(), self.fname, self.line, col)
390 def do_include(self, include):
391 incl_abs_fname = os.path.join(os.path.dirname(self.abs_fname),
393 # catch inclusion cycle
394 inf = self.data.incl_info
396 if incl_abs_fname == os.path.abspath(inf['file']):
397 raise KconfigParserError(self, "Inclusion loop for %s"
401 # skip multiple include of the same file
402 if incl_abs_fname in self.data.previously_included:
405 fp = open(incl_abs_fname, 'r')
407 raise KconfigParserError(self,
408 '%s: %s' % (e.strerror, include))
410 inf = self.data.incl_info
411 self.data.incl_info = { 'file': self.fname, 'line': self.line,
413 KconfigParser(self.data).parse_file(fp)
414 self.data.incl_info = inf
416 # recursive descent parser -----
419 def parse_y_or_n(self):
420 if self.tok == TOK_Y:
423 if self.tok == TOK_N:
426 raise KconfigParserError(self, 'Expected "y" or "n"')
430 if self.tok == TOK_ID:
433 return self.data.do_var(val)
435 raise KconfigParserError(self, 'Expected identifier')
437 # assignment_var: ID (starting with "CONFIG_")
438 def parse_assignment_var(self):
439 if self.tok == TOK_ID:
441 if not val.startswith("CONFIG_"):
442 raise KconfigParserError(self,
443 'Expected identifier starting with "CONFIG_"', TOK_NONE)
445 return self.data.do_var(val[7:])
447 raise KconfigParserError(self, 'Expected identifier')
449 # assignment: var EQUAL y_or_n
450 def parse_assignment(self):
451 var = self.parse_assignment_var()
452 if self.tok != TOK_EQUAL:
453 raise KconfigParserError(self, 'Expected "="')
455 self.data.do_assignment(var, self.parse_y_or_n())
457 # primary: NOT primary
458 # | LPAREN expr RPAREN
460 def parse_primary(self):
461 if self.tok == TOK_NOT:
463 val = ~self.parse_primary()
464 elif self.tok == TOK_LPAREN:
466 val = self.parse_expr()
467 if self.tok != TOK_RPAREN:
468 raise KconfigParserError(self, 'Expected ")"')
470 elif self.tok == TOK_ID:
471 val = self.parse_var()
473 raise KconfigParserError(self, 'Expected "!" or "(" or identifier')
476 # disj: primary (OR primary)*
477 def parse_disj(self):
478 lhs = self.parse_primary()
479 while self.tok == TOK_OR:
481 lhs = lhs | self.parse_primary()
484 # expr: disj (AND disj)*
485 def parse_expr(self):
486 lhs = self.parse_disj()
487 while self.tok == TOK_AND:
489 lhs = lhs & self.parse_disj()
494 def parse_condition(self):
495 if self.tok == TOK_IF:
497 return self.parse_expr()
501 # property: DEFAULT y_or_n condition
503 # | SELECT var condition
505 def parse_property(self, var):
506 if self.tok == TOK_DEFAULT:
508 val = self.parse_y_or_n()
509 cond = self.parse_condition()
510 self.data.do_default(var, val, cond)
511 elif self.tok == TOK_DEPENDS:
513 if self.tok != TOK_ON:
514 raise KconfigParserError(self, 'Expected "on"')
516 self.data.do_depends_on(var, self.parse_expr())
517 elif self.tok == TOK_SELECT:
519 symbol = self.parse_var()
520 cond = self.parse_condition()
521 self.data.do_select(var, symbol, cond)
522 elif self.tok == TOK_IMPLY:
524 symbol = self.parse_var()
525 cond = self.parse_condition()
526 self.data.do_imply(var, symbol, cond)
527 elif self.tok == TOK_BOOL:
530 raise KconfigParserError(self, 'Error in recursive descent?')
532 # properties: properties property
534 def parse_properties(self, var):
536 while self.tok == TOK_DEFAULT or self.tok == TOK_DEPENDS or \
537 self.tok == TOK_SELECT or self.tok == TOK_BOOL or \
538 self.tok == TOK_IMPLY:
539 self.parse_property(var)
541 # for nicer error message
542 if self.tok != TOK_SOURCE and self.tok != TOK_CONFIG and \
543 self.tok != TOK_ID and self.tok != TOK_EOF:
544 raise KconfigParserError(self, 'expected "source", "config", identifier, '
545 + '"default", "depends on", "imply" or "select"')
547 # declaration: config var properties
548 def parse_declaration(self):
549 if self.tok == TOK_CONFIG:
551 var = self.parse_var()
552 self.data.do_declaration(var)
553 self.parse_properties(var)
555 raise KconfigParserError(self, 'Error in recursive descent?')
560 def parse_clause(self):
561 if self.tok == TOK_SOURCE:
565 elif self.tok == TOK_CONFIG:
566 self.parse_declaration()
567 elif self.tok == TOK_ID:
568 self.parse_assignment()
570 raise KconfigParserError(self, 'expected "source", "config" or identifier')
572 # config: clause+ EOF
573 def parse_config(self):
574 while self.tok != TOK_EOF:
582 self.tok = self.src[self.cursor]
583 self.pos = self.cursor
587 self.tok = self.scan_token()
588 if self.tok is not None:
591 def check_keyword(self, rest):
592 if not self.src.startswith(rest, self.cursor):
595 if self.src[self.cursor + length].isalnum() or self.src[self.cursor + length] == '_':
597 self.cursor += length
600 def scan_token(self):
602 self.cursor = self.src.find('\n', self.cursor)
604 elif self.tok == '=':
606 elif self.tok == '(':
608 elif self.tok == ')':
610 elif self.tok == '&' and self.src[self.pos+1] == '&':
613 elif self.tok == '|' and self.src[self.pos+1] == '|':
616 elif self.tok == '!':
618 elif self.tok == 'd' and self.check_keyword("epends"):
620 elif self.tok == 'o' and self.check_keyword("n"):
622 elif self.tok == 's' and self.check_keyword("elect"):
624 elif self.tok == 'i' and self.check_keyword("mply"):
626 elif self.tok == 'c' and self.check_keyword("onfig"):
628 elif self.tok == 'd' and self.check_keyword("efault"):
630 elif self.tok == 'b' and self.check_keyword("ool"):
632 elif self.tok == 'i' and self.check_keyword("f"):
634 elif self.tok == 'y' and self.check_keyword(""):
636 elif self.tok == 'n' and self.check_keyword(""):
638 elif (self.tok == 's' and self.check_keyword("ource")) or \
639 self.tok == 'i' and self.check_keyword("nclude"):
642 while self.src[self.cursor].isspace():
645 self.cursor = self.src.find('\n', self.cursor)
646 self.val = self.src[start:self.cursor]
648 elif self.tok.isalpha():
650 while self.src[self.cursor].isalnum() or self.src[self.cursor] == '_':
652 self.val = self.src[self.pos:self.cursor]
654 elif self.tok == '\n':
655 if self.cursor == len(self.src):
658 self.line_pos = self.cursor
659 elif not self.tok.isspace():
660 raise KconfigParserError(self, 'invalid input')
664 if __name__ == '__main__':
667 if len(sys.argv) > 1:
668 if argv[1] == '--defconfig':
670 elif argv[1] == '--randconfig':
674 elif argv[1] == '--allyesconfig':
677 elif argv[1] == '--allnoconfig':
682 print ("%s: at least one argument is required" % argv[0], file=sys.stderr)
685 if argv[1].startswith('-'):
686 print ("%s: invalid option %s" % (argv[0], argv[1]), file=sys.stderr)
689 data = KconfigData(mode)
690 parser = KconfigParser(data)
692 m = re.match(r'^(CONFIG_[A-Z0-9_]+)=([yn]?)$', arg)
694 name, value = m.groups()
695 parser.do_assignment(name, value == 'y')
698 parser.parse_file(fp)
701 config = data.compute_config()
702 for key in sorted(config.keys()):
703 print ('CONFIG_%s=%s' % (key, ('y' if config[key] else 'n')))
705 deps = open(argv[2], 'w')
706 for fname in data.previously_included:
707 print ('%s: %s' % (argv[1], fname), file=deps)