#!/usr/bin/env python3

"""
Overview
========

A curses-based menuconfig implementation. The interface should feel familiar to
people used to mconf ('make menuconfig').

Supports the same keys as mconf, and also supports a set of keybindings
inspired by Vi:

  J/K     : Down/Up
  L       : Enter menu/Toggle item
  H       : Leave menu
  Ctrl-D/U: Page Down/Page Down
  G/End   : Jump to end of list
  g/Home  : Jump to beginning of list

The mconf feature where pressing a key jumps to a menu entry with that
character in it in the current menu isn't supported. A jump-to feature for
jumping directly to any symbol (including invisible symbols) is available
instead.

Space and Enter are "smart" and try to do what you'd expect for the given
menu entry.


Running
=======

menuconfig.py can be run either as a standalone executable or by calling the
menu.menuconfig() function with an existing Kconfig instance. The second option
is a bit inflexible in that it will still load and save .config, etc.

When run in standalone mode, the top-level Kconfig file to load can be passed
as a command-line argument. With no argument, it defaults to "Kconfig".

The KCONFIG_CONFIG environment variable specifies the .config file to load (if
it exists) and save. If KCONFIG_CONFIG is unset, ".config" is used.

$srctree is supported through Kconfiglib.


Other features
==============

  - Seamless terminal resizing

  - No dependencies on *nix, as the 'curses' module is in the Python standard
    library

  - Unicode text entry

  - Improved information screen compared to mconf:

      * Expressions are split up by their top-level &&/|| operands to improve
        readability

      * Undefined symbols in expressions are pointed out

      * Menus and comments have information displays

      * Kconfig definitions are printed


Limitations
===========

  - Python 3 only

    This is mostly due to Python 2 not having curses.get_wch(), which is needed
    for Unicode support.

  - Doesn't work out of the box on Windows

    Has been tested to work with the wheels provided at
    https://www.lfd.uci.edu/~gohlke/pythonlibs/#curses though.
"""

import curses
import errno
import locale
import os
import platform
import re
import sys
import textwrap

# We need this double import for the _expr_str() override below
import kconfiglib

from kconfiglib import Kconfig, \
                       Symbol, Choice, MENU, COMMENT, MenuNode, \
                       BOOL, TRISTATE, STRING, INT, HEX, UNKNOWN, \
                       AND, OR, NOT, \
                       expr_value, split_expr, \
                       TRI_TO_STR, TYPE_TO_STR


#
# Configuration variables
#

# If True, try to convert LC_CTYPE to a UTF-8 locale if it is set to the C
# locale (which implies ASCII). This fixes curses Unicode I/O issues on systems
# with bad defaults. ncurses configures itself from the locale settings.
#
# Related PEP: https://www.python.org/dev/peps/pep-0538/
_CONVERT_C_LC_CTYPE_TO_UTF8 = True

# How many steps an implicit submenu will be indented. Implicit submenus are
# created when an item depends on the symbol before it. Note that symbols
# defined with 'menuconfig' create a separate menu instead of indenting.
_SUBMENU_INDENT = 4

# Number of steps for Page Up/Down to jump
_PG_JUMP = 6

# How far the cursor needs to be from the edge of the window before it starts
# to scroll
_SCROLL_OFFSET = 5

# Minimum width of dialogs that ask for text input
_INPUT_DIALOG_MIN_WIDTH = 30

# Number of arrows pointing up/down to draw when a window is scrolled
_N_SCROLL_ARROWS = 14

# Lines of help text shown at the bottom of the "main" display
_MAIN_HELP_LINES = """
[Space/Enter] Toggle/enter   [ESC] Leave menu    [S] Save        [O] Load
[?] Symbol info              [/] Jump to symbol  [A] Toggle show-all mode
[Q] Quit (prompts for save)  [D] Save minimal config (advanced)
"""[1:-1].split("\n")

# Lines of help text shown at the bottom of the information dialog
_INFO_HELP_LINES = """
[ESC/q] Return to menu
"""[1:-1].split("\n")

# Lines of help text shown at the bottom of the search dialog
_JUMP_TO_HELP_LINES = """
Type text to narrow the search. Regexes are supported (via Python's 're'
module). The up/down cursor keys step in the list. [Enter] jumps to the
selected symbol. [ESC] aborts the search. Type multiple space-separated
strings/regexes to find entries that match all of them.
"""[1:-1].split("\n")

def _init_styles():
    global _SEPARATOR_STYLE
    global _HELP_STYLE
    global _LIST_STYLE
    global _LIST_SEL_STYLE
    global _LIST_INVISIBLE_STYLE
    global _LIST_INVISIBLE_SEL_STYLE
    global _INPUT_FIELD_STYLE

    global _PATH_STYLE

    global _DIALOG_FRAME_STYLE
    global _DIALOG_BODY_STYLE

    global _INFO_TEXT_STYLE

    # Initialize styles for different parts of the application. The arguments
    # are ordered as follows:
    #
    #   1. Text color
    #   2. Background color
    #   3. Attributes
    #   4. Extra attributes if colors aren't available. The colors will be
    #      ignored in this case, and the attributes from (3.) and (4.) will be
    #      ORed together.

    # A_BOLD tends to produce faint and hard-to-read text on the Windows
    # console, especially with the old color scheme, before the introduction of
    # https://blogs.msdn.microsoft.com/commandline/2017/08/02/updating-the-windows-console-colors/
    BOLD = curses.A_NORMAL if _IS_WINDOWS else curses.A_BOLD


    # Separator lines between windows. Also used for the top line in the symbol
    # information dialog.
    _SEPARATOR_STYLE          = _style(curses.COLOR_BLACK, curses.COLOR_YELLOW, BOLD,            curses.A_STANDOUT)

    # Edit boxes
    _INPUT_FIELD_STYLE        = _style(curses.COLOR_WHITE, curses.COLOR_BLUE,   curses.A_NORMAL, curses.A_STANDOUT)

    # List of items, e.g. the main display
    _LIST_STYLE               = _style(curses.COLOR_BLACK, curses.COLOR_WHITE,  curses.A_NORMAL                   )
    # Style for the selected item
    _LIST_SEL_STYLE           = _style(curses.COLOR_WHITE, curses.COLOR_BLUE,   curses.A_NORMAL, curses.A_STANDOUT)

    # Like _LIST_(SEL_)STYLE, for invisible items. Used in show-all mode.
    _LIST_INVISIBLE_STYLE     = _style(curses.COLOR_RED,   curses.COLOR_WHITE,  curses.A_NORMAL, BOLD             )
    _LIST_INVISIBLE_SEL_STYLE = _style(curses.COLOR_RED,   curses.COLOR_BLUE,   curses.A_NORMAL, curses.A_STANDOUT)

    # Help text windows at the bottom of various fullscreen dialogs
    _HELP_STYLE               = _style(curses.COLOR_BLACK, curses.COLOR_WHITE,  BOLD                              )

    # Top row in the main display, with the menu path
    _PATH_STYLE               = _style(curses.COLOR_BLACK, curses.COLOR_WHITE,  BOLD                              )

    # Symbol information text
    _INFO_TEXT_STYLE          = _LIST_STYLE

    # Frame around dialog boxes
    _DIALOG_FRAME_STYLE       = _style(curses.COLOR_BLACK, curses.COLOR_YELLOW, BOLD,            curses.A_STANDOUT)
    # Body of dialog boxes
    _DIALOG_BODY_STYLE        = _style(curses.COLOR_WHITE, curses.COLOR_BLACK,  curses.A_NORMAL                   )


#
# Main application
#

# color_attribs holds the color pairs we've already created, indexed by a
# (<foreground color>, <background color>) tuple.
#
# Obscure Python: We never pass a value for color_attribs, and it keeps
# pointing to the same dict. This avoids a global.
def _style(fg_color, bg_color, attribs, no_color_extra_attribs=0,
           color_attribs={}):
    # Returns an attribute with the specified foreground and background color
    # and the attributes in 'attribs'. Reuses color pairs already created if
    # possible, and creates a new color pair otherwise.
    #
    # Returns 'attribs | no_color_extra_attribs' if colors aren't supported.

    if not curses.has_colors():
        return attribs | no_color_extra_attribs

    if (fg_color, bg_color) not in color_attribs:
        # Create new color pair. Color pair number 0 is hardcoded and cannot be
        # changed, hence the +1s.
        curses.init_pair(len(color_attribs) + 1, fg_color, bg_color)
        color_attribs[(fg_color, bg_color)] = \
            curses.color_pair(len(color_attribs) + 1)

    return color_attribs[(fg_color, bg_color)] | attribs

# "Extend" the standard kconfiglib.expr_str() to show values for symbols
# appearing in expressions, for the information dialog.
#
# This is a bit hacky, but officially supported. It beats having to reimplement
# expression printing just to tweak it a bit.

