« back to all changes in this revision
Viewing changes to src/regexp.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Christian Marillat
- Date: 2001-11-13 15:06:22 UTC
- Revision ID: james.westby@ubuntu.com-20011113150622-vgmgmk6srj3kldr3
Tags: upstream-0.15.2
Import upstream version 0.15.2
- files added:
- doc
- intl
- lisp
- lisp/rep
- lisp/rep/data
- lisp/rep/i18n
- lisp/rep/io
- lisp/rep/io/file-handlers
- lisp/rep/io/file-handlers/remote
- lisp/rep/lang
- lisp/rep/mail
- lisp/rep/net
- lisp/rep/system
- lisp/rep/test
- lisp/rep/threads
- lisp/rep/util
- lisp/rep/vm
- lisp/rep/vm/compiler
- lisp/rep/www
- lisp/scheme
- lisp/unscheme
- man
- src
added
removed
src/regexp.c
1
/*
2
* regcomp and regexec -- regsub and regerror are elsewhere @(#)regexp.c 1.3
3
* of 18 April 87
4
*
5
* Copyright (c) 1986 by University of Toronto. Written by Henry Spencer. Not
6
* derived from licensed software.
7
*
8
* Permission is granted to anyone to use this software for any purpose on any
9
* computer system, and to redistribute it freely, subject to the following
10
* restrictions:
11
*
12
* 1. The author is not responsible for the consequences of use of this
13
* software, no matter how awful, even if they arise from defects in it.
14
*
15
* 2. The origin of this software must not be misrepresented, either by explicit
16
* claim or by omission.
17
*
18
* 3. Altered versions must be plainly marked as such, and must not be
19
* misrepresented as being the original software.
20
*
21
* Beware that some of this code is subtly aware of the way operator precedence
22
* is structured in regular expressions. Serious changes in
23
* regular-expression syntax might require a total rethink.
24
*/
25
26
/* Lots of changes for Jade. See the file README.regexp for more details */
27
28
#define _GNU_SOURCE
29
30
#define rep_NEED_REGEXP_INTERNALS
31
#include "repint.h"
32
33
#include <stdio.h>
34
#include <string.h>
35
#include <stdlib.h>
36
#include <ctype.h>
37
38
#undef DEBUG
39
40
/*
41
* Utility definitions.
42
*/
43
#ifndef CHARBITS
44
#define UCHARAT(p) ((int)*(unsigned char *)(p))
45
#else
46
#define UCHARAT(p) ((int)*(p)&CHARBITS)
47
#endif
48
49
#define FAIL(m) { rep_regerror(m); return(NULL); }
50
#define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')
51
#define META "^$.[()|?+*\\"
52
53
/*
54
* Flags to be passed up and down.
55
*/
56
#define HASWIDTH 01 /* Known never to match null string. */
57
#define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
58
#define SPSTART 04 /* Starts with * or +. */
59
#define WORST 0 /* Worst case. */
60
61
/*
62
* Global work variables for regcomp().
63
*/
64
static char *regparse; /* Input-scan pointer. */
65
static int regnpar; /* () count. */
66
static char regdummy;
67
static char *regcode; /* Code-emit pointer; ®dummy = don't. */
68
static long regsize; /* Code size. */
69
70
/*
71
* Forward declarations for regcomp()'s friends.
72
*/
73
static char *reg(int, int *);
74
static char *regbranch(int *);
75
static char *regpiece(int *);
76
static char *regatom(int *);
77
static char *regnode(char);
78
static char *regnext(char *);
79
static void regc(char);
80
static void reginsert(char, char *);
81
static void regtail(char *, char *);
82
static void regoptail(char *, char *);
83
extern void rep_regerror(char *);
84
#ifdef DEBUG
85
void regdump(rep_regexp *);
86
int regenable_debug = 0;
87
#endif
88
89
#ifndef HAVE_STRCSPN
90
int strcspn(char *, char *);
91
#endif
92
93
/*
94
* - regcomp - compile a regular expression into internal code
95
*
96
* We can't allocate space until we know how big the compiled form will be, but
97
* we can't compile it (and thus know how big it is) until we've got a place
98
* to put the code. So we cheat: we compile it twice, once with code
99
* generation turned off and size counting turned on, and once "for real".
100
* This also means that we don't allocate space until we are sure that the
101
* thing really will compile successfully, and we never have to move the code
102
* and thus invalidate pointers into it. (Note that it has to be in one
103
* piece because free() must be able to free it all.)
104
*
105
* Beware that the optimization-preparation code in here knows about some of the
106
* structure of the compiled regexp.
107
*/
108
rep_regexp *
109
rep_regcomp(char *exp)
110
{
111
register rep_regexp *r;
112
register char *scan;
113
register char *longest;
114
register int len;
115
int flags;
116
117
if (exp == NULL)
118
FAIL("NULL argument");
119
120
/* First pass: determine size, legality. */
121
regparse = exp;
122
regnpar = 1;
123
regsize = 0L;
124
regcode = ®dummy;
125
regc(MAGIC);
126
if (reg(0, &flags) == NULL)
127
return (NULL);
128
129
/* Small enough for pointer-storage convention? */
130
if (regsize >= 32767L) /* Probably could be 65535L. */
131
FAIL("regexp too big");
132
133
/* Allocate space. */
134
r = (rep_regexp *) malloc(sizeof(rep_regexp) + (unsigned) regsize);
135
if (r == NULL)
136
FAIL("out of space");
137
138
/* Second pass: emit code. */
139
regparse = exp;
140
regnpar = 1;
141
regcode = r->program;
142
regc(MAGIC);
143
if (reg(0, &flags) == NULL)
144
return (NULL);
145
146
/* Dig out information for optimizations. */
147
r->regstart = '\0'; /* Worst-case defaults. */
148
r->reganch = 0;
149
r->regmust = NULL;
150
r->regmlen = 0;
151
r->regsize = sizeof(rep_regexp) + (unsigned)regsize;
152
scan = r->program + 1; /* First BRANCH. */
153
if (OP(regnext(scan)) == END) { /* Only one top-level choice. */
154
scan = OPERAND(scan);
155
156
/* Starting-point info. */
157
if (OP(scan) == EXACTLY)
158
r->regstart = UCHARAT(OPERAND(scan));
159
else if (OP(scan) == BOL)
160
r->reganch++;
161
162
/*
163
* If there's something expensive in the r.e., find the longest
164
* literal string that must appear and make it the regmust. Resolve
165
* ties in favor of later strings, since the regstart check works
166
* with the beginning of the r.e. and avoiding duplication
167
* strengthens checking. Not a strong reason, but sufficient in the
168
* absence of others.
169
*/
170
if (flags & SPSTART) {
171
longest = NULL;
172
len = 0;
173
for (; scan != NULL; scan = regnext(scan))
174
if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
175
longest = OPERAND(scan);
176
len = strlen(OPERAND(scan));
177
}
178
r->regmust = longest;
179
r->regmlen = len;
180
}
181
}
182
#ifdef DEBUG
183
if (regenable_debug) {
184
printf ("compiled `%s' to:\n", exp);
185
regdump (r);
186
}
187
#endif
188
return (r);
189
}
190
191
/*
192
* - reg - regular expression, i.e. main body or parenthesized thing
193
*
194
* Caller must absorb opening parenthesis.
195
*
196
* Combining parenthesis handling with the base level of regular expression is a
197
* trifle forced, but the need to tie the tails of the branches to what
198
* follows makes it hard to avoid.
199
*/
200
static char *
201
reg(int paren, int *flagp)
202
{
203
register char *ret;
204
register char *br;
205
register char *ender;
206
register int parno = 0;
207
int flags;
208
209
*flagp = HASWIDTH; /* Tentatively. */
210
211
/* Make an OPEN node, if parenthesized. */
212
if (paren) {
213
if (regnpar >= rep_NSUBEXP)
214
FAIL("too many ()");
215
parno = regnpar;
216
regnpar++;
217
ret = regnode(OPEN + parno);
218
} else
219
ret = NULL;
220
221
/* Pick up the branches, linking them together. */
222
br = regbranch(&flags);
223
if (br == NULL)
224
return (NULL);
225
if (ret != NULL)
226
regtail(ret, br); /* OPEN -> first. */
227
else
228
ret = br;
229
if (!(flags & HASWIDTH))
230
*flagp &= ~HASWIDTH;
231
*flagp |= flags & SPSTART;
232
while (*regparse == '|') {
233
regparse++;
234
br = regbranch(&flags);
235
if (br == NULL)
236
return (NULL);
237
regtail(ret, br); /* BRANCH -> BRANCH. */
238
if (!(flags & HASWIDTH))
239
*flagp &= ~HASWIDTH;
240
*flagp |= flags & SPSTART;
241
}
242
243
/* Make a closing node, and hook it on the end. */
244
ender = regnode((paren) ? CLOSE + parno : END);
245
regtail(ret, ender);
246
247
/* Hook the tails of the branches to the closing node. */
248
for (br = ret; br != NULL; br = regnext(br))
249
regoptail(br, ender);
250
251
/* Check for proper termination. */
252
if (paren && *regparse++ != ')') {
253
FAIL("unmatched ()");
254
} else if (!paren && *regparse != '\0') {
255
if (*regparse == ')') {
256
FAIL("unmatched ()");
257
} else
258
FAIL("junk on end");/* "Can't happen". */
259
/* NOTREACHED */
260
}
261
return (ret);
262
}
263
264
/*
265
* - regbranch - one alternative of an | operator
266
*
267
* Implements the concatenation operator.
268
*/
269
static char *
270
regbranch(int *flagp)
271
{
272
register char *ret;
273
register char *chain;
274
register char *latest;
275
int flags;
276
277
*flagp = WORST; /* Tentatively. */
278
279
ret = regnode(BRANCH);
280
chain = NULL;
281
while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
282
latest = regpiece(&flags);
283
if (latest == NULL)
284
return (NULL);
285
*flagp |= flags & HASWIDTH;
286
if (chain == NULL) /* First piece. */
287
*flagp |= flags & SPSTART;
288
else
289
regtail(chain, latest);
290
chain = latest;
291
}
292
if (chain == NULL) /* Loop ran zero times. */
293
(void) regnode(NOTHING);
294
295
return (ret);
296
}
297
298
/*
299
* - regpiece - something followed by possible [*+?]
300
*
301
* Note that the branching code sequences used for ? and the general cases of *
302
* and + are somewhat optimized: they use the same NOTHING node as both the
303
* endmarker for their branch list and the body of the last branch. It might
304
* seem that this node could be dispensed with entirely, but the endmarker
305
* role is not redundant.
306
*/
307
static char *
308
regpiece(int *flagp)
309
{
310
register char *ret;
311
register char op;
312
register char *next;
313
int flags;
314
int greedy;
315
316
ret = regatom(&flags);
317
if (ret == NULL)
318
return (NULL);
319
320
op = *regparse;
321
if (!ISMULT(op)) {
322
*flagp = flags;
323
return (ret);
324
}
325
if (!(flags & HASWIDTH) && op != '?')
326
FAIL("*+ operand could be empty");
327
*flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
328
greedy = (regparse[1] != '?');
329
330
if (op == '*' && (flags & SIMPLE))
331
reginsert(greedy ? STAR : NGSTAR, ret);
332
else if (op == '*') {
333
if (greedy) {
334
/* Emit x* as (x&|), where & means "self". */
335
reginsert(BRANCH, ret); /* Either x */
336
regoptail(ret, regnode(BACK)); /* and loop */
337
regoptail(ret, ret); /* back */
338
regtail(ret, regnode(BRANCH)); /* or */
339
regtail(ret, regnode(NOTHING)); /* null. */
340
} else {
341
/* Emit x*? as (|x&), where & means "self". */
342
reginsert(BRANCH, ret); /* Either */
343
reginsert(NOTHING, ret); /* null. */
344
reginsert(BRANCH, ret); /* or x */
345
regtail(ret+9, regnode(BACK)); /* and loop */
346
regtail(ret+9, ret); /* back */
347
regtail(ret, ret+6);
348
regtail(ret+3, regcode);
349
}
350
} else if (op == '+' && (flags & SIMPLE))
351
reginsert(greedy ? PLUS : NGPLUS, ret);
352
else if (op == '+') {
353
if (greedy) {
354
/* Emit x+ as x(&|), where & means "self". */
355
next = regnode(BRANCH); /* Either */
356
regtail(ret, next);
357
regtail(regnode(BACK), ret); /* loop back */
358
regtail(next, regnode(BRANCH)); /* or */
359
regtail(ret, regnode(NOTHING)); /* null. */
360
} else {
361
char *null, *b2;
362
/* Emit x+? as x(|&), where & means "self". */
363
next = regnode(BRANCH); /* Either */
364
regtail(ret, next);
365
null = regnode(NOTHING); /* null */
366
b2 = regnode(BRANCH);
367
regtail(regnode(BACK), ret); /* or loop back */
368
regtail(next, b2);
369
regtail(null, regcode);
370
}
371
} else if (op == '?') {
372
if (greedy) {
373
/* Emit x? as (x|) */
374
reginsert(BRANCH, ret); /* Either x */
375
regtail(ret, regnode(BRANCH)); /* or */
376
next = regnode(NOTHING); /* null. */
377
regtail(ret, next);
378
regoptail(ret, next);
379
} else {
380
/* Emit x?? as (|x) */
381
reginsert(BRANCH, ret);
382
reginsert(NOTHING, ret); /* Either null */
383
reginsert(BRANCH, ret); /* or x. */
384
regoptail(ret, regcode);
385
regtail(ret, ret + 6);
386
regtail(ret, regcode);
387
}
388
}
389
if (greedy)
390
regparse++;
391
else
392
regparse += 2;
393
if (ISMULT(*regparse))
394
FAIL("nested *?+");
395
396
return (ret);
397
}
398
399
/*
400
* - regatom - the lowest level
401
*
402
* Optimization: gobbles an entire sequence of ordinary characters so that it
403
* can turn them into a single node, which is smaller to store and faster to
404
* run. Backslashed characters are exceptions, each becoming a separate
405
* node; the code is simpler that way and it's not worth fixing.
406
*/
407
static char *
408
regatom(int *flagp)
409
{
410
register char *ret;
411
int flags;
412
413
*flagp = WORST; /* Tentatively. */
414
415
switch (*regparse++) {
416
case '^':
417
ret = regnode(BOL);
418
break;
419
case '$':
420
ret = regnode(EOL);
421
break;
422
case '.':
423
ret = regnode(ANY);
424
*flagp |= HASWIDTH | SIMPLE;
425
break;
426
case '[':{
427
register int class;
428
register int classend;
429
430
if (*regparse == '^') { /* Complement of range. */
431
ret = regnode(ANYBUT);
432
regparse++;
433
} else
434
ret = regnode(ANYOF);
435
if (*regparse == ']' || *regparse == '-')
436
regc(*regparse++);
437
while (*regparse != '\0' && *regparse != ']') {
438
if (*regparse == '-') {
439
regparse++;
440
if (*regparse == ']' || *regparse == '\0')
441
regc('-');
442
else {
443
class = UCHARAT(regparse - 2) + 1;
444
classend = UCHARAT(regparse);
445
if (class > classend + 1)
446
FAIL("invalid [] range");
447
for (; class <= classend; class++)
448
regc(class);
449
regparse++;
450
}
451
} else
452
regc(*regparse++);
453
}
454
regc('\0');
455
if (*regparse != ']')
456
FAIL("unmatched []");
457
regparse++;
458
*flagp |= HASWIDTH | SIMPLE;
459
}
460
break;
461
case '(':
462
ret = reg(1, &flags);
463
if (ret == NULL)
464
return (NULL);
465
*flagp |= flags & (HASWIDTH | SPSTART);
466
break;
467
case '\0':
468
case '|':
469
case ')':
470
FAIL("internal urp"); /* Supposed to be caught earlier. */
471
break;
472
case '?':
473
case '+':
474
case '*':
475
FAIL("?+* follows nothing");
476
break;
477
case '\\':
478
switch (*regparse++)
479
{
480
case '\0':
481
FAIL("trailing \\");
482
break;
483
case 'w':
484
ret = regnode (WORD);
485
*flagp |= HASWIDTH | SIMPLE;
486
break;
487
case 'W':
488
ret = regnode (NWORD);
489
*flagp |= HASWIDTH | SIMPLE;
490
break;
491
case 's':
492
ret = regnode (WSPC);
493
*flagp |= HASWIDTH | SIMPLE;
494
break;
495
case 'S':
496
ret = regnode (NWSPC);
497
*flagp |= HASWIDTH | SIMPLE;
498
break;
499
case 'd':
500
ret = regnode (DIGI);
501
*flagp |= HASWIDTH | SIMPLE;
502
break;
503
case 'D':
504
ret = regnode (NDIGI);
505
*flagp |= HASWIDTH | SIMPLE;
506
break;
507
case 'b':
508
ret = regnode (WEDGE);
509
break;
510
case 'B':
511
ret = regnode (NWEDGE);
512
break;
513
default:
514
ret = regnode(EXACTLY);
515
regc(regparse[-1]);
516
regc('\0');
517
*flagp |= HASWIDTH | SIMPLE;
518
}
519
break;
520
default:{
521
register int len;
522
register char ender;
523
524
regparse--;
525
len = strcspn(regparse, META);
526
if (len <= 0)
527
FAIL("internal disaster");
528
ender = *(regparse + len);
529
if (len > 1 && ISMULT(ender))
530
len--; /* Back off clear of ?+* operand. */
531
*flagp |= HASWIDTH;
532
if (len == 1)
533
*flagp |= SIMPLE;
534
ret = regnode(EXACTLY);
535
while (len > 0) {
536
regc(*regparse++);
537
len--;
538
}
539
regc('\0');
540
}
541
break;
542
}
543
544
return (ret);
545
}
546
547
/*
548
* - regnode - emit a node
549
*/
550
static char * /* Location. */
551
regnode(char op)
552
{
553
register char *ret;
554
register char *ptr;
555
556
ret = regcode;
557
if (ret == ®dummy) {
558
regsize += 3;
559
return (ret);
560
}
561
ptr = ret;
562
*ptr++ = op;
563
*ptr++ = '\0'; /* Null "next" pointer. */
564
*ptr++ = '\0';
565
regcode = ptr;
566
567
return (ret);
568
}
569
570
/*
571
* - regc - emit (if appropriate) a byte of code
572
*/
573
static void
574
regc(char b)
575
{
576
if (regcode != ®dummy)
577
*regcode++ = b;
578
else
579
regsize++;
580
}
581
582
/*
583
* - reginsert - insert an operator in front of already-emitted operand
584
*
585
* Means relocating the operand.
586
*/
587
static void
588
reginsert(char op, char *opnd)
589
{
590
register char *src;
591
register char *dst;
592
register char *place;
593
594
if (regcode == ®dummy) {
595
regsize += 3;
596
return;
597
}
598
src = regcode;
599
regcode += 3;
600
dst = regcode;
601
while (src > opnd)
602
*--dst = *--src;
603
604
place = opnd; /* Op node, where operand used to be. */
605
*place++ = op;
606
*place++ = '\0';
607
*place++ = '\0';
608
}
609
610
/*
611
* - regtail - set the next-pointer at the end of a node chain
612
*/
613
static void
614
regtail(char *p, char *val)
615
{
616
register char *scan;
617
register char *temp;
618
register int offset;
619
620
if (regcode == ®dummy)
621
return;
622
623
/* Find last node. */
624
scan = p;
625
for (;;) {
626
temp = regnext(scan);
627
if (temp == NULL)
628
break;
629
scan = temp;
630
}
631
632
if (OP(scan) == BACK)
633
offset = scan - val;
634
else
635
offset = val - scan;
636
*(scan + 1) = (offset >> 8) & 0377;
637
*(scan + 2) = offset & 0377;
638
}
639
640
/*
641
* - regoptail - regtail on operand of first argument; nop if operandless
642
*/
643
static void
644
regoptail(char *p, char *val)
645
{
646
/* "Operandless" and "op != BRANCH" are synonymous in practice. */
647
if (p == NULL || regcode == ®dummy || OP(p) != BRANCH)
648
return;
649
regtail(OPERAND(p), val);
650
}
651
652
/*
653
* regexec and friends
654
*/
655
656
/*
657
* Global work variables for regexec().
658
*/
659
static char *reginput; /* String-input pointer. */
660
static char *regbol; /* Beginning of input, for ^ check. */
661
static char **regstartp; /* Pointer to startp array. */
662
static char **regendp; /* Ditto for endp. */
663
static char regnocase; /* Ignore case when string-matching. */
664
static int regnest; /* depth of recursion */
665
666
int rep_regexp_max_depth = 2048;
667
668
/*
669
* Forwards.
670
*/
671
static int regtry(rep_regexp *, char *);
672
static int regmatch(char *);
673
static int regrepeat(char *);
674
675
#ifdef DEBUG
676
int regnarrate = 0;
677
char *regprop(char *);
678
#endif /* DEBUG */
679
680
681
/*
682
* - regexec - match a regexp against a string
683
*
684
* jsh -- changed regexec to regexec2 with an extra argument for flag bits,
685
* flags are REG_NOTBOL and REG_NOCASE.
686
*/
687
int
688
rep_regexec2(rep_regexp *prog, char *string, int eflags)
689
{
690
register char *s;
691
/* For REG_NOCASE and strpbrk() */
692
static char mat[3] = "xX";
693
694
/* Be paranoid... */
695
if (prog == NULL || string == NULL) {
696
rep_regerror("NULL parameter");
697
return (0);
698
}
699
/* Check validity of program. */
700
if (UCHARAT(prog->program) != MAGIC) {
701
rep_regerror("corrupted program");
702
return (0);
703
}
704
705
/* jsh -- Check for REG_NOCASE, means ignore case in string matches. */
706
regnocase = ((eflags & rep_REG_NOCASE) != 0);
707
708
/* If there is a "must appear" string, look for it. */
709
if (prog->regmust != NULL)
710
{
711
s = string;
712
if(regnocase)
713
{
714
mat[0] = tolower(UCHARAT(prog->regmust));
715
mat[1] = toupper(UCHARAT(prog->regmust));
716
while ((s = strpbrk(s, mat)) != NULL)
717
{
718
if(strncasecmp(s, prog->regmust, prog->regmlen) == 0)
719
break; /* Found it. */
720
s++;
721
}
722
}
723
else
724
{
725
while ((s = strchr(s, prog->regmust[0])) != NULL)
726
{
727
if(strncmp(s, prog->regmust, prog->regmlen) == 0)
728
break; /* Found it. */
729
s++;
730
}
731
}
732
if (s == NULL) /* Not present. */
733
return (0);
734
}
735
/* Mark beginning of line for ^ . */
736
/* jsh -- if REG_NOTBOL is set then set regbol to something absurd
737
to guarantee ^ doesn't match */
738
regbol = (eflags & rep_REG_NOTBOL) ? "" : string;
739
740
/* Simplest case: anchored match need be tried only once. */
741
if (prog->reganch)
742
return (regtry(prog, string));
743
744
/* Messy cases: unanchored match. */
745
s = string;
746
if (prog->regstart != '\0')
747
{
748
/* We know what char it must start with. */
749
if(regnocase)
750
{
751
mat[0] = tolower(prog->regstart);
752
mat[1] = toupper(prog->regstart);
753
while((s = strpbrk(s, mat)) != NULL)
754
{
755
if(regtry(prog, s))
756
return (1);
757
s++;
758
}
759
}
760
else
761
{
762
while((s = strchr(s, prog->regstart)) != NULL)
763
{
764
if(regtry(prog, s))
765
return (1);
766
s++;
767
}
768
}
769
}
770
else
771
/* We don't -- general case. */
772
do {
773
if (regtry(prog, s))
774
return (1);
775
} while (*s++ != '\0');
776
777
/* Failure. */
778
return (0);
779
}
780
781
/*
782
* - regmatch_string - match a regexp against the string STRING.
783
* No searching
784
*/
785
int
786
rep_regmatch_string(rep_regexp *prog, char *string, int eflags)
787
{
788
/* Check for REG_NOCASE, means ignore case in string matches. */
789
regnocase = ((eflags & rep_REG_NOCASE) != 0);
790
791
/* Mark beginning of line for ^ . */
792
/* jsh -- if REG_NOTBOL is set then set regbol to something absurd
793
to guarantee ^ doesn't match */
794
regbol = (eflags & rep_REG_NOTBOL) ? "" : string;
795
796
return regtry(prog, string);
797
}
798
799
/*
800
* - regtry - try match at specific point
801
*/
802
static int /* 0 failure, 1 success */
803
regtry(rep_regexp *prog, char *string)
804
{
805
register int i;
806
register char **sp;
807
register char **ep;
808
809
reginput = string;
810
regstartp = prog->matches.string.startp;
811
regendp = prog->matches.string.endp;
812
regnest = 0;
813
814
sp = prog->matches.string.startp;
815
ep = prog->matches.string.endp;
816
for (i = rep_NSUBEXP; i > 0; i--) {
817
*sp++ = NULL;
818
*ep++ = NULL;
819
}
820
if (regmatch(prog->program + 1)) {
821
regstartp[0] = string;
822
regendp[0] = reginput;
823
prog->lasttype = rep_reg_string;
824
return (1);
825
} else
826
return (0);
827
}
828
829
/* get around the insane number of return statements in regmatch () */
830
static inline int
831
nested_regmatch (char *prog)
832
{
833
int ret;
834
regnest++;
835
ret = regmatch (prog);
836
regnest--;
837
return ret;
838
}
839
840
/*
841
* - regmatch - main matching routine
842
*
843
* Conceptually the strategy is simple: check to see whether the current node
844
* matches, call self recursively to see whether the rest matches, and then
845
* act accordingly. In practice we make some effort to avoid recursion, in
846
* particular by going through "ordinary" nodes (that don't need to know
847
* whether the rest of the match failed) by a loop instead of by recursion.
848
*/
849
static int /* 0 failure, 1 success */
850
regmatch(char *prog)
851
{
852
register char *scan; /* Current node. */
853
char *next; /* Next node. */
854
855
if (regnest >= rep_regexp_max_depth)
856
{
857
/* recursion overload, bail out */
858
rep_regerror ("stack overflow");
859
return 0;
860
}
861
862
scan = prog;
863
#ifdef DEBUG
864
if (scan != NULL && regnarrate)
865
fprintf(stderr, "%s(\n", regprop(scan));
866
#endif
867
while (scan != NULL) {
868
#ifdef DEBUG
869
if (regnarrate)
870
fprintf(stderr, "%s...\n", regprop(scan));
871
#endif
872
next = regnext(scan);
873
874
switch (OP(scan)) {
875
case BOL:
876
if (reginput != regbol)
877
return (0);
878
break;
879
case EOL:
880
if (*reginput != '\0')
881
return (0);
882
break;
883
case ANY:
884
if (*reginput == '\0')
885
return (0);
886
reginput++;
887
break;
888
case EXACTLY:{
889
register int len;
890
register char *opnd;
891
opnd = OPERAND(scan);
892
if(regnocase)
893
{
894
/* Inline the first character, for speed. */
895
if(toupper(UCHARAT(opnd)) != toupper(UCHARAT(reginput)))
896
return (0);
897
len = strlen(opnd);
898
if(len > 1 && strncasecmp(opnd, reginput, len) != 0)
899
return (0);
900
}
901
else
902
{
903
/* Inline the first character, for speed. */
904
if(*opnd != *reginput)
905
return (0);
906
len = strlen(opnd);
907
if(len > 1 && strncmp(opnd, reginput, len) != 0)
908
return (0);
909
}
910
reginput += len;
911
}
912
break;
913
case ANYOF:
914
if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
915
return (0);
916
reginput++;
917
break;
918
case ANYBUT:
919
if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
920
return (0);
921
reginput++;
922
break;
923
case NOTHING:
924
break;
925
case BACK:
926
break;
927
case OPEN + 1:
928
case OPEN + 2:
929
case OPEN + 3:
930
case OPEN + 4:
931
case OPEN + 5:
932
case OPEN + 6:
933
case OPEN + 7:
934
case OPEN + 8:
935
case OPEN + 9:{
936
register int no;
937
register char *save;
938
939
no = OP(scan) - OPEN;
940
save = reginput;
941
942
if (nested_regmatch(next)) {
943
/*
944
* Don't set startp if some later invocation of the same
945
* parentheses already has.
946
*/
947
if (regstartp[no] == NULL)
948
regstartp[no] = save;
949
return (1);
950
} else
951
return (0);
952
}
953
break;
954
case CLOSE + 1:
955
case CLOSE + 2:
956
case CLOSE + 3:
957
case CLOSE + 4:
958
case CLOSE + 5:
959
case CLOSE + 6:
960
case CLOSE + 7:
961
case CLOSE + 8:
962
case CLOSE + 9:{
963
register int no;
964
register char *save;
965
966
no = OP(scan) - CLOSE;
967
save = reginput;
968
969
if (nested_regmatch(next)) {
970
/*
971
* Don't set endp if some later invocation of the same
972
* parentheses already has.
973
*/
974
if (regendp[no] == NULL)
975
regendp[no] = save;
976
return (1);
977
} else
978
return (0);
979
}
980
break;
981
case BRANCH:{
982
register char *save;
983
984
if (OP(next) != BRANCH) /* No choice. */
985
next = OPERAND(scan); /* Avoid recursion. */
986
else {
987
do {
988
save = reginput;
989
if (nested_regmatch(OPERAND(scan)))
990
return (1);
991
reginput = save;
992
scan = regnext(scan);
993
} while (scan != NULL && OP(scan) == BRANCH);
994
return (0);
995
/* NOTREACHED */
996
}
997
}
998
break;
999
case STAR:
1000
case PLUS:{
1001
register u_char nextch;
1002
register int no;
1003
register char *save;
1004
register int min;
1005
1006
/*
1007
* Lookahead to avoid useless match attempts when we know
1008
* what character comes next.
1009
*/
1010
nextch = '\0';
1011
if (OP(next) == EXACTLY)
1012
nextch = UCHARAT(OPERAND(next));
1013
if(regnocase)
1014
nextch = toupper(nextch);
1015
min = (OP(scan) == STAR) ? 0 : 1;
1016
save = reginput;
1017
no = regrepeat(OPERAND(scan));
1018
while (no >= min) {
1019
/* If it could work, try it. */
1020
if (nextch == '\0'
1021
|| (regnocase ? toupper(UCHARAT(reginput))
1022
: *reginput) == nextch)
1023
if (nested_regmatch(next))
1024
return (1);
1025
/* Couldn't or didn't -- back up. */
1026
no--;
1027
reginput = save + no;
1028
}
1029
return (0);
1030
}
1031
break;
1032
case NGSTAR:
1033
case NGPLUS:{
1034
register u_char nextch;
1035
register int no;
1036
register char *save;
1037
register int max;
1038
1039
/*
1040
* Lookahead to avoid useless match attempts when we know
1041
* what character comes next.
1042
*/
1043
nextch = '\0';
1044
if (OP(next) == EXACTLY)
1045
nextch = UCHARAT(OPERAND(next));
1046
if(regnocase)
1047
nextch = toupper(nextch);
1048
no = (OP(scan) == NGSTAR) ? 0 : 1;
1049
save = reginput;
1050
max = regrepeat(OPERAND(scan));
1051
while (no <= max) {
1052
reginput = save + no;
1053
/* If it could work, try it. */
1054
if (nextch == '\0'
1055
|| (regnocase ? toupper(UCHARAT(reginput))
1056
: *reginput) == nextch)
1057
if (nested_regmatch(next))
1058
return (1);
1059
/* Couldn't or didn't -- move up. */
1060
no++;
1061
}
1062
return (0);
1063
}
1064
break;
1065
case WORD:
1066
if (*reginput != '_' && !isalnum (UCHARAT(reginput)))
1067
return 0;
1068
reginput++;
1069
break;
1070
case NWORD:
1071
if (*reginput == '_' || isalnum (UCHARAT(reginput)))
1072
return 0;
1073
reginput++;
1074
break;
1075
case WSPC:
1076
if (!isspace (UCHARAT(reginput)))
1077
return 0;
1078
reginput++;
1079
break;
1080
case NWSPC:
1081
if (isspace (UCHARAT(reginput)))
1082
return 0;
1083
reginput++;
1084
break;
1085
case DIGI:
1086
if (!isdigit (UCHARAT(reginput)))
1087
return 0;
1088
reginput++;
1089
break;
1090
case NDIGI:
1091
if (isdigit (UCHARAT(reginput)))
1092
return 0;
1093
reginput++;
1094
break;
1095
case WEDGE:
1096
if (reginput == regbol || *reginput == '\0'
1097
|| ((reginput[-1] == '_' || isalnum (UCHARAT(reginput - 1)))
1098
&& (*reginput != '_' && !isalnum (UCHARAT(reginput))))
1099
|| ((reginput[-1] != '_' && !isalnum (UCHARAT(reginput - 1)))
1100
&& (*reginput == '_' || isalnum (UCHARAT(reginput)))))
1101
break;
1102
return 0;
1103
case NWEDGE:
1104
if (!(reginput == regbol || *reginput == '\0'
1105
|| ((reginput[-1] == '_' || isalnum (UCHARAT(reginput - 1)))
1106
&& (*reginput != '_' && !isalnum (UCHARAT(reginput))))
1107
|| ((reginput[-1] != '_' && !isalnum (UCHARAT(reginput - 1)))
1108
&& (*reginput == '_' || isalnum (UCHARAT(reginput))))))
1109
break;
1110
return 0;
1111
case END:
1112
return (1); /* Success! */
1113
break;
1114
default:
1115
rep_regerror("memory corruption");
1116
return (0);
1117
break;
1118
}
1119
1120
scan = next;
1121
}
1122
1123
/*
1124
* We get here only if there's trouble -- normally "case END" is the
1125
* terminating point.
1126
*/
1127
rep_regerror("corrupted pointers");
1128
return (0);
1129
}
1130
1131
/*
1132
* - regrepeat - repeatedly match something simple, report how many
1133
*/
1134
static int
1135
regrepeat(char *p)
1136
{
1137
int count;
1138
register char *scan;
1139
register char *opnd;
1140
1141
scan = reginput;
1142
opnd = OPERAND(p);
1143
switch (OP(p)) {
1144
case ANY:
1145
scan += strlen(scan);
1146
break;
1147
case EXACTLY:
1148
if(regnocase)
1149
{
1150
while(toupper(UCHARAT(opnd)) == toupper(UCHARAT(scan))) {
1151
scan++;
1152
}
1153
}
1154
else
1155
{
1156
while(*opnd == *scan) {
1157
scan++;
1158
}
1159
}
1160
break;
1161
case ANYOF:
1162
while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
1163
scan++;
1164
}
1165
break;
1166
case ANYBUT:
1167
while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
1168
scan++;
1169
}
1170
break;
1171
case WORD:
1172
while (*scan != '\0' && (*scan == '_' || isalnum (UCHARAT(scan)))) {
1173
scan++;
1174
}
1175
break;
1176
case NWORD:
1177
while (*scan != '\0' && (*scan != '_' && !isalnum (UCHARAT(scan)))) {
1178
scan++;
1179
}
1180
break;
1181
case WSPC:
1182
while (*scan != '\0' && isspace (UCHARAT(scan))) {
1183
scan++;
1184
}
1185
break;
1186
case NWSPC:
1187
while (*scan != '\0' && !isspace (UCHARAT(scan))) {
1188
scan++;
1189
}
1190
break;
1191
case DIGI:
1192
while (*scan != '\0' && isdigit (UCHARAT(scan))) {
1193
scan++;
1194
}
1195
break;
1196
case NDIGI:
1197
while (*scan != '\0' && !isdigit (UCHARAT(scan))) {
1198
scan++;
1199
}
1200
break;
1201
default: /* Oh dear. Called inappropriately. */
1202
rep_regerror("internal foulup");
1203
return 0; /* Best compromise. */
1204
break;
1205
}
1206
1207
count = scan - reginput;
1208
reginput = scan;
1209
1210
return count;
1211
}
1212
1213
/*
1214
* - regnext - dig the "next" pointer out of a node
1215
*/
1216
static char *
1217
regnext(char *p)
1218
{
1219
register int offset;
1220
1221
if (p == ®dummy)
1222
return (NULL);
1223
1224
offset = NEXT(p);
1225
if (offset == 0)
1226
return (NULL);
1227
1228
if (OP(p) == BACK)
1229
return (p - offset);
1230
else
1231
return (p + offset);
1232
}
1233
1234
#ifdef DEBUG
1235
1236
char *regprop();
1237
1238
/*
1239
* - regdump - dump a regexp onto stdout in vaguely comprehensible form
1240
*/
1241
void
1242
regdump(rep_regexp *r)
1243
{
1244
register char *s;
1245
register char op = EXACTLY; /* Arbitrary non-END op. */
1246
register char *next;
1247
1248
1249
s = r->program + 1;
1250
while (op != END) { /* While that wasn't END last time... */
1251
op = OP(s);
1252
printf("\t%4d%s", s - r->program, regprop(s)); /* Where, what. */
1253
next = regnext(s);
1254
if (next == NULL) /* Next ptr. */
1255
printf("(0)");
1256
else
1257
printf("(%d)", (s - r->program) + (next - s));
1258
s += 3;
1259
if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
1260
/* Literal string, where present. */
1261
while (*s != '\0') {
1262
putchar(*s);
1263
s++;
1264
}
1265
s++;
1266
}
1267
putchar('\n');
1268
}
1269
1270
/* Header fields of interest. */
1271
if (r->regstart != '\0')
1272
printf("start `%c' ", r->regstart);
1273
if (r->reganch)
1274
printf("anchored ");
1275
if (r->regmust != NULL)
1276
printf("must have \"%s\"", r->regmust);
1277
printf("\n");
1278
}
1279
1280
/*
1281
* - regprop - printable representation of opcode
1282
*/
1283
char *
1284
regprop(char *op)
1285
{
1286
register char *p;
1287
static char buf[50];
1288
1289
(void) strcpy(buf, ":");
1290
1291
switch (OP(op)) {
1292
case BOL:
1293
p = "BOL";
1294
break;
1295
case EOL:
1296
p = "EOL";
1297
break;
1298
case ANY:
1299
p = "ANY";
1300
break;
1301
case ANYOF:
1302
p = "ANYOF";
1303
break;
1304
case ANYBUT:
1305
p = "ANYBUT";
1306
break;
1307
case BRANCH:
1308
p = "BRANCH";
1309
break;
1310
case EXACTLY:
1311
p = "EXACTLY";
1312
break;
1313
case NOTHING:
1314
p = "NOTHING";
1315
break;
1316
case BACK:
1317
p = "BACK";
1318
break;
1319
case END:
1320
p = "END";
1321
break;
1322
case OPEN + 1:
1323
case OPEN + 2:
1324
case OPEN + 3:
1325
case OPEN + 4:
1326
case OPEN + 5:
1327
case OPEN + 6:
1328
case OPEN + 7:
1329
case OPEN + 8:
1330
case OPEN + 9:
1331
sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
1332
p = NULL;
1333
break;
1334
case CLOSE + 1:
1335
case CLOSE + 2:
1336
case CLOSE + 3:
1337
case CLOSE + 4:
1338
case CLOSE + 5:
1339
case CLOSE + 6:
1340
case CLOSE + 7:
1341
case CLOSE + 8:
1342
case CLOSE + 9:
1343
sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
1344
p = NULL;
1345
break;
1346
case STAR:
1347
p = "STAR";
1348
break;
1349
case PLUS:
1350
p = "PLUS";
1351
break;
1352
case WORD:
1353
p = "WORD";
1354
break;
1355
case NWORD:
1356
p = "NWORD";
1357
break;
1358
case WSPC:
1359
p = "WSPC";
1360
break;
1361
case NWSPC:
1362
p = "NWSPC";
1363
break;
1364
case DIGI:
1365
p = "DIGI";
1366
break;
1367
case NDIGI:
1368
p = "NDIGI";
1369
break;
1370
case WEDGE:
1371
p = "WEDGE";
1372
break;
1373
case NWEDGE:
1374
p = "NWEDGE";
1375
break;
1376
case NGSTAR:
1377
p = "NGSTAR";
1378
break;
1379
case NGPLUS:
1380
p = "NGPLUS";
1381
break;
1382
default:
1383
rep_regerror("corrupted opcode");
1384
p = 0;
1385
break;
1386
}
1387
if (p != NULL)
1388
(void) strcat(buf, p);
1389
return (buf);
1390
}
1391
#endif
1392
1393
/*
1394
* The following is provided for those people who do not have strcspn() in
1395
* their C libraries. They should get off their butts and do something about
1396
* it; at least one public-domain implementation of those (highly useful)
1397
* string routines has been published on Usenet.
1398
*/
1399
#ifndef HAVE_STRCSPN
1400
/*
1401
* strcspn - find length of initial segment of s1 consisting entirely of
1402
* characters not from s2
1403
*/
1404
int
1405
strcspn(char *s1, char *s2)
1406
{
1407
register char *scan1;
1408
register char *scan2;
1409
register int count;
1410
1411
count = 0;
1412
for (scan1 = s1; *scan1 != '\0'; scan1++) {
1413
for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */
1414
if (*scan1 == *scan2++)
1415
return (count);
1416
count++;
1417
}
1418
return (count);
1419
}
1420
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1