8000 Improve performance: invariant_booleans by JPaulsen · Pull Request #501 · dart-archive/linter · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content
This repository was archived by the owner on Nov 20, 2024. It is now read-only.

Improve performance: invariant_booleans #501

Merged
merged 1 commit into from
Mar 22, 2017
Merged

Improve performance: invariant_booleans #501

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
210 changes: 28 additions & 182 deletions lib/src/rules/invariant_booleans.dart
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8,8 +8,10 @@ import 'package:analyzer/dart/ast/ast.dart';
import 'package:analyzer/dart/ast/standard_resolution_map.dart';
import 'package:analyzer/dart/ast/token.dart';
import 'package:analyzer/dart/ast/visitor.dart';
import 'package:analyzer/dart/element/element.dart';
import 'package:linter/src/analyzer.dart';
import 'package:linter/src/util/boolean_expression_utilities.dart';
import 'package:linter/src/util/condition_scope_visitor.dart';
import 'package:linter/src/util/dart_type_utilities.dart';
import 'package:linter/src/util/tested_expressions.dart';

Expand Down Expand Up @@ -96,166 +98,12 @@ void nestedOk5() {
}
```

_**WARNING:** this lint is comparatively expensive as, in general, calculating
[boolean satisfiability](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) is hard.
Performance improvements are planned ([#434](https://github.com/dart-lang/linter/issues/434)) but
in the meantime, this lint should be sparingly enabled in large projects or when lint performance
is a concern._
''';

Set<Expression> _findConditionsCausingReturns(
Expression node, Iterable<AstNode> nodesInDFS) =>
nodesInDFS
.where(_isAnalyzedNode)
.where(_isConditionalStatementWithReturn(nodesInDFS))
.takeWhile((n) => n != node.parent)
.where((_noFurtherAssignmentInvalidatingCondition(node, nodesInDFS)))
.fold(<Expression>[], (List<Expression> previous, AstNode statement) {
previous.add(_getCondition(statement));
return previous;
}).toSet();

Set<Expression> _findConditionsOfElseStatementAncestor(
Statement statement, Iterable<AstNode> nodesInDFS) {
return _findConditionsUnderStatementBranch(
statement,
(n) =>
n is IfStatement &&
statement.getAncestor((a) => a == n.elseStatement) != null,
nodesInDFS);
}

Set<Expression> _findConditionsOfStatementAncestor(
Statement statement, Iterable<AstNode> nodesInDFS) {
return _findConditionsUnderStatementBranch(
statement,
(n) =>
_isAnalyzedNode(n) &&
(n is! IfStatement ||
statement.getAncestor(
(a) => a == (n as IfStatement).thenStatement) !=
null),
nodesInDFS);
}

Set<Expression> _findConditionsUnderStatementBranch(Statement statement,
AstNodePredicate predicate, Iterable<AstNode> nodesInDFS) {
Expression condition = _getCondition(statement);
AstNodePredicate noFurtherAssignmentInvalidatingCondition =
_noFurtherAssignmentInvalidatingCondition(condition, nodesInDFS);
return nodesInDFS
.where((n) => n == statement.getAncestor((a) => a == n && a != statement))
.where(_isAnalyzedNode)
.where(predicate)
.where(noFurtherAssignmentInvalidatingCondition)
.fold(<Expression>[], (List<Expression> previous, AstNode statement) {
previous.add(_getCondition(statement));
return previous;
}).toSet();
}

TestedExpressions _findPreviousTestedExpressions(Expression node) {
Block block = node.getAncestor((a) => a is Block && a.parent is FunctionBody);
Iterable<AstNode> nodesInDFS = DartTypeUtilities.traverseNodesInDFS(block,
excludeCriteria: (n) => n is FunctionDeclarationStatement);
Iterable<Expression> conjunctions =
_findConditionsOfStatementAncestor(node.parent, nodesInDFS)
.map(_splitConjunctions)
.expand((iterable) => iterable)
.toSet();
Iterable<Expression> negations = (_findConditionsCausingReturns(
node, nodesInDFS)
..addAll(
_findConditionsOfElseStatementAncestor(node.parent, nodesInDFS)))
.toSet();
return new TestedExpressions(node, conjunctions, negations);
}

Set<Identifier> _findStatementIdentifiers(Statement statement) =>
DartTypeUtilities
.traverseNodesInDFS(statement)
.where((n) => n is Identifier)
.toSet();

Expression _getCondition(Statement statement) {
if (statement is IfStatement) {
return statement.condition;
}

if (statement is DoStatement) {
return statement.condition;
}

if (statement is ForStatement) {
return statement.condition;
}

if (statement is WhileStatement) {
return statement.condition;
}

return null;
}

bool _isAnalyzedNode(AstNode node) =>
node is IfStatement ||
node is DoStatement ||
node is ForStatement ||
node is WhileStatement;

AstNodePredicate _isConditionalStatementWithReturn(
Iterable<AstNode> blockNodes) =>
(AstNode node) {
Block block =
node.getAncestor((a) => a is Block && a.parent is BlockFunctionBody);
Iterable<AstNode> nodesInDFS = DartTypeUtilities.traverseNodesInDFS(node);
return nodesInDFS.any((n) => n is ReturnStatement) &&
// Ignore nested if statements.
!nodesInDFS.any(_isAnalyzedNode) &&
node.getAncestor((n) =>
n != node &&
_isAnalyzedNode(n) &&
n.getAncestor((a) => a == block) == block) ==
null;
};

AstNodePredicate _noFurtherAssignmentInvalidatingCondition(
Expression node, Iterable<AstNode> nodesInDFS) {
Set<Identifier> identifiers = _findStatementIdentifiers(node.parent);
return (AstNode statement) {
bool isMutation(AstNode n) {
if (n is AssignmentExpression) {
return !identifiers.contains(n.leftHandSide);
} else if (n is PostfixExpression) {
TokenType type = n.operator.type;
return (type == TokenType.PLUS_PLUS || type == TokenType.MINUS_MINUS) &&
!identifiers.contains(n.ope 8000 rand);
} else if (n is PrefixExpression) {
TokenType type = n.operator.type;
return (type == TokenType.PLUS_PLUS || type == TokenType.MINUS_MINUS) &&
!identifiers.contains(n.operand);
}

return false;
}

return nodesInDFS
.skipWhile((n) => n != statement)
.takeWhile((n) => n != node)
.where(isMutation)
.isEmpty;
};
}

List<Expression> _splitConjunctions(Expression expression) {
if (expression is BinaryExpression &&
expression.operator.type == TokenType.AMPERSAND_AMPERSAND) {
return _splitConjunctions(expression.leftOperand)
..addAll(_splitConjunctions(expression.rightOperand));
}

return [expression];
}
Iterable<Element> _getElementsInExpression(Expression node) => DartTypeUtilities
.traverseNodesInDFS(node)
.map(DartTypeUtilities.getCanonicalElementFromIdentifier)
.where((e) => e != null);

class InvariantBooleans extends LintRule {
_Visitor _visitor;
Expand Down Expand Up @@ -286,36 +134,16 @@ class _ContradictionReportRule extends LintRule {
maturity: Maturity.stable);
}

class _Visitor extends SimpleAstVisitor {
class _InvariantBooleansVisitor extends ConditionScopeVisitor {
final LintRule rule;

_Visitor(this.rule);

@override
visitDoStatement(DoStatement node) {
_reportExpressionIfConstantValue(node.condition);
}

@override
visitForStatement(ForStatement node) {
_reportExpressionIfConstantValue(node.condition);
}

@override
visitIfStatement(IfStatement node) {
_reportExpressionIfConstantValue(node.condition);
}
_InvariantBooleansVisitor(this.rule);

@override
visitWhileStatement(WhileStatement node) {
_reportExpressionIfConstantValue(node.condition);
}

_reportExpressionIfConstantValue(Expression node) {
visitCondition(Expression node) {
// Right part discards reporting a subexpression already reported.
if (node == null ||
resolutionMap.bestTypeForExpression(node).name != 'bool' ||
!_isAnalyzedNode(node.parent)) {
resolutionMap.bestTypeForExpression(node).name != 'bool') {
return;
}

Expand All @@ -340,4 +168,22 @@ class _Visitor extends SimpleAstVisitor {
rule.reportLint(node);
}
}

TestedExpressions _findPreviousTestedExpressions(Expression node) {
final elements = _getElementsInExpression(node);
Iterable<Expression> conjunctions = getTrueExpressions(elements).toSet();
Iterable<Expression> negations = getFalseExpressions(elements).toSet();
return new TestedExpressions(node, conjunctions, negations);
}
}

class _Visitor extends SimpleAstVisitor {
final LintRule rule;

_Visitor(this.rule);

@override
visitCompilationUnit(CompilationUnit node) {
new _InvariantBooleansVisitor(rule).visitCompilationUnit(node);
}
}
Loading
0