← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to regex/regcomp.c

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
regex/regcomp.c
 
1
#include <my_global.h>
 
2
#include <m_string.h>
 
3
#include <m_ctype.h>
 
4
#ifdef __WIN__
 
5
#include  <limits.h>
 
6
#endif
 
7
 
 
8
#include "my_regex.h"
 
9
#include "utils.h"
 
10
#include "regex2.h"
 
11
 
 
12
#include "cclass.h"
 
13
#include "cname.h"
 
14
 
 
15
/*
 
16
 * parse structure, passed up and down to avoid global variables and
 
17
 * other clumsinesses
 
18
 */
 
19
struct parse {
 
20
        char *next;             /* next character in RE */
 
21
        char *end;              /* end of string (-> NUL normally) */
 
22
        int error;              /* has an error been seen? */
 
23
        sop *strip;             /* malloced strip */
 
24
        sopno ssize;            /* malloced strip size (allocated) */
 
25
        sopno slen;             /* malloced strip length (used) */
 
26
        int ncsalloc;           /* number of csets allocated */
 
27
        struct re_guts *g;
 
28
#       define  NPAREN  10      /* we need to remember () 1-9 for back refs */
 
29
        sopno pbegin[NPAREN];   /* -> ( ([0] unused) */
 
30
        sopno pend[NPAREN];     /* -> ) ([0] unused) */
 
31
        CHARSET_INFO *charset;  /* for ctype things  */
 
32
};
 
33
 
 
34
#include "regcomp.ih"
 
35
 
 
36
static char nuls[10];           /* place to point scanner in event of error */
 
37
 
 
38
struct cclass cclasses[CCLASS_LAST+1]= {
 
39
  { "alnum",    "","", _MY_U | _MY_L | _MY_NMR},
 
40
  { "alpha",    "","", _MY_U | _MY_L },
 
41
  { "blank",    "","", _MY_B },
 
42
  { "cntrl",    "","", _MY_CTR },
 
43
  { "digit",    "","", _MY_NMR },
 
44
  { "graph",    "","", _MY_PNT | _MY_U | _MY_L | _MY_NMR},
 
45
  { "lower",    "","", _MY_L },
 
46
  { "print",    "","", _MY_PNT | _MY_U | _MY_L | _MY_NMR | _MY_B },
 
47
  { "punct",    "","", _MY_PNT },
 
48
  { "space",    "","", _MY_SPC },
 
49
  { "upper",    "","", _MY_U },
 
50
  { "xdigit",   "","", _MY_X },
 
51
  { NULL,NULL,NULL, 0 }
 
52
};
 
53
 
 
54
/*
 
55
 * macros for use with parse structure
 
56
 * BEWARE:  these know that the parse structure is named `p' !!!
 
57
 */
 
58
#define PEEK()  (*p->next)
 
59
#define PEEK2() (*(p->next+1))
 
60
#define MORE()  (p->next < p->end)
 
61
#define MORE2() (p->next+1 < p->end)
 
62
#define SEE(c)  (MORE() && PEEK() == (c))
 
63
#define SEETWO(a, b)    (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
 
64
#define EAT(c)  ((SEE(c)) ? (NEXT(), 1) : 0)
 
65
#define EATTWO(a, b)    ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
 
66
#define NEXT()  (p->next++)
 
67
#define NEXT2() (p->next += 2)
 
68
#define NEXTn(n)        (p->next += (n))
 
69
#define GETNEXT()       (*p->next++)
 
70
#define SETERROR(e)     seterr(p, (e))
 
71
#define REQUIRE(co, e)  ((co) || SETERROR(e))
 
72
#define MUSTSEE(c, e)   (REQUIRE(MORE() && PEEK() == (c), e))
 
73
#define MUSTEAT(c, e)   (REQUIRE(MORE() && GETNEXT() == (c), e))
 
74
#define MUSTNOTSEE(c, e)        (REQUIRE(!MORE() || PEEK() != (c), e))
 
75
#define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
 
76
#define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
 
77
#define AHEAD(pos)              dofwd(p, pos, HERE()-(pos))
 
78
#define ASTERN(sop, pos)        EMIT(sop, HERE()-pos)
 
79
#define HERE()          (p->slen)
 
80
#define THERE()         (p->slen - 1)
 
81
#define THERETHERE()    (p->slen - 2)
 
82
#define DROP(n) (p->slen -= (n))
 
83
 
 
84
#ifndef NDEBUG
 
85
static int never = 0;           /* for use in asserts; shuts lint up */
 
86
#else
 
87
#define never   0               /* some <assert.h>s have bugs too */
 
88
#endif
 
89
 
 
90
/*
 
91
 - regcomp - interface for parser and compilation
 
92
 = extern int regcomp(regex_t *, const char *, int);
 
93
 = #define      REG_BASIC       0000
 
94
 = #define      REG_EXTENDED    0001
 
95
 = #define      REG_ICASE       0002
 
96
 = #define      REG_NOSUB       0004
 
97
 = #define      REG_NEWLINE     0010
 
98
 = #define      REG_NOSPEC      0020
 
99
 = #define      REG_PEND        0040
 
100
 = #define      REG_DUMP        0200
 
101
 */
 
102
int                             /* 0 success, otherwise REG_something */
 
103
my_regcomp(preg, pattern, cflags, charset)
 
104
my_regex_t *preg;
 
105
const char *pattern;
 
106
int cflags;
 
107
CHARSET_INFO *charset;
 
