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 #ifdef REGEXP9_DEBUG_MEMSIZE
  94 extern int re9_memused;
  95 #endif
  96
  97
  98 /* maximum is 127, vm opcode limits this */
  99 enum { RE9_SUBEXP_MAX = 16 };
 100
 101
 102 #if defined(__GNUC__) && __GNUC__ >= 3
 103 # define REGEXP9_ATTR_PURE  __attribute__((pure))
 104 #else
 105 # define REGEXP9_ATTR_PURE
 106 #endif
 107
 108
 109 /* subexpression matches */
 110 typedef struct {
 111   const char *sp;
 112   const char *ep;
 113 } re9_sub_t;
 114
 115
 116 /* program definition */
 117 typedef struct re9_prog_s re9_prog_t;
 118
 119
 120 enum {
 121   RE9_FLAG_NONE = 0,
 122   RE9_FLAG_NONUTF8 = 0x01, /* for both compile and execute */
 123   RE9_FLAG_ANYDOT  = 0x02, /* '.' matches newline too; for both compile and execute */
 124   /* only for compiler */
 125   RE9_FLAG_LITERAL = 0x10,
 126   RE9_FLAG_NONGREEDY = 0x20, /* invert default repetition mode */
 127   RE9_FLAG_CASEINSENS = 0x40, /* only for ASCII */
 128   /* only for interpreter */
 129   RE9_FLAG_MT0_RANGE = 0x100, /* use match[0].sp and match[0].ep as string start and end */
 130   /* */
 131   RE9_FLAG_DUMPPRG = 0x1000
 132 };
 133
 134
 135 /*
 136  * re9_compile() compiles a regular expression and returns a pointer to the generated description.
 137  * re9_compile() returns 0 for an illegal expression or other failure.
 138  * Compiler is thread-safe.
 139  * errmsg can be NULL; if *errmsg is not NULL, it SHOULD NOT be free()d or modified!
 140  */
 141 extern re9_prog_t *re9_compile (const char *s, int flags, const char **errmsg);
 142
 143 extern re9_prog_t *re9_compile_ex (const char *s, const char *eol, int flags, const char **errmsg);
 144
 145 /* return number of captures in this regexp; 0th capture is always full match */
 146 extern int re9_nsub (const re9_prog_t *p);
 147
 148 /*
 149  * free compiled regular expression
 150  */
 151 extern void re9_free (re9_prog_t *p);
 152
 153 /* re9_execute() matches a null-terminated string against the compiled regular expression in prog.
 154  * If it matches, regexec returns 1 and fills in the array match with character pointers to the
 155  * substrings of string that correspond to the parenthesized subexpressions of exp: match[i].sp
 156  * points to the beginning and match[i].ep points just beyond the end of the ith substring.
 157  * (Subexpression i begins at the ith left parenthesis, counting from 1.) Pointers in match[0]
 158  * pick out the substring that corresponds to the whole regular expression.
 159  * If match[0].sp is nonzero on entry, regexec starts matching at that point within string.
 160  * If match[0].ep is nonzero on entry, the last character matched is the one preceding that point.
 161  * Unused elements of match are filled with zeros. Matches involving and are extended as far as
 162  * possible. The number of array elements in match is given by msize.
 163  * mp can be NULL and ms should be 0 in this case.
 164  * re9_execute() returns 0 if string is not matched.
 165  * Executor is thread-safe, one program can be used in multiple threads simultaneously.
 166  */
 167 /* progp: program to run
 168  * bol: string to run machine on
 169  * mp: subexpression elements (can be NULL)
 170  * ms: number of elements at mp (should be 0 if mp is NULL)
 171  */
 172 extern int re9_execute (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms);
 173
 174 /* executor can eat up to maxmem memory */
 175 extern int re9_execute_ex (const re9_prog_t *progp, int flags, const char *bol, re9_sub_t *mp, int ms, size_t maxmem);
 176
 177
 178 /* 'prepared for execution' program */
 179 typedef struct re9_prog_prepared_s re9_prog_prepared_t;
 180
 181
 182 /* 'prepare' program -- allocate some memory, etc.
 183  * this can be used to avoid excessive malloc()s.
 184  * return NULL on error.
 185  */
 186 extern re9_prog_prepared_t *re9_prepare (const re9_prog_t *progp);
 187
 188 /* executor can eat up to maxmem memory */
 189 extern re9_prog_prepared_t *re9_prepare_ex (const re9_prog_t *progp, size_t maxmem);
 190
 191 /* execute 'prepared' program */
 192 extern int re9_prepared_execute (re9_prog_prepared_t *pp, int flags, const char *bol, re9_sub_t *mp, int ms);
 193
 194 /* free 'prepared' program */
 195 extern void re9_prepared_free (re9_prog_prepared_t *pp);
 196
 197
 198 /* re9_sub() places in dp a substitution instance of sp in the context of the last regexec
 199  * performed using match. Each instance of '\n', where n is a digit, is replaced by the string
 200  * delimited by match[n].sp and match[n].ep. Each instance of is replaced by the string
 201  * delimited by match[0].sp and match[0].ep. The substitution will always be null terminated
 202  * and trimmed to fit into dlen bytes.
 203  * Function will return number of bytes needed to successfully insert everything (including trailing 0).
 204  * Use '\{num}' to insert 10th and bigger match.
 205  * Use '\z' to insert character with code 0.
 206  */
 207 /* sp: source string
 208  * dp: destination string
 209  * dlen: destination string size
 210  * mp: subexpression elements
 211  * ms: number of elements at mp
 212  */
 213 extern int re9_sub (char *dp, size_t dlen, const char *sp, const re9_sub_t *mp, int ms) REGEXP9_ATTR_PURE;
 214
 215
 216 #ifdef __cplusplus
 217 }
 218 #endif
 219 #endif