Skip to content

Commit e627d8b

Browse files
MichaelRFairhurstcommit-bot@chromium.org
MichaelRFairhurst
authored and
[email protected]
committed
[nnbd_migration] use postdominators to do hard edge detection in most cases
Change-Id: I6af934b4a4795a0cfd74519985b24ae171485880 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/111941 Reviewed-by: Paul Berry <[email protected]> Commit-Queue: Mike Fairhurst <[email protected]>
1 parent b614253 commit e627d8b

File tree

8 files changed

+947
-32
lines changed

8 files changed

+947
-32
lines changed

‎pkg/analyzer/lib/src/dart/ast/ast.dart‎

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4661,7 +4661,6 @@ class ForPartsWithDeclarationsImpl extends ForPartsImpl
46614661

46624662
@override
46634663
Token get beginToken => _variableList?.beginToken ?? super.beginToken;
4664-
46654664
@override
46664665
Iterable<SyntacticEntity> get childEntities => new ChildEntities()
46674666
..add(_variableList)
@@ -4704,7 +4703,6 @@ class ForPartsWithExpressionImpl extends ForPartsImpl
47044703

47054704
@override
47064705
Token get beginToken => initialization?.beginToken ?? super.beginToken;
4707-
47084706
@override
47094707
Iterable<SyntacticEntity> get childEntities => new ChildEntities()
47104708
..add(_initialization)

‎pkg/nnbd_migration/lib/src/edge_builder.dart‎

Lines changed: 147 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ import 'package:analyzer/dart/ast/token.dart';
77
import 'package:analyzer/dart/ast/visitor.dart';
88
import 'package:analyzer/dart/element/element.dart';
99
import 'package:analyzer/dart/element/type.dart';
10+
import 'package:analyzer/src/dart/ast/ast.dart';
1011
import 'package:analyzer/src/dart/element/handle.dart';
1112
import 'package:analyzer/src/dart/element/inheritance_manager3.dart';
1213
import 'package:analyzer/src/dart/element/member.dart';
@@ -22,6 +23,7 @@ import 'package:nnbd_migration/src/edge_origin.dart';
2223
import 'package:nnbd_migration/src/expression_checks.dart';
2324
import 'package:nnbd_migration/src/node_builder.dart';
2425
import 'package:nnbd_migration/src/nullability_node.dart';
26+
import 'package:nnbd_migration/src/utilities/scoped_set.dart';
2527

2628
/// Test class mixing in _AssignmentChecker, to allow [checkAssignment] to be
2729
/// more easily unit tested.
@@ -122,11 +124,13 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
122124
/// code that can be proven unreachable by the migration tool.
123125
final _guards = <NullabilityNode>[];
124126

125-
/// Indicates whether the statement or expression being visited is within
126-
/// conditional control flow. If `true`, this means that the enclosing
127-
/// function might complete normally without executing the current statement
128-
/// or expression.
129-
bool _inConditionalControlFlow = false;
127+
/// The scope of locals (parameters, variables) that are post-dominated by the
128+
/// current node as we walk the AST. We use a [ScopedSet] so that outer
129+
/// scopes may track their post-dominators separately from inner scopes.
130+
///
131+
/// Note that this is not guaranteed to be complete. It is used to make hard
132+
/// edges on a best-effort basis.
133+
final _postDominatedLocals = _ScopedLocalSet();
130134

131135
NullabilityNode _lastConditionalNode;
132136

