Optimize.py 130 KB
Newer Older
1 2 3 4 5 6

import cython
cython.declare(UtilityCode=object, EncodedString=object, BytesLiteral=object,
               Nodes=object, ExprNodes=object, PyrexTypes=object, Builtin=object,
               UtilNodes=object, Naming=object)

7 8
import Nodes
import ExprNodes
9
import PyrexTypes
10
import Visitor
11 12 13 14
import Builtin
import UtilNodes
import TypeSlots
import Symtab
15
import Options
16
import Naming
17

18
from Code import UtilityCode
19
from StringEncoding import EncodedString, BytesLiteral
20
from Errors import error
21 22
from ParseTreeTransforms import SkipDeclarations

23 24
import codecs

25
try:
26 27
    from __builtin__ import reduce
except ImportError:
28 29
    from functools import reduce

30 31 32 33 34
try:
    from __builtin__ import basestring
except ImportError:
    basestring = str # Python 3

35
def load_c_utility(name):
36
    return UtilityCode.load_cached(name, "Optimize.c")
37

38 39 40 41
class FakePythonEnv(object):
    "A fake environment for creating type test nodes etc."
    nogil = False

42 43 44 45 46
def unwrap_coerced_node(node, coercion_nodes=(ExprNodes.CoerceToPyTypeNode, ExprNodes.CoerceFromPyTypeNode)):
    if isinstance(node, coercion_nodes):
        return node.arg
    return node

47
def unwrap_node(node):
48 49
    while isinstance(node, UtilNodes.ResultRefNode):
        node = node.expression
50
    return node
51 52

def is_common_value(a, b):
53 54
    a = unwrap_node(a)
    b = unwrap_node(b)
55 56 57
    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):
58
        return not a.is_py_attr and is_common_value(a.obj, b.obj) and a.attribute == b.attribute
59 60
    return False

61 62 63 64
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
65
    - for-in-enumerate is replaced by an external counter variable
66
    - for-in-range loop becomes a plain C for loop
