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 PyrexTypes.c_py_unicode_type:
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                 type_check_args = [arg]
1999             elif test_type_node.type is Builtin.type_type:
2000                 type_check_function = '__Pyx_TypeCheck'
2001                 type_check_args = [arg, test_type_node]
2002             else:
2003                 return node
2004             if type_check_function not in tests:
2005                 tests.append(type_check_function)
2006                 test_nodes.append(
2007                     ExprNodes.PythonCapiCallNode(
2008                         test_type_node.pos, type_check_function, self.Py_type_check_func_type,
2009                         args = type_check_args,
2010                         is_temp = True,
2011                         ))
2012
2013         def join_with_or(a,b, make_binop_node=ExprNodes.binop_node):
2014             or_node = make_binop_node(node.pos, 'or', a, b)
2015             or_node.type = PyrexTypes.c_bint_type
2016             or_node.is_temp = True
2017             return or_node
2018
2019         test_node = reduce(join_with_or, test_nodes).coerce_to(node.type, env)
2020         if temp is not None:
2021             test_node = UtilNodes.EvalWithTempExprNode(temp, test_node)
2022         return test_node
2023
2024     def _handle_simple_function_ord(self, node, pos_args):
2025         """Unpack ord(Py_UNICODE).
2026         """
2027         if len(pos_args) != 1:
2028             return node
2029         arg = pos_args[0]
2030         if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
2031             if arg.arg.type is PyrexTypes.c_py_unicode_type:
2032                 return arg.arg.coerce_to(node.type, self.current_env())
2033         return node
2034
2035     ### special methods
2036
2037     Pyx_tp_new_func_type = PyrexTypes.CFuncType(
2038         PyrexTypes.py_object_type, [
2039             PyrexTypes.CFuncTypeArg("type", Builtin.type_type, None)
2040             ])
2041
2042     def _handle_simple_slot__new__(self, node, args, is_unbound_method):
2043         """Replace 'exttype.__new__(exttype)' by a call to exttype->tp_new()
2044         """
2045         obj = node.function.obj
2046         if not is_unbound_method or len(args) != 1:
2047             return node
2048         type_arg = args[0]
2049         if not obj.is_name or not type_arg.is_name:
2050             # play safe
2051             return node
2052         if obj.type != Builtin.type_type or type_arg.type != Builtin.type_type:
2053             # not a known type, play safe
2054             return node
2055         if not type_arg.type_entry or not obj.type_entry:
2056             if obj.name != type_arg.name:
2057                 return node
2058             # otherwise, we know it's a type and we know it's the same
2059             # type for both - that should do
2060         elif type_arg.type_entry != obj.type_entry:
2061             # different types - may or may not lead to an error at runtime
2062             return node
2063
2064         # FIXME: we could potentially look up the actual tp_new C
2065         # method of the extension type and call that instead of the
2066         # generic slot. That would also allow us to pass parameters
2067         # efficiently.
2068
2069         if not type_arg.type_entry:
2070             # arbitrary variable, needs a None check for safety
2071             type_arg = type_arg.as_none_safe_node(
2072                 "object.__new__(X): X is not a type object (NoneType)")
2073
2074         return ExprNodes.PythonCapiCallNode(
2075             node.pos, "__Pyx_tp_new", self.Pyx_tp_new_func_type,
2076             args = [type_arg],
2077             utility_code = tpnew_utility_code,
2078             is_temp = node.is_temp
2079             )
2080
2081     ### methods of builtin types
2082
2083     PyObject_Append_func_type = PyrexTypes.CFuncType(
2084         PyrexTypes.py_object_type, [
2085             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2086             PyrexTypes.CFuncTypeArg("item", PyrexTypes.py_object_type, None),
2087             ])
2088
2089     def _handle_simple_method_object_append(self, node, args, is_unbound_method):
2090         """Optimistic optimisation as X.append() is almost always
2091         referring to a list.
2092         """
2093         if len(args) != 2:
2094             return node
2095
2096         return ExprNodes.PythonCapiCallNode(
2097             node.pos, "__Pyx_PyObject_Append", self.PyObject_Append_func_type,
2098             args = args,
2099             may_return_none = True,
2100             is_temp = node.is_temp,
2101             utility_code = append_utility_code
2102             )
2103
2104     PyObject_Pop_func_type = PyrexTypes.CFuncType(
2105         PyrexTypes.py_object_type, [
2106             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2107             ])
2108
2109     PyObject_PopIndex_func_type = PyrexTypes.CFuncType(
2110         PyrexTypes.py_object_type, [
2111             PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
2112             PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_long_type, None),
2113             ])
2114
2115     def _handle_simple_method_object_pop(self, node, args, is_unbound_method):
2116         """Optimistic optimisation as X.pop([n]) is almost always
2117         referring to a list.
2118         """
2119         if len(args) == 1:
2120             return ExprNodes.PythonCapiCallNode(
2121                 node.pos, "__Pyx_PyObject_Pop", self.PyObject_Pop_func_type,
2122                 args = args,
2123                 may_return_none = True,
2124                 is_temp = node.is_temp,
2125                 utility_code = pop_utility_code
2126                 )
2127         elif len(args) == 2:
2128             if isinstance(args[1], ExprNodes.CoerceToPyTypeNode) and args[1].arg.type.is_int:
2129                 original_type = args[1].arg.type
2130                 if PyrexTypes.widest_numeric_type(original_type, PyrexTypes.c_py_ssize_t_type) == PyrexTypes.c_py_ssize_t_type:
2131                     args[1] = args[1].arg
2132                     return ExprNodes.PythonCapiCallNode(
2133                         node.pos, "__Pyx_PyObject_PopIndex", self.PyObject_PopIndex_func_type,
2134                         args = args,
2135                         may_return_none = True,
2136                         is_temp = node.is_temp,
2137                         utility_code = pop_index_utility_code
2138                         )
2139
2140         return node
2141
2142     _handle_simple_method_list_pop = _handle_simple_method_object_pop
2143
2144     single_param_func_type = PyrexTypes.CFuncType(
2145         PyrexTypes.c_int_type, [
2146             PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
2147             ],
2148         exception_value = "-1")
2149
2150     def _handle_simple_method_list_sort(self, node, args, is_unbound_method):
2151         """Call PyList_Sort() instead of the 0-argument l.sort().
2152         """
2153         if len(args) != 1:
2154             return node
2155         return self._substitute_method_call(
2156             node, "PyList_Sort", self.single_param_func_type,
2157             'sort', is_unbound_method, args)
2158
2159     Pyx_PyDict_GetItem_func_type = PyrexTypes.CFuncType(
2160         PyrexTypes.py_object_type, [
2161             PyrexTypes.CFuncTypeArg("dict", PyrexTypes.py_object_type, None),
2162             PyrexTypes.CFuncTypeArg("key", PyrexTypes.py_object_type, None),
2163             PyrexTypes.CFuncTypeArg("default", PyrexTypes.py_object_type, None),
2164             ])
2165
2166     def _handle_simple_method_dict_get(self, node, args, is_unbound_method):
2167         """Replace dict.get() by a call to PyDict_GetItem().
2168         """
2169         if len(args) == 2:
2170             args.append(ExprNodes.NoneNode(node.pos))
2171         elif len(args) != 3:
2172             self._error_wrong_arg_count('dict.get', node, args, "2 or 3")
2173             return node
2174
2175         return self._substitute_method_call(
2176             node, "__Pyx_PyDict_GetItemDefault", self.Pyx_PyDict_GetItem_func_type,
2177             'get', is_unbound_method, args,
2178             may_return_none = True,
2179             utility_code = dict_getitem_default_utility_code)
2180
2181
2182     ### unicode type methods
2183
2184     PyUnicode_uchar_predicate_func_type = PyrexTypes.CFuncType(
2185         PyrexTypes.c_bint_type, [
2186             PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_unicode_type, None),
2187             ])
2188
2189     def _inject_unicode_predicate(self, node, args, is_unbound_method):
2190         if is_unbound_method or len(args) != 1:
2191             return node
2192         ustring = args[0]
2193         if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
2194                ustring.arg.type is not PyrexTypes.c_py_unicode_type:
2195             return node
2196         uchar = ustring.arg
2197         method_name = node.function.attribute
2198         if method_name == 'istitle':
2199             # istitle() doesn't directly map to Py_UNICODE_ISTITLE()
2200             utility_code = py_unicode_istitle_utility_code
2201             function_name = '__Pyx_Py_UNICODE_ISTITLE'
2202         else:
2203             utility_code = None
2204             function_name = 'Py_UNICODE_%s' % method_name.upper()
2205         func_call = self._substitute_method_call(
2206             node, function_name, self.PyUnicode_uchar_predicate_func_type,
2207             method_name, is_unbound_method, [uchar],
2208             utility_code = utility_code)
2209         if node.type.is_pyobject:
2210             func_call = func_call.coerce_to_pyobject(self.current_env)
2211         return func_call
2212
2213     _handle_simple_method_unicode_isalnum   = _inject_unicode_predicate
2214     _handle_simple_method_unicode_isalpha   = _inject_unicode_predicate
2215     _handle_simple_method_unicode_isdecimal = _inject_unicode_predicate
2216     _handle_simple_method_unicode_isdigit   = _inject_unicode_predicate
2217     _handle_simple_method_unicode_islower   = _inject_unicode_predicate
2218     _handle_simple_method_unicode_isnumeric = _inject_unicode_predicate
2219     _handle_simple_method_unicode_isspace   = _inject_unicode_predicate
2220     _handle_simple_method_unicode_istitle   = _inject_unicode_predicate
2221     _handle_simple_method_unicode_isupper   = _inject_unicode_predicate
2222
2223     PyUnicode_uchar_conversion_func_type = PyrexTypes.CFuncType(
2224         PyrexTypes.c_py_unicode_type, [
2225             PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_unicode_type, None),
2226             ])
2227
2228     def _inject_unicode_character_conversion(self, node, args, is_unbound_method):
2229         if is_unbound_method or len(args) != 1:
2230             return node
2231         ustring = args[0]
2232         if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
2233                ustring.arg.type is not PyrexTypes.c_py_unicode_type:
2234             return node
2235         uchar = ustring.arg
2236         method_name = node.function.attribute
2237         function_name = 'Py_UNICODE_TO%s' % method_name.upper()
2238         func_call = self._substitute_method_call(
2239             node, function_name, self.PyUnicode_uchar_conversion_func_type,
2240             method_name, is_unbound_method, [uchar])
2241         if node.type.is_pyobject:
2242             func_call = func_call.coerce_to_pyobject(self.current_env)
2243         return func_call
2244
2245     _handle_simple_method_unicode_lower = _inject_unicode_character_conversion
2246     _handle_simple_method_unicode_upper = _inject_unicode_character_conversion
2247     _handle_simple_method_unicode_title = _inject_unicode_character_conversion
2248
2249     PyUnicode_Splitlines_func_type = PyrexTypes.CFuncType(
2250         Builtin.list_type, [
2251             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2252             PyrexTypes.CFuncTypeArg("keepends", PyrexTypes.c_bint_type, None),
2253             ])
2254
2255     def _handle_simple_method_unicode_splitlines(self, node, args, is_unbound_method):
2256         """Replace unicode.splitlines(...) by a direct call to the
2257         corresponding C-API function.
2258         """
2259         if len(args) not in (1,2):
2260             self._error_wrong_arg_count('unicode.splitlines', node, args, "1 or 2")
2261             return node
2262         self._inject_bint_default_argument(node, args, 1, False)
2263
2264         return self._substitute_method_call(
2265             node, "PyUnicode_Splitlines", self.PyUnicode_Splitlines_func_type,
2266             'splitlines', is_unbound_method, args)
2267
2268     PyUnicode_Split_func_type = PyrexTypes.CFuncType(
2269         Builtin.list_type, [
2270             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2271             PyrexTypes.CFuncTypeArg("sep", PyrexTypes.py_object_type, None),
2272             PyrexTypes.CFuncTypeArg("maxsplit", PyrexTypes.c_py_ssize_t_type, None),
2273             ]
2274         )
2275
2276     def _handle_simple_method_unicode_split(self, node, args, is_unbound_method):
2277         """Replace unicode.split(...) by a direct call to the
2278         corresponding C-API function.
2279         """
2280         if len(args) not in (1,2,3):
2281             self._error_wrong_arg_count('unicode.split', node, args, "1-3")
2282             return node
2283         if len(args) < 2:
2284             args.append(ExprNodes.NullNode(node.pos))
2285         self._inject_int_default_argument(
2286             node, args, 2, PyrexTypes.c_py_ssize_t_type, "-1")
2287
2288         return self._substitute_method_call(
2289             node, "PyUnicode_Split", self.PyUnicode_Split_func_type,
2290             'split', is_unbound_method, args)
2291
2292     PyUnicode_Tailmatch_func_type = PyrexTypes.CFuncType(
2293         PyrexTypes.c_bint_type, [
2294             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2295             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2296             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2297             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2298             PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
2299             ],
2300         exception_value = '-1')
2301
2302     def _handle_simple_method_unicode_endswith(self, node, args, is_unbound_method):
2303         return self._inject_unicode_tailmatch(
2304             node, args, is_unbound_method, 'endswith', +1)
2305
2306     def _handle_simple_method_unicode_startswith(self, node, args, is_unbound_method):
2307         return self._inject_unicode_tailmatch(
2308             node, args, is_unbound_method, 'startswith', -1)
2309
2310     def _inject_unicode_tailmatch(self, node, args, is_unbound_method,
2311                                   method_name, direction):
2312         """Replace unicode.startswith(...) and unicode.endswith(...)
2313         by a direct call to the corresponding C-API function.
2314         """
2315         if len(args) not in (2,3,4):
2316             self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
2317             return node
2318         self._inject_int_default_argument(
2319             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2320         self._inject_int_default_argument(
2321             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2322         args.append(ExprNodes.IntNode(
2323             node.pos, value=str(direction), type=PyrexTypes.c_int_type))
2324
2325         method_call = self._substitute_method_call(
2326             node, "__Pyx_PyUnicode_Tailmatch", self.PyUnicode_Tailmatch_func_type,
2327             method_name, is_unbound_method, args,
2328             utility_code = unicode_tailmatch_utility_code)
2329         return method_call.coerce_to(Builtin.bool_type, self.current_env())
2330
2331     PyUnicode_Find_func_type = PyrexTypes.CFuncType(
2332         PyrexTypes.c_py_ssize_t_type, [
2333             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2334             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2335             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2336             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2337             PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
2338             ],
2339         exception_value = '-2')
2340
2341     def _handle_simple_method_unicode_find(self, node, args, is_unbound_method):
2342         return self._inject_unicode_find(
2343             node, args, is_unbound_method, 'find', +1)
2344
2345     def _handle_simple_method_unicode_rfind(self, node, args, is_unbound_method):
2346         return self._inject_unicode_find(
2347             node, args, is_unbound_method, 'rfind', -1)
2348
2349     def _inject_unicode_find(self, node, args, is_unbound_method,
2350                              method_name, direction):
2351         """Replace unicode.find(...) and unicode.rfind(...) by a
2352         direct call to the corresponding C-API function.
2353         """
2354         if len(args) not in (2,3,4):
2355             self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
2356             return node
2357         self._inject_int_default_argument(
2358             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2359         self._inject_int_default_argument(
2360             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2361         args.append(ExprNodes.IntNode(
2362             node.pos, value=str(direction), type=PyrexTypes.c_int_type))
2363
2364         method_call = self._substitute_method_call(
2365             node, "PyUnicode_Find", self.PyUnicode_Find_func_type,
2366             method_name, is_unbound_method, args)
2367         return method_call.coerce_to_pyobject(self.current_env())
2368
2369     PyUnicode_Count_func_type = PyrexTypes.CFuncType(
2370         PyrexTypes.c_py_ssize_t_type, [
2371             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2372             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2373             PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
2374             PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
2375             ],
2376         exception_value = '-1')
2377
2378     def _handle_simple_method_unicode_count(self, node, args, is_unbound_method):
2379         """Replace unicode.count(...) by a direct call to the
2380         corresponding C-API function.
2381         """
2382         if len(args) not in (2,3,4):
2383             self._error_wrong_arg_count('unicode.count', node, args, "2-4")
2384             return node
2385         self._inject_int_default_argument(
2386             node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
2387         self._inject_int_default_argument(
2388             node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2389
2390         method_call = self._substitute_method_call(
2391             node, "PyUnicode_Count", self.PyUnicode_Count_func_type,
2392             'count', is_unbound_method, args)
2393         return method_call.coerce_to_pyobject(self.current_env())
2394
2395     PyUnicode_Replace_func_type = PyrexTypes.CFuncType(
2396         Builtin.unicode_type, [
2397             PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
2398             PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
2399             PyrexTypes.CFuncTypeArg("replstr", PyrexTypes.py_object_type, None),
2400             PyrexTypes.CFuncTypeArg("maxcount", PyrexTypes.c_py_ssize_t_type, None),
2401             ])
2402
2403     def _handle_simple_method_unicode_replace(self, node, args, is_unbound_method):
2404         """Replace unicode.replace(...) by a direct call to the
2405         corresponding C-API function.
2406         """
2407         if len(args) not in (3,4):
2408             self._error_wrong_arg_count('unicode.replace', node, args, "3-4")
2409             return node
2410         self._inject_int_default_argument(
2411             node, args, 3, PyrexTypes.c_py_ssize_t_type, "-1")
2412
2413         return self._substitute_method_call(
2414             node, "PyUnicode_Replace", self.PyUnicode_Replace_func_type,
2415             'replace', is_unbound_method, args)
2416
2417     PyUnicode_AsEncodedString_func_type = PyrexTypes.CFuncType(
2418         Builtin.bytes_type, [
2419             PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2420             PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
2421             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2422             ])
2423
2424     PyUnicode_AsXyzString_func_type = PyrexTypes.CFuncType(
2425         Builtin.bytes_type, [
2426             PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2427             ])
2428
2429     _special_encodings = ['UTF8', 'UTF16', 'Latin1', 'ASCII',
2430                           'unicode_escape', 'raw_unicode_escape']
2431
2432     _special_codecs = [ (name, codecs.getencoder(name))
2433                         for name in _special_encodings ]
2434
2435     def _handle_simple_method_unicode_encode(self, node, args, is_unbound_method):
2436         """Replace unicode.encode(...) by a direct C-API call to the
2437         corresponding codec.
2438         """
2439         if len(args) < 1 or len(args) > 3:
2440             self._error_wrong_arg_count('unicode.encode', node, args, '1-3')
2441             return node
2442
2443         string_node = args[0]
2444
2445         if len(args) == 1:
2446             null_node = ExprNodes.NullNode(node.pos)
2447             return self._substitute_method_call(
2448                 node, "PyUnicode_AsEncodedString",
2449                 self.PyUnicode_AsEncodedString_func_type,
2450                 'encode', is_unbound_method, [string_node, null_node, null_node])
2451
2452         parameters = self._unpack_encoding_and_error_mode(node.pos, args)
2453         if parameters is None:
2454             return node
2455         encoding, encoding_node, error_handling, error_handling_node = parameters
2456
2457         if isinstance(string_node, ExprNodes.UnicodeNode):
2458             # constant, so try to do the encoding at compile time
2459             try:
2460                 value = string_node.value.encode(encoding, error_handling)
2461             except:
2462                 # well, looks like we can't
2463                 pass
2464             else:
2465                 value = BytesLiteral(value)
2466                 value.encoding = encoding
2467                 return ExprNodes.BytesNode(
2468                     string_node.pos, value=value, type=Builtin.bytes_type)
2469
2470         if error_handling == 'strict':
2471             # try to find a specific encoder function
2472             codec_name = self._find_special_codec_name(encoding)
2473             if codec_name is not None:
2474                 encode_function = "PyUnicode_As%sString" % codec_name
2475                 return self._substitute_method_call(
2476                     node, encode_function,
2477                     self.PyUnicode_AsXyzString_func_type,
2478                     'encode', is_unbound_method, [string_node])
2479
2480         return self._substitute_method_call(
2481             node, "PyUnicode_AsEncodedString",
2482             self.PyUnicode_AsEncodedString_func_type,
2483             'encode', is_unbound_method,
2484             [string_node, encoding_node, error_handling_node])
2485
2486     PyUnicode_DecodeXyz_func_type = PyrexTypes.CFuncType(
2487         Builtin.unicode_type, [
2488             PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2489             PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
2490             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2491             ])
2492
2493     PyUnicode_Decode_func_type = PyrexTypes.CFuncType(
2494         Builtin.unicode_type, [
2495             PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2496             PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
2497             PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
2498             PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2499             ])
2500
2501     def _handle_simple_method_bytes_decode(self, node, args, is_unbound_method):
2502         """Replace char*.decode() by a direct C-API call to the
2503         corresponding codec, possibly resoving a slice on the char*.
2504         """
2505         if len(args) < 1 or len(args) > 3:
2506             self._error_wrong_arg_count('bytes.decode', node, args, '1-3')
2507             return node
2508         temps = []
2509         if isinstance(args[0], ExprNodes.SliceIndexNode):
2510             index_node = args[0]
2511             string_node = index_node.base
2512             if not string_node.type.is_string:
2513                 # nothing to optimise here
2514                 return node
2515             start, stop = index_node.start, index_node.stop
2516             if not start or start.constant_result == 0:
2517                 start = None
2518             else:
2519                 if start.type.is_pyobject:
2520                     start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2521                 if stop:
2522                     start = UtilNodes.LetRefNode(start)
2523                     temps.append(start)
2524                 string_node = ExprNodes.AddNode(pos=start.pos,
2525                                                 operand1=string_node,
2526                                                 operator='+',
2527                                                 operand2=start,
2528                                                 is_temp=False,
2529                                                 type=string_node.type
2530                                                 )
2531             if stop and stop.type.is_pyobject:
2532                 stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2533         elif isinstance(args[0], ExprNodes.CoerceToPyTypeNode) \
2534                  and args[0].arg.type.is_string:
2535             # use strlen() to find the string length, just as CPython would
2536             start = stop = None
2537             string_node = args[0].arg
2538         else:
2539             # let Python do its job
2540             return node
2541
2542         if not stop:
2543             if start or not string_node.is_name:
2544                 string_node = UtilNodes.LetRefNode(string_node)
2545                 temps.append(string_node)
2546             stop = ExprNodes.PythonCapiCallNode(
2547                 string_node.pos, "strlen", self.Pyx_strlen_func_type,
2548                     args = [string_node],
2549                     is_temp = False,
2550                     utility_code = Builtin.include_string_h_utility_code,
2551                     ).coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2552         elif start:
2553             stop = ExprNodes.SubNode(
2554                 pos = stop.pos,
2555                 operand1 = stop,
2556                 operator = '-',
2557                 operand2 = start,
2558                 is_temp = False,
2559                 type = PyrexTypes.c_py_ssize_t_type
2560                 )
2561
2562         parameters = self._unpack_encoding_and_error_mode(node.pos, args)
2563         if parameters is None:
2564             return node
2565         encoding, encoding_node, error_handling, error_handling_node = parameters
2566
2567         # try to find a specific encoder function
2568         codec_name = None
2569         if encoding is not None:
2570             codec_name = self._find_special_codec_name(encoding)
2571         if codec_name is not None:
2572             decode_function = "PyUnicode_Decode%s" % codec_name
2573             node = ExprNodes.PythonCapiCallNode(
2574                 node.pos, decode_function,
2575                 self.PyUnicode_DecodeXyz_func_type,
2576                 args = [string_node, stop, error_handling_node],
2577                 is_temp = node.is_temp,
2578                 )
2579         else:
2580             node = ExprNodes.PythonCapiCallNode(
2581                 node.pos, "PyUnicode_Decode",
2582                 self.PyUnicode_Decode_func_type,
2583                 args = [string_node, stop, encoding_node, error_handling_node],
2584                 is_temp = node.is_temp,
2585                 )
2586
2587         for temp in temps[::-1]:
2588             node = UtilNodes.EvalWithTempExprNode(temp, node)
2589         return node
2590
2591     def _find_special_codec_name(self, encoding):
2592         try:
2593             requested_codec = codecs.getencoder(encoding)
2594         except:
2595             return None
2596         for name, codec in self._special_codecs:
2597             if codec == requested_codec:
2598                 if '_' in name:
2599                     name = ''.join([ s.capitalize()
2600                                      for s in name.split('_')])
2601                 return name
2602         return None
2603
2604     def _unpack_encoding_and_error_mode(self, pos, args):
2605         null_node = ExprNodes.NullNode(pos)
2606
2607         if len(args) >= 2:
2608             encoding_node = args[1]
2609             if isinstance(encoding_node, ExprNodes.CoerceToPyTypeNode):
2610                 encoding_node = encoding_node.arg
2611             if isinstance(encoding_node, (ExprNodes.UnicodeNode, ExprNodes.StringNode,
2612                                           ExprNodes.BytesNode)):
2613                 encoding = encoding_node.value
2614                 encoding_node = ExprNodes.BytesNode(encoding_node.pos, value=encoding,
2615                                                      type=PyrexTypes.c_char_ptr_type)
2616             elif encoding_node.type is Builtin.bytes_type:
2617                 encoding = None
2618                 encoding_node = encoding_node.coerce_to(
2619                     PyrexTypes.c_char_ptr_type, self.current_env())
2620             elif encoding_node.type.is_string:
2621                 encoding = None
2622             else:
2623                 return None
2624         else:
2625             encoding = None
2626             encoding_node = null_node
2627
2628         if len(args) == 3:
2629             error_handling_node = args[2]
2630             if isinstance(error_handling_node, ExprNodes.CoerceToPyTypeNode):
2631                 error_handling_node = error_handling_node.arg
2632             if isinstance(error_handling_node,
2633                           (ExprNodes.UnicodeNode, ExprNodes.StringNode,
2634                            ExprNodes.BytesNode)):
2635                 error_handling = error_handling_node.value
2636                 if error_handling == 'strict':
2637                     error_handling_node = null_node
2638                 else:
2639                     error_handling_node = ExprNodes.BytesNode(
2640                         error_handling_node.pos, value=error_handling,
2641                         type=PyrexTypes.c_char_ptr_type)
2642             elif error_handling_node.type is Builtin.bytes_type:
2643                 error_handling = None
2644                 error_handling_node = error_handling_node.coerce_to(
2645                     PyrexTypes.c_char_ptr_type, self.current_env())
2646             elif error_handling_node.type.is_string:
2647                 error_handling = None
2648             else:
2649                 return None
2650         else:
2651             error_handling = 'strict'
2652             error_handling_node = null_node
2653
2654         return (encoding, encoding_node, error_handling, error_handling_node)
2655
2656
2657     ### helpers
2658
2659     def _substitute_method_call(self, node, name, func_type,
2660                                 attr_name, is_unbound_method, args=(),
2661                                 utility_code=None,
2662                                 may_return_none=ExprNodes.PythonCapiCallNode.may_return_none):
2663         args = list(args)
2664         if args and not args[0].is_literal:
2665             self_arg = args[0]
2666             if is_unbound_method:
2667                 self_arg = self_arg.as_none_safe_node(
2668                     "descriptor '%s' requires a '%s' object but received a 'NoneType'" % (
2669                         attr_name, node.function.obj.name))
2670             else:
2671                 self_arg = self_arg.as_none_safe_node(
2672                     "'NoneType' object has no attribute '%s'" % attr_name,
2673                     error = "PyExc_AttributeError")
2674             args[0] = self_arg
2675         return ExprNodes.PythonCapiCallNode(
2676             node.pos, name, func_type,
2677             args = args,
2678             is_temp = node.is_temp,
2679             utility_code = utility_code,
2680             may_return_none = may_return_none,
2681             )
2682
2683     def _inject_int_default_argument(self, node, args, arg_index, type, default_value):
2684         assert len(args) >= arg_index
2685         if len(args) == arg_index:
2686             args.append(ExprNodes.IntNode(node.pos, value=str(default_value),
2687                                           type=type, constant_result=default_value))
2688         else:
2689             args[arg_index] = args[arg_index].coerce_to(type, self.current_env())
2690
2691     def _inject_bint_default_argument(self, node, args, arg_index, default_value):
2692         assert len(args) >= arg_index
2693         if len(args) == arg_index:
2694             default_value = bool(default_value)
2695             args.append(ExprNodes.BoolNode(node.pos, value=default_value,
2696                                            constant_result=default_value))
2697         else:
2698             args[arg_index] = args[arg_index].coerce_to_boolean(self.current_env())
2699
2700
2701 py_unicode_istitle_utility_code = UtilityCode(
2702 # Py_UNICODE_ISTITLE() doesn't match unicode.istitle() as the latter
2703 # additionally allows character that comply with Py_UNICODE_ISUPPER()
2704 proto = '''
2705 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar); /* proto */
2706 ''',
2707 impl = '''
2708 static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar) {
2709     return Py_UNICODE_ISTITLE(uchar) || Py_UNICODE_ISUPPER(uchar);
2710 }
2711 ''')
2712
2713 unicode_tailmatch_utility_code = UtilityCode(
2714     # Python's unicode.startswith() and unicode.endswith() support a
2715     # tuple of prefixes/suffixes, whereas it's much more common to
2716     # test for a single unicode string.
2717 proto = '''
2718 static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr, \
2719 Py_ssize_t start, Py_ssize_t end, int direction);
2720 ''',
2721 impl = '''
2722 static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr,
2723                                      Py_ssize_t start, Py_ssize_t end, int direction) {
2724     if (unlikely(PyTuple_Check(substr))) {
2725         int result;
2726         Py_ssize_t i;
2727         for (i = 0; i < PyTuple_GET_SIZE(substr); i++) {
2728             result = PyUnicode_Tailmatch(s, PyTuple_GET_ITEM(substr, i),
2729                                          start, end, direction);
2730             if (result) {
2731                 return result;
2732             }
2733         }
2734         return 0;
2735     }
2736     return PyUnicode_Tailmatch(s, substr, start, end, direction);
2737 }
2738 ''',
2739 )
2740
2741 dict_getitem_default_utility_code = UtilityCode(
2742 proto = '''
2743 static PyObject* __Pyx_PyDict_GetItemDefault(PyObject* d, PyObject* key, PyObject* default_value) {
2744     PyObject* value;
2745 #if PY_MAJOR_VERSION >= 3
2746     value = PyDict_GetItemWithError(d, key);
2747     if (unlikely(!value)) {
2748         if (unlikely(PyErr_Occurred()))
2749             return NULL;
2750         value = default_value;
2751     }
2752     Py_INCREF(value);
2753 #else
2754     if (PyString_CheckExact(key) || PyUnicode_CheckExact(key) || PyInt_CheckExact(key)) {
2755         /* these presumably have safe hash functions */
2756         value = PyDict_GetItem(d, key);
2757         if (unlikely(!value)) {
2758             value = default_value;
2759         }
2760         Py_INCREF(value);
2761     } else {
2762         PyObject *m;
2763         m = __Pyx_GetAttrString(d, "get");
2764         if (!m) return NULL;
2765         value = PyObject_CallFunctionObjArgs(m, key,
2766             (default_value == Py_None) ? NULL : default_value, NULL);
2767         Py_DECREF(m);
2768     }
2769 #endif
2770     return value;
2771 }
2772 ''',
2773 impl = ""
2774 )
2775
2776 append_utility_code = UtilityCode(
2777 proto = """
2778 static CYTHON_INLINE PyObject* __Pyx_PyObject_Append(PyObject* L, PyObject* x) {
2779     if (likely(PyList_CheckExact(L))) {
2780         if (PyList_Append(L, x) < 0) return NULL;
2781         Py_INCREF(Py_None);
2782         return Py_None; /* this is just to have an accurate signature */
2783     }
2784     else {
2785         PyObject *r, *m;
2786         m = __Pyx_GetAttrString(L, "append");
2787         if (!m) return NULL;
2788         r = PyObject_CallFunctionObjArgs(m, x, NULL);
2789         Py_DECREF(m);
2790         return r;
2791     }
2792 }
2793 """,
2794 impl = ""
2795 )
2796
2797
2798 pop_utility_code = UtilityCode(
2799 proto = """
2800 static CYTHON_INLINE PyObject* __Pyx_PyObject_Pop(PyObject* L) {
2801     PyObject *r, *m;
2802 #if PY_VERSION_HEX >= 0x02040000
2803     if (likely(PyList_CheckExact(L))
2804             /* Check that both the size is positive and no reallocation shrinking needs to be done. */
2805             && likely(PyList_GET_SIZE(L) > (((PyListObject*)L)->allocated >> 1))) {
2806         Py_SIZE(L) -= 1;
2807         return PyList_GET_ITEM(L, PyList_GET_SIZE(L));
2808     }
2809 #endif
2810     m = __Pyx_GetAttrString(L, "pop");
2811     if (!m) return NULL;
2812     r = PyObject_CallObject(m, NULL);
2813     Py_DECREF(m);
2814     return r;
2815 }
2816 """,
2817 impl = ""
2818 )
2819
2820 pop_index_utility_code = UtilityCode(
2821 proto = """
2822 static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix);
2823 """,
2824 impl = """
2825 static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix) {
2826     PyObject *r, *m, *t, *py_ix;
2827 #if PY_VERSION_HEX >= 0x02040000
2828     if (likely(PyList_CheckExact(L))) {
2829         Py_ssize_t size = PyList_GET_SIZE(L);
2830         if (likely(size > (((PyListObject*)L)->allocated >> 1))) {
2831             if (ix < 0) {
2832                 ix += size;
2833             }
2834             if (likely(0 <= ix && ix < size)) {
2835                 Py_ssize_t i;
2836                 PyObject* v = PyList_GET_ITEM(L, ix);
2837                 Py_SIZE(L) -= 1;
2838                 size -= 1;
2839                 for(i=ix; i<size; i++) {
2840                     PyList_SET_ITEM(L, i, PyList_GET_ITEM(L, i+1));
2841                 }
2842                 return v;
2843             }
2844         }
2845     }
2846 #endif
2847     py_ix = t = NULL;
2848     m = __Pyx_GetAttrString(L, "pop");
2849     if (!m) goto bad;
2850     py_ix = PyInt_FromSsize_t(ix);
2851     if (!py_ix) goto bad;
2852     t = PyTuple_New(1);
2853     if (!t) goto bad;
2854     PyTuple_SET_ITEM(t, 0, py_ix);
2855     py_ix = NULL;
2856     r = PyObject_CallObject(m, t);
2857     Py_DECREF(m);
2858     Py_DECREF(t);
2859     return r;
2860 bad:
2861     Py_XDECREF(m);
2862     Py_XDECREF(t);
2863     Py_XDECREF(py_ix);
2864     return NULL;
2865 }
2866 """
2867 )
2868
2869
2870 pyobject_as_double_utility_code = UtilityCode(
2871 proto = '''
2872 static double __Pyx__PyObject_AsDouble(PyObject* obj); /* proto */
2873
2874 #define __Pyx_PyObject_AsDouble(obj) \\
2875     ((likely(PyFloat_CheckExact(obj))) ? \\
2876      PyFloat_AS_DOUBLE(obj) : __Pyx__PyObject_AsDouble(obj))
2877 ''',
2878 impl='''
2879 static double __Pyx__PyObject_AsDouble(PyObject* obj) {
2880     PyObject* float_value;
2881     if (Py_TYPE(obj)->tp_as_number && Py_TYPE(obj)->tp_as_number->nb_float) {
2882         return PyFloat_AsDouble(obj);
2883     } else if (PyUnicode_CheckExact(obj) || PyBytes_CheckExact(obj)) {
2884 #if PY_MAJOR_VERSION >= 3
2885         float_value = PyFloat_FromString(obj);
2886 #else
2887         float_value = PyFloat_FromString(obj, 0);
2888 #endif
2889     } else {
2890         PyObject* args = PyTuple_New(1);
2891         if (unlikely(!args)) goto bad;
2892         PyTuple_SET_ITEM(args, 0, obj);
2893         float_value = PyObject_Call((PyObject*)&PyFloat_Type, args, 0);
2894         PyTuple_SET_ITEM(args, 0, 0);
2895         Py_DECREF(args);
2896     }
2897     if (likely(float_value)) {
2898         double value = PyFloat_AS_DOUBLE(float_value);
2899         Py_DECREF(float_value);
2900         return value;
2901     }
2902 bad:
2903     return (double)-1;
2904 }
2905 '''
2906 )
2907
2908
2909 bytes_index_utility_code = UtilityCode(
2910 proto = """
2911 static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* unicode, Py_ssize_t index, int check_bounds); /* proto */
2912 """,
2913 impl = """
2914 static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* bytes, Py_ssize_t index, int check_bounds) {
2915     if (check_bounds) {
2916         if (unlikely(index >= PyBytes_GET_SIZE(bytes)) |
2917             ((index < 0) & unlikely(index < -PyBytes_GET_SIZE(bytes)))) {
2918             PyErr_Format(PyExc_IndexError, "string index out of range");
2919             return -1;
2920         }
2921     }
2922     if (index < 0)
2923         index += PyBytes_GET_SIZE(bytes);
2924     return PyBytes_AS_STRING(bytes)[index];
2925 }
2926 """
2927 )
2928
2929
2930 tpnew_utility_code = UtilityCode(
2931 proto = """
2932 static CYTHON_INLINE PyObject* __Pyx_tp_new(PyObject* type_obj) {
2933     return (PyObject*) (((PyTypeObject*)(type_obj))->tp_new(
2934         (PyTypeObject*)(type_obj), %(TUPLE)s, NULL));
2935 }
2936 """ % {'TUPLE' : Naming.empty_tuple}
2937 )
2938
2939
2940 class ConstantFolding(Visitor.VisitorTransform, SkipDeclarations):
2941     """Calculate the result of constant expressions to store it in
2942     ``expr_node.constant_result``, and replace trivial cases by their
2943     constant result.
2944
2945     General rules:
2946
2947     - We calculate float constants to make them available to the
2948       compiler, but we do not aggregate them into a single literal
2949       node to prevent any loss of precision.
2950
2951     - We recursively calculate constants from non-literal nodes to
2952       make them available to the compiler, but we only aggregate
2953       literal nodes at each step.  Non-literal nodes are never merged
2954       into a single node.
2955     """
2956     def _calculate_const(self, node):
2957         if node.constant_result is not ExprNodes.constant_value_not_set:
2958             return
2959
2960         # make sure we always set the value
2961         not_a_constant = ExprNodes.not_a_constant
2962         node.constant_result = not_a_constant
2963
2964         # check if all children are constant
2965         children = self.visitchildren(node)
2966         for child_result in children.values():
2967             if type(child_result) is list:
2968                 for child in child_result:
2969                     if getattr(child, 'constant_result', not_a_constant) is not_a_constant:
2970                         return
2971             elif getattr(child_result, 'constant_result', not_a_constant) is not_a_constant:
2972                 return
2973
2974         # now try to calculate the real constant value
2975         try:
2976             node.calculate_constant_result()
2977 #            if node.constant_result is not ExprNodes.not_a_constant:
2978 #                print node.__class__.__name__, node.constant_result
2979         except (ValueError, TypeError, KeyError, IndexError, AttributeError, ArithmeticError):
2980             # ignore all 'normal' errors here => no constant result
2981             pass
2982         except Exception:
2983             # this looks like a real error
2984             import traceback, sys
2985             traceback.print_exc(file=sys.stdout)
2986
2987     NODE_TYPE_ORDER = [ExprNodes.CharNode, ExprNodes.IntNode,
2988                        ExprNodes.LongNode, ExprNodes.FloatNode]
2989
2990     def _widest_node_class(self, *nodes):
2991         try:
2992             return self.NODE_TYPE_ORDER[
2993                 max(map(self.NODE_TYPE_ORDER.index, map(type, nodes)))]
2994         except ValueError:
2995             return None
2996
2997     def visit_ExprNode(self, node):
2998         self._calculate_const(node)
2999         return node
3000
3001     def visit_UnopNode(self, node):
3002         self._calculate_const(node)
3003         if node.constant_result is ExprNodes.not_a_constant:
3004             return node
3005         if not node.operand.is_literal:
3006             return node
3007         if isinstance(node.operand, ExprNodes.BoolNode):
3008             return ExprNodes.IntNode(node.pos, value = str(node.constant_result),
3009                                      type = PyrexTypes.c_int_type,
3010                                      constant_result = node.constant_result)
3011         if node.operator == '+':
3012             return self._handle_UnaryPlusNode(node)
3013         elif node.operator == '-':
3014             return self._handle_UnaryMinusNode(node)
3015         return node
3016
3017     def _handle_UnaryMinusNode(self, node):
3018         if isinstance(node.operand, ExprNodes.LongNode):
3019             return ExprNodes.LongNode(node.pos, value = '-' + node.operand.value,
3020                                       constant_result = node.constant_result)
3021         if isinstance(node.operand, ExprNodes.FloatNode):
3022             # this is a safe operation
3023             return ExprNodes.FloatNode(node.pos, value = '-' + node.operand.value,
3024                                        constant_result = node.constant_result)
3025         node_type = node.operand.type
3026         if node_type.is_int and node_type.signed or \
3027                isinstance(node.operand, ExprNodes.IntNode) and node_type.is_pyobject:
3028             return ExprNodes.IntNode(node.pos, value = '-' + node.operand.value,
3029                                      type = node_type,
3030                                      longness = node.operand.longness,
3031                                      constant_result = node.constant_result)
3032         return node
3033
3034     def _handle_UnaryPlusNode(self, node):
3035         if node.constant_result == node.operand.constant_result:
3036             return node.operand
3037         return node
3038
3039     def visit_BoolBinopNode(self, node):
3040         self._calculate_const(node)
3041         if node.constant_result is ExprNodes.not_a_constant:
3042             return node
3043         if not node.operand1.is_literal or not node.operand2.is_literal:
3044             return node
3045
3046         if node.constant_result == node.operand1.constant_result and node.operand1.is_literal:
3047             return node.operand1
3048         elif node.constant_result == node.operand2.constant_result and node.operand2.is_literal:
3049             return node.operand2
3050         else:
3051             # FIXME: we could do more ...
3052             return node
3053
3054     def visit_BinopNode(self, node):
3055         self._calculate_const(node)
3056         if node.constant_result is ExprNodes.not_a_constant:
3057             return node
3058         if isinstance(node.constant_result, float):
3059             return node
3060         operand1, operand2 = node.operand1, node.operand2
3061         if not operand1.is_literal or not operand2.is_literal:
3062             return node
3063
3064         # now inject a new constant node with the calculated value
3065         try:
3066             type1, type2 = operand1.type, operand2.type
3067             if type1 is None or type2 is None:
3068                 return node
3069         except AttributeError:
3070             return node
3071
3072         if type1.is_numeric and type2.is_numeric:
3073             widest_type = PyrexTypes.widest_numeric_type(type1, type2)
3074         else:
3075             widest_type = PyrexTypes.py_object_type
3076         target_class = self._widest_node_class(operand1, operand2)
3077         if target_class is None:
3078             return node
3079         elif target_class is ExprNodes.IntNode:
3080             unsigned = getattr(operand1, 'unsigned', '') and \
3081                        getattr(operand2, 'unsigned', '')
3082             longness = "LL"[:max(len(getattr(operand1, 'longness', '')),
3083                                  len(getattr(operand2, 'longness', '')))]
3084             new_node = ExprNodes.IntNode(pos=node.pos,
3085                                          unsigned = unsigned, longness = longness,
3086                                          value = str(node.constant_result),
3087                                          constant_result = node.constant_result)
3088             # IntNode is smart about the type it chooses, so we just
3089             # make sure we were not smarter this time
3090             if widest_type.is_pyobject or new_node.type.is_pyobject:
3091                 new_node.type = PyrexTypes.py_object_type
3092             else:
3093                 new_node.type = PyrexTypes.widest_numeric_type(widest_type, new_node.type)
3094         else:
3095             if isinstance(node, ExprNodes.BoolNode):
3096                 node_value = node.constant_result
3097             else:
3098                 node_value = str(node.constant_result)
3099             new_node = target_class(pos=node.pos, type = widest_type,
3100                                     value = node_value,
3101                                     constant_result = node.constant_result)
3102         return new_node
3103
3104     def visit_PrimaryCmpNode(self, node):
3105         self._calculate_const(node)
3106         if node.constant_result is ExprNodes.not_a_constant:
3107             return node
3108         bool_result = bool(node.constant_result)
3109         return ExprNodes.BoolNode(node.pos, value=bool_result,
3110                                   constant_result=bool_result)
3111
3112     def visit_IfStatNode(self, node):
3113         self.visitchildren(node)
3114         # eliminate dead code based on constant condition results
3115         if_clauses = []
3116         for if_clause in node.if_clauses:
3117             condition_result = if_clause.get_constant_condition_result()
3118             if condition_result is None:
3119                 # unknown result => normal runtime evaluation
3120                 if_clauses.append(if_clause)
3121             elif condition_result == True:
3122                 # subsequent clauses can safely be dropped
3123                 node.else_clause = if_clause.body
3124                 break
3125             else:
3126                 assert condition_result == False
3127         if not if_clauses:
3128             return node.else_clause
3129         node.if_clauses = if_clauses
3130         return node
3131
3132     # in the future, other nodes can have their own handler method here
3133     # that can replace them with a constant result node
3134
3135     visit_Node = Visitor.VisitorTransform.recurse_to_children
3136
3137
3138 class FinalOptimizePhase(Visitor.CythonTransform):
3139     """
3140     This visitor handles several commuting optimizations, and is run
3141     just before the C code generation phase.
3142
3143     The optimizations currently implemented in this class are:
3144         - eliminate None assignment and refcounting for first assignment.
3145         - isinstance -> typecheck for cdef types
3146         - eliminate checks for None and/or types that became redundant after tree changes
3147     """
3148     def visit_SingleAssignmentNode(self, node):
3149         """Avoid redundant initialisation of local variables before their
3150         first assignment.
3151         """
3152         self.visitchildren(node)
3153         if node.first:
3154             lhs = node.lhs
3155             lhs.lhs_of_first_assignment = True
3156             if isinstance(lhs, ExprNodes.NameNode) and lhs.entry.type.is_pyobject:
3157                 # Have variable initialized to 0 rather than None
3158                 lhs.entry.init_to_none = False
3159                 lhs.entry.init = 0
3160         return node
3161
3162     def visit_SimpleCallNode(self, node):
3163         """Replace generic calls to isinstance(x, type) by a more efficient
3164         type check.
3165         """
3166         self.visitchildren(node)
3167         if node.function.type.is_cfunction and isinstance(node.function, ExprNodes.NameNode):
3168             if node.function.name == 'isinstance':
3169                 type_arg = node.args[1]
3170                 if type_arg.type.is_builtin_type and type_arg.type.name == 'type':
3171                     from CythonScope import utility_scope
3172                     node.function.entry = utility_scope.lookup('PyObject_TypeCheck')
3173                     node.function.type = node.function.entry.type
3174                     PyTypeObjectPtr = PyrexTypes.CPtrType(utility_scope.lookup('PyTypeObject').type)
3175                     node.args[1] = ExprNodes.CastNode(node.args[1], PyTypeObjectPtr)
3176         return node
3177
3178     def visit_PyTypeTestNode(self, node):
3179         """Remove tests for alternatively allowed None values from
3180         type tests when we know that the argument cannot be None
3181         anyway.
3182         """
3183         self.visitchildren(node)
3184         if not node.notnone:
3185             if not node.arg.may_be_none():
3186                 node.notnone = True
3187         return node