import copy
import os
import re
import string
import sys
import warnings
from contextlib import contextmanager
from enum import Enum
from textwrap import dedent
from typing import (
    Any,
    Dict,
    Iterator,
    List,
    Optional,
    Tuple,
    Type,
    Union,
    get_type_hints,
)

import yaml

from .errors import (
    ConfigIndexError,
    ConfigTypeError,
    ConfigValueError,
    GrammarParseError,
    OmegaConfBaseException,
    ValidationError,
)
from .grammar_parser import SIMPLE_INTERPOLATION_PATTERN, parse

try:
    import dataclasses

except ImportError:  # pragma: no cover
    dataclasses = None  # type: ignore # pragma: no cover

try:
    import attr

except ImportError:  # pragma: no cover
    attr = None  # type: ignore # pragma: no cover


# Regexprs to match key paths like: a.b, a[b], ..a[c].d, etc.
# We begin by matching the head (in these examples: a, a, ..a).
# This can be read as "dots followed by any character but `.` or `[`"
# Note that a key starting with brackets, like [a], is purposedly *not*
# matched here and will instead be handled in the next regex below (this
# is to keep this regex simple).
KEY_PATH_HEAD = re.compile(r"(\.)*[^.[]*")
# Then we match other keys. The following expression matches one key and can
# be read as a choice between two syntaxes:
#   - `.` followed by anything except `.` or `[` (ex: .b, .d)
#   - `[` followed by anything then `]` (ex: [b], [c])
KEY_PATH_OTHER = re.compile(r"\.([^.[]*)|\[(.*?)\]")


# source: https://yaml.org/type/bool.html
YAML_BOOL_TYPES = [
    "y",
    "Y",
    "yes",
    "Yes",
    "YES",
    "n",
    "N",
    "no",
    "No",
    "NO",
    "true",
    "True",
    "TRUE",
    "false",
    "False",
    "FALSE",
    "on",
    "On",
    "ON",
    "off",
    "Off",
    "OFF",
]


class Marker:
    def __init__(self, desc: str):
        self.desc = desc

    def __repr__(self) -> str:
        return self.desc


# To be used as default value when `None` is not an option.
_DEFAULT_MARKER_: Any = Marker("_DEFAULT_MARKER_")


class OmegaConfDumper(yaml.Dumper):  # type: ignore
    str_representer_added = False

    @staticmethod
    def str_representer(dumper: yaml.Dumper, data: str) -> yaml.ScalarNode:
        with_quotes = yaml_is_bool(data) or is_int(data) or is_float(data)
        return dumper.represent_scalar(
            yaml.resolver.BaseResolver.DEFAULT_SCALAR_TAG,
            data,
            style=("'" if with_quotes else None),
        )


def get_omega_conf_dumper() -> Type[OmegaConfDumper]:
    if not OmegaConfDumper.str_representer_added:
        OmegaConfDumper.add_representer(str, OmegaConfDumper.str_representer)
        OmegaConfDumper.str_representer_added = True
    return OmegaConfDumper


def yaml_is_bool(b: str) -> bool:
    return b in YAML_BOOL_TYPES


def get_yaml_loader() -> Any:
    class OmegaConfLoader(yaml.SafeLoader):  # type: ignore
        def construct_mapping(self, node: yaml.Node, deep: bool = False) -> Any:
            keys = set()
            for key_node, value_node in node.value:
                if key_node.tag != yaml.resolver.BaseResolver.DEFAULT_SCALAR_TAG:
                    continue
                if key_node.value in keys:
                    raise yaml.constructor.ConstructorError(
                        "while constructing a mapping",
                        node.start_mark,
                        f"found duplicate key {key_node.value}",
                        key_node.start_mark,
                    )
                keys.add(key_node.value)
            return super().construct_mapping(node, deep=deep)

    loader = OmegaConfLoader
    loader.add_implicit_resolver(
        "tag:yaml.org,2002:float",
        re.compile(
            """^(?:
         [-+]?(?:[0-9][0-9_]*)\\.[0-9_]*(?:[eE][-+]?[0-9]+)?
        |[-+]?(?:[0-9][0-9_]*)(?:[eE][-+]?[0-9]+)
        |\\.[0-9_]+(?:[eE][-+][0-9]+)?
        |[-+]?[0-9][0-9_]*(?::[0-5]?[0-9])+\\.[0-9_]*
        |[-+]?\\.(?:inf|Inf|INF)
        |\\.(?:nan|NaN|NAN))$""",
            re.X,
        ),
        list("-+0123456789."),
    )
    loader.yaml_implicit_resolvers = {
        key: [
            (tag, regexp)
            for tag, regexp in resolvers
            if tag != "tag:yaml.org,2002:timestamp"
        ]
        for key, resolvers in loader.yaml_implicit_resolvers.items()
    }
    return loader


