Improve performance: invariant_booleans #501

JPaulsen · 2017-03-16T22:11:20Z

alexeieleusis · 2017-03-16T22:12:34Z

lib/src/rules/invariant_booleans.dart

-[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 
+_**WARNING:** this lint is comparatively expensive as, in general, calculating


This is no longer needed :)

JPaulsen · 2017-03-16T22:12:37Z

Benchmark in my machine:

---------------------------------------------------
Timings                                          ms
---------------------------------------------------
always_declare_return_types                      10
always_specify_types                              9
annotate_overrides                               27
avoid_as                                          3
avoid_empty_else                                  3
avoid_function_literals_in_foreach_calls          4
avoid_init_to_null                                3
avoid_return_types_on_setters                     3
avoid_slow_async_io                               5
await_only_futures                                3
camel_case_types                                 10
cancel_subscriptions                             28
cascade_invocations                               7
close_sinks                                      39
comment_references                                3
constant_identifier_names                         5
control_flow_in_finally                           5
directives_ordering                              16
empty_catches                                     5
empty_constructor_bodies                          4
empty_statements                                  3
hash_and_equals                                   4
implementation_imports                            4
invariant_booleans                               58
iterable_contains_unrelated_type                  6
library_names                                     7
library_prefixes                                 10
list_remove_unrelated_type                        5
literal_only_boolean_expressions                  4
no_adjacent_strings_in_list                       4
no_duplicate_case_values                          7
non_constant_identifier_names                    19
omit_local_variable_types                         6
one_member_abstracts                              3
only_throw_errors                                 4
overridden_fields                                 6
package_api_docs                                 14
package_prefixed_library_names                    8
parameter_assignments                             7
prefer_adjacent_string_concatenation              3
prefer_collection_literals                        3
prefer_const_constructors                         4
prefer_contains                                  15
prefer_expression_function_bodies                 4
prefer_final_fields                              16
prefer_final_locals                               6
prefer_function_declarations_over_variables       3
prefer_initializing_formals                       9
prefer_interpolation_to_compose_strings           5
prefer_is_empty                                  17
prefer_is_not_empty                               9
public_member_api_docs                           81
recursive_getters                                 8
slash_for_doc_comments                            4
sort_constructors_first                           5
sort_unnamed_constructors_first                   4
super_goes_last                                   3
test_types_in_equals                              3
throw_in_finally                                  4
type_annotate_public_apis                         6
type_init_formals                                 3
unawaited_futures                                 5
unnecessary_brace_in_string_interps               4
unnecessary_getters_setters                       6
unnecessary_lambdas                               7
unnecessary_null_aware_assignments                3
unneces
8000
sary_null_in_if_null_operators             3
unnecessary_this                                 18
unrelated_type_equality_checks                    6
valid_regexps                                     4
---------------------------------------------------
Total                                           642
---------------------------------------------------

bwilkerson · 2017-03-16T23:12:54Z

lib/src/rules/invariant_booleans.dart

