def walk(node):
    '''
    Bottom-up recursive walk through a data structure yielding a (key, value,
    node) tuple for every entry. `node[key] == value` is true in every entry.

    For example:

        >>> list(walk([{'x': 1}]))
        [
            ('x', 1, {'x': 1}),         # leaf:   key, value, node
            (0, {'x': 1}, [{'x': 1}])   # parent: index, value, node
        ]

    Circular linkage can lead to a RuntimeError.

        >>> x = {}
        >>> x['x'] = x
        >>> list(walk(x))
        ...
        RuntimeError: maximum recursion depth exceeded
    '''
    if hasattr(node, 'items'):
        # Convert note.items() to list to prevent keys changing during iteration
        for key, value in list(node.items()):
            yield from walk(value)
            yield key, value, node
    elif isinstance(node, list):
        for index, value in enumerate(node):
            yield from walk(value)
            yield index, value, node

def merge(old, new, mode='overwrite', warn=None, _path=''):
    '''
    Update old dict with new dict recursively.

        >>> merge({'a': {'x': 1}}, {'a': {'y': 2}})
        {'a': {'x': 1, 'y': 2}}

    If `new` is a list, convert into a dict with random keys.

    If `mode='overwrite'`, the old dict is overwritten (default).
    If `mode='setdefault'`, the old dict values are updated only if missing.

    `warn=` is an optional list of key paths. Any conflict on dictionaries
    matching any of these paths is logged as a warning. For example,
    `warn=['url.*', 'watch.*']` warns if any url: sub-key or watch: sub-key
    has a conflict.
    '''
    for key in new:
        if key in old and hasattr(old[key], 'items') and hasattr(new[key], 'items'):
            path_key = _path + ('.' if _path else '') + str(key)
            if warn is not None:
                for pattern in warn:
                    if fnmatch(path_key, pattern):
                        app_log.warning(f'Duplicate key: {path_key}')
                        break
            merge(old=old[key], new=new[key], mode=mode, warn=warn, _path=path_key)
        elif mode == 'overwrite' or key not in old:
            old[key] = deepcopy(new[key])
    return old

def objectpath(node, keypath, default=None):
    '''
    Traverse down a dot-separated object path into dict items or object attrs.
    For example, `objectpath(handler, 'request.headers.User-Agent')` returns
    `handler.request.headers['User-Agent']`. Dictionary access is preferred.
    Returns `None` if the path is not found.
    '''
    for key in keypath.split('.'):
        if hasattr(node, '__getitem__'):
            node = node.get(key)
        else:
            node = getattr(node, key, None)
        if node is None:
            return default
    return node

def recursive_encode(data, encoding='utf-8'):
    '''Convert Unicode to UTF-8 encoded byte strings in-place.'''
    for key, value, node in walk(data):
        if isinstance(key, str):
            newkey = key.encode(encoding)
            node[newkey] = node.pop(key)
            key = newkey
        if isinstance(value, str):
            node[key] = value.encode(encoding)

def prune_keys(conf, keys={}):
    '''Returns a deep copy of a configuration removing specified keys.

    `prune_keys(conf, {'comment'})` drops the "comment" key from any dict or sub-dict.
    '''
    if isinstance(conf, dict):
        conf = AttrDict({k: prune_keys(v, keys) for k, v in conf.items() if k not in keys})
    elif isinstance(conf, (list, tuple)):
        conf = [prune_keys(v, keys) for v in conf]
    return conf

def used_kwargs(method, kwargs, ignore_keywords=False):
    '''
    Splits kwargs into those used by method, and those that are not.

    Returns a tuple of (used, rest). *used* is a dict subset of kwargs with only
    keys used by method. *rest* has the remaining kwargs keys.

    If the method uses `**kwargs` (keywords), it uses all keys. To ignore this
    and return only named arguments, use `ignore_keywords=True`.
    '''
    # In Pandas 1.5, DataFrame.to_csv and DataFrame.to_excel are wrapped with @deprecate_kwargs.
    # We dive deeper to detect the actual keywords. __wrapped__ is provided by functools.wraps
    # https://docs.python.org/3/library/functools.html
    while hasattr(method, '__wrapped__'):
        method = method.__wrapped__
    argspec = inspect.getfullargspec(method)
    # If method uses **kwargs, return all kwargs (unless you ignore **kwargs)
    if argspec.varkw and not ignore_keywords:
        used, rest = kwargs, {}
    else:
        # Split kwargs into 2 dicts -- used and rest
        used, rest = {}, {}
        for key, val in kwargs.items():
            target = used if key in set(argspec.args) else rest
            target[key] = val
    return used, rest