def _get_class(path: str) -> type:
    from importlib import import_module

    module_path, _, class_name = path.rpartition(".")
    mod = import_module(module_path)
    try:
        klass: type = getattr(mod, class_name)
    except AttributeError:
        raise ImportError(f"Class {class_name} is not in module {module_path}")
    return klass


def _is_union(type_: Any) -> bool:
    return getattr(type_, "__origin__", None) is Union


def _resolve_optional(type_: Any) -> Tuple[bool, Any]:
    """Check whether `type_` is equivalent to `typing.Optional[T]` for some T."""
    if getattr(type_, "__origin__", None) is Union:
        args = type_.__args__
        if len(args) == 2 and args[1] == type(None):  # noqa E721
            return True, args[0]
    if type_ is Any:
        return True, Any

    return False, type_


def _is_optional(obj: Any, key: Optional[Union[int, str]] = None) -> bool:
    """Check `obj` metadata to see if the given node is optional."""
    from .base import Container, Node

    if key is not None:
        assert isinstance(obj, Container)
        obj = obj._get_node(key)
    if isinstance(obj, Node):
        return obj._is_optional()
    else:
        # In case `obj` is not a Node, treat it as optional by default.
        # This is used in `ListConfig.append` and `ListConfig.insert`
        # where the appended/inserted value might or might not be a Node.
        return True


def _resolve_forward(type_: Type[Any], module: str) -> Type[Any]:
    import typing  # lgtm [py/import-and-import-from]

    forward = typing.ForwardRef if hasattr(typing, "ForwardRef") else typing._ForwardRef  # type: ignore
    if type(type_) is forward:
        return _get_class(f"{module}.{type_.__forward_arg__}")
    else:
        if is_dict_annotation(type_):
            kt, vt = get_dict_key_value_types(type_)
            if kt is not None:
                kt = _resolve_forward(kt, module=module)
            if vt is not None:
                vt = _resolve_forward(vt, module=module)
            return Dict[kt, vt]  # type: ignore
        if is_list_annotation(type_):
            et = get_list_element_type(type_)
            if et is not None:
                et = _resolve_forward(et, module=module)
            return List[et]  # type: ignore

        return type_


def extract_dict_subclass_data(obj: Any, parent: Any) -> Optional[Dict[str, Any]]:
    """Check if obj is an instance of a subclass of Dict. If so, extract the Dict keys/values."""
    from omegaconf.omegaconf import _maybe_wrap

    is_type = isinstance(obj, type)
    obj_type = obj if is_type else type(obj)
    subclasses_dict = is_dict_subclass(obj_type)

    if subclasses_dict:
        warnings.warn(
            f"Class `{obj_type.__name__}` subclasses `Dict`."
            + " Subclassing `Dict` in Structured Config classes is deprecated,"
            + " see github.com/omry/omegaconf/issues/663",
            UserWarning,
            stacklevel=9,
        )

    if is_type:
        return None
    elif subclasses_dict:
        dict_subclass_data = {}
        key_type, element_type = get_dict_key_value_types(obj_type)
        for name, value in obj.items():
            is_optional, type_ = _resolve_optional(element_type)
            type_ = _resolve_forward(type_, obj.__module__)
            try:
                dict_subclass_data[name] = _maybe_wrap(
                    ref_type=type_,
                    is_optional=is_optional,
                    key=name,
                    value=value,
                    parent=parent,
                )
            except ValidationError as ex:
                format_and_raise(
                    node=None, key=name, value=value, cause=ex, msg=str(ex)
                )
        return dict_subclass_data
    else:
        return None


def get_attr_class_field_names(obj: Any) -> List[str]:
    is_type = isinstance(obj, type)
    obj_type = obj if is_type else type(obj)
    return list(attr.fields_dict(obj_type))


