Cython/Compiler/PyrexTypes.py

   1 #
   2 #   Pyrex - Types
   3 #
   4
   5 from Code import UtilityCode
   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 Pyrex types including pseudo-types.
  14
  15     def can_coerce_to_pyobject(self, env):
  16         return False
  17
  18     def cast_code(self, expr_code):
  19         return "((%s)%s)" % (self.declaration_code(""), expr_code)
  20
  21     def specialization_name(self):
  22         return self.declaration_code("").replace(" ", "__")
  23
  24     def base_declaration_code(self, base_code, entity_code):
  25         if entity_code:
  26             return "%s %s" % (base_code, entity_code)
  27         else:
  28             return base_code
  29
  30 class PyrexType(BaseType):
  31     #
  32     #  Base class for all Pyrex types.
  33     #
  34     #  is_pyobject           boolean     Is a Python object type
  35     #  is_extension_type     boolean     Is a Python extension type
  36     #  is_numeric            boolean     Is a C numeric type
  37     #  is_int                boolean     Is a C integer type
  38     #  is_float              boolean     Is a C floating point type
  39     #  is_complex            boolean     Is a C complex type
  40     #  is_void               boolean     Is the C void type
  41     #  is_array              boolean     Is a C array type
  42     #  is_ptr                boolean     Is a C pointer type
  43     #  is_null_ptr           boolean     Is the type of NULL
  44     #  is_reference          boolean     Is a C reference type
  45     #  is_cfunction          boolean     Is a C function type
  46     #  is_struct_or_union    boolean     Is a C struct or union type
  47     #  is_struct             boolean     Is a C struct type
  48     #  is_enum               boolean     Is a C enum type
  49     #  is_typedef            boolean     Is a typedef type
  50     #  is_string             boolean     Is a C char * type
  51     #  is_unicode            boolean     Is a UTF-8 encoded C char * type
  52     #  is_unicode_char       boolean     Is either Py_UCS4 or Py_UNICODE
  53     #  is_returncode         boolean     Is used only to signal exceptions
  54     #  is_error              boolean     Is the dummy error type
  55     #  is_buffer             boolean     Is buffer access type
  56     #  has_attributes        boolean     Has C dot-selectable attributes
  57     #  default_value         string      Initial value
  58     #
  59     #  declaration_code(entity_code,
  60     #      for_display = 0, dll_linkage = None, pyrex = 0)
  61     #    Returns a code fragment for the declaration of an entity
  62     #    of this type, given a code fragment for the entity.
  63     #    * If for_display, this is for reading by a human in an error
  64     #      message; otherwise it must be valid C code.
  65     #    * If dll_linkage is not None, it must be 'DL_EXPORT' or
  66     #      'DL_IMPORT', and will be added to the base type part of
  67     #      the declaration.
  68     #    * If pyrex = 1, this is for use in a 'cdef extern'
  69     #      statement of a Pyrex include file.
  70     #
  71     #  assignable_from(src_type)
  72     #    Tests whether a variable of this type can be
  73     #    assigned a value of type src_type.
  74     #
  75     #  same_as(other_type)
  76     #    Tests whether this type represents the same type
  77     #    as other_type.
  78     #
  79     #  as_argument_type():
  80     #    Coerces array type into pointer type for use as
  81     #    a formal argument type.
  82     #
  83
  84     is_pyobject = 0
  85     is_unspecified = 0
  86     is_extension_type = 0
  87     is_builtin_type = 0
  88     is_numeric = 0
  89     is_int = 0
  90     is_float = 0
  91     is_complex = 0
  92     is_void = 0
  93     is_array = 0
  94     is_ptr = 0
  95     is_null_ptr = 0
  96     is_reference = 0
  97     is_cfunction = 0
  98     is_struct_or_union = 0
  99     is_cpp_class = 0
 100     is_struct = 0
 101     is_enum = 0
 102     is_typedef = 0
 103     is_string = 0
 104     is_unicode = 0
 105     is_unicode_char = 0
 106     is_returncode = 0
 107     is_error = 0
 108     is_buffer = 0
 109     has_attributes = 0
 110     default_value = ""
 111
 112     def resolve(self):
 113         # If a typedef, returns the base type.
 114         return self
 115
 116     def specialize(self, values):
 117         # TODO(danilo): Override wherever it makes sense.
 118         return self
 119
 120     def literal_code(self, value):
 121         # Returns a C code fragment representing a literal
 122         # value of this type.
 123         return str(value)
 124
 125     def __str__(self):
 126         return self.declaration_code("", for_display = 1).strip()
 127
 128     def same_as(self, other_type, **kwds):
 129         return self.same_as_resolved_type(other_type.resolve(), **kwds)
 130
 131     def same_as_resolved_type(self, other_type):
 132         return self == other_type or other_type is error_type
 133
 134     def subtype_of(self, other_type):
 135         return self.subtype_of_resolved_type(other_type.resolve())
 136
 137     def subtype_of_resolved_type(self, other_type):
 138         return self.same_as(other_type)
 139
 140     def assignable_from(self, src_type):
 141         return self.assignable_from_resolved_type(src_type.resolve())
 142
 143     def assignable_from_resolved_type(self, src_type):
 144         return self.same_as(src_type)
 145
 146     def as_argument_type(self):
 147         return self
 148
 149     def is_complete(self):
 150         # A type is incomplete if it is an unsized array,
 151         # a struct whose attributes are not defined, etc.
 152         return 1
 153
 154     def is_simple_buffer_dtype(self):
 155         return (self.is_int or self.is_float or self.is_complex or self.is_pyobject or
 156                 self.is_extension_type or self.is_ptr)
 157
 158     def struct_nesting_depth(self):
 159         # Returns the number levels of nested structs. This is
 160         # used for constructing a stack for walking the run-time
 161         # type information of the struct.
 162         return 1
 163
 164
 165 def public_decl(base_code, dll_linkage):
 166     if dll_linkage:
 167         return "%s(%s)" % (dll_linkage, base_code)
 168     else:
 169         return base_code
 170
 171 def create_typedef_type(name, base_type, cname, is_external=0):
 172     if base_type.is_complex:
 173         if is_external:
 174             raise ValueError("Complex external typedefs not supported")
 175         return base_type
 176     else:
 177         return CTypedefType(name, base_type, cname, is_external)
 178
 179
 180 class CTypedefType(BaseType):
 181     #
 182     #  Pseudo-type defined with a ctypedef statement in a
 183     #  'cdef extern from' block. Delegates most attribute
 184     #  lookups to the base type. ANYTHING NOT DEFINED
 185     #  HERE IS DELEGATED!
 186     #
 187     #  qualified_name      string
 188     #  typedef_name        string
 189     #  typedef_cname       string
 190     #  typedef_base_type   PyrexType
 191     #  typedef_is_external bool
 192
 193     is_typedef = 1
 194     typedef_is_external = 0
 195
 196     to_py_utility_code = None
 197     from_py_utility_code = None
 198
 199
 200     def __init__(self, name, base_type, cname, is_external=0):
 201         assert not base_type.is_complex
 202         self.typedef_name = name
 203         self.typedef_cname = cname
 204         self.typedef_base_type = base_type
 205         self.typedef_is_external = is_external
 206
 207     def resolve(self):
 208         return self.typedef_base_type.resolve()
 209
 210     def declaration_code(self, entity_code,
 211             for_display = 0, dll_linkage = None, pyrex = 0):
 212         if pyrex or for_display:
 213             base_code = self.typedef_name
 214         else:
 215             base_code = public_decl(self.typedef_cname, dll_linkage)
 216         return self.base_declaration_code(base_code, entity_code)
 217
 218     def as_argument_type(self):
 219         return self
 220
 221     def cast_code(self, expr_code):
 222         # If self is really an array (rather than pointer), we can't cast.
 223         # For example, the gmp mpz_t.
 224         if self.typedef_base_type.is_array:
 225             base_type = self.typedef_base_type.base_type
 226             return CPtrType(base_type).cast_code(expr_code)
 227         else:
 228             return BaseType.cast_code(self, expr_code)
 229
 230     def __repr__(self):
 231         return "<CTypedefType %s>" % self.typedef_cname
 232
 233     def __str__(self):
 234         return self.typedef_name
 235
 236     def _create_utility_code(self, template_utility_code,
 237                              template_function_name):
 238         type_name = self.typedef_cname.replace(" ","_").replace("::","__")
 239         utility_code = template_utility_code.specialize(
 240             type     = self.typedef_cname,
 241             TypeName = type_name)
 242         function_name = template_function_name % type_name
 243         return utility_code, function_name
 244
 245     def create_to_py_utility_code(self, env):
 246         if self.typedef_is_external:
 247             if not self.to_py_utility_code:
 248                 base_type = self.typedef_base_type
 249                 if type(base_type) is CIntType:
 250                     # Various subclasses have special methods
 251                     # that should be inherited.
 252                     self.to_py_utility_code, self.to_py_function = \
 253                         self._create_utility_code(c_typedef_int_to_py_function,
 254                                                   '__Pyx_PyInt_to_py_%s')
 255                 elif base_type.is_float:
 256                     pass # XXX implement!
 257                 elif base_type.is_complex:
 258                     pass # XXX implement!
 259                     pass
 260             if self.to_py_utility_code:
 261                 env.use_utility_code(self.to_py_utility_code)
 262                 return True
 263         # delegation
 264         return self.typedef_base_type.create_to_py_utility_code(env)
 265
 266     def create_from_py_utility_code(self, env):
 267         if self.typedef_is_external:
 268             if not self.from_py_utility_code:
 269                 base_type = self.typedef_base_type
 270                 if type(base_type) is CIntType:
 271                     # Various subclasses have special methods
 272                     # that should be inherited.
 273                     self.from_py_utility_code, self.from_py_function = \
 274                         self._create_utility_code(c_typedef_int_from_py_function,
 275                                                   '__Pyx_PyInt_from_py_%s')
 276                 elif base_type.is_float:
 277                     pass # XXX implement!
 278                 elif base_type.is_complex:
 279                     pass # XXX implement!
 280             if self.from_py_utility_code:
 281                 env.use_utility_code(self.from_py_utility_code)
 282                 return True
 283         # delegation
 284         return self.typedef_base_type.create_from_py_utility_code(env)
 285
 286     def error_condition(self, result_code):
 287         if self.typedef_is_external:
 288             if self.exception_value:
 289                 condition = "(%s == (%s)%s)" % (
 290                     result_code, self.typedef_cname, self.exception_value)
 291                 if self.exception_check:
 292                     condition += " && PyErr_Occurred()"
 293                 return condition
 294         # delegation
 295         return self.typedef_base_type.error_condition(result_code)
 296
 297     def __getattr__(self, name):
 298         return getattr(self.typedef_base_type, name)
 299
 300
 301 class BufferType(BaseType):
 302     #
 303     #  Delegates most attribute
 304     #  lookups to the base type. ANYTHING NOT DEFINED
 305     #  HERE IS DELEGATED!
 306
 307     # dtype            PyrexType
 308     # ndim             int
 309     # mode             str
 310     # negative_indices bool
 311     # cast             bool
 312     # is_buffer        bool
 313     # writable         bool
 314
 315     is_buffer = 1
 316     writable = True
 317     def __init__(self, base, dtype, ndim, mode, negative_indices, cast):
 318         self.base = base
 319         self.dtype = dtype
 320         self.ndim = ndim
 321         self.buffer_ptr_type = CPtrType(dtype)
 322         self.mode = mode
 323         self.negative_indices = negative_indices
 324         self.cast = cast
 325
 326     def as_argument_type(self):
 327         return self
 328
 329     def __getattr__(self, name):
 330         return getattr(self.base, name)
 331
 332     def __repr__(self):
 333         return "<BufferType %r>" % self.base
 334
 335
 336 class PyObjectType(PyrexType):
 337     #
 338     #  Base class for all Python object types (reference-counted).
 339     #
 340     #  buffer_defaults  dict or None     Default options for bu
 341
 342     name = "object"
 343     is_pyobject = 1
 344     default_value = "0"
 345     buffer_defaults = None
 346     is_extern = False
 347     is_subclassed = False
 348
 349     def __str__(self):
 350         return "Python object"
 351
 352     def __repr__(self):
 353         return "<PyObjectType>"
 354
 355     def can_coerce_to_pyobject(self, env):
 356         return True
 357
 358     def default_coerced_ctype(self):
 359         "The default C type that this Python type coerces to, or None."
 360         return None
 361
 362     def assignable_from(self, src_type):
 363         # except for pointers, conversion will be attempted
 364         return not src_type.is_ptr or src_type.is_string
 365
 366     def declaration_code(self, entity_code,
 367             for_display = 0, dll_linkage = None, pyrex = 0):
 368         if pyrex or for_display:
 369             base_code = "object"
 370         else:
 371             base_code = public_decl("PyObject", dll_linkage)
 372             entity_code = "*%s" % entity_code
 373         return self.base_declaration_code(base_code, entity_code)
 374
 375     def as_pyobject(self, cname):
 376         if (not self.is_complete()) or self.is_extension_type:
 377             return "(PyObject *)" + cname
 378         else:
 379             return cname
 380
 381 class BuiltinObjectType(PyObjectType):
 382     #  objstruct_cname  string           Name of PyObject struct
 383
 384     is_builtin_type = 1
 385     has_attributes = 1
 386     base_type = None
 387     module_name = '__builtin__'
 388
 389     # fields that let it look like an extension type
 390     vtabslot_cname = None
 391     vtabstruct_cname = None
 392     vtabptr_cname = None
 393     typedef_flag = True
 394     is_external = True
 395
 396     def __init__(self, name, cname, objstruct_cname=None):
 397         self.name = name
 398         self.cname = cname
 399         self.typeptr_cname = "(&%s)" % cname
 400         self.objstruct_cname = objstruct_cname
 401
 402     def set_scope(self, scope):
 403         self.scope = scope
 404         if scope:
 405             scope.parent_type = self
 406
 407     def __str__(self):
 408         return "%s object" % self.name
 409
 410     def __repr__(self):
 411         return "<%s>"% self.cname
 412
 413     def default_coerced_ctype(self):
 414         if self.name == 'bytes':
 415             return c_char_ptr_type
 416         elif self.name == 'bool':
 417             return c_bint_type
 418         elif self.name == 'float':
 419             return c_double_type
 420         return None
 421
 422     def assignable_from(self, src_type):
 423         if isinstance(src_type, BuiltinObjectType):
 424             return src_type.name == self.name
 425         elif src_type.is_extension_type:
 426             return (src_type.module_name == '__builtin__' and
 427                     src_type.name == self.name)
 428         else:
 429             return True
 430
 431     def typeobj_is_available(self):
 432         return True
 433
 434     def attributes_known(self):
 435         return True
 436
 437     def subtype_of(self, type):
 438         return type.is_pyobject and self.assignable_from(type)
 439
 440     def type_check_function(self, exact=True):
 441         type_name = self.name
 442         if type_name == 'str':
 443             type_check = 'PyString_Check'
 444         elif type_name == 'frozenset':
 445             type_check = 'PyFrozenSet_Check'
 446         else:
 447             type_check = 'Py%s_Check' % type_name.capitalize()
 448         if exact and type_name not in ('bool', 'slice'):
 449             type_check += 'Exact'
 450         return type_check
 451
 452     def isinstance_code(self, arg):
 453         return '%s(%s)' % (self.type_check_function(exact=False), arg)
 454
 455     def type_test_code(self, arg, notnone=False):
 456         type_check = self.type_check_function(exact=True)
 457         check = 'likely(%s(%s))' % (type_check, arg)
 458         if not notnone:
 459             check = check + ('||((%s) == Py_None)' % arg)
 460         error = '(PyErr_Format(PyExc_TypeError, "Expected %s, got %%.200s", Py_TYPE(%s)->tp_name), 0)' % (self.name, arg)
 461         return check + '||' + error
 462
 463     def declaration_code(self, entity_code,
 464             for_display = 0, dll_linkage = None, pyrex = 0):
 465         if pyrex or for_display:
 466             base_code = self.name
 467         else:
 468             base_code = public_decl("PyObject", dll_linkage)
 469             entity_code = "*%s" % entity_code
 470         return self.base_declaration_code(base_code, entity_code)
 471
 472     def cast_code(self, expr_code, to_object_struct = False):
 473         return "((%s*)%s)" % (
 474             to_object_struct and self.objstruct_cname or "PyObject", # self.objstruct_cname may be None
 475             expr_code)
 476
 477
 478 class PyExtensionType(PyObjectType):
 479     #
 480     #  A Python extension type.
 481     #
 482     #  name             string
 483     #  scope            CClassScope      Attribute namespace
 484     #  visibility       string
 485     #  typedef_flag     boolean
 486     #  base_type        PyExtensionType or None
 487     #  module_name      string or None   Qualified name of defining module
 488     #  objstruct_cname  string           Name of PyObject struct
 489     #  objtypedef_cname string           Name of PyObject struct typedef
 490     #  typeobj_cname    string or None   C code fragment referring to type object
 491     #  typeptr_cname    string or None   Name of pointer to external type object
 492     #  vtabslot_cname   string           Name of C method table member
 493     #  vtabstruct_cname string           Name of C method table struct
 494     #  vtabptr_cname    string           Name of pointer to C method table
 495     #  vtable_cname     string           Name of C method table definition
 496
 497     is_extension_type = 1
 498     has_attributes = 1
 499
 500     objtypedef_cname = None
 501
 502     def __init__(self, name, typedef_flag, base_type, is_external=0):
 503         self.name = name
 504         self.scope = None
 505         self.typedef_flag = typedef_flag
 506         if base_type is not None:
 507             base_type.is_subclassed = True
 508         self.base_type = base_type
 509         self.module_name = None
 510         self.objstruct_cname = None
 511         self.typeobj_cname = None
 512         self.typeptr_cname = None
 513         self.vtabslot_cname = None
 514         self.vtabstruct_cname = None
 515         self.vtabptr_cname = None
 516         self.vtable_cname = None
 517         self.is_external = is_external
 518
 519     def set_scope(self, scope):
 520         self.scope = scope
 521         if scope:
 522             scope.parent_type = self
 523
 524     def subtype_of_resolved_type(self, other_type):
 525         if other_type.is_extension_type:
 526             return self is other_type or (
 527                 self.base_type and self.base_type.subtype_of(other_type))
 528         else:
 529             return other_type is py_object_type
 530
 531     def typeobj_is_available(self):
 532         # Do we have a pointer to the type object?
 533         return self.typeptr_cname
 534
 535     def typeobj_is_imported(self):
 536         # If we don't know the C name of the type object but we do
 537         # know which module it's defined in, it will be imported.
 538         return self.typeobj_cname is None and self.module_name is not None
 539
 540     def assignable_from(self, src_type):
 541         if self == src_type:
 542             return True
 543         if isinstance(src_type, PyExtensionType):
 544             if src_type.base_type is not None:
 545                 return self.assignable_from(src_type.base_type)
 546         return False
 547
 548     def declaration_code(self, entity_code,
 549             for_display = 0, dll_linkage = None, pyrex = 0, deref = 0):
 550         if pyrex or for_display:
 551             base_code = self.name
 552         else:
 553             if self.typedef_flag:
 554                 objstruct = self.objstruct_cname
 555             else:
 556                 objstruct = "struct %s" % self.objstruct_cname
 557             base_code = public_decl(objstruct, dll_linkage)
 558             if deref:
 559                 assert not entity_code
 560             else:
 561                 entity_code = "*%s" % entity_code
 562         return self.base_declaration_code(base_code, entity_code)
 563
 564     def type_test_code(self, py_arg, notnone=False):
 565
 566         none_check = "((%s) == Py_None)" % py_arg
 567         type_check = "likely(__Pyx_TypeTest(%s, %s))" % (
 568             py_arg, self.typeptr_cname)
 569         if notnone:
 570             return type_check
 571         else:
 572             return "likely(%s || %s)" % (none_check, type_check)
 573
 574     def attributes_known(self):
 575         return self.scope is not None
 576
 577     def __str__(self):
 578         return self.name
 579
 580     def __repr__(self):
 581         return "<PyExtensionType %s%s>" % (self.scope.class_name,
 582             ("", " typedef")[self.typedef_flag])
 583
 584
 585 class CType(PyrexType):
 586     #
 587     #  Base class for all C types (non-reference-counted).
 588     #
 589     #  to_py_function     string     C function for converting to Python object
 590     #  from_py_function   string     C function for constructing from Python object
 591     #
 592
 593     to_py_function = None
 594     from_py_function = None
 595     exception_value = None
 596     exception_check = 1
 597
 598     def create_to_py_utility_code(self, env):
 599         return self.to_py_function is not None
 600
 601     def create_from_py_utility_code(self, env):
 602         return self.from_py_function is not None
 603
 604     def can_coerce_to_pyobject(self, env):
 605         return self.create_to_py_utility_code(env)
 606
 607     def error_condition(self, result_code):
 608         conds = []
 609         if self.is_string:
 610             conds.append("(!%s)" % result_code)
 611         elif self.exception_value is not None:
 612             conds.append("(%s == (%s)%s)" % (result_code, self.sign_and_name(), self.exception_value))
 613         if self.exception_check:
 614             conds.append("PyErr_Occurred()")
 615         if len(conds) > 0:
 616             return " && ".join(conds)
 617         else:
 618             return 0
 619
 620
 621 class CVoidType(CType):
 622     #
 623     #   C "void" type
 624     #
 625
 626     is_void = 1
 627
 628     def __repr__(self):
 629         return "<CVoidType>"
 630
 631     def declaration_code(self, entity_code,
 632             for_display = 0, dll_linkage = None, pyrex = 0):
 633         if pyrex or for_display:
 634             base_code = "void"
 635         else:
 636             base_code = public_decl("void", dll_linkage)
 637         return self.base_declaration_code(base_code, entity_code)
 638
 639     def is_complete(self):
 640         return 0
 641
 642
 643 class CNumericType(CType):
 644     #
 645     #   Base class for all C numeric types.
 646     #
 647     #   rank      integer     Relative size
 648     #   signed    integer     0 = unsigned, 1 = unspecified, 2 = explicitly signed
 649     #
 650
 651     is_numeric = 1
 652     default_value = "0"
 653     has_attributes = True
 654     scope = None
 655
 656     sign_words = ("unsigned ", "", "signed ")
 657
 658     def __init__(self, rank, signed = 1):
 659         self.rank = rank
 660         self.signed = signed
 661
 662     def sign_and_name(self):
 663         s = self.sign_words[self.signed]
 664         n = rank_to_type_name[self.rank]
 665         return s + n
 666
 667     def __repr__(self):
 668         return "<CNumericType %s>" % self.sign_and_name()
 669
 670     def declaration_code(self, entity_code,
 671             for_display = 0, dll_linkage = None, pyrex = 0):
 672         type_name = self.sign_and_name()
 673         if pyrex or for_display:
 674             base_code = type_name.replace('PY_LONG_LONG', 'long long')
 675         else:
 676             base_code = public_decl(type_name, dll_linkage)
 677         return self.base_declaration_code(base_code, entity_code)
 678
 679     def attributes_known(self):
 680         if self.scope is None:
 681             import Symtab
 682             self.scope = scope = Symtab.CClassScope(
 683                     '',
 684                     None,
 685                     visibility="extern")
 686             scope.parent_type = self
 687             scope.directives = {}
 688             entry = scope.declare_cfunction(
 689                     "conjugate",
 690                     CFuncType(self, [CFuncTypeArg("self", self, None)], nogil=True),
 691                     pos=None,
 692                     defining=1,
 693                     cname=" ")
 694         return True
 695
 696
 697 type_conversion_predeclarations = ""
 698 type_conversion_functions = ""
 699
 700 c_int_from_py_function = UtilityCode(
 701 proto="""
 702 static CYTHON_INLINE %(type)s __Pyx_PyInt_As%(SignWord)s%(TypeName)s(PyObject *);
 703 """,
 704 impl="""
 705 static CYTHON_INLINE %(type)s __Pyx_PyInt_As%(SignWord)s%(TypeName)s(PyObject* x) {
 706     const %(type)s neg_one = (%(type)s)-1, const_zero = 0;
 707     const int is_unsigned = neg_one > const_zero;
 708     if (sizeof(%(type)s) < sizeof(long)) {
 709         long val = __Pyx_PyInt_AsLong(x);
 710         if (unlikely(val != (long)(%(type)s)val)) {
 711             if (!unlikely(val == -1 && PyErr_Occurred())) {
 712                 PyErr_SetString(PyExc_OverflowError,
 713                     (is_unsigned && unlikely(val < 0)) ?
 714                     "can't convert negative value to %(type)s" :
 715                     "value too large to convert to %(type)s");
 716             }
 717             return (%(type)s)-1;
 718         }
 719         return (%(type)s)val;
 720     }
 721     return (%(type)s)__Pyx_PyInt_As%(SignWord)sLong(x);
 722 }
 723 """) #fool emacs: '
 724
 725 c_long_from_py_function = UtilityCode(
 726 proto="""
 727 static CYTHON_INLINE %(type)s __Pyx_PyInt_As%(SignWord)s%(TypeName)s(PyObject *);
 728 """,
 729 impl="""
 730 static CYTHON_INLINE %(type)s __Pyx_PyInt_As%(SignWord)s%(TypeName)s(PyObject* x) {
 731     const %(type)s neg_one = (%(type)s)-1, const_zero = 0;
 732     const int is_unsigned = neg_one > const_zero;
 733 #if PY_VERSION_HEX < 0x03000000
 734     if (likely(PyInt_Check(x))) {
 735         long val = PyInt_AS_LONG(x);
 736         if (is_unsigned && unlikely(val < 0)) {
 737             PyErr_SetString(PyExc_OverflowError,
 738                             "can't convert negative value to %(type)s");
 739             return (%(type)s)-1;
 740         }
 741         return (%(type)s)val;
 742     } else
 743 #endif
 744     if (likely(PyLong_Check(x))) {
 745         if (is_unsigned) {
 746             if (unlikely(Py_SIZE(x) < 0)) {
 747                 PyErr_SetString(PyExc_OverflowError,
 748                                 "can't convert negative value to %(type)s");
 749                 return (%(type)s)-1;
 750             }
 751             return PyLong_AsUnsigned%(TypeName)s(x);
 752         } else {
 753             return PyLong_As%(TypeName)s(x);
 754         }
 755     } else {
 756         %(type)s val;
 757         PyObject *tmp = __Pyx_PyNumber_Int(x);
 758         if (!tmp) return (%(type)s)-1;
 759         val = __Pyx_PyInt_As%(SignWord)s%(TypeName)s(tmp);
 760         Py_DECREF(tmp);
 761         return val;
 762     }
 763 }
 764 """)
 765
 766 c_typedef_int_from_py_function = UtilityCode(
 767 proto="""
 768 static CYTHON_INLINE %(type)s __Pyx_PyInt_from_py_%(TypeName)s(PyObject *);
 769 """,
 770 impl="""
 771 static CYTHON_INLINE %(type)s __Pyx_PyInt_from_py_%(TypeName)s(PyObject* x) {
 772     const %(type)s neg_one = (%(type)s)-1, const_zero = (%(type)s)0;
 773     const int is_unsigned = const_zero < neg_one;
 774     if (sizeof(%(type)s) == sizeof(char)) {
 775         if (is_unsigned)
 776             return (%(type)s)__Pyx_PyInt_AsUnsignedChar(x);
 777         else
 778             return (%(type)s)__Pyx_PyInt_AsSignedChar(x);
 779     } else if (sizeof(%(type)s) == sizeof(short)) {
 780         if (is_unsigned)
 781             return (%(type)s)__Pyx_PyInt_AsUnsignedShort(x);
 782         else
 783             return (%(type)s)__Pyx_PyInt_AsSignedShort(x);
 784     } else if (sizeof(%(type)s) == sizeof(int)) {
 785         if (is_unsigned)
 786             return (%(type)s)__Pyx_PyInt_AsUnsignedInt(x);
 787         else
 788             return (%(type)s)__Pyx_PyInt_AsSignedInt(x);
 789     } else if (sizeof(%(type)s) == sizeof(long)) {
 790         if (is_unsigned)
 791             return (%(type)s)__Pyx_PyInt_AsUnsignedLong(x);
 792         else
 793             return (%(type)s)__Pyx_PyInt_AsSignedLong(x);
 794     } else if (sizeof(%(type)s) == sizeof(PY_LONG_LONG)) {
 795         if (is_unsigned)
 796             return (%(type)s)__Pyx_PyInt_AsUnsignedLongLong(x);
 797         else
 798             return (%(type)s)__Pyx_PyInt_AsSignedLongLong(x);
 799     }  else {
 800         %(type)s val;
 801         PyObject *v = __Pyx_PyNumber_Int(x);
 802         #if PY_VERSION_HEX < 0x03000000
 803         if (likely(v) && !PyLong_Check(v)) {
 804             PyObject *tmp = v;
 805             v = PyNumber_Long(tmp);
 806             Py_DECREF(tmp);
 807         }
 808         #endif
 809         if (likely(v)) {
 810             int one = 1; int is_little = (int)*(unsigned char *)&one;
 811             unsigned char *bytes = (unsigned char *)&val;
 812             int ret = _PyLong_AsByteArray((PyLongObject *)v,
 813                                           bytes, sizeof(val),
 814                                           is_little, !is_unsigned);
 815             Py_DECREF(v);
 816             if (likely(!ret))
 817                 return val;
 818         }
 819         return (%(type)s)-1;
 820     }
 821 }
 822 """)
 823
 824 c_typedef_int_to_py_function = UtilityCode(
 825 proto="""
 826 static CYTHON_INLINE PyObject *__Pyx_PyInt_to_py_%(TypeName)s(%(type)s);
 827 """,
 828 impl="""
 829 static CYTHON_INLINE PyObject *__Pyx_PyInt_to_py_%(TypeName)s(%(type)s val) {
 830     const %(type)s neg_one = (%(type)s)-1, const_zero = (%(type)s)0;
 831     const int is_unsigned = const_zero < neg_one;
 832     if ((sizeof(%(type)s) == sizeof(char))  ||
 833         (sizeof(%(type)s) == sizeof(short))) {
 834         return PyInt_FromLong((long)val);
 835     } else if ((sizeof(%(type)s) == sizeof(int)) ||
 836                (sizeof(%(type)s) == sizeof(long))) {
 837         if (is_unsigned)
 838             return PyLong_FromUnsignedLong((unsigned long)val);
 839         else
 840             return PyInt_FromLong((long)val);
 841     } else if (sizeof(%(type)s) == sizeof(PY_LONG_LONG)) {
 842         if (is_unsigned)
 843             return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)val);
 844         else
 845             return PyLong_FromLongLong((PY_LONG_LONG)val);
 846     } else {
 847         int one = 1; int little = (int)*(unsigned char *)&one;
 848         unsigned char *bytes = (unsigned char *)&val;
 849         return _PyLong_FromByteArray(bytes, sizeof(%(type)s),
 850                                      little, !is_unsigned);
 851     }
 852 }
 853 """)
 854
 855 class CIntType(CNumericType):
 856
 857     is_int = 1
 858     typedef_flag = 0
 859     to_py_function = None
 860     from_py_function = None
 861     exception_value = -1
 862
 863     def __init__(self, rank, signed = 1):
 864         CNumericType.__init__(self, rank, signed)
 865         if self.to_py_function is None:
 866             self.to_py_function = self.get_to_py_type_conversion()
 867         if self.from_py_function is None:
 868             self.from_py_function = self.get_from_py_type_conversion()
 869
 870     def get_to_py_type_conversion(self):
 871         if self.rank < list(rank_to_type_name).index('int'):
 872             # This assumes sizeof(short) < sizeof(int)
 873             return "PyInt_FromLong"
 874         else:
 875             # Py{Int|Long}_From[Unsigned]Long[Long]
 876             Prefix = "Int"
 877             SignWord = ""
 878             TypeName = "Long"
 879             if not self.signed:
 880                 Prefix = "Long"
 881                 SignWord = "Unsigned"
 882             if self.rank >= list(rank_to_type_name).index('PY_LONG_LONG'):
 883                 Prefix = "Long"
 884                 TypeName = "LongLong"
 885             return "Py%s_From%s%s" % (Prefix, SignWord, TypeName)
 886
 887     def get_from_py_type_conversion(self):
 888         type_name = rank_to_type_name[self.rank]
 889         type_name = type_name.replace("PY_LONG_LONG", "long long")
 890         TypeName = type_name.title().replace(" ", "")
 891         SignWord = self.sign_words[self.signed].strip().title()
 892         if self.rank >= list(rank_to_type_name).index('long'):
 893             utility_code = c_long_from_py_function
 894         else:
 895             utility_code = c_int_from_py_function
 896         utility_code.specialize(self,
 897                                 SignWord=SignWord,
 898                                 TypeName=TypeName)
 899         func_name = "__Pyx_PyInt_As%s%s" % (SignWord, TypeName)
 900         return func_name
 901
 902     def assignable_from_resolved_type(self, src_type):
 903         return src_type.is_int or src_type.is_enum or src_type is error_type
 904
 905
 906 class CAnonEnumType(CIntType):
 907
 908     is_enum = 1
 909
 910     def sign_and_name(self):
 911         return 'int'
 912
 913
 914 class CReturnCodeType(CIntType):
 915
 916     to_py_function = "__Pyx_Owned_Py_None"
 917
 918     is_returncode = 1
 919
 920
 921 class CBIntType(CIntType):
 922
 923     to_py_function = "__Pyx_PyBool_FromLong"
 924     from_py_function = "__Pyx_PyObject_IsTrue"
 925     exception_check = 1 # for C++ bool
 926
 927     def __repr__(self):
 928         return "<CNumericType bint>"
 929
 930     def __str__(self):
 931         return 'bint'
 932
 933
 934 class CPyUCS4IntType(CIntType):
 935     # Py_UCS4
 936
 937     is_unicode_char = True
 938
 939     # Py_UCS4 coerces from and to single character unicode strings (or
 940     # at most two characters on 16bit Unicode builds), but we also
 941     # allow Python integers as input.  The value range for Py_UCS4
 942     # is 0..1114111, which is checked when converting from an integer
 943     # value.
 944
 945     to_py_function = "PyUnicode_FromOrdinal"
 946     from_py_function = "__Pyx_PyObject_AsPy_UCS4"
 947
 948     def create_from_py_utility_code(self, env):
 949         env.use_utility_code(pyobject_as_py_ucs4_utility_code)
 950         return True
 951
 952     def sign_and_name(self):
 953         return "Py_UCS4"
 954
 955
 956 pyobject_as_py_ucs4_utility_code = UtilityCode(
 957 proto='''
 958 static CYTHON_INLINE Py_UCS4 __Pyx_PyObject_AsPy_UCS4(PyObject*);
 959 ''',
 960 impl='''
 961 static CYTHON_INLINE Py_UCS4 __Pyx_PyObject_AsPy_UCS4(PyObject* x) {
 962    long ival;
 963    if (PyUnicode_Check(x)) {
 964        if (likely(PyUnicode_GET_SIZE(x) == 1)) {
 965            return PyUnicode_AS_UNICODE(x)[0];
 966        }
 967        #if Py_UNICODE_SIZE == 2
 968        else if (PyUnicode_GET_SIZE(x) == 2) {
 969            Py_UCS4 high_val = PyUnicode_AS_UNICODE(x)[0];
 970            if (high_val >= 0xD800 && high_val <= 0xDBFF) {
 971                Py_UCS4 low_val = PyUnicode_AS_UNICODE(x)[1];
 972                if (low_val >= 0xDC00 && low_val <= 0xDFFF) {
 973                    return 0x10000 + (((high_val & ((1<<10)-1)) << 10) | (low_val & ((1<<10)-1)));
 974                }
 975            }
 976        }
 977        #endif
 978        PyErr_Format(PyExc_ValueError,
 979            "only single character unicode strings can be converted to Py_UCS4, got length "
 980            #if PY_VERSION_HEX < 0x02050000
 981            "%d",
 982            #else
 983            "%zd",
 984            #endif
 985            PyUnicode_GET_SIZE(x));
 986        return (Py_UCS4)-1;
 987    }
 988    ival = __Pyx_PyInt_AsLong(x);
 989    if (unlikely(ival < 0)) {
 990        if (!PyErr_Occurred())
 991            PyErr_SetString(PyExc_OverflowError,
 992                            "cannot convert negative value to Py_UCS4");
 993        return (Py_UCS4)-1;
 994    } else if (unlikely(ival > 1114111)) {
 995        PyErr_SetString(PyExc_OverflowError,
 996                        "value too large to convert to Py_UCS4");
 997        return (Py_UCS4)-1;
 998    }
 999    return (Py_UCS4)ival;
1000 }
1001 ''')
1002
1003
1004 class CPyUnicodeIntType(CIntType):
1005     # Py_UNICODE
1006
1007     is_unicode_char = True
1008
1009     # Py_UNICODE coerces from and to single character unicode strings,
1010     # but we also allow Python integers as input.  The value range for
1011     # Py_UNICODE is 0..1114111, which is checked when converting from
1012     # an integer value.
1013
1014     to_py_function = "PyUnicode_FromOrdinal"
1015     from_py_function = "__Pyx_PyObject_AsPy_UNICODE"
1016
1017     def create_from_py_utility_code(self, env):
1018         env.use_utility_code(pyobject_as_py_unicode_utility_code)
1019         return True
1020
1021     def sign_and_name(self):
1022         return "Py_UNICODE"
1023
1024 pyobject_as_py_unicode_utility_code = UtilityCode(
1025 proto='''
1026 static CYTHON_INLINE Py_UNICODE __Pyx_PyObject_AsPy_UNICODE(PyObject*);
1027 ''',
1028 impl='''
1029 static CYTHON_INLINE Py_UNICODE __Pyx_PyObject_AsPy_UNICODE(PyObject* x) {
1030    static long maxval = 0;
1031    long ival;
1032    if (PyUnicode_Check(x)) {
1033        if (unlikely(PyUnicode_GET_SIZE(x) != 1)) {
1034            PyErr_Format(PyExc_ValueError,
1035                "only single character unicode strings can be converted to Py_UNICODE, got length "
1036                #if PY_VERSION_HEX < 0x02050000
1037                "%d",
1038                #else
1039                "%zd",
1040                #endif
1041                PyUnicode_GET_SIZE(x));
1042            return (Py_UNICODE)-1;
1043        }
1044        return PyUnicode_AS_UNICODE(x)[0];
1045    }
1046    if (unlikely(!maxval))
1047        maxval = (long)PyUnicode_GetMax();
1048    ival = __Pyx_PyInt_AsLong(x);
1049    if (unlikely(ival < 0)) {
1050        if (!PyErr_Occurred())
1051            PyErr_SetString(PyExc_OverflowError,
1052                            "cannot convert negative value to Py_UNICODE");
1053        return (Py_UNICODE)-1;
1054    } else if (unlikely(ival > maxval)) {
1055        PyErr_SetString(PyExc_OverflowError,
1056                        "value too large to convert to Py_UNICODE");
1057        return (Py_UNICODE)-1;
1058    }
1059    return (Py_UNICODE)ival;
1060 }
1061 ''')
1062
1063
1064 class CPyHashTType(CIntType):
1065
1066     to_py_function = "__Pyx_PyInt_FromHash_t"
1067     from_py_function = "__Pyx_PyInt_AsHash_t"
1068
1069     def sign_and_name(self):
1070         return "Py_hash_t"
1071
1072 class CPySSizeTType(CIntType):
1073
1074     to_py_function = "PyInt_FromSsize_t"
1075     from_py_function = "__Pyx_PyIndex_AsSsize_t"
1076
1077     def sign_and_name(self):
1078         return "Py_ssize_t"
1079
1080 class CSSizeTType(CIntType):
1081
1082     to_py_function = "PyInt_FromSsize_t"
1083     from_py_function = "PyInt_AsSsize_t"
1084
1085     def sign_and_name(self):
1086         return "Py_ssize_t"
1087
1088 class CSizeTType(CIntType):
1089
1090     to_py_function = "__Pyx_PyInt_FromSize_t"
1091     from_py_function = "__Pyx_PyInt_AsSize_t"
1092
1093     def sign_and_name(self):
1094         return "size_t"
1095
1096
1097 class CFloatType(CNumericType):
1098
1099     is_float = 1
1100     to_py_function = "PyFloat_FromDouble"
1101     from_py_function = "__pyx_PyFloat_AsDouble"
1102
1103     exception_value = -1
1104
1105     def __init__(self, rank, math_h_modifier = ''):
1106         CNumericType.__init__(self, rank, 1)
1107         self.math_h_modifier = math_h_modifier
1108
1109     def assignable_from_resolved_type(self, src_type):
1110         return (src_type.is_numeric and not src_type.is_complex) or src_type is error_type
1111
1112
1113 class CComplexType(CNumericType):
1114
1115     is_complex = 1
1116     to_py_function = "__pyx_PyComplex_FromComplex"
1117     has_attributes = 1
1118     scope = None
1119
1120     def __init__(self, real_type):
1121         while real_type.is_typedef and not real_type.typedef_is_external:
1122             real_type = real_type.typedef_base_type
1123         if real_type.is_typedef and real_type.typedef_is_external:
1124             # The below is not actually used: Coercions are currently disabled
1125             # so that complex types of external types can not be created
1126             self.funcsuffix = "_%s" % real_type.specialization_name()
1127         elif hasattr(real_type, 'math_h_modifier'):
1128             self.funcsuffix = real_type.math_h_modifier
1129         else:
1130             self.funcsuffix = "_%s" % real_type.specialization_name()
1131
1132         self.real_type = real_type
1133         CNumericType.__init__(self, real_type.rank + 0.5, real_type.signed)
1134         self.binops = {}
1135         self.from_parts = "%s_from_parts" % self.specialization_name()
1136         self.default_value = "%s(0, 0)" % self.from_parts
1137
1138     def __eq__(self, other):
1139         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1140             return self.real_type == other.real_type
1141         else:
1142             return False
1143
1144     def __ne__(self, other):
1145         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1146             return self.real_type != other.real_type
1147         else:
1148             return True
1149
1150     def __lt__(self, other):
1151         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1152             return self.real_type < other.real_type
1153         else:
1154             # this is arbitrary, but it makes sure we always have
1155             # *some* kind of order
1156             return False
1157
1158     def __hash__(self):
1159         return ~hash(self.real_type)
1160
1161     def declaration_code(self, entity_code,
1162             for_display = 0, dll_linkage = None, pyrex = 0):
1163         if pyrex or for_display:
1164             real_code = self.real_type.declaration_code("", for_display, dll_linkage, pyrex)
1165             base_code = "%s complex" % real_code
1166         else:
1167             base_code = public_decl(self.sign_and_name(), dll_linkage)
1168         return self.base_declaration_code(base_code, entity_code)
1169
1170     def sign_and_name(self):
1171         real_type_name = self.real_type.specialization_name()
1172         real_type_name = real_type_name.replace('long__double','long_double')
1173         real_type_name = real_type_name.replace('PY_LONG_LONG','long_long')
1174         return Naming.type_prefix + real_type_name + "_complex"
1175
1176     def assignable_from(self, src_type):
1177         # Temporary hack/feature disabling, see #441
1178         if (not src_type.is_complex and src_type.is_numeric and src_type.is_typedef
1179             and src_type.typedef_is_external):
1180              return False
1181         else:
1182             return super(CComplexType, self).assignable_from(src_type)
1183
1184     def assignable_from_resolved_type(self, src_type):
1185         return (src_type.is_complex and self.real_type.assignable_from_resolved_type(src_type.real_type)
1186                     or src_type.is_numeric and self.real_type.assignable_from_resolved_type(src_type)
1187                     or src_type is error_type)
1188
1189     def attributes_known(self):
1190         if self.scope is None:
1191             import Symtab
1192             self.scope = scope = Symtab.CClassScope(
1193                     '',
1194                     None,
1195                     visibility="extern")
1196             scope.parent_type = self
1197             scope.directives = {}
1198             scope.declare_var("real", self.real_type, None, cname="real", is_cdef=True)
1199             scope.declare_var("imag", self.real_type, None, cname="imag", is_cdef=True)
1200             entry = scope.declare_cfunction(
1201                     "conjugate",
1202                     CFuncType(self, [CFuncTypeArg("self", self, None)], nogil=True),
1203                     pos=None,
1204                     defining=1,
1205                     cname="__Pyx_c_conj%s" % self.funcsuffix)
1206
1207         return True
1208
1209     def create_declaration_utility_code(self, env):
1210         # This must always be run, because a single CComplexType instance can be shared
1211         # across multiple compilations (the one created in the module scope)
1212         env.use_utility_code(complex_header_utility_code)
1213         env.use_utility_code(complex_real_imag_utility_code)
1214         for utility_code in (complex_type_utility_code,
1215                              complex_from_parts_utility_code,
1216                              complex_arithmetic_utility_code):
1217             env.use_utility_code(
1218                 utility_code.specialize(
1219                     self,
1220                     real_type = self.real_type.declaration_code(''),
1221                     m = self.funcsuffix,
1222                     is_float = self.real_type.is_float))
1223         return True
1224
1225     def create_to_py_utility_code(self, env):
1226         env.use_utility_code(complex_real_imag_utility_code)
1227         env.use_utility_code(complex_to_py_utility_code)
1228         return True
1229
1230     def create_from_py_utility_code(self, env):
1231         self.real_type.create_from_py_utility_code(env)
1232
1233         for utility_code in (complex_from_parts_utility_code,
1234                              complex_from_py_utility_code):
1235             env.use_utility_code(
1236                 utility_code.specialize(
1237                     self,
1238                     real_type = self.real_type.declaration_code(''),
1239                     m = self.funcsuffix,
1240                     is_float = self.real_type.is_float))
1241         self.from_py_function = "__Pyx_PyComplex_As_" + self.specialization_name()
1242         return True
1243
1244     def lookup_op(self, nargs, op):
1245         try:
1246             return self.binops[nargs, op]
1247         except KeyError:
1248             pass
1249         try:
1250             op_name = complex_ops[nargs, op]
1251             self.binops[nargs, op] = func_name = "__Pyx_c_%s%s" % (op_name, self.funcsuffix)
1252             return func_name
1253         except KeyError:
1254             return None
1255
1256     def unary_op(self, op):
1257         return self.lookup_op(1, op)
1258
1259     def binary_op(self, op):
1260         return self.lookup_op(2, op)
1261
1262 complex_ops = {
1263     (1, '-'): 'neg',
1264     (1, 'zero'): 'is_zero',
1265     (2, '+'): 'sum',
1266     (2, '-'): 'diff',
1267     (2, '*'): 'prod',
1268     (2, '/'): 'quot',
1269     (2, '=='): 'eq',
1270 }
1271
1272 complex_header_utility_code = UtilityCode(
1273 proto_block='h_code',
1274 proto="""
1275 #if !defined(CYTHON_CCOMPLEX)
1276   #if defined(__cplusplus)
1277     #define CYTHON_CCOMPLEX 1
1278   #elif defined(_Complex_I)
1279     #define CYTHON_CCOMPLEX 1
1280   #else
1281     #define CYTHON_CCOMPLEX 0
1282   #endif
1283 #endif
1284
1285 #if CYTHON_CCOMPLEX
1286   #ifdef __cplusplus
1287     #include <complex>
1288   #else
1289     #include <complex.h>
1290   #endif
1291 #endif
1292
1293 #if CYTHON_CCOMPLEX && !defined(__cplusplus) && defined(__sun__) && defined(__GNUC__)
1294   #undef _Complex_I
1295   #define _Complex_I 1.0fj
1296 #endif
1297 """)
1298
1299 complex_real_imag_utility_code = UtilityCode(
1300 proto="""
1301 #if CYTHON_CCOMPLEX
1302   #ifdef __cplusplus
1303     #define __Pyx_CREAL(z) ((z).real())
1304     #define __Pyx_CIMAG(z) ((z).imag())
1305   #else
1306     #define __Pyx_CREAL(z) (__real__(z))
1307     #define __Pyx_CIMAG(z) (__imag__(z))
1308   #endif
1309 #else
1310     #define __Pyx_CREAL(z) ((z).real)
1311     #define __Pyx_CIMAG(z) ((z).imag)
1312 #endif
1313
1314 #if defined(_WIN32) && defined(__cplusplus) && CYTHON_CCOMPLEX
1315     #define __Pyx_SET_CREAL(z,x) ((z).real(x))
1316     #define __Pyx_SET_CIMAG(z,y) ((z).imag(y))
1317 #else
1318     #define __Pyx_SET_CREAL(z,x) __Pyx_CREAL(z) = (x)
1319     #define __Pyx_SET_CIMAG(z,y) __Pyx_CIMAG(z) = (y)
1320 #endif
1321 """)
1322
1323 complex_type_utility_code = UtilityCode(
1324 proto_block='complex_type_declarations',
1325 proto="""
1326 #if CYTHON_CCOMPLEX
1327   #ifdef __cplusplus
1328     typedef ::std::complex< %(real_type)s > %(type_name)s;
1329   #else
1330     typedef %(real_type)s _Complex %(type_name)s;
1331   #endif
1332 #else
1333     typedef struct { %(real_type)s real, imag; } %(type_name)s;
1334 #endif
1335 """)
1336
1337 complex_from_parts_utility_code = UtilityCode(
1338 proto_block='utility_code_proto',
1339 proto="""
1340 static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s, %(real_type)s);
1341 """,
1342 impl="""
1343 #if CYTHON_CCOMPLEX
1344   #ifdef __cplusplus
1345     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1346       return ::std::complex< %(real_type)s >(x, y);
1347     }
1348   #else
1349     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1350       return x + y*(%(type)s)_Complex_I;
1351     }
1352   #endif
1353 #else
1354     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1355       %(type)s z;
1356       z.real = x;
1357       z.imag = y;
1358       return z;
1359     }
1360 #endif
1361 """)
1362
1363 complex_to_py_utility_code = UtilityCode(
1364 proto="""
1365 #define __pyx_PyComplex_FromComplex(z) \\
1366         PyComplex_FromDoubles((double)__Pyx_CREAL(z), \\
1367                               (double)__Pyx_CIMAG(z))
1368 """)
1369
1370 complex_from_py_utility_code = UtilityCode(
1371 proto="""
1372 static %(type)s __Pyx_PyComplex_As_%(type_name)s(PyObject*);
1373 """,
1374 impl="""
1375 static %(type)s __Pyx_PyComplex_As_%(type_name)s(PyObject* o) {
1376     Py_complex cval;
1377     if (PyComplex_CheckExact(o))
1378         cval = ((PyComplexObject *)o)->cval;
1379     else
1380         cval = PyComplex_AsCComplex(o);
1381     return %(type_name)s_from_parts(
1382                (%(real_type)s)cval.real,
1383                (%(real_type)s)cval.imag);
1384 }
1385 """)
1386
1387 complex_arithmetic_utility_code = UtilityCode(
1388 proto="""
1389 #if CYTHON_CCOMPLEX
1390     #define __Pyx_c_eq%(m)s(a, b)   ((a)==(b))
1391     #define __Pyx_c_sum%(m)s(a, b)  ((a)+(b))
1392     #define __Pyx_c_diff%(m)s(a, b) ((a)-(b))
1393     #define __Pyx_c_prod%(m)s(a, b) ((a)*(b))
1394     #define __Pyx_c_quot%(m)s(a, b) ((a)/(b))
1395     #define __Pyx_c_neg%(m)s(a)     (-(a))
1396   #ifdef __cplusplus
1397     #define __Pyx_c_is_zero%(m)s(z) ((z)==(%(real_type)s)0)
1398     #define __Pyx_c_conj%(m)s(z)    (::std::conj(z))
1399     #if %(is_float)s
1400         #define __Pyx_c_abs%(m)s(z)     (::std::abs(z))
1401         #define __Pyx_c_pow%(m)s(a, b)  (::std::pow(a, b))
1402     #endif
1403   #else
1404     #define __Pyx_c_is_zero%(m)s(z) ((z)==0)
1405     #define __Pyx_c_conj%(m)s(z)    (conj%(m)s(z))
1406     #if %(is_float)s
1407         #define __Pyx_c_abs%(m)s(z)     (cabs%(m)s(z))
1408         #define __Pyx_c_pow%(m)s(a, b)  (cpow%(m)s(a, b))
1409     #endif
1410  #endif
1411 #else
1412     static CYTHON_INLINE int __Pyx_c_eq%(m)s(%(type)s, %(type)s);
1413     static CYTHON_INLINE %(type)s __Pyx_c_sum%(m)s(%(type)s, %(type)s);
1414     static CYTHON_INLINE %(type)s __Pyx_c_diff%(m)s(%(type)s, %(type)s);
1415     static CYTHON_INLINE %(type)s __Pyx_c_prod%(m)s(%(type)s, %(type)s);
1416     static CYTHON_INLINE %(type)s __Pyx_c_quot%(m)s(%(type)s, %(type)s);
1417     static CYTHON_INLINE %(type)s __Pyx_c_neg%(m)s(%(type)s);
1418     static CYTHON_INLINE int __Pyx_c_is_zero%(m)s(%(type)s);
1419     static CYTHON_INLINE %(type)s __Pyx_c_conj%(m)s(%(type)s);
1420     #if %(is_float)s
1421         static CYTHON_INLINE %(real_type)s __Pyx_c_abs%(m)s(%(type)s);
1422         static CYTHON_INLINE %(type)s __Pyx_c_pow%(m)s(%(type)s, %(type)s);
1423     #endif
1424 #endif
1425 """,
1426 impl="""
1427 #if CYTHON_CCOMPLEX
1428 #else
1429     static CYTHON_INLINE int __Pyx_c_eq%(m)s(%(type)s a, %(type)s b) {
1430        return (a.real == b.real) && (a.imag == b.imag);
1431     }
1432     static CYTHON_INLINE %(type)s __Pyx_c_sum%(m)s(%(type)s a, %(type)s b) {
1433         %(type)s z;
1434         z.real = a.real + b.real;
1435         z.imag = a.imag + b.imag;
1436         return z;
1437     }
1438     static CYTHON_INLINE %(type)s __Pyx_c_diff%(m)s(%(type)s a, %(type)s b) {
1439         %(type)s z;
1440         z.real = a.real - b.real;
1441         z.imag = a.imag - b.imag;
1442         return z;
1443     }
1444     static CYTHON_INLINE %(type)s __Pyx_c_prod%(m)s(%(type)s a, %(type)s b) {
1445         %(type)s z;
1446         z.real = a.real * b.real - a.imag * b.imag;
1447         z.imag = a.real * b.imag + a.imag * b.real;
1448         return z;
1449     }
1450     static CYTHON_INLINE %(type)s __Pyx_c_quot%(m)s(%(type)s a, %(type)s b) {
1451         %(type)s z;
1452         %(real_type)s denom = b.real * b.real + b.imag * b.imag;
1453         z.real = (a.real * b.real + a.imag * b.imag) / denom;
1454         z.imag = (a.imag * b.real - a.real * b.imag) / denom;
1455         return z;
1456     }
1457     static CYTHON_INLINE %(type)s __Pyx_c_neg%(m)s(%(type)s a) {
1458         %(type)s z;
1459         z.real = -a.real;
1460         z.imag = -a.imag;
1461         return z;
1462     }
1463     static CYTHON_INLINE int __Pyx_c_is_zero%(m)s(%(type)s a) {
1464        return (a.real == 0) && (a.imag == 0);
1465     }
1466     static CYTHON_INLINE %(type)s __Pyx_c_conj%(m)s(%(type)s a) {
1467         %(type)s z;
1468         z.real =  a.real;
1469         z.imag = -a.imag;
1470         return z;
1471     }
1472     #if %(is_float)s
1473         static CYTHON_INLINE %(real_type)s __Pyx_c_abs%(m)s(%(type)s z) {
1474           #if !defined(HAVE_HYPOT) || defined(_MSC_VER)
1475             return sqrt%(m)s(z.real*z.real + z.imag*z.imag);
1476           #else
1477             return hypot%(m)s(z.real, z.imag);
1478           #endif
1479         }
1480         static CYTHON_INLINE %(type)s __Pyx_c_pow%(m)s(%(type)s a, %(type)s b) {
1481             %(type)s z;
1482             %(real_type)s r, lnr, theta, z_r, z_theta;
1483             if (b.imag == 0 && b.real == (int)b.real) {
1484                 if (b.real < 0) {
1485                     %(real_type)s denom = a.real * a.real + a.imag * a.imag;
1486                     a.real = a.real / denom;
1487                     a.imag = -a.imag / denom;
1488                     b.real = -b.real;
1489                 }
1490                 switch ((int)b.real) {
1491                     case 0:
1492                         z.real = 1;
1493                         z.imag = 0;
1494                         return z;
1495                     case 1:
1496                         return a;
1497                     case 2:
1498                         z = __Pyx_c_prod%(m)s(a, a);
1499                         return __Pyx_c_prod%(m)s(a, a);
1500                     case 3:
1501                         z = __Pyx_c_prod%(m)s(a, a);
1502                         return __Pyx_c_prod%(m)s(z, a);
1503                     case 4:
1504                         z = __Pyx_c_prod%(m)s(a, a);
1505                         return __Pyx_c_prod%(m)s(z, z);
1506                 }
1507             }
1508             if (a.imag == 0) {
1509                 if (a.real == 0) {
1510                     return a;
1511                 }
1512                 r = a.real;
1513                 theta = 0;
1514             } else {
1515                 r = __Pyx_c_abs%(m)s(a);
1516                 theta = atan2%(m)s(a.imag, a.real);
1517             }
1518             lnr = log%(m)s(r);
1519             z_r = exp%(m)s(lnr * b.real - theta * b.imag);
1520             z_theta = theta * b.real + lnr * b.imag;
1521             z.real = z_r * cos%(m)s(z_theta);
1522             z.imag = z_r * sin%(m)s(z_theta);
1523             return z;
1524         }
1525     #endif
1526 #endif
1527 """)
1528
1529 class CArrayType(CType):
1530     #  base_type     CType              Element type
1531     #  size          integer or None    Number of elements
1532
1533     is_array = 1
1534
1535     def __init__(self, base_type, size):
1536         self.base_type = base_type
1537         self.size = size
1538         if base_type in (c_char_type, c_uchar_type, c_schar_type):
1539             self.is_string = 1
1540
1541     def __repr__(self):
1542         return "<CArrayType %s %s>" % (self.size, repr(self.base_type))
1543
1544     def same_as_resolved_type(self, other_type):
1545         return ((other_type.is_array and
1546             self.base_type.same_as(other_type.base_type))
1547                 or other_type is error_type)
1548
1549     def assignable_from_resolved_type(self, src_type):
1550         # Can't assign to a variable of an array type
1551         return 0
1552
1553     def element_ptr_type(self):
1554         return c_ptr_type(self.base_type)
1555
1556     def declaration_code(self, entity_code,
1557             for_display = 0, dll_linkage = None, pyrex = 0):
1558         if self.size is not None:
1559             dimension_code = self.size
1560         else:
1561             dimension_code = ""
1562         if entity_code.startswith("*"):
1563             entity_code = "(%s)" % entity_code
1564         return self.base_type.declaration_code(
1565             "%s[%s]" % (entity_code, dimension_code),
1566             for_display, dll_linkage, pyrex)
1567
1568     def as_argument_type(self):
1569         return c_ptr_type(self.base_type)
1570
1571     def is_complete(self):
1572         return self.size is not None
1573
1574
1575 class CPtrType(CType):
1576     #  base_type     CType    Referenced type
1577
1578     is_ptr = 1
1579     default_value = "0"
1580
1581     def __init__(self, base_type):
1582         self.base_type = base_type
1583
1584     def __repr__(self):
1585         return "<CPtrType %s>" % repr(self.base_type)
1586
1587     def same_as_resolved_type(self, other_type):
1588         return ((other_type.is_ptr and
1589             self.base_type.same_as(other_type.base_type))
1590                 or other_type is error_type)
1591
1592     def declaration_code(self, entity_code,
1593             for_display = 0, dll_linkage = None, pyrex = 0):
1594         #print "CPtrType.declaration_code: pointer to", self.base_type ###
1595         return self.base_type.declaration_code(
1596             "*%s" % entity_code,
1597             for_display, dll_linkage, pyrex)
1598
1599     def assignable_from_resolved_type(self, other_type):
1600         if other_type is error_type:
1601             return 1
1602         if other_type.is_null_ptr:
1603             return 1
1604         if self.base_type.is_cfunction:
1605             if other_type.is_ptr:
1606                 other_type = other_type.base_type.resolve()
1607             if other_type.is_cfunction:
1608                 return self.base_type.pointer_assignable_from_resolved_type(other_type)
1609             else:
1610                 return 0
1611         if (self.base_type.is_cpp_class and other_type.is_ptr
1612                 and other_type.base_type.is_cpp_class and other_type.base_type.is_subclass(self.base_type)):
1613             return 1
1614         if other_type.is_array or other_type.is_ptr:
1615             return self.base_type.is_void or self.base_type.same_as(other_type.base_type)
1616         return 0
1617
1618     def specialize(self, values):
1619         base_type = self.base_type.specialize(values)
1620         if base_type == self.base_type:
1621             return self
1622         else:
1623             return CPtrType(base_type)
1624
1625
1626 class CNullPtrType(CPtrType):
1627
1628     is_null_ptr = 1
1629
1630
1631 class CReferenceType(BaseType):
1632
1633     is_reference = 1
1634
1635     def __init__(self, base_type):
1636         self.ref_base_type = base_type
1637
1638     def __repr__(self):
1639         return "<CReferenceType %s>" % repr(self.ref_base_type)
1640
1641     def __str__(self):
1642         return "%s &" % self.ref_base_type
1643
1644     def as_argument_type(self):
1645         return self
1646
1647     def declaration_code(self, entity_code,
1648             for_display = 0, dll_linkage = None, pyrex = 0):
1649         #print "CReferenceType.declaration_code: pointer to", self.base_type ###
1650         return self.ref_base_type.declaration_code(
1651             "&%s" % entity_code,
1652             for_display, dll_linkage, pyrex)
1653
1654     def specialize(self, values):
1655         base_type = self.ref_base_type.specialize(values)
1656         if base_type == self.ref_base_type:
1657             return self
1658         else:
1659             return CReferenceType(base_type)
1660
1661     def __getattr__(self, name):
1662         return getattr(self.ref_base_type, name)
1663
1664
1665 class CFuncType(CType):
1666     #  return_type      CType
1667     #  args             [CFuncTypeArg]
1668     #  has_varargs      boolean
1669     #  exception_value  string
1670     #  exception_check  boolean    True if PyErr_Occurred check needed
1671     #  calling_convention  string  Function calling convention
1672     #  nogil            boolean    Can be called without gil
1673     #  with_gil         boolean    Acquire gil around function body
1674     #  templates        [string] or None
1675
1676     is_cfunction = 1
1677     original_sig = None
1678
1679     def __init__(self, return_type, args, has_varargs = 0,
1680             exception_value = None, exception_check = 0, calling_convention = "",
1681             nogil = 0, with_gil = 0, is_overridable = 0, optional_arg_count = 0,
1682             templates = None):
1683         self.return_type = return_type
1684         self.args = args
1685         self.has_varargs = has_varargs
1686         self.optional_arg_count = optional_arg_count
1687         self.exception_value = exception_value
1688         self.exception_check = exception_check
1689         self.calling_convention = calling_convention
1690         self.nogil = nogil
1691         self.with_gil = with_gil
1692         self.is_overridable = is_overridable
1693         self.templates = templates
1694
1695     def __repr__(self):
1696         arg_reprs = map(repr, self.args)
1697         if self.has_varargs:
1698             arg_reprs.append("...")
1699         if self.exception_value:
1700             except_clause = " %r" % self.exception_value
1701         else:
1702             except_clause = ""
1703         if self.exception_check:
1704             except_clause += "?"
1705         return "<CFuncType %s %s[%s]%s>" % (
1706             repr(self.return_type),
1707             self.calling_convention_prefix(),
1708             ",".join(arg_reprs),
1709             except_clause)
1710
1711     def calling_convention_prefix(self):
1712         cc = self.calling_convention
1713         if cc:
1714             return cc + " "
1715         else:
1716             return ""
1717
1718     def same_c_signature_as(self, other_type, as_cmethod = 0):
1719         return self.same_c_signature_as_resolved_type(
1720             other_type.resolve(), as_cmethod)
1721
1722     def same_c_signature_as_resolved_type(self, other_type, as_cmethod = 0):
1723         #print "CFuncType.same_c_signature_as_resolved_type:", \
1724         #    self, other_type, "as_cmethod =", as_cmethod ###
1725         if other_type is error_type:
1726             return 1
1727         if not other_type.is_cfunction:
1728             return 0
1729         if self.is_overridable != other_type.is_overridable:
1730             return 0
1731         nargs = len(self.args)
1732         if nargs != len(other_type.args):
1733             return 0
1734         # When comparing C method signatures, the first argument
1735         # is exempt from compatibility checking (the proper check
1736         # is performed elsewhere).
1737         for i in range(as_cmethod, nargs):
1738             if not self.args[i].type.same_as(
1739                 other_type.args[i].type):
1740                     return 0
1741         if self.has_varargs != other_type.has_varargs:
1742             return 0
1743         if self.optional_arg_count != other_type.optional_arg_count:
1744             return 0
1745         if not self.return_type.same_as(other_type.return_type):
1746             return 0
1747         if not self.same_calling_convention_as(other_type):
1748             return 0
1749         return 1
1750
1751     def compatible_signature_with(self, other_type, as_cmethod = 0):
1752         return self.compatible_signature_with_resolved_type(other_type.resolve(), as_cmethod)
1753
1754     def compatible_signature_with_resolved_type(self, other_type, as_cmethod):
1755         #print "CFuncType.same_c_signature_as_resolved_type:", \
1756         #    self, other_type, "as_cmethod =", as_cmethod ###
1757         if other_type is error_type:
1758             return 1
1759         if not other_type.is_cfunction:
1760             return 0
1761         if not self.is_overridable and other_type.is_overridable:
1762             return 0
1763         nargs = len(self.args)
1764         if nargs - self.optional_arg_count != len(other_type.args) - other_type.optional_arg_count:
1765             return 0
1766         if self.optional_arg_count < other_type.optional_arg_count:
1767             return 0
1768         # When comparing C method signatures, the first argument
1769         # is exempt from compatibility checking (the proper check
1770         # is performed elsewhere).
1771         for i in range(as_cmethod, len(other_type.args)):
1772             if not self.args[i].type.same_as(
1773                 other_type.args[i].type):
1774                     return 0
1775         if self.has_varargs != other_type.has_varargs:
1776             return 0
1777         if not self.return_type.subtype_of_resolved_type(other_type.return_type):
1778             return 0
1779         if not self.same_calling_convention_as(other_type):
1780             return 0
1781         if self.nogil != other_type.nogil:
1782             return 0
1783         self.original_sig = other_type.original_sig or other_type
1784         if as_cmethod:
1785             self.args[0] = other_type.args[0]
1786         return 1
1787
1788
1789     def narrower_c_signature_than(self, other_type, as_cmethod = 0):
1790         return self.narrower_c_signature_than_resolved_type(other_type.resolve(), as_cmethod)
1791
1792     def narrower_c_signature_than_resolved_type(self, other_type, as_cmethod):
1793         if other_type is error_type:
1794             return 1
1795         if not other_type.is_cfunction:
1796             return 0
1797         nargs = len(self.args)
1798         if nargs != len(other_type.args):
1799             return 0
1800         for i in range(as_cmethod, nargs):
1801             if not self.args[i].type.subtype_of_resolved_type(other_type.args[i].type):
1802                 return 0
1803             else:
1804                 self.args[i].needs_type_test = other_type.args[i].needs_type_test \
1805                         or not self.args[i].type.same_as(other_type.args[i].type)
1806         if self.has_varargs != other_type.has_varargs:
1807             return 0
1808         if self.optional_arg_count != other_type.optional_arg_count:
1809             return 0
1810         if not self.return_type.subtype_of_resolved_type(other_type.return_type):
1811             return 0
1812         return 1
1813
1814     def same_calling_convention_as(self, other):
1815         ## XXX Under discussion ...
1816         ## callspec_words = ("__stdcall", "__cdecl", "__fastcall")
1817         ## cs1 = self.calling_convention
1818         ## cs2 = other.calling_convention
1819         ## if (cs1 in callspec_words or
1820         ##     cs2 in callspec_words):
1821         ##     return cs1 == cs2
1822         ## else:
1823         ##     return True
1824         sc1 = self.calling_convention == '__stdcall'
1825         sc2 = other.calling_convention == '__stdcall'
1826         return sc1 == sc2
1827
1828     def same_exception_signature_as(self, other_type):
1829         return self.same_exception_signature_as_resolved_type(
1830             other_type.resolve())
1831
1832     def same_exception_signature_as_resolved_type(self, other_type):
1833         return self.exception_value == other_type.exception_value \
1834             and self.exception_check == other_type.exception_check
1835
1836     def same_as_resolved_type(self, other_type, as_cmethod = 0):
1837         return self.same_c_signature_as_resolved_type(other_type, as_cmethod) \
1838             and self.same_exception_signature_as_resolved_type(other_type) \
1839             and self.nogil == other_type.nogil
1840
1841     def pointer_assignable_from_resolved_type(self, other_type):
1842         return self.same_c_signature_as_resolved_type(other_type) \
1843             and self.same_exception_signature_as_resolved_type(other_type) \
1844             and not (self.nogil and not other_type.nogil)
1845
1846     def declaration_code(self, entity_code,
1847                          for_display = 0, dll_linkage = None, pyrex = 0,
1848                          with_calling_convention = 1):
1849         arg_decl_list = []
1850         for arg in self.args[:len(self.args)-self.optional_arg_count]:
1851             arg_decl_list.append(
1852                 arg.type.declaration_code("", for_display, pyrex = pyrex))
1853         if self.is_overridable:
1854             arg_decl_list.append("int %s" % Naming.skip_dispatch_cname)
1855         if self.optional_arg_count:
1856             arg_decl_list.append(self.op_arg_struct.declaration_code(Naming.optional_args_cname))
1857         if self.has_varargs:
1858             arg_decl_list.append("...")
1859         arg_decl_code = ", ".join(arg_decl_list)
1860         if not arg_decl_code and not pyrex:
1861             arg_decl_code = "void"
1862         trailer = ""
1863         if (pyrex or for_display) and not self.return_type.is_pyobject:
1864             if self.exception_value and self.exception_check:
1865                 trailer = " except? %s" % self.exception_value
1866             elif self.exception_value:
1867                 trailer = " except %s" % self.exception_value
1868             elif self.exception_check == '+':
1869                 trailer = " except +"
1870             else:
1871                 " except *" # ignored
1872             if self.nogil:
1873                 trailer += " nogil"
1874         if not with_calling_convention:
1875             cc = ''
1876         else:
1877             cc = self.calling_convention_prefix()
1878             if (not entity_code and cc) or entity_code.startswith("*"):
1879                 entity_code = "(%s%s)" % (cc, entity_code)
1880                 cc = ""
1881         return self.return_type.declaration_code(
1882             "%s%s(%s)%s" % (cc, entity_code, arg_decl_code, trailer),
1883             for_display, dll_linkage, pyrex)
1884
1885     def function_header_code(self, func_name, arg_code):
1886         return "%s%s(%s)" % (self.calling_convention_prefix(),
1887             func_name, arg_code)
1888
1889     def signature_string(self):
1890         s = self.declaration_code("")
1891         return s
1892
1893     def signature_cast_string(self):
1894         s = self.declaration_code("(*)", with_calling_convention=False)
1895         return '(%s)' % s
1896
1897     def specialize(self, values):
1898         if self.templates is None:
1899             new_templates = None
1900         else:
1901             new_templates = [v.specialize(values) for v in self.templates]
1902         return CFuncType(self.return_type.specialize(values),
1903                              [arg.specialize(values) for arg in self.args],
1904                              has_varargs = 0,
1905                              exception_value = self.exception_value,
1906                              exception_check = self.exception_check,
1907                              calling_convention = self.calling_convention,
1908                              nogil = self.nogil,
1909                              with_gil = self.with_gil,
1910                              is_overridable = self.is_overridable,
1911                              optional_arg_count = self.optional_arg_count,
1912                              templates = new_templates)
1913
1914     def opt_arg_cname(self, arg_name):
1915         return self.op_arg_struct.base_type.scope.lookup(arg_name).cname
1916
1917
1918 class CFuncTypeArg(object):
1919     #  name       string
1920     #  cname      string
1921     #  type       PyrexType
1922     #  pos        source file position
1923
1924     # FIXME: is this the right setup? should None be allowed here?
1925     not_none = False
1926     or_none = False
1927     accept_none = True
1928
1929     def __init__(self, name, type, pos, cname=None):
1930         self.name = name
1931         if cname is not None:
1932             self.cname = cname
1933         else:
1934             self.cname = Naming.var_prefix + name
1935         self.type = type
1936         self.pos = pos
1937         self.needs_type_test = False # TODO: should these defaults be set in analyse_types()?
1938
1939     def __repr__(self):
1940         return "%s:%s" % (self.name, repr(self.type))
1941
1942     def declaration_code(self, for_display = 0):
1943         return self.type.declaration_code(self.cname, for_display)
1944
1945     def specialize(self, values):
1946         return CFuncTypeArg(self.name, self.type.specialize(values), self.pos, self.cname)
1947
1948 class StructUtilityCode(object):
1949     def __init__(self, type, forward_decl):
1950         self.type = type
1951         self.header = "static PyObject* %s(%s)" % (type.to_py_function, type.declaration_code('s'))
1952         self.forward_decl = forward_decl
1953
1954     def __eq__(self, other):
1955         return isinstance(other, StructUtilityCode) and self.header == other.header
1956     def __hash__(self):
1957         return hash(self.header)
1958
1959     def put_code(self, output):
1960         code = output['utility_code_def']
1961         proto = output['utility_code_proto']
1962
1963         code.putln("%s {" % self.header)
1964         code.putln("PyObject* res;")
1965         code.putln("PyObject* member;")
1966         code.putln("res = PyDict_New(); if (res == NULL) return NULL;")
1967         for member in self.type.scope.var_entries:
1968             nameconst_cname = code.get_py_string_const(member.name, identifier=True)
1969             code.putln("member = %s(s.%s); if (member == NULL) goto bad;" % (
1970                 member.type.to_py_function, member.cname))
1971             code.putln("if (PyDict_SetItem(res, %s, member) < 0) goto bad;" % nameconst_cname)
1972             code.putln("Py_DECREF(member);")
1973         code.putln("return res;")
1974         code.putln("bad:")
1975         code.putln("Py_XDECREF(member);")
1976         code.putln("Py_DECREF(res);")
1977         code.putln("return NULL;")
1978         code.putln("}")
1979
1980         # This is a bit of a hack, we need a forward declaration
1981         # due to the way things are ordered in the module...
1982         if self.forward_decl:
1983             proto.putln(self.type.declaration_code('') + ';')
1984         proto.putln(self.header + ";")
1985
1986
1987 class CStructOrUnionType(CType):
1988     #  name          string
1989     #  cname         string
1990     #  kind          string              "struct" or "union"
1991     #  scope         StructOrUnionScope, or None if incomplete
1992     #  typedef_flag  boolean
1993     #  packed        boolean
1994
1995     # entry          Entry
1996
1997     is_struct_or_union = 1
1998     has_attributes = 1
1999
2000     def __init__(self, name, kind, scope, typedef_flag, cname, packed=False):
2001         self.name = name
2002         self.cname = cname
2003         self.kind = kind
2004         self.scope = scope
2005         self.typedef_flag = typedef_flag
2006         self.is_struct = kind == 'struct'
2007         if self.is_struct:
2008             self.to_py_function = "%s_to_py_%s" % (Naming.convert_func_prefix, self.cname)
2009         self.exception_check = True
2010         self._convert_code = None
2011         self.packed = packed
2012
2013     def create_to_py_utility_code(self, env):
2014         if env.outer_scope is None:
2015             return False
2016
2017         if self._convert_code is False: return # tri-state-ish
2018
2019         if self._convert_code is None:
2020             for member in self.scope.var_entries:
2021                 if not member.type.to_py_function or not member.type.create_to_py_utility_code(env):
2022                     self.to_py_function = None
2023                     self._convert_code = False
2024                     return False
2025             forward_decl = (self.entry.visibility != 'extern')
2026             self._convert_code = StructUtilityCode(self, forward_decl)
2027
2028         env.use_utility_code(self._convert_code)
2029         return True
2030
2031     def __repr__(self):
2032         return "<CStructOrUnionType %s %s%s>" % (self.name, self.cname,
2033             ("", " typedef")[self.typedef_flag])
2034
2035     def declaration_code(self, entity_code,
2036             for_display = 0, dll_linkage = None, pyrex = 0):
2037         if pyrex or for_display:
2038             base_code = self.name
2039         else:
2040             if self.typedef_flag:
2041                 base_code = self.cname
2042             else:
2043                 base_code = "%s %s" % (self.kind, self.cname)
2044             base_code = public_decl(base_code, dll_linkage)
2045         return self.base_declaration_code(base_code, entity_code)
2046
2047     def __eq__(self, other):
2048         try:
2049             return (isinstance(other, CStructOrUnionType) and
2050                     self.name == other.name)
2051         except AttributeError:
2052             return False
2053
2054     def __lt__(self, other):
2055         try:
2056             return self.name < other.name
2057         except AttributeError:
2058             # this is arbitrary, but it makes sure we always have
2059             # *some* kind of order
2060             return False
2061
2062     def __hash__(self):
2063         return hash(self.cname) ^ hash(self.kind)
2064
2065     def is_complete(self):
2066         return self.scope is not None
2067
2068     def attributes_known(self):
2069         return self.is_complete()
2070
2071     def can_be_complex(self):
2072         # Does the struct consist of exactly two identical floats?
2073         fields = self.scope.var_entries
2074         if len(fields) != 2: return False
2075         a, b = fields
2076         return (a.type.is_float and b.type.is_float and
2077                 a.type.declaration_code("") ==
2078                 b.type.declaration_code(""))
2079
2080     def struct_nesting_depth(self):
2081         child_depths = [x.type.struct_nesting_depth()
2082                         for x in self.scope.var_entries]
2083         return max(child_depths) + 1
2084
2085 class CppClassType(CType):
2086     #  name          string
2087     #  cname         string
2088     #  scope         CppClassScope
2089     #  templates     [string] or None
2090
2091     is_cpp_class = 1
2092     has_attributes = 1
2093     exception_check = True
2094     namespace = None
2095
2096     def __init__(self, name, scope, cname, base_classes, templates = None, template_type = None):
2097         self.name = name
2098         self.cname = cname
2099         self.scope = scope
2100         self.base_classes = base_classes
2101         self.operators = []
2102         self.templates = templates
2103         self.template_type = template_type
2104         self.specializations = {}
2105
2106     def specialize_here(self, pos, template_values = None):
2107         if self.templates is None:
2108             error(pos, "'%s' type is not a template" % self);
2109             return PyrexTypes.error_type
2110         if len(self.templates) != len(template_values):
2111             error(pos, "%s templated type receives %d arguments, got %d" %
2112                   (self.name, len(self.templates), len(template_values)))
2113             return error_type
2114         return self.specialize(dict(zip(self.templates, template_values)))
2115
2116     def specialize(self, values):
2117         if not self.templates and not self.namespace:
2118             return self
2119         if self.templates is None:
2120             self.templates = []
2121         key = tuple(values.items())
2122         if key in self.specializations:
2123             return self.specializations[key]
2124         template_values = [t.specialize(values) for t in self.templates]
2125         specialized = self.specializations[key] = \
2126             CppClassType(self.name, None, self.cname, [], template_values, template_type=self)
2127         # Need to do these *after* self.specializations[key] is set
2128         # to avoid infinite recursion on circular references.
2129         specialized.base_classes = [b.specialize(values) for b in self.base_classes]
2130         specialized.scope = self.scope.specialize(values)
2131         if self.namespace is not None:
2132             specialized.namespace = self.namespace.specialize(values)
2133         return specialized
2134
2135     def declaration_code(self, entity_code,
2136             for_display = 0, dll_linkage = None, pyrex = 0):
2137         if self.templates:
2138             template_strings = [param.declaration_code('', for_display, None, pyrex)
2139                                 for param in self.templates]
2140             templates = "<%s>" % ",".join(template_strings)
2141             if templates[-2:] == ">>":
2142                 templates = templates[:-2] + "> >"
2143         else:
2144             templates = ""
2145         if pyrex or for_display:
2146             base_code = "%s%s" % (self.name, templates)
2147         else:
2148             base_code = "%s%s" % (self.cname, templates)
2149             if self.namespace is not None:
2150                 base_code = "%s::%s" % (self.namespace.declaration_code(''), base_code)
2151             base_code = public_decl(base_code, dll_linkage)
2152         return self.base_declaration_code(base_code, entity_code)
2153
2154     def is_subclass(self, other_type):
2155         # TODO(danilo): Handle templates.
2156         if self.same_as_resolved_type(other_type):
2157             return 1
2158         for base_class in self.base_classes:
2159             if base_class.is_subclass(other_type):
2160                 return 1
2161         return 0
2162
2163     def same_as_resolved_type(self, other_type):
2164         if other_type.is_cpp_class:
2165             if self == other_type:
2166                 return 1
2167             elif self.template_type and self.template_type == other_type.template_type:
2168                 if self.templates == other_type.templates:
2169                     return 1
2170                 for t1, t2 in zip(self.templates, other_type.templates):
2171                     if not t1.same_as_resolved_type(t2):
2172                         return 0
2173                 return 1
2174         return 0
2175
2176     def assignable_from_resolved_type(self, other_type):
2177         # TODO: handle operator=(...) here?
2178         if other_type is error_type:
2179             return True
2180         return other_type.is_cpp_class and other_type.is_subclass(self)
2181
2182     def attributes_known(self):
2183         return self.scope is not None
2184
2185
2186 class TemplatePlaceholderType(CType):
2187
2188     def __init__(self, name):
2189         self.name = name
2190
2191     def declaration_code(self, entity_code,
2192             for_display = 0, dll_linkage = None, pyrex = 0):
2193         if entity_code:
2194             return self.name + " " + entity_code
2195         else:
2196             return self.name
2197
2198     def specialize(self, values):
2199         if self in values:
2200             return values[self]
2201         else:
2202             return self
2203
2204     def same_as_resolved_type(self, other_type):
2205         if isinstance(other_type, TemplatePlaceholderType):
2206             return self.name == other_type.name
2207         else:
2208             return 0
2209
2210     def __hash__(self):
2211         return hash(self.name)
2212
2213     def __cmp__(self, other):
2214         if isinstance(other, TemplatePlaceholderType):
2215             return cmp(self.name, other.name)
2216         else:
2217             return cmp(type(self), type(other))
2218
2219 class CEnumType(CType):
2220     #  name           string
2221     #  cname          string or None
2222     #  typedef_flag   boolean
2223
2224     is_enum = 1
2225     signed = 1
2226     rank = -1 # Ranks below any integer type
2227     to_py_function = "PyInt_FromLong"
2228     from_py_function = "PyInt_AsLong"
2229
2230     def __init__(self, name, cname, typedef_flag):
2231         self.name = name
2232         self.cname = cname
2233         self.values = []
2234         self.typedef_flag = typedef_flag
2235
2236     def __str__(self):
2237         return self.name
2238
2239     def __repr__(self):
2240         return "<CEnumType %s %s%s>" % (self.name, self.cname,
2241             ("", " typedef")[self.typedef_flag])
2242
2243     def declaration_code(self, entity_code,
2244             for_display = 0, dll_linkage = None, pyrex = 0):
2245         if pyrex or for_display:
2246             base_code = self.name
2247         else:
2248             if self.typedef_flag:
2249                 base_code = self.cname
2250             else:
2251                 base_code = "enum %s" % self.cname
2252             base_code = public_decl(base_code, dll_linkage)
2253         return self.base_declaration_code(base_code, entity_code)
2254
2255
2256 class CStringType(object):
2257     #  Mixin class for C string types.
2258
2259     is_string = 1
2260     is_unicode = 0
2261
2262     to_py_function = "PyBytes_FromString"
2263     from_py_function = "PyBytes_AsString"
2264     exception_value = "NULL"
2265
2266     def literal_code(self, value):
2267         assert isinstance(value, str)
2268         return '"%s"' % StringEncoding.escape_byte_string(value)
2269
2270
2271 class CUTF8CharArrayType(CStringType, CArrayType):
2272     #  C 'char []' type.
2273
2274     is_unicode = 1
2275
2276     to_py_function = "PyUnicode_DecodeUTF8"
2277     exception_value = "NULL"
2278
2279     def __init__(self, size):
2280         CArrayType.__init__(self, c_char_type, size)
2281
2282 class CCharArrayType(CStringType, CArrayType):
2283     #  C 'char []' type.
2284
2285     def __init__(self, size):
2286         CArrayType.__init__(self, c_char_type, size)
2287
2288
2289 class CCharPtrType(CStringType, CPtrType):
2290     # C 'char *' type.
2291
2292     def __init__(self):
2293         CPtrType.__init__(self, c_char_type)
2294
2295
2296 class CUCharPtrType(CStringType, CPtrType):
2297     # C 'unsigned char *' type.
2298
2299     to_py_function = "__Pyx_PyBytes_FromUString"
2300     from_py_function = "__Pyx_PyBytes_AsUString"
2301
2302     def __init__(self):
2303         CPtrType.__init__(self, c_uchar_type)
2304
2305
2306 class UnspecifiedType(PyrexType):
2307     # Used as a placeholder until the type can be determined.
2308
2309     is_unspecified = 1
2310
2311     def declaration_code(self, entity_code,
2312             for_display = 0, dll_linkage = None, pyrex = 0):
2313         return "<unspecified>"
2314
2315     def same_as_resolved_type(self, other_type):
2316         return False
2317
2318
2319 class ErrorType(PyrexType):
2320     # Used to prevent propagation of error messages.
2321
2322     is_error = 1
2323     exception_value = "0"
2324     exception_check    = 0
2325     to_py_function = "dummy"
2326     from_py_function = "dummy"
2327
2328     def create_to_py_utility_code(self, env):
2329         return True
2330
2331     def create_from_py_utility_code(self, env):
2332         return True
2333
2334     def declaration_code(self, entity_code,
2335             for_display = 0, dll_linkage = None, pyrex = 0):
2336         return "<error>"
2337
2338     def same_as_resolved_type(self, other_type):
2339         return 1
2340
2341     def error_condition(self, result_code):
2342         return "dummy"
2343
2344
2345 rank_to_type_name = (
2346     "char",         # 0
2347     "short",        # 1
2348     "int",          # 2
2349     "long",         # 3
2350     "PY_LONG_LONG", # 4
2351     "float",        # 5
2352     "double",       # 6
2353     "long double",  # 7
2354 )
2355
2356 RANK_INT  = list(rank_to_type_name).index('int')
2357 RANK_LONG = list(rank_to_type_name).index('long')
2358 UNSIGNED = 0
2359 SIGNED = 2
2360
2361
2362 py_object_type = PyObjectType()
2363
2364 c_void_type =        CVoidType()
2365
2366 c_uchar_type =       CIntType(0, UNSIGNED)
2367 c_ushort_type =      CIntType(1, UNSIGNED)
2368 c_uint_type =        CIntType(2, UNSIGNED)
2369 c_ulong_type =       CIntType(3, UNSIGNED)
2370 c_ulonglong_type =   CIntType(4, UNSIGNED)
2371
2372 c_char_type =        CIntType(0)
2373 c_short_type =       CIntType(1)
2374 c_int_type =         CIntType(2)
2375 c_long_type =        CIntType(3)
2376 c_longlong_type =    CIntType(4)
2377
2378 c_schar_type =       CIntType(0, SIGNED)
2379 c_sshort_type =      CIntType(1, SIGNED)
2380 c_sint_type =        CIntType(2, SIGNED)
2381 c_slong_type =       CIntType(3, SIGNED)
2382 c_slonglong_type =   CIntType(4, SIGNED)
2383
2384 c_float_type =       CFloatType(5, math_h_modifier='f')
2385 c_double_type =      CFloatType(6)
2386 c_longdouble_type =  CFloatType(7, math_h_modifier='l')
2387
2388 c_float_complex_type =      CComplexType(c_float_type)
2389 c_double_complex_type =     CComplexType(c_double_type)
2390 c_longdouble_complex_type = CComplexType(c_longdouble_type)
2391
2392 c_anon_enum_type =   CAnonEnumType(-1)
2393 c_returncode_type =  CReturnCodeType(RANK_INT)
2394 c_bint_type =        CBIntType(RANK_INT)
2395 c_py_unicode_type =  CPyUnicodeIntType(RANK_INT-0.5, UNSIGNED)
2396 c_py_ucs4_type =     CPyUCS4IntType(RANK_LONG-0.5, UNSIGNED)
2397 c_py_hash_t_type =   CPyHashTType(RANK_LONG+0.5, SIGNED)
2398 c_py_ssize_t_type =  CPySSizeTType(RANK_LONG+0.5, SIGNED)
2399 c_ssize_t_type =     CSSizeTType(RANK_LONG+0.5, SIGNED)
2400 c_size_t_type =      CSizeTType(RANK_LONG+0.5, UNSIGNED)
2401
2402 c_null_ptr_type =     CNullPtrType(c_void_type)
2403 c_void_ptr_type =     CPtrType(c_void_type)
2404 c_void_ptr_ptr_type = CPtrType(c_void_ptr_type)
2405 c_char_array_type =   CCharArrayType(None)
2406 c_char_ptr_type =     CCharPtrType()
2407 c_uchar_ptr_type =    CUCharPtrType()
2408 c_utf8_char_array_type = CUTF8CharArrayType(None)
2409 c_char_ptr_ptr_type = CPtrType(c_char_ptr_type)
2410 c_int_ptr_type =      CPtrType(c_int_type)
2411 c_py_unicode_ptr_type = CPtrType(c_py_unicode_type)
2412 c_py_ssize_t_ptr_type =  CPtrType(c_py_ssize_t_type)
2413 c_ssize_t_ptr_type =  CPtrType(c_ssize_t_type)
2414 c_size_t_ptr_type =  CPtrType(c_size_t_type)
2415
2416
2417 # the Py_buffer type is defined in Builtin.py
2418 c_py_buffer_type = CStructOrUnionType("Py_buffer", "struct", None, 1, "Py_buffer")
2419 c_py_buffer_ptr_type = CPtrType(c_py_buffer_type)
2420
2421 error_type =    ErrorType()
2422 unspecified_type = UnspecifiedType()
2423
2424 modifiers_and_name_to_type = {
2425     #(signed, longness, name) : type
2426     (0,  0, "char"): c_uchar_type,
2427     (1,  0, "char"): c_char_type,
2428     (2,  0, "char"): c_schar_type,
2429
2430     (0, -1, "int"): c_ushort_type,
2431     (0,  0, "int"): c_uint_type,
2432     (0,  1, "int"): c_ulong_type,
2433     (0,  2, "int"): c_ulonglong_type,
2434
2435     (1, -1, "int"): c_short_type,
2436     (1,  0, "int"): c_int_type,
2437     (1,  1, "int"): c_long_type,
2438     (1,  2, "int"): c_longlong_type,
2439
2440     (2, -1, "int"): c_sshort_type,
2441     (2,  0, "int"): c_sint_type,
2442     (2,  1, "int"): c_slong_type,
2443     (2,  2, "int"): c_slonglong_type,
2444
2445     (1,  0, "float"):  c_float_type,
2446     (1,  0, "double"): c_double_type,
2447     (1,  1, "double"): c_longdouble_type,
2448
2449     (1,  0, "complex"):  c_double_complex_type,  # C: float, Python: double => Python wins
2450     (1,  0, "floatcomplex"):  c_float_complex_type,
2451     (1,  0, "doublecomplex"): c_double_complex_type,
2452     (1,  1, "doublecomplex"): c_longdouble_complex_type,
2453
2454     #
2455     (1,  0, "void"): c_void_type,
2456
2457     (1,  0, "bint"):       c_bint_type,
2458     (0,  0, "Py_UNICODE"): c_py_unicode_type,
2459     (0,  0, "Py_UCS4"):    c_py_ucs4_type,
2460     (2,  0, "Py_hash_t"):  c_py_hash_t_type,
2461     (2,  0, "Py_ssize_t"): c_py_ssize_t_type,
2462     (2,  0, "ssize_t") :   c_ssize_t_type,
2463     (0,  0, "size_t") :    c_size_t_type,
2464
2465     (1,  0, "object"): py_object_type,
2466 }
2467
2468 def is_promotion(src_type, dst_type):
2469     # It's hard to find a hard definition of promotion, but empirical
2470     # evidence suggests that the below is all that's allowed.
2471     if src_type.is_numeric:
2472         if dst_type.same_as(c_int_type):
2473             unsigned = (not src_type.signed)
2474             return (src_type.is_enum or
2475                     (src_type.is_int and
2476                      unsigned + src_type.rank < dst_type.rank))
2477         elif dst_type.same_as(c_double_type):
2478             return src_type.is_float and src_type.rank <= dst_type.rank
2479     return False
2480
2481 def best_match(args, functions, pos=None):
2482     """
2483     Given a list args of arguments and a list of functions, choose one
2484     to call which seems to be the "best" fit for this list of arguments.
2485     This function is used, e.g., when deciding which overloaded method
2486     to dispatch for C++ classes.
2487
2488     We first eliminate functions based on arity, and if only one
2489     function has the correct arity, we return it. Otherwise, we weight
2490     functions based on how much work must be done to convert the
2491     arguments, with the following priorities:
2492       * identical types or pointers to identical types
2493       * promotions
2494       * non-Python types
2495     That is, we prefer functions where no arguments need converted,
2496     and failing that, functions where only promotions are required, and
2497     so on.
2498
2499     If no function is deemed a good fit, or if two or more functions have
2500     the same weight, we return None (as there is no best match). If pos
2501     is not None, we also generate an error.
2502     """
2503     # TODO: args should be a list of types, not a list of Nodes.
2504     actual_nargs = len(args)
2505
2506     candidates = []
2507     errors = []
2508     for func in functions:
2509         error_mesg = ""
2510         func_type = func.type
2511         if func_type.is_ptr:
2512             func_type = func_type.base_type
2513         # Check function type
2514         if not func_type.is_cfunction:
2515             if not func_type.is_error and pos is not None:
2516                 error_mesg = "Calling non-function type '%s'" % func_type
2517             errors.append((func, error_mesg))
2518             continue
2519         # Check no. of args
2520         max_nargs = len(func_type.args)
2521         min_nargs = max_nargs - func_type.optional_arg_count
2522         if actual_nargs < min_nargs or \
2523             (not func_type.has_varargs and actual_nargs > max_nargs):
2524             if max_nargs == min_nargs and not func_type.has_varargs:
2525                 expectation = max_nargs
2526             elif actual_nargs < min_nargs:
2527                 expectation = "at least %s" % min_nargs
2528             else:
2529                 expectation = "at most %s" % max_nargs
2530             error_mesg = "Call with wrong number of arguments (expected %s, got %s)" \
2531                          % (expectation, actual_nargs)
2532             errors.append((func, error_mesg))
2533             continue
2534         candidates.append((func, func_type))
2535
2536     # Optimize the most common case of no overloading...
2537     if len(candidates) == 1:
2538         return candidates[0][0]
2539     elif len(candidates) == 0:
2540         if pos is not None:
2541             if len(errors) == 1:
2542                 error(pos, errors[0][1])
2543             else:
2544                 error(pos, "no suitable method found")
2545         return None
2546
2547     possibilities = []
2548     bad_types = []
2549     for func, func_type in candidates:
2550         score = [0,0,0]
2551         for i in range(min(len(args), len(func_type.args))):
2552             src_type = args[i].type
2553             dst_type = func_type.args[i].type
2554             if dst_type.assignable_from(src_type):
2555                 if src_type == dst_type or dst_type.same_as(src_type):
2556                     pass # score 0
2557                 elif is_promotion(src_type, dst_type):
2558                     score[2] += 1
2559                 elif not src_type.is_pyobject:
2560                     score[1] += 1
2561                 else:
2562                     score[0] += 1
2563             else:
2564                 error_mesg = "Invalid conversion from '%s' to '%s'"%(src_type,
2565                                                                      dst_type)
2566                 bad_types.append((func, error_mesg))
2567                 break
2568         else:
2569             possibilities.append((score, func)) # so we can sort it
2570     if possibilities:
2571         possibilities.sort()
2572         if len(possibilities) > 1 and possibilities[0][0] == possibilities[1][0]:
2573             if pos is not None:
2574                 error(pos, "ambiguous overloaded method")
2575             return None
2576         return possibilities[0][1]
2577     if pos is not None:
2578         if len(bad_types) == 1:
2579             error(pos, bad_types[0][1])
2580         else:
2581             error(pos, "no suitable method found")
2582     return None
2583
2584 def widest_numeric_type(type1, type2):
2585     # Given two numeric types, return the narrowest type
2586     # encompassing both of them.
2587     if type1 == type2:
2588         widest_type = type1
2589     elif type1.is_complex or type2.is_complex:
2590         def real_type(ntype):
2591             if ntype.is_complex:
2592                 return ntype.real_type
2593             return ntype
2594         widest_type = CComplexType(
2595             widest_numeric_type(
2596                 real_type(type1),
2597                 real_type(type2)))
2598     elif type1.is_enum and type2.is_enum:
2599         widest_type = c_int_type
2600     elif type1.rank < type2.rank:
2601         widest_type = type2
2602     elif type1.rank > type2.rank:
2603         widest_type = type1
2604     elif type1.signed < type2.signed:
2605         widest_type = type1
2606     else:
2607         widest_type = type2
2608     return widest_type
2609
2610 def independent_spanning_type(type1, type2):
2611     # Return a type assignable independently from both type1 and
2612     # type2, but do not require any interoperability between the two.
2613     # For example, in "True * 2", it is safe to assume an integer
2614     # result type (so spanning_type() will do the right thing),
2615     # whereas "x = True or 2" must evaluate to a type that can hold
2616     # both a boolean value and an integer, so this function works
2617     # better.
2618     if type1 == type2:
2619         return type1
2620     elif (type1 is c_bint_type or type2 is c_bint_type) and (type1.is_numeric and type2.is_numeric):
2621         # special case: if one of the results is a bint and the other
2622         # is another C integer, we must prevent returning a numeric
2623         # type so that we do not lose the ability to coerce to a
2624         # Python bool if we have to.
2625         return py_object_type
2626     span_type = _spanning_type(type1, type2)
2627     if span_type is None:
2628         return error_type
2629     return span_type
2630
2631 def spanning_type(type1, type2):
2632     # Return a type assignable from both type1 and type2, or
2633     # py_object_type if no better type is found.  Assumes that the
2634     # code that calls this will try a coercion afterwards, which will
2635     # fail if the types cannot actually coerce to a py_object_type.
2636     if type1 == type2:
2637         return type1
2638     elif type1 is py_object_type or type2 is py_object_type:
2639         return py_object_type
2640     elif type1 is c_py_unicode_type or type2 is c_py_unicode_type:
2641         # Py_UNICODE behaves more like a string than an int
2642         return py_object_type
2643     span_type = _spanning_type(type1, type2)
2644     if span_type is None:
2645         return py_object_type
2646     return span_type
2647
2648 def _spanning_type(type1, type2):
2649     if type1.is_numeric and type2.is_numeric:
2650         return widest_numeric_type(type1, type2)
2651     elif type1.is_builtin_type and type1.name == 'float' and type2.is_numeric:
2652         return widest_numeric_type(c_double_type, type2)
2653     elif type2.is_builtin_type and type2.name == 'float' and type1.is_numeric:
2654         return widest_numeric_type(type1, c_double_type)
2655     elif type1.is_extension_type and type2.is_extension_type:
2656         return widest_extension_type(type1, type2)
2657     elif type1.is_pyobject or type2.is_pyobject:
2658         return py_object_type
2659     elif type1.assignable_from(type2):
2660         if type1.is_extension_type and type1.typeobj_is_imported():
2661             # external types are unsafe, so we use PyObject instead
2662             return py_object_type
2663         return type1
2664     elif type2.assignable_from(type1):
2665         if type2.is_extension_type and type2.typeobj_is_imported():
2666             # external types are unsafe, so we use PyObject instead
2667             return py_object_type
2668         return type2
2669     else:
2670         return None
2671
2672 def widest_extension_type(type1, type2):
2673     if type1.typeobj_is_imported() or type2.typeobj_is_imported():
2674         return py_object_type
2675     while True:
2676         if type1.subtype_of(type2):
2677             return type2
2678         elif type2.subtype_of(type1):
2679             return type1
2680         type1, type2 = type1.base_type, type2.base_type
2681         if type1 is None or type2 is None:
2682             return py_object_type
2683
2684 def simple_c_type(signed, longness, name):
2685     # Find type descriptor for simple type given name and modifiers.
2686     # Returns None if arguments don't make sense.
2687     return modifiers_and_name_to_type.get((signed, longness, name))
2688
2689 def parse_basic_type(name):
2690     base = None
2691     if name.startswith('p_'):
2692         base = parse_basic_type(name[2:])
2693     elif name.startswith('p'):
2694         base = parse_basic_type(name[1:])
2695     elif name.endswith('*'):
2696         base = parse_basic_type(name[:-1])
2697     if base:
2698         return CPtrType(base)
2699     #
2700     basic_type = simple_c_type(1, 0, name)
2701     if basic_type:
2702         return basic_type
2703     #
2704     signed = 1
2705     longness = 0
2706     if name == 'Py_UNICODE':
2707         signed = 0
2708     elif name == 'Py_UCS4':
2709         signed = 0
2710     elif name == 'Py_hash_t':
2711         signed = 2
2712     elif name == 'Py_ssize_t':
2713         signed = 2
2714     elif name == 'ssize_t':
2715         signed = 2
2716     elif name == 'size_t':
2717         signed = 0
2718     else:
2719         if name.startswith('u'):
2720             name = name[1:]
2721             signed = 0
2722         elif (name.startswith('s') and
2723               not name.startswith('short')):
2724             name = name[1:]
2725             signed = 2
2726         longness = 0
2727         while name.startswith('short'):
2728             name = name.replace('short', '', 1).strip()
2729             longness -= 1
2730         while name.startswith('long'):
2731             name = name.replace('long', '', 1).strip()
2732             longness += 1
2733         if longness != 0 and not name:
2734             name = 'int'
2735     return simple_c_type(signed, longness, name)
2736
2737 def c_array_type(base_type, size):
2738     # Construct a C array type.
2739     if base_type is c_char_type:
2740         return CCharArrayType(size)
2741     elif base_type is error_type:
2742         return error_type
2743     else:
2744         return CArrayType(base_type, size)
2745
2746 def c_ptr_type(base_type):
2747     # Construct a C pointer type.
2748     if base_type is c_char_type:
2749         return c_char_ptr_type
2750     elif base_type is c_uchar_type:
2751         return c_uchar_ptr_type
2752     elif base_type is error_type:
2753         return error_type
2754     else:
2755         return CPtrType(base_type)
2756
2757 def c_ref_type(base_type):
2758     # Construct a C reference type
2759     if base_type is error_type:
2760         return error_type
2761     else:
2762         return CReferenceType(base_type)
2763
2764 def same_type(type1, type2):
2765     return type1.same_as(type2)
2766
2767 def assignable_from(type1, type2):
2768     return type1.assignable_from(type2)
2769
2770 def typecast(to_type, from_type, expr_code):
2771     #  Return expr_code cast to a C type which can be
2772     #  assigned to to_type, assuming its existing C type
2773     #  is from_type.
2774     if to_type is from_type or \
2775         (not to_type.is_pyobject and assignable_from(to_type, from_type)):
2776             return expr_code
2777     else:
2778         #print "typecast: to", to_type, "from", from_type ###
2779         return to_type.cast_code(expr_code)
2780
2781
2782 type_conversion_predeclarations = """
2783 /* Type Conversion Predeclarations */
2784
2785 #define __Pyx_PyBytes_FromUString(s) PyBytes_FromString((char*)s)
2786 #define __Pyx_PyBytes_AsUString(s)   ((unsigned char*) PyBytes_AsString(s))
2787
2788 #define __Pyx_Owned_Py_None(b) (Py_INCREF(Py_None), Py_None)
2789 #define __Pyx_PyBool_FromLong(b) ((b) ? (Py_INCREF(Py_True), Py_True) : (Py_INCREF(Py_False), Py_False))
2790 static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject*);
2791 static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x);
2792
2793 static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject*);
2794 static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t);
2795 static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject*);
2796
2797 #define __pyx_PyFloat_AsDouble(x) (PyFloat_CheckExact(x) ? PyFloat_AS_DOUBLE(x) : PyFloat_AsDouble(x))
2798
2799 """ + type_conversion_predeclarations
2800
2801 # Note: __Pyx_PyObject_IsTrue is written to minimize branching.
2802 type_conversion_functions = """
2803 /* Type Conversion Functions */
2804
2805 static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject* x) {
2806    int is_true = x == Py_True;
2807    if (is_true | (x == Py_False) | (x == Py_None)) return is_true;
2808    else return PyObject_IsTrue(x);
2809 }
2810
2811 static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x) {
2812   PyNumberMethods *m;
2813   const char *name = NULL;
2814   PyObject *res = NULL;
2815 #if PY_VERSION_HEX < 0x03000000
2816   if (PyInt_Check(x) || PyLong_Check(x))
2817 #else
2818   if (PyLong_Check(x))
2819 #endif
2820     return Py_INCREF(x), x;
2821   m = Py_TYPE(x)->tp_as_number;
2822 #if PY_VERSION_HEX < 0x03000000
2823   if (m && m->nb_int) {
2824     name = "int";
2825     res = PyNumber_Int(x);
2826   }
2827   else if (m && m->nb_long) {
2828     name = "long";
2829     res = PyNumber_Long(x);
2830   }
2831 #else
2832   if (m && m->nb_int) {
2833     name = "int";
2834     res = PyNumber_Long(x);
2835   }
2836 #endif
2837   if (res) {
2838 #if PY_VERSION_HEX < 0x03000000
2839     if (!PyInt_Check(res) && !PyLong_Check(res)) {
2840 #else
2841     if (!PyLong_Check(res)) {
2842 #endif
2843       PyErr_Format(PyExc_TypeError,
2844                    "__%s__ returned non-%s (type %.200s)",
2845                    name, name, Py_TYPE(res)->tp_name);
2846       Py_DECREF(res);
2847       return NULL;
2848     }
2849   }
2850   else if (!PyErr_Occurred()) {
2851     PyErr_SetString(PyExc_TypeError,
2852                     "an integer is required");
2853   }
2854   return res;
2855 }
2856
2857 static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject* b) {
2858   Py_ssize_t ival;
2859   PyObject* x = PyNumber_Index(b);
2860   if (!x) return -1;
2861   ival = PyInt_AsSsize_t(x);
2862   Py_DECREF(x);
2863   return ival;
2864 }
2865
2866 static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t ival) {
2867 #if PY_VERSION_HEX < 0x02050000
2868    if (ival <= LONG_MAX)
2869        return PyInt_FromLong((long)ival);
2870    else {
2871        unsigned char *bytes = (unsigned char *) &ival;
2872        int one = 1; int little = (int)*(unsigned char*)&one;
2873        return _PyLong_FromByteArray(bytes, sizeof(size_t), little, 0);
2874    }
2875 #else
2876    return PyInt_FromSize_t(ival);
2877 #endif
2878 }
2879
2880 static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject* x) {
2881    unsigned PY_LONG_LONG val = __Pyx_PyInt_AsUnsignedLongLong(x);
2882    if (unlikely(val == (unsigned PY_LONG_LONG)-1 && PyErr_Occurred())) {
2883        return (size_t)-1;
2884    } else if (unlikely(val != (unsigned PY_LONG_LONG)(size_t)val)) {
2885        PyErr_SetString(PyExc_OverflowError,
2886                        "value too large to convert to size_t");
2887        return (size_t)-1;
2888    }
2889    return (size_t)val;
2890 }
2891
2892 """ + type_conversion_functions
2893