import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import junit.framework.TestCase;

/*
 * Created on Feb 4, 2004
 */

/**
 * @author David Matuszek
 * @version Feb 6, 2004
 */
public class DavesParserTest extends TestCase {
    Parser parser;
    /**
     * Constructor for DavesParserTest.
     * @param arg0
     */
    public DavesParserTest(String arg0) {
        super(arg0);
    }
    
    protected void setUp() throws Exception {
        super.setUp();
    }

    public void testParser() {
        parser = new Parser("");
        parser = new Parser("2 + 2");
    }

    public void testExpression() {
        Tree expected;
        
        use("250");
        assertTrue(parser.expression());
        assertStackIs("250");
        
        use("hello");
        assertTrue(parser.expression());
        assertStackIs("hello");

        use("(xyz + 3)");
        assertTrue(parser.expression());
        assertStackIs("+{xyz 3}");

        use("a + b + c");
        assertTrue(parser.expression());
        assertStackIs("+{+{a b} c}");

        use("3 * 12 - 7");
        assertTrue(parser.expression());
        assertStackIs("- { *{3 12} 7}");

        use("12 * 5 - 3 * 4 / 6 + 8");
        assertTrue(parser.expression());
        assertStackIs("+{ -{ *{12 5} /{ *{3 4} 6}} 8}");
                     
        use("12 * ((5 - 3) * 4) / 6 + (8)");
        assertTrue(parser.expression());
        assertStackIs("+{ /{ *{12 *{ -{5 3} 4}} 6} 8}");
        
        use("");
        assertFalse(parser.expression());
        
        use("#");
        assertFalse(parser.expression());

        try {
            use("17 +");
            assertFalse(parser.expression());
            fail();
        }
        catch (LogoException e) {
        }
        try {
            use("22 *");
            assertFalse(parser.expression());
            fail();
        }
        catch (LogoException e) {
        }
    }

    public void testTerm() {        
        use("12");
        assertTrue(parser.term());
        assertStackIs("12");

        use("3*12");
        assertTrue(parser.term());
        Tree expected = tree("*{3 12}");
        Tree actual = (Tree) stackTop();
        assertEquals(expected, actual);
        assertEquals(tree("*{3 12}"), actual);

        use("x * y * z");
        assertTrue(parser.term());
        assertStackIs("*{ *{x y} z}");
        
        use("20 * 3 / 4");
        assertTrue(parser.term());
        assertStackIs("/{ *{20 3} 4}");

        use("20 * 3 / 4 + 5");
        assertTrue(parser.term());
        assertStackIs("/{ *{20 3} 4}");
        unused("+ 5");
        
        use("");
        assertFalse(parser.term());
        unused("");
        
        use("#");
        assertFalse(parser.term());unused("#");

    }

    public void testFactor() {
        use("12");
        assertTrue(parser.factor());
        assertStackIs("12");

        use("hello");
        assertTrue(parser.factor());
        assertStackIs("hello");
        
        use("(xyz + 3)");
        assertTrue(parser.factor());
        assertStackIs("+{xyz 3}");
        
        use("12 * 5");
        assertTrue(parser.factor());
        assertStackIs("12");
        unused("* 5");
        
        use("17 +");
        assertTrue(parser.factor());
        assertStackIs("17");
        unused("+");

        use("");
        assertFalse(parser.factor());
        unused("");
        
        use("#");
        assertFalse(parser.factor());
        unused("#");
    }

    public void testAddOperator() {
        use("+ - + $");
        assertTrue(parser.addOperator());
        assertTrue(parser.addOperator());
        assertTrue(parser.addOperator());
        assertFalse(parser.addOperator());
        unused("$");
    }

    public void testMultiplyOperator() {
        use("* / $");
        assertTrue(parser.multiplyOperator());
        assertTrue(parser.multiplyOperator());
        assertFalse(parser.multiplyOperator());
        unused("$");
    }
    
    public void testMove() {
        use("move 5 \n");
        assertTrue(parser.command());
        assertStackIs("move{5}");

        use("move x + 5 \n");
        assertTrue(parser.command());
        assertStackIs("move{ +{x 5}}");
    }
    
