/src/augeas/src/regexp.c

Source
/*
 * regexp.c:
 *
 * Copyright (C) 2007-2016 David Lutterkort
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 *
 * Author: David Lutterkort <dlutter@redhat.com>
 */

#include <config.h>
#include <regex.h>

#include "internal.h"
#include "syntax.h"
#include "memory.h"
#include "errcode.h"

static const struct string empty_pattern_string = {
    .ref = REF_MAX, .str = (char *) "()"
};

static const struct string *const empty_pattern = &empty_pattern_string;

char *regexp_escape(const struct regexp *r) {
    char *pat = NULL;

    if (r == NULL)
        return strdup("");

#if !HAVE_USELOCALE
    char *nre = NULL;
    int ret;
    size_t nre_len;

    /* Use a range with from > to to force conversion of ranges into
     * short form */
    ret = fa_restrict_alphabet(r->pattern->str, strlen(r->pattern->str),
                               &nre, &nre_len, 2, 1);
    if (ret == 0) {
        pat = escape(nre, nre_len, RX_ESCAPES);
        free(nre);
    }
#endif

    if (pat == NULL) {
        /* simplify the regexp by removing some artifacts of reserving
           chanaracters for internal purposes */
        if (index(r->pattern->str, RESERVED_FROM_CH)) {
            char *s = strdup(r->pattern->str);
            char *t = s;
            for (char *p = s; *p; p++) {
                if (STREQLEN(p, RESERVED_RANGE_RX, strlen(RESERVED_RANGE_RX))) {
                    /* Completely eliminate mentions of the reserved range */
                    p += strlen(RESERVED_RANGE_RX);
                } else if (STREQLEN(p,
                                    RESERVED_DOT_RX, strlen(RESERVED_DOT_RX))) {
                    /* Replace what amounts to a '.' by one */
                    p += strlen(RESERVED_DOT_RX);
                    *t++ = '.';
                }
                *t++ = *p;
            }
            *t = '\0';
            pat = escape(s, -1, RX_ESCAPES);
            free(s);
        } else {
            pat = escape(r->pattern->str, -1, RX_ESCAPES);
        }
    }

    if (pat == NULL)
        return NULL;

    /* Remove unneeded '()' from pat */
    for (int changed = 1; changed;) {
        changed = 0;
        for (char *p = pat; *p != '\0'; p++) {
            if (*p == '(' && p[1] == ')') {
                memmove(p, p+2, strlen(p+2)+1);
                changed = 1;
            }
        }
    }

    if (pat[0] == '(' && pat[strlen(pat)-1] == ')') {
        int level = 1;
        for (int i=1; i < strlen(pat)-1; i++) {
            if (pat[i] == '(')
                level += 1;
            if (pat[i] == ')')
                level -= 1;
            if (level == 0)
                break;
        }
        if (level == 1) {
            memmove(pat, pat+1, strlen(pat+1)+1);
            pat[strlen(pat)-1] = '\0';
        }
    }

    return pat;
}

void print_regexp(FILE *out, struct regexp *r) {
    if (r == NULL) {
        fprintf(out, "<NULL>");
        return;
    }

    fputc('/', out);
    if (r->pattern == NULL)
        fprintf(out, "%p", r);
    else {
        char *rx;
        size_t rx_len;
        fa_restrict_alphabet(r->pattern->str, strlen(r->pattern->str),
                             &rx, &rx_len, 2, 1);
        print_chars(out, rx, rx_len);
        FREE(rx);
    }
    fputc('/', out);
    if (r->nocase)
        fputc('i', out);
}

struct regexp *
make_regexp_unescape(struct info *info, const char *pat, int nocase) {
    char *p = unescape(pat, strlen(pat), NULL);

    if (p == NULL)
        return NULL;
    return make_regexp(info, p, nocase);
}

struct regexp *make_regexp(struct info *info, char *pat, int nocase) {
    struct regexp *regexp;

    make_ref(regexp);
    regexp->info = ref(info);

    make_ref(regexp->pattern);
    regexp->pattern->str = pat;
    regexp->nocase = nocase;
    return regexp;
}

/* Take a POSIX glob and turn it into a regexp. The regexp is constructed
 * by doing the following translations of characters in the string:
 *  * -> [^/]*
 *  ? -> [^/]
 *  leave characters escaped with a backslash alone
 *  escape any of ".|{}()+^$" with a backslash
 *
 * Note that that ignores some of the finer points of globs, like
 * complementation.
 */
