Came, saw, generalized: we plunge into Java Generics

Java Generics is one of the most significant changes in the history of the Java language. Generics, available with Java 5, have made using the Java Collection Framework simpler, more convenient, and safer. Errors related to incorrect use of types are now detected at compile time. And the Java language itself has become even safer. Despite the seeming simplicity of generic types, many developers have difficulty using them. In this post I will talk about the features of working with Java Generics, so that you have fewer difficulties. It is useful if you are not a guru in generics, and will help to avoid many difficulties when immersing in a topic.

Work with collections

Suppose a bank needs to calculate the amount of savings in customer accounts. Before the advent of “generics”, the sum calculation method looked like this:

publiclonggetSum(List accounts){
   long sum = 0;
   for (int i = 0, n = accounts.size(); i < n; i++) {
       Object account = accounts.get(i);
       if (account instanceof Account) {
           sum += ((Account) account).getAmount();
       }
   }
   return sum;
}

We iterated, ran through the list of accounts and checked whether the item from this list was really an instance of the class Account— that is, the user's account. The type of our class object Accountand the method getAmountthat returned the amount on this account were cast . Then it all summarized and returned the total amount. Two steps were required:

if (account instanceof Account) { // (1)

sum += ((Account) account).getAmount(); // (2)

If you do not check ( instanceof) for belonging to a class Account, then at the second stage it is possible ClassCastException- that is, the program crashes. Therefore, such a check was mandatory.

With the advent of Generics, the need to check and type casting disappeared:

publiclonggetSum2(List<Account> accounts){
   long sum = 0;
   for (Account account : accounts) {
       sum += account.getAmount();
   }
   return sum;
}

Now the method

getSum2(List<Account> accounts)

takes as arguments only a list of class objects Account. This limitation is indicated in the method itself, in its signature, the programmer simply cannot transfer any other list — only the list of client accounts.

We do not need to check the type of elements from this list: it is implied by the type description of the method parameter

List<Account> accounts

(you can read how список объектов класса Account). And the compiler will give an error if something goes wrong - that is, if someone tries to transfer to this method a list of objects other than a class Account.

In the second line of the test, the necessity also disappeared. If required, type conversion ( casting) will be done at compile time.

Substitution principle

Barbara Liskov's substitution principle is a specific definition of a subtype in object-oriented programming. Liskov's idea of ​​a “subtype” defines the concept of substitution: if it Sis a subtype T, then type objects Tin a program can be replaced with type objects Swithout any changes to the desired properties of this program.

Type of	Subtype
Number	Integer
List <E>	ArrayList <E>
Collection <E>	List <E>
Iterable <E>	Collection <E>

Type / Subtype Relations Examples The

following is an example of using the substitution principle in Java:

Number n = Integer.valueOf(42);
List<Number> aList = new ArrayList<>();
Collection<Number> aCollection = aList;
Iterable<Number> iterable = aCollection;

Integeris a subtype Number; therefore, you can assign a value to a ntype variable Numberthat the method returns Integer.valueOf(42).

Covariance, contravariance and invariance

First, a little theory. Covariance is the preservation of the inheritance hierarchy of source types in derived types in the same order. For example, if Cat is a subtype of Animals , then Set <Cats> is a subtype of Set <Animals> . Therefore, taking into account the substitution principle, one can perform the following assignment:

Set <Animals> = Set <Cats>

Contravariance is the inversion of the hierarchy of the original types to the opposite in derived types. For example, if the Cat is a subtype Животные, then the Set <Animals> is a subtype of Set <Cat> . Therefore, taking into account the principle of substitution, you can perform this assignment:

Set <Cats> = Set <Animals>

Invariance - no inheritance between derived types. If the Cat is a subtype of Animals , then the Set <Cats> is not a subtype of the Set <Animals> and the Set <Animals> is not a subtype of the Set <Cats> .

Java arrays are covariant . A type S[]is a subtype T[], if Sis a subtype T. Assignment Example:

String[] strings = new String[] {"a", "b", "c"};
Object[] arr = strings;

We have assigned a reference to an array of strings of a variable arrwhose type is - «массив объектов». If the arrays were not covariant, we would not be able to do this. Java allows you to do this, the program will compile and run without errors.

arr[0] = 42; // ArrayStoreException. Проблема обнаружилась на этапе выполнения программы

But if we try to change the contents of the array through a variable arrand write the number 42 there, we will get ArrayStoreExceptionat the program execution stage, since 42 is not a string, but a number. This is a disadvantage of the covariance of Java arrays: we cannot perform checks at the compilation stage, and something can break already in runtime.

"Generics" are invariant. Let's give an example:

List<Integer> ints = Arrays.asList(1,2,3);
List<Number> nums = ints; // compile-time error. Проблема обнаружилась на этапе компиляции
nums.set(2, 3.14);
assert ints.toString().equals("[1, 2, 3.14]");

If you take a list of integers, then it will not be a subtype of the type Number, nor any other subtype. He is only a subtype of himself. That is List <Integer>- this is List<Integer>nothing more. The compiler will make sure that a variable intsdeclared as a list of objects of the class Integer contains only objects of the class Integerand nothing but them. At the compilation stage, a check is performed, and nothing will fall in our runtime.

Wildcards

Are Generics Invariants Always? Not. I will give examples:

List<Integer> ints = new ArrayList<Integer>();
List<? extends Number> nums = ints;

This is covariance. List<Integer>- subtypeList<? extends Number>

List<Number> nums = new ArrayList<Number>();
List<? super Integer> ints = nums;

This contravariant. List<Number>is a subtype List<? super Integer>.

The view entry is "? extends ..."either "? super ..."called a wildcard or wildcard, with an upper bound ( extends) or lower bound ( super). List<? extends Number>may contain objects whose class is Numberor is inherited from Number. List<? super Number>may contain objects whose class Numberor for which Numberis an heir (supertype from Number).

extends B - wildcard character specifying the upper boundary super B - wildcard character specifying the lower limit wherein B - is the boundary recording form T 2 <= T 1 means that a set of types described T 2 is a subset of the types described T 1 te . Number <=? extends Object ? extends Number <=? extends Object and ? super Object <=? super number

A more mathematical interpretation of the topic.

A couple of tasks for testing knowledge:

1. Why in the example below is a file-time error? What value can be added to the list nums?

List<Integer> ints = new ArrayList<Integer>();
ints.add(1);
ints.add(2);
List<? extends Number> nums = ints;
nums.add(3.14); // compile-time error

2. Why can't I get an item from the list below?

publicstatic <T> T getFirst(List<? super T> list){
   return list.get(0); // compile-time error
}

The Get and Put Principle or PECS (Producer Extends Consumer Super)

The wildcard feature with the upper and lower bound provides additional features associated with the safe use of types. From one type of variables you can only read, in the other - just enter it (the exception is the ability to write nullfor extendsand read Objectfor super). To make it easier to remember which wildcard to use, there is the principle of PECS - Producer Extends Consumer Super.

• If we declared a wildcard with extends , then it is producer . It only "produces", provides an element from the container, but does not accept anything.
  
• If we declared a wildcard with super - then this is a consumer . He only accepts, but can not provide anything.
  

Consider using Wildcard and the PECS principle using the example of the copy method in the java.util.Collections class.

publicstatic <T> voidcopy(List<? super T> dest, List<? extends T> src){
…
}

The method copies the elements from the source list srcto the list dest. src- announced with a wildcard ? extendsand is a producer, and dest- declared with a wildcard ? superand is a consumer. Given the wildcard covariance and contravariance, you can copy items from the list intsto the list nums:

List<Number> nums = Arrays.<Number>asList(4.1F, 0.2F);
List<Integer> ints = Arrays.asList(1,2);
Collections.copy(nums, ints);

If we mistakenly mistake the parameters of the copy method and try to copy from list numsto list ints, the compiler will not allow us to do it:

Collections.copy(ints, nums); // Compile-time error

<?> and raw types

Below is a wildcard with an unlimited wildcard. We just put <?>, without keywords superor extends:

staticvoidprintCollection(Collection<?> c){
   // a wildcard collection
   for (Object o : c) {
       System.out.println(o);
   }
}

In fact, such an “unlimited” wildcard is still limited, from above. Collection<?> Is also a wildcard character, just like " ? extends Object". A record of a form is Collection<?>equivalent Collection<? extends Object> , which means that a collection can contain objects of any class, since all classes in Java are inherited from Object— so the substitution is called unbounded.

If we omit the type indication, for example, like this:

ArrayList arrayList = new ArrayList();

then, it is said that ArrayList- this is the Rawtype of the parameterized ArrayList <T> . Using Raw types, we return to the pre-generic era and consciously discard all the features inherent in parametrized types.

If we try to call a parameterized method on the Raw type, the compiler will give us a warning "Unchecked call". If we try to assign the reference to the parameterized Raw type to the type, the compiler will generate the warning “Unchecked assignment”. Ignoring these warnings, as we will see later, can lead to errors during the execution of our application.

ArrayList<String> strings = new ArrayList<>();
ArrayList arrayList = new ArrayList();
arrayList = strings; // Ok
strings = arrayList; // Unchecked assignment
arrayList.add(1); //unchecked call

Wildcard capture

Let us now try to implement a method that permutes the elements of the list in the reverse order.

publicstaticvoidreverse(List<?> list);
// Ошибка!publicstaticvoidreverse(List<?> list){
  List<Object> tmp = new ArrayList<Object>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1)); // compile-time error
  }
}

