From dc5de3bab2f6a202b6cd4b94ae9ac8b46e804caa Mon Sep 17 00:00:00 2001
From: Tim Peters <tim.peters@gmail.com>
Date: Thu, 19 Aug 2004 14:06:20 +0000
Subject: ellipsis_match():  Changed treatment of start- and end-of-string
 exact matches to be symmetric.  This makes the algorithm easier to
 understand.

---
 Lib/doctest.py | 60 ++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 35 insertions(+), 25 deletions(-)

diff --git a/Lib/doctest.py b/Lib/doctest.py
index 6c5679d..c7a183b 100644
--- a/Lib/doctest.py
+++ b/Lib/doctest.py
@@ -364,47 +364,57 @@ class _SpoofOut(StringIO):
 
 # Worst-case linear-time ellipsis matching.
 def ellipsis_match(want, got):
+    """
+    Essentially the only subtle case:
+    >>> ellipsis_match('aa...aa', 'aaa')
+    False
+    """
     if ELLIPSIS_MARKER not in want:
         return want == got
     # Remove \n from ...\n, else the newline will be required,
     # and (for example) ... on a line by itself can't match
     # nothing gracefully.
     want = want.replace(ELLIPSIS_MARKER + '\n', ELLIPSIS_MARKER)
+
     # Find "the real" strings.
     ws = want.split(ELLIPSIS_MARKER)
     assert len(ws) >= 2
-    # Match.  In general, we only need to find the leftmost non-overlapping
-    # match for each piece.  "Real strings" at the start or end of `want`
-    # are special cases.
+
+    # Deal with exact matches possibly needed at one or both ends.
+    startpos, endpos = 0, len(got)
     w = ws[0]
-    if w:
-        # An ellipsis didn't start `want`.  We need to match exactly
-        # at the start.
-        if not got.startswith(w):
+    if w:   # starts with exact match
+        if got.startswith(w):
+            startpos = len(w)
+            del ws[0]
+        else:
+            return False
+    w = ws[-1]
+    if w:   # ends with exact match
+        if got.endswith(w):
+            endpos -= len(w)
+            del ws[-1]
+        else:
             return False
-        pos = len(w)
-        del ws[0]
-    else:
-        pos = 0
 
+    if startpos > endpos:
+        # Exact end matches required more characters than we have, as in
+        # ellipsis_match('aa...aa', 'aaa')
+        return False
+
+    # For the rest, we only need to find the leftmost non-overlapping
+    # match for each piece.  If there's no overall match that way alone,
+    # there's no overall match period.
     for w in ws:
         # w may be '' at times, if there are consecutive ellipses, or
         # due to an ellipsis at the start or end of `want`.  That's OK.
-        # Search for an empty string succeeds, and doesn't change pos.
-        pos = got.find(w, pos)
-        if pos < 0:
+        # Search for an empty string succeeds, and doesn't change startpos.
+        startpos = got.find(w, startpos, endpos)
+        if startpos < 0:
             return False
-        pos += len(w)
-
-    # If `want` ended with an ellipsis, the tail matches anything.
-    if ws[-1] == '':
-        return True
-    # Else `want` ended with a real string.  If the last real match
-    # exhausted `got`, we win.
-    if pos == len(got):
-        return True
-    # Else maybe we matched the last real string too early.
-    return got.endswith(ws[-1])
+        startpos += len(w)
+
+    return True
 
 ######################################################################
 ## 2. Example & DocTest
-- 
cgit v0.12