67
    """
68
    visit_Node = Visitor.VisitorTransform.recurse_to_children
Stefan Behnel's avatar
Stefan Behnel committed
69

70 71
    def visit_ModuleNode(self, node):
        self.current_scope = node.scope
72
        self.module_scope = node.scope
73 74 75 76 77 78 79 80 81
        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
82

83 84
    def visit_PrimaryCmpNode(self, node):
        if node.is_ptr_contains():
85

86 87 88 89 90 91
            # for t in operand2:
            #     if operand1 == t:
            #         res = True
            #         break
            # else:
            #     res = False
92

93 94 95 96 97 98 99 100 101 102 103 104 105
            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(
106
                pos,
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
                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)
125

126 127 128 129 130 131 132
            if node.operator == 'not_in':
                new_node = ExprNodes.NotNode(pos, operand=new_node)
            return new_node

        else:
            self.visitchildren(node)
            return node
133

134 135
    def visit_ForInStatNode(self, node):
        self.visitchildren(node)
136
        return self._optimise_for_loop(node, node.iterator.sequence)
137

138
    def _optimise_for_loop(self, node, iterator, reversed=False):
139 140
        if iterator.type is Builtin.dict_type:
            # like iterating over dict.keys()
141
            if reversed:
Stefan Behnel's avatar
Stefan Behnel committed
142
                # CPython raises an error here: not a sequence
143
                return node
Stefan Behnel's avatar
Stefan Behnel committed
144
            return self._transform_dict_iteration(
145
                node, dict_obj=iterator, method=None, keys=True, values=False)
146

147
        # C array (slice) iteration?
148
        if iterator.type.is_ptr or iterator.type.is_array:
149
            return self._transform_carray_iteration(node, iterator, reversed=reversed)
150 151 152 153
        if iterator.type is Builtin.bytes_type:
            return self._transform_bytes_iteration(node, iterator, reversed=reversed)
        if iterator.type is Builtin.unicode_type:
            return self._transform_unicode_iteration(node, iterator, reversed=reversed)
154 155 156

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

159 160 161 162 163 164 165
        if iterator.args is None:
            arg_count = iterator.arg_tuple and len(iterator.arg_tuple.args) or 0
        else:
            arg_count = len(iterator.args)
            if arg_count and iterator.self is not None:
                arg_count -= 1

Stefan Behnel's avatar
Stefan Behnel committed
166
        function = iterator.function
167
        # dict iteration?
168
        if function.is_attribute and not reversed and not arg_count:
169
            base_obj = iterator.self or function.obj
170 171
            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
                keys = values = True
180 181 182 183

            if keys or values:
                return self._transform_dict_iteration(
                    node, base_obj, method, keys, values)
184

185
        # enumerate/reversed ?
Stefan Behnel's avatar
Stefan Behnel committed
186
        if iterator.self is None and function.is_name and \
187 188 189
               function.entry and function.entry.is_builtin:
            if function.name == 'enumerate':
                if reversed:
Stefan Behnel's avatar
Stefan Behnel committed
190
                    # CPython raises an error here: not a sequence
191 192 193 194
                    return node
                return self._transform_enumerate_iteration(node, iterator)
            elif function.name == 'reversed':
                if reversed:
Stefan Behnel's avatar
Stefan Behnel committed
195
                    # CPython raises an error here: not a sequence
196 197
                    return node
                return self._transform_reversed_iteration(node, iterator)
198

199 200
        # range() iteration?
        if Options.convert_range and node.target.type.is_int:
Stefan Behnel's avatar
Stefan Behnel committed
201 202 203
            if iterator.self is None and function.is_name and \
                   function.entry and function.entry.is_builtin and \
                   function.name in ('range', 'xrange'):
204
                return self._transform_range_iteration(node, iterator, reversed=reversed)
205

Stefan Behnel's avatar
Stefan Behnel committed
206
        return node
207

208 209 210 211 212 213 214 215 216 217
    def _transform_reversed_iteration(self, node, reversed_function):
        args = reversed_function.arg_tuple.args
        if len(args) == 0:
            error(reversed_function.pos,
                  "reversed() requires an iterable argument")
            return node
        elif len(args) > 1:
            error(reversed_function.pos,
                  "reversed() takes exactly 1 argument")
            return node
218 219 220 221 222 223 224 225 226
        arg = args[0]

        # reversed(list/tuple) ?
        if arg.type in (Builtin.tuple_type, Builtin.list_type):
            node.iterator.sequence = arg.as_none_safe_node("'NoneType' object is not iterable")
            node.iterator.reversed = True
            return node

        return self._optimise_for_loop(node, arg, reversed=True)
227

228 229 230 231 232 233 234 235 236 237
    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)
            ])

238 239
    def _transform_bytes_iteration(self, node, slice_node, reversed=False):
        target_type = node.target.type
240
        if not target_type.is_int and target_type is not Builtin.bytes_type:
241 242
            # bytes iteration returns bytes objects in Py2, but
            # integers in Py3
243 244 245
            return node

        unpack_temp_node = UtilNodes.LetRefNode(
246
            slice_node.as_none_safe_node("'NoneType' is not iterable"))
247 248

        slice_base_node = ExprNodes.PythonCapiCallNode(
249 250
            slice_node.pos, "PyBytes_AS_STRING",
            self.PyBytes_AS_STRING_func_type,
251 252 253 254
            args = [unpack_temp_node],
            is_temp = 0,
            )
        len_node = ExprNodes.PythonCapiCallNode(
255 256
            slice_node.pos, "PyBytes_GET_SIZE",
            self.PyBytes_GET_SIZE_func_type,
257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
            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,
273 274
                    ),
                reversed = reversed))
275

276 277 278 279 280 281 282
    PyUnicode_READ_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ucs4_type, [
            PyrexTypes.CFuncTypeArg("kind", PyrexTypes.c_int_type, None),
            PyrexTypes.CFuncTypeArg("data", PyrexTypes.c_void_ptr_type, None),
            PyrexTypes.CFuncTypeArg("index", PyrexTypes.c_py_ssize_t_type, None)
        ])

283 284 285 286 287 288 289 290
    init_unicode_iteration_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_int_type, [
            PyrexTypes.CFuncTypeArg("s", PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("length", PyrexTypes.c_py_ssize_t_ptr_type, None),
            PyrexTypes.CFuncTypeArg("data", PyrexTypes.c_void_ptr_ptr_type, None),
            PyrexTypes.CFuncTypeArg("kind", PyrexTypes.c_int_ptr_type, None)
        ],
        exception_value = '-1')
291 292 293 294 295 296 297

    def _transform_unicode_iteration(self, node, slice_node, reversed=False):
        unpack_temp_node = UtilNodes.LetRefNode(
            slice_node.as_none_safe_node("'NoneType' is not iterable"))

        start_node = ExprNodes.IntNode(
            node.pos, value='0', constant_result=0, type=PyrexTypes.c_py_ssize_t_type)
298 299
        length_temp = UtilNodes.TempHandle(PyrexTypes.c_py_ssize_t_type)
        end_node = length_temp.ref(node.pos)
300 301 302 303 304 305
        if reversed:
            relation1, relation2 = '>', '>='
            start_node, end_node = end_node, start_node
        else:
            relation1, relation2 = '<=', '<'

306 307 308
        kind_temp = UtilNodes.TempHandle(PyrexTypes.c_int_type)
        data_temp = UtilNodes.TempHandle(PyrexTypes.c_void_ptr_type)
        counter_temp = UtilNodes.TempHandle(PyrexTypes.c_py_ssize_t_type)
309

310 311 312
        target_value = ExprNodes.PythonCapiCallNode(
            slice_node.pos, "__Pyx_PyUnicode_READ",
            self.PyUnicode_READ_func_type,
313 314 315
            args = [kind_temp.ref(slice_node.pos),
                    data_temp.ref(slice_node.pos),
                    counter_temp.ref(node.target.pos)],
316 317 318 319 320
            is_temp = False,
            )
        if target_value.type != node.target.type:
            target_value = target_value.coerce_to(node.target.type,
                                                  self.current_scope)
321 322 323
        target_assign = Nodes.SingleAssignmentNode(
            pos = node.target.pos,
            lhs = node.target,
324
            rhs = target_value)
325 326 327 328 329 330 331
        body = Nodes.StatListNode(
            node.pos,
            stats = [target_assign, node.body])

        loop_node = Nodes.ForFromStatNode(
            node.pos,
            bound1=start_node, relation1=relation1,
332
            target=counter_temp.ref(node.target.pos),
333 334 335 336 337
            relation2=relation2, bound2=end_node,
            step=None, body=body,
            else_clause=node.else_clause,
            from_range=True)

338 339 340
        setup_node = Nodes.ExprStatNode(
            node.pos,
            expr = ExprNodes.PythonCapiCallNode(
341 342 343 344 345 346 347 348 349 350
                slice_node.pos, "__Pyx_init_unicode_iteration",
                self.init_unicode_iteration_func_type,
                args = [unpack_temp_node,
                        ExprNodes.AmpersandNode(slice_node.pos, operand=length_temp.ref(slice_node.pos),
                                                type=PyrexTypes.c_py_ssize_t_ptr_type),
                        ExprNodes.AmpersandNode(slice_node.pos, operand=data_temp.ref(slice_node.pos),
                                                type=PyrexTypes.c_void_ptr_ptr_type),
                        ExprNodes.AmpersandNode(slice_node.pos, operand=kind_temp.ref(slice_node.pos),
                                                type=PyrexTypes.c_int_ptr_type),
                        ],
351 352
                is_temp = True,
                result_is_used = False,
353
                utility_code=UtilityCode.load_cached("unicode_iter", "Optimize.c"),
354 355 356
                ))
        return UtilNodes.LetNode(
            unpack_temp_node,
357 358 359
            UtilNodes.TempsBlockNode(
                node.pos, temps=[counter_temp, length_temp, data_temp, kind_temp],
                body=Nodes.StatListNode(node.pos, stats=[setup_node, loop_node])))
360

361
    def _transform_carray_iteration(self, node, slice_node, reversed=False):
362
        neg_step = False
363 364 365 366 367 368
        if isinstance(slice_node, ExprNodes.SliceIndexNode):
            slice_base = slice_node.base
            start = slice_node.start
            stop = slice_node.stop
            step = None
            if not stop:
369 370
                if not slice_base.type.is_pyobject:
                    error(slice_node.pos, "C array iteration requires known end index")
371
                return node
372

373
        elif isinstance(slice_node, ExprNodes.IndexNode):
374
            assert isinstance(slice_node.index, ExprNodes.SliceNode)
375 376
            slice_base = slice_node.base
            index = slice_node.index
377 378 379 380 381 382 383 384 385 386
            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:
387 388
                    if not slice_base.type.is_pyobject:
                        error(step.pos, "C array iteration requires known step size and end index")
389 390 391
                    return node
                else:
                    # step sign is handled internally by ForFromStatNode
392 393 394 395
                    step_value = step.constant_result
                    if reversed:
                        step_value = -step_value
                    neg_step = step_value < 0
396
                    step = ExprNodes.IntNode(step.pos, type=PyrexTypes.c_py_ssize_t_type,
397 398
                                             value=str(abs(step_value)),
                                             constant_result=abs(step_value))
399

400 401
        elif slice_node.type.is_array:
            if slice_node.type.size is None:
Stefan Behnel's avatar
Stefan Behnel committed
402
                error(slice_node.pos, "C array iteration requires known end index")
403
                return node
404 405 406
            slice_base = slice_node
            start = None
            stop = ExprNodes.IntNode(
407 408
                slice_node.pos, value=str(slice_node.type.size),
                type=PyrexTypes.c_py_ssize_t_type, constant_result=slice_node.type.size)
409
            step = None
410

411
        else:
412
            if not slice_node.type.is_pyobject:
413
                error(slice_node.pos, "C array iteration requires known end index")
414 415
            return node

416 417 418 419 420 421 422 423 424 425
        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)
426 427 428 429 430 431 432
        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
433

434 435 436 437 438 439 440
        if reversed:
            if not start:
                start = ExprNodes.IntNode(slice_node.pos, value="0",  constant_result=0,
                                          type=PyrexTypes.c_py_ssize_t_type)
            # if step was provided, it was already negated above
            start, stop = stop, start

441 442 443 444
        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)
445

446
        if start and start.constant_result != 0:
447 448 449 450 451
            start_ptr_node = ExprNodes.AddNode(
                start.pos,
                operand1=carray_ptr,
                operator='+',
                operand2=start,
452
                type=ptr_type)
453
        else:
454
            start_ptr_node = carray_ptr
455

456 457 458 459 460 461 462 463 464 465
        if stop and stop.constant_result != 0:
            stop_ptr_node = ExprNodes.AddNode(
                stop.pos,
                operand1=ExprNodes.CloneNode(carray_ptr),
                operator='+',
                operand2=stop,
                type=ptr_type
                ).coerce_to_simple(self.current_scope)
        else:
            stop_ptr_node = ExprNodes.CloneNode(carray_ptr)
466

467
        counter = UtilNodes.TempHandle(ptr_type)
468 469
        counter_temp = counter.ref(node.target.pos)

470
        if slice_base.type.is_string and node.target.type.is_pyobject:
471
            # special case: char* -> bytes
472 473
            target_value = ExprNodes.SliceIndexNode(
                node.target.pos,
474 475 476 477 478 479 480
                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,
481 482
                type=Builtin.bytes_type,
                is_temp=1)
483 484 485
        elif node.target.type.is_ptr and not node.target.type.assignable_from(ptr_type.base_type):
            # Allow iteration with pointer target to avoid copy.
            target_value = counter_temp
486 487 488
        else:
            target_value = ExprNodes.IndexNode(
                node.target.pos,
489 490 491 492
                index=ExprNodes.IntNode(node.target.pos, value='0',
                                        constant_result=0,
                                        type=PyrexTypes.c_int_type),
                base=counter_temp,
493
                is_buffer_access=False,
494
                type=ptr_type.base_type)
495 496 497 498 499 500 501 502 503 504 505 506 507 508

        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])

509 510
        relation1, relation2 = self._find_for_from_node_relations(neg_step, reversed)

511 512
        for_node = Nodes.ForFromStatNode(
            node.pos,
513
            bound1=start_ptr_node, relation1=relation1,
514
            target=counter_temp,
515
            relation2=relation2, bound2=stop_ptr_node,
516 517 518 519 520 521 522 523
            step=step, body=body,
            else_clause=node.else_clause,
            from_range=True)

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

524 525 526 527 528 529
    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
530
        elif len(args) > 2:
531
            error(enumerate_function.pos,
532
                  "enumerate() takes at most 2 arguments")
533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552
            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

553 554 555 556 557 558 559 560 561
        if len(args) == 2:
            start = unwrap_coerced_node(args[1]).coerce_to(counter_type, self.current_scope)
        else:
            start = ExprNodes.IntNode(enumerate_function.pos,
                                      value='0',
                                      type=counter_type,
                                      constant_result=0)
        temp = UtilNodes.LetRefNode(start)

562 563
        inc_expression = ExprNodes.AddNode(
            enumerate_function.pos,
564
            operand1 = temp,
565
            operand2 = ExprNodes.IntNode(node.pos, value='1',
566 567
                                         type=counter_type,
                                         constant_result=1),
568 569 570 571 572
            operator = '+',
            type = counter_type,
            is_temp = counter_type.is_pyobject
            )

573 574 575 576
        loop_body = [
            Nodes.SingleAssignmentNode(
                pos = enumerate_target.pos,
                lhs = enumerate_target,
577
                rhs = temp),
578 579
            Nodes.SingleAssignmentNode(
                pos = enumerate_target.pos,
580
                lhs = temp,
581 582
                rhs = inc_expression)
            ]
583

584 585 586 587 588 589 590
        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)
591 592

        node.target = iterable_target
593
        node.item = node.item.coerce_to(iterable_target.type, self.current_scope)
594
        node.iterator.sequence = args[0]
595 596

        # recurse into loop to check for further optimisations
597
        return UtilNodes.LetNode(temp, self._optimise_for_loop(node, node.iterator.sequence))
598

599 600 601 602 603 604 605 606 607 608 609
    def _find_for_from_node_relations(self, neg_step_value, reversed):
        if reversed:
            if neg_step_value:
                return '<', '<='
            else:
                return '>', '>='
        else:
            if neg_step_value:
                return '>=', '>'
            else:
                return '<=', '<'
610

611
    def _transform_range_iteration(self, node, range_function, reversed=False):
612 613 614 615
        args = range_function.arg_tuple.args
        if len(args) < 3:
            step_pos = range_function.pos
            step_value = 1
616 617
            step = ExprNodes.IntNode(step_pos, value='1',
                                     constant_result=1)
618 619 620
        else:
            step = args[2]
            step_pos = step.pos
621
            if not isinstance(step.constant_result, (int, long)):
622 623
                # cannot determine step direction
                return node
624 625 626
            step_value = step.constant_result
            if step_value == 0:
                # will lead to an error elsewhere
627
                return node
628 629 630
            if reversed and step_value not in (1, -1):
                # FIXME: currently broken - requires calculation of the correct bounds
                return node
631
            if not isinstance(step, ExprNodes.IntNode):
632 633
                step = ExprNodes.IntNode(step_pos, value=str(step_value),
                                         constant_result=step_value)
634 635

        if len(args) == 1:
636 637
            bound1 = ExprNodes.IntNode(range_function.pos, value='0',
                                       constant_result=0)
638
            bound2 = args[0].coerce_to_integer(self.current_scope)
639
        else:
640 641
            bound1 = args[0].coerce_to_integer(self.current_scope)
            bound2 = args[1].coerce_to_integer(self.current_scope)
642

643 644
        relation1, relation2 = self._find_for_from_node_relations(step_value < 0, reversed)

645 646 647 648 649 650 651 652 653 654
        if reversed:
            bound1, bound2 = bound2, bound1
            if step_value < 0:
                step_value = -step_value
        else:
            if step_value < 0:
                step_value = -step_value

        step.value = str(step_value)
        step.constant_result = step_value
655
        step = step.coerce_to_integer(self.current_scope)
656

657
        if not bound2.is_literal:
658 659 660 661 662 663
            # stop bound must be immutable => keep it in a temp var
            bound2_is_temp = True
            bound2 = UtilNodes.LetRefNode(bound2)
        else:
            bound2_is_temp = False

664 665 666 667 668 669 670
        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
671
            from_range=True)
672 673 674 675

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

676 677
        return for_node

678
    def _transform_dict_iteration(self, node, dict_obj, method, keys, values):
679
        temps = []
680 681 682
        temp = UtilNodes.TempHandle(PyrexTypes.py_object_type)
        temps.append(temp)
        dict_temp = temp.ref(dict_obj.pos)
683 684
        temp = UtilNodes.TempHandle(PyrexTypes.c_py_ssize_t_type)
        temps.append(temp)
685
        pos_temp = temp.ref(node.pos)
686

687
        key_target = value_target = tuple_target = None
688 689 690 691 692
        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
693
                    # unusual case that may or may not lead to an error
694 695 696
                    return node
            else:
                tuple_target = node.target
697 698
        elif keys:
            key_target = node.target
699
        else:
700
            value_target = node.target
701 702 703 704 705 706 707 708 709 710

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

        # keep original length to guard against dict modification
        dict_len_temp = UtilNodes.TempHandle(PyrexTypes.c_py_ssize_t_type)
        temps.append(dict_len_temp)
711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737
        dict_len_temp_addr = ExprNodes.AmpersandNode(
            node.pos, operand=dict_len_temp.ref(dict_obj.pos),
            type=PyrexTypes.c_ptr_type(dict_len_temp.type))
        temp = UtilNodes.TempHandle(PyrexTypes.c_int_type)
        temps.append(temp)
        is_dict_temp = temp.ref(node.pos)
        is_dict_temp_addr = ExprNodes.AmpersandNode(
            node.pos, operand=is_dict_temp,
            type=PyrexTypes.c_ptr_type(temp.type))

        iter_next_node = Nodes.DictIterationNextNode(
            dict_temp, dict_len_temp.ref(dict_obj.pos), pos_temp,
            key_target, value_target, tuple_target,
            is_dict_temp)
        iter_next_node.analyse_expressions(self.current_scope)
        body.stats[0:0] = [iter_next_node]

        if method:
            method_node = ExprNodes.StringNode(
                dict_obj.pos, is_identifier=True, value=method)
            dict_obj = dict_obj.as_none_safe_node(
                "'NoneType' object has no attribute '%s'",
                error = "PyExc_AttributeError",
                format_args = [method])
        else:
            method_node = ExprNodes.NullNode(dict_obj.pos)
            dict_obj = dict_obj.as_none_safe_node("'NoneType' object is not iterable")
738

739 740 741
        def flag_node(value):
            value = value and 1 or 0
            return ExprNodes.IntNode(node.pos, value=str(value), constant_result=value)
742 743

        result_code = [
744 745 746
            Nodes.SingleAssignmentNode(
                pos = node.pos,
                lhs = pos_temp,
747 748
                rhs = ExprNodes.IntNode(node.pos, value='0',
                                        constant_result=0)),
749 750
            Nodes.SingleAssignmentNode(
                pos = dict_obj.pos,
751 752 753 754 755 756
                lhs = dict_temp,
                rhs = ExprNodes.PythonCapiCallNode(
                    dict_obj.pos,
                    "__Pyx_dict_iterator",
                    self.PyDict_Iterator_func_type,
                    utility_code = UtilityCode.load_cached("dict_iter", "Optimize.c"),
757
                    args = [dict_obj, flag_node(dict_obj.type is Builtin.dict_type),
758 759 760
                            method_node, dict_len_temp_addr, is_dict_temp_addr,
                            ],
                    is_temp=True,
761 762 763 764
                )),
            Nodes.WhileStatNode(
                pos = node.pos,
                condition = None,
765 766 767 768 769 770 771 772
                body = body,
                else_clause = node.else_clause
                )
            ]

        return UtilNodes.TempsBlockNode(
            node.pos, temps=temps,
            body=Nodes.StatListNode(
773
                node.pos,
774 775 776
                stats = result_code
                ))

777 778 779 780 781 782 783 784 785
    PyDict_Iterator_func_type = PyrexTypes.CFuncType(
        PyrexTypes.py_object_type, [
            PyrexTypes.CFuncTypeArg("dict",  PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("is_dict",  PyrexTypes.c_int_type, None),
            PyrexTypes.CFuncTypeArg("method_name",  PyrexTypes.py_object_type, None),
            PyrexTypes.CFuncTypeArg("p_orig_length",  PyrexTypes.c_py_ssize_t_ptr_type, None),
            PyrexTypes.CFuncTypeArg("p_is_dict",  PyrexTypes.c_int_ptr_type, None),
            ])

786

787 788
class SwitchTransform(Visitor.VisitorTransform):
    """
