[Python-checkins] python/dist/src/Lib doctest.py,1.67,1.68

[tim_one at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Lib
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv16095/Lib

Modified Files:
	doctest.py 
Log Message:
Replaced the ELLIPSIS implementation with a worst-case linear-time one.


Index: doctest.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/doctest.py,v
retrieving revision 1.67
retrieving revision 1.68
diff -C2 -d -r1.67 -r1.68
*** doctest.py	19 Aug 2004 06:49:33 -0000	1.67
--- doctest.py	19 Aug 2004 08:10:07 -0000	1.68
***************
*** 363,366 ****
--- 363,410 ----
              del self.softspace
  
+ # Worst-case linear-time ellipsis matching.
+ def ellipsis_match(want, got):
+     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.
+     w = ws[0]
+     if w:
+         # An ellipsis didn't start `want`.  We need to match exactly
+         # at the start.
+         if not got.startswith(w):
+             return False
+         pos = len(w)
+         del ws[0]
+     else:
+         pos = 0
+ 
+     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:
+             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])
+ 
  ######################################################################
  ## 2. Example & DocTest
***************
*** 1476,1495 ****
  
          # The ELLIPSIS flag says to let the sequence "..." in `want`
!         # match any substring in `got`.  We implement this by
!         # transforming `want` into a regular expression.
          if optionflags & ELLIPSIS:
!             # Remove \n from ...\n, else the newline will be required,
!             # and (for example) ... on a line by itself can't match
!             # nothing gracefully.
!             want_re = want.replace(ELLIPSIS_MARKER + '\n', ELLIPSIS_MARKER)
!             # Escape any special regexp characters
!             want_re = re.escape(want_re)
!             # Replace escaped ellipsis markers ('\.\.\.') with .*
!             want_re = want_re.replace(re.escape(ELLIPSIS_MARKER), '.*')
!             # Require that it matches the entire string; and set the
!             # re.DOTALL flag (with '(?s)').
!             want_re = '(?s)^%s$' % want_re
!             # Check if the `want_re` regexp matches got.
!             if re.match(want_re, got):
                  return True
  
--- 1520,1526 ----
  
          # The ELLIPSIS flag says to let the sequence "..." in `want`
!         # match any substring in `got`.
          if optionflags & ELLIPSIS:
!             if ellipsis_match(want, got):
                  return True