src/re9.h

   1 /*
   2  * The authors of this software are Rob Pike and Ken Thompson.
   3  * Copyright (c) 2002 by Lucent Technologies.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose without fee is hereby granted, provided that this entire notice
   7  * is included in all copies of any software which is or includes a copy
   8  * or modification of this software and in all copies of the supporting
   9  * documentation for such software.
  10  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  11  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY
  12  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  13  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  14  *
  15  * heavily modified by Ketmar // Vampire Avalon
  16  */
  17 #ifndef _REGEXP9_H_
  18 #define _REGEXP9_H_
  19
  20 #ifdef __cplusplus
  21 extern "C" {
  22 #endif
  23
  24 #include <stdint.h>
  25 #include <stdlib.h>
  26
  27 /*
  28  * A regular expression specifies a set of strings of characters. A
  29  * member of this set of strings is said to be matched by the regular
  30  * expression. In the following specification for regular expressions the
  31  * word `character' means any character (rune) but newline.
  32  *
  33  * The syntax for a regular expression e0 is
  34  *   e3:  literal | charclass | '.' | '^' | '$' | '(?:' e0 ')' | '(' e0 ')'
  35  *
  36  *   e2:  e3
  37  *     |  e2 REP
  38  *
  39  *   REP: '*' | '+' | '?'
  40  *
  41  *   e1:  e2
  42  *     |  e1 e2
  43  *
  44  *   e0:  e1
  45  *     |  e0 '|' e1
  46  *
  47  *
  48  * A literal is any non-metacharacter, or a metacharacter (one of .*+?[]()|\^$).
  49  *
  50  * A charclass is a nonempty string s bracketed [s] (or [^s]); it matches any
  51  * character in (or not in) s. A negated character class never matches newline.
  52  * A substring a-b, with a and b in ascending order, stands for the inclusive
  53  * range of characters between a and b. In s, the metacharacters '-', ']', an
  54  * initial '^' must be preceded by a '\'; other metacharacters have no special
  55  * meaning and may appear unescaped.
  56  *
  57  * A '^' matches the beginning of a line; '$' matches the end of the line.
  58  * A '.' matches any character.
  59  * A '\z' matches character with code 0 ('\0').
  60  * A '\d' matches digits ([0-9]).
  61  * A '\s' matches space ([\f\t\r\n\v ]).
  62  * A '\w' matches 'word character' ([0-9A-Za-z_]).
  63  * A '\b' matches 'word boundary'.
  64  * One can use 'negative metacharacters' too ('\Z', '\D', etc.).
  65  *
  66  * The REP operators match zero or more (*), one or more (+), zero or one (?),
  67  * instances respectively of the preceding regular expression e2.
  68  *
  69  * An alternative regular expression, e0|e1, matches either a match to e0 or a match to e1.
  70  *
  71  * A match to any part of a regular expression extends as far as possible without preventing
  72  * a match to the remainder of the regular expression.
  73  *
  74  * Remember that POSIX classes ([:alpha:], etc) covers only ASCII characters!
  75  */
  76
  77
  78 /* some cool defines:
  79  *
  80  * RE9_UNICODE_CASE
  81  *  define this to allow RE9_FLAG_CASEINSENS work with non-ascii characters
  82  *
  83  * RE9_DISABLE_NONGREEDY
  84  *  define this to disable non-greedy closures (the engine will be somewhat faster)
  85  *
  86  * RE9_DISABLE_POSIX_CLASSES
  87  *  disable parsing of posix classes like [:space:], [:digit:], etc.
  88  *
  89  * RE9_DISABLE_LEARNING
  90  *  disable regexp 'learning' in compiler
  91  */
  92
  93
  94 /* maximum is 127, vm opcode limits this */
  95 enum { RE9_SUBEXP_MAX = 16 };
  96
  97
  98 #if defined(__GNUC__) && __GNUC__ >= 3
  99 # define REGEXP9_ATTR_PURE  __attribute__((pure))
 100 #else
 101 # define REGEXP9_ATTR_PURE
 102 #endif
 103
 104
 105 /* subexpression matches */
 106 typedef struct {
 107   const char *sp;
 108   const char *ep;
 109 } re9_sub_t;
 110
 111
 112 /* program definition */
 113 typedef struct re9_prog_s re9_prog_t;
 114
 115
 116 enum {
 117   RE9_FLAG_NONE = 0,
 118   RE9_FLAG_NONUTF8 = 0x01, /* for both compile and execute */
 119   RE9_FLAG_ANYDOT  = 0x02, /* '.' matches newline too; for both compile and execute */
 120   /* only for compiler */
 121   RE9_FLAG_LITERAL = 0x10,
 122   RE9_FLAG_NONGREEDY = 0x20, /* invert default repetition mode */
 123   RE9_FLAG_CASEINSENS = 0x40, /* only for ASCII */
 124   /* only for interpreter */
 125   RE9_FLAG_MT0_RANGE = 0x100, /* use match[0].sp and match[0].ep as string start and end */
 126   /* */
 127   RE9_FLAG_DUMPPRG = 0x1000
 128 };
 129
 130
 131 /*
 132  * re9_compile() compiles a regular expression and returns a pointer to the generated description.
 133  * re9_compile() returns 0 for an illegal expression or other failure.
 134  * Compiler is thread-safe.
 135  * errmsg can be NULL; if *errmsg is not NULL, it SHOULD NOT be free()d or modified!
 136  */
 137 extern re9_prog_t *re9_compile (const char *s, int flags, const char **errmsg);
 138
 139 extern re9_prog_t *re9_compile_ex (const char *s, const char *eol, int flags, const char **errmsg);
 140
 141 /* return number of captures in this regexp; 0th capture is always full match */
 142 extern int re9_nsub (const re9_prog_t *p);
 143
 144 /*
 145  * free compiled regular expression
 146  */
 147 extern void re9_free (re9_prog_t *p);
 148
 149 /* re9_execute() matches a null-terminated string against the compiled regular expression in prog.
 150  * If it matches, regexec returns 1 and fills in the array match with character pointers to the
 151  * substrings of string that correspond to the parenthesized subexpressions of exp: match[i].sp
 152  * points to the beginning and match[i].ep points just beyond the end of the ith substring.
 153  * (Subexpression i begins at the ith left parenthesis, counting from 1.) Pointers in match[0]
 154  * pick out the substring that corresponds to the whole regular expression.
 155  * If match[0].sp is nonzero on entry, regexec starts matching at that point within string.
 156  * If match[0].ep is nonzero on entry, the last character matched is the one preceding that point.
 157  * Unused elements of match are filled with zeros. Matches involving and are extended as far as
 158  * possible. The number of array elements in match is given by msize.
 159  * mp can be NULL and ms should be 0 in this case.
 160  * re9_execute() returns 0 if string is not matched.
 161  * Executor is thread-safe, one program can be used in multiple threads simultaneously.
 162  */
 163 /* progp: program to run
 164  * bol: string to run machine on
 165  * mp: subexpression elements (can be NULL)
 166  * ms: number of elements at mp (should be 0 if mp is NULL)
 167  */
 168 extern int re9_execute (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms);
 169
 170 /* executor can eat up to maxmem memory */
 171 extern int re9_execute_ex (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms, size_t maxmem);
 172
 173
 174 /* 'prepared for execution' program */
 175 typedef struct re9_prog_prepared_s re9_prog_prepared_t;
 176
 177
 178 /* 'prepare' program -- allocate some memory, etc.
 179  * this can be used to avoid excessive malloc()s.
 180  * return NULL on error.
 181  */
 182 extern re9_prog_prepared_t *re9_prepare (const re9_prog_t *progp);
 183
 184 /* executor can eat up to maxmem memory */
 185 extern re9_prog_prepared_t *re9_prepare_ex (const re9_prog_t *progp, size_t maxmem);
 186
 187 /* execute 'prepared' program */
 188 extern int re9_prepared_execute (re9_prog_prepared_t *pp, int flags, const char *bol, re9_sub_t *mp, int ms);
 189
 190 /* free 'prepared' program */
 191 extern void re9_prepared_free (re9_prog_prepared_t *pp);
 192
 193
 194 /* re9_sub() places in dp a substitution instance of sp in the context of the last regexec
 195  * performed using match. Each instance of '\n', where n is a digit, is replaced by the string
 196  * delimited by match[n].sp and match[n].ep. Each instance of is replaced by the string
 197  * delimited by match[0].sp and match[0].ep. The substitution will always be null terminated
 198  * and trimmed to fit into dlen bytes.
 199  * Function will return number of bytes needed to successfully insert everything (including trailing 0).
 200  * Use '\{num}' to insert 10th and bigger match.
 201  * Use '\z' to insert character with code 0.
 202  */
 203 /* sp: source string
 204  * dp: destination string
 205  * dlen: destination string size
 206  * mp: subexpression elements
 207  * ms: number of elements at mp
 208  */
 209 extern int re9_sub (char *dp, size_t dlen, const char *sp, const re9_sub_t *mp, int ms) REGEXP9_ATTR_PURE;
 210
 211
 212 #ifdef __cplusplus
 213 }
 214 #endif
 215 #endif