##############################################################################
#
# Copyright (c) 2003 Zope Foundation and Contributors.
# All Rights Reserved.
#
# This software is subject to the provisions of the Zope Public License,
# Version 2.1 (ZPL).  A copy of the ZPL should accompany this distribution.
# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
# FOR A PARTICULAR PURPOSE.
#
##############################################################################
"""
Compute a resolution order for an object and its bases.

.. versionchanged:: 5.0
   The resolution order is now based on the same C3 order that Python
   uses for classes. In complex instances of multiple inheritance, this
   may result in a different ordering.

   In older versions, the ordering wasn't required to be C3 compliant,
   and for backwards compatibility, it still isn't. If the ordering
   isn't C3 compliant (if it is *inconsistent*), zope.interface will
   make a best guess to try to produce a reasonable resolution order.
   Still (just as before), the results in such cases may be
   surprising.

.. rubric:: Environment Variables

Due to the change in 5.0, certain environment variables can be used to control errors
and warnings about inconsistent resolution orders. They are listed in priority order, with
variables at the bottom generally overriding variables above them.

ZOPE_INTERFACE_WARN_BAD_IRO
    If this is set to "1", then if there is at least one inconsistent resolution
    order discovered, a warning (:class:`InconsistentResolutionOrderWarning`) will
    be issued. Use the usual warning mechanisms to control this behaviour. The warning
    text will contain additional information on debugging.
ZOPE_INTERFACE_TRACK_BAD_IRO
    If this is set to "1", then zope.interface will log information about each
    inconsistent resolution order discovered, and keep those details in memory in this module
    for later inspection.
ZOPE_INTERFACE_STRICT_IRO
    If this is set to "1", any attempt to use :func:`ro` that would produce a non-C3
    ordering will fail by raising :class:`InconsistentResolutionOrderError`.

There are two environment variables that are independent.

ZOPE_INTERFACE_LOG_CHANGED_IRO
    If this is set to "1", then if the C3 resolution order is different from
    the legacy resolution order for any given object, a message explaining the differences
    will be logged. This is intended to be used for debugging complicated IROs.
ZOPE_INTERFACE_USE_LEGACY_IRO
    If this is set to "1", then the C3 resolution order will *not* be used. The
    legacy IRO will be used instead. This is a temporary measure and will be removed in the
    future. It is intended to help during the transition.
    It implies ``ZOPE_INTERFACE_LOG_CHANGED_IRO``.
"""
from __future__ import print_function
__docformat__ = 'restructuredtext'

__all__ = [
    'ro',
    'InconsistentResolutionOrderError',
    'InconsistentResolutionOrderWarning',
]

__logger = None

def _logger():
    global __logger # pylint:disable=global-statement
    if __logger is None:
        import logging
        __logger = logging.getLogger(__name__)
    return __logger

def _legacy_mergeOrderings(orderings):
    """Merge multiple orderings so that within-ordering order is preserved

    Orderings are constrained in such a way that if an object appears
    in two or more orderings, then the suffix that begins with the
    object must be in both orderings.

    For example:

    >>> _mergeOrderings([
    ... ['x', 'y', 'z'],
    ... ['q', 'z'],
    ... [1, 3, 5],
    ... ['z']
    ... ])
    ['x', 'y', 'q', 1, 3, 5, 'z']

    """

    seen = set()
    result = []
    for ordering in reversed(orderings):
        for o in reversed(ordering):
            if o not in seen:
                seen.add(o)
                result.insert(0, o)

    return result

def _legacy_flatten(begin):
    result = [begin]
    i = 0
    for ob in iter(result):
        i += 1
        # The recursive calls can be avoided by inserting the base classes
        # into the dynamically growing list directly after the currently
        # considered object;  the iterator makes sure this will keep working
        # in the future, since it cannot rely on the length of the list
        # by definition.
        result[i:i] = ob.__bases__
    return result

def _legacy_ro(ob):
    return _legacy_mergeOrderings([_legacy_flatten(ob)])

###
# Compare base objects using identity, not equality. This matches what
# the CPython MRO algorithm does, and is *much* faster to boot: that,
# plus some other small tweaks makes the difference between 25s and 6s
# in loading 446 plone/zope interface.py modules (1925 InterfaceClass,
# 1200 Implements, 1100 ClassProvides objects)
###


class InconsistentResolutionOrderWarning(PendingDeprecationWarning):
    """
    The warning issued when an invalid IRO is requested.
    """

class InconsistentResolutionOrderError(TypeError):
    """
    The error raised when an invalid IRO is requested in strict mode.
    """

    def __init__(self, c3, base_tree_remaining):
        self.C = c3.leaf
        base_tree = c3.base_tree
        self.base_ros = {
            base: base_tree[i + 1]
            for i, base in enumerate(self.C.__bases__)
        }
        # Unfortunately, this doesn't necessarily directly match
        # up to any transformation on C.__bases__, because
        # if any were fully used up, they were removed already.
        self.base_tree_remaining = base_tree_remaining

        TypeError.__init__(self)

    def __str__(self):
        import pprint
        return "%s: For object %r.\nBase ROs:\n%s\nConflict Location:\n%s" % (
            self.__class__.__name__,
            self.C,
            pprint.pformat(self.base_ros),
            pprint.pformat(self.base_tree_remaining),
        )