    public void testDirection() {
        use("north");
        assertTrue(parser.direction());
        assertStackIs("direction{north}");
        
        use("south east west");
        assertTrue(parser.direction());
        assertStackIs("direction{south}");
        use("east");
        assertTrue(parser.direction());
        assertStackIs("direction{east}");
        use("west");
        assertTrue(parser.direction());
        assertStackIs("direction{west}");
        

        use("left \n");
        assertTrue(parser.direction());
        assertStackIs("direction{left}");
        use("right \n");
        assertTrue(parser.direction());
        assertStackIs("direction{right}");
        
        use("left 45");
        assertTrue(parser.direction());
        assertStackIs("direction{left 45}");
        
        use("right 2 + 2");
        Tree two = makeTreeNode("2");
        assertTrue(parser.direction());
        assertStackIs("direction{right +{2 2}}");
    }
    
    public void testTurn() {
        use("turn north \n");
        assertTrue(parser.command());
        assertStackIs("turn{direction{north}}");
        
    }
    
    public void testPenup() {
        use("penup \n");
        assertTrue(parser.command());
        assertStackIs("penup");
    }
    
    public void testPendown() {
        use("pendown \n");
        assertTrue(parser.command());
        assertStackIs("pendown");
    }
    
    public void testColor() {
        use("color red \n");
        assertTrue(parser.command());
        assertStackIs("color{red}");

        String[] colors = new String[] { "magenta", "red", "orange",
                                        "yellow", "green", "aqua",
                                        "blue", "purple", "violet",
                                        "brown", "black", "charcoal",
                                        "gray", "grey", "white", "pink" };
        for (String color : colors) {
            use(color);
            assertTrue(parser.colorName());
        }

        use("color red;\n .");
        try {
            parser.command();
            fail("Color name not followed by EOL");
        }
        catch (LogoException e) {
        }
    }
    
    public void testHome() {
        use("home \n");
        assertTrue(parser.command());
        assertStackIs("home");
    }
    
    public void testAssignment() {
        use("x = 5 \n");
        assertTrue(parser.command());
        assertStackIs("={x 5}");
        
        use("x = 2 + 3\n");
        assertTrue(parser.command());
        assertStackIs("={x +{2 3}}");
    }
    
    public void testRepeat() {
        use("repeat 2 + 2 [\n penup \n ]\n");
        assertTrue(parser.command());
        assertStackIs("repeat{ +{2 2} block{penup}}");
    }
    
    public void testWhile() {
        use("while x > y [\n penup \n ]\n");
        assertTrue(parser.command());
        assertStackIs("while{ >{x y} block{penup}}");
    }
    
    public void testIf() {
        use("if 2 + 2 = 4 [ \n penup \n ] \n");
        assertTrue(parser.command());
        assertStackIs("if{ ={ +{2 2} 4} block{penup}}");

        use("if 2 + 2 = 4 [ \n penup \n ] \n else [ \n pendown \n ] \n");
        assertTrue(parser.command());
        assertStackIs("if{ ={ +{2 2} 4} block{penup} block{pendown}}");
    }
    
    public void testCall() {
        use("call foo 1 2 + 3 x \n");
        assertTrue(parser.command());
        assertStackIs("call{foo 1 +{2 3} x}");
    }

    public void testBlock() {
        use("[ \n penup \n pendown \n pendown \n ] \n");
        assertTrue(parser.block());
        Tree block = tree("block{penup pendown pendown}");
        assertStackIs("block{penup pendown pendown}");

        use("[ \n ] \n");
        assertTrue(parser.block());
        assertStackIs("block");

        try {
            use("[ ]");
            parser.block();
            fail();
        }
        catch (LogoException e) {}
    }
    
    public void testProcedure() {
        use("define foo \n end \n");
        assertTrue(parser.procedure());
        assertStackIs("define{ foo parameters block}");

        use("define foo x y \n penup \n pendown \n end \n");
        assertTrue(parser.procedure());
        assertStackIs("define{ foo parameters{x y} block{penup pendown}}");
    }
    
