Lines Matching +full:- +full:m
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
85 const char *beginp; /* start of string -- virtual NUL precedes */
86 const char *endp; /* end of string -- virtual NUL here */
104 static const char *dissect(struct match *m, const char *start, const char *stop, sopno startst, sop…
105 static const char *backref(struct match *m, const char *start, const char *stop, sopno startst, sop…
106 static const char *walk(struct match *m, const char *start, const char *stop, sopno startst, sopno …
109 #define BOL (OUT-1)
110 #define EOL (BOL-1)
111 #define BOLEOL (BOL-2)
112 #define NOTHING (BOL-3)
113 #define BOW (BOL-4)
114 #define EOW (BOL-5)
115 #define BADCHAR (BOL-6)
116 #define NWBND (BOL-7)
123 static void print(struct match *m, const char *caption, states st, int ch, FILE *d);
126 static void at(struct match *m, const char *title, const char *start, const char *stop, sopno start…
138 #define SP(t, s, c) print(m, t, s, c, stdout)
139 #define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
140 #define NOTE(str) { if (m->eflags®_TRACE) printf("=%s\n", (str)); }
160 return ((cur - nchar) > start ? cur - nchar : NULL); in stepback()
163 for (wc = nchar; wc > 0; wc--) { in stepback()
165 if ((ret - mbc) < start) in stepback()
168 clen = mbrtowc(NULL, ret - mbc, mbc, &mbs); in stepback()
169 if (clen != (size_t)-1 && clen != (size_t)-2) in stepback()
174 ret -= mbc; in stepback()
181 - matcher - the actual matching engine
195 struct match *m = &mv; in matcher() local
197 const sopno gf = g->firststate+1; /* +1 for OEND */ in matcher()
198 const sopno gl = g->laststate; in matcher()
201 /* Boyer-Moore algorithms variables */ in matcher()
210 if (g->cflags®_NOSUB) in matcher()
223 if (g->must != NULL) { in matcher()
224 if (g->charjump != NULL && g->matchjump != NULL) { in matcher()
225 mustfirst = g->must; in matcher()
226 mustlast = g->must + g->mlen - 1; in matcher()
227 charjump = g->charjump; in matcher()
228 matchjump = g->matchjump; in matcher()
230 for (dp = start+g->mlen-1; dp < stop;) { in matcher()
231 /* Fast skip non-matches */ in matcher()
242 while (*--dp == *--pp && pp != mustfirst); in matcher()
248 mj = matchjump[pp - mustfirst]; in matcher()
257 if (*dp == g->must[0] && in matcher()
258 stop - dp >= g->mlen && in matcher()
259 memcmp(dp, g->must, (size_t)g->mlen) == 0) in matcher()
261 if (dp == stop) /* we didn't find g->must */ in matcher()
267 m->g = g; in matcher()
268 m->eflags = eflags; in matcher()
269 m->pmatch = NULL; in matcher()
270 m->lastpos = NULL; in matcher()
271 m->offp = string; in matcher()
272 m->beginp = start; in matcher()
273 m->endp = stop; in matcher()
274 STATESETUP(m, 4); in matcher()
275 SETUP(m->st); in matcher()
276 SETUP(m->fresh); in matcher()
277 SETUP(m->tmp); in matcher()
278 SETUP(m->empty); in matcher()
279 CLEAR(m->empty); in matcher()
280 ZAPSTATE(&m->mbs); in matcher()
283 if (dp != NULL && g->moffset > -1) { in matcher()
286 nstart = stepback(start, dp, g->moffset); in matcher()
291 SP("mloop", m->st, *start); in matcher()
295 endp = walk(m, start, stop, gf, gl, true); in matcher()
297 if (m->pmatch != NULL) in matcher()
298 free((char *)m->pmatch); in matcher()
299 if (m->lastpos != NULL) in matcher()
300 free((char *)m->lastpos); in matcher()
301 STATETEARDOWN(m); in matcher()
304 if (nmatch == 0 && !g->backrefs) in matcher()
308 assert(m->coldp != NULL); in matcher()
311 endp = walk(m, m->coldp, stop, gf, gl, false); in matcher()
314 assert(m->coldp < m->endp); in matcher()
315 m->coldp += XMBRTOWC(NULL, m->coldp, in matcher()
316 m->endp - m->coldp, &m->mbs, 0); in matcher()
318 if (nmatch == 1 && !g->backrefs) in matcher()
322 if (m->pmatch == NULL) in matcher()
323 m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) * in matcher()
325 if (m->pmatch == NULL) { in matcher()
326 STATETEARDOWN(m); in matcher()
329 for (i = 1; i <= m->g->nsub; i++) in matcher()
330 m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1; in matcher()
331 if (!g->backrefs && !(m->eflags®_BACKR)) { in matcher()
333 dp = dissect(m, m->coldp, endp, gf, gl); in matcher()
335 if (g->nplus > 0 && m->lastpos == NULL) in matcher()
336 m->lastpos = malloc((g->nplus+1) * in matcher()
338 if (g->nplus > 0 && m->lastpos == NULL) { in matcher()
339 free(m->pmatch); in matcher()
340 STATETEARDOWN(m); in matcher()
344 dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0); in matcher()
349 /* uh-oh... we couldn't find a subexpression-level match */ in matcher()
350 assert(g->backrefs); /* must be back references doing it */ in matcher()
351 assert(g->nplus == 0 || m->lastpos != NULL); in matcher()
353 if (dp != NULL || endp <= m->coldp) in matcher()
356 endp = walk(m, m->coldp, endp-1, gf, gl, false); in matcher()
361 for (i = 1; i <= m->g->nsub; i++) { in matcher()
362 assert(m->pmatch[i].rm_so == -1); in matcher()
363 assert(m->pmatch[i].rm_eo == -1); in matcher()
367 dp = backref(m, m->coldp, endp, gf, gl, (sopno)0, 0); in matcher()
376 start = m->coldp + XMBRTOWC(NULL, m->coldp, in matcher()
377 stop - m->coldp, &m->mbs, 0); in matcher()
383 pmatch[0].rm_so = m->coldp - m->offp; in matcher()
384 pmatch[0].rm_eo = endp - m->offp; in matcher()
387 assert(m->pmatch != NULL); in matcher()
389 if (i <= m->g->nsub) in matcher()
390 pmatch[i] = m->pmatch[i]; in matcher()
392 pmatch[i].rm_so = -1; in matcher()
393 pmatch[i].rm_eo = -1; in matcher()
397 if (m->pmatch != NULL) in matcher()
398 free((char *)m->pmatch); in matcher()
399 if (m->lastpos != NULL) in matcher()
400 free((char *)m->lastpos); in matcher()
401 STATETEARDOWN(m); in matcher()
406 - dissect - figure out what matched what, no back references
407 == static const char *dissect(struct match *m, const char *start, \
411 dissect(struct match *m, in dissect() argument
436 switch (OP(m->g->strip[es])) { in dissect()
439 es += OPND(m->g->strip[es]); in dissect()
442 while (OP(m->g->strip[es]) != (sop)O_CH) in dissect()
443 es += OPND(m->g->strip[es]); in dissect()
449 switch (OP(m->g->strip[ss])) { in dissect()
454 sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0); in dissect()
467 sp += XMBRTOWC(NULL, sp, stop - start, &m->mbs, 0); in dissect()
478 rest = walk(m, sp, stp, ss, es, false); in dissect()
481 tail = walk(m, rest, stop, es, stopst, false); in dissect()
484 /* no -- try a shorter match for this one */ in dissect()
485 stp = rest - 1; in dissect()
489 esub = es - 1; in dissect()
491 if (walk(m, sp, rest, ssub, esub, false) != NULL) { in dissect()
492 dp = dissect(m, sp, rest, ssub, esub); in dissect()
502 rest = walk(m, sp, stp, ss, es, false); in dissect()
505 tail = walk(m, rest, stop, es, stopst, false); in dissect()
508 /* no -- try a shorter match for this one */ in dissect()
509 stp = rest - 1; in dissect()
513 esub = es - 1; in dissect()
517 sep = walk(m, ssp, rest, ssub, esub, false); in dissect()
529 assert(walk(m, ssp, sep, ssub, esub, false) == rest); in dissect()
530 dp = dissect(m, ssp, sep, ssub, esub); in dissect()
538 rest = walk(m, sp, stp, ss, es, false); in dissect()
541 tail = walk(m, rest, stop, es, stopst, false); in dissect()
544 /* no -- try a shorter match for this one */ in dissect()
545 stp = rest - 1; in dissect()
549 esub = ss + OPND(m->g->strip[ss]) - 1; in dissect()
550 assert(OP(m->g->strip[esub]) == OOR1); in dissect()
552 if (walk(m, sp, rest, ssub, esub, false) == rest) in dissect()
555 assert(OP(m->g->strip[esub]) == OOR1); in dissect()
557 assert(OP(m->g->strip[esub]) == OOR2); in dissect()
559 esub += OPND(m->g->strip[esub]); in dissect()
560 if (OP(m->g->strip[esub]) == (sop)OOR2) in dissect()
561 esub--; in dissect()
563 assert(OP(m->g->strip[esub]) == O_CH); in dissect()
565 dp = dissect(m, sp, rest, ssub, esub); in dissect()
577 i = OPND(m->g->strip[ss]); in dissect()
578 assert(0 < i && i <= m->g->nsub); in dissect()
579 m->pmatch[i].rm_so = sp - m->offp; in dissect()
582 i = OPND(m->g->strip[ss]); in dissect()
583 assert(0 < i && i <= m->g->nsub); in dissect()
584 m->pmatch[i].rm_eo = sp - m->offp; in dissect()
596 #define ISBOW(m, sp) \ argument
597 (sp < m->endp && ISWORD(*sp) && \
598 ((sp == m->beginp && !(m->eflags®_NOTBOL)) || \
599 (sp > m->offp && !ISWORD(*(sp-1)))))
600 #define ISEOW(m, sp) \ argument
601 (((sp == m->endp && !(m->eflags®_NOTEOL)) || \
602 (sp < m->endp && *sp == '\n' && \
603 (m->g->cflags®_NEWLINE)) || \
604 (sp < m->endp && !ISWORD(*sp)) ) && \
605 (sp > m->beginp && ISWORD(*(sp-1)))) \
608 - backref - figure out what matched what, figuring in back references
609 == static const char *backref(struct match *m, const char *start, \
613 backref(struct match *m, in backref() argument
641 switch (OP(s = m->g->strip[ss])) { in backref()
645 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); in backref()
652 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); in backref()
659 cs = &m->g->sets[OPND(s)]; in backref()
660 sp += XMBRTOWC(&wc, sp, stop - sp, &m->mbs, BADCHAR); in backref()
665 if (sp == m->beginp && (m->eflags & REG_NOTBOL) == 0) in backref()
671 if (sp == m->endp && (m->eflags & REG_NOTEOL) == 0) in backref()
677 if ((sp == m->beginp && !(m->eflags®_NOTBOL)) || in backref()
678 (sp > m->offp && sp < m->endp && in backref()
679 *(sp-1) == '\n' && (m->g->cflags®_NEWLINE))) in backref()
685 if ( (sp == m->endp && !(m->eflags®_NOTEOL)) || in backref()
686 (sp < m->endp && *sp == '\n' && in backref()
687 (m->g->cflags®_NEWLINE)) ) in backref()
693 if (ISBOW(m, sp) || ISEOW(m, sp)) in backref()
699 if (((sp == m->beginp) && !ISWORD(*sp)) || in backref()
700 (sp == m->endp && !ISWORD(*(sp - 1)))) in backref()
702 else if (ISWORD(*(sp - 1)) == ISWORD(*sp)) in backref()
708 if (ISBOW(m, sp)) in backref()
714 if (ISEOW(m, sp)) in backref()
723 s = m->g->strip[ss]; in backref()
727 } while (OP(s = m->g->strip[ss]) != (sop)O_CH); in backref()
739 ss--; /* adjust for the for's final increment */ in backref()
743 s = m->g->strip[ss]; in backref()
747 assert(0 < i && i <= m->g->nsub); in backref()
748 if (m->pmatch[i].rm_eo == -1) in backref()
750 assert(m->pmatch[i].rm_so != -1); in backref()
751 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so; in backref()
754 assert(stop - m->beginp >= len); in backref()
755 if (sp > stop - len) in backref()
757 ssp = m->offp + m->pmatch[i].rm_so; in backref()
760 while (m->g->strip[ss] != (sop)SOP(O_BACK, i)) in backref()
762 return(backref(m, sp+len, stop, ss+1, stopst, lev, rec)); in backref()
764 dp = backref(m, sp, stop, ss+1, stopst, lev, rec); in backref()
767 return(backref(m, sp, stop, ss+OPND(s)+1, stopst, lev, rec)); in backref()
769 assert(m->lastpos != NULL); in backref()
770 assert(lev+1 <= m->g->nplus); in backref()
771 m->lastpos[lev+1] = sp; in backref()
772 return(backref(m, sp, stop, ss+1, stopst, lev+1, rec)); in backref()
774 if (sp == m->lastpos[lev]) /* last pass matched null */ in backref()
775 return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); in backref()
777 m->lastpos[lev] = sp; in backref()
778 dp = backref(m, sp, stop, ss-OPND(s)+1, stopst, lev, rec); in backref()
780 return(backref(m, sp, stop, ss+1, stopst, lev-1, rec)); in backref()
785 esub = ss + OPND(s) - 1; in backref()
786 assert(OP(m->g->strip[esub]) == OOR1); in backref()
788 dp = backref(m, sp, stop, ssub, esub, lev, rec); in backref()
792 if (OP(m->g->strip[esub]) == (sop)O_CH) in backref()
795 assert(OP(m->g->strip[esub]) == (sop)OOR2); in backref()
797 esub += OPND(m->g->strip[esub]); in backref()
798 if (OP(m->g->strip[esub]) == (sop)OOR2) in backref()
799 esub--; in backref()
801 assert(OP(m->g->strip[esub]) == O_CH); in backref()
807 assert(0 < i && i <= m->g->nsub); in backref()
808 offsave = m->pmatch[i].rm_so; in backref()
809 m->pmatch[i].rm_so = sp - m->offp; in backref()
810 dp = backref(m, sp, stop, ss+1, stopst, lev, rec); in backref()
813 m->pmatch[i].rm_so = offsave; in backref()
817 assert(0 < i && i <= m->g->nsub); in backref()
818 offsave = m->pmatch[i].rm_eo; in backref()
819 m->pmatch[i].rm_eo = sp - m->offp; in backref()
820 dp = backref(m, sp, stop, ss+1, stopst, lev, rec); in backref()
823 m->pmatch[i].rm_eo = offsave; in backref()
837 - walk - step through the string either quickly or slowly
838 == static const char *walk(struct match *m, const char *start, \
842 walk(struct match *m, const char *start, const char *stop, sopno startst, in walk() argument
845 states st = m->st; in walk()
846 states fresh = m->fresh; in walk()
847 states empty = m->empty; in walk()
848 states tmp = m->tmp; in walk()
862 st = step(m->g, startst, stopst, st, NOTHING, st, sflags); in walk()
866 if (start == m->offp || (start == m->beginp && !(m->eflags®_NOTBOL))) in walk()
870 * XXX Wrong if the previous character was multi-byte. in walk()
874 c = (uch)*(start - 1); in walk()
880 if (p == m->endp) { in walk()
884 clen = XMBRTOWC(&c, p, m->endp - p, &m->mbs, BADCHAR); in walk()
892 if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || in walk()
893 (lastc == OUT && !(m->eflags®_NOTBOL)) ) { in walk()
895 i = m->g->nbol; in walk()
897 if ( (c == '\n' && m->g->cflags®_NEWLINE) || in walk()
898 (c == OUT && !(m->eflags®_NOTEOL)) ) { in walk()
900 i += m->g->neol; in walk()
902 if (lastc == OUT && (m->eflags & REG_NOTBOL) == 0) { in walk()
907 if (c == OUT && (m->eflags & REG_NOTEOL) == 0) { in walk()
913 for (; i > 0; i--) in walk()
914 st = step(m->g, startst, stopst, st, flagch, st, in walk()
929 st = step(m->g, startst, stopst, st, flagch, st, sflags); in walk()
940 st = step(m->g, startst, stopst, st, flagch, st, sflags); in walk()
951 if (EQ(st, empty) || p == stop || clen > (size_t)(stop - p)) in walk()
961 st = step(m->g, startst, stopst, tmp, c, st, sflags); in walk()
963 assert(EQ(step(m->g, startst, stopst, st, NOTHING, st, sflags), in walk()
970 m->coldp = matchp; in walk()
972 return (p + XMBRTOWC(NULL, p, stop - p, &m->mbs, 0)); in walk()
980 - step - map set of states reachable before char to set reachable after
983 == #define BOL (OUT-1)
984 == #define EOL (BOL-1)
985 == #define BOLEOL (BOL-2)
986 == #define NOTHING (BOL-3)
987 == #define BOW (BOL-4)
988 == #define EOW (BOL-5)
989 == #define BADCHAR (BOL-6)
1009 s = g->strip[pc]; in step()
1012 assert(pc == stop-1); in step()
1057 cs = &g->sets[OPND(s)]; in step()
1074 pc -= OPND(s) + 1; in step()
1091 assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2); in step()
1097 OP(s = g->strip[pc+look]) != (sop)O_CH; in step()
1105 if (OP(g->strip[pc+OPND(s)]) != (sop)O_CH) { in step()
1106 assert(OP(g->strip[pc+OPND(s)]) == (sop)OOR2); in step()
1124 - print - print a set of states
1126 == static void print(struct match *m, const char *caption, states st, \
1131 print(struct match *m, in print() argument
1137 struct re_guts *g = m->g; in print()
1141 if (!(m->eflags®_TRACE)) in print()
1147 for (i = 0; i < g->nstates; i++) in print()
1156 - at - print current situation
1158 == static void at(struct match *m, const char *title, const char *start, \
1163 at( struct match *m, in at() argument
1170 if (!(m->eflags®_TRACE)) in at()
1173 printf("%s %s-", title, pchar(*start)); in at()
1175 printf("%ld-%ld\n", (long)startst, (long)stopst); in at()
1181 - pchar - make a character printable
1187 * duplicate here avoids having a debugging-capable regexec.o tied to
1189 * the non-debug compilation anyway, so it doesn't matter much.
1191 static const char * /* -> representation */