← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Support/regengine.inc

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Support/regengine.inc
 
1
/*-
 
2
 * This code is derived from OpenBSD's libc/regex, original license follows:
 
3
 *
 
4
 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
 
5
 * Copyright (c) 1992, 1993, 1994
 
6
 *      The Regents of the University of California.  All rights reserved.
 
7
 *
 
8
 * This code is derived from software contributed to Berkeley by
 
9
 * Henry Spencer.
 
10
 *
 
11
 * Redistribution and use in source and binary forms, with or without
 
12
 * modification, are permitted provided that the following conditions
 
13
 * are met:
 
14
 * 1. Redistributions of source code must retain the above copyright
 
15
 *    notice, this list of conditions and the following disclaimer.
 
16
 * 2. Redistributions in binary form must reproduce the above copyright
 
17
 *    notice, this list of conditions and the following disclaimer in the
 
18
 *    documentation and/or other materials provided with the distribution.
 
19
 * 3. Neither the name of the University nor the names of its contributors
 
20
 *    may be used to endorse or promote products derived from this software
 
21
 *    without specific prior written permission.
 
22
 *
 
23
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 
24
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
25
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
26
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 
27
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
28
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
29
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
30
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
31
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
32
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
33
 * SUCH DAMAGE.
 
34
 *
 
35
 *      @(#)engine.c    8.5 (Berkeley) 3/20/94
 
36
 */
 
37
 
 
38
/*
 
39
 * The matching engine and friends.  This file is #included by regexec.c
 
40
 * after suitable #defines of a variety of macros used herein, so that
 
41
 * different state representations can be used without duplicating masses
 
42
 * of code.
 
43
 */
 
44
 
 
45
#ifdef SNAMES
 
46
#define matcher smatcher
 
47
#define fast    sfast
 
48
#define slow    sslow
 
49
#define dissect sdissect
 
50
#define backref sbackref
 
51
#define step    sstep
 
52
#define print   sprint
 
53
#define at      sat
 
54
#define match   smat
 
55
#define nope    snope
 
56
#endif
 
57
#ifdef LNAMES
 
58
#define matcher lmatcher
 
59
#define fast    lfast
 
60
#define slow    lslow
 
61
#define dissect ldissect
 
62
#define backref lbackref
 
63
#define step    lstep
 
64
#define print   lprint
 
65
#define at      lat
 
66
#define match   lmat
 
67
#define nope    lnope
 
68
#endif
 
69
 
 
70
/* another structure passed up and down to avoid zillions of parameters */
 
71
struct match {
 
72
        struct re_guts *g;
 
73
        int eflags;
 
74
        llvm_regmatch_t *pmatch;        /* [nsub+1] (0 element unused) */
 
75
        const char *offp;               /* offsets work from here */
 
76
        const char *beginp;             /* start of string -- virtual NUL precedes */
 
77
        const char *endp;               /* end of string -- virtual NUL here */
 
78
        const char *coldp;              /* can be no match starting before here */
 
79
        const char **lastpos;           /* [nplus+1] */
 
80
        STATEVARS;
 
81
        states st;              /* current states */
 
82
        states fresh;           /* states for a fresh start */
 
83
        states tmp;             /* temporary */
 
84
        states empty;           /* empty set of states */
 
85
};
 
86
 
 
87
static int matcher(struct re_guts *, const char *, size_t,
 
88
                   llvm_regmatch_t[], int);
 
89
static const char *dissect(struct match *, const char *, const char *, sopno,
 
90
                           sopno);
 
91
static const char *backref(struct match *, const char *, const char *, sopno,
 
92
                           sopno, sopno, int);
 
93
static const char *fast(struct match *, const char *, const char *, sopno, sopno);
 
94
static const char *slow(struct match *, const char *, const char *, sopno, sopno);
 
95
static states step(struct re_guts *, sopno, sopno, states, int, states);
 
96
#define MAX_RECURSION   100
 
97
#define BOL     (OUT+1)
 
98
#define EOL     (BOL+1)
 
99
#define BOLEOL  (BOL+2)
 
100
#define NOTHING (BOL+3)
 
101
#define BOW     (BOL+4)
 
102
#define EOW     (BOL+5)
 
103
#define CODEMAX (BOL+5)         /* highest code used */
 
104
#define NONCHAR(c)      ((c) > CHAR_MAX)
 
105
#define NNONCHAR        (CODEMAX-CHAR_MAX)
 
106
#ifdef REDEBUG
 
107
static void print(struct match *, char *, states, int, FILE *);
 
108
#endif
 
109
#ifdef REDEBUG
 
110
static void at(struct match *, char *, char *, char *, sopno, sopno);
 
111
#endif
 
112
#ifdef REDEBUG
 
113
static char *pchar(int);
 
114
#endif
 
115
 
 
116
#ifdef REDEBUG
 
117
#define SP(t, s, c)     print(m, t, s, c, stdout)
 
118
#define AT(t, p1, p2, s1, s2)   at(m, t, p1, p2, s1, s2)
 
119
#define NOTE(str)       { if (m->eflags&REG_TRACE) (void)printf("=%s\n", (str)); }
 
120
static int nope = 0;
 
121
#else
 
122
#define SP(t, s, c)     /* nothing */
 
123
#define AT(t, p1, p2, s1, s2)   /* nothing */
 
124
#define NOTE(s) /* nothing */
 
125
#endif
 
126
 
 
127
/*
 
128
 - matcher - the actual matching engine
 
129
 */
 