def get_attr_data(obj: Any, allow_objects: Optional[bool] = None) -> Dict[str, Any]:
    from omegaconf.omegaconf import OmegaConf, _maybe_wrap

    flags = {"allow_objects": allow_objects} if allow_objects is not None else {}

    from omegaconf import MISSING

    d = {}
    is_type = isinstance(obj, type)
    obj_type = obj if is_type else type(obj)
    dummy_parent = OmegaConf.create({}, flags=flags)
    dummy_parent._metadata.object_type = obj_type

    for name, attrib in attr.fields_dict(obj_type).items():
        is_optional, type_ = _resolve_optional(attrib.type)
        type_ = _resolve_forward(type_, obj.__module__)
        if not is_type:
            value = getattr(obj, name)
        else:
            value = attrib.default
            if value == attr.NOTHING:
                value = MISSING
        if _is_union(type_):
            e = ConfigValueError(
                f"Union types are not supported:\n{name}: {type_str(type_)}"
            )
            format_and_raise(node=None, key=None, value=value, cause=e, msg=str(e))

        try:
            d[name] = _maybe_wrap(
                ref_type=type_,
                is_optional=is_optional,
                key=name,
                value=value,
                parent=dummy_parent,
            )
        except (ValidationError, GrammarParseError) as ex:
            format_and_raise(
                node=dummy_parent, key=name, value=value, cause=ex, msg=str(ex)
            )
        d[name]._set_parent(None)
    dict_subclass_data = extract_dict_subclass_data(obj=obj, parent=dummy_parent)
    if dict_subclass_data is not None:
        d.update(dict_subclass_data)
    return d


def get_dataclass_field_names(obj: Any) -> List[str]:
    return [field.name for field in dataclasses.fields(obj)]


def get_dataclass_data(
    obj: Any, allow_objects: Optional[bool] = None
) -> Dict[str, Any]:
    from omegaconf.omegaconf import MISSING, OmegaConf, _maybe_wrap

    flags = {"allow_objects": allow_objects} if allow_objects is not None else {}
    d = {}
    obj_type = get_type_of(obj)
    dummy_parent = OmegaConf.create({}, flags=flags)
    dummy_parent._metadata.object_type = obj_type
    resolved_hints = get_type_hints(obj_type)
    for field in dataclasses.fields(obj):
        name = field.name
        is_optional, type_ = _resolve_optional(resolved_hints[field.name])
        type_ = _resolve_forward(type_, obj.__module__)

        if hasattr(obj, name):
            value = getattr(obj, name)
            if value == dataclasses.MISSING:
                value = MISSING
        else:
            if field.default_factory == dataclasses.MISSING:  # type: ignore
                value = MISSING
            else:
                value = field.default_factory()  # type: ignore

        if _is_union(type_):
            e = ConfigValueError(
                f"Union types are not supported:\n{name}: {type_str(type_)}"
            )
            format_and_raise(node=None, key=None, value=value, cause=e, msg=str(e))
        try:
            d[name] = _maybe_wrap(
                ref_type=type_,
                is_optional=is_optional,
                key=name,
                value=value,
                parent=dummy_parent,
            )
        except (ValidationError, GrammarParseError) as ex:
            format_and_raise(
                node=dummy_parent, key=name, value=value, cause=ex, msg=str(ex)
            )
        d[name]._set_parent(None)
    dict_subclass_data = extract_dict_subclass_data(obj=obj, parent=dummy_parent)
    if dict_subclass_data is not None:
        d.update(dict_subclass_data)
    return d


def is_dataclass(obj: Any) -> bool:
    from omegaconf.base import Node

    if dataclasses is None or isinstance(obj, Node):
        return False
    return dataclasses.is_dataclass(obj)


def is_attr_class(obj: Any) -> bool:
    from omegaconf.base import Node

    if attr is None or isinstance(obj, Node):
        return False
    return attr.has(obj)


def is_structured_config(obj: Any) -> bool:
    return is_attr_class(obj) or is_dataclass(obj)


def is_dataclass_frozen(type_: Any) -> bool:
    return type_.__dataclass_params__.frozen  # type: ignore


def is_attr_frozen(type_: type) -> bool:
    # This is very hacky and probably fragile as well.
    # Unfortunately currently there isn't an official API in attr that can detect that.
    # noinspection PyProtectedMember
    return type_.__setattr__ == attr._make._frozen_setattrs  # type: ignore


def get_type_of(class_or_object: Any) -> Type[Any]:
    type_ = class_or_object
    if not isinstance(type_, type):
        type_ = type(class_or_object)
    assert isinstance(type_, type)
    return type_


def is_structured_config_frozen(obj: Any) -> bool:
    type_ = get_type_of(obj)

    if is_dataclass(type_):
        return is_dataclass_frozen(type_)
    if is_attr_class(type_):
        return is_attr_frozen(type_)
    return False


def get_structured_config_field_names(obj: Any) -> List[str]:
    if is_dataclass(obj):
        return get_dataclass_field_names(obj)
    elif is_attr_class(obj):
        return get_attr_class_field_names(obj)
    else:
        raise ValueError(f"Unsupported type: {type(obj).__name__}")


def get_structured_config_data(
    obj: Any, allow_objects: Optional[bool] = None
) -> Dict[str, Any]:
    if is_dataclass(obj):
        return get_dataclass_data(obj, allow_objects=allow_objects)
    elif is_attr_class(obj):
        return get_attr_data(obj, allow_objects=allow_objects)
    else:
        raise ValueError(f"Unsupported type: {type(obj).__name__}")