789
    This transformation tries to turn long if statements into C switch statements.
790
    The requirement is that every clause be an (or of) var == value, where the var
791
    is common among all clauses and both var and value are ints.
792
    """
793 794 795
    NO_MATCH = (None, None, None)

    def extract_conditions(self, cond, allow_not_in):
796 797 798 799 800 801 802 803 804 805
        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
806

807
        if isinstance(cond, ExprNodes.PrimaryCmpNode):
808 809 810 811 812 813 814 815 816 817 818 819 820 821 822
            if cond.cascade is not None:
                return self.NO_MATCH
            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
                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
                return not_in, cond.operand1, self.extract_in_string_conditions(cond.operand2)
            elif not cond.is_python_comparison():
823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852
                if cond.operator == '==':
                    not_in = False
                elif allow_not_in and cond.operator == '!=':
                    not_in = True
                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

853 854
    def extract_in_string_conditions(self, string_literal):
        if isinstance(string_literal, ExprNodes.UnicodeNode):
855
            charvals = list(map(ord, set(string_literal.value)))
856 857 858 859 860 861 862 863 864
            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
865 866
            characters = list(set([ characters[i:i+1] for i in range(len(characters)) ]))
            characters.sort()
867 868 869 870
            return [ ExprNodes.CharNode(string_literal.pos, value=charval,
                                        constant_result=charval)
                     for charval in characters ]

871 872
    def extract_common_conditions(self, common_var, condition, allow_not_in):
        not_in, var, conditions = self.extract_conditions(condition, allow_not_in)
873
        if var is None:
874
            return self.NO_MATCH
875
        elif common_var is not None and not is_common_value(var, common_var):
876
            return self.NO_MATCH
877
        elif not var.type.is_int or sum([not cond.type.is_int for cond in conditions]):
878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893
            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
894

895 896 897 898
    def visit_IfStatNode(self, node):
        common_var = None
        cases = []
        for if_clause in node.if_clauses:
899 900
            _, common_var, conditions = self.extract_common_conditions(
                common_var, if_clause.condition, False)
901
            if common_var is None:
902
                self.visitchildren(node)
903
                return node
904 905 906 907 908
            cases.append(Nodes.SwitchCaseNode(pos = if_clause.pos,
                                              conditions = conditions,
                                              body = if_clause.body))

        if sum([ len(case.conditions) for case in cases ]) < 2:
909 910 911 912
            self.visitchildren(node)
            return node
        if self.has_duplicate_values(sum([case.conditions for case in cases], [])):
            self.visitchildren(node)
913
            return node
914

Robert Bradshaw's avatar
Robert Bradshaw committed
915
        common_var = unwrap_node(common_var)
916 917 918 919 920 921 922
        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):
923 924 925 926 927 928
        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)
929
            return node
930 931 932
        return self.build_simple_switch_statement(
            node, common_var, conditions, not_in,
            node.true_val, node.false_val)
933 934

    def visit_BoolBinopNode(self, node):
935 936 937 938 939 940
        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)
941 942
            return node

943 944
        return self.build_simple_switch_statement(
            node, common_var, conditions, not_in,
945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960
            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))
961 962 963

    def build_simple_switch_statement(self, node, common_var, conditions,
                                      not_in, true_val, false_val):
964 965 966 967
        result_ref = UtilNodes.ResultRefNode(node)
        true_body = Nodes.SingleAssignmentNode(
            node.pos,
            lhs = result_ref,
968
            rhs = true_val,
969 970 971 972
            first = True)
        false_body = Nodes.SingleAssignmentNode(
            node.pos,
            lhs = result_ref,
973
            rhs = false_val,
974 975
            first = True)

976 977 978
        if not_in:
            true_body, false_body = false_body, true_body

979 980 981 982 983 984 985 986 987 988
        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)
989

990
    visit_Node = Visitor.VisitorTransform.recurse_to_children
991

992

993
class FlattenInListTransform(Visitor.VisitorTransform, SkipDeclarations):
994 995
    """
    This transformation flattens "x in [val1, ..., valn]" into a sequential list
996
    of comparisons.