    public void testProgram() {
        use("color red\n");
        assertTrue(parser.program());
        assertStackIs("program{ block{ color{red}} procedures}");
             
        String mainProgram = "color blue\n pendown\n move 50\n";
        use(mainProgram);
        assertTrue(parser.program());
        assertStackIs("program{ block {color{blue} pendown move{50}} procedures}");
        
        String procedure1 = "define foo\n end\n";
        use(mainProgram + procedure1);
        assertTrue(parser.program());
        assertStackIs("program{ block {color{blue} pendown move{50}}" +
                      "procedures{ define{foo parameters block}}}");
        
        String procedure2 = "define bar a b\n move a\n turn left b\n end\n";
        Tree procTree2 = tree(" define{bar parameters{a b}" +
                              " block{ move{a} turn{direction{left b}}}}}");
        use(mainProgram + procedure2);
        assertTrue(parser.program());
        assertStackIs("program {block {color{blue} pendown move{50}}" +
                " procedures{ define{bar parameters{a b} block{ move{a} turn{direction{left b}}}}}}");

        use(mainProgram + procedure1 + procedure2);
        assertTrue(parser.program());

        try {
            use(mainProgram + procedure1 + procedure2 + "garbage");
            assertFalse(parser.program());
        }
        catch (LogoException e) {}
    }
    
    public void testComparison() {
        use("2 < 3;;;");        
        assertTrue(parser.comparison());
        assertStackIs("<{2 3}");

        use("4 + y = 4 + y");
        assertTrue(parser.comparison());
        assertStackIs("={ +{4 y} +{4 y}}");
        
        use("2 <");
        try {
            assertFalse(parser.comparison());
        }
        catch (LogoException e) {}
    }
    
    public void testCondition() {
        String s = " 2 < 3 ";
        use(s + ";;");        
        assertTrue(parser.condition());
        assertStackIs("<{2 3}");
        
        use(s + "and" + s);
        assertTrue(parser.condition());
        assertStackIs("and{ <{2 3} <{2 3}}");
        
        use(s + "or" + s);
        assertTrue(parser.condition());
        assertStackIs("or{ <{2 3} <{2 3}}");
        
        use(s + "or" + s + "and" + s);
        assertTrue(parser.condition());
        assertStackIs("or{ <{2 3} and{ <{2 3} <{2 3}}}");
        
        use(s + "and" + s + "or" + s);
        assertTrue(parser.condition());
        assertStackIs("or{ and{ <{2 3} <{2 3}} <{2 3}}");
    }
    
    public void testDisjunct() {
        use("2 < 3;;;");        
        assertTrue(parser.disjunct());
        use("2 < 3 and 4 + y = 4 + y");
        assertTrue(parser.disjunct());
        assertStackIs("and{ <{2 3} ={ +{4 y} +{4 y}}}");   
    }
    
    public void testConjunct() {
        use("2 < 3;;;");        
        assertTrue(parser.conjunct());
        assertStackIs("<{2 3}");
        
        use("not 2 < 3;;;");        
        assertTrue(parser.conjunct());
        assertStackIs("not{<{2 3}}");
        
    }
    
    public void testLogicalFactor() {
        use("2 < 3;;;");        
        assertTrue(parser.logicalFactor());
        assertStackIs("<{2 3}");

        use("4 + y = 4 + y");
        assertTrue(parser.logicalFactor());
        assertStackIs("={ +{4 y} +{4 y}}");
        
        use("2 <");
        try {
            assertFalse(parser.logicalFactor());
        }
        catch (LogoException e) {}
    }
    
//  ----- "Helper" methods

    /**
     * Tests whether the Tokens in the parameter also occur in
     * the string remaining to be tokenized. Does not test whether
     * there are additional Tokens beyond these in the string to
     * be tokenized.
     * 
     * @param rest The tokens to look for.
     * @throws AssertionFailedError if the expected Tokens are not found.
     */
    private void unused(String rest) {
        LogoTokenizer actual = parser.tokenizer;
        LogoTokenizer expected = new LogoTokenizer(rest);
        while (expected.hasNext()) {
            Token actualToken = (Token)actual.next();
            Token expectedToken = (Token)expected.next();
            assertEquals(expectedToken, actualToken);
        }    
    }
    
    /**
     * Sets the <code>parser</code> instance to use the given string.
     * 
     * @param s The string to be parsed.
     */
    private void use(String s) {
        parser = new Parser(s);
    }
    
    /**
     * Returns the current top of the stack.
     *
     * @return The top of the stack.
     */
    private Object stackTop() {
        return parser.stack.peek();
    }
    
