← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/regex/regexec.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/regex/regexec.c
 
1
/*
 
2
 * re_*exec and friends - match REs
 
3
 *
 
4
 * Copyright (c) 1998, 1999 Henry Spencer.      All rights reserved.
 
5
 *
 
6
 * Development of this software was funded, in part, by Cray Research Inc.,
 
7
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 
8
 * Corporation, none of whom are responsible for the results.  The author
 
9
 * thanks all of them.
 
10
 *
 
11
 * Redistribution and use in source and binary forms -- with or without
 
12
 * modification -- are permitted for any purpose, provided that
 
13
 * redistributions in source form retain this entire copyright notice and
 
14
 * indicate the origin and nature of any modifications.
 
15
 *
 
16
 * I'd appreciate being given credit for this package in the documentation
 
17
 * of software which uses it, but that is not a requirement.
 
18
 *
 
19
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 
20
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 
21
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 
22
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 
23
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 
24
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 
25
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 
26
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 
27
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 
28
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
29
 *
 
30
 * $PostgreSQL: pgsql/src/backend/regex/regexec.c,v 1.24 2003-11-29 19:51:55 pgsql Exp $
 
31
 *
 
32
 */
 
33
 
 
34
#include "regex/regguts.h"
 
35
 
 
36
 
 
37
 
 
38
/* lazy-DFA representation */
 
39
struct arcp
 
40
{                                                               /* "pointer" to an outarc */
 
41
        struct sset *ss;
 
42
        color           co;
 
43
};
 
44
 
 
45
struct sset
 
46
{                                                               /* state set */
 
47
        unsigned   *states;                     /* pointer to bitvector */
 
48
        unsigned        hash;                   /* hash of bitvector */
 
49
#define  HASH(bv, nw)    (((nw) == 1) ? *(bv) : hash(bv, nw))
 
50
#define  HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \
 
51
                memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
 
52
        int                     flags;
 
53
#define  STARTER         01                     /* the initial state set */
 
54
#define  POSTSTATE       02                     /* includes the goal state */
 
55
#define  LOCKED          04                     /* locked in cache */
 
56
#define  NOPROGRESS  010                /* zero-progress state set */
 
57
        struct arcp ins;                        /* chain of inarcs pointing here */
 
58
        chr                *lastseen;           /* last entered on arrival here */
 
59
        struct sset **outs;                     /* outarc vector indexed by color */
 
60
        struct arcp *inchain;           /* chain-pointer vector for outarcs */
 
61
};
 
62
 
 
63
struct dfa
 
64
{
 
65
        int                     nssets;                 /* size of cache */
 
66
        int                     nssused;                /* how many entries occupied yet */
 
67
        int                     nstates;                /* number of states */
 
68
        int                     ncolors;                /* length of outarc and inchain vectors */
 
69
        int                     wordsper;               /* length of state-set bitvectors */
 
70
        struct sset *ssets;                     /* state-set cache */
 
71
        unsigned   *statesarea;         /* bitvector storage */
 
72
        unsigned   *work;                       /* pointer to work area within statesarea */
 
73
        struct sset **outsarea;         /* outarc-vector storage */
 
74
        struct arcp *incarea;           /* inchain storage */
 
75
        struct cnfa *cnfa;
 
76
        struct colormap *cm;
 
77
        chr                *lastpost;           /* location of last cache-flushed success */
 
78
        chr                *lastnopr;           /* location of last cache-flushed
 
79
                                                                 * NOPROGRESS */
 
80
        struct sset *search;            /* replacement-search-pointer memory */
 
81
        int                     cptsmalloced;   /* were the areas individually malloced? */
 
82
        char       *mallocarea;         /* self, or master malloced area, or NULL */
 
83
};
 
84
 
 
85
#define WORK    1                               /* number of work bitvectors needed */
 
86
 
 
87
/* setup for non-malloc allocation for small cases */
 
88
#define FEWSTATES       20                      /* must be less than UBITS */
 
89
#define FEWCOLORS       15
 
90
struct smalldfa
 
91
{
 
92
        struct dfa      dfa;
 
93
        struct sset ssets[FEWSTATES * 2];
 
94
        unsigned        statesarea[FEWSTATES * 2 + WORK];
 
95
        struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS];
 
96
        struct arcp incarea[FEWSTATES * 2 * FEWCOLORS];
 
97
};
 
98
 
 
99
#define DOMALLOC        ((struct smalldfa *)NULL)       /* force malloc */
 
100
 
 
101
 
 
102
 
 
103
/* internal variables, bundled for easy passing around */
 
104
struct vars
 
105
{
 
106
        regex_t    *re;
 
107
        struct guts *g;
 
108
        int                     eflags;                 /* copies of arguments */
 
109
        size_t          nmatch;
 
110
        regmatch_t *pmatch;
 
111
        rm_detail_t *details;
 
112
        chr                *start;                      /* start of string */
 
113
        chr                *stop;                       /* just past end of string */
 
114
        int                     err;                    /* error code if any (0 none) */
 
115
        regoff_t   *mem;                        /* memory vector for backtracking */
 
116
        struct smalldfa dfa1;
 
117
        struct smalldfa dfa2;
 
118
};
 
119
 
 
120
#define VISERR(vv)      ((vv)->err != 0)        /* have we seen an error yet? */
 
