← Back to branch summary

~ubuntu-branches/ubuntu/hoary/cdrtools/hoary

« back to all changes in this revision

Viewing changes to lib/match.c

  • Committer: Bazaar Package Importer
  • Author(s): Eduard Bloch
  • Date: 2002-04-09 10:03:06 UTC
  • Revision ID: james.westby@ubuntu.com-20020409100306-t4hagiv7gm0fhggv
Tags: upstream-1.10
Import upstream version 1.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/match.c
 
1
/* @(#)match.c  1.18 00/11/12 Copyright 1985 J. Schilling */
 
2
#include <standard.h>
 
3
#include <patmatch.h>
 
4
/*
 
5
 *      Pattern matching functions
 
6
 *
 
7
 *      Copyright (c) 1985,1995 J. Schilling
 
8
 */
 
9
/*
 
10
 * This program is free software; you can redistribute it and/or modify
 
11
 * it under the terms of the GNU General Public License as published by
 
12
 * the Free Software Foundation; either version 2, or (at your option)
 
13
 * any later version.
 
14
 *
 
15
 * This program is distributed in the hope that it will be useful,
 
16
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
17
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
18
 * GNU General Public License for more details.
 
19
 *
 
20
 * You should have received a copy of the GNU General Public License
 
21
 * along with this program; see the file COPYING.  If not, write to
 
22
 * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 
23
 */
 
24
/*
 
25
 *      The pattern matching functions below are based on the algorithm
 
26
 *      presented by Martin Richards in:
 
27
 *
 
28
 *      "A Compact Function for Regular Expression Pattern Matching", 
 
29
 *      Software-Practice and Experience, Vol. 9, 527-534 (1979)
 
30
 *
 
31
 *      Several changes have been made to the original source which has been
 
32
 *      written in BCPL:
 
33
 *
 
34
 *      '/'     is replaced by  '!'             (to allow UNIX filenames)
 
35
 *      '(',')' are replaced by '{', '}'
 
36
 *      '\''    is replaced by  '\\'            (UNIX compatible quote)
 
37
 *
 
38
 *      Character classes have been added to allow "[<character list>]"
 
39
 *      to be used.
 
40
 *      Start of line '^' and end of line '$' have been added.
 
41
 */
 
42
 
 
43
#ifdef  __LINE_MATCH
 
44
#define opatmatch       opatlmatch
 
45
#define patmatch        patlmatch
 
46
#endif
 
47
 
 
48
#define ENDSTATE        (-1)
 
49
typedef unsigned char   Uchar;
 
50
 
 
51
/*---------------------------------------------------------------------------
 
52
|
 
53
|       The Interpreter
 
54
|
 
55
+---------------------------------------------------------------------------*/
 
56
 
 
57
 
 
58
/*
 
59
 *      put adds a new state to the active list
 
60
 */
 
61
#define put(ret, state, sp, n)  {               \
 
62
        register int *lstate    = state;        \
 
63
        register int *lsp       = sp;           \
 
64
        register int ln         = n;            \
 
65
                                                \
 
66
        while (lstate < lsp) {                  \
 
67
                if (*lstate++ == ln) {          \
 
68
                        ret = lsp;              \
 
69
                        lsp = 0;                \
 
70
                        break;                  \
 
71
                }                               \
 
72
        }                                       \
 
73
        if (lsp) {                              \
 
74
                *lstate++ = ln;                 \
 
75
                ret = lstate;                   \
 
76
        }                                       \
 
77
}
 
78
 
 
79
 
 
80
/*
 
81
 *      match a character in class
 
82
 */
 
83
#define in_class(found, pat, c) {                       \
 
84
        register const Uchar    *lpat   = pat;          \
 
85
        register int            lc      = c;            \
 
86
        int     lo_bound;                               \
 
87
        int     hi_bound;                               \
 
88
                                                        \
 
89
        found = FALSE;                                  \
 
90
                                                        \
 
91
        if (*lpat == NOT) {                             \
 
92
                lpat++;                                 \
 
93
                found = TRUE;                           \
 
94
        }                                               \
 
