Changeset 3059 for trunk/libc/src/glibc/posix/regcomp.c

Timestamp:

Apr 8, 2007, 8:58:56 PM (18 years ago)

Author:

bird

Message:

Merged in regex from glibc 2.5. Fixes #147.

File:

• trunk/libc/src/glibc/posix/regcomp.c (modified) (81 diffs)

trunk/libc/src/glibc/posix/regcomp.c

@@ -1 +1 @@
 /* Extended regular expression matching and search library.
-   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+   Copyright (C) 2002,2003,2004,2005,2006 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
    Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
@@ -20 +20 @@
 
 static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
-                                          int length, reg_syntax_t syntax);
+                                          size_t length, reg_syntax_t syntax);
 static void re_compile_fastmap_iter (regex_t *bufp,
                                      const re_dfastate_t *init_state,
                                      char *fastmap);
-static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);
-static void init_word_char (re_dfa_t *dfa);
+static reg_errcode_t init_dfa (re_dfa_t *dfa, size_t pat_len);
 #ifdef RE_ENABLE_I18N
 static void free_charset (re_charset_t *cset);
@@ -35 +34 @@
 #endif
 static reg_errcode_t analyze (regex_t *preg);
-static reg_errcode_t create_initial_state (re_dfa_t *dfa);
 static reg_errcode_t preorder (bin_tree_t *root,
                                reg_errcode_t (fn (void *, bin_tree_t *)),
@@ -49 +47 @@
 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
-static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
-                                             int top_clone_node, int root_node,
-                                             unsigned int constraint);
-static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
-                                     unsigned int constraint);
-static int search_duplicated_node (re_dfa_t *dfa, int org_node,
+static int duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint);
+static int search_duplicated_node (const re_dfa_t *dfa, int org_node,
                                    unsigned int constraint);
 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
@@ -62 +56 @@
 static int fetch_number (re_string_t *input, re_token_t *token,
                          reg_syntax_t syntax);
-static void fetch_token (re_token_t *result, re_string_t *input,
-                         reg_syntax_t syntax);
 static int peek_token (re_token_t *token, re_string_t *input,
-                        reg_syntax_t syntax);
-static int peek_token_bracket (re_token_t *token, re_string_t *input,
-                               reg_syntax_t syntax);
+                        reg_syntax_t syntax) internal_function;
 static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
                           reg_syntax_t syntax, reg_errcode_t *err);
@@ -97 +87 @@
                                           re_string_t *regexp,
                                           re_token_t *token);
-#ifndef _LIBC
-# ifdef RE_ENABLE_I18N
-static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
-                                      re_charset_t *mbcset, int *range_alloc,
-                                      bracket_elem_t *start_elem,
-                                      bracket_elem_t *end_elem);
-static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
-                                             re_charset_t *mbcset,
-                                             int *coll_sym_alloc,
-                                             const unsigned char *name);
-# else /* not RE_ENABLE_I18N */
-static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,
-                                      bracket_elem_t *start_elem,
-                                      bracket_elem_t *end_elem);
-static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,
-                                             const unsigned char *name);
-# endif /* not RE_ENABLE_I18N */
-#endif /* not _LIBC */
-#ifdef RE_ENABLE_I18N
-static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
+#ifdef RE_ENABLE_I18N
+static reg_errcode_t build_equiv_class (bitset_t sbcset,
                                         re_charset_t *mbcset,
                                         int *equiv_class_alloc,
                                         const unsigned char *name);
-static reg_errcode_t build_charclass (unsigned RE_TRANSLATE_TYPE trans,
-                                      re_bitset_ptr_t sbcset,
+static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
+                                      bitset_t sbcset,
                                       re_charset_t *mbcset,
                                       int *char_class_alloc,
@@ -127 +99 @@
                                       reg_syntax_t syntax);
 #else  /* not RE_ENABLE_I18N */
-static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,
+static reg_errcode_t build_equiv_class (bitset_t sbcset,
                                         const unsigned char *name);
-static reg_errcode_t build_charclass (unsigned RE_TRANSLATE_TYPE trans,
-                                      re_bitset_ptr_t sbcset,
+static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
+                                      bitset_t sbcset,
                                       const unsigned char *class_name,
                                       reg_syntax_t syntax);
 #endif /* not RE_ENABLE_I18N */
 static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
-                                       unsigned RE_TRANSLATE_TYPE trans,
+                                       RE_TRANSLATE_TYPE trans,
                                        const unsigned char *class_name,
                                        const unsigned char *extra,
@@ -330 +302 @@
 
 static void
-re_compile_fastmap_iter (bufp, init_state, fastmap)
-     regex_t *bufp;
-     const re_dfastate_t *init_state;
-     char *fastmap;
+re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
+                         char *fastmap)
 {
   re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
@@ -359 +329 @@
                      && dfa->nodes[node].mb_partial)
                 *p++ = dfa->nodes[node].opr.c;
