/* Extended regular expression matching and search library.

   Copyright (C) 2002-2025 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/>.  */

static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,

             Idx n);

static void match_ctx_clean (re_match_context_t *mctx);

static void match_ctx_free (re_match_context_t *cache);

static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,

            Idx str_idx, Idx from, Idx to);

static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx);

static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,

             Idx str_idx);

static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,

                Idx node, Idx str_idx);

static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,

         re_dfastate_t **limited_sts, Idx last_node,

         Idx last_str_idx);

static reg_errcode_t re_search_internal (const regex_t *preg,

           const char *string, Idx length,

           Idx start, Idx last_start, Idx stop,

           size_t nmatch, regmatch_t pmatch[],

           int eflags);

static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,

          const char *string1, Idx length1,

          const char *string2, Idx length2,

          Idx start, regoff_t range,

          struct re_registers *regs,

          Idx stop, bool ret_len);

static regoff_t re_search_stub (struct re_pattern_buffer *bufp,

        const char *string, Idx length, Idx start,

        regoff_t range, Idx stop,

        struct re_registers *regs,

        bool ret_len);

static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,

                              Idx nregs, int regs_allocated);

static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx);

static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,

         Idx *p_match_first);

static Idx check_halt_state_context (const re_match_context_t *mctx,

             const re_dfastate_t *state, Idx idx);

static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,

       regmatch_t *prev_idx_match, Idx cur_node,

       Idx cur_idx, Idx nmatch);

static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,

              Idx str_idx, Idx dest_node, Idx nregs,

              regmatch_t *regs, regmatch_t *prevregs,

              re_node_set *eps_via_nodes);

static reg_errcode_t set_regs (const regex_t *preg,

             const re_match_context_t *mctx,

             size_t nmatch, regmatch_t *pmatch,

             bool fl_backtrack);

static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs);

static int sift_states_iter_mb (const re_match_context_t *mctx,

        re_sift_context_t *sctx,

        Idx node_idx, Idx str_idx, Idx max_str_idx);

static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,

             re_sift_context_t *sctx);

static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,

            re_sift_context_t *sctx, Idx str_idx,

            re_node_set *cur_dest);

static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,

                re_sift_context_t *sctx,

                Idx str_idx,

                re_node_set *dest_nodes);

static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,

              re_node_set *dest_nodes,

              const re_node_set *candidates);

static bool check_dst_limits (const re_match_context_t *mctx,

            const re_node_set *limits,

            Idx dst_node, Idx dst_idx, Idx src_node,

            Idx src_idx);

static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,

          int boundaries, Idx subexp_idx,

          Idx from_node, Idx bkref_idx);

static int check_dst_limits_calc_pos (const re_match_context_t *mctx,

              Idx limit, Idx subexp_idx,

              Idx node, Idx str_idx,

              Idx bkref_idx);

static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,

            re_node_set *dest_nodes,

            const re_node_set *candidates,

            re_node_set *limits,

            struct re_backref_cache_entry *bkref_ents,

            Idx str_idx);

static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,

          re_sift_context_t *sctx,

          Idx str_idx, const re_node_set *candidates);

static reg_errcode_t merge_state_array (const re_dfa_t *dfa,

          re_dfastate_t **dst,

          re_dfastate_t **src, Idx num);

static re_dfastate_t *find_recover_state (reg_errcode_t *err,

           re_match_context_t *mctx);

static re_dfastate_t *transit_state (reg_errcode_t *err,

             re_match_context_t *mctx,

             re_dfastate_t *state);

static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,

              re_match_context_t *mctx,

              re_dfastate_t *next_state);

static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,

            re_node_set *cur_nodes,

            Idx str_idx);

#if 0

static re_dfastate_t *transit_state_sb (reg_errcode_t *err,

          re_match_context_t *mctx,

          re_dfastate_t *pstate);

#endif

static reg_errcode_t transit_state_mb (re_match_context_t *mctx,

               re_dfastate_t *pstate);

static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,

            const re_node_set *nodes);

static reg_errcode_t get_subexp (re_match_context_t *mctx,

         Idx bkref_node, Idx bkref_str_idx);

