contrib/awk/dfa.h

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