Debian Codegraph @

parsing.c

raw
1 /*
2 * The Regina Rexx Interpreter
3 * Copyright (C) 1992-1994 Anders Christensen <[email protected]>
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
15 * You should have received a copy of the GNU Library General Public
16 * License along with this library; if not, write to the Free
17 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19
20 /*
21 * This implementation of the REXX parse template is quite near to
22 * what Cowlishaw specified in his book, but there is one very
23 * important difference. Cowlishaw sees a template as patterns and
24 * variables, with patterns in each end (and some of the patterns
25 * and/or the variables might be empty).
26 *
27 * The concept here is any sequence of variables and patterns, and
28 * the system is parsed into two levels and interpreted as such.
29 * First there is the level of patterns, which is anchored to
30 * particular locations in the string to be parsed.
31 *
32 * When the anchor-points are determined, the variables are filled
33 * in with the parts of the string that comes between each anchor.
34 * Here is an example:
35 *
36 * parse value 'That is a parse string!' with a b 'is' c d 'i' e
37 *
38 * In this example, there are four anchors in the string, the two
39 * patterns 'is' and 'i', and the two implicit anchors start-of-string
40 * and end-of-string. They anchor particular locations in the string
41 * to the lists of variables: (a b), (c d) and (e). At the first level
42 * the anchors are found and the text between them are deternmined
43 * (SOS=Start-Of-String, EOS=End-Of-String):
44 *
45 * That is a parse string!
46 * anchors (SOS)-----is------------i---(EOS)
47 * strings in-between <a b> <<<<c d>>>>> <e>
48 *
49 * Now, we have a set of substrings, and to each substring, there is
50 * possibly empty set of variable which are to receive its value from
51 * the contents of that substring. Doing that, we get:
52 *
53 * (a b) = 'That ' ==> a='That' b=' '
54 * (c d) = ' a parse str' ==> c='a' c=' parse str'
55 * (e) = 'ng!' ==> e='ng!'
56 *
57 * To some extent, one might say that there are one anchor between
58 * each variable, since these match a sequence of blank characters.
59 * However, these have less priority than the explicit patterns.
60 *
61 * This file makes available three functions:
62 *
63 * doparse() parses a single string into a single template
64 * parseargtree() parses a set of strings into a set of templates
65 * bmstrstr() implementation of Boyer-Moore string search
66 */
67
68 #include "rexx.h"
69 #include <string.h>
70 #include <stdio.h> /* Stupid SunOS acc uses stderr in assert(), yuk! */
71 #include <assert.h>
72 #include "strengs.h"
73
74 /*
75 * Using the 'tracestat' field of 'currlevel' in order to determine
76 * the current tracing mode.
77 */
78
79 /*
80 * This file-scope variable 'traceparse' is use to cache the value of the
81 * setting of the current trace mode. It is initialized at the entrypoint of
82 * each parse statement. However, if functionality is expanded, so that
83 * expression can occur inside a template, then this variable must be
84 * checked in order to ensure that it is up-to-date after the expression
85 * has been evaluated.
86 */
87
88 /*
89 * We have to seek for the nullstring rather often, so we make it a
90 * file-scope variable, in order to optimize a bit. This way, we have
91 * to neither allocate space for it, or deallocate it.
92 */
93 static const streng nullstring={ 0, 0, "" } ;
94
95 /*
96 * This is an implementation of the strstr() function, for the 'streng'
97 * datatype. The algorithm is a straight forward implementation of the
98 * Boyer-Moore string search algorithm.
99 *
100 * The input parameters are first the string to search in, then the start
101 * position of the search in that string, and then the string to search
102 * for. If the whole of the input string is to be searched, then the
103 * start position is set to zero. If start position is set to one, then
104 * a match will not be found if it includes the first character of the
105 * the string 'heystack' as the first character of the match.
106 *
107 * The returned value is an integer, which will be the index of the
108 * first character of 'heystack->value' that match. If no match is
109 * found, -1 is returned, if a match is found in the start of 'heystack'
110 * then 0 is returned. This means that both the 'start' parameter and
111 * the return value are zero-based.
112 */
113 int bmstrstr( const streng *heystack, int Offset, const streng *needle,
114 int caseless )
115 {
116 const unsigned char *TmpPtr, *TmpPtr2;
117 int NeedLen, HeyLen;
118 const unsigned char *NeedPtr, *HeyPtr, *HeyBase;
119 unsigned int NextChr[256];
120 int Tmp;
121 const unsigned char *eptr;
122
123 NeedPtr = (const unsigned char *) needle->value;
124 NeedLen = needle->len;
125
126 HeyBase = (const unsigned char *) heystack->value;
127 HeyLen = heystack->len - Offset;
128 HeyPtr = HeyBase + Offset;
129
130 /*
131 * Check for a fast break-out first.
132 */
133 if ( HeyLen < NeedLen )
134 return -1;
135
136 /*
137 * Next, sometimes we want to search for one character only. Although
138 * Boyer-Moore works for that case, it is hardly efficient. So, if the
139 * search pattern has length one, we use the ANSI C memchr() to find
140 * the string. That function is likely to to be more efficient, maybe
141 * even written in hand-optimized assembly.
142 */
143 if (NeedLen==1)
144 {
145 #ifdef __CHECKER__
146 /* Stupid Checker 0.9.9.1, FGC */
147 if (HeyLen == 0)
148 return -1;
149 #endif
150 if ( caseless )
151 {
152 /*
153 * We assume that two memchrs are much faster than several toupper
154 * or tolower. This is not true always, but the opposite is even
155 * wrong.
156 */
157 TmpPtr = (const unsigned char *)memchr( HeyPtr, rx_toupper( *NeedPtr ), HeyLen );
158 TmpPtr2 = (const unsigned char *)memchr( HeyPtr, rx_tolower( *NeedPtr ), HeyLen );
159 if ( TmpPtr == NULL )
160 TmpPtr = TmpPtr2;
161 else if ( ( TmpPtr2 != NULL ) && ( TmpPtr2 < TmpPtr ) )
162 TmpPtr = TmpPtr2;
163 }
164 else
165 TmpPtr = (const unsigned char *)memchr( HeyPtr, *NeedPtr, HeyLen );
166 if ( TmpPtr )
167 return TmpPtr - HeyBase;
168 else
169 return -1;
170 }
171
172 /*
173 * OK, here is the 'real' search. Basically, it consists of two
174 * phases: first a table (next) is built up, and then the string
175 * is searched using the table to decide how far to hop if a match
176 * was not found.
177 *
178 * Let's recount some of the theory behind Boyer-Moore search. If you
179 * got a pattern, P, and string to search in, S, then the first match
180 * may be S[1..len(P)]. To verify whether that is actually a match,
181 * we have to iterate through all the characters, i.e. over len(P).
182 *
183 * If that is a match, then return the correct position, else we must
184 * continue. Here comes the 'tricky' part. Suppose P is 'abcccd' and
185 * that S is 'gddeebfgghhhiiijjj'. Now we check character S[len(P)]
186 * and depending on its value we can determine something about the
187 * possibiltiy of having a match starting somewhere in the area from
188 * S[1] to S[len(P)]. Clearly, if S[len(P)] is a character not in P,
189 * then no match can occur in this area. Else, determine the first,
190 * of the next possible match, and move forward to check that.
191 *
192 *
193 * First, we have to set up the table to use during the search.
194 * Initially, we fill the whole table with the 'default' value, and
195 * then we patch the values which should have other values in the
196 * loop following the call to memset().
197 */
198 for ( Tmp = 0; Tmp < 256; Tmp++ )
199 NextChr[Tmp] = NeedLen;
200
201 eptr = HeyPtr + HeyLen - NeedLen;
202 NeedLen--;
203
204 TmpPtr = NeedPtr;
205
206 if ( caseless )
207 {
208 for (Tmp = NeedLen; Tmp >= 0; Tmp--, TmpPtr++ )
209 NextChr[rx_tolower(*TmpPtr)] = Tmp;
210
211 while ( HeyPtr <= eptr )
212 {
213 Tmp = NextChr[rx_tolower(HeyPtr[NeedLen])];
214 if ( !Tmp )
215 {
216 /*
217 * A hit here doesn't mean that we actually have the match. It is a
218 * possible match. We still have to compare the whole string.
219 * Remember: Boyer-Moore reduces the lookups for a proper start of
220 * the string, not the string comparisons itself.
221 *
222 * The last character matches, so compare the start.
223 * NeedLen = Str_len( needle ) - 1;
224 */
225 if ( mem_cmpic( HeyPtr, NeedPtr, NeedLen ) == 0 )
226 return HeyPtr - HeyBase;
227 HeyPtr++;
228 }
229 else
230 HeyPtr += Tmp;
231 }
232 }
233 else
234 {
235 /*
236 * For comments see above.
237 */
238 for (Tmp = NeedLen; Tmp >= 0; Tmp--, TmpPtr++ )
239 NextChr[*TmpPtr] = Tmp;
240
241 while ( HeyPtr <= eptr )
242 {
243 Tmp = NextChr[HeyPtr[NeedLen]];
244 if ( !Tmp )
245 {
246 if ( memcmp( HeyPtr, NeedPtr, NeedLen ) == 0 )
247 return HeyPtr - HeyBase;
248 HeyPtr++;
249 }
250 else
251 HeyPtr += Tmp;
252 }
253 }
254
255 return -1;
256 }
257
258
259 static const streng *handle_var( tsd_t *TSD, nodeptr thisptr )
260 {
261 if (thisptr->type == X_HEAD_SYMBOL)
262 return fix_compound( TSD, thisptr, NULL ) ;
263 else
264 return shortcut( TSD, thisptr ) ;
265 }
266
267 /*
268 * This parses a part of the source string, determined by (start)
269 * and (len) into the variables of the (thisptr) tree. Only variables
270 * are handled, not patterns. It will be called by doparse() to fit a
271 * string into a set of variables and placeholder.
272 *
273 * Start points to the first character to be parsed, while len gives the
274 * length of the string. len MUST be >= 0, which is currently detected by
275 * doparse.
276 *
277 * There is no returnvalue from this function, it is only called to
278 * achieve the special effects of setting variables and tracing
279 * variables and placeholders. Actually, this routine used to be
280 * tailrecursive, but I changed it into a goto.
281 *
282 * The variables and placeholders to parse ares stored in a chained
283 * of pointers, chased through p[0]. 'start' is a ptr to the first
284 * characters to be parsed by this function. 'len' gives the length
285 * of the string to be parsed by this function.
286 */
287 static void doparse3( tsd_t *TSD, cnodeptr thisptr, const char *start, int len )
288 {
289 int wordlen ;
290 streng *tptr ;
291 int CutLast = 0; /* see below */
292
293 recurse:
294 assert(len >= 0);
295 /*
296 * Since we are going to put the next word of the input string
297 * into a variable, we must first find that value. The if tests
298 * whether we are the last word before an 'anchor' to be parsed.
299 * if so, use the rest of the string. If not, scan forwards to
300 * identify a word.
301 */
302 if (thisptr->p[0])
303 {
304 /*
305 * We shall only fetch out one word. First skip leading spaces,
306 * then find the end of the next word.
307 */
308 while (len && rx_isspace(*start))
309 {
310 start++;
311 len--;
312 }
313
314 wordlen = 0;
315 while ((wordlen < len) && !rx_isspace(start[wordlen]))
316 wordlen++;
317 }
318 else
319 {
320 /*
321 * We are last word, use rest of string as value.
322 * FGC: This is NOT true. Accoring to ANSI standard, we have to
323 * cut the first char if it is a space AND it is not
324 * the only pattern to match.
325 */
326 if (CutLast && len && rx_isspace(*start))
327 {
328 start++;
329 len--;
330 }
331 wordlen = len;
332 }
333 CutLast = 1;
334
335 /*
336 * We have found the word to be parsed into something. Now we have
337 * to decide what to parse it into. There are two possibilities.
338 * It might be a variable, or just a placeholder (dot). The two are
339 * handled in each part of the if-statement below. The setting of
340 * 'tptr' could be lifted out of the if-statement to save space,
341 * but at the cost of MUCH more CPU.
342 * DON'T DO IT!
343 */
344 if ( thisptr->type == X_TPL_SYMBOL )
345 {
346 tptr = Str_ncreTSD( start, wordlen );
347 if ( TSD->traceparse )
348 tracevalue( TSD, tptr, '>' );
349
350 if ( thisptr->p[1]->type == X_HEAD_SYMBOL )
351 fix_compound( TSD, thisptr->p[1], tptr );
352 else
353 {
354 if ( KNOWN_RESERVED( thisptr->p[1]->name->value, thisptr->p[1]->name->len ) )
355 {
356 exiterror( ERR_INVALID_START, 3, tmpstr_of( TSD, thisptr->p[1]->name ) );
357 }
358 else
359 {
360 setshortcut( TSD, thisptr->p[1], tptr );
361 }
362 }
363 }
364 else
365 {
366 /*
367 * It's a placeholder, actually, we skip this if we arn't
368 * tracing. No harm is done if tracevalue() is called unnecessary,
369 * but this way we save three function calls whenever we're not
370 * doing TRACE INT.
371 *
372 * The three operations below do: 1) get the value to be traced,
373 * 2) then output the trace information, 3) and then free the
374 * temporary storage.
375 */
376
377 if ( TSD->traceparse )
378 {
379 tptr = Str_ncreTSD( start, wordlen );
380 tracevalue( TSD, tptr, '.' );
381 Free_stringTSD( tptr );
382 }
383 }
384
385 /*
386 * Now, this should actually be a tail recursion, but since be don't
387 * trust compilers, we are optimizeing it ourselves.
388 */
389 if ((thisptr = thisptr->p[0]) != NULL)
390 {
391 start += wordlen ;
392 len -= wordlen ;
393 goto recurse ;
394 }
395 }
396
397 /*
398 * This routine parses a string (source) into the template that is
399 * specified by the structure in the (thisptr) tree. It handles find the next
400 * template, and handles the aread between two templates.
401 *
402 * It calls it self recursively to handle a sequence of templates.
403 * Well, actually, it used to call it self recuseively, but the
404 * tail recursion has been removed to improve efficiency.
405 *
406 * A sequence of patterns must be chained together using p[1], while
407 * each pattern can contain the vars/placeholders as a chain linked
408 * in at p[0].
409 *
410 * 'source' is the string to be parsed, 'thisptr' it a ptr to the top
411 * of the parsetree that describes how 'source' after start'th
412 * position is to be parsed. 'start' is a ptr to the first char in
413 * 'source' to be parsed by this part of the template.
414 */
415
416 void doparse( tsd_t *TSD, const streng *source, cnodeptr thisptr, int caseless )
417 {
418 int start=0,point=0,length=0, end=0, nextstart=0, solid=0 ;
419 const streng *pattern=NULL ;
420 const streng *xtmp=NULL ;
421 char tch=' ' ;
422
423 nextstart = 0 ; /* too keep gcc from complaining about uninitialized */
424 tch = TSD->currlevel->tracestat ;
425 TSD->traceparse = ((tch=='I') || (tch=='R')) ;
426
427 recurse:
428 /*
429 * Cache the length of source, to avoid chasing ponters later.
430 * Then make pattern default to the nullstring. The nullstring is
431 * so muched used, that we don't want to allocate and deallocate
432 * that all the time.
433 */
434 length = source->len ;
435 pattern = &nullstring ;
436
437 /*
438 * There are two main cases, either this is the last pattern, in
439 * which case we use the rest of the string. Or either there is
440 * another pattern further out, in which case we have to find it.
441 *
442 */
443 if (thisptr->p[1])
444 {
445 /*
446 * We are not the last pattern, so first find the next pattern.
447 * First cache the type, so we don't chase pointers. There are
448 * two main choises: either seek for a string of some sort, or
449 * use an offset of some sort.
450 */
451 solid = thisptr->p[1]->type ;
452 if ((solid==X_TPL_MVE)||(solid==X_TPL_VAR))
453 {
454 /*
455 * The pattern to search for is either a literal string, or it
456 * is the value hold in a variable, set pattern to whatever
457 * it might be. Pattern previous points to a statically
458 * allocated variable, so don't bother to deallocate.
459 */
460 if (solid==X_TPL_MVE)
461 pattern = thisptr->p[1]->name ;
462 else
463 pattern = handle_var( TSD, thisptr->p[1]->p[0] ) ;
464 /*
465 * Then we must find where in the source string pattern occurs.
466 * If it don't occur there, we use the rest of the string, else
467 * we use the string up to, but not including, the first char
468 * that matched pattern. The 'bmstrstr' returns -1 for not
469 * found, so correct that to rest-of-string. Also note that if
470 * the pattern is the nullstring, it should match the end of
471 * the string.
472 */
473 if (Str_len(pattern))
474 {
475 end = bmstrstr( source, start, pattern, caseless ) ;
476 if (end<0)
477 {
478 point = end = length ;
479 nextstart = end ;
480 }
481 else
482 {
483 nextstart = end + Str_len(pattern) ;
484 point = end ;
485 }
486 }
487 else
488 {
489 nextstart = point = end = length ;
490 }
491
492 /*
493 * While 'end' marks how much to stuff into variables, nextstart
494 * marks where to start the search for the next pattern (if
495 * any). Remember that patterns "eat" up the part of the
496 * parse string that they match.
497 */
498 /* nextstart = end + Str_len(pattern) ; */
499 }
500 else
501 {
502 /*
503 * The next pattern to match is not a string to match, but a
504 * positional movement, which will always be numeric, and if
505 * it contains a sign, that should have been stripped off during
506 * parsing. But a variable may be negative, too.
507 */
508 if (thisptr->p[1]->name)
509 xtmp = thisptr->p[1]->name ;
510 else
511 xtmp = handle_var( TSD, thisptr->p[1]->p[0] ) ;
512
513 end = streng_to_int( TSD, xtmp, &nextstart ) ;
514 if (nextstart)
515 exiterror( ERR_INVALID_INTEGER, 4, tmpstr_of( TSD, xtmp ) );
516
517 /*
518 * Depending on what sort of positional movement, do the right
519 * thing.
520 */
521 if (solid==X_NEG_OFFS)
522 {
523 /*
524 * If it is a movement backwards, the concept goes something
525 * like move-it-foreward-to-a-backwards-position. That is,
526 * the string to be parsed continues forwards to the end of
527 * the sting and stops there, while the nextposition wraps
528 * round to the start again.
529 *
530 * Anyway, parse all the rest of the sting in this parse, and
531 * start on the specified position for the next parse.
532 */
533 start = point ;
534 nextstart = point - end ;
535 end = length ;
536 if (nextstart > length)
537 nextstart = length;
538 if (nextstart < 0)
539 nextstart = 0;
540
541 point = nextstart ;
542 }
543
544 else if (solid==X_POS_OFFS)
545 {
546 /*
547 * If the movement is forward, it is simpler, just move the
548 * position of both the end of thisptr, and the start of next
549 * to the right point.
550 */
551 start = point ;
552 nextstart = point + end ;
553 if (nextstart > length)
554 nextstart = length;
555 if (nextstart < 0)
556 nextstart = 0;
557 end = nextstart ;
558 if (end<=start)
559 end = length ;
560
561 point = nextstart ;
562 }
563
564 else if (solid==X_ABS_OFFS)
565 {
566 /*
567 * Same applies if the position is absolute, just move it.
568 */
569 end--;
570 if (end > length)
571 end = length;
572 if (end < 0) /* fixes bug 1107757 */
573 end = 0;
574
575 point = nextstart = end;
576 if (end <= start)
577 end = length;
578 }
579 }
580 }
581 else
582 /*
583 * We are last pattern to match, set the end of the string to
584 * be parsed to the rest of the string available.
585 */
586 end = nextstart = length ;
587
588 /*
589 * Make sure that we didn't do anything illegal when we pushed
590 * around on the value of end and nextstart. These should have been
591 * set correctly in the statements above.
592 */
593 assert((0<=nextstart) && (nextstart<=length)) ;
594
595 /*
596 * Then handle end. It must be _after_ the last character in
597 * the pattern, while it must not be larger than length.
598 */
599 assert((start <= end) && (end <= length)) ;
600
601 /*
602 * Now we have marked off an area to be parsed, so call 'doparse3' to
603 * put values into the variables. Note that end is decremented,
604 * since doparse3 expects ptr to last char to use, not ptr to char
605 * after last char to use.
606 */
607 if (thisptr->p[0])
608 {
609 doparse3( TSD, thisptr->p[0], source->value+start, end-start);
610 --end;
611 }
612
613 /*
614 * Then make a tailrecursive call, or rather, simulate one. This
615 * operation will take care of the next set of variables to be
616 * parsed values into.
617 */
618 if ((thisptr=thisptr->p[2]) != NULL)
619 {
620 start = nextstart ;
621 goto recurse ;
622 }
623
624 }
625
626
627
628 /*
629 * A single parse clause can parse multiple strings into multiple
630 * patterns. Normally, this is only done using 'parse arg'. The
631 * following piece of code parses multiples strings in an structure
632 * of arguments into the matching pattern.
633 *
634 * There are no limits on the number of arguments to be parsed,
635 * other than memory.
636 */
637 void parseargtree( tsd_t *TSD, cparamboxptr argbox, cnodeptr thisptr, int flags )
638 {
639 const streng *source ;
640 streng *upplow ;
641
642 /*
643 * All templates in a list of template are connected though the
644 * next field of the template.
645 */
646 for (; thisptr; thisptr=thisptr->next)
647 {
648 assert(thisptr->type==X_TPL_SOLID) ;
649
650 /*
651 * Else, it is a tempate into which a string is to be parsed.
652 * That string is an argument, to first get that argument,
653 * if it exist, else use the nullstring. Never bother about
654 * deallocating thisptr string; either it is part of an arguemnt
655 * which is deallocated somewhere else, or it is the statically
656 * allocated nullstring.
657 */
658 if ((argbox)&&(argbox->value))
659 source = argbox->value ;
660 else
661 source = &nullstring ;
662
663 if (flags & PARSE_UPPER)
664 {
665 upplow = Str_upper( Str_dupTSD( source )) ;
666 doparse( TSD, upplow, thisptr, flags & PARSE_CASELESS ) ;
667 Free_stringTSD( upplow ) ;
668 }
669 else if (flags & PARSE_LOWER)
670 {
671 upplow = Str_lower( Str_dupTSD( source )) ;
672 doparse( TSD, upplow, thisptr, flags & PARSE_CASELESS ) ;
673 Free_stringTSD( upplow ) ;
674 }
675 else
676 doparse( TSD, source, thisptr, flags & PARSE_CASELESS ) ;
677
678 if (argbox)
679 argbox = argbox->next ;
680 }
681 }