struct regexp *make_regexp_from_glob(struct info *info, const char *glob) {
    static const char *const star = "[^/]*";
    static const char *const qmark = "[^/]";
    static const char *const special = ".|{}()+^$";
    int newlen = strlen(glob);
    char *pat = NULL;

    for (const char *s = glob; *s; s++) {
        if (*s == '\\' && *(s+1))
            s += 1;
        else if (*s == '*')
            newlen += strlen(star)-1;
        else if (*s == '?')
            newlen += strlen(qmark)-1;
        else if (strchr(special, *s) != NULL)
            newlen += 1;
    }

    if (ALLOC_N(pat, newlen + 1) < 0)
        return NULL;

    char *t = pat;
    for (const char *s = glob; *s; s++) {
        if (*s == '\\' && *(s+1)) {
            *t++ = *s++;
            *t++ = *s;
        } else if (*s == '*') {
            t = stpcpy(t, star);
        } else if (*s == '?') {
            t = stpcpy(t, qmark);
        } else if (strchr(special, *s) != NULL) {
            *t++ = '\\';
            *t++ = *s;
        } else {
            *t++ = *s;
        }
    }

    return make_regexp(info, pat, 0);
}

void free_regexp(struct regexp *regexp) {
    if (regexp == NULL)
        return;
    assert(regexp->ref == 0);
    unref(regexp->info, info);
    unref(regexp->pattern, string);
    if (regexp->re != NULL) {
        regfree(regexp->re);
        free(regexp->re);
    }
    free(regexp);
}

int regexp_is_empty_pattern(struct regexp *r) {
    for (char *s = r->pattern->str; *s; s++) {
        if (*s != '(' && *s != ')')
            return 0;
    }
    return 1;
}

struct regexp *make_regexp_literal(struct info *info, const char *text) {
    char *pattern, *p;

    /* Escape special characters in text since it should be taken
       literally */
    if (ALLOC_N(pattern, 2*strlen(text)+1) < 0)
        return NULL;
    p = pattern;
    for (const char *t = text; *t != '\0'; t++) {
        if ((*t == '\\') && t[1]) {
            *p++ = *t++;
            *p++ = *t;
        } else if (strchr(".|{}[]()+*?", *t) != NULL) {
            *p++ = '\\';
            *p++ = *t;
        } else {
            *p++ = *t;
        }
    }
    return make_regexp(info, pattern, 0);
}

struct regexp *
regexp_union(struct info *info, struct regexp *r1, struct regexp *r2) {
    struct regexp *r[2];

    r[0] = r1;
    r[1] = r2;
    return regexp_union_n(info, 2, r);
}

char *regexp_expand_nocase(struct regexp *r) {
    const char *p = r->pattern->str, *t;
    char *s = NULL;
    size_t len;
    int ret;
    int psub = 0, rsub = 0;

    if (! r->nocase)
        return strdup(p);

    ret = fa_expand_nocase(p, strlen(p), &s, &len);
    ERR_NOMEM(ret == REG_ESPACE, r->info);
    BUG_ON(ret != REG_NOERROR, r->info, NULL);

    /* Make sure that r->pattern->str and ret have the same number
     * of parentheses/groups, since our parser critically depends
     * on the fact that the regexp for a union/concat and those
     * of its children have groups that are in direct relation */
    for (t = p; *t; t++) if (*t == '(') psub += 1;
    for (t = s; *t; t++) if (*t == '(') rsub += 1;
    BUG_ON(psub < rsub, r->info, NULL);
    psub -= rsub;
    if (psub > 0) {
        char *adjusted = NULL, *a;
        if (ALLOC_N(adjusted, strlen(s) + 2*psub + 1) < 0)
            ERR_NOMEM(true, r->info);
        a = adjusted;
        for (int i=0; i < psub; i++) *a++ = '(';
        a = stpcpy(a, s);
        for (int i=0; i < psub; i++) *a++ = ')';
        free(s);
        s = adjusted;
    }
 error:
    return s;
}

