/* * The Regina Rexx Interpreter * Copyright (C) 1992-1994 Anders Christensen * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public * License along with this library; if not, write to the Free * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ /* * This implementation of the REXX parse template is quite near to * what Cowlishaw specified in his book, but there is one very * important difference. Cowlishaw sees a template as patterns and * variables, with patterns in each end (and some of the patterns * and/or the variables might be empty). * * The concept here is any sequence of variables and patterns, and * the system is parsed into two levels and interpreted as such. * First there is the level of patterns, which is anchored to * particular locations in the string to be parsed. * * When the anchor-points are determined, the variables are filled * in with the parts of the string that comes between each anchor. * Here is an example: * * parse value 'That is a parse string!' with a b 'is' c d 'i' e * * In this example, there are four anchors in the string, the two * patterns 'is' and 'i', and the two implicit anchors start-of-string * and end-of-string. They anchor particular locations in the string * to the lists of variables: (a b), (c d) and (e). At the first level * the anchors are found and the text between them are deternmined * (SOS=Start-Of-String, EOS=End-Of-String): * * That is a parse string! * anchors (SOS)-----is------------i---(EOS) * strings in-between <<<>>>> * * Now, we have a set of substrings, and to each substring, there is * possibly empty set of variable which are to receive its value from * the contents of that substring. Doing that, we get: * * (a b) = 'That ' ==> a='That' b=' ' * (c d) = ' a parse str' ==> c='a' c=' parse str' * (e) = 'ng!' ==> e='ng!' * * To some extent, one might say that there are one anchor between * each variable, since these match a sequence of blank characters. * However, these have less priority than the explicit patterns. * * This file makes available three functions: * * doparse() parses a single string into a single template * parseargtree() parses a set of strings into a set of templates * bmstrstr() implementation of Boyer-Moore string search */ #include "rexx.h" #include #include /* Stupid SunOS acc uses stderr in assert(), yuk! */ #include #include "strengs.h" /* * Using the 'tracestat' field of 'currlevel' in order to determine * the current tracing mode. */ /* * This file-scope variable 'traceparse' is use to cache the value of the * setting of the current trace mode. It is initialized at the entrypoint of * each parse statement. However, if functionality is expanded, so that * expression can occur inside a template, then this variable must be * checked in order to ensure that it is up-to-date after the expression * has been evaluated. */ /* * We have to seek for the nullstring rather often, so we make it a * file-scope variable, in order to optimize a bit. This way, we have * to neither allocate space for it, or deallocate it. */ static const streng nullstring={ 0, 0, "" } ; /* * This is an implementation of the strstr() function, for the 'streng' * datatype. The algorithm is a straight forward implementation of the * Boyer-Moore string search algorithm. * * The input parameters are first the string to search in, then the start * position of the search in that string, and then the string to search * for. If the whole of the input string is to be searched, then the * start position is set to zero. If start position is set to one, then * a match will not be found if it includes the first character of the * the string 'heystack' as the first character of the match. * * The returned value is an integer, which will be the index of the * first character of 'heystack->value' that match. If no match is * found, -1 is returned, if a match is found in the start of 'heystack' * then 0 is returned. This means that both the 'start' parameter and * the return value are zero-based. */ int bmstrstr( const streng *heystack, int Offset, const streng *needle, int caseless ) { const unsigned char *TmpPtr, *TmpPtr2; int NeedLen, HeyLen; const unsigned char *NeedPtr, *HeyPtr, *HeyBase; unsigned int NextChr[256]; int Tmp; const unsigned char *eptr; NeedPtr = (const unsigned char *) needle->value; NeedLen = needle->len; HeyBase = (const unsigned char *) heystack->value; HeyLen = heystack->len - Offset; HeyPtr = HeyBase + Offset; /* * Check for a fast break-out first. */ if ( HeyLen < NeedLen ) return -1; /* * Next, sometimes we want to search for one character only. Although * Boyer-Moore works for that case, it is hardly efficient. So, if the * search pattern has length one, we use the ANSI C memchr() to find * the string. That function is likely to to be more efficient, maybe * even written in hand-optimized assembly. */ if (NeedLen==1) { #ifdef __CHECKER__ /* Stupid Checker 0.9.9.1, FGC */ if (HeyLen == 0) return -1; #endif if ( caseless ) { /* * We assume that two memchrs are much faster than several toupper * or tolower. This is not true always, but the opposite is even * wrong. */ TmpPtr = (const unsigned char *)memchr( HeyPtr, rx_toupper( *NeedPtr ), HeyLen ); TmpPtr2 = (const unsigned char *)memchr( HeyPtr, rx_tolower( *NeedPtr ), HeyLen ); if ( TmpPtr == NULL ) TmpPtr = TmpPtr2; else if ( ( TmpPtr2 != NULL ) && ( TmpPtr2 < TmpPtr ) ) TmpPtr = TmpPtr2; } else TmpPtr = (const unsigned char *)memchr( HeyPtr, *NeedPtr, HeyLen ); if ( TmpPtr ) return TmpPtr - HeyBase; else return -1; } /* * OK, here is the 'real' search. Basically, it consists of two * phases: first a table (next) is built up, and then the string * is searched using the table to decide how far to hop if a match * was not found. * * Let's recount some of the theory behind Boyer-Moore search. If you * got a pattern, P, and string to search in, S, then the first match * may be S[1..len(P)]. To verify whether that is actually a match, * we have to iterate through all the characters, i.e. over len(P). * * If that is a match, then return the correct position, else we must * continue. Here comes the 'tricky' part. Suppose P is 'abcccd' and * that S is 'gddeebfgghhhiiijjj'. Now we check character S[len(P)] * and depending on its value we can determine something about the * possibiltiy of having a match starting somewhere in the area from * S[1] to S[len(P)]. Clearly, if S[len(P)] is a character not in P, * then no match can occur in this area. Else, determine the first, * of the next possible match, and move forward to check that. * * * First, we have to set up the table to use during the search. * Initially, we fill the whole table with the 'default' value, and * then we patch the values which should have other values in the * loop following the call to memset(). */ for ( Tmp = 0; Tmp < 256; Tmp++ ) NextChr[Tmp] = NeedLen; eptr = HeyPtr + HeyLen - NeedLen; NeedLen--; TmpPtr = NeedPtr; if ( caseless ) { for (Tmp = NeedLen; Tmp >= 0; Tmp--, TmpPtr++ ) NextChr[rx_tolower(*TmpPtr)] = Tmp; while ( HeyPtr <= eptr ) { Tmp = NextChr[rx_tolower(HeyPtr[NeedLen])]; if ( !Tmp ) { /* * A hit here doesn't mean that we actually have the match. It is a * possible match. We still have to compare the whole string. * Remember: Boyer-Moore reduces the lookups for a proper start of * the string, not the string comparisons itself. * * The last character matches, so compare the start. * NeedLen = Str_len( needle ) - 1; */ if ( mem_cmpic( HeyPtr, NeedPtr, NeedLen ) == 0 ) return HeyPtr - HeyBase; HeyPtr++; } else HeyPtr += Tmp; } } else { /* * For comments see above. */ for (Tmp = NeedLen; Tmp >= 0; Tmp--, TmpPtr++ ) NextChr[*TmpPtr] = Tmp; while ( HeyPtr <= eptr ) { Tmp = NextChr[HeyPtr[NeedLen]]; if ( !Tmp ) { if ( memcmp( HeyPtr, NeedPtr, NeedLen ) == 0 ) return HeyPtr - HeyBase; HeyPtr++; } else HeyPtr += Tmp; } } return -1; } static const streng *handle_var( tsd_t *TSD, nodeptr thisptr ) { if (thisptr->type == X_HEAD_SYMBOL) return fix_compound( TSD, thisptr, NULL ) ; else return shortcut( TSD, thisptr ) ; } /* * This parses a part of the source string, determined by (start) * and (len) into the variables of the (thisptr) tree. Only variables * are handled, not patterns. It will be called by doparse() to fit a * string into a set of variables and placeholder. * * Start points to the first character to be parsed, while len gives the * length of the string. len MUST be >= 0, which is currently detected by * doparse. * * There is no returnvalue from this function, it is only called to * achieve the special effects of setting variables and tracing * variables and placeholders. Actually, this routine used to be * tailrecursive, but I changed it into a goto. * * The variables and placeholders to parse ares stored in a chained * of pointers, chased through p[0]. 'start' is a ptr to the first * characters to be parsed by this function. 'len' gives the length * of the string to be parsed by this function. */ static void doparse3( tsd_t *TSD, cnodeptr thisptr, const char *start, int len ) { int wordlen ; streng *tptr ; int CutLast = 0; /* see below */ recurse: assert(len >= 0); /* * Since we are going to put the next word of the input string * into a variable, we must first find that value. The if tests * whether we are the last word before an 'anchor' to be parsed. * if so, use the rest of the string. If not, scan forwards to * identify a word. */ if (thisptr->p[0]) { /* * We shall only fetch out one word. First skip leading spaces, * then find the end of the next word. */ while (len && rx_isspace(*start)) { start++; len--; } wordlen = 0; while ((wordlen < len) && !rx_isspace(start[wordlen])) wordlen++; } else { /* * We are last word, use rest of string as value. * FGC: This is NOT true. Accoring to ANSI standard, we have to * cut the first char if it is a space AND it is not * the only pattern to match. */ if (CutLast && len && rx_isspace(*start)) { start++; len--; } wordlen = len; } CutLast = 1; /* * We have found the word to be parsed into something. Now we have * to decide what to parse it into. There are two possibilities. * It might be a variable, or just a placeholder (dot). The two are * handled in each part of the if-statement below. The setting of * 'tptr' could be lifted out of the if-statement to save space, * but at the cost of MUCH more CPU. * DON'T DO IT! */ if ( thisptr->type == X_TPL_SYMBOL ) { tptr = Str_ncreTSD( start, wordlen ); if ( TSD->traceparse ) tracevalue( TSD, tptr, '>' ); if ( thisptr->p[1]->type == X_HEAD_SYMBOL ) fix_compound( TSD, thisptr->p[1], tptr ); else { if ( KNOWN_RESERVED( thisptr->p[1]->name->value, thisptr->p[1]->name->len ) ) { exiterror( ERR_INVALID_START, 3, tmpstr_of( TSD, thisptr->p[1]->name ) ); } else { setshortcut( TSD, thisptr->p[1], tptr ); } } } else { /* * It's a placeholder, actually, we skip this if we arn't * tracing. No harm is done if tracevalue() is called unnecessary, * but this way we save three function calls whenever we're not * doing TRACE INT. * * The three operations below do: 1) get the value to be traced, * 2) then output the trace information, 3) and then free the * temporary storage. */ if ( TSD->traceparse ) { tptr = Str_ncreTSD( start, wordlen ); tracevalue( TSD, tptr, '.' ); Free_stringTSD( tptr ); } } /* * Now, this should actually be a tail recursion, but since be don't * trust compilers, we are optimizeing it ourselves. */ if ((thisptr = thisptr->p[0]) != NULL) { start += wordlen ; len -= wordlen ; goto recurse ; } } /* * This routine parses a string (source) into the template that is * specified by the structure in the (thisptr) tree. It handles find the next * template, and handles the aread between two templates. * * It calls it self recursively to handle a sequence of templates. * Well, actually, it used to call it self recuseively, but the * tail recursion has been removed to improve efficiency. * * A sequence of patterns must be chained together using p[1], while * each pattern can contain the vars/placeholders as a chain linked * in at p[0]. * * 'source' is the string to be parsed, 'thisptr' it a ptr to the top * of the parsetree that describes how 'source' after start'th * position is to be parsed. 'start' is a ptr to the first char in * 'source' to be parsed by this part of the template. */ void doparse( tsd_t *TSD, const streng *source, cnodeptr thisptr, int caseless ) { int start=0,point=0,length=0, end=0, nextstart=0, solid=0 ; const streng *pattern=NULL ; const streng *xtmp=NULL ; char tch=' ' ; nextstart = 0 ; /* too keep gcc from complaining about uninitialized */ tch = TSD->currlevel->tracestat ; TSD->traceparse = ((tch=='I') || (tch=='R')) ; recurse: /* * Cache the length of source, to avoid chasing ponters later. * Then make pattern default to the nullstring. The nullstring is * so muched used, that we don't want to allocate and deallocate * that all the time. */ length = source->len ; pattern = &nullstring ; /* * There are two main cases, either this is the last pattern, in * which case we use the rest of the string. Or either there is * another pattern further out, in which case we have to find it. * */ if (thisptr->p[1]) { /* * We are not the last pattern, so first find the next pattern. * First cache the type, so we don't chase pointers. There are * two main choises: either seek for a string of some sort, or * use an offset of some sort. */ solid = thisptr->p[1]->type ; if ((solid==X_TPL_MVE)||(solid==X_TPL_VAR)) { /* * The pattern to search for is either a literal string, or it * is the value hold in a variable, set pattern to whatever * it might be. Pattern previous points to a statically * allocated variable, so don't bother to deallocate. */ if (solid==X_TPL_MVE) pattern = thisptr->p[1]->name ; else pattern = handle_var( TSD, thisptr->p[1]->p[0] ) ; /* * Then we must find where in the source string pattern occurs. * If it don't occur there, we use the rest of the string, else * we use the string up to, but not including, the first char * that matched pattern. The 'bmstrstr' returns -1 for not * found, so correct that to rest-of-string. Also note that if * the pattern is the nullstring, it should match the end of * the string. */ if (Str_len(pattern)) { end = bmstrstr( source, start, pattern, caseless ) ; if (end<0) { point = end = length ; nextstart = end ; } else { nextstart = end + Str_len(pattern) ; point = end ; } } else { nextstart = point = end = length ; } /* * While 'end' marks how much to stuff into variables, nextstart * marks where to start the search for the next pattern (if * any). Remember that patterns "eat" up the part of the * parse string that they match. */ /* nextstart = end + Str_len(pattern) ; */ } else { /* * The next pattern to match is not a string to match, but a * positional movement, which will always be numeric, and if * it contains a sign, that should have been stripped off during * parsing. But a variable may be negative, too. */ if (thisptr->p[1]->name) xtmp = thisptr->p[1]->name ; else xtmp = handle_var( TSD, thisptr->p[1]->p[0] ) ; end = streng_to_int( TSD, xtmp, &nextstart ) ; if (nextstart) exiterror( ERR_INVALID_INTEGER, 4, tmpstr_of( TSD, xtmp ) ); /* * Depending on what sort of positional movement, do the right * thing. */ if (solid==X_NEG_OFFS) { /* * If it is a movement backwards, the concept goes something * like move-it-foreward-to-a-backwards-position. That is, * the string to be parsed continues forwards to the end of * the sting and stops there, while the nextposition wraps * round to the start again. * * Anyway, parse all the rest of the sting in this parse, and * start on the specified position for the next parse. */ start = point ; nextstart = point - end ; end = length ; if (nextstart > length) nextstart = length; if (nextstart < 0) nextstart = 0; point = nextstart ; } else if (solid==X_POS_OFFS) { /* * If the movement is forward, it is simpler, just move the * position of both the end of thisptr, and the start of next * to the right point. */ start = point ; nextstart = point + end ; if (nextstart > length) nextstart = length; if (nextstart < 0) nextstart = 0; end = nextstart ; if (end<=start) end = length ; point = nextstart ; } else if (solid==X_ABS_OFFS) { /* * Same applies if the position is absolute, just move it. */ end--; if (end > length) end = length; if (end < 0) /* fixes bug 1107757 */ end = 0; point = nextstart = end; if (end <= start) end = length; } } } else /* * We are last pattern to match, set the end of the string to * be parsed to the rest of the string available. */ end = nextstart = length ; /* * Make sure that we didn't do anything illegal when we pushed * around on the value of end and nextstart. These should have been * set correctly in the statements above. */ assert((0<=nextstart) && (nextstart<=length)) ; /* * Then handle end. It must be _after_ the last character in * the pattern, while it must not be larger than length. */ assert((start <= end) && (end <= length)) ; /* * Now we have marked off an area to be parsed, so call 'doparse3' to * put values into the variables. Note that end is decremented, * since doparse3 expects ptr to last char to use, not ptr to char * after last char to use. */ if (thisptr->p[0]) { doparse3( TSD, thisptr->p[0], source->value+start, end-start); --end; } /* * Then make a tailrecursive call, or rather, simulate one. This * operation will take care of the next set of variables to be * parsed values into. */ if ((thisptr=thisptr->p[2]) != NULL) { start = nextstart ; goto recurse ; } } /* * A single parse clause can parse multiple strings into multiple * patterns. Normally, this is only done using 'parse arg'. The * following piece of code parses multiples strings in an structure * of arguments into the matching pattern. * * There are no limits on the number of arguments to be parsed, * other than memory. */ void parseargtree( tsd_t *TSD, cparamboxptr argbox, cnodeptr thisptr, int flags ) { const streng *source ; streng *upplow ; /* * All templates in a list of template are connected though the * next field of the template. */ for (; thisptr; thisptr=thisptr->next) { assert(thisptr->type==X_TPL_SOLID) ; /* * Else, it is a tempate into which a string is to be parsed. * That string is an argument, to first get that argument, * if it exist, else use the nullstring. Never bother about * deallocating thisptr string; either it is part of an arguemnt * which is deallocated somewhere else, or it is the statically * allocated nullstring. */ if ((argbox)&&(argbox->value)) source = argbox->value ; else source = &nullstring ; if (flags & PARSE_UPPER) { upplow = Str_upper( Str_dupTSD( source )) ; doparse( TSD, upplow, thisptr, flags & PARSE_CASELESS ) ; Free_stringTSD( upplow ) ; } else if (flags & PARSE_LOWER) { upplow = Str_lower( Str_dupTSD( source )) ; doparse( TSD, upplow, thisptr, flags & PARSE_CASELESS ) ; Free_stringTSD( upplow ) ; } else doparse( TSD, source, thisptr, flags & PARSE_CASELESS ) ; if (argbox) argbox = argbox->next ; } }