997
    """
998

999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010
    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
1011

1012 1013 1014
        if not isinstance(node.operand2, (ExprNodes.TupleNode,
                                          ExprNodes.ListNode,
                                          ExprNodes.SetNode)):
Stefan Behnel's avatar
Stefan Behnel committed
1015
            return node
1016

Stefan Behnel's avatar
Stefan Behnel committed
1017 1018 1019
        args = node.operand2.args
        if len(args) == 0:
            return ExprNodes.BoolNode(pos = node.pos, value = node.operator == 'not_in')
1020

1021
        lhs = UtilNodes.ResultRefNode(node.operand1)
Stefan Behnel's avatar
Stefan Behnel committed
1022 1023

        conds = []
1024
        temps = []
Stefan Behnel's avatar
Stefan Behnel committed
1025
        for arg in args:
1026 1027 1028 1029 1030 1031 1032 1033 1034
            try:
                # Trial optimisation to avoid redundant temp
                # assignments.  However, since is_simple() is meant to
                # be called after type analysis, we ignore any errors
                # and just play safe in that case.
                is_simple_arg = arg.is_simple()
            except Exception:
                is_simple_arg = False
            if not is_simple_arg:
1035 1036 1037
                # must evaluate all non-simple RHS before doing the comparisons
                arg = UtilNodes.LetRefNode(arg)
                temps.append(arg)
Stefan Behnel's avatar
Stefan Behnel committed
1038 1039 1040 1041 1042 1043 1044
            cond = ExprNodes.PrimaryCmpNode(
                                pos = node.pos,
                                operand1 = lhs,
                                operator = eq_or_neq,
                                operand2 = arg,
                                cascade = None)
            conds.append(ExprNodes.TypecastNode(
1045
                                pos = node.pos,
Stefan Behnel's avatar
Stefan Behnel committed
1046 1047 1048 1049
                                operand = cond,
                                type = PyrexTypes.c_bint_type))
        def concat(left, right):
            return ExprNodes.BoolBinopNode(
1050
                                pos = node.pos,
Stefan Behnel's avatar
Stefan Behnel committed
1051 1052 1053 1054
                                operator = conjunction,
                                operand1 = left,
                                operand2 = right)

1055
        condition = reduce(concat, conds)
1056 1057 1058 1059
        new_node = UtilNodes.EvalWithTempExprNode(lhs, condition)
        for temp in temps[::-1]:
            new_node = UtilNodes.EvalWithTempExprNode(temp, new_node)
        return new_node
1060

1061
    visit_Node = Visitor.VisitorTransform.recurse_to_children
1062 1063


1064 1065 1066 1067 1068 1069
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
1070 1071 1072
        """
        Parallel swap assignments like 'a,b = b,a' are safe.
        """
1073 1074 1075 1076
        left_names, right_names = [], []
        left_indices, right_indices = [], []
        temps = []

1077 1078
        for stat in node.stats:
            if isinstance(stat, Nodes.SingleAssignmentNode):
1079 1080
                if not self._extract_operand(stat.lhs, left_names,
                                             left_indices, temps):
1081
                    return node
1082 1083
                if not self._extract_operand(stat.rhs, right_names,
                                             right_indices, temps):
1084
                    return node
1085 1086 1087
            elif isinstance(stat, Nodes.CascadedAssignmentNode):
                # FIXME
                return node
1088 1089 1090
            else:
                return node

1091 1092
        if left_names or right_names:
            # lhs/rhs names must be a non-redundant permutation
1093 1094
            lnames = [ path for path, n in left_names ]
            rnames = [ path for path, n in right_names ]
1095 1096 1097
            if set(lnames) != set(rnames):
                return node
            if len(set(lnames)) != len(right_names):
1098 1099
                return node

1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114
        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)
1115

1116 1117 1118 1119 1120 1121 1122
            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
1123 1124
            return node

1125 1126 1127 1128
        temp_args = [t.arg for t in temps]
        for temp in temps:
            temp.use_managed_ref = False

1129
        for _, name_node in left_names + right_names:
1130 1131 1132 1133 1134
            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
1135 1136 1137

        return node

1138 1139 1140 1141 1142 1143 1144
    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
1145 1146 1147 1148
        name_path = []
        obj_node = node
        while isinstance(obj_node, ExprNodes.AttributeNode):
            if obj_node.is_py_attr:
1149
                return False
1150 1151 1152 1153 1154
            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) )
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178
        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)

1179

1180 1181 1182 1183 1184 1185 1186
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
1187 1188 1189 1190

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

1195 1196 1197 1198 1199 1200 1201
    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)

1202
    def visit_GeneralCallNode(self, node):
1203
        self.visitchildren(node)
1204
        function = node.function
1205
        if not self._function_is_builtin_name(function):
1206 1207 1208 1209
            return node
        arg_tuple = node.positional_args
        if not isinstance(arg_tuple, ExprNodes.TupleNode):
            return node
1210
        args = arg_tuple.args
1211
        return self._dispatch_to_handler(
1212
            node, function, args, node.keyword_args)
1213

1214 1215 1216
    def _function_is_builtin_name(self, function):
        if not function.is_name:
            return False
1217 1218 1219
        env = self.current_env()
        entry = env.lookup(function.name)
        if entry is not env.builtin_scope().lookup_here(function.name):
1220
            return False
1221
        # if entry is None, it's at least an undeclared name, so likely builtin
1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259
        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

1260 1261 1262 1263 1264 1265 1266
    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

1267 1268 1269
    class YieldNodeCollector(Visitor.TreeVisitor):
        def __init__(self):
            Visitor.TreeVisitor.__init__(self)
1270
            self.yield_stat_nodes = {}
1271 1272 1273
            self.yield_nodes = []

        visit_Node = Visitor.TreeVisitor.visitchildren
1274 1275
        # XXX: disable inlining while it's not back supported
        def __visit_YieldExprNode(self, node):
1276 1277 1278
            self.yield_nodes.append(node)
            self.visitchildren(node)

1279
        def __visit_ExprStatNode(self, node):
1280 1281 1282 1283
            self.visitchildren(node)
            if node.expr in self.yield_nodes:
                self.yield_stat_nodes[node.expr] = node

1284 1285 1286 1287 1288 1289
        def __visit_GeneratorExpressionNode(self, node):
            # enable when we support generic generator expressions
            #
            # everything below this node is out of scope
            pass

1290
    def _find_single_yield_expression(self, node):
1291 1292 1293
        collector = self.YieldNodeCollector()
        collector.visitchildren(node)
        if len(collector.yield_nodes) != 1:
1294 1295
            return None, None
        yield_node = collector.yield_nodes[0]
1296 1297 1298 1299
        try:
            return (yield_node.arg, collector.yield_stat_nodes[yield_node])
        except KeyError:
            return None, None
1300

1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345
    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
1346 1347
        gen_expr_node = pos_args[0]
        loop_node = gen_expr_node.loop
1348 1349
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1350 1351 1352 1353 1354 1355 1356
            return node

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

1357
        result_ref = UtilNodes.ResultRefNode(pos=node.pos, type=PyrexTypes.c_bint_type)
1358
        test_node = Nodes.IfStatNode(
1359
            yield_expression.pos,
1360 1361
            else_clause = None,
            if_clauses = [ Nodes.IfClauseNode(
1362
                yield_expression.pos,
1363 1364 1365 1366 1367 1368 1369
                condition = condition,
                body = Nodes.StatListNode(
                    node.pos,
                    stats = [
                        Nodes.SingleAssignmentNode(
                            node.pos,
                            lhs = result_ref,
1370
                            rhs = ExprNodes.BoolNode(yield_expression.pos, value = is_any,
1371 1372 1373 1374 1375 1376 1377 1378 1379
                                                     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,
1380
                Nodes.BreakStatNode(yield_expression.pos)
1381
                ])
1382
            next_loop.else_clause = Nodes.ContinueStatNode(yield_expression.pos)
1383 1384 1385 1386
            loop = next_loop
        loop_node.else_clause = Nodes.SingleAssignmentNode(
            node.pos,
            lhs = result_ref,
1387
            rhs = ExprNodes.BoolNode(yield_expression.pos, value = not is_any,
1388 1389
                                     constant_result = not is_any))

1390
        Visitor.recursively_replace_node(loop_node, yield_stat_node, test_node)
1391

1392 1393
        return ExprNodes.InlinedGeneratorExpressionNode(
            gen_expr_node.pos, loop = loop_node, result_node = result_ref,
1394
            expr_scope = gen_expr_node.expr_scope, orig_func = is_any and 'any' or 'all')
1395

1396
    def _handle_simple_function_sorted(self, node, pos_args):
1397 1398 1399 1400 1401
        """Transform sorted(genexpr) and sorted([listcomp]) into
        [listcomp].sort().  CPython just reads the iterable into a
        list and calls .sort() on it.  Expanding the iterable in a
        listcomp is still faster and the result can be sorted in
        place.
1402 1403 1404
        """
        if len(pos_args) != 1:
            return node
1405 1406 1407 1408 1409 1410 1411 1412 1413 1414
        if isinstance(pos_args[0], ExprNodes.ComprehensionNode) \
               and pos_args[0].target.type is Builtin.list_type:
            listcomp_node = pos_args[0]
            loop_node = listcomp_node.loop
        elif isinstance(pos_args[0], ExprNodes.GeneratorExpressionNode):
            gen_expr_node = pos_args[0]
            loop_node = gen_expr_node.loop
            yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
            if yield_expression is None:
                return node
1415

1416 1417 1418 1419
            target = ExprNodes.ListNode(node.pos, args = [])
            append_node = ExprNodes.ComprehensionAppendNode(
                yield_expression.pos, expr = yield_expression,
                target = ExprNodes.CloneNode(target))
1420

1421
            Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1422

1423 1424 1425 1426 1427 1428 1429
            listcomp_node = ExprNodes.ComprehensionNode(
                gen_expr_node.pos, loop = loop_node, target = target,
                append = append_node, type = Builtin.list_type,
                expr_scope = gen_expr_node.expr_scope,
                has_local_scope = True)
        else:
            return node
1430

1431 1432
        result_node = UtilNodes.ResultRefNode(
            pos = loop_node.pos, type = Builtin.list_type, may_hold_none=False)
1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449
        listcomp_assign_node = Nodes.SingleAssignmentNode(
            node.pos, lhs = result_node, rhs = listcomp_node, first = True)

        sort_method = ExprNodes.AttributeNode(
            node.pos, obj = result_node, attribute = EncodedString('sort'),
            # entry ? type ?
            needs_none_check = False)
        sort_node = Nodes.ExprStatNode(
            node.pos, expr = ExprNodes.SimpleCallNode(
                node.pos, function = sort_method, args = []))

        sort_node.analyse_declarations(self.current_env())

        return UtilNodes.TempResultFromStatNode(
            result_node,
            Nodes.StatListNode(node.pos, stats = [ listcomp_assign_node, sort_node ]))

1450
    def _handle_simple_function_sum(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1451 1452
        """Transform sum(genexpr) into an equivalent inlined aggregation loop.
        """
1453 1454
        if len(pos_args) not in (1,2):
            return node
1455 1456
        if not isinstance(pos_args[0], (ExprNodes.GeneratorExpressionNode,
                                        ExprNodes.ComprehensionNode)):
1457 1458 1459 1460
            return node
        gen_expr_node = pos_args[0]
        loop_node = gen_expr_node.loop

1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474
        if isinstance(gen_expr_node, ExprNodes.GeneratorExpressionNode):
            yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
            if yield_expression is None:
                return node
        else: # ComprehensionNode
            yield_stat_node = gen_expr_node.append
            yield_expression = yield_stat_node.expr
            try:
                if not yield_expression.is_literal or not yield_expression.type.is_int:
                    return node
            except AttributeError:
                return node # in case we don't have a type yet
            # special case: old Py2 backwards compatible "sum([int_const for ...])"
            # can safely be unpacked into a genexpr
1475 1476 1477 1478 1479 1480 1481 1482

        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(
1483
            yield_expression.pos,
1484 1485 1486 1487
            lhs = result_ref,
            rhs = ExprNodes.binop_node(node.pos, '+', result_ref, yield_expression)
            )

1488
        Visitor.recursively_replace_node(loop_node, yield_stat_node, add_node)
1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502

        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,
1503 1504
            expr_scope = gen_expr_node.expr_scope, orig_func = 'sum',
            has_local_scope = gen_expr_node.has_local_scope)
1505

1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518
    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

1519
        cascaded_nodes = list(map(UtilNodes.ResultRefNode, args[1:]))
1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541

        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

1542
    def _DISABLED_handle_simple_function_tuple(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1543
        if not pos_args:
1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556
            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

1557
    def _handle_simple_function_list(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1558
        if not pos_args:
1559 1560 1561 1562
            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):
Stefan Behnel's avatar
Stefan Behnel committed
1563
        if not pos_args:
1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576
            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

1577 1578
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1579 1580 1581 1582
            return node

        target_node = container_node_class(node.pos, args=[])
        append_node = ExprNodes.ComprehensionAppendNode(
1583
            yield_expression.pos,
1584
            expr = yield_expression,
Stefan Behnel's avatar
Stefan Behnel committed
1585
            target = ExprNodes.CloneNode(target_node))
1586

1587
        Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610

        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

1611 1612
        yield_expression, yield_stat_node = self._find_single_yield_expression(loop_node)
        if yield_expression is None:
1613 1614 1615 1616 1617 1618 1619 1620 1621
            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(
1622
            yield_expression.pos,
1623 1624
            key_expr = yield_expression.args[0],
            value_expr = yield_expression.args[1],
Stefan Behnel's avatar
Stefan Behnel committed
1625
            target = ExprNodes.CloneNode(target_node))
1626

1627
        Visitor.recursively_replace_node(loop_node, yield_stat_node, append_node)
1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638

        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

1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650
    # 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
        return kwargs

1651 1652 1653 1654 1655 1656 1657 1658 1659 1660
class InlineDefNodeCalls(Visitor.CythonTransform):
    visit_Node = Visitor.VisitorTransform.recurse_to_children

    def visit_SimpleCallNode(self, node):
        self.visitchildren(node)
        if not self.current_directives.get('optimize.inline_defnode_calls'):
            return node
        function_name = node.function
        if not function_name.is_name:
            return node
1661 1662
        if (function_name.cf_state is None or
            not function_name.cf_state.is_single):
1663
            return node
1664
        function = function_name.cf_state.one().rhs
1665 1666 1667 1668 1669 1670 1671 1672 1673
        if not isinstance(function, ExprNodes.PyCFunctionNode):
            return node
        inlined = ExprNodes.InlinedDefNodeCallNode(
            node.pos, function_name=function_name,
            function=function, args=node.args)
        if inlined.can_be_inlined():
            return inlined
        return node

1674

1675
class OptimizeBuiltinCalls(Visitor.MethodDispatcherTransform):
Stefan Behnel's avatar
Stefan Behnel committed
1676
    """Optimize some common methods calls and instantiation patterns
1677 1678 1679 1680 1681
    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.
