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