def random_string(size, chars=_valid_key_chars):
    '''Return random string of length size using chars (which defaults to alphanumeric)'''
    # B311:random random() is safe since it's for non-cryptographic use
    return ''.join(choice(chars) for index in range(size))  # nosec B311

def setup_variables():
    '''Initialise variables'''
    variables = DefaultAttrDict(str)
    # Load all environment variables, and overwrite with secrets
    variables.update(os.environ)
    variables.update(secrets)
    # GRAMEXPATH is the Gramex root directory
    variables['GRAMEXPATH'] = _gramex_path
    # GRAMEXAPPS is the Gramex apps directory
    variables['GRAMEXAPPS'] = os.path.join(_gramex_path, 'apps')
    # GRAMEXHOST is the hostname
    variables['GRAMEXHOST'] = socket.gethostname()
    # GRAMEXDATA varies based on OS
    if 'GRAMEXDATA' not in variables:
        if sys.platform.startswith('linux') or sys.platform == 'cygwin':
            variables['GRAMEXDATA'] = os.path.expanduser('~/.config/gramexdata')
        elif sys.platform == 'win32':
            variables['GRAMEXDATA'] = os.path.join(variables['LOCALAPPDATA'], 'Gramex Data')
        elif sys.platform == 'darwin':
            variables['GRAMEXDATA'] = os.path.expanduser(
                '~/Library/Application Support/Gramex Data'
            )
        else:
            variables['GRAMEXDATA'] = os.path.abspath('.')
            app_log.warning(f'$GRAMEXDATA set to {variables["GRAMEXDATA"]} for OS {sys.platform}')

    return variables

def load_imports(config, source, warn=None):
    '''
    Post-process a config for imports.

    `config` is the data to process. `source` is the path where it was
    loaded from.

    If `config` has an `import:` key, treat all values below that as YAML
    files (specified relative to `source`) and import them in sequence.

    Return a list of imported paths as :func:_pathstat objects. (This includes
    `source`.)

    For example, if the `source` is  `base.yaml` (which has the below
    configuration) and is loaded into `config`.

        app:
            port: 20
            start: true
        path: /
        import: update*.yaml    # Can be any glob, e.g. */gramex.yaml

    ... and `update.yaml` looks like this.

        app:
            port: 30
            new: yes

    ... then after this function is called, `config` looks like this.

        app:
            port: 20        # From base.yaml. NOT updated by update.yaml
            start: true     # From base.yaml
            new: yes        # From update.yaml
        path: /             # From base.yaml

    The `import:` keys are deleted. The return value contains :func:_pathstat
    values for `base.yaml` and `update.yaml` in that order.

    Multiple `import:` values can be specified as a dictionary.

        import:
            first-app: app1/*.yaml
            next-app: app2/*.yaml

    To import sub-keys as namespaces

        import:
            app: {path: */gramex.yaml, namespace: 'url'}

    This prefixes all keys under `url:`. Here are more examples.

        namespace: True             # Add namespace to all top-level keys
        namespace: url              # Add namespace to url.*
        namespace: log.loggers      # Add namespace to log.loggers.*
        namespace: [True, url]      # Add namespace to top level keys and url.*

    By default, the prefix is the relative path of the imported YAML file
    (relative to the importer).

    `warn=` is an optional list of key paths. Any conflict on dictionaries
    matching any of these paths is logged as a warning. For example,
    `warn=['url.*', 'watch.*']` warns if any url: sub-key or watch: sub-key
    has a conflict.
    '''
    imported_paths = [_pathstat(source)]
    root = source.absolute().parent
    for key, value, node in list(walk(config)):
        if isinstance(key, str) and key.startswith('import.merge'):
            # Strip the top level key(s) from import.merge values
            if isinstance(value, dict):
                for name, conf in value.items():
                    node[name] = conf
            elif value:
                raise ValueError(f'import.merge: must be dict, not {value!r} at {source}')
            # Delete the import key
            del node[key]
        elif key == 'import':
            # Convert "import: path" to "import: {app: path}"
            if isinstance(value, str):
                value = {'apps': value}
            # Allow "import: [path, path]" to "import: {app0: path, app1: path}"
            elif isinstance(value, list):
                value = OrderedDict(((f'app{i}', conf) for i, conf in enumerate(value)))
            # By now, import: should be a dict
            elif not isinstance(value, dict):
                raise ValueError(f'import: must be string/list/dict, not {value!r} at {source}')
            # If already a dict with a single import via 'path', convert to dict of apps
            if 'path' in value:
                value = {'app': value}
            for name, conf in value.items():
                if not isinstance(conf, dict):
                    conf = AttrDict(path=conf)
                if 'path' not in conf:
                    raise ValueError(f'import: has no conf at {source}')
                paths = conf.pop('path')
                paths = paths if isinstance(paths, list) else [paths]
                globbed_paths = []
                for path in paths:
                    globbed_paths += sorted(root.glob(path)) if '*' in path else [Path(path)]
                ns = conf.pop('namespace', None)
                for path in globbed_paths:
                    abspath = root.joinpath(path)
                    new_conf = _yaml_open(abspath, **conf)
                    if ns is not None:
                        prefix = Path(path).as_posix()
                        new_conf = _add_ns(new_conf, ns, name + ':' + prefix)
                    imported_paths += load_imports(new_conf, source=abspath)
                    merge(old=node, new=new_conf, mode='setdefault', warn=warn)
            # Delete the import key
            del node[key]
    return imported_paths