121
#define ISERR() VISERR(v)
 
122
#define VERR(vv,e)      (((vv)->err) ? (vv)->err : ((vv)->err = (e)))
 
123
#define ERR(e)  VERR(v, e)              /* record an error */
 
124
#define NOERR() {if (ISERR()) return v->err;}   /* if error seen, return
 
125
                                                                                                 * it */
 
126
#define OFF(p)  ((p) - v->start)
 
127
#define LOFF(p) ((long)OFF(p))
 
128
 
 
129
 
 
130
 
 
131
/*
 
132
 * forward declarations
 
133
 */
 
134
/* === regexec.c === */
 
135
static int      find(struct vars *, struct cnfa *, struct colormap *);
 
136
static int      cfind(struct vars *, struct cnfa *, struct colormap *);
 
137
static int      cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
 
138
static void zapsubs(regmatch_t *, size_t);
 
139
static void zapmem(struct vars *, struct subre *);
 
140
static void subset(struct vars *, struct subre *, chr *, chr *);
 
141
static int      dissect(struct vars *, struct subre *, chr *, chr *);
 
142
static int      condissect(struct vars *, struct subre *, chr *, chr *);
 
143
static int      altdissect(struct vars *, struct subre *, chr *, chr *);
 
144
static int      cdissect(struct vars *, struct subre *, chr *, chr *);
 
145
static int      ccondissect(struct vars *, struct subre *, chr *, chr *);
 
146
static int      crevdissect(struct vars *, struct subre *, chr *, chr *);
 
147
static int      cbrdissect(struct vars *, struct subre *, chr *, chr *);
 
148
static int      caltdissect(struct vars *, struct subre *, chr *, chr *);
 
149
 
 
150
/* === rege_dfa.c === */
 
151
static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
 
152
static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
 
153
static chr *lastcold(struct vars *, struct dfa *);
 
154
static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
 
155
static void freedfa(struct dfa *);
 
156
static unsigned hash(unsigned *, int);
 
157
static struct sset *initialize(struct vars *, struct dfa *, chr *);
 
158
static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *);
 
159
static int      lacon(struct vars *, struct cnfa *, chr *, pcolor);
 
160
static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
 
161
static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
 
162
 
 
163
 
 
164
/*
 
165
 * pg_regexec - match regular expression
 
166
 */
 
167
int
 
168
pg_regexec(regex_t *re,
 
169
                   const chr *string,
 
170
                   size_t len,
 
171
                   rm_detail_t *details,
 
172
                   size_t nmatch,
 
173
                   regmatch_t pmatch[],
 
174
                   int flags)
 
175
{
 
176
        struct vars var;
 
177
        register struct vars *v = &var;
 
178
        int                     st;
 
179
        size_t          n;
 
180
        int                     backref;
 
181
 
 
182
#define  LOCALMAT        20
 
183
        regmatch_t      mat[LOCALMAT];
 
184
 
 
185
#define  LOCALMEM        40
 
186
        regoff_t        mem[LOCALMEM];
 
187
 
 
188
        /* sanity checks */
 
189
        if (re == NULL || string == NULL || re->re_magic != REMAGIC)
 
190
                return REG_INVARG;
 
191
        if (re->re_csize != sizeof(chr))
 
192
                return REG_MIXED;
 
193
 
 
194
        /* setup */
 
195
        v->re = re;
 
196
        v->g = (struct guts *) re->re_guts;
 
197
        if ((v->g->cflags & REG_EXPECT) && details == NULL)
 
198
                return REG_INVARG;
 
199
        if (v->g->info & REG_UIMPOSSIBLE)
 
200
                return REG_NOMATCH;
 
201
        backref = (v->g->info & REG_UBACKREF) ? 1 : 0;
 
202
        v->eflags = flags;
 
203
        if (v->g->cflags & REG_NOSUB)
 
204
                nmatch = 0;                             /* override client */
 
205
        v->nmatch = nmatch;
 
206
        if (backref)
 
207
        {
 
208
                /* need work area */
 
209
                if (v->g->nsub + 1 <= LOCALMAT)
 
210
                        v->pmatch = mat;
 
211
                else
 
212
                        v->pmatch = (regmatch_t *) MALLOC((v->g->nsub + 1) *
 
213
                                                                                          sizeof(regmatch_t));
 
214
                if (v->pmatch == NULL)
 
215
                        return REG_ESPACE;
 
216
                v->nmatch = v->g->nsub + 1;
 
217
        }
 
218
        else
 
219
                v->pmatch = pmatch;
 
220
        v->details = details;
 
221
        v->start = (chr *) string;
 
222
        v->stop = (chr *) string + len;
 
223
        v->err = 0;
 
224
        if (backref)
 
225
        {
 
226
                /* need retry memory */
 
227
                assert(v->g->ntree >= 0);
 
228
                n = (size_t) v->g->ntree;
 
229
                if (n <= LOCALMEM)
 
230
                        v->mem = mem;
 
231
                else
 
232
                        v->mem = (regoff_t *) MALLOC(n * sizeof(regoff_t));
 
233
                if (v->mem == NULL)
 
234
                {
 
235
                        if (v->pmatch != pmatch && v->pmatch != mat)
 
236
                                FREE(v->pmatch);
 
237
                        return REG_ESPACE;
 
238
                }
 
239
        }
 
240
        else
 
241
                v->mem = NULL;
 
242
 
 
243
        /* do it */
 
244
        assert(v->g->tree != NULL);
 
245
        if (backref)
 
246
                st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
 
247
        else
 
248
                st = find(v, &v->g->tree->cnfa, &v->g->cmap);
 
249
 
 
250
        /* copy (portion of) match vector over if necessary */
 
251
        if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0)
 
