xref: /dports/devel/pytype/pytype-2021.9.9/pytype/abstract_utils.py

"""Utilities for abstract.py."""

import collections
import hashlib
import logging
from typing import Any, Collection, Dict, Iterable, Mapping, Optional, Sequence, Tuple, Union

from pytype import datatypes
from pytype import utils
from pytype.pyc import opcodes
from pytype.pyc import pyc
from pytype.pytd import mro
from pytype.typegraph import cfg
from pytype.typegraph import cfg_utils

log = logging.getLogger(__name__)

# We can't import abstract here due to a circular dep.
_BaseValue = Any  # abstract.BaseValue
_TypeParameter = Any  # abstract.TypeParameter

# Type parameter names matching the ones in builtins.pytd and typing.pytd.
T = "_T"
T2 = "_T2"
K = "_K"
V = "_V"
ARGS = "_ARGS"
RET = "_RET"

# TODO(rechen): Stop supporting all variants except _HAS_DYNAMIC_ATTRIBUTES.
DYNAMIC_ATTRIBUTE_MARKERS = [
    "HAS_DYNAMIC_ATTRIBUTES",
    "_HAS_DYNAMIC_ATTRIBUTES",
    "has_dynamic_attributes",
]

# A dummy container object for use in instantiating type parameters.
# A container is needed to preserve type parameter names for error messages
# and for sub_(one_)annotation(s).
DUMMY_CONTAINER = object()

# Names defined on every module/class that should be ignored in most cases.
TOP_LEVEL_IGNORE = frozenset({
    "__builtins__",
    "__doc__",
    "__file__",
    "__future__",
    "__module__",
    "__name__",
    "__annotations__",
    "google_type_annotations",
})
CLASS_LEVEL_IGNORE = frozenset({
    "__builtins__",
    "__class__",
    "__module__",
    "__name__",
    "__qualname__",
    "__slots__",
    "__annotations__",
})


class ConversionError(ValueError):
  pass


class EvaluationError(Exception):
  """Used to signal an errorlog error during type name evaluation."""

  @property
  def errors(self):
    return utils.message(self)

  @property
  def details(self):
    return "\n".join(error.message for error in self.errors)


class GenericTypeError(Exception):
  """The error for user-defined generic types."""

  def __init__(self, annot, error):
    super().__init__(annot, error)
    self.annot = annot
    self.error = error


class AsInstance:
  """Wrapper, used for marking things that we want to convert to an instance."""

  def __init__(self, cls):
    self.cls = cls


class AsReturnValue(AsInstance):
  """Specially mark return values, to handle NoReturn properly."""


# For lazy evaluation of ParameterizedClass.formal_type_parameters
LazyFormalTypeParameters = collections.namedtuple(
    "LazyFormalTypeParameters", ("template", "parameters", "subst"))


# Sentinel for get_atomic_value
class _None:
  pass


def get_atomic_value(variable, constant_type=None, default=_None()):
  """Get the atomic value stored in this variable."""
  if len(variable.bindings) == 1:
    v, = variable.bindings
    if isinstance(v.data, constant_type or object):
      return v.data  # success
  if not isinstance(default, _None):
    # If a default is specified, we return it instead of failing.
    return default
  # Determine an appropriate failure message.
  if not variable.bindings:
    raise ConversionError("Cannot get atomic value from empty variable.")
  bindings = variable.bindings
  name = bindings[0].data.vm.convert.constant_name(constant_type)
  raise ConversionError(
      "Cannot get atomic value %s from variable. %s %s"
      % (name, variable, [b.data for b in bindings]))


def get_atomic_python_constant(variable, constant_type=None):
  """Get the concrete atomic Python value stored in this variable.

  This is used for things that are stored in cfg.Variable, but we
  need the actual data in order to proceed. E.g. function / class definitions.

  Args:
    variable: A cfg.Variable. It can only have one possible value.
    constant_type: Optionally, the required type of the constant.
  Returns:
    A Python constant. (Typically, a string, a tuple, or a code object.)
  Raises:
    ConversionError: If the value in this Variable is purely abstract, i.e.
      doesn't store a Python value, or if it has more than one possible value.
  """
  atomic = get_atomic_value(variable)
  return atomic.vm.convert.value_to_constant(atomic, constant_type)


