Optimize.py 122 KB
Newer Older
1 2
import Nodes
import ExprNodes
3
import PyrexTypes
4
import Visitor
5 6 7 8
import Builtin
import UtilNodes
import TypeSlots
import Symtab
9
import Options
10
import Naming
11

12
from Code import UtilityCode
13
from StringEncoding import EncodedString, BytesLiteral
14
from Errors import error
15 16
from ParseTreeTransforms import SkipDeclarations

17 18
import codecs

19 20 21 22 23
try:
    reduce
except NameError:
    from functools import reduce

24 25 26 27 28
try:
    set
except NameError:
    from sets import Set as set

29 30 31 32
class FakePythonEnv(object):
    "A fake environment for creating type test nodes etc."
    nogil = False

33 34 35 36 37
def unwrap_coerced_node(node, coercion_nodes=(ExprNodes.CoerceToPyTypeNode, ExprNodes.CoerceFromPyTypeNode)):
    if isinstance(node, coercion_nodes):
        return node.arg
    return node

38
def unwrap_node(node):
39 40
    while isinstance(node, UtilNodes.ResultRefNode):
        node = node.expression
41
    return node
42 43

def is_common_value(a, b):
44 45
    a = unwrap_node(a)
    b = unwrap_node(b)
46 47 48
    if isinstance(a, ExprNodes.NameNode) and isinstance(b, ExprNodes.NameNode):
        return a.name == b.name
    if isinstance(a, ExprNodes.AttributeNode) and isinstance(b, ExprNodes.AttributeNode):
49
        return not a.is_py_attr and is_common_value(a.obj, b.obj) and a.attribute == b.attribute
50 51
    return False

52 53 54 55
class IterationTransform(Visitor.VisitorTransform):
    """Transform some common for-in loop patterns into efficient C loops:

    - for-in-dict loop becomes a while loop calling PyDict_Next()
Stefan Behnel's avatar
Stefan Behnel committed
56
    - for-in-enumerate is replaced by an external counter variable
57
    - for-in-range loop becomes a plain C for loop
58 59 60 61 62 63 64 65 66 67 68 69 70 71
    """
    PyDict_Next_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_bint_type, [
            PyrexTypes.CFuncTypeArg("dict",  PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("pos",   PyrexTypes.c_py_ssize_t_ptr_type, None),
            PyrexTypes.CFuncTypeArg("key",   PyrexTypes.CPtrType(PyrexTypes.py_object_type), None),
            PyrexTypes.CFuncTypeArg("value", PyrexTypes.CPtrType(PyrexTypes.py_object_type), None)
            ])

    PyDict_Next_name = EncodedString("PyDict_Next")

    PyDict_Next_entry = Symtab.Entry(
        PyDict_Next_name, PyDict_Next_name, PyDict_Next_func_type)

72
    visit_Node = Visitor.VisitorTransform.recurse_to_children
Stefan Behnel's avatar
Stefan Behnel committed
73

74 75
    def visit_ModuleNode(self, node):
        self.current_scope = node.scope
76
        self.module_scope = node.scope
77 78 79 80 81 82 83 84 85
        self.visitchildren(node)
        return node

    def visit_DefNode(self, node):
        oldscope = self.current_scope
        self.current_scope = node.entry.scope
        self.visitchildren(node)
        self.current_scope = oldscope
        return node
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
    
    def visit_PrimaryCmpNode(self, node):
        if node.is_ptr_contains():
        
            # for t in operand2:
            #     if operand1 == t:
            #         res = True
            #         break
            # else:
            #     res = False
            
            pos = node.pos
            res_handle = UtilNodes.TempHandle(PyrexTypes.c_bint_type)
            res = res_handle.ref(pos)
            result_ref = UtilNodes.ResultRefNode(node)
            if isinstance(node.operand2, ExprNodes.IndexNode):
                base_type = node.operand2.base.type.base_type
            else:
                base_type = node.operand2.type.base_type
            target_handle = UtilNodes.TempHandle(base_type)
            target = target_handle.ref(pos)
            cmp_node = ExprNodes.PrimaryCmpNode(
                pos, operator=u'==', operand1=node.operand1, operand2=target)
            if_body = Nodes.StatListNode(
                pos, 
                stats = [Nodes.SingleAssignmentNode(pos, lhs=result_ref, rhs=ExprNodes.BoolNode(pos, value=1)),
                         Nodes.BreakStatNode(pos)])
            if_node = Nodes.IfStatNode(
                pos,
                if_clauses=[Nodes.IfClauseNode(pos, condition=cmp_node, body=if_body)],
                else_clause=None)
            for_loop = UtilNodes.TempsBlockNode(
                pos,
                temps = [target_handle],
                body = Nodes.ForInStatNode(
                    pos,
                    target=target,
                    iterator=ExprNodes.IteratorNode(node.operand2.pos, sequence=node.operand2),
                    body=if_node,
                    else_clause=Nodes.SingleAssignmentNode(pos, lhs=result_ref, rhs=ExprNodes.BoolNode(pos, value=0))))
            for_loop.analyse_expressions(self.current_scope)
            for_loop = self(for_loop)
            new_node = UtilNodes.TempResultFromStatNode(result_ref, for_loop)
            
            if node.operator == 'not_in':
                new_node = ExprNodes.NotNode(pos, operand=new_node)
            return new_node

        else:
            self.visitchildren(node)
            return node
137

138 139
    def visit_ForInStatNode(self, node):
        self.visitchildren(node)
140
        return self._optimise_for_loop(node)
141
    
142
    def _optimise_for_loop(self, node):
143
        iterator = node.iterator.sequence
144 145
        if iterator.type is Builtin.dict_type:
            # like iterating over dict.keys()
Stefan Behnel's avatar
Stefan Behnel committed
146 147
            return self._transform_dict_iteration(
                node, dict_obj=iterator, keys=True, values=False)
148

149
        # C array (slice) iteration?
150 151 152 153
        if False:
            plain_iterator = unwrap_coerced_node(iterator)
            if isinstance(plain_iterator, ExprNodes.SliceIndexNode) and \
                   (plain_iterator.base.type.is_array or plain_iterator.base.type.is_ptr):
154
                return self._transform_carray_iteration(node, plain_iterator)
155 156

        if iterator.type.is_ptr or iterator.type.is_array:
157
            return self._transform_carray_iteration(node, iterator)
158
        if iterator.type in (Builtin.bytes_type, Builtin.unicode_type):
159 160 161 162
            return self._transform_string_iteration(node, iterator)

        # the rest is based on function calls
        if not isinstance(iterator, ExprNodes.SimpleCallNode):
Stefan Behnel's avatar
Stefan Behnel committed
163 164 165
            return node

        function = iterator.function
166
        # dict iteration?
Stefan Behnel's avatar
Stefan Behnel committed
167 168
        if isinstance(function, ExprNodes.AttributeNode) and \
                function.obj.type == Builtin.dict_type:
169 170 171
            dict_obj = function.obj
            method = function.attribute

172
            is_py3 = self.module_scope.context.language_level >= 3
173
            keys = values = False
174
            if method == 'iterkeys' or (is_py3 and method == 'keys'):
175
                keys = True
176
            elif method == 'itervalues' or (is_py3 and method == 'values'):
177
                values = True
178
            elif method == 'iteritems' or (is_py3 and method == 'items'):
179 180 181
                keys = values = True
            else:
                return node
Stefan Behnel's avatar
Stefan Behnel committed
182 183
            return self._transform_dict_iteration(
                node, dict_obj, keys, values)
184

185
        # enumerate() ?
Stefan Behnel's avatar
Stefan Behnel committed
186
        if iterator.self is None and function.is_name and \
187
               function.entry and function.entry.is_builtin and \
188 189 190
               function.name == 'enumerate':
            return self._transform_enumerate_iteration(node, iterator)

191 192
        # range() iteration?
        if Options.convert_range and node.target.type.is_int:
Stefan Behnel's avatar
Stefan Behnel committed
193 194 195
            if iterator.self is None and function.is_name and \
                   function.entry and function.entry.is_builtin and \
                   function.name in ('range', 'xrange'):
Stefan Behnel's avatar
Stefan Behnel committed
196
                return self._transform_range_iteration(node, iterator)
197

Stefan Behnel's avatar
Stefan Behnel committed
198
        return node
199

200
    PyUnicode_AS_UNICODE_func_type = PyrexTypes.CFuncType(
Stefan Behnel's avatar
Stefan Behnel committed
201
        PyrexTypes.c_py_unicode_ptr_type, [
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
            PyrexTypes.CFuncTypeArg("s", Builtin.unicode_type, None)
            ])

    PyUnicode_GET_SIZE_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ssize_t_type, [
            PyrexTypes.CFuncTypeArg("s", Builtin.unicode_type, None)
            ])

    PyBytes_AS_STRING_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_char_ptr_type, [
            PyrexTypes.CFuncTypeArg("s", Builtin.bytes_type, None)
            ])

    PyBytes_GET_SIZE_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ssize_t_type, [
            PyrexTypes.CFuncTypeArg("s", Builtin.bytes_type, None)
            ])

    def _transform_string_iteration(self, node, slice_node):
        if not node.target.type.is_int:
222
            return self._transform_carray_iteration(node, slice_node)
223 224 225 226 227 228 229 230 231 232 233 234 235 236
        if slice_node.type is Builtin.unicode_type:
            unpack_func = "PyUnicode_AS_UNICODE"
            len_func = "PyUnicode_GET_SIZE"
            unpack_func_type = self.PyUnicode_AS_UNICODE_func_type
            len_func_type = self.PyUnicode_GET_SIZE_func_type
        elif slice_node.type is Builtin.bytes_type:
            unpack_func = "PyBytes_AS_STRING"
            unpack_func_type = self.PyBytes_AS_STRING_func_type
            len_func = "PyBytes_GET_SIZE"
            len_func_type = self.PyBytes_GET_SIZE_func_type
        else:
            return node

        unpack_temp_node = UtilNodes.LetRefNode(
237
            slice_node.as_none_safe_node("'NoneType' is not iterable"))
238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263

        slice_base_node = ExprNodes.PythonCapiCallNode(
            slice_node.pos, unpack_func, unpack_func_type,
            args = [unpack_temp_node],
            is_temp = 0,
            )
        len_node = ExprNodes.PythonCapiCallNode(
            slice_node.pos, len_func, len_func_type,
            args = [unpack_temp_node],
            is_temp = 0,
            )

        return UtilNodes.LetNode(
            unpack_temp_node,
            self._transform_carray_iteration(
                node,
                ExprNodes.SliceIndexNode(
                    slice_node.pos,
                    base = slice_base_node,
                    start = None,
                    step = None,
                    stop = len_node,
                    type = slice_base_node.type,
                    is_temp = 1,
                    )))

264
    def _transform_carray_iteration(self, node, slice_node):
265
        neg_step = False
266 267 268 269 270 271
        if isinstance(slice_node, ExprNodes.SliceIndexNode):
            slice_base = slice_node.base
            start = slice_node.start
            stop = slice_node.stop
            step = None
            if not stop:
272 273
                if not slice_base.type.is_pyobject:
                    error(slice_node.pos, "C array iteration requires known end index")
274
                return node
275 276
        elif isinstance(slice_node, ExprNodes.IndexNode):
            # slice_node.index must be a SliceNode
277 278
            slice_base = slice_node.base
            index = slice_node.index
279 280 281 282 283 284 285 286 287 288
            start = index.start
            stop = index.stop
            step = index.step
            if step:
                if step.constant_result is None:
                    step = None
                elif not isinstance(step.constant_result, (int,long)) \
                       or step.constant_result == 0 \
                       or step.constant_result > 0 and not stop \
                       or step.constant_result < 0 and not start:
289 290
                    if not slice_base.type.is_pyobject:
                        error(step.pos, "C array iteration requires known step size and end index")
291 292 293 294 295 296 297
                    return node
                else:
                    # step sign is handled internally by ForFromStatNode
                    neg_step = step.constant_result < 0
                    step = ExprNodes.IntNode(step.pos, type=PyrexTypes.c_py_ssize_t_type,
                                             value=abs(step.constant_result),
                                             constant_result=abs(step.constant_result))
298 299 300 301
        elif slice_node.type.is_array:
            if slice_node.type.size is None:
                error(step.pos, "C array iteration requires known end index")
                return node
302 303 304
            slice_base = slice_node
            start = None
            stop = ExprNodes.IntNode(
305 306
                slice_node.pos, value=str(slice_node.type.size),
                type=PyrexTypes.c_py_ssize_t_type, constant_result=slice_node.type.size)
307
            step = None
308

309
        else:
310
            if not slice_node.type.is_pyobject:
311
                error(slice_node.pos, "C array iteration requires known end index")
312 313
            return node

314 315 316 317 318 319 320 321 322 323
        if start:
            if start.constant_result is None:
                start = None
            else:
                start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_scope)
        if stop:
            if stop.constant_result is None:
                stop = None
            else:
                stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_scope)
324 325 326 327 328 329 330
        if stop is None:
            if neg_step:
                stop = ExprNodes.IntNode(
                    slice_node.pos, value='-1', type=PyrexTypes.c_py_ssize_t_type, constant_result=-1)
            else:
                error(slice_node.pos, "C array iteration requires known step size and end index")
                return node
331

332 333 334 335
        ptr_type = slice_base.type
        if ptr_type.is_array:
            ptr_type = ptr_type.element_ptr_type()
        carray_ptr = slice_base.coerce_to_simple(self.current_scope)
336

337
        if start and start.constant_result != 0:
338 339 340 341 342
            start_ptr_node = ExprNodes.AddNode(
                start.pos,
                operand1=carray_ptr,
                operator='+',
                operand2=start,
343
                type=ptr_type)
344
        else:
345
            start_ptr_node = carray_ptr
346

347 348
        stop_ptr_node = ExprNodes.AddNode(
            stop.pos,
349
            operand1=ExprNodes.CloneNode(carray_ptr),
350 351
            operator='+',
            operand2=stop,
352
            type=ptr_type
353
            ).coerce_to_simple(self.current_scope)
354

355
        counter = UtilNodes.TempHandle(ptr_type)
356 357
        counter_temp = counter.ref(node.target.pos)

358
        if slice_base.type.is_string and node.target.type.is_pyobject:
359
            # special case: char* -> bytes
360 361
            target_value = ExprNodes.SliceIndexNode(
                node.target.pos,
362 363 364 365 366 367 368
                start=ExprNodes.IntNode(node.target.pos, value='0',
                                        constant_result=0,
                                        type=PyrexTypes.c_int_type),
                stop=ExprNodes.IntNode(node.target.pos, value='1',
                                       constant_result=1,
                                       type=PyrexTypes.c_int_type),
                base=counter_temp,
369 370 371 372 373
                type=Builtin.bytes_type,
                is_temp=1)
        else:
            target_value = ExprNodes.IndexNode(
                node.target.pos,
374 375 376 377
                index=ExprNodes.IntNode(node.target.pos, value='0',
                                        constant_result=0,
                                        type=PyrexTypes.c_int_type),
                base=counter_temp,
378
                is_buffer_access=False,
379
                type=ptr_type.base_type)
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395

        if target_value.type != node.target.type:
            target_value = target_value.coerce_to(node.target.type,
                                                  self.current_scope)

        target_assign = Nodes.SingleAssignmentNode(
            pos = node.target.pos,
            lhs = node.target,
            rhs = target_value)

        body = Nodes.StatListNode(
            node.pos,
            stats = [target_assign, node.body])

        for_node = Nodes.ForFromStatNode(
            node.pos,
396
            bound1=start_ptr_node, relation1=neg_step and '>=' or '<=',
397
            target=counter_temp,
398
            relation2=neg_step and '>' or '<', bound2=stop_ptr_node,
399 400 401 402 403 404 405 406
            step=step, body=body,
            else_clause=node.else_clause,
            from_range=True)

        return UtilNodes.TempsBlockNode(
            node.pos, temps=[counter],
            body=for_node)

