| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library logical_rewriter; | |
| 6 | |
| 7 import '../constants/values.dart' as values; | |
| 8 import 'tree_ir_nodes.dart'; | |
| 9 | |
| 10 /// Rewrites logical expressions to be more compact in the Tree IR. | |
| 11 /// | |
| 12 /// In this class an expression is said to occur in "boolean context" if | |
| 13 /// its result is immediately applied to boolean conversion. | |
| 14 /// | |
| 15 /// IF STATEMENTS: | |
| 16 /// | |
| 17 /// We apply the following two rules to [If] statements (see [visitIf]). | |
| 18 /// | |
| 19 /// if (E) {} else S ==> if (!E) S else {} (else can be omitted) | |
| 20 /// if (!E) S1 else S2 ==> if (E) S2 else S1 (unless previous rule applied) | |
| 21 /// | |
| 22 /// NEGATION: | |
| 23 /// | |
| 24 /// De Morgan's Laws are used to rewrite negations of logical operators so | |
| 25 /// negations are closer to the root: | |
| 26 /// | |
| 27 /// !x && !y --> !(x || y) | |
| 28 /// | |
| 29 /// This is to enable other rewrites, such as branch swapping in an if. In some | |
| 30 /// contexts, the rule is reversed because we do not expect to apply a rewrite | |
| 31 /// rule to the result. For example: | |
| 32 /// | |
| 33 /// z = !(x || y) ==> z = !x && !y; | |
| 34 /// | |
| 35 /// CONDITIONALS: | |
| 36 /// | |
| 37 /// Conditionals with boolean constant operands occur frequently in the input. | |
| 38 /// They can often the re-written to logical operators, for instance: | |
| 39 /// | |
| 40 /// if (x ? y : false) S1 else S2 | |
| 41 /// ==> | |
| 42 /// if (x && y) S1 else S2 | |
| 43 /// | |
| 44 /// Conditionals are tricky to rewrite when they occur out of boolean context. | |
| 45 /// Here we must apply more conservative rules, such as: | |
| 46 /// | |
| 47 /// x ? true : false ==> !!x | |
| 48 /// | |
| 49 /// If an operand is known to be a boolean, we can introduce a logical operator: | |
| 50 /// | |
| 51 /// x ? y : false ==> x && y (if y is known to be a boolean) | |
| 52 /// | |
| 53 /// The following sequence of rewrites demonstrates the merit of these rules: | |
| 54 /// | |
| 55 /// x ? (y ? true : false) : false | |
| 56 /// x ? !!y : false (double negation introduced by [toBoolean]) | |
| 57 /// x && !!y (!!y validated by [isBooleanValued]) | |
| 58 /// x && y (double negation removed by [putInBooleanContext]) | |
| 59 /// | |
| 60 class LogicalRewriter extends Visitor<Statement, Expression> { | |
| 61 | |
| 62 /// Statement to be executed next by natural fallthrough. Although fallthrough | |
| 63 /// is not introduced in this phase, we need to reason about fallthrough when | |
| 64 /// evaluating the benefit of swapping the branches of an [If]. | |
| 65 Statement fallthrough; | |
| 66 | |
| 67 void rewrite(FunctionDefinition definition) { | |
| 68 if (definition.isAbstract) return; | |
| 69 | |
| 70 definition.body = visitStatement(definition.body); | |
| 71 } | |
| 72 | |
| 73 Statement visitLabeledStatement(LabeledStatement node) { | |
| 74 Statement savedFallthrough = fallthrough; | |
| 75 fallthrough = node.next; | |
| 76 node.body = visitStatement(node.body); | |
| 77 fallthrough = savedFallthrough; | |
| 78 node.next = visitStatement(node.next); | |
| 79 return node; | |
| 80 } | |
| 81 | |
| 82 Statement visitAssign(Assign node) { | |
| 83 node.definition = visitExpression(node.definition); | |
| 84 node.next = visitStatement(node.next); | |
| 85 return node; | |
| 86 } | |
| 87 | |
| 88 Statement visitReturn(Return node) { | |
| 89 node.value = visitExpression(node.value); | |
| 90 return node; | |
| 91 } | |
| 92 | |
| 93 Statement visitBreak(Break node) { | |
| 94 return node; | |
| 95 } | |
| 96 | |
| 97 Statement visitContinue(Continue node) { | |
| 98 return node; | |
| 99 } | |
| 100 | |
| 101 bool isFallthroughBreak(Statement node) { | |
| 102 return node is Break && node.target.binding.next == fallthrough; | |
| 103 } | |
| 104 | |
| 105 Statement visitIf(If node) { | |
| 106 // If one of the branches is empty (i.e. just a fallthrough), then that | |
| 107 // branch should preferrably be the 'else' so we won't have to print it. | |
| 108 // In other words, we wish to perform this rewrite: | |
| 109 // if (E) {} else {S} | |
| 110 // ==> | |
| 111 // if (!E) {S} | |
| 112 // In the tree language, empty statements do not exist yet, so we must check | |
| 113 // if one branch contains a break that can be eliminated by fallthrough. | |
| 114 | |
| 115 // Swap branches if then is a fallthrough break. | |
| 116 if (isFallthroughBreak(node.thenStatement)) { | |
| 117 node.condition = new Not(node.condition); | |
| 118 Statement tmp = node.thenStatement; | |
| 119 node.thenStatement = node.elseStatement; | |
| 120 node.elseStatement = tmp; | |
| 121 } | |
| 122 | |
| 123 // Can the else part be eliminated? | |
| 124 // (Either due to the above swap or if the break was already there). | |
| 125 bool emptyElse = isFallthroughBreak(node.elseStatement); | |
| 126 | |
| 127 node.condition = makeCondition(node.condition, true, liftNots: !emptyElse); | |
| 128 node.thenStatement = visitStatement(node.thenStatement); | |
| 129 node.elseStatement = visitStatement(node.elseStatement); | |
| 130 | |
| 131 // If neither branch is empty, eliminate a negation in the condition | |
| 132 // if (!E) S1 else S2 | |
| 133 // ==> | |
| 134 // if (E) S2 else S1 | |
| 135 if (!emptyElse && node.condition is Not) { | |
| 136 node.condition = (node.condition as Not).operand; | |
| 137 Statement tmp = node.thenStatement; | |
| 138 node.thenStatement = node.elseStatement; | |
| 139 node.elseStatement = tmp; | |
| 140 } | |
| 141 | |
| 142 return node; | |
| 143 } | |
| 144 | |
| 145 Statement visitWhileTrue(WhileTrue node) { | |
| 146 node.body = visitStatement(node.body); | |
| 147 return node; | |
| 148 } | |
| 149 | |
| 150 Statement visitWhileCondition(WhileCondition node) { | |
| 151 node.condition = makeCondition(node.condition, true, liftNots: false); | |
| 152 node.body = visitStatement(node.body); | |
| 153 node.next = visitStatement(node.next); | |
| 154 return node; | |
| 155 } | |
| 156 | |
| 157 Statement visitExpressionStatement(ExpressionStatement node) { | |
| 158 node.expression = visitExpression(node.expression); | |
| 159 node.next = visitStatement(node.next); | |
| 160 return node; | |
| 161 } | |
| 162 | |
| 163 | |
| 164 Expression visitVariable(Variable node) { | |
| 165 return node; | |
| 166 } | |
| 167 | |
| 168 Expression visitInvokeStatic(InvokeStatic node) { | |
| 169 _rewriteList(node.arguments); | |
| 170 return node; | |
| 171 } | |
| 172 | |
| 173 Expression visitInvokeMethod(InvokeMethod node) { | |
| 174 node.receiver = visitExpression(node.receiver); | |
| 175 _rewriteList(node.arguments); | |
| 176 return node; | |
| 177 } | |
| 178 | |
| 179 Expression visitInvokeSuperMethod(InvokeSuperMethod node) { | |
| 180 _rewriteList(node.arguments); | |
| 181 return node; | |
| 182 } | |
| 183 | |
| 184 Expression visitInvokeConstructor(InvokeConstructor node) { | |
| 185 _rewriteList(node.arguments); | |
| 186 return node; | |
| 187 } | |
| 188 | |
| 189 Expression visitConcatenateStrings(ConcatenateStrings node) { | |
| 190 _rewriteList(node.arguments); | |
| 191 return node; | |
| 192 } | |
| 193 | |
| 194 Expression visitLiteralList(LiteralList node) { | |
| 195 _rewriteList(node.values); | |
| 196 return node; | |
| 197 } | |
| 198 | |
| 199 Expression visitLiteralMap(LiteralMap node) { | |
| 200 node.entries.forEach((LiteralMapEntry entry) { | |
| 201 entry.key = visitExpression(entry.key); | |
| 202 entry.value = visitExpression(entry.value); | |
| 203 }); | |
| 204 return node; | |
| 205 } | |
| 206 | |
| 207 Expression visitTypeOperator(TypeOperator node) { | |
| 208 node.receiver = visitExpression(node.receiver); | |
| 209 return node; | |
| 210 } | |
| 211 | |
| 212 Expression visitConstant(Constant node) { | |
| 213 return node; | |
| 214 } | |
| 215 | |
| 216 Expression visitThis(This node) { | |
| 217 return node; | |
| 218 } | |
| 219 | |
| 220 Expression visitReifyTypeVar(ReifyTypeVar node) { | |
| 221 return node; | |
| 222 } | |
| 223 | |
| 224 Expression visitFunctionExpression(FunctionExpression node) { | |
| 225 new LogicalRewriter().rewrite(node.definition); | |
| 226 return node; | |
| 227 } | |
| 228 | |
| 229 Statement visitFunctionDeclaration(FunctionDeclaration node) { | |
| 230 new LogicalRewriter().rewrite(node.definition); | |
| 231 node.next = visitStatement(node.next); | |
| 232 return node; | |
| 233 } | |
| 234 | |
| 235 Expression visitNot(Not node) { | |
| 236 return toBoolean(makeCondition(node.operand, false, liftNots: false)); | |
| 237 } | |
| 238 | |
| 239 Expression visitConditional(Conditional node) { | |
| 240 // node.condition will be visited after the then and else parts, because its | |
| 241 // polarity depends on what rewrite we use. | |
| 242 node.thenExpression = visitExpression(node.thenExpression); | |
| 243 node.elseExpression = visitExpression(node.elseExpression); | |
| 244 | |
| 245 // In the following, we must take care not to eliminate or introduce a | |
| 246 // boolean conversion. | |
| 247 | |
| 248 // x ? true : false --> !!x | |
| 249 if (isTrue(node.thenExpression) && isFalse(node.elseExpression)) { | |
| 250 return toBoolean(makeCondition(node.condition, true, liftNots: false)); | |
| 251 } | |
| 252 // x ? false : true --> !x | |
| 253 if (isFalse(node.thenExpression) && isTrue(node.elseExpression)) { | |
| 254 return toBoolean(makeCondition(node.condition, false, liftNots: false)); | |
| 255 } | |
| 256 | |
| 257 // x ? y : false ==> x && y (if y is known to be a boolean) | |
| 258 if (isBooleanValued(node.thenExpression) && isFalse(node.elseExpression)) { | |
| 259 return new LogicalOperator.and( | |
| 260 makeCondition(node.condition, true, liftNots:false), | |
| 261 putInBooleanContext(node.thenExpression)); | |
| 262 } | |
| 263 // x ? y : true ==> !x || y (if y is known to be a boolean) | |
| 264 if (isBooleanValued(node.thenExpression) && isTrue(node.elseExpression)) { | |
| 265 return new LogicalOperator.or( | |
| 266 makeCondition(node.condition, false, liftNots: false), | |
| 267 putInBooleanContext(node.thenExpression)); | |
| 268 } | |
| 269 // x ? true : y ==> x || y (if y if known to be boolean) | |
| 270 if (isBooleanValued(node.elseExpression) && isTrue(node.thenExpression)) { | |
| 271 return new LogicalOperator.or( | |
| 272 makeCondition(node.condition, true, liftNots: false), | |
| 273 putInBooleanContext(node.elseExpression)); | |
| 274 } | |
| 275 // x ? false : y ==> !x && y (if y is known to be a boolean) | |
| 276 if (isBooleanValued(node.elseExpression) && isFalse(node.thenExpression)) { | |
| 277 return new LogicalOperator.and( | |
| 278 makeCondition(node.condition, false, liftNots: false), | |
| 279 putInBooleanContext(node.elseExpression)); | |
| 280 } | |
| 281 | |
| 282 node.condition = makeCondition(node.condition, true); | |
| 283 | |
| 284 // !x ? y : z ==> x ? z : y | |
| 285 if (node.condition is Not) { | |
| 286 node.condition = (node.condition as Not).operand; | |
| 287 Expression tmp = node.thenExpression; | |
| 288 node.thenExpression = node.elseExpression; | |
| 289 node.elseExpression = tmp; | |
| 290 } | |
| 291 | |
| 292 return node; | |
| 293 } | |
| 294 | |
| 295 Expression visitLogicalOperator(LogicalOperator node) { | |
| 296 node.left = makeCondition(node.left, true); | |
| 297 node.right = makeCondition(node.right, true); | |
| 298 return node; | |
| 299 } | |
| 300 | |
| 301 /// True if the given expression is known to evaluate to a boolean. | |
| 302 /// This will not recursively traverse [Conditional] expressions, but if | |
| 303 /// applied to the result of [visitExpression] conditionals will have been | |
| 304 /// rewritten anyway. | |
| 305 bool isBooleanValued(Expression e) { | |
| 306 return isTrue(e) || isFalse(e) || e is Not || e is LogicalOperator; | |
| 307 } | |
| 308 | |
| 309 /// Rewrite an expression that was originally processed in a non-boolean | |
| 310 /// context. | |
| 311 Expression putInBooleanContext(Expression e) { | |
| 312 if (e is Not && e.operand is Not) { | |
| 313 return (e.operand as Not).operand; | |
| 314 } else { | |
| 315 return e; | |
| 316 } | |
| 317 } | |
| 318 | |
| 319 /// Forces a boolean conversion of the given expression. | |
| 320 Expression toBoolean(Expression e) { | |
| 321 if (isBooleanValued(e)) | |
| 322 return e; | |
| 323 else | |
| 324 return new Not(new Not(e)); | |
| 325 } | |
| 326 | |
| 327 /// Creates an equivalent boolean expression. The expression must occur in a | |
| 328 /// context where its result is immediately subject to boolean conversion. | |
| 329 /// If [polarity] if false, the negated condition will be created instead. | |
| 330 /// If [liftNots] is true (default) then Not expressions will be lifted toward | |
| 331 /// the root the condition so they can be eliminated by the caller. | |
| 332 Expression makeCondition(Expression e, bool polarity, {bool liftNots:true}) { | |
| 333 if (e is Not) { | |
| 334 // !!E ==> E | |
| 335 return makeCondition(e.operand, !polarity, liftNots: liftNots); | |
| 336 } | |
| 337 if (e is LogicalOperator) { | |
| 338 // If polarity=false, then apply the rewrite !(x && y) ==> !x || !y | |
| 339 e.left = makeCondition(e.left, polarity); | |
| 340 e.right = makeCondition(e.right, polarity); | |
| 341 if (!polarity) { | |
| 342 e.isAnd = !e.isAnd; | |
| 343 } | |
| 344 // !x && !y ==> !(x || y) (only if lifting nots) | |
| 345 if (e.left is Not && e.right is Not && liftNots) { | |
| 346 e.left = (e.left as Not).operand; | |
| 347 e.right = (e.right as Not).operand; | |
| 348 e.isAnd = !e.isAnd; | |
| 349 return new Not(e); | |
| 350 } | |
| 351 return e; | |
| 352 } | |
| 353 if (e is Conditional) { | |
| 354 // Handle polarity by: !(x ? y : z) ==> x ? !y : !z | |
| 355 // Rewrite individual branches now. The condition will be rewritten | |
| 356 // when we know what polarity to use (depends on which rewrite is used). | |
| 357 e.thenExpression = makeCondition(e.thenExpression, polarity); | |
| 358 e.elseExpression = makeCondition(e.elseExpression, polarity); | |
| 359 | |
| 360 // x ? true : false ==> x | |
| 361 if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) { | |
| 362 return makeCondition(e.condition, true, liftNots: liftNots); | |
| 363 } | |
| 364 // x ? false : true ==> !x | |
| 365 if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) { | |
| 366 return makeCondition(e.condition, false, liftNots: liftNots); | |
| 367 } | |
| 368 // x ? true : y ==> x || y | |
| 369 if (isTrue(e.thenExpression)) { | |
| 370 return makeOr(makeCondition(e.condition, true), | |
| 371 e.elseExpression, | |
| 372 liftNots: liftNots); | |
| 373 } | |
| 374 // x ? false : y ==> !x && y | |
| 375 if (isFalse(e.thenExpression)) { | |
| 376 return makeAnd(makeCondition(e.condition, false), | |
| 377 e.elseExpression, | |
| 378 liftNots: liftNots); | |
| 379 } | |
| 380 // x ? y : true ==> !x || y | |
| 381 if (isTrue(e.elseExpression)) { | |
| 382 return makeOr(makeCondition(e.condition, false), | |
| 383 e.thenExpression, | |
| 384 liftNots: liftNots); | |
| 385 } | |
| 386 // x ? y : false ==> x && y | |
| 387 if (isFalse(e.elseExpression)) { | |
| 388 return makeAnd(makeCondition(e.condition, true), | |
| 389 e.thenExpression, | |
| 390 liftNots: liftNots); | |
| 391 } | |
| 392 | |
| 393 e.condition = makeCondition(e.condition, true); | |
| 394 | |
| 395 // !x ? y : z ==> x ? z : y | |
| 396 if (e.condition is Not) { | |
| 397 e.condition = (e.condition as Not).operand; | |
| 398 Expression tmp = e.thenExpression; | |
| 399 e.thenExpression = e.elseExpression; | |
| 400 e.elseExpression = tmp; | |
| 401 } | |
| 402 // x ? !y : !z ==> !(x ? y : z) (only if lifting nots) | |
| 403 if (e.thenExpression is Not && e.elseExpression is Not && liftNots) { | |
| 404 e.thenExpression = (e.thenExpression as Not).operand; | |
| 405 e.elseExpression = (e.elseExpression as Not).operand; | |
| 406 return new Not(e); | |
| 407 } | |
| 408 return e; | |
| 409 } | |
| 410 if (e is Constant && e.value.isBool) { | |
| 411 // !true ==> false | |
| 412 if (!polarity) { | |
| 413 values.BoolConstantValue value = e.value; | |
| 414 return new Constant.primitive(value.negate()); | |
| 415 } | |
| 416 return e; | |
| 417 } | |
| 418 e = visitExpression(e); | |
| 419 return polarity ? e : new Not(e); | |
| 420 } | |
| 421 | |
| 422 bool isTrue(Expression e) { | |
| 423 return e is Constant && e.value.isTrue; | |
| 424 } | |
| 425 | |
| 426 bool isFalse(Expression e) { | |
| 427 return e is Constant && e.value.isFalse; | |
| 428 } | |
| 429 | |
| 430 Expression makeAnd(Expression e1, Expression e2, {bool liftNots: true}) { | |
| 431 if (e1 is Not && e2 is Not && liftNots) { | |
| 432 return new Not(new LogicalOperator.or(e1.operand, e2.operand)); | |
| 433 } else { | |
| 434 return new LogicalOperator.and(e1, e2); | |
| 435 } | |
| 436 } | |
| 437 | |
| 438 Expression makeOr(Expression e1, Expression e2, {bool liftNots: true}) { | |
| 439 if (e1 is Not && e2 is Not && liftNots) { | |
| 440 return new Not(new LogicalOperator.and(e1.operand, e2.operand)); | |
| 441 } else { | |
| 442 return new LogicalOperator.or(e1, e2); | |
| 443 } | |
| 444 } | |
| 445 | |
| 446 /// Destructively updates each entry of [l] with the result of visiting it. | |
| 447 void _rewriteList(List<Expression> l) { | |
| 448 for (int i = 0; i < l.length; i++) { | |
| 449 l[i] = visitExpression(l[i]); | |
| 450 } | |
| 451 } | |
| 452 } | |
| 453 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 694353007:
Move dart2js from sdk/lib/_internal/compiler to pkg/compiler (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart