/* Extended regular expression matching and search library.

   Copyright (C) 2002-2026 Free Software Foundation, Inc.

   This file is part of the GNU C Library.

   Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.

   The GNU C Library is free software; you can redistribute it and/or

   modify it under the terms of the GNU Lesser General Public

   License as published by the Free Software Foundation; either

   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public

   License along with the GNU C Library; if not, see

   <https://www.gnu.org/licenses/>.  */

#ifdef _LIBC

# include <locale/weight.h>

#endif

/* The localeinfo-related code fixes glibc bug 20381.

   Someday this fix should be merged into glibc.  */

#if !defined _LIBC && !defined _REGEX_AVOID_UCHAR_H

# include "localeinfo.h"

#endif

static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,

            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, size_t pat_len);

static void free_charset (re_charset_t *cset);

static void free_workarea_compile (regex_t *preg);

static reg_errcode_t create_initial_state (re_dfa_t *dfa);

static void optimize_utf8 (re_dfa_t *dfa);

static reg_errcode_t analyze (regex_t *preg);

static reg_errcode_t preorder (bin_tree_t *root,

             reg_errcode_t (fn (void *, bin_tree_t *)),

             void *extra);

static reg_errcode_t postorder (bin_tree_t *root,

        reg_errcode_t (fn (void *, bin_tree_t *)),

        void *extra);

static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);

static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);

static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,

         bin_tree_t *node);

static reg_errcode_t calc_first (void *extra, bin_tree_t *node);

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 Idx duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint);

static Idx search_duplicated_node (const re_dfa_t *dfa, Idx org_node,

           unsigned int constraint);

static reg_errcode_t calc_eclosure (re_dfa_t *dfa);

static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,

           Idx node, bool root);

static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);

static Idx fetch_number (re_string_t *input, re_token_t *token,

       reg_syntax_t syntax);

static int peek_token (re_token_t *token, re_string_t *input,

      reg_syntax_t syntax);

static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,

        reg_syntax_t syntax, reg_errcode_t *err);

static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,

          re_token_t *token, reg_syntax_t syntax,

          Idx nest, reg_errcode_t *err);

static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,

         re_token_t *token, reg_syntax_t syntax,

         Idx nest, reg_errcode_t *err);

static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,

             re_token_t *token, reg_syntax_t syntax,

             Idx nest, reg_errcode_t *err);

static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,

          re_token_t *token, reg_syntax_t syntax,

          Idx nest, reg_errcode_t *err);

static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,

         re_dfa_t *dfa, re_token_t *token,

         reg_syntax_t syntax, reg_errcode_t *err);

static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,

              re_token_t *token, reg_syntax_t syntax,

              reg_errcode_t *err);

static reg_errcode_t 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,

              bool accept_hyphen);

static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,

            re_string_t *regexp,

            re_token_t *token);

static reg_errcode_t build_equiv_class (bitset_t sbcset,

          re_charset_t *mbcset,

          Idx *equiv_class_alloc,

          const unsigned char *name);

static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,

              bitset_t sbcset,

              re_charset_t *mbcset,

              Idx *char_class_alloc,

              const char *class_name,

              reg_syntax_t syntax);

static bin_tree_t *build_charclass_op (re_dfa_t *dfa,

               RE_TRANSLATE_TYPE trans,

               const char *class_name,

               const char *extra,

               bool non_match, reg_errcode_t *err);

static bin_tree_t *create_tree (re_dfa_t *dfa,

        bin_tree_t *left, bin_tree_t *right,

        re_token_type_t type);

static bin_tree_t *create_token_tree (re_dfa_t *dfa,

              bin_tree_t *left, bin_tree_t *right,

              const re_token_t *token);

static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);

static void free_token (re_token_t *node);

static reg_errcode_t free_tree (void *extra, bin_tree_t *node);

static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);

/* This table gives an error message for each of the error codes listed

   in regex.h.  Obviously the order here has to be same as there.

   POSIX doesn't require that we do anything for REG_NOERROR,

   but why not be nice?  */

