← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

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
 * src/backend/regex/regexec.c
 
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 NOPROGRESS */
 
79
        struct sset *search;            /* replacement-search-pointer memory */
 
80
        int                     cptsmalloced;   /* were the areas individually malloced? */
 
81
        char       *mallocarea;         /* self, or master malloced area, or NULL */
 
82
};
 
83
 
 
84
#define WORK    1                               /* number of work bitvectors needed */
 
85
 
 
86
/* setup for non-malloc allocation for small cases */
 
87
#define FEWSTATES       20                      /* must be less than UBITS */
 
88
#define FEWCOLORS       15
 
89
struct smalldfa
 
90
{
 
91
        struct dfa      dfa;
 
92
        struct sset ssets[FEWSTATES * 2];
 
93
        unsigned        statesarea[FEWSTATES * 2 + WORK];
 
94
        struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS];
 
95
        struct arcp incarea[FEWSTATES * 2 * FEWCOLORS];
 
96
};
 
97
 
 
98
#define DOMALLOC        ((struct smalldfa *)NULL)       /* force malloc */
 
99
 
 
100
 
 
101
 
 
102
/* internal variables, bundled for easy passing around */
 
103
struct vars
 
104
{
 
105
        regex_t    *re;
 
106
        struct guts *g;
 
107
        int                     eflags;                 /* copies of arguments */
 
108
        size_t          nmatch;
 
109
        regmatch_t *pmatch;
 
110
        rm_detail_t *details;
 
111
        chr                *start;                      /* start of string */
 
112
        chr                *search_start;       /* search 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 it */
 
125
#define OFF(p)  ((p) - v->start)
 
126
#define LOFF(p) ((long)OFF(p))
 
127
 
 
128
 
 
129
 
 
130
/*
 
131
 * forward declarations
 
132
 */
 
133
/* === regexec.c === */
 
134
static int      find(struct vars *, struct cnfa *, struct colormap *);
 
135
static int      cfind(struct vars *, struct cnfa *, struct colormap *);
 
136
static int      cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
 
137
static void zapsubs(regmatch_t *, size_t);
 
138
static void zapmem(struct vars *, struct subre *);
 
139
static void subset(struct vars *, struct subre *, chr *, chr *);
 
140
static int      dissect(struct vars *, struct subre *, chr *, chr *);
 
141
static int      condissect(struct vars *, struct subre *, chr *, chr *);
 
142
static int      altdissect(struct vars *, struct subre *, chr *, chr *);
 
143
static int      cdissect(struct vars *, struct subre *, chr *, chr *);
 
144
static int      ccaptdissect(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
                   size_t search_start,
 
172
                   rm_detail_t *details,
 
173
                   size_t nmatch,
 
174
                   regmatch_t pmatch[],
 
175
                   int flags)
 
176
{
 
177
        struct vars var;
 
178
        register struct vars *v = &var;
 
179
        int                     st;
 
180
        size_t          n;
 
181
        int                     backref;
 
182
 
 
183
#define  LOCALMAT        20
 
184
        regmatch_t      mat[LOCALMAT];
 
185
 
 
186
#define  LOCALMEM        40
 
187
        regoff_t        mem[LOCALMEM];
 
188
 
 
189
        /* sanity checks */
 
190
        if (re == NULL || string == NULL || re->re_magic != REMAGIC)
 
191
                return REG_INVARG;
 
192
        if (re->re_csize != sizeof(chr))
 
193
                return REG_MIXED;
 
194
 
 
195
        /* Initialize locale-dependent support */
 
196
        pg_set_regex_collation(re->re_collation);
 
197
 
 
198
        /* setup */
 
199
        v->re = re;
 
200
        v->g = (struct guts *) re->re_guts;
 
201
        if ((v->g->cflags & REG_EXPECT) && details == NULL)
 
202
                return REG_INVARG;
 
203
        if (v->g->info & REG_UIMPOSSIBLE)
 
204
                return REG_NOMATCH;
 
205
        backref = (v->g->info & REG_UBACKREF) ? 1 : 0;
 
206
        v->eflags = flags;
 
207
        if (v->g->cflags & REG_NOSUB)
 
208
                nmatch = 0;                             /* override client */
 
209
        v->nmatch = nmatch;
 
210
        if (backref)
 
211
        {
 
212
                /* need work area */
 
213
                if (v->g->nsub + 1 <= LOCALMAT)
 
214
                        v->pmatch = mat;
 
215
                else
 
216
                        v->pmatch = (regmatch_t *) MALLOC((v->g->nsub + 1) *
 
217
                                                                                          sizeof(regmatch_t));
 
218
                if (v->pmatch == NULL)
 
219
                        return REG_ESPACE;
 
220
                v->nmatch = v->g->nsub + 1;
 
221
        }
 
222
        else
 
223
                v->pmatch = pmatch;
 
224
        v->details = details;
 
225
        v->start = (chr *) string;
 
226
        v->search_start = (chr *) string + search_start;
 
227
        v->stop = (chr *) string + len;
 
228
        v->err = 0;
 
229
        if (backref)
 
230
        {
 
231
                /* need retry memory */
 
232
                assert(v->g->ntree >= 0);
 
233
                n = (size_t) v->g->ntree;
 
234
                if (n <= LOCALMEM)
 
235
                        v->mem = mem;
 
236
                else
 
237
                        v->mem = (regoff_t *) MALLOC(n * sizeof(regoff_t));
 
238
                if (v->mem == NULL)
 
239
                {
 
240
                        if (v->pmatch != pmatch && v->pmatch != mat)
 
241
                                FREE(v->pmatch);
 
242
                        return REG_ESPACE;
 
243
                }
 
244
        }
 
245
        else
 
246
                v->mem = NULL;
 
247
 
 
248
        /* do it */
 
249
        assert(v->g->tree != NULL);
 
250
        if (backref)
 
251
                st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
 
252
        else
 
253
                st = find(v, &v->g->tree->cnfa, &v->g->cmap);
 
254
 
 
255
        /* copy (portion of) match vector over if necessary */
 
256
        if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0)
 
257
        {
 
258
                zapsubs(pmatch, nmatch);
 
259
                n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
 
260
                memcpy(VS(pmatch), VS(v->pmatch), n * sizeof(regmatch_t));
 
261
        }
 
262
 
 
263
        /* clean up */
 
264
        if (v->pmatch != pmatch && v->pmatch != mat)
 
265
                FREE(v->pmatch);
 
266
        if (v->mem != NULL && v->mem != mem)
 
267
                FREE(v->mem);
 
268
        return st;
 
269
}
 