    /**
     * Returns a Tree node consisting of a single leaf; the
     * node will contain a Token with a String as its value.
     * <ul>
     *   <li>Given a Tree, return the same Tree.</li>
     *   <li>Given a Token, return a Tree with the Token as its value.</li>
     *   <li>Given a String, make it into a Token, return a Tree.</li>
     * with the Token as its value.
     * </ul>
     * 
     * @param value A Tree, Token, or String from which to
              construct the Tree node.
     * @return A Tree leaf node containing a Token whose value
     *         is the parameter.
     */
    private Tree makeTreeNode(Object value) {
        if (value instanceof Tree) {
            return (Tree) value;
        }
        if (value instanceof Token) {
            return new Tree(value);
        }
        else if (value instanceof String) {
            return new Tree(makeToken((String) value));
        }
        assert false: "Illegal argument: tree(" + value + ")";
        return null; 
    }

    static Token openBraceToken = new Token(Type.SYMBOL, "{");
    static Token closeBraceToken = new Token(Type.SYMBOL, "}");
    static int indentCount;
    
    /**
     * Creates a Tree from a given String. The string has the form
     * "root { subtree1 subtree2 ... subtreeN }", where each subtree
     * has the same form.
     * 
     * For example, "+{2 *{3 4}}" yields the tree
     * <pre>    +
     *         / \
     *        2   *
     *           / \
     *          3   4  </pre>
     * 
     * @param input The String to turn into a Tree.
     * @return The newly created Tree.
     */
    private static Tree tree(String input) {
        assert input != null;
        LogoTokenizer tokenizer = new LogoTokenizer(input);
        assert tokenizer.hasNext();
        Tree root = new Tree(tokenizer.next());
        addChildrenIfAny(root, tokenizer);
        return root;
    }
    
    private static void addChildrenIfAny(Tree root, Tokenizer tokenizer) {
        Token token = (Token) tokenizer.next();
        if (token.equals(openBraceToken)) {
            token = (Token) tokenizer.next();
            while (!token.equals(closeBraceToken)) {
                Tree child = new Tree(token);
                root.addChild(child);
                addChildrenIfAny(child, tokenizer);
                token = (Token) tokenizer.next();
            }
            return;
        }
        else { // No children
            tokenizer.putBack(1);
            return;
        }
    }
    
    static Set<String> keywords = 
        new HashSet<String>(Arrays.asList("move", "turn", "penup",
                                          "pendown", "color", "home",
                                          "repeat", "while", "if", "call",
                                          "north", "east", "south", "west",
                                          "left", "right", "magenta", "red",
                                          "orange", "yellow", "green", "aqua",
                                          "blue", "purple", "violet", "brown",
                                          "black", "charcoal", "gray", "grey",
                                          "white", "pink", "or", "and", "not",
                                          "define", "end"));
    /**
     * Determines whether <code>word</code> is a keyword
     * in Logo2006.
     * @param word the word to check against Logo2006 keywords.
     * @return <code>true</code> if <code>word</code> is a 
     * Logo2006 keyword; <code>false</code> otherwise
     */
    static boolean isKeyword(String word) {
        return keywords.contains(word);
    }
    
    /**
     * Quick'n'dirty routine to make a Token from a String. The
     * type (name, number, or symbol) is inferred from the first
     * character; no error checking is done.
     * 
     * @param s The string to turn into a Token.
     * @return A Token whose value is the given string and whose
     *         type has been inferred from the first character.
     */
    private Token makeToken(String s) {
        char ch = s.charAt(0);
        if (Character.isDigit(ch)) {
            return new Token(Type.NUMBER, s);
        }
        else if (Character.isLetter(ch)) {
            if (isKeyword(s)) {
                return new Token(Type.KEYWORD, s);
            }
            else {
                return new Token(Type.NAME, s);
            }
        }
        else
            return new Token(Type.SYMBOL, s);
    }
    
    /**
     * Asserts that there is exactly one thing in the parser stack,
     * and that thing is equal to a Tree made from the given string.
     * 
     * @param string A string description of the Tree to compare against
     *               the top of the stack.
     * @throws AssertionFailedError if the stack is not as expected.
     */
    private void assertStackIs(String string) {
        assertEquals(tree(string), parser.stack.peek());
        assertStackSize(1);
    }
    
    /**
     * Asserts that we have exactly the given number of things on the
     * parser stack.
     * 
     * @param size The number of things we expect to be on the parser stack.
     * @throws AssertionFailedError if the stack is the wrong size.
     */
    private void assertStackSize(int size) {
        assertEquals("Incorrect stack size", size, parser.stack.size());
    }
}