Pourquoi le code suivant bloque-t-il javac? Que peut-on faire à ce sujet?

Je lisais cet article sur les “choses étranges en Java” et je suis tombé sur un concept intéressant: les types indécidables.

Considérez les trois classes / interfaces suivantes:

public interface Type { } 
 public class D

implements Type<Type<? super D<D

>>> { }

 public class WildcardTest { Type<? super D> d = new D(); } 

Apparemment, le problème est qu’il est indécidable que D soit un Type<? super D> Type<? super D> ; Quelqu’un peut-il expliquer cela davantage?

javac 1.8.0_60 génère une très longue StackOverflowError lors de la compilation de WildcardTest :

 The system is out of resources. Consult the following stack trace for details. java.lang.StackOverflowError at com.sun.tools.javac.code.Types$UnaryVisitor.visit(Types.java:4640) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3834) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3826) at com.sun.tools.javac.code.Type$ClassType.accept(Type.java:778) at com.sun.tools.javac.code.Types$UnaryVisitor.visit(Types.java:4640) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3839) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3826) at com.sun.tools.javac.code.Type$ClassType.accept(Type.java:778) at com.sun.tools.javac.code.Types$UnaryVisitor.visit(Types.java:4640) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3839) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3826) at com.sun.tools.javac.code.Type$ClassType.accept(Type.java:778) at com.sun.tools.javac.code.Types$UnaryVisitor.visit(Types.java:4640) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3839) at com.sun.tools.javac.code.Types$26.visitClassType(Types.java:3826) at com.sun.tools.javac.code.Type$ClassType.accept(Type.java:778) 

Ce code bloque également l’intégralité de l’EDI Eclipse.

L’auteur a déposé un bogue auprès de l’équipe Eclipse mais il n’a obtenu aucun vote (à part le mien). Peut-on même faire quelque chose? Est-ce simplement le problème de Halting sous forme de compilateur?

Il existe également un lien vers cet article à ce sujet dans l’article, mais j’espère qu’il existe une explication plus simple.

Comme Tunaki l’a souligné dans ses commentaires, cela remonte à un document de recherche Microsoft co-écrit par Pierce (l’auteur de TAPL). En fait, le problème Tate et al. donnez l’exemple 2 de l’annexe A (avec Byte = T , Type = N et D = C ).

Le débordement de stack

D’abord, essayons de comprendre pourquoi cela explose. Pour ce faire, il est bon de se rappeler que le compilateur vérifie les types à peu près de la même manière que nous. Les problèmes que nous rencontrons rencontrent.

 // To be determined: D <: Type> // using D

implements Type

>>> Type>>> <: Type> // The outermost type constructor (Type) matches. For the // suptyping relationship to hold, we have to test the type // arguments. (Sides are flipped due to contravariance.) D <: Type>> // Mhh… That looks an awful lot like above. // Feel free to rinse and repeat until your "stack" blows too… ;)

Pierce et al. décrivent une régression similaire à celle de l’exemple 2 de la section 3 de leur document. Il est légèrement différent car Java n’autorise pas les limites inférieures sur les variables de type, mais uniquement sur les caractères génériques.

Ce qui peut être fait?

Semblable à l’exemple 1 donné par Pierce et al., Cette régression suit un schéma. Ce motif peut être détecté par le compilateur et on peut supposer que la relation de sous-typage est valable dans l’interprétation co-inductive. (C’est le même raisonnement que pour le polymorphism lié à F, c’est-à-dire Enum> . Vous entrez une régression infinie similaire sans contradiction.)

Indécidable?

Le problème donné peut être résolu par un algorithme plus intelligent. Que le système de types de Java soit décidable ou non rest une question ouverte.

Si Java autorisait des limites inférieures pour les parameters de type, ce serait indécidable (semi-décidable). Cependant, dans leur article, Pierce et al. définir les ressortingctions avec lesquelles un tel système de types pourrait être redéfini. Soit dit en passant, ces ressortingctions ont été adoptées par Scala, qui dispose ironiquement d’un système de types complet.