LLVM  7.0.0svn
regcomp.c
Go to the documentation of this file.
1 /*-
2  * This code is derived from OpenBSD's libc/regex, original license follows:
3  *
4  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
5  * Copyright (c) 1992, 1993, 1994
6  * The Regents of the University of California. All rights reserved.
7  *
8  * This code is derived from software contributed to Berkeley by
9  * Henry Spencer.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  * notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  * notice, this list of conditions and the following disclaimer in the
18  * documentation and/or other materials provided with the distribution.
19  * 3. Neither the name of the University nor the names of its contributors
20  * may be used to endorse or promote products derived from this software
21  * without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33  * SUCH DAMAGE.
34  *
35  * @(#)regcomp.c 8.5 (Berkeley) 3/20/94
36  */
37 
38 #include <sys/types.h>
39 #include <stdint.h>
40 #include <stdio.h>
41 #include <string.h>
42 #include <ctype.h>
43 #include <limits.h>
44 #include <stdlib.h>
45 #include "regex_impl.h"
46 
47 #include "regutils.h"
48 #include "regex2.h"
49 
50 #include "llvm/Config/config.h"
51 
52 /* character-class table */
53 static struct cclass {
54  const char *name;
55  const char *chars;
56  const char *multis;
57 } cclasses[] = {
58  { "alnum", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\
59 0123456789", ""} ,
60  { "alpha", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
61  ""} ,
62  { "blank", " \t", ""} ,
63  { "cntrl", "\007\b\t\n\v\f\r\1\2\3\4\5\6\16\17\20\21\22\23\24\
64 \25\26\27\30\31\32\33\34\35\36\37\177", ""} ,
65  { "digit", "0123456789", ""} ,
66  { "graph", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\
67 0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~",
68  ""} ,
69  { "lower", "abcdefghijklmnopqrstuvwxyz",
70  ""} ,
71  { "print", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\
72 0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ ",
73  ""} ,
74  { "punct", "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~",
75  ""} ,
76  { "space", "\t\n\v\f\r ", ""} ,
77  { "upper", "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
78  ""} ,
79  { "xdigit", "0123456789ABCDEFabcdef",
80  ""} ,
81  { NULL, 0, "" }
82 };
83 
84 /* character-name table */
85 static struct cname {
86  const char *name;
87  char code;
88 } cnames[] = {
89  { "NUL", '\0' },
90  { "SOH", '\001' },
91  { "STX", '\002' },
92  { "ETX", '\003' },
93  { "EOT", '\004' },
94  { "ENQ", '\005' },
95  { "ACK", '\006' },
96  { "BEL", '\007' },
97  { "alert", '\007' },
98  { "BS", '\010' },
99  { "backspace", '\b' },
100  { "HT", '\011' },
101  { "tab", '\t' },
102  { "LF", '\012' },
103  { "newline", '\n' },
104  { "VT", '\013' },
105  { "vertical-tab", '\v' },
106  { "FF", '\014' },
107  { "form-feed", '\f' },
108  { "CR", '\015' },
109  { "carriage-return", '\r' },
110  { "SO", '\016' },
111  { "SI", '\017' },
112  { "DLE", '\020' },
113  { "DC1", '\021' },
114  { "DC2", '\022' },
115  { "DC3", '\023' },
116  { "DC4", '\024' },
117  { "NAK", '\025' },
118  { "SYN", '\026' },
119  { "ETB", '\027' },
120  { "CAN", '\030' },
121  { "EM", '\031' },
122  { "SUB", '\032' },
123  { "ESC", '\033' },
124  { "IS4", '\034' },
125  { "FS", '\034' },
126  { "IS3", '\035' },
127  { "GS", '\035' },
128  { "IS2", '\036' },
129  { "RS", '\036' },
130  { "IS1", '\037' },
131  { "US", '\037' },
132  { "space", ' ' },
133  { "exclamation-mark", '!' },
134  { "quotation-mark", '"' },
135  { "number-sign", '#' },
136  { "dollar-sign", '$' },
137  { "percent-sign", '%' },
138  { "ampersand", '&' },
139  { "apostrophe", '\'' },
140  { "left-parenthesis", '(' },
141  { "right-parenthesis", ')' },
142  { "asterisk", '*' },
143  { "plus-sign", '+' },
144  { "comma", ',' },
145  { "hyphen", '-' },
146  { "hyphen-minus", '-' },
147  { "period", '.' },
148  { "full-stop", '.' },
149  { "slash", '/' },
150  { "solidus", '/' },
151  { "zero", '0' },
152  { "one", '1' },
153  { "two", '2' },
154  { "three", '3' },
155  { "four", '4' },
156  { "five", '5' },
157  { "six", '6' },
158  { "seven", '7' },
159  { "eight", '8' },
160  { "nine", '9' },
161  { "colon", ':' },
162  { "semicolon", ';' },
163  { "less-than-sign", '<' },
164  { "equals-sign", '=' },
165  { "greater-than-sign", '>' },
166  { "question-mark", '?' },
167  { "commercial-at", '@' },
168  { "left-square-bracket", '[' },
169  { "backslash", '\\' },
170  { "reverse-solidus", '\\' },
171  { "right-square-bracket", ']' },
172  { "circumflex", '^' },
173  { "circumflex-accent", '^' },
174  { "underscore", '_' },
175  { "low-line", '_' },
176  { "grave-accent", '`' },
177  { "left-brace", '{' },
178  { "left-curly-bracket", '{' },
179  { "vertical-line", '|' },
180  { "right-brace", '}' },
181  { "right-curly-bracket", '}' },
182  { "tilde", '~' },
183  { "DEL", '\177' },
184  { NULL, 0 }
185 };
186 
187 /*
188  * parse structure, passed up and down to avoid global variables and
189  * other clumsinesses
190  */
191 struct parse {
192  char *next; /* next character in RE */
193  char *end; /* end of string (-> NUL normally) */
194  int error; /* has an error been seen? */
195  sop *strip; /* malloced strip */
196  sopno ssize; /* malloced strip size (allocated) */
197  sopno slen; /* malloced strip length (used) */
198  int ncsalloc; /* number of csets allocated */
199  struct re_guts *g;
200 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
201  sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
202  sopno pend[NPAREN]; /* -> ) ([0] unused) */
203 };
204 
205 static void p_ere(struct parse *, int);
206 static void p_ere_exp(struct parse *);
207 static void p_str(struct parse *);
208 static void p_bre(struct parse *, int, int);
209 static int p_simp_re(struct parse *, int);
210 static int p_count(struct parse *);
211 static void p_bracket(struct parse *);
212 static void p_b_term(struct parse *, cset *);
213 static void p_b_cclass(struct parse *, cset *);
214 static void p_b_eclass(struct parse *, cset *);
215 static char p_b_symbol(struct parse *);
216 static char p_b_coll_elem(struct parse *, int);
217 static char othercase(int);
218 static void bothcases(struct parse *, int);
219 static void ordinary(struct parse *, int);
220 static void nonnewline(struct parse *);
221 static void repeat(struct parse *, sopno, int, int);
222 static int seterr(struct parse *, int);
223 static cset *allocset(struct parse *);
224 static void freeset(struct parse *, cset *);
225 static int freezeset(struct parse *, cset *);
226 static int firstch(struct parse *, cset *);
227 static int nch(struct parse *, cset *);
228 static void mcadd(struct parse *, cset *, const char *);
229 static void mcinvert(struct parse *, cset *);
230 static void mccase(struct parse *, cset *);
231 static int isinsets(struct re_guts *, int);
232 static int samesets(struct re_guts *, int, int);
233 static void categorize(struct parse *, struct re_guts *);
234 static sopno dupl(struct parse *, sopno, sopno);
235 static void doemit(struct parse *, sop, size_t);
236 static void doinsert(struct parse *, sop, size_t, sopno);
237 static void dofwd(struct parse *, sopno, sop);
238 static void enlarge(struct parse *, sopno);
239 static void stripsnug(struct parse *, struct re_guts *);
240 static void findmust(struct parse *, struct re_guts *);
241 static sopno pluscount(struct parse *, struct re_guts *);
242 
243 static char nuls[10]; /* place to point scanner in event of error */
244 
245 /*
246  * macros for use with parse structure
247  * BEWARE: these know that the parse structure is named `p' !!!
248  */
249 #define PEEK() (*p->next)
250 #define PEEK2() (*(p->next+1))
251 #define MORE() (p->next < p->end)
252 #define MORE2() (p->next+1 < p->end)
253 #define SEE(c) (MORE() && PEEK() == (c))
254 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
255 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
256 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
257 #define NEXT() (p->next++)
258 #define NEXT2() (p->next += 2)
259 #define NEXTn(n) (p->next += (n))
260 #define GETNEXT() (*p->next++)
261 #define SETERROR(e) seterr(p, (e))
262 #define REQUIRE(co, e) (void)((co) || SETERROR(e))
263 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
264 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
265 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
266 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
267 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
268 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
269 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
270 #define HERE() (p->slen)
271 #define THERE() (p->slen - 1)
272 #define THERETHERE() (p->slen - 2)
273 #define DROP(n) (p->slen -= (n))
274 
275 #ifdef _POSIX2_RE_DUP_MAX
276 #define DUPMAX _POSIX2_RE_DUP_MAX
277 #else
278 #define DUPMAX 255
279 #endif
280 #define INFINITY (DUPMAX + 1)
281 
282 #ifndef NDEBUG
283 static int never = 0; /* for use in asserts; shuts lint up */
284 #else
285 #define never 0 /* some <assert.h>s have bugs too */
286 #endif
287 
288 /*
289  - llvm_regcomp - interface for parser and compilation
290  */
291 int /* 0 success, otherwise REG_something */
292 llvm_regcomp(llvm_regex_t *preg, const char *pattern, int cflags)
293 {
294  struct parse pa;
295  struct re_guts *g;
296  struct parse *p = &pa;
297  int i;
298  size_t len;
299 #ifdef REDEBUG
300 # define GOODFLAGS(f) (f)
301 #else
302 # define GOODFLAGS(f) ((f)&~REG_DUMP)
303 #endif
304 
305  cflags = GOODFLAGS(cflags);
306  if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
307  return(REG_INVARG);
308 
309  if (cflags&REG_PEND) {
310  if (preg->re_endp < pattern)
311  return(REG_INVARG);
312  len = preg->re_endp - pattern;
313  } else
314  len = strlen((const char *)pattern);
315 
316  /* do the mallocs early so failure handling is easy */
317  g = (struct re_guts *)malloc(sizeof(struct re_guts) +
318  (NC-1)*sizeof(cat_t));
319  if (g == NULL)
320  return(REG_ESPACE);
321  p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
322  p->strip = (sop *)calloc(p->ssize, sizeof(sop));
323  p->slen = 0;
324  if (p->strip == NULL) {
325  free((char *)g);
326  return(REG_ESPACE);
327  }
328 
329  /* set things up */
330  p->g = g;
331  p->next = (char *)pattern; /* convenience; we do not modify it */
332  p->end = p->next + len;
333  p->error = 0;
334  p->ncsalloc = 0;
335  for (i = 0; i < NPAREN; i++) {
336  p->pbegin[i] = 0;
337  p->pend[i] = 0;
338  }
339  g->csetsize = NC;
340  g->sets = NULL;
341  g->setbits = NULL;
342  g->ncsets = 0;
343  g->cflags = cflags;
344  g->iflags = 0;
345  g->nbol = 0;
346  g->neol = 0;
347  g->must = NULL;
348  g->mlen = 0;
349  g->nsub = 0;
350  g->ncategories = 1; /* category 0 is "everything else" */
351  g->categories = &g->catspace[-(CHAR_MIN)];
352  (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t));
353  g->backrefs = 0;
354 
355  /* do it */
356  EMIT(OEND, 0);
357  g->firststate = THERE();
358  if (cflags&REG_EXTENDED)
359  p_ere(p, OUT);
360  else if (cflags&REG_NOSPEC)
361  p_str(p);
362  else
363  p_bre(p, OUT, OUT);
364  EMIT(OEND, 0);
365  g->laststate = THERE();
366 
367  /* tidy up loose ends and fill things in */
368  categorize(p, g);
369  stripsnug(p, g);
370  findmust(p, g);
371  g->nplus = pluscount(p, g);
372  g->magic = MAGIC2;
373  preg->re_nsub = g->nsub;
374  preg->re_g = g;
375  preg->re_magic = MAGIC1;
376 #ifndef REDEBUG
377  /* not debugging, so can't rely on the assert() in llvm_regexec() */
378  if (g->iflags&REGEX_BAD)
380 #endif
381 
382  /* win or lose, we're done */
383  if (p->error != 0) /* lose */
384  llvm_regfree(preg);
385  return(p->error);
386 }
387 
388 /*
389  - p_ere - ERE parser top level, concatenation and alternation
390  */
391 static void
392 p_ere(struct parse *p, int stop) /* character this ERE should end at */
393 {
394  char c;
395  sopno prevback = 0;
396  sopno prevfwd = 0;
397  sopno conc;
398  int first = 1; /* is this the first alternative? */
399 
400  for (;;) {
401  /* do a bunch of concatenated expressions */
402  conc = HERE();
403  while (MORE() && (c = PEEK()) != '|' && c != stop)
404  p_ere_exp(p);
405  REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */
406 
407  if (!EAT('|'))
408  break; /* NOTE BREAK OUT */
409 
410  if (first) {
411  INSERT(OCH_, conc); /* offset is wrong */
412  prevfwd = conc;
413  prevback = conc;
414  first = 0;
415  }
416  ASTERN(OOR1, prevback);
417  prevback = THERE();
418  AHEAD(prevfwd); /* fix previous offset */
419  prevfwd = HERE();
420  EMIT(OOR2, 0); /* offset is very wrong */
421  }
422 
423  if (!first) { /* tail-end fixups */
424  AHEAD(prevfwd);
425  ASTERN(O_CH, prevback);
426  }
427 
428  assert(!MORE() || SEE(stop));
429 }
430 
431 /*
432  - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
433  */
434 static void
435 p_ere_exp(struct parse *p)
436 {
437  char c;
438  sopno pos;
439  int count;
440  int count2;
441  int backrefnum;
442  sopno subno;
443  int wascaret = 0;
444 
445  assert(MORE()); /* caller should have ensured this */
446  c = GETNEXT();
447 
448  pos = HERE();
449  switch (c) {
450  case '(':
451  REQUIRE(MORE(), REG_EPAREN);
452  p->g->nsub++;
453  subno = p->g->nsub;
454  if (subno < NPAREN)
455  p->pbegin[subno] = HERE();
456  EMIT(OLPAREN, subno);
457  if (!SEE(')'))
458  p_ere(p, ')');
459  if (subno < NPAREN) {
460  p->pend[subno] = HERE();
461  assert(p->pend[subno] != 0);
462  }
463  EMIT(ORPAREN, subno);
464  MUSTEAT(')', REG_EPAREN);
465  break;
466 #ifndef POSIX_MISTAKE
467  case ')': /* happens only if no current unmatched ( */
468  /*
469  * You may ask, why the ifndef? Because I didn't notice
470  * this until slightly too late for 1003.2, and none of the
471  * other 1003.2 regular-expression reviewers noticed it at
472  * all. So an unmatched ) is legal POSIX, at least until
473  * we can get it fixed.
474  */
476  break;
477 #endif
478  case '^':
479  EMIT(OBOL, 0);
480  p->g->iflags |= USEBOL;
481  p->g->nbol++;
482  wascaret = 1;
483  break;
484  case '$':
485  EMIT(OEOL, 0);
486  p->g->iflags |= USEEOL;
487  p->g->neol++;
488  break;
489  case '|':
491  break;
492  case '*':
493  case '+':
494  case '?':
496  break;
497  case '.':
498  if (p->g->cflags&REG_NEWLINE)
499  nonnewline(p);
500  else
501  EMIT(OANY, 0);
502  break;
503  case '[':
504  p_bracket(p);
505  break;
506  case '\\':
508  c = GETNEXT();
509  if (c >= '1' && c <= '9') {
510  /* \[0-9] is taken to be a back-reference to a previously specified
511  * matching group. backrefnum will hold the number. The matching
512  * group must exist (i.e. if \4 is found there must have been at
513  * least 4 matching groups specified in the pattern previously).
514  */
515  backrefnum = c - '0';
516  if (p->pend[backrefnum] == 0) {
518  break;
519  }
520 
521  /* Make sure everything checks out and emit the sequence
522  * that marks a back-reference to the parse structure.
523  */
524  assert(backrefnum <= p->g->nsub);
525  EMIT(OBACK_, backrefnum);
526  assert(p->pbegin[backrefnum] != 0);
527  assert(OP(p->strip[p->pbegin[backrefnum]]) != OLPAREN);
528  assert(OP(p->strip[p->pend[backrefnum]]) != ORPAREN);
529  (void) dupl(p, p->pbegin[backrefnum]+1, p->pend[backrefnum]);
530  EMIT(O_BACK, backrefnum);
531  p->g->backrefs = 1;
532  } else {
533  /* Other chars are simply themselves when escaped with a backslash.
534  */
535  ordinary(p, c);
536  }
537  break;
538  case '{': /* okay as ordinary except if digit follows */
539  REQUIRE(!MORE() || !isdigit((uch)PEEK()), REG_BADRPT);
540  /* FALLTHROUGH */
541  default:
542  ordinary(p, c);
543  break;
544  }
545 
546  if (!MORE())
547  return;
548  c = PEEK();
549  /* we call { a repetition if followed by a digit */
550  if (!( c == '*' || c == '+' || c == '?' ||
551  (c == '{' && MORE2() && isdigit((uch)PEEK2())) ))
552  return; /* no repetition, we're done */
553  NEXT();
554 
555  REQUIRE(!wascaret, REG_BADRPT);
556  switch (c) {
557  case '*': /* implemented as +? */
558  /* this case does not require the (y|) trick, noKLUDGE */
559  INSERT(OPLUS_, pos);
560  ASTERN(O_PLUS, pos);
561  INSERT(OQUEST_, pos);
562  ASTERN(O_QUEST, pos);
563  break;
564  case '+':
565  INSERT(OPLUS_, pos);
566  ASTERN(O_PLUS, pos);
567  break;
568  case '?':
569  /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
570  INSERT(OCH_, pos); /* offset slightly wrong */
571  ASTERN(OOR1, pos); /* this one's right */
572  AHEAD(pos); /* fix the OCH_ */
573  EMIT(OOR2, 0); /* offset very wrong... */
574  AHEAD(THERE()); /* ...so fix it */
575  ASTERN(O_CH, THERETHERE());
576  break;
577  case '{':
578  count = p_count(p);
579  if (EAT(',')) {
580  if (isdigit((uch)PEEK())) {
581  count2 = p_count(p);
582  REQUIRE(count <= count2, REG_BADBR);
583  } else /* single number with comma */
584  count2 = INFINITY;
585  } else /* just a single number */
586  count2 = count;
587  repeat(p, pos, count, count2);
588  if (!EAT('}')) { /* error heuristics */
589  while (MORE() && PEEK() != '}')
590  NEXT();
591  REQUIRE(MORE(), REG_EBRACE);
593  }
594  break;
595  }
596 
597  if (!MORE())
598  return;
599  c = PEEK();
600  if (!( c == '*' || c == '+' || c == '?' ||
601  (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) )
602  return;
604 }
605 
606 /*
607  - p_str - string (no metacharacters) "parser"
608  */
609 static void
610 p_str(struct parse *p)
611 {
612  REQUIRE(MORE(), REG_EMPTY);
613  while (MORE())
614  ordinary(p, GETNEXT());
615 }
616 
617 /*
618  - p_bre - BRE parser top level, anchoring and concatenation
619  * Giving end1 as OUT essentially eliminates the end1/end2 check.
620  *
621  * This implementation is a bit of a kludge, in that a trailing $ is first
622  * taken as an ordinary character and then revised to be an anchor. The
623  * only undesirable side effect is that '$' gets included as a character
624  * category in such cases. This is fairly harmless; not worth fixing.
625  * The amount of lookahead needed to avoid this kludge is excessive.
626  */
627 static void
628 p_bre(struct parse *p,
629  int end1, /* first terminating character */
630  int end2) /* second terminating character */
631 {
632  sopno start = HERE();
633  int first = 1; /* first subexpression? */
634  int wasdollar = 0;
635 
636  if (EAT('^')) {
637  EMIT(OBOL, 0);
638  p->g->iflags |= USEBOL;
639  p->g->nbol++;
640  }
641  while (MORE() && !SEETWO(end1, end2)) {
642  wasdollar = p_simp_re(p, first);
643  first = 0;
644  }
645  if (wasdollar) { /* oops, that was a trailing anchor */
646  DROP(1);
647  EMIT(OEOL, 0);
648  p->g->iflags |= USEEOL;
649  p->g->neol++;
650  }
651 
652  REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */
653 }
654 
655 /*
656  - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
657  */
658 static int /* was the simple RE an unbackslashed $? */
659 p_simp_re(struct parse *p,
660  int starordinary) /* is a leading * an ordinary character? */
661 {
662  int c;
663  int count;
664  int count2;
665  sopno pos;
666  int i;
667  sopno subno;
668 # define BACKSL (1<<CHAR_BIT)
669 
670  pos = HERE(); /* repetition op, if any, covers from here */
671 
672  assert(MORE()); /* caller should have ensured this */
673  c = GETNEXT();
674  if (c == '\\') {
676  c = BACKSL | GETNEXT();
677  }
678  switch (c) {
679  case '.':
680  if (p->g->cflags&REG_NEWLINE)
681  nonnewline(p);
682  else
683  EMIT(OANY, 0);
684  break;
685  case '[':
686  p_bracket(p);
687  break;
688  case BACKSL|'{':
690  break;
691  case BACKSL|'(':
692  p->g->nsub++;
693  subno = p->g->nsub;
694  if (subno < NPAREN)
695  p->pbegin[subno] = HERE();
696  EMIT(OLPAREN, subno);
697  /* the MORE here is an error heuristic */
698  if (MORE() && !SEETWO('\\', ')'))
699  p_bre(p, '\\', ')');
700  if (subno < NPAREN) {
701  p->pend[subno] = HERE();
702  assert(p->pend[subno] != 0);
703  }
704  EMIT(ORPAREN, subno);
705  REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
706  break;
707  case BACKSL|')': /* should not get here -- must be user */
708  case BACKSL|'}':
710  break;
711  case BACKSL|'1':
712  case BACKSL|'2':
713  case BACKSL|'3':
714  case BACKSL|'4':
715  case BACKSL|'5':
716  case BACKSL|'6':
717  case BACKSL|'7':
718  case BACKSL|'8':
719  case BACKSL|'9':
720  i = (c&~BACKSL) - '0';
721  assert(i < NPAREN);
722  if (p->pend[i] != 0) {
723  assert(i <= p->g->nsub);
724  EMIT(OBACK_, i);
725  assert(p->pbegin[i] != 0);
726  assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
727  assert(OP(p->strip[p->pend[i]]) == ORPAREN);
728  (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
729  EMIT(O_BACK, i);
730  } else
732  p->g->backrefs = 1;
733  break;
734  case '*':
735  REQUIRE(starordinary, REG_BADRPT);
736  /* FALLTHROUGH */
737  default:
738  ordinary(p, (char)c);
739  break;
740  }
741 
742  if (EAT('*')) { /* implemented as +? */
743  /* this case does not require the (y|) trick, noKLUDGE */
744  INSERT(OPLUS_, pos);
745  ASTERN(O_PLUS, pos);
746  INSERT(OQUEST_, pos);
747  ASTERN(O_QUEST, pos);
748  } else if (EATTWO('\\', '{')) {
749  count = p_count(p);
750  if (EAT(',')) {
751  if (MORE() && isdigit((uch)PEEK())) {
752  count2 = p_count(p);
753  REQUIRE(count <= count2, REG_BADBR);
754  } else /* single number with comma */
755  count2 = INFINITY;
756  } else /* just a single number */
757  count2 = count;
758  repeat(p, pos, count, count2);
759  if (!EATTWO('\\', '}')) { /* error heuristics */
760  while (MORE() && !SEETWO('\\', '}'))
761  NEXT();
762  REQUIRE(MORE(), REG_EBRACE);
764  }
765  } else if (c == '$') /* $ (but not \$) ends it */
766  return(1);
767 
768  return(0);
769 }
770 
771 /*
772  - p_count - parse a repetition count
773  */
774 static int /* the value */
775 p_count(struct parse *p)
776 {
777  int count = 0;
778  int ndigits = 0;
779 
780  while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {
781  count = count*10 + (GETNEXT() - '0');
782  ndigits++;
783  }
784 
785  REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
786  return(count);
787 }
788 
789 /*
790  - p_bracket - parse a bracketed character list
791  *
792  * Note a significant property of this code: if the allocset() did SETERROR,
793  * no set operations are done.
794  */
795 static void
796 p_bracket(struct parse *p)
797 {
798  cset *cs;
799  int invert = 0;
800 
801  /* Dept of Truly Sickening Special-Case Kludges */
802  if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
803  EMIT(OBOW, 0);
804  NEXTn(6);
805  return;
806  }
807  if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
808  EMIT(OEOW, 0);
809  NEXTn(6);
810  return;
811  }
812 
813  if ((cs = allocset(p)) == NULL) {
814  /* allocset did set error status in p */
815  return;
816  }
817 
818  if (EAT('^'))
819  invert++; /* make note to invert set at end */
820  if (EAT(']'))
821  CHadd(cs, ']');
822  else if (EAT('-'))
823  CHadd(cs, '-');
824  while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
825  p_b_term(p, cs);
826  if (EAT('-'))
827  CHadd(cs, '-');
828  MUSTEAT(']', REG_EBRACK);
829 
830  if (p->error != 0) { /* don't mess things up further */
831  freeset(p, cs);
832  return;
833  }
834 
835  if (p->g->cflags&REG_ICASE) {
836  int i;
837  int ci;
838 
839  for (i = p->g->csetsize - 1; i >= 0; i--)
840  if (CHIN(cs, i) && isalpha(i)) {
841  ci = othercase(i);
842  if (ci != i)
843  CHadd(cs, ci);
844  }
845  if (cs->multis != NULL)
846  mccase(p, cs);
847  }
848  if (invert) {
849  int i;
850 
851  for (i = p->g->csetsize - 1; i >= 0; i--)
852  if (CHIN(cs, i))
853  CHsub(cs, i);
854  else
855  CHadd(cs, i);
856  if (p->g->cflags&REG_NEWLINE)
857  CHsub(cs, '\n');
858  if (cs->multis != NULL)
859  mcinvert(p, cs);
860  }
861 
862  assert(cs->multis == NULL); /* xxx */
863 
864  if (nch(p, cs) == 1) { /* optimize singleton sets */
865  ordinary(p, firstch(p, cs));
866  freeset(p, cs);
867  } else
868  EMIT(OANYOF, freezeset(p, cs));
869 }
870 
871 /*
872  - p_b_term - parse one term of a bracketed character list
873  */
874 static void
875 p_b_term(struct parse *p, cset *cs)
876 {
877  char c;
878  char start, finish;
879  int i;
880 
881  /* classify what we've got */
882  switch ((MORE()) ? PEEK() : '\0') {
883  case '[':
884  c = (MORE2()) ? PEEK2() : '\0';
885  break;
886  case '-':
888  return; /* NOTE RETURN */
889  break;
890  default:
891  c = '\0';
892  break;
893  }
894 
895  switch (c) {
896  case ':': /* character class */
897  NEXT2();
898  REQUIRE(MORE(), REG_EBRACK);
899  c = PEEK();
900  REQUIRE(c != '-' && c != ']', REG_ECTYPE);
901  p_b_cclass(p, cs);
902  REQUIRE(MORE(), REG_EBRACK);
903  REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
904  break;
905  case '=': /* equivalence class */
906  NEXT2();
907  REQUIRE(MORE(), REG_EBRACK);
908  c = PEEK();
909  REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
910  p_b_eclass(p, cs);
911  REQUIRE(MORE(), REG_EBRACK);
912  REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
913  break;
914  default: /* symbol, ordinary character, or range */
915 /* xxx revision needed for multichar stuff */
916  start = p_b_symbol(p);
917  if (SEE('-') && MORE2() && PEEK2() != ']') {
918  /* range */
919  NEXT();
920  if (EAT('-'))
921  finish = '-';
922  else
923  finish = p_b_symbol(p);
924  } else
925  finish = start;
926 /* xxx what about signed chars here... */
927  REQUIRE(start <= finish, REG_ERANGE);
928  for (i = start; i <= finish; i++)
929  CHadd(cs, i);
930  break;
931  }
932 }
933 
934 /*
935  - p_b_cclass - parse a character-class name and deal with it
936  */
937 static void
938 p_b_cclass(struct parse *p, cset *cs)
939 {
940  char *sp = p->next;
941  struct cclass *cp;
942  size_t len;
943  const char *u;
944  char c;
945 
946  while (MORE() && isalpha((uch)PEEK()))
947  NEXT();
948  len = p->next - sp;
949  for (cp = cclasses; cp->name != NULL; cp++)
950  if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
951  break;
952  if (cp->name == NULL) {
953  /* oops, didn't find it */
955  return;
956  }
957 
958  u = cp->chars;
959  while ((c = *u++) != '\0')
960  CHadd(cs, c);
961  for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
962  MCadd(p, cs, u);
963 }
964 
965 /*
966  - p_b_eclass - parse an equivalence-class name and deal with it
967  *
968  * This implementation is incomplete. xxx
969  */
970 static void
971 p_b_eclass(struct parse *p, cset *cs)
972 {
973  char c;
974 
975  c = p_b_coll_elem(p, '=');
976  CHadd(cs, c);
977 }
978 
979 /*
980  - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
981  */
982 static char /* value of symbol */
983 p_b_symbol(struct parse *p)
984 {
985  char value;
986 
987  REQUIRE(MORE(), REG_EBRACK);
988  if (!EATTWO('[', '.'))
989  return(GETNEXT());
990 
991  /* collating symbol */
992  value = p_b_coll_elem(p, '.');
993  REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
994  return(value);
995 }
996 
997 /*
998  - p_b_coll_elem - parse a collating-element name and look it up
999  */
1000 static char /* value of collating element */
1002  int endc) /* name ended by endc,']' */
1003 {
1004  char *sp = p->next;
1005  struct cname *cp;
1006  size_t len;
1007 
1008  while (MORE() && !SEETWO(endc, ']'))
1009  NEXT();
1010  if (!MORE()) {
1012  return(0);
1013  }
1014  len = p->next - sp;
1015  for (cp = cnames; cp->name != NULL; cp++)
1016  if (strncmp(cp->name, sp, len) == 0 && strlen(cp->name) == len)
1017  return(cp->code); /* known name */
1018  if (len == 1)
1019  return(*sp); /* single character */
1020  SETERROR(REG_ECOLLATE); /* neither */
1021  return(0);
1022 }
1023 
1024 /*
1025  - othercase - return the case counterpart of an alphabetic
1026  */
1027 static char /* if no counterpart, return ch */
1028 othercase(int ch)
1029 {
1030  ch = (uch)ch;
1031  assert(isalpha(ch));
1032  if (isupper(ch))
1033  return ((uch)tolower(ch));
1034  else if (islower(ch))
1035  return ((uch)toupper(ch));
1036  else /* peculiar, but could happen */
1037  return(ch);
1038 }
1039 
1040 /*
1041  - bothcases - emit a dualcase version of a two-case character
1042  *
1043  * Boy, is this implementation ever a kludge...
1044  */
1045 static void
1046 bothcases(struct parse *p, int ch)
1047 {
1048  char *oldnext = p->next;
1049  char *oldend = p->end;
1050  char bracket[3];
1051 
1052  ch = (uch)ch;
1053  assert(othercase(ch) != ch); /* p_bracket() would recurse */
1054  p->next = bracket;
1055  p->end = bracket+2;
1056  bracket[0] = ch;
1057  bracket[1] = ']';
1058  bracket[2] = '\0';
1059  p_bracket(p);
1060  assert(p->next == bracket+2);
1061  p->next = oldnext;
1062  p->end = oldend;
1063 }
1064 
1065 /*
1066  - ordinary - emit an ordinary character
1067  */
1068 static void
1069 ordinary(struct parse *p, int ch)
1070 {
1071  cat_t *cap = p->g->categories;
1072 
1073  if ((p->g->cflags&REG_ICASE) && isalpha((uch)ch) && othercase(ch) != ch)
1074  bothcases(p, ch);
1075  else {
1076  EMIT(OCHAR, (uch)ch);
1077  if (cap[ch] == 0)
1078  cap[ch] = p->g->ncategories++;
1079  }
1080 }
1081 
1082 /*
1083  - nonnewline - emit REG_NEWLINE version of OANY
1084  *
1085  * Boy, is this implementation ever a kludge...
1086  */
1087 static void
1088 nonnewline(struct parse *p)
1089 {
1090  char *oldnext = p->next;
1091  char *oldend = p->end;
1092  char bracket[4];
1093 
1094  p->next = bracket;
1095  p->end = bracket+3;
1096  bracket[0] = '^';
1097  bracket[1] = '\n';
1098  bracket[2] = ']';
1099  bracket[3] = '\0';
1100  p_bracket(p);
1101  assert(p->next == bracket+3);
1102  p->next = oldnext;
1103  p->end = oldend;
1104 }
1105 
1106 /*
1107  - repeat - generate code for a bounded repetition, recursively if needed
1108  */
1109 static void
1110 repeat(struct parse *p,
1111  sopno start, /* operand from here to end of strip */
1112  int from, /* repeated from this number */
1113  int to) /* to this number of times (maybe INFINITY) */
1114 {
1115  sopno finish = HERE();
1116 # define N 2
1117 # define INF 3
1118 # define REP(f, t) ((f)*8 + (t))
1119 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1120  sopno copy;
1121 
1122  if (p->error != 0) /* head off possible runaway recursion */
1123  return;
1124 
1125  assert(from <= to);
1126 
1127  switch (REP(MAP(from), MAP(to))) {
1128  case REP(0, 0): /* must be user doing this */
1129  DROP(finish-start); /* drop the operand */
1130  break;
1131  case REP(0, 1): /* as x{1,1}? */
1132  case REP(0, N): /* as x{1,n}? */
1133  case REP(0, INF): /* as x{1,}? */
1134  /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1135  INSERT(OCH_, start); /* offset is wrong... */
1136  repeat(p, start+1, 1, to);
1137  ASTERN(OOR1, start);
1138  AHEAD(start); /* ... fix it */
1139  EMIT(OOR2, 0);
1140  AHEAD(THERE());
1141  ASTERN(O_CH, THERETHERE());
1142  break;
1143  case REP(1, 1): /* trivial case */
1144  /* done */
1145  break;
1146  case REP(1, N): /* as x?x{1,n-1} */
1147  /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1148  INSERT(OCH_, start);
1149  ASTERN(OOR1, start);
1150  AHEAD(start);
1151  EMIT(OOR2, 0); /* offset very wrong... */
1152  AHEAD(THERE()); /* ...so fix it */
1153  ASTERN(O_CH, THERETHERE());
1154  copy = dupl(p, start+1, finish+1);
1155  assert(copy == finish+4);
1156  repeat(p, copy, 1, to-1);
1157  break;
1158  case REP(1, INF): /* as x+ */
1159  INSERT(OPLUS_, start);
1160  ASTERN(O_PLUS, start);
1161  break;
1162  case REP(N, N): /* as xx{m-1,n-1} */
1163  copy = dupl(p, start, finish);
1164  repeat(p, copy, from-1, to-1);
1165  break;
1166  case REP(N, INF): /* as xx{n-1,INF} */
1167  copy = dupl(p, start, finish);
1168  repeat(p, copy, from-1, to);
1169  break;
1170  default: /* "can't happen" */
1171  SETERROR(REG_ASSERT); /* just in case */
1172  break;
1173  }
1174 }
1175 
1176 /*
1177  - seterr - set an error condition
1178  */
1179 static int /* useless but makes type checking happy */
1180 seterr(struct parse *p, int e)
1181 {
1182  if (p->error == 0) /* keep earliest error condition */
1183  p->error = e;
1184  p->next = nuls; /* try to bring things to a halt */
1185  p->end = nuls;
1186  return(0); /* make the return value well-defined */
1187 }
1188 
1189 /*
1190  - allocset - allocate a set of characters for []
1191  */
1192 static cset *
1193 allocset(struct parse *p)
1194 {
1195  int no = p->g->ncsets++;
1196  size_t nc;
1197  size_t nbytes;
1198  cset *cs;
1199  size_t css = (size_t)p->g->csetsize;
1200  int i;
1201 
1202  if (no >= p->ncsalloc) { /* need another column of space */
1203  void *ptr;
1204 
1205  p->ncsalloc += CHAR_BIT;
1206  nc = p->ncsalloc;
1207  if (nc > SIZE_MAX / sizeof(cset))
1208  goto nomem;
1209  assert(nc % CHAR_BIT == 0);
1210  nbytes = nc / CHAR_BIT * css;
1211 
1212  ptr = (cset *)realloc((char *)p->g->sets, nc * sizeof(cset));
1213  if (ptr == NULL)
1214  goto nomem;
1215  p->g->sets = ptr;
1216 
1217  ptr = (uch *)realloc((char *)p->g->setbits, nbytes);
1218  if (ptr == NULL)
1219  goto nomem;
1220  p->g->setbits = ptr;
1221 
1222  for (i = 0; i < no; i++)
1223  p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
1224 
1225  (void) memset((char *)p->g->setbits + (nbytes - css), 0, css);
1226  }
1227  /* XXX should not happen */
1228  if (p->g->sets == NULL || p->g->setbits == NULL)
1229  goto nomem;
1230 
1231  cs = &p->g->sets[no];
1232  cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
1233  cs->mask = 1 << ((no) % CHAR_BIT);
1234  cs->hash = 0;
1235  cs->smultis = 0;
1236  cs->multis = NULL;
1237 
1238  return(cs);
1239 nomem:
1240  free(p->g->sets);
1241  p->g->sets = NULL;
1242  free(p->g->setbits);
1243  p->g->setbits = NULL;
1244 
1246  /* caller's responsibility not to do set ops */
1247  return(NULL);
1248 }
1249 
1250 /*
1251  - freeset - free a now-unused set
1252  */
1253 static void
1254 freeset(struct parse *p, cset *cs)
1255 {
1256  size_t i;
1257  cset *top = &p->g->sets[p->g->ncsets];
1258  size_t css = (size_t)p->g->csetsize;
1259 
1260  for (i = 0; i < css; i++)
1261  CHsub(cs, i);
1262  if (cs == top-1) /* recover only the easy case */
1263  p->g->ncsets--;
1264 }
1265 
1266 /*
1267  - freezeset - final processing on a set of characters
1268  *
1269  * The main task here is merging identical sets. This is usually a waste
1270  * of time (although the hash code minimizes the overhead), but can win
1271  * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
1272  * is done using addition rather than xor -- all ASCII [aA] sets xor to
1273  * the same value!
1274  */
1275 static int /* set number */
1276 freezeset(struct parse *p, cset *cs)
1277 {
1278  uch h = cs->hash;
1279  size_t i;
1280  cset *top = &p->g->sets[p->g->ncsets];
1281  cset *cs2;
1282  size_t css = (size_t)p->g->csetsize;
1283 
1284  /* look for an earlier one which is the same */
1285  for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
1286  if (cs2->hash == h && cs2 != cs) {
1287  /* maybe */
1288  for (i = 0; i < css; i++)
1289  if (!!CHIN(cs2, i) != !!CHIN(cs, i))
1290  break; /* no */
1291  if (i == css)
1292  break; /* yes */
1293  }
1294 
1295  if (cs2 < top) { /* found one */
1296  freeset(p, cs);
1297  cs = cs2;
1298  }
1299 
1300  return((int)(cs - p->g->sets));
1301 }
1302 
1303 /*
1304  - firstch - return first character in a set (which must have at least one)
1305  */
1306 static int /* character; there is no "none" value */
1307 firstch(struct parse *p, cset *cs)
1308 {
1309  size_t i;
1310  size_t css = (size_t)p->g->csetsize;
1311 
1312  for (i = 0; i < css; i++)
1313  if (CHIN(cs, i))
1314  return((char)i);
1315  assert(never);
1316  return(0); /* arbitrary */
1317 }
1318 
1319 /*
1320  - nch - number of characters in a set
1321  */
1322 static int
1323 nch(struct parse *p, cset *cs)
1324 {
1325  size_t i;
1326  size_t css = (size_t)p->g->csetsize;
1327  int n = 0;
1328 
1329  for (i = 0; i < css; i++)
1330  if (CHIN(cs, i))
1331  n++;
1332  return(n);
1333 }
1334 
1335 /*
1336  - mcadd - add a collating element to a cset
1337  */
1338 static void
1339 mcadd( struct parse *p, cset *cs, const char *cp)
1340 {
1341  size_t oldend = cs->smultis;
1342  void *np;
1343 
1344  cs->smultis += strlen(cp) + 1;
1345  np = realloc(cs->multis, cs->smultis);
1346  if (np == NULL) {
1347  if (cs->multis)
1348  free(cs->multis);
1349  cs->multis = NULL;
1351  return;
1352  }
1353  cs->multis = np;
1354 
1355  llvm_strlcpy(cs->multis + oldend - 1, cp, cs->smultis - oldend + 1);
1356 }
1357 
1358 /*
1359  - mcinvert - invert the list of collating elements in a cset
1360  *
1361  * This would have to know the set of possibilities. Implementation
1362  * is deferred.
1363  */
1364 /* ARGSUSED */
1365 static void
1366 mcinvert(struct parse *p, cset *cs)
1367 {
1368  assert(cs->multis == NULL); /* xxx */
1369 }
1370 
1371 /*
1372  - mccase - add case counterparts of the list of collating elements in a cset
1373  *
1374  * This would have to know the set of possibilities. Implementation
1375  * is deferred.
1376  */
1377 /* ARGSUSED */
1378 static void
1379 mccase(struct parse *p, cset *cs)
1380 {
1381  assert(cs->multis == NULL); /* xxx */
1382 }
1383 
1384 /*
1385  - isinsets - is this character in any sets?
1386  */
1387 static int /* predicate */
1388 isinsets(struct re_guts *g, int c)
1389 {
1390  uch *col;
1391  int i;
1392  int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1393  unsigned uc = (uch)c;
1394 
1395  for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1396  if (col[uc] != 0)
1397  return(1);
1398  return(0);
1399 }
1400 
1401 /*
1402  - samesets - are these two characters in exactly the same sets?
1403  */
1404 static int /* predicate */
1405 samesets(struct re_guts *g, int c1, int c2)
1406 {
1407  uch *col;
1408  int i;
1409  int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1410  unsigned uc1 = (uch)c1;
1411  unsigned uc2 = (uch)c2;
1412 
1413  for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1414  if (col[uc1] != col[uc2])
1415  return(0);
1416  return(1);
1417 }
1418 
1419 /*
1420  - categorize - sort out character categories
1421  */
1422 static void
1423 categorize(struct parse *p, struct re_guts *g)
1424 {
1425  cat_t *cats = g->categories;
1426  int c;
1427  int c2;
1428  cat_t cat;
1429 
1430  /* avoid making error situations worse */
1431  if (p->error != 0)
1432  return;
1433 
1434  for (c = CHAR_MIN; c <= CHAR_MAX; c++)
1435  if (cats[c] == 0 && isinsets(g, c)) {
1436  cat = g->ncategories++;
1437  cats[c] = cat;
1438  for (c2 = c+1; c2 <= CHAR_MAX; c2++)
1439  if (cats[c2] == 0 && samesets(g, c, c2))
1440  cats[c2] = cat;
1441  }
1442 }
1443 
1444 /*
1445  - dupl - emit a duplicate of a bunch of sops
1446  */
1447 static sopno /* start of duplicate */
1448 dupl(struct parse *p,
1449  sopno start, /* from here */
1450  sopno finish) /* to this less one */
1451 {
1452  sopno ret = HERE();
1453  sopno len = finish - start;
1454 
1455  assert(finish >= start);
1456  if (len == 0)
1457  return(ret);
1458  enlarge(p, p->ssize + len); /* this many unexpected additions */
1459  assert(p->ssize >= p->slen + len);
1460  (void) memmove((char *)(p->strip + p->slen),
1461  (char *)(p->strip + start), (size_t)len*sizeof(sop));
1462  p->slen += len;
1463  return(ret);
1464 }
1465 
1466 /*
1467  - doemit - emit a strip operator
1468  *
1469  * It might seem better to implement this as a macro with a function as
1470  * hard-case backup, but it's just too big and messy unless there are
1471  * some changes to the data structures. Maybe later.
1472  */
1473 static void
1474 doemit(struct parse *p, sop op, size_t opnd)
1475 {
1476  /* avoid making error situations worse */
1477  if (p->error != 0)
1478  return;
1479 
1480  /* deal with oversize operands ("can't happen", more or less) */
1481  assert(opnd < 1<<OPSHIFT);
1482 
1483  /* deal with undersized strip */
1484  if (p->slen >= p->ssize)
1485  enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */
1486  assert(p->slen < p->ssize);
1487 
1488  /* finally, it's all reduced to the easy case */
1489  p->strip[p->slen++] = SOP(op, opnd);
1490 }
1491 
1492 /*
1493  - doinsert - insert a sop into the strip
1494  */
1495 static void
1496 doinsert(struct parse *p, sop op, size_t opnd, sopno pos)
1497 {
1498  sopno sn;
1499  sop s;
1500  int i;
1501 
1502  /* avoid making error situations worse */
1503  if (p->error != 0)
1504  return;
1505 
1506  sn = HERE();
1507  EMIT(op, opnd); /* do checks, ensure space */
1508  assert(HERE() == sn+1);
1509  s = p->strip[sn];
1510 
1511  /* adjust paren pointers */
1512  assert(pos > 0);
1513  for (i = 1; i < NPAREN; i++) {
1514  if (p->pbegin[i] >= pos) {
1515  p->pbegin[i]++;
1516  }
1517  if (p->pend[i] >= pos) {
1518  p->pend[i]++;
1519  }
1520  }
1521 
1522  memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1523  (HERE()-pos-1)*sizeof(sop));
1524  p->strip[pos] = s;
1525 }
1526 
1527 /*
1528  - dofwd - complete a forward reference
1529  */
1530 static void
1531 dofwd(struct parse *p, sopno pos, sop value)
1532 {
1533  /* avoid making error situations worse */
1534  if (p->error != 0)
1535  return;
1536 
1537  assert(value < 1<<OPSHIFT);
1538  p->strip[pos] = OP(p->strip[pos]) | value;
1539 }
1540 
1541 /*
1542  - enlarge - enlarge the strip
1543  */
1544 static void
1546 {
1547  sop *sp;
1548 
1549  if (p->ssize >= size)
1550  return;
1551 
1552  if ((uintptr_t)size > SIZE_MAX / sizeof(sop)) {
1554  return;
1555  }
1556 
1557  sp = (sop *)realloc(p->strip, size*sizeof(sop));
1558  if (sp == NULL) {
1560  return;
1561  }
1562  p->strip = sp;
1563  p->ssize = size;
1564 }
1565 
1566 /*
1567  - stripsnug - compact the strip
1568  */
1569 static void
1570 stripsnug(struct parse *p, struct re_guts *g)
1571 {
1572  g->nstates = p->slen;
1573  if ((uintptr_t)p->slen > SIZE_MAX / sizeof(sop)) {
1574  g->strip = p->strip;
1576  return;
1577  }
1578 
1579  g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
1580  if (g->strip == NULL) {
1582  g->strip = p->strip;
1583  }
1584 }
1585 
1586 /*
1587  - findmust - fill in must and mlen with longest mandatory literal string
1588  *
1589  * This algorithm could do fancy things like analyzing the operands of |
1590  * for common subsequences. Someday. This code is simple and finds most
1591  * of the interesting cases.
1592  *
1593  * Note that must and mlen got initialized during setup.
1594  */
1595 static void
1596 findmust(struct parse *p, struct re_guts *g)
1597 {
1598  sop *scan;
1599  sop *start = 0; /* start initialized in the default case, after that */
1600  sop *newstart = 0; /* newstart was initialized in the OCHAR case */
1601  sopno newlen;
1602  sop s;
1603  char *cp;
1604  sopno i;
1605 
1606  /* avoid making error situations worse */
1607  if (p->error != 0)
1608  return;
1609 
1610  /* find the longest OCHAR sequence in strip */
1611  newlen = 0;
1612  scan = g->strip + 1;
1613  do {
1614  s = *scan++;
1615  switch (OP(s)) {
1616  case OCHAR: /* sequence member */
1617  if (newlen == 0) /* new sequence */
1618  newstart = scan - 1;
1619  newlen++;
1620  break;
1621  case OPLUS_: /* things that don't break one */
1622  case OLPAREN:
1623  case ORPAREN:
1624  break;
1625  case OQUEST_: /* things that must be skipped */
1626  case OCH_:
1627  scan--;
1628  do {
1629  scan += OPND(s);
1630  s = *scan;
1631  /* assert() interferes w debug printouts */
1632  if (OP(s) != O_QUEST && OP(s) != O_CH &&
1633  OP(s) != OOR2) {
1634  g->iflags |= REGEX_BAD;
1635  return;
1636  }
1637  } while (OP(s) != O_QUEST && OP(s) != O_CH);
1638  /* fallthrough */
1639  default: /* things that break a sequence */
1640  if (newlen > g->mlen) { /* ends one */
1641  start = newstart;
1642  g->mlen = newlen;
1643  }
1644  newlen = 0;
1645  break;
1646  }
1647  } while (OP(s) != OEND);
1648 
1649  if (g->mlen == 0) /* there isn't one */
1650  return;
1651 
1652  /* turn it into a character string */
1653  g->must = malloc((size_t)g->mlen + 1);
1654  if (g->must == NULL) { /* argh; just forget it */
1655  g->mlen = 0;
1656  return;
1657  }
1658  cp = g->must;
1659  scan = start;
1660  for (i = g->mlen; i > 0; i--) {
1661  while (OP(s = *scan++) != OCHAR)
1662  continue;
1663  assert(cp < g->must + g->mlen);
1664  *cp++ = (char)OPND(s);
1665  }
1666  assert(cp == g->must + g->mlen);
1667  *cp++ = '\0'; /* just on general principles */
1668 }
1669 
1670 /*
1671  - pluscount - count + nesting
1672  */
1673 static sopno /* nesting depth */
1674 pluscount(struct parse *p, struct re_guts *g)
1675 {
1676  sop *scan;
1677  sop s;
1678  sopno plusnest = 0;
1679  sopno maxnest = 0;
1680 
1681  if (p->error != 0)
1682  return(0); /* there may not be an OEND */
1683 
1684  scan = g->strip + 1;
1685  do {
1686  s = *scan++;
1687  switch (OP(s)) {
1688  case OPLUS_:
1689  plusnest++;
1690  break;
1691  case O_PLUS:
1692  if (plusnest > maxnest)
1693  maxnest = plusnest;
1694  plusnest--;
1695  break;
1696  }
1697  } while (OP(s) != OEND);
1698  if (plusnest != 0)
1699  g->iflags |= REGEX_BAD;
1700  return(maxnest);
1701 }
static void nonnewline(struct parse *)
Definition: regcomp.c:1088
static void p_ere_exp(struct parse *)
Definition: regcomp.c:435
size_t re_nsub
Definition: regex_impl.h:50
#define OUT
Definition: regex2.h:162
#define REG_NOSPEC
Definition: regex_impl.h:61
#define REG_INVARG
Definition: regex_impl.h:81
#define OBOL
Definition: regex2.h:80
sopno nplus
Definition: regex2.h:156
static int p_simp_re(struct parse *, int)
Definition: regcomp.c:659
#define EAT(c)
Definition: regcomp.c:255
sopno slen
Definition: regcomp.c:197
static int firstch(struct parse *, cset *)
Definition: regcomp.c:1307
const char * name
Definition: regcomp.c:54
#define BACKSL
#define OEOL
Definition: regex2.h:81
static int samesets(struct re_guts *, int, int)
Definition: regcomp.c:1405
static int freezeset(struct parse *, cset *)
Definition: regcomp.c:1276
long sopno
Definition: regex2.h:69
char * multis
Definition: regex2.h:116
#define ASTERN(sop, pos)
Definition: regcomp.c:269
#define REP(f, t)
int ncategories
Definition: regex2.h:150
static struct cname cnames[]
int backrefs
Definition: regex2.h:155
#define THERE()
Definition: regcomp.c:271
#define REG_NEWLINE
Definition: regex_impl.h:60
static void mccase(struct parse *, cset *)
Definition: regcomp.c:1379
#define REG_BADRPT
Definition: regex_impl.h:78
#define MAGIC2
Definition: regex2.h:134
#define OOR2
Definition: regex2.h:94
#define OPLUS_
Definition: regex2.h:86
int mlen
Definition: regex2.h:153
static void p_b_term(struct parse *, cset *)
Definition: regcomp.c:875
#define REG_EESCAPE
Definition: regex_impl.h:70
static void categorize(struct parse *, struct re_guts *)
Definition: regcomp.c:1423
#define EMIT(op, sopnd)
Definition: regcomp.c:266
sopno ssize
Definition: regcomp.c:196
#define GETNEXT()
Definition: regcomp.c:260
static void findmust(struct parse *, struct re_guts *)
Definition: regcomp.c:1596
int llvm_regcomp(llvm_regex_t *preg, const char *pattern, int cflags)
Definition: regcomp.c:292
int csetsize
Definition: regex2.h:136
#define DUPMAX
Definition: regcomp.c:278
static int seterr(struct parse *, int)
Definition: regcomp.c:1180
#define REG_EPAREN
Definition: regex_impl.h:73
#define NEXT()
Definition: regcomp.c:257
#define OPSHIFT
Definition: regex2.h:72
void llvm_regfree(llvm_regex_t *)
Definition: regfree.c:50
#define op(i)
sop * strip
Definition: regex2.h:135
static cset * allocset(struct parse *)
Definition: regcomp.c:1193
#define O_CH
Definition: regex2.h:95
#define REG_EMPTY
Definition: regex_impl.h:79
int re_magic
Definition: regex_impl.h:49
const char * name
Definition: regcomp.c:86
int cflags
Definition: regex2.h:140
static void stripsnug(struct parse *, struct re_guts *)
Definition: regcomp.c:1570
static void dofwd(struct parse *, sopno, sop)
Definition: regcomp.c:1531
Definition: regcomp.c:85
#define REG_EXTENDED
Definition: regex_impl.h:57
sopno pend[NPAREN]
Definition: regcomp.c:202
static void doemit(struct parse *, sop, size_t)
Definition: regcomp.c:1474
#define CHIN(cs, c)
Definition: regex2.h:121
static void bothcases(struct parse *, int)
Definition: regcomp.c:1046
#define REG_EBRACE
Definition: regex_impl.h:74
int ncsets
Definition: regex2.h:137
#define MCadd(p, cs, cp)
Definition: regex2.h:122
char * must
Definition: regex2.h:152
#define CHadd(cs, c)
Definition: regex2.h:119
#define NEXTn(n)
Definition: regcomp.c:259
static int nch(struct parse *, cset *)
Definition: regcomp.c:1323
Definition: regcomp.c:191
sopno firststate
Definition: regex2.h:142
char * next
Definition: regcomp.c:192
#define OEND
Definition: regex2.h:78
sopno pbegin[NPAREN]
Definition: regcomp.c:201
const char * re_endp
Definition: regex_impl.h:51
#define OQUEST_
Definition: regex2.h:88
#define SOP(op, opnd)
Definition: regex2.h:75
int error
Definition: regcomp.c:194
struct re_guts * g
Definition: regcomp.c:199
size_t llvm_strlcpy(char *dst, const char *src, size_t siz)
Definition: regstrlcpy.c:29
#define NPAREN
Definition: regcomp.c:200
#define O_BACK
Definition: regex2.h:85
#define SETERROR(e)
Definition: regcomp.c:261
static void enlarge(struct parse *, sopno)
Definition: regcomp.c:1545
#define AHEAD(pos)
Definition: regcomp.c:268
uch hash
Definition: regex2.h:114
static void p_ere(struct parse *, int)
Definition: regcomp.c:392
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:974
sopno laststate
Definition: regex2.h:143
sopno nstates
Definition: regex2.h:141
#define CHsub(cs, c)
Definition: regex2.h:120
#define REG_ICASE
Definition: regex_impl.h:58
uch * ptr
Definition: regex2.h:112
Definition: regex2.h:111
size_t smultis
Definition: regex2.h:115
#define REG_ECOLLATE
Definition: regex_impl.h:68
#define HERE()
Definition: regcomp.c:270
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
#define ORPAREN
Definition: regex2.h:91
#define REG_BADBR
Definition: regex_impl.h:75
char code
Definition: regcomp.c:87
static void mcadd(struct parse *, cset *, const char *)
Definition: regcomp.c:1339
#define MAGIC1
Definition: regex2.h:47
uch * setbits
Definition: regex2.h:139
static void doinsert(struct parse *, sop, size_t, sopno)
Definition: regcomp.c:1496
#define OBOW
Definition: regex2.h:96
int neol
Definition: regex2.h:149
int iflags
Definition: regex2.h:144
char * end
Definition: regcomp.c:193
#define GOODFLAGS(f)
#define INFINITY
Definition: regcomp.c:280
#define DROP(n)
Definition: regcomp.c:273
#define OANY
Definition: regex2.h:82
sop * strip
Definition: regcomp.c:195
#define REG_EBRACK
Definition: regex_impl.h:72
struct re_guts * re_g
Definition: regex_impl.h:52
uch mask
Definition: regex2.h:113
static char nuls[10]
Definition: regcomp.c:243
unsigned char uch
Definition: regutils.h:43
#define REGEX_BAD
Definition: regex2.h:147
#define OLPAREN
Definition: regex2.h:90
int ncsalloc
Definition: regcomp.c:198
unsigned first
static void p_b_cclass(struct parse *, cset *)
Definition: regcomp.c:938
unsigned char cat_t
Definition: regex2.h:127
#define SEETWO(a, b)
Definition: regcomp.c:254
const char * multis
Definition: regcomp.c:56
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1032
#define EATTWO(a, b)
Definition: regcomp.c:256
static void p_bracket(struct parse *)
Definition: regcomp.c:796
static void freeset(struct parse *, cset *)
Definition: regcomp.c:1254
cset * sets
Definition: regex2.h:138
#define MORE()
Definition: regcomp.c:251
static char p_b_symbol(struct parse *)
Definition: regcomp.c:983
static void ordinary(struct parse *, int)
Definition: regcomp.c:1069
#define NC
Definition: regutils.h:42
#define MAP(n)
#define OANYOF
Definition: regex2.h:83
static void p_bre(struct parse *, int, int)
Definition: regcomp.c:628
#define MORE2()
Definition: regcomp.c:252
#define REG_ERANGE
Definition: regex_impl.h:76
#define SEE(c)
Definition: regcomp.c:253
static int p_count(struct parse *)
Definition: regcomp.c:775
#define OEOW
Definition: regex2.h:97
#define USEEOL
Definition: regex2.h:146
#define REG_PEND
Definition: regex_impl.h:62
#define OBACK_
Definition: regex2.h:84
#define USEBOL
Definition: regex2.h:145
#define THERETHERE()
Definition: regcomp.c:272
static char p_b_coll_elem(struct parse *, int)
Definition: regcomp.c:1001
static void p_b_eclass(struct parse *, cset *)
Definition: regcomp.c:971
static char othercase(int)
Definition: regcomp.c:1028
#define PEEK2()
Definition: regcomp.c:250
#define REG_ECTYPE
Definition: regex_impl.h:69
#define O_QUEST
Definition: regex2.h:89
#define N
static sopno dupl(struct parse *, sopno, sopno)
Definition: regcomp.c:1448
cat_t * categories
Definition: regex2.h:151
static struct cclass cclasses[]
static void repeat(struct parse *, sopno, int, int)
Definition: regcomp.c:1110
static sopno pluscount(struct parse *, struct re_guts *)
Definition: regcomp.c:1674
size_t nsub
Definition: regex2.h:154
#define OCH_
Definition: regex2.h:92
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int magic
Definition: regex2.h:133
static void p_str(struct parse *)
Definition: regcomp.c:610
#define MUSTEAT(c, e)
Definition: regcomp.c:264
static int isinsets(struct re_guts *, int)
Definition: regcomp.c:1388
#define never
Definition: regcomp.c:285
#define OPND(n)
Definition: regex2.h:74
#define INF
const char * chars
Definition: regcomp.c:55
#define REG_ASSERT
Definition: regex_impl.h:80
#define OCHAR
Definition: regex2.h:79
#define PEEK()
Definition: regcomp.c:249
#define O_PLUS
Definition: regex2.h:87
#define REQUIRE(co, e)
Definition: regcomp.c:262
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:960
#define NEXT2()
Definition: regcomp.c:258
Definition: regcomp.c:53
unsigned long sop
Definition: regex2.h:68
#define INSERT(op, pos)
Definition: regcomp.c:267
#define REG_ESPACE
Definition: regex_impl.h:77
#define OP(n)
Definition: regex2.h:73
static Expected< BitVector > scan(StringRef &S, StringRef Original)
Definition: GlobPattern.cpp:67
#define OOR1
Definition: regex2.h:93
cat_t catspace[1]
Definition: regex2.h:158
static void mcinvert(struct parse *, cset *)
Definition: regcomp.c:1366
int nbol
Definition: regex2.h:148
#define REG_ESUBREG
Definition: regex_impl.h:71