commit 6098e97ae5c7e51d56bb832ab20ea317083762fd
author Alexander Podkhalyuzin <Alexander.Podkhalyuzin@jetbrains.com> Tue Feb 26 16:18:26 2019 +0300
committer Alexander Podkhalyuzin <Alexander.Podkhalyuzin@jetbrains.com> Wed Feb 27 12:36:43 2019 +0300
tree e5f48684f01152f988f3466b978be82865ff331e
parent c151be5547768b19bd22f65662acf36511d54d1e

Do not go to the same type twice during contains search

This fixes exponent in algorithm for scala.FunctionN.curried, where N can be up to 22.

#KT-29435 Fixed

core/descriptors/src/org/jetbrains/kotlin/types/TypeUtils.java

diff --git a/core/descriptors/src/org/jetbrains/kotlin/types/TypeUtils.java b/core/descriptors/src/org/jetbrains/kotlin/types/TypeUtils.java
index 18f0536..bcd26cc 100644
--- a/core/descriptors/src/org/jetbrains/kotlin/types/TypeUtils.java
+++ b/core/descriptors/src/org/jetbrains/kotlin/types/TypeUtils.java
@@ -385,19 +385,29 @@
             @Nullable KotlinType type,
             @NotNull Function1<UnwrappedType, Boolean> isSpecialType
     ) {
+        return contains(type, isSpecialType, new HashSet<KotlinType>());
+    }
+
+    private static boolean contains(
+            @Nullable KotlinType type,
+            @NotNull Function1<UnwrappedType, Boolean> isSpecialType,
+            HashSet<KotlinType> visited
+    ) {
         if (type == null) return false;
+        if (visited.contains(type)) return false;
+        visited.add(type);
 
         UnwrappedType unwrappedType = type.unwrap();
         if (isSpecialType.invoke(unwrappedType)) return true;
 
         FlexibleType flexibleType = unwrappedType instanceof FlexibleType ? (FlexibleType) unwrappedType : null;
         if (flexibleType != null
-            && (contains(flexibleType.getLowerBound(), isSpecialType) || contains(flexibleType.getUpperBound(), isSpecialType))) {
+            && (contains(flexibleType.getLowerBound(), isSpecialType, visited) || contains(flexibleType.getUpperBound(), isSpecialType, visited))) {
             return true;
         }
 
         if (unwrappedType instanceof DefinitelyNotNullType &&
-            contains(((DefinitelyNotNullType) unwrappedType).getOriginal(), isSpecialType)) {
+            contains(((DefinitelyNotNullType) unwrappedType).getOriginal(), isSpecialType, visited)) {
             return true;
         }
 
@@ -405,13 +415,13 @@
         if (typeConstructor instanceof IntersectionTypeConstructor) {
             IntersectionTypeConstructor intersectionTypeConstructor = (IntersectionTypeConstructor) typeConstructor;
             for (KotlinType supertype : intersectionTypeConstructor.getSupertypes()) {
-                if (contains(supertype, isSpecialType)) return true;
+                if (contains(supertype, isSpecialType, visited)) return true;
             }
             return false;
         }
 
         for (TypeProjection projection : type.getArguments()) {
-            if (!projection.isStarProjection() && contains(projection.getType(), isSpecialType)) return true;
+            if (!projection.isStarProjection() && contains(projection.getType(), isSpecialType, visited)) return true;
         }
         return false;
     }