server/common/re-cmp.c

/*
 * static char *rcsid_player_c =
 *   "$Id$";
 */


/* re-cmp.c
 * Pattern match a string, parsing some of the common RE-metacharacters.
 *
 * This code is public domain, but I would appreciate to hear of
 * improvements or even the fact that you use it in your program.
 *
 * Deliberate BUGS:
 *    - These tokens are not supported: | ( )
 *    - You will get the longest expansion of the _first_ string which
 *      matches the RE, not the longest string which would be the proper
 *      behaviour for a RE-matcher.
 *
 * Author: Kjetil T. Homme <kjetilho@ifi.uio.no> May 1993
 */

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <limits.h>
#include <re-cmp.h>
#include <ctype.h>

/* Get prototype functions to prevent warnings. */
#if defined (__sun__) && defined(StupidSunHeaders)
#  include <sys/types.h>
#  include <sys/time.h>
#  include "sunos.h"   /* Prototypes for standard libraries, sunos lack those */
#endif


/*   P r o t o t y p e s
 */
const char *re_cmp(const char *, const char *);
static Boolean re_cmp_step(const char *, const char *, unsigned, int);
static void re_init(void);
static Boolean re_match_token(uchar, selection *);
static const char *re_get_token(selection *, const char *);
#ifdef DEBUG2
static void re_dump_sel(selection *);
#endif

/*   G l o b a l   v a r i a b l e s
 */
static Boolean          re_init_done = False;
static selection        *re_token[RE_TOKEN_MAX];
static const char       *re_substr[RE_TOKEN_MAX];
static unsigned int     re_token_depth;

/*   E x t e r n a l   f u n c t i o n
 */

/* re-cmp - get regular expression match.
 * Return values: NULL - no match or error in regexp.
 *                pointer to beginning of matching string
 */
const char *
re_cmp(const char *str, const char *regexp) {
    const char *next_regexp;
    Boolean once = False;
    Boolean matched;

    if (re_init_done == False)
        re_init();

#ifdef SAFE_CHECKS
    if (regexp == NULL || str == NULL)
        return NULL;
#endif
    if (*regexp == '^') {
        once = True;
        ++regexp;
    }
    if (*regexp == 0) {
        /* // or /^/ matches any string */
        return str;
    }

    next_regexp = re_get_token(re_token[0], regexp);
    re_token_depth = 0;
    re_substr[0] = next_regexp;

    matched = False;
    while (*str != '\0' && !(matched = re_match_token(*str, re_token[0])))
        str++;
    
    if (matched && *next_regexp == 0)
        return str;

    /* Apologies for the nearly duplicated code below, hopefully it
     * speeds things up.
     */
    if (once) {
        switch (re_token[0]->repeat) {
            case rep_once:
                if (matched == False)
                    return NULL;
                break;
            case rep_once_or_more:
                if (matched == False)
                    return NULL;

                if (re_cmp_step(str+1, regexp, 0, 1))
                    return str;
                break;
            case rep_null_or_once:
                if (matched == False)
                    return re_cmp_step(str, next_regexp, 1, 0) ? str : NULL;
                break;
            case rep_null_or_more:
                if (matched) {
                    if (re_cmp_step(str+1, regexp, 0, 1))
                        return str;
                } else {
                    return re_cmp_step(str, next_regexp, 1, 0) ? str : NULL;
                }
                break;
        }
        return re_cmp_step(str+1, next_regexp, 1, 0) ? str : NULL;
    }

    if (matched) {
        switch (re_token[0]->repeat) {
            case rep_once:
            case rep_null_or_once:
                break;
            case rep_once_or_more:
            case rep_null_or_more:
                if (re_cmp_step(str+1, regexp, 0, 1))
                    return str;
                break;
        }
        /* The logic here is that re_match_token only sees
         * if the one letter matches.  Thus, if the
         * regex is like '@match eureca', and the
         * the user enters anything with an e, re_match_token
         * returns true, but they really need to match the
         * entire regexp, which re_cmp_step will do.
         * However, what happens is that there can be a case
         * where the string being match is something like
         * 'where is eureca'.  In this case, the re_match_token
         * matches that first e, but the re_cmp_step below,
         * fails because the next character (r) doesn't match
         * the u.  So we call re_cmp with the string
         * after the first r, so that it should hopefully match
         * up properly.
         */
        if (re_cmp_step(str+1, next_regexp, 1, 0))
            return str;
        else if (*(str+1) != 0)
            return re_cmp(str+1, regexp);
    }
    return NULL;
}