130
static int                      /* 0 success, REG_NOMATCH failure */
 
131
matcher(struct re_guts *g, const char *string, size_t nmatch,
 
132
        llvm_regmatch_t pmatch[],
 
133
    int eflags)
 
134
{
 
135
        const char *endp;
 
136
        size_t i;
 
137
        struct match mv;
 
138
        struct match *m = &mv;
 
139
        const char *dp;
 
140
        const sopno gf = g->firststate+1;       /* +1 for OEND */
 
141
        const sopno gl = g->laststate;
 
142
        const char *start;
 
143
        const char *stop;
 
144
 
 
145
        /* simplify the situation where possible */
 
146
        if (g->cflags&REG_NOSUB)
 
147
                nmatch = 0;
 
148
        if (eflags&REG_STARTEND) {
 
149
                start = string + pmatch[0].rm_so;
 
150
                stop = string + pmatch[0].rm_eo;
 
151
        } else {
 
152
                start = string;
 
153
                stop = start + strlen(start);
 
154
        }
 
155
        if (stop < start)
 
156
                return(REG_INVARG);
 
157
 
 
158
        /* prescreening; this does wonders for this rather slow code */
 
159
        if (g->must != NULL) {
 
160
                for (dp = start; dp < stop; dp++)
 
161
                        if (*dp == g->must[0] && stop - dp >= g->mlen &&
 
162
                                memcmp(dp, g->must, (size_t)g->mlen) == 0)
 
163
                                break;
 
164
                if (dp == stop)         /* we didn't find g->must */
 
165
                        return(REG_NOMATCH);
 
166
        }
 
167
 
 
168
        /* match struct setup */
 
169
        m->g = g;
 
170
        m->eflags = eflags;
 
171
        m->pmatch = NULL;
 
172
        m->lastpos = NULL;
 
173
        m->offp = string;
 
174
        m->beginp = start;
 
175
        m->endp = stop;
 
176
        STATESETUP(m, 4);
 
177
        SETUP(m->st);
 
178
        SETUP(m->fresh);
 
179
        SETUP(m->tmp);
 
180
        SETUP(m->empty);
 
181
        CLEAR(m->empty);
 
182
 
 
183
        /* this loop does only one repetition except for backrefs */
 
184
        for (;;) {
 
185
                endp = fast(m, start, stop, gf, gl);
 
186
                if (endp == NULL) {             /* a miss */
 
187
                        free(m->pmatch);
 
188
                        free((void*)m->lastpos);
 
189
                        STATETEARDOWN(m);
 
190
                        return(REG_NOMATCH);
 
191
                }
 
192
                if (nmatch == 0 && !g->backrefs)
 
193
                        break;          /* no further info needed */
 
194
 
 
195
                /* where? */
 
196
                assert(m->coldp != NULL);
 
197
                for (;;) {
 
198
                        NOTE("finding start");
 
199
                        endp = slow(m, m->coldp, stop, gf, gl);
 
200
                        if (endp != NULL)
 
201
                                break;
 
202
                        assert(m->coldp < m->endp);
 
203
                        m->coldp++;
 
204
                }
 
205
                if (nmatch == 1 && !g->backrefs)
 
206
                        break;          /* no further info needed */
 
207
 
 
208
                /* oh my, he wants the subexpressions... */
 
209
                if (m->pmatch == NULL)
 
210
                        m->pmatch = (llvm_regmatch_t *)malloc((m->g->nsub + 1) *
 
211
                                                        sizeof(llvm_regmatch_t));
 
212
                if (m->pmatch == NULL) {
 
213
                        STATETEARDOWN(m);
 
214
                        return(REG_ESPACE);
 
215
                }
 
216
                for (i = 1; i <= m->g->nsub; i++)
 
217
                        m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
 
218
                if (!g->backrefs && !(m->eflags&REG_BACKR)) {
 
219
                        NOTE("dissecting");
 
220
                        dp = dissect(m, m->coldp, endp, gf, gl);
 
221
                } else {
 
222
                        if (g->nplus > 0 && m->lastpos == NULL)
 
223
                                m->lastpos = (const char **)malloc((g->nplus+1) *
 
224
                                                        sizeof(char *));
 
225
                        if (g->nplus > 0 && m->lastpos == NULL) {
 
226
                                free(m->pmatch);
 
227
                                STATETEARDOWN(m);
 
228
                                return(REG_ESPACE);
 
229
                        }
 
230
                        NOTE("backref dissect");
 
231
                        dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 
232
                }
 
233
                if (dp != NULL)
 
234
                        break;
 
235
 
 
236
                /* uh-oh... we couldn't find a subexpression-level match */
 
237
                assert(g->backrefs);    /* must be back references doing it */
 
238
                assert(g->nplus == 0 || m->lastpos != NULL);
 
239
                for (;;) {
 
240
                        if (dp != NULL || endp <= m->coldp)
 
241
                                break;          /* defeat */
 
242
                        NOTE("backoff");
 
243
                        endp = slow(m, m->coldp, endp-1, gf, gl);
 
244
                        if (endp == NULL)
 
245
                                break;          /* defeat */
 
246
                        /* try it on a shorter possibility */
 
247
#ifndef NDEBUG
 
248
                        for (i = 1; i <= m->g->nsub; i++) {
 
249
                                assert(m->pmatch[i].rm_so == -1);
 
250
                                assert(m->pmatch[i].rm_eo == -1);
 
251
                        }
 
252
#endif
 
253
                        NOTE("backoff dissect");
 
254
                        dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0);
 
255
                }
 
256
                assert(dp == NULL || dp == endp);
 
257
                if (dp != NULL)         /* found a shorter one */
 
258
                        break;
 
259
 
 
260
                /* despite initial appearances, there is no match here */
 
261
                NOTE("false alarm");
 
262
                if (m->coldp == stop)
 
263
                        break;
 
264
                start = m->coldp + 1;   /* recycle starting later */
 
265
        }
 
