Merge git://git.denx.de/u-boot-fsl-qoriq
[oweals/u-boot.git] / tools / buildman / kconfiglib.py
1 #
2 # SPDX-License-Identifier:      ISC
3 #
4 # Author: Ulf Magnusson
5 #   https://github.com/ulfalizer/Kconfiglib
6
7 # This is Kconfiglib, a Python library for scripting, debugging, and extracting
8 # information from Kconfig-based configuration systems. To view the
9 # documentation, run
10 #
11 #  $ pydoc kconfiglib
12 #
13 # or, if you prefer HTML,
14 #
15 #  $ pydoc -w kconfiglib
16 #
17 # The examples/ subdirectory contains examples, to be run with e.g.
18 #
19 #  $ make scriptconfig SCRIPT=Kconfiglib/examples/print_tree.py
20 #
21 # Look in testsuite.py for the test suite.
22
23 """
24 Kconfiglib is a Python library for scripting and extracting information from
25 Kconfig-based configuration systems. Features include the following:
26
27  - Symbol values and properties can be looked up and values assigned
28    programmatically.
29  - .config files can be read and written.
30  - Expressions can be evaluated in the context of a Kconfig configuration.
31  - Relations between symbols can be quickly determined, such as finding all
32    symbols that reference a particular symbol.
33  - Highly compatible with the scripts/kconfig/*conf utilities. The test suite
34    automatically compares outputs between Kconfiglib and the C implementation
35    for a large number of cases.
36
37 For the Linux kernel, scripts are run using
38
39  $ make scriptconfig [ARCH=<arch>] SCRIPT=<path to script> [SCRIPT_ARG=<arg>]
40
41 Using the 'scriptconfig' target ensures that required environment variables
42 (SRCARCH, ARCH, srctree, KERNELVERSION, etc.) are set up correctly.
43
44 Scripts receive the name of the Kconfig file to load in sys.argv[1]. As of
45 Linux 4.1.0-rc5, this is always "Kconfig" from the kernel top-level directory.
46 If an argument is provided with SCRIPT_ARG, it appears as sys.argv[2].
47
48 To get an interactive Python prompt with Kconfiglib preloaded and a Config
49 object 'c' created, run
50
51  $ make iscriptconfig [ARCH=<arch>]
52
53 Kconfiglib supports both Python 2 and Python 3. For (i)scriptconfig, the Python
54 interpreter to use can be passed in PYTHONCMD, which defaults to 'python'. PyPy
55 works well too, and might give a nice speedup for long-running jobs.
56
57 The examples/ directory contains short example scripts, which can be run with
58 e.g.
59
60  $ make scriptconfig SCRIPT=Kconfiglib/examples/print_tree.py
61
62 or
63
64  $ make scriptconfig SCRIPT=Kconfiglib/examples/help_grep.py SCRIPT_ARG=kernel
65
66 testsuite.py contains the test suite. See the top of the script for how to run
67 it.
68
69 Credits: Written by Ulf "Ulfalizer" Magnusson
70
71 Send bug reports, suggestions and other feedback to ulfalizer a.t Google's
72 email service. Don't wrestle with internal APIs. Tell me what you need and I
73 might add it in a safe way as a client API instead."""
74
75 import os
76 import re
77 import sys
78
79 # File layout:
80 #
81 # Public classes
82 # Public functions
83 # Internal classes
84 # Internal functions
85 # Internal global constants
86
87 # Line length: 79 columns
88
89 #
90 # Public classes
91 #
92
93 class Config(object):
94
95     """Represents a Kconfig configuration, e.g. for i386 or ARM. This is the
96     set of symbols and other items appearing in the configuration together with
97     their values. Creating any number of Config objects -- including for
98     different architectures -- is safe; Kconfiglib has no global state."""
99
100     #
101     # Public interface
102     #
103
104     def __init__(self, filename="Kconfig", base_dir=None, print_warnings=True,
105                  print_undef_assign=False):
106         """Creates a new Config object, representing a Kconfig configuration.
107         Raises Kconfig_Syntax_Error on syntax errors.
108
109         filename (default: "Kconfig"): The base Kconfig file of the
110            configuration. For the Linux kernel, you'll probably want "Kconfig"
111            from the top-level directory, as environment variables will make
112            sure the right Kconfig is included from there
113            (arch/<architecture>/Kconfig). If you are using Kconfiglib via 'make
114            scriptconfig', the filename of the base base Kconfig file will be in
115            sys.argv[1].
116
117         base_dir (default: None): The base directory relative to which 'source'
118            statements within Kconfig files will work. For the Linux kernel this
119            should be the top-level directory of the kernel tree. $-references
120            to existing environment variables will be expanded.
121
122            If None (the default), the environment variable 'srctree' will be
123            used if set, and the current directory otherwise. 'srctree' is set
124            by the Linux makefiles to the top-level kernel directory. A default
125            of "." would not work with an alternative build directory.
126
127         print_warnings (default: True): Set to True if warnings related to this
128            configuration should be printed to stderr. This can be changed later
129            with Config.set_print_warnings(). It is provided as a constructor
130            argument since warnings might be generated during parsing.
131
132         print_undef_assign (default: False): Set to True if informational
133            messages related to assignments to undefined symbols should be
134            printed to stderr for this configuration. Can be changed later with
135            Config.set_print_undef_assign()."""
136
137         # The set of all symbols, indexed by name (a string)
138         self.syms = {}
139         # Python 2/3 compatibility hack. This is the only one needed.
140         if sys.version_info[0] >= 3:
141             self.syms_iter = self.syms.values
142         else:
143             self.syms_iter = self.syms.itervalues
144
145         # The set of all defined symbols in the configuration in the order they
146         # appear in the Kconfig files. This excludes the special symbols n, m,
147         # and y as well as symbols that are referenced but never defined.
148         self.kconfig_syms = []
149
150         # The set of all named choices (yes, choices can have names), indexed
151         # by name (a string)
152         self.named_choices = {}
153
154         # Lists containing all choices, menus and comments in the configuration
155         self.choices = []
156         self.menus = []
157         self.comments = []
158
159         def register_special_symbol(type_, name, val):
160             sym = Symbol()
161             sym.is_special_ = True
162             sym.is_defined_ = True
163             sym.config = self
164             sym.name = name
165             sym.type = type_
166             sym.cached_val = val
167             self.syms[name] = sym
168             return sym
169
170         # The special symbols n, m and y, used as shorthand for "n", "m" and
171         # "y"
172         self.n = register_special_symbol(TRISTATE, "n", "n")
173         self.m = register_special_symbol(TRISTATE, "m", "m")
174         self.y = register_special_symbol(TRISTATE, "y", "y")
175         # DEFCONFIG_LIST uses this
176         register_special_symbol(STRING, "UNAME_RELEASE", os.uname()[2])
177
178         # The symbol with "option defconfig_list" set, containing a list of
179         # default .config files
180         self.defconfig_sym = None
181
182         # See Symbol.get_(src)arch()
183         self.arch = os.environ.get("ARCH")
184         self.srcarch = os.environ.get("SRCARCH")
185
186         # See Config.__init__(). We need this for get_defconfig_filename().
187         self.srctree = os.environ.get("srctree")
188         if self.srctree is None:
189             self.srctree = "."
190
191         self.filename = filename
192         if base_dir is None:
193             self.base_dir = self.srctree
194         else:
195             self.base_dir = os.path.expandvars(base_dir)
196
197         # The 'mainmenu' text
198         self.mainmenu_text = None
199
200         # The filename of the most recently loaded .config file
201         self.config_filename = None
202         # The textual header of the most recently loaded .config, uncommented
203         self.config_header = None
204
205         self.print_warnings = print_warnings
206         self.print_undef_assign = print_undef_assign
207         self._warnings = []
208
209         # For parsing routines that stop when finding a line belonging to a
210         # different construct, these holds that line and the tokenized version
211         # of that line. The purpose is to avoid having to re-tokenize the line,
212         # which is inefficient and causes problems when recording references to
213         # symbols.
214         self.end_line = None
215         self.end_line_tokens = None
216
217         # See the comment in _parse_expr().
218         self._cur_item = None
219         self._line = None
220         self._filename = None
221         self._linenr = None
222         self._transform_m = None
223
224         # Parse the Kconfig files
225         self.top_block = self._parse_file(filename, None, None, None)
226
227         # Build Symbol.dep for all symbols
228         self._build_dep()
229
230     def get_arch(self):
231         """Returns the value the environment variable ARCH had at the time the
232         Config instance was created, or None if ARCH was not set. For the
233         kernel, this corresponds to the architecture being built for, with
234         values such as "i386" or "mips"."""
235         return self.arch
236
237     def get_srcarch(self):
238         """Returns the value the environment variable SRCARCH had at the time
239         the Config instance was created, or None if SRCARCH was not set. For
240         the kernel, this corresponds to the particular arch/ subdirectory
241         containing architecture-specific code."""
242         return self.srcarch
243
244     def get_srctree(self):
245         """Returns the value the environment variable srctree had at the time
246         the Config instance was created, or None if srctree was not defined.
247         This variable points to the source directory and is used when building
248         in a separate directory."""
249         return self.srctree
250
251     def get_base_dir(self):
252         """Returns the base directory relative to which 'source' statements
253         will work, passed as an argument to Config.__init__()."""
254         return self.base_dir
255
256     def get_kconfig_filename(self):
257         """Returns the name of the (base) kconfig file this configuration was
258         loaded from."""
259         return self.filename
260
261     def get_config_filename(self):
262         """Returns the filename of the most recently loaded configuration file,
263         or None if no configuration has been loaded."""
264         return self.config_filename
265
266     def get_config_header(self):
267         """Returns the (uncommented) textual header of the .config file most
268         recently loaded with load_config(). Returns None if no .config file has
269         been loaded or if the most recently loaded .config file has no header.
270         The header consists of all lines up to but not including the first line
271         that either
272
273         1. Does not start with "#"
274         2. Has the form "# CONFIG_FOO is not set."
275         """
276         return self.config_header
277
278     def get_mainmenu_text(self):
279         """Returns the text of the 'mainmenu' statement (with $-references to
280         symbols replaced by symbol values), or None if the configuration has no
281         'mainmenu' statement."""
282         return None if self.mainmenu_text is None else \
283           self._expand_sym_refs(self.mainmenu_text)
284
285     def get_defconfig_filename(self):
286         """Returns the name of the defconfig file, which is the first existing
287         file in the list given in a symbol having 'option defconfig_list' set.
288         $-references to symbols will be expanded ("$FOO bar" -> "foo bar" if
289         FOO has the value "foo"). Returns None in case of no defconfig file.
290         Setting 'option defconfig_list' on multiple symbols currently results
291         in undefined behavior.
292
293         If the environment variable 'srctree' was set when the Config was
294         created, get_defconfig_filename() will first look relative to that
295         directory before looking in the current directory; see
296         Config.__init__().
297
298         WARNING: A wart here is that scripts/kconfig/Makefile sometimes uses
299         the --defconfig=<defconfig> option when calling the C implementation of
300         e.g. 'make defconfig'. This option overrides the 'option
301         defconfig_list' symbol, meaning the result from
302         get_defconfig_filename() might not match what 'make defconfig' would
303         use. That probably ought to be worked around somehow, so that this
304         function always gives the "expected" result."""
305         if self.defconfig_sym is None:
306             return None
307         for filename, cond_expr in self.defconfig_sym.def_exprs:
308             if self._eval_expr(cond_expr) == "y":
309                 filename = self._expand_sym_refs(filename)
310                 # We first look in $srctree. os.path.join() won't work here as
311                 # an absolute path in filename would override $srctree.
312                 srctree_filename = os.path.normpath(self.srctree + "/" +
313                                                     filename)
314                 if os.path.exists(srctree_filename):
315                     return srctree_filename
316                 if os.path.exists(filename):
317                     return filename
318         return None
319
320     def get_symbol(self, name):
321         """Returns the symbol with name 'name', or None if no such symbol
322         appears in the configuration. An alternative shorthand is conf[name],
323         where conf is a Config instance, though that will instead raise
324         KeyError if the symbol does not exist."""
325         return self.syms.get(name)
326
327     def __getitem__(self, name):
328         """Returns the symbol with name 'name'. Raises KeyError if the symbol
329         does not appear in the configuration."""
330         return self.syms[name]
331
332     def get_symbols(self, all_symbols=True):
333         """Returns a list of symbols from the configuration. An alternative for
334         iterating over all defined symbols (in the order of definition) is
335
336         for sym in config:
337             ...
338
339         which relies on Config implementing __iter__() and is equivalent to
340
341         for sym in config.get_symbols(False):
342             ...
343
344         all_symbols (default: True): If True, all symbols -- including special
345            and undefined symbols -- will be included in the result, in an
346            undefined order. If False, only symbols actually defined and not
347            merely referred to in the configuration will be included in the
348            result, and will appear in the order that they are defined within
349            the Kconfig configuration files."""
350         return list(self.syms.values()) if all_symbols else self.kconfig_syms
351
352     def __iter__(self):
353         """Convenience function for iterating over the set of all defined
354         symbols in the configuration, used like
355
356         for sym in conf:
357             ...
358
359         The iteration happens in the order of definition within the Kconfig
360         configuration files. Symbols only referred to but not defined will not
361         be included, nor will the special symbols n, m, and y. If you want to
362         include such symbols as well, see config.get_symbols()."""
363         return iter(self.kconfig_syms)
364
365     def get_choices(self):
366         """Returns a list containing all choice statements in the
367         configuration, in the order they appear in the Kconfig files."""
368         return self.choices
369
370     def get_menus(self):
371         """Returns a list containing all menus in the configuration, in the
372         order they appear in the Kconfig files."""
373         return self.menus
374
375     def get_comments(self):
376         """Returns a list containing all comments in the configuration, in the
377         order they appear in the Kconfig files."""
378         return self.comments
379
380     def get_top_level_items(self):
381         """Returns a list containing the items (symbols, menus, choices, and
382         comments) at the top level of the configuration -- that is, all items
383         that do not appear within a menu or choice. The items appear in the
384         same order as within the configuration."""
385         return self.top_block
386
387     def load_config(self, filename, replace=True):
388         """Loads symbol values from a file in the familiar .config format.
389         Equivalent to calling Symbol.set_user_value() to set each of the
390         values.
391
392         "# CONFIG_FOO is not set" within a .config file is treated specially
393         and sets the user value of FOO to 'n'. The C implementation works the
394         same way.
395
396         filename: The .config file to load. $-references to existing
397           environment variables will be expanded. For scripts to work even when
398           an alternative build directory is used with the Linux kernel, you
399           need to refer to the top-level kernel directory with "$srctree".
400
401         replace (default: True): True if the configuration should replace the
402            old configuration; False if it should add to it.
403
404         Returns a list or warnings (hopefully empty)
405         """
406
407         self._warnings = []
408         # Put this first so that a missing file doesn't screw up our state
409         filename = os.path.expandvars(filename)
410         line_feeder = _FileFeed(filename)
411
412         self.config_filename = filename
413
414         #
415         # Read header
416         #
417
418         def is_header_line(line):
419             return line is not None and line.startswith("#") and \
420                    not _unset_re_match(line)
421
422         self.config_header = None
423
424         line = line_feeder.peek_next()
425         if is_header_line(line):
426             self.config_header = ""
427             while is_header_line(line_feeder.peek_next()):
428                 self.config_header += line_feeder.get_next()[1:]
429             # Remove trailing newline
430             if self.config_header.endswith("\n"):
431                 self.config_header = self.config_header[:-1]
432
433         #
434         # Read assignments. Hotspot for some workloads.
435         #
436
437         def warn_override(filename, linenr, name, old_user_val, new_user_val):
438             self._warn('overriding the value of {0}. '
439                        'Old value: "{1}", new value: "{2}".'
440                        .format(name, old_user_val, new_user_val),
441                        filename, linenr)
442
443         # Invalidate everything to keep things simple. It might be possible to
444         # improve performance for the case where multiple configurations are
445         # loaded by only invalidating a symbol (and its dependent symbols) if
446         # the new user value differs from the old. One complication would be
447         # that symbols not mentioned in the .config must lose their user value
448         # when replace = True, which is the usual case.
449         if replace:
450             self.unset_user_values()
451         else:
452             self._invalidate_all()
453
454         while 1:
455             line = line_feeder.get_next()
456             if line is None:
457                 return self._warnings
458
459             line = line.rstrip()
460
461             set_match = _set_re_match(line)
462             if set_match:
463                 name, val = set_match.groups()
464
465                 if val.startswith('"'):
466                     if len(val) < 2 or val[-1] != '"':
467                         _parse_error(line, "malformed string literal",
468                                      line_feeder.filename, line_feeder.linenr)
469                     # Strip quotes and remove escapings. The unescaping
470                     # procedure should be safe since " can only appear as \"
471                     # inside the string.
472                     val = val[1:-1].replace('\\"', '"').replace("\\\\", "\\")
473
474                 if name in self.syms:
475                     sym = self.syms[name]
476                     if sym.user_val is not None:
477                         warn_override(line_feeder.filename, line_feeder.linenr,
478                                       name, sym.user_val, val)
479
480                     if sym.is_choice_sym:
481                         user_mode = sym.parent.user_mode
482                         if user_mode is not None and user_mode != val:
483                             self._warn("assignment to {0} changes mode of "
484                                        'containing choice from "{1}" to "{2}".'
485                                        .format(name, val, user_mode),
486                                        line_feeder.filename,
487                                        line_feeder.linenr)
488
489                     sym._set_user_value_no_invalidate(val, True)
490                 else:
491                     if self.print_undef_assign:
492                         _stderr_msg('note: attempt to assign the value "{0}" '
493                                     "to the undefined symbol {1}."
494                                     .format(val, name),
495                                     line_feeder.filename, line_feeder.linenr)
496             else:
497                 unset_match = _unset_re_match(line)
498                 if unset_match:
499                     name = unset_match.group(1)
500                     if name in self.syms:
501                         sym = self.syms[name]
502                         if sym.user_val is not None:
503                             warn_override(line_feeder.filename,
504                                           line_feeder.linenr,
505                                           name, sym.user_val, "n")
506
507                         sym._set_user_value_no_invalidate("n", True)
508
509     def write_config(self, filename, header=None):
510         """Writes out symbol values in the familiar .config format.
511
512         Kconfiglib makes sure the format matches what the C implementation
513         would generate, down to whitespace. This eases testing.
514
515         filename: The filename under which to save the configuration.
516
517         header (default: None): A textual header that will appear at the
518            beginning of the file, with each line commented out automatically.
519            None means no header."""
520
521         for sym in self.syms_iter():
522             sym.already_written = False
523
524         with open(filename, "w") as f:
525             # Write header
526             if header is not None:
527                 f.write(_comment(header))
528                 f.write("\n")
529
530             # Build and write configuration
531             conf_strings = []
532             _make_block_conf(self.top_block, conf_strings.append)
533             f.write("\n".join(conf_strings))
534             f.write("\n")
535
536     def eval(self, s):
537         """Returns the value of the expression 's' -- where 's' is represented
538         as a string -- in the context of the configuration. Raises
539         Kconfig_Syntax_Error if syntax errors are detected in 's'.
540
541         For example, if FOO and BAR are tristate symbols at least one of which
542         has the value "y", then config.eval("y && (FOO || BAR)") => "y"
543
544         This function always yields a tristate value. To get the value of
545         non-bool, non-tristate symbols, use Symbol.get_value().
546
547         The result of this function is consistent with how evaluation works for
548         conditional expressions in the configuration as well as in the C
549         implementation. "m" and m are rewritten as '"m" && MODULES' and 'm &&
550         MODULES', respectively, and a result of "m" will get promoted to "y" if
551         we're running without modules.
552
553         Syntax checking is somewhat lax, partly to be compatible with lax
554         parsing in the C implementation."""
555         return self._eval_expr(self._parse_expr(self._tokenize(s, True), # Feed
556                                                 None, # Current symbol/choice
557                                                 s))   # line
558
559     def unset_user_values(self):
560         """Resets the values of all symbols, as if Config.load_config() or
561         Symbol.set_user_value() had never been called."""
562         for sym in self.syms_iter():
563             sym._unset_user_value_no_recursive_invalidate()
564
565     def set_print_warnings(self, print_warnings):
566         """Determines whether warnings related to this configuration (for
567         things like attempting to assign illegal values to symbols with
568         Symbol.set_user_value()) should be printed to stderr.
569
570         print_warnings: True if warnings should be printed."""
571         self.print_warnings = print_warnings
572
573     def set_print_undef_assign(self, print_undef_assign):
574         """Determines whether informational messages related to assignments to
575         undefined symbols should be printed to stderr for this configuration.
576
577         print_undef_assign: If True, such messages will be printed."""
578         self.print_undef_assign = print_undef_assign
579
580     def __str__(self):
581         """Returns a string containing various information about the Config."""
582         return _lines("Configuration",
583                       "File                                   : " +
584                         self.filename,
585                       "Base directory                         : " +
586                         self.base_dir,
587                       "Value of $ARCH at creation time        : " +
588                         ("(not set)" if self.arch is None else self.arch),
589                       "Value of $SRCARCH at creation time     : " +
590                         ("(not set)" if self.srcarch is None else
591                                         self.srcarch),
592                       "Source tree (derived from $srctree;",
593                       "defaults to '.' if $srctree isn't set) : " +
594                         self.srctree,
595                       "Most recently loaded .config           : " +
596                         ("(no .config loaded)"
597                           if self.config_filename is None else
598                              self.config_filename),
599                       "Print warnings                         : " +
600                         BOOL_STR[self.print_warnings],
601                       "Print assignments to undefined symbols : " +
602                         BOOL_STR[self.print_undef_assign])
603
604     #
605     # Private methods
606     #
607
608     #
609     # Kconfig parsing
610     #
611
612     def _parse_file(self, filename, parent, deps, visible_if_deps, res=None):
613         """Parses the Kconfig file 'filename'. Returns a list with the Items in
614         the file. See _parse_block() for the meaning of the parameters."""
615         return self._parse_block(_FileFeed(filename), None, parent, deps,
616                                  visible_if_deps, res)
617
618     def _parse_block(self, line_feeder, end_marker, parent, deps,
619                      visible_if_deps, res=None):
620         """Parses a block, which is the contents of either a file or an if,
621         menu, or choice statement. Returns a list with the Items in the block.
622
623         line_feeder: A _FileFeed instance feeding lines from a file. The
624           Kconfig language is line-based in practice.
625
626         end_marker: The token that ends the block, e.g. T_ENDIF ("endif") for
627            ifs. None for files.
628
629         parent: The enclosing menu or choice, or None if we're at the top
630            level.
631
632         deps: Dependencies from enclosing menus, choices and ifs.
633
634         visible_if_deps (default: None): 'visible if' dependencies from
635            enclosing menus.
636
637         res (default: None): The list to add items to. If None, a new list is
638            created to hold the items."""
639
640         block = [] if res is None else res
641
642         while 1:
643             # Do we already have a tokenized line that we determined wasn't
644             # part of whatever we were parsing earlier? See comment in
645             # Config.__init__().
646             if self.end_line is not None:
647                 line = self.end_line
648                 tokens = self.end_line_tokens
649                 tokens.unget_all()
650
651                 self.end_line = None
652                 self.end_line_tokens = None
653             else:
654                 line = line_feeder.get_next()
655                 if line is None:
656                     if end_marker is not None:
657                         raise Kconfig_Syntax_Error("Unexpected end of file {0}"
658                                                  .format(line_feeder.filename))
659                     return block
660
661                 tokens = self._tokenize(line, False, line_feeder.filename,
662                                         line_feeder.linenr)
663
664             t0 = tokens.get_next()
665             if t0 is None:
666                 continue
667
668             # Cases are ordered roughly by frequency, which speeds things up a
669             # bit
670
671             if t0 == T_CONFIG or t0 == T_MENUCONFIG:
672                 # The tokenizer will automatically allocate a new Symbol object
673                 # for any new names it encounters, so we don't need to worry
674                 # about that here.
675                 sym = tokens.get_next()
676
677                 # Symbols defined in multiple places get the parent of their
678                 # first definition. However, for symbols whose parents are
679                 # choice statements, the choice statement takes precedence.
680                 if not sym.is_defined_ or isinstance(parent, Choice):
681                     sym.parent = parent
682
683                 sym.is_defined_ = True
684
685                 self.kconfig_syms.append(sym)
686                 block.append(sym)
687
688                 self._parse_properties(line_feeder, sym, deps, visible_if_deps)
689
690             elif t0 == T_SOURCE:
691                 kconfig_file = tokens.get_next()
692                 exp_kconfig_file = self._expand_sym_refs(kconfig_file)
693                 f = os.path.join(self.base_dir, exp_kconfig_file)
694                 if not os.path.exists(f):
695                     raise IOError('{0}:{1}: sourced file "{2}" (expands to '
696                                   '"{3}") not found. Perhaps base_dir '
697                                   '(argument to Config.__init__(), currently '
698                                   '"{4}") is set to the wrong value.'
699                                   .format(line_feeder.filename,
700                                           line_feeder.linenr,
701                                           kconfig_file, exp_kconfig_file,
702                                           self.base_dir))
703                 # Add items to the same block
704                 self._parse_file(f, parent, deps, visible_if_deps, block)
705
706             elif t0 == end_marker:
707                 # We have reached the end of the block
708                 return block
709
710             elif t0 == T_IF:
711                 # If statements are treated as syntactic sugar for adding
712                 # dependencies to enclosed items and do not have an explicit
713                 # object representation.
714
715                 dep_expr = self._parse_expr(tokens, None, line,
716                                             line_feeder.filename,
717                                             line_feeder.linenr)
718                 # Add items to the same block
719                 self._parse_block(line_feeder, T_ENDIF, parent,
720                                   _make_and(dep_expr, deps),
721                                   visible_if_deps, block)
722
723             elif t0 == T_COMMENT:
724                 comment = Comment()
725
726                 comment.config = self
727                 comment.parent = parent
728                 comment.filename = line_feeder.filename
729                 comment.linenr = line_feeder.linenr
730                 comment.text = tokens.get_next()
731
732                 self.comments.append(comment)
733                 block.append(comment)
734
735                 self._parse_properties(line_feeder, comment, deps,
736                                        visible_if_deps)
737
738             elif t0 == T_MENU:
739                 menu = Menu()
740
741                 menu.config = self
742                 menu.parent = parent
743                 menu.filename = line_feeder.filename
744                 menu.linenr = line_feeder.linenr
745                 menu.title = tokens.get_next()
746
747                 self.menus.append(menu)
748                 block.append(menu)
749
750                 # Parse properties and contents
751                 self._parse_properties(line_feeder, menu, deps,
752                                        visible_if_deps)
753                 menu.block = self._parse_block(line_feeder, T_ENDMENU, menu,
754                                                menu.dep_expr,
755                                                _make_and(visible_if_deps,
756                                                          menu.visible_if_expr))
757
758             elif t0 == T_CHOICE:
759                 name = tokens.get_next()
760                 if name is None:
761                     choice = Choice()
762                     self.choices.append(choice)
763                 else:
764                     # Named choice
765                     choice = self.named_choices.get(name)
766                     if choice is None:
767                         choice = Choice()
768                         choice.name = name
769                         self.named_choices[name] = choice
770                         self.choices.append(choice)
771
772                 choice.config = self
773                 choice.parent = parent
774
775                 choice.def_locations.append((line_feeder.filename,
776                                              line_feeder.linenr))
777
778                 # Parse properties and contents
779                 self._parse_properties(line_feeder, choice, deps,
780                                        visible_if_deps)
781                 choice.block = self._parse_block(line_feeder, T_ENDCHOICE,
782                                                  choice, deps, visible_if_deps)
783
784                 choice._determine_actual_symbols()
785
786                 # If no type is specified for the choice, its type is that of
787                 # the first choice item with a specified type
788                 if choice.type == UNKNOWN:
789                     for item in choice.actual_symbols:
790                         if item.type != UNKNOWN:
791                             choice.type = item.type
792                             break
793
794                 # Each choice item of UNKNOWN type gets the type of the choice
795                 for item in choice.actual_symbols:
796                     if item.type == UNKNOWN:
797                         item.type = choice.type
798
799                 block.append(choice)
800
801             elif t0 == T_MAINMENU:
802                 text = tokens.get_next()
803                 if self.mainmenu_text is not None:
804                     self._warn("overriding 'mainmenu' text. "
805                                'Old value: "{0}", new value: "{1}".'
806                                .format(self.mainmenu_text, text),
807                                line_feeder.filename, line_feeder.linenr)
808                 self.mainmenu_text = text
809
810             else:
811                 _parse_error(line, "unrecognized construct",
812                              line_feeder.filename, line_feeder.linenr)
813
814     def _parse_properties(self, line_feeder, stmt, deps, visible_if_deps):
815         """Parsing of properties for symbols, menus, choices, and comments.
816         Takes care of propagating dependencies from enclosing menus and ifs."""
817
818         def parse_val_and_cond(tokens, line, filename, linenr):
819             """Parses '<expr1> if <expr2>' constructs, where the 'if' part is
820             optional. Returns a tuple containing the parsed expressions, with
821             None as the second element if the 'if' part is missing."""
822             val = self._parse_expr(tokens, stmt, line, filename, linenr, False)
823             if tokens.check(T_IF):
824                 return (val, self._parse_expr(tokens, stmt, line, filename,
825                                               linenr))
826             return (val, None)
827
828         # In case the symbol is defined in multiple locations, we need to
829         # remember what prompts, defaults, and selects are new for this
830         # definition, as "depends on" should only apply to the local
831         # definition.
832         new_prompt = None
833         new_def_exprs = []
834         new_selects = []
835
836         # Dependencies from 'depends on' statements
837         depends_on_expr = None
838
839         while 1:
840             line = line_feeder.get_next()
841             if line is None:
842                 break
843
844             filename = line_feeder.filename
845             linenr = line_feeder.linenr
846
847             tokens = self._tokenize(line, False, filename, linenr)
848
849             t0 = tokens.get_next()
850             if t0 is None:
851                 continue
852
853             # Cases are ordered roughly by frequency, which speeds things up a
854             # bit
855
856             if t0 == T_DEPENDS:
857                 if not tokens.check(T_ON):
858                     _parse_error(line, 'expected "on" after "depends"',
859                                  filename, linenr)
860
861                 parsed_deps = self._parse_expr(tokens, stmt, line, filename,
862                                                linenr)
863
864                 if isinstance(stmt, (Menu, Comment)):
865                     stmt.orig_deps = _make_and(stmt.orig_deps, parsed_deps)
866                 else:
867                     depends_on_expr = _make_and(depends_on_expr, parsed_deps)
868
869             elif t0 == T_HELP:
870                 # Find first non-blank (not all-space) line and get its
871                 # indentation
872                 line = line_feeder.next_nonblank()
873                 if line is None:
874                     stmt.help = ""
875                     break
876                 indent = _indentation(line)
877                 if indent == 0:
878                     # If the first non-empty lines has zero indent, there is no
879                     # help text
880                     stmt.help = ""
881                     line_feeder.unget()
882                     break
883
884                 # The help text goes on till the first non-empty line with less
885                 # indent
886                 help_lines = [_deindent(line, indent)]
887                 while 1:
888                     line = line_feeder.get_next()
889                     if line is None or \
890                        (not line.isspace() and _indentation(line) < indent):
891                         stmt.help = "".join(help_lines)
892                         break
893                     help_lines.append(_deindent(line, indent))
894
895                 if line is None:
896                     break
897
898                 line_feeder.unget()
899
900             elif t0 == T_SELECT or t0 == T_IMPLY:
901                 target = tokens.get_next()
902
903                 stmt.referenced_syms.add(target)
904                 stmt.selected_syms.add(target)
905
906                 if tokens.check(T_IF):
907                     new_selects.append((target,
908                                         self._parse_expr(tokens, stmt, line,
909                                                          filename, linenr)))
910                 else:
911                     new_selects.append((target, None))
912
913             elif t0 in (T_BOOL, T_TRISTATE, T_INT, T_HEX, T_STRING):
914                 stmt.type = TOKEN_TO_TYPE[t0]
915                 if tokens.peek_next() is not None:
916                     new_prompt = parse_val_and_cond(tokens, line, filename,
917                                                     linenr)
918
919             elif t0 == T_DEFAULT:
920                 new_def_exprs.append(parse_val_and_cond(tokens, line, filename,
921                                                         linenr))
922
923             elif t0 == T_DEF_BOOL:
924                 stmt.type = BOOL
925                 if tokens.peek_next() is not None:
926                     new_def_exprs.append(parse_val_and_cond(tokens, line,
927                                                             filename, linenr))
928
929             elif t0 == T_PROMPT:
930                 # 'prompt' properties override each other within a single
931                 # definition of a symbol, but additional prompts can be added
932                 # by defining the symbol multiple times; hence 'new_prompt'
933                 # instead of 'prompt'.
934                 new_prompt = parse_val_and_cond(tokens, line, filename, linenr)
935
936             elif t0 == T_RANGE:
937                 low = tokens.get_next()
938                 high = tokens.get_next()
939                 stmt.referenced_syms.add(low)
940                 stmt.referenced_syms.add(high)
941
942                 if tokens.check(T_IF):
943                     stmt.ranges.append((low, high,
944                                         self._parse_expr(tokens, stmt, line,
945                                                          filename, linenr)))
946                 else:
947                     stmt.ranges.append((low, high, None))
948
949             elif t0 == T_DEF_TRISTATE:
950                 stmt.type = TRISTATE
951                 if tokens.peek_next() is not None:
952                     new_def_exprs.append(parse_val_and_cond(tokens, line,
953                                                             filename, linenr))
954
955             elif t0 == T_OPTION:
956                 if tokens.check(T_ENV) and tokens.check(T_EQUAL):
957                     env_var = tokens.get_next()
958
959                     stmt.is_special_ = True
960                     stmt.is_from_env = True
961
962                     if env_var not in os.environ:
963                         self._warn("The symbol {0} references the "
964                                    "non-existent environment variable {1} and "
965                                    "will get the empty string as its value. "
966                                    "If you're using Kconfiglib via "
967                                    "'make (i)scriptconfig', it should have "
968                                    "set up the environment correctly for you. "
969                                    "If you still got this message, that "
970                                    "might be an error, and you should email "
971                                    "ulfalizer a.t Google's email service."""
972                                    .format(stmt.name, env_var),
973                                    filename, linenr)
974
975                         stmt.cached_val = ""
976                     else:
977                         stmt.cached_val = os.environ[env_var]
978
979                 elif tokens.check(T_DEFCONFIG_LIST):
980                     self.defconfig_sym = stmt
981
982                 elif tokens.check(T_MODULES):
983                     # To reduce warning spam, only warn if 'option modules' is
984                     # set on some symbol that isn't MODULES, which should be
985                     # safe. I haven't run into any projects that make use
986                     # modules besides the kernel yet, and there it's likely to
987                     # keep being called "MODULES".
988                     if stmt.name != "MODULES":
989                         self._warn("the 'modules' option is not supported. "
990                                    "Let me know if this is a problem for you; "
991                                    "it shouldn't be that hard to implement. "
992                                    "(Note that modules are still supported -- "
993                                    "Kconfiglib just assumes the symbol name "
994                                    "MODULES, like older versions of the C "
995                                    "implementation did when 'option modules' "
996                                    "wasn't used.)",
997                                    filename, linenr)
998
999                 elif tokens.check(T_ALLNOCONFIG_Y):
1000                     if not isinstance(stmt, Symbol):
1001                         _parse_error(line,
1002                                      "the 'allnoconfig_y' option is only "
1003                                      "valid for symbols",
1004                                      filename, linenr)
1005                     stmt.allnoconfig_y = True
1006
1007                 else:
1008                     _parse_error(line, "unrecognized option", filename, linenr)
1009
1010             elif t0 == T_VISIBLE:
1011                 if not tokens.check(T_IF):
1012                     _parse_error(line, 'expected "if" after "visible"',
1013                                  filename, linenr)
1014                 if not isinstance(stmt, Menu):
1015                     _parse_error(line,
1016                                  "'visible if' is only valid for menus",
1017                                  filename, linenr)
1018
1019                 parsed_deps = self._parse_expr(tokens, stmt, line, filename,
1020                                                linenr)
1021                 stmt.visible_if_expr = _make_and(stmt.visible_if_expr,
1022                                                  parsed_deps)
1023
1024             elif t0 == T_OPTIONAL:
1025                 if not isinstance(stmt, Choice):
1026                     _parse_error(line,
1027                                  '"optional" is only valid for choices',
1028                                  filename,
1029                                  linenr)
1030                 stmt.optional = True
1031
1032             else:
1033                 # See comment in Config.__init__()
1034                 self.end_line = line
1035                 self.end_line_tokens = tokens
1036                 break
1037
1038         # Done parsing properties. Now propagate 'depends on' and enclosing
1039         # menu/if dependencies to expressions.
1040
1041         # The set of symbols referenced directly by the statement plus all
1042         # symbols referenced by enclosing menus and ifs
1043         stmt.all_referenced_syms = stmt.referenced_syms | _get_expr_syms(deps)
1044
1045         # Save original dependencies from enclosing menus and ifs
1046         stmt.deps_from_containing = deps
1047
1048         if isinstance(stmt, (Menu, Comment)):
1049             stmt.dep_expr = _make_and(stmt.orig_deps, deps)
1050         else:
1051             # Symbol or Choice
1052
1053             # See comment for 'menu_dep'
1054             stmt.menu_dep = depends_on_expr
1055
1056             # Propagate dependencies to prompts
1057
1058             if new_prompt is not None:
1059                 # Propagate 'visible if' dependencies from enclosing menus
1060                 prompt, cond_expr = new_prompt
1061                 cond_expr = _make_and(cond_expr, visible_if_deps)
1062                 # Propagate 'depends on' dependencies
1063                 new_prompt = (prompt, _make_and(cond_expr, depends_on_expr))
1064                 # Save original
1065                 stmt.orig_prompts.append(new_prompt)
1066                 # Finalize with dependencies from enclosing menus and ifs
1067                 stmt.prompts.append((new_prompt[0],
1068                                      _make_and(new_prompt[1], deps)))
1069
1070             # Propagate dependencies to defaults
1071
1072             # Propagate 'depends on' dependencies
1073             new_def_exprs = [(val_expr, _make_and(cond_expr, depends_on_expr))
1074                              for val_expr, cond_expr in new_def_exprs]
1075             # Save original
1076             stmt.orig_def_exprs.extend(new_def_exprs)
1077             # Finalize with dependencies from enclosing menus and ifs
1078             stmt.def_exprs.extend([(val_expr, _make_and(cond_expr, deps))
1079                                    for val_expr, cond_expr in new_def_exprs])
1080
1081             # Propagate dependencies to selects
1082
1083             # Only symbols can select
1084             if isinstance(stmt, Symbol):
1085                 # Propagate 'depends on' dependencies
1086                 new_selects = [(target, _make_and(cond_expr, depends_on_expr))
1087                                for target, cond_expr in new_selects]
1088                 # Save original
1089                 stmt.orig_selects.extend(new_selects)
1090                 # Finalize with dependencies from enclosing menus and ifs
1091                 for target, cond in new_selects:
1092                     target.rev_dep = _make_or(target.rev_dep,
1093                                               _make_and(stmt,
1094                                                         _make_and(cond, deps)))
1095
1096     def _parse_expr(self, feed, cur_item, line, filename=None, linenr=None,
1097                     transform_m=True):
1098         """Parses an expression from the tokens in 'feed' using a simple
1099         top-down approach. The result has the form
1100         '(<operator>, [<parsed operands>])', where <operator> is e.g.
1101         kconfiglib.AND. If there is only one operand (i.e., no && or ||), then
1102         the operand is returned directly. This also goes for subexpressions.
1103
1104         feed: _Feed instance containing the tokens for the expression.
1105
1106         cur_item: The item (Symbol, Choice, Menu, or Comment) currently being
1107            parsed, or None if we're not parsing an item. Used for recording
1108            references to symbols.
1109
1110         line: The line containing the expression being parsed.
1111
1112         filename (default: None): The file containing the expression.
1113
1114         linenr (default: None): The line number containing the expression.
1115
1116         transform_m (default: False): Determines if 'm' should be rewritten to
1117            'm && MODULES' -- see parse_val_and_cond().
1118
1119         Expression grammar, in decreasing order of precedence:
1120
1121         <expr> -> <symbol>
1122                   <symbol> '=' <symbol>
1123                   <symbol> '!=' <symbol>
1124                   '(' <expr> ')'
1125                   '!' <expr>
1126                   <expr> '&&' <expr>
1127                   <expr> '||' <expr>"""
1128
1129         # Use instance variables to avoid having to pass these as arguments
1130         # through the top-down parser in _parse_expr_rec(), which is tedious
1131         # and obfuscates the code. A profiler run shows no noticeable
1132         # performance difference.
1133         self._cur_item = cur_item
1134         self._transform_m = transform_m
1135         self._line = line
1136         self._filename = filename
1137         self._linenr = linenr
1138
1139         return self._parse_expr_rec(feed)
1140
1141     def _parse_expr_rec(self, feed):
1142         or_term = self._parse_or_term(feed)
1143         if not feed.check(T_OR):
1144             # Common case -- no need for an OR node since it's just a single
1145             # operand
1146             return or_term
1147         or_terms = [or_term, self._parse_or_term(feed)]
1148         while feed.check(T_OR):
1149             or_terms.append(self._parse_or_term(feed))
1150         return (OR, or_terms)
1151
1152     def _parse_or_term(self, feed):
1153         and_term = self._parse_factor(feed)
1154         if not feed.check(T_AND):
1155             # Common case -- no need for an AND node since it's just a single
1156             # operand
1157             return and_term
1158         and_terms = [and_term, self._parse_factor(feed)]
1159         while feed.check(T_AND):
1160             and_terms.append(self._parse_factor(feed))
1161         return (AND, and_terms)
1162
1163     def _parse_factor(self, feed):
1164         token = feed.get_next()
1165
1166         if isinstance(token, (Symbol, str)):
1167             if self._cur_item is not None and isinstance(token, Symbol):
1168                 self._cur_item.referenced_syms.add(token)
1169
1170             next_token = feed.peek_next()
1171             # For conditional expressions ('depends on <expr>',
1172             # '... if <expr>', # etc.), "m" and m are rewritten to
1173             # "m" && MODULES.
1174             if next_token != T_EQUAL and next_token != T_UNEQUAL:
1175                 if self._transform_m and (token is self.m or token == "m"):
1176                     return (AND, ["m", self._sym_lookup("MODULES")])
1177                 return token
1178
1179             relation = EQUAL if (feed.get_next() == T_EQUAL) else UNEQUAL
1180             token_2 = feed.get_next()
1181             if self._cur_item is not None and isinstance(token_2, Symbol):
1182                 self._cur_item.referenced_syms.add(token_2)
1183             return (relation, token, token_2)
1184
1185         if token == T_NOT:
1186             return (NOT, self._parse_factor(feed))
1187
1188         if token == T_OPEN_PAREN:
1189             expr_parse = self._parse_expr_rec(feed)
1190             if not feed.check(T_CLOSE_PAREN):
1191                 _parse_error(self._line, "missing end parenthesis",
1192                              self._filename, self._linenr)
1193             return expr_parse
1194
1195         _parse_error(self._line, "malformed expression", self._filename,
1196                      self._linenr)
1197
1198     def _tokenize(self, s, for_eval, filename=None, linenr=None):
1199         """Returns a _Feed instance containing tokens derived from the string
1200         's'. Registers any new symbols encountered (via _sym_lookup()).
1201
1202         (I experimented with a pure regular expression implementation, but it
1203         came out slower, less readable, and wouldn't have been as flexible.)
1204
1205         for_eval: True when parsing an expression for a call to Config.eval(),
1206            in which case we should not treat the first token specially nor
1207            register new symbols."""
1208
1209         s = s.strip()
1210         if s == "" or s[0] == "#":
1211             return _Feed([])
1212
1213         if for_eval:
1214             previous = None # The previous token seen
1215             tokens = []
1216             i = 0 # The current index in the string being tokenized
1217
1218         else:
1219             # The initial word on a line is parsed specially. Let
1220             # command_chars = [A-Za-z0-9_]. Then
1221             #  - leading non-command_chars characters are ignored, and
1222             #  - the first token consists the following one or more
1223             #    command_chars characters.
1224             # This is why things like "----help--" are accepted.
1225             initial_token_match = _initial_token_re_match(s)
1226             if initial_token_match is None:
1227                 return _Feed([])
1228             keyword = _get_keyword(initial_token_match.group(1))
1229             if keyword == T_HELP:
1230                 # Avoid junk after "help", e.g. "---", being registered as a
1231                 # symbol
1232                 return _Feed([T_HELP])
1233             if keyword is None:
1234                 # We expect a keyword as the first token
1235                 _tokenization_error(s, filename, linenr)
1236
1237             previous = keyword
1238             tokens = [keyword]
1239             # The current index in the string being tokenized
1240             i = initial_token_match.end()
1241
1242         # _tokenize() is a hotspot during parsing, and this speeds things up a
1243         # bit
1244         strlen = len(s)
1245         append = tokens.append
1246
1247         # Main tokenization loop. (Handles tokens past the first one.)
1248         while i < strlen:
1249             # Test for an identifier/keyword preceded by whitespace first; this
1250             # is the most common case.
1251             id_keyword_match = _id_keyword_re_match(s, i)
1252             if id_keyword_match:
1253                 # We have an identifier or keyword. The above also stripped any
1254                 # whitespace for us.
1255                 name = id_keyword_match.group(1)
1256                 # Jump past it
1257                 i = id_keyword_match.end()
1258
1259                 keyword = _get_keyword(name)
1260                 if keyword is not None:
1261                     # It's a keyword
1262                     append(keyword)
1263                 elif previous in STRING_LEX:
1264                     # What would ordinarily be considered an identifier is
1265                     # treated as a string after certain tokens
1266                     append(name)
1267                 else:
1268                     # It's a symbol name. _sym_lookup() will take care of
1269                     # allocating a new Symbol instance if it's the first time
1270                     # we see it.
1271                     sym = self._sym_lookup(name, for_eval)
1272
1273                     if previous == T_CONFIG or previous == T_MENUCONFIG:
1274                         # If the previous token is T_(MENU)CONFIG
1275                         # ("(menu)config"), we're tokenizing the first line of
1276                         # a symbol definition, and should remember this as a
1277                         # location where the symbol is defined
1278                         sym.def_locations.append((filename, linenr))
1279                     else:
1280                         # Otherwise, it's a reference to the symbol
1281                         sym.ref_locations.append((filename, linenr))
1282
1283                     append(sym)
1284
1285             else:
1286                 # Not an identifier/keyword
1287
1288                 while i < strlen and s[i].isspace():
1289                     i += 1
1290                 if i == strlen:
1291                     break
1292                 c = s[i]
1293                 i += 1
1294
1295                 # String literal (constant symbol)
1296                 if c == '"' or c == "'":
1297                     if "\\" in s:
1298                         # Slow path: This could probably be sped up, but it's a
1299                         # very unusual case anyway.
1300                         quote = c
1301                         val = ""
1302                         while 1:
1303                             if i >= len(s):
1304                                 _tokenization_error(s, filename, linenr)
1305                             c = s[i]
1306                             if c == quote:
1307                                 break
1308                             if c == "\\":
1309                                 if i + 1 >= len(s):
1310                                     _tokenization_error(s, filename, linenr)
1311                                 val += s[i + 1]
1312                                 i += 2
1313                             else:
1314                                 val += c
1315                                 i += 1
1316                         i += 1
1317                         append(val)
1318                     else:
1319                         # Fast path: If the string contains no backslashes
1320                         # (almost always) we can simply look for the matching
1321                         # quote.
1322                         end = s.find(c, i)
1323                         if end == -1:
1324                             _tokenization_error(s, filename, linenr)
1325                         append(s[i:end])
1326                         i = end + 1
1327
1328                 elif c == "&":
1329                     # Invalid characters are ignored
1330                     if i >= len(s) or s[i] != "&": continue
1331                     append(T_AND)
1332                     i += 1
1333
1334                 elif c == "|":
1335                     # Invalid characters are ignored
1336                     if i >= len(s) or s[i] != "|": continue
1337                     append(T_OR)
1338                     i += 1
1339
1340                 elif c == "!":
1341                     if i < len(s) and s[i] == "=":
1342                         append(T_UNEQUAL)
1343                         i += 1
1344                     else:
1345                         append(T_NOT)
1346
1347                 elif c == "=": append(T_EQUAL)
1348                 elif c == "(": append(T_OPEN_PAREN)
1349                 elif c == ")": append(T_CLOSE_PAREN)
1350                 elif c == "#": break # Comment
1351
1352                 else: continue # Invalid characters are ignored
1353
1354             previous = tokens[-1]
1355
1356         return _Feed(tokens)
1357
1358     def _sym_lookup(self, name, for_eval=False):
1359         """Fetches the symbol 'name' from the symbol table, creating and
1360         registering it if it does not exist. If 'for_eval' is True, the symbol
1361         won't be added to the symbol table if it does not exist -- this is for
1362         Config.eval()."""
1363         if name in self.syms:
1364             return self.syms[name]
1365
1366         new_sym = Symbol()
1367         new_sym.config = self
1368         new_sym.name = name
1369         if for_eval:
1370             self._warn("no symbol {0} in configuration".format(name))
1371         else:
1372             self.syms[name] = new_sym
1373         return new_sym
1374
1375     #
1376     # Expression evaluation
1377     #
1378
1379     def _eval_expr(self, expr):
1380         """Evaluates an expression to "n", "m", or "y"."""
1381
1382         # Handles e.g. an "x if y" condition where the "if y" part is missing.
1383         if expr is None:
1384             return "y"
1385
1386         res = self._eval_expr_rec(expr)
1387         if res == "m":
1388             # Promote "m" to "y" if we're running without modules.
1389             #
1390             # Internally, "m" is often rewritten to "m" && MODULES by both the
1391             # C implementation and Kconfiglib, which takes care of cases where
1392             # "m" should be demoted to "n" instead.
1393             modules_sym = self.syms.get("MODULES")
1394             if modules_sym is None or modules_sym.get_value() != "y":
1395                 return "y"
1396         return res
1397
1398     def _eval_expr_rec(self, expr):
1399         if isinstance(expr, Symbol):
1400             # Non-bool/tristate symbols are always "n" in a tristate sense,
1401             # regardless of their value
1402             if expr.type != BOOL and expr.type != TRISTATE:
1403                 return "n"
1404             return expr.get_value()
1405
1406         if isinstance(expr, str):
1407             return expr if (expr == "y" or expr == "m") else "n"
1408
1409         # Ordered by frequency
1410
1411         if expr[0] == AND:
1412             res = "y"
1413             for subexpr in expr[1]:
1414                 ev = self._eval_expr_rec(subexpr)
1415                 # Return immediately upon discovering an "n" term
1416                 if ev == "n":
1417                     return "n"
1418                 if ev == "m":
1419                     res = "m"
1420             # 'res' is either "m" or "y" here; we already handled the
1421             # short-circuiting "n" case in the loop.
1422             return res
1423
1424         if expr[0] == NOT:
1425             ev = self._eval_expr_rec(expr[1])
1426             if ev == "y":
1427                 return "n"
1428             return "y" if (ev == "n") else "m"
1429
1430         if expr[0] == OR:
1431             res = "n"
1432             for subexpr in expr[1]:
1433                 ev = self._eval_expr_rec(subexpr)
1434                 # Return immediately upon discovering a "y" term
1435                 if ev == "y":
1436                     return "y"
1437                 if ev == "m":
1438                     res = "m"
1439             # 'res' is either "n" or "m" here; we already handled the
1440             # short-circuiting "y" case in the loop.
1441             return res
1442
1443         if expr[0] == EQUAL:
1444             return "y" if (_str_val(expr[1]) == _str_val(expr[2])) else "n"
1445
1446         if expr[0] == UNEQUAL:
1447             return "y" if (_str_val(expr[1]) != _str_val(expr[2])) else "n"
1448
1449         _internal_error("Internal error while evaluating expression: "
1450                         "unknown operation {0}.".format(expr[0]))
1451
1452     def _eval_min(self, e1, e2):
1453         """Returns the minimum value of the two expressions. Equates None with
1454         'y'."""
1455         e1_eval = self._eval_expr(e1)
1456         e2_eval = self._eval_expr(e2)
1457         return e1_eval if tri_less(e1_eval, e2_eval) else e2_eval
1458
1459     def _eval_max(self, e1, e2):
1460         """Returns the maximum value of the two expressions. Equates None with
1461         'y'."""
1462         e1_eval = self._eval_expr(e1)
1463         e2_eval = self._eval_expr(e2)
1464         return e1_eval if tri_greater(e1_eval, e2_eval) else e2_eval
1465
1466     #
1467     # Dependency tracking (for caching and invalidation)
1468     #
1469
1470     def _build_dep(self):
1471         """Populates the Symbol.dep sets, linking the symbol to the symbols
1472         that immediately depend on it in the sense that changing the value of
1473         the symbol might affect the values of those other symbols. This is used
1474         for caching/invalidation purposes. The calculated sets might be larger
1475         than necessary as we don't do any complicated analysis of the
1476         expressions."""
1477
1478         # Adds 'sym' as a directly dependent symbol to all symbols that appear
1479         # in the expression 'e'
1480         def add_expr_deps(e, sym):
1481             for s in _get_expr_syms(e):
1482                 s.dep.add(sym)
1483
1484         # The directly dependent symbols of a symbol are:
1485         #  - Any symbols whose prompts, default values, rev_dep (select
1486         #    condition), or ranges depend on the symbol
1487         #  - Any symbols that belong to the same choice statement as the symbol
1488         #    (these won't be included in 'dep' as that makes the dependency
1489         #    graph unwieldy, but Symbol._get_dependent() will include them)
1490         #  - Any symbols in a choice statement that depends on the symbol
1491         for sym in self.syms_iter():
1492             for _, e in sym.prompts:
1493                 add_expr_deps(e, sym)
1494
1495             for v, e in sym.def_exprs:
1496                 add_expr_deps(v, sym)
1497                 add_expr_deps(e, sym)
1498
1499             add_expr_deps(sym.rev_dep, sym)
1500
1501             for l, u, e in sym.ranges:
1502                 add_expr_deps(l, sym)
1503                 add_expr_deps(u, sym)
1504                 add_expr_deps(e, sym)
1505
1506             if sym.is_choice_sym:
1507                 choice = sym.parent
1508                 for _, e in choice.prompts:
1509                     add_expr_deps(e, sym)
1510                 for _, e in choice.def_exprs:
1511                     add_expr_deps(e, sym)
1512
1513     def _eq_to_sym(self, eq):
1514         """_expr_depends_on() helper. For (in)equalities of the form sym = y/m
1515         or sym != n, returns sym. For other (in)equalities, returns None."""
1516         relation, left, right = eq
1517
1518         def transform_y_m_n(item):
1519             if item is self.y: return "y"
1520             if item is self.m: return "m"
1521             if item is self.n: return "n"
1522             return item
1523
1524         left = transform_y_m_n(left)
1525         right = transform_y_m_n(right)
1526
1527         # Make sure the symbol (if any) appears to the left
1528         if not isinstance(left, Symbol):
1529             left, right = right, left
1530         if not isinstance(left, Symbol):
1531             return None
1532         if (relation == EQUAL and (right == "y" or right == "m")) or \
1533            (relation == UNEQUAL and right == "n"):
1534             return left
1535         return None
1536
1537     def _expr_depends_on(self, expr, sym):
1538         """Reimplementation of expr_depends_symbol() from mconf.c. Used to
1539         determine if a submenu should be implicitly created, which influences
1540         what items inside choice statements are considered choice items."""
1541         if expr is None:
1542             return False
1543
1544         def rec(expr):
1545             if isinstance(expr, str):
1546                 return False
1547             if isinstance(expr, Symbol):
1548                 return expr is sym
1549
1550             if expr[0] in (EQUAL, UNEQUAL):
1551                 return self._eq_to_sym(expr) is sym
1552             if expr[0] == AND:
1553                 for and_expr in expr[1]:
1554                     if rec(and_expr):
1555                         return True
1556             return False
1557
1558         return rec(expr)
1559
1560     def _invalidate_all(self):
1561         for sym in self.syms_iter():
1562             sym._invalidate()
1563
1564     #
1565     # Printing and misc.
1566     #
1567
1568     def _expand_sym_refs(self, s):
1569         """Expands $-references to symbols in 's' to symbol values, or to the
1570         empty string for undefined symbols."""
1571
1572         while 1:
1573             sym_ref_match = _sym_ref_re_search(s)
1574             if sym_ref_match is None:
1575                 return s
1576
1577             sym_name = sym_ref_match.group(0)[1:]
1578             sym = self.syms.get(sym_name)
1579             expansion = "" if sym is None else sym.get_value()
1580
1581             s = s[:sym_ref_match.start()] + \
1582                 expansion + \
1583                 s[sym_ref_match.end():]
1584
1585     def _expr_val_str(self, expr, no_value_str="(none)",
1586                       get_val_instead_of_eval=False):
1587         """Printing helper. Returns a string with 'expr' and its value.
1588
1589         no_value_str: String to return when 'expr' is missing (None).
1590
1591         get_val_instead_of_eval: Assume 'expr' is a symbol or string (constant
1592           symbol) and get its value directly instead of evaluating it to a
1593           tristate value."""
1594
1595         if expr is None:
1596             return no_value_str
1597
1598         if get_val_instead_of_eval:
1599             if isinstance(expr, str):
1600                 return _expr_to_str(expr)
1601             val = expr.get_value()
1602         else:
1603             val = self._eval_expr(expr)
1604
1605         return "{0} (value: {1})".format(_expr_to_str(expr), _expr_to_str(val))
1606
1607     def _get_sym_or_choice_str(self, sc):
1608         """Symbols and choices have many properties in common, so we factor out
1609         common __str__() stuff here. "sc" is short for "symbol or choice"."""
1610
1611         # As we deal a lot with string representations here, use some
1612         # convenient shorthand:
1613         s = _expr_to_str
1614
1615         #
1616         # Common symbol/choice properties
1617         #
1618
1619         user_val_str = "(no user value)" if sc.user_val is None else \
1620                        s(sc.user_val)
1621
1622         # Build prompts string
1623         if not sc.prompts:
1624             prompts_str = " (no prompts)"
1625         else:
1626             prompts_str_rows = []
1627             for prompt, cond_expr in sc.orig_prompts:
1628                 if cond_expr is None:
1629                     prompts_str_rows.append(' "{0}"'.format(prompt))
1630                 else:
1631                     prompts_str_rows.append(
1632                       ' "{0}" if {1}'.format(prompt,
1633                                              self._expr_val_str(cond_expr)))
1634             prompts_str = "\n".join(prompts_str_rows)
1635
1636         # Build locations string
1637         if not sc.def_locations:
1638             locations_str = "(no locations)"
1639         else:
1640             locations_str = " ".join(["{0}:{1}".format(filename, linenr) for
1641                                       (filename, linenr) in sc.def_locations])
1642
1643         # Build additional-dependencies-from-menus-and-ifs string
1644         additional_deps_str = " " + \
1645           self._expr_val_str(sc.deps_from_containing,
1646                              "(no additional dependencies)")
1647
1648         #
1649         # Symbol-specific stuff
1650         #
1651
1652         if isinstance(sc, Symbol):
1653             # Build ranges string
1654             if isinstance(sc, Symbol):
1655                 if not sc.ranges:
1656                     ranges_str = " (no ranges)"
1657                 else:
1658                     ranges_str_rows = []
1659                     for l, u, cond_expr in sc.ranges:
1660                         if cond_expr is None:
1661                             ranges_str_rows.append(" [{0}, {1}]".format(s(l),
1662                                                                         s(u)))
1663                         else:
1664                             ranges_str_rows.append(" [{0}, {1}] if {2}"
1665                               .format(s(l), s(u),
1666                                       self._expr_val_str(cond_expr)))
1667                     ranges_str = "\n".join(ranges_str_rows)
1668
1669             # Build default values string
1670             if not sc.def_exprs:
1671                 defaults_str = " (no default values)"
1672             else:
1673                 defaults_str_rows = []
1674                 for val_expr, cond_expr in sc.orig_def_exprs:
1675                     row_str = " " + self._expr_val_str(val_expr, "(none)",
1676                                                        sc.type == STRING)
1677                     defaults_str_rows.append(row_str)
1678                     defaults_str_rows.append("  Condition: " +
1679                                                self._expr_val_str(cond_expr))
1680                 defaults_str = "\n".join(defaults_str_rows)
1681
1682             # Build selects string
1683             if not sc.orig_selects:
1684                 selects_str = " (no selects)"
1685             else:
1686                 selects_str_rows = []
1687                 for target, cond_expr in sc.orig_selects:
1688                     if cond_expr is None:
1689                         selects_str_rows.append(" {0}".format(target.name))
1690                     else:
1691                         selects_str_rows.append(
1692                           " {0} if {1}".format(target.name,
1693                                                self._expr_val_str(cond_expr)))
1694                 selects_str = "\n".join(selects_str_rows)
1695
1696             res = _lines("Symbol " +
1697                            ("(no name)" if sc.name is None else sc.name),
1698                          "Type           : " + TYPENAME[sc.type],
1699                          "Value          : " + s(sc.get_value()),
1700                          "User value     : " + user_val_str,
1701                          "Visibility     : " + s(_get_visibility(sc)),
1702                          "Is choice item : " + BOOL_STR[sc.is_choice_sym],
1703                          "Is defined     : " + BOOL_STR[sc.is_defined_],
1704                          "Is from env.   : " + BOOL_STR[sc.is_from_env],
1705                          "Is special     : " + BOOL_STR[sc.is_special_] + "\n")
1706             if sc.ranges:
1707                 res += _lines("Ranges:", ranges_str + "\n")
1708             res += _lines("Prompts:",
1709                           prompts_str,
1710                           "Default values:",
1711                           defaults_str,
1712                           "Selects:",
1713                           selects_str,
1714                           "Reverse (select-related) dependencies:",
1715                           " (no reverse dependencies)" if sc.rev_dep == "n"
1716                             else " " + self._expr_val_str(sc.rev_dep),
1717                           "Additional dependencies from enclosing menus "
1718                             "and ifs:",
1719                           additional_deps_str,
1720                           "Locations: " + locations_str)
1721
1722             return res
1723
1724         #
1725         # Choice-specific stuff
1726         #
1727
1728         # Build selected symbol string
1729         sel = sc.get_selection()
1730         sel_str = "(no selection)" if sel is None else sel.name
1731
1732         # Build default values string
1733         if not sc.def_exprs:
1734             defaults_str = " (no default values)"
1735         else:
1736             defaults_str_rows = []
1737             for sym, cond_expr in sc.orig_def_exprs:
1738                 if cond_expr is None:
1739                     defaults_str_rows.append(" {0}".format(sym.name))
1740                 else:
1741                     defaults_str_rows.append(" {0} if {1}".format(sym.name,
1742                                                 self._expr_val_str(cond_expr)))
1743             defaults_str = "\n".join(defaults_str_rows)
1744
1745         # Build contained symbols string
1746         names = [sym.name for sym in sc.actual_symbols]
1747         syms_string = " ".join(names) if names else "(empty)"
1748
1749         return _lines("Choice",
1750                       "Name (for named choices): " +
1751                         ("(no name)" if sc.name is None else sc.name),
1752                       "Type            : " + TYPENAME[sc.type],
1753                       "Selected symbol : " + sel_str,
1754                       "User value      : " + user_val_str,
1755                       "Mode            : " + s(sc.get_mode()),
1756                       "Visibility      : " + s(_get_visibility(sc)),
1757                       "Optional        : " + BOOL_STR[sc.optional],
1758                       "Prompts:",
1759                       prompts_str,
1760                       "Defaults:",
1761                       defaults_str,
1762                       "Choice symbols:",
1763                       " " + syms_string,
1764                       "Additional dependencies from enclosing menus and "
1765                         "ifs:",
1766                       additional_deps_str,
1767                       "Locations: " + locations_str)
1768
1769     def _warn(self, msg, filename=None, linenr=None):
1770         """For printing warnings to stderr."""
1771         msg = _build_msg("warning: " + msg, filename, linenr)
1772         if self.print_warnings:
1773             sys.stderr.write(msg + "\n")
1774         self._warnings.append(msg)
1775
1776 class Item(object):
1777
1778     """Base class for symbols and other Kconfig constructs. Subclasses are
1779     Symbol, Choice, Menu, and Comment."""
1780
1781     def is_symbol(self):
1782         """Returns True if the item is a symbol. Short for
1783         isinstance(item, kconfiglib.Symbol)."""
1784         return isinstance(self, Symbol)
1785
1786     def is_choice(self):
1787         """Returns True if the item is a choice. Short for
1788         isinstance(item, kconfiglib.Choice)."""
1789         return isinstance(self, Choice)
1790
1791     def is_menu(self):
1792         """Returns True if the item is a menu. Short for
1793         isinstance(item, kconfiglib.Menu)."""
1794         return isinstance(self, Menu)
1795
1796     def is_comment(self):
1797         """Returns True if the item is a comment. Short for
1798         isinstance(item, kconfiglib.Comment)."""
1799         return isinstance(self, Comment)
1800
1801 class Symbol(Item):
1802
1803     """Represents a configuration symbol - e.g. FOO for
1804
1805     config FOO
1806         ..."""
1807
1808     #
1809     # Public interface
1810     #
1811
1812     def get_config(self):
1813         """Returns the Config instance this symbol is from."""
1814         return self.config
1815
1816     def get_name(self):
1817         """Returns the name of the symbol."""
1818         return self.name
1819
1820     def get_type(self):
1821         """Returns the type of the symbol: one of UNKNOWN, BOOL, TRISTATE,
1822         STRING, HEX, or INT. These are defined at the top level of the module,
1823         so you'd do something like
1824
1825         if sym.get_type() == kconfiglib.STRING:
1826             ..."""
1827         return self.type
1828
1829     def get_prompts(self):
1830         """Returns a list of prompts defined for the symbol, in the order they
1831         appear in the configuration files. Returns the empty list for symbols
1832         with no prompt.
1833
1834         This list will have a single entry for the vast majority of symbols
1835         having prompts, but having multiple prompts for a single symbol is
1836         possible through having multiple 'config' entries for it."""
1837         return [prompt for prompt, _ in self.orig_prompts]
1838
1839     def get_help(self):
1840         """Returns the help text of the symbol, or None if the symbol has no
1841         help text."""
1842         return self.help
1843
1844     def get_parent(self):
1845         """Returns the menu or choice statement that contains the symbol, or
1846         None if the symbol is at the top level. Note that if statements are
1847         treated as syntactic and do not have an explicit class
1848         representation."""
1849         return self.parent
1850
1851     def get_def_locations(self):
1852         """Returns a list of (filename, linenr) tuples, where filename (string)
1853         and linenr (int) represent a location where the symbol is defined. For
1854         the vast majority of symbols this list will only contain one element.
1855         For the following Kconfig, FOO would get two entries: the lines marked
1856         with *.
1857
1858         config FOO *
1859             bool "foo prompt 1"
1860
1861         config FOO *
1862             bool "foo prompt 2"
1863         """
1864         return self.def_locations
1865
1866     def get_ref_locations(self):
1867         """Returns a list of (filename, linenr) tuples, where filename (string)
1868         and linenr (int) represent a location where the symbol is referenced in
1869         the configuration. For example, the lines marked by * would be included
1870         for FOO below:
1871
1872         config A
1873             bool
1874             default BAR || FOO *
1875
1876         config B
1877             tristate
1878             depends on FOO *
1879             default m if FOO *
1880
1881         if FOO *
1882             config A
1883                 bool "A"
1884         endif
1885
1886         config FOO (definition not included)
1887             bool
1888         """
1889         return self.ref_locations
1890
1891     def get_value(self):
1892         """Calculate and return the value of the symbol. See also
1893         Symbol.set_user_value()."""
1894
1895         if self.cached_val is not None:
1896             return self.cached_val
1897
1898         # As a quirk of Kconfig, undefined symbols get their name as their
1899         # value. This is why things like "FOO = bar" work for seeing if FOO has
1900         # the value "bar".
1901         if self.type == UNKNOWN:
1902             self.cached_val = self.name
1903             return self.name
1904
1905         new_val = DEFAULT_VALUE[self.type]
1906         vis = _get_visibility(self)
1907
1908         # This is easiest to calculate together with the value
1909         self.write_to_conf = False
1910
1911         if self.type == BOOL or self.type == TRISTATE:
1912             # The visibility and mode (modules-only or single-selection) of
1913             # choice items will be taken into account in _get_visibility()
1914             if self.is_choice_sym:
1915                 if vis != "n":
1916                     choice = self.parent
1917                     mode = choice.get_mode()
1918
1919                     self.write_to_conf = (mode != "n")
1920
1921                     if mode == "y":
1922                         if choice.get_selection() is self:
1923                             new_val = "y"
1924                         else:
1925                             new_val = "n"
1926                     elif mode == "m":
1927                         if self.user_val == "m" or self.user_val == "y":
1928                             new_val = "m"
1929
1930             else:
1931                 # If the symbol is visible and has a user value, use that.
1932                 # Otherwise, look at defaults.
1933                 use_defaults = True
1934
1935                 if vis != "n":
1936                     self.write_to_conf = True
1937                     if self.user_val is not None:
1938                         new_val = self.config._eval_min(self.user_val, vis)
1939                         use_defaults = False
1940
1941                 if use_defaults:
1942                     for val_expr, cond_expr in self.def_exprs:
1943                         cond_eval = self.config._eval_expr(cond_expr)
1944                         if cond_eval != "n":
1945                             self.write_to_conf = True
1946                             new_val = self.config._eval_min(val_expr,
1947                                                             cond_eval)
1948                             break
1949
1950                 # Reverse (select-related) dependencies take precedence
1951                 rev_dep_val = self.config._eval_expr(self.rev_dep)
1952                 if rev_dep_val != "n":
1953                     self.write_to_conf = True
1954                     new_val = self.config._eval_max(new_val, rev_dep_val)
1955
1956             # Promote "m" to "y" for booleans
1957             if new_val == "m" and self.type == BOOL:
1958                 new_val = "y"
1959
1960         elif self.type == INT or self.type == HEX:
1961             has_active_range = False
1962             low = None
1963             high = None
1964             use_defaults = True
1965
1966             base = 16 if self.type == HEX else 10
1967
1968             for l, h, cond_expr in self.ranges:
1969                 if self.config._eval_expr(cond_expr) != "n":
1970                     has_active_range = True
1971
1972                     low_str = _str_val(l)
1973                     high_str = _str_val(h)
1974                     low = int(low_str, base) if \
1975                       _is_base_n(low_str, base) else 0
1976                     high = int(high_str, base) if \
1977                       _is_base_n(high_str, base) else 0
1978
1979                     break
1980
1981             if vis != "n":
1982                 self.write_to_conf = True
1983
1984                 if self.user_val is not None and \
1985                    _is_base_n(self.user_val, base) and \
1986                    (not has_active_range or
1987                     low <= int(self.user_val, base) <= high):
1988
1989                     # If the user value is OK, it is stored in exactly the same
1990                     # form as specified in the assignment (with or without
1991                     # "0x", etc).
1992
1993                     use_defaults = False
1994                     new_val = self.user_val
1995
1996             if use_defaults:
1997                 for val_expr, cond_expr in self.def_exprs:
1998                     if self.config._eval_expr(cond_expr) != "n":
1999                         self.write_to_conf = True
2000
2001                         # If the default value is OK, it is stored in exactly
2002                         # the same form as specified. Otherwise, it is clamped
2003                         # to the range, and the output has "0x" as appropriate
2004                         # for the type.
2005
2006                         new_val = _str_val(val_expr)
2007
2008                         if _is_base_n(new_val, base):
2009                             new_val_num = int(new_val, base)
2010                             if has_active_range:
2011                                 clamped_val = None
2012
2013                                 if new_val_num < low:
2014                                     clamped_val = low
2015                                 elif new_val_num > high:
2016                                     clamped_val = high
2017
2018                                 if clamped_val is not None:
2019                                     new_val = (hex(clamped_val) if \
2020                                       self.type == HEX else str(clamped_val))
2021
2022                             break
2023                 else: # For the for loop
2024                     # If no user value or default kicks in but the hex/int has
2025                     # an active range, then the low end of the range is used,
2026                     # provided it's > 0, with "0x" prepended as appropriate.
2027                     if has_active_range and low > 0:
2028                         new_val = (hex(low) if self.type == HEX else str(low))
2029
2030         elif self.type == STRING:
2031             use_defaults = True
2032
2033             if vis != "n":
2034                 self.write_to_conf = True
2035                 if self.user_val is not None:
2036                     new_val = self.user_val
2037                     use_defaults = False
2038
2039             if use_defaults:
2040                 for val_expr, cond_expr in self.def_exprs:
2041                     if self.config._eval_expr(cond_expr) != "n":
2042                         self.write_to_conf = True
2043                         new_val = _str_val(val_expr)
2044                         break
2045
2046         self.cached_val = new_val
2047         return new_val
2048
2049     def get_user_value(self):
2050         """Returns the value assigned to the symbol in a .config or via
2051         Symbol.set_user_value() (provided the value was valid for the type of
2052         the symbol). Returns None in case of no user value."""
2053         return self.user_val
2054
2055     def get_upper_bound(self):
2056         """For string/hex/int symbols and for bool and tristate symbols that
2057         cannot be modified (see is_modifiable()), returns None.
2058
2059         Otherwise, returns the highest value the symbol can be set to with
2060         Symbol.set_user_value() (that will not be truncated): one of "m" or
2061         "y", arranged from lowest to highest. This corresponds to the highest
2062         value the symbol could be given in e.g. the 'make menuconfig'
2063         interface.
2064
2065         See also the tri_less*() and tri_greater*() functions, which could come
2066         in handy."""
2067         if self.type != BOOL and self.type != TRISTATE:
2068             return None
2069         rev_dep = self.config._eval_expr(self.rev_dep)
2070         # A bool selected to "m" gets promoted to "y", pinning it
2071         if rev_dep == "m" and self.type == BOOL:
2072             return None
2073         vis = _get_visibility(self)
2074         if TRI_TO_INT[vis] > TRI_TO_INT[rev_dep]:
2075             return vis
2076         return None
2077
2078     def get_lower_bound(self):
2079         """For string/hex/int symbols and for bool and tristate symbols that
2080         cannot be modified (see is_modifiable()), returns None.
2081
2082         Otherwise, returns the lowest value the symbol can be set to with
2083         Symbol.set_user_value() (that will not be truncated): one of "n" or
2084         "m", arranged from lowest to highest. This corresponds to the lowest
2085         value the symbol could be given in e.g. the 'make menuconfig'
2086         interface.
2087
2088         See also the tri_less*() and tri_greater*() functions, which could come
2089         in handy."""
2090         if self.type != BOOL and self.type != TRISTATE:
2091             return None
2092         rev_dep = self.config._eval_expr(self.rev_dep)
2093         # A bool selected to "m" gets promoted to "y", pinning it
2094         if rev_dep == "m" and self.type == BOOL:
2095             return None
2096         if TRI_TO_INT[_get_visibility(self)] > TRI_TO_INT[rev_dep]:
2097             return rev_dep
2098         return None
2099
2100     def get_assignable_values(self):
2101         """For string/hex/int symbols and for bool and tristate symbols that
2102         cannot be modified (see is_modifiable()), returns the empty list.
2103
2104         Otherwise, returns a list containing the user values that can be
2105         assigned to the symbol (that won't be truncated). Usage example:
2106
2107         if "m" in sym.get_assignable_values():
2108             sym.set_user_value("m")
2109
2110         This is basically a more convenient interface to
2111         get_lower/upper_bound() when wanting to test if a particular tristate
2112         value can be assigned."""
2113         if self.type != BOOL and self.type != TRISTATE:
2114             return []
2115         rev_dep = self.config._eval_expr(self.rev_dep)
2116         # A bool selected to "m" gets promoted to "y", pinning it
2117         if rev_dep == "m" and self.type == BOOL:
2118             return []
2119         res = ["n", "m", "y"][TRI_TO_INT[rev_dep] :
2120                               TRI_TO_INT[_get_visibility(self)] + 1]
2121         return res if len(res) > 1 else []
2122
2123     def get_visibility(self):
2124         """Returns the visibility of the symbol: one of "n", "m" or "y". For
2125         bool and tristate symbols, this is an upper bound on the value users
2126         can set for the symbol. For other types of symbols, a visibility of "n"
2127         means the user value will be ignored. A visibility of "n" corresponds
2128         to not being visible in the 'make *config' interfaces.
2129
2130         Example (assuming we're running with modules enabled -- i.e., MODULES
2131         set to 'y'):
2132
2133         # Assume this has been assigned 'n'
2134         config N_SYM
2135             tristate "N_SYM"
2136
2137         # Assume this has been assigned 'm'
2138         config M_SYM
2139             tristate "M_SYM"
2140
2141         # Has visibility 'n'
2142         config A
2143             tristate "A"
2144             depends on N_SYM
2145
2146         # Has visibility 'm'
2147         config B
2148             tristate "B"
2149             depends on M_SYM
2150
2151         # Has visibility 'y'
2152         config C
2153             tristate "C"
2154
2155         # Has no prompt, and hence visibility 'n'
2156         config D
2157             tristate
2158
2159         Having visibility be tri-valued ensures that e.g. a symbol cannot be
2160         set to "y" by the user if it depends on a symbol with value "m", which
2161         wouldn't be safe.
2162
2163         You should probably look at get_lower/upper_bound(),
2164         get_assignable_values() and is_modifiable() before using this."""
2165         return _get_visibility(self)
2166
2167     def get_referenced_symbols(self, refs_from_enclosing=False):
2168         """Returns the set() of all symbols referenced by this symbol. For
2169         example, the symbol defined by
2170
2171         config FOO
2172             bool
2173             prompt "foo" if A && B
2174             default C if D
2175             depends on E
2176             select F if G
2177
2178         references the symbols A through G.
2179
2180         refs_from_enclosing (default: False): If True, the symbols referenced
2181            by enclosing menus and ifs will be included in the result."""
2182         return self.all_referenced_syms if refs_from_enclosing else \
2183                self.referenced_syms
2184
2185     def get_selected_symbols(self):
2186         """Returns the set() of all symbols X for which this symbol has a
2187         'select X' or 'select X if Y' (regardless of whether Y is satisfied or
2188         not). This is a subset of the symbols returned by
2189         get_referenced_symbols()."""
2190         return self.selected_syms
2191
2192     def set_user_value(self, v):
2193         """Sets the user value of the symbol.
2194
2195         Equal in effect to assigning the value to the symbol within a .config
2196         file. Use get_lower/upper_bound() or get_assignable_values() to find
2197         the range of currently assignable values for bool and tristate symbols;
2198         setting values outside this range will cause the user value to differ
2199         from the result of Symbol.get_value() (be truncated). Values that are
2200         invalid for the type (such as a_bool.set_user_value("foo")) are
2201         ignored, and a warning is emitted if an attempt is made to assign such
2202         a value.
2203
2204         For any type of symbol, is_modifiable() can be used to check if a user
2205         value will currently have any effect on the symbol, as determined by
2206         its visibility and range of assignable values. Any value that is valid
2207         for the type (bool, tristate, etc.) will end up being reflected in
2208         get_user_value() though, and might have an effect later if conditions
2209         change. To get rid of the user value, use unset_user_value().
2210
2211         Any symbols dependent on the symbol are (recursively) invalidated, so
2212         things will just work with regards to dependencies.
2213
2214         v: The user value to give to the symbol."""
2215         self._set_user_value_no_invalidate(v, False)
2216
2217         # There might be something more efficient you could do here, but play
2218         # it safe.
2219         if self.name == "MODULES":
2220             self.config._invalidate_all()
2221             return
2222
2223         self._invalidate()
2224         self._invalidate_dependent()
2225
2226     def unset_user_value(self):
2227         """Resets the user value of the symbol, as if the symbol had never
2228         gotten a user value via Config.load_config() or
2229         Symbol.set_user_value()."""
2230         self._unset_user_value_no_recursive_invalidate()
2231         self._invalidate_dependent()
2232
2233     def is_modifiable(self):
2234         """Returns True if the value of the symbol could be modified by calling
2235         Symbol.set_user_value().
2236
2237         For bools and tristates, this corresponds to the symbol being visible
2238         in the 'make menuconfig' interface and not already being pinned to a
2239         specific value (e.g. because it is selected by another symbol).
2240
2241         For strings and numbers, this corresponds to just being visible. (See
2242         Symbol.get_visibility().)"""
2243         if self.is_special_:
2244             return False
2245         if self.type == BOOL or self.type == TRISTATE:
2246             rev_dep = self.config._eval_expr(self.rev_dep)
2247             # A bool selected to "m" gets promoted to "y", pinning it
2248             if rev_dep == "m" and self.type == BOOL:
2249                 return False
2250             return TRI_TO_INT[_get_visibility(self)] > TRI_TO_INT[rev_dep]
2251         return _get_visibility(self) != "n"
2252
2253     def is_defined(self):
2254         """Returns False if the symbol is referred to in the Kconfig but never
2255         actually defined."""
2256         return self.is_defined_
2257
2258     def is_special(self):
2259         """Returns True if the symbol is one of the special symbols n, m, y, or
2260         UNAME_RELEASE, or gets its value from the environment."""
2261         return self.is_special_
2262
2263     def is_from_environment(self):
2264         """Returns True if the symbol gets its value from the environment."""
2265         return self.is_from_env
2266
2267     def has_ranges(self):
2268         """Returns True if the symbol is of type INT or HEX and has ranges that
2269         limit what values it can take on."""
2270         return bool(self.ranges)
2271
2272     def is_choice_symbol(self):
2273         """Returns True if the symbol is in a choice statement and is an actual
2274         choice symbol (see Choice.get_symbols())."""
2275         return self.is_choice_sym
2276
2277     def is_choice_selection(self):
2278         """Returns True if the symbol is contained in a choice statement and is
2279         the selected item. Equivalent to
2280
2281         sym.is_choice_symbol() and sym.get_parent().get_selection() is sym"""
2282         return self.is_choice_sym and self.parent.get_selection() is self
2283
2284     def is_allnoconfig_y(self):
2285         """Returns True if the symbol has the 'allnoconfig_y' option set."""
2286         return self.allnoconfig_y
2287
2288     def __str__(self):
2289         """Returns a string containing various information about the symbol."""
2290         return self.config._get_sym_or_choice_str(self)
2291
2292     #
2293     # Private methods
2294     #
2295
2296     def __init__(self):
2297         """Symbol constructor -- not intended to be called directly by
2298         Kconfiglib clients."""
2299
2300         self.name = None
2301         self.type = UNKNOWN
2302         self.prompts = []
2303         self.def_exprs = [] # 'default' properties
2304         self.ranges = [] # 'range' properties (for int and hex)
2305         self.help = None # Help text
2306         self.rev_dep = "n" # Reverse (select-related) dependencies
2307         self.config = None
2308         self.parent = None
2309
2310         self.user_val = None # Value set by user
2311
2312         # The prompt, default value and select conditions without any
2313         # dependencies from menus and ifs propagated to them
2314         self.orig_prompts = []
2315         self.orig_def_exprs = []
2316         self.orig_selects = []
2317
2318         # Dependencies inherited from containing menus and ifs
2319         self.deps_from_containing = None
2320         # The set of symbols referenced by this symbol (see
2321         # get_referenced_symbols())
2322         self.referenced_syms = set()
2323         # The set of symbols selected by this symbol (see
2324         # get_selected_symbols())
2325         self.selected_syms = set()
2326         # Like 'referenced_syms', but includes symbols from
2327         # dependencies inherited from enclosing menus and ifs
2328         self.all_referenced_syms = set()
2329
2330         # This records only dependencies specified with 'depends on'. Needed
2331         # when determining actual choice items (hrrrr...). See also
2332         # Choice._determine_actual_symbols().
2333         self.menu_dep = None
2334
2335         # See Symbol.get_ref/def_locations().
2336         self.def_locations = []
2337         self.ref_locations = []
2338
2339         # Populated in Config._build_dep() after parsing. Links the symbol to
2340         # the symbols that immediately depend on it (in a caching/invalidation
2341         # sense). The total set of dependent symbols for the symbol (the
2342         # transitive closure) is calculated on an as-needed basis in
2343         # _get_dependent().
2344         self.dep = set()
2345
2346         # Cached values
2347
2348         # Caches the calculated value
2349         self.cached_val = None
2350         # Caches the visibility, which acts as an upper bound on the value
2351         self.cached_visibility = None
2352         # Caches the total list of dependent symbols. Calculated in
2353         # _get_dependent().
2354         self.cached_deps = None
2355
2356         # Flags
2357
2358         # Does the symbol have an entry in the Kconfig file? The trailing
2359         # underscore avoids a collision with is_defined().
2360         self.is_defined_ = False
2361         # Should the symbol get an entry in .config?
2362         self.write_to_conf = False
2363         # Set to true when _make_conf() is called on a symbol, so that symbols
2364         # defined in multiple locations only get one .config entry. We need to
2365         # reset it prior to writing out a new .config.
2366         self.already_written = False
2367         # This is set to True for "actual" choice symbols; see
2368         # Choice._determine_actual_symbols().
2369         self.is_choice_sym = False
2370         # Does the symbol get its value in some special way, e.g. from the
2371         # environment or by being one of the special symbols n, m, and y? If
2372         # so, the value is stored in self.cached_val, which is never
2373         # invalidated. The trailing underscore avoids a collision with
2374         # is_special().
2375         self.is_special_ = False
2376         # Does the symbol get its value from the environment?
2377         self.is_from_env = False
2378         # Does the symbol have the 'allnoconfig_y' option set?
2379         self.allnoconfig_y = False
2380
2381     def _invalidate(self):
2382         if self.is_special_:
2383             return
2384
2385         if self.is_choice_sym:
2386             self.parent._invalidate()
2387
2388         self.cached_val = None
2389         self.cached_visibility = None
2390
2391     def _invalidate_dependent(self):
2392         for sym in self._get_dependent():
2393             sym._invalidate()
2394
2395     def _set_user_value_no_invalidate(self, v, suppress_load_warnings):
2396         """Like set_user_value(), but does not invalidate any symbols.
2397
2398         suppress_load_warnings: some warnings are annoying when loading a
2399            .config that can be helpful when manually invoking set_user_value().
2400            This flag is set to True to suppress such warnings.
2401
2402            Perhaps this could be made optional for load_config() instead."""
2403
2404         if self.is_special_:
2405             if self.is_from_env:
2406                 self.config._warn('attempt to assign the value "{0}" to the '
2407                                   'symbol {1}, which gets its value from the '
2408                                   'environment. Assignment ignored.'
2409                                   .format(v, self.name))
2410             else:
2411                 self.config._warn('attempt to assign the value "{0}" to the '
2412                                   'special symbol {1}. Assignment ignored.'
2413                                   .format(v, self.name))
2414             return
2415
2416         if not self.is_defined_:
2417             filename, linenr = self.ref_locations[0]
2418             if self.config.print_undef_assign:
2419                 _stderr_msg('note: attempt to assign the value "{0}" to {1}, '
2420                             "which is referenced at {2}:{3} but never "
2421                             "defined. Assignment ignored."
2422                             .format(v, self.name, filename, linenr))
2423             return
2424
2425         # Check if the value is valid for our type
2426         if not ((self.type == BOOL     and (v == "y" or v == "n")   ) or
2427                 (self.type == TRISTATE and (v == "y" or v == "m" or
2428                                             v == "n")               ) or
2429                 (self.type == STRING                                ) or
2430                 (self.type == INT      and _is_base_n(v, 10)        ) or
2431                 (self.type == HEX      and _is_base_n(v, 16)        )):
2432             self.config._warn('the value "{0}" is invalid for {1}, which has '
2433                               "type {2}. Assignment ignored."
2434                               .format(v, self.name, TYPENAME[self.type]))
2435             return
2436
2437         if not self.prompts and not suppress_load_warnings:
2438             self.config._warn('assigning "{0}" to the symbol {1} which '
2439                               'lacks prompts and thus has visibility "n". '
2440                               'The assignment will have no effect.'
2441                               .format(v, self.name))
2442
2443         self.user_val = v
2444
2445         if self.is_choice_sym and (self.type == BOOL or self.type == TRISTATE):
2446             choice = self.parent
2447             if v == "y":
2448                 choice.user_val = self
2449                 choice.user_mode = "y"
2450             elif v == "m":
2451                 choice.user_val = None
2452                 choice.user_mode = "m"
2453
2454     def _unset_user_value_no_recursive_invalidate(self):
2455         self._invalidate()
2456         self.user_val = None
2457
2458         if self.is_choice_sym:
2459             self.parent._unset_user_value()
2460
2461     def _make_conf(self, append_fn):
2462         if self.already_written:
2463             return
2464
2465         self.already_written = True
2466
2467         # Note: write_to_conf is determined in get_value()
2468         val = self.get_value()
2469         if not self.write_to_conf:
2470             return
2471
2472         if self.type == BOOL or self.type == TRISTATE:
2473             if val == "y" or val == "m":
2474                 append_fn("CONFIG_{0}={1}".format(self.name, val))
2475             else:
2476                 append_fn("# CONFIG_{0} is not set".format(self.name))
2477
2478         elif self.type == INT or self.type == HEX:
2479             append_fn("CONFIG_{0}={1}".format(self.name, val))
2480
2481         elif self.type == STRING:
2482             # Escape \ and "
2483             append_fn('CONFIG_{0}="{1}"'
2484                       .format(self.name,
2485                               val.replace("\\", "\\\\").replace('"', '\\"')))
2486
2487         else:
2488             _internal_error("Internal error while creating .config: unknown "
2489                             'type "{0}".'.format(self.type))
2490
2491     def _get_dependent(self):
2492         """Returns the set of symbols that should be invalidated if the value
2493         of the symbol changes, because they might be affected by the change.
2494         Note that this is an internal API -- it's probably of limited
2495         usefulness to clients."""
2496         if self.cached_deps is not None:
2497             return self.cached_deps
2498
2499         res = set(self.dep)
2500         for s in self.dep:
2501             res |= s._get_dependent()
2502
2503         if self.is_choice_sym:
2504             # Choice symbols also depend (recursively) on their siblings. The
2505             # siblings are not included in 'dep' to avoid dependency loops.
2506             for sibling in self.parent.actual_symbols:
2507                 if sibling is not self:
2508                     res.add(sibling)
2509                     res |= sibling.dep
2510                     for s in sibling.dep:
2511                         res |= s._get_dependent()
2512
2513         self.cached_deps = res
2514         return res
2515
2516     def _has_auto_menu_dep_on(self, on):
2517         """See Choice._determine_actual_symbols()."""
2518         if not isinstance(self.parent, Choice):
2519             _internal_error("Attempt to determine auto menu dependency for "
2520                             "symbol ouside of choice.")
2521
2522         if not self.prompts:
2523             # If we have no prompt, use the menu dependencies instead (what was
2524             # specified with 'depends on')
2525             return self.menu_dep is not None and \
2526                    self.config._expr_depends_on(self.menu_dep, on)
2527
2528         for _, cond_expr in self.prompts:
2529             if self.config._expr_depends_on(cond_expr, on):
2530                 return True
2531
2532         return False
2533
2534 class Menu(Item):
2535
2536     """Represents a menu statement."""
2537
2538     #
2539     # Public interface
2540     #
2541
2542     def get_config(self):
2543         """Return the Config instance this menu is from."""
2544         return self.config
2545
2546     def get_title(self):
2547         """Returns the title text of the menu."""
2548         return self.title
2549
2550     def get_parent(self):
2551         """Returns the menu or choice statement that contains the menu, or
2552         None if the menu is at the top level. Note that if statements are
2553         treated as syntactic sugar and do not have an explicit class
2554         representation."""
2555         return self.parent
2556
2557     def get_location(self):
2558         """Returns the location of the menu as a (filename, linenr) tuple,
2559         where filename is a string and linenr an int."""
2560         return (self.filename, self.linenr)
2561
2562     def get_items(self, recursive=False):
2563         """Returns a list containing the items (symbols, menus, choice
2564         statements and comments) in in the menu, in the same order that the
2565         items appear within the menu.
2566
2567         recursive (default: False): True if items contained in items within the
2568            menu should be included recursively (preorder)."""
2569
2570         if not recursive:
2571             return self.block
2572
2573         res = []
2574         for item in self.block:
2575             res.append(item)
2576             if isinstance(item, Menu):
2577                 res.extend(item.get_items(True))
2578             elif isinstance(item, Choice):
2579                 res.extend(item.get_items())
2580         return res
2581
2582     def get_symbols(self, recursive=False):
2583         """Returns a list containing the symbols in the menu, in the same order
2584         that they appear within the menu.
2585
2586         recursive (default: False): True if symbols contained in items within
2587            the menu should be included recursively."""
2588
2589         return [item for item in self.get_items(recursive) if
2590                 isinstance(item, Symbol)]
2591
2592     def get_visibility(self):
2593         """Returns the visibility of the menu. This also affects the visibility
2594         of subitems. See also Symbol.get_visibility()."""
2595         return self.config._eval_expr(self.dep_expr)
2596
2597     def get_visible_if_visibility(self):
2598         """Returns the visibility the menu gets from its 'visible if'
2599         condition. "y" if the menu has no 'visible if' condition."""
2600         return self.config._eval_expr(self.visible_if_expr)
2601
2602     def get_referenced_symbols(self, refs_from_enclosing=False):
2603         """See Symbol.get_referenced_symbols()."""
2604         return self.all_referenced_syms if refs_from_enclosing else \
2605                self.referenced_syms
2606
2607     def __str__(self):
2608         """Returns a string containing various information about the menu."""
2609         depends_on_str = self.config._expr_val_str(self.orig_deps,
2610                                                    "(no dependencies)")
2611         visible_if_str = self.config._expr_val_str(self.visible_if_expr,
2612                                                    "(no dependencies)")
2613
2614         additional_deps_str = " " + \
2615           self.config._expr_val_str(self.deps_from_containing,
2616                                     "(no additional dependencies)")
2617
2618         return _lines("Menu",
2619                       "Title                     : " + self.title,
2620                       "'depends on' dependencies : " + depends_on_str,
2621                       "'visible if' dependencies : " + visible_if_str,
2622                       "Additional dependencies from enclosing menus and "
2623                         "ifs:",
2624                       additional_deps_str,
2625                       "Location: {0}:{1}".format(self.filename, self.linenr))
2626
2627     #
2628     # Private methods
2629     #
2630
2631     def __init__(self):
2632         """Menu constructor -- not intended to be called directly by
2633         Kconfiglib clients."""
2634
2635         self.title = None
2636         self.dep_expr = None
2637         self.visible_if_expr = None
2638         self.block = None
2639         self.config = None
2640         self.parent = None
2641
2642         # Dependency expression without dependencies from enclosing menus and
2643         # ifs propagated
2644         self.orig_deps = None
2645
2646         # Dependencies inherited from containing menus and ifs
2647         self.deps_from_containing = None
2648         # The set of symbols referenced by this menu (see
2649         # get_referenced_symbols())
2650         self.referenced_syms = set()
2651         # Like 'referenced_syms', but includes symbols from
2652         # dependencies inherited from enclosing menus and ifs
2653         self.all_referenced_syms = None
2654
2655         self.filename = None
2656         self.linenr = None
2657
2658     def _make_conf(self, append_fn):
2659         if self.config._eval_expr(self.dep_expr) != "n" and \
2660            self.config._eval_expr(self.visible_if_expr) != "n":
2661             append_fn("\n#\n# {0}\n#".format(self.title))
2662         _make_block_conf(self.block, append_fn)
2663
2664 class Choice(Item):
2665
2666     """Represents a choice statement. A choice can be in one of three modes:
2667
2668     "n" - The choice is not visible and no symbols can be selected.
2669
2670     "m" - Any number of symbols can be set to "m". The rest will be "n". This
2671           is safe since potentially conflicting options don't actually get
2672           compiled into the kernel simultaneously with "m".
2673
2674     "y" - One symbol will be "y" while the rest are "n".
2675
2676     Only tristate choices can be in "m" mode, and the visibility of the choice
2677     is an upper bound on the mode, so that e.g. a choice that depends on a
2678     symbol with value "m" will be in "m" mode.
2679
2680     The mode changes automatically when a value is assigned to a symbol within
2681     the choice.
2682
2683     See Symbol.get_visibility() too."""
2684
2685     #
2686     # Public interface
2687     #
2688
2689     def get_config(self):
2690         """Returns the Config instance this choice is from."""
2691         return self.config
2692
2693     def get_name(self):
2694         """For named choices, returns the name. Returns None for unnamed
2695         choices. No named choices appear anywhere in the kernel Kconfig files
2696         as of Linux 3.7.0-rc8."""
2697         return self.name
2698
2699     def get_type(self):
2700         """Returns the type of the choice. See Symbol.get_type()."""
2701         return self.type
2702
2703     def get_prompts(self):
2704         """Returns a list of prompts defined for the choice, in the order they
2705         appear in the configuration files. Returns the empty list for choices
2706         with no prompt.
2707
2708         This list will have a single entry for the vast majority of choices
2709         having prompts, but having multiple prompts for a single choice is
2710         possible through having multiple 'choice' entries for it (though I'm
2711         not sure if that ever happens in practice)."""
2712         return [prompt for prompt, _ in self.orig_prompts]
2713
2714     def get_help(self):
2715         """Returns the help text of the choice, or None if the choice has no
2716         help text."""
2717         return self.help
2718
2719     def get_parent(self):
2720         """Returns the menu or choice statement that contains the choice, or
2721         None if the choice is at the top level. Note that if statements are
2722         treated as syntactic sugar and do not have an explicit class
2723         representation."""
2724         return self.parent
2725
2726     def get_def_locations(self):
2727         """Returns a list of (filename, linenr) tuples, where filename (string)
2728         and linenr (int) represent a location where the choice is defined. For
2729         the vast majority of choices (all of them as of Linux 3.7.0-rc8) this
2730         list will only contain one element, but its possible for named choices
2731         to be defined in multiple locations."""
2732         return self.def_locations
2733
2734     def get_selection(self):
2735         """Returns the symbol selected (either by the user or through
2736         defaults), or None if either no symbol is selected or the mode is not
2737         "y"."""
2738         if self.cached_selection is not None:
2739             if self.cached_selection == NO_SELECTION:
2740                 return None
2741             return self.cached_selection
2742
2743         if self.get_mode() != "y":
2744             return self._cache_ret(None)
2745
2746         # User choice available?
2747         if self.user_val is not None and _get_visibility(self.user_val) == "y":
2748             return self._cache_ret(self.user_val)
2749
2750         if self.optional:
2751             return self._cache_ret(None)
2752
2753         return self._cache_ret(self.get_selection_from_defaults())
2754
2755     def get_selection_from_defaults(self):
2756         """Like Choice.get_selection(), but acts as if no symbol has been
2757         selected by the user and no 'optional' flag is in effect."""
2758
2759         if not self.actual_symbols:
2760             return None
2761
2762         for symbol, cond_expr in self.def_exprs:
2763             if self.config._eval_expr(cond_expr) != "n":
2764                 chosen_symbol = symbol
2765                 break
2766         else:
2767             chosen_symbol = self.actual_symbols[0]
2768
2769         # Is the chosen symbol visible?
2770         if _get_visibility(chosen_symbol) != "n":
2771             return chosen_symbol
2772         # Otherwise, pick the first visible symbol
2773         for sym in self.actual_symbols:
2774             if _get_visibility(sym) != "n":
2775                 return sym
2776         return None
2777
2778     def get_user_selection(self):
2779         """If the choice is in "y" mode and has a user-selected symbol, returns
2780         that symbol. Otherwise, returns None."""
2781         return self.user_val
2782
2783     def get_items(self):
2784         """Gets all items contained in the choice in the same order as within
2785         the configuration ("items" instead of "symbols" since choices and
2786         comments might appear within choices. This only happens in one place as
2787         of Linux 3.7.0-rc8, in drivers/usb/gadget/Kconfig)."""
2788         return self.block
2789
2790     def get_symbols(self):
2791         """Returns a list containing the choice's symbols.
2792
2793         A quirk (perhaps a bug) of Kconfig is that you can put items within a
2794         choice that will not be considered members of the choice insofar as
2795         selection is concerned. This happens for example if one symbol within a
2796         choice 'depends on' the symbol preceding it, or if you put non-symbol
2797         items within choices.
2798
2799         As of Linux 3.7.0-rc8, this seems to be used intentionally in one
2800         place: drivers/usb/gadget/Kconfig.
2801
2802         This function returns the "proper" symbols of the choice in the order
2803         they appear in the choice, excluding such items. If you want all items
2804         in the choice, use get_items()."""
2805         return self.actual_symbols
2806
2807     def get_referenced_symbols(self, refs_from_enclosing=False):
2808         """See Symbol.get_referenced_symbols()."""
2809         return self.all_referenced_syms if refs_from_enclosing else \
2810                self.referenced_syms
2811
2812     def get_visibility(self):
2813         """Returns the visibility of the choice statement: one of "n", "m" or
2814         "y". This acts as an upper limit on the mode of the choice (though bool
2815         choices can only have the mode "y"). See the class documentation for an
2816         explanation of modes."""
2817         return _get_visibility(self)
2818
2819     def get_mode(self):
2820         """Returns the mode of the choice. See the class documentation for
2821         an explanation of modes."""
2822         minimum_mode = "n" if self.optional else "m"
2823         mode = self.user_mode if self.user_mode is not None else minimum_mode
2824         mode = self.config._eval_min(mode, _get_visibility(self))
2825
2826         # Promote "m" to "y" for boolean choices
2827         if mode == "m" and self.type == BOOL:
2828             return "y"
2829
2830         return mode
2831
2832     def is_optional(self):
2833         """Returns True if the choice has the 'optional' flag set (and so will
2834         default to "n" mode)."""
2835         return self.optional
2836
2837     def __str__(self):
2838         """Returns a string containing various information about the choice
2839         statement."""
2840         return self.config._get_sym_or_choice_str(self)
2841
2842     #
2843     # Private methods
2844     #
2845
2846     def __init__(self):
2847         """Choice constructor -- not intended to be called directly by
2848         Kconfiglib clients."""
2849
2850         self.name = None # Yes, choices can be named
2851         self.type = UNKNOWN
2852         self.prompts = []
2853         self.def_exprs = [] # 'default' properties
2854         self.help = None # Help text
2855         self.block = None # List of contained items
2856         self.config = None
2857         self.parent = None
2858
2859         self.user_val = None
2860         self.user_mode = None
2861
2862         # We need to filter out symbols that appear within the choice block but
2863         # are not considered choice items (see
2864         # Choice._determine_actual_symbols()) This list holds the "actual"
2865         # choice items.
2866         self.actual_symbols = []
2867
2868         # The prompts and default values without any dependencies from
2869         # enclosing menus and ifs propagated
2870         self.orig_prompts = []
2871         self.orig_def_exprs = []
2872
2873         # Dependencies inherited from containing menus and ifs
2874         self.deps_from_containing = None
2875         # The set of symbols referenced by this choice (see
2876         # get_referenced_symbols())
2877         self.referenced_syms = set()
2878         # Like 'referenced_syms', but includes symbols from
2879         # dependencies inherited from enclosing menus and ifs
2880         self.all_referenced_syms = set()
2881
2882         # See Choice.get_def_locations()
2883         self.def_locations = []
2884
2885         # Cached values
2886         self.cached_selection = None
2887         self.cached_visibility = None
2888
2889         self.optional = False
2890
2891     def _determine_actual_symbols(self):
2892         """If a symbol's visibility depends on the preceding symbol within a
2893         choice, it is no longer viewed as a choice item. (This is quite
2894         possibly a bug, but some things consciously use it... ugh. It stems
2895         from automatic submenu creation.) In addition, it's possible to have
2896         choices and comments within choices, and those shouldn't be considered
2897         choice items either. Only drivers/usb/gadget/Kconfig seems to depend on
2898         any of this. This method computes the "actual" items in the choice and
2899         sets the is_choice_sym flag on them (retrieved via is_choice_symbol()).
2900
2901         Don't let this scare you: an earlier version simply checked for a
2902         sequence of symbols where all symbols after the first appeared in the
2903         'depends on' expression of the first, and that worked fine.  The added
2904         complexity is to be future-proof in the event that
2905         drivers/usb/gadget/Kconfig turns even more sinister. It might very well
2906         be overkilling things (especially if that file is refactored ;)."""
2907
2908         # Items might depend on each other in a tree structure, so we need a
2909         # stack to keep track of the current tentative parent
2910         stack = []
2911
2912         for item in self.block:
2913             if not isinstance(item, Symbol):
2914                 stack = []
2915                 continue
2916
2917             while stack:
2918                 if item._has_auto_menu_dep_on(stack[-1]):
2919                     # The item should not be viewed as a choice item, so don't
2920                     # set item.is_choice_sym
2921                     stack.append(item)
2922                     break
2923                 else:
2924                     stack.pop()
2925             else:
2926                 item.is_choice_sym = True
2927                 self.actual_symbols.append(item)
2928                 stack.append(item)
2929
2930     def _cache_ret(self, selection):
2931         # As None is used to indicate the lack of a cached value we can't use
2932         # that to cache the fact that the choice has no selection. Instead, we
2933         # use the symbolic constant NO_SELECTION.
2934         if selection is None:
2935             self.cached_selection = NO_SELECTION
2936         else:
2937             self.cached_selection = selection
2938
2939         return selection
2940
2941     def _invalidate(self):
2942         self.cached_selection = None
2943         self.cached_visibility = None
2944
2945     def _unset_user_value(self):
2946         self._invalidate()
2947         self.user_val = None
2948         self.user_mode = None
2949
2950     def _make_conf(self, append_fn):
2951         _make_block_conf(self.block, append_fn)
2952
2953 class Comment(Item):
2954
2955     """Represents a comment statement."""
2956
2957     #
2958     # Public interface
2959     #
2960
2961     def get_config(self):
2962         """Returns the Config instance this comment is from."""
2963         return self.config
2964
2965     def get_text(self):
2966         """Returns the text of the comment."""
2967         return self.text
2968
2969     def get_parent(self):
2970         """Returns the menu or choice statement that contains the comment, or
2971         None if the comment is at the top level. Note that if statements are
2972         treated as syntactic sugar and do not have an explicit class
2973         representation."""
2974         return self.parent
2975
2976     def get_location(self):
2977         """Returns the location of the comment as a (filename, linenr) tuple,
2978         where filename is a string and linenr an int."""
2979         return (self.filename, self.linenr)
2980
2981     def get_visibility(self):
2982         """Returns the visibility of the comment. See also
2983         Symbol.get_visibility()."""
2984         return self.config._eval_expr(self.dep_expr)
2985
2986     def get_referenced_symbols(self, refs_from_enclosing=False):
2987         """See Symbol.get_referenced_symbols()."""
2988         return self.all_referenced_syms if refs_from_enclosing else \
2989                self.referenced_syms
2990
2991     def __str__(self):
2992         """Returns a string containing various information about the
2993         comment."""
2994         dep_str = self.config._expr_val_str(self.orig_deps,
2995                                             "(no dependencies)")
2996
2997         additional_deps_str = " " + \
2998           self.config._expr_val_str(self.deps_from_containing,
2999                                     "(no additional dependencies)")
3000
3001         return _lines("Comment",
3002                       "Text: "         + str(self.text),
3003                       "Dependencies: " + dep_str,
3004                       "Additional dependencies from enclosing menus and "
3005                         "ifs:",
3006                       additional_deps_str,
3007                       "Location: {0}:{1}".format(self.filename, self.linenr))
3008
3009     #
3010     # Private methods
3011     #
3012
3013     def __init__(self):
3014         """Comment constructor -- not intended to be called directly by
3015         Kconfiglib clients."""
3016
3017         self.text = None
3018         self.dep_expr = None
3019         self.config = None
3020         self.parent = None
3021
3022         # Dependency expression without dependencies from enclosing menus and
3023         # ifs propagated
3024         self.orig_deps = None
3025
3026         # Dependencies inherited from containing menus and ifs
3027         self.deps_from_containing = None
3028         # The set of symbols referenced by this comment (see
3029         # get_referenced_symbols())
3030         self.referenced_syms = set()
3031         # Like 'referenced_syms', but includes symbols from
3032         # dependencies inherited from enclosing menus and ifs
3033         self.all_referenced_syms = None
3034
3035         self.filename = None
3036         self.linenr = None
3037
3038     def _make_conf(self, append_fn):
3039         if self.config._eval_expr(self.dep_expr) != "n":
3040             append_fn("\n#\n# {0}\n#".format(self.text))
3041
3042 class Kconfig_Syntax_Error(Exception):
3043     """Exception raised for syntax errors."""
3044     pass
3045
3046 class Internal_Error(Exception):
3047     """Exception raised for internal errors."""
3048     pass
3049
3050 #
3051 # Public functions
3052 #
3053
3054 def tri_less(v1, v2):
3055     """Returns True if the tristate v1 is less than the tristate v2, where "n",
3056     "m" and "y" are ordered from lowest to highest."""
3057     return TRI_TO_INT[v1] < TRI_TO_INT[v2]
3058
3059 def tri_less_eq(v1, v2):
3060     """Returns True if the tristate v1 is less than or equal to the tristate
3061     v2, where "n", "m" and "y" are ordered from lowest to highest."""
3062     return TRI_TO_INT[v1] <= TRI_TO_INT[v2]
3063
3064 def tri_greater(v1, v2):
3065     """Returns True if the tristate v1 is greater than the tristate v2, where
3066     "n", "m" and "y" are ordered from lowest to highest."""
3067     return TRI_TO_INT[v1] > TRI_TO_INT[v2]
3068
3069 def tri_greater_eq(v1, v2):
3070     """Returns True if the tristate v1 is greater than or equal to the tristate
3071     v2, where "n", "m" and "y" are ordered from lowest to highest."""
3072     return TRI_TO_INT[v1] >= TRI_TO_INT[v2]
3073
3074 #
3075 # Internal classes
3076 #
3077
3078 class _Feed(object):
3079
3080     """Class for working with sequences in a stream-like fashion; handy for
3081     tokens."""
3082
3083     # This would be more helpful on the item classes, but would remove some
3084     # flexibility
3085     __slots__ = ['items', 'length', 'i']
3086
3087     def __init__(self, items):
3088         self.items = items
3089         self.length = len(self.items)
3090         self.i = 0
3091
3092     def get_next(self):
3093         if self.i >= self.length:
3094             return None
3095         item = self.items[self.i]
3096         self.i += 1
3097         return item
3098
3099     def peek_next(self):
3100         return None if self.i >= self.length else self.items[self.i]
3101
3102     def check(self, token):
3103         """Check if the next token is 'token'. If so, remove it from the token
3104         feed and return True. Otherwise, leave it in and return False."""
3105         if self.i < self.length and self.items[self.i] == token:
3106             self.i += 1
3107             return True
3108         return False
3109
3110     def unget_all(self):
3111         self.i = 0
3112
3113 class _FileFeed(object):
3114
3115     """Feeds lines from a file. Keeps track of the filename and current line
3116     number. Joins any line ending in \\ with the following line. We need to be
3117     careful to get the line number right in the presence of continuation
3118     lines."""
3119
3120     __slots__ = ['filename', 'lines', 'length', 'linenr']
3121
3122     def __init__(self, filename):
3123         self.filename = _clean_up_path(filename)
3124         with open(filename, "r") as f:
3125             # No interleaving of I/O and processing yet. Don't know if it would
3126             # help.
3127             self.lines = f.readlines()
3128         self.length = len(self.lines)
3129         self.linenr = 0
3130
3131     def get_next(self):
3132         if self.linenr >= self.length:
3133             return None
3134         line = self.lines[self.linenr]
3135         self.linenr += 1
3136         while line.endswith("\\\n"):
3137             line = line[:-2] + self.lines[self.linenr]
3138             self.linenr += 1
3139         return line
3140
3141     def peek_next(self):
3142         linenr = self.linenr
3143         if linenr >= self.length:
3144             return None
3145         line = self.lines[linenr]
3146         while line.endswith("\\\n"):
3147             linenr += 1
3148             line = line[:-2] + self.lines[linenr]
3149         return line
3150
3151     def unget(self):
3152         self.linenr -= 1
3153         while self.lines[self.linenr].endswith("\\\n"):
3154             self.linenr -= 1
3155
3156     def next_nonblank(self):
3157         """Removes lines up to and including the next non-blank (not all-space)
3158         line and returns it. Returns None if there are no more non-blank
3159         lines."""
3160         while 1:
3161             line = self.get_next()
3162             if line is None or not line.isspace():
3163                 return line
3164
3165 #
3166 # Internal functions
3167 #
3168
3169 def _get_visibility(sc):
3170     """Symbols and Choices have a "visibility" that acts as an upper bound on
3171     the values a user can set for them, corresponding to the visibility in e.g.
3172     'make menuconfig'. This function calculates the visibility for the Symbol
3173     or Choice 'sc' -- the logic is nearly identical."""
3174     if sc.cached_visibility is None:
3175         vis = "n"
3176         for _, cond_expr in sc.prompts:
3177             vis = sc.config._eval_max(vis, cond_expr)
3178
3179         if isinstance(sc, Symbol) and sc.is_choice_sym:
3180             vis = sc.config._eval_min(vis, _get_visibility(sc.parent))
3181
3182         # Promote "m" to "y" if we're dealing with a non-tristate
3183         if vis == "m" and sc.type != TRISTATE:
3184             vis = "y"
3185
3186         sc.cached_visibility = vis
3187
3188     return sc.cached_visibility
3189
3190 def _make_and(e1, e2):
3191     """Constructs an AND (&&) expression. Performs trivial simplification.
3192     Nones equate to 'y'.
3193
3194     Note: returns None if e1 == e2 == None."""
3195     if e1 is None or e1 == "y":
3196         return e2
3197     if e2 is None or e2 == "y":
3198         return e1
3199
3200     # Prefer to merge argument lists if possible to reduce the number of nodes
3201
3202     if isinstance(e1, tuple) and e1[0] == AND:
3203         if isinstance(e2, tuple) and e2[0] == AND:
3204             return (AND, e1[1] + e2[1])
3205         return (AND, e1[1] + [e2])
3206
3207     if isinstance(e2, tuple) and e2[0] == AND:
3208         return (AND, e2[1] + [e1])
3209
3210     return (AND, [e1, e2])
3211
3212 def _make_or(e1, e2):
3213     """Constructs an OR (||) expression. Performs trivial simplification and
3214     avoids Nones. Nones equate to 'y', which is usually what we want, but needs
3215     to be kept in mind."""
3216
3217     # Perform trivial simplification and avoid None's (which
3218     # correspond to y's)
3219     if e1 is None or e2 is None or e1 == "y" or e2 == "y":
3220         return "y"
3221     if e1 == "n":
3222         return e2
3223
3224     # Prefer to merge argument lists if possible to reduce the number of nodes
3225
3226     if isinstance(e1, tuple) and e1[0] == OR:
3227         if isinstance(e2, tuple) and e2[0] == OR:
3228             return (OR, e1[1] + e2[1])
3229         return (OR, e1[1] + [e2])
3230
3231     if isinstance(e2, tuple) and e2[0] == OR:
3232         return (OR, e2[1] + [e1])
3233
3234     return (OR, [e1, e2])
3235
3236 def _get_expr_syms_rec(expr, res):
3237     """_get_expr_syms() helper. Recurses through expressions."""
3238     if isinstance(expr, Symbol):
3239         res.add(expr)
3240     elif isinstance(expr, str):
3241         return
3242     elif expr[0] == AND or expr[0] == OR:
3243         for term in expr[1]:
3244             _get_expr_syms_rec(term, res)
3245     elif expr[0] == NOT:
3246         _get_expr_syms_rec(expr[1], res)
3247     elif expr[0] == EQUAL or expr[0] == UNEQUAL:
3248         if isinstance(expr[1], Symbol):
3249             res.add(expr[1])
3250         if isinstance(expr[2], Symbol):
3251             res.add(expr[2])
3252     else:
3253         _internal_error("Internal error while fetching symbols from an "
3254                         "expression with token stream {0}.".format(expr))
3255
3256 def _get_expr_syms(expr):
3257     """Returns the set() of symbols appearing in expr."""
3258     res = set()
3259     if expr is not None:
3260         _get_expr_syms_rec(expr, res)
3261     return res
3262
3263 def _str_val(obj):
3264     """Returns the value of obj as a string. If obj is not a string (constant
3265     symbol), it must be a Symbol."""
3266     return obj if isinstance(obj, str) else obj.get_value()
3267
3268 def _make_block_conf(block, append_fn):
3269     """Returns a list of .config strings for a block (list) of items."""
3270
3271     # Collect the substrings in a list and later use join() instead of += to
3272     # build the final .config contents. With older Python versions, this yields
3273     # linear instead of quadratic complexity.
3274     for item in block:
3275         item._make_conf(append_fn)
3276
3277 def _sym_str_string(sym_or_str):
3278     if isinstance(sym_or_str, str):
3279         return '"' + sym_or_str + '"'
3280     return sym_or_str.name
3281
3282 def _intersperse(lst, op):
3283     """_expr_to_str() helper. Gets the string representation of each expression
3284     in lst and produces a list where op has been inserted between the
3285     elements."""
3286     if not lst:
3287         return ""
3288
3289     res = []
3290
3291     def handle_sub_expr(expr):
3292         no_parens = isinstance(expr, (str, Symbol)) or \
3293                     expr[0] in (EQUAL, UNEQUAL) or \
3294                     PRECEDENCE[op] <= PRECEDENCE[expr[0]]
3295         if not no_parens:
3296             res.append("(")
3297         res.extend(_expr_to_str_rec(expr))
3298         if not no_parens:
3299             res.append(")")
3300
3301     op_str = OP_TO_STR[op]
3302
3303     handle_sub_expr(lst[0])
3304     for expr in lst[1:]:
3305         res.append(op_str)
3306         handle_sub_expr(expr)
3307
3308     return res
3309
3310 def _expr_to_str_rec(expr):
3311     if expr is None:
3312         return [""]
3313
3314     if isinstance(expr, (Symbol, str)):
3315         return [_sym_str_string(expr)]
3316
3317     if expr[0] in (AND, OR):
3318         return _intersperse(expr[1], expr[0])
3319
3320     if expr[0] == NOT:
3321         need_parens = not isinstance(expr[1], (str, Symbol))
3322
3323         res = ["!"]
3324         if need_parens:
3325             res.append("(")
3326         res.extend(_expr_to_str_rec(expr[1]))
3327         if need_parens:
3328             res.append(")")
3329         return res
3330
3331     if expr[0] in (EQUAL, UNEQUAL):
3332         return [_sym_str_string(expr[1]),
3333                 OP_TO_STR[expr[0]],
3334                 _sym_str_string(expr[2])]
3335
3336 def _expr_to_str(expr):
3337     return "".join(_expr_to_str_rec(expr))
3338
3339 def _indentation(line):
3340     """Returns the length of the line's leading whitespace, treating tab stops
3341     as being spaced 8 characters apart."""
3342     line = line.expandtabs()
3343     return len(line) - len(line.lstrip())
3344
3345 def _deindent(line, indent):
3346     """Deindent 'line' by 'indent' spaces."""
3347     line = line.expandtabs()
3348     if len(line) <= indent:
3349         return line
3350     return line[indent:]
3351
3352 def _is_base_n(s, n):
3353     try:
3354         int(s, n)
3355         return True
3356     except ValueError:
3357         return False
3358
3359 def _lines(*args):
3360     """Returns a string consisting of all arguments, with newlines inserted
3361     between them."""
3362     return "\n".join(args)
3363
3364 def _comment(s):
3365     """Returns a new string with "#" inserted before each line in 's'."""
3366     if not s:
3367         return "#"
3368     res = "".join(["#" + line for line in s.splitlines(True)])
3369     if s.endswith("\n"):
3370         return res + "#"
3371     return res
3372
3373 def _clean_up_path(path):
3374     """Strips an initial "./" and any trailing slashes from 'path'."""
3375     if path.startswith("./"):
3376         path = path[2:]
3377     return path.rstrip("/")
3378
3379 def _build_msg(msg, filename, linenr):
3380     if filename is not None:
3381         msg = "{0}:{1}: ".format(_clean_up_path(filename), linenr) + msg
3382     return msg
3383
3384 def _stderr_msg(msg, filename, linenr):
3385     sys.stderr.write(_build_msg(msg, filename, linenr) + "\n")
3386
3387 def _tokenization_error(s, filename, linenr):
3388     loc = "" if filename is None else "{0}:{1}: ".format(filename, linenr)
3389     raise Kconfig_Syntax_Error("{0}Couldn't tokenize '{1}'"
3390                                .format(loc, s.strip()))
3391
3392 def _parse_error(s, msg, filename, linenr):
3393     loc = "" if filename is None else "{0}:{1}: ".format(filename, linenr)
3394     raise Kconfig_Syntax_Error("{0}Couldn't parse '{1}'{2}"
3395                                .format(loc, s.strip(),
3396                                        "." if msg is None else ": " + msg))
3397
3398 def _internal_error(msg):
3399     raise Internal_Error(msg +
3400       "\nSorry! You may want to send an email to ulfalizer a.t Google's "
3401       "email service to tell me about this. Include the message above and the "
3402       "stack trace and describe what you were doing.")
3403
3404 #
3405 # Internal global constants
3406 #
3407
3408 # Tokens
3409 (T_AND, T_OR, T_NOT,
3410  T_OPEN_PAREN, T_CLOSE_PAREN,
3411  T_EQUAL, T_UNEQUAL,
3412  T_MAINMENU, T_MENU, T_ENDMENU,
3413  T_SOURCE, T_CHOICE, T_ENDCHOICE,
3414  T_COMMENT, T_CONFIG, T_MENUCONFIG,
3415  T_HELP, T_IF, T_ENDIF, T_DEPENDS, T_ON,
3416  T_OPTIONAL, T_PROMPT, T_DEFAULT,
3417  T_BOOL, T_TRISTATE, T_HEX, T_INT, T_STRING,
3418  T_DEF_BOOL, T_DEF_TRISTATE,
3419  T_SELECT, T_IMPLY, T_RANGE, T_OPTION, T_ALLNOCONFIG_Y, T_ENV,
3420  T_DEFCONFIG_LIST, T_MODULES, T_VISIBLE) = range(40)
3421
3422 # The leading underscore before the function assignments below prevent pydoc
3423 # from listing them. The constants could be hidden too, but they're fairly
3424 # obviously internal anyway, so don't bother spamming the code.
3425
3426 # Keyword to token map. Note that the get() method is assigned directly as a
3427 # small optimization.
3428 _get_keyword = \
3429   {"mainmenu": T_MAINMENU, "menu": T_MENU, "endmenu": T_ENDMENU,
3430    "endif": T_ENDIF, "endchoice": T_ENDCHOICE, "source": T_SOURCE,
3431    "choice": T_CHOICE, "config": T_CONFIG, "comment": T_COMMENT,
3432    "menuconfig": T_MENUCONFIG, "help": T_HELP, "if": T_IF,
3433    "depends": T_DEPENDS, "on": T_ON, "optional": T_OPTIONAL,
3434    "prompt": T_PROMPT, "default": T_DEFAULT, "bool": T_BOOL, "boolean": T_BOOL,
3435    "tristate": T_TRISTATE, "int": T_INT, "hex": T_HEX, "def_bool": T_DEF_BOOL,
3436    "def_tristate": T_DEF_TRISTATE, "string": T_STRING, "select": T_SELECT,
3437    "imply": T_IMPLY, "range": T_RANGE, "option": T_OPTION,
3438    "allnoconfig_y": T_ALLNOCONFIG_Y, "env": T_ENV,
3439    "defconfig_list": T_DEFCONFIG_LIST, "modules": T_MODULES,
3440    "visible": T_VISIBLE}.get
3441
3442 # Strings to use for True and False
3443 BOOL_STR = {False: "false", True: "true"}
3444
3445 # Tokens after which identifier-like lexemes are treated as strings. T_CHOICE
3446 # is included to avoid symbols being registered for named choices.
3447 STRING_LEX = frozenset((T_BOOL, T_TRISTATE, T_INT, T_HEX, T_STRING, T_CHOICE,
3448                         T_PROMPT, T_MENU, T_COMMENT, T_SOURCE, T_MAINMENU))
3449
3450 # Matches the initial token on a line; see _tokenize(). Also eats trailing
3451 # whitespace as an optimization.
3452 _initial_token_re_match = re.compile(r"[^\w]*(\w+)\s*").match
3453
3454 # Matches an identifier/keyword optionally preceded by whitespace. Also eats
3455 # trailing whitespace as an optimization.
3456 _id_keyword_re_match = re.compile(r"\s*([\w./-]+)\s*").match
3457
3458 # Regular expressions for parsing .config files
3459 _set_re_match = re.compile(r"CONFIG_(\w+)=(.*)").match
3460 _unset_re_match = re.compile(r"# CONFIG_(\w+) is not set").match
3461
3462 # Regular expression for finding $-references to symbols in strings
3463 _sym_ref_re_search = re.compile(r"\$[A-Za-z0-9_]+").search
3464
3465 # Integers representing symbol types
3466 UNKNOWN, BOOL, TRISTATE, STRING, HEX, INT = range(6)
3467
3468 # Strings to use for types
3469 TYPENAME = {UNKNOWN: "unknown", BOOL: "bool", TRISTATE: "tristate",
3470             STRING: "string", HEX: "hex", INT: "int"}
3471
3472 # Token to type mapping
3473 TOKEN_TO_TYPE = {T_BOOL: BOOL, T_TRISTATE: TRISTATE, T_STRING: STRING,
3474                  T_INT: INT, T_HEX: HEX}
3475
3476 # Default values for symbols of different types (the value the symbol gets if
3477 # it is not assigned a user value and none of its 'default' clauses kick in)
3478 DEFAULT_VALUE = {BOOL: "n", TRISTATE: "n", STRING: "", INT: "", HEX: ""}
3479
3480 # Indicates that no item is selected in a choice statement
3481 NO_SELECTION = 0
3482
3483 # Integers representing expression types
3484 AND, OR, NOT, EQUAL, UNEQUAL = range(5)
3485
3486 # Map from tristate values to integers
3487 TRI_TO_INT = {"n": 0, "m": 1, "y": 2}
3488
3489 # Printing-related stuff
3490
3491 OP_TO_STR = {AND: " && ", OR: " || ", EQUAL: " = ", UNEQUAL: " != "}
3492 PRECEDENCE = {OR: 0, AND: 1, NOT: 2}