/src/bind9/lib/isc/regex.c

Source
/*
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
 *
 * SPDX-License-Identifier: MPL-2.0
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

#include <stdbool.h>

#include <isc/file.h>
#include <isc/regex.h>
#include <isc/string.h>

#if VALREGEX_REPORT_REASON
#define FAIL(x)               \
  do {                  \
    reason = (x); \
    goto error;   \
  } while (0)
#else /* if VALREGEX_REPORT_REASON */
#define FAIL(x) goto error
#endif /* if VALREGEX_REPORT_REASON */

/*
 * Validate the regular expression 'C' locale.
 */
int
isc_regex_validate(const char *c) {
  enum {
    none,
    parse_bracket,
    parse_bound,
    parse_ce,
    parse_ec,
    parse_cc
  } state = none;
  /* Well known character classes. */
  const char *cc[] = { ":alnum:", ":digit:", ":punct:", ":alpha:",
           ":graph:", ":space:", ":blank:", ":lower:",
           ":upper:", ":cntrl:", ":print:", ":xdigit:" };
  bool seen_comma = false;
  bool seen_high = false;
  bool seen_char = false;
  bool seen_ec = false;
  bool seen_ce = false;
  bool have_atom = false;
  int group = 0;
  int range = 0;
  int sub = 0;
  bool empty_ok = false;
  bool neg = false;
  bool was_multiple = false;
  unsigned int low = 0;
  unsigned int high = 0;
  const char *ccname = NULL;
  int range_start = 0;
#if VALREGEX_REPORT_REASON
  const char *reason = "";
#endif /* if VALREGEX_REPORT_REASON */

  if (c == NULL || *c == 0) {
    FAIL("empty string");
  }

  while (c != NULL && *c != 0) {
    switch (state) {
    case none:
      switch (*c) {
      case '\\': /* make literal */
        ++c;
        switch (*c) {
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
          if ((*c - '0') > sub) {
            FAIL("bad back reference");
          }
          have_atom = true;
          was_multiple = false;
          break;
        case 0:
          FAIL("escaped end-of-string");
        default:
          goto literal;
        }
        ++c;
        break;
      case '[': /* bracket start */
        ++c;
        neg = false;
        was_multiple = false;
        seen_char = false;
        state = parse_bracket;
        break;
      case '{': /* bound start */
        switch (c[1]) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9':
          if (!have_atom) {
            FAIL("no atom");
          }
          if (was_multiple) {
            FAIL("was multiple");
          }
          seen_comma = false;
          seen_high = false;
          low = high = 0;
          state = parse_bound;
          break;
        default:
          goto literal;
        }
        ++c;
        have_atom = true;
        was_multiple = true;
        break;
      case '}':
        goto literal;
      case '(': /* group start */
        have_atom = false;
        was_multiple = false;
        empty_ok = true;
        ++group;
        ++sub;
        ++c;
        break;
      case ')': /* group end */
        if (group && !have_atom && !empty_ok) {
          FAIL("empty alternative");
        }
        have_atom = true;
        was_multiple = false;
        if (group != 0) {
          --group;
        }
        ++c;
        break;
      case '|': /* alternative separator */
        if (!have_atom) {
          FAIL("no atom");
        }
        have_atom = false;
        empty_ok = false;
        was_multiple = false;
        ++c;
        break;
      case '^':
      case '$':
        have_atom = true;
        was_multiple = true;
        ++c;
        break;
      case '+':
      case '*':
      case '?':
        if (was_multiple) {
          FAIL("was multiple");
        }
        if (!have_atom) {
          FAIL("no atom");
        }
        have_atom = true;
        was_multiple = true;
        ++c;
        break;
      case '.':
      default:
      literal:
        have_atom = true;
        was_multiple = false;
        ++c;
        break;
      }
      break;
    case parse_bound:
      switch (*c) {
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
        if (!seen_comma) {
          low = low * 10 + *c - '0';
          if (low > 255) {
            FAIL("lower bound too big");
          }
        } else {
          seen_high = true;
          high = high * 10 + *c - '0';
          if (high > 255) {
            FAIL("upper bound too big");
          }
        }
        ++c;
        break;
      case ',':
        if (seen_comma) {
          FAIL("multiple commas");
        }
        seen_comma = true;
        ++c;
        break;
      default:
      case '{':
        FAIL("non digit/comma");
      case '}':
        if (seen_high && low > high) {
          FAIL("bad parse bound");
        }
        seen_comma = false;
        state = none;
        ++c;
        break;
      }
      break;
    case parse_bracket:
      switch (*c) {
      case '^':
        if (seen_char || neg) {
          goto inside;
        }
        neg = true;
        ++c;
        break;
      case '-':
        if (range == 2) {
          goto inside;
        }
        if (!seen_char) {
          goto inside;
        }
        if (range == 1) {
          FAIL("bad range");
        }
        range = 2;
        ++c;
        break;
      case '[':
        ++c;
        switch (*c) {
        case '.': /* collating element */
          if (range != 0) {
            --range;
          }
          ++c;
          state = parse_ce;
          seen_ce = false;
          break;
        case '=': /* equivalence class */
          if (range == 2) {
            FAIL("equivalence class in "
                 "range");
          }
          ++c;
          state = parse_ec;
          seen_ec = false;
          break;
        case ':': /* character class */
          if (range == 2) {
            FAIL("character class in "
                 "range");
          }
          ccname = c;
          ++c;
          state = parse_cc;
          break;
        }
        seen_char = true;
        break;
      case ']':
        if (!c[1] && !seen_char) {
          FAIL("unfinished brace");
        }
        if (!seen_char) {
          goto inside;
        }
        ++c;
        range = 0;
        have_atom = true;
        state = none;
        break;
      default:
      inside:
        seen_char = true;
        if (range == 2 && (*c & 0xff) < range_start) {
          FAIL("out of order range");
        }
        if (range != 0) {
          --range;
        }
        range_start = *c & 0xff;
        ++c;
        break;
      }
      break;
    case parse_ce:
      switch (*c) {
      case '.':
        ++c;
        switch (*c) {
        case ']':
          if (!seen_ce) {
            FAIL("empty ce");
          }
          ++c;
          state = parse_bracket;
          break;
        default:
          if (seen_ce) {
            range_start = 256;
          } else {
            range_start = '.';
          }
          seen_ce = true;
          break;
        }
        break;
      default:
        if (seen_ce) {
          range_start = 256;
        } else {
          range_start = *c;
        }
        seen_ce = true;
        ++c;
        break;
      }
      break;
    case parse_ec:
      switch (*c) {
      case '=':
        ++c;
        switch (*c) {
        case ']':
          if (!seen_ec) {
            FAIL("no ec");
          }
          ++c;
          state = parse_bracket;
          break;
        default:
          seen_ec = true;
          break;
        }
        break;
      default:
        seen_ec = true;
        ++c;
        break;
      }
      break;
    case parse_cc:
      switch (*c) {
      case ':':
        ++c;
        switch (*c) {
        case ']': {
          unsigned int i;
          bool found = false;
          for (i = 0;
               i < sizeof(cc) / sizeof(*cc); i++)
          {
            unsigned int len;
            len = strlen(cc[i]);
            if (len !=
                (unsigned int)(c - ccname))
            {
              continue;
            }
            if (strncmp(cc[i], ccname, len))
            {
              continue;
            }
            found = true;
          }
          if (!found) {
            FAIL("unknown cc");
          }
          ++c;
          state = parse_bracket;
          break;
        }
        default:
          break;
        }
        break;
      default:
        ++c;
        break;
      }
      break;
    }
  }
  if (group != 0) {
    FAIL("group open");
  }
  if (state != none) {
    FAIL("incomplete");
  }
  if (!have_atom) {
    FAIL("no atom");
  }
  return sub;

