dfa.h revision 131576
1235289Sadrian/* dfa.h - declarations for GNU deterministic regexp compiler 2330449Seadler Copyright (C) 1988, 1998 Free Software Foundation, Inc. 3330449Seadler 4235289Sadrian This program is free software; you can redistribute it and/or modify 5235289Sadrian it under the terms of the GNU General Public License as published by 6235289Sadrian the Free Software Foundation; either version 2, or (at your option) 7235289Sadrian any later version. 8235289Sadrian 9235289Sadrian This program is distributed in the hope that it will be useful, 10235289Sadrian but WITHOUT ANY WARRANTY; without even the implied warranty of 11235289Sadrian MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12235289Sadrian GNU General Public License for more details. 13235289Sadrian 14235289Sadrian You should have received a copy of the GNU General Public License 15235289Sadrian along with this program; if not, write to the Free Software 16235289Sadrian Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ 17235289Sadrian 18235289Sadrian/* Written June, 1988 by Mike Haertel */ 19235289Sadrian 20235289Sadrian/* $FreeBSD: head/gnu/usr.bin/grep/dfa.h 131576 2004-07-04 16:16:59Z tjr $ */ 21235289Sadrian 22235289Sadrian/* FIXME: 23235289Sadrian 2. We should not export so much of the DFA internals. 24235289Sadrian In addition to clobbering modularity, we eat up valuable 25235289Sadrian name space. */ 26235289Sadrian 27235289Sadrian#include "mbcache.h" 28235289Sadrian 29235289Sadrian#ifdef __STDC__ 30235289Sadrian# ifndef _PTR_T 31235289Sadrian# define _PTR_T 32235289Sadrian typedef void * ptr_t; 33235289Sadrian# endif 34235289Sadrian#else 35235289Sadrian# ifndef _PTR_T 36235289Sadrian# define _PTR_T 37235289Sadrian typedef char * ptr_t; 38235289Sadrian# endif 39235289Sadrian#endif 40235289Sadrian 41235289Sadrian#ifdef PARAMS 42235289Sadrian# undef PARAMS 43235289Sadrian#endif 44235289Sadrian#if PROTOTYPES 45235289Sadrian# define PARAMS(x) x 46235289Sadrian#else 47235289Sadrian# define PARAMS(x) () 48235289Sadrian#endif 49235289Sadrian 50235289Sadrian/* Number of bits in an unsigned char. */ 51235289Sadrian#ifndef CHARBITS 52235289Sadrian#define CHARBITS 8 53235289Sadrian#endif 54235289Sadrian 55235289Sadrian/* First integer value that is greater than any character code. */ 56235289Sadrian#define NOTCHAR (1 << CHARBITS) 57235289Sadrian 58235289Sadrian/* INTBITS need not be exact, just a lower bound. */ 59235289Sadrian#ifndef INTBITS 60235289Sadrian#define INTBITS (CHARBITS * sizeof (int)) 61235289Sadrian#endif 62235289Sadrian 63250382Sadrian/* Number of ints required to hold a bit for every character. */ 64235289Sadrian#define CHARCLASS_INTS ((NOTCHAR + INTBITS - 1) / INTBITS) 65235289Sadrian 66235289Sadrian/* Sets of unsigned characters are stored as bit vectors in arrays of ints. */ 67235289Sadriantypedef int charclass[CHARCLASS_INTS]; 68235289Sadrian 69235289Sadrian/* The regexp is parsed into an array of tokens in postfix form. Some tokens 70235289Sadrian are operators and others are terminal symbols. Most (but not all) of these 71235289Sadrian codes are returned by the lexical analyzer. */ 72235289Sadrian 73235289Sadriantypedef enum 74250382Sadrian{ 75235289Sadrian END = -1, /* END is a terminal symbol that matches the 76235289Sadrian end of input; any value of END or less in 77235289Sadrian the parse tree is such a symbol. Accepting 78235289Sadrian states of the DFA are those that would have 79235289Sadrian a transition on END. */ 80235289Sadrian 81235289Sadrian /* Ordinary character values are terminal symbols that match themselves. */ 82235289Sadrian 83235289Sadrian EMPTY = NOTCHAR, /* EMPTY is a terminal symbol that matches 84235289Sadrian the empty string. */ 85235289Sadrian 86241720Sed BACKREF, /* BACKREF is generated by \<digit>; it 87235289Sadrian it not completely handled. If the scanner 88235289Sadrian detects a transition on backref, it returns 89250382Sadrian a kind of "semi-success" indicating that 90250382Sadrian the match will have to be verified with 91250382Sadrian a backtracking matcher. */ 92250382Sadrian 93250382Sadrian BEGLINE, /* BEGLINE is a terminal symbol that matches 94250382Sadrian the empty string if it is at the beginning 95250382Sadrian of a line. */ 96250382Sadrian 97250382Sadrian ENDLINE, /* ENDLINE is a terminal symbol that matches 98235289Sadrian the empty string if it is at the end of 99250382Sadrian a line. */ 100250382Sadrian 101250382Sadrian BEGWORD, /* BEGWORD is a terminal symbol that matches 102250382Sadrian the empty string if it is at the beginning 103250382Sadrian of a word. */ 104250382Sadrian 105250382Sadrian ENDWORD, /* ENDWORD is a terminal symbol that matches 106250382Sadrian the empty string if it is at the end of 107250382Sadrian a word. */ 108250382Sadrian 109250382Sadrian LIMWORD, /* LIMWORD is a terminal symbol that matches 110250382Sadrian the empty string if it is at the beginning 111250382Sadrian or the end of a word. */ 112250382Sadrian 113250382Sadrian NOTLIMWORD, /* NOTLIMWORD is a terminal symbol that 114250382Sadrian matches the empty string if it is not at 115250382Sadrian the beginning or end of a word. */ 116250382Sadrian 117250382Sadrian QMARK, /* QMARK is an operator of one argument that 118250382Sadrian matches zero or one occurences of its 119250382Sadrian argument. */ 120250382Sadrian 121235289Sadrian STAR, /* STAR is an operator of one argument that 122235289Sadrian matches the Kleene closure (zero or more 123235289Sadrian occurrences) of its argument. */ 124235289Sadrian 125235289Sadrian PLUS, /* PLUS is an operator of one argument that 126235289Sadrian matches the positive closure (one or more 127235289Sadrian occurrences) of its argument. */ 128235289Sadrian 129235289Sadrian REPMN, /* REPMN is a lexical token corresponding 130235289Sadrian to the {m,n} construct. REPMN never 131235289Sadrian appears in the compiled token vector. */ 132235289Sadrian 133235289Sadrian CAT, /* CAT is an operator of two arguments that 134235289Sadrian matches the concatenation of its 135235289Sadrian arguments. CAT is never returned by the 136235289Sadrian lexical analyzer. */ 137235289Sadrian 138235289Sadrian OR, /* OR is an operator of two arguments that 139235289Sadrian matches either of its arguments. */ 140235289Sadrian 141235289Sadrian ORTOP, /* OR at the toplevel in the parse tree. 142235289Sadrian This is used for a boyer-moore heuristic. */ 143235289Sadrian 144235289Sadrian LPAREN, /* LPAREN never appears in the parse tree, 145235289Sadrian it is only a lexeme. */ 146235289Sadrian 147235289Sadrian RPAREN, /* RPAREN never appears in the parse tree. */ 148235289Sadrian 149235289Sadrian CRANGE, /* CRANGE never appears in the parse tree. 150235289Sadrian It stands for a character range that can 151235289Sadrian match a string of one or more characters. 152235289Sadrian For example, [a-z] can match "ch" in 153235289Sadrian a Spanish locale. */ 154235289Sadrian 155235289Sadrian#ifdef MBS_SUPPORT 156235289Sadrian ANYCHAR, /* ANYCHAR is a terminal symbol that matches 157235289Sadrian any multibyte(or singlebyte) characters. 158235289Sadrian It is used only if MB_CUR_MAX > 1. */ 159235289Sadrian 160235289Sadrian MBCSET, /* MBCSET is similar to CSET, but for 161235289Sadrian multibyte characters. */ 162235289Sadrian#endif /* MBS_SUPPORT */ 163235289Sadrian 164235289Sadrian CSET /* CSET and (and any value greater) is a 165235289Sadrian terminal symbol that matches any of a 166235289Sadrian class of characters. */ 167235289Sadrian} token; 168249752Sadrian 169235289Sadrian/* Sets are stored in an array in the compiled dfa; the index of the 170235289Sadrian array corresponding to a given set token is given by SET_INDEX(t). */ 171235289Sadrian#define SET_INDEX(t) ((t) - CSET) 172235289Sadrian 173235289Sadrian/* Sometimes characters can only be matched depending on the surrounding 174249752Sadrian context. Such context decisions depend on what the previous character 175249752Sadrian was, and the value of the current (lookahead) character. Context 176249752Sadrian dependent constraints are encoded as 8 bit integers. Each bit that 177249747Sadrian is set indicates that the constraint succeeds in the corresponding 178235289Sadrian context. 179235289Sadrian 180235289Sadrian bit 7 - previous and current are newlines 181249752Sadrian bit 6 - previous was newline, current isn't 182235289Sadrian bit 5 - previous wasn't newline, current is 183235289Sadrian bit 4 - neither previous nor current is a newline 184235289Sadrian bit 3 - previous and current are word-constituents 185235289Sadrian bit 2 - previous was word-constituent, current isn't 186235289Sadrian bit 1 - previous wasn't word-constituent, current is 187250382Sadrian bit 0 - neither previous nor current is word-constituent 188250382Sadrian 189250382Sadrian Word-constituent characters are those that satisfy isalnum(). 190250382Sadrian 191250382Sadrian The macro SUCCEEDS_IN_CONTEXT determines whether a a given constraint 192250382Sadrian succeeds in a particular context. Prevn is true if the previous character 193250382Sadrian was a newline, currn is true if the lookahead character is a newline. 194250382Sadrian Prevl and currl similarly depend upon whether the previous and current 195250382Sadrian characters are word-constituent letters. */ 196250382Sadrian#define MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \ 197250382Sadrian ((constraint) & 1 << (((prevn) ? 2 : 0) + ((currn) ? 1 : 0) + 4)) 198250382Sadrian#define MATCHES_LETTER_CONTEXT(constraint, prevl, currl) \ 199250382Sadrian ((constraint) & 1 << (((prevl) ? 2 : 0) + ((currl) ? 1 : 0))) 200250382Sadrian#define SUCCEEDS_IN_CONTEXT(constraint, prevn, currn, prevl, currl) \ 201250382Sadrian (MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \ 202250382Sadrian && MATCHES_LETTER_CONTEXT(constraint, prevl, currl)) 203250382Sadrian 204250382Sadrian/* The following macros give information about what a constraint depends on. */ 205250382Sadrian#define PREV_NEWLINE_DEPENDENT(constraint) \ 206250382Sadrian (((constraint) & 0xc0) >> 2 != ((constraint) & 0x30)) 207250382Sadrian#define PREV_LETTER_DEPENDENT(constraint) \ 208250382Sadrian (((constraint) & 0x0c) >> 2 != ((constraint) & 0x03)) 209250382Sadrian 210250382Sadrian/* Tokens that match the empty string subject to some constraint actually 211250382Sadrian work by applying that constraint to determine what may follow them, 212250382Sadrian taking into account what has gone before. The following values are 213250382Sadrian the constraints corresponding to the special tokens previously defined. */ 214250382Sadrian#define NO_CONSTRAINT 0xff 215250382Sadrian#define BEGLINE_CONSTRAINT 0xcf 216250382Sadrian#define ENDLINE_CONSTRAINT 0xaf 217250382Sadrian#define BEGWORD_CONSTRAINT 0xf2 218250382Sadrian#define ENDWORD_CONSTRAINT 0xf4 219250382Sadrian#define LIMWORD_CONSTRAINT 0xf6 220250382Sadrian#define NOTLIMWORD_CONSTRAINT 0xf9 221250382Sadrian 222250382Sadrian/* States of the recognizer correspond to sets of positions in the parse 223250382Sadrian tree, together with the constraints under which they may be matched. 224250382Sadrian So a position is encoded as an index into the parse tree together with 225250382Sadrian a constraint. */ 226250382Sadriantypedef struct 227250382Sadrian{ 228235289Sadrian unsigned index; /* Index into the parse array. */ 229235289Sadrian unsigned constraint; /* Constraint for matching this position. */ 230235289Sadrian} position; 231235289Sadrian 232235289Sadrian/* Sets of positions are stored as arrays. */ 233235289Sadriantypedef struct 234235289Sadrian{ 235235289Sadrian position *elems; /* Elements of this position set. */ 236235289Sadrian int nelem; /* Number of elements in this set. */ 237235289Sadrian} position_set; 238235289Sadrian 239235289Sadrian/* A state of the dfa consists of a set of positions, some flags, 240268301Sloos and the token value of the lowest-numbered position of the state that 241268301Sloos contains an END token. */ 242235289Sadriantypedef struct 243235289Sadrian{ 244235289Sadrian int hash; /* Hash of the positions of this state. */ 245235289Sadrian position_set elems; /* Positions this state could match. */ 246235289Sadrian char newline; /* True if previous state matched newline. */ 247235289Sadrian char letter; /* True if previous state matched a letter. */ 248235289Sadrian char backref; /* True if this state matches a \<digit>. */ 249235289Sadrian unsigned char constraint; /* Constraint for this state to accept. */ 250235289Sadrian int first_end; /* Token value of the first END in elems. */ 251235289Sadrian#ifdef MBS_SUPPORT 252235289Sadrian position_set mbps; /* Positions which can match multibyte 253235289Sadrian characters. e.g. period. 254235289Sadrian These staff are used only if 255235289Sadrian MB_CUR_MAX > 1. */ 256235289Sadrian#endif 257235289Sadrian} dfa_state; 258235289Sadrian 259235289Sadrian/* Element of a list of strings, at least one of which is known to 260235289Sadrian appear in any R.E. matching the DFA. */ 261235289Sadrianstruct dfamust 262235289Sadrian{ 263235289Sadrian int exact; 264235289Sadrian char *must; 265235289Sadrian struct dfamust *next; 266235289Sadrian}; 267235289Sadrian 268235289Sadrian#ifdef MBS_SUPPORT 269235289Sadrian/* A bracket operator. 270235289Sadrian e.g. [a-c], [[:alpha:]], etc. */ 271235289Sadrianstruct mb_char_classes 272235289Sadrian{ 273235289Sadrian int invert; 274235289Sadrian wchar_t *chars; /* Normal characters. */ 275235289Sadrian int nchars; 276235289Sadrian wctype_t *ch_classes; /* Character classes. */ 277235289Sadrian int nch_classes; 278235289Sadrian wchar_t *range_sts; /* Range characters (start of the range). */ 279308891Sloos wchar_t *range_ends; /* Range characters (end of the range). */ 280308891Sloos int nranges; 281235289Sadrian char **equivs; /* Equivalent classes. */ 282255730Shiren int nequivs; 283235289Sadrian char **coll_elems; 284235289Sadrian int ncoll_elems; /* Collating elements. */ 285235289Sadrian}; 286235289Sadrian#endif 287235289Sadrian 288235289Sadrian/* A compiled regular expression. */ 289235289Sadrianstruct dfa 290235289Sadrian{ 291235289Sadrian /* Stuff built by the scanner. */ 292235289Sadrian charclass *charclasses; /* Array of character sets for CSET tokens. */ 293235289Sadrian int cindex; /* Index for adding new charclasses. */ 294235289Sadrian int calloc; /* Number of charclasses currently allocated. */ 295235289Sadrian 296235289Sadrian /* Stuff built by the parser. */ 297235289Sadrian token *tokens; /* Postfix parse array. */ 298235289Sadrian int tindex; /* Index for adding new tokens. */ 299308891Sloos int talloc; /* Number of tokens currently allocated. */ 300235289Sadrian int depth; /* Depth required of an evaluation stack 301308891Sloos used for depth-first traversal of the 302235289Sadrian parse tree. */ 303235289Sadrian int nleaves; /* Number of leaves on the parse tree. */ 304235289Sadrian int nregexps; /* Count of parallel regexps being built 305235289Sadrian with dfaparse(). */ 306235289Sadrian#ifdef MBS_SUPPORT 307235289Sadrian /* These stuff are used only if MB_CUR_MAX > 1 or multibyte environments. */ 308235289Sadrian int nmultibyte_prop; 309235289Sadrian int *multibyte_prop; 310235289Sadrian /* The value of multibyte_prop[i] is defined by following rule. 311235289Sadrian if tokens[i] < NOTCHAR 312235289Sadrian bit 1 : tokens[i] is a singlebyte character, or the last-byte of 313235289Sadrian a multibyte character. 314235289Sadrian bit 0 : tokens[i] is a singlebyte character, or the 1st-byte of 315235289Sadrian a multibyte character. 316235289Sadrian if tokens[i] = MBCSET 317235289Sadrian ("the index of mbcsets correspnd to this operator" << 2) + 3 318235289Sadrian 319235289Sadrian e.g. 320235289Sadrian tokens 321235289Sadrian = 'single_byte_a', 'multi_byte_A', single_byte_b' 322235289Sadrian = 'sb_a', 'mb_A(1st byte)', 'mb_A(2nd byte)', 'mb_A(3rd byte)', 'sb_b' 323235289Sadrian multibyte_prop 324235289Sadrian = 3 , 1 , 0 , 2 , 3 325235289Sadrian */ 326235289Sadrian 327235289Sadrian /* Array of the bracket expressoin in the DFA. */ 328235289Sadrian struct mb_char_classes *mbcsets; 329235289Sadrian int nmbcsets; 330235289Sadrian int mbcsets_alloc; 331235289Sadrian#endif 332235289Sadrian 333235289Sadrian /* Stuff owned by the state builder. */ 334235289Sadrian dfa_state *states; /* States of the dfa. */ 335235289Sadrian int sindex; /* Index for adding new states. */ 336235289Sadrian int salloc; /* Number of states currently allocated. */ 337235289Sadrian 338235289Sadrian /* Stuff built by the structure analyzer. */ 339235289Sadrian position_set *follows; /* Array of follow sets, indexed by position 340235289Sadrian index. The follow of a position is the set 341235289Sadrian of positions containing characters that 342235289Sadrian could conceivably follow a character 343235289Sadrian matching the given position in a string 344235289Sadrian matching the regexp. Allocated to the 345235289Sadrian maximum possible position index. */ 346235289Sadrian int searchflag; /* True if we are supposed to build a searching 347235289Sadrian as opposed to an exact matcher. A searching 348235289Sadrian matcher finds the first and shortest string 349235289Sadrian matching a regexp anywhere in the buffer, 350235289Sadrian whereas an exact matcher finds the longest 351235289Sadrian string matching, but anchored to the 352235289Sadrian beginning of the buffer. */ 353235289Sadrian 354235289Sadrian /* Stuff owned by the executor. */ 355235289Sadrian int tralloc; /* Number of transition tables that have 356235289Sadrian slots so far. */ 357235289Sadrian int trcount; /* Number of transition tables that have 358235289Sadrian actually been built. */ 359235289Sadrian int **trans; /* Transition tables for states that can 360235289Sadrian never accept. If the transitions for a 361235289Sadrian state have not yet been computed, or the 362235289Sadrian state could possibly accept, its entry in 363235289Sadrian this table is NULL. */ 364235289Sadrian int **realtrans; /* Trans always points to realtrans + 1; this 365235289Sadrian is so trans[-1] can contain NULL. */ 366235289Sadrian int **fails; /* Transition tables after failing to accept 367235289Sadrian on a state that potentially could do so. */ 368235289Sadrian int *success; /* Table of acceptance conditions used in 369235289Sadrian dfaexec and computed in build_state. */ 370235289Sadrian struct dfamust *musts; /* List of strings, at least one of which 371235289Sadrian is known to appear in any r.e. matching 372250382Sadrian the dfa. */ 373250382Sadrian}; 374250382Sadrian 375250382Sadrian/* Some macros for user access to dfa internals. */ 376250382Sadrian 377250382Sadrian/* ACCEPTING returns true if s could possibly be an accepting state of r. */ 378250382Sadrian#define ACCEPTING(s, r) ((r).states[s].constraint) 379250382Sadrian 380250382Sadrian/* ACCEPTS_IN_CONTEXT returns true if the given state accepts in the 381250382Sadrian specified context. */ 382250382Sadrian#define ACCEPTS_IN_CONTEXT(prevn, currn, prevl, currl, state, dfa) \ 383250382Sadrian SUCCEEDS_IN_CONTEXT((dfa).states[state].constraint, \ 384250382Sadrian prevn, currn, prevl, currl) 385250382Sadrian 386250382Sadrian/* FIRST_MATCHING_REGEXP returns the index number of the first of parallel 387250382Sadrian regexps that a given state could accept. Parallel regexps are numbered 388250382Sadrian starting at 1. */ 389250382Sadrian#define FIRST_MATCHING_REGEXP(state, dfa) (-(dfa).states[state].first_end) 390250382Sadrian 391250382Sadrian/* Entry points. */ 392250382Sadrian 393250382Sadrian/* dfasyntax() takes three arguments; the first sets the syntax bits described 394250382Sadrian earlier in this file, the second sets the case-folding flag, and the 395250382Sadrian third specifies the line terminator. */ 396250382Sadrianextern void dfasyntax PARAMS ((reg_syntax_t, int, unsigned char)); 397250382Sadrian 398250382Sadrian/* Compile the given string of the given length into the given struct dfa. 399250382Sadrian Final argument is a flag specifying whether to build a searching or an 400250382Sadrian exact matcher. */ 401250382Sadrianextern void dfacomp PARAMS ((char const *, size_t, struct dfa *, int)); 402250382Sadrian 403250382Sadrian/* Execute the given struct dfa on the buffer of characters. The 404250382Sadrian last byte of the buffer must equal the end-of-line byte. 405250382Sadrian The final argument points to a flag that will 406250382Sadrian be set if further examination by a backtracking matcher is needed in 407250382Sadrian order to verify backreferencing; otherwise the flag will be cleared. 408250382Sadrian Returns (size_t) -1 if no match is found, or the offset of the first 409250382Sadrian character after the first & shortest matching string in the buffer. */ 410250382Sadrianextern size_t dfaexec PARAMS ((struct dfa *, char const *, size_t, int *, 411250382Sadrian struct mb_cache *)); 412250382Sadrian 413250382Sadrian/* Free the storage held by the components of a struct dfa. */ 414250382Sadrianextern void dfafree PARAMS ((struct dfa *)); 415250382Sadrian 416250382Sadrian/* Entry points for people who know what they're doing. */ 417250382Sadrian 418250382Sadrian/* Initialize the components of a struct dfa. */ 419250382Sadrianextern void dfainit PARAMS ((struct dfa *)); 420250382Sadrian 421250382Sadrian/* Incrementally parse a string of given length into a struct dfa. */ 422250382Sadrianextern void dfaparse PARAMS ((char const *, size_t, struct dfa *)); 423250382Sadrian 424250382Sadrian/* Analyze a parsed regexp; second argument tells whether to build a searching 425250382Sadrian or an exact matcher. */ 426250382Sadrianextern void dfaanalyze PARAMS ((struct dfa *, int)); 427250382Sadrian 428250382Sadrian/* Compute, for each possible character, the transitions out of a given 429250382Sadrian state, storing them in an array of integers. */ 430250382Sadrianextern void dfastate PARAMS ((int, struct dfa *, int [])); 431250382Sadrian 432235289Sadrian/* Error handling. */ 433235289Sadrian 434235289Sadrian/* dfaerror() is called by the regexp routines whenever an error occurs. It 435235289Sadrian takes a single argument, a NUL-terminated string describing the error. 436235289Sadrian The user must supply a dfaerror. */ 437235289Sadrianextern void dfaerror PARAMS ((const char *)); 438235289Sadrian