/*   A u x i l l i a r y   f u n c t i o n s
 */

static Boolean
re_cmp_step(const char *str, const char *regexp, unsigned slot, int matches) {
    /* str      - string to match
     * regexp   - pattern
     * slot     - number of the token which under consideration
     * matches  - how many times the token has matched
     */
    const char *next_regexp;
    Boolean matched;

#ifdef DEBUG
/*    fprintf(stderr, "['%s', '%s', %u, %d]\n", str, regexp, slot, matches);*/
#endif

    if (*regexp == 0) {
        /* When we reach the end of the regexp, the match is a success
         */
        return True;
    }

    /* This chunk of code makes sure that the regexp-tokenising happens
     * only once. We only tokenise as much as we need.
     */
    if (slot > re_token_depth) {
        re_token_depth = slot;
        if (re_token[slot] == NULL)
            re_token[slot] = (selection *) malloc(sizeof(selection));
        next_regexp = re_get_token(re_token[slot], regexp);
        if (next_regexp == NULL) {
            /* Syntax error, what else can we do? */
            return False;
        }
        re_substr[slot] = next_regexp;
    } else {
        next_regexp = re_substr[slot];
    }

    matched = re_match_token(*str, re_token[slot]);
    if (matched)
        ++matches;

    if (*str == 0)
        return (*next_regexp == 0 || re_token[slot]->type == sel_end) && matched;

    switch (re_token[slot]->repeat) {
        case rep_once:
            if (matches == 1) { /* (matches == 1) => (matched == True) */
                return re_cmp_step(str+1, next_regexp, slot+1, 0);
            }
            return False;
        case rep_once_or_more:
            if (matched) {      /* (matched == True) => (matches >= 1) */
                /* First check if the current token repeats more */
                if (re_cmp_step(str+1, regexp, slot, matches))
                    return True;
                return re_cmp_step(str+1, next_regexp, slot+1, 0);
            }
            return False;
        case rep_null_or_once:
            /* We must go on to the next token, but should we advance str? */
            if (matches == 0) {
                return re_cmp_step(str, next_regexp, slot+1, 0);
            } else if (matches == 1) {
                return re_cmp_step(str+1, next_regexp, slot+1, 0);
            }
            return False;       /* Not reached */
        case rep_null_or_more:
            if (matched) {
                /* Look for further repeats, advance str */
                if (re_cmp_step(str+1, regexp, slot, matches))
                    return True;
                return re_cmp_step(str, next_regexp, slot+1, 0);
            }
            return re_cmp_step(str, next_regexp, slot+1, 0);
    }
    return False;
}

static void
re_init(void) {
    int i;

    re_token[0] = (selection *) malloc(sizeof(selection));
    for (i = 1; i < RE_TOKEN_MAX; i++)
        re_token[i] = NULL;

    re_init_done = True;
}

static Boolean
re_match_token(uchar c, selection *sel) {
    switch (sel->type) {
        case sel_any:
            return True;
        case sel_end:
            return (c == 0);
        case sel_single:
            return (tolower(c) == tolower(sel->u.single));
        case sel_range:
            return (c >= sel->u.range.low && c <= sel->u.range.high);
        case sel_array:
            return (sel->u.array[c]);
        case sel_not_single:
            return (tolower(c) != tolower(sel->u.single));
        case sel_not_range:
            return (c < sel->u.range.low && c > sel->u.range.high);
    }
    return False;
}