407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435
    def _transform_enumerate_iteration(self, node, enumerate_function):
        args = enumerate_function.arg_tuple.args
        if len(args) == 0:
            error(enumerate_function.pos,
                  "enumerate() requires an iterable argument")
            return node
        elif len(args) > 1:
            error(enumerate_function.pos,
                  "enumerate() takes at most 1 argument")
            return node

        if not node.target.is_sequence_constructor:
            # leave this untouched for now
            return node
        targets = node.target.args
        if len(targets) != 2:
            # leave this untouched for now
            return node
        if not isinstance(targets[0], ExprNodes.NameNode):
            # leave this untouched for now
            return node

        enumerate_target, iterable_target = targets
        counter_type = enumerate_target.type

        if not counter_type.is_pyobject and not counter_type.is_int:
            # nothing we can do here, I guess
            return node

436 437 438 439
        temp = UtilNodes.LetRefNode(ExprNodes.IntNode(enumerate_function.pos,
                                                      value='0',
                                                      type=counter_type,
                                                      constant_result=0))
440 441
        inc_expression = ExprNodes.AddNode(
            enumerate_function.pos,
442
            operand1 = temp,
443
            operand2 = ExprNodes.IntNode(node.pos, value='1',
444 445
                                         type=counter_type,
                                         constant_result=1),
446 447 448 449 450
            operator = '+',
            type = counter_type,
            is_temp = counter_type.is_pyobject
            )

451 452 453 454
        loop_body = [
            Nodes.SingleAssignmentNode(
                pos = enumerate_target.pos,
                lhs = enumerate_target,
455
                rhs = temp),
456 457
            Nodes.SingleAssignmentNode(
                pos = enumerate_target.pos,
458
                lhs = temp,
459 460
                rhs = inc_expression)
            ]
461

462 463 464 465 466 467 468
        if isinstance(node.body, Nodes.StatListNode):
            node.body.stats = loop_body + node.body.stats
        else:
            loop_body.append(node.body)
            node.body = Nodes.StatListNode(
                node.body.pos,
                stats = loop_body)
469 470

        node.target = iterable_target
471
        node.item = node.item.coerce_to(iterable_target.type, self.current_scope)
472 473 474
        node.iterator.sequence = enumerate_function.arg_tuple.args[0]

        # recurse into loop to check for further optimisations
475
        return UtilNodes.LetNode(temp, self._optimise_for_loop(node))
476

477 478 479 480 481
    def _transform_range_iteration(self, node, range_function):
        args = range_function.arg_tuple.args
        if len(args) < 3:
            step_pos = range_function.pos
            step_value = 1
482 483
            step = ExprNodes.IntNode(step_pos, value='1',
                                     constant_result=1)
484 485 486
        else:
            step = args[2]
            step_pos = step.pos
487
            if not isinstance(step.constant_result, (int, long)):
488 489
                # cannot determine step direction
                return node
490 491 492
            step_value = step.constant_result
            if step_value == 0:
                # will lead to an error elsewhere
493 494
                return node
            if not isinstance(step, ExprNodes.IntNode):
495 496
                step = ExprNodes.IntNode(step_pos, value=str(step_value),
                                         constant_result=step_value)
497

498
        if step_value < 0:
499
            step.value = str(-step_value)
500 501 502
            relation1 = '>='
            relation2 = '>'
        else:
503 504
            relation1 = '<='
            relation2 = '<'
505 506

        if len(args) == 1:
507 508
            bound1 = ExprNodes.IntNode(range_function.pos, value='0',
                                       constant_result=0)
509
            bound2 = args[0].coerce_to_integer(self.current_scope)
510
        else:
511 512 513
            bound1 = args[0].coerce_to_integer(self.current_scope)
            bound2 = args[1].coerce_to_integer(self.current_scope)
        step = step.coerce_to_integer(self.current_scope)
514

515
        if not bound2.is_literal:
516 517 518 519 520 521
            # stop bound must be immutable => keep it in a temp var
            bound2_is_temp = True
            bound2 = UtilNodes.LetRefNode(bound2)
        else:
            bound2_is_temp = False

522 523 524 525 526 527 528
        for_node = Nodes.ForFromStatNode(
            node.pos,
            target=node.target,
            bound1=bound1, relation1=relation1,
            relation2=relation2, bound2=bound2,
            step=step, body=node.body,
            else_clause=node.else_clause,
Magnus Lie Hetland's avatar
Magnus Lie Hetland committed
529
            from_range=True)
530 531 532 533

        if bound2_is_temp:
            for_node = UtilNodes.LetNode(bound2, for_node)

534 535
        return for_node

Stefan Behnel's avatar
Stefan Behnel committed
536
    def _transform_dict_iteration(self, node, dict_obj, keys, values):
537 538 539
        py_object_ptr = PyrexTypes.c_void_ptr_type

        temps = []
540 541 542
        temp = UtilNodes.TempHandle(PyrexTypes.py_object_type)
        temps.append(temp)
        dict_temp = temp.ref(dict_obj.pos)
543 544
        temp = UtilNodes.TempHandle(PyrexTypes.c_py_ssize_t_type)
        temps.append(temp)
545
        pos_temp = temp.ref(node.pos)
546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576
        pos_temp_addr = ExprNodes.AmpersandNode(
            node.pos, operand=pos_temp,
            type=PyrexTypes.c_ptr_type(PyrexTypes.c_py_ssize_t_type))
        if keys:
            temp = UtilNodes.TempHandle(py_object_ptr)
            temps.append(temp)
            key_temp = temp.ref(node.target.pos)
            key_temp_addr = ExprNodes.AmpersandNode(
                node.target.pos, operand=key_temp,
                type=PyrexTypes.c_ptr_type(py_object_ptr))
        else:
            key_temp_addr = key_temp = ExprNodes.NullNode(
                pos=node.target.pos)
        if values:
            temp = UtilNodes.TempHandle(py_object_ptr)
            temps.append(temp)
            value_temp = temp.ref(node.target.pos)
            value_temp_addr = ExprNodes.AmpersandNode(
                node.target.pos, operand=value_temp,
                type=PyrexTypes.c_ptr_type(py_object_ptr))
        else:
            value_temp_addr = value_temp = ExprNodes.NullNode(
                pos=node.target.pos)

        key_target = value_target = node.target
        tuple_target = None
        if keys and values:
            if node.target.is_sequence_constructor:
                if len(node.target.args) == 2:
                    key_target, value_target = node.target.args
                else:
Stefan Behnel's avatar
Stefan Behnel committed
577
                    # unusual case that may or may not lead to an error
578 579 580 581
                    return node
            else:
                tuple_target = node.target

582 583
        def coerce_object_to(obj_node, dest_type):
            if dest_type.is_pyobject:
584 585 586
                if dest_type != obj_node.type:
                    if dest_type.is_extension_type or dest_type.is_builtin_type:
                        obj_node = ExprNodes.PyTypeTestNode(
587
                            obj_node, dest_type, self.current_scope, notnone=True)
588 589 590 591
                result = ExprNodes.TypecastNode(
                    obj_node.pos,
                    operand = obj_node,
                    type = dest_type)
592
                return (result, None)
593 594 595 596 597 598 599 600 601
            else:
                temp = UtilNodes.TempHandle(dest_type)
                temps.append(temp)
                temp_result = temp.ref(obj_node.pos)
                class CoercedTempNode(ExprNodes.CoerceFromPyTypeNode):
                    def result(self):
                        return temp_result.result()
                    def generate_execution_code(self, code):
                        self.generate_result_code(code)
602
                return (temp_result, CoercedTempNode(dest_type, obj_node, self.current_scope))
603 604 605 606 607 608 609 610

        if isinstance(node.body, Nodes.StatListNode):
            body = node.body
        else:
            body = Nodes.StatListNode(pos = node.body.pos,
                                      stats = [node.body])

        if tuple_target:
611
            tuple_result = ExprNodes.TupleNode(
612
                pos = tuple_target.pos,
613
                args = [key_temp, value_temp],
614 615
                is_temp = 1,
                type = Builtin.tuple_type,
616
                )
617
            body.stats.insert(
618 619 620 621
                0, Nodes.SingleAssignmentNode(
                    pos = tuple_target.pos,
                    lhs = tuple_target,
                    rhs = tuple_result))
622
        else:
623 624 625
            # execute all coercions before the assignments
            coercion_stats = []
            assign_stats = []
626
            if keys:
627 628 629 630 631 632 633
                temp_result, coercion = coerce_object_to(
                    key_temp, key_target.type)
                if coercion:
                    coercion_stats.append(coercion)
                assign_stats.append(
                    Nodes.SingleAssignmentNode(
                        pos = key_temp.pos,
634 635
                        lhs = key_target,
                        rhs = temp_result))
636 637 638 639 640 641 642 643
            if values:
                temp_result, coercion = coerce_object_to(
                    value_temp, value_target.type)
                if coercion:
                    coercion_stats.append(coercion)
                assign_stats.append(
                    Nodes.SingleAssignmentNode(
                        pos = value_temp.pos,
644 645
                        lhs = value_target,
                        rhs = temp_result))
646
            body.stats[0:0] = coercion_stats + assign_stats
647 648

        result_code = [
649 650 651 652
            Nodes.SingleAssignmentNode(
                pos = dict_obj.pos,
                lhs = dict_temp,
                rhs = dict_obj),
653 654 655
            Nodes.SingleAssignmentNode(
                pos = node.pos,
                lhs = pos_temp,
656 657
                rhs = ExprNodes.IntNode(node.pos, value='0',
                                        constant_result=0)),
658 659 660 661 662 663
            Nodes.WhileStatNode(
                pos = node.pos,
                condition = ExprNodes.SimpleCallNode(
                    pos = dict_obj.pos,
                    type = PyrexTypes.c_bint_type,
                    function = ExprNodes.NameNode(
Stefan Behnel's avatar
Stefan Behnel committed
664 665
                        pos = dict_obj.pos,
                        name = self.PyDict_Next_name,
666 667
                        type = self.PyDict_Next_func_type,
                        entry = self.PyDict_Next_entry),
668
                    args = [dict_temp, pos_temp_addr,
669 670 671 672 673 674 675 676 677 678
                            key_temp_addr, value_temp_addr]
                    ),
                body = body,
                else_clause = node.else_clause
                )
            ]

        return UtilNodes.TempsBlockNode(
            node.pos, temps=temps,
            body=Nodes.StatListNode(
679
                node.pos,
680 681 682 683
                stats = result_code
                ))


684 685 686 687
class SwitchTransform(Visitor.VisitorTransform):
    """
    This transformation tries to turn long if statements into C switch statements. 
    The requirement is that every clause be an (or of) var == value, where the var
Robert Bradshaw's avatar
Robert Bradshaw committed
688
    is common among all clauses and both var and value are ints. 
689
    """
690 691 692
    NO_MATCH = (None, None, None)

    def extract_conditions(self, cond, allow_not_in):
693 694 695 696 697 698 699 700 701 702
        while True:
            if isinstance(cond, ExprNodes.CoerceToTempNode):
                cond = cond.arg
            elif isinstance(cond, UtilNodes.EvalWithTempExprNode):
                # this is what we get from the FlattenInListTransform
                cond = cond.subexpression
            elif isinstance(cond, ExprNodes.TypecastNode):
                cond = cond.operand
            else:
                break
703

704 705 706 707 708 709
        if isinstance(cond, ExprNodes.PrimaryCmpNode):
            if cond.cascade is None and not cond.is_python_comparison():
                if cond.operator == '==':
                    not_in = False
                elif allow_not_in and cond.operator == '!=':
                    not_in = True
710 711 712 713 714
                elif cond.is_c_string_contains() and \
                         isinstance(cond.operand2, (ExprNodes.UnicodeNode, ExprNodes.BytesNode)):
                    not_in = cond.operator == 'not_in'
                    if not_in and not allow_not_in:
                        return self.NO_MATCH
715 716 717 718 719 720
                    if isinstance(cond.operand2, ExprNodes.UnicodeNode) and \
                           cond.operand2.contains_surrogates():
                        # dealing with surrogates leads to different
                        # behaviour on wide and narrow Unicode
                        # platforms => refuse to optimise this case
                        return self.NO_MATCH
721 722 723 724 725 726
                    # this looks somewhat silly, but it does the right
                    # checks for NameNode and AttributeNode
                    if is_common_value(cond.operand1, cond.operand1):
                        return not_in, cond.operand1, self.extract_in_string_conditions(cond.operand2)
                    else:
                        return self.NO_MATCH
727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752
                else:
                    return self.NO_MATCH
                # this looks somewhat silly, but it does the right
                # checks for NameNode and AttributeNode
                if is_common_value(cond.operand1, cond.operand1):
                    if cond.operand2.is_literal:
                        return not_in, cond.operand1, [cond.operand2]
                    elif getattr(cond.operand2, 'entry', None) \
                             and cond.operand2.entry.is_const:
                        return not_in, cond.operand1, [cond.operand2]
                if is_common_value(cond.operand2, cond.operand2):
                    if cond.operand1.is_literal:
                        return not_in, cond.operand2, [cond.operand1]
                    elif getattr(cond.operand1, 'entry', None) \
                             and cond.operand1.entry.is_const:
                        return not_in, cond.operand2, [cond.operand1]
        elif isinstance(cond, ExprNodes.BoolBinopNode):
            if cond.operator == 'or' or (allow_not_in and cond.operator == 'and'):
                allow_not_in = (cond.operator == 'and')
                not_in_1, t1, c1 = self.extract_conditions(cond.operand1, allow_not_in)
                not_in_2, t2, c2 = self.extract_conditions(cond.operand2, allow_not_in)
                if t1 is not None and not_in_1 == not_in_2 and is_common_value(t1, t2):
                    if (not not_in_1) or allow_not_in:
                        return not_in_1, t1, c1+c2
        return self.NO_MATCH

753 754 755 756 757 758 759 760 761 762 763 764
    def extract_in_string_conditions(self, string_literal):
        if isinstance(string_literal, ExprNodes.UnicodeNode):
            charvals = map(ord, set(string_literal.value))
            charvals.sort()
            return [ ExprNodes.IntNode(string_literal.pos, value=str(charval),
                                       constant_result=charval)
                     for charval in charvals ]
        else:
            # this is a bit tricky as Py3's bytes type returns
            # integers on iteration, whereas Py2 returns 1-char byte
            # strings
            characters = string_literal.value
