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     is_returncode = 1
 917
 918
 919 class CBIntType(CIntType):
 920
 921     to_py_function = "__Pyx_PyBool_FromLong"
 922     from_py_function = "__Pyx_PyObject_IsTrue"
 923     exception_check = 1 # for C++ bool
 924
 925     def __repr__(self):
 926         return "<CNumericType bint>"
 927
 928
 929 class CPyUCS4IntType(CIntType):
 930     # Py_UCS4
 931
 932     is_unicode_char = True
 933
 934     # Py_UCS4 coerces from and to single character unicode strings (or
 935     # at most two characters on 16bit Unicode builds), but we also
 936     # allow Python integers as input.  The value range for Py_UCS4
 937     # is 0..1114111, which is checked when converting from an integer
 938     # value.
 939
 940     to_py_function = "PyUnicode_FromOrdinal"
 941     from_py_function = "__Pyx_PyObject_AsPy_UCS4"
 942
 943     def create_from_py_utility_code(self, env):
 944         env.use_utility_code(pyobject_as_py_ucs4_utility_code)
 945         return True
 946
 947     def sign_and_name(self):
 948         return "Py_UCS4"
 949
 950
 951 pyobject_as_py_ucs4_utility_code = UtilityCode(
 952 proto='''
 953 static CYTHON_INLINE Py_UCS4 __Pyx_PyObject_AsPy_UCS4(PyObject*);
 954 ''',
 955 impl='''
 956 static CYTHON_INLINE Py_UCS4 __Pyx_PyObject_AsPy_UCS4(PyObject* x) {
 957    long ival;
 958    if (PyUnicode_Check(x)) {
 959        if (likely(PyUnicode_GET_SIZE(x) == 1)) {
 960            return PyUnicode_AS_UNICODE(x)[0];
 961        } else if (PyUnicode_GET_SIZE(x) == 2) {
 962            Py_UCS4 high_val = PyUnicode_AS_UNICODE(x)[0];
 963            if (high_val >= 0xD800 && high_val <= 0xDBFF) {
 964                Py_UCS4 low_val = PyUnicode_AS_UNICODE(x)[1];
 965                if (low_val >= 0xDC00 && low_val <= 0xDFFF) {
 966                    return 0x10000 | ((high_val & ((1<<10)-1)) << 10) | (low_val & ((1<<10)-1));
 967                }
 968            }
 969        }
 970        PyErr_Format(PyExc_ValueError,
 971            "only single character unicode strings or surrogate pairs can be converted to Py_UCS4, got length "
 972            #if PY_VERSION_HEX < 0x02050000
 973            "%d",
 974            #else
 975            "%zd",
 976            #endif
 977            PyUnicode_GET_SIZE(x));
 978        return (Py_UCS4)-1;
 979    }
 980    ival = __Pyx_PyInt_AsLong(x);
 981    if (unlikely(ival < 0)) {
 982        if (!PyErr_Occurred())
 983            PyErr_SetString(PyExc_OverflowError,
 984                            "cannot convert negative value to Py_UCS4");
 985        return (Py_UCS4)-1;
 986    } else if (unlikely(ival > 1114111)) {
 987        PyErr_SetString(PyExc_OverflowError,
 988                        "value too large to convert to Py_UCS4");
 989        return (Py_UCS4)-1;
 990    }
 991    return (Py_UCS4)ival;
 992 }
 993 ''')
 994
 995
 996 class CPyUnicodeIntType(CIntType):
 997     # Py_UNICODE
 998
 999     is_unicode_char = True
