Should this be?

fn into_searcher(self, haystack: &'t str) -> RegexSearcher<'r, 't> {

This lifetime setup is also used by the various Pattern impls in the standard library:
rust-lang/rust@772315d

Your version doesn't compile directly, the first suggestion below is exactly what I have implemented now (but with 't being elided) and the second suggestion is what was used before my PR and now fails to compile.

error[E0261]: use of undeclared lifetime name `'t`
  --> src/pattern.rs:16:68
   |
16 |     fn into_searcher(self, haystack: &'t str) -> RegexSearcher<'r, 't> {
   |                                                                    ^^ undeclared lifetime
   |
help: consider introducing lifetime `'t` here
   |
16 |     fn into_searcher<'t>(self, haystack: &'t str) -> RegexSearcher<'r, 't> {
   |                     ++++
help: consider introducing lifetime `'t` here
   |
13 | impl<'t, 'r> Pattern for &'r Regex {
   |      +++

I guess the problem I have here is how does the RegexSearcher connect its lifetime to the haystack? I must be missing something.

What I wrote here is equivalent to this, which is how the &str lifetime flows into the RegexSearcher lifetime (I can commit that instead if you want)

fn into_searcher<'h>(self, haystack: &'h str) -> RegexSearcher<'r, 'h>

Is that what you meant?

Ooooo, yes, I get it now. Yes, please do write that. I'm usually fine with lifetime elision, but I think it actually helps a lot here.

Right right. This all makes sense now. Got it. I was confused myself.

Perfect 😄
I've added back that explicit lifetime

Sorry, can this be 't instead of 'h to be consistent? I don't think there is a shadowing concern here.