46#define matcher smatcher
49#define dissect sdissect
50#define backref sbackref
56#define step_back sstep_back
59#define matcher lmatcher
62#define dissect ldissect
63#define backref lbackref
69#define step_back lstep_back
89static int matcher(
struct re_guts *,
const char *,
size_t,
91static const char *dissect(
struct match *,
const char *,
const char *,
sopno,
93static const char *backref(
struct match *,
const char *,
const char *,
sopno,
95static const char *fast(
struct match *,
const char *,
const char *,
sopno,
sopno);
96static const char *slow(
struct match *,
const char *,
const char *,
sopno,
sopno);
98#define MAX_RECURSION 100
101#define BOLEOL (BOL+2)
102#define NOTHING (BOL+3)
105#define CODEMAX (BOL+5)
106#define NONCHAR(c) ((c) > CHAR_MAX)
107#define NNONCHAR (CODEMAX-CHAR_MAX)
109static void print(
struct match *,
const char *,
states,
int, FILE *);
113 struct match *,
const char *,
const char *,
const char *,
sopno,
sopno);
116static char *pchar(
int);
120#define SP(t, s, c) print(m, t, s, c, stdout)
121#define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
122#define NOTE(str) { if (m->eflags®_TRACE) (void)printf("=%s\n", (str)); }
126#define AT(t, p1, p2, s1, s2)
134matcher(
struct re_guts *
g,
const char *
string,
size_t nmatch,
141 struct match *m = &mv;
143 const sopno gf =
g->firststate+1;
144 const sopno gl =
g->laststate;
152 start =
string + pmatch[0].
rm_so;
153 stop =
string + pmatch[0].
rm_eo;
156 stop = start + strlen(start);
162 if (
g->must != NULL) {
163 for (dp = start; dp < stop; dp++)
164 if (*dp ==
g->must[0] && stop - dp >=
g->mlen &&
165 memcmp(dp,
g->must, (
size_t)
g->mlen) == 0)
188 endp = fast(m, start, stop, gf, gl);
191 free((
void*)m->lastpos);
195 if (nmatch == 0 && !
g->backrefs)
201 NOTE(
"finding start");
202 endp = slow(m, m->coldp, stop, gf, gl);
205 assert(m->coldp < m->endp);
208 if (nmatch == 1 && !
g->backrefs)
212 if (m->pmatch == NULL)
215 if (m->pmatch == NULL) {
219 for (i = 1; i <= m->g->nsub; i++)
220 m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1;
223 dp = dissect(m, m->coldp, endp, gf, gl);
225 if (
g->nplus > 0 && m->lastpos == NULL)
226 m->lastpos = (
const char **)malloc((
g->nplus+1) *
228 if (
g->nplus > 0 && m->lastpos == NULL) {
233 NOTE(
"backref dissect");
234 dp = backref(m, m->coldp, endp, gf, gl, (
sopno)0, 0);
241 assert(
g->nplus == 0 || m->lastpos != NULL);
243 if (dp != NULL || endp <= m->coldp)
246 endp = slow(m, m->coldp, endp-1, gf, gl);
251 for (i = 1; i <= m->g->nsub; i++) {
252 assert(m->pmatch[i].rm_so == -1);
253 assert(m->pmatch[i].rm_eo == -1);
256 NOTE(
"backoff dissect");
257 dp = backref(m, m->coldp, endp, gf, gl, (
sopno)0, 0);
259 assert(dp == NULL || dp == endp);
265 if (m->coldp == stop)
267 start = m->coldp + 1;
272 pmatch[0].
rm_so = m->coldp - m->offp;
273 pmatch[0].
rm_eo = endp - m->offp;
276 assert(m->pmatch != NULL);
277 for (i = 1; i < nmatch; i++)
279 pmatch[i] = m->pmatch[i];
281 pmatch[i].
rm_so = -1;
282 pmatch[i].
rm_eo = -1;
286 if (m->pmatch != NULL)
287 free((
char *)m->pmatch);
288 if (m->lastpos != NULL)
289 free((
char *)m->lastpos);
298step_back(
struct re_guts *
g,
const char *start,
const char *stop,
sopno startst,
303 const char *res = stop - 1;
308 if (startst >= stopst)
318 char ch =
OPND(
g->strip[startst]);
319 for (; res != start; --res) {
322 sopno nextst = startst + 1;
323 const char *next = res + 1;
324 if (nextst >= stopst ||
OP(
g->strip[nextst]) !=
OCHAR || next >= stop ||
325 *next == (
char)
OPND(
g->strip[nextst]))
336dissect(
struct match *m,
const char *start,
const char *stop,
sopno startst,
352 AT(
"diss", start, stop, startst, stopst);
354 for (ss = startst; ss < stopst; ss = es) {
357 switch (
OP(m->g->strip[es])) {
360 es +=
OPND(m->g->strip[es]);
363 while (
OP(m->g->strip[es]) !=
O_CH)
364 es +=
OPND(m->g->strip[es]);
370 switch (
OP(m->g->strip[ss])) {
395 rest = slow(m, sp, stp, ss, es);
398 tail = slow(m, rest, stop, es, stopst);
402 stp = step_back(m->g, sp, rest, es, stopst);
408 if (slow(m, sp, rest, ssub, esub) != NULL) {
409 const char *dp = dissect(m, sp, rest, ssub, esub);
420 rest = slow(m, sp, stp, ss, es);
423 tail = slow(m, rest, stop, es, stopst);
427 stp = step_back(m->g, sp, rest, es, stopst);
435 sep = slow(m, ssp, rest, ssub, esub);
436 if (sep == NULL || sep == ssp)
447 assert(slow(m, ssp, sep, ssub, esub) == rest);
449 const char *dp = dissect(m, ssp, sep, ssub, esub);
459 rest = slow(m, sp, stp, ss, es);
462 tail = slow(m, rest, stop, es, stopst);
470 esub = ss +
OPND(m->g->strip[ss]) - 1;
473 if (slow(m, sp, rest, ssub, esub) == rest)
480 esub +=
OPND(m->g->strip[esub]);
481 if (
OP(m->g->strip[esub]) ==
OOR2)
487 const char *dp = dissect(m, sp, rest, ssub, esub);
501 i =
OPND(m->g->strip[ss]);
502 assert(0 < i && i <= m->
g->nsub);
503 m->pmatch[i].rm_so = sp - m->offp;
506 i =
OPND(m->g->strip[ss]);
507 assert(0 < i && i <= m->
g->nsub);
508 m->pmatch[i].rm_eo = sp - m->offp;
524backref(
struct match *m,
const char *start,
const char *stop,
sopno startst,
540 AT(
"back", start, stop, startst, stopst);
545 for (ss = startst; !hard && ss < stopst; ss++)
546 switch (
OP(s = m->g->strip[ss])) {
548 if (sp == stop || *sp++ != (
char)
OPND(s))
557 cs = &m->g->sets[
OPND(s)];
558 if (sp == stop || !
CHIN(cs, *sp++))
562 if ( (sp == m->beginp && !(m->eflags&
REG_NOTBOL)) ||
563 (sp < m->endp && *(sp-1) ==
'\n' &&
570 if ( (sp == m->endp && !(m->eflags&
REG_NOTEOL)) ||
571 (sp < m->endp && *sp ==
'\n' &&
578 if (( (sp == m->beginp && !(m->eflags&
REG_NOTBOL)) ||
579 (sp < m->endp && *(sp-1) ==
'\n' &&
583 (sp < m->endp &&
ISWORD(*sp)) )
589 if (( (sp == m->endp && !(m->eflags&
REG_NOTEOL)) ||
590 (sp < m->endp && *sp ==
'\n' &&
592 (sp < m->endp && !
ISWORD(*sp)) ) &&
593 (sp > m->beginp &&
ISWORD(*(sp-1))) )
607 }
while (
OP(s = m->g->strip[ss]) !=
O_CH);
622 AT(
"hard", sp, stop, ss, stopst);
627 assert(0 < i && i <= m->
g->nsub);
628 if (m->pmatch[i].rm_eo == -1)
630 assert(m->pmatch[i].rm_so != -1);
631 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so;
632 if (len == 0 && rec++ > MAX_RECURSION)
634 assert(stop - m->beginp >= len);
637 ssp = m->offp + m->pmatch[i].rm_so;
638 if (
memcmp(sp, ssp, len) != 0)
640 while (m->g->strip[ss] !=
SOP(
O_BACK, i))
642 return(backref(m, sp+len, stop, ss+1, stopst, lev, rec));
645 dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
648 return(backref(m, sp, stop, ss+
OPND(s)+1, stopst, lev, rec));
651 assert(m->lastpos != NULL);
652 assert(lev+1 <= m->g->nplus);
653 m->lastpos[lev+1] = sp;
654 return(backref(m, sp, stop, ss+1, stopst, lev+1, rec));
657 if (sp == m->lastpos[lev])
658 return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
660 m->lastpos[lev] = sp;
661 dp = backref(m, sp, stop, ss-
OPND(s)+1, stopst, lev, rec);
663 return(backref(m, sp, stop, ss+1, stopst, lev-1, rec));
669 esub = ss +
OPND(s) - 1;
672 dp = backref(m, sp, stop, ssub, stopst, lev, rec);
676 if (
OP(m->g->strip[esub]) ==
O_CH)
681 esub +=
OPND(m->g->strip[esub]);
682 if (
OP(m->g->strip[esub]) ==
OOR2)
690 assert(0 < i && i <= m->
g->nsub);
691 offsave = m->pmatch[i].rm_so;
692 m->pmatch[i].rm_so = sp - m->offp;
693 dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
696 m->pmatch[i].rm_so = offsave;
701 assert(0 < i && i <= m->
g->nsub);
702 offsave = m->pmatch[i].rm_eo;
703 m->pmatch[i].rm_eo = sp - m->offp;
704 dp = backref(m, sp, stop, ss+1, stopst, lev, rec);
707 m->pmatch[i].rm_eo = offsave;
725fast(
struct match *m,
const char *start,
const char *stop,
sopno startst,
731 const char *
p = start;
732 int c = (start == m->beginp) ?
OUT : *(start-1);
740 st = step(m->g, startst, stopst, st, NOTHING, st);
747 c = (
p == m->endp) ?
OUT : *p;
754 if ( (lastc ==
'\n' && m->g->cflags&
REG_NEWLINE) ||
761 flagch = (flagch == BOL) ? BOLEOL : EOL;
766 st = step(m->g, startst, stopst, st, flagch, st);
771 if ( (flagch == BOL || (lastc !=
OUT && !
ISWORD(lastc))) &&
776 (flagch == EOL || (c !=
OUT && !
ISWORD(c))) ) {
779 if (flagch == BOW || flagch == EOW) {
780 st = step(m->g, startst, stopst, st, flagch, st);
785 if (
ISSET(st, stopst) || p == stop)
792 st = step(m->g, startst, stopst, tmp, c, st);
794 assert(
EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
800 if (
ISSET(st, stopst))
810slow(
struct match *m,
const char *start,
const char *stop,
sopno startst,
814 const char *
p = start;
815 for (; startst < stopst; ++startst) {
817 sop s = m->g->strip[startst];
824 if (p == stop || *p != (
char)
OPND(s))
839 int c = (
p == m->beginp) ?
OUT : *(p-1);
845 AT(
"slow", start, stop, startst, stopst);
848 SP(
"sstart", st, *p);
849 st = step(m->g, startst, stopst, st, NOTHING, st);
854 c = (
p == m->endp) ?
OUT : *p;
859 if ( (lastc ==
'\n' && m->g->cflags&
REG_NEWLINE) ||
866 flagch = (flagch == BOL) ? BOLEOL : EOL;
871 st = step(m->g, startst, stopst, st, flagch, st);
872 SP(
"sboleol", st, c);
876 if ( (flagch == BOL || (lastc !=
OUT && !
ISWORD(lastc))) &&
881 (flagch == EOL || (c !=
OUT && !
ISWORD(c))) ) {
884 if (flagch == BOW || flagch == EOW) {
885 st = step(m->g, startst, stopst, st, flagch, st);
886 SP(
"sboweow", st, c);
890 if (
ISSET(st, stopst))
892 if (
EQ(st, empty) || p == stop)
899 st = step(m->g, startst, stopst, tmp, c, st);
901 assert(
EQ(step(m->g, startst, stopst, st, NOTHING, st), st));
927 for (pc = start,
INIT(here, pc); pc != stop; pc++,
INC(here)) {
936 if (ch == (
char)
OPND(s))
940 if (ch == BOL || ch == BOLEOL)
944 if (ch == EOL || ch == BOLEOL)
960 cs = &
g->sets[
OPND(s)];
961 if (!NONCHAR(ch) &&
CHIN(cs, ch))
1000 OP(s =
g->strip[pc+look]) !=
O_CH;
1003 FWD(aft, aft, look);
1030print(
struct match *m,
const char *caption,
states st,
int ch, FILE *d)
1039 (void)fprintf(d,
"%s", caption);
1041 (void)fprintf(d,
" %s", pchar(ch));
1042 for (i = 0; i <
g->nstates; i++)
1044 (void)fprintf(d,
"%s%d", (first) ?
"\t" :
", ", i);
1047 (void)fprintf(d,
"\n");
1054at(
struct match *m,
const char *title,
const char *start,
const char *stop,
1060 (void)printf(
"%s %s-", title, pchar(*start));
1061 (void)printf(
"%s ", pchar(*stop));
1062 (void)printf(
"%ld-%ld\n", (
long)startst, (long)stopst);
1078 static char pbuf[10];
1080 if (isprint(ch) || ch ==
' ')
1081 (void)snprintf(pbuf,
sizeof pbuf,
"%c", ch);
1083 (
void)snprintf(pbuf,
sizeof pbuf,
"\\%o", ch);
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Merge contiguous icmps into a memcmp
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d, uint32_t x, uint32_t y)
bool match(const SCEV *S, const Pattern &P)
#define BACK(dst, src, n)