266
 
 
267
        /* fill in the details if requested */
 
268
        if (nmatch > 0) {
 
269
                pmatch[0].rm_so = m->coldp - m->offp;
 
270
                pmatch[0].rm_eo = endp - m->offp;
 
271
        }
 
272
        if (nmatch > 1) {
 
273
                assert(m->pmatch != NULL);
 
274
                for (i = 1; i < nmatch; i++)
 
275
                        if (i <= m->g->nsub)
 
276
                                pmatch[i] = m->pmatch[i];
 
277
                        else {
 
278
                                pmatch[i].rm_so = -1;
 
279
                                pmatch[i].rm_eo = -1;
 
280
                        }
 
281
        }
 
282
 
 
283
        if (m->pmatch != NULL)
 
284
                free((char *)m->pmatch);
 
285
        if (m->lastpos != NULL)
 
286
                free((char *)m->lastpos);
 
287
        STATETEARDOWN(m);
 
288
        return(0);
 
289
}
 
290
 
 
291
/*
 
292
 - dissect - figure out what matched what, no back references
 
293
 */
 
294
static const char *                     /* == stop (success) always */
 
295
dissect(struct match *m, const char *start, const char *stop, sopno startst,
 
296
        sopno stopst)
 
297
{
 
298
        int i;
 
299
        sopno ss;       /* start sop of current subRE */
 
300
        sopno es;       /* end sop of current subRE */
 
301
        const char *sp; /* start of string matched by it */
 
302
        const char *stp;        /* string matched by it cannot pass here */
 
303
        const char *rest;       /* start of rest of string */
 
304
        const char *tail;       /* string unmatched by rest of RE */
 
305
        sopno ssub;     /* start sop of subsubRE */
 
306
        sopno esub;     /* end sop of subsubRE */
 
307
        const char *ssp;        /* start of string matched by subsubRE */
 
308
        const char *sep;        /* end of string matched by subsubRE */
 
309
        const char *oldssp;     /* previous ssp */
 
310
 
 
311
        AT("diss", start, stop, startst, stopst);
 
312
        sp = start;
 
313
        for (ss = startst; ss < stopst; ss = es) {
 
314
                /* identify end of subRE */
 
315
                es = ss;
 
316
                switch (OP(m->g->strip[es])) {
 
317
                case OPLUS_:
 
318
                case OQUEST_:
 
319
                        es += OPND(m->g->strip[es]);
 
320
                        break;
 
321
                case OCH_:
 
322
                        while (OP(m->g->strip[es]) != O_CH)
 
323
                                es += OPND(m->g->strip[es]);
 
324
                        break;
 
325
                }
 
326
                es++;
 
327
 
 
328
                /* figure out what it matched */
 
329
                switch (OP(m->g->strip[ss])) {
 
330
                case OEND:
 
331
                        assert(nope);
 
332
                        break;
 
333
                case OCHAR:
 
334
                        sp++;
 
335
                        break;
 
336
                case OBOL:
 
337
                case OEOL:
 
338
                case OBOW:
 
339
                case OEOW:
 
340
                        break;
 
341
                case OANY:
 
342
                case OANYOF:
 
343
                        sp++;
 
344
                        break;
 
345
                case OBACK_:
 
346
                case O_BACK:
 
347
                        assert(nope);
 
348
                        break;
 
349
                /* cases where length of match is hard to find */
 
350
                case OQUEST_:
 
351
                        stp = stop;
 
352
                        for (;;) {
 
353
                                /* how long could this one be? */
 
354
                                rest = slow(m, sp, stp, ss, es);
 
355
                                assert(rest != NULL);   /* it did match */
 
356
                                /* could the rest match the rest? */
 
357
                                tail = slow(m, rest, stop, es, stopst);
 
358
                                if (tail == stop)
 
359
                                        break;          /* yes! */
 
360
                                /* no -- try a shorter match for this one */
 
361
                                stp = rest - 1;
 
362
                                assert(stp >= sp);      /* it did work */
 
363
                        }
 
364
                        ssub = ss + 1;
 
365
                        esub = es - 1;
 
366
                        /* did innards match? */
 
367
                        if (slow(m, sp, rest, ssub, esub) != NULL) {
 
368
                                const char *dp = dissect(m, sp, rest, ssub, esub);
 
369
                                (void)dp; /* avoid warning if assertions off */
 
370
                                assert(dp == rest);
 
371
                        } else          /* no */
 
372
                                assert(sp == rest);
 
373
                        sp = rest;
 
374
                        break;
 
375
                case OPLUS_:
 
376
                        stp = stop;
 
377
                        for (;;) {
 
378
                                /* how long could this one be? */
 
379
                                rest = slow(m, sp, stp, ss, es);
 
380
                                assert(rest != NULL);   /* it did match */
 
381
                                /* could the rest match the rest? */
 
382
                                tail = slow(m, rest, stop, es, stopst);
 
383
                                if (tail == stop)
 
384
                                        break;          /* yes! */
 
385
                                /* no -- try a shorter match for this one */
 
386
                                stp = rest - 1;
 
387
                                assert(stp >= sp);      /* it did work */
 
388
                        }
 
389
                        ssub = ss + 1;
 
390
                        esub = es - 1;
 
391
                        ssp = sp;
 
392
                        oldssp = ssp;
 
393
                        for (;;) {      /* find last match of innards */
 
394
                                sep = slow(m, ssp, rest, ssub, esub);
 
395
                                if (sep == NULL || sep == ssp)
 
396
                                        break;  /* failed or matched null */
 
397
                                oldssp = ssp;   /* on to next try */
 
398
                                ssp = sep;
 
399
                        }
 
400
                        if (sep == NULL) {
 
401
                                /* last successful match */
 
402
                                sep = ssp;
 
403
                                ssp = oldssp;
 
404
                        }
 
405
                        assert(sep == rest);    /* must exhaust substring */
 
406
                        assert(slow(m, ssp, sep, ssub, esub) == rest);
 
407
                        {
 
408
                                const char *dp = dissect(m, ssp, sep, ssub, esub);
 
409
                                (void)dp; /* avoid warning if assertions off */
 
410
                                assert(dp == sep);
 
411
                        }
 
412
                        sp = rest;
 
413
                        break;
 
414
                case OCH_:
 
415
                        stp = stop;
 
416
                        for (;;) {
 
417
                                /* how long could this one be? */
 
418
                                rest = slow(m, sp, stp, ss, es);
 
419
                                assert(rest != NULL);   /* it did match */
 
420
                                /* could the rest match the rest? */
 
421
                                tail = slow(m, rest, stop, es, stopst);
 
422
                                if (tail == stop)
 
423
                                        break;          /* yes! */
 
424
                                /* no -- try a shorter match for this one */
 
425
                                stp = rest - 1;
 
426
                                assert(stp >= sp);      /* it did work */
 
427
                        }
 
428
                        ssub = ss + 1;
 
429
                        esub = ss + OPND(m->g->strip[ss]) - 1;
 
430
                        assert(OP(m->g->strip[esub]) == OOR1);
 
431
                        for (;;) {      /* find first matching branch */
 
432
                                if (slow(m, sp, rest, ssub, esub) == rest)
 
433
                                        break;  /* it matched all of it */
 
434
                                /* that one missed, try next one */
 
435
                                assert(OP(m->g->strip[esub]) == OOR1);
 
436
                                esub++;
 
437
                                assert(OP(m->g->strip[esub]) == OOR2);
 
438
                                ssub = esub + 1;
 
439
                                esub += OPND(m->g->strip[esub]);
 
440
                                if (OP(m->g->strip[esub]) == OOR2)
 
441
                                        esub--;
 
442
                                else
 
443
                                        assert(OP(m->g->strip[esub]) == O_CH);
 
444
                        }
 
445
                        {
 
446
                                const char *dp = dissect(m, sp, rest, ssub, esub);
 
447
                                (void)dp; /* avoid warning if assertions off */
 
448
                                assert(dp == rest);
 
449
                        }
 
450
                        sp = rest;
 
451
                        break;
 
452
                case O_PLUS:
 
453
                case O_QUEST:
 
454
                case OOR1:
 
455
                case OOR2:
 
456
                case O_CH:
 
457
                        assert(nope);
 
458
                        break;
 
459
                case OLPAREN:
 
460
                        i = OPND(m->g->strip[ss]);
 
461
                        assert(0 < i && i <= m->g->nsub);
 
462
                        m->pmatch[i].rm_so = sp - m->offp;
 
463
                        break;
 
464
                case ORPAREN:
 
465
                        i = OPND(m->g->strip[ss]);
 
466
                        assert(0 < i && i <= m->g->nsub);
 
467
                        m->pmatch[i].rm_eo = sp - m->offp;
 
468
                        break;
 
469
                default:                /* uh oh */
 
470
                        assert(nope);
 
471
                        break;
 
472
                }
 
473
        }
 
474
 
 
475
        assert(sp == stop);
 
476
        return(sp);
 
477
}
 
