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