def get_views(variables, node):
  """Get all possible views of the given variables at a particular node.

  For performance reasons, this method uses node.CanHaveCombination for
  filtering. For a more precise check, you can call
  node.HasCombination(list(view.values())). Do so judiciously, as the latter
  method can be very slow.

  This function can be used either as a regular generator or in an optimized way
  to yield only functionally unique views:
    views = get_views(...)
    skip_future = None
    while True:
      try:
        view = views.send(skip_future)
      except StopIteration:
        break
      ...
    The caller should set `skip_future` to True when it is safe to skip
    equivalent future views and False otherwise.

  Args:
    variables: The variables.
    node: The node.

  Yields:
    A datatypes.AcessTrackingDict mapping variables to bindings.
  """
  try:
    combinations = cfg_utils.deep_variable_product(variables)
  except cfg_utils.TooComplexError:
    combinations = ((var.AddBinding(node.program.default_data, [], node)
                     for var in variables),)
  seen = []  # the accessed subsets of previously seen views
  for combination in combinations:
    view = {value.variable: value for value in combination}
    if any(subset <= view.items() for subset in seen):
      # Optimization: This view can be skipped because it matches the accessed
      # subset of a previous one.
      log.info("Skipping view (already seen): %r", view)
      continue
    combination = list(view.values())
    if not node.CanHaveCombination(combination):
      log.info("Skipping combination (unreachable): %r", combination)
      continue
    view = datatypes.AccessTrackingDict(view)
    skip_future = yield view
    if skip_future:
      # Skip future views matching this accessed subset.
      seen.append(view.accessed_subset.items())


def get_signatures(func):
  """Gets the given function's signatures."""
  if func.isinstance_PyTDFunction():
    return [sig.signature for sig in func.signatures]
  elif func.isinstance_InterpreterFunction():
    return [f.signature for f in func.signature_functions()]
  elif func.isinstance_BoundFunction():
    sigs = get_signatures(func.underlying)
    return [sig.drop_first_parameter() for sig in sigs]  # drop "self"
  elif func.isinstance_ClassMethod() or func.isinstance_StaticMethod():
    return get_signatures(func.method)
  elif func.isinstance_SimpleFunction():
    return [func.signature]
  else:
    raise NotImplementedError(func.__class__.__name__)


def func_name_is_class_init(name):
  """Return True if |name| is that of a class' __init__ method."""
  # Python 3's MAKE_FUNCTION byte code takes an explicit fully qualified
  # function name as an argument and that is used for the function name.
  # On the other hand, Python 2's MAKE_FUNCTION does not take any name
  # argument so we pick the name from the code object. This name is not
  # fully qualified. Hence, constructor names in Python 3 are fully
  # qualified ending in '.__init__', and constructor names in Python 2
  # are all '__init__'. So, we identify a constructor by matching its
  # name with one of these patterns.
  return name == "__init__" or name.endswith(".__init__")


def equivalent_to(binding, cls):
  """Whether binding.data is equivalent to cls, modulo parameterization."""
  return (binding.data.isinstance_Class() and
          binding.data.full_name == cls.full_name)


def apply_mutations(node, get_mutations):
  """Apply mutations yielded from a get_mutations function."""
  log.info("Applying mutations")
  num_mutations = 0
  for obj, name, value in get_mutations():
    if not num_mutations:
      # mutations warrant creating a new CFG node
      node = node.ConnectNew(node.name)
    num_mutations += 1
    obj.merge_instance_type_parameter(node, name, value)
  log.info("Applied %d mutations", num_mutations)
  return node


def get_template(val):
  """Get the value's class template."""
  if val.isinstance_Class():
    res = {t.full_name for t in val.template}
    if val.isinstance_ParameterizedClass():
      res.update(get_template(val.base_cls))
    elif val.isinstance_PyTDClass() or val.isinstance_InterpreterClass():
      for base in val.bases():
        base = get_atomic_value(base, default=val.vm.convert.unsolvable)
        res.update(get_template(base))
    return res
  elif val.cls:
    return get_template(val.cls)
  else:
    return set()


