[Runtime] Fix infinite recursion in protocol conformance checking on class Sub: Super<Sub>.
[Runtime] Fix infinite recursion in protocol conformance checking on class Sub: Super<Sub>.

Conformance checks now walk the superclass chain in two stages: stage 1 only walks superclasses that have already been instantiated. When there's a negative result and there's an uninstantiated superclass, then stage 2 will walk the uninstantiated superclasses.

The infinite recursion would occur in this scenario:

    class Super<T: P> {}
    class Sub: Super<Sub>, P {}

Instantiating the metadata for Super requires looking up the conformance for Sub: P. Conformance checking for Sub would instantiate the metadata for Super to check for a Super: P conformance.

The compiler does not allow the conformance to come from a superclass in this situation. This does not compile:

    class Super<T: P>: P {}
    class Sub: Super<Sub> {}

Therefore it's not necessary to look at Super when finding the conformance for Sub: P in this particular case. The trick is knowing when to skip Super.

We do need to instantiate Super in the general case, otherwise we can get false negatives. This was addressed in a80fe8536bdb06f0eb6e6020a7ce3cf487dc2ca9, which walks the full superclass chain during conformance checks, even if the superclass has not yet been instantiated. Unfortunately, that causes this infinite recursion.

This fix modifies that fix to make superclass instantiation conditional. The result is the ability to choose between the old algorithm (which skipped uninstantiated superclasses, albeit somewhat by accident) and the new one. A small wrapper then runs the check with the old algorithm, and then only if the old algorithm fails and there is an uninstantiated superclass, it runs with the new one.

Uninstantiated superclasses are uncommon and transient (you only run into this while metadata is in the process of being constructed) so 99.9999% of the time we'll just run the first stage and be done, and performance should remain the same as before.

rdar://80532245

glessard/swift,atrick/swift,rudkx/swift,rudkx/swift,apple/swift,roambotics/swift,JGiola/swift,apple/swift,gregomni/swift,hooman/swift,atrick/swift,hooman/swift,roambotics/swift,xwu/swift,gregomni/swift,ahoppen/swift,glessard/swift,apple/swift,xwu/swift,roambotics/swift,atrick/swift,atrick/swift,xwu/swift,ahoppen/swift,rudkx/swift,JGiola/swift,parkera/swift,ahoppen/swift,parkera/swift,hooman/swift,parkera/swift,apple/swift,roambotics/swift,benlangmuir/swift,JGiola/swift,roambotics/swift,xwu/swift,rudkx/swift,rudkx/swift,benlangmuir/swift,benlangmuir/swift,hooman/swift,glessard/swift,benlangmuir/swift,atrick/swift,parkera/swift,benlangmuir/swift,hooman/swift,parkera/swift,parkera/swift,glessard/swift,benlangmuir/swift,gregomni/swift,hooman/swift,roambotics/swift,hooman/swift,JGiola/swift,ahoppen/swift,parkera/swift,apple/swift,glessard/swift,parkera/swift,rudkx/swift,gregomni/swift,apple/swift,glessard/swift,JGiola/swift,atrick/swift,xwu/swift,ahoppen/swift,xwu/swift,ahoppen/swift,JGiola/swift,gregomni/swift,gregomni/swift,xwu/swift