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