-              memset (&state, 0, sizeof (state));
+              memset (&state, '\0', sizeof (state));
               if (mbrtowc (&wc, (const char *) buf, p - buf,
                            &state) == p - buf
@@ -370 +340 @@
       else if (type == SIMPLE_BRACKET)
         {
-          int i, j, ch;
-          for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
-            for (j = 0; j < UINT_BITS; ++j, ++ch)
-              if (dfa->nodes[node].opr.sbcset[i] & (1 << j))
-                re_set_fastmap (fastmap, icase, ch);
+          int i, ch;
+          for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
+            {
+              int j;
+              bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
+              for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
+                if (w & ((bitset_word_t) 1 << j))
+                  re_set_fastmap (fastmap, icase, ch);
+            }
         }
 #ifdef RE_ENABLE_I18N
@@ -393 +367 @@
                           'b' since 'b' is the only collation element
                           which starts from 'b'.  */
-                  int j, ch;
                   const int32_t *table = (const int32_t *)
                     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
-                  for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
-                    for (j = 0; j < UINT_BITS; ++j, ++ch)
-                      if (table[ch] < 0)
-                        re_set_fastmap (fastmap, icase, ch);
+                  for (i = 0; i < SBC_MAX; ++i)
+                    if (table[i] < 0)
+                      re_set_fastmap (fastmap, icase, i);
                 }
 # else
@@ -419 +391 @@
                   if (__wcrtomb (buf, towlower (cset->mbchars[i]), &state)
                       != (size_t) -1)
-                  re_set_fastmap (fastmap, 0, *(unsigned char *) buf);
+                    re_set_fastmap (fastmap, 0, *(unsigned char *) buf);
                 }
             }
@@ -540 +512 @@
 _STD(regerror) (errcode, preg, errbuf, errbuf_size)
     int errcode;
