lib/dfa.h

   1 /* dfa.h - declarations for GNU deterministic regexp compiler
   2    Copyright (C) 1988, 1998, 2007, 2009-2024 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 #ifndef DFA_H_
  22 #define DFA_H_
  23
  24 /* This file uses _Noreturn, _GL_ATTRIBUTE_DEALLOC, _GL_ATTRIBUTE_MALLOC,
  25    _GL_ATTRIBUTE_PURE, _GL_ATTRIBUTE_RETURNS_NONNULL.  */
  26 #if !_GL_CONFIG_H_INCLUDED
  27  #error "Please include config.h first."
  28 #endif
  29
  30 #include "idx.h"
  31 #include <regex.h>
  32 #include <stddef.h>
  33 #include <stdlib.h>
  34
  35 #ifdef __cplusplus
  36 extern "C" {
  37 #endif
  38
  39 struct localeinfo; /* See localeinfo.h.  */
  40
  41 /* Element of a list of strings, at least one of which is known to
  42    appear in any R.E. matching the DFA. */
  43 struct dfamust
  44 {
  45   bool exact;
  46   bool begline;
  47   bool endline;
  48   char must[FLEXIBLE_ARRAY_MEMBER];
  49 };
  50
  51 /* The dfa structure. It is completely opaque. */
  52 struct dfa;
  53
  54 /* Needed when Gnulib is not used.  */
  55 #ifndef _GL_ATTRIBUTE_MALLOC
  56 # define _GL_ATTRIBUTE_MALLOC
  57 # define _GL_ATTRIBUTE_DEALLOC(f, i)
  58 # define _GL_ATTRIBUTE_DEALLOC_FREE
  59 # define _GL_ATTRIBUTE_RETURNS_NONNULL
  60 #endif
  61
  62 /* Entry points. */
  63
  64 /* Allocate a struct dfa.  The struct dfa is completely opaque.
  65    It should be initialized via dfasyntax or dfacopysyntax before other use.
  66    The returned pointer should be passed directly to free() after
  67    calling dfafree() on it. */
  68 extern struct dfa *dfaalloc (void)
  69   _GL_ATTRIBUTE_MALLOC _GL_ATTRIBUTE_DEALLOC_FREE
  70   _GL_ATTRIBUTE_RETURNS_NONNULL;
  71
  72 /* DFA options that can be ORed together, for dfasyntax's 4th arg.  */
  73 enum
  74   {
  75     /* ^ and $ match only the start and end of data, and do not match
  76        end-of-line within data.  This is always false for grep, but
  77        possibly true for other apps.  */
  78     DFA_ANCHOR = 1 << 0,
  79
  80     /* '\0' in data is end-of-line, instead of the traditional '\n'.  */
  81     DFA_EOL_NUL = 1 << 1,
  82
  83     /* Treat [:alpha:] etc. as an error at the top level, instead of
  84        merely a warning.  */
  85     DFA_CONFUSING_BRACKETS_ERROR = 1 << 2,
  86
  87     /* Warn about stray backslashes before ordinary characters other
  88        than ] and } which are special because even though POSIX
  89        says \] and \} have undefined interpretation, platforms
  90        reliably ignore those stray backlashes and warning about them
  91        would likely cause more trouble than it's worth.  */
  92     DFA_STRAY_BACKSLASH_WARN = 1 << 3,
  93
  94     /* Warn about * appearing out of context at the start of an
  95        expression or subexpression.  */
  96     DFA_STAR_WARN = 1 << 4,
  97
  98     /* Warn about +, ?, {...} appearing out of context at the start of
  99        an expression or subexpression.  */
 100     DFA_PLUS_WARN = 1 << 5,
 101   };
 102
 103 /* Initialize or reinitialize a DFA.  The arguments are:
 104    1. The DFA to operate on.
 105    2. Information about the current locale.
 106    3. Syntax bits described in regex.h.
 107    4. Additional DFA options described above.  */
 108 extern void dfasyntax (struct dfa *, struct localeinfo const *,
 109                        reg_syntax_t, int);
 110
 111 /* Initialize or reinitialize a DFA from an already-initialized DFA.  */
 112 extern void dfacopysyntax (struct dfa *, struct dfa const *);
 113
 114 /* Parse the given string of given length into the given struct dfa.  */
 115 extern void dfaparse (char const *, idx_t, struct dfa *);
 116
 117 struct dfamust;
 118
 119 /* Free the storage held by the components of a struct dfamust. */
 120 extern void dfamustfree (struct dfamust *);
 121
 122 /* Allocate and return a struct dfamust from a struct dfa that was
 123    initialized by dfaparse and not yet given to dfacomp.  */
 124 extern struct dfamust *dfamust (struct dfa const *)
 125   _GL_ATTRIBUTE_DEALLOC (dfamustfree, 1);
 126
 127 /* Compile the given string of the given length into the given struct dfa.
 128    The last argument says whether to build a searching or an exact matcher.
 129    A null first argument means the struct dfa has already been
 130    initialized by dfaparse; the second argument is ignored.  */
 131 extern void dfacomp (char const *, idx_t, struct dfa *, bool);
 132
 133 /* Search through a buffer looking for a match to the given struct dfa.
 134    Find the first occurrence of a string matching the regexp in the
 135    buffer, and the shortest possible version thereof.  Return a pointer to
 136    the first character after the match, or NULL if none is found.  BEGIN
 137    points to the beginning of the buffer, and END points to the first byte
 138    after its end.  Note however that we store a sentinel byte (usually
 139    newline) in *END, so the actual buffer must be one byte longer.
 140    When ALLOW_NL is true, newlines may appear in the matching string.
 141    If COUNT is non-NULL, increment *COUNT once for each newline processed.
 142    Finally, if BACKREF is non-NULL set *BACKREF to indicate whether we
 143    encountered a back-reference.  The caller can use this to decide
 144    whether to fall back on a backtracking matcher.  */
 145 extern char *dfaexec (struct dfa *d, char const *begin, char *end,
 146                       bool allow_nl, idx_t *count, bool *backref);
 147
 148 /* Return a superset for D.  The superset matches everything that D
 149    matches, along with some other strings (though the latter should be
 150    rare, for efficiency reasons).  Return a null pointer if no useful
 151    superset is available.  */
 152 extern struct dfa *dfasuperset (struct dfa const *d) _GL_ATTRIBUTE_PURE;
 153
 154 /* The DFA is likely to be fast.  */
 155 extern bool dfaisfast (struct dfa const *) _GL_ATTRIBUTE_PURE;
 156
 157 /* Return true if every construct in D is supported by this DFA matcher.  */
 158 extern bool dfasupported (struct dfa const *) _GL_ATTRIBUTE_PURE;
 159
 160 /* Free the storage held by the components of a struct dfa. */
 161 extern void dfafree (struct dfa *);
 162
 163 /* Error handling. */
 164
 165 /* dfawarn() is called by the regexp routines whenever a regex is compiled
 166    that likely doesn't do what the user wanted.  It takes a single
 167    argument, a NUL-terminated string describing the situation.  The user
 168    must supply a dfawarn.  */
 169 extern void dfawarn (const char *);
 170
 171 /* dfaerror() is called by the regexp routines whenever an error occurs.  It
 172    takes a single argument, a NUL-terminated string describing the error.
 173    The user must supply a dfaerror.  */
 174 extern _Noreturn void dfaerror (const char *);
 175
 176 #ifdef __cplusplus
 177 }
 178 #endif
 179
 180 #endif /* dfa.h */