RFR 8178150: Regression in logic for handling inference stuck constraints

Tue Oct 24 23:43:35 UTC 2017

On 24/10/17 23:21, Vicente Romero wrote:
> Hi Maurizio,
>
> Thanks for the updated version. I agree with you that once the closure 
> of a given node is calculated it should be cached. Probably in an 
> independent data structure as it could be expensive to calculate the 
> closure and also because for a given graph, the closure will be the 
> same for a given node until the graph changes. I still have comments 
> on the performance land but I would like to focus on the correctness 
> first. This code, at DeferredAttrContext::buildStuckGraph:
>
> InferenceGraph graph = infer.new GraphSolver(inferenceContext, 
> types.noWarnings)
>                     .new InferenceGraph();
>
> will return a graph in which strongly connected components have been 
> merged along with theirs dependencies, meaning that if variable T1 and 
> T2 are strongly connected, dependencies of T1 will be the same as 
> dependencies of T2. I'm not sure that the spec considered this graph 
> as the one over which to calculate input and output variables. 
input and output variables are computed on a number of factors; first 
there's a structural definition that says what input and output 
variables are, looking at the shape of the constraints.

Then, once you know which variables are input and which are output, you 
have to (quoting the spec) do this:

  "A subset of constraints is selected in C, satisfying the property 
that, for each constraint, no input variable can influence an output 
variable of another constraint in C"

The "can influence" bit here is crucial - in fact the spec goes on and 
says "An inference variable α /can influence/ an inference variable β if 
α depends on the resolution of β (§18.4 
<https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.4>), 
or vice versa; or if there exists a third inference variable γ such that 
α can influence γ and γ can influence β. "

That is, 'can influence' induces the same inference graph that is used 
during resolution - it _is_ the same thing. So it's natural, I think, 
for the implementation, to reuse the same graph to model the 'can 
influence' relationship.
> Also I'm wondering if it could be the case that the tarjan algorithm 
> could place an input and an output variable in the same node.
In terms of the spec, I think you are asking "is it possible for two 
variables alpha and beta, where alpha is an input variable and beta is 
an output variable to be such that alpha can influence beta and beta can 
influence alpha?"

I think that's possible yes. But that's why 18.5.2.2 allows for cycles, 
and breaks up the deadlock by picking one.
>
> Apart from this there are assumptions that even though are previous to 
> this code, could affect the outcome. It is been assumed that stuck 
> variables == input variables. But according to the spec in this case
>
> ‹LambdaExpression → throws T ›
>
> T is an input variable, but I don't think that it will be considered 
> as a stuck variable. Similar for method references.
I was confused a bit by that too - but note that it doesn't mean what it 
looks - for instance, consider this (18.1.2):

"‹/LambdaExpression/ →_/throws/ T›: The checked exceptions thrown by the 
body of the /LambdaExpression/ are declared by the |throws| clause of 
the function type derived from T."

This implies that T is just a target type (a functional interface); in 
other words, this means that we have a lambda and a target which is an 
inference var - so the constraint for evaluating checked exceptions is 
also 'stuck' because you can't obtain the set of expected exceptions if 
you don't have a functional interface as a target.

But I believe that both

  ‹/LambdaExpression/ → T›

and

‹/LambdaExpression/ →_/throws/ T›

lead to the same set of input variables; there is actually a very tiny 
difference, in that the latter constraint doesn't add in the input 
variable set the input variables of the constraints coming from the 
return expressions of the lambda - and that's because, I think, you can 
reason about exceptions being thrown by a lambda even if some return 
expressions are 'stuck'. Which means I guess, at least hypothetically, 
you could write a test where the spec picks ‹/LambdaExpression/ 
→_/throws/ T› and decides to process that ahead of  ‹/LambdaExpression/ 
→ T› - while in javac the two happen at the same time (because javac 
doesn't have the distinction between these two constraints - throws 
constraints are evaluated as part of evaluating the lambda compatibility 
constraint).

In other words, I'm not denying that there's a slight mismatch here - 
but I think the magnitude of that mismatch is very small - especially 
compared to the current situation. Moreover, I suspect that fixing this 
mismatch will require a lot of implementation changes - as I say above, 
in a way the mismatch reflects the different way in which the compiler 
goes about when reasoning about constraint formulas (which was mostly 
dictated out of compatibility constraints - e.g. make same inference 
engine work on both 8 and 7).

So, while I'm not dismissing the concern, I think that's a candidate for 
a followup investigation.

Maurizio
>
> Thanks,
> Vicente
>
> On 10/19/2017 05:41 AM, Maurizio Cimadamore wrote:
>> Updated webrev
>>
>> http://cr.openjdk.java.net/~mcimadamore/8178150_v2/
>>
>> Maurizio
>>
>>
>> On 19/10/17 09:38, Maurizio Cimadamore wrote:
>>> I think you are right - this method was there when I first wrote the 
>>> patch but then got removed. I resurrected it for the purpose of this 
>>> patch, but it seems like it's not doing what we need.
>>>
>>> Maurizio
>>>
>>>
>>> On 19/10/17 00:57, Vicente Romero wrote:
>>>> Hi Maurizio,
>>>>
>>>> I'm not sure about the correctness or the objective of the 
>>>> closure() method. The termination condition seems to be: stop as 
>>>> soon as you find a cycle in the graph, at least this is my reading. 
>>>> But for some graphs this could imply finding a subset of the 
>>>> closure not the whole of it. It seems to me like implementing a 
>>>> graph traversal method should be what it is wanted here. Unless 
>>>> there is something I'm missing.
>>>>
>>>> Also in the same method the javadoc could have stall comments as it 
>>>> says that a kind of dependencies is given but there is no argument 
>>>> passed to the method.
>>>>
>>>> Thanks,
>>>> Vicente
>>>>
>>>> On 10/18/2017 04:15 PM, Maurizio Cimadamore wrote:
>>>>> Hi,
>>>>> this issue has already been discussed in [1].
>>>>>
>>>>> The issue has to do with the fact that logic for picking a 
>>>>> deferred node to unstick ignores the can-influence relationship 
>>>>> (aka inference graph dependencies).
>>>>>
>>>>> The implemented code is not optimized (almost deliberately); I 
>>>>> wanted the code to follow the spec more or less cleanly. While I'm 
>>>>> open to small improvements, I would please ask to focus on 
>>>>> correctness for the time being since (i) this code is not an hot 
>>>>> execution path and (ii) other performance improvements in this 
>>>>> area will follow, see [2].
>>>>>
>>>>> http://cr.openjdk.java.net/~mcimadamore/8178150/
>>>>>
>>>>> [1] - 
>>>>> http://mail.openjdk.java.net/pipermail/compiler-dev/2017-October/011192.html
>>>>> [2] - 
>>>>> http://mail.openjdk.java.net/pipermail/compiler-dev/2017-October/011126.html
>>>>>
>>>>> Cheers
>>>>> Maurizio
>>>>>
>>>>
>>>
>>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20171025/f3dd1c8b/attachment-0001.html>