static const char __re_error_msgid[] =

  {

#define REG_NOERROR_IDX 0

    gettext_noop ("Success")  /* REG_NOERROR */

    "\0"

#define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")

    gettext_noop ("No match") /* REG_NOMATCH */

    "\0"

#define REG_BADPAT_IDX  (REG_NOMATCH_IDX + sizeof "No match")

    gettext_noop ("Invalid regular expression") /* REG_BADPAT */

    "\0"

#define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")

    gettext_noop ("Invalid collation character") /* REG_ECOLLATE */

    "\0"

#define REG_ECTYPE_IDX  (REG_ECOLLATE_IDX + sizeof "Invalid collation character")

    gettext_noop ("Invalid character class name") /* REG_ECTYPE */

    "\0"

#define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")

    gettext_noop ("Trailing backslash") /* REG_EESCAPE */

    "\0"

#define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")

    gettext_noop ("Invalid back reference") /* REG_ESUBREG */

    "\0"

#define REG_EBRACK_IDX  (REG_ESUBREG_IDX + sizeof "Invalid back reference")

    gettext_noop ("Unmatched [, [^, [:, [., or [=") /* REG_EBRACK */

    "\0"

#define REG_EPAREN_IDX  (REG_EBRACK_IDX + sizeof "Unmatched [, [^, [:, [., or [=")

    gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */

    "\0"

#define REG_EBRACE_IDX  (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")

    gettext_noop ("Unmatched \\{") /* REG_EBRACE */

    "\0"

#define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")

    gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */

    "\0"

#define REG_ERANGE_IDX  (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")

    gettext_noop ("Invalid range end")  /* REG_ERANGE */

    "\0"

#define REG_ESPACE_IDX  (REG_ERANGE_IDX + sizeof "Invalid range end")

    gettext_noop ("Memory exhausted") /* REG_ESPACE */

    "\0"

#define REG_BADRPT_IDX  (REG_ESPACE_IDX + sizeof "Memory exhausted")

    gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */

    "\0"

#define REG_EEND_IDX  (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")

    gettext_noop ("Premature end of regular expression") /* REG_EEND */

    "\0"

#define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")

    gettext_noop ("Regular expression too big") /* REG_ESIZE */

    "\0"

#define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")

    gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */

  };

static const size_t __re_error_msgid_idx[] =

  {

    REG_NOERROR_IDX,

    REG_NOMATCH_IDX,

    REG_BADPAT_IDX,

    REG_ECOLLATE_IDX,

    REG_ECTYPE_IDX,

    REG_EESCAPE_IDX,

    REG_ESUBREG_IDX,

    REG_EBRACK_IDX,

    REG_EPAREN_IDX,

    REG_EBRACE_IDX,

    REG_BADBR_IDX,

    REG_ERANGE_IDX,

    REG_ESPACE_IDX,

    REG_BADRPT_IDX,

    REG_EEND_IDX,

    REG_ESIZE_IDX,

    REG_ERPAREN_IDX

  };

/* Entry points for GNU code.  */

/* re_compile_pattern is the GNU regular expression compiler: it

   compiles PATTERN (of length LENGTH) and puts the result in BUFP.

   Returns 0 if the pattern was valid, otherwise an error string.

   Assumes the 'allocated' (and perhaps 'buffer') and 'translate' fields

   are set in BUFP on entry.  */

const char *

re_compile_pattern (const char *pattern, size_t length,

        struct re_pattern_buffer *bufp)

{

  reg_errcode_t ret;

  /* And GNU code determines whether or not to get register information

     by passing null for the REGS argument to re_match, etc., not by

     setting no_sub, unless RE_NO_SUB is set.  */

  bufp->no_sub = !!(re_syntax_options & RE_NO_SUB);

  /* Match anchors at newline.  */

  bufp->newline_anchor = 1;

  ret = re_compile_internal (bufp, pattern, length, re_syntax_options);

  if (!ret)