static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,

             const re_sub_match_top_t *sub_top,

             re_sub_match_last_t *sub_last,

             Idx bkref_node, Idx bkref_str);

static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,

           Idx subexp_idx, int type);

static reg_errcode_t check_arrival (re_match_context_t *mctx,

            state_array_t *path, Idx top_node,

            Idx top_str, Idx last_node, Idx last_str,

            int type);

static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,

               Idx str_idx,

               re_node_set *cur_nodes,

               re_node_set *next_nodes);

static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,

                 re_node_set *cur_nodes,

                 Idx ex_subexp, int type);

static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,

               re_node_set *dst_nodes,

               Idx target, Idx ex_subexp,

               int type);

static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,

           re_node_set *cur_nodes, Idx cur_str,

           Idx subexp_num, int type);

static bool build_trtable (const re_dfa_t *dfa, re_dfastate_t *state);

static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,

            const re_string_t *input, Idx idx);

#ifdef _LIBC

static unsigned int find_collation_sequence_value (const unsigned char *mbs,

               size_t name_len);

#endif

static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,

               const re_dfastate_t *state,

               re_node_set *states_node,

               bitset_t *states_ch);

static bool check_node_accept (const re_match_context_t *mctx,

             const re_token_t *node, Idx idx);

static reg_errcode_t extend_buffers (re_match_context_t *mctx, int min_len);

/* Entry point for POSIX code.  */

/* regexec searches for a given pattern, specified by PREG, in the

   string STRING.

   If NMATCH is zero or REG_NOSUB was set in the cflags argument to

   'regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at

   least NMATCH elements, and we set them to the offsets of the

   corresponding matched substrings.

   EFLAGS specifies "execution flags" which affect matching: if

   REG_NOTBOL is set, then ^ does not match at the beginning of the

   string; if REG_NOTEOL is set, then $ does not match at the end.

   Return 0 if a match is found, REG_NOMATCH if not, REG_BADPAT if

   EFLAGS is invalid.  */

int

regexec (const regex_t *__restrict preg, const char *__restrict string,

   size_t nmatch, regmatch_t pmatch[_REGEX_NELTS (nmatch)], int eflags)

{

  reg_errcode_t err;

  Idx start, length;

  re_dfa_t *dfa = preg->buffer;

  if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))

    return REG_BADPAT;

  if (eflags & REG_STARTEND)

    {

      start = pmatch[0].rm_so;

      length = pmatch[0].rm_eo;

    }

  else

    {

      start = 0;

      length = strlen (string);

    }

  lock_lock (dfa->lock);

  if (preg->no_sub)

    err = re_search_internal (preg, string, length, start, length,

            length, 0, NULL, eflags);

  else

    err = re_search_internal (preg, string, length, start, length,

            length, nmatch, pmatch, eflags);

  lock_unlock (dfa->lock);

  return err != REG_NOERROR;

}

#ifdef _LIBC

libc_hidden_def (__regexec)

# include <shlib-compat.h>

versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);

# if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)

__typeof__ (__regexec) __compat_regexec;

int

attribute_compat_text_section

__compat_regexec (const regex_t *__restrict preg,

      const char *__restrict string, size_t nmatch,

      regmatch_t pmatch[_REGEX_NELTS (nmatch)], int eflags)

{

  return regexec (preg, string, nmatch, pmatch,

      eflags & (REG_NOTBOL | REG_NOTEOL));

}

compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);

# endif

#endif

/* Entry points for GNU code.  */

/* re_match, re_search, re_match_2, re_search_2

   The former two functions operate on STRING with length LENGTH,

   while the later two operate on concatenation of STRING1 and STRING2

   with lengths LENGTH1 and LENGTH2, respectively.

   re_match() matches the compiled pattern in BUFP against the string,

   starting at index START.

   re_search() first tries matching at index START, then it tries to match

   starting from index START + 1, and so on.  The last start position tried

   is START + RANGE.  (Thus RANGE = 0 forces re_search to operate the same

   way as re_match().)

   The parameter STOP of re_{match,search}_2 specifies that no match exceeding

   the first STOP characters of the concatenation of the strings should be

   concerned.

   If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match

   and all groups is stored in REGS.  (For the "_2" variants, the offsets are

   computed relative to the concatenation, not relative to the individual

   strings.)

   On success, re_match* functions return the length of the match, re_search*

   return the position of the start of the match.  They return -1 on

   match failure, -2 on error.  */