1682
    """
1683 1684
    ### cleanup to avoid redundant coercions to/from Python types

1685 1686 1687
    def _visit_PyTypeTestNode(self, node):
        # disabled - appears to break assignments in some cases, and
        # also drops a None check, which might still be required
1688 1689 1690 1691 1692 1693 1694 1695
        """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

1696 1697 1698
    def _visit_TypecastNode(self, node):
        # disabled - the user may have had a reason to put a type
        # cast, even if it looks redundant to Cython
1699 1700 1701 1702 1703 1704 1705 1706
        """
        Drop redundant type casts.
        """
        self.visitchildren(node)
        if node.type == node.operand.type:
            return node.operand
        return node

1707 1708 1709 1710 1711 1712 1713 1714 1715
    def visit_ExprStatNode(self, node):
        """
        Drop useless coercions.
        """
        self.visitchildren(node)
        if isinstance(node.expr, ExprNodes.CoerceToPyTypeNode):
            node.expr = node.expr.arg
        return node

1716 1717 1718 1719 1720
    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
1721 1722
        if isinstance(arg, ExprNodes.PyTypeTestNode):
            arg = arg.arg
1723 1724
        if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
            if arg.type in (PyrexTypes.py_object_type, Builtin.bool_type):
1725
                return arg.arg.coerce_to_boolean(self.current_env())
1726 1727
        return node

1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
    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:
1742
                return arg.coerce_to(node.type, self.current_env())
1743 1744
        if isinstance(arg, ExprNodes.PyTypeTestNode):
            arg = arg.arg
1745 1746 1747 1748
        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
1749
                    return arg.arg.coerce_to(node.type, self.current_env())
Stefan Behnel's avatar
Stefan Behnel committed
1750 1751 1752
        if isinstance(arg, ExprNodes.SimpleCallNode):
            if node.type.is_int or node.type.is_float:
                return self._optimise_numeric_cast_call(node, arg)
1753 1754 1755 1756 1757 1758
        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
1759 1760
        return node

1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772
    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
1773
        if arg.base.type is Builtin.bytes_type:
1774 1775 1776 1777 1778 1779 1780 1781 1782
            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
1783
                        arg.base.as_none_safe_node("'NoneType' object is not subscriptable"),
1784 1785 1786 1787
                        index_node.coerce_to(PyrexTypes.c_py_ssize_t_type, env),
                        bound_check_node,
                        ],
                    is_temp = True,
1788
                    utility_code=load_c_utility('bytes_index'))
1789 1790 1791 1792 1793
                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
1794
    def _optimise_numeric_cast_call(self, node, arg):
1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813
        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:
1814 1815
                    return ExprNodes.TypecastNode(
                        node.pos, operand=func_arg, type=node.type)
1816 1817 1818 1819 1820
        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:
1821 1822
                    return ExprNodes.TypecastNode(
                        node.pos, operand=func_arg, type=node.type)
1823 1824
        return node

1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840
    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)))

1841 1842
    ### builtin types

1843 1844 1845 1846 1847 1848
    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):
1849
        """Replace dict(some_dict) by PyDict_Copy(some_dict).
1850
        """
1851
        if len(pos_args) != 1:
1852
            return node
1853
        arg = pos_args[0]
1854
        if arg.type is Builtin.dict_type:
1855
            arg = arg.as_none_safe_node("'NoneType' is not iterable")
1856 1857
            return ExprNodes.PythonCapiCallNode(
                node.pos, "PyDict_Copy", self.PyDict_Copy_func_type,
1858
                args = [arg],
1859 1860 1861
                is_temp = node.is_temp
                )
        return node
1862

1863 1864 1865 1866 1867
    PyList_AsTuple_func_type = PyrexTypes.CFuncType(
        Builtin.tuple_type, [
            PyrexTypes.CFuncTypeArg("list", Builtin.list_type, None)
            ])

1868
    def _handle_simple_function_tuple(self, node, pos_args):
1869 1870
        """Replace tuple([...]) by a call to PyList_AsTuple.
        """
1871
        if len(pos_args) != 1:
1872
            return node
1873
        list_arg = pos_args[0]
1874 1875 1876 1877
        if list_arg.type is not Builtin.list_type:
            return node
        if not isinstance(list_arg, (ExprNodes.ComprehensionNode,
                                     ExprNodes.ListNode)):
1878
            pos_args[0] = list_arg.as_none_safe_node(
1879
                "'NoneType' object is not iterable")
1880

1881 1882
        return ExprNodes.PythonCapiCallNode(
            node.pos, "PyList_AsTuple", self.PyList_AsTuple_func_type,
1883
            args = pos_args,
1884 1885 1886
            is_temp = node.is_temp
            )

1887 1888 1889 1890 1891 1892 1893
    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)

1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914
    def _handle_simple_function_set(self, node, pos_args):
        if len(pos_args) == 1 and isinstance(pos_args[0], (ExprNodes.ListNode,
                                                           ExprNodes.TupleNode)):
            # We can optimise set([x,y,z]) safely into a set literal,
            # but only if we create all items before adding them -
            # adding an item may raise an exception if it is not
            # hashable, but creating the later items may have
            # side-effects.
            args = []
            temps = []
            for arg in pos_args[0].args:
                if not arg.is_simple():
                    arg = UtilNodes.LetRefNode(arg)
                    temps.append(arg)
                args.append(arg)
            result = ExprNodes.SetNode(node.pos, is_temp=1, args=args)
            for temp in temps[::-1]:
                result = UtilNodes.EvalWithTempExprNode(temp, result)
            return result
        return node

1915
    def _handle_simple_function_float(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1916 1917 1918
        """Transform float() into either a C type cast or a faster C
        function call.
        """
1919 1920
        # Note: this requires the float() function to be typed as
        # returning a C 'double'
1921
        if len(pos_args) == 0:
Stefan Behnel's avatar
typo  
Stefan Behnel committed
1922
            return ExprNodes.FloatNode(
1923 1924 1925 1926
                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')
1927 1928 1929 1930 1931 1932 1933
            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:
1934 1935
            return ExprNodes.TypecastNode(
                node.pos, operand=func_arg, type=node.type)
1936 1937 1938 1939 1940
        return ExprNodes.PythonCapiCallNode(
            node.pos, "__Pyx_PyObject_AsDouble",
            self.PyObject_AsDouble_func_type,
            args = pos_args,
            is_temp = node.is_temp,
1941
            utility_code = load_c_utility('pyobject_as_double'),
1942 1943
            py_name = "float")

1944 1945 1946
    def _handle_simple_function_bool(self, node, pos_args):
        """Transform bool(x) into a type coercion to a boolean.
        """
1947 1948 1949 1950 1951 1952
        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')
1953
            return node
Craig Citro's avatar
Craig Citro committed
1954
        else:
1955 1956 1957 1958 1959 1960
            # => !!<bint>(x)  to make sure it's exactly 0 or 1
            operand = pos_args[0].coerce_to_boolean(self.current_env())
            operand = ExprNodes.NotNode(node.pos, operand = operand)
            operand = ExprNodes.NotNode(node.pos, operand = operand)
            # coerce back to Python object as that's the result we are expecting
            return operand.coerce_to_pyobject(self.current_env())
1961

1962 1963
    ### builtin functions

1964 1965 1966 1967 1968
    Pyx_strlen_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_size_t_type, [
            PyrexTypes.CFuncTypeArg("bytes", PyrexTypes.c_char_ptr_type, None)
            ])

1969 1970 1971
    PyObject_Size_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_py_ssize_t_type, [
            PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None)
1972 1973
            ],
        exception_value="-1")