class ValueKind(Enum):
    VALUE = 0
    MANDATORY_MISSING = 1
    INTERPOLATION = 2


def _is_missing_value(value: Any) -> bool:
    from omegaconf import Node

    if isinstance(value, Node):
        value = value._value()
    return _is_missing_literal(value)


def _is_missing_literal(value: Any) -> bool:
    # Uses literal '???' instead of the MISSING const for performance reasons.
    return isinstance(value, str) and value == "???"


def _is_none(
    value: Any, resolve: bool = False, throw_on_resolution_failure: bool = True
) -> bool:
    from omegaconf import Node

    if not isinstance(value, Node):
        return value is None

    if resolve:
        value = value._maybe_dereference_node(
            throw_on_resolution_failure=throw_on_resolution_failure
        )
        if not throw_on_resolution_failure and value is None:
            # Resolution failure: consider that it is *not* None.
            return False
        assert isinstance(value, Node)

    return value._is_none()


def get_value_kind(
    value: Any, strict_interpolation_validation: bool = False
) -> ValueKind:
    """
    Determine the kind of a value
    Examples:
    VALUE: "10", "20", True
    MANDATORY_MISSING: "???"
    INTERPOLATION: "${foo.bar}", "${foo.${bar}}", "${foo:bar}", "[${foo}, ${bar}]",
                   "ftp://${host}/path", "${foo:${bar}, [true], {'baz': ${baz}}}"

    :param value: Input to classify.
    :param strict_interpolation_validation: If `True`, then when `value` is a string
        containing "${", it is parsed to validate the interpolation syntax. If `False`,
        this parsing step is skipped: this is more efficient, but will not detect errors.
    """

    if _is_missing_value(value):
        return ValueKind.MANDATORY_MISSING

    value = _get_value(value)

    # We identify potential interpolations by the presence of "${" in the string.
    # Note that escaped interpolations (ex: "esc: \${bar}") are identified as
    # interpolations: this is intended, since they must be processed as interpolations
    # for the string to be properly un-escaped.
    # Keep in mind that invalid interpolations will only be detected when
    # `strict_interpolation_validation` is True.
    if isinstance(value, str) and "${" in value:
        if strict_interpolation_validation:
            # First try the cheap regex matching that detects common interpolations.
            if SIMPLE_INTERPOLATION_PATTERN.match(value) is None:
                # If no match, do the more expensive grammar parsing to detect errors.
                parse(value)
        return ValueKind.INTERPOLATION
    else:
        return ValueKind.VALUE


# DEPRECATED: remove in 2.2
def is_bool(st: str) -> bool:
    st = str.lower(st)
    return st == "true" or st == "false"


def is_float(st: str) -> bool:
    try:
        float(st)
        return True
    except ValueError:
        return False


def is_int(st: str) -> bool:
    try:
        int(st)
        return True
    except ValueError:
        return False


# DEPRECATED: remove in 2.2
def decode_primitive(s: str) -> Any:
    if is_bool(s):
        return str.lower(s) == "true"

    if is_int(s):
        return int(s)

    if is_float(s):
        return float(s)

    return s


def is_primitive_list(obj: Any) -> bool:
    from .base import Container

    return not isinstance(obj, Container) and isinstance(obj, (list, tuple))


def is_primitive_dict(obj: Any) -> bool:
    t = get_type_of(obj)
    return t is dict


def is_dict_annotation(type_: Any) -> bool:
    origin = getattr(type_, "__origin__", None)
    if sys.version_info < (3, 7, 0):
        return origin is Dict or type_ is Dict  # pragma: no cover
    else:  # pragma: no cover
        # type_dict is a bit hard to detect.
        # this support is tentative, if it eventually causes issues in other areas it may be dropped.
        typed_dict = hasattr(type_, "__base__") and type_.__base__ == dict
        return origin is dict or typed_dict


def is_list_annotation(type_: Any) -> bool:
    origin = getattr(type_, "__origin__", None)
    if sys.version_info < (3, 7, 0):
        return origin is List or type_ is List  # pragma: no cover
    else:
        return origin is list  # pragma: no cover


def is_tuple_annotation(type_: Any) -> bool:
    origin = getattr(type_, "__origin__", None)
    if sys.version_info < (3, 7, 0):
        return origin is Tuple or type_ is Tuple  # pragma: no cover
    else:
        return origin is tuple  # pragma: no cover


def is_dict_subclass(type_: Any) -> bool:
    return type_ is not None and isinstance(type_, type) and issubclass(type_, Dict)


def is_dict(obj: Any) -> bool:
    return is_primitive_dict(obj) or is_dict_annotation(obj) or is_dict_subclass(obj)


