I'm not at all an expert in this code, so I've tried to apply your patch by myself.
It definitely fixes related issue.

But I suggest some changes.
Moreover, I can see very similar code at adaptive_find function.
IMO, we should investigate both cases and fix them in the same PR if needed.

I'm not at all an expert in this code, so I've tried to apply your patch by myself. It definitely fixes related issue.

I have been hesitant to ping specific developers, as I don't want to annoy people or violate etiquette, but if you think it would be appropriate there are a couple of devs who have worked on this code frequently and/or recently I could tag in?

But I suggest some changes. Moreover, I can see very similar code at adaptive_find function. IMO, we should investigate both cases and fix them in the same PR if needed.

That is an excellent find, thanks! Agreed: I'll investigate, try to get a test that reproduces the issue there also, and fix it.

I've just used git blame and find some names.
I hope that's appropriate.
@serhiy-storchaka @sweeneyde

I can trigger the off-by-one reads in the adaptive algorithm easily enough, but I haven't been able to get it to cause an ASAN error as yet, so no luck so far on a test for that.

The third variant, default_rfind, already includes the equivalent guard:

            /* miss: check if previous character is part of pattern */          
            if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) {                      
                i = i - m;                                                      
            }                                                                   
            else {                                                              
                i = i - skip;                                                   
            }                                                                   
        }                                                                       
        else {                                                                  
            /* skip: check if previous character is part of pattern */          
            if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) {                      
                i = i - m;                                                      
            }                                                                   
        }                                                                       
    }                                                                           

Does default_rfind have tests on it? If not, those worth to be added too.

IMO, we can add check and tests for adaptive_find even if there is no real crash under ASan.

default_rfind does have tests, including ones that exercise the relevant code path. In fact any str.rfind with a non-matching pattern longer than one character (but shorter or equal to input length so it doesn't short-circuit) does so. adaptive_find also has tests, albeit none that trigger the code branches in question.

Looking closer at adaptive_find, on second thought I don't think the check is strictly required there. adaptive_find is only ever called directly from FASTSEARCH. For that function to use the adaptive_find algorithm the input length has to be > 2.5k length, and the pattern length has to be more than one character (actually 6+ or 100+ depending on input size). Given that, the character "one past the last possible position the pattern could start" will always be a valid character in the input string. As mentioned above, it doesn't actually matter which branch is taken, so it doesn't matter what its value is.

Presumably the extra clause in the conditional has some measurable performance impact, however slight, and given the input string minimum length requirements it will likely add up to much more than would be saved by avoiding one unnecessary character read. So, perhaps we shouldn't add it to adaptive_find, even though the current code seems safe only due to unchecked implementation details of when/under what circumstances it is called.

Nonetheless, I'll push out an update to this that adds an adaptive_find test, to ensure that code path is exercised, even though there is nothing we can check to verify it is doing what it is supposed to.

I suggest to slightly rewrite i < w condition as i + 1 <= w for default_find and maybe i > 0 as i - 1 >= 0 for default_rfind.
Moreover, some short comment at adaptive_find code itself also seems valuable.

But those are only cosmetical changes, in other aspects LGTM.

I suggest to slightly rewrite i < w condition as i + 1 <= w for default_find and maybe i > 0 as i - 1 >= 0 for default_rfind. Moreover, some short comment at adaptive_find code itself also seems valuable.

But those are only cosmetical changes, in other aspects LGTM.

Sure thing, will update, thanks!

I am not fond of tests that may trigger a crash and the comments explaining why we have them are too long IMO. I don't see why we can't find an explicit input that triggers the code paths we want (except that it may be hard to craft such input). If it's too hard, we can just.. remove the tests. Or we should indicate in the C code that tests must be updated if we change the implementation.

I'm not fond of such tests either. I was unable to craft a test case that triggers an ASAN warning, so I will gladly drop it.

Ok, just remove the ASAN guard (my bad).

OK, will remove the ASAN guard and always run the test. I agree, that seems easiest. Thanks very much for the reviews, both of you, I appreciate it!

Thanks @duaneg for the PR, and @picnixz for merging it 🌮🎉.. I'm working now to backport this PR to: 3.13.
🐍🍒⛏🤖

Thanks @duaneg for the PR, and @picnixz for merging it 🌮🎉.. I'm working now to backport this PR to: 3.14.
🐍🍒⛏🤖 I'm not a witch! I'm not a witch!

Sorry, @duaneg and @picnixz, I could not cleanly backport this to 3.13 due to a conflict.
Please backport using cherry_picker on command line.

cherry_picker 85ec3b3b503ffd5b7e45f8b3fa2cec0c10e4bef0 3.13

Can you take care of the failed backport? TiA.

GH-136628 is a backport of this pull request to the 3.14 branch.

@duaneg

IMO, it'll be better to wait few days for @duaneg's response. I also can make such backport.

With pleasure! It's just so that I can close the issue otherwise I'll likely forget about it :)

Sorry, is there anything else to do? It looks like the backport PR has now been merged (thanks!) but if there is anything more required, please let me know and I'll take care of it.

Apologies for not doing it myself immediately last night, but it was 1am local time and I've not done a (CPython) backport before, so while it all looks quite straight-forward I wanted to wait until morning when I had time and was fully awake 🙂

Yes, there is some work to be done.
You can see PR (#136628) for 3.14, which has already being merged.
OTOH, there're two CPython versions at prerelease/bugfix stages: 3.14 and 3.13 (https://devguide.python.org/versions/).
So, you should manually prepare PR for 3.13 version with cherry-picking technique.

Also, this link maybe useful: https://devguide.python.org/contrib/core-team/committing/#backporting-changes-to-an-older-version

GH-136645 is a backport of this pull request to the 3.13 branch.

GH-136648 is a backport of this pull request to the 3.13 branch.

GH-136645 is a backport of this pull request to the 3.13 branch.

This first one I made a mistake and tried to merge it into main, sorry. Hopefully the second attempt worked correctly!