1/* dfa.h - declarations for GNU deterministic regexp compiler
2   Copyright (C) 1988, 1998 Free Software Foundation, Inc.
3
4   This program is free software; you can redistribute it and/or modify
5   it under the terms of the GNU General Public License as published by
6   the Free Software Foundation; either version 2, or (at your option)
7   any later version.
8
9   This program is distributed in the hope that it will be useful,
10   but WITHOUT ANY WARRANTY; without even the implied warranty of
11   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12   GNU General Public License for more details.
13
14   You should have received a copy of the GNU General Public License
15   along with this program; if not, write to the Free Software
16   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA */
17
18/* Written June, 1988 by Mike Haertel */
19
20/* $FreeBSD$ */
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. */
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. */
408extern size_t dfaexec PARAMS ((struct dfa *, char const *, size_t, int *));
409
410/* Free the storage held by the components of a struct dfa. */
411extern 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. */
416extern void dfainit PARAMS ((struct dfa *));
417
418/* Incrementally parse a string of given length into a struct dfa. */
419extern 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. */
423extern 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. */
427extern 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.  */
434extern void dfaerror PARAMS ((const char *));
435