[dart2js] Resolve non-converging parameter types in linearized inference algorithm. Due to the introduction of "virtual parameters" (parameters of virtual functions) there was a new pattern that allowed for non-converging types. If two functions are mutually recursive and one makes a virtual call to the other, then we end up with a cycle in the parameter types. That part isn't new, that cycle already existed. However, now the cycle can include the virtual parameters for those functions. The way we enqueue the users after resolving a virtual parameter can cause an alternating pattern of refinement that doesn't allow the cycle to fully resolve itself. We resolve this by manually enqueueing the concrete parameter and its associated NarrowTypeInformation (which enforces the static type). The key is that these are enqueued before other users of the virtual parameter which in the bad case are other members in the cycle that were being processed out of order. Change-Id: Ic20afcc55ca6e75152d7858eaab1cb24a57ea20e Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/303120 Commit-Queue: Nate Biggs <natebiggs@google.com> Reviewed-by: Mayank Patke <fishythefish@google.com>
diff --git a/pkg/compiler/lib/src/inferrer/engine.dart b/pkg/compiler/lib/src/inferrer/engine.dart index c5f4cc4..fc2d1e0 100644 --- a/pkg/compiler/lib/src/inferrer/engine.dart +++ b/pkg/compiler/lib/src/inferrer/engine.dart
@@ -791,7 +791,21 @@ info.type = info.refine(this); info.doNotEnqueue = true; } - _workQueue.addAll(info.users); + for (final user in info.users) { + _workQueue.add(user); + // Virtual parameters that are part of a cycle can end up stuck in + // a refinement pattern that prevents the members of the cycle from + // converging. We avoid this by adding the concrete parameter and + // corresponding narrowing type to the queue before other members of + // the cycle. + if (user is ParameterTypeInformation) { + final concreteParameterType = user.concreteParameterType; + if (concreteParameterType != null) { + _workQueue.add(concreteParameterType); + _workQueue.addAll(concreteParameterType.users); + } + } + } if (info.hasStableType(this)) { info.stabilize(this); } @@ -855,7 +869,7 @@ } if (type == null) type = getDefaultTypeOfParameter(parameter); TypeInformation info = - types.getInferredTypeOfParameter(parameter, virtual: virtualCall); + types.getInferredTypeOfParameter(parameter, isVirtual: virtualCall); if (remove) { info.removeInput(type); } else { @@ -908,9 +922,10 @@ types.strategy.forEachParameter(member as FunctionEntity, (Local parameter) { final virtualParamInfo = - types.getInferredTypeOfParameter(parameter, virtual: true); + types.getInferredTypeOfParameter(parameter, isVirtual: true); final realParamInfo = types.getInferredTypeOfParameter(parameter); realParamInfo.addInput(virtualParamInfo); + assert(virtualParamInfo.users.first == realParamInfo); }); if (member.isFunction) { virtualCallType.addInput(types.getInferredTypeOfMember(member)); @@ -927,7 +942,7 @@ final Map<String, TypeInformation> named = {}; types.strategy.forEachParameter(parent, (Local parameter) { TypeInformation type = - types.getInferredTypeOfParameter(parameter, virtual: true); + types.getInferredTypeOfParameter(parameter, isVirtual: true); if (parameterIndex < parameterStructure.requiredPositionalParameters) { positional.add(type); } else if (parameterStructure.namedParameters.isNotEmpty) { @@ -956,7 +971,7 @@ // default value will be used within the body of the override. parentParamInfo ??= getDefaultTypeOfParameter(parameter); TypeInformation overrideParamInfo = - types.getInferredTypeOfParameter(parameter, virtual: true); + types.getInferredTypeOfParameter(parameter, isVirtual: true); overrideParamInfo.addInput(parentParamInfo); parameterIndex++; }); @@ -979,7 +994,7 @@ types.strategy.forEachParameter(override as FunctionEntity, (Local parameter) { final paramInfo = - types.getInferredTypeOfParameter(parameter, virtual: true); + types.getInferredTypeOfParameter(parameter, isVirtual: true); paramInfo.addInput(parentType); }); } else { @@ -1002,7 +1017,7 @@ types.strategy.forEachParameter(parent as FunctionEntity, (Local parameter) { final paramInfo = - types.getInferredTypeOfParameter(parameter, virtual: true); + types.getInferredTypeOfParameter(parameter, isVirtual: true); overrideType.addInput(paramInfo); }); } @@ -1032,8 +1047,8 @@ } types.strategy.forEachParameter(member as FunctionEntity, (Local parameter) { - ParameterTypeInformation info = - types.getInferredTypeOfParameter(parameter, virtual: isVirtualCall); + ParameterTypeInformation info = types + .getInferredTypeOfParameter(parameter, isVirtual: isVirtualCall); info.tagAsTearOffClosureParameter(this); if (addToQueue) _workQueue.add(info); }); @@ -1099,7 +1114,7 @@ TypeInformation info = types.getInferredTypeOfParameter(parameter); if (existing != null && existing is PlaceholderTypeInformation) { TypeInformation virtualInfo = - types.getInferredTypeOfParameter(parameter, virtual: true); + types.getInferredTypeOfParameter(parameter, isVirtual: true); // Replace references to [existing] to use [type] instead. info.inputs.replace(existing, type); virtualInfo.inputs.replace(existing, type); @@ -1508,7 +1523,8 @@ ParameterTypeInformation createParameterTypeInformation( AbstractValueDomain abstractValueDomain, covariant JLocal parameter, - TypeSystem types) { + TypeSystem types, + {required bool isVirtual}) { MemberEntity context = parameter.memberContext; KernelToLocalsMap localsMap = _globalLocalsMap.getLocalsMap(context); ir.FunctionNode functionNode = @@ -1537,7 +1553,8 @@ parameter, type, member as FunctionEntity, - ParameterInputs.instanceMember()); + ParameterInputs.instanceMember(), + isVirtual: isVirtual); } else { return ParameterTypeInformation.static(abstractValueDomain, memberTypeInformation, parameter, type, member as FunctionEntity);
diff --git a/pkg/compiler/lib/src/inferrer/type_graph_nodes.dart b/pkg/compiler/lib/src/inferrer/type_graph_nodes.dart index e5da169..976eab1 100644 --- a/pkg/compiler/lib/src/inferrer/type_graph_nodes.dart +++ b/pkg/compiler/lib/src/inferrer/type_graph_nodes.dart
@@ -47,35 +47,36 @@ isInstanceMemberParameter, // 5 isClosureParameter, // 6 isInitializingFormal, // 7 + isVirtual, // 8 // ---Flags for [CallSiteTypeInformation]--- - inLoop, // 8 + inLoop, // 9 // ---Flags for [DynamicCallSiteTypeInformation]--- - isConditional, // 9 - hasClosureCallTargets, // 10 - targetsIncludeComplexNoSuchMethod, // 11 - hasTargetsIncludeComplexNoSuchMethod, // 12 + isConditional, // 10 + hasClosureCallTargets, // 11 + targetsIncludeComplexNoSuchMethod, // 12 + hasTargetsIncludeComplexNoSuchMethod, // 13 // ---Flags for [PhiElementTypeInformation]--- - isTry, // 13 + isTry, // 14 // ---Flags for [ValueInMapTypeInformation]--- - valueInMapNonNull, // 14 + valueInMapNonNull, // 15 // ---Flags for [MemberTypeInformation]--- - isCalled, // 15 - isCalledMoreThanOnce, // 16 + isCalled, // 16 + isCalledMoreThanOnce, // 17 // ---Flags for [ApplyableTypeInformation]--- - mightBePassedToFunctionApply, // 17 + mightBePassedToFunctionApply, // 18 // ---Flags for [InferredTypeInformation]--- - inferred, // 18 + inferred, // 19 // ---Flags for [TracedTypeInformation]--- - notBailedOut, // 19 - analyzed, // 20 + notBailedOut, // 20 + analyzed, // 21 } /// Common class for all nodes in the graph. The current nodes are: @@ -787,6 +788,8 @@ bool get _isClosureParameter => _hasFlag(_Flag.isClosureParameter); bool get _isInitializingFormal => _hasFlag(_Flag.isInitializingFormal); bool _isTearOffClosureParameter = false; + TypeInformation? get concreteParameterType => + _hasFlag(_Flag.isVirtual) ? users.first : null; ParameterTypeInformation.localFunction( super.abstractValueDomain, @@ -815,9 +818,11 @@ this._parameter, this._type, this._method, - ParameterInputs inputs) + ParameterInputs inputs, + {required bool isVirtual}) : super._withInputs(abstractValueDomain, context, inputs) { _setFlag(_Flag.isInstanceMemberParameter); + _setFlagTo(_Flag.isVirtual, isVirtual); } FunctionEntity get method => _method;
diff --git a/pkg/compiler/lib/src/inferrer/type_system.dart b/pkg/compiler/lib/src/inferrer/type_system.dart index 55d03b5..dfa591e 100644 --- a/pkg/compiler/lib/src/inferrer/type_system.dart +++ b/pkg/compiler/lib/src/inferrer/type_system.dart
@@ -22,7 +22,8 @@ ParameterTypeInformation createParameterTypeInformation( AbstractValueDomain abstractValueDomain, Local parameter, - TypeSystem types); + TypeSystem types, + {required bool isVirtual}); /// Calls [f] for each parameter in [function]. void forEachParameter(FunctionEntity function, void f(Local parameter)); @@ -322,13 +323,14 @@ } ParameterTypeInformation getInferredTypeOfParameter(Local parameter, - {bool virtual = false}) { - final typeInformations = - virtual ? virtualParameterTypeInformations : parameterTypeInformations; + {bool isVirtual = false}) { + final typeInformations = isVirtual + ? virtualParameterTypeInformations + : parameterTypeInformations; return typeInformations.putIfAbsent(parameter, () { - ParameterTypeInformation typeInformation = - strategy.createParameterTypeInformation( - _abstractValueDomain, parameter, this); + ParameterTypeInformation typeInformation = strategy + .createParameterTypeInformation(_abstractValueDomain, parameter, this, + isVirtual: isVirtual); _orderedTypeInformations.add(typeInformation); return typeInformation; });