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