1974 1975

    _map_to_capi_len_function = {
1976
        Builtin.unicode_type   : "__Pyx_PyUnicode_GET_LENGTH",
1977
        Builtin.bytes_type     : "PyBytes_GET_SIZE",
1978 1979 1980 1981 1982 1983 1984
        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

1985
    def _handle_simple_function_len(self, node, pos_args):
Stefan Behnel's avatar
Stefan Behnel committed
1986 1987
        """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
1988
        """
1989 1990 1991 1992 1993 1994
        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
1995 1996 1997 1998 1999
        if arg.type.is_string:
            new_node = ExprNodes.PythonCapiCallNode(
                node.pos, "strlen", self.Pyx_strlen_func_type,
                args = [arg],
                is_temp = node.is_temp,
2000
                utility_code = UtilityCode.load_cached("IncludeStringH", "StringTools.c"))
2001 2002 2003 2004
        elif arg.type.is_pyobject:
            cfunc_name = self._map_to_capi_len_function(arg.type)
            if cfunc_name is None:
                return node
2005 2006
            arg = arg.as_none_safe_node(
                "object of type 'NoneType' has no len()")
2007 2008 2009 2010
            new_node = ExprNodes.PythonCapiCallNode(
                node.pos, cfunc_name, self.PyObject_Size_func_type,
                args = [arg],
                is_temp = node.is_temp)
Stefan Behnel's avatar
Stefan Behnel committed
2011
        elif arg.type.is_unicode_char:
2012 2013
            return ExprNodes.IntNode(node.pos, value='1', constant_result=1,
                                     type=node.type)
2014
        else:
Stefan Behnel's avatar
Stefan Behnel committed
2015
            return node
2016
        if node.type not in (PyrexTypes.c_size_t_type, PyrexTypes.c_py_ssize_t_type):
2017
            new_node = new_node.coerce_to(node.type, self.current_env())
2018
        return new_node
2019

2020 2021 2022 2023 2024 2025
    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
2026 2027
        """Replace type(o) by a macro call to Py_TYPE(o).
        """
2028
        if len(pos_args) != 1:
2029 2030
            return node
        node = ExprNodes.PythonCapiCallNode(
2031 2032 2033 2034
            node.pos, "Py_TYPE", self.Pyx_Type_func_type,
            args = pos_args,
            is_temp = False)
        return ExprNodes.CastNode(node, PyrexTypes.py_object_type)
2035

2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060
    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:
Robert Bradshaw's avatar
Robert Bradshaw committed
2061 2062 2063 2064 2065 2066 2067 2068
            builtin_type = None
            if isinstance(test_type_node, ExprNodes.NameNode):
                if test_type_node.entry:
                    entry = env.lookup(test_type_node.entry.name)
                    if entry and entry.type and entry.type.is_builtin_type:
                        builtin_type = entry.type
            if builtin_type and builtin_type is not Builtin.type_type:
                type_check_function = entry.type.type_check_function(exact=False)
2069 2070 2071
                if type_check_function in tests:
                    continue
                tests.append(type_check_function)
Robert Bradshaw's avatar
Robert Bradshaw committed
2072 2073 2074 2075 2076
                type_check_args = [arg]
            elif test_type_node.type is Builtin.type_type:
                type_check_function = '__Pyx_TypeCheck'
                type_check_args = [arg, test_type_node]
            else:
2077
                return node
2078 2079 2080 2081 2082 2083
            test_nodes.append(
                ExprNodes.PythonCapiCallNode(
                    test_type_node.pos, type_check_function, self.Py_type_check_func_type,
                    args = type_check_args,
                    is_temp = True,
                    ))
2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095

        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

2096
    def _handle_simple_function_ord(self, node, pos_args):
2097
        """Unpack ord(Py_UNICODE) and ord('X').
2098 2099 2100 2101 2102
        """
        if len(pos_args) != 1:
            return node
        arg = pos_args[0]
        if isinstance(arg, ExprNodes.CoerceToPyTypeNode):
Stefan Behnel's avatar
Stefan Behnel committed
2103
            if arg.arg.type.is_unicode_char:
2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121
                return ExprNodes.TypecastNode(
                    arg.pos, operand=arg.arg, type=PyrexTypes.c_int_type
                    ).coerce_to(node.type, self.current_env())
        elif isinstance(arg, ExprNodes.UnicodeNode):
            if len(arg.value) == 1:
                return ExprNodes.IntNode(
                    ord(arg.value), type=PyrexTypes.c_int_type,
                    value=str(ord(arg.value)),
                    constant_result=ord(arg.value)
                    ).coerce_to(node.type, self.current_env())
        elif isinstance(arg, ExprNodes.StringNode):
            if arg.unicode_value and len(arg.unicode_value) == 1 \
                   and ord(arg.unicode_value) <= 255: # Py2/3 portability
                return ExprNodes.IntNode(
                    ord(arg.unicode_value), type=PyrexTypes.c_int_type,
                    value=str(ord(arg.unicode_value)),
                    constant_result=ord(arg.unicode_value)
                    ).coerce_to(node.type, self.current_env())
2122 2123
        return node

2124 2125
    ### special methods

2126 2127 2128 2129 2130
    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
2131
    def _handle_simple_slot__new__(self, node, args, is_unbound_method):
2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149
        """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:
2150
            # different types - may or may not lead to an error at runtime
2151 2152
            return node

Stefan Behnel's avatar
Stefan Behnel committed
2153 2154 2155 2156
        # 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.
2157

2158 2159
        if not type_arg.type_entry:
            # arbitrary variable, needs a None check for safety
2160
            type_arg = type_arg.as_none_safe_node(
2161 2162
                "object.__new__(X): X is not a type object (NoneType)")

2163
        return ExprNodes.PythonCapiCallNode(
2164
            node.pos, "__Pyx_tp_new", self.Pyx_tp_new_func_type,
2165
            args = [type_arg],
2166 2167 2168 2169
            utility_code = tpnew_utility_code,
            is_temp = node.is_temp
            )

2170 2171 2172 2173 2174 2175 2176 2177
    ### 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),
            ])

2178
    def _handle_simple_method_object_append(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2179 2180 2181
        """Optimistic optimisation as X.append() is almost always
        referring to a list.
        """
2182
        if len(args) != 2:
2183 2184
            return node

2185 2186 2187
        return ExprNodes.PythonCapiCallNode(
            node.pos, "__Pyx_PyObject_Append", self.PyObject_Append_func_type,
            args = args,
Stefan Behnel's avatar
Stefan Behnel committed
2188
            may_return_none = True,
2189
            is_temp = node.is_temp,
2190
            utility_code = load_c_utility('append')
2191 2192
            )

Robert Bradshaw's avatar
Robert Bradshaw committed
2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204
    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
2205 2206 2207
        """Optimistic optimisation as X.pop([n]) is almost always
        referring to a list.
        """
Robert Bradshaw's avatar
Robert Bradshaw committed
2208 2209 2210 2211
        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
2212
                may_return_none = True,
Robert Bradshaw's avatar
Robert Bradshaw committed
2213
                is_temp = node.is_temp,
2214
                utility_code = load_c_utility('pop')
Robert Bradshaw's avatar
Robert Bradshaw committed
2215 2216
                )
        elif len(args) == 2:
2217 2218 2219 2220 2221 2222 2223 2224 2225 2226
            index = args[1]
            if isinstance(index, ExprNodes.CoerceToPyTypeNode):
                index = index.arg
            if isinstance(index, ExprNodes.IntNode):
                index = index.coerce_to(PyrexTypes.c_py_ssize_t_type, None)
            if index.type.is_int:
                widest = PyrexTypes.widest_numeric_type(
                    index.type, PyrexTypes.c_py_ssize_t_type)
                if widest == PyrexTypes.c_py_ssize_t_type:
                    args[1] = index
Robert Bradshaw's avatar
Robert Bradshaw committed
2227
                    return ExprNodes.PythonCapiCallNode(
2228 2229
                        node.pos, "__Pyx_PyObject_PopIndex",
                        self.PyObject_PopIndex_func_type,
Robert Bradshaw's avatar
Robert Bradshaw committed
2230
                        args = args,
Stefan Behnel's avatar
Stefan Behnel committed
2231
                        may_return_none = True,
Robert Bradshaw's avatar
Robert Bradshaw committed
2232
                        is_temp = node.is_temp,
2233
                        utility_code = load_c_utility("pop_index")
Robert Bradshaw's avatar
Robert Bradshaw committed
2234
                        )
2235

Robert Bradshaw's avatar
Robert Bradshaw committed
2236 2237
        return node

2238 2239
    _handle_simple_method_list_pop = _handle_simple_method_object_pop

2240
    single_param_func_type = PyrexTypes.CFuncType(
2241
        PyrexTypes.c_returncode_type, [
2242 2243 2244
            PyrexTypes.CFuncTypeArg("obj", PyrexTypes.py_object_type, None),
            ],
        exception_value = "-1")
2245

2246
    def _handle_simple_method_list_sort(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2247 2248
        """Call PyList_Sort() instead of the 0-argument l.sort().
        """
2249
        if len(args) != 1:
2250
            return node
2251
        return self._substitute_method_call(
2252
            node, "PyList_Sort", self.single_param_func_type,
2253
            'sort', is_unbound_method, args).coerce_to(node.type, self.current_env)
2254

2255 2256 2257 2258 2259
    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),
2260
            ])
2261 2262

    def _handle_simple_method_dict_get(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2263 2264
        """Replace dict.get() by a call to PyDict_GetItem().
        """
2265 2266 2267 2268 2269 2270 2271 2272 2273
        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
2274
            may_return_none = True,
2275
            utility_code = load_c_utility("dict_getitem_default"))
2276

2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296
    Pyx_PyDict_SetDefault_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),
            ])

    def _handle_simple_method_dict_setdefault(self, node, args, is_unbound_method):
        """Replace dict.setdefault() by calls to PyDict_GetItem() and PyDict_SetItem().
        """
        if len(args) == 2:
            args.append(ExprNodes.NoneNode(node.pos))
        elif len(args) != 3:
            self._error_wrong_arg_count('dict.setdefault', node, args, "2 or 3")
            return node

        return self._substitute_method_call(
            node, "__Pyx_PyDict_SetDefault", self.Pyx_PyDict_SetDefault_func_type,
            'setdefault', is_unbound_method, args,
            may_return_none = True,
2297
            utility_code = load_c_utility('dict_setdefault'))
2298

2299 2300 2301

    ### unicode type methods

2302 2303
    PyUnicode_uchar_predicate_func_type = PyrexTypes.CFuncType(
        PyrexTypes.c_bint_type, [
2304
            PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_ucs4_type, None),
2305 2306 2307 2308 2309 2310 2311
            ])

    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 \
Stefan Behnel's avatar
Stefan Behnel committed
2312
               not ustring.arg.type.is_unicode_char:
2313 2314 2315 2316 2317
            return node
        uchar = ustring.arg
        method_name = node.function.attribute
        if method_name == 'istitle':
            # istitle() doesn't directly map to Py_UNICODE_ISTITLE()
2318
            utility_code = load_c_utility("py_unicode_istitle")
2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341
            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(
2342 2343
        PyrexTypes.c_py_ucs4_type, [
            PyrexTypes.CFuncTypeArg("uchar", PyrexTypes.c_py_ucs4_type, None),
2344 2345 2346 2347 2348 2349 2350
            ])

    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 \
Stefan Behnel's avatar
Stefan Behnel committed
2351
               not ustring.arg.type.is_unicode_char:
2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366
            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

2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379
    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
2380
        self._inject_bint_default_argument(node, args, 1, False)
2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402

        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))
2403 2404
        self._inject_int_default_argument(
            node, args, 2, PyrexTypes.c_py_ssize_t_type, "-1")
2405 2406 2407 2408 2409

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

2410
    PyString_Tailmatch_func_type = PyrexTypes.CFuncType(
2411
        PyrexTypes.c_bint_type, [
2412
            PyrexTypes.CFuncTypeArg("str", PyrexTypes.py_object_type, None),  # bytes/str/unicode
2413 2414 2415 2416 2417 2418 2419 2420
            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):
2421
        return self._inject_tailmatch(
Vitja Makarov's avatar
Vitja Makarov committed
2422
            node, args, is_unbound_method, 'unicode', 'endswith',
2423
            unicode_tailmatch_utility_code, +1)
2424 2425

    def _handle_simple_method_unicode_startswith(self, node, args, is_unbound_method):
2426
        return self._inject_tailmatch(
Vitja Makarov's avatar
Vitja Makarov committed
2427
            node, args, is_unbound_method, 'unicode', 'startswith',
2428
            unicode_tailmatch_utility_code, -1)
2429

Vitja Makarov's avatar
Vitja Makarov committed
2430
    def _inject_tailmatch(self, node, args, is_unbound_method, type_name,
2431
                          method_name, utility_code, direction):
2432 2433 2434 2435
        """Replace unicode.startswith(...) and unicode.endswith(...)
        by a direct call to the corresponding C-API function.
        """
        if len(args) not in (2,3,4):
2436
            self._error_wrong_arg_count('%s.%s' % (type_name, method_name), node, args, "2-4")
2437
            return node
2438 2439 2440 2441
        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")
2442 2443 2444 2445
        args.append(ExprNodes.IntNode(
            node.pos, value=str(direction), type=PyrexTypes.c_int_type))

        method_call = self._substitute_method_call(
2446 2447
            node, "__Pyx_Py%s_Tailmatch" % type_name.capitalize(),
            self.PyString_Tailmatch_func_type,
2448
            method_name, is_unbound_method, args,
2449
            utility_code = utility_code)
Stefan Behnel's avatar
Stefan Behnel committed
2450
        return method_call.coerce_to(Builtin.bool_type, self.current_env())
2451

2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477
    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
2478 2479 2480 2481
        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")
2482 2483 2484 2485 2486 2487
        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
2488
        return method_call.coerce_to_pyobject(self.current_env())
2489

Stefan Behnel's avatar
Stefan Behnel committed
2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505
    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
2506 2507 2508 2509
        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
2510 2511 2512 2513

        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
2514
        return method_call.coerce_to_pyobject(self.current_env())
Stefan Behnel's avatar
Stefan Behnel committed
2515

Stefan Behnel's avatar
Stefan Behnel committed
2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530
    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
2531 2532
        self._inject_int_default_argument(
            node, args, 3, PyrexTypes.c_py_ssize_t_type, "-1")
Stefan Behnel's avatar
Stefan Behnel committed
2533 2534 2535 2536 2537

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

2538 2539
    PyUnicode_AsEncodedString_func_type = PyrexTypes.CFuncType(
        Builtin.bytes_type, [
2540
            PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2541 2542
            PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
            PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2543
            ])
2544 2545 2546

    PyUnicode_AsXyzString_func_type = PyrexTypes.CFuncType(
        Builtin.bytes_type, [
2547
            PyrexTypes.CFuncTypeArg("obj", Builtin.unicode_type, None),
2548
            ])
2549 2550 2551 2552

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

2553 2554
    _special_codecs = [ (name, codecs.getencoder(name))
                        for name in _special_encodings ]
2555 2556

    def _handle_simple_method_unicode_encode(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2557 2558 2559
        """Replace unicode.encode(...) by a direct C-API call to the
        corresponding codec.
        """
2560
        if len(args) < 1 or len(args) > 3:
2561
            self._error_wrong_arg_count('unicode.encode', node, args, '1-3')
2562 2563 2564 2565 2566
            return node

        string_node = args[0]

        if len(args) == 1:
2567
            null_node = ExprNodes.NullNode(node.pos)
2568 2569 2570 2571 2572
            return self._substitute_method_call(
                node, "PyUnicode_AsEncodedString",
                self.PyUnicode_AsEncodedString_func_type,
                'encode', is_unbound_method, [string_node, null_node, null_node])

2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601 2602 2603 2604 2605 2606
        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])

2607
    PyUnicode_DecodeXyz_func_ptr_type = PyrexTypes.CPtrType(PyrexTypes.CFuncType(
2608 2609 2610 2611
        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),
2612
            ]))
2613

2614
    _decode_c_string_func_type = PyrexTypes.CFuncType(
2615 2616
        Builtin.unicode_type, [
            PyrexTypes.CFuncTypeArg("string", PyrexTypes.c_char_ptr_type, None),
2617 2618
            PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
            PyrexTypes.CFuncTypeArg("stop", PyrexTypes.c_py_ssize_t_type, None),
2619 2620
            PyrexTypes.CFuncTypeArg("encoding", PyrexTypes.c_char_ptr_type, None),
            PyrexTypes.CFuncTypeArg("errors", PyrexTypes.c_char_ptr_type, None),
2621
            PyrexTypes.CFuncTypeArg("decode_func", PyUnicode_DecodeXyz_func_ptr_type, None),
2622
            ])
2623

2624 2625
    _decode_cpp_string_func_type = None # lazy init

2626
    def _handle_simple_method_bytes_decode(self, node, args, is_unbound_method):
Stefan Behnel's avatar
Stefan Behnel committed
2627 2628 2629
        """Replace char*.decode() by a direct C-API call to the
        corresponding codec, possibly resoving a slice on the char*.
        """
2630
        if not (1 <= len(args) <= 3):
2631 2632
            self._error_wrong_arg_count('bytes.decode', node, args, '1-3')
            return node
2633 2634

        # normalise input nodes
2635 2636 2637 2638 2639 2640
        if isinstance(args[0], ExprNodes.SliceIndexNode):
            index_node = args[0]
            string_node = index_node.base
            start, stop = index_node.start, index_node.stop
            if not start or start.constant_result == 0:
                start = None
2641
        elif isinstance(args[0], ExprNodes.CoerceToPyTypeNode):
2642
            string_node = args[0].arg
2643
            start = stop = None
2644
        else:
2645
            return node
2646

2647 2648 2649
        if not string_node.type.is_string and not string_node.type.is_cpp_string:
            # nothing to optimise here
            return node
2650 2651 2652 2653 2654 2655

        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

2656 2657 2658 2659 2660 2661 2662
        if not start:
            start = ExprNodes.IntNode(node.pos, value='0', constant_result=0)
        elif not start.type.is_int:
            start = start.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
        if stop and not stop.type.is_int:
            stop = stop.coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())

2663
        # try to find a specific encoder function
2664 2665 2666
        codec_name = None
        if encoding is not None:
            codec_name = self._find_special_codec_name(encoding)
2667
        if codec_name is not None:
2668 2669 2670 2671
            decode_function = ExprNodes.RawCNameExprNode(
                node.pos, type=self.PyUnicode_DecodeXyz_func_ptr_type,
                cname="PyUnicode_Decode%s" % codec_name)
            encoding_node = ExprNodes.NullNode(node.pos)
2672
        else:
2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714
            decode_function = ExprNodes.NullNode(node.pos)

        # build the helper function call
        temps = []
        if string_node.type.is_string:
            # C string
            if not stop:
                # use strlen() to find the string length, just as CPython would
                if not string_node.is_name:
                    string_node = UtilNodes.LetRefNode(string_node) # used twice
                    temps.append(string_node)
                stop = ExprNodes.PythonCapiCallNode(
                    string_node.pos, "strlen", self.Pyx_strlen_func_type,
                    args = [string_node],
                    is_temp = False,
                    utility_code = UtilityCode.load_cached("IncludeStringH", "StringTools.c"),
                    ).coerce_to(PyrexTypes.c_py_ssize_t_type, self.current_env())
            helper_func_type = self._decode_c_string_func_type
            utility_code_name = 'decode_c_string'
        else:
            # C++ std::string
            if not stop:
                stop = ExprNodes.IntNode(node.pos, value='PY_SSIZE_T_MAX',
                                         constant_result=ExprNodes.not_a_constant)
            if self._decode_cpp_string_func_type is None:
                # lazy init to reuse the C++ string type
                self._decode_cpp_string_func_type = PyrexTypes.CFuncType(
                    Builtin.unicode_type, [
                        PyrexTypes.CFuncTypeArg("string", string_node.type, None),
                        PyrexTypes.CFuncTypeArg("start", PyrexTypes.c_py_ssize_t_type, None),
                        PyrexTypes.CFuncTypeArg("stop", 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),
                        PyrexTypes.CFuncTypeArg("decode_func", self.PyUnicode_DecodeXyz_func_ptr_type, None),
                        ])
            helper_func_type = self._decode_cpp_string_func_type
            utility_code_name = 'decode_cpp_string'

        node = ExprNodes.PythonCapiCallNode(
            node.pos, '__Pyx_%s' % utility_code_name, helper_func_type,
            args = [string_node, start, stop, encoding_node, error_handling_node, decode_function],
            is_temp = node.is_temp,
2715
            utility_code=UtilityCode.load_cached(utility_code_name, 'StringTools.c'),
2716
            )
2717

2718 2719 2720
        for temp in temps[::-1]:
            node = UtilNodes.EvalWithTempExprNode(temp, node)
        return node
2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735

    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):
2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746
        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)
2747 2748 2749 2750
            elif encoding_node.type is Builtin.bytes_type:
                encoding = None
                encoding_node = encoding_node.coerce_to(
                    PyrexTypes.c_char_ptr_type, self.current_env())
2751 2752 2753 2754
            elif encoding_node.type.is_string:
                encoding = None
            else:
                return None
2755
        else:
2756 2757
            encoding = None
            encoding_node = null_node
2758 2759 2760 2761 2762

        if len(args) == 3:
            error_handling_node = args[2]
            if isinstance(error_handling_node, ExprNodes.CoerceToPyTypeNode):
                error_handling_node = error_handling_node.arg
2763 2764 2765 2766 2767 2768 2769 2770 2771 2772
            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)
2773 2774 2775 2776
            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())
2777 2778
            elif error_handling_node.type.is_string:
                error_handling = None
2779
            else:
2780
                return None
2781 2782 2783 2784
        else:
            error_handling = 'strict'
            error_handling_node = null_node

2785
        return (encoding, encoding_node, error_handling, error_handling_node)
2786

2787
    def _handle_simple_method_str_endswith(self, node, args, is_unbound_method):
2788
        return self._inject_tailmatch(
Vitja Makarov's avatar
Vitja Makarov committed
2789
            node, args, is_unbound_method, 'str', 'endswith',
2790
            str_tailmatch_utility_code, +1)
2791 2792

    def _handle_simple_method_str_startswith(self, node, args, is_unbound_method):
2793 2794
        return self._inject_tailmatch(
            node, args, is_unbound_method, 'str', 'startswith',
2795
            str_tailmatch_utility_code, -1)
2796 2797 2798

    def _handle_simple_method_bytes_endswith(self, node, args, is_unbound_method):
        return self._inject_tailmatch(
Vitja Makarov's avatar
Vitja Makarov committed
2799
            node, args, is_unbound_method, 'bytes', 'endswith',
2800
            bytes_tailmatch_utility_code, +1)
2801 2802 2803 2804

    def _handle_simple_method_bytes_startswith(self, node, args, is_unbound_method):
        return self._inject_tailmatch(
            node, args, is_unbound_method, 'bytes', 'startswith',
2805
            bytes_tailmatch_utility_code, -1)
2806 2807 2808

    ### helpers

2809
    def _substitute_method_call(self, node, name, func_type,
2810
                                attr_name, is_unbound_method, args=(),
2811
                                utility_code=None, is_temp=None,
Stefan Behnel's avatar
Stefan Behnel committed
2812
                                may_return_none=ExprNodes.PythonCapiCallNode.may_return_none):
2813
        args = list(args)
2814
        if args and not args[0].is_literal:
2815 2816
            self_arg = args[0]
            if is_unbound_method:
2817
                self_arg = self_arg.as_none_safe_node(
2818 2819
                    "descriptor '%s' requires a '%s' object but received a 'NoneType'",
                    format_args = [attr_name, node.function.obj.name])
2820
            else:
2821
                self_arg = self_arg.as_none_safe_node(
2822 2823 2824
                    "'NoneType' object has no attribute '%s'",
                    error = "PyExc_AttributeError",
                    format_args = [attr_name])
2825
            args[0] = self_arg
2826 2827
        if is_temp is None:
            is_temp = node.is_temp
2828
        return ExprNodes.PythonCapiCallNode(
2829
            node.pos, name, func_type,
2830
            args = args,
2831
            is_temp = is_temp,
Stefan Behnel's avatar
Stefan Behnel committed
2832 2833
            utility_code = utility_code,
            may_return_none = may_return_none,
2834
            result_is_used = node.result_is_used,
2835 2836
            )

2837 2838 2839
    def _inject_int_default_argument(self, node, args, arg_index, type, default_value):
        assert len(args) >= arg_index
        if len(args) == arg_index:
2840 2841
            args.append(ExprNodes.IntNode(node.pos, value=str(default_value),
                                          type=type, constant_result=default_value))
2842
        else:
2843
            args[arg_index] = args[arg_index].coerce_to(type, self.current_env())
2844 2845 2846 2847

    def _inject_bint_default_argument(self, node, args, arg_index, default_value):
        assert len(args) >= arg_index
        if len(args) == arg_index:
2848 2849 2850
            default_value = bool(default_value)
            args.append(ExprNodes.BoolNode(node.pos, value=default_value,
                                           constant_result=default_value))
2851
        else:
2852
            args[arg_index] = args[arg_index].coerce_to_boolean(self.current_env())
2853

2854

2855
unicode_tailmatch_utility_code = load_c_utility('unicode_tailmatch')
2856

2857
bytes_tailmatch_utility_code = load_c_utility('bytes_tailmatch')
2858

2859 2860
str_tailmatch_utility_code = UtilityCode(
proto = '''
2861 2862
static CYTHON_INLINE int __Pyx_PyStr_Tailmatch(PyObject* self, PyObject* arg, Py_ssize_t start,
                                               Py_ssize_t end, int direction);
2863
''',
2864 2865 2866 2867
# We do not use a C compiler macro here to avoid "unused function"
# warnings for the *_Tailmatch() function that is not being used in
# the specific CPython version.  The C compiler will generate the same
# code anyway, and will usually just remove the unused function.
2868
impl = '''
2869 2870
static CYTHON_INLINE int __Pyx_PyStr_Tailmatch(PyObject* self, PyObject* arg, Py_ssize_t start,
                                               Py_ssize_t end, int direction)
2871
{
2872 2873 2874 2875
    if (PY_MAJOR_VERSION < 3)
        return __Pyx_PyBytes_Tailmatch(self, arg, start, end, direction);
    else
        return __Pyx_PyUnicode_Tailmatch(self, arg, start, end, direction);
2876 2877 2878 2879 2880
}
''',
requires=[unicode_tailmatch_utility_code, bytes_tailmatch_utility_code]
)

2881

2882 2883
tpnew_utility_code = UtilityCode(
proto = """
2884
static CYTHON_INLINE PyObject* __Pyx_tp_new(PyObject* type_obj) {
2885 2886 2887 2888 2889 2890 2891
    return (PyObject*) (((PyTypeObject*)(type_obj))->tp_new(
        (PyTypeObject*)(type_obj), %(TUPLE)s, NULL));
}
""" % {'TUPLE' : Naming.empty_tuple}
)


2892 2893 2894 2895
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.
2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906

    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.
2907
    """
2908

Mark Florisson's avatar
Mark Florisson committed
2909 2910 2911 2912 2913 2914 2915
    def __init__(self, reevaluate=False):
        """
        The reevaluate argument specifies whether constant values that were
        previously computed should be recomputed.
        """
        super(ConstantFolding, self).__init__()
        self.reevaluate = reevaluate
2916

2917
    def _calculate_const(self, node):
Mark Florisson's avatar
Mark Florisson committed
2918
        if (not self.reevaluate and
2919
                node.constant_result is not ExprNodes.constant_value_not_set):
2920 2921 2922 2923 2924 2925 2926 2927
            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)
