← Back to branch summary

~ubuntu-branches/ubuntu/trusty/grub2/trusty-updates

« back to all changes in this revision

Viewing changes to grub-core/gnulib/regex_internal.c

Tags: upstream-1.99~20101122
Import upstream version 1.99~20101122

Show diffs side-by-side

added added

removed removed

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