108
{
 
109
        struct parse pa;
 
110
        register struct re_guts *g;
 
111
        register struct parse *p = &pa;
 
112
        register int i;
 
113
        register size_t len;
 
114
#ifdef REDEBUG
 
115
#       define  GOODFLAGS(f)    (f)
 
116
#else
 
117
#       define  GOODFLAGS(f)    ((f)&~REG_DUMP)
 
118
#endif
 
119
 
 
120
        my_regex_init(charset); /* Init cclass if neaded */
 
121
        preg->charset=charset;
 
122
        cflags = GOODFLAGS(cflags);
 
123
        if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
 
124
                return(REG_INVARG);
 
125
 
 
126
        if (cflags&REG_PEND) {
 
127
                if (preg->re_endp < pattern)
 
128
                        return(REG_INVARG);
 
129
                len = preg->re_endp - pattern;
 
130
        } else
 
131
                len = strlen((char *)pattern);
 
132
 
 
133
        /* do the mallocs early so failure handling is easy */
 
134
        g = (struct re_guts *)malloc(sizeof(struct re_guts) +
 
135
                                                        (NC-1)*sizeof(cat_t));
 
136
        if (g == NULL)
 
137
                return(REG_ESPACE);
 
138
        p->ssize = (long) (len/(size_t)2*(size_t)3 + (size_t)1); /* ugh */
 
139
        p->strip = (sop *)malloc(p->ssize * sizeof(sop));
 
140
        p->slen = 0;
 
141
        if (p->strip == NULL) {
 
142
                free((char *)g);
 
143
                return(REG_ESPACE);
 
144
        }
 
145
 
 
146
        /* set things up */
 
147
        p->g = g;
 
148
        p->next = (char *)pattern;      /* convenience; we do not modify it */
 
149
        p->end = p->next + len;
 
150
        p->error = 0;
 
151
        p->ncsalloc = 0;
 
152
        p->charset = preg->charset;
 
153
        for (i = 0; i < NPAREN; i++) {
 
154
                p->pbegin[i] = 0;
 
155
                p->pend[i] = 0;
 
156
        }
 
157
        g->csetsize = NC;
 
158
        g->sets = NULL;
 
159
        g->setbits = NULL;
 
160
        g->ncsets = 0;
 
161
        g->cflags = cflags;
 
162
        g->iflags = 0;
 
163
        g->nbol = 0;
 
164
        g->neol = 0;
 
165
        g->must = NULL;
 
166
        g->mlen = 0;
 
167
        g->nsub = 0;
 
168
        g->ncategories = 1;     /* category 0 is "everything else" */
 
169
        g->categories = &g->catspace[-(CHAR_MIN)];
 
170
        (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
 
171
        g->backrefs = 0;
 
172
 
 
173
        /* do it */
 
174
        EMIT(OEND, 0);
 
175
        g->firststate = THERE();
 
176
        if (cflags&REG_EXTENDED)
 
177
                p_ere(p, OUT);
 
178
        else if (cflags&REG_NOSPEC)
 
179
                p_str(p);
 
180
        else
 
181
                p_bre(p, OUT, OUT);
 
182
        EMIT(OEND, 0);
 
183
        g->laststate = THERE();
 
184
 
 
185
        /* tidy up loose ends and fill things in */
 
186
        categorize(p, g);
 
187
        stripsnug(p, g);
 
188
        findmust(p, g);
 
189
        g->nplus = pluscount(p, g);
 
190
        g->magic = MAGIC2;
 
191
        preg->re_nsub = g->nsub;
 
192
        preg->re_g = g;
 
193
        preg->re_magic = MAGIC1;
 
194
#ifndef REDEBUG
 
195
        /* not debugging, so can't rely on the assert() in regexec() */
 
196
        if (g->iflags&BAD)
 
197
                SETERROR(REG_ASSERT);
 
198
#endif
 
199
 
 
200
        /* win or lose, we're done */
 
201
        if (p->error != 0)      /* lose */
 
202
                my_regfree(preg);
 
203
        return(p->error);
 
204
}
 
205
 
 
206
/*
 
207
 - p_ere - ERE parser top level, concatenation and alternation
 
208
 == static void p_ere(register struct parse *p, int stop);
 
209
 */
 
210
static void
 
211
p_ere(p, stop)
 
212
register struct parse *p;
 
213
int stop;                       /* character this ERE should end at */
 
214
{
 
215
        register char c;
 
216
        register sopno UNINIT_VAR(prevback);
 
217
        register sopno UNINIT_VAR(prevfwd);
 
218
        register sopno conc;
 
219
        register int first = 1;         /* is this the first alternative? */
 
220
 
 
221
        for (;;) {
 
222
                /* do a bunch of concatenated expressions */
 
223
                conc = HERE();
 
224
                while (MORE() && (c = PEEK()) != '|' && c != stop)
 
225
                        p_ere_exp(p);
 
226
                if(REQUIRE(HERE() != conc, REG_EMPTY)) {}/* require nonempty */
 
227
 
 
228
                if (!EAT('|'))
 
229
                        break;          /* NOTE BREAK OUT */
 
230
 
 
231
                if (first) {
 
232
                        INSERT(OCH_, conc);     /* offset is wrong */
 
233
                        prevfwd = conc;
 
234
                        prevback = conc;
 
235
                        first = 0;
 
236
                }
 
237
                ASTERN(OOR1, prevback);
 
238
                prevback = THERE();
 
239
                AHEAD(prevfwd);                 /* fix previous offset */
 
240
                prevfwd = HERE();
 
241
                EMIT(OOR2, 0);                  /* offset is very wrong */
 
242
        }
 
243
 
 
244
        if (!first) {           /* tail-end fixups */
 
245
                AHEAD(prevfwd);
 
246
                ASTERN(O_CH, prevback);
 
247
        }
 
248
 
 
249
        assert(!MORE() || SEE(stop));
 
250
}
 
251
 
 
252
/*
 
253
 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
 
254
 == static void p_ere_exp(register struct parse *p);
 
255
 */
 
256
static void
 
257
p_ere_exp(p)
 
258
register struct parse *p;
 
259
{
 
260
        register char c;
 
261
        register sopno pos;
 
262
        register int count;
 
263
        register int count2;
 
264
        register sopno subno;
 
265
        int wascaret = 0;
 
266
 
 
267
        assert(MORE());         /* caller should have ensured this */
 
268
        c = GETNEXT();
 
269
 
 
270
        pos = HERE();
 
271
        switch (c) {
 
272
        case '(':
 
273
                if(REQUIRE(MORE(), REG_EPAREN)) {}
 
274
                p->g->nsub++;
 
275
                subno = (sopno) p->g->nsub;
 
276
                if (subno < NPAREN)
 
277
                        p->pbegin[subno] = HERE();
 
278
                EMIT(OLPAREN, subno);
 
279
                if (!SEE(')'))
 
280
                        p_ere(p, ')');
 
281
                if (subno < NPAREN) {
 
282
                        p->pend[subno] = HERE();
 
283
                        assert(p->pend[subno] != 0);
 
284
                }
 
285
                EMIT(ORPAREN, subno);
 
286
                if(MUSTEAT(')', REG_EPAREN)) {}
 
287
                break;
 
288
#ifndef POSIX_MISTAKE
 
289
        case ')':               /* happens only if no current unmatched ( */
 
290
                /*
 
291
                 * You may ask, why the ifndef?  Because I didn't notice
 
292
                 * this until slightly too late for 1003.2, and none of the
 
293
                 * other 1003.2 regular-expression reviewers noticed it at
 
294
                 * all.  So an unmatched ) is legal POSIX, at least until
 
295
                 * we can get it fixed.
 
296
                 */
 
297
                SETERROR(REG_EPAREN);
 
298
                break;
 
299
#endif
 
300
        case '^':
 
301
                EMIT(OBOL, 0);
 
302
                p->g->iflags |= USEBOL;
 
303
                p->g->nbol++;
 
304
                wascaret = 1;
 
305
                break;
 
306
        case '$':
 
307
                EMIT(OEOL, 0);
 
308
                p->g->iflags |= USEEOL;
 
309
                p->g->neol++;
 
310
                break;
 
311
        case '|':
 
312
                SETERROR(REG_EMPTY);
 
313
                break;
 
314
        case '*':
 
315
        case '+':
 
316
        case '?':
 
317
                SETERROR(REG_BADRPT);
 
318
                break;
 
319
        case '.':
 
320
                if (p->g->cflags&REG_NEWLINE)
 
321
                        nonnewline(p);
 
322
                else
 
323
                        EMIT(OANY, 0);
 
324
                break;
 
325
        case '[':
 
326
                p_bracket(p);
 
327
                break;
 
328
        case '\\':
 
329
                if(REQUIRE(MORE(), REG_EESCAPE)) {}
 
330
                c = GETNEXT();
 
331
                ordinary(p, c);
 
332
                break;
 
333
        case '{':               /* okay as ordinary except if digit follows */
 
334
                if(REQUIRE(!MORE() || !my_isdigit(p->charset,PEEK()), REG_BADRPT)) {}
 
335
                /* FALLTHROUGH */
 
336
        default:
 
337
                ordinary(p, c);
 
338
                break;
 
339
        }
 
340
 
 
341
        if (!MORE())
 
342
                return;
 
343
        c = PEEK();
 
344
        /* we call { a repetition if followed by a digit */
 
345
        if (!( c == '*' || c == '+' || c == '?' ||
 
346
                                (c == '{' && MORE2() && 
 
347
                                 my_isdigit(p->charset,PEEK2())) ))
 
348
                return;         /* no repetition, we're done */
 
349
        NEXT();
 
350
 
 
351
        if(REQUIRE(!wascaret, REG_BADRPT)) {}
 
352
        switch (c) {
 
353
        case '*':       /* implemented as +? */
 
354
                /* this case does not require the (y|) trick, noKLUDGE */
 
355
                INSERT(OPLUS_, pos);
 
356
                ASTERN(O_PLUS, pos);
 
357
                INSERT(OQUEST_, pos);
 
358
                ASTERN(O_QUEST, pos);
 
359
                break;
 
360
        case '+':
 
361
                INSERT(OPLUS_, pos);
 
362
                ASTERN(O_PLUS, pos);
 
363
                break;
 
364
        case '?':
 
365
                /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
 
366
                INSERT(OCH_, pos);              /* offset slightly wrong */
 
367
                ASTERN(OOR1, pos);              /* this one's right */
 
368
                AHEAD(pos);                     /* fix the OCH_ */
 
369
                EMIT(OOR2, 0);                  /* offset very wrong... */
 
370
                AHEAD(THERE());                 /* ...so fix it */
 
371
                ASTERN(O_CH, THERETHERE());
 
372
                break;
 
373
        case '{':
 
374
                count = p_count(p);
 
375
                if (EAT(',')) {
 
376
                        if (my_isdigit(p->charset,PEEK())) {
 
377
                                count2 = p_count(p);
 
378
                                if(REQUIRE(count <= count2, REG_BADBR)) {}
 
379
                        } else          /* single number with comma */
 
380
                                count2 = RE_INFINITY;
 
381
                } else          /* just a single number */
 
382
                        count2 = count;
 
383
                repeat(p, pos, count, count2);
 
384
                if (!EAT('}')) {        /* error heuristics */
 
385
                        while (MORE() && PEEK() != '}')
 
386
                                NEXT();
 
387
                        if(REQUIRE(MORE(), REG_EBRACE)) {}
 
388
                        SETERROR(REG_BADBR);
 
389
                }
 
390
                break;
 
391
        }
 
392
 
 
393
        if (!MORE())
 
394
                return;
 
395
        c = PEEK();
 
396
        if (!( c == '*' || c == '+' || c == '?' ||
 
397
                                (c == '{' && MORE2() && 
 
398
                                 my_isdigit(p->charset,PEEK2())) ) )
 
399
                return;
 
400
        SETERROR(REG_BADRPT);
 
401
}
 
402
 
 
403
/*
 
404
 - p_str - string (no metacharacters) "parser"
 
405
 == static void p_str(register struct parse *p);
 
406
 */
 
407
static void
 
408
p_str(p)
 
409
register struct parse *p;
 
410
{
 
411
        if(REQUIRE(MORE(), REG_EMPTY)) {}
 
412
        while (MORE())
 
413
                ordinary(p, GETNEXT());
 
414
}
 
415
 
 
416
/*
 
417
 - p_bre - BRE parser top level, anchoring and concatenation
 
418
 == static void p_bre(register struct parse *p, register int end1, \
 
419
 ==     register int end2);
 
420
 * Giving end1 as OUT essentially eliminates the end1/end2 check.
 
421
 *
 
422
 * This implementation is a bit of a kludge, in that a trailing $ is first
 
423
 * taken as an ordinary character and then revised to be an anchor.  The
 
424
 * only undesirable side effect is that '$' gets included as a character
 
425
 * category in such cases.  This is fairly harmless; not worth fixing.
 
426
 * The amount of lookahead needed to avoid this kludge is excessive.
 
427
 */
 
428
static void
 
429
p_bre(p, end1, end2)
 
430
register struct parse *p;
 
431
register int end1;              /* first terminating character */
 
432
register int end2;              /* second terminating character */
 
433
{
 
434
        register sopno start = HERE();
 
435
        register int first = 1;                 /* first subexpression? */
 
436
        register int wasdollar = 0;
 
437
 
 
438
        if (EAT('^')) {
 
439
                EMIT(OBOL, 0);
 
440
                p->g->iflags |= USEBOL;
 
441
                p->g->nbol++;
 
442
        }
 
443
        while (MORE() && !SEETWO(end1, end2)) {
 
444
                wasdollar = p_simp_re(p, first);
 
445
                first = 0;
 
446
        }
 
447
        if (wasdollar) {        /* oops, that was a trailing anchor */
 
448
                DROP(1);
 
449
                EMIT(OEOL, 0);
 
450
                p->g->iflags |= USEEOL;
 
451
                p->g->neol++;
 
452
        }
 
453
 
 
454
        if(REQUIRE(HERE() != start, REG_EMPTY)) {}      /* require nonempty */
 
455
}
 
456
 
 
457
/*
 
458
 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
 
459
 == static int p_simp_re(register struct parse *p, int starordinary);
 
460
 */
 
461
static int                      /* was the simple RE an unbackslashed $? */
 
462
p_simp_re(p, starordinary)
 
463
register struct parse *p;
 
464
int starordinary;               /* is a leading * an ordinary character? */
 
465
{
 
466
        register int c;
 
467
        register int count;
 
468
        register int count2;
 
469
        register sopno pos;
 
470
        register int i;
 
471
        register sopno subno;
 
472
#       define  BACKSL  (1<<CHAR_BIT)
 
473
 
 
474
        pos = HERE();           /* repetion op, if any, covers from here */
 
475
 
 
476
        assert(MORE());         /* caller should have ensured this */
 
477
        c = GETNEXT();
 
478
        if (c == '\\') {
 
479
                if(REQUIRE(MORE(), REG_EESCAPE)) {}
 
480
                c = BACKSL | (unsigned char)GETNEXT();
 
481
        }
 
482
        switch (c) {
 
483
        case '.':
 
484
                if (p->g->cflags&REG_NEWLINE)
 
485
                        nonnewline(p);
 
486
                else
 
487
                        EMIT(OANY, 0);
 
488
                break;
 
489
        case '[':
 
490
                p_bracket(p);
 
491
                break;
 
492
        case BACKSL|'{':
 
493
                SETERROR(REG_BADRPT);
 
494
                break;
 
495
        case BACKSL|'(':
 
496
                p->g->nsub++;
 
497
                subno = (sopno) p->g->nsub;
 
498
                if (subno < NPAREN)
 
499
                        p->pbegin[subno] = HERE();
 
500
                EMIT(OLPAREN, subno);
 
501
                /* the MORE here is an error heuristic */
 
502
                if (MORE() && !SEETWO('\\', ')'))
 
503
                        p_bre(p, '\\', ')');
 
504
                if (subno < NPAREN) {
 
505
                        p->pend[subno] = HERE();
 
506
                        assert(p->pend[subno] != 0);
 
507
                }
 
508
                EMIT(ORPAREN, subno);
 
509
                if(REQUIRE(EATTWO('\\', ')'), REG_EPAREN)) {}
 
510
                break;
 
511
        case BACKSL|')':        /* should not get here -- must be user */
 
512
        case BACKSL|'}':
 
513
                SETERROR(REG_EPAREN);
 
514
                break;
 
515
        case BACKSL|'1':
 
516
        case BACKSL|'2':
 
517
        case BACKSL|'3':
 
518
        case BACKSL|'4':
 
519
        case BACKSL|'5':
 
520
        case BACKSL|'6':
 
521
        case BACKSL|'7':
 
522
        case BACKSL|'8':
 
523
        case BACKSL|'9':
 
524
                i = (c&~BACKSL) - '0';
 
525
                assert(i < NPAREN);
 
526
                if (p->pend[i] != 0) {
 
527
                        assert((uint) i <= p->g->nsub);
 
528
                        EMIT(OBACK_, i);
 
529
                        assert(p->pbegin[i] != 0);
 
530
                        assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
 
531
                        assert(OP(p->strip[p->pend[i]]) == ORPAREN);
 
532
                        (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
 
533
                        EMIT(O_BACK, i);
 
534
                } else
 
535
                        SETERROR(REG_ESUBREG);
 
536
                p->g->backrefs = 1;
 
537
                break;
 
538
        case '*':
 
539
                if(REQUIRE(starordinary, REG_BADRPT)) {}
 
540
                /* FALLTHROUGH */
 
541
        default:
 
542
                ordinary(p, c &~ BACKSL);
 
543
                break;
 
544
        }
 
545
 
 
546
        if (EAT('*')) {         /* implemented as +? */
 
547
                /* this case does not require the (y|) trick, noKLUDGE */
 
548
                INSERT(OPLUS_, pos);
 
549
                ASTERN(O_PLUS, pos);
 
550
                INSERT(OQUEST_, pos);
 
551
                ASTERN(O_QUEST, pos);
 
552
        } else if (EATTWO('\\', '{')) {
 
553
                count = p_count(p);
 
554
                if (EAT(',')) {
 
555
                        if (MORE() && my_isdigit(p->charset,PEEK())) {
 
556
                                count2 = p_count(p);
 
557
                                if(REQUIRE(count <= count2, REG_BADBR)) {}
 
558
                        } else          /* single number with comma */
 
559
                                count2 = RE_INFINITY;
 
560
                } else          /* just a single number */
 
561
                        count2 = count;
 
562
                repeat(p, pos, count, count2);
 
563
                if (!EATTWO('\\', '}')) {       /* error heuristics */
 
564
                        while (MORE() && !SEETWO('\\', '}'))
 
565
                                NEXT();
 
566
                        if(REQUIRE(MORE(), REG_EBRACE)) {}
 
567
                        SETERROR(REG_BADBR);
 
568
                }
 
569
        } else if (c == (unsigned char)'$')     /* $ (but not \$) ends it */
 
570
                return(1);
 
571
 
 
572
        return(0);
 
573
}
 
574
 
 
575
/*
 
576
 - p_count - parse a repetition count
 
577
 == static int p_count(register struct parse *p);
 
578
 */
 
579
static int                      /* the value */
 
580
p_count(p)
 
581
register struct parse *p;
 
582
{
 
583
        register int count = 0;
 
584
        register int ndigits = 0;
 
585
 
 
586
        while (MORE() && my_isdigit(p->charset,PEEK()) && count <= DUPMAX) {
 
587
                count = count*10 + (GETNEXT() - '0');
 
588
                ndigits++;
 
589
        }
 
590
 
 
591
        if(REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR)) {}
 
592
        return(count);
 
593
}
 
594
 
 
595
/*
 
596
 - p_bracket - parse a bracketed character list
 
597
 == static void p_bracket(register struct parse *p);
 
598
 *
 
599
 * Note a significant property of this code:  if the allocset() did SETERROR,
 
600
 * no set operations are done.
 
601
 */
 
602
static void
 
603
p_bracket(p)
 
604
register struct parse *p;
 
605
{
 
606
        register cset *cs = allocset(p);
 
607
        register int invert = 0;
 
608
 
 
609
        /* Dept of Truly Sickening Special-Case Kludges */
 
610
        if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
 
611
                EMIT(OBOW, 0);
 
612
                NEXTn(6);
 
613
                return;
 
614
        }
 
615
        if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
 
616
                EMIT(OEOW, 0);
 
617
                NEXTn(6);
 
618
                return;
 
619
        }
 
