As you are probably well aware, a conformance is abstractly a function that takes a type and returns a set of witnesses. If we want to be able to make these witness choice decisions deterministically, then we need to somehow incorporate the relevant conditional conformances into the inputs to that conformance function. Today, in a conformance like your example struct X<T, U>: P, the only input to the conformance is the conforming type X<T, U>, which by itself carries no conformance information about T or U, so in the most general case, there's too little information to see the conditional conformances without doing global lookup (and thereby introducing nondeterminism due to the shared mutable nature of the global conformance set). If we had a mechanism for making the relevant conditional conformances be direct inputs to the conformance, that could provide a way out of the problem. One way to do this might be to have a formal concept of optional generic constraints; these could work by telling the type system to grab a protocol conformance for the constraint if it has it, or pass null otherwise. That would let you declare your type as (stealing ?Protocol syntax from Rust as a strawman):
struct X<T: ?Equatable, U: ?CustomStringConvertible> { ... }
That would let us know that, any time we instantiate X, we capture the conditional conformances for the generic arguments when we have them. Instantiations would notionally lower like this:
let xis = X<Int, String>.self // swift_getGenericMetadata(X, Int, String, `Int: Equatable`, `String: CustomStringConvertible`)
struct Foo {}
struct Bar {}
let xfb = X<Foo, Bar>.self // swift_getGenericMetadata(X, Foo, Bar, nullptr, nullptr)
We would probably also want to raise errors or warnings for non-concrete generic arguments that don't forward the optional requirements, to ensure that the information gets plumbed through:
func lossyGeneric<A, B>() -> X<A, B> // error: instantiation of X<A, B> loses optional requirements on T = A and U = B
func losslessGeneric<T: ?Equatable, U: ?CustomStringConvertible>() -> X<T, U> // ok
With the optional requirements captured into the metadata, then checks whether T conforms to Equatable, or U conforms to CustomStringConvertible, can be answered using local data, and unlike as? Protocol checks today, these local state checks can be made to behave deterministically, and reliably specialized away when we monomorphize. That would also enable your example case of choosing a P.foo witness based on the conformances of T and U to be done deterministically.
OTOH, if we treat optional requirements the way we do requirements today, that would mean new optional requirements can't be added retroactively to types, and couldn't even be added by the API author without breaking ABI, which wouldn't be very expressive. I can however see us having more flexibility with optional constraints in protocols. A protocol could use optional constraints to capture conditional conformance information into its conforming types, which would be appropriate for capability towers like *Collection, where it is common to want to deterministically query the higher capabilities of a collection. If the protocol were declared:
protocol Collection: ?BidirectionalCollection, ?RandomAccessCollection /*etc.*/ { ... }
that would direct the compiler to capture the BidirectionalCollection and RandomAccessCollection conformances for a type when available, and make them available for deterministic capability checking on any type that conforms to Collection. The situation for extension, both proactively and retroactively, is a bit more promising too. Protocols can already add new requirements resiliently, so if the standard library expands the Collection hierarchy, it can also extend Collection with optional constraints to capture the extended hierarchy. The story for retroactive expansion is a bit sadder within the confines of the language today, but if we had the ability to extend protocols with new dispatched requirements, that could also conceivably be used to introduce new optional requirements, and give a third party library the ability to expand the Collection hierarchy as well.
.