1: /* Extended regular expression matching and search library.
2: Copyright (C) 2002, 2003 Free Software Foundation, Inc.
3: This file is part of the GNU C Library.
4: Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5:
6: The GNU C Library is free software; you can redistribute it and/or
7: modify it under the terms of the GNU Lesser General Public
8: License as published by the Free Software Foundation; either
9: version 2.1 of the License, or (at your option) any later version.
10:
11: The GNU C Library is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14: Lesser General Public License for more details.
15:
16: You should have received a copy of the GNU Lesser General Public
17: License along with the GNU C Library; if not, write to the Free
18: Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
19: MA 02110-1301 USA. */
20:
21: static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
22: int length, reg_syntax_t syntax);
23: static void re_compile_fastmap_iter (regex_t *bufp,
24: const re_dfastate_t *init_state,
25: char *fastmap);
26: static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);
27: static reg_errcode_t init_word_char (re_dfa_t *dfa);
28: #ifdef RE_ENABLE_I18N
29: static void free_charset (re_charset_t *cset);
30: #endif /* RE_ENABLE_I18N */
31: static void free_workarea_compile (regex_t *preg);
32: static reg_errcode_t create_initial_state (re_dfa_t *dfa);
33: static reg_errcode_t analyze (re_dfa_t *dfa);
34: static reg_errcode_t analyze_tree (re_dfa_t *dfa, bin_tree_t *node);
35: static void calc_first (re_dfa_t *dfa, bin_tree_t *node);
36: static void calc_next (re_dfa_t *dfa, bin_tree_t *node);
37: static void calc_epsdest (re_dfa_t *dfa, bin_tree_t *node);
38: static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
39: int top_clone_node, int root_node,
40: unsigned int constraint);
41: static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
42: unsigned int constraint);
43: static int search_duplicated_node (re_dfa_t *dfa, int org_node,
44: unsigned int constraint);
45: static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
46: static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
47: int node, int root);
48: static void calc_inveclosure (re_dfa_t *dfa);
49: static int fetch_number (re_string_t *input, re_token_t *token,
50: reg_syntax_t syntax);
51: static re_token_t fetch_token (re_string_t *input, reg_syntax_t syntax);
52: static int peek_token (re_token_t *token, re_string_t *input,
53: reg_syntax_t syntax);
54: static int peek_token_bracket (re_token_t *token, re_string_t *input,
55: reg_syntax_t syntax);
56: static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
57: reg_syntax_t syntax, reg_errcode_t *err);
58: static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
59: re_token_t *token, reg_syntax_t syntax,
60: int nest, reg_errcode_t *err);
61: static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,
62: re_token_t *token, reg_syntax_t syntax,
63: int nest, reg_errcode_t *err);
64: static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,
65: re_token_t *token, reg_syntax_t syntax,
66: int nest, reg_errcode_t *err);
67: static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,
68: re_token_t *token, reg_syntax_t syntax,
69: int nest, reg_errcode_t *err);
70: static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
71: re_dfa_t *dfa, re_token_t *token,
72: reg_syntax_t syntax, reg_errcode_t *err);
73: static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
74: re_token_t *token, reg_syntax_t syntax,
75: reg_errcode_t *err);
76: static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
77: re_string_t *regexp,
78: re_token_t *token, int token_len,
79: re_dfa_t *dfa,
80: reg_syntax_t syntax);
81: static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
82: re_string_t *regexp,
83: re_token_t *token);
84: #ifndef _LIBC
85: # ifdef RE_ENABLE_I18N
86: static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
87: re_charset_t *mbcset, int *range_alloc,
88: bracket_elem_t *start_elem,
89: bracket_elem_t *end_elem);
90: static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
91: re_charset_t *mbcset,
92: int *coll_sym_alloc,
93: const unsigned char *name);
94: # else /* not RE_ENABLE_I18N */
95: static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
96: bracket_elem_t *start_elem,
97: bracket_elem_t *end_elem);
98: static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
99: const unsigned char *name);
100: # endif /* not RE_ENABLE_I18N */
101: #endif /* not _LIBC */
102: #ifdef RE_ENABLE_I18N
103: static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
104: re_charset_t *mbcset,
105: int *equiv_class_alloc,
106: const unsigned char *name);
107: static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,
108: re_charset_t *mbcset,
109: int *char_class_alloc,
110: const unsigned char *class_name,
111: reg_syntax_t syntax);
112: #else /* not RE_ENABLE_I18N */
113: static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
114: const unsigned char *name);
115: static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,
116: const unsigned char *class_name,
117: reg_syntax_t syntax);
118: #endif /* not RE_ENABLE_I18N */
119: static bin_tree_t *build_word_op (re_dfa_t *dfa, int not, reg_errcode_t *err);
120: static void free_bin_tree (bin_tree_t *tree);
121: static bin_tree_t *create_tree (bin_tree_t *left, bin_tree_t *right,
122: re_token_type_t type, int index);
123: static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
124:
125: /* This table gives an error message for each of the error codes listed
126: in regex.h. Obviously the order here has to be same as there.
127: POSIX doesn't require that we do anything for REG_NOERROR,
128: but why not be nice? */
129:
130: const char __re_error_msgid[] attribute_hidden =
131: {
132: #define REG_NOERROR_IDX 0
133: gettext_noop ("Success") /* REG_NOERROR */
134: "\0"
135: #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
136: gettext_noop ("No match") /* REG_NOMATCH */
137: "\0"
138: #define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
139: gettext_noop ("Invalid regular expression") /* REG_BADPAT */
140: "\0"
141: #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
142: gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
143: "\0"
144: #define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
145: gettext_noop ("Invalid character class name") /* REG_ECTYPE */
146: "\0"
147: #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
148: gettext_noop ("Trailing backslash") /* REG_EESCAPE */
149: "\0"
150: #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
151: gettext_noop ("Invalid back reference") /* REG_ESUBREG */
152: "\0"
153: #define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
154: gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
155: "\0"
156: #define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
157: gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
158: "\0"
159: #define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
160: gettext_noop ("Unmatched \\{") /* REG_EBRACE */
161: "\0"
162: #define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
163: gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
164: "\0"
165: #define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
166: gettext_noop ("Invalid range end") /* REG_ERANGE */
167: "\0"
168: #define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
169: gettext_noop ("Memory exhausted") /* REG_ESPACE */
170: "\0"
171: #define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
172: gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
173: "\0"
174: #define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
175: gettext_noop ("Premature end of regular expression") /* REG_EEND */
176: "\0"
177: #define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
178: gettext_noop ("Regular expression too big") /* REG_ESIZE */
179: "\0"
180: #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
181: gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
182: };
183:
184: const size_t __re_error_msgid_idx[] attribute_hidden =
185: {
186: REG_NOERROR_IDX,
187: REG_NOMATCH_IDX,
188: REG_BADPAT_IDX,
189: REG_ECOLLATE_IDX,
190: REG_ECTYPE_IDX,
191: REG_EESCAPE_IDX,
192: REG_ESUBREG_IDX,
193: REG_EBRACK_IDX,
194: REG_EPAREN_IDX,
195: REG_EBRACE_IDX,
196: REG_BADBR_IDX,
197: REG_ERANGE_IDX,
198: REG_ESPACE_IDX,
199: REG_BADRPT_IDX,
200: REG_EEND_IDX,
201: REG_ESIZE_IDX,
202: REG_ERPAREN_IDX
203: };
204:
205: /* Entry points for GNU code. */
206:
207: /* re_compile_pattern is the GNU regular expression compiler: it
208: compiles PATTERN (of length LENGTH) and puts the result in BUFP.
209: Returns 0 if the pattern was valid, otherwise an error string.
210:
211: Assumes the `allocated' (and perhaps `buffer') and `translate' fields
212: are set in BUFP on entry. */
213:
214: const char *
215: re_compile_pattern (pattern, length, bufp)
216: const char *pattern;
217: size_t length;
218: struct re_pattern_buffer *bufp;
219: {
220: reg_errcode_t ret;
221:
222: /* And GNU code determines whether or not to get register information
223: by passing null for the REGS argument to re_match, etc., not by
224: setting no_sub. */
225: bufp->no_sub = 0;
226:
227: /* Match anchors at newline. */
228: bufp->newline_anchor = 1;
229:
230: ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
231:
232: if (!ret)
233: return NULL;
234: return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
235: }
236: #ifdef _LIBC
237: weak_alias (__re_compile_pattern, re_compile_pattern)
238: #endif
239:
240: /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
241: also be assigned to arbitrarily: each pattern buffer stores its own
242: syntax, so it can be changed between regex compilations. */
243: /* This has no initializer because initialized variables in Emacs
244: become read-only after dumping. */
245: reg_syntax_t re_syntax_options;
246:
247:
248: /* Specify the precise syntax of regexps for compilation. This provides
249: for compatibility for various utilities which historically have
250: different, incompatible syntaxes.
251:
252: The argument SYNTAX is a bit mask comprised of the various bits
253: defined in regex.h. We return the old syntax. */
254:
255: reg_syntax_t
256: re_set_syntax (syntax)
257: reg_syntax_t syntax;
258: {
259: reg_syntax_t ret = re_syntax_options;
260:
261: re_syntax_options = syntax;
262: return ret;
263: }
264: #ifdef _LIBC
265: weak_alias (__re_set_syntax, re_set_syntax)
266: #endif
267:
268: int
269: re_compile_fastmap (bufp)
270: struct re_pattern_buffer *bufp;
271: {
272: re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
273: char *fastmap = bufp->fastmap;
274:
275: memset (fastmap, '\0', sizeof (char) * SBC_MAX);
276: re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
277: if (dfa->init_state != dfa->init_state_word)
278: re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
279: if (dfa->init_state != dfa->init_state_nl)
280: re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
281: if (dfa->init_state != dfa->init_state_begbuf)
282: re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
283: bufp->fastmap_accurate = 1;
284: return 0;
285: }
286: #ifdef _LIBC
287: weak_alias (__re_compile_fastmap, re_compile_fastmap)
288: #endif
289:
290: static inline void
291: re_set_fastmap (char *fastmap, int icase, int ch)
292: {
293: fastmap[ch] = 1;
294: if (icase)
295: fastmap[tolower (ch)] = 1;
296: }
297:
298: /* Helper function for re_compile_fastmap.
299: Compile fastmap for the initial_state INIT_STATE. */
300:
301: static void
302: re_compile_fastmap_iter (bufp, init_state, fastmap)
303: regex_t *bufp;
304: const re_dfastate_t *init_state;
305: char *fastmap;
306: {
307: re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
308: int node_cnt;
309: int icase = (MB_CUR_MAX == 1 && (bufp->syntax & RE_ICASE));
310: for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
311: {
312: int node = init_state->nodes.elems[node_cnt];
313: re_token_type_t type = dfa->nodes[node].type;
314:
315: if (type == CHARACTER)
316: re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
317: else if (type == SIMPLE_BRACKET)
318: {
319: int i, j, ch;
320: for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
321: for (j = 0; j < UINT_BITS; ++j, ++ch)
322: if (dfa->nodes[node].opr.sbcset[i] & (1 << j))
323: re_set_fastmap (fastmap, icase, ch);
324: }
325: #ifdef RE_ENABLE_I18N
326: else if (type == COMPLEX_BRACKET)
327: {
328: int i;
329: re_charset_t *cset = dfa->nodes[node].opr.mbcset;
330: if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes
331: || cset->nranges || cset->nchar_classes)
332: {
333: # ifdef _LIBC
334: if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0)
335: {
336: /* In this case we want to catch the bytes which are
337: the first byte of any collation elements.
338: e.g. In da_DK, we want to catch 'a' since "aa"
339: is a valid collation element, and don't catch
340: 'b' since 'b' is the only collation element
341: which starts from 'b'. */
342: int j, ch;
343: const int32_t *table = (const int32_t *)
344: _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
345: for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
346: for (j = 0; j < UINT_BITS; ++j, ++ch)
347: if (table[ch] < 0)
348: re_set_fastmap (fastmap, icase, ch);
349: }
350: # else
351: if (MB_CUR_MAX > 1)
352: for (i = 0; i < SBC_MAX; ++i)
353: if (__btowc (i) == WEOF)
354: re_set_fastmap (fastmap, icase, i);
355: # endif /* not _LIBC */
356: }
357: for (i = 0; i < cset->nmbchars; ++i)
358: {
359: char buf[256];
360: mbstate_t state;
361: memset (&state, '\0', sizeof (state));
362: __wcrtomb (buf, cset->mbchars[i], &state);
363: re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
364: }
365: }
366: #endif /* RE_ENABLE_I18N */
367: else if (type == END_OF_RE || type == OP_PERIOD)
368: {
369: memset (fastmap, '\1', sizeof (char) * SBC_MAX);
370: if (type == END_OF_RE)
371: bufp->can_be_null = 1;
372: return;
373: }
374: }
375: }
376:
377: /* Entry point for POSIX code. */
378: /* regcomp takes a regular expression as a string and compiles it.
379:
380: PREG is a regex_t *. We do not expect any fields to be initialized,
381: since POSIX says we shouldn't. Thus, we set
382:
383: `buffer' to the compiled pattern;
384: `used' to the length of the compiled pattern;
385: `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
386: REG_EXTENDED bit in CFLAGS is set; otherwise, to
387: RE_SYNTAX_POSIX_BASIC;
388: `newline_anchor' to REG_NEWLINE being set in CFLAGS;
389: `fastmap' to an allocated space for the fastmap;
390: `fastmap_accurate' to zero;
391: `re_nsub' to the number of subexpressions in PATTERN.
392:
393: PATTERN is the address of the pattern string.
394:
395: CFLAGS is a series of bits which affect compilation.
396:
397: If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
398: use POSIX basic syntax.
399:
400: If REG_NEWLINE is set, then . and [^...] don't match newline.
401: Also, regexec will try a match beginning after every newline.
402:
403: If REG_ICASE is set, then we considers upper- and lowercase
404: versions of letters to be equivalent when matching.
405:
406: If REG_NOSUB is set, then when PREG is passed to regexec, that
407: routine will report only success or failure, and nothing about the
408: registers.
409:
410: It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
411: the return codes and their meanings.) */
412:
413: int
414: regcomp (preg, pattern, cflags)
415: regex_t *__restrict preg;
416: const char *__restrict pattern;
417: int cflags;
418: {
419: reg_errcode_t ret;
420: reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
421: : RE_SYNTAX_POSIX_BASIC);
422:
423: preg->buffer = NULL;
424: preg->allocated = 0;
425: preg->used = 0;
426:
427: /* Try to allocate space for the fastmap. */
428: preg->fastmap = re_malloc (char, SBC_MAX);
429: if (BE (preg->fastmap == NULL, 0))
430: return REG_ESPACE;
431:
432: syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;
433:
434: /* If REG_NEWLINE is set, newlines are treated differently. */
435: if (cflags & REG_NEWLINE)
436: { /* REG_NEWLINE implies neither . nor [^...] match newline. */
437: syntax &= ~RE_DOT_NEWLINE;
438: syntax |= RE_HAT_LISTS_NOT_NEWLINE;
439: /* It also changes the matching behavior. */
440: preg->newline_anchor = 1;
441: }
442: else
443: preg->newline_anchor = 0;
444: preg->no_sub = !!(cflags & REG_NOSUB);
445: preg->translate = NULL;
446:
447: ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
448:
449: /* POSIX doesn't distinguish between an unmatched open-group and an
450: unmatched close-group: both are REG_EPAREN. */
451: if (ret == REG_ERPAREN)
452: ret = REG_EPAREN;
453:
454: /* We have already checked preg->fastmap != NULL. */
455: if (BE (ret == REG_NOERROR, 1))
456: /* Compute the fastmap now, since regexec cannot modify the pattern
457: buffer. This function nevers fails in this implementation. */
458: (void) re_compile_fastmap (preg);
459: else
460: {
461: /* Some error occurred while compiling the expression. */
462: re_free (preg->fastmap);
463: preg->fastmap = NULL;
464: }
465:
466: return (int) ret;
467: }
468: #ifdef _LIBC
469: weak_alias (__regcomp, regcomp)
470: #endif
471:
472: /* Returns a message corresponding to an error code, ERRCODE, returned
473: from either regcomp or regexec. We don't use PREG here. */
474:
475: size_t
476: regerror (errcode, preg, errbuf, errbuf_size)
477: int errcode;
478: const regex_t *preg;
479: char *errbuf;
480: size_t errbuf_size;
481: {
482: const char *msg;
483: size_t msg_size;
484:
485: if (BE (errcode < 0
486: || errcode >= (int) (sizeof (__re_error_msgid_idx)
487: / sizeof (__re_error_msgid_idx[0])), 0))
488: /* Only error codes returned by the rest of the code should be passed
489: to this routine. If we are given anything else, or if other regex
490: code generates an invalid error code, then the program has a bug.
491: Dump core so we can fix it. */
492: abort ();
493:
494: msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
495:
496: msg_size = strlen (msg) + 1; /* Includes the null. */
497:
498: if (BE (errbuf_size != 0, 1))
499: {
500: if (BE (msg_size > errbuf_size, 0))
501: {
502: #if defined HAVE_MEMPCPY || defined _LIBC
503: *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
504: #else
505: memcpy (errbuf, msg, errbuf_size - 1);
506: errbuf[errbuf_size - 1] = 0;
507: #endif
508: }
509: else
510: memcpy (errbuf, msg, msg_size);
511: }
512:
513: return msg_size;
514: }
515: #ifdef _LIBC
516: weak_alias (__regerror, regerror)
517: #endif
518:
519:
520: static void
521: free_dfa_content (re_dfa_t *dfa)
522: {
523: int i, j;
524:
525: re_free (dfa->subexps);
526:
527: for (i = 0; i < dfa->nodes_len; ++i)
528: {
529: re_token_t *node = dfa->nodes + i;
530: #ifdef RE_ENABLE_I18N
531: if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
532: free_charset (node->opr.mbcset);
533: else
534: #endif /* RE_ENABLE_I18N */
535: if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
536: re_free (node->opr.sbcset);
537: }
538: re_free (dfa->nexts);
539: for (i = 0; i < dfa->nodes_len; ++i)
540: {
541: if (dfa->eclosures != NULL)
542: re_node_set_free (dfa->eclosures + i);
543: if (dfa->inveclosures != NULL)
544: re_node_set_free (dfa->inveclosures + i);
545: if (dfa->edests != NULL)
546: re_node_set_free (dfa->edests + i);
547: }
548: re_free (dfa->edests);
549: re_free (dfa->eclosures);
550: re_free (dfa->inveclosures);
551: re_free (dfa->nodes);
552:
553: for (i = 0; i <= dfa->state_hash_mask; ++i)
554: {
555: struct re_state_table_entry *entry = dfa->state_table + i;
556: for (j = 0; j < entry->num; ++j)
557: {
558: re_dfastate_t *state = entry->array[j];
559: free_state (state);
560: }
561: re_free (entry->array);
562: }
563: re_free (dfa->state_table);
564:
565: if (dfa->word_char != NULL)
566: re_free (dfa->word_char);
567: #ifdef DEBUG
568: re_free (dfa->re_str);
569: #endif
570:
571: re_free (dfa);
572: }
573:
574:
575: /* Free dynamically allocated space used by PREG. */
576:
577: void
578: regfree (preg)
579: regex_t *preg;
580: {
581: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
582: if (BE (dfa != NULL, 1))
583: free_dfa_content (dfa);
584:
585: re_free (preg->fastmap);
586: }
587: #ifdef _LIBC
588: weak_alias (__regfree, regfree)
589: #endif
590:
591: /* Entry points compatible with 4.2 BSD regex library. We don't define
592: them unless specifically requested. */
593:
594: #if defined _REGEX_RE_COMP || defined _LIBC
595:
596: /* BSD has one and only one pattern buffer. */
597: static struct re_pattern_buffer re_comp_buf;
598:
599: char *
600: # ifdef _LIBC
601: /* Make these definitions weak in libc, so POSIX programs can redefine
602: these names if they don't use our functions, and still use
603: regcomp/regexec above without link errors. */
604: weak_function
605: # endif
606: re_comp (s)
607: const char *s;
608: {
609: reg_errcode_t ret;
610: char *fastmap;
611:
612: if (!s)
613: {
614: if (!re_comp_buf.buffer)
615: return gettext ("No previous regular expression");
616: return 0;
617: }
618:
619: if (re_comp_buf.buffer)
620: {
621: fastmap = re_comp_buf.fastmap;
622: re_comp_buf.fastmap = NULL;
623: __regfree (&re_comp_buf);
624: memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
625: re_comp_buf.fastmap = fastmap;
626: }
627:
628: if (re_comp_buf.fastmap == NULL)
629: {
630: re_comp_buf.fastmap = (char *) malloc (SBC_MAX);
631: if (re_comp_buf.fastmap == NULL)
632: return (char *) gettext (__re_error_msgid
633: + __re_error_msgid_idx[(int) REG_ESPACE]);
634: }
635:
636: /* Since `re_exec' always passes NULL for the `regs' argument, we
637: don't need to initialize the pattern buffer fields which affect it. */
638:
639: /* Match anchors at newlines. */
640: re_comp_buf.newline_anchor = 1;
641:
642: ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
643:
644: if (!ret)
645: return NULL;
646:
647: /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
648: return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
649: }
650:
651: #ifdef _LIBC
652: libc_freeres_fn (free_mem)
653: {
654: __regfree (&re_comp_buf);
655: }
656: #endif
657:
658: #endif /* _REGEX_RE_COMP */
659:
660: /* Internal entry point.
661: Compile the regular expression PATTERN, whose length is LENGTH.
662: SYNTAX indicate regular expression's syntax. */
663:
664: static reg_errcode_t
665: re_compile_internal (preg, pattern, length, syntax)
666: regex_t *preg;
667: const char * pattern;
668: int length;
669: reg_syntax_t syntax;
670: {
671: reg_errcode_t err = REG_NOERROR;
672: re_dfa_t *dfa;
673: re_string_t regexp;
674:
675: /* Initialize the pattern buffer. */
676: preg->fastmap_accurate = 0;
677: preg->syntax = syntax;
678: preg->not_bol = preg->not_eol = 0;
679: preg->used = 0;
680: preg->re_nsub = 0;
681: preg->can_be_null = 0;
682: preg->regs_allocated = REGS_UNALLOCATED;
683:
684: /* Initialize the dfa. */
685: dfa = (re_dfa_t *) preg->buffer;
686: if (preg->allocated < sizeof (re_dfa_t))
687: {
688: /* If zero allocated, but buffer is non-null, try to realloc
689: enough space. This loses if buffer's address is bogus, but
690: that is the user's responsibility. If ->buffer is NULL this
691: is a simple allocation. */
692: dfa = re_realloc (preg->buffer, re_dfa_t, 1);
693: if (dfa == NULL)
694: return REG_ESPACE;
695: preg->allocated = sizeof (re_dfa_t);
696: }
697: preg->buffer = (unsigned char *) dfa;
698: preg->used = sizeof (re_dfa_t);
699:
700: err = init_dfa (dfa, length);
701: if (BE (err != REG_NOERROR, 0))
702: {
703: re_free (dfa);
704: preg->buffer = NULL;
705: preg->allocated = 0;
706: return err;
707: }
708: #ifdef DEBUG
709: dfa->re_str = re_malloc (char, length + 1);
710: strncpy (dfa->re_str, pattern, length + 1);
711: #endif
712:
713: err = re_string_construct (®exp, pattern, length, preg->translate,
714: syntax & RE_ICASE);
715: if (BE (err != REG_NOERROR, 0))
716: {
717: re_free (dfa);
718: preg->buffer = NULL;
719: preg->allocated = 0;
720: return err;
721: }
722:
723: /* Parse the regular expression, and build a structure tree. */
724: preg->re_nsub = 0;
725: dfa->str_tree = parse (®exp, preg, syntax, &err);
726: if (BE (dfa->str_tree == NULL, 0))
727: goto re_compile_internal_free_return;
728:
729: /* Analyze the tree and collect information which is necessary to
730: create the dfa. */
731: err = analyze (dfa);
732: if (BE (err != REG_NOERROR, 0))
733: goto re_compile_internal_free_return;
734:
735: /* Then create the initial state of the dfa. */
736: err = create_initial_state (dfa);
737:
738: /* Release work areas. */
739: free_workarea_compile (preg);
740: re_string_destruct (®exp);
741:
742: if (BE (err != REG_NOERROR, 0))
743: {
744: re_compile_internal_free_return:
745: free_dfa_content (dfa);
746: preg->buffer = NULL;
747: preg->allocated = 0;
748: }
749:
750: return err;
751: }
752:
753: /* Initialize DFA. We use the length of the regular expression PAT_LEN
754: as the initial length of some arrays. */
755:
756: static reg_errcode_t
757: init_dfa (dfa, pat_len)
758: re_dfa_t *dfa;
759: int pat_len;
760: {
761: int table_size;
762:
763: memset (dfa, '\0', sizeof (re_dfa_t));
764:
765: dfa->nodes_alloc = pat_len + 1;
766: dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
767:
768: dfa->states_alloc = pat_len + 1;
769:
770: /* table_size = 2 ^ ceil(log pat_len) */
771: for (table_size = 1; table_size > 0; table_size <<= 1)
772: if (table_size > pat_len)
773: break;
774:
775: dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size);
776: dfa->state_hash_mask = table_size - 1;
777:
778: dfa->subexps_alloc = 1;
779: dfa->subexps = re_malloc (re_subexp_t, dfa->subexps_alloc);
780: dfa->word_char = NULL;
781:
782: if (BE (dfa->nodes == NULL || dfa->state_table == NULL
783: || dfa->subexps == NULL, 0))
784: {
785: /* We don't bother to free anything which was allocated. Very
786: soon the process will go down anyway. */
787: dfa->subexps = NULL;
788: dfa->state_table = NULL;
789: dfa->nodes = NULL;
790: return REG_ESPACE;
791: }
792: return REG_NOERROR;
793: }
794:
795: /* Initialize WORD_CHAR table, which indicate which character is
796: "word". In this case "word" means that it is the word construction
797: character used by some operators like "\<", "\>", etc. */
798:
799: static reg_errcode_t
800: init_word_char (dfa)
801: re_dfa_t *dfa;
802: {
803: int i, j, ch;
804: dfa->word_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1);
805: if (BE (dfa->word_char == NULL, 0))
806: return REG_ESPACE;
807: for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
808: for (j = 0; j < UINT_BITS; ++j, ++ch)
809: if (isalnum (ch) || ch == '_')
810: dfa->word_char[i] |= 1 << j;
811: return REG_NOERROR;
812: }
813:
814: /* Free the work area which are only used while compiling. */
815:
816: static void
817: free_workarea_compile (preg)
818: regex_t *preg;
819: {
820: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
821: free_bin_tree (dfa->str_tree);
822: dfa->str_tree = NULL;
823: re_free (dfa->org_indices);
824: dfa->org_indices = NULL;
825: }
826:
827: /* Create initial states for all contexts. */
828:
829: static reg_errcode_t
830: create_initial_state (dfa)
831: re_dfa_t *dfa;
832: {
833: int first, i;
834: reg_errcode_t err;
835: re_node_set init_nodes;
836:
837: /* Initial states have the epsilon closure of the node which is
838: the first node of the regular expression. */
839: first = dfa->str_tree->first;
840: dfa->init_node = first;
841: err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
842: if (BE (err != REG_NOERROR, 0))
843: return err;
844:
845: /* The back-references which are in initial states can epsilon transit,
846: since in this case all of the subexpressions can be null.
847: Then we add epsilon closures of the nodes which are the next nodes of
848: the back-references. */
849: if (dfa->nbackref > 0)
850: for (i = 0; i < init_nodes.nelem; ++i)
851: {
852: int node_idx = init_nodes.elems[i];
853: re_token_type_t type = dfa->nodes[node_idx].type;
854:
855: int clexp_idx;
856: if (type != OP_BACK_REF)
857: continue;
858: for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
859: {
860: re_token_t *clexp_node;
861: clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
862: if (clexp_node->type == OP_CLOSE_SUBEXP
863: && clexp_node->opr.idx + 1 == dfa->nodes[node_idx].opr.idx)
864: break;
865: }
866: if (clexp_idx == init_nodes.nelem)
867: continue;
868:
869: if (type == OP_BACK_REF)
870: {
871: int dest_idx = dfa->edests[node_idx].elems[0];
872: if (!re_node_set_contains (&init_nodes, dest_idx))
873: {
874: re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
875: i = 0;
876: }
877: }
878: }
879:
880: /* It must be the first time to invoke acquire_state. */
881: dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
882: /* We don't check ERR here, since the initial state must not be NULL. */
883: if (BE (dfa->init_state == NULL, 0))
884: return err;
885: if (dfa->init_state->has_constraint)
886: {
887: dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
888: CONTEXT_WORD);
889: dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
890: CONTEXT_NEWLINE);
891: dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
892: &init_nodes,
893: CONTEXT_NEWLINE
894: | CONTEXT_BEGBUF);
895: if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
896: || dfa->init_state_begbuf == NULL, 0))
897: return err;
898: }
899: else
900: dfa->init_state_word = dfa->init_state_nl
901: = dfa->init_state_begbuf = dfa->init_state;
902:
903: re_node_set_free (&init_nodes);
904: return REG_NOERROR;
905: }
906:
907: /* Analyze the structure tree, and calculate "first", "next", "edest",
908: "eclosure", and "inveclosure". */
909:
910: static reg_errcode_t
911: analyze (dfa)
912: re_dfa_t *dfa;
913: {
914: int i;
915: reg_errcode_t ret;
916:
917: /* Allocate arrays. */
918: dfa->nexts = re_malloc (int, dfa->nodes_alloc);
919: dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
920: dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
921: dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
922: dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);
923: if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
924: || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
925: return REG_ESPACE;
926: /* Initialize them. */
927: for (i = 0; i < dfa->nodes_len; ++i)
928: {
929: dfa->nexts[i] = -1;
930: re_node_set_init_empty (dfa->edests + i);
931: re_node_set_init_empty (dfa->eclosures + i);
932: re_node_set_init_empty (dfa->inveclosures + i);
933: }
934:
935: ret = analyze_tree (dfa, dfa->str_tree);
936: if (BE (ret == REG_NOERROR, 1))
937: {
938: ret = calc_eclosure (dfa);
939: if (ret == REG_NOERROR)
940: calc_inveclosure (dfa);
941: }
942: return ret;
943: }
944:
945: /* Helper functions for analyze.
946: This function calculate "first", "next", and "edest" for the subtree
947: whose root is NODE. */
948:
949: static reg_errcode_t
950: analyze_tree (dfa, node)
951: re_dfa_t *dfa;
952: bin_tree_t *node;
953: {
954: reg_errcode_t ret;
955: if (node->first == -1)
956: calc_first (dfa, node);
957: if (node->next == -1)
958: calc_next (dfa, node);
959: if (node->eclosure.nelem == 0)
960: calc_epsdest (dfa, node);
961: /* Calculate "first" etc. for the left child. */
962: if (node->left != NULL)
963: {
964: ret = analyze_tree (dfa, node->left);
965: if (BE (ret != REG_NOERROR, 0))
966: return ret;
967: }
968: /* Calculate "first" etc. for the right child. */
969: if (node->right != NULL)
970: {
971: ret = analyze_tree (dfa, node->right);
972: if (BE (ret != REG_NOERROR, 0))
973: return ret;
974: }
975: return REG_NOERROR;
976: }
977:
978: /* Calculate "first" for the node NODE. */
979: static void
980: calc_first (dfa, node)
981: re_dfa_t *dfa;
982: bin_tree_t *node;
983: {
984: int idx, type;
985: idx = node->node_idx;
986: type = (node->type == 0) ? dfa->nodes[idx].type : node->type;
987:
988: switch (type)
989: {
990: #ifdef DEBUG
991: case OP_OPEN_BRACKET:
992: case OP_CLOSE_BRACKET:
993: case OP_OPEN_DUP_NUM:
994: case OP_CLOSE_DUP_NUM:
995: case OP_NON_MATCH_LIST:
996: case OP_OPEN_COLL_ELEM:
997: case OP_CLOSE_COLL_ELEM:
998: case OP_OPEN_EQUIV_CLASS:
999: case OP_CLOSE_EQUIV_CLASS:
1000: case OP_OPEN_CHAR_CLASS:
1001: case OP_CLOSE_CHAR_CLASS:
1002: /* These must not be appeared here. */
1003: assert (0);
1004: #endif
1005: case END_OF_RE:
1006: case CHARACTER:
1007: case OP_PERIOD:
1008: case OP_DUP_ASTERISK:
1009: case OP_DUP_QUESTION:
1010: #ifdef RE_ENABLE_I18N
1011: case COMPLEX_BRACKET:
1012: #endif /* RE_ENABLE_I18N */
1013: case SIMPLE_BRACKET:
1014: case OP_BACK_REF:
1015: case ANCHOR:
1016: case OP_OPEN_SUBEXP:
1017: case OP_CLOSE_SUBEXP:
1018: node->first = idx;
1019: break;
1020: case OP_DUP_PLUS:
1021: #ifdef DEBUG
1022: assert (node->left != NULL);
1023: #endif
1024: if (node->left->first == -1)
1025: calc_first (dfa, node->left);
1026: node->first = node->left->first;
1027: break;
1028: case OP_ALT:
1029: node->first = idx;
1030: break;
1031: /* else fall through */
1032: default:
1033: #ifdef DEBUG
1034: assert (node->left != NULL);
1035: #endif
1036: if (node->left->first == -1)
1037: calc_first (dfa, node->left);
1038: node->first = node->left->first;
1039: break;
1040: }
1041: }
1042:
1043: /* Calculate "next" for the node NODE. */
1044:
1045: static void
1046: calc_next (dfa, node)
1047: re_dfa_t *dfa;
1048: bin_tree_t *node;
1049: {
1050: int idx, type;
1051: bin_tree_t *parent = node->parent;
1052: if (parent == NULL)
1053: {
1054: node->next = -1;
1055: idx = node->node_idx;
1056: if (node->type == 0)
1057: dfa->nexts[idx] = node->next;
1058: return;
1059: }
1060:
1061: idx = parent->node_idx;
1062: type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type;
1063:
1064: switch (type)
1065: {
1066: case OP_DUP_ASTERISK:
1067: case OP_DUP_PLUS:
1068: node->next = idx;
1069: break;
1070: case CONCAT:
1071: if (parent->left == node)
1072: {
1073: if (parent->right->first == -1)
1074: calc_first (dfa, parent->right);
1075: node->next = parent->right->first;
1076: break;
1077: }
1078: /* else fall through */
1079: default:
1080: if (parent->next == -1)
1081: calc_next (dfa, parent);
1082: node->next = parent->next;
1083: break;
1084: }
1085: idx = node->node_idx;
1086: if (node->type == 0)
1087: dfa->nexts[idx] = node->next;
1088: }
1089:
1090: /* Calculate "edest" for the node NODE. */
1091:
1092: static void
1093: calc_epsdest (dfa, node)
1094: re_dfa_t *dfa;
1095: bin_tree_t *node;
1096: {
1097: int idx;
1098: idx = node->node_idx;
1099: if (node->type == 0)
1100: {
1101: if (dfa->nodes[idx].type == OP_DUP_ASTERISK
1102: || dfa->nodes[idx].type == OP_DUP_PLUS
1103: || dfa->nodes[idx].type == OP_DUP_QUESTION)
1104: {
1105: if (node->left->first == -1)
1106: calc_first (dfa, node->left);
1107: if (node->next == -1)
1108: calc_next (dfa, node);
1109: re_node_set_init_2 (dfa->edests + idx, node->left->first,
1110: node->next);
1111: }
1112: else if (dfa->nodes[idx].type == OP_ALT)
1113: {
1114: int left, right;
1115: if (node->left != NULL)
1116: {
1117: if (node->left->first == -1)
1118: calc_first (dfa, node->left);
1119: left = node->left->first;
1120: }
1121: else
1122: {
1123: if (node->next == -1)
1124: calc_next (dfa, node);
1125: left = node->next;
1126: }
1127: if (node->right != NULL)
1128: {
1129: if (node->right->first == -1)
1130: calc_first (dfa, node->right);
1131: right = node->right->first;
1132: }
1133: else
1134: {
1135: if (node->next == -1)
1136: calc_next (dfa, node);
1137: right = node->next;
1138: }
1139: re_node_set_init_2 (dfa->edests + idx, left, right);
1140: }
1141: else if (dfa->nodes[idx].type == ANCHOR
1142: || dfa->nodes[idx].type == OP_OPEN_SUBEXP
1143: || dfa->nodes[idx].type == OP_CLOSE_SUBEXP
1144: || dfa->nodes[idx].type == OP_BACK_REF)
1145: re_node_set_init_1 (dfa->edests + idx, node->next);
1146: }
1147: }
1148:
1149: /* Duplicate the epsilon closure of the node ROOT_NODE.
1150: Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1151: to their own constraint. */
1152:
1153: static reg_errcode_t
1154: duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
1155: init_constraint)
1156: re_dfa_t *dfa;
1157: int top_org_node, top_clone_node, root_node;
1158: unsigned int init_constraint;
1159: {
1160: reg_errcode_t err;
1161: int org_node, clone_node, ret;
1162: unsigned int constraint = init_constraint;
1163: for (org_node = top_org_node, clone_node = top_clone_node;;)
1164: {
1165: int org_dest, clone_dest;
1166: if (dfa->nodes[org_node].type == OP_BACK_REF)
1167: {
1168: /* If the back reference epsilon-transit, its destination must
1169: also have the constraint. Then duplicate the epsilon closure
1170: of the destination of the back reference, and store it in
1171: edests of the back reference. */
1172: org_dest = dfa->nexts[org_node];
1173: re_node_set_empty (dfa->edests + clone_node);
1174: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1175: if (BE (err != REG_NOERROR, 0))
1176: return err;
1177: dfa->nexts[clone_node] = dfa->nexts[org_node];
1178: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1179: if (BE (ret < 0, 0))
1180: return REG_ESPACE;
1181: }
1182: else if (dfa->edests[org_node].nelem == 0)
1183: {
1184: /* In case of the node can't epsilon-transit, don't duplicate the
1185: destination and store the original destination as the
1186: destination of the node. */
1187: dfa->nexts[clone_node] = dfa->nexts[org_node];
1188: break;
1189: }
1190: else if (dfa->edests[org_node].nelem == 1)
1191: {
1192: /* In case of the node can epsilon-transit, and it has only one
1193: destination. */
1194: org_dest = dfa->edests[org_node].elems[0];
1195: re_node_set_empty (dfa->edests + clone_node);
1196: if (dfa->nodes[org_node].type == ANCHOR)
1197: {
1198: /* In case of the node has another constraint, append it. */
1199: if (org_node == root_node && clone_node != org_node)
1200: {
1201: /* ...but if the node is root_node itself, it means the
1202: epsilon closure have a loop, then tie it to the
1203: destination of the root_node. */
1204: ret = re_node_set_insert (dfa->edests + clone_node,
1205: org_dest);
1206: if (BE (ret < 0, 0))
1207: return REG_ESPACE;
1208: break;
1209: }
1210: constraint |= dfa->nodes[org_node].opr.ctx_type;
1211: }
1212: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1213: if (BE (err != REG_NOERROR, 0))
1214: return err;
1215: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1216: if (BE (ret < 0, 0))
1217: return REG_ESPACE;
1218: }
1219: else /* dfa->edests[org_node].nelem == 2 */
1220: {
1221: /* In case of the node can epsilon-transit, and it has two
1222: destinations. E.g. '|', '*', '+', '?'. */
1223: org_dest = dfa->edests[org_node].elems[0];
1224: re_node_set_empty (dfa->edests + clone_node);
1225: /* Search for a duplicated node which satisfies the constraint. */
1226: clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1227: if (clone_dest == -1)
1228: {
1229: /* There are no such a duplicated node, create a new one. */
1230: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1231: if (BE (err != REG_NOERROR, 0))
1232: return err;
1233: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1234: if (BE (ret < 0, 0))
1235: return REG_ESPACE;
1236: err = duplicate_node_closure (dfa, org_dest, clone_dest,
1237: root_node, constraint);
1238: if (BE (err != REG_NOERROR, 0))
1239: return err;
1240: }
1241: else
1242: {
1243: /* There are a duplicated node which satisfy the constraint,
1244: use it to avoid infinite loop. */
1245: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1246: if (BE (ret < 0, 0))
1247: return REG_ESPACE;
1248: }
1249:
1250: org_dest = dfa->edests[org_node].elems[1];
1251: err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
1252: if (BE (err != REG_NOERROR, 0))
1253: return err;
1254: ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1255: if (BE (ret < 0, 0))
1256: return REG_ESPACE;
1257: }
1258: org_node = org_dest;
1259: clone_node = clone_dest;
1260: }
1261: return REG_NOERROR;
1262: }
1263:
1264: /* Search for a node which is duplicated from the node ORG_NODE, and
1265: satisfies the constraint CONSTRAINT. */
1266:
1267: static int
1268: search_duplicated_node (dfa, org_node, constraint)
1269: re_dfa_t *dfa;
1270: int org_node;
1271: unsigned int constraint;
1272: {
1273: int idx;
1274: for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
1275: {
1276: if (org_node == dfa->org_indices[idx]
1277: && constraint == dfa->nodes[idx].constraint)
1278: return idx; /* Found. */
1279: }
1280: return -1; /* Not found. */
1281: }
1282:
1283: /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1284: The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
1285: otherwise return the error code. */
1286:
1287: static reg_errcode_t
1288: duplicate_node (new_idx, dfa, org_idx, constraint)
1289: re_dfa_t *dfa;
1290: int *new_idx, org_idx;
1291: unsigned int constraint;
1292: {
1293: re_token_t dup;
1294: int dup_idx;
1295:
1296: dup = dfa->nodes[org_idx];
1297: dup_idx = re_dfa_add_node (dfa, dup, 1);
1298: if (BE (dup_idx == -1, 0))
1299: return REG_ESPACE;
1300: dfa->nodes[dup_idx].constraint = constraint;
1301: if (dfa->nodes[org_idx].type == ANCHOR)
1302: dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
1303: dfa->nodes[dup_idx].duplicated = 1;
1304: re_node_set_init_empty (dfa->edests + dup_idx);
1305: re_node_set_init_empty (dfa->eclosures + dup_idx);
1306: re_node_set_init_empty (dfa->inveclosures + dup_idx);
1307:
1308: /* Store the index of the original node. */
1309: dfa->org_indices[dup_idx] = org_idx;
1310: *new_idx = dup_idx;
1311: return REG_NOERROR;
1312: }
1313:
1314: static void
1315: calc_inveclosure (dfa)
1316: re_dfa_t *dfa;
1317: {
1318: int src, idx, dest;
1319: for (src = 0; src < dfa->nodes_len; ++src)
1320: {
1321: for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1322: {
1323: dest = dfa->eclosures[src].elems[idx];
1324: re_node_set_insert (dfa->inveclosures + dest, src);
1325: }
1326: }
1327: }
1328:
1329: /* Calculate "eclosure" for all the node in DFA. */
1330:
1331: static reg_errcode_t
1332: calc_eclosure (dfa)
1333: re_dfa_t *dfa;
1334: {
1335: int node_idx, incomplete;
1336: #ifdef DEBUG
1337: assert (dfa->nodes_len > 0);
1338: #endif
1339: incomplete = 0;
1340: /* For each nodes, calculate epsilon closure. */
1341: for (node_idx = 0; ; ++node_idx)
1342: {
1343: reg_errcode_t err;
1344: re_node_set eclosure_elem;
1345: if (node_idx == dfa->nodes_len)
1346: {
1347: if (!incomplete)
1348: break;
1349: incomplete = 0;
1350: node_idx = 0;
1351: }
1352:
1353: #ifdef DEBUG
1354: assert (dfa->eclosures[node_idx].nelem != -1);
1355: #endif
1356: /* If we have already calculated, skip it. */
1357: if (dfa->eclosures[node_idx].nelem != 0)
1358: continue;
1359: /* Calculate epsilon closure of `node_idx'. */
1360: err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1);
1361: if (BE (err != REG_NOERROR, 0))
1362: return err;
1363:
1364: if (dfa->eclosures[node_idx].nelem == 0)
1365: {
1366: incomplete = 1;
1367: re_node_set_free (&eclosure_elem);
1368: }
1369: }
1370: return REG_NOERROR;
1371: }
1372:
1373: /* Calculate epsilon closure of NODE. */
1374:
1375: static reg_errcode_t
1376: calc_eclosure_iter (new_set, dfa, node, root)
1377: re_node_set *new_set;
1378: re_dfa_t *dfa;
1379: int node, root;
1380: {
1381: reg_errcode_t err;
1382: unsigned int constraint;
1383: int i, incomplete;
1384: re_node_set eclosure;
1385: incomplete = 0;
1386: err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1387: if (BE (err != REG_NOERROR, 0))
1388: return err;
1389:
1390: /* This indicates that we are calculating this node now.
1391: We reference this value to avoid infinite loop. */
1392: dfa->eclosures[node].nelem = -1;
1393:
1394: constraint = ((dfa->nodes[node].type == ANCHOR)
1395: ? dfa->nodes[node].opr.ctx_type : 0);
1396: /* If the current node has constraints, duplicate all nodes.
1397: Since they must inherit the constraints. */
1398: if (constraint && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1399: {
1400: int org_node, cur_node;
1401: org_node = cur_node = node;
1402: err = duplicate_node_closure (dfa, node, node, node, constraint);
1403: if (BE (err != REG_NOERROR, 0))
1404: return err;
1405: }
1406:
1407: /* Expand each epsilon destination nodes. */
1408: if (IS_EPSILON_NODE(dfa->nodes[node].type))
1409: for (i = 0; i < dfa->edests[node].nelem; ++i)
1410: {
1411: re_node_set eclosure_elem;
1412: int edest = dfa->edests[node].elems[i];
1413: /* If calculating the epsilon closure of `edest' is in progress,
1414: return intermediate result. */
1415: if (dfa->eclosures[edest].nelem == -1)
1416: {
1417: incomplete = 1;
1418: continue;
1419: }
1420: /* If we haven't calculated the epsilon closure of `edest' yet,
1421: calculate now. Otherwise use calculated epsilon closure. */
1422: if (dfa->eclosures[edest].nelem == 0)
1423: {
1424: err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0);
1425: if (BE (err != REG_NOERROR, 0))
1426: return err;
1427: }
1428: else
1429: eclosure_elem = dfa->eclosures[edest];
1430: /* Merge the epsilon closure of `edest'. */
1431: re_node_set_merge (&eclosure, &eclosure_elem);
1432: /* If the epsilon closure of `edest' is incomplete,
1433: the epsilon closure of this node is also incomplete. */
1434: if (dfa->eclosures[edest].nelem == 0)
1435: {
1436: incomplete = 1;
1437: re_node_set_free (&eclosure_elem);
1438: }
1439: }
1440:
1441: /* Epsilon closures include itself. */
1442: re_node_set_insert (&eclosure, node);
1443: if (incomplete && !root)
1444: dfa->eclosures[node].nelem = 0;
1445: else
1446: dfa->eclosures[node] = eclosure;
1447: *new_set = eclosure;
1448: return REG_NOERROR;
1449: }
1450:
1451: /* Functions for token which are used in the parser. */
1452:
1453: /* Fetch a token from INPUT.
1454: We must not use this function inside bracket expressions. */
1455:
1456: static re_token_t
1457: fetch_token (input, syntax)
1458: re_string_t *input;
1459: reg_syntax_t syntax;
1460: {
1461: re_token_t token;
1462: int consumed_byte;
1463: consumed_byte = peek_token (&token, input, syntax);
1464: re_string_skip_bytes (input, consumed_byte);
1465: return token;
1466: }
1467:
1468: /* Peek a token from INPUT, and return the length of the token.
1469: We must not use this function inside bracket expressions. */
1470:
1471: static int
1472: peek_token (token, input, syntax)
1473: re_token_t *token;
1474: re_string_t *input;
1475: reg_syntax_t syntax;
1476: {
1477: unsigned char c;
1478:
1479: if (re_string_eoi (input))
1480: {
1481: token->type = END_OF_RE;
1482: return 0;
1483: }
1484:
1485: c = re_string_peek_byte (input, 0);
1486: token->opr.c = c;
1487:
1488: #ifdef RE_ENABLE_I18N
1489: token->mb_partial = 0;
1490: if (MB_CUR_MAX > 1 &&
1491: !re_string_first_byte (input, re_string_cur_idx (input)))
1492: {
1493: token->type = CHARACTER;
1494: token->mb_partial = 1;
1495: return 1;
1496: }
1497: #endif
1498: if (c == '\\')
1499: {
1500: unsigned char c2;
1501: if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1502: {
1503: token->type = BACK_SLASH;
1504: return 1;
1505: }
1506:
1507: c2 = re_string_peek_byte_case (input, 1);
1508: token->opr.c = c2;
1509: token->type = CHARACTER;
1510: switch (c2)
1511: {
1512: case '|':
1513: if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
1514: token->type = OP_ALT;
1515: break;
1516: case '1': case '2': case '3': case '4': case '5':
1517: case '6': case '7': case '8': case '9':
1518: if (!(syntax & RE_NO_BK_REFS))
1519: {
1520: token->type = OP_BACK_REF;
1521: token->opr.idx = c2 - '0';
1522: }
1523: break;
1524: case '<':
1525: if (!(syntax & RE_NO_GNU_OPS))
1526: {
1527: token->type = ANCHOR;
1528: token->opr.idx = WORD_FIRST;
1529: }
1530: break;
1531: case '>':
1532: if (!(syntax & RE_NO_GNU_OPS))
1533: {
1534: token->type = ANCHOR;
1535: token->opr.idx = WORD_LAST;
1536: }
1537: break;
1538: case 'b':
1539: if (!(syntax & RE_NO_GNU_OPS))
1540: {
1541: token->type = ANCHOR;
1542: token->opr.idx = WORD_DELIM;
1543: }
1544: break;
1545: case 'B':
1546: if (!(syntax & RE_NO_GNU_OPS))
1547: {
1548: token->type = ANCHOR;
1549: token->opr.idx = INSIDE_WORD;
1550: }
1551: break;
1552: case 'w':
1553: if (!(syntax & RE_NO_GNU_OPS))
1554: token->type = OP_WORD;
1555: break;
1556: case 'W':
1557: if (!(syntax & RE_NO_GNU_OPS))
1558: token->type = OP_NOTWORD;
1559: break;
1560: case '`':
1561: if (!(syntax & RE_NO_GNU_OPS))
1562: {
1563: token->type = ANCHOR;
1564: token->opr.idx = BUF_FIRST;
1565: }
1566: break;
1567: case '\'':
1568: if (!(syntax & RE_NO_GNU_OPS))
1569: {
1570: token->type = ANCHOR;
1571: token->opr.idx = BUF_LAST;
1572: }
1573: break;
1574: case '(':
1575: if (!(syntax & RE_NO_BK_PARENS))
1576: token->type = OP_OPEN_SUBEXP;
1577: break;
1578: case ')':
1579: if (!(syntax & RE_NO_BK_PARENS))
1580: token->type = OP_CLOSE_SUBEXP;
1581: break;
1582: case '+':
1583: if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1584: token->type = OP_DUP_PLUS;
1585: break;
1586: case '?':
1587: if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1588: token->type = OP_DUP_QUESTION;
1589: break;
1590: case '{':
1591: if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1592: token->type = OP_OPEN_DUP_NUM;
1593: break;
1594: case '}':
1595: if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1596: token->type = OP_CLOSE_DUP_NUM;
1597: break;
1598: default:
1599: break;
1600: }
1601: return 2;
1602: }
1603:
1604: token->type = CHARACTER;
1605: switch (c)
1606: {
1607: case '\n':
1608: if (syntax & RE_NEWLINE_ALT)
1609: token->type = OP_ALT;
1610: break;
1611: case '|':
1612: if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
1613: token->type = OP_ALT;
1614: break;
1615: case '*':
1616: token->type = OP_DUP_ASTERISK;
1617: break;
1618: case '+':
1619: if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1620: token->type = OP_DUP_PLUS;
1621: break;
1622: case '?':
1623: if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1624: token->type = OP_DUP_QUESTION;
1625: break;
1626: case '{':
1627: if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1628: token->type = OP_OPEN_DUP_NUM;
1629: break;
1630: case '}':
1631: if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1632: token->type = OP_CLOSE_DUP_NUM;
1633: break;
1634: case '(':
1635: if (syntax & RE_NO_BK_PARENS)
1636: token->type = OP_OPEN_SUBEXP;
1637: break;
1638: case ')':
1639: if (syntax & RE_NO_BK_PARENS)
1640: token->type = OP_CLOSE_SUBEXP;
1641: break;
1642: case '[':
1643: token->type = OP_OPEN_BRACKET;
1644: break;
1645: case '.':
1646: token->type = OP_PERIOD;
1647: break;
1648: case '^':
1649: if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1650: re_string_cur_idx (input) != 0)
1651: {
1652: char prev = re_string_peek_byte (input, -1);
1653: if (prev != '|' && prev != '(' &&
1654: (!(syntax & RE_NEWLINE_ALT) || prev != '\n'))
1655: break;
1656: }
1657: token->type = ANCHOR;
1658: token->opr.idx = LINE_FIRST;
1659: break;
1660: case '$':
1661: if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1662: re_string_cur_idx (input) + 1 != re_string_length (input))
1663: {
1664: re_token_t next;
1665: re_string_skip_bytes (input, 1);
1666: peek_token (&next, input, syntax);
1667: re_string_skip_bytes (input, -1);
1668: if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1669: break;
1670: }
1671: token->type = ANCHOR;
1672: token->opr.idx = LINE_LAST;
1673: break;
1674: default:
1675: break;
1676: }
1677: return 1;
1678: }
1679:
1680: /* Peek a token from INPUT, and return the length of the token.
1681: We must not use this function out of bracket expressions. */
1682:
1683: static int
1684: peek_token_bracket (token, input, syntax)
1685: re_token_t *token;
1686: re_string_t *input;
1687: reg_syntax_t syntax;
1688: {
1689: unsigned char c;
1690: if (re_string_eoi (input))
1691: {
1692: token->type = END_OF_RE;
1693: return 0;
1694: }
1695: c = re_string_peek_byte (input, 0);
1696: token->opr.c = c;
1697:
1698: #ifdef RE_ENABLE_I18N
1699: if (MB_CUR_MAX > 1 &&
1700: !re_string_first_byte (input, re_string_cur_idx (input)))
1701: {
1702: token->type = CHARACTER;
1703: return 1;
1704: }
1705: #endif /* RE_ENABLE_I18N */
1706:
1707: if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS))
1708: {
1709: /* In this case, '\' escape a character. */
1710: unsigned char c2;
1711: re_string_skip_bytes (input, 1);
1712: c2 = re_string_peek_byte (input, 0);
1713: token->opr.c = c2;
1714: token->type = CHARACTER;
1715: return 1;
1716: }
1717: if (c == '[') /* '[' is a special char in a bracket exps. */
1718: {
1719: unsigned char c2;
1720: int token_len;
1721: c2 = re_string_peek_byte (input, 1);
1722: token->opr.c = c2;
1723: token_len = 2;
1724: switch (c2)
1725: {
1726: case '.':
1727: token->type = OP_OPEN_COLL_ELEM;
1728: break;
1729: case '=':
1730: token->type = OP_OPEN_EQUIV_CLASS;
1731: break;
1732: case ':':
1733: if (syntax & RE_CHAR_CLASSES)
1734: {
1735: token->type = OP_OPEN_CHAR_CLASS;
1736: break;
1737: }
1738: /* else fall through. */
1739: default:
1740: token->type = CHARACTER;
1741: token->opr.c = c;
1742: token_len = 1;
1743: break;
1744: }
1745: return token_len;
1746: }
1747: switch (c)
1748: {
1749: case '-':
1750: token->type = OP_CHARSET_RANGE;
1751: break;
1752: case ']':
1753: token->type = OP_CLOSE_BRACKET;
1754: break;
1755: case '^':
1756: token->type = OP_NON_MATCH_LIST;
1757: break;
1758: default:
1759: token->type = CHARACTER;
1760: }
1761: return 1;
1762: }
1763:
1764: /* Functions for parser. */
1765:
1766: /* Entry point of the parser.
1767: Parse the regular expression REGEXP and return the structure tree.
1768: If an error is occured, ERR is set by error code, and return NULL.
1769: This function build the following tree, from regular expression <reg_exp>:
1770: CAT
1771: / \
1772: / \
1773: <reg_exp> EOR
1774:
1775: CAT means concatenation.
1776: EOR means end of regular expression. */
1777:
1778: static bin_tree_t *
1779: parse (regexp, preg, syntax, err)
1780: re_string_t *regexp;
1781: regex_t *preg;
1782: reg_syntax_t syntax;
1783: reg_errcode_t *err;
1784: {
1785: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1786: bin_tree_t *tree, *eor, *root;
1787: re_token_t current_token;
1788: int new_idx;
1789: current_token = fetch_token (regexp, syntax);
1790: tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
1791: if (BE (*err != REG_NOERROR && tree == NULL, 0))
1792: return NULL;
1793: new_idx = re_dfa_add_node (dfa, current_token, 0);
1794: eor = create_tree (NULL, NULL, 0, new_idx);
1795: if (tree != NULL)
1796: root = create_tree (tree, eor, CONCAT, 0);
1797: else
1798: root = eor;
1799: if (BE (new_idx == -1 || eor == NULL || root == NULL, 0))
1800: {
1801: *err = REG_ESPACE;
1802: return NULL;
1803: }
1804: return root;
1805: }
1806:
1807: /* This function build the following tree, from regular expression
1808: <branch1>|<branch2>:
1809: ALT
1810: / \
1811: / \
1812: <branch1> <branch2>
1813:
1814: ALT means alternative, which represents the operator `|'. */
1815:
1816: static bin_tree_t *
1817: parse_reg_exp (regexp, preg, token, syntax, nest, err)
1818: re_string_t *regexp;
1819: regex_t *preg;
1820: re_token_t *token;
1821: reg_syntax_t syntax;
1822: int nest;
1823: reg_errcode_t *err;
1824: {
1825: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1826: bin_tree_t *tree, *branch = NULL;
1827: int new_idx;
1828: tree = parse_branch (regexp, preg, token, syntax, nest, err);
1829: if (BE (*err != REG_NOERROR && tree == NULL, 0))
1830: return NULL;
1831:
1832: while (token->type == OP_ALT)
1833: {
1834: re_token_t alt_token = *token;
1835: new_idx = re_dfa_add_node (dfa, alt_token, 0);
1836: *token = fetch_token (regexp, syntax);
1837: if (token->type != OP_ALT && token->type != END_OF_RE
1838: && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
1839: {
1840: branch = parse_branch (regexp, preg, token, syntax, nest, err);
1841: if (BE (*err != REG_NOERROR && branch == NULL, 0))
1842: {
1843: free_bin_tree (tree);
1844: return NULL;
1845: }
1846: }
1847: else
1848: branch = NULL;
1849: tree = create_tree (tree, branch, 0, new_idx);
1850: if (BE (new_idx == -1 || tree == NULL, 0))
1851: {
1852: *err = REG_ESPACE;
1853: return NULL;
1854: }
1855: dfa->has_plural_match = 1;
1856: }
1857: return tree;
1858: }
1859:
1860: /* This function build the following tree, from regular expression
1861: <exp1><exp2>:
1862: CAT
1863: / \
1864: / \
1865: <exp1> <exp2>
1866:
1867: CAT means concatenation. */
1868:
1869: static bin_tree_t *
1870: parse_branch (regexp, preg, token, syntax, nest, err)
1871: re_string_t *regexp;
1872: regex_t *preg;
1873: re_token_t *token;
1874: reg_syntax_t syntax;
1875: int nest;
1876: reg_errcode_t *err;
1877: {
1878: bin_tree_t *tree, *exp;
1879: tree = parse_expression (regexp, preg, token, syntax, nest, err);
1880: if (BE (*err != REG_NOERROR && tree == NULL, 0))
1881: return NULL;
1882:
1883: while (token->type != OP_ALT && token->type != END_OF_RE
1884: && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
1885: {
1886: exp = parse_expression (regexp, preg, token, syntax, nest, err);
1887: if (BE (*err != REG_NOERROR && exp == NULL, 0))
1888: {
1889: free_bin_tree (tree);
1890: return NULL;
1891: }
1892: if (tree != NULL && exp != NULL)
1893: {
1894: tree = create_tree (tree, exp, CONCAT, 0);
1895: if (tree == NULL)
1896: {
1897: *err = REG_ESPACE;
1898: return NULL;
1899: }
1900: }
1901: else if (tree == NULL)
1902: tree = exp;
1903: /* Otherwise exp == NULL, we don't need to create new tree. */
1904: }
1905: return tree;
1906: }
1907:
1908: /* This function build the following tree, from regular expression a*:
1909: *
1910: |
1911: a
1912: */
1913:
1914: static bin_tree_t *
1915: parse_expression (regexp, preg, token, syntax, nest, err)
1916: re_string_t *regexp;
1917: regex_t *preg;
1918: re_token_t *token;
1919: reg_syntax_t syntax;
1920: int nest;
1921: reg_errcode_t *err;
1922: {
1923: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1924: bin_tree_t *tree;
1925: int new_idx;
1926: switch (token->type)
1927: {
1928: case CHARACTER:
1929: new_idx = re_dfa_add_node (dfa, *token, 0);
1930: tree = create_tree (NULL, NULL, 0, new_idx);
1931: if (BE (new_idx == -1 || tree == NULL, 0))
1932: {
1933: *err = REG_ESPACE;
1934: return NULL;
1935: }
1936: #ifdef RE_ENABLE_I18N
1937: if (MB_CUR_MAX > 1)
1938: {
1939: while (!re_string_eoi (regexp)
1940: && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
1941: {
1942: bin_tree_t *mbc_remain;
1943: *token = fetch_token (regexp, syntax);
1944: new_idx = re_dfa_add_node (dfa, *token, 0);
1945: mbc_remain = create_tree (NULL, NULL, 0, new_idx);
1946: tree = create_tree (tree, mbc_remain, CONCAT, 0);
1947: if (BE (new_idx == -1 || mbc_remain == NULL || tree == NULL, 0))
1948: {
1949: *err = REG_ESPACE;
1950: return NULL;
1951: }
1952: }
1953: }
1954: #endif
1955: break;
1956: case OP_OPEN_SUBEXP:
1957: tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
1958: if (BE (*err != REG_NOERROR && tree == NULL, 0))
1959: return NULL;
1960: break;
1961: case OP_OPEN_BRACKET:
1962: tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
1963: if (BE (*err != REG_NOERROR && tree == NULL, 0))
1964: return NULL;
1965: break;
1966: case OP_BACK_REF:
1967: if (BE (preg->re_nsub < token->opr.idx
1968: || dfa->subexps[token->opr.idx - 1].end == -1, 0))
1969: {
1970: *err = REG_ESUBREG;
1971: return NULL;
1972: }
1973: dfa->used_bkref_map |= 1 << (token->opr.idx - 1);
1974: new_idx = re_dfa_add_node (dfa, *token, 0);
1975: tree = create_tree (NULL, NULL, 0, new_idx);
1976: if (BE (new_idx == -1 || tree == NULL, 0))
1977: {
1978: *err = REG_ESPACE;
1979: return NULL;
1980: }
1981: ++dfa->nbackref;
1982: dfa->has_mb_node = 1;
1983: break;
1984: case OP_DUP_ASTERISK:
1985: case OP_DUP_PLUS:
1986: case OP_DUP_QUESTION:
1987: case OP_OPEN_DUP_NUM:
1988: if (syntax & RE_CONTEXT_INVALID_OPS)
1989: {
1990: *err = REG_BADRPT;
1991: return NULL;
1992: }
1993: else if (syntax & RE_CONTEXT_INDEP_OPS)
1994: {
1995: *token = fetch_token (regexp, syntax);
1996: return parse_expression (regexp, preg, token, syntax, nest, err);
1997: }
1998: /* else fall through */
1999: case OP_CLOSE_SUBEXP:
2000: if ((token->type == OP_CLOSE_SUBEXP) &&
2001: !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
2002: {
2003: *err = REG_ERPAREN;
2004: return NULL;
2005: }
2006: /* else fall through */
2007: case OP_CLOSE_DUP_NUM:
2008: /* We treat it as a normal character. */
2009:
2010: /* Then we can these characters as normal characters. */
2011: token->type = CHARACTER;
2012: new_idx = re_dfa_add_node (dfa, *token, 0);
2013: tree = create_tree (NULL, NULL, 0, new_idx);
2014: if (BE (new_idx == -1 || tree == NULL, 0))
2015: {
2016: *err = REG_ESPACE;
2017: return NULL;
2018: }
2019: break;
2020: case ANCHOR:
2021: if (dfa->word_char == NULL)
2022: {
2023: *err = init_word_char (dfa);
2024: if (BE (*err != REG_NOERROR, 0))
2025: return NULL;
2026: }
2027: if (token->opr.ctx_type == WORD_DELIM)
2028: {
2029: bin_tree_t *tree_first, *tree_last;
2030: int idx_first, idx_last;
2031: token->opr.ctx_type = WORD_FIRST;
2032: idx_first = re_dfa_add_node (dfa, *token, 0);
2033: tree_first = create_tree (NULL, NULL, 0, idx_first);
2034: token->opr.ctx_type = WORD_LAST;
2035: idx_last = re_dfa_add_node (dfa, *token, 0);
2036: tree_last = create_tree (NULL, NULL, 0, idx_last);
2037: token->type = OP_ALT;
2038: new_idx = re_dfa_add_node (dfa, *token, 0);
2039: tree = create_tree (tree_first, tree_last, 0, new_idx);
2040: if (BE (idx_first == -1 || idx_last == -1 || new_idx == -1
2041: || tree_first == NULL || tree_last == NULL
2042: || tree == NULL, 0))
2043: {
2044: *err = REG_ESPACE;
2045: return NULL;
2046: }
2047: }
2048: else
2049: {
2050: new_idx = re_dfa_add_node (dfa, *token, 0);
2051: tree = create_tree (NULL, NULL, 0, new_idx);
2052: if (BE (new_idx == -1 || tree == NULL, 0))
2053: {
2054: *err = REG_ESPACE;
2055: return NULL;
2056: }
2057: }
2058: /* We must return here, since ANCHORs can't be followed
2059: by repetition operators.
2060: eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2061: it must not be "<ANCHOR(^)><REPEAT(*)>". */
2062: *token = fetch_token (regexp, syntax);
2063: return tree;
2064: case OP_PERIOD:
2065: new_idx = re_dfa_add_node (dfa, *token, 0);
2066: tree = create_tree (NULL, NULL, 0, new_idx);
2067: if (BE (new_idx == -1 || tree == NULL, 0))
2068: {
2069: *err = REG_ESPACE;
2070: return NULL;
2071: }
2072: if (MB_CUR_MAX > 1)
2073: dfa->has_mb_node = 1;
2074: break;
2075: case OP_WORD:
2076: tree = build_word_op (dfa, 0, err);
2077: if (BE (*err != REG_NOERROR && tree == NULL, 0))
2078: return NULL;
2079: break;
2080: case OP_NOTWORD:
2081: tree = build_word_op (dfa, 1, err);
2082: if (BE (*err != REG_NOERROR && tree == NULL, 0))
2083: return NULL;
2084: break;
2085: case OP_ALT:
2086: case END_OF_RE:
2087: return NULL;
2088: case BACK_SLASH:
2089: *err = REG_EESCAPE;
2090: return NULL;
2091: default:
2092: /* Must not happen? */
2093: #ifdef DEBUG
2094: assert (0);
2095: #endif
2096: return NULL;
2097: }
2098: *token = fetch_token (regexp, syntax);
2099:
2100: while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2101: || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2102: {
2103: tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2104: if (BE (*err != REG_NOERROR && tree == NULL, 0))
2105: return NULL;
2106: dfa->has_plural_match = 1;
2107: }
2108:
2109: return tree;
2110: }
2111:
2112: /* This function build the following tree, from regular expression
2113: (<reg_exp>):
2114: SUBEXP
2115: |
2116: <reg_exp>
2117: */
2118:
2119: static bin_tree_t *
2120: parse_sub_exp (regexp, preg, token, syntax, nest, err)
2121: re_string_t *regexp;
2122: regex_t *preg;
2123: re_token_t *token;
2124: reg_syntax_t syntax;
2125: int nest;
2126: reg_errcode_t *err;
2127: {
2128: re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2129: bin_tree_t *tree, *left_par, *right_par;
2130: size_t cur_nsub;
2131: int new_idx;
2132: cur_nsub = preg->re_nsub++;
2133: if (dfa->subexps_alloc < preg->re_nsub)
2134: {
2135: re_subexp_t *new_array;
2136: dfa->subexps_alloc *= 2;
2137: new_array = re_realloc (dfa->subexps, re_subexp_t, dfa->subexps_alloc);
2138: if (BE (new_array == NULL, 0))
2139: {
2140: dfa->subexps_alloc /= 2;
2141: *err = REG_ESPACE;
2142: return NULL;
2143: }
2144: dfa->subexps = new_array;
2145: }
2146: dfa->subexps[cur_nsub].start = dfa->nodes_len;
2147: dfa->subexps[cur_nsub].end = -1;
2148:
2149: new_idx = re_dfa_add_node (dfa, *token, 0);
2150: left_par = create_tree (NULL, NULL, 0, new_idx);
2151: if (BE (new_idx == -1 || left_par == NULL, 0))
2152: {
2153: *err = REG_ESPACE;
2154: return NULL;
2155: }
2156: dfa->nodes[new_idx].opr.idx = cur_nsub;
2157: *token = fetch_token (regexp, syntax);
2158:
2159: /* The subexpression may be a null string. */
2160: if (token->type == OP_CLOSE_SUBEXP)
2161: tree = NULL;
2162: else
2163: {
2164: tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2165: if (BE (*err != REG_NOERROR && tree == NULL, 0))
2166: return NULL;
2167: }
2168: if (BE (token->type != OP_CLOSE_SUBEXP, 0))
2169: {
2170: free_bin_tree (tree);
2171: *err = REG_BADPAT;
2172: return NULL;
2173: }
2174: new_idx = re_dfa_add_node (dfa, *token, 0);
2175: dfa->subexps[cur_nsub].end = dfa->nodes_len;
2176: right_par = create_tree (NULL, NULL, 0, new_idx);
2177: tree = ((tree == NULL) ? right_par
2178: : create_tree (tree, right_par, CONCAT, 0));
2179: tree = create_tree (left_par, tree, CONCAT, 0);
2180: if (BE (new_idx == -1 || right_par == NULL || tree == NULL, 0))
2181: {
2182: *err = REG_ESPACE;
2183: return NULL;
2184: }
2185: dfa->nodes[new_idx].opr.idx = cur_nsub;
2186:
2187: return tree;
2188: }
2189:
2190: /* This function parse repetition operators like "*", "+", "{1,3}" etc. */
2191:
2192: static bin_tree_t *
2193: parse_dup_op (dup_elem, regexp, dfa, token, syntax, err)
2194: bin_tree_t *dup_elem;
2195: re_string_t *regexp;
2196: re_dfa_t *dfa;
2197: re_token_t *token;
2198: reg_syntax_t syntax;
2199: reg_errcode_t *err;
2200: {
2201: re_token_t dup_token;
2202: bin_tree_t *tree = dup_elem, *work_tree;
2203: int new_idx, start_idx = re_string_cur_idx (regexp);
2204: re_token_t start_token = *token;
2205: if (token->type == OP_OPEN_DUP_NUM)
2206: {
2207: int i;
2208: int end = 0;
2209: int start = fetch_number (regexp, token, syntax);
2210: bin_tree_t *elem;
2211: if (start == -1)
2212: {
2213: if (token->type == CHARACTER && token->opr.c == ',')
2214: start = 0; /* We treat "{,m}" as "{0,m}". */
2215: else
2216: {
2217: *err = REG_BADBR; /* <re>{} is invalid. */
2218: return NULL;
2219: }
2220: }
2221: if (BE (start != -2, 1))
2222: {
2223: /* We treat "{n}" as "{n,n}". */
2224: end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2225: : ((token->type == CHARACTER && token->opr.c == ',')
2226: ? fetch_number (regexp, token, syntax) : -2));
2227: }
2228: if (BE (start == -2 || end == -2, 0))
2229: {
2230: /* Invalid sequence. */
2231: if (token->type == OP_CLOSE_DUP_NUM)
2232: goto parse_dup_op_invalid_interval;
2233: else
2234: goto parse_dup_op_ebrace;
2235: }
2236: if (BE (start == 0 && end == 0, 0))
2237: {
2238: /* We treat "<re>{0}" and "<re>{0,0}" as null string. */
2239: *token = fetch_token (regexp, syntax);
2240: free_bin_tree (dup_elem);
2241: return NULL;
2242: }
2243:
2244: /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
2245: elem = tree;
2246: for (i = 0; i < start; ++i)
2247: if (i != 0)
2248: {
2249: work_tree = duplicate_tree (elem, dfa);
2250: tree = create_tree (tree, work_tree, CONCAT, 0);
2251: if (BE (work_tree == NULL || tree == NULL, 0))
2252: goto parse_dup_op_espace;
2253: }
2254:
2255: if (end == -1)
2256: {
2257: /* We treat "<re>{0,}" as "<re>*". */
2258: dup_token.type = OP_DUP_ASTERISK;
2259: if (start > 0)
2260: {
2261: elem = duplicate_tree (elem, dfa);
2262: new_idx = re_dfa_add_node (dfa, dup_token, 0);
2263: work_tree = create_tree (elem, NULL, 0, new_idx);
2264: tree = create_tree (tree, work_tree, CONCAT, 0);
2265: if (BE (elem == NULL || new_idx == -1 || work_tree == NULL
2266: || tree == NULL, 0))
2267: goto parse_dup_op_espace;
2268: }
2269: else
2270: {
2271: new_idx = re_dfa_add_node (dfa, dup_token, 0);
2272: tree = create_tree (elem, NULL, 0, new_idx);
2273: if (BE (new_idx == -1 || tree == NULL, 0))
2274: goto parse_dup_op_espace;
2275: }
2276: }
2277: else if (end - start > 0)
2278: {
2279: /* Then extract "<re>{0,m}" to "<re>?<re>?...<re>?". */
2280: dup_token.type = OP_DUP_QUESTION;
2281: if (start > 0)
2282: {
2283: elem = duplicate_tree (elem, dfa);
2284: new_idx = re_dfa_add_node (dfa, dup_token, 0);
2285: elem = create_tree (elem, NULL, 0, new_idx);
2286: tree = create_tree (tree, elem, CONCAT, 0);
2287: if (BE (elem == NULL || new_idx == -1 || tree == NULL, 0))
2288: goto parse_dup_op_espace;
2289: }
2290: else
2291: {
2292: new_idx = re_dfa_add_node (dfa, dup_token, 0);
2293: tree = elem = create_tree (elem, NULL, 0, new_idx);
2294: if (BE (new_idx == -1 || tree == NULL, 0))
2295: goto parse_dup_op_espace;
2296: }
2297: for (i = 1; i < end - start; ++i)
2298: {
2299: work_tree = duplicate_tree (elem, dfa);
2300: tree = create_tree (tree, work_tree, CONCAT, 0);
2301: if (BE (work_tree == NULL || tree == NULL, 0))
2302: {
2303: *err = REG_ESPACE;
2304: return NULL;
2305: }
2306: }
2307: }
2308: }
2309: else
2310: {
2311: new_idx = re_dfa_add_node (dfa, *token, 0);
2312: tree = create_tree (tree, NULL, 0, new_idx);
2313: if (BE (new_idx == -1 || tree == NULL, 0))
2314: {
2315: *err = REG_ESPACE;
2316: return NULL;
2317: }
2318: }
2319: *token = fetch_token (regexp, syntax);
2320: return tree;
2321:
2322: parse_dup_op_espace:
2323: free_bin_tree (tree);
2324: *err = REG_ESPACE;
2325: return NULL;
2326:
2327: parse_dup_op_ebrace:
2328: if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2329: {
2330: *err = REG_EBRACE;
2331: return NULL;
2332: }
2333: goto parse_dup_op_rollback;
2334: parse_dup_op_invalid_interval:
2335: if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2336: {
2337: *err = REG_BADBR;
2338: return NULL;
2339: }
2340: parse_dup_op_rollback:
2341: re_string_set_index (regexp, start_idx);
2342: *token = start_token;
2343: token->type = CHARACTER;
2344: return dup_elem;
2345: }
2346:
2347: /* Size of the names for collating symbol/equivalence_class/character_class.
2348: I'm not sure, but maybe enough. */
2349: #define BRACKET_NAME_BUF_SIZE 32
2350:
2351: #ifndef _LIBC
2352: /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
2353: Build the range expression which starts from START_ELEM, and ends
2354: at END_ELEM. The result are written to MBCSET and SBCSET.
2355: RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2356: mbcset->range_ends, is a pointer argument sinse we may
2357: update it. */
2358:
2359: static reg_errcode_t
2360: # ifdef RE_ENABLE_I18N
2361: build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
2362: re_charset_t *mbcset;
2363: int *range_alloc;
2364: # else /* not RE_ENABLE_I18N */
2365: build_range_exp (sbcset, start_elem, end_elem)
2366: # endif /* not RE_ENABLE_I18N */
2367: re_bitset_ptr_t sbcset;
2368: bracket_elem_t *start_elem, *end_elem;
2369: {
2370: unsigned int start_ch, end_ch;
2371: /* Equivalence Classes and Character Classes can't be a range start/end. */
2372: if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2373: || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2374: 0))
2375: return REG_ERANGE;
2376:
2377: /* We can handle no multi character collating elements without libc
2378: support. */
2379: if (BE ((start_elem->type == COLL_SYM
2380: && strlen ((char *) start_elem->opr.name) > 1)
2381: || (end_elem->type == COLL_SYM
2382: && strlen ((char *) end_elem->opr.name) > 1), 0))
2383: return REG_ECOLLATE;
2384:
2385: # ifdef RE_ENABLE_I18N
2386: {
2387: wchar_t wc, start_wc, end_wc;
2388: wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2389:
2390: start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2391: : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2392: : 0));
2393: end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2394: : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2395: : 0));
2396: start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2397: ? __btowc (start_ch) : start_elem->opr.wch);
2398: end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2399: ? __btowc (end_ch) : end_elem->opr.wch);
2400: cmp_buf[0] = start_wc;
2401: cmp_buf[4] = end_wc;
2402: if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
2403: return REG_ERANGE;
2404:
2405: /* Check the space of the arrays. */
2406: if (*range_alloc == mbcset->nranges)
2407: {
2408: /* There are not enough space, need realloc. */
2409: wchar_t *new_array_start, *new_array_end;
2410: int new_nranges;
2411:
2412: /* +1 in case of mbcset->nranges is 0. */
2413: new_nranges = 2 * mbcset->nranges + 1;
2414: /* Use realloc since mbcset->range_starts and mbcset->range_ends
2415: are NULL if *range_alloc == 0. */
2416: new_array_start = re_realloc (mbcset->range_starts, wchar_t,
2417: new_nranges);
2418: new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2419: new_nranges);
2420:
2421: if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2422: return REG_ESPACE;
2423:
2424: mbcset->range_starts = new_array_start;
2425: mbcset->range_ends = new_array_end;
2426: *range_alloc = new_nranges;
2427: }
2428:
2429: mbcset->range_starts[mbcset->nranges] = start_wc;
2430: mbcset->range_ends[mbcset->nranges++] = end_wc;
2431:
2432: /* Build the table for single byte characters. */
2433: for (wc = 0; wc <= SBC_MAX; ++wc)
2434: {
2435: cmp_buf[2] = wc;
2436: if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2437: && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2438: bitset_set (sbcset, wc);
2439: }
2440: }
2441: # else /* not RE_ENABLE_I18N */
2442: {
2443: unsigned int ch;
2444: start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
2445: : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2446: : 0));
2447: end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
2448: : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2449: : 0));
2450: if (start_ch > end_ch)
2451: return REG_ERANGE;
2452: /* Build the table for single byte characters. */
2453: for (ch = 0; ch <= SBC_MAX; ++ch)
2454: if (start_ch <= ch && ch <= end_ch)
2455: bitset_set (sbcset, ch);
2456: }
2457: # endif /* not RE_ENABLE_I18N */
2458: return REG_NOERROR;
2459: }
2460: #endif /* not _LIBC */
2461:
2462: #ifndef _LIBC
2463: /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
2464: Build the collating element which is represented by NAME.
2465: The result are written to MBCSET and SBCSET.
2466: COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2467: pointer argument since we may update it. */
2468:
2469: static reg_errcode_t
2470: # ifdef RE_ENABLE_I18N
2471: build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
2472: re_charset_t *mbcset;
2473: int *coll_sym_alloc;
2474: # else /* not RE_ENABLE_I18N */
2475: build_collating_symbol (sbcset, name)
2476: # endif /* not RE_ENABLE_I18N */
2477: re_bitset_ptr_t sbcset;
2478: const unsigned char *name;
2479: {
2480: size_t name_len = strlen ((const char *) name);
2481: if (BE (name_len != 1, 0))
2482: return REG_ECOLLATE;
2483: else
2484: {
2485: bitset_set (sbcset, name[0]);
2486: return REG_NOERROR;
2487: }
2488: }
2489: #endif /* not _LIBC */
2490:
2491: /* This function parse bracket expression like "[abc]", "[a-c]",
2492: "[[.a-a.]]" etc. */
2493:
2494: static bin_tree_t *
2495: parse_bracket_exp (regexp, dfa, token, syntax, err)
2496: re_string_t *regexp;
2497: re_dfa_t *dfa;
2498: re_token_t *token;
2499: reg_syntax_t syntax;
2500: reg_errcode_t *err;
2501: {
2502: #ifdef _LIBC
2503: const unsigned char *collseqmb;
2504: const char *collseqwc;
2505: uint32_t nrules;
2506: int32_t table_size;
2507: const int32_t *symb_table;
2508: const unsigned char *extra;
2509:
2510: /* Local function for parse_bracket_exp used in _LIBC environement.
2511: Seek the collating symbol entry correspondings to NAME.
2512: Return the index of the symbol in the SYMB_TABLE. */
2513:
2514: static inline int32_t
2515: seek_collating_symbol_entry (name, name_len)
2516: const unsigned char *name;
2517: size_t name_len;
2518: {
2519: int32_t hash = elem_hash ((const char *) name, name_len);
2520: int32_t elem = hash % table_size;
2521: int32_t second = hash % (table_size - 2);
2522: while (symb_table[2 * elem] != 0)
2523: {
2524: /* First compare the hashing value. */
2525: if (symb_table[2 * elem] == hash
2526: /* Compare the length of the name. */
2527: && name_len == extra[symb_table[2 * elem + 1]]
2528: /* Compare the name. */
2529: && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
2530: name_len) == 0)
2531: {
2532: /* Yep, this is the entry. */
2533: break;
2534: }
2535:
2536: /* Next entry. */
2537: elem += second;
2538: }
2539: return elem;
2540: }
2541:
2542: /* Local function for parse_bracket_exp used in _LIBC environement.
2543: Look up the collation sequence value of BR_ELEM.
2544: Return the value if succeeded, UINT_MAX otherwise. */
2545:
2546: static inline unsigned int
2547: lookup_collation_sequence_value (br_elem)
2548: bracket_elem_t *br_elem;
2549: {
2550: if (br_elem->type == SB_CHAR)
2551: {
2552: /*
2553: if (MB_CUR_MAX == 1)
2554: */
2555: if (nrules == 0)
2556: return collseqmb[br_elem->opr.ch];
2557: else
2558: {
2559: wint_t wc = __btowc (br_elem->opr.ch);
2560: return collseq_table_lookup (collseqwc, wc);
2561: }
2562: }
2563: else if (br_elem->type == MB_CHAR)
2564: {
2565: return collseq_table_lookup (collseqwc, br_elem->opr.wch);
2566: }
2567: else if (br_elem->type == COLL_SYM)
2568: {
2569: size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2570: if (nrules != 0)
2571: {
2572: int32_t elem, idx;
2573: elem = seek_collating_symbol_entry (br_elem->opr.name,
2574: sym_name_len);
2575: if (symb_table[2 * elem] != 0)
2576: {
2577: /* We found the entry. */
2578: idx = symb_table[2 * elem + 1];
2579: /* Skip the name of collating element name. */
2580: idx += 1 + extra[idx];
2581: /* Skip the byte sequence of the collating element. */
2582: idx += 1 + extra[idx];
2583: /* Adjust for the alignment. */
2584: idx = (idx + 3) & ~3;
2585: /* Skip the multibyte collation sequence value. */
2586: idx += sizeof (unsigned int);
2587: /* Skip the wide char sequence of the collating element. */
2588: idx += sizeof (unsigned int) *
2589: (1 + *(unsigned int *) (extra + idx));
2590: /* Return the collation sequence value. */
2591: return *(unsigned int *) (extra + idx);
2592: }
2593: else if (symb_table[2 * elem] == 0 && sym_name_len == 1)
2594: {
2595: /* No valid character. Match it as a single byte
2596: character. */
2597: return collseqmb[br_elem->opr.name[0]];
2598: }
2599: }
2600: else if (sym_name_len == 1)
2601: return collseqmb[br_elem->opr.name[0]];
2602: }
2603: return UINT_MAX;
2604: }
2605:
2606: /* Local function for parse_bracket_exp used in _LIBC environement.
2607: Build the range expression which starts from START_ELEM, and ends
2608: at END_ELEM. The result are written to MBCSET and SBCSET.
2609: RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2610: mbcset->range_ends, is a pointer argument sinse we may
2611: update it. */
2612:
2613: static inline reg_errcode_t
2614: # ifdef RE_ENABLE_I18N
2615: build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
2616: re_charset_t *mbcset;
2617: int *range_alloc;
2618: # else /* not RE_ENABLE_I18N */
2619: build_range_exp (sbcset, start_elem, end_elem)
2620: # endif /* not RE_ENABLE_I18N */
2621: re_bitset_ptr_t sbcset;
2622: bracket_elem_t *start_elem, *end_elem;
2623: {
2624: unsigned int ch;
2625: uint32_t start_collseq;
2626: uint32_t end_collseq;
2627:
2628: # ifdef RE_ENABLE_I18N
2629: /* Check the space of the arrays. */
2630: if (*range_alloc == mbcset->nranges)
2631: {
2632: /* There are not enough space, need realloc. */
2633: uint32_t *new_array_start;
2634: uint32_t *new_array_end;
2635: int new_nranges;
2636:
2637: /* +1 in case of mbcset->nranges is 0. */
2638: new_nranges = 2 * mbcset->nranges + 1;
2639: /* Use realloc since mbcset->range_starts and mbcset->range_ends
2640: are NULL if *range_alloc == 0. */
2641: new_array_start = re_realloc (mbcset->range_starts, uint32_t,
2642: new_nranges);
2643: new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2644: new_nranges);
2645:
2646: if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2647: return REG_ESPACE;
2648:
2649: mbcset->range_starts = new_array_start;
2650: mbcset->range_ends = new_array_end;
2651: *range_alloc = new_nranges;
2652: }
2653: # endif /* RE_ENABLE_I18N */
2654:
2655: /* Equivalence Classes and Character Classes can't be a range
2656: start/end. */
2657: if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2658: || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2659: 0))
2660: return REG_ERANGE;
2661:
2662: start_collseq = lookup_collation_sequence_value (start_elem);
2663: end_collseq = lookup_collation_sequence_value (end_elem);
2664: /* Check start/end collation sequence values. */
2665: if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
2666: return REG_ECOLLATE;
2667: if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
2668: return REG_ERANGE;
2669:
2670: # ifdef RE_ENABLE_I18N
2671: /* Got valid collation sequence values, add them as a new entry. */
2672: mbcset->range_starts[mbcset->nranges] = start_collseq;
2673: mbcset->range_ends[mbcset->nranges++] = end_collseq;
2674: # endif /* RE_ENABLE_I18N */
2675:
2676: /* Build the table for single byte characters. */
2677: for (ch = 0; ch <= SBC_MAX; ch++)
2678: {
2679: uint32_t ch_collseq;
2680: /*
2681: if (MB_CUR_MAX == 1)
2682: */
2683: if (nrules == 0)
2684: ch_collseq = collseqmb[ch];
2685: else
2686: ch_collseq = collseq_table_lookup (collseqwc, __btowc (ch));
2687: if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2688: bitset_set (sbcset, ch);
2689: }
2690: return REG_NOERROR;
2691: }
2692:
2693: /* Local function for parse_bracket_exp used in _LIBC environement.
2694: Build the collating element which is represented by NAME.
2695: The result are written to MBCSET and SBCSET.
2696: COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2697: pointer argument sinse we may update it. */
2698:
2699: static inline reg_errcode_t
2700: # ifdef RE_ENABLE_I18N
2701: build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
2702: re_charset_t *mbcset;
2703: int *coll_sym_alloc;
2704: # else /* not RE_ENABLE_I18N */
2705: build_collating_symbol (sbcset, name)
2706: # endif /* not RE_ENABLE_I18N */
2707: re_bitset_ptr_t sbcset;
2708: const unsigned char *name;
2709: {
2710: int32_t elem, idx;
2711: size_t name_len = strlen ((const char *) name);
2712: if (nrules != 0)
2713: {
2714: elem = seek_collating_symbol_entry (name, name_len);
2715: if (symb_table[2 * elem] != 0)
2716: {
2717: /* We found the entry. */
2718: idx = symb_table[2 * elem + 1];
2719: /* Skip the name of collating element name. */
2720: idx += 1 + extra[idx];
2721: }
2722: else if (symb_table[2 * elem] == 0 && name_len == 1)
2723: {
2724: /* No valid character, treat it as a normal
2725: character. */
2726: bitset_set (sbcset, name[0]);
2727: return REG_NOERROR;
2728: }
2729: else
2730: return REG_ECOLLATE;
2731:
2732: # ifdef RE_ENABLE_I18N
2733: /* Got valid collation sequence, add it as a new entry. */
2734: /* Check the space of the arrays. */
2735: if (*coll_sym_alloc == mbcset->ncoll_syms)
2736: {
2737: /* Not enough, realloc it. */
2738: /* +1 in case of mbcset->ncoll_syms is 0. */
2739: *coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
2740: /* Use realloc since mbcset->coll_syms is NULL
2741: if *alloc == 0. */
2742: mbcset->coll_syms = re_realloc (mbcset->coll_syms, int32_t,
2743: *coll_sym_alloc);
2744: if (BE (mbcset->coll_syms == NULL, 0))
2745: return REG_ESPACE;
2746: }
2747: mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
2748: # endif /* RE_ENABLE_I18N */
2749: return REG_NOERROR;
2750: }
2751: else
2752: {
2753: if (BE (name_len != 1, 0))
2754: return REG_ECOLLATE;
2755: else
2756: {
2757: bitset_set (sbcset, name[0]);
2758: return REG_NOERROR;
2759: }
2760: }
2761: }
2762: #endif
2763:
2764: re_token_t br_token;
2765: re_bitset_ptr_t sbcset;
2766: #ifdef RE_ENABLE_I18N
2767: re_charset_t *mbcset;
2768: int coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
2769: int equiv_class_alloc = 0, char_class_alloc = 0;
2770: #else /* not RE_ENABLE_I18N */
2771: int non_match = 0;
2772: #endif /* not RE_ENABLE_I18N */
2773: bin_tree_t *work_tree;
2774: int token_len, new_idx;
2775: #ifdef _LIBC
2776: collseqmb = (const unsigned char *)
2777: _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
2778: nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2779: if (nrules)
2780: {
2781: /*
2782: if (MB_CUR_MAX > 1)
2783: */
2784: collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
2785: table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
2786: symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
2787: _NL_COLLATE_SYMB_TABLEMB);
2788: extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
2789: _NL_COLLATE_SYMB_EXTRAMB);
2790: }
2791: #endif
2792: sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
2793: #ifdef RE_ENABLE_I18N
2794: mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
2795: #endif /* RE_ENABLE_I18N */
2796: #ifdef RE_ENABLE_I18N
2797: if (BE (sbcset == NULL || mbcset == NULL, 0))
2798: #else
2799: if (BE (sbcset == NULL, 0))
2800: #endif /* RE_ENABLE_I18N */
2801: {
2802: *err = REG_ESPACE;
2803: return NULL;
2804: }
2805:
2806: token_len = peek_token_bracket (token, regexp, syntax);
2807: if (BE (token->type == END_OF_RE, 0))
2808: {
2809: *err = REG_BADPAT;
2810: goto parse_bracket_exp_free_return;
2811: }
2812: if (token->type == OP_NON_MATCH_LIST)
2813: {
2814: #ifdef RE_ENABLE_I18N
2815: int i;
2816: mbcset->non_match = 1;
2817: #else /* not RE_ENABLE_I18N */
2818: non_match = 1;
2819: #endif /* not RE_ENABLE_I18N */
2820: if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
2821: bitset_set (sbcset, '\0');
2822: re_string_skip_bytes (regexp, token_len); /* Skip a token. */
2823: token_len = peek_token_bracket (token, regexp, syntax);
2824: if (BE (token->type == END_OF_RE, 0))
2825: {
2826: *err = REG_BADPAT;
2827: goto parse_bracket_exp_free_return;
2828: }
2829: #ifdef RE_ENABLE_I18N
2830: if (MB_CUR_MAX > 1)
2831: for (i = 0; i < SBC_MAX; ++i)
2832: if (__btowc (i) == WEOF)
2833: bitset_set (sbcset, i);
2834: #endif /* RE_ENABLE_I18N */
2835: }
2836:
2837: /* We treat the first ']' as a normal character. */
2838: if (token->type == OP_CLOSE_BRACKET)
2839: token->type = CHARACTER;
2840:
2841: while (1)
2842: {
2843: bracket_elem_t start_elem, end_elem;
2844: unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
2845: unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
2846: reg_errcode_t ret;
2847: int token_len2 = 0, is_range_exp = 0;
2848: re_token_t token2;
2849:
2850: start_elem.opr.name = start_name_buf;
2851: ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
2852: syntax);
2853: if (BE (ret != REG_NOERROR, 0))
2854: {
2855: *err = ret;
2856: goto parse_bracket_exp_free_return;
2857: }
2858:
2859: token_len = peek_token_bracket (token, regexp, syntax);
2860: if (BE (token->type == END_OF_RE, 0))
2861: {
2862: *err = REG_BADPAT;
2863: goto parse_bracket_exp_free_return;
2864: }
2865: if (token->type == OP_CHARSET_RANGE)
2866: {
2867: re_string_skip_bytes (regexp, token_len); /* Skip '-'. */
2868: token_len2 = peek_token_bracket (&token2, regexp, syntax);
2869: if (BE (token->type == END_OF_RE, 0))
2870: {
2871: *err = REG_BADPAT;
2872: goto parse_bracket_exp_free_return;
2873: }
2874: if (token2.type == OP_CLOSE_BRACKET)
2875: {
2876: /* We treat the last '-' as a normal character. */
2877: re_string_skip_bytes (regexp, -token_len);
2878: token->type = CHARACTER;
2879: }
2880: else
2881: is_range_exp = 1;
2882: }
2883:
2884: if (is_range_exp == 1)
2885: {
2886: end_elem.opr.name = end_name_buf;
2887: ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
2888: dfa, syntax);
2889: if (BE (ret != REG_NOERROR, 0))
2890: {
2891: *err = ret;
2892: goto parse_bracket_exp_free_return;
2893: }
2894:
2895: token_len = peek_token_bracket (token, regexp, syntax);
2896: if (BE (token->type == END_OF_RE, 0))
2897: {
2898: *err = REG_BADPAT;
2899: goto parse_bracket_exp_free_return;
2900: }
2901: *err = build_range_exp (sbcset,
2902: #ifdef RE_ENABLE_I18N
2903: mbcset, &range_alloc,
2904: #endif /* RE_ENABLE_I18N */
2905: &start_elem, &end_elem);
2906: if (BE (*err != REG_NOERROR, 0))
2907: goto parse_bracket_exp_free_return;
2908: }
2909: else
2910: {
2911: switch (start_elem.type)
2912: {
2913: case SB_CHAR:
2914: bitset_set (sbcset, start_elem.opr.ch);
2915: break;
2916: #ifdef RE_ENABLE_I18N
2917: case MB_CHAR:
2918: /* Check whether the array has enough space. */
2919: if (mbchar_alloc == mbcset->nmbchars)
2920: {
2921: /* Not enough, realloc it. */
2922: /* +1 in case of mbcset->nmbchars is 0. */
2923: mbchar_alloc = 2 * mbcset->nmbchars + 1;
2924: /* Use realloc since array is NULL if *alloc == 0. */
2925: mbcset->mbchars = re_realloc (mbcset->mbchars, wchar_t,
2926: mbchar_alloc);
2927: if (BE (mbcset->mbchars == NULL, 0))
2928: goto parse_bracket_exp_espace;
2929: }
2930: mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
2931: break;
2932: #endif /* RE_ENABLE_I18N */
2933: case EQUIV_CLASS:
2934: *err = build_equiv_class (sbcset,
2935: #ifdef RE_ENABLE_I18N
2936: mbcset, &equiv_class_alloc,
2937: #endif /* RE_ENABLE_I18N */
2938: start_elem.opr.name);
2939: if (BE (*err != REG_NOERROR, 0))
2940: goto parse_bracket_exp_free_return;
2941: break;
2942: case COLL_SYM:
2943: *err = build_collating_symbol (sbcset,
2944: #ifdef RE_ENABLE_I18N
2945: mbcset, &coll_sym_alloc,
2946: #endif /* RE_ENABLE_I18N */
2947: start_elem.opr.name);
2948: if (BE (*err != REG_NOERROR, 0))
2949: goto parse_bracket_exp_free_return;
2950: break;
2951: case CHAR_CLASS:
2952: *err = build_charclass (sbcset,
2953: #ifdef RE_ENABLE_I18N
2954: mbcset, &char_class_alloc,
2955: #endif /* RE_ENABLE_I18N */
2956: start_elem.opr.name, syntax);
2957: if (BE (*err != REG_NOERROR, 0))
2958: goto parse_bracket_exp_free_return;
2959: break;
2960: default:
2961: assert (0);
2962: break;
2963: }
2964: }
2965: if (token->type == OP_CLOSE_BRACKET)
2966: break;
2967: }
2968:
2969: re_string_skip_bytes (regexp, token_len); /* Skip a token. */
2970:
2971: /* If it is non-matching list. */
2972: #ifdef RE_ENABLE_I18N
2973: if (mbcset->non_match)
2974: #else /* not RE_ENABLE_I18N */
2975: if (non_match)
2976: #endif /* not RE_ENABLE_I18N */
2977: bitset_not (sbcset);
2978:
2979: /* Build a tree for simple bracket. */
2980: br_token.type = SIMPLE_BRACKET;
2981: br_token.opr.sbcset = sbcset;
2982: new_idx = re_dfa_add_node (dfa, br_token, 0);
2983: work_tree = create_tree (NULL, NULL, 0, new_idx);
2984: if (BE (new_idx == -1 || work_tree == NULL, 0))
2985: goto parse_bracket_exp_espace;
2986:
2987: #ifdef RE_ENABLE_I18N
2988: if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
2989: || mbcset->nranges || (MB_CUR_MAX > 1 && (mbcset->nchar_classes
2990: || mbcset->non_match)))
2991: {
2992: re_token_t alt_token;
2993: bin_tree_t *mbc_tree;
2994: /* Build a tree for complex bracket. */
2995: br_token.type = COMPLEX_BRACKET;
2996: br_token.opr.mbcset = mbcset;
2997: dfa->has_mb_node = 1;
2998: new_idx = re_dfa_add_node (dfa, br_token, 0);
2999: mbc_tree = create_tree (NULL, NULL, 0, new_idx);
3000: if (BE (new_idx == -1 || mbc_tree == NULL, 0))
3001: goto parse_bracket_exp_espace;
3002: /* Then join them by ALT node. */
3003: dfa->has_plural_match = 1;
3004: alt_token.type = OP_ALT;
3005: new_idx = re_dfa_add_node (dfa, alt_token, 0);
3006: work_tree = create_tree (work_tree, mbc_tree, 0, new_idx);
3007: if (BE (new_idx != -1 && mbc_tree != NULL, 1))
3008: return work_tree;
3009: }
3010: else
3011: {
3012: free_charset (mbcset);
3013: return work_tree;
3014: }
3015: #else /* not RE_ENABLE_I18N */
3016: return work_tree;
3017: #endif /* not RE_ENABLE_I18N */
3018:
3019: parse_bracket_exp_espace:
3020: *err = REG_ESPACE;
3021: parse_bracket_exp_free_return:
3022: re_free (sbcset);
3023: #ifdef RE_ENABLE_I18N
3024: free_charset (mbcset);
3025: #endif /* RE_ENABLE_I18N */
3026: return NULL;
3027: }
3028:
3029: /* Parse an element in the bracket expression. */
3030:
3031: static reg_errcode_t
3032: parse_bracket_element (elem, regexp, token, token_len, dfa, syntax)
3033: bracket_elem_t *elem;
3034: re_string_t *regexp;
3035: re_token_t *token;
3036: int token_len;
3037: re_dfa_t *dfa;
3038: reg_syntax_t syntax;
3039: {
3040: #ifdef RE_ENABLE_I18N
3041: int cur_char_size;
3042: cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3043: if (cur_char_size > 1)
3044: {
3045: elem->type = MB_CHAR;
3046: elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3047: re_string_skip_bytes (regexp, cur_char_size);
3048: return REG_NOERROR;
3049: }
3050: #endif /* RE_ENABLE_I18N */
3051: re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3052: if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3053: || token->type == OP_OPEN_EQUIV_CLASS)
3054: return parse_bracket_symbol (elem, regexp, token);
3055: elem->type = SB_CHAR;
3056: elem->opr.ch = token->opr.c;
3057: return REG_NOERROR;
3058: }
3059:
3060: /* Parse a bracket symbol in the bracket expression. Bracket symbols are
3061: such as [:<character_class>:], [.<collating_element>.], and
3062: [=<equivalent_class>=]. */
3063:
3064: static reg_errcode_t
3065: parse_bracket_symbol (elem, regexp, token)
3066: bracket_elem_t *elem;
3067: re_string_t *regexp;
3068: re_token_t *token;
3069: {
3070: unsigned char ch, delim = token->opr.c;
3071: int i = 0;
3072: for (;; ++i)
3073: {
3074: if (re_string_eoi(regexp) || i >= BRACKET_NAME_BUF_SIZE)
3075: return REG_EBRACK;
3076: if (token->type == OP_OPEN_CHAR_CLASS)
3077: ch = re_string_fetch_byte_case (regexp);
3078: else
3079: ch = re_string_fetch_byte (regexp);
3080: if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3081: break;
3082: elem->opr.name[i] = ch;
3083: }
3084: re_string_skip_bytes (regexp, 1);
3085: elem->opr.name[i] = '\0';
3086: switch (token->type)
3087: {
3088: case OP_OPEN_COLL_ELEM:
3089: elem->type = COLL_SYM;
3090: break;
3091: case OP_OPEN_EQUIV_CLASS:
3092: elem->type = EQUIV_CLASS;
3093: break;
3094: case OP_OPEN_CHAR_CLASS:
3095: elem->type = CHAR_CLASS;
3096: break;
3097: default:
3098: break;
3099: }
3100: return REG_NOERROR;
3101: }
3102:
3103: /* Helper function for parse_bracket_exp.
3104: Build the equivalence class which is represented by NAME.
3105: The result are written to MBCSET and SBCSET.
3106: EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
3107: is a pointer argument sinse we may update it. */
3108:
3109: static reg_errcode_t
3110: #ifdef RE_ENABLE_I18N
3111: build_equiv_class (sbcset, mbcset, equiv_class_alloc, name)
3112: re_charset_t *mbcset;
3113: int *equiv_class_alloc;
3114: #else /* not RE_ENABLE_I18N */
3115: build_equiv_class (sbcset, name)
3116: #endif /* not RE_ENABLE_I18N */
3117: re_bitset_ptr_t sbcset;
3118: const unsigned char *name;
3119: {
3120: #if defined _LIBC && defined RE_ENABLE_I18N
3121: uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3122: if (nrules != 0)
3123: {
3124: const int32_t *table, *indirect;
3125: const unsigned char *weights, *extra, *cp;
3126: unsigned char char_buf[2];
3127: int32_t idx1, idx2;
3128: unsigned int ch;
3129: size_t len;
3130: /* This #include defines a local function! */
3131: # include <locale/weight.h>
3132: /* Calculate the index for equivalence class. */
3133: cp = name;
3134: table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3135: weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3136: _NL_COLLATE_WEIGHTMB);
3137: extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3138: _NL_COLLATE_EXTRAMB);
3139: indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3140: _NL_COLLATE_INDIRECTMB);
3141: idx1 = findidx (&cp);
3142: if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0))
3143: /* This isn't a valid character. */
3144: return REG_ECOLLATE;
3145:
3146: /* Build single byte matcing table for this equivalence class. */
3147: char_buf[1] = (unsigned char) '\0';
3148: len = weights[idx1];
3149: for (ch = 0; ch < SBC_MAX; ++ch)
3150: {
3151: char_buf[0] = ch;
3152: cp = char_buf;
3153: idx2 = findidx (&cp);
3154: /*
3155: idx2 = table[ch];
3156: */
3157: if (idx2 == 0)
3158: /* This isn't a valid character. */
3159: continue;
3160: if (len == weights[idx2])
3161: {
3162: int cnt = 0;
3163: while (cnt <= len &&
3164: weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt])
3165: ++cnt;
3166:
3167: if (cnt > len)
3168: bitset_set (sbcset, ch);
3169: }
3170: }
3171: /* Check whether the array has enough space. */
3172: if (*equiv_class_alloc == mbcset->nequiv_classes)
3173: {
3174: /* Not enough, realloc it. */
3175: /* +1 in case of mbcset->nequiv_classes is 0. */
3176: *equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
3177: /* Use realloc since the array is NULL if *alloc == 0. */
3178: mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t,
3179: *equiv_class_alloc);
3180: if (BE (mbcset->equiv_classes == NULL, 0))
3181: return REG_ESPACE;
3182: }
3183: mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
3184: }
3185: else
3186: #endif /* _LIBC && RE_ENABLE_I18N */
3187: {
3188: if (BE (strlen ((const char *) name) != 1, 0))
3189: return REG_ECOLLATE;
3190: bitset_set (sbcset, *name);
3191: }
3192: return REG_NOERROR;
3193: }
3194:
3195: /* Helper function for parse_bracket_exp.
3196: Build the character class which is represented by NAME.
3197: The result are written to MBCSET and SBCSET.
3198: CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
3199: is a pointer argument sinse we may update it. */
3200:
3201: static reg_errcode_t
3202: #ifdef RE_ENABLE_I18N
3203: build_charclass (sbcset, mbcset, char_class_alloc, class_name, syntax)
3204: re_charset_t *mbcset;
3205: int *char_class_alloc;
3206: #else /* not RE_ENABLE_I18N */
3207: build_charclass (sbcset, class_name, syntax)
3208: #endif /* not RE_ENABLE_I18N */
3209: re_bitset_ptr_t sbcset;
3210: const unsigned char *class_name;
3211: reg_syntax_t syntax;
3212: {
3213: int i;
3214: const char *name = (const char *) class_name;
3215:
3216: /* In case of REG_ICASE "upper" and "lower" match the both of
3217: upper and lower cases. */
3218: if ((syntax & RE_ICASE)
3219: && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
3220: name = "alpha";
3221:
3222: #ifdef RE_ENABLE_I18N
3223: /* Check the space of the arrays. */
3224: if (*char_class_alloc == mbcset->nchar_classes)
3225: {
3226: /* Not enough, realloc it. */
3227: /* +1 in case of mbcset->nchar_classes is 0. */
3228: *char_class_alloc = 2 * mbcset->nchar_classes + 1;
3229: /* Use realloc since array is NULL if *alloc == 0. */
3230: mbcset->char_classes = re_realloc (mbcset->char_classes, wctype_t,
3231: *char_class_alloc);
3232: if (BE (mbcset->char_classes == NULL, 0))
3233: return REG_ESPACE;
3234: }
3235: mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
3236: #endif /* RE_ENABLE_I18N */
3237:
3238: #define BUILD_CHARCLASS_LOOP(ctype_func)\
3239: for (i = 0; i < SBC_MAX; ++i) \
3240: { \
3241: if (ctype_func (i)) \
3242: bitset_set (sbcset, i); \
3243: }
3244:
3245: if (strcmp (name, "alnum") == 0)
3246: BUILD_CHARCLASS_LOOP (isalnum)
3247: else if (strcmp (name, "cntrl") == 0)
3248: BUILD_CHARCLASS_LOOP (iscntrl)
3249: else if (strcmp (name, "lower") == 0)
3250: BUILD_CHARCLASS_LOOP (islower)
3251: else if (strcmp (name, "space") == 0)
3252: BUILD_CHARCLASS_LOOP (isspace)
3253: else if (strcmp (name, "alpha") == 0)
3254: BUILD_CHARCLASS_LOOP (isalpha)
3255: else if (strcmp (name, "digit") == 0)
3256: BUILD_CHARCLASS_LOOP (isdigit)
3257: else if (strcmp (name, "print") == 0)
3258: BUILD_CHARCLASS_LOOP (isprint)
3259: else if (strcmp (name, "upper") == 0)
3260: BUILD_CHARCLASS_LOOP (isupper)
3261: else if (strcmp (name, "blank") == 0)
3262: BUILD_CHARCLASS_LOOP (isblank)
3263: else if (strcmp (name, "graph") == 0)
3264: BUILD_CHARCLASS_LOOP (isgraph)
3265: else if (strcmp (name, "punct") == 0)
3266: BUILD_CHARCLASS_LOOP (ispunct)
3267: else if (strcmp (name, "xdigit") == 0)
3268: BUILD_CHARCLASS_LOOP (isxdigit)
3269: else
3270: return REG_ECTYPE;
3271:
3272: return REG_NOERROR;
3273: }
3274:
3275: static bin_tree_t *
3276: build_word_op (dfa, not, err)
3277: re_dfa_t *dfa;
3278: int not;
3279: reg_errcode_t *err;
3280: {
3281: re_bitset_ptr_t sbcset;
3282: #ifdef RE_ENABLE_I18N
3283: re_charset_t *mbcset;
3284: int alloc = 0;
3285: #else /* not RE_ENABLE_I18N */
3286: int non_match = 0;
3287: #endif /* not RE_ENABLE_I18N */
3288: reg_errcode_t ret;
3289: re_token_t br_token;
3290: bin_tree_t *tree;
3291: int new_idx;
3292:
3293: sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
3294: #ifdef RE_ENABLE_I18N
3295: mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3296: #endif /* RE_ENABLE_I18N */
3297:
3298: #ifdef RE_ENABLE_I18N
3299: if (BE (sbcset == NULL || mbcset == NULL, 0))
3300: #else /* not RE_ENABLE_I18N */
3301: if (BE (sbcset == NULL, 0))
3302: #endif /* not RE_ENABLE_I18N */
3303: {
3304: *err = REG_ESPACE;
3305: return NULL;
3306: }
3307:
3308: if (not)
3309: {
3310: #ifdef RE_ENABLE_I18N
3311: int i;
3312: /*
3313: if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
3314: bitset_set(cset->sbcset, '\0');
3315: */
3316: mbcset->non_match = 1;
3317: if (MB_CUR_MAX > 1)
3318: for (i = 0; i < SBC_MAX; ++i)
3319: if (__btowc (i) == WEOF)
3320: bitset_set (sbcset, i);
3321: #else /* not RE_ENABLE_I18N */
3322: non_match = 1;
3323: #endif /* not RE_ENABLE_I18N */
3324: }
3325:
3326: /* We don't care the syntax in this case. */
3327: ret = build_charclass (sbcset,
3328: #ifdef RE_ENABLE_I18N
3329: mbcset, &alloc,
3330: #endif /* RE_ENABLE_I18N */
3331: (const unsigned char *) "alpha", 0);
3332:
3333: if (BE (ret != REG_NOERROR, 0))
3334: {
3335: re_free (sbcset);
3336: #ifdef RE_ENABLE_I18N
3337: free_charset (mbcset);
3338: #endif /* RE_ENABLE_I18N */
3339: *err = ret;
3340: return NULL;
3341: }
3342: /* \w match '_' also. */
3343: bitset_set (sbcset, '_');
3344:
3345: /* If it is non-matching list. */
3346: #ifdef RE_ENABLE_I18N
3347: if (mbcset->non_match)
3348: #else /* not RE_ENABLE_I18N */
3349: if (non_match)
3350: #endif /* not RE_ENABLE_I18N */
3351: bitset_not (sbcset);
3352:
3353: /* Build a tree for simple bracket. */
3354: br_token.type = SIMPLE_BRACKET;
3355: br_token.opr.sbcset = sbcset;
3356: new_idx = re_dfa_add_node (dfa, br_token, 0);
3357: tree = create_tree (NULL, NULL, 0, new_idx);
3358: if (BE (new_idx == -1 || tree == NULL, 0))
3359: goto build_word_op_espace;
3360:
3361: #ifdef RE_ENABLE_I18N
3362: if (MB_CUR_MAX > 1)
3363: {
3364: re_token_t alt_token;
3365: bin_tree_t *mbc_tree;
3366: /* Build a tree for complex bracket. */
3367: br_token.type = COMPLEX_BRACKET;
3368: br_token.opr.mbcset = mbcset;
3369: dfa->has_mb_node = 1;
3370: new_idx = re_dfa_add_node (dfa, br_token, 0);
3371: mbc_tree = create_tree (NULL, NULL, 0, new_idx);
3372: if (BE (new_idx == -1 || mbc_tree == NULL, 0))
3373: goto build_word_op_espace;
3374: /* Then join them by ALT node. */
3375: alt_token.type = OP_ALT;
3376: new_idx = re_dfa_add_node (dfa, alt_token, 0);
3377: tree = create_tree (tree, mbc_tree, 0, new_idx);
3378: if (BE (new_idx != -1 && mbc_tree != NULL, 1))
3379: return tree;
3380: }
3381: else
3382: {
3383: free_charset (mbcset);
3384: return tree;
3385: }
3386: #else /* not RE_ENABLE_I18N */
3387: return tree;
3388: #endif /* not RE_ENABLE_I18N */
3389:
3390: build_word_op_espace:
3391: re_free (sbcset);
3392: #ifdef RE_ENABLE_I18N
3393: free_charset (mbcset);
3394: #endif /* RE_ENABLE_I18N */
3395: *err = REG_ESPACE;
3396: return NULL;
3397: }
3398:
3399: /* This is intended for the expressions like "a{1,3}".
3400: Fetch a number from `input', and return the number.
3401: Return -1, if the number field is empty like "{,1}".
3402: Return -2, If an error is occured. */
3403:
3404: static int
3405: fetch_number (input, token, syntax)
3406: re_string_t *input;
3407: re_token_t *token;
3408: reg_syntax_t syntax;
3409: {
3410: int num = -1;
3411: unsigned char c;
3412: while (1)
3413: {
3414: *token = fetch_token (input, syntax);
3415: c = token->opr.c;
3416: if (BE (token->type == END_OF_RE, 0))
3417: return -2;
3418: if (token->type == OP_CLOSE_DUP_NUM || c == ',')
3419: break;
3420: num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)
3421: ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0'));
3422: num = (num > RE_DUP_MAX) ? -2 : num;
3423: }
3424: return num;
3425: }
3426:
3427: #ifdef RE_ENABLE_I18N
3428: static void
3429: free_charset (re_charset_t *cset)
3430: {
3431: re_free (cset->mbchars);
3432: # ifdef _LIBC
3433: re_free (cset->coll_syms);
3434: re_free (cset->equiv_classes);
3435: re_free (cset->range_starts);
3436: re_free (cset->range_ends);
3437: # endif
3438: re_free (cset->char_classes);
3439: re_free (cset);
3440: }
3441: #endif /* RE_ENABLE_I18N */
3442:
3443: /* Functions for binary tree operation. */
3444:
3445: /* Create a node of tree.
3446: Note: This function automatically free left and right if malloc fails. */
3447:
3448: static bin_tree_t *
3449: create_tree (left, right, type, index)
3450: bin_tree_t *left;
3451: bin_tree_t *right;
3452: re_token_type_t type;
3453: int index;
3454: {
3455: bin_tree_t *tree;
3456: tree = re_malloc (bin_tree_t, 1);
3457: if (BE (tree == NULL, 0))
3458: {
3459: free_bin_tree (left);
3460: free_bin_tree (right);
3461: return NULL;
3462: }
3463: tree->parent = NULL;
3464: tree->left = left;
3465: tree->right = right;
3466: tree->type = type;
3467: tree->node_idx = index;
3468: tree->first = -1;
3469: tree->next = -1;
3470: re_node_set_init_empty (&tree->eclosure);
3471:
3472: if (left != NULL)
3473: left->parent = tree;
3474: if (right != NULL)
3475: right->parent = tree;
3476: return tree;
3477: }
3478:
3479: /* Free the sub tree pointed by TREE. */
3480:
3481: static void
3482: free_bin_tree (tree)
3483: bin_tree_t *tree;
3484: {
3485: if (tree == NULL)
3486: return;
3487: /*re_node_set_free (&tree->eclosure);*/
3488: free_bin_tree (tree->left);
3489: free_bin_tree (tree->right);
3490: re_free (tree);
3491: }
3492:
3493: /* Duplicate the node SRC, and return new node. */
3494:
3495: static bin_tree_t *
3496: duplicate_tree (src, dfa)
3497: const bin_tree_t *src;
3498: re_dfa_t *dfa;
3499: {
3500: bin_tree_t *left = NULL, *right = NULL, *new_tree;
3501: int new_node_idx;
3502: /* Since node indies must be according to Post-order of the tree,
3503: we must duplicate the left at first. */
3504: if (src->left != NULL)
3505: {
3506: left = duplicate_tree (src->left, dfa);
3507: if (left == NULL)
3508: return NULL;
3509: }
3510:
3511: /* Secondaly, duplicate the right. */
3512: if (src->right != NULL)
3513: {
3514: right = duplicate_tree (src->right, dfa);
3515: if (right == NULL)
3516: {
3517: free_bin_tree (left);
3518: return NULL;
3519: }
3520: }
3521:
3522: /* At last, duplicate itself. */
3523: if (src->type == NON_TYPE)
3524: {
3525: new_node_idx = re_dfa_add_node (dfa, dfa->nodes[src->node_idx], 0);
3526: dfa->nodes[new_node_idx].duplicated = 1;
3527: if (BE (new_node_idx == -1, 0))
3528: {
3529: free_bin_tree (left);
3530: free_bin_tree (right);
3531: return NULL;
3532: }
3533: }
3534: else
3535: new_node_idx = src->type;
3536:
3537: new_tree = create_tree (left, right, src->type, new_node_idx);
3538: if (BE (new_tree == NULL, 0))
3539: {
3540: free_bin_tree (left);
3541: free_bin_tree (right);
3542: }
3543: return new_tree;
3544: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to regcomp.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / smartmontools / regex