95
        while (*lpat != RCLASS) {                       \
 
96
                if (*lpat == QUOTE)                     \
 
97
                        lpat++;                         \
 
98
                lo_bound = *lpat++;                     \
 
99
                if (*lpat == RANGE) {                   \
 
100
                        lpat++;                         \
 
101
                        if (*lpat == QUOTE)             \
 
102
                                lpat++;                 \
 
103
                        hi_bound = *lpat++;             \
 
104
                } else {                                \
 
105
                        hi_bound = lo_bound;            \
 
106
                }                                       \
 
107
                if (lo_bound <= lc && lc <= hi_bound) { \
 
108
                        found = !found;                 \
 
109
                        break;                          \
 
110
                }                                       \
 
111
        }                                               \
 
112
}
 
113
 
 
114
/*
 
115
 *      opatmatch - the old external interpreter interface.
 
116
 *
 
117
 *      Trys to match a string beginning at offset
 
118
 *      against the compiled pattern.
 
119
 */
 
120
Uchar *opatmatch(pat, aux, str, soff, slen, alt)
 
121
        const Uchar     *pat;
 
122
        const int       *aux;
 
123
        const Uchar     *str;
 
124
        int             soff;
 
125
        int             slen;
 
126
        int             alt;
 
127
{
 
128
        int             state[MAXPAT];
 
129
 
 
130
        return (patmatch(pat, aux, str, soff, slen, alt, state));
 
131
}
 
132
 
 
133
/*
 
134
 *      patmatch - the external interpreter interface.
 
135
 *
 
136
 *      Trys to match a string beginning at offset
 
137
 *      against the compiled pattern.
 
138
 */
 
139
Uchar *patmatch(pat, aux, str, soff, slen, alt, state)
 
140
        const Uchar     *pat;
 
141
        const int       *aux;
 
142
        const Uchar     *str;
 
143
        int             soff;
 
144
        int             slen;
 
145
        int             alt;
 
146
        int             state[];
 
