test_userstring: test_find_periodic_pattern() failed on GHA Hypothesis tests on Ubuntu

[vstinner]

GHA Hypothesis tests on Ubuntu:

FAIL: test_find_periodic_pattern (test.test_userstring.UserStringTest.test_find_periodic_pattern) (p='', text='')
Cover the special path for periodic patterns.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/runner/work/cpython/cpython-ro-srcdir/Lib/test/string_tests.py", line 341, in test_find_periodic_pattern
    self.checkequal(reference_find(p, text),
  File "/home/runner/work/cpython/cpython-ro-srcdir/Lib/test/test_userstring.py", line 24, in checkequal
    self.assertEqual(
AssertionError: -1 != 0

build: https://github.com/python/cpython/actions/runs/6365753186/job/17283009565?pr=109907

Linked PRs

• gh-110160: Fix flaky test_find_periodic_pattern in string_tests #110170
• [3.12] gh-110160: Fix flaky test_find_periodic_pattern in string_tests (GH-110170) #110182
• [3.11] gh-110160: Fix flaky test_find_periodic_pattern in string_tests (… #110183

[vstinner]

I'm not sure how Hypothesis managed to get p='' and text=''. text must always be non-empty, no?

    def test_find_periodic_pattern(self):
        """Cover the special path for periodic patterns."""
        def reference_find(p, s):
            for i in range(len(s)):
                if s.startswith(p, i):
                    return i
            return -1

        rr = random.randrange
        choices = random.choices
        for _ in range(1000):
            p0 = ''.join(choices('abcde', k=rr(10))) * rr(10, 20)
            p = p0[:len(p0) - rr(10)] # pop off some characters
            left = ''.join(choices('abcdef', k=rr(2000)))
            right = ''.join(choices('abcdef', k=rr(2000)))
            text = left + p + right
            with self.subTest(p=p, text=text):
                self.checkequal(reference_find(p, text),
                                text, 'find', p)

cc @sobolevn @hugovk

[terryjreedy]

rr = randrange(n) selects from 0 to n-1. choices(s, k=0) returns an empty list (verified on main). So I believe p0, p, left, right, and text can all be ''. ''.find('') == 0. I don't know what reference_find is but it apparently returns -1 in the same situation. If that is correct and not a bug, 1 should be added as the first parameter to one of the rr(2000) calls, depending on whether only text or also p needs to be non-empty.

[sobolevn]

Thanks for the report, @vstinner!
@terryjreedy thanks for the analysis.

First of all, this is not related to Hypothesis, this test just happens to fail in this test job.

Yes, this test is flaky by design. Here's the minimal repro that always fails:

» git patch
diff --git Lib/test/string_tests.py Lib/test/string_tests.py
index 8d210b198d2..1df4147521b 100644
--- Lib/test/string_tests.py
+++ Lib/test/string_tests.py
@@ -332,9 +332,9 @@ def reference_find(p, s):
         rr = random.randrange
         choices = random.choices
         for _ in range(1000):
-            p0 = ''.join(choices('abcde', k=rr(10))) * rr(10, 20)
-            p = p0[:len(p0) - rr(10)] # pop off some characters
-            left = ''.join(choices('abcdef', k=rr(2000)))
-            right = ''.join(choices('abcdef', k=rr(2000)))
+            p0 = ''.join(choices('abcde', k=0)) * rr(10, 20)
+            p = p0[:len(p0) - 0] # pop off some characters
+            left = ''.join(choices('abcdef', k=0))
+            right = ''.join(choices('abcdef', k=0))
             text = left + p + right
             with self.subTest(p=p, text=text):                                        

Sometimes even it fails even without right = ''.join(choices('abcdef', k=0)) change. But, with this line it is always failing.

Since randrange can return 0, it is possible to get this result. Possibly, there are other cases when this can fail.