Challenges 20/21/22/10: "Assumption 3" is now a safety requirement of unsafe trait Pattern (rust-lang/rust#165681) #753

Summary

rust-lang#165681 (merged 2026-11-10) made Pattern an unsafe trait, with this
new requirement on into_searcher:

The returned searcher must search the provided haystack. In particular,
Searcher::haystack() must return the same string slice passed to this method.

This is the property that Assumption 3 of Challenges 20 and 21 lets solutions assume
("all the Searchers ... are created by the into_searcher(_, haystack) with haystack being a
valid UTF-8 string"). Before the change, nothing guaranteed it. Pattern was a safe trait,
so safe code could return a valid std Searcher built for a different string, and std
consumers then applied its indices to the original string. That led to UB from safe code:

• Safe custom Pattern can bind a valid Searcher to a different haystack, causing out-of-bounds reads rust-lang/rust#158265 (strip_prefix, still open but fixed by the same PR)
• Unsoundness due to user-provided Pattern impl returning an incorrect Searcher rust-lang/rust#165076 (split_once, closed by Add safety requirements for Pattern and Searcher rust-lang/rust#165681)
• Searcher's safety contract does not state the preconditions that str::split relies on rust-lang/rust#164904 (incomplete Searcher safety docs, closed by Add safety requirements for Pattern and Searcher rust-lang/rust#165681)
• String::remove_matches writes out of bounds when a Pattern returns a Searcher for a different haystack rust-lang/rust#165832 (String::remove_matches: out-of-bounds write, fixed by Add safety requirements for Pattern and Searcher rust-lang/rust#165681)

Scope: the assumption covered real UB in functions these challenges list

On nightly-2026-10-23, which is this repo's current toolchain, I checked every
str/String consumer of into_searcher(self) with a safe Pattern returning a
CharSearcher for another string. I used Kani on the real std, then confirmed each case
natively with AddressSanitizer. 17 APIs had UB:

Not affected: matches, rmatches, match_indices, rmatch_indices, find, rfind.

So, before rust-lang#165681:

• A proof of Challenges 20/21 under Assumption 3 was sound only relative to an assumption
  that safe code could break.
• Challenge 22's assumption 2 ("safety and functional correctness of all functions in
  pattern.rs") and Challenge 10's remove_matches relied on it implicitly.

After rust-lang#165681 the assumption is part of Pattern's safety contract, which is the right
place for it.

Suggested changes

1. Challenge text (20, 21; maybe 22 and 10). Replace Assumption 3 with a reference to
   Pattern's safety requirement (into_searcher returns a searcher for the given
   haystack). Challenge 22's assumption 2 and Challenge 10's remove_matches entry could
   say explicitly that they depend on it.
2. Toolchain bump. The repo is pinned to nightly-2026-10-23, which is before Add safety requirements for Pattern and Searcher rust-lang/rust#165681.
   After a bump past 2026-11-10, impl Pattern for … in harnesses fails with E0200 and
   needs unsafe impl. Open PRs that define a safe Pattern impl:
   • Challenge 10: Verify memory safety of String functions (Challenge 10) #558, Challenge 10: Verify memory safety of String functions with Kani #702, Challenge 10: Verify String safety with Kani #725
   • Challenge 22: Challenge 22: Verify safety of str iter with Kani #741
3. Harness modelling. A model Pattern must now uphold the into_searcher
   guarantee (haystack() is the passed slice). The PRs above already bind the searcher
   to the passed haystack, so this only needs to be stated as the reason the model is valid.

Proposed solutions for the affected challenges

Challenge 20 (#277): char Searchers in str::pattern

• Verify safety of char-related Searcher methods (Challenge 20) #537 (open, jrey8343): Verify safety of char-related Searcher methods
• Challenge 20: Verify Char Searcher with Kani #620 (open, v3risec): Verify Char Searcher with Kani
• Challenge 20: Verify char-class Searcher safety in str::pattern with Kani #722 (open, kasimte): Verify char-class Searcher safety in str::pattern with Kani
• Challenge 20: Unbounded proofs for the char Searchers of str::pattern #740 (open, hung1962003): Unbounded proofs for the char Searchers of str::pattern

Challenge 21 (#278): StrSearcher in str::pattern

• Verify safety of StrSearcher (Challenge 21) #538 (open, jrey8343): Verify safety of StrSearcher
• Challenge 21: Verify safety of StrSearcher with Kani #621 (open, v3risec): Verify safety of StrSearcher with Kani
• Challenge 21 (partial): bounded Kani PROBE of shipped TwoWaySearcher::next_back short-period arms #664 (open, ivmat): partial, bounded Kani probe of TwoWaySearcher::next_back short-period arms
• Challenge 21: Verify StrSearcher safety in str::pattern with Kani #721 (open, kasimte): Verify StrSearcher safety in str::pattern with Kani

Challenge 22 (#279): str iter functions

• Verify safety of str iter functions (Challenge 22) #539 (closed, jrey8343), Verify safety of str iter functions (Challenge 22) #557 (open, jrey8343): Verify safety of str iter functions
• Challenge 22: Verify safety of str iter functions #572 (closed, Samuelsills): Verify safety of str iter functions
• Challenge 22: Kani contracts for str iterators #646 (closed, sankalpsthakur): Kani contracts for str iterators
• Challenge 22: Verify the safety of str iter functions #706 (open, kasimte): Verify the safety of str iter functions
• Challenge 22: Verify safety of str iter with Kani #741 (open, v3risec): Verify safety of str iter with Kani (safe impl Pattern)

Challenge 10 (#61): String (covers remove_matches)

• Verify memory safety of String functions (Challenge 10) #541 (closed, jrey8343), Verify memory safety of String functions (Challenge 10) #558 (open, jrey8343): Verify memory safety of String functions (safe impl Pattern)
• Challenge 10: Verify memory safety of String functions #571 (closed, Samuelsills): Verify memory safety of String functions
• Challenge 10: Kani contracts for String memory safety #645 (closed, sankalpsthakur): Kani contracts for String memory safety
• Challenge 10: Verify memory safety of String functions with Kani #702 (open, Talha-Dmr): Verify memory safety of String functions with Kani (safe impl Pattern)
• Challenge 10: Verify String safety with Kani #725 (open, v3risec): Verify String safety with Kani (safe impl Pattern)

Reproducer (pre-rust-lang#165681 toolchain)

#![feature(pattern, string_remove_matches)]
#![forbid(unsafe_code)]
use std::str::pattern::{CharSearcher, Pattern};

struct WrongHaystack;
impl Pattern for WrongHaystack {
    type Searcher<'a> = CharSearcher<'a>;
    fn into_searcher(self, _haystack: &str) -> CharSearcher<'_> {
        'X'.into_searcher("aaaaaXaX")
    }
}

fn main() {
    let mut s = String::from("a");
    s.remove_matches(WrongHaystack); // nightly-2026-10-23: len = usize::MAX, capacity = 1, heap corruption
}

On nightly-2026-11-11 (9c5648833) this no longer compiles:
error[E0200]: the trait Pattern requires an unsafe impl declaration.