def get_mro_bases(bases, vm):
  """Get bases for MRO computation."""
  mro_bases = []
  has_user_generic = False
  for base_var in bases:
    if not base_var.data:
      continue
    # A base class is a Variable. If it has multiple options, we would
    # technically get different MROs. But since ambiguous base classes are rare
    # enough, we instead just pick one arbitrary option per base class.
    base = get_atomic_value(base_var, default=vm.convert.unsolvable)
    mro_bases.append(base)
    # check if it contains user-defined generic types
    if (base.isinstance_ParameterizedClass() and
        base.full_name != "typing.Generic"):
      has_user_generic = True
  # if user-defined generic type exists, we won't add `typing.Generic` to
  # the final result list
  if has_user_generic:
    return [b for b in mro_bases if b.full_name != "typing.Generic"]
  else:
    return mro_bases


def _merge_type(t0, t1, name, cls):
  """Merge two types.

  Rules: Type `Any` can match any type, we will return the other type if one
  of them is `Any`. Return the sub-class if the types have inheritance
  relationship.

  Args:
    t0: The first type.
    t1: The second type.
    name: Type parameter name.
    cls: The class_mixin.Class on which any error should be reported.
  Returns:
    A type.
  Raises:
    GenericTypeError: if the types don't match.
  """
  if t0 is None or t0.isinstance_Unsolvable():
    return t1
  if t1 is None or t1.isinstance_Unsolvable():
    return t0
  # t0 is parent of t1
  if t0 in t1.mro:
    return t1
  # t1 is parent of t0
  if t1 in t0.mro:
    return t0
  raise GenericTypeError(cls, "Conflicting value for TypeVar %s" % name)


def parse_formal_type_parameters(
    base, prefix, formal_type_parameters, container=None):
  """Parse type parameters from base class.

  Args:
    base: base class.
    prefix: the full name of subclass of base class.
    formal_type_parameters: the mapping of type parameter name to its type.
    container: An abstract value whose class template is used when prefix=None
      to decide how to handle type parameters that are aliased to other type
      parameters. Values that are in the class template are kept, while all
      others are ignored.

  Raises:
    GenericTypeError: If the lazy types of type parameter don't match
  """
  def merge(t0, t1, name):
    return _merge_type(t0, t1, name, base)

  if base.isinstance_ParameterizedClass():
    if base.full_name == "typing.Generic":
      return
    if (base.base_cls.isinstance_InterpreterClass() or
        base.base_cls.isinstance_PyTDClass()):
      # merge the type parameters info from base class
      formal_type_parameters.merge_from(
          base.base_cls.all_formal_type_parameters, merge)
    params = base.get_formal_type_parameters()
    if getattr(container, "cls", None):
      container_template = container.cls.template
    else:
      container_template = ()
    for name, param in params.items():
      if param.isinstance_TypeParameter():
        # We have type parameter renaming, e.g.,
        #  class List(Generic[T]): pass
        #  class Foo(List[U]): pass
        if prefix:
          formal_type_parameters.add_alias(
              name, prefix + "." + param.name, merge)
        elif param in container_template:
          formal_type_parameters[name] = param
      else:
        # We have either a non-formal parameter, e.g.,
        # class Foo(List[int]), or a non-1:1 parameter mapping, e.g.,
        # class Foo(List[K or V]). Initialize the corresponding instance
        # parameter appropriately.
        if name not in formal_type_parameters:
          formal_type_parameters[name] = param
        else:
          # Two unrelated containers happen to use the same type
          # parameter but with different types.
          last_type = formal_type_parameters[name]
          formal_type_parameters[name] = merge(last_type, param, name)
  else:
    if base.isinstance_InterpreterClass() or base.isinstance_PyTDClass():
      # merge the type parameters info from base class
      formal_type_parameters.merge_from(
          base.all_formal_type_parameters, merge)
    if base.template:
      # handle unbound type parameters
      for item in base.template:
        if item.isinstance_TypeParameter():
          # This type parameter will be set as `ANY`.
          name = full_type_name(base, item.name)
          if name not in formal_type_parameters:
            formal_type_parameters[name] = None


