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