270
 
 
271
/*
 
272
 * find - find a match for the main NFA (no-complications case)
 
273
 */
 
274
static int
 
275
find(struct vars * v,
 
276
         struct cnfa * cnfa,
 
277
         struct colormap * cm)
 
278
{
 
279
        struct dfa *s;
 
280
        struct dfa *d;
 
281
        chr                *begin;
 
282
        chr                *end = NULL;
 
283
        chr                *cold;
 
284
        chr                *open;                       /* open and close of range of possible starts */
 
285
        chr                *close;
 
286
        int                     hitend;
 
287
        int                     shorter = (v->g->tree->flags & SHORTER) ? 1 : 0;
 
288
 
 
289
        /* first, a shot with the search RE */
 
290
        s = newdfa(v, &v->g->search, cm, &v->dfa1);
 
291
        assert(!(ISERR() && s != NULL));
 
292
        NOERR();
 
293
        MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
 
294
        cold = NULL;
 
295
        close = shortest(v, s, v->search_start, v->search_start, v->stop,
 
296
                                         &cold, (int *) NULL);
 
297
        freedfa(s);
 
298
        NOERR();
 
299
        if (v->g->cflags & REG_EXPECT)
 
300
        {
 
301
                assert(v->details != NULL);
 
302
                if (cold != NULL)
 
303
                        v->details->rm_extend.rm_so = OFF(cold);
 
304
                else
 
305
                        v->details->rm_extend.rm_so = OFF(v->stop);
 
306
                v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
 
307
        }
 
308
        if (close == NULL)                      /* not found */
 
309
                return REG_NOMATCH;
 
310
        if (v->nmatch == 0)                     /* found, don't need exact location */
 
311
                return REG_OKAY;
 
312
 
 
313
        /* find starting point and match */
 
314
        assert(cold != NULL);
 
315
        open = cold;
 
316
        cold = NULL;
 
317
        MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
 
318
        d = newdfa(v, cnfa, cm, &v->dfa1);
 
319
        assert(!(ISERR() && d != NULL));
 
320
        NOERR();
 
321
        for (begin = open; begin <= close; begin++)
 
322
        {
 
323
                MDEBUG(("\nfind trying at %ld\n", LOFF(begin)));
 
324
                if (shorter)
 
325
                        end = shortest(v, d, begin, begin, v->stop,
 
326
                                                   (chr **) NULL, &hitend);
 
327
                else
 
328
                        end = longest(v, d, begin, v->stop, &hitend);
 
329
                NOERR();
 
330
                if (hitend && cold == NULL)
 
331
                        cold = begin;
 
332
                if (end != NULL)
 
333
                        break;                          /* NOTE BREAK OUT */
 
334
        }
 
335
        assert(end != NULL);            /* search RE succeeded so loop should */
 
336
        freedfa(d);
 
337
 
 
338
        /* and pin down details */
 
339
        assert(v->nmatch > 0);
 
340
        v->pmatch[0].rm_so = OFF(begin);
 
341
        v->pmatch[0].rm_eo = OFF(end);
 
342
        if (v->g->cflags & REG_EXPECT)
 
343
        {
 
344
                if (cold != NULL)
 
345
                        v->details->rm_extend.rm_so = OFF(cold);
 
346
                else
 
347
                        v->details->rm_extend.rm_so = OFF(v->stop);
 
348
                v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
 
349
        }
 
350
        if (v->nmatch == 1)                     /* no need for submatches */
 
351
                return REG_OKAY;
 
352
 
 
353
        /* submatches */
 
354
        zapsubs(v->pmatch, v->nmatch);
 
355
        return dissect(v, v->g->tree, begin, end);
 
356
}
 