static char *append_expanded(struct regexp *r, char **pat, char *p,
                             size_t *len) {
    char *expanded = NULL;
    size_t ofs = p - *pat;
    int ret;

    expanded = regexp_expand_nocase(r);
    ERR_BAIL(r->info);

    *len += strlen(expanded) - strlen(r->pattern->str);

    ret = REALLOC_N(*pat, *len);
    ERR_NOMEM(ret < 0, r->info);

    p = stpcpy(*pat + ofs, expanded);
 error:
    FREE(expanded);
    return p;
}

struct regexp *
regexp_union_n(struct info *info, int n, struct regexp **r) {
    size_t len = 0;
    char *pat = NULL, *p, *expanded = NULL;
    int nnocase = 0, npresent = 0;

    for (int i=0; i < n; i++)
        if (r[i] != NULL) {
            len += strlen(r[i]->pattern->str) + strlen("()|");
            npresent += 1;
            if (r[i]->nocase)
                nnocase += 1;
        }

    bool mixedcase = nnocase > 0 && nnocase < npresent;

    if (len == 0)
        return NULL;

    if (ALLOC_N(pat, len) < 0)
        return NULL;

    p = pat;
    int added = 0;
    for (int i=0; i < n; i++) {
        if (r[i] == NULL)
            continue;
        if (added > 0)
            *p++ = '|';
        *p++ = '(';
        if (mixedcase && r[i]->nocase) {
            p = append_expanded(r[i], &pat, p, &len);
            ERR_BAIL(r[i]->info);
        } else {
            p = stpcpy(p, r[i]->pattern->str);
        }
        *p++ = ')';
        added += 1;
    }
    *p = '\0';
    return make_regexp(info, pat, nnocase == npresent);
 error:
    FREE(expanded);
    FREE(pat);
    return NULL;
}

struct regexp *
regexp_concat(struct info *info, struct regexp *r1, struct regexp *r2) {
    struct regexp *r[2];

    r[0] = r1;
    r[1] = r2;
    return regexp_concat_n(info, 2, r);
}

struct regexp *
regexp_concat_n(struct info *info, int n, struct regexp **r) {
    size_t len = 0;
    char *pat = NULL, *p, *expanded = NULL;
    int nnocase = 0, npresent = 0;

    for (int i=0; i < n; i++)
        if (r[i] != NULL) {
            len += strlen(r[i]->pattern->str) + strlen("()");
            npresent += 1;
            if (r[i]->nocase)
                nnocase += 1;
        }

    bool mixedcase = nnocase > 0 && nnocase < npresent;

    if (len == 0)
        return NULL;

    len += 1;
    if (ALLOC_N(pat, len) < 0)
        return NULL;

    p = pat;
    for (int i=0; i < n; i++) {
        if (r[i] == NULL)
            continue;
        *p++ = '(';
        if (mixedcase && r[i]->nocase) {
            p = append_expanded(r[i], &pat, p, &len);
            ERR_BAIL(r[i]->info);
        } else {
            p = stpcpy(p, r[i]->pattern->str);
        }
        *p++ = ')';
    }
    *p = '\0';
    return make_regexp(info, pat, nnocase == npresent);
 error:
    FREE(expanded);
    FREE(pat);
    return NULL;
}

static struct fa *regexp_to_fa(struct regexp *r) {
    const char *p = r->pattern->str;
    int ret;
    struct fa *fa = NULL;

    ret = fa_compile(p, strlen(p), &fa);
    ERR_NOMEM(ret == REG_ESPACE, r->info);
    BUG_ON(ret != REG_NOERROR, r->info, NULL);

    if (r->nocase) {
        ret = fa_nocase(fa);
        ERR_NOMEM(ret < 0, r->info);
    }
    return fa;

 error:
    fa_free(fa);
    return NULL;
}

struct regexp *
regexp_minus(struct info *info, struct regexp *r1, struct regexp *r2) {
    struct regexp *result = NULL;
    struct fa *fa = NULL, *fa1 = NULL, *fa2 = NULL;
    int r;
    char *s = NULL;
    size_t s_len;

    fa1 = regexp_to_fa(r1);
    ERR_BAIL(r1->info);

    fa2 = regexp_to_fa(r2);
    ERR_BAIL(r2->info);

    fa = fa_minus(fa1, fa2);
    if (fa == NULL)
        goto error;

    r = fa_as_regexp(fa, &s, &s_len);
    if (r < 0)
        goto error;

    if (s == NULL) {
        /* FA is the empty set, which we can't represent as a regexp */
        goto error;
    }

    if (regexp_c_locale(&s, NULL) < 0)
        goto error;

    result = make_regexp(info, s, fa_is_nocase(fa));
    s = NULL;

 done:
    fa_free(fa);
    fa_free(fa1);
    fa_free(fa2);
    free(s);
    return result;
 error:
    unref(result, regexp);
    goto done;
}