478
 
 
479
/*
 
480
 - backref - figure out what matched what, figuring in back references
 
481
 */
 
482
static const char *                     /* == stop (success) or NULL (failure) */
 
483
backref(struct match *m, const char *start, const char *stop, sopno startst,
 
484
        sopno stopst, sopno lev, int rec)                       /* PLUS nesting level */
 
485
{
 
486
        int i;
 
487
        sopno ss;       /* start sop of current subRE */
 
488
        const char *sp; /* start of string matched by it */
 
489
        sopno ssub;     /* start sop of subsubRE */
 
490
        sopno esub;     /* end sop of subsubRE */
 
491
        const char *ssp;        /* start of string matched by subsubRE */
 
492
        const char *dp;
 
493
        size_t len;
 
494
        int hard;
 
495
        sop s;
 
496
        llvm_regoff_t offsave;
 
497
        cset *cs;
 
498
 
 
499
        AT("back", start, stop, startst, stopst);
 
500
        sp = start;
 
501
 
 
502
        /* get as far as we can with easy stuff */
 
503
        hard = 0;
 
504
        for (ss = startst; !hard && ss < stopst; ss++)
 
505
                switch (OP(s = m->g->strip[ss])) {
 
506
                case OCHAR:
 
507
                        if (sp == stop || *sp++ != (char)OPND(s))
 
508
                                return(NULL);
 
509
                        break;
 
510
                case OANY:
 
511
                        if (sp == stop)
 
512
                                return(NULL);
 
513
                        sp++;
 
514
                        break;
 
515
                case OANYOF:
 
516
                        cs = &m->g->sets[OPND(s)];
 
517
                        if (sp == stop || !CHIN(cs, *sp++))
 
518
                                return(NULL);
 
519
                        break;
 
520
                case OBOL:
 
521
                        if ( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
 
522
                                        (sp < m->endp && *(sp-1) == '\n' &&
 
523
                                                (m->g->cflags&REG_NEWLINE)) )
 
524
                                { /* yes */ }
 
525
                        else
 
526
                                return(NULL);
 
527
                        break;
 
528
                case OEOL:
 
529
                        if ( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
 
530
                                        (sp < m->endp && *sp == '\n' &&
 
531
                                                (m->g->cflags&REG_NEWLINE)) )
 
532
                                { /* yes */ }
 
533
                        else
 
534
                                return(NULL);
 
535
                        break;
 
536
                case OBOW:
 
537
                        if (( (sp == m->beginp && !(m->eflags&REG_NOTBOL)) ||
 
538
                                        (sp < m->endp && *(sp-1) == '\n' &&
 
539
                                                (m->g->cflags&REG_NEWLINE)) ||
 
540
                                        (sp > m->beginp &&
 
541
                                                        !ISWORD(*(sp-1))) ) &&
 
542
                                        (sp < m->endp && ISWORD(*sp)) )
 
543
                                { /* yes */ }
 
544
                        else
 
545
                                return(NULL);
 
546
                        break;
 
547
                case OEOW:
 
548
                        if (( (sp == m->endp && !(m->eflags&REG_NOTEOL)) ||
 
549
                                        (sp < m->endp && *sp == '\n' &&
 
550
                                                (m->g->cflags&REG_NEWLINE)) ||
 
551
                                        (sp < m->endp && !ISWORD(*sp)) ) &&
 
552
                                        (sp > m->beginp && ISWORD(*(sp-1))) )
 
553
                                { /* yes */ }
 
554
                        else
 
555
                                return(NULL);
 
556
                        break;
 
557
                case O_QUEST:
 
558
                        break;
 
559
                case OOR1:      /* matches null but needs to skip */
 
560
                        ss++;
 
561
                        s = m->g->strip[ss];
 
562
                        do {
 
563
                                assert(OP(s) == OOR2);
 
564
                                ss += OPND(s);
 
565
                        } while (OP(s = m->g->strip[ss]) != O_CH);
 
566
                        /* note that the ss++ gets us past the O_CH */
 
567
                        break;
 
568
                default:        /* have to make a choice */
 
569
                        hard = 1;
 
570
                        break;
 
571
                }
 
572
        if (!hard) {            /* that was it! */
 
573
                if (sp != stop)
 
574
                        return(NULL);
 
575
                return(sp);
 
576
        }
 
577
        ss--;                   /* adjust for the for's final increment */
 
578
 
 
579
        /* the hard stuff */
 
580
        AT("hard", sp, stop, ss, stopst);
 
581
        s = m->g->strip[ss];
 
582
        switch (OP(s)) {
 
583
        case OBACK_:            /* the vilest depths */
 
584
                i = OPND(s);
 
585
                assert(0 < i && i <= m->g->nsub);
 
586
                if (m->pmatch[i].rm_eo == -1)
 
587
                        return(NULL);
 
588
                assert(m->pmatch[i].rm_so != -1);
 
589
                len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
 
590
                if (len == 0 && rec++ > MAX_RECURSION)
 
591
                        return(NULL);
 
592
                assert(stop - m->beginp >= len);
 
593
                if (sp > stop - len)
 
594
                        return(NULL);   /* not enough left to match */
 
595
                ssp = m->offp + m->pmatch[i].rm_so;
 
596
                if (memcmp(sp, ssp, len) != 0)
 
597
                        return(NULL);
 
598
                while (m->g->strip[ss] != SOP(O_BACK, i))
 
599
                        ss++;
 
600
                return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));
 