@@ -209,10 +213,10 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
209213
DecoratedType visitAssertStatement(AssertStatement node) {
210214
_handleAssignment(node.condition, _notNullType);
211215
if (identical(_conditionInfo?.condition, node.condition)) {
212-
if (!_inConditionalControlFlow &&
213-
_conditionInfo.trueDemonstratesNonNullIntent != null) {
214-
_connect(_conditionInfo.trueDemonstratesNonNullIntent, _graph.never,
215-
NonNullAssertionOrigin(_source, node.offset),
216+
var intentNode = _conditionInfo.trueDemonstratesNonNullIntent;
217+
if (intentNode != null && _conditionInfo.postDominatingIntent) {
218+
_graph.connect(_conditionInfo.trueDemonstratesNonNullIntent,
219+
_graph.never, NonNullAssertionOrigin(_source, node.offset),
216220
hard: true);
217221
}
218222
}
@@ -226,6 +230,7 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
226230
// TODO(paulberry)
227231
_unimplemented(node, 'Assignment with operator ${node.operator.lexeme}');
228232
}
233+
_postDominatedLocals.removeReferenceFromAllScopes(node.leftHandSide);
229234
var leftType = node.leftHandSide.accept(this);
230235
var conditionalNode = _lastConditionalNode;
231236
_lastConditionalNode = null;
@@ -263,6 +268,8 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
263268
bool isPure = node.leftOperand is SimpleIdentifier;
264269
var conditionInfo = _ConditionInfo(node,
265270
isPure: isPure,
271+
postDominatingIntent:
272+
_postDominatedLocals.isReferenceInScope(node.leftOperand),
266273
trueGuard: leftType.node,
267274
falseDemonstratesNonNullIntent: leftType.node);
268275
_conditionInfo = operatorType == TokenType.EQ_EQ
@@ -273,7 +280,8 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
273280
} else if (operatorType == TokenType.AMPERSAND_AMPERSAND ||
274281
operatorType == TokenType.BAR_BAR) {
275282
_handleAssignment(node.leftOperand, _notNullType);
276-
_handleAssignment(node.rightOperand, _notNullType);
283+
_postDominatedLocals.doScoped(
284+
action: () => _handleAssignment(node.rightOperand, _notNullType));
277285
return _nonNullableBoolType;
278286
} else if (operatorType == TokenType.QUESTION_QUESTION) {
279287
DecoratedType expressionType;
@@ -317,6 +325,16 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
317325
return DecoratedType(node.staticType, _graph.never);
318326
}
319327

328+
@override
329+
DecoratedType visitBreakStatement(BreakStatement node) {
330+
// Later statements no longer post-dominate the declarations because we
331+
// exited (or, in parent scopes, conditionally exited).
332+
// TODO(mfairhurst): don't clear post-dominators beyond the current loop.
333+
_postDominatedLocals.clearEachScope();
334+
335+
return null;
336+
}
337+
320338
@override
321339
DecoratedType visitCascadeExpression(CascadeExpression node) {
322340
var type = node.target.accept(this);
@@ -365,9 +383,19 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
365383
@override
366384
DecoratedType visitConditionalExpression(ConditionalExpression node) {
367385
_handleAssignment(node.condition, _notNullType);
386+
387+
DecoratedType thenType;
388+
DecoratedType elseType;
389+
368390
// TODO(paulberry): guard anything inside the true and false branches
369-
var thenType = node.thenExpression.accept(this);
370-
var elseType = node.elseExpression.accept(this);
391+
392+
// Post-dominators diverge as we branch in the conditional.
393+
// Note: we don't have to create a scope for each branch because they can't
394+
// define variables.
395+
_postDominatedLocals.doScoped(action: () {
396+
thenType = node.thenExpression.accept(this);
397+
elseType = node.elseExpression.accept(this);
398+
});
371399

372400
var overallType = _decorateUpperOrLowerBound(
373401
node, node.staticType, thenType, elseType, true);
@@ -397,6 +425,16 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
397425
return null;
398426
}
399427

428+
@override
429+
DecoratedType visitContinueStatement(ContinueStatement node) {
430+
// Later statements no longer post-dominate the declarations because we
431+
// exited (or, in parent scopes, conditionally exited).
432+
// TODO(mfairhurst): don't clear post-dominators beyond the current loop.
433+
_postDominatedLocals.clearEachScope();
434+
435+
return null;
436+
}
437+
400438
@override
401439
DecoratedType visitDefaultFormalParameter(DefaultFormalParameter node) {
402440
node.parameter.accept(this);
@@ -458,15 +496,54 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
458496
return null;
459497
}
460498

499+
@override
500+
DecoratedType visitForStatement(ForStatement node) {
501+
// TODO do special condition handling
502+
// TODO do create true/false guards?
503+
// Create a scope of for new initializers etc, which includes previous
504+
// post-dominators.
505+
_postDominatedLocals.doScoped(
506+
copyCurrent: true,
507+
action: () {
508+
final parts = node.forLoopParts;
509+
if (parts is ForParts) {
510+
if (parts is ForPartsWithDeclarations) {
511+
parts.variables.accept(this);
512+
}
513+
if (parts is ForPartsWithExpression) {
514+
parts.initialization.accept(this);
515+
}
516+
parts.condition.accept(this);
517+
}
518+
if (parts is ForEachParts) {
519+
parts.iterable.accept(this);
520+
}
521+
522+
// The condition may fail/iterable may be empty, so the body does not
523+
// post-dominate the parts, or the outer scope.
524+
_postDominatedLocals.popScope();
525+
_postDominatedLocals.pushScope();
526+
527+
if (parts is ForParts) {
528+
parts.updaters.accept(this);
529+
}
530+
531+
node.body.accept(this);
532+
});
533+
return null;
534+
}
535+
461536
@override
462537
DecoratedType visitFunctionDeclaration(FunctionDeclaration node) {
463538
node.functionExpression.parameters?.accept(this);
464539
assert(_currentFunctionType == null);
465540
_currentFunctionType =
466541
_variables.decoratedElementType(node.declaredElement);
467-
_inConditionalControlFlow = false;
542+
// Initialize a new postDominator scope that contains only the parameters.
468543
try {
469-
node.functionExpression.body.accept(this);
544+
_postDominatedLocals.doScoped(
545+
elements: node.functionExpression.declaredElement.parameters,
546+
action: () => node.functionExpression.body.accept(this));
470547
} finally {
471548
_currentFunctionType = null;
472549
}
@@ -476,6 +553,7 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
476553
@override
477554
DecoratedType visitFunctionExpression(FunctionExpression node) {
478555
// TODO(brianwilkerson)
556+
// TODO(mfairhurst): enable edge builder "_insideFunction" hard edge tests.
479557
_unimplemented(node, 'FunctionExpression');
480558
}
481559

@@ -492,7 +570,6 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
492570
// TODO(paulberry): should the use of a boolean in an if-statement be
493571
// treated like an implicit `assert(b != null)`? Probably.
494572
_handleAssignment(node.condition, _notNullType);
495-
_inConditionalControlFlow = true;
496573
NullabilityNode trueGuard;
497574
NullabilityNode falseGuard;
498575
if (identical(_conditionInfo?.condition, node.condition)) {
@@ -505,7 +582,9 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
505582
_guards.add(trueGuard);
506583
}
507584
try {
508-
node.thenStatement.accept(this);
585+
// We branched, so create a new scope for post-dominators.
586+
_postDominatedLocals.doScoped(
587+
action: () => node.thenStatement.accept(this));
509588
} finally {
510589
if (trueGuard != null) {
511590
_guards.removeLast();
@@ -515,7 +594,9 @@ class EdgeBuilder extends GeneralizingAstVisitor<DecoratedType>
515594
_guards.add(falseGuard);
516595
}
517596
try {
518-
node.elseStatement?.accept(this);
597+
// We branched, so create a new scope for post-dominators.
598+
_postDominatedLocals.doScoped(
599+
action: () => node.elseStatement?.accept(this));
519600
} finally {
520601
if (falseGuard != null) {
521602
_guards.removeLast();
@@ -800,6 +881,12 @@ $stackTrace''');
800881
} else {
801882
_handleAssignment(returnValue, returnType);
802883
}
884+
885+
// Later statements no longer post-dominate the declarations because we
886+
// exited (or, in parent scopes, conditionally exited).
887+
// TODO(mfairhurst): don't clear post-dominators beyond the current function.
888+
_postDominatedLocals.clearEachScope();
889+
803890
return null;
804891
}
805892

@@ -962,6 +1049,17 @@ $stackTrace''');
9621049
}
9631050
}
9641051
}
1052+
_postDominatedLocals
1053+
.addAll(node.variables.map((variable) => variable.declaredElement));
1054+
return null;
1055+
}
1056+
1057+
@override
1058+
DecoratedType visitWhileStatement(WhileStatement node) {
1059+
// TODO do special condition handling
1060+
// TODO do create true/false guards?
1061+
_handleAssignment(node.condition, _notNullType);
1062+
_postDominatedLocals.doScoped(action: () => node.body.accept(this));
9651063
return null;
9661064
}
9671065

@@ -1112,8 +1210,7 @@ $stackTrace''');
11121210
_checkAssignment(expressionChecks,
11131211
source: sourceType,
11141212
destination: destinationType,
1115-
hard: _isVariableOrParameterReference(expression) &&
1116-
!_inConditionalControlFlow);
1213+
hard: _postDominatedLocals.isReferenceInScope(expression));
11171214
return sourceType;
11181215
}
11191216

@@ -1147,7 +1244,8 @@ $stackTrace''');
11471244
returnType?.accept(this);
11481245
parameters?.accept(this);
11491246
_currentFunctionType = _variables.decoratedElementType(declaredElement);
1150-
_inConditionalControlFlow = false;
1247+
// Push a scope of post-dominated declarations on the stack.
1248+
_postDominatedLocals.pushScope(elements: declaredElement.parameters);
11511249
try {
11521250
initializers?.accept(this);
11531251
body.accept(this);
@@ -1231,6 +1329,7 @@ $stackTrace''');
12311329
}
12321330
} finally {
12331331
_currentFunctionType = null;
1332+
_postDominatedLocals.popScope();
12341333
}
12351334
}
12361335

@@ -1370,15 +1469,6 @@ $stackTrace''');
13701469
} else {
13711470
return false;
13721471
}
1373-
}
1374-
1375-
bool _isVariableOrParameterReference(Expression expression) {
1376-
expression = expression.unParenthesized;
1377-
if (expression is SimpleIdentifier) {
1378-
var element = expression.staticElement;
1379-
if (element is LocalVariableElement) return true;
1380-
if (element is ParameterElement) return true;
1381-
}
13821472
return false;
13831473
}
13841474

