src/regexp.c

   1 /*
   2  * regexp.c:
   3  *
   4  * Copyright (C) 2007-2015 David Lutterkort
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
  19  *
  20  * Author: David Lutterkort <dlutter@redhat.com>
  21  */
  22
  23 #include <config.h>
  24 #include <regex.h>
  25
  26 #include "internal.h"
  27 #include "syntax.h"
  28 #include "memory.h"
  29 #include "errcode.h"
  30
  31 static const struct string empty_pattern_string = {
  32     .ref = REF_MAX, .str = (char *) "()"
  33 };
  34
  35 static const struct string *const empty_pattern = &empty_pattern_string;
  36
  37 char *regexp_escape(const struct regexp *r) {
  38     char *pat = NULL;
  39
  40     if (r == NULL)
  41         return strdup("");
  42
  43 #if !HAVE_USELOCALE
  44     char *nre = NULL;
  45     int ret;
  46     size_t nre_len;
  47
  48     /* Use a range with from > to to force conversion of ranges into
  49      * short form */
  50     ret = fa_restrict_alphabet(r->pattern->str, strlen(r->pattern->str),
  51                                &nre, &nre_len, 2, 1);
  52     if (ret == 0) {
  53         pat = escape(nre, nre_len, RX_ESCAPES);
  54         free(nre);
  55     }
  56 #endif
  57
  58     if (pat == NULL)
  59         pat = escape(r->pattern->str, -1, RX_ESCAPES);
  60
  61     if (pat == NULL)
  62         return NULL;
  63
  64     /* Remove unneeded '()' from pat */
  65     for (int changed = 1; changed;) {
  66         changed = 0;
  67         for (char *p = pat; *p != '\0'; p++) {
  68             if (*p == '(' && p[1] == ')') {
  69                 memmove(p, p+2, strlen(p+2)+1);
  70                 changed = 1;
  71             }
  72         }
  73     }
  74
  75     if (pat[0] == '(' && pat[strlen(pat)-1] == ')') {
  76         int level = 1;
  77         for (int i=1; i < strlen(pat)-1; i++) {
  78             if (pat[i] == '(')
  79                 level += 1;
  80             if (pat[i] == ')')
  81                 level -= 1;
  82             if (level == 0)
  83                 break;
  84         }
  85         if (level == 1) {
  86             memmove(pat, pat+1, strlen(pat+1)+1);
  87             pat[strlen(pat)-1] = '\0';
  88         }
  89     }
  90
  91     return pat;
  92 }
  93
  94 void print_regexp(FILE *out, struct regexp *r) {
  95     if (r == NULL) {
  96         fprintf(out, "<NULL>");
  97         return;
  98     }
  99
 100     fputc('/', out);
 101     if (r->pattern == NULL)
 102         fprintf(out, "%p", r);
 103     else {
 104         char *rx;
 105         size_t rx_len;
 106         fa_restrict_alphabet(r->pattern->str, strlen(r->pattern->str),
 107                              &rx, &rx_len, 2, 1);
 108         print_chars(out, rx, rx_len);
 109         FREE(rx);
 110     }
 111     fputc('/', out);
 112     if (r->nocase)
 113         fputc('i', out);
 114 }
 115
 116 struct regexp *
 117 make_regexp_unescape(struct info *info, const char *pat, int nocase) {
 118     char *p = unescape(pat, strlen(pat), NULL);
 119
 120     if (p == NULL)
 121         return NULL;
 122     return make_regexp(info, p, nocase);
 123 }
 124
 125 struct regexp *make_regexp(struct info *info, char *pat, int nocase) {
 126     struct regexp *regexp;
 127
 128     make_ref(regexp);
 129     regexp->info = ref(info);
 130
 131     make_ref(regexp->pattern);
 132     regexp->pattern->str = pat;
 133     regexp->nocase = nocase;
 134     return regexp;
 135 }
 136
 137 /* Take a POSIX glob and turn it into a regexp. The regexp is constructed
 138  * by doing the following translations of characters in the string:
 139  *  * -> [^/]*
 140  *  ? -> [^/]
 141  *  leave characters escaped with a backslash alone
 142  *  escape any of ".|{}()+^$" with a backslash
 143  *
 144  * Note that that ignores some of the finer points of globs, like
 145  * complementation.
 146  */
 147 struct regexp *make_regexp_from_glob(struct info *info, const char *glob) {
 148     static const char *const star = "[^/]*";
 149     static const char *const qmark = "[^/]";
 150     static const char *const special = ".|{}()+^$";
 151     int newlen = strlen(glob);
 152     char *pat = NULL;
 153
 154     for (const char *s = glob; *s; s++) {
 155         if (*s == '\\' && *(s+1))
 156             s += 1;
 157         else if (*s == '*')
 158             newlen += strlen(star)-1;
 159         else if (*s == '?')
 160             newlen += strlen(qmark)-1;
 161         else if (strchr(special, *s) != NULL)
 162             newlen += 1;
 163     }
 164
 165     if (ALLOC_N(pat, newlen + 1) < 0)
 166         return NULL;
 167
 168     char *t = pat;
 169     for (const char *s = glob; *s; s++) {
 170         if (*s == '\\' && *(s+1)) {
 171             *t++ = *s++;
 172             *t++ = *s;
 173         } else if (*s == '*') {
 174             t = stpcpy(t, star);
 175         } else if (*s == '?') {
 176             t = stpcpy(t, qmark);
 177         } else if (strchr(special, *s) != NULL) {
 178             *t++ = '\\';
 179             *t++ = *s;
 180         } else {
 181             *t++ = *s;
 182         }
 183     }
 184
 185     return make_regexp(info, pat, 0);
 186 }
 187
 188 void free_regexp(struct regexp *regexp) {
 189     if (regexp == NULL)
 190         return;
 191     assert(regexp->ref == 0);
 192     unref(regexp->info, info);
 193     unref(regexp->pattern, string);
 194     if (regexp->re != NULL) {
 195         regfree(regexp->re);
 196         free(regexp->re);
 197     }
 198     free(regexp);
 199 }
 200
 201 int regexp_is_empty_pattern(struct regexp *r) {
 202     for (char *s = r->pattern->str; *s; s++) {
 203         if (*s != '(' && *s != ')')
 204             return 0;
 205     }
 206     return 1;
 207 }
 208
 209 struct regexp *make_regexp_literal(struct info *info, const char *text) {
 210     char *pattern, *p;
 211
 212     /* Escape special characters in text since it should be taken
 213        literally */
 214     CALLOC(pattern, 2*strlen(text)+1);
 215     p = pattern;
 216     for (const char *t = text; *t != '\0'; t++) {
 217         if ((*t == '\\') && t[1]) {
 218             *p++ = *t++;
 219             *p++ = *t;
 220         } else if (strchr(".|{}[]()+*?", *t) != NULL) {
 221             *p++ = '\\';
 222             *p++ = *t;
 223         } else {
 224             *p++ = *t;
 225         }
 226     }
 227     return make_regexp(info, pattern, 0);
 228 }
 229
 230 struct regexp *
 231 regexp_union(struct info *info, struct regexp *r1, struct regexp *r2) {
 232     struct regexp *r[2];
 233
 234     r[0] = r1;
 235     r[1] = r2;
 236     return regexp_union_n(info, 2, r);
 237 }
 238
 239 char *regexp_expand_nocase(struct regexp *r) {
 240     const char *p = r->pattern->str, *t;
 241     char *s = NULL;
 242     size_t len;
 243     int ret;
 244     int psub = 0, rsub = 0;
 245
 246     if (! r->nocase)
 247         return strdup(p);
 248
 249     ret = fa_expand_nocase(p, strlen(p), &s, &len);
 250     ERR_NOMEM(ret == REG_ESPACE, r->info);
 251     BUG_ON(ret != REG_NOERROR, r->info, NULL);
 252
 253     /* Make sure that r->pattern->str and ret have the same number
 254      * of parentheses/groups, since our parser critically depends
 255      * on the fact that the regexp for a union/concat and those
 256      * of its children have groups that are in direct relation */
 257     for (t = p; *t; t++) if (*t == '(') psub += 1;
 258     for (t = s; *t; t++) if (*t == '(') rsub += 1;
 259     BUG_ON(psub < rsub, r->info, NULL);
 260     psub -= rsub;
 261     if (psub > 0) {
 262         char *adjusted = NULL, *a;
 263         if (ALLOC_N(adjusted, strlen(s) + 2*psub + 1) < 0)
 264             ERR_NOMEM(true, r->info);
 265         a = adjusted;
 266         for (int i=0; i < psub; i++) *a++ = '(';
 267         a = stpcpy(a, s);
 268         for (int i=0; i < psub; i++) *a++ = ')';
 269         free(s);
 270         s = adjusted;
 271     }
 272  error:
 273     return s;
 274 }
 275
 276 static char *append_expanded(struct regexp *r, char **pat, char *p,
 277                              size_t *len) {
 278     char *expanded = NULL;
 279     size_t ofs = p - *pat;
 280     int ret;
 281
 282     expanded = regexp_expand_nocase(r);
 283     ERR_BAIL(r->info);
 284
 285     *len += strlen(expanded) - strlen(r->pattern->str);
 286
 287     ret = REALLOC_N(*pat, *len);
 288     ERR_NOMEM(ret < 0, r->info);
 289
 290     p = stpcpy(*pat + ofs, expanded);
 291  error:
 292     FREE(expanded);
 293     return p;
 294 }
 295
 296 struct regexp *
 297 regexp_union_n(struct info *info, int n, struct regexp **r) {
 298     size_t len = 0;
 299     char *pat = NULL, *p, *expanded = NULL;
 300     int nnocase = 0, npresent = 0;
 301
 302     for (int i=0; i < n; i++)
 303         if (r[i] != NULL) {
 304             len += strlen(r[i]->pattern->str) + strlen("()|");
 305             npresent += 1;
 306             if (r[i]->nocase)
 307                 nnocase += 1;
 308         }
 309
 310     bool mixedcase = nnocase > 0 && nnocase < npresent;
 311
 312     if (len == 0)
 313         return NULL;
 314
 315     if (ALLOC_N(pat, len) < 0)
 316         return NULL;
 317
 318     p = pat;
 319     int added = 0;
 320     for (int i=0; i < n; i++) {
 321         if (r[i] == NULL)
 322             continue;
 323         if (added > 0)
 324             *p++ = '|';
 325         *p++ = '(';
 326         if (mixedcase && r[i]->nocase) {
 327             p = append_expanded(r[i], &pat, p, &len);
 328             ERR_BAIL(r[i]->info);
 329         } else {
 330             p = stpcpy(p, r[i]->pattern->str);
 331         }
 332         *p++ = ')';
 333         added += 1;
 334     }
 335     *p = '\0';
 336     return make_regexp(info, pat, nnocase == npresent);
 337  error:
 338     FREE(expanded);
 339     FREE(pat);
 340     return NULL;
 341 }
 342
 343 struct regexp *
 344 regexp_concat(struct info *info, struct regexp *r1, struct regexp *r2) {
 345     struct regexp *r[2];
 346
 347     r[0] = r1;
 348     r[1] = r2;
 349     return regexp_concat_n(info, 2, r);
 350 }
 351
 352 struct regexp *
 353 regexp_concat_n(struct info *info, int n, struct regexp **r) {
 354     size_t len = 0;
 355     char *pat = NULL, *p, *expanded = NULL;
 356     int nnocase = 0, npresent = 0;
 357
 358     for (int i=0; i < n; i++)
 359         if (r[i] != NULL) {
 360             len += strlen(r[i]->pattern->str) + strlen("()");
 361             npresent += 1;
 362             if (r[i]->nocase)
 363                 nnocase += 1;
 364         }
 365
 366     bool mixedcase = nnocase > 0 && nnocase < npresent;
 367
 368     if (len == 0)
 369         return NULL;
 370
 371     len += 1;
 372     if (ALLOC_N(pat, len) < 0)
 373         return NULL;
 374
 375     p = pat;
 376     for (int i=0; i < n; i++) {
 377         if (r[i] == NULL)
 378             continue;
 379         *p++ = '(';
 380         if (mixedcase && r[i]->nocase) {
 381             p = append_expanded(r[i], &pat, p, &len);
 382             ERR_BAIL(r[i]->info);
 383         } else {
 384             p = stpcpy(p, r[i]->pattern->str);
 385         }
 386         *p++ = ')';
 387     }
 388     *p = '\0';
 389     return make_regexp(info, pat, nnocase == npresent);
 390  error:
 391     FREE(expanded);
 392     FREE(pat);
 393     return NULL;
 394 }
 395
 396 static struct fa *regexp_to_fa(struct regexp *r) {
 397     const char *p = r->pattern->str;
 398     int ret;
 399     struct fa *fa = NULL;
 400
 401     ret = fa_compile(p, strlen(p), &fa);
 402     ERR_NOMEM(ret == REG_ESPACE, r->info);
 403     BUG_ON(ret != REG_NOERROR, r->info, NULL);
 404
 405     if (r->nocase) {
 406         ret = fa_nocase(fa);
 407         ERR_NOMEM(ret < 0, r->info);
 408     }
 409     return fa;
 410
 411  error:
 412     fa_free(fa);
 413     return NULL;
 414 }
 415
 416 struct regexp *
 417 regexp_minus(struct info *info, struct regexp *r1, struct regexp *r2) {
 418     struct regexp *result = NULL;
 419     struct fa *fa = NULL, *fa1 = NULL, *fa2 = NULL;
 420     int r;
 421     char *s = NULL;
 422     size_t s_len;
 423
 424     fa1 = regexp_to_fa(r1);
 425     ERR_BAIL(r1->info);
 426
 427     fa2 = regexp_to_fa(r2);
 428     ERR_BAIL(r2->info);
 429
 430     fa = fa_minus(fa1, fa2);
 431     if (fa == NULL)
 432         goto error;
 433
 434     r = fa_as_regexp(fa, &s, &s_len);
 435     if (r < 0)
 436         goto error;
 437
 438     if (s == NULL) {
 439         /* FA is the empty set, which we can't represent as a regexp */
 440         goto error;
 441     }
 442
 443     if (regexp_c_locale(&s, NULL) < 0)
 444         goto error;
 445
 446     result = make_regexp(info, s, fa_is_nocase(fa));
 447     s = NULL;
 448
 449  done:
 450     fa_free(fa);
 451     fa_free(fa1);
 452     fa_free(fa2);
 453     free(s);
 454     return result;
 455  error:
 456     unref(result, regexp);
 457     goto done;
 458 }
 459
 460
 461 struct regexp *
 462 regexp_iter(struct info *info, struct regexp *r, int min, int max) {
 463     const char *p;
 464     char *s;
 465     int ret = 0;
 466
 467     if (r == NULL)
 468         return NULL;
 469
 470     p = r->pattern->str;
 471     if ((min == 0 || min == 1) && max == -1) {
 472         char q = (min == 0) ? '*' : '+';
 473         ret = asprintf(&s, "(%s)%c", p, q);
 474     } else if (min == max) {
 475         ret = asprintf(&s, "(%s){%d}", p, min);
 476     } else {
 477         ret = asprintf(&s, "(%s){%d,%d}", p, min, max);
 478     }
 479     return (ret == -1) ? NULL : make_regexp(info, s, r->nocase);
 480 }
 481
 482 struct regexp *
 483 regexp_maybe(struct info *info, struct regexp *r) {
 484     const char *p;
 485     char *s;
 486     int ret;
 487
 488     if (r == NULL)
 489         return NULL;
 490     p = r->pattern->str;
 491     ret = asprintf(&s, "(%s)?", p);
 492     return (ret == -1) ? NULL : make_regexp(info, s, r->nocase);
 493 }
 494
 495 struct regexp *regexp_make_empty(struct info *info) {
 496     struct regexp *regexp;
 497
 498     make_ref(regexp);
 499     if (regexp != NULL) {
 500         regexp->info = ref(info);
 501         /* Casting away the CONST for EMPTY_PATTERN is ok since it
 502            is protected against changes because REF == REF_MAX */
 503         regexp->pattern = (struct string *) empty_pattern;
 504         regexp->nocase = 0;
 505     }
 506     return regexp;
 507 }
 508
 509 static int regexp_compile_internal(struct regexp *r, const char **c) {
 510     /* See the GNU regex manual or regex.h in gnulib for
 511      * an explanation of these flags. They are set so that the regex
 512      * matcher interprets regular expressions the same way that libfa
 513      * does
 514      */
 515     static const reg_syntax_t syntax =
 516         RE_CONTEXT_INDEP_OPS|RE_CONTEXT_INVALID_OPS|RE_DOT_NOT_NULL
 517         |RE_INTERVALS|RE_NO_BK_BRACES|RE_NO_BK_PARENS|RE_NO_BK_REFS
 518         |RE_NO_BK_VBAR|RE_NO_EMPTY_RANGES
 519         |RE_NO_POSIX_BACKTRACKING|RE_CONTEXT_INVALID_DUP|RE_NO_GNU_OPS;
 520     reg_syntax_t old_syntax = re_syntax_options;
 521
 522     *c = NULL;
 523
 524     if (r->re == NULL)
 525         CALLOC(r->re, 1);
 526
 527     re_syntax_options = syntax;
 528     if (r->nocase)
 529         re_syntax_options |= RE_ICASE;
 530     *c = re_compile_pattern(r->pattern->str, strlen(r->pattern->str), r->re);
 531     re_syntax_options = old_syntax;
 532
 533     r->re->regs_allocated = REGS_REALLOCATE;
 534     if (*c != NULL)
 535         return -1;
 536     return 0;
 537 }
 538
 539 int regexp_compile(struct regexp *r) {
 540     const char *c;
 541
 542     return regexp_compile_internal(r, &c);
 543 }
 544
 545 int regexp_check(struct regexp *r, const char **msg) {
 546     return regexp_compile_internal(r, msg);
 547 }
 548
 549 int regexp_match(struct regexp *r,
 550                  const char *string, const int size,
 551                  const int start, struct re_registers *regs) {
 552     if (r->re == NULL) {
 553         if (regexp_compile(r) == -1)
 554             return -3;
 555     }
 556     return re_match(r->re, string, size, start, regs);
 557 }
 558
 559 int regexp_matches_empty(struct regexp *r) {
 560     return regexp_match(r, "", 0, 0, NULL) == 0;
 561 }
 562
 563 int regexp_nsub(struct regexp *r) {
 564     if (r->re == NULL)
 565         if (regexp_compile(r) == -1)
 566             return -1;
 567     return r->re->re_nsub;
 568 }
 569
 570 void regexp_release(struct regexp *regexp) {
 571     if (regexp != NULL && regexp->re != NULL) {
 572         regfree(regexp->re);
 573         FREE(regexp->re);
 574     }
 575 }
 576
 577 /*
 578  * Local variables:
 579  *  indent-tabs-mode: nil
 580  *  c-indent-level: 4
 581  *  c-basic-offset: 4
 582  *  tab-width: 4
 583  * End:
 584  */