620
 
 
621
        if (EAT('^'))
 
622
                invert++;       /* make note to invert set at end */
 
623
        if (EAT(']'))
 
624
                CHadd(cs, ']');
 
625
        else if (EAT('-'))
 
626
                CHadd(cs, '-');
 
627
        while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
 
628
                p_b_term(p, cs);
 
629
        if (EAT('-'))
 
630
                CHadd(cs, '-');
 
631
        if(MUSTEAT(']', REG_EBRACK)) {}
 
632
 
 
633
        if (p->error != 0)      /* don't mess things up further */
 
634
                return;
 
635
 
 
636
        if (p->g->cflags&REG_ICASE) {
 
637
                register int i;
 
638
                register int ci;
 
639
 
 
640
                for (i = p->g->csetsize - 1; i >= 0; i--)
 
641
                        if (CHIN(cs, i) && my_isalpha(p->charset,i)) {
 
642
                                ci = othercase(p->charset,i);
 
643
                                if (ci != i)
 
644
                                        CHadd(cs, ci);
 
645
                        }
 
646
                if (cs->multis != NULL)
 
647
                        mccase(p, cs);
 
648
        }
 
649
        if (invert) {
 
650
                register int i;
 
651
 
 
652
                for (i = p->g->csetsize - 1; i >= 0; i--)
 
653
                        if (CHIN(cs, i))
 
654
                                CHsub(cs, i);
 
655
                        else
 
656
                                CHadd(cs, i);
 
657
                if (p->g->cflags&REG_NEWLINE)
 
658
                        CHsub(cs, '\n');
 
659
                if (cs->multis != NULL)
 
660
                        mcinvert(p, cs);
 
661
        }
 