def full_type_name(val, name):
  """Compute complete type parameter name with scope.

  Args:
    val: The object with type parameters.
    name: The short type parameter name (e.g., T).

  Returns:
    The full type parameter name (e.g., List.T).
  """
  if val.isinstance_Instance():
    return full_type_name(val.cls, name)
  # The type is in current `class`
  for t in val.template:
    if t.name == name:
      return val.full_name + "." + name
    elif t.full_name == name:
      return t.full_name
  # The type is instantiated in `base class`
  for t in val.all_template_names:
    if t.split(".")[-1] == name or t == name:
      return t
  return name


def maybe_extract_tuple(t):
  """Returns a tuple of Variables."""
  values = t.data
  if len(values) > 1:
    return (t,)
  v, = values
  if not v.isinstance_Tuple():
    return (t,)
  return v.pyval


def compute_template(val):
  """Compute the precedence list of template parameters according to C3.

  1. For the base class list, if it contains `typing.Generic`, then all the
  type parameters should be provided. That means we don't need to parse extra
  base class and then we can get all the type parameters.
  2. If there is no `typing.Generic`, parse the precedence list according to
  C3 based on all the base classes.
  3. If `typing.Generic` exists, it must contain at least one type parameters.
  And there is at most one `typing.Generic` in the base classes. Report error
  if the check fails.

  Args:
    val: The abstract.BaseValue to compute a template for.

  Returns:
    parsed type parameters

  Raises:
    GenericTypeError: if the type annotation for generic type is incorrect
  """
  if val.isinstance_PyTDClass():
    return [val.vm.convert.constant_to_value(itm.type_param)
            for itm in val.pytd_cls.template]
  elif not val.isinstance_InterpreterClass():
    return ()
  bases = [get_atomic_value(base, default=val.vm.convert.unsolvable)
           for base in val.bases()]
  template = []

  # Compute the number of `typing.Generic` and collect the type parameters
  for base in bases:
    if base.full_name == "typing.Generic":
      if base.isinstance_PyTDClass():
        raise GenericTypeError(val, "Cannot inherit from plain Generic")
      if template:
        raise GenericTypeError(
            val, "Cannot inherit from Generic[...] multiple times")
      for item in base.template:
        param = base.formal_type_parameters.get(item.name)
        template.append(param.with_module(val.full_name))

  if template:
    # All type parameters in the base classes should appear in
    # `typing.Generic`
    for base in bases:
      if base.full_name != "typing.Generic":
        if base.isinstance_ParameterizedClass():
          for item in base.template:
            param = base.formal_type_parameters.get(item.name)
            if param.isinstance_TypeParameter():
              t = param.with_module(val.full_name)
              if t not in template:
                raise GenericTypeError(
                    val, "Generic should contain all the type variables")
  else:
    # Compute template parameters according to C3
    seqs = []
    for base in bases:
      if base.isinstance_ParameterizedClass():
        seq = []
        for item in base.template:
          param = base.formal_type_parameters.get(item.name)
          if param.isinstance_TypeParameter():
            seq.append(param.with_module(val.full_name))
        seqs.append(seq)
    try:
      template.extend(mro.MergeSequences(seqs))
    except ValueError as e:
      raise GenericTypeError(
          val, "Illegal type parameter order in class %s" % val.name) from e

  return template


def _hash_dict(vardict, names):
  """Hash a dictionary.

  This contains the keys and the full hashes of the data in the values.

  Arguments:
    vardict: A dictionary mapping str to Variable.
    names: If this is non-None, the snapshot will include only those
      dictionary entries whose keys appear in names.

  Returns:
    A hash of the dictionary.
  """
  if names is not None:
    vardict = {name: vardict[name] for name in names.intersection(vardict)}
  m = hashlib.md5()
  for name, var in sorted(vardict.items()):
    m.update(str(name).encode("utf-8"))
    for value in var.bindings:
      m.update(value.data.get_fullhash())
  return m.digest()