252
        {
 
253
                zapsubs(pmatch, nmatch);
 
254
                n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
 
255
                memcpy(VS(pmatch), VS(v->pmatch), n * sizeof(regmatch_t));
 
256
        }
 
257
 
 
258
        /* clean up */
 
259
        if (v->pmatch != pmatch && v->pmatch != mat)
 
260
                FREE(v->pmatch);
 
261
        if (v->mem != NULL && v->mem != mem)
 
262
                FREE(v->mem);
 
263
        return st;
 
264
}
 
265
 
 
266
/*
 
267
 * find - find a match for the main NFA (no-complications case)
 
268
 */
 
269
static int
 
270
find(struct vars * v,
 
271
         struct cnfa * cnfa,
 
272
         struct colormap * cm)
 
273
{
 
274
        struct dfa *s;
 
275
        struct dfa *d;
 
276
        chr                *begin;
 
277
        chr                *end = NULL;
 
278
        chr                *cold;
 
279
        chr                *open;                       /* open and close of range of possible
 
280
                                                                 * starts */
 
281
        chr                *close;
 
282
        int                     hitend;
 
283
        int                     shorter = (v->g->tree->flags & SHORTER) ? 1 : 0;
 
284
 
 
285
        /* first, a shot with the search RE */
 
286
        s = newdfa(v, &v->g->search, cm, &v->dfa1);
 
287
        assert(!(ISERR() && s != NULL));
 
288
        NOERR();
 
289
        MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
 
290
        cold = NULL;
 
291
        close = shortest(v, s, v->start, v->start, v->stop, &cold, (int *) NULL);
 
292
        freedfa(s);
 
293
        NOERR();
 
294
        if (v->g->cflags & REG_EXPECT)
 
295
        {
 
296
                assert(v->details != NULL);
 
297
                if (cold != NULL)
 
298
                        v->details->rm_extend.rm_so = OFF(cold);
 
299
                else
 
300
                        v->details->rm_extend.rm_so = OFF(v->stop);
 
301
                v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
 
302
        }
 
303
        if (close == NULL)                      /* not found */
 
304
                return REG_NOMATCH;
 
305
        if (v->nmatch == 0)                     /* found, don't need exact location */
 
306
                return REG_OKAY;
 
307
 
 
308
        /* find starting point and match */
 
309
        assert(cold != NULL);
 
310
        open = cold;
 
311
        cold = NULL;
 
312
        MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
 
313
        d = newdfa(v, cnfa, cm, &v->dfa1);
 
314
        assert(!(ISERR() && d != NULL));
 
315
        NOERR();
 
316
        for (begin = open; begin <= close; begin++)
 
317
        {
 
318
                MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
 
319
                if (shorter)
 
320
                        end = shortest(v, d, begin, begin, v->stop,
 
321
                                                   (chr **) NULL, &hitend);
 
322
                else
 
323
                        end = longest(v, d, begin, v->stop, &hitend);
 
324
                NOERR();
 
325
                if (hitend && cold == NULL)
 
326
                        cold = begin;
 
327
                if (end != NULL)
 
328
                        break;                          /* NOTE BREAK OUT */
 
329
        }
 
330
        assert(end != NULL);            /* search RE succeeded so loop should */
 
331
        freedfa(d);
 
332
 
 
333
        /* and pin down details */
 
334
        assert(v->nmatch > 0);
 
335
        v->pmatch[0].rm_so = OFF(begin);
 
336
        v->pmatch[0].rm_eo = OFF(end);
 
337
        if (v->g->cflags & REG_EXPECT)
 
338
        {
 
339
                if (cold != NULL)
 
340
                        v->details->rm_extend.rm_so = OFF(cold);
 
341
                else
 
342
                        v->details->rm_extend.rm_so = OFF(v->stop);
 
343
                v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
 
344
        }
 
345
        if (v->nmatch == 1)                     /* no need for submatches */
 
346
                return REG_OKAY;
 
347
 
 
348
        /* submatches */
 
349
        zapsubs(v->pmatch, v->nmatch);
 
350
        return dissect(v, v->g->tree, begin, end);
 
351
}
 
352
 
 
353
/*
 
354
 * cfind - find a match for the main NFA (with complications)
 
355
 */
 
356
static int
 
357
cfind(struct vars * v,
 
358
          struct cnfa * cnfa,
 
359
          struct colormap * cm)
 
