29#ifdef __STDC__
30# ifndef _PTR_T
31# define _PTR_T
32 typedef void * ptr_t;
33# endif
34#else
35# ifndef _PTR_T
36# define _PTR_T
37 typedef char * ptr_t;
38# endif
39#endif
40
41#ifdef PARAMS
42# undef PARAMS
43#endif
44#if PROTOTYPES
45# define PARAMS(x) x
46#else
47# define PARAMS(x) ()
48#endif
49
50/* Number of bits in an unsigned char. */
51#ifndef CHARBITS
52#define CHARBITS 8
53#endif
54
55/* First integer value that is greater than any character code. */
56#define NOTCHAR (1 << CHARBITS)
57
58/* INTBITS need not be exact, just a lower bound. */
59#ifndef INTBITS
60#define INTBITS (CHARBITS * sizeof (int))
61#endif
62
63/* Number of ints required to hold a bit for every character. */
64#define CHARCLASS_INTS ((NOTCHAR + INTBITS - 1) / INTBITS)
65
66/* Sets of unsigned characters are stored as bit vectors in arrays of ints. */
67typedef int charclass[CHARCLASS_INTS];
68
69/* The regexp is parsed into an array of tokens in postfix form. Some tokens
70 are operators and others are terminal symbols. Most (but not all) of these
71 codes are returned by the lexical analyzer. */
72
73typedef enum
74{
75 END = -1, /* END is a terminal symbol that matches the
76 end of input; any value of END or less in
77 the parse tree is such a symbol. Accepting
78 states of the DFA are those that would have
79 a transition on END. */
80
81 /* Ordinary character values are terminal symbols that match themselves. */
82
83 EMPTY = NOTCHAR, /* EMPTY is a terminal symbol that matches
84 the empty string. */
85
86 BACKREF, /* BACKREF is generated by \<digit>; it
87 it not completely handled. If the scanner
88 detects a transition on backref, it returns
89 a kind of "semi-success" indicating that
90 the match will have to be verified with
91 a backtracking matcher. */
92
93 BEGLINE, /* BEGLINE is a terminal symbol that matches
94 the empty string if it is at the beginning
95 of a line. */
96
97 ENDLINE, /* ENDLINE is a terminal symbol that matches
98 the empty string if it is at the end of
99 a line. */
100
101 BEGWORD, /* BEGWORD is a terminal symbol that matches
102 the empty string if it is at the beginning
103 of a word. */
104
105 ENDWORD, /* ENDWORD is a terminal symbol that matches
106 the empty string if it is at the end of
107 a word. */
108
109 LIMWORD, /* LIMWORD is a terminal symbol that matches
110 the empty string if it is at the beginning
111 or the end of a word. */
112
113 NOTLIMWORD, /* NOTLIMWORD is a terminal symbol that
114 matches the empty string if it is not at
115 the beginning or end of a word. */
116
117 QMARK, /* QMARK is an operator of one argument that
118 matches zero or one occurences of its
119 argument. */
120
121 STAR, /* STAR is an operator of one argument that
122 matches the Kleene closure (zero or more
123 occurrences) of its argument. */
124
125 PLUS, /* PLUS is an operator of one argument that
126 matches the positive closure (one or more
127 occurrences) of its argument. */
128
129 REPMN, /* REPMN is a lexical token corresponding
130 to the {m,n} construct. REPMN never
131 appears in the compiled token vector. */
132
133 CAT, /* CAT is an operator of two arguments that
134 matches the concatenation of its
135 arguments. CAT is never returned by the
136 lexical analyzer. */
137
138 OR, /* OR is an operator of two arguments that
139 matches either of its arguments. */
140
141 ORTOP, /* OR at the toplevel in the parse tree.
142 This is used for a boyer-moore heuristic. */
143
144 LPAREN, /* LPAREN never appears in the parse tree,
145 it is only a lexeme. */
146
147 RPAREN, /* RPAREN never appears in the parse tree. */
148
149 CRANGE, /* CRANGE never appears in the parse tree.
150 It stands for a character range that can
151 match a string of one or more characters.
152 For example, [a-z] can match "ch" in
153 a Spanish locale. */
154
155#ifdef MBS_SUPPORT
156 ANYCHAR, /* ANYCHAR is a terminal symbol that matches
157 any multibyte(or singlebyte) characters.
158 It is used only if MB_CUR_MAX > 1. */
159
160 MBCSET, /* MBCSET is similar to CSET, but for
161 multibyte characters. */
162#endif /* MBS_SUPPORT */
163
164 CSET /* CSET and (and any value greater) is a
165 terminal symbol that matches any of a
166 class of characters. */
167} token;
168
169/* Sets are stored in an array in the compiled dfa; the index of the
170 array corresponding to a given set token is given by SET_INDEX(t). */
171#define SET_INDEX(t) ((t) - CSET)
172
173/* Sometimes characters can only be matched depending on the surrounding
174 context. Such context decisions depend on what the previous character
175 was, and the value of the current (lookahead) character. Context
176 dependent constraints are encoded as 8 bit integers. Each bit that
177 is set indicates that the constraint succeeds in the corresponding
178 context.
179
180 bit 7 - previous and current are newlines
181 bit 6 - previous was newline, current isn't
182 bit 5 - previous wasn't newline, current is
183 bit 4 - neither previous nor current is a newline
184 bit 3 - previous and current are word-constituents
185 bit 2 - previous was word-constituent, current isn't
186 bit 1 - previous wasn't word-constituent, current is
187 bit 0 - neither previous nor current is word-constituent
188
189 Word-constituent characters are those that satisfy isalnum().
190
191 The macro SUCCEEDS_IN_CONTEXT determines whether a a given constraint
192 succeeds in a particular context. Prevn is true if the previous character
193 was a newline, currn is true if the lookahead character is a newline.
194 Prevl and currl similarly depend upon whether the previous and current
195 characters are word-constituent letters. */
196#define MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \
197 ((constraint) & 1 << (((prevn) ? 2 : 0) + ((currn) ? 1 : 0) + 4))
198#define MATCHES_LETTER_CONTEXT(constraint, prevl, currl) \
199 ((constraint) & 1 << (((prevl) ? 2 : 0) + ((currl) ? 1 : 0)))
200#define SUCCEEDS_IN_CONTEXT(constraint, prevn, currn, prevl, currl) \
201 (MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \
202 && MATCHES_LETTER_CONTEXT(constraint, prevl, currl))
203
204/* The following macros give information about what a constraint depends on. */
205#define PREV_NEWLINE_DEPENDENT(constraint) \
206 (((constraint) & 0xc0) >> 2 != ((constraint) & 0x30))
207#define PREV_LETTER_DEPENDENT(constraint) \
208 (((constraint) & 0x0c) >> 2 != ((constraint) & 0x03))
209
210/* Tokens that match the empty string subject to some constraint actually
211 work by applying that constraint to determine what may follow them,
212 taking into account what has gone before. The following values are
213 the constraints corresponding to the special tokens previously defined. */
214#define NO_CONSTRAINT 0xff
215#define BEGLINE_CONSTRAINT 0xcf
216#define ENDLINE_CONSTRAINT 0xaf
217#define BEGWORD_CONSTRAINT 0xf2
218#define ENDWORD_CONSTRAINT 0xf4
219#define LIMWORD_CONSTRAINT 0xf6
220#define NOTLIMWORD_CONSTRAINT 0xf9
221
222/* States of the recognizer correspond to sets of positions in the parse
223 tree, together with the constraints under which they may be matched.
224 So a position is encoded as an index into the parse tree together with
225 a constraint. */
226typedef struct
227{
228 unsigned index; /* Index into the parse array. */
229 unsigned constraint; /* Constraint for matching this position. */
230} position;
231
232/* Sets of positions are stored as arrays. */
233typedef struct
234{
235 position *elems; /* Elements of this position set. */
236 int nelem; /* Number of elements in this set. */
237} position_set;
238
239/* A state of the dfa consists of a set of positions, some flags,
240 and the token value of the lowest-numbered position of the state that
241 contains an END token. */
242typedef struct
243{
244 int hash; /* Hash of the positions of this state. */
245 position_set elems; /* Positions this state could match. */
246 char newline; /* True if previous state matched newline. */
247 char letter; /* True if previous state matched a letter. */
248 char backref; /* True if this state matches a \<digit>. */
249 unsigned char constraint; /* Constraint for this state to accept. */
250 int first_end; /* Token value of the first END in elems. */
251#ifdef MBS_SUPPORT
252 position_set mbps; /* Positions which can match multibyte
253 characters. e.g. period.
254 These staff are used only if
255 MB_CUR_MAX > 1. */
256#endif
257} dfa_state;
258
259/* Element of a list of strings, at least one of which is known to
260 appear in any R.E. matching the DFA. */
261struct dfamust
262{
263 int exact;
264 char *must;
265 struct dfamust *next;
266};
267
268#ifdef MBS_SUPPORT
269/* A bracket operator.
270 e.g. [a-c], [[:alpha:]], etc. */
271struct mb_char_classes
272{
273 int invert;
274 wchar_t *chars; /* Normal characters. */
275 int nchars;
276 wctype_t *ch_classes; /* Character classes. */
277 int nch_classes;
278 wchar_t *range_sts; /* Range characters (start of the range). */
279 wchar_t *range_ends; /* Range characters (end of the range). */
280 int nranges;
281 char **equivs; /* Equivalent classes. */
282 int nequivs;
283 char **coll_elems;
284 int ncoll_elems; /* Collating elements. */
285};
286#endif
287
288/* A compiled regular expression. */
289struct dfa
290{
291 /* Stuff built by the scanner. */
292 charclass *charclasses; /* Array of character sets for CSET tokens. */
293 int cindex; /* Index for adding new charclasses. */
294 int calloc; /* Number of charclasses currently allocated. */
295
296 /* Stuff built by the parser. */
297 token *tokens; /* Postfix parse array. */
298 int tindex; /* Index for adding new tokens. */
299 int talloc; /* Number of tokens currently allocated. */
300 int depth; /* Depth required of an evaluation stack
301 used for depth-first traversal of the
302 parse tree. */
303 int nleaves; /* Number of leaves on the parse tree. */
304 int nregexps; /* Count of parallel regexps being built
305 with dfaparse(). */
306#ifdef MBS_SUPPORT
307 /* These stuff are used only if MB_CUR_MAX > 1 or multibyte environments. */
308 int nmultibyte_prop;
309 int *multibyte_prop;
310 /* The value of multibyte_prop[i] is defined by following rule.
311 if tokens[i] < NOTCHAR
312 bit 1 : tokens[i] is a singlebyte character, or the last-byte of
313 a multibyte character.
314 bit 0 : tokens[i] is a singlebyte character, or the 1st-byte of
315 a multibyte character.
316 if tokens[i] = MBCSET
317 ("the index of mbcsets correspnd to this operator" << 2) + 3
318
319 e.g.
320 tokens
321 = 'single_byte_a', 'multi_byte_A', single_byte_b'
322 = 'sb_a', 'mb_A(1st byte)', 'mb_A(2nd byte)', 'mb_A(3rd byte)', 'sb_b'
323 multibyte_prop
324 = 3 , 1 , 0 , 2 , 3
325 */
326
327 /* Array of the bracket expressoin in the DFA. */
328 struct mb_char_classes *mbcsets;
329 int nmbcsets;
330 int mbcsets_alloc;
331#endif
332
333 /* Stuff owned by the state builder. */
334 dfa_state *states; /* States of the dfa. */
335 int sindex; /* Index for adding new states. */
336 int salloc; /* Number of states currently allocated. */
337
338 /* Stuff built by the structure analyzer. */
339 position_set *follows; /* Array of follow sets, indexed by position
340 index. The follow of a position is the set
341 of positions containing characters that
342 could conceivably follow a character
343 matching the given position in a string
344 matching the regexp. Allocated to the
345 maximum possible position index. */
346 int searchflag; /* True if we are supposed to build a searching
347 as opposed to an exact matcher. A searching
348 matcher finds the first and shortest string
349 matching a regexp anywhere in the buffer,
350 whereas an exact matcher finds the longest
351 string matching, but anchored to the
352 beginning of the buffer. */
353
354 /* Stuff owned by the executor. */
355 int tralloc; /* Number of transition tables that have
356 slots so far. */
357 int trcount; /* Number of transition tables that have
358 actually been built. */
359 int **trans; /* Transition tables for states that can
360 never accept. If the transitions for a
361 state have not yet been computed, or the
362 state could possibly accept, its entry in
363 this table is NULL. */
364 int **realtrans; /* Trans always points to realtrans + 1; this
365 is so trans[-1] can contain NULL. */
366 int **fails; /* Transition tables after failing to accept
367 on a state that potentially could do so. */
368 int *success; /* Table of acceptance conditions used in
369 dfaexec and computed in build_state. */
370 struct dfamust *musts; /* List of strings, at least one of which
371 is known to appear in any r.e. matching
372 the dfa. */
373};
374
375/* Some macros for user access to dfa internals. */
376
377/* ACCEPTING returns true if s could possibly be an accepting state of r. */
378#define ACCEPTING(s, r) ((r).states[s].constraint)
379
380/* ACCEPTS_IN_CONTEXT returns true if the given state accepts in the
381 specified context. */
382#define ACCEPTS_IN_CONTEXT(prevn, currn, prevl, currl, state, dfa) \
383 SUCCEEDS_IN_CONTEXT((dfa).states[state].constraint, \
384 prevn, currn, prevl, currl)
385
386/* FIRST_MATCHING_REGEXP returns the index number of the first of parallel
387 regexps that a given state could accept. Parallel regexps are numbered
388 starting at 1. */
389#define FIRST_MATCHING_REGEXP(state, dfa) (-(dfa).states[state].first_end)
390
391/* Entry points. */
392
393/* dfasyntax() takes three arguments; the first sets the syntax bits described
394 earlier in this file, the second sets the case-folding flag, and the
395 third specifies the line terminator. */
396extern void dfasyntax PARAMS ((reg_syntax_t, int, unsigned char));
397
398/* Compile the given string of the given length into the given struct dfa.
399 Final argument is a flag specifying whether to build a searching or an
400 exact matcher. */
401extern void dfacomp PARAMS ((char const *, size_t, struct dfa *, int));
402
403/* Execute the given struct dfa on the buffer of characters. The
404 last byte of the buffer must equal the end-of-line byte.
405 The final argument points to a flag that will
406 be set if further examination by a backtracking matcher is needed in
407 order to verify backreferencing; otherwise the flag will be cleared.
408 Returns (size_t) -1 if no match is found, or the offset of the first
409 character after the first & shortest matching string in the buffer. */
| 27#ifdef __STDC__
28# ifndef _PTR_T
29# define _PTR_T
30 typedef void * ptr_t;
31# endif
32#else
33# ifndef _PTR_T
34# define _PTR_T
35 typedef char * ptr_t;
36# endif
37#endif
38
39#ifdef PARAMS
40# undef PARAMS
41#endif
42#if PROTOTYPES
43# define PARAMS(x) x
44#else
45# define PARAMS(x) ()
46#endif
47
48/* Number of bits in an unsigned char. */
49#ifndef CHARBITS
50#define CHARBITS 8
51#endif
52
53/* First integer value that is greater than any character code. */
54#define NOTCHAR (1 << CHARBITS)
55
56/* INTBITS need not be exact, just a lower bound. */
57#ifndef INTBITS
58#define INTBITS (CHARBITS * sizeof (int))
59#endif
60
61/* Number of ints required to hold a bit for every character. */
62#define CHARCLASS_INTS ((NOTCHAR + INTBITS - 1) / INTBITS)
63
64/* Sets of unsigned characters are stored as bit vectors in arrays of ints. */
65typedef int charclass[CHARCLASS_INTS];
66
67/* The regexp is parsed into an array of tokens in postfix form. Some tokens
68 are operators and others are terminal symbols. Most (but not all) of these
69 codes are returned by the lexical analyzer. */
70
71typedef enum
72{
73 END = -1, /* END is a terminal symbol that matches the
74 end of input; any value of END or less in
75 the parse tree is such a symbol. Accepting
76 states of the DFA are those that would have
77 a transition on END. */
78
79 /* Ordinary character values are terminal symbols that match themselves. */
80
81 EMPTY = NOTCHAR, /* EMPTY is a terminal symbol that matches
82 the empty string. */
83
84 BACKREF, /* BACKREF is generated by \<digit>; it
85 it not completely handled. If the scanner
86 detects a transition on backref, it returns
87 a kind of "semi-success" indicating that
88 the match will have to be verified with
89 a backtracking matcher. */
90
91 BEGLINE, /* BEGLINE is a terminal symbol that matches
92 the empty string if it is at the beginning
93 of a line. */
94
95 ENDLINE, /* ENDLINE is a terminal symbol that matches
96 the empty string if it is at the end of
97 a line. */
98
99 BEGWORD, /* BEGWORD is a terminal symbol that matches
100 the empty string if it is at the beginning
101 of a word. */
102
103 ENDWORD, /* ENDWORD is a terminal symbol that matches
104 the empty string if it is at the end of
105 a word. */
106
107 LIMWORD, /* LIMWORD is a terminal symbol that matches
108 the empty string if it is at the beginning
109 or the end of a word. */
110
111 NOTLIMWORD, /* NOTLIMWORD is a terminal symbol that
112 matches the empty string if it is not at
113 the beginning or end of a word. */
114
115 QMARK, /* QMARK is an operator of one argument that
116 matches zero or one occurences of its
117 argument. */
118
119 STAR, /* STAR is an operator of one argument that
120 matches the Kleene closure (zero or more
121 occurrences) of its argument. */
122
123 PLUS, /* PLUS is an operator of one argument that
124 matches the positive closure (one or more
125 occurrences) of its argument. */
126
127 REPMN, /* REPMN is a lexical token corresponding
128 to the {m,n} construct. REPMN never
129 appears in the compiled token vector. */
130
131 CAT, /* CAT is an operator of two arguments that
132 matches the concatenation of its
133 arguments. CAT is never returned by the
134 lexical analyzer. */
135
136 OR, /* OR is an operator of two arguments that
137 matches either of its arguments. */
138
139 ORTOP, /* OR at the toplevel in the parse tree.
140 This is used for a boyer-moore heuristic. */
141
142 LPAREN, /* LPAREN never appears in the parse tree,
143 it is only a lexeme. */
144
145 RPAREN, /* RPAREN never appears in the parse tree. */
146
147 CRANGE, /* CRANGE never appears in the parse tree.
148 It stands for a character range that can
149 match a string of one or more characters.
150 For example, [a-z] can match "ch" in
151 a Spanish locale. */
152
153#ifdef MBS_SUPPORT
154 ANYCHAR, /* ANYCHAR is a terminal symbol that matches
155 any multibyte(or singlebyte) characters.
156 It is used only if MB_CUR_MAX > 1. */
157
158 MBCSET, /* MBCSET is similar to CSET, but for
159 multibyte characters. */
160#endif /* MBS_SUPPORT */
161
162 CSET /* CSET and (and any value greater) is a
163 terminal symbol that matches any of a
164 class of characters. */
165} token;
166
167/* Sets are stored in an array in the compiled dfa; the index of the
168 array corresponding to a given set token is given by SET_INDEX(t). */
169#define SET_INDEX(t) ((t) - CSET)
170
171/* Sometimes characters can only be matched depending on the surrounding
172 context. Such context decisions depend on what the previous character
173 was, and the value of the current (lookahead) character. Context
174 dependent constraints are encoded as 8 bit integers. Each bit that
175 is set indicates that the constraint succeeds in the corresponding
176 context.
177
178 bit 7 - previous and current are newlines
179 bit 6 - previous was newline, current isn't
180 bit 5 - previous wasn't newline, current is
181 bit 4 - neither previous nor current is a newline
182 bit 3 - previous and current are word-constituents
183 bit 2 - previous was word-constituent, current isn't
184 bit 1 - previous wasn't word-constituent, current is
185 bit 0 - neither previous nor current is word-constituent
186
187 Word-constituent characters are those that satisfy isalnum().
188
189 The macro SUCCEEDS_IN_CONTEXT determines whether a a given constraint
190 succeeds in a particular context. Prevn is true if the previous character
191 was a newline, currn is true if the lookahead character is a newline.
192 Prevl and currl similarly depend upon whether the previous and current
193 characters are word-constituent letters. */
194#define MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \
195 ((constraint) & 1 << (((prevn) ? 2 : 0) + ((currn) ? 1 : 0) + 4))
196#define MATCHES_LETTER_CONTEXT(constraint, prevl, currl) \
197 ((constraint) & 1 << (((prevl) ? 2 : 0) + ((currl) ? 1 : 0)))
198#define SUCCEEDS_IN_CONTEXT(constraint, prevn, currn, prevl, currl) \
199 (MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \
200 && MATCHES_LETTER_CONTEXT(constraint, prevl, currl))
201
202/* The following macros give information about what a constraint depends on. */
203#define PREV_NEWLINE_DEPENDENT(constraint) \
204 (((constraint) & 0xc0) >> 2 != ((constraint) & 0x30))
205#define PREV_LETTER_DEPENDENT(constraint) \
206 (((constraint) & 0x0c) >> 2 != ((constraint) & 0x03))
207
208/* Tokens that match the empty string subject to some constraint actually
209 work by applying that constraint to determine what may follow them,
210 taking into account what has gone before. The following values are
211 the constraints corresponding to the special tokens previously defined. */
212#define NO_CONSTRAINT 0xff
213#define BEGLINE_CONSTRAINT 0xcf
214#define ENDLINE_CONSTRAINT 0xaf
215#define BEGWORD_CONSTRAINT 0xf2
216#define ENDWORD_CONSTRAINT 0xf4
217#define LIMWORD_CONSTRAINT 0xf6
218#define NOTLIMWORD_CONSTRAINT 0xf9
219
220/* States of the recognizer correspond to sets of positions in the parse
221 tree, together with the constraints under which they may be matched.
222 So a position is encoded as an index into the parse tree together with
223 a constraint. */
224typedef struct
225{
226 unsigned index; /* Index into the parse array. */
227 unsigned constraint; /* Constraint for matching this position. */
228} position;
229
230/* Sets of positions are stored as arrays. */
231typedef struct
232{
233 position *elems; /* Elements of this position set. */
234 int nelem; /* Number of elements in this set. */
235} position_set;
236
237/* A state of the dfa consists of a set of positions, some flags,
238 and the token value of the lowest-numbered position of the state that
239 contains an END token. */
240typedef struct
241{
242 int hash; /* Hash of the positions of this state. */
243 position_set elems; /* Positions this state could match. */
244 char newline; /* True if previous state matched newline. */
245 char letter; /* True if previous state matched a letter. */
246 char backref; /* True if this state matches a \<digit>. */
247 unsigned char constraint; /* Constraint for this state to accept. */
248 int first_end; /* Token value of the first END in elems. */
249#ifdef MBS_SUPPORT
250 position_set mbps; /* Positions which can match multibyte
251 characters. e.g. period.
252 These staff are used only if
253 MB_CUR_MAX > 1. */
254#endif
255} dfa_state;
256
257/* Element of a list of strings, at least one of which is known to
258 appear in any R.E. matching the DFA. */
259struct dfamust
260{
261 int exact;
262 char *must;
263 struct dfamust *next;
264};
265
266#ifdef MBS_SUPPORT
267/* A bracket operator.
268 e.g. [a-c], [[:alpha:]], etc. */
269struct mb_char_classes
270{
271 int invert;
272 wchar_t *chars; /* Normal characters. */
273 int nchars;
274 wctype_t *ch_classes; /* Character classes. */
275 int nch_classes;
276 wchar_t *range_sts; /* Range characters (start of the range). */
277 wchar_t *range_ends; /* Range characters (end of the range). */
278 int nranges;
279 char **equivs; /* Equivalent classes. */
280 int nequivs;
281 char **coll_elems;
282 int ncoll_elems; /* Collating elements. */
283};
284#endif
285
286/* A compiled regular expression. */
287struct dfa
288{
289 /* Stuff built by the scanner. */
290 charclass *charclasses; /* Array of character sets for CSET tokens. */
291 int cindex; /* Index for adding new charclasses. */
292 int calloc; /* Number of charclasses currently allocated. */
293
294 /* Stuff built by the parser. */
295 token *tokens; /* Postfix parse array. */
296 int tindex; /* Index for adding new tokens. */
297 int talloc; /* Number of tokens currently allocated. */
298 int depth; /* Depth required of an evaluation stack
299 used for depth-first traversal of the
300 parse tree. */
301 int nleaves; /* Number of leaves on the parse tree. */
302 int nregexps; /* Count of parallel regexps being built
303 with dfaparse(). */
304#ifdef MBS_SUPPORT
305 /* These stuff are used only if MB_CUR_MAX > 1 or multibyte environments. */
306 int nmultibyte_prop;
307 int *multibyte_prop;
308 /* The value of multibyte_prop[i] is defined by following rule.
309 if tokens[i] < NOTCHAR
310 bit 1 : tokens[i] is a singlebyte character, or the last-byte of
311 a multibyte character.
312 bit 0 : tokens[i] is a singlebyte character, or the 1st-byte of
313 a multibyte character.
314 if tokens[i] = MBCSET
315 ("the index of mbcsets correspnd to this operator" << 2) + 3
316
317 e.g.
318 tokens
319 = 'single_byte_a', 'multi_byte_A', single_byte_b'
320 = 'sb_a', 'mb_A(1st byte)', 'mb_A(2nd byte)', 'mb_A(3rd byte)', 'sb_b'
321 multibyte_prop
322 = 3 , 1 , 0 , 2 , 3
323 */
324
325 /* Array of the bracket expressoin in the DFA. */
326 struct mb_char_classes *mbcsets;
327 int nmbcsets;
328 int mbcsets_alloc;
329#endif
330
331 /* Stuff owned by the state builder. */
332 dfa_state *states; /* States of the dfa. */
333 int sindex; /* Index for adding new states. */
334 int salloc; /* Number of states currently allocated. */
335
336 /* Stuff built by the structure analyzer. */
337 position_set *follows; /* Array of follow sets, indexed by position
338 index. The follow of a position is the set
339 of positions containing characters that
340 could conceivably follow a character
341 matching the given position in a string
342 matching the regexp. Allocated to the
343 maximum possible position index. */
344 int searchflag; /* True if we are supposed to build a searching
345 as opposed to an exact matcher. A searching
346 matcher finds the first and shortest string
347 matching a regexp anywhere in the buffer,
348 whereas an exact matcher finds the longest
349 string matching, but anchored to the
350 beginning of the buffer. */
351
352 /* Stuff owned by the executor. */
353 int tralloc; /* Number of transition tables that have
354 slots so far. */
355 int trcount; /* Number of transition tables that have
356 actually been built. */
357 int **trans; /* Transition tables for states that can
358 never accept. If the transitions for a
359 state have not yet been computed, or the
360 state could possibly accept, its entry in
361 this table is NULL. */
362 int **realtrans; /* Trans always points to realtrans + 1; this
363 is so trans[-1] can contain NULL. */
364 int **fails; /* Transition tables after failing to accept
365 on a state that potentially could do so. */
366 int *success; /* Table of acceptance conditions used in
367 dfaexec and computed in build_state. */
368 struct dfamust *musts; /* List of strings, at least one of which
369 is known to appear in any r.e. matching
370 the dfa. */
371};
372
373/* Some macros for user access to dfa internals. */
374
375/* ACCEPTING returns true if s could possibly be an accepting state of r. */
376#define ACCEPTING(s, r) ((r).states[s].constraint)
377
378/* ACCEPTS_IN_CONTEXT returns true if the given state accepts in the
379 specified context. */
380#define ACCEPTS_IN_CONTEXT(prevn, currn, prevl, currl, state, dfa) \
381 SUCCEEDS_IN_CONTEXT((dfa).states[state].constraint, \
382 prevn, currn, prevl, currl)
383
384/* FIRST_MATCHING_REGEXP returns the index number of the first of parallel
385 regexps that a given state could accept. Parallel regexps are numbered
386 starting at 1. */
387#define FIRST_MATCHING_REGEXP(state, dfa) (-(dfa).states[state].first_end)
388
389/* Entry points. */
390
391/* dfasyntax() takes three arguments; the first sets the syntax bits described
392 earlier in this file, the second sets the case-folding flag, and the
393 third specifies the line terminator. */
394extern void dfasyntax PARAMS ((reg_syntax_t, int, unsigned char));
395
396/* Compile the given string of the given length into the given struct dfa.
397 Final argument is a flag specifying whether to build a searching or an
398 exact matcher. */
399extern void dfacomp PARAMS ((char const *, size_t, struct dfa *, int));
400
401/* Execute the given struct dfa on the buffer of characters. The
402 last byte of the buffer must equal the end-of-line byte.
403 The final argument points to a flag that will
404 be set if further examination by a backtracking matcher is needed in
405 order to verify backreferencing; otherwise the flag will be cleared.
406 Returns (size_t) -1 if no match is found, or the offset of the first
407 character after the first & shortest matching string in the buffer. */
|