def is_primitive_container(obj: Any) -> bool:
    return is_primitive_list(obj) or is_primitive_dict(obj)


def get_list_element_type(ref_type: Optional[Type[Any]]) -> Any:
    args = getattr(ref_type, "__args__", None)
    if ref_type is not List and args is not None and args[0]:
        element_type = args[0]
    else:
        element_type = Any
    return element_type


def get_dict_key_value_types(ref_type: Any) -> Tuple[Any, Any]:
    args = getattr(ref_type, "__args__", None)
    if args is None:
        bases = getattr(ref_type, "__orig_bases__", None)
        if bases is not None and len(bases) > 0:
            args = getattr(bases[0], "__args__", None)

    key_type: Any
    element_type: Any
    if ref_type is None or ref_type == Dict:
        key_type = Any
        element_type = Any
    else:
        if args is not None:
            key_type = args[0]
            element_type = args[1]
        else:
            key_type = Any
            element_type = Any

    return key_type, element_type


def valid_value_annotation_type(type_: Any) -> bool:
    return type_ is Any or is_primitive_type(type_) or is_structured_config(type_)


def _valid_dict_key_annotation_type(type_: Any) -> bool:
    from omegaconf import DictKeyType

    return type_ is None or type_ is Any or issubclass(type_, DictKeyType.__args__)  # type: ignore


def is_primitive_type(type_: Any) -> bool:
    type_ = get_type_of(type_)
    return issubclass(type_, Enum) or type_ in (int, float, bool, str, type(None))


def _is_interpolation(v: Any, strict_interpolation_validation: bool = False) -> bool:
    if isinstance(v, str):
        ret = (
            get_value_kind(v, strict_interpolation_validation)
            == ValueKind.INTERPOLATION
        )
        assert isinstance(ret, bool)
        return ret
    return False


def _get_value(value: Any) -> Any:
    from .base import Container
    from .nodes import ValueNode

    if isinstance(value, ValueNode):
        return value._value()
    elif isinstance(value, Container):
        boxed = value._value()
        if boxed is None or _is_missing_literal(boxed) or _is_interpolation(boxed):
            return boxed

    # return primitives and regular OmegaConf Containers as is
    return value


def get_ref_type(obj: Any, key: Any = None) -> Optional[Type[Any]]:
    from omegaconf import Container, Node

    if isinstance(obj, Container):
        if key is not None:
            obj = obj._get_node(key)
    else:
        if key is not None:
            raise ValueError("Key must only be provided when obj is a container")

    if isinstance(obj, Node):
        ref_type = obj._metadata.ref_type
        if obj._is_optional() and ref_type is not Any:
            return Optional[ref_type]  # type: ignore
        else:
            return ref_type
    else:
        return Any  # type: ignore


def _raise(ex: Exception, cause: Exception) -> None:
    # Set the environment variable OC_CAUSE=1 to get a stacktrace that includes the
    # causing exception.
    env_var = os.environ["OC_CAUSE"] if "OC_CAUSE" in os.environ else None
    debugging = sys.gettrace() is not None
    full_backtrace = (debugging and not env_var == "0") or (env_var == "1")
    if full_backtrace:
        ex.__cause__ = cause
    else:
        ex.__cause__ = None
    raise ex.with_traceback(sys.exc_info()[2])  # set end OC_CAUSE=1 for full backtrace