def hash_all_dicts(*hash_args):
  """Convenience method for hashing a sequence of dicts."""
  return hashlib.md5(b"".join(_hash_dict(*args) for args in hash_args)).digest()


def _matches_generator(type_obj, allowed_types):
  """Check if type_obj matches a Generator/AsyncGenerator type."""
  if type_obj.isinstance_Union():
    return all(_matches_generator(sub_type, allowed_types)
               for sub_type in type_obj.options)
  else:
    base_cls = type_obj
    if type_obj.isinstance_ParameterizedClass():
      base_cls = type_obj.base_cls
    return ((base_cls.isinstance_PyTDClass() and
             base_cls.name in allowed_types) or
            base_cls.isinstance_AMBIGUOUS_OR_EMPTY())


def matches_generator(type_obj):
  allowed_types = ("generator", "Iterable", "Iterator")
  return _matches_generator(type_obj, allowed_types)


def matches_async_generator(type_obj):
  allowed_types = ("asyncgenerator", "AsyncIterable", "AsyncIterator")
  return _matches_generator(type_obj, allowed_types)


def var_map(func, var):
  return (func(v) for v in var.data)


def eval_expr(vm, node, f_globals, f_locals, expr):
  """Evaluate an expression with the given node and globals."""
  # This is used to resolve type comments and late annotations.
  #
  # We don't chain node and f_globals as we want to remain in the context
  # where we've just finished evaluating the module. This would prevent
  # nasty things like:
  #
  # def f(a: "A = 1"):
  #   pass
  #
  # def g(b: "A"):
  #   pass
  #
  # Which should simply complain at both annotations that 'A' is not defined
  # in both function annotations. Chaining would cause 'b' in 'g' to yield a
  # different error message.
  log.info("Evaluating expr: %r", expr)

  # Any errors logged here will have a filename of None and a linenumber of 1
  # when what we really want is to allow the caller to handle/log the error
  # themselves.  Thus we checkpoint the errorlog and then restore and raise
  # an exception if anything was logged.
  with vm.errorlog.checkpoint() as record:
    try:
      code = vm.compile_src(expr, mode="eval")
    except pyc.CompileError as e:
      # We keep only the error message, since the filename and line number are
      # for a temporary file.
      vm.errorlog.python_compiler_error(None, 0, e.error)
      ret = vm.new_unsolvable(node)
    else:
      _, _, _, ret = vm.run_bytecode(node, code, f_globals, f_locals)
  log.info("Finished evaluating expr: %r", expr)
  if record.errors:
    # Annotations are constants, so tracebacks aren't needed.
    e = EvaluationError([error.drop_traceback() for error in record.errors])
  else:
    e = None
  return ret, e


def check_classes(var, check):
  """Check whether the cls of each value in `var` is a class and passes `check`.

  Args:
    var: A cfg.Variable or empty.
    check: (BaseValue) -> bool.

  Returns:
    Whether the check passes.
  """
  return var and all(
      v.cls.isinstance_Class() and check(v.cls) for v in var.data if v.cls)


def match_type_container(typ, container_type_name: Union[str, Tuple[str, ...]]):
  """Unpack the type parameter from ContainerType[T]."""
  if typ is None:
    return None
  if isinstance(container_type_name, str):
    container_type_name = (container_type_name,)
  if not (typ.isinstance_ParameterizedClass() and
          typ.full_name in container_type_name):
    return None
  param = typ.get_formal_type_parameter(T)
  return param


def get_annotations_dict(members):
  """Get __annotations__ from a members map.

  Returns None rather than {} if the dict does not exist so that callers always
  have a reference to the actual dictionary, and can mutate it if needed.

  Args:
    members: A dict of member name to variable

  Returns:
    members['__annotations__'] unpacked as a python dict, or None
  """
  if "__annotations__" not in members:
    return None
  annots_var = members["__annotations__"]
  try:
    annots = get_atomic_value(annots_var)
  except ConversionError:
    return None
  return annots if annots.isinstance_AnnotationsDict() else None