357
 
 
358
/*
 
359
 * cfind - find a match for the main NFA (with complications)
 
360
 */
 
361
static int
 
362
cfind(struct vars * v,
 
363
          struct cnfa * cnfa,
 
364
          struct colormap * cm)
 
365
{
 
366
        struct dfa *s;
 
367
        struct dfa *d;
 
368
        chr                *cold;
 
369
        int                     ret;
 
370
 
 
371
        s = newdfa(v, &v->g->search, cm, &v->dfa1);
 
372
        NOERR();
 
373
        d = newdfa(v, cnfa, cm, &v->dfa2);
 
374
        if (ISERR())
 
375
        {
 
376
                assert(d == NULL);
 
377
                freedfa(s);
 
378
                return v->err;
 
379
        }
 
380
 
 
381
        ret = cfindloop(v, cnfa, cm, d, s, &cold);
 
382
 
 
383
        freedfa(d);
 
384
        freedfa(s);
 
385
        NOERR();
 
386
        if (v->g->cflags & REG_EXPECT)
 
387
        {
 
388
                assert(v->details != NULL);
 
389
                if (cold != NULL)
 
390
                        v->details->rm_extend.rm_so = OFF(cold);
 
391
                else
 
392
                        v->details->rm_extend.rm_so = OFF(v->stop);
 
393
                v->details->rm_extend.rm_eo = OFF(v->stop);             /* unknown */
 
394
        }
 
395
        return ret;
 
396
}
 
397
 
 
398
/*
 
399
 * cfindloop - the heart of cfind
 
400
 */
 
401
static int
 
402
cfindloop(struct vars * v,
 
403
                  struct cnfa * cnfa,
 
404
                  struct colormap * cm,
 
405
                  struct dfa * d,
 
406
                  struct dfa * s,
 
407
                  chr **coldp)                  /* where to put coldstart pointer */
 
408
{
 
409
        chr                *begin;
 
410
        chr                *end;
 
411
        chr                *cold;
 
412
        chr                *open;                       /* open and close of range of possible starts */
 
413
        chr                *close;
 
414
        chr                *estart;
 
415
        chr                *estop;
 
416
        int                     er;
 
417
        int                     shorter = v->g->tree->flags & SHORTER;
 
418
        int                     hitend;
 
419
 
 
420
        assert(d != NULL && s != NULL);
 
421
        cold = NULL;
 
422
        close = v->search_start;
 
423
        do
 
424
        {
 
425
                MDEBUG(("\ncsearch at %ld\n", LOFF(close)));
 
426
                close = shortest(v, s, close, close, v->stop, &cold, (int *) NULL);
 
427
                if (close == NULL)
 
428
                        break;                          /* NOTE BREAK */
 
429
                assert(cold != NULL);
 
430
                open = cold;
 
431
                cold = NULL;
 
432
                MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
 
433
                for (begin = open; begin <= close; begin++)
 
434
                {
 
435
                        MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
 
436
                        estart = begin;
 
437
                        estop = v->stop;
 
438
                        for (;;)
 
439
                        {
 
440
                                if (shorter)
 
441
                                        end = shortest(v, d, begin, estart,
 
442
                                                                   estop, (chr **) NULL, &hitend);
 
443
                                else
 
444
                                        end = longest(v, d, begin, estop,
 
445
                                                                  &hitend);
 
446
                                if (hitend && cold == NULL)
 
447
                                        cold = begin;
 
448
                                if (end == NULL)
 
449
                                        break;          /* NOTE BREAK OUT */
 
450
                                MDEBUG(("tentative end %ld\n", LOFF(end)));
 
451
                                zapsubs(v->pmatch, v->nmatch);
 
452
                                zapmem(v, v->g->tree);
 
453
                                er = cdissect(v, v->g->tree, begin, end);
 
454
                                if (er == REG_OKAY)
 
455
                                {
 
456
                                        if (v->nmatch > 0)
 
457
                                        {
 
458
                                                v->pmatch[0].rm_so = OFF(begin);
 
459
                                                v->pmatch[0].rm_eo = OFF(end);
 
460
                                        }
 
461
                                        *coldp = cold;
 
462
                                        return REG_OKAY;
 
463
                                }
 
464
                                if (er != REG_NOMATCH)
 
465
                                {
 
466
                                        ERR(er);
 
467
                                        *coldp = cold;
 
468
                                        return er;
 
469
                                }
 
470
                                if ((shorter) ? end == estop : end == begin)
 
471
                                {
 
472
                                        /* no point in trying again */
 
473
                                        *coldp = cold;
 
474
                                        return REG_NOMATCH;
 
475
                                }
 
476
                                /* go around and try again */
 
477
                                if (shorter)
 
478
                                        estart = end + 1;
 
479
                                else
 
480
                                        estop = end - 1;
 
481
                        }
 
482
                }
 
483
        } while (close < v->stop);
 
484
 
 
485
        *coldp = cold;
 
486
        return REG_NOMATCH;
 
487
}
 
