lib/silcutil/silcregex.h

   1 /*
   2
   3   silcregex.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2007 - 2008 Pekka Riikonen
   8
   9   This program is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation; version 2 of the License.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18 */
  19
  20 /****h* silcutil/Regex Interface
  21  *
  22  * DESCRIPTION
  23  *
  24  * SILC regular expression interface provides Unix and POSIX compliant
  25  * regular expression compilation and matching.
  26  *
  27  * The interface also provides many convenience functions to make the use
  28  * of regular expressions easier.  Especially the silc_regex allows very
  29  * simple way to match strings against regular expressions and get the
  30  * exact match or matches as a return.  The silc_subst provides simple and
  31  * familiar way to match and substitute strings (Sed syntax).
  32  *
  33  * The regex syntax follows POSIX regex syntax:
  34  *
  35  * Expressions:
  36  *   ^        Match start of line/string
  37  *              '^a' matches 'ab' but not 'ba'
  38  *   $        Match end of line/string
  39  *              'a$' matches 'ba' but not 'ab'
  40  *   .        Match any single character (except new line (\n))
  41  *              '.a' matches 'ba' but not 'a'
  42  *   +        Preceding item is matched one or more times
  43  *              'a+b' matches 'aaab' but not 'b'
  44  *   *        Preceding item is matched zero or more times
  45  *              'a*b' matches 'ab', 'aab' and 'b'
  46  *   ?        Preceding item is matched zero or one time
  47  *              'ca?b' matches 'cb' and 'cab' but not 'caab'
  48  *   |        Joins two expressions and matches either of them (OR)
  49  *              'foo|bar' matches 'foo' or 'bar'
  50  *   {n}      Preceding item is matched exactly n times (n can be 0-255)
  51  *              'a{2}' matches 'aa' but not 'aaa'
  52  *   {n,}     Preceding item is matched n or more times
  53  *              'a{2,} matches 'aa' and 'aaaa' but not 'a'
  54  *   {n,m}    Preceding item is matched at least n times and at most m times
  55  *              'a{2,4}' matches 'aa', 'aaa' and 'aaaa' but not 'aaaaa'
  56  *   [ ]      Match any single character in the character list inside [ ]
  57  *              '[0123]' matches only '0', '1', '2' or '3'
  58  *   [ - ]    Match any single character in the specified range
  59  *              '[0-5]' matches digits 0-5.
  60  *   [^ ]     Match any character not in the character list or range
  61  *              '[^09]]' matches any other character except '0' and '9'
  62  *   ( )      Subexpression, grouping
  63  *
  64  * Escaping (C-language style, '\' is written as '\\'):
  65  *   \\       Considers following character literal ('\\{' is '{')
  66  *   \\\\     Matches literal \
  67  *   \a       Matches bell (BEL)
  68  *   \t       Matches horizontal tab (HT)
  69  *   \n       Matches new line (LF)
  70  *   \v       Matches vertical tab (VT)
  71  *   \f       Matches form feed (FF)
  72  *   \r       Matches carriage ret (CR)
  73  *   \\<      Match null string at the start of a word
  74  *   \\>      Match null string at the end of a word
  75  *   \\b      Match null string at the edge of a wrod
  76  *   \\B      Match null string when not at the edge of a word
  77  *
  78  * EXAMPLE
  79  *
  80  * SilcRegexStruct reg;
  81  *
  82  * // Compile regular expression
  83  * if (!silc_regex_compile(&reg, "foo[0-9]*", 0))
  84  *   error;
  85  *
  86  * // Match string against the compiled regex
  87  * if (!silc_regex_match(&reg, "foo20", 0, NULL, 0))
  88  *   no_match;
  89  *
  90  * // Free the compiled regular expression
  91  * silc_regex_free(&reg);
  92  *
  93  * // Simple match
  94  * if (!silc_regex("foobar", "foo.", NULL))
  95  *   no_match;
  96  *
  97  * // Replace all foos with bar on all lines in the buffer
  98  * silc_subst(buffer, "s/foo/bar/g");
  99  *
 100  ***/
 101
 102 #ifndef SILCREGEX_H
 103 #define SILCREGEX_H
 104
 105 /****s* silcutil/SilcRegex
 106  *
 107  * NAME
 108  *
 109  *    typedef struct { ... } *SilcRegex, SilcRegexStruct;
 110  *
 111  * DESCRIPTION
 112  *
 113  *    The regular expression context.  This context is given as argument
 114  *    to all silc_regex_* functions.  It is usually statically allocated
 115  *    but can be dynamically allocated by silc_malloc.
 116  *
 117  ***/
 118 typedef struct SilcRegexObject {
 119   SilcStack rstack;            /* Stack for fast allocations */
 120   unsigned char *buffer;       /* compiled pattern */
 121   char *fastmap;               /* fastmap[ch] is true if ch can start pattern */
 122   char *translate;             /* translation to apply during comp/match */
 123   int allocated;               /* allocated size of compiled pattern */
 124   int used;                    /* actual length of compiled pattern */
 125   int num_registers;           /* number of registers used */
 126   char fastmap_accurate;       /* true if fastmap is valid */
 127   char can_be_null;            /* true if can match empty string */
 128   char uses_registers;         /* registers used and need to be initialized */
 129   char anchor;                 /* anchor: 0=none 1=begline 2=begbuf */
 130 } *SilcRegex, SilcRegexStruct;
 131
 132 /****s* silcutil/SilcRegexMatch
 133  *
 134  * NAME
 135  *
 136  *    typedef struct { ... } *SilcRegexMatch, SilcRegexMatchStruct;
 137  *
 138  * DESCRIPTION
 139  *
 140  *    The regular expression match context that provides information on the
 141  *    found match.  It provides the start offset and end offset of the
 142  *    found match.
 143  *
 144  * SOURCE
 145  */
 146 typedef struct SilcRegexMatchObject {
 147   int start;                   /* Start offset of region */
 148   int end;                     /* End offset of region */
 149 } *SilcRegexMatch, SilcRegexMatchStruct;
 150 /***/
 151
 152 /****d* silcutil/SilcRegexFlags
 153  *
 154  * NAME
 155  *
 156  *    typedef enum { ... } SilcRegexFlags;
 157  *
 158  * DESCRIPTION
 159  *
 160  *    Regular expression feature flags.
 161  *
 162  * SOURCE
 163  */
 164 typedef enum {
 165   SILC_REGEX_DEFAULT   = 0x00000000,
 166
 167   /* The following flags can be used with silc_regex_match */
 168
 169   /* The beginning-of-line (^) always fails to match.  This can be useful
 170      when beginning of a string should not be interpreted as the beginning
 171      of line. */
 172   SILC_REGEX_NOTBOL    = 0x00010000,
 173
 174   /* The end-of-line ($) always fails to match. */
 175   SILC_REGEX_NOTEOL    = 0x00020000,
 176 } SilcRegexFlags;
 177 /***/
 178
 179 /****f* silcutil/silc_regex_compile
 180  *
 181  * SYNOPSIS
 182  *
 183  *    SilcBool silc_regex_compile(SilcRegex regexp, const char *regex,
 184  *                                SilcRegexFlags flags);
 185  *
 186  * DESCRIPTION
 187  *
 188  *    Compiles the regular expression string `regex'.  The `regexp' is a
 189  *    pre-allocated regular expression context.  The `flags' define
 190  *    various feature flags.  This function must be called before the
 191  *    silc_regex_match can be used to find matches.
 192  *
 193  *    Returns TRUE after the compilation is completed.  Returns FALSE on
 194  *    error and sets silc_errno.
 195  *
 196  ***/
 197 SilcBool silc_regex_compile(SilcRegex regexp, const char *regex,
 198                             SilcRegexFlags flags);
 199
 200 /****f* silcutil/silc_regex_match
 201  *
 202  * SYNOPSIS
 203  *
 204  *    SilcBool silc_regex_match(SilcRegex regexp, const char *string,
 205  *                              SilcUInt32 string_len, SilcUInt32 num_match,
 206  *                              SilcRegexMatch match, SilcRegexFlags flags);
 207  *
 208  * DESCRIPTION
 209  *
 210  *    Finds one or more matches from the `string' using the pre-compiled
 211  *    regular expression `regexp'.  It must be compiled by calling the
 212  *    silc_regex_compile before calling this function.  The `flags' defines
 213  *    various feature flags.
 214  *
 215  *    If only one match is needed the `num_match' may be set to 0 and the
 216  *    `match' is set to NULL.  If multiple matches (substrings) are needed the
 217  *    `num_match' defines the size of the `match' array, where each of the
 218  *    matches (with parenthesized regular expression) will be stored.  The
 219  *    `match' provides information on where the match was found in `string',
 220  *    providing the start offset and end offset of the match.  Unused entires
 221  *    in the array will have -1 as the offset values.
 222  *
 223  *    Returns TRUE if the string matched the regular expression or FALSE
 224  *    if it did not match or error occurred.  The silc_errno will indicate
 225  *    the error.  The silc_errno is set to SILC_ERR_NOT_FOUND if the regular
 226  *    expression did not match.
 227  *
 228  * EXAMPLE
 229  *
 230  *    // Find first match (check if string matches)
 231  *    if (!silc_regex_match(&reg, "foo20", 5, 0, NULL, 0))
 232  *      no_match;
 233  *
 234  *    // Find multiple matches, one by one
 235  *    SilcRegexMatchStruct match;
 236  *
 237  *    while (silc_regex_match(&reg, string, len, 1, &match, 0)) {
 238  *      match_string = silc_memdup(string + match.start,
 239  *                                 match.end - match.start);
 240  *      string += match.end;
 241  *    }
 242  *
 243  *    // Parse URI into its components, available in the match[] array
 244  *    SilcRegexStruct reg;
 245  *    SilcRegexMatchStruct match[7];
 246  *
 247  *    silc_regex_compile(&reg, "^(([^:]+)://)?([^:/]+)(:([0-9]+))?(/.*)", 0);
 248  *    silc_regex_match(&reg, "http://example.com/page.html", len, 7, match, 0);
 249  *
 250  ***/
 251 SilcBool silc_regex_match(SilcRegex regexp, const char *string,
 252                           SilcUInt32 string_len, SilcUInt32 num_match,
 253                           SilcRegexMatch match, SilcRegexFlags flags);
 254
 255 /****f* silcutil/silc_regex_free
 256  *
 257  * SYNOPSIS
 258  *
 259  *    void silc_regex_free(SilcRegex regexp);
 260  *
 261  * DESCRIPTION
 262  *
 263  *    Free's the compiled regular expression context `regexp'.  This must
 264  *    be called even if `regexp' is statically allocated.  If the
 265  *    silc_regex_compile has been called this function must be called.
 266  *
 267  ***/
 268 void silc_regex_free(SilcRegex regexp);
 269
 270 /****f* silcutil/silc_regex
 271  *
 272  * SYNOPSIS
 273  *
 274  *    SilcBool silc_regex(const char *string, const char *regex,
 275  *                        SilcBuffer match, ...);
 276  *
 277  * DESCRIPTION
 278  *
 279  *    Matches the `string' to the regular expression `regex'.  Returns TRUE
 280  *    if the `string' matches the regular expression or FALSE if it does not
 281  *    match.  The silc_errno is also set to SILC_ERR_NOT_FOUND.
 282  *
 283  *    The first (whole) match is returned to `match' buffer if it is non-NULL.
 284  *    The variable argument list are buffers where multiple matches are
 285  *    returned in case of group (parenthesized) regular expression.  The caller
 286  *    needs to know how many pointers to provide in order to get all matches.
 287  *    If a particular group is optional, a buffer pointer still must be given
 288  *    as argument for it, however, if it did not match the returned buffer
 289  *    length is 0 and data pointer is NULL.
 290  *
 291  *    If `match' is non-NULL the variable argument list must be ended with
 292  *    NULL.  The data in the `match' and in any other buffer is from `string'
 293  *    and must not be freed by the caller.
 294  *
 295  * EXAMPLE
 296  *
 297  *    // Simple match
 298  *    if (!silc_regex("foobar", "foo.", NULL))
 299  *      no_match;
 300  *
 301  *    // Get the pointer to the first match
 302  *    if (!silc_regex("foobar", ".bar", &match, NULL))
 303  *      no_match;
 304  *
 305  *    // Group match
 306  *    SilcBufferStruct match, sub1, sub2;
 307  *
 308  *    if (!silc_regex("Hello World", "(H..).(o..)", &match, &sub1, &sub2, NULL))
 309  *      no_match;
 310  *
 311  ***/
 312 SilcBool silc_regex(const char *string, const char *regex,
 313                     SilcBuffer match, ...);
 314
 315 /****f* silcutil/silc_regex_buffer
 316  *
 317  * SYNOPSIS
 318  *
 319  *    SilcBool silc_regex_buffer(SilcBuffer buffer, const char *regex,
 320  *                               SilcBuffer match, ...);
 321  *
 322  * DESCRIPTION
 323  *
 324  *    Same as silc_regex but the string to match is in `buffer'.  Returns
 325  *    TRUE if the string matches and FALSE if it doesn't.  See examples and
 326  *    other information in silc_regex.  The `buffer' and `match' may be the
 327  *    same buffer.
 328  *
 329  ***/
 330 SilcBool silc_regex_buffer(SilcBuffer buffer, const char *regex,
 331                            SilcBuffer match, ...);
 332
 333 /****f* silcutil/silc_subst
 334  *
 335  * SYNOPSIS
 336  *
 337  *    SilcBool silc_subst(SilcBuffer buffer, const char *subst);
 338  *
 339  * DESCRIPTION
 340  *
 341  *    Regular expression matching and substitution in `buffer' according
 342  *    to the substitution expression `subst'.  This function provides
 343  *    Sed (Stream Editor) style substitution interface.  The `subst' may
 344  *    be of following formats:
 345  *
 346  *     's/REGEXP/REPLACEMENT/FLAGS'
 347  *
 348  *    Matches regular expression REGEXP in each line in the buffer and
 349  *    substitutes the match with REPLACEMENT.
 350  *
 351  *     'ADDRs/REGEXP/REPLACEMENT/FLAGS'
 352  *
 353  *    Selects lines in the buffer matching the address ADDR and matches the
 354  *    regular expression REGEXP in the line and substitutes the match with
 355  *    REPLACEMENT.
 356  *
 357  *    The ADDR may be of following format:
 358  *
 359  *     /REGEXP/       Matches only lines matching the regular expression
 360  *     NUMBER         Matches only the specified line number (1-n)
 361  *     $              Matches only the last line
 362  *
 363  *    The FLAGS may be of following format:
 364  *
 365  *     no FLAGS       Finds first match in the line and replaces that
 366  *     g              Finds and replaces all matches in the line
 367  *
 368  *    An '!' may precede the 's'.  In that case the ADDR is not matched.
 369  *
 370  *    Returns TRUE if the match and replacement was done, FALSE in case
 371  *    of error, and sets the silc_errno.
 372  *
 373  *    If you need to match and/or replace '/' characters, they must be
 374  *    escaped with '\' (C-style escaping for '\' is '\\').
 375  *
 376  *    If you need more versatile ways to modify the buffer you may consider
 377  *    using the SILC_STR_REGEX in SILC Buffer Format API directly.  This
 378  *    function only provides basic matching and substitution.
 379  *
 380  * EXAMPLE
 381  *
 382  *    // Replace all foos with bar on all lines in the buffer
 383  *    silc_subst(buffer, "s/foo/bar/g");
 384  *
 385  ***/
 386 SilcBool silc_subst(SilcBuffer buffer, const char *subst);
 387
 388 /* Backwards support */
 389 #define silc_string_regex_match(regex, string) silc_regex(string, regex, NULL)
 390
 391 #endif /* SILCREGEX_H */