    return NULL;

  return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);

}

weak_alias (__re_compile_pattern, re_compile_pattern)

/* Set by 're_set_syntax' to the current regexp syntax to recognize.  Can

   also be assigned to arbitrarily: each pattern buffer stores its own

   syntax, so it can be changed between regex compilations.  */

/* This has no initializer because initialized variables in Emacs

   become read-only after dumping.  */

reg_syntax_t re_syntax_options;

/* Specify the precise syntax of regexps for compilation.  This provides

   for compatibility for various utilities which historically have

   different, incompatible syntaxes.

   The argument SYNTAX is a bit mask comprised of the various bits

   defined in regex.h.  We return the old syntax.  */

reg_syntax_t

re_set_syntax (reg_syntax_t syntax)

{

  reg_syntax_t ret = re_syntax_options;

  re_syntax_options = syntax;

  return ret;

}

weak_alias (__re_set_syntax, re_set_syntax)

int

re_compile_fastmap (struct re_pattern_buffer *bufp)

{

  re_dfa_t *dfa = bufp->buffer;

  char *fastmap = bufp->fastmap;

  memset (fastmap, '\0', sizeof (char) * SBC_MAX);

  re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);

  if (dfa->init_state != dfa->init_state_word)

    re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);

  if (dfa->init_state != dfa->init_state_nl)

    re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);

  if (dfa->init_state != dfa->init_state_begbuf)

    re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);

  bufp->fastmap_accurate = 1;

  return 0;

}

weak_alias (__re_compile_fastmap, re_compile_fastmap)

static __always_inline void

re_set_fastmap (char *fastmap, unsigned char ch)

{

  fastmap[ch] = 1;

}

/* Record in FASTMAP the initial byte of the representations of all

   characters that match WC ignoring case, other than WC itself.

   Use MBS as a scratch state.  */

static void

re_set_fastmap_icase (char *fastmap, wchar_t wc, mbstate_t *mbs)

{

#if defined _LIBC || defined _REGEX_AVOID_UCHAR_H

  wchar_t folded[1] = {__towlower (wc)};

  int nfolded = folded[0] != wc;

#else

  wchar_t folded[CASE_FOLDED_BUFSIZE];

  int nfolded = case_folded_counterparts (wc, folded);

#endif

  for (int i = 0; i < nfolded; i++)

    {

      char buf[MB_LEN_MAX];

      if (__wcrtomb (buf, folded[i], mbs) != (size_t) -1)

  re_set_fastmap (fastmap, buf[0]);

    }

}

/* Helper function for re_compile_fastmap.

   Compile fastmap for the initial_state INIT_STATE.  */

static void

re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,

       char *fastmap)

{

  re_dfa_t *dfa = bufp->buffer;

  Idx node_cnt;

  for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)

    {

      Idx node = init_state->nodes.elems[node_cnt];

      re_token_type_t type = dfa->nodes[node].type;

      if (type == CHARACTER)

  {

    re_set_fastmap (fastmap, dfa->nodes[node].opr.c);

    if (bufp->syntax & RE_ICASE)

      {

        unsigned char buf[MB_LEN_MAX];

        unsigned char *p;

        wchar_t wc;

        mbstate_t state;

        p = buf;

        *p++ = dfa->nodes[node].opr.c;

        while (++node < dfa->nodes_len

         && dfa->nodes[node].type == CHARACTER

         && dfa->nodes[node].mb_partial)

    *p++ = dfa->nodes[node].opr.c;

        memset (&state, '\0', sizeof (state));

        if (__mbrtowc (&wc, (const char *) buf, p - buf,

           &state) == p - buf)

    re_set_fastmap_icase (fastmap, wc, &state);

      }

  }

      else if (type == SIMPLE_BRACKET)

  {

    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, ch);

      }

  }

      else if (type == COMPLEX_BRACKET)

  {

    re_charset_t *cset = dfa->nodes[node].opr.mbcset;

    Idx i;

#ifdef _LIBC

    /* See if we have to try all bytes which start multiple collation

       elements.

       e.g. In da_DK, we want to catch 'a' since "aa" is a valid

      collation element, and don't catch 'b' since 'b' is

      the only collation element which starts from 'b' (and

      it is caught by SIMPLE_BRACKET).  */

        if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0

      && (cset->ncoll_syms || cset->nranges))

    {

      const int32_t *table = (const int32_t *)

        _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);

      for (i = 0; i < SBC_MAX; ++i)

        if (table[i] < 0)

          re_set_fastmap (fastmap, i);

    }