488
 
 
489
/*
 
490
 * zapsubs - initialize the subexpression matches to "no match"
 
491
 */
 
492
static void
 
493
zapsubs(regmatch_t *p,
 
494
                size_t n)
 
495
{
 
496
        size_t          i;
 
497
 
 
498
        for (i = n - 1; i > 0; i--)
 
499
        {
 
500
                p[i].rm_so = -1;
 
501
                p[i].rm_eo = -1;
 
502
        }
 
503
}
 
504
 
 
505
/*
 
506
 * zapmem - initialize the retry memory of a subtree to zeros
 
507
 */
 
508
static void
 
509
zapmem(struct vars * v,
 
510
           struct subre * t)
 
511
{
 
512
        if (t == NULL)
 
513
                return;
 
514
 
 
515
        assert(v->mem != NULL);
 
516
        v->mem[t->retry] = 0;
 
517
        if (t->op == '(')
 
518
        {
 
519
                assert(t->subno > 0);
 
520
                v->pmatch[t->subno].rm_so = -1;
 
521
                v->pmatch[t->subno].rm_eo = -1;
 
522
        }
 
523
 
 
524
        if (t->left != NULL)
 
525
                zapmem(v, t->left);
 
526
        if (t->right != NULL)
 
527
                zapmem(v, t->right);
 
528
}
 
529
 
 
530
/*
 
531
 * subset - set any subexpression relevant to a successful subre
 
532
 */
 
533
static void
 
534
subset(struct vars * v,
 
535
           struct subre * sub,
 
536
           chr *begin,
 
537
           chr *end)
 
538
{
 
539
        int                     n = sub->subno;
 
540
 
 
541
        assert(n > 0);
 
542
        if ((size_t) n >= v->nmatch)
 
543
                return;
 
544
 
 
545
        MDEBUG(("setting %d\n", n));
 
546
        v->pmatch[n].rm_so = OFF(begin);
 
547
        v->pmatch[n].rm_eo = OFF(end);
 
548
}
 
549
 
 
550
/*
 
551
 * dissect - determine subexpression matches (uncomplicated case)
 
552
 */
 
553
static int                                              /* regexec return code */
 
554
dissect(struct vars * v,
 
555
                struct subre * t,
 
556
                chr *begin,                             /* beginning of relevant substring */
 
557
                chr *end)                               /* end of same */
 
558
{
 
559
        assert(t != NULL);
 
560
        MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
 
561
 
 
562
        switch (t->op)
 
563
        {
 
564
                case '=':                               /* terminal node */
 
565
                        assert(t->left == NULL && t->right == NULL);
 
566
                        return REG_OKAY;        /* no action, parent did the work */
 
567
                case '|':                               /* alternation */
 
568
                        assert(t->left != NULL);
 
569
                        return altdissect(v, t, begin, end);
 
570
                case 'b':                               /* back ref -- shouldn't be calling us! */
 
571
                        return REG_ASSERT;
 
572
                case '.':                               /* concatenation */
 
573
                        assert(t->left != NULL && t->right != NULL);
 
574
                        return condissect(v, t, begin, end);
 
575
                case '(':                               /* capturing */
 
576
                        assert(t->left != NULL && t->right == NULL);
 
577
                        assert(t->subno > 0);
 
578
                        subset(v, t, begin, end);
 
579
                        return dissect(v, t->left, begin, end);
 
580
                default:
 
581
                        return REG_ASSERT;
 
582
        }
 
583
}
 
584
 
 
585
/*
 
586
 * condissect - determine concatenation subexpression matches (uncomplicated)
 
587
 */
 
588
static int                                              /* regexec return code */
 
589
condissect(struct vars * v,
 
590
                   struct subre * t,
 
591
                   chr *begin,                  /* beginning of relevant substring */
 
592
                   chr *end)                    /* end of same */
 
