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         # XXX: disable inlining while it's not back supported
1171         def __visit_YieldExprNode(self, node):
1172             self.yield_nodes.append(node)
1173             self.visitchildren(node)
1174
1175         def __visit_ExprStatNode(self, node):
1176             self.visitchildren(node)
1177             if node.expr in self.yield_nodes:
1178                 self.yield_stat_nodes[node.expr] = node
1179
1180         def __visit_GeneratorExpressionNode(self, node):
1181             # enable when we support generic generator expressions
1182             #
1183             # everything below this node is out of scope
1184             pass
1185
1186     def _find_single_yield_expression(self, node):
1187         collector = self.YieldNodeCollector()
1188         collector.visitchildren(node)
1189         if len(collector.yield_nodes) != 1:
1190             return None, None
1191         yield_node = collector.yield_nodes[0]
1192         try:
1193             return (yield_node.arg, collector.yield_stat_nodes[yield_node])
1194         except KeyError:
1195             return None, None
1196
1197     def _handle_simple_function_all(self, node, pos_args):
1198         """Transform
1199
1200         _result = all(x for L in LL for x in L)
1201
1202         into
1203
1204         for L in LL:
1205             for x in L:
1206                 if not x:
1207                     _result = False
1208                     break
1209             else:
1210                 continue
1211             break
1212         else:
1213             _result = True
1214         """
1215         return self._transform_any_all(node, pos_args, False)
1216
1217     def _handle_simple_function_any(self, node, pos_args):
1218         """Transform
1219
1220         _result = any(x for L in LL for x in L)
1221
1222         into
1223
1224         for L in LL:
1225             for x in L:
1226                 if x:
1227                     _result = True
1228                     break
1229             else:
1230                 continue
1231             break
1232         else:
1233             _result = False
1234         """
1235         return self._transform_any_all(node, pos_args, True)
1236
1237     def _transform_any_all(self, node, pos_args, is_any):
1238         if len(pos_args) != 1:
1239             return node
1240         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1241             return node
1242         gen_expr_node = pos_args[0]
1243         loop_node = gen_expr_node.loop
1244         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1245         if yield_expression is None:
1246             return node
1247
1248         if is_any:
1249             condition = yield_expression
1250         else:
1251             condition = ExprNodes.NotNode(yield_expression.pos, operand = yield_expression)
1252
1253         result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.c_bint_type)
1254         test_node = Nodes.IfStatNode(
1255             yield_expression.pos,
1256             else_clause = None,
1257             if_clauses = [ Nodes.IfClauseNode(
1258                 yield_expression.pos,
1259                 condition = condition,
1260                 body = Nodes.StatListNode(
1261                     node.pos,
1262                     stats = [
1263                         Nodes.SingleAssignmentNode(
1264                             node.pos,
1265                             lhs = result_ref,
1266                             rhs = ExprNodes.BoolNode(yield_expression.pos, value = is_any,
1267                                                      constant_result = is_any)),
1268                         Nodes.BreakStatNode(node.pos)
1269                         ])) ]
1270             )
1271         loop = loop_node
1272         while isinstance(loop.body, Nodes.LoopNode):
1273             next_loop = loop.body
1274             loop.body = Nodes.StatListNode(loop.body.pos, stats = [
1275                 loop.body,
1276                 Nodes.BreakStatNode(yield_expression.pos)
1277                 ])
1278             next_loop.else_clause = Nodes.ContinueStatNode(yield_expression.pos)
1279             loop = next_loop
1280         loop_node.else_clause = Nodes.SingleAssignmentNode(
1281             node.pos,
1282             lhs = result_ref,
1283             rhs = ExprNodes.BoolNode(yield_expression.pos, value = not is_any,
1284                                      constant_result = not is_any))
1285
1286         Visitor.recursively_replace_node(loop_node, yield_stat_node, test_node)
1287
1288         return ExprNodes.InlinedGeneratorExpressionNode(
1289             gen_expr_node.pos, loop = loop_node, result_node = result_ref,
1290             expr_scope = gen_expr_node.expr_scope, orig_func = is_any and 'any' or 'all')
1291
1292     def _handle_simple_function_sorted(self, node, pos_args):
1293         """Transform sorted(genexpr) into [listcomp].sort().  CPython
1294         just reads the iterable into a list and calls .sort() on it.
1295         Expanding the iterable in a listcomp is still faster.
1296         """
1297         if len(pos_args) != 1:
1298             return node
1299         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1300             return node
1301         gen_expr_node = pos_args[0]
1302         loop_node = gen_expr_node.loop
1303         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1304         if yield_expression is None:
1305             return node
1306
1307         result_node = UtilNodes.ResultRefNode(
1308             pos = loop_node.pos, type = Builtin.list_type, may_hold_none=False)
1309
1310         target = ExprNodes.ListNode(node.pos, args = [])
1311         append_node = ExprNodes.ComprehensionAppendNode(
1312             yield_expression.pos, expr = yield_expression,
1313             target = ExprNodes.CloneNode(target))
1314
1315         Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1316
1317         listcomp_node = ExprNodes.ComprehensionNode(
1318             gen_expr_node.pos, loop = loop_node, target = target,
1319             append = append_node, type = Builtin.list_type,
1320             expr_scope = gen_expr_node.expr_scope,
1321             has_local_scope = True)
1322         listcomp_assign_node = Nodes.SingleAssignmentNode(
1323             node.pos, lhs = result_node, rhs = listcomp_node, first = True)
1324
1325         sort_method = ExprNodes.AttributeNode(
1326             node.pos, obj = result_node, attribute = EncodedString('sort'),
1327             # entry ? type ?
1328             needs_none_check = False)
1329         sort_node = Nodes.ExprStatNode(
1330             node.pos, expr = ExprNodes.SimpleCallNode(
1331                 node.pos, function = sort_method, args = []))
1332
1333         sort_node.analyse_declarations(self.current_env())
1334
1335         return UtilNodes.TempResultFromStatNode(
1336             result_node,
1337             Nodes.StatListNode(node.pos, stats = [ listcomp_assign_node, sort_node ]))
1338
1339     def _handle_simple_function_sum(self, node, pos_args):
1340         """Transform sum(genexpr) into an equivalent inlined aggregation loop.
1341         """
1342         if len(pos_args) not in (1,2):
1343             return node
1344         if not isinstance(pos_args[0], (ExprNodes.GeneratorExpressionNode,
1345                                         ExprNodes.ComprehensionNode)):
1346             return node
1347         gen_expr_node = pos_args[0]
1348         loop_node = gen_expr_node.loop
1349
1350         if isinstance(gen_expr_node, ExprNodes.GeneratorExpressionNode):
1351             yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1352             if yield_expression is None:
1353                 return node
1354         else: # ComprehensionNode
1355             yield_stat_node = gen_expr_node.append
1356             yield_expression = yield_stat_node.expr
1357             try:
1358                 if not yield_expression.is_literal or not yield_expression.type.is_int:
1359                     return node
1360             except AttributeError:
1361                 return node # in case we don't have a type yet
1362             # special case: old Py2 backwards compatible "sum([int_const for ...])"
1363             # can safely be unpacked into a genexpr
1364
1365         if len(pos_args) == 1:
1366             start = ExprNodes.IntNode(node.pos, value='0', constant_result=0)
1367         else:
1368             start = pos_args[1]
1369
1370         result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.py_object_type)
1371         add_node = Nodes.SingleAssignmentNode(
1372             yield_expression.pos,
1373             lhs = result_ref,
1374             rhs = ExprNodes.binop_node(node.pos, '+', result_ref, yield_expression)
1375             )
1376
1377         Visitor.recursively_replace_node(loop_node, yield_stat_node, add_node)
1378
1379         exec_code = Nodes.StatListNode(
1380             node.pos,
1381             stats = [
1382                 Nodes.SingleAssignmentNode(
1383                     start.pos,
1384                     lhs = UtilNodes.ResultRefNode(pos=node.pos, expression=result_ref),
1385                     rhs = start,
1386                     first = True),
1387                 loop_node
1388                 ])
1389
1390         return ExprNodes.InlinedGeneratorExpressionNode(
1391             gen_expr_node.pos, loop = exec_code, result_node = result_ref,
1392             expr_scope = gen_expr_node.expr_scope, orig_func = 'sum',
1393             has_local_scope = gen_expr_node.has_local_scope)
1394
1395     def _handle_simple_function_min(self, node, pos_args):
1396         return self._optimise_min_max(node, pos_args, '<')
1397
1398     def _handle_simple_function_max(self, node, pos_args):
1399         return self._optimise_min_max(node, pos_args, '>')
1400
1401     def _optimise_min_max(self, node, args, operator):
1402         """Replace min(a,b,...) and max(a,b,...) by explicit comparison code.
1403         """
1404         if len(args) <= 1:
1405             # leave this to Python
1406             return node
1407
1408         cascaded_nodes = list(map(UtilNodes.ResultRefNode, args[1:]))
1409
1410         last_result = args[0]
1411         for arg_node in cascaded_nodes:
1412             result_ref = UtilNodes.ResultRefNode(last_result)
1413             last_result = ExprNodes.CondExprNode(
1414                 arg_node.pos,
1415                 true_val = arg_node,
1416                 false_val = result_ref,
1417                 test = ExprNodes.PrimaryCmpNode(
1418                     arg_node.pos,
1419                     operand1 = arg_node,
1420                     operator = operator,
1421                     operand2 = result_ref,
1422                     )
1423                 )
1424             last_result = UtilNodes.EvalWithTempExprNode(result_ref, last_result)
1425
1426         for ref_node in cascaded_nodes[::-1]:
1427             last_result = UtilNodes.EvalWithTempExprNode(ref_node, last_result)
1428
1429         return last_result
1430
1431     def _DISABLED_handle_simple_function_tuple(self, node, pos_args):
1432         if len(pos_args) == 0:
1433             return ExprNodes.TupleNode(node.pos, args=[], constant_result=())
1434         # This is a bit special - for iterables (including genexps),
1435         # Python actually overallocates and resizes a newly created
1436         # tuple incrementally while reading items, which we can't
1437         # easily do without explicit node support. Instead, we read
1438         # the items into a list and then copy them into a tuple of the
1439         # final size.  This takes up to twice as much memory, but will
1440         # have to do until we have real support for genexps.
1441         result = self._transform_list_set_genexpr(node, pos_args, ExprNodes.ListNode)
1442         if result is not node:
1443             return ExprNodes.AsTupleNode(node.pos, arg=result)
1444         return node
1445
1446     def _handle_simple_function_list(self, node, pos_args):
1447         if len(pos_args) == 0:
1448             return ExprNodes.ListNode(node.pos, args=[], constant_result=[])
1449         return self._transform_list_set_genexpr(node, pos_args, ExprNodes.ListNode)
1450
1451     def _handle_simple_function_set(self, node, pos_args):
1452         if len(pos_args) == 0:
1453             return ExprNodes.SetNode(node.pos, args=[], constant_result=set())
1454         return self._transform_list_set_genexpr(node, pos_args, ExprNodes.SetNode)
1455
1456     def _transform_list_set_genexpr(self, node, pos_args, container_node_class):
1457         """Replace set(genexpr) and list(genexpr) by a literal comprehension.
1458         """
1459         if len(pos_args) > 1:
1460             return node
1461         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1462             return node
1463         gen_expr_node = pos_args[0]
1464         loop_node = gen_expr_node.loop
1465
1466         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1467         if yield_expression is None:
1468             return node
1469
1470         target_node = container_node_class(node.pos, args=[])
1471         append_node = ExprNodes.ComprehensionAppendNode(
1472             yield_expression.pos,
1473             expr = yield_expression,
1474             target = ExprNodes.CloneNode(target_node))
1475
1476         Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1477
1478         setcomp = ExprNodes.ComprehensionNode(
1479             node.pos,
1480             has_local_scope = True,
1481             expr_scope = gen_expr_node.expr_scope,
1482             loop = loop_node,
1483             append = append_node,
1484             target = target_node)
1485         append_node.target = setcomp
1486         return setcomp
1487
1488     def _handle_simple_function_dict(self, node, pos_args):
1489         """Replace dict( (a,b) for ... ) by a literal { a:b for ... }.
1490         """
1491         if len(pos_args) == 0:
1492             return ExprNodes.DictNode(node.pos, key_value_pairs=[], constant_result={})
1493         if len(pos_args) > 1:
1494             return node
1495         if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
1496             return node
1497         gen_expr_node = pos_args[0]
1498         loop_node = gen_expr_node.loop
1499
1500         yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
1501         if yield_expression is None:
1502             return node
1503
1504         if not isinstance(yield_expression, ExprNodes.TupleNode):
1505             return node
1506         if len(yield_expression.args) != 2:
1507             return node
1508
1509         target_node = ExprNodes.DictNode(node.pos, key_value_pairs=[])
1510         append_node = ExprNodes.DictComprehensionAppendNode(
1511             yield_expression.pos,
1512             key_expr = yield_expression.args[0],
1513             value_expr = yield_expression.args[1],
1514             target = ExprNodes.CloneNode(target_node))
1515
1516         Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1517
1518         dictcomp = ExprNodes.ComprehensionNode(
1519             node.pos,
1520             has_local_scope = True,
1521             expr_scope = gen_expr_node.expr_scope,
1522             loop = loop_node,
1523             append = append_node,
1524             target = target_node)
1525         append_node.target = dictcomp
1526         return dictcomp
1527
1528     # specific handlers for general call nodes
1529
1530     def _handle_general_function_dict(self, node, pos_args, kwargs):
1531         """Replace dict(a=b,c=d,...) by the underlying keyword dict
1532         construction which is done anyway.
1533         """
1534         if len(pos_args) > 0:
1535             return node
1536         if not isinstance(kwargs, ExprNodes.DictNode):
1537             return node
1538         if node.starstar_arg:
1539             # we could optimize this by updating the kw dict instead
1540             return node
1541         return kwargs
1542
1543
1544 class OptimizeBuiltinCalls(Visitor.EnvTransform):
1545     """Optimize some common methods calls and instantiation patterns
1546     for builtin types *after* the type analysis phase.
1547
1548     Running after type analysis, this transform can only perform
1549     function replacements that do not alter the function return type
1550     in a way that was not anticipated by the type analysis.
1551     """
1552     # only intercept on call nodes
1553     visit_Node = Visitor.VisitorTransform.recurse_to_children
1554
1555     def visit_GeneralCallNode(self, node):
1556         self.visitchildren(node)
1557         function = node.function
1558         if not function.type.is_pyobject:
1559             return node
1560         arg_tuple = node.positional_args
1561         if not isinstance(arg_tuple, ExprNodes.TupleNode):
1562             return node
1563         if node.starstar_arg:
1564             return node
1565         args = arg_tuple.args
1566         return self._dispatch_to_handler(
1567             node, function, args, node.keyword_args)
1568
1569     def visit_SimpleCallNode(self, node):
1570         self.visitchildren(node)
1571         function = node.function
1572         if function.type.is_pyobject:
1573             arg_tuple = node.arg_tuple
1574             if not isinstance(arg_tuple, ExprNodes.TupleNode):
1575                 return node
1576             args = arg_tuple.args
1577         else:
1578             args = node.args
1579         return self._dispatch_to_handler(
1580             node, function, args)
1581
1582     ### cleanup to avoid redundant coercions to/from Python types
1583
1584     def _visit_PyTypeTestNode(self, node):
1585         # disabled - appears to break assignments in some cases, and
1586         # also drops a None check, which might still be required
1587         """Flatten redundant type checks after tree changes.
1588         """
1589         old_arg = node.arg
1590         self.visitchildren(node)
1591         if old_arg is node.arg or node.arg.type != node.type:
1592             return node
1593         return node.arg
1594
1595     def visit_TypecastNode(self, node):
1596         """
1597         Drop redundant type casts.
1598         """
1599         self.visitchildren(node)
1600         if node.type == node.operand.type:
1601             return node.operand
1602         return node
1603
1604     def visit_CoerceToBooleanNode(self, node):
1605         """Drop redundant conversion nodes after tree changes.
1606         """
1607         self.visitchildren(node)
1608         arg = node.arg
1609         if isinstance(arg, ExprNodes.PyTypeTestNode):
1610             arg = arg.arg
1611         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
1612             if arg.type in (PyrexTypes.py_object_type, Builtin.bool_type):
1613                 return arg.arg.coerce_to_boolean(self.current_env())
1614         return node
1615
1616     def visit_CoerceFromPyTypeNode(self, node):
1617         """Drop redundant conversion nodes after tree changes.
1618
1619         Also, optimise away calls to Python's builtin int() and
1620         float() if the result is going to be coerced back into a C
1621         type anyway.
1622         """
1623         self.visitchildren(node)
1624         arg = node.arg
1625         if not arg.type.is_pyobject:
1626             # no Python conversion left at all, just do a C coercion instead
1627             if node.type == arg.type:
1628                 return arg
1629             else:
1630                 return arg.coerce_to(node.type, self.current_env())
1631         if isinstance(arg, ExprNodes.PyTypeTestNode):
1632             arg = arg.arg
1633         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
1634             if arg.type is PyrexTypes.py_object_type:
1635                 if node.type.assignable_from(arg.arg.type):
1636                     # completely redundant C->Py->C coercion
1637                     return arg.arg.coerce_to(node.type, self.current_env())
1638         if isinstance(arg, ExprNodes.SimpleCallNode):
1639             if node.type.is_int or node.type.is_float:
1640                 return self._optimise_numeric_cast_call(node, arg)
1641         elif isinstance(arg, ExprNodes.IndexNode) and not arg.is_buffer_access:
1642             index_node = arg.index
1643             if isinstance(index_node, ExprNodes.CoerceToPyTypeNode):
1644                 index_node = index_node.arg
1645             if index_node.type.is_int:
1646                 return self._optimise_int_indexing(node, arg, index_node)
1647         return node
1648
1649     PyBytes_GetItemInt_func_type = PyrexTypes.CFuncType(
1650         PyrexTypes.c_char_type, [
1651             PyrexTypes.CFuncTypeArg("bytes", Builtin.bytes_type, None),
1652             PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_py_ssize_t_type, None),
1653             PyrexTypes.CFuncTypeArg("check_bounds", PyrexTypes.c_int_type, None),
1654             ],
1655         exception_value = "((char)-1)",
1656         exception_check = True)
1657
1658     def _optimise_int_indexing(self, coerce_node, arg, index_node):
1659         env = self.current_env()
1660         bound_check_bool = env.directives['boundscheck'] and 1 or 0
1661         if arg.base.type is Builtin.bytes_type:
1662             if coerce_node.type in (PyrexTypes.c_char_type, PyrexTypes.c_uchar_type):
1663                 # bytes[index] -> char
1664                 bound_check_node = ExprNodes.IntNode(
1665                     coerce_node.pos, value=str(bound_check_bool),
1666                     constant_result=bound_check_bool)
1667                 node = ExprNodes.PythonCapiCallNode(
1668                     coerce_node.pos, "__Pyx_PyBytes_GetItemInt",
1669                     self.PyBytes_GetItemInt_func_type,
1670                     args = [
1671                         arg.base.as_none_safe_node("'NoneType' object is not subscriptable"),
1672                         index_node.coerce_to(PyrexTypes.c_py_ssize_t_type, env),
1673                         bound_check_node,
1674                         ],
1675                     is_temp = True,
1676                     utility_code=bytes_index_utility_code)
1677                 if coerce_node.type is not PyrexTypes.c_char_type:
1678                     node = node.coerce_to(coerce_node.type, env)
1679                 return node
1680         return coerce_node
1681
1682     def _optimise_numeric_cast_call(self, node, arg):
1683         function = arg.function
1684         if not isinstance(function, ExprNodes.NameNode) \
1685                or not function.type.is_builtin_type \
1686                or not isinstance(arg.arg_tuple, ExprNodes.TupleNode):
1687             return node
1688         args = arg.arg_tuple.args
1689         if len(args) != 1:
1690             return node
1691         func_arg = args[0]
1692         if isinstance(func_arg, ExprNodes.CoerceToPyTypeNode):
1693             func_arg = func_arg.arg
1694         elif func_arg.type.is_pyobject:
1695             # play safe: Python conversion might work on all sorts of things
1696             return node
1697         if function.name == 'int':
1698             if func_arg.type.is_int or node.type.is_int:
1699                 if func_arg.type == node.type:
1700                     return func_arg
1701                 elif node.type.assignable_from(func_arg.type) or func_arg.type.is_float:
1702                     return ExprNodes.TypecastNode(
1703                         node.pos, operand=func_arg, type=node.type)
1704         elif function.name == 'float':
1705             if func_arg.type.is_float or node.type.is_float:
1706                 if func_arg.type == node.type:
1707                     return func_arg
1708                 elif node.type.assignable_from(func_arg.type) or func_arg.type.is_float:
1709                     return ExprNodes.TypecastNode(
1710                         node.pos, operand=func_arg, type=node.type)
1711         return node
1712
1713     ### dispatch to specific optimisers
1714
1715     def _find_handler(self, match_name, has_kwargs):
1716         call_type = has_kwargs and 'general' or 'simple'
1717         handler = getattr(self, '_handle_%s_%s' % (call_type, match_name), None)
1718         if handler is None:
1719             handler = getattr(self, '_handle_any_%s' % match_name, None)
1720         return handler
1721
1722     def _dispatch_to_handler(self, node, function, arg_list, kwargs=None):
1723         if function.is_name:
1724             # we only consider functions that are either builtin
1725             # Python functions or builtins that were already replaced
1726             # into a C function call (defined in the builtin scope)
1727             if not function.entry:
1728                 return node
1729             is_builtin = function.entry.is_builtin or \
1730                          function.entry is self.current_env().builtin_scope().lookup_here(function.name)
1731             if not is_builtin:
1732                 return node
1733             function_handler = self._find_handler(
1734                 "function_%s" % function.name, kwargs)
1735             if function_handler is None:
1736                 return node
1737             if kwargs:
1738                 return function_handler(node, arg_list, kwargs)
1739             else:
1740                 return function_handler(node, arg_list)
1741         elif function.is_attribute and function.type.is_pyobject:
1742             attr_name = function.attribute
1743             self_arg = function.obj
1744             obj_type = self_arg.type
1745             is_unbound_method = False
1746             if obj_type.is_builtin_type:
1747                 if obj_type is Builtin.type_type and arg_list and \
1748                          arg_list[0].type.is_pyobject:
1749                     # calling an unbound method like 'list.append(L,x)'
1750                     # (ignoring 'type.mro()' here ...)
1751                     type_name = function.obj.name
1752                     self_arg = None
1753                     is_unbound_method = True
1754                 else:
1755                     type_name = obj_type.name
1756             else:
1757                 type_name = "object" # safety measure
1758             method_handler = self._find_handler(
1759                 "method_%s_%s" % (type_name, attr_name), kwargs)
1760             if method_handler is None:
1761                 if attr_name in TypeSlots.method_name_to_slot \
1762                        or attr_name == '__new__':
1763                     method_handler = self._find_handler(
1764                         "slot%s" % attr_name, kwargs)
1765                 if method_handler is None:
1766                     return node
1767             if self_arg is not None:
1768                 arg_list = [self_arg] + list(arg_list)
1769             if kwargs:
1770                 return method_handler(node, arg_list, kwargs, is_unbound_method)
1771             else:
1772                 return method_handler(node, arg_list, is_unbound_method)
1773         else:
1774             return node
1775
1776     def _error_wrong_arg_count(self, function_name, node, args, expected=None):
1777         if not expected: # None or 0
1778             arg_str = ''
1779         elif isinstance(expected, basestring) or expected > 1:
1780             arg_str = '...'
1781         elif expected == 1:
1782             arg_str = 'x'
1783         else:
1784             arg_str = ''
1785         if expected is not None:
1786             expected_str = 'expected %s, ' % expected
1787         else:
1788             expected_str = ''
1789         error(node.pos, "%s(%s) called with wrong number of args, %sfound %d" % (
1790             function_name, arg_str, expected_str, len(args)))
1791
1792     ### builtin types
1793
1794     PyDict_Copy_func_type = PyrexTypes.CFuncType(
1795         Builtin.dict_type, [
1796             PyrexTypes.CFuncTypeArg("dict", Builtin.dict_type, None)
1797             ])
1798
1799     def _handle_simple_function_dict(self, node, pos_args):
1800         """Replace dict(some_dict) by PyDict_Copy(some_dict).
1801         """
1802         if len(pos_args) != 1:
1803             return node
1804         arg = pos_args[0]
1805         if arg.type is Builtin.dict_type:
1806             arg = arg.as_none_safe_node("'NoneType' is not iterable")
1807             return ExprNodes.PythonCapiCallNode(
1808                 node.pos, "PyDict_Copy", self.PyDict_Copy_func_type,
1809                 args = [arg],
1810                 is_temp = node.is_temp
1811                 )
1812         return node
1813
1814     PyList_AsTuple_func_type = PyrexTypes.CFuncType(
1815         Builtin.tuple_type, [
1816             PyrexTypes.CFuncTypeArg("list", Builtin.list_type, None)
1817             ])
1818
1819     def _handle_simple_function_tuple(self, node, pos_args):
1820         """Replace tuple([...]) by a call to PyList_AsTuple.
1821         """
1822         if len(pos_args) != 1:
1823             return node
1824         list_arg = pos_args[0]
1825         if list_arg.type is not Builtin.list_type:
1826             return node
1827         if not isinstance(list_arg, (ExprNodes.ComprehensionNode,
1828                                      ExprNodes.ListNode)):
1829             pos_args[0] = list_arg.as_none_safe_node(
1830                 "'NoneType' object is not iterable")
1831
1832         return ExprNodes.PythonCapiCallNode(
1833             node.pos, "PyList_AsTuple", self.PyList_AsTuple_func_type,
1834             args = pos_args,
1835             is_temp = node.is_temp
1836             )
1837
1838     PyObject_AsDouble_func_type = PyrexTypes.CFuncType(
1839         PyrexTypes.c_double_type, [
1840             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
1841             ],
1842         exception_value = "((double)-1)",
1843         exception_check = True)
1844
1845     def _handle_simple_function_float(self, node, pos_args):
1846         """Transform float() into either a C type cast or a faster C
1847         function call.
1848         """
1849         # Note: this requires the float() function to be typed as
1850         # returning a C 'double'
1851         if len(pos_args) == 0:
1852             return ExprNodes.FloatNode(
1853                 node, value="0.0", constant_result=0.0
1854                 ).coerce_to(Builtin.float_type, self.current_env())
1855         elif len(pos_args) != 1:
1856             self._error_wrong_arg_count('float', node, pos_args, '0 or 1')
1857             return node
1858         func_arg = pos_args[0]
1859         if isinstance(func_arg, ExprNodes.CoerceToPyTypeNode):
1860             func_arg = func_arg.arg
1861         if func_arg.type is PyrexTypes.c_double_type:
1862             return func_arg
1863         elif node.type.assignable_from(func_arg.type) or func_arg.type.is_numeric:
1864             return ExprNodes.TypecastNode(
1865                 node.pos, operand=func_arg, type=node.type)
1866         return ExprNodes.PythonCapiCallNode(
1867             node.pos, "__Pyx_PyObject_AsDouble",
1868             self.PyObject_AsDouble_func_type,
1869             args = pos_args,
1870             is_temp = node.is_temp,
1871             utility_code = pyobject_as_double_utility_code,
1872             py_name = "float")
1873
1874     def _handle_simple_function_bool(self, node, pos_args):
1875         """Transform bool(x) into a type coercion to a boolean.
1876         """
1877         if len(pos_args) == 0:
1878             return ExprNodes.BoolNode(
1879                 node.pos, value=False, constant_result=False
1880                 ).coerce_to(Builtin.bool_type, self.current_env())
1881         elif len(pos_args) != 1:
1882             self._error_wrong_arg_count('bool', node, pos_args, '0 or 1')
1883             return node
1884         else:
1885             # => !!<bint>(x)  to make sure it's exactly 0 or 1
1886             operand = pos_args[0].coerce_to_boolean(self.current_env())
1887             operand = ExprNodes.NotNode(node.pos, operand = operand)
1888             operand = ExprNodes.NotNode(node.pos, operand = operand)
1889             # coerce back to Python object as that's the result we are expecting
1890             return operand.coerce_to_pyobject(self.current_env())
1891
1892     ### builtin functions
1893
1894     Pyx_strlen_func_type = PyrexTypes.CFuncType(
1895         PyrexTypes.c_size_t_type, [
1896             PyrexTypes.CFuncTypeArg("bytes", PyrexTypes.c_char_ptr_type, None)
1897             ])
1898
1899     PyObject_Size_func_type = PyrexTypes.CFuncType(
1900         PyrexTypes.c_py_ssize_t_type, [
1901             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None)
1902             ])
1903
1904     _map_to_capi_len_function = {
1905         Builtin.unicode_type   : "PyUnicode_GET_SIZE",
1906         Builtin.bytes_type     : "PyBytes_GET_SIZE",
1907         Builtin.list_type      : "PyList_GET_SIZE",
1908         Builtin.tuple_type     : "PyTuple_GET_SIZE",
1909         Builtin.dict_type      : "PyDict_Size",
1910         Builtin.set_type       : "PySet_Size",
1911         Builtin.frozenset_type : "PySet_Size",
1912         }.get
1913
1914     def _handle_simple_function_len(self, node, pos_args):
1915         """Replace len(char*) by the equivalent call to strlen() and
1916         len(known_builtin_type) by an equivalent C-API call.
1917         """
1918         if len(pos_args) != 1:
1919             self._error_wrong_arg_count('len', node, pos_args, 1)
1920             return node
1921         arg = pos_args[0]
1922         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
1923             arg = arg.arg
1924         if arg.type.is_string:
1925             new_node = ExprNodes.PythonCapiCallNode(
1926                 node.pos, "strlen", self.Pyx_strlen_func_type,
1927                 args = [arg],
1928                 is_temp = node.is_temp,
1929                 utility_code = Builtin.include_string_h_utility_code)
1930         elif arg.type.is_pyobject:
1931             cfunc_name = self._map_to_capi_len_function(arg.type)
1932             if cfunc_name is None:
1933                 return node
1934             arg = arg.as_none_safe_node(
1935                 "object of type 'NoneType' has no len()")
1936             new_node = ExprNodes.PythonCapiCallNode(
1937                 node.pos, cfunc_name, self.PyObject_Size_func_type,
1938                 args = [arg],
1939                 is_temp = node.is_temp)
1940         elif arg.type.is_unicode_char:
1941             return ExprNodes.IntNode(node.pos, value='1', constant_result=1,
1942                                      type=node.type)
1943         else:
1944             return node
1945         if node.type not in (PyrexTypes.c_size_t_type, PyrexTypes.c_py_ssize_t_type):
1946             new_node = new_node.coerce_to(node.type, self.current_env())
1947         return new_node
1948
1949     Pyx_Type_func_type = PyrexTypes.CFuncType(
1950         Builtin.type_type, [
1951             PyrexTypes.CFuncTypeArg("object", PyrexTypes.py_object_type, None)
1952             ])
1953
1954     def _handle_simple_function_type(self, node, pos_args):
1955         """Replace type(o) by a macro call to Py_TYPE(o).
1956         """
1957         if len(pos_args) != 1:
1958             return node
1959         node = ExprNodes.PythonCapiCallNode(
1960             node.pos, "Py_TYPE", self.Pyx_Type_func_type,
1961             args = pos_args,
1962             is_temp = False)
1963         return ExprNodes.CastNode(node, PyrexTypes.py_object_type)
1964
1965     Py_type_check_func_type = PyrexTypes.CFuncType(
1966         PyrexTypes.c_bint_type, [
1967             PyrexTypes.CFuncTypeArg("arg", PyrexTypes.py_object_type, None)
1968             ])
1969
1970     def _handle_simple_function_isinstance(self, node, pos_args):
1971         """Replace isinstance() checks against builtin types by the
1972         corresponding C-API call.
1973         """
1974         if len(pos_args) != 2:
1975             return node
1976         arg, types = pos_args
1977         temp = None
1978         if isinstance(types, ExprNodes.TupleNode):
1979             types = types.args
1980             arg = temp = UtilNodes.ResultRefNode(arg)
1981         elif types.type is Builtin.type_type:
1982             types = [types]
1983         else:
1984             return node
1985
1986         tests = []
1987         test_nodes = []
1988         env = self.current_env()
1989         for test_type_node in types:
1990             builtin_type = None
1991             if isinstance(test_type_node, ExprNodes.NameNode):
1992                 if test_type_node.entry:
1993                     entry = env.lookup(test_type_node.entry.name)
1994                     if entry and entry.type and entry.type.is_builtin_type:
1995                         builtin_type = entry.type
1996             if builtin_type and builtin_type is not Builtin.type_type:
1997                 type_check_function = entry.type.type_check_function(exact=False)
1998                 if type_check_function in tests:
1999                     continue
2000                 tests.append(type_check_function)
2001                 type_check_args = [arg]
2002             elif test_type_node.type is Builtin.type_type:
2003                 type_check_function = '__Pyx_TypeCheck'
2004                 type_check_args = [arg, test_type_node]
2005             else:
2006                 return node
2007             test_nodes.append(
2008                 ExprNodes.PythonCapiCallNode(
2009                     test_type_node.pos, type_check_function, self.Py_type_check_func_type,
2010                     args = type_check_args,
2011                     is_temp = True,
2012                     ))
2013
2014         def join_with_or(a,b, make_binop_node=ExprNodes.binop_node):
2015             or_node = make_binop_node(node.pos, 'or', a, b)
2016             or_node.type = PyrexTypes.c_bint_type
2017             or_node.is_temp = True
2018             return or_node
2019
2020         test_node = reduce(join_with_or, test_nodes).coerce_to(node.type, env)
2021         if temp is not None:
2022             test_node = UtilNodes.EvalWithTempExprNode(temp, test_node)
2023         return test_node
2024
2025     def _handle_simple_function_ord(self, node, pos_args):
2026         """Unpack ord(Py_UNICODE).
2027         """
2028         if len(pos_args) != 1:
2029             return node
2030         arg = pos_args[0]
2031         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
2032             if arg.arg.type.is_unicode_char:
2033                 return arg.arg.coerce_to(node.type, self.current_env())
2034         return node
2035
2036     ### special methods
2037
2038     Pyx_tp_new_func_type = PyrexTypes.CFuncType(
2039         PyrexTypes.py_object_type, [
2040             PyrexTypes.CFuncTypeArg("type", Builtin.type_type, None)
2041             ])
2042
2043     def _handle_simple_slot__new__(self, node, args, is_unbound_method):
2044         """Replace 'exttype.__new__(exttype)' by a call to exttype->tp_new()
2045         """
2046         obj = node.function.obj
2047         if not is_unbound_method or len(args) != 1:
2048             return node
2049         type_arg = args[0]
2050         if not obj.is_name or not type_arg.is_name:
2051             # play safe
2052             return node
2053         if obj.type != Builtin.type_type or type_arg.type != Builtin.type_type:
2054             # not a known type, play safe
2055             return node
2056         if not type_arg.type_entry or not obj.type_entry:
2057             if obj.name != type_arg.name:
2058                 return node
2059             # otherwise, we know it's a type and we know it's the same
2060             # type for both - that should do
2061         elif type_arg.type_entry != obj.type_entry:
2062             # different types - may or may not lead to an error at runtime
2063             return node
2064
2065         # FIXME: we could potentially look up the actual tp_new C
2066         # method of the extension type and call that instead of the
2067         # generic slot. That would also allow us to pass parameters
2068         # efficiently.
2069
2070         if not type_arg.type_entry:
2071             # arbitrary variable, needs a None check for safety
2072             type_arg = type_arg.as_none_safe_node(
2073                 "object.__new__(X): X is not a type object (NoneType)")
2074
2075         return ExprNodes.PythonCapiCallNode(
2076             node.pos, "__Pyx_tp_new", self.Pyx_tp_new_func_type,
2077             args = [type_arg],
2078             utility_code = tpnew_utility_code,
2079             is_temp = node.is_temp
2080             )
2081
2082     ### methods of builtin types
2083
2084     PyObject_Append_func_type = PyrexTypes.CFuncType(
2085         PyrexTypes.py_object_type, [
2086             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2087             PyrexTypes.CFuncTypeArg("item", PyrexTypes.py_object_type, None),
2088             ])
2089
2090     def _handle_simple_method_object_append(self, node, args, is_unbound_method):
2091         """Optimistic optimisation as X.append() is almost always
2092         referring to a list.
2093         """
2094         if len(args) != 2:
2095             return node
2096
2097         return ExprNodes.PythonCapiCallNode(
2098             node.pos, "__Pyx_PyObject_Append", self.PyObject_Append_func_type,
2099             args = args,
2100             may_return_none = True,
2101             is_temp = node.is_temp,
2102             utility_code = append_utility_code
2103             )
2104
2105     PyObject_Pop_func_type = PyrexTypes.CFuncType(
2106         PyrexTypes.py_object_type, [
2107             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2108             ])
2109
2110     PyObject_PopIndex_func_type = PyrexTypes.CFuncType(
2111         PyrexTypes.py_object_type, [
2112             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2113             PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_long_type, None),
2114             ])
2115
2116     def _handle_simple_method_object_pop(self, node, args, is_unbound_method):
2117         """Optimistic optimisation as X.pop([n]) is almost always
2118         referring to a list.
2119         """
2120         if len(args) == 1:
2121             return ExprNodes.PythonCapiCallNode(
2122                 node.pos, "__Pyx_PyObject_Pop", self.PyObject_Pop_func_type,
2123                 args = args,
2124                 may_return_none = True,
2125                 is_temp = node.is_temp,
2126                 utility_code = pop_utility_code
2127                 )
2128         elif len(args) == 2:
2129             if isinstance(args[1], ExprNodes.CoerceToPyTypeNode) and args[1].arg.type.is_int:
2130                 original_type = args[1].arg.type
2131                 if PyrexTypes.widest_numeric_type(original_type, PyrexTypes.c_py_ssize_t_type) == PyrexTypes.c_py_ssize_t_type:
2132                     args[1] = args[1].arg
2133                     return ExprNodes.PythonCapiCallNode(
2134                         node.pos, "__Pyx_PyObject_PopIndex", self.PyObject_PopIndex_func_type,
2135                         args = args,
2136                         may_return_none = True,
2137                         is_temp = node.is_temp,
2138                         utility_code = pop_index_utility_code
2139                         )
2140
2141         return node
2142
2143     _handle_simple_method_list_pop = _handle_simple_method_object_pop
2144
2145     single_param_func_type = PyrexTypes.CFuncType(
2146         PyrexTypes.c_int_type, [
2147             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
2148             ],
2149         exception_value = "-1")
2150
2151     def _handle_simple_method_list_sort(self, node, args, is_unbound_method):
2152         """Call PyList_Sort() instead of the 0-argument l.sort().
2153         """
2154         if len(args) != 1:
2155             return node
2156         return self._substitute_method_call(
2157             node, "PyList_Sort", self.single_param_func_type,
2158             'sort', is_unbound_method, args)
2159
2160     Pyx_PyDict_GetItem_func_type = PyrexTypes.CFuncType(
2161         PyrexTypes.py_object_type, [
2162             PyrexTypes.CFuncTypeArg("dict", PyrexTypes.py_object_type, None),
2163             PyrexTypes.CFuncTypeArg("key", PyrexTypes.py_object_type, None),
2164             PyrexTypes.CFuncTypeArg("default", PyrexTypes.py_object_type, None),
2165             ])
2166
2167     def _handle_simple_method_dict_get(self, node, args, is_unbound_method):
2168         """Replace dict.get() by a call to PyDict_GetItem().
2169         """
2170         if len(args) == 2:
2171             args.append(ExprNodes.NoneNode(node.pos))
2172         elif len(args) != 3:
2173             self._error_wrong_arg_count('dict.get', node, args, "2 or 3")
2174             return node
2175
2176         return self._substitute_method_call(
2177             node, "__Pyx_PyDict_GetItemDefault", self.Pyx_PyDict_GetItem_func_type,
2178             'get', is_unbound_method, args,
2179             may_return_none = True,
2180             utility_code = dict_getitem_default_utility_code)
2181
2182
2183     ### unicode type methods
2184
2185     PyUnicode_uchar_predicate_func_type = PyrexTypes.CFuncType(
2186         PyrexTypes.c_bint_type, [
2187             PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_ucs4_type, None),
2188             ])
2189
2190     def _inject_unicode_predicate(self, node, args, is_unbound_method):
2191         if is_unbound_method or len(args) != 1:
2192             return node
2193         ustring = args[0]
2194         if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
2195                not ustring.arg.type.is_unicode_char:
2196             return node
2197         uchar = ustring.arg
2198         method_name = node.function.attribute
2199         if method_name == 'istitle':
2200             # istitle() doesn't directly map to Py_UNICODE_ISTITLE()
2201             utility_code = py_unicode_istitle_utility_code
2202             function_name = '__Pyx_Py_UNICODE_ISTITLE'
2203         else:
2204             utility_code = None
2205             function_name = 'Py_UNICODE_%s' % method_name.upper()
2206         func_call = self._substitute_method_call(
2207             node, function_name, self.PyUnicode_uchar_predicate_func_type,
2208             method_name, is_unbound_method, [uchar],
2209             utility_code = utility_code)
2210         if node.type.is_pyobject:
2211             func_call = func_call.coerce_to_pyobject(self.current_env)
2212         return func_call
2213
2214     _handle_simple_method_unicode_isalnum   = _inject_unicode_predicate
2215     _handle_simple_method_unicode_isalpha   = _inject_unicode_predicate
2216     _handle_simple_method_unicode_isdecimal = _inject_unicode_predicate
2217     _handle_simple_method_unicode_isdigit   = _inject_unicode_predicate
2218     _handle_simple_method_unicode_islower   = _inject_unicode_predicate
2219     _handle_simple_method_unicode_isnumeric = _inject_unicode_predicate
2220     _handle_simple_method_unicode_isspace   = _inject_unicode_predicate
2221     _handle_simple_method_unicode_istitle   = _inject_unicode_predicate
2222     _handle_simple_method_unicode_isupper   = _inject_unicode_predicate
2223
2224     PyUnicode_uchar_conversion_func_type = PyrexTypes.CFuncType(
2225         PyrexTypes.c_py_ucs4_type, [
2226             PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_ucs4_type, None),
2227             ])
2228
2229     def _inject_unicode_character_conversion(self, node, args, is_unbound_method):
2230         if is_unbound_method or len(args) != 1:
2231             return node
2232         ustring = args[0]
2233         if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
2234                not ustring.arg.type.is_unicode_char:
2235             return node
2236         uchar = ustring.arg
2237         method_name = node.function.attribute
2238         function_name = 'Py_UNICODE_TO%s' % method_name.upper()
2239         func_call = self._substitute_method_call(
2240             node, function_name, self.PyUnicode_uchar_conversion_func_type,
2241             method_name, is_unbound_method, [uchar])
2242         if node.type.is_pyobject:
2243             func_call = func_call.coerce_to_pyobject(self.current_env)
2244         return func_call
2245
2246     _handle_simple_method_unicode_lower = _inject_unicode_character_conversion
2247     _handle_simple_method_unicode_upper = _inject_unicode_character_conversion
2248     _handle_simple_method_unicode_title = _inject_unicode_character_conversion
2249
2250     PyUnicode_Splitlines_func_type = PyrexTypes.CFuncType(
2251         Builtin.list_type, [
2252             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2253             PyrexTypes.CFuncTypeArg("keepends", PyrexTypes.c_bint_type, None),
2254             ])
2255
2256     def _handle_simple_method_unicode_splitlines(self, node, args, is_unbound_method):
2257         """Replace unicode.splitlines(...) by a direct call to the
2258         corresponding C-API function.
2259         """
2260         if len(args) not in (1,2):
2261             self._error_wrong_arg_count('unicode.splitlines', node, args, "1 or 2")
2262             return node
2263         self._inject_bint_default_argument(node, args, 1, False)
2264
2265         return self._substitute_method_call(
2266             node, "PyUnicode_Splitlines", self.PyUnicode_Splitlines_func_type,
2267             'splitlines', is_unbound_method, args)
2268
2269     PyUnicode_Split_func_type = PyrexTypes.CFuncType(
2270         Builtin.list_type, [
2271             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2272             PyrexTypes.CFuncTypeArg("sep", PyrexTypes.py_object_type, None),
2273             PyrexTypes.CFuncTypeArg("maxsplit", PyrexTypes.c_py_ssize_t_type, None),
2274             ]
2275         )
2276
2277     def _handle_simple_method_unicode_split(self, node, args, is_unbound_method):
2278         """Replace unicode.split(...) by a direct call to the
2279         corresponding C-API function.
2280         """
2281         if len(args) not in (1,2,3):
2282             self._error_wrong_arg_count('unicode.split', node, args, "1-3")
2283             return node
2284         if len(args) < 2:
2285             args.append(ExprNodes.NullNode(node.pos))
2286         self._inject_int_default_argument(
2287             node, args, 2, PyrexTypes.c_py_ssize_t_type, "-1")
2288
2289         return self._substitute_method_call(
2290             node, "PyUnicode_Split", self.PyUnicode_Split_func_type,
2291             'split', is_unbound_method, args)
2292
2293     PyUnicode_Tailmatch_func_type = PyrexTypes.CFuncType(
2294         PyrexTypes.c_bint_type, [
2295             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2296             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2297             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2298             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2299             PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
2300             ],
2301         exception_value = '-1')
2302
2303     def _handle_simple_method_unicode_endswith(self, node, args, is_unbound_method):
2304         return self._inject_unicode_tailmatch(
2305             node, args, is_unbound_method, 'endswith', +1)
2306
2307     def _handle_simple_method_unicode_startswith(self, node, args, is_unbound_method):
2308         return self._inject_unicode_tailmatch(
2309             node, args, is_unbound_method, 'startswith', -1)
2310
2311     def _inject_unicode_tailmatch(self, node, args, is_unbound_method,
2312                                   method_name, direction):
2313         """Replace unicode.startswith(...) and unicode.endswith(...)
2314         by a direct call to the corresponding C-API function.
2315         """
2316         if len(args) not in (2,3,4):
2317             self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
2318             return node
2319         self._inject_int_default_argument(
2320             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2321         self._inject_int_default_argument(
2322             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2323         args.append(ExprNodes.IntNode(
2324             node.pos, value=str(direction), type=PyrexTypes.c_int_type))
2325
2326         method_call = self._substitute_method_call(
2327             node, "__Pyx_PyUnicode_Tailmatch", self.PyUnicode_Tailmatch_func_type,
2328             method_name, is_unbound_method, args,
2329             utility_code = unicode_tailmatch_utility_code)
2330         return method_call.coerce_to(Builtin.bool_type, self.current_env())
2331
2332     PyUnicode_Find_func_type = PyrexTypes.CFuncType(
2333         PyrexTypes.c_py_ssize_t_type, [
2334             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2335             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2336             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2337             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2338             PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
2339             ],
2340         exception_value = '-2')
2341
2342     def _handle_simple_method_unicode_find(self, node, args, is_unbound_method):
2343         return self._inject_unicode_find(
2344             node, args, is_unbound_method, 'find', +1)
2345
2346     def _handle_simple_method_unicode_rfind(self, node, args, is_unbound_method):
2347         return self._inject_unicode_find(
2348             node, args, is_unbound_method, 'rfind', -1)
2349
2350     def _inject_unicode_find(self, node, args, is_unbound_method,
2351                              method_name, direction):
2352         """Replace unicode.find(...) and unicode.rfind(...) by a
2353         direct call to the corresponding C-API function.
2354         """
2355         if len(args) not in (2,3,4):
2356             self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
2357             return node
2358         self._inject_int_default_argument(
2359             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2360         self._inject_int_default_argument(
2361             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2362         args.append(ExprNodes.IntNode(
2363             node.pos, value=str(direction), type=PyrexTypes.c_int_type))
2364
2365         method_call = self._substitute_method_call(
2366             node, "PyUnicode_Find", self.PyUnicode_Find_func_type,
2367             method_name, is_unbound_method, args)
2368         return method_call.coerce_to_pyobject(self.current_env())
2369
2370     PyUnicode_Count_func_type = PyrexTypes.CFuncType(
2371         PyrexTypes.c_py_ssize_t_type, [
2372             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2373             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2374             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2375             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2376             ],
2377         exception_value = '-1')
2378
2379     def _handle_simple_method_unicode_count(self, node, args, is_unbound_method):
2380         """Replace unicode.count(...) by a direct call to the
2381         corresponding C-API function.
2382         """
2383         if len(args) not in (2,3,4):
2384             self._error_wrong_arg_count('unicode.count', node, args, "2-4")
2385             return node
2386         self._inject_int_default_argument(
2387             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2388         self._inject_int_default_argument(
2389             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2390
2391         method_call = self._substitute_method_call(
2392             node, "PyUnicode_Count", self.PyUnicode_Count_func_type,
2393             'count', is_unbound_method, args)
2394         return method_call.coerce_to_pyobject(self.current_env())
2395
2396     PyUnicode_Replace_func_type = PyrexTypes.CFuncType(
2397         Builtin.unicode_type, [
2398             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2399             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2400             PyrexTypes.CFuncTypeArg("replstr", PyrexTypes.py_object_type, None),
2401             PyrexTypes.CFuncTypeArg("maxcount", PyrexTypes.c_py_ssize_t_type, None),
2402             ])
2403
2404     def _handle_simple_method_unicode_replace(self, node, args, is_unbound_method):
2405         """Replace unicode.replace(...) by a direct call to the
2406         corresponding C-API function.
2407         """
2408         if len(args) not in (3,4):
2409             self._error_wrong_arg_count('unicode.replace', node, args, "3-4")
2410             return node
2411         self._inject_int_default_argument(
2412             node, args, 3, PyrexTypes.c_py_ssize_t_type, "-1")
2413
2414         return self._substitute_method_call(
2415             node, "PyUnicode_Replace", self.PyUnicode_Replace_func_type,
2416             'replace', is_unbound_method, args)
2417
2418     PyUnicode_AsEncodedString_func_type = PyrexTypes.CFuncType(
2419         Builtin.bytes_type, [
2420             PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2421             PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
2422             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2423             ])
2424
2425     PyUnicode_AsXyzString_func_type = PyrexTypes.CFuncType(
2426         Builtin.bytes_type, [
2427             PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2428             ])
2429
2430     _special_encodings = ['UTF8', 'UTF16', 'Latin1', 'ASCII',
2431                           'unicode_escape', 'raw_unicode_escape']
2432
2433     _special_codecs = [ (name, codecs.getencoder(name))
2434                         for name in _special_encodings ]
2435
2436     def _handle_simple_method_unicode_encode(self, node, args, is_unbound_method):
2437         """Replace unicode.encode(...) by a direct C-API call to the
2438         corresponding codec.
2439         """
2440         if len(args) < 1 or len(args) > 3:
2441             self._error_wrong_arg_count('unicode.encode', node, args, '1-3')
2442             return node
2443
2444         string_node = args[0]
2445
2446         if len(args) == 1:
2447             null_node = ExprNodes.NullNode(node.pos)
2448             return self._substitute_method_call(
2449                 node, "PyUnicode_AsEncodedString",
2450                 self.PyUnicode_AsEncodedString_func_type,
2451                 'encode', is_unbound_method, [string_node, null_node, null_node])
2452
2453         parameters = self._unpack_encoding_and_error_mode(node.pos, args)
2454         if parameters is None:
2455             return node
2456         encoding, encoding_node, error_handling, error_handling_node = parameters
2457
2458         if isinstance(string_node, ExprNodes.UnicodeNode):
2459             # constant, so try to do the encoding at compile time
2460             try:
2461                 value = string_node.value.encode(encoding, error_handling)
2462             except:
2463                 # well, looks like we can't
2464                 pass
2465             else:
2466                 value = BytesLiteral(value)
2467                 value.encoding = encoding
2468                 return ExprNodes.BytesNode(
2469                     string_node.pos, value=value, type=Builtin.bytes_type)
2470
2471         if error_handling == 'strict':
2472             # try to find a specific encoder function
2473             codec_name = self._find_special_codec_name(encoding)
2474             if codec_name is not None:
2475                 encode_function = "PyUnicode_As%sString" % codec_name
2476                 return self._substitute_method_call(
2477                     node, encode_function,
2478                     self.PyUnicode_AsXyzString_func_type,
2479                     'encode', is_unbound_method, [string_node])
2480
2481         return self._substitute_method_call(
2482             node, "PyUnicode_AsEncodedString",
2483             self.PyUnicode_AsEncodedString_func_type,
2484             'encode', is_unbound_method,
2485             [string_node, encoding_node, error_handling_node])
2486
2487     PyUnicode_DecodeXyz_func_type = PyrexTypes.CFuncType(
2488         Builtin.unicode_type, [
2489             PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2490             PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
2491             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2492             ])
2493
2494     PyUnicode_Decode_func_type = PyrexTypes.CFuncType(
2495         Builtin.unicode_type, [
2496             PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2497             PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
2498             PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
2499             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2500             ])
2501
2502     def _handle_simple_method_bytes_decode(self, node, args, is_unbound_method):
2503         """Replace char*.decode() by a direct C-API call to the
2504         corresponding codec, possibly resoving a slice on the char*.
2505         """
2506         if len(args) < 1 or len(args) > 3:
2507             self._error_wrong_arg_count('bytes.decode', node, args, '1-3')
2508             return node
2509         temps = []
2510         if isinstance(args[0], ExprNodes.SliceIndexNode):
2511             index_node = args[0]
2512             string_node = index_node.base
2513             if not string_node.type.is_string:
2514                 # nothing to optimise here
2515                 return node
2516             start, stop = index_node.start, index_node.stop
2517             if not start or start.constant_result == 0:
2518                 start = None
2519             else:
2520                 if start.type.is_pyobject:
2521                     start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2522                 if stop:
2523                     start = UtilNodes.LetRefNode(start)
2524                     temps.append(start)
2525                 string_node = ExprNodes.AddNode(pos=start.pos,
2526                                                 operand1=string_node,
2527                                                 operator='+',
2528                                                 operand2=start,
2529                                                 is_temp=False,
2530                                                 type=string_node.type
2531                                                 )
2532             if stop and stop.type.is_pyobject:
2533                 stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2534         elif isinstance(args[0], ExprNodes.CoerceToPyTypeNode) \
2535                  and args[0].arg.type.is_string:
2536             # use strlen() to find the string length, just as CPython would
2537             start = stop = None
2538             string_node = args[0].arg
2539         else:
2540             # let Python do its job
2541             return node
2542
2543         if not stop:
2544             if start or not string_node.is_name:
2545                 string_node = UtilNodes.LetRefNode(string_node)
2546                 temps.append(string_node)
2547             stop = ExprNodes.PythonCapiCallNode(
2548                 string_node.pos, "strlen", self.Pyx_strlen_func_type,
2549                     args = [string_node],
2550                     is_temp = False,
2551                     utility_code = Builtin.include_string_h_utility_code,
2552                     ).coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2553         elif start:
2554             stop = ExprNodes.SubNode(
2555                 pos = stop.pos,
2556                 operand1 = stop,
2557                 operator = '-',
2558                 operand2 = start,
2559                 is_temp = False,
2560                 type = PyrexTypes.c_py_ssize_t_type
2561                 )
2562
2563         parameters = self._unpack_encoding_and_error_mode(node.pos, args)
2564         if parameters is None:
2565             return node
2566         encoding, encoding_node, error_handling, error_handling_node = parameters
2567
2568         # try to find a specific encoder function
2569         codec_name = None
2570         if encoding is not None:
2571             codec_name = self._find_special_codec_name(encoding)
2572         if codec_name is not None:
2573             decode_function = "PyUnicode_Decode%s" % codec_name
2574             node = ExprNodes.PythonCapiCallNode(
2575                 node.pos, decode_function,
2576                 self.PyUnicode_DecodeXyz_func_type,
2577                 args = [string_node, stop, error_handling_node],
2578                 is_temp = node.is_temp,
2579                 )
2580         else:
2581             node = ExprNodes.PythonCapiCallNode(
2582                 node.pos, "PyUnicode_Decode",
2583                 self.PyUnicode_Decode_func_type,
2584                 args = [string_node, stop, encoding_node, error_handling_node],
2585                 is_temp = node.is_temp,
2586                 )
2587
2588         for temp in temps[::-1]:
2589             node = UtilNodes.EvalWithTempExprNode(temp, node)
2590         return node
2591
2592     def _find_special_codec_name(self, encoding):
2593         try:
2594             requested_codec = codecs.getencoder(encoding)
2595         except:
2596             return None
2597         for name, codec in self._special_codecs:
2598             if codec == requested_codec:
2599                 if '_' in name:
2600                     name = ''.join([ s.capitalize()
2601                                      for s in name.split('_')])
2602                 return name
2603         return None
2604
2605     def _unpack_encoding_and_error_mode(self, pos, args):
2606         null_node = ExprNodes.NullNode(pos)
2607
2608         if len(args) >= 2:
2609             encoding_node = args[1]
2610             if isinstance(encoding_node, ExprNodes.CoerceToPyTypeNode):
2611                 encoding_node = encoding_node.arg
2612             if isinstance(encoding_node, (ExprNodes.UnicodeNode, ExprNodes.StringNode,
2613                                           ExprNodes.BytesNode)):
2614                 encoding = encoding_node.value
2615                 encoding_node = ExprNodes.BytesNode(encoding_node.pos, value=encoding,
2616                                                      type=PyrexTypes.c_char_ptr_type)
2617             elif encoding_node.type is Builtin.bytes_type:
2618                 encoding = None
2619                 encoding_node = encoding_node.coerce_to(
2620                     PyrexTypes.c_char_ptr_type, self.current_env())
2621             elif encoding_node.type.is_string:
2622                 encoding = None
2623             else:
2624                 return None
2625         else:
2626             encoding = None
2627             encoding_node = null_node
2628
2629         if len(args) == 3:
2630             error_handling_node = args[2]
2631             if isinstance(error_handling_node, ExprNodes.CoerceToPyTypeNode):
2632                 error_handling_node = error_handling_node.arg
2633             if isinstance(error_handling_node,
2634                           (ExprNodes.UnicodeNode, ExprNodes.StringNode,
2635                            ExprNodes.BytesNode)):
2636                 error_handling = error_handling_node.value
2637                 if error_handling == 'strict':
2638                     error_handling_node = null_node
2639                 else:
2640                     error_handling_node = ExprNodes.BytesNode(
2641                         error_handling_node.pos, value=error_handling,
2642                         type=PyrexTypes.c_char_ptr_type)
2643             elif error_handling_node.type is Builtin.bytes_type:
2644                 error_handling = None
2645                 error_handling_node = error_handling_node.coerce_to(
2646                     PyrexTypes.c_char_ptr_type, self.current_env())
2647             elif error_handling_node.type.is_string:
2648                 error_handling = None
2649             else:
2650                 return None
2651         else:
2652             error_handling = 'strict'
2653             error_handling_node = null_node
2654
2655         return (encoding, encoding_node, error_handling, error_handling_node)
2656
2657
2658     ### helpers
2659
2660     def _substitute_method_call(self, node, name, func_type,
2661                                 attr_name, is_unbound_method, args=(),
2662                                 utility_code=None,
2663                                 may_return_none=ExprNodes.PythonCapiCallNode.may_return_none):
2664         args = list(args)
2665         if args and not args[0].is_literal:
2666             self_arg = args[0]
2667             if is_unbound_method:
2668                 self_arg = self_arg.as_none_safe_node(
2669                     "descriptor '%s' requires a '%s' object but received a 'NoneType'" % (
2670                         attr_name, node.function.obj.name))
2671             else:
2672                 self_arg = self_arg.as_none_safe_node(
2673                     "'NoneType' object has no attribute '%s'" % attr_name,
2674                     error = "PyExc_AttributeError")
2675             args[0] = self_arg
2676         return ExprNodes.PythonCapiCallNode(
2677             node.pos, name, func_type,
2678             args = args,
2679             is_temp = node.is_temp,
2680             utility_code = utility_code,
2681             may_return_none = may_return_none,
2682             )
2683
2684     def _inject_int_default_argument(self, node, args, arg_index, type, default_value):
2685         assert len(args) >= arg_index
2686         if len(args) == arg_index:
2687             args.append(ExprNodes.IntNode(node.pos, value=str(default_value),
2688                                           type=type, constant_result=default_value))
2689         else:
2690             args[arg_index] = args[arg_index].coerce_to(type, self.current_env())
2691
2692     def _inject_bint_default_argument(self, node, args, arg_index, default_value):
2693         assert len(args) >= arg_index
2694         if len(args) == arg_index:
2695             default_value = bool(default_value)
2696             args.append(ExprNodes.BoolNode(node.pos, value=default_value,
2697                                            constant_result=default_value))
2698         else:
2699             args[arg_index] = args[arg_index].coerce_to_boolean(self.current_env())
2700
2701
2702 py_unicode_istitle_utility_code = UtilityCode(
2703 # Py_UNICODE_ISTITLE() doesn't match unicode.istitle() as the latter
2704 # additionally allows character that comply with Py_UNICODE_ISUPPER()
2705 proto = '''
2706 #if PY_VERSION_HEX < 0x030200A2
2707 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar); /* proto */
2708 #else
2709 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UCS4 uchar); /* proto */
2710 #endif
2711 ''',
2712 impl = '''
2713 #if PY_VERSION_HEX < 0x030200A2
2714 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar) {
2715 #else
2716 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UCS4 uchar) {
2717 #endif
2718     return Py_UNICODE_ISTITLE(uchar) || Py_UNICODE_ISUPPER(uchar);
2719 }
2720 ''')
2721
2722 unicode_tailmatch_utility_code = UtilityCode(
2723     # Python's unicode.startswith() and unicode.endswith() support a
2724     # tuple of prefixes/suffixes, whereas it's much more common to
2725     # test for a single unicode string.
2726 proto = '''
2727 static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr, \
2728 Py_ssize_t start, Py_ssize_t end, int direction);
2729 ''',
2730 impl = '''
2731 static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr,
2732                                      Py_ssize_t start, Py_ssize_t end, int direction) {
2733     if (unlikely(PyTuple_Check(substr))) {
2734         int result;
2735         Py_ssize_t i;
2736         for (i = 0; i < PyTuple_GET_SIZE(substr); i++) {
2737             result = PyUnicode_Tailmatch(s, PyTuple_GET_ITEM(substr, i),
2738                                          start, end, direction);
2739             if (result) {
2740                 return result;
2741             }
2742         }
2743         return 0;
2744     }
2745     return PyUnicode_Tailmatch(s, substr, start, end, direction);
2746 }
2747 ''',
2748 )
2749
2750 dict_getitem_default_utility_code = UtilityCode(
2751 proto = '''
2752 static PyObject* __Pyx_PyDict_GetItemDefault(PyObject* d, PyObject* key, PyObject* default_value) {
2753     PyObject* value;
2754 #if PY_MAJOR_VERSION >= 3
2755     value = PyDict_GetItemWithError(d, key);
2756     if (unlikely(!value)) {
2757         if (unlikely(PyErr_Occurred()))
2758             return NULL;
2759         value = default_value;
2760     }
2761     Py_INCREF(value);
2762 #else
2763     if (PyString_CheckExact(key) || PyUnicode_CheckExact(key) || PyInt_CheckExact(key)) {
2764         /* these presumably have safe hash functions */
2765         value = PyDict_GetItem(d, key);
2766         if (unlikely(!value)) {
2767             value = default_value;
2768         }
2769         Py_INCREF(value);
2770     } else {
2771         PyObject *m;
2772         m = __Pyx_GetAttrString(d, "get");
2773         if (!m) return NULL;
2774         value = PyObject_CallFunctionObjArgs(m, key,
2775             (default_value == Py_None) ? NULL : default_value, NULL);
2776         Py_DECREF(m);
2777     }
2778 #endif
2779     return value;
2780 }
2781 ''',
2782 impl = ""
2783 )
2784
2785 append_utility_code = UtilityCode(
2786 proto = """
2787 static CYTHON_INLINE PyObject* __Pyx_PyObject_Append(PyObject* L, PyObject* x) {
2788     if (likely(PyList_CheckExact(L))) {
2789         if (PyList_Append(L, x) < 0) return NULL;
2790         Py_INCREF(Py_None);
2791         return Py_None; /* this is just to have an accurate signature */
2792     }
2793     else {
2794         PyObject *r, *m;
2795         m = __Pyx_GetAttrString(L, "append");
2796         if (!m) return NULL;
2797         r = PyObject_CallFunctionObjArgs(m, x, NULL);
2798         Py_DECREF(m);
2799         return r;
2800     }
2801 }
2802 """,
2803 impl = ""
2804 )
2805
2806
2807 pop_utility_code = UtilityCode(
2808 proto = """
2809 static CYTHON_INLINE PyObject* __Pyx_PyObject_Pop(PyObject* L) {
2810     PyObject *r, *m;
2811 #if PY_VERSION_HEX >= 0x02040000
2812     if (likely(PyList_CheckExact(L))
2813             /* Check that both the size is positive and no reallocation shrinking needs to be done. */
2814             && likely(PyList_GET_SIZE(L) > (((PyListObject*)L)->allocated >> 1))) {
2815         Py_SIZE(L) -= 1;
2816         return PyList_GET_ITEM(L, PyList_GET_SIZE(L));
2817     }
2818 #endif
2819     m = __Pyx_GetAttrString(L, "pop");
2820     if (!m) return NULL;
2821     r = PyObject_CallObject(m, NULL);
2822     Py_DECREF(m);
2823     return r;
2824 }
2825 """,
2826 impl = ""
2827 )
2828
2829 pop_index_utility_code = UtilityCode(
2830 proto = """
2831 static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix);
2832 """,
2833 impl = """
2834 static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix) {
2835     PyObject *r, *m, *t, *py_ix;
2836 #if PY_VERSION_HEX >= 0x02040000
2837     if (likely(PyList_CheckExact(L))) {
2838         Py_ssize_t size = PyList_GET_SIZE(L);
2839         if (likely(size > (((PyListObject*)L)->allocated >> 1))) {
2840             if (ix < 0) {
2841                 ix += size;
2842             }
2843             if (likely(0 <= ix && ix < size)) {
2844                 Py_ssize_t i;
2845                 PyObject* v = PyList_GET_ITEM(L, ix);
2846                 Py_SIZE(L) -= 1;
2847                 size -= 1;
2848                 for(i=ix; i<size; i++) {
2849                     PyList_SET_ITEM(L, i, PyList_GET_ITEM(L, i+1));
2850                 }
2851                 return v;
2852             }
2853         }
2854     }
2855 #endif
2856     py_ix = t = NULL;
2857     m = __Pyx_GetAttrString(L, "pop");
2858     if (!m) goto bad;
2859     py_ix = PyInt_FromSsize_t(ix);
2860     if (!py_ix) goto bad;
2861     t = PyTuple_New(1);
2862     if (!t) goto bad;
2863     PyTuple_SET_ITEM(t, 0, py_ix);
2864     py_ix = NULL;
2865     r = PyObject_CallObject(m, t);
2866     Py_DECREF(m);
2867     Py_DECREF(t);
2868     return r;
2869 bad:
2870     Py_XDECREF(m);
2871     Py_XDECREF(t);
2872     Py_XDECREF(py_ix);
2873     return NULL;
2874 }
2875 """
2876 )
2877
2878
2879 pyobject_as_double_utility_code = UtilityCode(
2880 proto = '''
2881 static double __Pyx__PyObject_AsDouble(PyObject* obj); /* proto */
2882
2883 #define __Pyx_PyObject_AsDouble(obj) \\
2884     ((likely(PyFloat_CheckExact(obj))) ? \\
2885      PyFloat_AS_DOUBLE(obj) : __Pyx__PyObject_AsDouble(obj))
2886 ''',
2887 impl='''
2888 static double __Pyx__PyObject_AsDouble(PyObject* obj) {
2889     PyObject* float_value;
2890     if (Py_TYPE(obj)->tp_as_number && Py_TYPE(obj)->tp_as_number->nb_float) {
2891         return PyFloat_AsDouble(obj);
2892     } else if (PyUnicode_CheckExact(obj) || PyBytes_CheckExact(obj)) {
2893 #if PY_MAJOR_VERSION >= 3
2894         float_value = PyFloat_FromString(obj);
2895 #else
2896         float_value = PyFloat_FromString(obj, 0);
2897 #endif
2898     } else {
2899         PyObject* args = PyTuple_New(1);
2900         if (unlikely(!args)) goto bad;
2901         PyTuple_SET_ITEM(args, 0, obj);
2902         float_value = PyObject_Call((PyObject*)&PyFloat_Type, args, 0);
2903         PyTuple_SET_ITEM(args, 0, 0);
2904         Py_DECREF(args);
2905     }
2906     if (likely(float_value)) {
2907         double value = PyFloat_AS_DOUBLE(float_value);
2908         Py_DECREF(float_value);
2909         return value;
2910     }
2911 bad:
2912     return (double)-1;
2913 }
2914 '''
2915 )
2916
2917
2918 bytes_index_utility_code = UtilityCode(
2919 proto = """
2920 static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* unicode, Py_ssize_t index, int check_bounds); /* proto */
2921 """,
2922 impl = """
2923 static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* bytes, Py_ssize_t index, int check_bounds) {
2924     if (check_bounds) {
2925         if (unlikely(index >= PyBytes_GET_SIZE(bytes)) |
2926             ((index < 0) & unlikely(index < -PyBytes_GET_SIZE(bytes)))) {
2927             PyErr_Format(PyExc_IndexError, "string index out of range");
2928             return -1;
2929         }
2930     }
2931     if (index < 0)
2932         index += PyBytes_GET_SIZE(bytes);
2933     return PyBytes_AS_STRING(bytes)[index];
2934 }
2935 """
2936 )
2937
2938
2939 tpnew_utility_code = UtilityCode(
2940 proto = """
2941 static CYTHON_INLINE PyObject* __Pyx_tp_new(PyObject* type_obj) {
2942     return (PyObject*) (((PyTypeObject*)(type_obj))->tp_new(
2943         (PyTypeObject*)(type_obj), %(TUPLE)s, NULL));
2944 }
2945 """ % {'TUPLE' : Naming.empty_tuple}
2946 )
2947
2948
2949 class ConstantFolding(Visitor.VisitorTransform, SkipDeclarations):
2950     """Calculate the result of constant expressions to store it in
2951     ``expr_node.constant_result``, and replace trivial cases by their
2952     constant result.
2953
2954     General rules:
2955
2956     - We calculate float constants to make them available to the
2957       compiler, but we do not aggregate them into a single literal
2958       node to prevent any loss of precision.
2959
2960     - We recursively calculate constants from non-literal nodes to
2961       make them available to the compiler, but we only aggregate
2962       literal nodes at each step.  Non-literal nodes are never merged
2963       into a single node.
2964     """
2965     def _calculate_const(self, node):
2966         if node.constant_result is not ExprNodes.constant_value_not_set:
2967             return
2968
2969         # make sure we always set the value
2970         not_a_constant = ExprNodes.not_a_constant
2971         node.constant_result = not_a_constant
2972
2973         # check if all children are constant
2974         children = self.visitchildren(node)
2975         for child_result in children.values():
2976             if type(child_result) is list:
2977                 for child in child_result:
2978                     if getattr(child, 'constant_result', not_a_constant) is not_a_constant:
2979                         return
2980             elif getattr(child_result, 'constant_result', not_a_constant) is not_a_constant:
2981                 return
2982
2983         # now try to calculate the real constant value
2984         try:
2985             node.calculate_constant_result()
2986 #            if node.constant_result is not ExprNodes.not_a_constant:
2987 #                print node.__class__.__name__, node.constant_result
2988         except (ValueError, TypeError, KeyError, IndexError, AttributeError, ArithmeticError):
2989             # ignore all 'normal' errors here => no constant result
2990             pass
2991         except Exception:
2992             # this looks like a real error
2993             import traceback, sys
2994             traceback.print_exc(file=sys.stdout)
2995
2996     NODE_TYPE_ORDER = [ExprNodes.CharNode, ExprNodes.IntNode,
2997                        ExprNodes.LongNode, ExprNodes.FloatNode]
2998
2999     def _widest_node_class(self, *nodes):
3000         try:
3001             return self.NODE_TYPE_ORDER[
3002                 max(map(self.NODE_TYPE_ORDER.index, map(type, nodes)))]
3003         except ValueError:
3004             return None
3005
3006     def visit_ExprNode(self, node):
3007         self._calculate_const(node)
3008         return node
3009
3010     def visit_UnopNode(self, node):
3011         self._calculate_const(node)
3012         if node.constant_result is ExprNodes.not_a_constant:
3013             return node
3014         if not node.operand.is_literal:
3015             return node
3016         if isinstance(node.operand, ExprNodes.BoolNode):
3017             return ExprNodes.IntNode(node.pos, value = str(node.constant_result),
3018                                      type = PyrexTypes.c_int_type,
3019                                      constant_result = node.constant_result)
3020         if node.operator == '+':
3021             return self._handle_UnaryPlusNode(node)
3022         elif node.operator == '-':
3023             return self._handle_UnaryMinusNode(node)
3024         return node
3025
3026     def _handle_UnaryMinusNode(self, node):
3027         if isinstance(node.operand, ExprNodes.LongNode):
3028             return ExprNodes.LongNode(node.pos, value = '-' + node.operand.value,
3029                                       constant_result = node.constant_result)
3030         if isinstance(node.operand, ExprNodes.FloatNode):
3031             # this is a safe operation
3032             return ExprNodes.FloatNode(node.pos, value = '-' + node.operand.value,
3033                                        constant_result = node.constant_result)
3034         node_type = node.operand.type
3035         if node_type.is_int and node_type.signed or \
3036                isinstance(node.operand, ExprNodes.IntNode) and node_type.is_pyobject:
3037             return ExprNodes.IntNode(node.pos, value = '-' + node.operand.value,
3038                                      type = node_type,
3039                                      longness = node.operand.longness,
3040                                      constant_result = node.constant_result)
3041         return node
3042
3043     def _handle_UnaryPlusNode(self, node):
3044         if node.constant_result == node.operand.constant_result:
3045             return node.operand
3046         return node
3047
3048     def visit_BoolBinopNode(self, node):
3049         self._calculate_const(node)
3050         if node.constant_result is ExprNodes.not_a_constant:
3051             return node
3052         if not node.operand1.is_literal or not node.operand2.is_literal:
3053             return node
3054
3055         if node.constant_result == node.operand1.constant_result and node.operand1.is_literal:
3056             return node.operand1
3057         elif node.constant_result == node.operand2.constant_result and node.operand2.is_literal:
3058             return node.operand2
3059         else:
3060             # FIXME: we could do more ...
3061             return node
3062
3063     def visit_BinopNode(self, node):
3064         self._calculate_const(node)
3065         if node.constant_result is ExprNodes.not_a_constant:
3066             return node
3067         if isinstance(node.constant_result, float):
3068             return node
3069         operand1, operand2 = node.operand1, node.operand2
3070         if not operand1.is_literal or not operand2.is_literal:
3071             return node
3072
3073         # now inject a new constant node with the calculated value
3074         try:
3075             type1, type2 = operand1.type, operand2.type
3076             if type1 is None or type2 is None:
3077                 return node
3078         except AttributeError:
3079             return node
3080
3081         if type1.is_numeric and type2.is_numeric:
3082             widest_type = PyrexTypes.widest_numeric_type(type1, type2)
3083         else:
3084             widest_type = PyrexTypes.py_object_type
3085         target_class = self._widest_node_class(operand1, operand2)
3086         if target_class is None:
3087             return node
3088         elif target_class is ExprNodes.IntNode:
3089             unsigned = getattr(operand1, 'unsigned', '') and \
3090                        getattr(operand2, 'unsigned', '')
3091             longness = "LL"[:max(len(getattr(operand1, 'longness', '')),
3092                                  len(getattr(operand2, 'longness', '')))]
3093             new_node = ExprNodes.IntNode(pos=node.pos,
3094                                          unsigned = unsigned, longness = longness,
3095                                          value = str(node.constant_result),
3096                                          constant_result = node.constant_result)
3097             # IntNode is smart about the type it chooses, so we just
3098             # make sure we were not smarter this time
3099             if widest_type.is_pyobject or new_node.type.is_pyobject:
3100                 new_node.type = PyrexTypes.py_object_type
3101             else:
3102                 new_node.type = PyrexTypes.widest_numeric_type(widest_type, new_node.type)
3103         else:
3104             if isinstance(node, ExprNodes.BoolNode):
3105                 node_value = node.constant_result
3106             else:
3107                 node_value = str(node.constant_result)
3108             new_node = target_class(pos=node.pos, type = widest_type,
3109                                     value = node_value,
3110                                     constant_result = node.constant_result)
3111         return new_node
3112
3113     def visit_PrimaryCmpNode(self, node):
3114         self._calculate_const(node)
3115         if node.constant_result is ExprNodes.not_a_constant:
3116             return node
3117         bool_result = bool(node.constant_result)
3118         return ExprNodes.BoolNode(node.pos, value=bool_result,
3119                                   constant_result=bool_result)
3120
3121     def visit_IfStatNode(self, node):
3122         self.visitchildren(node)
3123         # eliminate dead code based on constant condition results
3124         if_clauses = []
3125         for if_clause in node.if_clauses:
3126             condition_result = if_clause.get_constant_condition_result()
3127             if condition_result is None:
3128                 # unknown result => normal runtime evaluation
3129                 if_clauses.append(if_clause)
3130             elif condition_result == True:
3131                 # subsequent clauses can safely be dropped
3132                 node.else_clause = if_clause.body
3133                 break
3134             else:
3135                 assert condition_result == False
3136         if not if_clauses:
3137             return node.else_clause
3138         node.if_clauses = if_clauses
3139         return node
3140
3141     # in the future, other nodes can have their own handler method here
3142     # that can replace them with a constant result node
3143
3144     visit_Node = Visitor.VisitorTransform.recurse_to_children
3145
3146
3147 class FinalOptimizePhase(Visitor.CythonTransform):
3148     """
3149     This visitor handles several commuting optimizations, and is run
3150     just before the C code generation phase.
3151
3152     The optimizations currently implemented in this class are:
3153         - eliminate None assignment and refcounting for first assignment.
3154         - isinstance -> typecheck for cdef types
3155         - eliminate checks for None and/or types that became redundant after tree changes
3156     """
3157     def visit_SingleAssignmentNode(self, node):
3158         """Avoid redundant initialisation of local variables before their
3159         first assignment.
3160         """
3161         self.visitchildren(node)
3162         if node.first:
3163             lhs = node.lhs
3164             lhs.lhs_of_first_assignment = True
3165             if isinstance(lhs, ExprNodes.NameNode) and lhs.entry.type.is_pyobject:
3166                 # Have variable initialized to 0 rather than None
3167                 lhs.entry.init_to_none = False
3168                 lhs.entry.init = 0
3169         return node
3170
3171     def visit_SimpleCallNode(self, node):
3172         """Replace generic calls to isinstance(x, type) by a more efficient
3173         type check.
3174         """
3175         self.visitchildren(node)
3176         if node.function.type.is_cfunction and isinstance(node.function, ExprNodes.NameNode):
3177             if node.function.name == 'isinstance':
3178                 type_arg = node.args[1]
3179                 if type_arg.type.is_builtin_type and type_arg.type.name == 'type':
3180                     from CythonScope import utility_scope
3181                     node.function.entry = utility_scope.lookup('PyObject_TypeCheck')
3182                     node.function.type = node.function.entry.type
3183                     PyTypeObjectPtr = PyrexTypes.CPtrType(utility_scope.lookup('PyTypeObject').type)
3184                     node.args[1] = ExprNodes.CastNode(node.args[1], PyTypeObjectPtr)
3185         return node
3186
3187     def visit_PyTypeTestNode(self, node):
3188         """Remove tests for alternatively allowed None values from
3189         type tests when we know that the argument cannot be None
3190         anyway.
3191         """
3192         self.visitchildren(node)
3193         if not node.notnone:
3194             if not node.arg.may_be_none():
3195                 node.notnone = True
3196         return node