1/** Support functions for traversing cyclic DFA states as laid
2 *  out in static initialized structures by the code generator.
3 *
4 * A DFA implemented as a set of transition tables.
5 *
6 *  Any state that has a semantic predicate edge is special; those states
7 *  are generated with if-then-else structures in a ->specialStateTransition()
8 *  which is generated by cyclicDFA template.
9 *
10 *  There are at most 32767 states (16-bit signed short).
11 *  Could get away with byte sometimes but would have to generate different
12 *  types and the simulation code too.  For a point of reference, the Java
13 *  lexer's Tokens rule DFA has 326 states roughly.
14 */
15
16// [The "BSD licence"]
17// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
18// http://www.temporal-wave.com
19// http://www.linkedin.com/in/jimidle
20//
21// All rights reserved.
22//
23// Redistribution and use in source and binary forms, with or without
24// modification, are permitted provided that the following conditions
25// are met:
26// 1. Redistributions of source code must retain the above copyright
27//    notice, this list of conditions and the following disclaimer.
28// 2. Redistributions in binary form must reproduce the above copyright
29//    notice, this list of conditions and the following disclaimer in the
30//    documentation and/or other materials provided with the distribution.
31// 3. The name of the author may not be used to endorse or promote products
32//    derived from this software without specific prior written permission.
33//
34// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
35// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
36// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
37// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
38// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
39// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
40// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
41// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
42// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
43// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44
45#include    <antlr3defs.h>
46#include    <antlr3cyclicdfa.h>
47
48#ifdef	ANTLR3_WINDOWS
49#pragma warning( disable : 4100 )
50#endif
51
52static void
53noViableAlt(pANTLR3_BASE_RECOGNIZER rec, pANTLR3_CYCLIC_DFA cdfa, ANTLR3_UINT32	s)
54{
55	// In backtracking mode, we just set the failed flag so that the
56	// alt can just exit right now. If we are parsing though, then
57	// we want the exception to be raised.
58	//
59    if	(rec->state->backtracking > 0)
60    {
61		rec->state->failed = ANTLR3_TRUE;
62    }
63	else
64	{
65		rec->exConstruct(rec);
66		rec->state->exception->type         = ANTLR3_NO_VIABLE_ALT_EXCEPTION;
67		rec->state->exception->message      = cdfa->description;
68		rec->state->exception->decisionNum  = cdfa->decisionNumber;
69		rec->state->exception->state        = s;
70	}
71}
72
73/** From the input stream, predict what alternative will succeed
74 *  using this DFA (representing the covering regular approximation
75 *  to the underlying CFL).  Return an alternative number 1..n.  Throw
76 *  an exception upon error.
77 */
78ANTLR3_API ANTLR3_INT32
79antlr3dfapredict (void * ctx, pANTLR3_BASE_RECOGNIZER rec, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA cdfa)
80{
81    ANTLR3_MARKER	mark;
82    ANTLR3_INT32	s;
83    ANTLR3_INT32	specialState;
84    ANTLR3_INT32	c;
85
86    mark	= is->mark(is);	    /* Store where we are right now	*/
87    s		= 0;		    /* Always start with state 0	*/
88
89	for (;;)
90	{
91		/* Pick out any special state entry for this state
92		 */
93		specialState	= cdfa->special[s];
94
95		/* Transition the special state and consume an input token
96		 */
97		if  (specialState >= 0)
98		{
99			s = cdfa->specialStateTransition(ctx, rec, is, cdfa, specialState);
100
101			// Error?
102			//
103			if	(s<0)
104			{
105				// If the predicate/rule raised an exception then we leave it
106				// in tact, else we have an NVA.
107				//
108				if	(rec->state->error != ANTLR3_TRUE)
109				{
110					noViableAlt(rec,cdfa, s);
111				}
112				is->rewind(is, mark);
113				return	0;
114			}
115			is->consume(is);
116			continue;
117		}
118
119		/* Accept state?
120		 */
121		if  (cdfa->accept[s] >= 1)
122		{
123			is->rewind(is, mark);
124			return  cdfa->accept[s];
125		}
126
127		/* Look for a normal transition state based upon the input token element
128		 */
129		c = is->_LA(is, 1);
130
131		/* Check against min and max for this state
132		 */
133		if  (c>= cdfa->min[s] && c <= cdfa->max[s])
134		{
135			ANTLR3_INT32   snext;
136
137			/* What is the next state?
138			 */
139			snext = cdfa->transition[s][c - cdfa->min[s]];
140
141			if	(snext < 0)
142			{
143				/* Was in range but not a normal transition
144				 * must check EOT, which is like the else clause.
145				 * eot[s]>=0 indicates that an EOT edge goes to another
146				 * state.
147				 */
148				if  (cdfa->eot[s] >= 0)
149				{
150					s = cdfa->eot[s];
151					is->consume(is);
152					continue;
153				}
154				noViableAlt(rec,cdfa, s);
155				is->rewind(is, mark);
156				return	0;
157			}
158
159			/* New current state - move to it
160			 */
161			s	= snext;
162			is->consume(is);
163			continue;
164		}
165		/* EOT Transition?
166		 */
167		if  (cdfa->eot[s] >= 0)
168		{
169			s	= cdfa->eot[s];
170			is->consume(is);
171			continue;
172		}
173		/* EOF transition to accept state?
174		 */
175		if  ( c == ANTLR3_TOKEN_EOF && cdfa->eof[s] >= 0)
176		{
177			is->rewind(is, mark);
178			return  cdfa->accept[cdfa->eof[s]];
179		}
180
181		/* No alt, so bomb
182		 */
183		noViableAlt(rec, cdfa, s);
184		is->rewind(is, mark);
185		return 0;
186	}
187
188}
189
190/** Default special state implementation
191 */
192ANTLR3_API ANTLR3_INT32
193antlr3dfaspecialStateTransition   (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
194{
195    return -1;
196}
197
198/* Default special transition implementation
199 */
200ANTLR3_API ANTLR3_INT32
201antlr3dfaspecialTransition    (void * ctx, pANTLR3_BASE_RECOGNIZER recognizer, pANTLR3_INT_STREAM is, pANTLR3_CYCLIC_DFA dfa, ANTLR3_INT32 s)
202{
203    return 0;
204}
205