lib/regex.c

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