lib/dfa.h

   1 /* dfa.h - declarations for GNU deterministic regexp compiler
   2    Copyright (C) 1988, 1998, 2007, 2009-2016 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 #if 3 <= __GNUC__
  26 # define _GL_ATTRIBUTE_MALLOC __attribute__ ((__malloc__))
  27 #else
  28 # define _GL_ATTRIBUTE_MALLOC
  29 #endif
  30
  31 struct localeinfo; /* See localeinfo.h.  */
  32
  33 /* Element of a list of strings, at least one of which is known to
  34    appear in any R.E. matching the DFA. */
  35 struct dfamust
  36 {
  37   bool exact;
  38   bool begline;
  39   bool endline;
  40   char *must;
  41 };
  42
  43 /* The dfa structure. It is completely opaque. */
  44 struct dfa;
  45
  46 /* Entry points. */
  47
  48 /* Allocate a struct dfa.  The struct dfa is completely opaque.
  49    The returned pointer should be passed directly to free() after
  50    calling dfafree() on it. */
  51 extern struct dfa *dfaalloc (void) _GL_ATTRIBUTE_MALLOC;
  52
  53 /* DFA options that can be ORed together, for dfasyntax's 4th arg.  */
  54 enum
  55   {
  56     /* ^ and $ match only the start and end of data, and do not match
  57        end-of-line within data.  This is always false for grep, but
  58        possibly true for other apps.  */
  59     DFA_ANCHOR = 1 << 0,
  60
  61     /* Ignore case while matching.  */
  62     DFA_CASE_FOLD = 1 << 1,
  63
  64     /* '\0' in data is end-of-line, instead of the traditional '\n'.  */
  65     DFA_EOL_NUL = 1 << 2
  66   };
  67
  68 /* Initialize or reinitialize a DFA.  This must be called before
  69    any of the routines below.  The arguments are:
  70    1. The DFA to operate on.
  71    2. Information about the current locale.
  72    3. Syntax bits described in regex.h.
  73    4. Additional DFA options described above.  */
  74 extern void dfasyntax (struct dfa *, struct localeinfo const *,
  75                        reg_syntax_t, int);
  76
  77 /* Build and return the struct dfamust from the given struct dfa. */
  78 extern struct dfamust *dfamust (struct dfa const *);
  79
  80 /* Free the storage held by the components of a struct dfamust. */
  81 extern void dfamustfree (struct dfamust *);
  82
  83 /* Compile the given string of the given length into the given struct dfa.
  84    Final argument is a flag specifying whether to build a searching or an
  85    exact matcher. */
  86 extern void dfacomp (char const *, size_t, struct dfa *, bool);
  87
  88 /* Search through a buffer looking for a match to the given struct dfa.
  89    Find the first occurrence of a string matching the regexp in the
  90    buffer, and the shortest possible version thereof.  Return a pointer to
  91    the first character after the match, or NULL if none is found.  BEGIN
  92    points to the beginning of the buffer, and END points to the first byte
  93    after its end.  Note however that we store a sentinel byte (usually
  94    newline) in *END, so the actual buffer must be one byte longer.
  95    When ALLOW_NL is true, newlines may appear in the matching string.
  96    If COUNT is non-NULL, increment *COUNT once for each newline processed.
  97    Finally, if BACKREF is non-NULL set *BACKREF to indicate whether we
  98    encountered a back-reference.  The caller can use this to decide
  99    whether to fall back on a backtracking matcher.  */
 100 extern char *dfaexec (struct dfa *d, char const *begin, char *end,
 101                       bool allow_nl, size_t *count, bool *backref);
 102
 103 /* Return a superset for D.  The superset matches everything that D
 104    matches, along with some other strings (though the latter should be
 105    rare, for efficiency reasons).  Return a null pointer if no useful
 106    superset is available.  */
 107 extern struct dfa *dfasuperset (struct dfa const *d) _GL_ATTRIBUTE_PURE;
 108
 109 /* The DFA is likely to be fast.  */
 110 extern bool dfaisfast (struct dfa const *) _GL_ATTRIBUTE_PURE;
 111
 112 /* Free the storage held by the components of a struct dfa. */
 113 extern void dfafree (struct dfa *);
 114
 115 /* Error handling. */
 116
 117 /* dfawarn() is called by the regexp routines whenever a regex is compiled
 118    that likely doesn't do what the user wanted.  It takes a single
 119    argument, a NUL-terminated string describing the situation.  The user
 120    must supply a dfawarn.  */
 121 extern void dfawarn (const char *);
 122
 123 /* dfaerror() is called by the regexp routines whenever an error occurs.  It
 124    takes a single argument, a NUL-terminated string describing the error.
 125    The user must supply a dfaerror.  */
 126 extern _Noreturn void dfaerror (const char *);