classification
Title: Add start and stop parameters to the Sequence.index() ABC mixin method
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Devin Jeanpierre, josh.r, python-dev, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2014-12-18 20:41 by rhettinger, last changed 2015-05-23 02:31 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
issue23086.patch Devin Jeanpierre, 2015-01-05 23:58 Patch with tests. review
issue23086.2.patch Devin Jeanpierre, 2015-01-07 17:42 Updated patch with test. review
Messages (17)
msg232904 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-12-18 20:41
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.
msg233485 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-05 23:58
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.
msg233564 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-07 06:48
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)
msg233589 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-07 17:42
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.
msg233590 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-07 17:43
Why is there no "review" link next to my second patch?
msg233635 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-08 09:46
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
msg233684 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-08 19:22
Are you sure? I noticed that __iter__ went out of its way to avoid calling len().
msg233693 - (view) Author: Josh Rosenberg (josh.r) * Date: 2015-01-08 22:44
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.
msg233695 - (view) Author: Josh Rosenberg (josh.r) * Date: 2015-01-08 22:49
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.
msg233698 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-08 23:41
I'm going to add a test case that changes the sequence length during .index(), and just do whatever list does in that case.
msg233722 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-09 07:26
I take it back, I don't want to copy what the list type does, because it's wrong: http://bugs.python.org/issue23204
msg233724 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-09 08:01
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.
msg233736 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-01-09 08:46
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.
msg233761 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-09 15:58
> The iteration usually has linear complexity

The iteration abstract method depends on indexing as well:

    def __iter__(self):
        i = 0
        try:
            while True:
                v = self[i]
                yield v
                i += 1
        except IndexError:
            return
msg233791 - (view) Author: Devin Jeanpierre (Devin Jeanpierre) * Date: 2015-01-10 00:53
I inferred from Serhiy's comment that if you override __iter__ to be efficient and not use __getitem__, this overridden behavior used to pass on to index(), but wouldn't after this patch.
msg243880 - (view) Author: Roundup Robot (python-dev) Date: 2015-05-23 02:29
New changeset cabd7261ae80 by Raymond Hettinger in branch 'default':
Issue #23086: Add start and stop arguments to the Sequence.index() mixin method.
https://hg.python.org/cpython/rev/cabd7261ae80
msg243881 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-05-23 02:31
Devin, thanks for the patch.

Serhiy, I added a performance note discussing the computational complexity.
History
Date User Action Args
2015-05-23 02:31:23rhettingersetstatus: open -> closed
resolution: fixed
messages: + msg243881

stage: patch review -> resolved
2015-05-23 02:29:35python-devsetnosy: + python-dev
messages: + msg243880
2015-01-10 00:53:47Devin Jeanpierresetmessages: + msg233791
2015-01-09 15:58:12rhettingersetmessages: + msg233761
2015-01-09 08:46:28serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg233736

type: enhancement
stage: patch review
2015-01-09 08:01:21rhettingersetmessages: + msg233724
2015-01-09 07:26:25Devin Jeanpierresetmessages: + msg233722
2015-01-08 23:41:09Devin Jeanpierresetmessages: + msg233698
2015-01-08 22:49:41josh.rsetmessages: + msg233695
2015-01-08 22:44:10josh.rsetnosy: + josh.r
messages: + msg233693
2015-01-08 19:22:21Devin Jeanpierresetmessages: + msg233684
2015-01-08 09:46:16rhettingersetmessages: + msg233635
2015-01-07 17:43:13Devin Jeanpierresetmessages: + msg233590
2015-01-07 17:42:33Devin Jeanpierresetfiles: + issue23086.2.patch

messages: + msg233589
2015-01-07 06:48:25rhettingersetmessages: + msg233564
2015-01-05 23:58:20Devin Jeanpierresetfiles: + issue23086.patch

nosy: + Devin Jeanpierre
messages: + msg233485

keywords: + patch
2014-12-18 20:41:46rhettingercreate