« back to all changes in this revision
Viewing changes to gnulib/lib/regexec.c
- browse files at revision 11
- compare with another revision
- download diff
- download tarball
- view history from revision 11
- Committer: Bazaar Package Importer
- Author(s): Andreas Metzler
- Date: 2006-08-06 09:53:05 UTC
- mfrom: (1.1.6 upstream)
- Revision ID: james.westby@ubuntu.com-20060806095305-265uqmwsguy8vfjq
Tags: 4.2.28-1
* New upstream version.
- includes 01_updatedb-withnew-su.dpatch, drop it.
- includes 01_updatedb-withnew-su.dpatch, drop it.
- files added:
- gnulib/lib/getndelim2.c
- files removed:
- debian/patches/01_updatedb-withnew-su.dpatch
- files modified:
- ChangeLog
added
removed
gnulib/lib/regexec.c
18
18
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19
19
20
20
static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
21
Idx n) internal_function;
21
int n) internal_function;
22
22
static void match_ctx_clean (re_match_context_t *mctx) internal_function;
23
23
static void match_ctx_free (re_match_context_t *cache) internal_function;
24
static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
25
Idx str_idx, Idx from, Idx to)
26
internal_function;
27
static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
28
internal_function;
29
static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
30
Idx str_idx) internal_function;
24
static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
25
int str_idx, int from, int to)
26
internal_function;
27
static int search_cur_bkref_entry (re_match_context_t *mctx, int str_idx)
28
internal_function;
29
static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, int node,
30
int str_idx) internal_function;
31
31
static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
32
Idx node, Idx str_idx)
32
int node, int str_idx)
33
33
internal_function;
34
34
static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
35
re_dfastate_t **limited_sts, Idx last_node,
36
Idx last_str_idx)
35
re_dfastate_t **limited_sts, int last_node,
36
int last_str_idx)
37
37
internal_function;
38
38
static reg_errcode_t re_search_internal (const regex_t *preg,
39
const char *string, Idx length,
40
Idx start, Idx last_start, Idx stop,
39
const char *string, int length,
40
int start, int range, int stop,
41
41
size_t nmatch, regmatch_t pmatch[],
42
42
int eflags) internal_function;
43
static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
44
const char *string1, Idx length1,
45
const char *string2, Idx length2,
46
Idx start, regoff_t range,
47
struct re_registers *regs,
48
Idx stop, bool ret_len) internal_function;
49
static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
50
const char *string, Idx length, Idx start,
51
regoff_t range, Idx stop,
52
struct re_registers *regs,
53
bool ret_len) internal_function;
43
static int re_search_2_stub (struct re_pattern_buffer *bufp,
44
const char *string1, int length1,
45
const char *string2, int length2,
46
int start, int range, struct re_registers *regs,
47
int stop, int ret_len) internal_function;
48
static int re_search_stub (struct re_pattern_buffer *bufp,
49
const char *string, int length, int start,
50
int range, int stop, struct re_registers *regs,
51
int ret_len) internal_function;
54
52
static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
55
Idx nregs, int regs_allocated) internal_function;
53
int nregs, int regs_allocated) internal_function;
54
static inline re_dfastate_t *acquire_init_state_context
55
(reg_errcode_t *err, const re_match_context_t *mctx, int idx)
56
__attribute ((always_inline)) internal_function;
56
57
static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
57
58
internal_function;
58
static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
59
Idx *p_match_first)
59
static int check_matching (re_match_context_t *mctx, int fl_longest_match,
60
int *p_match_first)
60
61
internal_function;
61
static Idx check_halt_state_context (const re_match_context_t *mctx,
62
const re_dfastate_t *state, Idx idx)
62
static int check_halt_node_context (const re_dfa_t *dfa, int node,
63
unsigned int context) internal_function;
64
static int check_halt_state_context (const re_match_context_t *mctx,
65
const re_dfastate_t *state, int idx)
63
66
internal_function;
64
67
static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch,
65
regmatch_t *prev_idx_match, Idx cur_node,
66
Idx cur_idx, Idx nmatch) internal_function;
68
regmatch_t *prev_idx_match, int cur_node,
69
int cur_idx, int nmatch) internal_function;
70
static int proceed_next_node (const re_match_context_t *mctx,
71
int nregs, regmatch_t *regs,
72
int *pidx, int node, re_node_set *eps_via_nodes,
73
struct re_fail_stack_t *fs) internal_function;
67
74
static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
68
Idx str_idx, Idx dest_node, Idx nregs,
75
int str_idx, int dest_node, int nregs,
69
76
regmatch_t *regs,
70
77
re_node_set *eps_via_nodes) internal_function;
78
static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
79
regmatch_t *regs, re_node_set *eps_via_nodes) internal_function;
71
80
static reg_errcode_t set_regs (const regex_t *preg,
72
81
const re_match_context_t *mctx,
73
82
size_t nmatch, regmatch_t *pmatch,
74
bool fl_backtrack) internal_function;
83
int fl_backtrack) internal_function;
75
84
static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs) internal_function;
76
85
77
86
#ifdef RE_ENABLE_I18N
78
87
static int sift_states_iter_mb (const re_match_context_t *mctx,
79
88
re_sift_context_t *sctx,
80
Idx node_idx, Idx str_idx, Idx max_str_idx) internal_function;
89
int node_idx, int str_idx, int max_str_idx) internal_function;
81
90
#endif /* RE_ENABLE_I18N */
82
91
static reg_errcode_t sift_states_backward (re_match_context_t *mctx,
83
92
re_sift_context_t *sctx) internal_function;
84
93
static reg_errcode_t build_sifted_states (re_match_context_t *mctx,
85
re_sift_context_t *sctx, Idx str_idx,
94
re_sift_context_t *sctx, int str_idx,
86
95
re_node_set *cur_dest) internal_function;
87
96
static reg_errcode_t update_cur_sifted_state (re_match_context_t *mctx,
88
97
re_sift_context_t *sctx,
89
Idx str_idx,
98
int str_idx,
90
99
re_node_set *dest_nodes) internal_function;
91
100
static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa,
92
101
re_node_set *dest_nodes,
93
102
const re_node_set *candidates) internal_function;
94
static bool check_dst_limits (const re_match_context_t *mctx,
95
const re_node_set *limits,
96
Idx dst_node, Idx dst_idx, Idx src_node,
97
Idx src_idx) internal_function;
98
static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
99
int boundaries, Idx subexp_idx,
100
Idx from_node, Idx bkref_idx) internal_function;
101
static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
102
Idx limit, Idx subexp_idx,
103
Idx node, Idx str_idx,
104
Idx bkref_idx) internal_function;
103
static reg_errcode_t sub_epsilon_src_nodes (re_dfa_t *dfa, int node,
104
re_node_set *dest_nodes,
105
const re_node_set *and_nodes) internal_function;
106
static int check_dst_limits (re_match_context_t *mctx, re_node_set *limits,
107
int dst_node, int dst_idx, int src_node,
108
int src_idx) internal_function;
109
static int check_dst_limits_calc_pos_1 (re_match_context_t *mctx,
110
int boundaries, int subexp_idx,
111
int from_node, int bkref_idx) internal_function;
112
static int check_dst_limits_calc_pos (re_match_context_t *mctx,
113
int limit, int subexp_idx,
114
int node, int str_idx,
115
int bkref_idx) internal_function;
105
116
static reg_errcode_t check_subexp_limits (re_dfa_t *dfa,
106
117
re_node_set *dest_nodes,
107
118
const re_node_set *candidates,
108
119
re_node_set *limits,
109
120
struct re_backref_cache_entry *bkref_ents,
110
Idx str_idx) internal_function;
121
int str_idx) internal_function;
111
122
static reg_errcode_t sift_states_bkref (re_match_context_t *mctx,
112
123
re_sift_context_t *sctx,
113
Idx str_idx, const re_node_set *candidates) internal_function;
124
int str_idx, const re_node_set *candidates) internal_function;
125
static reg_errcode_t clean_state_log_if_needed (re_match_context_t *mctx,
126
int next_state_log_idx) internal_function;
114
127
static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
115
re_dfastate_t **src, Idx num) internal_function;
128
re_dfastate_t **src, int num) internal_function;
116
129
static re_dfastate_t *find_recover_state (reg_errcode_t *err,
117
130
re_match_context_t *mctx) internal_function;
118
131
static re_dfastate_t *transit_state (reg_errcode_t *err,
123
136
re_dfastate_t *next_state) internal_function;
124
137
static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
125
138
re_node_set *cur_nodes,
126
Idx str_idx) internal_function;
139
int str_idx) internal_function;
127
140
#if 0
128
141
static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
129
142
re_match_context_t *mctx,
136
149
static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
137
150
const re_node_set *nodes) internal_function;
138
151
static reg_errcode_t get_subexp (re_match_context_t *mctx,
139
Idx bkref_node, Idx bkref_str_idx) internal_function;
152
int bkref_node, int bkref_str_idx) internal_function;
140
153
static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
141
154
const re_sub_match_top_t *sub_top,
142
155
re_sub_match_last_t *sub_last,
143
Idx bkref_node, Idx bkref_str) internal_function;
144
static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
145
Idx subexp_idx, int type) internal_function;
156
int bkref_node, int bkref_str) internal_function;
157
static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
158
int subexp_idx, int type) internal_function;
146
159
static reg_errcode_t check_arrival (re_match_context_t *mctx,
147
state_array_t *path, Idx top_node,
148
Idx top_str, Idx last_node, Idx last_str,
160
state_array_t *path, int top_node,
161
int top_str, int last_node, int last_str,
149
162
int type) internal_function;
150
163
static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
151
Idx str_idx,
164
int str_idx,
152
165
re_node_set *cur_nodes,
153
166
re_node_set *next_nodes) internal_function;
154
167
static reg_errcode_t check_arrival_expand_ecl (re_dfa_t *dfa,
155
168
re_node_set *cur_nodes,
156
Idx ex_subexp, int type) internal_function;
169
int ex_subexp, int type) internal_function;
157
170
static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa,
158
171
re_node_set *dst_nodes,
159
Idx target, Idx ex_subexp,
172
int target, int ex_subexp,
160
173
int type) internal_function;
161
174
static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
162
re_node_set *cur_nodes, Idx cur_str,
163
Idx subexp_num, int type) internal_function;
164
static bool build_trtable (re_dfa_t *dfa,
165
re_dfastate_t *state) internal_function;
175
re_node_set *cur_nodes, int cur_str,
176
int subexp_num, int type) internal_function;
177
static int build_trtable (re_dfa_t *dfa,
178
re_dfastate_t *state) internal_function;
166
179
#ifdef RE_ENABLE_I18N
167
static int check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
168
const re_string_t *input, Idx idx) internal_function;
180
static int check_node_accept_bytes (re_dfa_t *dfa, int node_idx,
181
const re_string_t *input, int idx) internal_function;
169
182
# ifdef _LIBC
170
183
static unsigned int find_collation_sequence_value (const unsigned char *mbs,
171
184
size_t name_len) internal_function;
172
185
# endif /* _LIBC */
173
186
#endif /* RE_ENABLE_I18N */
174
static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
187
static int group_nodes_into_DFAstates (re_dfa_t *dfa,
175
188
const re_dfastate_t *state,
176
189
re_node_set *states_node,
177
190
bitset *states_ch) internal_function;
178
static bool check_node_accept (const re_match_context_t *mctx,
179
const re_token_t *node, Idx idx)
180
internal_function;
191
static int check_node_accept (const re_match_context_t *mctx,
192
const re_token_t *node, int idx) internal_function;
181
193
static reg_errcode_t extend_buffers (re_match_context_t *mctx) internal_function;
182
194
183
195
/* Entry point for POSIX code. */
197
209
We return 0 if we find a match and REG_NOMATCH if not. */
198
210
199
211
int
200
regexec (const regex_t *__restrict preg, const char *__restrict string,
201
size_t nmatch, regmatch_t pmatch[], int eflags)
212
regexec (preg, string, nmatch, pmatch, eflags)
213
const regex_t *__restrict preg;
214
const char *__restrict string;
215
size_t nmatch;
216
regmatch_t pmatch[];
217
int eflags;
202
218
{
203
219
reg_errcode_t err;
204
Idx start, length;
205
#ifdef _LIBC
206
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
207
#endif
220
int start, length;
221
re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
208
222
209
223
if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
210
224
return REG_BADPAT;
221
235
}
222
236
223
237
__libc_lock_lock (dfa->lock);
224
if (preg->re_no_sub)
225
err = re_search_internal (preg, string, length, start, length,
238
if (preg->no_sub)
239
err = re_search_internal (preg, string, length, start, length - start,
226
240
length, 0, NULL, eflags);
227
241
else
228
err = re_search_internal (preg, string, length, start, length,
242
err = re_search_internal (preg, string, length, start, length - start,
229
243
length, nmatch, pmatch, eflags);
230
244
__libc_lock_unlock (dfa->lock);
231
245
return err != REG_NOERROR;
271
285
the first STOP characters of the concatenation of the strings should be
272
286
concerned.
273
287
274
If REGS is not NULL, and BUFP->re_no_sub is not set, the offsets of the match
288
If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
275
289
and all groups is stroed in REGS. (For the "_2" variants, the offsets are
276
290
computed relative to the concatenation, not relative to the individual
277
291
strings.)
280
294
return the position of the start of the match. Return value -1 means no
281
295
match was found and -2 indicates an internal error. */
282
296
283
regoff_t
284
re_match (struct re_pattern_buffer *bufp, const char *string,
285
Idx length, Idx start, struct re_registers *regs)
297
int
298
re_match (bufp, string, length, start, regs)
299
struct re_pattern_buffer *bufp;
300
const char *string;
301
int length, start;
302
struct re_registers *regs;
286
303
{
287
return re_search_stub (bufp, string, length, start, 0, length, regs, true);
304
return re_search_stub (bufp, string, length, start, 0, length, regs, 1);
288
305
}
289
306
#ifdef _LIBC
290
307
weak_alias (__re_match, re_match)
291
308
#endif
292
309
293
regoff_t
294
re_search (struct re_pattern_buffer *bufp, const char *string,
295
Idx length, Idx start, regoff_t range, struct re_registers *regs)
310
int
311
re_search (bufp, string, length, start, range, regs)
312
struct re_pattern_buffer *bufp;
313
const char *string;
314
int length, start, range;
315
struct re_registers *regs;
296
316
{
297
return re_search_stub (bufp, string, length, start, range, length, regs,
298
false);
317
return re_search_stub (bufp, string, length, start, range, length, regs, 0);
299
318
}
300
319
#ifdef _LIBC
301
320
weak_alias (__re_search, re_search)
302
321
#endif
303
322
304
regoff_t
305
re_match_2 (struct re_pattern_buffer *bufp,
306
const char *string1, Idx length1,
307
const char *string2, Idx length2,
308
Idx start, struct re_registers *regs, Idx stop)
323
int
324
re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
325
struct re_pattern_buffer *bufp;
326
const char *string1, *string2;
327
int length1, length2, start, stop;
328
struct re_registers *regs;
309
329
{
310
330
return re_search_2_stub (bufp, string1, length1, string2, length2,
311
start, 0, regs, stop, true);
331
start, 0, regs, stop, 1);
312
332
}
313
333
#ifdef _LIBC
314
334
weak_alias (__re_match_2, re_match_2)
315
335
#endif
316
336
317
regoff_t
318
re_search_2 (struct re_pattern_buffer *bufp,
319
const char *string1, Idx length1,
320
const char *string2, Idx length2,
321
Idx start, regoff_t range, struct re_registers *regs, Idx stop)
337
int
338
re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
339
struct re_pattern_buffer *bufp;
340
const char *string1, *string2;
341
int length1, length2, start, range, stop;
342
struct re_registers *regs;
322
343
{
323
344
return re_search_2_stub (bufp, string1, length1, string2, length2,
324
start, range, regs, stop, false);
345
start, range, regs, stop, 0);
325
346
}
326
347
#ifdef _LIBC
327
348
weak_alias (__re_search_2, re_search_2)
328
349
#endif
329
350
330
static regoff_t
331
internal_function
332
re_search_2_stub (struct re_pattern_buffer *bufp,
333
const char *string1, Idx length1,
334
const char *string2, Idx length2,
335
Idx start, regoff_t range, struct re_registers *regs,
336
Idx stop, bool ret_len)
351
static int
352
re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs,
353
stop, ret_len)
354
struct re_pattern_buffer *bufp;
355
const char *string1, *string2;
356
int length1, length2, start, range, stop, ret_len;
357
struct re_registers *regs;
337
358
{
338
359
const char *str;
339
regoff_t rval;
340
Idx len = length1 + length2;
341
char *s = NULL;
360
int rval;
361
int len = length1 + length2;
362
int free_str = 0;
342
363
343
if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
364
if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
344
365
return -2;
345
366
346
367
/* Concatenate the strings. */
347
368
if (length2 > 0)
348
369
if (length1 > 0)
349
370
{
350
s = re_malloc (char, len);
371
char *s = re_malloc (char, len);
351
372
352
373
if (BE (s == NULL, 0))
353
374
return -2;
354
375
memcpy (s, string1, length1);
355
376
memcpy (s + length1, string2, length2);
356
377
str = s;
378
free_str = 1;
357
379
}
358
380
else
359
381
str = string2;
362
384
363
385
rval = re_search_stub (bufp, str, len, start, range, stop, regs,
364
386
ret_len);
365
re_free (s);
387
if (free_str)
388
re_free ((char *) str);
366
389
return rval;
367
390
}
368
391
369
392
/* The parameters have the same meaning as those of re_search.
370
393
Additional parameters:
371
If RET_LEN is true the length of the match is returned (re_match style);
394
If RET_LEN is nonzero the length of the match is returned (re_match style);
372
395
otherwise the position of the match is returned. */
373
396
374
static regoff_t
375
internal_function
376
re_search_stub (struct re_pattern_buffer *bufp,
377
const char *string, Idx length,
378
Idx start, regoff_t range, Idx stop, struct re_registers *regs,
379
bool ret_len)
397
static int
398
re_search_stub (bufp, string, length, start, range, stop, regs, ret_len)
399
struct re_pattern_buffer *bufp;
400
const char *string;
401
int length, start, range, stop, ret_len;
402
struct re_registers *regs;
380
403
{
381
404
reg_errcode_t result;
382
405
regmatch_t *pmatch;
383
Idx nregs;
384
regoff_t rval;
406
int nregs, rval;
385
407
int eflags = 0;
386
#ifdef _LIBC
387
re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
388
#endif
389
Idx last_start = start + range;
408
re_dfa_t *dfa = (re_dfa_t *)bufp->buffer;
390
409
391
410
/* Check for out-of-range. */
392
411
if (BE (start < 0 || start > length, 0))
393
412
return -1;
394
if (sizeof start < sizeof range)
395
{
396
regoff_t length_offset = length;
397
regoff_t start_offset = start;
398
if (BE (length_offset - start_offset < range, 0))
399
last_start = length;
400
else if (BE (range < - start_offset, 0))
401
last_start = 0;
402
}
403
else
404
{
405
if (BE ((last_start < start) != (range < 0), 0))
406
{
407
/* Overflow occurred when computing last_start; substitute
408
the extreme value. */
409
last_start = range < 0 ? 0 : length;
410
}
411
else
412
{
413
if (BE (length < last_start, 0))
414
last_start = length;
415
else if (BE (last_start < 0, 0))
416
last_start = 0;
417
}
418
}
413
if (BE (start + range > length, 0))
414
range = length - start;
415
else if (BE (start + range < 0, 0))
416
range = -start;
419
417
420
418
__libc_lock_lock (dfa->lock);
421
419
422
eflags |= (bufp->re_not_bol) ? REG_NOTBOL : 0;
423
eflags |= (bufp->re_not_eol) ? REG_NOTEOL : 0;
420
eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
421
eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
424
422
425
423
/* Compile fastmap if we haven't yet. */
426
if (start < last_start && bufp->re_fastmap != NULL
427
&& !bufp->re_fastmap_accurate)
424
if (range > 0 && bufp->fastmap != NULL && !bufp->fastmap_accurate)
428
425
re_compile_fastmap (bufp);
429
426
430
if (BE (bufp->re_no_sub, 0))
427
if (BE (bufp->no_sub, 0))
431
428
regs = NULL;
432
429
433
430
/* We need at least 1 register. */
434
431
if (regs == NULL)
435
432
nregs = 1;
436
else if (BE (bufp->re_regs_allocated == REG_FIXED
437
&& regs->rm_num_regs <= bufp->re_nsub, 0))
433
else if (BE (bufp->regs_allocated == REGS_FIXED &&
434
regs->num_regs < bufp->re_nsub + 1, 0))
438
435
{
439
nregs = regs->rm_num_regs;
436
nregs = regs->num_regs;
440
437
if (BE (nregs < 1, 0))
441
438
{
442
439
/* Nothing can be copied to regs. */
446
443
}
447
444
else
448
445
nregs = bufp->re_nsub + 1;
449
pmatch = re_xmalloc (regmatch_t, nregs);
446
pmatch = re_malloc (regmatch_t, nregs);
450
447
if (BE (pmatch == NULL, 0))
451
448
{
452
449
rval = -2;
453
450
goto out;
454
451
}
455
452
456
result = re_search_internal (bufp, string, length, start, last_start, stop,
453
result = re_search_internal (bufp, string, length, start, range, stop,
457
454
nregs, pmatch, eflags);
458
455
459
456
rval = 0;
464
461
else if (regs != NULL)
465
462
{
466
463
/* If caller wants register contents data back, copy them. */
467
bufp->re_regs_allocated = re_copy_regs (regs, pmatch, nregs,
468
bufp->re_regs_allocated);
469
if (BE (bufp->re_regs_allocated == REG_UNALLOCATED, 0))
464
bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
465
bufp->regs_allocated);
466
if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
470
467
rval = -2;
471
468
}
472
469
487
484
}
488
485
489
486
static unsigned
490
internal_function
491
re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
492
int regs_allocated)
487
re_copy_regs (regs, pmatch, nregs, regs_allocated)
488
struct re_registers *regs;
489
regmatch_t *pmatch;
490
int nregs, regs_allocated;
493
491
{
494
int rval = REG_REALLOCATE;
495
Idx i;
496
Idx need_regs = nregs + 1;
497
/* We need one extra element beyond `rm_num_regs' for the `-1' marker GNU code
492
int rval = REGS_REALLOCATE;
493
int i;
494
int need_regs = nregs + 1;
495
/* We need one extra element beyond `num_regs' for the `-1' marker GNU code
498
496
uses. */
499
497
500
498
/* Have the register data arrays been allocated? */
501
if (regs_allocated == REG_UNALLOCATED)
499
if (regs_allocated == REGS_UNALLOCATED)
502
500
{ /* No. So allocate them with malloc. */
503
regs->rm_start = re_xmalloc (regoff_t, need_regs);
504
regs->rm_end = re_malloc (regoff_t, need_regs);
505
if (BE (regs->rm_start == NULL, 0) || BE (regs->rm_end == NULL, 0))
506
return REG_UNALLOCATED;
507
regs->rm_num_regs = need_regs;
501
regs->start = re_malloc (regoff_t, need_regs);
502
regs->end = re_malloc (regoff_t, need_regs);
503
if (BE (regs->start == NULL, 0) || BE (regs->end == NULL, 0))
504
return REGS_UNALLOCATED;
505
regs->num_regs = need_regs;
508
506
}
509
else if (regs_allocated == REG_REALLOCATE)
507
else if (regs_allocated == REGS_REALLOCATE)
510
508
{ /* Yes. If we need more elements than were already
511
509
allocated, reallocate them. If we need fewer, just
512
510
leave it alone. */
513
if (BE (need_regs > regs->rm_num_regs, 0))
511
if (BE (need_regs > regs->num_regs, 0))
514
512
{
515
regoff_t *new_start =
516
re_xrealloc (regs->rm_start, regoff_t, need_regs);
517
regoff_t *new_end = re_realloc (regs->rm_end, regoff_t, need_regs);
513
regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
514
regoff_t *new_end = re_realloc (regs->end, regoff_t, need_regs);
518
515
if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
519
return REG_UNALLOCATED;
520
regs->rm_start = new_start;
521
regs->rm_end = new_end;
522
regs->rm_num_regs = need_regs;
516
return REGS_UNALLOCATED;
517
regs->start = new_start;
518
regs->end = new_end;
519
regs->num_regs = need_regs;
523
520
}
524
521
}
525
522
else
526
523
{
527
assert (regs_allocated == REG_FIXED);
528
/* This function may not be called with REG_FIXED and nregs too big. */
529
assert (regs->rm_num_regs >= nregs);
530
rval = REG_FIXED;
524
assert (regs_allocated == REGS_FIXED);
525
/* This function may not be called with REGS_FIXED and nregs too big. */
526
assert (regs->num_regs >= nregs);
527
rval = REGS_FIXED;
531
528
}
532
529
533
530
/* Copy the regs. */
534
531
for (i = 0; i < nregs; ++i)
535
532
{
536
regs->rm_start[i] = pmatch[i].rm_so;
537
regs->rm_end[i] = pmatch[i].rm_eo;
533
regs->start[i] = pmatch[i].rm_so;
534
regs->end[i] = pmatch[i].rm_eo;
538
535
}
539
for ( ; i < regs->rm_num_regs; ++i)
540
regs->rm_start[i] = regs->rm_end[i] = -1;
536
for ( ; i < regs->num_regs; ++i)
537
regs->start[i] = regs->end[i] = -1;
541
538
542
539
return rval;
543
540
}
556
553
freeing the old data. */
557
554
558
555
void
559
re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,
560
__re_size_t num_regs, regoff_t *starts, regoff_t *ends)
556
re_set_registers (bufp, regs, num_regs, starts, ends)
557
struct re_pattern_buffer *bufp;
558
struct re_registers *regs;
559
unsigned num_regs;
560
regoff_t *starts, *ends;
561
561
{
562
562
if (num_regs)
563
563
{
564
bufp->re_regs_allocated = REG_REALLOCATE;
565
regs->rm_num_regs = num_regs;
566
regs->rm_start = starts;
567
regs->rm_end = ends;
564
bufp->regs_allocated = REGS_REALLOCATE;
565
regs->num_regs = num_regs;
566
regs->start = starts;
567
regs->end = ends;
568
568
}
569
569
else
570
570
{
571
bufp->re_regs_allocated = REG_UNALLOCATED;
572
regs->rm_num_regs = 0;
573
regs->rm_start = regs->rm_end = NULL;
571
bufp->regs_allocated = REGS_UNALLOCATED;
572
regs->num_regs = 0;
573
regs->start = regs->end = (regoff_t *) 0;
574
574
}
575
575
}
576
576
#ifdef _LIBC
585
585
# ifdef _LIBC
586
586
weak_function
587
587
# endif
588
re_exec (const char *s)
588
re_exec (s)
589
const char *s;
589
590
{
590
591
return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
591
592
}
595
596
596
597
/* Searches for a compiled pattern PREG in the string STRING, whose
597
598
length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
598
meaning as with regexec. LAST_START is START + RANGE, where
599
START and RANGE have the same meaning as with re_search.
599
mingings with regexec. START, and RANGE have the same meanings
600
with re_search.
600
601
Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
601
602
otherwise return the error code.
602
603
Note: We assume front end functions already check ranges.
603
(0 <= LAST_START && LAST_START <= LENGTH) */
604
(START + RANGE >= 0 && START + RANGE <= LENGTH) */
604
605
605
606
static reg_errcode_t
606
internal_function
607
re_search_internal (const regex_t *preg,
608
const char *string, Idx length,
609
Idx start, Idx last_start, Idx stop,
610
size_t nmatch, regmatch_t pmatch[],
611
int eflags)
607
re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
608
eflags)
609
const regex_t *preg;
610
const char *string;
611
int length, start, range, stop, eflags;
612
size_t nmatch;
613
regmatch_t pmatch[];
612
614
{
613
615
reg_errcode_t err;
614
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
615
Idx left_lim, right_lim;
616
int incr;
617
bool fl_longest_match;
618
int match_kind;
619
Idx match_first, match_last = REG_MISSING;
620
Idx extra_nmatch;
621
bool sb;
622
int ch;
616
re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
617
int left_lim, right_lim, incr;
618
int fl_longest_match, match_first, match_kind, match_last = -1;
619
int extra_nmatch;
620
int sb, ch;
623
621
#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
624
622
re_match_context_t mctx = { .dfa = dfa };
625
623
#else
626
624
re_match_context_t mctx;
627
625
#endif
628
char *fastmap = ((preg->re_fastmap != NULL && preg->re_fastmap_accurate
629
&& start != last_start && !preg->re_can_be_null)
630
? preg->re_fastmap : NULL);
631
unsigned REG_TRANSLATE_TYPE t =
632
(unsigned REG_TRANSLATE_TYPE) preg->re_translate;
626
char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
627
&& range && !preg->can_be_null) ? preg->fastmap : NULL;
628
unsigned RE_TRANSLATE_TYPE t = (unsigned RE_TRANSLATE_TYPE) preg->translate;
633
629
634
630
#if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
635
631
memset (&mctx, '\0', sizeof (re_match_context_t));
640
636
nmatch -= extra_nmatch;
641
637
642
638
/* Check if the DFA haven't been compiled. */
643
if (BE (preg->re_used == 0 || dfa->init_state == NULL
639
if (BE (preg->used == 0 || dfa->init_state == NULL
644
640
|| dfa->init_state_word == NULL || dfa->init_state_nl == NULL
645
641
|| dfa->init_state_begbuf == NULL, 0))
646
642
return REG_NOMATCH;
647
643
648
644
#ifdef DEBUG
649
645
/* We assume front-end functions already check them. */
650
assert (0 <= last_start && last_start <= length);
646
assert (start + range >= 0 && start + range <= length);
651
647
#endif
652
648
653
649
/* If initial states with non-begbuf contexts have no elements,
654
the regex must be anchored. If preg->re_newline_anchor is set,
650
the regex must be anchored. If preg->newline_anchor is set,
655
651
we'll never use init_state_nl, so do not check it. */
656
652
if (dfa->init_state->nodes.nelem == 0
657
653
&& dfa->init_state_word->nodes.nelem == 0
658
654
&& (dfa->init_state_nl->nodes.nelem == 0
659
|| !preg->re_newline_anchor))
655
|| !preg->newline_anchor))
660
656
{
661
if (start != 0 && last_start != 0)
657
if (start != 0 && start + range != 0)
662
658
return REG_NOMATCH;
663
start = last_start = 0;
659
start = range = 0;
664
660
}
665
661
666
662
/* We must check the longest matching, if nmatch > 0. */
667
663
fl_longest_match = (nmatch != 0 || dfa->nbackref);
668
664
669
665
err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
670
preg->re_translate,
671
preg->re_syntax & REG_IGNORE_CASE, dfa);
666
preg->translate, preg->syntax & RE_ICASE, dfa);
672
667
if (BE (err != REG_NOERROR, 0))
673
668
goto free_return;
674
669
mctx.input.stop = stop;
675
670
mctx.input.raw_stop = stop;
676
mctx.input.newline_anchor = preg->re_newline_anchor;
671
mctx.input.newline_anchor = preg->newline_anchor;
677
672
678
673
err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
679
674
if (BE (err != REG_NOERROR, 0))
685
680
multi character collating element. */
686
681
if (nmatch > 1 || dfa->has_mb_node)
687
682
{
688
mctx.state_log = re_xmalloc (re_dfastate_t *, mctx.input.bufs_len + 1);
683
mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
689
684
if (BE (mctx.state_log == NULL, 0))
690
685
{
691
686
err = REG_ESPACE;
700
695
: CONTEXT_NEWLINE | CONTEXT_BEGBUF;
701
696
702
697
/* Check incrementally whether of not the input string match. */
703
incr = (last_start < start) ? -1 : 1;
704
left_lim = (last_start < start) ? last_start : start;
705
right_lim = (last_start < start) ? start : last_start;
698
incr = (range < 0) ? -1 : 1;
699
left_lim = (range < 0) ? start + range : start;
700
right_lim = (range < 0) ? start : start + range;
706
701
sb = dfa->mb_cur_max == 1;
707
702
match_kind =
708
703
(fastmap
709
? ((sb || !(preg->re_syntax & REG_IGNORE_CASE || t) ? 4 : 0)
710
| (start <= last_start ? 2 : 0)
704
? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
705
| (range >= 0 ? 2 : 0)
711
706
| (t != NULL ? 1 : 0))
712
707
: 8);
713
708
774
769
{
775
770
/* If MATCH_FIRST is out of the valid range, reconstruct the
776
771
buffers. */
777
__re_size_t offset = match_first - mctx.input.raw_mbs_idx;
778
if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
772
unsigned int offset = match_first - mctx.input.raw_mbs_idx;
773
if (BE (offset >= (unsigned int) mctx.input.valid_raw_len, 0))
779
774
{
780
775
err = re_string_reconstruct (&mctx.input, match_first,
781
776
eflags);
817
812
/* We assume that the matching starts from 0. */
818
813
mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
819
814
match_last = check_matching (&mctx, fl_longest_match,
820
start <= last_start ? &match_first : NULL);
821
if (match_last != REG_MISSING)
815
range >= 0 ? &match_first : NULL);
816
if (match_last != -1)
822
817
{
823
if (BE (match_last == REG_ERROR, 0))
818
if (BE (match_last == -2, 0))
824
819
{
825
820
err = REG_ESPACE;
826
821
goto free_return;
828
823
else
829
824
{
830
825
mctx.match_last = match_last;
831
if ((!preg->re_no_sub && nmatch > 1) || dfa->nbackref)
826
if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
832
827
{
833
828
re_dfastate_t *pstate = mctx.state_log[match_last];
834
829
mctx.last_node = check_halt_state_context (&mctx, pstate,
835
830
match_last);
836
831
}
837
if ((!preg->re_no_sub && nmatch > 1 && dfa->has_plural_match)
832
if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
838
833
|| dfa->nbackref)
839
834
{
840
835
err = prune_impossible_nodes (&mctx);
842
837
break;
843
838
if (BE (err != REG_NOMATCH, 0))
844
839
goto free_return;
845
match_last = REG_MISSING;
840
match_last = -1;
846
841
}
847
842
else
848
843
break; /* We found a match. */
853
848
}
854
849
855
850
#ifdef DEBUG
856
assert (match_last != REG_MISSING);
851
assert (match_last != -1);
857
852
assert (err == REG_NOERROR);
858
853
#endif
859
854
860
855
/* Set pmatch[] if we need. */
861
856
if (nmatch > 0)
862
857
{
863
Idx reg_idx;
858
int reg_idx;
864
859
865
860
/* Initialize registers. */
866
861
for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
869
864
/* Set the points where matching start/end. */
870
865
pmatch[0].rm_so = 0;
871
866
pmatch[0].rm_eo = mctx.match_last;
872
/* FIXME: This function should fail if mctx.match_last exceeds
873
the maximum possible regoff_t value. We need a new error
874
code REG_OVERFLOW. */
875
867
876
if (!preg->re_no_sub && nmatch > 1)
868
if (!preg->no_sub && nmatch > 1)
877
869
{
878
870
err = set_regs (preg, &mctx, nmatch, pmatch,
879
871
dfa->has_plural_match && dfa->nbackref > 0);
890
882
#ifdef RE_ENABLE_I18N
891
883
if (BE (mctx.input.offsets_needed != 0, 0))
892
884
{
893
pmatch[reg_idx].rm_so =
894
(pmatch[reg_idx].rm_so == mctx.input.valid_len
895
? mctx.input.valid_raw_len
896
: mctx.input.offsets[pmatch[reg_idx].rm_so]);
897
pmatch[reg_idx].rm_eo =
898
(pmatch[reg_idx].rm_eo == mctx.input.valid_len
899
? mctx.input.valid_raw_len
900
: mctx.input.offsets[pmatch[reg_idx].rm_eo]);
885
if (pmatch[reg_idx].rm_so == mctx.input.valid_len)
886
pmatch[reg_idx].rm_so += mctx.input.valid_raw_len - mctx.input.valid_len;
887
else
888
pmatch[reg_idx].rm_so = mctx.input.offsets[pmatch[reg_idx].rm_so];
889
if (pmatch[reg_idx].rm_eo == mctx.input.valid_len)
890
pmatch[reg_idx].rm_eo += mctx.input.valid_raw_len - mctx.input.valid_len;
891
else
892
pmatch[reg_idx].rm_eo = mctx.input.offsets[pmatch[reg_idx].rm_eo];
901
893
}
902
894
#else
903
895
assert (mctx.input.offsets_needed == 0);
931
923
}
932
924
933
925
static reg_errcode_t
934
internal_function
935
prune_impossible_nodes (re_match_context_t *mctx)
926
prune_impossible_nodes (mctx)
927
re_match_context_t *mctx;
936
928
{
937
929
re_dfa_t *const dfa = mctx->dfa;
938
Idx halt_node, match_last;
930
int halt_node, match_last;
939
931
reg_errcode_t ret;
940
932
re_dfastate_t **sifted_states;
941
933
re_dfastate_t **lim_states = NULL;
945
937
#endif
946
938
match_last = mctx->match_last;
947
939
halt_node = mctx->last_node;
948
sifted_states = re_xmalloc (re_dfastate_t *, match_last + 1);
940
sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
949
941
if (BE (sifted_states == NULL, 0))
950
942
{
951
943
ret = REG_ESPACE;
953
945
}
954
946
if (dfa->nbackref)
955
947
{
956
lim_states = re_xmalloc (re_dfastate_t *, match_last + 1);
948
lim_states = re_malloc (re_dfastate_t *, match_last + 1);
957
949
if (BE (lim_states == NULL, 0))
958
950
{
959
951
ret = REG_ESPACE;
974
966
do
975
967
{
976
968
--match_last;
977
if (! REG_VALID_INDEX (match_last))
969
if (match_last < 0)
978
970
{
979
971
ret = REG_NOMATCH;
980
972
goto free_return;
1017
1009
since initial states may have constraints like "\<", "^", etc.. */
1018
1010
1019
1011
static inline re_dfastate_t *
1020
__attribute ((always_inline)) internal_function
1021
acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1022
Idx idx)
1012
acquire_init_state_context (err, mctx, idx)
1013
reg_errcode_t *err;
1014
const re_match_context_t *mctx;
1015
int idx;
1023
1016
{
1024
1017
re_dfa_t *const dfa = mctx->dfa;
1025
1018
if (dfa->init_state->has_constraint)
1050
1043
}
1051
1044
1052
1045
/* Check whether the regular expression match input string INPUT or not,
1053
and return the index where the matching end. Return REG_MISSING if
1054
there is no match, and return REG_ERROR in case of an error.
1046
and return the index where the matching end, return -1 if not match,
1047
or return -2 in case of an error.
1055
1048
FL_LONGEST_MATCH means we want the POSIX longest matching.
1056
1049
If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1057
1050
next place where we may want to try matching.
1058
1051
Note that the matcher assume that the maching starts from the current
1059
1052
index of the buffer. */
1060
1053
1061
static Idx
1062
internal_function
1063
check_matching (re_match_context_t *mctx, bool fl_longest_match,
1064
Idx *p_match_first)
1054
static int
1055
check_matching (mctx, fl_longest_match, p_match_first)
1056
re_match_context_t *mctx;
1057
int fl_longest_match;
1058
int *p_match_first;
1065
1059
{
1066
1060
re_dfa_t *const dfa = mctx->dfa;
1067
1061
reg_errcode_t err;
1068
Idx match = 0;
1069
Idx match_last = REG_MISSING;
1070
Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1062
int match = 0;
1063
int match_last = -1;
1064
int cur_str_idx = re_string_cur_idx (&mctx->input);
1071
1065
re_dfastate_t *cur_state;
1072
bool at_init_state = p_match_first != NULL;
1073
Idx next_start_idx = cur_str_idx;
1066
int at_init_state = p_match_first != NULL;
1067
int next_start_idx = cur_str_idx;
1074
1068
1075
1069
err = REG_NOERROR;
1076
1070
cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1078
1072
if (BE (cur_state == NULL, 0))
1079
1073
{
1080
1074
assert (err == REG_ESPACE);
1081
return REG_ERROR;
1075
return -2;
1082
1076
}
1083
1077
1084
1078
if (mctx->state_log != NULL)
1089
1083
later. E.g. Processing back references. */
1090
1084
if (BE (dfa->nbackref, 0))
1091
1085
{
1092
at_init_state = false;
1086
at_init_state = 0;
1093
1087
err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1094
1088
if (BE (err != REG_NOERROR, 0))
1095
1089
return err;
1122
1116
while (!re_string_eoi (&mctx->input))
1123
1117
{
1124
1118
re_dfastate_t *old_state = cur_state;
1125
Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1119
int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1126
1120
1127
1121
if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1128
1122
|| (BE (next_char_idx >= mctx->input.valid_len, 0)
1132
1126
if (BE (err != REG_NOERROR, 0))
1133
1127
{
1134
1128
assert (err == REG_ESPACE);
1135
return REG_ERROR;
1129
return -2;
1136
1130
}
1137
1131
}
1138
1132
1146
1140
state using the state log, if available and if we have not
1147
1141
already found a valid (even if not the longest) match. */
1148
1142
if (BE (err != REG_NOERROR, 0))
1149
return REG_ERROR;
1143
return -2;
1150
1144
1151
1145
if (mctx->state_log == NULL
1152
1146
|| (match && !fl_longest_match)
1159
1153
if (old_state == cur_state)
1160
1154
next_start_idx = next_char_idx;
1161
1155
else
1162
at_init_state = false;
1156
at_init_state = 0;
1163
1157
}
1164
1158
1165
1159
if (cur_state->halt)
1190
1184
1191
1185
/* Check NODE match the current context. */
1192
1186
1193
static bool
1194
internal_function
1195
check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1187
static int check_halt_node_context (dfa, node, context)
1188
const re_dfa_t *dfa;
1189
int node;
1190
unsigned int context;
1196
1191
{
1197
1192
re_token_type_t type = dfa->nodes[node].type;
1198
1193
unsigned int constraint = dfa->nodes[node].constraint;
1199
1194
if (type != END_OF_RE)
1200
return false;
1195
return 0;
1201
1196
if (!constraint)
1202
return true;
1197
return 1;
1203
1198
if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1204
return false;
1205
return true;
1199
return 0;
1200
return 1;
1206
1201
}
1207
1202
1208
1203
/* Check the halt state STATE match the current context.
1209
1204
Return 0 if not match, if the node, STATE has, is a halt node and
1210
1205
match the context, return the node. */
1211
1206
1212
static Idx
1213
internal_function
1214
check_halt_state_context (const re_match_context_t *mctx,
1215
const re_dfastate_t *state, Idx idx)
1207
static int
1208
check_halt_state_context (mctx, state, idx)
1209
const re_match_context_t *mctx;
1210
const re_dfastate_t *state;
1211
int idx;
1216
1212
{
1217
Idx i;
1213
int i;
1218
1214
unsigned int context;
1219
1215
#ifdef DEBUG
1220
1216
assert (state->halt);
1228
1224
1229
1225
/* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1230
1226
corresponding to the DFA).
1231
Return the destination node, and update EPS_VIA_NODES;
1232
return REG_MISSING in case of errors. */
1227
Return the destination node, and update EPS_VIA_NODES, return -1 in case
1228
of errors. */
1233
1229
1234
static Idx
1235
internal_function
1236
proceed_next_node (const re_match_context_t *mctx,
1237
Idx nregs, regmatch_t *regs, Idx *pidx, Idx node,
1238
re_node_set *eps_via_nodes, struct re_fail_stack_t *fs)
1230
static int
1231
proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
1232
const re_match_context_t *mctx;
1233
regmatch_t *regs;
1234
int nregs, *pidx, node;
1235
re_node_set *eps_via_nodes;
1236
struct re_fail_stack_t *fs;
1239
1237
{
1240
1238
re_dfa_t *const dfa = mctx->dfa;
1241
Idx i;
1242
bool ok;
1239
int i, err, dest_node;
1240
dest_node = -1;
1243
1241
if (IS_EPSILON_NODE (dfa->nodes[node].type))
1244
1242
{
1245
1243
re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1246
1244
re_node_set *edests = &dfa->edests[node];
1247
Idx dest_node;
1248
ok = re_node_set_insert (eps_via_nodes, node);
1249
if (BE (! ok, 0))
1250
return REG_ERROR;
1251
/* Pick up a valid destination, or return REG_MISSING if none
1252
is found. */
1253
for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1245
int dest_node;
1246
err = re_node_set_insert (eps_via_nodes, node);
1247
if (BE (err < 0, 0))
1248
return -2;
1249
/* Pick up a valid destination, or return -1 if none is found. */
1250
for (dest_node = -1, i = 0; i < edests->nelem; ++i)
1254
1251
{
1255
Idx candidate = edests->elems[i];
1252
int candidate = edests->elems[i];
1256
1253
if (!re_node_set_contains (cur_nodes, candidate))
1257
1254
continue;
1258
if (dest_node == REG_MISSING)
1255
if (dest_node == -1)
1259
1256
dest_node = candidate;
1260
1257
1261
1258
else
1269
1266
else if (fs != NULL
1270
1267
&& push_fail_stack (fs, *pidx, candidate, nregs, regs,
1271
1268
eps_via_nodes))
1272
return REG_ERROR;
1269
return -2;
1273
1270
1274
1271
/* We know we are going to exit. */
1275
1272
break;
1279
1276
}
1280
1277
else
1281
1278
{
1282
Idx naccepted = 0;
1279
int naccepted = 0;
1283
1280
re_token_type_t type = dfa->nodes[node].type;
1284
1281
1285
1282
#ifdef RE_ENABLE_I18N
1289
1286
#endif /* RE_ENABLE_I18N */
1290
1287
if (type == OP_BACK_REF)
1291
1288
{
1292
Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1289
int subexp_idx = dfa->nodes[node].opr.idx + 1;
1293
1290
naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1294
1291
if (fs != NULL)
1295
1292
{
1296
1293
if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1297
return REG_MISSING;
1294
return -1;
1298
1295
else if (naccepted)
1299
1296
{
1300
1297
char *buf = (char *) re_string_get_buffer (&mctx->input);
1301
1298
if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1302
1299
naccepted) != 0)
1303
return REG_MISSING;
1300
return -1;
1304
1301
}
1305
1302
}
1306
1303
1307
1304
if (naccepted == 0)
1308
1305
{
1309
Idx dest_node;
1310
ok = re_node_set_insert (eps_via_nodes, node);
1311
if (BE (! ok, 0))
1312
return REG_ERROR;
1306
err = re_node_set_insert (eps_via_nodes, node);
1307
if (BE (err < 0, 0))
1308
return -2;
1313
1309
dest_node = dfa->edests[node].elems[0];
1314
1310
if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1315
1311
dest_node))
1320
1316
if (naccepted != 0
1321
1317
|| check_node_accept (mctx, dfa->nodes + node, *pidx))
1322
1318
{
1323
Idx dest_node = dfa->nexts[node];
1319
dest_node = dfa->nexts[node];
1324
1320
*pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1325
1321
if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1326
1322
|| !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1327
1323
dest_node)))
1328
return REG_MISSING;
1324
return -1;
1329
1325
re_node_set_empty (eps_via_nodes);
1330
1326
return dest_node;
1331
1327
}
1332
1328
}
1333
return REG_MISSING;
1329
return -1;
1334
1330
}
1335
1331
1336
1332
static reg_errcode_t
1337
internal_function
1338
push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1339
Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1333
push_fail_stack (fs, str_idx, dest_node, nregs, regs, eps_via_nodes)
1334
struct re_fail_stack_t *fs;
1335
int str_idx, dest_node, nregs;
1336
regmatch_t *regs;
1337
re_node_set *eps_via_nodes;
1340
1338
{
1341
1339
reg_errcode_t err;
1342
Idx num = fs->num++;
1340
int num = fs->num++;
1343
1341
if (fs->num == fs->alloc)
1344
1342
{
1345
struct re_fail_stack_ent_t *new_array =
1346
re_x2realloc (fs->stack, struct re_fail_stack_ent_t, &fs->alloc);
1343
struct re_fail_stack_ent_t *new_array;
1344
new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1345
* fs->alloc * 2));
1347
1346
if (new_array == NULL)
1348
1347
return REG_ESPACE;
1348
fs->alloc *= 2;
1349
1349
fs->stack = new_array;
1350
1350
}
1351
1351
fs->stack[num].idx = str_idx;
1352
1352
fs->stack[num].node = dest_node;
1353
fs->stack[num].regs = re_xmalloc (regmatch_t, nregs);
1353
fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1354
1354
if (fs->stack[num].regs == NULL)
1355
1355
return REG_ESPACE;
1356
1356
memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1358
1358
return err;
1359
1359
}
1360
1360
1361
static Idx
1362
internal_function
1363
pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx,
1364
Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1361
static int
1362
pop_fail_stack (fs, pidx, nregs, regs, eps_via_nodes)
1363
struct re_fail_stack_t *fs;
1364
int *pidx, nregs;
1365
regmatch_t *regs;
1366
re_node_set *eps_via_nodes;
1365
1367
{
1366
Idx num = --fs->num;
1367
assert (REG_VALID_INDEX (num));
1368
int num = --fs->num;
1369
assert (num >= 0);
1368
1370
*pidx = fs->stack[num].idx;
1369
1371
memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1370
1372
re_node_set_free (eps_via_nodes);
1379
1381
pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1380
1382
1381
1383
static reg_errcode_t
1382
internal_function
1383
set_regs (const regex_t *preg, const re_match_context_t *mctx,
1384
size_t nmatch, regmatch_t *pmatch, bool fl_backtrack)
1384
set_regs (preg, mctx, nmatch, pmatch, fl_backtrack)
1385
const regex_t *preg;
1386
const re_match_context_t *mctx;
1387
size_t nmatch;
1388
regmatch_t *pmatch;
1389
int fl_backtrack;
1385
1390
{
1386
re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1387
Idx idx, cur_node;
1391
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1392
int idx, cur_node;
1388
1393
re_node_set eps_via_nodes;
1389
1394
struct re_fail_stack_t *fs;
1390
1395
struct re_fail_stack_t fs_body = { 0, 2, NULL };
1391
1396
regmatch_t *prev_idx_match;
1392
bool prev_idx_match_malloced = false;
1393
1397
1394
1398
#ifdef DEBUG
1395
1399
assert (nmatch > 1);
1398
1402
if (fl_backtrack)
1399
1403
{
1400
1404
fs = &fs_body;
1401
fs->stack = re_xmalloc (struct re_fail_stack_ent_t, fs->alloc);
1405
fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1402
1406
if (fs->stack == NULL)
1403
1407
return REG_ESPACE;
1404
1408
}
1408
1412
cur_node = dfa->init_node;
1409
1413
re_node_set_init_empty (&eps_via_nodes);
1410
1414
1411
if (re_alloc_oversized (nmatch, sizeof (regmatch_t)))
1412
{
1413
free_fail_stack_return (fs);
1414
return REG_ESPACE;
1415
}
1416
if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1417
prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1418
else
1419
{
1420
prev_idx_match = re_malloc (regmatch_t, nmatch);
1421
if (prev_idx_match == NULL)
1422
{
1423
free_fail_stack_return (fs);
1424
return REG_ESPACE;
1425
}
1426
prev_idx_match_malloced = true;
1427
}
1415
prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * nmatch);
1428
1416
memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1429
1417
1430
1418
for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1433
1421
1434
1422
if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1435
1423
{
1436
Idx reg_idx;
1424
int reg_idx;
1437
1425
if (fs)
1438
1426
{
1439
1427
for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1442
1430
if (reg_idx == nmatch)
1443
1431
{
1444
1432
re_node_set_free (&eps_via_nodes);
1445
if (prev_idx_match_malloced)
1446
re_free (prev_idx_match);
1447
1433
return free_fail_stack_return (fs);
1448
1434
}
1449
1435
cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1452
1438
else
1453
1439
{
1454
1440
re_node_set_free (&eps_via_nodes);
1455
if (prev_idx_match_malloced)
1456
re_free (prev_idx_match);
1457
1441
return REG_NOERROR;
1458
1442
}
1459
1443
}
1462
1446
cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1463
1447
&eps_via_nodes, fs);
1464
1448
1465
if (BE (! REG_VALID_INDEX (cur_node), 0))
1449
if (BE (cur_node < 0, 0))
1466
1450
{
1467
if (BE (cur_node == REG_ERROR, 0))
1451
if (BE (cur_node == -2, 0))
1468
1452
{
1469
1453
re_node_set_free (&eps_via_nodes);
1470
if (prev_idx_match_malloced)
1471
re_free (prev_idx_match);
1472
1454
free_fail_stack_return (fs);
1473
1455
return REG_ESPACE;
1474
1456
}
1478
1460
else
1479
1461
{
1480
1462
re_node_set_free (&eps_via_nodes);
1481
if (prev_idx_match_malloced)
1482
re_free (prev_idx_match);
1483
1463
return REG_NOMATCH;
1484
1464
}
1485
1465
}
1486
1466
}
1487
1467
re_node_set_free (&eps_via_nodes);
1488
if (prev_idx_match_malloced)
1489
re_free (prev_idx_match);
1490
1468
return free_fail_stack_return (fs);
1491
1469
}
1492
1470
1493
1471
static reg_errcode_t
1494
internal_function
1495
free_fail_stack_return (struct re_fail_stack_t *fs)
1472
free_fail_stack_return (fs)
1473
struct re_fail_stack_t *fs;
1496
1474
{
1497
1475
if (fs)
1498
1476
{
1499
Idx fs_idx;
1477
int fs_idx;
1500
1478
for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1501
1479
{
1502
1480
re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1508
1486
}
1509
1487
1510
1488
static void
1511
internal_function
1512
update_regs (re_dfa_t *dfa, regmatch_t *pmatch, regmatch_t *prev_idx_match,
1513
Idx cur_node, Idx cur_idx, Idx nmatch)
1489
update_regs (dfa, pmatch, prev_idx_match, cur_node, cur_idx, nmatch)
1490
re_dfa_t *dfa;
1491
regmatch_t *pmatch, *prev_idx_match;
1492
int cur_node, cur_idx, nmatch;
1514
1493
{
1515
1494
int type = dfa->nodes[cur_node].type;
1516
1495
if (type == OP_OPEN_SUBEXP)
1517
1496
{
1518
Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1497
int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1519
1498
1520
1499
/* We are at the first node of this sub expression. */
1521
1500
if (reg_num < nmatch)
1526
1505
}
1527
1506
else if (type == OP_CLOSE_SUBEXP)
1528
1507
{
1529
Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1508
int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1530
1509
if (reg_num < nmatch)
1531
1510
{
1532
1511
/* We are at the last node of this sub expression. */
1580
1559
((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1581
1560
1582
1561
static reg_errcode_t
1583
internal_function
1584
sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx)
1562
sift_states_backward (mctx, sctx)
1563
re_match_context_t *mctx;
1564
re_sift_context_t *sctx;
1585
1565
{
1586
1566
reg_errcode_t err;
1587
1567
int null_cnt = 0;
1588
Idx str_idx = sctx->last_str_idx;
1568
int str_idx = sctx->last_str_idx;
1589
1569
re_node_set cur_dest;
1590
1570
1591
1571
#ifdef DEBUG
1638
1618
}
1639
1619
1640
1620
static reg_errcode_t
1641
internal_function
1642
build_sifted_states (re_match_context_t *mctx, re_sift_context_t *sctx,
1643
Idx str_idx, re_node_set *cur_dest)
1621
build_sifted_states (mctx, sctx, str_idx, cur_dest)
1622
re_match_context_t *mctx;
1623
re_sift_context_t *sctx;
1624
int str_idx;
1625
re_node_set *cur_dest;
1644
1626
{
1645
1627
re_dfa_t *const dfa = mctx->dfa;
1646
1628
re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1647
Idx i;
1629
int i;
1648
1630
1649
1631
/* Then build the next sifted state.
1650
1632
We build the next sifted state on `cur_dest', and update
1655
1637
(with the epsilon nodes pre-filtered out). */
1656
1638
for (i = 0; i < cur_src->nelem; i++)
1657
1639
{
1658
Idx prev_node = cur_src->elems[i];
1640
int prev_node = cur_src->elems[i];
1659
1641
int naccepted = 0;
1660
bool ok;
1642
int ret;
1661
1643
1662
1644
#ifdef DEBUG
1663
1645
re_token_type_t type = dfa->nodes[prev_node].type;
1683
1665
1684
1666
if (sctx->limits.nelem)
1685
1667
{
1686
Idx to_idx = str_idx + naccepted;
1668
int to_idx = str_idx + naccepted;
1687
1669
if (check_dst_limits (mctx, &sctx->limits,
1688
1670
dfa->nexts[prev_node], to_idx,
1689
1671
prev_node, str_idx))
1690
1672
continue;
1691
1673
}
1692
ok = re_node_set_insert (cur_dest, prev_node);
1693
if (BE (! ok, 0))
1674
ret = re_node_set_insert (cur_dest, prev_node);
1675
if (BE (ret == -1, 0))
1694
1676
return REG_ESPACE;
1695
1677
}
1696
1678
1700
1682
/* Helper functions. */
1701
1683
1702
1684
static reg_errcode_t
1703
internal_function
1704
clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1685
clean_state_log_if_needed (mctx, next_state_log_idx)
1686
re_match_context_t *mctx;
1687
int next_state_log_idx;
1705
1688
{
1706
Idx top = mctx->state_log_top;
1689
int top = mctx->state_log_top;
1707
1690
1708
1691
if (next_state_log_idx >= mctx->input.bufs_len
1709
1692
|| (next_state_log_idx >= mctx->input.valid_len
1725
1708
}
1726
1709
1727
1710
static reg_errcode_t
1728
internal_function
1729
merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, re_dfastate_t **src,
1730
Idx num)
1711
merge_state_array (dfa, dst, src, num)
1712
re_dfa_t *dfa;
1713
re_dfastate_t **dst;
1714
re_dfastate_t **src;
1715
int num;
1731
1716
{
1732
Idx st_idx;
1717
int st_idx;
1733
1718
reg_errcode_t err;
1734
1719
for (st_idx = 0; st_idx < num; ++st_idx)
1735
1720
{
1752
1737
}
1753
1738
1754
1739
static reg_errcode_t
1755
internal_function
1756
update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx,
1757
Idx str_idx, re_node_set *dest_nodes)
1740
update_cur_sifted_state (mctx, sctx, str_idx, dest_nodes)
1741
re_match_context_t *mctx;
1742
re_sift_context_t *sctx;
1743
int str_idx;
1744
re_node_set *dest_nodes;
1758
1745
{
1759
1746
re_dfa_t *const dfa = mctx->dfa;
1760
1747
reg_errcode_t err;
1799
1786
}
1800
1787
1801
1788
static reg_errcode_t
1802
internal_function
1803
add_epsilon_src_nodes (re_dfa_t *dfa, re_node_set *dest_nodes,
1804
const re_node_set *candidates)
1789
add_epsilon_src_nodes (dfa, dest_nodes, candidates)
1790
re_dfa_t *dfa;
1791
re_node_set *dest_nodes;
1792
const re_node_set *candidates;
1805
1793
{
1806
1794
reg_errcode_t err = REG_NOERROR;
1807
Idx i;
1795
int i;
1808
1796
1809
1797
re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1810
1798
if (BE (err != REG_NOERROR, 0))
1824
1812
}
1825
1813
1826
1814
static reg_errcode_t
1827
internal_function
1828
sub_epsilon_src_nodes (re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1829
const re_node_set *candidates)
1815
sub_epsilon_src_nodes (dfa, node, dest_nodes, candidates)
1816
re_dfa_t *dfa;
1817
int node;
1818
re_node_set *dest_nodes;
1819
const re_node_set *candidates;
1830
1820
{
1831
Idx ecl_idx;
1821
int ecl_idx;
1832
1822
reg_errcode_t err;
1833
1823
re_node_set *inv_eclosure = dfa->inveclosures + node;
1834
1824
re_node_set except_nodes;
1835
1825
re_node_set_init_empty (&except_nodes);
1836
1826
for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1837
1827
{
1838
Idx cur_node = inv_eclosure->elems[ecl_idx];
1828
int cur_node = inv_eclosure->elems[ecl_idx];
1839
1829
if (cur_node == node)
1840
1830
continue;
1841
1831
if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1842
1832
{
1843
Idx edst1 = dfa->edests[cur_node].elems[0];
1844
Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1845
? dfa->edests[cur_node].elems[1] : REG_MISSING);
1833
int edst1 = dfa->edests[cur_node].elems[0];
1834
int edst2 = ((dfa->edests[cur_node].nelem > 1)
1835
? dfa->edests[cur_node].elems[1] : -1);
1846
1836
if ((!re_node_set_contains (inv_eclosure, edst1)
1847
1837
&& re_node_set_contains (dest_nodes, edst1))
1848
|| (REG_VALID_NONZERO_INDEX (edst2)
1838
|| (edst2 > 0
1849
1839
&& !re_node_set_contains (inv_eclosure, edst2)
1850
1840
&& re_node_set_contains (dest_nodes, edst2)))
1851
1841
{
1861
1851
}
1862
1852
for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1863
1853
{
1864
Idx cur_node = inv_eclosure->elems[ecl_idx];
1854
int cur_node = inv_eclosure->elems[ecl_idx];
1865
1855
if (!re_node_set_contains (&except_nodes, cur_node))
1866
1856
{
1867
Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1857
int idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1868
1858
re_node_set_remove_at (dest_nodes, idx);
1869
1859
}
1870
1860
}
1872
1862
return REG_NOERROR;
1873
1863
}
1874
1864
1875
static bool
1876
internal_function
1877
check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1878
Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1865
static int
1866
check_dst_limits (mctx, limits, dst_node, dst_idx, src_node, src_idx)
1867
re_match_context_t *mctx;
1868
re_node_set *limits;
1869
int dst_node, dst_idx, src_node, src_idx;
1879
1870
{
1880
1871
re_dfa_t *const dfa = mctx->dfa;
1881
Idx lim_idx, src_pos, dst_pos;
1872
int lim_idx, src_pos, dst_pos;
1882
1873
1883
Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1884
Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1874
int dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1875
int src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1885
1876
for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1886
1877
{
1887
Idx subexp_idx;
1878
int subexp_idx;
1888
1879
struct re_backref_cache_entry *ent;
1889
1880
ent = mctx->bkref_ents + limits->elems[lim_idx];
1890
1881
subexp_idx = dfa->nodes[ent->node].opr.idx;
1903
1894
if (src_pos == dst_pos)
1904
1895
continue; /* This is unrelated limitation. */
1905
1896
else
1906
return true;
1897
return 1;
1907
1898
}
1908
return false;
1899
return 0;
1909
1900
}
1910
1901
1911
1902
static int
1912
internal_function
1913
check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1914
Idx subexp_idx, Idx from_node, Idx bkref_idx)
1903
check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx)
1904
re_match_context_t *mctx;
1905
int boundaries, subexp_idx, from_node, bkref_idx;
1915
1906
{
1916
1907
re_dfa_t *const dfa = mctx->dfa;
1917
1908
re_node_set *eclosures = dfa->eclosures + from_node;
1918
Idx node_idx;
1909
int node_idx;
1919
1910
1920
1911
/* Else, we are on the boundary: examine the nodes on the epsilon
1921
1912
closure. */
1922
1913
for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1923
1914
{
1924
Idx node = eclosures->elems[node_idx];
1915
int node = eclosures->elems[node_idx];
1925
1916
switch (dfa->nodes[node].type)
1926
1917
{
1927
1918
case OP_BACK_REF:
1928
if (bkref_idx != REG_MISSING)
1919
if (bkref_idx != -1)
1929
1920
{
1930
1921
struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1931
1922
do
1932
1923
{
1933
Idx dst;
1934
int cpos;
1924
int dst, cpos;
1935
1925
1936
1926
if (ent->node != node)
1937
1927
continue;
1938
1928
1939
if (subexp_idx < BITSET_WORD_BITS
1940
&& !(ent->eps_reachable_subexps_map
1941
& ((bitset_word) 1 << subexp_idx)))
1929
if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map)
1930
&& !(ent->eps_reachable_subexps_map & (1 << subexp_idx)))
1942
1931
continue;
1943
1932
1944
1933
/* Recurse trying to reach the OP_OPEN_SUBEXP and
1964
1953
if (cpos == 0 && (boundaries & 2))
1965
1954
return 0;
1966
1955
1967
if (subexp_idx < BITSET_WORD_BITS)
1968
ent->eps_reachable_subexps_map &=
1969
~ ((bitset_word) 1 << subexp_idx);
1956
ent->eps_reachable_subexps_map &= ~(1 << subexp_idx);
1970
1957
}
1971
1958
while (ent++->more);
1972
1959
}
1991
1978
}
1992
1979
1993
1980
static int
1994
internal_function
1995
check_dst_limits_calc_pos (const re_match_context_t *mctx,
1996
Idx limit, Idx subexp_idx,
1997
Idx from_node, Idx str_idx, Idx bkref_idx)
1981
check_dst_limits_calc_pos (mctx, limit, subexp_idx, from_node, str_idx, bkref_idx)
1982
re_match_context_t *mctx;
1983
int limit, subexp_idx, from_node, str_idx, bkref_idx;
1998
1984
{
1999
1985
struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2000
1986
int boundaries;
2021
2007
which are against limitations from DEST_NODES. */
2022
2008
2023
2009
static reg_errcode_t
2024
internal_function
2025
check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes,
2026
const re_node_set *candidates, re_node_set *limits,
2027
struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2010
check_subexp_limits (dfa, dest_nodes, candidates, limits, bkref_ents, str_idx)
2011
re_dfa_t *dfa;
2012
re_node_set *dest_nodes;
2013
const re_node_set *candidates;
2014
re_node_set *limits;
2015
struct re_backref_cache_entry *bkref_ents;
2016
int str_idx;
2028
2017
{
2029
2018
reg_errcode_t err;
2030
Idx node_idx, lim_idx;
2019
int node_idx, lim_idx;
2031
2020
2032
2021
for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2033
2022
{
2034
Idx subexp_idx;
2023
int subexp_idx;
2035
2024
struct re_backref_cache_entry *ent;
2036
2025
ent = bkref_ents + limits->elems[lim_idx];
2037
2026
2041
2030
subexp_idx = dfa->nodes[ent->node].opr.idx;
2042
2031
if (ent->subexp_to == str_idx)
2043
2032
{
2044
Idx ops_node = REG_MISSING;
2045
Idx cls_node = REG_MISSING;
2033
int ops_node = -1;
2034
int cls_node = -1;
2046
2035
for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2047
2036
{
2048
Idx node = dest_nodes->elems[node_idx];
2037
int node = dest_nodes->elems[node_idx];
2049
2038
re_token_type_t type = dfa->nodes[node].type;
2050
2039
if (type == OP_OPEN_SUBEXP
2051
2040
&& subexp_idx == dfa->nodes[node].opr.idx)
2057
2046
2058
2047
/* Check the limitation of the open subexpression. */
2059
2048
/* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2060
if (REG_VALID_INDEX (ops_node))
2049
if (ops_node >= 0)
2061
2050
{
2062
2051
err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2063
2052
candidates);
2066
2055
}
2067
2056
2068
2057
/* Check the limitation of the close subexpression. */
2069
if (REG_VALID_INDEX (cls_node))
2058
if (cls_node >= 0)
2070
2059
for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2071
2060
{
2072
Idx node = dest_nodes->elems[node_idx];
2061
int node = dest_nodes->elems[node_idx];
2073
2062
if (!re_node_set_contains (dfa->inveclosures + node,
2074
2063
cls_node)
2075
2064
&& !re_node_set_contains (dfa->eclosures + node,
2089
2078
{
2090
2079
for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2091
2080
{
2092
Idx node = dest_nodes->elems[node_idx];
2081
int node = dest_nodes->elems[node_idx];
2093
2082
re_token_type_t type = dfa->nodes[node].type;
2094
2083
if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2095
2084
{
2109
2098
}
2110
2099
2111
2100
static reg_errcode_t
2112
internal_function
2113
sift_states_bkref (re_match_context_t *mctx, re_sift_context_t *sctx,
2114
Idx str_idx, const re_node_set *candidates)
2101
sift_states_bkref (mctx, sctx, str_idx, candidates)
2102
re_match_context_t *mctx;
2103
re_sift_context_t *sctx;
2104
int str_idx;
2105
const re_node_set *candidates;
2115
2106
{
2116
2107
re_dfa_t *const dfa = mctx->dfa;
2117
2108
reg_errcode_t err;
2118
Idx node_idx, node;
2109
int node_idx, node;
2119
2110
re_sift_context_t local_sctx;
2120
Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2111
int first_idx = search_cur_bkref_entry (mctx, str_idx);
2121
2112
2122
if (first_idx == REG_MISSING)
2113
if (first_idx == -1)
2123
2114
return REG_NOERROR;
2124
2115
2125
2116
local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2126
2117
2127
2118
for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2128
2119
{
2129
Idx enabled_idx;
2120
int enabled_idx;
2130
2121
re_token_type_t type;
2131
2122
struct re_backref_cache_entry *entry;
2132
2123
node = candidates->elems[node_idx];
2141
2132
enabled_idx = first_idx;
2142
2133
do
2143
2134
{
2144
bool ok;
2145
Idx subexp_len, to_idx, dst_node;
2135
int subexp_len, to_idx, dst_node;
2146
2136
re_dfastate_t *cur_state;
2147
2137
2148
2138
if (entry->node != node)
2168
2158
}
2169
2159
local_sctx.last_node = node;
2170
2160
local_sctx.last_str_idx = str_idx;
2171
ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2172
if (BE (! ok, 0))
2161
err = re_node_set_insert (&local_sctx.limits, enabled_idx);
2162
if (BE (err < 0, 0))
2173
2163
{
2174
2164
err = REG_ESPACE;
2175
2165
goto free_return;
2207
2197
2208
2198
#ifdef RE_ENABLE_I18N
2209
2199
static int
2210
internal_function
2211
sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2212
Idx node_idx, Idx str_idx, Idx max_str_idx)
2200
sift_states_iter_mb (mctx, sctx, node_idx, str_idx, max_str_idx)
2201
const re_match_context_t *mctx;
2202
re_sift_context_t *sctx;
2203
int node_idx, str_idx, max_str_idx;
2213
2204
{
2214
2205
re_dfa_t *const dfa = mctx->dfa;
2215
2206
int naccepted;
2237
2228
update the destination of STATE_LOG. */
2238
2229
2239
2230
static re_dfastate_t *
2240
internal_function
2241
transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2242
re_dfastate_t *state)
2231
transit_state (err, mctx, state)
2232
reg_errcode_t *err;
2233
re_match_context_t *mctx;
2234
re_dfastate_t *state;
2243
2235
{
2244
2236
re_dfastate_t **trtable;
2245
2237
unsigned char ch;
2295
2287
2296
2288
/* Update the state_log if we need */
2297
2289
re_dfastate_t *
2298
internal_function
2299
merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2300
re_dfastate_t *next_state)
2290
merge_state_with_log (err, mctx, next_state)
2291
reg_errcode_t *err;
2292
re_match_context_t *mctx;
2293
re_dfastate_t *next_state;
2301
2294
{
2302
2295
re_dfa_t *const dfa = mctx->dfa;
2303
Idx cur_idx = re_string_cur_idx (&mctx->input);
2296
int cur_idx = re_string_cur_idx (&mctx->input);
2304
2297
2305
2298
if (cur_idx > mctx->state_log_top)
2306
2299
{
2373
2366
/* Skip bytes in the input that correspond to part of a
2374
2367
multi-byte match, then look in the log for a state
2375
2368
from which to restart matching. */
2376
static re_dfastate_t *
2377
internal_function
2378
find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2369
re_dfastate_t *
2370
find_recover_state (err, mctx)
2371
reg_errcode_t *err;
2372
re_match_context_t *mctx;
2379
2373
{
2380
2374
re_dfastate_t *cur_state = NULL;
2381
2375
do
2382
2376
{
2383
Idx max = mctx->state_log_top;
2384
Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2377
int max = mctx->state_log_top;
2378
int cur_str_idx = re_string_cur_idx (&mctx->input);
2385
2379
2386
2380
do
2387
2381
{
2393
2387
2394
2388
cur_state = merge_state_with_log (err, mctx, NULL);
2395
2389
}
2396
while (*err == REG_NOERROR && cur_state == NULL);
2390
while (err == REG_NOERROR && cur_state == NULL);
2397
2391
return cur_state;
2398
2392
}
2399
2393
2405
2399
correspoding back references. */
2406
2400
2407
2401
static reg_errcode_t
2408
internal_function
2409
check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2410
Idx str_idx)
2402
check_subexp_matching_top (mctx, cur_nodes, str_idx)
2403
re_match_context_t *mctx;
2404
re_node_set *cur_nodes;
2405
int str_idx;
2411
2406
{
2412
2407
re_dfa_t *const dfa = mctx->dfa;
2413
Idx node_idx;
2408
int node_idx;
2414
2409
reg_errcode_t err;
2415
2410
2416
2411
/* TODO: This isn't efficient.
2420
2415
E.g. RE: (a){2} */
2421
2416
for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2422
2417
{
2423
Idx node = cur_nodes->elems[node_idx];
2418
int node = cur_nodes->elems[node_idx];
2424
2419
if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2425
&& dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2426
&& (dfa->used_bkref_map
2427
& ((bitset_word) 1 << dfa->nodes[node].opr.idx)))
2420
&& dfa->nodes[node].opr.idx < (8 * sizeof (dfa->used_bkref_map))
2421
&& dfa->used_bkref_map & (1 << dfa->nodes[node].opr.idx))
2428
2422
{
2429
2423
err = match_ctx_add_subtop (mctx, node, str_idx);
2430
2424
if (BE (err != REG_NOERROR, 0))
2439
2433
accepting the current input byte. */
2440
2434
2441
2435
static re_dfastate_t *
2442
transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2443
re_dfastate_t *state)
2436
transit_state_sb (err, mctx, state)
2437
reg_errcode_t *err;
2438
re_match_context_t *mctx;
2439
re_dfastate_t *state;
2444
2440
{
2445
2441
re_dfa_t *const dfa = mctx->dfa;
2446
2442
re_node_set next_nodes;
2447
2443
re_dfastate_t *next_state;
2448
Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2444
int node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2449
2445
unsigned int context;
2450
2446
2451
2447
*err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2453
2449
return NULL;
2454
2450
for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2455
2451
{
2456
Idx cur_node = state->nodes.elems[node_cnt];
2452
int cur_node = state->nodes.elems[node_cnt];
2457
2453
if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2458
2454
{
2459
2455
*err = re_node_set_merge (&next_nodes,
2478
2474
2479
2475
#ifdef RE_ENABLE_I18N
2480
2476
static reg_errcode_t
2481
internal_function
2482
transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2477
transit_state_mb (mctx, pstate)
2478
re_match_context_t *mctx;
2479
re_dfastate_t *pstate;
2483
2480
{
2484
2481
re_dfa_t *const dfa = mctx->dfa;
2485
2482
reg_errcode_t err;
2486
Idx i;
2483
int i;
2487
2484
2488
2485
for (i = 0; i < pstate->nodes.nelem; ++i)
2489
2486
{
2490
2487
re_node_set dest_nodes, *new_nodes;
2491
Idx cur_node_idx = pstate->nodes.elems[i];
2492
int naccepted;
2493
Idx dest_idx;
2488
int cur_node_idx = pstate->nodes.elems[i];
2489
int naccepted, dest_idx;
2494
2490
unsigned int context;
2495
2491
re_dfastate_t *dest_state;
2496
2492
2521
2517
if (BE (err != REG_NOERROR, 0))
2522
2518
return err;
2523
2519
#ifdef DEBUG
2524
assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2520
assert (dfa->nexts[cur_node_idx] != -1);
2525
2521
#endif
2526
2522
new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2527
2523
2548
2544
#endif /* RE_ENABLE_I18N */
2549
2545
2550
2546
static reg_errcode_t
2551
internal_function
2552
transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2547
transit_state_bkref (mctx, nodes)
2548
re_match_context_t *mctx;
2549
const re_node_set *nodes;
2553
2550
{
2554
2551
re_dfa_t *const dfa = mctx->dfa;
2555
2552
reg_errcode_t err;
2556
Idx i;
2557
Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2553
int i;
2554
int cur_str_idx = re_string_cur_idx (&mctx->input);
2558
2555
2559
2556
for (i = 0; i < nodes->nelem; ++i)
2560
2557
{
2561
Idx dest_str_idx, prev_nelem, bkc_idx;
2562
Idx node_idx = nodes->elems[i];
2558
int dest_str_idx, prev_nelem, bkc_idx;
2559
int node_idx = nodes->elems[i];
2563
2560
unsigned int context;
2564
2561
const re_token_t *node = dfa->nodes + node_idx;
2565
2562
re_node_set *new_dest_nodes;
2586
2583
/* And add the epsilon closures (which is `new_dest_nodes') of
2587
2584
the backreference to appropriate state_log. */
2588
2585
#ifdef DEBUG
2589
assert (dfa->nexts[node_idx] != REG_MISSING);
2586
assert (dfa->nexts[node_idx] != -1);
2590
2587
#endif
2591
2588
for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2592
2589
{
2593
Idx subexp_len;
2590
int subexp_len;
2594
2591
re_dfastate_t *dest_state;
2595
2592
struct re_backref_cache_entry *bkref_ent;
2596
2593
bkref_ent = mctx->bkref_ents + bkc_idx;
2662
2659
delay these checking for prune_impossible_nodes(). */
2663
2660
2664
2661
static reg_errcode_t
2665
internal_function
2666
get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2662
get_subexp (mctx, bkref_node, bkref_str_idx)
2663
re_match_context_t *mctx;
2664
int bkref_node, bkref_str_idx;
2667
2665
{
2668
2666
re_dfa_t *const dfa = mctx->dfa;
2669
Idx subexp_num, sub_top_idx;
2667
int subexp_num, sub_top_idx;
2670
2668
const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2671
2669
/* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2672
Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2673
if (cache_idx != REG_MISSING)
2670
int cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2671
if (cache_idx != -1)
2674
2672
{
2675
2673
const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx;
2676
2674
do
2687
2685
reg_errcode_t err;
2688
2686
re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2689
2687
re_sub_match_last_t *sub_last;
2690
Idx sub_last_idx, sl_str, bkref_str_off;
2688
int sub_last_idx, sl_str, bkref_str_off;
2691
2689
2692
2690
if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2693
2691
continue; /* It isn't related. */
2698
2696
evaluated. */
2699
2697
for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2700
2698
{
2701
regoff_t sl_str_diff;
2699
int sl_str_diff;
2702
2700
sub_last = sub_top->lasts[sub_last_idx];
2703
2701
sl_str_diff = sub_last->str_idx - sl_str;
2704
2702
/* The matched string by the sub expression match with the substring
2743
2741
/* Then, search for the other last nodes of the sub expression. */
2744
2742
for (; sl_str <= bkref_str_idx; ++sl_str)
2745
2743
{
2746
Idx cls_node;
2747
regoff_t sl_str_off;
2744
int cls_node, sl_str_off;
2748
2745
const re_node_set *nodes;
2749
2746
sl_str_off = sl_str - sub_top->str_idx;
2750
2747
/* The matched string by the sub expression match with the substring
2772
2769
/* Does this state have a ')' of the sub expression? */
2773
2770
nodes = &mctx->state_log[sl_str]->nodes;
2774
2771
cls_node = find_subexp_node (dfa, nodes, subexp_num, OP_CLOSE_SUBEXP);
2775
if (cls_node == REG_MISSING)
2772
if (cls_node == -1)
2776
2773
continue; /* No. */
2777
2774
if (sub_top->path == NULL)
2778
2775
{
2779
sub_top->path = re_calloc (state_array_t,
2780
sl_str - sub_top->str_idx + 1);
2776
sub_top->path = calloc (sizeof (state_array_t),
2777
sl_str - sub_top->str_idx + 1);
2781
2778
if (sub_top->path == NULL)
2782
2779
return REG_ESPACE;
2783
2780
}
2808
2805
and SUB_LAST. */
2809
2806
2810
2807
static reg_errcode_t
2811
internal_function
2812
get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2813
re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2808
get_subexp_sub (mctx, sub_top, sub_last, bkref_node, bkref_str)
2809
re_match_context_t *mctx;
2810
const re_sub_match_top_t *sub_top;
2811
re_sub_match_last_t *sub_last;
2812
int bkref_node, bkref_str;
2814
2813
{
2815
2814
reg_errcode_t err;
2816
Idx to_idx;
2815
int to_idx;
2817
2816
/* Can the subexpression arrive the back reference? */
2818
2817
err = check_arrival (mctx, &sub_last->path, sub_last->node,
2819
2818
sub_last->str_idx, bkref_node, bkref_str, OP_OPEN_SUBEXP);
2835
2834
nodes.
2836
2835
E.g. RE: (a){2} */
2837
2836
2838
static Idx
2839
internal_function
2840
find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2841
Idx subexp_idx, int type)
2837
static int
2838
find_subexp_node (dfa, nodes, subexp_idx, type)
2839
const re_dfa_t *dfa;
2840
const re_node_set *nodes;
2841
int subexp_idx, type;
2842
2842
{
2843
Idx cls_idx;
2843
int cls_idx;
2844
2844
for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2845
2845
{
2846
Idx cls_node = nodes->elems[cls_idx];
2846
int cls_node = nodes->elems[cls_idx];
2847
2847
const re_token_t *node = dfa->nodes + cls_node;
2848
2848
if (node->type == type
2849
2849
&& node->opr.idx == subexp_idx)
2850
2850
return cls_node;
2851
2851
}
2852
return REG_MISSING;
2852
return -1;
2853
2853
}
2854
2854
2855
2855
/* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2858
2858
Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2859
2859
2860
2860
static reg_errcode_t
2861
internal_function
2862
check_arrival (re_match_context_t *mctx, state_array_t *path,
2863
Idx top_node, Idx top_str, Idx last_node, Idx last_str,
2864
int type)
2861
check_arrival (mctx, path, top_node, top_str, last_node, last_str,
2862
type)
2863
re_match_context_t *mctx;
2864
state_array_t *path;
2865
int top_node, top_str, last_node, last_str, type;
2865
2866
{
2866
2867
re_dfa_t *const dfa = mctx->dfa;
2867
2868
reg_errcode_t err;
2868
Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2869
int subexp_num, backup_cur_idx, str_idx, null_cnt;
2869
2870
re_dfastate_t *cur_state = NULL;
2870
2871
re_node_set *cur_nodes, next_nodes;
2871
2872
re_dfastate_t **backup_state_log;
2876
2877
if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2877
2878
{
2878
2879
re_dfastate_t **new_array;
2879
Idx old_alloc = path->alloc;
2880
Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2881
if (BE (new_alloc < old_alloc, 0))
2882
return REG_ESPACE;
2883
new_array = re_xrealloc (path->array, re_dfastate_t *, new_alloc);
2884
if (BE (new_array == NULL, 0))
2885
return REG_ESPACE;
2880
int old_alloc = path->alloc;
2881
path->alloc += last_str + mctx->max_mb_elem_len + 1;
2882
new_array = re_realloc (path->array, re_dfastate_t *, path->alloc);
2883
if (new_array == NULL)
2884
{
2885
path->alloc = old_alloc;
2886
return REG_ESPACE;
2887
}
2886
2888
path->array = new_array;
2887
path->alloc = new_alloc;
2888
2889
memset (new_array + old_alloc, '\0',
2889
sizeof (re_dfastate_t *) * (new_alloc - old_alloc));
2890
sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2890
2891
}
2891
2892
2892
2893
str_idx = path->next_idx == 0 ? top_str : path->next_idx;
3019
3020
Can't we unify them? */
3020
3021
3021
3022
static reg_errcode_t
3022
internal_function
3023
check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3024
re_node_set *cur_nodes,
3025
re_node_set *next_nodes)
3023
check_arrival_add_next_nodes (mctx, str_idx, cur_nodes, next_nodes)
3024
re_match_context_t *mctx;
3025
int str_idx;
3026
re_node_set *cur_nodes, *next_nodes;
3026
3027
{
3027
3028
re_dfa_t *const dfa = mctx->dfa;
3028
bool ok;
3029
Idx cur_idx;
3029
int result;
3030
int cur_idx;
3030
3031
reg_errcode_t err;
3031
3032
re_node_set union_set;
3032
3033
re_node_set_init_empty (&union_set);
3033
3034
for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3034
3035
{
3035
3036
int naccepted = 0;
3036
Idx cur_node = cur_nodes->elems[cur_idx];
3037
int cur_node = cur_nodes->elems[cur_idx];
3037
3038
#ifdef DEBUG
3038
3039
re_token_type_t type = dfa->nodes[cur_node].type;
3039
3040
assert (!IS_EPSILON_NODE (type));
3047
3048
if (naccepted > 1)
3048
3049
{
3049
3050
re_dfastate_t *dest_state;
3050
Idx next_node = dfa->nexts[cur_node];
3051
Idx next_idx = str_idx + naccepted;
3051
int next_node = dfa->nexts[cur_node];
3052
int next_idx = str_idx + naccepted;
3052
3053
dest_state = mctx->state_log[next_idx];
3053
3054
re_node_set_empty (&union_set);
3054
3055
if (dest_state)
3060
3061
return err;
3061
3062
}
3062
3063
}
3063
ok = re_node_set_insert (&union_set, next_node);
3064
if (BE (! ok, 0))
3064
result = re_node_set_insert (&union_set, next_node);
3065
if (BE (result < 0, 0))
3065
3066
{
3066
3067
re_node_set_free (&union_set);
3067
3068
return REG_ESPACE;
3080
3081
if (naccepted
3081
3082
|| check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3082
3083
{
3083
ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3084
if (BE (! ok, 0))
3084
result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3085
if (BE (result < 0, 0))
3085
3086
{
3086
3087
re_node_set_free (&union_set);
3087
3088
return REG_ESPACE;
3099
3100
*/
3100
3101
3101
3102
static reg_errcode_t
3102
internal_function
3103
check_arrival_expand_ecl (re_dfa_t *dfa, re_node_set *cur_nodes,
3104
Idx ex_subexp, int type)
3103
check_arrival_expand_ecl (dfa, cur_nodes, ex_subexp, type)
3104
re_dfa_t *dfa;
3105
re_node_set *cur_nodes;
3106
int ex_subexp, type;
3105
3107
{
3106
3108
reg_errcode_t err;
3107
Idx idx, outside_node;
3109
int idx, outside_node;
3108
3110
re_node_set new_nodes;
3109
3111
#ifdef DEBUG
3110
3112
assert (cur_nodes->nelem);
3117
3119
3118
3120
for (idx = 0; idx < cur_nodes->nelem; ++idx)
3119
3121
{
3120
Idx cur_node = cur_nodes->elems[idx];
3122
int cur_node = cur_nodes->elems[idx];
3121
3123
re_node_set *eclosure = dfa->eclosures + cur_node;
3122
3124
outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3123
if (outside_node == REG_MISSING)
3125
if (outside_node == -1)
3124
3126
{
3125
3127
/* There are no problematic nodes, just merge them. */
3126
3128
err = re_node_set_merge (&new_nodes, eclosure);
3152
3154
problematic append it to DST_NODES. */
3153
3155
3154
3156
static reg_errcode_t
3155
internal_function
3156
check_arrival_expand_ecl_sub (re_dfa_t *dfa, re_node_set *dst_nodes,
3157
Idx target, Idx ex_subexp, int type)
3157
check_arrival_expand_ecl_sub (dfa, dst_nodes, target, ex_subexp, type)
3158
re_dfa_t *dfa;
3159
int target, ex_subexp, type;
3160
re_node_set *dst_nodes;
3158
3161
{
3159
Idx cur_node;
3162
int cur_node;
3160
3163
for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3161
3164
{
3162
bool ok;
3165
int err;
3163
3166
3164
3167
if (dfa->nodes[cur_node].type == type
3165
3168
&& dfa->nodes[cur_node].opr.idx == ex_subexp)
3166
3169
{
3167
3170
if (type == OP_CLOSE_SUBEXP)
3168
3171
{
3169
ok = re_node_set_insert (dst_nodes, cur_node);
3170
if (BE (! ok, 0))
3172
err = re_node_set_insert (dst_nodes, cur_node);
3173
if (BE (err == -1, 0))
3171
3174
return REG_ESPACE;
3172
3175
}
3173
3176
break;
3174
3177
}
3175
ok = re_node_set_insert (dst_nodes, cur_node);
3176
if (BE (! ok, 0))
3178
err = re_node_set_insert (dst_nodes, cur_node);
3179
if (BE (err == -1, 0))
3177
3180
return REG_ESPACE;
3178
3181
if (dfa->edests[cur_node].nelem == 0)
3179
3182
break;
3180
3183
if (dfa->edests[cur_node].nelem == 2)
3181
3184
{
3182
reg_errcode_t ret =
3183
check_arrival_expand_ecl_sub (dfa, dst_nodes,
3184
dfa->edests[cur_node].elems[1],
3185
ex_subexp, type);
3186
if (BE (ret != REG_NOERROR, 0))
3187
return ret;
3185
err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3186
dfa->edests[cur_node].elems[1],
3187
ex_subexp, type);
3188
if (BE (err != REG_NOERROR, 0))
3189
return err;
3188
3190
}
3189
3191
cur_node = dfa->edests[cur_node].elems[0];
3190
3192
}
3197
3199
in MCTX->BKREF_ENTS. */
3198
3200
3199
3201
static reg_errcode_t
3200
internal_function
3201
expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3202
Idx cur_str, Idx subexp_num, int type)
3202
expand_bkref_cache (mctx, cur_nodes, cur_str, subexp_num,
3203
type)
3204
re_match_context_t *mctx;
3205
int cur_str, subexp_num, type;
3206
re_node_set *cur_nodes;
3203
3207
{
3204
3208
re_dfa_t *const dfa = mctx->dfa;
3205
3209
reg_errcode_t err;
3206
Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3210
int cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3207
3211
struct re_backref_cache_entry *ent;
3208
3212
3209
if (cache_idx_start == REG_MISSING)
3213
if (cache_idx_start == -1)
3210
3214
return REG_NOERROR;
3211
3215
3212
3216
restart:
3213
3217
ent = mctx->bkref_ents + cache_idx_start;
3214
3218
do
3215
3219
{
3216
Idx to_idx, next_node;
3220
int to_idx, next_node;
3217
3221
3218
3222
/* Is this entry ENT is appropriate? */
3219
3223
if (!re_node_set_contains (cur_nodes, ent->node))
3251
3255
next_node = dfa->nexts[ent->node];
3252
3256
if (mctx->state_log[to_idx])
3253
3257
{
3254
bool ok;
3258
int ret;
3255
3259
if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3256
3260
next_node))
3257
3261
continue;
3258
3262
err = re_node_set_init_copy (&union_set,
3259
3263
&mctx->state_log[to_idx]->nodes);
3260
ok = re_node_set_insert (&union_set, next_node);
3261
if (BE (err != REG_NOERROR || ! ok, 0))
3264
ret = re_node_set_insert (&union_set, next_node);
3265
if (BE (err != REG_NOERROR || ret < 0, 0))
3262
3266
{
3263
3267
re_node_set_free (&union_set);
3264
3268
err = err != REG_NOERROR ? err : REG_ESPACE;
3283
3287
}
3284
3288
3285
3289
/* Build transition table for the state.
3286
Return true if successful. */
3290
Return 1 if succeeded, otherwise return NULL. */
3287
3291
3288
static bool
3289
internal_function
3290
build_trtable (re_dfa_t *dfa, re_dfastate_t *state)
3292
static int
3293
build_trtable (dfa, state)
3294
re_dfa_t *dfa;
3295
re_dfastate_t *state;
3291
3296
{
3292
3297
reg_errcode_t err;
3293
Idx i, j;
3294
int ch;
3295
bool need_word_trtable = false;
3296
bitset_word elem, mask;
3297
bool dests_node_malloced = false, dest_states_malloced = false;
3298
Idx ndests; /* Number of the destination states from `state'. */
3298
int i, j, ch, need_word_trtable = 0;
3299
unsigned int elem, mask;
3300
int dests_node_malloced = 0, dest_states_malloced = 0;
3301
int ndests; /* Number of the destination states from `state'. */
3299
3302
re_dfastate_t **trtable;
3300
3303
re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3301
3304
re_node_set follows, *dests_node;
3302
3305
bitset *dests_ch;
3303
3306
bitset acceptable;
3304
3307
3305
struct dests_alloc
3306
{
3307
re_node_set dests_node[SBC_MAX];
3308
bitset dests_ch[SBC_MAX];
3309
} *dests_alloc;
3310
3311
3308
/* We build DFA states which corresponds to the destination nodes
3312
3309
from `state'. `dests_node[i]' represents the nodes which i-th
3313
3310
destination state contains, and `dests_ch[i]' represents the
3314
3311
characters which i-th destination state accepts. */
3315
if (__libc_use_alloca (sizeof (struct dests_alloc)))
3316
dests_alloc = (struct dests_alloc *) alloca (sizeof dests_alloc[0]);
3312
#ifdef _LIBC
3313
if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX))
3314
dests_node = (re_node_set *)
3315
alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3317
3316
else
3317
#endif
3318
3318
{
3319
dests_alloc = re_malloc (struct dests_alloc, 1);
3320
if (BE (dests_alloc == NULL, 0))
3321
return false;
3322
dests_node_malloced = true;
3319
dests_node = (re_node_set *)
3320
malloc ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3321
if (BE (dests_node == NULL, 0))
3322
return 0;
3323
dests_node_malloced = 1;
3323
3324
}
3324
dests_node = dests_alloc->dests_node;
3325
dests_ch = dests_alloc->dests_ch;
3325
dests_ch = (bitset *) (dests_node + SBC_MAX);
3326
3326
3327
3327
/* Initialize transiton table. */
3328
3328
state->word_trtable = state->trtable = NULL;
3330
3330
/* At first, group all nodes belonging to `state' into several
3331
3331
destinations. */
3332
3332
ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3333
if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3333
if (BE (ndests <= 0, 0))
3334
3334
{
3335
3335
if (dests_node_malloced)
3336
free (dests_alloc);
3336
free (dests_node);
3337
/* Return 0 in case of an error, 1 otherwise. */
3337
3338
if (ndests == 0)
3338
3339
{
3339
state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3340
return true;
3340
state->trtable = (re_dfastate_t **)
3341
calloc (sizeof (re_dfastate_t *), SBC_MAX);
3342
return 1;
3341
3343
}
3342
return false;
3344
return 0;
3343
3345
}
3344
3346
3345
3347
err = re_node_set_alloc (&follows, ndests + 1);
3346
3348
if (BE (err != REG_NOERROR, 0))
3347
3349
goto out_free;
3348
3350
3349
/* Avoid arithmetic overflow in size calculation. */
3350
if (BE (((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX)
3351
/ (3 * sizeof (re_dfastate_t *)))
3352
< ndests, 0))
3353
goto out_free;
3354
3351
#ifdef _LIBC
3355
3352
if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX
3356
3353
+ ndests * 3 * sizeof (re_dfastate_t *)))
3357
3354
dest_states = (re_dfastate_t **)
3358
3355
alloca (ndests * 3 * sizeof (re_dfastate_t *));
3359
3356
else
3357
#endif
3360
3358
{
3361
3359
dest_states = (re_dfastate_t **)
3362
3360
malloc (ndests * 3 * sizeof (re_dfastate_t *));
3369
3367
for (i = 0; i < ndests; ++i)
3370
3368
re_node_set_free (dests_node + i);
3371
3369
if (dests_node_malloced)
3372
free (dests_alloc);
3373
return false;
3370
free (dests_node);
3371
return 0;
3374
3372
}
3375
dest_states_malloced = true;
3373
dest_states_malloced = 1;
3376
3374
}
3377
3375
dest_states_word = dest_states + ndests;
3378
3376
dest_states_nl = dest_states_word + ndests;
3381
3379
/* Then build the states for all destinations. */
3382
3380
for (i = 0; i < ndests; ++i)
3383
3381
{
3384
Idx next_node;
3382
int next_node;
3385
3383
re_node_set_empty (&follows);
3386
3384
/* Merge the follows of this destination states. */
3387
3385
for (j = 0; j < dests_node[i].nelem; ++j)
3388
3386
{
3389
3387
next_node = dfa->nexts[dests_node[i].elems[j]];
3390
if (next_node != REG_MISSING)
3388
if (next_node != -1)
3391
3389
{
3392
3390
err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3393
3391
if (BE (err != REG_NOERROR, 0))
3407
3405
goto out_free;
3408
3406
3409
3407
if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3410
need_word_trtable = true;
3408
need_word_trtable = 1;
3411
3409
3412
3410
dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3413
3411
CONTEXT_NEWLINE);
3428
3426
character, or we are in a single-byte character set so we can
3429
3427
discern by looking at the character code: allocate a
3430
3428
256-entry transition table. */
3431
trtable = state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3429
trtable = state->trtable =
3430
(re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3432
3431
if (BE (trtable == NULL, 0))
3433
3432
goto out_free;
3434
3433
3435
3434
/* For all characters ch...: */
3436
for (i = 0; i < BITSET_WORDS; ++i)
3437
for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3435
for (i = 0; i < BITSET_UINTS; ++i)
3436
for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3438
3437
elem;
3439
3438
mask <<= 1, elem >>= 1, ++ch)
3440
3439
if (BE (elem & 1, 0))
3458
3457
by looking at the character code: build two 256-entry
3459
3458
transition tables, one starting at trtable[0] and one
3460
3459
starting at trtable[SBC_MAX]. */
3461
trtable = state->word_trtable = re_calloc (re_dfastate_t *, 2 * SBC_MAX);
3460
trtable = state->word_trtable =
3461
(re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3462
3462
if (BE (trtable == NULL, 0))
3463
3463
goto out_free;
3464
3464
3465
3465
/* For all characters ch...: */
3466
for (i = 0; i < BITSET_WORDS; ++i)
3467
for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3466
for (i = 0; i < BITSET_UINTS; ++i)
3467
for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3468
3468
elem;
3469
3469
mask <<= 1, elem >>= 1, ++ch)
3470
3470
if (BE (elem & 1, 0))
3505
3505
re_node_set_free (dests_node + i);
3506
3506
3507
3507
if (dests_node_malloced)
3508
free (dests_alloc);
3508
free (dests_node);
3509
3509
3510
return true;
3510
return 1;
3511
3511
}
3512
3512
3513
3513
/* Group all nodes belonging to STATE into several destinations.
3515
3515
to DESTS_NODE[i] and set the characters accepted by the destination
3516
3516
to DEST_CH[i]. This function return the number of destinations. */
3517
3517
3518
static Idx
3519
internal_function
3520
group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3521
re_node_set *dests_node, bitset *dests_ch)
3518
static int
3519
group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch)
3520
re_dfa_t *dfa;
3521
const re_dfastate_t *state;
3522
re_node_set *dests_node;
3523
bitset *dests_ch;
3522
3524
{
3523
3525
reg_errcode_t err;
3524
bool ok;
3525
Idx i, j, k;
3526
Idx ndests; /* Number of the destinations from `state'. */
3526
int result;
3527
int i, j, k;
3528
int ndests; /* Number of the destinations from `state'. */
3527
3529
bitset accepts; /* Characters a node can accept. */
3528
3530
const re_node_set *cur_nodes = &state->nodes;
3529
3531
bitset_empty (accepts);
3551
3553
else
3552
3554
#endif
3553
3555
bitset_set_all (accepts);
3554
if (!(dfa->syntax & REG_DOT_NEWLINE))
3556
if (!(dfa->syntax & RE_DOT_NEWLINE))
3555
3557
bitset_clear (accepts, '\n');
3556
if (dfa->syntax & REG_DOT_NOT_NULL)
3558
if (dfa->syntax & RE_DOT_NOT_NULL)
3557
3559
bitset_clear (accepts, '\0');
3558
3560
}
3559
3561
#ifdef RE_ENABLE_I18N
3560
3562
else if (type == OP_UTF8_PERIOD)
3561
3563
{
3562
if (SBC_MAX / 2 % BITSET_WORD_BITS == 0)
3563
memset (accepts, -1, sizeof accepts / 2);
3564
else
3565
bitset_merge (accepts, utf8_sb_map);
3566
if (!(dfa->syntax & REG_DOT_NEWLINE))
3564
memset (accepts, 255, sizeof (unsigned int) * BITSET_UINTS / 2);
3565
if (!(dfa->syntax & RE_DOT_NEWLINE))
3567
3566
bitset_clear (accepts, '\n');
3568
if (dfa->syntax & REG_DOT_NOT_NULL)
3567
if (dfa->syntax & RE_DOT_NOT_NULL)
3569
3568
bitset_clear (accepts, '\0');
3570
3569
}
3571
3570
#endif
3578
3577
{
3579
3578
if (constraint & NEXT_NEWLINE_CONSTRAINT)
3580
3579
{
3581
bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3580
int accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3582
3581
bitset_empty (accepts);
3583
3582
if (accepts_newline)
3584
3583
bitset_set (accepts, NEWLINE_CHAR);
3593
3592
3594
3593
if (constraint & NEXT_WORD_CONSTRAINT)
3595
3594
{
3596
bitset_word any_set = 0;
3595
unsigned int any_set = 0;
3597
3596
if (type == CHARACTER && !node->word_char)
3598
3597
{
3599
3598
bitset_empty (accepts);
3601
3600
}
3602
3601
#ifdef RE_ENABLE_I18N
3603
3602
if (dfa->mb_cur_max > 1)
3604
for (j = 0; j < BITSET_WORDS; ++j)
3603
for (j = 0; j < BITSET_UINTS; ++j)
3605
3604
any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3606
3605
else
3607
3606
#endif
3608
for (j = 0; j < BITSET_WORDS; ++j)
3607
for (j = 0; j < BITSET_UINTS; ++j)
3609
3608
any_set |= (accepts[j] &= dfa->word_char[j]);
3610
3609
if (!any_set)
3611
3610
continue;
3612
3611
}
3613
3612
if (constraint & NEXT_NOTWORD_CONSTRAINT)
3614
3613
{
3615
bitset_word any_set = 0;
3614
unsigned int any_set = 0;
3616
3615
if (type == CHARACTER && node->word_char)
3617
3616
{
3618
3617
bitset_empty (accepts);
3620
3619
}
3621
3620
#ifdef RE_ENABLE_I18N
3622
3621
if (dfa->mb_cur_max > 1)
3623
for (j = 0; j < BITSET_WORDS; ++j)
3622
for (j = 0; j < BITSET_UINTS; ++j)
3624
3623
any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3625
3624
else
3626
3625
#endif
3627
for (j = 0; j < BITSET_WORDS; ++j)
3626
for (j = 0; j < BITSET_UINTS; ++j)
3628
3627
any_set |= (accepts[j] &= ~dfa->word_char[j]);
3629
3628
if (!any_set)
3630
3629
continue;
3638
3637
bitset intersec; /* Intersection sets, see below. */
3639
3638
bitset remains;
3640
3639
/* Flags, see below. */
3641
bitset_word has_intersec, not_subset, not_consumed;
3640
int has_intersec, not_subset, not_consumed;
3642
3641
3643
3642
/* Optimization, skip if this state doesn't accept the character. */
3644
3643
if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3646
3645
3647
3646
/* Enumerate the intersection set of this state and `accepts'. */
3648
3647
has_intersec = 0;
3649
for (k = 0; k < BITSET_WORDS; ++k)
3648
for (k = 0; k < BITSET_UINTS; ++k)
3650
3649
has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3651
3650
/* And skip if the intersection set is empty. */
3652
3651
if (!has_intersec)
3654
3653
3655
3654
/* Then check if this state is a subset of `accepts'. */
3656
3655
not_subset = not_consumed = 0;
3657
for (k = 0; k < BITSET_WORDS; ++k)
3656
for (k = 0; k < BITSET_UINTS; ++k)
3658
3657
{
3659
3658
not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3660
3659
not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3673
3672
}
3674
3673
3675
3674
/* Put the position in the current group. */
3676
ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3677
if (BE (! ok, 0))
3675
result = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3676
if (BE (result < 0, 0))
3678
3677
goto error_return;
3679
3678
3680
3679
/* If all characters are consumed, go to next node. */
3696
3695
error_return:
3697
3696
for (j = 0; j < ndests; ++j)
3698
3697
re_node_set_free (dests_node + j);
3699
return REG_MISSING;
3698
return -1;
3700
3699
}
3701
3700
3702
3701
#ifdef RE_ENABLE_I18N
3709
3708
can only accept one byte. */
3710
3709
3711
3710
static int
3712
internal_function
3713
check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
3714
const re_string_t *input, Idx str_idx)
3711
check_node_accept_bytes (dfa, node_idx, input, str_idx)
3712
re_dfa_t *dfa;
3713
int node_idx, str_idx;
3714
const re_string_t *input;
3715
3715
{
3716
3716
const re_token_t *node = dfa->nodes + node_idx;
3717
3717
int char_len, elem_len;
3718
Idx i;
3718
int i;
3719
3719
3720
3720
if (BE (node->type == OP_UTF8_PERIOD, 0))
3721
3721
{
3776
3776
/* FIXME: I don't think this if is needed, as both '\n'
3777
3777
and '\0' are char_len == 1. */
3778
3778
/* '.' accepts any one character except the following two cases. */
3779
if ((!(dfa->syntax & REG_DOT_NEWLINE) &&
3779
if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3780
3780
re_string_byte_at (input, str_idx) == '\n') ||
3781
((dfa->syntax & REG_DOT_NOT_NULL) &&
3781
((dfa->syntax & RE_DOT_NOT_NULL) &&
3782
3782
re_string_byte_at (input, str_idx) == '\0'))
3783
3783
return 0;
3784
3784
return char_len;
3794
3794
# ifdef _LIBC
3795
3795
const unsigned char *pin
3796
3796
= ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3797
Idx j;
3797
int j;
3798
3798
uint32_t nrules;
3799
3799
# endif /* _LIBC */
3800
3800
int match_len = 0;
3893
3893
size_t weight_len = weights[idx];
3894
3894
if (weight_len == weights[equiv_class_idx])
3895
3895
{
3896
Idx cnt = 0;
3896
int cnt = 0;
3897
3897
while (cnt <= weight_len
3898
3898
&& (weights[equiv_class_idx + 1 + cnt]
3899
3899
== weights[idx + 1 + cnt]))
3945
3945
3946
3946
# ifdef _LIBC
3947
3947
static unsigned int
3948
find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
3948
find_collation_sequence_value (mbs, mbs_len)
3949
const unsigned char *mbs;
3950
size_t mbs_len;
3949
3951
{
3950
3952
uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3951
3953
if (nrules == 0)
3969
3971
3970
3972
for (idx = 0; idx < extrasize;)
3971
3973
{
3972
int mbs_cnt;
3973
bool found = false;
3974
int mbs_cnt, found = 0;
3974
3975
int32_t elem_mbs_len;
3975
3976
/* Skip the name of collating element name. */
3976
3977
idx = idx + extra[idx] + 1;
3982
3983
break;
3983
3984
if (mbs_cnt == elem_mbs_len)
3984
3985
/* Found the entry. */
3985
found = true;
3986
found = 1;
3986
3987
}
3987
3988
/* Skip the byte sequence of the collating element. */
3988
3989
idx += elem_mbs_len;
4007
4008
/* Check whether the node accepts the byte which is IDX-th
4008
4009
byte of the INPUT. */
4009
4010
4010
static bool
4011
internal_function
4012
check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4013
Idx idx)
4011
static int
4012
check_node_accept (mctx, node, idx)
4013
const re_match_context_t *mctx;
4014
const re_token_t *node;
4015
int idx;
4014
4016
{
4015
4017
unsigned char ch;
4016
4018
ch = re_string_byte_at (&mctx->input, idx);
4018
4020
{
4019
4021
case CHARACTER:
4020
4022
if (node->opr.c != ch)
4021
return false;
4023
return 0;
4022
4024
break;
4023
4025
4024
4026
case SIMPLE_BRACKET:
4025
4027
if (!bitset_contain (node->opr.sbcset, ch))
4026
return false;
4028
return 0;
4027
4029
break;
4028
4030
4029
4031
#ifdef RE_ENABLE_I18N
4030
4032
case OP_UTF8_PERIOD:
4031
4033
if (ch >= 0x80)
4032
return false;
4034
return 0;
4033
4035
/* FALLTHROUGH */
4034
4036
#endif
4035
4037
case OP_PERIOD:
4036
if ((ch == '\n' && !(mctx->dfa->syntax & REG_DOT_NEWLINE))
4037
|| (ch == '\0' && (mctx->dfa->syntax & REG_DOT_NOT_NULL)))
4038
return false;
4038
if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4039
|| (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4040
return 0;
4039
4041
break;
4040
4042
4041
4043
default:
4042
return false;
4044
return 0;
4043
4045
}
4044
4046
4045
4047
if (node->constraint)
4049
4051
unsigned int context = re_string_context_at (&mctx->input, idx,
4050
4052
mctx->eflags);
4051
4053
if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4052
return false;
4054
return 0;
4053
4055
}
4054
4056
4055
return true;
4057
return 1;
4056
4058
}
4057
4059
4058
4060
/* Extend the buffers, if the buffers have run out. */
4059
4061
4060
4062
static reg_errcode_t
4061
internal_function
4062
extend_buffers (re_match_context_t *mctx)
4063
extend_buffers (mctx)
4064
re_match_context_t *mctx;
4063
4065
{
4064
4066
reg_errcode_t ret;
4065
4067
re_string_t *pstr = &mctx->input;
4075
4077
/* XXX We have no indication of the size of this buffer. If this
4076
4078
allocation fail we have no indication that the state_log array
4077
4079
does not have the right size. */
4078
re_dfastate_t **new_array = re_xrealloc (mctx->state_log, re_dfastate_t *,
4079
pstr->bufs_len + 1);
4080
re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4081
pstr->bufs_len + 1);
4080
4082
if (BE (new_array == NULL, 0))
4081
4083
return REG_ESPACE;
4082
4084
mctx->state_log = new_array;
4117
4119
/* Initialize MCTX. */
4118
4120
4119
4121
static reg_errcode_t
4120
internal_function
4121
match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4122
match_ctx_init (mctx, eflags, n)
4123
re_match_context_t *mctx;
4124
int eflags, n;
4122
4125
{
4123
4126
mctx->eflags = eflags;
4124
mctx->match_last = REG_MISSING;
4127
mctx->match_last = -1;
4125
4128
if (n > 0)
4126
4129
{
4127
mctx->bkref_ents = re_xmalloc (struct re_backref_cache_entry, n);
4128
mctx->sub_tops = re_xmalloc (re_sub_match_top_t *, n);
4130
mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4131
mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4129
4132
if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4130
4133
return REG_ESPACE;
4131
4134
}
4145
4148
of the input, or changes the input string. */
4146
4149
4147
4150
static void
4148
internal_function
4149
match_ctx_clean (re_match_context_t *mctx)
4151
match_ctx_clean (mctx)
4152
re_match_context_t *mctx;
4150
4153
{
4151
Idx st_idx;
4154
int st_idx;
4152
4155
for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4153
4156
{
4154
Idx sl_idx;
4157
int sl_idx;
4155
4158
re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4156
4159
for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4157
4160
{
4175
4178
/* Free all the memory associated with MCTX. */
4176
4179
4177
4180
static void
4178
internal_function
4179
match_ctx_free (re_match_context_t *mctx)
4181
match_ctx_free (mctx)
4182
re_match_context_t *mctx;
4180
4183
{
4181
4184
/* First, free all the memory associated with MCTX->SUB_TOPS. */
4182
4185
match_ctx_clean (mctx);
4190
4193
*/
4191
4194
4192
4195
static reg_errcode_t
4193
internal_function
4194
match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx,
4195
Idx from, Idx to)
4196
match_ctx_add_entry (mctx, node, str_idx, from, to)
4197
re_match_context_t *mctx;
4198
int node, str_idx, from, to;
4196
4199
{
4197
4200
if (mctx->nbkref_ents >= mctx->abkref_ents)
4198
4201
{
4199
4202
struct re_backref_cache_entry* new_entry;
4200
new_entry = re_x2realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4201
&mctx->abkref_ents);
4203
new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4204
mctx->abkref_ents * 2);
4202
4205
if (BE (new_entry == NULL, 0))
4203
4206
{
4204
4207
re_free (mctx->bkref_ents);
4206
4209
}
4207
4210
mctx->bkref_ents = new_entry;
4208
4211
memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4209
(sizeof (struct re_backref_cache_entry)
4210
* (mctx->abkref_ents - mctx->nbkref_ents)));
4212
sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4213
mctx->abkref_ents *= 2;
4211
4214
}
4212
4215
if (mctx->nbkref_ents > 0
4213
4216
&& mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4227
4230
A backreference does not epsilon-transition unless it is empty, so set
4228
4231
to all zeros if FROM != TO. */
4229
4232
mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4230
= (from == to ? -1 : 0);
4233
= (from == to ? ~0 : 0);
4231
4234
4232
4235
mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4233
4236
if (mctx->max_mb_elem_len < to - from)
4235
4238
return REG_NOERROR;
4236
4239
}
4237
4240
4238
/* Return the first entry with the same str_idx, or REG_MISSING if none is
4241
/* Search for the first entry which has the same str_idx, or -1 if none is
4239
4242
found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4240
4243
4241
static Idx
4242
internal_function
4243
search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4244
static int
4245
search_cur_bkref_entry (mctx, str_idx)
4246
re_match_context_t *mctx;
4247
int str_idx;
4244
4248
{
4245
Idx left, right, mid, last;
4249
int left, right, mid, last;
4246
4250
last = right = mctx->nbkref_ents;
4247
4251
for (left = 0; left < right;)
4248
4252
{
4255
4259
if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4256
4260
return left;
4257
4261
else
4258
return REG_MISSING;
4262
return -1;
4259
4263
}
4260
4264
4261
4265
/* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4262
4266
at STR_IDX. */
4263
4267
4264
4268
static reg_errcode_t
4265
internal_function
4266
match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4269
match_ctx_add_subtop (mctx, node, str_idx)
4270
re_match_context_t *mctx;
4271
int node, str_idx;
4267
4272
{
4268
4273
#ifdef DEBUG
4269
4274
assert (mctx->sub_tops != NULL);
4271
4276
#endif
4272
4277
if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4273
4278
{
4274
Idx new_asub_tops = mctx->asub_tops;
4275
re_sub_match_top_t **new_array = re_x2realloc (mctx->sub_tops,
4276
re_sub_match_top_t *,
4277
&new_asub_tops);
4279
int new_asub_tops = mctx->asub_tops * 2;
4280
re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4281
re_sub_match_top_t *,
4282
new_asub_tops);
4278
4283
if (BE (new_array == NULL, 0))
4279
4284
return REG_ESPACE;
4280
4285
mctx->sub_tops = new_array;
4281
4286
mctx->asub_tops = new_asub_tops;
4282
4287
}
4283
mctx->sub_tops[mctx->nsub_tops] = re_calloc (re_sub_match_top_t, 1);
4288
mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4284
4289
if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4285
4290
return REG_ESPACE;
4286
4291
mctx->sub_tops[mctx->nsub_tops]->node = node;
4292
4297
at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4293
4298
4294
4299
static re_sub_match_last_t *
4295
internal_function
4296
match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4300
match_ctx_add_sublast (subtop, node, str_idx)
4301
re_sub_match_top_t *subtop;
4302
int node, str_idx;
4297
4303
{
4298
4304
re_sub_match_last_t *new_entry;
4299
4305
if (BE (subtop->nlasts == subtop->alasts, 0))
4300
4306
{
4301
Idx new_alasts = subtop->alasts;
4302
re_sub_match_last_t **new_array = re_x2realloc (subtop->lasts,
4303
re_sub_match_last_t *,
4304
&new_alasts);
4307
int new_alasts = 2 * subtop->alasts + 1;
4308
re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4309
re_sub_match_last_t *,
4310
new_alasts);
4305
4311
if (BE (new_array == NULL, 0))
4306
4312
return NULL;
4307
4313
subtop->lasts = new_array;
4308
4314
subtop->alasts = new_alasts;
4309
4315
}
4310
new_entry = re_calloc (re_sub_match_last_t, 1);
4316
new_entry = calloc (1, sizeof (re_sub_match_last_t));
4311
4317
if (BE (new_entry != NULL, 1))
4312
4318
{
4313
4319
subtop->lasts[subtop->nlasts] = new_entry;
4319
4325
}
4320
4326
4321
4327
static void
4322
internal_function
4323
sift_ctx_init (re_sift_context_t *sctx,
4324
re_dfastate_t **sifted_sts,
4325
re_dfastate_t **limited_sts,
4326
Idx last_node, Idx last_str_idx)
4328
sift_ctx_init (sctx, sifted_sts, limited_sts, last_node, last_str_idx)
4329
re_sift_context_t *sctx;
4330
re_dfastate_t **sifted_sts, **limited_sts;
4331
int last_node, last_str_idx;
4327
4332
{
4328
4333
sctx->sifted_states = sifted_sts;
4329
4334
sctx->limited_states = limited_sts;
Loggerhead is a web-based interface for Breezy
Version: 2.0.1