765 766
            characters = list(set([ characters[i:i+1] for i in range(len(characters)) ]))
            characters.sort()
767 768 769 770
            return [ ExprNodes.CharNode(string_literal.pos, value=charval,
                                        constant_result=charval)
                     for charval in characters ]

771 772
    def extract_common_conditions(self, common_var, condition, allow_not_in):
        not_in, var, conditions = self.extract_conditions(condition, allow_not_in)
773
        if var is None:
774
            return self.NO_MATCH
775
        elif common_var is not None and not is_common_value(var, common_var):
776
            return self.NO_MATCH
777
        elif not var.type.is_int or sum([not cond.type.is_int for cond in conditions]):
778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793
            return self.NO_MATCH
        return not_in, var, conditions

    def has_duplicate_values(self, condition_values):
        # duplicated values don't work in a switch statement
        seen = set()
        for value in condition_values:
            if value.constant_result is not ExprNodes.not_a_constant:
                if value.constant_result in seen:
                    return True
                seen.add(value.constant_result)
            else:
                # this isn't completely safe as we don't know the
                # final C value, but this is about the best we can do
                seen.add(getattr(getattr(value, 'entry', None), 'cname'))
        return False
794

795 796 797 798
    def visit_IfStatNode(self, node):
        common_var = None
        cases = []
        for if_clause in node.if_clauses:
799 800
            _, common_var, conditions = self.extract_common_conditions(
                common_var, if_clause.condition, False)
801
            if common_var is None:
802
                self.visitchildren(node)
803
                return node
804 805 806 807 808
            cases.append(Nodes.SwitchCaseNode(pos = if_clause.pos,
                                              conditions = conditions,
                                              body = if_clause.body))

        if sum([ len(case.conditions) for case in cases ]) < 2:
809 810 811 812
            self.visitchildren(node)
            return node
        if self.has_duplicate_values(sum([case.conditions for case in cases], [])):
            self.visitchildren(node)
813
            return node
814

Robert Bradshaw's avatar
Robert Bradshaw committed
815
        common_var = unwrap_node(common_var)
816 817 818 819 820 821 822
        switch_node = Nodes.SwitchStatNode(pos = node.pos,
                                           test = common_var,
                                           cases = cases,
                                           else_clause = node.else_clause)
        return switch_node

    def visit_CondExprNode(self, node):
823 824 825 826 827 828
        not_in, common_var, conditions = self.extract_common_conditions(
            None, node.test, True)
        if common_var is None \
               or len(conditions) < 2 \
               or self.has_duplicate_values(conditions):
            self.visitchildren(node)
829
            return node
830 831 832
        return self.build_simple_switch_statement(
            node, common_var, conditions, not_in,
            node.true_val, node.false_val)
833 834

    def visit_BoolBinopNode(self, node):
835 836 837 838 839 840
        not_in, common_var, conditions = self.extract_common_conditions(
            None, node, True)
        if common_var is None \
               or len(conditions) < 2 \
               or self.has_duplicate_values(conditions):
            self.visitchildren(node)
841 842
            return node

843 844
        return self.build_simple_switch_statement(
            node, common_var, conditions, not_in,
845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860
            ExprNodes.BoolNode(node.pos, value=True, constant_result=True),
            ExprNodes.BoolNode(node.pos, value=False, constant_result=False))

    def visit_PrimaryCmpNode(self, node):
        not_in, common_var, conditions = self.extract_common_conditions(
            None, node, True)
        if common_var is None \
               or len(conditions) < 2 \
               or self.has_duplicate_values(conditions):
            self.visitchildren(node)
            return node

        return self.build_simple_switch_statement(
            node, common_var, conditions, not_in,
            ExprNodes.BoolNode(node.pos, value=True, constant_result=True),
            ExprNodes.BoolNode(node.pos, value=False, constant_result=False))
861 862 863

    def build_simple_switch_statement(self, node, common_var, conditions,
                                      not_in, true_val, false_val):
864 865 866 867
        result_ref = UtilNodes.ResultRefNode(node)
        true_body = Nodes.SingleAssignmentNode(
            node.pos,
            lhs = result_ref,
868
            rhs = true_val,
869 870 871 872
            first = True)
        false_body = Nodes.SingleAssignmentNode(
            node.pos,
            lhs = result_ref,
873
            rhs = false_val,
874 875
            first = True)

876 877 878
        if not_in:
            true_body, false_body = false_body, true_body

879 880 881 882 883 884 885 886 887 888
        cases = [Nodes.SwitchCaseNode(pos = node.pos,
                                      conditions = conditions,
                                      body = true_body)]

        common_var = unwrap_node(common_var)
        switch_node = Nodes.SwitchStatNode(pos = node.pos,
                                           test = common_var,
                                           cases = cases,
                                           else_clause = false_body)
        return UtilNodes.TempResultFromStatNode(result_ref, switch_node)
889

890
    visit_Node = Visitor.VisitorTransform.recurse_to_children
891
                              
892

893
class FlattenInListTransform(Visitor.VisitorTransform, SkipDeclarations):
894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910
    """
    This transformation flattens "x in [val1, ..., valn]" into a sequential list
    of comparisons. 
    """
    
    def visit_PrimaryCmpNode(self, node):
        self.visitchildren(node)
        if node.cascade is not None:
            return node
        elif node.operator == 'in':
            conjunction = 'or'
            eq_or_neq = '=='
        elif node.operator == 'not_in':
            conjunction = 'and'
            eq_or_neq = '!='
        else:
            return node
911

912 913 914
        if not isinstance(node.operand2, (ExprNodes.TupleNode,
                                          ExprNodes.ListNode,
                                          ExprNodes.SetNode)):
Stefan Behnel's avatar
Stefan Behnel committed
915
            return node
916

Stefan Behnel's avatar
Stefan Behnel committed
917 918 919
        args = node.operand2.args
        if len(args) == 0:
            return ExprNodes.BoolNode(pos = node.pos, value = node.operator == 'not_in')
920

921
        lhs = UtilNodes.ResultRefNode(node.operand1)
Stefan Behnel's avatar
Stefan Behnel committed
922 923

        conds = []
924
        temps = []
Stefan Behnel's avatar
Stefan Behnel committed
925
        for arg in args:
926 927 928 929
            if not arg.is_simple():
                # must evaluate all non-simple RHS before doing the comparisons
                arg = UtilNodes.LetRefNode(arg)
                temps.append(arg)
Stefan Behnel's avatar
Stefan Behnel committed
930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946
            cond = ExprNodes.PrimaryCmpNode(
                                pos = node.pos,
                                operand1 = lhs,
                                operator = eq_or_neq,
                                operand2 = arg,
                                cascade = None)
            conds.append(ExprNodes.TypecastNode(
                                pos = node.pos, 
                                operand = cond,
                                type = PyrexTypes.c_bint_type))
        def concat(left, right):
            return ExprNodes.BoolBinopNode(
                                pos = node.pos, 
                                operator = conjunction,
                                operand1 = left,
                                operand2 = right)

947
        condition = reduce(concat, conds)
948 949 950 951
        new_node = UtilNodes.EvalWithTempExprNode(lhs, condition)
        for temp in temps[::-1]:
            new_node = UtilNodes.EvalWithTempExprNode(temp, new_node)
        return new_node
952

953
    visit_Node = Visitor.VisitorTransform.recurse_to_children
954 955


956 957 958 959 960 961
class DropRefcountingTransform(Visitor.VisitorTransform):
    """Drop ref-counting in safe places.
    """
    visit_Node = Visitor.VisitorTransform.recurse_to_children

    def visit_ParallelAssignmentNode(self, node):
Stefan Behnel's avatar
Stefan Behnel committed
962 963 964
        """
        Parallel swap assignments like 'a,b = b,a' are safe.
        """
965 966 967 968
        left_names, right_names = [], []
        left_indices, right_indices = [], []
        temps = []

969 970
        for stat in node.stats:
            if isinstance(stat, Nodes.SingleAssignmentNode):
971 972
                if not self._extract_operand(stat.lhs, left_names,
                                             left_indices, temps):
973
                    return node
974 975
                if not self._extract_operand(stat.rhs, right_names,
                                             right_indices, temps):
976
                    return node
977 978 979
            elif isinstance(stat, Nodes.CascadedAssignmentNode):
                # FIXME
                return node
980 981 982
            else:
                return node

983 984
        if left_names or right_names:
            # lhs/rhs names must be a non-redundant permutation
985 986
            lnames = [ path for path, n in left_names ]
            rnames = [ path for path, n in right_names ]
987 988 989
            if set(lnames) != set(rnames):
                return node
            if len(set(lnames)) != len(right_names):
990 991
                return node

992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014
        if left_indices or right_indices:
            # base name and index of index nodes must be a
            # non-redundant permutation
            lindices = []
            for lhs_node in left_indices:
                index_id = self._extract_index_id(lhs_node)
                if not index_id:
                    return node
                lindices.append(index_id)
            rindices = []
            for rhs_node in right_indices:
                index_id = self._extract_index_id(rhs_node)
                if not index_id:
                    return node
                rindices.append(index_id)
            
            if set(lindices) != set(rindices):
                return node
            if len(set(lindices)) != len(right_indices):
                return node

            # really supporting IndexNode requires support in
            # __Pyx_GetItemInt(), so let's stop short for now
1015 1016
            return node

1017 1018 1019 1020
        temp_args = [t.arg for t in temps]
        for temp in temps:
            temp.use_managed_ref = False

1021
        for _, name_node in left_names + right_names:
1022 1023 1024 1025 1026
            if name_node not in temp_args:
                name_node.use_managed_ref = False

        for index_node in left_indices + right_indices:
            index_node.use_managed_ref = False
1027 1028 1029

        return node

1030 1031 1032 1033 1034 1035 1036
    def _extract_operand(self, node, names, indices, temps):
        node = unwrap_node(node)
        if not node.type.is_pyobject:
            return False
        if isinstance(node, ExprNodes.CoerceToTempNode):
            temps.append(node)
            node = node.arg
1037 1038 1039 1040
        name_path = []
        obj_node = node
        while isinstance(obj_node, ExprNodes.AttributeNode):
            if obj_node.is_py_attr:
1041
                return False
1042 1043 1044 1045 1046
            name_path.append(obj_node.member)
            obj_node = obj_node.obj
        if isinstance(obj_node, ExprNodes.NameNode):
            name_path.append(obj_node.name)
            names.append( ('.'.join(name_path[::-1]), node) )
1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070
        elif isinstance(node, ExprNodes.IndexNode):
            if node.base.type != Builtin.list_type:
                return False
            if not node.index.type.is_int:
                return False
            if not isinstance(node.base, ExprNodes.NameNode):
                return False
            indices.append(node)
        else:
            return False
        return True

    def _extract_index_id(self, index_node):
        base = index_node.base
        index = index_node.index
        if isinstance(index, ExprNodes.NameNode):
            index_val = index.name
        elif isinstance(index, ExprNodes.ConstNode):
            # FIXME:
            return None
        else:
            return None
        return (base.name, index_val)

1071

1072 1073 1074 1075 1076 1077 1078
class EarlyReplaceBuiltinCalls(Visitor.EnvTransform):
    """Optimize some common calls to builtin types *before* the type
    analysis phase and *after* the declarations analysis phase.

    This transform cannot make use of any argument types, but it can
    restructure the tree in a way that the type analysis phase can
    respond to.
Stefan Behnel's avatar
Stefan Behnel committed
1079 1080 1081 1082

    Introducing C function calls here may not be a good idea.  Move
    them to the OptimizeBuiltinCalls transform instead, which runs
    after type analyis.
1083
    """
1084 1085
    # only intercept on call nodes
    visit_Node = Visitor.VisitorTransform.recurse_to_children
1086

1087 1088 1089 1090 1091 1092 1093
    def visit_SimpleCallNode(self, node):
        self.visitchildren(node)
        function = node.function
        if not self._function_is_builtin_name(function):
            return node
        return self._dispatch_to_handler(node, function, node.args)

1094
    def visit_GeneralCallNode(self, node):
1095
        self.visitchildren(node)
1096
        function = node.function
1097
        if not self._function_is_builtin_name(function):
1098 1099 1100 1101
            return node
        arg_tuple = node.positional_args
        if not isinstance(arg_tuple, ExprNodes.TupleNode):
            return node
1102
        args = arg_tuple.args
1103
        return self._dispatch_to_handler(
1104
            node, function, args, node.keyword_args)
1105

1106 1107 1108
    def _function_is_builtin_name(self, function):
        if not function.is_name:
            return False
1109
        entry = self.current_env().lookup(function.name)
1110
        if entry and getattr(entry, 'scope', None) is not Builtin.builtin_scope:
1111
            return False
1112
        # if entry is None, it's at least an undeclared name, so likely builtin
1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150
        return True

    def _dispatch_to_handler(self, node, function, args, kwargs=None):
        if kwargs is None:
            handler_name = '_handle_simple_function_%s' % function.name
        else:
            handler_name = '_handle_general_function_%s' % function.name
        handle_call = getattr(self, handler_name, None)
        if handle_call is not None:
            if kwargs is None:
                return handle_call(node, args)
            else:
                return handle_call(node, args, kwargs)
        return node

    def _inject_capi_function(self, node, cname, func_type, utility_code=None):
        node.function = ExprNodes.PythonCapiFunctionNode(
            node.function.pos, node.function.name, cname, func_type,
            utility_code = utility_code)

    def _error_wrong_arg_count(self, function_name, node, args, expected=None):
        if not expected: # None or 0
            arg_str = ''
        elif isinstance(expected, basestring) or expected > 1:
            arg_str = '...'
        elif expected == 1:
            arg_str = 'x'
        else:
            arg_str = ''
        if expected is not None:
            expected_str = 'expected %s, ' % expected
        else:
            expected_str = ''
        error(node.pos, "%s(%s) called with wrong number of args, %sfound %d" % (
            function_name, arg_str, expected_str, len(args)))

    # specific handlers for simple call nodes

1151 1152 1153 1154 1155 1156 1157
    def _handle_simple_function_float(self, node, pos_args):
        if len(pos_args) == 0:
            return ExprNodes.FloatNode(node.pos, value='0.0')
        if len(pos_args) > 1:
            self._error_wrong_arg_count('float', node, pos_args, 1)
        return node

1158 1159 1160
    class YieldNodeCollector(Visitor.TreeVisitor):
        def __init__(self):
            Visitor.TreeVisitor.__init__(self)
1161
            self.yield_stat_nodes = {}
1162 1163 1164 1165 1166 1167 1168
            self.yield_nodes = []

        visit_Node = Visitor.TreeVisitor.visitchildren
        def visit_YieldExprNode(self, node):
            self.yield_nodes.append(node)
            self.visitchildren(node)

1169 1170 1171 1172 1173
        def visit_ExprStatNode(self, node):
            self.visitchildren(node)
            if node.expr in self.yield_nodes:
                self.yield_stat_nodes[node.expr] = node

1174 1175 1176 1177 1178 1179
        def __visit_GeneratorExpressionNode(self, node):
            # enable when we support generic generator expressions
            #
            # everything below this node is out of scope
            pass

1180
    def _find_single_yield_expression(self, node):