662
 
 
663
        assert(cs->multis == NULL);             /* xxx */
 
664
 
 
665
        if (nch(p, cs) == 1) {          /* optimize singleton sets */
 
666
                ordinary(p, firstch(p, cs));
 
667
                freeset(p, cs);
 
668
        } else
 
669
                EMIT(OANYOF, freezeset(p, cs));
 
670
}
 
671
 
 
672
/*
 
673
 - p_b_term - parse one term of a bracketed character list
 
674
 == static void p_b_term(register struct parse *p, register cset *cs);
 
675
 */
 
676
static void
 
677
p_b_term(p, cs)
 
678
register struct parse *p;
 
679
register cset *cs;
 
680
{
 
681
        register char c;
 
682
        register char start, finish;
 
683
        register int i;
 
684
 
 
685
        /* classify what we've got */
 
686
        switch ((MORE()) ? PEEK() : '\0') {
 
687
        case '[':
 
688
                c = (MORE2()) ? PEEK2() : '\0';
 
689
                break;
 
690
        case '-':
 
691
                SETERROR(REG_ERANGE);
 
692
                return;                 /* NOTE RETURN */
 
693
                break;
 
694
        default:
 
695
                c = '\0';
 
696
                break;
 
697
        }
 
698
 
 
699
        switch (c) {
 
700
        case ':':               /* character class */
 
701
                NEXT2();
 
702
                if(REQUIRE(MORE(), REG_EBRACK)) {}
 
703
                c = PEEK();
 
704
                if(REQUIRE(c != '-' && c != ']', REG_ECTYPE)) {}
 
705
                p_b_cclass(p, cs);
 
706
                if(REQUIRE(MORE(), REG_EBRACK)) {}
 
707
                if(REQUIRE(EATTWO(':', ']'), REG_ECTYPE)) {}
 
708
                break;
 
709
        case '=':               /* equivalence class */
 
710
                NEXT2();
 
711
                if(REQUIRE(MORE(), REG_EBRACK)) {}
 
712
                c = PEEK();
 
713
                if(REQUIRE(c != '-' && c != ']', REG_ECOLLATE)) {}
 
714
                p_b_eclass(p, cs);
 
715
                if(REQUIRE(MORE(), REG_EBRACK)) {}
 
716
                if(REQUIRE(EATTWO('=', ']'), REG_ECOLLATE)) {}
 
717
                break;
 
718
        default:                /* symbol, ordinary character, or range */
 
719
/* xxx revision needed for multichar stuff */
 
720
                start = p_b_symbol(p);
 
721
                if (SEE('-') && MORE2() && PEEK2() != ']') {
 
722
                        /* range */
 
723
                        NEXT();
 
724
                        if (EAT('-'))
 
725
                                finish = '-';
 
726
                        else
 
727
                                finish = p_b_symbol(p);
 
728
                } else
 
729
                        finish = start;
 
730
/* xxx what about signed chars here... */
 
731
                if(REQUIRE(start <= finish, REG_ERANGE)) {}
 
732
                for (i = start; i <= finish; i++)
 
733
                        CHadd(cs, i);
 
734
                break;
 
735
        }
 
736
}
 
737
 
 
738
/*
 
739
 - p_b_cclass - parse a character-class name and deal with it
 
740
 == static void p_b_cclass(register struct parse *p, register cset *cs);
 
741
 */
 
742
static void
 
743
p_b_cclass(p, cs)
 
744
register struct parse *p;
 
745
register cset *cs;
 
746
{
 
747
        register char *sp = p->next;
 
748
        register struct cclass *cp;
 
749
        register size_t len;
 
750
        
 
751
        while (MORE() && my_isalpha(p->charset,PEEK()))
 
752
                NEXT();
 
753
        len = p->next - sp;
 
754
        for (cp = cclasses; cp->name != NULL; cp++)
 
755
                if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
 
756
                        break;
 
757
        if (cp->name == NULL) {
 
758
                /* oops, didn't find it */
 
759
                SETERROR(REG_ECTYPE);
 
760
                return;
 
761
        }
 
762
 
 
763
#ifndef USE_ORIG_REGEX_CODE
 
764
        {
 
765
                register size_t i;
 
766
                for (i=1 ; i<256 ; i++)
 
767
                        if (p->charset->ctype[i+1] & cp->mask)
 
768
                                CHadd(cs, i);
 
769
        }
 
770
#else   
 
771
        {
 
772
                register char *u = (char*) cp->chars;
 
773
                register char c;
 
774
                
 
775
                while ((c = *u++) != '\0')
 
776
                        CHadd(cs, c);
 
777
                
 
778
                for (u = (char*) cp->multis; *u != '\0'; u += strlen(u) + 1)
 
779
                        MCadd(p, cs, u);
 
780
        }
 
781
#endif
 
782
 
 
783
}
 
784
 
 
785
/*
 
786
 - p_b_eclass - parse an equivalence-class name and deal with it
 
787
 == static void p_b_eclass(register struct parse *p, register cset *cs);
 
788
 *
 
789
 * This implementation is incomplete. xxx
 
790
 */
 
791
static void
 
792
p_b_eclass(p, cs)
 
793
register struct parse *p;
 
794
register cset *cs;
 
795
{
 
796
        register char c;
 
797
 
 
798
        c = p_b_coll_elem(p, '=');
 
799
        CHadd(cs, c);
 
800
}
 
801
 
 
802
/*
 
803
 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
 
804
 == static char p_b_symbol(register struct parse *p);
 
805
 */
 
806
static char                     /* value of symbol */
 
807
p_b_symbol(p)
 
808
register struct parse *p;
 
