fuzz: use qemu_get_exec_dir
[qemu.git] / scripts / minikconf.py
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
14 import os
15 import sys
16 import re
17 import random
18
19 __all__ = [ 'KconfigDataError', 'KconfigParserError',
20 'KconfigData', 'KconfigParser' ,
21 'defconfig', 'allyesconfig', 'allnoconfig', 'randconfig' ]
22
23 def 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
37 class KconfigDataError(Exception):
38 def __init__(self, msg):
39 self.msg = msg
40
41 def __str__(self):
42 return self.msg
43
44 allyesconfig = lambda x: True
45 allnoconfig = lambda x: False
46 defconfig = lambda x: x
47 randconfig = lambda x: random.randint(0, 1) == 1
48
49 class 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)
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
305 TOKENS = {}
306 TOK_NONE = -1
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';
326
327 class 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
339 class KconfigParser:
340
341 @classmethod
342 def parse(self, fp, mode=None):
343 data = KconfigData(mode or KconfigParser.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 Error('assigned variable should start with CONFIG_')
367 var = self.data.do_var(var[7:])
368 self.data.do_assignment(var, val)
369
370 # file management -----
371
372 def error_path(self):
373 inf = self.data.incl_info
374 res = ""
375 while inf:
376 res = ("In file included from %s:%d:\n" % (inf['file'],
377 inf['line'])) + res
378 inf = inf['parent']
379 return res
380
381 def location(self):
382 col = 1
383 for ch in self.src[self.line_pos:self.pos]:
384 if ch == '\t':
385 col += 8 - ((col - 1) % 8)
386 else:
387 col += 1
388 return '%s%s:%d:%d' %(self.error_path(), self.fname, self.line, col)
389
390 def do_include(self, include):
391 incl_abs_fname = os.path.join(os.path.dirname(self.abs_fname),
392 include)
393 # catch inclusion cycle
394 inf = self.data.incl_info
395 while inf:
396 if incl_abs_fname == os.path.abspath(inf['file']):
397 raise KconfigParserError(self, "Inclusion loop for %s"
398 % include)
399 inf = inf['parent']
400
401 # skip multiple include of the same file
402 if incl_abs_fname in self.data.previously_included:
403 return
404 try:
405 fp = open(incl_abs_fname, 'rt', encoding='utf-8')
406 except IOError as e:
407 raise KconfigParserError(self,
408 '%s: %s' % (e.strerror, include))
409
410 inf = self.data.incl_info
411 self.data.incl_info = { 'file': self.fname, 'line': self.line,
412 'parent': inf }
413 KconfigParser(self.data).parse_file(fp)
414 self.data.incl_info = inf
415
416 # recursive descent parser -----
417
418 # y_or_n: Y | N
419 def parse_y_or_n(self):
420 if self.tok == TOK_Y:
421 self.get_token()
422 return True
423 if self.tok == TOK_N:
424 self.get_token()
425 return False
426 raise KconfigParserError(self, 'Expected "y" or "n"')
427
428 # var: ID
429 def parse_var(self):
430 if self.tok == TOK_ID:
431 val = self.val
432 self.get_token()
433 return self.data.do_var(val)
434 else:
435 raise KconfigParserError(self, 'Expected identifier')
436
437 # assignment_var: ID (starting with "CONFIG_")
438 def parse_assignment_var(self):
439 if self.tok == TOK_ID:
440 val = self.val
441 if not val.startswith("CONFIG_"):
442 raise KconfigParserError(self,
443 'Expected identifier starting with "CONFIG_"', TOK_NONE)
444 self.get_token()
445 return self.data.do_var(val[7:])
446 else:
447 raise KconfigParserError(self, 'Expected identifier')
448
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 "="')
454 self.get_token()
455 self.data.do_assignment(var, self.parse_y_or_n())
456
457 # primary: NOT primary
458 # | LPAREN expr RPAREN
459 # | var
460 def parse_primary(self):
461 if self.tok == TOK_NOT:
462 self.get_token()
463 val = ~self.parse_primary()
464 elif self.tok == TOK_LPAREN:
465 self.get_token()
466 val = self.parse_expr()
467 if self.tok != TOK_RPAREN:
468 raise KconfigParserError(self, 'Expected ")"')
469 self.get_token()
470 elif self.tok == TOK_ID:
471 val = self.parse_var()
472 else:
473 raise KconfigParserError(self, 'Expected "!" or "(" or identifier')
474 return val
475
476 # disj: primary (OR primary)*
477 def parse_disj(self):
478 lhs = self.parse_primary()
479 while self.tok == TOK_OR:
480 self.get_token()
481 lhs = lhs | self.parse_primary()
482 return lhs
483
484 # expr: disj (AND disj)*
485 def parse_expr(self):
486 lhs = self.parse_disj()
487 while self.tok == TOK_AND:
488 self.get_token()
489 lhs = lhs & self.parse_disj()
490 return lhs
491
492 # condition: IF expr
493 # | empty
494 def parse_condition(self):
495 if self.tok == TOK_IF:
496 self.get_token()
497 return self.parse_expr()
498 else:
499 return None
500
501 # property: DEFAULT y_or_n condition
502 # | DEPENDS ON expr
503 # | SELECT var condition
504 # | BOOL
505 def parse_property(self, var):
506 if self.tok == TOK_DEFAULT:
507 self.get_token()
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:
512 self.get_token()
513 if self.tok != TOK_ON:
514 raise KconfigParserError(self, 'Expected "on"')
515 self.get_token()
516 self.data.do_depends_on(var, self.parse_expr())
517 elif self.tok == TOK_SELECT:
518 self.get_token()
519 symbol = self.parse_var()
520 cond = self.parse_condition()
521 self.data.do_select(var, symbol, cond)
522 elif self.tok == TOK_IMPLY:
523 self.get_token()
524 symbol = self.parse_var()
525 cond = self.parse_condition()
526 self.data.do_imply(var, symbol, cond)
527 elif self.tok == TOK_BOOL:
528 self.get_token()
529 else:
530 raise KconfigParserError(self, 'Error in recursive descent?')
531
532 # properties: properties property
533 # | /* empty */
534 def parse_properties(self, var):
535 had_default = False
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)
540
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"')
546
547 # declaration: config var properties
548 def parse_declaration(self):
549 if self.tok == TOK_CONFIG:
550 self.get_token()
551 var = self.parse_var()
552 self.data.do_declaration(var)
553 self.parse_properties(var)
554 else:
555 raise KconfigParserError(self, 'Error in recursive descent?')
556
557 # clause: SOURCE
558 # | declaration
559 # | assignment
560 def parse_clause(self):
561 if self.tok == TOK_SOURCE:
562 val = self.val
563 self.get_token()
564 self.do_include(val)
565 elif self.tok == TOK_CONFIG:
566 self.parse_declaration()
567 elif self.tok == TOK_ID:
568 self.parse_assignment()
569 else:
570 raise KconfigParserError(self, 'expected "source", "config" or identifier')
571
572 # config: clause+ EOF
573 def parse_config(self):
574 while self.tok != TOK_EOF:
575 self.parse_clause()
576 return self.data
577
578 # scanner -----
579
580 def get_token(self):
581 while True:
582 self.tok = self.src[self.cursor]
583 self.pos = self.cursor
584 self.cursor += 1
585
586 self.val = None
587 self.tok = self.scan_token()
588 if self.tok is not None:
589 return
590
591 def check_keyword(self, rest):
592 if not self.src.startswith(rest, self.cursor):
593 return False
594 length = len(rest)
595 if self.src[self.cursor + length].isalnum() or self.src[self.cursor + length] == '_':
596 return False
597 self.cursor += length
598 return True
599
600 def scan_token(self):
601 if self.tok == '#':
602 self.cursor = self.src.find('\n', self.cursor)
603 return None
604 elif self.tok == '=':
605 return TOK_EQUAL
606 elif self.tok == '(':
607 return TOK_LPAREN
608 elif self.tok == ')':
609 return TOK_RPAREN
610 elif self.tok == '&' and self.src[self.pos+1] == '&':
611 self.cursor += 1
612 return TOK_AND
613 elif self.tok == '|' and self.src[self.pos+1] == '|':
614 self.cursor += 1
615 return TOK_OR
616 elif self.tok == '!':
617 return TOK_NOT
618 elif self.tok == 'd' and self.check_keyword("epends"):
619 return TOK_DEPENDS
620 elif self.tok == 'o' and self.check_keyword("n"):
621 return TOK_ON
622 elif self.tok == 's' and self.check_keyword("elect"):
623 return TOK_SELECT
624 elif self.tok == 'i' and self.check_keyword("mply"):
625 return TOK_IMPLY
626 elif self.tok == 'c' and self.check_keyword("onfig"):
627 return TOK_CONFIG
628 elif self.tok == 'd' and self.check_keyword("efault"):
629 return TOK_DEFAULT
630 elif self.tok == 'b' and self.check_keyword("ool"):
631 return TOK_BOOL
632 elif self.tok == 'i' and self.check_keyword("f"):
633 return TOK_IF
634 elif self.tok == 'y' and self.check_keyword(""):
635 return TOK_Y
636 elif self.tok == 'n' and self.check_keyword(""):
637 return TOK_N
638 elif (self.tok == 's' and self.check_keyword("ource")) or \
639 self.tok == 'i' and self.check_keyword("nclude"):
640 # source FILENAME
641 # include FILENAME
642 while self.src[self.cursor].isspace():
643 self.cursor += 1
644 start = self.cursor
645 self.cursor = self.src.find('\n', self.cursor)
646 self.val = self.src[start:self.cursor]
647 return TOK_SOURCE
648 elif self.tok.isalnum():
649 # identifier
650 while self.src[self.cursor].isalnum() or self.src[self.cursor] == '_':
651 self.cursor += 1
652 self.val = self.src[self.pos:self.cursor]
653 return TOK_ID
654 elif self.tok == '\n':
655 if self.cursor == len(self.src):
656 return TOK_EOF
657 self.line += 1
658 self.line_pos = self.cursor
659 elif not self.tok.isspace():
660 raise KconfigParserError(self, 'invalid input')
661
662 return None
663
664 if __name__ == '__main__':
665 argv = sys.argv
666 mode = defconfig
667 if len(sys.argv) > 1:
668 if argv[1] == '--defconfig':
669 del argv[1]
670 elif argv[1] == '--randconfig':
671 random.seed()
672 mode = randconfig
673 del argv[1]
674 elif argv[1] == '--allyesconfig':
675 mode = allyesconfig
676 del argv[1]
677 elif argv[1] == '--allnoconfig':
678 mode = allnoconfig
679 del argv[1]
680
681 if len(argv) == 1:
682 print ("%s: at least one argument is required" % argv[0], file=sys.stderr)
683 sys.exit(1)
684
685 if argv[1].startswith('-'):
686 print ("%s: invalid option %s" % (argv[0], argv[1]), file=sys.stderr)
687 sys.exit(1)
688
689 data = KconfigData(mode)
690 parser = KconfigParser(data)
691 external_vars = set()
692 for arg in argv[3:]:
693 m = re.match(r'^(CONFIG_[A-Z0-9_]+)=([yn]?)$', arg)
694 if m is not None:
695 name, value = m.groups()
696 parser.do_assignment(name, value == 'y')
697 external_vars.add(name[7:])
698 else:
699 fp = open(arg, 'rt', encoding='utf-8')
700 parser.parse_file(fp)
701 fp.close()
702
703 config = data.compute_config()
704 for key in sorted(config.keys()):
705 if key not in external_vars and config[key]:
706 print ('CONFIG_%s=y' % key)
707
708 deps = open(argv[2], 'wt', encoding='utf-8')
709 for fname in data.previously_included:
710 print ('%s: %s' % (argv[1], fname), file=deps)
711 deps.close()