Comment nous à IntelliJ IDEA recherchons les expressions lambda

Une caractéristique importante de tout IDE est la recherche et la navigation dans le code. L'une des options de recherche Java fréquemment utilisées consiste à rechercher toutes les implémentations de cette interface. Souvent, une telle fonction est appelée une hiérarchie de types et ressemble à l'image de droite.

Itérer à travers toutes les classes d'un projet lors de l'appel de cette fonction est inefficace. Vous pouvez enregistrer la hiérarchie de classe complète dans l'index au moment de la compilation, car le compilateur la construit quand même. Nous le faisons si la compilation est lancée par l'IDE lui-même et non déléguée, par exemple, dans Gradle. Mais cela ne fonctionne que si rien n'a changé dans le module après la compilation. Mais dans le cas général, les codes source sont la source d'information la plus pertinente et les index sont construits sur des codes source.

Trouver des héritiers immédiats est une tâche simple si nous n'avons pas affaire à une interface fonctionnelle. Lorsque vous recherchez des implémentations de l'interface Foo , vous devez trouver toutes les classes où il y a des implements Foo , et les interfaces où il y a des extends Foo , ainsi que des classes anonymes de la forme new Foo(...) {...} . Pour ce faire, il suffit de construire à l'avance l'arborescence syntaxique de chaque fichier projet, de trouver les constructions correspondantes et de les ajouter à l'index.

Bien sûr, il y a une légère subtilité ici: vous recherchez peut-être l'interface org.example.evilcompany.Foo , mais quelque part org.example.evilcompany.Foo est réellement utilisé. Est-il possible de pré-mettre le nom complet de l'interface parent dans l'index? Il y a des difficultés avec cela. Par exemple, le fichier dans lequel l'interface est utilisée peut ressembler à ceci:

 // MyFoo.java import org.example.foo.*; import org.example.bar.*; import org.example.evilcompany.*; class MyFoo implements Foo {...} 

En ne regardant que le fichier, nous ne pouvons pas comprendre quel est le vrai nom complet Foo . Vous devez regarder le contenu de plusieurs packages. Et chaque paquet peut être défini à plusieurs endroits (par exemple, dans plusieurs fichiers jar). L'indexation prendra du temps si, lors de l'analyse de ce fichier, nous devons faire une résolution complète du caractère. Mais le problème principal n'est même pas cela, mais le fait que l'index construit sur le fichier MyFoo.java dépendra non seulement de lui, mais aussi d'autres fichiers. Après tout, nous pouvons transférer la description de l'interface Foo , par exemple, du package org.example.foo package org.example.bar , et ne rien changer dans le fichier MyFoo.java , et le nom complet de Foo changera.

Les index dans IntelliJ IDEA dépendent uniquement du contenu d'un seul fichier. D'une part, c'est très pratique: l'index relatif à un fichier particulier devient invalide lorsque ce fichier change. En revanche, cela impose de grandes restrictions sur ce qui peut être placé dans l'index. Par exemple, il ne peut pas stocker de manière fiable les noms complets des classes parentes dans l'index. Mais, en principe, ce n'est pas si effrayant. Lorsque vous interrogez la hiérarchie de types, nous pouvons trouver tout ce qui convient au nom court, puis pour ces fichiers, effectuez une résolution honnête du caractère et déterminez si cela nous convient vraiment. Dans la plupart des cas, il n'y aura pas trop de caractères supplémentaires et une telle vérification sera assez rapide.

La situation change radicalement lorsque la classe dont nous recherchons les descendants est une interface fonctionnelle. Ensuite, en plus des héritiers explicites et anonymes, nous obtenons des expressions lambda et des liens de méthode. Que mettre maintenant dans un index et que calculer directement lors de la recherche?

Supposons que nous ayons une interface fonctionnelle:

 @FunctionalInterface public interface StringConsumer { void consume(String s); } 

Il existe différentes expressions lambda dans le code. Par exemple:

 () -> {} //   :   (a, b) -> a + b //   :   s -> { return list.add(s); //   :   } s -> list.add(s); //    

Autrement dit, nous ne pouvons filtrer rapidement que les lambdas qui ont le mauvais nombre de paramètres ou évidemment le mauvais type de retour, par exemple void contre non-void. Il est généralement impossible de déterminer plus précisément le type de retour. Dites, dans lambda s -> list.add(s) pour cela, vous devez résoudre la list caractères et add , et, éventuellement, démarrer une procédure d'inférence de type à part entière. Tout cela est long et nécessitera une fixation sur le contenu des autres fichiers.

