1 | /* Extended regular expression matching and search library. |
2 | Copyright (C) 2002-2017 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, see |
18 | <http://www.gnu.org/licenses/>. */ |
19 | |
20 | static void re_string_construct_common (const char *str, int len, |
21 | re_string_t *pstr, |
22 | RE_TRANSLATE_TYPE trans, int icase, |
23 | const re_dfa_t *dfa) internal_function; |
24 | static re_dfastate_t *create_ci_newstate (const re_dfa_t *dfa, |
25 | const re_node_set *nodes, |
26 | unsigned int hash) internal_function; |
27 | static re_dfastate_t *create_cd_newstate (const re_dfa_t *dfa, |
28 | const re_node_set *nodes, |
29 | unsigned int context, |
30 | unsigned int hash) internal_function; |
31 | |
32 | /* Functions for string operation. */ |
33 | |
34 | /* This function allocate the buffers. It is necessary to call |
35 | re_string_reconstruct before using the object. */ |
36 | |
37 | static reg_errcode_t |
38 | internal_function __attribute_warn_unused_result__ |
39 | re_string_allocate (re_string_t *pstr, const char *str, int len, int init_len, |
40 | RE_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa) |
41 | { |
42 | reg_errcode_t ret; |
43 | int init_buf_len; |
44 | |
45 | /* Ensure at least one character fits into the buffers. */ |
46 | if (init_len < dfa->mb_cur_max) |
47 | init_len = dfa->mb_cur_max; |
48 | init_buf_len = (len + 1 < init_len) ? len + 1: init_len; |
49 | re_string_construct_common (str, len, pstr, trans, icase, dfa); |
50 | |
51 | ret = re_string_realloc_buffers (pstr, init_buf_len); |
52 | if (BE (ret != REG_NOERROR, 0)) |
53 | return ret; |
54 | |
55 | pstr->word_char = dfa->word_char; |
56 | pstr->word_ops_used = dfa->word_ops_used; |
57 | pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str; |
58 | pstr->valid_len = (pstr->mbs_allocated || dfa->mb_cur_max > 1) ? 0 : len; |
59 | pstr->valid_raw_len = pstr->valid_len; |
60 | return REG_NOERROR; |
61 | } |
62 | |
63 | /* This function allocate the buffers, and initialize them. */ |
64 | |
65 | static reg_errcode_t |
66 | internal_function __attribute_warn_unused_result__ |
67 | re_string_construct (re_string_t *pstr, const char *str, int len, |
68 | RE_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa) |
69 | { |
70 | reg_errcode_t ret; |
71 | memset (pstr, '\0', sizeof (re_string_t)); |
72 | re_string_construct_common (str, len, pstr, trans, icase, dfa); |
73 | |
74 | if (len > 0) |
75 | { |
76 | ret = re_string_realloc_buffers (pstr, len + 1); |
77 | if (BE (ret != REG_NOERROR, 0)) |
78 | return ret; |
79 | } |
80 | pstr->mbs = pstr->mbs_allocated ? pstr->mbs : (unsigned char *) str; |
81 | |
82 | if (icase) |
83 | { |
84 | #ifdef RE_ENABLE_I18N |
85 | if (dfa->mb_cur_max > 1) |
86 | { |
87 | while (1) |
88 | { |
89 | ret = build_wcs_upper_buffer (pstr); |
90 | if (BE (ret != REG_NOERROR, 0)) |
91 | return ret; |
92 | if (pstr->valid_raw_len >= len) |
93 | break; |
94 | if (pstr->bufs_len > pstr->valid_len + dfa->mb_cur_max) |
95 | break; |
96 | ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2); |
97 | if (BE (ret != REG_NOERROR, 0)) |
98 | return ret; |
99 | } |
100 | } |
101 | else |
102 | #endif /* RE_ENABLE_I18N */ |
103 | build_upper_buffer (pstr); |
104 | } |
105 | else |
106 | { |
107 | #ifdef RE_ENABLE_I18N |
108 | if (dfa->mb_cur_max > 1) |
109 | build_wcs_buffer (pstr); |
110 | else |
111 | #endif /* RE_ENABLE_I18N */ |
112 | { |
113 | if (trans != NULL) |
114 | re_string_translate_buffer (pstr); |
115 | else |
116 | { |
117 | pstr->valid_len = pstr->bufs_len; |
118 | pstr->valid_raw_len = pstr->bufs_len; |
119 | } |
120 | } |
121 | } |
122 | |
123 | return REG_NOERROR; |
124 | } |
125 | |
126 | /* Helper functions for re_string_allocate, and re_string_construct. */ |
127 | |
128 | static reg_errcode_t |
129 | internal_function __attribute_warn_unused_result__ |
130 | re_string_realloc_buffers (re_string_t *pstr, int new_buf_len) |
131 | { |
132 | #ifdef RE_ENABLE_I18N |
133 | if (pstr->mb_cur_max > 1) |
134 | { |
135 | wint_t *new_wcs; |
136 | |
137 | /* Avoid overflow in realloc. */ |
138 | const size_t max_object_size = MAX (sizeof (wint_t), sizeof (int)); |
139 | if (BE (SIZE_MAX / max_object_size < new_buf_len, 0)) |
140 | return REG_ESPACE; |
141 | |
142 | new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len); |
143 | if (BE (new_wcs == NULL, 0)) |
144 | return REG_ESPACE; |
145 | pstr->wcs = new_wcs; |
146 | if (pstr->offsets != NULL) |
147 | { |
148 | int *new_offsets = re_realloc (pstr->offsets, int, new_buf_len); |
149 | if (BE (new_offsets == NULL, 0)) |
150 | return REG_ESPACE; |
151 | pstr->offsets = new_offsets; |
152 | } |
153 | } |
154 | #endif /* RE_ENABLE_I18N */ |
155 | if (pstr->mbs_allocated) |
156 | { |
157 | unsigned char *new_mbs = re_realloc (pstr->mbs, unsigned char, |
158 | new_buf_len); |
159 | if (BE (new_mbs == NULL, 0)) |
160 | return REG_ESPACE; |
161 | pstr->mbs = new_mbs; |
162 | } |
163 | pstr->bufs_len = new_buf_len; |
164 | return REG_NOERROR; |
165 | } |
166 | |
167 | |
168 | static void |
169 | internal_function |
170 | re_string_construct_common (const char *str, int len, re_string_t *pstr, |
171 | RE_TRANSLATE_TYPE trans, int icase, |
172 | const re_dfa_t *dfa) |
173 | { |
174 | pstr->raw_mbs = (const unsigned char *) str; |
175 | pstr->len = len; |
176 | pstr->raw_len = len; |
177 | pstr->trans = trans; |
178 | pstr->icase = icase ? 1 : 0; |
179 | pstr->mbs_allocated = (trans != NULL || icase); |
180 | pstr->mb_cur_max = dfa->mb_cur_max; |
181 | pstr->is_utf8 = dfa->is_utf8; |
182 | pstr->map_notascii = dfa->map_notascii; |
183 | pstr->stop = pstr->len; |
184 | pstr->raw_stop = pstr->stop; |
185 | } |
186 | |
187 | #ifdef RE_ENABLE_I18N |
188 | |
189 | /* Build wide character buffer PSTR->WCS. |
190 | If the byte sequence of the string are: |
191 | <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3> |
192 | Then wide character buffer will be: |
193 | <wc1> , WEOF , <wc2> , WEOF , <wc3> |
194 | We use WEOF for padding, they indicate that the position isn't |
195 | a first byte of a multibyte character. |
196 | |
197 | Note that this function assumes PSTR->VALID_LEN elements are already |
198 | built and starts from PSTR->VALID_LEN. */ |
199 | |
200 | static void |
201 | internal_function |
202 | build_wcs_buffer (re_string_t *pstr) |
203 | { |
204 | #ifdef _LIBC |
205 | unsigned char buf[MB_LEN_MAX]; |
206 | assert (MB_LEN_MAX >= pstr->mb_cur_max); |
207 | #else |
208 | unsigned char buf[64]; |
209 | #endif |
210 | mbstate_t prev_st; |
211 | int byte_idx, end_idx, remain_len; |
212 | size_t mbclen; |
213 | |
214 | /* Build the buffers from pstr->valid_len to either pstr->len or |
215 | pstr->bufs_len. */ |
216 | end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; |
217 | for (byte_idx = pstr->valid_len; byte_idx < end_idx;) |
218 | { |
219 | wchar_t wc; |
220 | const char *p; |
221 | |
222 | remain_len = end_idx - byte_idx; |
223 | prev_st = pstr->cur_state; |
224 | /* Apply the translation if we need. */ |
225 | if (BE (pstr->trans != NULL, 0)) |
226 | { |
227 | int i, ch; |
228 | |
229 | for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i) |
230 | { |
231 | ch = pstr->raw_mbs [pstr->raw_mbs_idx + byte_idx + i]; |
232 | buf[i] = pstr->mbs[byte_idx + i] = pstr->trans[ch]; |
233 | } |
234 | p = (const char *) buf; |
235 | } |
236 | else |
237 | p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx; |
238 | mbclen = __mbrtowc (&wc, p, remain_len, &pstr->cur_state); |
239 | if (BE (mbclen == (size_t) -1 || mbclen == 0 |
240 | || (mbclen == (size_t) -2 && pstr->bufs_len >= pstr->len), 0)) |
241 | { |
242 | /* We treat these cases as a singlebyte character. */ |
243 | mbclen = 1; |
244 | wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]; |
245 | if (BE (pstr->trans != NULL, 0)) |
246 | wc = pstr->trans[wc]; |
247 | pstr->cur_state = prev_st; |
248 | } |
249 | else if (BE (mbclen == (size_t) -2, 0)) |
250 | { |
251 | /* The buffer doesn't have enough space, finish to build. */ |
252 | pstr->cur_state = prev_st; |
253 | break; |
254 | } |
255 | |
256 | /* Write wide character and padding. */ |
257 | pstr->wcs[byte_idx++] = wc; |
258 | /* Write paddings. */ |
259 | for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;) |
260 | pstr->wcs[byte_idx++] = WEOF; |
261 | } |
262 | pstr->valid_len = byte_idx; |
263 | pstr->valid_raw_len = byte_idx; |
264 | } |
265 | |
266 | /* Build wide character buffer PSTR->WCS like build_wcs_buffer, |
267 | but for REG_ICASE. */ |
268 | |
269 | static reg_errcode_t |
270 | internal_function __attribute_warn_unused_result__ |
271 | build_wcs_upper_buffer (re_string_t *pstr) |
272 | { |
273 | mbstate_t prev_st; |
274 | int src_idx, byte_idx, end_idx, remain_len; |
275 | size_t mbclen; |
276 | #ifdef _LIBC |
277 | char buf[MB_LEN_MAX]; |
278 | assert (MB_LEN_MAX >= pstr->mb_cur_max); |
279 | #else |
280 | char buf[64]; |
281 | #endif |
282 | |
283 | byte_idx = pstr->valid_len; |
284 | end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; |
285 | |
286 | /* The following optimization assumes that ASCII characters can be |
287 | mapped to wide characters with a simple cast. */ |
288 | if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed) |
289 | { |
290 | while (byte_idx < end_idx) |
291 | { |
292 | wchar_t wc; |
293 | |
294 | if (isascii (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]) |
295 | && mbsinit (&pstr->cur_state)) |
296 | { |
297 | /* In case of a singlebyte character. */ |
298 | pstr->mbs[byte_idx] |
299 | = toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]); |
300 | /* The next step uses the assumption that wchar_t is encoded |
301 | ASCII-safe: all ASCII values can be converted like this. */ |
302 | pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx]; |
303 | ++byte_idx; |
304 | continue; |
305 | } |
306 | |
307 | remain_len = end_idx - byte_idx; |
308 | prev_st = pstr->cur_state; |
309 | mbclen = __mbrtowc (&wc, |
310 | ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx |
311 | + byte_idx), remain_len, &pstr->cur_state); |
312 | if (BE (mbclen + 2 > 2, 1)) |
313 | { |
314 | wchar_t wcu = wc; |
315 | if (__iswlower (wc)) |
316 | { |
317 | size_t mbcdlen; |
318 | |
319 | wcu = __towupper (wc); |
320 | mbcdlen = __wcrtomb (buf, wcu, &prev_st); |
321 | if (BE (mbclen == mbcdlen, 1)) |
322 | memcpy (pstr->mbs + byte_idx, buf, mbclen); |
323 | else |
324 | { |
325 | src_idx = byte_idx; |
326 | goto offsets_needed; |
327 | } |
328 | } |
329 | else |
330 | memcpy (pstr->mbs + byte_idx, |
331 | pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen); |
332 | pstr->wcs[byte_idx++] = wcu; |
333 | /* Write paddings. */ |
334 | for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;) |
335 | pstr->wcs[byte_idx++] = WEOF; |
336 | } |
337 | else if (mbclen == (size_t) -1 || mbclen == 0 |
338 | || (mbclen == (size_t) -2 && pstr->bufs_len >= pstr->len)) |
339 | { |
340 | /* It is an invalid character, an incomplete character |
341 | at the end of the string, or '\0'. Just use the byte. */ |
342 | int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]; |
343 | pstr->mbs[byte_idx] = ch; |
344 | /* And also cast it to wide char. */ |
345 | pstr->wcs[byte_idx++] = (wchar_t) ch; |
346 | if (BE (mbclen == (size_t) -1, 0)) |
347 | pstr->cur_state = prev_st; |
348 | } |
349 | else |
350 | { |
351 | /* The buffer doesn't have enough space, finish to build. */ |
352 | pstr->cur_state = prev_st; |
353 | break; |
354 | } |
355 | } |
356 | pstr->valid_len = byte_idx; |
357 | pstr->valid_raw_len = byte_idx; |
358 | return REG_NOERROR; |
359 | } |
360 | else |
361 | for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;) |
362 | { |
363 | wchar_t wc; |
364 | const char *p; |
365 | offsets_needed: |
366 | remain_len = end_idx - byte_idx; |
367 | prev_st = pstr->cur_state; |
368 | if (BE (pstr->trans != NULL, 0)) |
369 | { |
370 | int i, ch; |
371 | |
372 | for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i) |
373 | { |
374 | ch = pstr->raw_mbs [pstr->raw_mbs_idx + src_idx + i]; |
375 | buf[i] = pstr->trans[ch]; |
376 | } |
377 | p = (const char *) buf; |
378 | } |
379 | else |
380 | p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx; |
381 | mbclen = __mbrtowc (&wc, p, remain_len, &pstr->cur_state); |
382 | if (BE (mbclen + 2 > 2, 1)) |
383 | { |
384 | wchar_t wcu = wc; |
385 | if (__iswlower (wc)) |
386 | { |
387 | size_t mbcdlen; |
388 | |
389 | wcu = __towupper (wc); |
390 | mbcdlen = __wcrtomb ((char *) buf, wcu, &prev_st); |
391 | if (BE (mbclen == mbcdlen, 1)) |
392 | memcpy (pstr->mbs + byte_idx, buf, mbclen); |
393 | else if (mbcdlen != (size_t) -1) |
394 | { |
395 | size_t i; |
396 | |
397 | if (byte_idx + mbcdlen > pstr->bufs_len) |
398 | { |
399 | pstr->cur_state = prev_st; |
400 | break; |
401 | } |
402 | |
403 | if (pstr->offsets == NULL) |
404 | { |
405 | pstr->offsets = re_malloc (int, pstr->bufs_len); |
406 | |
407 | if (pstr->offsets == NULL) |
408 | return REG_ESPACE; |
409 | } |
410 | if (!pstr->offsets_needed) |
411 | { |
412 | for (i = 0; i < (size_t) byte_idx; ++i) |
413 | pstr->offsets[i] = i; |
414 | pstr->offsets_needed = 1; |
415 | } |
416 | |
417 | memcpy (pstr->mbs + byte_idx, buf, mbcdlen); |
418 | pstr->wcs[byte_idx] = wcu; |
419 | pstr->offsets[byte_idx] = src_idx; |
420 | for (i = 1; i < mbcdlen; ++i) |
421 | { |
422 | pstr->offsets[byte_idx + i] |
423 | = src_idx + (i < mbclen ? i : mbclen - 1); |
424 | pstr->wcs[byte_idx + i] = WEOF; |
425 | } |
426 | pstr->len += mbcdlen - mbclen; |
427 | if (pstr->raw_stop > src_idx) |
428 | pstr->stop += mbcdlen - mbclen; |
429 | end_idx = (pstr->bufs_len > pstr->len) |
430 | ? pstr->len : pstr->bufs_len; |
431 | byte_idx += mbcdlen; |
432 | src_idx += mbclen; |
433 | continue; |
434 | } |
435 | else |
436 | memcpy (pstr->mbs + byte_idx, p, mbclen); |
437 | } |
438 | else |
439 | memcpy (pstr->mbs + byte_idx, p, mbclen); |
440 | |
441 | if (BE (pstr->offsets_needed != 0, 0)) |
442 | { |
443 | size_t i; |
444 | for (i = 0; i < mbclen; ++i) |
445 | pstr->offsets[byte_idx + i] = src_idx + i; |
446 | } |
447 | src_idx += mbclen; |
448 | |
449 | pstr->wcs[byte_idx++] = wcu; |
450 | /* Write paddings. */ |
451 | for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;) |
452 | pstr->wcs[byte_idx++] = WEOF; |
453 | } |
454 | else if (mbclen == (size_t) -1 || mbclen == 0 |
455 | || (mbclen == (size_t) -2 && pstr->bufs_len >= pstr->len)) |
456 | { |
457 | /* It is an invalid character or '\0'. Just use the byte. */ |
458 | int ch = pstr->raw_mbs[pstr->raw_mbs_idx + src_idx]; |
459 | |
460 | if (BE (pstr->trans != NULL, 0)) |
461 | ch = pstr->trans [ch]; |
462 | pstr->mbs[byte_idx] = ch; |
463 | |
464 | if (BE (pstr->offsets_needed != 0, 0)) |
465 | pstr->offsets[byte_idx] = src_idx; |
466 | ++src_idx; |
467 | |
468 | /* And also cast it to wide char. */ |
469 | pstr->wcs[byte_idx++] = (wchar_t) ch; |
470 | if (BE (mbclen == (size_t) -1, 0)) |
471 | pstr->cur_state = prev_st; |
472 | } |
473 | else |
474 | { |
475 | /* The buffer doesn't have enough space, finish to build. */ |
476 | pstr->cur_state = prev_st; |
477 | break; |
478 | } |
479 | } |
480 | pstr->valid_len = byte_idx; |
481 | pstr->valid_raw_len = src_idx; |
482 | return REG_NOERROR; |
483 | } |
484 | |
485 | /* Skip characters until the index becomes greater than NEW_RAW_IDX. |
486 | Return the index. */ |
487 | |
488 | static int |
489 | internal_function |
490 | re_string_skip_chars (re_string_t *pstr, int new_raw_idx, wint_t *last_wc) |
491 | { |
492 | mbstate_t prev_st; |
493 | int rawbuf_idx; |
494 | size_t mbclen; |
495 | wint_t wc = WEOF; |
496 | |
497 | /* Skip the characters which are not necessary to check. */ |
498 | for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len; |
499 | rawbuf_idx < new_raw_idx;) |
500 | { |
501 | wchar_t wc2; |
502 | int remain_len = pstr->raw_len - rawbuf_idx; |
503 | prev_st = pstr->cur_state; |
504 | mbclen = __mbrtowc (&wc2, (const char *) pstr->raw_mbs + rawbuf_idx, |
505 | remain_len, &pstr->cur_state); |
506 | if (BE ((ssize_t) mbclen <= 0, 0)) |
507 | { |
508 | /* We treat these cases as a single byte character. */ |
509 | if (mbclen == 0 || remain_len == 0) |
510 | wc = L'\0'; |
511 | else |
512 | wc = *(unsigned char *) (pstr->raw_mbs + rawbuf_idx); |
513 | mbclen = 1; |
514 | pstr->cur_state = prev_st; |
515 | } |
516 | else |
517 | wc = (wint_t) wc2; |
518 | /* Then proceed the next character. */ |
519 | rawbuf_idx += mbclen; |
520 | } |
521 | *last_wc = wc; |
522 | return rawbuf_idx; |
523 | } |
524 | #endif /* RE_ENABLE_I18N */ |
525 | |
526 | /* Build the buffer PSTR->MBS, and apply the translation if we need. |
527 | This function is used in case of REG_ICASE. */ |
528 | |
529 | static void |
530 | internal_function |
531 | build_upper_buffer (re_string_t *pstr) |
532 | { |
533 | int char_idx, end_idx; |
534 | end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; |
535 | |
536 | for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx) |
537 | { |
538 | int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx]; |
539 | if (BE (pstr->trans != NULL, 0)) |
540 | ch = pstr->trans[ch]; |
541 | if (islower (ch)) |
542 | pstr->mbs[char_idx] = toupper (ch); |
543 | else |
544 | pstr->mbs[char_idx] = ch; |
545 | } |
546 | pstr->valid_len = char_idx; |
547 | pstr->valid_raw_len = char_idx; |
548 | } |
549 | |
550 | /* Apply TRANS to the buffer in PSTR. */ |
551 | |
552 | static void |
553 | internal_function |
554 | re_string_translate_buffer (re_string_t *pstr) |
555 | { |
556 | int buf_idx, end_idx; |
557 | end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; |
558 | |
559 | for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx) |
560 | { |
561 | int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx]; |
562 | pstr->mbs[buf_idx] = pstr->trans[ch]; |
563 | } |
564 | |
565 | pstr->valid_len = buf_idx; |
566 | pstr->valid_raw_len = buf_idx; |
567 | } |
568 | |
569 | /* This function re-construct the buffers. |
570 | Concretely, convert to wide character in case of pstr->mb_cur_max > 1, |
571 | convert to upper case in case of REG_ICASE, apply translation. */ |
572 | |
573 | static reg_errcode_t |
574 | internal_function __attribute_warn_unused_result__ |
575 | re_string_reconstruct (re_string_t *pstr, int idx, int eflags) |
576 | { |
577 | int offset = idx - pstr->raw_mbs_idx; |
578 | if (BE (offset < 0, 0)) |
579 | { |
580 | /* Reset buffer. */ |
581 | #ifdef RE_ENABLE_I18N |
582 | if (pstr->mb_cur_max > 1) |
583 | memset (&pstr->cur_state, '\0', sizeof (mbstate_t)); |
584 | #endif /* RE_ENABLE_I18N */ |
585 | pstr->len = pstr->raw_len; |
586 | pstr->stop = pstr->raw_stop; |
587 | pstr->valid_len = 0; |
588 | pstr->raw_mbs_idx = 0; |
589 | pstr->valid_raw_len = 0; |
590 | pstr->offsets_needed = 0; |
591 | pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF |
592 | : CONTEXT_NEWLINE | CONTEXT_BEGBUF); |
593 | if (!pstr->mbs_allocated) |
594 | pstr->mbs = (unsigned char *) pstr->raw_mbs; |
595 | offset = idx; |
596 | } |
597 | |
598 | if (BE (offset != 0, 1)) |
599 | { |
600 | /* Should the already checked characters be kept? */ |
601 | if (BE (offset < pstr->valid_raw_len, 1)) |
602 | { |
603 | /* Yes, move them to the front of the buffer. */ |
604 | #ifdef RE_ENABLE_I18N |
605 | if (BE (pstr->offsets_needed, 0)) |
606 | { |
607 | int low = 0, high = pstr->valid_len, mid; |
608 | do |
609 | { |
610 | mid = (high + low) / 2; |
611 | if (pstr->offsets[mid] > offset) |
612 | high = mid; |
613 | else if (pstr->offsets[mid] < offset) |
614 | low = mid + 1; |
615 | else |
616 | break; |
617 | } |
618 | while (low < high); |
619 | if (pstr->offsets[mid] < offset) |
620 | ++mid; |
621 | pstr->tip_context = re_string_context_at (pstr, mid - 1, |
622 | eflags); |
623 | /* This can be quite complicated, so handle specially |
624 | only the common and easy case where the character with |
625 | different length representation of lower and upper |
626 | case is present at or after offset. */ |
627 | if (pstr->valid_len > offset |
628 | && mid == offset && pstr->offsets[mid] == offset) |
629 | { |
630 | memmove (pstr->wcs, pstr->wcs + offset, |
631 | (pstr->valid_len - offset) * sizeof (wint_t)); |
632 | memmove (pstr->mbs, pstr->mbs + offset, pstr->valid_len - offset); |
633 | pstr->valid_len -= offset; |
634 | pstr->valid_raw_len -= offset; |
635 | for (low = 0; low < pstr->valid_len; low++) |
636 | pstr->offsets[low] = pstr->offsets[low + offset] - offset; |
637 | } |
638 | else |
639 | { |
640 | /* Otherwise, just find out how long the partial multibyte |
641 | character at offset is and fill it with WEOF/255. */ |
642 | pstr->len = pstr->raw_len - idx + offset; |
643 | pstr->stop = pstr->raw_stop - idx + offset; |
644 | pstr->offsets_needed = 0; |
645 | while (mid > 0 && pstr->offsets[mid - 1] == offset) |
646 | --mid; |
647 | while (mid < pstr->valid_len) |
648 | if (pstr->wcs[mid] != WEOF) |
649 | break; |
650 | else |
651 | ++mid; |
652 | if (mid == pstr->valid_len) |
653 | pstr->valid_len = 0; |
654 | else |
655 | { |
656 | pstr->valid_len = pstr->offsets[mid] - offset; |
657 | if (pstr->valid_len) |
658 | { |
659 | for (low = 0; low < pstr->valid_len; ++low) |
660 | pstr->wcs[low] = WEOF; |
661 | memset (pstr->mbs, 255, pstr->valid_len); |
662 | } |
663 | } |
664 | pstr->valid_raw_len = pstr->valid_len; |
665 | } |
666 | } |
667 | else |
668 | #endif |
669 | { |
670 | pstr->tip_context = re_string_context_at (pstr, offset - 1, |
671 | eflags); |
672 | #ifdef RE_ENABLE_I18N |
673 | if (pstr->mb_cur_max > 1) |
674 | memmove (pstr->wcs, pstr->wcs + offset, |
675 | (pstr->valid_len - offset) * sizeof (wint_t)); |
676 | #endif /* RE_ENABLE_I18N */ |
677 | if (BE (pstr->mbs_allocated, 0)) |
678 | memmove (pstr->mbs, pstr->mbs + offset, |
679 | pstr->valid_len - offset); |
680 | pstr->valid_len -= offset; |
681 | pstr->valid_raw_len -= offset; |
682 | #if defined DEBUG && DEBUG |
683 | assert (pstr->valid_len > 0); |
684 | #endif |
685 | } |
686 | } |
687 | else |
688 | { |
689 | /* No, skip all characters until IDX. */ |
690 | int prev_valid_len = pstr->valid_len; |
691 | |
692 | #ifdef RE_ENABLE_I18N |
693 | if (BE (pstr->offsets_needed, 0)) |
694 | { |
695 | pstr->len = pstr->raw_len - idx + offset; |
696 | pstr->stop = pstr->raw_stop - idx + offset; |
697 | pstr->offsets_needed = 0; |
698 | } |
699 | #endif |
700 | pstr->valid_len = 0; |
701 | #ifdef RE_ENABLE_I18N |
702 | if (pstr->mb_cur_max > 1) |
703 | { |
704 | int wcs_idx; |
705 | wint_t wc = WEOF; |
706 | |
707 | if (pstr->is_utf8) |
708 | { |
709 | const unsigned char *raw, *p, *end; |
710 | |
711 | /* Special case UTF-8. Multi-byte chars start with any |
712 | byte other than 0x80 - 0xbf. */ |
713 | raw = pstr->raw_mbs + pstr->raw_mbs_idx; |
714 | end = raw + (offset - pstr->mb_cur_max); |
715 | if (end < pstr->raw_mbs) |
716 | end = pstr->raw_mbs; |
717 | p = raw + offset - 1; |
718 | #ifdef _LIBC |
719 | /* We know the wchar_t encoding is UCS4, so for the simple |
720 | case, ASCII characters, skip the conversion step. */ |
721 | if (isascii (*p) && BE (pstr->trans == NULL, 1)) |
722 | { |
723 | memset (&pstr->cur_state, '\0', sizeof (mbstate_t)); |
724 | /* pstr->valid_len = 0; */ |
725 | wc = (wchar_t) *p; |
726 | } |
727 | else |
728 | #endif |
729 | for (; p >= end; --p) |
730 | if ((*p & 0xc0) != 0x80) |
731 | { |
732 | mbstate_t cur_state; |
733 | wchar_t wc2; |
734 | int mlen = raw + pstr->len - p; |
735 | unsigned char buf[6]; |
736 | size_t mbclen; |
737 | |
738 | const unsigned char *pp = p; |
739 | if (BE (pstr->trans != NULL, 0)) |
740 | { |
741 | int i = mlen < 6 ? mlen : 6; |
742 | while (--i >= 0) |
743 | buf[i] = pstr->trans[p[i]]; |
744 | pp = buf; |
745 | } |
746 | /* XXX Don't use mbrtowc, we know which conversion |
747 | to use (UTF-8 -> UCS4). */ |
748 | memset (&cur_state, 0, sizeof (cur_state)); |
749 | mbclen = __mbrtowc (&wc2, (const char *) pp, mlen, |
750 | &cur_state); |
751 | if (raw + offset - p <= mbclen |
752 | && mbclen < (size_t) -2) |
753 | { |
754 | memset (&pstr->cur_state, '\0', |
755 | sizeof (mbstate_t)); |
756 | pstr->valid_len = mbclen - (raw + offset - p); |
757 | wc = wc2; |
758 | } |
759 | break; |
760 | } |
761 | } |
762 | |
763 | if (wc == WEOF) |
764 | pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx; |
765 | if (wc == WEOF) |
766 | pstr->tip_context |
767 | = re_string_context_at (pstr, prev_valid_len - 1, eflags); |
768 | else |
769 | pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0) |
770 | && IS_WIDE_WORD_CHAR (wc)) |
771 | ? CONTEXT_WORD |
772 | : ((IS_WIDE_NEWLINE (wc) |
773 | && pstr->newline_anchor) |
774 | ? CONTEXT_NEWLINE : 0)); |
775 | if (BE (pstr->valid_len, 0)) |
776 | { |
777 | for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx) |
778 | pstr->wcs[wcs_idx] = WEOF; |
779 | if (pstr->mbs_allocated) |
780 | memset (pstr->mbs, 255, pstr->valid_len); |
781 | } |
782 | pstr->valid_raw_len = pstr->valid_len; |
783 | } |
784 | else |
785 | #endif /* RE_ENABLE_I18N */ |
786 | { |
787 | int c = pstr->raw_mbs[pstr->raw_mbs_idx + offset - 1]; |
788 | pstr->valid_raw_len = 0; |
789 | if (pstr->trans) |
790 | c = pstr->trans[c]; |
791 | pstr->tip_context = (bitset_contain (pstr->word_char, c) |
792 | ? CONTEXT_WORD |
793 | : ((IS_NEWLINE (c) && pstr->newline_anchor) |
794 | ? CONTEXT_NEWLINE : 0)); |
795 | } |
796 | } |
797 | if (!BE (pstr->mbs_allocated, 0)) |
798 | pstr->mbs += offset; |
799 | } |
800 | pstr->raw_mbs_idx = idx; |
801 | pstr->len -= offset; |
802 | pstr->stop -= offset; |
803 | |
804 | /* Then build the buffers. */ |
805 | #ifdef RE_ENABLE_I18N |
806 | if (pstr->mb_cur_max > 1) |
807 | { |
808 | if (pstr->icase) |
809 | { |
810 | reg_errcode_t ret = build_wcs_upper_buffer (pstr); |
811 | if (BE (ret != REG_NOERROR, 0)) |
812 | return ret; |
813 | } |
814 | else |
815 | build_wcs_buffer (pstr); |
816 | } |
817 | else |
818 | #endif /* RE_ENABLE_I18N */ |
819 | if (BE (pstr->mbs_allocated, 0)) |
820 | { |
821 | if (pstr->icase) |
822 | build_upper_buffer (pstr); |
823 | else if (pstr->trans != NULL) |
824 | re_string_translate_buffer (pstr); |
825 | } |
826 | else |
827 | pstr->valid_len = pstr->len; |
828 | |
829 | pstr->cur_idx = 0; |
830 | return REG_NOERROR; |
831 | } |
832 | |
833 | static unsigned char |
834 | internal_function __attribute ((pure)) |
835 | re_string_peek_byte_case (const re_string_t *pstr, int idx) |
836 | { |
837 | int ch, off; |
838 | |
839 | /* Handle the common (easiest) cases first. */ |
840 | if (BE (!pstr->mbs_allocated, 1)) |
841 | return re_string_peek_byte (pstr, idx); |
842 | |
843 | #ifdef RE_ENABLE_I18N |
844 | if (pstr->mb_cur_max > 1 |
845 | && ! re_string_is_single_byte_char (pstr, pstr->cur_idx + idx)) |
846 | return re_string_peek_byte (pstr, idx); |
847 | #endif |
848 | |
849 | off = pstr->cur_idx + idx; |
850 | #ifdef RE_ENABLE_I18N |
851 | if (pstr->offsets_needed) |
852 | off = pstr->offsets[off]; |
853 | #endif |
854 | |
855 | ch = pstr->raw_mbs[pstr->raw_mbs_idx + off]; |
856 | |
857 | #ifdef RE_ENABLE_I18N |
858 | /* Ensure that e.g. for tr_TR.UTF-8 BACKSLASH DOTLESS SMALL LETTER I |
859 | this function returns CAPITAL LETTER I instead of first byte of |
860 | DOTLESS SMALL LETTER I. The latter would confuse the parser, |
861 | since peek_byte_case doesn't advance cur_idx in any way. */ |
862 | if (pstr->offsets_needed && !isascii (ch)) |
863 | return re_string_peek_byte (pstr, idx); |
864 | #endif |
865 | |
866 | return ch; |
867 | } |
868 | |
869 | static unsigned char |
870 | internal_function |
871 | re_string_fetch_byte_case (re_string_t *pstr) |
872 | { |
873 | if (BE (!pstr->mbs_allocated, 1)) |
874 | return re_string_fetch_byte (pstr); |
875 | |
876 | #ifdef RE_ENABLE_I18N |
877 | if (pstr->offsets_needed) |
878 | { |
879 | int off, ch; |
880 | |
881 | /* For tr_TR.UTF-8 [[:islower:]] there is |
882 | [[: CAPITAL LETTER I WITH DOT lower:]] in mbs. Skip |
883 | in that case the whole multi-byte character and return |
884 | the original letter. On the other side, with |
885 | [[: DOTLESS SMALL LETTER I return [[:I, as doing |
886 | anything else would complicate things too much. */ |
887 | |
888 | if (!re_string_first_byte (pstr, pstr->cur_idx)) |
889 | return re_string_fetch_byte (pstr); |
890 | |
891 | off = pstr->offsets[pstr->cur_idx]; |
892 | ch = pstr->raw_mbs[pstr->raw_mbs_idx + off]; |
893 | |
894 | if (! isascii (ch)) |
895 | return re_string_fetch_byte (pstr); |
896 | |
897 | re_string_skip_bytes (pstr, |
898 | re_string_char_size_at (pstr, pstr->cur_idx)); |
899 | return ch; |
900 | } |
901 | #endif |
902 | |
903 | return pstr->raw_mbs[pstr->raw_mbs_idx + pstr->cur_idx++]; |
904 | } |
905 | |
906 | static void |
907 | internal_function |
908 | re_string_destruct (re_string_t *pstr) |
909 | { |
910 | #ifdef RE_ENABLE_I18N |
911 | re_free (pstr->wcs); |
912 | re_free (pstr->offsets); |
913 | #endif /* RE_ENABLE_I18N */ |
914 | if (pstr->mbs_allocated) |
915 | re_free (pstr->mbs); |
916 | } |
917 | |
918 | /* Return the context at IDX in INPUT. */ |
919 | |
920 | static unsigned int |
921 | internal_function |
922 | re_string_context_at (const re_string_t *input, int idx, int eflags) |
923 | { |
924 | int c; |
925 | if (BE (idx < 0, 0)) |
926 | /* In this case, we use the value stored in input->tip_context, |
927 | since we can't know the character in input->mbs[-1] here. */ |
928 | return input->tip_context; |
929 | if (BE (idx == input->len, 0)) |
930 | return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF |
931 | : CONTEXT_NEWLINE | CONTEXT_ENDBUF); |
932 | #ifdef RE_ENABLE_I18N |
933 | if (input->mb_cur_max > 1) |
934 | { |
935 | wint_t wc; |
936 | int wc_idx = idx; |
937 | while(input->wcs[wc_idx] == WEOF) |
938 | { |
939 | #if defined DEBUG && DEBUG |
940 | /* It must not happen. */ |
941 | assert (wc_idx >= 0); |
942 | #endif |
943 | --wc_idx; |
944 | if (wc_idx < 0) |
945 | return input->tip_context; |
946 | } |
947 | wc = input->wcs[wc_idx]; |
948 | if (BE (input->word_ops_used != 0, 0) && IS_WIDE_WORD_CHAR (wc)) |
949 | return CONTEXT_WORD; |
950 | return (IS_WIDE_NEWLINE (wc) && input->newline_anchor |
951 | ? CONTEXT_NEWLINE : 0); |
952 | } |
953 | else |
954 | #endif |
955 | { |
956 | c = re_string_byte_at (input, idx); |
957 | if (bitset_contain (input->word_char, c)) |
958 | return CONTEXT_WORD; |
959 | return IS_NEWLINE (c) && input->newline_anchor ? CONTEXT_NEWLINE : 0; |
960 | } |
961 | } |
962 | |
963 | /* Functions for set operation. */ |
964 | |
965 | static reg_errcode_t |
966 | internal_function __attribute_warn_unused_result__ |
967 | re_node_set_alloc (re_node_set *set, int size) |
968 | { |
969 | set->alloc = size; |
970 | set->nelem = 0; |
971 | set->elems = re_malloc (int, size); |
972 | if (BE (set->elems == NULL, 0)) |
973 | return REG_ESPACE; |
974 | return REG_NOERROR; |
975 | } |
976 | |
977 | static reg_errcode_t |
978 | internal_function __attribute_warn_unused_result__ |
979 | re_node_set_init_1 (re_node_set *set, int elem) |
980 | { |
981 | set->alloc = 1; |
982 | set->nelem = 1; |
983 | set->elems = re_malloc (int, 1); |
984 | if (BE (set->elems == NULL, 0)) |
985 | { |
986 | set->alloc = set->nelem = 0; |
987 | return REG_ESPACE; |
988 | } |
989 | set->elems[0] = elem; |
990 | return REG_NOERROR; |
991 | } |
992 | |
993 | static reg_errcode_t |
994 | internal_function __attribute_warn_unused_result__ |
995 | re_node_set_init_2 (re_node_set *set, int elem1, int elem2) |
996 | { |
997 | set->alloc = 2; |
998 | set->elems = re_malloc (int, 2); |
999 | if (BE (set->elems == NULL, 0)) |
1000 | return REG_ESPACE; |
1001 | if (elem1 == elem2) |
1002 | { |
1003 | set->nelem = 1; |
1004 | set->elems[0] = elem1; |
1005 | } |
1006 | else |
1007 | { |
1008 | set->nelem = 2; |
1009 | if (elem1 < elem2) |
1010 | { |
1011 | set->elems[0] = elem1; |
1012 | set->elems[1] = elem2; |
1013 | } |
1014 | else |
1015 | { |
1016 | set->elems[0] = elem2; |
1017 | set->elems[1] = elem1; |
1018 | } |
1019 | } |
1020 | return REG_NOERROR; |
1021 | } |
1022 | |
1023 | static reg_errcode_t |
1024 | internal_function __attribute_warn_unused_result__ |
1025 | re_node_set_init_copy (re_node_set *dest, const re_node_set *src) |
1026 | { |
1027 | dest->nelem = src->nelem; |
1028 | if (src->nelem > 0) |
1029 | { |
1030 | dest->alloc = dest->nelem; |
1031 | dest->elems = re_malloc (int, dest->alloc); |
1032 | if (BE (dest->elems == NULL, 0)) |
1033 | { |
1034 | dest->alloc = dest->nelem = 0; |
1035 | return REG_ESPACE; |
1036 | } |
1037 | memcpy (dest->elems, src->elems, src->nelem * sizeof (int)); |
1038 | } |
1039 | else |
1040 | re_node_set_init_empty (dest); |
1041 | return REG_NOERROR; |
1042 | } |
1043 | |
1044 | /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to |
1045 | DEST. Return value indicate the error code or REG_NOERROR if succeeded. |
1046 | Note: We assume dest->elems is NULL, when dest->alloc is 0. */ |
1047 | |
1048 | static reg_errcode_t |
1049 | internal_function __attribute_warn_unused_result__ |
1050 | re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, |
1051 | const re_node_set *src2) |
1052 | { |
1053 | int i1, i2, is, id, delta, sbase; |
1054 | if (src1->nelem == 0 || src2->nelem == 0) |
1055 | return REG_NOERROR; |
1056 | |
1057 | /* We need dest->nelem + 2 * elems_in_intersection; this is a |
1058 | conservative estimate. */ |
1059 | if (src1->nelem + src2->nelem + dest->nelem > dest->alloc) |
1060 | { |
1061 | int new_alloc = src1->nelem + src2->nelem + dest->alloc; |
1062 | int *new_elems = re_realloc (dest->elems, int, new_alloc); |
1063 | if (BE (new_elems == NULL, 0)) |
1064 | return REG_ESPACE; |
1065 | dest->elems = new_elems; |
1066 | dest->alloc = new_alloc; |
1067 | } |
1068 | |
1069 | /* Find the items in the intersection of SRC1 and SRC2, and copy |
1070 | into the top of DEST those that are not already in DEST itself. */ |
1071 | sbase = dest->nelem + src1->nelem + src2->nelem; |
1072 | i1 = src1->nelem - 1; |
1073 | i2 = src2->nelem - 1; |
1074 | id = dest->nelem - 1; |
1075 | for (;;) |
1076 | { |
1077 | if (src1->elems[i1] == src2->elems[i2]) |
1078 | { |
1079 | /* Try to find the item in DEST. Maybe we could binary search? */ |
1080 | while (id >= 0 && dest->elems[id] > src1->elems[i1]) |
1081 | --id; |
1082 | |
1083 | if (id < 0 || dest->elems[id] != src1->elems[i1]) |
1084 | dest->elems[--sbase] = src1->elems[i1]; |
1085 | |
1086 | if (--i1 < 0 || --i2 < 0) |
1087 | break; |
1088 | } |
1089 | |
1090 | /* Lower the highest of the two items. */ |
1091 | else if (src1->elems[i1] < src2->elems[i2]) |
1092 | { |
1093 | if (--i2 < 0) |
1094 | break; |
1095 | } |
1096 | else |
1097 | { |
1098 | if (--i1 < 0) |
1099 | break; |
1100 | } |
1101 | } |
1102 | |
1103 | id = dest->nelem - 1; |
1104 | is = dest->nelem + src1->nelem + src2->nelem - 1; |
1105 | delta = is - sbase + 1; |
1106 | |
1107 | /* Now copy. When DELTA becomes zero, the remaining |
1108 | DEST elements are already in place; this is more or |
1109 | less the same loop that is in re_node_set_merge. */ |
1110 | dest->nelem += delta; |
1111 | if (delta > 0 && id >= 0) |
1112 | for (;;) |
1113 | { |
1114 | if (dest->elems[is] > dest->elems[id]) |
1115 | { |
1116 | /* Copy from the top. */ |
1117 | dest->elems[id + delta--] = dest->elems[is--]; |
1118 | if (delta == 0) |
1119 | break; |
1120 | } |
1121 | else |
1122 | { |
1123 | /* Slide from the bottom. */ |
1124 | dest->elems[id + delta] = dest->elems[id]; |
1125 | if (--id < 0) |
1126 | break; |
1127 | } |
1128 | } |
1129 | |
1130 | /* Copy remaining SRC elements. */ |
1131 | memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int)); |
1132 | |
1133 | return REG_NOERROR; |
1134 | } |
1135 | |
1136 | /* Calculate the union set of the sets SRC1 and SRC2. And store it to |
1137 | DEST. Return value indicate the error code or REG_NOERROR if succeeded. */ |
1138 | |
1139 | static reg_errcode_t |
1140 | internal_function __attribute_warn_unused_result__ |
1141 | re_node_set_init_union (re_node_set *dest, const re_node_set *src1, |
1142 | const re_node_set *src2) |
1143 | { |
1144 | int i1, i2, id; |
1145 | if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0) |
1146 | { |
1147 | dest->alloc = src1->nelem + src2->nelem; |
1148 | dest->elems = re_malloc (int, dest->alloc); |
1149 | if (BE (dest->elems == NULL, 0)) |
1150 | return REG_ESPACE; |
1151 | } |
1152 | else |
1153 | { |
1154 | if (src1 != NULL && src1->nelem > 0) |
1155 | return re_node_set_init_copy (dest, src1); |
1156 | else if (src2 != NULL && src2->nelem > 0) |
1157 | return re_node_set_init_copy (dest, src2); |
1158 | else |
1159 | re_node_set_init_empty (dest); |
1160 | return REG_NOERROR; |
1161 | } |
1162 | for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;) |
1163 | { |
1164 | if (src1->elems[i1] > src2->elems[i2]) |
1165 | { |
1166 | dest->elems[id++] = src2->elems[i2++]; |
1167 | continue; |
1168 | } |
1169 | if (src1->elems[i1] == src2->elems[i2]) |
1170 | ++i2; |
1171 | dest->elems[id++] = src1->elems[i1++]; |
1172 | } |
1173 | if (i1 < src1->nelem) |
1174 | { |
1175 | memcpy (dest->elems + id, src1->elems + i1, |
1176 | (src1->nelem - i1) * sizeof (int)); |
1177 | id += src1->nelem - i1; |
1178 | } |
1179 | else if (i2 < src2->nelem) |
1180 | { |
1181 | memcpy (dest->elems + id, src2->elems + i2, |
1182 | (src2->nelem - i2) * sizeof (int)); |
1183 | id += src2->nelem - i2; |
1184 | } |
1185 | dest->nelem = id; |
1186 | return REG_NOERROR; |
1187 | } |
1188 | |
1189 | /* Calculate the union set of the sets DEST and SRC. And store it to |
1190 | DEST. Return value indicate the error code or REG_NOERROR if succeeded. */ |
1191 | |
1192 | static reg_errcode_t |
1193 | internal_function __attribute_warn_unused_result__ |
1194 | re_node_set_merge (re_node_set *dest, const re_node_set *src) |
1195 | { |
1196 | int is, id, sbase, delta; |
1197 | if (src == NULL || src->nelem == 0) |
1198 | return REG_NOERROR; |
1199 | if (dest->alloc < 2 * src->nelem + dest->nelem) |
1200 | { |
1201 | int new_alloc = 2 * (src->nelem + dest->alloc); |
1202 | int *new_buffer = re_realloc (dest->elems, int, new_alloc); |
1203 | if (BE (new_buffer == NULL, 0)) |
1204 | return REG_ESPACE; |
1205 | dest->elems = new_buffer; |
1206 | dest->alloc = new_alloc; |
1207 | } |
1208 | |
1209 | if (BE (dest->nelem == 0, 0)) |
1210 | { |
1211 | dest->nelem = src->nelem; |
1212 | memcpy (dest->elems, src->elems, src->nelem * sizeof (int)); |
1213 | return REG_NOERROR; |
1214 | } |
1215 | |
1216 | /* Copy into the top of DEST the items of SRC that are not |
1217 | found in DEST. Maybe we could binary search in DEST? */ |
1218 | for (sbase = dest->nelem + 2 * src->nelem, |
1219 | is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; ) |
1220 | { |
1221 | if (dest->elems[id] == src->elems[is]) |
1222 | is--, id--; |
1223 | else if (dest->elems[id] < src->elems[is]) |
1224 | dest->elems[--sbase] = src->elems[is--]; |
1225 | else /* if (dest->elems[id] > src->elems[is]) */ |
1226 | --id; |
1227 | } |
1228 | |
1229 | if (is >= 0) |
1230 | { |
1231 | /* If DEST is exhausted, the remaining items of SRC must be unique. */ |
1232 | sbase -= is + 1; |
1233 | memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int)); |
1234 | } |
1235 | |
1236 | id = dest->nelem - 1; |
1237 | is = dest->nelem + 2 * src->nelem - 1; |
1238 | delta = is - sbase + 1; |
1239 | if (delta == 0) |
1240 | return REG_NOERROR; |
1241 | |
1242 | /* Now copy. When DELTA becomes zero, the remaining |
1243 | DEST elements are already in place. */ |
1244 | dest->nelem += delta; |
1245 | for (;;) |
1246 | { |
1247 | if (dest->elems[is] > dest->elems[id]) |
1248 | { |
1249 | /* Copy from the top. */ |
1250 | dest->elems[id + delta--] = dest->elems[is--]; |
1251 | if (delta == 0) |
1252 | break; |
1253 | } |
1254 | else |
1255 | { |
1256 | /* Slide from the bottom. */ |
1257 | dest->elems[id + delta] = dest->elems[id]; |
1258 | if (--id < 0) |
1259 | { |
1260 | /* Copy remaining SRC elements. */ |
1261 | memcpy (dest->elems, dest->elems + sbase, |
1262 | delta * sizeof (int)); |
1263 | break; |
1264 | } |
1265 | } |
1266 | } |
1267 | |
1268 | return REG_NOERROR; |
1269 | } |
1270 | |
1271 | /* Insert the new element ELEM to the re_node_set* SET. |
1272 | SET should not already have ELEM. |
1273 | return -1 if an error is occured, return 1 otherwise. */ |
1274 | |
1275 | static int |
1276 | internal_function __attribute_warn_unused_result__ |
1277 | re_node_set_insert (re_node_set *set, int elem) |
1278 | { |
1279 | int idx; |
1280 | /* In case the set is empty. */ |
1281 | if (set->alloc == 0) |
1282 | { |
1283 | if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1)) |
1284 | return 1; |
1285 | else |
1286 | return -1; |
1287 | } |
1288 | |
1289 | if (BE (set->nelem, 0) == 0) |
1290 | { |
1291 | /* We already guaranteed above that set->alloc != 0. */ |
1292 | set->elems[0] = elem; |
1293 | ++set->nelem; |
1294 | return 1; |
1295 | } |
1296 | |
1297 | /* Realloc if we need. */ |
1298 | if (set->alloc == set->nelem) |
1299 | { |
1300 | int *new_elems; |
1301 | set->alloc = set->alloc * 2; |
1302 | new_elems = re_realloc (set->elems, int, set->alloc); |
1303 | if (BE (new_elems == NULL, 0)) |
1304 | return -1; |
1305 | set->elems = new_elems; |
1306 | } |
1307 | |
1308 | /* Move the elements which follows the new element. Test the |
1309 | first element separately to skip a check in the inner loop. */ |
1310 | if (elem < set->elems[0]) |
1311 | { |
1312 | idx = 0; |
1313 | for (idx = set->nelem; idx > 0; idx--) |
1314 | set->elems[idx] = set->elems[idx - 1]; |
1315 | } |
1316 | else |
1317 | { |
1318 | for (idx = set->nelem; set->elems[idx - 1] > elem; idx--) |
1319 | set->elems[idx] = set->elems[idx - 1]; |
1320 | } |
1321 | |
1322 | /* Insert the new element. */ |
1323 | set->elems[idx] = elem; |
1324 | ++set->nelem; |
1325 | return 1; |
1326 | } |
1327 | |
1328 | /* Insert the new element ELEM to the re_node_set* SET. |
1329 | SET should not already have any element greater than or equal to ELEM. |
1330 | Return -1 if an error is occured, return 1 otherwise. */ |
1331 | |
1332 | static int |
1333 | internal_function __attribute_warn_unused_result__ |
1334 | re_node_set_insert_last (re_node_set *set, int elem) |
1335 | { |
1336 | /* Realloc if we need. */ |
1337 | if (set->alloc == set->nelem) |
1338 | { |
1339 | int *new_elems; |
1340 | set->alloc = (set->alloc + 1) * 2; |
1341 | new_elems = re_realloc (set->elems, int, set->alloc); |
1342 | if (BE (new_elems == NULL, 0)) |
1343 | return -1; |
1344 | set->elems = new_elems; |
1345 | } |
1346 | |
1347 | /* Insert the new element. */ |
1348 | set->elems[set->nelem++] = elem; |
1349 | return 1; |
1350 | } |
1351 | |
1352 | /* Compare two node sets SET1 and SET2. |
1353 | return 1 if SET1 and SET2 are equivalent, return 0 otherwise. */ |
1354 | |
1355 | static int |
1356 | internal_function __attribute ((pure)) |
1357 | re_node_set_compare (const re_node_set *set1, const re_node_set *set2) |
1358 | { |
1359 | int i; |
1360 | if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem) |
1361 | return 0; |
1362 | for (i = set1->nelem ; --i >= 0 ; ) |
1363 | if (set1->elems[i] != set2->elems[i]) |
1364 | return 0; |
1365 | return 1; |
1366 | } |
1367 | |
1368 | /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise. */ |
1369 | |
1370 | static int |
1371 | internal_function __attribute ((pure)) |
1372 | re_node_set_contains (const re_node_set *set, int elem) |
1373 | { |
1374 | unsigned int idx, right, mid; |
1375 | if (set->nelem <= 0) |
1376 | return 0; |
1377 | |
1378 | /* Binary search the element. */ |
1379 | idx = 0; |
1380 | right = set->nelem - 1; |
1381 | while (idx < right) |
1382 | { |
1383 | mid = (idx + right) / 2; |
1384 | if (set->elems[mid] < elem) |
1385 | idx = mid + 1; |
1386 | else |
1387 | right = mid; |
1388 | } |
1389 | return set->elems[idx] == elem ? idx + 1 : 0; |
1390 | } |
1391 | |
1392 | static void |
1393 | internal_function |
1394 | re_node_set_remove_at (re_node_set *set, int idx) |
1395 | { |
1396 | if (idx < 0 || idx >= set->nelem) |
1397 | return; |
1398 | --set->nelem; |
1399 | for (; idx < set->nelem; idx++) |
1400 | set->elems[idx] = set->elems[idx + 1]; |
1401 | } |
1402 | |
1403 | |
1404 | /* Add the token TOKEN to dfa->nodes, and return the index of the token. |
1405 | Or return -1, if an error will be occured. */ |
1406 | |
1407 | static int |
1408 | internal_function |
1409 | re_dfa_add_node (re_dfa_t *dfa, re_token_t token) |
1410 | { |
1411 | int type = token.type; |
1412 | if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0)) |
1413 | { |
1414 | size_t new_nodes_alloc = dfa->nodes_alloc * 2; |
1415 | int *new_nexts, *new_indices; |
1416 | re_node_set *new_edests, *new_eclosures; |
1417 | re_token_t *new_nodes; |
1418 | |
1419 | /* Avoid overflows in realloc. */ |
1420 | const size_t max_object_size = MAX (sizeof (re_token_t), |
1421 | MAX (sizeof (re_node_set), |
1422 | sizeof (int))); |
1423 | if (BE (SIZE_MAX / max_object_size < new_nodes_alloc, 0)) |
1424 | return -1; |
1425 | |
1426 | new_nodes = re_realloc (dfa->nodes, re_token_t, new_nodes_alloc); |
1427 | if (BE (new_nodes == NULL, 0)) |
1428 | return -1; |
1429 | dfa->nodes = new_nodes; |
1430 | new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc); |
1431 | new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc); |
1432 | new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc); |
1433 | new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc); |
1434 | if (BE (new_nexts == NULL || new_indices == NULL |
1435 | || new_edests == NULL || new_eclosures == NULL, 0)) |
1436 | return -1; |
1437 | dfa->nexts = new_nexts; |
1438 | dfa->org_indices = new_indices; |
1439 | dfa->edests = new_edests; |
1440 | dfa->eclosures = new_eclosures; |
1441 | dfa->nodes_alloc = new_nodes_alloc; |
1442 | } |
1443 | dfa->nodes[dfa->nodes_len] = token; |
1444 | dfa->nodes[dfa->nodes_len].constraint = 0; |
1445 | #ifdef RE_ENABLE_I18N |
1446 | dfa->nodes[dfa->nodes_len].accept_mb = |
1447 | (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET; |
1448 | #endif |
1449 | dfa->nexts[dfa->nodes_len] = -1; |
1450 | re_node_set_init_empty (dfa->edests + dfa->nodes_len); |
1451 | re_node_set_init_empty (dfa->eclosures + dfa->nodes_len); |
1452 | return dfa->nodes_len++; |
1453 | } |
1454 | |
1455 | static inline unsigned int |
1456 | internal_function |
1457 | calc_state_hash (const re_node_set *nodes, unsigned int context) |
1458 | { |
1459 | unsigned int hash = nodes->nelem + context; |
1460 | int i; |
1461 | for (i = 0 ; i < nodes->nelem ; i++) |
1462 | hash += nodes->elems[i]; |
1463 | return hash; |
1464 | } |
1465 | |
1466 | /* Search for the state whose node_set is equivalent to NODES. |
1467 | Return the pointer to the state, if we found it in the DFA. |
1468 | Otherwise create the new one and return it. In case of an error |
1469 | return NULL and set the error code in ERR. |
1470 | Note: - We assume NULL as the invalid state, then it is possible that |
1471 | return value is NULL and ERR is REG_NOERROR. |
1472 | - We never return non-NULL value in case of any errors, it is for |
1473 | optimization. */ |
1474 | |
1475 | static re_dfastate_t * |
1476 | internal_function __attribute_warn_unused_result__ |
1477 | re_acquire_state (reg_errcode_t *err, const re_dfa_t *dfa, |
1478 | const re_node_set *nodes) |
1479 | { |
1480 | unsigned int hash; |
1481 | re_dfastate_t *new_state; |
1482 | struct re_state_table_entry *spot; |
1483 | int i; |
1484 | if (BE (nodes->nelem == 0, 0)) |
1485 | { |
1486 | *err = REG_NOERROR; |
1487 | return NULL; |
1488 | } |
1489 | hash = calc_state_hash (nodes, 0); |
1490 | spot = dfa->state_table + (hash & dfa->state_hash_mask); |
1491 | |
1492 | for (i = 0 ; i < spot->num ; i++) |
1493 | { |
1494 | re_dfastate_t *state = spot->array[i]; |
1495 | if (hash != state->hash) |
1496 | continue; |
1497 | if (re_node_set_compare (&state->nodes, nodes)) |
1498 | return state; |
1499 | } |
1500 | |
1501 | /* There are no appropriate state in the dfa, create the new one. */ |
1502 | new_state = create_ci_newstate (dfa, nodes, hash); |
1503 | if (BE (new_state == NULL, 0)) |
1504 | *err = REG_ESPACE; |
1505 | |
1506 | return new_state; |
1507 | } |
1508 | |
1509 | /* Search for the state whose node_set is equivalent to NODES and |
1510 | whose context is equivalent to CONTEXT. |
1511 | Return the pointer to the state, if we found it in the DFA. |
1512 | Otherwise create the new one and return it. In case of an error |
1513 | return NULL and set the error code in ERR. |
1514 | Note: - We assume NULL as the invalid state, then it is possible that |
1515 | return value is NULL and ERR is REG_NOERROR. |
1516 | - We never return non-NULL value in case of any errors, it is for |
1517 | optimization. */ |
1518 | |
1519 | static re_dfastate_t * |
1520 | internal_function __attribute_warn_unused_result__ |
1521 | re_acquire_state_context (reg_errcode_t *err, const re_dfa_t *dfa, |
1522 | const re_node_set *nodes, unsigned int context) |
1523 | { |
1524 | unsigned int hash; |
1525 | re_dfastate_t *new_state; |
1526 | struct re_state_table_entry *spot; |
1527 | int i; |
1528 | if (nodes->nelem == 0) |
1529 | { |
1530 | *err = REG_NOERROR; |
1531 | return NULL; |
1532 | } |
1533 | hash = calc_state_hash (nodes, context); |
1534 | spot = dfa->state_table + (hash & dfa->state_hash_mask); |
1535 | |
1536 | for (i = 0 ; i < spot->num ; i++) |
1537 | { |
1538 | re_dfastate_t *state = spot->array[i]; |
1539 | if (state->hash == hash |
1540 | && state->context == context |
1541 | && re_node_set_compare (state->entrance_nodes, nodes)) |
1542 | return state; |
1543 | } |
1544 | /* There are no appropriate state in `dfa', create the new one. */ |
1545 | new_state = create_cd_newstate (dfa, nodes, context, hash); |
1546 | if (BE (new_state == NULL, 0)) |
1547 | *err = REG_ESPACE; |
1548 | |
1549 | return new_state; |
1550 | } |
1551 | |
1552 | /* Finish initialization of the new state NEWSTATE, and using its hash value |
1553 | HASH put in the appropriate bucket of DFA's state table. Return value |
1554 | indicates the error code if failed. */ |
1555 | |
1556 | static reg_errcode_t |
1557 | __attribute_warn_unused_result__ |
1558 | register_state (const re_dfa_t *dfa, re_dfastate_t *newstate, |
1559 | unsigned int hash) |
1560 | { |
1561 | struct re_state_table_entry *spot; |
1562 | reg_errcode_t err; |
1563 | int i; |
1564 | |
1565 | newstate->hash = hash; |
1566 | err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem); |
1567 | if (BE (err != REG_NOERROR, 0)) |
1568 | return REG_ESPACE; |
1569 | for (i = 0; i < newstate->nodes.nelem; i++) |
1570 | { |
1571 | int elem = newstate->nodes.elems[i]; |
1572 | if (!IS_EPSILON_NODE (dfa->nodes[elem].type)) |
1573 | if (re_node_set_insert_last (&newstate->non_eps_nodes, elem) < 0) |
1574 | return REG_ESPACE; |
1575 | } |
1576 | |
1577 | spot = dfa->state_table + (hash & dfa->state_hash_mask); |
1578 | if (BE (spot->alloc <= spot->num, 0)) |
1579 | { |
1580 | int new_alloc = 2 * spot->num + 2; |
1581 | re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *, |
1582 | new_alloc); |
1583 | if (BE (new_array == NULL, 0)) |
1584 | return REG_ESPACE; |
1585 | spot->array = new_array; |
1586 | spot->alloc = new_alloc; |
1587 | } |
1588 | spot->array[spot->num++] = newstate; |
1589 | return REG_NOERROR; |
1590 | } |
1591 | |
1592 | static void |
1593 | free_state (re_dfastate_t *state) |
1594 | { |
1595 | re_node_set_free (&state->non_eps_nodes); |
1596 | re_node_set_free (&state->inveclosure); |
1597 | if (state->entrance_nodes != &state->nodes) |
1598 | { |
1599 | re_node_set_free (state->entrance_nodes); |
1600 | re_free (state->entrance_nodes); |
1601 | } |
1602 | re_node_set_free (&state->nodes); |
1603 | re_free (state->word_trtable); |
1604 | re_free (state->trtable); |
1605 | re_free (state); |
1606 | } |
1607 | |
1608 | /* Create the new state which is independ of contexts. |
1609 | Return the new state if succeeded, otherwise return NULL. */ |
1610 | |
1611 | static re_dfastate_t * |
1612 | internal_function __attribute_warn_unused_result__ |
1613 | create_ci_newstate (const re_dfa_t *dfa, const re_node_set *nodes, |
1614 | unsigned int hash) |
1615 | { |
1616 | int i; |
1617 | reg_errcode_t err; |
1618 | re_dfastate_t *newstate; |
1619 | |
1620 | newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); |
1621 | if (BE (newstate == NULL, 0)) |
1622 | return NULL; |
1623 | err = re_node_set_init_copy (&newstate->nodes, nodes); |
1624 | if (BE (err != REG_NOERROR, 0)) |
1625 | { |
1626 | re_free (newstate); |
1627 | return NULL; |
1628 | } |
1629 | |
1630 | newstate->entrance_nodes = &newstate->nodes; |
1631 | for (i = 0 ; i < nodes->nelem ; i++) |
1632 | { |
1633 | re_token_t *node = dfa->nodes + nodes->elems[i]; |
1634 | re_token_type_t type = node->type; |
1635 | if (type == CHARACTER && !node->constraint) |
1636 | continue; |
1637 | #ifdef RE_ENABLE_I18N |
1638 | newstate->accept_mb |= node->accept_mb; |
1639 | #endif /* RE_ENABLE_I18N */ |
1640 | |
1641 | /* If the state has the halt node, the state is a halt state. */ |
1642 | if (type == END_OF_RE) |
1643 | newstate->halt = 1; |
1644 | else if (type == OP_BACK_REF) |
1645 | newstate->has_backref = 1; |
1646 | else if (type == ANCHOR || node->constraint) |
1647 | newstate->has_constraint = 1; |
1648 | } |
1649 | err = register_state (dfa, newstate, hash); |
1650 | if (BE (err != REG_NOERROR, 0)) |
1651 | { |
1652 | free_state (newstate); |
1653 | newstate = NULL; |
1654 | } |
1655 | return newstate; |
1656 | } |
1657 | |
1658 | /* Create the new state which is depend on the context CONTEXT. |
1659 | Return the new state if succeeded, otherwise return NULL. */ |
1660 | |
1661 | static re_dfastate_t * |
1662 | internal_function __attribute_warn_unused_result__ |
1663 | create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, |
1664 | unsigned int context, unsigned int hash) |
1665 | { |
1666 | int i, nctx_nodes = 0; |
1667 | reg_errcode_t err; |
1668 | re_dfastate_t *newstate; |
1669 | |
1670 | newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); |
1671 | if (BE (newstate == NULL, 0)) |
1672 | return NULL; |
1673 | err = re_node_set_init_copy (&newstate->nodes, nodes); |
1674 | if (BE (err != REG_NOERROR, 0)) |
1675 | { |
1676 | re_free (newstate); |
1677 | return NULL; |
1678 | } |
1679 | |
1680 | newstate->context = context; |
1681 | newstate->entrance_nodes = &newstate->nodes; |
1682 | |
1683 | for (i = 0 ; i < nodes->nelem ; i++) |
1684 | { |
1685 | re_token_t *node = dfa->nodes + nodes->elems[i]; |
1686 | re_token_type_t type = node->type; |
1687 | unsigned int constraint = node->constraint; |
1688 | |
1689 | if (type == CHARACTER && !constraint) |
1690 | continue; |
1691 | #ifdef RE_ENABLE_I18N |
1692 | newstate->accept_mb |= node->accept_mb; |
1693 | #endif /* RE_ENABLE_I18N */ |
1694 | |
1695 | /* If the state has the halt node, the state is a halt state. */ |
1696 | if (type == END_OF_RE) |
1697 | newstate->halt = 1; |
1698 | else if (type == OP_BACK_REF) |
1699 | newstate->has_backref = 1; |
1700 | |
1701 | if (constraint) |
1702 | { |
1703 | if (newstate->entrance_nodes == &newstate->nodes) |
1704 | { |
1705 | newstate->entrance_nodes = re_malloc (re_node_set, 1); |
1706 | if (BE (newstate->entrance_nodes == NULL, 0)) |
1707 | { |
1708 | free_state (newstate); |
1709 | return NULL; |
1710 | } |
1711 | if (re_node_set_init_copy (newstate->entrance_nodes, nodes) |
1712 | != REG_NOERROR) |
1713 | return NULL; |
1714 | nctx_nodes = 0; |
1715 | newstate->has_constraint = 1; |
1716 | } |
1717 | |
1718 | if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context)) |
1719 | { |
1720 | re_node_set_remove_at (&newstate->nodes, i - nctx_nodes); |
1721 | ++nctx_nodes; |
1722 | } |
1723 | } |
1724 | } |
1725 | err = register_state (dfa, newstate, hash); |
1726 | if (BE (err != REG_NOERROR, 0)) |
1727 | { |
1728 | free_state (newstate); |
1729 | newstate = NULL; |
1730 | } |
1731 | return newstate; |
1732 | } |
1733 | |