Add start and stop parameters to the Sequence.index() ABC mixin method

[rhettinger]

BPO	23086
Nosy	@rhettinger, @ssbr, @serhiy-storchaka, @MojoVampire
Files	issue23086.patch: Patch with tests. issue23086.2.patch: Updated patch with test.

^{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:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2015-05-23.02:31:23.191>
created_at = <Date 2014-12-18.20:41:46.585>
labels = ['type-feature', 'library']
title = 'Add start and stop parameters to the Sequence.index() ABC mixin method'
updated_at = <Date 2015-05-23.02:31:23.190>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2015-05-23.02:31:23.190>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2015-05-23.02:31:23.191>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2014-12-18.20:41:46.585>
creator = 'rhettinger'
dependencies = []
files = ['37607', '37631']
hgrepos = []
issue_num = 23086
keywords = ['patch']
message_count = 17.0
messages = ['232904', '233485', '233564', '233589', '233590', '233635', '233684', '233693', '233695', '233698', '233722', '233724', '233736', '233761', '233791', '243880', '243881']
nosy_count = 5.0
nosy_names = ['rhettinger', 'Devin Jeanpierre', 'python-dev', 'serhiy.storchaka', 'josh.r']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue23086'
versions = ['Python 3.5']

[rhettinger]

Currently, the Sequence ABC doesn't support start and stop arguments for the index() method which limits its usefulness in doing repeated searches (iterating over a target value) and which limits it substitutablity for various concrete sequences such as tuples, lists, strings, bytes, bytearrays, etc.

>>> help(Sequence.index)
Help on method index in module _abcoll:

index(self, value) unbound _abcoll.Sequence method
S.index(value) -> integer -- return first index of value.
Raises ValueError if the value is not present.

>>> help(list.index)
Help on method_descriptor:

index(...)
 L.index(value, [start, [stop]]) -> integer -- return first index of value.
 Raises ValueError if the value is not present.

>>> help(str.index)
Help on method_descriptor:

index(...)
 S.index(sub [,start [,end]]) -> int
 
 Like S.find() but raise ValueError when the substring is not found.

>>> help(tuple.index)
Help on method_descriptor:

index(...)
 T.index(value, [start, [stop]]) -> integer -- return first index of value.
 Raises ValueError if the value is not present.

>>> help(bytes.index)
Help on method_descriptor:

index(...)
 S.index(sub [,start [,end]]) -> int
 
 Like S.find() but raise ValueError when the substring is not found.

>>> help(bytearray.index)
Help on method_descriptor:

index(...)
 B.index(sub [,start [,end]]) -> int
 
 Like B.find() but raise ValueError when the subsection is not found.

[ssbr]

A wild patch appears!

Test is included, I'm unhappy with it, because it uses one test method to test all of Sequence, but that's what the test suite does for MutableSequence.

[rhettinger]

This test looks like it may have been a typo:

self.assertEqual(seq.index('a'), 0, 1)

Also, it would be nice to investigate the differences with list.index() and str.index() for the corner cases. Something along these lines:

 # Compare Sequence.index() behavior to list.index() behavior 
 listseq = list('abracadabra')
 seqseq = SequenceSubclass(listseq)
 for start in range(-3, len(listseq) + 3):
 for stop in range(-3, len(listseq) + 3):
 for letter in set(listseq + ['z']):
 try:
 expected = listseq.index(letter, start, stop)
 except ValueError:
 with self.assertRaises(ValueError):
 seqseq.index(letter, start, stop)
 else:
 actual = seqseq.index(letter, start, stop)
 self.assertEqual(actual, expected, (letter, start, stop))

 # Compare Sequence.index() behavior to str.index() behavior 
 strseq = 'abracadabra'
 seqseq = SequenceSubclass(strseq)
 for start in range(-3, len(strseq) + 3):
 for stop in range(-3, len(strseq) + 3):
 for letter in set(strseq + 'z'):
 try:
 expected = strseq.index(letter, start, stop)
 except ValueError:
 with self.assertRaises(ValueError):
 seqseq.index(letter, start, stop)
 else:
 actual = seqseq.index(letter, start, stop)
 self.assertEqual(actual, expected, (letter, start, stop)

[ssbr]

I modified your test case somewhat. Also, your tests uncovered an issue with negative indexes -- oops, hadn't thought of those. Fixed. Let me know what you think.

[ssbr]

Why is there no "review" link next to my second patch?

[rhettinger]

Try something like this:

 if start < 0:
 start += len(self)
 if stop is None:
 stop = len(self)
 elif stop < 0:
 stop += len(self)
 for i in range(max(start, 0), min(stop, len(self))):
 if self[i] == value:
 return i
 raise ValueError

[ssbr]

Are you sure? I noticed that __iter__ went out of its way to avoid calling len().

[MojoVampire]

I think it avoids len because the length might change during iteration due to side-effects of other code. Since a shrinking sequence would raise an IndexError anyway when you overran the end, it may as well not assume the length is static and just keep indexing forward until it hits an IndexError. It's less of an issue (though not a non-issue) with index, because index actually performs all the indexing without returning to user code; __iter__ pauses to allow user code to execute between each yield, so the odds of a length mutation are much higher.

You might be able to use len (and just say that if a side-effect of an equality comparison causes the sequence to change length, or another thread messes with it, that's your own fault), but you'd probably want to catch and convert IndexError to ValueError to consistently respond to "we didn't find it" with the same exception.

[MojoVampire]

Note: index returns without the caller having a chance to execute code that would change the sequence length directly. But other threads could change it, as could a custom __eq__ on an object stored in the sequence (or a poorly implemented __getitem__ or __len__ on the sequence itself, but that's getting even more pathological). Thread consistency is the code's responsibility though (we just need to make sure we behave the best we can, and hope they use locks correctly), and the odds of equality of __getitem__ altering the sequence are much lower than the odds of someone iterating the sequence and changing it as they go (which is what __iter__'s implementation allows, responding with potentially incomplete results since items might be skipped due to the mutation), but keeping the sequence in a consistent state.

[ssbr]

I'm going to add a test case that changes the sequence length during .index(), and just do whatever list does in that case.

[ssbr]

I take it back, I don't want to copy what the list type does, because it's wrong: http://bugs.python.org/issue23204

[rhettinger]

I'm afraid you're getting lost in details that don't matter. We're trying to make the index() method more useful so that searches and be restarted where they left off.

[serhiy-storchaka]

I afraid that the patch can change computational complexity. The iteration usually has linear complexity, but indexing can has non-constant complexity. E.g. for linked list it will cause quadratic complexity of index(). May be we should have special case for start=0 and stop=None. And document this.