593
{
 
594
        struct dfa *d;
 
595
        struct dfa *d2;
 
596
        chr                *mid;
 
597
        int                     i;
 
598
        int                     shorter = (t->left->flags & SHORTER) ? 1 : 0;
 
599
        chr                *stop = (shorter) ? end : begin;
 
600
 
 
601
        assert(t->op == '.');
 
602
        assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
603
        assert(t->right != NULL && t->right->cnfa.nstates > 0);
 
604
 
 
605
        d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
 
606
        NOERR();
 
607
        d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
 
608
        if (ISERR())
 
609
        {
 
610
                assert(d2 == NULL);
 
611
                freedfa(d);
 
612
                return v->err;
 
613
        }
 
614
 
 
615
        /* pick a tentative midpoint */
 
616
        if (shorter)
 
617
                mid = shortest(v, d, begin, begin, end, (chr **) NULL,
 
618
                                           (int *) NULL);
 
619
        else
 
620
                mid = longest(v, d, begin, end, (int *) NULL);
 
621
        if (mid == NULL)
 
622
        {
 
623
                freedfa(d);
 
624
                freedfa(d2);
 
625
                return REG_ASSERT;
 
626
        }
 
627
        MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
628
 
 
629
        /* iterate until satisfaction or failure */
 
630
        while (longest(v, d2, mid, end, (int *) NULL) != end)
 
631
        {
 
632
                /* that midpoint didn't work, find a new one */
 
633
                if (mid == stop)
 
634
                {
 
635
                        /* all possibilities exhausted! */
 
636
                        MDEBUG(("no midpoint!\n"));
 
637
                        freedfa(d);
 
638
                        freedfa(d2);
 
639
                        return REG_ASSERT;
 
640
                }
 
641
                if (shorter)
 
642
                        mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL,
 
643
                                                   (int *) NULL);
 
644
                else
 
645
                        mid = longest(v, d, begin, mid - 1, (int *) NULL);
 
646
                if (mid == NULL)
 
647
                {
 
648
                        /* failed to find a new one! */
 
649
                        MDEBUG(("failed midpoint!\n"));
 
650
                        freedfa(d);
 
651
                        freedfa(d2);
 
652
                        return REG_ASSERT;
 
653
                }
 
654
                MDEBUG(("new midpoint %ld\n", LOFF(mid)));
 
655
        }
 
656
 
 
657
        /* satisfaction */
 
658
        MDEBUG(("successful\n"));
 
659
        freedfa(d);
 
660
        freedfa(d2);
 
661
        i = dissect(v, t->left, begin, mid);
 
662
        if (i != REG_OKAY)
 
663
                return i;
 
664
        return dissect(v, t->right, mid, end);
 
665
}
 
666
 
 
667
/*
 
668
 * altdissect - determine alternative subexpression matches (uncomplicated)
 
669
 */
 
670
static int                                              /* regexec return code */
 
671
altdissect(struct vars * v,
 
672
                   struct subre * t,
 
673
                   chr *begin,                  /* beginning of relevant substring */
 
674
                   chr *end)                    /* end of same */
 
675
{
 
676
        struct dfa *d;
 
677
        int                     i;
 
678
 
 
679
        assert(t != NULL);
 
680
        assert(t->op == '|');
 
681
 
 
682
        for (i = 0; t != NULL; t = t->right, i++)
 
683
        {
 
684
                MDEBUG(("trying %dth\n", i));
 
685
                assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
686
                d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
 
687
                if (ISERR())
 
688
                        return v->err;
 
689
                if (longest(v, d, begin, end, (int *) NULL) == end)
 
690
                {
 
691
                        MDEBUG(("success\n"));
 
692
                        freedfa(d);
 
693
                        return dissect(v, t->left, begin, end);
 
694
                }
 
695
                freedfa(d);
 
696
        }
 
697
        return REG_ASSERT;                      /* none of them matched?!? */
 
698
}
 
699
 
 
700
/*
 
701
 * cdissect - determine subexpression matches (with complications)
 
702
 * The retry memory stores the offset of the trial midpoint from begin,
 
703
 * plus 1 so that 0 uniquely means "clean slate".
 
704
 */
 
705
static int                                              /* regexec return code */
 
706
cdissect(struct vars * v,
 
707
                 struct subre * t,
 
708
                 chr *begin,                    /* beginning of relevant substring */
 
709
                 chr *end)                              /* end of same */
 