/* re_get_token - get regular expression token
 * Returns the first token found in <regexp> in <sel>
 * Return values: NULL  syntax error
 *                pointer to first character past token.
 */
static const char *
re_get_token(selection *sel, const char *regexp) {

#ifdef SAFE_CHECKS
#   define exit_if_null if (*regexp == 0) return NULL
#else
#   define exit_if_null
#endif

    Boolean quoted = False;
    uchar looking_at;

#ifdef SAFE_CHECKS
    if (sel == NULL || regexp == NULL || *regexp == 0)
        return NULL;
#endif

    do {
        looking_at = *regexp++;
        switch (looking_at) {
            case '$':
                if (quoted) {
                    quoted = False;
                    sel->type = sel_single;
                    sel->u.single = looking_at;
                } else {
                    sel->type = sel_end;
                }
                break;
            case '.':
                if (quoted) {
                    quoted = False;
                    sel->type = sel_single;
                    sel->u.single = looking_at;
                } else {
                    sel->type = sel_any;
                }
                break;
            case '[':
                /* The fun stuff... perhaps a little obfuscated since I
                 * don't trust the compiler to analyse liveness.
                 */
                if (quoted) {
                    quoted = False;
                    sel->type = sel_single;
                    sel->u.single = looking_at;
                } else {
                    Boolean neg = False;
                    uchar first, last = 0;

                    exit_if_null;
                    looking_at = *regexp++;

                    if (looking_at == '^') {
                        neg = True;
                        exit_if_null;
                        looking_at = *regexp++;
                    }
                    first = looking_at;
                    exit_if_null;
                    looking_at = *regexp++;
                    if (looking_at == ']') {
                        /* On the form [q] or [^q] */
                        sel->type = neg ? sel_not_single : sel_single;
                        sel->u.single = first;
                        break;
                    } else if (looking_at == '-') {
                        exit_if_null;
                        last = *regexp++;
                        if (last == ']') {
                            /* On the form [A-] or [^A-]. Checking for
                             * [,-] and making it a range is probably not
                             * worth it :-)
                             */
                            sel->type = sel_array;
                            memset(sel->u.array, neg, sizeof(sel->u.array));
                            sel->u.array[first] = sel->u.array['-'] = !neg;
                            break;
                        } else {
                            exit_if_null;
                            looking_at = *regexp++;
                            if (looking_at == ']') {
                                /* On the form [A-G] or [^A-G]. Note that [G-A]
                                 * is a syntax error. Fair enough, I think.
                                 */
#ifdef SAFE_CHECK
                                if (first > last)
                                    return NULL;
#endif
                                sel->type = neg ? sel_not_range : sel_range;
                                sel->u.range.low = first;
                                sel->u.range.high = last;
                                break;
                            }
                        }
                    }
                    {
                        /* The datastructure can only represent a RE this
                         * complex with an array.
                         */
                        int i;
                        uchar previous;

                        sel->type = sel_array;
                        memset(sel->u.array, neg, sizeof(sel->u.array));
                        if (last) {
                            /* It starts with a range */
#ifdef SAFE_CHECK
                            if (first > last)
                                return NULL;
#endif
                            for (i = first; i <= last; i++) {
                                sel->u.array[i] = !neg;
                            }
                        } else {
                            /* It begins with a "random" character */
                            sel->u.array[first] = !neg;
                        }
                        sel->u.array[looking_at] = !neg;

                        exit_if_null;
                        previous = looking_at;
                        looking_at = *regexp++;

                        /* Add more characters to the array until we reach
                         * ]. Quoting doesn't and shouldn't work in here.
                         * ("]" should be put first, and "-" last if they
                         * are needed inside this construct.)
                         * Look for ranges as we go along.
                         */
                        while (looking_at != ']') {
                            if (looking_at == '-') {
                                exit_if_null;
                                looking_at = *regexp++;
                                if (looking_at != ']') {
#ifdef SAFE_CHECK
                                    if (previous > looking_at)
                                        return NULL;
#endif
                                    for (i = previous+1; i < looking_at; i++) {
                                        /* previous has already been set and
                                         * looking_at is set below.
                                         */
                                        sel->u.array[i] = !neg;
                                    }
                                    exit_if_null;
                                } else {
                                    sel->u.array['-'] = !neg;
                                    break;
                                }
                            }
                            sel->u.array[looking_at] = !neg;
                            previous = looking_at;
                            exit_if_null;
                            looking_at = *regexp++;
                        }
                    }
                }
                break;
            case '\\':
                if (quoted) {
                    quoted = False;
                    sel->type = sel_single;
                    sel->u.single = looking_at;
                } else {
                    quoted = True;
                }
                break;
            default:
                quoted = False;
                sel->type = sel_single;
                sel->u.single = looking_at;
                break;
        }
    } while (quoted);

    if (*regexp == '*') {
        sel->repeat = rep_null_or_more;
        ++regexp;
    } else if (*regexp == '?') {
        sel->repeat = rep_null_or_once;
        ++regexp;
    } else if (*regexp == '+') {
        sel->repeat = rep_once_or_more;
        ++regexp;
    } else {
        sel->repeat = rep_once;
    }

    return regexp;
}

