1package org.antlr.runtime {
2	
3	/** A DFA implemented as a set of transition tables.
4	 *
5	 *  Any state that has a semantic predicate edge is special; those states
6	 *  are generated with if-then-else structures in a specialStateTransition()
7	 *  which is generated by cyclicDFA template.
8	 *
9	 *  There are at most 32767 states (16-bit signed short).
10	 *  Could get away with byte sometimes but would have to generate different
11	 *  types and the simulation code too.  For a point of reference, the Java
12	 *  lexer's Tokens rule DFA has 326 states roughly.
13	 */
14	public class DFA {
15		protected var eot:Array; // short[]
16		protected var eof:Array; // short[]
17		protected var min:Array; // char[]
18	    protected var max:Array; // char[]
19	    protected var accept:Array; //short[]
20	    protected var special:Array; // short[]
21	    protected var transition:Array; // short[][]
22	
23		protected var decisionNumber:int;
24	
25		/** Which recognizer encloses this DFA?  Needed to check backtracking */
26		protected var recognizer:BaseRecognizer;
27	
28		private var _description:String;
29		
30		public static const debug:Boolean = false;
31
32		public function DFA(recognizer:BaseRecognizer, decisionNumber:int, description:String,
33							eot:Array, eof:Array, min:Array, max:Array, accept:Array, special:Array, transition:Array,
34							specialStateTransitionFunction:Function = null, errorFunction:Function = null) {			
35			this.recognizer = recognizer;
36			this.decisionNumber = decisionNumber;
37			this._description = description;
38			
39			this.eot = eot;
40			this.eof = eof;
41			this.min = min;
42			this.max = max;
43			this.accept = accept;
44			this.special = special;
45            this.transition = transition;
46						
47			if (specialStateTransitionFunction != null) {
48				specialStateTransition = specialStateTransitionFunction;
49			}
50			
51			if (errorFunction != null) {
52				error = errorFunction;
53			}
54						
55		}
56		/** From the input stream, predict what alternative will succeed
57		 *  using this DFA (representing the covering regular approximation
58		 *  to the underlying CFL).  Return an alternative number 1..n.  Throw
59		 *  an exception upon error.
60		 */
61		public function predict(input:IntStream):int	{
62    		if ( debug ) {
63    			trace("Enter DFA.predict for decision "+decisionNumber);
64    		}
65
66			var mark:int = input.mark(); // remember where decision started in input
67			var s:int = 0; // we always start at s0
68			try {
69				while ( true ) {
70					if ( debug ) trace("DFA "+decisionNumber+" state "+s+" LA(1)="+String.fromCharCode(input.LA(1))+"("+input.LA(1)+
71													"), index="+input.index);
72					var specialState:int = special[s];
73					if ( specialState>=0 ) {
74						if ( debug ) {
75						    trace("DFA "+decisionNumber+
76							" state "+s+" is special state "+specialState);
77						}
78						s = specialStateTransition(this, specialState,input);
79						if ( debug ) {
80						    trace("DFA "+decisionNumber+
81							" returns from special state "+specialState+" to "+s);
82					    }
83						if ( s==-1 ) {
84						    noViableAlt(s,input);
85						    return 0;
86					    }
87						input.consume();
88						continue;
89					}
90					if ( accept[s] >= 1 ) {
91						if ( debug ) trace("accept; predict "+accept[s]+" from state "+s);
92						return accept[s];
93					}
94					// look for a normal char transition
95					var c:int = input.LA(1); // -1 == \uFFFF, all tokens fit in 65000 space
96					if (c>=min[s] && c<=max[s]) {
97						var snext:int = transition[s][c-min[s]]; // move to next state
98						if ( snext < 0 ) {
99							// was in range but not a normal transition
100							// must check EOT, which is like the else clause.
101							// eot[s]>=0 indicates that an EOT edge goes to another
102							// state.
103							if ( eot[s]>=0 ) {  // EOT Transition to accept state?
104								if ( debug ) trace("EOT transition");
105								s = eot[s];
106								input.consume();
107								// TODO: I had this as return accept[eot[s]]
108								// which assumed here that the EOT edge always
109								// went to an accept...faster to do this, but
110								// what about predicated edges coming from EOT
111								// target?
112								continue;
113							}
114							noViableAlt(s,input);
115							return 0;
116						}
117						s = snext;
118						input.consume();
119						continue;
120					}
121					if ( eot[s]>=0 ) {  // EOT Transition?
122						if ( debug ) trace("EOT transition");
123						s = eot[s];
124						input.consume();
125						continue;
126					}
127					if ( c==TokenConstants.EOF && eof[s]>=0 ) {  // EOF Transition to accept state?
128						if ( debug ) trace("accept via EOF; predict "+accept[eof[s]]+" from "+eof[s]);
129						return accept[eof[s]];
130					}
131					// not in range and not EOF/EOT, must be invalid symbol
132					if ( debug ) {
133						trace("min["+s+"]="+min[s]);
134						trace("max["+s+"]="+max[s]);
135						trace("eot["+s+"]="+eot[s]);
136						trace("eof["+s+"]="+eof[s]);
137						for (var p:int=0; p<transition[s].length; p++) {
138							trace(transition[s][p]+" ");
139						}
140						trace();
141					}
142					noViableAlt(s,input);
143					return 0;
144				}
145			}
146			finally {
147				input.rewindTo(mark);
148			}
149			// not reached -- added due to bug in Flex compiler reachability analysis of while loop with no breaks
150			return -1;
151		}
152	
153		protected function noViableAlt(s:int, input:IntStream):void {
154			if (recognizer.state.backtracking>0) {
155				recognizer.state.failed=true;
156				return;
157			}
158			var nvae:NoViableAltException =
159				new NoViableAltException(description,
160										 decisionNumber,
161										 s,
162										 input);
163			error(nvae);
164			throw nvae;
165		}
166	
167		/** A hook for debugging interface */
168		public var error:Function = function(nvae:NoViableAltException):NoViableAltException { return nvae; }
169	
170		public var specialStateTransition:Function = function(dfa:DFA, s:int, input:IntStream):int {
171			return -1;
172		}
173	
174		public function get description():String {
175			return _description;	
176		}
177	
178		/** Given a String that has a run-length-encoding of some unsigned shorts
179		 *  like "\1\2\3\9", convert to short[] {2,9,9,9}.  We do this to avoid
180		 *  static short[] which generates so much init code that the class won't
181		 *  compile. :(
182		 */
183		public static function unpackEncodedString(encodedString:String, unsigned:Boolean = false):Array {
184			// walk first to find how big it is.
185			/* Don't pre-allocate
186			var size:int = 0;
187			for (var i:int=0; i<encodedString.length; i+=2) {
188				size += encodedString.charCodeAt(i);
189			}
190			*/
191			var data:Array = new Array();
192			var di:int = 0;
193			for (var i:int=0; i<encodedString.length; i+=2) {
194				var n:int = encodedString.charCodeAt(i);
195				if (n > 0x8000) {
196				    // need to read another byte
197				    i++;
198				    var lowBits:int = encodedString.charCodeAt(i);
199				    n &= 0xff;
200				    n <<= 8;
201				    n |= lowBits;
202				}
203				var v:int = encodedString.charCodeAt(i+1);
204				if (v > 0x8000) {
205				    // need to read another byte
206				    i++;
207				    lowBits = encodedString.charCodeAt(i);
208				    v &= 0xff;
209				    v <<= 8;
210				    v |= lowBits;
211				}
212				if (!unsigned && v > 0x7fff) {
213				    v = -(0xffff - v + 1);
214				}
215				// add v n times to data
216				for (var j:int=1; j<=n; j++) {
217					data[di++] = v;
218				}
219			}
220			return data;
221		}
222	
223	}
224
225}