601
                break;
 
602
        case OQUEST_:           /* to null or not */
 
603
                dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 
604
                if (dp != NULL)
 
605
                        return(dp);     /* not */
 
606
                return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec));
 
607
                break;
 
608
        case OPLUS_:
 
609
                assert(m->lastpos != NULL);
 
610
                assert(lev+1 <= m->g->nplus);
 
611
                m->lastpos[lev+1] = sp;
 
612
                return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));
 
613
                break;
 
614
        case O_PLUS:
 
615
                if (sp == m->lastpos[lev])      /* last pass matched null */
 
616
                        return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 
617
                /* try another pass */
 
618
                m->lastpos[lev] = sp;
 
619
                dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec);
 
620
                if (dp == NULL)
 
621
                        return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
 
622
                else
 
623
                        return(dp);
 
624
                break;
 
625
        case OCH_:              /* find the right one, if any */
 
626
                ssub = ss + 1;
 
627
                esub = ss + OPND(s) - 1;
 
628
                assert(OP(m->g->strip[esub]) == OOR1);
 
629
                for (;;) {      /* find first matching branch */
 
630
                        dp = backref(m, sp, stop, ssub, esub, lev, rec);
 
631
                        if (dp != NULL)
 
632
                                return(dp);
 
633
                        /* that one missed, try next one */
 
634
                        if (OP(m->g->strip[esub]) == O_CH)
 
635
                                return(NULL);   /* there is none */
 
636
                        esub++;
 
637
                        assert(OP(m->g->strip[esub]) == OOR2);
 
638
                        ssub = esub + 1;
 
639
                        esub += OPND(m->g->strip[esub]);
 
640
                        if (OP(m->g->strip[esub]) == OOR2)
 
641
                                esub--;
 
642
                        else
 
643
                                assert(OP(m->g->strip[esub]) == O_CH);
 
644
                }
 