error:
#if VALREGEX_REPORT_REASON
  fprintf(stderr, "%s\n", reason);
#endif /* if VALREGEX_REPORT_REASON */
  return -1;
}

Coverage Report

Created: 2026-09-01 06:32

Line	Count	Source
1		/*
2		* Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3		*
4		* SPDX-License-Identifier: MPL-2.0
5		*
6		* This Source Code Form is subject to the terms of the Mozilla Public
7		* License, v. 2.0. If a copy of the MPL was not distributed with this
8		* file, you can obtain one at https://mozilla.org/MPL/2.0/.
9		*
10		* See the COPYRIGHT file distributed with this work for additional
11		* information regarding copyright ownership.
12		*/
13
14		#include <stdbool.h>
15
16		#include <isc/file.h>
17		#include <isc/regex.h>
18		#include <isc/string.h>
19
20		#if VALREGEX_REPORT_REASON
21		#define FAIL(x) \
22		do { \
23		reason = (x); \
24		goto error; \
25		} while (0)
26		#else /* if VALREGEX_REPORT_REASON */
27	1.37k	#define FAIL(x) goto error
28		#endif /* if VALREGEX_REPORT_REASON */
29
30		/*
31		* Validate the regular expression 'C' locale.
32		*/
33		int
34	10.3k	isc_regex_validate(const char *c) {
35	10.3k	enum {
36	10.3k	none,
37	10.3k	parse_bracket,
38	10.3k	parse_bound,
39	10.3k	parse_ce,
40	10.3k	parse_ec,
41	10.3k	parse_cc
42	10.3k	} state = none;
43		/* Well known character classes. */
44	10.3k	const char *cc[] = { ":alnum:", ":digit:", ":punct:", ":alpha:",
45	10.3k	":graph:", ":space:", ":blank:", ":lower:",
46	10.3k	":upper:", ":cntrl:", ":print:", ":xdigit:" };
47	10.3k	bool seen_comma = false;
48	10.3k	bool seen_high = false;
49	10.3k	bool seen_char = false;
50	10.3k	bool seen_ec = false;
51	10.3k	bool seen_ce = false;
52	10.3k	bool have_atom = false;
53	10.3k	int group = 0;
54	10.3k	int range = 0;
55	10.3k	int sub = 0;
56	10.3k	bool empty_ok = false;
57	10.3k	bool neg = false;
58	10.3k	bool was_multiple = false;
59	10.3k	unsigned int low = 0;
60	10.3k	unsigned int high = 0;
61	10.3k	const char *ccname = NULL;
62	10.3k	int range_start = 0;
63		#if VALREGEX_REPORT_REASON
64		const char *reason = "";
65		#endif /* if VALREGEX_REPORT_REASON */
66
67	10.3k	if (c == NULL \|\| *c == 0) {
68	25	FAIL("empty string");
69	25	}
70
71	528k	while (c != NULL && *c != 0) {
72	518k	switch (state) {
73	340k	case none:
74	340k	switch (*c) {
75	13.2k	case '\\': /* make literal */
76	13.2k	++c;
77	13.2k	switch (*c) {
78	1.04k	case '1':
79	1.78k	case '2':
80	2.82k	case '3':
81	3.88k	case '4':
82	5.08k	case '5':
83	5.61k	case '6':
84	6.00k	case '7':
85	6.83k	case '8':
86	8.11k	case '9':
87	8.11k	if ((*c - '0') > sub) {
88	38	FAIL("bad back reference");
89	38	}
90	8.07k	have_atom = true;
91	8.07k	was_multiple = false;
92	8.07k	break;
93	0	case 0:
94	0	FAIL("escaped end-of-string");
95	5.15k	default:
96	5.15k	goto literal;
97	13.2k	}
98	8.07k	++c;
99	8.07k	break;
100	13.2k	case '[': /* bracket start */
101	13.2k	++c;
102	13.2k	neg = false;
103	13.2k	was_multiple = false;
104	13.2k	seen_char = false;
105	13.2k	state = parse_bracket;
106	13.2k	break;
107	16.6k	case '{': /* bound start */
108	16.6k	switch (c[1]) {
109	1.25k	case '0':
110	3.11k	case '1':
111	3.42k	case '2':
112	4.22k	case '3':
113	4.46k	case '4':
114	4.90k	case '5':
115	5.32k	case '6':
116	6.54k	case '7':
117	6.78k	case '8':
118	7.09k	case '9':
119	7.09k	if (!have_atom) {
120	6	FAIL("no atom");
121	6	}
122	7.09k	if (was_multiple) {
123	5	FAIL("was multiple");
124	5	}
125	7.08k	seen_comma = false;
126	7.08k	seen_high = false;
127	7.08k	low = high = 0;
128	7.08k	state = parse_bound;
129	7.08k	break;
130	9.52k	default:
131	9.52k	goto literal;
132	16.6k	}
133	7.08k	++c;
134	7.08k	have_atom = true;
135	7.08k	was_multiple = true;
136	7.08k	break;
137	6.13k	case '}':
138	6.13k	goto literal;
139	34.9k	case '(': /* group start */
140	34.9k	have_atom = false;
141	34.9k	was_multiple = false;
142	34.9k	empty_ok = true;
143	34.9k	++group;
144	34.9k	++sub;
145	34.9k	++c;
146	34.9k	break;
147	44.4k	case ')': /* group end */
148	44.4k	if (group && !have_atom && !empty_ok) {
149	4	FAIL("empty alternative");
150	4	}
151	44.4k	have_atom = true;
152	44.4k	was_multiple = false;
153	44.4k	if (group != 0) {
154	33.3k	--group;
155	33.3k	}
156	44.4k	++c;
157	44.4k	break;
158	1.85k	case '\|': /* alternative separator */
159	1.85k	if (!have_atom) {
160	5	FAIL("no atom");
161	5	}
162	1.84k	have_atom = false;
163	1.84k	empty_ok = false;
164	1.84k	was_multiple = false;
165	1.84k	++c;
166	1.84k	break;
167	2.13k	case '^':
168	5.89k	case '$':
169	5.89k	have_atom = true;
170	5.89k	was_multiple = true;
171	5.89k	++c;
172	5.89k	break;
173	3.28k	case '+':
174	6.85k	case '*':
175	12.0k	case '?':
176	12.0k	if (was_multiple) {
177	41	FAIL("was multiple");
178	41	}
179	12.0k	if (!have_atom) {
180	15	FAIL("no atom");
181	15	}
182	12.0k	have_atom = true;
183	12.0k	was_multiple = true;
184	12.0k	++c;
185	12.0k	break;
186	3.42k	case '.':
187	191k	default:
188	212k	literal:
189	212k	have_atom = true;
190	212k	was_multiple = false;
191	212k	++c;
192	212k	break;
193	340k	}
194	340k	break;
195	340k	case parse_bound:
196	26.0k	switch (*c) {
197	3.29k	case '0':
198	5.96k	case '1':
199	6.74k	case '2':
200	8.12k	case '3':
201	8.97k	case '4':
202	10.2k	case '5':
203	11.9k	case '6':
204	14.9k	case '7':
205	16.3k	case '8':
206	17.4k	case '9':
207	17.4k	if (!seen_comma) {
208	14.1k	low = low * 10 + *c - '0';
209	14.1k	if (low > 255) {
210	45	FAIL("lower bound too big");
211	45	}
212	14.1k	} else {
213	3.33k	seen_high = true;
214	3.33k	high = high * 10 + *c - '0';
215	3.33k	if (high > 255) {
216	25	FAIL("upper bound too big");
217	25	}
218	3.33k	}
219	17.3k	++c;
220	17.3k	break;
221	1.74k	case ',':
222	1.74k	if (seen_comma) {
223	4	FAIL("multiple commas");
224	4	}
225	1.74k	seen_comma = true;
226	1.74k	++c;
227	1.74k	break;
228	23	default:
229	25	case '{':
230	25	FAIL("non digit/comma");
231	6.81k	case '}':
232	6.81k	if (seen_high && low > high) {
233	20	FAIL("bad parse bound");
234	20	}
235	6.79k	seen_comma = false;
236	6.79k	state = none;
237	6.79k	++c;
238	6.79k	break;
239	26.0k	}
240	25.9k	break;
241	112k	case parse_bracket:
242	112k	switch (*c) {
243	4.20k	case '^':
244	4.20k	if (seen_char \|\| neg) {
245	2.64k	goto inside;
246	2.64k	}
247	1.55k	neg = true;
248	1.55k	++c;
249	1.55k	break;
250	8.84k	case '-':
251	8.84k	if (range == 2) {
252	796	goto inside;
253	796	}
254	8.04k	if (!seen_char) {
255	1.62k	goto inside;
256	1.62k	}
257	6.42k	if (range == 1) {
258	5	FAIL("bad range");
259	5	}
260	6.41k	range = 2;
261	6.41k	++c;
262	6.41k	break;
263	14.4k	case '[':
264	14.4k	++c;
265	14.4k	switch (*c) {
266	3.28k	case '.': /* collating element */
267	3.28k	if (range != 0) {
268	1.47k	--range;
269	1.47k	}
270	3.28k	++c;
271	3.28k	state = parse_ce;
272	3.28k	seen_ce = false;
273	3.28k	break;
274	363	case '=': /* equivalence class */
275	363	if (range == 2) {
276	4	FAIL("equivalence class in "
277	4	"range");
278	4	}
279	359	++c;
280	359	state = parse_ec;
281	359	seen_ec = false;
282	359	break;
283	1.41k	case ':': /* character class */
284	1.41k	if (range == 2) {
285	4	FAIL("character class in "
286	4	"range");
287	4	}
288	1.40k	ccname = c;
289	1.40k	++c;
290	1.40k	state = parse_cc;
291	1.40k	break;
292	14.4k	}
293	14.4k	seen_char = true;
294	14.4k	break;
295	14.4k	case ']':
296	14.4k	if (!c[1] && !seen_char) {
297	6	FAIL("unfinished brace");
298	6	}
299	14.4k	if (!seen_char) {
300	1.99k	goto inside;
301	1.99k	}
302	12.4k	++c;
303	12.4k	range = 0;
304	12.4k	have_atom = true;
305	12.4k	state = none;
306	12.4k	break;
307	70.5k	default:
308	77.6k	inside:
309	77.6k	seen_char = true;
310	77.6k	if (range == 2 && (*c & 0xff) < range_start) {
311	24	FAIL("out of order range");
312	24	}
313	77.6k	if (range != 0) {
314	10.1k	--range;
315	10.1k	}
316	77.6k	range_start = *c & 0xff;
317	77.6k	++c;
318	77.6k	break;
319	112k	}
320	112k	break;
321	112k	case parse_ce:
322	26.2k	switch (*c) {
323	9.16k	case '.':
324	9.16k	++c;
325	9.16k	switch (*c) {
326	3.14k	case ']':
327	3.14k	if (!seen_ce) {
328	4	FAIL("empty ce");
329	4	}
330	3.14k	++c;
331	3.14k	state = parse_bracket;
332	3.14k	break;
333	6.02k	default:
334	6.02k	if (seen_ce) {
335	4.48k	range_start = 256;
336	4.48k	} else {
337	1.53k	range_start = '.';
338	1.53k	}
339	6.02k	seen_ce = true;
340	6.02k	break;
341	9.16k	}
342	9.16k	break;
343	17.0k	default:
344	17.0k	if (seen_ce) {
345	15.3k	range_start = 256;
346	15.3k	} else {
347	1.72k	range_start = *c;
348	1.72k	}
349	17.0k	seen_ce = true;
350	17.0k	++c;
351	17.0k	break;
352	26.2k	}
353	26.2k	break;
354	26.2k	case parse_ec:
355	3.90k	switch (*c) {
356	1.06k	case '=':
357	1.06k	++c;
358	1.06k	switch (*c) {
359	268	case ']':
360	268	if (!seen_ec) {
361	4	FAIL("no ec");
362	4	}
363	264	++c;
364	264	state = parse_bracket;
365	264	break;
366	800	default:
367	800	seen_ec = true;
368	800	break;
369	1.06k	}
370	1.06k	break;
371	2.83k	default:
372	2.83k	seen_ec = true;
373	2.83k	++c;
374	2.83k	break;
375	3.90k	}
376	3.89k	break;
377	9.61k	case parse_cc:
378	9.61k	switch (*c) {
379	2.05k	case ':':
380	2.05k	++c;
381	2.05k	switch (*c) {
382	1.32k	case ']': {
383	1.32k	unsigned int i;
384	1.32k	bool found = false;
385	1.32k	for (i = 0;
386	17.1k	i < sizeof(cc) / sizeof(*cc); i++)
387	15.8k	{
388	15.8k	unsigned int len;
389	15.8k	len = strlen(cc[i]);
390	15.8k	if (len !=
391	15.8k	(unsigned int)(c - ccname))
392	2.25k	{
393	2.25k	continue;
394	2.25k	}
395	13.5k	if (strncmp(cc[i], ccname, len))
396	12.4k	{
397	12.4k	continue;
398	12.4k	}
399	1.18k	found = true;
400	1.18k	}
401	1.32k	if (!found) {
402	135	FAIL("unknown cc");
403	135	}
404	1.18k	++c;
405	1.18k	state = parse_bracket;
406	1.18k	break;
407	1.32k	}
408	738	default:
409	738	break;
410	2.05k	}
411	1.92k	break;
412	7.55k	default:
413	7.55k	++c;
414	7.55k	break;
415	9.61k	}
416	9.47k	break;
417	518k	}
418	518k	}
419	9.92k	if (group != 0) {
420	186	FAIL("group open");
421	186	}
422	9.73k	if (state != none) {
423	731	FAIL("incomplete");
424	731	}
425	9.00k	if (!have_atom) {
426	18	FAIL("no atom");
427	18	}
428	8.98k	return sub;
429
430	1.37k	error:
431		#if VALREGEX_REPORT_REASON
432		fprintf(stderr, "%s\n", reason);
433		#endif /* if VALREGEX_REPORT_REASON */
434	1.37k	return -1;
435	9.00k	}