src/third_party/cython/src/Cython/Compiler/PyrexTypes.py

   1 #
   2 #   Cython/Python language types
   3 #
   4
   5 from Code import UtilityCode, LazyUtilityCode, TempitaUtilityCode
   6 import StringEncoding
   7 import Naming
   8 import copy
   9 from Errors import error
  10
  11 class BaseType(object):
  12     #
  13     #  Base class for all Cython types including pseudo-types.
  14
  15     # List of attribute names of any subtypes
  16     subtypes = []
  17
  18     def can_coerce_to_pyobject(self, env):
  19         return False
  20
  21     def cast_code(self, expr_code):
  22         return "((%s)%s)" % (self.declaration_code(""), expr_code)
  23
  24     def specialization_name(self):
  25         # This is not entirely robust.
  26         safe = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_0123456789'
  27         all = []
  28         for c in self.declaration_code("").replace("unsigned ", "unsigned_").replace("long long", "long_long").replace(" ", "__"):
  29             if c in safe:
  30                 all.append(c)
  31             else:
  32                 all.append('_%x_' % ord(c))
  33         return ''.join(all)
  34
  35     def base_declaration_code(self, base_code, entity_code):
  36         if entity_code:
  37             return "%s %s" % (base_code, entity_code)
  38         else:
  39             return base_code
  40
  41     def __deepcopy__(self, memo):
  42         """
  43         Types never need to be copied, if we do copy, Unfortunate Things
  44         Will Happen!
  45         """
  46         return self
  47
  48     def get_fused_types(self, result=None, seen=None, subtypes=None):
  49         subtypes = subtypes or self.subtypes
  50         if subtypes:
  51             if result is None:
  52                 result = []
  53                 seen = set()
  54
  55             for attr in subtypes:
  56                 list_or_subtype = getattr(self, attr)
  57                 if list_or_subtype:
  58                     if isinstance(list_or_subtype, BaseType):
  59                         list_or_subtype.get_fused_types(result, seen)
  60                     else:
  61                         for subtype in list_or_subtype:
  62                             subtype.get_fused_types(result, seen)
  63
  64             return result
  65
  66         return None
  67
  68     def specialize_fused(self, env):
  69         if env.fused_to_specific:
  70             return self.specialize(env.fused_to_specific)
  71
  72         return self
  73
  74     def _get_fused_types(self):
  75         """
  76         Add this indirection for the is_fused property to allow overriding
  77         get_fused_types in subclasses.
  78         """
  79         return self.get_fused_types()
  80
  81     is_fused = property(_get_fused_types, doc="Whether this type or any of its "
  82                                              "subtypes is a fused type")
  83
  84     def deduce_template_params(self, actual):
  85         """
  86         Deduce any template params in this (argument) type given the actual
  87         argument type.
  88
  89         http://en.cppreference.com/w/cpp/language/function_template#Template_argument_deduction
  90         """
  91         if self == actual:
  92             return {}
  93         else:
  94             return None
  95
  96     def __lt__(self, other):
  97         """
  98         For sorting. The sorting order should correspond to the preference of
  99         conversion from Python types.
 100
 101         Override to provide something sensible. This is only implemented so that
 102         python 3 doesn't trip
 103         """
 104         return id(type(self)) < id(type(other))
 105
 106     def py_type_name(self):
 107         """
 108         Return the name of the Python type that can coerce to this type.
 109         """
 110
 111     def typeof_name(self):
 112         """
 113         Return the string with which fused python functions can be indexed.
 114         """
 115         if self.is_builtin_type or self.py_type_name() == 'object':
 116             index_name = self.py_type_name()
 117         else:
 118             index_name = str(self)
 119
 120         return index_name
 121
 122     def check_for_null_code(self, cname):
 123         """
 124         Return the code for a NULL-check in case an UnboundLocalError should
 125         be raised if an entry of this type is referenced before assignment.
 126         Returns None if no check should be performed.
 127         """
 128         return None
 129
 130     def invalid_value(self):
 131         """
 132         Returns the most invalid value an object of this type can assume as a
 133         C expression string. Returns None if no such value exists.
 134         """
 135
 136
 137 class PyrexType(BaseType):
 138     #
 139     #  Base class for all Cython types
 140     #
 141     #  is_pyobject           boolean     Is a Python object type
 142     #  is_extension_type     boolean     Is a Python extension type
 143     #  is_final_type         boolean     Is a final extension type
 144     #  is_numeric            boolean     Is a C numeric type
 145     #  is_int                boolean     Is a C integer type
 146     #  is_float              boolean     Is a C floating point type
 147     #  is_complex            boolean     Is a C complex type
 148     #  is_void               boolean     Is the C void type
 149     #  is_array              boolean     Is a C array type
 150     #  is_ptr                boolean     Is a C pointer type
 151     #  is_null_ptr           boolean     Is the type of NULL
 152     #  is_reference          boolean     Is a C reference type
 153     #  is_const              boolean     Is a C const type.
 154     #  is_cfunction          boolean     Is a C function type
 155     #  is_struct_or_union    boolean     Is a C struct or union type
 156     #  is_struct             boolean     Is a C struct type
 157     #  is_enum               boolean     Is a C enum type
 158     #  is_typedef            boolean     Is a typedef type
 159     #  is_string             boolean     Is a C char * type
 160     #  is_pyunicode_ptr      boolean     Is a C PyUNICODE * type
 161     #  is_cpp_string         boolean     Is a C++ std::string type
 162     #  is_unicode_char       boolean     Is either Py_UCS4 or Py_UNICODE
 163     #  is_returncode         boolean     Is used only to signal exceptions
 164     #  is_error              boolean     Is the dummy error type
 165     #  is_buffer             boolean     Is buffer access type
 166     #  has_attributes        boolean     Has C dot-selectable attributes
 167     #  default_value         string      Initial value
 168     #  entry                 Entry       The Entry for this type
 169     #
 170     #  declaration_code(entity_code,
 171     #      for_display = 0, dll_linkage = None, pyrex = 0)
 172     #    Returns a code fragment for the declaration of an entity
 173     #    of this type, given a code fragment for the entity.
 174     #    * If for_display, this is for reading by a human in an error
 175     #      message; otherwise it must be valid C code.
 176     #    * If dll_linkage is not None, it must be 'DL_EXPORT' or
 177     #      'DL_IMPORT', and will be added to the base type part of
 178     #      the declaration.
 179     #    * If pyrex = 1, this is for use in a 'cdef extern'
 180     #      statement of a Cython include file.
 181     #
 182     #  assignable_from(src_type)
 183     #    Tests whether a variable of this type can be
 184     #    assigned a value of type src_type.
 185     #
 186     #  same_as(other_type)
 187     #    Tests whether this type represents the same type
 188     #    as other_type.
 189     #
 190     #  as_argument_type():
 191     #    Coerces array and C function types into pointer type for use as
 192     #    a formal argument type.
 193     #
 194
 195     is_pyobject = 0
 196     is_unspecified = 0
 197     is_extension_type = 0
 198     is_final_type = 0
 199     is_builtin_type = 0
 200     is_numeric = 0
 201     is_int = 0
 202     is_float = 0
 203     is_complex = 0
 204     is_void = 0
 205     is_array = 0
 206     is_ptr = 0
 207     is_null_ptr = 0
 208     is_reference = 0
 209     is_const = 0
 210     is_cfunction = 0
 211     is_struct_or_union = 0
 212     is_cpp_class = 0
 213     is_cpp_string = 0
 214     is_struct = 0
 215     is_enum = 0
 216     is_typedef = 0
 217     is_string = 0
 218     is_pyunicode_ptr = 0
 219     is_unicode_char = 0
 220     is_returncode = 0
 221     is_error = 0
 222     is_buffer = 0
 223     is_memoryviewslice = 0
 224     has_attributes = 0
 225     default_value = ""
 226
 227     def resolve(self):
 228         # If a typedef, returns the base type.
 229         return self
 230
 231     def specialize(self, values):
 232         # TODO(danilo): Override wherever it makes sense.
 233         return self
 234
 235     def literal_code(self, value):
 236         # Returns a C code fragment representing a literal
 237         # value of this type.
 238         return str(value)
 239
 240     def __str__(self):
 241         return self.declaration_code("", for_display = 1).strip()
 242
 243     def same_as(self, other_type, **kwds):
 244         return self.same_as_resolved_type(other_type.resolve(), **kwds)
 245
 246     def same_as_resolved_type(self, other_type):
 247         return self == other_type or other_type is error_type
 248
 249     def subtype_of(self, other_type):
 250         return self.subtype_of_resolved_type(other_type.resolve())
 251
 252     def subtype_of_resolved_type(self, other_type):
 253         return self.same_as(other_type)
 254
 255     def assignable_from(self, src_type):
 256         return self.assignable_from_resolved_type(src_type.resolve())
 257
 258     def assignable_from_resolved_type(self, src_type):
 259         return self.same_as(src_type)
 260
 261     def as_argument_type(self):
 262         return self
 263
 264     def is_complete(self):
 265         # A type is incomplete if it is an unsized array,
 266         # a struct whose attributes are not defined, etc.
 267         return 1
 268
 269     def is_simple_buffer_dtype(self):
 270         return (self.is_int or self.is_float or self.is_complex or self.is_pyobject or
 271                 self.is_extension_type or self.is_ptr)
 272
 273     def struct_nesting_depth(self):
 274         # Returns the number levels of nested structs. This is
 275         # used for constructing a stack for walking the run-time
 276         # type information of the struct.
 277         return 1
 278
 279     def global_init_code(self, entry, code):
 280         # abstract
 281         pass
 282
 283     def needs_nonecheck(self):
 284         return 0
 285
 286
 287 def public_decl(base_code, dll_linkage):
 288     if dll_linkage:
 289         return "%s(%s)" % (dll_linkage, base_code)
 290     else:
 291         return base_code
 292
 293 def create_typedef_type(name, base_type, cname, is_external=0):
 294     is_fused = base_type.is_fused
 295     if base_type.is_complex or is_fused:
 296         if is_external:
 297             if is_fused:
 298                 msg = "Fused"
 299             else:
 300                 msg = "Complex"
 301
 302             raise ValueError("%s external typedefs not supported" % msg)
 303
 304         return base_type
 305     else:
 306         return CTypedefType(name, base_type, cname, is_external)
 307
 308
 309 class CTypedefType(BaseType):
 310     #
 311     #  Pseudo-type defined with a ctypedef statement in a
 312     #  'cdef extern from' block.
 313     #  Delegates most attribute lookups to the base type.
 314     #  (Anything not defined here or in the BaseType is delegated.)
 315     #
 316     #  qualified_name      string
 317     #  typedef_name        string
 318     #  typedef_cname       string
 319     #  typedef_base_type   PyrexType
 320     #  typedef_is_external bool
 321
 322     is_typedef = 1
 323     typedef_is_external = 0
 324
 325     to_py_utility_code = None
 326     from_py_utility_code = None
 327
 328     subtypes = ['typedef_base_type']
 329
 330     def __init__(self, name, base_type, cname, is_external=0):
 331         assert not base_type.is_complex
 332         self.typedef_name = name
 333         self.typedef_cname = cname
 334         self.typedef_base_type = base_type
 335         self.typedef_is_external = is_external
 336
 337     def invalid_value(self):
 338         return self.typedef_base_type.invalid_value()
 339
 340     def resolve(self):
 341         return self.typedef_base_type.resolve()
 342
 343     def declaration_code(self, entity_code,
 344             for_display = 0, dll_linkage = None, pyrex = 0):
 345         if pyrex or for_display:
 346             base_code = self.typedef_name
 347         else:
 348             base_code = public_decl(self.typedef_cname, dll_linkage)
 349         return self.base_declaration_code(base_code, entity_code)
 350
 351     def as_argument_type(self):
 352         return self
 353
 354     def cast_code(self, expr_code):
 355         # If self is really an array (rather than pointer), we can't cast.
 356         # For example, the gmp mpz_t.
 357         if self.typedef_base_type.is_array:
 358             base_type = self.typedef_base_type.base_type
 359             return CPtrType(base_type).cast_code(expr_code)
 360         else:
 361             return BaseType.cast_code(self, expr_code)
 362
 363     def __repr__(self):
 364         return "<CTypedefType %s>" % self.typedef_cname
 365
 366     def __str__(self):
 367         return self.typedef_name
 368
 369     def _create_utility_code(self, template_utility_code,
 370                              template_function_name):
 371         type_name = self.typedef_cname.replace(" ","_").replace("::","__")
 372         utility_code = template_utility_code.specialize(
 373             type     = self.typedef_cname,
 374             TypeName = type_name)
 375         function_name = template_function_name % type_name
 376         return utility_code, function_name
 377
 378     def create_to_py_utility_code(self, env):
 379         if self.typedef_is_external:
 380             if not self.to_py_utility_code:
 381                 base_type = self.typedef_base_type
 382                 if type(base_type) is CIntType:
 383                     self.to_py_function = "__Pyx_PyInt_From_" + self.specialization_name()
 384                     env.use_utility_code(TempitaUtilityCode.load(
 385                         "CIntToPy", "TypeConversion.c",
 386                         context={"TYPE": self.declaration_code(''),
 387                                  "TO_PY_FUNCTION": self.to_py_function}))
 388                     return True
 389                 elif base_type.is_float:
 390                     pass # XXX implement!
 391                 elif base_type.is_complex:
 392                     pass # XXX implement!
 393                     pass
 394             if self.to_py_utility_code:
 395                 env.use_utility_code(self.to_py_utility_code)
 396                 return True
 397         # delegation
 398         return self.typedef_base_type.create_to_py_utility_code(env)
 399
 400     def create_from_py_utility_code(self, env):
 401         if self.typedef_is_external:
 402             if not self.from_py_utility_code:
 403                 base_type = self.typedef_base_type
 404                 if type(base_type) is CIntType:
 405                     self.from_py_function = "__Pyx_PyInt_As_" + self.specialization_name()
 406                     env.use_utility_code(TempitaUtilityCode.load(
 407                         "CIntFromPy", "TypeConversion.c",
 408                         context={"TYPE": self.declaration_code(''),
 409                                  "FROM_PY_FUNCTION": self.from_py_function}))
 410                     return True
 411                 elif base_type.is_float:
 412                     pass # XXX implement!
 413                 elif base_type.is_complex:
 414                     pass # XXX implement!
 415             if self.from_py_utility_code:
 416                 env.use_utility_code(self.from_py_utility_code)
 417                 return True
 418         # delegation
 419         return self.typedef_base_type.create_from_py_utility_code(env)
 420
 421     def overflow_check_binop(self, binop, env, const_rhs=False):
 422         env.use_utility_code(UtilityCode.load("Common", "Overflow.c"))
 423         type = self.declaration_code("")
 424         name = self.specialization_name()
 425         if binop == "lshift":
 426             env.use_utility_code(TempitaUtilityCode.load(
 427                 "LeftShift", "Overflow.c",
 428                 context={'TYPE': type, 'NAME': name, 'SIGNED': self.signed}))
 429         else:
 430             if const_rhs:
 431                 binop += "_const"
 432             _load_overflow_base(env)
 433             env.use_utility_code(TempitaUtilityCode.load(
 434                 "SizeCheck", "Overflow.c",
 435                 context={'TYPE': type, 'NAME': name}))
 436             env.use_utility_code(TempitaUtilityCode.load(
 437                 "Binop", "Overflow.c",
 438                 context={'TYPE': type, 'NAME': name, 'BINOP': binop}))
 439         return "__Pyx_%s_%s_checking_overflow" % (binop, name)
 440
 441     def error_condition(self, result_code):
 442         if self.typedef_is_external:
 443             if self.exception_value:
 444                 condition = "(%s == (%s)%s)" % (
 445                     result_code, self.typedef_cname, self.exception_value)
 446                 if self.exception_check:
 447                     condition += " && PyErr_Occurred()"
 448                 return condition
 449         # delegation
 450         return self.typedef_base_type.error_condition(result_code)
 451
 452     def __getattr__(self, name):
 453         return getattr(self.typedef_base_type, name)
 454
 455     def py_type_name(self):
 456         return self.typedef_base_type.py_type_name()
 457
 458     def can_coerce_to_pyobject(self, env):
 459         return self.typedef_base_type.can_coerce_to_pyobject(env)
 460
 461
 462 class MemoryViewSliceType(PyrexType):
 463
 464     is_memoryviewslice = 1
 465
 466     has_attributes = 1
 467     scope = None
 468
 469     # These are special cased in Defnode
 470     from_py_function = None
 471     to_py_function = None
 472
 473     exception_value = None
 474     exception_check = True
 475
 476     subtypes = ['dtype']
 477
 478     def __init__(self, base_dtype, axes):
 479         """
 480         MemoryViewSliceType(base, axes)
 481
 482         Base is the C base type; axes is a list of (access, packing) strings,
 483         where access is one of 'full', 'direct' or 'ptr' and packing is one of
 484         'contig', 'strided' or 'follow'.  There is one (access, packing) tuple
 485         for each dimension.
 486
 487         the access specifiers determine whether the array data contains
 488         pointers that need to be dereferenced along that axis when
 489         retrieving/setting:
 490
 491         'direct' -- No pointers stored in this dimension.
 492         'ptr' -- Pointer stored in this dimension.
 493         'full' -- Check along this dimension, don't assume either.
 494
 495         the packing specifiers specify how the array elements are layed-out
 496         in memory.
 497
 498         'contig' -- The data are contiguous in memory along this dimension.
 499                 At most one dimension may be specified as 'contig'.
 500         'strided' -- The data aren't contiguous along this dimenison.
 501         'follow' -- Used for C/Fortran contiguous arrays, a 'follow' dimension
 502             has its stride automatically computed from extents of the other
 503             dimensions to ensure C or Fortran memory layout.
 504
 505         C-contiguous memory has 'direct' as the access spec, 'contig' as the
 506         *last* axis' packing spec and 'follow' for all other packing specs.
 507
 508         Fortran-contiguous memory has 'direct' as the access spec, 'contig' as
 509         the *first* axis' packing spec and 'follow' for all other packing
 510         specs.
 511         """
 512         import MemoryView
 513
 514         self.dtype = base_dtype
 515         self.axes = axes
 516         self.ndim = len(axes)
 517         self.flags = MemoryView.get_buf_flags(self.axes)
 518
 519         self.is_c_contig, self.is_f_contig = MemoryView.is_cf_contig(self.axes)
 520         assert not (self.is_c_contig and self.is_f_contig)
 521
 522         self.mode = MemoryView.get_mode(axes)
 523         self.writable_needed = False
 524
 525         if not self.dtype.is_fused:
 526             self.dtype_name = MemoryView.mangle_dtype_name(self.dtype)
 527
 528     def same_as_resolved_type(self, other_type):
 529         return ((other_type.is_memoryviewslice and
 530             self.dtype.same_as(other_type.dtype) and
 531             self.axes == other_type.axes) or
 532             other_type is error_type)
 533
 534     def needs_nonecheck(self):
 535         return True
 536
 537     def is_complete(self):
 538         # incomplete since the underlying struct doesn't have a cython.memoryview object.
 539         return 0
 540
 541     def declaration_code(self, entity_code,
 542             for_display = 0, dll_linkage = None, pyrex = 0):
 543         # XXX: we put these guards in for now...
 544         assert not pyrex
 545         assert not dll_linkage
 546         import MemoryView
 547         return self.base_declaration_code(
 548                 MemoryView.memviewslice_cname,
 549                 entity_code)
 550
 551     def attributes_known(self):
 552         if self.scope is None:
 553             import Symtab
 554
 555             self.scope = scope = Symtab.CClassScope(
 556                     'mvs_class_'+self.specialization_suffix(),
 557                     None,
 558                     visibility='extern')
 559
 560             scope.parent_type = self
 561             scope.directives = {}
 562
 563             scope.declare_var('_data', c_char_ptr_type, None,
 564                               cname='data', is_cdef=1)
 565
 566         return True
 567
 568     def declare_attribute(self, attribute, env, pos):
 569         import MemoryView, Options
 570
 571         scope = self.scope
 572
 573         if attribute == 'shape':
 574             scope.declare_var('shape',
 575                     c_array_type(c_py_ssize_t_type,
 576                                  Options.buffer_max_dims),
 577                     pos,
 578                     cname='shape',
 579                     is_cdef=1)
 580
 581         elif attribute == 'strides':
 582             scope.declare_var('strides',
 583                     c_array_type(c_py_ssize_t_type,
 584                                  Options.buffer_max_dims),
 585                     pos,
 586                     cname='strides',
 587                     is_cdef=1)
 588
 589         elif attribute == 'suboffsets':
 590             scope.declare_var('suboffsets',
 591                     c_array_type(c_py_ssize_t_type,
 592                                  Options.buffer_max_dims),
 593                     pos,
 594                     cname='suboffsets',
 595                     is_cdef=1)
 596
 597         elif attribute in ("copy", "copy_fortran"):
 598             ndim = len(self.axes)
 599
 600             to_axes_c = [('direct', 'contig')]
 601             to_axes_f = [('direct', 'contig')]
 602             if ndim - 1:
 603                 to_axes_c = [('direct', 'follow')]*(ndim-1) + to_axes_c
 604                 to_axes_f = to_axes_f + [('direct', 'follow')]*(ndim-1)
 605
 606             to_memview_c = MemoryViewSliceType(self.dtype, to_axes_c)
 607             to_memview_f = MemoryViewSliceType(self.dtype, to_axes_f)
 608
 609             for to_memview, cython_name in [(to_memview_c, "copy"),
 610                                             (to_memview_f, "copy_fortran")]:
 611                 entry = scope.declare_cfunction(cython_name,
 612                             CFuncType(self, [CFuncTypeArg("memviewslice", self, None)]),
 613                             pos=pos,
 614                             defining=1,
 615                             cname=MemoryView.copy_c_or_fortran_cname(to_memview))
 616
 617                 #entry.utility_code_definition = \
 618                 env.use_utility_code(MemoryView.get_copy_new_utility(pos, self, to_memview))
 619
 620             MemoryView.use_cython_array_utility_code(env)
 621
 622         elif attribute in ("is_c_contig", "is_f_contig"):
 623             # is_c_contig and is_f_contig functions
 624             for (c_or_f, cython_name) in (('c', 'is_c_contig'), ('f', 'is_f_contig')):
 625
 626                 is_contig_name = \
 627                         MemoryView.get_is_contig_func_name(c_or_f, self.ndim)
 628
 629                 cfunctype = CFuncType(
 630                         return_type=c_bint_type,
 631                         args=[CFuncTypeArg("memviewslice", self, None)],
 632                         exception_value="-1",
 633                 )
 634
 635                 entry = scope.declare_cfunction(cython_name,
 636                             cfunctype,
 637                             pos=pos,
 638                             defining=1,
 639                             cname=is_contig_name)
 640
 641                 entry.utility_code_definition = MemoryView.get_is_contig_utility(
 642                                             attribute == 'is_c_contig', self.ndim)
 643
 644         return True
 645
 646     def specialization_suffix(self):
 647         return "%s_%s" % (self.axes_to_name(), self.dtype_name)
 648
 649     def can_coerce_to_pyobject(self, env):
 650         return True
 651
 652     def check_for_null_code(self, cname):
 653         return cname + '.memview'
 654
 655     def create_from_py_utility_code(self, env):
 656         import MemoryView, Buffer
 657
 658         # We don't have 'code', so use a LazyUtilityCode with a callback.
 659         def lazy_utility_callback(code):
 660             context['dtype_typeinfo'] = Buffer.get_type_information_cname(
 661                                                           code, self.dtype)
 662             return TempitaUtilityCode.load(
 663                         "ObjectToMemviewSlice", "MemoryView_C.c", context=context)
 664
 665         env.use_utility_code(Buffer.acquire_utility_code)
 666         env.use_utility_code(MemoryView.memviewslice_init_code)
 667         env.use_utility_code(LazyUtilityCode(lazy_utility_callback))
 668
 669         if self.is_c_contig:
 670             c_or_f_flag = "__Pyx_IS_C_CONTIG"
 671         elif self.is_f_contig:
 672             c_or_f_flag = "__Pyx_IS_F_CONTIG"
 673         else:
 674             c_or_f_flag = "0"
 675
 676         suffix = self.specialization_suffix()
 677         funcname = "__Pyx_PyObject_to_MemoryviewSlice_" + suffix
 678
 679         context = dict(
 680             MemoryView.context,
 681             buf_flag = self.flags,
 682             ndim = self.ndim,
 683             axes_specs = ', '.join(self.axes_to_code()),
 684             dtype_typedecl = self.dtype.declaration_code(""),
 685             struct_nesting_depth = self.dtype.struct_nesting_depth(),
 686             c_or_f_flag = c_or_f_flag,
 687             funcname = funcname,
 688         )
 689
 690         self.from_py_function = funcname
 691         return True
 692
 693     def create_to_py_utility_code(self, env):
 694         return True
 695
 696     def get_to_py_function(self, env, obj):
 697         to_py_func, from_py_func = self.dtype_object_conversion_funcs(env)
 698         to_py_func = "(PyObject *(*)(char *)) " + to_py_func
 699         from_py_func = "(int (*)(char *, PyObject *)) " + from_py_func
 700
 701         tup = (obj.result(), self.ndim, to_py_func, from_py_func,
 702                self.dtype.is_pyobject)
 703         return "__pyx_memoryview_fromslice(%s, %s, %s, %s, %d);" % tup
 704
 705     def dtype_object_conversion_funcs(self, env):
 706         get_function = "__pyx_memview_get_%s" % self.dtype_name
 707         set_function = "__pyx_memview_set_%s" % self.dtype_name
 708
 709         context = dict(
 710             get_function = get_function,
 711             set_function = set_function,
 712         )
 713
 714         if self.dtype.is_pyobject:
 715             utility_name = "MemviewObjectToObject"
 716         else:
 717             to_py = self.dtype.create_to_py_utility_code(env)
 718             from_py = self.dtype.create_from_py_utility_code(env)
 719             if not (to_py or from_py):
 720                 return "NULL", "NULL"
 721
 722             if not self.dtype.to_py_function:
 723                 get_function = "NULL"
 724
 725             if not self.dtype.from_py_function:
 726                 set_function = "NULL"
 727
 728             utility_name = "MemviewDtypeToObject"
 729             error_condition = (self.dtype.error_condition('value') or
 730                                'PyErr_Occurred()')
 731             context.update(
 732                 to_py_function = self.dtype.to_py_function,
 733                 from_py_function = self.dtype.from_py_function,
 734                 dtype = self.dtype.declaration_code(""),
 735                 error_condition = error_condition,
 736             )
 737
 738         utility = TempitaUtilityCode.load(
 739                         utility_name, "MemoryView_C.c", context=context)
 740         env.use_utility_code(utility)
 741         return get_function, set_function
 742
 743     def axes_to_code(self):
 744         """Return a list of code constants for each axis"""
 745         import MemoryView
 746         d = MemoryView._spec_to_const
 747         return ["(%s | %s)" % (d[a], d[p]) for a, p in self.axes]
 748
 749     def axes_to_name(self):
 750         """Return an abbreviated name for our axes"""
 751         import MemoryView
 752         d = MemoryView._spec_to_abbrev
 753         return "".join(["%s%s" % (d[a], d[p]) for a, p in self.axes])
 754
 755     def error_condition(self, result_code):
 756         return "!%s.memview" % result_code
 757
 758     def __str__(self):
 759         import MemoryView
 760
 761         axes_code_list = []
 762         for idx, (access, packing) in enumerate(self.axes):
 763             flag = MemoryView.get_memoryview_flag(access, packing)
 764             if flag == "strided":
 765                 axes_code_list.append(":")
 766             else:
 767                 if flag == 'contiguous':
 768                     have_follow = [p for a, p in self.axes[idx - 1:idx + 2]
 769                                          if p == 'follow']
 770                     if have_follow or self.ndim == 1:
 771                         flag = '1'
 772
 773                 axes_code_list.append("::" + flag)
 774
 775         if self.dtype.is_pyobject:
 776             dtype_name = self.dtype.name
 777         else:
 778             dtype_name = self.dtype
 779
 780         return "%s[%s]" % (dtype_name, ", ".join(axes_code_list))
 781
 782     def specialize(self, values):
 783         """This does not validate the base type!!"""
 784         dtype = self.dtype.specialize(values)
 785         if dtype is not self.dtype:
 786             return MemoryViewSliceType(dtype, self.axes)
 787
 788         return self
 789
 790     def cast_code(self, expr_code):
 791         return expr_code
 792
 793
 794 class BufferType(BaseType):
 795     #
 796     #  Delegates most attribute lookups to the base type.
 797     #  (Anything not defined here or in the BaseType is delegated.)
 798     #
 799     # dtype            PyrexType
 800     # ndim             int
 801     # mode             str
 802     # negative_indices bool
 803     # cast             bool
 804     # is_buffer        bool
 805     # writable         bool
 806
 807     is_buffer = 1
 808     writable = True
 809
 810     subtypes = ['dtype']
 811
 812     def __init__(self, base, dtype, ndim, mode, negative_indices, cast):
 813         self.base = base
 814         self.dtype = dtype
 815         self.ndim = ndim
 816         self.buffer_ptr_type = CPtrType(dtype)
 817         self.mode = mode
 818         self.negative_indices = negative_indices
 819         self.cast = cast
 820
 821     def as_argument_type(self):
 822         return self
 823
 824     def specialize(self, values):
 825         dtype = self.dtype.specialize(values)
 826         if dtype is not self.dtype:
 827             return BufferType(self.base, dtype, self.ndim, self.mode,
 828                               self.negative_indices, self.cast)
 829         return self
 830
 831     def __getattr__(self, name):
 832         return getattr(self.base, name)
 833
 834     def __repr__(self):
 835         return "<BufferType %r>" % self.base
 836
 837     def __str__(self):
 838         # avoid ', ', as fused functions split the signature string on ', '
 839         cast_str = ''
 840         if self.cast:
 841             cast_str = ',cast=True'
 842
 843         return "%s[%s,ndim=%d%s]" % (self.base, self.dtype, self.ndim,
 844                                       cast_str)
 845
 846     def assignable_from(self, other_type):
 847         if other_type.is_buffer:
 848             return (self.same_as(other_type, compare_base=False) and
 849                     self.base.assignable_from(other_type.base))
 850
 851         return self.base.assignable_from(other_type)
 852
 853     def same_as(self, other_type, compare_base=True):
 854         if not other_type.is_buffer:
 855             return other_type.same_as(self.base)
 856
 857         return (self.dtype.same_as(other_type.dtype) and
 858                 self.ndim == other_type.ndim and
 859                 self.mode == other_type.mode and
 860                 self.cast == other_type.cast and
 861                 (not compare_base or self.base.same_as(other_type.base)))
 862
 863
 864 class PyObjectType(PyrexType):
 865     #
 866     #  Base class for all Python object types (reference-counted).
 867     #
 868     #  buffer_defaults  dict or None     Default options for bu
 869
 870     name = "object"
 871     is_pyobject = 1
 872     default_value = "0"
 873     buffer_defaults = None
 874     is_extern = False
 875     is_subclassed = False
 876     is_gc_simple = False
 877
 878     def __str__(self):
 879         return "Python object"
 880
 881     def __repr__(self):
 882         return "<PyObjectType>"
 883
 884     def can_coerce_to_pyobject(self, env):
 885         return True
 886
 887     def default_coerced_ctype(self):
 888         """The default C type that this Python type coerces to, or None."""
 889         return None
 890
 891     def assignable_from(self, src_type):
 892         # except for pointers, conversion will be attempted
 893         return not src_type.is_ptr or src_type.is_string or src_type.is_pyunicode_ptr
 894
 895     def declaration_code(self, entity_code,
 896             for_display = 0, dll_linkage = None, pyrex = 0):
 897         if pyrex or for_display:
 898             base_code = "object"
 899         else:
 900             base_code = public_decl("PyObject", dll_linkage)
 901             entity_code = "*%s" % entity_code
 902         return self.base_declaration_code(base_code, entity_code)
 903
 904     def as_pyobject(self, cname):
 905         if (not self.is_complete()) or self.is_extension_type:
 906             return "(PyObject *)" + cname
 907         else:
 908             return cname
 909
 910     def py_type_name(self):
 911         return "object"
 912
 913     def __lt__(self, other):
 914         """
 915         Make sure we sort highest, as instance checking on py_type_name
 916         ('object') is always true
 917         """
 918         return False
 919
 920     def global_init_code(self, entry, code):
 921         code.put_init_var_to_py_none(entry, nanny=False)
 922
 923     def check_for_null_code(self, cname):
 924         return cname
 925
 926
 927 builtin_types_that_cannot_create_refcycles = set([
 928     'bool', 'int', 'long', 'float', 'complex',
 929     'bytearray', 'bytes', 'unicode', 'str', 'basestring'
 930 ])
 931
 932
 933 class BuiltinObjectType(PyObjectType):
 934     #  objstruct_cname  string           Name of PyObject struct
 935
 936     is_builtin_type = 1
 937     has_attributes = 1
 938     base_type = None
 939     module_name = '__builtin__'
 940
 941     # fields that let it look like an extension type
 942     vtabslot_cname = None
 943     vtabstruct_cname = None
 944     vtabptr_cname = None
 945     typedef_flag = True
 946     is_external = True
 947
 948     def __init__(self, name, cname, objstruct_cname=None):
 949         self.name = name
 950         self.cname = cname
 951         self.typeptr_cname = "(&%s)" % cname
 952         self.objstruct_cname = objstruct_cname
 953         self.is_gc_simple = name in builtin_types_that_cannot_create_refcycles
 954
 955     def set_scope(self, scope):
 956         self.scope = scope
 957         if scope:
 958             scope.parent_type = self
 959
 960     def __str__(self):
 961         return "%s object" % self.name
 962
 963     def __repr__(self):
 964         return "<%s>"% self.cname
 965
 966     def default_coerced_ctype(self):
 967         if self.name in ('bytes', 'bytearray'):
 968             return c_char_ptr_type
 969         elif self.name == 'bool':
 970             return c_bint_type
 971         elif self.name == 'float':
 972             return c_double_type
 973         return None
 974
 975     def assignable_from(self, src_type):
 976         if isinstance(src_type, BuiltinObjectType):
 977             if self.name == 'basestring':
 978                 return src_type.name in ('str', 'unicode', 'basestring')
 979             else:
 980                 return src_type.name == self.name
 981         elif src_type.is_extension_type:
 982             # FIXME: This is an ugly special case that we currently
 983             # keep supporting.  It allows users to specify builtin
 984             # types as external extension types, while keeping them
 985             # compatible with the real builtin types.  We already
 986             # generate a warning for it.  Big TODO: remove!
 987             return (src_type.module_name == '__builtin__' and
 988                     src_type.name == self.name)
 989         else:
 990             return True
 991
 992     def typeobj_is_available(self):
 993         return True
 994
 995     def attributes_known(self):
 996         return True
 997
 998     def subtype_of(self, type):
 999         return type.is_pyobject and type.assignable_from(self)