def format_and_raise(
    node: Any,
    key: Any,
    value: Any,
    msg: str,
    cause: Exception,
    type_override: Any = None,
) -> None:
    from omegaconf import OmegaConf
    from omegaconf.base import Node

    if isinstance(cause, AssertionError):
        raise

    if isinstance(cause, OmegaConfBaseException) and cause._initialized:
        ex = cause
        if type_override is not None:
            ex = type_override(str(cause))
            ex.__dict__ = copy.deepcopy(cause.__dict__)
        _raise(ex, cause)

    object_type: Optional[Type[Any]]
    object_type_str: Optional[str] = None
    ref_type: Optional[Type[Any]]
    ref_type_str: Optional[str]

    child_node: Optional[Node] = None
    if node is None:
        full_key = key if key is not None else ""
        object_type = None
        ref_type = None
        ref_type_str = None
    else:
        if key is not None and not node._is_none():
            child_node = node._get_node(key, validate_access=False)

        try:
            full_key = node._get_full_key(key=key)
        except Exception as exc:
            # Since we are handling an exception, raising a different one here would
            # be misleading. Instead, we display it in the key.
            full_key = f"<unresolvable due to {type(exc).__name__}: {exc}>"

        object_type = OmegaConf.get_type(node)
        object_type_str = type_str(object_type)

        ref_type = get_ref_type(node)
        ref_type_str = type_str(ref_type)

    msg = string.Template(msg).safe_substitute(
        REF_TYPE=ref_type_str,
        OBJECT_TYPE=object_type_str,
        KEY=key,
        FULL_KEY=full_key,
        VALUE=value,
        VALUE_TYPE=type_str(type(value), include_module_name=True),
        KEY_TYPE=f"{type(key).__name__}",
    )

    if ref_type not in (None, Any):
        template = dedent(
            """\
            $MSG
                full_key: $FULL_KEY
                reference_type=$REF_TYPE
                object_type=$OBJECT_TYPE"""
        )
    else:
        template = dedent(
            """\
            $MSG
                full_key: $FULL_KEY
                object_type=$OBJECT_TYPE"""
        )
    s = string.Template(template=template)

    message = s.substitute(
        REF_TYPE=ref_type_str, OBJECT_TYPE=object_type_str, MSG=msg, FULL_KEY=full_key
    )
    exception_type = type(cause) if type_override is None else type_override
    if exception_type == TypeError:
        exception_type = ConfigTypeError
    elif exception_type == IndexError:
        exception_type = ConfigIndexError

    ex = exception_type(f"{message}")
    if issubclass(exception_type, OmegaConfBaseException):
        ex._initialized = True
        ex.msg = message
        ex.parent_node = node
        ex.child_node = child_node
        ex.key = key
        ex.full_key = full_key
        ex.value = value
        ex.object_type = object_type
        ex.object_type_str = object_type_str
        ex.ref_type = ref_type
        ex.ref_type_str = ref_type_str

    _raise(ex, cause)


def type_str(t: Any, include_module_name: bool = False) -> str:
    is_optional, t = _resolve_optional(t)
    if t is None:
        return type(t).__name__
    if t is Any:
        return "Any"
    if t is ...:
        return "..."

    if sys.version_info < (3, 7, 0):  # pragma: no cover
        # Python 3.6
        if hasattr(t, "__name__"):
            name = str(t.__name__)
        else:
            if t.__origin__ is not None:
                name = type_str(t.__origin__)
            else:
                name = str(t)
                if name.startswith("typing."):
                    name = name[len("typing.") :]
    else:  # pragma: no cover
        # Python >= 3.7
        if hasattr(t, "__name__"):
            name = str(t.__name__)
        else:
            if t._name is None:
                if t.__origin__ is not None:
                    name = type_str(
                        t.__origin__, include_module_name=include_module_name
                    )
            else:
                name = str(t._name)

    args = getattr(t, "__args__", None)
    if args is not None:
        args = ", ".join(
            [type_str(t, include_module_name=include_module_name) for t in t.__args__]
        )
        ret = f"{name}[{args}]"
    else:
        ret = name
    if include_module_name:
        if (
            hasattr(t, "__module__")
            and t.__module__ != "builtins"
            and t.__module__ != "typing"
            and not t.__module__.startswith("omegaconf.")
        ):
            module_prefix = t.__module__ + "."
        else:
            module_prefix = ""
        ret = module_prefix + ret
    if is_optional:
        return f"Optional[{ret}]"
    else:
        return ret


def _ensure_container(target: Any, flags: Optional[Dict[str, bool]] = None) -> Any:
    from omegaconf import OmegaConf

    if is_primitive_container(target):
        assert isinstance(target, (list, dict))
        target = OmegaConf.create(target, flags=flags)
    elif is_structured_config(target):
        target = OmegaConf.structured(target, flags=flags)
    elif not OmegaConf.is_config(target):
        raise ValueError(
            "Invalid input. Supports one of "
            + "[dict,list,DictConfig,ListConfig,dataclass,dataclass instance,attr class,attr class instance]"
        )

    return target


def is_generic_list(type_: Any) -> bool:
    """
    Checks if a type is a generic list, for example:
    list returns False
    typing.List returns False
    typing.List[T] returns True

    :param type_: variable type
    :return: bool
    """
    return is_list_annotation(type_) and get_list_element_type(type_) is not None


def is_generic_dict(type_: Any) -> bool:
    """
    Checks if a type is a generic dict, for example:
    list returns False
    typing.List returns False
    typing.List[T] returns True

    :param type_: variable type
    :return: bool
    """
    return is_dict_annotation(type_) and len(get_dict_key_value_types(type_)) > 0


def is_container_annotation(type_: Any) -> bool:
    return is_list_annotation(type_) or is_dict_annotation(type_)


