Sources/Antlr3.Runtime/DFA.cs

/*
 * [The "BSD licence"]
 * Copyright (c) 2005-2008 Terence Parr
 * All rights reserved.
 *
 * Conversion to C#:
 * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
 * 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.
 */

namespace Antlr.Runtime
{
    using ArgumentNullException = System.ArgumentNullException;
    using ConditionalAttribute = System.Diagnostics.ConditionalAttribute;
    using Console = System.Console;
    using IDebugEventListener = Antlr.Runtime.Debug.IDebugEventListener;

    public delegate int SpecialStateTransitionHandler( DFA dfa, int s, IIntStream input );

    /** <summary>A DFA implemented as a set of transition tables.</summary>
     *
     *  <remarks>
     *  Any state that has a semantic predicate edge is special; those states
     *  are generated with if-then-else structures in a specialStateTransition()
     *  which is generated by cyclicDFA template.
     *
     *  There are at most 32767 states (16-bit signed short).
     *  Could get away with byte sometimes but would have to generate different
     *  types and the simulation code too.  For a point of reference, the Java
     *  lexer's Tokens rule DFA has 326 states roughly.
     *  </remarks>
     */
    public class DFA
    {
        protected short[] eot;
        protected short[] eof;
        protected char[] min;
        protected char[] max;
        protected short[] accept;
        protected short[] special;
        protected short[][] transition;

        protected int decisionNumber;

        /** <summary>Which recognizer encloses this DFA?  Needed to check backtracking</summary> */
        protected BaseRecognizer recognizer;

        public bool debug = false;

        public DFA()
            : this(SpecialStateTransitionDefault)
        {
        }

        public DFA( SpecialStateTransitionHandler specialStateTransition )
        {
            this.SpecialStateTransition = specialStateTransition ?? SpecialStateTransitionDefault;
        }

        public virtual string Description
        {
            get
            {
                return "n/a";
            }
        }

        /** <summary>
         *  From the input stream, predict what alternative will succeed
         *  using this DFA (representing the covering regular approximation
         *  to the underlying CFL).  Return an alternative number 1..n.  Throw
         *  an exception upon error.
         *  </summary>
         */
        public virtual int Predict( IIntStream input )
        {
            if (input == null)
                throw new ArgumentNullException("input");

            DfaDebugMessage("Enter DFA.Predict for decision {0}", decisionNumber);

            int mark = input.Mark(); // remember where decision started in input
            int s = 0; // we always start at s0
            try
            {
                while (true)
                {
                    DfaDebugMessage("DFA {0} state {1} LA(1)={2}({3}), index={4}", decisionNumber, s, (char)input.LA(1), input.LA(1), input.Index);

                    int specialState = special[s];
                    if ( specialState >= 0 )
                    {
                        DfaDebugMessage("DFA {0} state {1} is special state {2}", decisionNumber, s, specialState);

                        s = SpecialStateTransition( this, specialState, input );

                        DfaDebugMessage("DFA {0} returns from special state {1} to {2}", decisionNumber, specialState, s);

                        if ( s == -1 )
                        {
                            NoViableAlt( s, input );
                            return 0;
                        }

                        input.Consume();
                        continue;
                    }

                    if ( accept[s] >= 1 )
                    {
                        DfaDebugMessage("accept; predict {0} from state {1}", accept[s], s);
                        return accept[s];
                    }

                    // look for a normal char transition
                    char c = (char)input.LA( 1 ); // -1 == \uFFFF, all tokens fit in 65000 space
                    if ( c >= min[s] && c <= max[s] )
                    {
                        int snext = transition[s][c - min[s]]; // move to next state
                        if ( snext < 0 )
                        {
                            // was in range but not a normal transition
                            // must check EOT, which is like the else clause.
                            // eot[s]>=0 indicates that an EOT edge goes to another
                            // state.
                            if ( eot[s] >= 0 )
                            {
                                // EOT Transition to accept state?
                                DfaDebugMessage("EOT transition");
                                s = eot[s];
                                input.Consume();
                                // TODO: I had this as return accept[eot[s]]
                                // which assumed here that the EOT edge always
                                // went to an accept...faster to do this, but
                                // what about predicated edges coming from EOT
                                // target?
                                continue;
                            }

                            NoViableAlt( s, input );
                            return 0;
                        }

                        s = snext;
                        input.Consume();
                        continue;
                    }

                    if ( eot[s] >= 0 )
                    {
                        // EOT Transition?
                        DfaDebugMessage("EOT transition");
                        s = eot[s];
                        input.Consume();
                        continue;
                    }

                    if ( c == unchecked( (char)TokenTypes.EndOfFile ) && eof[s] >= 0 )
                    {
                        // EOF Transition to accept state?
                        DfaDebugMessage("accept via EOF; predict {0} from {1}", accept[eof[s]], eof[s]);
                        return accept[eof[s]];
                    }

                    // not in range and not EOF/EOT, must be invalid symbol
                    DfaDebugInvalidSymbol(s);

                    NoViableAlt( s, input );
                    return 0;
                }
            }
            finally
            {
                input.Rewind( mark );
            }
        }