def _expr_str_val(expr):
    if isinstance(expr, Symbol) and not expr.is_constant and \
       not _is_num(expr.name):
        # Show the values of non-constant (non-quoted) symbols that don't look
        # like numbers. Things like 123 are actually a symbol references, and
        # only work as expected due to undefined symbols getting their name as
        # their value. Showing the symbol value there isn't helpful though.

        if not expr.nodes:
            # Undefined symbol reference
            return "{}(undefined/n)".format(expr.name)

        return '{}(="{}")'.format(expr.name, expr.str_value)

    if isinstance(expr, tuple) and expr[0] == NOT and \
       isinstance(expr[1], Symbol):

        # Put a space after "!" before a symbol, since '! FOO(="y")' makes it
        # clearer than '!FOO(="y")' that "y" is the value of FOO itself
        return "! " + _expr_str(expr[1])

    # We'll end up back in _expr_str_val() when _expr_str_orig() does recursive
    # calls for subexpressions
    return _expr_str_orig(expr)

# Do hacky expr_str() extension. The rest of the code will just call
# _expr_str().
_expr_str_orig = kconfiglib.expr_str
kconfiglib.expr_str = _expr_str_val
_expr_str = _expr_str_val

def menuconfig(kconf):
    """
    Launches the configuration interface, returning after the user exits.

    kconf:
      Kconfig instance to be configured
    """

    globals()["_kconf"] = kconf
    global _config_filename
    global _show_all


    _config_filename = os.environ.get("KCONFIG_CONFIG")
    if _config_filename is None:
        _config_filename = ".config"


    if os.path.exists(_config_filename):
        print("Using existing configuration '{}' as base"
              .format(_config_filename))
        _kconf.load_config(_config_filename)

    elif kconf.defconfig_filename is not None:
        print("Using default configuration found in '{}' as base"
              .format(kconf.defconfig_filename))
        _kconf.load_config(kconf.defconfig_filename)

    else:
        print("Using default symbol values as base")


    # Any visible items in the top menu?
    _show_all = False
    if not _shown_nodes(_kconf.top_node):
        # Nothing visible. Start in show-all mode and try again.
        _show_all = True
        if not _shown_nodes(_kconf.top_node):
            # Give up. The implementation relies on always having a selected
            # node.
            print("Empty configuration -- nothing to configure.\n"
                  "Check that environment variables are set properly.")
            return

    # Disable warnings. They get mangled in curses mode, and we deal with
    # errors ourselves.
    _kconf.disable_warnings()

    # Make curses use the locale settings specified in the environment
    locale.setlocale(locale.LC_ALL, "")

    # Try to fix Unicode issues on systems with bad defaults
    if _CONVERT_C_LC_CTYPE_TO_UTF8:
        _convert_c_lc_ctype_to_utf8()

    # Get rid of the delay between pressing ESC and jumping to the parent menu
    os.environ.setdefault("ESCDELAY", "0")

    # Enter curses mode. _menuconfig() returns a string to print on exit, after
    # curses has been de-initialized.
    print(curses.wrapper(_menuconfig))

# Global variables used below:
#
#   _cur_menu:
#     Menu node of the menu (or menuconfig symbol, or choice) currently being
#     shown
#
#   _shown:
#     List of items in _cur_menu that are shown (ignoring scrolling). In
#     show-all mode, this list contains all items in _cur_menu. Otherwise, it
#     contains just the visible items.
#
#   _sel_node_i:
#     Index in _shown of the currently selected node
#
#   _menu_scroll:
#     Index in _shown of the top row of the main display
#
#   _parent_screen_rows:
#     List/stack of the row numbers that the selections in the parent menus
#     appeared on. This is used to prevent the scrolling from jumping around
#     when going in and out of menus.
#
#   _show_all:
#     If True, "show-all" mode is on. Show-all mode shows all symbols and other
#     items in the current menu, including those that lack a prompt or aren't
#     currently visible.
#
#     Invisible items are drawn in a different style to make them stand out.
#
#   _conf_changed:
#     True if the configuration has been changed. If False, we don't bother
#     showing the save-and-quit dialog.
#
#     We reset this to False whenever the configuration is saved explicitly
#     from the save dialog.

def _menuconfig(stdscr):
    # Logic for the main display, with the list of symbols, etc.

    globals()["stdscr"] = stdscr
    global _conf_changed

    _init()

    while True:
        _draw_main()
        curses.doupdate()


        c = _get_wch_compat(_menu_win)

        if c == curses.KEY_RESIZE:
            _resize_main()

        if c in (curses.KEY_DOWN, "j", "J"):
            _select_next_menu_entry()

        elif c in (curses.KEY_UP, "k", "K"):
            _select_prev_menu_entry()

        elif c in (curses.KEY_NPAGE, "\x04"):  # Page Down/Ctrl-D
            # Keep it simple. This way we get sane behavior for small windows,
            # etc., for free.
            for _ in range(_PG_JUMP):
                _select_next_menu_entry()

        elif c in (curses.KEY_PPAGE, "\x15"):  # Page Up/Ctrl-U
            for _ in range(_PG_JUMP):
                _select_prev_menu_entry()

        elif c in (curses.KEY_END, "G"):
            _select_last_menu_entry()

        elif c in (curses.KEY_HOME, "g"):
            _select_first_menu_entry()

        elif c in (curses.KEY_RIGHT, " ", "\n", "l", "L"):
            # Do appropriate node action. Only Space is treated specially,
            # preferring to toggle nodes rather than enter menus.

            sel_node = _shown[_sel_node_i]

            if sel_node.is_menuconfig and not \
               (c == " " and _prefer_toggle(sel_node.item)):

                _enter_menu(sel_node)

            else:
                _change_node(sel_node)
                if _is_y_mode_choice_sym(sel_node.item):
                    # Immediately jump to the parent menu after making a choice
                    # selection, like 'make menuconfig' does
                    _leave_menu()

        elif c in ("n", "N"):
            _set_node_tri_val(_shown[_sel_node_i], 0)

        elif c in ("m", "M"):
            _set_node_tri_val(_shown[_sel_node_i], 1)

        elif c in ("y", "Y"):
            _set_node_tri_val(_shown[_sel_node_i], 2)

        elif c in (curses.KEY_LEFT, curses.KEY_BACKSPACE, _ERASE_CHAR,
                   "\x1B",  # \x1B = ESC
                   "h", "H"):

            if c == "\x1B" and _cur_menu is _kconf.top_node:
                res = quit_dialog()
                if res:
                    return res
            else:
                _leave_menu()

        elif c in ("o", "O"):
            if _conf_changed:
                c = _key_dialog(
                    "Load",
                    "You have unsaved changes. Load new\n"
                    "configuration anyway?\n"
                    "\n"
                    "        (Y)es  (C)ancel",
                    "yc")

                if c is None or c == "c":
                    continue

            if _load_dialog():
                _conf_changed = False

        elif c in ("s", "S"):
            if _save_dialog(_kconf.write_config, _config_filename,
                            "configuration"):

                _conf_changed = False

        elif c in ("d", "D"):
            _save_dialog(_kconf.write_min_config, "defconfig",
                         "minimal configuration")

        elif c == "/":
            _jump_to_dialog()
            # The terminal might have been resized while the fullscreen jump-to
            # dialog was open
            _resize_main()

        elif c == "?":
            _info_dialog(_shown[_sel_node_i])
            # The terminal might have been resized while the fullscreen info
            # dialog was open
            _resize_main()

        elif c in ("a", "A"):
            _toggle_show_all()

        elif c in ("q", "Q"):
            res = quit_dialog()
            if res:
                return res

def quit_dialog():
   if not _conf_changed:
       return "No changes to save"

   while True:
       c = _key_dialog(
           "Quit",
           " Save configuration?\n"
           "\n"
           "(Y)es  (N)o  (C)ancel",
           "ync")

       if c is None or c == "c":
           return None

       if c == "y":
           if _try_save(_kconf.write_config, _config_filename,
                        "configuration"):

               return "Configuration saved to '{}'" \
                      .format(_config_filename)

       elif c == "n":
           return "Configuration was not saved"