-            _findConditionsOfElseStatementAncestor(node.parent, nodesInDFS)))
-      .toSet();
-  return new TestedExpressions(node, conjunctions, negations);
+Element _getRealElement(AstNode node) {


Can we rename this method to "Canonical" as well?

bwilkerson · 2017-03-16T23:13:06Z

lib/src/util/condition_scope_visitor.dart

+      : leftPart is PropertyAccess
+          ? DartTypeUtilities
+              .getCanonicalElement(leftPart.propertyName.bestElement)
+          : null;


Maybe move _getRealElement from invariant_booleans.dart to here and convert this to => _getRealElement(assignment.leftHandSide);?

Fixed (good idea)

bwilkerson · 2017-03-16T23:13:09Z

lib/src/util/condition_scope_visitor.dart

+bool _isBreakStatement(Statement statement) => (statement is BreakStatement ||
+    (statement is Block &&
+        statement.statements.length == 1 &&
+        statement.statements.first is BreakStatement));


Is it worth a recursive call here to handle strange, but possible, code like this?

{ { break; } }

Probably not, but it's your call.

bwilkerson · 2017-03-16T23:13:12Z

lib/src/util/condition_scope_visitor.dart

+        statement.statements.first is ReturnStatement));
+
+abstract class ConditionScopeVisitor extends RecursiveAstVisitor {
+  final Queue<Queue<_ExpressionBox>> environments = new Queue();


Still seems odd to me to use a Queue, especially when we're treating the top-level queue as a stack. :-)

In fact all of them are stacks xd, I am trying to figure out what is exactly what we need in this kind of "scope"

This is one of the few issues that I have not solved, what do you think is a better option here @bwilkerson?

I would start by writing a class like the following:

class ConditionScope { /** * The outer scope, of `null` if this is the outermost scope. */ final Scope outer; /** * Initialize a newly created scope to have the given [outer] scope. */ ConditionScope(this.outer); }

Then I would add fields and methods to support adding _ExpressionBoxs and performing lookup (which would replace one of the method in ConditionScopeVisitor). Given that you're not really treating the inner queues as queues, I'd probably change to using a list. The environments field would be replaced by

ConditionScope currentScope;

pushes look like

currentScope = new ConditionScope(currentScope);

and pops look like

currentScope = currentScope.outer;

I implemented my own Stack the other day to see if that improved the benchmark of my iterative version of traverseNodeInDfs jaja, I got it, I will be focused on this

Fixed, I used a List but I had to reversed it when getting condition expression, PTAL, maybe is better use a Queue internally in the ConditionScope

bwilkerson · 2017-03-16T23:13:15Z

lib/src/util/condition_scope_visitor.dart

+
+  @override
+  visitAssignmentExpression(AssignmentExpression node) {
+    _addElementToEnvironment(new _UndefinedExpression(_getLeftElement(node)));


We might want to guard against nodes that cannot be resolved by not adding anything to the environment (here and elsewhere):

Element element = _getLeftElement(node); if (element != null) { _addElementToEnvironment(new _UndefinedExpression(node); }

We should minimally add a test.

I fixed this creating a factory constructor, so if the parameter is null, the constructor return null and _addElementToEnvironment does not add null objects, so FIXED, but what kind of test could add?

In this case, we need an assignment expression whose left-hand-side is not resolved:

notDefined = 3;

(any name that isn't defined will work). Of course, you'll want to back out your fix to ensure that the test case actually triggers the bug.

Yes but, in that case, we would add to the scope something like, null is undefined, and that would not change the behavior of invariant booleans, at least we do something like:

if (notDefined2 < 2) { notDefined = 3; // we undefine null if (notDefined2 < 2) { // this won't be linted, because notDefined2 is null and null (notDefined) was undefined just before this condition is evaluated } }

My point is that checking those nulls wont change the behavior in code with not null elements in conditions inside if/while/do/for, so we should take care about conditions with null elements inside too, what do you think?

Given how few undefined names there usually are in code, if it doesn't cause exceptions to be thrown then I don't suppose it's worth doing a lot of work to guard against having a null element.

@bwilkerson this is my last issue, and I can not figure out a test where the rule do something and without checking adding null elements would do something different. (I mean lints)

It's quite possible that having an instance of _UndefinedExpression whose element is null is harmless. It just wasn't clear to me that that would be the case.

Yes it is harmless, but other things like:

if (notDefined < 2) { if (notDefined < 2) { // there is a lint here } }

can decrease the UX level, because there will be a linter and an error in the same place, I fixed this locally but it is necessary to check for types and it is really expensive (the benchmark in the rule moved from ~55 to >140), so I think it is a cost I would pay to have a faster linter as a user.

If you think this is OK the branch is ready to merge, if you want me to fix this even that means have a worse performance just tell me and I will do it.

I think I'll merge it, and we can re-visit this after the fact.

bwilkerson · 2017-03-16T23:13:27Z

lib/src/util/condition_scope_visitor.dart

+    if (_isReturnStatement(statement) ||
+        _isBreakStatement(statement) ||
+        _isContinueStatement(statement)) {
+      _addElementToEnvironment(expressionBox);


We do something similar for dead code detection. Check out https://github.com/dart-lang/sdk/blob/master/pkg/analyzer/lib/src/generated/resolver.dart#L2201. Our checking is a bit more complete, and you might be able to make use of it here (although we'd need to make it available).

bwilkerson · 2017-03-16T23:13:30Z

lib/src/util/condition_scope_visitor.dart

+    }
+  }
+
+  void _addLocalEnvironment() {


Under what conditions do we need to add a local environment? (Adding a comment would be good.) It seems like we might be adding and removing too many, but I'm not sure.

I think so, but I am not sure yet, we are trying to refactor the way we use the scope

I realized that it is necessary to create new local environments, I created an unifying visitor so now it asks which clases just creates local environments, PTAL at the methods visitNode and _needsLocalEnvironment

Replicated issue

bwilkerson · 2017-03-18T15:56:51Z

lib/src/util/condition_scope_visitor.dart

+    node is CompilationUnit ||
+    node is ConstructorDeclaration ||
+    node is FunctionDeclaration ||
+    node is MethodDeclaration;


The value analysis performed by this rule can only be used on local variables, so it isn't clear to me why it makes sense to test for ClassDeclaration or CompilationUnit. Please add documentation somewhere explaining when and/or why we need a local environment.

I believe that the last three conditions could be replaced by node is FunctionBody, although testing for FunctionBody will also cause a local environment to be created when visiting local functions, so it's not strictly equivalent.

Also, given that blocks define a name scope, do we need to define a local environment when we enter a block? Asked another way, should the conditions tested inside a block still be considered when we leave the block?

It was not necessary, and yes, now they only is FunctionBody and trying to resolve what to do with blocks

There is not necessary to create new local environments in blocks

Just so it isn't forgotten, I'll repeat the request:

Please add documentation somewhere explaining when and/or why we need a local environment.

Fixed, PTAL

bwilkerson · 2017-03-18T15:57:14Z

lib/src/util/condition_scope_visitor.dart

+    bool hasBreak = DartTypeUtilities
+        .traverseNodesInDFS(node, excludeCriteria: _isLoopStatement)
+        .any((e) => e is BreakStatement);
+    if (!hasBreak) {


I suspect that this will not work correctly with labeled break statements:

outer: for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (i > j) { break outer; } } }

bwilkerson · 2017-03-18T15:57:57Z

lib/src/util/condition_scope_visitor.dart

+  }
+
+  @override
+  visitNode(AstNode node) {


This will work, and I'm fine with it if you want to leave it, but there are two factors to consider. First, is tests are surprisingly slow, so it would be faster if you take advantage of the polymorphism that's going to be done either way. Second, if anyone ever creates a subclass and overwrites a visit... method to visit a node for which _needsLocalEnvironment would return true, it will be harder for them to see that they need to invoke either the super visit... method or visitNode.

Does the overridden method do exactly what this one does? (I think it does, but it's hard for me to check right now.) If so, let's just delete this method.

This method made this Visitor have the behavior of a RecursiveAstVisitor, I deleted the method and replace the extends UnifyingAstVisitor by extends RecursiveAstVisitor.

bwilkerson · 2017-03-18T16:02:50Z

lib/src/util/condition_scope_visitor.dart

+
+  @override
+  visitVariableDeclaration(VariableDeclaration node) {
+    _addElementToEnvironment(new _UndefinedExpression(node.element));


Are there plans to use either the initialization expression (or the right-hand side in an assignment) when the value assigned is known (a constant expression)? For example, will we create a lint here:

var x = 0; // code that doesn't modify x if (x > 0) { ... }

(It's ok if the answer is "no", or to do that as a follow-on to this CL if the answer is "yes".)

It is not supported by now, and before this optimization it was not contemplated, but it could be implemented in the future, I would like to do it, what do you think @alexeieleusis ?

It is definitely nice to have, I wonder if now is the best time. We need to consider the cost/benefit, I lean towards leaving it for later, there are rules that require less effort and provide more value.

bwilkerson · 2017-03-18T16:06:37Z

lib/src/rules/invariant_booleans.dart

+  TestedExpressions _findPreviousTestedExpressions(Expression node) {
+    final elements = _getRealElementsInExpression(node);
+    Iterable<Expression> conjunctions = getTrueExpressions(elements)
+        .map(_splitConjunctions)


Would it be more efficient to split conjunctions when adding the conditions rather than when finding tested expressions?

bwilkerson · 2017-03-21T13:59:19Z

lib/src/util/condition_scope_visitor.dart

+  Iterable<_ExpressionBox> getUndefinedExpressions() =>
+      environment.where((e) => e is _UndefinedExpression);
+
+  static void _recursiveGetExpressions(ConditionScope conditionScope,


If you make this an instance method, then the conditionScope parameter can be removed in favor of using this. The last line would need to change to invoke this method on outer, and only when outer is non-null. But I think it will make the code a little smaller. (Not a requirement, though.)

bwilkerson · 2017-03-21T14:01:18Z

lib/src/util/condition_scope_visitor.dart

+  }
+
+  @override
+  visitEmptyFunctionBody(EmptyFunctionBody node) {


Given that an empty function body doesn't have any children, this method should be unnecessary.

bwilkerson · 2017-03-21T14:03:58Z

lib/src/util/condition_scope_visitor.dart

+    node.updaters.accept(this);
+    node.body?.accept(this);
+    _propagateUndefinedExpressions(_removeLastScope());
+    bool hasBreak = DartTypeUtilities


It would be good to add a comment here related to the handling of break statements so that we remember the issues.

bwilkerson · 2017-03-21T14:12:00Z

lib/src/util/condition_scope_visitor.dart

+    node.body?.accept(this);
+    _propagateUndefinedExpressions(_removeLastScope());
+    bool hasBreak = DartTypeUtilities
+        .traverseNodesInDFS(node, excludeCriteria: _isLoopStatement)


Given that we're not handling break statements with labels correctly, I think that excluding loop statements will cause false positives. Consider:

loop: for (...) { while (...) { break loop; } }

Also, not excluding function bodies might well cause false negatives. Consider:

while (...) { void func() { while (...) { break; } } }

About this:

while (...) { void func() { while (...) { break; } } }

The first while search for breaks excluding other for and while, so in that case, the break won't be see because is inside other while, an option would be something like this:

while (...) { void func() { break; } }

But that is not possible, the analyzer would say 'A break statement cannot be used outside of a loop or switch statement'

Ok, replace the body of the function with a switch statement and stick a break in one case. Then I think we can get to the break when we shouldn't.

Yes, that is a bug that I made, I should exclude loop statements and switch statements, and that's it

loop: for (...) { while (...) { break loop; } }

I have been thinking a lot about this, can you help me?

How do you think this would produce a false positive?

My understanding is that hasBreak should be true (in both the for and while cases) if there is any way for control to reach the statement following the loop other than for the condition to evaluate to false. But if you don't look inside the nested while loop (in the example above) then you won't find the break statement that applies to the for loop and hasBreak will be false despite the fact that the condition doesn't have to be false. Here's a more concrete example:

String s = '...'; loop: for (; s != null; s += '.') { while (true != false) { break loop; } } // I think there will be a lint on the following line, // even though the test is reasonable. if (s != null) { print(s); }

Woooow!! I see now, I thought a break with label worked like a goto, I am so sorry, my bad, I understood perfectly now, and I will work fixing this

Fixed (finally :D)

bwilkerson · 2017-03-21T14:46:35Z

lib/src/util/condition_scope_visitor.dart

+    _visitIfStatement(node);
+    _propagateUndefinedExpressions(elseScope);
+    if (_isLastStatementAnExitStatement(node.thenStatement)) {
+      _addFalseCondition(node.condition);


What happens with the following (pathological) case:

if (x == null) { return false; } else { return true; } if (x == null) { ... }

(and with the sense of the conditions reversed)?

I think we only want to record either true or false conditions only when exactly one block terminates.

In that case the last if is dead code, in the environment we would see that (x == null) is true and false at the same time, and probably would lint the last if. But it still correct that if a then statement is return the condition is false after de if/else block the same if the else is a return block. There is only one exception when you have a label after the if/else statement, in that case, when we see a label, we should undefine all expression, what do you think?

I don't understand the case you're thinking of. Can you give me an example involving a label after an if statement?

That said, I do think that we might want to forget everything we think we know when we hit a label because we don't know what the state of any variable will be when execution reaches the break or continue that will transfer control to that label. Unfortunately, the same is true for any do, for, switch or while statement because they all have an implicit empty label.

Forget what I said, in that case x == null is true and false in the environment, so it will be resolved to a lint, but we can easily detect those kind of cases, because they are dead code and do not lint if you want, what do you think is better lint or not to lint?

It is better to have one diagnostic ("dead code") than to have multiple diagnostics for the same problem. That's why I think we shouldn't produce a lint in this case.

bwilkerson · 2017-03-21T14:52:52Z

lib/src/util/condition_scope_visitor.dart

+  bool _isLastStatementAnExitStatement(Statement statement) {
+    if (statement is Block) {
+      return _isLastStatementAnExitStatement(
+          DartTypeUtilities.getLastStatementInBlock(statement));


Does ExitDetector not handle blocks? (I'm wondering whether you need to special case blocks here.)

If you do need to special case blocks, I think you need to search for a statement within the block that can exit in order to handle pathological cases such as

if (...) { return; print("Shouldn't get here"); }

Otherwise we'll think that the last statement means that we can fall through.

Does the analyzer find the dead code there?, I think in that case we would be doing something that is already done

Yes, analyzer will find and report the dead code. The question is what we need to do in order to avoid false positives for cases like these.

An easy fix would be add an UndefinedAllExpressions when we see a return statement :)

A return, a throw, or a rethrow (assuming I'm not forgetting anything).

As long as we've thought hard about possible false positives and worked to prevent them, and document in the code how we've done that, I'm fine with most solutions. (Including undefining everything after an exit from the current function body.)

Fixed, I will work in documentation now, Alexei will help me also.

JPaulsen · 2017-03-21T18:21:45Z

lib/src/util/condition_scope_visitor.dart

+  }
+
+  @override
+  visitReturnStatement(ReturnStatement node) {


I have to create test for this, and throw and rethrow

pq · 2017-03-22T12:53:06Z

@bwilkerson : could you take a quick look at @JPaulsen's latest? Looks like the main issues are addressed. Thanks in advance!

bwilkerson

I think we should get this landed. As a future enhancement we might want to handle the conditional expression:

int i = 0;
return i == 0 ? (i ==0 ? false : true) : false;

bwilkerson · 2017-03-22T16:09:34Z

lib/src/util/condition_scope_visitor.dart

+
+  @override
+  visitAssignmentExpression(AssignmentExpression node) {
+    _addElementToEnvironment(new _UndefinedExpression(_getLeftElement(node)));


It's quite possible that having an instance of _UndefinedExpression whose element is null is harmless. It just wasn't clear to me that that would be the case.

googlebot added the cla: yes label Mar 16, 2017

alexeieleusis reviewed Mar 16, 2017

View reviewed changes

JPaulsen force-pushed the improve_performance_invariant_booleans branch from e26d57a to 1d77944 Compare March 16, 2017 22:13

bwilkerson reviewed Mar 16, 2017

View reviewed changes

JPaulsen force-pushed the improve_performance_invariant_booleans branch 5 times, most recently from 57ce820 to 15128e2 Compare March 18, 2017 03:48

bwilkerson reviewed Mar 18, 2017

View reviewed changes

JPaulsen force-pushed the improve_performance_invariant_booleans branch 9 times, most recently from aba4d3e to d7f2817 Compare March 20, 2017 20:46

JPaulsen changed the title ~~Improve performance: Invariant Booleans~~ Improve performance: invariant_booleans Mar 21, 2017

JPaulsen force-pushed the improve_performance_invariant_booleans branch 2 times, most recently from bd96969 to a9b2c55 Compare March 21, 2017 03:52

bwilkerson reviewed Mar 21, 2017

View reviewed changes

JPaulsen force-pushed the improve_performance_invariant_booleans branch 4 times, most recently from c517a88 to d7ff56b Compare March 21, 2017 18:21

JPaulsen commented Mar 21, 2017

View reviewed changes

JPaulsen force-pushed the improve_performance_invariant_booleans branch from d7ff56b to aa528c5 Compare March 21, 2017 18:58

JPaulsen force-pushed the improve_performance_invariant_booleans branch 6 times, most recently from d38232e to 766d0ff Compare March 22, 2017 00:57

bwilkerson approved these changes Mar 22, 2017

View reviewed changes

Improve performance: Invariant Booleans

0999a4b

JPaulsen force-pushed the improve_performance_invariant_booleans branch from 766d0ff to 0999a4b Compare March 22, 2017 19:06

bwilkerson merged commit f451f4c into dart-archive:master Mar 22, 2017

Improve performance: invariant_booleans #501

Improve performance: invariant_booleans #501

Uh oh!

Conversation

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!