src/regexp.c

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