Nous avons de la chance si notre interface fonctionnelle prend cinq arguments. Mais s'il ne prend qu'un seul argument, un tel filtre laissera un grand nombre de lambdas supplémentaires. Encore pire avec les références de méthode. En principe, l'apparition de toute référence à une méthode ne peut en aucun cas être dite qu'elle soit appropriée ou non.

Peut-être devriez-vous regarder autour de la lambda pour comprendre quelque chose? Oui, parfois ça marche. Par exemple:

 //        Predicate<String> p = s -> list.add(s); //      IntPredicate getPredicate() { return s -> list.add(s); } //      SomeType fn; fn = s -> list.add(s); //     foo((SomeFunctionalType)(s -> list.add(s))); //     Foo[] myLambdas = {s -> list.add(s), s -> list.remove(s)}; 

Dans tous ces cas, le nom court de l'interface fonctionnelle correspondante peut être trouvé dans le fichier actuel et placé dans l'index à côté de l'expression fonctionnelle, que ce soit un lambda ou une référence de méthode. Malheureusement, dans les projets réels, ces cas couvrent une très petite fraction de tous les lambdas. Dans la grande majorité des cas, lambda est utilisé comme argument d'une méthode:

 list.stream() .filter(s -> StringUtil.isNonEmpty(s)) .map(s -> s.trim()) .forEach(s -> list.add(s)); 

Lequel de ces trois lambdas peut être de type StringConsumer ? Il est clair pour le programmeur qu'aucun. Parce qu'il est évident que nous avons ici la chaîne Stream API, et qu'il n'y a que des interfaces fonctionnelles de la bibliothèque standard, notre type ne peut pas être là.

Cependant, l'IDE ne doit pas se laisser tromper, il doit donner une réponse précise. Que faire si la list n'est pas du tout java.util.List et que list.stream() ne renvoie pas du tout java.util.stream.Stream ? Pour ce faire, vous devez résoudre le symbole de list , ce qui, comme nous le savons, ne peut pas être effectué de manière fiable uniquement sur la base du contenu du fichier actuel. Et même si nous l'avons installé, la recherche ne doit pas porter sur l'implémentation de la bibliothèque standard. Peut-être que nous avons spécifiquement remplacé dans ce projet la classe java.util.List par la nôtre? La recherche doit y répondre. Eh bien, bien sûr, les lambdas sont utilisés non seulement dans les flux standard, il existe de nombreuses autres méthodes où ils sont transférés.

En conséquence, il s'avère que nous pouvons interroger l'index pour une liste de tous les fichiers Java qui utilisent des lambdas avec le nombre de paramètres requis et un type de retour valide (en fait, nous ne suivons que quatre options: void, non void, boolean et any). Et puis quoi? Pour chacun de ces fichiers, créez une arborescence PSI complète (est-ce comme une arborescence d'analyse, mais avec une résolution de caractères, une inférence de type et d'autres éléments intelligents) et exécutez honnêtement l'inférence de type pour lambda? Ensuite, dans un grand projet, vous n'attendrez pas la liste de toutes les implémentations d'interface, même s'il n'y en a que deux.

Il s'avère que nous devons effectuer les étapes suivantes:

• Demandez l'index (pas cher)
• Construire un PSI (cher)
• Imprimer le type lambda (très cher)

Dans Java version 8 et versions ultérieures, l'inférence de type est une opération incroyablement coûteuse. Dans une chaîne d'appels complexe, vous pouvez avoir de nombreux paramètres génériques génériques, dont les valeurs doivent être déterminées à l'aide de la procédure furieuse décrite au chapitre 18 de la spécification. Cela peut être fait en arrière-plan pour le fichier en cours de modification, mais il sera difficile de le faire pour des milliers de fichiers non ouverts.

Ici, cependant, vous pouvez couper un peu le coin: dans la plupart des cas, nous n'avons pas besoin du type final. Si seulement lambda n'est pas passé à une méthode qui prend un paramètre générique à cet endroit, nous pouvons nous débarrasser de la dernière étape de substitution de paramètre. Disons, si nous avons déduit le type lambda java.util.function.Function<T, R> , nous ne pouvons pas calculer les valeurs des paramètres de substitution T et R : et il est donc clair de le renvoyer ou non au résultat de la recherche. Bien que cela ne fonctionne pas lors de l'appel d'une méthode comme celle-ci:

 static <T> void doSmth(Class<T> aClass, T value) {} 

Cette méthode peut être appelée comme ceci: doSmth(Runnable.class, () -> {}) . Ensuite, le type lambda sera affiché comme T , et vous devrez quand même le remplacer. Mais c'est un cas rare. Par conséquent, il s'avère économiser, mais pas plus de 10%. Le problème n'est pas fondamentalement résolu.

