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