def split_key(key: str) -> List[str]:
    """
    Split a full key path into its individual components.

    This is similar to `key.split(".")` but also works with the getitem syntax:
        "a.b"       -> ["a", "b"]
        "a[b]"      -> ["a, "b"]
        ".a.b[c].d" -> ["", "a", "b", "c", "d"]
        "[a].b"     -> ["a", "b"]
    """
    # Obtain the first part of the key (in docstring examples: a, a, .a, '')
    first = KEY_PATH_HEAD.match(key)
    assert first is not None
    first_stop = first.span()[1]

    # `tokens` will contain all elements composing the key.
    tokens = key[0:first_stop].split(".")

    # Optimization in case `key` has no other component: we are done.
    if first_stop == len(key):
        return tokens

    if key[first_stop] == "[" and not tokens[-1]:
        # This is a special case where the first key starts with brackets, e.g.
        # [a] or ..[a]. In that case there is an extra "" in `tokens` that we
        # need to get rid of:
        #   [a]   -> tokens = [""] but we would like []
        #   ..[a] -> tokens = ["", "", ""] but we would like ["", ""]
        tokens.pop()

    # Identify other key elements (in docstring examples: b, b, b/c/d, b)
    others = KEY_PATH_OTHER.findall(key[first_stop:])

    # There are two groups in the `KEY_PATH_OTHER` regex: one for keys starting
    # with a dot (.b, .d) and one for keys starting with a bracket ([b], [c]).
    # Only one group can be non-empty.
    tokens += [dot_key if dot_key else bracket_key for dot_key, bracket_key in others]

    return tokens


# Similar to Python 3.7+'s `contextlib.nullcontext` (which should be used instead,
# once support for Python 3.6 is dropped).
@contextmanager
def nullcontext(enter_result: Any = None) -> Iterator[Any]:
    yield enter_result

