tools/buildman/kconfiglib.py

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