2928
        for child_result in children.values():
2929 2930
            if type(child_result) is list:
                for child in child_result:
Stefan Behnel's avatar
Stefan Behnel committed
2931
                    if getattr(child, 'constant_result', not_a_constant) is not_a_constant:
2932
                        return
Stefan Behnel's avatar
Stefan Behnel committed
2933
            elif getattr(child_result, 'constant_result', not_a_constant) is not_a_constant:
2934 2935 2936 2937 2938 2939 2940
                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
2941
        except (ValueError, TypeError, KeyError, IndexError, AttributeError, ArithmeticError):
2942 2943 2944 2945 2946 2947 2948
            # 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)

Stefan Behnel's avatar
Stefan Behnel committed
2949 2950
    NODE_TYPE_ORDER = [ExprNodes.CharNode, ExprNodes.IntNode,
                       ExprNodes.LongNode, ExprNodes.FloatNode]
2951 2952 2953 2954 2955 2956 2957 2958

    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

2959 2960 2961 2962
    def visit_ExprNode(self, node):
        self._calculate_const(node)
        return node

2963
    def visit_UnopNode(self, node):
2964 2965 2966 2967 2968
        self._calculate_const(node)
        if node.constant_result is ExprNodes.not_a_constant:
            return node
        if not node.operand.is_literal:
            return node
