| 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 _rewriteList(node.keys); | |
| 201 _rewriteList(node.values); | |
| 202 return node; | |
| 203 } | |
| 204 | |
| 205 Expression visitTypeOperator(TypeOperator node) { | |
| 206 node.receiver = visitExpression(node.receiver); | |
| 207 return node; | |
| 208 } | |
| 209 | |
| 210 Expression visitConstant(Constant node) { | |
| 211 return node; | |
| 212 } | |
| 213 | |
| 214 Expression visitThis(This node) { | |
| 215 return node; | |
| 216 } | |
| 217 | |
| 218 Expression visitReifyTypeVar(ReifyTypeVar node) { | |
| 219 return node; | |
| 220 } | |
| 221 | |
| 222 Expression visitFunctionExpression(FunctionExpression node) { | |
| 223 new LogicalRewriter().rewrite(node.definition); | |
| 224 return node; | |
| 225 } | |
| 226 | |
| 227 Statement visitFunctionDeclaration(FunctionDeclaration node) { | |
| 228 new LogicalRewriter().rewrite(node.definition); | |
| 229 node.next = visitStatement(node.next); | |
| 230 return node; | |
| 231 } | |
| 232 | |
| 233 Expression visitNot(Not node) { | |
| 234 return toBoolean(makeCondition(node.operand, false, liftNots: false)); | |
| 235 } | |
| 236 | |
| 237 Expression visitConditional(Conditional node) { | |
| 238 // node.condition will be visited after the then and else parts, because its | |
| 239 // polarity depends on what rewrite we use. | |
| 240 node.thenExpression = visitExpression(node.thenExpression); | |
| 241 node.elseExpression = visitExpression(node.elseExpression); | |
| 242 | |
| 243 // In the following, we must take care not to eliminate or introduce a | |
| 244 // boolean conversion. | |
| 245 | |
| 246 // x ? true : false --> !!x | |
| 247 if (isTrue(node.thenExpression) && isFalse(node.elseExpression)) { | |
| 248 return toBoolean(makeCondition(node.condition, true, liftNots: false)); | |
| 249 } | |
| 250 // x ? false : true --> !x | |
| 251 if (isFalse(node.thenExpression) && isTrue(node.elseExpression)) { | |
| 252 return toBoolean(makeCondition(node.condition, false, liftNots: false)); | |
| 253 } | |
| 254 | |
| 255 // x ? y : false ==> x && y (if y is known to be a boolean) | |
| 256 if (isBooleanValued(node.thenExpression) && isFalse(node.elseExpression)) { | |
| 257 return new LogicalOperator.and( | |
| 258 makeCondition(node.condition, true, liftNots:false), | |
| 259 putInBooleanContext(node.thenExpression)); | |
| 260 } | |
| 261 // x ? y : true ==> !x || y (if y is known to be a boolean) | |
| 262 if (isBooleanValued(node.thenExpression) && isTrue(node.elseExpression)) { | |
| 263 return new LogicalOperator.or( | |
| 264 makeCondition(node.condition, false, liftNots: false), | |
| 265 putInBooleanContext(node.thenExpression)); | |
| 266 } | |
| 267 // x ? true : y ==> x || y (if y if known to be boolean) | |
| 268 if (isBooleanValued(node.elseExpression) && isTrue(node.thenExpression)) { | |
| 269 return new LogicalOperator.or( | |
| 270 makeCondition(node.condition, true, liftNots: false), | |
| 271 putInBooleanContext(node.elseExpression)); | |
| 272 } | |
| 273 // x ? false : y ==> !x && y (if y is known to be a boolean) | |
| 274 if (isBooleanValued(node.elseExpression) && isFalse(node.thenExpression)) { | |
| 275 return new LogicalOperator.and( | |
| 276 makeCondition(node.condition, false, liftNots: false), | |
| 277 putInBooleanContext(node.elseExpression)); | |
| 278 } | |
| 279 | |
| 280 node.condition = makeCondition(node.condition, true); | |
| 281 | |
| 282 // !x ? y : z ==> x ? z : y | |
| 283 if (node.condition is Not) { | |
| 284 node.condition = (node.condition as Not).operand; | |
| 285 Expression tmp = node.thenExpression; | |
| 286 node.thenExpression = node.elseExpression; | |
| 287 node.elseExpression = tmp; | |
| 288 } | |
| 289 | |
| 290 return node; | |
| 291 } | |
| 292 | |
| 293 Expression visitLogicalOperator(LogicalOperator node) { | |
| 294 node.left = makeCondition(node.left, true); | |
| 295 node.right = makeCondition(node.right, true); | |
| 296 return node; | |
| 297 } | |
| 298 | |
| 299 /// True if the given expression is known to evaluate to a boolean. | |
| 300 /// This will not recursively traverse [Conditional] expressions, but if | |
| 301 /// applied to the result of [visitExpression] conditionals will have been | |
| 302 /// rewritten anyway. | |
| 303 bool isBooleanValued(Expression e) { | |
| 304 return isTrue(e) || isFalse(e) || e is Not || e is LogicalOperator; | |
| 305 } | |
| 306 | |
| 307 /// Rewrite an expression that was originally processed in a non-boolean | |
| 308 /// context. | |
| 309 Expression putInBooleanContext(Expression e) { | |
| 310 if (e is Not && e.operand is Not) { | |
| 311 return (e.operand as Not).operand; | |
| 312 } else { | |
| 313 return e; | |
| 314 } | |
| 315 } | |
| 316 | |
| 317 /// Forces a boolean conversion of the given expression. | |
| 318 Expression toBoolean(Expression e) { | |
| 319 if (isBooleanValued(e)) | |
| 320 return e; | |
| 321 else | |
| 322 return new Not(new Not(e)); | |
| 323 } | |
| 324 | |
| 325 /// Creates an equivalent boolean expression. The expression must occur in a | |
| 326 /// context where its result is immediately subject to boolean conversion. | |
| 327 /// If [polarity] if false, the negated condition will be created instead. | |
| 328 /// If [liftNots] is true (default) then Not expressions will be lifted toward | |
| 329 /// the root the condition so they can be eliminated by the caller. | |
| 330 Expression makeCondition(Expression e, bool polarity, {bool liftNots:true}) { | |
| 331 if (e is Not) { | |
| 332 // !!E ==> E | |
| 333 return makeCondition(e.operand, !polarity, liftNots: liftNots); | |
| 334 } | |
| 335 if (e is LogicalOperator) { | |
| 336 // If polarity=false, then apply the rewrite !(x && y) ==> !x || !y | |
| 337 e.left = makeCondition(e.left, polarity); | |
| 338 e.right = makeCondition(e.right, polarity); | |
| 339 if (!polarity) { | |
| 340 e.isAnd = !e.isAnd; | |
| 341 } | |
| 342 // !x && !y ==> !(x || y) (only if lifting nots) | |
| 343 if (e.left is Not && e.right is Not && liftNots) { | |
| 344 e.left = (e.left as Not).operand; | |
| 345 e.right = (e.right as Not).operand; | |
| 346 e.isAnd = !e.isAnd; | |
| 347 return new Not(e); | |
| 348 } | |
| 349 return e; | |
| 350 } | |
| 351 if (e is Conditional) { | |
| 352 // Handle polarity by: !(x ? y : z) ==> x ? !y : !z | |
| 353 // Rewrite individual branches now. The condition will be rewritten | |
| 354 // when we know what polarity to use (depends on which rewrite is used). | |
| 355 e.thenExpression = makeCondition(e.thenExpression, polarity); | |
| 356 e.elseExpression = makeCondition(e.elseExpression, polarity); | |
| 357 | |
| 358 // x ? true : false ==> x | |
| 359 if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) { | |
| 360 return makeCondition(e.condition, true, liftNots: liftNots); | |
| 361 } | |
| 362 // x ? false : true ==> !x | |
| 363 if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) { | |
| 364 return makeCondition(e.condition, false, liftNots: liftNots); | |
| 365 } | |
| 366 // x ? true : y ==> x || y | |
| 367 if (isTrue(e.thenExpression)) { | |
| 368 return makeOr(makeCondition(e.condition, true), | |
| 369 e.elseExpression, | |
| 370 liftNots: liftNots); | |
| 371 } | |
| 372 // x ? false : y ==> !x && y | |
| 373 if (isFalse(e.thenExpression)) { | |
| 374 return makeAnd(makeCondition(e.condition, false), | |
| 375 e.elseExpression, | |
| 376 liftNots: liftNots); | |
| 377 } | |
| 378 // x ? y : true ==> !x || y | |
| 379 if (isTrue(e.elseExpression)) { | |
| 380 return makeOr(makeCondition(e.condition, false), | |
| 381 e.thenExpression, | |
| 382 liftNots: liftNots); | |
| 383 } | |
| 384 // x ? y : false ==> x && y | |
| 385 if (isFalse(e.elseExpression)) { | |
| 386 return makeAnd(makeCondition(e.condition, true), | |
| 387 e.thenExpression, | |
| 388 liftNots: liftNots); | |
| 389 } | |
| 390 | |
| 391 e.condition = makeCondition(e.condition, true); | |
| 392 | |
| 393 // !x ? y : z ==> x ? z : y | |
| 394 if (e.condition is Not) { | |
| 395 e.condition = (e.condition as Not).operand; | |
| 396 Expression tmp = e.thenExpression; | |
| 397 e.thenExpression = e.elseExpression; | |
| 398 e.elseExpression = tmp; | |
| 399 } | |
| 400 // x ? !y : !z ==> !(x ? y : z) (only if lifting nots) | |
| 401 if (e.thenExpression is Not && e.elseExpression is Not && liftNots) { | |
| 402 e.thenExpression = (e.thenExpression as Not).operand; | |
| 403 e.elseExpression = (e.elseExpression as Not).operand; | |
| 404 return new Not(e); | |
| 405 } | |
| 406 return e; | |
| 407 } | |
| 408 if (e is Constant && e.value.isBool) { | |
| 409 // !true ==> false | |
| 410 if (!polarity) { | |
| 411 values.BoolConstantValue value = e.value; | |
| 412 return new Constant.primitive(value.negate()); | |
| 413 } | |
| 414 return e; | |
| 415 } | |
| 416 e = visitExpression(e); | |
| 417 return polarity ? e : new Not(e); | |
| 418 } | |
| 419 | |
| 420 bool isTrue(Expression e) { | |
| 421 return e is Constant && e.value.isTrue; | |
| 422 } | |
| 423 | |
| 424 bool isFalse(Expression e) { | |
| 425 return e is Constant && e.value.isFalse; | |
| 426 } | |
| 427 | |
| 428 Expression makeAnd(Expression e1, Expression e2, {bool liftNots: true}) { | |
| 429 if (e1 is Not && e2 is Not && liftNots) { | |
| 430 return new Not(new LogicalOperator.or(e1.operand, e2.operand)); | |
| 431 } else { | |
| 432 return new LogicalOperator.and(e1, e2); | |
| 433 } | |
| 434 } | |
| 435 | |
| 436 Expression makeOr(Expression e1, Expression e2, {bool liftNots: true}) { | |
| 437 if (e1 is Not && e2 is Not && liftNots) { | |
| 438 return new Not(new LogicalOperator.and(e1.operand, e2.operand)); | |
| 439 } else { | |
| 440 return new LogicalOperator.or(e1, e2); | |
| 441 } | |
| 442 } | |
| 443 | |
| 444 /// Destructively updates each entry of [l] with the result of visiting it. | |
| 445 void _rewriteList(List<Expression> l) { | |
| 446 for (int i = 0; i < l.length; i++) { | |
| 447 l[i] = visitExpression(l[i]); | |
| 448 } | |
| 449 } | |
| 450 } | |
| 451 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 692513002:
Remove old dart2js code. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart