xref: /external/antlr/antlr-3.4/runtime/CSharp2/Sources/Antlr3.Runtime/Antlr.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 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 {
        public DFA()
            : this(new SpecialStateTransitionHandler(SpecialStateTransitionDefault)) {
        }
        public DFA(SpecialStateTransitionHandler specialStateTransition) {
            this.SpecialStateTransition = specialStateTransition ?? new SpecialStateTransitionHandler(SpecialStateTransitionDefault);
        }

        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 readonly bool debug = false;

        /** <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 (debug) {
                Console.Error.WriteLine("Enter DFA.predict for decision " + decisionNumber);
            }
            int mark = input.Mark(); // remember where decision started in input
            int s = 0; // we always start at s0
            try {
                for (; ; ) {
                    if (debug)
                        Console.Error.WriteLine("DFA " + decisionNumber + " state " + s + " LA(1)=" + (char)input.LA(1) + "(" + input.LA(1) +
                                           "), index=" + input.Index);
                    int specialState = special[s];
                    if (specialState >= 0) {
                        if (debug) {
                            Console.Error.WriteLine("DFA " + decisionNumber +
                                " state " + s + " is special state " + specialState);
                        }
                        s = SpecialStateTransition(this, specialState, input);
                        if (debug) {
                            Console.Error.WriteLine("DFA " + decisionNumber +
                                " returns from special state " + specialState + " to " + s);
                        }
                        if (s == -1) {
                            NoViableAlt(s, input);
                            return 0;
                        }
                        input.Consume();
                        continue;
                    }
                    if (accept[s] >= 1) {
                        if (debug)
                            Console.Error.WriteLine("accept; predict " + accept[s] + " from state " + 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?
                                if (debug)
                                    Console.Error.WriteLine("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?
                        if (debug)
                            Console.Error.WriteLine("EOT transition");
                        s = eot[s];
                        input.Consume();
                        continue;
                    }
                    if (c == unchecked((char)TokenTypes.EndOfFile) && eof[s] >= 0) {  // EOF Transition to accept state?
                        if (debug)
                            Console.Error.WriteLine("accept via EOF; predict " + accept[eof[s]] + " from " + eof[s]);
                        return accept[eof[s]];
                    }
                    // not in range and not EOF/EOT, must be invalid symbol
                    if (debug) {
                        Console.Error.WriteLine("min[" + s + "]=" + min[s]);
                        Console.Error.WriteLine("max[" + s + "]=" + max[s]);
                        Console.Error.WriteLine("eot[" + s + "]=" + eot[s]);
                        Console.Error.WriteLine("eof[" + s + "]=" + eof[s]);
                        for (int p = 0; p < transition[s].Length; p++) {
                            Console.Error.Write(transition[s][p] + " ");
                        }
                        Console.Error.WriteLine();
                    }
                    NoViableAlt(s, input);
                    return 0;
                }
            } finally {
                input.Rewind(mark);
            }
        }

        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;
        }

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

        /** <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);
        }
    }
}