« back to all changes in this revision
Viewing changes to support/regex_internal.h
- browse files at revision 731.3.11
- compare with another revision
- download diff
- download tarball
- view history from revision 731.3.11
- Committer: Arnold D. Robbins
- Date: 2016-12-22 15:23:16 UTC
- mfrom: (731.1.11)
- mto: (731.14.2) (1056.1.1)
- mto: This revision was merged to the branch mainline in revision 742.
- Revision ID: git-v1:293b5a86a9053668773e75b35682c41ca64e0db6
Merge branch 'master' into feature/andy
added
removed
support/regex_internal.h
1
/* Extended regular expression matching and search library.
2
Copyright (C) 2002-2016 Free Software Foundation, Inc.
3
This file is part of the GNU C Library.
4
Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5
6
The GNU C Library is free software; you can redistribute it and/or
7
modify it under the terms of the GNU Lesser General Public
8
License as published by the Free Software Foundation; either
9
version 2.1 of the License, or (at your option) any later version.
10
11
The GNU C Library is distributed in the hope that it will be useful,
12
but WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14
Lesser General Public License for more details.
15
16
You should have received a copy of the GNU Lesser General Public
17
License along with the GNU C Library; if not, see
18
<http://www.gnu.org/licenses/>. */
19
20
#ifndef _REGEX_INTERNAL_H
21
#define _REGEX_INTERNAL_H 1
22
23
#include <assert.h>
24
#include <ctype.h>
25
#include <stdio.h>
26
#include <stdlib.h>
27
#include <string.h>
28
29
#if defined HAVE_LANGINFO_H || defined HAVE_LANGINFO_CODESET || defined _LIBC
30
# include <langinfo.h>
31
#endif
32
#if defined HAVE_LOCALE_H || defined _LIBC
33
# include <locale.h>
34
#endif
35
#if defined HAVE_WCHAR_H || defined _LIBC
36
# include <wchar.h>
37
#endif /* HAVE_WCHAR_H || _LIBC */
38
#if defined HAVE_WCTYPE_H || defined _LIBC
39
# include <wctype.h>
40
#endif /* HAVE_WCTYPE_H || _LIBC */
41
#if defined HAVE_STDBOOL_H || defined _LIBC
42
# include <stdbool.h>
43
#endif /* HAVE_STDBOOL_H || _LIBC */
44
#if defined HAVE_STDINT_H || defined _LIBC
45
# include <stdint.h>
46
#endif /* HAVE_STDINT_H || _LIBC */
47
48
#include "intprops.h"
49
50
#if defined _LIBC
51
# include <libc-lock.h>
52
#else
53
# define __libc_lock_define(CLASS,NAME)
54
# define __libc_lock_init(NAME) do { } while (0)
55
# define __libc_lock_lock(NAME) do { } while (0)
56
# define __libc_lock_unlock(NAME) do { } while (0)
57
#endif
58
59
#ifndef GAWK
60
/* In case that the system doesn't have isblank(). */
61
#if !defined _LIBC && !defined HAVE_ISBLANK && !defined isblank
62
# define isblank(ch) ((ch) == ' ' || (ch) == '\t')
63
#endif
64
#else /* GAWK */
65
/*
66
* This is a freaking mess. On glibc systems you have to define
67
* a magic constant to get isblank() out of <ctype.h>, since it's
68
* a C99 function. To heck with all that and borrow a page from
69
* dfa.c's book.
70
*/
71
72
static int
73
is_blank (int c)
74
{
75
return (c == ' ' || c == '\t');
76
}
77
#endif /* GAWK */
78
79
#ifdef _LIBC
80
# ifndef _RE_DEFINE_LOCALE_FUNCTIONS
81
# define _RE_DEFINE_LOCALE_FUNCTIONS 1
82
# include <locale/localeinfo.h>
83
# include <locale/coll-lookup.h>
84
# endif
85
#endif
86
87
/* This is for other GNU distributions with internationalized messages. */
88
#if (HAVE_LIBINTL_H && ENABLE_NLS) || defined _LIBC
89
# include <libintl.h>
90
# ifdef _LIBC
91
# undef gettext
92
# define gettext(msgid) \
93
__dcgettext (_libc_intl_domainname, msgid, LC_MESSAGES)
94
# endif
95
#else
96
# define gettext(msgid) (msgid)
97
#endif
98
99
#ifndef gettext_noop
100
/* This define is so xgettext can find the internationalizable
101
strings. */
102
# define gettext_noop(String) String
103
#endif
104
105
/* For loser systems without the definition. */
106
#ifndef SIZE_MAX
107
# define SIZE_MAX ((size_t) -1)
108
#endif
109
110
#if ! defined(__DJGPP__) && (defined(GAWK) || _LIBC)
111
# define RE_ENABLE_I18N
112
#endif
113
114
#if __GNUC__ >= 3
115
# define BE(expr, val) __builtin_expect (expr, val)
116
#else
117
# define BE(expr, val) (expr)
118
# ifdef inline
119
# undef inline
120
# endif
121
# define inline
122
#endif
123
124
/* Number of single byte character. */
125
#define SBC_MAX 256
126
127
#define COLL_ELEM_LEN_MAX 8
128
129
/* The character which represents newline. */
130
#define NEWLINE_CHAR '\n'
131
#define WIDE_NEWLINE_CHAR L'\n'
132
133
/* Rename to standard API for using out of glibc. */
134
#ifndef _LIBC
135
# ifdef __wctype
136
# undef __wctype
137
# endif
138
# define __wctype wctype
139
# ifdef __iswctype
140
# undef __iswctype
141
# endif
142
# define __iswctype iswctype
143
# define __btowc btowc
144
# define __mbrtowc mbrtowc
145
#undef __mempcpy /* GAWK */
146
# define __mempcpy mempcpy
147
# define __wcrtomb wcrtomb
148
# define __regfree regfree
149
#endif /* not _LIBC */
150
151
#if __GNUC__ < 3 + (__GNUC_MINOR__ < 1)
152
# define __attribute__(arg)
153
#endif
154
155
#ifdef GAWK
156
/*
157
* Instead of trying to figure out which GCC version introduced
158
* this symbol, just define it out and be done.
159
*/
160
# undef __attribute_warn_unused_result__
161
# define __attribute_warn_unused_result__
162
#endif
163
164
/* An integer used to represent a set of bits. It must be unsigned,
165
and must be at least as wide as unsigned int. */
166
typedef unsigned long int bitset_word_t;
167
/* All bits set in a bitset_word_t. */
168
#define BITSET_WORD_MAX ULONG_MAX
169
/* Number of bits in a bitset_word_t. */
170
#define BITSET_WORD_BITS (sizeof (bitset_word_t) * CHAR_BIT)
171
/* Number of bitset_word_t in a bit_set. */
172
#define BITSET_WORDS (SBC_MAX / BITSET_WORD_BITS)
173
typedef bitset_word_t bitset_t[BITSET_WORDS];
174
typedef bitset_word_t *re_bitset_ptr_t;
175
typedef const bitset_word_t *re_const_bitset_ptr_t;
176
177
#define bitset_set(set,i) \
178
(set[i / BITSET_WORD_BITS] |= (bitset_word_t) 1 << i % BITSET_WORD_BITS)
179
#define bitset_clear(set,i) \
180
(set[i / BITSET_WORD_BITS] &= ~((bitset_word_t) 1 << i % BITSET_WORD_BITS))
181
#define bitset_contain(set,i) \
182
(set[i / BITSET_WORD_BITS] & ((bitset_word_t) 1 << i % BITSET_WORD_BITS))
183
#define bitset_empty(set) memset (set, '\0', sizeof (bitset_t))
184
#define bitset_set_all(set) memset (set, '\xff', sizeof (bitset_t))
185
#define bitset_copy(dest,src) memcpy (dest, src, sizeof (bitset_t))
186
187
#define PREV_WORD_CONSTRAINT 0x0001
188
#define PREV_NOTWORD_CONSTRAINT 0x0002
189
#define NEXT_WORD_CONSTRAINT 0x0004
190
#define NEXT_NOTWORD_CONSTRAINT 0x0008
191
#define PREV_NEWLINE_CONSTRAINT 0x0010
192
#define NEXT_NEWLINE_CONSTRAINT 0x0020
193
#define PREV_BEGBUF_CONSTRAINT 0x0040
194
#define NEXT_ENDBUF_CONSTRAINT 0x0080
195
#define WORD_DELIM_CONSTRAINT 0x0100
196
#define NOT_WORD_DELIM_CONSTRAINT 0x0200
197
198
typedef enum
199
{
200
INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
201
WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
202
WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
203
INSIDE_NOTWORD = PREV_NOTWORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
204
LINE_FIRST = PREV_NEWLINE_CONSTRAINT,
205
LINE_LAST = NEXT_NEWLINE_CONSTRAINT,
206
BUF_FIRST = PREV_BEGBUF_CONSTRAINT,
207
BUF_LAST = NEXT_ENDBUF_CONSTRAINT,
208
WORD_DELIM = WORD_DELIM_CONSTRAINT,
209
NOT_WORD_DELIM = NOT_WORD_DELIM_CONSTRAINT
210
} re_context_type;
211
212
typedef struct
213
{
214
int alloc;
215
int nelem;
216
int *elems;
217
} re_node_set;
218
219
typedef enum
220
{
221
NON_TYPE = 0,
222
223
/* Node type, These are used by token, node, tree. */
224
CHARACTER = 1,
225
END_OF_RE = 2,
226
SIMPLE_BRACKET = 3,
227
OP_BACK_REF = 4,
228
OP_PERIOD = 5,
229
#ifdef RE_ENABLE_I18N
230
COMPLEX_BRACKET = 6,
231
OP_UTF8_PERIOD = 7,
232
#endif /* RE_ENABLE_I18N */
233
234
/* We define EPSILON_BIT as a macro so that OP_OPEN_SUBEXP is used
235
when the debugger shows values of this enum type. */
236
#define EPSILON_BIT 8
237
OP_OPEN_SUBEXP = EPSILON_BIT | 0,
238
OP_CLOSE_SUBEXP = EPSILON_BIT | 1,
239
OP_ALT = EPSILON_BIT | 2,
240
OP_DUP_ASTERISK = EPSILON_BIT | 3,
241
ANCHOR = EPSILON_BIT | 4,
242
243
/* Tree type, these are used only by tree. */
244
CONCAT = 16,
245
SUBEXP = 17,
246
247
/* Token type, these are used only by token. */
248
OP_DUP_PLUS = 18,
249
OP_DUP_QUESTION,
250
OP_OPEN_BRACKET,
251
OP_CLOSE_BRACKET,
252
OP_CHARSET_RANGE,
253
OP_OPEN_DUP_NUM,
254
OP_CLOSE_DUP_NUM,
255
OP_NON_MATCH_LIST,
256
OP_OPEN_COLL_ELEM,
257
OP_CLOSE_COLL_ELEM,
258
OP_OPEN_EQUIV_CLASS,
259
OP_CLOSE_EQUIV_CLASS,
260
OP_OPEN_CHAR_CLASS,
261
OP_CLOSE_CHAR_CLASS,
262
OP_WORD,
263
OP_NOTWORD,
264
OP_SPACE,
265
OP_NOTSPACE,
266
BACK_SLASH
267
268
} re_token_type_t;
269
270
#ifdef RE_ENABLE_I18N
271
typedef struct
272
{
273
/* Multibyte characters. */
274
wchar_t *mbchars;
275
276
/* Collating symbols. */
277
# ifdef _LIBC
278
int32_t *coll_syms;
279
# endif
280
281
/* Equivalence classes. */
282
# ifdef _LIBC
283
int32_t *equiv_classes;
284
# endif
285
286
/* Range expressions. */
287
# ifdef _LIBC
288
uint32_t *range_starts;
289
uint32_t *range_ends;
290
# else /* not _LIBC */
291
wchar_t *range_starts;
292
wchar_t *range_ends;
293
# endif /* not _LIBC */
294
295
/* Character classes. */
296
wctype_t *char_classes;
297
298
/* If this character set is the non-matching list. */
299
unsigned int non_match : 1;
300
301
/* # of multibyte characters. */
302
int nmbchars;
303
304
/* # of collating symbols. */
305
int ncoll_syms;
306
307
/* # of equivalence classes. */
308
int nequiv_classes;
309
310
/* # of range expressions. */
311
int nranges;
312
313
/* # of character classes. */
314
int nchar_classes;
315
} re_charset_t;
316
#endif /* RE_ENABLE_I18N */
317
318
typedef struct
319
{
320
union
321
{
322
unsigned char c; /* for CHARACTER */
323
re_bitset_ptr_t sbcset; /* for SIMPLE_BRACKET */
324
#ifdef RE_ENABLE_I18N
325
re_charset_t *mbcset; /* for COMPLEX_BRACKET */
326
#endif /* RE_ENABLE_I18N */
327
int idx; /* for BACK_REF */
328
re_context_type ctx_type; /* for ANCHOR */
329
} opr;
330
#if __GNUC__ >= 2
331
re_token_type_t type : 8;
332
#else
333
re_token_type_t type;
334
#endif
335
unsigned int constraint : 10; /* context constraint */
336
unsigned int duplicated : 1;
337
unsigned int opt_subexp : 1;
338
#ifdef RE_ENABLE_I18N
339
unsigned int accept_mb : 1;
340
/* These 2 bits can be moved into the union if needed (e.g. if running out
341
of bits; move opr.c to opr.c.c and move the flags to opr.c.flags). */
342
unsigned int mb_partial : 1;
343
#endif
344
unsigned int word_char : 1;
345
} re_token_t;
346
347
#define IS_EPSILON_NODE(type) ((type) & EPSILON_BIT)
348
349
struct re_string_t
350
{
351
/* Indicate the raw buffer which is the original string passed as an
352
argument of regexec(), re_search(), etc.. */
353
const unsigned char *raw_mbs;
354
/* Store the multibyte string. In case of "case insensitive mode" like
355
REG_ICASE, upper cases of the string are stored, otherwise MBS points
356
the same address that RAW_MBS points. */
357
unsigned char *mbs;
358
#ifdef RE_ENABLE_I18N
359
/* Store the wide character string which is corresponding to MBS. */
360
wint_t *wcs;
361
int *offsets;
362
mbstate_t cur_state;
363
#endif
364
/* Index in RAW_MBS. Each character mbs[i] corresponds to
365
raw_mbs[raw_mbs_idx + i]. */
366
int raw_mbs_idx;
367
/* The length of the valid characters in the buffers. */
368
int valid_len;
369
/* The corresponding number of bytes in raw_mbs array. */
370
int valid_raw_len;
371
/* The length of the buffers MBS and WCS. */
372
int bufs_len;
373
/* The index in MBS, which is updated by re_string_fetch_byte. */
374
int cur_idx;
375
/* length of RAW_MBS array. */
376
int raw_len;
377
/* This is RAW_LEN - RAW_MBS_IDX + VALID_LEN - VALID_RAW_LEN. */
378
int len;
379
/* End of the buffer may be shorter than its length in the cases such
380
as re_match_2, re_search_2. Then, we use STOP for end of the buffer
381
instead of LEN. */
382
int raw_stop;
383
/* This is RAW_STOP - RAW_MBS_IDX adjusted through OFFSETS. */
384
int stop;
385
386
/* The context of mbs[0]. We store the context independently, since
387
the context of mbs[0] may be different from raw_mbs[0], which is
388
the beginning of the input string. */
389
unsigned int tip_context;
390
/* The translation passed as a part of an argument of re_compile_pattern. */
391
RE_TRANSLATE_TYPE trans;
392
/* Copy of re_dfa_t's word_char. */
393
re_const_bitset_ptr_t word_char;
394
/* 1 if REG_ICASE. */
395
unsigned char icase;
396
unsigned char is_utf8;
397
unsigned char map_notascii;
398
unsigned char mbs_allocated;
399
unsigned char offsets_needed;
400
unsigned char newline_anchor;
401
unsigned char word_ops_used;
402
int mb_cur_max;
403
};
404
typedef struct re_string_t re_string_t;
405
406
407
struct re_dfa_t;
408
typedef struct re_dfa_t re_dfa_t;
409
410
#ifndef _LIBC
411
# ifdef __i386__
412
# define internal_function __attribute__ ((regparm (3), stdcall))
413
# else
414
# define internal_function
415
# endif
416
#endif
417
418
#ifndef NOT_IN_libc
419
static reg_errcode_t re_string_realloc_buffers (re_string_t *pstr,
420
int new_buf_len)
421
internal_function;
422
# ifdef RE_ENABLE_I18N
423
static void build_wcs_buffer (re_string_t *pstr) internal_function;
424
static reg_errcode_t build_wcs_upper_buffer (re_string_t *pstr)
425
internal_function;
426
# endif /* RE_ENABLE_I18N */
427
static void build_upper_buffer (re_string_t *pstr) internal_function;
428
static void re_string_translate_buffer (re_string_t *pstr) internal_function;
429
static unsigned int re_string_context_at (const re_string_t *input, int idx,
430
int eflags)
431
internal_function __attribute__ ((pure));
432
#endif
433
#define re_string_peek_byte(pstr, offset) \
434
((pstr)->mbs[(pstr)->cur_idx + offset])
435
#define re_string_fetch_byte(pstr) \
436
((pstr)->mbs[(pstr)->cur_idx++])
437
#define re_string_first_byte(pstr, idx) \
438
((idx) == (pstr)->valid_len || (pstr)->wcs[idx] != WEOF)
439
#define re_string_is_single_byte_char(pstr, idx) \
440
((pstr)->wcs[idx] != WEOF && ((pstr)->valid_len == (idx) + 1 \
441
|| (pstr)->wcs[(idx) + 1] != WEOF))
442
#define re_string_eoi(pstr) ((pstr)->stop <= (pstr)->cur_idx)
443
#define re_string_cur_idx(pstr) ((pstr)->cur_idx)
444
#define re_string_get_buffer(pstr) ((pstr)->mbs)
445
#define re_string_length(pstr) ((pstr)->len)
446
#define re_string_byte_at(pstr,idx) ((pstr)->mbs[idx])
447
#define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
448
#define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
449
450
#ifndef _LIBC
451
# if HAVE_ALLOCA
452
# include <alloca.h>
453
/* The OS usually guarantees only one guard page at the bottom of the stack,
454
and a page size can be as small as 4096 bytes. So we cannot safely
455
allocate anything larger than 4096 bytes. Also care for the possibility
456
of a few compiler-allocated temporary stack slots. */
457
# define __libc_use_alloca(n) ((n) < 4032)
458
# else
459
/* alloca is implemented with malloc, so just use malloc. */
460
# define __libc_use_alloca(n) 0
461
# endif
462
#endif
463
464
/*
465
* GAWK checks for zero-size allocations everywhere else,
466
* do it here too.
467
*/
468
#ifndef GAWK
469
#define re_malloc(t,n) ((t *) malloc ((n) * sizeof (t)))
470
#define re_realloc(p,t,n) ((t *) realloc (p, (n) * sizeof (t)))
471
#else
472
static void *
473
test_malloc(size_t count, const char *file, size_t line)
474
{
475
if (count == 0) {
476
fprintf(stderr, "%s:%lu: allocation of zero bytes\n",
477
file, (unsigned long) line);
478
exit(1);
479
}
480
return malloc(count);
481
}
482
483
static void *
484
test_realloc(void *p, size_t count, const char *file, size_t line)
485
{
486
if (count == 0) {
487
fprintf(stderr, "%s:%lu: reallocation of zero bytes\n",
488
file, (unsigned long) line);
489
exit(1);
490
}
491
return realloc(p, count);
492
}
493
#define re_malloc(t,n) ((t *) test_malloc (((n) * sizeof (t)), __FILE__, __LINE__))
494
#define re_realloc(p,t,n) ((t *) test_realloc (p, (n) * sizeof (t), __FILE__, __LINE__))
495
#endif
496
#define re_free(p) free (p)
497
498
struct bin_tree_t
499
{
500
struct bin_tree_t *parent;
501
struct bin_tree_t *left;
502
struct bin_tree_t *right;
503
struct bin_tree_t *first;
504
struct bin_tree_t *next;
505
506
re_token_t token;
507
508
/* `node_idx' is the index in dfa->nodes, if `type' == 0.
509
Otherwise `type' indicate the type of this node. */
510
int node_idx;
511
};
512
typedef struct bin_tree_t bin_tree_t;
513
514
#define BIN_TREE_STORAGE_SIZE \
515
((1024 - sizeof (void *)) / sizeof (bin_tree_t))
516
517
struct bin_tree_storage_t
518
{
519
struct bin_tree_storage_t *next;
520
bin_tree_t data[BIN_TREE_STORAGE_SIZE];
521
};
522
typedef struct bin_tree_storage_t bin_tree_storage_t;
523
524
#define CONTEXT_WORD 1
525
#define CONTEXT_NEWLINE (CONTEXT_WORD << 1)
526
#define CONTEXT_BEGBUF (CONTEXT_NEWLINE << 1)
527
#define CONTEXT_ENDBUF (CONTEXT_BEGBUF << 1)
528
529
#define IS_WORD_CONTEXT(c) ((c) & CONTEXT_WORD)
530
#define IS_NEWLINE_CONTEXT(c) ((c) & CONTEXT_NEWLINE)
531
#define IS_BEGBUF_CONTEXT(c) ((c) & CONTEXT_BEGBUF)
532
#define IS_ENDBUF_CONTEXT(c) ((c) & CONTEXT_ENDBUF)
533
#define IS_ORDINARY_CONTEXT(c) ((c) == 0)
534
535
#define IS_WORD_CHAR(ch) (isalnum (ch) || (ch) == '_')
536
#define IS_NEWLINE(ch) ((ch) == NEWLINE_CHAR)
537
#define IS_WIDE_WORD_CHAR(ch) (iswalnum (ch) || (ch) == L'_')
538
#define IS_WIDE_NEWLINE(ch) ((ch) == WIDE_NEWLINE_CHAR)
539
540
#define NOT_SATISFY_PREV_CONSTRAINT(constraint,context) \
541
((((constraint) & PREV_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
542
|| ((constraint & PREV_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
543
|| ((constraint & PREV_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context))\
544
|| ((constraint & PREV_BEGBUF_CONSTRAINT) && !IS_BEGBUF_CONTEXT (context)))
545
546
#define NOT_SATISFY_NEXT_CONSTRAINT(constraint,context) \
547
((((constraint) & NEXT_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
548
|| (((constraint) & NEXT_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
549
|| (((constraint) & NEXT_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context)) \
550
|| (((constraint) & NEXT_ENDBUF_CONSTRAINT) && !IS_ENDBUF_CONTEXT (context)))
551
552
struct re_dfastate_t
553
{
554
unsigned int hash;
555
re_node_set nodes;
556
re_node_set non_eps_nodes;
557
re_node_set inveclosure;
558
re_node_set *entrance_nodes;
559
struct re_dfastate_t **trtable, **word_trtable;
560
unsigned int context : 4;
561
unsigned int halt : 1;
562
/* If this state can accept `multi byte'.
563
Note that we refer to multibyte characters, and multi character
564
collating elements as `multi byte'. */
565
unsigned int accept_mb : 1;
566
/* If this state has backreference node(s). */
567
unsigned int has_backref : 1;
568
unsigned int has_constraint : 1;
569
};
570
typedef struct re_dfastate_t re_dfastate_t;
571
572
struct re_state_table_entry
573
{
574
int num;
575
int alloc;
576
re_dfastate_t **array;
577
};
578
579
/* Array type used in re_sub_match_last_t and re_sub_match_top_t. */
580
581
typedef struct
582
{
583
int next_idx;
584
int alloc;
585
re_dfastate_t **array;
586
} state_array_t;
587
588
/* Store information about the node NODE whose type is OP_CLOSE_SUBEXP. */
589
590
typedef struct
591
{
592
int node;
593
int str_idx; /* The position NODE match at. */
594
state_array_t path;
595
} re_sub_match_last_t;
596
597
/* Store information about the node NODE whose type is OP_OPEN_SUBEXP.
598
And information about the node, whose type is OP_CLOSE_SUBEXP,
599
corresponding to NODE is stored in LASTS. */
600
601
typedef struct
602
{
603
int str_idx;
604
int node;
605
state_array_t *path;
606
int alasts; /* Allocation size of LASTS. */
607
int nlasts; /* The number of LASTS. */
608
re_sub_match_last_t **lasts;
609
} re_sub_match_top_t;
610
611
struct re_backref_cache_entry
612
{
613
int node;
614
int str_idx;
615
int subexp_from;
616
int subexp_to;
617
char more;
618
char unused;
619
unsigned short int eps_reachable_subexps_map;
620
};
621
622
typedef struct
623
{
624
/* The string object corresponding to the input string. */
625
re_string_t input;
626
#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
627
const re_dfa_t *const dfa;
628
#else
629
const re_dfa_t *dfa;
630
#endif
631
/* EFLAGS of the argument of regexec. */
632
int eflags;
633
/* Where the matching ends. */
634
int match_last;
635
int last_node;
636
/* The state log used by the matcher. */
637
re_dfastate_t **state_log;
638
int state_log_top;
639
/* Back reference cache. */
640
int nbkref_ents;
641
int abkref_ents;
642
struct re_backref_cache_entry *bkref_ents;
643
int max_mb_elem_len;
644
int nsub_tops;
645
int asub_tops;
646
re_sub_match_top_t **sub_tops;
647
} re_match_context_t;
648
649
typedef struct
650
{
651
re_dfastate_t **sifted_states;
652
re_dfastate_t **limited_states;
653
int last_node;
654
int last_str_idx;
655
re_node_set limits;
656
} re_sift_context_t;
657
658
struct re_fail_stack_ent_t
659
{
660
int idx;
661
int node;
662
regmatch_t *regs;
663
re_node_set eps_via_nodes;
664
};
665
666
struct re_fail_stack_t
667
{
668
int num;
669
int alloc;
670
struct re_fail_stack_ent_t *stack;
671
};
672
673
struct re_dfa_t
674
{
675
re_token_t *nodes;
676
size_t nodes_alloc;
677
size_t nodes_len;
678
int *nexts;
679
int *org_indices;
680
re_node_set *edests;
681
re_node_set *eclosures;
682
re_node_set *inveclosures;
683
struct re_state_table_entry *state_table;
684
re_dfastate_t *init_state;
685
re_dfastate_t *init_state_word;
686
re_dfastate_t *init_state_nl;
687
re_dfastate_t *init_state_begbuf;
688
bin_tree_t *str_tree;
689
bin_tree_storage_t *str_tree_storage;
690
re_bitset_ptr_t sb_char;
691
int str_tree_storage_idx;
692
693
/* number of subexpressions `re_nsub' is in regex_t. */
694
unsigned int state_hash_mask;
695
int init_node;
696
int nbackref; /* The number of backreference in this dfa. */
697
698
/* Bitmap expressing which backreference is used. */
699
bitset_word_t used_bkref_map;
700
bitset_word_t completed_bkref_map;
701
702
unsigned int has_plural_match : 1;
703
/* If this dfa has "multibyte node", which is a backreference or
704
a node which can accept multibyte character or multi character
705
collating element. */
706
unsigned int has_mb_node : 1;
707
unsigned int is_utf8 : 1;
708
unsigned int map_notascii : 1;
709
unsigned int word_ops_used : 1;
710
int mb_cur_max;
711
bitset_t word_char;
712
reg_syntax_t syntax;
713
int *subexp_map;
714
#ifdef DEBUG
715
char* re_str;
716
#endif
717
#if defined _LIBC
718
__libc_lock_define (, lock)
719
#endif
720
};
721
722
#define re_node_set_init_empty(set) memset (set, '\0', sizeof (re_node_set))
723
#define re_node_set_remove(set,id) \
724
(re_node_set_remove_at (set, re_node_set_contains (set, id) - 1))
725
#define re_node_set_empty(p) ((p)->nelem = 0)
726
#define re_node_set_free(set) re_free ((set)->elems)
727
728
729
typedef enum
730
{
731
SB_CHAR,
732
MB_CHAR,
733
EQUIV_CLASS,
734
COLL_SYM,
735
CHAR_CLASS
736
} bracket_elem_type;
737
738
typedef struct
739
{
740
bracket_elem_type type;
741
union
742
{
743
unsigned char ch;
744
unsigned char *name;
745
wchar_t wch;
746
} opr;
747
} bracket_elem_t;
748
749
750
/* Inline functions for bitset operation. */
751
static void __attribute__ ((unused))
752
bitset_not (bitset_t set)
753
{
754
int bitset_i;
755
for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
756
set[bitset_i] = ~set[bitset_i];
757
}
758
759
static void __attribute__ ((unused))
760
bitset_merge (bitset_t dest, const bitset_t src)
761
{
762
int bitset_i;
763
for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
764
dest[bitset_i] |= src[bitset_i];
765
}
766
767
static void __attribute__ ((unused))
768
bitset_mask (bitset_t dest, const bitset_t src)
769
{
770
int bitset_i;
771
for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
772
dest[bitset_i] &= src[bitset_i];
773
}
774
775
#ifdef RE_ENABLE_I18N
776
/* Inline functions for re_string. */
777
static int
778
internal_function __attribute__ ((pure, unused))
779
re_string_char_size_at (const re_string_t *pstr, int idx)
780
{
781
int byte_idx;
782
if (pstr->mb_cur_max == 1)
783
return 1;
784
for (byte_idx = 1; idx + byte_idx < pstr->valid_len; ++byte_idx)
785
if (pstr->wcs[idx + byte_idx] != WEOF)
786
break;
787
return byte_idx;
788
}
789
790
static wint_t
791
internal_function __attribute__ ((pure, unused))
792
re_string_wchar_at (const re_string_t *pstr, int idx)
793
{
794
if (pstr->mb_cur_max == 1)
795
return (wint_t) pstr->mbs[idx];
796
return (wint_t) pstr->wcs[idx];
797
}
798
799
# ifndef NOT_IN_libc
800
# ifdef _LIBC
801
# include <locale/weight.h>
802
# endif
803
804
static int
805
internal_function __attribute__ ((pure, unused))
806
re_string_elem_size_at (const re_string_t *pstr, int idx)
807
{
808
# ifdef _LIBC
809
const unsigned char *p, *extra;
810
const int32_t *table, *indirect;
811
uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
812
813
if (nrules != 0)
814
{
815
table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
816
extra = (const unsigned char *)
817
_NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
818
indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
819
_NL_COLLATE_INDIRECTMB);
820
p = pstr->mbs + idx;
821
findidx (table, indirect, extra, &p, pstr->len - idx);
822
return p - pstr->mbs - idx;
823
}
824
else
825
# endif /* _LIBC */
826
return 1;
827
}
828
# endif
829
#endif /* RE_ENABLE_I18N */
830
831
#endif /* _REGEX_INTERNAL_H */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1