147
{
 
148
        register int    *sp;
 
149
        register int    *n;
 
150
        register int    *i;
 
151
        register int    p;
 
152
        register int    q, s, k;
 
153
        int             c;
 
154
        const Uchar     *lastp = (Uchar *)NULL;
 
155
 
 
156
#ifdef  __LINE_MATCH
 
157
for( ;soff <= slen; soff++) {
 
158
#endif
 
159
 
 
160
        sp = state;
 
161
        put(sp, state, state, 0);
 
162
        if (alt != ENDSTATE)
 
163
                put(sp, state, sp, alt);
 
164
 
 
165
        for(s = soff; ; s++) {
 
166
                /*
 
167
                 * next char from input string
 
168
                 */
 
169
                if (s >= slen)
 
170
                        c = 0;
 
171
                else
 
172
                        c = str[s];
 
173
                /*
 
174
                 * first complete the closure
 
175
                 */
 
176
                for(n = state; n < sp;) {
 
177
                        p = *n++;               /* next state number */
 
178
                        if (p == ENDSTATE)
 
179
                                continue;
 
180
                        q = aux[p];             /* get next state for pat */
 
181
                        k = pat[p];             /* get next char from pat */
 
182
                        switch (k) {
 
183
 
 
184
                        case REP:
 
185
                                put(sp, state, sp, p+1);
 
186
                        case NIL:               /* NIL matches always */
 
187
                        case STAR:
 
188
                                put(sp, state, sp, q);
 
189
                                break;
 
190
                        case LBRACK:            /* alternations */
 
191
                        case ALT:
 
192
                                put(sp, state, sp, p+1);
 
193
                                if (q != ENDSTATE)
 
194
                                        put(sp, state, sp, q);
 
195
                                break;
 
196
                        case START:
 
197
                                if (s == 0)
 
198
                                        put(sp, state, sp, q);
 
199
                                break;
 
200
                        case END:
 
201
                                if (c == '\0')
 
202
                                        put(sp, state, sp, q);
 
203
                                break;
 
204
                        }
 
205
                }
 
206
 
 
207
                for (i = state; i < sp;) {
 
208
                        if (*i++ == ENDSTATE) {
 
209
                                lastp = &str[s];
 
210
                                break;
 
211
                        }
 
212
                }
 
213
                if (c == 0)
 
214
                        return ((Uchar *)lastp);
 
215
 
 
216
                /*
 
217
                 * now try to match next character
 
218
                 */
 
219
                n = sp;
 
220
                sp = state;
 
221
                for(i = sp; i < n;) {
 
222
                        p = *i++;               /* next active state number */
 
223
                        if (p == ENDSTATE)
 
224
                                continue;
 
225
                        k = pat[p];
 
226
                        switch (k) {
 
227
 
 
228
                        case ALT:
 
229
                        case REP:
 
230
                        case NIL:
 
231
                        case LBRACK:
 
232
                        case START:
 
233
                        case END:
 
234
                                continue;
 
235
                        case LCLASS:
 
236
                                in_class(q, &pat[p+1], c);
 
237
                                if (!q)
 
238
                                        continue;
 
239
                                break;
 
240
                        case STAR:
 
241
                                put(sp, state, sp, p);
 
242
                                continue;
 
243
                        case QUOTE:
 
244
                                k = pat[p+1];
 
245
                        default:
 
246
                                if (k != c)
 
247
                                        continue;
 
248
                        case ANY:
 
249
                                break;
 
250
                        }
 
251
                        put(sp, state, sp, aux[p]);
 
252
                }
 
253
                if (sp == state) {              /* if no new states return */
 
254
#ifdef  __LINE_MATCH
 
255
 
 
256
                        if (lastp || (soff == slen - 1))
 
257
                                return ((Uchar *)lastp);
 
258
                        else
 
259
                                break;
 
260
#else
 
261
                        return ((Uchar *)lastp);
 
262
#endif
 
263
                }
 
264
        }
 
265
#ifdef  __LINE_MATCH
 
266
   }
 
267
   return ((Uchar *)lastp);
 
268
#endif
 
269
}
 
270
 
 
271
 
 
272
#ifndef __LINE_MATCH
 
273
/*---------------------------------------------------------------------------
 
274
|
 
275
|       The Compiler
 
276
|
 
277
+---------------------------------------------------------------------------*/
 
278
 
 
279
typedef struct args {
 
280
        const Uchar     *pattern;
 
281
        int             *aux;
 
282
        int             patp;
 
283
        int             length;
 
284
        Uchar           Ch;
 
285
} arg_t;
 
286
 
 
287
static  void    nextitem __PR((arg_t *));
 
288
static  int     prim     __PR((arg_t *));
 
289
static  int     exp      __PR((arg_t *, int *));
 
290
static  void    setexits __PR((int *, int, int));
 
291
static  int     join     __PR((int *, int, int));
 
292
        
 
293
/*
 
294
 *      'read' the next character from pattern
 
295
 */
 
296
#define rch(ap)                                         \
 
297
{                                                       \
 
298
        if (++(ap)->patp >= (ap)->length)               \
 
299
                (ap)->Ch = 0;                           \
 
300
        else                                            \
 
301
                (ap)->Ch = (ap)->pattern[(ap)->patp];   \
 
302
}
 
303
 
 
304
/*
 
305
 *      get the next item from pattern
 
306
 */
 
307
static void nextitem(ap)
 
308
        arg_t   *ap;
 
309
{
 
310
        if (ap->Ch == QUOTE)
 
311
                rch(ap);
 
312
        rch(ap);
 
313
}
 
314
 
 
315
/*
 
316
 *      parse a primary
 
317
 */
 
318
static int prim(ap)
 
319
        arg_t   *ap;
 