1000
1001     def type_check_function(self, exact=True):
1002         type_name = self.name
1003         if type_name == 'str':
1004             type_check = 'PyString_Check'
1005         elif type_name == 'basestring':
1006             type_check = '__Pyx_PyBaseString_Check'
1007         elif type_name == 'bytearray':
1008             type_check = 'PyByteArray_Check'
1009         elif type_name == 'frozenset':
1010             type_check = 'PyFrozenSet_Check'
1011         else:
1012             type_check = 'Py%s_Check' % type_name.capitalize()
1013         if exact and type_name not in ('bool', 'slice'):
1014             type_check += 'Exact'
1015         return type_check
1016
1017     def isinstance_code(self, arg):
1018         return '%s(%s)' % (self.type_check_function(exact=False), arg)
1019
1020     def type_test_code(self, arg, notnone=False, exact=True):
1021         type_check = self.type_check_function(exact=exact)
1022         check = 'likely(%s(%s))' % (type_check, arg)
1023         if not notnone:
1024             check += '||((%s) == Py_None)' % arg
1025         if self.name == 'basestring':
1026             name = '(PY_MAJOR_VERSION < 3 ? "basestring" : "str")'
1027             space_for_name = 16
1028         else:
1029             name = '"%s"' % self.name
1030             # avoid wasting too much space but limit number of different format strings
1031             space_for_name = (len(self.name) // 16 + 1) * 16
1032         error = '(PyErr_Format(PyExc_TypeError, "Expected %%.%ds, got %%.200s", %s, Py_TYPE(%s)->tp_name), 0)' % (
1033             space_for_name, name, arg)
1034         return check + '||' + error
1035
1036     def declaration_code(self, entity_code,
1037             for_display = 0, dll_linkage = None, pyrex = 0):
1038         if pyrex or for_display:
1039             base_code = self.name
1040         else:
1041             base_code = public_decl("PyObject", dll_linkage)
1042             entity_code = "*%s" % entity_code
1043         return self.base_declaration_code(base_code, entity_code)
1044
1045     def cast_code(self, expr_code, to_object_struct = False):
1046         return "((%s*)%s)" % (
1047             to_object_struct and self.objstruct_cname or "PyObject", # self.objstruct_cname may be None
1048             expr_code)
1049
1050     def py_type_name(self):
1051         return self.name
1052
1053
1054
1055 class PyExtensionType(PyObjectType):
1056     #
1057     #  A Python extension type.
1058     #
1059     #  name             string
1060     #  scope            CClassScope      Attribute namespace
1061     #  visibility       string
1062     #  typedef_flag     boolean
1063     #  base_type        PyExtensionType or None
1064     #  module_name      string or None   Qualified name of defining module
1065     #  objstruct_cname  string           Name of PyObject struct
1066     #  objtypedef_cname string           Name of PyObject struct typedef
1067     #  typeobj_cname    string or None   C code fragment referring to type object
1068     #  typeptr_cname    string or None   Name of pointer to external type object
1069     #  vtabslot_cname   string           Name of C method table member
1070     #  vtabstruct_cname string           Name of C method table struct
1071     #  vtabptr_cname    string           Name of pointer to C method table
1072     #  vtable_cname     string           Name of C method table definition
1073     #  defered_declarations [thunk]      Used to declare class hierarchies in order
1074
1075     is_extension_type = 1
1076     has_attributes = 1
1077
1078     objtypedef_cname = None
1079
1080     def __init__(self, name, typedef_flag, base_type, is_external=0):
1081         self.name = name
1082         self.scope = None
1083         self.typedef_flag = typedef_flag
1084         if base_type is not None:
1085             base_type.is_subclassed = True
1086         self.base_type = base_type
1087         self.module_name = None
1088         self.objstruct_cname = None
1089         self.typeobj_cname = None
1090         self.typeptr_cname = None
1091         self.vtabslot_cname = None
1092         self.vtabstruct_cname = None
1093         self.vtabptr_cname = None
1094         self.vtable_cname = None
1095         self.is_external = is_external
1096         self.defered_declarations = []
1097
1098     def set_scope(self, scope):
1099         self.scope = scope
1100         if scope:
1101             scope.parent_type = self
1102
1103     def needs_nonecheck(self):
1104         return True
1105
1106     def subtype_of_resolved_type(self, other_type):
1107         if other_type.is_extension_type or other_type.is_builtin_type:
1108             return self is other_type or (
1109                 self.base_type and self.base_type.subtype_of(other_type))
1110         else:
1111             return other_type is py_object_type
1112
1113     def typeobj_is_available(self):
1114         # Do we have a pointer to the type object?
1115         return self.typeptr_cname
1116
1117     def typeobj_is_imported(self):
1118         # If we don't know the C name of the type object but we do
1119         # know which module it's defined in, it will be imported.
1120         return self.typeobj_cname is None and self.module_name is not None
1121
1122     def assignable_from(self, src_type):
1123         if self == src_type:
1124             return True
1125         if isinstance(src_type, PyExtensionType):
1126             if src_type.base_type is not None:
1127                 return self.assignable_from(src_type.base_type)
1128         if isinstance(src_type, BuiltinObjectType):
1129             # FIXME: This is an ugly special case that we currently
1130             # keep supporting.  It allows users to specify builtin
1131             # types as external extension types, while keeping them
1132             # compatible with the real builtin types.  We already
1133             # generate a warning for it.  Big TODO: remove!
1134             return (self.module_name == '__builtin__' and
1135                     self.name == src_type.name)
1136         return False
1137
1138     def declaration_code(self, entity_code,
1139             for_display = 0, dll_linkage = None, pyrex = 0, deref = 0):
1140         if pyrex or for_display:
1141             base_code = self.name
1142         else:
1143             if self.typedef_flag:
1144                 objstruct = self.objstruct_cname
1145             else:
1146                 objstruct = "struct %s" % self.objstruct_cname
1147             base_code = public_decl(objstruct, dll_linkage)
1148             if deref:
1149                 assert not entity_code
1150             else:
1151                 entity_code = "*%s" % entity_code
1152         return self.base_declaration_code(base_code, entity_code)
1153
1154     def type_test_code(self, py_arg, notnone=False):
1155
1156         none_check = "((%s) == Py_None)" % py_arg
1157         type_check = "likely(__Pyx_TypeTest(%s, %s))" % (
1158             py_arg, self.typeptr_cname)
1159         if notnone:
1160             return type_check
1161         else:
1162             return "likely(%s || %s)" % (none_check, type_check)
1163
1164     def attributes_known(self):
1165         return self.scope is not None
1166
1167     def __str__(self):
1168         return self.name
1169
1170     def __repr__(self):
1171         return "<PyExtensionType %s%s>" % (self.scope.class_name,
1172             ("", " typedef")[self.typedef_flag])
1173
1174     def py_type_name(self):
1175         if not self.module_name:
1176             return self.name
1177
1178         return "__import__(%r, None, None, ['']).%s" % (self.module_name,
1179                                                         self.name)
1180
1181 class CType(PyrexType):
1182     #
1183     #  Base class for all C types (non-reference-counted).
1184     #
1185     #  to_py_function     string     C function for converting to Python object
1186     #  from_py_function   string     C function for constructing from Python object
1187     #
1188
1189     to_py_function = None
1190     from_py_function = None
1191     exception_value = None
1192     exception_check = 1
1193
1194     def create_to_py_utility_code(self, env):
1195         return self.to_py_function is not None
1196
1197     def create_from_py_utility_code(self, env):
1198         return self.from_py_function is not None
1199
1200     def can_coerce_to_pyobject(self, env):
1201         return self.create_to_py_utility_code(env)
1202
1203     def error_condition(self, result_code):
1204         conds = []
1205         if self.is_string or self.is_pyunicode_ptr:
1206             conds.append("(!%s)" % result_code)
1207         elif self.exception_value is not None:
1208             conds.append("(%s == (%s)%s)" % (result_code, self.sign_and_name(), self.exception_value))
1209         if self.exception_check:
1210             conds.append("PyErr_Occurred()")
1211         if len(conds) > 0:
1212             return " && ".join(conds)
1213         else:
1214             return 0
1215
1216
1217 class CConstType(BaseType):
1218
1219     is_const = 1
1220
1221     def __init__(self, const_base_type):
1222         self.const_base_type = const_base_type
1223         if const_base_type.has_attributes and const_base_type.scope is not None:
1224             import Symtab
1225             self.scope = Symtab.CConstScope(const_base_type.scope)
1226
1227     def __repr__(self):
1228         return "<CConstType %s>" % repr(self.const_base_type)
1229
1230     def __str__(self):
1231         return self.declaration_code("", for_display=1)
1232
1233     def declaration_code(self, entity_code,
1234             for_display = 0, dll_linkage = None, pyrex = 0):
1235         return self.const_base_type.declaration_code("const %s" % entity_code, for_display, dll_linkage, pyrex)
1236
1237     def specialize(self, values):
1238         base_type = self.const_base_type.specialize(values)
1239         if base_type == self.const_base_type:
1240             return self
1241         else:
1242             return CConstType(base_type)
1243
1244     def deduce_template_params(self, actual):
1245         return self.const_base_type.deduce_template_params(actual)
1246
1247     def create_to_py_utility_code(self, env):
1248         if self.const_base_type.create_to_py_utility_code(env):
1249             self.to_py_function = self.const_base_type.to_py_function
1250             return True
1251
1252     def __getattr__(self, name):
1253         return getattr(self.const_base_type, name)
1254
1255
1256 class FusedType(CType):
1257     """
1258     Represents a Fused Type. All it needs to do is keep track of the types
1259     it aggregates, as it will be replaced with its specific version wherever
1260     needed.
1261
1262     See http://wiki.cython.org/enhancements/fusedtypes
1263
1264     types           [PyrexType]             is the list of types to be fused
1265     name            str                     the name of the ctypedef
1266     """
1267
1268     is_fused = 1
1269     exception_check = 0
1270
1271     def __init__(self, types, name=None):
1272         self.types = types
1273         self.name = name
1274
1275     def declaration_code(self, entity_code, for_display = 0,
1276                          dll_linkage = None, pyrex = 0):
1277         if pyrex or for_display:
1278             return self.name
1279
1280         raise Exception("This may never happen, please report a bug")
1281
1282     def __repr__(self):
1283         return 'FusedType(name=%r)' % self.name
1284
1285     def specialize(self, values):
1286         return values[self]
1287
1288     def get_fused_types(self, result=None, seen=None):
1289         if result is None:
1290             return [self]
1291
1292         if self not in seen:
1293             result.append(self)
1294             seen.add(self)
1295
1296
1297 class CVoidType(CType):
1298     #
1299     #   C "void" type
1300     #
1301
1302     is_void = 1
1303
1304     def __repr__(self):
1305         return "<CVoidType>"
1306
1307     def declaration_code(self, entity_code,
1308             for_display = 0, dll_linkage = None, pyrex = 0):
1309         if pyrex or for_display:
1310             base_code = "void"
1311         else:
1312             base_code = public_decl("void", dll_linkage)
1313         return self.base_declaration_code(base_code, entity_code)
1314
1315     def is_complete(self):
1316         return 0
1317
1318 class InvisibleVoidType(CVoidType):
1319     #
1320     #   For use with C++ constructors and destructors return types.
1321     #   Acts like void, but does not print out a declaration.
1322     #
1323     def declaration_code(self, entity_code,
1324             for_display = 0, dll_linkage = None, pyrex = 0):
1325         if pyrex or for_display:
1326             base_code = "[void]"
1327         else:
1328             base_code = public_decl("", dll_linkage)
1329         return self.base_declaration_code(base_code, entity_code)
1330
1331
1332 class CNumericType(CType):
1333     #
1334     #   Base class for all C numeric types.
1335     #
1336     #   rank      integer     Relative size
1337     #   signed    integer     0 = unsigned, 1 = unspecified, 2 = explicitly signed
1338     #
1339
1340     is_numeric = 1
1341     default_value = "0"
1342     has_attributes = True
1343     scope = None
1344
1345     sign_words = ("unsigned ", "", "signed ")
1346
1347     def __init__(self, rank, signed = 1):
1348         self.rank = rank
1349         self.signed = signed
1350
1351     def sign_and_name(self):
1352         s = self.sign_words[self.signed]
1353         n = rank_to_type_name[self.rank]
1354         return s + n
1355
1356     def __repr__(self):
1357         return "<CNumericType %s>" % self.sign_and_name()
1358
1359     def declaration_code(self, entity_code,
1360             for_display = 0, dll_linkage = None, pyrex = 0):
1361         type_name = self.sign_and_name()
1362         if pyrex or for_display:
1363             base_code = type_name.replace('PY_LONG_LONG', 'long long')
1364         else:
1365             base_code = public_decl(type_name, dll_linkage)
1366         return self.base_declaration_code(base_code, entity_code)
1367
1368     def attributes_known(self):
1369         if self.scope is None:
1370             import Symtab
1371             self.scope = scope = Symtab.CClassScope(
1372                     '',
1373                     None,
1374                     visibility="extern")
1375             scope.parent_type = self
1376             scope.directives = {}
1377             scope.declare_cfunction(
1378                     "conjugate",
1379                     CFuncType(self, [CFuncTypeArg("self", self, None)], nogil=True),
1380                     pos=None,
1381                     defining=1,
1382                     cname=" ")
1383         return True
1384
1385     def __lt__(self, other):
1386         """Sort based on rank, preferring signed over unsigned"""
1387         if other.is_numeric:
1388             return self.rank > other.rank and self.signed >= other.signed
1389
1390         # Prefer numeric types over others
1391         return True
1392
1393     def py_type_name(self):
1394         if self.rank <= 4:
1395             return "(int, long)"
1396         return "float"
1397
1398
1399 class ForbidUseClass:
1400     def __repr__(self):
1401         raise RuntimeError()
1402     def __str__(self):
1403         raise RuntimeError()
1404 ForbidUse = ForbidUseClass()
1405
1406
1407 class CIntType(CNumericType):
1408
1409     is_int = 1
1410     typedef_flag = 0
1411     to_py_function = None
1412     from_py_function = None
1413     exception_value = -1
1414
1415     def create_to_py_utility_code(self, env):
1416         if type(self).to_py_function is None:
1417             self.to_py_function = "__Pyx_PyInt_From_" + self.specialization_name()
1418             env.use_utility_code(TempitaUtilityCode.load(
1419                 "CIntToPy", "TypeConversion.c",
1420                 context={"TYPE": self.declaration_code(''),
1421                          "TO_PY_FUNCTION": self.to_py_function}))
1422         return True
1423
1424     def create_from_py_utility_code(self, env):
1425         if type(self).from_py_function is None:
1426             self.from_py_function = "__Pyx_PyInt_As_" + self.specialization_name()
1427             env.use_utility_code(TempitaUtilityCode.load(
1428                 "CIntFromPy", "TypeConversion.c",
1429                 context={"TYPE": self.declaration_code(''),
1430                          "FROM_PY_FUNCTION": self.from_py_function}))
1431         return True
1432
1433     def get_to_py_type_conversion(self):
1434         if self.rank < list(rank_to_type_name).index('int'):
1435             # This assumes sizeof(short) < sizeof(int)
1436             return "PyInt_FromLong"
1437         else:
1438             # Py{Int|Long}_From[Unsigned]Long[Long]
1439             Prefix = "Int"
1440             SignWord = ""
1441             TypeName = "Long"
1442             if not self.signed:
1443                 Prefix = "Long"
1444                 SignWord = "Unsigned"
1445             if self.rank >= list(rank_to_type_name).index('PY_LONG_LONG'):
1446                 Prefix = "Long"
1447                 TypeName = "LongLong"
1448             return "Py%s_From%s%s" % (Prefix, SignWord, TypeName)
1449
1450     def get_from_py_type_conversion(self):
1451         type_name = rank_to_type_name[self.rank]
1452         type_name = type_name.replace("PY_LONG_LONG", "long long")
1453         TypeName = type_name.title().replace(" ", "")
1454         SignWord = self.sign_words[self.signed].strip().title()
1455         if self.rank >= list(rank_to_type_name).index('long'):
1456             utility_code = c_long_from_py_function
1457         else:
1458             utility_code = c_int_from_py_function
1459         utility_code.specialize(self,
1460                                 SignWord=SignWord,
1461                                 TypeName=TypeName)
1462         func_name = "__Pyx_PyInt_As%s%s" % (SignWord, TypeName)
1463         return func_name
1464
1465     def assignable_from_resolved_type(self, src_type):
1466         return src_type.is_int or src_type.is_enum or src_type is error_type
1467
1468     def invalid_value(self):
1469         if rank_to_type_name[int(self.rank)] == 'char':
1470             return "'?'"
1471         else:
1472             # We do not really know the size of the type, so return
1473             # a 32-bit literal and rely on casting to final type. It will
1474             # be negative for signed ints, which is good.
1475             return "0xbad0bad0"
1476
1477     def overflow_check_binop(self, binop, env, const_rhs=False):
1478         env.use_utility_code(UtilityCode.load("Common", "Overflow.c"))
1479         type = self.declaration_code("")
1480         name = self.specialization_name()
1481         if binop == "lshift":
1482             env.use_utility_code(TempitaUtilityCode.load(
1483                 "LeftShift", "Overflow.c",
1484                 context={'TYPE': type, 'NAME': name, 'SIGNED': self.signed}))
1485         else:
1486             if const_rhs:
1487                 binop += "_const"
1488             if type in ('int', 'long', 'long long'):
1489                 env.use_utility_code(TempitaUtilityCode.load(
1490                     "BaseCaseSigned", "Overflow.c",
1491                     context={'INT': type, 'NAME': name}))
1492             elif type in ('unsigned int', 'unsigned long', 'unsigned long long'):
1493                 env.use_utility_code(TempitaUtilityCode.load(
1494                     "BaseCaseUnsigned", "Overflow.c",
1495                     context={'UINT': type, 'NAME': name}))
1496             elif self.rank <= 1:
1497                 # sizeof(short) < sizeof(int)
1498                 return "__Pyx_%s_%s_no_overflow" % (binop, name)
1499             else:
1500                 _load_overflow_base(env)
1501                 env.use_utility_code(TempitaUtilityCode.load(
1502                     "SizeCheck", "Overflow.c",
1503                     context={'TYPE': type, 'NAME': name}))
1504                 env.use_utility_code(TempitaUtilityCode.load(
1505                     "Binop", "Overflow.c",
1506                     context={'TYPE': type, 'NAME': name, 'BINOP': binop}))
1507         return "__Pyx_%s_%s_checking_overflow" % (binop, name)
1508
1509 def _load_overflow_base(env):
1510     env.use_utility_code(UtilityCode.load("Common", "Overflow.c"))
1511     for type in ('int', 'long', 'long long'):
1512         env.use_utility_code(TempitaUtilityCode.load(
1513             "BaseCaseSigned", "Overflow.c",
1514             context={'INT': type, 'NAME': type.replace(' ', '_')}))
1515     for type in ('unsigned int', 'unsigned long', 'unsigned long long'):
1516         env.use_utility_code(TempitaUtilityCode.load(
1517             "BaseCaseUnsigned", "Overflow.c",
1518             context={'UINT': type, 'NAME': type.replace(' ', '_')}))
1519
1520
1521 class CAnonEnumType(CIntType):
1522
1523     is_enum = 1
1524
1525     def sign_and_name(self):
1526         return 'int'
1527
1528
1529 class CReturnCodeType(CIntType):
1530
1531     to_py_function = "__Pyx_Owned_Py_None"
1532
1533     is_returncode = True
1534     exception_check = False
1535
1536
1537 class CBIntType(CIntType):
1538
1539     to_py_function = "__Pyx_PyBool_FromLong"
1540     from_py_function = "__Pyx_PyObject_IsTrue"
1541     exception_check = 1 # for C++ bool
1542
1543     def declaration_code(self, entity_code,
1544             for_display = 0, dll_linkage = None, pyrex = 0):
1545         if pyrex or for_display:
1546             base_code = 'bool'
1547         else:
1548             base_code = public_decl('int', dll_linkage)
1549         return self.base_declaration_code(base_code, entity_code)
1550
1551     def __repr__(self):
1552         return "<CNumericType bint>"
1553
1554     def __str__(self):
1555         return 'bint'
1556
1557     def py_type_name(self):
1558         return "bool"
1559
1560
1561 class CPyUCS4IntType(CIntType):
1562     # Py_UCS4
1563
1564     is_unicode_char = True
1565
1566     # Py_UCS4 coerces from and to single character unicode strings (or
1567     # at most two characters on 16bit Unicode builds), but we also
1568     # allow Python integers as input.  The value range for Py_UCS4
1569     # is 0..1114111, which is checked when converting from an integer
1570     # value.
1571
1572     to_py_function = "PyUnicode_FromOrdinal"
1573     from_py_function = "__Pyx_PyObject_AsPy_UCS4"
1574
1575     def create_from_py_utility_code(self, env):
1576         env.use_utility_code(UtilityCode.load_cached("ObjectAsUCS4", "TypeConversion.c"))
1577         return True
1578
1579     def sign_and_name(self):
1580         return "Py_UCS4"
1581
1582
1583 class CPyUnicodeIntType(CIntType):
1584     # Py_UNICODE
1585
1586     is_unicode_char = True
1587
1588     # Py_UNICODE coerces from and to single character unicode strings,
1589     # but we also allow Python integers as input.  The value range for
1590     # Py_UNICODE is 0..1114111, which is checked when converting from
1591     # an integer value.
1592
1593     to_py_function = "PyUnicode_FromOrdinal"
1594     from_py_function = "__Pyx_PyObject_AsPy_UNICODE"
1595
1596     def create_from_py_utility_code(self, env):
1597         env.use_utility_code(UtilityCode.load_cached("ObjectAsPyUnicode", "TypeConversion.c"))
1598         return True
1599
1600     def sign_and_name(self):
1601         return "Py_UNICODE"
1602
1603
1604 class CPyHashTType(CIntType):
1605
1606     to_py_function = "__Pyx_PyInt_FromHash_t"
1607     from_py_function = "__Pyx_PyInt_AsHash_t"
1608
1609     def sign_and_name(self):
1610         return "Py_hash_t"
1611
1612 class CPySSizeTType(CIntType):
1613
1614     to_py_function = "PyInt_FromSsize_t"
1615     from_py_function = "__Pyx_PyIndex_AsSsize_t"
1616
1617     def sign_and_name(self):
1618         return "Py_ssize_t"
1619
1620 class CSSizeTType(CIntType):
1621
1622     to_py_function = "PyInt_FromSsize_t"
1623     from_py_function = "PyInt_AsSsize_t"
1624
1625     def sign_and_name(self):
1626         return "Py_ssize_t"
1627
1628 class CSizeTType(CIntType):
1629
1630     to_py_function = "__Pyx_PyInt_FromSize_t"
1631
1632     def sign_and_name(self):
1633         return "size_t"
1634
1635 class CPtrdiffTType(CIntType):
1636
1637     def sign_and_name(self):
1638         return "ptrdiff_t"
1639
1640
1641 class CFloatType(CNumericType):
1642
1643     is_float = 1
1644     to_py_function = "PyFloat_FromDouble"
1645     from_py_function = "__pyx_PyFloat_AsDouble"
1646
1647     exception_value = -1
1648
1649     def __init__(self, rank, math_h_modifier = ''):
1650         CNumericType.__init__(self, rank, 1)
1651         self.math_h_modifier = math_h_modifier
1652         if rank == RANK_FLOAT:
1653             self.from_py_function = "__pyx_PyFloat_AsFloat"
1654
1655     def assignable_from_resolved_type(self, src_type):
1656         return (src_type.is_numeric and not src_type.is_complex) or src_type is error_type
1657
1658     def invalid_value(self):
1659         return Naming.PYX_NAN
1660
1661 class CComplexType(CNumericType):
1662
1663     is_complex = 1
1664     to_py_function = "__pyx_PyComplex_FromComplex"
1665     has_attributes = 1
1666     scope = None
1667
1668     def __init__(self, real_type):
1669         while real_type.is_typedef and not real_type.typedef_is_external:
1670             real_type = real_type.typedef_base_type
1671         if real_type.is_typedef and real_type.typedef_is_external:
1672             # The below is not actually used: Coercions are currently disabled
1673             # so that complex types of external types can not be created
1674             self.funcsuffix = "_%s" % real_type.specialization_name()
1675         elif hasattr(real_type, 'math_h_modifier'):
1676             self.funcsuffix = real_type.math_h_modifier
1677         else:
1678             self.funcsuffix = "_%s" % real_type.specialization_name()
1679
1680         self.real_type = real_type
1681         CNumericType.__init__(self, real_type.rank + 0.5, real_type.signed)
1682         self.binops = {}
1683         self.from_parts = "%s_from_parts" % self.specialization_name()
1684         self.default_value = "%s(0, 0)" % self.from_parts
1685
1686     def __eq__(self, other):
1687         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1688             return self.real_type == other.real_type
1689         else:
1690             return False
1691
1692     def __ne__(self, other):
1693         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1694             return self.real_type != other.real_type
1695         else:
1696             return True
1697
1698     def __lt__(self, other):
1699         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1700             return self.real_type < other.real_type
1701         else:
1702             # this is arbitrary, but it makes sure we always have
1703             # *some* kind of order
1704             return False
1705
1706     def __hash__(self):
1707         return ~hash(self.real_type)
1708
1709     def declaration_code(self, entity_code,
1710             for_display = 0, dll_linkage = None, pyrex = 0):
1711         if pyrex or for_display:
1712             real_code = self.real_type.declaration_code("", for_display, dll_linkage, pyrex)
1713             base_code = "%s complex" % real_code
1714         else:
1715             base_code = public_decl(self.sign_and_name(), dll_linkage)
1716         return self.base_declaration_code(base_code, entity_code)
1717
1718     def sign_and_name(self):
1719         real_type_name = self.real_type.specialization_name()
1720         real_type_name = real_type_name.replace('long__double','long_double')
1721         real_type_name = real_type_name.replace('PY_LONG_LONG','long_long')
1722         return Naming.type_prefix + real_type_name + "_complex"
1723
1724     def assignable_from(self, src_type):
1725         # Temporary hack/feature disabling, see #441
1726         if (not src_type.is_complex and src_type.is_numeric and src_type.is_typedef
1727             and src_type.typedef_is_external):
1728              return False
1729         else:
1730             return super(CComplexType, self).assignable_from(src_type)
1731
1732     def assignable_from_resolved_type(self, src_type):
1733         return (src_type.is_complex and self.real_type.assignable_from_resolved_type(src_type.real_type)
1734                     or src_type.is_numeric and self.real_type.assignable_from_resolved_type(src_type)
1735                     or src_type is error_type)
1736
1737     def attributes_known(self):
1738         if self.scope is None:
1739             import Symtab
1740             self.scope = scope = Symtab.CClassScope(
1741                     '',
1742                     None,
1743                     visibility="extern")
1744             scope.parent_type = self
1745             scope.directives = {}
1746             scope.declare_var("real", self.real_type, None, cname="real", is_cdef=True)
1747             scope.declare_var("imag", self.real_type, None, cname="imag", is_cdef=True)
1748             scope.declare_cfunction(
1749                     "conjugate",
1750                     CFuncType(self, [CFuncTypeArg("self", self, None)], nogil=True),
1751                     pos=None,
1752                     defining=1,
1753                     cname="__Pyx_c_conj%s" % self.funcsuffix)
1754
1755         return True
1756
1757     def create_declaration_utility_code(self, env):
1758         # This must always be run, because a single CComplexType instance can be shared
1759         # across multiple compilations (the one created in the module scope)
1760         env.use_utility_code(complex_header_utility_code)
1761         env.use_utility_code(complex_real_imag_utility_code)
1762         for utility_code in (complex_type_utility_code,
1763                              complex_from_parts_utility_code,
1764                              complex_arithmetic_utility_code):
1765             env.use_utility_code(
1766                 utility_code.specialize(
1767                     self,
1768                     real_type = self.real_type.declaration_code(''),
1769                     m = self.funcsuffix,
1770                     is_float = self.real_type.is_float))
1771         return True
1772
1773     def create_to_py_utility_code(self, env):
1774         env.use_utility_code(complex_real_imag_utility_code)
1775         env.use_utility_code(complex_to_py_utility_code)
1776         return True
1777
1778     def create_from_py_utility_code(self, env):
1779         self.real_type.create_from_py_utility_code(env)
1780
1781         for utility_code in (complex_from_parts_utility_code,
1782                              complex_from_py_utility_code):
1783             env.use_utility_code(
1784                 utility_code.specialize(
1785                     self,
1786                     real_type = self.real_type.declaration_code(''),
1787                     m = self.funcsuffix,
1788                     is_float = self.real_type.is_float))
1789         self.from_py_function = "__Pyx_PyComplex_As_" + self.specialization_name()
1790         return True
1791
1792     def lookup_op(self, nargs, op):
1793         try:
1794             return self.binops[nargs, op]
1795         except KeyError:
1796             pass
1797         try:
1798             op_name = complex_ops[nargs, op]
1799             self.binops[nargs, op] = func_name = "__Pyx_c_%s%s" % (op_name, self.funcsuffix)
1800             return func_name
1801         except KeyError:
1802             return None
1803
1804     def unary_op(self, op):
1805         return self.lookup_op(1, op)
1806
1807     def binary_op(self, op):
1808         return self.lookup_op(2, op)
1809
1810     def py_type_name(self):
1811         return "complex"
1812
1813     def cast_code(self, expr_code):
1814         return expr_code
1815
1816 complex_ops = {
1817     (1, '-'): 'neg',
1818     (1, 'zero'): 'is_zero',
1819     (2, '+'): 'sum',
1820     (2, '-'): 'diff',
1821     (2, '*'): 'prod',
1822     (2, '/'): 'quot',
1823     (2, '=='): 'eq',
1824 }
1825
1826 complex_header_utility_code = UtilityCode(
1827 proto_block='h_code',
1828 proto="""
1829 #if !defined(CYTHON_CCOMPLEX)
1830   #if defined(__cplusplus)
1831     #define CYTHON_CCOMPLEX 1
1832   #elif defined(_Complex_I)
1833     #define CYTHON_CCOMPLEX 1
1834   #else
1835     #define CYTHON_CCOMPLEX 0
1836   #endif
1837 #endif
1838
1839 #if CYTHON_CCOMPLEX
1840   #ifdef __cplusplus
1841     #include <complex>
1842   #else
1843     #include <complex.h>
1844   #endif
1845 #endif
1846
1847 #if CYTHON_CCOMPLEX && !defined(__cplusplus) && defined(__sun__) && defined(__GNUC__)
1848   #undef _Complex_I
1849   #define _Complex_I 1.0fj
1850 #endif
1851 """)
1852
1853 complex_real_imag_utility_code = UtilityCode(
1854 proto="""
1855 #if CYTHON_CCOMPLEX
1856   #ifdef __cplusplus
1857     #define __Pyx_CREAL(z) ((z).real())
1858     #define __Pyx_CIMAG(z) ((z).imag())
1859   #else
1860     #define __Pyx_CREAL(z) (__real__(z))
1861     #define __Pyx_CIMAG(z) (__imag__(z))
1862   #endif
1863 #else
1864     #define __Pyx_CREAL(z) ((z).real)
1865     #define __Pyx_CIMAG(z) ((z).imag)
1866 #endif
1867
1868 #if (defined(_WIN32) || defined(__clang__)) && defined(__cplusplus) && CYTHON_CCOMPLEX
1869     #define __Pyx_SET_CREAL(z,x) ((z).real(x))
1870     #define __Pyx_SET_CIMAG(z,y) ((z).imag(y))
1871 #else
1872     #define __Pyx_SET_CREAL(z,x) __Pyx_CREAL(z) = (x)
1873     #define __Pyx_SET_CIMAG(z,y) __Pyx_CIMAG(z) = (y)
1874 #endif
1875 """)
1876
1877 complex_type_utility_code = UtilityCode(
1878 proto_block='complex_type_declarations',
1879 proto="""
1880 #if CYTHON_CCOMPLEX
1881   #ifdef __cplusplus
1882     typedef ::std::complex< %(real_type)s > %(type_name)s;
1883   #else
1884     typedef %(real_type)s _Complex %(type_name)s;
1885   #endif
1886 #else
1887     typedef struct { %(real_type)s real, imag; } %(type_name)s;
1888 #endif
1889 """)
1890
1891 complex_from_parts_utility_code = UtilityCode(
1892 proto_block='utility_code_proto',
1893 proto="""
1894 static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s, %(real_type)s);
1895 """,
1896 impl="""
1897 #if CYTHON_CCOMPLEX
1898   #ifdef __cplusplus
1899     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1900       return ::std::complex< %(real_type)s >(x, y);
1901     }
1902   #else
1903     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1904       return x + y*(%(type)s)_Complex_I;
1905     }
1906   #endif
1907 #else
1908     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1909       %(type)s z;
1910       z.real = x;
1911       z.imag = y;
1912       return z;
1913     }
1914 #endif
1915 """)
1916
1917 complex_to_py_utility_code = UtilityCode(
1918 proto="""
1919 #define __pyx_PyComplex_FromComplex(z) \\
1920         PyComplex_FromDoubles((double)__Pyx_CREAL(z), \\
1921                               (double)__Pyx_CIMAG(z))
1922 """)
1923
1924 complex_from_py_utility_code = UtilityCode(
1925 proto="""
1926 static %(type)s __Pyx_PyComplex_As_%(type_name)s(PyObject*);
1927 """,
1928 impl="""
1929 static %(type)s __Pyx_PyComplex_As_%(type_name)s(PyObject* o) {
1930     Py_complex cval;
1931 #if CYTHON_COMPILING_IN_CPYTHON
1932     if (PyComplex_CheckExact(o))
1933         cval = ((PyComplexObject *)o)->cval;
1934     else
1935 #endif
1936         cval = PyComplex_AsCComplex(o);
1937     return %(type_name)s_from_parts(
1938                (%(real_type)s)cval.real,
1939                (%(real_type)s)cval.imag);
1940 }
1941 """)
1942
1943 complex_arithmetic_utility_code = UtilityCode(
1944 proto="""
1945 #if CYTHON_CCOMPLEX
1946     #define __Pyx_c_eq%(m)s(a, b)   ((a)==(b))
1947     #define __Pyx_c_sum%(m)s(a, b)  ((a)+(b))
1948     #define __Pyx_c_diff%(m)s(a, b) ((a)-(b))
1949     #define __Pyx_c_prod%(m)s(a, b) ((a)*(b))
1950     #define __Pyx_c_quot%(m)s(a, b) ((a)/(b))
1951     #define __Pyx_c_neg%(m)s(a)     (-(a))
1952   #ifdef __cplusplus
1953     #define __Pyx_c_is_zero%(m)s(z) ((z)==(%(real_type)s)0)
1954     #define __Pyx_c_conj%(m)s(z)    (::std::conj(z))
1955     #if %(is_float)s
1956         #define __Pyx_c_abs%(m)s(z)     (::std::abs(z))
1957         #define __Pyx_c_pow%(m)s(a, b)  (::std::pow(a, b))
1958     #endif
1959   #else
1960     #define __Pyx_c_is_zero%(m)s(z) ((z)==0)
1961     #define __Pyx_c_conj%(m)s(z)    (conj%(m)s(z))
1962     #if %(is_float)s
1963         #define __Pyx_c_abs%(m)s(z)     (cabs%(m)s(z))
1964         #define __Pyx_c_pow%(m)s(a, b)  (cpow%(m)s(a, b))
1965     #endif
1966  #endif
1967 #else
1968     static CYTHON_INLINE int __Pyx_c_eq%(m)s(%(type)s, %(type)s);
1969     static CYTHON_INLINE %(type)s __Pyx_c_sum%(m)s(%(type)s, %(type)s);
1970     static CYTHON_INLINE %(type)s __Pyx_c_diff%(m)s(%(type)s, %(type)s);
1971     static CYTHON_INLINE %(type)s __Pyx_c_prod%(m)s(%(type)s, %(type)s);
1972     static CYTHON_INLINE %(type)s __Pyx_c_quot%(m)s(%(type)s, %(type)s);
1973     static CYTHON_INLINE %(type)s __Pyx_c_neg%(m)s(%(type)s);
1974     static CYTHON_INLINE int __Pyx_c_is_zero%(m)s(%(type)s);
1975     static CYTHON_INLINE %(type)s __Pyx_c_conj%(m)s(%(type)s);
1976     #if %(is_float)s
1977         static CYTHON_INLINE %(real_type)s __Pyx_c_abs%(m)s(%(type)s);
1978         static CYTHON_INLINE %(type)s __Pyx_c_pow%(m)s(%(type)s, %(type)s);
1979     #endif
1980 #endif
1981 """,
1982 impl="""
1983 #if CYTHON_CCOMPLEX
1984 #else
1985     static CYTHON_INLINE int __Pyx_c_eq%(m)s(%(type)s a, %(type)s b) {
1986        return (a.real == b.real) && (a.imag == b.imag);
1987     }
1988     static CYTHON_INLINE %(type)s __Pyx_c_sum%(m)s(%(type)s a, %(type)s b) {
1989         %(type)s z;
1990         z.real = a.real + b.real;
1991         z.imag = a.imag + b.imag;
1992         return z;
1993     }
1994     static CYTHON_INLINE %(type)s __Pyx_c_diff%(m)s(%(type)s a, %(type)s b) {
1995         %(type)s z;
1996         z.real = a.real - b.real;
1997         z.imag = a.imag - b.imag;
1998         return z;
1999     }
2000     static CYTHON_INLINE %(type)s __Pyx_c_prod%(m)s(%(type)s a, %(type)s b) {
2001         %(type)s z;
2002         z.real = a.real * b.real - a.imag * b.imag;
2003         z.imag = a.real * b.imag + a.imag * b.real;
2004         return z;
2005     }
2006     static CYTHON_INLINE %(type)s __Pyx_c_quot%(m)s(%(type)s a, %(type)s b) {
2007         %(type)s z;
2008         %(real_type)s denom = b.real * b.real + b.imag * b.imag;
2009         z.real = (a.real * b.real + a.imag * b.imag) / denom;
2010         z.imag = (a.imag * b.real - a.real * b.imag) / denom;
2011         return z;
2012     }
2013     static CYTHON_INLINE %(type)s __Pyx_c_neg%(m)s(%(type)s a) {
2014         %(type)s z;
2015         z.real = -a.real;
2016         z.imag = -a.imag;
2017         return z;
2018     }
2019     static CYTHON_INLINE int __Pyx_c_is_zero%(m)s(%(type)s a) {
2020        return (a.real == 0) && (a.imag == 0);
2021     }
2022     static CYTHON_INLINE %(type)s __Pyx_c_conj%(m)s(%(type)s a) {
2023         %(type)s z;
2024         z.real =  a.real;
2025         z.imag = -a.imag;
2026         return z;
2027     }
2028     #if %(is_float)s
2029         static CYTHON_INLINE %(real_type)s __Pyx_c_abs%(m)s(%(type)s z) {
2030           #if !defined(HAVE_HYPOT) || defined(_MSC_VER)
2031             return sqrt%(m)s(z.real*z.real + z.imag*z.imag);
2032           #else
2033             return hypot%(m)s(z.real, z.imag);
2034           #endif
2035         }
2036         static CYTHON_INLINE %(type)s __Pyx_c_pow%(m)s(%(type)s a, %(type)s b) {
2037             %(type)s z;
2038             %(real_type)s r, lnr, theta, z_r, z_theta;
2039             if (b.imag == 0 && b.real == (int)b.real) {
2040                 if (b.real < 0) {
2041                     %(real_type)s denom = a.real * a.real + a.imag * a.imag;
2042                     a.real = a.real / denom;
2043                     a.imag = -a.imag / denom;
2044                     b.real = -b.real;
2045                 }
2046                 switch ((int)b.real) {
2047                     case 0:
2048                         z.real = 1;
2049                         z.imag = 0;
2050                         return z;
2051                     case 1:
2052                         return a;
2053                     case 2:
2054                         z = __Pyx_c_prod%(m)s(a, a);
2055                         return __Pyx_c_prod%(m)s(a, a);
2056                     case 3:
2057                         z = __Pyx_c_prod%(m)s(a, a);
2058                         return __Pyx_c_prod%(m)s(z, a);
2059                     case 4:
2060                         z = __Pyx_c_prod%(m)s(a, a);
2061                         return __Pyx_c_prod%(m)s(z, z);
2062                 }
2063             }
2064             if (a.imag == 0) {
2065                 if (a.real == 0) {
2066                     return a;
2067                 }
2068                 r = a.real;
2069                 theta = 0;
2070             } else {
2071                 r = __Pyx_c_abs%(m)s(a);
2072                 theta = atan2%(m)s(a.imag, a.real);
2073             }
2074             lnr = log%(m)s(r);
2075             z_r = exp%(m)s(lnr * b.real - theta * b.imag);
2076             z_theta = theta * b.real + lnr * b.imag;
2077             z.real = z_r * cos%(m)s(z_theta);
2078             z.imag = z_r * sin%(m)s(z_theta);
2079             return z;
2080         }
2081     #endif
2082 #endif
2083 """)
2084
2085 class CPointerBaseType(CType):
2086     # common base type for pointer/array types
2087     #
2088     #  base_type     CType              Reference type
2089
2090     subtypes = ['base_type']
2091
2092     def __init__(self, base_type):
2093         self.base_type = base_type
2094         for char_type in (c_char_type, c_uchar_type, c_schar_type):
2095             if base_type.same_as(char_type):
2096                 self.is_string = 1
2097                 break
2098         else:
2099             if base_type.same_as(c_py_unicode_type):
2100                 self.is_pyunicode_ptr = 1
2101
2102         if self.is_string and not base_type.is_error:
2103             if base_type.signed:
2104                 self.to_py_function = "__Pyx_PyObject_FromString"
2105                 if self.is_ptr:
2106                     if base_type.signed == 2:
2107                         self.from_py_function = "__Pyx_PyObject_AsSString"
2108                     else:
2109                         self.from_py_function = "__Pyx_PyObject_AsString"
2110             else:
2111                 self.to_py_function = "__Pyx_PyObject_FromUString"
2112                 if self.is_ptr:
2113                     self.from_py_function = "__Pyx_PyObject_AsUString"
2114             self.exception_value = "NULL"
2115         elif self.is_pyunicode_ptr and not base_type.is_error:
2116             self.to_py_function = "__Pyx_PyUnicode_FromUnicode"
2117             if self.is_ptr:
2118                 self.from_py_function = "__Pyx_PyUnicode_AsUnicode"
2119             self.exception_value = "NULL"
2120
2121     def py_type_name(self):
2122         if self.is_string:
2123             return "bytes"
2124         elif self.is_pyunicode_ptr:
2125             return "unicode"
2126         else:
2127             return super(CPointerBaseType, self).py_type_name()
2128
2129     def literal_code(self, value):
2130         if self.is_string:
2131             assert isinstance(value, str)
2132             return '"%s"' % StringEncoding.escape_byte_string(value)
2133
2134
2135 class CArrayType(CPointerBaseType):
2136     #  base_type     CType              Element type
2137     #  size          integer or None    Number of elements
2138
2139     is_array = 1
2140
2141     def __init__(self, base_type, size):
2142         super(CArrayType, self).__init__(base_type)
2143         self.size = size
2144
2145     def __eq__(self, other):
2146         if isinstance(other, CType) and other.is_array and self.size == other.size:
2147             return self.base_type.same_as(other.base_type)
2148         return False
2149
2150     def __hash__(self):
2151         return hash(self.base_type) + 28 # arbitrarily chosen offset
2152
2153     def __repr__(self):
2154         return "<CArrayType %s %s>" % (self.size, repr(self.base_type))
2155
2156     def same_as_resolved_type(self, other_type):
2157         return ((other_type.is_array and
2158             self.base_type.same_as(other_type.base_type))
2159                 or other_type is error_type)
2160
2161     def assignable_from_resolved_type(self, src_type):
2162         # Can't assign to a variable of an array type
2163         return 0
2164
2165     def element_ptr_type(self):
2166         return c_ptr_type(self.base_type)
2167
2168     def declaration_code(self, entity_code,
2169             for_display = 0, dll_linkage = None, pyrex = 0):
2170         if self.size is not None:
2171             dimension_code = self.size
2172         else:
2173             dimension_code = ""
2174         if entity_code.startswith("*"):
2175             entity_code = "(%s)" % entity_code
2176         return self.base_type.declaration_code(
2177             "%s[%s]" % (entity_code, dimension_code),
2178             for_display, dll_linkage, pyrex)
2179
2180     def as_argument_type(self):
2181         return c_ptr_type(self.base_type)
2182
2183     def is_complete(self):
2184         return self.size is not None
2185
2186     def specialize(self, values):
2187         base_type = self.base_type.specialize(values)
2188         if base_type == self.base_type:
2189             return self
2190         else:
2191             return CArrayType(base_type)
2192
2193     def deduce_template_params(self, actual):
2194         if isinstance(actual, CArrayType):
2195             return self.base_type.deduce_template_params(actual.base_type)
2196         else:
2197             return None
2198
2199
2200 class CPtrType(CPointerBaseType):
2201     #  base_type     CType              Reference type
2202
2203     is_ptr = 1
2204     default_value = "0"
2205
2206     def __hash__(self):
2207         return hash(self.base_type) + 27 # arbitrarily chosen offset
2208
2209     def __eq__(self, other):
2210         if isinstance(other, CType) and other.is_ptr:
2211             return self.base_type.same_as(other.base_type)
2212         return False
2213
2214     def __ne__(self, other):
2215         return not (self == other)
2216
2217     def __repr__(self):
2218         return "<CPtrType %s>" % repr(self.base_type)
2219
2220     def same_as_resolved_type(self, other_type):
2221         return ((other_type.is_ptr and
2222             self.base_type.same_as(other_type.base_type))
2223                 or other_type is error_type)
2224
2225     def declaration_code(self, entity_code,
2226             for_display = 0, dll_linkage = None, pyrex = 0):
2227         #print "CPtrType.declaration_code: pointer to", self.base_type ###
2228         return self.base_type.declaration_code(
2229             "*%s" % entity_code,
2230             for_display, dll_linkage, pyrex)
2231
2232     def assignable_from_resolved_type(self, other_type):
2233         if other_type is error_type:
2234             return 1
2235         if other_type.is_null_ptr:
2236             return 1
2237         if self.base_type.is_const:
2238             self = CPtrType(self.base_type.const_base_type)
2239         if self.base_type.is_cfunction:
2240             if other_type.is_ptr:
2241                 other_type = other_type.base_type.resolve()
2242             if other_type.is_cfunction:
2243                 return self.base_type.pointer_assignable_from_resolved_type(other_type)
2244             else:
2245                 return 0
2246         if (self.base_type.is_cpp_class and other_type.is_ptr
2247                 and other_type.base_type.is_cpp_class and other_type.base_type.is_subclass(self.base_type)):
2248             return 1
2249         if other_type.is_array or other_type.is_ptr:
2250             return self.base_type.is_void or self.base_type.same_as(other_type.base_type)
2251         return 0
2252
2253     def specialize(self, values):
2254         base_type = self.base_type.specialize(values)
2255         if base_type == self.base_type:
2256             return self
2257         else:
2258             return CPtrType(base_type)
2259
2260     def deduce_template_params(self, actual):
2261         if isinstance(actual, CPtrType):
2262             return self.base_type.deduce_template_params(actual.base_type)
2263         else:
2264             return None
2265
2266     def invalid_value(self):
2267         return "1"
2268
2269     def find_cpp_operation_type(self, operator, operand_type=None):
2270         if self.base_type.is_cpp_class:
2271             return self.base_type.find_cpp_operation_type(operator, operand_type)
2272         return None
2273
2274 class CNullPtrType(CPtrType):
2275
2276     is_null_ptr = 1
2277
2278
2279 class CReferenceType(BaseType):
2280
2281     is_reference = 1
2282
2283     def __init__(self, base_type):
2284         self.ref_base_type = base_type
2285
2286     def __repr__(self):
2287         return "<CReferenceType %s>" % repr(self.ref_base_type)
2288
2289     def __str__(self):
2290         return "%s &" % self.ref_base_type
2291
2292     def declaration_code(self, entity_code,
2293             for_display = 0, dll_linkage = None, pyrex = 0):
2294         #print "CReferenceType.declaration_code: pointer to", self.base_type ###
2295         return self.ref_base_type.declaration_code(
2296             "&%s" % entity_code,
2297             for_display, dll_linkage, pyrex)
2298
2299     def specialize(self, values):
2300         base_type = self.ref_base_type.specialize(values)
2301         if base_type == self.ref_base_type:
2302             return self
2303         else:
2304             return CReferenceType(base_type)
2305
2306     def deduce_template_params(self, actual):
2307         return self.ref_base_type.deduce_template_params(actual)
2308
2309     def __getattr__(self, name):
2310         return getattr(self.ref_base_type, name)
2311
2312
2313 class CFuncType(CType):
2314     #  return_type      CType
2315     #  args             [CFuncTypeArg]
2316     #  has_varargs      boolean
2317     #  exception_value  string
2318     #  exception_check  boolean    True if PyErr_Occurred check needed
2319     #  calling_convention  string  Function calling convention
2320     #  nogil            boolean    Can be called without gil
2321     #  with_gil         boolean    Acquire gil around function body
2322     #  templates        [string] or None
2323     #  cached_specialized_types [CFuncType]   cached specialized versions of the CFuncType if defined in a pxd
2324     #  from_fused       boolean    Indicates whether this is a specialized
2325     #                              C function
2326     #  is_strict_signature boolean  function refuses to accept coerced arguments
2327     #                               (used for optimisation overrides)
2328     #  is_const_method  boolean
2329
2330     is_cfunction = 1
2331     original_sig = None
2332     cached_specialized_types = None
2333     from_fused = False
2334     is_const_method = False
2335
2336     subtypes = ['return_type', 'args']
2337
2338     def __init__(self, return_type, args, has_varargs = 0,
2339             exception_value = None, exception_check = 0, calling_convention = "",
2340             nogil = 0, with_gil = 0, is_overridable = 0, optional_arg_count = 0,
2341             is_const_method = False, templates = None, is_strict_signature = False):
2342         self.return_type = return_type
2343         self.args = args
2344         self.has_varargs = has_varargs
2345         self.optional_arg_count = optional_arg_count
2346         self.exception_value = exception_value
2347         self.exception_check = exception_check
2348         self.calling_convention = calling_convention
2349         self.nogil = nogil
2350         self.with_gil = with_gil
2351         self.is_overridable = is_overridable
2352         self.is_const_method = is_const_method
2353         self.templates = templates
2354         self.is_strict_signature = is_strict_signature
2355
2356     def __repr__(self):
2357         arg_reprs = map(repr, self.args)
2358         if self.has_varargs:
2359             arg_reprs.append("...")
2360         if self.exception_value:
2361             except_clause = " %r" % self.exception_value
2362         else:
2363             except_clause = ""
2364         if self.exception_check:
2365             except_clause += "?"
2366         return "<CFuncType %s %s[%s]%s>" % (
2367             repr(self.return_type),
2368             self.calling_convention_prefix(),
2369             ",".join(arg_reprs),
2370             except_clause)
2371
2372     def calling_convention_prefix(self):
2373         cc = self.calling_convention
2374         if cc:
2375             return cc + " "
2376         else:
2377             return ""
2378
2379     def as_argument_type(self):
2380         return c_ptr_type(self)
2381
2382     def same_c_signature_as(self, other_type, as_cmethod = 0):
2383         return self.same_c_signature_as_resolved_type(
2384             other_type.resolve(), as_cmethod)
2385
2386     def same_c_signature_as_resolved_type(self, other_type, as_cmethod = 0):
2387         #print "CFuncType.same_c_signature_as_resolved_type:", \
2388         #    self, other_type, "as_cmethod =", as_cmethod ###
2389         if other_type is error_type:
2390             return 1
2391         if not other_type.is_cfunction:
2392             return 0
2393         if self.is_overridable != other_type.is_overridable:
2394             return 0
2395         nargs = len(self.args)
2396         if nargs != len(other_type.args):
2397             return 0
2398         # When comparing C method signatures, the first argument
2399         # is exempt from compatibility checking (the proper check
2400         # is performed elsewhere).
2401         for i in range(as_cmethod, nargs):
2402             if not self.args[i].type.same_as(
2403                 other_type.args[i].type):
2404                     return 0
2405         if self.has_varargs != other_type.has_varargs:
2406             return 0
2407         if self.optional_arg_count != other_type.optional_arg_count:
2408             return 0
2409         if not self.return_type.same_as(other_type.return_type):
2410             return 0
2411         if not self.same_calling_convention_as(other_type):
2412             return 0
2413         return 1
2414
2415     def compatible_signature_with(self, other_type, as_cmethod = 0):
2416         return self.compatible_signature_with_resolved_type(other_type.resolve(), as_cmethod)
2417
2418     def compatible_signature_with_resolved_type(self, other_type, as_cmethod):
2419         #print "CFuncType.same_c_signature_as_resolved_type:", \
2420         #    self, other_type, "as_cmethod =", as_cmethod ###
2421         if other_type is error_type:
2422             return 1
2423         if not other_type.is_cfunction:
2424             return 0
2425         if not self.is_overridable and other_type.is_overridable:
2426             return 0
2427         nargs = len(self.args)
2428         if nargs - self.optional_arg_count != len(other_type.args) - other_type.optional_arg_count:
2429             return 0
2430         if self.optional_arg_count < other_type.optional_arg_count:
2431             return 0
2432         # When comparing C method signatures, the first argument
2433         # is exempt from compatibility checking (the proper check
2434         # is performed elsewhere).
2435         for i in range(as_cmethod, len(other_type.args)):
2436             if not self.args[i].type.same_as(
2437                 other_type.args[i].type):
2438                     return 0
2439         if self.has_varargs != other_type.has_varargs:
2440             return 0
2441         if not self.return_type.subtype_of_resolved_type(other_type.return_type):
2442             return 0
2443         if not self.same_calling_convention_as(other_type):
2444             return 0
2445         if self.nogil != other_type.nogil:
2446             return 0
2447         self.original_sig = other_type.original_sig or other_type
2448         return 1
2449
2450
2451     def narrower_c_signature_than(self, other_type, as_cmethod = 0):
2452         return self.narrower_c_signature_than_resolved_type(other_type.resolve(), as_cmethod)
2453
2454     def narrower_c_signature_than_resolved_type(self, other_type, as_cmethod):
2455         if other_type is error_type:
2456             return 1
2457         if not other_type.is_cfunction:
2458             return 0
2459         nargs = len(self.args)
2460         if nargs != len(other_type.args):
2461             return 0
2462         for i in range(as_cmethod, nargs):
2463             if not self.args[i].type.subtype_of_resolved_type(other_type.args[i].type):
2464                 return 0
2465             else:
2466                 self.args[i].needs_type_test = other_type.args[i].needs_type_test \
2467                         or not self.args[i].type.same_as(other_type.args[i].type)
2468         if self.has_varargs != other_type.has_varargs:
2469             return 0
2470         if self.optional_arg_count != other_type.optional_arg_count:
2471             return 0
2472         if not self.return_type.subtype_of_resolved_type(other_type.return_type):
2473             return 0
2474         return 1
2475
2476     def same_calling_convention_as(self, other):
2477         ## XXX Under discussion ...
2478         ## callspec_words = ("__stdcall", "__cdecl", "__fastcall")
2479         ## cs1 = self.calling_convention
2480         ## cs2 = other.calling_convention
2481         ## if (cs1 in callspec_words or
2482         ##     cs2 in callspec_words):
2483         ##     return cs1 == cs2
2484         ## else:
2485         ##     return True
2486         sc1 = self.calling_convention == '__stdcall'
2487         sc2 = other.calling_convention == '__stdcall'
2488         return sc1 == sc2
2489
2490     def same_exception_signature_as(self, other_type):
2491         return self.same_exception_signature_as_resolved_type(
2492             other_type.resolve())
2493
2494     def same_exception_signature_as_resolved_type(self, other_type):
2495         return self.exception_value == other_type.exception_value \
2496             and self.exception_check == other_type.exception_check
2497
2498     def same_as_resolved_type(self, other_type, as_cmethod = 0):
2499         return self.same_c_signature_as_resolved_type(other_type, as_cmethod) \
2500             and self.same_exception_signature_as_resolved_type(other_type) \
2501             and self.nogil == other_type.nogil
2502
2503     def pointer_assignable_from_resolved_type(self, other_type):
2504         return self.same_c_signature_as_resolved_type(other_type) \
2505             and self.same_exception_signature_as_resolved_type(other_type) \
2506             and not (self.nogil and not other_type.nogil)
2507
2508     def declaration_code(self, entity_code,
2509                          for_display = 0, dll_linkage = None, pyrex = 0,
2510                          with_calling_convention = 1):
2511         arg_decl_list = []
2512         for arg in self.args[:len(self.args)-self.optional_arg_count]:
2513             arg_decl_list.append(
2514                 arg.type.declaration_code("", for_display, pyrex = pyrex))
2515         if self.is_overridable:
2516             arg_decl_list.append("int %s" % Naming.skip_dispatch_cname)
2517         if self.optional_arg_count:
2518             arg_decl_list.append(self.op_arg_struct.declaration_code(Naming.optional_args_cname))
2519         if self.has_varargs:
2520             arg_decl_list.append("...")
2521         arg_decl_code = ", ".join(arg_decl_list)
2522         if not arg_decl_code and not pyrex:
2523             arg_decl_code = "void"
2524         trailer = ""
2525         if (pyrex or for_display) and not self.return_type.is_pyobject:
2526             if self.exception_value and self.exception_check:
2527                 trailer = " except? %s" % self.exception_value
2528             elif self.exception_value:
2529                 trailer = " except %s" % self.exception_value
2530             elif self.exception_check == '+':
2531                 trailer = " except +"
2532             else:
2533                 " except *" # ignored
2534             if self.nogil:
2535                 trailer += " nogil"
2536         if not with_calling_convention:
2537             cc = ''
2538         else:
2539             cc = self.calling_convention_prefix()
2540             if (not entity_code and cc) or entity_code.startswith("*"):
2541                 entity_code = "(%s%s)" % (cc, entity_code)
2542                 cc = ""
2543         if self.is_const_method:
2544             trailer += " const"
2545         return self.return_type.declaration_code(
2546             "%s%s(%s)%s" % (cc, entity_code, arg_decl_code, trailer),
2547             for_display, dll_linkage, pyrex)
2548
2549     def function_header_code(self, func_name, arg_code):
2550         if self.is_const_method:
2551             trailer = " const"
2552         else:
2553             trailer = ""
2554         return "%s%s(%s)%s" % (self.calling_convention_prefix(),
2555             func_name, arg_code, trailer)
2556
2557     def signature_string(self):
2558         s = self.declaration_code("")
2559         return s
2560
2561     def signature_cast_string(self):
2562         s = self.declaration_code("(*)", with_calling_convention=False)
2563         return '(%s)' % s
2564
2565     def specialize(self, values):
2566         result = CFuncType(self.return_type.specialize(values),
2567                            [arg.specialize(values) for arg in self.args],
2568                            has_varargs = self.has_varargs,
2569                            exception_value = self.exception_value,
2570                            exception_check = self.exception_check,
2571                            calling_convention = self.calling_convention,
2572                            nogil = self.nogil,
2573                            with_gil = self.with_gil,
2574                            is_overridable = self.is_overridable,
2575                            optional_arg_count = self.optional_arg_count,
2576                            is_const_method = self.is_const_method,
2577                            templates = self.templates)
2578
2579         result.from_fused = self.is_fused
2580         return result
2581
2582     def opt_arg_cname(self, arg_name):
2583         return self.op_arg_struct.base_type.scope.lookup(arg_name).cname
2584
2585     # Methods that deal with Fused Types
2586     # All but map_with_specific_entries should be called only on functions
2587     # with fused types (and not on their corresponding specific versions).
2588
2589     def get_all_specialized_permutations(self, fused_types=None):
2590         """
2591         Permute all the types. For every specific instance of a fused type, we
2592         want all other specific instances of all other fused types.
2593
2594         It returns an iterable of two-tuples of the cname that should prefix
2595         the cname of the function, and a dict mapping any fused types to their
2596         respective specific types.
2597         """
2598         assert self.is_fused
2599
2600         if fused_types is None:
2601             fused_types = self.get_fused_types()
2602
2603         return get_all_specialized_permutations(fused_types)
2604
2605     def get_all_specialized_function_types(self):
2606         """
2607         Get all the specific function types of this one.
2608         """
2609         assert self.is_fused
2610
2611         if self.entry.fused_cfunction:
2612             return [n.type for n in self.entry.fused_cfunction.nodes]
2613         elif self.cached_specialized_types is not None:
2614             return self.cached_specialized_types
2615
2616         cfunc_entries = self.entry.scope.cfunc_entries
2617         cfunc_entries.remove(self.entry)
2618
2619         result = []
2620         permutations = self.get_all_specialized_permutations()
2621
2622         for cname, fused_to_specific in permutations:
2623             new_func_type = self.entry.type.specialize(fused_to_specific)
2624
2625             if self.optional_arg_count:
2626                 # Remember, this method is set by CFuncDeclaratorNode
2627                 self.declare_opt_arg_struct(new_func_type, cname)
2628
2629             new_entry = copy.deepcopy(self.entry)
2630             new_func_type.specialize_entry(new_entry, cname)
2631
2632             new_entry.type = new_func_type
2633             new_func_type.entry = new_entry
2634             result.append(new_func_type)
2635
2636             cfunc_entries.append(new_entry)
2637
2638         self.cached_specialized_types = result
2639
2640         return result
2641
2642     def get_fused_types(self, result=None, seen=None, subtypes=None):
2643         """Return fused types in the order they appear as parameter types"""
2644         return super(CFuncType, self).get_fused_types(result, seen,
2645                                                       subtypes=['args'])
2646
2647     def specialize_entry(self, entry, cname):
2648         assert not self.is_fused
2649         specialize_entry(entry, cname)
2650
2651
2652 def specialize_entry(entry, cname):
2653     """
2654     Specialize an entry of a copied fused function or method
2655     """
2656     entry.is_fused_specialized = True
2657     entry.name = get_fused_cname(cname, entry.name)
2658
2659     if entry.is_cmethod:
2660         entry.cname = entry.name
2661         if entry.is_inherited:
2662             entry.cname = StringEncoding.EncodedString(
2663                     "%s.%s" % (Naming.obj_base_cname, entry.cname))
2664     else:
2665         entry.cname = get_fused_cname(cname, entry.cname)
2666
2667     if entry.func_cname:
2668         entry.func_cname = get_fused_cname(cname, entry.func_cname)
2669
2670 def get_fused_cname(fused_cname, orig_cname):
2671     """
2672     Given the fused cname id and an original cname, return a specialized cname
2673     """
2674     assert fused_cname and orig_cname
2675     return StringEncoding.EncodedString('%s%s%s' % (Naming.fused_func_prefix,
2676                                                     fused_cname, orig_cname))
2677
2678 def unique(somelist):
2679     seen = set()
2680     result = []
2681     for obj in somelist:
2682         if obj not in seen:
2683             result.append(obj)
2684             seen.add(obj)
2685
2686     return result
2687
2688 def get_all_specialized_permutations(fused_types):
2689     return _get_all_specialized_permutations(unique(fused_types))
2690
2691 def _get_all_specialized_permutations(fused_types, id="", f2s=()):
2692     fused_type, = fused_types[0].get_fused_types()
2693     result = []
2694
2695     for newid, specific_type in enumerate(fused_type.types):
2696         # f2s = dict(f2s, **{ fused_type: specific_type })
2697         f2s = dict(f2s)
2698         f2s.update({ fused_type: specific_type })
2699
2700         if id:
2701             cname = '%s_%s' % (id, newid)
2702         else:
2703             cname = str(newid)
2704
2705         if len(fused_types) > 1:
2706             result.extend(_get_all_specialized_permutations(
2707                                             fused_types[1:], cname, f2s))
2708         else:
2709             result.append((cname, f2s))
2710
2711     return result
2712
2713 def specialization_signature_string(fused_compound_type, fused_to_specific):
2714     """
2715     Return the signature for a specialization of a fused type. e.g.
2716
2717         floating[:] ->
2718             'float' or 'double'
2719
2720         cdef fused ft:
2721             float[:]
2722             double[:]
2723
2724         ft ->
2725             'float[:]' or 'double[:]'
2726
2727         integral func(floating) ->
2728             'int (*func)(float)' or ...
2729     """
2730     fused_types = fused_compound_type.get_fused_types()
2731     if len(fused_types) == 1:
2732         fused_type = fused_types[0]
2733     else:
2734         fused_type = fused_compound_type
2735
2736     return fused_type.specialize(fused_to_specific).typeof_name()
2737
2738 def get_specialized_types(type):
2739     """
2740     Return a list of specialized types sorted in reverse order in accordance
2741     with their preference in runtime fused-type dispatch
2742     """
2743     assert type.is_fused
2744
2745     if isinstance(type, FusedType):
2746         result = type.types
2747         for specialized_type in result:
2748             specialized_type.specialization_string = specialized_type.typeof_name()
2749     else:
2750         result = []
2751         for cname, f2s in get_all_specialized_permutations(type.get_fused_types()):
2752             specialized_type = type.specialize(f2s)
2753             specialized_type.specialization_string = (
2754                             specialization_signature_string(type, f2s))
2755             result.append(specialized_type)
2756
2757     return sorted(result)
2758
2759
2760 class CFuncTypeArg(BaseType):
2761     #  name       string
2762     #  cname      string
2763     #  type       PyrexType
2764     #  pos        source file position
2765
2766     # FIXME: is this the right setup? should None be allowed here?
2767     not_none = False
2768     or_none = False
2769     accept_none = True
2770     accept_builtin_subtypes = False
2771
2772     subtypes = ['type']
2773
2774     def __init__(self, name, type, pos, cname=None):
2775         self.name = name
2776         if cname is not None:
2777             self.cname = cname
2778         else:
2779             self.cname = Naming.var_prefix + name
2780         self.type = type
2781         self.pos = pos
2782         self.needs_type_test = False # TODO: should these defaults be set in analyse_types()?
2783
2784     def __repr__(self):
2785         return "%s:%s" % (self.name, repr(self.type))
2786
2787     def declaration_code(self, for_display = 0):
2788         return self.type.declaration_code(self.cname, for_display)
2789
2790     def specialize(self, values):
2791         return CFuncTypeArg(self.name, self.type.specialize(values), self.pos, self.cname)
2792
2793 class ToPyStructUtilityCode(object):
2794
2795     requires = None
2796
2797     def __init__(self, type, forward_decl):
2798         self.type = type
2799         self.header = "static PyObject* %s(%s)" % (type.to_py_function,
2800                                                    type.declaration_code('s'))
2801         self.forward_decl = forward_decl
2802
2803     def __eq__(self, other):
2804         return isinstance(other, ToPyStructUtilityCode) and self.header == other.header
2805
2806     def __hash__(self):
2807         return hash(self.header)
2808
2809     def get_tree(self):
2810         pass
2811
2812     def put_code(self, output):
2813         code = output['utility_code_def']
2814         proto = output['utility_code_proto']
2815
2816         code.putln("%s {" % self.header)
2817         code.putln("PyObject* res;")
2818         code.putln("PyObject* member;")
2819         code.putln("res = PyDict_New(); if (res == NULL) return NULL;")
2820         for member in self.type.scope.var_entries:
2821             nameconst_cname = code.get_py_string_const(member.name, identifier=True)
2822             code.putln("member = %s(s.%s); if (member == NULL) goto bad;" % (
2823                 member.type.to_py_function, member.cname))
2824             code.putln("if (PyDict_SetItem(res, %s, member) < 0) goto bad;" % nameconst_cname)
2825             code.putln("Py_DECREF(member);")
2826         code.putln("return res;")
2827         code.putln("bad:")
2828         code.putln("Py_XDECREF(member);")
2829         code.putln("Py_DECREF(res);")
2830         code.putln("return NULL;")
2831         code.putln("}")
2832
2833         # This is a bit of a hack, we need a forward declaration
2834         # due to the way things are ordered in the module...
2835         if self.forward_decl:
2836             proto.putln(self.type.declaration_code('') + ';')
2837         proto.putln(self.header + ";")
2838
2839     def inject_tree_and_scope_into(self, module_node):
2840         pass
2841
2842
2843 class CStructOrUnionType(CType):
2844     #  name          string
2845     #  cname         string
2846     #  kind          string              "struct" or "union"
2847     #  scope         StructOrUnionScope, or None if incomplete
2848     #  typedef_flag  boolean
2849     #  packed        boolean
2850
2851     # entry          Entry
2852
2853     is_struct_or_union = 1
2854     has_attributes = 1
2855     exception_check = True
2856
2857     def __init__(self, name, kind, scope, typedef_flag, cname, packed=False):
2858         self.name = name
2859         self.cname = cname
2860         self.kind = kind
2861         self.scope = scope
2862         self.typedef_flag = typedef_flag
2863         self.is_struct = kind == 'struct'
2864         if self.is_struct:
2865             self.to_py_function = "%s_to_py_%s" % (Naming.convert_func_prefix, self.cname)
2866             self.from_py_function = "%s_from_py_%s" % (Naming.convert_func_prefix, self.cname)
2867         self.exception_check = True
2868         self._convert_to_py_code = None
2869         self._convert_from_py_code = None
2870         self.packed = packed
2871
2872     def create_to_py_utility_code(self, env):
2873         if env.outer_scope is None:
2874             return False
2875
2876         if self._convert_to_py_code is False:
2877             return None  # tri-state-ish
2878
2879         if self._convert_to_py_code is None:
2880             for member in self.scope.var_entries:
2881                 if not member.type.create_to_py_utility_code(env):
2882                     self.to_py_function = None
2883                     self._convert_to_py_code = False
2884                     return False
2885             forward_decl = (self.entry.visibility != 'extern')
2886             self._convert_to_py_code = ToPyStructUtilityCode(self, forward_decl)
2887
2888         env.use_utility_code(self._convert_to_py_code)
2889         return True
2890
2891     def create_from_py_utility_code(self, env):
2892         if env.outer_scope is None:
2893             return False
2894
2895         if self._convert_from_py_code is False:
2896             return None  # tri-state-ish
2897
2898         if self._convert_from_py_code is None:
2899             for member in self.scope.var_entries:
2900                 if not member.type.create_from_py_utility_code(env):
2901                     self.from_py_function = None
2902                     self._convert_from_py_code = False
2903                     return False
2904
2905             context = dict(
2906                 struct_type_decl=self.declaration_code(""),
2907                 var_entries=self.scope.var_entries,
2908                 funcname=self.from_py_function,
2909             )
2910             self._convert_from_py_code = TempitaUtilityCode.load(
2911                 "FromPyStructUtility", "TypeConversion.c", context=context)
2912
2913         env.use_utility_code(self._convert_from_py_code)
2914         return True
2915
2916     def __repr__(self):
2917         return "<CStructOrUnionType %s %s%s>" % (
2918             self.name, self.cname,
2919             ("", " typedef")[self.typedef_flag])
2920
2921     def declaration_code(self, entity_code,
2922                          for_display=0, dll_linkage=None, pyrex=0):
2923         if pyrex or for_display:
2924             base_code = self.name
2925         else:
2926             if self.typedef_flag:
2927                 base_code = self.cname
2928             else:
2929                 base_code = "%s %s" % (self.kind, self.cname)
2930             base_code = public_decl(base_code, dll_linkage)
2931         return self.base_declaration_code(base_code, entity_code)
2932
2933     def __eq__(self, other):
2934         try:
2935             return (isinstance(other, CStructOrUnionType) and
2936                     self.name == other.name)
2937         except AttributeError:
2938             return False
2939
2940     def __lt__(self, other):
2941         try:
2942             return self.name < other.name
2943         except AttributeError:
2944             # this is arbitrary, but it makes sure we always have
2945             # *some* kind of order
2946             return False
2947
2948     def __hash__(self):
2949         return hash(self.cname) ^ hash(self.kind)
2950
2951     def is_complete(self):
2952         return self.scope is not None
2953
2954     def attributes_known(self):
2955         return self.is_complete()
2956
2957     def can_be_complex(self):
2958         # Does the struct consist of exactly two identical floats?
2959         fields = self.scope.var_entries
2960         if len(fields) != 2: return False
2961         a, b = fields
2962         return (a.type.is_float and b.type.is_float and
2963                 a.type.declaration_code("") ==
2964                 b.type.declaration_code(""))
2965
2966     def struct_nesting_depth(self):
2967         child_depths = [x.type.struct_nesting_depth()
2968                         for x in self.scope.var_entries]
2969         return max(child_depths) + 1
2970
2971     def cast_code(self, expr_code):
2972         if self.is_struct:
2973             return expr_code
2974         return super(CStructOrUnionType, self).cast_code(expr_code)
2975
2976
2977 builtin_cpp_conversions = ("std::string",
2978                            "std::pair",
2979                            "std::vector", "std::list",
2980                            "std::set", "std::unordered_set",
2981                            "std::map", "std::unordered_map")
2982
2983 class CppClassType(CType):
2984     #  name          string
2985     #  cname         string
2986     #  scope         CppClassScope
2987     #  templates     [string] or None
2988
2989     is_cpp_class = 1
2990     has_attributes = 1
2991     exception_check = True
2992     namespace = None
2993
2994     # For struct-like declaration.
2995     kind = "struct"
2996     packed = False
2997     typedef_flag = False
2998
2999     subtypes = ['templates']
3000
3001     def __init__(self, name, scope, cname, base_classes, templates = None, template_type = None):
3002         self.name = name
3003         self.cname = cname
3004         self.scope = scope
3005         self.base_classes = base_classes
3006         self.operators = []
3007         self.templates = templates
3008         self.template_type = template_type
3009         self.specializations = {}
3010         self.is_cpp_string = cname == 'std::string'
3011
3012     def use_conversion_utility(self, from_or_to):
3013         pass
3014
3015     def maybe_unordered(self):
3016         if 'unordered' in self.cname:
3017             return 'unordered_'
3018         else:
3019             return ''
3020
3021     def create_from_py_utility_code(self, env):
3022         if self.from_py_function is not None:
3023             return True
3024         if self.cname in builtin_cpp_conversions:
3025             X = "XYZABC"
3026             tags = []
3027             declarations = ["cdef extern from *:"]
3028             for ix, T in enumerate(self.templates or []):
3029                 if T.is_pyobject or not T.create_from_py_utility_code(env):
3030                     return False
3031                 tags.append(T.specialization_name())
3032                 if T.exception_value is not None:
3033                     except_clause = T.exception_value
3034                     if T.exception_check:
3035                         except_clause = "? %s" % except_clause
3036                     declarations.append(
3037                         "    ctypedef %s %s '%s'" % (
3038                              T.declaration_code("", for_display=True), X[ix], T.declaration_code("")))
3039                 else:
3040                     except_clause = "*"
3041                     declarations.append(
3042                         "    ctypedef struct %s '%s':\n        pass" % (
3043                              X[ix], T.declaration_code("")))
3044                 declarations.append(
3045                     "    cdef %s %s_from_py '%s' (object) except %s" % (
3046                          X[ix], X[ix], T.from_py_function, except_clause))
3047             cls = self.cname[5:]
3048             cname = '__pyx_convert_%s_from_py_%s' % (cls, '____'.join(tags))
3049             context = {
3050                 'template_type_declarations': '\n'.join(declarations),
3051                 'cname': cname,
3052                 'maybe_unordered': self.maybe_unordered(),
3053             }
3054             from UtilityCode import CythonUtilityCode
3055             env.use_utility_code(CythonUtilityCode.load(cls.replace('unordered_', '') + ".from_py", "CppConvert.pyx", context=context))
3056             self.from_py_function = cname
3057             return True
3058
3059     def create_to_py_utility_code(self, env):
3060         if self.to_py_function is not None:
3061             return True
3062         if self.cname in builtin_cpp_conversions:
3063             X = "XYZABC"
3064             tags = []
3065             declarations = ["cdef extern from *:"]
3066             for ix, T in enumerate(self.templates or []):
3067                 if not T.create_to_py_utility_code(env):
3068                     return False
3069                 tags.append(T.specialization_name())
3070                 declarations.append(
3071                     "    ctypedef struct %s '%s':\n        pass" % (
3072                          X[ix], T.declaration_code("")))
3073                 declarations.append(
3074                     "    cdef object %s_to_py '%s' (%s)" % (
3075                          X[ix], T.to_py_function, X[ix]))
3076             cls = self.cname[5:]
3077             cname = "__pyx_convert_%s_to_py_%s" % (cls, "____".join(tags))
3078             context = {
3079                 'template_type_declarations': '\n'.join(declarations),
3080                 'cname': cname,
3081                 'maybe_unordered': self.maybe_unordered(),
3082             }
3083             from UtilityCode import CythonUtilityCode
3084             env.use_utility_code(CythonUtilityCode.load(cls.replace('unordered_', '') + ".to_py", "CppConvert.pyx", context=context))
3085             self.to_py_function = cname
3086             return True
3087
3088     def specialize_here(self, pos, template_values = None):
3089         if self.templates is None:
3090             error(pos, "'%s' type is not a template" % self)
3091             return error_type
3092         if len(self.templates) != len(template_values):
3093             error(pos, "%s templated type receives %d arguments, got %d" %
3094                   (self.name, len(self.templates), len(template_values)))
3095             return error_type
3096         has_object_template_param = False
3097         for value in template_values:
3098             if value.is_pyobject:
3099                 has_object_template_param = True
3100                 error(pos,
3101                       "Python object type '%s' cannot be used as a template argument" % value)
3102         if has_object_template_param:
3103             return error_type
3104         return self.specialize(dict(zip(self.templates, template_values)))
3105
3106     def specialize(self, values):
3107         if not self.templates and not self.namespace:
3108             return self
3109         if self.templates is None:
3110             self.templates = []
3111         key = tuple(values.items())
3112         if key in self.specializations:
3113             return self.specializations[key]
3114         template_values = [t.specialize(values) for t in self.templates]
3115         specialized = self.specializations[key] = \
3116             CppClassType(self.name, None, self.cname, [], template_values, template_type=self)
3117         # Need to do these *after* self.specializations[key] is set
3118         # to avoid infinite recursion on circular references.
3119         specialized.base_classes = [b.specialize(values) for b in self.base_classes]
3120         specialized.scope = self.scope.specialize(values)
3121         if self.namespace is not None:
3122             specialized.namespace = self.namespace.specialize(values)
3123         return specialized
3124
3125     def deduce_template_params(self, actual):
3126         if self == actual:
3127             return {}
3128         # TODO(robertwb): Actual type equality.
3129         elif self.declaration_code("") == actual.template_type.declaration_code(""):
3130             return reduce(
3131                 merge_template_deductions,
3132                 [formal_param.deduce_template_params(actual_param) for (formal_param, actual_param) in zip(self.templates, actual.templates)],
3133                 {})
3134         else:
3135             return None
3136
3137     def declaration_code(self, entity_code,
3138             for_display = 0, dll_linkage = None, pyrex = 0):
3139         if self.templates:
3140             template_strings = [param.declaration_code('', for_display, None, pyrex)
3141                                 for param in self.templates]
3142             if for_display:
3143                 brackets = "[%s]"
3144             else:
3145                 brackets = "<%s>"
3146             templates = brackets % ",".join(template_strings)
3147             if templates[-2:] == ">>":
3148                 templates = templates[:-2] + "> >"
3149         else:
3150             templates = ""
3151         if pyrex or for_display:
3152             base_code = "%s%s" % (self.name, templates)
3153         else:
3154             base_code = "%s%s" % (self.cname, templates)
3155             if self.namespace is not None:
3156                 base_code = "%s::%s" % (self.namespace.declaration_code(''), base_code)
3157             base_code = public_decl(base_code, dll_linkage)
3158         return self.base_declaration_code(base_code, entity_code)
3159
3160     def is_subclass(self, other_type):
3161         if self.same_as_resolved_type(other_type):
3162             return 1
3163         for base_class in self.base_classes:
3164             if base_class.is_subclass(other_type):
3165                 return 1
3166         return 0
3167
3168     def same_as_resolved_type(self, other_type):
3169         if other_type.is_cpp_class:
3170             if self == other_type:
3171                 return 1
3172             elif (self.cname == other_type.cname and
3173                   self.template_type and other_type.template_type):
3174                 if self.templates == other_type.templates:
3175                     return 1
3176                 for t1, t2 in zip(self.templates, other_type.templates):
3177                     if not t1.same_as_resolved_type(t2):
3178                         return 0
3179                 return 1
3180         return 0
3181
3182     def assignable_from_resolved_type(self, other_type):
3183         # TODO: handle operator=(...) here?
3184         if other_type is error_type:
3185             return True
3186         return other_type.is_cpp_class and other_type.is_subclass(self)
3187
3188     def attributes_known(self):
3189         return self.scope is not None
3190
3191     def find_cpp_operation_type(self, operator, operand_type=None):
3192         operands = [self]
3193         if operand_type is not None:
3194             operands.append(operand_type)
3195         # pos == None => no errors
3196         operator_entry = self.scope.lookup_operator_for_types(None, operator, operands)
3197         if not operator_entry:
3198             return None
3199         func_type = operator_entry.type
3200         if func_type.is_ptr:
3201             func_type = func_type.base_type
3202         return func_type.return_type
3203
3204     def check_nullary_constructor(self, pos, msg="stack allocated"):
3205         constructor = self.scope.lookup(u'<init>')
3206         if constructor is not None and best_match([], constructor.all_alternatives()) is None:
3207             error(pos, "C++ class must have a nullary constructor to be %s" % msg)
3208
3209
3210 class TemplatePlaceholderType(CType):
3211
3212     def __init__(self, name):
3213         self.name = name
3214
3215     def declaration_code(self, entity_code,
3216             for_display = 0, dll_linkage = None, pyrex = 0):
3217         if entity_code:
3218             return self.name + " " + entity_code
3219         else:
3220             return self.name
3221
3222     def specialize(self, values):
3223         if self in values:
3224             return values[self]
3225         else:
3226             return self
3227
3228     def deduce_template_params(self, actual):
3229         return {self: actual}
3230
3231     def same_as_resolved_type(self, other_type):
3232         if isinstance(other_type, TemplatePlaceholderType):
3233             return self.name == other_type.name
3234         else:
3235             return 0
3236
3237     def __hash__(self):
3238         return hash(self.name)
3239
3240     def __cmp__(self, other):
3241         if isinstance(other, TemplatePlaceholderType):
3242             return cmp(self.name, other.name)
3243         else:
3244             return cmp(type(self), type(other))
3245
3246     def __eq__(self, other):
3247         if isinstance(other, TemplatePlaceholderType):
3248             return self.name == other.name
3249         else:
3250             return False
3251
3252 class CEnumType(CType):
3253     #  name           string
3254     #  cname          string or None
3255     #  typedef_flag   boolean
3256
3257     is_enum = 1
3258     signed = 1
3259     rank = -1 # Ranks below any integer type
3260     to_py_function = "PyInt_FromLong"
3261     from_py_function = "PyInt_AsLong"
3262
3263     def __init__(self, name, cname, typedef_flag):
3264         self.name = name
3265         self.cname = cname
3266         self.values = []
3267         self.typedef_flag = typedef_flag
3268
3269     def __str__(self):
3270         return self.name
3271
3272     def __repr__(self):
3273         return "<CEnumType %s %s%s>" % (self.name, self.cname,
3274             ("", " typedef")[self.typedef_flag])
3275
3276     def declaration_code(self, entity_code,
3277             for_display = 0, dll_linkage = None, pyrex = 0):
3278         if pyrex or for_display:
3279             base_code = self.name
3280         else:
3281             if self.typedef_flag:
3282                 base_code = self.cname
3283             else:
3284                 base_code = "enum %s" % self.cname
3285             base_code = public_decl(base_code, dll_linkage)
3286         return self.base_declaration_code(base_code, entity_code)
3287
3288 class UnspecifiedType(PyrexType):
3289     # Used as a placeholder until the type can be determined.
3290
3291     is_unspecified = 1
3292
3293     def declaration_code(self, entity_code,
3294             for_display = 0, dll_linkage = None, pyrex = 0):
3295         return "<unspecified>"
3296
3297     def same_as_resolved_type(self, other_type):
3298         return False
3299
3300
3301 class ErrorType(PyrexType):
3302     # Used to prevent propagation of error messages.
3303
3304     is_error = 1
3305     exception_value = "0"
3306     exception_check    = 0
3307     to_py_function = "dummy"
3308     from_py_function = "dummy"
3309
3310     def create_to_py_utility_code(self, env):
3311         return True
3312
3313     def create_from_py_utility_code(self, env):
3314         return True
3315
3316     def declaration_code(self, entity_code,
3317             for_display = 0, dll_linkage = None, pyrex = 0):
3318         return "<error>"
3319
3320     def same_as_resolved_type(self, other_type):
3321         return 1
3322
3323     def error_condition(self, result_code):
3324         return "dummy"
3325
3326
3327 rank_to_type_name = (
3328     "char",         # 0
3329     "short",        # 1
3330     "int",          # 2
3331     "long",         # 3
3332     "PY_LONG_LONG", # 4
3333     "float",        # 5
3334     "double",       # 6
3335     "long double",  # 7
3336 )
3337
3338 _rank_to_type_name = list(rank_to_type_name)
3339 RANK_INT  = _rank_to_type_name.index('int')
3340 RANK_LONG = _rank_to_type_name.index('long')
3341 RANK_FLOAT = _rank_to_type_name.index('float')
3342 UNSIGNED = 0
3343 SIGNED = 2
3344
3345 error_type =    ErrorType()
3346 unspecified_type = UnspecifiedType()
3347
3348 py_object_type = PyObjectType()
3349
3350 c_void_type =        CVoidType()
3351
3352 c_uchar_type =       CIntType(0, UNSIGNED)
3353 c_ushort_type =      CIntType(1, UNSIGNED)
3354 c_uint_type =        CIntType(2, UNSIGNED)
3355 c_ulong_type =       CIntType(3, UNSIGNED)
3356 c_ulonglong_type =   CIntType(4, UNSIGNED)
3357
3358 c_char_type =        CIntType(0)
3359 c_short_type =       CIntType(1)
3360 c_int_type =         CIntType(2)
3361 c_long_type =        CIntType(3)
3362 c_longlong_type =    CIntType(4)
3363
3364 c_schar_type =       CIntType(0, SIGNED)
3365 c_sshort_type =      CIntType(1, SIGNED)
3366 c_sint_type =        CIntType(2, SIGNED)
3367 c_slong_type =       CIntType(3, SIGNED)
3368 c_slonglong_type =   CIntType(4, SIGNED)
3369
3370 c_float_type =       CFloatType(5, math_h_modifier='f')
3371 c_double_type =      CFloatType(6)
3372 c_longdouble_type =  CFloatType(7, math_h_modifier='l')
3373
3374 c_float_complex_type =      CComplexType(c_float_type)
3375 c_double_complex_type =     CComplexType(c_double_type)
3376 c_longdouble_complex_type = CComplexType(c_longdouble_type)
3377
3378 c_anon_enum_type =   CAnonEnumType(-1)
3379 c_returncode_type =  CReturnCodeType(RANK_INT)
3380 c_bint_type =        CBIntType(RANK_INT)
3381 c_py_unicode_type =  CPyUnicodeIntType(RANK_INT-0.5, UNSIGNED)
3382 c_py_ucs4_type =     CPyUCS4IntType(RANK_LONG-0.5, UNSIGNED)
3383 c_py_hash_t_type =   CPyHashTType(RANK_LONG+0.5, SIGNED)
3384 c_py_ssize_t_type =  CPySSizeTType(RANK_LONG+0.5, SIGNED)
3385 c_ssize_t_type =     CSSizeTType(RANK_LONG+0.5, SIGNED)
3386 c_size_t_type =      CSizeTType(RANK_LONG+0.5, UNSIGNED)
3387 c_ptrdiff_t_type =   CPtrdiffTType(RANK_LONG+0.75, SIGNED)
3388
3389 c_null_ptr_type =     CNullPtrType(c_void_type)
3390 c_void_ptr_type =     CPtrType(c_void_type)
3391 c_void_ptr_ptr_type = CPtrType(c_void_ptr_type)
3392 c_char_ptr_type =     CPtrType(c_char_type)
3393 c_uchar_ptr_type =    CPtrType(c_uchar_type)
3394 c_char_ptr_ptr_type = CPtrType(c_char_ptr_type)
3395 c_int_ptr_type =      CPtrType(c_int_type)
3396 c_py_unicode_ptr_type = CPtrType(c_py_unicode_type)
3397 c_py_ssize_t_ptr_type =  CPtrType(c_py_ssize_t_type)
3398 c_ssize_t_ptr_type =  CPtrType(c_ssize_t_type)
3399 c_size_t_ptr_type =  CPtrType(c_size_t_type)
3400
3401 # GIL state
3402 c_gilstate_type = CEnumType("PyGILState_STATE", "PyGILState_STATE", True)
3403 c_threadstate_type = CStructOrUnionType("PyThreadState", "struct", None, 1, "PyThreadState")
3404 c_threadstate_ptr_type = CPtrType(c_threadstate_type)
3405
3406 # the Py_buffer type is defined in Builtin.py
3407 c_py_buffer_type = CStructOrUnionType("Py_buffer", "struct", None, 1, "Py_buffer")
3408 c_py_buffer_ptr_type = CPtrType(c_py_buffer_type)
3409
3410 # Not sure whether the unsigned versions and 'long long' should be in there
3411 # long long requires C99 and might be slow, and would always get preferred
3412 # when specialization happens through calling and not indexing
3413 cy_integral_type = FusedType([c_short_type, c_int_type, c_long_type],
3414                              name="integral")
3415 # Omitting long double as it might be slow
3416 cy_floating_type = FusedType([c_float_type, c_double_type], name="floating")
3417 cy_numeric_type = FusedType([c_short_type,
3418                              c_int_type,
3419                              c_long_type,
3420                              c_float_type,
3421                              c_double_type,
3422                              c_float_complex_type,
3423                              c_double_complex_type], name="numeric")
3424
3425 # buffer-related structs
3426 c_buf_diminfo_type =  CStructOrUnionType("__Pyx_Buf_DimInfo", "struct",
3427                                       None, 1, "__Pyx_Buf_DimInfo")
3428 c_pyx_buffer_type = CStructOrUnionType("__Pyx_Buffer", "struct", None, 1, "__Pyx_Buffer")
3429 c_pyx_buffer_ptr_type = CPtrType(c_pyx_buffer_type)
3430 c_pyx_buffer_nd_type = CStructOrUnionType("__Pyx_LocalBuf_ND", "struct",
3431                                       None, 1, "__Pyx_LocalBuf_ND")
3432
3433 cython_memoryview_type = CStructOrUnionType("__pyx_memoryview_obj", "struct",
3434                                       None, 0, "__pyx_memoryview_obj")
3435
3436 memoryviewslice_type = CStructOrUnionType("memoryviewslice", "struct",
3437                                           None, 1, "__Pyx_memviewslice")
3438
3439 modifiers_and_name_to_type = {
3440     #(signed, longness, name) : type
3441     (0,  0, "char"): c_uchar_type,
3442     (1,  0, "char"): c_char_type,
3443     (2,  0, "char"): c_schar_type,
3444
3445     (0, -1, "int"): c_ushort_type,
3446     (0,  0, "int"): c_uint_type,
3447     (0,  1, "int"): c_ulong_type,
3448     (0,  2, "int"): c_ulonglong_type,
3449
3450     (1, -1, "int"): c_short_type,
3451     (1,  0, "int"): c_int_type,
3452     (1,  1, "int"): c_long_type,
3453     (1,  2, "int"): c_longlong_type,
3454
3455     (2, -1, "int"): c_sshort_type,
3456     (2,  0, "int"): c_sint_type,
3457     (2,  1, "int"): c_slong_type,
3458     (2,  2, "int"): c_slonglong_type,
3459
3460     (1,  0, "float"):  c_float_type,
3461     (1,  0, "double"): c_double_type,
3462     (1,  1, "double"): c_longdouble_type,
3463
3464     (1,  0, "complex"):  c_double_complex_type,  # C: float, Python: double => Python wins
3465     (1,  0, "floatcomplex"):  c_float_complex_type,
3466     (1,  0, "doublecomplex"): c_double_complex_type,
3467     (1,  1, "doublecomplex"): c_longdouble_complex_type,
3468
3469     #
3470     (1,  0, "void"): c_void_type,
3471
3472     (1,  0, "bint"):       c_bint_type,
3473     (0,  0, "Py_UNICODE"): c_py_unicode_type,
3474     (0,  0, "Py_UCS4"):    c_py_ucs4_type,
3475     (2,  0, "Py_hash_t"):  c_py_hash_t_type,
3476     (2,  0, "Py_ssize_t"): c_py_ssize_t_type,
3477     (2,  0, "ssize_t") :   c_ssize_t_type,
3478     (0,  0, "size_t") :    c_size_t_type,
3479     (2,  0, "ptrdiff_t") : c_ptrdiff_t_type,
3480
3481     (1,  0, "object"): py_object_type,
3482 }
3483
3484 def is_promotion(src_type, dst_type):
3485     # It's hard to find a hard definition of promotion, but empirical
3486     # evidence suggests that the below is all that's allowed.
3487     if src_type.is_numeric:
3488         if dst_type.same_as(c_int_type):
3489             unsigned = (not src_type.signed)
3490             return (src_type.is_enum or
3491                     (src_type.is_int and
3492                      unsigned + src_type.rank < dst_type.rank))
3493         elif dst_type.same_as(c_double_type):
3494             return src_type.is_float and src_type.rank <= dst_type.rank
3495     return False
3496
3497 def best_match(args, functions, pos=None, env=None):
3498     """
3499     Given a list args of arguments and a list of functions, choose one
3500     to call which seems to be the "best" fit for this list of arguments.
3501     This function is used, e.g., when deciding which overloaded method
3502     to dispatch for C++ classes.
3503
3504     We first eliminate functions based on arity, and if only one
3505     function has the correct arity, we return it. Otherwise, we weight
3506     functions based on how much work must be done to convert the
3507     arguments, with the following priorities:
3508       * identical types or pointers to identical types
3509       * promotions
3510       * non-Python types
3511     That is, we prefer functions where no arguments need converted,
3512     and failing that, functions where only promotions are required, and
3513     so on.
3514
3515     If no function is deemed a good fit, or if two or more functions have
3516     the same weight, we return None (as there is no best match). If pos
3517     is not None, we also generate an error.
3518     """
3519     # TODO: args should be a list of types, not a list of Nodes.
3520     actual_nargs = len(args)
3521
3522     candidates = []
3523     errors = []
3524     for func in functions:
3525         error_mesg = ""
3526         func_type = func.type
3527         if func_type.is_ptr:
3528             func_type = func_type.base_type
3529         # Check function type
3530         if not func_type.is_cfunction:
3531             if not func_type.is_error and pos is not None:
3532                 error_mesg = "Calling non-function type '%s'" % func_type
3533             errors.append((func, error_mesg))
3534             continue
3535         # Check no. of args
3536         max_nargs = len(func_type.args)
3537         min_nargs = max_nargs - func_type.optional_arg_count
3538         if actual_nargs < min_nargs or \
3539             (not func_type.has_varargs and actual_nargs > max_nargs):
3540             if max_nargs == min_nargs and not func_type.has_varargs:
3541                 expectation = max_nargs
3542             elif actual_nargs < min_nargs:
3543                 expectation = "at least %s" % min_nargs
3544             else:
3545                 expectation = "at most %s" % max_nargs
3546             error_mesg = "Call with wrong number of arguments (expected %s, got %s)" \
3547                          % (expectation, actual_nargs)
3548             errors.append((func, error_mesg))
3549             continue
3550         if func_type.templates:
3551             arg_types = [arg.type for arg in args]
3552             deductions = reduce(
3553                 merge_template_deductions,
3554                 [pattern.type.deduce_template_params(actual) for (pattern, actual) in zip(func_type.args, arg_types)],
3555                 {})
3556             if deductions is None:
3557                 errors.append((func, "Unable to deduce type parameters"))
3558             elif len(deductions) < len(func_type.templates):
3559                 errors.append((func, "Unable to deduce type parameter %s" % (
3560                     ", ".join([param.name for param in set(func_type.templates) - set(deductions.keys())]))))
3561             else:
3562                 type_list = [deductions[param] for param in func_type.templates]
3563                 from Symtab import Entry
3564                 specialization = Entry(
3565                     name = func.name + "[%s]" % ",".join([str(t) for t in type_list]),
3566                     cname = func.cname + "<%s>" % ",".join([t.declaration_code("") for t in type_list]),
3567                     type = func_type.specialize(deductions),
3568                     pos = func.pos)
3569                 candidates.append((specialization, specialization.type))
3570         else:
3571             candidates.append((func, func_type))
3572
3573     # Optimize the most common case of no overloading...
3574     if len(candidates) == 1:
3575         return candidates[0][0]
3576     elif len(candidates) == 0:
3577         if pos is not None:
3578             func, errmsg = errors[0]
3579             if len(errors) == 1 or [1 for func, e in errors if e == errmsg]:
3580                 error(pos, errmsg)
3581             else:
3582                 error(pos, "no suitable method found")
3583         return None
3584
3585     possibilities = []
3586     bad_types = []
3587     needed_coercions = {}
3588
3589     for index, (func, func_type) in enumerate(candidates):
3590         score = [0,0,0,0]
3591         for i in range(min(len(args), len(func_type.args))):
3592             src_type = args[i].type
3593             dst_type = func_type.args[i].type
3594
3595             assignable = dst_type.assignable_from(src_type)
3596
3597             # Now take care of normal string literals. So when you call a cdef
3598             # function that takes a char *, the coercion will mean that the
3599             # type will simply become bytes. We need to do this coercion
3600             # manually for overloaded and fused functions
3601             if not assignable and src_type.is_pyobject:
3602                 if (src_type.is_builtin_type and src_type.name == 'str' and
3603                         dst_type.resolve() is c_char_ptr_type):
3604                     c_src_type = c_char_ptr_type
3605                 else:
3606                     c_src_type = src_type.default_coerced_ctype()
3607
3608                 if c_src_type:
3609                     assignable = dst_type.assignable_from(c_src_type)
3610                     if assignable:
3611                         src_type = c_src_type
3612                         needed_coercions[func] = i, dst_type
3613
3614             if assignable:
3615                 if src_type == dst_type or dst_type.same_as(src_type):
3616                     pass # score 0
3617                 elif func_type.is_strict_signature:
3618                     break # exact match requested but not found
3619                 elif is_promotion(src_type, dst_type):
3620                     score[2] += 1
3621                 elif ((src_type.is_int and dst_type.is_int) or
3622                       (src_type.is_float and dst_type.is_float)):
3623                     score[2] += abs(dst_type.rank + (not dst_type.signed) -
3624                                     (src_type.rank + (not src_type.signed))) + 1
3625                 elif not src_type.is_pyobject:
3626                     score[1] += 1
3627                 else:
3628                     score[0] += 1
3629             else:
3630                 error_mesg = "Invalid conversion from '%s' to '%s'"%(src_type,
3631                                                                      dst_type)
3632                 bad_types.append((func, error_mesg))
3633                 break
3634         else:
3635             possibilities.append((score, index, func)) # so we can sort it
3636
3637     if possibilities:
3638         possibilities.sort()
3639         if len(possibilities) > 1:
3640             score1 = possibilities[0][0]
3641             score2 = possibilities[1][0]
3642             if score1 == score2:
3643                 if pos is not None:
3644                     error(pos, "ambiguous overloaded method")
3645                 return None
3646
3647         function = possibilities[0][-1]
3648
3649         if function in needed_coercions and env:
3650             arg_i, coerce_to_type = needed_coercions[function]
3651             args[arg_i] = args[arg_i].coerce_to(coerce_to_type, env)
3652
3653         return function
3654
3655     if pos is not None:
3656         if len(bad_types) == 1:
3657             error(pos, bad_types[0][1])
3658         else:
3659             error(pos, "no suitable method found")
3660
3661     return None
3662
3663 def merge_template_deductions(a, b):
3664     if a is None or b is None:
3665         return None
3666     all = a
3667     for param, value in b.iteritems():
3668         if param in all:
3669             if a[param] != b[param]:
3670                 return None
3671         else:
3672             all[param] = value
3673     return all
3674
3675 def widest_numeric_type(type1, type2):
3676     # Given two numeric types, return the narrowest type
3677     # encompassing both of them.
3678     if type1 == type2:
3679         widest_type = type1
3680     elif type1.is_complex or type2.is_complex:
3681         def real_type(ntype):
3682             if ntype.is_complex:
3683                 return ntype.real_type
3684             return ntype
3685         widest_type = CComplexType(
3686             widest_numeric_type(
3687                 real_type(type1),
3688                 real_type(type2)))
3689     elif type1.is_enum and type2.is_enum:
3690         widest_type = c_int_type
3691     elif type1.rank < type2.rank:
3692         widest_type = type2
3693     elif type1.rank > type2.rank:
3694         widest_type = type1
3695     elif type1.signed < type2.signed:
3696         widest_type = type1
3697     else:
3698         widest_type = type2
3699     return widest_type
3700
3701 def independent_spanning_type(type1, type2):
3702     # Return a type assignable independently from both type1 and
3703     # type2, but do not require any interoperability between the two.
3704     # For example, in "True * 2", it is safe to assume an integer
3705     # result type (so spanning_type() will do the right thing),
3706     # whereas "x = True or 2" must evaluate to a type that can hold
3707     # both a boolean value and an integer, so this function works
3708     # better.
3709     if type1 == type2:
3710         return type1
3711     elif (type1 is c_bint_type or type2 is c_bint_type) and (type1.is_numeric and type2.is_numeric):
3712         # special case: if one of the results is a bint and the other
3713         # is another C integer, we must prevent returning a numeric
3714         # type so that we do not lose the ability to coerce to a
3715         # Python bool if we have to.
3716         return py_object_type
3717     span_type = _spanning_type(type1, type2)
3718     if span_type is None:
3719         return error_type
3720     return span_type
3721
3722 def spanning_type(type1, type2):
3723     # Return a type assignable from both type1 and type2, or
3724     # py_object_type if no better type is found.  Assumes that the
3725     # code that calls this will try a coercion afterwards, which will
3726     # fail if the types cannot actually coerce to a py_object_type.
3727     if type1 == type2:
3728         return type1
3729     elif type1 is py_object_type or type2 is py_object_type:
3730         return py_object_type
3731     elif type1 is c_py_unicode_type or type2 is c_py_unicode_type:
3732         # Py_UNICODE behaves more like a string than an int
3733         return py_object_type
3734     span_type = _spanning_type(type1, type2)
3735     if span_type is None:
3736         return py_object_type
3737     return span_type
3738
3739 def _spanning_type(type1, type2):
3740     if type1.is_numeric and type2.is_numeric:
3741         return widest_numeric_type(type1, type2)
3742     elif type1.is_builtin_type and type1.name == 'float' and type2.is_numeric:
3743         return widest_numeric_type(c_double_type, type2)
3744     elif type2.is_builtin_type and type2.name == 'float' and type1.is_numeric:
3745         return widest_numeric_type(type1, c_double_type)
3746     elif type1.is_extension_type and type2.is_extension_type:
3747         return widest_extension_type(type1, type2)
3748     elif type1.is_pyobject or type2.is_pyobject:
3749         return py_object_type
3750     elif type1.assignable_from(type2):
3751         if type1.is_extension_type and type1.typeobj_is_imported():
3752             # external types are unsafe, so we use PyObject instead
3753             return py_object_type
3754         return type1
3755     elif type2.assignable_from(type1):
3756         if type2.is_extension_type and type2.typeobj_is_imported():
3757             # external types are unsafe, so we use PyObject instead
3758             return py_object_type
3759         return type2
3760     else:
3761         return None
3762
3763 def widest_extension_type(type1, type2):
3764     if type1.typeobj_is_imported() or type2.typeobj_is_imported():
3765         return py_object_type
3766     while True:
3767         if type1.subtype_of(type2):
3768             return type2
3769         elif type2.subtype_of(type1):
3770             return type1
3771         type1, type2 = type1.base_type, type2.base_type
3772         if type1 is None or type2 is None:
3773             return py_object_type
3774
3775 def simple_c_type(signed, longness, name):
3776     # Find type descriptor for simple type given name and modifiers.
3777     # Returns None if arguments don't make sense.
3778     return modifiers_and_name_to_type.get((signed, longness, name))
3779
3780 def parse_basic_type(name):
3781     base = None
3782     if name.startswith('p_'):
3783         base = parse_basic_type(name[2:])
3784     elif name.startswith('p'):
3785         base = parse_basic_type(name[1:])
3786     elif name.endswith('*'):
3787         base = parse_basic_type(name[:-1])
3788     if base:
3789         return CPtrType(base)
3790     #
3791     basic_type = simple_c_type(1, 0, name)
3792     if basic_type:
3793         return basic_type
3794     #
3795     signed = 1
3796     longness = 0
3797     if name == 'Py_UNICODE':
3798         signed = 0
3799     elif name == 'Py_UCS4':
3800         signed = 0
3801     elif name == 'Py_hash_t':
3802         signed = 2
3803     elif name == 'Py_ssize_t':
3804         signed = 2
3805     elif name == 'ssize_t':
3806         signed = 2
3807     elif name == 'size_t':
3808         signed = 0
3809     else:
3810         if name.startswith('u'):
3811             name = name[1:]
3812             signed = 0
3813         elif (name.startswith('s') and
3814               not name.startswith('short')):
3815             name = name[1:]
3816             signed = 2
3817         longness = 0
3818         while name.startswith('short'):
3819             name = name.replace('short', '', 1).strip()
3820             longness -= 1
3821         while name.startswith('long'):
3822             name = name.replace('long', '', 1).strip()
3823             longness += 1
3824         if longness != 0 and not name:
3825             name = 'int'
3826     return simple_c_type(signed, longness, name)
3827
3828 def c_array_type(base_type, size):
3829     # Construct a C array type.
3830     if base_type is error_type:
3831         return error_type
3832     else:
3833         return CArrayType(base_type, size)
3834
3835 def c_ptr_type(base_type):
3836     # Construct a C pointer type.
3837     if base_type is error_type:
3838         return error_type
3839     else:
3840         return CPtrType(base_type)
3841
3842 def c_ref_type(base_type):
3843     # Construct a C reference type
3844     if base_type is error_type:
3845         return error_type
3846     else:
3847         return CReferenceType(base_type)
3848
3849 def c_const_type(base_type):
3850     # Construct a C const type.
3851     if base_type is error_type:
3852         return error_type
3853     else:
3854         return CConstType(base_type)
3855
3856 def same_type(type1, type2):
3857     return type1.same_as(type2)
3858
3859 def assignable_from(type1, type2):
3860     return type1.assignable_from(type2)
3861
3862 def typecast(to_type, from_type, expr_code):
3863     #  Return expr_code cast to a C type which can be
3864     #  assigned to to_type, assuming its existing C type
3865     #  is from_type.
3866     if (to_type is from_type or
3867             (not to_type.is_pyobject and assignable_from(to_type, from_type))):
3868         return expr_code
3869     elif (to_type is py_object_type and from_type and
3870             from_type.is_builtin_type and from_type.name != 'type'):
3871         # no cast needed, builtins are PyObject* already
3872         return expr_code
3873     else:
3874         #print "typecast: to", to_type, "from", from_type ###
3875         return to_type.cast_code(expr_code)