809
{
 
810
        register char value;
 
811
 
 
812
        if(REQUIRE(MORE(), REG_EBRACK)) {}
 
813
        if (!EATTWO('[', '.'))
 
814
                return(GETNEXT());
 
815
 
 
816
        /* collating symbol */
 
817
        value = p_b_coll_elem(p, '.');
 
818
        if(REQUIRE(EATTWO('.', ']'), REG_ECOLLATE)) {}
 
819
        return(value);
 
820
}
 
821
 
 
822
/*
 
823
 - p_b_coll_elem - parse a collating-element name and look it up
 
824
 == static char p_b_coll_elem(register struct parse *p, int endc);
 
825
 */
 
826
static char                     /* value of collating element */
 
827
p_b_coll_elem(p, endc)
 
828
register struct parse *p;
 
829
int endc;                       /* name ended by endc,']' */
 
830
{
 
831
        register char *sp = p->next;
 
832
        register struct cname *cp;
 
833
#ifdef _WIN64
 
834
        register __int64 len;
 
835
#else
 
836
        register int len;
 
837
#endif
 
838
        while (MORE() && !SEETWO(endc, ']'))
 
839
                NEXT();
 
840
        if (!MORE()) {
 
841
                SETERROR(REG_EBRACK);
 
842
                return(0);
 
843
        }
 
844
        len = p->next - sp;
 
845
        for (cp = cnames; cp->name != NULL; cp++)
 
846
                if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
 
847
                        return(cp->code);       /* known name */
 
848
        if (len == 1)
 
849
                return(*sp);    /* single character */
 
850
        SETERROR(REG_ECOLLATE);                 /* neither */
 
851
        return(0);
 
852
}
 
853
 
 
854
/*
 
855
 - othercase - return the case counterpart of an alphabetic
 
856
 == static char othercase(int ch);
 
857
 */
 
858
static char                     /* if no counterpart, return ch */
 
859
othercase(charset,ch)
 
860
CHARSET_INFO *charset;
 
861
int ch;
 
862
{
 
863
        /*
 
864
          In MySQL some multi-byte character sets
 
865
          have 'ctype' array but don't have 'to_lower'
 
866
          and 'to_upper' arrays. In this case we handle
 
867
          only basic latin letters a..z and A..Z.
 
868
          
 
869
          If 'to_lower' and 'to_upper' arrays are empty in a character set,
 
870
          then my_isalpha(cs, ch) should never return TRUE for characters
 
871
          other than basic latin letters. Otherwise it should be
 
872
          considered as a mistake in character set definition.
 
873
        */
 
874
        assert(my_isalpha(charset,ch));
 
875
        if (my_isupper(charset,ch))
 
876
        {
 
877
                return(charset->to_lower ? my_tolower(charset,ch) :
 
878
                                          ch - 'A' + 'a');
 
879
        }
 
880
        else if (my_islower(charset,ch))
 
881
        {
 
882
                return(charset->to_upper ? my_toupper(charset,ch) :
 
883
                                          ch - 'a' + 'A');
 
884
        }
 
885
        else                    /* peculiar, but could happen */
 
886
                return(ch);
 
887
}
 
888
 
 
889
/*
 
890
 - bothcases - emit a dualcase version of a two-case character
 
891
 == static void bothcases(register struct parse *p, int ch);
 
892
 *
 
893
 * Boy, is this implementation ever a kludge...
 
894
 */
 
895
static void
 
896
bothcases(p, ch)
 
897
register struct parse *p;
 
898
int ch;
 
899
{
 
900
        register char *oldnext = p->next;
 
901
        register char *oldend = p->end;
 
902
        char bracket[3];
 
903
 
 
904
        assert(othercase(p->charset, ch) != ch); /* p_bracket() would recurse */
 
905
        p->next = bracket;
 
906
        p->end = bracket+2;
 
907
        bracket[0] = ch;
 
908
        bracket[1] = ']';
 
909
        bracket[2] = '\0';
 
910
        p_bracket(p);
 
911
        assert(p->next == bracket+2);
 
912
        p->next = oldnext;
 
913
        p->end = oldend;
 
914
}
 
915
 
 
916
/*
 
917
 - ordinary - emit an ordinary character
 
918
 == static void ordinary(register struct parse *p, register int ch);
 
919
 */
 
920
static void
 
921
ordinary(p, ch)
 
922
register struct parse *p;
 
923
register int ch;
 
924
{
 
925
        register cat_t *cap = p->g->categories;
 
926
 
 
927
        if ((p->g->cflags&REG_ICASE) && my_isalpha(p->charset,ch) && 
 
928
             othercase(p->charset,ch) != ch)
 
929
                bothcases(p, ch);
 
930
        else {
 
931
                EMIT(OCHAR, (unsigned char)ch);
 
932
                if (cap[ch] == 0)
 
933
                        cap[ch] = p->g->ncategories++;
 
934
        }
 
935
}
 
936
 
 
937
/*
 
938
 - nonnewline - emit REG_NEWLINE version of OANY
 
939
 == static void nonnewline(register struct parse *p);
 
940
 *
 
941
 * Boy, is this implementation ever a kludge...
 
942
 */
 
943
static void
 
944
nonnewline(p)
 
945
register struct parse *p;
 
946
{
 
947
        register char *oldnext = p->next;
 
948
        register char *oldend = p->end;
 
949
        char bracket[4];
 
950
 
 
951
        p->next = bracket;
 
952
        p->end = bracket+3;
 
953
        bracket[0] = '^';
 
954
        bracket[1] = '\n';
 
955
        bracket[2] = ']';
 
956
        bracket[3] = '\0';
 
957
        p_bracket(p);
 
958
        assert(p->next == bracket+3);
 
959
        p->next = oldnext;
 
960
        p->end = oldend;
 
961
}
 
962
 
 
963
/*
 
964
 - repeat - generate code for a bounded repetition, recursively if needed
 
965
 == static void repeat(register struct parse *p, sopno start, int from, int to);
 
966
 */
 
967
static void
 
968
repeat(p, start, from, to)
 
969
register struct parse *p;
 
970
sopno start;                    /* operand from here to end of strip */
 
971
int from;                       /* repeated from this number */
 
972
int to;                         /* to this number of times (maybe RE_INFINITY) */
 
973
{
 
974
        register sopno finish = HERE();
 
975
#       define  N       2
 
976
#       define  INF     3
 
977
#       define  REP(f, t)       ((f)*8 + (t))
 
978
#       define  MAP(n)  (((n) <= 1) ? (n) : ((n) == RE_INFINITY) ? INF : N)
 
979
        register sopno copy;
 
980
 
 
981
        if (p->error != 0)      /* head off possible runaway recursion */
 
982
                return;
 
983
 
 
984
        assert(from <= to);
 
985
 
 
986
        switch (REP(MAP(from), MAP(to))) {
 
987
        case REP(0, 0):                 /* must be user doing this */
 
988
                DROP(finish-start);     /* drop the operand */
 
989
                break;
 
990
        case REP(0, 1):                 /* as x{1,1}? */
 
991
        case REP(0, N):                 /* as x{1,n}? */
 
992
        case REP(0, INF):               /* as x{1,}? */
 
993
                /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
 
994
                INSERT(OCH_, start);            /* offset is wrong... */
 
995
                repeat(p, start+1, 1, to);
 
996
                ASTERN(OOR1, start);
 
997
                AHEAD(start);                   /* ... fix it */
 
998
                EMIT(OOR2, 0);
 
999
                AHEAD(THERE());
 
1000
                ASTERN(O_CH, THERETHERE());
 
1001
                break;
 
1002
        case REP(1, 1):                 /* trivial case */
 
1003
                /* done */
 
1004
                break;
 
1005
        case REP(1, N):                 /* as x?x{1,n-1} */
 
1006
                /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
 
1007
                INSERT(OCH_, start);
 
1008
                ASTERN(OOR1, start);
 
1009
                AHEAD(start);
 
1010
                EMIT(OOR2, 0);                  /* offset very wrong... */
 
1011
                AHEAD(THERE());                 /* ...so fix it */
 
1012
                ASTERN(O_CH, THERETHERE());
 
1013
                copy = dupl(p, start+1, finish+1);
 
1014
                assert(copy == finish+4);
 
1015
                repeat(p, copy, 1, to-1);
 
1016
                break;
 
1017
        case REP(1, INF):               /* as x+ */
 
1018
                INSERT(OPLUS_, start);
 
1019
                ASTERN(O_PLUS, start);
 
1020
                break;
 
1021
        case REP(N, N):                 /* as xx{m-1,n-1} */
 
1022
                copy = dupl(p, start, finish);
 
1023
                repeat(p, copy, from-1, to-1);
 
1024
                break;
 
1025
        case REP(N, INF):               /* as xx{n-1,INF} */
 
1026
                copy = dupl(p, start, finish);
 
1027
                repeat(p, copy, from-1, to);
 
1028
                break;
 
1029
        default:                        /* "can't happen" */
 
1030
                SETERROR(REG_ASSERT);   /* just in case */
 
1031
                break;
 
1032
        }
 
1033
}
 
