52e450f556e576eac172040678bf9ef90f9a449d
[openafs.git] / src / util / regex.c
1 /*
2  * Copyright 2000, International Business Machines Corporation and others.
3  * All Rights Reserved.
4  * 
5  * This software has been released under the terms of the IBM Public
6  * License.  For details, see the LICENSE file in the top-level source
7  * directory or online at http://www.openafs.org/dl/license10.html
8  */
9
10 /*
11  * regex.c -- regular expression patter matching functions
12  * 
13  */
14
15 #include <afsconfig.h>
16 #include <afs/param.h>
17
18 RCSID
19     ("$Header$");
20
21 /*
22  * routines to do regular expression matching
23  *
24  * Entry points:
25  *
26  *      re_comp(s)
27  *              char *s;
28  *       ... returns 0 if the string s was compiled successfully,
29  *                   a pointer to an error message otherwise.
30  *           If passed 0 or a null string returns without changing
31  *           the currently compiled re (see note 11 below).
32  *
33  *      re_exec(s)
34  *              char *s;
35  *       ... returns 1 if the string s matches the last compiled regular
36  *                     expression, 
37  *                   0 if the string s failed to match the last compiled
38  *                     regular expression, and
39  *                  -1 if the compiled regular expression was invalid 
40  *                     (indicating an internal error).
41  *
42  * The strings passed to both re_comp and re_exec may have trailing or
43  * embedded newline characters; they are terminated by nulls.
44  *
45  * The identity of the author of these routines is lost in antiquity;
46  * this is essentially the same as the re code in the original V6 ed.
47  *
48  * The regular expressions recognized are described below. This description
49  * is essentially the same as that for ed.
50  *
51  *      A regular expression specifies a set of strings of characters.
52  *      A member of this set of strings is said to be matched by
53  *      the regular expression.  In the following specification for
54  *      regular expressions the word `character' means any character but NUL.
55  *
56  *      1.  Any character except a special character matches itself.
57  *          Special characters are the regular expression delimiter plus
58  *          \ [ . and sometimes ^ * $.
59  *      2.  A . matches any character.
60  *      3.  A \ followed by any character except a digit or ( )
61  *          matches that character.
62  *      4.  A nonempty string s bracketed [s] (or [^s]) matches any
63  *          character in (or not in) s. In s, \ has no special meaning,
64  *          and ] may only appear as the first letter. A substring 
65  *          a-b, with a and b in ascending ASCII order, stands for
66  *          the inclusive range of ASCII characters.
67  *      5.  A regular expression of form 1-4 followed by * matches a
68  *          sequence of 0 or more matches of the regular expression.
69  *      6.  A regular expression, x, of form 1-8, bracketed \(x\)
70  *          matches what x matches.
71  *      7.  A \ followed by a digit n matches a copy of the string that the
72  *          bracketed regular expression beginning with the nth \( matched.
73  *      8.  A regular expression of form 1-8, x, followed by a regular
74  *          expression of form 1-7, y matches a match for x followed by
75  *          a match for y, with the x match being as long as possible
76  *          while still permitting a y match.
77  *      9.  A regular expression of form 1-8 preceded by ^ (or followed
78  *          by $), is constrained to matches that begin at the left
79  *          (or end at the right) end of a line.
80  *      10. A regular expression of form 1-9 picks out the longest among
81  *          the leftmost matches in a line.
82  *      11. An empty regular expression stands for a copy of the last
83  *          regular expression encountered.
84  */
85
86 /*
87  * constants for re's
88  */
89 #define CBRA    1
90 #define CCHR    2
91 #define CDOT    4
92 #define CCL     6
93 #define NCCL    8
94 #define CDOL    10
95 #define CEOF    11
96 #define CKET    12
97 #define CBACK   18
98
99 #define CSTAR   01
100
101 #define ESIZE   512
102 #define NBRA    9
103
104 static char expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
105 static char circf;
106
107 /* forward defs
108 */
109
110 static int advance();
111 static int backref();
112 static int cclass();
113
114
115 /*
116  * compile the regular expression argument into a dfa
117  */
118 char *
119 re_comp(register char *sp)
120 {
121     register int c;
122     register char *ep = expbuf;
123     int cclcnt, numbra = 0;
124     char *lastep = 0;
125     char bracket[NBRA];
126     char *bracketp = &bracket[0];
127     static char *retoolong = "Regular expression too long";
128
129 #define comperr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
130
131     if (sp == 0 || *sp == '\0') {
132         if (*ep == 0)
133             return ("No previous regular expression");
134         return (0);
135     }
136     if (*sp == '^') {
137         circf = 1;
138         sp++;
139     } else
140         circf = 0;
141     for (;;) {
142         if (ep >= &expbuf[ESIZE - 10 /* fudge factor */])
143             comperr(retoolong);
144         if ((c = *sp++) == '\0') {
145             if (bracketp != bracket)
146                 comperr("unmatched \\(");
147             *ep++ = CEOF;
148             *ep++ = 0;
149             return (0);
150         }
151         if (c != '*')
152             lastep = ep;
153         switch (c) {
154
155         case '.':
156             *ep++ = CDOT;
157             continue;
158
159         case '*':
160             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
161                 goto defchar;
162             *lastep |= CSTAR;
163             continue;
164
165         case '$':
166             if (*sp != '\0')
167                 goto defchar;
168             *ep++ = CDOL;
169             continue;
170
171         case '[':
172             *ep++ = CCL;
173             *ep++ = 0;
174             cclcnt = 1;
175             if ((c = *sp++) == '^') {
176                 c = *sp++;
177                 ep[-2] = NCCL;
178             }
179             do {
180                 if (c == '\0')
181                     comperr("missing ]");
182                 if (c == '-' && ep[-1] != 0) {
183                     if ((c = *sp++) == ']') {
184                         *ep++ = '-';
185                         cclcnt++;
186                         break;
187                     }
188                     while (ep[-1] < c) {
189                         *ep = ep[-1] + 1;
190                         ep++;
191                         cclcnt++;
192                         if (ep >= &expbuf[ESIZE - 10 /* fudge factor */])
193                             comperr(retoolong);
194                     }
195                 }
196                 *ep++ = c;
197                 cclcnt++;
198                 if (ep >= &expbuf[ESIZE - 10 /* fudge factor */])
199                     comperr(retoolong);
200             } while ((c = *sp++) != ']');
201             lastep[1] = cclcnt;
202             continue;
203
204         case '\\':
205             if ((c = *sp++) == '(') {
206                 if (numbra >= NBRA)
207                     comperr("too many \\(\\) pairs");
208                 *bracketp++ = numbra;
209                 *ep++ = CBRA;
210                 *ep++ = numbra++;
211                 continue;
212             }
213             if (c == ')') {
214                 if (bracketp <= bracket)
215                     comperr("unmatched \\)");
216                 *ep++ = CKET;
217                 *ep++ = *--bracketp;
218                 continue;
219             }
220             if (c >= '1' && c < ('1' + NBRA)) {
221                 *ep++ = CBACK;
222                 *ep++ = c - '1';
223                 continue;
224             }
225             *ep++ = CCHR;
226             *ep++ = c;
227             continue;
228
229           defchar:
230         default:
231             *ep++ = CCHR;
232             *ep++ = c;
233         }
234     }
235 }
236
237 /* 
238  * match the argument string against the compiled re
239  */
240 int
241 re_exec(register char *p1)
242 {
243     register char *p2 = expbuf;
244     register int c;
245     int rv;
246
247     for (c = 0; c < NBRA; c++) {
248         braslist[c] = 0;
249         braelist[c] = 0;
250     }
251     if (circf)
252         return ((advance(p1, p2)));
253     /*
254      * fast check for first character
255      */
256     if (*p2 == CCHR) {
257         c = p2[1];
258         do {
259             if (*p1 != c)
260                 continue;
261             if (rv = advance(p1, p2))
262                 return (rv);
263         } while (*p1++);
264         return (0);
265     }
266     /*
267      * regular algorithm
268      */
269     do
270         if (rv = advance(p1, p2))
271             return (rv);
272     while (*p1++);
273     return (0);
274 }
275
276 /* 
277  * try to match the next thing in the dfa
278  */
279 static int
280 advance(lp, ep)
281      register char *lp, *ep;
282 {
283     register char *curlp;
284     int ct, i;
285     int rv;
286
287     for (;;)
288         switch (*ep++) {
289
290         case CCHR:
291             if (*ep++ == *lp++)
292                 continue;
293             return (0);
294
295         case CDOT:
296             if (*lp++)
297                 continue;
298             return (0);
299
300         case CDOL:
301             if (*lp == '\0')
302                 continue;
303             return (0);
304
305         case CEOF:
306             return (1);
307
308         case CCL:
309             if (cclass(ep, *lp++, 1)) {
310                 ep += *ep;
311                 continue;
312             }
313             return (0);
314
315         case NCCL:
316             if (cclass(ep, *lp++, 0)) {
317                 ep += *ep;
318                 continue;
319             }
320             return (0);
321
322         case CBRA:
323             braslist[*ep++] = lp;
324             continue;
325
326         case CKET:
327             braelist[*ep++] = lp;
328             continue;
329
330         case CBACK:
331             if (braelist[i = *ep++] == 0)
332                 return (-1);
333             if (backref(i, lp)) {
334                 lp += braelist[i] - braslist[i];
335                 continue;
336             }
337             return (0);
338
339         case CBACK | CSTAR:
340             if (braelist[i = *ep++] == 0)
341                 return (-1);
342             curlp = lp;
343             ct = braelist[i] - braslist[i];
344             while (backref(i, lp))
345                 lp += ct;
346             while (lp >= curlp) {
347                 if (rv = advance(lp, ep))
348                     return (rv);
349                 lp -= ct;
350             }
351             continue;
352
353         case CDOT | CSTAR:
354             curlp = lp;
355             while (*lp++);
356             goto star;
357
358         case CCHR | CSTAR:
359             curlp = lp;
360             while (*lp++ == *ep);
361             ep++;
362             goto star;
363
364         case CCL | CSTAR:
365         case NCCL | CSTAR:
366             curlp = lp;
367             while (cclass(ep, *lp++, ep[-1] == (CCL | CSTAR)));
368             ep += *ep;
369             goto star;
370
371           star:
372             do {
373                 lp--;
374                 if (rv = advance(lp, ep))
375                     return (rv);
376             } while (lp > curlp);
377             return (0);
378
379         default:
380             return (-1);
381         }
382 }
383
384 static int
385 backref(i, lp)
386      register int i;
387      register char *lp;
388 {
389     register char *bp;
390
391     bp = braslist[i];
392     while (*bp++ == *lp++)
393         if (bp >= braelist[i])
394             return (1);
395     return (0);
396 }
397
398 static int
399 cclass(set, c, af)
400      register char *set, c;
401      int af;
402 {
403     register int n;
404
405     if (c == 0)
406         return (0);
407     n = *set++;
408     while (--n)
409         if (*set++ == c)
410             return (af);
411     return (!af);
412 }