1 /* $NetBSD: dfa.h,v 1.1.1.1 2016/01/10 21:36:21 christos Exp $ */ 2 3 /* dfa.h - declarations for GNU deterministic regexp compiler 4 Copyright (C) 1988, 1998 Free Software Foundation, Inc. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2, or (at your option) 9 any later version. 10 11 This program 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 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ 19 20 /* Written June, 1988 by Mike Haertel */ 21 22 /* FIXME: 23 2. We should not export so much of the DFA internals. 24 In addition to clobbering modularity, we eat up valuable 25 name space. */ 26 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. */ 65 typedef 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 71 typedef 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. */ 224 typedef 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. */ 231 typedef 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. */ 240 typedef 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. */ 259 struct 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. */ 269 struct 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. */ 287 struct 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. */ 394 extern 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. */ 399 extern 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. */ 408 extern size_t dfaexec PARAMS ((struct dfa *, char const *, size_t, int *)); 409 410 /* Free the storage held by the components of a struct dfa. */ 411 extern void dfafree PARAMS ((struct dfa *)); 412 413 /* Entry points for people who know what they're doing. */ 414 415 /* Initialize the components of a struct dfa. */ 416 extern void dfainit PARAMS ((struct dfa *)); 417 418 /* Incrementally parse a string of given length into a struct dfa. */ 419 extern void dfaparse PARAMS ((char const *, size_t, struct dfa *)); 420 421 /* Analyze a parsed regexp; second argument tells whether to build a searching 422 or an exact matcher. */ 423 extern void dfaanalyze PARAMS ((struct dfa *, int)); 424 425 /* Compute, for each possible character, the transitions out of a given 426 state, storing them in an array of integers. */ 427 extern void dfastate PARAMS ((int, struct dfa *, int [])); 428 429 /* Error handling. */ 430 431 /* dfaerror() is called by the regexp routines whenever an error occurs. It 432 takes a single argument, a NUL-terminated string describing the error. 433 The user must supply a dfaerror. */ 434 extern void dfaerror PARAMS ((const char *)); 435