360
{
 
361
        struct dfa *s;
 
362
        struct dfa *d;
 
363
        chr                *cold;
 
364
        int                     ret;
 
365
 
 
366
        s = newdfa(v, &v->g->search, cm, &v->dfa1);
 
367
        NOERR();
 
368
        d = newdfa(v, cnfa, cm, &v->dfa2);
 
369
        if (ISERR())
 
370
        {
 
371
                assert(d == NULL);
 
372
                freedfa(s);
 
373
                return v->err;
 
374
        }
 
375
 
 
376
        ret = cfindloop(v, cnfa, cm, d, s, &cold);
 
377
 
 
378
        freedfa(d);
 
379
        freedfa(s);
 
380
        NOERR();
 
381
        if (v->g->cflags & REG_EXPECT)
 
382
        {
 
383
                assert(v->details != NULL);
 
384
                if (cold != NULL)
 
385
                        v->details->rm_extend.rm_so = OFF(cold);
 
386
                else
 
387
                        v->details->rm_extend.rm_so = OFF(v->stop);
 
388
                v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
 
389
        }
 
390
        return ret;
 
391
}
 
392
 
 
393
/*
 
394
 * cfindloop - the heart of cfind
 
395
 */
 
396
static int
 
397
cfindloop(struct vars * v,
 
398
                  struct cnfa * cnfa,
 
399
                  struct colormap * cm,
 
400
                  struct dfa * d,
 
401
                  struct dfa * s,
 
402
                  chr **coldp)                  /* where to put coldstart pointer */
 
403
{
 
404
        chr                *begin;
 
405
        chr                *end;
 
406
        chr                *cold;
 
407
        chr                *open;                       /* open and close of range of possible
 
408
                                                                 * starts */
 
409
        chr                *close;
 
410
        chr                *estart;
 
411
        chr                *estop;
 
412
        int                     er;
 
413
        int                     shorter = v->g->tree->flags & SHORTER;
 
414
        int                     hitend;
 
415
 
 
416
        assert(d != NULL && s != NULL);
 
417
        cold = NULL;
 
418
        close = v->start;
 
419
        do
 
420
        {
 
421
                MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
 
422
                close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
 
423
                if (close == NULL)
 
424
                        break;                          /* NOTE BREAK */
 
425
                assert(cold != NULL);
 
426
                open = cold;
 
427
                cold = NULL;
 
428
                MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
 
429
                for (begin = open; begin <= close; begin++)
 
430
                {
 
431
                        MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
 
432
                        estart = begin;
 
433
                        estop = v->stop;
 
434
                        for (;;)
 
435
                        {
 
436
                                if (shorter)
 
437
                                        end = shortest(v, d, begin, estart,
 
438
                                                                   estop, (chr **) NULL, &hitend);
 
439
                                else
 
440
                                        end = longest(v, d, begin, estop,
 
441
                                                                  &hitend);
 
442
                                if (hitend && cold == NULL)
 
443
                                        cold = begin;
 
444
                                if (end == NULL)
 
445
                                        break;          /* NOTE BREAK OUT */
 
446
                                MDEBUG(("tentative end %ld\n", LOFF(end)));
 
447
                                zapsubs(v->pmatch, v->nmatch);
 
448
                                zapmem(v, v->g->tree);
 
449
                                er = cdissect(v, v->g->tree, begin, end);
 
450
                                if (er == REG_OKAY)
 
451
                                {
 
452
                                        if (v->nmatch > 0)
 
453
                                        {
 
454
                                                v->pmatch[0].rm_so = OFF(begin);
 
455
                                                v->pmatch[0].rm_eo = OFF(end);
 
456
                                        }
 
457
                                        *coldp = cold;
 
458
                                        return REG_OKAY;
 
459
                                }
 
460
                                if (er != REG_NOMATCH)
 
461
                                {
 
462
                                        ERR(er);
 
463
                                        return er;
 
464
                                }
 
465
                                if ((shorter) ? end == estop : end == begin)
 
466
                                {
 
467
                                        /* no point in trying again */
 
468
                                        *coldp = cold;
 
469
                                        return REG_NOMATCH;
 
470
                                }
 
471
                                /* go around and try again */
 
472
                                if (shorter)
 
473
                                        estart = end + 1;
 
474
                                else
 
475
                                        estop = end - 1;
 
476
                        }
 
477
                }
 
478
        } while (close < v->stop);
 
479
 
 
480
        *coldp = cold;
 
481
        return REG_NOMATCH;
 
482
}
 
483
 
 
484
/*
 
485
 * zapsubs - initialize the subexpression matches to "no match"
 
486
 */
 
487
static void
 
488
zapsubs(regmatch_t *p,
 
489
                size_t n)
 
490
{
 
491
        size_t          i;
 
492
 
 
493
        for (i = n - 1; i > 0; i--)
 
494
        {
 
495
                p[i].rm_so = -1;
 
496
                p[i].rm_eo = -1;
 
497
        }
 
498
}
 
499
 
 
500
/*
 
501
 * zapmem - initialize the retry memory of a subtree to zeros
 
502
 */
 
503
static void
 
504
zapmem(struct vars * v,
 
505
           struct subre * t)
 
506
{
 
507
        if (t == NULL)
 
508
                return;
 
509
 
 
510
        assert(v->mem != NULL);
 
511
        v->mem[t->retry] = 0;
 
512
        if (t->op == '(')
 
513
        {
 
514
                assert(t->subno > 0);
 
515
                v->pmatch[t->subno].rm_so = -1;
 
516
                v->pmatch[t->subno].rm_eo = -1;
 
517
        }
 
518
 
 
519
        if (t->left != NULL)
 
520
                zapmem(v, t->left);
 
521
        if (t->right != NULL)
 
522
                zapmem(v, t->right);
 
523
}
 
