Lines Matching +full:p +full:- +full:states
3 /*-
74 const RCHAR_T *beginp; /* start of string -- virtual NUL precedes */
75 const RCHAR_T *endp; /* end of string -- virtual NUL here */
79 states st; /* current states */
80 states fresh; /* states for a fresh start */
81 states tmp; /* temporary */
82 states empty; /* empty set of states */
96 static states step(struct re_guts *g, sopno start, sopno stop, states bef, int flag, RCHAR_T ch, st…
104 static void print(struct match *m, char *caption, states st, int ch, FILE *d);
121 #define NOTE(str) do { if (m->eflags®_TRACE) printf("=%s\n", (str)); } while(0);
129 - matcher - the actual matching engine
140 const sopno gf = g->firststate+1; /* +1 for OEND */ in matcher()
141 const sopno gl = g->laststate; in matcher()
146 if (g->cflags®_NOSUB) in matcher()
159 if (g->must != NULL) { in matcher()
161 if (*dp == g->must[0] && (size_t)(stop - dp) >= g->mlen && in matcher()
162 MEMCMP(dp, g->must, g->mlen) == 0) in matcher()
164 if (dp == stop) /* we didn't find g->must */ in matcher()
169 m->g = g; in matcher()
170 m->eflags = eflags; in matcher()
171 m->pmatch = NULL; in matcher()
172 m->lastpos = NULL; in matcher()
173 m->offp = string; in matcher()
174 m->beginp = start; in matcher()
175 m->endp = stop; in matcher()
177 SETUP(m->st); in matcher()
178 SETUP(m->fresh); in matcher()
179 SETUP(m->tmp); in matcher()
180 SETUP(m->empty); in matcher()
181 CLEAR(m->empty); in matcher()
190 if (nmatch == 0 && !g->backrefs) in matcher()
194 assert(m->coldp != NULL); in matcher()
197 endp = slow(m, m->coldp, stop, gf, gl); in matcher()
200 assert(m->coldp < m->endp); in matcher()
201 m->coldp++; in matcher()
203 if (nmatch == 1 && !g->backrefs) in matcher()
207 if (m->pmatch == NULL) in matcher()
208 m->pmatch = (regmatch_t *)malloc((m->g->nsub + 1) * in matcher()
210 if (m->pmatch == NULL) { in matcher()
214 for (i = 1; i <= m->g->nsub; i++) in matcher()
215 m->pmatch[i].rm_so = m->pmatch[i].rm_eo = -1; in matcher()
216 if (!g->backrefs && !(m->eflags®_BACKR)) { in matcher()
218 dp = dissect(m, m->coldp, endp, gf, gl); in matcher()
220 if (g->nplus > 0 && m->lastpos == NULL) in matcher()
221 m->lastpos = (const RCHAR_T **)malloc((g->nplus+1) * in matcher()
223 if (g->nplus > 0 && m->lastpos == NULL) { in matcher()
224 free(m->pmatch); in matcher()
229 dp = backref(m, m->coldp, endp, gf, gl, (sopno)0); in matcher()
234 /* uh-oh... we couldn't find a subexpression-level match */ in matcher()
235 assert(g->backrefs); /* must be back references doing it */ in matcher()
236 assert(g->nplus == 0 || m->lastpos != NULL); in matcher()
238 if (dp != NULL || endp <= m->coldp) in matcher()
241 endp = slow(m, m->coldp, endp-1, gf, gl); in matcher()
246 for (i = 1; i <= m->g->nsub; i++) { in matcher()
247 assert(m->pmatch[i].rm_so == -1); in matcher()
248 assert(m->pmatch[i].rm_eo == -1); in matcher()
252 dp = backref(m, m->coldp, endp, gf, gl, (sopno)0); in matcher()
260 start = m->coldp + 1; /* recycle starting later */ in matcher()
266 pmatch[0].rm_so = m->coldp - m->offp; in matcher()
267 pmatch[0].rm_eo = endp - m->offp; in matcher()
270 assert(m->pmatch != NULL); in matcher()
272 if (i <= m->g->nsub) in matcher()
273 pmatch[i] = m->pmatch[i]; in matcher()
275 pmatch[i].rm_so = -1; in matcher()
276 pmatch[i].rm_eo = -1; in matcher()
280 if (m->pmatch != NULL) in matcher()
281 free((char *)m->pmatch); in matcher()
282 if (m->lastpos != NULL) in matcher()
283 free((char *)m->lastpos); in matcher()
289 - dissect - figure out what matched what, no back references
314 switch (m->g->strip[es]) { in dissect()
317 es += m->g->stripdata[es]; in dissect()
320 while (m->g->strip[es] != O_CH) in dissect()
321 es += m->g->stripdata[es]; in dissect()
327 switch (m->g->strip[ss]) { in dissect()
358 /* no -- try a shorter match for this one */ in dissect()
359 stp = rest - 1; in dissect()
363 esub = es - 1; in dissect()
382 /* no -- try a shorter match for this one */ in dissect()
383 stp = rest - 1; in dissect()
387 esub = es - 1; in dissect()
418 /* no -- try a shorter match for this one */ in dissect()
419 stp = rest - 1; in dissect()
423 esub = ss + m->g->stripdata[ss] - 1; in dissect()
424 assert(m->g->strip[esub] == OOR1); in dissect()
429 assert(m->g->strip[esub] == OOR1); in dissect()
431 assert(m->g->strip[esub] == OOR2); in dissect()
433 esub += m->g->stripdata[esub]; in dissect()
434 if (m->g->strip[esub] == OOR2) in dissect()
435 esub--; in dissect()
437 assert(m->g->strip[esub] == O_CH); in dissect()
451 i = m->g->stripdata[ss]; in dissect()
452 assert(0 < i && i <= m->g->nsub); in dissect()
453 m->pmatch[i].rm_so = sp - m->offp; in dissect()
456 i = m->g->stripdata[ss]; in dissect()
457 assert(0 < i && i <= m->g->nsub); in dissect()
458 m->pmatch[i].rm_eo = sp - m->offp; in dissect()
471 - backref - figure out what matched what, figuring in back references
497 s = m->g->strip[ss]; in backref()
498 d = m->g->stripdata[ss]; in backref()
510 cs = &m->g->sets[d]; in backref()
515 if ( (sp == m->beginp && !(m->eflags®_NOTBOL)) || in backref()
516 (sp < m->endp && *(sp-1) == '\n' && in backref()
517 (m->g->cflags®_NEWLINE)) ) in backref()
523 if ( (sp == m->endp && !(m->eflags®_NOTEOL)) || in backref()
524 (sp < m->endp && *sp == '\n' && in backref()
525 (m->g->cflags®_NEWLINE)) ) in backref()
531 if (( (sp == m->beginp && !(m->eflags®_NOTBOL)) || in backref()
532 (sp < m->endp && *(sp-1) == '\n' && in backref()
533 (m->g->cflags®_NEWLINE)) || in backref()
534 (sp > m->beginp && in backref()
535 !ISWORD(*(sp-1))) ) && in backref()
536 (sp < m->endp && ISWORD(*sp)) ) in backref()
542 if (( (sp == m->endp && !(m->eflags®_NOTEOL)) || in backref()
543 (sp < m->endp && *sp == '\n' && in backref()
544 (m->g->cflags®_NEWLINE)) || in backref()
545 (sp < m->endp && !ISWORD(*sp)) ) && in backref()
546 (sp > m->beginp && ISWORD(*(sp-1))) ) in backref()
555 s = m->g->strip[ss]; in backref()
556 d = m->g->stripdata[ss]; in backref()
560 s = m->g->strip[ss]; in backref()
561 d = m->g->stripdata[ss]; in backref()
575 ss--; /* adjust for the for's final increment */ in backref()
579 s = m->g->strip[ss]; in backref()
580 d = m->g->stripdata[ss]; in backref()
584 assert(0 < i && i <= m->g->nsub); in backref()
585 if (m->pmatch[i].rm_eo == -1) in backref()
587 assert(m->pmatch[i].rm_so != -1); in backref()
588 len = m->pmatch[i].rm_eo - m->pmatch[i].rm_so; in backref()
589 assert(stop - m->beginp >= len); in backref()
590 if (sp > stop - len) in backref()
592 ssp = m->offp + m->pmatch[i].rm_so; in backref()
595 while (m->g->strip[ss] != O_BACK || m->g->stripdata[ss] != i) in backref()
606 assert(m->lastpos != NULL); in backref()
607 assert(lev+1 <= m->g->nplus); in backref()
608 m->lastpos[lev+1] = sp; in backref()
612 if (sp == m->lastpos[lev]) /* last pass matched null */ in backref()
613 return(backref(m, sp, stop, ss+1, stopst, lev-1)); in backref()
615 m->lastpos[lev] = sp; in backref()
616 dp = backref(m, sp, stop, ss-d+1, stopst, lev); in backref()
618 return(backref(m, sp, stop, ss+1, stopst, lev-1)); in backref()
624 esub = ss + d - 1; in backref()
625 assert(m->g->strip[esub] == OOR1); in backref()
631 if (m->g->strip[esub] == O_CH) in backref()
634 assert(m->g->strip[esub] == OOR2); in backref()
636 esub += m->g->stripdata[esub]; in backref()
637 if (m->g->strip[esub] == OOR2) in backref()
638 esub--; in backref()
640 assert(m->g->strip[esub] == O_CH); in backref()
645 assert(0 < i && i <= m->g->nsub); in backref()
646 offsave = m->pmatch[i].rm_so; in backref()
647 m->pmatch[i].rm_so = sp - m->offp; in backref()
651 m->pmatch[i].rm_so = offsave; in backref()
656 assert(0 < i && i <= m->g->nsub); in backref()
657 offsave = m->pmatch[i].rm_eo; in backref()
658 m->pmatch[i].rm_eo = sp - m->offp; in backref()
662 m->pmatch[i].rm_eo = offsave; in backref()
677 - fast - step through the string at top speed
683 states st = m->st; in fast()
684 states fresh = m->fresh; in fast()
685 states tmp = m->tmp; in fast()
686 const RCHAR_T *p = start; in fast() local
687 RCHAR_T c = (start == m->beginp) ? OUT : *(start-1); in fast()
691 const RCHAR_T *coldp; /* last p after which no match was underway */ in fast()
695 st = step(m->g, startst, stopst, st, NOTHING, OUT, st); in fast()
697 SP("start", st, *p); in fast()
702 c = (p == m->endp) ? OUT : *p; in fast()
704 coldp = p; in fast()
709 if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || in fast()
710 (lastc == OUT && !(m->eflags®_NOTBOL)) ) { in fast()
712 i = m->g->nbol; in fast()
714 if ( (c == '\n' && m->g->cflags®_NEWLINE) || in fast()
715 (c == OUT && !(m->eflags®_NOTEOL)) ) { in fast()
717 i += m->g->neol; in fast()
720 for (; i > 0; i--) in fast()
721 st = step(m->g, startst, stopst, st, flag, OUT, st); in fast()
735 st = step(m->g, startst, stopst, st, flag, OUT, st); in fast()
740 if (ISSET(st, stopst) || p == stop) in fast()
747 st = step(m->g, startst, stopst, tmp, 0, c, st); in fast()
749 assert(EQ(step(m->g, startst, stopst, st, NOTHING, OUT, st), st)); in fast()
750 p++; in fast()
754 m->coldp = coldp; in fast()
756 return(p+1); in fast()
762 - slow - step through the string more deliberately
768 states st = m->st; in slow()
769 states empty = m->empty; in slow()
770 states tmp = m->tmp; in slow()
771 const RCHAR_T *p = start; in slow() local
772 RCHAR_T c = (start == m->beginp) ? OUT : *(start-1); in slow()
776 const RCHAR_T *matchp; /* last p at which a match ended */ in slow()
781 SP("sstart", st, *p); in slow()
782 st = step(m->g, startst, stopst, st, NOTHING, OUT, st); in slow()
787 c = (p == m->endp) ? OUT : *p; in slow()
792 if ( (lastc == '\n' && m->g->cflags®_NEWLINE) || in slow()
793 (lastc == OUT && !(m->eflags®_NOTBOL)) ) { in slow()
795 i = m->g->nbol; in slow()
797 if ( (c == '\n' && m->g->cflags®_NEWLINE) || in slow()
798 (c == OUT && !(m->eflags®_NOTEOL)) ) { in slow()
800 i += m->g->neol; in slow()
803 for (; i > 0; i--) in slow()
804 st = step(m->g, startst, stopst, st, flag, OUT, st); in slow()
818 st = step(m->g, startst, stopst, st, flag, OUT, st); in slow()
824 matchp = p; in slow()
825 if (EQ(st, empty) || p == stop) in slow()
832 st = step(m->g, startst, stopst, tmp, 0, c, st); in slow()
834 assert(EQ(step(m->g, startst, stopst, st, NOTHING, OUT, st), st)); in slow()
835 p++; in slow()
843 - step - map set of states reachable before char to set reachable after
845 static states
849 states bef, /* states reachable before */ in step()
852 states aft) /* states already known reachable after */ in step()
863 s = g->strip[pc]; in step()
864 d = g->stripdata[pc]; in step()
867 assert(pc == stop-1); in step()
896 cs = &g->sets[d]; in step()
913 pc -= d + 1; in step()
930 assert(OP(g->strip[pc+d]) == OOR2); in step()
936 s = g->strip[pc+look]; in step()
937 d = g->stripdata[pc+look]; in step()
947 if (g->strip[pc+d] != O_CH) { in step()
948 assert(g->strip[pc+d] == OOR2); in step()
966 - print - print a set of states
969 print(struct match *m, char *caption, states st, int ch, FILE *d) in print()
971 struct re_guts *g = m->g; in print()
975 if (!(m->eflags®_TRACE)) in print()
981 for (i = 0; i < g->nstates; i++) in print()
990 - at - print current situation
996 if (!(m->eflags®_TRACE)) in at()
999 printf("%s %s-", title, pchar(*start)); in at()
1001 printf("%ld-%ld\n", (long)startst, (long)stopst); in at()
1007 - pchar - make a character printable
1010 * duplicate here avoids having a debugging-capable regexec.o tied to
1012 * the non-debug compilation anyway, so it doesn't matter much.
1014 static char * /* -> representation */