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