RFR: 8337142: StackOverflowError in Types.containsTypeRecursive with deeply nested type hierarchy

[Vicente Romero]

On Mon, 3 Nov 2025 13:04:53 GMT, Maurizio Cimadamore <mcimadamore at openjdk.org> wrote:

>> javac can crash with SOE for some deeply nested type hierarchies. See the related JBS issue for the code example. Here we have another example of infinite recursion in the compiler. This is what is happening:
>> 
>> - method Types."isSubtype"::containsTypeRecursive uses a cache, which is a Set, the elements in that cache are of type Types.TypePair. Method TypePair::equals invoke Types::isSameType
>> - Types::isSameType for this test case ends up invoking Types."isSubtype"::containsTypeRecursive, closing the infinite loop
>> 
>> The proposed solution is to define current anonymous class isSameTypeVisitor as a named class and derive from it a visitor that will be the one used by Types.TypePair and thus invoked by TypePair::equals every time instances of TypePair are added or removed from a Map, Set, etc.
>> 
>> This new visitor will compare types looking for exactness which is something desirable in a map key.
>> 
>> TIA
>
> I did some more analysis. It seems like inference completes correctly. But at the last step we end up with a very complex type (for the type variable in List::of):
> 
> 
> M<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>,? extends java.lang.Object&Nine<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>>&Six<? extends java.lang.Object&Nine<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thir
 teen>&Thirteen>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>&Thirteen&Eleven<? extends Ten<? extends Ten<?>&Thirteen>&Thirteen>>>&Six<?>>>
> 
> 
> (!!)
> 
> In the very last step of inference we have to check if this is a subtype of Object (the upper bound of the tvar). And this crashes javac, because subtyping needs to capture and capture triggers a glb involving this huge type which then consumes the stack.
> 
> Eventually this computation ends up in `containsTypeRecursive` with these two types:
> 
> 
> T = Test.Ten<? extends Test.Ten<?>&Test.Thirteen&Test.Eleven<? extends Test.Ten<? extends Test.Ten<?>&Test.Thirteen>&Test.Thirteen>>
> 
> S = Test.Ten<? extends Test.Ten<?>&Test.Thirteen>
> 
> 
> At which point we keep looping forever because, to check if we have already seen this type pair, we need to perform (as you said), a nested containment check which brings us back here. So, we never decide whether we can add the type pair to the cache or not...
> 
> So, your fix seems to be correct -- we need a simpler way to structurally compares two types w/o calling back into containment.

@mcimadamore thanks for the review!

-------------

PR Comment: https://git.openjdk.org/jdk/pull/28101#issuecomment-3486976235