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.test;
29 
30 import org.antlr.misc.Graph;
31 import org.junit.Test;
32 
33 import java.util.List;
34 
35 /** Test topo sort in GraphNode. */
36 public class TestTopologicalSort extends BaseTest {
37     @Test
testFairlyLargeGraph()38     public void testFairlyLargeGraph() throws Exception {
39         Graph g = new Graph();
40         g.addEdge("C", "F");
41         g.addEdge("C", "G");
42         g.addEdge("C", "A");
43         g.addEdge("C", "B");
44         g.addEdge("A", "D");
45         g.addEdge("A", "E");
46         g.addEdge("B", "E");
47         g.addEdge("D", "E");
48         g.addEdge("D", "F");
49         g.addEdge("F", "H");
50         g.addEdge("E", "F");
51 
52         String expecting = "[H, F, E, D, G, A, B, C]";
53         List nodes = g.sort();
54         String result = nodes.toString();
55         assertEquals(expecting, result);
56     }
57 
58     @Test
testCyclicGraph()59     public void testCyclicGraph() throws Exception {
60         Graph g = new Graph();
61         g.addEdge("A", "B");
62         g.addEdge("B", "C");
63         g.addEdge("C", "A");
64         g.addEdge("C", "D");
65 
66         String expecting = "[D, C, B, A]";
67         List nodes = g.sort();
68         String result = nodes.toString();
69         assertEquals(expecting, result);
70     }
71 
72     @Test
testRepeatedEdges()73     public void testRepeatedEdges() throws Exception {
74         Graph g = new Graph();
75         g.addEdge("A", "B");
76         g.addEdge("B", "C");
77         g.addEdge("A", "B"); // dup
78         g.addEdge("C", "D");
79 
80         String expecting = "[D, C, B, A]";
81         List nodes = g.sort();
82         String result = nodes.toString();
83         assertEquals(expecting, result);
84     }
85 
86     @Test
testSimpleTokenDependence()87     public void testSimpleTokenDependence() throws Exception {
88         Graph g = new Graph();
89         g.addEdge("Java.g", "MyJava.tokens"); // Java feeds off manual token file
90         g.addEdge("Java.tokens", "Java.g");
91         g.addEdge("Def.g", "Java.tokens");    // walkers feed off generated tokens
92         g.addEdge("Ref.g", "Java.tokens");
93 
94         String expecting = "[MyJava.tokens, Java.g, Java.tokens, Ref.g, Def.g]";
95         List nodes = g.sort();
96         String result = nodes.toString();
97         assertEquals(expecting, result);
98     }
99 
100     @Test
testParserLexerCombo()101     public void testParserLexerCombo() throws Exception {
102         Graph g = new Graph();
103         g.addEdge("JavaLexer.tokens", "JavaLexer.g");
104         g.addEdge("JavaParser.g", "JavaLexer.tokens");
105         g.addEdge("Def.g", "JavaLexer.tokens");
106         g.addEdge("Ref.g", "JavaLexer.tokens");
107 
108         String expecting = "[JavaLexer.g, JavaLexer.tokens, JavaParser.g, Ref.g, Def.g]";
109         List nodes = g.sort();
110         String result = nodes.toString();
111         assertEquals(expecting, result);
112     }
113 }
114