xref: /qemu/scripts/minikconf.py (revision 138ca49a) 
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)
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 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
664if __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()
712