Summary
-------

Implement a new method type-checking strategy in `javac` to speed up attribution of poly expression in argument position.

Goals
-------

Implement a new approach for type checking poly expressions, _tiered attribution_ (TA), which provides:

- Improved performances by implementing an approach which reduces the number of (redundant) passes needed to attribute a given expression, and

- The same results as the current type-checking implementation.

Non-Goals
---------

It is not a goal to alter the space of compilable programs, although some changes might result as a consequence of fixing lurking bugs in the existing type-checking scheme. Some minor differences in the compiler generated messages are also to be expected.

It is also a non-goal to significantly improve cleanliness and maintainability of the current code - although it might be possible that some of the changes introduced by this JEP would also result in cleaner code.

Motivation
----------
The currently implemented approach for implementing type-checking of Java SE 8 poly expressions is known as 'Speculative attribution' (SA); the main idea of SA is to type-check the same tree multiple times against different targets; this makes it possible to e.g. check a lambda expression against multiple overload resolution targets.

The ability of performing type-checking in the middle of overload resolution is a very powerful and flexible technique, but it comes at a very high price in terms of performances. More precisely, with N overload candidates, the same argument expression can be checked up to N * 3 (once per each overload phase, strict, loose, varargs) + 1 (final check phase). If argument expressions allow nesting (e.g. a lambda returning a poly method call) those factors need to be multiplied, leading to a combinatorial explosion of attribution calls.

The exponential number of calls to the speculative attribution machinery has resulted in performance issues that have been observed and reported as bugs, e.g., [JDK-8077247](https://bugs.openjdk.java.net/browse/JDK-8077247), [JDK-8078093](https://bugs.openjdk.java.net/browse/JDK-8078093) and [JDK-8055984](https://bugs.openjdk.java.net/browse/JDK-8055984).

Description
-----------

This JEP proposes an alternate, and more effective, implementation scheme for supporting type checking of poly expressions in `javac`. Conceptually, there is no need to type-check an expression while performing overload resolution; in fact, an argument expression can either be type-checked in a bottom-up style - resulting in an attribution-free overload check, or such expression is not pertinent to applicability (see JLS 15.12.2.2)- meaning such expression does not contribute to the overload resolution applicability check. For instance, a lambda expression can either be explicit - in which case type-checking of the body can be performed ahead of overload resolution; or it can be implicit, in which case no type-checking is required during overload resolution.

The main idea behind tiered attribution is to produce, ahead of overload resolution, bottom-up structural types (one for each poly argument expression occurring in a given method call) with all the information needed to perform the overload resolution applicability check - i.e. without further need for attribution. It is possible for such structural types to contain partially-inferred type variables which will only be fixed at a later stage - during invocation type-inference (see JLS 18.5.2). New structural types will be created for the following argument expressions:

- Lambda expressions,
- Conditional poly expressions,
- Generic method calls,
- Parenthesized poly expressions,
- Method references, and
- Diamond instance creation expressions.

Since some of the expressions mentioned above can allow nesting, it is possible for a structural type to mention other structural types. For example, the case of a lambda expression returning a generic method call can be modelled with a structural type (for the lambda expression) pointing to another structural type modelling the generic method call. In such cases, the overload check associated with a structural type can be recursive - e.g. all structural types mentioned by the return expressions in a lambda body will have to be checked against the target-type provided by the overload resolution machinery.

Structural types will typically be created when attributing arguments of a method/constructor call. Poly expressions that occur in a context other than method/constructor invocation should be handled in the same way as they are today.

Some changes to type inference will also be required in order to implement nested generic method calls appropriately; more specifically, the type inference machinery must be equipped with better save and rollback features in order to handle overload checks involving generic method calls (which could require some inference tasks to be performed) without permanently polluting the contextual information associated with such calls.

Testing
-------

`javac` already contains a comprehensive set of regression tests to prove that SA works as expected; while most of these tests are mainly black-box tests they should be effective in catching tiered attribution implementation bugs. Some additional tests - especially in relation to well-known performance bottlenecks - might be added as a result of this JEP.

Dependences
-----------

The work proposed here may benefit two related JEPs:
[Process Import Statements Correctly (JEP 216)](http://openjdk.java.net/jeps/216)
and [Annotations Pipeline 2.0 (JEP 217)](http://openjdk.java.net/jeps/217).