1034
 
 
1035
/*
 
1036
 - seterr - set an error condition
 
1037
 == static int seterr(register struct parse *p, int e);
 
1038
 */
 
1039
static int                      /* useless but makes type checking happy */
 
1040
seterr(p, e)
 
1041
register struct parse *p;
 
1042
int e;
 
1043
{
 
1044
        if (p->error == 0)      /* keep earliest error condition */
 
1045
                p->error = e;
 
1046
        p->next = nuls;         /* try to bring things to a halt */
 
1047
        p->end = nuls;
 
1048
        return(0);              /* make the return value well-defined */
 
1049
}
 
1050
 
 
1051
/*
 
1052
 - allocset - allocate a set of characters for []
 
1053
 == static cset *allocset(register struct parse *p);
 
1054
 */
 
1055
static cset *
 
1056
allocset(p)
 
1057
register struct parse *p;
 
1058
{
 
1059
        register int no = p->g->ncsets++;
 
1060
        register size_t nc;
 
1061
        register size_t nbytes;
 
1062
        register cset *cs;
 
1063
        register size_t css = (size_t)p->g->csetsize;
 
1064
        register int i;
 
1065
 
 
1066
        if (no >= p->ncsalloc) {        /* need another column of space */
 
1067
                p->ncsalloc += CHAR_BIT;
 
1068
                nc = p->ncsalloc;
 
1069
                assert(nc % CHAR_BIT == 0);
 
1070
                nbytes = nc / CHAR_BIT * css;
 
1071
                if (p->g->sets == NULL)
 
1072
                        p->g->sets = (cset *)malloc(nc * sizeof(cset));
 
1073
                else
 
1074
                        p->g->sets = (cset *)realloc((char *)p->g->sets,
 
1075
                                                        nc * sizeof(cset));
 
1076
                if (p->g->setbits == NULL)
 
1077
                        p->g->setbits = (uch *)malloc(nbytes);
 
1078
                else {
 
1079
                        p->g->setbits = (uch *)realloc((char *)p->g->setbits,
 
1080
                                                                nbytes);
 
1081
                        /* xxx this isn't right if setbits is now NULL */
 
1082
                        for (i = 0; i < no; i++)
 
1083
                                p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
 
1084
                }
 
1085
                if (p->g->sets != NULL && p->g->setbits != NULL)
 
1086
                        (void) memset((char *)p->g->setbits + (nbytes - css),
 
1087
                                                                0, css);
 
1088
                else {
 
1089
                        no = 0;
 
1090
                        SETERROR(REG_ESPACE);
 
1091
                        /* caller's responsibility not to do set ops */
 
1092
                }
 
1093
        }
 
1094
 
 
1095
        assert(p->g->sets != NULL);     /* xxx */
 
1096
        cs = &p->g->sets[no];
 
1097
        cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
 
1098
        cs->mask = 1 << ((no) % CHAR_BIT);
 
1099
        cs->hash = 0;
 
1100
        cs->smultis = 0;
 
1101
        cs->multis = NULL;
 
1102
 
 
1103
        return(cs);
 
1104
}
 
1105
 
 
1106
/*
 
1107
 - freeset - free a now-unused set
 
1108
 == static void freeset(register struct parse *p, register cset *cs);
 
1109
 */
 
1110
static void
 
1111
freeset(p, cs)
 
1112
register struct parse *p;
 
1113
register cset *cs;
 
1114
{
 
1115
        register size_t i;
 
1116
        register cset *top = &p->g->sets[p->g->ncsets];
 
1117
        register size_t css = (size_t)p->g->csetsize;
 
1118
 
 
1119
        for (i = 0; i < css; i++)
 
1120
          CHsub(cs, i);
 
1121
        if (cs == top-1)        /* recover only the easy case */
 
1122
          p->g->ncsets--;
 
1123
}
 
1124
 
 
1125
/*
 
1126
 - freezeset - final processing on a set of characters
 
1127
 == static int freezeset(register struct parse *p, register cset *cs);
 
1128
 *
 
1129
 * The main task here is merging identical sets.  This is usually a waste
 
1130
 * of time (although the hash code minimizes the overhead), but can win
 
1131
 * big if REG_ICASE is being used.  REG_ICASE, by the way, is why the hash
 
1132
 * is done using addition rather than xor -- all ASCII [aA] sets xor to
 
1133
 * the same value!
 
1134
 */
 
1135
static int                      /* set number */
 
1136
freezeset(p, cs)
 
1137
register struct parse *p;
 
1138
register cset *cs;
 
1139
{
 
1140
        register uch h = cs->hash;
 
1141
        register size_t i;
 
1142
        register cset *top = &p->g->sets[p->g->ncsets];
 
1143
        register cset *cs2;
 
1144
        register size_t css = (size_t)p->g->csetsize;
 
1145
 
 
1146
        /* look for an earlier one which is the same */
 
1147
        for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
 
1148
                if (cs2->hash == h && cs2 != cs) {
 
1149
                        /* maybe */
 
1150
                        for (i = 0; i < css; i++)
 
1151
                                if (!!CHIN(cs2, i) != !!CHIN(cs, i))
 
1152
                                        break;          /* no */
 
1153
                        if (i == css)
 
1154
                                break;                  /* yes */
 
1155
                }
 
1156
 
 
1157
        if (cs2 < top) {        /* found one */
 
1158
                freeset(p, cs);
 
1159
                cs = cs2;
 
1160
        }
 
1161
 
 
1162
        return((int)(cs - p->g->sets));
 
1163
}
 
1164
 
 
1165
/*
 
1166
 - firstch - return first character in a set (which must have at least one)
 
1167
 == static int firstch(register struct parse *p, register cset *cs);
 
1168
 */
 
1169
static int                      /* character; there is no "none" value */
 
1170
firstch(p, cs)
 
1171
register struct parse *p;
 
1172
register cset *cs;
 
1173
{
 
1174
        register size_t i;
 
1175
        register size_t css = (size_t)p->g->csetsize;
 
1176
 
 
1177
        for (i = 0; i < css; i++)
 
1178
                if (CHIN(cs, i))
 
1179
                        return((char)i);
 
1180
        assert(never);
 
1181
        return(0);              /* arbitrary */
 
1182
}
 
1183
 
 
1184
/*
 
1185
 - nch - number of characters in a set
 
1186
 == static int nch(register struct parse *p, register cset *cs);
 
1187
 */
 
1188
static int
 
1189
nch(p, cs)
 
1190
register struct parse *p;
 
1191
register cset *cs;
 
1192
{
 
1193
        register size_t i;
 
1194
        register size_t css = (size_t)p->g->csetsize;
 
1195
        register int n = 0;
 
1196
 
 
1197
        for (i = 0; i < css; i++)
 
1198
                if (CHIN(cs, i))
 
1199
                        n++;
 
1200
        return(n);
 
1201
}
 
1202
 
 
1203
#ifdef USE_ORIG_REGEX_CODE
 
1204
/*
 
1205
 - mcadd - add a collating element to a cset
 
1206
 == static void mcadd(register struct parse *p, register cset *cs, \
 
1207
 ==     register char *cp);
 
1208
 */
 
1209
static void
 
1210
mcadd(p, cs, cp)
 
1211
register struct parse *p;
 
1212
register cset *cs;
 
1213
register char *cp;
 
1214
{
 
1215
        register size_t oldend = cs->smultis;
 
1216
 
 
1217
        cs->smultis += strlen(cp) + 1;
 
1218
        if (cs->multis == NULL)
 
1219
                cs->multis = malloc(cs->smultis);
 
1220
        else
 
1221
                cs->multis = realloc(cs->multis, cs->smultis);
 
1222
        if (cs->multis == NULL) {
 
1223
                SETERROR(REG_ESPACE);
 
1224
                return;
 
1225
        }
 
1226
 
 
1227
        (void) strcpy(cs->multis + oldend - 1, cp);
 
1228
        cs->multis[cs->smultis - 1] = '\0';
 
1229
}
 