struct regexp *
regexp_iter(struct info *info, struct regexp *r, int min, int max) {
    const char *p;
    char *s;
    int ret = 0;

    if (r == NULL)
        return NULL;

    p = r->pattern->str;
    if ((min == 0 || min == 1) && max == -1) {
        char q = (min == 0) ? '*' : '+';
        ret = asprintf(&s, "(%s)%c", p, q);
    } else if (min == max) {
        ret = asprintf(&s, "(%s){%d}", p, min);
    } else {
        ret = asprintf(&s, "(%s){%d,%d}", p, min, max);
    }
    return (ret == -1) ? NULL : make_regexp(info, s, r->nocase);
}

struct regexp *
regexp_maybe(struct info *info, struct regexp *r) {
    const char *p;
    char *s;
    int ret;

    if (r == NULL)
        return NULL;
    p = r->pattern->str;
    ret = asprintf(&s, "(%s)?", p);
    return (ret == -1) ? NULL : make_regexp(info, s, r->nocase);
}

struct regexp *regexp_make_empty(struct info *info) {
    struct regexp *regexp;

    make_ref(regexp);
    if (regexp != NULL) {
        regexp->info = ref(info);
        /* Casting away the CONST for EMPTY_PATTERN is ok since it
           is protected against changes because REF == REF_MAX */
        regexp->pattern = (struct string *) empty_pattern;
        regexp->nocase = 0;
    }
    return regexp;
}

static int regexp_compile_internal(struct regexp *r, const char **c) {
    /* See the GNU regex manual or regex.h in gnulib for
     * an explanation of these flags. They are set so that the regex
     * matcher interprets regular expressions the same way that libfa
     * does
     */
    static const reg_syntax_t syntax =
        RE_CONTEXT_INDEP_OPS|RE_CONTEXT_INVALID_OPS|RE_DOT_NOT_NULL
        |RE_INTERVALS|RE_NO_BK_BRACES|RE_NO_BK_PARENS|RE_NO_BK_REFS
        |RE_NO_BK_VBAR|RE_NO_EMPTY_RANGES
        |RE_NO_POSIX_BACKTRACKING|RE_CONTEXT_INVALID_DUP|RE_NO_GNU_OPS;
    reg_syntax_t old_syntax = re_syntax_options;

    *c = NULL;

    if (r->re == NULL) {
        if (ALLOC(r->re) < 0)
            return -1;
    }

    re_syntax_options = syntax;
    if (r->nocase)
        re_syntax_options |= RE_ICASE;
    *c = re_compile_pattern(r->pattern->str, strlen(r->pattern->str), r->re);
    re_syntax_options = old_syntax;

    r->re->regs_allocated = REGS_REALLOCATE;
    if (*c != NULL)
        return -1;
    return 0;
}

int regexp_compile(struct regexp *r) {
    const char *c;

    return regexp_compile_internal(r, &c);
}

int regexp_check(struct regexp *r, const char **msg) {
    return regexp_compile_internal(r, msg);
}

int regexp_match(struct regexp *r,
                 const char *string, const int size,
                 const int start, struct re_registers *regs) {
    if (r->re == NULL) {
        if (regexp_compile(r) == -1)
            return -3;
    }
    return re_match(r->re, string, size, start, regs);
}

int regexp_matches_empty(struct regexp *r) {
    return regexp_match(r, "", 0, 0, NULL) == 0;
}

int regexp_nsub(struct regexp *r) {
    if (r->re == NULL)
        if (regexp_compile(r) == -1)
            return -1;
    return r->re->re_nsub;
}

void regexp_release(struct regexp *regexp) {
    if (regexp != NULL && regexp->re != NULL) {
        regfree(regexp->re);
        FREE(regexp->re);
    }
}

/*
 * Local variables:
 *  indent-tabs-mode: nil
 *  c-indent-level: 4
 *  c-basic-offset: 4
 *  tab-width: 4
 * End:
 */

Coverage Report

Created: 2026-08-31 07:05

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