From ec219ba1c04c4514b8b004239b1a0eac914dde4a Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Fri, 22 May 2015 19:29:22 -0700
Subject: Issue #23086: Add start and stop arguments to the Sequence.index()
 mixin method.

---
 Doc/library/collections.abc.rst | 14 ++++++++++++++
 Lib/_collections_abc.py         | 20 +++++++++++++++-----
 Lib/test/test_collections.py    | 35 +++++++++++++++++++++++++++++++++++
 Misc/ACKS                       |  1 +
 Misc/NEWS                       |  4 ++++
 5 files changed, 69 insertions(+), 5 deletions(-)

diff --git a/Doc/library/collections.abc.rst b/Doc/library/collections.abc.rst
index 28ba430..0039bb2 100644
--- a/Doc/library/collections.abc.rst
+++ b/Doc/library/collections.abc.rst
@@ -121,6 +121,20 @@ ABC                        Inherits from          Abstract Methods        Mixin
 
    ABCs for read-only and mutable :term:`sequences <sequence>`.
 
+   Implementation note: Some of the mixin methods, such as
+   :meth:`__iter__`, :meth:`__reversed__` and :meth:`index`, make
+   repeated calls to the underlying :meth:`__getitem__` method.
+   Consequently, if :meth:`__getitem__` is implemented with constant
+   access speed, the mixin methods will have linear performance;
+   however, if the underlying method is linear (as it would be with a
+   linked list), the mixins will have quadratic performance and will
+   likely need to be overridden.
+
+   .. versionchanged:: 3.5
+      The index() method added support for *stop* and *start*
+      arguments.
+
+
 .. class:: Set
            MutableSet
 
diff --git a/Lib/_collections_abc.py b/Lib/_collections_abc.py
index 2f83543..0ca7deb 100644
--- a/Lib/_collections_abc.py
+++ b/Lib/_collections_abc.py
@@ -825,13 +825,23 @@ class Sequence(Sized, Iterable, Container):
         for i in reversed(range(len(self))):
             yield self[i]
 
-    def index(self, value):
-        '''S.index(value) -> integer -- return first index of value.
+    def index(self, value, start=0, stop=None):
+        '''S.index(value, [start, [stop]]) -> integer -- return first index of value.
            Raises ValueError if the value is not present.
         '''
-        for i, v in enumerate(self):
-            if v == value:
-                return i
+        if start is not None and start < 0:
+            start = max(len(self) + start, 0)
+        if stop is not None and stop < 0:
+            stop += len(self)
+
+        i = start
+        while stop is None or i < stop:
+            try:
+                if self[i] == value:
+                    return i
+            except IndexError:
+                break
+            i += 1
         raise ValueError
 
     def count(self, value):
diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py
index a15651f..ec86466 100644
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -1227,6 +1227,41 @@ class TestCollectionABCs(ABCTestCase):
         self.validate_abstract_methods(Sequence, '__contains__', '__iter__', '__len__',
             '__getitem__')
 
+    def test_Sequence_mixins(self):
+        class SequenceSubclass(Sequence):
+            def __init__(self, seq=()):
+                self.seq = seq
+
+            def __getitem__(self, index):
+                return self.seq[index]
+
+            def __len__(self):
+                return len(self.seq)
+
+        # Compare Sequence.index() behavior to (list|str).index() behavior
+        def assert_index_same(seq1, seq2, index_args):
+            try:
+                expected = seq1.index(*index_args)
+            except ValueError:
+                with self.assertRaises(ValueError):
+                    seq2.index(*index_args)
+            else:
+                actual = seq2.index(*index_args)
+                self.assertEqual(
+                    actual, expected, '%r.index%s' % (seq1, index_args))
+
+        for ty in list, str:
+            nativeseq = ty('abracadabra')
+            indexes = [-10000, -9999] + list(range(-3, len(nativeseq) + 3))
+            seqseq = SequenceSubclass(nativeseq)
+            for letter in set(nativeseq) | {'z'}:
+                assert_index_same(nativeseq, seqseq, (letter,))
+                for start in range(-3, len(nativeseq) + 3):
+                    assert_index_same(nativeseq, seqseq, (letter, start))
+                    for stop in range(-3, len(nativeseq) + 3):
+                        assert_index_same(
+                            nativeseq, seqseq, (letter, start, stop))
+
     def test_ByteString(self):
         for sample in [bytes, bytearray]:
             self.assertIsInstance(sample(), ByteString)
diff --git a/Misc/ACKS b/Misc/ACKS
index 4d3e290..76f2df8 100644
--- a/Misc/ACKS
+++ b/Misc/ACKS
@@ -660,6 +660,7 @@ Bill Janssen
 Thomas Jarosch
 Juhana Jauhiainen
 Rajagopalasarma Jayakrishnan
+Devin Jeanpierre
 Zbigniew Jędrzejewski-Szmek
 Julien Jehannet
 Muhammad Jehanzeb
diff --git a/Misc/NEWS b/Misc/NEWS
index 02ce0e7..9239cbb 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -73,6 +73,10 @@ Library
 
 - Issue #23973: PEP 484: Add the typing module.
 
+- Issue #23086: The collections.abc.Sequence() abstract base class added
+  *start* and *stop* parameters to the index() mixin.
+  Patch by Devin Jeanpierre.
+
 - Issue #20035: Replaced the ``tkinter._fix`` module used for setting up the
   Tcl/Tk environment on Windows with a private function in the ``_tkinter``
   module that makes no permanent changes to the environment.
-- 
cgit v0.12