A compilation error occurred because the method reverse takes as an argument a list with an unlimited wildcard character <?> .
<?> means the same as <? extends Object>. Therefore, according to the PECS principle, listit is producer. And produceronly producing elements. And we in a cycle forcall a method set(), i.e. trying to write in list. And therefore we rest against the protection of Java, which does not allow to set any value on the index.

What to do? The pattern will help us Wildcard Capture. Here we create a generic method rev. It is declared with a type variable T. This method takes a list of types T, and we can make a set.

publicstaticvoidreverse(List<?> list){ 
  rev(list); 
}
privatestatic <T> voidrev(List<T> list){
  List<T> tmp = new ArrayList<T>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));
  }
}

Now we have everything compiled. This is where the wildcard capture was captured. When calling a method reverse(List<?> list), a list of some objects (for example, strings or integers) is passed as an argument. If we can capture the type of these objects and assign it to a type variable X, then we can conclude what Tis X.

More information about Wildcard Capturecan be read here and here .

Conclusion

If you need to read from the container, then use a wildcard with the upper limit " ? extends". If you need to write to the container, then use a wildcard with a lower bound " ? super". Do not use a wildcard if you need to write and read.

Do not use Rawtypes! If the type argument is not defined, use a wildcard <?>.

Type variables

When we write an identifier in angle brackets, for example <T>or when declaring a class or method <E>, we create a type variable . A type variable is an unqualified identifier that can be used as a type in the body of a class or method. A type variable can be bounded above.