2969 2970 2971 2972 2973
        if isinstance(node, ExprNodes.NotNode):
            return ExprNodes.BoolNode(node.pos, value = bool(node.constant_result),
                                      constant_result = bool(node.constant_result))
        elif isinstance(node.operand, ExprNodes.BoolNode):
            return ExprNodes.IntNode(node.pos, value = str(int(node.constant_result)),
2974
                                     type = PyrexTypes.c_int_type,
2975 2976
                                     constant_result = int(node.constant_result))
        elif node.operator == '+':
2977 2978 2979 2980 2981 2982
            return self._handle_UnaryPlusNode(node)
        elif node.operator == '-':
            return self._handle_UnaryMinusNode(node)
        return node

    def _handle_UnaryMinusNode(self, node):
2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994
        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,
2995
                                     longness = node.operand.longness,
2996 2997 2998
                                     constant_result = node.constant_result)
        return node

2999
    def _handle_UnaryPlusNode(self, node):
3000 3001 3002 3003
        if node.constant_result == node.operand.constant_result:
            return node.operand
        return node

3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018
    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:
            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

3019 3020 3021 3022
    def visit_BinopNode(self, node):
        self._calculate_const(node)
        if node.constant_result is ExprNodes.not_a_constant:
            return node
3023 3024
        if isinstance(node.constant_result, float):
            return node
3025 3026
        operand1, operand2 = node.operand1, node.operand2
        if not operand1.is_literal or not operand2.is_literal:
3027 3028 3029
            return node

        # now inject a new constant node with the calculated value
3030
        try:
3031
            type1, type2 = operand1.type, operand2.type
3032
            if type1 is None or type2 is None:
3033 3034 3035 3036
                return node
        except AttributeError:
            return node

3037
        if type1.is_numeric and type2.is_numeric:
3038
            widest_type = PyrexTypes.widest_numeric_type(type1, type2)
3039 3040
        else:
            widest_type = PyrexTypes.py_object_type
3041
        target_class = self._widest_node_class(operand1, operand2)
3042 3043 3044
        if target_class is None:
            return node
        elif target_class is ExprNodes.IntNode:
3045 3046 3047 3048
            unsigned = getattr(operand1, 'unsigned', '') and \
                       getattr(operand2, 'unsigned', '')
            longness = "LL"[:max(len(getattr(operand1, 'longness', '')),
                                 len(getattr(operand2, 'longness', '')))]
3049 3050 3051 3052 3053 3054 3055 3056
            new_node = ExprNodes.IntNode(pos=node.pos,
                                         unsigned = unsigned, longness = longness,
                                         value = str(node.constant_result),
                                         constant_result = node.constant_result)
            # IntNode is smart about the type it chooses, so we just
            # make sure we were not smarter this time
            if widest_type.is_pyobject or new_node.type.is_pyobject:
                new_node.type = PyrexTypes.py_object_type
3057
            else:
3058
                new_node.type = PyrexTypes.widest_numeric_type(widest_type, new_node.type)
3059
        else:
3060 3061 3062 3063 3064 3065 3066
            if isinstance(node, ExprNodes.BoolNode):
                node_value = node.constant_result
            else:
                node_value = str(node.constant_result)
            new_node = target_class(pos=node.pos, type = widest_type,
                                    value = node_value,
                                    constant_result = node.constant_result)
3067 3068
        return new_node

3069 3070 3071 3072 3073
    def visit_MulNode(self, node):
        if isinstance(node.operand1, (ExprNodes.ListNode, ExprNodes.TupleNode)):
            sequence_node = node.operand1
            factor = node.operand2
            self._calculate_const(factor)
3074 3075 3076 3077 3078 3079 3080 3081 3082
            if factor.constant_result != 1:
                sequence_node.mult_factor = factor
            self.visitchildren(sequence_node)
            return sequence_node
        if isinstance(node.operand1, ExprNodes.IntNode) and \
               isinstance(node.operand2, (ExprNodes.ListNode, ExprNodes.TupleNode)):
            sequence_node = node.operand2
            factor = node.operand1
            self._calculate_const(factor)
3083 3084 3085 3086 3087 3088
            if factor.constant_result != 1:
                sequence_node.mult_factor = factor
            self.visitchildren(sequence_node)
            return sequence_node
        return self.visit_BinopNode(node)

3089 3090 3091 3092 3093 3094 3095 3096
    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)

3097 3098 3099 3100 3101 3102 3103 3104 3105
    def visit_CondExprNode(self, node):
        self._calculate_const(node)
        if node.test.constant_result is ExprNodes.not_a_constant:
            return node
        if node.test.constant_result:
            return node.true_val
        else:
            return node.false_val

3106 3107 3108 3109 3110 3111
    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()
3112 3113
            if condition_result is None:
                # unknown result => normal runtime evaluation
3114
                if_clauses.append(if_clause)
3115 3116 3117 3118 3119 3120
            elif condition_result == True:
                # subsequent clauses can safely be dropped
                node.else_clause = if_clause.body
                break
            else:
                assert condition_result == False
3121
        if not if_clauses:
3122 3123 3124
            return node.else_clause
        node.if_clauses = if_clauses
        return node
3125

3126 3127
    # 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
3128

3129
    visit_Node = Visitor.VisitorTransform.recurse_to_children
3130 3131


3132 3133 3134
class FinalOptimizePhase(Visitor.CythonTransform):
    """
    This visitor handles several commuting optimizations, and is run
3135 3136 3137 3138
    just before the C code generation phase.

    The optimizations currently implemented in this class are:
        - eliminate None assignment and refcounting for first assignment.
3139
        - isinstance -> typecheck for cdef types
Stefan Behnel's avatar
Stefan Behnel committed
3140
        - eliminate checks for None and/or types that became redundant after tree changes
3141
    """
3142
    def visit_SingleAssignmentNode(self, node):
3143 3144 3145 3146
        """Avoid redundant initialisation of local variables before their
        first assignment.
        """
        self.visitchildren(node)
3147 3148
        if node.first:
            lhs = node.lhs
3149
            lhs.lhs_of_first_assignment = True
3150
        return node
3151

3152
    def visit_SimpleCallNode(self, node):
3153 3154 3155
        """Replace generic calls to isinstance(x, type) by a more efficient
        type check.
        """
3156
        self.visitchildren(node)
Robert Bradshaw's avatar
Robert Bradshaw committed
3157
        if node.function.type.is_cfunction and isinstance(node.function, ExprNodes.NameNode):
3158 3159 3160
            if node.function.name == 'isinstance':
                type_arg = node.args[1]
                if type_arg.type.is_builtin_type and type_arg.type.name == 'type':
3161 3162
                    cython_scope = self.context.cython_scope
                    node.function.entry = cython_scope.lookup('PyObject_TypeCheck')
3163
                    node.function.type = node.function.entry.type
3164
                    PyTypeObjectPtr = PyrexTypes.CPtrType(cython_scope.lookup('PyTypeObject').type)
3165 3166
                    node.args[1] = ExprNodes.CastNode(node.args[1], PyTypeObjectPtr)
        return node
Stefan Behnel's avatar
Stefan Behnel committed
3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177

    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
3178 3179 3180 3181 3182 3183 3184 3185 3186

    def visit_NoneCheckNode(self, node):
        """Remove None checks from expressions that definitely do not
        carry a None value.
        """
        self.visitchildren(node)
        if not node.arg.may_be_none():
            return node.arg
        return node