#endif /* _LIBC */

    /* See if we have to start the match at all multibyte characters,

       i.e. where we would not find an invalid sequence.  This only

       applies to multibyte character sets; for single byte character

       sets, the SIMPLE_BRACKET again suffices.  */

    if (dfa->mb_cur_max > 1

        && (cset->nchar_classes || cset->non_match || cset->nranges

#ifdef _LIBC

      || cset->nequiv_classes

#endif /* _LIBC */

     ))

      {

        unsigned char c = 0;

        do

    {

      mbstate_t mbs;

      memset (&mbs, 0, sizeof (mbs));

      if (__mbrtowc (NULL, (char *) &c, 1, &mbs) == (size_t) -2)

        re_set_fastmap (fastmap, c);

    }

        while (++c != 0);

      }

    else

      {

        /* ... Else catch all bytes which can start the mbchars.  */

        for (i = 0; i < cset->nmbchars; ++i)

    {

      char buf[MB_LEN_MAX];

      mbstate_t state;

      memset (&state, '\0', sizeof (state));

      if (__wcrtomb (buf, cset->mbchars[i], &state) != (size_t) -1)

        re_set_fastmap (fastmap, buf[0]);

      if (bufp->syntax & RE_ICASE)

        re_set_fastmap_icase (fastmap, cset->mbchars[i], &state);

    }

      }

  }

      else if (type == OP_PERIOD || type == OP_UTF8_PERIOD || type == END_OF_RE)

  {

    memset (fastmap, '\1', sizeof (char) * SBC_MAX);

    if (type == END_OF_RE)

      bufp->can_be_null = 1;

    return;

  }

    }

}

/* Entry point for POSIX code.  */

/* regcomp takes a regular expression as a string and compiles it.

   PREG is a regex_t *.  We do not expect any fields to be initialized,

   since POSIX says we shouldn't.  Thus, we set

     'buffer' to the compiled pattern;

     'used' to the length of the compiled pattern;

     'syntax' to RE_SYNTAX_POSIX_EXTENDED if the

       REG_EXTENDED bit in CFLAGS is set; otherwise, to

       RE_SYNTAX_POSIX_BASIC;

     'newline_anchor' to REG_NEWLINE being set in CFLAGS;

     'fastmap' to an allocated space for the fastmap;

     'fastmap_accurate' to zero;

     're_nsub' to the number of subexpressions in PATTERN.

   PATTERN is the address of the pattern string.

   CFLAGS is a series of bits which affect compilation.

     If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we

     use POSIX basic syntax.

     If REG_NEWLINE is set, then . and [^...] don't match newline.

     Also, regexec will try a match beginning after every newline.

     If REG_ICASE is set, then we considers upper- and lowercase

     versions of letters to be equivalent when matching.

     If REG_NOSUB is set, then when PREG is passed to regexec, that

     routine will report only success or failure, and nothing about the

     registers.

   It returns 0 if it succeeds, nonzero if it doesn't.  (See regex.h for

   the return codes and their meanings.)  */

int

regcomp (regex_t *__restrict preg, const char *__restrict pattern, int cflags)