/*   D e b u g   c o d e
 */
#ifdef DEBUG2 /* compile all with DEBUG also ? hevi@lut.fi */
static void
re_dump_sel(selection *sel) {
    switch(sel->type) {
        case sel_any:
            printf(".");
            break;
        case sel_end:
            printf("$");
            break;
        case sel_single:
            printf("<%c>", sel->u.single);
            break;
        case sel_range:
            printf("[%c-%c]", sel->u.range.low, sel->u.range.high);
            break;
        case sel_array:
            {
                int i;
                printf("[");
                for (i = 0; i < UCHAR_MAX; i++) {
                    if (sel->u.array[i]) {
                        printf("%c", i);
                    }
                }
                printf("]");
            }
            break;
        case sel_not_single:
            printf("[^%c]", sel->u.single);
            break;
        case sel_not_range:
            printf("[^%c-%c]", sel->u.range.low, sel->u.range.high);
            break;
        default:
            printf("<UNKNOWN TOKEN!>");
            break;
    }
    switch(sel->repeat) {
        case rep_once:
            break;
        case rep_null_or_once:
            printf("?");
            break;
        case rep_null_or_more:
            printf("*");
            break;
        case rep_once_or_more:
            printf("+");
            break;
        default:
            printf("<UNKNOWN REP-TOKEN!>");
            break;
    }
}