1181 1182 1183
        collector = self.YieldNodeCollector()
        collector.visitchildren(node)
        if len(collector.yield_nodes) != 1:
1184 1185
            return None, None
        yield_node = collector.yield_nodes[0]
1186 1187 1188 1189
        try:
            return (yield_node.arg, collector.yield_stat_nodes[yield_node])
        except KeyError:
            return None, None
1190

1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
    def _handle_simple_function_all(self, node, pos_args):
        """Transform

        _result = all(x for L in LL for x in L)

        into

        for L in LL:
            for x in L:
                if not x:
                    _result = False
                    break
            else:
                continue
            break
        else:
            _result = True
        """
        return self._transform_any_all(node, pos_args, False)

    def _handle_simple_function_any(self, node, pos_args):
        """Transform

        _result = any(x for L in LL for x in L)

        into

        for L in LL:
            for x in L:
                if x:
                    _result = True
                    break
            else:
                continue
            break
        else:
            _result = False
        """
        return self._transform_any_all(node, pos_args, True)

    def _transform_any_all(self, node, pos_args, is_any):
        if len(pos_args) != 1:
            return node
        if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
            return node
1236 1237
        gen_expr_node = pos_args[0]
        loop_node = gen_expr_node.loop
1238 1239
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1240 1241 1242 1243 1244 1245 1246
            return node

        if is_any:
            condition = yield_expression
        else:
            condition = ExprNodes.NotNode(yield_expression.pos, operand = yield_expression)

1247
        result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.c_bint_type)
1248
        test_node = Nodes.IfStatNode(
1249
            yield_expression.pos,
1250 1251
            else_clause = None,
            if_clauses = [ Nodes.IfClauseNode(
1252
                yield_expression.pos,
1253 1254 1255 1256 1257 1258 1259
                condition = condition,
                body = Nodes.StatListNode(
                    node.pos,
                    stats = [
                        Nodes.SingleAssignmentNode(
                            node.pos,
                            lhs = result_ref,
1260
                            rhs = ExprNodes.BoolNode(yield_expression.pos, value = is_any,
1261 1262 1263 1264 1265 1266 1267 1268 1269
                                                     constant_result = is_any)),
                        Nodes.BreakStatNode(node.pos)
                        ])) ]
            )
        loop = loop_node
        while isinstance(loop.body, Nodes.LoopNode):
            next_loop = loop.body
            loop.body = Nodes.StatListNode(loop.body.pos, stats = [
                loop.body,
1270
                Nodes.BreakStatNode(yield_expression.pos)
1271
                ])
1272
            next_loop.else_clause = Nodes.ContinueStatNode(yield_expression.pos)
1273 1274 1275 1276
            loop = next_loop
        loop_node.else_clause = Nodes.SingleAssignmentNode(
            node.pos,
            lhs = result_ref,
1277
            rhs = ExprNodes.BoolNode(yield_expression.pos, value = not is_any,
1278 1279
                                     constant_result = not is_any))

1280
        Visitor.recursively_replace_node(loop_node, yield_stat_node, test_node)
1281

1282 1283
        return ExprNodes.InlinedGeneratorExpressionNode(
            gen_expr_node.pos, loop = loop_node, result_node = result_ref,
1284
            expr_scope = gen_expr_node.expr_scope, orig_func = is_any and 'any' or 'all')
1285

1286
    def _handle_simple_function_sum(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1287 1288
        """Transform sum(genexpr) into an equivalent inlined aggregation loop.
        """
1289 1290 1291 1292 1293 1294 1295
        if len(pos_args) not in (1,2):
            return node
        if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
            return node
        gen_expr_node = pos_args[0]
        loop_node = gen_expr_node.loop

1296 1297
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1298 1299 1300 1301 1302 1303 1304 1305 1306
            return node

        if len(pos_args) == 1:
            start = ExprNodes.IntNode(node.pos, value='0', constant_result=0)
        else:
            start = pos_args[1]

        result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.py_object_type)
        add_node = Nodes.SingleAssignmentNode(
1307
            yield_expression.pos,
1308 1309 1310 1311
            lhs = result_ref,
            rhs = ExprNodes.binop_node(node.pos, '+', result_ref, yield_expression)
            )

1312
        Visitor.recursively_replace_node(loop_node, yield_stat_node, add_node)
1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326

        exec_code = Nodes.StatListNode(
            node.pos,
            stats = [
                Nodes.SingleAssignmentNode(
                    start.pos,
                    lhs = UtilNodes.ResultRefNode(pos=node.pos, expression=result_ref),
                    rhs = start,
                    first = True),
                loop_node
                ])

        return ExprNodes.InlinedGeneratorExpressionNode(
            gen_expr_node.pos, loop = exec_code, result_node = result_ref,
1327
            expr_scope = gen_expr_node.expr_scope, orig_func = 'sum')
1328

1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364
    def _handle_simple_function_min(self, node, pos_args):
        return self._optimise_min_max(node, pos_args, '<')

    def _handle_simple_function_max(self, node, pos_args):
        return self._optimise_min_max(node, pos_args, '>')

    def _optimise_min_max(self, node, args, operator):
        """Replace min(a,b,...) and max(a,b,...) by explicit comparison code.
        """
        if len(args) <= 1:
            # leave this to Python
            return node

        cascaded_nodes = map(UtilNodes.ResultRefNode, args[1:])

        last_result = args[0]
        for arg_node in cascaded_nodes:
            result_ref = UtilNodes.ResultRefNode(last_result)
            last_result = ExprNodes.CondExprNode(
                arg_node.pos,
                true_val = arg_node,
                false_val = result_ref,
                test = ExprNodes.PrimaryCmpNode(
                    arg_node.pos,
                    operand1 = arg_node,
                    operator = operator,
                    operand2 = result_ref,
                    )
                )
            last_result = UtilNodes.EvalWithTempExprNode(result_ref, last_result)

        for ref_node in cascaded_nodes[::-1]:
            last_result = UtilNodes.EvalWithTempExprNode(ref_node, last_result)

        return last_result

1365
    def _DISABLED_handle_simple_function_tuple(self, node, pos_args):
1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379
        if len(pos_args) == 0:
            return ExprNodes.TupleNode(node.pos, args=[], constant_result=())
        # This is a bit special - for iterables (including genexps),
        # Python actually overallocates and resizes a newly created
        # tuple incrementally while reading items, which we can't
        # easily do without explicit node support. Instead, we read
        # the items into a list and then copy them into a tuple of the
        # final size.  This takes up to twice as much memory, but will
        # have to do until we have real support for genexps.
        result = self._transform_list_set_genexpr(node, pos_args, ExprNodes.ListNode)
        if result is not node:
            return ExprNodes.AsTupleNode(node.pos, arg=result)
        return node

1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399
    def _handle_simple_function_list(self, node, pos_args):
        if len(pos_args) == 0:
            return ExprNodes.ListNode(node.pos, args=[], constant_result=[])
        return self._transform_list_set_genexpr(node, pos_args, ExprNodes.ListNode)

    def _handle_simple_function_set(self, node, pos_args):
        if len(pos_args) == 0:
            return ExprNodes.SetNode(node.pos, args=[], constant_result=set())
        return self._transform_list_set_genexpr(node, pos_args, ExprNodes.SetNode)

    def _transform_list_set_genexpr(self, node, pos_args, container_node_class):
        """Replace set(genexpr) and list(genexpr) by a literal comprehension.
        """
        if len(pos_args) > 1:
            return node
        if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
            return node
        gen_expr_node = pos_args[0]
        loop_node = gen_expr_node.loop

1400 1401
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1402 1403 1404 1405
            return node

        target_node = container_node_class(node.pos, args=[])
        append_node = ExprNodes.ComprehensionAppendNode(
1406
            yield_expression.pos,
1407
            expr = yield_expression,
Stefan Behnel's avatar
Stefan Behnel committed
1408
            target = ExprNodes.CloneNode(target_node))
1409

1410
        Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433

        setcomp = ExprNodes.ComprehensionNode(
            node.pos,
            has_local_scope = True,
            expr_scope = gen_expr_node.expr_scope,
            loop = loop_node,
            append = append_node,
            target = target_node)
        append_node.target = setcomp
        return setcomp

    def _handle_simple_function_dict(self, node, pos_args):
        """Replace dict( (a,b) for ... ) by a literal { a:b for ... }.
        """
        if len(pos_args) == 0:
            return ExprNodes.DictNode(node.pos, key_value_pairs=[], constant_result={})
        if len(pos_args) > 1:
            return node
        if not isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
            return node
        gen_expr_node = pos_args[0]
        loop_node = gen_expr_node.loop

1434 1435
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1436 1437 1438 1439 1440 1441 1442 1443 1444
            return node

        if not isinstance(yield_expression, ExprNodes.TupleNode):
            return node
        if len(yield_expression.args) != 2:
            return node

        target_node = ExprNodes.DictNode(node.pos, key_value_pairs=[])
        append_node = ExprNodes.DictComprehensionAppendNode(
1445
            yield_expression.pos,
1446 1447
            key_expr = yield_expression.args[0],
            value_expr = yield_expression.args[1],
Stefan Behnel's avatar
Stefan Behnel committed
1448
            target = ExprNodes.CloneNode(target_node))
1449

1450
        Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461

        dictcomp = ExprNodes.ComprehensionNode(
            node.pos,
            has_local_scope = True,
            expr_scope = gen_expr_node.expr_scope,
            loop = loop_node,
            append = append_node,
            target = target_node)
        append_node.target = dictcomp
        return dictcomp

1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477
    # specific handlers for general call nodes

    def _handle_general_function_dict(self, node, pos_args, kwargs):
        """Replace dict(a=b,c=d,...) by the underlying keyword dict
        construction which is done anyway.
        """
        if len(pos_args) > 0:
            return node
        if not isinstance(kwargs, ExprNodes.DictNode):
            return node
        if node.starstar_arg:
            # we could optimize this by updating the kw dict instead
            return node
        return kwargs


1478
class OptimizeBuiltinCalls(Visitor.EnvTransform):
Stefan Behnel's avatar
Stefan Behnel committed
1479
    """Optimize some common methods calls and instantiation patterns
1480 1481 1482 1483 1484
    for builtin types *after* the type analysis phase.

    Running after type analysis, this transform can only perform
    function replacements that do not alter the function return type
    in a way that was not anticipated by the type analysis.
1485
    """
1486 1487
    # only intercept on call nodes
    visit_Node = Visitor.VisitorTransform.recurse_to_children
1488

1489
    def visit_GeneralCallNode(self, node):
1490
        self.visitchildren(node)
1491 1492
        function = node.function
        if not function.type.is_pyobject:
Stefan Behnel's avatar
Stefan Behnel committed
1493
            return node
1494 1495 1496
        arg_tuple = node.positional_args
        if not isinstance(arg_tuple, ExprNodes.TupleNode):
            return node
1497 1498
        if node.starstar_arg:
            return node
1499
        args = arg_tuple.args
1500
        return self._dispatch_to_handler(
1501
            node, function, args, node.keyword_args)
1502 1503 1504

    def visit_SimpleCallNode(self, node):
        self.visitchildren(node)
1505
        function = node.function
1506 1507 1508 1509 1510 1511 1512
        if function.type.is_pyobject:
            arg_tuple = node.arg_tuple
            if not isinstance(arg_tuple, ExprNodes.TupleNode):
                return node
            args = arg_tuple.args
        else:
            args = node.args
1513
        return self._dispatch_to_handler(
1514
            node, function, args)
1515

1516 1517
    ### cleanup to avoid redundant coercions to/from Python types

1518 1519 1520
    def _visit_PyTypeTestNode(self, node):
        # disabled - appears to break assignments in some cases, and
        # also drops a None check, which might still be required
1521 1522 1523 1524 1525 1526 1527 1528
        """Flatten redundant type checks after tree changes.
        """
        old_arg = node.arg
        self.visitchildren(node)
        if old_arg is node.arg or node.arg.type != node.type:
            return node
        return node.arg

1529 1530 1531 1532 1533 1534 1535 1536 1537
    def visit_TypecastNode(self, node):
        """
        Drop redundant type casts.
        """
        self.visitchildren(node)
        if node.type == node.operand.type:
            return node.operand
        return node

1538 1539 1540 1541 1542
    def visit_CoerceToBooleanNode(self, node):
        """Drop redundant conversion nodes after tree changes.
        """
        self.visitchildren(node)
        arg = node.arg
Stefan Behnel's avatar
Stefan Behnel committed
1543 1544
        if isinstance(arg, ExprNodes.PyTypeTestNode):
            arg = arg.arg
1545 1546
        if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
            if arg.type in (PyrexTypes.py_object_type, Builtin.bool_type):
1547
                return arg.arg.coerce_to_boolean(self.current_env())
1548 1549
        return node

1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563
    def visit_CoerceFromPyTypeNode(self, node):
        """Drop redundant conversion nodes after tree changes.

        Also, optimise away calls to Python's builtin int() and
        float() if the result is going to be coerced back into a C
        type anyway.
        """
        self.visitchildren(node)
        arg = node.arg
        if not arg.type.is_pyobject:
            # no Python conversion left at all, just do a C coercion instead
            if node.type == arg.type:
                return arg
            else:
1564
                return arg.coerce_to(node.type, self.current_env())
1565 1566
        if isinstance(arg, ExprNodes.PyTypeTestNode):
            arg = arg.arg
1567 1568 1569 1570
        if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
            if arg.type is PyrexTypes.py_object_type:
                if node.type.assignable_from(arg.arg.type):
                    # completely redundant C->Py->C coercion
1571
                    return arg.arg.coerce_to(node.type, self.current_env())
Stefan Behnel's avatar
Stefan Behnel committed
1572 1573 1574
        if isinstance(arg, ExprNodes.SimpleCallNode):
            if node.type.is_int or node.type.is_float:
                return self._optimise_numeric_cast_call(node, arg)
1575 1576 1577 1578 1579 1580
        elif isinstance(arg, ExprNodes.IndexNode) and not arg.is_buffer_access:
            index_node = arg.index
            if isinstance(index_node, ExprNodes.CoerceToPyTypeNode):
                index_node = index_node.arg
            if index_node.type.is_int:
                return self._optimise_int_indexing(node, arg, index_node)
Stefan Behnel's avatar
Stefan Behnel committed
1581 1582
        return node

1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594
    PyBytes_GetItemInt_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_char_type, [
            PyrexTypes.CFuncTypeArg("bytes", Builtin.bytes_type, None),
            PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("check_bounds", PyrexTypes.c_int_type, None),
            ],
        exception_value = "((char)-1)",
        exception_check = True)

    def _optimise_int_indexing(self, coerce_node, arg, index_node):
        env = self.current_env()
        bound_check_bool = env.directives['boundscheck'] and 1 or 0
1595
        if arg.base.type is Builtin.bytes_type:
1596 1597 1598 1599 1600 1601 1602 1603 1604
            if coerce_node.type in (PyrexTypes.c_char_type, PyrexTypes.c_uchar_type):
                # bytes[index] -> char
                bound_check_node = ExprNodes.IntNode(
                    coerce_node.pos, value=str(bound_check_bool),
                    constant_result=bound_check_bool)
                node = ExprNodes.PythonCapiCallNode(
                    coerce_node.pos, "__Pyx_PyBytes_GetItemInt",
                    self.PyBytes_GetItemInt_func_type,
                    args = [
Stefan Behnel's avatar
Stefan Behnel committed
1605
                        arg.base.as_none_safe_node("'NoneType' object is not subscriptable"),
1606 1607 1608 1609 1610 1611 1612 1613 1614 1615
                        index_node.coerce_to(PyrexTypes.c_py_ssize_t_type, env),
                        bound_check_node,
                        ],
                    is_temp = True,
                    utility_code=bytes_index_utility_code)
                if coerce_node.type is not PyrexTypes.c_char_type:
                    node = node.coerce_to(coerce_node.type, env)
                return node
        return coerce_node

Stefan Behnel's avatar
Stefan Behnel committed
1616
    def _optimise_numeric_cast_call(self, node, arg):
1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635
        function = arg.function
        if not isinstance(function, ExprNodes.NameNode) \
               or not function.type.is_builtin_type \
               or not isinstance(arg.arg_tuple, ExprNodes.TupleNode):
            return node
        args = arg.arg_tuple.args
        if len(args) != 1:
            return node
        func_arg = args[0]
        if isinstance(func_arg, ExprNodes.CoerceToPyTypeNode):
            func_arg = func_arg.arg
        elif func_arg.type.is_pyobject:
            # play safe: Python conversion might work on all sorts of things
            return node
        if function.name == 'int':
            if func_arg.type.is_int or node.type.is_int:
                if func_arg.type == node.type:
                    return func_arg
                elif node.type.assignable_from(func_arg.type) or func_arg.type.is_float:
1636 1637
                    return ExprNodes.TypecastNode(
                        node.pos, operand=func_arg, type=node.type)
1638 1639 1640 1641 1642
        elif function.name == 'float':
            if func_arg.type.is_float or node.type.is_float:
                if func_arg.type == node.type:
                    return func_arg
                elif node.type.assignable_from(func_arg.type) or func_arg.type.is_float:
1643 1644
                    return ExprNodes.TypecastNode(
                        node.pos, operand=func_arg, type=node.type)
1645 1646 1647 1648
        return node

    ### dispatch to specific optimisers

1649 1650 1651 1652 1653 1654 1655
    def _find_handler(self, match_name, has_kwargs):
        call_type = has_kwargs and 'general' or 'simple'
        handler = getattr(self, '_handle_%s_%s' % (call_type, match_name), None)
        if handler is None:
            handler = getattr(self, '_handle_any_%s' % match_name, None)
        return handler

1656
    def _dispatch_to_handler(self, node, function, arg_list, kwargs=None):
1657
        if function.is_name:
1658 1659 1660
            # we only consider functions that are either builtin
            # Python functions or builtins that were already replaced
            # into a C function call (defined in the builtin scope)
1661 1662
            if not function.entry:
                return node
1663 1664 1665 1666
            is_builtin = function.entry.is_builtin \
                         or getattr(function.entry, 'scope', None) is Builtin.builtin_scope
            if not is_builtin:
                return node
1667 1668 1669 1670 1671
            function_handler = self._find_handler(
                "function_%s" % function.name, kwargs)
            if function_handler is None:
                return node
            if kwargs:
1672
                return function_handler(node, arg_list, kwargs)
1673
            else:
1674 1675
                return function_handler(node, arg_list)
        elif function.is_attribute and function.type.is_pyobject:
Stefan Behnel's avatar
Stefan Behnel committed
1676
            attr_name = function.attribute
1677 1678
            self_arg = function.obj
            obj_type = self_arg.type
1679
            is_unbound_method = False
1680 1681 1682 1683 1684 1685 1686
            if obj_type.is_builtin_type:
                if obj_type is Builtin.type_type and arg_list and \
                         arg_list[0].type.is_pyobject:
                    # calling an unbound method like 'list.append(L,x)'
                    # (ignoring 'type.mro()' here ...)
                    type_name = function.obj.name
                    self_arg = None
1687
                    is_unbound_method = True
1688 1689 1690
                else:
                    type_name = obj_type.name
            else:
1691
                type_name = "object" # safety measure
1692
            method_handler = self._find_handler(
Stefan Behnel's avatar
Stefan Behnel committed
1693
                "method_%s_%s" % (type_name, attr_name), kwargs)
1694
            if method_handler is None:
Stefan Behnel's avatar
Stefan Behnel committed
1695 1696 1697 1698
                if attr_name in TypeSlots.method_name_to_slot \
                       or attr_name == '__new__':
                    method_handler = self._find_handler(
                        "slot%s" % attr_name, kwargs)
1699 1700
                if method_handler is None:
                    return node
1701 1702 1703
            if self_arg is not None:
                arg_list = [self_arg] + list(arg_list)
            if kwargs:
1704
                return method_handler(node, arg_list, kwargs, is_unbound_method)
1705
            else:
1706
                return method_handler(node, arg_list, is_unbound_method)
1707
        else:
1708
            return node
1709

1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725
    def _error_wrong_arg_count(self, function_name, node, args, expected=None):
        if not expected: # None or 0
            arg_str = ''
        elif isinstance(expected, basestring) or expected > 1:
            arg_str = '...'
        elif expected == 1:
            arg_str = 'x'
        else:
            arg_str = ''
        if expected is not None:
            expected_str = 'expected %s, ' % expected
        else:
            expected_str = ''
        error(node.pos, "%s(%s) called with wrong number of args, %sfound %d" % (
            function_name, arg_str, expected_str, len(args)))

1726 1727
    ### builtin types

1728 1729 1730 1731 1732 1733
    PyDict_Copy_func_type = PyrexTypes.CFuncType(
        Builtin.dict_type, [
            PyrexTypes.CFuncTypeArg("dict", Builtin.dict_type, None)
            ])

    def _handle_simple_function_dict(self, node, pos_args):
1734
        """Replace dict(some_dict) by PyDict_Copy(some_dict).
1735
        """
1736
        if len(pos_args) != 1:
1737
            return node
1738
        arg = pos_args[0]
1739
        if arg.type is Builtin.dict_type:
1740
            arg = arg.as_none_safe_node("'NoneType' is not iterable")
1741 1742
            return ExprNodes.PythonCapiCallNode(
                node.pos, "PyDict_Copy", self.PyDict_Copy_func_type,
1743
                args = [arg],
1744 1745 1746
                is_temp = node.is_temp
                )
        return node
1747

1748 1749 1750 1751 1752
    PyList_AsTuple_func_type = PyrexTypes.CFuncType(
        Builtin.tuple_type, [
            PyrexTypes.CFuncTypeArg("list", Builtin.list_type, None)
            ])

1753
    def _handle_simple_function_tuple(self, node, pos_args):
1754 1755
        """Replace tuple([...]) by a call to PyList_AsTuple.
        """
1756
        if len(pos_args) != 1:
1757
            return node
1758
        list_arg = pos_args[0]
1759 1760 1761 1762
        if list_arg.type is not Builtin.list_type:
            return node
        if not isinstance(list_arg, (ExprNodes.ComprehensionNode,
                                     ExprNodes.ListNode)):
1763
            pos_args[0] = list_arg.as_none_safe_node(
1764
                "'NoneType' object is not iterable")
1765

1766 1767
        return ExprNodes.PythonCapiCallNode(
            node.pos, "PyList_AsTuple", self.PyList_AsTuple_func_type,
1768
            args = pos_args,
1769 1770 1771
            is_temp = node.is_temp
            )

1772 1773 1774 1775 1776 1777 1778 1779
    PyObject_AsDouble_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_double_type, [
            PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
            ],
        exception_value = "((double)-1)",
        exception_check = True)

    def _handle_simple_function_float(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1780 1781 1782
        """Transform float() into either a C type cast or a faster C
        function call.
        """
1783 1784
        # Note: this requires the float() function to be typed as
        # returning a C 'double'
1785 1786 1787 1788 1789 1790
        if len(pos_args) == 0:
            return ExprNode.FloatNode(
                node, value="0.0", constant_result=0.0
                ).coerce_to(Builtin.float_type, self.current_env())
        elif len(pos_args) != 1:
            self._error_wrong_arg_count('float', node, pos_args, '0 or 1')
1791 1792 1793 1794 1795 1796 1797
            return node
        func_arg = pos_args[0]
        if isinstance(func_arg, ExprNodes.CoerceToPyTypeNode):
            func_arg = func_arg.arg
        if func_arg.type is PyrexTypes.c_double_type:
            return func_arg
        elif node.type.assignable_from(func_arg.type) or func_arg.type.is_numeric:
1798 1799
            return ExprNodes.TypecastNode(
                node.pos, operand=func_arg, type=node.type)
1800 1801 1802 1803 1804 1805 1806 1807
        return ExprNodes.PythonCapiCallNode(
            node.pos, "__Pyx_PyObject_AsDouble",
            self.PyObject_AsDouble_func_type,
            args = pos_args,
            is_temp = node.is_temp,
            utility_code = pyobject_as_double_utility_code,
            py_name = "float")

1808 1809 1810
    def _handle_simple_function_bool(self, node, pos_args):
        """Transform bool(x) into a type coercion to a boolean.
        """
1811 1812 1813 1814 1815 1816
        if len(pos_args) == 0:
            return ExprNodes.BoolNode(
                node.pos, value=False, constant_result=False
                ).coerce_to(Builtin.bool_type, self.current_env())
        elif len(pos_args) != 1:
            self._error_wrong_arg_count('bool', node, pos_args, '0 or 1')
1817
            return node
Craig Citro's avatar
Craig Citro committed
1818 1819 1820
        else:
            return pos_args[0].coerce_to_boolean(
                self.current_env()).coerce_to_pyobject(self.current_env())
1821

1822 1823
    ### builtin functions

1824 1825 1826 1827 1828
    Pyx_strlen_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_size_t_type, [
            PyrexTypes.CFuncTypeArg("bytes", PyrexTypes.c_char_ptr_type, None)
            ])

1829 1830 1831 1832 1833 1834 1835
    PyObject_Size_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ssize_t_type, [
            PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None)
            ])

    _map_to_capi_len_function = {
        Builtin.unicode_type   : "PyUnicode_GET_SIZE",
1836
        Builtin.bytes_type     : "PyBytes_GET_SIZE",
1837 1838 1839 1840 1841 1842 1843
        Builtin.list_type      : "PyList_GET_SIZE",
        Builtin.tuple_type     : "PyTuple_GET_SIZE",
        Builtin.dict_type      : "PyDict_Size",
        Builtin.set_type       : "PySet_Size",
        Builtin.frozenset_type : "PySet_Size",
        }.get