{

  reg_errcode_t ret;

  reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED

       : RE_SYNTAX_POSIX_BASIC);

  preg->buffer = NULL;

  preg->allocated = 0;

  preg->used = 0;

  /* Try to allocate space for the fastmap.  */

  preg->fastmap = re_malloc (char, SBC_MAX);

  if (__glibc_unlikely (preg->fastmap == NULL))

    return REG_ESPACE;

  syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;

  /* If REG_NEWLINE is set, newlines are treated differently.  */

  if (cflags & REG_NEWLINE)

    { /* REG_NEWLINE implies neither . nor [^...] match newline.  */

      syntax &= ~RE_DOT_NEWLINE;

      syntax |= RE_HAT_LISTS_NOT_NEWLINE;

      /* It also changes the matching behavior.  */

      preg->newline_anchor = 1;

    }

  else

    preg->newline_anchor = 0;

  preg->no_sub = !!(cflags & REG_NOSUB);

  preg->translate = NULL;

  ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);

  /* POSIX doesn't distinguish between an unmatched open-group and an

     unmatched close-group: both are REG_EPAREN.  */

  if (ret == REG_ERPAREN)

    ret = REG_EPAREN;

  /* We have already checked preg->fastmap != NULL.  */

  if (__glibc_likely (ret == REG_NOERROR))

    /* Compute the fastmap now, since regexec cannot modify the pattern

       buffer.  This function never fails in this implementation.  */

    (void) re_compile_fastmap (preg);

  else

    {

      /* Some error occurred while compiling the expression.  */

      re_free (preg->fastmap);

      preg->fastmap = NULL;

    }

  return (int) ret;

}

libc_hidden_def (__regcomp)

weak_alias (__regcomp, regcomp)

/* Returns a message corresponding to an error code, ERRCODE, returned

   from either regcomp or regexec.   We don't use PREG here.  */

size_t

regerror (int errcode, const regex_t *__restrict preg, char *__restrict errbuf,

    size_t errbuf_size)

{

  const char *msg;

  size_t msg_size;

  int nerrcodes = countof (__re_error_msgid_idx);

  if (__glibc_unlikely (errcode < 0 || errcode >= nerrcodes))

    /* Only error codes returned by the rest of the code should be passed

       to this routine.  If we are given anything else, or if other regex

       code generates an invalid error code, then the program has a bug.

       Dump core so we can fix it.  */

    abort ();

  msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);

  msg_size = strlen (msg) + 1; /* Includes the null.  */

  if (__glibc_likely (errbuf_size != 0))

    {

      size_t cpy_size = msg_size;

      if (__glibc_unlikely (msg_size > errbuf_size))

  {

    cpy_size = errbuf_size - 1;

    errbuf[cpy_size] = '\0';

  }

      memcpy (errbuf, msg, cpy_size);

    }

  return msg_size;

}

weak_alias (__regerror, regerror)

/* This static array is used for the map to single-byte characters when

   UTF-8 is used.  Otherwise we would allocate memory just to initialize

   it the same all the time.  UTF-8 is the preferred encoding so this is

   a worthwhile optimization.  */

static const bitset_t utf8_sb_map =

{

  /* Set the first 128 bits.  */

#if (defined __GNUC__ || __clang_major__ >= 4) && !defined __STRICT_ANSI__

  [0 ... 0x80 / BITSET_WORD_BITS - 1] = BITSET_WORD_MAX

#else

# if 4 * BITSET_WORD_BITS < ASCII_CHARS

#  error "bitset_word_t is narrower than 32 bits"

# elif 3 * BITSET_WORD_BITS < ASCII_CHARS

  BITSET_WORD_MAX, BITSET_WORD_MAX, BITSET_WORD_MAX,

# elif 2 * BITSET_WORD_BITS < ASCII_CHARS

  BITSET_WORD_MAX, BITSET_WORD_MAX,

# elif 1 * BITSET_WORD_BITS < ASCII_CHARS

  BITSET_WORD_MAX,

# endif

  (BITSET_WORD_MAX

   >> (SBC_MAX % BITSET_WORD_BITS == 0

       ? 0

       : BITSET_WORD_BITS - SBC_MAX % BITSET_WORD_BITS))

#endif

};

static void

free_dfa_content (re_dfa_t *dfa)