1230
#endif
 
1231
 
 
1232
#ifdef NOT_USED
 
1233
/*
 
1234
 - mcsub - subtract a collating element from a cset
 
1235
 == static void mcsub(register cset *cs, register char *cp);
 
1236
 */
 
1237
static void
 
1238
mcsub(cs, cp)
 
1239
register cset *cs;
 
1240
register char *cp;
 
1241
{
 
1242
        register char *fp = mcfind(cs, cp);
 
1243
        register size_t len = strlen(fp);
 
1244
 
 
1245
        assert(fp != NULL);
 
1246
        (void) memmove(fp, fp + len + 1,
 
1247
                                cs->smultis - (fp + len + 1 - cs->multis));
 
1248
        cs->smultis -= len;
 
1249
 
 
1250
        if (cs->smultis == 0) {
 
1251
                free(cs->multis);
 
1252
                cs->multis = NULL;
 
1253
                return;
 
1254
        }
 
1255
 
 
1256
        cs->multis = realloc(cs->multis, cs->smultis);
 
1257
        assert(cs->multis != NULL);
 
1258
}
 
1259
 
 
1260
/*
 
1261
 - mcin - is a collating element in a cset?
 
1262
 == static int mcin(register cset *cs, register char *cp);
 
1263
 */
 
1264
static int
 
1265
mcin(cs, cp)
 
1266
register cset *cs;
 
1267
register char *cp;
 
1268
{
 
1269
        return(mcfind(cs, cp) != NULL);
 
1270
}
 
1271
 
 
1272
/*
 
1273
 - mcfind - find a collating element in a cset
 
1274
 == static char *mcfind(register cset *cs, register char *cp);
 
1275
 */
 
1276
static char *
 
1277
mcfind(cs, cp)
 
1278
register cset *cs;
 
1279
register char *cp;
 
1280
{
 
1281
        register char *p;
 
1282
 
 
1283
        if (cs->multis == NULL)
 
1284
                return(NULL);
 
1285
        for (p = cs->multis; *p != '\0'; p += strlen(p) + 1)
 
1286
                if (strcmp(cp, p) == 0)
 
1287
                        return(p);
 
1288
        return(NULL);
 
1289
}
 
1290
#endif
 
1291
 
 
1292
/*
 
1293
 - mcinvert - invert the list of collating elements in a cset
 
1294
 == static void mcinvert(register struct parse *p, register cset *cs);
 
1295
 *
 
1296
 * This would have to know the set of possibilities.  Implementation
 
1297
 * is deferred.
 
1298
 */
 
1299
static void
 
1300
mcinvert(p, cs)
 
1301
  register struct parse *p __attribute__((unused));
 
1302
  register cset *cs __attribute__((unused));
 
1303
{
 
1304
        assert(cs->multis == NULL);     /* xxx */
 
1305
}
 
1306
 
 
1307
/*
 
1308
 - mccase - add case counterparts of the list of collating elements in a cset
 
1309
 == static void mccase(register struct parse *p, register cset *cs);
 
1310
 *
 
1311
 * This would have to know the set of possibilities.  Implementation
 
1312
 * is deferred.
 
1313
 */
 
1314
static void
 
1315
mccase(p, cs)
 
1316
register struct parse *p __attribute__((unused));
 
1317
register cset *cs __attribute__((unused));
 
1318
{
 
1319
        assert(cs->multis == NULL);     /* xxx */
 
1320
}
 
1321
 
 
1322
/*
 
1323
 - isinsets - is this character in any sets?
 
1324
 == static int isinsets(register struct re_guts *g, int c);
 
1325
 */
 
1326
static int                      /* predicate */
 
1327
isinsets(g, c)
 
1328
register struct re_guts *g;
 
1329
int c;
 
1330
{
 
1331
        register uch *col;
 
1332
        register int i;
 
1333
        register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
 
1334
        register unsigned uc = (unsigned char)c;
 
1335
 
 
1336
        for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
 
1337
                if (col[uc] != 0)
 
1338
                        return(1);
 
1339
        return(0);
 
1340
}
 
1341
 
 
1342
/*
 
1343
 - samesets - are these two characters in exactly the same sets?
 
1344
 == static int samesets(register struct re_guts *g, int c1, int c2);
 
1345
 */
 
1346
static int                      /* predicate */
 
1347
samesets(g, c1, c2)
 
1348
register struct re_guts *g;
 
1349
int c1;
 
1350
int c2;
 
1351
{
 
1352
        register uch *col;
 
1353
        register int i;
 
1354
        register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
 
1355
        register unsigned uc1 = (unsigned char)c1;
 
1356
        register unsigned uc2 = (unsigned char)c2;
 
1357
 
 
1358
        for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
 
1359
                if (col[uc1] != col[uc2])
 
1360
                        return(0);
 
1361
        return(1);
 
1362
}
 
1363
 
 
1364
/*
 
1365
 - categorize - sort out character categories
 
1366
 == static void categorize(struct parse *p, register struct re_guts *g);
 
1367
 */
 
1368
static void
 
1369
categorize(p, g)
 
1370
struct parse *p;
 
1371
register struct re_guts *g;
 
1372
{
 
1373
        register cat_t *cats = g->categories;
 
1374
        register int c;
 
1375
        register int c2;
 
1376
        register cat_t cat;
 
1377
 
 
1378
        /* avoid making error situations worse */
 
1379
        if (p->error != 0)
 
1380
                return;
 
1381
 
 
1382
        for (c = CHAR_MIN; c <= CHAR_MAX; c++)
 
1383
                if (cats[c] == 0 && isinsets(g, c)) {
 
1384
                        cat = g->ncategories++;
 
1385
                        cats[c] = cat;
 
1386
                        for (c2 = c+1; c2 <= CHAR_MAX; c2++)
 
1387
                                if (cats[c2] == 0 && samesets(g, c, c2))
 
1388
                                        cats[c2] = cat;
 
1389
                }
 
1390
}
 
1391
 
 
1392
/*
 
1393
 - dupl - emit a duplicate of a bunch of sops
 
1394
 == static sopno dupl(register struct parse *p, sopno start, sopno finish);
 
1395
 */
 
1396
static sopno                    /* start of duplicate */
 
1397
dupl(p, start, finish)
 
1398
register struct parse *p;
 
1399
sopno start;                    /* from here */
 
1400
sopno finish;                   /* to this less one */
 
1401
{
 
1402
        register sopno ret = HERE();
 
1403
        register sopno len = finish - start;
 
1404
 
 
1405
        assert(finish >= start);
 
1406
        if (len == 0)
 
1407
                return(ret);
 
1408
        enlarge(p, p->ssize + len);     /* this many unexpected additions */
 
1409
        assert(p->ssize >= p->slen + len);
 
1410
        (void) memcpy((char *)(p->strip + p->slen),
 
1411
                (char *)(p->strip + start), (size_t)len*sizeof(sop));
 
1412
        p->slen += len;
 
1413
        return(ret);
 
1414
}
 
1415
 
 
1416
/*
 
1417
 - doemit - emit a strip operator
 
1418
 == static void doemit(register struct parse *p, sop op, size_t opnd);
 
1419
 *
 
1420
 * It might seem better to implement this as a macro with a function as
 
1421
 * hard-case backup, but it's just too big and messy unless there are
 
1422
 * some changes to the data structures.  Maybe later.
 
1423
 */
 
1424
static void
 
1425
doemit(p, op, opnd)
 
1426
register struct parse *p;
 
1427
sop op;
 
1428
size_t opnd;
 
1429
{
 
1430
        /* avoid making error situations worse */
 
1431
        if (p->error != 0)
 
1432
                return;
 
1433
 
 
1434
        /* deal with oversize operands ("can't happen", more or less) */
 
1435
        assert(opnd < 1<<OPSHIFT);
 
1436
 
 
1437
        /* deal with undersized strip */
 
1438
        if (p->slen >= p->ssize)
 
1439
                enlarge(p, (p->ssize+1) / 2 * 3);       /* +50% */
 
1440
        assert(p->slen < p->ssize);
 
1441
 
 
1442
        /* finally, it's all reduced to the easy case */
 
1443
        p->strip[p->slen++] = SOP(op, opnd);
 
1444
}
 
1445
 
 
1446
/*
 
1447
 - doinsert - insert a sop into the strip
 
1448
 == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos);
 
1449
 */
 
1450
static void
 