524
 
 
525
/*
 
526
 * subset - set any subexpression relevant to a successful subre
 
527
 */
 
528
static void
 
529
subset(struct vars * v,
 
530
           struct subre * sub,
 
531
           chr *begin,
 
532
           chr *end)
 
533
{
 
534
        int                     n = sub->subno;
 
535
 
 
536
        assert(n > 0);
 
537
        if ((size_t) n >= v->nmatch)
 
538
                return;
 
539
 
 
540
        MDEBUG(("setting %d\n", n));
 
541
        v->pmatch[n].rm_so = OFF(begin);
 
542
        v->pmatch[n].rm_eo = OFF(end);
 
543
}
 
544
 
 
545
/*
 
546
 * dissect - determine subexpression matches (uncomplicated case)
 
547
 */
 
548
static int                                              /* regexec return code */
 
549
dissect(struct vars * v,
 
550
                struct subre * t,
 
551
                chr *begin,                             /* beginning of relevant substring */
 
552
                chr *end)                               /* end of same */
 
553
{
 
554
        assert(t != NULL);
 
555
        MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
 
556
 
 
557
        switch (t->op)
 
558
        {
 
559
                case '=':                               /* terminal node */
 
560
                        assert(t->left == NULL && t->right == NULL);
 
561
                        return REG_OKAY;        /* no action, parent did the work */
 
562
                        break;
 
563
                case '|':                               /* alternation */
 
564
                        assert(t->left != NULL);
 
565
                        return altdissect(v, t, begin, end);
 
566
                        break;
 
567
                case 'b':                               /* back ref -- shouldn't be calling us! */
 
568
                        return REG_ASSERT;
 
569
                        break;
 
570
                case '.':                               /* concatenation */
 
571
                        assert(t->left != NULL && t->right != NULL);
 
572
                        return condissect(v, t, begin, end);
 
573
                        break;
 
574
                case '(':                               /* capturing */
 
575
                        assert(t->left != NULL && t->right == NULL);
 
576
                        assert(t->subno > 0);
 
577
                        subset(v, t, begin, end);
 
578
                        return dissect(v, t->left, begin, end);
 
579
                        break;
 
580
                default:
 
581
                        return REG_ASSERT;
 
582
                        break;
 
583
        }
 
584
}
 
585
 
 
586
/*
 
587
 * condissect - determine concatenation subexpression matches (uncomplicated)
 
588
 */
 
589
static int                                              /* regexec return code */
 
590
condissect(struct vars * v,
 
591
                   struct subre * t,
 
592
                   chr *begin,                  /* beginning of relevant substring */
 
593
                   chr *end)                    /* end of same */
 
594
{
 
595
        struct dfa *d;
 
596
        struct dfa *d2;
 
597
        chr                *mid;
 
598
        int                     i;
 
599
        int                     shorter = (t->left->flags & SHORTER) ? 1 : 0;
 
600
        chr                *stop = (shorter) ? end : begin;
 
601
 
 
602
        assert(t->op == '.');
 
603
        assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
604
        assert(t->right != NULL && t->right->cnfa.nstates > 0);
 
605
 
 
606
        d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
 
607
        NOERR();
 
608
        d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
 
609
        if (ISERR())
 
610
        {
 
611
                assert(d2 == NULL);
 
612
                freedfa(d);
 
613
                return v->err;
 
614
        }
 
615
 
 
616
        /* pick a tentative midpoint */
 
617
        if (shorter)
 
618
                mid = shortest(v, d, begin, begin, end, (chr **) NULL,
 
619
                                           (int *) NULL);
 
620
        else
 
621
                mid = longest(v, d, begin, end, (int *) NULL);
 
622
        if (mid == NULL)
 
623
        {
 
624
                freedfa(d);
 
625
                freedfa(d2);
 
626
                return REG_ASSERT;
 
627
        }
 
628
        MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
629
 
 
630
        /* iterate until satisfaction or failure */
 
631
        while (longest(v, d2, mid, end, (int *) NULL) != end)
 
632
        {
 
633
                /* that midpoint didn't work, find a new one */
 
634
                if (mid == stop)
 
635
                {
 
636
                        /* all possibilities exhausted! */
 
637
                        MDEBUG(("no midpoint!\n"));
 
638
                        freedfa(d);
 
639
                        freedfa(d2);
 
640
                        return REG_ASSERT;
 
641
                }
 
642
                if (shorter)
 
643
                        mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL,
 
644
                                                   (int *) NULL);
 
645
                else
 
646
                        mid = longest(v, d, begin, mid - 1, (int *) NULL);
 
647
                if (mid == NULL)
 
648
                {
 
649
                        /* failed to find a new one! */
 
650
                        MDEBUG(("failed midpoint!\n"));
 
651
                        freedfa(d);
 
652
                        freedfa(d2);
 
653
                        return REG_ASSERT;
 
654
                }
 
655
                MDEBUG(("new midpoint %ld\n", LOFF(mid)));
 
656
        }
 
657
 
 
658
        /* satisfaction */
 
659
        MDEBUG(("successful\n"));
 