645
                break;
 
646
        case OLPAREN:           /* must undo assignment if rest fails */
 
647
                i = OPND(s);
 
648
                assert(0 < i && i <= m->g->nsub);
 
649
                offsave = m->pmatch[i].rm_so;
 
650
                m->pmatch[i].rm_so = sp - m->offp;
 
651
                dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 
652
                if (dp != NULL)
 
653
                        return(dp);
 
654
                m->pmatch[i].rm_so = offsave;
 
655
                return(NULL);
 
656
                break;
 
657
        case ORPAREN:           /* must undo assignment if rest fails */
 
658
                i = OPND(s);
 
659
                assert(0 < i && i <= m->g->nsub);
 
660
                offsave = m->pmatch[i].rm_eo;
 
661
                m->pmatch[i].rm_eo = sp - m->offp;
 
662
                dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
 
663
                if (dp != NULL)
 
664
                        return(dp);
 
665
                m->pmatch[i].rm_eo = offsave;
 
666
                return(NULL);
 
667
                break;
 
668
        default:                /* uh oh */
 
669
                assert(nope);
 
670
                break;
 
671
        }
 
672
 
 
673
        /* "can't happen" */
 
674
        assert(nope);
 
675
        /* NOTREACHED */
 
676
        return NULL;
 
677
}
 
678
 
 
679
/*
 
680
 - fast - step through the string at top speed
 
681
 */
 
682
static const char *                     /* where tentative match ended, or NULL */
 
683
fast(struct match *m, const char *start, const char *stop, sopno startst,
 
684
     sopno stopst)
 
685
{
 
686
        states st = m->st;
 
687
        states fresh = m->fresh;
 
688
        states tmp = m->tmp;
 
689
        const char *p = start;
 
690
        int c = (start == m->beginp) ? OUT : *(start-1);
 
691
        int lastc;      /* previous c */
 
692
        int flagch;
 
693
        int i;
 
694
        const char *coldp;      /* last p after which no match was underway */
 
695
 
 
696
        CLEAR(st);
 
697
        SET1(st, startst);
 
698
        st = step(m->g, startst, stopst, st, NOTHING, st);
 
699
        ASSIGN(fresh, st);
 
700
        SP("start", st, *p);
 
701
        coldp = NULL;
 
702
        for (;;) {
 
703
                /* next character */
 
704
                lastc = c;
 
705
                c = (p == m->endp) ? OUT : *p;
 
706
                if (EQ(st, fresh))
 
707
                        coldp = p;
 
708
 
 
709
                /* is there an EOL and/or BOL between lastc and c? */
 
710
                flagch = '\0';
 
711
                i = 0;
 
712
                if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
 
713
                                (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
 
714
                        flagch = BOL;
 
715
                        i = m->g->nbol;
 
716
                }
 
717
                if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
 
718
                                (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
 
719
                        flagch = (flagch == BOL) ? BOLEOL : EOL;
 
720
                        i += m->g->neol;
 
721
                }
 
722
                if (i != 0) {
 
723
                        for (; i > 0; i--)
 
724
                                st = step(m->g, startst, stopst, st, flagch, st);
 
725
                        SP("boleol", st, c);
 
726
                }
 
727
 
 
728
                /* how about a word boundary? */
 
729
                if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
 
730
                                        (c != OUT && ISWORD(c)) ) {
 
731
                        flagch = BOW;
 
732
                }
 
733
                if ( (lastc != OUT && ISWORD(lastc)) &&
 
734
                                (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
 
735
                        flagch = EOW;
 
736
                }
 
737
                if (flagch == BOW || flagch == EOW) {
 
738
                        st = step(m->g, startst, stopst, st, flagch, st);
 
739
                        SP("boweow", st, c);
 
740
                }
 
741
 
 
742
                /* are we done? */
 
743
                if (ISSET(st, stopst) || p == stop)
 
744
                        break;          /* NOTE BREAK OUT */
 
745
 
 
746
                /* no, we must deal with this character */
 
747
                ASSIGN(tmp, st);
 
748
                ASSIGN(st, fresh);
 
749
                assert(c != OUT);
 
750
                st = step(m->g, startst, stopst, tmp, c, st);
 
751
                SP("aft", st, c);
 
752
                assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
 
753
                p++;
 
754
        }
 
755
 
 
756
        assert(coldp != NULL);
 
757
        m->coldp = coldp;
 
758
        if (ISSET(st, stopst))
 
759
                return(p+1);
 
760
        else
 
761
                return(NULL);
 
762
}
 
763
 
 
764
/*
 
765
 - slow - step through the string more deliberately
 
766
 */
 
767
static const char *                     /* where it ended */
 
768
slow(struct match *m, const char *start, const char *stop, sopno startst,
 
769
     sopno stopst)
 