class Local:
  """A possibly annotated local variable."""

  def __init__(
      self,
      node,
      op: Optional[opcodes.Opcode],
      typ: Optional[_BaseValue],
      orig: Optional[cfg.Variable],
      vm):
    self._ops = [op]
    if typ:
      self.typ = vm.program.NewVariable([typ], [], node)
    else:
      # Creating too many variables bloats the typegraph, hurting performance,
      # so we use None instead of an empty variable.
      self.typ = None
    self.orig = orig
    self.vm = vm

  @property
  def stack(self):
    return self.vm.simple_stack(self._ops[-1])

  def update(self, node, op, typ, orig):
    """Update this variable's annotation and/or value."""
    if op in self._ops:
      return
    self._ops.append(op)
    if typ:
      if self.typ:
        self.typ.AddBinding(typ, [], node)
      else:
        self.typ = self.vm.program.NewVariable([typ], [], node)
    if orig:
      self.orig = orig

  def get_type(self, node, name):
    """Gets the variable's annotation."""
    if not self.typ:
      return None
    values = self.typ.Data(node)
    if len(values) > 1:
      self.vm.errorlog.ambiguous_annotation(self.stack, values, name)
      return self.vm.convert.unsolvable
    elif values:
      return values[0]
    else:
      return None


def is_literal(annot: Optional[_BaseValue]):
  if not annot:
    return False
  if annot.isinstance_Union():
    return all(is_literal(o) for o in annot.options)
  return annot.isinstance_LiteralClass()


def is_concrete_dict(val: _BaseValue):
  return val.isinstance_Dict() and not val.could_contain_anything


def is_concrete_list(val: _BaseValue):
  return val.isinstance_List() and not val.could_contain_anything


def is_concrete(val: _BaseValue):
  return (val.isinstance_PythonConstant() and
          not getattr(val, "could_contain_anything", False))


def is_indefinite_iterable(val: _BaseValue):
  """True if val is a non-concrete instance of typing.Iterable."""
  instance = val.isinstance_Instance()
  concrete = is_concrete(val)
  cls_instance = val.cls and val.cls.isinstance_Class()
  if not (instance and cls_instance and not concrete):
    return False
  for cls in val.cls.mro:
    if cls.full_name == "builtins.str":
      return False
    elif cls.full_name == "builtins.tuple":
      # A tuple's cls attribute may point to either PyTDClass(tuple) or
      # TupleClass; only the former is indefinite.
      return cls.isinstance_PyTDClass()
    elif cls.full_name == "typing.Iterable":
      return True
  return False


def is_var_indefinite_iterable(var):
  """True if all bindings of var are indefinite sequences."""
  return all(is_indefinite_iterable(x) for x in var.data)


def merged_type_parameter(node, var, param):
  if not var.bindings:
    return node.program.NewVariable()
  if is_var_splat(var):
    var = unwrap_splat(var)
  params = [v.get_instance_type_parameter(param) for v in var.data]
  return var.data[0].vm.join_variables(node, params)


def is_var_splat(var):
  if var.data and var.data[0].isinstance_Splat():
    # A splat should never have more than one binding, since we create and use
    # it immediately.
    assert len(var.bindings) == 1
    return True
  return False


def unwrap_splat(var):
  return var.data[0].iterable


def is_callable(value: _BaseValue):
  """Returns whether 'value' is a callable."""
  if (value.isinstance_Function() or
      value.isinstance_BoundFunction() or
      value.isinstance_ClassMethod() or
      value.isinstance_ClassMethodInstance() or
      value.isinstance_StaticMethod() or
      value.isinstance_StaticMethodInstance()):
    return True
  if not value.cls or not value.cls.isinstance_Class():
    return False
  _, attr = value.vm.attribute_handler.get_attribute(
      value.vm.root_node, value.cls, "__call__")
  return attr is not None