@@ -1572,6 +1662,9 @@ class _ConditionInfo {
15721662
/// effect other than returning a boolean value.
15731663
final bool isPure;
15741664

1665+
/// Indicates whether the intents postdominate the intent node declarations.
1666+
final bool postDominatingIntent;
1667+
15751668
/// If not `null`, the [NullabilityNode] that would need to be nullable in
15761669
/// order for [condition] to evaluate to `true`.
15771670
final NullabilityNode trueGuard;
@@ -1581,7 +1674,7 @@ class _ConditionInfo {
15811674
final NullabilityNode falseGuard;
15821675

15831676
/// If not `null`, the [NullabilityNode] that should be asserted to have
1584-
// /// non-null intent if [condition] is asserted to be `true`.
1677+
/// non-null intent if [condition] is asserted to be `true`.
15851678
final NullabilityNode trueDemonstratesNonNullIntent;
15861679

15871680
/// If not `null`, the [NullabilityNode] that should be asserted to have
@@ -1590,6 +1683,7 @@ class _ConditionInfo {
15901683

15911684
_ConditionInfo(this.condition,
15921685
{@required this.isPure,
1686+
this.postDominatingIntent,
15931687
this.trueGuard,
15941688
this.falseGuard,
15951689
this.trueDemonstratesNonNullIntent,
@@ -1598,8 +1692,31 @@ class _ConditionInfo {
15981692
/// Returns a new [_ConditionInfo] describing the boolean "not" of `this`.
15991693
_ConditionInfo not(Expression condition) => _ConditionInfo(condition,
16001694
isPure: isPure,
1695+
postDominatingIntent: postDominatingIntent,
16011696
trueGuard: falseGuard,
16021697
falseGuard: trueGuard,
16031698
trueDemonstratesNonNullIntent: falseDemonstratesNonNullIntent,
16041699
falseDemonstratesNonNullIntent: trueDemonstratesNonNullIntent);
16051700
}
1701+
1702+
/// A [ScopedSet] specific to the [Element]s of locals/parameters.
1703+
///
1704+
/// Contains helpers for dealing with expressions as if they were elements.
1705+
class _ScopedLocalSet extends ScopedSet<Element> {
1706+
bool isReferenceInScope(Expression expression) {
1707+
expression = expression.unParenthesized;
1708+
if (expression is SimpleIdentifier) {
1709+
var element = expression.staticElement;
1710+
return isInScope(element);
1711+
}
1712+
return false;
1713+
}
1714+
1715+
void removeReferenceFromAllScopes(Expression expression) {
1716+
expression = expression.unParenthesized;
1717+
if (expression is SimpleIdentifier) {
1718+
var element = expression.staticElement;
1719+
removeFromAllScopes(element);
1720+
}
1721+
}
1722+
}

0 commit comments

Comments
 (0)