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