int
main(int argc, char *argv[]) {
    char *re, *m;
    selection sel;

    re = re_get_token(&sel, argv[1]);

    printf("'%s' -> '%s'\n", argv[1], re);
    re_dump_sel(&sel);
    printf("\n");
    m = re_cmp(argv[2], argv[1]);
    if (m)
        printf("MATCH! -> '%s'\n", m);
    return 0;
}
#endif
Revision:	1.2
Committed:	Sun Aug 13 17:16:00 2006 UTC (17 years, 9 months ago) by elmex
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+1 -1 lines
State:	*FILE REMOVED*
Log Message:	Made server compile with C++. Removed cfanim plugin and crossedit. C++ here we come.
#	Content
1	/*
2	* static char *rcsid_player_c =
3	* "$Id$";
4	*/
5
6
7	/* re-cmp.c
8	* Pattern match a string, parsing some of the common RE-metacharacters.
9	*
10	* This code is public domain, but I would appreciate to hear of
11	* improvements or even the fact that you use it in your program.
12	*
13	* Deliberate BUGS:
14	* - These tokens are not supported: \| ( )
15	* - You will get the longest expansion of the _first_ string which
16	* matches the RE, not the longest string which would be the proper
17	* behaviour for a RE-matcher.
18	*
19	* Author: Kjetil T. Homme <kjetilho@ifi.uio.no> May 1993
20	*/
21
22	#include <stdio.h>
23	#include <stdlib.h>
24	#include <memory.h>
25	#include <limits.h>
26	#include <re-cmp.h>
27	#include <ctype.h>
28
29	/* Get prototype functions to prevent warnings. */
30	#if defined (__sun__) && defined(StupidSunHeaders)
31	# include <sys/types.h>
32	# include <sys/time.h>
33	# include "sunos.h" /* Prototypes for standard libraries, sunos lack those */
34	#endif
35
36
37	/* P r o t o t y p e s
38	*/
39	const char re_cmp(const char , const char *);
40	static Boolean re_cmp_step(const char , const char , unsigned, int);
41	static void re_init(void);
42	static Boolean re_match_token(uchar, selection *);
43	static const char re_get_token(selection , const char *);
44	#ifdef DEBUG2
45	static void re_dump_sel(selection *);
46	#endif
47
48	/* G l o b a l v a r i a b l e s
49	*/
50	static Boolean re_init_done = False;
51	static selection *re_token[RE_TOKEN_MAX];
52	static const char *re_substr[RE_TOKEN_MAX];
53	static unsigned int re_token_depth;
54
55	/* E x t e r n a l f u n c t i o n
56	*/
57
58	/* re-cmp - get regular expression match.
59	* Return values: NULL - no match or error in regexp.
60	* pointer to beginning of matching string
61	*/
62	const char *
63	re_cmp(const char str, const char regexp) {
64	const char *next_regexp;
65	Boolean once = False;
66	Boolean matched;
67
68	if (re_init_done == False)
69	re_init();
70
71	#ifdef SAFE_CHECKS
72	if (regexp == NULL \|\| str == NULL)
73	return NULL;
74	#endif
75	if (*regexp == '^') {
76	once = True;
77	++regexp;
78	}
79	if (*regexp == 0) {
80	/* // or /^/ matches any string */
81	return str;
82	}
83
84	next_regexp = re_get_token(re_token[0], regexp);
85	re_token_depth = 0;
86	re_substr[0] = next_regexp;
87
88	matched = False;
89	while (str != '\0' && !(matched = re_match_token(str, re_token[0])))
90	str++;
91
92	if (matched && *next_regexp == 0)
93	return str;
94
95	/* Apologies for the nearly duplicated code below, hopefully it
96	* speeds things up.
97	*/
98	if (once) {
99	switch (re_token[0]->repeat) {
100	case rep_once:
101	if (matched == False)
102	return NULL;
103	break;
104	case rep_once_or_more:
105	if (matched == False)
106	return NULL;
107
108	if (re_cmp_step(str+1, regexp, 0, 1))
109	return str;
110	break;
111	case rep_null_or_once:
112	if (matched == False)
113	return re_cmp_step(str, next_regexp, 1, 0) ? str : NULL;
114	break;
115	case rep_null_or_more:
116	if (matched) {
117	if (re_cmp_step(str+1, regexp, 0, 1))
118	return str;
119	} else {
120	return re_cmp_step(str, next_regexp, 1, 0) ? str : NULL;
121	}
122	break;
123	}
124	return re_cmp_step(str+1, next_regexp, 1, 0) ? str : NULL;
125	}
126
127	if (matched) {
128	switch (re_token[0]->repeat) {
129	case rep_once:
130	case rep_null_or_once:
131	break;
132	case rep_once_or_more:
133	case rep_null_or_more:
134	if (re_cmp_step(str+1, regexp, 0, 1))
135	return str;
136	break;
137	}
138	/* The logic here is that re_match_token only sees
139	* if the one letter matches. Thus, if the
140	* regex is like '@match eureca', and the
141	* the user enters anything with an e, re_match_token
142	* returns true, but they really need to match the
143	* entire regexp, which re_cmp_step will do.
144	* However, what happens is that there can be a case
145	* where the string being match is something like
146	* 'where is eureca'. In this case, the re_match_token
147	* matches that first e, but the re_cmp_step below,
148	* fails because the next character (r) doesn't match
149	* the u. So we call re_cmp with the string
150	* after the first r, so that it should hopefully match
151	* up properly.
152	*/
153	if (re_cmp_step(str+1, next_regexp, 1, 0))
154	return str;
155	else if (*(str+1) != 0)
156	return re_cmp(str+1, regexp);
157	}
158	return NULL;
159	}
160
161	/* A u x i l l i a r y f u n c t i o n s
162	*/
163
164	static Boolean
165	re_cmp_step(const char str, const char regexp, unsigned slot, int matches) {
166	/* str - string to match
167	* regexp - pattern
168	* slot - number of the token which under consideration
169	* matches - how many times the token has matched
170	*/
171	const char *next_regexp;
172	Boolean matched;
173
174	#ifdef DEBUG
175	/* fprintf(stderr, "['%s', '%s', %u, %d]\n", str, regexp, slot, matches);*/
176	#endif
177
178	if (*regexp == 0) {
179	/* When we reach the end of the regexp, the match is a success
180	*/
181	return True;
182	}
183
184	/* This chunk of code makes sure that the regexp-tokenising happens
185	* only once. We only tokenise as much as we need.
186	*/
187	if (slot > re_token_depth) {
188	re_token_depth = slot;
189	if (re_token[slot] == NULL)
190	re_token[slot] = (selection *) malloc(sizeof(selection));
191	next_regexp = re_get_token(re_token[slot], regexp);
192	if (next_regexp == NULL) {
193	/* Syntax error, what else can we do? */
194	return False;
195	}
196	re_substr[slot] = next_regexp;
197	} else {
198	next_regexp = re_substr[slot];
199	}
200
201	matched = re_match_token(*str, re_token[slot]);
202	if (matched)
203	++matches;
204
205	if (*str == 0)
206	return (*next_regexp == 0 \|\| re_token[slot]->type == sel_end) && matched;
207
208	switch (re_token[slot]->repeat) {
209	case rep_once:
210	if (matches == 1) { /* (matches == 1) => (matched == True) */
211	return re_cmp_step(str+1, next_regexp, slot+1, 0);
212	}
213	return False;
214	case rep_once_or_more:
215	if (matched) { /* (matched == True) => (matches >= 1) */
216	/* First check if the current token repeats more */
217	if (re_cmp_step(str+1, regexp, slot, matches))
218	return True;
219	return re_cmp_step(str+1, next_regexp, slot+1, 0);
220	}
221	return False;
222	case rep_null_or_once:
223	/* We must go on to the next token, but should we advance str? */
224	if (matches == 0) {
225	return re_cmp_step(str, next_regexp, slot+1, 0);
226	} else if (matches == 1) {
227	return re_cmp_step(str+1, next_regexp, slot+1, 0);
228	}
229	return False; /* Not reached */
230	case rep_null_or_more:
231	if (matched) {
232	/* Look for further repeats, advance str */
233	if (re_cmp_step(str+1, regexp, slot, matches))
234	return True;
235	return re_cmp_step(str, next_regexp, slot+1, 0);
236	}
237	return re_cmp_step(str, next_regexp, slot+1, 0);
238	}
239	return False;
240	}
241
242	static void
243	re_init(void) {
244	int i;
245
246	re_token[0] = (selection *) malloc(sizeof(selection));
247	for (i = 1; i < RE_TOKEN_MAX; i++)
248	re_token[i] = NULL;
249
250	re_init_done = True;
251	}
252
253	static Boolean
254	re_match_token(uchar c, selection *sel) {
255	switch (sel->type) {
256	case sel_any:
257	return True;
258	case sel_end:
259	return (c == 0);
260	case sel_single:
261	return (tolower(c) == tolower(sel->u.single));
262	case sel_range:
263	return (c >= sel->u.range.low && c <= sel->u.range.high);
264	case sel_array:
265	return (sel->u.array[c]);
266	case sel_not_single:
267	return (tolower(c) != tolower(sel->u.single));
268	case sel_not_range:
269	return (c < sel->u.range.low && c > sel->u.range.high);
270	}
271	return False;
272	}
273
274	/* re_get_token - get regular expression token
275	* Returns the first token found in <regexp> in <sel>
276	* Return values: NULL syntax error
277	* pointer to first character past token.
278	*/
279	static const char *
280	re_get_token(selection sel, const char regexp) {
281
282	#ifdef SAFE_CHECKS
283	# define exit_if_null if (*regexp == 0) return NULL
284	#else
285	# define exit_if_null
286	#endif
287
288	Boolean quoted = False;
289	uchar looking_at;
290
291	#ifdef SAFE_CHECKS
292	if (sel == NULL \|\| regexp == NULL \|\| *regexp == 0)
293	return NULL;
294	#endif
295
296	do {
297	looking_at = *regexp++;
298	switch (looking_at) {
299	case '$':
300	if (quoted) {
301	quoted = False;
302	sel->type = sel_single;
303	sel->u.single = looking_at;
304	} else {
305	sel->type = sel_end;
306	}
307	break;
308	case '.':
309	if (quoted) {
310	quoted = False;
311	sel->type = sel_single;
312	sel->u.single = looking_at;
313	} else {
314	sel->type = sel_any;
315	}
316	break;
317	case '[':
318	/* The fun stuff... perhaps a little obfuscated since I
319	* don't trust the compiler to analyse liveness.
320	*/
321	if (quoted) {
322	quoted = False;
323	sel->type = sel_single;
324	sel->u.single = looking_at;
325	} else {
326	Boolean neg = False;
327	uchar first, last = 0;
328
329	exit_if_null;
330	looking_at = *regexp++;
331
332	if (looking_at == '^') {
333	neg = True;
334	exit_if_null;
335	looking_at = *regexp++;
336	}
337	first = looking_at;
338	exit_if_null;
339	looking_at = *regexp++;
340	if (looking_at == ']') {
341	/* On the form [q] or [^q] */
342	sel->type = neg ? sel_not_single : sel_single;
343	sel->u.single = first;
344	break;
345	} else if (looking_at == '-') {
346	exit_if_null;
347	last = *regexp++;
348	if (last == ']') {
349	/* On the form [A-] or [^A-]. Checking for
350	* [,-] and making it a range is probably not
351	* worth it :-)
352	*/
353	sel->type = sel_array;
354	memset(sel->u.array, neg, sizeof(sel->u.array));
355	sel->u.array[first] = sel->u.array['-'] = !neg;
356	break;
357	} else {
358	exit_if_null;
359	looking_at = *regexp++;
360	if (looking_at == ']') {
361	/* On the form [A-G] or [^A-G]. Note that [G-A]
362	* is a syntax error. Fair enough, I think.
363	*/
364	#ifdef SAFE_CHECK
365	if (first > last)
366	return NULL;
367	#endif
368	sel->type = neg ? sel_not_range : sel_range;
369	sel->u.range.low = first;
370	sel->u.range.high = last;
371	break;
372	}
373	}
374	}
375	{
376	/* The datastructure can only represent a RE this
377	* complex with an array.
378	*/
379	int i;
380	uchar previous;
381
382	sel->type = sel_array;
383	memset(sel->u.array, neg, sizeof(sel->u.array));
384	if (last) {
385	/* It starts with a range */
386	#ifdef SAFE_CHECK
387	if (first > last)
388	return NULL;
389	#endif
390	for (i = first; i <= last; i++) {
391	sel->u.array[i] = !neg;
392	}
393	} else {
394	/* It begins with a "random" character */
395	sel->u.array[first] = !neg;
396	}
397	sel->u.array[looking_at] = !neg;
398
399	exit_if_null;
400	previous = looking_at;
401	looking_at = *regexp++;
402
403	/* Add more characters to the array until we reach
404	* ]. Quoting doesn't and shouldn't work in here.
405	* ("]" should be put first, and "-" last if they
406	* are needed inside this construct.)
407	* Look for ranges as we go along.
408	*/
409	while (looking_at != ']') {
410	if (looking_at == '-') {
411	exit_if_null;
412	looking_at = *regexp++;
413	if (looking_at != ']') {
414	#ifdef SAFE_CHECK
415	if (previous > looking_at)
416	return NULL;
417	#endif
418	for (i = previous+1; i < looking_at; i++) {
419	/* previous has already been set and
420	* looking_at is set below.
421	*/
422	sel->u.array[i] = !neg;
423	}
424	exit_if_null;
425	} else {
426	sel->u.array['-'] = !neg;
427	break;
428	}
429	}
430	sel->u.array[looking_at] = !neg;
431	previous = looking_at;
432	exit_if_null;
433	looking_at = *regexp++;
434	}
435	}
436	}
437	break;
438	case '\\':
439	if (quoted) {
440	quoted = False;
441	sel->type = sel_single;
442	sel->u.single = looking_at;
443	} else {
444	quoted = True;
445	}
446	break;
447	default:
448	quoted = False;
449	sel->type = sel_single;
450	sel->u.single = looking_at;
451	break;
452	}
453	} while (quoted);
454
455	if (regexp == '') {
456	sel->repeat = rep_null_or_more;
457	++regexp;
458	} else if (*regexp == '?') {
459	sel->repeat = rep_null_or_once;
460	++regexp;
461	} else if (*regexp == '+') {
462	sel->repeat = rep_once_or_more;
463	++regexp;
464	} else {
465	sel->repeat = rep_once;
466	}
467
468	return regexp;
469	}
470
471	/* D e b u g c o d e
472	*/
473	#ifdef DEBUG2 /* compile all with DEBUG also ? hevi@lut.fi */
474	static void
475	re_dump_sel(selection *sel) {
476	switch(sel->type) {
477	case sel_any:
478	printf(".");
479	break;
480	case sel_end:
481	printf("$");
482	break;
483	case sel_single:
484	printf("<%c>", sel->u.single);
485	break;
486	case sel_range:
487	printf("[%c-%c]", sel->u.range.low, sel->u.range.high);
488	break;
489	case sel_array:
490	{
491	int i;
492	printf("[");
493	for (i = 0; i < UCHAR_MAX; i++) {
494	if (sel->u.array[i]) {
495	printf("%c", i);
496	}
497	}
498	printf("]");
499	}
500	break;
501	case sel_not_single:
502	printf("[^%c]", sel->u.single);
503	break;
504	case sel_not_range:
505	printf("[^%c-%c]", sel->u.range.low, sel->u.range.high);
506	break;
507	default:
508	printf("<UNKNOWN TOKEN!>");
509	break;
510	}
511	switch(sel->repeat) {
512	case rep_once:
513	break;
514	case rep_null_or_once:
515	printf("?");
516	break;
517	case rep_null_or_more:
518	printf("*");
519	break;
520	case rep_once_or_more:
521	printf("+");
522	break;
523	default:
524	printf("<UNKNOWN REP-TOKEN!>");
525	break;
526	}
527	}
528
529	int
530	main(int argc, char *argv[]) {
531	char re, m;
532	selection sel;
533
534	re = re_get_token(&sel, argv[1]);
535
536	printf("'%s' -> '%s'\n", argv[1], re);
537	re_dump_sel(&sel);
538	printf("\n");
539	m = re_cmp(argv[2], argv[1]);
540	if (m)
541	printf("MATCH! -> '%s'\n", m);
542	return 0;
543	}
544	#endif