publicstatic <T extends Comparable<T>> T max(Collection<T> coll){
  T candidate = coll.iterator().next();
  for (T elt : coll) {
    if (candidate.compareTo(elt) < 0) candidate = elt;
  }
  return candidate;
}

In this example, the expression T extends Comparable<T>defines T(a type variable) bounded above by type Comparable<T>. Unlike a wildcard, type variables can only be limited from above (only extends). Can not write super. In addition, in this example it Tdepends on itself; this is called the recursive boundrecursive boundary.

Here is another example from the Enum class:

publicabstractclassEnum<EextendsEnum<E>>implementsComparable<E>, Serializable

Here, the Enum class is parameterized by the type E, which is a subtype of Enum<E>.

Multiple bounds

Multiple Bounds- multiple restrictions. It is written through the symbol " &", that is, we say that the type represented by a type variable Tmust be limited from above by the class Objectand interface Comparable.

<T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

The entry Object & Comparable<? super T&gtforms the type of intersection Multiple Bounds. The first limitation - in this case Object- is used for the erasuretype mashing process. It is executed by the compiler at the compilation stage.

Conclusion

A type variable can only be bounded above by one or more types. In the case of multiple constraints, the left border (the first constraint) is used during the mashing process (Type Erasure).

Type erasure

Type Erasure is a mapping of types (possibly including parameterized types and type variables) to types that are never parametrized types or variable types. We write mashing type Tas |T|.