{

  Idx i, j;

  if (dfa->nodes)

    for (i = 0; i < dfa->nodes_len; ++i)

      free_token (dfa->nodes + i);

  re_free (dfa->nexts);

  for (i = 0; i < dfa->nodes_len; ++i)

    {

      if (dfa->eclosures != NULL)

  re_node_set_free (dfa->eclosures + i);

      if (dfa->inveclosures != NULL)

  re_node_set_free (dfa->inveclosures + i);

      if (dfa->edests != NULL)

  re_node_set_free (dfa->edests + i);

    }

  re_free (dfa->edests);

  re_free (dfa->eclosures);

  re_free (dfa->inveclosures);

  re_free (dfa->nodes);

  if (dfa->state_table)

    for (i = 0; i <= dfa->state_hash_mask; ++i)

      {

  struct re_state_table_entry *entry = dfa->state_table + i;

  for (j = 0; j < entry->num; ++j)

    {

      re_dfastate_t *state = entry->array[j];

      free_state (state);

    }

  re_free (entry->array);

      }

  re_free (dfa->state_table);

  if (dfa->sb_char != utf8_sb_map)

    re_free (dfa->sb_char);

  re_free (dfa->subexp_map);

#ifdef DEBUG

  re_free (dfa->re_str);

#endif

  re_free (dfa);

}

/* Free dynamically allocated space used by PREG.  */

void

regfree (regex_t *preg)

{

  re_dfa_t *dfa = preg->buffer;

  if (__glibc_likely (dfa != NULL))

    {

      lock_fini (dfa->lock);

      free_dfa_content (dfa);

    }

  preg->buffer = NULL;

  preg->allocated = 0;

  re_free (preg->fastmap);

  preg->fastmap = NULL;

  re_free (preg->translate);

  preg->translate = NULL;

}

libc_hidden_def (__regfree)

weak_alias (__regfree, regfree)

/* Entry points compatible with 4.2 BSD regex library.  We don't define

   them unless specifically requested.  */

#if defined _REGEX_RE_COMP || defined _LIBC

/* BSD has one and only one pattern buffer.  */

static struct re_pattern_buffer re_comp_buf;

char *

# ifdef _LIBC

/* Make these definitions weak in libc, so POSIX programs can redefine

   these names if they don't use our functions, and still use

   regcomp/regexec above without link errors.  */

weak_function

# endif

re_comp (const char *s)

{

  reg_errcode_t ret;

  char *fastmap;

  if (!s)

    {

      if (!re_comp_buf.buffer)

  return gettext ("No previous regular expression");

      return 0;

    }

  if (re_comp_buf.buffer)

    {

      fastmap = re_comp_buf.fastmap;

      re_comp_buf.fastmap = NULL;

      __regfree (&re_comp_buf);

      memset (&re_comp_buf, '\0', sizeof (re_comp_buf));

      re_comp_buf.fastmap = fastmap;

    }

  if (re_comp_buf.fastmap == NULL)

    {

      re_comp_buf.fastmap = re_malloc (char, SBC_MAX);

      if (re_comp_buf.fastmap == NULL)

  return (char *) gettext (__re_error_msgid

         + __re_error_msgid_idx[(int) REG_ESPACE]);

    }

  /* Since 're_exec' always passes NULL for the 'regs' argument, we

     don't need to initialize the pattern buffer fields which affect it.  */

  /* Match anchors at newlines.  */

  re_comp_buf.newline_anchor = 1;

  ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);

  if (!ret)

    return NULL;

  /* Yes, we're discarding 'const' here if !HAVE_LIBINTL.  */

  return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);

}

#ifdef _LIBC

libc_freeres_fn (free_mem)

{

  __regfree (&re_comp_buf);

}

#endif

#endif /* _REGEX_RE_COMP */

/* Internal entry point.

   Compile the regular expression PATTERN, whose length is LENGTH.

   SYNTAX indicate regular expression's syntax.  */

static reg_errcode_t