320
{
 
321
        int     a  = ap->patp;
 
322
        int     op = ap->Ch;
 
323
        int     t;
 
324
 
 
325
        nextitem(ap);
 
326
        switch (op) {
 
327
 
 
328
        case '\0':
 
329
        case ALT:
 
330
        case RBRACK:
 
331
                return (ENDSTATE);
 
332
        case LCLASS:
 
333
                while (ap->Ch != RCLASS && ap->Ch != '\0')
 
334
                        nextitem(ap);
 
335
                if (ap->Ch == '\0')
 
336
                        return (ENDSTATE);
 
337
                nextitem(ap);
 
338
                break;
 
339
        case REP:
 
340
                t = prim(ap);
 
341
                if (t == ENDSTATE)
 
342
                        return (ENDSTATE);
 
343
                setexits(ap->aux, t, a);
 
344
                break;
 
345
        case LBRACK:
 
346
                a = exp(ap, &ap->aux[a]);
 
347
                if (a == ENDSTATE || ap->Ch != RBRACK)
 
348
                        return (ENDSTATE);
 
349
                nextitem(ap);
 
350
                break;
 
351
        }
 
352
        return (a);
 
353
}
 
354
 
 
355
/*
 
356
 *      parse an expression (a sequence of primaries)
 
357
 */
 
358
static int exp(ap, altp)
 
359
        arg_t   *ap;
 
360
        int     *altp;
 
361
{
 
362
        int     exits = ENDSTATE;
 
363
        int     a;
 
364
        int     *aux = ap->aux;
 
365
        Uchar   Ch;
 
366
 
 
367
        for(;;) {
 
368
                a = prim(ap);
 
369
                Ch = ap->Ch;
 
370
                if (Ch == ALT || Ch == RBRACK || Ch == '\0') {
 
371
                        exits = join(aux, exits, a);
 
372
                        if (Ch != ALT)
 
373
                                return (exits);
 
374
                        *altp = ap->patp;
 
375
                        altp = &aux[ap->patp];
 
376
                        nextitem(ap);
 
377
                } else
 
378
                        setexits(aux, a, ap->patp);
 
379
        }
 
380
}
 
381
 
 
382
/*
 
383
 *      set all exits in a list to a specified value
 
384
 */
 
385
static void setexits(aux, list, val)
 
386
        int     *aux;
 
387
        int     list;
 
388
        int     val;
 
389
{
 
390
        int     a;
 
391
 
 
392
        while (list != ENDSTATE) {
 
393
                a = aux[list];
 
394
                aux[list] = val;
 
395
                list = a;
 
396
        }
 
397
}
 
398
 
 
399
/*
 
400
 *      concatenate two lists
 
401
 */
 
402
static int join(aux, a, b)
 
403
        int     *aux;
 
404
        int     a;
 
405
        int     b;
 
406
{
 
407
        int     t;
 
408
 
 
409
        if (a == ENDSTATE)
 
410
                return (b);
 
411
        t = a;
 
412
        while (aux[t] != ENDSTATE)
 
413
                t = aux[t];
 
414
        aux[t] = b;
 
415
        return (a);
 
416
}
 
417
 
 
418
/*
 
419
 *      patcompile - the external compiler interface.
 
420
 *
 
421
 *      The pattern is compiled into the aux array.
 
422
 *      Return value on success, is the outermost alternate which is != 0.
 
423
 *      Error is indicated by return of 0.
 
424
 */
 
425
int patcompile(pat, len, aux)
 
426
        const Uchar     *pat;
 
427
        int             len;
 
428
        int             *aux;
 
429
{
 
430
        arg_t   a;
 
431
        int     alt = ENDSTATE;
 
432
        int     i;
 
433
 
 
434
        a.pattern = pat;
 
435
        a.length  = len;
 
436
        a.aux     = aux;
 
437
        a.patp    = -1;
 
438
 
 
439
        for(i = 0; i < len; i++)
 
440
                aux[i] = ENDSTATE;
 
441
        rch(&a);
 
442
        i = exp(&a, &alt);
 
443
        if (i == ENDSTATE)
 
444
                return (0);
 
445
        setexits(aux, i, ENDSTATE);
 
446
        return (alt);
 
447
}
 
448
#endif  /* LMATCH */