class _NamedBool(int): # cannot actually inherit bool

    def __new__(cls, val, name):
        inst = super(cls, _NamedBool).__new__(cls, val)
        inst.__name__ = name
        return inst


class _ClassBoolFromEnv(object):
    """
    Non-data descriptor that reads a transformed environment variable
    as a boolean, and caches the result in the class.
    """

    def __get__(self, inst, klass):
        import os
        for cls in klass.__mro__:
            my_name = None
            for k in dir(klass):
                if k in cls.__dict__ and cls.__dict__[k] is self:
                    my_name = k
                    break
            if my_name is not None:
                break
        else: # pragma: no cover
            raise RuntimeError("Unable to find self")

        env_name = 'ZOPE_INTERFACE_' + my_name
        val = os.environ.get(env_name, '') == '1'
        val = _NamedBool(val, my_name)
        setattr(klass, my_name, val)
        setattr(klass, 'ORIG_' + my_name, self)
        return val


class _StaticMRO(object):
    # A previously resolved MRO, supplied by the caller.
    # Used in place of calculating it.

    had_inconsistency = None # We don't know...

    def __init__(self, C, mro):
        self.leaf = C
        self.__mro = tuple(mro)

    def mro(self):
        return list(self.__mro)


class C3(object):
    # Holds the shared state during computation of an MRO.

    @staticmethod
    def resolver(C, strict, base_mros):
        strict = strict if strict is not None else C3.STRICT_IRO
        factory = C3
        if strict:
            factory = _StrictC3
        elif C3.TRACK_BAD_IRO:
            factory = _TrackingC3

        memo = {}
        base_mros = base_mros or {}
        for base, mro in base_mros.items():
            assert base in C.__bases__
            memo[base] = _StaticMRO(base, mro)

        return factory(C, memo)

    __mro = None
    __legacy_ro = None
    direct_inconsistency = False

    def __init__(self, C, memo):
        self.leaf = C
        self.memo = memo
        kind = self.__class__

        base_resolvers = []
        for base in C.__bases__:
            if base not in memo:
                resolver = kind(base, memo)
                memo[base] = resolver
            base_resolvers.append(memo[base])

        self.base_tree = [
            [C]
        ] + [
            memo[base].mro() for base in C.__bases__
        ] + [
            list(C.__bases__)
        ]

        self.bases_had_inconsistency = any(base.had_inconsistency for base in base_resolvers)

        if len(C.__bases__) == 1:
            self.__mro = [C] + memo[C.__bases__[0]].mro()

    @property
    def had_inconsistency(self):
        return self.direct_inconsistency or self.bases_had_inconsistency

    @property
    def legacy_ro(self):
        if self.__legacy_ro is None:
            self.__legacy_ro = tuple(_legacy_ro(self.leaf))
        return list(self.__legacy_ro)

    TRACK_BAD_IRO = _ClassBoolFromEnv()
    STRICT_IRO = _ClassBoolFromEnv()
    WARN_BAD_IRO = _ClassBoolFromEnv()
    LOG_CHANGED_IRO = _ClassBoolFromEnv()
    USE_LEGACY_IRO = _ClassBoolFromEnv()
    BAD_IROS = ()

    def _warn_iro(self):
        if not self.WARN_BAD_IRO:
            # For the initial release, one must opt-in to see the warning.
            # In the future (2021?) seeing at least the first warning will
            # be the default
            return
        import warnings
        warnings.warn(
            "An inconsistent resolution order is being requested. "
            "(Interfaces should follow the Python class rules known as C3.) "
            "For backwards compatibility, zope.interface will allow this, "
            "making the best guess it can to produce as meaningful an order as possible. "
            "In the future this might be an error. Set the warning filter to error, or set "
            "the environment variable 'ZOPE_INTERFACE_TRACK_BAD_IRO' to '1' and examine "
            "ro.C3.BAD_IROS to debug, or set 'ZOPE_INTERFACE_STRICT_IRO' to raise exceptions.",
            InconsistentResolutionOrderWarning,
        )

    @staticmethod
    def _can_choose_base(base, base_tree_remaining):
        # From C3:
        # nothead = [s for s in nonemptyseqs if cand in s[1:]]
        for bases in base_tree_remaining:
            if not bases or bases[0] is base:
                continue

            for b in bases:
                if b is base:
                    return False
        return True

    @staticmethod
    def _nonempty_bases_ignoring(base_tree, ignoring):
        return list(filter(None, [
            [b for b in bases if b is not ignoring]
            for bases
            in base_tree
        ]))

    def _choose_next_base(self, base_tree_remaining):
        """
        Return the next base.

        The return value will either fit the C3 constraints or be our best
        guess about what to do. If we cannot guess, this may raise an exception.
        """
        base = self._find_next_C3_base(base_tree_remaining)
        if base is not None:
            return base
        return self._guess_next_base(base_tree_remaining)

    def _find_next_C3_base(self, base_tree_remaining):
        """
        Return the next base that fits the constraints, or ``None`` if there isn't one.
        """
        for bases in base_tree_remaining:
            base = bases[0]
            if self._can_choose_base(base, base_tree_remaining):
                return base
        return None

    class _UseLegacyRO(Exception):
        pass

    def _guess_next_base(self, base_tree_remaining):