regoff_t

re_match (struct re_pattern_buffer *bufp, const char *string, Idx length,

    Idx start, struct re_registers *regs)

{

  return re_search_stub (bufp, string, length, start, 0, length, regs, true);

}

#ifdef _LIBC

weak_alias (__re_match, re_match)

#endif

regoff_t

re_search (struct re_pattern_buffer *bufp, const char *string, Idx length,

     Idx start, regoff_t range, struct re_registers *regs)

{

  return re_search_stub (bufp, string, length, start, range, length, regs,

       false);

}

#ifdef _LIBC

weak_alias (__re_search, re_search)

#endif

regoff_t

re_match_2 (struct re_pattern_buffer *bufp, const char *string1, Idx length1,

      const char *string2, Idx length2, Idx start,

      struct re_registers *regs, Idx stop)

{

  return re_search_2_stub (bufp, string1, length1, string2, length2,

         start, 0, regs, stop, true);

}

#ifdef _LIBC

weak_alias (__re_match_2, re_match_2)

#endif

regoff_t

re_search_2 (struct re_pattern_buffer *bufp, const char *string1, Idx length1,

       const char *string2, Idx length2, Idx start, regoff_t range,

       struct re_registers *regs, Idx stop)

{

  return re_search_2_stub (bufp, string1, length1, string2, length2,

         start, range, regs, stop, false);

}

#ifdef _LIBC

weak_alias (__re_search_2, re_search_2)

#endif

static regoff_t

re_search_2_stub (struct re_pattern_buffer *bufp, const char *string1,

      Idx length1, const char *string2, Idx length2, Idx start,

      regoff_t range, struct re_registers *regs,

      Idx stop, bool ret_len)

{

  const char *str;

  regoff_t rval;

  Idx len;

  char *s = NULL;

  if (__glibc_unlikely ((length1 < 0 || length2 < 0 || stop < 0

       || ckd_add (&len, length1, length2))))

    return -2;

  /* Concatenate the strings.  */

  if (length2 > 0)

    if (length1 > 0)

      {

  s = re_malloc (char, len);

  if (__glibc_unlikely (s == NULL))

    return -2;

#ifdef _LIBC

  memcpy (__mempcpy (s, string1, length1), string2, length2);

#else

  memcpy (s, string1, length1);

  memcpy (s + length1, string2, length2);

#endif

  str = s;

      }

    else

      str = string2;

  else

    str = string1;

  rval = re_search_stub (bufp, str, len, start, range, stop, regs,

       ret_len);

  re_free (s);

  return rval;

}

/* The parameters have the same meaning as those of re_search.

   Additional parameters:

   If RET_LEN is true the length of the match is returned (re_match style);

   otherwise the position of the match is returned.  */

static regoff_t

re_search_stub (struct re_pattern_buffer *bufp, const char *string, Idx length,

    Idx start, regoff_t range, Idx stop, struct re_registers *regs,

    bool ret_len)

