DeepCode's Top Findings #13: Writing Immutable Objects in Python

DeepCode offers an AI-based Static Program Analysis for Java, JavaScript and TypeScript, C/C++ and Python. As you might know, DeepCode uses thousands of open source repos to train our engine. We asked the engine team to provide some stats on the findings. On the top suggestions from our engine, we want to introduce and give some background in this series of blog articles.

Language: Python
Defect: X is an immutable object and one of its elements gets assigned
Diagnose: The code tries to write to an element within an instance of an immutable data type

I found this example in monkeylyf / interviewjam and as usual, you can open the repo in DeepCode and follow along. Below is the snippet of the dashboard in DeepCode:

def findCelebrityWithExtraSpace(self, n):
    """
    :type n: int
    :rtype: int
    """
    stack = range(n)
...
            stack[-2] = a
...

DeepCode gives us the feedback "Trying to store a value in element of immutable type range (from call to range) will lead to a crash." But does range() not bring a list back? Well, that used to be...

Let us replay what happens in the Python interpreter:

Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> stack = range(10)
>>> stack
range(0, 10)
>>> a = stack[-1]
>>> stack[-2] = a
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'range' object does not support item assignment
>>>

What we are calling here is the range() function. In Python3 it is a renamed version of Python2's xrange() function. This means it does not actually produce a list with a sequence of values. Rather, it uses yielding to produce the specific value when it is needed instead of storing vast amounts of data. That is the reason why Python says the range object does not support item assignment. And by the way, it also does not support the pop() function which is used in the code example.

In the above code example, the application would crash when trying to write into the range object. Yet, as ranges are used often as a sequencer for loops, ranges can get quite large. Thus it makes sense to use such a range object instead of a list. Yet, if you need the list as a datastore - such as in our example here - there is an easy way to get lists with value sequences:

stack = list(range(n))

For the static code analysis, the task here was to understand the underlying type returned by the range() function and infer the abilities the type has (like supporting index operators).

Test it yourself and run analysis over your code. It is very fast and free to check out at deepcode.ai.