re_compile_internal (regex_t *preg, const char * pattern, size_t length,

         reg_syntax_t syntax)

{

  reg_errcode_t err = REG_NOERROR;

  re_dfa_t *dfa;

  re_string_t regexp;

  /* Initialize the pattern buffer.  */

  preg->fastmap_accurate = 0;

  preg->syntax = syntax;

  preg->not_bol = preg->not_eol = 0;

  preg->used = 0;

  preg->re_nsub = 0;

  preg->can_be_null = 0;

  preg->regs_allocated = REGS_UNALLOCATED;

  /* Initialize the dfa.  */

  dfa = preg->buffer;

  if (__glibc_unlikely (preg->allocated < sizeof (re_dfa_t)))

    {

      /* If zero allocated, but buffer is non-null, try to realloc

   enough space.  This loses if buffer's address is bogus, but

   that is the user's responsibility.  If ->buffer is NULL this

   is a simple allocation.  */

      dfa = re_realloc (preg->buffer, re_dfa_t, 1);

      if (dfa == NULL)

  return REG_ESPACE;

      preg->allocated = sizeof (re_dfa_t);

      preg->buffer = dfa;

    }

  preg->used = sizeof (re_dfa_t);

  err = init_dfa (dfa, length);

  if (__glibc_unlikely (err == REG_NOERROR && lock_init (dfa->lock) != 0))

    err = REG_ESPACE;

  if (__glibc_unlikely (err != REG_NOERROR))

    {

      free_dfa_content (dfa);

      preg->buffer = NULL;

      preg->allocated = 0;

      return err;

    }

#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

  err = re_string_construct (&regexp, pattern, length, preg->translate,

           (syntax & RE_ICASE) != 0, dfa);

  if (__glibc_unlikely (err != REG_NOERROR))

    {

    re_compile_internal_free_return:

      free_workarea_compile (preg);

      re_string_destruct (&regexp);

      lock_fini (dfa->lock);

      free_dfa_content (dfa);

      preg->buffer = NULL;

      preg->allocated = 0;

      return err;

    }

  /* Parse the regular expression, and build a structure tree.  */

  preg->re_nsub = 0;

  dfa->str_tree = parse (&regexp, preg, syntax, &err);

  if (__glibc_unlikely (dfa->str_tree == NULL))

    goto re_compile_internal_free_return;

  /* Analyze the tree and create the nfa.  */

  err = analyze (preg);

  if (__glibc_unlikely (err != REG_NOERROR))

    goto re_compile_internal_free_return;

  /* If possible, do searching in single byte encoding to speed things up.  */

  if (dfa->is_utf8 && !(syntax & RE_ICASE) && preg->translate == NULL)

    optimize_utf8 (dfa);

  /* Then create the initial state of the dfa.  */

  err = create_initial_state (dfa);

  /* Release work areas.  */

  free_workarea_compile (preg);

  re_string_destruct (&regexp);

  if (__glibc_unlikely (err != REG_NOERROR))

    {

      lock_fini (dfa->lock);

      free_dfa_content (dfa);

      preg->buffer = NULL;

      preg->allocated = 0;

    }

  return err;

}

/* Initialize DFA.  We use the length of the regular expression PAT_LEN

   as the initial length of some arrays.  */

static reg_errcode_t

init_dfa (re_dfa_t *dfa, size_t pat_len)

{

  __re_size_t table_size;

#ifndef _LIBC

  const char *codeset_name;

#endif

  size_t max_i18n_object_size = MAX (sizeof (wchar_t), sizeof (wctype_t));

  size_t max_object_size =

    MAX (sizeof (struct re_state_table_entry),

   MAX (sizeof (re_token_t),

        MAX (sizeof (re_node_set),

       MAX (sizeof (regmatch_t),

      max_i18n_object_size))));

  memset (dfa, '\0', sizeof (re_dfa_t));

  /* Force allocation of str_tree_storage the first time.  */

  dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;

  /* Avoid overflows.  The extra "/ 2" is for the table_size doubling

     calculation below, and for similar doubling calculations

     elsewhere.  And it's <= rather than <, because some of the

     doubling calculations add 1 afterwards.  */

  if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / max_object_size) / 2

      <= pat_len))

    return REG_ESPACE;

  dfa->nodes_alloc = pat_len + 1;

  dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);

  /*  table_size = 2 ^ ceil(log pat_len) */

  for (table_size = 1; ; table_size <<= 1)

    if (table_size > pat_len)

      break;

  dfa->state_table = calloc (table_size, sizeof (struct re_state_table_entry));

  dfa->state_hash_mask = table_size - 1;

  dfa->mb_cur_max = MB_CUR_MAX;

