text: # Copyright 2017 Google Inc.
  #
  # Licensed under the Apache License, Version 2.0 (the "License");
  # you may not use this file except in compliance with the License.
  # You may obtain a copy of the License at
  #
  #      http://www.apache.org/licenses/LICENSE-2.0
  #
  # Unless required by applicable law or agreed to in writing, software
  # distributed under the License is distributed on an "AS IS" BASIS,
  # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  # See the License for the specific language governing permissions and
  # limitations under the License.
  
  """Convert "pyparsed" CLIF PYTD IR to CLIF AST proto.
  
  Use
    p = Postprocessor()
    p.Translate(file_object) to get CLIF AST proto generated from CLIF PYTD text.
  
  In case of errors it will raise an exception. Possible exceptions are:
    pyparsing.ParseFatalException - grammar error in input text
    NameError - wrong naming (usually duplicate names)
    SyntaxError - wrong construct or statement usage
  """
  
  from __future__ import print_function
  
  import codecs
  import contextlib
  import os
  import pickle
  import re
  import sys
  
  from clif.protos import ast_pb2
  from clif.python import ast_manipulations
  from clif.python import pytd_parser
  
  CLIF_USE = re.compile(r'// *CLIF:? +use'
                        r' +`(?P<cname>.+)` +as +(?P<pyname>[\w.]+)')
  CLIF_INIT = re.compile(r'// *CLIF:? +init_module +(?P<cpp_statement>.+)')
  CLIF_MACRO = re.compile(r'// *CLIF:? +macro +(?P<name>.+) +(?P<def>.+)$')
  CLIF_INCLUDE = re.compile(r'// *CLIF:? +include +"(?P<path>[^"]+)"')
  KEEP_GIL_DECORATOR = 'do_not_release_gil'
  
  
  def _read_include(input_stream, fname, prefix, typetable, capsules, interfaces,
                    extra_init):
    """Reads a C++ .h file generated by CLIF to check wrapper information."""
    for s in input_stream:
      use = CLIF_USE.match(s)
      if use:
        cname = use.group('cname')
        pyname = use.group('pyname')
        if pyname.endswith('.'):  # Like in a normal English sentence.
          pyname = pyname[:-1]
        if not (cname and pyname):
          raise SyntaxError('Invalid "use" pragma in "%s": %s' % (fname, s))
        pyname = prefix + pyname
        if pyname in capsules:
          raise NameError('C++ type "%s" already wrapped as capsule by name %s'
                          % (cname, pyname))
        if typetable.has_type(pyname) and cname.endswith('*'):
          raise NameError('C++ type "%s" already wrapped by name %s'
                          % (cname, pyname))
  
        existing_pyname = typetable.find_pyname_for_cpp_type(cname)
        if existing_pyname:
          raise NameError('C++ type {!r} already wrapped by name {!r}'.format(
              cname, existing_pyname))
        if cname.endswith('*'):
          capsules[pyname] = cname
        else:
          typetable.add_type(pyname, cname)
        continue
      init = CLIF_INIT.match(s)
      if init:
        extra_init.append(init.group('cpp_statement'))
        continue
      include = CLIF_INCLUDE.match(s)
      if include:
        yield include.group('path')
        continue
      macro = CLIF_MACRO.match(s)
      if macro:
        name = macro.group('name')
        s = macro.group('def').replace(r'\n', '\n').encode('utf-8')
        try:
          sysver, ppver, src = pickle.loads(s)
        except Exception:  # pylint: disable=broad-except
          raise ImportError('Macro %s loading error' % name)
        if sysver != sys.hexversion or ppver != pytd_parser.version:
          raise ValueError('Interface name "%s" from file %s is from '
                           'incompatible version (%s, %s)'
                           % (name, fname, sysver, ppver))
        if name in interfaces:
          raise NameError('Interface name "%s" from file %s already used'
                          % (name, fname))
        interfaces[name] = src + (False,)
        continue
  
  
  class Postprocessor(object):
    """Process parsed IR."""
  
    def __init__(self, config_headers=None, include_paths=('.',), preamble='',
                 py3output=True):
      self._names = {}  # Keep name->FQN for all 'from path import' statements.
      self._capsules = {}   # Keep raw pointer names (pytype -> cpptype).
      self._typenames = {}  # Keep typedef aliases (pytype -> type_ir).
      self._typetable = _TypeTable()
      self._macros = {}  # Keep interfaces (name -> (num_args, subtree, local)).
      self._scan_includes = config_headers or []
      self._include_paths = include_paths
      self._preamble = preamble
      self.source = None
      # _macro_values [actual, param, values] only set in _class that
      # has implements MACRO<actual, param, values>.
      self._macro_values = []
      self._py3output = py3output
  
    def is_pyname_known(self, name):
      return (name in self._capsules or
              self._typetable.has_type(name) or
              name in self._typenames)
  
    def check_known_name(self, name, allowed=None):
      """Check that a type name is not defined or defined with the given value.
  
      Args:
        name: str, the name of the type in the type table.
        allowed: optional str, if a type is already defined in the
          typetable, then the existing C++ type for `name` must match this
          value. This only applies if `name` already exists.
  
      Raises:
        NameError: if the name is not defined, or if it is defined but doesn't
          match the allowed value.
      """
      if name in self._capsules:
        raise NameError('Name "%s" already defined as capsule name.' % name)
  
      if self._typetable.has_type(name):
        if not allowed:
          raise NameError(
              'Name %r already defined as type %r, but it was expected to '
              'be undefined' % (name, self._typetable.get_last_cpp_type(name)))
        elif self._typetable.get_last_cpp_type(name) != allowed:
          raise NameError(
              'Name %r already defined as type %r, but %r was expected' %
              (name, self._typetable.get_last_cpp_type(name), allowed))
  
      if name in self._typenames:
        raise NameError('Name "%s" already defined as type alias.' % name)
      if name in self._macros:
        raise NameError('Name "%s" already defined as interface name.' % name)
  
    def Translate(self, pytd_file):  # pylint: disable=invalid-name
      """Given an open .pytd file, return a CLIF AST ast_pb2.AST protobuffer."""
      pb = ast_pb2.AST()
      pb.source = pytd_file.name
      for hdr in self._scan_includes:
        pb.usertype_includes.append(hdr)
        self._include(0, [hdr], pb, scan_only=True)
      self._parse_preamble(pb)
  
      self._parse_pytd(pytd_file, pb)
  
      # Since most C++ calls release GIL we need threads.
      pb.extra_init.append('PyEval_InitThreads();')
      # Assumed we always want a deterministic output proto. Since dict/set order
      # is not, do sorted() order traversal.
      order = sorted
      for name, fq_name in order(self._names.items()):
        nm = pb.namemaps.add()
        nm.name = name
        nm.fq_name = fq_name
      for pytype, cpp_types  in order(self._typetable.iter_types()):
        tm = pb.typemaps.add()
        tm.lang_type = pytype
        for cpp_type in order(set(cpp_types)):
          tm.cpp_type.append(cpp_type)
      for t in order(self._capsules):
        tm = pb.typemaps.add()
        tm.lang_type = t
        tm.cpp_type.append(self._capsules[t])
      for name, (nargs, src, local) in order(self._macros.items()):
        if local:
          m = pb.macros.add()
          m.name = name
          # Use protocol 0 to keep version independence.
          m.definition = pickle.dumps(
              (sys.hexversion, pytd_parser.version, (nargs, src)), 0)
      ast_manipulations.MoveExtendsOutOfClassesInPlace(pb)
      return pb
  
    def _parse_preamble(self, pb):
      if self._preamble:
        source = self._preamble
        self._parse_pytd_ast(source, self._ast_from_text(source), pb)
  
    def _parse_pytd(self, fp, pb):
      """Parse a pytd input file.
  
      Args:
        fp: an open file for reading.
        pb: output proto to parse into.
      """
      source = fp.read()
      ast = self._ast_from_text(source)
      self._gather_types(ast)  # For forward references.
      self._parse_pytd_ast(source, ast, pb)
  
    def _parse_pytd_ast(self, source, ast, pb):
      self.source = source  # Save for line number calculation.
      for ir in ast:
        if ir:
          # IR is specific to the parser.
          # IR[0] is a statement name.
          getattr(self, '_'+ir[0])(self.line(ir[1]), ir[2:], pb)
      self.source = None
  
    def line(self, loc):
      return pytd_parser.LineNum(loc, self.source)
  
    def _ast_from_text(self, text):
      return pytd_parser.Clif.parseString(text, parseAll=True)
  
    def _gather_types(self, ast):
      """Populate typetable with fully qualified type names."""
      for ir in ast:
        if ir:
          self._gather_dispatch(ir)
  
    def _gather_dispatch(self, ast, **kwargs):
      """Given an AST node, dispatch to the appropriate handler function.
  
      Args:
        ast: pyparsing.ParseResults
        **kwargs: Additional keyword args to pass onto the dispatched-to function.
      """
      ast_type = ast[0]
      # We only visit constructs that might contribute type information
      if ast_type not in ('from', 'namespace', 'class'):
        return
      func_name = '_gather_{}'.format(ast_type)
      func = getattr(self, func_name, None)
      assert func, 'No gather_types function for AST node type {!r}'.format(
          ast_type)
      func(ast, **kwargs)  # pylint: disable=not-callable
  
    def _gather_from(self, ast):
      """Visit a from-header ast node to gather types."""
      for child in ast[3]:
        self._gather_dispatch(child)
  
    def _gather_class(self, ast, namespace=None):
      """Visit a class declaration to gather type declarations.
  
      Args:
        ast: pyparsing.ParseResults
        namespace: Optional[str], the cpp namespace the class is within; this
          is only used by top-level class definitions.
      """
      # The ast name is either:
      # * 1 element: [Foo] from "class Foo"
      # * 2 elements: [CppName, PyName] from "class `CppName` as PyName
      if len(ast.name) not in (1, 2):
        raise ValueError(
            'Class name ast node must be length 1 or 2, got {!r}'.format(
                list(ast.name)))
  
      if namespace:
        cpp_name = '{}::{}'.format(namespace, ast.name[0])
      else:
        cpp_name = ast.name[0]
  
      pyname = ast.name[-1]
      self._typetable.set_type(pyname, cpp_name)
  
      with self._typetable.scope(pyname):
        children = ast[-1]
        for child in children:
          self._gather_dispatch(
              child,
              # Explicitly clear namespace to prevent the namespace from being
              # redundantly and errorneously prepended to nested types. This
              # also mimics the normal parsing behavior.
              namespace=None)
  
    def _gather_namespace(self, ast):
      """Visit a namespace node for gathering types."""
      namespace = ast[2]
      children = ast[3]
      for child in children:
        self._gather_dispatch(child, namespace=namespace)
  
    # statement
    #
    # Args:
    #   ln: line number in the .clif file
    #   p: IR subtree (with statement keyword removed)
    #   pb: AST proto for this statement to fill
  
    def _interface(self, ln, p, unused_pb=None):
      """'Macro definition' stores a subtree with var placeholders (%0, %1...)."""
      assert len(p) > 2, p
      nargs = len(p) - 2  # 0-name, -1-block, [1:-1]-args
      name = p[0]
      self.check_known_name(name)
      args = {name: pos for pos, name in enumerate(p[:-1])}
      if len(args) != nargs+1:
        raise NameError('all interface args must be different '
                        'at line %d, got %s<%s>' % (ln, name, ', '.join(p[1:-1])))
      src = p[-1]
      if nargs:
        for ast in src:
          if ast[0] == 'func':
            for p in ast.params:
              _subst_type_formal(p, args)
            for p in ast.returns:
              _subst_type_formal(p, args)
          elif ast[0] == 'var':
            _subst_type_formal(ast, args)
          else:
            raise NameError('Only def and var allowed in interface,'
                            ' found "%s" at line %d' % (ast[0], ln))
      self._macros[name] = nargs, src, True
  
    def _from(self, unused_ln, p, pb):
      """from "full/project/path/cheader.h": BLOCK."""
      assert len(p) == 2, str(p)
      hdr = p[0]
      for s in p[1]:
        if s[0] == 'namespace':
          self._namespace(None, s, pb, hdr)
        elif s[0] == 'staticmethods':
          self._staticmethods(None, s, pb, hdr)
        elif s[0] != 'pass':
          decl = pb.decls.add()
          decl.cpp_file = hdr
          getattr(self, '_'+s[0])(self.line(s[1]), s, decl)
  
    def _namespace(self, unused_ln, p, pb, hdr):
      """namespace `x::y::z` processing."""
      assert len(p) == 4, str(p)
      ns = 'clif' if p[2] == 'std' else p[2]
      for s in p[-1]:
        if s[0] == 'interface':
          self._interface(self.line(s[1]), s[2:])
        elif s[0] == 'staticmethods':
          self._staticmethods(self.line(s[1]), s, pb, hdr, ns=ns)
        else:
          decl = pb.decls.add()
          decl.cpp_file = hdr
          decl.namespace_ = ns
          getattr(self, '_'+s[0])(self.line(s[1]), s, decl, ns=ns)
  
    def _staticmethods(self, ln, p, pb, hdr, ns=''):
      """staticmethods from `SomeType` processing."""
      assert len(p) == 4, str(p)
      assert hdr
      if ns and p[2].startswith(':'):
        raise NameError('Invalid reference to global class %s inside namespace %s'
                        ' at line %d' % (p[2], ns, ln))
      cns = ns +  '::' + p[2]
      for s in p[-1]:
        decl = pb.decls.add()
        decl.cpp_file = hdr
        if ns:
          decl.namespace_ = ns
        getattr(self, '_'+s[0])(self.line(s[1]), s, decl, ns=cns)
  
    def _include(self, unused_ln, p, pb, scan_only=False):
      """from "full/project/path/cheader.h" import *."""
      assert len(p) in (1, 2), p
      hdr = p[0]
      if not scan_only:
        pb.usertype_includes.append(hdr)
      # Scan hdr for new types
      namespace = p[1]+'.' if len(p) > 1 else ''
      for root in self._include_paths:
        try:
          with codecs.open(os.path.join(root, hdr),
                           encoding='utf-8') as include_file:
            pb.usertype_includes.extend(
                _read_include(include_file, hdr, namespace,
                              self._typetable, self._capsules, self._macros,
                              pb.extra_init))
          break
        except IOError:
          pass
      else:
        # Helpful pointer related to "_clif" infix change, added 2020-06-23.
        # TODO: Remove this code after a few weeks.
        if hdr.endswith('_clif.h') or hdr.endswith('_pyclif.h'):
          go_link = ''
        else:
          go_link = ' (maybe related to >>> go/clif_h_infix <<< change?)'
        raise NameError('include "%s" not found%s' % (hdr, go_link))
  
    def _import(self, unused_ln, p, unused_pb):
      """from full.python.path import postprocessor."""
      assert len(p) == 2, str(p)
      n = p[1]
      if n in self._names:
        raise NameError('Name %r already defined' % n)
      self._names[n] = '.'.join(p)
  
    def _type(self, unused_ln, p, pb):
      """type T = [`postconversion` as] pytype."""
      # typedef alias name(p[0]) = type(p[1])
      assert len(p) == 2, p.dump()
      if p[0] in self._typenames:
        raise NameError('Type %r already defined' % p[0])
      pytype = p[1].name[-1]
      if not self._typetable.has_type(pytype):
        raise NameError('Type %r not defined' % pytype)
      self._typenames[p[0]] = p[1]
      if len(p[1].name) > 1:
        # Save postconversion.
        tm = pb.typemaps.add()
        tm.lang_type = p[0]
        tm.postconversion = p[1].name[0]
  
    def _use(self, ln, p, unused_pb):
      """use `ctype` as pytype."""
      assert len(p) == 2, p.dump()
      if p[0].endswith('*'):
        raise NameError('Wrap type %s before use' % p[0][:-1])
      if not self.is_pyname_known(p[1]):
        raise NameError('Type %s should be defined before use at line %s'
                        % (p[1], ln))
      self._typetable.add_type(p[1], p[0])
  
    # decl
  
    def _capsule(self, ln, ast, pb, ns=None):
      assert isinstance(pb, ast_pb2.Decl), repr(pb)
      assert len(ast) == 3, ast.dump()
      pb.line_number = ln
      pb.decltype = pb.TYPE
      p = pb.fdecl
      _set_name(p.name, ast.name, ns)
      self.check_known_name(p.name.native)
      self._capsules[p.name.native] = p.name.cpp_name + ' *'
      return p.name.native
  
    def _extract_template_base_name(self, cpp_class_name):
      """Extracts the template name when the class is a renamed C++ template.
  
      We only want to check for `::` in the class/template name but not in the
      template parameters:
      - "class `Foo<namespace::Type>` as PyFoo" is valid,
      - "class `namespace::Foo` as PyFoo" is not valid,
      - "class `namespace::Foo<Type>` as PyFoo" is not valid.
  
      Args:
        cpp_class_name: The name of the cpp class, i.e. `Class` or
          `Template<...>`.
      Returns:
        The base name of the template (left of first "<") when
        cpp_class_name is templated, None otherwise.
      """
      parameter_index = cpp_class_name.find('<')
      return None if parameter_index < 0 else cpp_class_name[:parameter_index]
  
    def _class(self, ln, ast, pb, ns=None):
      """Translate PYTD class IR ast to AST Decl protobuf."""
      assert isinstance(pb, ast_pb2.Decl), repr(pb)
      atln = ' at line %d' % ln
      pb.line_number = ln
      pb.decltype = pb.CLASS
      p = pb.class_
      cpp_name = ast.name[0]  # Save C++ name without FQ.
      is_iterator = ast.name[-1] == '__iter__'
      _set_name(
          p.name,
          ast.name,
          ns,
          allow_fqcppname=is_iterator,
          template_name=self._extract_template_base_name(cpp_name))
      pyname = p.name.native
      self.check_known_name(pyname, p.name.cpp_name)
      decorators = ast.decorators.asList()
      if not is_iterator:
        self._typetable.set_type(pyname, p.name.cpp_name)
        if 'final' in decorators:
          p.final = True
          decorators.remove('final')
        if 'enable_instance_dict' in decorators:
          p.enable_instance_dict = True
          decorators.remove('enable_instance_dict')
        if 'supress_upcasts' in decorators:
          p.supress_upcasts = True
          decorators.remove('supress_upcasts')
      if decorators:
        raise NameError('Unknown class decorator(s)%s: %s'
                        % (atln, ', '.join(decorators)))
      _set_bases(p.bases, ast.bases, self._names, self._typetable)
  
      # Iterators don't add themselves to the type table (see above), so we can't
      # create a child scope based on them. Not that it matters: __iter__
      # classes aren't allowed to have anything in them.
      if not is_iterator:
        self._typetable.push_scope(pyname)
  
      if ast.docstring:
        p.docstring = ast.docstring[0][2]
  
      local_names = set()
      for decl in ast[-1]:
        if decl[0] == 'pass':
          # Pass is a special case as we don't want to add() to the proto.
          if len(ast[-1]) != 1:
            raise SyntaxError('pass must be the only class statement' + atln)
          continue
        line_number = self.line(decl[1])
        if is_iterator:
          if (len(ast[-1]) != 1 or
              decl[0] != 'func' or decl.name[-1] != '__next__'):
            raise SyntaxError('__iter__ class must only def __next__ at line %d'
                              % line_number)
        else:
          if decl[0] == 'implements':
            name = decl[2]
            self._macro_values = [pyname] + decl[3:]
            try:
              nargs, src, _ = self._macros[name]
            except KeyError:
              raise NameError('interface %s not defined' % name + atln)
            if len(self._macro_values) != nargs+1:
              raise NameError('interface %s needs %d args (%d given)'
                              % (name, len(self._macro_values)-1, nargs) + atln)
            for d in src:
              ln = self.line(d[1])
              if d[0] == 'func':
                if not self.unproperty(ln, d, pyname, p.members, local_names):
                  _add_uniq(pyname, local_names,
                            self._func(ln, d, p.members.add()))
              elif d[0] == 'var':
                _add_uniq(pyname, local_names, self._var(ln, d, p.members.add()))
              else:
                raise SyntaxError('implements %s contains disallowed %s%s'
                                  % (name, d[0], atln))
            self._macro_values = []
            continue
          if decl[0] == 'func' and self.unproperty(
              line_number, decl, pyname, p.members, local_names):
            continue
        name = getattr(self, '_'+decl[0])(line_number, decl, p.members.add())
        _add_uniq(pyname, local_names, name)
  
      funcs = [m.func for m in p.members if m.decltype == m.FUNC]
      is_sequential = any(f.name.native.endswith('#') for f in funcs)
      if is_sequential and any(f.name.native in _RIGHT_OPS for f in funcs):
        raise NameError("class %s %s can't be sequence and number"
                        ' at the same time' % (p.name.native, atln))
      for f in funcs:
        # Fix ctor name to be the class name.
        if f.name.native == '__init__':
          if (f.name.cpp_name and
              f.name.cpp_name not in [cpp_name, '__init__']):
            print('Arbitrary names (like "{0}") for {1} ctor not allowed.'
                  ' Set to {1}'.format(f.name.cpp_name, cpp_name),
                  file=sys.stderr)
          f.name.cpp_name = cpp_name
          f.constructor = True
        elif f.name.native == cpp_name:
          raise NameError('Use __init__ to wrap a "%s" constructor'%pyname + atln)
        elif f.name.cpp_name == cpp_name:
          # @add__init__ will reset cpp_name to be empty.
          raise NameError('Use @add__init__ to wrap additional "%s" constructor'
                          '(s).' % pyname + atln)
        elif not f.name.cpp_name:  # An additional ctor.
          f.name.cpp_name = cpp_name
          f.constructor = True
  
        # Fix 'self' for C++ operator function (implemented out of class).
        elif f.name.native in _RIGHT_OPS:
          if len(f.params) != 1:
            raise ValueError('%s must have only 1 input parameter'
                             % f.name.native + atln)
          f.cpp_opfunction = True  # Request a non-member function.
          self._set_this(f.params.add(), cpp_name, p.name.cpp_name)
        elif '::' in f.name.cpp_name:
          if not f.params:
            f.params.add()
          # else make room for param[0] by shifting 0->1, 1->2 and so on.
          elif len(f.params) == 1:
            f.params.extend([f.params[0]])
          else:
            pcopy = ast_pb2.FuncDecl()
            pcopy.params.extend(f.params)
            del f.params[1:]
            f.params.extend(pcopy.params)
            del pcopy
          f.cpp_opfunction = True  # Request a non-member function.
          self._set_this(f.params[0], cpp_name, p.name.cpp_name)
  
        # Fix 'item|add__' for a 'sequential' class.
        elif is_sequential and (f.name.native.endswith('item__') or
                                f.name.native.endswith('add__')):
          f.name.native += '#'  # Move '+' to tp_as_sequence slots.
  
      if not is_iterator:
        self._typetable.pop_scope()
      return pyname
  
    @staticmethod
    def _set_this(param, py_class_name, cpp_class_name):
      param.name.native = 'self'
      param.name.cpp_name = 'this'
      param.type.lang_type = py_class_name
      param.type.cpp_type = cpp_class_name
  
    def unproperty(self, ln, ast, class_name, members, known_names):
      """Translate PYTD func IR into VAR getter / setter protobuf.
  
      Args:
        ln: .clif line number
        ast: func IR
        class_name: Python name of the wrapped C++ class
        members: wrapped C++ class memebers
        known_names: names already defined in a C++ class wrapper
      Returns:
        True if ast is a @getter/@setter func that describes 'unproperty' C++ var.
      Raises:
        ValueError: if @getter or @setter refers to exising var with =property().
      """
      assert ast[0] == 'func', repr(ast)
      getset = ast.decorators.asList()
      try:
        getset.remove(KEEP_GIL_DECORATOR)
        do_not_release_gil = True
      except ValueError:
        do_not_release_gil = False
      if getset not in (['getter'], ['setter']): return False
      ast.decorators[:] = []
      # Convert func to var.
      f = ast_pb2.Decl()
      self._func(ln, ast, f)
      f = f.func
      if do_not_release_gil: f.py_keep_gil = True
      cname = f.name.cpp_name
      pyname = f.name.native
      for m in members:
        if m.decltype == m.VAR and m.var.name.cpp_name == cname:
          if m.var.cpp_get.name.cpp_name:
            raise ValueError("property var can't have @getter / @setter func")
          if m.var.name.native == pyname:
            known_names.discard(m.var.name.native)
          break
      else:
        m = members.add()
        m.line_number = ln
        m.decltype = m.VAR
        m.var.name.cpp_name = cname
      _add_uniq(class_name, known_names, pyname)
      p = m.var
      if getset == ['getter']:
        if len(f.returns) != 1 or f.params:
          raise TypeError('@getter signature must be (self)->T')
        p.type.CopyFrom(f.returns[0].type)
        p.cpp_get.name.native = pyname
      else:
        assert getset == ['setter']
        if len(f.params) != 1 or f.returns:
          raise TypeError('@setter signature must be (self, _:T)')
        p.type.CopyFrom(f.params[0].type)
        p.cpp_set.name.native = pyname
        if not p.cpp_get.name.native:
          # Provide default getter as VARNAME().
          p.cpp_get.name.native = cname
        # Preserve func param varname for the error message (not useful otherwise)
        p.name.native = f.params[0].name.native
      return True
  
    def _enum(self, ln, ast, pb, ns=None):
      """Translate PYTD enum IR ast to AST Decl protobuf."""
      assert isinstance(pb, ast_pb2.Decl), repr(pb)
      pb.line_number = ln
      pb.decltype = pb.ENUM
      e = pb.enum
      _set_name(e.name, ast.name, ns)
      pyname = e.name.native
      self.check_known_name(pyname)
      self._typetable.set_type(pyname, e.name.cpp_name)
      if len(ast) > 3:
        for rename in ast[-1]:
          _set_name(e.members.add(), rename)
      return pyname
  
    def _var(self, ln, ast, pb):
      """Translate PYTD var IR ast to AST Decl protobuf."""
      assert isinstance(pb, ast_pb2.Decl), repr(pb)
      pb.line_number = ln
      pb.decltype = pb.VAR
      p = pb.var
      _set_name(p.name, ast.name)
      self.set_type(p.type, ast)
      if ast.getter:
        f = p.cpp_get
        f.name.cpp_name = ast.getter
        self.set_type(f.returns.add().type, ast,
                      lambda x, f=f: _set_keep_gil(f, x))
      if ast.setter:
        f = p.cpp_set
        f.name.cpp_name = ast.setter
        self.set_type(f.params.add().type, ast,
                      lambda x, f=f: _set_keep_gil(f, x))
        f.ignore_return_value = True
      if ast.docstring:
        p.docstring = ast.docstring[0][2]
      decorators = ast.decorators.asList()
      if 'extend' in decorators:
        p.is_extend_variable = True
        decorators.remove('extend')
      return p.name.native
  
    def _const(self, ln, ast, pb, ns=None):
      """Translate PYTD const IR ast to AST Decl protobuf."""
      assert isinstance(pb, ast_pb2.Decl), repr(pb)
      pb.line_number = ln
      pb.decltype = pb.CONST
      p = pb.const
      _set_name(p.name, ast.name, ns)
      if self.set_type(p.type, ast) == 'str':
        p.type.cpp_type = 'const char *'  # Special case for b/27458244.
      return p.name.native
  
    def _func(self, ln, ast, pb, ns=None):
      """Translate PYTD def IR ast to AST Decl protobuf."""
      assert isinstance(pb, ast_pb2.Decl), repr(pb)
      pb.line_number = ln
      pb.decltype = pb.FUNC
      f = pb.func
      modified_ast_name = ast.name
      if modified_ast_name[-1] == '__reduce__':
        raise NameError('Please define `__reduce_ex__` instead of `__reduce__`. '
                        'Pickle prefers `__reduce_ex__` over `__reduce__`. '
                        '`__reduce__` is a legacy API and only used if '
                        '`__reduce_ex__` does not exist. See go/pyclif-pickle '
                        'for details.')
      if modified_ast_name[-1] == '__nonzero__':
        raise NameError('Please define `__bool__` instead of `__nonzero__`. '
                        'See b/62796379 for details.')
      if modified_ast_name[-1] == '__bool__' and not self._py3output:
        modified_ast_name[-1] = '__nonzero__'
      _set_name(f.name, _fix_special_names(modified_ast_name), ns,
                allow_fqcppname=True)
      if ast.returns and ast.returns.asList() == [['', [['self']]]]:
        del ast['returns']
        return_self = True
      else:
        return_self = False
      self.set_func(f, ast)
      decorators = ast.decorators.asList()
      if ast.self == 'cls':
        if 'classmethod' not in decorators:
          raise ValueError('Method %s with the first arg cls should be '
                           '@classmethod' % f.name.native)
        if 'virtual' in decorators:
          raise ValueError("Classmethods can't be @virtual")
        f.classmethod = True
        decorators.remove('classmethod')
      elif 'classmethod' in decorators:
        raise ValueError('Method %s with the first arg self should not be '
                         '@classmethod' % f.name.native)
      elif 'virtual' in decorators:
        if ast.self != 'self':
          raise ValueError('@virtual method first arg must be self')
        f.virtual = True
        decorators.remove('virtual')
      if KEEP_GIL_DECORATOR in decorators:
        f.py_keep_gil = True
        decorators.remove(KEEP_GIL_DECORATOR)
      if 'add__init__' in decorators:
        f.name.cpp_name = ''  # A hack to flag an extra ctor.
        decorators.remove('add__init__')
      if 'sequential' in decorators:
        if f.name.native not in ('__getitem__', '__setitem__', '__delitem__',
                                 '__add__', '__iadd__',
                                 '__mul__', '__imul__'):
          raise NameError('Only __{get/set/del}item__, __*add__, or __*mul__'
                          ' can be @sequential (not %s).' % f.name.native)
        f.name.native += '#'  # A hack to flag a sq_* slot.
        decorators.remove('sequential')
      if 'extend' in decorators:
        f.is_extend_method = True
        decorators.remove('extend')
      if '__enter__' in decorators:
        f.name.native = '__enter__@'  # A hack to flag a ctx mgr.
        decorators.remove('__enter__')
      elif f.name.native == '__enter__':
        if f.postproc or f.params or len(f.returns) != 1:
          raise NameError('Use @__enter__ decorator for %s instead of rename'
                          % f.name.cpp_name)
      if '__exit__' in decorators:
        f.name.native = '__exit__@'  # A hack to flag a ctx mgr.
        decorators.remove('__exit__')
      elif f.name.native == '__exit__':
        if (len(f.params) != 3
            or len(f.returns) > 1
            or any(p.type.lang_type != 'object' for p in f.params)):
          raise NameError('Use @__exit__ decorator for %s instead of rename'
                          % f.name.cpp_name)
      elif f.name.native in _IGNORE_RETURN_VALUE:
        f.ignore_return_value = True
        if f.name.native in _INPLACE_OPS:
          if ast.self != 'self':
            raise NameError('Inplace ops must have "self" as the first argument.')
          if not return_self:
            raise NameError('Inplace ops must return "self".')
          if ast.postproc:
            raise ValueError('Inplace ops can\'t have "return Postprocess(...)"')
          f.postproc = '->self'  # '->' indicate special postprocessing.
      if return_self and f.postproc != '->self':
        raise ValueError('Only inplace ops can return "self".')
      if ast.postproc:
        name = ast.postproc[0][0][0]
        try:
          f.postproc = self._names[name]
        except KeyError:
          raise NameError('Should import name "%s" before use.' % name)
      name = f.name.native.rstrip('@#')
      if decorators:
        raise ValueError('Unknown decorator%s for def %s: %s'
                         % ('s' if len(decorators) > 1 else '',
                            name, ', '.join('@'+f for f in decorators)))
      if ast.docstring:
        f.docstring = ast.docstring[0][2]
      return name
  
    # helpers
  
    def set_type(self, pb, ast, has_object=lambda x: None):
      """Fill AST Type protobuf from PYTD IR ast."""
      assert isinstance(pb, ast_pb2.Type), repr(pb)
      if ast.callable:
        self.set_func(pb.callable, ast.callable)
        inputs = (a.name.native+':'+a.type.lang_type for a in pb.callable.params)
        inputs = '(%s)' % ', '.join(inputs)
        if len(pb.callable.returns) > 1:
          outputs = (':'+r.type.lang_type for r in pb.callable.returns)
          outputs = '(%s)' % ', '.join(outputs)
        elif pb.callable.returns:
          outputs = pb.callable.returns[0].type.lang_type or 'None'
        else:
          outputs = 'None'
        pb.lang_type = inputs + '->' + outputs
        if pb.lang_type == '()->None':
          # Set any field inside to avoid empty callable message.
          pb.callable.cpp_opfunction = True
        if len(ast.callable) == 3:  # Has an explicit C++ type.
          pb.cpp_type = ast.callable[0]
        # Else fill it after matcher finds the types.
      if ast.named:
        self.set_typename(pb, ast.named)
        if len(ast.named) > 1:
          pb.lang_type += '<%s>' % ', '.join(self.set_type(
              pb.params.add(), t, has_object) for t in ast.named[1:])
          if len(ast.named.name) > 1:  # Has an explicit C++ type.
            pb.cpp_type = ast.named.name[0]
      assert pb.lang_type, 'Parameter AST is not "named" or "callable":\n%r' % ast
      if pb.lang_type == 'object': has_object(True)
      return pb.lang_type
  
    def set_typename(self, pb, ast):
      """Substitute C++ type based on pytype name."""
      assert isinstance(pb, ast_pb2.Type), repr(pb)
      pytype = ast.name[-1]
      if pytype.startswith('%'):
        assert self._macro_values
        pytype = self._macro_values[int(pytype[1:])]
      if not self.is_pyname_known(pytype):
        raise NameError('Type %s should be defined before use. Did you forget to'
                        ' import a CLIF-generated C++ header?' % pytype)
      pb.lang_type = pytype
      if len(ast.name) > 1:  # Has an explicit C++ type.
        pb.cpp_type = ast.name[0]
      else:
        ctype = self._capsules.get(pytype)
        if ctype:
          pb.cpp_raw_pointer = True
        elif self._typetable.has_type(pytype):
          ctype = self._typetable.get_last_cpp_type(pytype)
        else:
          alias_ir = self._typenames.get(pytype)
          if alias_ir:
            pytype = alias_ir.name[-1]
            assert self._typetable.has_type(pytype), ('alias %s not in typetable'
                                                      % pytype)
            ctype = self._typetable.get_last_cpp_type(pytype)
        assert ctype, 'C++ type for %s not found' % pytype
        pb.cpp_type = ctype
  
    def set_func(self, pb, ast):
      """Fill AST FuncDecl protobuf from PYTD IR ast."""
      assert isinstance(pb, ast_pb2.FuncDecl), repr(pb)
      arg_names = set()
      must_be_optional = False
      for arg in ast.params:
        pyname = arg.name[-1]
        if pyname in arg_names:
          raise NameError('Name "%s" already used in args.' % pyname)
        arg_names.add(pyname)
        p = pb.params.add()
        _set_name(p.name, arg.name)
        self.set_type(p.type, arg, lambda x, f=pb: _set_keep_gil(f, x))
        if len(arg) > 2:
          p.default_value = arg[2]
          must_be_optional = True
        elif must_be_optional:
          raise ValueError('Arg "%s" (and all after) must be optional bacause '
                           'arg(s) before it marked optional.')
      for t in ast.returns:
        p = pb.returns.add()
        self.set_type(p.type, t, lambda x, f=pb: _set_keep_gil(f, x))
        if t.name:
          pyname = t.name[-1]
          if pyname in arg_names:
            raise NameError('Name "%s" already used in args.' % pyname)
          arg_names.add(pyname)
          _set_name(p.name, t.name)
  
  
  class _TypeTable(object):
    """Manage the Python -> C++ type name mappings.
  
    Normally, the Python -> C++ mapping is simple: replace '.' with '::'. However,
    there are a variety of special cases:
     * Aliased imports create a Python name with no corresponding C++ type.
     * Class functions can wrap absolutely qualified C++ functions.
     * Mappings added from headers map the Python name to the fully qualified
       C++ type.
  
    Additionally, there are some basic scoping rules that apply, so the type
    table allows controlling the scope in which lookups occur.
    """
  
    def __init__(self):
      """Create an instance."""
      self._root = _TypeEntry.create_root_entry()
      self._current_scope = self._root
  
    @contextlib.contextmanager
    def scope(self, pyname):
      """Context manager for entering and leaving a scope of type names.
  
      Args:
        pyname: str, Python type name; see `push_scope()`
      Yields:
        None
      """
      try:
        self.push_scope(pyname)
        yield
      finally:
        self.pop_scope()
  
    def push_scope(self, pyname):
      """Enters a new scope for adding types into under the given `pyname`.
  
      Instead of calling this manually, prefer to use the `scope()` context
      manager instead.
  
      Args:
        pyname: str, the name of an existing Python type.
      """
      assert pyname, 'Non-empty pyname is required'
      self._current_scope = self._current_scope.get_nested_type(pyname)
  
    def pop_scope(self):
      """Leaves the current scope and switches to the parent scope."""
      self._current_scope = self._current_scope.parent
  
    def set_type(self, pyname, cpp_name):
      """Set a C++ type for a Python type in the current scope.
  
      This will check that, if `pyname` already exists, that `cpp_name`
      matches the existing value. A mismatch will raise an error.
  
      This is usually used to add types as they are encountered from type
      definitions in a Clif file.
  
      Args:
        pyname: str, the Python name of the type. It will be added to the
          current scope. A dotted name is not allowed: the name should
          be the base name for the type in the current scope.
        cpp_name: str, the C++ type name, relative to the current scope, or an
          absolute type name. This _may_ begin with a namespace (MyNs::MyCls),
          but shouldn't include sub-types (MyType::MySubType).
      """
      assert not isinstance(cpp_name, list)
      assert '.' not in pyname
      self._current_scope.set_nested_type(pyname, cpp_name)
  
    def add_type(self, pyname, cpp_name):
      """Append a CPP type to a Python name in the current scope.
  
      This makes `cpp_name` the preferred type to use for `pyname`, i.e.,
      last added type wins.
  
      This is usually used to add imported mappings, e.g., from headers
      or import statements.
  
      Args:
        pyname: str, the Python name for the type. It can be a dotted name,
          e.g., 'Foo.Bar'. If intermediate types don't exist, empty scopes
          will be created.
        cpp_name: str, the C++ name for the type. If a dotted `pyname` is used,
          then `cpp_name` should reflect the properly qualified C++ name
          for `pyname` relative to the current scope. e.g., if
          pyname=Foo.Bar, then `cpp_name` should likely be 'Foo::Bar'. An absolute
          C++ name can also be used instead (e.g. ::Foo::Bar).
      """
      assert not isinstance(cpp_name, list)
      if '.' in pyname:
        parts = pyname.split('.')
        base_name = parts.pop()
        current = self._current_scope
        for name in parts:
          current = current.add_empty_nested_type(name)
        current.add_nested_type(base_name, cpp_name)
      else:
        self._current_scope.add_nested_type(pyname, cpp_name)
  
    def get_last_cpp_type(self, pyname):
      """Get the last registered C++ type for a Python type.
  
      Some Python types have multiple C++ types registered. Most (e.g.,
      a class defined in a .clif file) only have a single type registered.
      For reasons unknown, the last registered type is what gets used
      as the preferred C++ type.
  
      Args:
        pyname: str, the name of the type. It can be a dotted name, e.g. 'A.B'.
  
      Returns:
        str, the fully qualified C++ type name that was last mapped to the Python
        type.
  
      Raises:
        NameError: on unknown Python type.
      """
      parts = pyname.split('.')
      fq_cpp_name_parts = []
  
      current = self._find_entry(parts[0])
      if not current:
        raise NameError('Unknown Python type: {!r}'.format(pyname))
  
      for name in parts:
        entry = current.get_nested_type(name)
        cpp_type = entry.get_last_cpp_type()
        if cpp_type:
          # TODO: add a test where an absolute type is registered
          # under a dotted name. Some stubby Response.Code tests failed due to
          # something like that going on. Need a test with a line like
          #   // CLIF use `::Response::Code` as Response.Code
          # An inner type can be mapped to an absolute C++ type, in which case,
          # we don't want to prefix it with the parent. So just reset the parts.
          # Keep iterating, though, since we need to continue down to the
          # final name part.
          if cpp_type.startswith('::'):
            fq_cpp_name_parts = [cpp_type]
          else:
            fq_cpp_name_parts.append(cpp_type)
        current = entry
  
      full_cpp_type = '::'.join(fq_cpp_name_parts)
  
      # If types get registered and/or re-joined incorrectly, it can generate
      # names that are malformed, usually by joining two empty names or
      # a relative and absolute name. This helps catch that simple case.
      assert ':::' not in full_cpp_type, 'Malformed C++ typename: {}'.format(
          full_cpp_type)
      return full_cpp_type
  
    def _find_entry(self, pyname):
      """Search up the scope tree for a Python name."""
      assert '.' not in pyname
      current = self._current_scope
      while current:
        if current.has_nested_type(pyname):
          break
        current = current.parent
      return current
  
    def has_type(self, pyname):
      """Tells if a Python type is registered.
  
      Note that it doesn't mean there are C++ types associated with it.
  
      Args:
        pyname: str, the name of the Python type. It can be a dotted name.
  
      Returns:
        bool, True if any C++ types are registered, False if not.
      """
      parts = pyname.split('.')
  
      current = self._find_entry(parts[0])
  
      if not current:
        return False
  
      for name in parts:
        if not current.has_nested_type(name):
          return False
        current = current.get_nested_type(name)
      return True
  
    def find_pyname_for_cpp_type(self, cpp_type):
      """Find the first matching Python type for a C++ type, if any.
  
      Args:
        cpp_type: str, the c++ type to search for.
  
      Returns:
        str, the Python type that matches, or empty string if no match.
      """
      for pyname, cpp_types in self.iter_types():
        if cpp_type in cpp_types:
          return pyname
      return ''
  
    def iter_types(self):
      """Walks through all knowns types and their C++ mappings.
  
      Yields:
        Tuple[str pyname, list[str] cpp_names], where `pyname` is the
        fully qualified Python name, and `cpp_names` are the fully
        qualified C++ names.
      """
      for entry in self._root.walk_nested_types():
        yield entry
  
    def __repr__(self):
      # The type table can be pretty big, so format it in a nice way so that
      # its intelligible.
      types = '\n'.join(
          '{:<20} -> {}'.format(*entry) for entry in sorted(self.iter_types()))
      return '_TypeTable(types=\n{types}\n)'.format(types=types)
  
  
  class _TypeEntry(object):
    """Type mapping information for use by _TypeTable.
  
    This is private to _TypeTable; _TypeTable has the public APIs for correctly
    interacting with _TypeEntry data.
    """
  
    def __init__(self, pyname=None, cpp_name=None, parent=None):
      """Creates an instance: use the class-level helpers instead.
  
      This constructor is private: use the appropriate create_* methods
      for creating instances to ensure correct creation.
  
      Args:
        pyname: Optional[str], name of the Python type. Optional for
          the root-level _TypeEntry, otherwise required.
        cpp_name: Optiona[str], name of the corresponding C++ type,
          if any. Additional names may be added later. Root instances
          and "namespace" instances (i.e., names created through an
          aliased import) won't have a C++ type.
        parent: Optional[_TypeEntry], the outer scope for this entry.
          Root level entries don't have it, all others do.
      """
      # Optional[str]
      self._pyname = pyname
      # The C++ type names may be relative to the parent entry, or
      # fully qualified.
      # list[str]
      self._cpp_names = []
      if cpp_name:
        self.add_cpp_type(cpp_name)
      # Optional[_TypeEntry]
      self._parent = parent
      # MutableMapping[str py_name, _TypeEntry]
      self._types = {}
  
    @classmethod
    def create_root_entry(cls):
      """Create a top-level object; only _TypeTable should call this."""
      return cls(None, None)
  
    def _create_child_entry(self, pyname, cpp_name):
      """Create a child entry of the current entry.
  
      Args:
        pyname: str, the Python type name, required.
        cpp_name: Optional[str], C++ type name; it may be omitted if
          the child entry is just a "namespace" for containing other types,
          e.g., as part of an aliased import.
  
      Returns:
        _TypeEntry
      """
      assert pyname, 'Non-empty pyname is required'
      return _TypeEntry(pyname, cpp_name, parent=self)
  
    @property
    def parent(self):
      return self._parent
  
    def get_last_cpp_type(self):
      """Get the last registered C++ type, or an empty string if none."""
      return self._cpp_names[-1] if self._cpp_names else ''
  
    def get_cpp_types(self):
      return self._cpp_names[:]
  
    def add_cpp_type(self, cpp_name):
      """Add a C++ type to this entry."""
      assert cpp_name
      # NOTE: `cpp_name` may already be in the list, which seems redundant,
      # but is relied upon so that the last use X as Y statement wins.
      self._cpp_names.append(cpp_name)
  
    def set_nested_type(self, pyname, cpp_name):
      """Set the C++ type for a Python type, checking for conflicts.
  
      This is usually used to add a specific mapping for which there is only
      one C++ type, such as a class definition in a clif file -- in such cases,
      there should only be a single C++ type.
  
      Args:
        pyname: str, the Python name for the type. No dots allowed. If
          the name already exists, then `cpp_name` must match the pre-existing
          entry.
        cpp_name: str, the C++ type name.
      """
      assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                                 'meant to use _TypeTable').format(pyname)
      try:
        existing = self._types[pyname]
      except KeyError:
        entry = self._create_child_entry(pyname, cpp_name)
        self._types[pyname] = entry
      else:
        desired_cpp_names = [cpp_name]
        existing_cpp_names = existing._cpp_names  # pylint: disable=protected-access
        if existing_cpp_names != desired_cpp_names:
          raise ValueError(
              'Python type {!r}: existing C++ types {!r} don\'t match desired '
              'types {!r}'.format(pyname, existing_cpp_names, desired_cpp_names))
  
    def add_nested_type(self, pyname, cpp_name):
      """Append a C++ type to a Python type.
  
      If the Python type doesn't exist, it will be created.
      If it already exists, then the C++ type will be added.
  
      This is usually used to add imported mappings, e.g., from headers or
      import statements.
  
      Args:
        pyname: str, the Python type name, no dots allowed.
        cpp_name: str, the C++ type name.
      """
      assert pyname, 'Non-empty pyname required'
      assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                                 'meant to use _TypeTable').format(pyname)
      assert cpp_name, 'Non-empty cpp_name required'
      try:
        existing = self._types[pyname]
      except KeyError:
        entry = self._create_child_entry(pyname, cpp_name)
        self._types[pyname] = entry
      else:
        existing.add_cpp_type(cpp_name)
  
    def add_empty_nested_type(self, pyname):
      """Create an empty nested type, e.g., to act as a namespace."""
      assert pyname, 'Non-empty pyname required'
      assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                                 'meant to use _TypeTable').format(pyname)
      try:
        existing = self._types[pyname]
      except KeyError:
        entry = self._create_child_entry(pyname, None)
        self._types[pyname] = entry
        return entry
      else:
        return existing
  
    def has_nested_type(self, pyname):
      """Tell if the Python type is present."""
      assert pyname, 'Non-empty pyname required'
      assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                                 'meant to use _TypeTable').format(pyname)
      return pyname in self._types
  
    def get_nested_type(self, pyname):
      """Get the type entry for the Python name.
  
      Args:
        pyname: str, the Python name, no dots allowed. For dotted-name
          lookup, use the _TypeTable APIs.
  
      Returns:
        _TypeEntry of the nested type.
  
      Raises:
        _TypeNotFoundError: if the nested type isn't found.
      """
      assert pyname, 'Non-empty pyname required'
      assert '.' not in pyname, ('pyname {!r} cannot contain dots: you probably '
                                 'meant to use _TypeTable').format(pyname)
      try:
        child = self._types[pyname]
      except KeyError:
        raise _TypeNotFoundError(pyname)
      return child
  
    def walk_nested_types(self):
      """Walks over all nested types, recursively.
  
      Yields:
        Tuple[str pyname, List[str] cpp_names]. `pyname` is the fully
        qualified (relative to this entry) name. `cpp_names` is a list of
        C++ type names; each C++ type is either an absolute name (starts with
        '::'), or fully qualified relative to this entry.
      """
      for pyname, entry in self._types.items():
        cpp_types = entry.get_cpp_types()
        if cpp_types:
          yield pyname, cpp_types
  
        for child_pyname, child_cpp_types in entry.walk_nested_types():
          if cpp_types:
            prefix = cpp_types[-1]
            child_cpp_types = [
                self._build_cpp_type(prefix, child_cpp_type)
                for child_cpp_type in child_cpp_types
            ]
          yield pyname + '.' + child_pyname, child_cpp_types
  
    def _build_cpp_type(self, parent_prefix, child_cpp_type):
      if child_cpp_type.startswith('::'):
        return child_cpp_type
      else:
        return '{}::{}'.format(parent_prefix, child_cpp_type)
  
    def __repr__(self):
      return (
          '_TypeEntry(pyname={pyname!r}, cpp_types={ctypes!r}, '
          'nested_types={nested_names}').format(
              pyname=self._pyname, ctypes=self._cpp_names,
              nested_names=sorted(self._types.keys()))
  
  
  class _TypeNotFoundError(Exception):
    """Raised when a _TypeEntry doesn't have a requested Python name."""
  
  
  def _set_bases(pb, ast_bases, names, typetable):
    """Fill AST.ClassDecl bases pb from IR.bases."""
    for b in ast_bases:
      n = b[-1]
      if len(b) != 1:
        raise NameError('Base class must not have a C++ name')
      if n not in names:
        # TODO: Lookup possible 'renames' for bases.
        if not typetable.has_type(n):
          raise NameError('Base class %s not defined' % n)
      base = pb.add()
      base.native = n
  
  
  def _set_name(pb,
                ast,
                namespace=None,
                allow_fqcppname=False,
                template_name=None):
    """Fill AST Name protobuf from PYTD IR ast.
  
    Args:
      pb: the AST Name protocol buffer to fill.
      ast: the PYTD IR ast node.
      namespace: the namespace of the c++ type.
      allow_fqcppname: whether to allow fullt qualified namespace.
      template_name: the template base name i.e. `Template` in `Template<...>`. It
        is passed for renamed C++ templated classes only.
  
    Raises:
      NameError: when the name is not supported.
    """
    assert isinstance(pb, ast_pb2.Name), repr(pb)
    assert ast, repr(ast)
    pb.native = ast[-1]
    if not allow_fqcppname and '::' in (template_name or ast[0]):
      raise NameError(':: not allowed in C++ name for ' + ast[-1])
    if not namespace or ast[0].startswith('::'):  # absolute name
      pb.cpp_name = ast[0]
    else:
      if not namespace.endswith('::'):
        namespace += '::'
      pb.cpp_name = namespace + ast[0]
  
  
  def _set_keep_gil(f, val):
    f.py_keep_gil = val
  
  
  def _add_uniq(class_name, names_set, new_name):
    assert new_name, class_name+' has %s' % names_set
    if new_name:
      if new_name in names_set:
        raise NameError('Name "%s" already defined in class %s'
                        % (new_name, class_name))
      names_set.add(new_name)
  
  
  def _subst_type_formal(ast, from_map):
    """Walk type ast and replace names from_map to %position markers."""
    if ast.callable:
      for p in ast.callable.params:
        _subst_type_formal(p, from_map)
      for p in ast.callable.returns:
        _subst_type_formal(p, from_map)
    if ast.named:
      n = ast.named.name
      if len(ast.named) > 1:
        for t in ast.named[1:]:
          _subst_type_formal(t, from_map)
      else:
        p = n[-1]
        if p in from_map:
          if len(n) > 1:  # Has an explicit C++ type.
            raise NameError('C++ name not allowed in interface parameters (%s)'%p)
          n[-1] = '%' + str(from_map[p])
  
  
  # Special methods that must return self.
  _INPLACE_OPS = frozenset([
      '__iadd__',
      '__iadd__#',  # sq_concat
      '__isub__',
      '__imul__',
      '__imul__#',  # sq_repeat
      '__idiv__',
      '__ifloordiv__',
      '__itruediv__',
      '__imod__',
      '__ipow__',
      '__ilshift__',
      '__irshift__',
      '__iand__',
      '__ixor__',
      '__ior__',
  ])
  # Special methods that don't use returning C++ value, so we can ignore it.
  _IGNORE_RETURN_VALUE = frozenset([
      '__setitem__',
      '__delitem__',
      '__setattr__',
      '__delattr__',
  ] + list(_INPLACE_OPS))
  
  # Python special method name -> C++ operator rename table.
  _SPECIAL = {
      '__lt__': 'operator<',
      '__le__': 'operator<=',
      '__gt__': 'operator>',
      '__ge__': 'operator>=',
      '__eq__': 'operator==',
      '__ne__': 'operator!=',
      '__pos__': 'operator+',
      '__add__': 'operator+',
      '__radd__': 'operator+',
      '__iadd__': 'operator+=',
      '__neg__': 'operator-',
      '__sub__': 'operator-',
      '__rsub__': 'operator-',
      '__isub__': 'operator-=',
      '__mul__': 'operator*',
      '__rmul__': 'operator*',
      '__imul__': 'operator*=',
      '__div__': 'operator/',
      '__rdiv__': 'operator/',
      '__idiv__': 'operator/=',
      '__floordiv__': 'operator/',
      '__rfloordiv__': 'operator/',
      '__ifloordiv__': 'operator/=',
      '__truediv__': 'operator/',
      '__rtruediv__': 'operator/',
      '__itruediv__': 'operator/=',
      '__mod__': 'operator%',
      '__rmod__': 'operator%',
      '__imod__': 'operator%=',
      '__lshift__': 'operator<<',
      '__rlshift__': 'operator<<',
      '__ilshift__': 'operator<<=',
      '__rshift__': 'operator>>',
      '__rrshift__': 'operator>>',
      '__irshift__': 'operator>>=',
      '__and__': 'operator&',
      '__rand__': 'operator&',
      '__iand__': 'operator&=',
      '__xor__': 'operator^',
      '__rxor__': 'operator^',
      '__ixor__': 'operator^=',
      '__or__': 'operator|',
      '__ror__': 'operator|',
      '__ior__': 'operator|=',
      '__inv__': 'operator~',
      '__invert__': 'operator~',
      '__call__': 'operator()',
      '__getitem__': 'operator[]',
      '__del__': 'DO_NOT_DECLARE_DTOR',
      '__next__': 'operator*',  # For the "class __iter__: def __next__" case.
      '__int__': 'operator int',
      '__float__': 'operator double',
      # TODO:  fix / remove one of 'operator bool' mapping,
      # so will have only one in the future.
      '__nonzero__': 'operator bool',  # PY2
      '__bool__': 'operator bool',  # PY3
  }
  _RIGHT_OPS = frozenset([
      # Can only be implemented as free functions, not C++ member functions.
      '__radd__',
      '__rsub__',
      '__rmul__',
      '__rdiv__',
      '__rtruediv__',
      '__rfloordiv__',
      '__rmod__',
      '__rdivmod__',
      '__rpow__',
      '__rlshift__',
      '__rrshift__',
      '__rand__',
      '__ror__',
      '__rxor__',
  ])
  assert _RIGHT_OPS - set(_SPECIAL), frozenset('__r%s__' % op for op in (
      'divmod pow'.split(' ')))
  
  
  def _fix_special_names(ast_name):
    """Fill "cpp_name" for Python special name if empty."""
    if len(ast_name) == 1:
      pyname = ast_name[0]
      op = _SPECIAL.get(pyname)
      if op:
        return [op, pyname]
    return ast_name
  