1// [The "BSD licence"]
2// Copyright (c) 2006-2007 Kay Roepke 2010 Alan Condit
3// All rights reserved.
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions
7// are met:
8// 1. Redistributions of source code must retain the above copyright
9//    notice, this list of conditions and the following disclaimer.
10// 2. Redistributions in binary form must reproduce the above copyright
11//    notice, this list of conditions and the following disclaimer in the
12//    documentation and/or other materials provided with the distribution.
13// 3. The name of the author may not be used to endorse or promote products
14//    derived from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27#import "DFA.h"
28#import <Token.h>
29#import <NoViableAltException.h>
30
31NSInteger debug = 0;
32
33@implementation DFA
34@synthesize recognizer;
35@synthesize decisionNumber;
36@synthesize len;
37
38- (id) initWithRecognizer:(BaseRecognizer *) theRecognizer
39{
40	if ((self = [super init]) != nil) {
41		recognizer = theRecognizer;
42        [recognizer retain];
43        debug = 0;
44	}
45	return self;
46}
47
48// using the tables ANTLR generates for the DFA based prediction this method simulates the DFA
49// and returns the prediction of the alternative to be used.
50- (NSInteger) predict:(id<IntStream>)input
51{
52    if ( debug > 2 ) {
53        NSLog(@"Enter DFA.predict for decision %d", decisionNumber);
54    }
55	int aMark = [input mark];
56	int s = 0;
57	@try {
58		while (YES) {
59			if ( debug > 2 )
60                NSLog(@"DFA %d state %d LA(1)='%c'(%x)", decisionNumber, s, (unichar)[input LA:1], [input LA:1]);
61			NSInteger specialState = special[s];
62			if (specialState >= 0) {
63				// this state is special in that it has some code associated with it. we cannot do this in a pure DFA so
64				// we signal the caller accordingly.
65				if ( debug > 2 ) {
66                    NSLog(@"DFA %d state %d is special state %d", decisionNumber, s, specialState);
67                }
68				s = [self specialStateTransition:specialState Stream:input];
69                if ( debug > 2 ) {
70                    NSLog(@"DFA %d returns from special state %d to %d", decisionNumber, specialState, s);
71                }
72                if (s == -1 ) {
73                    [self noViableAlt:s Stream:input];
74                    return 0;
75                }
76				[input consume];
77				continue;
78			}
79			if (accept[s] >= 1) {  // if this is an accepting state return the prediction
80				if ( debug > 2 ) NSLog(@"accept; predict %d from state %d", accept[s], s);
81				return accept[s];
82			}
83			// based on the lookahead lookup the next transition, consume and do transition
84			// or signal that we have no viable alternative
85			NSInteger c = [input LA:1];
86			if ( (unichar)c >= min[s] && (unichar)c <= max[s]) {
87				int snext = transition[s][c-min[s]];
88				if (snext < 0) {
89                    // was in range but not a normal transition
90                    // must check EOT, which is like the else clause.
91                    // eot[s]>=0 indicates that an EOT edge goes to another
92                    // state.
93					if (eot[s] >= 0) {
94						if ( debug > 2 ) NSLog(@"EOT transition");
95						s = eot[s];
96						[input consume];
97                        // TODO: I had this as return accept[eot[s]]
98                        // which assumed here that the EOT edge always
99                        // went to an accept...faster to do this, but
100                        // what about predicated edges coming from EOT
101                        // target?
102						continue;
103					}
104					[self noViableAlt:s Stream:input];
105					return 0;
106				}
107				s = snext;
108				[input consume];
109				continue;
110			}
111
112			if (eot[s] >= 0) {// EOT transition? we may still accept the input in the next state
113				if ( debug > 2 ) NSLog(@"EOT transition");
114				s = eot[s];
115				[input consume];
116				continue;
117			}
118			if ( c == TokenTypeEOF && eof[s] >= 0) {  // we are at EOF and may even accept the input.
119				if ( debug > 2 ) NSLog(@"accept via EOF; predict %d from %d", accept[eof[s]], eof[s]);
120				return accept[eof[s]];
121			}
122			if ( debug > 2 ) {
123                NSLog(@"no viable alt!\n");
124                NSLog(@"min[%d] = %d\n", s, min[s]);
125                NSLog(@"max[%d] = %d\n", s, min[s]);
126                NSLog(@"eot[%d] = %d\n", s, min[s]);
127                NSLog(@"eof[%d] = %d\n", s, min[s]);
128                for (NSInteger p = 0; p < self.len; p++) {
129                    NSLog(@"%d ", transition[s][p]);
130                }
131                NSLog(@"\n");
132            }
133			[self noViableAlt:s Stream:input];
134            return 0;
135		}
136	}
137	@finally {
138		[input rewind:aMark];
139	}
140	return 0; // silence warning
141}
142
143- (void) noViableAlt:(NSInteger)state Stream:(id<IntStream>)anInput
144{
145	if ([recognizer.state isBacktracking]) {
146		[recognizer.state setFailed:YES];
147		return;
148	}
149	NoViableAltException *nvae = [NoViableAltException newException:decisionNumber state:state stream:anInput];
150	[self error:nvae];
151	@throw nvae;
152}
153
154- (NSInteger) specialStateTransition:(NSInteger)state Stream:(id<IntStream>)anInput
155{
156    @throw [NoViableAltException newException:-1 state:state stream:anInput];
157	return -1;
158}
159
160- (void) error:(NoViableAltException *)nvae
161{
162	// empty, hook for debugger support
163}
164
165- (NSString *) description
166{
167	return @"subclass responsibility";
168}
169
170- (BOOL) evaluateSyntacticPredicate:(SEL)synpredFragment
171{
172	return [recognizer evaluateSyntacticPredicate:synpredFragment];
173}
174
175+ (void) setIsEmittingDebugInfo:(BOOL) shouldEmitDebugInfo
176{
177	debug = shouldEmitDebugInfo;
178}
179
180/** Given a String that has a run-length-encoding of some unsigned shorts
181 *  like "\1\2\3\9", convert to short[] {2,9,9,9}.  We do this to avoid
182 *  static short[] which generates so much init code that the class won't
183 *  compile. :(
184 */
185- (NSInteger *) unpackEncodedString:(NSString *)encodedString
186{
187    // walk first to find how big it is.
188    int size = 0;
189    for (int i=0; i < [encodedString length]; i+=2) {
190        size += [encodedString characterAtIndex:i];
191    }
192    __strong NSInteger *data = (NSInteger *)calloc(size, sizeof(NSInteger));
193    int di = 0;
194    for (int i=0; i < [encodedString length]; i+=2) {
195        char n = [encodedString characterAtIndex:i];
196        char v = [encodedString characterAtIndex:i+1];
197        // add v n times to data
198        for (int j = 0; j < n; j++) {
199            data[di++] = v;
200        }
201    }
202    return data;
203}
204
205/** Hideous duplication of code, but I need different typed arrays out :( */
206- (short *) unpackEncodedStringToUnsignedChars:(NSString *)encodedString
207{
208    // walk first to find how big it is.
209    int size = 0;
210    for (int i=0; i < [encodedString length]; i+=2) {
211        size += [encodedString characterAtIndex:i];
212    }
213    __strong short *data = (short *)calloc(size, sizeof(short));
214    int di = 0;
215    for (int i=0; i < [encodedString length]; i+=2) {
216        char n = [encodedString characterAtIndex:i];
217        char v = [encodedString characterAtIndex:i+1];
218        // add v n times to data
219        for (int j = 0; j < n; j++) {
220            data[di++] = v;
221        }
222    }
223    return (short *)data;
224}
225
226- (NSInteger)getDecision
227{
228    return decisionNumber;
229}
230
231- (void)setDecision:(NSInteger)aDecison
232{
233    decisionNumber = aDecison;
234}
235
236- (BaseRecognizer *)getRecognizer
237{
238    return recognizer;
239}
240
241- (void)setRecognizer:(BaseRecognizer *)aRecognizer
242{
243    if ( recognizer != aRecognizer ) {
244        if ( recognizer ) [recognizer release];
245        [aRecognizer retain];
246    }
247    recognizer = aRecognizer;
248}
249
250- (NSInteger)length
251{
252    return len;
253}
254
255@synthesize eot;
256@synthesize eof;
257@synthesize min;
258@synthesize max;
259@synthesize accept;
260@synthesize special;
261@synthesize transition;
262@end
263