def _init():
    # Initializes the main display with the list of symbols, etc. Also does
    # misc. global initialization that needs to happen after initializing
    # curses.

    global _ERASE_CHAR

    global _path_win
    global _top_sep_win
    global _menu_win
    global _bot_sep_win
    global _help_win

    global _parent_screen_rows
    global _cur_menu
    global _shown
    global _sel_node_i
    global _menu_scroll

    global _conf_changed

    # Looking for this in addition to KEY_BACKSPACE (which is unreliable) makes
    # backspace work with TERM=vt100. That makes it likely to work in sane
    # environments.
    #
    # erasechar() returns a 'bytes' object. Since we use get_wch(), we need to
    # decode it. Just give up and avoid crashing if it can't be decoded.
    _ERASE_CHAR = curses.erasechar().decode("utf-8", "ignore")

    _init_styles()

    # Hide the cursor
    _safe_curs_set(0)

    # Initialize windows

    # Top row, with menu path
    _path_win = _styled_win(_PATH_STYLE)

    # Separator below menu path, with title and arrows pointing up
    _top_sep_win = _styled_win(_SEPARATOR_STYLE)

    # List of menu entries with symbols, etc.
    _menu_win = _styled_win(_LIST_STYLE)
    _menu_win.keypad(True)

    # Row below menu list, with arrows pointing down
    _bot_sep_win = _styled_win(_SEPARATOR_STYLE)

    # Help window with keys at the bottom
    _help_win = _styled_win(_HELP_STYLE)

    # The rows we'd like the nodes in the parent menus to appear on. This
    # prevents the scroll from jumping around when going in and out of menus.
    _parent_screen_rows = []

    # Initial state
    _cur_menu = _kconf.top_node
    _shown = _shown_nodes(_cur_menu)
    _sel_node_i = 0
    _menu_scroll = 0

    # Give windows their initial size
    _resize_main()

    # No changes yet
    _conf_changed = False

def _resize_main():
    # Resizes the main display, with the list of symbols, etc., to fill the
    # terminal

    global _menu_scroll

    screen_height, screen_width = stdscr.getmaxyx()

    _path_win.resize(1, screen_width)
    _top_sep_win.resize(1, screen_width)
    _bot_sep_win.resize(1, screen_width)

    help_win_height = len(_MAIN_HELP_LINES)
    menu_win_height = screen_height - help_win_height - 3

    if menu_win_height >= 1:
        _menu_win.resize(menu_win_height, screen_width)
        _help_win.resize(help_win_height, screen_width)

        _top_sep_win.mvwin(1, 0)
        _menu_win.mvwin(2, 0)
        _bot_sep_win.mvwin(2 + menu_win_height, 0)
        _help_win.mvwin(2 + menu_win_height + 1, 0)
    else:
        # Degenerate case. Give up on nice rendering and just prevent errors.

        menu_win_height = 1

        _menu_win.resize(1, screen_width)
        _help_win.resize(1, screen_width)

        for win in _top_sep_win, _menu_win, _bot_sep_win, _help_win:
            win.mvwin(0, 0)

    # Adjust the scroll so that the selected node is still within the window,
    # if needed
    if _sel_node_i - _menu_scroll >= menu_win_height:
        _menu_scroll = _sel_node_i - menu_win_height + 1

def _menu_win_height():
    # Returns the height of the menu display

    return _menu_win.getmaxyx()[0]

def _prefer_toggle(item):
    # For nodes with menus, determines whether Space should change the value of
    # the node's item or enter its menu. We toggle symbols (which have menus
    # when they're defined with 'menuconfig') and choices that can be in more
    # than one mode (e.g. optional choices). In other cases, we enter the menu.

    return isinstance(item, Symbol) or \
           (isinstance(item, Choice) and len(item.assignable) > 1)

def _enter_menu(menu):
    # Makes 'menu' the currently displayed menu

    global _cur_menu
    global _shown
    global _sel_node_i
    global _menu_scroll

    shown_sub = _shown_nodes(menu)
    # Never enter empty menus. We depend on having a current node.
    if shown_sub:
        # Remember where the current node appears on the screen, so we can try
        # to get it to appear in the same place when we leave the menu
        _parent_screen_rows.append(_sel_node_i - _menu_scroll)

        # Jump into menu
        _cur_menu = menu
        _shown = shown_sub
        _sel_node_i = 0
        _menu_scroll = 0

