[Python-checkins] python/dist/src/Lib/test string_tests.py, 1.42, 1.43

[rhettinger at users.sourceforge.net]

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

Modified Files:
	string_tests.py 
Log Message:
* Beef-up testing of str.__contains__() and str.find().
* Speed-up "x in y" where x has more than one character.

The existing code made excessive calls to the expensive memcmp() function.  
The new code uses memchr() to rapidly find a start point for memcmp().   
In addition to knowing that the first character is a match, the new code 
also checks that the last character is a match.  This significantly reduces
the incidence of false starts (saving memcmp() calls and making quadratic 
behavior less likely).

Improves the timings on:
    python -m timeit -r7 -s"x='a'*1000" "'ab' in x"
    python -m timeit -r7 -s"x='a'*1000" "'bc' in x"

Once this code has proven itself, then string_find_internal() should refer 
to it rather than running its own version.  Also, something similar may 
apply to unicode objects.



Index: string_tests.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/string_tests.py,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- string_tests.py	26 Oct 2004 01:52:36 -0000	1.42
+++ string_tests.py	20 Feb 2005 04:07:08 -0000	1.43
@@ -122,6 +122,30 @@
         self.checkraises(TypeError, 'hello', 'find')
         self.checkraises(TypeError, 'hello', 'find', 42)
 
+        # For a variety of combinations,
+        #    verify that str.find() matches __contains__
+        #    and that the found substring is really at that location
+        charset = ['', 'a', 'b', 'c']
+        digits = 5
+        base = len(charset)
+        teststrings = set()
+        for i in xrange(base ** digits):
+            entry = []
+            for j in xrange(digits):
+                i, m = divmod(i, base)
+                entry.append(charset[m])
+            teststrings.add(''.join(entry))
+        for i in teststrings:
+            i = self.fixtype(i)
+            for j in teststrings:
+                loc = i.find(j)
+                r1 = (loc != -1)
+                r2 = j in i
+                if r1 != r2:
+                    self.assertEqual(r1, r2)
+                if loc != -1:
+                    self.assertEqual(i[loc:loc+len(j)], j)
+
     def test_rfind(self):
         self.checkequal(9,  'abcdefghiabc', 'rfind', 'abc')
         self.checkequal(12, 'abcdefghiabc', 'rfind', '')