Requirement Machine Failure?

@Slava_Pestov, you did much of the work on the Requirement Machine, correct? Are you (or anyone with comparable expertise) able to decipher what is going on here? Swift 5.8 is unable to compile source that works with Swift 5.7. The output from the compiler resembles the notation you used in your post, so it seems to have something to do with the generic signature minimization you wrote about. But I cannot tell if the compiler is finding a real problem with the source, or just confusing itself. Either way, it does not say what it was working on when it ran into trouble, so I do not know which part of the source triggered the confusion. Was it the protocol declaration itself, one of the related protocol conformances, the declaration of a generic function that uses the protocol, or a call made to such a generic function? Are you able to give any advice on how to evade the problem, preferably in a way that is source‐compatible for any clients and that does not break compatibility with Swift 5.7?

Yes, thank you for the bug report, I will take a look.

Splitting concrete equivalence classes did not reach fixed point after 2 attempts.
Last attempt produced these requirements:
conforms_to: τ_0_0 BidirectionalPattern
same_type: τ_0_0.[Pattern]Match.[PatternMatch]Searched Data
same_type: τ_0_0.[Pattern]Match.[PatternMatch]Searched.[BidirectionalPattern]Reversed.[Collection]SubSequence τ_0_0.[Pattern]Match.[PatternMatch]Searched.[BidirectionalPattern]Reversed.[Pattern]SubSequencePattern

By experimentation, I have figured out that the module can be made to build by removing the conformances to SearchableBidirectionalCollection and its inherited BidirectionalPattern from Data and several of String’s view types (which defeats the purpose). What these types appear to have in common is that SubSequence == Self and/or that Element is concrete. The other types that appear to successfully conform either have a distinct SubSequence or have conditional conformance based on a generic Element (e.g. Array where Element: Equatable).

I reduced a self-contained test case from your project and filed Incorrect generic signature minimization causes failure in concrete equivalence class splitting · Issue #64995 · apple/swift · GitHub.

Basically one weakness of the requirement machine (which was shared by the previous GenericSignatureBuilder) is that the handling of concrete types isn't too great. In your case, the root cause is the same-type requirement on the Reversed associated type in BidirectionalPattern:

associatedtype Reversed: Pattern where Reversed.Searchable == ReversedCollection<Searchable>

If you could find a way to express your protocol without this exact requirement it would fix the problem.

Keep an eye on that GitHub issue for further updates.