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