710
{
 
711
        assert(t != NULL);
 
712
        MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
 
713
 
 
714
        switch (t->op)
 
715
        {
 
716
                case '=':                               /* terminal node */
 
717
                        assert(t->left == NULL && t->right == NULL);
 
718
                        return REG_OKAY;        /* no action, parent did the work */
 
719
                case '|':                               /* alternation */
 
720
                        assert(t->left != NULL);
 
721
                        return caltdissect(v, t, begin, end);
 
722
                case 'b':                               /* back ref -- shouldn't be calling us! */
 
723
                        assert(t->left == NULL && t->right == NULL);
 
724
                        return cbrdissect(v, t, begin, end);
 
725
                case '.':                               /* concatenation */
 
726
                        assert(t->left != NULL && t->right != NULL);
 
727
                        return ccondissect(v, t, begin, end);
 
728
                case '(':                               /* capturing */
 
729
                        assert(t->left != NULL && t->right == NULL);
 
730
                        return ccaptdissect(v, t, begin, end);
 
731
                default:
 
732
                        return REG_ASSERT;
 
733
        }
 
734
}
 
735
 
 
736
/*
 
737
 * ccaptdissect - capture subexpression matches (with complications)
 
738
 */
 
739
static int                                              /* regexec return code */
 
740
ccaptdissect(struct vars * v,
 
741
                         struct subre * t,
 
742
                         chr *begin,            /* beginning of relevant substring */
 
743
                         chr *end)                      /* end of same */
 
744
{
 
745
        int                     er;
 
746
 
 
747
        assert(t->subno > 0);
 
748
 
 
749
        er = cdissect(v, t->left, begin, end);
 
750
        if (er == REG_OKAY)
 
751
                subset(v, t, begin, end);
 
752
        return er;
 
753
}
 
754
 
 
755
/*
 
756
 * ccondissect - concatenation subexpression matches (with complications)
 
757
 * The retry memory stores the offset of the trial midpoint from begin,
 
758
 * plus 1 so that 0 uniquely means "clean slate".
 
759
 */
 
760
static int                                              /* regexec return code */
 
761
ccondissect(struct vars * v,
 
762
                        struct subre * t,
 
763
                        chr *begin,                     /* beginning of relevant substring */
 
764
                        chr *end)                       /* end of same */
 
765
{
 
766
        struct dfa *d;
 
767
        struct dfa *d2;
 
768
        chr                *mid;
 
769
        int                     er;
 
770
 
 
771
        assert(t->op == '.');
 
772
        assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
773
        assert(t->right != NULL && t->right->cnfa.nstates > 0);
 
774
 
 
775
        if (t->left->flags & SHORTER)           /* reverse scan */
 
776
                return crevdissect(v, t, begin, end);
 
777
 
 
778
        d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 
779
        if (ISERR())
 
780
                return v->err;
 
781
        d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
 
782
        if (ISERR())
 
783
        {
 
784
                freedfa(d);
 
785
                return v->err;
 
786
        }
 
787
        MDEBUG(("cconcat %d\n", t->retry));
 
788
 
 
789
        /* pick a tentative midpoint */
 
790
        if (v->mem[t->retry] == 0)
 
791
        {
 
792
                mid = longest(v, d, begin, end, (int *) NULL);
 
793
                if (mid == NULL)
 
794
                {
 
795
                        freedfa(d);
 
796
                        freedfa(d2);
 
797
                        return REG_NOMATCH;
 
798
                }
 
799
                MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
800
                v->mem[t->retry] = (mid - begin) + 1;
 
801
        }
 
802
        else
 
803
        {
 
804
                mid = begin + (v->mem[t->retry] - 1);
 
805
                MDEBUG(("working midpoint %ld\n", LOFF(mid)));
 
806
        }
 
807
 
 
808
        /* iterate until satisfaction or failure */
 
809
        for (;;)
 
810
        {
 
811
                /* try this midpoint on for size */
 
812
                if (longest(v, d2, mid, end, (int *) NULL) == end)
 
813
                {
 
814
                        er = cdissect(v, t->left, begin, mid);
 
815
                        if (er == REG_OKAY)
 
816
                        {
 
817
                                er = cdissect(v, t->right, mid, end);
 
818
                                if (er == REG_OKAY)
 
819
                                {
 
820
                                        /* satisfaction */
 
821
                                        MDEBUG(("successful\n"));
 
822
                                        freedfa(d);
 
823
                                        freedfa(d2);
 
824
                                        return REG_OKAY;
 
825
                                }
 
826
                        }
 
827
                        if (er != REG_OKAY && er != REG_NOMATCH)
 
828
                        {
 
829
                                freedfa(d);
 
830
                                freedfa(d2);
 
831
                                return er;
 
832
                        }
 
833
                }
 
834
 
 
835
                /* that midpoint didn't work, find a new one */
 
836
                if (mid == begin)
 
837
                {
 
838
                        /* all possibilities exhausted */
 
839
                        MDEBUG(("%d no midpoint\n", t->retry));
 
840
                        freedfa(d);
 
841
                        freedfa(d2);
 
842
                        return REG_NOMATCH;
 
843
                }
 
844
                mid = longest(v, d, begin, mid - 1, (int *) NULL);
 
845
                if (mid == NULL)
 
846
                {
 
847
                        /* failed to find a new one */
 
848
                        MDEBUG(("%d failed midpoint\n", t->retry));
 
849
                        freedfa(d);
 
850
                        freedfa(d2);
 
851
                        return REG_NOMATCH;
 
852
                }
 
853
                MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
 
854
                v->mem[t->retry] = (mid - begin) + 1;
 
855
                zapmem(v, t->left);
 
856
                zapmem(v, t->right);
 
857
        }
 
858
 
 
859
        /* can't get here */
 
860
        return REG_ASSERT;
 
861
}
 
