reversed(range(x, -1, -1)) is empty when x > 1

[3767615f-e34f-48d9-8059-23c34a5efe77]

BPO	7298
Nosy	@mdickinson, @pitrou, @ericvsmith
Files	issue7298_test.patch: Tests for this issue. issue7298.patch issue7298_v2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = 'https://github.com/mdickinson' closed_at = created_at = labels = ['interpreter-core', 'type-bug', 'release-blocker'] title = 'reversed(range(x, -1, -1)) is empty when x > 1' updated_at = user = 'https://bugs.python.org/ledave123' ``` bugs.python.org fields: ```python activity = actor = 'mark.dickinson' assignee = 'mark.dickinson' closed = True closed_date = closer = 'mark.dickinson' components = ['Interpreter Core'] creation = creator = 'ledave123' dependencies = [] files = ['15306', '15310', '15329'] hgrepos = [] issue_num = 7298 keywords = ['patch'] message_count = 17.0 messages = ['95104', '95105', '95108', '95110', '95116', '95147', '95148', '95149', '95211', '95213', '95236', '95239', '95282', '95287', '95318', '95326', '95327'] nosy_count = 4.0 nosy_names = ['mark.dickinson', 'pitrou', 'eric.smith', 'ledave123'] pr_nums = [] priority = 'release blocker' resolution = 'fixed' stage = 'patch review' status = 'closed' superseder = None type = 'behavior' url = 'https://bugs.python.org/issue7298' versions = ['Python 2.6', 'Python 2.7'] ```

[3767615f-e34f-48d9-8059-23c34a5efe77]

On python 2.4.4, reversed(range()) is correct :
>>> list(reversed(range(12,-1,-1)))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

However, on python 3.1.1 :
>>> list(reversed(range(12,-1,-1)))
[]
which is obviously wrong.

When step is positive, the result is okay on python 3.1.1 :
>>> list(reversed(range(13)))
[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

[mdickinson]

Nice catch! Thanks for reporting this.

get_len_of_range in Objects/rangeobject.c only works for positive steps, but is being called with a negative step here.

I think get_len_of_range should be changed to work with both positive and negative steps. It's only called from one other place, and that place also has to deal with negative steps. (And I'm not convinced that this place is dealing with negative steps correctly either: it uses simply -step to negate the step, which can overflow if step == LONG_MIN.)

I'll put a patch together.

[mdickinson]

There's another problem with range_reverse: it uses a short range (all fields longs) if start, stop and step fit into a C long. But it doesn't check whether the length fits into a C long. This leads to the following:

>>> list(reversed(range(-1, 2**63-1)))
[]

(this is on a 64-bit machine; for a 32-bit machine the same failure should occur with 2**31-1 in place of 2**63-1).

[mdickinson]

Further investigations show that range_iter has the same problem. :-(

>>> for x in range(-1, 2**63-1): print(x)
...
(no output)

This really needs to be fixed. Upgrading to release blocker, and removing the easy flag.

[mdickinson]

Here are some tests.

[mdickinson]

and here's a patch (includes the earlier tests).

[mdickinson]

I've uploaded this patch to Rietveld to make it easier to review:

http://codereview.appspot.com/154060/show

[ericvsmith]

I reviewed the issue on Rietveld, and it looks fine to me with the exception of my comment about the tests. The comment is mostly a nit, so if you don't agree don't worry about it.

I tested it with and without pydebug and the tests pass.

I think this should be committed and backported.

[mdickinson]

Thanks for reviewing, Eric. I'll work a bit more on the tests.

I'm also not sure what to do about 2.x: here reversed(xrange(start, stop, step)) has some of the same problems for large numbers. (E.g., if step == LONG_MIN.)

The options are: (1) have reversed(x) raise ValueError for some extreme xrange instances x, or (2) rework the internals so that reversed(x) always works.

Given that this is a bugfix, I'm inclined to go for (1) for now; we can always look at reworking xrange later on, for 2.7 and 3.2.

[ericvsmith]

For 2.x, I'd just raise an exception. No one is going to be using a step of LONG_MIN.

[mdickinson]

It looks like the PyLong version of reverse is broken too:

>>> list(range(10**100, 10**100-2, -2))
[1000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000]
>>> list(reversed(range(10**100, 10**100-2, -2)))
[9999999999999999999999999999999999999999999999999999999999999999999999999
999999999999999999999999998]

[mdickinson]

I've updated to patch to improve the tests, and fix the problems with the PyLong version of range.__reversed__. (Also updated on Rietveld.)

[mdickinson]

The fix was applied to py3k in r76292, but I bodged the commit and committed some extra (non-working) code by mistake. That was removed in r76293, so all should be well now.

Merged to release31-maint in r76294.

trunk and the 2.6 maintenance branch also need some (but not all) of these fixes backporting.

[mdickinson]

Backported the tests and some of the fixes to 2.x in r76295 (trunk) and r76296 (release26-maint).

2.x seems to have been producing correct results in all cases on my machine. The only problem on 2.x was that the code depended on signed arithmetic wrapping modulo 2**width (undefined behaviour! very bad!);
now it only depends on unsigned -> signed conversions wrapping modulo 2**width, which still isn't guaranteed by the C standards, but it's merely implementation-defined behaviour rather than undefined behaviour, and all implementations that I'm aware of do this.

[pitrou]

Not sure whether it's related, but there is now a sizeable refleak:

test_range beginning 6 repetitions 123456 ...... test_range leaked [150, 150, 150] references, sum=450

[mdickinson]

Thanks, Antoine. I'll investigate.

[mdickinson]

Looks like Benjamin already fixed the refleak in r76319, r76320.