1/*
2 * [The "BSD licence"]
3 * Copyright (c) 2005-2008 Terence Parr
4 * All rights reserved.
5 *
6 * Conversion to C#:
7 * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. The name of the author may not be used to endorse or promote products
19 *    derived from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33namespace Antlr.Runtime
34{
35    using ConditionalAttribute = System.Diagnostics.ConditionalAttribute;
36    using Console = System.Console;
37    using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener;
38
39    public delegate int SpecialStateTransitionHandler( DFA dfa, int s, IIntStream input );
40
41    /** <summary>A DFA implemented as a set of transition tables.</summary>
42     *
43     *  <remarks>
44     *  Any state that has a semantic predicate edge is special; those states
45     *  are generated with if-then-else structures in a specialStateTransition()
46     *  which is generated by cyclicDFA template.
47     *
48     *  There are at most 32767 states (16-bit signed short).
49     *  Could get away with byte sometimes but would have to generate different
50     *  types and the simulation code too.  For a point of reference, the Java
51     *  lexer's Tokens rule DFA has 326 states roughly.
52     *  </remarks>
53     */
54    public class DFA
55    {
56        protected short[] eot;
57        protected short[] eof;
58        protected char[] min;
59        protected char[] max;
60        protected short[] accept;
61        protected short[] special;
62        protected short[][] transition;
63
64        protected int decisionNumber;
65
66        /** <summary>Which recognizer encloses this DFA?  Needed to check backtracking</summary> */
67        protected BaseRecognizer recognizer;
68
69        public readonly bool debug = false;
70
71        public DFA()
72            : this( new SpecialStateTransitionHandler( SpecialStateTransitionDefault ) )
73        {
74        }
75
76        public DFA( SpecialStateTransitionHandler specialStateTransition )
77        {
78            this.SpecialStateTransition = specialStateTransition ?? new SpecialStateTransitionHandler( SpecialStateTransitionDefault );
79        }
80
81        public virtual string Description
82        {
83            get
84            {
85                return "n/a";
86            }
87        }
88
89        /** <summary>
90         *  From the input stream, predict what alternative will succeed
91         *  using this DFA (representing the covering regular approximation
92         *  to the underlying CFL).  Return an alternative number 1..n.  Throw
93         *  an exception upon error.
94         *  </summary>
95         */
96        public virtual int Predict( IIntStream input )
97        {
98            if ( debug )
99            {
100                Console.Error.WriteLine( "Enter DFA.predict for decision " + decisionNumber );
101            }
102            int mark = input.Mark(); // remember where decision started in input
103            int s = 0; // we always start at s0
104            try
105            {
106                for ( ; ; )
107                {
108                    if ( debug )
109                        Console.Error.WriteLine( "DFA " + decisionNumber + " state " + s + " LA(1)=" + (char)input.LA( 1 ) + "(" + input.LA( 1 ) +
110                                           "), index=" + input.Index );
111                    int specialState = special[s];
112                    if ( specialState >= 0 )
113                    {
114                        if ( debug )
115                        {
116                            Console.Error.WriteLine( "DFA " + decisionNumber +
117                                " state " + s + " is special state " + specialState );
118                        }
119                        s = SpecialStateTransition( this, specialState, input );
120                        if ( debug )
121                        {
122                            Console.Error.WriteLine( "DFA " + decisionNumber +
123                                " returns from special state " + specialState + " to " + s );
124                        }
125                        if ( s == -1 )
126                        {
127                            NoViableAlt( s, input );
128                            return 0;
129                        }
130                        input.Consume();
131                        continue;
132                    }
133                    if ( accept[s] >= 1 )
134                    {
135                        if ( debug )
136                            Console.Error.WriteLine( "accept; predict " + accept[s] + " from state " + s );
137                        return accept[s];
138                    }
139                    // look for a normal char transition
140                    char c = (char)input.LA( 1 ); // -1 == \uFFFF, all tokens fit in 65000 space
141                    if ( c >= min[s] && c <= max[s] )
142                    {
143                        int snext = transition[s][c - min[s]]; // move to next state
144                        if ( snext < 0 )
145                        {
146                            // was in range but not a normal transition
147                            // must check EOT, which is like the else clause.
148                            // eot[s]>=0 indicates that an EOT edge goes to another
149                            // state.
150                            if ( eot[s] >= 0 )
151                            {  // EOT Transition to accept state?
152                                if ( debug )
153                                    Console.Error.WriteLine( "EOT transition" );
154                                s = eot[s];
155                                input.Consume();
156                                // TODO: I had this as return accept[eot[s]]
157                                // which assumed here that the EOT edge always
158                                // went to an accept...faster to do this, but
159                                // what about predicated edges coming from EOT
160                                // target?
161                                continue;
162                            }
163                            NoViableAlt( s, input );
164                            return 0;
165                        }
166                        s = snext;
167                        input.Consume();
168                        continue;
169                    }
170                    if ( eot[s] >= 0 )
171                    {  // EOT Transition?
172                        if ( debug )
173                            Console.Error.WriteLine( "EOT transition" );
174                        s = eot[s];
175                        input.Consume();
176                        continue;
177                    }
178                    if ( c == unchecked( (char)TokenTypes.EndOfFile ) && eof[s] >= 0 )
179                    {  // EOF Transition to accept state?
180                        if ( debug )
181                            Console.Error.WriteLine( "accept via EOF; predict " + accept[eof[s]] + " from " + eof[s] );
182                        return accept[eof[s]];
183                    }
184                    // not in range and not EOF/EOT, must be invalid symbol
185                    if ( debug )
186                    {
187                        Console.Error.WriteLine( "min[" + s + "]=" + min[s] );
188                        Console.Error.WriteLine( "max[" + s + "]=" + max[s] );
189                        Console.Error.WriteLine( "eot[" + s + "]=" + eot[s] );
190                        Console.Error.WriteLine( "eof[" + s + "]=" + eof[s] );
191                        for ( int p = 0; p < transition[s].Length; p++ )
192                        {
193                            Console.Error.Write( transition[s][p] + " " );
194                        }
195                        Console.Error.WriteLine();
196                    }
197                    NoViableAlt( s, input );
198                    return 0;
199                }
200            }
201            finally
202            {
203                input.Rewind( mark );
204            }
205        }
206
207        protected virtual void NoViableAlt( int s, IIntStream input )
208        {
209            if ( recognizer.state.backtracking > 0 )
210            {
211                recognizer.state.failed = true;
212                return;
213            }
214            NoViableAltException nvae =
215                new NoViableAltException( Description,
216                                         decisionNumber,
217                                         s,
218                                         input );
219            Error( nvae );
220            throw nvae;
221        }
222
223        /** <summary>A hook for debugging interface</summary> */
224        public virtual void Error( NoViableAltException nvae )
225        {
226        }
227
228        public SpecialStateTransitionHandler SpecialStateTransition
229        {
230            get;
231            private set;
232        }
233        //public virtual int specialStateTransition( int s, IntStream input )
234        //{
235        //    return -1;
236        //}
237
238        static int SpecialStateTransitionDefault( DFA dfa, int s, IIntStream input )
239        {
240            return -1;
241        }
242
243        /** <summary>
244         *  Given a String that has a run-length-encoding of some unsigned shorts
245         *  like "\1\2\3\9", convert to short[] {2,9,9,9}.  We do this to avoid
246         *  static short[] which generates so much init code that the class won't
247         *  compile. :(
248         *  </summary>
249         */
250        public static short[] UnpackEncodedString( string encodedString )
251        {
252            // walk first to find how big it is.
253            int size = 0;
254            for ( int i = 0; i < encodedString.Length; i += 2 )
255            {
256                size += encodedString[i];
257            }
258            short[] data = new short[size];
259            int di = 0;
260            for ( int i = 0; i < encodedString.Length; i += 2 )
261            {
262                char n = encodedString[i];
263                char v = encodedString[i + 1];
264                // add v n times to data
265                for ( int j = 1; j <= n; j++ )
266                {
267                    data[di++] = (short)v;
268                }
269            }
270            return data;
271        }
272
273        /** <summary>Hideous duplication of code, but I need different typed arrays out :(</summary> */
274        public static char[] UnpackEncodedStringToUnsignedChars( string encodedString )
275        {
276            // walk first to find how big it is.
277            int size = 0;
278            for ( int i = 0; i < encodedString.Length; i += 2 )
279            {
280                size += encodedString[i];
281            }
282            char[] data = new char[size];
283            int di = 0;
284            for ( int i = 0; i < encodedString.Length; i += 2 )
285            {
286                char n = encodedString[i];
287                char v = encodedString[i + 1];
288                // add v n times to data
289                for ( int j = 1; j <= n; j++ )
290                {
291                    data[di++] = v;
292                }
293            }
294            return data;
295        }
296
297        [Conditional("ANTLR_DEBUG")]
298        protected virtual void DebugRecognitionException(RecognitionException ex)
299        {
300            IDebugEventListener dbg = recognizer.DebugListener;
301            if (dbg != null)
302                dbg.RecognitionException(ex);
303        }
304    }
305}
306