862
 
 
863
/*
 
864
 * crevdissect - determine backref shortest-first subexpression matches
 
865
 * The retry memory stores the offset of the trial midpoint from begin,
 
866
 * plus 1 so that 0 uniquely means "clean slate".
 
867
 */
 
868
static int                                              /* regexec return code */
 
869
crevdissect(struct vars * v,
 
870
                        struct subre * t,
 
871
                        chr *begin,                     /* beginning of relevant substring */
 
872
                        chr *end)                       /* end of same */
 
873
{
 
874
        struct dfa *d;
 
875
        struct dfa *d2;
 
876
        chr                *mid;
 
877
        int                     er;
 
878
 
 
879
        assert(t->op == '.');
 
880
        assert(t->left != NULL && t->left->cnfa.nstates > 0);
 
881
        assert(t->right != NULL && t->right->cnfa.nstates > 0);
 
882
        assert(t->left->flags & SHORTER);
 
883
 
 
884
        /* concatenation -- need to split the substring between parts */
 
885
        d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 
886
        if (ISERR())
 
887
                return v->err;
 
888
        d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
 
889
        if (ISERR())
 
890
        {
 
891
                freedfa(d);
 
892
                return v->err;
 
893
        }
 
894
        MDEBUG(("crev %d\n", t->retry));
 
895
 
 
896
        /* pick a tentative midpoint */
 
897
        if (v->mem[t->retry] == 0)
 
898
        {
 
899
                mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
 
900
                if (mid == NULL)
 
901
                {
 
902
                        freedfa(d);
 
903
                        freedfa(d2);
 
904
                        return REG_NOMATCH;
 
905
                }
 
906
                MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
 
907
                v->mem[t->retry] = (mid - begin) + 1;
 
908
        }
 
909
        else
 
910
        {
 
911
                mid = begin + (v->mem[t->retry] - 1);
 
912
                MDEBUG(("working midpoint %ld\n", LOFF(mid)));
 
913
        }
 
914
 
 
915
        /* iterate until satisfaction or failure */
 
916
        for (;;)
 
917
        {
 
918
                /* try this midpoint on for size */
 
919
                if (longest(v, d2, mid, end, (int *) NULL) == end)
 
920
                {
 
921
                        er = cdissect(v, t->left, begin, mid);
 
922
                        if (er == REG_OKAY)
 
923
                        {
 
924
                                er = cdissect(v, t->right, mid, end);
 
925
                                if (er == REG_OKAY)
 
926
                                {
 
927
                                        /* satisfaction */
 
928
                                        MDEBUG(("successful\n"));
 
929
                                        freedfa(d);
 
930
                                        freedfa(d2);
 
931
                                        return REG_OKAY;
 
932
                                }
 
933
                        }
 
934
                        if (er != REG_OKAY && er != REG_NOMATCH)
 
935
                        {
 
936
                                freedfa(d);
 
937
                                freedfa(d2);
 
938
                                return er;
 
939
                        }
 
940
                }
 
941
 
 
942
                /* that midpoint didn't work, find a new one */
 
943
                if (mid == end)
 
944
                {
 
945
                        /* all possibilities exhausted */
 
946
                        MDEBUG(("%d no midpoint\n", t->retry));
 
947
                        freedfa(d);
 
948
                        freedfa(d2);
 
949
                        return REG_NOMATCH;
 
950
                }
 
951
                mid = shortest(v, d, begin, mid + 1, end, (chr **) NULL, (int *) NULL);
 
952
                if (mid == NULL)
 
953
                {
 
954
                        /* failed to find a new one */
 
955
                        MDEBUG(("%d failed midpoint\n", t->retry));
 
956
                        freedfa(d);
 
957
                        freedfa(d2);
 
958
                        return REG_NOMATCH;
 
959
                }
 
960
                MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
 
961
                v->mem[t->retry] = (mid - begin) + 1;
 
962
                zapmem(v, t->left);
 
963
                zapmem(v, t->right);
 
964
        }
 
965
 
 
966
        /* can't get here */
 
967
        return REG_ASSERT;
 
968
}
 