660
        freedfa(d);
 
661
        freedfa(d2);
 
662
        i = dissect(v, t->left, begin, mid);
 
663
        if (i != REG_OKAY)
 
664
                return i;
 
665
        return dissect(v, t->right, mid, end);
 
666
}
 
667
 
 
668
/*
 
669
 * altdissect - determine alternative subexpression matches (uncomplicated)
 
670
 */
 
671
static int                                              /* regexec return code */
 
672
altdissect(struct vars * v,
 
673
                   struct subre * t,
 
674
                   chr *begin,                  /* beginning of relevant substring */
 
675
                   chr *end)                    /* end of same */
 
676
{
 
677
        struct dfa *d;
 
678
        int                     i;
 
679
 
 
680
        assert(t != NULL);
 
681
        assert(t->op == '|');
 
682
 
 
683
        for (i = 0; t != NULL; t = t->right, i++)
 
684
        {
 
685
                MDEBUG(("trying %dth\n", i));
 
686
                assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
687
                d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
 
688
                if (ISERR())
 
689
                        return v->err;
 
690
                if (longest(v, d, begin, end, (int *) NULL) == end)
 
691
                {
 
692
                        MDEBUG(("success\n"));
 
693
                        freedfa(d);
 
694
                        return dissect(v, t->left, begin, end);
 
695
                }
 
696
                freedfa(d);
 
697
        }
 
698
        return REG_ASSERT;                      /* none of them matched?!? */
 
699
}
 
700
 
 
701
/*
 
702
 * cdissect - determine subexpression matches (with complications)
 
703
 * The retry memory stores the offset of the trial midpoint from begin,
 
704
 * plus 1 so that 0 uniquely means "clean slate".
 
705
 */
 
706
static int                                              /* regexec return code */
 
707
cdissect(struct vars * v,
 
708
                 struct subre * t,
 
709
                 chr *begin,                    /* beginning of relevant substring */
 
710
                 chr *end)                              /* end of same */
 
711
{
 
712
        int                     er;
 
713
 
 
714
        assert(t != NULL);
 
715
        MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
 
716
 
 
717
        switch (t->op)
 
718
        {
 
719
                case '=':                               /* terminal node */
 
720
                        assert(t->left == NULL && t->right == NULL);
 
721
                        return REG_OKAY;        /* no action, parent did the work */
 
722
                        break;
 
723
                case '|':                               /* alternation */
 
724
                        assert(t->left != NULL);
 
725
                        return caltdissect(v, t, begin, end);
 
726
                        break;
 
727
                case 'b':                               /* back ref -- shouldn't be calling us! */
 
728
                        assert(t->left == NULL && t->right == NULL);
 
729
                        return cbrdissect(v, t, begin, end);
 
730
                        break;
 
731
                case '.':                               /* concatenation */
 
732
                        assert(t->left != NULL && t->right != NULL);
 
733
                        return ccondissect(v, t, begin, end);
 
734
                        break;
 
735
                case '(':                               /* capturing */
 
736
                        assert(t->left != NULL && t->right == NULL);
 
737
                        assert(t->subno > 0);
 
738
                        er = cdissect(v, t->left, begin, end);
 
739
                        if (er == REG_OKAY)
 
740
                                subset(v, t, begin, end);
 
741
                        return er;
 
742
                        break;
 
743
                default:
 
744
                        return REG_ASSERT;
 
745
                        break;
 
746
        }
 
747
}
 
748
 
 
749
/*
 
750
 * ccondissect - concatenation subexpression matches (with complications)
 
751
 * The retry memory stores the offset of the trial midpoint from begin,
 
752
 * plus 1 so that 0 uniquely means "clean slate".
 
753
 */
 
754
static int                                              /* regexec return code */
 
755
ccondissect(struct vars * v,
 
756
                        struct subre * t,
 
757
                        chr *begin,                     /* beginning of relevant substring */
 
758
                        chr *end)                       /* end of same */
 