770
{
 
771
        states st = m->st;
 
772
        states empty = m->empty;
 
773
        states tmp = m->tmp;
 
774
        const char *p = start;
 
775
        int c = (start == m->beginp) ? OUT : *(start-1);
 
776
        int lastc;      /* previous c */
 
777
        int flagch;
 
778
        int i;
 
779
        const char *matchp;     /* last p at which a match ended */
 
780
 
 
781
        AT("slow", start, stop, startst, stopst);
 
782
        CLEAR(st);
 
783
        SET1(st, startst);
 
784
        SP("sstart", st, *p);
 
785
        st = step(m->g, startst, stopst, st, NOTHING, st);
 
786
        matchp = NULL;
 
787
        for (;;) {
 
788
                /* next character */
 
789
                lastc = c;
 
790
                c = (p == m->endp) ? OUT : *p;
 
791
 
 
792
                /* is there an EOL and/or BOL between lastc and c? */
 
793
                flagch = '\0';
 
794
                i = 0;
 
795
                if ( (lastc == '\n' && m->g->cflags&REG_NEWLINE) ||
 
796
                                (lastc == OUT && !(m->eflags&REG_NOTBOL)) ) {
 
797
                        flagch = BOL;
 
798
                        i = m->g->nbol;
 
799
                }
 
800
                if ( (c == '\n' && m->g->cflags&REG_NEWLINE) ||
 
801
                                (c == OUT && !(m->eflags&REG_NOTEOL)) ) {
 
802
                        flagch = (flagch == BOL) ? BOLEOL : EOL;
 
803
                        i += m->g->neol;
 
804
                }
 
805
                if (i != 0) {
 
806
                        for (; i > 0; i--)
 
807
                                st = step(m->g, startst, stopst, st, flagch, st);
 
808
                        SP("sboleol", st, c);
 
809
                }
 
810
 
 
811
                /* how about a word boundary? */
 
812
                if ( (flagch == BOL || (lastc != OUT && !ISWORD(lastc))) &&
 
813
                                        (c != OUT && ISWORD(c)) ) {
 
814
                        flagch = BOW;
 
815
                }
 
816
                if ( (lastc != OUT && ISWORD(lastc)) &&
 
817
                                (flagch == EOL || (c != OUT && !ISWORD(c))) ) {
 
818
                        flagch = EOW;
 
819
                }
 
820
                if (flagch == BOW || flagch == EOW) {
 
821
                        st = step(m->g, startst, stopst, st, flagch, st);
 
822
                        SP("sboweow", st, c);
 
823
                }
 
824
 
 
825
                /* are we done? */
 
826
                if (ISSET(st, stopst))
 
827
                        matchp = p;
 
828
                if (EQ(st, empty) || p == stop)
 
829
                        break;          /* NOTE BREAK OUT */
 
830
 
 
831
                /* no, we must deal with this character */
 
832
                ASSIGN(tmp, st);
 
833
                ASSIGN(st, empty);
 
834
                assert(c != OUT);
 
835
                st = step(m->g, startst, stopst, tmp, c, st);
 
836
                SP("saft", st, c);
 
837
                assert(EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
 
838
                p++;
 
839
        }
 
840
 
 
841
        return(matchp);
 
842
}
 
843
 
 
844
 
 
845
/*
 
846
 - step - map set of states reachable before char to set reachable after
 
847
 */
 
848
static states
 
849
step(struct re_guts *g,
 
850
    sopno start,                /* start state within strip */
 
851
    sopno stop,                 /* state after stop state within strip */
 
852
    states bef,                 /* states reachable before */
 
853
    int ch,                     /* character or NONCHAR code */
 
854
    states aft)                 /* states already known reachable after */
 
855
{
 
856
        cset *cs;
 
857
        sop s;
 
858
        sopno pc;
 
859
        onestate here;          /* note, macros know this name */
 
860
        sopno look;
 
861
        int i;
 
862
 
 
863
        for (pc = start, INIT(here, pc); pc != stop; pc++, INC(here)) {
 
864
                s = g->strip[pc];
 
865
                switch (OP(s)) {
 
866
                case OEND:
 
867
                        assert(pc == stop-1);
 
868
                        break;
 
869
                case OCHAR:
 
870
                        /* only characters can match */
 
871
                        assert(!NONCHAR(ch) || ch != (char)OPND(s));
 
872
                        if (ch == (char)OPND(s))
 
873
                                FWD(aft, bef, 1);
 
874
                        break;
 
875
                case OBOL:
 
876
                        if (ch == BOL || ch == BOLEOL)
 
877
                                FWD(aft, bef, 1);
 
878
                        break;
 
879
                case OEOL:
 
880
                        if (ch == EOL || ch == BOLEOL)
 
881
                                FWD(aft, bef, 1);
 
882
                        break;
 
883
                case OBOW:
 
884
                        if (ch == BOW)
 
885
                                FWD(aft, bef, 1);
 
886
                        break;
 
887
                case OEOW:
 
888
                        if (ch == EOW)
 
889
                                FWD(aft, bef, 1);
 
890
                        break;
 
891
                case OANY:
 
892
                        if (!NONCHAR(ch))
 
893
                                FWD(aft, bef, 1);
 
894
                        break;
 
895
                case OANYOF:
 
896
                        cs = &g->sets[OPND(s)];
 
897
                        if (!NONCHAR(ch) && CHIN(cs, ch))
 
898
                                FWD(aft, bef, 1);
 
899
                        break;
 
900
                case OBACK_:            /* ignored here */
 
901
                case O_BACK:
 
902
                        FWD(aft, aft, 1);
 
903
                        break;
 
904
                case OPLUS_:            /* forward, this is just an empty */
 
905
                        FWD(aft, aft, 1);
 
906
                        break;
 
907
                case O_PLUS:            /* both forward and back */
 
908
                        FWD(aft, aft, 1);
 
909
                        i = ISSETBACK(aft, OPND(s));
 
910
                        BACK(aft, aft, OPND(s));
 
911
                        if (!i && ISSETBACK(aft, OPND(s))) {
 
912
                                /* oho, must reconsider loop body */
 
913
                                pc -= OPND(s) + 1;
 
914
                                INIT(here, pc);
 
915
                        }
 
916
                        break;
 
917
                case OQUEST_:           /* two branches, both forward */
 
918
                        FWD(aft, aft, 1);
 
919
                        FWD(aft, aft, OPND(s));
 
920
                        break;
 
921
                case O_QUEST:           /* just an empty */
 
922
                        FWD(aft, aft, 1);
 
923
                        break;
 
924
                case OLPAREN:           /* not significant here */
 
925
                case ORPAREN:
 
926
                        FWD(aft, aft, 1);
 
927
                        break;
 
928
                case OCH_:              /* mark the first two branches */
 
929
                        FWD(aft, aft, 1);
 
930
                        assert(OP(g->strip[pc+OPND(s)]) == OOR2);
 
931
                        FWD(aft, aft, OPND(s));
 
932
                        break;
 
933
                case OOR1:              /* done a branch, find the O_CH */
 
934
                        if (ISSTATEIN(aft, here)) {
 
935
                                for (look = 1;
 
936
                                                OP(s = g->strip[pc+look]) != O_CH;
 
937
                                                look += OPND(s))
 
938
                                        assert(OP(s) == OOR2);
 
939
                                FWD(aft, aft, look);
 
940
                        }
 
941
                        break;
 
942
                case OOR2:              /* propagate OCH_'s marking */
 
943
                        FWD(aft, aft, 1);
 
944
                        if (OP(g->strip[pc+OPND(s)]) != O_CH) {
 
945
                                assert(OP(g->strip[pc+OPND(s)]) == OOR2);
 
946
                                FWD(aft, aft, OPND(s));
 
947
                        }
 
948
                        break;
 
949
                case O_CH:              /* just empty */
 
950
                        FWD(aft, aft, 1);
 
951
                        break;
 
952
                default:                /* ooooops... */
 
953
                        assert(nope);
 
954
                        break;
 
955
                }
 
956
        }
 
957
 
 
958
        return(aft);
 
959
}
 
960
 
 
961
#ifdef REDEBUG
 
962
/*
 
963
 - print - print a set of states
 
964
 */
 
965
static void
 
966
print(struct match *m, char *caption, states st, int ch, FILE *d)
 
967
{
 
968
        struct re_guts *g = m->g;
 
969
        int i;
 
970
        int first = 1;
 
971
 
 
972
        if (!(m->eflags&REG_TRACE))
 
973
                return;
 
974
 
 
975
        (void)fprintf(d, "%s", caption);
 
976
        if (ch != '\0')
 
977
                (void)fprintf(d, " %s", pchar(ch));
 
978
        for (i = 0; i < g->nstates; i++)
 
979
                if (ISSET(st, i)) {
 
980
                        (void)fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
 
981
                        first = 0;
 
982
                }
 
983
        (void)fprintf(d, "\n");
 
984
}
 
985
 
 
986
/* 
 
987
 - at - print current situation
 
988
 */
 
989
static void
 
990
at(struct match *m, char *title, char *start, char *stop, sopno startst,
 
991
    sopno stopst)
 
992
{
 
993
        if (!(m->eflags&REG_TRACE))
 
994
                return;
 
995
 
 
996
        (void)printf("%s %s-", title, pchar(*start));
 
997
        (void)printf("%s ", pchar(*stop));
 
998
        (void)printf("%ld-%ld\n", (long)startst, (long)stopst);
 
999
}
 
1000
 
 
1001
#ifndef PCHARDONE
 
1002
#define PCHARDONE       /* never again */
 
1003
/*
 
1004
 - pchar - make a character printable
 
1005
 *
 
1006
 * Is this identical to regchar() over in debug.c?  Well, yes.  But a
 
1007
 * duplicate here avoids having a debugging-capable regexec.o tied to
 
1008
 * a matching debug.o, and this is convenient.  It all disappears in
 
1009
 * the non-debug compilation anyway, so it doesn't matter much.
 
1010
 */
 
1011
static char *                   /* -> representation */
 
1012
pchar(int ch)
 
1013
{
 
1014
        static char pbuf[10];
 
1015
 
 
1016
        if (isprint(ch) || ch == ' ')
 
1017
                (void)snprintf(pbuf, sizeof pbuf, "%c", ch);
 
1018
        else
 
1019
                (void)snprintf(pbuf, sizeof pbuf, "\\%o", ch);
 
1020
        return(pbuf);
 
1021
}
 
1022
#endif
 
1023
#endif
 
1024
 
 
1025
#undef  matcher
 
1026
#undef  fast
 
1027
#undef  slow
 
1028
#undef  dissect
 
1029
#undef  backref
 
1030
#undef  step
 
1031
#undef  print
 
1032
#undef  at
 
1033
#undef  match
 
1034
#undef  nope