969
 
 
970
/*
 
971
 * cbrdissect - determine backref subexpression matches
 
972
 */
 
973
static int                                              /* regexec return code */
 
974
cbrdissect(struct vars * v,
 
975
                   struct subre * t,
 
976
                   chr *begin,                  /* beginning of relevant substring */
 
977
                   chr *end)                    /* end of same */
 
978
{
 
979
        int                     i;
 
980
        int                     n = t->subno;
 
981
        size_t          len;
 
982
        chr                *paren;
 
983
        chr                *p;
 
984
        chr                *stop;
 
985
        int                     min = t->min;
 
986
        int                     max = t->max;
 
987
 
 
988
        assert(t != NULL);
 
989
        assert(t->op == 'b');
 
990
        assert(n >= 0);
 
991
        assert((size_t) n < v->nmatch);
 
992
 
 
993
        MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max));
 
994
 
 
995
        if (v->pmatch[n].rm_so == -1)
 
996
                return REG_NOMATCH;
 
997
        paren = v->start + v->pmatch[n].rm_so;
 
998
        len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;
 
999
 
 
1000
        /* no room to maneuver -- retries are pointless */
 
1001
        if (v->mem[t->retry])
 
1002
                return REG_NOMATCH;
 
1003
        v->mem[t->retry] = 1;
 
1004
 
 
1005
        /* special-case zero-length string */
 
1006
        if (len == 0)
 
1007
        {
 
1008
                if (begin == end)
 
1009
                        return REG_OKAY;
 
1010
                return REG_NOMATCH;
 
1011
        }
 
1012
 
 
1013
        /* and too-short string */
 
1014
        assert(end >= begin);
 
1015
        if ((size_t) (end - begin) < len)
 
1016
                return REG_NOMATCH;
 
1017
        stop = end - len;
 
1018
 
 
1019
        /* count occurrences */
 
1020
        i = 0;
 
1021
        for (p = begin; p <= stop && (i < max || max == INFINITY); p += len)
 
1022
        {
 
1023
                if ((*v->g->compare) (paren, p, len) != 0)
 
1024
                        break;
 
1025
                i++;
 
1026
        }
 
1027
        MDEBUG(("cbackref found %d\n", i));
 
1028
 
 
1029
        /* and sort it out */
 
1030
        if (p != end)                           /* didn't consume all of it */
 
1031
                return REG_NOMATCH;
 
1032
        if (min <= i && (i <= max || max == INFINITY))
 
1033
                return REG_OKAY;
 
1034
        return REG_NOMATCH;                     /* out of range */
 
1035
}
 
1036
 
 
1037
/*
 
1038
 * caltdissect - determine alternative subexpression matches (w. complications)
 
1039
 */
 
1040
static int                                              /* regexec return code */
 
1041
caltdissect(struct vars * v,
 
1042
                        struct subre * t,
 
1043
                        chr *begin,                     /* beginning of relevant substring */
 
1044
                        chr *end)                       /* end of same */
 
1045
{
 
1046
        struct dfa *d;
 
1047
        int                     er;
 
1048
 
 
1049
#define  UNTRIED 0                              /* not yet tried at all */
 
1050
#define  TRYING  1                              /* top matched, trying submatches */
 
1051
#define  TRIED   2                              /* top didn't match or submatches exhausted */
 
1052
 
 
1053
        if (t == NULL)
 
1054
                return REG_NOMATCH;
 
1055
        assert(t->op == '|');
 
1056
        if (v->mem[t->retry] == TRIED)
 
1057
                return caltdissect(v, t->right, begin, end);
 
1058
 
 
1059
        MDEBUG(("calt n%d\n", t->retry));
 
1060
        assert(t->left != NULL);
 
1061
 
 
1062
        if (v->mem[t->retry] == UNTRIED)
 
1063
        {
 
1064
                d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
 
1065
                if (ISERR())
 
1066
                        return v->err;
 
1067
                if (longest(v, d, begin, end, (int *) NULL) != end)
 
1068
                {
 
1069
                        freedfa(d);
 
1070
                        v->mem[t->retry] = TRIED;
 
1071
                        return caltdissect(v, t->right, begin, end);
 
1072
                }
 
1073
                freedfa(d);
 
1074
                MDEBUG(("calt matched\n"));
 
1075
                v->mem[t->retry] = TRYING;
 
1076
        }
 
1077
 
 
1078
        er = cdissect(v, t->left, begin, end);
 
1079
        if (er != REG_NOMATCH)
 
1080
                return er;
 
1081
 
 
1082
        v->mem[t->retry] = TRIED;
 
1083
        return caltdissect(v, t->right, begin, end);
 
1084
}
 
1085
 
 
1086
 
 
1087
 
 
1088
#include "rege_dfa.c"