759
{
 
760
        struct dfa *d;
 
761
        struct dfa *d2;
 
762
        chr                *mid;
 
763
        int                     er;
 
764
 
 
765
        assert(t->op == '.');
 
766
        assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
767
        assert(t->right != NULL && t->right->cnfa.nstates > 0);
 
768
 
 
769
        if (t->left->flags & SHORTER)           /* reverse scan */
 
770
                return crevdissect(v, t, begin, end);
 
771
 
 
772
        d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 
773
        if (ISERR())
 
774
                return v->err;
 
775
        d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
 
776
        if (ISERR())
 
777
        {
 
778
                freedfa(d);
 
779
                return v->err;
 
780
        }
 
781
        MDEBUG(("cconcat %d\n", t->retry));
 
782
 
 
783
        /* pick a tentative midpoint */
 
784
        if (v->mem[t->retry] == 0)
 
785
        {
 
786
                mid = longest(v, d, begin, end, (int *) NULL);
 
787
                if (mid == NULL)
 
788
                {
 
789
                        freedfa(d);
 
790
                        freedfa(d2);
 
791
                        return REG_NOMATCH;
 
792
                }
 
793
                MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
794
                v->mem[t->retry] = (mid - begin) + 1;
 
795
        }
 
796
        else
 
797
        {
 
798
                mid = begin + (v->mem[t->retry] - 1);
 
799
                MDEBUG(("working midpoint %ld\n", LOFF(mid)));
 
800
        }
 
801
 
 
802
        /* iterate until satisfaction or failure */
 
803
        for (;;)
 
804
        {
 
805
                /* try this midpoint on for size */
 
806
                er = cdissect(v, t->left, begin, mid);
 
807
                if (er == REG_OKAY &&
 
808
                        longest(v, d2, mid, end, (int *) NULL) == end &&
 
809
                        (er = cdissect(v, t->right, mid, end)) ==
 
810
                        REG_OKAY)
 
811
                        break;                          /* NOTE BREAK OUT */
 
812
                if (er != REG_OKAY && er != REG_NOMATCH)
 
813
                {
 
814
                        freedfa(d);
 
815
                        freedfa(d2);
 
816
                        return er;
 
817
                }
 
818
 
 
819
                /* that midpoint didn't work, find a new one */
 
820
                if (mid == begin)
 
821
                {
 
822
                        /* all possibilities exhausted */
 
823
                        MDEBUG(("%d no midpoint\n", t->retry));
 
824
                        freedfa(d);
 
825
                        freedfa(d2);
 
826
                        return REG_NOMATCH;
 
827
                }
 
828
                mid = longest(v, d, begin, mid - 1, (int *) NULL);
 
829
                if (mid == NULL)
 
830
                {
 
831
                        /* failed to find a new one */
 
832
                        MDEBUG(("%d failed midpoint\n", t->retry));
 
833
                        freedfa(d);
 
834
                        freedfa(d2);
 
835
                        return REG_NOMATCH;
 
836
                }
 
837
                MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
 
838
                v->mem[t->retry] = (mid - begin) + 1;
 
839
                zapmem(v, t->left);
 
840
                zapmem(v, t->right);
 
841
        }
 
842
 
 
843
        /* satisfaction */
 
844
        MDEBUG(("successful\n"));
 
845
        freedfa(d);
 
846
        freedfa(d2);
 
847
        return REG_OKAY;
 
848
}
 
849
 
 
850
/*
 
851
 * crevdissect - determine backref shortest-first subexpression matches
 
852
 * The retry memory stores the offset of the trial midpoint from begin,
 
853
 * plus 1 so that 0 uniquely means "clean slate".
 
854
 */
 
855
static int                                              /* regexec return code */
 
856
crevdissect(struct vars * v,
 
857
                        struct subre * t,
 
858
                        chr *begin,                     /* beginning of relevant substring */
 
859
                        chr *end)                       /* end of same */
 
860
{
 
861
        struct dfa *d;
 
862
        struct dfa *d2;
 
863
        chr                *mid;
 
864
        int                     er;
 
865
 
 
866
        assert(t->op == '.');
 
867
        assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
868
        assert(t->right != NULL && t->right->cnfa.nstates > 0);
 
869
        assert(t->left->flags & SHORTER);
 
870
 
 
871
        /* concatenation -- need to split the substring between parts */
 
872
        d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 
873
        if (ISERR())
 
874
                return v->err;
 
875
        d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
 
876
        if (ISERR())
 
877
        {
 
878
                freedfa(d);
 
879
                return v->err;
 
880
        }
 
881
        MDEBUG(("crev %d\n", t->retry));
 
882
 
 
883
        /* pick a tentative midpoint */
 
884
        if (v->mem[t->retry] == 0)
 
885
        {
 
886
                mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
 
887
                if (mid == NULL)
 
888
                {
 
889
                        freedfa(d);
 
890
                        freedfa(d2);
 
891
                        return REG_NOMATCH;
 
892
                }
 
893
                MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
894
                v->mem[t->retry] = (mid - begin) + 1;
 
895
        }
 
896
        else
 
897
        {
 
898
                mid = begin + (v->mem[t->retry] - 1);
 
899
                MDEBUG(("working midpoint %ld\n", LOFF(mid)));
 
900
        }
 
901
 
 
902
        /* iterate until satisfaction or failure */
 
903
        for (;;)
 
904
        {
 
905
                /* try this midpoint on for size */
 
906
                er = cdissect(v, t->left, begin, mid);
 
907
                if (er == REG_OKAY &&
 
908
                        longest(v, d2, mid, end, (int *) NULL) == end &&
 
909
                        (er = cdissect(v, t->right, mid, end)) ==
 
910
                        REG_OKAY)
 
911
                        break;                          /* NOTE BREAK OUT */
 
912
                if (er != REG_OKAY && er != REG_NOMATCH)
 
913
                {
 
914
                        freedfa(d);
 
915
                        freedfa(d2);
 
916
                        return er;
 
917
                }
 
918
 
 
919
                /* that midpoint didn't work, find a new one */
 
920
                if (mid == end)
 
921
                {
 
922
                        /* all possibilities exhausted */
 
923
                        MDEBUG(("%d no midpoint\n", t->retry));
 
924
                        freedfa(d);
 
925
                        freedfa(d2);
 
926
                        return REG_NOMATCH;
 
927
                }
 
928
                mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL);
 
929
                if (mid == NULL)
 
930
                {
 
931
                        /* failed to find a new one */
 
932
                        MDEBUG(("%d failed midpoint\n", t->retry));
 
933
                        freedfa(d);
 
934
                        freedfa(d2);
 
935
                        return REG_NOMATCH;
 
936
                }
 
937
                MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
 
938
                v->mem[t->retry] = (mid - begin) + 1;
 
939
                zapmem(v, t->left);
 
940
                zapmem(v, t->right);
 
941
        }
 
