Obsolete option --no-sig-create-check.
[gnupg.git] / util / regex_internal.c
1 /* Extended regular expression matching and search library.
2    Copyright (C) 2002 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public License
17    along with the GNU C Library; if not, see <http://www.gnu.org/licenses/>. 
18 */
19
20 #include <assert.h>
21 #include <ctype.h>
22 #include <limits.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #if defined HAVE_WCHAR_H || defined _LIBC
28 # include <wchar.h>
29 #endif /* HAVE_WCHAR_H || _LIBC */
30 #if defined HAVE_WCTYPE_H || defined _LIBC
31 # include <wctype.h>
32 #endif /* HAVE_WCTYPE_H || _LIBC */
33
34 #ifdef _LIBC
35 # ifndef _RE_DEFINE_LOCALE_FUNCTIONS
36 #  define _RE_DEFINE_LOCALE_FUNCTIONS 1
37 #  include <locale/localeinfo.h>
38 #  include <locale/elem-hash.h>
39 #  include <locale/coll-lookup.h>
40 # endif
41 #endif
42
43 /* This is for other GNU distributions with internationalized messages.  */
44 #if HAVE_LIBINTL_H || defined _LIBC
45 # include <libintl.h>
46 # ifdef _LIBC
47 #  undef gettext
48 #  define gettext(msgid) \
49   INTUSE(__dcgettext) (_libc_intl_domainname_internal, msgid, LC_MESSAGES)
50 # endif
51 #else
52 # define gettext(msgid) (msgid)
53 #endif
54
55 #ifndef gettext_noop
56 /* This define is so xgettext can find the internationalizable
57    strings.  */
58 # define gettext_noop(String) String
59 #endif
60
61 #include "_regex.h" /* gnupg */
62 #include "regex_internal.h"
63
64 static void re_string_construct_common (const char *str, int len,
65                                         re_string_t *pstr,
66                                         RE_TRANSLATE_TYPE trans, int icase);
67 #ifdef RE_ENABLE_I18N
68 static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx);
69 #endif /* RE_ENABLE_I18N */
70 static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
71                                               const re_node_set *nodes,
72                                               unsigned int hash);
73 static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
74                                      unsigned int hash);
75 static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
76                                           const re_node_set *nodes,
77                                           unsigned int hash);
78 static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa,
79                                           const re_node_set *nodes,
80                                           unsigned int context,
81                                           unsigned int hash);
82 static unsigned int inline calc_state_hash (const re_node_set *nodes,
83                                             unsigned int context);
84 \f
85 /* Functions for string operation.  */
86
87 /* This function allocate the buffers.  It is necessary to call
88    re_string_reconstruct before using the object.  */
89
90 static reg_errcode_t
91 re_string_allocate (pstr, str, len, init_len, trans, icase)
92      re_string_t *pstr;
93      const char *str;
94      int len, init_len, icase;
95      RE_TRANSLATE_TYPE trans;
96 {
97   reg_errcode_t ret;
98   int init_buf_len = (len + 1 < init_len) ? len + 1: init_len;
99   re_string_construct_common (str, len, pstr, trans, icase);
100   pstr->stop = pstr->len;
101
102   ret = re_string_realloc_buffers (pstr, init_buf_len);
103   if (BE (ret != REG_NOERROR, 0))
104     return ret;
105
106   pstr->mbs_case = (MBS_CASE_ALLOCATED (pstr) ? pstr->mbs_case
107                     : (unsigned char *) str);
108   pstr->mbs = MBS_ALLOCATED (pstr) ? pstr->mbs : pstr->mbs_case;
109   pstr->valid_len = (MBS_CASE_ALLOCATED (pstr) || MBS_ALLOCATED (pstr)
110                      || MB_CUR_MAX > 1) ? pstr->valid_len : len;
111   return REG_NOERROR;
112 }
113
114 /* This function allocate the buffers, and initialize them.  */
115
116 static reg_errcode_t
117 re_string_construct (pstr, str, len, trans, icase)
118      re_string_t *pstr;
119      const char *str;
120      int len, icase;
121      RE_TRANSLATE_TYPE trans;
122 {
123   reg_errcode_t ret;
124   re_string_construct_common (str, len, pstr, trans, icase);
125   pstr->stop = pstr->len;
126   /* Set 0 so that this function can initialize whole buffers.  */
127   pstr->valid_len = 0;
128
129   if (len > 0)
130     {
131       ret = re_string_realloc_buffers (pstr, len + 1);
132       if (BE (ret != REG_NOERROR, 0))
133         return ret;
134     }
135   pstr->mbs_case = (MBS_CASE_ALLOCATED (pstr) ? pstr->mbs_case
136                     : (unsigned char *) str);
137   pstr->mbs = MBS_ALLOCATED (pstr) ? pstr->mbs : pstr->mbs_case;
138
139   if (icase)
140     {
141 #ifdef RE_ENABLE_I18N
142       if (MB_CUR_MAX > 1)
143         build_wcs_upper_buffer (pstr);
144       else
145 #endif /* RE_ENABLE_I18N  */
146         build_upper_buffer (pstr);
147     }
148   else
149     {
150 #ifdef RE_ENABLE_I18N
151       if (MB_CUR_MAX > 1)
152         build_wcs_buffer (pstr);
153       else
154 #endif /* RE_ENABLE_I18N  */
155         {
156           if (trans != NULL)
157             re_string_translate_buffer (pstr);
158           else
159             pstr->valid_len = len;
160         }
161     }
162
163   /* Initialized whole buffers, then valid_len == bufs_len.  */
164   pstr->valid_len = pstr->bufs_len;
165   return REG_NOERROR;
166 }
167
168 /* Helper functions for re_string_allocate, and re_string_construct.  */
169
170 static reg_errcode_t
171 re_string_realloc_buffers (pstr, new_buf_len)
172      re_string_t *pstr;
173      int new_buf_len;
174 {
175 #ifdef RE_ENABLE_I18N
176   if (MB_CUR_MAX > 1)
177     {
178       pstr->wcs = re_realloc (pstr->wcs, wint_t, new_buf_len);
179       if (BE (pstr->wcs == NULL, 0))
180         return REG_ESPACE;
181     }
182 #endif /* RE_ENABLE_I18N  */
183   if (MBS_ALLOCATED (pstr))
184     {
185       pstr->mbs = re_realloc (pstr->mbs, unsigned char, new_buf_len);
186       if (BE (pstr->mbs == NULL, 0))
187         return REG_ESPACE;
188     }
189   if (MBS_CASE_ALLOCATED (pstr))
190     {
191       pstr->mbs_case = re_realloc (pstr->mbs_case, unsigned char, new_buf_len);
192       if (BE (pstr->mbs_case == NULL, 0))
193         return REG_ESPACE;
194       if (!MBS_ALLOCATED (pstr))
195         pstr->mbs = pstr->mbs_case;
196     }
197   pstr->bufs_len = new_buf_len;
198   return REG_NOERROR;
199 }
200
201
202 static void
203 re_string_construct_common (str, len, pstr, trans, icase)
204      const char *str;
205      int len;
206      re_string_t *pstr;
207      RE_TRANSLATE_TYPE trans;
208      int icase;
209 {
210   memset (pstr, '\0', sizeof (re_string_t));
211   pstr->raw_mbs = (const unsigned char *) str;
212   pstr->len = len;
213   pstr->trans = trans;
214   pstr->icase = icase ? 1 : 0;
215 }
216
217 #ifdef RE_ENABLE_I18N
218
219 /* Build wide character buffer PSTR->WCS.
220    If the byte sequence of the string are:
221      <mb1>(0), <mb1>(1), <mb2>(0), <mb2>(1), <sb3>
222    Then wide character buffer will be:
223      <wc1>   , WEOF    , <wc2>   , WEOF    , <wc3>
224    We use WEOF for padding, they indicate that the position isn't
225    a first byte of a multibyte character.
226
227    Note that this function assumes PSTR->VALID_LEN elements are already
228    built and starts from PSTR->VALID_LEN.  */
229
230 static void
231 build_wcs_buffer (pstr)
232      re_string_t *pstr;
233 {
234   mbstate_t prev_st;
235   int byte_idx, end_idx, mbclen, remain_len;
236   /* Build the buffers from pstr->valid_len to either pstr->len or
237      pstr->bufs_len.  */
238   end_idx = (pstr->bufs_len > pstr->len)? pstr->len : pstr->bufs_len;
239   for (byte_idx = pstr->valid_len; byte_idx < end_idx;)
240     {
241       wchar_t wc;
242       remain_len = end_idx - byte_idx;
243       prev_st = pstr->cur_state;
244       mbclen = mbrtowc (&wc, ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
245                               + byte_idx), remain_len, &pstr->cur_state);
246       if (BE (mbclen == (size_t) -2, 0))
247         {
248           /* The buffer doesn't have enough space, finish to build.  */
249           pstr->cur_state = prev_st;
250           break;
251         }
252       else if (BE (mbclen == (size_t) -1 || mbclen == 0, 0))
253         {
254           /* We treat these cases as a singlebyte character.  */
255           mbclen = 1;
256           wc = (wchar_t) pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
257           pstr->cur_state = prev_st;
258         }
259
260       /* Apply the translateion if we need.  */
261       if (pstr->trans != NULL && mbclen == 1)
262         {
263           int ch = pstr->trans[pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]];
264           pstr->mbs_case[byte_idx] = ch;
265         }
266       /* Write wide character and padding.  */
267       pstr->wcs[byte_idx++] = wc;
268       /* Write paddings.  */
269       for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
270         pstr->wcs[byte_idx++] = WEOF;
271     }
272   pstr->valid_len = byte_idx;
273 }
274
275 /* Build wide character buffer PSTR->WCS like build_wcs_buffer,
276    but for REG_ICASE.  */
277
278 static void
279 build_wcs_upper_buffer (pstr)
280      re_string_t *pstr;
281 {
282   mbstate_t prev_st;
283   int byte_idx, end_idx, mbclen, remain_len;
284   /* Build the buffers from pstr->valid_len to either pstr->len or
285      pstr->bufs_len.  */
286   end_idx = (pstr->bufs_len > pstr->len)? pstr->len : pstr->bufs_len;
287   for (byte_idx = pstr->valid_len; byte_idx < end_idx;)
288     {
289       wchar_t wc;
290       remain_len = end_idx - byte_idx;
291       prev_st = pstr->cur_state;
292       mbclen = mbrtowc (&wc, ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx
293                               + byte_idx), remain_len, &pstr->cur_state);
294       if (BE (mbclen == (size_t) -2, 0))
295         {
296           /* The buffer doesn't have enough space, finish to build.  */
297           pstr->cur_state = prev_st;
298           break;
299         }
300       else if (mbclen == 1 || mbclen == (size_t) -1 || mbclen == 0)
301         {
302           /* In case of a singlebyte character.  */
303           int ch = pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx];
304           /* Apply the translateion if we need.  */
305           if (pstr->trans != NULL && mbclen == 1)
306             {
307               ch = pstr->trans[ch];
308               pstr->mbs_case[byte_idx] = ch;
309             }
310           pstr->wcs[byte_idx] = iswlower (wc) ? toupper (wc) : wc;
311           pstr->mbs[byte_idx++] = islower (ch) ? toupper (ch) : ch;
312           if (BE (mbclen == (size_t) -1, 0))
313             pstr->cur_state = prev_st;
314         }
315       else /* mbclen > 1 */
316         {
317           if (iswlower (wc))
318             wcrtomb ((char *) pstr->mbs + byte_idx, towupper (wc), &prev_st);
319           else
320             memcpy (pstr->mbs + byte_idx,
321                     pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx, mbclen);
322           pstr->wcs[byte_idx++] = iswlower (wc) ? toupper (wc) : wc;
323           /* Write paddings.  */
324           for (remain_len = byte_idx + mbclen - 1; byte_idx < remain_len ;)
325             pstr->wcs[byte_idx++] = WEOF;
326         }
327     }
328   pstr->valid_len = byte_idx;
329 }
330
331 /* Skip characters until the index becomes greater than NEW_RAW_IDX.
332    Return the index.  */
333
334 static int
335 re_string_skip_chars (pstr, new_raw_idx)
336      re_string_t *pstr;
337      int new_raw_idx;
338 {
339   mbstate_t prev_st;
340   int rawbuf_idx, mbclen;
341
342   /* Skip the characters which are not necessary to check.  */
343   for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_len;
344        rawbuf_idx < new_raw_idx;)
345     {
346       int remain_len = pstr->len - rawbuf_idx;
347       prev_st = pstr->cur_state;
348       mbclen = mbrlen ((const char *) pstr->raw_mbs + rawbuf_idx, remain_len,
349                        &pstr->cur_state);
350       if (BE (mbclen == (size_t) -2 || mbclen == (size_t) -1 || mbclen == 0, 0))
351         {
352           /* We treat these cases as a singlebyte character.  */
353           mbclen = 1;
354           pstr->cur_state = prev_st;
355         }
356       /* Then proceed the next character.  */
357       rawbuf_idx += mbclen;
358     }
359   return rawbuf_idx;
360 }
361 #endif /* RE_ENABLE_I18N  */
362
363 /* Build the buffer PSTR->MBS, and apply the translation if we need.  
364    This function is used in case of REG_ICASE.  */
365
366 static void
367 build_upper_buffer (pstr)
368      re_string_t *pstr;
369 {
370   int char_idx, end_idx;
371   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
372
373   for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx)
374     {
375       int ch = pstr->raw_mbs[pstr->raw_mbs_idx + char_idx];
376       if (pstr->trans != NULL)
377         {
378           ch =  pstr->trans[ch];
379           pstr->mbs_case[char_idx] = ch;
380         }
381       if (islower (ch))
382         pstr->mbs[char_idx] = toupper (ch);
383       else
384         pstr->mbs[char_idx] = ch;
385     }
386   pstr->valid_len = char_idx;
387 }
388
389 /* Apply TRANS to the buffer in PSTR.  */
390
391 static void
392 re_string_translate_buffer (pstr)
393      re_string_t *pstr;
394 {
395   int buf_idx, end_idx;
396   end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
397
398   for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx)
399     {
400       int ch = pstr->raw_mbs[pstr->raw_mbs_idx + buf_idx];
401       pstr->mbs_case[buf_idx] = pstr->trans[ch];
402     }
403
404   pstr->valid_len = buf_idx;
405 }
406
407 /* This function re-construct the buffers.
408    Concretely, convert to wide character in case of MB_CUR_MAX > 1,
409    convert to upper case in case of REG_ICASE, apply translation.  */
410
411 static reg_errcode_t
412 re_string_reconstruct (pstr, idx, eflags, newline)
413      re_string_t *pstr;
414      int idx, eflags, newline;
415 {
416   int offset = idx - pstr->raw_mbs_idx;
417   if (offset < 0)
418     {
419       /* Reset buffer.  */
420 #ifdef RE_ENABLE_I18N
421       if (MB_CUR_MAX > 1)
422         memset (&pstr->cur_state, '\0', sizeof (mbstate_t));
423 #endif /* RE_ENABLE_I18N */
424       pstr->len += pstr->raw_mbs_idx;
425       pstr->stop += pstr->raw_mbs_idx;
426       pstr->valid_len = pstr->raw_mbs_idx = 0;
427       pstr->tip_context = ((eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
428                            : CONTEXT_NEWLINE | CONTEXT_BEGBUF);
429       if (!MBS_CASE_ALLOCATED (pstr))
430         pstr->mbs_case = (unsigned char *) pstr->raw_mbs;
431       if (!MBS_ALLOCATED (pstr) && !MBS_CASE_ALLOCATED (pstr))
432         pstr->mbs = (unsigned char *) pstr->raw_mbs;
433       offset = idx;
434     }
435
436   if (offset != 0)
437     {
438       pstr->tip_context = re_string_context_at (pstr, offset - 1, eflags,
439                                                 newline);
440       /* Are the characters which are already checked remain?  */
441       if (offset < pstr->valid_len)
442         {
443           /* Yes, move them to the front of the buffer.  */
444 #ifdef RE_ENABLE_I18N
445           if (MB_CUR_MAX > 1)
446             memmove (pstr->wcs, pstr->wcs + offset,
447                      (pstr->valid_len - offset) * sizeof (wint_t));
448 #endif /* RE_ENABLE_I18N */
449           if (MBS_ALLOCATED (pstr))
450             memmove (pstr->mbs, pstr->mbs + offset,
451                      pstr->valid_len - offset);
452           if (MBS_CASE_ALLOCATED (pstr))
453             memmove (pstr->mbs_case, pstr->mbs_case + offset,
454                      pstr->valid_len - offset);
455           pstr->valid_len -= offset;
456 #if DEBUG
457           assert (pstr->valid_len > 0);
458 #endif
459         }
460       else
461         {
462           /* No, skip all characters until IDX.  */
463           pstr->valid_len = 0;
464 #ifdef RE_ENABLE_I18N
465           if (MB_CUR_MAX > 1)
466             {
467               int wcs_idx;
468               pstr->valid_len = re_string_skip_chars (pstr, idx) - idx;
469               for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx)
470                 pstr->wcs[wcs_idx] = WEOF;
471             }
472 #endif /* RE_ENABLE_I18N */
473         }
474       if (!MBS_CASE_ALLOCATED (pstr))
475         {
476           pstr->mbs_case += offset; 
477           /* In case of !MBS_ALLOCATED && !MBS_CASE_ALLOCATED.  */
478           if (!MBS_ALLOCATED (pstr))
479             pstr->mbs += offset; 
480         }
481     }
482   pstr->raw_mbs_idx = idx;
483   pstr->len -= offset;
484   pstr->stop -= offset;
485
486   /* Then build the buffers.  */
487 #ifdef RE_ENABLE_I18N
488   if (MB_CUR_MAX > 1)
489     {
490       if (pstr->icase)
491         build_wcs_upper_buffer (pstr);
492       else
493         build_wcs_buffer (pstr);
494     }
495   else
496 #endif /* RE_ENABLE_I18N */
497     {
498       if (pstr->icase)
499         build_upper_buffer (pstr);
500       else if (pstr->trans != NULL)
501         re_string_translate_buffer (pstr);
502     }
503   pstr->cur_idx = 0;
504
505   return REG_NOERROR;
506 }
507
508 static void
509 re_string_destruct (pstr)
510      re_string_t *pstr;
511 {
512 #ifdef RE_ENABLE_I18N
513   re_free (pstr->wcs);
514 #endif /* RE_ENABLE_I18N  */
515   if (MBS_ALLOCATED (pstr))
516     re_free (pstr->mbs);
517   if (MBS_CASE_ALLOCATED (pstr))
518     re_free (pstr->mbs_case);
519 }
520
521 /* Return the context at IDX in INPUT.  */
522
523 static unsigned int
524 re_string_context_at (input, idx, eflags, newline_anchor)
525      const re_string_t *input;
526      int idx, eflags, newline_anchor;
527 {
528   int c;
529   if (idx < 0 || idx == input->len)
530     {
531       if (idx < 0)
532         /* In this case, we use the value stored in input->tip_context,
533            since we can't know the character in input->mbs[-1] here.  */
534         return input->tip_context;
535       else /* (idx == input->len) */
536         return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
537                 : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
538     }
539   c = re_string_byte_at (input, idx);
540   if (IS_WORD_CHAR (c))
541     return CONTEXT_WORD;
542   return (newline_anchor && IS_NEWLINE (c)) ? CONTEXT_NEWLINE : 0;
543 }
544 \f
545 /* Functions for set operation.  */
546
547 static reg_errcode_t
548 re_node_set_alloc (set, size)
549      re_node_set *set;
550      int size;
551 {
552   set->alloc = size;
553   set->nelem = 0;
554   set->elems = re_malloc (int, size);
555   if (BE (set->elems == NULL, 0))
556     return REG_ESPACE;
557   return REG_NOERROR;
558 }
559
560 static reg_errcode_t
561 re_node_set_init_1 (set, elem)
562      re_node_set *set;
563      int elem;
564 {
565   set->alloc = 1;
566   set->nelem = 1;
567   set->elems = re_malloc (int, 1);
568   if (BE (set->elems == NULL, 0))
569     return REG_ESPACE;
570   set->elems[0] = elem;
571   return REG_NOERROR;
572 }
573
574 static reg_errcode_t
575 re_node_set_init_2 (set, elem1, elem2)
576      re_node_set *set;
577      int elem1, elem2;
578 {
579   set->alloc = 2;
580   set->elems = re_malloc (int, 2);
581   if (BE (set->elems == NULL, 0))
582     return REG_ESPACE;
583   if (elem1 == elem2)
584     {
585       set->nelem = 1;
586       set->elems[0] = elem1;
587     }
588   else
589     {
590       set->nelem = 2;
591       if (elem1 < elem2)
592         {
593           set->elems[0] = elem1;
594           set->elems[1] = elem2;
595         }
596       else
597         {
598           set->elems[0] = elem2;
599           set->elems[1] = elem1;
600         }
601     }
602   return REG_NOERROR;
603 }
604
605 static reg_errcode_t
606 re_node_set_init_copy (dest, src)
607      re_node_set *dest;
608      const re_node_set *src;
609 {
610   dest->nelem = src->nelem;
611   if (src->nelem > 0)
612     {
613       dest->alloc = dest->nelem;
614       dest->elems = re_malloc (int, dest->alloc);
615       if (BE (dest->elems == NULL, 0))
616         return REG_ESPACE;
617       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
618     }
619   else
620     re_node_set_init_empty (dest);
621   return REG_NOERROR;
622 }
623
624 /* Calculate the intersection of the sets SRC1 and SRC2. And merge it to
625    DEST. Return value indicate the error code or REG_NOERROR if succeeded.
626    Note: We assume dest->elems is NULL, when dest->alloc is 0.  */
627
628 static reg_errcode_t
629 re_node_set_add_intersect (dest, src1, src2)
630      re_node_set *dest;
631      const re_node_set *src1, *src2;
632 {
633   int i1, i2, id;
634   if (src1->nelem > 0 && src2->nelem > 0)
635     {
636       if (src1->nelem + src2->nelem + dest->nelem > dest->alloc)
637         {
638           dest->alloc = src1->nelem + src2->nelem + dest->nelem;
639           dest->elems = re_realloc (dest->elems, int, dest->alloc);
640           if (BE (dest->elems == NULL, 0))
641             return REG_ESPACE;
642         }
643     }
644   else
645     return REG_NOERROR;
646
647   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
648     {
649       if (src1->elems[i1] > src2->elems[i2])
650         {
651           ++i2;
652           continue;
653         }
654       if (src1->elems[i1] == src2->elems[i2])
655         {
656           while (id < dest->nelem && dest->elems[id] < src2->elems[i2])
657             ++id;
658           if (id < dest->nelem && dest->elems[id] == src2->elems[i2])
659             ++id;
660           else
661             {
662               memmove (dest->elems + id + 1, dest->elems + id,
663                        sizeof (int) * (dest->nelem - id));
664               dest->elems[id++] = src2->elems[i2++];
665               ++dest->nelem;
666             }
667         }
668       ++i1;
669     }
670   return REG_NOERROR;
671 }
672
673 /* Calculate the union set of the sets SRC1 and SRC2. And store it to
674    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
675
676 static reg_errcode_t
677 re_node_set_init_union (dest, src1, src2)
678      re_node_set *dest;
679      const re_node_set *src1, *src2;
680 {
681   int i1, i2, id;
682   if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0)
683     {
684       dest->alloc = src1->nelem + src2->nelem;
685       dest->elems = re_malloc (int, dest->alloc);
686       if (BE (dest->elems == NULL, 0))
687         return REG_ESPACE;
688     }
689   else
690     {
691       if (src1 != NULL && src1->nelem > 0)
692         return re_node_set_init_copy (dest, src1);
693       else if (src2 != NULL && src2->nelem > 0)
694         return re_node_set_init_copy (dest, src2);
695       else
696         re_node_set_init_empty (dest);
697       return REG_NOERROR;
698     }
699   for (i1 = i2 = id = 0 ; i1 < src1->nelem && i2 < src2->nelem ;)
700     {
701       if (src1->elems[i1] > src2->elems[i2])
702         {
703           dest->elems[id++] = src2->elems[i2++];
704           continue;
705         }
706       if (src1->elems[i1] == src2->elems[i2])
707         ++i2;
708       dest->elems[id++] = src1->elems[i1++];
709     }
710   if (i1 < src1->nelem)
711     {
712       memcpy (dest->elems + id, src1->elems + i1,
713              (src1->nelem - i1) * sizeof (int));
714       id += src1->nelem - i1;
715     }
716   else if (i2 < src2->nelem)
717     {
718       memcpy (dest->elems + id, src2->elems + i2,
719              (src2->nelem - i2) * sizeof (int));
720       id += src2->nelem - i2;
721     }
722   dest->nelem = id;
723   return REG_NOERROR;
724 }
725
726 /* Calculate the union set of the sets DEST and SRC. And store it to
727    DEST. Return value indicate the error code or REG_NOERROR if succeeded.  */
728
729 static reg_errcode_t
730 re_node_set_merge (dest, src)
731      re_node_set *dest;
732      const re_node_set *src;
733 {
734   int si, di;
735   if (src == NULL || src->nelem == 0)
736     return REG_NOERROR;
737   if (dest->alloc < src->nelem + dest->nelem)
738     {
739       dest->alloc = 2 * (src->nelem + dest->alloc);
740       dest->elems = re_realloc (dest->elems, int, dest->alloc);
741       if (BE (dest->elems == NULL, 0))
742         return REG_ESPACE;
743     }
744
745   for (si = 0, di = 0 ; si < src->nelem && di < dest->nelem ;)
746     {
747       int cp_from, ncp, mid, right, src_elem = src->elems[si];
748       /* Binary search the spot we will add the new element.  */
749       right = dest->nelem;
750       while (di < right)
751         {
752           mid = (di + right) / 2;
753           if (dest->elems[mid] < src_elem)
754             di = mid + 1;
755           else
756             right = mid;
757         }
758       if (di >= dest->nelem)
759         break;
760
761       if (dest->elems[di] == src_elem)
762         {
763           /* Skip since, DEST already has the element.  */
764           ++di;
765           ++si;
766           continue;
767         }
768
769       /* Skip the src elements which are less than dest->elems[di].  */
770       cp_from = si;
771       while (si < src->nelem && src->elems[si] < dest->elems[di])
772         ++si;
773       /* Copy these src elements.  */
774       ncp = si - cp_from;
775       memmove (dest->elems + di + ncp, dest->elems + di,
776                sizeof (int) * (dest->nelem - di));
777       memcpy (dest->elems + di, src->elems + cp_from,
778               sizeof (int) * ncp);
779       /* Update counters.  */
780       di += ncp;
781       dest->nelem += ncp;
782     }
783
784   /* Copy remaining src elements.  */
785   if (si < src->nelem)
786     {
787       memcpy (dest->elems + di, src->elems + si,
788               sizeof (int) * (src->nelem - si));
789       dest->nelem += src->nelem - si;
790     }
791   return REG_NOERROR;
792 }
793
794 /* Insert the new element ELEM to the re_node_set* SET.
795    return 0 if SET already has ELEM,
796    return -1 if an error is occured, return 1 otherwise.  */
797
798 static int
799 re_node_set_insert (set, elem)
800      re_node_set *set;
801      int elem;
802 {
803   int idx, right, mid;
804   /* In case of the set is empty.  */
805   if (set->elems == NULL || set->alloc == 0)
806     {
807       if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1))
808         return 1;
809       else
810         return -1;
811     }
812
813   /* Binary search the spot we will add the new element.  */
814   idx = 0;
815   right = set->nelem;
816   while (idx < right)
817     {
818       mid = (idx + right) / 2;
819       if (set->elems[mid] < elem)
820         idx = mid + 1;
821       else
822         right = mid;
823     }
824
825   /* Realloc if we need.  */
826   if (set->alloc < set->nelem + 1)
827     {
828       int *new_array;
829       set->alloc = set->alloc * 2;
830       new_array = re_malloc (int, set->alloc);
831       if (BE (new_array == NULL, 0))
832         return -1;
833       /* Copy the elements they are followed by the new element.  */
834       if (idx > 0)
835         memcpy (new_array, set->elems, sizeof (int) * (idx));
836       /* Copy the elements which follows the new element.  */
837       if (set->nelem - idx > 0)
838         memcpy (new_array + idx + 1, set->elems + idx,
839                 sizeof (int) * (set->nelem - idx));
840       re_free (set->elems);
841       set->elems = new_array;
842     }
843   else
844     {
845       /* Move the elements which follows the new element.  */
846       if (set->nelem - idx > 0)
847         memmove (set->elems + idx + 1, set->elems + idx,
848                  sizeof (int) * (set->nelem - idx));
849     }
850   /* Insert the new element.  */
851   set->elems[idx] = elem;
852   ++set->nelem;
853   return 1;
854 }
855
856 /* Compare two node sets SET1 and SET2.
857    return 1 if SET1 and SET2 are equivalent, retrun 0 otherwise.  */
858
859 static int
860 re_node_set_compare (set1, set2)
861      const re_node_set *set1, *set2;
862 {
863   int i;
864   if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
865     return 0;
866   for (i = 0 ; i < set1->nelem ; i++)
867     if (set1->elems[i] != set2->elems[i])
868       return 0;
869   return 1;
870 }
871
872 /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */
873
874 static int
875 re_node_set_contains (set, elem)
876      const re_node_set *set;
877      int elem;
878 {
879   int idx, right, mid;
880   if (set->nelem <= 0)
881     return 0;
882
883   /* Binary search the element.  */
884   idx = 0;
885   right = set->nelem - 1;
886   while (idx < right)
887     {
888       mid = (idx + right) / 2;
889       if (set->elems[mid] < elem)
890         idx = mid + 1;
891       else
892         right = mid;
893     }
894   return set->elems[idx] == elem ? idx + 1 : 0;
895 }
896
897 static void
898 re_node_set_remove_at (set, idx)
899      re_node_set *set;
900      int idx;
901 {
902   if (idx < 0 || idx >= set->nelem)
903     return;
904   if (idx < set->nelem - 1)
905     memmove (set->elems + idx, set->elems + idx + 1,
906              sizeof (int) * (set->nelem - idx - 1));
907   --set->nelem;
908 }
909 \f
910
911 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
912    Or return -1, if an error will be occured.  */
913
914 static int
915 re_dfa_add_node (dfa, token, mode)
916      re_dfa_t *dfa;
917      re_token_t token;
918      int mode;
919 {
920   if (dfa->nodes_len >= dfa->nodes_alloc)
921     {
922       re_token_t *new_array;
923       dfa->nodes_alloc *= 2;
924       new_array = re_realloc (dfa->nodes, re_token_t, dfa->nodes_alloc);
925       if (BE (new_array == NULL, 0))
926         return -1;
927       else
928         dfa->nodes = new_array;
929       if (mode)
930         {
931           int *new_firsts, *new_nexts;
932           re_node_set *new_edests, *new_eclosures, *new_inveclosures;
933
934           new_firsts = re_realloc (dfa->firsts, int, dfa->nodes_alloc);
935           new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
936           new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
937           new_eclosures = re_realloc (dfa->eclosures, re_node_set,
938                                       dfa->nodes_alloc);
939           new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
940                                          dfa->nodes_alloc);
941           if (BE (new_firsts == NULL || new_nexts == NULL || new_edests == NULL
942                   || new_eclosures == NULL || new_inveclosures == NULL, 0))
943             return -1;
944           dfa->firsts = new_firsts;
945           dfa->nexts = new_nexts;
946           dfa->edests = new_edests;
947           dfa->eclosures = new_eclosures;
948           dfa->inveclosures = new_inveclosures;
949         }
950     }
951   dfa->nodes[dfa->nodes_len] = token;
952   dfa->nodes[dfa->nodes_len].duplicated = 0;
953   return dfa->nodes_len++;
954 }
955
956 static unsigned int inline
957 calc_state_hash (nodes, context)
958      const re_node_set *nodes;
959      unsigned int context;
960 {
961   unsigned int hash = nodes->nelem + context;
962   int i;
963   for (i = 0 ; i < nodes->nelem ; i++)
964     hash += nodes->elems[i];
965   return hash;
966 }
967
968 /* Search for the state whose node_set is equivalent to NODES.
969    Return the pointer to the state, if we found it in the DFA.
970    Otherwise create the new one and return it.  In case of an error
971    return NULL and set the error code in ERR.
972    Note: - We assume NULL as the invalid state, then it is possible that
973            return value is NULL and ERR is REG_NOERROR.
974          - We never return non-NULL value in case of any errors, it is for
975            optimization.  */
976
977 static re_dfastate_t*
978 re_acquire_state (err, dfa, nodes)
979      reg_errcode_t *err;
980      re_dfa_t *dfa;
981      const re_node_set *nodes;
982 {
983   unsigned int hash;
984   re_dfastate_t *new_state;
985   struct re_state_table_entry *spot;
986   int i;
987   if (BE (nodes->nelem == 0, 0))
988     {
989       *err = REG_NOERROR;
990       return NULL;
991     }
992   hash = calc_state_hash (nodes, 0);
993   spot = dfa->state_table + (hash & dfa->state_hash_mask);
994
995   for (i = 0 ; i < spot->num ; i++)
996     {
997       re_dfastate_t *state = spot->array[i];
998       if (hash != state->hash)
999         continue;
1000       if (re_node_set_compare (&state->nodes, nodes))
1001         return state;
1002     }
1003
1004   /* There are no appropriate state in the dfa, create the new one.  */
1005   new_state = create_ci_newstate (dfa, nodes, hash);
1006   if (BE (new_state != NULL, 1))
1007     return new_state;
1008   else
1009     {
1010       *err = REG_ESPACE;
1011       return NULL;
1012     }
1013 }
1014
1015 /* Search for the state whose node_set is equivalent to NODES and
1016    whose context is equivalent to CONTEXT.
1017    Return the pointer to the state, if we found it in the DFA.
1018    Otherwise create the new one and return it.  In case of an error
1019    return NULL and set the error code in ERR.
1020    Note: - We assume NULL as the invalid state, then it is possible that
1021            return value is NULL and ERR is REG_NOERROR.
1022          - We never return non-NULL value in case of any errors, it is for
1023            optimization.  */
1024
1025 static re_dfastate_t*
1026 re_acquire_state_context (err, dfa, nodes, context)
1027      reg_errcode_t *err;
1028      re_dfa_t *dfa;
1029      const re_node_set *nodes;
1030      unsigned int context;
1031 {
1032   unsigned int hash;
1033   re_dfastate_t *new_state;
1034   struct re_state_table_entry *spot;
1035   int i;
1036   if (nodes->nelem == 0)
1037     {
1038       *err = REG_NOERROR;
1039       return NULL;
1040     }
1041   hash = calc_state_hash (nodes, context);
1042   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1043
1044   for (i = 0 ; i < spot->num ; i++)
1045     {
1046       re_dfastate_t *state = spot->array[i];
1047       if (hash != state->hash)
1048         continue;
1049       if (re_node_set_compare (state->entrance_nodes, nodes)
1050           && state->context == context)
1051         return state;
1052     }
1053   /* There are no appropriate state in `dfa', create the new one.  */
1054   new_state = create_cd_newstate (dfa, nodes, context, hash);
1055   if (BE (new_state != NULL, 1))
1056     return new_state;
1057   else
1058     {
1059       *err = REG_ESPACE;
1060       return NULL;
1061     }
1062 }
1063
1064 /* Allocate memory for DFA state and initialize common properties.
1065    Return the new state if succeeded, otherwise return NULL.  */
1066
1067 static re_dfastate_t *
1068 create_newstate_common (dfa, nodes, hash)
1069      re_dfa_t *dfa;
1070      const re_node_set *nodes;
1071      unsigned int hash;
1072 {
1073   re_dfastate_t *newstate;
1074   newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1075   if (BE (newstate == NULL, 0))
1076     return NULL;
1077   re_node_set_init_copy (&newstate->nodes, nodes);
1078   newstate->trtable = NULL;
1079   newstate->trtable_search = NULL;
1080   newstate->hash = hash;
1081   return newstate;
1082 }
1083
1084 /* Store the new state NEWSTATE whose hash value is HASH in appropriate
1085    position.  Return value indicate the error code if failed.  */
1086
1087 static reg_errcode_t
1088 register_state (dfa, newstate, hash)
1089      re_dfa_t *dfa;
1090      re_dfastate_t *newstate;
1091      unsigned int hash;
1092 {
1093   struct re_state_table_entry *spot;
1094   spot = dfa->state_table + (hash & dfa->state_hash_mask);
1095
1096   if (spot->alloc <= spot->num)
1097     {
1098       spot->alloc = 2 * spot->num + 2;
1099       spot->array = re_realloc (spot->array, re_dfastate_t *, spot->alloc);
1100       if (BE (spot->array == NULL, 0))
1101         return REG_ESPACE;
1102     }
1103   spot->array[spot->num++] = newstate;
1104   return REG_NOERROR;
1105 }
1106
1107 /* Create the new state which is independ of contexts.
1108    Return the new state if succeeded, otherwise return NULL.  */
1109
1110 static re_dfastate_t *
1111 create_ci_newstate (dfa, nodes, hash)
1112      re_dfa_t *dfa;
1113      const re_node_set *nodes;
1114      unsigned int hash;
1115 {
1116   int i;
1117   reg_errcode_t err;
1118   re_dfastate_t *newstate;
1119   newstate = create_newstate_common (dfa, nodes, hash);
1120   if (BE (newstate == NULL, 0))
1121     return NULL;
1122   newstate->entrance_nodes = &newstate->nodes;
1123
1124   for (i = 0 ; i < nodes->nelem ; i++)
1125     {
1126       re_token_t *node = dfa->nodes + nodes->elems[i];
1127       re_token_type_t type = node->type;
1128       if (type == CHARACTER)
1129         continue;
1130
1131       /* If the state has the halt node, the state is a halt state.  */
1132       else if (type == END_OF_RE)
1133         newstate->halt = 1;
1134 #ifdef RE_ENABLE_I18N
1135       else if (type == COMPLEX_BRACKET
1136                || (type == OP_PERIOD && MB_CUR_MAX > 1))
1137         newstate->accept_mb = 1;
1138 #endif /* RE_ENABLE_I18N */
1139       else if (type == OP_BACK_REF)
1140         newstate->has_backref = 1;
1141       else if (type == ANCHOR || OP_CONTEXT_NODE)
1142         {
1143           newstate->has_constraint = 1;
1144           if (type == OP_CONTEXT_NODE
1145               && dfa->nodes[node->opr.ctx_info->entity].type == END_OF_RE)
1146             newstate->halt = 1;
1147         }
1148     }
1149   err = register_state (dfa, newstate, hash);
1150   return (err != REG_NOERROR) ? NULL : newstate;
1151 }
1152
1153 /* Create the new state which is depend on the context CONTEXT.
1154    Return the new state if succeeded, otherwise return NULL.  */
1155
1156 static re_dfastate_t *
1157 create_cd_newstate (dfa, nodes, context, hash)
1158      re_dfa_t *dfa;
1159      const re_node_set *nodes;
1160      unsigned int context, hash;
1161 {
1162   int i, nctx_nodes = 0;
1163   reg_errcode_t err;
1164   re_dfastate_t *newstate;
1165
1166   newstate = create_newstate_common (dfa, nodes, hash);
1167   if (BE (newstate == NULL, 0))
1168     return NULL;
1169   newstate->context = context;
1170   newstate->entrance_nodes = &newstate->nodes;
1171
1172   for (i = 0 ; i < nodes->nelem ; i++)
1173     {
1174       unsigned int constraint = 0;
1175       re_token_t *node = dfa->nodes + nodes->elems[i];
1176       re_token_type_t type = node->type;
1177       if (type == CHARACTER)
1178         continue;
1179
1180       /* If the state has the halt node, the state is a halt state.  */
1181       else if (type == END_OF_RE)
1182         newstate->halt = 1;
1183 #ifdef RE_ENABLE_I18N
1184       else if (type == COMPLEX_BRACKET
1185                || (type == OP_PERIOD && MB_CUR_MAX > 1))
1186         newstate->accept_mb = 1;
1187 #endif /* RE_ENABLE_I18N */
1188       else if (type == OP_BACK_REF)
1189         newstate->has_backref = 1;
1190       else if (type == ANCHOR)
1191         constraint = node->opr.ctx_type;
1192       else if (type == OP_CONTEXT_NODE)
1193         {
1194           re_token_type_t ctype = dfa->nodes[node->opr.ctx_info->entity].type;
1195           constraint = node->constraint;
1196           if (ctype == END_OF_RE)
1197             newstate->halt = 1;
1198           else if (ctype == OP_BACK_REF)
1199             newstate->has_backref = 1;
1200 #ifdef RE_ENABLE_I18N
1201           else if (ctype == COMPLEX_BRACKET
1202                    || (type == OP_PERIOD && MB_CUR_MAX > 1))
1203             newstate->accept_mb = 1;
1204 #endif /* RE_ENABLE_I18N */
1205         }
1206
1207       if (constraint)
1208         {
1209           if (newstate->entrance_nodes == &newstate->nodes)
1210             {
1211               newstate->entrance_nodes = re_malloc (re_node_set, 1);
1212               if (BE (newstate->entrance_nodes == NULL, 0))
1213                 return NULL;
1214               re_node_set_init_copy (newstate->entrance_nodes, nodes);
1215               nctx_nodes = 0;
1216               newstate->has_constraint = 1;
1217             }
1218
1219           if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
1220             {
1221               re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
1222               ++nctx_nodes;
1223             }
1224         }
1225     }
1226   err = register_state (dfa, newstate, hash);
1227   return (err != REG_NOERROR) ? NULL : newstate;
1228 }