{

  reg_errcode_t result;

  regmatch_t *pmatch;

  Idx nregs;

  regoff_t rval;

  int eflags = 0;

  re_dfa_t *dfa = bufp->buffer;

  Idx last_start = start + range;

  /* Check for out-of-range.  */

  if (__glibc_unlikely (start < 0 || start > length))

    return -1;

  if (__glibc_unlikely (length < last_start

      || (0 <= range && last_start < start)))

    last_start = length;

  else if (__glibc_unlikely (last_start < 0

           || (range < 0 && start <= last_start)))

    last_start = 0;

  lock_lock (dfa->lock);

  eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;

  eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;

  /* Compile fastmap if we haven't yet.  */

  if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)

    re_compile_fastmap (bufp);

  if (__glibc_unlikely (bufp->no_sub))

    regs = NULL;

  /* We need at least 1 register.  */

  if (regs == NULL)

    nregs = 1;

  else if (__glibc_unlikely (bufp->regs_allocated == REGS_FIXED

           && regs->num_regs <= bufp->re_nsub))

    {

      nregs = regs->num_regs;

      if (__glibc_unlikely (nregs < 1))

  {

    /* Nothing can be copied to regs.  */

    regs = NULL;

    nregs = 1;

  }

    }

  else

    nregs = bufp->re_nsub + 1;

  pmatch = re_malloc (regmatch_t, nregs);

  if (__glibc_unlikely (pmatch == NULL))

    {

      rval = -2;

      goto out;

    }

  result = re_search_internal (bufp, string, length, start, last_start, stop,

             nregs, pmatch, eflags);

  rval = 0;

  /* I hope we needn't fill their regs with -1's when no match was found.  */

  if (result != REG_NOERROR)

    rval = result == REG_NOMATCH ? -1 : -2;

  else if (regs != NULL)

    {

      /* If caller wants register contents data back, copy them.  */

      bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,

             bufp->regs_allocated);

      if (__glibc_unlikely (bufp->regs_allocated == REGS_UNALLOCATED))

  rval = -2;

    }

  if (__glibc_likely (rval == 0))

    {

      if (ret_len)

  {

    DEBUG_ASSERT (pmatch[0].rm_so == start);

    rval = pmatch[0].rm_eo - start;

  }

      else

  rval = pmatch[0].rm_so;

    }

  re_free (pmatch);

 out:

  lock_unlock (dfa->lock);

  return rval;

}

static unsigned

re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,

        int regs_allocated)

{

  int rval = REGS_REALLOCATE;

  Idx i;

  Idx need_regs = nregs + 1;

  /* We need one extra element beyond 'num_regs' for the '-1' marker GNU code

     uses.  */

  /* Have the register data arrays been allocated?  */

  if (regs_allocated == REGS_UNALLOCATED)

    { /* No.  So allocate them with malloc.  */

      regs->start = re_malloc (regoff_t, need_regs);

      if (__glibc_unlikely (regs->start == NULL))

  return REGS_UNALLOCATED;

      regs->end = re_malloc (regoff_t, need_regs);

      if (__glibc_unlikely (regs->end == NULL))

  {

    re_free (regs->start);

    return REGS_UNALLOCATED;

  }

      regs->num_regs = need_regs;

    }

  else if (regs_allocated == REGS_REALLOCATE)

    { /* Yes.  If we need more elements than were already

   allocated, reallocate them.  If we need fewer, just

   leave it alone.  */

      if (__glibc_unlikely (need_regs > regs->num_regs))

  {

    regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);

    regoff_t *new_end;

    if (__glibc_unlikely (new_start == NULL))

      return REGS_UNALLOCATED;

    new_end = re_realloc (regs->end, regoff_t, need_regs);

    if (__glibc_unlikely (new_end == NULL))

      {

        re_free (new_start);

        return REGS_UNALLOCATED;

      }

    regs->start = new_start;

    regs->end = new_end;

    regs->num_regs = need_regs;

  }

    }

  else

    {

      DEBUG_ASSERT (regs_allocated == REGS_FIXED);

      /* This function may not be called with REGS_FIXED and nregs too big.  */

      DEBUG_ASSERT (nregs <= regs->num_regs);

      rval = REGS_FIXED;

    }

  /* Copy the regs.  */

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

    {

      regs->start[i] = pmatch[i].rm_so;

      regs->end[i] = pmatch[i].rm_eo;

    }

  for ( ; i < regs->num_regs; ++i)

    regs->start[i] = regs->end[i] = -1;

  return rval;

}

/* Set REGS to hold NUM_REGS registers, storing them in STARTS and

   ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use

   this memory for recording register information.  STARTS and ENDS

   must be allocated using the malloc library routine, and must each

   be at least NUM_REGS * sizeof (regoff_t) bytes long.

   If NUM_REGS == 0, then subsequent matches should allocate their own

   register data.

   Unless this function is called, the first search or match using

   PATTERN_BUFFER will allocate its own register data, without

   freeing the old data.  */

