• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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