xref: /aosp_15_r20/external/antlr/runtime/ObjC/Framework/DFA.m (revision 16467b971bd3e2009fad32dd79016f2c7e421deb)

// [The "BSD licence"]
// Copyright (c) 2006-2007 Kay Roepke 2010 Alan Condit
// 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.

#import "DFA.h"
#import <Token.h>
#import <NoViableAltException.h>

NSInteger debug = 0;

@implementation DFA
@synthesize recognizer;
@synthesize decisionNumber;
@synthesize len;

- (id) initWithRecognizer:(BaseRecognizer *) theRecognizer
{
	if ((self = [super init]) != nil) {
		recognizer = theRecognizer;
        [recognizer retain];
        debug = 0;
	}
	return self;
}

// using the tables ANTLR generates for the DFA based prediction this method simulates the DFA
// and returns the prediction of the alternative to be used.
- (NSInteger) predict:(id<IntStream>)input
{
    if ( debug > 2 ) {
        NSLog(@"Enter DFA.predict for decision %d", decisionNumber);
    }
	int aMark = [input mark];
	int s = 0;
	@try {
		while (YES) {
			if ( debug > 2 )
                NSLog(@"DFA %d state %d LA(1)='%c'(%x)", decisionNumber, s, (unichar)[input LA:1], [input LA:1]);
			NSInteger specialState = special[s];
			if (specialState >= 0) {
				// this state is special in that it has some code associated with it. we cannot do this in a pure DFA so
				// we signal the caller accordingly.
				if ( debug > 2 ) {
                    NSLog(@"DFA %d state %d is special state %d", decisionNumber, s, specialState);
                }
				s = [self specialStateTransition:specialState Stream:input];
                if ( debug > 2 ) {
                    NSLog(@"DFA %d returns from special state %d to %d", decisionNumber, specialState, s);
                }
                if (s == -1 ) {
                    [self noViableAlt:s Stream:input];
                    return 0;
                }
				[input consume];
				continue;
			}
			if (accept[s] >= 1) {  // if this is an accepting state return the prediction
				if ( debug > 2 ) NSLog(@"accept; predict %d from state %d", accept[s], s);
				return accept[s];
			}
			// based on the lookahead lookup the next transition, consume and do transition
			// or signal that we have no viable alternative
			NSInteger c = [input LA:1];
			if ( (unichar)c >= min[s] && (unichar)c <= max[s]) {
				int snext = transition[s][c-min[s]];
				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) {
						if ( debug > 2 ) NSLog(@"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;
					}
					[self noViableAlt:s Stream:input];
					return 0;
				}
				s = snext;
				[input consume];
				continue;
			}

			if (eot[s] >= 0) {// EOT transition? we may still accept the input in the next state
				if ( debug > 2 ) NSLog(@"EOT transition");
				s = eot[s];
				[input consume];
				continue;
			}
			if ( c == TokenTypeEOF && eof[s] >= 0) {  // we are at EOF and may even accept the input.
				if ( debug > 2 ) NSLog(@"accept via EOF; predict %d from %d", accept[eof[s]], eof[s]);
				return accept[eof[s]];
			}
			if ( debug > 2 ) {
                NSLog(@"no viable alt!\n");
                NSLog(@"min[%d] = %d\n", s, min[s]);
                NSLog(@"max[%d] = %d\n", s, min[s]);
                NSLog(@"eot[%d] = %d\n", s, min[s]);
                NSLog(@"eof[%d] = %d\n", s, min[s]);
                for (NSInteger p = 0; p < self.len; p++) {
                    NSLog(@"%d ", transition[s][p]);
                }
                NSLog(@"\n");
            }
			[self noViableAlt:s Stream:input];
            return 0;
		}
	}
	@finally {
		[input rewind:aMark];
	}
	return 0; // silence warning
}

- (void) noViableAlt:(NSInteger)state Stream:(id<IntStream>)anInput
{
	if ([recognizer.state isBacktracking]) {
		[recognizer.state setFailed:YES];
		return;
	}
	NoViableAltException *nvae = [NoViableAltException newException:decisionNumber state:state stream:anInput];
	[self error:nvae];
	@throw nvae;
}

- (NSInteger) specialStateTransition:(NSInteger)state Stream:(id<IntStream>)anInput
{
    @throw [NoViableAltException newException:-1 state:state stream:anInput];
	return -1;
}

- (void) error:(NoViableAltException *)nvae
{
	// empty, hook for debugger support
}

- (NSString *) description
{
	return @"subclass responsibility";
}

- (BOOL) evaluateSyntacticPredicate:(SEL)synpredFragment
{
	return [recognizer evaluateSyntacticPredicate:synpredFragment];
}

+ (void) setIsEmittingDebugInfo:(BOOL) shouldEmitDebugInfo
{
	debug = shouldEmitDebugInfo;
}

/** 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. :(
 */
- (NSInteger *) unpackEncodedString:(NSString *)encodedString
{
    // walk first to find how big it is.
    int size = 0;
    for (int i=0; i < [encodedString length]; i+=2) {
        size += [encodedString characterAtIndex:i];
    }
    __strong NSInteger *data = (NSInteger *)calloc(size, sizeof(NSInteger));
    int di = 0;
    for (int i=0; i < [encodedString length]; i+=2) {
        char n = [encodedString characterAtIndex:i];
        char v = [encodedString characterAtIndex:i+1];
        // add v n times to data
        for (int j = 0; j < n; j++) {
            data[di++] = v;
        }
    }
    return data;
}

/** Hideous duplication of code, but I need different typed arrays out :( */
- (short *) unpackEncodedStringToUnsignedChars:(NSString *)encodedString
{
    // walk first to find how big it is.
    int size = 0;
    for (int i=0; i < [encodedString length]; i+=2) {
        size += [encodedString characterAtIndex:i];
    }
    __strong short *data = (short *)calloc(size, sizeof(short));
    int di = 0;
    for (int i=0; i < [encodedString length]; i+=2) {
        char n = [encodedString characterAtIndex:i];
        char v = [encodedString characterAtIndex:i+1];
        // add v n times to data
        for (int j = 0; j < n; j++) {
            data[di++] = v;
        }
    }
    return (short *)data;
}

- (NSInteger)getDecision
{
    return decisionNumber;
}

- (void)setDecision:(NSInteger)aDecison
{
    decisionNumber = aDecison;
}

- (BaseRecognizer *)getRecognizer
{
    return recognizer;
}

- (void)setRecognizer:(BaseRecognizer *)aRecognizer
{
    if ( recognizer != aRecognizer ) {
        if ( recognizer ) [recognizer release];
        [aRecognizer retain];
    }
    recognizer = aRecognizer;
}

- (NSInteger)length
{
    return len;
}

@synthesize eot;
@synthesize eof;
@synthesize min;
@synthesize max;
@synthesize accept;
@synthesize special;
@synthesize transition;
@end