void

re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,

      __re_size_t num_regs, regoff_t *starts, regoff_t *ends)

{

  if (num_regs)

    {

      bufp->regs_allocated = REGS_REALLOCATE;

      regs->num_regs = num_regs;

      regs->start = starts;

      regs->end = ends;

    }

  else

    {

      bufp->regs_allocated = REGS_UNALLOCATED;

      regs->num_regs = 0;

      regs->start = regs->end = NULL;

    }

}

#ifdef _LIBC

weak_alias (__re_set_registers, re_set_registers)

#endif

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

   them unless specifically requested.  */

#if defined _REGEX_RE_COMP || defined _LIBC

int

# ifdef _LIBC

weak_function

# endif

re_exec (const char *s)

{

  return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);

}

#endif /* _REGEX_RE_COMP */

/* Internal entry point.  */

/* Searches for a compiled pattern PREG in the string STRING, whose

   length is LENGTH.  NMATCH, PMATCH, and EFLAGS have the same

   meaning as with regexec.  LAST_START is START + RANGE, where

   START and RANGE have the same meaning as with re_search.

   Return REG_NOERROR if we find a match, and REG_NOMATCH if not,

   otherwise return the error code.

   Note: We assume front end functions already check ranges.

   (0 <= LAST_START && LAST_START <= LENGTH)  */

static reg_errcode_t

__attribute_warn_unused_result__

re_search_internal (const regex_t *preg, const char *string, Idx length,

        Idx start, Idx last_start, Idx stop, size_t nmatch,

        regmatch_t pmatch[], int eflags)