942
 
 
943
        /* satisfaction */
 
944
        MDEBUG(("successful\n"));
 
945
        freedfa(d);
 
946
        freedfa(d2);
 
947
        return REG_OKAY;
 
948
}
 
949
 
 
950
/*
 
951
 * cbrdissect - determine backref subexpression matches
 
952
 */
 
953
static int                                              /* regexec return code */
 
954
cbrdissect(struct vars * v,
 
955
                   struct subre * t,
 
956
                   chr *begin,                  /* beginning of relevant substring */
 
957
                   chr *end)                    /* end of same */
 
958
{
 
959
        int                     i;
 
960
        int                     n = t->subno;
 
961
        size_t          len;
 
962
        chr                *paren;
 
963
        chr                *p;
 
964
        chr                *stop;
 
965
        int                     min = t->min;
 
966
        int                     max = t->max;
 
967
 
 
968
        assert(t != NULL);
 
969
        assert(t->op == 'b');
 
970
        assert(n >= 0);
 
971
        assert((size_t) n < v->nmatch);
 
972
 
 
973
        MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
 
974
 
 
975
        if (v->pmatch[n].rm_so == -1)
 
976
                return REG_NOMATCH;
 
977
        paren = v->start + v->pmatch[n].rm_so;
 
978
        len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
 
979
 
 
980
        /* no room to maneuver -- retries are pointless */
 
981
        if (v->mem[t->retry])
 
982
                return REG_NOMATCH;
 
983
        v->mem[t->retry] = 1;
 
984
 
 
985
        /* special-case zero-length string */
 
986
        if (len == 0)
 
987
        {
 
988
                if (begin == end)
 
989
                        return REG_OKAY;
 
990
                return REG_NOMATCH;
 
991
        }
 
992
 
 
993
        /* and too-short string */
 
994
        assert(end >= begin);
 
995
        if ((size_t) (end - begin) < len)
 
996
                return REG_NOMATCH;
 
997
        stop = end - len;
 
998
 
 
999
        /* count occurrences */
 
1000
        i = 0;
 
1001
        for (p = begin; p <= stop && (i < max || max == INFINITY); p += len)
 
1002
        {
 
1003
                if ((*v->g->compare) (paren, p, len) != 0)
 
1004
                        break;
 
1005
                i++;
 
1006
        }
 
1007
        MDEBUG(("cbackref found %d\n", i));
 
1008
 
 
1009
        /* and sort it out */
 
1010
        if (p != end)                           /* didn't consume all of it */
 
1011
                return REG_NOMATCH;
 
1012
        if (min <= i && (i <= max || max == INFINITY))
 
1013
                return REG_OKAY;
 
1014
        return REG_NOMATCH;                     /* out of range */
 
1015
}
 
1016
 
 
1017
/*
 
1018
 * caltdissect - determine alternative subexpression matches (w. complications)
 
1019
 */
 
1020
static int                                              /* regexec return code */
 
1021
caltdissect(struct vars * v,
 
1022
                        struct subre * t,
 
1023
                        chr *begin,                     /* beginning of relevant substring */
 
1024
                        chr *end)                       /* end of same */
 
1025
{
 
1026
        struct dfa *d;
 
1027
        int                     er;
 
1028
 
 
1029
#define  UNTRIED 0                              /* not yet tried at all */
 
1030
#define  TRYING  1                              /* top matched, trying submatches */
 
1031
#define  TRIED   2                              /* top didn't match or submatches
 
1032
                                                                 * exhausted */
 
1033
 
 
1034
        if (t == NULL)
 
1035
                return REG_NOMATCH;
 
1036
        assert(t->op == '|');
 
1037
        if (v->mem[t->retry] == TRIED)
 
1038
                return caltdissect(v, t->right, begin, end);
 
1039
 
 
1040
        MDEBUG(("calt n%d\n", t->retry));
 
1041
        assert(t->left != NULL);
 
1042
 
 
1043
        if (v->mem[t->retry] == UNTRIED)
 
1044
        {
 
1045
                d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 
1046
                if (ISERR())
 
1047
                        return v->err;
 
1048
                if (longest(v, d, begin, end, (int *) NULL) != end)
 
1049
                {
 
1050
                        freedfa(d);
 
1051
                        v->mem[t->retry] = TRIED;
 
1052
                        return caltdissect(v, t->right, begin, end);
 
1053
                }
 
1054
                freedfa(d);
 
1055
                MDEBUG(("calt matched\n"));
 
1056
                v->mem[t->retry] = TRYING;
 
1057
        }
 
1058
 
 
1059
        er = cdissect(v, t->left, begin, end);
 
1060
        if (er != REG_NOMATCH)
 
1061
                return er;
 
1062
 
 
1063
        v->mem[t->retry] = TRIED;
 
1064
        return caltdissect(v, t->right, begin, end);
 
1065
}
 
1066
 
 
1067
 
 
1068
 
 
1069
#include "rege_dfa.c"