| // 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 'dart:collection'; | |
| import 'package:analyzer/dart/ast/ast.dart'; | |
| import 'package:analyzer/src/generated/source.dart'; | |
| import 'package:meta/meta.dart'; | |
| import 'package:nnbd_migration/instrumentation.dart'; | |
| import 'package:nnbd_migration/nullability_state.dart'; | |
| import 'package:nnbd_migration/src/expression_checks.dart'; | |
| import 'package:nnbd_migration/src/nullability_node_target.dart'; | |
| import 'package:nnbd_migration/src/postmortem_file.dart'; | |
| import 'edge_origin.dart'; | |
| /// Base class for steps that occur as part of downstream propagation, where the | |
| /// nullability of a node is changed to a new state. | |
| abstract class DownstreamPropagationStep extends PropagationStep | |
| implements DownstreamPropagationStepInfo { | |
| @override | |
| NullabilityNodeMutable targetNode; | |
| /// The state that the node's nullability was changed to. | |
| /// | |
| /// Any propagation step that took effect should have a non-null value here. | |
| /// Propagation steps that are pending but have not taken effect yet, or that | |
| /// never had an effect (e.g. because an edge was not triggered) will have a | |
| /// `null` value for this field. | |
| Nullability newState; | |
| DownstreamPropagationStep(); | |
| DownstreamPropagationStep.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : targetNode = deserializer.nodeForId(json['target'] as int) | |
| as NullabilityNodeMutable, | |
| newState = Nullability.fromJson(json['newState']); | |
| @override | |
| DownstreamPropagationStep get principalCause; | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| return { | |
| 'target': serializer.idForNode(targetNode), | |
| 'newState': newState.toJson() | |
| }; | |
| } | |
| } | |
| /// Base class for steps that occur as part of propagating exact nullability | |
| /// upstream through the nullability graph. | |
| abstract class ExactNullablePropagationStep extends DownstreamPropagationStep { | |
| ExactNullablePropagationStep(); | |
| ExactNullablePropagationStep.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : super.fromJson(json, deserializer); | |
| } | |
| /// Conditions of the "lateness" of a [NullabilityNode]. | |
| enum LateCondition { | |
| /// The associated [NullabilityNode] does not represent the type of a late | |
| /// variable. | |
| notLate, | |
| /// The associated [NullabilityNode] represents the type of a late variable, | |
| /// due to a `/*late*/` hint. | |
| lateDueToHint, | |
| /// The associated [NullabilityNode] represents an variable which is possibly | |
| /// late, due to the late-inferring algorithm. | |
| possiblyLate, | |
| /// The associated [NullabilityNode] represents an variable which is possibly | |
| /// late, due to being assigned in a function passed to a call to the test | |
| /// package's `setUp` function. | |
| possiblyLateDueToTestSetup, | |
| } | |
| /// Abstract interface for assigning ids numbers to nodes. This allows us to | |
| /// annotate nodes with their ids when analyzing postmortem output. | |
| abstract class NodeToIdMapper { | |
| /// Gets the id corresponding to the given [node]. | |
| int idForNode(NullabilityNode node); | |
| } | |
| /// Data structure to keep track of the relationship from one [NullabilityNode] | |
| /// object to another [NullabilityNode] that is "downstream" from it (meaning | |
| /// that if the former node is nullable, then the latter node will either have | |
| /// to be nullable, or null checks will have to be added). | |
| class NullabilityEdge implements EdgeInfo { | |
| @override | |
| final NullabilityNode destinationNode; | |
| /// A set of upstream nodes. By convention, the first node is the source node | |
| /// and the other nodes are "guards". The destination node will only need to | |
| /// be made nullable if all the upstream nodes are nullable. | |
| final List<NullabilityNode> upstreamNodes; | |
| final _NullabilityEdgeKind _kind; | |
| /// The location in the source code that caused this edge to be built. | |
| final CodeReference codeReference; | |
| final String description; | |
| /// Whether this edge is the result of an uninitialized variable declaration. | |
| final bool isUninit; | |
| /// Whether this edge is the result of an assignment within the test package's | |
| /// `setUp` function. | |
| final bool isSetupAssignment; | |
| NullabilityEdge.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : destinationNode = deserializer.nodeForId(json['dest'] as int), | |
| upstreamNodes = [], | |
| _kind = _deserializeKind(json['kind']), | |
| codeReference = | |
| json['code'] == null ? null : CodeReference.fromJson(json['code']), | |
| description = json['description'] as String, | |
| isUninit = json['isUninit'] as bool, | |
| isSetupAssignment = json['isSetupAssignment'] as bool { | |
| deserializer.defer(() { | |
| for (var id in json['us'] as List<dynamic>) { | |
| upstreamNodes.add(deserializer.nodeForId(id as int)); | |
| } | |
| }); | |
| } | |
| NullabilityEdge._( | |
| this.destinationNode, this.upstreamNodes, this._kind, this.description, | |
| {this.codeReference, this.isUninit, this.isSetupAssignment}); | |
| @override | |
| Iterable<NullabilityNode> get guards => upstreamNodes.skip(1); | |
| /// Indicates whether it's possible for migration to cope with this edge being | |
| /// unsatisfied by inserting a null check. Graph propagation favors | |
| /// satisfying uncheckable edges over satisfying hard edges. | |
| bool get isCheckable => | |
| _kind == _NullabilityEdgeKind.soft || _kind == _NullabilityEdgeKind.hard; | |
| @override | |
| bool get isHard => | |
| _kind == _NullabilityEdgeKind.hard || _kind == _NullabilityEdgeKind.union; | |
| @override | |
| bool get isSatisfied { | |
| if (!isTriggered) return true; | |
| return destinationNode.isNullable; | |
| } | |
| @override | |
| bool get isTriggered { | |
| for (var upstreamNode in upstreamNodes) { | |
| if (!upstreamNode.isNullable) return false; | |
| } | |
| return true; | |
| } | |
| @override | |
| bool get isUnion => _kind == _NullabilityEdgeKind.union; | |
| @override | |
| bool get isUpstreamTriggered { | |
| if (!isHard) return false; | |
| return destinationNode.nonNullIntent.isPresent; | |
| } | |
| @override | |
| NullabilityNode get sourceNode => upstreamNodes.first; | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = <String, Object>{}; | |
| switch (_kind) { | |
| case _NullabilityEdgeKind.soft: | |
| break; | |
| case _NullabilityEdgeKind.uncheckable: | |
| json['kind'] = 'uncheckable'; | |
| break; | |
| case _NullabilityEdgeKind.hard: | |
| json['kind'] = 'hard'; | |
| break; | |
| case _NullabilityEdgeKind.union: | |
| json['kind'] = 'union'; | |
| break; | |
| case _NullabilityEdgeKind.dummy: | |
| json['kind'] = 'dummy'; | |
| break; | |
| } | |
| if (codeReference != null) json['code'] = codeReference.toJson(); | |
| if (description != null) json['description'] = description; | |
| serializer.defer(() { | |
| json['dest'] = serializer.idForNode(destinationNode); | |
| json['us'] = [for (var n in upstreamNodes) serializer.idForNode(n)]; | |
| }); | |
| return json; | |
| } | |
| @override | |
| String toString({NodeToIdMapper idMapper}) { | |
| var edgeDecorations = <Object>[]; | |
| switch (_kind) { | |
| case _NullabilityEdgeKind.soft: | |
| break; | |
| case _NullabilityEdgeKind.uncheckable: | |
| edgeDecorations.add('uncheckable'); | |
| break; | |
| case _NullabilityEdgeKind.hard: | |
| edgeDecorations.add('hard'); | |
| break; | |
| case _NullabilityEdgeKind.union: | |
| edgeDecorations.add('union'); | |
| break; | |
| case _NullabilityEdgeKind.dummy: | |
| edgeDecorations.add('dummy'); | |
| break; | |
| } | |
| edgeDecorations.addAll(guards); | |
| var edgeDecoration = | |
| edgeDecorations.isEmpty ? '' : '-(${edgeDecorations.join(', ')})'; | |
| return '${sourceNode.toString(idMapper: idMapper)} $edgeDecoration-> ' | |
| '${destinationNode.toString(idMapper: idMapper)}'; | |
| } | |
| static _NullabilityEdgeKind _deserializeKind(dynamic json) { | |
| if (json == null) return _NullabilityEdgeKind.soft; | |
| var kind = json as String; | |
| switch (kind) { | |
| case 'uncheckable': | |
| return _NullabilityEdgeKind.uncheckable; | |
| case 'hard': | |
| return _NullabilityEdgeKind.hard; | |
| case 'union': | |
| return _NullabilityEdgeKind.union; | |
| default: | |
| throw StateError('Unrecognized edge kind $kind'); | |
| } | |
| } | |
| } | |
| /// Data structure to keep track of the relationship between [NullabilityNode] | |
| /// objects. | |
| class NullabilityGraph { | |
| /// Set this const to `true` to dump the nullability graph just before | |
| /// propagation. | |
| static const _debugBeforePropagation = false; | |
| /// Set this const to `true` to dump the nullability graph just before | |
| /// propagation. | |
| static const _debugAfterPropagation = false; | |
| final NullabilityMigrationInstrumentation /*?*/ instrumentation; | |
| /// Returns a [NullabilityNode] that is a priori nullable. | |
| /// | |
| /// Propagation of nullability always proceeds downstream starting at this | |
| /// node. | |
| final NullabilityNode always; | |
| /// Returns a [NullabilityNode] that is a priori non-nullable. | |
| /// | |
| /// Propagation of nullability always proceeds upstream starting at this | |
| /// node. | |
| final NullabilityNode never; | |
| /// Set containing all sources being migrated. | |
| final _sourcesBeingMigrated = <Source>{}; | |
| /// A set containing all of the nodes in the graph. | |
| final Set<NullabilityNode> nodes = {}; | |
| NullabilityGraph({this.instrumentation}) | |
| : always = _NullabilityNodeImmutable('always', true), | |
| never = _NullabilityNodeImmutable('never', false); | |
| NullabilityGraph.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : instrumentation = null, | |
| always = deserializer.nodeForId(json['always'] as int), | |
| never = deserializer.nodeForId(json['never'] as int) { | |
| var serializedNodes = json['nodes'] as List<dynamic>; | |
| for (int id = 0; id < serializedNodes.length; id++) { | |
| nodes.add(deserializer.nodeForId(id)); | |
| } | |
| deserializer.finish(); | |
| } | |
| /// Records that [sourceNode] is immediately upstream from [destinationNode]. | |
| /// | |
| /// Returns the edge created by the connection. | |
| NullabilityEdge connect(NullabilityNode sourceNode, | |
| NullabilityNode destinationNode, EdgeOrigin origin, | |
| {bool hard: false, | |
| bool checkable = true, | |
| List<NullabilityNode> guards: const []}) { | |
| var upstreamNodes = [sourceNode]..addAll(guards); | |
| var kind = hard | |
| ? _NullabilityEdgeKind.hard | |
| : checkable | |
| ? _NullabilityEdgeKind.soft | |
| : _NullabilityEdgeKind.uncheckable; | |
| return _connect(upstreamNodes, destinationNode, kind, origin); | |
| } | |
| /// Records that [sourceNode] is immediately upstream from [always], via a | |
| /// dummy edge. | |
| NullabilityEdge connectDummy(NullabilityNode sourceNode, EdgeOrigin origin) => | |
| _connect([sourceNode], always, _NullabilityEdgeKind.dummy, origin); | |
| /// Prints out a representation of the graph nodes. Useful in debugging | |
| /// broken tests. | |
| void debugDump() { | |
| Set<NullabilityNode> visitedNodes = {}; | |
| Map<NullabilityNode, String> shortNames = {}; | |
| int counter = 0; | |
| String nameNode(NullabilityNode node) { | |
| if (node.isImmutable) { | |
| var name = 'n${counter++}'; | |
| print(' $name [label="$node" shape=none]'); | |
| return name; | |
| } | |
| var name = shortNames[node]; | |
| if (name == null) { | |
| shortNames[node] = name = 'n${counter++}'; | |
| String styleSuffix = node.isNullable ? ' style=filled' : ''; | |
| String intentSuffix = | |
| node.nonNullIntent.isPresent ? ', non-null intent' : ''; | |
| String label = '$node (${node._nullability}$intentSuffix)'; | |
| print(' $name [label="$label"$styleSuffix]'); | |
| if (node is NullabilityNodeCompound) { | |
| for (var component in node._components) { | |
| print(' ${nameNode(component)} -> $name [style=dashed]'); | |
| } | |
| } | |
| } | |
| return name; | |
| } | |
| void visitNode(NullabilityNode node) { | |
| if (!visitedNodes.add(node)) return; | |
| for (var edge in node._upstreamEdges) { | |
| String suffix; | |
| if (edge.isUnion) { | |
| suffix = ' [label="union"]'; | |
| } else if (edge.isHard) { | |
| suffix = ' [label="hard"]'; | |
| } else if (edge.isCheckable) { | |
| suffix = ''; | |
| } else { | |
| suffix = ' [label="uncheckable"]'; | |
| } | |
| var upstreamNodes = edge.upstreamNodes; | |
| if (upstreamNodes.length == 1) { | |
| print( | |
| ' ${nameNode(upstreamNodes.single)} -> ${nameNode(node)}$suffix'); | |
| } else { | |
| var tmpName = 'n${counter++}'; | |
| print(' $tmpName [label=""]'); | |
| print(' $tmpName -> ${nameNode(node)}$suffix}'); | |
| for (var upstreamNode in upstreamNodes) { | |
| print(' ${nameNode(upstreamNode)} -> $tmpName'); | |
| } | |
| } | |
| } | |
| } | |
| print('digraph G {'); | |
| print(' rankdir="LR"'); | |
| visitNode(always); | |
| visitNode(never); | |
| for (var node in nodes) { | |
| visitNode(node); | |
| } | |
| print('}'); | |
| } | |
| /// Determine if [source] is in the code being migrated. | |
| bool isBeingMigrated(Source source) { | |
| return _sourcesBeingMigrated.contains(source); | |
| } | |
| /// Creates a graph edge that will try to force the given [node] to be | |
| /// non-nullable. | |
| NullabilityEdge makeNonNullable(NullabilityNode node, EdgeOrigin origin, | |
| {bool hard: true, List<NullabilityNode> guards: const []}) { | |
| return connect(node, never, origin, hard: hard, guards: guards); | |
| } | |
| /// Creates union edges that will guarantee that the given [node] is | |
| /// non-nullable. | |
| void makeNonNullableUnion(NullabilityNode node, EdgeOrigin origin) { | |
| union(node, never, origin); | |
| } | |
| /// Creates a graph edge that will try to force the given [node] to be | |
| /// nullable. | |
| void makeNullable(NullabilityNode node, EdgeOrigin origin, | |
| {List<NullabilityNode> guards: const []}) { | |
| connect(always, node, origin, guards: guards); | |
| } | |
| /// Creates a `union` graph edge that will try to force the given [node] to be | |
| /// nullable. This is a stronger signal than [makeNullable] (it overrides | |
| /// [makeNonNullable]). | |
| void makeNullableUnion(NullabilityNode node, EdgeOrigin origin) { | |
| union(always, node, origin); | |
| } | |
| /// Record source as code that is being migrated. | |
| void migrating(Source source) { | |
| _sourcesBeingMigrated.add(source); | |
| } | |
| /// Determines the nullability of each node in the graph by propagating | |
| /// nullability information from one node to another. | |
| PropagationResult propagate(PostmortemFileWriter postmortemFileWriter) { | |
| postmortemFileWriter?.clearPropagationSteps(); | |
| if (_debugBeforePropagation) debugDump(); | |
| var propagationState = | |
| _PropagationState(always, never, postmortemFileWriter).result; | |
| if (_debugAfterPropagation) debugDump(); | |
| return propagationState; | |
| } | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = <String, Object>{}; | |
| json['always'] = serializer.idForNode(always); | |
| json['never'] = serializer.idForNode(never); | |
| serializer.finish(); | |
| json['nodes'] = serializer.serializedNodes; | |
| json['edges'] = serializer.serializedEdges; | |
| return json; | |
| } | |
| /// Records that nodes [x] and [y] should have exactly the same nullability. | |
| void union(NullabilityNode x, NullabilityNode y, EdgeOrigin origin) { | |
| _connect([x], y, _NullabilityEdgeKind.union, origin); | |
| _connect([y], x, _NullabilityEdgeKind.union, origin); | |
| } | |
| /// Update the graph after an edge has been added or removed. | |
| void update(PostmortemFileWriter postmortemFileWriter) { | |
| // | |
| // Reset the state of the nodes. | |
| // | |
| // This is inefficient because we reset the state of some nodes more than | |
| // once, but not all nodes are reachable from both `never` and `always`, so | |
| // we need to traverse the graph from both directions. | |
| // | |
| for (var node in nodes) { | |
| node.resetState(); | |
| } | |
| // | |
| // Reset the state of the listener. | |
| // | |
| instrumentation.prepareForUpdate(); | |
| // | |
| // Re-run the propagation step. | |
| // | |
| propagate(postmortemFileWriter); | |
| } | |
| NullabilityEdge _connect( | |
| List<NullabilityNode> upstreamNodes, | |
| NullabilityNode destinationNode, | |
| _NullabilityEdgeKind kind, | |
| EdgeOrigin origin) { | |
| var isUninit = origin?.kind == EdgeOriginKind.fieldNotInitialized || | |
| origin?.kind == EdgeOriginKind.implicitNullInitializer || | |
| origin?.kind == EdgeOriginKind.uninitializedRead; | |
| var isSetupAssignment = | |
| origin is ExpressionChecksOrigin && origin.isSetupAssignment; | |
| var edge = NullabilityEdge._( | |
| destinationNode, upstreamNodes, kind, origin?.description, | |
| codeReference: origin?.codeReference, | |
| isUninit: isUninit, | |
| isSetupAssignment: isSetupAssignment); | |
| instrumentation?.graphEdge(edge, origin); | |
| for (var upstreamNode in upstreamNodes) { | |
| _connectDownstream(upstreamNode, edge); | |
| } | |
| destinationNode._upstreamEdges.add(edge); | |
| nodes.addAll(upstreamNodes); | |
| nodes.add(destinationNode); | |
| return edge; | |
| } | |
| void _connectDownstream(NullabilityNode upstreamNode, NullabilityEdge edge) { | |
| upstreamNode._downstreamEdges.add(edge); | |
| if (upstreamNode is NullabilityNodeCompound) { | |
| for (var component in upstreamNode._components) { | |
| _connectDownstream(component, edge); | |
| } | |
| } | |
| } | |
| } | |
| /// Helper object used to deserialize a nullability graph from a JSON | |
| /// representation. | |
| class NullabilityGraphDeserializer implements NodeToIdMapper { | |
| final List<dynamic> _serializedNodes; | |
| final List<dynamic> _serializedEdges; | |
| final Map<int, NullabilityNode> _idToNodeMap = {}; | |
| final Map<int, NullabilityEdge> _idToEdgeMap = {}; | |
| final List<void Function()> _deferred = []; | |
| final Map<NullabilityNode, int> _nodeToIdMap = {}; | |
| final Map<PropagationStep, int> _stepToIdMap = {}; | |
| final List<PropagationStep> _propagationSteps; | |
| NullabilityGraphDeserializer( | |
| this._serializedNodes, this._serializedEdges, this._propagationSteps); | |
| /// Defers a deserialization action until later. The nullability node | |
| /// `fromJson` constructors use this method to defer populating edge lists | |
| /// until all nodes have been deserialized. | |
| void defer(void Function() callback) { | |
| _deferred.add(callback); | |
| } | |
| /// Gets the edge having the given [id], deserializing it if it hasn't been | |
| /// deserialized already. | |
| NullabilityEdge edgeForId(int id) { | |
| var edge = _idToEdgeMap[id]; | |
| if (edge == null) { | |
| _idToEdgeMap[id] = | |
| edge = NullabilityEdge.fromJson(_serializedEdges[id], this); | |
| } | |
| return edge; | |
| } | |
| /// Runs all deferred actions that have been passed to [defer]. | |
| void finish() { | |
| while (_deferred.isNotEmpty) { | |
| var callback = _deferred.removeLast(); | |
| callback(); | |
| } | |
| } | |
| @override | |
| int idForNode(NullabilityNode node) => _nodeToIdMap[node]; | |
| /// Gets the node having the given [id], deserializing it if it hasn't been | |
| /// deserialized already. | |
| NullabilityNode nodeForId(int id) { | |
| var node = _idToNodeMap[id]; | |
| if (node == null) { | |
| _idToNodeMap[id] = node = _deserializeNode(id); | |
| _nodeToIdMap[node] = id; | |
| } | |
| return node; | |
| } | |
| /// Records that the given [step] was stored in the postmortem file with the | |
| /// given [id] number. | |
| void recordStepId(PropagationStep step, int id) { | |
| _stepToIdMap[step] = id; | |
| } | |
| /// Gets the propagation step having the given [id]. | |
| PropagationStep stepForId(int id) => | |
| id == null ? null : _propagationSteps[id]; | |
| NullabilityNode _deserializeNode(int id) { | |
| var json = _serializedNodes[id]; | |
| var kind = json['kind'] as String; | |
| switch (kind) { | |
| case 'immutable': | |
| return _NullabilityNodeImmutable.fromJson(json, this); | |
| case 'simple': | |
| return _NullabilityNodeSimple.fromJson(json, this); | |
| case 'lub': | |
| return NullabilityNodeForLUB.fromJson(json, this); | |
| case 'substitution': | |
| return NullabilityNodeForSubstitution.fromJson(json, this); | |
| default: | |
| throw StateError('Unrecognized node kind $kind'); | |
| } | |
| } | |
| } | |
| /// Same as [NullabilityGraph], but extended with extra methods for easier | |
| /// testing. | |
| @visibleForTesting | |
| class NullabilityGraphForTesting extends NullabilityGraph { | |
| final List<NullabilityEdge> _allEdges = []; | |
| final Map<NullabilityEdge, EdgeOrigin> _edgeOrigins = {}; | |
| /// Iterates through all edges in the graph. | |
| @visibleForTesting | |
| Iterable<NullabilityEdge> getAllEdges() { | |
| return _allEdges; | |
| } | |
| /// Retrieves the [EdgeOrigin] object that was used to create [edge]. | |
| @visibleForTesting | |
| EdgeOrigin getEdgeOrigin(NullabilityEdge edge) => _edgeOrigins[edge]; | |
| @override | |
| NullabilityEdge _connect( | |
| List<NullabilityNode> upstreamNodes, | |
| NullabilityNode destinationNode, | |
| _NullabilityEdgeKind kind, | |
| EdgeOrigin origin) { | |
| var edge = super._connect(upstreamNodes, destinationNode, kind, origin); | |
| _allEdges.add(edge); | |
| _edgeOrigins[edge] = origin; | |
| return edge; | |
| } | |
| } | |
| /// Helper object used to serialize a nullability graph into a JSON | |
| /// representation. | |
| class NullabilityGraphSerializer { | |
| /// The list of serialized node objects to be stored in the output JSON. | |
| final List<Map<String, Object>> serializedNodes = []; | |
| final Map<NullabilityNode, int> _nodeToIdMap = {}; | |
| /// The list of serialized edge objects to be stored in the output JSON. | |
| final List<Map<String, Object>> serializedEdges = []; | |
| final Map<NullabilityEdge, int> _edgeToIdMap = {}; | |
| final List<void Function()> _deferred = []; | |
| bool _serializingNodeOrEdge = false; | |
| final Map<PropagationStep, int> _stepToIdMap = {}; | |
| /// Defers a serialization action until later. The nullability node | |
| /// `toJson` methods use this method to defer serializing edge lists | |
| /// until all nodes have been serialized. | |
| void defer(void Function() callback) { | |
| _deferred.add(callback); | |
| } | |
| /// Runs all deferred actions that have been passed to [defer]. | |
| void finish() { | |
| while (_deferred.isNotEmpty) { | |
| var callback = _deferred.removeLast(); | |
| callback(); | |
| } | |
| } | |
| /// Gets the id for the given [edge], serializing it if it hasn't been | |
| /// serialized already. | |
| int idForEdge(NullabilityEdge edge) { | |
| var result = _edgeToIdMap[edge]; | |
| if (result == null) { | |
| if (_serializingNodeOrEdge) { | |
| throw StateError('Illegal nesting of idForEdge'); | |
| } | |
| _serializingNodeOrEdge = true; | |
| assert(_edgeToIdMap.length == serializedEdges.length); | |
| result = _edgeToIdMap[edge] = _edgeToIdMap.length; | |
| serializedEdges.add(edge.toJson(this)); | |
| _serializingNodeOrEdge = false; | |
| } | |
| return result; | |
| } | |
| /// Gets the id for the given [node], serializing it if it hasn't been | |
| /// serialized already. | |
| int idForNode(NullabilityNode node) { | |
| var result = _nodeToIdMap[node]; | |
| if (result == null) { | |
| if (_serializingNodeOrEdge) { | |
| throw StateError('Illegal nesting of idForEdge'); | |
| } | |
| _serializingNodeOrEdge = true; | |
| assert(_nodeToIdMap.length == serializedNodes.length); | |
| result = _nodeToIdMap[node] = _nodeToIdMap.length; | |
| serializedNodes.add(node.toJson(this)); | |
| _serializingNodeOrEdge = false; | |
| } | |
| return result; | |
| } | |
| int idForStep(PropagationStep step) => _stepToIdMap[step]; | |
| void recordStepId(PropagationStep step, int id) { | |
| _stepToIdMap[step] = id; | |
| } | |
| } | |
| /// Representation of a single node in the nullability inference graph. | |
| /// | |
| /// Initially, this is just a wrapper over constraint variables, and the | |
| /// nullability inference graph is encoded into the wrapped constraint | |
| /// variables. Over time this will be replaced by a first class representation | |
| /// of the nullability inference graph. | |
| abstract class NullabilityNode implements NullabilityNodeInfo { | |
| LateCondition _lateCondition = LateCondition.notLate; | |
| bool _isPossiblyOptional = false; | |
| /// List of [NullabilityEdge] objects describing this node's relationship to | |
| /// other nodes that are "downstream" from it (meaning that if a key node is | |
| /// nullable, then all the nodes in the corresponding value will either have | |
| /// to be nullable, or null checks will have to be added). | |
| final _downstreamEdges = <NullabilityEdge>[]; | |
| /// List of edges that have this node as their destination. | |
| final _upstreamEdges = <NullabilityEdge>[]; | |
| /// List of compound nodes wrapping this node. | |
| final List<NullabilityNodeCompound> outerCompoundNodes = | |
| <NullabilityNodeCompound>[]; | |
| /// Creates a [NullabilityNode] representing the nullability of a variable | |
| /// whose type comes from an already-migrated library. | |
| factory NullabilityNode.forAlreadyMigrated(NullabilityNodeTarget target) => | |
| _NullabilityNodeSimple(target); | |
| /// Creates a [NullabilityNode] representing the nullability of an expression | |
| /// which is nullable iff two other nullability nodes are both nullable. | |
| /// | |
| /// The caller is required to create the appropriate graph edges to ensure | |
| /// that the appropriate relationship between the nodes' nullabilities holds. | |
| factory NullabilityNode.forGLB() => _NullabilityNodeSimple( | |
| NullabilityNodeTarget.text('(greatest lower bound)')); | |
| /// Creates a [NullabilityNode] representing the nullability of a variable | |
| /// whose type is determined by the `??` operator. | |
| factory NullabilityNode.forIfNotNull(AstNode node) => _NullabilityNodeSimple( | |
| NullabilityNodeTarget.text('?? operator').withCodeRef(node)); | |
| /// Creates a [NullabilityNode] representing the nullability of a variable | |
| /// whose type is determined by type inference. | |
| factory NullabilityNode.forInferredType(NullabilityNodeTarget target) => | |
| _NullabilityNodeSimple(target); | |
| /// Creates a [NullabilityNode] representing the nullability of an | |
| /// expression which is nullable iff either [a] or [b] is nullable. | |
| factory NullabilityNode.forLUB(NullabilityNode left, NullabilityNode right) = | |
| NullabilityNodeForLUB._; | |
| /// Creates a [NullabilityNode] representing the nullability of a type | |
| /// substitution where [outerNode] is the nullability node for the type | |
| /// variable being eliminated by the substitution, and [innerNode] is the | |
| /// nullability node for the type being substituted in its place. | |
| /// | |
| /// If either [innerNode] or [outerNode] is `null`, then the other node is | |
| /// returned. | |
| factory NullabilityNode.forSubstitution( | |
| NullabilityNode innerNode, NullabilityNode outerNode) { | |
| if (innerNode == null) return outerNode; | |
| if (outerNode == null) return innerNode; | |
| return NullabilityNodeForSubstitution._(innerNode, outerNode); | |
| } | |
| /// Creates a [NullabilityNode] representing the nullability of a type | |
| /// annotation appearing explicitly in the user's program. | |
| factory NullabilityNode.forTypeAnnotation(NullabilityNodeTarget target) => | |
| _NullabilityNodeSimple(target); | |
| NullabilityNode.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) { | |
| deserializer.defer(() { | |
| if (json['isPossiblyOptional'] == true) { | |
| _isPossiblyOptional = true; | |
| } | |
| for (var id in json['ds'] ?? []) { | |
| _downstreamEdges.add(deserializer.edgeForId(id as int)); | |
| } | |
| for (var id in json['us'] ?? []) { | |
| _upstreamEdges.add(deserializer.edgeForId(id as int)); | |
| } | |
| for (var id in json['outerCompoundNodes'] ?? []) { | |
| outerCompoundNodes | |
| .add(deserializer.nodeForId(id as int) as NullabilityNodeCompound); | |
| } | |
| }); | |
| } | |
| NullabilityNode._(); | |
| @override | |
| CodeReference get codeReference => null; | |
| /// Gets a string that can be appended to a type name during debugging to help | |
| /// annotate the nullability of that type. | |
| String get debugSuffix => '?($this)'; | |
| /// Gets a name for the nullability node that is suitable for display to the | |
| /// user. | |
| String get displayName; | |
| Iterable<EdgeInfo> get downstreamEdges => _downstreamEdges; | |
| /// After nullability propagation, this getter can be used to query whether | |
| /// the type associated with this node should be considered "exact nullable". | |
| @visibleForTesting | |
| bool get isExactNullable; | |
| /// After nullability propagation, this getter can be used to query whether | |
| /// the type associated with this node should be considered nullable. | |
| @override | |
| bool get isNullable; | |
| /// Indicates whether this node is associated with a named parameter for which | |
| /// nullability migration needs to decide whether it is optional or required. | |
| bool get isPossiblyOptional => _isPossiblyOptional; | |
| /// Indicates whether this node is associated with a variable declaration | |
| /// which should be annotated with "late". | |
| LateCondition get lateCondition => _lateCondition; | |
| /// After nullability propagation, this getter can be used to query the node's | |
| /// non-null intent state. | |
| NonNullIntent get nonNullIntent; | |
| @override | |
| Iterable<EdgeInfo> get upstreamEdges => _upstreamEdges; | |
| @override | |
| UpstreamPropagationStep get whyNotNullable; | |
| String get _jsonKind; | |
| Nullability get _nullability; | |
| /// Records the fact that an invocation was made to a function with named | |
| /// parameters, and the named parameter associated with this node was not | |
| /// supplied. | |
| void recordNamedParameterNotSupplied(List<NullabilityNode> guards, | |
| NullabilityGraph graph, NamedParameterNotSuppliedOrigin origin) { | |
| if (isPossiblyOptional) { | |
| graph.connect(graph.always, this, origin, guards: guards); | |
| } | |
| } | |
| /// Reset the state of this node to what it was before the graph was solved. | |
| void resetState(); | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = <String, Object>{}; | |
| json['kind'] = _jsonKind; | |
| if (_isPossiblyOptional) { | |
| json['isPossiblyOptional'] = true; | |
| } | |
| serializer.defer(() { | |
| if (_downstreamEdges.isNotEmpty) { | |
| json['ds'] = [for (var e in _downstreamEdges) serializer.idForEdge(e)]; | |
| } | |
| if (_upstreamEdges.isNotEmpty) { | |
| json['us'] = [for (var e in _upstreamEdges) serializer.idForEdge(e)]; | |
| } | |
| if (outerCompoundNodes.isNotEmpty) { | |
| json['outerCompoundNodes'] = [ | |
| for (var e in outerCompoundNodes) serializer.idForNode(e) | |
| ]; | |
| } | |
| }); | |
| return json; | |
| } | |
| String toString({NodeToIdMapper idMapper}) { | |
| var name = displayName; | |
| if (idMapper == null) { | |
| return name; | |
| } else { | |
| return '${idMapper.idForNode(this)}: $name'; | |
| } | |
| } | |
| /// Tracks the possibility that this node is associated with a named parameter | |
| /// for which nullability migration needs to decide whether it is optional or | |
| /// required. | |
| void trackPossiblyOptional() { | |
| _isPossiblyOptional = true; | |
| } | |
| } | |
| /// Base class for nullability nodes that are nullable if at least one of a set | |
| /// of other nodes is nullable, and non-nullable otherwise; the set of other | |
| /// nodes are called "components". | |
| abstract class NullabilityNodeCompound extends NullabilityNodeMutable { | |
| NullabilityNodeCompound() : super._(); | |
| NullabilityNodeCompound.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : super.fromJson(json, deserializer); | |
| /// A map describing each of the node's components by name. | |
| Map<String, NullabilityNode> get componentsByName; | |
| @override | |
| bool get isExactNullable => _components.any((c) => c.isExactNullable); | |
| @override | |
| bool get isNullable => _components.any((c) => c.isNullable); | |
| Iterable<NullabilityNode> get _components; | |
| } | |
| /// Derived class for nullability nodes that arise from the least-upper-bound | |
| /// implied by a conditional expression. | |
| class NullabilityNodeForLUB extends NullabilityNodeCompound { | |
| final NullabilityNode left; | |
| final NullabilityNode right; | |
| NullabilityNodeForLUB.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : left = deserializer.nodeForId(json['left'] as int), | |
| right = deserializer.nodeForId(json['right'] as int), | |
| super.fromJson(json, deserializer); | |
| NullabilityNodeForLUB._(this.left, this.right) { | |
| left.outerCompoundNodes.add(this); | |
| right.outerCompoundNodes.add(this); | |
| } | |
| @override | |
| Map<String, NullabilityNode> get componentsByName => | |
| {'left': left, 'right': right}; | |
| @override | |
| String get displayName => '${left.displayName} or ${right.displayName}'; | |
| @override | |
| Iterable<NullabilityNode> get _components => [left, right]; | |
| @override | |
| String get _jsonKind => 'lub'; | |
| @override | |
| void resetState() { | |
| left.resetState(); | |
| right.resetState(); | |
| } | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| serializer.defer(() { | |
| json['left'] = serializer.idForNode(left); | |
| json['right'] = serializer.idForNode(right); | |
| }); | |
| return json; | |
| } | |
| } | |
| /// Derived class for nullability nodes that arise from type variable | |
| /// substitution. | |
| class NullabilityNodeForSubstitution extends NullabilityNodeCompound | |
| implements SubstitutionNodeInfo { | |
| @override | |
| final NullabilityNode innerNode; | |
| @override | |
| final NullabilityNode outerNode; | |
| NullabilityNodeForSubstitution.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : innerNode = deserializer.nodeForId(json['inner'] as int), | |
| outerNode = deserializer.nodeForId(json['outer'] as int), | |
| super.fromJson(json, deserializer); | |
| NullabilityNodeForSubstitution._(this.innerNode, this.outerNode) { | |
| innerNode.outerCompoundNodes.add(this); | |
| outerNode.outerCompoundNodes.add(this); | |
| } | |
| @override | |
| Map<String, NullabilityNode> get componentsByName => | |
| {'inner': innerNode, 'outer': outerNode}; | |
| @override | |
| String get displayName => | |
| '${innerNode.displayName} or ${outerNode.displayName}'; | |
| @override | |
| Iterable<NullabilityNode> get _components => [innerNode, outerNode]; | |
| @override | |
| String get _jsonKind => 'substitution'; | |
| @override | |
| void resetState() { | |
| innerNode.resetState(); | |
| outerNode.resetState(); | |
| } | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| serializer.defer(() { | |
| json['inner'] = serializer.idForNode(innerNode); | |
| json['outer'] = serializer.idForNode(outerNode); | |
| }); | |
| return json; | |
| } | |
| } | |
| /// Base class for nullability nodes whose state can be mutated safely. | |
| /// | |
| /// Nearly all nullability nodes derive from this class; the only exceptions are | |
| /// the fixed nodes "always "never". | |
| abstract class NullabilityNodeMutable extends NullabilityNode { | |
| Nullability _nullability; | |
| NonNullIntent _nonNullIntent; | |
| DownstreamPropagationStep _whyNullable; | |
| UpstreamPropagationStep _whyNotNullable; | |
| NullabilityNodeMutable.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : _nullability = json['nullability'] == null | |
| ? Nullability.nonNullable | |
| : Nullability.fromJson(json['nullability']), | |
| _nonNullIntent = json['nonNullIntent'] == null | |
| ? NonNullIntent.none | |
| : NonNullIntent.fromJson(json['nonNullIntent']), | |
| super.fromJson(json, deserializer); | |
| NullabilityNodeMutable._( | |
| {Nullability initialNullability = Nullability.nonNullable}) | |
| : _nullability = initialNullability, | |
| _nonNullIntent = NonNullIntent.none, | |
| super._(); | |
| @override | |
| bool get isExactNullable => _nullability.isExactNullable; | |
| @override | |
| bool get isImmutable => false; | |
| @override | |
| bool get isNullable => _nullability.isNullable; | |
| @override | |
| NonNullIntent get nonNullIntent => _nonNullIntent; | |
| @override | |
| UpstreamPropagationStep get whyNotNullable => _whyNotNullable; | |
| @override | |
| DownstreamPropagationStepInfo get whyNullable => _whyNullable; | |
| @override | |
| void resetState() { | |
| _nullability = Nullability.nonNullable; | |
| _nonNullIntent = NonNullIntent.none; | |
| _whyNullable = null; | |
| } | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| if (_nullability != Nullability.nonNullable) { | |
| json['nullability'] = _nullability.toJson(); | |
| } | |
| if (_nonNullIntent != NonNullIntent.none) { | |
| json['intent'] = _nonNullIntent.toJson(); | |
| } | |
| return json; | |
| } | |
| } | |
| /// Information produced by [NullabilityGraph.propagate] about the results of | |
| /// graph propagation. | |
| class PropagationResult { | |
| /// A list of all edges that couldn't be satisfied. May contain duplicates. | |
| final List<NullabilityEdge> unsatisfiedEdges = []; | |
| /// A list of all substitution nodes that couldn't be satisfied. | |
| final List<NullabilityNodeForSubstitution> unsatisfiedSubstitutions = []; | |
| PropagationResult._(); | |
| } | |
| /// Class representing a step taken by the nullability propagation algorithm. | |
| abstract class PropagationStep implements PropagationStepInfo { | |
| PropagationStep(); | |
| factory PropagationStep.fromJson( | |
| json, NullabilityGraphDeserializer deserializer) { | |
| var kind = json['kind'] as String; | |
| switch (kind) { | |
| case 'downstream': | |
| return SimpleDownstreamPropagationStep.fromJson(json, deserializer); | |
| case 'exact': | |
| return SimpleExactNullablePropagationStep.fromJson(json, deserializer); | |
| case 'resolveSubstitution': | |
| return ResolveSubstitutionPropagationStep.fromJson(json, deserializer); | |
| case 'upstream': | |
| return UpstreamPropagationStep.fromJson(json, deserializer); | |
| default: | |
| throw StateError('Unrecognized propagation step kind: $kind'); | |
| } | |
| } | |
| /// The location in the source code that caused this step to be necessary, | |
| /// or `null` if not known. | |
| CodeReference get codeReference => null; | |
| /// The previous propagation step that led to this one, or `null` if there was | |
| /// no previous step. | |
| PropagationStep get principalCause; | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer); | |
| @override | |
| String toString({NodeToIdMapper idMapper}); | |
| } | |
| /// Propagation step where we consider mark one of the components of a | |
| /// substitution node as nullable because the substitution node itself is | |
| /// nullable. | |
| class ResolveSubstitutionPropagationStep extends ExactNullablePropagationStep { | |
| @override | |
| final DownstreamPropagationStep principalCause; | |
| /// The substitution node that needed resolution. | |
| final NullabilityNodeForSubstitution node; | |
| ResolveSubstitutionPropagationStep(this.principalCause, this.node); | |
| ResolveSubstitutionPropagationStep.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : principalCause = deserializer.stepForId(json['cause'] as int) | |
| as DownstreamPropagationStep, | |
| node = deserializer.nodeForId(json['node'] as int) | |
| as NullabilityNodeForSubstitution, | |
| super.fromJson(json, deserializer); | |
| @override | |
| EdgeInfo get edge => null; | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| json['kind'] = 'resolveSubstitution'; | |
| json['cause'] = serializer.idForStep(principalCause); | |
| json['node'] = serializer.idForNode(node); | |
| return json; | |
| } | |
| @override | |
| String toString({NodeToIdMapper idMapper}) => | |
| '${targetNode.toString(idMapper: idMapper)} becomes $newState due to ' | |
| '${node.toString(idMapper: idMapper)}'; | |
| } | |
| /// Propagation step where we mark the destination of an edge as nullable, due | |
| /// to its sources becoming nullable. | |
| class SimpleDownstreamPropagationStep extends DownstreamPropagationStep { | |
| @override | |
| final DownstreamPropagationStep principalCause; | |
| @override | |
| final NullabilityEdge edge; | |
| SimpleDownstreamPropagationStep(this.principalCause, this.edge); | |
| SimpleDownstreamPropagationStep.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : principalCause = deserializer.stepForId(json['cause'] as int) | |
| as DownstreamPropagationStep, | |
| edge = deserializer.edgeForId(json['edge'] as int), | |
| super.fromJson(json, deserializer); | |
| @override | |
| CodeReference get codeReference => edge.codeReference; | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| json['kind'] = 'downstream'; | |
| json['cause'] = serializer.idForStep(principalCause); | |
| json['edge'] = serializer.idForEdge(edge); | |
| return json; | |
| } | |
| @override | |
| String toString({NodeToIdMapper idMapper}) => | |
| '${targetNode.toString(idMapper: idMapper)} becomes $newState due to ' | |
| '${edge.toString(idMapper: idMapper)}'; | |
| } | |
| /// Propagation step where we mark the source of an edge as exact nullable, due | |
| /// to its destination becoming exact nullable. | |
| class SimpleExactNullablePropagationStep extends ExactNullablePropagationStep { | |
| @override | |
| final ExactNullablePropagationStep principalCause; | |
| @override | |
| final NullabilityEdge edge; | |
| SimpleExactNullablePropagationStep(this.principalCause, this.edge); | |
| SimpleExactNullablePropagationStep.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : principalCause = deserializer.stepForId(json['cause'] as int) | |
| as ExactNullablePropagationStep, | |
| edge = deserializer.edgeForId(json['edge'] as int), | |
| super.fromJson(json, deserializer); | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| json['kind'] = 'exact'; | |
| json['cause'] = serializer.idForStep(principalCause); | |
| json['edge'] = serializer.idForEdge(edge); | |
| return json; | |
| } | |
| @override | |
| String toString({NodeToIdMapper idMapper}) => | |
| '${targetNode.toString(idMapper: idMapper)} becomes $newState due to ' | |
| '${edge.toString(idMapper: idMapper)}'; | |
| } | |
| /// Propagation step where we mark a node as having non-null intent due to it | |
| /// being upstream from another node with non-null intent. | |
| class UpstreamPropagationStep extends PropagationStep | |
| implements UpstreamPropagationStepInfo { | |
| @override | |
| final UpstreamPropagationStep principalCause; | |
| /// The node being marked as having non-null intent. | |
| final NullabilityNode node; | |
| /// The new state of the node's non-null intent. | |
| final NonNullIntent newNonNullIntent; | |
| /// The nullability edge connecting [node] to the node it is upstream from, if | |
| /// any. | |
| final NullabilityEdge edge; | |
| UpstreamPropagationStep( | |
| this.principalCause, this.node, this.newNonNullIntent, this.edge); | |
| UpstreamPropagationStep.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : principalCause = deserializer.stepForId(json['cause'] as int) | |
| as UpstreamPropagationStep, | |
| node = deserializer.nodeForId(json['node'] as int), | |
| newNonNullIntent = NonNullIntent.fromJson(json['newState']), | |
| edge = deserializer.edgeForId(json['edge'] as int); | |
| @override | |
| CodeReference get codeReference => edge?.codeReference; | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| return { | |
| 'kind': 'upstream', | |
| 'cause': serializer.idForStep(principalCause), | |
| 'node': serializer.idForNode(node), | |
| 'newState': newNonNullIntent.toJson(), | |
| 'edge': serializer.idForEdge(edge) | |
| }; | |
| } | |
| @override | |
| String toString({NodeToIdMapper idMapper}) => | |
| '${node.toString(idMapper: idMapper)} becomes $newNonNullIntent'; | |
| } | |
| /// Kinds of nullability edges | |
| enum _NullabilityEdgeKind { | |
| /// Soft edge. Propagates nullability downstream only. May be overridden by | |
| /// suggestions that the user intends non-nullability. | |
| soft, | |
| /// Uncheckable edge. Propagates nullability downstream only. May not be | |
| /// overridden by suggestions that the user intends non-nullability. | |
| uncheckable, | |
| /// Hard edge. Propagates nullability downstream and non-nullability | |
| /// upstream. | |
| hard, | |
| /// Union edge. Indicates that two nodes should have exactly the same | |
| /// nullability. | |
| union, | |
| /// Dummy edge. Indicates that two edges are connected in a way that should | |
| /// not propagate (non-)nullability in either direction. | |
| dummy, | |
| } | |
| class _NullabilityNodeImmutable extends NullabilityNode { | |
| @override | |
| final String displayName; | |
| @override | |
| final bool isNullable; | |
| _NullabilityNodeImmutable(this.displayName, this.isNullable) : super._(); | |
| _NullabilityNodeImmutable.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : displayName = json['displayName'] as String, | |
| isNullable = json['isNullable'] as bool, | |
| super.fromJson(json, deserializer); | |
| @override | |
| String get debugSuffix => isNullable ? '?' : ''; | |
| @override | |
| // Note: the node "always" is not exact nullable, because exact nullability is | |
| // a concept for contravariant generics which propagates upstream instead of | |
| // downstream. "always" is not a contravariant generic, and does not have any | |
| // upstream nodes, so it should not be considered *exact* nullable. | |
| bool get isExactNullable => false; | |
| @override | |
| bool get isImmutable => true; | |
| @override | |
| NonNullIntent get nonNullIntent => | |
| isNullable ? NonNullIntent.none : NonNullIntent.direct; | |
| @override | |
| UpstreamPropagationStep get whyNotNullable => null; | |
| @override | |
| DownstreamPropagationStepInfo get whyNullable => null; | |
| @override | |
| String get _jsonKind => 'immutable'; | |
| @override | |
| Nullability get _nullability => | |
| isNullable ? Nullability.ordinaryNullable : Nullability.nonNullable; | |
| @override | |
| void resetState() { | |
| // There is no state to reset. | |
| } | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| json['displayName'] = displayName; | |
| json['isNullable'] = isNullable; | |
| return json; | |
| } | |
| } | |
| class _NullabilityNodeSimple extends NullabilityNodeMutable { | |
| final NullabilityNodeTarget target; | |
| _NullabilityNodeSimple(this.target) : super._(); | |
| _NullabilityNodeSimple.fromJson( | |
| dynamic json, NullabilityGraphDeserializer deserializer) | |
| : target = | |
| NullabilityNodeTarget.text(json['targetDisplayName'] as String), | |
| super.fromJson(json, deserializer); | |
| @override | |
| CodeReference get codeReference => target.codeReference; | |
| @override | |
| String get displayName => target.displayName; | |
| @override | |
| String get _jsonKind => 'simple'; | |
| @override | |
| Map<String, Object> toJson(NullabilityGraphSerializer serializer) { | |
| var json = super.toJson(serializer); | |
| json['targetDisplayName'] = target.displayName; | |
| return json; | |
| } | |
| } | |
| /// Workspace for performing graph propagation. | |
| /// | |
| /// Graph propagation is performed immediately upon construction, so as soon as | |
| /// the caller has constructed this object, the graph has been propagated and | |
| /// the results of propagation can be retrieved from [result]. | |
| class _PropagationState { | |
| /// The result of propagation, for sharing with the client. | |
| final PropagationResult result = PropagationResult._(); | |
| /// The graph's one and only "always" node. | |
| final NullabilityNode _always; | |
| /// The graph's one and only "never" node. | |
| final NullabilityNode _never; | |
| /// During any given stage of nullability propagation, a queue of all the | |
| /// edges that need to be examined before the stage is complete. | |
| final Queue<SimpleDownstreamPropagationStep> _pendingDownstreamSteps = | |
| Queue(); | |
| final PostmortemFileWriter _postmortemFileWriter; | |
| /// During execution of [_propagateDownstream], a list of all the substitution | |
| /// nodes that have not yet been resolved. | |
| List<ResolveSubstitutionPropagationStep> _pendingSubstitutions = []; | |
| _PropagationState(this._always, this._never, this._postmortemFileWriter) { | |
| _propagateUpstream(); | |
| _propagateDownstream(); | |
| } | |
| /// Propagates nullability downstream. | |
| void _propagateDownstream() { | |
| assert(_pendingDownstreamSteps.isEmpty); | |
| for (var edge in _always._downstreamEdges) { | |
| _pendingDownstreamSteps.add(SimpleDownstreamPropagationStep(null, edge)); | |
| } | |
| while (true) { | |
| while (_pendingDownstreamSteps.isNotEmpty) { | |
| var step = _pendingDownstreamSteps.removeFirst(); | |
| var edge = step.edge; | |
| if (!edge.isTriggered) continue; | |
| var node = edge.destinationNode; | |
| var nonNullIntent = node.nonNullIntent; | |
| if (nonNullIntent.isPresent) { | |
| if (edge.isCheckable) { | |
| // The node has already been marked as having non-null intent, and | |
| // the edge can be addressed by adding a null check, so we prefer to | |
| // leave the edge unsatisfied and let the null check happen. | |
| result.unsatisfiedEdges.add(edge); | |
| continue; | |
| } | |
| if (nonNullIntent.isDirect) { | |
| // The node has direct non-null intent so we aren't in a position to | |
| // mark it as nullable. | |
| result.unsatisfiedEdges.add(edge); | |
| continue; | |
| } | |
| } | |
| if (edge.isUninit && !node.isNullable) { | |
| // [edge] is an edge from always to an uninitialized variable | |
| // declaration. | |
| var isSetupAssigned = node.upstreamEdges | |
| .any((e) => e is NullabilityEdge && e.isSetupAssignment); | |
| // Whether all downstream edges go to nodes with non-null intent. | |
| var allDownstreamHaveNonNullIntent = false; | |
| if (node.downstreamEdges.isNotEmpty) { | |
| allDownstreamHaveNonNullIntent = node.downstreamEdges.every((e) { | |
| var destination = e.destinationNode; | |
| return destination is NullabilityNode && | |
| destination.nonNullIntent.isPresent; | |
| }); | |
| } | |
| if (allDownstreamHaveNonNullIntent) { | |
| node._lateCondition = LateCondition.possiblyLate; | |
| continue; | |
| } else if (isSetupAssigned) { | |
| node._lateCondition = LateCondition.possiblyLateDueToTestSetup; | |
| continue; | |
| } | |
| } | |
| if (node is NullabilityNodeMutable && !node.isNullable) { | |
| assert(step.targetNode == null); | |
| step.targetNode = node; | |
| step.newState = Nullability.ordinaryNullable; | |
| _setNullable(step); | |
| node._lateCondition = LateCondition.notLate; | |
| } | |
| } | |
| if (_pendingSubstitutions.isEmpty) break; | |
| var oldPendingSubstitutions = _pendingSubstitutions; | |
| _pendingSubstitutions = []; | |
| for (var step in oldPendingSubstitutions) { | |
| _resolvePendingSubstitution(step); | |
| } | |
| } | |
| } | |
| /// Propagates non-null intent upstream along unconditional control flow | |
| /// lines. | |
| void _propagateUpstream() { | |
| Queue<UpstreamPropagationStep> pendingSteps = Queue(); | |
| pendingSteps | |
| .add(UpstreamPropagationStep(null, _never, NonNullIntent.direct, null)); | |
| while (pendingSteps.isNotEmpty) { | |
| var cause = pendingSteps.removeFirst(); | |
| var pendingNode = cause.node; | |
| for (var edge in pendingNode._upstreamEdges) { | |
| // We only propagate for nodes that are "upstream triggered". At this | |
| // point of propagation, a node is upstream triggered if it is hard. | |
| assert(edge.isUpstreamTriggered == edge.isHard); | |
| if (!edge.isHard) continue; | |
| var node = edge.sourceNode; | |
| if (node is NullabilityNodeMutable) { | |
| var oldNonNullIntent = node._nonNullIntent; | |
| NonNullIntent newNonNullIntent; | |
| if (edge.isUnion && edge.destinationNode == _never) { | |
| // If a node is unioned with "never" then it's considered to have | |
| // direct non-null intent. | |
| newNonNullIntent = NonNullIntent.direct; | |
| } else { | |
| newNonNullIntent = oldNonNullIntent.addIndirect(); | |
| } | |
| var step = | |
| UpstreamPropagationStep(cause, node, newNonNullIntent, edge); | |
| _setNonNullIntent(step); | |
| if (!oldNonNullIntent.isPresent) { | |
| // We did not previously have non-null intent, so we need to | |
| // propagate. | |
| pendingSteps.add(step); | |
| } | |
| } | |
| } | |
| // If any compound node is forced to be non-nullable by this change, | |
| // propagate to it. | |
| for (var node in pendingNode.outerCompoundNodes) { | |
| if (node._components | |
| .any((component) => !component.nonNullIntent.isPresent)) { | |
| continue; | |
| } | |
| var oldNonNullIntent = node._nonNullIntent; | |
| var newNonNullIntent = oldNonNullIntent.addIndirect(); | |
| var step = UpstreamPropagationStep(cause, node, newNonNullIntent, null); | |
| _setNonNullIntent(step); | |
| if (!oldNonNullIntent.isPresent) { | |
| // We did not previously have non-null intent, so we need to | |
| // propagate. | |
| pendingSteps.add(step); | |
| } | |
| } | |
| } | |
| } | |
| void _resolvePendingSubstitution(ResolveSubstitutionPropagationStep step) { | |
| NullabilityNodeForSubstitution substitutionNode = step.node; | |
| assert(substitutionNode._nullability.isNullable); | |
| // If both nodes pointed to by the substitution node have non-null intent, | |
| // then no resolution is needed; the substitution node can’t be satisfied. | |
| if (substitutionNode.innerNode.nonNullIntent.isPresent && | |
| substitutionNode.outerNode.nonNullIntent.isPresent) { | |
| result.unsatisfiedSubstitutions.add(substitutionNode); | |
| return; | |
| } | |
| // Otherwise, if the outer node is in a nullable state, then no resolution | |
| // is needed because the substitution node is already satisfied. | |
| if (substitutionNode.outerNode.isNullable) { | |
| return; | |
| } | |
| // Otherwise, if the inner node has non-null intent, then we set the outer | |
| // node to the ordinary nullable state. | |
| if (substitutionNode.innerNode.nonNullIntent.isPresent) { | |
| assert(step.targetNode == null); | |
| step.targetNode = substitutionNode.outerNode as NullabilityNodeMutable; | |
| step.newState = Nullability.ordinaryNullable; | |
| _setNullable(step); | |
| return; | |
| } | |
| // Otherwise, we set the inner node to the exact nullable state, and we | |
| // propagate this state upstream as far as possible using the following | |
| // rule: if there is an edge A → B, where A is in the undetermined or | |
| // ordinary nullable state, and B is in the exact nullable state, then A’s | |
| // state is changed to exact nullable. | |
| var pendingExactNullableSteps = <SimpleExactNullablePropagationStep>[]; | |
| var node = substitutionNode.innerNode; | |
| if (node is NullabilityNodeMutable) { | |
| assert(step.targetNode == null); | |
| step.targetNode = node; | |
| step.newState = Nullability.exactNullable; | |
| var oldNullability = _setNullable(step); | |
| if (!oldNullability.isExactNullable) { | |
| // Was not previously in the "exact nullable" state. Need to | |
| // propagate. | |
| for (var edge in node._upstreamEdges) { | |
| pendingExactNullableSteps | |
| .add(SimpleExactNullablePropagationStep(step, edge)); | |
| } | |
| // TODO(mfairhurst): should this propagate back up outerContainerNodes? | |
| } | |
| } | |
| while (pendingExactNullableSteps.isNotEmpty) { | |
| var step = pendingExactNullableSteps.removeLast(); | |
| var edge = step.edge; | |
| var node = edge.sourceNode; | |
| if (node is NullabilityNodeMutable && | |
| !edge.isCheckable && | |
| !node.nonNullIntent.isPresent) { | |
| assert(step.targetNode == null); | |
| step.targetNode = node; | |
| step.newState = Nullability.exactNullable; | |
| var oldNullability = _setNullable(step); | |
| if (!oldNullability.isExactNullable) { | |
| // Was not previously in the "exact nullable" state. Need to | |
| // propagate. | |
| for (var edge in node._upstreamEdges) { | |
| pendingExactNullableSteps | |
| .add(SimpleExactNullablePropagationStep(step, edge)); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| void _setNonNullIntent(UpstreamPropagationStep step) { | |
| var node = step.node as NullabilityNodeMutable; | |
| var newNonNullIntent = step.newNonNullIntent; | |
| var oldNonNullIntent = node.nonNullIntent; | |
| node._nonNullIntent = newNonNullIntent; | |
| _postmortemFileWriter?.addPropagationStep(step); | |
| if (!oldNonNullIntent.isPresent) { | |
| node._whyNotNullable = step; | |
| } | |
| } | |
| Nullability _setNullable(DownstreamPropagationStep step) { | |
| var node = step.targetNode; | |
| var newState = step.newState; | |
| var oldState = node._nullability; | |
| node._nullability = newState; | |
| _postmortemFileWriter?.addPropagationStep(step); | |
| if (!oldState.isNullable) { | |
| node._whyNullable = step; | |
| // Was not previously nullable, so we need to propagate. | |
| for (var edge in node._downstreamEdges) { | |
| _pendingDownstreamSteps | |
| .add(SimpleDownstreamPropagationStep(step, edge)); | |
| } | |
| if (node is NullabilityNodeForSubstitution) { | |
| _pendingSubstitutions | |
| .add(ResolveSubstitutionPropagationStep(step, node)); | |
| } | |
| } | |
| return oldState; | |
| } | |
| } |