| // Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import 'package:analyzer/dart/ast/ast.dart'; |
| import 'package:analyzer/dart/element/element.dart'; |
| import 'package:analyzer/dart/element/type.dart'; |
| import 'package:analyzer/src/dart/element/element.dart'; |
| import 'package:analyzer/src/dart/element/type.dart'; |
| import 'package:analyzer/src/dart/element/type_algebra.dart'; |
| import 'package:analyzer/src/summary2/function_type_builder.dart'; |
| import 'package:analyzer/src/summary2/lazy_ast.dart'; |
| import 'package:analyzer/src/summary2/named_type_builder.dart'; |
| import 'package:analyzer/src/summary2/type_builder.dart'; |
| import 'package:analyzer/src/util/graph.dart'; |
| |
| class DefaultTypesBuilder { |
| void build(List<AstNode> nodes) { |
| for (var node in nodes) { |
| if (node is ClassDeclaration) { |
| var element = node.declaredElement; |
| _breakSelfCycles(node.typeParameters); |
| _breakRawTypeCycles(element, node.typeParameters); |
| _computeBounds(element, node.typeParameters); |
| } else if (node is ClassTypeAlias) { |
| var element = node.declaredElement; |
| _breakSelfCycles(node.typeParameters); |
| _breakRawTypeCycles(element, node.typeParameters); |
| _computeBounds(element, node.typeParameters); |
| } else if (node is FunctionTypeAlias) { |
| var element = node.declaredElement; |
| _breakSelfCycles(node.typeParameters); |
| _breakRawTypeCycles(element, node.typeParameters); |
| _computeBounds(element, node.typeParameters); |
| } else if (node is GenericTypeAlias) { |
| var element = node.declaredElement; |
| _breakSelfCycles(node.typeParameters); |
| _breakRawTypeCycles(element, node.typeParameters); |
| _computeBounds(element, node.typeParameters); |
| } else if (node is MixinDeclaration) { |
| var element = node.declaredElement; |
| _breakSelfCycles(node.typeParameters); |
| _breakRawTypeCycles(element, node.typeParameters); |
| _computeBounds(element, node.typeParameters); |
| } |
| } |
| for (var node in nodes) { |
| if (node is ClassDeclaration) { |
| _build(node.typeParameters); |
| } else if (node is ClassTypeAlias) { |
| _build(node.typeParameters); |
| } else if (node is FunctionTypeAlias) { |
| _build(node.typeParameters); |
| } else if (node is GenericTypeAlias) { |
| _build(node.typeParameters); |
| } else if (node is MixinDeclaration) { |
| _build(node.typeParameters); |
| } |
| } |
| } |
| |
| void _breakRawTypeCycles( |
| Element declarationElement, |
| TypeParameterList parameterList, |
| ) { |
| if (parameterList == null) return; |
| |
| var allCycles = <List<_CycleElement>>[]; |
| for (var parameter in parameterList.typeParameters) { |
| var boundNode = parameter.bound; |
| if (boundNode == null) continue; |
| |
| var cycles = _findRawTypePathsToDeclaration( |
| parameter, |
| boundNode.type, |
| declarationElement, |
| Set<Element>.identity(), |
| ); |
| allCycles.addAll(cycles); |
| } |
| |
| for (var cycle in allCycles) { |
| for (var element in cycle) { |
| var boundNode = element.parameter.bound; |
| if (boundNode is TypeName) { |
| boundNode.type = DynamicTypeImpl.instance; |
| } else { |
| throw UnimplementedError('(${boundNode.runtimeType}) $boundNode'); |
| } |
| } |
| } |
| } |
| |
| void _breakSelfCycles(TypeParameterList parameterList) { |
| if (parameterList == null) return; |
| var typeParameters = parameterList.typeParameters; |
| |
| Map<String, TypeParameter> typeParametersByName; |
| for (var parameter in typeParameters) { |
| var boundNode = parameter.bound; |
| if (boundNode is TypeName) { |
| if (typeParametersByName == null) { |
| typeParametersByName = {}; |
| for (var parameterNode in typeParameters) { |
| var name = parameterNode.name.name; |
| typeParametersByName[name] = parameterNode; |
| } |
| } |
| |
| var current = parameter; |
| for (var step = 0; |
| current != null && step < typeParameters.length; |
| ++step) { |
| var bound = current.bound; |
| if (bound is TypeName) { |
| var typeNameIdentifier = bound.name; |
| if (typeNameIdentifier is SimpleIdentifier) { |
| current = typeParametersByName[typeNameIdentifier.name]; |
| continue; |
| } |
| } |
| current = null; |
| break; |
| } |
| |
| if (current != null) { |
| boundNode.type = DynamicTypeImpl.instance; |
| } |
| } |
| } |
| } |
| |
| /// Build actual default type [DartType]s from computed [TypeBuilder]s. |
| void _build(TypeParameterList parameterList) { |
| if (parameterList == null) return; |
| |
| for (var parameter in parameterList.typeParameters) { |
| var defaultType = LazyAst.getDefaultType(parameter); |
| if (defaultType is TypeBuilder) { |
| var builtType = defaultType.build(); |
| LazyAst.setDefaultType(parameter, builtType); |
| } |
| } |
| } |
| |
| /// Compute bounds to be provided as type arguments in place of missing type |
| /// arguments on raw types with the given type parameters. |
| void _computeBounds( |
| Element declarationElement, |
| TypeParameterList parameterList, |
| ) { |
| if (parameterList == null) return; |
| |
| var typeProvider = declarationElement.library.typeProvider; |
| var dynamicType = typeProvider.dynamicType; |
| var nullType = typeProvider.nullType; |
| |
| var nodes = parameterList.typeParameters; |
| var length = nodes.length; |
| var elements = List<TypeParameterElement>(length); |
| var bounds = List<DartType>(length); |
| for (int i = 0; i < length; i++) { |
| var node = nodes[i]; |
| elements[i] = node.declaredElement; |
| bounds[i] = node.bound?.type ?? dynamicType; |
| } |
| |
| var graph = _TypeParametersGraph(elements, bounds); |
| var stronglyConnected = computeStrongComponents(graph); |
| for (var component in stronglyConnected) { |
| var dynamicSubstitution = <TypeParameterElement, DartType>{}; |
| var nullSubstitution = <TypeParameterElement, DartType>{}; |
| for (var i in component) { |
| var element = elements[i]; |
| dynamicSubstitution[element] = dynamicType; |
| nullSubstitution[element] = nullType; |
| } |
| |
| var substitution = Substitution.fromUpperAndLowerBounds( |
| dynamicSubstitution, |
| nullSubstitution, |
| ); |
| for (var i in component) { |
| bounds[i] = substitution.substituteType(bounds[i]); |
| } |
| } |
| |
| for (var i = 0; i < length; i++) { |
| var thisSubstitution = <TypeParameterElement, DartType>{}; |
| var nullSubstitution = <TypeParameterElement, DartType>{}; |
| var element = elements[i]; |
| thisSubstitution[element] = bounds[i]; |
| nullSubstitution[element] = nullType; |
| |
| var substitution = Substitution.fromUpperAndLowerBounds( |
| thisSubstitution, |
| nullSubstitution, |
| ); |
| for (var j = 0; j < length; j++) { |
| bounds[j] = substitution.substituteType(bounds[j]); |
| } |
| } |
| |
| // Set computed TypeBuilder(s) as default types. |
| for (var i = 0; i < length; i++) { |
| LazyAst.setDefaultType(nodes[i], bounds[i]); |
| } |
| } |
| |
| /// Finds raw type paths starting with the [startParameter] and a |
| /// [startType] that is used in its bound, and ending with [end]. |
| List<List<_CycleElement>> _findRawTypePathsToDeclaration( |
| TypeParameter startParameter, |
| DartType startType, |
| Element end, |
| Set<Element> visited, |
| ) { |
| var paths = <List<_CycleElement>>[]; |
| if (startType is NamedTypeBuilder) { |
| var declaration = startType.element; |
| if (startType.arguments.isEmpty) { |
| if (startType.element == end) { |
| paths.add([ |
| _CycleElement(startParameter, startType), |
| ]); |
| } else if (visited.add(startType.element)) { |
| void recurseParameters(List<TypeParameterElement> parameters) { |
| for (TypeParameterElementImpl parameter in parameters) { |
| TypeParameter parameterNode = parameter.linkedNode; |
| var bound = parameterNode.bound; |
| if (bound != null) { |
| var tails = _findRawTypePathsToDeclaration( |
| parameterNode, |
| bound.type, |
| end, |
| visited, |
| ); |
| for (var tail in tails) { |
| paths.add(<_CycleElement>[ |
| _CycleElement(startParameter, startType), |
| ...tail, |
| ]); |
| } |
| } |
| } |
| } |
| |
| if (declaration is ClassElement) { |
| recurseParameters(declaration.typeParameters); |
| } else if (declaration is GenericTypeAliasElement) { |
| recurseParameters(declaration.typeParameters); |
| } |
| visited.remove(startType.element); |
| } |
| } else { |
| for (var argument in startType.arguments) { |
| paths.addAll( |
| _findRawTypePathsToDeclaration( |
| startParameter, |
| argument, |
| end, |
| visited, |
| ), |
| ); |
| } |
| } |
| } else if (startType is FunctionTypeBuilder) { |
| paths.addAll( |
| _findRawTypePathsToDeclaration( |
| startParameter, |
| startType.returnType, |
| end, |
| visited, |
| ), |
| ); |
| for (var formalParameter in startType.parameters) { |
| paths.addAll( |
| _findRawTypePathsToDeclaration( |
| startParameter, |
| formalParameter.type, |
| end, |
| visited, |
| ), |
| ); |
| } |
| } |
| return paths; |
| } |
| } |
| |
| class _CycleElement { |
| final TypeParameter parameter; |
| final DartType type; |
| |
| _CycleElement(this.parameter, this.type); |
| } |
| |
| /// Graph of mutual dependencies of type parameters from the same declaration. |
| /// Type parameters are represented by their indices in the corresponding |
| /// declaration. |
| class _TypeParametersGraph implements Graph<int> { |
| @override |
| List<int> vertices; |
| |
| // Each `edges[i]` is the list of indices of type parameters that reference |
| // the type parameter with the index `i` in their bounds. |
| List<List<int>> _edges; |
| |
| final Map<TypeParameterElement, int> _parameterToIndex = Map.identity(); |
| |
| _TypeParametersGraph( |
| List<TypeParameterElement> parameters, |
| List<DartType> bounds, |
| ) { |
| assert(parameters.length == bounds.length); |
| |
| vertices = List<int>(parameters.length); |
| _edges = List<List<int>>(parameters.length); |
| for (int i = 0; i < vertices.length; i++) { |
| vertices[i] = i; |
| _edges[i] = <int>[]; |
| _parameterToIndex[parameters[i]] = i; |
| } |
| |
| for (int i = 0; i < vertices.length; i++) { |
| _collectReferencesFrom(i, bounds[i]); |
| } |
| } |
| |
| /// Return type parameters that depend on the [index]th type parameter. |
| @override |
| Iterable<int> neighborsOf(int index) { |
| return _edges[index]; |
| } |
| |
| /// Collect references to the [index]th type parameter from the [type]. |
| void _collectReferencesFrom(int index, DartType type) { |
| if (type is FunctionTypeBuilder) { |
| for (var parameter in type.typeFormals) { |
| _collectReferencesFrom(index, parameter.bound); |
| } |
| for (var parameter in type.parameters) { |
| _collectReferencesFrom(index, parameter.type); |
| } |
| _collectReferencesFrom(index, type.returnType); |
| } else if (type is NamedTypeBuilder) { |
| for (var argument in type.arguments) { |
| _collectReferencesFrom(index, argument); |
| } |
| } else if (type is TypeParameterType) { |
| var typeIndex = _parameterToIndex[type.element]; |
| if (typeIndex != null) { |
| _edges[typeIndex].add(index); |
| } |
| } |
| } |
| } |