def expand_type_parameter_instances(bindings: Iterable[cfg.Binding]):
  bindings = list(bindings)
  while bindings:
    b = bindings.pop(0)
    if b.data.isinstance_TypeParameterInstance():
      param_value = b.data.instance.get_instance_type_parameter(b.data.name)
      if param_value.bindings:
        bindings = param_value.bindings + bindings
        continue
    yield b


def get_type_parameter_substitutions(
    val: _BaseValue, type_params: Iterable[_TypeParameter]
) -> Mapping[str, cfg.Variable]:
  """Get values for type_params from val's type parameters."""
  subst = {}
  for p in type_params:
    if val.isinstance_Class():
      param_value = val.get_formal_type_parameter(p.name).instantiate(
          val.vm.root_node)
    else:
      param_value = val.get_instance_type_parameter(p.name)
    subst[p.full_name] = param_value
  return subst


def build_generic_template(
    type_params: Sequence[_BaseValue], base_type: _BaseValue
) -> Tuple[Sequence[str], Sequence[_TypeParameter]]:
  """Build a typing.Generic template from a sequence of type parameters."""
  if not all(item.isinstance_TypeParameter() for item in type_params):
    base_type.vm.errorlog.invalid_annotation(
        base_type.vm.frames, base_type,
        "Parameters to Generic[...] must all be type variables")
    type_params = [item for item in type_params
                   if item.isinstance_TypeParameter()]

  template = [item.name for item in type_params]

  if len(set(template)) != len(template):
    base_type.vm.errorlog.invalid_annotation(
        base_type.vm.frames, base_type,
        "Parameters to Generic[...] must all be unique")

  return template, type_params


def is_generic_protocol(val: _BaseValue) -> bool:
  return (val.isinstance_ParameterizedClass() and
          val.full_name == "typing.Protocol")


def combine_substs(
    substs1: Optional[Collection[Dict[str, cfg.Variable]]],
    substs2: Optional[Collection[Dict[str, cfg.Variable]]]
) -> Collection[Dict[str, cfg.Variable]]:
  """Combines the two collections of type parameter substitutions."""
  if substs1 and substs2:
    return tuple({**sub1, **sub2} for sub1 in substs1 for sub2 in substs2)  # pylint: disable=g-complex-comprehension
  elif substs1:
    return substs1
  elif substs2:
    return substs2
  else:
    return ()


def _flatten(value, classes):
  """Flatten the contents of value into classes.

  If value is a Class, it is appended to classes.
  If value is a PythonConstant of type tuple, then each element of the tuple
  that has a single binding is also flattened.
  Any other type of value, or tuple elements that have multiple bindings are
  ignored.

  Args:
    value: An abstract value.
    classes: A list to be modified.

  Returns:
    True iff a value was ignored during flattening.
  """
  # Used by special_builtins.IsInstance and IsSubclass
  if value.isinstance_AnnotationClass():
    value = value.base_cls
  if value.isinstance_Class():
    # A single class, no ambiguity.
    classes.append(value)
    return False
  elif value.isinstance_Tuple():
    # A tuple, need to process each element.
    ambiguous = False
    for var in value.pyval:
      if (len(var.bindings) != 1 or
          _flatten(var.bindings[0].data, classes)):
        # There were either multiple bindings or ambiguity deeper in the
        # recursion.
        ambiguous = True
    return ambiguous
  else:
    return True


def check_against_mro(vm, target, class_spec):
  """Check if any of the classes are in the target's MRO.

  Args:
    vm: The virtual machine.
    target: A BaseValue whose MRO will be checked.
    class_spec: A Class or PythonConstant tuple of classes (i.e. the second
      argument to isinstance or issubclass).

  Returns:
    True if any class in classes is found in the target's MRO,
    False if no match is found and None if it's ambiguous.
  """
  # Determine the flattened list of classes to check.
  classes = []
  ambiguous = _flatten(class_spec, classes)

  for c in classes:
    if vm.matcher(None).match_from_mro(target, c, allow_compat_builtins=False):
      return True  # A definite match.
  # No matches, return result depends on whether flatten() was
  # ambiguous.
  return None if ambiguous else False