        [Conditional("DEBUG_DFA")]
        private void DfaDebugMessage(string format, params object[] args)
        {
            Console.Error.WriteLine(format, args);
        }

        [Conditional("DEBUG_DFA")]
        private void DfaDebugInvalidSymbol(int s)
        {
            Console.Error.WriteLine("min[{0}]={1}", s, min[s]);
            Console.Error.WriteLine("max[{0}]={1}", s, max[s]);
            Console.Error.WriteLine("eot[{0}]={1}", s, eot[s]);
            Console.Error.WriteLine("eof[{0}]={1}", s, eof[s]);

            for (int p = 0; p < transition[s].Length; p++)
                Console.Error.Write(transition[s][p] + " ");

            Console.Error.WriteLine();
        }

        protected virtual void NoViableAlt( int s, IIntStream input )
        {
            if ( recognizer.state.backtracking > 0 )
            {
                recognizer.state.failed = true;
                return;
            }
            NoViableAltException nvae =
                new NoViableAltException( Description,
                                         decisionNumber,
                                         s,
                                         input );
            Error( nvae );
            throw nvae;
        }

        /** <summary>A hook for debugging interface</summary> */
        public virtual void Error( NoViableAltException nvae )
        {
        }

        public SpecialStateTransitionHandler SpecialStateTransition
        {
            get;
            private set;
        }
        //public virtual int specialStateTransition( int s, IntStream input )
        //{
        //    return -1;
        //}

        static int SpecialStateTransitionDefault( DFA dfa, int s, IIntStream input )
        {
            return -1;
        }

        /** <summary>
         *  Given a String that has a run-length-encoding of some unsigned shorts
         *  like "\1\2\3\9", convert to short[] {2,9,9,9}.  We do this to avoid
         *  static short[] which generates so much init code that the class won't
         *  compile. :(
         *  </summary>
         */
        public static short[] UnpackEncodedString( string encodedString )
        {
            // walk first to find how big it is.
            int size = 0;
            for ( int i = 0; i < encodedString.Length; i += 2 )
            {
                size += encodedString[i];
            }
            short[] data = new short[size];
            int di = 0;
            for ( int i = 0; i < encodedString.Length; i += 2 )
            {
                char n = encodedString[i];
                char v = encodedString[i + 1];
                // add v n times to data
                for ( int j = 1; j <= n; j++ )
                {
                    data[di++] = (short)v;
                }
            }
            return data;
        }

        /** <summary>Hideous duplication of code, but I need different typed arrays out :(</summary> */
        public static char[] UnpackEncodedStringToUnsignedChars( string encodedString )
        {
            // walk first to find how big it is.
            int size = 0;
            for ( int i = 0; i < encodedString.Length; i += 2 )
            {
                size += encodedString[i];
            }
            char[] data = new char[size];
            int di = 0;
            for ( int i = 0; i < encodedString.Length; i += 2 )
            {
                char n = encodedString[i];
                char v = encodedString[i + 1];
                // add v n times to data
                for ( int j = 1; j <= n; j++ )
                {
                    data[di++] = v;
                }
            }
            return data;
        }

        [Conditional("ANTLR_DEBUG")]
        protected virtual void DebugRecognitionException(RecognitionException ex)
        {
            IDebugEventListener dbg = recognizer.DebugListener;
            if (dbg != null)
                dbg.RecognitionException(ex);
        }
    }
}