{

  reg_errcode_t err;

  const re_dfa_t *dfa = preg->buffer;

  Idx left_lim, right_lim;

  int incr;

  bool fl_longest_match;

  int match_kind;

  Idx match_first;

  Idx match_last = -1;

  Idx extra_nmatch;

  bool sb;

  int ch;

  re_match_context_t mctx = { .dfa = dfa };

  char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate

        && start != last_start && !preg->can_be_null)

       ? preg->fastmap : NULL);

  RE_TRANSLATE_TYPE t = preg->translate;

  extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;

  nmatch -= extra_nmatch;

  /* Check if the DFA haven't been compiled.  */

  if (__glibc_unlikely (preg->used == 0 || dfa->init_state == NULL

      || dfa->init_state_word == NULL

      || dfa->init_state_nl == NULL

      || dfa->init_state_begbuf == NULL))

    return REG_NOMATCH;

  /* We assume front-end functions already check them.  */

  DEBUG_ASSERT (0 <= last_start && last_start <= length);

  /* If initial states with non-begbuf contexts have no elements,

     the regex must be anchored.  If preg->newline_anchor is set,

     we'll never use init_state_nl, so do not check it.  */

  if (dfa->init_state->nodes.nelem == 0

      && dfa->init_state_word->nodes.nelem == 0

      && (dfa->init_state_nl->nodes.nelem == 0

    || !preg->newline_anchor))

    {

      if (start != 0 && last_start != 0)

        return REG_NOMATCH;

      start = last_start = 0;

    }

  /* We must check the longest matching, if nmatch > 0.  */

  fl_longest_match = (nmatch != 0 || dfa->nbackref);

  err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,

          preg->translate, (preg->syntax & RE_ICASE) != 0,

          dfa);

  if (__glibc_unlikely (err != REG_NOERROR))

    goto free_return;

  mctx.input.stop = stop;

  mctx.input.raw_stop = stop;

  mctx.input.newline_anchor = preg->newline_anchor;

  err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);

  if (__glibc_unlikely (err != REG_NOERROR))

    goto free_return;

  /* We will log all the DFA states through which the dfa pass,

     if nmatch > 1, or this dfa has "multibyte node", which is a

     back-reference or a node which can accept multibyte character or

     multi character collating element.  */

  if (nmatch > 1 || dfa->has_mb_node)

    {

      /* Avoid overflow.  */

      if (__glibc_unlikely ((MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *))

           <= mctx.input.bufs_len)))

  {

    err = REG_ESPACE;

    goto free_return;

  }

      mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);

      if (__glibc_unlikely (mctx.state_log == NULL))

  {

    err = REG_ESPACE;

    goto free_return;

  }

    }

  match_first = start;

  mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF

         : CONTEXT_NEWLINE | CONTEXT_BEGBUF;

  /* Check incrementally whether the input string matches.  */

  incr = (last_start < start) ? -1 : 1;

  left_lim = (last_start < start) ? last_start : start;

  right_lim = (last_start < start) ? start : last_start;

  sb = dfa->mb_cur_max == 1;

  match_kind =

    (fastmap

     ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)

  | (start <= last_start ? 2 : 0)

  | (t != NULL ? 1 : 0))

     : 8);

  for (;; match_first += incr)

    {

      err = REG_NOMATCH;

      if (match_first < left_lim || right_lim < match_first)

  goto free_return;

      /* Advance as rapidly as possible through the string, until we

   find a plausible place to start matching.  This may be done

   with varying efficiency, so there are various possibilities:

   only the most common of them are specialized, in order to

   save on code size.  We use a switch statement for speed.  */

      switch (match_kind)

  {

  case 8:

    /* No fastmap.  */

    break;

  case 7:

    /* Fastmap with single-byte translation, match forward.  */

    while (__glibc_likely (match_first < right_lim)

     && !fastmap[t[(unsigned char) string[match_first]]])

      ++match_first;

    goto forward_match_found_start_or_reached_end;

  case 6:

    /* Fastmap without translation, match forward.  */

    while (__glibc_likely (match_first < right_lim)

     && !fastmap[(unsigned char) string[match_first]])

      ++match_first;

  forward_match_found_start_or_reached_end:

    if (__glibc_unlikely (match_first == right_lim))

      {

        ch = match_first >= length

           ? 0 : (unsigned char) string[match_first];

        if (!fastmap[t ? t[ch] : ch])

    goto free_return;

      }

    break;

  case 4:

  case 5:

    /* Fastmap without multi-byte translation, match backwards.  */

    while (match_first >= left_lim)

      {

        ch = match_first >= length

           ? 0 : (unsigned char) string[match_first];

        if (fastmap[t ? t[ch] : ch])

    break;

        --match_first;

      }

    if (match_first < left_lim)

      goto free_return;

    break;

  default:

    /* In this case, we can't determine easily the current byte,

       since it might be a component byte of a multibyte

       character.  Then we use the constructed buffer instead.  */

    for (;;)

      {

        /* If MATCH_FIRST is out of the valid range, reconstruct the

     buffers.  */

        __re_size_t offset = match_first - mctx.input.raw_mbs_idx;

        if (__glibc_unlikely (offset

            >= (__re_size_t) mctx.input.valid_raw_len))

    {

      err = re_string_reconstruct (&mctx.input, match_first,

                 eflags);

      if (__glibc_unlikely (err != REG_NOERROR))

        goto free_return;

      offset = match_first - mctx.input.raw_mbs_idx;

    }

        /* Use buffer byte if OFFSET is in buffer, otherwise '\0'.  */

        ch = (offset < mctx.input.valid_len

        ? re_string_byte_at (&mctx.input, offset) : 0);

        if (fastmap[ch])

    break;

        match_first += incr;

        if (match_first < left_lim || match_first > right_lim)

    {

      err = REG_NOMATCH;

      goto free_return;

    }

      }

    break;

  }

      /* Reconstruct the buffers so that the matcher can assume that

   the matching starts from the beginning of the buffer.  */

      err = re_string_reconstruct (&mctx.input, match_first, eflags);

      if (__glibc_unlikely (err != REG_NOERROR))

  goto free_return;

      /* Don't consider this char as a possible match start if it part,

         yet isn't the head, of a multibyte character.  */

      if (!sb && !re_string_first_byte (&mctx.input, 0))

  continue;

      /* It seems to be appropriate one, then use the matcher.  */

      /* We assume that the matching starts from 0.  */

      mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;

      match_last = check_matching (&mctx, fl_longest_match,

           start <= last_start ? &match_first : NULL);

      if (match_last != -1)

  {

    if (__glibc_unlikely (match_last == -2))

      {

        err = REG_ESPACE;

        goto free_return;

      }

    else

      {

        mctx.match_last = match_last;

        if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)

    {

      re_dfastate_t *pstate = mctx.state_log[match_last];

      mctx.last_node = check_halt_state_context (&mctx, pstate,

                   match_last);

    }

        if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)

      || dfa->nbackref)

    {

      err = prune_impossible_nodes (&mctx);

      if (err == REG_NOERROR)

        break;

      if (__glibc_unlikely (err != REG_NOMATCH))

        goto free_return;

      match_last = -1;

    }

        else

    break; /* We found a match.  */

      }

  }

      match_ctx_clean (&mctx);

    }

  DEBUG_ASSERT (match_last != -1);

  DEBUG_ASSERT (err == REG_NOERROR);

  /* Set pmatch[] if we need.  */

  if (nmatch > 0)

    {

      Idx reg_idx;

      /* Initialize registers.  */

      for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)

  pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;

      /* Set the points where matching start/end.  */

      pmatch[0].rm_so = 0;

      pmatch[0].rm_eo = mctx.match_last;

      /* FIXME: This function should fail if mctx.match_last exceeds

   the maximum possible regoff_t value.  We need a new error

   code REG_OVERFLOW.  */

      if (!preg->no_sub && nmatch > 1)

  {

    err = set_regs (preg, &mctx, nmatch, pmatch,

        dfa->has_plural_match && dfa->nbackref > 0);

    if (__glibc_unlikely (err != REG_NOERROR))

      goto free_return;

  }

      /* At last, add the offset to each register, since we slid

   the buffers so that we could assume that the matching starts

   from 0.  */

      for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)

  if (pmatch[reg_idx].rm_so != -1)

    {

      if (__glibc_unlikely (mctx.input.offsets_needed != 0))

        {

    pmatch[reg_idx].rm_so =

      (pmatch[reg_idx].rm_so == mctx.input.valid_len

       ? mctx.input.valid_raw_len

       : mctx.input.offsets[pmatch[reg_idx].rm_so]);

    pmatch[reg_idx].rm_eo =

      (pmatch[reg_idx].rm_eo == mctx.input.valid_len

       ? mctx.input.valid_raw_len

       : mctx.input.offsets[pmatch[reg_idx].rm_eo]);

        }

      pmatch[reg_idx].rm_so += match_first;

      pmatch[reg_idx].rm_eo += match_first;

    }

      for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)

  {

    pmatch[nmatch + reg_idx].rm_so = -1;

    pmatch[nmatch + reg_idx].rm_eo = -1;

  }

      if (dfa->subexp_map)

  for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)

    if (dfa->subexp_map[reg_idx] != reg_idx)

      {

        pmatch[reg_idx + 1].rm_so

    = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;

        pmatch[reg_idx + 1].rm_eo

    = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;

      }

    }

 free_return:

  re_free (mctx.state_log);

  if (dfa->nbackref)

    match_ctx_free (&mctx);

  re_string_destruct (&mctx.input);

  return err;

}

static reg_errcode_t

__attribute_warn_unused_result__

prune_impossible_nodes (re_match_context_t *mctx)

{

  const re_dfa_t *const dfa = mctx->dfa;

  Idx halt_node, match_last;

  reg_errcode_t ret;

  re_dfastate_t **sifted_states;

  re_dfastate_t **lim_states = NULL;

  re_sift_context_t sctx;

  DEBUG_ASSERT (mctx->state_log != NULL);

  match_last = mctx->match_last;

  halt_node = mctx->last_node;

  /* Avoid overflow.  */

  if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *))

      <= match_last))

    return REG_ESPACE;

  sifted_states = re_malloc (re_dfastate_t *, match_last + 1);

  if (__glibc_unlikely (sifted_states == NULL))

    {

      ret = REG_ESPACE;

      goto free_return;

    }

  if (dfa->nbackref)

    {