[((53, 16, 53, 42), 're.compile', 're.compile', ({(53, 27, 53, 41): '"""(\\\\.)*[^.[]*"""'}, {}), "('(\\\\.)*[^.[]*')", False, 'import re\n'), ((58, 17, 58, 52), 're.compile', 're.compile', ({(58, 28, 58, 51): '"""\\\\.([^.[]*)|\\\\[(.*?)\\\\]"""'}, {}), "('\\\\.([^.[]*)|\\\\[(.*?)\\\\]')", False, 'import re\n'), ((171, 10, 171, 36), 'importlib.import_module', 'import_module', ({(171, 24, 171, 35): 'module_path'}, {}), '(module_path)', False, 'from importlib import import_module\n'), ((292, 19, 292, 52), 'omegaconf.OmegaConf.create', 'OmegaConf.create', (), '', False, 'from omegaconf import OmegaConf\n'), ((341, 19, 341, 52), 'omegaconf.OmegaConf.create', 'OmegaConf.create', (), '', False, 'from omegaconf import OmegaConf\n'), ((343, 21, 343, 45), 'typing.get_type_hints', 'get_type_hints', ({(343, 36, 343, 44): 'obj_type'}, {}), '(obj_type)', False, 'from typing import Any, Dict, Iterator, List, Optional, Tuple, Type, Union, get_type_hints\n'), ((344, 17, 344, 40), 'dataclasses.fields', 'dataclasses.fields', ({(344, 36, 344, 39): 'obj'}, {}), '(obj)', False, 'import dataclasses\n'), ((388, 11, 388, 40), 'dataclasses.is_dataclass', 'dataclasses.is_dataclass', ({(388, 36, 388, 39): 'obj'}, {}), '(obj)', False, 'import dataclasses\n'), ((396, 11, 396, 24), 'attr.has', 'attr.has', ({(396, 20, 396, 23): 'obj'}, {}), '(obj)', False, 'import attr\n'), ((796, 8, 796, 42), 'string.Template', 'string.Template', (), '', False, 'import string\n'), ((144, 8, 153, 9), 're.compile', 're.compile', ({(145, 12, 151, 32): '"""^(?:\n         [-+]?(?:[0-9][0-9_]*)\\\\.[0-9_]*(?:[eE][-+]?[0-9]+)?\n        |[-+]?(?:[0-9][0-9_]*)(?:[eE][-+]?[0-9]+)\n        |\\\\.[0-9_]+(?:[eE][-+][0-9]+)?\n        |[-+]?[0-9][0-9_]*(?::[0-5]?[0-9])+\\\\.[0-9_]*\n        |[-+]?\\\\.(?:inf|Inf|INF)\n        |\\\\.(?:nan|NaN|NAN))$"""', (152, 12, 152, 16): 're.X'}, {}), '(\n    """^(?:\n         [-+]?(?:[0-9][0-9_]*)\\\\.[0-9_]*(?:[eE][-+]?[0-9]+)?\n        |[-+]?(?:[0-9][0-9_]*)(?:[eE][-+]?[0-9]+)\n        |\\\\.[0-9_]+(?:[eE][-+][0-9]+)?\n        |[-+]?[0-9][0-9_]*(?::[0-5]?[0-9])+\\\\.[0-9_]*\n        |[-+]?\\\\.(?:inf|Inf|INF)\n        |\\\\.(?:nan|NaN|NAN))$"""\n    , re.X)', False, 'import re\n'), ((243, 8, 249, 9), 'warnings.warn', 'warnings.warn', (), '', False, 'import warnings\n'), ((279, 16, 279, 42), 'attr.fields_dict', 'attr.fields_dict', ({(279, 33, 279, 41): 'obj_type'}, {}), '(obj_type)', False, 'import attr\n'), ((713, 16, 713, 30), 'sys.gettrace', 'sys.gettrace', ({}, {}), '()', False, 'import sys\n'), ((765, 22, 765, 46), 'omegaconf.OmegaConf.get_type', 'OmegaConf.get_type', ({(765, 41, 765, 45): 'node'}, {}), '(node)', False, 'from omegaconf import OmegaConf\n'), ((782, 19, 788, 9), 'textwrap.dedent', 'dedent', ({(783, 12, 787, 43): '"""            $MSG\n                full_key: $FULL_KEY\n                reference_type=$REF_TYPE\n                object_type=$OBJECT_TYPE"""'}, {}), '(\n    """            $MSG\n                full_key: $FULL_KEY\n                reference_type=$REF_TYPE\n                object_type=$OBJECT_TYPE"""\n    )', False, 'from textwrap import dedent\n'), ((790, 19, 795, 9), 'textwrap.dedent', 'dedent', ({(791, 12, 794, 43): '"""            $MSG\n                full_key: $FULL_KEY\n                object_type=$OBJECT_TYPE"""'}, {}), '(\n    """            $MSG\n                full_key: $FULL_KEY\n                object_type=$OBJECT_TYPE"""\n    )', False, 'from textwrap import dedent\n'), ((887, 17, 887, 54), 'omegaconf.OmegaConf.create', 'OmegaConf.create', (), '', False, 'from omegaconf import OmegaConf\n'), ((295, 24, 295, 50), 'attr.fields_dict', 'attr.fields_dict', ({(295, 41, 295, 49): 'obj_type'}, {}), '(obj_type)', False, 'import attr\n'), ((311, 22, 317, 13), 'omegaconf.omegaconf._maybe_wrap', '_maybe_wrap', (), '', False, 'from omegaconf.omegaconf import MISSING, OmegaConf, _maybe_wrap\n'), ((330, 36, 330, 59), 'dataclasses.fields', 'dataclasses.fields', ({(330, 55, 330, 58): 'obj'}, {}), '(obj)', False, 'import dataclasses\n'), ((365, 22, 371, 13), 'omegaconf.omegaconf._maybe_wrap', '_maybe_wrap', (), '', False, 'from omegaconf.omegaconf import MISSING, OmegaConf, _maybe_wrap\n'), ((719, 28, 719, 42), 'sys.exc_info', 'sys.exc_info', ({}, {}), '()', False, 'import sys\n'), ((740, 26, 740, 55), 'copy.deepcopy', 'copy.deepcopy', ({(740, 40, 740, 54): 'cause.__dict__'}, {}), '(cause.__dict__)', False, 'import copy\n'), ((771, 10, 771, 30), 'string.Template', 'string.Template', ({(771, 26, 771, 29): 'msg'}, {}), '(msg)', False, 'import string\n'), ((889, 17, 889, 58), 'omegaconf.OmegaConf.structured', 'OmegaConf.structured', (), '', False, 'from omegaconf import OmegaConf\n'), ((890, 13, 890, 40), 'omegaconf.OmegaConf.is_config', 'OmegaConf.is_config', ({(890, 33, 890, 39): 'target'}, {}), '(target)', False, 'from omegaconf import OmegaConf\n'), ((132, 26, 137, 21), 'yaml.constructor.ConstructorError', 'yaml.constructor.ConstructorError', ({(133, 24, 133, 54): '"""while constructing a mapping"""', (134, 24, 134, 39): 'node.start_mark', (135, 24, 135, 63): 'f"""found duplicate key {key_node.value}"""', (136, 24, 136, 43): 'key_node.start_mark'}, {}), "('while constructing a mapping', node.\n    start_mark, f'found duplicate key {key_node.value}', key_node.start_mark)", False, 'import yaml\n'), ((260, 43, 266, 17), 'omegaconf.omegaconf._maybe_wrap', '_maybe_wrap', (), '', False, 'from omegaconf.omegaconf import MISSING, OmegaConf, _maybe_wrap\n')]