Autre idée: si l'inférence de type exacte est complexe, faisons une conclusion approximative. Laissez-le fonctionner uniquement sur les types de classes effacés et ne réduisez pas l'ensemble des restrictions, comme écrit dans la spécification, mais suivez simplement la chaîne d'appels. Tant que le type effacé n'inclut pas de paramètres génériques, alors tout va bien. Par exemple, prenez le flux de l'exemple ci-dessus et déterminez si le dernier lambda implémente notre StringConsumer :

• list variable -> tapez java.util.List
• List.stream() - List.stream() type java.util.stream.Stream
• Stream.filter(...) → tapez java.util.stream.Stream , nous ne regardons même pas les arguments du filter , quelle est la différence
• Stream.map(...) - Stream.map(...) type java.util.stream.Stream , de manière similaire
• La Stream.forEach(...) → il existe une telle méthode, son paramètre est du type Consumer , qui n'est évidemment pas StringConsumer .

Eh bien, ils l'ont fait sans inférence de type complet. Avec une approche aussi simple, cependant, il est facile d'exécuter des méthodes surchargées. Si nous ne démarrons pas complètement l'inférence de type, vous ne pouvez pas sélectionner la bonne version surchargée. Bien que non, il est parfois possible que le nombre de paramètres de méthode diffère. Par exemple:

 CompletableFuture.supplyAsync(Foo::bar, myExecutor).thenRunAsync(s -> list.add(s)); 

Ici, nous pouvons facilement comprendre que

• Il existe deux méthodes CompletableFuture.supplyAsync , mais l'une prend un argument et la seconde en prend deux, alors choisissez celle qui en prend deux. Il renvoie un CompletableFuture .
• thenRunAsync méthodes thenRunAsync également deux, et parmi elles, vous pouvez également choisir celle qui prend un argument. Le paramètre correspondant est de type Runnable , ce qui signifie qu'il n'est pas StringConsumer .

Si plusieurs méthodes acceptent le même nombre de paramètres, ou si certaines ont un nombre variable de paramètres et semblent également appropriées, vous devrez garder une trace de toutes les options. Mais souvent, cela n'est pas non plus effrayant. Par exemple:

 new StringBuilder().append(foo).append(bar).chars().forEach(s -> list.add(s)); 

• new StringBuilder() crée évidemment java.lang.StringBuilder . Pour les concepteurs, nous autorisons toujours le lien, mais l'inférence de type complexe n'est pas requise ici. Même s'il y avait de new Foo<>(x, y, z) , nous n'affichons pas les valeurs des paramètres typiques, nous ne sommes intéressés que par Foo .
• Il existe de StringBuilder.append méthodes StringBuilder.append qui prennent un argument, mais elles renvoient toutes le type java.lang.StringBuilder , donc peu importe le type foo et bar .
• La méthode StringBuilder.chars une et renvoie java.util.stream.IntStream .
• La méthode IntStream.forEach une et accepte le type IntConsumer .

Même si plusieurs options restent quelque part, vous pouvez toutes les suivre. Par exemple, le type de lambda passé à ForkJoinPool.getInstance().submit(...) peut être Runnable ou Callable , mais si nous cherchons quelque chose de troisième, nous pouvons toujours ignorer ce lambda.

Une situation désagréable se produit lorsqu'une méthode renvoie un paramètre générique. Ensuite, la procédure échoue et vous devez exécuter l'inférence de type complet. Cependant, nous avons soutenu un cas. Il apparaît bien dans ma bibliothèque StreamEx, qui a une classe abstraite AbstractStreamEx<T, S extends AbstractStreamEx<T, S>> contenant des méthodes comme le S filter(Predicate<? super T> predicate) . Habituellement, les gens travaillent avec une classe spécifique StreamEx<T> extends AbstractStreamEx<T, StreamEx<T>> . Dans ce cas, vous pouvez effectuer la substitution du paramètre type et découvrir que S = StreamEx .

Eh bien, dans de nombreux cas, nous nous sommes débarrassés d'une inférence de type très coûteuse. Mais nous n'avons rien fait avec la construction du PSI. C'est une honte d'analyser un fichier en cinq cents lignes juste pour découvrir que le lambda de la ligne 480 ne correspond pas à notre requête. Revenons à notre flux:

 list.stream() .filter(s -> StringUtil.isNonEmpty(s)) .map(s -> s.trim()) .forEach(s -> list.add(s)); 

Si la list est une variable locale, un paramètre de méthode ou un champ dans la classe actuelle, alors déjà au stade de l'indexation, nous pouvons trouver sa déclaration et établir que le nom court du type est
List En conséquence, dans l'indice de la dernière lambda, nous pouvons mettre les informations suivantes:

