4 # Copyright (c) 2015 Red Hat Inc.
7 # Paolo Bonzini <pbonzini@redhat.com>
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
)
691 external_vars
= set()
693 m
= re
.match(r
'^(CONFIG_[A-Z0-9_]+)=([yn]?)$', arg
)
695 name
, value
= m
.groups()
696 parser
.do_assignment(name
, value
== 'y')
697 external_vars
.add(name
[7:])
700 parser
.parse_file(fp
)
703 config
= data
.compute_config()
704 for key
in sorted(config
.keys()):
705 if key
not in external_vars
:
706 print ('CONFIG_%s=%s' % (key
, ('y' if config
[key
] else 'n')))
708 deps
= open(argv
[2], 'w')
709 for fname
in data
.previously_included
:
710 print ('%s: %s' % (argv
[1], fname
), file=deps
)