1000
1001     # Py_UNICODE coerces from and to single character unicode strings,
1002     # but we also allow Python integers as input.  The value range for
1003     # Py_UNICODE is 0..1114111, which is checked when converting from
1004     # an integer value.
1005
1006     to_py_function = "PyUnicode_FromOrdinal"
1007     from_py_function = "__Pyx_PyObject_AsPy_UNICODE"
1008
1009     def create_from_py_utility_code(self, env):
1010         env.use_utility_code(pyobject_as_py_unicode_utility_code)
1011         return True
1012
1013     def sign_and_name(self):
1014         return "Py_UNICODE"
1015
1016 pyobject_as_py_unicode_utility_code = UtilityCode(
1017 proto='''
1018 static CYTHON_INLINE Py_UNICODE __Pyx_PyObject_AsPy_UNICODE(PyObject*);
1019 ''',
1020 impl='''
1021 static CYTHON_INLINE Py_UNICODE __Pyx_PyObject_AsPy_UNICODE(PyObject* x) {
1022    static long maxval = 0;
1023    long ival;
1024    if (PyUnicode_Check(x)) {
1025        if (unlikely(PyUnicode_GET_SIZE(x) != 1)) {
1026            PyErr_Format(PyExc_ValueError,
1027                "only single character unicode strings can be converted to Py_UNICODE, got length "
1028                #if PY_VERSION_HEX < 0x02050000
1029                "%d",
1030                #else
1031                "%zd",
1032                #endif
1033                PyUnicode_GET_SIZE(x));
1034            return (Py_UNICODE)-1;
1035        }
1036        return PyUnicode_AS_UNICODE(x)[0];
1037    }
1038    if (unlikely(!maxval))
1039        maxval = (long)PyUnicode_GetMax();
1040    ival = __Pyx_PyInt_AsLong(x);
1041    if (unlikely(ival < 0)) {
1042        if (!PyErr_Occurred())
1043            PyErr_SetString(PyExc_OverflowError,
1044                            "cannot convert negative value to Py_UNICODE");
1045        return (Py_UNICODE)-1;
1046    } else if (unlikely(ival > maxval)) {
1047        PyErr_SetString(PyExc_OverflowError,
1048                        "value too large to convert to Py_UNICODE");
1049        return (Py_UNICODE)-1;
1050    }
1051    return (Py_UNICODE)ival;
1052 }
1053 ''')
1054
1055
1056 class CPySSizeTType(CIntType):
1057
1058     to_py_function = "PyInt_FromSsize_t"
1059     from_py_function = "__Pyx_PyIndex_AsSsize_t"
1060
1061     def sign_and_name(self):
1062         return "Py_ssize_t"
1063
1064 class CSSizeTType(CIntType):
1065
1066     to_py_function = "PyInt_FromSsize_t"
1067     from_py_function = "PyInt_AsSsize_t"
1068
1069     def sign_and_name(self):
1070         return "Py_ssize_t"
1071
1072 class CSizeTType(CIntType):
1073
1074     to_py_function = "__Pyx_PyInt_FromSize_t"
1075     from_py_function = "__Pyx_PyInt_AsSize_t"
1076
1077     def sign_and_name(self):
1078         return "size_t"
1079
1080
1081 class CFloatType(CNumericType):
1082
1083     is_float = 1
1084     to_py_function = "PyFloat_FromDouble"
1085     from_py_function = "__pyx_PyFloat_AsDouble"
1086
1087     exception_value = -1
1088
1089     def __init__(self, rank, math_h_modifier = ''):
1090         CNumericType.__init__(self, rank, 1)
1091         self.math_h_modifier = math_h_modifier
1092
1093     def assignable_from_resolved_type(self, src_type):
1094         return (src_type.is_numeric and not src_type.is_complex) or src_type is error_type
1095
1096
1097 class CComplexType(CNumericType):
1098
1099     is_complex = 1
1100     to_py_function = "__pyx_PyComplex_FromComplex"
1101     has_attributes = 1
1102     scope = None
1103
1104     def __init__(self, real_type):
1105         while real_type.is_typedef and not real_type.typedef_is_external:
1106             real_type = real_type.typedef_base_type
1107         if real_type.is_typedef and real_type.typedef_is_external:
1108             # The below is not actually used: Coercions are currently disabled
1109             # so that complex types of external types can not be created
1110             self.funcsuffix = "_%s" % real_type.specialization_name()
1111         elif hasattr(real_type, 'math_h_modifier'):
1112             self.funcsuffix = real_type.math_h_modifier
1113         else:
1114             self.funcsuffix = "_%s" % real_type.specialization_name()
1115
1116         self.real_type = real_type
1117         CNumericType.__init__(self, real_type.rank + 0.5, real_type.signed)
1118         self.binops = {}
1119         self.from_parts = "%s_from_parts" % self.specialization_name()
1120         self.default_value = "%s(0, 0)" % self.from_parts
1121
1122     def __eq__(self, other):
1123         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1124             return self.real_type == other.real_type
1125         else:
1126             return False
1127
1128     def __ne__(self, other):
1129         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1130             return self.real_type != other.real_type
1131         else:
1132             return True
1133
1134     def __lt__(self, other):
1135         if isinstance(self, CComplexType) and isinstance(other, CComplexType):
1136             return self.real_type < other.real_type
1137         else:
1138             # this is arbitrary, but it makes sure we always have
1139             # *some* kind of order
1140             return False
1141
1142     def __hash__(self):
1143         return ~hash(self.real_type)
1144
1145     def declaration_code(self, entity_code,
1146             for_display = 0, dll_linkage = None, pyrex = 0):
1147         if pyrex or for_display:
1148             real_code = self.real_type.declaration_code("", for_display, dll_linkage, pyrex)
1149             base_code = "%s complex" % real_code
1150         else:
1151             base_code = public_decl(self.sign_and_name(), dll_linkage)
1152         return self.base_declaration_code(base_code, entity_code)
1153
1154     def sign_and_name(self):
1155         real_type_name = self.real_type.specialization_name()
1156         real_type_name = real_type_name.replace('long__double','long_double')
1157         real_type_name = real_type_name.replace('PY_LONG_LONG','long_long')
1158         return Naming.type_prefix + real_type_name + "_complex"
1159
1160     def assignable_from(self, src_type):
1161         # Temporary hack/feature disabling, see #441
1162         if (not src_type.is_complex and src_type.is_numeric and src_type.is_typedef
1163             and src_type.typedef_is_external):
1164              return False
1165         else:
1166             return super(CComplexType, self).assignable_from(src_type)
1167
1168     def assignable_from_resolved_type(self, src_type):
1169         return (src_type.is_complex and self.real_type.assignable_from_resolved_type(src_type.real_type)
1170                     or src_type.is_numeric and self.real_type.assignable_from_resolved_type(src_type)
1171                     or src_type is error_type)
1172
1173     def attributes_known(self):
1174         if self.scope is None:
1175             import Symtab
1176             self.scope = scope = Symtab.CClassScope(
1177                     '',
1178                     None,
1179                     visibility="extern")
1180             scope.parent_type = self
1181             scope.directives = {}
1182             scope.declare_var("real", self.real_type, None, "real", is_cdef=True)
1183             scope.declare_var("imag", self.real_type, None, "imag", is_cdef=True)
1184             entry = scope.declare_cfunction(
1185                     "conjugate",
1186                     CFuncType(self, [CFuncTypeArg("self", self, None)], nogil=True),
1187                     pos=None,
1188                     defining=1,
1189                     cname="__Pyx_c_conj%s" % self.funcsuffix)
1190
1191         return True
1192
1193     def create_declaration_utility_code(self, env):
1194         # This must always be run, because a single CComplexType instance can be shared
1195         # across multiple compilations (the one created in the module scope)
1196         env.use_utility_code(complex_header_utility_code)
1197         env.use_utility_code(complex_real_imag_utility_code)
1198         for utility_code in (complex_type_utility_code,
1199                              complex_from_parts_utility_code,
1200                              complex_arithmetic_utility_code):
1201             env.use_utility_code(
1202                 utility_code.specialize(
1203                     self,
1204                     real_type = self.real_type.declaration_code(''),
1205                     m = self.funcsuffix,
1206                     is_float = self.real_type.is_float))
1207         return True
1208
1209     def create_to_py_utility_code(self, env):
1210         env.use_utility_code(complex_real_imag_utility_code)
1211         env.use_utility_code(complex_to_py_utility_code)
1212         return True
1213
1214     def create_from_py_utility_code(self, env):
1215         self.real_type.create_from_py_utility_code(env)
1216
1217         for utility_code in (complex_from_parts_utility_code,
1218                              complex_from_py_utility_code):
1219             env.use_utility_code(
1220                 utility_code.specialize(
1221                     self,
1222                     real_type = self.real_type.declaration_code(''),
1223                     m = self.funcsuffix,
1224                     is_float = self.real_type.is_float))
1225         self.from_py_function = "__Pyx_PyComplex_As_" + self.specialization_name()
1226         return True
1227
1228     def lookup_op(self, nargs, op):
1229         try:
1230             return self.binops[nargs, op]
1231         except KeyError:
1232             pass
1233         try:
1234             op_name = complex_ops[nargs, op]
1235             self.binops[nargs, op] = func_name = "__Pyx_c_%s%s" % (op_name, self.funcsuffix)
1236             return func_name
1237         except KeyError:
1238             return None
1239
1240     def unary_op(self, op):
1241         return self.lookup_op(1, op)
1242
1243     def binary_op(self, op):
1244         return self.lookup_op(2, op)
1245
1246 complex_ops = {
1247     (1, '-'): 'neg',
1248     (1, 'zero'): 'is_zero',
1249     (2, '+'): 'sum',
1250     (2, '-'): 'diff',
1251     (2, '*'): 'prod',
1252     (2, '/'): 'quot',
1253     (2, '=='): 'eq',
1254 }
1255
1256 complex_header_utility_code = UtilityCode(
1257 proto_block='h_code',
1258 proto="""
1259 #if !defined(CYTHON_CCOMPLEX)
1260   #if defined(__cplusplus)
1261     #define CYTHON_CCOMPLEX 1
1262   #elif defined(_Complex_I)
1263     #define CYTHON_CCOMPLEX 1
1264   #else
1265     #define CYTHON_CCOMPLEX 0
1266   #endif
1267 #endif
1268
1269 #if CYTHON_CCOMPLEX
1270   #ifdef __cplusplus
1271     #include <complex>
1272   #else
1273     #include <complex.h>
1274   #endif
1275 #endif
1276
1277 #if CYTHON_CCOMPLEX && !defined(__cplusplus) && defined(__sun__) && defined(__GNUC__)
1278   #undef _Complex_I
1279   #define _Complex_I 1.0fj
1280 #endif
1281 """)
1282
1283 complex_real_imag_utility_code = UtilityCode(
1284 proto="""
1285 #if CYTHON_CCOMPLEX
1286   #ifdef __cplusplus
1287     #define __Pyx_CREAL(z) ((z).real())
1288     #define __Pyx_CIMAG(z) ((z).imag())
1289   #else
1290     #define __Pyx_CREAL(z) (__real__(z))
1291     #define __Pyx_CIMAG(z) (__imag__(z))
1292   #endif
1293 #else
1294     #define __Pyx_CREAL(z) ((z).real)
1295     #define __Pyx_CIMAG(z) ((z).imag)
1296 #endif
1297
1298 #if defined(_WIN32) && defined(__cplusplus) && CYTHON_CCOMPLEX
1299     #define __Pyx_SET_CREAL(z,x) ((z).real(x))
1300     #define __Pyx_SET_CIMAG(z,y) ((z).imag(y))
1301 #else
1302     #define __Pyx_SET_CREAL(z,x) __Pyx_CREAL(z) = (x)
1303     #define __Pyx_SET_CIMAG(z,y) __Pyx_CIMAG(z) = (y)
1304 #endif
1305 """)
1306
1307 complex_type_utility_code = UtilityCode(
1308 proto_block='complex_type_declarations',
1309 proto="""
1310 #if CYTHON_CCOMPLEX
1311   #ifdef __cplusplus
1312     typedef ::std::complex< %(real_type)s > %(type_name)s;
1313   #else
1314     typedef %(real_type)s _Complex %(type_name)s;
1315   #endif
1316 #else
1317     typedef struct { %(real_type)s real, imag; } %(type_name)s;
1318 #endif
1319 """)
1320
1321 complex_from_parts_utility_code = UtilityCode(
1322 proto_block='utility_code_proto',
1323 proto="""
1324 static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s, %(real_type)s);
1325 """,
1326 impl="""
1327 #if CYTHON_CCOMPLEX
1328   #ifdef __cplusplus
1329     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1330       return ::std::complex< %(real_type)s >(x, y);
1331     }
1332   #else
1333     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1334       return x + y*(%(type)s)_Complex_I;
1335     }
1336   #endif
1337 #else
1338     static CYTHON_INLINE %(type)s %(type_name)s_from_parts(%(real_type)s x, %(real_type)s y) {
1339       %(type)s z;
1340       z.real = x;
1341       z.imag = y;
1342       return z;
1343     }
1344 #endif
1345 """)
1346
1347 complex_to_py_utility_code = UtilityCode(
1348 proto="""
1349 #define __pyx_PyComplex_FromComplex(z) \\
1350         PyComplex_FromDoubles((double)__Pyx_CREAL(z), \\
1351                               (double)__Pyx_CIMAG(z))
1352 """)
1353
1354 complex_from_py_utility_code = UtilityCode(
1355 proto="""
1356 static %(type)s __Pyx_PyComplex_As_%(type_name)s(PyObject*);
1357 """,
1358 impl="""
1359 static %(type)s __Pyx_PyComplex_As_%(type_name)s(PyObject* o) {
1360     Py_complex cval;
1361     if (PyComplex_CheckExact(o))
1362         cval = ((PyComplexObject *)o)->cval;
1363     else
1364         cval = PyComplex_AsCComplex(o);
1365     return %(type_name)s_from_parts(
1366                (%(real_type)s)cval.real,
1367                (%(real_type)s)cval.imag);
1368 }
1369 """)
1370
1371 complex_arithmetic_utility_code = UtilityCode(
1372 proto="""
1373 #if CYTHON_CCOMPLEX
1374     #define __Pyx_c_eq%(m)s(a, b)   ((a)==(b))
1375     #define __Pyx_c_sum%(m)s(a, b)  ((a)+(b))
1376     #define __Pyx_c_diff%(m)s(a, b) ((a)-(b))
1377     #define __Pyx_c_prod%(m)s(a, b) ((a)*(b))
1378     #define __Pyx_c_quot%(m)s(a, b) ((a)/(b))
1379     #define __Pyx_c_neg%(m)s(a)     (-(a))
1380   #ifdef __cplusplus
1381     #define __Pyx_c_is_zero%(m)s(z) ((z)==(%(real_type)s)0)
1382     #define __Pyx_c_conj%(m)s(z)    (::std::conj(z))
1383     #if %(is_float)s
1384         #define __Pyx_c_abs%(m)s(z)     (::std::abs(z))
1385         #define __Pyx_c_pow%(m)s(a, b)  (::std::pow(a, b))
1386     #endif
1387   #else
1388     #define __Pyx_c_is_zero%(m)s(z) ((z)==0)
1389     #define __Pyx_c_conj%(m)s(z)    (conj%(m)s(z))
1390     #if %(is_float)s
1391         #define __Pyx_c_abs%(m)s(z)     (cabs%(m)s(z))
1392         #define __Pyx_c_pow%(m)s(a, b)  (cpow%(m)s(a, b))
1393     #endif
1394  #endif
1395 #else
1396     static CYTHON_INLINE int __Pyx_c_eq%(m)s(%(type)s, %(type)s);
1397     static CYTHON_INLINE %(type)s __Pyx_c_sum%(m)s(%(type)s, %(type)s);
1398     static CYTHON_INLINE %(type)s __Pyx_c_diff%(m)s(%(type)s, %(type)s);
1399     static CYTHON_INLINE %(type)s __Pyx_c_prod%(m)s(%(type)s, %(type)s);
1400     static CYTHON_INLINE %(type)s __Pyx_c_quot%(m)s(%(type)s, %(type)s);
1401     static CYTHON_INLINE %(type)s __Pyx_c_neg%(m)s(%(type)s);
1402     static CYTHON_INLINE int __Pyx_c_is_zero%(m)s(%(type)s);
1403     static CYTHON_INLINE %(type)s __Pyx_c_conj%(m)s(%(type)s);
1404     #if %(is_float)s
1405         static CYTHON_INLINE %(real_type)s __Pyx_c_abs%(m)s(%(type)s);
1406         static CYTHON_INLINE %(type)s __Pyx_c_pow%(m)s(%(type)s, %(type)s);
1407     #endif
1408 #endif
1409 """,
1410 impl="""
1411 #if CYTHON_CCOMPLEX
1412 #else
1413     static CYTHON_INLINE int __Pyx_c_eq%(m)s(%(type)s a, %(type)s b) {
1414        return (a.real == b.real) && (a.imag == b.imag);
1415     }
1416     static CYTHON_INLINE %(type)s __Pyx_c_sum%(m)s(%(type)s a, %(type)s b) {
1417         %(type)s z;
1418         z.real = a.real + b.real;
1419         z.imag = a.imag + b.imag;
1420         return z;
1421     }
1422     static CYTHON_INLINE %(type)s __Pyx_c_diff%(m)s(%(type)s a, %(type)s b) {
1423         %(type)s z;
1424         z.real = a.real - b.real;
1425         z.imag = a.imag - b.imag;
1426         return z;
1427     }
1428     static CYTHON_INLINE %(type)s __Pyx_c_prod%(m)s(%(type)s a, %(type)s b) {
1429         %(type)s z;
1430         z.real = a.real * b.real - a.imag * b.imag;
1431         z.imag = a.real * b.imag + a.imag * b.real;
1432         return z;
1433     }
1434     static CYTHON_INLINE %(type)s __Pyx_c_quot%(m)s(%(type)s a, %(type)s b) {
1435         %(type)s z;
1436         %(real_type)s denom = b.real * b.real + b.imag * b.imag;
1437         z.real = (a.real * b.real + a.imag * b.imag) / denom;
1438         z.imag = (a.imag * b.real - a.real * b.imag) / denom;
1439         return z;
1440     }
1441     static CYTHON_INLINE %(type)s __Pyx_c_neg%(m)s(%(type)s a) {
1442         %(type)s z;
1443         z.real = -a.real;
1444         z.imag = -a.imag;
1445         return z;
1446     }
1447     static CYTHON_INLINE int __Pyx_c_is_zero%(m)s(%(type)s a) {
1448        return (a.real == 0) && (a.imag == 0);
1449     }
1450     static CYTHON_INLINE %(type)s __Pyx_c_conj%(m)s(%(type)s a) {
1451         %(type)s z;
1452         z.real =  a.real;
1453         z.imag = -a.imag;
1454         return z;
1455     }
1456     #if %(is_float)s
1457         static CYTHON_INLINE %(real_type)s __Pyx_c_abs%(m)s(%(type)s z) {
1458           #if !defined(HAVE_HYPOT) || defined(_MSC_VER)
1459             return sqrt%(m)s(z.real*z.real + z.imag*z.imag);
1460           #else
1461             return hypot%(m)s(z.real, z.imag);
1462           #endif
1463         }
1464         static CYTHON_INLINE %(type)s __Pyx_c_pow%(m)s(%(type)s a, %(type)s b) {
1465             %(type)s z;
1466             %(real_type)s r, lnr, theta, z_r, z_theta;
1467             if (b.imag == 0 && b.real == (int)b.real) {
1468                 if (b.real < 0) {
1469                     %(real_type)s denom = a.real * a.real + a.imag * a.imag;
1470                     a.real = a.real / denom;
1471                     a.imag = -a.imag / denom;
1472                     b.real = -b.real;
1473                 }
1474                 switch ((int)b.real) {
1475                     case 0:
1476                         z.real = 1;
1477                         z.imag = 0;
1478                         return z;
1479                     case 1:
1480                         return a;
1481                     case 2:
1482                         z = __Pyx_c_prod%(m)s(a, a);
1483                         return __Pyx_c_prod%(m)s(a, a);
1484                     case 3:
1485                         z = __Pyx_c_prod%(m)s(a, a);
1486                         return __Pyx_c_prod%(m)s(z, a);
1487                     case 4:
1488                         z = __Pyx_c_prod%(m)s(a, a);
1489                         return __Pyx_c_prod%(m)s(z, z);
1490                 }
1491             }
1492             if (a.imag == 0) {
1493                 if (a.real == 0) {
1494                     return a;
1495                 }
1496                 r = a.real;
1497                 theta = 0;
1498             } else {
1499                 r = __Pyx_c_abs%(m)s(a);
1500                 theta = atan2%(m)s(a.imag, a.real);
1501             }
1502             lnr = log%(m)s(r);
1503             z_r = exp%(m)s(lnr * b.real - theta * b.imag);
1504             z_theta = theta * b.real + lnr * b.imag;
1505             z.real = z_r * cos%(m)s(z_theta);
1506             z.imag = z_r * sin%(m)s(z_theta);
1507             return z;
1508         }
1509     #endif
1510 #endif
1511 """)
1512
1513 class CArrayType(CType):
1514     #  base_type     CType              Element type
1515     #  size          integer or None    Number of elements
1516
1517     is_array = 1
1518
1519     def __init__(self, base_type, size):
1520         self.base_type = base_type
1521         self.size = size
1522         if base_type is c_char_type:
1523             self.is_string = 1
1524
1525     def __repr__(self):
1526         return "<CArrayType %s %s>" % (self.size, repr(self.base_type))
1527
1528     def same_as_resolved_type(self, other_type):
1529         return ((other_type.is_array and
1530             self.base_type.same_as(other_type.base_type))
1531                 or other_type is error_type)
1532
1533     def assignable_from_resolved_type(self, src_type):
1534         # Can't assign to a variable of an array type
1535         return 0
1536
1537     def element_ptr_type(self):
1538         return c_ptr_type(self.base_type)
1539
1540     def declaration_code(self, entity_code,
1541             for_display = 0, dll_linkage = None, pyrex = 0):
1542         if self.size is not None:
1543             dimension_code = self.size
1544         else:
1545             dimension_code = ""
1546         if entity_code.startswith("*"):
1547             entity_code = "(%s)" % entity_code
1548         return self.base_type.declaration_code(
1549             "%s[%s]" % (entity_code, dimension_code),
1550             for_display, dll_linkage, pyrex)
1551
1552     def as_argument_type(self):
1553         return c_ptr_type(self.base_type)
1554
1555     def is_complete(self):
1556         return self.size is not None
1557
1558
1559 class CPtrType(CType):
1560     #  base_type     CType    Referenced type
1561
1562     is_ptr = 1
1563     default_value = "0"
1564
1565     def __init__(self, base_type):
1566         self.base_type = base_type
1567
1568     def __repr__(self):
1569         return "<CPtrType %s>" % repr(self.base_type)
1570
1571     def same_as_resolved_type(self, other_type):
1572         return ((other_type.is_ptr and
1573             self.base_type.same_as(other_type.base_type))
1574                 or other_type is error_type)
1575
1576     def declaration_code(self, entity_code,
1577             for_display = 0, dll_linkage = None, pyrex = 0):
1578         #print "CPtrType.declaration_code: pointer to", self.base_type ###
1579         return self.base_type.declaration_code(
1580             "*%s" % entity_code,
1581             for_display, dll_linkage, pyrex)
1582
1583     def assignable_from_resolved_type(self, other_type):
1584         if other_type is error_type:
1585             return 1
1586         if other_type.is_null_ptr:
1587             return 1
1588         if self.base_type.is_cfunction:
1589             if other_type.is_ptr:
1590                 other_type = other_type.base_type.resolve()
1591             if other_type.is_cfunction:
1592                 return self.base_type.pointer_assignable_from_resolved_type(other_type)
1593             else:
1594                 return 0
1595         if (self.base_type.is_cpp_class and other_type.is_ptr
1596                 and other_type.base_type.is_cpp_class and other_type.base_type.is_subclass(self.base_type)):
1597             return 1
1598         if other_type.is_array or other_type.is_ptr:
1599             return self.base_type.is_void or self.base_type.same_as(other_type.base_type)
1600         return 0
1601
1602     def specialize(self, values):
1603         base_type = self.base_type.specialize(values)
1604         if base_type == self.base_type:
1605             return self
1606         else:
1607             return CPtrType(base_type)
1608
1609
1610 class CNullPtrType(CPtrType):
1611
1612     is_null_ptr = 1
1613
1614
1615 class CReferenceType(BaseType):
1616
1617     is_reference = 1
1618
1619     def __init__(self, base_type):
1620         self.ref_base_type = base_type
1621
1622     def __repr__(self):
1623         return "<CReferenceType %s>" % repr(self.ref_base_type)
1624
1625     def __str__(self):
1626         return "%s &" % self.ref_base_type
1627
1628     def as_argument_type(self):
1629         return self
1630
1631     def declaration_code(self, entity_code,
1632             for_display = 0, dll_linkage = None, pyrex = 0):
1633         #print "CReferenceType.declaration_code: pointer to", self.base_type ###
1634         return self.ref_base_type.declaration_code(
1635             "&%s" % entity_code,
1636             for_display, dll_linkage, pyrex)
1637
1638     def specialize(self, values):
1639         base_type = self.ref_base_type.specialize(values)
1640         if base_type == self.ref_base_type:
1641             return self
1642         else:
1643             return CReferenceType(base_type)
1644
1645     def __getattr__(self, name):
1646         return getattr(self.ref_base_type, name)
1647
1648
1649 class CFuncType(CType):
1650     #  return_type      CType
1651     #  args             [CFuncTypeArg]
1652     #  has_varargs      boolean
1653     #  exception_value  string
1654     #  exception_check  boolean    True if PyErr_Occurred check needed
1655     #  calling_convention  string  Function calling convention
1656     #  nogil            boolean    Can be called without gil
1657     #  with_gil         boolean    Acquire gil around function body
1658     #  templates        [string] or None
1659
1660     is_cfunction = 1
1661     original_sig = None
1662
1663     def __init__(self, return_type, args, has_varargs = 0,
1664             exception_value = None, exception_check = 0, calling_convention = "",
1665             nogil = 0, with_gil = 0, is_overridable = 0, optional_arg_count = 0,
1666             templates = None):
1667         self.return_type = return_type
1668         self.args = args
1669         self.has_varargs = has_varargs
1670         self.optional_arg_count = optional_arg_count
1671         self.exception_value = exception_value
1672         self.exception_check = exception_check
1673         self.calling_convention = calling_convention
1674         self.nogil = nogil
1675         self.with_gil = with_gil
1676         self.is_overridable = is_overridable
1677         self.templates = templates
1678
1679     def __repr__(self):
1680         arg_reprs = map(repr, self.args)
1681         if self.has_varargs:
1682             arg_reprs.append("...")
1683         if self.exception_value:
1684             except_clause = " %r" % self.exception_value
1685         else:
1686             except_clause = ""
1687         if self.exception_check:
1688             except_clause += "?"
1689         return "<CFuncType %s %s[%s]%s>" % (
1690             repr(self.return_type),
1691             self.calling_convention_prefix(),
1692             ",".join(arg_reprs),
1693             except_clause)
1694
1695     def calling_convention_prefix(self):
1696         cc = self.calling_convention
1697         if cc:
1698             return cc + " "
1699         else:
1700             return ""
1701
1702     def same_c_signature_as(self, other_type, as_cmethod = 0):
1703         return self.same_c_signature_as_resolved_type(
1704             other_type.resolve(), as_cmethod)
1705
1706     def same_c_signature_as_resolved_type(self, other_type, as_cmethod = 0):
1707         #print "CFuncType.same_c_signature_as_resolved_type:", \
1708         #    self, other_type, "as_cmethod =", as_cmethod ###
1709         if other_type is error_type:
1710             return 1
1711         if not other_type.is_cfunction:
1712             return 0
1713         if self.is_overridable != other_type.is_overridable:
1714             return 0
1715         nargs = len(self.args)
1716         if nargs != len(other_type.args):
1717             return 0
1718         # When comparing C method signatures, the first argument
1719         # is exempt from compatibility checking (the proper check
1720         # is performed elsewhere).
1721         for i in range(as_cmethod, nargs):
1722             if not self.args[i].type.same_as(
1723                 other_type.args[i].type):
1724                     return 0
1725         if self.has_varargs != other_type.has_varargs:
1726             return 0
1727         if self.optional_arg_count != other_type.optional_arg_count:
1728             return 0
1729         if not self.return_type.same_as(other_type.return_type):
1730             return 0
1731         if not self.same_calling_convention_as(other_type):
1732             return 0
1733         return 1
1734
1735     def compatible_signature_with(self, other_type, as_cmethod = 0):
1736         return self.compatible_signature_with_resolved_type(other_type.resolve(), as_cmethod)
1737
1738     def compatible_signature_with_resolved_type(self, other_type, as_cmethod):
1739         #print "CFuncType.same_c_signature_as_resolved_type:", \
1740         #    self, other_type, "as_cmethod =", as_cmethod ###
1741         if other_type is error_type:
1742             return 1
1743         if not other_type.is_cfunction:
1744             return 0
1745         if not self.is_overridable and other_type.is_overridable:
1746             return 0
1747         nargs = len(self.args)
1748         if nargs - self.optional_arg_count != len(other_type.args) - other_type.optional_arg_count:
1749             return 0
1750         if self.optional_arg_count < other_type.optional_arg_count:
1751             return 0
1752         # When comparing C method signatures, the first argument
1753         # is exempt from compatibility checking (the proper check
1754         # is performed elsewhere).
1755         for i in range(as_cmethod, len(other_type.args)):
1756             if not self.args[i].type.same_as(
1757                 other_type.args[i].type):
1758                     return 0
1759         if self.has_varargs != other_type.has_varargs:
1760             return 0
1761         if not self.return_type.subtype_of_resolved_type(other_type.return_type):
1762             return 0
1763         if not self.same_calling_convention_as(other_type):
1764             return 0
1765         if self.nogil != other_type.nogil:
1766             return 0
1767         self.original_sig = other_type.original_sig or other_type
1768         if as_cmethod:
1769             self.args[0] = other_type.args[0]
1770         return 1
1771
1772
1773     def narrower_c_signature_than(self, other_type, as_cmethod = 0):
1774         return self.narrower_c_signature_than_resolved_type(other_type.resolve(), as_cmethod)
1775
1776     def narrower_c_signature_than_resolved_type(self, other_type, as_cmethod):
1777         if other_type is error_type:
1778             return 1
1779         if not other_type.is_cfunction:
1780             return 0
1781         nargs = len(self.args)
1782         if nargs != len(other_type.args):
1783             return 0
1784         for i in range(as_cmethod, nargs):
1785             if not self.args[i].type.subtype_of_resolved_type(other_type.args[i].type):
1786                 return 0
1787             else:
1788                 self.args[i].needs_type_test = other_type.args[i].needs_type_test \
1789                         or not self.args[i].type.same_as(other_type.args[i].type)
1790         if self.has_varargs != other_type.has_varargs:
1791             return 0
1792         if self.optional_arg_count != other_type.optional_arg_count:
1793             return 0
1794         if not self.return_type.subtype_of_resolved_type(other_type.return_type):
1795             return 0
1796         return 1
1797
1798     def same_calling_convention_as(self, other):
1799         ## XXX Under discussion ...
1800         ## callspec_words = ("__stdcall", "__cdecl", "__fastcall")
1801         ## cs1 = self.calling_convention
1802         ## cs2 = other.calling_convention
1803         ## if (cs1 in callspec_words or
1804         ##     cs2 in callspec_words):
1805         ##     return cs1 == cs2
1806         ## else:
1807         ##     return True
1808         sc1 = self.calling_convention == '__stdcall'
1809         sc2 = other.calling_convention == '__stdcall'
1810         return sc1 == sc2
1811
1812     def same_exception_signature_as(self, other_type):
1813         return self.same_exception_signature_as_resolved_type(
1814             other_type.resolve())
1815
1816     def same_exception_signature_as_resolved_type(self, other_type):
1817         return self.exception_value == other_type.exception_value \
1818             and self.exception_check == other_type.exception_check
1819
1820     def same_as_resolved_type(self, other_type, as_cmethod = 0):
1821         return self.same_c_signature_as_resolved_type(other_type, as_cmethod) \
1822             and self.same_exception_signature_as_resolved_type(other_type) \
1823             and self.nogil == other_type.nogil
1824
1825     def pointer_assignable_from_resolved_type(self, other_type):
1826         return self.same_c_signature_as_resolved_type(other_type) \
1827             and self.same_exception_signature_as_resolved_type(other_type) \
1828             and not (self.nogil and not other_type.nogil)
1829
1830     def declaration_code(self, entity_code,
1831                          for_display = 0, dll_linkage = None, pyrex = 0,
1832                          with_calling_convention = 1):
1833         arg_decl_list = []
1834         for arg in self.args[:len(self.args)-self.optional_arg_count]:
1835             arg_decl_list.append(
1836                 arg.type.declaration_code("", for_display, pyrex = pyrex))
1837         if self.is_overridable:
1838             arg_decl_list.append("int %s" % Naming.skip_dispatch_cname)
1839         if self.optional_arg_count:
1840             arg_decl_list.append(self.op_arg_struct.declaration_code(Naming.optional_args_cname))
1841         if self.has_varargs:
1842             arg_decl_list.append("...")
1843         arg_decl_code = ", ".join(arg_decl_list)
1844         if not arg_decl_code and not pyrex:
1845             arg_decl_code = "void"
1846         trailer = ""
1847         if (pyrex or for_display) and not self.return_type.is_pyobject:
1848             if self.exception_value and self.exception_check:
1849                 trailer = " except? %s" % self.exception_value
1850             elif self.exception_value:
1851                 trailer = " except %s" % self.exception_value
1852             elif self.exception_check == '+':
1853                 trailer = " except +"
1854             else:
1855                 " except *" # ignored
1856             if self.nogil:
1857                 trailer += " nogil"
1858         if not with_calling_convention:
1859             cc = ''
1860         else:
1861             cc = self.calling_convention_prefix()
1862             if (not entity_code and cc) or entity_code.startswith("*"):
1863                 entity_code = "(%s%s)" % (cc, entity_code)
1864                 cc = ""
1865         return self.return_type.declaration_code(
1866             "%s%s(%s)%s" % (cc, entity_code, arg_decl_code, trailer),
1867             for_display, dll_linkage, pyrex)
1868
1869     def function_header_code(self, func_name, arg_code):
1870         return "%s%s(%s)" % (self.calling_convention_prefix(),
1871             func_name, arg_code)
1872
1873     def signature_string(self):
1874         s = self.declaration_code("")
1875         return s
1876
1877     def signature_cast_string(self):
1878         s = self.declaration_code("(*)", with_calling_convention=False)
1879         return '(%s)' % s
1880
1881     def specialize(self, values):
1882         if self.templates is None:
1883             new_templates = None
1884         else:
1885             new_templates = [v.specialize(values) for v in self.templates]
1886         return CFuncType(self.return_type.specialize(values),
1887                              [arg.specialize(values) for arg in self.args],
1888                              has_varargs = 0,
1889                              exception_value = self.exception_value,
1890                              exception_check = self.exception_check,
1891                              calling_convention = self.calling_convention,
1892                              nogil = self.nogil,
1893                              with_gil = self.with_gil,
1894                              is_overridable = self.is_overridable,
1895                              optional_arg_count = self.optional_arg_count,
1896                              templates = new_templates)
1897
1898     def opt_arg_cname(self, arg_name):
1899         return self.op_arg_struct.base_type.scope.lookup(arg_name).cname
1900
1901
1902 class CFuncTypeArg(object):
1903     #  name       string
1904     #  cname      string
1905     #  type       PyrexType
1906     #  pos        source file position
1907
1908     # FIXME: is this the right setup? should None be allowed here?
1909     not_none = False
1910     or_none = False
1911     accept_none = True
1912
1913     def __init__(self, name, type, pos, cname=None):
1914         self.name = name
1915         if cname is not None:
1916             self.cname = cname
1917         else:
1918             self.cname = Naming.var_prefix + name
1919         self.type = type
1920         self.pos = pos
1921         self.needs_type_test = False # TODO: should these defaults be set in analyse_types()?
1922
1923     def __repr__(self):
1924         return "%s:%s" % (self.name, repr(self.type))
1925
1926     def declaration_code(self, for_display = 0):
1927         return self.type.declaration_code(self.cname, for_display)
1928
1929     def specialize(self, values):
1930         return CFuncTypeArg(self.name, self.type.specialize(values), self.pos, self.cname)
1931
1932 class StructUtilityCode(object):
1933     def __init__(self, type, forward_decl):
1934         self.type = type
1935         self.header = "static PyObject* %s(%s)" % (type.to_py_function, type.declaration_code('s'))
1936         self.forward_decl = forward_decl
1937
1938     def __eq__(self, other):
1939         return isinstance(other, StructUtilityCode) and self.header == other.header
1940     def __hash__(self):
1941         return hash(self.header)
1942
1943     def put_code(self, output):
1944         code = output['utility_code_def']
1945         proto = output['utility_code_proto']
1946
1947         code.putln("%s {" % self.header)
1948         code.putln("PyObject* res;")
1949         code.putln("PyObject* member;")
1950         code.putln("res = PyDict_New(); if (res == NULL) return NULL;")
1951         for member in self.type.scope.var_entries:
1952             nameconst_cname = code.get_py_string_const(member.name, identifier=True)
1953             code.putln("member = %s(s.%s); if (member == NULL) goto bad;" % (
1954                 member.type.to_py_function, member.cname))
1955             code.putln("if (PyDict_SetItem(res, %s, member) < 0) goto bad;" % nameconst_cname)
1956             code.putln("Py_DECREF(member);")
1957         code.putln("return res;")
1958         code.putln("bad:")
1959         code.putln("Py_XDECREF(member);")
1960         code.putln("Py_DECREF(res);")
1961         code.putln("return NULL;")
1962         code.putln("}")
1963
1964         # This is a bit of a hack, we need a forward declaration
1965         # due to the way things are ordered in the module...
1966         if self.forward_decl:
1967             proto.putln(self.type.declaration_code('') + ';')
1968         proto.putln(self.header + ";")
1969
1970
1971 class CStructOrUnionType(CType):
1972     #  name          string
1973     #  cname         string
1974     #  kind          string              "struct" or "union"
1975     #  scope         StructOrUnionScope, or None if incomplete
1976     #  typedef_flag  boolean
1977     #  packed        boolean
1978
1979     # entry          Entry
1980
1981     is_struct_or_union = 1
1982     has_attributes = 1
1983
1984     def __init__(self, name, kind, scope, typedef_flag, cname, packed=False):
1985         self.name = name
1986         self.cname = cname
1987         self.kind = kind
1988         self.scope = scope
1989         self.typedef_flag = typedef_flag
1990         self.is_struct = kind == 'struct'
1991         if self.is_struct:
1992             self.to_py_function = "%s_to_py_%s" % (Naming.convert_func_prefix, self.cname)
1993         self.exception_check = True
1994         self._convert_code = None
1995         self.packed = packed
1996
1997     def create_to_py_utility_code(self, env):
1998         if env.outer_scope is None:
1999             return False
2000
2001         if self._convert_code is False: return # tri-state-ish
2002
2003         if self._convert_code is None:
2004             for member in self.scope.var_entries:
2005                 if not member.type.to_py_function or not member.type.create_to_py_utility_code(env):
2006                     self.to_py_function = None
2007                     self._convert_code = False
2008                     return False
2009             forward_decl = (self.entry.visibility != 'extern')
2010             self._convert_code = StructUtilityCode(self, forward_decl)
2011
2012         env.use_utility_code(self._convert_code)
2013         return True
2014
2015     def __repr__(self):
2016         return "<CStructOrUnionType %s %s%s>" % (self.name, self.cname,
2017             ("", " typedef")[self.typedef_flag])
2018
2019     def declaration_code(self, entity_code,
2020             for_display = 0, dll_linkage = None, pyrex = 0):
2021         if pyrex or for_display:
2022             base_code = self.name
2023         else:
2024             if self.typedef_flag:
2025                 base_code = self.cname
2026             else:
2027                 base_code = "%s %s" % (self.kind, self.cname)
2028             base_code = public_decl(base_code, dll_linkage)
2029         return self.base_declaration_code(base_code, entity_code)
2030
2031     def __eq__(self, other):
2032         try:
2033             return (isinstance(other, CStructOrUnionType) and
2034                     self.name == other.name)
2035         except AttributeError:
2036             return False
2037
2038     def __lt__(self, other):
2039         try:
2040             return self.name < other.name
2041         except AttributeError:
2042             # this is arbitrary, but it makes sure we always have
2043             # *some* kind of order
2044             return False
2045
2046     def __hash__(self):
2047         return hash(self.cname) ^ hash(self.kind)
2048
2049     def is_complete(self):
2050         return self.scope is not None
2051
2052     def attributes_known(self):
2053         return self.is_complete()
2054
2055     def can_be_complex(self):
2056         # Does the struct consist of exactly two identical floats?
2057         fields = self.scope.var_entries
2058         if len(fields) != 2: return False
2059         a, b = fields
2060         return (a.type.is_float and b.type.is_float and
2061                 a.type.declaration_code("") ==
2062                 b.type.declaration_code(""))
2063
2064     def struct_nesting_depth(self):
2065         child_depths = [x.type.struct_nesting_depth()
2066                         for x in self.scope.var_entries]
2067         return max(child_depths) + 1
2068
2069 class CppClassType(CType):
2070     #  name          string
2071     #  cname         string
2072     #  scope         CppClassScope
2073     #  templates     [string] or None
2074
2075     is_cpp_class = 1
2076     has_attributes = 1
2077     exception_check = True
2078     namespace = None
2079
2080     def __init__(self, name, scope, cname, base_classes, templates = None, template_type = None):
2081         self.name = name
2082         self.cname = cname
2083         self.scope = scope
2084         self.base_classes = base_classes
2085         self.operators = []
2086         self.templates = templates
2087         self.template_type = template_type
2088         self.specializations = {}
2089
2090     def specialize_here(self, pos, template_values = None):
2091         if self.templates is None:
2092             error(pos, "'%s' type is not a template" % self);
2093             return PyrexTypes.error_type
2094         if len(self.templates) != len(template_values):
2095             error(pos, "%s templated type receives %d arguments, got %d" %
2096                   (self.name, len(self.templates), len(template_values)))
2097             return error_type
2098         return self.specialize(dict(zip(self.templates, template_values)))
2099
2100     def specialize(self, values):
2101         if not self.templates and not self.namespace:
2102             return self
2103         if self.templates is None:
2104             self.templates = []
2105         key = tuple(values.items())
2106         if key in self.specializations:
2107             return self.specializations[key]
2108         template_values = [t.specialize(values) for t in self.templates]
2109         specialized = self.specializations[key] = \
2110             CppClassType(self.name, None, self.cname, [], template_values, template_type=self)
2111         # Need to do these *after* self.specializations[key] is set
2112         # to avoid infinite recursion on circular references.
2113         specialized.base_classes = [b.specialize(values) for b in self.base_classes]
2114         specialized.scope = self.scope.specialize(values)
2115         if self.namespace is not None:
2116             specialized.namespace = self.namespace.specialize(values)
2117         return specialized
2118
2119     def declaration_code(self, entity_code,
2120             for_display = 0, dll_linkage = None, pyrex = 0):
2121         if self.templates:
2122             template_strings = [param.declaration_code('', for_display, None, pyrex)
2123                                 for param in self.templates]
2124             templates = "<%s>" % ",".join(template_strings)
2125             if templates[-2:] == ">>":
2126                 templates = templates[:-2] + "> >"
2127         else:
2128             templates = ""
2129         if pyrex or for_display:
2130             base_code = "%s%s" % (self.name, templates)
2131         else:
2132             base_code = "%s%s" % (self.cname, templates)
2133             if self.namespace is not None:
2134                 base_code = "%s::%s" % (self.namespace.declaration_code(''), base_code)
2135             base_code = public_decl(base_code, dll_linkage)
2136         return self.base_declaration_code(base_code, entity_code)
2137
2138     def is_subclass(self, other_type):
2139         # TODO(danilo): Handle templates.
2140         if self.same_as_resolved_type(other_type):
2141             return 1
2142         for base_class in self.base_classes:
2143             if base_class.is_subclass(other_type):
2144                 return 1
2145         return 0
2146
2147     def same_as_resolved_type(self, other_type):
2148         if other_type.is_cpp_class:
2149             if self == other_type:
2150                 return 1
2151             elif self.template_type and self.template_type == other_type.template_type:
2152                 if self.templates == other_type.templates:
2153                     return 1
2154                 for t1, t2 in zip(self.templates, other_type.templates):
2155                     if not t1.same_as_resolved_type(t2):
2156                         return 0
2157                 return 1
2158         return 0
2159
2160     def assignable_from_resolved_type(self, other_type):
2161         # TODO: handle operator=(...) here?
2162         if other_type is error_type:
2163             return True
2164         return other_type.is_cpp_class and other_type.is_subclass(self)
2165
2166     def attributes_known(self):
2167         return self.scope is not None
2168
2169
2170 class TemplatePlaceholderType(CType):
2171
2172     def __init__(self, name):
2173         self.name = name
2174
2175     def declaration_code(self, entity_code,
2176             for_display = 0, dll_linkage = None, pyrex = 0):
2177         if entity_code:
2178             return self.name + " " + entity_code
2179         else:
2180             return self.name
2181
2182     def specialize(self, values):
2183         if self in values:
2184             return values[self]
2185         else:
2186             return self
2187
2188     def same_as_resolved_type(self, other_type):
2189         if isinstance(other_type, TemplatePlaceholderType):
2190             return self.name == other_type.name
2191         else:
2192             return 0
2193
2194     def __hash__(self):
2195         return hash(self.name)
2196
2197     def __cmp__(self, other):
2198         if isinstance(other, TemplatePlaceholderType):
2199             return cmp(self.name, other.name)
2200         else:
2201             return cmp(type(self), type(other))
2202
2203 class CEnumType(CType):
2204     #  name           string
2205     #  cname          string or None
2206     #  typedef_flag   boolean
2207
2208     is_enum = 1
2209     signed = 1
2210     rank = -1 # Ranks below any integer type
2211     to_py_function = "PyInt_FromLong"
2212     from_py_function = "PyInt_AsLong"
2213
2214     def __init__(self, name, cname, typedef_flag):
2215         self.name = name
2216         self.cname = cname
2217         self.values = []
2218         self.typedef_flag = typedef_flag
2219
2220     def __str__(self):
2221         return self.name
2222
2223     def __repr__(self):
2224         return "<CEnumType %s %s%s>" % (self.name, self.cname,
2225             ("", " typedef")[self.typedef_flag])
2226
2227     def declaration_code(self, entity_code,
2228             for_display = 0, dll_linkage = None, pyrex = 0):
2229         if pyrex or for_display:
2230             base_code = self.name
2231         else:
2232             if self.typedef_flag:
2233                 base_code = self.cname
2234             else:
2235                 base_code = "enum %s" % self.cname
2236             base_code = public_decl(base_code, dll_linkage)
2237         return self.base_declaration_code(base_code, entity_code)
2238
2239
2240 class CStringType(object):
2241     #  Mixin class for C string types.
2242
2243     is_string = 1
2244     is_unicode = 0
2245
2246     to_py_function = "PyBytes_FromString"
2247     from_py_function = "PyBytes_AsString"
2248     exception_value = "NULL"
2249
2250     def literal_code(self, value):
2251         assert isinstance(value, str)
2252         return '"%s"' % StringEncoding.escape_byte_string(value)
2253
2254
2255 class CUTF8CharArrayType(CStringType, CArrayType):
2256     #  C 'char []' type.
2257
2258     is_unicode = 1
2259
2260     to_py_function = "PyUnicode_DecodeUTF8"
2261     exception_value = "NULL"
2262
2263     def __init__(self, size):
2264         CArrayType.__init__(self, c_char_type, size)
2265
2266 class CCharArrayType(CStringType, CArrayType):
2267     #  C 'char []' type.
2268
2269     def __init__(self, size):
2270         CArrayType.__init__(self, c_char_type, size)
2271
2272
2273 class CCharPtrType(CStringType, CPtrType):
2274     # C 'char *' type.
2275
2276     def __init__(self):
2277         CPtrType.__init__(self, c_char_type)
2278
2279
2280 class CUCharPtrType(CStringType, CPtrType):
2281     # C 'unsigned char *' type.
2282
2283     to_py_function = "__Pyx_PyBytes_FromUString"
2284     from_py_function = "__Pyx_PyBytes_AsUString"
2285
2286     def __init__(self):
2287         CPtrType.__init__(self, c_uchar_type)
2288
2289
2290 class UnspecifiedType(PyrexType):
2291     # Used as a placeholder until the type can be determined.
2292
2293     is_unspecified = 1
2294
2295     def declaration_code(self, entity_code,
2296             for_display = 0, dll_linkage = None, pyrex = 0):
2297         return "<unspecified>"
2298
2299     def same_as_resolved_type(self, other_type):
2300         return False
2301
2302
2303 class ErrorType(PyrexType):
2304     # Used to prevent propagation of error messages.
2305
2306     is_error = 1
2307     exception_value = "0"
2308     exception_check    = 0
2309     to_py_function = "dummy"
2310     from_py_function = "dummy"
2311
2312     def create_to_py_utility_code(self, env):
2313         return True
2314
2315     def create_from_py_utility_code(self, env):
2316         return True
2317
2318     def declaration_code(self, entity_code,
2319             for_display = 0, dll_linkage = None, pyrex = 0):
2320         return "<error>"
2321
2322     def same_as_resolved_type(self, other_type):
2323         return 1
2324
2325     def error_condition(self, result_code):
2326         return "dummy"
2327
2328
2329 rank_to_type_name = (
2330     "char",         # 0
2331     "short",        # 1
2332     "int",          # 2
2333     "long",         # 3
2334     "PY_LONG_LONG", # 4
2335     "float",        # 5
2336     "double",       # 6
2337     "long double",  # 7
2338 )
2339
2340 RANK_INT  = list(rank_to_type_name).index('int')
2341 RANK_LONG = list(rank_to_type_name).index('long')
2342 UNSIGNED = 0
2343 SIGNED = 2
2344
2345
2346 py_object_type = PyObjectType()
2347
2348 c_void_type =        CVoidType()
2349
2350 c_uchar_type =       CIntType(0, UNSIGNED)
2351 c_ushort_type =      CIntType(1, UNSIGNED)
2352 c_uint_type =        CIntType(2, UNSIGNED)
2353 c_ulong_type =       CIntType(3, UNSIGNED)
2354 c_ulonglong_type =   CIntType(4, UNSIGNED)
2355
2356 c_char_type =        CIntType(0)
2357 c_short_type =       CIntType(1)
2358 c_int_type =         CIntType(2)
2359 c_long_type =        CIntType(3)
2360 c_longlong_type =    CIntType(4)
2361
2362 c_schar_type =       CIntType(0, SIGNED)
2363 c_sshort_type =      CIntType(1, SIGNED)
2364 c_sint_type =        CIntType(2, SIGNED)
2365 c_slong_type =       CIntType(3, SIGNED)
2366 c_slonglong_type =   CIntType(4, SIGNED)
2367
2368 c_float_type =       CFloatType(5, math_h_modifier='f')
2369 c_double_type =      CFloatType(6)
2370 c_longdouble_type =  CFloatType(7, math_h_modifier='l')
2371
2372 c_float_complex_type =      CComplexType(c_float_type)
2373 c_double_complex_type =     CComplexType(c_double_type)
2374 c_longdouble_complex_type = CComplexType(c_longdouble_type)
2375
2376 c_anon_enum_type =   CAnonEnumType(-1)
2377 c_returncode_type =  CReturnCodeType(RANK_INT)
2378 c_bint_type =        CBIntType(RANK_INT)
2379 c_py_unicode_type =  CPyUnicodeIntType(RANK_INT-0.5, UNSIGNED)
2380 c_py_ucs4_type =     CPyUCS4IntType(RANK_LONG-0.5, UNSIGNED)
2381 c_py_ssize_t_type =  CPySSizeTType(RANK_LONG+0.5, SIGNED)
2382 c_ssize_t_type =     CSSizeTType(RANK_LONG+0.5, SIGNED)
2383 c_size_t_type =      CSizeTType(RANK_LONG+0.5, UNSIGNED)
2384
2385 c_null_ptr_type =     CNullPtrType(c_void_type)
2386 c_void_ptr_type =     CPtrType(c_void_type)
2387 c_void_ptr_ptr_type = CPtrType(c_void_ptr_type)
2388 c_char_array_type =   CCharArrayType(None)
2389 c_char_ptr_type =     CCharPtrType()
2390 c_uchar_ptr_type =    CUCharPtrType()
2391 c_utf8_char_array_type = CUTF8CharArrayType(None)
2392 c_char_ptr_ptr_type = CPtrType(c_char_ptr_type)
2393 c_int_ptr_type =      CPtrType(c_int_type)
2394 c_py_unicode_ptr_type = CPtrType(c_py_unicode_type)
2395 c_py_ssize_t_ptr_type =  CPtrType(c_py_ssize_t_type)
2396 c_ssize_t_ptr_type =  CPtrType(c_ssize_t_type)
2397 c_size_t_ptr_type =  CPtrType(c_size_t_type)
2398
2399
2400 # the Py_buffer type is defined in Builtin.py
2401 c_py_buffer_type = CStructOrUnionType("Py_buffer", "struct", None, 1, "Py_buffer")
2402 c_py_buffer_ptr_type = CPtrType(c_py_buffer_type)
2403
2404 error_type =    ErrorType()
2405 unspecified_type = UnspecifiedType()
2406
2407 modifiers_and_name_to_type = {
2408     #(signed, longness, name) : type
2409     (0,  0, "char"): c_uchar_type,
2410     (1,  0, "char"): c_char_type,
2411     (2,  0, "char"): c_schar_type,
2412
2413     (0, -1, "int"): c_ushort_type,
2414     (0,  0, "int"): c_uint_type,
2415     (0,  1, "int"): c_ulong_type,
2416     (0,  2, "int"): c_ulonglong_type,
2417
2418     (1, -1, "int"): c_short_type,
2419     (1,  0, "int"): c_int_type,
2420     (1,  1, "int"): c_long_type,
2421     (1,  2, "int"): c_longlong_type,
2422
2423     (2, -1, "int"): c_sshort_type,
2424     (2,  0, "int"): c_sint_type,
2425     (2,  1, "int"): c_slong_type,
2426     (2,  2, "int"): c_slonglong_type,
2427
2428     (1,  0, "float"):  c_float_type,
2429     (1,  0, "double"): c_double_type,
2430     (1,  1, "double"): c_longdouble_type,
2431
2432     (1,  0, "complex"):  c_double_complex_type,  # C: float, Python: double => Python wins
2433     (1,  0, "floatcomplex"):  c_float_complex_type,
2434     (1,  0, "doublecomplex"): c_double_complex_type,
2435     (1,  1, "doublecomplex"): c_longdouble_complex_type,
2436
2437     #
2438     (1,  0, "void"): c_void_type,
2439
2440     (1,  0, "bint"):       c_bint_type,
2441     (0,  0, "Py_UNICODE"): c_py_unicode_type,
2442     (0,  0, "Py_UCS4"):    c_py_ucs4_type,
2443     (2,  0, "Py_ssize_t"): c_py_ssize_t_type,
2444     (2,  0, "ssize_t") :   c_ssize_t_type,
2445     (0,  0, "size_t") :    c_size_t_type,
2446
2447     (1,  0, "object"): py_object_type,
2448 }
2449
2450 def is_promotion(src_type, dst_type):
2451     # It's hard to find a hard definition of promotion, but empirical
2452     # evidence suggests that the below is all that's allowed.
2453     if src_type.is_numeric:
2454         if dst_type.same_as(c_int_type):
2455             unsigned = (not src_type.signed)
2456             return (src_type.is_enum or
2457                     (src_type.is_int and
2458                      unsigned + src_type.rank < dst_type.rank))
2459         elif dst_type.same_as(c_double_type):
2460             return src_type.is_float and src_type.rank <= dst_type.rank
2461     return False
2462
2463 def best_match(args, functions, pos=None):
2464     """
2465     Given a list args of arguments and a list of functions, choose one
2466     to call which seems to be the "best" fit for this list of arguments.
2467     This function is used, e.g., when deciding which overloaded method
2468     to dispatch for C++ classes.
2469
2470     We first eliminate functions based on arity, and if only one
2471     function has the correct arity, we return it. Otherwise, we weight
2472     functions based on how much work must be done to convert the
2473     arguments, with the following priorities:
2474       * identical types or pointers to identical types
2475       * promotions
2476       * non-Python types
2477     That is, we prefer functions where no arguments need converted,
2478     and failing that, functions where only promotions are required, and
2479     so on.
2480
2481     If no function is deemed a good fit, or if two or more functions have
2482     the same weight, we return None (as there is no best match). If pos
2483     is not None, we also generate an error.
2484     """
2485     # TODO: args should be a list of types, not a list of Nodes.
2486     actual_nargs = len(args)
2487
2488     candidates = []
2489     errors = []
2490     for func in functions:
2491         error_mesg = ""
2492         func_type = func.type
2493         if func_type.is_ptr:
2494             func_type = func_type.base_type
2495         # Check function type
2496         if not func_type.is_cfunction:
2497             if not func_type.is_error and pos is not None:
2498                 error_mesg = "Calling non-function type '%s'" % func_type
2499             errors.append((func, error_mesg))
2500             continue
2501         # Check no. of args
2502         max_nargs = len(func_type.args)
2503         min_nargs = max_nargs - func_type.optional_arg_count
2504         if actual_nargs < min_nargs or \
2505             (not func_type.has_varargs and actual_nargs > max_nargs):
2506             if max_nargs == min_nargs and not func_type.has_varargs:
2507                 expectation = max_nargs
2508             elif actual_nargs < min_nargs:
2509                 expectation = "at least %s" % min_nargs
2510             else:
2511                 expectation = "at most %s" % max_nargs
2512             error_mesg = "Call with wrong number of arguments (expected %s, got %s)" \
2513                          % (expectation, actual_nargs)
2514             errors.append((func, error_mesg))
2515             continue
2516         candidates.append((func, func_type))
2517
2518     # Optimize the most common case of no overloading...
2519     if len(candidates) == 1:
2520         return candidates[0][0]
2521     elif len(candidates) == 0:
2522         if pos is not None:
2523             if len(errors) == 1:
2524                 error(pos, errors[0][1])
2525             else:
2526                 error(pos, "no suitable method found")
2527         return None
2528
2529     possibilities = []
2530     bad_types = []
2531     for func, func_type in candidates:
2532         score = [0,0,0]
2533         for i in range(min(len(args), len(func_type.args))):
2534             src_type = args[i].type
2535             dst_type = func_type.args[i].type
2536             if dst_type.assignable_from(src_type):
2537                 if src_type == dst_type or dst_type.same_as(src_type):
2538                     pass # score 0
2539                 elif is_promotion(src_type, dst_type):
2540                     score[2] += 1
2541                 elif not src_type.is_pyobject:
2542                     score[1] += 1
2543                 else:
2544                     score[0] += 1
2545             else:
2546                 error_mesg = "Invalid conversion from '%s' to '%s'"%(src_type,
2547                                                                      dst_type)
2548                 bad_types.append((func, error_mesg))
2549                 break
2550         else:
2551             possibilities.append((score, func)) # so we can sort it
2552     if possibilities:
2553         possibilities.sort()
2554         if len(possibilities) > 1 and possibilities[0][0] == possibilities[1][0]:
2555             if pos is not None:
2556                 error(pos, "ambiguous overloaded method")
2557             return None
2558         return possibilities[0][1]
2559     if pos is not None:
2560         if len(bad_types) == 1:
2561             error(pos, bad_types[0][1])
2562         else:
2563             error(pos, "no suitable method found")
2564     return None
2565
2566 def widest_numeric_type(type1, type2):
2567     # Given two numeric types, return the narrowest type
2568     # encompassing both of them.
2569     if type1 == type2:
2570         widest_type = type1
2571     elif type1.is_complex or type2.is_complex:
2572         def real_type(ntype):
2573             if ntype.is_complex:
2574                 return ntype.real_type
2575             return ntype
2576         widest_type = CComplexType(
2577             widest_numeric_type(
2578                 real_type(type1),
2579                 real_type(type2)))
2580     elif type1.is_enum and type2.is_enum:
2581         widest_type = c_int_type
2582     elif type1.rank < type2.rank:
2583         widest_type = type2
2584     elif type1.rank > type2.rank:
2585         widest_type = type1
2586     elif type1.signed < type2.signed:
2587         widest_type = type1
2588     else:
2589         widest_type = type2
2590     return widest_type
2591
2592 def independent_spanning_type(type1, type2):
2593     # Return a type assignable independently from both type1 and
2594     # type2, but do not require any interoperability between the two.
2595     # For example, in "True * 2", it is safe to assume an integer
2596     # result type (so spanning_type() will do the right thing),
2597     # whereas "x = True or 2" must evaluate to a type that can hold
2598     # both a boolean value and an integer, so this function works
2599     # better.
2600     if type1 == type2:
2601         return type1
2602     elif (type1 is c_bint_type or type2 is c_bint_type) and (type1.is_numeric and type2.is_numeric):
2603         # special case: if one of the results is a bint and the other
2604         # is another C integer, we must prevent returning a numeric
2605         # type so that we do not lose the ability to coerce to a
2606         # Python bool if we have to.
2607         return py_object_type
2608     span_type = _spanning_type(type1, type2)
2609     if span_type is None:
2610         return error_type
2611     return span_type
2612
2613 def spanning_type(type1, type2):
2614     # Return a type assignable from both type1 and type2, or
2615     # py_object_type if no better type is found.  Assumes that the
2616     # code that calls this will try a coercion afterwards, which will
2617     # fail if the types cannot actually coerce to a py_object_type.
2618     if type1 == type2:
2619         return type1
2620     elif type1 is py_object_type or type2 is py_object_type:
2621         return py_object_type
2622     elif type1 is c_py_unicode_type or type2 is c_py_unicode_type:
2623         # Py_UNICODE behaves more like a string than an int
2624         return py_object_type
2625     span_type = _spanning_type(type1, type2)
2626     if span_type is None:
2627         return py_object_type
2628     return span_type
2629
2630 def _spanning_type(type1, type2):
2631     if type1.is_numeric and type2.is_numeric:
2632         return widest_numeric_type(type1, type2)
2633     elif type1.is_builtin_type and type1.name == 'float' and type2.is_numeric:
2634         return widest_numeric_type(c_double_type, type2)
2635     elif type2.is_builtin_type and type2.name == 'float' and type1.is_numeric:
2636         return widest_numeric_type(type1, c_double_type)
2637     elif type1.is_extension_type and type2.is_extension_type:
2638         return widest_extension_type(type1, type2)
2639     elif type1.is_pyobject or type2.is_pyobject:
2640         return py_object_type
2641     elif type1.assignable_from(type2):
2642         if type1.is_extension_type and type1.typeobj_is_imported():
2643             # external types are unsafe, so we use PyObject instead
2644             return py_object_type
2645         return type1
2646     elif type2.assignable_from(type1):
2647         if type2.is_extension_type and type2.typeobj_is_imported():
2648             # external types are unsafe, so we use PyObject instead
2649             return py_object_type
2650         return type2
2651     else:
2652         return None
2653
2654 def widest_extension_type(type1, type2):
2655     if type1.typeobj_is_imported() or type2.typeobj_is_imported():
2656         return py_object_type
2657     while True:
2658         if type1.subtype_of(type2):
2659             return type2
2660         elif type2.subtype_of(type1):
2661             return type1
2662         type1, type2 = type1.base_type, type2.base_type
2663         if type1 is None or type2 is None:
2664             return py_object_type
2665
2666 def simple_c_type(signed, longness, name):
2667     # Find type descriptor for simple type given name and modifiers.
2668     # Returns None if arguments don't make sense.
2669     return modifiers_and_name_to_type.get((signed, longness, name))
2670
2671 def parse_basic_type(name):
2672     base = None
2673     if name.startswith('p_'):
2674         base = parse_basic_type(name[2:])
2675     elif name.startswith('p'):
2676         base = parse_basic_type(name[1:])
2677     elif name.endswith('*'):
2678         base = parse_basic_type(name[:-1])
2679     if base:
2680         return CPtrType(base)
2681     #
2682     basic_type = simple_c_type(1, 0, name)
2683     if basic_type:
2684         return basic_type
2685     #
2686     signed = 1
2687     longness = 0
2688     if name == 'Py_UNICODE':
2689         signed = 0
2690     elif name == 'Py_UCS4':
2691         signed = 0
2692     elif name == 'Py_ssize_t':
2693         signed = 2
2694     elif name == 'ssize_t':
2695         signed = 2
2696     elif name == 'size_t':
2697         signed = 0
2698     else:
2699         if name.startswith('u'):
2700             name = name[1:]
2701             signed = 0
2702         elif (name.startswith('s') and
2703               not name.startswith('short')):
2704             name = name[1:]
2705             signed = 2
2706         longness = 0
2707         while name.startswith('short'):
2708             name = name.replace('short', '', 1).strip()
2709             longness -= 1
2710         while name.startswith('long'):
2711             name = name.replace('long', '', 1).strip()
2712             longness += 1
2713         if longness != 0 and not name:
2714             name = 'int'
2715     return simple_c_type(signed, longness, name)
2716
2717 def c_array_type(base_type, size):
2718     # Construct a C array type.
2719     if base_type is c_char_type:
2720         return CCharArrayType(size)
2721     elif base_type is error_type:
2722         return error_type
2723     else:
2724         return CArrayType(base_type, size)
2725
2726 def c_ptr_type(base_type):
2727     # Construct a C pointer type.
2728     if base_type is c_char_type:
2729         return c_char_ptr_type
2730     elif base_type is c_uchar_type:
2731         return c_uchar_ptr_type
2732     elif base_type is error_type:
2733         return error_type
2734     else:
2735         return CPtrType(base_type)
2736
2737 def c_ref_type(base_type):
2738     # Construct a C reference type
2739     if base_type is error_type:
2740         return error_type
2741     else:
2742         return CReferenceType(base_type)
2743
2744 def same_type(type1, type2):
2745     return type1.same_as(type2)
2746
2747 def assignable_from(type1, type2):
2748     return type1.assignable_from(type2)
2749
2750 def typecast(to_type, from_type, expr_code):
2751     #  Return expr_code cast to a C type which can be
2752     #  assigned to to_type, assuming its existing C type
2753     #  is from_type.
2754     if to_type is from_type or \
2755         (not to_type.is_pyobject and assignable_from(to_type, from_type)):
2756             return expr_code
2757     else:
2758         #print "typecast: to", to_type, "from", from_type ###
2759         return to_type.cast_code(expr_code)
2760
2761
2762 type_conversion_predeclarations = """
2763 /* Type Conversion Predeclarations */
2764
2765 #define __Pyx_PyBytes_FromUString(s) PyBytes_FromString((char*)s)
2766 #define __Pyx_PyBytes_AsUString(s)   ((unsigned char*) PyBytes_AsString(s))
2767
2768 #define __Pyx_PyBool_FromLong(b) ((b) ? (Py_INCREF(Py_True), Py_True) : (Py_INCREF(Py_False), Py_False))
2769 static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject*);
2770 static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x);
2771
2772 static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject*);
2773 static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t);
2774 static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject*);
2775
2776 #define __pyx_PyFloat_AsDouble(x) (PyFloat_CheckExact(x) ? PyFloat_AS_DOUBLE(x) : PyFloat_AsDouble(x))
2777
2778 """ + type_conversion_predeclarations
2779
2780 # Note: __Pyx_PyObject_IsTrue is written to minimize branching.
2781 type_conversion_functions = """
2782 /* Type Conversion Functions */
2783
2784 static CYTHON_INLINE int __Pyx_PyObject_IsTrue(PyObject* x) {
2785    int is_true = x == Py_True;
2786    if (is_true | (x == Py_False) | (x == Py_None)) return is_true;
2787    else return PyObject_IsTrue(x);
2788 }
2789
2790 static CYTHON_INLINE PyObject* __Pyx_PyNumber_Int(PyObject* x) {
2791   PyNumberMethods *m;
2792   const char *name = NULL;
2793   PyObject *res = NULL;
2794 #if PY_VERSION_HEX < 0x03000000
2795   if (PyInt_Check(x) || PyLong_Check(x))
2796 #else
2797   if (PyLong_Check(x))
2798 #endif
2799     return Py_INCREF(x), x;
2800   m = Py_TYPE(x)->tp_as_number;
2801 #if PY_VERSION_HEX < 0x03000000
2802   if (m && m->nb_int) {
2803     name = "int";
2804     res = PyNumber_Int(x);
2805   }
2806   else if (m && m->nb_long) {
2807     name = "long";
2808     res = PyNumber_Long(x);
2809   }
2810 #else
2811   if (m && m->nb_int) {
2812     name = "int";
2813     res = PyNumber_Long(x);
2814   }
2815 #endif
2816   if (res) {
2817 #if PY_VERSION_HEX < 0x03000000
2818     if (!PyInt_Check(res) && !PyLong_Check(res)) {
2819 #else
2820     if (!PyLong_Check(res)) {
2821 #endif
2822       PyErr_Format(PyExc_TypeError,
2823                    "__%s__ returned non-%s (type %.200s)",
2824                    name, name, Py_TYPE(res)->tp_name);
2825       Py_DECREF(res);
2826       return NULL;
2827     }
2828   }
2829   else if (!PyErr_Occurred()) {
2830     PyErr_SetString(PyExc_TypeError,
2831                     "an integer is required");
2832   }
2833   return res;
2834 }
2835
2836 static CYTHON_INLINE Py_ssize_t __Pyx_PyIndex_AsSsize_t(PyObject* b) {
2837   Py_ssize_t ival;
2838   PyObject* x = PyNumber_Index(b);
2839   if (!x) return -1;
2840   ival = PyInt_AsSsize_t(x);
2841   Py_DECREF(x);
2842   return ival;
2843 }
2844
2845 static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t ival) {
2846 #if PY_VERSION_HEX < 0x02050000
2847    if (ival <= LONG_MAX)
2848        return PyInt_FromLong((long)ival);
2849    else {
2850        unsigned char *bytes = (unsigned char *) &ival;
2851        int one = 1; int little = (int)*(unsigned char*)&one;
2852        return _PyLong_FromByteArray(bytes, sizeof(size_t), little, 0);
2853    }
2854 #else
2855    return PyInt_FromSize_t(ival);
2856 #endif
2857 }
2858
2859 static CYTHON_INLINE size_t __Pyx_PyInt_AsSize_t(PyObject* x) {
2860    unsigned PY_LONG_LONG val = __Pyx_PyInt_AsUnsignedLongLong(x);
2861    if (unlikely(val == (unsigned PY_LONG_LONG)-1 && PyErr_Occurred())) {
2862        return (size_t)-1;
2863    } else if (unlikely(val != (unsigned PY_LONG_LONG)(size_t)val)) {
2864        PyErr_SetString(PyExc_OverflowError,
2865                        "value too large to convert to size_t");
2866        return (size_t)-1;
2867    }
2868    return (size_t)val;
2869 }
2870
2871 """ + type_conversion_functions
2872