Needs a release note.

This is also ready to go from my side. A review would be very helpful!

@ngoldbaum @seberg @charris A review here would be very helpful, whenever you get some free cycles.

Benchmark results:

| Change   | Before [19bfa3ff] <main>   | After [b35de314] <string-ufuncs-find-rfind>   |   Ratio | Benchmark (Parameter)                                |
|----------|----------------------------|-----------------------------------------------|---------|------------------------------------------------------|
| -        | 17.1±0.08μs                | 9.24±0.02μs                                   |    0.54 | bench_core.NumPyChar.time_find_small_list_big_string |
| -        | 5.67±0.03ms                | 15.5±0.05μs                                   |    0    | bench_core.NumPyChar.time_find_big_list_small_string |

Do we you really need to vendor that file with large changes? Any chance of vendoring it without changes?

Unfortunately, for this to play along with string_ufuncs.cpp and the templating mechanism it uses, the changes are needed. This file has been there part of the CPython source tree for a long time with very minimal changes, in case that makes you less concerned.

How should I go about fixing the test failure?

numpy._core._exceptions._UFuncNoLoopError:
    ufunc 'find' did not contain a loop with signature matching types
    (<class 'numpy.dtypes.StrDType'>,
     <class 'numpy.dtypes.StrDType'>,
     <class 'numpy.dtypes.Int64DType'>,
     <class 'numpy.dtypes.Int64DType'>) -> <class 'numpy.dtypes.Int32DType'>

Add another loop? Downcast the result? While I think I've understood a lot about how to handle input arguments dtypes and type resolving, output dtypes still confuse me a bit for some reason.

I left a comment on the last commit, should probably have been here: fcd600a#r130812759

@seberg @ngoldbaum I've reworked this PR to use the buffer approach suggested by @ngoldbaum. Unfortunately, the tests all fail with the same kind of error:

[gw1] linux -- Python 3.11.6 /opt/hostedtoolcache/Python/3.11.6/x64/bin/python

    def test_find_access_past_buffer():
        # This checks that no read past the string buffer occurs in
        # string_fastsearch.h. The READC macro is there to check this.
        # To see it in action, you can redefine READC to just read the
        # i'th character of the buffer and this test will produce an
        # 'Invalid read' if run under valgrind.
        arr = np.array([b'abcd', b'ebcd'])
>       result = np._core.umath.find(arr, b'cde', 0, np.iinfo(np.int64).max)
E       numpy._core._exceptions._UFuncNoLoopError: ufunc 'find' did not contain a loop with signature matching types (<class 'numpy.dtypes.BytesDType'>, <class 'numpy.dtypes.BytesDType'>, <class 'numpy._IntegerAbstractDType'>, <class 'numpy._IntegerAbstractDType'>) -> None

This seems completely unrelated to the change I did in the last commits and I can't reproduce it locally either on a Ubuntu machine or an M1 macbook. Any ideas what might be causing it?

@seberg @ngoldbaum This appears to be working properly now and all the fixes are in, as well as the migration to using a buffer class and a promoter rather than the old-style type resolution functions. Can you have a final look, so that we can merge this and I can start working on reworking the rest of the PRs to the new buffer solution?

Are the benchmark results still similar to #24868 (comment)?

Yeah, sorry, I forgot to post the updated benchmark results.

| Change   | Before [cdfbdf42] <main>   | After [03d737dc] <string-ufuncs-find-rfind>   |   Ratio | Benchmark (Parameter)                                |
|----------|----------------------------|-----------------------------------------------|---------|------------------------------------------------------|
| -        | 17.1±0.2μs                 | 9.45±0.3μs                                    |    0.55 | bench_core.NumPyChar.time_find_small_list_big_string |
| -        | 5.73±0.2ms                 | 17.2±0.4μs                                    |    0    | bench_core.NumPyChar.time_find_big_list_small_string |

Test failures seem to be unrelated.

Maybe we can just remove the utf-8 stuff? Or put a big comment somewhere that the utf-8 stuff was intended to be used in the near future, but is not usable yet.

Removing it is fine with me.

I'm happy to benchmark whether implicit conversions to UCS-4 arrays is faster than just plugging in the Buffer class when I do that.

Removed the UTF-8 stuff and addressed all review comments.

I'm happy to benchmark whether implicit conversions to UCS-4 arrays is faster than just plugging in the Buffer class when I do that.

Yeah, I am not too worried about it. My gut feeling is that the simplest solution for many algorithms will be to use the bytes directly (for whitespace/isalpha, etc. of course not, but those are clean single pass algorithms anyway).
For find/rfind you will have to do translate the slicing into byte-offets at the start and the result byte-offset back to character offsets when done.

Btw. I don't think it is useful enough at this point, but the code could in principle be optimized a bit for the likely case that needle is a constant: we can re-use the bloom filter from the previous iteration.

Are there any more actions points for me to take care of before we can merge this?

@lysnikolaou sorry, I don't want to fret about a few style nits, and I can't see a better path than vendoring the Python stuff (I really don't love how much code it is for something we don't do often, but...).
So I think, given that Nathan is also around to help with maintaining thing, I think we can just put it in.

There is one problem now, unfortunately. I suspect the tests will fail after merging the change to what the default integer is. My suggestion would be that you squash all current commits into one (or few) and then add a single commit to fix all NPY_LONG to NPY_DEFAULT_INT (or intp if easier), hopefully that will make any test pass?

That way, the PR isn't directly tied to any possible revert, etc. due to the intp changes.

@seberg Done.

Thanks, lets see how it goes :).