Cython/Compiler/Optimize.py

   1
   2 import cython
   3 from cython import set
   4 cython.declare(UtilityCode=object, EncodedString=object, BytesLiteral=object,
   5                Nodes=object, ExprNodes=object, PyrexTypes=object, Builtin=object,
   6                UtilNodes=object, Naming=object)
   7
   8 import Nodes
   9 import ExprNodes
  10 import PyrexTypes
  11 import Visitor
  12 import Builtin
  13 import UtilNodes
  14 import TypeSlots
  15 import Symtab
  16 import Options
  17 import Naming
  18
  19 from Code import UtilityCode
  20 from StringEncoding import EncodedString, BytesLiteral
  21 from Errors import error
  22 from ParseTreeTransforms import SkipDeclarations
  23
  24 import codecs
  25
  26 try:
  27     from __builtin__ import reduce
  28 except ImportError:
  29     from functools import reduce
  30
  31 try:
  32     from __builtin__ import basestring
  33 except ImportError:
  34     basestring = str # Python 3
  35
  36 class FakePythonEnv(object):
  37     "A fake environment for creating type test nodes etc."
  38     nogil = False
  39
  40 def unwrap_coerced_node(node, coercion_nodes=(ExprNodes.CoerceToPyTypeNode, ExprNodes.CoerceFromPyTypeNode)):
  41     if isinstance(node, coercion_nodes):
  42         return node.arg
  43     return node
  44
  45 def unwrap_node(node):
  46     while isinstance(node, UtilNodes.ResultRefNode):
  47         node = node.expression
  48     return node
  49
  50 def is_common_value(a, b):
  51     a = unwrap_node(a)
  52     b = unwrap_node(b)
  53     if isinstance(a, ExprNodes.NameNode) and isinstance(b, ExprNodes.NameNode):
  54         return a.name == b.name
  55     if isinstance(a, ExprNodes.AttributeNode) and isinstance(b, ExprNodes.AttributeNode):
  56         return not a.is_py_attr and is_common_value(a.obj, b.obj) and a.attribute == b.attribute
  57     return False
  58
  59 class IterationTransform(Visitor.VisitorTransform):
  60     """Transform some common for-in loop patterns into efficient C loops:
  61
  62     - for-in-dict loop becomes a while loop calling PyDict_Next()
  63     - for-in-enumerate is replaced by an external counter variable
  64     - for-in-range loop becomes a plain C for loop
  65     """
  66     PyDict_Next_func_type = PyrexTypes.CFuncType(
  67         PyrexTypes.c_bint_type, [
  68             PyrexTypes.CFuncTypeArg("dict",  PyrexTypes.py_object_type, None),
  69             PyrexTypes.CFuncTypeArg("pos",   PyrexTypes.c_py_ssize_t_ptr_type, None),
  70             PyrexTypes.CFuncTypeArg("key",   PyrexTypes.CPtrType(PyrexTypes.py_object_type), None),
  71             PyrexTypes.CFuncTypeArg("value", PyrexTypes.CPtrType(PyrexTypes.py_object_type), None)
  72             ])
  73
  74     PyDict_Next_name = EncodedString("PyDict_Next")
  75
  76     PyDict_Next_entry = Symtab.Entry(
  77         PyDict_Next_name, PyDict_Next_name, PyDict_Next_func_type)
  78
  79     visit_Node = Visitor.VisitorTransform.recurse_to_children
  80
  81     def visit_ModuleNode(self, node):
  82         self.current_scope = node.scope
  83         self.module_scope = node.scope
  84         self.visitchildren(node)
  85         return node
  86
  87     def visit_DefNode(self, node):
  88         oldscope = self.current_scope
  89         self.current_scope = node.entry.scope
  90         self.visitchildren(node)
  91         self.current_scope = oldscope
  92         return node
  93
  94     def visit_PrimaryCmpNode(self, node):
  95         if node.is_ptr_contains():
  96
  97             # for t in operand2:
  98             #     if operand1 == t:
  99             #         res = True
 100             #         break
 101             # else:
 102             #     res = False
 103
 104             pos = node.pos
 105             res_handle = UtilNodes.TempHandle(PyrexTypes.c_bint_type)
 106             res = res_handle.ref(pos)
 107             result_ref = UtilNodes.ResultRefNode(node)
 108             if isinstance(node.operand2, ExprNodes.IndexNode):
 109                 base_type = node.operand2.base.type.base_type
 110             else:
 111                 base_type = node.operand2.type.base_type
 112             target_handle = UtilNodes.TempHandle(base_type)
 113             target = target_handle.ref(pos)
 114             cmp_node = ExprNodes.PrimaryCmpNode(
 115                 pos, operator=u'==', operand1=node.operand1, operand2=target)
 116             if_body = Nodes.StatListNode(
 117                 pos,
 118                 stats = [Nodes.SingleAssignmentNode(pos, lhs=result_ref, rhs=ExprNodes.BoolNode(pos, value=1)),
 119                          Nodes.BreakStatNode(pos)])
 120             if_node = Nodes.IfStatNode(
 121                 pos,
 122                 if_clauses=[Nodes.IfClauseNode(pos, condition=cmp_node, body=if_body)],
 123                 else_clause=None)
 124             for_loop = UtilNodes.TempsBlockNode(
 125                 pos,
 126                 temps = [target_handle],
 127                 body = Nodes.ForInStatNode(
 128                     pos,
 129                     target=target,
 130                     iterator=ExprNodes.IteratorNode(node.operand2.pos, sequence=node.operand2),
 131                     body=if_node,
 132                     else_clause=Nodes.SingleAssignmentNode(pos, lhs=result_ref, rhs=ExprNodes.BoolNode(pos, value=0))))
 133             for_loop.analyse_expressions(self.current_scope)
 134             for_loop = self(for_loop)
 135             new_node = UtilNodes.TempResultFromStatNode(result_ref, for_loop)
 136
 137             if node.operator == 'not_in':
 138                 new_node = ExprNodes.NotNode(pos, operand=new_node)
 139             return new_node
 140
 141         else:
 142             self.visitchildren(node)
 143             return node
 144
 145     def visit_ForInStatNode(self, node):
 146         self.visitchildren(node)
 147         return self._optimise_for_loop(node)
 148
 149     def _optimise_for_loop(self, node):
 150         iterator = node.iterator.sequence
 151         if iterator.type is Builtin.dict_type:
 152             # like iterating over dict.keys()
 153             return self._transform_dict_iteration(
 154                 node, dict_obj=iterator, keys=True, values=False)
 155
 156         # C array (slice) iteration?
 157         if False:
 158             plain_iterator = unwrap_coerced_node(iterator)
 159             if isinstance(plain_iterator, ExprNodes.SliceIndexNode) and \
 160                    (plain_iterator.base.type.is_array or plain_iterator.base.type.is_ptr):
 161                 return self._transform_carray_iteration(node, plain_iterator)
 162
 163         if iterator.type.is_ptr or iterator.type.is_array:
 164             return self._transform_carray_iteration(node, iterator)
 165         if iterator.type in (Builtin.bytes_type, Builtin.unicode_type):
 166             return self._transform_string_iteration(node, iterator)
 167
 168         # the rest is based on function calls
 169         if not isinstance(iterator, ExprNodes.SimpleCallNode):
 170             return node
 171
 172         function = iterator.function
 173         # dict iteration?
 174         if isinstance(function, ExprNodes.AttributeNode) and \
 175                 function.obj.type == Builtin.dict_type:
 176             dict_obj = function.obj
 177             method = function.attribute
 178
 179             is_py3 = self.module_scope.context.language_level >= 3
 180             keys = values = False
 181             if method == 'iterkeys' or (is_py3 and method == 'keys'):
 182                 keys = True
 183             elif method == 'itervalues' or (is_py3 and method == 'values'):
 184                 values = True
 185             elif method == 'iteritems' or (is_py3 and method == 'items'):
 186                 keys = values = True
 187             else:
 188                 return node
 189             return self._transform_dict_iteration(
 190                 node, dict_obj, keys, values)
 191
 192         # enumerate() ?
 193         if iterator.self is None and function.is_name and \
 194                function.entry and function.entry.is_builtin and \
 195                function.name == 'enumerate':
 196             return self._transform_enumerate_iteration(node, iterator)
 197
 198         # range() iteration?
 199         if Options.convert_range and node.target.type.is_int:
 200             if iterator.self is None and function.is_name and \
 201                    function.entry and function.entry.is_builtin and \
 202                    function.name in ('range', 'xrange'):
 203                 return self._transform_range_iteration(node, iterator)
 204
 205         return node
 206
 207     PyUnicode_AS_UNICODE_func_type = PyrexTypes.CFuncType(
 208         PyrexTypes.c_py_unicode_ptr_type, [
 209             PyrexTypes.CFuncTypeArg("s", Builtin.unicode_type, None)
 210             ])
 211
 212     PyUnicode_GET_SIZE_func_type = PyrexTypes.CFuncType(
 213         PyrexTypes.c_py_ssize_t_type, [
 214             PyrexTypes.CFuncTypeArg("s", Builtin.unicode_type, None)
 215             ])
 216
 217     PyBytes_AS_STRING_func_type = PyrexTypes.CFuncType(
 218         PyrexTypes.c_char_ptr_type, [
 219             PyrexTypes.CFuncTypeArg("s", Builtin.bytes_type, None)
 220             ])
 221
 222     PyBytes_GET_SIZE_func_type = PyrexTypes.CFuncType(
 223         PyrexTypes.c_py_ssize_t_type, [
 224             PyrexTypes.CFuncTypeArg("s", Builtin.bytes_type, None)
 225             ])
 226
 227     def _transform_string_iteration(self, node, slice_node):
 228         if not node.target.type.is_int:
 229             return self._transform_carray_iteration(node, slice_node)
 230         if slice_node.type is Builtin.unicode_type:
 231             unpack_func = "PyUnicode_AS_UNICODE"
 232             len_func = "PyUnicode_GET_SIZE"
 233             unpack_func_type = self.PyUnicode_AS_UNICODE_func_type
 234             len_func_type = self.PyUnicode_GET_SIZE_func_type
 235         elif slice_node.type is Builtin.bytes_type:
 236             unpack_func = "PyBytes_AS_STRING"
 237             unpack_func_type = self.PyBytes_AS_STRING_func_type
 238             len_func = "PyBytes_GET_SIZE"
 239             len_func_type = self.PyBytes_GET_SIZE_func_type
 240         else:
 241             return node
 242
 243         unpack_temp_node = UtilNodes.LetRefNode(
 244             slice_node.as_none_safe_node("'NoneType' is not iterable"))
 245
 246         slice_base_node = ExprNodes.PythonCapiCallNode(
 247             slice_node.pos, unpack_func, unpack_func_type,
 248             args = [unpack_temp_node],
 249             is_temp = 0,
 250             )
 251         len_node = ExprNodes.PythonCapiCallNode(
 252             slice_node.pos, len_func, len_func_type,
 253             args = [unpack_temp_node],
 254             is_temp = 0,
 255             )
 256
 257         return UtilNodes.LetNode(
 258             unpack_temp_node,
 259             self._transform_carray_iteration(
 260                 node,
 261                 ExprNodes.SliceIndexNode(
 262                     slice_node.pos,
 263                     base = slice_base_node,
 264                     start = None,
 265                     step = None,
 266                     stop = len_node,
 267                     type = slice_base_node.type,
 268                     is_temp = 1,
 269                     )))
 270
 271     def _transform_carray_iteration(self, node, slice_node):
 272         neg_step = False
 273         if isinstance(slice_node, ExprNodes.SliceIndexNode):
 274             slice_base = slice_node.base
 275             start = slice_node.start
 276             stop = slice_node.stop
 277             step = None
 278             if not stop:
 279                 if not slice_base.type.is_pyobject:
 280                     error(slice_node.pos, "C array iteration requires known end index")
 281                 return node
 282         elif isinstance(slice_node, ExprNodes.IndexNode):
 283             # slice_node.index must be a SliceNode
 284             slice_base = slice_node.base
 285             index = slice_node.index
 286             start = index.start
 287             stop = index.stop
 288             step = index.step
 289             if step:
 290                 if step.constant_result is None:
 291                     step = None
 292                 elif not isinstance(step.constant_result, (int,long)) \
 293                        or step.constant_result == 0 \
 294                        or step.constant_result > 0 and not stop \
 295                        or step.constant_result < 0 and not start:
 296                     if not slice_base.type.is_pyobject:
 297                         error(step.pos, "C array iteration requires known step size and end index")
 298                     return node
 299                 else:
 300                     # step sign is handled internally by ForFromStatNode
 301                     neg_step = step.constant_result < 0
 302                     step = ExprNodes.IntNode(step.pos, type=PyrexTypes.c_py_ssize_t_type,
 303                                              value=abs(step.constant_result),
 304                                              constant_result=abs(step.constant_result))
 305         elif slice_node.type.is_array:
 306             if slice_node.type.size is None:
 307                 error(step.pos, "C array iteration requires known end index")
 308                 return node
 309             slice_base = slice_node
 310             start = None
 311             stop = ExprNodes.IntNode(
 312                 slice_node.pos, value=str(slice_node.type.size),
 313                 type=PyrexTypes.c_py_ssize_t_type, constant_result=slice_node.type.size)
 314             step = None
 315
 316         else:
 317             if not slice_node.type.is_pyobject:
 318                 error(slice_node.pos, "C array iteration requires known end index")
 319             return node
 320
 321         if start:
 322             if start.constant_result is None:
 323                 start = None
 324             else:
 325                 start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_scope)
 326         if stop:
 327             if stop.constant_result is None:
 328                 stop = None
 329             else:
 330                 stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_scope)
 331         if stop is None:
 332             if neg_step:
 333                 stop = ExprNodes.IntNode(
 334                     slice_node.pos, value='-1', type=PyrexTypes.c_py_ssize_t_type, constant_result=-1)
 335             else:
 336                 error(slice_node.pos, "C array iteration requires known step size and end index")
 337                 return node
 338
 339         ptr_type = slice_base.type
 340         if ptr_type.is_array:
 341             ptr_type = ptr_type.element_ptr_type()
 342         carray_ptr = slice_base.coerce_to_simple(self.current_scope)
 343
 344         if start and start.constant_result != 0:
 345             start_ptr_node = ExprNodes.AddNode(
 346                 start.pos,
 347                 operand1=carray_ptr,
 348                 operator='+',
 349                 operand2=start,
 350                 type=ptr_type)
 351         else:
 352             start_ptr_node = carray_ptr
 353
 354         stop_ptr_node = ExprNodes.AddNode(
 355             stop.pos,
 356             operand1=ExprNodes.CloneNode(carray_ptr),
 357             operator='+',
 358             operand2=stop,
 359             type=ptr_type
 360             ).coerce_to_simple(self.current_scope)
 361
 362         counter = UtilNodes.TempHandle(ptr_type)
 363         counter_temp = counter.ref(node.target.pos)
 364
 365         if slice_base.type.is_string and node.target.type.is_pyobject:
 366             # special case: char* -> bytes
 367             target_value = ExprNodes.SliceIndexNode(
 368                 node.target.pos,
 369                 start=ExprNodes.IntNode(node.target.pos, value='0',
 370                                         constant_result=0,
 371                                         type=PyrexTypes.c_int_type),
 372                 stop=ExprNodes.IntNode(node.target.pos, value='1',
 373                                        constant_result=1,
 374                                        type=PyrexTypes.c_int_type),
 375                 base=counter_temp,
 376                 type=Builtin.bytes_type,
 377                 is_temp=1)
 378         elif node.target.type.is_ptr and not node.target.type.assignable_from(ptr_type.base_type):
 379             # Allow iteration with pointer target to avoid copy.
 380             target_value = counter_temp
 381         else:
 382             target_value = ExprNodes.IndexNode(
 383                 node.target.pos,
 384                 index=ExprNodes.IntNode(node.target.pos, value='0',
 385                                         constant_result=0,
 386                                         type=PyrexTypes.c_int_type),
 387                 base=counter_temp,
 388                 is_buffer_access=False,
 389                 type=ptr_type.base_type)
 390
 391         if target_value.type != node.target.type:
 392             target_value = target_value.coerce_to(node.target.type,
 393                                                   self.current_scope)
 394
 395         target_assign = Nodes.SingleAssignmentNode(
 396             pos = node.target.pos,
 397             lhs = node.target,
 398             rhs = target_value)
 399
 400         body = Nodes.StatListNode(
 401             node.pos,
 402             stats = [target_assign, node.body])
 403
 404         for_node = Nodes.ForFromStatNode(
 405             node.pos,
 406             bound1=start_ptr_node, relation1=neg_step and '>=' or '<=',
 407             target=counter_temp,
 408             relation2=neg_step and '>' or '<', bound2=stop_ptr_node,
 409             step=step, body=body,
 410             else_clause=node.else_clause,
 411             from_range=True)
 412
 413         return UtilNodes.TempsBlockNode(
 414             node.pos, temps=[counter],
 415             body=for_node)
 416
 417     def _transform_enumerate_iteration(self, node, enumerate_function):
 418         args = enumerate_function.arg_tuple.args
 419         if len(args) == 0:
 420             error(enumerate_function.pos,
 421                   "enumerate() requires an iterable argument")
 422             return node
 423         elif len(args) > 1:
 424             error(enumerate_function.pos,
 425                   "enumerate() takes at most 1 argument")
 426             return node
 427
 428         if not node.target.is_sequence_constructor:
 429             # leave this untouched for now
 430             return node
 431         targets = node.target.args
 432         if len(targets) != 2:
 433             # leave this untouched for now
 434             return node
 435         if not isinstance(targets[0], ExprNodes.NameNode):
 436             # leave this untouched for now
 437             return node
 438
 439         enumerate_target, iterable_target = targets
 440         counter_type = enumerate_target.type
 441
 442         if not counter_type.is_pyobject and not counter_type.is_int:
 443             # nothing we can do here, I guess
 444             return node
 445
 446         temp = UtilNodes.LetRefNode(ExprNodes.IntNode(enumerate_function.pos,
 447                                                       value='0',
 448                                                       type=counter_type,
 449                                                       constant_result=0))
 450         inc_expression = ExprNodes.AddNode(
 451             enumerate_function.pos,
 452             operand1 = temp,
 453             operand2 = ExprNodes.IntNode(node.pos, value='1',
 454                                          type=counter_type,
 455                                          constant_result=1),
 456             operator = '+',
 457             type = counter_type,
 458             is_temp = counter_type.is_pyobject
 459             )
 460
 461         loop_body = [
 462             Nodes.SingleAssignmentNode(
 463                 pos = enumerate_target.pos,
 464                 lhs = enumerate_target,
 465                 rhs = temp),
 466             Nodes.SingleAssignmentNode(
 467                 pos = enumerate_target.pos,
 468                 lhs = temp,
 469                 rhs = inc_expression)
 470             ]
 471
 472         if isinstance(node.body, Nodes.StatListNode):
 473             node.body.stats = loop_body + node.body.stats
 474         else:
 475             loop_body.append(node.body)
 476             node.body = Nodes.StatListNode(
 477                 node.body.pos,
 478                 stats = loop_body)
 479
 480         node.target = iterable_target
 481         node.item = node.item.coerce_to(iterable_target.type, self.current_scope)
 482         node.iterator.sequence = enumerate_function.arg_tuple.args[0]
 483
 484         # recurse into loop to check for further optimisations
 485         return UtilNodes.LetNode(temp, self._optimise_for_loop(node))
 486
 487     def _transform_range_iteration(self, node, range_function):
 488         args = range_function.arg_tuple.args
 489         if len(args) < 3:
 490             step_pos = range_function.pos
 491             step_value = 1
 492             step = ExprNodes.IntNode(step_pos, value='1',
 493                                      constant_result=1)
 494         else:
 495             step = args[2]
 496             step_pos = step.pos
 497             if not isinstance(step.constant_result, (int, long)):
 498                 # cannot determine step direction
 499                 return node
 500             step_value = step.constant_result
 501             if step_value == 0:
 502                 # will lead to an error elsewhere
 503                 return node
 504             if not isinstance(step, ExprNodes.IntNode):
 505                 step = ExprNodes.IntNode(step_pos, value=str(step_value),
 506                                          constant_result=step_value)
 507
 508         if step_value < 0:
 509             step.value = str(-step_value)
 510             relation1 = '>='
 511             relation2 = '>'
 512         else:
 513             relation1 = '<='
 514             relation2 = '<'
 515
 516         if len(args) == 1:
 517             bound1 = ExprNodes.IntNode(range_function.pos, value='0',
 518                                        constant_result=0)
 519             bound2 = args[0].coerce_to_integer(self.current_scope)
 520         else:
 521             bound1 = args[0].coerce_to_integer(self.current_scope)
 522             bound2 = args[1].coerce_to_integer(self.current_scope)
 523         step = step.coerce_to_integer(self.current_scope)
 524
 525         if not bound2.is_literal:
 526             # stop bound must be immutable => keep it in a temp var
 527             bound2_is_temp = True
 528             bound2 = UtilNodes.LetRefNode(bound2)
 529         else:
 530             bound2_is_temp = False
 531
 532         for_node = Nodes.ForFromStatNode(
 533             node.pos,
 534             target=node.target,
 535             bound1=bound1, relation1=relation1,
 536             relation2=relation2, bound2=bound2,
 537             step=step, body=node.body,
 538             else_clause=node.else_clause,
 539             from_range=True)
 540
 541         if bound2_is_temp:
 542             for_node = UtilNodes.LetNode(bound2, for_node)
 543
 544         return for_node
 545
 546     def _transform_dict_iteration(self, node, dict_obj, keys, values):
 547         py_object_ptr = PyrexTypes.c_void_ptr_type
 548
 549         temps = []
 550         temp = UtilNodes.TempHandle(PyrexTypes.py_object_type)
 551         temps.append(temp)
 552         dict_temp = temp.ref(dict_obj.pos)
 553         temp = UtilNodes.TempHandle(PyrexTypes.c_py_ssize_t_type)
 554         temps.append(temp)
 555         pos_temp = temp.ref(node.pos)
 556         pos_temp_addr = ExprNodes.AmpersandNode(
 557             node.pos, operand=pos_temp,
 558             type=PyrexTypes.c_ptr_type(PyrexTypes.c_py_ssize_t_type))
 559         if keys:
 560             temp = UtilNodes.TempHandle(py_object_ptr)
 561             temps.append(temp)
 562             key_temp = temp.ref(node.target.pos)
 563             key_temp_addr = ExprNodes.AmpersandNode(
 564                 node.target.pos, operand=key_temp,
 565                 type=PyrexTypes.c_ptr_type(py_object_ptr))
 566         else:
 567             key_temp_addr = key_temp = ExprNodes.NullNode(
 568                 pos=node.target.pos)
 569         if values:
 570             temp = UtilNodes.TempHandle(py_object_ptr)
 571             temps.append(temp)
 572             value_temp = temp.ref(node.target.pos)
 573             value_temp_addr = ExprNodes.AmpersandNode(
 574                 node.target.pos, operand=value_temp,
 575                 type=PyrexTypes.c_ptr_type(py_object_ptr))
 576         else:
 577             value_temp_addr = value_temp = ExprNodes.NullNode(
 578                 pos=node.target.pos)
 579
 580         key_target = value_target = node.target
 581         tuple_target = None
 582         if keys and values:
 583             if node.target.is_sequence_constructor:
 584                 if len(node.target.args) == 2:
 585                     key_target, value_target = node.target.args
 586                 else:
 587                     # unusual case that may or may not lead to an error
 588                     return node
 589             else:
 590                 tuple_target = node.target
 591
 592         def coerce_object_to(obj_node, dest_type):
 593             if dest_type.is_pyobject:
 594                 if dest_type != obj_node.type:
 595                     if dest_type.is_extension_type or dest_type.is_builtin_type:
 596                         obj_node = ExprNodes.PyTypeTestNode(
 597                             obj_node, dest_type, self.current_scope, notnone=True)
 598                 result = ExprNodes.TypecastNode(
 599                     obj_node.pos,
 600                     operand = obj_node,
 601                     type = dest_type)
 602                 return (result, None)
 603             else:
 604                 temp = UtilNodes.TempHandle(dest_type)
 605                 temps.append(temp)
 606                 temp_result = temp.ref(obj_node.pos)
 607                 class CoercedTempNode(ExprNodes.CoerceFromPyTypeNode):
 608                     def result(self):
 609                         return temp_result.result()
 610                     def generate_execution_code(self, code):
 611                         self.generate_result_code(code)
 612                 return (temp_result, CoercedTempNode(dest_type, obj_node, self.current_scope))
 613
 614         if isinstance(node.body, Nodes.StatListNode):
 615             body = node.body
 616         else:
 617             body = Nodes.StatListNode(pos = node.body.pos,
 618                                       stats = [node.body])
 619
 620         if tuple_target:
 621             tuple_result = ExprNodes.TupleNode(
 622                 pos = tuple_target.pos,
 623                 args = [key_temp, value_temp],
 624                 is_temp = 1,
 625                 type = Builtin.tuple_type,
 626                 )
 627             body.stats.insert(
 628                 0, Nodes.SingleAssignmentNode(
 629                     pos = tuple_target.pos,
 630                     lhs = tuple_target,
 631                     rhs = tuple_result))
 632         else:
 633             # execute all coercions before the assignments
 634             coercion_stats = []
 635             assign_stats = []
 636             if keys:
 637                 temp_result, coercion = coerce_object_to(
 638                     key_temp, key_target.type)
 639                 if coercion:
 640                     coercion_stats.append(coercion)
 641                 assign_stats.append(
 642                     Nodes.SingleAssignmentNode(
 643                         pos = key_temp.pos,
 644                         lhs = key_target,
 645                         rhs = temp_result))
 646             if values:
 647                 temp_result, coercion = coerce_object_to(
 648                     value_temp, value_target.type)
 649                 if coercion:
 650                     coercion_stats.append(coercion)
 651                 assign_stats.append(
 652                     Nodes.SingleAssignmentNode(
 653                         pos = value_temp.pos,
 654                         lhs = value_target,
 655                         rhs = temp_result))
 656             body.stats[0:0] = coercion_stats + assign_stats
 657
 658         result_code = [
 659             Nodes.SingleAssignmentNode(
 660                 pos = dict_obj.pos,
 661                 lhs = dict_temp,
 662                 rhs = dict_obj),
 663             Nodes.SingleAssignmentNode(
 664                 pos = node.pos,
 665                 lhs = pos_temp,
 666                 rhs = ExprNodes.IntNode(node.pos, value='0',
 667                                         constant_result=0)),
 668             Nodes.WhileStatNode(
 669                 pos = node.pos,
 670                 condition = ExprNodes.SimpleCallNode(
 671                     pos = dict_obj.pos,
 672                     type = PyrexTypes.c_bint_type,
 673                     function = ExprNodes.NameNode(
 674                         pos = dict_obj.pos,
 675                         name = self.PyDict_Next_name,
 676                         type = self.PyDict_Next_func_type,
 677                         entry = self.PyDict_Next_entry),
 678                     args = [dict_temp, pos_temp_addr,
 679                             key_temp_addr, value_temp_addr]
 680                     ),
 681                 body = body,
 682                 else_clause = node.else_clause
 683                 )
 684             ]
 685
 686         return UtilNodes.TempsBlockNode(
 687             node.pos, temps=temps,
 688             body=Nodes.StatListNode(
 689                 node.pos,
 690                 stats = result_code
 691                 ))
 692
 693
 694 class SwitchTransform(Visitor.VisitorTransform):
 695     """
 696     This transformation tries to turn long if statements into C switch statements.
 697     The requirement is that every clause be an (or of) var == value, where the var
 698     is common among all clauses and both var and value are ints.
 699     """
 700     NO_MATCH = (None, None, None)
 701
 702     def extract_conditions(self, cond, allow_not_in):
 703         while True:
 704             if isinstance(cond, ExprNodes.CoerceToTempNode):
 705                 cond = cond.arg
 706             elif isinstance(cond, UtilNodes.EvalWithTempExprNode):
 707                 # this is what we get from the FlattenInListTransform
 708                 cond = cond.subexpression
 709             elif isinstance(cond, ExprNodes.TypecastNode):
 710                 cond = cond.operand
 711             else:
 712                 break
 713
 714         if isinstance(cond, ExprNodes.PrimaryCmpNode):
 715             if cond.cascade is not None:
 716                 return self.NO_MATCH
 717             elif cond.is_c_string_contains() and \
 718                    isinstance(cond.operand2, (ExprNodes.UnicodeNode, ExprNodes.BytesNode)):
 719                 not_in = cond.operator == 'not_in'
 720                 if not_in and not allow_not_in:
 721                     return self.NO_MATCH
 722                 if isinstance(cond.operand2, ExprNodes.UnicodeNode) and \
 723                        cond.operand2.contains_surrogates():
 724                     # dealing with surrogates leads to different
 725                     # behaviour on wide and narrow Unicode
 726                     # platforms => refuse to optimise this case
 727                     return self.NO_MATCH
 728                 return not_in, cond.operand1, self.extract_in_string_conditions(cond.operand2)
 729             elif not cond.is_python_comparison():
 730                 if cond.operator == '==':
 731                     not_in = False
 732                 elif allow_not_in and cond.operator == '!=':
 733                     not_in = True
 734                 else:
 735                     return self.NO_MATCH
 736                 # this looks somewhat silly, but it does the right
 737                 # checks for NameNode and AttributeNode
 738                 if is_common_value(cond.operand1, cond.operand1):
 739                     if cond.operand2.is_literal:
 740                         return not_in, cond.operand1, [cond.operand2]
 741                     elif getattr(cond.operand2, 'entry', None) \
 742                              and cond.operand2.entry.is_const:
 743                         return not_in, cond.operand1, [cond.operand2]
 744                 if is_common_value(cond.operand2, cond.operand2):
 745                     if cond.operand1.is_literal:
 746                         return not_in, cond.operand2, [cond.operand1]
 747                     elif getattr(cond.operand1, 'entry', None) \
 748                              and cond.operand1.entry.is_const:
 749                         return not_in, cond.operand2, [cond.operand1]
 750         elif isinstance(cond, ExprNodes.BoolBinopNode):
 751             if cond.operator == 'or' or (allow_not_in and cond.operator == 'and'):
 752                 allow_not_in = (cond.operator == 'and')
 753                 not_in_1, t1, c1 = self.extract_conditions(cond.operand1, allow_not_in)
 754                 not_in_2, t2, c2 = self.extract_conditions(cond.operand2, allow_not_in)
 755                 if t1 is not None and not_in_1 == not_in_2 and is_common_value(t1, t2):
 756                     if (not not_in_1) or allow_not_in:
 757                         return not_in_1, t1, c1+c2
 758         return self.NO_MATCH
 759
 760     def extract_in_string_conditions(self, string_literal):
 761         if isinstance(string_literal, ExprNodes.UnicodeNode):
 762             charvals = list(map(ord, set(string_literal.value)))
 763             charvals.sort()
 764             return [ ExprNodes.IntNode(string_literal.pos, value=str(charval),
 765                                        constant_result=charval)
 766                      for charval in charvals ]
 767         else:
 768             # this is a bit tricky as Py3's bytes type returns
 769             # integers on iteration, whereas Py2 returns 1-char byte
 770             # strings
 771             characters = string_literal.value
 772             characters = list(set([ characters[i:i+1] for i in range(len(characters)) ]))
 773             characters.sort()
 774             return [ ExprNodes.CharNode(string_literal.pos, value=charval,
 775                                         constant_result=charval)
 776                      for charval in characters ]
 777
 778     def extract_common_conditions(self, common_var, condition, allow_not_in):
 779         not_in, var, conditions = self.extract_conditions(condition, allow_not_in)
 780         if var is None:
 781             return self.NO_MATCH
 782         elif common_var is not None and not is_common_value(var, common_var):
 783             return self.NO_MATCH
 784         elif not var.type.is_int or sum([not cond.type.is_int for cond in conditions]):
 785             return self.NO_MATCH
 786         return not_in, var, conditions
 787
 788     def has_duplicate_values(self, condition_values):
 789         # duplicated values don't work in a switch statement
 790         seen = set()
 791         for value in condition_values:
 792             if value.constant_result is not ExprNodes.not_a_constant:
 793                 if value.constant_result in seen:
 794                     return True
 795                 seen.add(value.constant_result)
 796             else:
 797                 # this isn't completely safe as we don't know the
 798                 # final C value, but this is about the best we can do
 799                 seen.add(getattr(getattr(value, 'entry', None), 'cname'))
 800         return False
 801
 802     def visit_IfStatNode(self, node):
 803         common_var = None
 804         cases = []
 805         for if_clause in node.if_clauses:
 806             _, common_var, conditions = self.extract_common_conditions(
 807                 common_var, if_clause.condition, False)
 808             if common_var is None:
 809                 self.visitchildren(node)
 810                 return node
 811             cases.append(Nodes.SwitchCaseNode(pos = if_clause.pos,
 812                                               conditions = conditions,
 813                                               body = if_clause.body))
 814
 815         if sum([ len(case.conditions) for case in cases ]) < 2:
 816             self.visitchildren(node)
 817             return node
 818         if self.has_duplicate_values(sum([case.conditions for case in cases], [])):
 819             self.visitchildren(node)
 820             return node
 821
 822         common_var = unwrap_node(common_var)
 823         switch_node = Nodes.SwitchStatNode(pos = node.pos,
 824                                            test = common_var,
 825                                            cases = cases,
 826                                            else_clause = node.else_clause)
 827         return switch_node
 828
 829     def visit_CondExprNode(self, node):
 830         not_in, common_var, conditions = self.extract_common_conditions(
 831             None, node.test, True)
 832         if common_var is None \
 833                or len(conditions) < 2 \
 834                or self.has_duplicate_values(conditions):
 835             self.visitchildren(node)
 836             return node
 837         return self.build_simple_switch_statement(
 838             node, common_var, conditions, not_in,
 839             node.true_val, node.false_val)
 840
 841     def visit_BoolBinopNode(self, node):
 842         not_in, common_var, conditions = self.extract_common_conditions(
 843             None, node, True)
 844         if common_var is None \
 845                or len(conditions) < 2 \
 846                or self.has_duplicate_values(conditions):
 847             self.visitchildren(node)
 848             return node
 849
 850         return self.build_simple_switch_statement(
 851             node, common_var, conditions, not_in,
 852             ExprNodes.BoolNode(node.pos, value=True, constant_result=True),
 853             ExprNodes.BoolNode(node.pos, value=False, constant_result=False))
 854
 855     def visit_PrimaryCmpNode(self, node):
 856         not_in, common_var, conditions = self.extract_common_conditions(
 857             None, node, True)
 858         if common_var is None \
 859                or len(conditions) < 2 \
 860                or self.has_duplicate_values(conditions):
 861             self.visitchildren(node)
 862             return node
 863
 864         return self.build_simple_switch_statement(
 865             node, common_var, conditions, not_in,
 866             ExprNodes.BoolNode(node.pos, value=True, constant_result=True),
 867             ExprNodes.BoolNode(node.pos, value=False, constant_result=False))
 868
 869     def build_simple_switch_statement(self, node, common_var, conditions,
 870                                       not_in, true_val, false_val):
 871         result_ref = UtilNodes.ResultRefNode(node)
 872         true_body = Nodes.SingleAssignmentNode(
 873             node.pos,
 874             lhs = result_ref,
 875             rhs = true_val,
 876             first = True)
 877         false_body = Nodes.SingleAssignmentNode(
 878             node.pos,
 879             lhs = result_ref,
 880             rhs = false_val,
 881             first = True)
 882
 883         if not_in:
 884             true_body, false_body = false_body, true_body
 885
 886         cases = [Nodes.SwitchCaseNode(pos = node.pos,
 887                                       conditions = conditions,
 888                                       body = true_body)]
 889
 890         common_var = unwrap_node(common_var)
 891         switch_node = Nodes.SwitchStatNode(pos = node.pos,
 892                                            test = common_var,
 893                                            cases = cases,
 894                                            else_clause = false_body)
 895         return UtilNodes.TempResultFromStatNode(result_ref, switch_node)
 896
 897     visit_Node = Visitor.VisitorTransform.recurse_to_children
 898
 899
 900 class FlattenInListTransform(Visitor.VisitorTransform, SkipDeclarations):
 901     """
 902     This transformation flattens "x in [val1, ..., valn]" into a sequential list
 903     of comparisons.
 904     """
 905
 906     def visit_PrimaryCmpNode(self, node):
 907         self.visitchildren(node)
 908         if node.cascade is not None:
 909             return node
 910         elif node.operator == 'in':
 911             conjunction = 'or'
 912             eq_or_neq = '=='
 913         elif node.operator == 'not_in':
 914             conjunction = 'and'
 915             eq_or_neq = '!='
 916         else:
 917             return node
 918
 919         if not isinstance(node.operand2, (ExprNodes.TupleNode,
 920                                           ExprNodes.ListNode,
 921                                           ExprNodes.SetNode)):
 922             return node
 923
 924         args = node.operand2.args
 925         if len(args) == 0:
 926             return ExprNodes.BoolNode(pos = node.pos, value = node.operator == 'not_in')
 927
 928         lhs = UtilNodes.ResultRefNode(node.operand1)
 929
 930         conds = []
 931         temps = []
 932         for arg in args:
 933             if not arg.is_simple():
 934                 # must evaluate all non-simple RHS before doing the comparisons
 935                 arg = UtilNodes.LetRefNode(arg)
 936                 temps.append(arg)
 937             cond = ExprNodes.PrimaryCmpNode(
 938                                 pos = node.pos,
 939                                 operand1 = lhs,
 940                                 operator = eq_or_neq,
 941                                 operand2 = arg,
 942                                 cascade = None)
 943             conds.append(ExprNodes.TypecastNode(
 944                                 pos = node.pos,
 945                                 operand = cond,
 946                                 type = PyrexTypes.c_bint_type))
 947         def concat(left, right):
 948             return ExprNodes.BoolBinopNode(
 949                                 pos = node.pos,
 950                                 operator = conjunction,
 951                                 operand1 = left,
 952                                 operand2 = right)
 953
 954         condition = reduce(concat, conds)
 955         new_node = UtilNodes.EvalWithTempExprNode(lhs, condition)
 956         for temp in temps[::-1]:
 957             new_node = UtilNodes.EvalWithTempExprNode(temp, new_node)
 958         return new_node
 959
 960     visit_Node = Visitor.VisitorTransform.recurse_to_children
 961
 962
 963 class DropRefcountingTransform(Visitor.VisitorTransform):
 964     """Drop ref-counting in safe places.
 965     """
 966     visit_Node = Visitor.VisitorTransform.recurse_to_children
 967
 968     def visit_ParallelAssignmentNode(self, node):
 969         """
 970         Parallel swap assignments like 'a,b = b,a' are safe.
 971         """
 972         left_names, right_names = [], []
 973         left_indices, right_indices = [], []
 974         temps = []
 975
 976         for stat in node.stats:
 977             if isinstance(stat, Nodes.SingleAssignmentNode):
 978                 if not self._extract_operand(stat.lhs, left_names,
 979                                              left_indices, temps):
 980                     return node
 981                 if not self._extract_operand(stat.rhs, right_names,
 982                                              right_indices, temps):
 983                     return node
 984             elif isinstance(stat, Nodes.CascadedAssignmentNode):
 985                 # FIXME
 986                 return node
 987             else:
 988                 return node
 989
 990         if left_names or right_names:
 991             # lhs/rhs names must be a non-redundant permutation
 992             lnames = [ path for path, n in left_names ]
 993             rnames = [ path for path, n in right_names ]
 994             if set(lnames) != set(rnames):
 995                 return node
 996             if len(set(lnames)) != len(right_names):
 997                 return node
 998
 999         if left_indices or right_indices:
1000             # base name and index of index nodes must be a
1001             # non-redundant permutation
1002             lindices = []
1003             for lhs_node in left_indices:
1004                 index_id = self._extract_index_id(lhs_node)
1005                 if not index_id:
1006                     return node
1007                 lindices.append(index_id)
1008             rindices = []
1009             for rhs_node in right_indices:
1010                 index_id = self._extract_index_id(rhs_node)
1011                 if not index_id:
1012                     return node
1013                 rindices.append(index_id)
1014
1015             if set(lindices) != set(rindices):
1016                 return node
1017             if len(set(lindices)) != len(right_indices):
1018                 return node
1019
1020             # really supporting IndexNode requires support in
1021             # __Pyx_GetItemInt(), so let's stop short for now
1022             return node
1023
1024         temp_args = [t.arg for t in temps]
1025         for temp in temps:
1026             temp.use_managed_ref = False
1027
1028         for _, name_node in left_names + right_names:
1029             if name_node not in temp_args:
1030                 name_node.use_managed_ref = False
1031
1032         for index_node in left_indices + right_indices:
1033             index_node.use_managed_ref = False
1034
1035         return node
1036
1037     def _extract_operand(self, node, names, indices, temps):
1038         node = unwrap_node(node)
1039         if not node.type.is_pyobject:
1040             return False
1041         if isinstance(node, ExprNodes.CoerceToTempNode):
1042             temps.append(node)
1043             node = node.arg
1044         name_path = []
1045         obj_node = node
1046         while isinstance(obj_node, ExprNodes.AttributeNode):
1047             if obj_node.is_py_attr:
1048                 return False
1049             name_path.append(obj_node.member)
1050             obj_node = obj_node.obj
1051         if isinstance(obj_node, ExprNodes.NameNode):
1052             name_path.append(obj_node.name)
1053             names.append( ('.'.join(name_path[::-1]), node) )
1054         elif isinstance(node, ExprNodes.IndexNode):
1055             if node.base.type != Builtin.list_type:
1056                 return False
1057             if not node.index.type.is_int:
1058                 return False
1059             if not isinstance(node.base, ExprNodes.NameNode):
1060                 return False
1061             indices.append(node)
1062         else:
1063             return False
1064         return True
1065
1066     def _extract_index_id(self, index_node):
1067         base = index_node.base
1068         index = index_node.index
1069         if isinstance(index, ExprNodes.NameNode):
1070             index_val = index.name
1071         elif isinstance(index, ExprNodes.ConstNode):
1072             # FIXME:
1073             return None
1074         else:
1075             return None
1076         return (base.name, index_val)
1077
1078
1079 class EarlyReplaceBuiltinCalls(Visitor.EnvTransform):
1080     """Optimize some common calls to builtin types *before* the type
1081     analysis phase and *after* the declarations analysis phase.
1082
1083     This transform cannot make use of any argument types, but it can
1084     restructure the tree in a way that the type analysis phase can
1085     respond to.
1086
1087     Introducing C function calls here may not be a good idea.  Move
1088     them to the OptimizeBuiltinCalls transform instead, which runs
1089     after type analyis.
1090     """
1091     # only intercept on call nodes
1092     visit_Node = Visitor.VisitorTransform.recurse_to_children
1093
1094     def visit_SimpleCallNode(self, node):
1095         self.visitchildren(node)
1096         function = node.function
1097         if not self._function_is_builtin_name(function):
1098             return node
1099         return self._dispatch_to_handler(node, function, node.args)
1100
1101     def visit_GeneralCallNode(self, node):
1102         self.visitchildren(node)
1103         function = node.function
1104         if not self._function_is_builtin_name(function):
1105             return node
1106         arg_tuple = node.positional_args
1107         if not isinstance(arg_tuple, ExprNodes.TupleNode):
1108             return node
1109         args = arg_tuple.args
1110         return self._dispatch_to_handler(
1111             node, function, args, node.keyword_args)
1112
1113     def _function_is_builtin_name(self, function):
1114         if not function.is_name:
1115             return False
1116         env = self.current_env()
1117         entry = env.lookup(function.name)
1118         if entry is not env.builtin_scope().lookup_here(function.name):
1119             return False
1120         # if entry is None, it's at least an undeclared name, so likely builtin
1121         return True
1122
1123     def _dispatch_to_handler(self, node, function, args, kwargs=None):
1124         if kwargs is None:
1125             handler_name = '_handle_simple_function_%s' % function.name
1126         else:
1127             handler_name = '_handle_general_function_%s' % function.name
1128         handle_call = getattr(self, handler_name, None)
1129         if handle_call is not None:
1130             if kwargs is None:
1131                 return handle_call(node, args)
1132             else:
1133                 return handle_call(node, args, kwargs)
1134         return node
1135
1136     def _inject_capi_function(self, node, cname, func_type, utility_code=None):
1137         node.function = ExprNodes.PythonCapiFunctionNode(
1138             node.function.pos, node.function.name, cname, func_type,
1139             utility_code = utility_code)
1140
1141     def _error_wrong_arg_count(self, function_name, node, args, expected=None):
1142         if not expected: # None or 0
1143             arg_str = ''
1144         elif isinstance(expected, basestring) or expected > 1:
1145             arg_str = '...'
1146         elif expected == 1:
1147             arg_str = 'x'
1148         else:
1149             arg_str = ''
1150         if expected is not None:
1151             expected_str = 'expected %s, ' % expected
1152         else:
1153             expected_str = ''
1154         error(node.pos, "%s(%s) called with wrong number of args, %sfound %d" % (
1155             function_name, arg_str, expected_str, len(args)))
1156
1157     # specific handlers for simple call nodes
1158
1159     def _handle_simple_function_float(self, node, pos_args):
1160         if len(pos_args) == 0:
1161             return ExprNodes.FloatNode(node.pos, value='0.0')
1162         if len(pos_args) > 1:
1163             self._error_wrong_arg_count('float', node, pos_args, 1)
1164         return node
1165
1166     class YieldNodeCollector(Visitor.TreeVisitor):
1167         def __init__(self):
1168             Visitor.TreeVisitor.__init__(self)
1169             self.yield_stat_nodes = {}
1170             self.yield_nodes = []
1171
1172         visit_Node = Visitor.TreeVisitor.visitchildren
1173         # XXX: disable inlining while it's not back supported
1174         def __visit_YieldExprNode(self, node):
1175             self.yield_nodes.append(node)
1176             self.visitchildren(node)
1177
1178         def __visit_ExprStatNode(self, node):
1179             self.visitchildren(node)
1180             if node.expr in self.yield_nodes:
1181                 self.yield_stat_nodes[node.expr] = node
1182
1183         def __visit_GeneratorExpressionNode(self, node):
1184             # enable when we support generic generator expressions
1185             #
1186             # everything below this node is out of scope
1187             pass
1188
1189     def _find_single_yield_expression(self, node):
1190         collector = self.YieldNodeCollector()
1191         collector.visitchildren(node)
1192         if len(collector.yield_nodes) != 1:
1193             return None, None
1194         yield_node = collector.yield_nodes[0]
1195         try:
1196             return (yield_node.arg, collector.yield_stat_nodes[yield_node])
1197         except KeyError:
1198             return None, None
1199
1200     def _handle_simple_function_all(self, node, pos_args):
1201         """Transform
1202
1203         _result = all(x for L in LL for x in L)
1204
1205         into
1206
1207         for L in LL:
1208             for x in L:
1209                 if not x:
1210                     _result = False
1211                     break
1212             else:
1213                 continue
1214             break
1215         else:
1216             _result = True
1217         """
1218         return self._transform_any_all(node, pos_args, False)
1219
1220     def _handle_simple_function_any(self, node, pos_args):
1221         """Transform
1222
1223         _result = any(x for L in LL for x in L)
1224
1225         into
1226
1227         for L in LL:
1228             for x in L:
1229                 if x:
1230                     _result = True
1231                     break
1232             else:
1233                 continue
1234             break
1235         else:
1236             _result = False
1237         """
1238         return self._transform_any_all(node, pos_args, True)
1239
1240     def _transform_any_all(self, node, pos_args, is_any):
1241         if len(pos_args) != 1:
1242             return node
1243         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1244             return node
1245         gen_expr_node = pos_args[0]
1246         loop_node = gen_expr_node.loop
1247         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1248         if yield_expression is None:
1249             return node
1250
1251         if is_any:
1252             condition = yield_expression
1253         else:
1254             condition = ExprNodes.NotNode(yield_expression.pos, operand = yield_expression)
1255
1256         result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.c_bint_type)
1257         test_node = Nodes.IfStatNode(
1258             yield_expression.pos,
1259             else_clause = None,
1260             if_clauses = [ Nodes.IfClauseNode(
1261                 yield_expression.pos,
1262                 condition = condition,
1263                 body = Nodes.StatListNode(
1264                     node.pos,
1265                     stats = [
1266                         Nodes.SingleAssignmentNode(
1267                             node.pos,
1268                             lhs = result_ref,
1269                             rhs = ExprNodes.BoolNode(yield_expression.pos, value = is_any,
1270                                                      constant_result = is_any)),
1271                         Nodes.BreakStatNode(node.pos)
1272                         ])) ]
1273             )
1274         loop = loop_node
1275         while isinstance(loop.body, Nodes.LoopNode):
1276             next_loop = loop.body
1277             loop.body = Nodes.StatListNode(loop.body.pos, stats = [
1278                 loop.body,
1279                 Nodes.BreakStatNode(yield_expression.pos)
1280                 ])
1281             next_loop.else_clause = Nodes.ContinueStatNode(yield_expression.pos)
1282             loop = next_loop
1283         loop_node.else_clause = Nodes.SingleAssignmentNode(
1284             node.pos,
1285             lhs = result_ref,
1286             rhs = ExprNodes.BoolNode(yield_expression.pos, value = not is_any,
1287                                      constant_result = not is_any))
1288
1289         Visitor.recursively_replace_node(loop_node, yield_stat_node, test_node)
1290
1291         return ExprNodes.InlinedGeneratorExpressionNode(
1292             gen_expr_node.pos, loop = loop_node, result_node = result_ref,
1293             expr_scope = gen_expr_node.expr_scope, orig_func = is_any and 'any' or 'all')
1294
1295     def _handle_simple_function_sorted(self, node, pos_args):
1296         """Transform sorted(genexpr) into [listcomp].sort().  CPython
1297         just reads the iterable into a list and calls .sort() on it.
1298         Expanding the iterable in a listcomp is still faster.
1299         """
1300         if len(pos_args) != 1:
1301             return node
1302         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1303             return node
1304         gen_expr_node = pos_args[0]
1305         loop_node = gen_expr_node.loop
1306         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1307         if yield_expression is None:
1308             return node
1309
1310         result_node = UtilNodes.ResultRefNode(
1311             pos = loop_node.pos, type = Builtin.list_type, may_hold_none=False)
1312
1313         target = ExprNodes.ListNode(node.pos, args = [])
1314         append_node = ExprNodes.ComprehensionAppendNode(
1315             yield_expression.pos, expr = yield_expression,
1316             target = ExprNodes.CloneNode(target))
1317
1318         Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1319
1320         listcomp_node = ExprNodes.ComprehensionNode(
1321             gen_expr_node.pos, loop = loop_node, target = target,
1322             append = append_node, type = Builtin.list_type,
1323             expr_scope = gen_expr_node.expr_scope,
1324             has_local_scope = True)
1325         listcomp_assign_node = Nodes.SingleAssignmentNode(
1326             node.pos, lhs = result_node, rhs = listcomp_node, first = True)
1327
1328         sort_method = ExprNodes.AttributeNode(
1329             node.pos, obj = result_node, attribute = EncodedString('sort'),
1330             # entry ? type ?
1331             needs_none_check = False)
1332         sort_node = Nodes.ExprStatNode(
1333             node.pos, expr = ExprNodes.SimpleCallNode(
1334                 node.pos, function = sort_method, args = []))
1335
1336         sort_node.analyse_declarations(self.current_env())
1337
1338         return UtilNodes.TempResultFromStatNode(
1339             result_node,
1340             Nodes.StatListNode(node.pos, stats = [ listcomp_assign_node, sort_node ]))
1341
1342     def _handle_simple_function_sum(self, node, pos_args):
1343         """Transform sum(genexpr) into an equivalent inlined aggregation loop.
1344         """
1345         if len(pos_args) not in (1,2):
1346             return node
1347         if not isinstance(pos_args[0], (ExprNodes.GeneratorExpressionNode,
1348                                         ExprNodes.ComprehensionNode)):
1349             return node
1350         gen_expr_node = pos_args[0]
1351         loop_node = gen_expr_node.loop
1352
1353         if isinstance(gen_expr_node, ExprNodes.GeneratorExpressionNode):
1354             yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1355             if yield_expression is None:
1356                 return node
1357         else: # ComprehensionNode
1358             yield_stat_node = gen_expr_node.append
1359             yield_expression = yield_stat_node.expr
1360             try:
1361                 if not yield_expression.is_literal or not yield_expression.type.is_int:
1362                     return node
1363             except AttributeError:
1364                 return node # in case we don't have a type yet
1365             # special case: old Py2 backwards compatible "sum([int_const for ...])"
1366             # can safely be unpacked into a genexpr
1367
1368         if len(pos_args) == 1:
1369             start = ExprNodes.IntNode(node.pos, value='0', constant_result=0)
1370         else:
1371             start = pos_args[1]
1372
1373         result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.py_object_type)
1374         add_node = Nodes.SingleAssignmentNode(
1375             yield_expression.pos,
1376             lhs = result_ref,
1377             rhs = ExprNodes.binop_node(node.pos, '+', result_ref, yield_expression)
1378             )
1379
1380         Visitor.recursively_replace_node(loop_node, yield_stat_node, add_node)
1381
1382         exec_code = Nodes.StatListNode(
1383             node.pos,
1384             stats = [
1385                 Nodes.SingleAssignmentNode(
1386                     start.pos,
1387                     lhs = UtilNodes.ResultRefNode(pos=node.pos, expression=result_ref),
1388                     rhs = start,
1389                     first = True),
1390                 loop_node
1391                 ])
1392
1393         return ExprNodes.InlinedGeneratorExpressionNode(
1394             gen_expr_node.pos, loop = exec_code, result_node = result_ref,
1395             expr_scope = gen_expr_node.expr_scope, orig_func = 'sum',
1396             has_local_scope = gen_expr_node.has_local_scope)
1397
1398     def _handle_simple_function_min(self, node, pos_args):
1399         return self._optimise_min_max(node, pos_args, '<')
1400
1401     def _handle_simple_function_max(self, node, pos_args):
1402         return self._optimise_min_max(node, pos_args, '>')
1403
1404     def _optimise_min_max(self, node, args, operator):
1405         """Replace min(a,b,...) and max(a,b,...) by explicit comparison code.
1406         """
1407         if len(args) <= 1:
1408             # leave this to Python
1409             return node
1410
1411         cascaded_nodes = list(map(UtilNodes.ResultRefNode, args[1:]))
1412
1413         last_result = args[0]
1414         for arg_node in cascaded_nodes:
1415             result_ref = UtilNodes.ResultRefNode(last_result)
1416             last_result = ExprNodes.CondExprNode(
1417                 arg_node.pos,
1418                 true_val = arg_node,
1419                 false_val = result_ref,
1420                 test = ExprNodes.PrimaryCmpNode(
1421                     arg_node.pos,
1422                     operand1 = arg_node,
1423                     operator = operator,
1424                     operand2 = result_ref,
1425                     )
1426                 )
1427             last_result = UtilNodes.EvalWithTempExprNode(result_ref, last_result)
1428
1429         for ref_node in cascaded_nodes[::-1]:
1430             last_result = UtilNodes.EvalWithTempExprNode(ref_node, last_result)
1431
1432         return last_result
1433
1434     def _DISABLED_handle_simple_function_tuple(self, node, pos_args):
1435         if len(pos_args) == 0:
1436             return ExprNodes.TupleNode(node.pos, args=[], constant_result=())
1437         # This is a bit special - for iterables (including genexps),
1438         # Python actually overallocates and resizes a newly created
1439         # tuple incrementally while reading items, which we can't
1440         # easily do without explicit node support. Instead, we read
1441         # the items into a list and then copy them into a tuple of the
1442         # final size.  This takes up to twice as much memory, but will
1443         # have to do until we have real support for genexps.
1444         result = self._transform_list_set_genexpr(node, pos_args, ExprNodes.ListNode)
1445         if result is not node:
1446             return ExprNodes.AsTupleNode(node.pos, arg=result)
1447         return node
1448
1449     def _handle_simple_function_list(self, node, pos_args):
1450         if len(pos_args) == 0:
1451             return ExprNodes.ListNode(node.pos, args=[], constant_result=[])
1452         return self._transform_list_set_genexpr(node, pos_args, ExprNodes.ListNode)
1453
1454     def _handle_simple_function_set(self, node, pos_args):
1455         if len(pos_args) == 0:
1456             return ExprNodes.SetNode(node.pos, args=[], constant_result=set())
1457         return self._transform_list_set_genexpr(node, pos_args, ExprNodes.SetNode)
1458
1459     def _transform_list_set_genexpr(self, node, pos_args, container_node_class):
1460         """Replace set(genexpr) and list(genexpr) by a literal comprehension.
1461         """
1462         if len(pos_args) > 1:
1463             return node
1464         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1465             return node
1466         gen_expr_node = pos_args[0]
1467         loop_node = gen_expr_node.loop
1468
1469         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1470         if yield_expression is None:
1471             return node
1472
1473         target_node = container_node_class(node.pos, args=[])
1474         append_node = ExprNodes.ComprehensionAppendNode(
1475             yield_expression.pos,
1476             expr = yield_expression,
1477             target = ExprNodes.CloneNode(target_node))
1478
1479         Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1480
1481         setcomp = ExprNodes.ComprehensionNode(
1482             node.pos,
1483             has_local_scope = True,
1484             expr_scope = gen_expr_node.expr_scope,
1485             loop = loop_node,
1486             append = append_node,
1487             target = target_node)
1488         append_node.target = setcomp
1489         return setcomp
1490
1491     def _handle_simple_function_dict(self, node, pos_args):
1492         """Replace dict( (a,b) for ... ) by a literal { a:b for ... }.
1493         """
1494         if len(pos_args) == 0:
1495             return ExprNodes.DictNode(node.pos, key_value_pairs=[], constant_result={})
1496         if len(pos_args) > 1:
1497             return node
1498         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1499             return node
1500         gen_expr_node = pos_args[0]
1501         loop_node = gen_expr_node.loop
1502
1503         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1504         if yield_expression is None:
1505             return node
1506
1507         if not isinstance(yield_expression, ExprNodes.TupleNode):
1508             return node
1509         if len(yield_expression.args) != 2:
1510             return node
1511
1512         target_node = ExprNodes.DictNode(node.pos, key_value_pairs=[])
1513         append_node = ExprNodes.DictComprehensionAppendNode(
1514             yield_expression.pos,
1515             key_expr = yield_expression.args[0],
1516             value_expr = yield_expression.args[1],
1517             target = ExprNodes.CloneNode(target_node))
1518
1519         Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1520
1521         dictcomp = ExprNodes.ComprehensionNode(
1522             node.pos,
1523             has_local_scope = True,
1524             expr_scope = gen_expr_node.expr_scope,
1525             loop = loop_node,
1526             append = append_node,
1527             target = target_node)
1528         append_node.target = dictcomp
1529         return dictcomp
1530
1531     # specific handlers for general call nodes
1532
1533     def _handle_general_function_dict(self, node, pos_args, kwargs):
1534         """Replace dict(a=b,c=d,...) by the underlying keyword dict
1535         construction which is done anyway.
1536         """
1537         if len(pos_args) > 0:
1538             return node
1539         if not isinstance(kwargs, ExprNodes.DictNode):
1540             return node
1541         if node.starstar_arg:
1542             # we could optimize this by updating the kw dict instead
1543             return node
1544         return kwargs
1545
1546
1547 class OptimizeBuiltinCalls(Visitor.EnvTransform):
1548     """Optimize some common methods calls and instantiation patterns
1549     for builtin types *after* the type analysis phase.
1550
1551     Running after type analysis, this transform can only perform
1552     function replacements that do not alter the function return type
1553     in a way that was not anticipated by the type analysis.
1554     """
1555     # only intercept on call nodes
1556     visit_Node = Visitor.VisitorTransform.recurse_to_children
1557
1558     def visit_GeneralCallNode(self, node):
1559         self.visitchildren(node)
1560         function = node.function
1561         if not function.type.is_pyobject:
1562             return node
1563         arg_tuple = node.positional_args
1564         if not isinstance(arg_tuple, ExprNodes.TupleNode):
1565             return node
1566         if node.starstar_arg:
1567             return node
1568         args = arg_tuple.args
1569         return self._dispatch_to_handler(
1570             node, function, args, node.keyword_args)
1571
1572     def visit_SimpleCallNode(self, node):
1573         self.visitchildren(node)
1574         function = node.function
1575         if function.type.is_pyobject:
1576             arg_tuple = node.arg_tuple
1577             if not isinstance(arg_tuple, ExprNodes.TupleNode):
1578                 return node
1579             args = arg_tuple.args
1580         else:
1581             args = node.args
1582         return self._dispatch_to_handler(
1583             node, function, args)
1584
1585     ### cleanup to avoid redundant coercions to/from Python types
1586
1587     def _visit_PyTypeTestNode(self, node):
1588         # disabled - appears to break assignments in some cases, and
1589         # also drops a None check, which might still be required
1590         """Flatten redundant type checks after tree changes.
1591         """
1592         old_arg = node.arg
1593         self.visitchildren(node)
1594         if old_arg is node.arg or node.arg.type != node.type:
1595             return node
1596         return node.arg
1597
1598     def visit_TypecastNode(self, node):
1599         """
1600         Drop redundant type casts.
1601         """
1602         self.visitchildren(node)
1603         if node.type == node.operand.type:
1604             return node.operand
1605         return node
1606
1607     def visit_ExprStatNode(self, node):
1608         """
1609         Drop useless coercions.
1610         """
1611         self.visitchildren(node)
1612         if isinstance(node.expr, ExprNodes.CoerceToPyTypeNode):
1613             node.expr = node.expr.arg
1614         return node
1615
1616     def visit_CoerceToBooleanNode(self, node):
1617         """Drop redundant conversion nodes after tree changes.
1618         """
1619         self.visitchildren(node)
1620         arg = node.arg
1621         if isinstance(arg, ExprNodes.PyTypeTestNode):
1622             arg = arg.arg
1623         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
1624             if arg.type in (PyrexTypes.py_object_type, Builtin.bool_type):
1625                 return arg.arg.coerce_to_boolean(self.current_env())
1626         return node
1627
1628     def visit_CoerceFromPyTypeNode(self, node):
1629         """Drop redundant conversion nodes after tree changes.
1630
1631         Also, optimise away calls to Python's builtin int() and
1632         float() if the result is going to be coerced back into a C
1633         type anyway.
1634         """
1635         self.visitchildren(node)
1636         arg = node.arg
1637         if not arg.type.is_pyobject:
1638             # no Python conversion left at all, just do a C coercion instead
1639             if node.type == arg.type:
1640                 return arg
1641             else:
1642                 return arg.coerce_to(node.type, self.current_env())
1643         if isinstance(arg, ExprNodes.PyTypeTestNode):
1644             arg = arg.arg
1645         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
1646             if arg.type is PyrexTypes.py_object_type:
1647                 if node.type.assignable_from(arg.arg.type):
1648                     # completely redundant C->Py->C coercion
1649                     return arg.arg.coerce_to(node.type, self.current_env())
1650         if isinstance(arg, ExprNodes.SimpleCallNode):
1651             if node.type.is_int or node.type.is_float:
1652                 return self._optimise_numeric_cast_call(node, arg)
1653         elif isinstance(arg, ExprNodes.IndexNode) and not arg.is_buffer_access:
1654             index_node = arg.index
1655             if isinstance(index_node, ExprNodes.CoerceToPyTypeNode):
1656                 index_node = index_node.arg
1657             if index_node.type.is_int:
1658                 return self._optimise_int_indexing(node, arg, index_node)
1659         return node
1660
1661     PyBytes_GetItemInt_func_type = PyrexTypes.CFuncType(
1662         PyrexTypes.c_char_type, [
1663             PyrexTypes.CFuncTypeArg("bytes", Builtin.bytes_type, None),
1664             PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_py_ssize_t_type, None),
1665             PyrexTypes.CFuncTypeArg("check_bounds", PyrexTypes.c_int_type, None),
1666             ],
1667         exception_value = "((char)-1)",
1668         exception_check = True)
1669
1670     def _optimise_int_indexing(self, coerce_node, arg, index_node):
1671         env = self.current_env()
1672         bound_check_bool = env.directives['boundscheck'] and 1 or 0
1673         if arg.base.type is Builtin.bytes_type:
1674             if coerce_node.type in (PyrexTypes.c_char_type, PyrexTypes.c_uchar_type):
1675                 # bytes[index] -> char
1676                 bound_check_node = ExprNodes.IntNode(
1677                     coerce_node.pos, value=str(bound_check_bool),
1678                     constant_result=bound_check_bool)
1679                 node = ExprNodes.PythonCapiCallNode(
1680                     coerce_node.pos, "__Pyx_PyBytes_GetItemInt",
1681                     self.PyBytes_GetItemInt_func_type,
1682                     args = [
1683                         arg.base.as_none_safe_node("'NoneType' object is not subscriptable"),
1684                         index_node.coerce_to(PyrexTypes.c_py_ssize_t_type, env),
1685                         bound_check_node,
1686                         ],
1687                     is_temp = True,
1688                     utility_code=bytes_index_utility_code)
1689                 if coerce_node.type is not PyrexTypes.c_char_type:
1690                     node = node.coerce_to(coerce_node.type, env)
1691                 return node
1692         return coerce_node
1693
1694     def _optimise_numeric_cast_call(self, node, arg):
1695         function = arg.function
1696         if not isinstance(function, ExprNodes.NameNode) \
1697                or not function.type.is_builtin_type \
1698                or not isinstance(arg.arg_tuple, ExprNodes.TupleNode):
1699             return node
1700         args = arg.arg_tuple.args
1701         if len(args) != 1:
1702             return node
1703         func_arg = args[0]
1704         if isinstance(func_arg, ExprNodes.CoerceToPyTypeNode):
1705             func_arg = func_arg.arg
1706         elif func_arg.type.is_pyobject:
1707             # play safe: Python conversion might work on all sorts of things
1708             return node
1709         if function.name == 'int':
1710             if func_arg.type.is_int or node.type.is_int:
1711                 if func_arg.type == node.type:
1712                     return func_arg
1713                 elif node.type.assignable_from(func_arg.type) or func_arg.type.is_float:
1714                     return ExprNodes.TypecastNode(
1715                         node.pos, operand=func_arg, type=node.type)
1716         elif function.name == 'float':
1717             if func_arg.type.is_float or node.type.is_float:
1718                 if func_arg.type == node.type:
1719                     return func_arg
1720                 elif node.type.assignable_from(func_arg.type) or func_arg.type.is_float:
1721                     return ExprNodes.TypecastNode(
1722                         node.pos, operand=func_arg, type=node.type)
1723         return node
1724
1725     ### dispatch to specific optimisers
1726
1727     def _find_handler(self, match_name, has_kwargs):
1728         call_type = has_kwargs and 'general' or 'simple'
1729         handler = getattr(self, '_handle_%s_%s' % (call_type, match_name), None)
1730         if handler is None:
1731             handler = getattr(self, '_handle_any_%s' % match_name, None)
1732         return handler
1733
1734     def _dispatch_to_handler(self, node, function, arg_list, kwargs=None):
1735         if function.is_name:
1736             # we only consider functions that are either builtin
1737             # Python functions or builtins that were already replaced
1738             # into a C function call (defined in the builtin scope)
1739             if not function.entry:
1740                 return node
1741             is_builtin = function.entry.is_builtin or \
1742                          function.entry is self.current_env().builtin_scope().lookup_here(function.name)
1743             if not is_builtin:
1744                 return node
1745             function_handler = self._find_handler(
1746                 "function_%s" % function.name, kwargs)
1747             if function_handler is None:
1748                 return node
1749             if kwargs:
1750                 return function_handler(node, arg_list, kwargs)
1751             else:
1752                 return function_handler(node, arg_list)
1753         elif function.is_attribute and function.type.is_pyobject:
1754             attr_name = function.attribute
1755             self_arg = function.obj
1756             obj_type = self_arg.type
1757             is_unbound_method = False
1758             if obj_type.is_builtin_type:
1759                 if obj_type is Builtin.type_type and arg_list and \
1760                          arg_list[0].type.is_pyobject:
1761                     # calling an unbound method like 'list.append(L,x)'
1762                     # (ignoring 'type.mro()' here ...)
1763                     type_name = function.obj.name
1764                     self_arg = None
1765                     is_unbound_method = True
1766                 else:
1767                     type_name = obj_type.name
1768             else:
1769                 type_name = "object" # safety measure
1770             method_handler = self._find_handler(
1771                 "method_%s_%s" % (type_name, attr_name), kwargs)
1772             if method_handler is None:
1773                 if attr_name in TypeSlots.method_name_to_slot \
1774                        or attr_name == '__new__':
1775                     method_handler = self._find_handler(
1776                         "slot%s" % attr_name, kwargs)
1777                 if method_handler is None:
1778                     return node
1779             if self_arg is not None:
1780                 arg_list = [self_arg] + list(arg_list)
1781             if kwargs:
1782                 return method_handler(node, arg_list, kwargs, is_unbound_method)
1783             else:
1784                 return method_handler(node, arg_list, is_unbound_method)
1785         else:
1786             return node
1787
1788     def _error_wrong_arg_count(self, function_name, node, args, expected=None):
1789         if not expected: # None or 0
1790             arg_str = ''
1791         elif isinstance(expected, basestring) or expected > 1:
1792             arg_str = '...'
1793         elif expected == 1:
1794             arg_str = 'x'
1795         else:
1796             arg_str = ''
1797         if expected is not None:
1798             expected_str = 'expected %s, ' % expected
1799         else:
1800             expected_str = ''
1801         error(node.pos, "%s(%s) called with wrong number of args, %sfound %d" % (
1802             function_name, arg_str, expected_str, len(args)))
1803
1804     ### builtin types
1805
1806     PyDict_Copy_func_type = PyrexTypes.CFuncType(
1807         Builtin.dict_type, [
1808             PyrexTypes.CFuncTypeArg("dict", Builtin.dict_type, None)
1809             ])
1810
1811     def _handle_simple_function_dict(self, node, pos_args):
1812         """Replace dict(some_dict) by PyDict_Copy(some_dict).
1813         """
1814         if len(pos_args) != 1:
1815             return node
1816         arg = pos_args[0]
1817         if arg.type is Builtin.dict_type:
1818             arg = arg.as_none_safe_node("'NoneType' is not iterable")
1819             return ExprNodes.PythonCapiCallNode(
1820                 node.pos, "PyDict_Copy", self.PyDict_Copy_func_type,
1821                 args = [arg],
1822                 is_temp = node.is_temp
1823                 )
1824         return node
1825
1826     PyList_AsTuple_func_type = PyrexTypes.CFuncType(
1827         Builtin.tuple_type, [
1828             PyrexTypes.CFuncTypeArg("list", Builtin.list_type, None)
1829             ])
1830
1831     def _handle_simple_function_tuple(self, node, pos_args):
1832         """Replace tuple([...]) by a call to PyList_AsTuple.
1833         """
1834         if len(pos_args) != 1:
1835             return node
1836         list_arg = pos_args[0]
1837         if list_arg.type is not Builtin.list_type:
1838             return node
1839         if not isinstance(list_arg, (ExprNodes.ComprehensionNode,
1840                                      ExprNodes.ListNode)):
1841             pos_args[0] = list_arg.as_none_safe_node(
1842                 "'NoneType' object is not iterable")
1843
1844         return ExprNodes.PythonCapiCallNode(
1845             node.pos, "PyList_AsTuple", self.PyList_AsTuple_func_type,
1846             args = pos_args,
1847             is_temp = node.is_temp
1848             )
1849
1850     PyObject_AsDouble_func_type = PyrexTypes.CFuncType(
1851         PyrexTypes.c_double_type, [
1852             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
1853             ],
1854         exception_value = "((double)-1)",
1855         exception_check = True)
1856
1857     def _handle_simple_function_float(self, node, pos_args):
1858         """Transform float() into either a C type cast or a faster C
1859         function call.
1860         """
1861         # Note: this requires the float() function to be typed as
1862         # returning a C 'double'
1863         if len(pos_args) == 0:
1864             return ExprNodes.FloatNode(
1865                 node, value="0.0", constant_result=0.0
1866                 ).coerce_to(Builtin.float_type, self.current_env())
1867         elif len(pos_args) != 1:
1868             self._error_wrong_arg_count('float', node, pos_args, '0 or 1')
1869             return node
1870         func_arg = pos_args[0]
1871         if isinstance(func_arg, ExprNodes.CoerceToPyTypeNode):
1872             func_arg = func_arg.arg
1873         if func_arg.type is PyrexTypes.c_double_type:
1874             return func_arg
1875         elif node.type.assignable_from(func_arg.type) or func_arg.type.is_numeric:
1876             return ExprNodes.TypecastNode(
1877                 node.pos, operand=func_arg, type=node.type)
1878         return ExprNodes.PythonCapiCallNode(
1879             node.pos, "__Pyx_PyObject_AsDouble",
1880             self.PyObject_AsDouble_func_type,
1881             args = pos_args,
1882             is_temp = node.is_temp,
1883             utility_code = pyobject_as_double_utility_code,
1884             py_name = "float")
1885
1886     def _handle_simple_function_bool(self, node, pos_args):
1887         """Transform bool(x) into a type coercion to a boolean.
1888         """
1889         if len(pos_args) == 0:
1890             return ExprNodes.BoolNode(
1891                 node.pos, value=False, constant_result=False
1892                 ).coerce_to(Builtin.bool_type, self.current_env())
1893         elif len(pos_args) != 1:
1894             self._error_wrong_arg_count('bool', node, pos_args, '0 or 1')
1895             return node
1896         else:
1897             # => !!<bint>(x)  to make sure it's exactly 0 or 1
1898             operand = pos_args[0].coerce_to_boolean(self.current_env())
1899             operand = ExprNodes.NotNode(node.pos, operand = operand)
1900             operand = ExprNodes.NotNode(node.pos, operand = operand)
1901             # coerce back to Python object as that's the result we are expecting
1902             return operand.coerce_to_pyobject(self.current_env())
1903
1904     ### builtin functions
1905
1906     Pyx_strlen_func_type = PyrexTypes.CFuncType(
1907         PyrexTypes.c_size_t_type, [
1908             PyrexTypes.CFuncTypeArg("bytes", PyrexTypes.c_char_ptr_type, None)
1909             ])
1910
1911     PyObject_Size_func_type = PyrexTypes.CFuncType(
1912         PyrexTypes.c_py_ssize_t_type, [
1913             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None)
1914             ])
1915
1916     _map_to_capi_len_function = {
1917         Builtin.unicode_type   : "PyUnicode_GET_SIZE",
1918         Builtin.bytes_type     : "PyBytes_GET_SIZE",
1919         Builtin.list_type      : "PyList_GET_SIZE",
1920         Builtin.tuple_type     : "PyTuple_GET_SIZE",
1921         Builtin.dict_type      : "PyDict_Size",
1922         Builtin.set_type       : "PySet_Size",
1923         Builtin.frozenset_type : "PySet_Size",
1924         }.get
1925
1926     def _handle_simple_function_len(self, node, pos_args):
1927         """Replace len(char*) by the equivalent call to strlen() and
1928         len(known_builtin_type) by an equivalent C-API call.
1929         """
1930         if len(pos_args) != 1:
1931             self._error_wrong_arg_count('len', node, pos_args, 1)
1932             return node
1933         arg = pos_args[0]
1934         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
1935             arg = arg.arg
1936         if arg.type.is_string:
1937             new_node = ExprNodes.PythonCapiCallNode(
1938                 node.pos, "strlen", self.Pyx_strlen_func_type,
1939                 args = [arg],
1940                 is_temp = node.is_temp,
1941                 utility_code = Builtin.include_string_h_utility_code)
1942         elif arg.type.is_pyobject:
1943             cfunc_name = self._map_to_capi_len_function(arg.type)
1944             if cfunc_name is None:
1945                 return node
1946             arg = arg.as_none_safe_node(
1947                 "object of type 'NoneType' has no len()")
1948             new_node = ExprNodes.PythonCapiCallNode(
1949                 node.pos, cfunc_name, self.PyObject_Size_func_type,
1950                 args = [arg],
1951                 is_temp = node.is_temp)
1952         elif arg.type.is_unicode_char:
1953             return ExprNodes.IntNode(node.pos, value='1', constant_result=1,
1954                                      type=node.type)
1955         else:
1956             return node
1957         if node.type not in (PyrexTypes.c_size_t_type, PyrexTypes.c_py_ssize_t_type):
1958             new_node = new_node.coerce_to(node.type, self.current_env())
1959         return new_node
1960
1961     Pyx_Type_func_type = PyrexTypes.CFuncType(
1962         Builtin.type_type, [
1963             PyrexTypes.CFuncTypeArg("object", PyrexTypes.py_object_type, None)
1964             ])
1965
1966     def _handle_simple_function_type(self, node, pos_args):
1967         """Replace type(o) by a macro call to Py_TYPE(o).
1968         """
1969         if len(pos_args) != 1:
1970             return node
1971         node = ExprNodes.PythonCapiCallNode(
1972             node.pos, "Py_TYPE", self.Pyx_Type_func_type,
1973             args = pos_args,
1974             is_temp = False)
1975         return ExprNodes.CastNode(node, PyrexTypes.py_object_type)
1976
1977     Py_type_check_func_type = PyrexTypes.CFuncType(
1978         PyrexTypes.c_bint_type, [
1979             PyrexTypes.CFuncTypeArg("arg", PyrexTypes.py_object_type, None)
1980             ])
1981
1982     def _handle_simple_function_isinstance(self, node, pos_args):
1983         """Replace isinstance() checks against builtin types by the
1984         corresponding C-API call.
1985         """
1986         if len(pos_args) != 2:
1987             return node
1988         arg, types = pos_args
1989         temp = None
1990         if isinstance(types, ExprNodes.TupleNode):
1991             types = types.args
1992             arg = temp = UtilNodes.ResultRefNode(arg)
1993         elif types.type is Builtin.type_type:
1994             types = [types]
1995         else:
1996             return node
1997
1998         tests = []
1999         test_nodes = []
2000         env = self.current_env()
2001         for test_type_node in types:
2002             builtin_type = None
2003             if isinstance(test_type_node, ExprNodes.NameNode):
2004                 if test_type_node.entry:
2005                     entry = env.lookup(test_type_node.entry.name)
2006                     if entry and entry.type and entry.type.is_builtin_type:
2007                         builtin_type = entry.type
2008             if builtin_type and builtin_type is not Builtin.type_type:
2009                 type_check_function = entry.type.type_check_function(exact=False)
2010                 if type_check_function in tests:
2011                     continue
2012                 tests.append(type_check_function)
2013                 type_check_args = [arg]
2014             elif test_type_node.type is Builtin.type_type:
2015                 type_check_function = '__Pyx_TypeCheck'
2016                 type_check_args = [arg, test_type_node]
2017             else:
2018                 return node
2019             test_nodes.append(
2020                 ExprNodes.PythonCapiCallNode(
2021                     test_type_node.pos, type_check_function, self.Py_type_check_func_type,
2022                     args = type_check_args,
2023                     is_temp = True,
2024                     ))
2025
2026         def join_with_or(a,b, make_binop_node=ExprNodes.binop_node):
2027             or_node = make_binop_node(node.pos, 'or', a, b)
2028             or_node.type = PyrexTypes.c_bint_type
2029             or_node.is_temp = True
2030             return or_node
2031
2032         test_node = reduce(join_with_or, test_nodes).coerce_to(node.type, env)
2033         if temp is not None:
2034             test_node = UtilNodes.EvalWithTempExprNode(temp, test_node)
2035         return test_node
2036
2037     def _handle_simple_function_ord(self, node, pos_args):
2038         """Unpack ord(Py_UNICODE).
2039         """
2040         if len(pos_args) != 1:
2041             return node
2042         arg = pos_args[0]
2043         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
2044             if arg.arg.type.is_unicode_char:
2045                 return arg.arg.coerce_to(node.type, self.current_env())
2046         return node
2047
2048     ### special methods
2049
2050     Pyx_tp_new_func_type = PyrexTypes.CFuncType(
2051         PyrexTypes.py_object_type, [
2052             PyrexTypes.CFuncTypeArg("type", Builtin.type_type, None)
2053             ])
2054
2055     def _handle_simple_slot__new__(self, node, args, is_unbound_method):
2056         """Replace 'exttype.__new__(exttype)' by a call to exttype->tp_new()
2057         """
2058         obj = node.function.obj
2059         if not is_unbound_method or len(args) != 1:
2060             return node
2061         type_arg = args[0]
2062         if not obj.is_name or not type_arg.is_name:
2063             # play safe
2064             return node
2065         if obj.type != Builtin.type_type or type_arg.type != Builtin.type_type:
2066             # not a known type, play safe
2067             return node
2068         if not type_arg.type_entry or not obj.type_entry:
2069             if obj.name != type_arg.name:
2070                 return node
2071             # otherwise, we know it's a type and we know it's the same
2072             # type for both - that should do
2073         elif type_arg.type_entry != obj.type_entry:
2074             # different types - may or may not lead to an error at runtime
2075             return node
2076
2077         # FIXME: we could potentially look up the actual tp_new C
2078         # method of the extension type and call that instead of the
2079         # generic slot. That would also allow us to pass parameters
2080         # efficiently.
2081
2082         if not type_arg.type_entry:
2083             # arbitrary variable, needs a None check for safety
2084             type_arg = type_arg.as_none_safe_node(
2085                 "object.__new__(X): X is not a type object (NoneType)")
2086
2087         return ExprNodes.PythonCapiCallNode(
2088             node.pos, "__Pyx_tp_new", self.Pyx_tp_new_func_type,
2089             args = [type_arg],
2090             utility_code = tpnew_utility_code,
2091             is_temp = node.is_temp
2092             )
2093
2094     ### methods of builtin types
2095
2096     PyObject_Append_func_type = PyrexTypes.CFuncType(
2097         PyrexTypes.py_object_type, [
2098             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2099             PyrexTypes.CFuncTypeArg("item", PyrexTypes.py_object_type, None),
2100             ])
2101
2102     def _handle_simple_method_object_append(self, node, args, is_unbound_method):
2103         """Optimistic optimisation as X.append() is almost always
2104         referring to a list.
2105         """
2106         if len(args) != 2:
2107             return node
2108
2109         return ExprNodes.PythonCapiCallNode(
2110             node.pos, "__Pyx_PyObject_Append", self.PyObject_Append_func_type,
2111             args = args,
2112             may_return_none = True,
2113             is_temp = node.is_temp,
2114             utility_code = append_utility_code
2115             )
2116
2117     PyObject_Pop_func_type = PyrexTypes.CFuncType(
2118         PyrexTypes.py_object_type, [
2119             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2120             ])
2121
2122     PyObject_PopIndex_func_type = PyrexTypes.CFuncType(
2123         PyrexTypes.py_object_type, [
2124             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2125             PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_long_type, None),
2126             ])
2127
2128     def _handle_simple_method_object_pop(self, node, args, is_unbound_method):
2129         """Optimistic optimisation as X.pop([n]) is almost always
2130         referring to a list.
2131         """
2132         if len(args) == 1:
2133             return ExprNodes.PythonCapiCallNode(
2134                 node.pos, "__Pyx_PyObject_Pop", self.PyObject_Pop_func_type,
2135                 args = args,
2136                 may_return_none = True,
2137                 is_temp = node.is_temp,
2138                 utility_code = pop_utility_code
2139                 )
2140         elif len(args) == 2:
2141             if isinstance(args[1], ExprNodes.CoerceToPyTypeNode) and args[1].arg.type.is_int:
2142                 original_type = args[1].arg.type
2143                 if PyrexTypes.widest_numeric_type(original_type, PyrexTypes.c_py_ssize_t_type) == PyrexTypes.c_py_ssize_t_type:
2144                     args[1] = args[1].arg
2145                     return ExprNodes.PythonCapiCallNode(
2146                         node.pos, "__Pyx_PyObject_PopIndex", self.PyObject_PopIndex_func_type,
2147                         args = args,
2148                         may_return_none = True,
2149                         is_temp = node.is_temp,
2150                         utility_code = pop_index_utility_code
2151                         )
2152
2153         return node
2154
2155     _handle_simple_method_list_pop = _handle_simple_method_object_pop
2156
2157     single_param_func_type = PyrexTypes.CFuncType(
2158         PyrexTypes.c_returncode_type, [
2159             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
2160             ],
2161         exception_value = "-1")
2162
2163     def _handle_simple_method_list_sort(self, node, args, is_unbound_method):
2164         """Call PyList_Sort() instead of the 0-argument l.sort().
2165         """
2166         if len(args) != 1:
2167             return node
2168         return self._substitute_method_call(
2169             node, "PyList_Sort", self.single_param_func_type,
2170             'sort', is_unbound_method, args).coerce_to(node.type, self.current_env)
2171
2172     Pyx_PyDict_GetItem_func_type = PyrexTypes.CFuncType(
2173         PyrexTypes.py_object_type, [
2174             PyrexTypes.CFuncTypeArg("dict", PyrexTypes.py_object_type, None),
2175             PyrexTypes.CFuncTypeArg("key", PyrexTypes.py_object_type, None),
2176             PyrexTypes.CFuncTypeArg("default", PyrexTypes.py_object_type, None),
2177             ])
2178
2179     def _handle_simple_method_dict_get(self, node, args, is_unbound_method):
2180         """Replace dict.get() by a call to PyDict_GetItem().
2181         """
2182         if len(args) == 2:
2183             args.append(ExprNodes.NoneNode(node.pos))
2184         elif len(args) != 3:
2185             self._error_wrong_arg_count('dict.get', node, args, "2 or 3")
2186             return node
2187
2188         return self._substitute_method_call(
2189             node, "__Pyx_PyDict_GetItemDefault", self.Pyx_PyDict_GetItem_func_type,
2190             'get', is_unbound_method, args,
2191             may_return_none = True,
2192             utility_code = dict_getitem_default_utility_code)
2193
2194
2195     ### unicode type methods
2196
2197     PyUnicode_uchar_predicate_func_type = PyrexTypes.CFuncType(
2198         PyrexTypes.c_bint_type, [
2199             PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_ucs4_type, None),
2200             ])
2201
2202     def _inject_unicode_predicate(self, node, args, is_unbound_method):
2203         if is_unbound_method or len(args) != 1:
2204             return node
2205         ustring = args[0]
2206         if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
2207                not ustring.arg.type.is_unicode_char:
2208             return node
2209         uchar = ustring.arg
2210         method_name = node.function.attribute
2211         if method_name == 'istitle':
2212             # istitle() doesn't directly map to Py_UNICODE_ISTITLE()
2213             utility_code = py_unicode_istitle_utility_code
2214             function_name = '__Pyx_Py_UNICODE_ISTITLE'
2215         else:
2216             utility_code = None
2217             function_name = 'Py_UNICODE_%s' % method_name.upper()
2218         func_call = self._substitute_method_call(
2219             node, function_name, self.PyUnicode_uchar_predicate_func_type,
2220             method_name, is_unbound_method, [uchar],
2221             utility_code = utility_code)
2222         if node.type.is_pyobject:
2223             func_call = func_call.coerce_to_pyobject(self.current_env)
2224         return func_call
2225
2226     _handle_simple_method_unicode_isalnum   = _inject_unicode_predicate
2227     _handle_simple_method_unicode_isalpha   = _inject_unicode_predicate
2228     _handle_simple_method_unicode_isdecimal = _inject_unicode_predicate
2229     _handle_simple_method_unicode_isdigit   = _inject_unicode_predicate
2230     _handle_simple_method_unicode_islower   = _inject_unicode_predicate
2231     _handle_simple_method_unicode_isnumeric = _inject_unicode_predicate
2232     _handle_simple_method_unicode_isspace   = _inject_unicode_predicate
2233     _handle_simple_method_unicode_istitle   = _inject_unicode_predicate
2234     _handle_simple_method_unicode_isupper   = _inject_unicode_predicate
2235
2236     PyUnicode_uchar_conversion_func_type = PyrexTypes.CFuncType(
2237         PyrexTypes.c_py_ucs4_type, [
2238             PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_ucs4_type, None),
2239             ])
2240
2241     def _inject_unicode_character_conversion(self, node, args, is_unbound_method):
2242         if is_unbound_method or len(args) != 1:
2243             return node
2244         ustring = args[0]
2245         if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
2246                not ustring.arg.type.is_unicode_char:
2247             return node
2248         uchar = ustring.arg
2249         method_name = node.function.attribute
2250         function_name = 'Py_UNICODE_TO%s' % method_name.upper()
2251         func_call = self._substitute_method_call(
2252             node, function_name, self.PyUnicode_uchar_conversion_func_type,
2253             method_name, is_unbound_method, [uchar])
2254         if node.type.is_pyobject:
2255             func_call = func_call.coerce_to_pyobject(self.current_env)
2256         return func_call
2257
2258     _handle_simple_method_unicode_lower = _inject_unicode_character_conversion
2259     _handle_simple_method_unicode_upper = _inject_unicode_character_conversion
2260     _handle_simple_method_unicode_title = _inject_unicode_character_conversion
2261
2262     PyUnicode_Splitlines_func_type = PyrexTypes.CFuncType(
2263         Builtin.list_type, [
2264             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2265             PyrexTypes.CFuncTypeArg("keepends", PyrexTypes.c_bint_type, None),
2266             ])
2267
2268     def _handle_simple_method_unicode_splitlines(self, node, args, is_unbound_method):
2269         """Replace unicode.splitlines(...) by a direct call to the
2270         corresponding C-API function.
2271         """
2272         if len(args) not in (1,2):
2273             self._error_wrong_arg_count('unicode.splitlines', node, args, "1 or 2")
2274             return node
2275         self._inject_bint_default_argument(node, args, 1, False)
2276
2277         return self._substitute_method_call(
2278             node, "PyUnicode_Splitlines", self.PyUnicode_Splitlines_func_type,
2279             'splitlines', is_unbound_method, args)
2280
2281     PyUnicode_Split_func_type = PyrexTypes.CFuncType(
2282         Builtin.list_type, [
2283             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2284             PyrexTypes.CFuncTypeArg("sep", PyrexTypes.py_object_type, None),
2285             PyrexTypes.CFuncTypeArg("maxsplit", PyrexTypes.c_py_ssize_t_type, None),
2286             ]
2287         )
2288
2289     def _handle_simple_method_unicode_split(self, node, args, is_unbound_method):
2290         """Replace unicode.split(...) by a direct call to the
2291         corresponding C-API function.
2292         """
2293         if len(args) not in (1,2,3):
2294             self._error_wrong_arg_count('unicode.split', node, args, "1-3")
2295             return node
2296         if len(args) < 2:
2297             args.append(ExprNodes.NullNode(node.pos))
2298         self._inject_int_default_argument(
2299             node, args, 2, PyrexTypes.c_py_ssize_t_type, "-1")
2300
2301         return self._substitute_method_call(
2302             node, "PyUnicode_Split", self.PyUnicode_Split_func_type,
2303             'split', is_unbound_method, args)
2304
2305     PyUnicode_Tailmatch_func_type = PyrexTypes.CFuncType(
2306         PyrexTypes.c_bint_type, [
2307             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2308             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2309             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2310             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2311             PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
2312             ],
2313         exception_value = '-1')
2314
2315     def _handle_simple_method_unicode_endswith(self, node, args, is_unbound_method):
2316         return self._inject_unicode_tailmatch(
2317             node, args, is_unbound_method, 'endswith', +1)
2318
2319     def _handle_simple_method_unicode_startswith(self, node, args, is_unbound_method):
2320         return self._inject_unicode_tailmatch(
2321             node, args, is_unbound_method, 'startswith', -1)
2322
2323     def _inject_unicode_tailmatch(self, node, args, is_unbound_method,
2324                                   method_name, direction):
2325         """Replace unicode.startswith(...) and unicode.endswith(...)
2326         by a direct call to the corresponding C-API function.
2327         """
2328         if len(args) not in (2,3,4):
2329             self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
2330             return node
2331         self._inject_int_default_argument(
2332             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2333         self._inject_int_default_argument(
2334             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2335         args.append(ExprNodes.IntNode(
2336             node.pos, value=str(direction), type=PyrexTypes.c_int_type))
2337
2338         method_call = self._substitute_method_call(
2339             node, "__Pyx_PyUnicode_Tailmatch", self.PyUnicode_Tailmatch_func_type,
2340             method_name, is_unbound_method, args,
2341             utility_code = unicode_tailmatch_utility_code)
2342         return method_call.coerce_to(Builtin.bool_type, self.current_env())
2343
2344     PyUnicode_Find_func_type = PyrexTypes.CFuncType(
2345         PyrexTypes.c_py_ssize_t_type, [
2346             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2347             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2348             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2349             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2350             PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
2351             ],
2352         exception_value = '-2')
2353
2354     def _handle_simple_method_unicode_find(self, node, args, is_unbound_method):
2355         return self._inject_unicode_find(
2356             node, args, is_unbound_method, 'find', +1)
2357
2358     def _handle_simple_method_unicode_rfind(self, node, args, is_unbound_method):
2359         return self._inject_unicode_find(
2360             node, args, is_unbound_method, 'rfind', -1)
2361
2362     def _inject_unicode_find(self, node, args, is_unbound_method,
2363                              method_name, direction):
2364         """Replace unicode.find(...) and unicode.rfind(...) by a
2365         direct call to the corresponding C-API function.
2366         """
2367         if len(args) not in (2,3,4):
2368             self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
2369             return node
2370         self._inject_int_default_argument(
2371             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2372         self._inject_int_default_argument(
2373             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2374         args.append(ExprNodes.IntNode(
2375             node.pos, value=str(direction), type=PyrexTypes.c_int_type))
2376
2377         method_call = self._substitute_method_call(
2378             node, "PyUnicode_Find", self.PyUnicode_Find_func_type,
2379             method_name, is_unbound_method, args)
2380         return method_call.coerce_to_pyobject(self.current_env())
2381
2382     PyUnicode_Count_func_type = PyrexTypes.CFuncType(
2383         PyrexTypes.c_py_ssize_t_type, [
2384             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2385             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2386             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2387             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2388             ],
2389         exception_value = '-1')
2390
2391     def _handle_simple_method_unicode_count(self, node, args, is_unbound_method):
2392         """Replace unicode.count(...) by a direct call to the
2393         corresponding C-API function.
2394         """
2395         if len(args) not in (2,3,4):
2396             self._error_wrong_arg_count('unicode.count', node, args, "2-4")
2397             return node
2398         self._inject_int_default_argument(
2399             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2400         self._inject_int_default_argument(
2401             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2402
2403         method_call = self._substitute_method_call(
2404             node, "PyUnicode_Count", self.PyUnicode_Count_func_type,
2405             'count', is_unbound_method, args)
2406         return method_call.coerce_to_pyobject(self.current_env())
2407
2408     PyUnicode_Replace_func_type = PyrexTypes.CFuncType(
2409         Builtin.unicode_type, [
2410             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2411             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2412             PyrexTypes.CFuncTypeArg("replstr", PyrexTypes.py_object_type, None),
2413             PyrexTypes.CFuncTypeArg("maxcount", PyrexTypes.c_py_ssize_t_type, None),
2414             ])
2415
2416     def _handle_simple_method_unicode_replace(self, node, args, is_unbound_method):
2417         """Replace unicode.replace(...) by a direct call to the
2418         corresponding C-API function.
2419         """
2420         if len(args) not in (3,4):
2421             self._error_wrong_arg_count('unicode.replace', node, args, "3-4")
2422             return node
2423         self._inject_int_default_argument(
2424             node, args, 3, PyrexTypes.c_py_ssize_t_type, "-1")
2425
2426         return self._substitute_method_call(
2427             node, "PyUnicode_Replace", self.PyUnicode_Replace_func_type,
2428             'replace', is_unbound_method, args)
2429
2430     PyUnicode_AsEncodedString_func_type = PyrexTypes.CFuncType(
2431         Builtin.bytes_type, [
2432             PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2433             PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
2434             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2435             ])
2436
2437     PyUnicode_AsXyzString_func_type = PyrexTypes.CFuncType(
2438         Builtin.bytes_type, [
2439             PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2440             ])
2441
2442     _special_encodings = ['UTF8', 'UTF16', 'Latin1', 'ASCII',
2443                           'unicode_escape', 'raw_unicode_escape']
2444
2445     _special_codecs = [ (name, codecs.getencoder(name))
2446                         for name in _special_encodings ]
2447
2448     def _handle_simple_method_unicode_encode(self, node, args, is_unbound_method):
2449         """Replace unicode.encode(...) by a direct C-API call to the
2450         corresponding codec.
2451         """
2452         if len(args) < 1 or len(args) > 3:
2453             self._error_wrong_arg_count('unicode.encode', node, args, '1-3')
2454             return node
2455
2456         string_node = args[0]
2457
2458         if len(args) == 1:
2459             null_node = ExprNodes.NullNode(node.pos)
2460             return self._substitute_method_call(
2461                 node, "PyUnicode_AsEncodedString",
2462                 self.PyUnicode_AsEncodedString_func_type,
2463                 'encode', is_unbound_method, [string_node, null_node, null_node])
2464
2465         parameters = self._unpack_encoding_and_error_mode(node.pos, args)
2466         if parameters is None:
2467             return node
2468         encoding, encoding_node, error_handling, error_handling_node = parameters
2469
2470         if isinstance(string_node, ExprNodes.UnicodeNode):
2471             # constant, so try to do the encoding at compile time
2472             try:
2473                 value = string_node.value.encode(encoding, error_handling)
2474             except:
2475                 # well, looks like we can't
2476                 pass
2477             else:
2478                 value = BytesLiteral(value)
2479                 value.encoding = encoding
2480                 return ExprNodes.BytesNode(
2481                     string_node.pos, value=value, type=Builtin.bytes_type)
2482
2483         if error_handling == 'strict':
2484             # try to find a specific encoder function
2485             codec_name = self._find_special_codec_name(encoding)
2486             if codec_name is not None:
2487                 encode_function = "PyUnicode_As%sString" % codec_name
2488                 return self._substitute_method_call(
2489                     node, encode_function,
2490                     self.PyUnicode_AsXyzString_func_type,
2491                     'encode', is_unbound_method, [string_node])
2492
2493         return self._substitute_method_call(
2494             node, "PyUnicode_AsEncodedString",
2495             self.PyUnicode_AsEncodedString_func_type,
2496             'encode', is_unbound_method,
2497             [string_node, encoding_node, error_handling_node])
2498
2499     PyUnicode_DecodeXyz_func_type = PyrexTypes.CFuncType(
2500         Builtin.unicode_type, [
2501             PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2502             PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
2503             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2504             ])
2505
2506     PyUnicode_Decode_func_type = PyrexTypes.CFuncType(
2507         Builtin.unicode_type, [
2508             PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2509             PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
2510             PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
2511             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2512             ])
2513
2514     def _handle_simple_method_bytes_decode(self, node, args, is_unbound_method):
2515         """Replace char*.decode() by a direct C-API call to the
2516         corresponding codec, possibly resoving a slice on the char*.
2517         """
2518         if len(args) < 1 or len(args) > 3:
2519             self._error_wrong_arg_count('bytes.decode', node, args, '1-3')
2520             return node
2521         temps = []
2522         if isinstance(args[0], ExprNodes.SliceIndexNode):
2523             index_node = args[0]
2524             string_node = index_node.base
2525             if not string_node.type.is_string:
2526                 # nothing to optimise here
2527                 return node
2528             start, stop = index_node.start, index_node.stop
2529             if not start or start.constant_result == 0:
2530                 start = None
2531             else:
2532                 if start.type.is_pyobject:
2533                     start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2534                 if stop:
2535                     start = UtilNodes.LetRefNode(start)
2536                     temps.append(start)
2537                 string_node = ExprNodes.AddNode(pos=start.pos,
2538                                                 operand1=string_node,
2539                                                 operator='+',
2540                                                 operand2=start,
2541                                                 is_temp=False,
2542                                                 type=string_node.type
2543                                                 )
2544             if stop and stop.type.is_pyobject:
2545                 stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2546         elif isinstance(args[0], ExprNodes.CoerceToPyTypeNode) \
2547                  and args[0].arg.type.is_string:
2548             # use strlen() to find the string length, just as CPython would
2549             start = stop = None
2550             string_node = args[0].arg
2551         else:
2552             # let Python do its job
2553             return node
2554
2555         if not stop:
2556             if start or not string_node.is_name:
2557                 string_node = UtilNodes.LetRefNode(string_node)
2558                 temps.append(string_node)
2559             stop = ExprNodes.PythonCapiCallNode(
2560                 string_node.pos, "strlen", self.Pyx_strlen_func_type,
2561                     args = [string_node],
2562                     is_temp = False,
2563                     utility_code = Builtin.include_string_h_utility_code,
2564                     ).coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2565         elif start:
2566             stop = ExprNodes.SubNode(
2567                 pos = stop.pos,
2568                 operand1 = stop,
2569                 operator = '-',
2570                 operand2 = start,
2571                 is_temp = False,
2572                 type = PyrexTypes.c_py_ssize_t_type
2573                 )
2574
2575         parameters = self._unpack_encoding_and_error_mode(node.pos, args)
2576         if parameters is None:
2577             return node
2578         encoding, encoding_node, error_handling, error_handling_node = parameters
2579
2580         # try to find a specific encoder function
2581         codec_name = None
2582         if encoding is not None:
2583             codec_name = self._find_special_codec_name(encoding)
2584         if codec_name is not None:
2585             decode_function = "PyUnicode_Decode%s" % codec_name
2586             node = ExprNodes.PythonCapiCallNode(
2587                 node.pos, decode_function,
2588                 self.PyUnicode_DecodeXyz_func_type,
2589                 args = [string_node, stop, error_handling_node],
2590                 is_temp = node.is_temp,
2591                 )
2592         else:
2593             node = ExprNodes.PythonCapiCallNode(
2594                 node.pos, "PyUnicode_Decode",
2595                 self.PyUnicode_Decode_func_type,
2596                 args = [string_node, stop, encoding_node, error_handling_node],
2597                 is_temp = node.is_temp,
2598                 )
2599
2600         for temp in temps[::-1]:
2601             node = UtilNodes.EvalWithTempExprNode(temp, node)
2602         return node
2603
2604     def _find_special_codec_name(self, encoding):
2605         try:
2606             requested_codec = codecs.getencoder(encoding)
2607         except:
2608             return None
2609         for name, codec in self._special_codecs:
2610             if codec == requested_codec:
2611                 if '_' in name:
2612                     name = ''.join([ s.capitalize()
2613                                      for s in name.split('_')])
2614                 return name
2615         return None
2616
2617     def _unpack_encoding_and_error_mode(self, pos, args):
2618         null_node = ExprNodes.NullNode(pos)
2619
2620         if len(args) >= 2:
2621             encoding_node = args[1]
2622             if isinstance(encoding_node, ExprNodes.CoerceToPyTypeNode):
2623                 encoding_node = encoding_node.arg
2624             if isinstance(encoding_node, (ExprNodes.UnicodeNode, ExprNodes.StringNode,
2625                                           ExprNodes.BytesNode)):
2626                 encoding = encoding_node.value
2627                 encoding_node = ExprNodes.BytesNode(encoding_node.pos, value=encoding,
2628                                                      type=PyrexTypes.c_char_ptr_type)
2629             elif encoding_node.type is Builtin.bytes_type:
2630                 encoding = None
2631                 encoding_node = encoding_node.coerce_to(
2632                     PyrexTypes.c_char_ptr_type, self.current_env())
2633             elif encoding_node.type.is_string:
2634                 encoding = None
2635             else:
2636                 return None
2637         else:
2638             encoding = None
2639             encoding_node = null_node
2640
2641         if len(args) == 3:
2642             error_handling_node = args[2]
2643             if isinstance(error_handling_node, ExprNodes.CoerceToPyTypeNode):
2644                 error_handling_node = error_handling_node.arg
2645             if isinstance(error_handling_node,
2646                           (ExprNodes.UnicodeNode, ExprNodes.StringNode,
2647                            ExprNodes.BytesNode)):
2648                 error_handling = error_handling_node.value
2649                 if error_handling == 'strict':
2650                     error_handling_node = null_node
2651                 else:
2652                     error_handling_node = ExprNodes.BytesNode(
2653                         error_handling_node.pos, value=error_handling,
2654                         type=PyrexTypes.c_char_ptr_type)
2655             elif error_handling_node.type is Builtin.bytes_type:
2656                 error_handling = None
2657                 error_handling_node = error_handling_node.coerce_to(
2658                     PyrexTypes.c_char_ptr_type, self.current_env())
2659             elif error_handling_node.type.is_string:
2660                 error_handling = None
2661             else:
2662                 return None
2663         else:
2664             error_handling = 'strict'
2665             error_handling_node = null_node
2666
2667         return (encoding, encoding_node, error_handling, error_handling_node)
2668
2669
2670     ### helpers
2671
2672     def _substitute_method_call(self, node, name, func_type,
2673                                 attr_name, is_unbound_method, args=(),
2674                                 utility_code=None,
2675                                 may_return_none=ExprNodes.PythonCapiCallNode.may_return_none):
2676         args = list(args)
2677         if args and not args[0].is_literal:
2678             self_arg = args[0]
2679             if is_unbound_method:
2680                 self_arg = self_arg.as_none_safe_node(
2681                     "descriptor '%s' requires a '%s' object but received a 'NoneType'" % (
2682                         attr_name, node.function.obj.name))
2683             else:
2684                 self_arg = self_arg.as_none_safe_node(
2685                     "'NoneType' object has no attribute '%s'" % attr_name,
2686                     error = "PyExc_AttributeError")
2687             args[0] = self_arg
2688         return ExprNodes.PythonCapiCallNode(
2689             node.pos, name, func_type,
2690             args = args,
2691             is_temp = node.is_temp,
2692             utility_code = utility_code,
2693             may_return_none = may_return_none,
2694             )
2695
2696     def _inject_int_default_argument(self, node, args, arg_index, type, default_value):
2697         assert len(args) >= arg_index
2698         if len(args) == arg_index:
2699             args.append(ExprNodes.IntNode(node.pos, value=str(default_value),
2700                                           type=type, constant_result=default_value))
2701         else:
2702             args[arg_index] = args[arg_index].coerce_to(type, self.current_env())
2703
2704     def _inject_bint_default_argument(self, node, args, arg_index, default_value):
2705         assert len(args) >= arg_index
2706         if len(args) == arg_index:
2707             default_value = bool(default_value)
2708             args.append(ExprNodes.BoolNode(node.pos, value=default_value,
2709                                            constant_result=default_value))
2710         else:
2711             args[arg_index] = args[arg_index].coerce_to_boolean(self.current_env())
2712
2713
2714 py_unicode_istitle_utility_code = UtilityCode(
2715 # Py_UNICODE_ISTITLE() doesn't match unicode.istitle() as the latter
2716 # additionally allows character that comply with Py_UNICODE_ISUPPER()
2717 proto = '''
2718 #if PY_VERSION_HEX < 0x030200A2
2719 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar); /* proto */
2720 #else
2721 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UCS4 uchar); /* proto */
2722 #endif
2723 ''',
2724 impl = '''
2725 #if PY_VERSION_HEX < 0x030200A2
2726 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar) {
2727 #else
2728 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UCS4 uchar) {
2729 #endif
2730     return Py_UNICODE_ISTITLE(uchar) || Py_UNICODE_ISUPPER(uchar);
2731 }
2732 ''')
2733
2734 unicode_tailmatch_utility_code = UtilityCode(
2735     # Python's unicode.startswith() and unicode.endswith() support a
2736     # tuple of prefixes/suffixes, whereas it's much more common to
2737     # test for a single unicode string.
2738 proto = '''
2739 static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr, \
2740 Py_ssize_t start, Py_ssize_t end, int direction);
2741 ''',
2742 impl = '''
2743 static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr,
2744                                      Py_ssize_t start, Py_ssize_t end, int direction) {
2745     if (unlikely(PyTuple_Check(substr))) {
2746         int result;
2747         Py_ssize_t i;
2748         for (i = 0; i < PyTuple_GET_SIZE(substr); i++) {
2749             result = PyUnicode_Tailmatch(s, PyTuple_GET_ITEM(substr, i),
2750                                          start, end, direction);
2751             if (result) {
2752                 return result;
2753             }
2754         }
2755         return 0;
2756     }
2757     return PyUnicode_Tailmatch(s, substr, start, end, direction);
2758 }
2759 ''',
2760 )
2761
2762 dict_getitem_default_utility_code = UtilityCode(
2763 proto = '''
2764 static PyObject* __Pyx_PyDict_GetItemDefault(PyObject* d, PyObject* key, PyObject* default_value) {
2765     PyObject* value;
2766 #if PY_MAJOR_VERSION >= 3
2767     value = PyDict_GetItemWithError(d, key);
2768     if (unlikely(!value)) {
2769         if (unlikely(PyErr_Occurred()))
2770             return NULL;
2771         value = default_value;
2772     }
2773     Py_INCREF(value);
2774 #else
2775     if (PyString_CheckExact(key) || PyUnicode_CheckExact(key) || PyInt_CheckExact(key)) {
2776         /* these presumably have safe hash functions */
2777         value = PyDict_GetItem(d, key);
2778         if (unlikely(!value)) {
2779             value = default_value;
2780         }
2781         Py_INCREF(value);
2782     } else {
2783         PyObject *m;
2784         m = __Pyx_GetAttrString(d, "get");
2785         if (!m) return NULL;
2786         value = PyObject_CallFunctionObjArgs(m, key,
2787             (default_value == Py_None) ? NULL : default_value, NULL);
2788         Py_DECREF(m);
2789     }
2790 #endif
2791     return value;
2792 }
2793 ''',
2794 impl = ""
2795 )
2796
2797 append_utility_code = UtilityCode(
2798 proto = """
2799 static CYTHON_INLINE PyObject* __Pyx_PyObject_Append(PyObject* L, PyObject* x) {
2800     if (likely(PyList_CheckExact(L))) {
2801         if (PyList_Append(L, x) < 0) return NULL;
2802         Py_INCREF(Py_None);
2803         return Py_None; /* this is just to have an accurate signature */
2804     }
2805     else {
2806         PyObject *r, *m;
2807         m = __Pyx_GetAttrString(L, "append");
2808         if (!m) return NULL;
2809         r = PyObject_CallFunctionObjArgs(m, x, NULL);
2810         Py_DECREF(m);
2811         return r;
2812     }
2813 }
2814 """,
2815 impl = ""
2816 )
2817
2818
2819 pop_utility_code = UtilityCode(
2820 proto = """
2821 static CYTHON_INLINE PyObject* __Pyx_PyObject_Pop(PyObject* L) {
2822     PyObject *r, *m;
2823 #if PY_VERSION_HEX >= 0x02040000
2824     if (likely(PyList_CheckExact(L))
2825             /* Check that both the size is positive and no reallocation shrinking needs to be done. */
2826             && likely(PyList_GET_SIZE(L) > (((PyListObject*)L)->allocated >> 1))) {
2827         Py_SIZE(L) -= 1;
2828         return PyList_GET_ITEM(L, PyList_GET_SIZE(L));
2829     }
2830 #endif
2831     m = __Pyx_GetAttrString(L, "pop");
2832     if (!m) return NULL;
2833     r = PyObject_CallObject(m, NULL);
2834     Py_DECREF(m);
2835     return r;
2836 }
2837 """,
2838 impl = ""
2839 )
2840
2841 pop_index_utility_code = UtilityCode(
2842 proto = """
2843 static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix);
2844 """,
2845 impl = """
2846 static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix) {
2847     PyObject *r, *m, *t, *py_ix;
2848 #if PY_VERSION_HEX >= 0x02040000
2849     if (likely(PyList_CheckExact(L))) {
2850         Py_ssize_t size = PyList_GET_SIZE(L);
2851         if (likely(size > (((PyListObject*)L)->allocated >> 1))) {
2852             if (ix < 0) {
2853                 ix += size;
2854             }
2855             if (likely(0 <= ix && ix < size)) {
2856                 Py_ssize_t i;
2857                 PyObject* v = PyList_GET_ITEM(L, ix);
2858                 Py_SIZE(L) -= 1;
2859                 size -= 1;
2860                 for(i=ix; i<size; i++) {
2861                     PyList_SET_ITEM(L, i, PyList_GET_ITEM(L, i+1));
2862                 }
2863                 return v;
2864             }
2865         }
2866     }
2867 #endif
2868     py_ix = t = NULL;
2869     m = __Pyx_GetAttrString(L, "pop");
2870     if (!m) goto bad;
2871     py_ix = PyInt_FromSsize_t(ix);
2872     if (!py_ix) goto bad;
2873     t = PyTuple_New(1);
2874     if (!t) goto bad;
2875     PyTuple_SET_ITEM(t, 0, py_ix);
2876     py_ix = NULL;
2877     r = PyObject_CallObject(m, t);
2878     Py_DECREF(m);
2879     Py_DECREF(t);
2880     return r;
2881 bad:
2882     Py_XDECREF(m);
2883     Py_XDECREF(t);
2884     Py_XDECREF(py_ix);
2885     return NULL;
2886 }
2887 """
2888 )
2889
2890
2891 pyobject_as_double_utility_code = UtilityCode(
2892 proto = '''
2893 static double __Pyx__PyObject_AsDouble(PyObject* obj); /* proto */
2894
2895 #define __Pyx_PyObject_AsDouble(obj) \\
2896     ((likely(PyFloat_CheckExact(obj))) ? \\
2897      PyFloat_AS_DOUBLE(obj) : __Pyx__PyObject_AsDouble(obj))
2898 ''',
2899 impl='''
2900 static double __Pyx__PyObject_AsDouble(PyObject* obj) {
2901     PyObject* float_value;
2902     if (Py_TYPE(obj)->tp_as_number && Py_TYPE(obj)->tp_as_number->nb_float) {
2903         return PyFloat_AsDouble(obj);
2904     } else if (PyUnicode_CheckExact(obj) || PyBytes_CheckExact(obj)) {
2905 #if PY_MAJOR_VERSION >= 3
2906         float_value = PyFloat_FromString(obj);
2907 #else
2908         float_value = PyFloat_FromString(obj, 0);
2909 #endif
2910     } else {
2911         PyObject* args = PyTuple_New(1);
2912         if (unlikely(!args)) goto bad;
2913         PyTuple_SET_ITEM(args, 0, obj);
2914         float_value = PyObject_Call((PyObject*)&PyFloat_Type, args, 0);
2915         PyTuple_SET_ITEM(args, 0, 0);
2916         Py_DECREF(args);
2917     }
2918     if (likely(float_value)) {
2919         double value = PyFloat_AS_DOUBLE(float_value);
2920         Py_DECREF(float_value);
2921         return value;
2922     }
2923 bad:
2924     return (double)-1;
2925 }
2926 '''
2927 )
2928
2929
2930 bytes_index_utility_code = UtilityCode(
2931 proto = """
2932 static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* unicode, Py_ssize_t index, int check_bounds); /* proto */
2933 """,
2934 impl = """
2935 static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* bytes, Py_ssize_t index, int check_bounds) {
2936     if (check_bounds) {
2937         if (unlikely(index >= PyBytes_GET_SIZE(bytes)) |
2938             ((index < 0) & unlikely(index < -PyBytes_GET_SIZE(bytes)))) {
2939             PyErr_Format(PyExc_IndexError, "string index out of range");
2940             return -1;
2941         }
2942     }
2943     if (index < 0)
2944         index += PyBytes_GET_SIZE(bytes);
2945     return PyBytes_AS_STRING(bytes)[index];
2946 }
2947 """
2948 )
2949
2950
2951 tpnew_utility_code = UtilityCode(
2952 proto = """
2953 static CYTHON_INLINE PyObject* __Pyx_tp_new(PyObject* type_obj) {
2954     return (PyObject*) (((PyTypeObject*)(type_obj))->tp_new(
2955         (PyTypeObject*)(type_obj), %(TUPLE)s, NULL));
2956 }
2957 """ % {'TUPLE' : Naming.empty_tuple}
2958 )
2959
2960
2961 class ConstantFolding(Visitor.VisitorTransform, SkipDeclarations):
2962     """Calculate the result of constant expressions to store it in
2963     ``expr_node.constant_result``, and replace trivial cases by their
2964     constant result.
2965
2966     General rules:
2967
2968     - We calculate float constants to make them available to the
2969       compiler, but we do not aggregate them into a single literal
2970       node to prevent any loss of precision.
2971
2972     - We recursively calculate constants from non-literal nodes to
2973       make them available to the compiler, but we only aggregate
2974       literal nodes at each step.  Non-literal nodes are never merged
2975       into a single node.
2976     """
2977     def _calculate_const(self, node):
2978         if node.constant_result is not ExprNodes.constant_value_not_set:
2979             return
2980
2981         # make sure we always set the value
2982         not_a_constant = ExprNodes.not_a_constant
2983         node.constant_result = not_a_constant
2984
2985         # check if all children are constant
2986         children = self.visitchildren(node)
2987         for child_result in children.values():
2988             if type(child_result) is list:
2989                 for child in child_result:
2990                     if getattr(child, 'constant_result', not_a_constant) is not_a_constant:
2991                         return
2992             elif getattr(child_result, 'constant_result', not_a_constant) is not_a_constant:
2993                 return
2994
2995         # now try to calculate the real constant value
2996         try:
2997             node.calculate_constant_result()
2998 #            if node.constant_result is not ExprNodes.not_a_constant:
2999 #                print node.__class__.__name__, node.constant_result
3000         except (ValueError, TypeError, KeyError, IndexError, AttributeError, ArithmeticError):
3001             # ignore all 'normal' errors here => no constant result
3002             pass
3003         except Exception:
3004             # this looks like a real error
3005             import traceback, sys
3006             traceback.print_exc(file=sys.stdout)
3007
3008     NODE_TYPE_ORDER = [ExprNodes.CharNode, ExprNodes.IntNode,
3009                        ExprNodes.LongNode, ExprNodes.FloatNode]
3010
3011     def _widest_node_class(self, *nodes):
3012         try:
3013             return self.NODE_TYPE_ORDER[
3014                 max(map(self.NODE_TYPE_ORDER.index, map(type, nodes)))]
3015         except ValueError:
3016             return None
3017
3018     def visit_ExprNode(self, node):
3019         self._calculate_const(node)
3020         return node
3021
3022     def visit_UnopNode(self, node):
3023         self._calculate_const(node)
3024         if node.constant_result is ExprNodes.not_a_constant:
3025             return node
3026         if not node.operand.is_literal:
3027             return node
3028         if isinstance(node.operand, ExprNodes.BoolNode):
3029             return ExprNodes.IntNode(node.pos, value = str(node.constant_result),
3030                                      type = PyrexTypes.c_int_type,
3031                                      constant_result = node.constant_result)
3032         if node.operator == '+':
3033             return self._handle_UnaryPlusNode(node)
3034         elif node.operator == '-':
3035             return self._handle_UnaryMinusNode(node)
3036         return node
3037
3038     def _handle_UnaryMinusNode(self, node):
3039         if isinstance(node.operand, ExprNodes.LongNode):
3040             return ExprNodes.LongNode(node.pos, value = '-' + node.operand.value,
3041                                       constant_result = node.constant_result)
3042         if isinstance(node.operand, ExprNodes.FloatNode):
3043             # this is a safe operation
3044             return ExprNodes.FloatNode(node.pos, value = '-' + node.operand.value,
3045                                        constant_result = node.constant_result)
3046         node_type = node.operand.type
3047         if node_type.is_int and node_type.signed or \
3048                isinstance(node.operand, ExprNodes.IntNode) and node_type.is_pyobject:
3049             return ExprNodes.IntNode(node.pos, value = '-' + node.operand.value,
3050                                      type = node_type,
3051                                      longness = node.operand.longness,
3052                                      constant_result = node.constant_result)
3053         return node
3054
3055     def _handle_UnaryPlusNode(self, node):
3056         if node.constant_result == node.operand.constant_result:
3057             return node.operand
3058         return node
3059
3060     def visit_BoolBinopNode(self, node):
3061         self._calculate_const(node)
3062         if node.constant_result is ExprNodes.not_a_constant:
3063             return node
3064         if not node.operand1.is_literal or not node.operand2.is_literal:
3065             return node
3066
3067         if node.constant_result == node.operand1.constant_result and node.operand1.is_literal:
3068             return node.operand1
3069         elif node.constant_result == node.operand2.constant_result and node.operand2.is_literal:
3070             return node.operand2
3071         else:
3072             # FIXME: we could do more ...
3073             return node
3074
3075     def visit_BinopNode(self, node):
3076         self._calculate_const(node)
3077         if node.constant_result is ExprNodes.not_a_constant:
3078             return node
3079         if isinstance(node.constant_result, float):
3080             return node
3081         operand1, operand2 = node.operand1, node.operand2
3082         if not operand1.is_literal or not operand2.is_literal:
3083             return node
3084
3085         # now inject a new constant node with the calculated value
3086         try:
3087             type1, type2 = operand1.type, operand2.type
3088             if type1 is None or type2 is None:
3089                 return node
3090         except AttributeError:
3091             return node
3092
3093         if type1.is_numeric and type2.is_numeric:
3094             widest_type = PyrexTypes.widest_numeric_type(type1, type2)
3095         else:
3096             widest_type = PyrexTypes.py_object_type
3097         target_class = self._widest_node_class(operand1, operand2)
3098         if target_class is None:
3099             return node
3100         elif target_class is ExprNodes.IntNode:
3101             unsigned = getattr(operand1, 'unsigned', '') and \
3102                        getattr(operand2, 'unsigned', '')
3103             longness = "LL"[:max(len(getattr(operand1, 'longness', '')),
3104                                  len(getattr(operand2, 'longness', '')))]
3105             new_node = ExprNodes.IntNode(pos=node.pos,
3106                                          unsigned = unsigned, longness = longness,
3107                                          value = str(node.constant_result),
3108                                          constant_result = node.constant_result)
3109             # IntNode is smart about the type it chooses, so we just
3110             # make sure we were not smarter this time
3111             if widest_type.is_pyobject or new_node.type.is_pyobject:
3112                 new_node.type = PyrexTypes.py_object_type
3113             else:
3114                 new_node.type = PyrexTypes.widest_numeric_type(widest_type, new_node.type)
3115         else:
3116             if isinstance(node, ExprNodes.BoolNode):
3117                 node_value = node.constant_result
3118             else:
3119                 node_value = str(node.constant_result)
3120             new_node = target_class(pos=node.pos, type = widest_type,
3121                                     value = node_value,
3122                                     constant_result = node.constant_result)
3123         return new_node
3124
3125     def visit_PrimaryCmpNode(self, node):
3126         self._calculate_const(node)
3127         if node.constant_result is ExprNodes.not_a_constant:
3128             return node
3129         bool_result = bool(node.constant_result)
3130         return ExprNodes.BoolNode(node.pos, value=bool_result,
3131                                   constant_result=bool_result)
3132
3133     def visit_IfStatNode(self, node):
3134         self.visitchildren(node)
3135         # eliminate dead code based on constant condition results
3136         if_clauses = []
3137         for if_clause in node.if_clauses:
3138             condition_result = if_clause.get_constant_condition_result()
3139             if condition_result is None:
3140                 # unknown result => normal runtime evaluation
3141                 if_clauses.append(if_clause)
3142             elif condition_result == True:
3143                 # subsequent clauses can safely be dropped
3144                 node.else_clause = if_clause.body
3145                 break
3146             else:
3147                 assert condition_result == False
3148         if not if_clauses:
3149             return node.else_clause
3150         node.if_clauses = if_clauses
3151         return node
3152
3153     # in the future, other nodes can have their own handler method here
3154     # that can replace them with a constant result node
3155
3156     visit_Node = Visitor.VisitorTransform.recurse_to_children
3157
3158
3159 class FinalOptimizePhase(Visitor.CythonTransform):
3160     """
3161     This visitor handles several commuting optimizations, and is run
3162     just before the C code generation phase.
3163
3164     The optimizations currently implemented in this class are:
3165         - eliminate None assignment and refcounting for first assignment.
3166         - isinstance -> typecheck for cdef types
3167         - eliminate checks for None and/or types that became redundant after tree changes
3168     """
3169     def visit_SingleAssignmentNode(self, node):
3170         """Avoid redundant initialisation of local variables before their
3171         first assignment.
3172         """
3173         self.visitchildren(node)
3174         if node.first:
3175             lhs = node.lhs
3176             lhs.lhs_of_first_assignment = True
3177             if isinstance(lhs, ExprNodes.NameNode) and lhs.entry.type.is_pyobject:
3178                 # Have variable initialized to 0 rather than None
3179                 lhs.entry.init_to_none = False
3180                 lhs.entry.init = 0
3181         return node
3182
3183     def visit_SimpleCallNode(self, node):
3184         """Replace generic calls to isinstance(x, type) by a more efficient
3185         type check.
3186         """
3187         self.visitchildren(node)
3188         if node.function.type.is_cfunction and isinstance(node.function, ExprNodes.NameNode):
3189             if node.function.name == 'isinstance':
3190                 type_arg = node.args[1]
3191                 if type_arg.type.is_builtin_type and type_arg.type.name == 'type':
3192                     from CythonScope import utility_scope
3193                     node.function.entry = utility_scope.lookup('PyObject_TypeCheck')
3194                     node.function.type = node.function.entry.type
3195                     PyTypeObjectPtr = PyrexTypes.CPtrType(utility_scope.lookup('PyTypeObject').type)
3196                     node.args[1] = ExprNodes.CastNode(node.args[1], PyTypeObjectPtr)
3197         return node
3198
3199     def visit_PyTypeTestNode(self, node):
3200         """Remove tests for alternatively allowed None values from
3201         type tests when we know that the argument cannot be None
3202         anyway.
3203         """
3204         self.visitchildren(node)
3205         if not node.notnone:
3206             if not node.arg.may_be_none():
3207                 node.notnone = True
3208         return node