1#     Copyright 2021, Kay Hayen, mailto:kay.hayen@gmail.com
2#
3#     Part of "Nuitka", an optimizing Python compiler that is compatible and
4#     integrates with CPython, but also works on its own.
5#
6#     Licensed under the Apache License, Version 2.0 (the "License");
7#     you may not use this file except in compliance with the License.
8#     You may obtain a copy of the License at
9#
10#        http://www.apache.org/licenses/LICENSE-2.0
11#
12#     Unless required by applicable law or agreed to in writing, software
13#     distributed under the License is distributed on an "AS IS" BASIS,
14#     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15#     See the License for the specific language governing permissions and
16#     limitations under the License.
17#
18""" Node the calls to the 'range' built-in.
19
20This is a rather complex beast as it has many cases, is difficult to know if
21it's sizable enough to compute, and there are complex cases, where the bad
22result of it can be predicted still, and these are interesting for warnings.
23
24"""
25
26import math
27
28from nuitka.PythonVersions import python_version
29from nuitka.specs import BuiltinParameterSpecs
30
31from .ExpressionBases import (
32    ExpressionChildHavingBase,
33    ExpressionChildrenHavingBase,
34)
35from .IterationHandles import (
36    IterationHandleRange1,
37    IterationHandleRange2,
38    IterationHandleRange3,
39)
40from .NodeMakingHelpers import makeConstantReplacementNode
41from .shapes.BuiltinTypeShapes import tshape_list, tshape_xrange
42
43
44class ExpressionBuiltinRangeMixin(object):
45    """Mixin class for range nodes with 1/2/3 arguments."""
46
47    # Mixins are required to slots
48    __slots__ = ()
49
50    builtin_spec = BuiltinParameterSpecs.builtin_range_spec
51
52    @staticmethod
53    def getTypeShape():
54        return tshape_list
55
56    def getTruthValue(self):
57        length = self.getIterationLength()
58
59        if length is None:
60            return None
61        else:
62            return length > 0
63
64    def mayHaveSideEffects(self):
65        for child in self.getVisitableNodes():
66            if child.mayHaveSideEffects():
67                return True
68
69            if child.getIntegerValue() is None:
70                return True
71
72            if python_version >= 0x270 and child.isExpressionConstantFloatRef():
73                return True
74
75        return False
76
77    def mayRaiseException(self, exception_type):
78        for child in self.getVisitableNodes():
79            if child.mayRaiseException(exception_type):
80                return True
81
82            # TODO: Should take exception_type value into account here.
83            if child.getIntegerValue() is None:
84                return True
85
86            if python_version >= 0x270 and child.isExpressionConstantFloatRef():
87                return True
88
89        step = self.subnode_step
90
91        # A step of 0 will raise.
92        if step is not None and step.getIntegerValue() == 0:
93            return True
94
95        return False
96
97    def computeBuiltinSpec(self, trace_collection, given_values):
98        assert self.builtin_spec is not None, self
99
100        if not self.builtin_spec.isCompileTimeComputable(given_values):
101            trace_collection.onExceptionRaiseExit(BaseException)
102
103            # TODO: Raise exception known step 0.
104
105            return self, None, None
106
107        return trace_collection.getCompileTimeComputationResult(
108            node=self,
109            computation=lambda: self.builtin_spec.simulateCall(given_values),
110            description="Built-in call to '%s' computed."
111            % (self.builtin_spec.getName()),
112        )
113
114    def computeExpressionIter1(self, iter_node, trace_collection):
115        assert python_version < 0x300
116
117        # TODO: The xrange is always faster and more memory usage than range, so this makes no sense, to
118        # use it as a source for any iteration, esp. as xrange is the Python3 only type that will be
119        # best optimized.
120        result = makeExpressionBuiltinXrange(
121            low=self.subnode_low,
122            high=self.subnode_high,
123            step=self.subnode_step,
124            source_ref=self.source_ref,
125        )
126
127        self.parent.replaceChild(self, result)
128        del self.parent
129
130        return (
131            iter_node,
132            "new_expression",
133            "Replaced 'range' with 'xrange' built-in call for iteration.",
134        )
135
136    def canPredictIterationValues(self):
137        return self.getIterationLength() is not None
138
139
140class ExpressionBuiltinRange1(ExpressionBuiltinRangeMixin, ExpressionChildHavingBase):
141    kind = "EXPRESSION_BUILTIN_RANGE1"
142
143    named_child = "low"
144
145    subnode_high = None
146    subnode_step = None
147
148    def __init__(self, low, source_ref):
149        assert low is not None
150        assert python_version < 0x300
151
152        ExpressionChildHavingBase.__init__(self, value=low, source_ref=source_ref)
153
154    def computeExpression(self, trace_collection):
155        low = self.subnode_low
156
157        return self.computeBuiltinSpec(
158            trace_collection=trace_collection, given_values=(low,)
159        )
160
161    def getIterationLength(self):
162        low = self.subnode_low.getIntegerValue()
163
164        if low is None:
165            return None
166
167        return max(0, low)
168
169    def getIterationHandle(self):
170        low = self.subnode_low.getIntegerValue()
171        if low is None:
172            return None
173
174        return IterationHandleRange1(low, self.source_ref)
175
176    def getIterationValue(self, element_index):
177        length = self.getIterationLength()
178
179        if length is None:
180            return None
181
182        if element_index > length:
183            return None
184
185        # TODO: Make sure to cast element_index to what CPython will give, for
186        # now a downcast will do.
187        return makeConstantReplacementNode(
188            constant=int(element_index), node=self, user_provided=False
189        )
190
191    def isKnownToBeIterable(self, count):
192        return count is None or count == self.getIterationLength()
193
194
195class ExpressionBuiltinRange2(
196    ExpressionBuiltinRangeMixin, ExpressionChildrenHavingBase
197):
198    kind = "EXPRESSION_BUILTIN_RANGE2"
199
200    named_children = ("low", "high")
201
202    subnode_step = None
203
204    def __init__(self, low, high, source_ref):
205        ExpressionChildrenHavingBase.__init__(
206            self, values={"low": low, "high": high}, source_ref=source_ref
207        )
208
209    builtin_spec = BuiltinParameterSpecs.builtin_range_spec
210
211    def computeExpression(self, trace_collection):
212        assert python_version < 0x300
213
214        low = self.subnode_low
215        high = self.subnode_high
216
217        return self.computeBuiltinSpec(
218            trace_collection=trace_collection, given_values=(low, high)
219        )
220
221    def getIterationLength(self):
222        low = self.subnode_low
223        high = self.subnode_high
224
225        low = low.getIntegerValue()
226
227        if low is None:
228            return None
229
230        high = high.getIntegerValue()
231
232        if high is None:
233            return None
234
235        return max(0, high - low)
236
237    def getIterationHandle(self):
238        low = self.subnode_low.getIntegerValue()
239        if low is None:
240            return None
241
242        high = self.subnode_high.getIntegerValue()
243        if high is None:
244            return None
245
246        return IterationHandleRange2(low, high, self.source_ref)
247
248    def getIterationValue(self, element_index):
249        low = self.subnode_low
250        high = self.subnode_high
251
252        low = low.getIntegerValue()
253
254        if low is None:
255            return None
256
257        high = high.getIntegerValue()
258
259        if high is None:
260            return None
261
262        result = low + element_index
263
264        if result >= high:
265            return None
266        else:
267            return makeConstantReplacementNode(
268                constant=result, node=self, user_provided=False
269            )
270
271    def isKnownToBeIterable(self, count):
272        return count is None or count == self.getIterationLength()
273
274
275class ExpressionBuiltinRange3(
276    ExpressionBuiltinRangeMixin, ExpressionChildrenHavingBase
277):
278    kind = "EXPRESSION_BUILTIN_RANGE3"
279
280    named_children = ("low", "high", "step")
281
282    def __init__(self, low, high, step, source_ref):
283        assert python_version < 0x300
284
285        ExpressionChildrenHavingBase.__init__(
286            self, values={"low": low, "high": high, "step": step}, source_ref=source_ref
287        )
288
289    builtin_spec = BuiltinParameterSpecs.builtin_range_spec
290
291    def computeExpression(self, trace_collection):
292        low = self.subnode_low
293        high = self.subnode_high
294        step = self.subnode_step
295
296        return self.computeBuiltinSpec(
297            trace_collection=trace_collection, given_values=(low, high, step)
298        )
299
300    def getIterationLength(self):
301        low = self.subnode_low
302        high = self.subnode_high
303        step = self.subnode_step
304
305        low = low.getIntegerValue()
306
307        if low is None:
308            return None
309
310        high = high.getIntegerValue()
311
312        if high is None:
313            return None
314
315        step = step.getIntegerValue()
316
317        if step is None:
318            return None
319
320        # Give up on this, will raise ValueError.
321        if step == 0:
322            return None
323
324        if low < high:
325            if step < 0:
326                estimate = 0
327            else:
328                estimate = math.ceil(float(high - low) / step)
329        else:
330            if step > 0:
331                estimate = 0
332            else:
333                estimate = math.ceil(float(high - low) / step)
334
335        estimate = round(estimate)
336
337        assert estimate >= 0
338
339        return int(estimate)
340
341    def canPredictIterationValues(self):
342        return self.getIterationLength() is not None
343
344    def getIterationHandle(self):
345        low = self.subnode_low.getIntegerValue()
346        if low is None:
347            return None
348
349        high = self.subnode_high.getIntegerValue()
350        if high is None:
351            return None
352
353        step = self.subnode_step.getIntegerValue()
354        if step is None:
355            return None
356
357        # Give up on this, will raise ValueError.
358        if step == 0:
359            return None
360
361        return IterationHandleRange3(low, high, step, self.source_ref)
362
363    def getIterationValue(self, element_index):
364        low = self.subnode_low.getIntegerValue()
365
366        if low is None:
367            return None
368
369        high = self.subnode_high.getIntegerValue()
370
371        if high is None:
372            return None
373
374        step = self.subnode_step.getIntegerValue()
375
376        result = low + step * element_index
377
378        if result >= high:
379            return None
380        else:
381            return makeConstantReplacementNode(
382                constant=result, node=self, user_provided=False
383            )
384
385    def isKnownToBeIterable(self, count):
386        return count is None or count == self.getIterationLength()
387
388
389class ExpressionBuiltinXrangeMixin(object):
390    """Mixin class for xrange nodes with 1/2/3 arguments."""
391
392    # Mixins are required to slots
393    __slots__ = ()
394
395    builtin_spec = BuiltinParameterSpecs.builtin_xrange_spec
396
397    @staticmethod
398    def getTypeShape():
399        return tshape_xrange
400
401    def canPredictIterationValues(self):
402        return self.getIterationLength() is not None
403
404    def getTruthValue(self):
405        length = self.getIterationLength()
406
407        if length is None:
408            return None
409        else:
410            return length > 0
411
412    def mayHaveSideEffects(self):
413        for child in self.getVisitableNodes():
414            if child.mayHaveSideEffects():
415                return True
416
417            if child.getIntegerValue() is None:
418                return True
419
420        return False
421
422    def mayRaiseException(self, exception_type):
423        for child in self.getVisitableNodes():
424            if child.mayRaiseException(exception_type):
425                return True
426
427            # TODO: Should take exception_type value into account here.
428            if child.getIntegerValue() is None:
429                return True
430
431        step = self.subnode_step
432
433        # A step of 0 will raise.
434        if step is not None and step.getIntegerValue() == 0:
435            return True
436
437        return False
438
439    def computeBuiltinSpec(self, trace_collection, given_values):
440        assert self.builtin_spec is not None, self
441
442        if not self.builtin_spec.isCompileTimeComputable(given_values):
443            trace_collection.onExceptionRaiseExit(BaseException)
444
445            # TODO: Raise exception known step 0.
446
447            return self, None, None
448
449        return trace_collection.getCompileTimeComputationResult(
450            node=self,
451            computation=lambda: self.builtin_spec.simulateCall(given_values),
452            description="Built-in call to '%s' computed."
453            % (self.builtin_spec.getName()),
454        )
455
456    def computeExpressionIter1(self, iter_node, trace_collection):
457        # No exception will be raised on xrange iteration, but there is nothing to
458        # lower for, virtual method: pylint: disable=no-self-use
459
460        return iter_node, None, None
461
462
463class ExpressionBuiltinXrange1(ExpressionBuiltinXrangeMixin, ExpressionChildHavingBase):
464    kind = "EXPRESSION_BUILTIN_XRANGE1"
465
466    named_child = "low"
467
468    subnode_high = None
469    subnode_step = None
470
471    def __init__(self, low, source_ref):
472        ExpressionChildHavingBase.__init__(self, value=low, source_ref=source_ref)
473
474    def computeExpression(self, trace_collection):
475        low = self.subnode_low
476
477        # TODO: Optimize this if self.subnode_low.getIntegerValue() is Not None
478        return self.computeBuiltinSpec(
479            trace_collection=trace_collection, given_values=(low,)
480        )
481
482    def getIterationLength(self):
483        low = self.subnode_low.getIntegerValue()
484
485        if low is None:
486            return None
487
488        return max(0, low)
489
490    def getIterationValue(self, element_index):
491        length = self.getIterationLength()
492
493        if length is None:
494            return None
495
496        if element_index > length:
497            return None
498
499        # TODO: Make sure to cast element_index to what CPython will give, for
500        # now a downcast will do.
501        return makeConstantReplacementNode(
502            constant=int(element_index), node=self, user_provided=False
503        )
504
505
506class ExpressionBuiltinXrange2(
507    ExpressionBuiltinXrangeMixin, ExpressionChildrenHavingBase
508):
509    kind = "EXPRESSION_BUILTIN_XRANGE2"
510
511    named_children = ("low", "high")
512
513    subnode_step = None
514
515    def __init__(self, low, high, source_ref):
516        ExpressionChildrenHavingBase.__init__(
517            self, values={"low": low, "high": high}, source_ref=source_ref
518        )
519
520    def computeExpression(self, trace_collection):
521        low = self.subnode_low
522        high = self.subnode_high
523
524        return self.computeBuiltinSpec(
525            trace_collection=trace_collection, given_values=(low, high)
526        )
527
528    def getIterationLength(self):
529        low = self.subnode_low
530        high = self.subnode_high
531
532        low = low.getIntegerValue()
533
534        if low is None:
535            return None
536
537        high = high.getIntegerValue()
538
539        if high is None:
540            return None
541
542        return max(0, high - low)
543
544    def getIterationValue(self, element_index):
545        low = self.subnode_low
546        high = self.subnode_high
547
548        low = low.getIntegerValue()
549
550        if low is None:
551            return None
552
553        high = high.getIntegerValue()
554
555        if high is None:
556            return None
557
558        result = low + element_index
559
560        if result >= high:
561            return None
562        else:
563            return makeConstantReplacementNode(
564                constant=result, node=self, user_provided=False
565            )
566
567
568class ExpressionBuiltinXrange3(
569    ExpressionBuiltinXrangeMixin, ExpressionChildrenHavingBase
570):
571    kind = "EXPRESSION_BUILTIN_XRANGE3"
572
573    named_children = ("low", "high", "step")
574
575    def __init__(self, low, high, step, source_ref):
576        ExpressionChildrenHavingBase.__init__(
577            self, values={"low": low, "high": high, "step": step}, source_ref=source_ref
578        )
579
580    def computeExpression(self, trace_collection):
581        low = self.subnode_low
582        high = self.subnode_high
583        step = self.subnode_step
584
585        return self.computeBuiltinSpec(
586            trace_collection=trace_collection, given_values=(low, high, step)
587        )
588
589    def getIterationLength(self):
590        low = self.subnode_low
591        high = self.subnode_high
592        step = self.subnode_step
593
594        low = low.getIntegerValue()
595
596        if low is None:
597            return None
598
599        high = high.getIntegerValue()
600
601        if high is None:
602            return None
603
604        step = step.getIntegerValue()
605
606        if step is None:
607            return None
608
609        # Give up on this, will raise ValueError.
610        if step == 0:
611            return None
612
613        if low < high:
614            if step < 0:
615                estimate = 0
616            else:
617                estimate = math.ceil(float(high - low) / step)
618        else:
619            if step > 0:
620                estimate = 0
621            else:
622                estimate = math.ceil(float(high - low) / step)
623
624        estimate = round(estimate)
625
626        assert estimate >= 0
627
628        return int(estimate)
629
630    def getIterationValue(self, element_index):
631        low = self.subnode_low.getIntegerValue()
632
633        if low is None:
634            return None
635
636        high = self.subnode_high.getIntegerValue()
637
638        if high is None:
639            return None
640
641        step = self.subnode_step.getIntegerValue()
642
643        result = low + step * element_index
644
645        if result >= high:
646            return None
647        else:
648            return makeConstantReplacementNode(
649                constant=result, node=self, user_provided=False
650            )
651
652
653def makeExpressionBuiltinXrange(low, high, step, source_ref):
654    if high is None:
655        return ExpressionBuiltinXrange1(low=low, source_ref=source_ref)
656    elif step is None:
657        return ExpressionBuiltinXrange2(low=low, high=high, source_ref=source_ref)
658    else:
659        return ExpressionBuiltinXrange3(
660            low=low, high=high, step=step, source_ref=source_ref
661        )
662