1451
doinsert(p, op, opnd, pos)
 
1452
register struct parse *p;
 
1453
sop op;
 
1454
size_t opnd;
 
1455
sopno pos;
 
1456
{
 
1457
        register sopno sn;
 
1458
        register sop s;
 
1459
        register int i;
 
1460
 
 
1461
        /* avoid making error situations worse */
 
1462
        if (p->error != 0)
 
1463
                return;
 
1464
 
 
1465
        sn = HERE();
 
1466
        EMIT(op, opnd);         /* do checks, ensure space */
 
1467
        assert(HERE() == sn+1);
 
1468
        s = p->strip[sn];
 
1469
 
 
1470
        /* adjust paren pointers */
 
1471
        assert(pos > 0);
 
1472
        for (i = 1; i < NPAREN; i++) {
 
1473
                if (p->pbegin[i] >= pos) {
 
1474
                        p->pbegin[i]++;
 
1475
                }
 
1476
                if (p->pend[i] >= pos) {
 
1477
                        p->pend[i]++;
 
1478
                }
 
1479
        }
 
1480
        {
 
1481
          int length=(HERE()-pos-1)*sizeof(sop);
 
1482
          bmove_upp((uchar *) &p->strip[pos+1]+length,
 
1483
                    (uchar *) &p->strip[pos]+length,
 
1484
                    length);
 
1485
        }
 
1486
#ifdef OLD_CODE
 
1487
        memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
 
1488
                                                (HERE()-pos-1)*sizeof(sop));
 
1489
#endif
 
1490
        p->strip[pos] = s;
 
1491
}
 
1492
 
 
1493
/*
 
1494
 - dofwd - complete a forward reference
 
1495
 == static void dofwd(register struct parse *p, sopno pos, sop value);
 
1496
 */
 
1497
static void
 
1498
dofwd(p, pos, value)
 
1499
register struct parse *p;
 
1500
register sopno pos;
 
1501
sop value;
 
1502
{
 
1503
        /* avoid making error situations worse */
 
1504
        if (p->error != 0)
 
1505
                return;
 
1506
 
 
1507
        assert(value < 1<<OPSHIFT);
 
1508
        p->strip[pos] = OP(p->strip[pos]) | value;
 
1509
}
 
1510
 
 
1511
/*
 
1512
 - enlarge - enlarge the strip
 
1513
 == static void enlarge(register struct parse *p, sopno size);
 
1514
 */
 
1515
static void
 
1516
enlarge(p, size)
 
1517
register struct parse *p;
 
1518
register sopno size;
 
1519
{
 
1520
        register sop *sp;
 
1521
 
 
1522
        if (p->ssize >= size)
 
1523
                return;
 
1524
 
 
1525
        sp = (sop *)realloc(p->strip, size*sizeof(sop));
 
1526
        if (sp == NULL) {
 
1527
                SETERROR(REG_ESPACE);
 
1528
                return;
 
1529
        }
 
1530
        p->strip = sp;
 
1531
        p->ssize = size;
 
1532
}
 
1533
 
 
1534
/*
 
1535
 - stripsnug - compact the strip
 
1536
 == static void stripsnug(register struct parse *p, register struct re_guts *g);
 
1537
 */
 
1538
static void
 
1539
stripsnug(p, g)
 
1540
register struct parse *p;
 
1541
register struct re_guts *g;
 
1542
{
 
1543
        g->nstates = p->slen;
 
1544
        g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
 
1545
        if (g->strip == NULL) {
 
1546
                SETERROR(REG_ESPACE);
 
1547
                g->strip = p->strip;
 
1548
        }
 
1549
}
 
1550
 
 
1551
/*
 
1552
 - findmust - fill in must and mlen with longest mandatory literal string
 
1553
 == static void findmust(register struct parse *p, register struct re_guts *g);
 
1554
 *
 
1555
 * This algorithm could do fancy things like analyzing the operands of |
 
1556
 * for common subsequences.  Someday.  This code is simple and finds most
 
1557
 * of the interesting cases.
 
1558
 *
 
1559
 * Note that must and mlen got initialized during setup.
 
1560
 */
 
1561
static void
 
1562
findmust(p, g)
 
1563
struct parse *p;
 
1564
register struct re_guts *g;
 
1565
{
 
1566
        register sop *scan;
 
1567
        sop *start;
 
1568
        register sop *newstart;
 
1569
        register sopno newlen;
 
1570
        register sop s;
 
1571
        register char *cp;
 
1572
        register sopno i;
 
1573
        LINT_INIT(start); LINT_INIT(newstart);
 
1574
        /* avoid making error situations worse */
 
1575
        if (p->error != 0)
 
1576
                return;
 
1577
 
 
1578
        /* find the longest OCHAR sequence in strip */
 
1579
        newlen = 0;
 
1580
        scan = g->strip + 1;
 
1581
        do {
 
1582
                s = *scan++;
 
1583
                switch (OP(s)) {
 
1584
                case OCHAR:             /* sequence member */
 
1585
                        if (newlen == 0)                /* new sequence */
 
1586
                                newstart = scan - 1;
 
1587
                        newlen++;
 
1588
                        break;
 
1589
                case OPLUS_:            /* things that don't break one */
 
1590
                case OLPAREN:
 
1591
                case ORPAREN:
 
1592
                        break;
 
1593
                case OQUEST_:           /* things that must be skipped */
 
1594
                case OCH_:
 
1595
                        scan--;
 
1596
                        do {
 
1597
                                scan += OPND(s);
 
1598
                                s = *scan;
 
1599
                                /* assert() interferes w debug printouts */
 
1600
                                if (OP(s) != O_QUEST && OP(s) != O_CH &&
 
1601
                                                        OP(s) != OOR2) {
 
1602
                                        g->iflags |= BAD;
 
1603
                                        return;
 
1604
                                }
 
1605
                        } while (OP(s) != O_QUEST && OP(s) != O_CH);
 
1606
                        /* fallthrough */
 
1607
                default:                /* things that break a sequence */
 
1608
                        if (newlen > g->mlen) {         /* ends one */
 
1609
                                start = newstart;
 
1610
                                g->mlen = newlen;
 
1611
                        }
 
1612
                        newlen = 0;
 
1613
                        break;
 
1614
                }
 
1615
        } while (OP(s) != OEND);
 
1616
 
 
1617
        if (g->mlen == 0)               /* there isn't one */
 
1618
                return;
 
1619
 
 
1620
        /* turn it into a character string */
 
1621
        g->must = malloc((size_t)g->mlen + 1);
 
1622
        if (g->must == NULL) {          /* argh; just forget it */
 
1623
                g->mlen = 0;
 
1624
                return;
 
1625
        }
 
1626
        cp = g->must;
 
1627
        scan = start;
 
1628
        for (i = g->mlen; i > 0; i--) {
 
1629
                while (OP(s = *scan++) != OCHAR)
 
1630
                        continue;
 
1631
                assert(cp < g->must + g->mlen);
 
1632
                *cp++ = (char)OPND(s);
 
1633
        }
 
1634
        assert(cp == g->must + g->mlen);
 
1635
        *cp++ = '\0';           /* just on general principles */
 
1636
}
 
1637
 
 
1638
/*
 
1639
 - pluscount - count + nesting
 
1640
 == static sopno pluscount(register struct parse *p, register struct re_guts *g);
 
1641
 */
 
1642
static sopno                    /* nesting depth */
 
1643
pluscount(p, g)
 
1644
struct parse *p;
 
1645
register struct re_guts *g;
 
1646
{
 
1647
        register sop *scan;
 
1648
        register sop s;
 
1649
        register sopno plusnest = 0;
 
1650
        register sopno maxnest = 0;
 
1651
 
 
1652
        if (p->error != 0)
 
1653
                return(0);      /* there may not be an OEND */
 
1654
 
 
1655
        scan = g->strip + 1;
 
1656
        do {
 
1657
                s = *scan++;
 
1658
                switch (OP(s)) {
 
1659
                case OPLUS_:
 
1660
                        plusnest++;
 
1661
                        break;
 
1662
                case O_PLUS:
 
1663
                        if (plusnest > maxnest)
 
1664
                                maxnest = plusnest;
 
1665
                        plusnest--;
 
1666
                        break;
 
1667
                }
 
1668
        } while (OP(s) != OEND);
 
1669
        if (plusnest != 0)
 
1670
                g->iflags |= BAD;
 
1671
        return(maxnest);
 
1672
}