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 atadaptive_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 atadaptive_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 usedgit 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;                                                                  }                                                                           }                                                                           }

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

IMO, we can add check and tests foradaptive_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 anystr.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 atadaptive_find, on second thought I don't think the check is strictly required there.adaptive_find is only ever called directly fromFASTSEARCH. For that function to use theadaptive_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 toadaptive_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 anadaptive_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 rewritei < w condition asi + 1 <= w fordefault_find and maybei > 0 asi - 1 >= 0 fordefault_rfind.
Moreover, some short comment atadaptive_find code itself also seems valuable.

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

I suggest to slightly rewritei < w condition asi + 1 <= w fordefault_find and maybei > 0 asi - 1 >= 0 fordefault_rfind. Moreover, some short comment atadaptive_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 thatmay 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 to3.13 due to a conflict.
Please backport usingcherry_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 the3.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 the3.13 branch.

GH-136648 is a backport of this pull request to the3.13 branch.

GH-136645 is a backport of this pull request to the3.13 branch.

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