#ifdef _LIBC

  if (dfa->mb_cur_max == 6

      && strcmp (_NL_CURRENT (LC_CTYPE, _NL_CTYPE_CODESET_NAME), "UTF-8") == 0)

    dfa->is_utf8 = 1;

  dfa->map_notascii = (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_MAP_TO_NONASCII)

           != 0);

#else

  codeset_name = nl_langinfo (CODESET);

  if ((codeset_name[0] == 'U' || codeset_name[0] == 'u')

      && (codeset_name[1] == 'T' || codeset_name[1] == 't')

      && (codeset_name[2] == 'F' || codeset_name[2] == 'f')

      && strcmp (codeset_name + 3 + (codeset_name[3] == '-'), "8") == 0)

    dfa->is_utf8 = 1;

  /* We check exhaustively in the loop below if this charset is a

     superset of ASCII.  */

  dfa->map_notascii = 0;

#endif

  if (dfa->mb_cur_max > 1)

    {

      if (dfa->is_utf8)

  dfa->sb_char = (re_bitset_ptr_t) utf8_sb_map;

      else

  {

    int i, j, ch;

    dfa->sb_char = (re_bitset_ptr_t) calloc (1, sizeof (bitset_t));

    if (__glibc_unlikely (dfa->sb_char == NULL))

      return REG_ESPACE;

    /* 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] |= (bitset_word_t) 1 << j;

#ifndef _LIBC

    if (isascii (ch) && wch != ch)

      dfa->map_notascii = 1;

#endif

        }

  }

    }

  if (__glibc_unlikely (dfa->nodes == NULL || dfa->state_table == NULL))

    return REG_ESPACE;

  return REG_NOERROR;

}

/* Initialize WORD_CHAR table, which indicate which character is

   "word".  In this case "word" means that it is the word construction

   character used by some operators like "\<", "\>", etc.  */

static void

init_word_char (re_dfa_t *dfa)

{

  int i = 0;

  int j;

  int ch = 0;

  dfa->word_ops_used = 1;

  if (__glibc_likely (dfa->map_notascii == 0))

    {

      bitset_word_t bits0 = 0x00000000;

      bitset_word_t bits1 = 0x03ff0000;

      bitset_word_t bits2 = 0x87fffffe;

      bitset_word_t bits3 = 0x07fffffe;

      if (BITSET_WORD_BITS == 64)

  {

    /* Pacify gcc -Woverflow on 32-bit platforms.  */

    dfa->word_char[0] = bits1 << 31 << 1 | bits0;

    dfa->word_char[1] = bits3 << 31 << 1 | bits2;

    i = 2;

  }

      else if (BITSET_WORD_BITS == 32)

  {

    dfa->word_char[0] = bits0;

    dfa->word_char[1] = bits1;

    dfa->word_char[2] = bits2;

    dfa->word_char[3] = bits3;

    i = 4;

  }

      else

        goto general_case;

      ch = 128;

      if (__glibc_likely (dfa->is_utf8))

  {

    memset (&dfa->word_char[i], '\0', (SBC_MAX - ch) / 8);

    return;

  }

    }

 general_case:

  for (; i < BITSET_WORDS; ++i)

    for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)

      if (isalnum (ch) || ch == '_')

  dfa->word_char[i] |= (bitset_word_t) 1 << j;

}