def _jump_to(node):
    # Jumps directly to the menu node 'node'

    global _cur_menu
    global _shown
    global _sel_node_i
    global _menu_scroll
    global _show_all
    global _parent_screen_rows

    # Clear remembered menu locations. We might not even have been in the
    # parent menus before.
    _parent_screen_rows = []

    # Turn on show-all mode if the node isn't visible
    if not (node.prompt and expr_value(node.prompt[1])):
        _show_all = True

    _cur_menu = _parent_menu(node)
    _shown = _shown_nodes(_cur_menu)
    _sel_node_i = _shown.index(node)

    # Center the jumped-to node vertically, if possible
    _menu_scroll = max(_sel_node_i - _menu_win_height()//2, 0)

def _leave_menu():
    # Jumps to the parent menu of the current menu. Does nothing if we're in
    # the top menu.

    global _cur_menu
    global _shown
    global _sel_node_i
    global _menu_scroll

    if _cur_menu is _kconf.top_node:
        return

    # Jump to parent menu
    parent = _parent_menu(_cur_menu)
    _shown = _shown_nodes(parent)
    _sel_node_i = _shown.index(_cur_menu)
    _cur_menu = parent

    # Try to make the menu entry appear on the same row on the screen as it did
    # before we entered the menu.

    if _parent_screen_rows:
        # The terminal might have shrunk since we were last in the parent menu
        screen_row = min(_parent_screen_rows.pop(), _menu_win_height() - 1)
        _menu_scroll = max(_sel_node_i - screen_row, 0)
    else:
        # No saved parent menu locations, meaning we jumped directly to some
        # node earlier. Just center the node vertically if possible.
        _menu_scroll = max(_sel_node_i - _menu_win_height()//2, 0)

def _select_next_menu_entry():
    # Selects the menu entry after the current one, adjusting the scroll if
    # necessary. Does nothing if we're already at the last menu entry.

    global _sel_node_i
    global _menu_scroll

    if _sel_node_i < len(_shown) - 1:
        # Jump to the next node
        _sel_node_i += 1

        # If the new node is sufficiently close to the edge of the menu window
        # (as determined by _SCROLL_OFFSET), increase the scroll by one. This
        # gives nice and non-jumpy behavior even when
        # _SCROLL_OFFSET >= _menu_win_height().
        if _sel_node_i >= _menu_scroll + _menu_win_height() - _SCROLL_OFFSET:
            _menu_scroll = min(_menu_scroll + 1,
                               _max_scroll(_shown, _menu_win))

def _select_prev_menu_entry():
    # Selects the menu entry before the current one, adjusting the scroll if
    # necessary. Does nothing if we're already at the first menu entry.

    global _sel_node_i
    global _menu_scroll

    if _sel_node_i > 0:
        # Jump to the previous node
        _sel_node_i -= 1

        # See _select_next_menu_entry()
        if _sel_node_i <= _menu_scroll + _SCROLL_OFFSET:
            _menu_scroll = max(_menu_scroll - 1, 0)

def _select_last_menu_entry():
    # Selects the last menu entry in the current menu

    global _sel_node_i
    global _menu_scroll

    _sel_node_i = len(_shown) - 1
    _menu_scroll = _max_scroll(_shown, _menu_win)

def _select_first_menu_entry():
    # Selects the first menu entry in the current menu

    global _sel_node_i
    global _menu_scroll

    _sel_node_i = _menu_scroll = 0

def _toggle_show_all():
    # Toggles show-all mode on/off

    global _show_all
    global _shown
    global _sel_node_i
    global _menu_scroll

    # Row on the screen the cursor is on. Preferably we want the same row to
    # stay highlighted.
    old_row = _sel_node_i - _menu_scroll

    _show_all = not _show_all
    # List of new nodes to be shown after toggling _show_all
    new_shown = _shown_nodes(_cur_menu)

    # Find a good node to select. The selected node might disappear if show-all
    # mode is turned off.

    # If there are visible nodes before the previously selected node, select
    # the closest one. This will select the previously selected node itself if
    # it is still visible.
    for node in reversed(_shown[:_sel_node_i + 1]):
        if node in new_shown:
            _sel_node_i = new_shown.index(node)
            break
    else:
        # No visible nodes before the previously selected node. Select the
        # closest visible node after it instead.
        for node in _shown[_sel_node_i + 1:]:
            if node in new_shown:
                _sel_node_i = new_shown.index(node)
                break
        else:
            # No visible nodes at all, meaning show-all was turned off inside
            # an invisible menu. Don't allow that, as the implementation relies
            # on always having a selected node.
            _show_all = True

            return

    _shown = new_shown

    # Try to make the cursor stay on the same row in the menu window. This
    # might be impossible if too many nodes have disappeared above the node.
    _menu_scroll = max(_sel_node_i - old_row, 0)

def _draw_main():
    # Draws the "main" display, with the list of symbols, the header, and the
    # footer.
    #
    # This could be optimized to only update the windows that have actually
    # changed, but keep it simple for now and let curses sort it out.

    term_width = stdscr.getmaxyx()[1]


    #
    # Update the top row with the menu path
    #

    _path_win.erase()

    # Draw the menu path ("(top menu) -> menu -> submenu -> ...")

    menu_prompts = []

    menu = _cur_menu
    while menu is not _kconf.top_node:
        menu_prompts.append(menu.prompt[0])
        menu = _parent_menu(menu)
    menu_prompts.append("(top menu)")
    menu_prompts.reverse()

    # Hack: We can't put ACS_RARROW directly in the string. Temporarily
    # represent it with NULL. Maybe using a Unicode character would be better.
    menu_path_str = " \0 ".join(menu_prompts)

    # Scroll the menu path to the right if needed to make the current menu's
    # title visible
    if len(menu_path_str) > term_width:
        menu_path_str = menu_path_str[len(menu_path_str) - term_width:]

    # Print the path with the arrows reinserted
    split_path = menu_path_str.split("\0")
    _safe_addstr(_path_win, split_path[0])
    for s in split_path[1:]:
        _safe_addch(_path_win, curses.ACS_RARROW)
        _safe_addstr(_path_win, s)

    _path_win.noutrefresh()


    #
    # Update the separator row below the menu path
    #

    _top_sep_win.erase()

    # Draw arrows pointing up if the symbol window is scrolled down. Draw them
    # before drawing the title, so the title ends up on top for small windows.
    if _menu_scroll > 0:
        _safe_hline(_top_sep_win, 0, 4, curses.ACS_UARROW, _N_SCROLL_ARROWS)

    # Add the 'mainmenu' text as the title, centered at the top
    _safe_addstr(_top_sep_win,
                 0, (term_width - len(_kconf.mainmenu_text))//2,
                 _kconf.mainmenu_text)

    _top_sep_win.noutrefresh()


    #
    # Update the symbol window
    #

    _menu_win.erase()

    # Draw the _shown nodes starting from index _menu_scroll up to either as
    # many as fit in the window, or to the end of _shown
    for i in range(_menu_scroll,
                   min(_menu_scroll + _menu_win_height(), len(_shown))):

        node = _shown[i]

        if node.prompt and expr_value(node.prompt[1]):
            style = _LIST_SEL_STYLE if i == _sel_node_i else _LIST_STYLE
        else:
            style = _LIST_INVISIBLE_SEL_STYLE if i == _sel_node_i else \
                    _LIST_INVISIBLE_STYLE

        _safe_addstr(_menu_win, i - _menu_scroll, 0, _node_str(node), style)

    _menu_win.noutrefresh()


    #
    # Update the bottom separator window
    #

    _bot_sep_win.erase()

    # Draw arrows pointing down if the symbol window is scrolled up
    if _menu_scroll < _max_scroll(_shown, _menu_win):
        _safe_hline(_bot_sep_win, 0, 4, curses.ACS_DARROW, _N_SCROLL_ARROWS)

    # Indicate when show-all mode is enabled
    if _show_all:
        s = "Show-all mode enabled"
        _safe_addstr(_bot_sep_win, 0, term_width - len(s) - 2, s)

    _bot_sep_win.noutrefresh()


    #
    # Update the help window
    #

    _help_win.erase()

    for i, line in enumerate(_MAIN_HELP_LINES):
        _safe_addstr(_help_win, i, 0, line)

    _help_win.noutrefresh()

def _parent_menu(node):
    # Returns the menu node of the menu that contains 'node'. In addition to
    # proper 'menu's, this might also be a 'menuconfig' symbol or a 'choice'.
    # "Menu" here means a menu in the interface.

    menu = node.parent
    while not menu.is_menuconfig:
        menu = menu.parent
    return menu

def _shown_nodes(menu):
    # Returns a list of the nodes in 'menu' (see _parent_menu()) that should be
    # shown in the menu window

    res = []

    def rec(node):
        nonlocal res

        while node:
            # Show the node if its prompt is visible. For menus, also check
            # 'visible if'. In show-all mode, show everything.
            if _show_all or \
               (node.prompt and expr_value(node.prompt[1]) and not \
                (node.item == MENU and not expr_value(node.visibility))):

                res.append(node)

                # If a node has children but doesn't have the is_menuconfig
                # flag set, the children come from a submenu created implicitly
                # from dependencies. Show those in this menu too.
                if node.list and not node.is_menuconfig:
                    rec(node.list)

            node = node.next

    rec(menu.list)
    return res

def _change_node(node):
    # Changes the value of the menu node 'node' if it is a symbol. Bools and
    # tristates are toggled, while other symbol types pop up a text entry
    # dialog.

    if not isinstance(node.item, (Symbol, Choice)):
        return

    # This will hit for invisible symbols in show-all mode
    if not (node.prompt and expr_value(node.prompt[1])):
        return

    # sc = symbol/choice
    sc = node.item

    if sc.type in (INT, HEX, STRING):
        s = sc.str_value

        while True:
            s = _input_dialog("Value for '{}' ({})".format(
                                  node.prompt[0], TYPE_TO_STR[sc.type]),
                              s, _range_info(sc))

            if s is None:
                break

            if sc.type in (INT, HEX):
                s = s.strip()

                # 'make menuconfig' does this too. Hex values not starting with
                # '0x' are accepted when loading .config files though.
                if sc.type == HEX and not s.startswith(("0x", "0X")):
                    s = "0x" + s

            if _check_validity(sc, s):
                _set_val(sc, s)
                break

    elif len(sc.assignable) == 1:
        # Handles choice symbols for choices in y mode, which are a special
        # case: .assignable can be (2,) while .tri_value is 0.
        _set_val(sc, sc.assignable[0])

    else:
        # Set the symbol to the value after the current value in
        # sc.assignable, with wrapping
        val_index = sc.assignable.index(sc.tri_value)
        _set_val(sc, sc.assignable[(val_index + 1) % len(sc.assignable)])

    _update_menu()

def _set_node_tri_val(node, tri_val):
    # Sets 'node' to 'tri_val', if that value can be assigned

    if isinstance(node.item, (Symbol, Choice)) and \
       tri_val in node.item.assignable:

        _set_val(node.item, tri_val)

def _set_val(sc, val):
    # Wrapper around Symbol/Choice.set_value() for updating the menu state and
    # _conf_changed

    global _conf_changed

    # Use the string representation of tristate values. This makes the format
    # consistent for all symbol types.
    if val in TRI_TO_STR:
        val = TRI_TO_STR[val]

    if val != sc.str_value:
        sc.set_value(val)
        _conf_changed = True

        # Changing the value of the symbol might have changed what items in the
        # current menu are visible. Recalculate the state.
        _update_menu()

def _update_menu():
    # Updates the current menu after the value of a symbol or choice has been
    # changed. Changing a value might change which items in the menu are
    # visible.
    #
    # Tries to preserve the location of the cursor when items disappear above
    # it.

    global _shown
    global _sel_node_i
    global _menu_scroll

    # Row on the screen the cursor was on
    old_row = _sel_node_i - _menu_scroll

    sel_node = _shown[_sel_node_i]

    # New visible nodes
    _shown = _shown_nodes(_cur_menu)

    # New index of selected node
    _sel_node_i = _shown.index(sel_node)

    # Try to make the cursor stay on the same row in the menu window. This
    # might be impossible if too many nodes have disappeared above the node.
    _menu_scroll = max(_sel_node_i - old_row, 0)

def _input_dialog(title, initial_text, info_text=None):
    # Pops up a dialog that prompts the user for a string
    #
    # title:
    #   Title to display at the top of the dialog window's border
    #
    # initial_text:
    #   Initial text to prefill the input field with
    #
    # info_text:
    #   String to show next to the input field. If None, just the input field
    #   is shown.

    win = _styled_win(_DIALOG_BODY_STYLE)
    win.keypad(True)

    # Give the input dialog its initial size
    _resize_input_dialog(win, title, info_text)

    _safe_curs_set(2)

    # Input field text
    s = initial_text

    # Cursor position
    i = len(initial_text)

    def edit_width():
        return win.getmaxyx()[1] - 4

    # Horizontal scroll offset
    hscroll = max(i - edit_width() + 1, 0)

    while True:
        # Draw the "main" display with the menu, etc., so that resizing still
        # works properly. This is like a stack of windows, only hardcoded for
        # now.
        _draw_main()
        _draw_input_dialog(win, title, info_text, s, i, hscroll)
        curses.doupdate()


        c = _get_wch_compat(win)

        if c == "\n":
            _safe_curs_set(0)
            return s

        if c == "\x1B":  # \x1B = ESC
            _safe_curs_set(0)
            return None


        if c == curses.KEY_RESIZE:
            # Resize the main display too. The dialog floats above it.
            _resize_main()
            _resize_input_dialog(win, title, info_text)

        else:
            s, i, hscroll = _edit_text(c, s, i, hscroll, edit_width())

def _resize_input_dialog(win, title, info_text):
    # Resizes the input dialog to a size appropriate for the terminal size

    screen_height, screen_width = stdscr.getmaxyx()

    win_height = min(5 if info_text is None else 7, screen_height)

    win_width = max(_INPUT_DIALOG_MIN_WIDTH, len(title) + 4)
    if info_text is not None:
        win_width = max(win_width, len(info_text) + 4)
    win_width = min(win_width, screen_width)

    win.resize(win_height, win_width)
    win.mvwin((screen_height - win_height)//2,
              (screen_width - win_width)//2)

def _draw_input_dialog(win, title, info_text, s, i, hscroll):
    edit_width = win.getmaxyx()[1] - 4

    win.erase()

    _draw_frame(win, title)

    # Note: Perhaps having a separate window for the input field would be nicer
    visible_s = s[hscroll:hscroll + edit_width]
    _safe_addstr(win, 2, 2, visible_s + " "*(edit_width - len(visible_s)),
                 _INPUT_FIELD_STYLE)

    if info_text is not None:
        _safe_addstr(win, 4, 2, info_text)

    _safe_move(win, 2, 2 + i - hscroll)

    win.noutrefresh()

def _load_dialog():
    # Dialog for loading a new configuration
    #
    # Return value:
    #   True if a new configuration was loaded, and False if the user canceled
    #   the dialog

    global _show_all

    filename = ""
    while True:
        filename = _input_dialog("File to load", filename)

        if filename is None:
            return False

        if _try_load(filename):
            sel_node = _shown[_sel_node_i]

            # Turn on show-all mode if the current node is (no longer) visible
            if not (sel_node.prompt and expr_value(sel_node.prompt[1])):
                _show_all = True

            _update_menu()

            # The message dialog indirectly updates the menu display, so _msg()
            # must be called after the new state has been initialized
            _msg("Success", "Loaded {}".format(filename))
            return True

def _try_load(filename):
    # Tries to load a configuration file. Pops up an error and returns False on
    # failure.
    #
    # filename:
    #   Configuration file to load

    # Hack: strerror and errno are lost after we raise the custom IOError with
    # troubleshooting help in Kconfig.load_config(). Adding them back to the
    # exception loses the custom message. As a workaround, try opening the file
    # separately first and report any errors.
    try:
        open(filename).close()
    except OSError as e:
        _error("Error loading {}\n\n{} (errno: {})"
               .format(filename, e.strerror, errno.errorcode[e.errno]))
        return False

    try:
        _kconf.load_config(filename)
        return True
    except OSError as e:
        _error("Error loading {}\n\nUnknown error".format(filename))
        return False

def _save_dialog(save_fn, default_filename, description):
    # Dialog for saving the current configuration
    #
    # save_fn:
    #   Function to call with 'filename' to save the file
    #
    # default_filename:
    #   Prefilled filename in the input field
    #
    # description:
    #   String describing the thing being saved
    #
    # Return value:
    #   True if the configuration was saved, and False if the user canceled the
    #   dialog

    filename = default_filename
    while True:
        filename = _input_dialog(
            "Filename to save {} to".format(description),
            filename)

        if filename is None:
            return False

        if _try_save(save_fn, filename, description):
            _msg("Success", "{} saved to {}".format(description, filename))
            return True

def _try_save(save_fn, filename, description):
    # Tries to save a configuration file. Pops up an error and returns False on
    # failure.
    #
    # save_fn:
    #   Function to call with 'filename' to save the file
    #
    # description:
    #   String describing the thing being saved

    try:
        save_fn(filename)
        return True
    except OSError as e:
        _error("Error saving {} to '{}'\n\n{} (errno: {})"
               .format(description, e.filename, e.strerror,
                       errno.errorcode[e.errno]))
        return False

def _key_dialog(title, text, keys):
    # Pops up a dialog that can be closed by pressing a key
    #
    # title:
    #   Title to display at the top of the dialog window's border
    #
    # text:
    #   Text to show in the dialog
    #
    # keys:
    #   List of keys that will close the dialog. Other keys (besides ESC) are
    #   ignored. The caller is responsible for providing a hint about which
    #   keys can be pressed in 'text'.
    #
    # Return value:
    #   The key that was pressed to close the dialog. Uppercase characters are
    #   converted to lowercase. ESC will always close the dialog, and returns
    #   None.

    win = _styled_win(_DIALOG_BODY_STYLE)
    win.keypad(True)

    _resize_key_dialog(win, text)

    while True:
        # See _input_dialog()
        _draw_main()
        _draw_key_dialog(win, title, text)
        curses.doupdate()


        c = _get_wch_compat(win)

        if c == "\x1B":  # \x1B = ESC
            return None


        if c == curses.KEY_RESIZE:
            # Resize the main display too. The dialog floats above it.
            _resize_main()
            _resize_key_dialog(win, text)

        elif isinstance(c, str):
            c = c.lower()
            if c in keys:
                return c

def _resize_key_dialog(win, text):
    # Resizes the key dialog to a size appropriate for the terminal size

    screen_height, screen_width = stdscr.getmaxyx()

    lines = text.split("\n")

    win_height = min(len(lines) + 4, screen_height)
    win_width = min(max(len(line) for line in lines) + 4, screen_width)

    win.resize(win_height, win_width)
    win.mvwin((screen_height - win_height)//2,
              (screen_width - win_width)//2)

def _draw_key_dialog(win, title, text):
    win.erase()
    _draw_frame(win, title)

    for i, line in enumerate(text.split("\n")):
        _safe_addstr(win, 2 + i, 2, line)

    win.noutrefresh()

def _draw_frame(win, title):
    # Draw a frame around the inner edges of 'win', with 'title' at the top

    win_height, win_width = win.getmaxyx()

    win.attron(_DIALOG_FRAME_STYLE)

    # Draw top/bottom edge
    _safe_hline(win,              0, 0, " ", win_width)
    _safe_hline(win, win_height - 1, 0, " ", win_width)

    # Draw left/right edge
    _safe_vline(win, 0,             0, " ", win_height)
    _safe_vline(win, 0, win_width - 1, " ", win_height)

    # Draw title
    _safe_addstr(win, 0, (win_width - len(title))//2, title)

    win.attroff(_DIALOG_FRAME_STYLE)

def _jump_to_dialog():
    # Search text
    s = ""
    # Previous search text
    prev_s = None
    # Search text cursor position
    s_i = 0
    # Horizontal scroll offset
    hscroll = 0

    # Index of selected row
    sel_node_i = 0
    # Index in 'matches' of the top row of the list
    scroll = 0

    # Edit box at the top
    edit_box = _styled_win(_INPUT_FIELD_STYLE)
    edit_box.keypad(True)

    # List of matches
    matches_win = _styled_win(_LIST_STYLE)

    # Bottom separator, with arrows pointing down
    bot_sep_win = _styled_win(_SEPARATOR_STYLE)

    # Help window with instructions at the bottom
    help_win = _styled_win(_HELP_STYLE)

    # Give windows their initial size
    _resize_jump_to_dialog(edit_box, matches_win, bot_sep_win, help_win,
                           sel_node_i, scroll)

    _safe_curs_set(2)

    # TODO: Code duplication with _select_{next,prev}_menu_entry(). Can this be
    # factored out in some nice way?

    def select_next_match():
        nonlocal sel_node_i
        nonlocal scroll

        if sel_node_i < len(matches) - 1:
            sel_node_i += 1

            if sel_node_i >= scroll + matches_win.getmaxyx()[0] - _SCROLL_OFFSET:
                scroll = min(scroll + 1, _max_scroll(matches, matches_win))

    def select_prev_match():
        nonlocal sel_node_i
        nonlocal scroll

        if sel_node_i > 0:
           sel_node_i -= 1

           if sel_node_i <= scroll + _SCROLL_OFFSET:
               scroll = max(scroll - 1, 0)

    while True:
        if s != prev_s:
            # The search text changed. Find new matching nodes.

            prev_s = s

            try:
                regex_searches = [re.compile(regex, re.IGNORECASE).search
                                  for regex in s.split()]

                # No exception thrown, so the regexes are okay
                bad_re = None

                # List of (node, node_string) tuples for the matching nodes
                matches = []

                # Go through the list of (node, node_string) tuples, where
                # 'node_string' describes 'node'
                for node, node_string in _search_strings():
                    for search in regex_searches:
                        if not search(node_string):
                            break
                    else:
                        matches.append((node, node_string))

            except re.error as e:
                # Bad regex. Remember the error message so we can show it.
                bad_re = e.msg
                matches = []

            # Reset scroll and jump to the top of the list of matches
            sel_node_i = scroll = 0

        _draw_jump_to_dialog(edit_box, matches_win, bot_sep_win, help_win,
                             s, s_i, hscroll,
                             bad_re, matches, sel_node_i, scroll)
        curses.doupdate()


        c = _get_wch_compat(edit_box)

        if c == "\n":
            if matches:
                _jump_to(matches[sel_node_i][0])
                _safe_curs_set(0)
                return

        if c == "\x1B":  # \x1B = ESC
            _safe_curs_set(0)
            return


        if c == curses.KEY_RESIZE:
            # We adjust the scroll so that the selected node stays visible in
            # the list when the terminal is resized, hence the 'scroll'
            # assignment
            scroll = _resize_jump_to_dialog(
                edit_box, matches_win, bot_sep_win, help_win,
                sel_node_i, scroll)

        elif c == curses.KEY_DOWN:
            select_next_match()

        elif c == curses.KEY_UP:
            select_prev_match()

        elif c == curses.KEY_NPAGE:  # Page Down
            # Keep it simple. This way we get sane behavior for small windows,
            # etc., for free.
            for _ in range(_PG_JUMP):
                select_next_match()

        elif c == curses.KEY_PPAGE:  # Page Up
            for _ in range(_PG_JUMP):
                select_prev_match()

        else:
            s, s_i, hscroll = _edit_text(c, s, s_i, hscroll,
                                         edit_box.getmaxyx()[1] - 2)

# Obscure Python: We never pass a value for cached_search_strings, and it keeps
# pointing to the same list. This avoids a global.
def _search_strings(cached_search_strings=[]):
    # Returns a list with (node, node_string) tuples for all symbol menu nodes,
    # sorted by symbol name.
    #
    # node_string is a string containing the symbol's name and prompt. It is
    # matched against the regex(es) the user inputs during search, and doubles
    # as the string displayed for the node in the list of matches.

    # This is a static list. Only computing it once makes the search dialog
    # come up a bit faster after the first time it's entered.
    if not cached_search_strings:
        # Defined symbols sorted by name, with duplicates removed.
        #
        # Duplicates appear when symbols have multiple menu nodes (definition
        # locations), but they appear in menu order, which isn't what we want
        # here. We'd still need to go through sym.nodes as well.
        for sym in sorted(set(_kconf.defined_syms), key=lambda sym: sym.name):
            for node in sym.nodes:
                node_string = sym.name
                if node.prompt:
                    node_string += ' "{}"'.format(node.prompt[0])
                cached_search_strings.append((node, node_string))

    return cached_search_strings

def _resize_jump_to_dialog(edit_box, matches_win, bot_sep_win, help_win,
                           sel_node_i, scroll):
    # Resizes the jump-to dialog to fill the terminal.
    #
    # Returns the new scroll index. We adjust the scroll if needed so that the
    # selected node stays visible.

    screen_height, screen_width = stdscr.getmaxyx()

    bot_sep_win.resize(1, screen_width)

    help_win_height = len(_JUMP_TO_HELP_LINES)
    matches_win_height = screen_height - help_win_height - 4

    if matches_win_height >= 1:
        edit_box.resize(3, screen_width)
        matches_win.resize(matches_win_height, screen_width)
        help_win.resize(help_win_height, screen_width)

        matches_win.mvwin(3, 0)
        bot_sep_win.mvwin(3 + matches_win_height, 0)
        help_win.mvwin(3 + matches_win_height + 1, 0)
    else:
        # Degenerate case. Give up on nice rendering and just prevent errors.

        matches_win_height = 1

        edit_box.resize(screen_height, screen_width)
        matches_win.resize(1, screen_width)
        help_win.resize(1, screen_width)

        for win in matches_win, bot_sep_win, help_win:
            win.mvwin(0, 0)

    # Adjust the scroll so that the selected row is still within the window, if
    # needed
    if sel_node_i - scroll >= matches_win_height:
        return sel_node_i - matches_win_height + 1
    return scroll

def _draw_jump_to_dialog(edit_box, matches_win, bot_sep_win, help_win,
                         s, s_i, hscroll,
                         bad_re, matches, sel_node_i, scroll):
    edit_width = edit_box.getmaxyx()[1] - 2


    #
    # Update list of matches
    #

    matches_win.erase()

    if matches:
        for i in range(scroll,
                       min(scroll + matches_win.getmaxyx()[0], len(matches))):

            _safe_addstr(matches_win, i - scroll, 0, matches[i][1],
                         _LIST_SEL_STYLE if i == sel_node_i else _LIST_STYLE)

    else:
        # bad_re holds the error message from the re.error exception on errors
        _safe_addstr(matches_win, 0, 0,
                     "No matches"
                     if bad_re is None else
                     "Bad regular expression: " + bad_re)

    matches_win.noutrefresh()


    #
    # Update bottom separator line
    #

    bot_sep_win.erase()

    # Draw arrows pointing down if the symbol list is scrolled up
    if scroll < _max_scroll(matches, matches_win):
        _safe_hline(bot_sep_win, 0, 4, curses.ACS_DARROW, _N_SCROLL_ARROWS)

    bot_sep_win.noutrefresh()


    #
    # Update help window at bottom
    #

    help_win.erase()

    for i, line in enumerate(_JUMP_TO_HELP_LINES):
        _safe_addstr(help_win, i, 0, line)

    help_win.noutrefresh()


    #
    # Update edit box. We do this last since it makes it handy to position the
    # cursor.
    #

    edit_box.erase()

    _draw_frame(edit_box, "Jump to symbol")

    # Draw arrows pointing up if the symbol list is scrolled down
    if scroll > 0:
        # TODO: Bit ugly that _DIALOG_FRAME_STYLE is repeated here
        _safe_hline(edit_box, 2, 4, curses.ACS_UARROW, _N_SCROLL_ARROWS,
                    _DIALOG_FRAME_STYLE)

    # Note: Perhaps having a separate window for the input field would be nicer
    visible_s = s[hscroll:hscroll + edit_width]
    _safe_addstr(edit_box, 1, 1, visible_s, _INPUT_FIELD_STYLE)

    _safe_move(edit_box, 1, 1 + s_i - hscroll)

    edit_box.noutrefresh()

def _info_dialog(node):
    # Shows a fullscreen window with information about 'node'

    # Top row, with title and arrows point up
    top_line_win = _styled_win(_SEPARATOR_STYLE)

    # Text display
    text_win = _styled_win(_INFO_TEXT_STYLE)
    text_win.keypad(True)

    # Bottom separator, with arrows pointing down
    bot_sep_win = _styled_win(_SEPARATOR_STYLE)

    # Help window with keys at the bottom
    help_win = _styled_win(_HELP_STYLE)

    # Give windows their initial size
    _resize_info_dialog(top_line_win, text_win, bot_sep_win, help_win)


    # Get lines of help text
    lines = _info_str(node).split("\n")

    # Index of first row in 'lines' to show
    scroll = 0

    while True:
        _draw_info_dialog(node, lines, scroll, top_line_win, text_win,
                          bot_sep_win, help_win)
        curses.doupdate()


        c = _get_wch_compat(text_win)

        if c == curses.KEY_RESIZE:
            _resize_info_dialog(top_line_win, text_win, bot_sep_win, help_win)

        elif c in (curses.KEY_DOWN, "j", "J"):
            if scroll < _max_scroll(lines, text_win):
                scroll += 1

        elif c in (curses.KEY_NPAGE, "\x04"):  # Page Down/Ctrl-D
            scroll = min(scroll + _PG_JUMP, _max_scroll(lines, text_win))

        elif c in (curses.KEY_PPAGE, "\x15"):  # Page Up/Ctrl-U
            scroll = max(scroll - _PG_JUMP, 0)

        elif c in (curses.KEY_END, "G"):
            scroll = _max_scroll(lines, text_win)

        elif c in (curses.KEY_HOME, "g"):
            scroll = 0

        elif c in (curses.KEY_UP, "k", "K"):
            if scroll > 0:
                scroll -= 1

        elif c in (curses.KEY_LEFT, curses.KEY_BACKSPACE, _ERASE_CHAR,
                   "\x1B",  # \x1B = ESC
                   "q", "Q", "h", "H"):

            return

def _resize_info_dialog(top_line_win, text_win, bot_sep_win, help_win):
    # Resizes the info dialog to fill the terminal

    screen_height, screen_width = stdscr.getmaxyx()

    top_line_win.resize(1, screen_width)
    bot_sep_win.resize(1, screen_width)

    help_win_height = len(_INFO_HELP_LINES)
    text_win_height = screen_height - help_win_height - 2

    if text_win_height >= 1:
        text_win.resize(text_win_height, screen_width)
        help_win.resize(help_win_height, screen_width)

        text_win.mvwin(1, 0)
        bot_sep_win.mvwin(1 + text_win_height, 0)
        help_win.mvwin(1 + text_win_height + 1, 0)
    else:
        # Degenerate case. Give up on nice rendering and just prevent errors.

        text_win.resize(1, screen_width)
        help_win.resize(1, screen_width)

        for win in text_win, bot_sep_win, help_win:
            win.mvwin(0, 0)

def _draw_info_dialog(node, lines, scroll, top_line_win, text_win,
                      bot_sep_win, help_win):

    text_win_height, text_win_width = text_win.getmaxyx()


    #
    # Update top row
    #

    top_line_win.erase()

    # Draw arrows pointing up if the information window is scrolled down. Draw
    # them before drawing the title, so the title ends up on top for small
    # windows.
    if scroll > 0:
        _safe_hline(top_line_win, 0, 4, curses.ACS_UARROW, _N_SCROLL_ARROWS)


    if isinstance(node.item, Symbol):
        title = "{}{}".format(_kconf.config_prefix, node.item.name)

    elif isinstance(node.item, Choice):
        title = node.item.name or "Choice"

    elif node.item == MENU:
        title = 'menu "{}"'.format(node.prompt[0])

    else:  # node.item == COMMENT
        title = 'comment "{}"'.format(node.prompt[0])


    _safe_addstr(top_line_win, 0, (text_win_width - len(title))//2, title)

    top_line_win.noutrefresh()


    #
    # Update text display
    #

    text_win.erase()

    for i, line in enumerate(lines[scroll:scroll + text_win_height]):
        _safe_addstr(text_win, i, 0, line)

    text_win.noutrefresh()


    #
    # Update bottom separator line
    #

    bot_sep_win.erase()

    # Draw arrows pointing down if the symbol window is scrolled up
    if scroll < _max_scroll(lines, text_win):
        _safe_hline(bot_sep_win, 0, 4, curses.ACS_DARROW, _N_SCROLL_ARROWS)

    bot_sep_win.noutrefresh()


    #
    # Update help window at bottom
    #

    help_win.erase()

    for i, line in enumerate(_INFO_HELP_LINES):
        _safe_addstr(help_win, i, 0, line)

    help_win.noutrefresh()

def _info_str(node):
    # Returns information about the menu node 'node' as a string.
    #
    # The helper functions are responsible for adding newlines. This allows
    # them to return "" if they don't want to add any output.

    if isinstance(node.item, Symbol):
        sym = node.item

        return (
            _prompt_info(sym) +
            "Type: {}\n".format(TYPE_TO_STR[sym.type]) +
            'Value: "{}"\n\n'.format(sym.str_value) +
            _help_info(sym) +
            _direct_dep_info(sym) +
            _defaults_info(sym) +
            _select_imply_info(sym) +
            _kconfig_def_info(sym)
        )

    if isinstance(node.item, Choice):
        choice = node.item

        return (
            _prompt_info(choice) +
            "Type: {}\n".format(TYPE_TO_STR[choice.type]) +
            'Mode: "{}"\n\n'.format(choice.str_value) +
            _help_info(choice) +
            _choice_syms_info(choice) +
            _direct_dep_info(choice) +
            _defaults_info(choice) +
            _kconfig_def_info(choice)
        )

    # node.item in (MENU, COMMENT)
    return _kconfig_def_info(node)

def _prompt_info(sc):
    # Returns a string listing the prompts of 'sc' (Symbol or Choice)

    s = ""

    for node in sc.nodes:
        if node.prompt:
            s += "Prompt: {}\n".format(node.prompt[0])

    return s

def _choice_syms_info(choice):
    # Returns a string listing the choice symbols in 'choice'. Adds
    # "(selected)" next to the selected one.

    s = "Choice symbols:\n"

    for sym in choice.syms:
        s += "  - " + sym.name
        if sym is choice.selection:
            s += " (selected)"
        s += "\n"

    return s + "\n"

def _help_info(sc):
    # Returns a string with the help text(s) of 'sc' (Symbol or Choice).
    # Symbols and choices defined in multiple locations can have multiple help
    # texts.

    s = ""

    for node in sc.nodes:
        if node.help is not None:
            s += "Help:\n\n{}\n\n" \
                 .format(textwrap.indent(node.help, "  "))

    return s

def _direct_dep_info(sc):
    # Returns a string describing the direct dependencies of 'sc' (Symbol or
    # Choice). The direct dependencies are the OR of the dependencies from each
    # definition location. The dependencies at each definition location come
    # from 'depends on' and dependencies inherited from parent items.

    if sc.direct_dep is _kconf.y:
        return ""

    return 'Direct dependencies (value: "{}"):\n{}\n' \
           .format(TRI_TO_STR[expr_value(sc.direct_dep)],
                   _split_expr_info(sc.direct_dep, 2))

def _defaults_info(sc):
    # Returns a string describing the defaults of 'sc' (Symbol or Choice)

    if not sc.defaults:
        return ""

    s = "Defaults:\n"

    for val, cond in sc.defaults:
        s += "  - "
        if isinstance(sc, Symbol):
            s += '{} (value: "{}")' \
                 .format(_expr_str(val), TRI_TO_STR[expr_value(val)])
        else:
            # Don't print the value next to the symbol name for choice
            # defaults, as it looks a bit confusing
            s += val.name
        s += "\n"

        if cond is not _kconf.y:
            s += '    Condition (value: "{}"):\n{}' \
                 .format(TRI_TO_STR[expr_value(cond)],
                         _split_expr_info(cond, 7))

    return s + "\n"

def _split_expr_info(expr, indent):
    # Returns a string with 'expr' split into its top-level && or || operands,
    # with one operand per line, together with the operand's value. This is
    # usually enough to get something readable for long expressions. A fancier
    # recursive thingy would be possible too.
    #
    # indent:
    #   Number of leading spaces to add before the split expression.

    if len(split_expr(expr, AND)) > 1:
        split_op = AND
        op_str = "&&"
    else:
        split_op = OR
        op_str = "||"

    s = ""
    for i, term in enumerate(split_expr(expr, split_op)):
        s += '{}{} {} (value: "{}")\n' \
             .format(" "*indent,
                     "  " if i == 0 else op_str,
                     _expr_str(term),
                     TRI_TO_STR[expr_value(term)])
    return s

def _select_imply_info(sym):
    # Returns a string with information about which symbols 'select' or 'imply'
    # 'sym'. The selecting/implying symbols are grouped according to which
    # value they select/imply 'sym' to (n/m/y).

    s = ""

    def add_sis(expr, val, title):
        nonlocal s

        # sis = selects/implies
        sis = [si for si in split_expr(expr, OR) if expr_value(si) == val]

        if sis:
            s += title
            for si in sis:
                s += "  - {}\n".format(split_expr(si, AND)[0].name)
            s += "\n"

    if sym.rev_dep is not _kconf.n:
        add_sis(sym.rev_dep, 2, "Symbols currently y-selecting this symbol:\n")
        add_sis(sym.rev_dep, 1, "Symbols currently m-selecting this symbol:\n")
        add_sis(sym.rev_dep, 0, "Symbols currently n-selecting this symbol (no effect):\n")

    if sym.weak_rev_dep is not _kconf.n:
        add_sis(sym.weak_rev_dep, 2, "Symbols currently y-implying this symbol:\n")
        add_sis(sym.weak_rev_dep, 1, "Symbols currently m-implying this symbol:\n")
        add_sis(sym.weak_rev_dep, 0, "Symbols currently n-implying this symbol (no effect):\n")

    return s

def _kconfig_def_info(item):
    # Returns a string with the definition of 'item' in Kconfig syntax,
    # together with the definition location(s)

    nodes = [item] if isinstance(item, MenuNode) else item.nodes

    s = "Kconfig definition{}, with propagated dependencies\n" \
        .format("s" if len(nodes) > 1 else "")
    s += (len(s) - 1)*"=" + "\n\n"

    s += "\n\n".join("At {}:{}, in menu {}:\n\n{}".format(
                         node.filename, node.linenr, _menu_path_info(node),
                         textwrap.indent(str(node), "  "))
                     for node in nodes)

    return s

def _menu_path_info(node):
    # Returns a string describing the menu path leading up to 'node'

    path = ""

    menu = node.parent
    while menu is not _kconf.top_node:
        path = " -> " + menu.prompt[0] + path
        menu = menu.parent

    return "(top menu)" + path

def _styled_win(style):
    # Returns a new curses window with background 'style' and space as the fill
    # character. The initial dimensions are (1, 1), so the window needs to be
    # sized and positioned separately.

    win = curses.newwin(1, 1)
    win.bkgdset(" ", style)
    return win

def _max_scroll(lst, win):
    # Assuming 'lst' is a list of items to be displayed in 'win',
    # returns the maximum number of steps 'win' can be scrolled down.
    # We stop scrolling when the bottom item is visible.

    return max(0, len(lst) - win.getmaxyx()[0])

def _edit_text(c, s, i, hscroll, width):
    # Implements text editing commands for edit boxes. Takes a character (which
    # could also be e.g. curses.KEY_LEFT) and the edit box state, and returns
    # the new state after the character has been processed.
    #
    # c:
    #   Character from user
    #
    # s:
    #   Current contents of string
    #
    # i:
    #   Current cursor index in string
    #
    # hscroll:
    #   Index in s of the leftmost character in the edit box, for horizontal
    #   scrolling
    #
    # width:
    #   Width in characters of the edit box
    #
    # Return value:
    #   An (s, i, hscroll) tuple for the new state

    if c == curses.KEY_LEFT:
        if i > 0:
            i -= 1

    elif c == curses.KEY_RIGHT:
        if i < len(s):
            i += 1

    elif c in (curses.KEY_HOME, "\x01"):  # \x01 = CTRL-A
        i = 0

    elif c in (curses.KEY_END, "\x05"):  # \x05 = CTRL-E
        i = len(s)

    elif c in (curses.KEY_BACKSPACE, _ERASE_CHAR):
        if i > 0:
            s = s[:i-1] + s[i:]
            i -= 1

    elif c == curses.KEY_DC:
        s = s[:i] + s[i+1:]

    elif c == "\x17":  # \x17 = CTRL-W
        # The \W removes characters like ',' one at a time
        new_i = re.search(r"(?:\w*|\W)\s*$", s[:i]).start()
        s = s[:new_i] + s[i:]
        i = new_i

    elif c == "\x0B":  # \x0B = CTRL-K
        s = s[:i]

    elif c == "\x15":  # \x15 = CTRL-U
        s = s[i:]
        i = 0

    elif isinstance(c, str):
        # Insert character

        s = s[:i] + c + s[i:]
        i += 1


    # Adjust the horizontal scroll if the cursor would be outside the input
    # field
    if i < hscroll:
        hscroll = i
    elif i >= hscroll + width:
        hscroll = i - width + 1


    return s, i, hscroll

def _msg(title, text):
    # Pops up a message dialog that can be dismissed with Space/Enter/ESC

    _key_dialog(title, text, " \n")

def _error(text):
    # Pops up an error dialog that can be dismissed with Space/Enter/ESC

    _msg("Error", text)

def _node_str(node):
    # Returns the complete menu entry text for a menu node.
    #
    # Example return value: "[*] Support for X"

    # Calculate the indent to print the item with by checking how many levels
    # above it the closest 'menuconfig' item is (this includes menus and
    # choices as well as menuconfig symbols)
    indent = 0
    parent = node.parent
    while not parent.is_menuconfig:
        indent += _SUBMENU_INDENT
        parent = parent.parent

    # This approach gives nice alignment for empty string symbols ("()  Foo")
    s = "{:{}} ".format(_value_str(node), 3 + indent)

    if not node.prompt:
        # Show the symbol/choice name in <> brackets if it has no prompt. This
        # path can only hit in show-all mode.
        s += "<{}>".format(node.item.name)

    else:
        if node.item == COMMENT:
            s += "*** {} ***".format(node.prompt[0])
        else:
            s += node.prompt[0]

        if isinstance(node.item, Symbol):
            sym = node.item

            # Print "(NEW)" next to symbols without a user value (from e.g. a
            # .config), but skip it for choice symbols in choices in y mode
            if sym.user_value is None and \
               not (sym.choice and sym.choice.tri_value == 2):

                s += " (NEW)"

        if isinstance(node.item, Choice) and node.item.tri_value == 2:
            # Print the prompt of the selected symbol after the choice for
            # choices in y mode
            sym = node.item.selection
            if sym:
                for node_ in sym.nodes:
                    if node_.prompt:
                        s += " ({})".format(node_.prompt[0])

    # Print "--->" next to nodes that have menus that can potentially be
    # entered. Add "(empty)" if the menu is empty. We don't allow those to be
    # entered.
    if node.is_menuconfig:
        s += "  --->" if _shown_nodes(node) else "  ---> (empty)"

    return s

def _value_str(node):
    # Returns the value part ("[*]", "<M>", "(foo)" etc.) of a menu node

    item = node.item

    if item in (MENU, COMMENT):
        return ""

    # Wouldn't normally happen, and generates a warning
    if item.type == UNKNOWN:
        return ""

    if item.type in (STRING, INT, HEX):
        return "({})".format(item.str_value)

    # BOOL or TRISTATE

    if _is_y_mode_choice_sym(item):
        return "(X)" if item.choice.selection is item else "( )"

    tri_val_str = (" ", "M", "*")[item.tri_value]

    if len(item.assignable) == 1:
        # Pinned to a single value
        return "" if isinstance(item, Choice) else "-{}-".format(tri_val_str)

    if item.type == BOOL:
        return "[{}]".format(tri_val_str)

    if item.type == TRISTATE:
        if item.assignable == (1, 2):
            return "{{{}}}".format(tri_val_str)  # {M}/{*}
        return "<{}>".format(tri_val_str)

def _is_y_mode_choice_sym(item):
    # The choice mode is an upper bound on the visibility of choice symbols, so
    # we can check the choice symbols' own visibility to see if the choice is
    # in y mode
    return isinstance(item, Symbol) and item.choice and item.visibility == 2

def _check_validity(sym, s):
    # Returns True if the string 's' is a well-formed value for 'sym'.
    # Otherwise, displays an error and returns False.

    if sym.type not in (INT, HEX):
        # Anything goes for non-int/hex symbols
        return True

    base = 10 if sym.type == INT else 16

    try:
        int(s, base)
    except ValueError:
        _error("'{}' is a malformed {} value"
               .format(s, TYPE_TO_STR[sym.type]))
        return False

    for low_sym, high_sym, cond in sym.ranges:
        if expr_value(cond):
            low = int(low_sym.str_value, base)
            val = int(s, base)
            high = int(high_sym.str_value, base)

            if not low <= val <= high:
                _error("{} is outside the range {}-{}"
                       .format(s, low_sym.str_value, high_sym.str_value))

                return False

            break

    return True

def _range_info(sym):
    # Returns a string with information about the valid range for the symbol
    # 'sym', or None if 'sym' isn't an int/hex symbol

    if sym.type not in (INT, HEX):
        return None

    for low, high, cond in sym.ranges:
        if expr_value(cond):
            return "Range: {}-{}".format(low.str_value, high.str_value)

    return "No range constraints."

def _is_num(name):
    # Heuristic to see if a symbol name looks like a number, for nicer output
    # when printing expressions. Things like 16 are actually symbol names, only
    # they get their name as their value when the symbol is undefined.

    try:
        int(name, 10)
        return True

    except ValueError:
        if not name.startswith(("0x", "0X")):
            return False

        try:
            int(name, 16)
            return True

        except ValueError:
            return False

def _get_wch_compat(win):
    # Decent resizing behavior on PDCurses requires calling resize_term(0, 0)
    # after receiving KEY_RESIZE, while NCURSES (usually) handles terminal
    # resizing automatically in get(_w)ch() (see the end of the
    # resizeterm(3NCURSES) man page).
    #
    # resize_term(0, 0) reliably fails and does nothing on NCURSES, so this
    # hack gives NCURSES/PDCurses compatibility for resizing. I don't know
    # whether it would cause trouble for other implementations.

    c = win.get_wch()
    if c == curses.KEY_RESIZE:
        try:
            curses.resize_term(0, 0)
        except curses.error:
            pass

    return c

# Ignore exceptions from some functions that might fail, e.g. for small
# windows. They usually do reasonable things anyway.

def _safe_curs_set(visibility):
    try:
        curses.curs_set(visibility)
    except curses.error:
        pass

def _safe_addstr(win, *args):
    try:
        win.addstr(*args)
    except curses.error:
        pass

def _safe_addch(win, *args):
    try:
        win.addch(*args)
    except curses.error:
        pass

def _safe_hline(win, *args):
    try:
        win.hline(*args)
    except curses.error:
        pass

def _safe_vline(win, *args):
    try:
        win.vline(*args)
    except curses.error:
        pass

def _safe_move(win, *args):
    try:
        win.move(*args)
    except curses.error:
        pass

def _convert_c_lc_ctype_to_utf8():
    # See _CONVERT_C_LC_CTYPE_TO_UTF8

    if _IS_WINDOWS:
        # Windows rarely has issues here, and the PEP 538 implementation avoids
        # changing the locale on it. None of the UTF-8 locales below were
        # supported from some quick testing either. Play it safe.
        return

    def _try_set_locale(loc):
        try:
            locale.setlocale(locale.LC_CTYPE, loc)
            return True
        except locale.Error:
            return False

    # Is LC_CTYPE set to the C locale?
    if locale.setlocale(locale.LC_CTYPE, None) == "C":
        # This list was taken from the PEP 538 implementation in the CPython
        # code, in Python/pylifecycle.c
        for loc in "C.UTF-8", "C.utf8", "UTF-8":
            if _try_set_locale(loc):
                print("Note: Your environment is configured to use ASCII. To "
                      "avoid Unicode issues, LC_CTYPE was changed from the "
                      "C locale to the {} locale.".format(loc))
                break

# Are we running on Windows?
_IS_WINDOWS = (platform.system() == "Windows")

if __name__ == "__main__":
    if len(sys.argv) > 2:
        print("usage: {} [Kconfig]".format(sys.argv[0]), file=sys.stderr)
        sys.exit(1)

    menuconfig(Kconfig("Kconfig" if len(sys.argv) < 2 else sys.argv[1]))