Le type de ce lambda est le type de paramètre de la méthode forEach partir d'un argument, appelé sur le résultat de la méthode map partir d'un argument, appelé sur le résultat de la méthode filter partir d'un argument, appelé sur le résultat de la méthode stream partir de zéro arguments, appelé sur un objet de type List .

Toutes ces informations sont disponibles sur le fichier courant, ce qui signifie qu'elles peuvent être placées dans l'index. Pendant la recherche, nous demandons à l'index de telles informations sur tous les lambdas et essayons de restaurer le type lambda sans construire de PSI. Vous devez d'abord effectuer une recherche globale de classes avec la List noms List . Bien sûr, nous trouverons non seulement java.util.List , mais aussi java.awt.List ou quelque chose du code du projet utilisateur. De plus, nous soumettrons toutes ces classes à la même procédure de résolution de type inexacte que nous avons utilisée auparavant. Souvent, les classes supplémentaires elles-mêmes sont rapidement éliminées. Par exemple, dans java.awt.List il n'y a pas de méthode de stream , elle est donc exclue davantage. Mais même si quelque chose de superflu est avec nous jusqu'à la fin et que nous trouvons plusieurs candidats pour le type de notre lambda, il y a de bonnes chances qu'ils ne correspondent pas tous à la requête de recherche, et nous éviterons toujours de construire un PSI complet.

Il est possible que la recherche globale soit trop coûteuse (il existe de nombreuses classes List dans le projet), soit le début de la chaîne n'est pas autorisé dans le contexte d'un seul fichier (par exemple, c'est le champ de la classe parente), soit la chaîne sera interrompue quelque part car la méthode renvoie un paramètre générique. Ensuite, nous n'abandonnons pas tout de suite et essayons à nouveau de commencer par une recherche globale sur la prochaine méthode de chaînage. Par exemple, pour la map.get(key).updateAndGet(a -> a * 2) , l'instruction suivante est entrée dans l'index:

Le type de lambda est le type du seul paramètre de la méthode updateAndGet , appelé sur le résultat de la méthode get avec un paramètre, appelé sur l'objet de type Map .

Soyons chanceux et dans le projet il n'y a qu'un seul type de Map - java.util.Map . Il a une méthode get(Object) , mais malheureusement il retourne le paramètre générique V Ensuite, nous updateAndGet la chaîne et recherchons globalement la méthode updateAndGet avec un paramètre (en utilisant l'index, bien sûr). AtomicInteger , il n'y a que trois de ces méthodes dans le projet, dans les AtomicInteger , AtomicLong et AtomicReference avec des paramètres de type IntUnaryOperator , LongUnaryOperator et UnaryOperator , respectivement. Si nous recherchons un autre type, nous avons découvert que cette lambda ne convient pas et que le PSI ne peut pas être construit.

Étonnamment, il s'agit d'un exemple frappant d'une fonctionnalité qui, au fil du temps, commence elle-même à fonctionner plus lentement. Par exemple, vous recherchez l'implémentation d'une interface fonctionnelle, il n'y en a que trois dans le projet, et IntelliJ IDEA les recherche pendant dix secondes. Et vous vous souvenez très bien qu'il y a trois ans, il y en avait aussi trois, vous les cherchiez aussi, mais ensuite l'environnement a répondu en deux secondes sur la même machine. Et votre projet, bien qu'énorme, a progressé en trois ans, peut-être de 5%. Bien sûr, vous commencez à ressentir à juste titre ce que ces développeurs ont raté avec le fait que l'IDE a commencé à ralentir si terriblement. Mains pour arracher ces malheureux programmeurs.

Et peut-être que nous n'avons rien changé du tout. Peut-être que la recherche fonctionne de la même manière qu'il y a trois ans. Il y a tout juste trois ans, vous veniez de passer à Java 8 et vous aviez, disons, une centaine de lambdas dans votre projet. Et maintenant, vos collègues ont transformé des classes anonymes en lambdas, ont commencé à utiliser activement des flux ou ont connecté une sorte de bibliothèque réactive, à la suite des lambdas, ils sont devenus non pas cent, mais dix mille. Et maintenant, pour creuser les trois lambdas nécessaires, l'IDE doit être fouillé cent fois plus.

J'ai dit «peut-être» parce que, bien sûr, nous revenons à cette recherche de temps en temps et essayons de l'accélérer. Mais ici, vous devez ramer même pas contre le ruisseau, mais vers le haut de la cascade. Nous essayons, mais le nombre de lambdas dans les projets augmente très rapidement.