contrib/grep/src/dfa.h

   1 /* dfa.h - declarations for GNU deterministic regexp compiler
   2    Copyright (C) 1988, 1998, 2007, 2009-2014 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 3, 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.,
  17    51 Franklin Street - Fifth Floor, Boston, MA  02110-1301, USA */
  18
  19 /* Written June, 1988 by Mike Haertel */
  20
  21 #include <regex.h>
  22 #include <stdbool.h>
  23 #include <stddef.h>
  24
  25 /* Element of a list of strings, at least one of which is known to
  26    appear in any R.E. matching the DFA. */
  27 struct dfamust
  28 {
  29   bool exact;
  30   bool begline;
  31   bool endline;
  32   char *must;
  33   struct dfamust *next;
  34 };
  35
  36 /* The dfa structure. It is completely opaque. */
  37 struct dfa;
  38
  39 /* Entry points. */
  40
  41 /* Allocate a struct dfa.  The struct dfa is completely opaque.
  42    The returned pointer should be passed directly to free() after
  43    calling dfafree() on it. */
  44 extern struct dfa *dfaalloc (void);
  45
  46 /* Return the dfamusts associated with a dfa. */
  47 extern struct dfamust *dfamusts (struct dfa const *);
  48
  49 /* dfasyntax() takes three arguments; the first sets the syntax bits described
  50    earlier in this file, the second sets the case-folding flag, and the
  51    third specifies the line terminator. */
  52 extern void dfasyntax (reg_syntax_t, int, unsigned char);
  53
  54 /* Compile the given string of the given length into the given struct dfa.
  55    Final argument is a flag specifying whether to build a searching or an
  56    exact matcher. */
  57 extern void dfacomp (char const *, size_t, struct dfa *, int);
  58
  59 /* Search through a buffer looking for a match to the given struct dfa.
  60    Find the first occurrence of a string matching the regexp in the
  61    buffer, and the shortest possible version thereof.  Return a pointer to
  62    the first character after the match, or NULL if none is found.  BEGIN
  63    points to the beginning of the buffer, and END points to the first byte
  64    after its end.  Note however that we store a sentinel byte (usually
  65    newline) in *END, so the actual buffer must be one byte longer.
  66    When NEWLINE is nonzero, newlines may appear in the matching string.
  67    If COUNT is non-NULL, increment *COUNT once for each newline processed.
  68    Finally, if BACKREF is non-NULL set *BACKREF to indicate whether we
  69    encountered a back-reference (1) or not (0).  The caller may use this
  70    to decide whether to fall back on a backtracking matcher. */
  71 extern char *dfaexec (struct dfa *d, char const *begin, char *end,
  72                       int newline, size_t *count, int *backref);
  73
  74 /* Return a superset for D.  The superset matches everything that D
  75    matches, along with some other strings (though the latter should be
  76    rare, for efficiency reasons).  Return a null pointer if no useful
  77    superset is available.  */
  78 extern struct dfa *dfasuperset (struct dfa const *d) _GL_ATTRIBUTE_PURE;
  79
  80 /* The DFA is likely to be fast.  */
  81 extern bool dfaisfast (struct dfa const *) _GL_ATTRIBUTE_PURE;
  82
  83 /* Free the storage held by the components of a struct dfa. */
  84 extern void dfafree (struct dfa *);
  85
  86 /* Entry points for people who know what they're doing. */
  87
  88 /* Initialize the components of a struct dfa. */
  89 extern void dfainit (struct dfa *);
  90
  91 /* Incrementally parse a string of given length into a struct dfa. */
  92 extern void dfaparse (char const *, size_t, struct dfa *);
  93
  94 /* Analyze a parsed regexp; second argument tells whether to build a searching
  95    or an exact matcher. */
  96 extern void dfaanalyze (struct dfa *, int);
  97
  98 /* Compute, for each possible character, the transitions out of a given
  99    state, storing them in an array of integers. */
 100 extern void dfastate (ptrdiff_t, struct dfa *, ptrdiff_t []);
 101
 102 /* Error handling. */
 103
 104 /* dfawarn() is called by the regexp routines whenever a regex is compiled
 105    that likely doesn't do what the user wanted.  It takes a single
 106    argument, a NUL-terminated string describing the situation.  The user
 107    must supply a dfawarn.  */
 108 extern void dfawarn (const char *);
 109
 110 /* dfaerror() is called by the regexp routines whenever an error occurs.  It
 111    takes a single argument, a NUL-terminated string describing the error.
 112    The user must supply a dfaerror.  */
 113 extern _Noreturn void dfaerror (const char *);
 114
 115 extern int using_utf8 (void);