gnu/usr.bin/grep/dfa.h

   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: src/gnu/usr.bin/grep/dfa.h,v 1.6 2000/01/04 03:25:39 obrien Exp $ */
  21 /* $DragonFly: src/gnu/usr.bin/grep/dfa.h,v 1.2 2003/06/17 04:25:45 dillon Exp $ */
  22
  23 /* FIXME:
  24    2.  We should not export so much of the DFA internals.
  25    In addition to clobbering modularity, we eat up valuable
  26    name space. */
  27
  28 # undef PARAMS
  29 #if __STDC__
  30 # ifndef _PTR_T
  31 # define _PTR_T
  32   typedef void * ptr_t;
  33 # endif
  34 # define PARAMS(x) x
  35 #else
  36 # ifndef _PTR_T
  37 # define _PTR_T
  38   typedef char * ptr_t;
  39 # endif
  40 # define PARAMS(x) ()
  41 #endif
  42
  43 /* Number of bits in an unsigned char. */
  44 #ifndef CHARBITS
  45 #define CHARBITS 8
  46 #endif
  47
  48 /* First integer value that is greater than any character code. */
  49 #define NOTCHAR (1 << CHARBITS)
  50
  51 /* INTBITS need not be exact, just a lower bound. */
  52 #ifndef INTBITS
  53 #define INTBITS (CHARBITS * sizeof (int))
  54 #endif
  55
  56 /* Number of ints required to hold a bit for every character. */
  57 #define CHARCLASS_INTS ((NOTCHAR + INTBITS - 1) / INTBITS)
  58
  59 /* Sets of unsigned characters are stored as bit vectors in arrays of ints. */
  60 typedef int charclass[CHARCLASS_INTS];
  61
  62 /* The regexp is parsed into an array of tokens in postfix form.  Some tokens
  63    are operators and others are terminal symbols.  Most (but not all) of these
  64    codes are returned by the lexical analyzer. */
  65
  66 typedef enum
  67 {
  68   END = -1,                     /* END is a terminal symbol that matches the
  69                                    end of input; any value of END or less in
  70                                    the parse tree is such a symbol.  Accepting
  71                                    states of the DFA are those that would have
  72                                    a transition on END. */
  73
  74   /* Ordinary character values are terminal symbols that match themselves. */
  75
  76   EMPTY = NOTCHAR,              /* EMPTY is a terminal symbol that matches
  77                                    the empty string. */
  78
  79   BACKREF,                      /* BACKREF is generated by \<digit>; it
  80                                    it not completely handled.  If the scanner
  81                                    detects a transition on backref, it returns
  82                                    a kind of "semi-success" indicating that
  83                                    the match will have to be verified with
  84                                    a backtracking matcher. */
  85
  86   BEGLINE,                      /* BEGLINE is a terminal symbol that matches
  87                                    the empty string if it is at the beginning
  88                                    of a line. */
  89
  90   ENDLINE,                      /* ENDLINE is a terminal symbol that matches
  91                                    the empty string if it is at the end of
  92                                    a line. */
  93
  94   BEGWORD,                      /* BEGWORD is a terminal symbol that matches
  95                                    the empty string if it is at the beginning
  96                                    of a word. */
  97
  98   ENDWORD,                      /* ENDWORD is a terminal symbol that matches
  99                                    the empty string if it is at the end of
 100                                    a word. */
 101
 102   LIMWORD,                      /* LIMWORD is a terminal symbol that matches
 103                                    the empty string if it is at the beginning
 104                                    or the end of a word. */
 105
 106   NOTLIMWORD,                   /* NOTLIMWORD is a terminal symbol that
 107                                    matches the empty string if it is not at
 108                                    the beginning or end of a word. */
 109
 110   QMARK,                        /* QMARK is an operator of one argument that
 111                                    matches zero or one occurences of its
 112                                    argument. */
 113
 114   STAR,                         /* STAR is an operator of one argument that
 115                                    matches the Kleene closure (zero or more
 116                                    occurrences) of its argument. */
 117
 118   PLUS,                         /* PLUS is an operator of one argument that
 119                                    matches the positive closure (one or more
 120                                    occurrences) of its argument. */
 121
 122   REPMN,                        /* REPMN is a lexical token corresponding
 123                                    to the {m,n} construct.  REPMN never
 124                                    appears in the compiled token vector. */
 125
 126   CAT,                          /* CAT is an operator of two arguments that
 127                                    matches the concatenation of its
 128                                    arguments.  CAT is never returned by the
 129                                    lexical analyzer. */
 130
 131   OR,                           /* OR is an operator of two arguments that
 132                                    matches either of its arguments. */
 133
 134   ORTOP,                        /* OR at the toplevel in the parse tree.
 135                                    This is used for a boyer-moore heuristic. */
 136
 137   LPAREN,                       /* LPAREN never appears in the parse tree,
 138                                    it is only a lexeme. */
 139
 140   RPAREN,                       /* RPAREN never appears in the parse tree. */
 141
 142   CSET                          /* CSET and (and any value greater) is a
 143                                    terminal symbol that matches any of a
 144                                    class of characters. */
 145 } token;
 146
 147 /* Sets are stored in an array in the compiled dfa; the index of the
 148    array corresponding to a given set token is given by SET_INDEX(t). */
 149 #define SET_INDEX(t) ((t) - CSET)
 150
 151 /* Sometimes characters can only be matched depending on the surrounding
 152    context.  Such context decisions depend on what the previous character
 153    was, and the value of the current (lookahead) character.  Context
 154    dependent constraints are encoded as 8 bit integers.  Each bit that
 155    is set indicates that the constraint succeeds in the corresponding
 156    context.
 157
 158    bit 7 - previous and current are newlines
 159    bit 6 - previous was newline, current isn't
 160    bit 5 - previous wasn't newline, current is
 161    bit 4 - neither previous nor current is a newline
 162    bit 3 - previous and current are word-constituents
 163    bit 2 - previous was word-constituent, current isn't
 164    bit 1 - previous wasn't word-constituent, current is
 165    bit 0 - neither previous nor current is word-constituent
 166
 167    Word-constituent characters are those that satisfy isalnum().
 168
 169    The macro SUCCEEDS_IN_CONTEXT determines whether a a given constraint
 170    succeeds in a particular context.  Prevn is true if the previous character
 171    was a newline, currn is true if the lookahead character is a newline.
 172    Prevl and currl similarly depend upon whether the previous and current
 173    characters are word-constituent letters. */
 174 #define MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn) \
 175   ((constraint) & 1 << (((prevn) ? 2 : 0) + ((currn) ? 1 : 0) + 4))
 176 #define MATCHES_LETTER_CONTEXT(constraint, prevl, currl) \
 177   ((constraint) & 1 << (((prevl) ? 2 : 0) + ((currl) ? 1 : 0)))
 178 #define SUCCEEDS_IN_CONTEXT(constraint, prevn, currn, prevl, currl) \
 179   (MATCHES_NEWLINE_CONTEXT(constraint, prevn, currn)                 \
 180    && MATCHES_LETTER_CONTEXT(constraint, prevl, currl))
 181
 182 /* The following macros give information about what a constraint depends on. */
 183 #define PREV_NEWLINE_DEPENDENT(constraint) \
 184   (((constraint) & 0xc0) >> 2 != ((constraint) & 0x30))
 185 #define PREV_LETTER_DEPENDENT(constraint) \
 186   (((constraint) & 0x0c) >> 2 != ((constraint) & 0x03))
 187
 188 /* Tokens that match the empty string subject to some constraint actually
 189    work by applying that constraint to determine what may follow them,
 190    taking into account what has gone before.  The following values are
 191    the constraints corresponding to the special tokens previously defined. */
 192 #define NO_CONSTRAINT 0xff
 193 #define BEGLINE_CONSTRAINT 0xcf
 194 #define ENDLINE_CONSTRAINT 0xaf
 195 #define BEGWORD_CONSTRAINT 0xf2
 196 #define ENDWORD_CONSTRAINT 0xf4
 197 #define LIMWORD_CONSTRAINT 0xf6
 198 #define NOTLIMWORD_CONSTRAINT 0xf9
 199
 200 /* States of the recognizer correspond to sets of positions in the parse
 201    tree, together with the constraints under which they may be matched.
 202    So a position is encoded as an index into the parse tree together with
 203    a constraint. */
 204 typedef struct
 205 {
 206   unsigned index;               /* Index into the parse array. */
 207   unsigned constraint;          /* Constraint for matching this position. */
 208 } position;
 209
 210 /* Sets of positions are stored as arrays. */
 211 typedef struct
 212 {
 213   position *elems;              /* Elements of this position set. */
 214   int nelem;                    /* Number of elements in this set. */
 215 } position_set;
 216
 217 /* A state of the dfa consists of a set of positions, some flags,
 218    and the token value of the lowest-numbered position of the state that
 219    contains an END token. */
 220 typedef struct
 221 {
 222   int hash;                     /* Hash of the positions of this state. */
 223   position_set elems;           /* Positions this state could match. */
 224   char newline;                 /* True if previous state matched newline. */
 225   char letter;                  /* True if previous state matched a letter. */
 226   char backref;                 /* True if this state matches a \<digit>. */
 227   unsigned char constraint;     /* Constraint for this state to accept. */
 228   int first_end;                /* Token value of the first END in elems. */
 229 } dfa_state;
 230
 231 /* Element of a list of strings, at least one of which is known to
 232    appear in any R.E. matching the DFA. */
 233 struct dfamust
 234 {
 235   int exact;
 236   char *must;
 237   struct dfamust *next;
 238 };
 239
 240 /* A compiled regular expression. */
 241 struct dfa
 242 {
 243   /* Stuff built by the scanner. */
 244   charclass *charclasses;       /* Array of character sets for CSET tokens. */
 245   int cindex;                   /* Index for adding new charclasses. */
 246   int calloc;                   /* Number of charclasses currently allocated. */
 247
 248   /* Stuff built by the parser. */
 249   token *tokens;                /* Postfix parse array. */
 250   int tindex;                   /* Index for adding new tokens. */
 251   int talloc;                   /* Number of tokens currently allocated. */
 252   int depth;                    /* Depth required of an evaluation stack
 253                                    used for depth-first traversal of the
 254                                    parse tree. */
 255   int nleaves;                  /* Number of leaves on the parse tree. */
 256   int nregexps;                 /* Count of parallel regexps being built
 257                                    with dfaparse(). */
 258
 259   /* Stuff owned by the state builder. */
 260   dfa_state *states;            /* States of the dfa. */
 261   int sindex;                   /* Index for adding new states. */
 262   int salloc;                   /* Number of states currently allocated. */
 263
 264   /* Stuff built by the structure analyzer. */
 265   position_set *follows;        /* Array of follow sets, indexed by position
 266                                    index.  The follow of a position is the set
 267                                    of positions containing characters that
 268                                    could conceivably follow a character
 269                                    matching the given position in a string
 270                                    matching the regexp.  Allocated to the
 271                                    maximum possible position index. */
 272   int searchflag;               /* True if we are supposed to build a searching
 273                                    as opposed to an exact matcher.  A searching
 274                                    matcher finds the first and shortest string
 275                                    matching a regexp anywhere in the buffer,
 276                                    whereas an exact matcher finds the longest
 277                                    string matching, but anchored to the
 278                                    beginning of the buffer. */
 279
 280   /* Stuff owned by the executor. */
 281   int tralloc;                  /* Number of transition tables that have
 282                                    slots so far. */
 283   int trcount;                  /* Number of transition tables that have
 284                                    actually been built. */
 285   int **trans;                  /* Transition tables for states that can
 286                                    never accept.  If the transitions for a
 287                                    state have not yet been computed, or the
 288                                    state could possibly accept, its entry in
 289                                    this table is NULL. */
 290   int **realtrans;              /* Trans always points to realtrans + 1; this
 291                                    is so trans[-1] can contain NULL. */
 292   int **fails;                  /* Transition tables after failing to accept
 293                                    on a state that potentially could do so. */
 294   int *success;                 /* Table of acceptance conditions used in
 295                                    dfaexec and computed in build_state. */
 296   int *newlines;                /* Transitions on newlines.  The entry for a
 297                                    newline in any transition table is always
 298                                    -1 so we can count lines without wasting
 299                                    too many cycles.  The transition for a
 300                                    newline is stored separately and handled
 301                                    as a special case.  Newline is also used
 302                                    as a sentinel at the end of the buffer. */
 303   struct dfamust *musts;        /* List of strings, at least one of which
 304                                    is known to appear in any r.e. matching
 305                                    the dfa. */
 306 };
 307
 308 /* Some macros for user access to dfa internals. */
 309
 310 /* ACCEPTING returns true if s could possibly be an accepting state of r. */
 311 #define ACCEPTING(s, r) ((r).states[s].constraint)
 312
 313 /* ACCEPTS_IN_CONTEXT returns true if the given state accepts in the
 314    specified context. */
 315 #define ACCEPTS_IN_CONTEXT(prevn, currn, prevl, currl, state, dfa) \
 316   SUCCEEDS_IN_CONTEXT((dfa).states[state].constraint,              \
 317                        prevn, currn, prevl, currl)
 318
 319 /* FIRST_MATCHING_REGEXP returns the index number of the first of parallel
 320    regexps that a given state could accept.  Parallel regexps are numbered
 321    starting at 1. */
 322 #define FIRST_MATCHING_REGEXP(state, dfa) (-(dfa).states[state].first_end)
 323
 324 /* Entry points. */
 325
 326 /* dfasyntax() takes three arguments; the first sets the syntax bits described
 327    earlier in this file, the second sets the case-folding flag, and the
 328    third specifies the line terminator. */
 329 extern void dfasyntax PARAMS ((reg_syntax_t, int, int));
 330
 331 /* Compile the given string of the given length into the given struct dfa.
 332    Final argument is a flag specifying whether to build a searching or an
 333    exact matcher. */
 334 extern void dfacomp PARAMS ((char *, size_t, struct dfa *, int));
 335
 336 /* Execute the given struct dfa on the buffer of characters.  The
 337    first char * points to the beginning, and the second points to the
 338    first character after the end of the buffer, which must be a writable
 339    place so a sentinel end-of-buffer marker can be stored there.  The
 340    second-to-last argument is a flag telling whether to allow newlines to
 341    be part of a string matching the regexp.  The next-to-last argument,
 342    if non-NULL, points to a place to increment every time we see a
 343    newline.  The final argument, if non-NULL, points to a flag that will
 344    be set if further examination by a backtracking matcher is needed in
 345    order to verify backreferencing; otherwise the flag will be cleared.
 346    Returns NULL if no match is found, or a pointer to the first
 347    character after the first & shortest matching string in the buffer. */
 348 extern char *dfaexec PARAMS ((struct dfa *, char *, char *, int, int *, int *));
 349
 350 /* Free the storage held by the components of a struct dfa. */
 351 extern void dfafree PARAMS ((struct dfa *));
 352
 353 /* Entry points for people who know what they're doing. */
 354
 355 /* Initialize the components of a struct dfa. */
 356 extern void dfainit PARAMS ((struct dfa *));
 357
 358 /* Incrementally parse a string of given length into a struct dfa. */
 359 extern void dfaparse PARAMS ((char *, size_t, struct dfa *));
 360
 361 /* Analyze a parsed regexp; second argument tells whether to build a searching
 362    or an exact matcher. */
 363 extern void dfaanalyze PARAMS ((struct dfa *, int));
 364
 365 /* Compute, for each possible character, the transitions out of a given
 366    state, storing them in an array of integers. */
 367 extern void dfastate PARAMS ((int, struct dfa *, int []));
 368
 369 /* Error handling. */
 370
 371 /* dfaerror() is called by the regexp routines whenever an error occurs.  It
 372    takes a single argument, a NUL-terminated string describing the error.
 373    The default dfaerror() prints the error message to stderr and exits.
 374    The user can provide a different dfafree() if so desired. */
 375 extern void dfaerror PARAMS ((const char *));