path: root/tool/src/test/java/org/antlr/test/TestSemanticPredicates.java

/*
 * [The "BSD license"]
 *  Copyright (c) 2010 Terence Parr
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *  1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.antlr.test;

import org.antlr.analysis.DFA;
import org.antlr.analysis.DecisionProbe;
import org.antlr.analysis.Label;
import org.antlr.codegen.CodeGenerator;
import org.antlr.misc.BitSet;
import org.antlr.runtime.Token;
import org.antlr.tool.*;
import org.junit.Test;

import java.util.List;
import java.util.Map;
import java.util.Set;

import static org.junit.Assert.*;

public class TestSemanticPredicates extends BaseTest {

	/** Public default constructor used by TestRig */
	public TestSemanticPredicates() {
	}

	@Test public void testPredsButSyntaxResolves() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? A | {p2}? B ;");
		String expecting =
			".s0-A->:s1=>1\n" +
			".s0-B->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testLL_1_Pred() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? A | {p2}? A ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testLL_1_Pred_forced_k_1() throws Exception {
		// should stop just like before w/o k set.
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a options {k=1;} : {p1}? A | {p2}? A ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testLL_2_Pred() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? A B | {p2}? A B ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-B->.s2\n" +
			".s2-{p1}?->:s3=>1\n" +
			".s2-{p2}?->:s4=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testPredicatedLoop() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : ( {p1}? A | {p2}? A )+;");
		String expecting =                   // loop back
			".s0-A->.s2\n" +
			".s0-EOF->:s1=>3\n" +
			".s2-{p1}?->:s3=>1\n" +
			".s2-{p2}?->:s4=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testPredicatedToStayInLoop() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : ( {p1}? A )+ (A)+;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n";       // loop back
        checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testAndPredicates() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? {p1a}? A | {p2}? A ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-{(p1a&&p1)}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test
    public void testOrPredicates() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : b | {p2}? A ;\n" +
			"b : {p1}? A | {p1a}? A ;");
		String expecting =
			".s0-A->.s1\n" +
            ".s1-{(p1a||p1)}?->:s2=>1\n" +
            ".s1-{p2}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testIgnoresHoistingDepthGreaterThanZero() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : A {p1}? | A {p2}?;");
		String expecting =
			".s0-A->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "A", null, null, 2, false);
	}

	@Test public void testIgnoresPredsHiddenByActions() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {a1} {p1}? A | {a2} {p2}? A ;");
		String expecting =
			".s0-A->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "A", null, null, 2, true);
	}

	@Test public void testIgnoresPredsHiddenByActionsOneAlt() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? A | {a2} {p2}? A ;"); // ok since 1 pred visible
		String expecting =
			".s0-A->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null,
					  null, null, null, null, 0, true);
	}

	/*
	@Test public void testIncompleteSemanticHoistedContextk2() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b | A B;\n" +
			"b : {p1}? A B | A B ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-B->:s2=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "A B", new int[] {1}, null, 3);
	}	
	 */

	@Test public void testHoist2() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : b | c ;\n" +
			"b : {p1}? A ;\n" +
			"c : {p2}? A ;\n");
		String expecting =
			".s0-A->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testHoistCorrectContext() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : b | {p2}? ID ;\n" +
			"b : {p1}? ID | INT ;\n");
		String expecting =  // only tests after ID, not INT :)
			".s0-ID->.s1\n" +
			".s0-INT->:s2=>1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testDefaultPredNakedAltIsLast() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : b | ID ;\n" +
			"b : {p1}? ID | INT ;\n");
		String expecting =
			".s0-ID->.s1\n" +
			".s0-INT->:s2=>1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testDefaultPredNakedAltNotLast() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : ID | b ;\n" +
			"b : {p1}? ID | INT ;\n");
		String expecting =
			".s0-ID->.s1\n" +
			".s0-INT->:s3=>2\n" +
			".s1-{!(p1)}?->:s2=>1\n" +
			".s1-{p1}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testLeftRecursivePred() throws Exception {
		// No analysis possible. but probably good to fail.  Not sure we really want
		// left-recursion even if guarded with pred.
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"s : a ;\n" +
			"a : {p1}? a | ID ;\n");
		String expecting =
			".s0-ID->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{true}?->:s3=>2\n";

		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		CodeGenerator generator = new CodeGenerator(newTool(), g, "Java");
		g.setCodeGenerator(generator);
		if ( g.getNumberOfDecisions()==0 ) {
			g.buildNFA();
			g.createLookaheadDFAs(false);
		}

		DFA dfa = g.getLookaheadDFA(1);
		assertEquals(null, dfa); // can't analyze.

		/*
		String result = serializer.serialize(dfa.startState);
		assertEquals(expecting, result);
		*/

		assertEquals("unexpected number of expected problems", 1, equeue.size());
		Message msg = equeue.errors.get(0);
		assertTrue("warning must be a left recursion msg",
				    msg instanceof LeftRecursionCyclesMessage);
	}

	@Test public void testIgnorePredFromLL2AltLastAltIsDefaultTrue() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? A B | A C | {p2}? A | {p3}? A | A ;\n");
		// two situations of note:
		// 1. A B syntax is enough to predict that alt, so p1 is not used
		//    to distinguish it from alts 2..5
		// 2. Alts 3, 4, 5 are nondeterministic with upon A.  p2, p3 and the
		//    complement of p2||p3 is sufficient to resolve the conflict. Do
		//    not include alt 1's p1 pred in the "complement of other alts"
		//    because it is not considered nondeterministic with alts 3..5
		String expecting =
			".s0-A->.s1\n" +
			".s1-B->:s2=>1\n" +
			".s1-C->:s3=>2\n" +
			".s1-{p2}?->:s4=>3\n" +
			".s1-{p3}?->:s5=>4\n" +
			".s1-{true}?->:s6=>5\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testIgnorePredFromLL2AltPredUnionNeeded() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : {p1}? A B | A C | {p2}? A | A | {p3}? A ;\n");
		// two situations of note:
		// 1. A B syntax is enough to predict that alt, so p1 is not used
		//    to distinguish it from alts 2..5
		// 2. Alts 3, 4, 5 are nondeterministic with upon A.  p2, p3 and the
		//    complement of p2||p3 is sufficient to resolve the conflict. Do
		//    not include alt 1's p1 pred in the "complement of other alts"
		//    because it is not considered nondeterministic with alts 3..5
		String expecting =
			".s0-A->.s1\n" +
			".s1-B->:s2=>1\n" +
			".s1-C->:s3=>2\n" +
			".s1-{!((p3||p2))}?->:s5=>4\n" +
			".s1-{p2}?->:s4=>3\n" +
			".s1-{p3}?->:s6=>5\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testPredGets2SymbolSyntacticContext() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : b | A B | C ;\n" +
			"b : {p1}? A B ;\n");
		String expecting =
			".s0-A->.s1\n" +
			".s0-C->:s5=>3\n" +
			".s1-B->.s2\n" +
			".s2-{p1}?->:s3=>1\n" +
			".s2-{true}?->:s4=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testMatchesLongestThenTestPred() throws Exception {
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"a : b | c ;\n" +
			"b : {p}? A ;\n" +
			"c : {q}? (A|B)+ ;");
		String expecting =
			".s0-A->.s1\n" +
			".s0-B->:s3=>2\n" +
			".s1-{p}?->:s2=>1\n" +
			".s1-{q}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testPredsUsedAfterRecursionOverflow() throws Exception {
		// analysis must bail out due to non-LL(*) nature (ovf)
		// retries with k=1 (but with LL(*) algorithm not optimized version
		// as it has preds)
		Grammar g = new Grammar(
			"parser grammar P;\n"+
			"s : {p1}? e '.' | {p2}? e ':' ;\n" +
			"e : '(' e ')' | INT ;\n");
		String expecting =
			".s0-'('->.s1\n" +
			".s0-INT->.s4\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n" +
			".s4-{p1}?->:s2=>1\n" +
			".s4-{p2}?->:s3=>2\n";
		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		CodeGenerator generator = new CodeGenerator(newTool(), g, "Java");
		g.setCodeGenerator(generator);
		if ( g.getNumberOfDecisions()==0 ) {
			g.buildNFA();
			g.createLookaheadDFAs(false);
		}

		assertEquals("unexpected number of expected problems", 0, equeue.size());
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testPredsUsedAfterK2FailsNoRecursionOverflow() throws Exception {
		// analysis must bail out due to non-LL(*) nature (ovf)
		// retries with k=1 (but with LL(*) algorithm not optimized version
		// as it has preds)
		Grammar g = new Grammar(
			"grammar P;\n" +
			"options {k=2;}\n"+
			"s : {p1}? e '.' | {p2}? e ':' ;\n" +
			"e : '(' e ')' | INT ;\n");
		String expecting =
			".s0-'('->.s1\n" +
			".s0-INT->.s6\n" +
			".s1-'('->.s2\n" +
			".s1-INT->.s5\n" +
			".s2-{p1}?->:s3=>1\n" +
			".s2-{p2}?->:s4=>2\n" +
			".s5-{p1}?->:s3=>1\n" +
			".s5-{p2}?->:s4=>2\n" +
			".s6-'.'->:s3=>1\n" +
			".s6-':'->:s4=>2\n";
		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		CodeGenerator generator = new CodeGenerator(newTool(), g, "Java");
		g.setCodeGenerator(generator);
		if ( g.getNumberOfDecisions()==0 ) {
			g.buildNFA();
			g.createLookaheadDFAs(false);
		}

		assertEquals("unexpected number of expected problems", 0, equeue.size());
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testLexerMatchesLongestThenTestPred() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"B : {p}? 'a' ;\n" +
			"C : {q}? ('a'|'b')+ ;");
		String expecting =
			".s0-'a'->.s1\n" +
			".s0-'b'->:s4=>2\n" +
			".s1-'a'..'b'->:s4=>2\n" +
			".s1-<EOT>->.s2\n" +
			".s2-{p}?->:s3=>1\n" +
			".s2-{q}?->:s4=>2\n";
		checkDecision(g, 2, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testLexerMatchesLongestMinusPred() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"B : 'a' ;\n" +
			"C : ('a'|'b')+ ;");
		String expecting =
			".s0-'a'->.s1\n" +
			".s0-'b'->:s3=>2\n" +
			".s1-'a'..'b'->:s3=>2\n" +
			".s1-<EOT>->:s2=>1\n";
		checkDecision(g, 2, expecting, null, null, null, null, null, 0, false);
	}

    @Test
    public void testGatedPred() throws Exception {
		// gated preds are present on all arcs in predictor
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"B : {p}? => 'a' ;\n" +
			"C : {q}? => ('a'|'b')+ ;");
		String expecting =
			".s0-'a'&&{(q||p)}?->.s1\n" +
            ".s0-'b'&&{q}?->:s4=>2\n" +
            ".s1-'a'..'b'&&{q}?->:s4=>2\n" +
            ".s1-<EOT>&&{(q||p)}?->.s2\n" +
            ".s2-{p}?->:s3=>1\n" +
            ".s2-{q}?->:s4=>2\n";
		checkDecision(g, 2, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testGatedPredHoistsAndCanBeInStopState() throws Exception {
		// I found a bug where merging stop states made us throw away
		// a stop state with a gated pred!
		Grammar g = new Grammar(
			"grammar u;\n" +
			"a : b+ ;\n" +
			"b : 'x' | {p}?=> 'y' ;");
		String expecting =
			".s0-'x'->:s2=>1\n" +
			".s0-'y'&&{p}?->:s3=>1\n" +
			".s0-EOF->:s1=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test
    public void testGatedPredInCyclicDFA() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : {p}?=> ('a')+ 'x' ;\n" +
			"B : {q}?=> ('a'|'b')+ 'x' ;");
		String expecting =
			".s0-'a'&&{(q||p)}?->.s1\n" +
            ".s0-'b'&&{q}?->:s5=>2\n" +
            ".s1-'a'&&{(q||p)}?->.s1\n" +
            ".s1-'b'&&{q}?->:s5=>2\n" +
            ".s1-'x'&&{(q||p)}?->.s2\n" +
            ".s2-<EOT>&&{(q||p)}?->.s3\n" +
            ".s3-{p}?->:s4=>1\n" +
            ".s3-{q}?->:s5=>2\n";
		checkDecision(g, 3, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testGatedPredNotActuallyUsedOnEdges() throws Exception {
		Grammar g = new Grammar(
			"lexer grammar P;\n"+
			"A : ('a' | {p}?=> 'a')\n" +
			"  | 'a' 'b'\n" +
			"  ;");
		String expecting1 =
			".s0-'a'->.s1\n" +
			".s1-{!(p)}?->:s2=>1\n" +  	// Used to disambig subrule
			".s1-{p}?->:s3=>2\n";
		// rule A decision can't test p from s0->1 because 'a' is valid
		// for alt1 *and* alt2 w/o p.  Can't test p from s1 to s3 because
		// we might have passed the first alt of subrule.  The same state
		// is listed in s2 in 2 different configurations: one with and one
		// w/o p.  Can't test therefore.  p||true == true.
		String expecting2 =
			".s0-'a'->.s1\n" +
			".s1-'b'->:s2=>2\n" +
			".s1-<EOT>->:s3=>1\n";
		checkDecision(g, 1, expecting1, null, null, null, null, null, 0, false);
		checkDecision(g, 2, expecting2, null, null, null, null, null, 0, false);
	}

	@Test public void testGatedPredDoesNotForceAllToBeGated() throws Exception {
		Grammar g = new Grammar(
			"grammar w;\n" +
			"a : b | c ;\n" +
			"b : {p}? B ;\n" +
			"c : {q}?=> d ;\n" +
			"d : {r}? C ;\n");
		String expecting =
			".s0-B->:s1=>1\n" +
			".s0-C&&{q}?->:s2=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testGatedPredDoesNotForceAllToBeGated2() throws Exception {
		Grammar g = new Grammar(
			"grammar w;\n" +
			"a : b | c ;\n" +
			"b : {p}? B ;\n" +
			"c : {q}?=> d ;\n" +
			"d : {r}?=> C\n" +
			"  | B\n" +
			"  ;\n");
		String expecting =
			".s0-B->.s1\n" +
			".s0-C&&{(r&&q)}?->:s3=>2\n" +
			".s1-{p}?->:s2=>1\n" +
			".s1-{q}?->:s3=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	@Test public void testORGatedPred() throws Exception {
		Grammar g = new Grammar(
			"grammar w;\n" +
			"a : b | c ;\n" +
			"b : {p}? B ;\n" +
			"c : {q}?=> d ;\n" +
			"d : {r}?=> C\n" +
			"  | {s}?=> B\n" +
			"  ;\n");
		String expecting =
			".s0-B->.s1\n" +
			".s0-C&&{(r&&q)}?->:s3=>2\n" +
			".s1-{(s&&q)}?->:s3=>2\n" +
			".s1-{p}?->:s2=>1\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	/** The following grammar should yield an error that rule 'a' has
	 *  insufficient semantic info pulled from 'b'.
	 */
	@Test public void testIncompleteSemanticHoistedContext() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b | B;\n" +
			"b : {p1}? B | B ;");
		String expecting =
			".s0-B->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "B", new int[] {1}, null, 3, false);
	}

	@Test public void testIncompleteSemanticHoistedContextk2() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b | A B;\n" +
			"b : {p1}? A B | A B ;");
		String expecting =
			".s0-A->.s1\n" +
			".s1-B->:s2=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "A B", new int[] {1}, null, 3, false);
	}

	@Test public void testIncompleteSemanticHoistedContextInFOLLOW() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"options {k=1;}\n" + // limit to k=1 because it's LL(2); force pred hoist
			"a : A? ;\n" + // need FOLLOW
			"b : X a {p1}? A | Y a A ;"); // only one A is covered
		String expecting =
			".s0-A->:s1=>1\n"; // s0-EOF->s2 branch pruned during optimization
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "A", new int[] {2}, null, 3, false);
	}

	@Test public void testIncompleteSemanticHoistedContextInFOLLOWk2() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (A B)? ;\n" + // need FOLLOW
			"b : X a {p1}? A B | Y a A B | Z a ;"); // only first alt is covered
		String expecting =
			".s0-A->.s1\n" +
			".s0-EOF->:s3=>2\n" +
			".s1-B->:s2=>1\n";
		checkDecision(g, 1, expecting, null,
					  new int[] {1,2}, "A B", new int[] {2}, null, 2, false);
	}

	@Test public void testIncompleteSemanticHoistedContextInFOLLOWDueToHiddenPred() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : (A B)? ;\n" + // need FOLLOW
			"b : X a {p1}? A B | Y a {a1} {p2}? A B | Z a ;"); // only first alt is covered
		String expecting =
			".s0-A->.s1\n" +
			".s0-EOF->:s3=>2\n" +
			".s1-B->:s2=>1\n";
		checkDecision(g, 1, expecting, null,
					  new int[] {1,2}, "A B", new int[] {2}, null, 2, true);
	}

	/** The following grammar should yield an error that rule 'a' has
	 *  insufficient semantic info pulled from 'b'.  This is the same
	 *  as the previous case except that the D prevents the B path from
	 *  "pinching" together into a single NFA state.
	 *
	 *  This test also demonstrates that just because B D could predict
	 *  alt 1 in rule 'a', it is unnecessary to continue NFA&rarr;DFA
	 *  conversion to include an edge for D.  Alt 1 is the only possible
	 *  prediction because we resolve the ambiguity by choosing alt 1.
	 */
	@Test public void testIncompleteSemanticHoistedContext2() throws Exception {
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : b | B;\n" +
			"b : {p1}? B | B D ;");
		String expecting =
			".s0-B->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2},
					  new int[] {1,2}, "B", new int[] {1},
					  null, 3, false);
	}

	@Test public void testTooFewSemanticPredicates() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : {p1}? A | A | A ;");
		String expecting =
			".s0-A->:s1=>1\n";
		checkDecision(g, 1, expecting, new int[] {2,3},
					  new int[] {1,2,3}, "A",
					  null, null, 2, false);
	}

	@Test public void testPredWithK1() throws Exception {
		Grammar g = new Grammar(
			"\tlexer grammar TLexer;\n" +
			"A\n" +
			"options {\n" +
			"  k=1;\n" +
			"}\n" +
			"  : {p1}? ('x')+ '.'\n" +
			"  | {p2}? ('x')+ '.'\n" +
			"  ;\n");
		String expecting =
			".s0-'x'->.s1\n" +
			".s1-{p1}?->:s2=>1\n" +
			".s1-{p2}?->:s3=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] insufficientPredAlts = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings, false);
	}

	@Test public void testPredWithArbitraryLookahead() throws Exception {
		Grammar g = new Grammar(
			"\tlexer grammar TLexer;\n" +
			"A : {p1}? ('x')+ '.'\n" +
			"  | {p2}? ('x')+ '.'\n" +
			"  ;\n");
		String expecting =
			".s0-'x'->.s1\n" +
			".s1-'.'->.s2\n" +
			".s1-'x'->.s1\n" +
			".s2-{p1}?->:s3=>1\n" +
			".s2-{p2}?->:s4=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] insufficientPredAlts = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings, false);
	}

	@Test
    /** For a DFA state with lots of configurations that have the same
	 *  predicate, don't just OR them all together as it's a waste to
	 *  test a||a||b||a||a etc...  ANTLR makes a unique set and THEN
	 *  OR's them together.
	 */
    public void testUniquePredicateOR() throws Exception {
		Grammar g = new Grammar(
			"parser grammar v;\n" +
			"\n" +
			"a : {a}? b\n" +
			"  | {b}? b\n" +
			"  ;\n" +
			"\n" +
			"b : {c}? (X)+ ;\n" +
			"\n" +
			"c : a\n" +
			"  | b\n" +
			"  ;\n");
		String expecting =
			".s0-X->.s1\n" +
            ".s1-{((b||a)&&c)}?->:s2=>1\n" +
            ".s1-{c}?->:s3=>2\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = null;
		String ambigInput = null;
		int[] insufficientPredAlts = null;
		int[] danglingAlts = null;
		int numWarnings = 0;
		checkDecision(g, 3, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings, false);
	}

    @Test
    public void testSemanticContextPreventsEarlyTerminationOfClosure() throws Exception {
		Grammar g = new Grammar(
			"parser grammar T;\n" +
			"a : loop SEMI | ID SEMI\n" +
			"  ;\n" +
			"loop\n" +
			"    : {while}? ID\n" +
			"    | {do}? ID\n" +
			"    | {for}? ID\n" +
			"    ;");
		String expecting =
			".s0-ID->.s1\n" +
            ".s1-SEMI->.s2\n" +
            ".s2-{(for||do||while)}?->:s3=>1\n" +
            ".s2-{true}?->:s4=>2\n";
		checkDecision(g, 1, expecting, null, null, null, null, null, 0, false);
	}

	// S U P P O R T

	public void _template() throws Exception {
		Grammar g = new Grammar(
			"parser grammar t;\n"+
			"a : A | B;");
		String expecting =
			"\n";
		int[] unreachableAlts = null;
		int[] nonDetAlts = new int[] {1,2};
		String ambigInput = "L ID R";
		int[] insufficientPredAlts = new int[] {1};
		int[] danglingAlts = null;
		int numWarnings = 1;
		checkDecision(g, 1, expecting, unreachableAlts,
					  nonDetAlts, ambigInput, insufficientPredAlts,
					  danglingAlts, numWarnings, false);
	}

	protected void checkDecision(Grammar g,
								 int decision,
								 String expecting,
								 int[] expectingUnreachableAlts,
								 int[] expectingNonDetAlts,
								 String expectingAmbigInput,
								 int[] expectingInsufficientPredAlts,
								 int[] expectingDanglingAlts,
								 int expectingNumWarnings,
								 boolean hasPredHiddenByAction)
		throws Exception
	{
		DecisionProbe.verbose=true; // make sure we get all error info
		ErrorQueue equeue = new ErrorQueue();
		ErrorManager.setErrorListener(equeue);
		CodeGenerator generator = new CodeGenerator(newTool(), g, "Java");
		g.setCodeGenerator(generator);
		// mimic actions of org.antlr.Tool first time for grammar g
		if ( g.getNumberOfDecisions()==0 ) {
			g.buildNFA();
			g.createLookaheadDFAs(false);
		}

		if ( equeue.size()!=expectingNumWarnings ) {
			System.err.println("Warnings issued: "+equeue);
		}

		assertEquals("unexpected number of expected problems",
				   expectingNumWarnings, equeue.size());

		DFA dfa = g.getLookaheadDFA(decision);
		FASerializer serializer = new FASerializer(g);
		String result = serializer.serialize(dfa.startState);
		//System.out.print(result);
		List<Integer> unreachableAlts = dfa.getUnreachableAlts();

		// make sure unreachable alts are as expected
		if ( expectingUnreachableAlts!=null ) {
			BitSet s = new BitSet();
			s.addAll(expectingUnreachableAlts);
			BitSet s2 = new BitSet();
			s2.addAll(unreachableAlts);
			assertEquals("unreachable alts mismatch", s, s2);
		}
		else {
			assertEquals("unreachable alts mismatch", 0,
						 unreachableAlts!=null?unreachableAlts.size():0);
		}

		// check conflicting input
		if ( expectingAmbigInput!=null ) {
			// first, find nondet message
			Message msg = getNonDeterminismMessage(equeue.warnings);
			assertNotNull("no nondeterminism warning?", msg);
			assertTrue("expecting nondeterminism; found "+msg.getClass().getName(),
			msg instanceof GrammarNonDeterminismMessage);
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			List<Label> labels =
				nondetMsg.probe.getSampleNonDeterministicInputSequence(nondetMsg.problemState);
			String input = nondetMsg.probe.getInputSequenceDisplay(labels);
			assertEquals(expectingAmbigInput, input);
		}

		// check nondet alts
		if ( expectingNonDetAlts!=null ) {
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			assertNotNull("found no nondet alts; expecting: "+
										str(expectingNonDetAlts), nondetMsg);
			List<Integer> nonDetAlts =
				nondetMsg.probe.getNonDeterministicAltsForState(nondetMsg.problemState);
			// compare nonDetAlts with expectingNonDetAlts
			BitSet s = new BitSet();
			s.addAll(expectingNonDetAlts);
			BitSet s2 = new BitSet();
			s2.addAll(nonDetAlts);
			assertEquals("nondet alts mismatch", s, s2);
			assertEquals("mismatch between expected hasPredHiddenByAction", hasPredHiddenByAction,
						 nondetMsg.problemState.dfa.hasPredicateBlockedByAction);
		}
		else {
			// not expecting any nondet alts, make sure there are none
			GrammarNonDeterminismMessage nondetMsg =
				getNonDeterminismMessage(equeue.warnings);
			assertNull("found nondet alts, but expecting none", nondetMsg);
		}

		if ( expectingInsufficientPredAlts!=null ) {
			GrammarInsufficientPredicatesMessage insuffPredMsg =
				getGrammarInsufficientPredicatesMessage(equeue.warnings);
			assertNotNull("found no GrammarInsufficientPredicatesMessage alts; expecting: "+
										str(expectingNonDetAlts), insuffPredMsg);
			Map<Integer, Set<Token>> locations = insuffPredMsg.altToLocations;
			Set<Integer> actualAlts = locations.keySet();
			BitSet s = new BitSet();
			s.addAll(expectingInsufficientPredAlts);
			BitSet s2 = new BitSet();
			s2.addAll(actualAlts);
			assertEquals("mismatch between insufficiently covered alts", s, s2);
			assertEquals("mismatch between expected hasPredHiddenByAction", hasPredHiddenByAction,
						 insuffPredMsg.problemState.dfa.hasPredicateBlockedByAction);
		}
		else {
			// not expecting any nondet alts, make sure there are none
			GrammarInsufficientPredicatesMessage nondetMsg =
				getGrammarInsufficientPredicatesMessage(equeue.warnings);
			if ( nondetMsg!=null ) {
				System.out.println(equeue.warnings);
			}
			assertNull("found insufficiently covered alts, but expecting none", nondetMsg);
		}

		assertEquals(expecting, result);
	}

	protected GrammarNonDeterminismMessage getNonDeterminismMessage(List<? extends Message> warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = warnings.get(i);
			if ( m instanceof GrammarNonDeterminismMessage ) {
				return (GrammarNonDeterminismMessage)m;
			}
		}
		return null;
	}

	protected GrammarInsufficientPredicatesMessage getGrammarInsufficientPredicatesMessage(List<? extends Message> warnings) {
		for (int i = 0; i < warnings.size(); i++) {
			Message m = warnings.get(i);
			if ( m instanceof GrammarInsufficientPredicatesMessage ) {
				return (GrammarInsufficientPredicatesMessage)m;
			}
		}
		return null;
	}

	protected String str(int[] elements) {
		StringBuilder buf = new StringBuilder();
		for (int i = 0; i < elements.length; i++) {
			if ( i>0 ) {
				buf.append(", ");
			}
			int element = elements[i];
			buf.append(element);
		}
		return buf.toString();
	}
}