The rubbing mapping is defined as follows:

• The rubbing of the parameterized type G < T1 , ..., Tn > is | G |
• Overwriting nested type TC is | T |. C
• The rubbing of the array type T [] is | T | []
• Rubbing a type variable is rubbing its left border.
• Mashing any other type is this type itself.

During the execution of Type Erasure (type mashing), the compiler performs the following actions:

• adds casting to ensure type safety, if necessary
• generates bridge methods to save polymorphism

T (Type)	| T | (Rubbing type)
List <Integer>, List <String>, List <List <String >>	List
List <Integer> []	List []
List	List
int	int
Integer	Integer
<T extends Comparable <T >>	Comparable
<T extends Object & Comparable <? super T >>	Object
LinkedCollection <E> .Node	LinkedCollection.Node

This table shows what the different types are turning into in the process of mashing, Type Erasure.

In the screenshot below, two examples of the program:


The difference between them is that the compile-time error occurs on the left, and everything on the right is compiled without errors. Why?

Reifiable types

In Java, we say that a type is reifiableif information about it is fully accessible at runtime. Reifiable types include:

• Primitive types ( int , long , boolean )
• Non-parameterized (non-generic) types ( String , Integer )
• Parameterized types whose parameters are represented as an unbounded wildcard (unlimited wildcard characters) ( List <?> , Collection <?> )
• Raw (unformed) types ( List , ArrayList )
• Arrays whose components are Reifiable types ( int [] , Number [] , List <?> [] , List [ )

Why information about some types is available, but not about others? The fact is that due to the type overwriting process by the compiler, information about some types may be lost. If it is lost, then this type will no longer be reifiable. That is, it is not available at runtime. If available, respectively, reifiable.

The decision not to make all generic types available at runtime is one of the most important and controversial design decisions in the Java type system. So did, first of all, for compatibility with existing code. I had to pay for migratory compatibility - full availability of the system of generalized types at runtime is impossible.

Which types are not reifiable:

• Variable type ( t )
• Parameterized type with specified parameter type ( List <Number> ArrayList <String> , List <List <String >> )
• Parameterized type with the specified upper or lower bound ( List <? Extends Number>, Comparable <? Super String> ). But here it is worth mentioning: List <? extends Object> is not reifiable, but List <?> is reifiable

And one more problem. Why in the example below it is impossible to create a parameterized Exception?

classMyException<T> extendsException{ 
   T t;
}

Unchecked warnings

Compilation of our application can give the so-called Unchecked Warning- a warning that the compiler could not correctly determine the level of security using our types. This is not a mistake, but a warning, so you can skip it. But it is advisable to fix everything in order to avoid problems in the future.

Heap pollution

As we mentioned earlier, assigning a reference to the Raw type of a variable of a parameterized type results in the warning “Unchecked assignment”. If we ignore it, a situation called " Heap Pollution" (heap pollution) is possible . Here is an example:

static List<String> t(){
   List l = new ArrayList<Number>();
   l.add(1);
   List<String> ls = l; // (1)
   ls.add("");
   return ls;
}

In line (1), the compiler warns about “Unchecked assignment”.

We need to give another example of “pollution of the heap” - when we use parameterized objects. The code snippet below clearly shows that it is unacceptable to use parameterized types as method arguments using Varargs. In this case, the parameter of the method m is List<String>…, i.e. in fact, an array of type elements List<String>. Given the type mapping rule for mashing, the type is stringListsconverted into an array of raw lists ( List[]), i.e. you can perform an assignment Object[] array = stringLists;and then write to arrayan object other than the list of strings (1), which will cause ClassCastExceptiona string (2).

staticvoidm(List<String>... stringLists){
   Object[] array = stringLists;
   List<Integer> tmpList = Arrays.asList(42);
   array[0] = tmpList; // (1)
   String s = stringLists[0].get(0); // (2)
}

Consider another example:

ArrayList<String> strings = new ArrayList<>();
ArrayList arrayList = new ArrayList();
arrayList = strings; // (1) Ok
arrayList.add(1); // (2) unchecked call

Java permits assignment in string (1). This is necessary for backward compatibility. But if we try to execute the method addin line (2), we get a warning Unchecked call- the compiler warns us about a possible error. In fact, we are trying to add an integer to the list of strings.

Reflection

Although the compiled types are subject to the erasure procedure (type erasure), we can get some information using Reflection.

• All reifiable are available through the Reflection mechanism.
  
• Information about the type of class fields, method parameters and the values ​​returned by them is available via Reflection.
  

If we want through Reflection to get information about the type of the object and this type is not Reifiable, then we will fail. But, if, for example, this object returned some method to us, then we can get the type of the value returned by this method:

java.lang.reflect.Method.getGenericReturnType()

With the advent of Generics, the class has java.lang.Classbecome parameterized. Consider this code:

List<Integer> ints = new ArrayList<Integer>();
Class<? extends List> k = ints.getClass();
assert k == ArrayList.class;

A variable intshas a type List<Integer>and it contains a reference to an object of type ArrayList< Integer>. It ints.getClass()will then return an object of type Class<ArrayLis>, since it is List<Integer>overwritten by List. A type object Class<ArrayList>can be assigned to a ktype variable Class<? extends List>according to the covariance of the wildcard characters? extends. And ArrayList.classreturns an object of type Class<ArrayList>.

Conclusion

If type information is available at runtime, then that type is called Reifiable. Reifiable types include primitive types, non-parameterized types, parameterized types with unlimited wildcard characters, Raw types, and arrays whose elements are reifiable.

Ignoring Unchecked Warnings can lead to heap pollution and errors during program execution.

Reflection does not provide information about the type of an object if it is not Reifiable. But Reflection allows you to get information about the type of the value returned by the method, the type of the method arguments and the type of the class fields.

Type Inference

The term can be translated as "type inference". This is the ability of the compiler to determine (infer) the type from the context. Here is a sample code:

List<Integer> list = new ArrayList<Integer>();

With the advent of the diamond operator in Java 7, we can omit the type of y ArrayList:

List<Integer> list = new ArrayList<>();

The compiler will infer the type ArrayListout of context List<Integer>. This process is called type inference.

In Java 8, the type inference engine has been greatly improved with JEP 101.
In general, the process of obtaining information about unknown types is referred to as Type Inference type inference. At the top level, type inference can be divided into three processes:

• Reduction
  
• Incorporation
  
• Resolution
  

These processes work closely together: a cast can trigger a join, a join can lead to a further cast, and a resolution can lead to a further join.
A detailed description of the type inference mechanism is available in the language specification, where an entire chapter is devoted to it. We will return to JEP 101 and consider what goals he pursued.

Suppose we have a class here that describes a linked list:

classList<E> {
   static <Z> List<Z> nil(){ ... };
   static <Z> List<Z> cons(Z head, List<Z> tail){ ... };
   E head(){ ... }
}

The result of the generalized method List.nil()can be derived from the right side:

List<String> ls = List.nil();

The type selection mechanism of the compiler shows that the type argument to call is List.nil()valid String— it works in JDK 7, everything is fine.

It seems reasonable that the compiler should also be able to infer a type when the result of such a call to the generic method is passed to another method as an argument, for example:

List.cons(42, List.nil()); //error: expected List<Integer>, found List<Object>

In JDK 7, we would get a compile-time error. And in JDK 8 it will be compiled. This is the first part of JEP-101, its first goal is type inference in the position of the argument. The only way to do this in versions prior to JDK 8 is to use an explicit type argument when calling the generic method:

List.cons(42, List.<Integer>nil());

The second part of JEP-101 says that it would be nice to display the type in the call chain of generalized methods, for example:

String s = List.nil().head(); //error: expected String, found Object

But this problem has not been solved so far, and it is unlikely that such a function will appear in the near future. Perhaps in future versions of the JDK the need for this will disappear, but for now you need to specify the arguments manually:

String s = List.<String>nil().head();

After JEP 101 was released on StackOverflow, a lot of questions appeared on the topic. Programmers ask why the code that was executed on version 7 is executed differently on the 8th version - or is it not compiled at all? Here is an example of such a code:

classTest{
   staticvoidm(Object o){
       System.out.println("one");
   }
   staticvoidm(String[] o){
       System.out.println("two");
   }
   static <T> T g(){
       returnnull;
   }
   publicstaticvoidmain(String[] args){
       m(g());
   }
}

Look at the bytecode after compiling on JDK1.8:

  publicstaticvoidmain(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=1, locals=1, args_size=1
         0: invokestatic  #6                  // Method g:()Ljava/lang/Object;
         3: checkcast     #7                  // class "[Ljava/lang/String;"
         6: invokestatic  #8                  // Method m:([Ljava/lang/String;)V
         9: return
      LineNumberTable:
        line 15: 0
        line 16: 9

Instruction number 0 makes a method call. g:()Ljava/lang/Object;The method returns java.lang.Object. Next, instruction 3 performs the casting (“casting”) of the object obtained in the previous step to the array type java.lang.String, and instruction 6 executes the method m:([Ljava/lang/String;), which will print “two” on the console.

And now the bytecode after compiling on JDK1.7 - that is, on Java 7:

  publicstaticvoidmain(java.lang.String[]);
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=1, locals=1, args_size=1
         0: invokestatic  #6                  // Method g:()Ljava/lang/Object;
         3: invokestatic  #7                  // Method m:(Ljava/lang/Object;)V
         6: return        
      LineNumberTable:
        line 15: 0
        line 16: 6

We see that there is no instruction checkcastthat Java 8 has added, so the method will be called m:(Ljava/lang/Object;), and “one” will be printed on the console. Checkcast- the result of a new type deduction that was improved in Java 8.

To avoid such problems, Oracle released a guide to migrating from JDK1.7 to JDK 1.8, which describes problems that may arise when upgrading to a new version of Java, and how these problems can be solved.

For example, if you want the code above after compiling to Java 8 to work the same as Java 7, do the type conversion manually:

publicstaticvoidmain(String[] args){
   m((Object)g());
}

Conclusion

This is where my story about Java Generics comes to an end. Here are other sources to help you master the topic:

• Naftalin, Maurice; Wadler, Philip. Java Generics and Collections. O'Reilly Media. ISBN-13: 978-0596527754
  
• https://docs.oracle.com/javase/specs/jls/se8/html/index.html
  
• Programming language Java SE 8. Addison-Wesley. ISBN: 978-5-8459-1875-8
  

• Bloch, Joshua. Effective Java. Third Edition. Addison-Wesley. ISBN-13: 978-0-13-468599-1
  

The post is a brief retelling of the report of the same name, in which we understand the features of working with Java Generics.