1844
    def _handle_simple_function_len(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1845 1846
        """Replace len(char*) by the equivalent call to strlen() and
        len(known_builtin_type) by an equivalent C-API call.
Stefan Behnel's avatar
Stefan Behnel committed
1847
        """
1848 1849 1850 1851 1852 1853
        if len(pos_args) != 1:
            self._error_wrong_arg_count('len', node, pos_args, 1)
            return node
        arg = pos_args[0]
        if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
            arg = arg.arg
1854 1855 1856 1857 1858
        if arg.type.is_string:
            new_node = ExprNodes.PythonCapiCallNode(
                node.pos, "strlen", self.Pyx_strlen_func_type,
                args = [arg],
                is_temp = node.is_temp,
1859
                utility_code = Builtin.include_string_h_utility_code)
1860 1861 1862 1863
        elif arg.type.is_pyobject:
            cfunc_name = self._map_to_capi_len_function(arg.type)
            if cfunc_name is None:
                return node
1864 1865
            arg = arg.as_none_safe_node(
                "object of type 'NoneType' has no len()")
1866 1867 1868 1869
            new_node = ExprNodes.PythonCapiCallNode(
                node.pos, cfunc_name, self.PyObject_Size_func_type,
                args = [arg],
                is_temp = node.is_temp)
1870 1871 1872
        elif arg.type is PyrexTypes.c_py_unicode_type:
            return ExprNodes.IntNode(node.pos, value='1', constant_result=1,
                                     type=node.type)
1873
        else:
Stefan Behnel's avatar
Stefan Behnel committed
1874
            return node
1875
        if node.type not in (PyrexTypes.c_size_t_type, PyrexTypes.c_py_ssize_t_type):
1876
            new_node = new_node.coerce_to(node.type, self.current_env())
1877
        return new_node
1878

1879 1880 1881 1882 1883 1884
    Pyx_Type_func_type = PyrexTypes.CFuncType(
        Builtin.type_type, [
            PyrexTypes.CFuncTypeArg("object", PyrexTypes.py_object_type, None)
            ])

    def _handle_simple_function_type(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1885 1886
        """Replace type(o) by a macro call to Py_TYPE(o).
        """
1887
        if len(pos_args) != 1:
1888 1889
            return node
        node = ExprNodes.PythonCapiCallNode(
1890 1891 1892 1893
            node.pos, "Py_TYPE", self.Pyx_Type_func_type,
            args = pos_args,
            is_temp = False)
        return ExprNodes.CastNode(node, PyrexTypes.py_object_type)
1894

1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947
    Py_type_check_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_bint_type, [
            PyrexTypes.CFuncTypeArg("arg", PyrexTypes.py_object_type, None)
            ])

    def _handle_simple_function_isinstance(self, node, pos_args):
        """Replace isinstance() checks against builtin types by the
        corresponding C-API call.
        """
        if len(pos_args) != 2:
            return node
        arg, types = pos_args
        temp = None
        if isinstance(types, ExprNodes.TupleNode):
            types = types.args
            arg = temp = UtilNodes.ResultRefNode(arg)
        elif types.type is Builtin.type_type:
            types = [types]
        else:
            return node

        tests = []
        test_nodes = []
        env = self.current_env()
        for test_type_node in types:
            if not test_type_node.entry:
                return node
            entry = env.lookup(test_type_node.entry.name)
            if not entry or not entry.type or not entry.type.is_builtin_type:
                return node
            type_check_function = entry.type.type_check_function(exact=False)
            if not type_check_function:
                return node
            if type_check_function not in tests:
                tests.append(type_check_function)
                test_nodes.append(
                    ExprNodes.PythonCapiCallNode(
                        test_type_node.pos, type_check_function, self.Py_type_check_func_type,
                        args = [arg],
                        is_temp = True,
                        ))

        def join_with_or(a,b, make_binop_node=ExprNodes.binop_node):
            or_node = make_binop_node(node.pos, 'or', a, b)
            or_node.type = PyrexTypes.c_bint_type
            or_node.is_temp = True
            return or_node

        test_node = reduce(join_with_or, test_nodes).coerce_to(node.type, env)
        if temp is not None:
            test_node = UtilNodes.EvalWithTempExprNode(temp, test_node)
        return test_node

1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958
    def _handle_simple_function_ord(self, node, pos_args):
        """Unpack ord(Py_UNICODE).
        """
        if len(pos_args) != 1:
            return node
        arg = pos_args[0]
        if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
            if arg.arg.type is PyrexTypes.c_py_unicode_type:
                return arg.arg.coerce_to(node.type, self.current_env())
        return node

1959 1960
    ### special methods

1961 1962 1963 1964 1965
    Pyx_tp_new_func_type = PyrexTypes.CFuncType(
        PyrexTypes.py_object_type, [
            PyrexTypes.CFuncTypeArg("type", Builtin.type_type, None)
            ])

Stefan Behnel's avatar
Stefan Behnel committed
1966
    def _handle_simple_slot__new__(self, node, args, is_unbound_method):
1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984
        """Replace 'exttype.__new__(exttype)' by a call to exttype->tp_new()
        """
        obj = node.function.obj
        if not is_unbound_method or len(args) != 1:
            return node
        type_arg = args[0]
        if not obj.is_name or not type_arg.is_name:
            # play safe
            return node
        if obj.type != Builtin.type_type or type_arg.type != Builtin.type_type:
            # not a known type, play safe
            return node
        if not type_arg.type_entry or not obj.type_entry:
            if obj.name != type_arg.name:
                return node
            # otherwise, we know it's a type and we know it's the same
            # type for both - that should do
        elif type_arg.type_entry != obj.type_entry:
1985
            # different types - may or may not lead to an error at runtime
1986 1987
            return node

Stefan Behnel's avatar
Stefan Behnel committed
1988 1989 1990 1991
        # FIXME: we could potentially look up the actual tp_new C
        # method of the extension type and call that instead of the
        # generic slot. That would also allow us to pass parameters
        # efficiently.
1992

1993 1994
        if not type_arg.type_entry:
            # arbitrary variable, needs a None check for safety
1995
            type_arg = type_arg.as_none_safe_node(
1996 1997
                "object.__new__(X): X is not a type object (NoneType)")

1998
        return ExprNodes.PythonCapiCallNode(
1999
            node.pos, "__Pyx_tp_new", self.Pyx_tp_new_func_type,
2000
            args = [type_arg],
2001 2002 2003 2004
            utility_code = tpnew_utility_code,
            is_temp = node.is_temp
            )

2005 2006 2007 2008 2009 2010 2011 2012
    ### methods of builtin types

    PyObject_Append_func_type = PyrexTypes.CFuncType(
        PyrexTypes.py_object_type, [
            PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("item", PyrexTypes.py_object_type, None),
            ])

2013
    def _handle_simple_method_object_append(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2014 2015 2016
        """Optimistic optimisation as X.append() is almost always
        referring to a list.
        """
2017
        if len(args) != 2:
2018 2019
            return node

2020 2021 2022
        return ExprNodes.PythonCapiCallNode(
            node.pos, "__Pyx_PyObject_Append", self.PyObject_Append_func_type,
            args = args,
Stefan Behnel's avatar
Stefan Behnel committed
2023
            may_return_none = True,
2024
            is_temp = node.is_temp,
2025
            utility_code = append_utility_code
2026 2027
            )

Robert Bradshaw's avatar
Robert Bradshaw committed
2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039
    PyObject_Pop_func_type = PyrexTypes.CFuncType(
        PyrexTypes.py_object_type, [
            PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
            ])

    PyObject_PopIndex_func_type = PyrexTypes.CFuncType(
        PyrexTypes.py_object_type, [
            PyrexTypes.CFuncTypeArg("list", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_long_type, None),
            ])

    def _handle_simple_method_object_pop(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2040 2041 2042
        """Optimistic optimisation as X.pop([n]) is almost always
        referring to a list.
        """
Robert Bradshaw's avatar
Robert Bradshaw committed
2043 2044 2045 2046
        if len(args) == 1:
            return ExprNodes.PythonCapiCallNode(
                node.pos, "__Pyx_PyObject_Pop", self.PyObject_Pop_func_type,
                args = args,
Stefan Behnel's avatar
Stefan Behnel committed
2047
                may_return_none = True,
Robert Bradshaw's avatar
Robert Bradshaw committed
2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058
                is_temp = node.is_temp,
                utility_code = pop_utility_code
                )
        elif len(args) == 2:
            if isinstance(args[1], ExprNodes.CoerceToPyTypeNode) and args[1].arg.type.is_int:
                original_type = args[1].arg.type
                if PyrexTypes.widest_numeric_type(original_type, PyrexTypes.c_py_ssize_t_type) == PyrexTypes.c_py_ssize_t_type:
                    args[1] = args[1].arg
                    return ExprNodes.PythonCapiCallNode(
                        node.pos, "__Pyx_PyObject_PopIndex", self.PyObject_PopIndex_func_type,
                        args = args,
Stefan Behnel's avatar
Stefan Behnel committed
2059
                        may_return_none = True,
Robert Bradshaw's avatar
Robert Bradshaw committed
2060 2061 2062 2063 2064 2065
                        is_temp = node.is_temp,
                        utility_code = pop_index_utility_code
                        )
                
        return node

2066 2067
    _handle_simple_method_list_pop = _handle_simple_method_object_pop

2068 2069 2070 2071 2072
    single_param_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_int_type, [
            PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
            ],
        exception_value = "-1")
2073

2074
    def _handle_simple_method_list_sort(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2075 2076
        """Call PyList_Sort() instead of the 0-argument l.sort().
        """
2077
        if len(args) != 1:
2078
            return node
2079
        return self._substitute_method_call(
2080 2081
            node, "PyList_Sort", self.single_param_func_type,
            'sort', is_unbound_method, args)
2082

2083 2084 2085 2086 2087
    Pyx_PyDict_GetItem_func_type = PyrexTypes.CFuncType(
        PyrexTypes.py_object_type, [
            PyrexTypes.CFuncTypeArg("dict", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("key", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("default", PyrexTypes.py_object_type, None),
2088
            ])
2089 2090

    def _handle_simple_method_dict_get(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2091 2092
        """Replace dict.get() by a call to PyDict_GetItem().
        """
2093 2094 2095 2096 2097 2098 2099 2100 2101
        if len(args) == 2:
            args.append(ExprNodes.NoneNode(node.pos))
        elif len(args) != 3:
            self._error_wrong_arg_count('dict.get', node, args, "2 or 3")
            return node

        return self._substitute_method_call(
            node, "__Pyx_PyDict_GetItemDefault", self.Pyx_PyDict_GetItem_func_type,
            'get', is_unbound_method, args,
Stefan Behnel's avatar
Stefan Behnel committed
2102
            may_return_none = True,
2103 2104
            utility_code = dict_getitem_default_utility_code)

2105 2106 2107

    ### unicode type methods

2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172
    PyUnicode_uchar_predicate_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_bint_type, [
            PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_unicode_type, None),
            ])

    def _inject_unicode_predicate(self, node, args, is_unbound_method):
        if is_unbound_method or len(args) != 1:
            return node
        ustring = args[0]
        if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
               ustring.arg.type is not PyrexTypes.c_py_unicode_type:
            return node
        uchar = ustring.arg
        method_name = node.function.attribute
        if method_name == 'istitle':
            # istitle() doesn't directly map to Py_UNICODE_ISTITLE()
            utility_code = py_unicode_istitle_utility_code
            function_name = '__Pyx_Py_UNICODE_ISTITLE'
        else:
            utility_code = None
            function_name = 'Py_UNICODE_%s' % method_name.upper()
        func_call = self._substitute_method_call(
            node, function_name, self.PyUnicode_uchar_predicate_func_type,
            method_name, is_unbound_method, [uchar],
            utility_code = utility_code)
        if node.type.is_pyobject:
            func_call = func_call.coerce_to_pyobject(self.current_env)
        return func_call

    _handle_simple_method_unicode_isalnum   = _inject_unicode_predicate
    _handle_simple_method_unicode_isalpha   = _inject_unicode_predicate
    _handle_simple_method_unicode_isdecimal = _inject_unicode_predicate
    _handle_simple_method_unicode_isdigit   = _inject_unicode_predicate
    _handle_simple_method_unicode_islower   = _inject_unicode_predicate
    _handle_simple_method_unicode_isnumeric = _inject_unicode_predicate
    _handle_simple_method_unicode_isspace   = _inject_unicode_predicate
    _handle_simple_method_unicode_istitle   = _inject_unicode_predicate
    _handle_simple_method_unicode_isupper   = _inject_unicode_predicate

    PyUnicode_uchar_conversion_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_unicode_type, [
            PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_unicode_type, None),
            ])

    def _inject_unicode_character_conversion(self, node, args, is_unbound_method):
        if is_unbound_method or len(args) != 1:
            return node
        ustring = args[0]
        if not isinstance(ustring, ExprNodes.CoerceToPyTypeNode) or \
               ustring.arg.type is not PyrexTypes.c_py_unicode_type:
            return node
        uchar = ustring.arg
        method_name = node.function.attribute
        function_name = 'Py_UNICODE_TO%s' % method_name.upper()
        func_call = self._substitute_method_call(
            node, function_name, self.PyUnicode_uchar_conversion_func_type,
            method_name, is_unbound_method, [uchar])
        if node.type.is_pyobject:
            func_call = func_call.coerce_to_pyobject(self.current_env)
        return func_call

    _handle_simple_method_unicode_lower = _inject_unicode_character_conversion
    _handle_simple_method_unicode_upper = _inject_unicode_character_conversion
    _handle_simple_method_unicode_title = _inject_unicode_character_conversion

2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185
    PyUnicode_Splitlines_func_type = PyrexTypes.CFuncType(
        Builtin.list_type, [
            PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
            PyrexTypes.CFuncTypeArg("keepends", PyrexTypes.c_bint_type, None),
            ])

    def _handle_simple_method_unicode_splitlines(self, node, args, is_unbound_method):
        """Replace unicode.splitlines(...) by a direct call to the
        corresponding C-API function.
        """
        if len(args) not in (1,2):
            self._error_wrong_arg_count('unicode.splitlines', node, args, "1 or 2")
            return node
2186
        self._inject_bint_default_argument(node, args, 1, False)
2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208

        return self._substitute_method_call(
            node, "PyUnicode_Splitlines", self.PyUnicode_Splitlines_func_type,
            'splitlines', is_unbound_method, args)

    PyUnicode_Split_func_type = PyrexTypes.CFuncType(
        Builtin.list_type, [
            PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
            PyrexTypes.CFuncTypeArg("sep", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("maxsplit", PyrexTypes.c_py_ssize_t_type, None),
            ]
        )

    def _handle_simple_method_unicode_split(self, node, args, is_unbound_method):
        """Replace unicode.split(...) by a direct call to the
        corresponding C-API function.
        """
        if len(args) not in (1,2,3):
            self._error_wrong_arg_count('unicode.split', node, args, "1-3")
            return node
        if len(args) < 2:
            args.append(ExprNodes.NullNode(node.pos))
2209 2210
        self._inject_int_default_argument(
            node, args, 2, PyrexTypes.c_py_ssize_t_type, "-1")
2211 2212 2213 2214 2215

        return self._substitute_method_call(
            node, "PyUnicode_Split", self.PyUnicode_Split_func_type,
            'split', is_unbound_method, args)

2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241
    PyUnicode_Tailmatch_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_bint_type, [
            PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
            PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
            ],
        exception_value = '-1')

    def _handle_simple_method_unicode_endswith(self, node, args, is_unbound_method):
        return self._inject_unicode_tailmatch(
            node, args, is_unbound_method, 'endswith', +1)

    def _handle_simple_method_unicode_startswith(self, node, args, is_unbound_method):
        return self._inject_unicode_tailmatch(
            node, args, is_unbound_method, 'startswith', -1)

    def _inject_unicode_tailmatch(self, node, args, is_unbound_method,
                                  method_name, direction):
        """Replace unicode.startswith(...) and unicode.endswith(...)
        by a direct call to the corresponding C-API function.
        """
        if len(args) not in (2,3,4):
            self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
            return node
2242 2243 2244 2245
        self._inject_int_default_argument(
            node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
        self._inject_int_default_argument(
            node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2246 2247 2248 2249 2250 2251 2252
        args.append(ExprNodes.IntNode(
            node.pos, value=str(direction), type=PyrexTypes.c_int_type))

        method_call = self._substitute_method_call(
            node, "__Pyx_PyUnicode_Tailmatch", self.PyUnicode_Tailmatch_func_type,
            method_name, is_unbound_method, args,
            utility_code = unicode_tailmatch_utility_code)
Stefan Behnel's avatar
Stefan Behnel committed
2253
        return method_call.coerce_to(Builtin.bool_type, self.current_env())
2254

2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280
    PyUnicode_Find_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ssize_t_type, [
            PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
            PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("direction", PyrexTypes.c_int_type, None),
            ],
        exception_value = '-2')

    def _handle_simple_method_unicode_find(self, node, args, is_unbound_method):
        return self._inject_unicode_find(
            node, args, is_unbound_method, 'find', +1)

    def _handle_simple_method_unicode_rfind(self, node, args, is_unbound_method):
        return self._inject_unicode_find(
            node, args, is_unbound_method, 'rfind', -1)

    def _inject_unicode_find(self, node, args, is_unbound_method,
                             method_name, direction):
        """Replace unicode.find(...) and unicode.rfind(...) by a
        direct call to the corresponding C-API function.
        """
        if len(args) not in (2,3,4):
            self._error_wrong_arg_count('unicode.%s' % method_name, node, args, "2-4")
            return node
2281 2282 2283 2284
        self._inject_int_default_argument(
            node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
        self._inject_int_default_argument(
            node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
2285 2286 2287 2288 2289 2290
        args.append(ExprNodes.IntNode(
            node.pos, value=str(direction), type=PyrexTypes.c_int_type))

        method_call = self._substitute_method_call(
            node, "PyUnicode_Find", self.PyUnicode_Find_func_type,
            method_name, is_unbound_method, args)
Stefan Behnel's avatar
Stefan Behnel committed
2291
        return method_call.coerce_to_pyobject(self.current_env())
2292

Stefan Behnel's avatar
Stefan Behnel committed
2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308
    PyUnicode_Count_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ssize_t_type, [
            PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
            PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("end", PyrexTypes.c_py_ssize_t_type, None),
            ],
        exception_value = '-1')

    def _handle_simple_method_unicode_count(self, node, args, is_unbound_method):
        """Replace unicode.count(...) by a direct call to the
        corresponding C-API function.
        """
        if len(args) not in (2,3,4):
            self._error_wrong_arg_count('unicode.count', node, args, "2-4")
            return node
2309 2310 2311 2312
        self._inject_int_default_argument(
            node, args, 2, PyrexTypes.c_py_ssize_t_type, "0")
        self._inject_int_default_argument(
            node, args, 3, PyrexTypes.c_py_ssize_t_type, "PY_SSIZE_T_MAX")
Stefan Behnel's avatar
Stefan Behnel committed
2313 2314 2315 2316

        method_call = self._substitute_method_call(
            node, "PyUnicode_Count", self.PyUnicode_Count_func_type,
            'count', is_unbound_method, args)
Stefan Behnel's avatar
Stefan Behnel committed
2317
        return method_call.coerce_to_pyobject(self.current_env())
Stefan Behnel's avatar
Stefan Behnel committed
2318

Stefan Behnel's avatar
Stefan Behnel committed
2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333
    PyUnicode_Replace_func_type = PyrexTypes.CFuncType(
        Builtin.unicode_type, [
            PyrexTypes.CFuncTypeArg("str", Builtin.unicode_type, None),
            PyrexTypes.CFuncTypeArg("substring", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("replstr", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("maxcount", PyrexTypes.c_py_ssize_t_type, None),
            ])

    def _handle_simple_method_unicode_replace(self, node, args, is_unbound_method):
        """Replace unicode.replace(...) by a direct call to the
        corresponding C-API function.
        """
        if len(args) not in (3,4):
            self._error_wrong_arg_count('unicode.replace', node, args, "3-4")
            return node
2334 2335
        self._inject_int_default_argument(
            node, args, 3, PyrexTypes.c_py_ssize_t_type, "-1")
Stefan Behnel's avatar
Stefan Behnel committed
2336 2337 2338 2339 2340

        return self._substitute_method_call(
            node, "PyUnicode_Replace", self.PyUnicode_Replace_func_type,
            'replace', is_unbound_method, args)

2341 2342
    PyUnicode_AsEncodedString_func_type = PyrexTypes.CFuncType(
        Builtin.bytes_type, [
2343
            PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2344 2345
            PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
            PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2346
            ])
2347 2348 2349

    PyUnicode_AsXyzString_func_type = PyrexTypes.CFuncType(
        Builtin.bytes_type, [
2350
            PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2351
            ])
2352 2353 2354 2355

    _special_encodings = ['UTF8', 'UTF16', 'Latin1', 'ASCII',
                          'unicode_escape', 'raw_unicode_escape']

2356 2357
    _special_codecs = [ (name, codecs.getencoder(name))
                        for name in _special_encodings ]
2358 2359

    def _handle_simple_method_unicode_encode(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2360 2361 2362
        """Replace unicode.encode(...) by a direct C-API call to the
        corresponding codec.
        """
2363
        if len(args) < 1 or len(args) > 3:
2364
            self._error_wrong_arg_count('unicode.encode', node, args, '1-3')
2365 2366 2367 2368 2369
            return node

        string_node = args[0]

        if len(args) == 1:
2370
            null_node = ExprNodes.NullNode(node.pos)
2371 2372 2373 2374 2375
            return self._substitute_method_call(
                node, "PyUnicode_AsEncodedString",
                self.PyUnicode_AsEncodedString_func_type,
                'encode', is_unbound_method, [string_node, null_node, null_node])

2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414
        parameters = self._unpack_encoding_and_error_mode(node.pos, args)
        if parameters is None:
            return node
        encoding, encoding_node, error_handling, error_handling_node = parameters

        if isinstance(string_node, ExprNodes.UnicodeNode):
            # constant, so try to do the encoding at compile time
            try:
                value = string_node.value.encode(encoding, error_handling)
            except:
                # well, looks like we can't
                pass
            else:
                value = BytesLiteral(value)
                value.encoding = encoding
                return ExprNodes.BytesNode(
                    string_node.pos, value=value, type=Builtin.bytes_type)

        if error_handling == 'strict':
            # try to find a specific encoder function
            codec_name = self._find_special_codec_name(encoding)
            if codec_name is not None:
                encode_function = "PyUnicode_As%sString" % codec_name
                return self._substitute_method_call(
                    node, encode_function,
                    self.PyUnicode_AsXyzString_func_type,
                    'encode', is_unbound_method, [string_node])

        return self._substitute_method_call(
            node, "PyUnicode_AsEncodedString",
            self.PyUnicode_AsEncodedString_func_type,
            'encode', is_unbound_method,
            [string_node, encoding_node, error_handling_node])

    PyUnicode_DecodeXyz_func_type = PyrexTypes.CFuncType(
        Builtin.unicode_type, [
            PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
            PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2415
            ])
2416 2417 2418 2419 2420 2421 2422

    PyUnicode_Decode_func_type = PyrexTypes.CFuncType(
        Builtin.unicode_type, [
            PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
            PyrexTypes.CFuncTypeArg("size", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
            PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2423
            ])
2424 2425

    def _handle_simple_method_bytes_decode(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2426 2427 2428
        """Replace char*.decode() by a direct C-API call to the
        corresponding codec, possibly resoving a slice on the char*.
        """
2429 2430 2431
        if len(args) < 1 or len(args) > 3:
            self._error_wrong_arg_count('bytes.decode', node, args, '1-3')
            return node
2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443
        temps = []
        if isinstance(args[0], ExprNodes.SliceIndexNode):
            index_node = args[0]
            string_node = index_node.base
            if not string_node.type.is_string:
                # nothing to optimise here
                return node
            start, stop = index_node.start, index_node.stop
            if not start or start.constant_result == 0:
                start = None
            else:
                if start.type.is_pyobject:
2444
                    start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2445
                if stop:
2446 2447 2448 2449 2450 2451 2452 2453 2454 2455
                    start = UtilNodes.LetRefNode(start)
                    temps.append(start)
                string_node = ExprNodes.AddNode(pos=start.pos,
                                                operand1=string_node,
                                                operator='+',
                                                operand2=start,
                                                is_temp=False,
                                                type=string_node.type
                                                )
            if stop and stop.type.is_pyobject:
2456
                stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2457 2458 2459 2460 2461 2462 2463
        elif isinstance(args[0], ExprNodes.CoerceToPyTypeNode) \
                 and args[0].arg.type.is_string:
            # use strlen() to find the string length, just as CPython would
            start = stop = None
            string_node = args[0].arg
        else:
            # let Python do its job
2464
            return node
2465

2466
        if not stop:
2467
            if start or not string_node.is_name:
2468 2469 2470 2471 2472 2473
                string_node = UtilNodes.LetRefNode(string_node)
                temps.append(string_node)
            stop = ExprNodes.PythonCapiCallNode(
                string_node.pos, "strlen", self.Pyx_strlen_func_type,
                    args = [string_node],
                    is_temp = False,
2474
                    utility_code = Builtin.include_string_h_utility_code,
2475
                    ).coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
2476 2477 2478 2479 2480 2481 2482 2483 2484
        elif start:
            stop = ExprNodes.SubNode(
                pos = stop.pos,
                operand1 = stop,
                operator = '-',
                operand2 = start,
                is_temp = False,
                type = PyrexTypes.c_py_ssize_t_type
                )
2485 2486 2487 2488 2489 2490 2491

        parameters = self._unpack_encoding_and_error_mode(node.pos, args)
        if parameters is None:
            return node
        encoding, encoding_node, error_handling, error_handling_node = parameters

        # try to find a specific encoder function
2492 2493 2494
        codec_name = None
        if encoding is not None:
            codec_name = self._find_special_codec_name(encoding)
2495 2496
        if codec_name is not None:
            decode_function = "PyUnicode_Decode%s" % codec_name
2497
            node = ExprNodes.PythonCapiCallNode(
2498 2499 2500 2501 2502
                node.pos, decode_function,
                self.PyUnicode_DecodeXyz_func_type,
                args = [string_node, stop, error_handling_node],
                is_temp = node.is_temp,
                )
2503 2504 2505 2506 2507 2508 2509
        else:
            node = ExprNodes.PythonCapiCallNode(
                node.pos, "PyUnicode_Decode",
                self.PyUnicode_Decode_func_type,
                args = [string_node, stop, encoding_node, error_handling_node],
                is_temp = node.is_temp,
                )
2510

2511 2512 2513
        for temp in temps[::-1]:
            node = UtilNodes.EvalWithTempExprNode(temp, node)
        return node
2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528

    def _find_special_codec_name(self, encoding):
        try:
            requested_codec = codecs.getencoder(encoding)
        except:
            return None
        for name, codec in self._special_codecs:
            if codec == requested_codec:
                if '_' in name:
                    name = ''.join([ s.capitalize()
                                     for s in name.split('_')])
                return name
        return None

    def _unpack_encoding_and_error_mode(self, pos, args):
2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539
        null_node = ExprNodes.NullNode(pos)

        if len(args) >= 2:
            encoding_node = args[1]
            if isinstance(encoding_node, ExprNodes.CoerceToPyTypeNode):
                encoding_node = encoding_node.arg
            if isinstance(encoding_node, (ExprNodes.UnicodeNode, ExprNodes.StringNode,
                                          ExprNodes.BytesNode)):
                encoding = encoding_node.value
                encoding_node = ExprNodes.BytesNode(encoding_node.pos, value=encoding,
                                                     type=PyrexTypes.c_char_ptr_type)
2540 2541 2542 2543
            elif encoding_node.type is Builtin.bytes_type:
                encoding = None
                encoding_node = encoding_node.coerce_to(
                    PyrexTypes.c_char_ptr_type, self.current_env())
2544 2545 2546 2547
            elif encoding_node.type.is_string:
                encoding = None
            else:
                return None
2548
        else:
2549 2550
            encoding = None
            encoding_node = null_node
2551 2552 2553 2554 2555

        if len(args) == 3:
            error_handling_node = args[2]
            if isinstance(error_handling_node, ExprNodes.CoerceToPyTypeNode):
                error_handling_node = error_handling_node.arg
2556 2557 2558 2559 2560 2561 2562 2563 2564 2565
            if isinstance(error_handling_node,
                          (ExprNodes.UnicodeNode, ExprNodes.StringNode,
                           ExprNodes.BytesNode)):
                error_handling = error_handling_node.value
                if error_handling == 'strict':
                    error_handling_node = null_node
                else:
                    error_handling_node = ExprNodes.BytesNode(
                        error_handling_node.pos, value=error_handling,
                        type=PyrexTypes.c_char_ptr_type)
2566 2567 2568 2569
            elif error_handling_node.type is Builtin.bytes_type:
                error_handling = None
                error_handling_node = error_handling_node.coerce_to(
                    PyrexTypes.c_char_ptr_type, self.current_env())
2570 2571
            elif error_handling_node.type.is_string:
                error_handling = None
2572
            else:
2573
                return None
2574 2575 2576 2577
        else:
            error_handling = 'strict'
            error_handling_node = null_node

2578
        return (encoding, encoding_node, error_handling, error_handling_node)
2579

2580 2581 2582

    ### helpers

2583
    def _substitute_method_call(self, node, name, func_type,
2584
                                attr_name, is_unbound_method, args=(),
Stefan Behnel's avatar
Stefan Behnel committed
2585 2586
                                utility_code=None,
                                may_return_none=ExprNodes.PythonCapiCallNode.may_return_none):
2587
        args = list(args)
2588
        if args and not args[0].is_literal:
2589 2590
            self_arg = args[0]
            if is_unbound_method:
2591
                self_arg = self_arg.as_none_safe_node(
2592
                    "descriptor '%s' requires a '%s' object but received a 'NoneType'" % (
2593
                        attr_name, node.function.obj.name))
2594
            else:
2595
                self_arg = self_arg.as_none_safe_node(
2596 2597
                    "'NoneType' object has no attribute '%s'" % attr_name,
                    error = "PyExc_AttributeError")
2598
            args[0] = self_arg
2599
        return ExprNodes.PythonCapiCallNode(
2600
            node.pos, name, func_type,
2601
            args = args,
2602
            is_temp = node.is_temp,
Stefan Behnel's avatar
Stefan Behnel committed
2603 2604
            utility_code = utility_code,
            may_return_none = may_return_none,
2605 2606
            )

2607 2608 2609
    def _inject_int_default_argument(self, node, args, arg_index, type, default_value):
        assert len(args) >= arg_index
        if len(args) == arg_index:
2610 2611
            args.append(ExprNodes.IntNode(node.pos, value=str(default_value),
                                          type=type, constant_result=default_value))
2612
        else:
2613
            args[arg_index] = args[arg_index].coerce_to(type, self.current_env())
2614 2615 2616 2617

    def _inject_bint_default_argument(self, node, args, arg_index, default_value):
        assert len(args) >= arg_index
        if len(args) == arg_index:
2618 2619 2620
            default_value = bool(default_value)
            args.append(ExprNodes.BoolNode(node.pos, value=default_value,
                                           constant_result=default_value))
2621
        else:
2622
            args[arg_index] = args[arg_index].coerce_to_boolean(self.current_env())
2623

2624

2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636
py_unicode_istitle_utility_code = UtilityCode(
# Py_UNICODE_ISTITLE() doesn't match unicode.istitle() as the latter
# additionally allows character that comply with Py_UNICODE_ISUPPER()
proto = '''
static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar); /* proto */
''',
impl = '''
static CYTHON_INLINE int __Pyx_Py_UNICODE_ISTITLE(Py_UNICODE uchar) {
    return Py_UNICODE_ISTITLE(uchar) || Py_UNICODE_ISUPPER(uchar);
}
''')

2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663
unicode_tailmatch_utility_code = UtilityCode(
    # Python's unicode.startswith() and unicode.endswith() support a
    # tuple of prefixes/suffixes, whereas it's much more common to
    # test for a single unicode string.
proto = '''
static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr, \
Py_ssize_t start, Py_ssize_t end, int direction);
''',
impl = '''
static int __Pyx_PyUnicode_Tailmatch(PyObject* s, PyObject* substr,
                                     Py_ssize_t start, Py_ssize_t end, int direction) {
    if (unlikely(PyTuple_Check(substr))) {
        int result;
        Py_ssize_t i;
        for (i = 0; i < PyTuple_GET_SIZE(substr); i++) {
            result = PyUnicode_Tailmatch(s, PyTuple_GET_ITEM(substr, i),
                                         start, end, direction);
            if (result) {
                return result;
            }
        }
        return 0;
    }
    return PyUnicode_Tailmatch(s, substr, start, end, direction);
}
''',
)
2664

2665 2666
dict_getitem_default_utility_code = UtilityCode(
proto = '''
2667
static PyObject* __Pyx_PyDict_GetItemDefault(PyObject* d, PyObject* key, PyObject* default_value) {
2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688
    PyObject* value;
#if PY_MAJOR_VERSION >= 3
    value = PyDict_GetItemWithError(d, key);
    if (unlikely(!value)) {
        if (unlikely(PyErr_Occurred()))
            return NULL;
        value = default_value;
    }
    Py_INCREF(value);
#else
    if (PyString_CheckExact(key) || PyUnicode_CheckExact(key) || PyInt_CheckExact(key)) {
        /* these presumably have safe hash functions */
        value = PyDict_GetItem(d, key);
        if (unlikely(!value)) {
            value = default_value;
        }
        Py_INCREF(value);
    } else {
        PyObject *m;
        m = __Pyx_GetAttrString(d, "get");
        if (!m) return NULL;
2689 2690
        value = PyObject_CallFunctionObjArgs(m, key,
            (default_value == Py_None) ? NULL : default_value, NULL);
2691 2692 2693 2694 2695 2696 2697 2698 2699
        Py_DECREF(m);
    }
#endif
    return value;
}
''',
impl = ""
)

2700 2701
append_utility_code = UtilityCode(
proto = """
2702
static CYTHON_INLINE PyObject* __Pyx_PyObject_Append(PyObject* L, PyObject* x) {
2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719
    if (likely(PyList_CheckExact(L))) {
        if (PyList_Append(L, x) < 0) return NULL;
        Py_INCREF(Py_None);
        return Py_None; /* this is just to have an accurate signature */
    }
    else {
        PyObject *r, *m;
        m = __Pyx_GetAttrString(L, "append");
        if (!m) return NULL;
        r = PyObject_CallFunctionObjArgs(m, x, NULL);
        Py_DECREF(m);
        return r;
    }
}
""",
impl = ""
)
2720 2721


Robert Bradshaw's avatar
Robert Bradshaw committed
2722 2723
pop_utility_code = UtilityCode(
proto = """
2724
static CYTHON_INLINE PyObject* __Pyx_PyObject_Pop(PyObject* L) {
2725
    PyObject *r, *m;
2726
#if PY_VERSION_HEX >= 0x02040000
Robert Bradshaw's avatar
Robert Bradshaw committed
2727 2728 2729 2730 2731 2732
    if (likely(PyList_CheckExact(L))
            /* Check that both the size is positive and no reallocation shrinking needs to be done. */
            && likely(PyList_GET_SIZE(L) > (((PyListObject*)L)->allocated >> 1))) {
        Py_SIZE(L) -= 1;
        return PyList_GET_ITEM(L, PyList_GET_SIZE(L));
    }
2733 2734 2735 2736 2737 2738
#endif
    m = __Pyx_GetAttrString(L, "pop");
    if (!m) return NULL;
    r = PyObject_CallObject(m, NULL);
    Py_DECREF(m);
    return r;
Robert Bradshaw's avatar
Robert Bradshaw committed
2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750
}
""",
impl = ""
)

pop_index_utility_code = UtilityCode(
proto = """
static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix);
""",
impl = """
static PyObject* __Pyx_PyObject_PopIndex(PyObject* L, Py_ssize_t ix) {
    PyObject *r, *m, *t, *py_ix;
2751
#if PY_VERSION_HEX >= 0x02040000
Robert Bradshaw's avatar
Robert Bradshaw committed
2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769
    if (likely(PyList_CheckExact(L))) {
        Py_ssize_t size = PyList_GET_SIZE(L);
        if (likely(size > (((PyListObject*)L)->allocated >> 1))) {
            if (ix < 0) {
                ix += size;
            }
            if (likely(0 <= ix && ix < size)) {
                Py_ssize_t i;
                PyObject* v = PyList_GET_ITEM(L, ix);
                Py_SIZE(L) -= 1;
                size -= 1;
                for(i=ix; i<size; i++) {
                    PyList_SET_ITEM(L, i, PyList_GET_ITEM(L, i+1));
                }
                return v;
            }
        }
    }
2770
#endif
Robert Bradshaw's avatar
Robert Bradshaw committed
2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793
    py_ix = t = NULL;
    m = __Pyx_GetAttrString(L, "pop");
    if (!m) goto bad;
    py_ix = PyInt_FromSsize_t(ix);
    if (!py_ix) goto bad;
    t = PyTuple_New(1);
    if (!t) goto bad;
    PyTuple_SET_ITEM(t, 0, py_ix);
    py_ix = NULL;
    r = PyObject_CallObject(m, t);
    Py_DECREF(m);
    Py_DECREF(t);
    return r;
bad:
    Py_XDECREF(m);
    Py_XDECREF(t);
    Py_XDECREF(py_ix);
    return NULL;
}
"""
)


2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806
pyobject_as_double_utility_code = UtilityCode(
proto = '''
static double __Pyx__PyObject_AsDouble(PyObject* obj); /* proto */

#define __Pyx_PyObject_AsDouble(obj) \\
    ((likely(PyFloat_CheckExact(obj))) ? \\
     PyFloat_AS_DOUBLE(obj) : __Pyx__PyObject_AsDouble(obj))
''',
impl='''
static double __Pyx__PyObject_AsDouble(PyObject* obj) {
    PyObject* float_value;
    if (Py_TYPE(obj)->tp_as_number && Py_TYPE(obj)->tp_as_number->nb_float) {
        return PyFloat_AsDouble(obj);
2807
    } else if (PyUnicode_CheckExact(obj) || PyBytes_CheckExact(obj)) {
2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827
#if PY_MAJOR_VERSION >= 3
        float_value = PyFloat_FromString(obj);
#else
        float_value = PyFloat_FromString(obj, 0);
#endif
    } else {
        PyObject* args = PyTuple_New(1);
        if (unlikely(!args)) goto bad;
        PyTuple_SET_ITEM(args, 0, obj);
        float_value = PyObject_Call((PyObject*)&PyFloat_Type, args, 0);
        PyTuple_SET_ITEM(args, 0, 0);
        Py_DECREF(args);
    }
    if (likely(float_value)) {
        double value = PyFloat_AS_DOUBLE(float_value);
        Py_DECREF(float_value);
        return value;
    }
bad:
    return (double)-1;
2828
}
2829 2830 2831 2832
'''
)


2833 2834 2835 2836 2837 2838 2839 2840
bytes_index_utility_code = UtilityCode(
proto = """
static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* unicode, Py_ssize_t index, int check_bounds); /* proto */
""",
impl = """
static CYTHON_INLINE char __Pyx_PyBytes_GetItemInt(PyObject* bytes, Py_ssize_t index, int check_bounds) {
    if (check_bounds) {
        if (unlikely(index >= PyBytes_GET_SIZE(bytes)) |
2841
            ((index < 0) & unlikely(index < -PyBytes_GET_SIZE(bytes)))) {
2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853
            PyErr_Format(PyExc_IndexError, "string index out of range");
            return -1;
        }
    }
    if (index < 0)
        index += PyBytes_GET_SIZE(bytes);
    return PyBytes_AS_STRING(bytes)[index];
}
"""
)


2854 2855
tpnew_utility_code = UtilityCode(
proto = """
2856
static CYTHON_INLINE PyObject* __Pyx_tp_new(PyObject* type_obj) {
2857 2858 2859 2860 2861 2862 2863
    return (PyObject*) (((PyTypeObject*)(type_obj))->tp_new(
        (PyTypeObject*)(type_obj), %(TUPLE)s, NULL));
}
""" % {'TUPLE' : Naming.empty_tuple}
)


2864 2865 2866 2867
class ConstantFolding(Visitor.VisitorTransform, SkipDeclarations):
    """Calculate the result of constant expressions to store it in
    ``expr_node.constant_result``, and replace trivial cases by their
    constant result.
2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878

    General rules:

    - We calculate float constants to make them available to the
      compiler, but we do not aggregate them into a single literal
      node to prevent any loss of precision.

    - We recursively calculate constants from non-literal nodes to
      make them available to the compiler, but we only aggregate
      literal nodes at each step.  Non-literal nodes are never merged
      into a single node.
2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890 2891 2892
    """
    def _calculate_const(self, node):
        if node.constant_result is not ExprNodes.constant_value_not_set:
            return

        # make sure we always set the value
        not_a_constant = ExprNodes.not_a_constant
        node.constant_result = not_a_constant

        # check if all children are constant
        children = self.visitchildren(node)
        for child_result in children.itervalues():
            if type(child_result) is list:
                for child in child_result:
Stefan Behnel's avatar
Stefan Behnel committed
2893
                    if getattr(child, 'constant_result', not_a_constant) is not_a_constant:
2894
                        return
Stefan Behnel's avatar
Stefan Behnel committed
2895
            elif getattr(child_result, 'constant_result', not_a_constant) is not_a_constant:
2896 2897 2898 2899 2900 2901 2902
                return

        # now try to calculate the real constant value
        try:
            node.calculate_constant_result()
#            if node.constant_result is not ExprNodes.not_a_constant:
#                print node.__class__.__name__, node.constant_result
2903
        except (ValueError, TypeError, KeyError, IndexError, AttributeError, ArithmeticError):
2904 2905 2906 2907 2908 2909 2910
            # ignore all 'normal' errors here => no constant result
            pass
        except Exception:
            # this looks like a real error
            import traceback, sys
            traceback.print_exc(file=sys.stdout)

2911 2912 2913 2914 2915 2916 2917 2918 2919 2920
    NODE_TYPE_ORDER = (ExprNodes.CharNode, ExprNodes.IntNode,
                       ExprNodes.LongNode, ExprNodes.FloatNode)

    def _widest_node_class(self, *nodes):
        try:
            return self.NODE_TYPE_ORDER[
                max(map(self.NODE_TYPE_ORDER.index, map(type, nodes)))]
        except ValueError:
            return None

2921 2922 2923 2924
    def visit_ExprNode(self, node):
        self._calculate_const(node)
        return node

2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945
    def visit_UnaryMinusNode(self, node):
        self._calculate_const(node)
        if node.constant_result is ExprNodes.not_a_constant:
            return node
        if not node.operand.is_literal:
            return node
        if isinstance(node.operand, ExprNodes.LongNode):
            return ExprNodes.LongNode(node.pos, value = '-' + node.operand.value,
                                      constant_result = node.constant_result)
        if isinstance(node.operand, ExprNodes.FloatNode):
            # this is a safe operation
            return ExprNodes.FloatNode(node.pos, value = '-' + node.operand.value,
                                       constant_result = node.constant_result)
        node_type = node.operand.type
        if node_type.is_int and node_type.signed or \
               isinstance(node.operand, ExprNodes.IntNode) and node_type.is_pyobject:
            return ExprNodes.IntNode(node.pos, value = '-' + node.operand.value,
                                     type = node_type,
                                     constant_result = node.constant_result)
        return node

2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963
    def visit_BoolBinopNode(self, node):
        self._calculate_const(node)
        if node.constant_result is ExprNodes.not_a_constant:
            return node
        if not node.operand1.is_literal or not node.operand2.is_literal:
            # We calculate other constants to make them available to
            # the compiler, but we only aggregate constant nodes
            # recursively, so non-const nodes are straight out.
            return node

        if node.constant_result == node.operand1.constant_result and node.operand1.is_literal:
            return node.operand1
        elif node.constant_result == node.operand2.constant_result and node.operand2.is_literal:
            return node.operand2
        else:
            # FIXME: we could do more ...
            return node

2964 2965 2966 2967
    def visit_BinopNode(self, node):
        self._calculate_const(node)
        if node.constant_result is ExprNodes.not_a_constant:
            return node
2968 2969 2970 2971 2972
        if isinstance(node.constant_result, float):
            # We calculate float constants to make them available to
            # the compiler, but we do not aggregate them into a
            # constant node to prevent any loss of precision.
            return node
2973
        if not node.operand1.is_literal or not node.operand2.is_literal:
2974 2975 2976 2977 2978 2979
            # We calculate other constants to make them available to
            # the compiler, but we only aggregate constant nodes
            # recursively, so non-const nodes are straight out.
            return node

        # now inject a new constant node with the calculated value
2980
        try:
2981 2982
            type1, type2 = node.operand1.type, node.operand2.type
            if type1 is None or type2 is None:
2983 2984 2985 2986
                return node
        except AttributeError:
            return node

2987 2988 2989 2990 2991
        if type1 is type2:
            new_node = node.operand1
        else:
            widest_type = PyrexTypes.widest_numeric_type(type1, type2)
            if type(node.operand1) is type(node.operand2):
2992
                new_node = node.operand1
2993 2994
                new_node.type = widest_type
            elif type1 is widest_type:
2995
                new_node = node.operand1
2996 2997
            elif type2 is widest_type:
                new_node = node.operand2
2998
            else:
2999 3000 3001 3002 3003
                target_class = self._widest_node_class(
                    node.operand1, node.operand2)
                if target_class is None:
                    return node
                new_node = target_class(pos=node.pos, type = widest_type)
3004 3005

        new_node.constant_result = node.constant_result
3006 3007 3008 3009
        if isinstance(node, ExprNodes.BoolNode):
            new_node.value = node.constant_result
        else:
            new_node.value = str(node.constant_result)
3010 3011
        return new_node

3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025
    def visit_PrimaryCmpNode(self, node):
        self._calculate_const(node)
        if node.constant_result is ExprNodes.not_a_constant:
            return node
        bool_result = bool(node.constant_result)
        return ExprNodes.BoolNode(node.pos, value=bool_result,
                                  constant_result=bool_result)

    def visit_IfStatNode(self, node):
        self.visitchildren(node)
        # eliminate dead code based on constant condition results
        if_clauses = []
        for if_clause in node.if_clauses:
            condition_result = if_clause.get_constant_condition_result()
3026 3027
            if condition_result is None:
                # unknown result => normal runtime evaluation
3028
                if_clauses.append(if_clause)
3029 3030 3031 3032 3033 3034
            elif condition_result == True:
                # subsequent clauses can safely be dropped
                node.else_clause = if_clause.body
                break
            else:
                assert condition_result == False
3035
        if not if_clauses:
3036 3037 3038
            return node.else_clause
        node.if_clauses = if_clauses
        return node
3039

3040 3041
    # in the future, other nodes can have their own handler method here
    # that can replace them with a constant result node
Stefan Behnel's avatar
Stefan Behnel committed
3042

3043
    visit_Node = Visitor.VisitorTransform.recurse_to_children
3044 3045


3046 3047 3048 3049 3050 3051
class FinalOptimizePhase(Visitor.CythonTransform):
    """
    This visitor handles several commuting optimizations, and is run
    just before the C code generation phase. 
    
    The optimizations currently implemented in this class are: 
Stefan Behnel's avatar
Stefan Behnel committed
3052
        - eliminate None assignment and refcounting for first assignment. 
3053
        - isinstance -> typecheck for cdef types
Stefan Behnel's avatar
Stefan Behnel committed
3054
        - eliminate checks for None and/or types that became redundant after tree changes
3055
    """
3056
    def visit_SingleAssignmentNode(self, node):
3057 3058 3059 3060
        """Avoid redundant initialisation of local variables before their
        first assignment.
        """
        self.visitchildren(node)
3061 3062
        if node.first:
            lhs = node.lhs
3063
            lhs.lhs_of_first_assignment = True
3064 3065 3066 3067 3068
            if isinstance(lhs, ExprNodes.NameNode) and lhs.entry.type.is_pyobject:
                # Have variable initialized to 0 rather than None
                lhs.entry.init_to_none = False
                lhs.entry.init = 0
        return node
3069

3070
    def visit_SimpleCallNode(self, node):
3071 3072 3073
        """Replace generic calls to isinstance(x, type) by a more efficient
        type check.
        """
3074
        self.visitchildren(node)
Robert Bradshaw's avatar
Robert Bradshaw committed
3075
        if node.function.type.is_cfunction and isinstance(node.function, ExprNodes.NameNode):
3076 3077 3078
            if node.function.name == 'isinstance':
                type_arg = node.args[1]
                if type_arg.type.is_builtin_type and type_arg.type.name == 'type':
3079 3080
                    from CythonScope import utility_scope
                    node.function.entry = utility_scope.lookup('PyObject_TypeCheck')
3081
                    node.function.type = node.function.entry.type
3082
                    PyTypeObjectPtr = PyrexTypes.CPtrType(utility_scope.lookup('PyTypeObject').type)
3083 3084
                    node.args[1] = ExprNodes.CastNode(node.args[1], PyTypeObjectPtr)
        return node
Stefan Behnel's avatar
Stefan Behnel committed
3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095

    def visit_PyTypeTestNode(self, node):
        """Remove tests for alternatively allowed None values from
        type tests when we know that the argument cannot be None
        anyway.
        """
        self.visitchildren(node)
        if not node.notnone:
            if not node.arg.may_be_none():
                node.notnone = True
        return node