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