summaryrefslogtreecommitdiffstats
path: root/gl/regexec.c
diff options
context:
space:
mode:
Diffstat (limited to 'gl/regexec.c')
-rw-r--r--gl/regexec.c1097
1 files changed, 475 insertions, 622 deletions
diff --git a/gl/regexec.c b/gl/regexec.c
index d29d442b..6aeba3c0 100644
--- a/gl/regexec.c
+++ b/gl/regexec.c
@@ -1,206 +1,176 @@
1/* Extended regular expression matching and search library. 1/* Extended regular expression matching and search library.
2 Copyright (C) 2002-2013 Free Software Foundation, Inc. 2 Copyright (C) 2002-2021 Free Software Foundation, Inc.
3 This file is part of the GNU C Library. 3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>. 4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5 5
6 The GNU C Library is free software; you can redistribute it and/or 6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public 7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either 8 License as published by the Free Software Foundation; either
9 version 3 of the License, or (at your option) any later version. 9 version 2.1 of the License, or (at your option) any later version.
10 10
11 The GNU C Library is distributed in the hope that it will be useful, 11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details. 14 Lesser General Public License for more details.
15 15
16 You should have received a copy of the GNU General Public 16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see 17 License along with the GNU C Library; if not, see
18 <http://www.gnu.org/licenses/>. */ 18 <https://www.gnu.org/licenses/>. */
19 19
20static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags, 20static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
21 Idx n) internal_function; 21 Idx n);
22static void match_ctx_clean (re_match_context_t *mctx) internal_function; 22static void match_ctx_clean (re_match_context_t *mctx);
23static void match_ctx_free (re_match_context_t *cache) internal_function; 23static void match_ctx_free (re_match_context_t *cache);
24static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node, 24static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
25 Idx str_idx, Idx from, Idx to) 25 Idx str_idx, Idx from, Idx to);
26 internal_function; 26static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx);
27static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
28 internal_function;
29static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node, 27static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
30 Idx str_idx) internal_function; 28 Idx str_idx);
31static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop, 29static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
32 Idx node, Idx str_idx) 30 Idx node, Idx str_idx);
33 internal_function;
34static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts, 31static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
35 re_dfastate_t **limited_sts, Idx last_node, 32 re_dfastate_t **limited_sts, Idx last_node,
36 Idx last_str_idx) 33 Idx last_str_idx);
37 internal_function;
38static reg_errcode_t re_search_internal (const regex_t *preg, 34static reg_errcode_t re_search_internal (const regex_t *preg,
39 const char *string, Idx length, 35 const char *string, Idx length,
40 Idx start, Idx last_start, Idx stop, 36 Idx start, Idx last_start, Idx stop,
41 size_t nmatch, regmatch_t pmatch[], 37 size_t nmatch, regmatch_t pmatch[],
42 int eflags) internal_function; 38 int eflags);
43static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp, 39static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
44 const char *string1, Idx length1, 40 const char *string1, Idx length1,
45 const char *string2, Idx length2, 41 const char *string2, Idx length2,
46 Idx start, regoff_t range, 42 Idx start, regoff_t range,
47 struct re_registers *regs, 43 struct re_registers *regs,
48 Idx stop, bool ret_len) internal_function; 44 Idx stop, bool ret_len);
49static regoff_t re_search_stub (struct re_pattern_buffer *bufp, 45static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
50 const char *string, Idx length, Idx start, 46 const char *string, Idx length, Idx start,
51 regoff_t range, Idx stop, 47 regoff_t range, Idx stop,
52 struct re_registers *regs, 48 struct re_registers *regs,
53 bool ret_len) internal_function; 49 bool ret_len);
54static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, 50static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
55 Idx nregs, int regs_allocated) internal_function; 51 Idx nregs, int regs_allocated);
56static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx) 52static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx);
57 internal_function;
58static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match, 53static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
59 Idx *p_match_first) internal_function; 54 Idx *p_match_first);
60static Idx check_halt_state_context (const re_match_context_t *mctx, 55static Idx check_halt_state_context (const re_match_context_t *mctx,
61 const re_dfastate_t *state, Idx idx) 56 const re_dfastate_t *state, Idx idx);
62 internal_function;
63static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch, 57static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
64 regmatch_t *prev_idx_match, Idx cur_node, 58 regmatch_t *prev_idx_match, Idx cur_node,
65 Idx cur_idx, Idx nmatch) internal_function; 59 Idx cur_idx, Idx nmatch);
66static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs, 60static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
67 Idx str_idx, Idx dest_node, Idx nregs, 61 Idx str_idx, Idx dest_node, Idx nregs,
68 regmatch_t *regs, 62 regmatch_t *regs, regmatch_t *prevregs,
69 re_node_set *eps_via_nodes) 63 re_node_set *eps_via_nodes);
70 internal_function;
71static reg_errcode_t set_regs (const regex_t *preg, 64static reg_errcode_t set_regs (const regex_t *preg,
72 const re_match_context_t *mctx, 65 const re_match_context_t *mctx,
73 size_t nmatch, regmatch_t *pmatch, 66 size_t nmatch, regmatch_t *pmatch,
74 bool fl_backtrack) internal_function; 67 bool fl_backtrack);
75static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs) 68static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs);
76 internal_function;
77 69
78#ifdef RE_ENABLE_I18N 70#ifdef RE_ENABLE_I18N
79static int sift_states_iter_mb (const re_match_context_t *mctx, 71static int sift_states_iter_mb (const re_match_context_t *mctx,
80 re_sift_context_t *sctx, 72 re_sift_context_t *sctx,
81 Idx node_idx, Idx str_idx, Idx max_str_idx) 73 Idx node_idx, Idx str_idx, Idx max_str_idx);
82 internal_function;
83#endif /* RE_ENABLE_I18N */ 74#endif /* RE_ENABLE_I18N */
84static reg_errcode_t sift_states_backward (const re_match_context_t *mctx, 75static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
85 re_sift_context_t *sctx) 76 re_sift_context_t *sctx);
86 internal_function;
87static reg_errcode_t build_sifted_states (const re_match_context_t *mctx, 77static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
88 re_sift_context_t *sctx, Idx str_idx, 78 re_sift_context_t *sctx, Idx str_idx,
89 re_node_set *cur_dest) 79 re_node_set *cur_dest);
90 internal_function;
91static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx, 80static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
92 re_sift_context_t *sctx, 81 re_sift_context_t *sctx,
93 Idx str_idx, 82 Idx str_idx,
94 re_node_set *dest_nodes) 83 re_node_set *dest_nodes);
95 internal_function;
96static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa, 84static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
97 re_node_set *dest_nodes, 85 re_node_set *dest_nodes,
98 const re_node_set *candidates) 86 const re_node_set *candidates);
99 internal_function;
100static bool check_dst_limits (const re_match_context_t *mctx, 87static bool check_dst_limits (const re_match_context_t *mctx,
101 const re_node_set *limits, 88 const re_node_set *limits,
102 Idx dst_node, Idx dst_idx, Idx src_node, 89 Idx dst_node, Idx dst_idx, Idx src_node,
103 Idx src_idx) internal_function; 90 Idx src_idx);
104static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, 91static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
105 int boundaries, Idx subexp_idx, 92 int boundaries, Idx subexp_idx,
106 Idx from_node, Idx bkref_idx) 93 Idx from_node, Idx bkref_idx);
107 internal_function;
108static int check_dst_limits_calc_pos (const re_match_context_t *mctx, 94static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
109 Idx limit, Idx subexp_idx, 95 Idx limit, Idx subexp_idx,
110 Idx node, Idx str_idx, 96 Idx node, Idx str_idx,
111 Idx bkref_idx) internal_function; 97 Idx bkref_idx);
112static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa, 98static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
113 re_node_set *dest_nodes, 99 re_node_set *dest_nodes,
114 const re_node_set *candidates, 100 const re_node_set *candidates,
115 re_node_set *limits, 101 re_node_set *limits,
116 struct re_backref_cache_entry *bkref_ents, 102 struct re_backref_cache_entry *bkref_ents,
117 Idx str_idx) internal_function; 103 Idx str_idx);
118static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx, 104static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
119 re_sift_context_t *sctx, 105 re_sift_context_t *sctx,
120 Idx str_idx, const re_node_set *candidates) 106 Idx str_idx, const re_node_set *candidates);
121 internal_function;
122static reg_errcode_t merge_state_array (const re_dfa_t *dfa, 107static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
123 re_dfastate_t **dst, 108 re_dfastate_t **dst,
124 re_dfastate_t **src, Idx num) 109 re_dfastate_t **src, Idx num);
125 internal_function;
126static re_dfastate_t *find_recover_state (reg_errcode_t *err, 110static re_dfastate_t *find_recover_state (reg_errcode_t *err,
127 re_match_context_t *mctx) internal_function; 111 re_match_context_t *mctx);
128static re_dfastate_t *transit_state (reg_errcode_t *err, 112static re_dfastate_t *transit_state (reg_errcode_t *err,
129 re_match_context_t *mctx, 113 re_match_context_t *mctx,
130 re_dfastate_t *state) internal_function; 114 re_dfastate_t *state);
131static re_dfastate_t *merge_state_with_log (reg_errcode_t *err, 115static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
132 re_match_context_t *mctx, 116 re_match_context_t *mctx,
133 re_dfastate_t *next_state) 117 re_dfastate_t *next_state);
134 internal_function;
135static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx, 118static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
136 re_node_set *cur_nodes, 119 re_node_set *cur_nodes,
137 Idx str_idx) internal_function; 120 Idx str_idx);
138#if 0 121#if 0
139static re_dfastate_t *transit_state_sb (reg_errcode_t *err, 122static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
140 re_match_context_t *mctx, 123 re_match_context_t *mctx,
141 re_dfastate_t *pstate) 124 re_dfastate_t *pstate);
142 internal_function;
143#endif 125#endif
144#ifdef RE_ENABLE_I18N 126#ifdef RE_ENABLE_I18N
145static reg_errcode_t transit_state_mb (re_match_context_t *mctx, 127static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
146 re_dfastate_t *pstate) 128 re_dfastate_t *pstate);
147 internal_function;
148#endif /* RE_ENABLE_I18N */ 129#endif /* RE_ENABLE_I18N */
149static reg_errcode_t transit_state_bkref (re_match_context_t *mctx, 130static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
150 const re_node_set *nodes) 131 const re_node_set *nodes);
151 internal_function;
152static reg_errcode_t get_subexp (re_match_context_t *mctx, 132static reg_errcode_t get_subexp (re_match_context_t *mctx,
153 Idx bkref_node, Idx bkref_str_idx) 133 Idx bkref_node, Idx bkref_str_idx);
154 internal_function;
155static reg_errcode_t get_subexp_sub (re_match_context_t *mctx, 134static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
156 const re_sub_match_top_t *sub_top, 135 const re_sub_match_top_t *sub_top,
157 re_sub_match_last_t *sub_last, 136 re_sub_match_last_t *sub_last,
158 Idx bkref_node, Idx bkref_str) 137 Idx bkref_node, Idx bkref_str);
159 internal_function;
160static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes, 138static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
161 Idx subexp_idx, int type) internal_function; 139 Idx subexp_idx, int type);
162static reg_errcode_t check_arrival (re_match_context_t *mctx, 140static reg_errcode_t check_arrival (re_match_context_t *mctx,
163 state_array_t *path, Idx top_node, 141 state_array_t *path, Idx top_node,
164 Idx top_str, Idx last_node, Idx last_str, 142 Idx top_str, Idx last_node, Idx last_str,
165 int type) internal_function; 143 int type);
166static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx, 144static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
167 Idx str_idx, 145 Idx str_idx,
168 re_node_set *cur_nodes, 146 re_node_set *cur_nodes,
169 re_node_set *next_nodes) 147 re_node_set *next_nodes);
170 internal_function;
171static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa, 148static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
172 re_node_set *cur_nodes, 149 re_node_set *cur_nodes,
173 Idx ex_subexp, int type) 150 Idx ex_subexp, int type);
174 internal_function;
175static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa, 151static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
176 re_node_set *dst_nodes, 152 re_node_set *dst_nodes,
177 Idx target, Idx ex_subexp, 153 Idx target, Idx ex_subexp,
178 int type) internal_function; 154 int type);
179static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx, 155static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
180 re_node_set *cur_nodes, Idx cur_str, 156 re_node_set *cur_nodes, Idx cur_str,
181 Idx subexp_num, int type) 157 Idx subexp_num, int type);
182 internal_function; 158static bool build_trtable (const re_dfa_t *dfa, re_dfastate_t *state);
183static bool build_trtable (const re_dfa_t *dfa,
184 re_dfastate_t *state) internal_function;
185#ifdef RE_ENABLE_I18N 159#ifdef RE_ENABLE_I18N
186static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx, 160static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
187 const re_string_t *input, Idx idx) 161 const re_string_t *input, Idx idx);
188 internal_function;
189# ifdef _LIBC 162# ifdef _LIBC
190static unsigned int find_collation_sequence_value (const unsigned char *mbs, 163static unsigned int find_collation_sequence_value (const unsigned char *mbs,
191 size_t name_len) 164 size_t name_len);
192 internal_function;
193# endif /* _LIBC */ 165# endif /* _LIBC */
194#endif /* RE_ENABLE_I18N */ 166#endif /* RE_ENABLE_I18N */
195static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa, 167static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
196 const re_dfastate_t *state, 168 const re_dfastate_t *state,
197 re_node_set *states_node, 169 re_node_set *states_node,
198 bitset_t *states_ch) internal_function; 170 bitset_t *states_ch);
199static bool check_node_accept (const re_match_context_t *mctx, 171static bool check_node_accept (const re_match_context_t *mctx,
200 const re_token_t *node, Idx idx) 172 const re_token_t *node, Idx idx);
201 internal_function; 173static reg_errcode_t extend_buffers (re_match_context_t *mctx, int min_len);
202static reg_errcode_t extend_buffers (re_match_context_t *mctx, int min_len)
203 internal_function;
204 174
205/* Entry point for POSIX code. */ 175/* Entry point for POSIX code. */
206 176
@@ -216,15 +186,12 @@ static reg_errcode_t extend_buffers (re_match_context_t *mctx, int min_len)
216 REG_NOTBOL is set, then ^ does not match at the beginning of the 186 REG_NOTBOL is set, then ^ does not match at the beginning of the
217 string; if REG_NOTEOL is set, then $ does not match at the end. 187 string; if REG_NOTEOL is set, then $ does not match at the end.
218 188
219 We return 0 if we find a match and REG_NOMATCH if not. */ 189 Return 0 if a match is found, REG_NOMATCH if not, REG_BADPAT if
190 EFLAGS is invalid. */
220 191
221int 192int
222regexec (preg, string, nmatch, pmatch, eflags) 193regexec (const regex_t *__restrict preg, const char *__restrict string,
223 const regex_t *_Restrict_ preg; 194 size_t nmatch, regmatch_t pmatch[_REGEX_NELTS (nmatch)], int eflags)
224 const char *_Restrict_ string;
225 size_t nmatch;
226 regmatch_t pmatch[_Restrict_arr_];
227 int eflags;
228{ 195{
229 reg_errcode_t err; 196 reg_errcode_t err;
230 Idx start, length; 197 Idx start, length;
@@ -256,6 +223,8 @@ regexec (preg, string, nmatch, pmatch, eflags)
256} 223}
257 224
258#ifdef _LIBC 225#ifdef _LIBC
226libc_hidden_def (__regexec)
227
259# include <shlib-compat.h> 228# include <shlib-compat.h>
260versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4); 229versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
261 230
@@ -264,9 +233,9 @@ __typeof__ (__regexec) __compat_regexec;
264 233
265int 234int
266attribute_compat_text_section 235attribute_compat_text_section
267__compat_regexec (const regex_t *_Restrict_ preg, 236__compat_regexec (const regex_t *__restrict preg,
268 const char *_Restrict_ string, size_t nmatch, 237 const char *__restrict string, size_t nmatch,
269 regmatch_t pmatch[], int eflags) 238 regmatch_t pmatch[_REGEX_NELTS (nmatch)], int eflags)
270{ 239{
271 return regexec (preg, string, nmatch, pmatch, 240 return regexec (preg, string, nmatch, pmatch,
272 eflags & (REG_NOTBOL | REG_NOTEOL)); 241 eflags & (REG_NOTBOL | REG_NOTEOL));
@@ -301,15 +270,12 @@ compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
301 strings.) 270 strings.)
302 271
303 On success, re_match* functions return the length of the match, re_search* 272 On success, re_match* functions return the length of the match, re_search*
304 return the position of the start of the match. Return value -1 means no 273 return the position of the start of the match. They return -1 on
305 match was found and -2 indicates an internal error. */ 274 match failure, -2 on error. */
306 275
307regoff_t 276regoff_t
308re_match (bufp, string, length, start, regs) 277re_match (struct re_pattern_buffer *bufp, const char *string, Idx length,
309 struct re_pattern_buffer *bufp; 278 Idx start, struct re_registers *regs)
310 const char *string;
311 Idx length, start;
312 struct re_registers *regs;
313{ 279{
314 return re_search_stub (bufp, string, length, start, 0, length, regs, true); 280 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
315} 281}
@@ -318,12 +284,8 @@ weak_alias (__re_match, re_match)
318#endif 284#endif
319 285
320regoff_t 286regoff_t
321re_search (bufp, string, length, start, range, regs) 287re_search (struct re_pattern_buffer *bufp, const char *string, Idx length,
322 struct re_pattern_buffer *bufp; 288 Idx start, regoff_t range, struct re_registers *regs)
323 const char *string;
324 Idx length, start;
325 regoff_t range;
326 struct re_registers *regs;
327{ 289{
328 return re_search_stub (bufp, string, length, start, range, length, regs, 290 return re_search_stub (bufp, string, length, start, range, length, regs,
329 false); 291 false);
@@ -333,11 +295,9 @@ weak_alias (__re_search, re_search)
333#endif 295#endif
334 296
335regoff_t 297regoff_t
336re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop) 298re_match_2 (struct re_pattern_buffer *bufp, const char *string1, Idx length1,
337 struct re_pattern_buffer *bufp; 299 const char *string2, Idx length2, Idx start,
338 const char *string1, *string2; 300 struct re_registers *regs, Idx stop)
339 Idx length1, length2, start, stop;
340 struct re_registers *regs;
341{ 301{
342 return re_search_2_stub (bufp, string1, length1, string2, length2, 302 return re_search_2_stub (bufp, string1, length1, string2, length2,
343 start, 0, regs, stop, true); 303 start, 0, regs, stop, true);
@@ -347,12 +307,9 @@ weak_alias (__re_match_2, re_match_2)
347#endif 307#endif
348 308
349regoff_t 309regoff_t
350re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop) 310re_search_2 (struct re_pattern_buffer *bufp, const char *string1, Idx length1,
351 struct re_pattern_buffer *bufp; 311 const char *string2, Idx length2, Idx start, regoff_t range,
352 const char *string1, *string2; 312 struct re_registers *regs, Idx stop)
353 Idx length1, length2, start, stop;
354 regoff_t range;
355 struct re_registers *regs;
356{ 313{
357 return re_search_2_stub (bufp, string1, length1, string2, length2, 314 return re_search_2_stub (bufp, string1, length1, string2, length2,
358 start, range, regs, stop, false); 315 start, range, regs, stop, false);
@@ -362,18 +319,18 @@ weak_alias (__re_search_2, re_search_2)
362#endif 319#endif
363 320
364static regoff_t 321static regoff_t
365re_search_2_stub (struct re_pattern_buffer *bufp, 322re_search_2_stub (struct re_pattern_buffer *bufp, const char *string1,
366 const char *string1, Idx length1, 323 Idx length1, const char *string2, Idx length2, Idx start,
367 const char *string2, Idx length2, 324 regoff_t range, struct re_registers *regs,
368 Idx start, regoff_t range, struct re_registers *regs,
369 Idx stop, bool ret_len) 325 Idx stop, bool ret_len)
370{ 326{
371 const char *str; 327 const char *str;
372 regoff_t rval; 328 regoff_t rval;
373 Idx len = length1 + length2; 329 Idx len;
374 char *s = NULL; 330 char *s = NULL;
375 331
376 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0)) 332 if (__glibc_unlikely ((length1 < 0 || length2 < 0 || stop < 0
333 || INT_ADD_WRAPV (length1, length2, &len))))
377 return -2; 334 return -2;
378 335
379 /* Concatenate the strings. */ 336 /* Concatenate the strings. */
@@ -382,7 +339,7 @@ re_search_2_stub (struct re_pattern_buffer *bufp,
382 { 339 {
383 s = re_malloc (char, len); 340 s = re_malloc (char, len);
384 341
385 if (BE (s == NULL, 0)) 342 if (__glibc_unlikely (s == NULL))
386 return -2; 343 return -2;
387#ifdef _LIBC 344#ifdef _LIBC
388 memcpy (__mempcpy (s, string1, length1), string2, length2); 345 memcpy (__mempcpy (s, string1, length1), string2, length2);
@@ -409,8 +366,7 @@ re_search_2_stub (struct re_pattern_buffer *bufp,
409 otherwise the position of the match is returned. */ 366 otherwise the position of the match is returned. */
410 367
411static regoff_t 368static regoff_t
412re_search_stub (struct re_pattern_buffer *bufp, 369re_search_stub (struct re_pattern_buffer *bufp, const char *string, Idx length,
413 const char *string, Idx length,
414 Idx start, regoff_t range, Idx stop, struct re_registers *regs, 370 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
415 bool ret_len) 371 bool ret_len)
416{ 372{
@@ -423,11 +379,13 @@ re_search_stub (struct re_pattern_buffer *bufp,
423 Idx last_start = start + range; 379 Idx last_start = start + range;
424 380
425 /* Check for out-of-range. */ 381 /* Check for out-of-range. */
426 if (BE (start < 0 || start > length, 0)) 382 if (__glibc_unlikely (start < 0 || start > length))
427 return -1; 383 return -1;
428 if (BE (length < last_start || (0 <= range && last_start < start), 0)) 384 if (__glibc_unlikely (length < last_start
385 || (0 <= range && last_start < start)))
429 last_start = length; 386 last_start = length;
430 else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0)) 387 else if (__glibc_unlikely (last_start < 0
388 || (range < 0 && start <= last_start)))
431 last_start = 0; 389 last_start = 0;
432 390
433 lock_lock (dfa->lock); 391 lock_lock (dfa->lock);
@@ -439,17 +397,17 @@ re_search_stub (struct re_pattern_buffer *bufp,
439 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate) 397 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
440 re_compile_fastmap (bufp); 398 re_compile_fastmap (bufp);
441 399
442 if (BE (bufp->no_sub, 0)) 400 if (__glibc_unlikely (bufp->no_sub))
443 regs = NULL; 401 regs = NULL;
444 402
445 /* We need at least 1 register. */ 403 /* We need at least 1 register. */
446 if (regs == NULL) 404 if (regs == NULL)
447 nregs = 1; 405 nregs = 1;
448 else if (BE (bufp->regs_allocated == REGS_FIXED 406 else if (__glibc_unlikely (bufp->regs_allocated == REGS_FIXED
449 && regs->num_regs <= bufp->re_nsub, 0)) 407 && regs->num_regs <= bufp->re_nsub))
450 { 408 {
451 nregs = regs->num_regs; 409 nregs = regs->num_regs;
452 if (BE (nregs < 1, 0)) 410 if (__glibc_unlikely (nregs < 1))
453 { 411 {
454 /* Nothing can be copied to regs. */ 412 /* Nothing can be copied to regs. */
455 regs = NULL; 413 regs = NULL;
@@ -459,7 +417,7 @@ re_search_stub (struct re_pattern_buffer *bufp,
459 else 417 else
460 nregs = bufp->re_nsub + 1; 418 nregs = bufp->re_nsub + 1;
461 pmatch = re_malloc (regmatch_t, nregs); 419 pmatch = re_malloc (regmatch_t, nregs);
462 if (BE (pmatch == NULL, 0)) 420 if (__glibc_unlikely (pmatch == NULL))
463 { 421 {
464 rval = -2; 422 rval = -2;
465 goto out; 423 goto out;
@@ -478,15 +436,15 @@ re_search_stub (struct re_pattern_buffer *bufp,
478 /* If caller wants register contents data back, copy them. */ 436 /* If caller wants register contents data back, copy them. */
479 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs, 437 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
480 bufp->regs_allocated); 438 bufp->regs_allocated);
481 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0)) 439 if (__glibc_unlikely (bufp->regs_allocated == REGS_UNALLOCATED))
482 rval = -2; 440 rval = -2;
483 } 441 }
484 442
485 if (BE (rval == 0, 1)) 443 if (__glibc_likely (rval == 0))
486 { 444 {
487 if (ret_len) 445 if (ret_len)
488 { 446 {
489 assert (pmatch[0].rm_so == start); 447 DEBUG_ASSERT (pmatch[0].rm_so == start);
490 rval = pmatch[0].rm_eo - start; 448 rval = pmatch[0].rm_eo - start;
491 } 449 }
492 else 450 else
@@ -512,10 +470,10 @@ re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
512 if (regs_allocated == REGS_UNALLOCATED) 470 if (regs_allocated == REGS_UNALLOCATED)
513 { /* No. So allocate them with malloc. */ 471 { /* No. So allocate them with malloc. */
514 regs->start = re_malloc (regoff_t, need_regs); 472 regs->start = re_malloc (regoff_t, need_regs);
515 if (BE (regs->start == NULL, 0)) 473 if (__glibc_unlikely (regs->start == NULL))
516 return REGS_UNALLOCATED; 474 return REGS_UNALLOCATED;
517 regs->end = re_malloc (regoff_t, need_regs); 475 regs->end = re_malloc (regoff_t, need_regs);
518 if (BE (regs->end == NULL, 0)) 476 if (__glibc_unlikely (regs->end == NULL))
519 { 477 {
520 re_free (regs->start); 478 re_free (regs->start);
521 return REGS_UNALLOCATED; 479 return REGS_UNALLOCATED;
@@ -526,14 +484,14 @@ re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
526 { /* Yes. If we need more elements than were already 484 { /* Yes. If we need more elements than were already
527 allocated, reallocate them. If we need fewer, just 485 allocated, reallocate them. If we need fewer, just
528 leave it alone. */ 486 leave it alone. */
529 if (BE (need_regs > regs->num_regs, 0)) 487 if (__glibc_unlikely (need_regs > regs->num_regs))
530 { 488 {
531 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs); 489 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
532 regoff_t *new_end; 490 regoff_t *new_end;
533 if (BE (new_start == NULL, 0)) 491 if (__glibc_unlikely (new_start == NULL))
534 return REGS_UNALLOCATED; 492 return REGS_UNALLOCATED;
535 new_end = re_realloc (regs->end, regoff_t, need_regs); 493 new_end = re_realloc (regs->end, regoff_t, need_regs);
536 if (BE (new_end == NULL, 0)) 494 if (__glibc_unlikely (new_end == NULL))
537 { 495 {
538 re_free (new_start); 496 re_free (new_start);
539 return REGS_UNALLOCATED; 497 return REGS_UNALLOCATED;
@@ -545,9 +503,9 @@ re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
545 } 503 }
546 else 504 else
547 { 505 {
548 assert (regs_allocated == REGS_FIXED); 506 DEBUG_ASSERT (regs_allocated == REGS_FIXED);
549 /* This function may not be called with REGS_FIXED and nregs too big. */ 507 /* This function may not be called with REGS_FIXED and nregs too big. */
550 assert (regs->num_regs >= nregs); 508 DEBUG_ASSERT (nregs <= regs->num_regs);
551 rval = REGS_FIXED; 509 rval = REGS_FIXED;
552 } 510 }
553 511
@@ -577,11 +535,8 @@ re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
577 freeing the old data. */ 535 freeing the old data. */
578 536
579void 537void
580re_set_registers (bufp, regs, num_regs, starts, ends) 538re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,
581 struct re_pattern_buffer *bufp; 539 __re_size_t num_regs, regoff_t *starts, regoff_t *ends)
582 struct re_registers *regs;
583 __re_size_t num_regs;
584 regoff_t *starts, *ends;
585{ 540{
586 if (num_regs) 541 if (num_regs)
587 { 542 {
@@ -609,8 +564,7 @@ int
609# ifdef _LIBC 564# ifdef _LIBC
610weak_function 565weak_function
611# endif 566# endif
612re_exec (s) 567re_exec (const char *s)
613 const char *s;
614{ 568{
615 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0); 569 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
616} 570}
@@ -629,11 +583,9 @@ re_exec (s)
629 583
630static reg_errcode_t 584static reg_errcode_t
631__attribute_warn_unused_result__ 585__attribute_warn_unused_result__
632re_search_internal (const regex_t *preg, 586re_search_internal (const regex_t *preg, const char *string, Idx length,
633 const char *string, Idx length, 587 Idx start, Idx last_start, Idx stop, size_t nmatch,
634 Idx start, Idx last_start, Idx stop, 588 regmatch_t pmatch[], int eflags)
635 size_t nmatch, regmatch_t pmatch[],
636 int eflags)
637{ 589{
638 reg_errcode_t err; 590 reg_errcode_t err;
639 const re_dfa_t *dfa = preg->buffer; 591 const re_dfa_t *dfa = preg->buffer;
@@ -642,38 +594,28 @@ re_search_internal (const regex_t *preg,
642 bool fl_longest_match; 594 bool fl_longest_match;
643 int match_kind; 595 int match_kind;
644 Idx match_first; 596 Idx match_first;
645 Idx match_last = REG_MISSING; 597 Idx match_last = -1;
646 Idx extra_nmatch; 598 Idx extra_nmatch;
647 bool sb; 599 bool sb;
648 int ch; 600 int ch;
649#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
650 re_match_context_t mctx = { .dfa = dfa }; 601 re_match_context_t mctx = { .dfa = dfa };
651#else
652 re_match_context_t mctx;
653#endif
654 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate 602 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
655 && start != last_start && !preg->can_be_null) 603 && start != last_start && !preg->can_be_null)
656 ? preg->fastmap : NULL); 604 ? preg->fastmap : NULL);
657 RE_TRANSLATE_TYPE t = preg->translate; 605 RE_TRANSLATE_TYPE t = preg->translate;
658 606
659#if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
660 memset (&mctx, '\0', sizeof (re_match_context_t));
661 mctx.dfa = dfa;
662#endif
663
664 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0; 607 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
665 nmatch -= extra_nmatch; 608 nmatch -= extra_nmatch;
666 609
667 /* Check if the DFA haven't been compiled. */ 610 /* Check if the DFA haven't been compiled. */
668 if (BE (preg->used == 0 || dfa->init_state == NULL 611 if (__glibc_unlikely (preg->used == 0 || dfa->init_state == NULL
669 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL 612 || dfa->init_state_word == NULL
670 || dfa->init_state_begbuf == NULL, 0)) 613 || dfa->init_state_nl == NULL
614 || dfa->init_state_begbuf == NULL))
671 return REG_NOMATCH; 615 return REG_NOMATCH;
672 616
673#ifdef DEBUG
674 /* We assume front-end functions already check them. */ 617 /* We assume front-end functions already check them. */
675 assert (0 <= last_start && last_start <= length); 618 DEBUG_ASSERT (0 <= last_start && last_start <= length);
676#endif
677 619
678 /* If initial states with non-begbuf contexts have no elements, 620 /* If initial states with non-begbuf contexts have no elements,
679 the regex must be anchored. If preg->newline_anchor is set, 621 the regex must be anchored. If preg->newline_anchor is set,
@@ -694,14 +636,14 @@ re_search_internal (const regex_t *preg,
694 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1, 636 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
695 preg->translate, (preg->syntax & RE_ICASE) != 0, 637 preg->translate, (preg->syntax & RE_ICASE) != 0,
696 dfa); 638 dfa);
697 if (BE (err != REG_NOERROR, 0)) 639 if (__glibc_unlikely (err != REG_NOERROR))
698 goto free_return; 640 goto free_return;
699 mctx.input.stop = stop; 641 mctx.input.stop = stop;
700 mctx.input.raw_stop = stop; 642 mctx.input.raw_stop = stop;
701 mctx.input.newline_anchor = preg->newline_anchor; 643 mctx.input.newline_anchor = preg->newline_anchor;
702 644
703 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2); 645 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
704 if (BE (err != REG_NOERROR, 0)) 646 if (__glibc_unlikely (err != REG_NOERROR))
705 goto free_return; 647 goto free_return;
706 648
707 /* We will log all the DFA states through which the dfa pass, 649 /* We will log all the DFA states through which the dfa pass,
@@ -711,22 +653,20 @@ re_search_internal (const regex_t *preg,
711 if (nmatch > 1 || dfa->has_mb_node) 653 if (nmatch > 1 || dfa->has_mb_node)
712 { 654 {
713 /* Avoid overflow. */ 655 /* Avoid overflow. */
714 if (BE ((MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) 656 if (__glibc_unlikely ((MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *))
715 <= mctx.input.bufs_len), 0)) 657 <= mctx.input.bufs_len)))
716 { 658 {
717 err = REG_ESPACE; 659 err = REG_ESPACE;
718 goto free_return; 660 goto free_return;
719 } 661 }
720 662
721 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1); 663 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
722 if (BE (mctx.state_log == NULL, 0)) 664 if (__glibc_unlikely (mctx.state_log == NULL))
723 { 665 {
724 err = REG_ESPACE; 666 err = REG_ESPACE;
725 goto free_return; 667 goto free_return;
726 } 668 }
727 } 669 }
728 else
729 mctx.state_log = NULL;
730 670
731 match_first = start; 671 match_first = start;
732 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF 672 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
@@ -763,19 +703,19 @@ re_search_internal (const regex_t *preg,
763 703
764 case 7: 704 case 7:
765 /* Fastmap with single-byte translation, match forward. */ 705 /* Fastmap with single-byte translation, match forward. */
766 while (BE (match_first < right_lim, 1) 706 while (__glibc_likely (match_first < right_lim)
767 && !fastmap[t[(unsigned char) string[match_first]]]) 707 && !fastmap[t[(unsigned char) string[match_first]]])
768 ++match_first; 708 ++match_first;
769 goto forward_match_found_start_or_reached_end; 709 goto forward_match_found_start_or_reached_end;
770 710
771 case 6: 711 case 6:
772 /* Fastmap without translation, match forward. */ 712 /* Fastmap without translation, match forward. */
773 while (BE (match_first < right_lim, 1) 713 while (__glibc_likely (match_first < right_lim)
774 && !fastmap[(unsigned char) string[match_first]]) 714 && !fastmap[(unsigned char) string[match_first]])
775 ++match_first; 715 ++match_first;
776 716
777 forward_match_found_start_or_reached_end: 717 forward_match_found_start_or_reached_end:
778 if (BE (match_first == right_lim, 0)) 718 if (__glibc_unlikely (match_first == right_lim))
779 { 719 {
780 ch = match_first >= length 720 ch = match_first >= length
781 ? 0 : (unsigned char) string[match_first]; 721 ? 0 : (unsigned char) string[match_first];
@@ -808,19 +748,19 @@ re_search_internal (const regex_t *preg,
808 /* If MATCH_FIRST is out of the valid range, reconstruct the 748 /* If MATCH_FIRST is out of the valid range, reconstruct the
809 buffers. */ 749 buffers. */
810 __re_size_t offset = match_first - mctx.input.raw_mbs_idx; 750 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
811 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0)) 751 if (__glibc_unlikely (offset
752 >= (__re_size_t) mctx.input.valid_raw_len))
812 { 753 {
813 err = re_string_reconstruct (&mctx.input, match_first, 754 err = re_string_reconstruct (&mctx.input, match_first,
814 eflags); 755 eflags);
815 if (BE (err != REG_NOERROR, 0)) 756 if (__glibc_unlikely (err != REG_NOERROR))
816 goto free_return; 757 goto free_return;
817 758
818 offset = match_first - mctx.input.raw_mbs_idx; 759 offset = match_first - mctx.input.raw_mbs_idx;
819 } 760 }
820 /* If MATCH_FIRST is out of the buffer, leave it as '\0'. 761 /* Use buffer byte if OFFSET is in buffer, otherwise '\0'. */
821 Note that MATCH_FIRST must not be smaller than 0. */ 762 ch = (offset < mctx.input.valid_len
822 ch = (match_first >= length 763 ? re_string_byte_at (&mctx.input, offset) : 0);
823 ? 0 : re_string_byte_at (&mctx.input, offset));
824 if (fastmap[ch]) 764 if (fastmap[ch])
825 break; 765 break;
826 match_first += incr; 766 match_first += incr;
@@ -836,7 +776,7 @@ re_search_internal (const regex_t *preg,
836 /* Reconstruct the buffers so that the matcher can assume that 776 /* Reconstruct the buffers so that the matcher can assume that
837 the matching starts from the beginning of the buffer. */ 777 the matching starts from the beginning of the buffer. */
838 err = re_string_reconstruct (&mctx.input, match_first, eflags); 778 err = re_string_reconstruct (&mctx.input, match_first, eflags);
839 if (BE (err != REG_NOERROR, 0)) 779 if (__glibc_unlikely (err != REG_NOERROR))
840 goto free_return; 780 goto free_return;
841 781
842#ifdef RE_ENABLE_I18N 782#ifdef RE_ENABLE_I18N
@@ -851,9 +791,9 @@ re_search_internal (const regex_t *preg,
851 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0; 791 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
852 match_last = check_matching (&mctx, fl_longest_match, 792 match_last = check_matching (&mctx, fl_longest_match,
853 start <= last_start ? &match_first : NULL); 793 start <= last_start ? &match_first : NULL);
854 if (match_last != REG_MISSING) 794 if (match_last != -1)
855 { 795 {
856 if (BE (match_last == REG_ERROR, 0)) 796 if (__glibc_unlikely (match_last == -2))
857 { 797 {
858 err = REG_ESPACE; 798 err = REG_ESPACE;
859 goto free_return; 799 goto free_return;
@@ -873,9 +813,9 @@ re_search_internal (const regex_t *preg,
873 err = prune_impossible_nodes (&mctx); 813 err = prune_impossible_nodes (&mctx);
874 if (err == REG_NOERROR) 814 if (err == REG_NOERROR)
875 break; 815 break;
876 if (BE (err != REG_NOMATCH, 0)) 816 if (__glibc_unlikely (err != REG_NOMATCH))
877 goto free_return; 817 goto free_return;
878 match_last = REG_MISSING; 818 match_last = -1;
879 } 819 }
880 else 820 else
881 break; /* We found a match. */ 821 break; /* We found a match. */
@@ -885,10 +825,8 @@ re_search_internal (const regex_t *preg,
885 match_ctx_clean (&mctx); 825 match_ctx_clean (&mctx);
886 } 826 }
887 827
888#ifdef DEBUG 828 DEBUG_ASSERT (match_last != -1);
889 assert (match_last != REG_MISSING); 829 DEBUG_ASSERT (err == REG_NOERROR);
890 assert (err == REG_NOERROR);
891#endif
892 830
893 /* Set pmatch[] if we need. */ 831 /* Set pmatch[] if we need. */
894 if (nmatch > 0) 832 if (nmatch > 0)
@@ -910,7 +848,7 @@ re_search_internal (const regex_t *preg,
910 { 848 {
911 err = set_regs (preg, &mctx, nmatch, pmatch, 849 err = set_regs (preg, &mctx, nmatch, pmatch,
912 dfa->has_plural_match && dfa->nbackref > 0); 850 dfa->has_plural_match && dfa->nbackref > 0);
913 if (BE (err != REG_NOERROR, 0)) 851 if (__glibc_unlikely (err != REG_NOERROR))
914 goto free_return; 852 goto free_return;
915 } 853 }
916 854
@@ -921,7 +859,7 @@ re_search_internal (const regex_t *preg,
921 if (pmatch[reg_idx].rm_so != -1) 859 if (pmatch[reg_idx].rm_so != -1)
922 { 860 {
923#ifdef RE_ENABLE_I18N 861#ifdef RE_ENABLE_I18N
924 if (BE (mctx.input.offsets_needed != 0, 0)) 862 if (__glibc_unlikely (mctx.input.offsets_needed != 0))
925 { 863 {
926 pmatch[reg_idx].rm_so = 864 pmatch[reg_idx].rm_so =
927 (pmatch[reg_idx].rm_so == mctx.input.valid_len 865 (pmatch[reg_idx].rm_so == mctx.input.valid_len
@@ -933,7 +871,7 @@ re_search_internal (const regex_t *preg,
933 : mctx.input.offsets[pmatch[reg_idx].rm_eo]); 871 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
934 } 872 }
935#else 873#else
936 assert (mctx.input.offsets_needed == 0); 874 DEBUG_ASSERT (mctx.input.offsets_needed == 0);
937#endif 875#endif
938 pmatch[reg_idx].rm_so += match_first; 876 pmatch[reg_idx].rm_so += match_first;
939 pmatch[reg_idx].rm_eo += match_first; 877 pmatch[reg_idx].rm_eo += match_first;
@@ -973,18 +911,17 @@ prune_impossible_nodes (re_match_context_t *mctx)
973 re_dfastate_t **sifted_states; 911 re_dfastate_t **sifted_states;
974 re_dfastate_t **lim_states = NULL; 912 re_dfastate_t **lim_states = NULL;
975 re_sift_context_t sctx; 913 re_sift_context_t sctx;
976#ifdef DEBUG 914 DEBUG_ASSERT (mctx->state_log != NULL);
977 assert (mctx->state_log != NULL);
978#endif
979 match_last = mctx->match_last; 915 match_last = mctx->match_last;
980 halt_node = mctx->last_node; 916 halt_node = mctx->last_node;
981 917
982 /* Avoid overflow. */ 918 /* Avoid overflow. */
983 if (BE (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) <= match_last, 0)) 919 if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *))
920 <= match_last))
984 return REG_ESPACE; 921 return REG_ESPACE;
985 922
986 sifted_states = re_malloc (re_dfastate_t *, match_last + 1); 923 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
987 if (BE (sifted_states == NULL, 0)) 924 if (__glibc_unlikely (sifted_states == NULL))
988 { 925 {
989 ret = REG_ESPACE; 926 ret = REG_ESPACE;
990 goto free_return; 927 goto free_return;
@@ -992,7 +929,7 @@ prune_impossible_nodes (re_match_context_t *mctx)
992 if (dfa->nbackref) 929 if (dfa->nbackref)
993 { 930 {
994 lim_states = re_malloc (re_dfastate_t *, match_last + 1); 931 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
995 if (BE (lim_states == NULL, 0)) 932 if (__glibc_unlikely (lim_states == NULL))
996 { 933 {
997 ret = REG_ESPACE; 934 ret = REG_ESPACE;
998 goto free_return; 935 goto free_return;
@@ -1005,14 +942,14 @@ prune_impossible_nodes (re_match_context_t *mctx)
1005 match_last); 942 match_last);
1006 ret = sift_states_backward (mctx, &sctx); 943 ret = sift_states_backward (mctx, &sctx);
1007 re_node_set_free (&sctx.limits); 944 re_node_set_free (&sctx.limits);
1008 if (BE (ret != REG_NOERROR, 0)) 945 if (__glibc_unlikely (ret != REG_NOERROR))
1009 goto free_return; 946 goto free_return;
1010 if (sifted_states[0] != NULL || lim_states[0] != NULL) 947 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1011 break; 948 break;
1012 do 949 do
1013 { 950 {
1014 --match_last; 951 --match_last;
1015 if (! REG_VALID_INDEX (match_last)) 952 if (match_last < 0)
1016 { 953 {
1017 ret = REG_NOMATCH; 954 ret = REG_NOMATCH;
1018 goto free_return; 955 goto free_return;
@@ -1027,7 +964,7 @@ prune_impossible_nodes (re_match_context_t *mctx)
1027 match_last + 1); 964 match_last + 1);
1028 re_free (lim_states); 965 re_free (lim_states);
1029 lim_states = NULL; 966 lim_states = NULL;
1030 if (BE (ret != REG_NOERROR, 0)) 967 if (__glibc_unlikely (ret != REG_NOERROR))
1031 goto free_return; 968 goto free_return;
1032 } 969 }
1033 else 970 else
@@ -1035,7 +972,7 @@ prune_impossible_nodes (re_match_context_t *mctx)
1035 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last); 972 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1036 ret = sift_states_backward (mctx, &sctx); 973 ret = sift_states_backward (mctx, &sctx);
1037 re_node_set_free (&sctx.limits); 974 re_node_set_free (&sctx.limits);
1038 if (BE (ret != REG_NOERROR, 0)) 975 if (__glibc_unlikely (ret != REG_NOERROR))
1039 goto free_return; 976 goto free_return;
1040 if (sifted_states[0] == NULL) 977 if (sifted_states[0] == NULL)
1041 { 978 {
@@ -1060,7 +997,7 @@ prune_impossible_nodes (re_match_context_t *mctx)
1060 since initial states may have constraints like "\<", "^", etc.. */ 997 since initial states may have constraints like "\<", "^", etc.. */
1061 998
1062static inline re_dfastate_t * 999static inline re_dfastate_t *
1063__attribute__ ((always_inline)) internal_function 1000__attribute__ ((always_inline))
1064acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx, 1001acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1065 Idx idx) 1002 Idx idx)
1066{ 1003{
@@ -1093,8 +1030,8 @@ acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1093} 1030}
1094 1031
1095/* Check whether the regular expression match input string INPUT or not, 1032/* Check whether the regular expression match input string INPUT or not,
1096 and return the index where the matching end. Return REG_MISSING if 1033 and return the index where the matching end. Return -1 if
1097 there is no match, and return REG_ERROR in case of an error. 1034 there is no match, and return -2 in case of an error.
1098 FL_LONGEST_MATCH means we want the POSIX longest matching. 1035 FL_LONGEST_MATCH means we want the POSIX longest matching.
1099 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the 1036 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1100 next place where we may want to try matching. 1037 next place where we may want to try matching.
@@ -1102,14 +1039,14 @@ acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1102 index of the buffer. */ 1039 index of the buffer. */
1103 1040
1104static Idx 1041static Idx
1105internal_function __attribute_warn_unused_result__ 1042__attribute_warn_unused_result__
1106check_matching (re_match_context_t *mctx, bool fl_longest_match, 1043check_matching (re_match_context_t *mctx, bool fl_longest_match,
1107 Idx *p_match_first) 1044 Idx *p_match_first)
1108{ 1045{
1109 const re_dfa_t *const dfa = mctx->dfa; 1046 const re_dfa_t *const dfa = mctx->dfa;
1110 reg_errcode_t err; 1047 reg_errcode_t err;
1111 Idx match = 0; 1048 Idx match = 0;
1112 Idx match_last = REG_MISSING; 1049 Idx match_last = -1;
1113 Idx cur_str_idx = re_string_cur_idx (&mctx->input); 1050 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1114 re_dfastate_t *cur_state; 1051 re_dfastate_t *cur_state;
1115 bool at_init_state = p_match_first != NULL; 1052 bool at_init_state = p_match_first != NULL;
@@ -1118,10 +1055,10 @@ check_matching (re_match_context_t *mctx, bool fl_longest_match,
1118 err = REG_NOERROR; 1055 err = REG_NOERROR;
1119 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx); 1056 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1120 /* An initial state must not be NULL (invalid). */ 1057 /* An initial state must not be NULL (invalid). */
1121 if (BE (cur_state == NULL, 0)) 1058 if (__glibc_unlikely (cur_state == NULL))
1122 { 1059 {
1123 assert (err == REG_ESPACE); 1060 DEBUG_ASSERT (err == REG_ESPACE);
1124 return REG_ERROR; 1061 return -2;
1125 } 1062 }
1126 1063
1127 if (mctx->state_log != NULL) 1064 if (mctx->state_log != NULL)
@@ -1130,24 +1067,24 @@ check_matching (re_match_context_t *mctx, bool fl_longest_match,
1130 1067
1131 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them 1068 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1132 later. E.g. Processing back references. */ 1069 later. E.g. Processing back references. */
1133 if (BE (dfa->nbackref, 0)) 1070 if (__glibc_unlikely (dfa->nbackref))
1134 { 1071 {
1135 at_init_state = false; 1072 at_init_state = false;
1136 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0); 1073 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1137 if (BE (err != REG_NOERROR, 0)) 1074 if (__glibc_unlikely (err != REG_NOERROR))
1138 return err; 1075 return err;
1139 1076
1140 if (cur_state->has_backref) 1077 if (cur_state->has_backref)
1141 { 1078 {
1142 err = transit_state_bkref (mctx, &cur_state->nodes); 1079 err = transit_state_bkref (mctx, &cur_state->nodes);
1143 if (BE (err != REG_NOERROR, 0)) 1080 if (__glibc_unlikely (err != REG_NOERROR))
1144 return err; 1081 return err;
1145 } 1082 }
1146 } 1083 }
1147 } 1084 }
1148 1085
1149 /* If the RE accepts NULL string. */ 1086 /* If the RE accepts NULL string. */
1150 if (BE (cur_state->halt, 0)) 1087 if (__glibc_unlikely (cur_state->halt))
1151 { 1088 {
1152 if (!cur_state->has_constraint 1089 if (!cur_state->has_constraint
1153 || check_halt_state_context (mctx, cur_state, cur_str_idx)) 1090 || check_halt_state_context (mctx, cur_state, cur_str_idx))
@@ -1167,16 +1104,16 @@ check_matching (re_match_context_t *mctx, bool fl_longest_match,
1167 re_dfastate_t *old_state = cur_state; 1104 re_dfastate_t *old_state = cur_state;
1168 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1; 1105 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1169 1106
1170 if ((BE (next_char_idx >= mctx->input.bufs_len, 0) 1107 if ((__glibc_unlikely (next_char_idx >= mctx->input.bufs_len)
1171 && mctx->input.bufs_len < mctx->input.len) 1108 && mctx->input.bufs_len < mctx->input.len)
1172 || (BE (next_char_idx >= mctx->input.valid_len, 0) 1109 || (__glibc_unlikely (next_char_idx >= mctx->input.valid_len)
1173 && mctx->input.valid_len < mctx->input.len)) 1110 && mctx->input.valid_len < mctx->input.len))
1174 { 1111 {
1175 err = extend_buffers (mctx, next_char_idx + 1); 1112 err = extend_buffers (mctx, next_char_idx + 1);
1176 if (BE (err != REG_NOERROR, 0)) 1113 if (__glibc_unlikely (err != REG_NOERROR))
1177 { 1114 {
1178 assert (err == REG_ESPACE); 1115 DEBUG_ASSERT (err == REG_ESPACE);
1179 return REG_ERROR; 1116 return -2;
1180 } 1117 }
1181 } 1118 }
1182 1119
@@ -1189,8 +1126,8 @@ check_matching (re_match_context_t *mctx, bool fl_longest_match,
1189 /* Reached the invalid state or an error. Try to recover a valid 1126 /* Reached the invalid state or an error. Try to recover a valid
1190 state using the state log, if available and if we have not 1127 state using the state log, if available and if we have not
1191 already found a valid (even if not the longest) match. */ 1128 already found a valid (even if not the longest) match. */
1192 if (BE (err != REG_NOERROR, 0)) 1129 if (__glibc_unlikely (err != REG_NOERROR))
1193 return REG_ERROR; 1130 return -2;
1194 1131
1195 if (mctx->state_log == NULL 1132 if (mctx->state_log == NULL
1196 || (match && !fl_longest_match) 1133 || (match && !fl_longest_match)
@@ -1198,7 +1135,7 @@ check_matching (re_match_context_t *mctx, bool fl_longest_match,
1198 break; 1135 break;
1199 } 1136 }
1200 1137
1201 if (BE (at_init_state, 0)) 1138 if (__glibc_unlikely (at_init_state))
1202 { 1139 {
1203 if (old_state == cur_state) 1140 if (old_state == cur_state)
1204 next_start_idx = next_char_idx; 1141 next_start_idx = next_char_idx;
@@ -1235,7 +1172,6 @@ check_matching (re_match_context_t *mctx, bool fl_longest_match,
1235/* Check NODE match the current context. */ 1172/* Check NODE match the current context. */
1236 1173
1237static bool 1174static bool
1238internal_function
1239check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context) 1175check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1240{ 1176{
1241 re_token_type_t type = dfa->nodes[node].type; 1177 re_token_type_t type = dfa->nodes[node].type;
@@ -1254,15 +1190,12 @@ check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1254 match the context, return the node. */ 1190 match the context, return the node. */
1255 1191
1256static Idx 1192static Idx
1257internal_function
1258check_halt_state_context (const re_match_context_t *mctx, 1193check_halt_state_context (const re_match_context_t *mctx,
1259 const re_dfastate_t *state, Idx idx) 1194 const re_dfastate_t *state, Idx idx)
1260{ 1195{
1261 Idx i; 1196 Idx i;
1262 unsigned int context; 1197 unsigned int context;
1263#ifdef DEBUG 1198 DEBUG_ASSERT (state->halt);
1264 assert (state->halt);
1265#endif
1266 context = re_string_context_at (&mctx->input, idx, mctx->eflags); 1199 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1267 for (i = 0; i < state->nodes.nelem; ++i) 1200 for (i = 0; i < state->nodes.nelem; ++i)
1268 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context)) 1201 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
@@ -1273,33 +1206,35 @@ check_halt_state_context (const re_match_context_t *mctx,
1273/* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA 1206/* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1274 corresponding to the DFA). 1207 corresponding to the DFA).
1275 Return the destination node, and update EPS_VIA_NODES; 1208 Return the destination node, and update EPS_VIA_NODES;
1276 return REG_MISSING in case of errors. */ 1209 return -1 on match failure, -2 on error. */
1277 1210
1278static Idx 1211static Idx
1279internal_function
1280proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs, 1212proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1213 regmatch_t *prevregs,
1281 Idx *pidx, Idx node, re_node_set *eps_via_nodes, 1214 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1282 struct re_fail_stack_t *fs) 1215 struct re_fail_stack_t *fs)
1283{ 1216{
1284 const re_dfa_t *const dfa = mctx->dfa; 1217 const re_dfa_t *const dfa = mctx->dfa;
1285 Idx i;
1286 bool ok;
1287 if (IS_EPSILON_NODE (dfa->nodes[node].type)) 1218 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1288 { 1219 {
1289 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes; 1220 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1290 re_node_set *edests = &dfa->edests[node]; 1221 re_node_set *edests = &dfa->edests[node];
1291 Idx dest_node; 1222
1292 ok = re_node_set_insert (eps_via_nodes, node); 1223 if (! re_node_set_contains (eps_via_nodes, node))
1293 if (BE (! ok, 0)) 1224 {
1294 return REG_ERROR; 1225 bool ok = re_node_set_insert (eps_via_nodes, node);
1295 /* Pick up a valid destination, or return REG_MISSING if none 1226 if (__glibc_unlikely (! ok))
1296 is found. */ 1227 return -2;
1297 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i) 1228 }
1229
1230 /* Pick a valid destination, or return -1 if none is found. */
1231 Idx dest_node = -1;
1232 for (Idx i = 0; i < edests->nelem; i++)
1298 { 1233 {
1299 Idx candidate = edests->elems[i]; 1234 Idx candidate = edests->elems[i];
1300 if (!re_node_set_contains (cur_nodes, candidate)) 1235 if (!re_node_set_contains (cur_nodes, candidate))
1301 continue; 1236 continue;
1302 if (dest_node == REG_MISSING) 1237 if (dest_node == -1)
1303 dest_node = candidate; 1238 dest_node = candidate;
1304 1239
1305 else 1240 else
@@ -1312,8 +1247,8 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1312 /* Otherwise, push the second epsilon-transition on the fail stack. */ 1247 /* Otherwise, push the second epsilon-transition on the fail stack. */
1313 else if (fs != NULL 1248 else if (fs != NULL
1314 && push_fail_stack (fs, *pidx, candidate, nregs, regs, 1249 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1315 eps_via_nodes)) 1250 prevregs, eps_via_nodes))
1316 return REG_ERROR; 1251 return -2;
1317 1252
1318 /* We know we are going to exit. */ 1253 /* We know we are going to exit. */
1319 break; 1254 break;
@@ -1334,26 +1269,31 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1334 if (type == OP_BACK_REF) 1269 if (type == OP_BACK_REF)
1335 { 1270 {
1336 Idx subexp_idx = dfa->nodes[node].opr.idx + 1; 1271 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1337 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so; 1272 if (subexp_idx < nregs)
1273 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1338 if (fs != NULL) 1274 if (fs != NULL)
1339 { 1275 {
1340 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1) 1276 if (subexp_idx >= nregs
1341 return REG_MISSING; 1277 || regs[subexp_idx].rm_so == -1
1278 || regs[subexp_idx].rm_eo == -1)
1279 return -1;
1342 else if (naccepted) 1280 else if (naccepted)
1343 { 1281 {
1344 char *buf = (char *) re_string_get_buffer (&mctx->input); 1282 char *buf = (char *) re_string_get_buffer (&mctx->input);
1345 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx, 1283 if (mctx->input.valid_len - *pidx < naccepted
1346 naccepted) != 0) 1284 || (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1347 return REG_MISSING; 1285 naccepted)
1286 != 0))
1287 return -1;
1348 } 1288 }
1349 } 1289 }
1350 1290
1351 if (naccepted == 0) 1291 if (naccepted == 0)
1352 { 1292 {
1353 Idx dest_node; 1293 Idx dest_node;
1354 ok = re_node_set_insert (eps_via_nodes, node); 1294 bool ok = re_node_set_insert (eps_via_nodes, node);
1355 if (BE (! ok, 0)) 1295 if (__glibc_unlikely (! ok))
1356 return REG_ERROR; 1296 return -2;
1357 dest_node = dfa->edests[node].elems[0]; 1297 dest_node = dfa->edests[node].elems[0];
1358 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes, 1298 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1359 dest_node)) 1299 dest_node))
@@ -1369,26 +1309,27 @@ proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1369 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL 1309 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1370 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes, 1310 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1371 dest_node))) 1311 dest_node)))
1372 return REG_MISSING; 1312 return -1;
1373 re_node_set_empty (eps_via_nodes); 1313 re_node_set_empty (eps_via_nodes);
1374 return dest_node; 1314 return dest_node;
1375 } 1315 }
1376 } 1316 }
1377 return REG_MISSING; 1317 return -1;
1378} 1318}
1379 1319
1380static reg_errcode_t 1320static reg_errcode_t
1381internal_function __attribute_warn_unused_result__ 1321__attribute_warn_unused_result__
1382push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node, 1322push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1383 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes) 1323 Idx nregs, regmatch_t *regs, regmatch_t *prevregs,
1324 re_node_set *eps_via_nodes)
1384{ 1325{
1385 reg_errcode_t err; 1326 reg_errcode_t err;
1386 Idx num = fs->num++; 1327 Idx num = fs->num++;
1387 if (fs->num == fs->alloc) 1328 if (fs->num == fs->alloc)
1388 { 1329 {
1389 struct re_fail_stack_ent_t *new_array; 1330 struct re_fail_stack_ent_t *new_array;
1390 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t) 1331 new_array = re_realloc (fs->stack, struct re_fail_stack_ent_t,
1391 * fs->alloc * 2)); 1332 fs->alloc * 2);
1392 if (new_array == NULL) 1333 if (new_array == NULL)
1393 return REG_ESPACE; 1334 return REG_ESPACE;
1394 fs->alloc *= 2; 1335 fs->alloc *= 2;
@@ -1396,36 +1337,46 @@ push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1396 } 1337 }
1397 fs->stack[num].idx = str_idx; 1338 fs->stack[num].idx = str_idx;
1398 fs->stack[num].node = dest_node; 1339 fs->stack[num].node = dest_node;
1399 fs->stack[num].regs = re_malloc (regmatch_t, nregs); 1340 fs->stack[num].regs = re_malloc (regmatch_t, 2 * nregs);
1400 if (fs->stack[num].regs == NULL) 1341 if (fs->stack[num].regs == NULL)
1401 return REG_ESPACE; 1342 return REG_ESPACE;
1402 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs); 1343 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1344 memcpy (fs->stack[num].regs + nregs, prevregs, sizeof (regmatch_t) * nregs);
1403 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes); 1345 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1404 return err; 1346 return err;
1405} 1347}
1406 1348
1407static Idx 1349static Idx
1408internal_function
1409pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs, 1350pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1410 regmatch_t *regs, re_node_set *eps_via_nodes) 1351 regmatch_t *regs, regmatch_t *prevregs,
1352 re_node_set *eps_via_nodes)
1411{ 1353{
1354 if (fs == NULL || fs->num == 0)
1355 return -1;
1412 Idx num = --fs->num; 1356 Idx num = --fs->num;
1413 assert (REG_VALID_INDEX (num));
1414 *pidx = fs->stack[num].idx; 1357 *pidx = fs->stack[num].idx;
1415 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs); 1358 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1359 memcpy (prevregs, fs->stack[num].regs + nregs, sizeof (regmatch_t) * nregs);
1416 re_node_set_free (eps_via_nodes); 1360 re_node_set_free (eps_via_nodes);
1417 re_free (fs->stack[num].regs); 1361 re_free (fs->stack[num].regs);
1418 *eps_via_nodes = fs->stack[num].eps_via_nodes; 1362 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1363 DEBUG_ASSERT (0 <= fs->stack[num].node);
1419 return fs->stack[num].node; 1364 return fs->stack[num].node;
1420} 1365}
1421 1366
1367
1368#define DYNARRAY_STRUCT regmatch_list
1369#define DYNARRAY_ELEMENT regmatch_t
1370#define DYNARRAY_PREFIX regmatch_list_
1371#include <malloc/dynarray-skeleton.c>
1372
1422/* Set the positions where the subexpressions are starts/ends to registers 1373/* Set the positions where the subexpressions are starts/ends to registers
1423 PMATCH. 1374 PMATCH.
1424 Note: We assume that pmatch[0] is already set, and 1375 Note: We assume that pmatch[0] is already set, and
1425 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */ 1376 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1426 1377
1427static reg_errcode_t 1378static reg_errcode_t
1428internal_function __attribute_warn_unused_result__ 1379__attribute_warn_unused_result__
1429set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch, 1380set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1430 regmatch_t *pmatch, bool fl_backtrack) 1381 regmatch_t *pmatch, bool fl_backtrack)
1431{ 1382{
@@ -1434,13 +1385,11 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1434 re_node_set eps_via_nodes; 1385 re_node_set eps_via_nodes;
1435 struct re_fail_stack_t *fs; 1386 struct re_fail_stack_t *fs;
1436 struct re_fail_stack_t fs_body = { 0, 2, NULL }; 1387 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1437 regmatch_t *prev_idx_match; 1388 struct regmatch_list prev_match;
1438 bool prev_idx_match_malloced = false; 1389 regmatch_list_init (&prev_match);
1439 1390
1440#ifdef DEBUG 1391 DEBUG_ASSERT (nmatch > 1);
1441 assert (nmatch > 1); 1392 DEBUG_ASSERT (mctx->state_log != NULL);
1442 assert (mctx->state_log != NULL);
1443#endif
1444 if (fl_backtrack) 1393 if (fl_backtrack)
1445 { 1394 {
1446 fs = &fs_body; 1395 fs = &fs_body;
@@ -1454,85 +1403,73 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1454 cur_node = dfa->init_node; 1403 cur_node = dfa->init_node;
1455 re_node_set_init_empty (&eps_via_nodes); 1404 re_node_set_init_empty (&eps_via_nodes);
1456 1405
1457 if (__libc_use_alloca (nmatch * sizeof (regmatch_t))) 1406 if (!regmatch_list_resize (&prev_match, nmatch))
1458 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1459 else
1460 { 1407 {
1461 prev_idx_match = re_malloc (regmatch_t, nmatch); 1408 regmatch_list_free (&prev_match);
1462 if (prev_idx_match == NULL) 1409 free_fail_stack_return (fs);
1463 { 1410 return REG_ESPACE;
1464 free_fail_stack_return (fs);
1465 return REG_ESPACE;
1466 }
1467 prev_idx_match_malloced = true;
1468 } 1411 }
1412 regmatch_t *prev_idx_match = regmatch_list_begin (&prev_match);
1469 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch); 1413 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1470 1414
1471 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;) 1415 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1472 { 1416 {
1473 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch); 1417 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1474 1418
1475 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node) 1419 if ((idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1420 || (fs && re_node_set_contains (&eps_via_nodes, cur_node)))
1476 { 1421 {
1477 Idx reg_idx; 1422 Idx reg_idx;
1423 cur_node = -1;
1478 if (fs) 1424 if (fs)
1479 { 1425 {
1480 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx) 1426 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1481 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1) 1427 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1482 break; 1428 {
1483 if (reg_idx == nmatch) 1429 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1484 { 1430 prev_idx_match, &eps_via_nodes);
1485 re_node_set_free (&eps_via_nodes); 1431 break;
1486 if (prev_idx_match_malloced) 1432 }
1487 re_free (prev_idx_match);
1488 return free_fail_stack_return (fs);
1489 }
1490 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1491 &eps_via_nodes);
1492 } 1433 }
1493 else 1434 if (cur_node < 0)
1494 { 1435 {
1495 re_node_set_free (&eps_via_nodes); 1436 re_node_set_free (&eps_via_nodes);
1496 if (prev_idx_match_malloced) 1437 regmatch_list_free (&prev_match);
1497 re_free (prev_idx_match); 1438 return free_fail_stack_return (fs);
1498 return REG_NOERROR;
1499 } 1439 }
1500 } 1440 }
1501 1441
1502 /* Proceed to next node. */ 1442 /* Proceed to next node. */
1503 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node, 1443 cur_node = proceed_next_node (mctx, nmatch, pmatch, prev_idx_match,
1444 &idx, cur_node,
1504 &eps_via_nodes, fs); 1445 &eps_via_nodes, fs);
1505 1446
1506 if (BE (! REG_VALID_INDEX (cur_node), 0)) 1447 if (__glibc_unlikely (cur_node < 0))
1507 { 1448 {
1508 if (BE (cur_node == REG_ERROR, 0)) 1449 if (__glibc_unlikely (cur_node == -2))
1509 { 1450 {
1510 re_node_set_free (&eps_via_nodes); 1451 re_node_set_free (&eps_via_nodes);
1511 if (prev_idx_match_malloced) 1452 regmatch_list_free (&prev_match);
1512 re_free (prev_idx_match);
1513 free_fail_stack_return (fs); 1453 free_fail_stack_return (fs);
1514 return REG_ESPACE; 1454 return REG_ESPACE;
1515 } 1455 }
1516 if (fs) 1456 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1517 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch, 1457 prev_idx_match, &eps_via_nodes);
1518 &eps_via_nodes); 1458 if (cur_node < 0)
1519 else
1520 { 1459 {
1521 re_node_set_free (&eps_via_nodes); 1460 re_node_set_free (&eps_via_nodes);
1522 if (prev_idx_match_malloced) 1461 regmatch_list_free (&prev_match);
1523 re_free (prev_idx_match); 1462 free_fail_stack_return (fs);
1524 return REG_NOMATCH; 1463 return REG_NOMATCH;
1525 } 1464 }
1526 } 1465 }
1527 } 1466 }
1528 re_node_set_free (&eps_via_nodes); 1467 re_node_set_free (&eps_via_nodes);
1529 if (prev_idx_match_malloced) 1468 regmatch_list_free (&prev_match);
1530 re_free (prev_idx_match);
1531 return free_fail_stack_return (fs); 1469 return free_fail_stack_return (fs);
1532} 1470}
1533 1471
1534static reg_errcode_t 1472static reg_errcode_t
1535internal_function
1536free_fail_stack_return (struct re_fail_stack_t *fs) 1473free_fail_stack_return (struct re_fail_stack_t *fs)
1537{ 1474{
1538 if (fs) 1475 if (fs)
@@ -1549,7 +1486,6 @@ free_fail_stack_return (struct re_fail_stack_t *fs)
1549} 1486}
1550 1487
1551static void 1488static void
1552internal_function
1553update_regs (const re_dfa_t *dfa, regmatch_t *pmatch, 1489update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1554 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch) 1490 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1555{ 1491{
@@ -1567,10 +1503,10 @@ update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1567 } 1503 }
1568 else if (type == OP_CLOSE_SUBEXP) 1504 else if (type == OP_CLOSE_SUBEXP)
1569 { 1505 {
1506 /* We are at the last node of this sub expression. */
1570 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1; 1507 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1571 if (reg_num < nmatch) 1508 if (reg_num < nmatch)
1572 { 1509 {
1573 /* We are at the last node of this sub expression. */
1574 if (pmatch[reg_num].rm_so < cur_idx) 1510 if (pmatch[reg_num].rm_so < cur_idx)
1575 { 1511 {
1576 pmatch[reg_num].rm_eo = cur_idx; 1512 pmatch[reg_num].rm_eo = cur_idx;
@@ -1621,7 +1557,6 @@ update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1621 ((state) != NULL && re_node_set_contains (&(state)->nodes, node)) 1557 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1622 1558
1623static reg_errcode_t 1559static reg_errcode_t
1624internal_function
1625sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx) 1560sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1626{ 1561{
1627 reg_errcode_t err; 1562 reg_errcode_t err;
@@ -1629,17 +1564,15 @@ sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1629 Idx str_idx = sctx->last_str_idx; 1564 Idx str_idx = sctx->last_str_idx;
1630 re_node_set cur_dest; 1565 re_node_set cur_dest;
1631 1566
1632#ifdef DEBUG 1567 DEBUG_ASSERT (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1633 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1634#endif
1635 1568
1636 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon 1569 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1637 transit to the last_node and the last_node itself. */ 1570 transit to the last_node and the last_node itself. */
1638 err = re_node_set_init_1 (&cur_dest, sctx->last_node); 1571 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1639 if (BE (err != REG_NOERROR, 0)) 1572 if (__glibc_unlikely (err != REG_NOERROR))
1640 return err; 1573 return err;
1641 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest); 1574 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1642 if (BE (err != REG_NOERROR, 0)) 1575 if (__glibc_unlikely (err != REG_NOERROR))
1643 goto free_return; 1576 goto free_return;
1644 1577
1645 /* Then check each states in the state_log. */ 1578 /* Then check each states in the state_log. */
@@ -1660,7 +1593,7 @@ sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1660 if (mctx->state_log[str_idx]) 1593 if (mctx->state_log[str_idx])
1661 { 1594 {
1662 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest); 1595 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1663 if (BE (err != REG_NOERROR, 0)) 1596 if (__glibc_unlikely (err != REG_NOERROR))
1664 goto free_return; 1597 goto free_return;
1665 } 1598 }
1666 1599
@@ -1669,7 +1602,7 @@ sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1669 - It is in CUR_SRC. 1602 - It is in CUR_SRC.
1670 And update state_log. */ 1603 And update state_log. */
1671 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest); 1604 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1672 if (BE (err != REG_NOERROR, 0)) 1605 if (__glibc_unlikely (err != REG_NOERROR))
1673 goto free_return; 1606 goto free_return;
1674 } 1607 }
1675 err = REG_NOERROR; 1608 err = REG_NOERROR;
@@ -1679,7 +1612,7 @@ sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1679} 1612}
1680 1613
1681static reg_errcode_t 1614static reg_errcode_t
1682internal_function __attribute_warn_unused_result__ 1615__attribute_warn_unused_result__
1683build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx, 1616build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1684 Idx str_idx, re_node_set *cur_dest) 1617 Idx str_idx, re_node_set *cur_dest)
1685{ 1618{
@@ -1699,11 +1632,8 @@ build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1699 Idx prev_node = cur_src->elems[i]; 1632 Idx prev_node = cur_src->elems[i];
1700 int naccepted = 0; 1633 int naccepted = 0;
1701 bool ok; 1634 bool ok;
1635 DEBUG_ASSERT (!IS_EPSILON_NODE (dfa->nodes[prev_node].type));
1702 1636
1703#ifdef DEBUG
1704 re_token_type_t type = dfa->nodes[prev_node].type;
1705 assert (!IS_EPSILON_NODE (type));
1706#endif
1707#ifdef RE_ENABLE_I18N 1637#ifdef RE_ENABLE_I18N
1708 /* If the node may accept "multi byte". */ 1638 /* If the node may accept "multi byte". */
1709 if (dfa->nodes[prev_node].accept_mb) 1639 if (dfa->nodes[prev_node].accept_mb)
@@ -1731,7 +1661,7 @@ build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1731 continue; 1661 continue;
1732 } 1662 }
1733 ok = re_node_set_insert (cur_dest, prev_node); 1663 ok = re_node_set_insert (cur_dest, prev_node);
1734 if (BE (! ok, 0)) 1664 if (__glibc_unlikely (! ok))
1735 return REG_ESPACE; 1665 return REG_ESPACE;
1736 } 1666 }
1737 1667
@@ -1741,7 +1671,6 @@ build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1741/* Helper functions. */ 1671/* Helper functions. */
1742 1672
1743static reg_errcode_t 1673static reg_errcode_t
1744internal_function
1745clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx) 1674clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1746{ 1675{
1747 Idx top = mctx->state_log_top; 1676 Idx top = mctx->state_log_top;
@@ -1753,7 +1682,7 @@ clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1753 { 1682 {
1754 reg_errcode_t err; 1683 reg_errcode_t err;
1755 err = extend_buffers (mctx, next_state_log_idx + 1); 1684 err = extend_buffers (mctx, next_state_log_idx + 1);
1756 if (BE (err != REG_NOERROR, 0)) 1685 if (__glibc_unlikely (err != REG_NOERROR))
1757 return err; 1686 return err;
1758 } 1687 }
1759 1688
@@ -1767,7 +1696,6 @@ clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1767} 1696}
1768 1697
1769static reg_errcode_t 1698static reg_errcode_t
1770internal_function
1771merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst, 1699merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1772 re_dfastate_t **src, Idx num) 1700 re_dfastate_t **src, Idx num)
1773{ 1701{
@@ -1782,11 +1710,11 @@ merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1782 re_node_set merged_set; 1710 re_node_set merged_set;
1783 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes, 1711 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1784 &src[st_idx]->nodes); 1712 &src[st_idx]->nodes);
1785 if (BE (err != REG_NOERROR, 0)) 1713 if (__glibc_unlikely (err != REG_NOERROR))
1786 return err; 1714 return err;
1787 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set); 1715 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1788 re_node_set_free (&merged_set); 1716 re_node_set_free (&merged_set);
1789 if (BE (err != REG_NOERROR, 0)) 1717 if (__glibc_unlikely (err != REG_NOERROR))
1790 return err; 1718 return err;
1791 } 1719 }
1792 } 1720 }
@@ -1794,7 +1722,6 @@ merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1794} 1722}
1795 1723
1796static reg_errcode_t 1724static reg_errcode_t
1797internal_function
1798update_cur_sifted_state (const re_match_context_t *mctx, 1725update_cur_sifted_state (const re_match_context_t *mctx,
1799 re_sift_context_t *sctx, Idx str_idx, 1726 re_sift_context_t *sctx, Idx str_idx,
1800 re_node_set *dest_nodes) 1727 re_node_set *dest_nodes)
@@ -1814,7 +1741,7 @@ update_cur_sifted_state (const re_match_context_t *mctx,
1814 /* At first, add the nodes which can epsilon transit to a node in 1741 /* At first, add the nodes which can epsilon transit to a node in
1815 DEST_NODE. */ 1742 DEST_NODE. */
1816 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates); 1743 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1817 if (BE (err != REG_NOERROR, 0)) 1744 if (__glibc_unlikely (err != REG_NOERROR))
1818 return err; 1745 return err;
1819 1746
1820 /* Then, check the limitations in the current sift_context. */ 1747 /* Then, check the limitations in the current sift_context. */
@@ -1822,27 +1749,27 @@ update_cur_sifted_state (const re_match_context_t *mctx,
1822 { 1749 {
1823 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits, 1750 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1824 mctx->bkref_ents, str_idx); 1751 mctx->bkref_ents, str_idx);
1825 if (BE (err != REG_NOERROR, 0)) 1752 if (__glibc_unlikely (err != REG_NOERROR))
1826 return err; 1753 return err;
1827 } 1754 }
1828 } 1755 }
1829 1756
1830 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes); 1757 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1831 if (BE (err != REG_NOERROR, 0)) 1758 if (__glibc_unlikely (err != REG_NOERROR))
1832 return err; 1759 return err;
1833 } 1760 }
1834 1761
1835 if (candidates && mctx->state_log[str_idx]->has_backref) 1762 if (candidates && mctx->state_log[str_idx]->has_backref)
1836 { 1763 {
1837 err = sift_states_bkref (mctx, sctx, str_idx, candidates); 1764 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1838 if (BE (err != REG_NOERROR, 0)) 1765 if (__glibc_unlikely (err != REG_NOERROR))
1839 return err; 1766 return err;
1840 } 1767 }
1841 return REG_NOERROR; 1768 return REG_NOERROR;
1842} 1769}
1843 1770
1844static reg_errcode_t 1771static reg_errcode_t
1845internal_function __attribute_warn_unused_result__ 1772__attribute_warn_unused_result__
1846add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes, 1773add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1847 const re_node_set *candidates) 1774 const re_node_set *candidates)
1848{ 1775{
@@ -1850,19 +1777,19 @@ add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1850 Idx i; 1777 Idx i;
1851 1778
1852 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes); 1779 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1853 if (BE (err != REG_NOERROR, 0)) 1780 if (__glibc_unlikely (err != REG_NOERROR))
1854 return err; 1781 return err;
1855 1782
1856 if (!state->inveclosure.alloc) 1783 if (!state->inveclosure.alloc)
1857 { 1784 {
1858 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem); 1785 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1859 if (BE (err != REG_NOERROR, 0)) 1786 if (__glibc_unlikely (err != REG_NOERROR))
1860 return REG_ESPACE; 1787 return REG_ESPACE;
1861 for (i = 0; i < dest_nodes->nelem; i++) 1788 for (i = 0; i < dest_nodes->nelem; i++)
1862 { 1789 {
1863 err = re_node_set_merge (&state->inveclosure, 1790 err = re_node_set_merge (&state->inveclosure,
1864 dfa->inveclosures + dest_nodes->elems[i]); 1791 dfa->inveclosures + dest_nodes->elems[i]);
1865 if (BE (err != REG_NOERROR, 0)) 1792 if (__glibc_unlikely (err != REG_NOERROR))
1866 return REG_ESPACE; 1793 return REG_ESPACE;
1867 } 1794 }
1868 } 1795 }
@@ -1871,7 +1798,6 @@ add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1871} 1798}
1872 1799
1873static reg_errcode_t 1800static reg_errcode_t
1874internal_function
1875sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes, 1801sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1876 const re_node_set *candidates) 1802 const re_node_set *candidates)
1877{ 1803{
@@ -1889,16 +1815,16 @@ sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1889 { 1815 {
1890 Idx edst1 = dfa->edests[cur_node].elems[0]; 1816 Idx edst1 = dfa->edests[cur_node].elems[0];
1891 Idx edst2 = ((dfa->edests[cur_node].nelem > 1) 1817 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1892 ? dfa->edests[cur_node].elems[1] : REG_MISSING); 1818 ? dfa->edests[cur_node].elems[1] : -1);
1893 if ((!re_node_set_contains (inv_eclosure, edst1) 1819 if ((!re_node_set_contains (inv_eclosure, edst1)
1894 && re_node_set_contains (dest_nodes, edst1)) 1820 && re_node_set_contains (dest_nodes, edst1))
1895 || (REG_VALID_NONZERO_INDEX (edst2) 1821 || (edst2 > 0
1896 && !re_node_set_contains (inv_eclosure, edst2) 1822 && !re_node_set_contains (inv_eclosure, edst2)
1897 && re_node_set_contains (dest_nodes, edst2))) 1823 && re_node_set_contains (dest_nodes, edst2)))
1898 { 1824 {
1899 err = re_node_set_add_intersect (&except_nodes, candidates, 1825 err = re_node_set_add_intersect (&except_nodes, candidates,
1900 dfa->inveclosures + cur_node); 1826 dfa->inveclosures + cur_node);
1901 if (BE (err != REG_NOERROR, 0)) 1827 if (__glibc_unlikely (err != REG_NOERROR))
1902 { 1828 {
1903 re_node_set_free (&except_nodes); 1829 re_node_set_free (&except_nodes);
1904 return err; 1830 return err;
@@ -1920,7 +1846,6 @@ sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1920} 1846}
1921 1847
1922static bool 1848static bool
1923internal_function
1924check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits, 1849check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1925 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx) 1850 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1926{ 1851{
@@ -1956,7 +1881,6 @@ check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1956} 1881}
1957 1882
1958static int 1883static int
1959internal_function
1960check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries, 1884check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1961 Idx subexp_idx, Idx from_node, Idx bkref_idx) 1885 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1962{ 1886{
@@ -1972,7 +1896,7 @@ check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1972 switch (dfa->nodes[node].type) 1896 switch (dfa->nodes[node].type)
1973 { 1897 {
1974 case OP_BACK_REF: 1898 case OP_BACK_REF:
1975 if (bkref_idx != REG_MISSING) 1899 if (bkref_idx != -1)
1976 { 1900 {
1977 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx; 1901 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1978 do 1902 do
@@ -2038,7 +1962,6 @@ check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
2038} 1962}
2039 1963
2040static int 1964static int
2041internal_function
2042check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit, 1965check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2043 Idx subexp_idx, Idx from_node, Idx str_idx, 1966 Idx subexp_idx, Idx from_node, Idx str_idx,
2044 Idx bkref_idx) 1967 Idx bkref_idx)
@@ -2068,7 +1991,6 @@ check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2068 which are against limitations from DEST_NODES. */ 1991 which are against limitations from DEST_NODES. */
2069 1992
2070static reg_errcode_t 1993static reg_errcode_t
2071internal_function
2072check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes, 1994check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2073 const re_node_set *candidates, re_node_set *limits, 1995 const re_node_set *candidates, re_node_set *limits,
2074 struct re_backref_cache_entry *bkref_ents, Idx str_idx) 1996 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
@@ -2088,8 +2010,8 @@ check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2088 subexp_idx = dfa->nodes[ent->node].opr.idx; 2010 subexp_idx = dfa->nodes[ent->node].opr.idx;
2089 if (ent->subexp_to == str_idx) 2011 if (ent->subexp_to == str_idx)
2090 { 2012 {
2091 Idx ops_node = REG_MISSING; 2013 Idx ops_node = -1;
2092 Idx cls_node = REG_MISSING; 2014 Idx cls_node = -1;
2093 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) 2015 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2094 { 2016 {
2095 Idx node = dest_nodes->elems[node_idx]; 2017 Idx node = dest_nodes->elems[node_idx];
@@ -2104,16 +2026,16 @@ check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2104 2026
2105 /* Check the limitation of the open subexpression. */ 2027 /* Check the limitation of the open subexpression. */
2106 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */ 2028 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2107 if (REG_VALID_INDEX (ops_node)) 2029 if (ops_node >= 0)
2108 { 2030 {
2109 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes, 2031 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2110 candidates); 2032 candidates);
2111 if (BE (err != REG_NOERROR, 0)) 2033 if (__glibc_unlikely (err != REG_NOERROR))
2112 return err; 2034 return err;
2113 } 2035 }
2114 2036
2115 /* Check the limitation of the close subexpression. */ 2037 /* Check the limitation of the close subexpression. */
2116 if (REG_VALID_INDEX (cls_node)) 2038 if (cls_node >= 0)
2117 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx) 2039 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2118 { 2040 {
2119 Idx node = dest_nodes->elems[node_idx]; 2041 Idx node = dest_nodes->elems[node_idx];
@@ -2126,7 +2048,7 @@ check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2126 Remove it form the current sifted state. */ 2048 Remove it form the current sifted state. */
2127 err = sub_epsilon_src_nodes (dfa, node, dest_nodes, 2049 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2128 candidates); 2050 candidates);
2129 if (BE (err != REG_NOERROR, 0)) 2051 if (__glibc_unlikely (err != REG_NOERROR))
2130 return err; 2052 return err;
2131 --node_idx; 2053 --node_idx;
2132 } 2054 }
@@ -2146,7 +2068,7 @@ check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2146 Remove it form the current sifted state. */ 2068 Remove it form the current sifted state. */
2147 err = sub_epsilon_src_nodes (dfa, node, dest_nodes, 2069 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2148 candidates); 2070 candidates);
2149 if (BE (err != REG_NOERROR, 0)) 2071 if (__glibc_unlikely (err != REG_NOERROR))
2150 return err; 2072 return err;
2151 } 2073 }
2152 } 2074 }
@@ -2156,7 +2078,7 @@ check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2156} 2078}
2157 2079
2158static reg_errcode_t 2080static reg_errcode_t
2159internal_function __attribute_warn_unused_result__ 2081__attribute_warn_unused_result__
2160sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx, 2082sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2161 Idx str_idx, const re_node_set *candidates) 2083 Idx str_idx, const re_node_set *candidates)
2162{ 2084{
@@ -2166,7 +2088,7 @@ sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2166 re_sift_context_t local_sctx; 2088 re_sift_context_t local_sctx;
2167 Idx first_idx = search_cur_bkref_entry (mctx, str_idx); 2089 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2168 2090
2169 if (first_idx == REG_MISSING) 2091 if (first_idx == -1)
2170 return REG_NOERROR; 2092 return REG_NOERROR;
2171 2093
2172 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */ 2094 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
@@ -2212,27 +2134,27 @@ sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2212 { 2134 {
2213 local_sctx = *sctx; 2135 local_sctx = *sctx;
2214 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits); 2136 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2215 if (BE (err != REG_NOERROR, 0)) 2137 if (__glibc_unlikely (err != REG_NOERROR))
2216 goto free_return; 2138 goto free_return;
2217 } 2139 }
2218 local_sctx.last_node = node; 2140 local_sctx.last_node = node;
2219 local_sctx.last_str_idx = str_idx; 2141 local_sctx.last_str_idx = str_idx;
2220 ok = re_node_set_insert (&local_sctx.limits, enabled_idx); 2142 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2221 if (BE (! ok, 0)) 2143 if (__glibc_unlikely (! ok))
2222 { 2144 {
2223 err = REG_ESPACE; 2145 err = REG_ESPACE;
2224 goto free_return; 2146 goto free_return;
2225 } 2147 }
2226 cur_state = local_sctx.sifted_states[str_idx]; 2148 cur_state = local_sctx.sifted_states[str_idx];
2227 err = sift_states_backward (mctx, &local_sctx); 2149 err = sift_states_backward (mctx, &local_sctx);
2228 if (BE (err != REG_NOERROR, 0)) 2150 if (__glibc_unlikely (err != REG_NOERROR))
2229 goto free_return; 2151 goto free_return;
2230 if (sctx->limited_states != NULL) 2152 if (sctx->limited_states != NULL)
2231 { 2153 {
2232 err = merge_state_array (dfa, sctx->limited_states, 2154 err = merge_state_array (dfa, sctx->limited_states,
2233 local_sctx.sifted_states, 2155 local_sctx.sifted_states,
2234 str_idx + 1); 2156 str_idx + 1);
2235 if (BE (err != REG_NOERROR, 0)) 2157 if (__glibc_unlikely (err != REG_NOERROR))
2236 goto free_return; 2158 goto free_return;
2237 } 2159 }
2238 local_sctx.sifted_states[str_idx] = cur_state; 2160 local_sctx.sifted_states[str_idx] = cur_state;
@@ -2256,7 +2178,6 @@ sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2256 2178
2257#ifdef RE_ENABLE_I18N 2179#ifdef RE_ENABLE_I18N
2258static int 2180static int
2259internal_function
2260sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx, 2181sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2261 Idx node_idx, Idx str_idx, Idx max_str_idx) 2182 Idx node_idx, Idx str_idx, Idx max_str_idx)
2262{ 2183{
@@ -2264,12 +2185,12 @@ sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2264 int naccepted; 2185 int naccepted;
2265 /* Check the node can accept "multi byte". */ 2186 /* Check the node can accept "multi byte". */
2266 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx); 2187 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2267 if (naccepted > 0 && str_idx + naccepted <= max_str_idx && 2188 if (naccepted > 0 && str_idx + naccepted <= max_str_idx
2268 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted], 2189 && !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2269 dfa->nexts[node_idx])) 2190 dfa->nexts[node_idx]))
2270 /* The node can't accept the "multi byte", or the 2191 /* The node can't accept the "multi byte", or the
2271 destination was already thrown away, then the node 2192 destination was already thrown away, then the node
2272 could't accept the current input "multi byte". */ 2193 couldn't accept the current input "multi byte". */
2273 naccepted = 0; 2194 naccepted = 0;
2274 /* Otherwise, it is sure that the node could accept 2195 /* Otherwise, it is sure that the node could accept
2275 'naccepted' bytes input. */ 2196 'naccepted' bytes input. */
@@ -2282,11 +2203,12 @@ sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2282 2203
2283/* Return the next state to which the current state STATE will transit by 2204/* Return the next state to which the current state STATE will transit by
2284 accepting the current input byte, and update STATE_LOG if necessary. 2205 accepting the current input byte, and update STATE_LOG if necessary.
2206 Return NULL on failure.
2285 If STATE can accept a multibyte char/collating element/back reference 2207 If STATE can accept a multibyte char/collating element/back reference
2286 update the destination of STATE_LOG. */ 2208 update the destination of STATE_LOG. */
2287 2209
2288static re_dfastate_t * 2210static re_dfastate_t *
2289internal_function __attribute_warn_unused_result__ 2211__attribute_warn_unused_result__
2290transit_state (reg_errcode_t *err, re_match_context_t *mctx, 2212transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2291 re_dfastate_t *state) 2213 re_dfastate_t *state)
2292{ 2214{
@@ -2295,10 +2217,10 @@ transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2295 2217
2296#ifdef RE_ENABLE_I18N 2218#ifdef RE_ENABLE_I18N
2297 /* If the current state can accept multibyte. */ 2219 /* If the current state can accept multibyte. */
2298 if (BE (state->accept_mb, 0)) 2220 if (__glibc_unlikely (state->accept_mb))
2299 { 2221 {
2300 *err = transit_state_mb (mctx, state); 2222 *err = transit_state_mb (mctx, state);
2301 if (BE (*err != REG_NOERROR, 0)) 2223 if (__glibc_unlikely (*err != REG_NOERROR))
2302 return NULL; 2224 return NULL;
2303 } 2225 }
2304#endif /* RE_ENABLE_I18N */ 2226#endif /* RE_ENABLE_I18N */
@@ -2315,11 +2237,11 @@ transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2315 for (;;) 2237 for (;;)
2316 { 2238 {
2317 trtable = state->trtable; 2239 trtable = state->trtable;
2318 if (BE (trtable != NULL, 1)) 2240 if (__glibc_likely (trtable != NULL))
2319 return trtable[ch]; 2241 return trtable[ch];
2320 2242
2321 trtable = state->word_trtable; 2243 trtable = state->word_trtable;
2322 if (BE (trtable != NULL, 1)) 2244 if (__glibc_likely (trtable != NULL))
2323 { 2245 {
2324 unsigned int context; 2246 unsigned int context;
2325 context 2247 context
@@ -2344,7 +2266,6 @@ transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2344 2266
2345/* Update the state_log if we need */ 2267/* Update the state_log if we need */
2346static re_dfastate_t * 2268static re_dfastate_t *
2347internal_function
2348merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx, 2269merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2349 re_dfastate_t *next_state) 2270 re_dfastate_t *next_state)
2350{ 2271{
@@ -2376,7 +2297,7 @@ merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2376 table_nodes = next_state->entrance_nodes; 2297 table_nodes = next_state->entrance_nodes;
2377 *err = re_node_set_init_union (&next_nodes, table_nodes, 2298 *err = re_node_set_init_union (&next_nodes, table_nodes,
2378 log_nodes); 2299 log_nodes);
2379 if (BE (*err != REG_NOERROR, 0)) 2300 if (__glibc_unlikely (*err != REG_NOERROR))
2380 return NULL; 2301 return NULL;
2381 } 2302 }
2382 else 2303 else
@@ -2396,21 +2317,21 @@ merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2396 re_node_set_free (&next_nodes); 2317 re_node_set_free (&next_nodes);
2397 } 2318 }
2398 2319
2399 if (BE (dfa->nbackref, 0) && next_state != NULL) 2320 if (__glibc_unlikely (dfa->nbackref) && next_state != NULL)
2400 { 2321 {
2401 /* Check OP_OPEN_SUBEXP in the current state in case that we use them 2322 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2402 later. We must check them here, since the back references in the 2323 later. We must check them here, since the back references in the
2403 next state might use them. */ 2324 next state might use them. */
2404 *err = check_subexp_matching_top (mctx, &next_state->nodes, 2325 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2405 cur_idx); 2326 cur_idx);
2406 if (BE (*err != REG_NOERROR, 0)) 2327 if (__glibc_unlikely (*err != REG_NOERROR))
2407 return NULL; 2328 return NULL;
2408 2329
2409 /* If the next state has back references. */ 2330 /* If the next state has back references. */
2410 if (next_state->has_backref) 2331 if (next_state->has_backref)
2411 { 2332 {
2412 *err = transit_state_bkref (mctx, &next_state->nodes); 2333 *err = transit_state_bkref (mctx, &next_state->nodes);
2413 if (BE (*err != REG_NOERROR, 0)) 2334 if (__glibc_unlikely (*err != REG_NOERROR))
2414 return NULL; 2335 return NULL;
2415 next_state = mctx->state_log[cur_idx]; 2336 next_state = mctx->state_log[cur_idx];
2416 } 2337 }
@@ -2423,7 +2344,6 @@ merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2423 multi-byte match, then look in the log for a state 2344 multi-byte match, then look in the log for a state
2424 from which to restart matching. */ 2345 from which to restart matching. */
2425static re_dfastate_t * 2346static re_dfastate_t *
2426internal_function
2427find_recover_state (reg_errcode_t *err, re_match_context_t *mctx) 2347find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2428{ 2348{
2429 re_dfastate_t *cur_state; 2349 re_dfastate_t *cur_state;
@@ -2454,7 +2374,6 @@ find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2454 corresponding back references. */ 2374 corresponding back references. */
2455 2375
2456static reg_errcode_t 2376static reg_errcode_t
2457internal_function
2458check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes, 2377check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2459 Idx str_idx) 2378 Idx str_idx)
2460{ 2379{
@@ -2476,7 +2395,7 @@ check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2476 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx))) 2395 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2477 { 2396 {
2478 err = match_ctx_add_subtop (mctx, node, str_idx); 2397 err = match_ctx_add_subtop (mctx, node, str_idx);
2479 if (BE (err != REG_NOERROR, 0)) 2398 if (__glibc_unlikely (err != REG_NOERROR))
2480 return err; 2399 return err;
2481 } 2400 }
2482 } 2401 }
@@ -2485,7 +2404,7 @@ check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2485 2404
2486#if 0 2405#if 0
2487/* Return the next state to which the current state STATE will transit by 2406/* Return the next state to which the current state STATE will transit by
2488 accepting the current input byte. */ 2407 accepting the current input byte. Return NULL on failure. */
2489 2408
2490static re_dfastate_t * 2409static re_dfastate_t *
2491transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx, 2410transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
@@ -2498,7 +2417,7 @@ transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2498 unsigned int context; 2417 unsigned int context;
2499 2418
2500 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1); 2419 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2501 if (BE (*err != REG_NOERROR, 0)) 2420 if (__glibc_unlikely (*err != REG_NOERROR))
2502 return NULL; 2421 return NULL;
2503 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt) 2422 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2504 { 2423 {
@@ -2507,7 +2426,7 @@ transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2507 { 2426 {
2508 *err = re_node_set_merge (&next_nodes, 2427 *err = re_node_set_merge (&next_nodes,
2509 dfa->eclosures + dfa->nexts[cur_node]); 2428 dfa->eclosures + dfa->nexts[cur_node]);
2510 if (BE (*err != REG_NOERROR, 0)) 2429 if (__glibc_unlikely (*err != REG_NOERROR))
2511 { 2430 {
2512 re_node_set_free (&next_nodes); 2431 re_node_set_free (&next_nodes);
2513 return NULL; 2432 return NULL;
@@ -2527,7 +2446,6 @@ transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2527 2446
2528#ifdef RE_ENABLE_I18N 2447#ifdef RE_ENABLE_I18N
2529static reg_errcode_t 2448static reg_errcode_t
2530internal_function
2531transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate) 2449transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2532{ 2450{
2533 const re_dfa_t *const dfa = mctx->dfa; 2451 const re_dfa_t *const dfa = mctx->dfa;
@@ -2567,11 +2485,9 @@ transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2567 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted 2485 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2568 : mctx->max_mb_elem_len); 2486 : mctx->max_mb_elem_len);
2569 err = clean_state_log_if_needed (mctx, dest_idx); 2487 err = clean_state_log_if_needed (mctx, dest_idx);
2570 if (BE (err != REG_NOERROR, 0)) 2488 if (__glibc_unlikely (err != REG_NOERROR))
2571 return err; 2489 return err;
2572#ifdef DEBUG 2490 DEBUG_ASSERT (dfa->nexts[cur_node_idx] != -1);
2573 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2574#endif
2575 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx]; 2491 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2576 2492
2577 dest_state = mctx->state_log[dest_idx]; 2493 dest_state = mctx->state_log[dest_idx];
@@ -2581,7 +2497,7 @@ transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2581 { 2497 {
2582 err = re_node_set_init_union (&dest_nodes, 2498 err = re_node_set_init_union (&dest_nodes,
2583 dest_state->entrance_nodes, new_nodes); 2499 dest_state->entrance_nodes, new_nodes);
2584 if (BE (err != REG_NOERROR, 0)) 2500 if (__glibc_unlikely (err != REG_NOERROR))
2585 return err; 2501 return err;
2586 } 2502 }
2587 context = re_string_context_at (&mctx->input, dest_idx - 1, 2503 context = re_string_context_at (&mctx->input, dest_idx - 1,
@@ -2590,7 +2506,8 @@ transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2590 = re_acquire_state_context (&err, dfa, &dest_nodes, context); 2506 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2591 if (dest_state != NULL) 2507 if (dest_state != NULL)
2592 re_node_set_free (&dest_nodes); 2508 re_node_set_free (&dest_nodes);
2593 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0)) 2509 if (__glibc_unlikely (mctx->state_log[dest_idx] == NULL
2510 && err != REG_NOERROR))
2594 return err; 2511 return err;
2595 } 2512 }
2596 return REG_NOERROR; 2513 return REG_NOERROR;
@@ -2598,7 +2515,6 @@ transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2598#endif /* RE_ENABLE_I18N */ 2515#endif /* RE_ENABLE_I18N */
2599 2516
2600static reg_errcode_t 2517static reg_errcode_t
2601internal_function
2602transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes) 2518transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2603{ 2519{
2604 const re_dfa_t *const dfa = mctx->dfa; 2520 const re_dfa_t *const dfa = mctx->dfa;
@@ -2630,14 +2546,12 @@ transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2630 Check the substring which the substring matched. */ 2546 Check the substring which the substring matched. */
2631 bkc_idx = mctx->nbkref_ents; 2547 bkc_idx = mctx->nbkref_ents;
2632 err = get_subexp (mctx, node_idx, cur_str_idx); 2548 err = get_subexp (mctx, node_idx, cur_str_idx);
2633 if (BE (err != REG_NOERROR, 0)) 2549 if (__glibc_unlikely (err != REG_NOERROR))
2634 goto free_return; 2550 goto free_return;
2635 2551
2636 /* And add the epsilon closures (which is 'new_dest_nodes') of 2552 /* And add the epsilon closures (which is 'new_dest_nodes') of
2637 the backreference to appropriate state_log. */ 2553 the backreference to appropriate state_log. */
2638#ifdef DEBUG 2554 DEBUG_ASSERT (dfa->nexts[node_idx] != -1);
2639 assert (dfa->nexts[node_idx] != REG_MISSING);
2640#endif
2641 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx) 2555 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2642 { 2556 {
2643 Idx subexp_len; 2557 Idx subexp_len;
@@ -2663,8 +2577,8 @@ transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2663 mctx->state_log[dest_str_idx] 2577 mctx->state_log[dest_str_idx]
2664 = re_acquire_state_context (&err, dfa, new_dest_nodes, 2578 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2665 context); 2579 context);
2666 if (BE (mctx->state_log[dest_str_idx] == NULL 2580 if (__glibc_unlikely (mctx->state_log[dest_str_idx] == NULL
2667 && err != REG_NOERROR, 0)) 2581 && err != REG_NOERROR))
2668 goto free_return; 2582 goto free_return;
2669 } 2583 }
2670 else 2584 else
@@ -2673,7 +2587,7 @@ transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2673 err = re_node_set_init_union (&dest_nodes, 2587 err = re_node_set_init_union (&dest_nodes,
2674 dest_state->entrance_nodes, 2588 dest_state->entrance_nodes,
2675 new_dest_nodes); 2589 new_dest_nodes);
2676 if (BE (err != REG_NOERROR, 0)) 2590 if (__glibc_unlikely (err != REG_NOERROR))
2677 { 2591 {
2678 re_node_set_free (&dest_nodes); 2592 re_node_set_free (&dest_nodes);
2679 goto free_return; 2593 goto free_return;
@@ -2681,8 +2595,8 @@ transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2681 mctx->state_log[dest_str_idx] 2595 mctx->state_log[dest_str_idx]
2682 = re_acquire_state_context (&err, dfa, &dest_nodes, context); 2596 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2683 re_node_set_free (&dest_nodes); 2597 re_node_set_free (&dest_nodes);
2684 if (BE (mctx->state_log[dest_str_idx] == NULL 2598 if (__glibc_unlikely (mctx->state_log[dest_str_idx] == NULL
2685 && err != REG_NOERROR, 0)) 2599 && err != REG_NOERROR))
2686 goto free_return; 2600 goto free_return;
2687 } 2601 }
2688 /* We need to check recursively if the backreference can epsilon 2602 /* We need to check recursively if the backreference can epsilon
@@ -2692,10 +2606,10 @@ transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2692 { 2606 {
2693 err = check_subexp_matching_top (mctx, new_dest_nodes, 2607 err = check_subexp_matching_top (mctx, new_dest_nodes,
2694 cur_str_idx); 2608 cur_str_idx);
2695 if (BE (err != REG_NOERROR, 0)) 2609 if (__glibc_unlikely (err != REG_NOERROR))
2696 goto free_return; 2610 goto free_return;
2697 err = transit_state_bkref (mctx, new_dest_nodes); 2611 err = transit_state_bkref (mctx, new_dest_nodes);
2698 if (BE (err != REG_NOERROR, 0)) 2612 if (__glibc_unlikely (err != REG_NOERROR))
2699 goto free_return; 2613 goto free_return;
2700 } 2614 }
2701 } 2615 }
@@ -2712,7 +2626,7 @@ transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2712 delay these checking for prune_impossible_nodes(). */ 2626 delay these checking for prune_impossible_nodes(). */
2713 2627
2714static reg_errcode_t 2628static reg_errcode_t
2715internal_function __attribute_warn_unused_result__ 2629__attribute_warn_unused_result__
2716get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx) 2630get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2717{ 2631{
2718 const re_dfa_t *const dfa = mctx->dfa; 2632 const re_dfa_t *const dfa = mctx->dfa;
@@ -2720,7 +2634,7 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2720 const char *buf = (const char *) re_string_get_buffer (&mctx->input); 2634 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2721 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */ 2635 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2722 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx); 2636 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2723 if (cache_idx != REG_MISSING) 2637 if (cache_idx != -1)
2724 { 2638 {
2725 const struct re_backref_cache_entry *entry 2639 const struct re_backref_cache_entry *entry
2726 = mctx->bkref_ents + cache_idx; 2640 = mctx->bkref_ents + cache_idx;
@@ -2756,7 +2670,8 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2756 at the back reference? */ 2670 at the back reference? */
2757 if (sl_str_diff > 0) 2671 if (sl_str_diff > 0)
2758 { 2672 {
2759 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0)) 2673 if (__glibc_unlikely (bkref_str_off + sl_str_diff
2674 > mctx->input.valid_len))
2760 { 2675 {
2761 /* Not enough chars for a successful match. */ 2676 /* Not enough chars for a successful match. */
2762 if (bkref_str_off + sl_str_diff > mctx->input.len) 2677 if (bkref_str_off + sl_str_diff > mctx->input.len)
@@ -2765,7 +2680,7 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2765 err = clean_state_log_if_needed (mctx, 2680 err = clean_state_log_if_needed (mctx,
2766 bkref_str_off 2681 bkref_str_off
2767 + sl_str_diff); 2682 + sl_str_diff);
2768 if (BE (err != REG_NOERROR, 0)) 2683 if (__glibc_unlikely (err != REG_NOERROR))
2769 return err; 2684 return err;
2770 buf = (const char *) re_string_get_buffer (&mctx->input); 2685 buf = (const char *) re_string_get_buffer (&mctx->input);
2771 } 2686 }
@@ -2784,7 +2699,7 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2784 2699
2785 if (err == REG_NOMATCH) 2700 if (err == REG_NOMATCH)
2786 continue; 2701 continue;
2787 if (BE (err != REG_NOERROR, 0)) 2702 if (__glibc_unlikely (err != REG_NOERROR))
2788 return err; 2703 return err;
2789 } 2704 }
2790 2705
@@ -2803,14 +2718,14 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2803 at the back reference? */ 2718 at the back reference? */
2804 if (sl_str_off > 0) 2719 if (sl_str_off > 0)
2805 { 2720 {
2806 if (BE (bkref_str_off >= mctx->input.valid_len, 0)) 2721 if (__glibc_unlikely (bkref_str_off >= mctx->input.valid_len))
2807 { 2722 {
2808 /* If we are at the end of the input, we cannot match. */ 2723 /* If we are at the end of the input, we cannot match. */
2809 if (bkref_str_off >= mctx->input.len) 2724 if (bkref_str_off >= mctx->input.len)
2810 break; 2725 break;
2811 2726
2812 err = extend_buffers (mctx, bkref_str_off + 1); 2727 err = extend_buffers (mctx, bkref_str_off + 1);
2813 if (BE (err != REG_NOERROR, 0)) 2728 if (__glibc_unlikely (err != REG_NOERROR))
2814 return err; 2729 return err;
2815 2730
2816 buf = (const char *) re_string_get_buffer (&mctx->input); 2731 buf = (const char *) re_string_get_buffer (&mctx->input);
@@ -2825,7 +2740,7 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2825 nodes = &mctx->state_log[sl_str]->nodes; 2740 nodes = &mctx->state_log[sl_str]->nodes;
2826 cls_node = find_subexp_node (dfa, nodes, subexp_num, 2741 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2827 OP_CLOSE_SUBEXP); 2742 OP_CLOSE_SUBEXP);
2828 if (cls_node == REG_MISSING) 2743 if (cls_node == -1)
2829 continue; /* No. */ 2744 continue; /* No. */
2830 if (sub_top->path == NULL) 2745 if (sub_top->path == NULL)
2831 { 2746 {
@@ -2841,15 +2756,18 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2841 OP_CLOSE_SUBEXP); 2756 OP_CLOSE_SUBEXP);
2842 if (err == REG_NOMATCH) 2757 if (err == REG_NOMATCH)
2843 continue; 2758 continue;
2844 if (BE (err != REG_NOERROR, 0)) 2759 if (__glibc_unlikely (err != REG_NOERROR))
2845 return err; 2760 return err;
2846 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str); 2761 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2847 if (BE (sub_last == NULL, 0)) 2762 if (__glibc_unlikely (sub_last == NULL))
2848 return REG_ESPACE; 2763 return REG_ESPACE;
2849 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node, 2764 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2850 bkref_str_idx); 2765 bkref_str_idx);
2766 buf = (const char *) re_string_get_buffer (&mctx->input);
2851 if (err == REG_NOMATCH) 2767 if (err == REG_NOMATCH)
2852 continue; 2768 continue;
2769 if (__glibc_unlikely (err != REG_NOERROR))
2770 return err;
2853 } 2771 }
2854 } 2772 }
2855 return REG_NOERROR; 2773 return REG_NOERROR;
@@ -2862,7 +2780,6 @@ get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2862 and SUB_LAST. */ 2780 and SUB_LAST. */
2863 2781
2864static reg_errcode_t 2782static reg_errcode_t
2865internal_function
2866get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top, 2783get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2867 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str) 2784 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2868{ 2785{
@@ -2876,7 +2793,7 @@ get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2876 return err; 2793 return err;
2877 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx, 2794 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2878 sub_last->str_idx); 2795 sub_last->str_idx);
2879 if (BE (err != REG_NOERROR, 0)) 2796 if (__glibc_unlikely (err != REG_NOERROR))
2880 return err; 2797 return err;
2881 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx; 2798 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2882 return clean_state_log_if_needed (mctx, to_idx); 2799 return clean_state_log_if_needed (mctx, to_idx);
@@ -2891,7 +2808,6 @@ get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2891 E.g. RE: (a){2} */ 2808 E.g. RE: (a){2} */
2892 2809
2893static Idx 2810static Idx
2894internal_function
2895find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes, 2811find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2896 Idx subexp_idx, int type) 2812 Idx subexp_idx, int type)
2897{ 2813{
@@ -2904,16 +2820,17 @@ find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2904 && node->opr.idx == subexp_idx) 2820 && node->opr.idx == subexp_idx)
2905 return cls_node; 2821 return cls_node;
2906 } 2822 }
2907 return REG_MISSING; 2823 return -1;
2908} 2824}
2909 2825
2910/* Check whether the node TOP_NODE at TOP_STR can arrive to the node 2826/* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2911 LAST_NODE at LAST_STR. We record the path onto PATH since it will be 2827 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2912 heavily reused. 2828 heavily reused.
2913 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */ 2829 Return REG_NOERROR if it can arrive, REG_NOMATCH if it cannot,
2830 REG_ESPACE if memory is exhausted. */
2914 2831
2915static reg_errcode_t 2832static reg_errcode_t
2916internal_function __attribute_warn_unused_result__ 2833__attribute_warn_unused_result__
2917check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node, 2834check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2918 Idx top_str, Idx last_node, Idx last_str, int type) 2835 Idx top_str, Idx last_node, Idx last_str, int type)
2919{ 2836{
@@ -2927,19 +2844,19 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2927 2844
2928 subexp_num = dfa->nodes[top_node].opr.idx; 2845 subexp_num = dfa->nodes[top_node].opr.idx;
2929 /* Extend the buffer if we need. */ 2846 /* Extend the buffer if we need. */
2930 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0)) 2847 if (__glibc_unlikely (path->alloc < last_str + mctx->max_mb_elem_len + 1))
2931 { 2848 {
2932 re_dfastate_t **new_array; 2849 re_dfastate_t **new_array;
2933 Idx old_alloc = path->alloc; 2850 Idx old_alloc = path->alloc;
2934 Idx incr_alloc = last_str + mctx->max_mb_elem_len + 1; 2851 Idx incr_alloc = last_str + mctx->max_mb_elem_len + 1;
2935 Idx new_alloc; 2852 Idx new_alloc;
2936 if (BE (IDX_MAX - old_alloc < incr_alloc, 0)) 2853 if (__glibc_unlikely (IDX_MAX - old_alloc < incr_alloc))
2937 return REG_ESPACE; 2854 return REG_ESPACE;
2938 new_alloc = old_alloc + incr_alloc; 2855 new_alloc = old_alloc + incr_alloc;
2939 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0)) 2856 if (__glibc_unlikely (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc))
2940 return REG_ESPACE; 2857 return REG_ESPACE;
2941 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc); 2858 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2942 if (BE (new_array == NULL, 0)) 2859 if (__glibc_unlikely (new_array == NULL))
2943 return REG_ESPACE; 2860 return REG_ESPACE;
2944 path->array = new_array; 2861 path->array = new_array;
2945 path->alloc = new_alloc; 2862 path->alloc = new_alloc;
@@ -2960,10 +2877,10 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2960 if (str_idx == top_str) 2877 if (str_idx == top_str)
2961 { 2878 {
2962 err = re_node_set_init_1 (&next_nodes, top_node); 2879 err = re_node_set_init_1 (&next_nodes, top_node);
2963 if (BE (err != REG_NOERROR, 0)) 2880 if (__glibc_unlikely (err != REG_NOERROR))
2964 return err; 2881 return err;
2965 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type); 2882 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2966 if (BE (err != REG_NOERROR, 0)) 2883 if (__glibc_unlikely (err != REG_NOERROR))
2967 { 2884 {
2968 re_node_set_free (&next_nodes); 2885 re_node_set_free (&next_nodes);
2969 return err; 2886 return err;
@@ -2975,7 +2892,7 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2975 if (cur_state && cur_state->has_backref) 2892 if (cur_state && cur_state->has_backref)
2976 { 2893 {
2977 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes); 2894 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2978 if (BE (err != REG_NOERROR, 0)) 2895 if (__glibc_unlikely (err != REG_NOERROR))
2979 return err; 2896 return err;
2980 } 2897 }
2981 else 2898 else
@@ -2987,14 +2904,14 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2987 { 2904 {
2988 err = expand_bkref_cache (mctx, &next_nodes, str_idx, 2905 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2989 subexp_num, type); 2906 subexp_num, type);
2990 if (BE (err != REG_NOERROR, 0)) 2907 if (__glibc_unlikely (err != REG_NOERROR))
2991 { 2908 {
2992 re_node_set_free (&next_nodes); 2909 re_node_set_free (&next_nodes);
2993 return err; 2910 return err;
2994 } 2911 }
2995 } 2912 }
2996 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context); 2913 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2997 if (BE (cur_state == NULL && err != REG_NOERROR, 0)) 2914 if (__glibc_unlikely (cur_state == NULL && err != REG_NOERROR))
2998 { 2915 {
2999 re_node_set_free (&next_nodes); 2916 re_node_set_free (&next_nodes);
3000 return err; 2917 return err;
@@ -3009,7 +2926,7 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
3009 { 2926 {
3010 err = re_node_set_merge (&next_nodes, 2927 err = re_node_set_merge (&next_nodes,
3011 &mctx->state_log[str_idx + 1]->nodes); 2928 &mctx->state_log[str_idx + 1]->nodes);
3012 if (BE (err != REG_NOERROR, 0)) 2929 if (__glibc_unlikely (err != REG_NOERROR))
3013 { 2930 {
3014 re_node_set_free (&next_nodes); 2931 re_node_set_free (&next_nodes);
3015 return err; 2932 return err;
@@ -3020,7 +2937,7 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
3020 err = check_arrival_add_next_nodes (mctx, str_idx, 2937 err = check_arrival_add_next_nodes (mctx, str_idx,
3021 &cur_state->non_eps_nodes, 2938 &cur_state->non_eps_nodes,
3022 &next_nodes); 2939 &next_nodes);
3023 if (BE (err != REG_NOERROR, 0)) 2940 if (__glibc_unlikely (err != REG_NOERROR))
3024 { 2941 {
3025 re_node_set_free (&next_nodes); 2942 re_node_set_free (&next_nodes);
3026 return err; 2943 return err;
@@ -3030,14 +2947,14 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
3030 if (next_nodes.nelem) 2947 if (next_nodes.nelem)
3031 { 2948 {
3032 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type); 2949 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3033 if (BE (err != REG_NOERROR, 0)) 2950 if (__glibc_unlikely (err != REG_NOERROR))
3034 { 2951 {
3035 re_node_set_free (&next_nodes); 2952 re_node_set_free (&next_nodes);
3036 return err; 2953 return err;
3037 } 2954 }
3038 err = expand_bkref_cache (mctx, &next_nodes, str_idx, 2955 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3039 subexp_num, type); 2956 subexp_num, type);
3040 if (BE (err != REG_NOERROR, 0)) 2957 if (__glibc_unlikely (err != REG_NOERROR))
3041 { 2958 {
3042 re_node_set_free (&next_nodes); 2959 re_node_set_free (&next_nodes);
3043 return err; 2960 return err;
@@ -3045,7 +2962,7 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
3045 } 2962 }
3046 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags); 2963 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3047 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context); 2964 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3048 if (BE (cur_state == NULL && err != REG_NOERROR, 0)) 2965 if (__glibc_unlikely (cur_state == NULL && err != REG_NOERROR))
3049 { 2966 {
3050 re_node_set_free (&next_nodes); 2967 re_node_set_free (&next_nodes);
3051 return err; 2968 return err;
@@ -3078,7 +2995,7 @@ check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
3078 Can't we unify them? */ 2995 Can't we unify them? */
3079 2996
3080static reg_errcode_t 2997static reg_errcode_t
3081internal_function __attribute_warn_unused_result__ 2998__attribute_warn_unused_result__
3082check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx, 2999check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3083 re_node_set *cur_nodes, re_node_set *next_nodes) 3000 re_node_set *cur_nodes, re_node_set *next_nodes)
3084{ 3001{
@@ -3094,10 +3011,8 @@ check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3094 { 3011 {
3095 int naccepted = 0; 3012 int naccepted = 0;
3096 Idx cur_node = cur_nodes->elems[cur_idx]; 3013 Idx cur_node = cur_nodes->elems[cur_idx];
3097#ifdef DEBUG 3014 DEBUG_ASSERT (!IS_EPSILON_NODE (dfa->nodes[cur_node].type));
3098 re_token_type_t type = dfa->nodes[cur_node].type; 3015
3099 assert (!IS_EPSILON_NODE (type));
3100#endif
3101#ifdef RE_ENABLE_I18N 3016#ifdef RE_ENABLE_I18N
3102 /* If the node may accept "multi byte". */ 3017 /* If the node may accept "multi byte". */
3103 if (dfa->nodes[cur_node].accept_mb) 3018 if (dfa->nodes[cur_node].accept_mb)
@@ -3114,22 +3029,22 @@ check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3114 if (dest_state) 3029 if (dest_state)
3115 { 3030 {
3116 err = re_node_set_merge (&union_set, &dest_state->nodes); 3031 err = re_node_set_merge (&union_set, &dest_state->nodes);
3117 if (BE (err != REG_NOERROR, 0)) 3032 if (__glibc_unlikely (err != REG_NOERROR))
3118 { 3033 {
3119 re_node_set_free (&union_set); 3034 re_node_set_free (&union_set);
3120 return err; 3035 return err;
3121 } 3036 }
3122 } 3037 }
3123 ok = re_node_set_insert (&union_set, next_node); 3038 ok = re_node_set_insert (&union_set, next_node);
3124 if (BE (! ok, 0)) 3039 if (__glibc_unlikely (! ok))
3125 { 3040 {
3126 re_node_set_free (&union_set); 3041 re_node_set_free (&union_set);
3127 return REG_ESPACE; 3042 return REG_ESPACE;
3128 } 3043 }
3129 mctx->state_log[next_idx] = re_acquire_state (&err, dfa, 3044 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3130 &union_set); 3045 &union_set);
3131 if (BE (mctx->state_log[next_idx] == NULL 3046 if (__glibc_unlikely (mctx->state_log[next_idx] == NULL
3132 && err != REG_NOERROR, 0)) 3047 && err != REG_NOERROR))
3133 { 3048 {
3134 re_node_set_free (&union_set); 3049 re_node_set_free (&union_set);
3135 return err; 3050 return err;
@@ -3141,7 +3056,7 @@ check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3141 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx)) 3056 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3142 { 3057 {
3143 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]); 3058 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3144 if (BE (! ok, 0)) 3059 if (__glibc_unlikely (! ok))
3145 { 3060 {
3146 re_node_set_free (&union_set); 3061 re_node_set_free (&union_set);
3147 return REG_ESPACE; 3062 return REG_ESPACE;
@@ -3159,18 +3074,15 @@ check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3159*/ 3074*/
3160 3075
3161static reg_errcode_t 3076static reg_errcode_t
3162internal_function
3163check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes, 3077check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3164 Idx ex_subexp, int type) 3078 Idx ex_subexp, int type)
3165{ 3079{
3166 reg_errcode_t err; 3080 reg_errcode_t err;
3167 Idx idx, outside_node; 3081 Idx idx, outside_node;
3168 re_node_set new_nodes; 3082 re_node_set new_nodes;
3169#ifdef DEBUG 3083 DEBUG_ASSERT (cur_nodes->nelem);
3170 assert (cur_nodes->nelem);
3171#endif
3172 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem); 3084 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3173 if (BE (err != REG_NOERROR, 0)) 3085 if (__glibc_unlikely (err != REG_NOERROR))
3174 return err; 3086 return err;
3175 /* Create a new node set NEW_NODES with the nodes which are epsilon 3087 /* Create a new node set NEW_NODES with the nodes which are epsilon
3176 closures of the node in CUR_NODES. */ 3088 closures of the node in CUR_NODES. */
@@ -3180,11 +3092,11 @@ check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3180 Idx cur_node = cur_nodes->elems[idx]; 3092 Idx cur_node = cur_nodes->elems[idx];
3181 const re_node_set *eclosure = dfa->eclosures + cur_node; 3093 const re_node_set *eclosure = dfa->eclosures + cur_node;
3182 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type); 3094 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3183 if (outside_node == REG_MISSING) 3095 if (outside_node == -1)
3184 { 3096 {
3185 /* There are no problematic nodes, just merge them. */ 3097 /* There are no problematic nodes, just merge them. */
3186 err = re_node_set_merge (&new_nodes, eclosure); 3098 err = re_node_set_merge (&new_nodes, eclosure);
3187 if (BE (err != REG_NOERROR, 0)) 3099 if (__glibc_unlikely (err != REG_NOERROR))
3188 { 3100 {
3189 re_node_set_free (&new_nodes); 3101 re_node_set_free (&new_nodes);
3190 return err; 3102 return err;
@@ -3195,7 +3107,7 @@ check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3195 /* There are problematic nodes, re-calculate incrementally. */ 3107 /* There are problematic nodes, re-calculate incrementally. */
3196 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node, 3108 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3197 ex_subexp, type); 3109 ex_subexp, type);
3198 if (BE (err != REG_NOERROR, 0)) 3110 if (__glibc_unlikely (err != REG_NOERROR))
3199 { 3111 {
3200 re_node_set_free (&new_nodes); 3112 re_node_set_free (&new_nodes);
3201 return err; 3113 return err;
@@ -3212,7 +3124,7 @@ check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3212 problematic append it to DST_NODES. */ 3124 problematic append it to DST_NODES. */
3213 3125
3214static reg_errcode_t 3126static reg_errcode_t
3215internal_function __attribute_warn_unused_result__ 3127__attribute_warn_unused_result__
3216check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes, 3128check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3217 Idx target, Idx ex_subexp, int type) 3129 Idx target, Idx ex_subexp, int type)
3218{ 3130{
@@ -3227,13 +3139,13 @@ check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3227 if (type == OP_CLOSE_SUBEXP) 3139 if (type == OP_CLOSE_SUBEXP)
3228 { 3140 {
3229 ok = re_node_set_insert (dst_nodes, cur_node); 3141 ok = re_node_set_insert (dst_nodes, cur_node);
3230 if (BE (! ok, 0)) 3142 if (__glibc_unlikely (! ok))
3231 return REG_ESPACE; 3143 return REG_ESPACE;
3232 } 3144 }
3233 break; 3145 break;
3234 } 3146 }
3235 ok = re_node_set_insert (dst_nodes, cur_node); 3147 ok = re_node_set_insert (dst_nodes, cur_node);
3236 if (BE (! ok, 0)) 3148 if (__glibc_unlikely (! ok))
3237 return REG_ESPACE; 3149 return REG_ESPACE;
3238 if (dfa->edests[cur_node].nelem == 0) 3150 if (dfa->edests[cur_node].nelem == 0)
3239 break; 3151 break;
@@ -3243,7 +3155,7 @@ check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3243 err = check_arrival_expand_ecl_sub (dfa, dst_nodes, 3155 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3244 dfa->edests[cur_node].elems[1], 3156 dfa->edests[cur_node].elems[1],
3245 ex_subexp, type); 3157 ex_subexp, type);
3246 if (BE (err != REG_NOERROR, 0)) 3158 if (__glibc_unlikely (err != REG_NOERROR))
3247 return err; 3159 return err;
3248 } 3160 }
3249 cur_node = dfa->edests[cur_node].elems[0]; 3161 cur_node = dfa->edests[cur_node].elems[0];
@@ -3257,7 +3169,7 @@ check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3257 in MCTX->BKREF_ENTS. */ 3169 in MCTX->BKREF_ENTS. */
3258 3170
3259static reg_errcode_t 3171static reg_errcode_t
3260internal_function __attribute_warn_unused_result__ 3172__attribute_warn_unused_result__
3261expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes, 3173expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3262 Idx cur_str, Idx subexp_num, int type) 3174 Idx cur_str, Idx subexp_num, int type)
3263{ 3175{
@@ -3266,7 +3178,7 @@ expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3266 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str); 3178 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3267 struct re_backref_cache_entry *ent; 3179 struct re_backref_cache_entry *ent;
3268 3180
3269 if (cache_idx_start == REG_MISSING) 3181 if (cache_idx_start == -1)
3270 return REG_NOERROR; 3182 return REG_NOERROR;
3271 3183
3272 restart: 3184 restart:
@@ -3295,8 +3207,8 @@ expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3295 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type); 3207 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3296 err3 = re_node_set_merge (cur_nodes, &new_dests); 3208 err3 = re_node_set_merge (cur_nodes, &new_dests);
3297 re_node_set_free (&new_dests); 3209 re_node_set_free (&new_dests);
3298 if (BE (err != REG_NOERROR || err2 != REG_NOERROR 3210 if (__glibc_unlikely (err != REG_NOERROR || err2 != REG_NOERROR
3299 || err3 != REG_NOERROR, 0)) 3211 || err3 != REG_NOERROR))
3300 { 3212 {
3301 err = (err != REG_NOERROR ? err 3213 err = (err != REG_NOERROR ? err
3302 : (err2 != REG_NOERROR ? err2 : err3)); 3214 : (err2 != REG_NOERROR ? err2 : err3));
@@ -3318,7 +3230,7 @@ expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3318 err = re_node_set_init_copy (&union_set, 3230 err = re_node_set_init_copy (&union_set,
3319 &mctx->state_log[to_idx]->nodes); 3231 &mctx->state_log[to_idx]->nodes);
3320 ok = re_node_set_insert (&union_set, next_node); 3232 ok = re_node_set_insert (&union_set, next_node);
3321 if (BE (err != REG_NOERROR || ! ok, 0)) 3233 if (__glibc_unlikely (err != REG_NOERROR || ! ok))
3322 { 3234 {
3323 re_node_set_free (&union_set); 3235 re_node_set_free (&union_set);
3324 err = err != REG_NOERROR ? err : REG_ESPACE; 3236 err = err != REG_NOERROR ? err : REG_ESPACE;
@@ -3328,13 +3240,13 @@ expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3328 else 3240 else
3329 { 3241 {
3330 err = re_node_set_init_1 (&union_set, next_node); 3242 err = re_node_set_init_1 (&union_set, next_node);
3331 if (BE (err != REG_NOERROR, 0)) 3243 if (__glibc_unlikely (err != REG_NOERROR))
3332 return err; 3244 return err;
3333 } 3245 }
3334 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set); 3246 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3335 re_node_set_free (&union_set); 3247 re_node_set_free (&union_set);
3336 if (BE (mctx->state_log[to_idx] == NULL 3248 if (__glibc_unlikely (mctx->state_log[to_idx] == NULL
3337 && err != REG_NOERROR, 0)) 3249 && err != REG_NOERROR))
3338 return err; 3250 return err;
3339 } 3251 }
3340 } 3252 }
@@ -3345,8 +3257,7 @@ expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3345/* Build transition table for the state. 3257/* Build transition table for the state.
3346 Return true if successful. */ 3258 Return true if successful. */
3347 3259
3348static bool 3260static bool __attribute_noinline__
3349internal_function
3350build_trtable (const re_dfa_t *dfa, re_dfastate_t *state) 3261build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3351{ 3262{
3352 reg_errcode_t err; 3263 reg_errcode_t err;
@@ -3354,36 +3265,20 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3354 int ch; 3265 int ch;
3355 bool need_word_trtable = false; 3266 bool need_word_trtable = false;
3356 bitset_word_t elem, mask; 3267 bitset_word_t elem, mask;
3357 bool dests_node_malloced = false;
3358 bool dest_states_malloced = false;
3359 Idx ndests; /* Number of the destination states from 'state'. */ 3268 Idx ndests; /* Number of the destination states from 'state'. */
3360 re_dfastate_t **trtable; 3269 re_dfastate_t **trtable;
3361 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl; 3270 re_dfastate_t *dest_states[SBC_MAX];
3362 re_node_set follows, *dests_node; 3271 re_dfastate_t *dest_states_word[SBC_MAX];
3363 bitset_t *dests_ch; 3272 re_dfastate_t *dest_states_nl[SBC_MAX];
3273 re_node_set follows;
3364 bitset_t acceptable; 3274 bitset_t acceptable;
3365 3275
3366 struct dests_alloc
3367 {
3368 re_node_set dests_node[SBC_MAX];
3369 bitset_t dests_ch[SBC_MAX];
3370 } *dests_alloc;
3371
3372 /* We build DFA states which corresponds to the destination nodes 3276 /* We build DFA states which corresponds to the destination nodes
3373 from 'state'. 'dests_node[i]' represents the nodes which i-th 3277 from 'state'. 'dests_node[i]' represents the nodes which i-th
3374 destination state contains, and 'dests_ch[i]' represents the 3278 destination state contains, and 'dests_ch[i]' represents the
3375 characters which i-th destination state accepts. */ 3279 characters which i-th destination state accepts. */
3376 if (__libc_use_alloca (sizeof (struct dests_alloc))) 3280 re_node_set dests_node[SBC_MAX];
3377 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc)); 3281 bitset_t dests_ch[SBC_MAX];
3378 else
3379 {
3380 dests_alloc = re_malloc (struct dests_alloc, 1);
3381 if (BE (dests_alloc == NULL, 0))
3382 return false;
3383 dests_node_malloced = true;
3384 }
3385 dests_node = dests_alloc->dests_node;
3386 dests_ch = dests_alloc->dests_ch;
3387 3282
3388 /* Initialize transition table. */ 3283 /* Initialize transition table. */
3389 state->word_trtable = state->trtable = NULL; 3284 state->word_trtable = state->trtable = NULL;
@@ -3391,16 +3286,14 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3391 /* At first, group all nodes belonging to 'state' into several 3286 /* At first, group all nodes belonging to 'state' into several
3392 destinations. */ 3287 destinations. */
3393 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch); 3288 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3394 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0)) 3289 if (__glibc_unlikely (ndests <= 0))
3395 { 3290 {
3396 if (dests_node_malloced)
3397 free (dests_alloc);
3398 /* Return false in case of an error, true otherwise. */ 3291 /* Return false in case of an error, true otherwise. */
3399 if (ndests == 0) 3292 if (ndests == 0)
3400 { 3293 {
3401 state->trtable = (re_dfastate_t **) 3294 state->trtable = (re_dfastate_t **)
3402 calloc (sizeof (re_dfastate_t *), SBC_MAX); 3295 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3403 if (BE (state->trtable == NULL, 0)) 3296 if (__glibc_unlikely (state->trtable == NULL))
3404 return false; 3297 return false;
3405 return true; 3298 return true;
3406 } 3299 }
@@ -3408,40 +3301,15 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3408 } 3301 }
3409 3302
3410 err = re_node_set_alloc (&follows, ndests + 1); 3303 err = re_node_set_alloc (&follows, ndests + 1);
3411 if (BE (err != REG_NOERROR, 0)) 3304 if (__glibc_unlikely (err != REG_NOERROR))
3412 goto out_free;
3413
3414 /* Avoid arithmetic overflow in size calculation. */
3415 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3416 / (3 * sizeof (re_dfastate_t *)))
3417 < ndests),
3418 0))
3419 goto out_free;
3420
3421 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3422 + ndests * 3 * sizeof (re_dfastate_t *)))
3423 dest_states = (re_dfastate_t **)
3424 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3425 else
3426 { 3305 {
3427 dest_states = (re_dfastate_t **) 3306 out_free:
3428 malloc (ndests * 3 * sizeof (re_dfastate_t *)); 3307 re_node_set_free (&follows);
3429 if (BE (dest_states == NULL, 0)) 3308 for (i = 0; i < ndests; ++i)
3430 { 3309 re_node_set_free (dests_node + i);
3431out_free: 3310 return false;
3432 if (dest_states_malloced)
3433 free (dest_states);
3434 re_node_set_free (&follows);
3435 for (i = 0; i < ndests; ++i)
3436 re_node_set_free (dests_node + i);
3437 if (dests_node_malloced)
3438 free (dests_alloc);
3439 return false;
3440 }
3441 dest_states_malloced = true;
3442 } 3311 }
3443 dest_states_word = dest_states + ndests; 3312
3444 dest_states_nl = dest_states_word + ndests;
3445 bitset_empty (acceptable); 3313 bitset_empty (acceptable);
3446 3314
3447 /* Then build the states for all destinations. */ 3315 /* Then build the states for all destinations. */
@@ -3453,15 +3321,15 @@ out_free:
3453 for (j = 0; j < dests_node[i].nelem; ++j) 3321 for (j = 0; j < dests_node[i].nelem; ++j)
3454 { 3322 {
3455 next_node = dfa->nexts[dests_node[i].elems[j]]; 3323 next_node = dfa->nexts[dests_node[i].elems[j]];
3456 if (next_node != REG_MISSING) 3324 if (next_node != -1)
3457 { 3325 {
3458 err = re_node_set_merge (&follows, dfa->eclosures + next_node); 3326 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3459 if (BE (err != REG_NOERROR, 0)) 3327 if (__glibc_unlikely (err != REG_NOERROR))
3460 goto out_free; 3328 goto out_free;
3461 } 3329 }
3462 } 3330 }
3463 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0); 3331 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3464 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0)) 3332 if (__glibc_unlikely (dest_states[i] == NULL && err != REG_NOERROR))
3465 goto out_free; 3333 goto out_free;
3466 /* If the new state has context constraint, 3334 /* If the new state has context constraint,
3467 build appropriate states for these contexts. */ 3335 build appropriate states for these contexts. */
@@ -3469,7 +3337,8 @@ out_free:
3469 { 3337 {
3470 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows, 3338 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3471 CONTEXT_WORD); 3339 CONTEXT_WORD);
3472 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0)) 3340 if (__glibc_unlikely (dest_states_word[i] == NULL
3341 && err != REG_NOERROR))
3473 goto out_free; 3342 goto out_free;
3474 3343
3475 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1) 3344 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
@@ -3477,7 +3346,7 @@ out_free:
3477 3346
3478 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows, 3347 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3479 CONTEXT_NEWLINE); 3348 CONTEXT_NEWLINE);
3480 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0)) 3349 if (__glibc_unlikely (dest_states_nl[i] == NULL && err != REG_NOERROR))
3481 goto out_free; 3350 goto out_free;
3482 } 3351 }
3483 else 3352 else
@@ -3488,7 +3357,7 @@ out_free:
3488 bitset_merge (acceptable, dests_ch[i]); 3357 bitset_merge (acceptable, dests_ch[i]);
3489 } 3358 }
3490 3359
3491 if (!BE (need_word_trtable, 0)) 3360 if (!__glibc_unlikely (need_word_trtable))
3492 { 3361 {
3493 /* We don't care about whether the following character is a word 3362 /* We don't care about whether the following character is a word
3494 character, or we are in a single-byte character set so we can 3363 character, or we are in a single-byte character set so we can
@@ -3496,7 +3365,7 @@ out_free:
3496 256-entry transition table. */ 3365 256-entry transition table. */
3497 trtable = state->trtable = 3366 trtable = state->trtable =
3498 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX); 3367 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3499 if (BE (trtable == NULL, 0)) 3368 if (__glibc_unlikely (trtable == NULL))
3500 goto out_free; 3369 goto out_free;
3501 3370
3502 /* For all characters ch...: */ 3371 /* For all characters ch...: */
@@ -3504,7 +3373,7 @@ out_free:
3504 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1; 3373 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3505 elem; 3374 elem;
3506 mask <<= 1, elem >>= 1, ++ch) 3375 mask <<= 1, elem >>= 1, ++ch)
3507 if (BE (elem & 1, 0)) 3376 if (__glibc_unlikely (elem & 1))
3508 { 3377 {
3509 /* There must be exactly one destination which accepts 3378 /* There must be exactly one destination which accepts
3510 character ch. See group_nodes_into_DFAstates. */ 3379 character ch. See group_nodes_into_DFAstates. */
@@ -3527,7 +3396,7 @@ out_free:
3527 starting at trtable[SBC_MAX]. */ 3396 starting at trtable[SBC_MAX]. */
3528 trtable = state->word_trtable = 3397 trtable = state->word_trtable =
3529 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX); 3398 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3530 if (BE (trtable == NULL, 0)) 3399 if (__glibc_unlikely (trtable == NULL))
3531 goto out_free; 3400 goto out_free;
3532 3401
3533 /* For all characters ch...: */ 3402 /* For all characters ch...: */
@@ -3535,7 +3404,7 @@ out_free:
3535 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1; 3404 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3536 elem; 3405 elem;
3537 mask <<= 1, elem >>= 1, ++ch) 3406 mask <<= 1, elem >>= 1, ++ch)
3538 if (BE (elem & 1, 0)) 3407 if (__glibc_unlikely (elem & 1))
3539 { 3408 {
3540 /* There must be exactly one destination which accepts 3409 /* There must be exactly one destination which accepts
3541 character ch. See group_nodes_into_DFAstates. */ 3410 character ch. See group_nodes_into_DFAstates. */
@@ -3565,26 +3434,19 @@ out_free:
3565 } 3434 }
3566 } 3435 }
3567 3436
3568 if (dest_states_malloced)
3569 free (dest_states);
3570
3571 re_node_set_free (&follows); 3437 re_node_set_free (&follows);
3572 for (i = 0; i < ndests; ++i) 3438 for (i = 0; i < ndests; ++i)
3573 re_node_set_free (dests_node + i); 3439 re_node_set_free (dests_node + i);
3574
3575 if (dests_node_malloced)
3576 free (dests_alloc);
3577
3578 return true; 3440 return true;
3579} 3441}
3580 3442
3581/* Group all nodes belonging to STATE into several destinations. 3443/* Group all nodes belonging to STATE into several destinations.
3582 Then for all destinations, set the nodes belonging to the destination 3444 Then for all destinations, set the nodes belonging to the destination
3583 to DESTS_NODE[i] and set the characters accepted by the destination 3445 to DESTS_NODE[i] and set the characters accepted by the destination
3584 to DEST_CH[i]. This function return the number of destinations. */ 3446 to DEST_CH[i]. Return the number of destinations if successful,
3447 -1 on internal error. */
3585 3448
3586static Idx 3449static Idx
3587internal_function
3588group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state, 3450group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3589 re_node_set *dests_node, bitset_t *dests_ch) 3451 re_node_set *dests_node, bitset_t *dests_ch)
3590{ 3452{
@@ -3735,14 +3597,14 @@ group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3735 bitset_copy (dests_ch[ndests], remains); 3597 bitset_copy (dests_ch[ndests], remains);
3736 bitset_copy (dests_ch[j], intersec); 3598 bitset_copy (dests_ch[j], intersec);
3737 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]); 3599 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3738 if (BE (err != REG_NOERROR, 0)) 3600 if (__glibc_unlikely (err != REG_NOERROR))
3739 goto error_return; 3601 goto error_return;
3740 ++ndests; 3602 ++ndests;
3741 } 3603 }
3742 3604
3743 /* Put the position in the current group. */ 3605 /* Put the position in the current group. */
3744 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]); 3606 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3745 if (BE (! ok, 0)) 3607 if (__glibc_unlikely (! ok))
3746 goto error_return; 3608 goto error_return;
3747 3609
3748 /* If all characters are consumed, go to next node. */ 3610 /* If all characters are consumed, go to next node. */
@@ -3754,17 +3616,18 @@ group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3754 { 3616 {
3755 bitset_copy (dests_ch[ndests], accepts); 3617 bitset_copy (dests_ch[ndests], accepts);
3756 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]); 3618 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3757 if (BE (err != REG_NOERROR, 0)) 3619 if (__glibc_unlikely (err != REG_NOERROR))
3758 goto error_return; 3620 goto error_return;
3759 ++ndests; 3621 ++ndests;
3760 bitset_empty (accepts); 3622 bitset_empty (accepts);
3761 } 3623 }
3762 } 3624 }
3625 assume (ndests <= SBC_MAX);
3763 return ndests; 3626 return ndests;
3764 error_return: 3627 error_return:
3765 for (j = 0; j < ndests; ++j) 3628 for (j = 0; j < ndests; ++j)
3766 re_node_set_free (dests_node + j); 3629 re_node_set_free (dests_node + j);
3767 return REG_MISSING; 3630 return -1;
3768} 3631}
3769 3632
3770#ifdef RE_ENABLE_I18N 3633#ifdef RE_ENABLE_I18N
@@ -3776,8 +3639,11 @@ group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3776 one collating element like '.', '[a-z]', opposite to the other nodes 3639 one collating element like '.', '[a-z]', opposite to the other nodes
3777 can only accept one byte. */ 3640 can only accept one byte. */
3778 3641
3642# ifdef _LIBC
3643# include <locale/weight.h>
3644# endif
3645
3779static int 3646static int
3780internal_function
3781check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx, 3647check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3782 const re_string_t *input, Idx str_idx) 3648 const re_string_t *input, Idx str_idx)
3783{ 3649{
@@ -3785,10 +3651,10 @@ check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3785 int char_len, elem_len; 3651 int char_len, elem_len;
3786 Idx i; 3652 Idx i;
3787 3653
3788 if (BE (node->type == OP_UTF8_PERIOD, 0)) 3654 if (__glibc_unlikely (node->type == OP_UTF8_PERIOD))
3789 { 3655 {
3790 unsigned char c = re_string_byte_at (input, str_idx), d; 3656 unsigned char c = re_string_byte_at (input, str_idx), d;
3791 if (BE (c < 0xc2, 1)) 3657 if (__glibc_likely (c < 0xc2))
3792 return 0; 3658 return 0;
3793 3659
3794 if (str_idx + 2 > input->len) 3660 if (str_idx + 2 > input->len)
@@ -3844,10 +3710,10 @@ check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3844 /* FIXME: I don't think this if is needed, as both '\n' 3710 /* FIXME: I don't think this if is needed, as both '\n'
3845 and '\0' are char_len == 1. */ 3711 and '\0' are char_len == 1. */
3846 /* '.' accepts any one character except the following two cases. */ 3712 /* '.' accepts any one character except the following two cases. */
3847 if ((!(dfa->syntax & RE_DOT_NEWLINE) && 3713 if ((!(dfa->syntax & RE_DOT_NEWLINE)
3848 re_string_byte_at (input, str_idx) == '\n') || 3714 && re_string_byte_at (input, str_idx) == '\n')
3849 ((dfa->syntax & RE_DOT_NOT_NULL) && 3715 || ((dfa->syntax & RE_DOT_NOT_NULL)
3850 re_string_byte_at (input, str_idx) == '\0')) 3716 && re_string_byte_at (input, str_idx) == '\0'))
3851 return 0; 3717 return 0;
3852 return char_len; 3718 return char_len;
3853 } 3719 }
@@ -3895,8 +3761,6 @@ check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3895 const int32_t *table, *indirect; 3761 const int32_t *table, *indirect;
3896 const unsigned char *weights, *extra; 3762 const unsigned char *weights, *extra;
3897 const char *collseqwc; 3763 const char *collseqwc;
3898 /* This #include defines a local function! */
3899# include <locale/weight.h>
3900 3764
3901 /* match with collating_symbol? */ 3765 /* match with collating_symbol? */
3902 if (cset->ncoll_syms) 3766 if (cset->ncoll_syms)
@@ -3953,31 +3817,28 @@ check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3953 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB); 3817 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3954 indirect = (const int32_t *) 3818 indirect = (const int32_t *)
3955 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB); 3819 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3956 int32_t idx = findidx (&cp, elem_len); 3820 int32_t idx = findidx (table, indirect, extra, &cp, elem_len);
3821 int32_t rule = idx >> 24;
3822 idx &= 0xffffff;
3957 if (idx > 0) 3823 if (idx > 0)
3958 for (i = 0; i < cset->nequiv_classes; ++i) 3824 {
3959 { 3825 size_t weight_len = weights[idx];
3960 int32_t equiv_class_idx = cset->equiv_classes[i]; 3826 for (i = 0; i < cset->nequiv_classes; ++i)
3961 size_t weight_len = weights[idx & 0xffffff]; 3827 {
3962 if (weight_len == weights[equiv_class_idx & 0xffffff] 3828 int32_t equiv_class_idx = cset->equiv_classes[i];
3963 && (idx >> 24) == (equiv_class_idx >> 24)) 3829 int32_t equiv_class_rule = equiv_class_idx >> 24;
3964 { 3830 equiv_class_idx &= 0xffffff;
3965 Idx cnt = 0; 3831 if (weights[equiv_class_idx] == weight_len
3966 3832 && equiv_class_rule == rule
3967 idx &= 0xffffff; 3833 && memcmp (weights + idx + 1,
3968 equiv_class_idx &= 0xffffff; 3834 weights + equiv_class_idx + 1,
3969 3835 weight_len) == 0)
3970 while (cnt <= weight_len 3836 {
3971 && (weights[equiv_class_idx + 1 + cnt] 3837 match_len = elem_len;
3972 == weights[idx + 1 + cnt])) 3838 goto check_node_accept_bytes_match;
3973 ++cnt; 3839 }
3974 if (cnt > weight_len) 3840 }
3975 { 3841 }
3976 match_len = elem_len;
3977 goto check_node_accept_bytes_match;
3978 }
3979 }
3980 }
3981 } 3842 }
3982 } 3843 }
3983 else 3844 else
@@ -4009,7 +3870,6 @@ check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
4009 3870
4010# ifdef _LIBC 3871# ifdef _LIBC
4011static unsigned int 3872static unsigned int
4012internal_function
4013find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len) 3873find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4014{ 3874{
4015 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES); 3875 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
@@ -4073,7 +3933,6 @@ find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4073 byte of the INPUT. */ 3933 byte of the INPUT. */
4074 3934
4075static bool 3935static bool
4076internal_function
4077check_node_accept (const re_match_context_t *mctx, const re_token_t *node, 3936check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4078 Idx idx) 3937 Idx idx)
4079{ 3938{
@@ -4095,7 +3954,7 @@ check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4095 case OP_UTF8_PERIOD: 3954 case OP_UTF8_PERIOD:
4096 if (ch >= ASCII_CHARS) 3955 if (ch >= ASCII_CHARS)
4097 return false; 3956 return false;
4098 /* FALLTHROUGH */ 3957 FALLTHROUGH;
4099#endif 3958#endif
4100 case OP_PERIOD: 3959 case OP_PERIOD:
4101 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE)) 3960 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
@@ -4123,22 +3982,22 @@ check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4123/* Extend the buffers, if the buffers have run out. */ 3982/* Extend the buffers, if the buffers have run out. */
4124 3983
4125static reg_errcode_t 3984static reg_errcode_t
4126internal_function __attribute_warn_unused_result__ 3985__attribute_warn_unused_result__
4127extend_buffers (re_match_context_t *mctx, int min_len) 3986extend_buffers (re_match_context_t *mctx, int min_len)
4128{ 3987{
4129 reg_errcode_t ret; 3988 reg_errcode_t ret;
4130 re_string_t *pstr = &mctx->input; 3989 re_string_t *pstr = &mctx->input;
4131 3990
4132 /* Avoid overflow. */ 3991 /* Avoid overflow. */
4133 if (BE (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) / 2 3992 if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) / 2
4134 <= pstr->bufs_len, 0)) 3993 <= pstr->bufs_len))
4135 return REG_ESPACE; 3994 return REG_ESPACE;
4136 3995
4137 /* Double the lengths of the buffers, but allocate at least MIN_LEN. */ 3996 /* Double the lengths of the buffers, but allocate at least MIN_LEN. */
4138 ret = re_string_realloc_buffers (pstr, 3997 ret = re_string_realloc_buffers (pstr,
4139 MAX (min_len, 3998 MAX (min_len,
4140 MIN (pstr->len, pstr->bufs_len * 2))); 3999 MIN (pstr->len, pstr->bufs_len * 2)));
4141 if (BE (ret != REG_NOERROR, 0)) 4000 if (__glibc_unlikely (ret != REG_NOERROR))
4142 return ret; 4001 return ret;
4143 4002
4144 if (mctx->state_log != NULL) 4003 if (mctx->state_log != NULL)
@@ -4149,7 +4008,7 @@ extend_buffers (re_match_context_t *mctx, int min_len)
4149 does not have the right size. */ 4008 does not have the right size. */
4150 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *, 4009 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4151 pstr->bufs_len + 1); 4010 pstr->bufs_len + 1);
4152 if (BE (new_array == NULL, 0)) 4011 if (__glibc_unlikely (new_array == NULL))
4153 return REG_ESPACE; 4012 return REG_ESPACE;
4154 mctx->state_log = new_array; 4013 mctx->state_log = new_array;
4155 } 4014 }
@@ -4161,7 +4020,7 @@ extend_buffers (re_match_context_t *mctx, int min_len)
4161 if (pstr->mb_cur_max > 1) 4020 if (pstr->mb_cur_max > 1)
4162 { 4021 {
4163 ret = build_wcs_upper_buffer (pstr); 4022 ret = build_wcs_upper_buffer (pstr);
4164 if (BE (ret != REG_NOERROR, 0)) 4023 if (__glibc_unlikely (ret != REG_NOERROR))
4165 return ret; 4024 return ret;
4166 } 4025 }
4167 else 4026 else
@@ -4189,23 +4048,23 @@ extend_buffers (re_match_context_t *mctx, int min_len)
4189/* Initialize MCTX. */ 4048/* Initialize MCTX. */
4190 4049
4191static reg_errcode_t 4050static reg_errcode_t
4192internal_function __attribute_warn_unused_result__ 4051__attribute_warn_unused_result__
4193match_ctx_init (re_match_context_t *mctx, int eflags, Idx n) 4052match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4194{ 4053{
4195 mctx->eflags = eflags; 4054 mctx->eflags = eflags;
4196 mctx->match_last = REG_MISSING; 4055 mctx->match_last = -1;
4197 if (n > 0) 4056 if (n > 0)
4198 { 4057 {
4199 /* Avoid overflow. */ 4058 /* Avoid overflow. */
4200 size_t max_object_size = 4059 size_t max_object_size =
4201 MAX (sizeof (struct re_backref_cache_entry), 4060 MAX (sizeof (struct re_backref_cache_entry),
4202 sizeof (re_sub_match_top_t *)); 4061 sizeof (re_sub_match_top_t *));
4203 if (BE (MIN (IDX_MAX, SIZE_MAX / max_object_size) < n, 0)) 4062 if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / max_object_size) < n))
4204 return REG_ESPACE; 4063 return REG_ESPACE;
4205 4064
4206 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n); 4065 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4207 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n); 4066 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4208 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0)) 4067 if (__glibc_unlikely (mctx->bkref_ents == NULL || mctx->sub_tops == NULL))
4209 return REG_ESPACE; 4068 return REG_ESPACE;
4210 } 4069 }
4211 /* Already zero-ed by the caller. 4070 /* Already zero-ed by the caller.
@@ -4224,7 +4083,6 @@ match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4224 of the input, or changes the input string. */ 4083 of the input, or changes the input string. */
4225 4084
4226static void 4085static void
4227internal_function
4228match_ctx_clean (re_match_context_t *mctx) 4086match_ctx_clean (re_match_context_t *mctx)
4229{ 4087{
4230 Idx st_idx; 4088 Idx st_idx;
@@ -4244,7 +4102,7 @@ match_ctx_clean (re_match_context_t *mctx)
4244 re_free (top->path->array); 4102 re_free (top->path->array);
4245 re_free (top->path); 4103 re_free (top->path);
4246 } 4104 }
4247 free (top); 4105 re_free (top);
4248 } 4106 }
4249 4107
4250 mctx->nsub_tops = 0; 4108 mctx->nsub_tops = 0;
@@ -4254,7 +4112,6 @@ match_ctx_clean (re_match_context_t *mctx)
4254/* Free all the memory associated with MCTX. */ 4112/* Free all the memory associated with MCTX. */
4255 4113
4256static void 4114static void
4257internal_function
4258match_ctx_free (re_match_context_t *mctx) 4115match_ctx_free (re_match_context_t *mctx)
4259{ 4116{
4260 /* First, free all the memory associated with MCTX->SUB_TOPS. */ 4117 /* First, free all the memory associated with MCTX->SUB_TOPS. */
@@ -4269,7 +4126,7 @@ match_ctx_free (re_match_context_t *mctx)
4269*/ 4126*/
4270 4127
4271static reg_errcode_t 4128static reg_errcode_t
4272internal_function __attribute_warn_unused_result__ 4129__attribute_warn_unused_result__
4273match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from, 4130match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4274 Idx to) 4131 Idx to)
4275{ 4132{
@@ -4278,7 +4135,7 @@ match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4278 struct re_backref_cache_entry* new_entry; 4135 struct re_backref_cache_entry* new_entry;
4279 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry, 4136 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4280 mctx->abkref_ents * 2); 4137 mctx->abkref_ents * 2);
4281 if (BE (new_entry == NULL, 0)) 4138 if (__glibc_unlikely (new_entry == NULL))
4282 { 4139 {
4283 re_free (mctx->bkref_ents); 4140 re_free (mctx->bkref_ents);
4284 return REG_ESPACE; 4141 return REG_ESPACE;
@@ -4314,11 +4171,10 @@ match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4314 return REG_NOERROR; 4171 return REG_NOERROR;
4315} 4172}
4316 4173
4317/* Return the first entry with the same str_idx, or REG_MISSING if none is 4174/* Return the first entry with the same str_idx, or -1 if none is
4318 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */ 4175 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4319 4176
4320static Idx 4177static Idx
4321internal_function
4322search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx) 4178search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4323{ 4179{
4324 Idx left, right, mid, last; 4180 Idx left, right, mid, last;
@@ -4334,33 +4190,31 @@ search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4334 if (left < last && mctx->bkref_ents[left].str_idx == str_idx) 4190 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4335 return left; 4191 return left;
4336 else 4192 else
4337 return REG_MISSING; 4193 return -1;
4338} 4194}
4339 4195
4340/* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches 4196/* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4341 at STR_IDX. */ 4197 at STR_IDX. */
4342 4198
4343static reg_errcode_t 4199static reg_errcode_t
4344internal_function __attribute_warn_unused_result__ 4200__attribute_warn_unused_result__
4345match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx) 4201match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4346{ 4202{
4347#ifdef DEBUG 4203 DEBUG_ASSERT (mctx->sub_tops != NULL);
4348 assert (mctx->sub_tops != NULL); 4204 DEBUG_ASSERT (mctx->asub_tops > 0);
4349 assert (mctx->asub_tops > 0); 4205 if (__glibc_unlikely (mctx->nsub_tops == mctx->asub_tops))
4350#endif
4351 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4352 { 4206 {
4353 Idx new_asub_tops = mctx->asub_tops * 2; 4207 Idx new_asub_tops = mctx->asub_tops * 2;
4354 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops, 4208 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4355 re_sub_match_top_t *, 4209 re_sub_match_top_t *,
4356 new_asub_tops); 4210 new_asub_tops);
4357 if (BE (new_array == NULL, 0)) 4211 if (__glibc_unlikely (new_array == NULL))
4358 return REG_ESPACE; 4212 return REG_ESPACE;
4359 mctx->sub_tops = new_array; 4213 mctx->sub_tops = new_array;
4360 mctx->asub_tops = new_asub_tops; 4214 mctx->asub_tops = new_asub_tops;
4361 } 4215 }
4362 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t)); 4216 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4363 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0)) 4217 if (__glibc_unlikely (mctx->sub_tops[mctx->nsub_tops] == NULL))
4364 return REG_ESPACE; 4218 return REG_ESPACE;
4365 mctx->sub_tops[mctx->nsub_tops]->node = node; 4219 mctx->sub_tops[mctx->nsub_tops]->node = node;
4366 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx; 4220 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
@@ -4368,26 +4222,26 @@ match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4368} 4222}
4369 4223
4370/* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches 4224/* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4371 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */ 4225 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP.
4226 Return the new entry if successful, NULL if memory is exhausted. */
4372 4227
4373static re_sub_match_last_t * 4228static re_sub_match_last_t *
4374internal_function
4375match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx) 4229match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4376{ 4230{
4377 re_sub_match_last_t *new_entry; 4231 re_sub_match_last_t *new_entry;
4378 if (BE (subtop->nlasts == subtop->alasts, 0)) 4232 if (__glibc_unlikely (subtop->nlasts == subtop->alasts))
4379 { 4233 {
4380 Idx new_alasts = 2 * subtop->alasts + 1; 4234 Idx new_alasts = 2 * subtop->alasts + 1;
4381 re_sub_match_last_t **new_array = re_realloc (subtop->lasts, 4235 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4382 re_sub_match_last_t *, 4236 re_sub_match_last_t *,
4383 new_alasts); 4237 new_alasts);
4384 if (BE (new_array == NULL, 0)) 4238 if (__glibc_unlikely (new_array == NULL))
4385 return NULL; 4239 return NULL;
4386 subtop->lasts = new_array; 4240 subtop->lasts = new_array;
4387 subtop->alasts = new_alasts; 4241 subtop->alasts = new_alasts;
4388 } 4242 }
4389 new_entry = calloc (1, sizeof (re_sub_match_last_t)); 4243 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4390 if (BE (new_entry != NULL, 1)) 4244 if (__glibc_likely (new_entry != NULL))
4391 { 4245 {
4392 subtop->lasts[subtop->nlasts] = new_entry; 4246 subtop->lasts[subtop->nlasts] = new_entry;
4393 new_entry->node = node; 4247 new_entry->node = node;
@@ -4398,7 +4252,6 @@ match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4398} 4252}
4399 4253
4400static void 4254static void
4401internal_function
4402sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts, 4255sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4403 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx) 4256 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4404{ 4257{