def locate(path, modules=[], forceload=0):
    '''
    Locate an object by name or dotted path.

    For example, `locate('str')` returns the `str` built-in.
    `locate('gramex.handlers.FileHandler')` returns the class
    `gramex.handlers.FileHandler`.

    `modules` is a list of modules to search for the path in first. So
    `locate('FileHandler', modules=[gramex.handlers])` will return
    `gramex.handlers.FileHandler`.

    If importing raises an Exception, log it and return None.
    '''
    try:
        for module_name in modules:
            module = _locate(module_name, forceload)
            if hasattr(module, path):
                return getattr(module, path)
        return _locate(path, forceload)
    except ErrorDuringImport:
        app_log.exception(f'Exception when importing {path}')
        return None

def ioloop_running(loop):
    '''Returns whether the Tornado ioloop is running on not'''
    # TODO: Pressing Ctrl+C may cause this to raise an exception. Explore how to handle that
    return loop.asyncio_loop.is_running()

def setup_secrets(path, max_age_days=1000000, clear=True):
    '''
    Load `<path>` (which must be Path) as a YAML file. Update it into gramex.config.variables.

    If there's a `SECRETS_URL:` and `SECRETS_KEY:` key, the text from `SECRETS_URL:` is
    decrypted using `secrets_key`.

    If there's a `SECRETS_IMPORT:` string, list or dict, the values are treated as file patterns
    pointing to other secrets file to be imported.
    '''
    if not path.is_file():
        return

    with path.open(encoding='utf-8') as handle:
        result = yaml.safe_load(handle)
    # Ignore empty .secrets.yaml
    if not result:
        return
    # If it's non-empty, it must be a dict
    if not isinstance(result, dict):
        raise ValueError(f'{path}: must be a YAML file with a single dict')
    # Clear secrets if we are re-initializing. Not if we're importing recursively.
    if clear:
        secrets.clear()
    # If SECRETS_URL: and SECRETS_KEY: are set, fetch secrets from URL and decrypted with the key.
    # This allows changing secrets remotely without access to the server.
    secrets_url = result.pop('SECRETS_URL', None)
    secrets_key = result.pop('SECRETS_KEY', None)
    if secrets_url and secrets_key:
        from urllib.request import urlopen
        from tornado.web import decode_signed_value

        app_log.info(f'Fetching remote secrets from {secrets_url}')
        # Load string from the URL -- but ignore comments. file:// URLs are fine too
        # B310:urllib_urlopen secrets can be local files or URLs
        value = yaml.safe_load(urlopen(secrets_url))  # nosec B310
        value = decode_signed_value(secrets_key, '', value, max_age_days=max_age_days)
        result.update(loads(value.decode('utf-8')))
    # If SECRETS_IMPORT: is set, fetch secrets from those file(s) as well.
    # SECRETS_IMPORT: can be a file pattern, or a list/dict of file patterns
    secrets_import = result.pop('SECRETS_IMPORT', None)
    if secrets_import:
        # Create a list of file patterns to import from
        imports = (
            list(secrets_import.values())
            if isinstance(secrets_import, dict)
            else secrets_import
            if isinstance(secrets_import, (list, tuple))
            else [secrets_import]
        )
        for pattern in imports:
            for import_path in path.parent.glob(pattern):
                setup_secrets(import_path, max_age_days, clear=False)
    secrets.update(result)