-    const regex_t *preg;
-    char *errbuf;
+    const regex_t *__restrict preg;
+    char *__restrict errbuf;
     size_t errbuf_size;
 {
@@ -587 +559 @@
    it the same all the time.  UTF-8 is the preferred encoding so this is
    a worthwhile optimization.  */
-static const bitset utf8_sb_map =
+static const bitset_t utf8_sb_map =
 {
   /* Set the first 128 bits.  */
-# if UINT_MAX == 0xffffffff
-  0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
-# else
-#  error "Add case for new unsigned int size"
-# endif
+  [0 ... 0x80 / BITSET_WORD_BITS - 1] = BITSET_WORD_MAX
 };
 #endif
@@ -745 +713 @@
 
 static reg_errcode_t
-re_compile_internal (preg, pattern, length, syntax)
-     regex_t *preg;
-     const char * pattern;
-     int length;
-     reg_syntax_t syntax;
+re_compile_internal (regex_t *preg, const char * pattern, size_t length,
+                     reg_syntax_t syntax)
 {
   reg_errcode_t err = REG_NOERROR;
@@ -780 +745 @@
   preg->used = sizeof (re_dfa_t);
 
-  /* __libc_lock_init (dfa->lock); - why init before memsetting the whole thing? */
-
   err = init_dfa (dfa, length);
   if (BE (err != REG_NOERROR, 0))
@@ -790 +753 @@
       return err;
     }
-  __libc_lock_init (dfa->lock); /* bird */
-
 #ifdef DEBUG
+  /* Note: length+1 will not overflow since it is checked in init_dfa.  */
   dfa->re_str = re_malloc (char, length + 1);
   strncpy (dfa->re_str, pattern, length + 1);
 #endif
+
+  __libc_lock_init (dfa->lock);
 
   err = re_string_construct (&regexp, pattern, length, preg->translate,
@@ -848 +812 @@
 
 static reg_errcode_t
-init_dfa (dfa, pat_len)
-     re_dfa_t *dfa;
-     int pat_len;
-{
-  int table_size;
+init_dfa (re_dfa_t *dfa, size_t pat_len)
+{
+  unsigned int table_size;
 #ifndef _LIBC
   char *codeset_name;
@@ -862 +824 @@
   dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
 
+  /* Avoid overflows.  */
+  if (pat_len == SIZE_MAX)
+    return REG_ESPACE;
+
   dfa->nodes_alloc = pat_len + 1;
   dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
 
-  dfa->states_alloc = pat_len + 1;
-
   /*  table_size = 2 ^ ceil(log pat_len) */
-  for (table_size = 1; table_size > 0; table_size <<= 1)
+  for (table_size = 1; ; table_size <<= 1)
     if (table_size > pat_len)
       break;
@@ -915 +879 @@
           int i, j, ch;
 
-          dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1);
+          dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
           if (BE (dfa->sb_char == NULL, 0))
             return REG_ESPACE;
 
-          /* Clear all bits by, then set those corresponding to single
-             byte chars.  */
-          bitset_empty (dfa->sb_char);
-
-          for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
-            for (j = 0; j < UINT_BITS; ++j, ++ch)
+          /* Set the bits corresponding to single byte chars.  */
+          for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
+            for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
               {
                 wint_t wch = __btowc (ch);
                 if (wch != WEOF)
-                  dfa->sb_char[i] |= 1 << j;
-# if !defined (_LIBC) && !defined (__INNOTEK_LIBC__)
-                if (isascii (ch) && wch != (wchar_t) ch)
+                  dfa->sb_char[i] |= (bitset_word_t) 1 << j;
+# if !defined (_LIBC)
+                if (isascii (ch) && wch != ch)
                   dfa->map_notascii = 1;
 # endif
@@ -948 +909 @@
 
 static void
-init_word_char (dfa)
-     re_dfa_t *dfa;
+internal_function
+init_word_char (re_dfa_t *dfa)
 {
   int i, j, ch;
   dfa->word_ops_used = 1;
-  for (i = 0, ch = 0; i < BITSET_UINTS; ++i)
-    for (j = 0; j < UINT_BITS; ++j, ++ch)
+  for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
+    for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
       if (isalnum (ch) || ch == '_')
-        dfa->word_char[i] |= 1 << j;
+        dfa->word_char[i] |= (bitset_word_t) 1 << j;
 }
 
@@ -962 +923 @@
 
 static void
-free_workarea_compile (preg)
-     regex_t *preg;
+free_workarea_compile (regex_t *preg)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -982 +942 @@
 
 static reg_errcode_t
-create_initial_state (dfa)
-     re_dfa_t *dfa;
+create_initial_state (re_dfa_t *dfa)
 {
   int first, i;
@@ -1066 +1025 @@
 
 static void
-optimize_utf8 (dfa)
-     re_dfa_t *dfa;
+optimize_utf8 (re_dfa_t *dfa)
 {
   int node, i, mb_chars = 0, has_period = 0;
@@ -1104 +1062 @@
         return;
       case SIMPLE_BRACKET:
-        /* Just double check.  */
-        for (i = 0x80 / UINT_BITS; i < BITSET_UINTS; ++i)
+        /* Just double check.  The non-ASCII range starts at 0x80.  */
+        assert (0x80 % BITSET_WORD_BITS == 0);
+        for (i = 0x80 / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
           if (dfa->nodes[node].opr.sbcset[i])
             return;
@@ -1135 +1094 @@
 
 static reg_errcode_t
-analyze (preg)
-     regex_t *preg;
+analyze (regex_t *preg)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -1199 +1157 @@
    some hairy code in these two functions.  */
 static reg_errcode_t
-postorder (root, fn, extra)
-     bin_tree_t *root;
-     reg_errcode_t (fn (void *, bin_tree_t *));
-     void *extra;
+postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
+           void *extra)
 {
   bin_tree_t *node, *prev;
@@ -1233 +1189 @@
 
 static reg_errcode_t
-preorder (root, fn, extra)
-     bin_tree_t *root;
-     reg_errcode_t (fn (void *, bin_tree_t *));
-     void *extra;
+preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
+          void *extra)
 {
   bin_tree_t *node;
@@ -1268 +1222 @@
    backreferences as well.  Requires a preorder visit.  */
 static reg_errcode_t
-optimize_subexps (extra, node)
-     void *extra;
-     bin_tree_t *node;
+optimize_subexps (void *extra, bin_tree_t *node)
 {
   re_dfa_t *dfa = (re_dfa_t *) extra;
@@ -1291 +1243 @@
 
       dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
-      if (other_idx < 8 * sizeof (dfa->used_bkref_map))
-        dfa->used_bkref_map &= ~(1 << other_idx);
+      if (other_idx < BITSET_WORD_BITS)
+          dfa->used_bkref_map &= ~((bitset_word_t) 1 << other_idx);
     }
 
@@ -1301 +1253 @@
    of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP.  */
 static reg_errcode_t
-lower_subexps (extra, node)
-     void *extra;
-     bin_tree_t *node;
+lower_subexps (void *extra, bin_tree_t *node)
 {
   regex_t *preg = (regex_t *) extra;
@@ -1325 +1275 @@
 
 static bin_tree_t *
-lower_subexp (err, preg, node)
-     reg_errcode_t *err;
-     regex_t *preg;
-     bin_tree_t *node;
+lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -1340 +1287 @@
          this case is the sed "script" /\(\)/x.  */
       && node->left != NULL
-      && (node->token.opr.idx >= 8 * sizeof (dfa->used_bkref_map)
-          || !(dfa->used_bkref_map & (1 << node->token.opr.idx))))
+      && (node->token.opr.idx >= BITSET_WORD_BITS
+          || !(dfa->used_bkref_map
+               & ((bitset_word_t) 1 << node->token.opr.idx))))
     return node->left;
 
@@ -1364 +1312 @@
    nodes.  Requires a postorder visit.  */
 static reg_errcode_t
-calc_first (extra, node)
-     void *extra;
-     bin_tree_t *node;
+calc_first (void *extra, bin_tree_t *node)
 {
   re_dfa_t *dfa = (re_dfa_t *) extra;
@@ -1386 +1332 @@
 /* Pass 2: compute NEXT on the tree.  Preorder visit.  */
 static reg_errcode_t
-calc_next (extra, node)
-     void *extra;
-     bin_tree_t *node;
+calc_next (void *extra, bin_tree_t *node)
 {
   switch (node->token.type)
@@ -1411 +1355 @@
 /* Pass 3: link all DFA nodes to their NEXT node (any order will do).  */
 static reg_errcode_t
-link_nfa_nodes (extra, node)
-     void *extra;
-     bin_tree_t *node;
+link_nfa_nodes (void *extra, bin_tree_t *node)
 {
   re_dfa_t *dfa = (re_dfa_t *) extra;
@@ -1473 +1415 @@
 
 static reg_errcode_t
-duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
-                        init_constraint)
-     re_dfa_t *dfa;
-     int top_org_node, top_clone_node, root_node;
-     unsigned int init_constraint;
-{
-  reg_errcode_t err;
+internal_function
+duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
+                        int root_node, unsigned int init_constraint)
+{
   int org_node, clone_node, ret;
   unsigned int constraint = init_constraint;
@@ -1493 +1432 @@
           org_dest = dfa->nexts[org_node];
           re_node_set_empty (dfa->edests + clone_node);
-          err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
-          if (BE (err != REG_NOERROR, 0))
-            return err;
+          clone_dest = duplicate_node (dfa, org_dest, constraint);
+          if (BE (clone_dest == -1, 0))
+            return REG_ESPACE;
           dfa->nexts[clone_node] = dfa->nexts[org_node];
           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
@@ -1531 +1470 @@
               constraint |= dfa->nodes[org_node].opr.ctx_type;
             }
-          err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
-          if (BE (err != REG_NOERROR, 0))
-            return err;
+          clone_dest = duplicate_node (dfa, org_dest, constraint);
+          if (BE (clone_dest == -1, 0))
+            return REG_ESPACE;
           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
           if (BE (ret < 0, 0))
@@ -1549 +1488 @@
             {
               /* There are no such a duplicated node, create a new one.  */
-              err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
-              if (BE (err != REG_NOERROR, 0))
-                return err;
+              reg_errcode_t err;
+              clone_dest = duplicate_node (dfa, org_dest, constraint);
+              if (BE (clone_dest == -1, 0))
+                return REG_ESPACE;
               ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
               if (BE (ret < 0, 0))
@@ -1570 +1510 @@
 
           org_dest = dfa->edests[org_node].elems[1];
-          err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
-          if (BE (err != REG_NOERROR, 0))
-            return err;
+          clone_dest = duplicate_node (dfa, org_dest, constraint);
+          if (BE (clone_dest == -1, 0))
+            return REG_ESPACE;
           ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
           if (BE (ret < 0, 0))
@@ -1587 +1527 @@
 
 static int
-search_duplicated_node (dfa, org_node, constraint)
-     re_dfa_t *dfa;
-     int org_node;
-     unsigned int constraint;
+search_duplicated_node (const re_dfa_t *dfa, int org_node,
+                        unsigned int constraint)
 {
   int idx;
@@ -1603 +1541 @@
 
 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
-   The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
-   otherwise return the error code.  */
+   Return the index of the new node, or -1 if insufficient storage is
+   available.  */
+
+static int
+duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint)
+{
+  int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
+  if (BE (dup_idx != -1, 1))
+    {
+      dfa->nodes[dup_idx].constraint = constraint;
+      if (dfa->nodes[org_idx].type == ANCHOR)
+        dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
+      dfa->nodes[dup_idx].duplicated = 1;
+
+      /* Store the index of the original node.  */
+      dfa->org_indices[dup_idx] = org_idx;
+    }
+  return dup_idx;
+}
 
 static reg_errcode_t
-duplicate_node (new_idx, dfa, org_idx, constraint)
-     re_dfa_t *dfa;
-     int *new_idx, org_idx;
-     unsigned int constraint;
-{
-  int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
-  if (BE (dup_idx == -1, 0))
-    return REG_ESPACE;
-  dfa->nodes[dup_idx].constraint = constraint;
-  if (dfa->nodes[org_idx].type == ANCHOR)
-    dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
-  dfa->nodes[dup_idx].duplicated = 1;
-
-  /* Store the index of the original node.  */
-  dfa->org_indices[dup_idx] = org_idx;
-  *new_idx = dup_idx;
-  return REG_NOERROR;
-}
-
-static reg_errcode_t
-calc_inveclosure (dfa)
-     re_dfa_t *dfa;
+calc_inveclosure (re_dfa_t *dfa)
 {
   int src, idx, ret;
@@ -1651 +1585 @@
 
 static reg_errcode_t
-calc_eclosure (dfa)
-     re_dfa_t *dfa;
+calc_eclosure (re_dfa_t *dfa)
 {
   int node_idx, incomplete;
@@ -1696 +1629 @@
 
 static reg_errcode_t
-calc_eclosure_iter (new_set, dfa, node, root)
-     re_node_set *new_set;
-     re_dfa_t *dfa;
-     int node, root;
+calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
 {
   reg_errcode_t err;
@@ -1722 +1652 @@
       && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
     {
-      int org_node, cur_node;
-      org_node = cur_node = node;
       err = duplicate_node_closure (dfa, node, node, node, constraint);
       if (BE (err != REG_NOERROR, 0))
@@ -1780 +1708 @@
 
 static void
-fetch_token (result, input, syntax)
-     re_token_t *result;
-     re_string_t *input;
-     reg_syntax_t syntax;
+internal_function
+fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
 {
   re_string_skip_bytes (input, peek_token (result, input, syntax));
@@ -1792 +1718 @@
 
 static int
-peek_token (token, input, syntax)
-     re_token_t *token;
-     re_string_t *input;
-     reg_syntax_t syntax;
+internal_function
+peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
 {
   unsigned char c;
@@ -2033 +1957 @@
 
 static int
-peek_token_bracket (token, input, syntax)
-     re_token_t *token;
-     re_string_t *input;
-     reg_syntax_t syntax;
+internal_function
+peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
 {
   unsigned char c;
@@ -2133 +2055 @@
 
 static bin_tree_t *
-parse (regexp, preg, syntax, err)
-     re_string_t *regexp;
-     regex_t *preg;
-     reg_syntax_t syntax;
-     reg_errcode_t *err;
+parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
+       reg_errcode_t *err)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -2170 +2089 @@
 
 static bin_tree_t *
-parse_reg_exp (regexp, preg, token, syntax, nest, err)
-     re_string_t *regexp;
-     regex_t *preg;
-     re_token_t *token;
-     reg_syntax_t syntax;
-     int nest;
-     reg_errcode_t *err;
+parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
+               reg_syntax_t syntax, int nest, reg_errcode_t *err)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -2216 +2130 @@
 
 static bin_tree_t *
-parse_branch (regexp, preg, token, syntax, nest, err)
-     re_string_t *regexp;
-     regex_t *preg;
-     re_token_t *token;
-     reg_syntax_t syntax;
-     int nest;
-     reg_errcode_t *err;
+parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
+              reg_syntax_t syntax, int nest, reg_errcode_t *err)
 {
   bin_tree_t *tree, *exp;
@@ -2261 +2170 @@
 
 static bin_tree_t *
-parse_expression (regexp, preg, token, syntax, nest, err)
-     re_string_t *regexp;
-     regex_t *preg;
-     re_token_t *token;
-     reg_syntax_t syntax;
-     int nest;
-     reg_errcode_t *err;
+parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
+                  reg_syntax_t syntax, int nest, reg_errcode_t *err)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -2482 +2386 @@
 
 static bin_tree_t *
-parse_sub_exp (regexp, preg, token, syntax, nest, err)
-     re_string_t *regexp;
-     regex_t *preg;
-     re_token_t *token;
-     reg_syntax_t syntax;
-     int nest;
-     reg_errcode_t *err;
+parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
+               reg_syntax_t syntax, int nest, reg_errcode_t *err)
 {
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
@@ -2508 +2407 @@
         return NULL;
     }
-  dfa->completed_bkref_map |= 1 << cur_nsub;
+
+  if (cur_nsub <= '9' - '1')
+    dfa->completed_bkref_map |= 1 << cur_nsub;
 
   tree = create_tree (dfa, tree, NULL, SUBEXP);
@@ -2523 +2424 @@
 
 static bin_tree_t *
-parse_dup_op (elem, regexp, dfa, token, syntax, err)
-     bin_tree_t *elem;
-     re_string_t *regexp;
-     re_dfa_t *dfa;
-     re_token_t *token;
-     reg_syntax_t syntax;
-     reg_errcode_t *err;
+parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
+              re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
 {
   bin_tree_t *tree = NULL, *old_tree = NULL;
@@ -2668 +2564 @@
 
 static reg_errcode_t
+internal_function
 # ifdef RE_ENABLE_I18N
-build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
-     re_charset_t *mbcset;
-     int *range_alloc;
+build_range_exp (bitset_t sbcset, re_charset_t *mbcset, int *range_alloc,
+                 bracket_elem_t *start_elem, bracket_elem_t *end_elem, reg_syntax_t syntax) /* bird: syntax */
 # else /* not RE_ENABLE_I18N */
-build_range_exp (sbcset, start_elem, end_elem)
+build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
+                 bracket_elem_t *end_elem, reg_syntax_t syntax)                             /* bird: syntax */
 # endif /* not RE_ENABLE_I18N */
-     re_bitset_ptr_t sbcset;
-     bracket_elem_t *start_elem, *end_elem;
 {
   unsigned int start_ch, end_ch;
@@ -2695 +2590 @@
 # ifdef RE_ENABLE_I18N
   {
-    wint_t wc, start_wc, end_wc;
+    wchar_t wc;
+    wint_t start_wc;
+    wint_t end_wc;
     wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
 
@@ -2712 +2609 @@
     cmp_buf[0] = start_wc;
     cmp_buf[4] = end_wc;
-    if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
+    if ((syntax & RE_NO_EMPTY_RANGES) && wcscoll (cmp_buf, cmp_buf + 4) > 0) /* bird: RE_NO_EMPTY_RANGES */
       return REG_ERANGE;
 
@@ -2769 +2666 @@
                  : 0));
     if (start_ch > end_ch)
-      return REG_ERANGE;
+      return (syntax & RE_NO_EMPTY_RANGES) ? REG_ERANGE : REG_NOERROR; /* bird: added RE_NO_EMPTY_RANGES check. */
+
     /* Build the table for single byte characters.  */
     for (ch = 0; ch < SBC_MAX; ++ch)
@@ -2788 +2686 @@
 
 static reg_errcode_t
+internal_function
 # ifdef RE_ENABLE_I18N
-build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
-     re_charset_t *mbcset;
-     int *coll_sym_alloc;
+build_collating_symbol (bitset_t sbcset, re_charset_t *mbcset,
+                        int *coll_sym_alloc, const unsigned char *name)
 # else /* not RE_ENABLE_I18N */
-build_collating_symbol (sbcset, name)
+build_collating_symbol (bitset_t sbcset, const unsigned char *name)
 # endif /* not RE_ENABLE_I18N */
-     re_bitset_ptr_t sbcset;
-     const unsigned char *name;
 {
   size_t name_len = strlen ((const char *) name);
@@ -2813 +2709 @@
 
 static bin_tree_t *
-parse_bracket_exp (regexp, dfa, token, syntax, err)
-     re_string_t *regexp;
-     re_dfa_t *dfa;
-     re_token_t *token;
-     reg_syntax_t syntax;
-     reg_errcode_t *err;
+parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
+                   reg_syntax_t syntax, reg_errcode_t *err)
 {
 #ifdef _LIBC
@@ -2840 +2732 @@
       int32_t hash = elem_hash ((const char *) name, name_len);
       int32_t elem = hash % table_size;
-      int32_t second = hash % (table_size - 2);
-      while (symb_table[2 * elem] != 0)
-        {
-          /* First compare the hashing value.  */
-          if (symb_table[2 * elem] == hash
-              /* Compare the length of the name.  */
-              && name_len == extra[symb_table[2 * elem + 1]]
-              /* Compare the name.  */
-              && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
-                         name_len) == 0)
+      if (symb_table[2 * elem] != 0)
+        {
+          int32_t second = hash % (table_size - 2) + 1;
+
+          do
             {
-              /* Yep, this is the entry.  */
-              break;
+              /* First compare the hashing value.  */
+              if (symb_table[2 * elem] == hash
+                  /* Compare the length of the name.  */
+                  && name_len == extra[symb_table[2 * elem + 1]]
+                  /* Compare the name.  */
+                  && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
+                             name_len) == 0)
+                {
+                  /* Yep, this is the entry.  */
+                  break;
+                }
+
+              /* Next entry.  */
+              elem += second;
             }
-
-          /* Next entry.  */
-          elem += second;
+          while (symb_table[2 * elem] != 0);
         }
       return elem;
@@ -2938 +2835 @@
          re_charset_t *mbcset;
          int *range_alloc;
-         re_bitset_ptr_t sbcset;
+         bitset_t sbcset;
          bracket_elem_t *start_elem, *end_elem;
     {
@@ -3021 +2918 @@
          re_charset_t *mbcset;
          int *coll_sym_alloc;
-         re_bitset_ptr_t sbcset;
+         bitset_t sbcset;
          const unsigned char *name;
     {
@@ -3098 +2995 @@
       if (MB_CUR_MAX > 1)
       */
-        collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
+      collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
       table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
       symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
@@ -3106 +3003 @@
     }
 #endif
-  sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
+  sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
 #ifdef RE_ENABLE_I18N
   mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
@@ -3217 +3114 @@
           *err = build_range_exp (sbcset,
                                   dfa->mb_cur_max > 1 ? mbcset : NULL,
-                                  &range_alloc, &start_elem, &end_elem);
+                                  &range_alloc, &start_elem, &end_elem, syntax);
 # else
-          *err = build_range_exp (sbcset, &start_elem, &end_elem);
+          *err = build_range_exp (sbcset, &start_elem, &end_elem, syntax);
 # endif
 #endif /* RE_ENABLE_I18N */
@@ -3316 +3213 @@
       if (BE (mbc_tree == NULL, 0))
         goto parse_bracket_exp_espace;
-      for (sbc_idx = 0; sbc_idx < BITSET_UINTS; ++sbc_idx)
+      for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
         if (sbcset[sbc_idx])
           break;
       /* If there are no bits set in sbcset, there is no point
          of having both SIMPLE_BRACKET and COMPLEX_BRACKET.  */
-      if (sbc_idx < BITSET_UINTS)
+      if (sbc_idx < BITSET_WORDS)
         {
           /* Build a tree for simple bracket.  */
@@ -3369 +3266 @@
 
 static reg_errcode_t
-parse_bracket_element (elem, regexp, token, token_len, dfa, syntax,
-                       accept_hyphen)
-     bracket_elem_t *elem;
-     re_string_t *regexp;
-     re_token_t *token;
-     int token_len;
-     re_dfa_t *dfa;
-     reg_syntax_t syntax;
-     int accept_hyphen;
+parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
+                       re_token_t *token, int token_len, re_dfa_t *dfa,
+                       reg_syntax_t syntax, int accept_hyphen)
 {
 #ifdef RE_ENABLE_I18N
@@ -3415 +3306 @@
 
 static reg_errcode_t
-parse_bracket_symbol (elem, regexp, token)
-     bracket_elem_t *elem;
-     re_string_t *regexp;
-     re_token_t *token;
+parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
+                      re_token_t *token)
 {
   unsigned char ch, delim = token->opr.c;
@@ -3465 +3354 @@
 static reg_errcode_t
 #ifdef RE_ENABLE_I18N
-build_equiv_class (sbcset, mbcset, equiv_class_alloc, name)
-     re_charset_t *mbcset;
-     int *equiv_class_alloc;
+build_equiv_class (bitset_t sbcset, re_charset_t *mbcset,
+                   int *equiv_class_alloc, const unsigned char *name)
 #else /* not RE_ENABLE_I18N */
-build_equiv_class (sbcset, name)
+build_equiv_class (bitset_t sbcset, const unsigned char *name)
 #endif /* not RE_ENABLE_I18N */
-     re_bitset_ptr_t sbcset;
-     const unsigned char *name;
-{
-#if defined _LIBC
+{
+#ifdef _LIBC
   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
   if (nrules != 0)
@@ -3560 +3446 @@
 static reg_errcode_t
 #ifdef RE_ENABLE_I18N
-build_charclass (trans, sbcset, mbcset, char_class_alloc, class_name, syntax)
-     re_charset_t *mbcset;
-     int *char_class_alloc;
+build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
+                 re_charset_t *mbcset, int *char_class_alloc,
+                 const unsigned char *class_name, reg_syntax_t syntax)
 #else /* not RE_ENABLE_I18N */
-build_charclass (trans, sbcset, class_name, syntax)
+build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
+                 const unsigned char *class_name, reg_syntax_t syntax)
 #endif /* not RE_ENABLE_I18N */
-     unsigned RE_TRANSLATE_TYPE trans;
-     re_bitset_ptr_t sbcset;
-     const unsigned char *class_name;
-     reg_syntax_t syntax;
 {
   int i;
@@ -3599 +3482 @@
 
 #define BUILD_CHARCLASS_LOOP(ctype_func)        \
-    for (i = 0; i < SBC_MAX; ++i)               \
+  do {                                          \
+    if (BE (trans != NULL, 0))                  \
       {                                         \
-        if (ctype_func (i))                     \
-          {                                     \
-            int ch = trans ? trans[i] : i;      \
-            bitset_set (sbcset, ch);            \
-          }                                     \
-      }
+        for (i = 0; i < SBC_MAX; ++i)           \
+          if (ctype_func (i))                   \
+            bitset_set (sbcset, trans[i]);      \
+      }                                         \
+    else                                        \
+      {                                         \
+        for (i = 0; i < SBC_MAX; ++i)           \
+          if (ctype_func (i))                   \
+            bitset_set (sbcset, i);             \
+      }                                         \
+  } while (0)
 
   if (strcmp (name, "alnum") == 0)
-    BUILD_CHARCLASS_LOOP (isalnum)
+    BUILD_CHARCLASS_LOOP (isalnum);
   else if (strcmp (name, "cntrl") == 0)
-    BUILD_CHARCLASS_LOOP (iscntrl)
+    BUILD_CHARCLASS_LOOP (iscntrl);
   else if (strcmp (name, "lower") == 0)
-    BUILD_CHARCLASS_LOOP (islower)
+    BUILD_CHARCLASS_LOOP (islower);
   else if (strcmp (name, "space") == 0)
-    BUILD_CHARCLASS_LOOP (isspace)
+    BUILD_CHARCLASS_LOOP (isspace);
   else if (strcmp (name, "alpha") == 0)
-    BUILD_CHARCLASS_LOOP (isalpha)
+    BUILD_CHARCLASS_LOOP (isalpha);
   else if (strcmp (name, "digit") == 0)
-    BUILD_CHARCLASS_LOOP (isdigit)
+    BUILD_CHARCLASS_LOOP (isdigit);
   else if (strcmp (name, "print") == 0)
-    BUILD_CHARCLASS_LOOP (isprint)
+    BUILD_CHARCLASS_LOOP (isprint);
   else if (strcmp (name, "upper") == 0)
-    BUILD_CHARCLASS_LOOP (isupper)
+    BUILD_CHARCLASS_LOOP (isupper);
   else if (strcmp (name, "blank") == 0)
-    BUILD_CHARCLASS_LOOP (isblank)
+    BUILD_CHARCLASS_LOOP (isblank);
   else if (strcmp (name, "graph") == 0)
-    BUILD_CHARCLASS_LOOP (isgraph)
+    BUILD_CHARCLASS_LOOP (isgraph);
   else if (strcmp (name, "punct") == 0)
-    BUILD_CHARCLASS_LOOP (ispunct)
+    BUILD_CHARCLASS_LOOP (ispunct);
   else if (strcmp (name, "xdigit") == 0)
-    BUILD_CHARCLASS_LOOP (isxdigit)
+    BUILD_CHARCLASS_LOOP (isxdigit);
   else
     return REG_ECTYPE;
@@ -3639 +3528 @@
 
 static bin_tree_t *
-build_charclass_op (dfa, trans, class_name, extra, non_match, err)
-     re_dfa_t *dfa;
-     unsigned RE_TRANSLATE_TYPE trans;
-     const unsigned char *class_name;
-     const unsigned char *extra;
-     int non_match;
-     reg_errcode_t *err;
+build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
+                    const unsigned char *class_name,
+                    const unsigned char *extra, int non_match,
+                    reg_errcode_t *err)
 {
   re_bitset_ptr_t sbcset;
@@ -3656 +3542 @@
   bin_tree_t *tree;
 
-  sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);
+  sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
 #ifdef RE_ENABLE_I18N
   mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
@@ -3759 +3645 @@
 
 static int
-fetch_number (input, token, syntax)
-     re_string_t *input;
-     re_token_t *token;
-     reg_syntax_t syntax;
+fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
 {
   int num = -1;
@@ -3804 +3687 @@
 
 static bin_tree_t *
-create_tree (dfa, left, right, type)
-     re_dfa_t *dfa;
-     bin_tree_t *left;
-     bin_tree_t *right;
-     re_token_type_t type;
+create_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
+             re_token_type_t type)
 {
   re_token_t t;
@@ -3816 +3696 @@
 
 static bin_tree_t *
-create_token_tree (dfa, left, right, token)
-     re_dfa_t *dfa;
-     bin_tree_t *left;
-     bin_tree_t *right;
-     const re_token_t *token;
+create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
+                   const re_token_t *token)
 {
   bin_tree_t *tree;
@@ -3856 +3733 @@
 
 static reg_errcode_t
-mark_opt_subexp (extra, node)
-     void *extra;
-     bin_tree_t *node;
+mark_opt_subexp (void *extra, bin_tree_t *node)
 {
   int idx = (int) (long) extra;
@@ -3898 +3773 @@
 
 static bin_tree_t *
-duplicate_tree (root, dfa)
-     const bin_tree_t *root;
-     re_dfa_t *dfa;
+duplicate_tree (const bin_tree_t *root, re_dfa_t *dfa)
 {
   const bin_tree_t *node;