1 /* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.analysis; 29 30 import org.antlr.codegen.CodeGenerator; 31 import org.antlr.grammar.v3.ANTLRParser; 32 import org.antlr.tool.Grammar; 33 import org.antlr.tool.GrammarAST; 34 import org.stringtemplate.v4.ST; 35 import org.stringtemplate.v4.STGroup; 36 37 import java.util.*; 38 39 /** A binary tree structure used to record the semantic context in which 40 * an NFA configuration is valid. It's either a single predicate or 41 * a tree representing an operation tree such as: p1&&p2 or p1||p2. 42 * 43 * For NFA o-p1->o-p2->o, create tree AND(p1,p2). 44 * For NFA (1)-p1->(2) 45 * | ^ 46 * | | 47 * (3)-p2---- 48 * we will have to combine p1 and p2 into DFA state as we will be 49 * adding NFA configurations for state 2 with two predicates p1,p2. 50 * So, set context for combined NFA config for state 2: OR(p1,p2). 51 * 52 * I have scoped the AND, NOT, OR, and Predicate subclasses of 53 * SemanticContext within the scope of this outer class. 54 * 55 * July 7, 2006: TJP altered OR to be set of operands. the Binary tree 56 * made it really hard to reduce complicated || sequences to their minimum. 57 * Got huge repeated || conditions. 58 */ 59 public abstract class SemanticContext { 60 /** Create a default value for the semantic context shared among all 61 * NFAConfigurations that do not have an actual semantic context. 62 * This prevents lots of if!=null type checks all over; it represents 63 * just an empty set of predicates. 64 */ 65 public static final SemanticContext EMPTY_SEMANTIC_CONTEXT = new Predicate(Predicate.INVALID_PRED_VALUE); 66 67 /** Given a semantic context expression tree, return a tree with all 68 * nongated predicates set to true and then reduced. So p&&(q||r) would 69 * return p&&r if q is nongated but p and r are gated. 70 */ getGatedPredicateContext()71 public abstract SemanticContext getGatedPredicateContext(); 72 73 /** Generate an expression that will evaluate the semantic context, 74 * given a set of output templates. 75 */ genExpr(CodeGenerator generator, STGroup templates, DFA dfa)76 public abstract ST genExpr(CodeGenerator generator, 77 STGroup templates, 78 DFA dfa); 79 hasUserSemanticPredicate()80 public abstract boolean hasUserSemanticPredicate(); // user-specified sempred {}? or {}?=> isSyntacticPredicate()81 public abstract boolean isSyntacticPredicate(); 82 83 /** Notify the indicated grammar of any syn preds used within this context */ trackUseOfSyntacticPredicates(Grammar g)84 public void trackUseOfSyntacticPredicates(Grammar g) { 85 } 86 87 public static class Predicate extends SemanticContext { 88 /** The AST node in tree created from the grammar holding the predicate */ 89 public GrammarAST predicateAST; 90 91 /** Is this a {...}?=> gating predicate or a normal disambiguating {..}? 92 * If any predicate in expression is gated, then expression is considered 93 * gated. 94 * 95 * The simple Predicate object's predicate AST's type is used to set 96 * gated to true if type==GATED_SEMPRED. 97 */ 98 protected boolean gated = false; 99 100 /** syntactic predicates are converted to semantic predicates 101 * but synpreds are generated slightly differently. 102 */ 103 protected boolean synpred = false; 104 105 public static final int INVALID_PRED_VALUE = -2; 106 public static final int FALSE_PRED = 0; 107 public static final int TRUE_PRED = ~0; 108 109 /** sometimes predicates are known to be true or false; we need 110 * a way to represent this without resorting to a target language 111 * value like true or TRUE. 112 */ 113 protected int constantValue = INVALID_PRED_VALUE; 114 Predicate(int constantValue)115 public Predicate(int constantValue) { 116 predicateAST = new GrammarAST(); 117 this.constantValue=constantValue; 118 } 119 Predicate(GrammarAST predicate)120 public Predicate(GrammarAST predicate) { 121 this.predicateAST = predicate; 122 this.gated = 123 predicate.getType()==ANTLRParser.GATED_SEMPRED || 124 predicate.getType()==ANTLRParser.SYN_SEMPRED ; 125 this.synpred = 126 predicate.getType()==ANTLRParser.SYN_SEMPRED || 127 predicate.getType()==ANTLRParser.BACKTRACK_SEMPRED; 128 } 129 Predicate(Predicate p)130 public Predicate(Predicate p) { 131 this.predicateAST = p.predicateAST; 132 this.gated = p.gated; 133 this.synpred = p.synpred; 134 this.constantValue = p.constantValue; 135 } 136 137 /** Two predicates are the same if they are literally the same 138 * text rather than same node in the grammar's AST. 139 * Or, if they have the same constant value, return equal. 140 * As of July 2006 I'm not sure these are needed. 141 */ 142 @Override equals(Object o)143 public boolean equals(Object o) { 144 if ( !(o instanceof Predicate) ) { 145 return false; 146 } 147 148 Predicate other = (Predicate)o; 149 if (this.constantValue != other.constantValue){ 150 return false; 151 } 152 153 if (this.constantValue != INVALID_PRED_VALUE){ 154 return true; 155 } 156 157 return predicateAST.getText().equals(other.predicateAST.getText()); 158 } 159 160 @Override hashCode()161 public int hashCode() { 162 if (constantValue != INVALID_PRED_VALUE){ 163 return constantValue; 164 } 165 166 if ( predicateAST ==null ) { 167 return 0; 168 } 169 170 return predicateAST.getText().hashCode(); 171 } 172 173 @Override genExpr(CodeGenerator generator, STGroup templates, DFA dfa)174 public ST genExpr(CodeGenerator generator, 175 STGroup templates, 176 DFA dfa) 177 { 178 ST eST; 179 if ( templates!=null ) { 180 if ( synpred ) { 181 eST = templates.getInstanceOf("evalSynPredicate"); 182 } 183 else { 184 eST = templates.getInstanceOf("evalPredicate"); 185 generator.grammar.decisionsWhoseDFAsUsesSemPreds.add(dfa); 186 } 187 String predEnclosingRuleName = predicateAST.enclosingRuleName; 188 /* 189 String decisionEnclosingRuleName = 190 dfa.getNFADecisionStartState().getEnclosingRule(); 191 // if these rulenames are diff, then pred was hoisted out of rule 192 // Currently I don't warn you about this as it could be annoying. 193 // I do the translation anyway. 194 */ 195 //eST.add("pred", this.toString()); 196 if ( generator!=null ) { 197 eST.add("pred", 198 generator.translateAction(predEnclosingRuleName,predicateAST)); 199 } 200 } 201 else { 202 eST = new ST("<pred>"); 203 eST.add("pred", this.toString()); 204 return eST; 205 } 206 if ( generator!=null ) { 207 String description = 208 generator.target.getTargetStringLiteralFromString(this.toString()); 209 eST.add("description", description); 210 } 211 return eST; 212 } 213 214 @Override getGatedPredicateContext()215 public SemanticContext getGatedPredicateContext() { 216 if ( gated ) { 217 return this; 218 } 219 return null; 220 } 221 222 @Override hasUserSemanticPredicate()223 public boolean hasUserSemanticPredicate() { // user-specified sempred 224 return predicateAST !=null && 225 ( predicateAST.getType()==ANTLRParser.GATED_SEMPRED || 226 predicateAST.getType()==ANTLRParser.SEMPRED ); 227 } 228 229 @Override isSyntacticPredicate()230 public boolean isSyntacticPredicate() { 231 return predicateAST !=null && 232 ( predicateAST.getType()==ANTLRParser.SYN_SEMPRED || 233 predicateAST.getType()==ANTLRParser.BACKTRACK_SEMPRED ); 234 } 235 236 @Override trackUseOfSyntacticPredicates(Grammar g)237 public void trackUseOfSyntacticPredicates(Grammar g) { 238 if ( synpred ) { 239 g.synPredNamesUsedInDFA.add(predicateAST.getText()); 240 } 241 } 242 243 @Override toString()244 public String toString() { 245 if ( predicateAST ==null ) { 246 return "<nopred>"; 247 } 248 return predicateAST.getText(); 249 } 250 } 251 252 public static class TruePredicate extends Predicate { TruePredicate()253 public TruePredicate() { 254 super(TRUE_PRED); 255 } 256 257 @Override genExpr(CodeGenerator generator, STGroup templates, DFA dfa)258 public ST genExpr(CodeGenerator generator, 259 STGroup templates, 260 DFA dfa) 261 { 262 if ( templates!=null ) { 263 return templates.getInstanceOf("true_value"); 264 } 265 return new ST("true"); 266 } 267 268 @Override hasUserSemanticPredicate()269 public boolean hasUserSemanticPredicate() { 270 return false; // not user specified. 271 } 272 273 @Override toString()274 public String toString() { 275 return "true"; // not used for code gen, just DOT and print outs 276 } 277 } 278 279 public static class FalsePredicate extends Predicate { FalsePredicate()280 public FalsePredicate() { 281 super(FALSE_PRED); 282 } 283 284 @Override genExpr(CodeGenerator generator, STGroup templates, DFA dfa)285 public ST genExpr(CodeGenerator generator, 286 STGroup templates, 287 DFA dfa) 288 { 289 if ( templates!=null ) { 290 return templates.getInstanceOf("false"); 291 } 292 return new ST("false"); 293 } 294 295 @Override hasUserSemanticPredicate()296 public boolean hasUserSemanticPredicate() { 297 return false; // not user specified. 298 } 299 300 @Override toString()301 public String toString() { 302 return "false"; // not used for code gen, just DOT and print outs 303 } 304 } 305 306 public static abstract class CommutativePredicate extends SemanticContext { 307 protected final Set<SemanticContext> operands = new HashSet<SemanticContext>(); 308 protected int hashcode; 309 CommutativePredicate(SemanticContext a, SemanticContext b)310 public CommutativePredicate(SemanticContext a, SemanticContext b) { 311 if (a.getClass() == this.getClass()){ 312 CommutativePredicate predicate = (CommutativePredicate)a; 313 operands.addAll(predicate.operands); 314 } else { 315 operands.add(a); 316 } 317 318 if (b.getClass() == this.getClass()){ 319 CommutativePredicate predicate = (CommutativePredicate)b; 320 operands.addAll(predicate.operands); 321 } else { 322 operands.add(b); 323 } 324 325 hashcode = calculateHashCode(); 326 } 327 CommutativePredicate(HashSet<SemanticContext> contexts)328 public CommutativePredicate(HashSet<SemanticContext> contexts){ 329 for (SemanticContext context : contexts){ 330 if (context.getClass() == this.getClass()){ 331 CommutativePredicate predicate = (CommutativePredicate)context; 332 operands.addAll(predicate.operands); 333 } else { 334 operands.add(context); 335 } 336 } 337 338 hashcode = calculateHashCode(); 339 } 340 341 @Override getGatedPredicateContext()342 public SemanticContext getGatedPredicateContext() { 343 SemanticContext result = null; 344 for (SemanticContext semctx : operands) { 345 SemanticContext gatedPred = semctx.getGatedPredicateContext(); 346 if ( gatedPred!=null ) { 347 result = combinePredicates(result, gatedPred); 348 } 349 } 350 return result; 351 } 352 353 @Override hasUserSemanticPredicate()354 public boolean hasUserSemanticPredicate() { 355 for (SemanticContext semctx : operands) { 356 if ( semctx.hasUserSemanticPredicate() ) { 357 return true; 358 } 359 } 360 return false; 361 } 362 363 @Override isSyntacticPredicate()364 public boolean isSyntacticPredicate() { 365 for (SemanticContext semctx : operands) { 366 if ( semctx.isSyntacticPredicate() ) { 367 return true; 368 } 369 } 370 return false; 371 } 372 373 @Override trackUseOfSyntacticPredicates(Grammar g)374 public void trackUseOfSyntacticPredicates(Grammar g) { 375 for (SemanticContext semctx : operands) { 376 semctx.trackUseOfSyntacticPredicates(g); 377 } 378 } 379 380 @Override equals(Object obj)381 public boolean equals(Object obj) { 382 if (this == obj) 383 return true; 384 385 if (obj.getClass() == this.getClass()) { 386 CommutativePredicate commutative = (CommutativePredicate)obj; 387 Set<SemanticContext> otherOperands = commutative.operands; 388 if (operands.size() != otherOperands.size()) 389 return false; 390 391 return operands.containsAll(otherOperands); 392 } 393 394 if (obj instanceof NOT) 395 { 396 NOT not = (NOT)obj; 397 if (not.ctx instanceof CommutativePredicate && not.ctx.getClass() != this.getClass()) { 398 Set<SemanticContext> otherOperands = ((CommutativePredicate)not.ctx).operands; 399 if (operands.size() != otherOperands.size()) 400 return false; 401 402 ArrayList<SemanticContext> temp = new ArrayList<SemanticContext>(operands.size()); 403 for (SemanticContext context : otherOperands) { 404 temp.add(not(context)); 405 } 406 407 return operands.containsAll(temp); 408 } 409 } 410 411 return false; 412 } 413 414 @Override hashCode()415 public int hashCode(){ 416 return hashcode; 417 } 418 419 @Override toString()420 public String toString() { 421 StringBuilder buf = new StringBuilder(); 422 buf.append("("); 423 int i = 0; 424 for (SemanticContext semctx : operands) { 425 if ( i>0 ) { 426 buf.append(getOperandString()); 427 } 428 buf.append(semctx.toString()); 429 i++; 430 } 431 buf.append(")"); 432 return buf.toString(); 433 } 434 getOperandString()435 public abstract String getOperandString(); 436 combinePredicates(SemanticContext left, SemanticContext right)437 public abstract SemanticContext combinePredicates(SemanticContext left, SemanticContext right); 438 calculateHashCode()439 public abstract int calculateHashCode(); 440 } 441 442 public static class AND extends CommutativePredicate { AND(SemanticContext a, SemanticContext b)443 public AND(SemanticContext a, SemanticContext b) { 444 super(a,b); 445 } 446 AND(HashSet<SemanticContext> contexts)447 public AND(HashSet<SemanticContext> contexts) { 448 super(contexts); 449 } 450 451 @Override genExpr(CodeGenerator generator, STGroup templates, DFA dfa)452 public ST genExpr(CodeGenerator generator, 453 STGroup templates, 454 DFA dfa) 455 { 456 ST result = null; 457 for (SemanticContext operand : operands) { 458 if (result == null) { 459 result = operand.genExpr(generator, templates, dfa); 460 continue; 461 } 462 463 ST eST; 464 if ( templates!=null ) { 465 eST = templates.getInstanceOf("andPredicates"); 466 } 467 else { 468 eST = new ST("(<left>&&<right>)"); 469 } 470 eST.add("left", result); 471 eST.add("right", operand.genExpr(generator,templates,dfa)); 472 result = eST; 473 } 474 475 return result; 476 } 477 478 @Override getOperandString()479 public String getOperandString() { 480 return "&&"; 481 } 482 483 @Override combinePredicates(SemanticContext left, SemanticContext right)484 public SemanticContext combinePredicates(SemanticContext left, SemanticContext right) { 485 return SemanticContext.and(left, right); 486 } 487 488 @Override calculateHashCode()489 public int calculateHashCode() { 490 int hashcode = 0; 491 for (SemanticContext context : operands) { 492 hashcode = hashcode ^ context.hashCode(); 493 } 494 495 return hashcode; 496 } 497 } 498 499 public static class OR extends CommutativePredicate { OR(SemanticContext a, SemanticContext b)500 public OR(SemanticContext a, SemanticContext b) { 501 super(a,b); 502 } 503 OR(HashSet<SemanticContext> contexts)504 public OR(HashSet<SemanticContext> contexts) { 505 super(contexts); 506 } 507 508 @Override genExpr(CodeGenerator generator, STGroup templates, DFA dfa)509 public ST genExpr(CodeGenerator generator, 510 STGroup templates, 511 DFA dfa) 512 { 513 ST eST; 514 if ( templates!=null ) { 515 eST = templates.getInstanceOf("orPredicates"); 516 } 517 else { 518 eST = new ST("(<operands; separator=\"||\">)"); 519 } 520 for (SemanticContext semctx : operands) { 521 eST.add("operands", semctx.genExpr(generator,templates,dfa)); 522 } 523 return eST; 524 } 525 526 @Override getOperandString()527 public String getOperandString() { 528 return "||"; 529 } 530 531 @Override combinePredicates(SemanticContext left, SemanticContext right)532 public SemanticContext combinePredicates(SemanticContext left, SemanticContext right) { 533 return SemanticContext.or(left, right); 534 } 535 536 @Override calculateHashCode()537 public int calculateHashCode() { 538 int hashcode = 0; 539 for (SemanticContext context : operands) { 540 hashcode = ~hashcode ^ context.hashCode(); 541 } 542 543 return hashcode; 544 } 545 } 546 547 public static class NOT extends SemanticContext { 548 protected SemanticContext ctx; NOT(SemanticContext ctx)549 public NOT(SemanticContext ctx) { 550 this.ctx = ctx; 551 } 552 553 @Override genExpr(CodeGenerator generator, STGroup templates, DFA dfa)554 public ST genExpr(CodeGenerator generator, 555 STGroup templates, 556 DFA dfa) 557 { 558 ST eST; 559 if ( templates!=null ) { 560 eST = templates.getInstanceOf("notPredicate"); 561 } 562 else { 563 eST = new ST("!(<pred>)"); 564 } 565 eST.add("pred", ctx.genExpr(generator,templates,dfa)); 566 return eST; 567 } 568 569 @Override getGatedPredicateContext()570 public SemanticContext getGatedPredicateContext() { 571 SemanticContext p = ctx.getGatedPredicateContext(); 572 if ( p==null ) { 573 return null; 574 } 575 return new NOT(p); 576 } 577 578 @Override hasUserSemanticPredicate()579 public boolean hasUserSemanticPredicate() { 580 return ctx.hasUserSemanticPredicate(); 581 } 582 583 @Override isSyntacticPredicate()584 public boolean isSyntacticPredicate() { 585 return ctx.isSyntacticPredicate(); 586 } 587 588 @Override trackUseOfSyntacticPredicates(Grammar g)589 public void trackUseOfSyntacticPredicates(Grammar g) { 590 ctx.trackUseOfSyntacticPredicates(g); 591 } 592 593 @Override equals(Object object)594 public boolean equals(Object object) { 595 if ( !(object instanceof NOT) ) { 596 return false; 597 } 598 return this.ctx.equals(((NOT)object).ctx); 599 } 600 601 @Override hashCode()602 public int hashCode() { 603 return ~ctx.hashCode(); 604 } 605 606 @Override toString()607 public String toString() { 608 return "!("+ctx+")"; 609 } 610 } 611 and(SemanticContext a, SemanticContext b)612 public static SemanticContext and(SemanticContext a, SemanticContext b) { 613 //System.out.println("AND: "+a+"&&"+b); 614 if (a instanceof FalsePredicate || b instanceof FalsePredicate) 615 return new FalsePredicate(); 616 617 SemanticContext[] terms = factorOr(a, b); 618 SemanticContext commonTerms = terms[0]; 619 a = terms[1]; 620 b = terms[2]; 621 622 boolean factored = commonTerms != null && commonTerms != EMPTY_SEMANTIC_CONTEXT && !(commonTerms instanceof TruePredicate); 623 if (factored) { 624 return or(commonTerms, and(a, b)); 625 } 626 627 //System.Console.Out.WriteLine( "AND: " + a + "&&" + b ); 628 if (a instanceof FalsePredicate || b instanceof FalsePredicate) 629 return new FalsePredicate(); 630 631 if ( a==EMPTY_SEMANTIC_CONTEXT || a==null ) { 632 return b; 633 } 634 if ( b==EMPTY_SEMANTIC_CONTEXT || b==null ) { 635 return a; 636 } 637 638 if (a instanceof TruePredicate) 639 return b; 640 641 if (b instanceof TruePredicate) 642 return a; 643 644 //// Factoring takes care of this case 645 //if (a.Equals(b)) 646 // return a; 647 648 //System.out.println("## have to AND"); 649 AND result = new AND(a,b); 650 if (result.operands.size() == 1) { 651 return result.operands.iterator().next(); 652 } 653 654 return result; 655 } 656 or(SemanticContext a, SemanticContext b)657 public static SemanticContext or(SemanticContext a, SemanticContext b) { 658 //System.out.println("OR: "+a+"||"+b); 659 if (a instanceof TruePredicate || b instanceof TruePredicate) 660 return new TruePredicate(); 661 662 SemanticContext[] terms = factorAnd(a, b); 663 SemanticContext commonTerms = terms[0]; 664 a = terms[1]; 665 b = terms[2]; 666 boolean factored = commonTerms != null && commonTerms != EMPTY_SEMANTIC_CONTEXT && !(commonTerms instanceof FalsePredicate); 667 if (factored) { 668 return and(commonTerms, or(a, b)); 669 } 670 671 if ( a==EMPTY_SEMANTIC_CONTEXT || a==null || a instanceof FalsePredicate ) { 672 return b; 673 } 674 675 if ( b==EMPTY_SEMANTIC_CONTEXT || b==null || b instanceof FalsePredicate ) { 676 return a; 677 } 678 679 if ( a instanceof TruePredicate || b instanceof TruePredicate || commonTerms instanceof TruePredicate ) { 680 return new TruePredicate(); 681 } 682 683 //// Factoring takes care of this case 684 //if (a.equals(b)) 685 // return a; 686 687 if ( a instanceof NOT ) { 688 NOT n = (NOT)a; 689 // check for !p||p 690 if ( n.ctx.equals(b) ) { 691 return new TruePredicate(); 692 } 693 } 694 else if ( b instanceof NOT ) { 695 NOT n = (NOT)b; 696 // check for p||!p 697 if ( n.ctx.equals(a) ) { 698 return new TruePredicate(); 699 } 700 } 701 702 //System.out.println("## have to OR"); 703 OR result = new OR(a,b); 704 if (result.operands.size() == 1) 705 return result.operands.iterator().next(); 706 707 return result; 708 } 709 not(SemanticContext a)710 public static SemanticContext not(SemanticContext a) { 711 if (a instanceof NOT) { 712 return ((NOT)a).ctx; 713 } 714 715 if (a instanceof TruePredicate) 716 return new FalsePredicate(); 717 else if (a instanceof FalsePredicate) 718 return new TruePredicate(); 719 720 return new NOT(a); 721 } 722 723 // Factor so (a && b) == (result && a && b) factorAnd(SemanticContext a, SemanticContext b)724 public static SemanticContext[] factorAnd(SemanticContext a, SemanticContext b) 725 { 726 if (a == EMPTY_SEMANTIC_CONTEXT || a == null || a instanceof FalsePredicate) 727 return new SemanticContext[] { EMPTY_SEMANTIC_CONTEXT, a, b }; 728 if (b == EMPTY_SEMANTIC_CONTEXT || b == null || b instanceof FalsePredicate) 729 return new SemanticContext[] { EMPTY_SEMANTIC_CONTEXT, a, b }; 730 731 if (a instanceof TruePredicate || b instanceof TruePredicate) 732 { 733 return new SemanticContext[] { new TruePredicate(), EMPTY_SEMANTIC_CONTEXT, EMPTY_SEMANTIC_CONTEXT }; 734 } 735 736 HashSet<SemanticContext> opsA = new HashSet<SemanticContext>(getAndOperands(a)); 737 HashSet<SemanticContext> opsB = new HashSet<SemanticContext>(getAndOperands(b)); 738 739 HashSet<SemanticContext> result = new HashSet<SemanticContext>(opsA); 740 result.retainAll(opsB); 741 if (result.isEmpty()) 742 return new SemanticContext[] { EMPTY_SEMANTIC_CONTEXT, a, b }; 743 744 opsA.removeAll(result); 745 if (opsA.isEmpty()) 746 a = new TruePredicate(); 747 else if (opsA.size() == 1) 748 a = opsA.iterator().next(); 749 else 750 a = new AND(opsA); 751 752 opsB.removeAll(result); 753 if (opsB.isEmpty()) 754 b = new TruePredicate(); 755 else if (opsB.size() == 1) 756 b = opsB.iterator().next(); 757 else 758 b = new AND(opsB); 759 760 if (result.size() == 1) 761 return new SemanticContext[] { result.iterator().next(), a, b }; 762 763 return new SemanticContext[] { new AND(result), a, b }; 764 } 765 766 // Factor so (a || b) == (result || a || b) factorOr(SemanticContext a, SemanticContext b)767 public static SemanticContext[] factorOr(SemanticContext a, SemanticContext b) 768 { 769 HashSet<SemanticContext> opsA = new HashSet<SemanticContext>(getOrOperands(a)); 770 HashSet<SemanticContext> opsB = new HashSet<SemanticContext>(getOrOperands(b)); 771 772 HashSet<SemanticContext> result = new HashSet<SemanticContext>(opsA); 773 result.retainAll(opsB); 774 if (result.isEmpty()) 775 return new SemanticContext[] { EMPTY_SEMANTIC_CONTEXT, a, b }; 776 777 opsA.removeAll(result); 778 if (opsA.isEmpty()) 779 a = new FalsePredicate(); 780 else if (opsA.size() == 1) 781 a = opsA.iterator().next(); 782 else 783 a = new OR(opsA); 784 785 opsB.removeAll(result); 786 if (opsB.isEmpty()) 787 b = new FalsePredicate(); 788 else if (opsB.size() == 1) 789 b = opsB.iterator().next(); 790 else 791 b = new OR(opsB); 792 793 if (result.size() == 1) 794 return new SemanticContext[] { result.iterator().next(), a, b }; 795 796 return new SemanticContext[] { new OR(result), a, b }; 797 } 798 getAndOperands(SemanticContext context)799 public static Collection<SemanticContext> getAndOperands(SemanticContext context) 800 { 801 if (context instanceof AND) 802 return ((AND)context).operands; 803 804 if (context instanceof NOT) { 805 Collection<SemanticContext> operands = getOrOperands(((NOT)context).ctx); 806 List<SemanticContext> result = new ArrayList<SemanticContext>(operands.size()); 807 for (SemanticContext operand : operands) { 808 result.add(not(operand)); 809 } 810 return result; 811 } 812 813 ArrayList<SemanticContext> result = new ArrayList<SemanticContext>(); 814 result.add(context); 815 return result; 816 } 817 getOrOperands(SemanticContext context)818 public static Collection<SemanticContext> getOrOperands(SemanticContext context) 819 { 820 if (context instanceof OR) 821 return ((OR)context).operands; 822 823 if (context instanceof NOT) { 824 Collection<SemanticContext> operands = getAndOperands(((NOT)context).ctx); 825 List<SemanticContext> result = new ArrayList<SemanticContext>(operands.size()); 826 for (SemanticContext operand : operands) { 827 result.add(not(operand)); 828 } 829 return result; 830 } 831 832 ArrayList<SemanticContext> result = new ArrayList<SemanticContext>(); 833 result.add(context); 834 return result; 835 } 836 } 837