lib/regex.c

   1 /*
   2  *      Sherlock Library -- Interface to Regular Expression Libraries
   3  *
   4  *      (c) 1997--2004 Martin Mares <mj@ucw.cz>
   5  *      (c) 2001 Robert Spalek <robert@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #include "lib/lib.h"
  12 #include "lib/chartype.h"
  13 #include "lib/hashfunc.h"
  14
  15 #include <stdio.h>
  16 #include <string.h>
  17 #include <stdlib.h>
  18
  19 #if !defined(CONFIG_PCRE) && !defined(CONFIG_POSIX_RE)
  20
  21 /* BSD regular expression library */
  22
  23 #include <regex.h>
  24
  25 #define INITIAL_MEM 1024                /* Initial space allocated for each pattern */
  26 #define CHAR_SET_SIZE 256               /* How many characters in the character set.  */
  27
  28 struct regex {
  29   struct re_pattern_buffer buf;
  30   struct re_registers regs;             /* Must not change between re_match() calls */
  31   int len_cache;
  32 };
  33
  34 regex *
  35 rx_compile(byte *p, int icase)
  36 {
  37   regex *r = xmalloc_zero(sizeof(regex));
  38   const char *msg;
  39
  40   r->buf.buffer = xmalloc(INITIAL_MEM);
  41   r->buf.allocated = INITIAL_MEM;
  42   if (icase)
  43     {
  44       unsigned i;
  45       r->buf.translate = xmalloc (CHAR_SET_SIZE);
  46       /* Map uppercase characters to corresponding lowercase ones.  */
  47       for (i = 0; i < CHAR_SET_SIZE; i++)
  48         r->buf.translate[i] = Cupcase(i);
  49     }
  50   else
  51     r->buf.translate = NULL;
  52   re_set_syntax(RE_SYNTAX_POSIX_EXTENDED);
  53   msg = re_compile_pattern(p, strlen(p), &r->buf);
  54   if (!msg)
  55     return r;
  56   die("Error parsing pattern `%s': %s", p, msg);
  57 }
  58
  59 void
  60 rx_free(regex *r)
  61 {
  62   xfree(r->buf.buffer);
  63   if (r->buf.translate)
  64     xfree(r->buf.translate);
  65   xfree(r);
  66 }
  67
  68 int
  69 rx_match(regex *r, byte *s)
  70 {
  71   int len = strlen(s);
  72
  73   r->len_cache = len;
  74   if (re_match(&r->buf, s, len, 0, &r->regs) < 0)
  75     return 0;
  76   if (r->regs.start[0] || r->regs.end[0] != len) /* XXX: Why regex doesn't enforce implicit "^...$" ? */
  77     return 0;
  78   return 1;
  79 }
  80
  81 int
  82 rx_subst(regex *r, byte *by, byte *src, byte *dest, uns destlen)
  83 {
  84   byte *end = dest + destlen - 1;
  85
  86   if (!rx_match(r, src))
  87     return 0;
  88
  89   while (*by)
  90     {
  91       if (*by == '\\')
  92         {
  93           by++;
  94           if (*by >= '0' && *by <= '9') /* \0 gets replaced by entire pattern */
  95             {
  96               uns j = *by++ - '0';
  97               if (j < r->regs.num_regs)
  98                 {
  99                   byte *s = src + r->regs.start[j];
 100                   uns i = r->regs.end[j] - r->regs.start[j];
 101                   if (r->regs.start[j] > r->len_cache || r->regs.end[j] > r->len_cache)
 102                     return -1;
 103                   if (dest + i >= end)
 104                     return -1;
 105                   memcpy(dest, s, i);
 106                   dest += i;
 107                   continue;
 108                 }
 109             }
 110         }
 111       if (dest < end)
 112         *dest++ = *by++;
 113       else
 114         return -1;
 115     }
 116   *dest = 0;
 117   return 1;
 118 }
 119
 120 #elif defined(CONFIG_POSIX_RE)
 121
 122 /* POSIX regular expression library */
 123
 124 #include <regex.h>
 125
 126 struct regex {
 127   regex_t rx;
 128   regmatch_t matches[10];
 129 };
 130
 131 regex *
 132 rx_compile(byte *p, int icase)
 133 {
 134   regex *r = xmalloc_zero(sizeof(regex));
 135
 136   int err = regcomp(&r->rx, p, REG_EXTENDED | (icase ? REG_ICASE : 0));
 137   if (err)
 138     {
 139       byte msg[256];
 140       regerror(err, &r->rx, msg, sizeof(msg)-1);
 141       /* regfree(&r->rx) not needed */
 142       die("Error parsing regular expression `%s': %s", p, msg);
 143     }
 144   return r;
 145 }
 146
 147 void
 148 rx_free(regex *r)
 149 {
 150   regfree(&r->rx);
 151   xfree(r);
 152 }
 153
 154 int
 155 rx_match(regex *r, byte *s)
 156 {
 157   int err = regexec(&r->rx, s, 10, r->matches, 0);
 158   if (!err)
 159     {
 160       /* regexec doesn't support anchored expressions, so we have to check ourselves that the full string is matched */
 161       return !(r->matches[0].rm_so || s[r->matches[0].rm_eo]);
 162     }
 163   else if (err == REG_NOMATCH)
 164     return 0;
 165   else if (err == REG_ESPACE)
 166     die("Regex matching ran out of memory");
 167   else
 168     die("Regex matching failed with unknown error %d", err);
 169 }
 170
 171 int
 172 rx_subst(regex *r, byte *by, byte *src, byte *dest, uns destlen)
 173 {
 174   byte *end = dest + destlen - 1;
 175
 176   if (!rx_match(r, src))
 177     return 0;
 178
 179   while (*by)
 180     {
 181       if (*by == '\\')
 182         {
 183           by++;
 184           if (*by >= '0' && *by <= '9') /* \0 gets replaced by entire pattern */
 185             {
 186               uns j = *by++ - '0';
 187               if (j <= r->rx.re_nsub && r->matches[j].rm_so >= 0)
 188                 {
 189                   byte *s = src + r->matches[j].rm_so;
 190                   uns i = r->matches[j].rm_eo - r->matches[j].rm_so;
 191                   if (dest + i >= end)
 192                     return -1;
 193                   memcpy(dest, s, i);
 194                   dest += i;
 195                   continue;
 196                 }
 197             }
 198         }
 199       if (dest < end)
 200         *dest++ = *by++;
 201       else
 202         return -1;
 203     }
 204   *dest = 0;
 205   return 1;
 206 }
 207
 208 #else
 209
 210 /* PCRE library */
 211
 212 #include <pcre.h>
 213
 214 struct regex {
 215   pcre *rx;
 216   pcre_extra *extra;
 217   uns match_array_size;
 218   uns real_matches;
 219   int matches[0];                       /* (max_matches+1) pairs (pos,len) plus some workspace */
 220 };
 221
 222 regex *
 223 rx_compile(byte *p, int icase)
 224 {
 225   const char *err;
 226   int errpos, match_array_size, eno;
 227
 228   pcre *rx = pcre_compile(p, PCRE_ANCHORED | PCRE_EXTRA | (icase ? PCRE_CASELESS : 0), &err, &errpos, NULL);
 229   if (!rx)
 230     die("Error parsing regular expression `%s': %s at position %d", p, err, errpos);
 231   eno = pcre_fullinfo(rx, NULL, PCRE_INFO_CAPTURECOUNT, &match_array_size);
 232   if (eno)
 233     die("Internal error: pcre_fullinfo() failed with error %d", eno);
 234   match_array_size = 3*(match_array_size+1);
 235   regex *r = xmalloc_zero(sizeof(regex) + match_array_size * sizeof(int));
 236   r->rx = rx;
 237   r->match_array_size = match_array_size;
 238   r->extra = pcre_study(r->rx, 0, &err);
 239   if (err)
 240     die("Error studying regular expression `%s': %s", p, err);
 241   return r;
 242 }
 243
 244 void
 245 rx_free(regex *r)
 246 {
 247   xfree(r->rx);
 248   xfree(r->extra);
 249   xfree(r);
 250 }
 251
 252 int
 253 rx_match(regex *r, byte *s)
 254 {
 255   int len = str_len(s);
 256   int err = pcre_exec(r->rx, r->extra, s, len, 0, 0, r->matches, r->match_array_size);
 257   if (err >= 0)
 258     {
 259       r->real_matches = err;
 260       /* need to check that the full string matches */
 261       return !(r->matches[0] || s[r->matches[1]]);
 262     }
 263   else if (err == PCRE_ERROR_NOMATCH)
 264     return 0;
 265   else if (err == PCRE_ERROR_NOMEMORY)
 266     die("Regex matching ran out of memory");
 267   else
 268     die("Regex matching failed with unknown error %d", err);
 269 }
 270
 271 int
 272 rx_subst(regex *r, byte *by, byte *src, byte *dest, uns destlen)
 273 {
 274   byte *end = dest + destlen - 1;
 275
 276   if (!rx_match(r, src))
 277     return 0;
 278
 279   while (*by)
 280     {
 281       if (*by == '\\')
 282         {
 283           by++;
 284           if (*by >= '0' && *by <= '9') /* \0 gets replaced by entire pattern */
 285             {
 286               uns j = *by++ - '0';
 287               if (j < r->real_matches && r->matches[2*j] >= 0)
 288                 {
 289                   byte *s = src + r->matches[2*j];
 290                   uns i = r->matches[2*j+1] - r->matches[2*j];
 291                   if (dest + i >= end)
 292                     return -1;
 293                   memcpy(dest, s, i);
 294                   dest += i;
 295                   continue;
 296                 }
 297             }
 298         }
 299       if (dest < end)
 300         *dest++ = *by++;
 301       else
 302         return -1;
 303     }
 304   *dest = 0;
 305   return 1;
 306 }
 307
 308 #endif
 309
 310 #ifdef TEST
 311
 312 int main(int argc, char **argv)
 313 {
 314   regex *r;
 315   byte buf1[4096], buf2[4096];
 316   int opt_i = 0;
 317
 318   if (!strcmp(argv[1], "-i"))
 319     {
 320       opt_i = 1;
 321       argv++;
 322       argc--;
 323     }
 324   r = rx_compile(argv[1], opt_i);
 325   while (fgets(buf1, sizeof(buf1), stdin))
 326     {
 327       char *p = strchr(buf1, '\n');
 328       if (p)
 329         *p = 0;
 330       if (argc == 2)
 331         {
 332           if (rx_match(r, buf1))
 333             puts("MATCH");
 334           else
 335             puts("NO MATCH");
 336         }
 337       else
 338         {
 339           int i = rx_subst(r, argv[2], buf1, buf2, sizeof(buf2));
 340           if (i < 0)
 341             puts("OVERFLOW");
 342           else if (!i)
 343             puts("NO MATCH");
 344           else
 345             puts(buf2);
 346         }
 347     }
 348   rx_free(r);
 349 }
 350
 351 #endif