2 * Copyright 2010 Nexenta Systems, Inc. All rights reserved.
3 * Copyright 2012 Milan Jurik. All rights reserved.
4 * Copyright (c) 2016 by Delphix. All rights reserved.
5 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
6 * Copyright (c) 1992, 1993, 1994
7 * The Regents of the University of California. All rights reserved.
9 * This code is derived from software contributed to Berkeley by
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * The matching engine and friends. This file is #included by regexec.c
39 * after suitable #defines of a variety of macros used herein, so that
40 * different state representations can be used without duplicating masses
45 #define matcher smatcher
48 #define dissect sdissect
49 #define backref sbackref
56 #define matcher lmatcher
59 #define dissect ldissect
60 #define backref lbackref
67 #define matcher mmatcher
70 #define dissect mdissect
71 #define backref mbackref
78 /* another structure passed up and down to avoid zillions of parameters */
82 regmatch_t
*pmatch
; /* [nsub+1] (0 element unused) */
83 const char *offp
; /* offsets work from here */
84 const char *beginp
; /* start of string -- virtual NUL precedes */
85 const char *endp
; /* end of string -- virtual NUL here */
86 const char *coldp
; /* can be no match starting before here */
87 const char **lastpos
; /* [nplus+1] */
89 states st
; /* current states */
90 states fresh
; /* states for a fresh start */
91 states tmp
; /* temporary */
92 states empty
; /* empty set of states */
93 mbstate_t mbs
; /* multibyte conversion state */
96 /* ========= begin header generated by ./mkh ========= */
101 /* === engine.c === */
102 static int matcher(struct re_guts
*, const char *, size_t, regmatch_t
[], int);
103 static const char *dissect(struct match
*, const char *, const char *,
105 static const char *backref(struct match
*, const char *, const char *, sopno
,
107 static const char *fast(struct match
*, const char *, const char *, sopno
,
109 static const char *slow(struct match
*, const char *, const char *, sopno
,
111 static states
step(struct re_guts
*, sopno
, sopno
, states
, wint_t, states
);
112 #define MAX_RECURSION 100
115 #define BOLEOL (BOL-2)
116 #define NOTHING (BOL-3)
119 #define BADCHAR (BOL-6)
120 #define NONCHAR(c) ((c) <= OUT)
122 static void print(struct match
*, const char *, states
, int, FILE *);
125 static void at(struct match
*, const char *, const char *, const char *,
129 static const char *pchar(int ch
);
135 /* ========= end header generated by ./mkh ========= */
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)); }
142 #define SP(t, s, c) /* nothing */
143 #define AT(t, p1, p2, s1, s2) /* nothing */
144 #define NOTE(s) /* nothing */
148 * matcher - the actual matching engine
150 static int /* 0 success, REG_NOMATCH failure */
151 matcher(struct re_guts
*g
, const char *string
, size_t nmatch
,
152 regmatch_t pmatch
[], int eflags
)
157 struct match
*m
= &mv
;
158 const char *dp
= NULL
;
159 const sopno gf
= g
->firststate
+1; /* +1 for OEND */
160 const sopno gl
= g
->laststate
;
163 /* Boyer-Moore algorithms variables */
166 const char *mustfirst
;
167 const char *mustlast
;
171 /* simplify the situation where possible */
172 if (g
->cflags
®_NOSUB
)
175 if (eflags
®_STARTEND
) {
176 start
= string
+ pmatch
[0].rm_so
;
177 stop
= string
+ pmatch
[0].rm_eo
;
180 stop
= start
+ strlen(start
);
186 /* prescreening; this does wonders for this rather slow code */
187 if (g
->must
!= NULL
) {
188 if (g
->charjump
!= NULL
&& g
->matchjump
!= NULL
) {
190 mustlast
= g
->must
+ g
->mlen
- 1;
191 charjump
= g
->charjump
;
192 matchjump
= g
->matchjump
;
194 for (dp
= start
+g
->mlen
-1; dp
< stop
; ) {
195 /* Fast skip non-matches */
196 while (dp
< stop
&& charjump
[(int)*dp
])
197 dp
+= charjump
[(int)*dp
];
204 * We depend on not being used for
205 * for strings of length 1
207 while (*--dp
== *--pp
&& pp
!= mustfirst
)
213 /* Jump to next possible match */
214 mj
= matchjump
[pp
- mustfirst
];
215 cj
= charjump
[(int)*dp
];
216 dp
+= (cj
< mj
? mj
: cj
);
220 return (REG_NOMATCH
);
222 for (dp
= start
; dp
< stop
; dp
++)
223 if (*dp
== g
->must
[0] &&
224 stop
- dp
>= g
->mlen
&&
225 memcmp(dp
, g
->must
, (size_t)g
->mlen
) == 0)
227 if (dp
== stop
) /* we didn't find g->must */
228 return (REG_NOMATCH
);
232 /* match struct setup */
248 /* Adjust start according to moffset, to speed things up */
249 if (dp
!= NULL
&& g
->moffset
> -1)
250 start
= ((dp
- g
->moffset
) < start
) ? start
: dp
- g
->moffset
;
252 SP("mloop", m
->st
, *start
);
254 /* this loop does only one repetition except for backrefs */
256 endp
= fast(m
, start
, stop
, gf
, gl
);
257 if (endp
== NULL
) { /* a miss */
258 if (m
->pmatch
!= NULL
)
259 free((char *)m
->pmatch
);
260 if (m
->lastpos
!= NULL
)
261 free((char *)m
->lastpos
);
263 return (REG_NOMATCH
);
265 if (nmatch
== 0 && !g
->backrefs
)
266 break; /* no further info needed */
269 assert(m
->coldp
!= NULL
);
271 NOTE("finding start");
272 endp
= slow(m
, m
->coldp
, stop
, gf
, gl
);
275 assert(m
->coldp
< m
->endp
);
276 m
->coldp
+= XMBRTOWC(NULL
, m
->coldp
,
277 m
->endp
- m
->coldp
, &m
->mbs
, 0);
279 if (nmatch
== 1 && !g
->backrefs
)
280 break; /* no further info needed */
282 /* oh my, it wants the subexpressions... */
283 if (m
->pmatch
== NULL
)
284 m
->pmatch
= (regmatch_t
*)malloc((m
->g
->nsub
+ 1) *
285 sizeof (regmatch_t
));
286 if (m
->pmatch
== NULL
) {
290 for (i
= 1; i
<= m
->g
->nsub
; i
++)
291 m
->pmatch
[i
].rm_so
= m
->pmatch
[i
].rm_eo
= -1;
292 if (!g
->backrefs
&& !(m
->eflags
®_BACKR
)) {
294 dp
= dissect(m
, m
->coldp
, endp
, gf
, gl
);
296 if (g
->nplus
> 0 && m
->lastpos
== NULL
)
297 m
->lastpos
= malloc((g
->nplus
+1) *
298 sizeof (const char *));
299 if (g
->nplus
> 0 && m
->lastpos
== NULL
) {
304 NOTE("backref dissect");
305 dp
= backref(m
, m
->coldp
, endp
, gf
, gl
, (sopno
)0, 0);
310 /* uh-oh... we couldn't find a subexpression-level match */
311 assert(g
->backrefs
); /* must be back references doing it */
312 assert(g
->nplus
== 0 || m
->lastpos
!= NULL
);
314 if (dp
!= NULL
|| endp
<= m
->coldp
)
317 endp
= slow(m
, m
->coldp
, endp
-1, gf
, gl
);
320 /* try it on a shorter possibility */
322 for (i
= 1; i
<= m
->g
->nsub
; i
++) {
323 assert(m
->pmatch
[i
].rm_so
== -1);
324 assert(m
->pmatch
[i
].rm_eo
== -1);
327 NOTE("backoff dissect");
328 dp
= backref(m
, m
->coldp
, endp
, gf
, gl
, (sopno
)0, 0);
330 assert(dp
== NULL
|| dp
== endp
);
331 if (dp
!= NULL
) /* found a shorter one */
334 /* despite initial appearances, there is no match here */
336 /* recycle starting later */
337 start
= m
->coldp
+ XMBRTOWC(NULL
, m
->coldp
,
338 stop
- m
->coldp
, &m
->mbs
, 0);
339 assert(start
<= stop
);
342 /* fill in the details if requested */
344 pmatch
[0].rm_so
= m
->coldp
- m
->offp
;
345 pmatch
[0].rm_eo
= endp
- m
->offp
;
348 assert(m
->pmatch
!= NULL
);
349 for (i
= 1; i
< nmatch
; i
++)
351 pmatch
[i
] = m
->pmatch
[i
];
353 pmatch
[i
].rm_so
= -1;
354 pmatch
[i
].rm_eo
= -1;
358 if (m
->pmatch
!= NULL
)
359 free((char *)m
->pmatch
);
360 if (m
->lastpos
!= NULL
)
361 free((char *)m
->lastpos
);
367 * dissect - figure out what matched what, no back references
370 dissect(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
374 sopno ss
; /* start sop of current subRE */
375 sopno es
; /* end sop of current subRE */
376 const char *sp
; /* start of string matched by it */
377 const char *stp
; /* string matched by it cannot pass here */
378 const char *rest
; /* start of rest of string */
379 const char *tail
; /* string unmatched by rest of RE */
380 sopno ssub
; /* start sop of subsubRE */
381 sopno esub
; /* end sop of subsubRE */
382 const char *ssp
; /* start of string matched by subsubRE */
383 const char *sep
; /* end of string matched by subsubRE */
384 const char *oldssp
; /* previous ssp */
387 AT("diss", start
, stop
, startst
, stopst
);
389 for (ss
= startst
; ss
< stopst
; ss
= es
) {
390 /* identify end of subRE */
392 switch (OP(m
->g
->strip
[es
])) {
395 es
+= OPND(m
->g
->strip
[es
]);
398 while (OP(m
->g
->strip
[es
]) != O_CH
)
399 es
+= OPND(m
->g
->strip
[es
]);
404 /* figure out what it matched */
405 switch (OP(m
->g
->strip
[ss
])) {
410 sp
+= XMBRTOWC(NULL
, sp
, stop
- start
, &m
->mbs
, 0);
419 sp
+= XMBRTOWC(NULL
, sp
, stop
- start
, &m
->mbs
, 0);
425 /* cases where length of match is hard to find */
429 /* how long could this one be? */
430 rest
= slow(m
, sp
, stp
, ss
, es
);
431 assert(rest
!= NULL
); /* it did match */
432 /* could the rest match the rest? */
433 tail
= slow(m
, rest
, stop
, es
, stopst
);
436 /* no -- try a shorter match for this one */
438 assert(stp
>= sp
); /* it did work */
442 /* did innards match? */
443 if (slow(m
, sp
, rest
, ssub
, esub
) != NULL
) {
444 dp
= dissect(m
, sp
, rest
, ssub
, esub
);
456 /* how long could this one be? */
457 rest
= slow(m
, sp
, stp
, ss
, es
);
458 assert(rest
!= NULL
); /* it did match */
459 /* could the rest match the rest? */
460 tail
= slow(m
, rest
, stop
, es
, stopst
);
463 /* no -- try a shorter match for this one */
465 assert(stp
>= sp
); /* it did work */
471 for (;;) { /* find last match of innards */
472 sep
= slow(m
, ssp
, rest
, ssub
, esub
);
473 if (sep
== NULL
|| sep
== ssp
)
474 break; /* failed or matched null */
475 oldssp
= ssp
; /* on to next try */
479 /* last successful match */
483 assert(sep
== rest
); /* must exhaust substring */
484 assert(slow(m
, ssp
, sep
, ssub
, esub
) == rest
);
485 dp
= dissect(m
, ssp
, sep
, ssub
, esub
);
492 /* how long could this one be? */
493 rest
= slow(m
, sp
, stp
, ss
, es
);
494 assert(rest
!= NULL
); /* it did match */
495 /* could the rest match the rest? */
496 tail
= slow(m
, rest
, stop
, es
, stopst
);
499 /* no -- try a shorter match for this one */
501 assert(stp
>= sp
); /* it did work */
504 esub
= ss
+ OPND(m
->g
->strip
[ss
]) - 1;
505 assert(OP(m
->g
->strip
[esub
]) == OOR1
);
506 for (;;) { /* find first matching branch */
507 if (slow(m
, sp
, rest
, ssub
, esub
) == rest
)
508 break; /* it matched all of it */
509 /* that one missed, try next one */
510 assert(OP(m
->g
->strip
[esub
]) == OOR1
);
512 assert(OP(m
->g
->strip
[esub
]) == OOR2
);
514 esub
+= OPND(m
->g
->strip
[esub
]);
515 if (OP(m
->g
->strip
[esub
]) == OOR2
)
518 assert(OP(m
->g
->strip
[esub
]) == O_CH
);
520 dp
= dissect(m
, sp
, rest
, ssub
, esub
);
532 i
= OPND(m
->g
->strip
[ss
]);
533 assert(0 < i
&& i
<= m
->g
->nsub
);
534 m
->pmatch
[i
].rm_so
= sp
- m
->offp
;
537 i
= OPND(m
->g
->strip
[ss
]);
538 assert(0 < i
&& i
<= m
->g
->nsub
);
539 m
->pmatch
[i
].rm_eo
= sp
- m
->offp
;
552 * backref - figure out what matched what, figuring in back references
555 backref(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
556 sopno stopst
, sopno lev
, /* PLUS nesting level */
560 sopno ss
; /* start sop of current subRE */
561 const char *sp
; /* start of string matched by it */
562 sopno ssub
; /* start sop of subsubRE */
563 sopno esub
; /* end sop of subsubRE */
564 const char *ssp
; /* start of string matched by subsubRE */
573 AT("back", start
, stop
, startst
, stopst
);
576 /* get as far as we can with easy stuff */
578 for (ss
= startst
; !hard
&& ss
< stopst
; ss
++)
579 switch (OP(s
= m
->g
->strip
[ss
])) {
583 sp
+= XMBRTOWC(&wc
, sp
, stop
- sp
, &m
->mbs
, BADCHAR
);
590 sp
+= XMBRTOWC(&wc
, sp
, stop
- sp
, &m
->mbs
, BADCHAR
);
597 cs
= &m
->g
->sets
[OPND(s
)];
598 sp
+= XMBRTOWC(&wc
, sp
, stop
- sp
, &m
->mbs
, BADCHAR
);
599 if (wc
== BADCHAR
|| !CHIN(cs
, wc
))
603 if ((sp
== m
->beginp
&& !(m
->eflags
®_NOTBOL
)) ||
604 (sp
> m
->offp
&& sp
< m
->endp
&&
605 *(sp
-1) == '\n' && (m
->g
->cflags
®_NEWLINE
))) {
610 if ((sp
== m
->endp
&& !(m
->eflags
®_NOTEOL
)) ||
611 (sp
< m
->endp
&& *sp
== '\n' &&
612 (m
->g
->cflags
®_NEWLINE
))) {
617 if (sp
< m
->endp
&& ISWORD(*sp
) &&
618 ((sp
== m
->beginp
&& !(m
->eflags
®_NOTBOL
)) ||
619 (sp
> m
->offp
&& !ISWORD(*(sp
-1))))) {
624 if (((sp
== m
->endp
&& !(m
->eflags
®_NOTEOL
)) ||
625 (sp
< m
->endp
&& *sp
== '\n' &&
626 (m
->g
->cflags
®_NEWLINE
)) ||
627 (sp
< m
->endp
&& !ISWORD(*sp
))) &&
628 (sp
> m
->beginp
&& ISWORD(*(sp
-1)))) {
634 case OOR1
: /* matches null but needs to skip */
638 assert(OP(s
) == OOR2
);
640 } while (OP(s
= m
->g
->strip
[ss
]) != O_CH
);
641 /* note that the ss++ gets us past the O_CH */
643 default: /* have to make a choice */
647 if (!hard
) { /* that was it! */
652 ss
--; /* adjust for the for's final increment */
655 AT("hard", sp
, stop
, ss
, stopst
);
658 case OBACK_
: /* the vilest depths */
660 assert(0 < i
&& i
<= m
->g
->nsub
);
661 if (m
->pmatch
[i
].rm_eo
== -1)
663 assert(m
->pmatch
[i
].rm_so
!= -1);
664 len
= m
->pmatch
[i
].rm_eo
- m
->pmatch
[i
].rm_so
;
665 if (len
== 0 && rec
++ > MAX_RECURSION
)
667 assert(stop
- m
->beginp
>= len
);
669 return (NULL
); /* not enough left to match */
670 ssp
= m
->offp
+ m
->pmatch
[i
].rm_so
;
671 if (memcmp(sp
, ssp
, len
) != 0)
673 while (m
->g
->strip
[ss
] != SOP(O_BACK
, i
))
675 return (backref(m
, sp
+len
, stop
, ss
+1, stopst
, lev
, rec
));
676 case OQUEST_
: /* to null or not */
677 dp
= backref(m
, sp
, stop
, ss
+1, stopst
, lev
, rec
);
679 return (dp
); /* not */
680 return (backref(m
, sp
, stop
, ss
+OPND(s
)+1, stopst
, lev
, rec
));
682 assert(m
->lastpos
!= NULL
);
683 assert(lev
+1 <= m
->g
->nplus
);
684 m
->lastpos
[lev
+1] = sp
;
685 return (backref(m
, sp
, stop
, ss
+1, stopst
, lev
+1, rec
));
687 if (sp
== m
->lastpos
[lev
]) /* last pass matched null */
688 return (backref(m
, sp
, stop
, ss
+1, stopst
, lev
-1, rec
));
689 /* try another pass */
690 m
->lastpos
[lev
] = sp
;
691 dp
= backref(m
, sp
, stop
, ss
-OPND(s
)+1, stopst
, lev
, rec
);
693 return (backref(m
, sp
, stop
, ss
+1, stopst
, lev
-1, rec
));
695 case OCH_
: /* find the right one, if any */
697 esub
= ss
+ OPND(s
) - 1;
698 assert(OP(m
->g
->strip
[esub
]) == OOR1
);
699 for (;;) { /* find first matching branch */
700 dp
= backref(m
, sp
, stop
, ssub
, esub
, lev
, rec
);
703 /* that one missed, try next one */
704 if (OP(m
->g
->strip
[esub
]) == O_CH
)
705 return (NULL
); /* there is none */
707 assert(OP(m
->g
->strip
[esub
]) == OOR2
);
709 esub
+= OPND(m
->g
->strip
[esub
]);
710 if (OP(m
->g
->strip
[esub
]) == OOR2
)
713 assert(OP(m
->g
->strip
[esub
]) == O_CH
);
717 case OLPAREN
: /* must undo assignment if rest fails */
719 assert(0 < i
&& i
<= m
->g
->nsub
);
720 offsave
= m
->pmatch
[i
].rm_so
;
721 m
->pmatch
[i
].rm_so
= sp
- m
->offp
;
722 dp
= backref(m
, sp
, stop
, ss
+1, stopst
, lev
, rec
);
725 m
->pmatch
[i
].rm_so
= offsave
;
727 case ORPAREN
: /* must undo assignment if rest fails */
729 assert(0 < i
&& i
<= m
->g
->nsub
);
730 offsave
= m
->pmatch
[i
].rm_eo
;
731 m
->pmatch
[i
].rm_eo
= sp
- m
->offp
;
732 dp
= backref(m
, sp
, stop
, ss
+1, stopst
, lev
, rec
);
735 m
->pmatch
[i
].rm_eo
= offsave
;
748 * fast - step through the string at top speed
751 fast(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
755 states fresh
= m
->fresh
;
757 const char *p
= start
;
759 wint_t lastc
; /* previous c */
762 const char *coldp
; /* last p after which no match was underway */
768 st
= step(m
->g
, startst
, stopst
, st
, NOTHING
, st
);
772 if (start
== m
->offp
|| (start
== m
->beginp
&& !(m
->eflags
®_NOTBOL
)))
776 * XXX Wrong if the previous character was multi-byte.
777 * Newline never is (in encodings supported by FreeBSD),
778 * so this only breaks the ISWORD tests below.
780 c
= (uch
)*(start
- 1);
789 clen
= XMBRTOWC(&c
, p
, m
->endp
- p
, &m
->mbs
, BADCHAR
);
793 /* is there an EOL and/or BOL between lastc and c? */
796 if ((lastc
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
797 (lastc
== OUT
&& !(m
->eflags
®_NOTBOL
))) {
801 if ((c
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
802 (c
== OUT
&& !(m
->eflags
®_NOTEOL
))) {
803 flagch
= (flagch
== BOL
) ? BOLEOL
: EOL
;
808 st
= step(m
->g
, startst
, stopst
, st
,
813 /* how about a word boundary? */
814 if ((flagch
== BOL
|| (lastc
!= OUT
&& !ISWORD(lastc
))) &&
815 (c
!= OUT
&& ISWORD(c
))) {
818 if ((lastc
!= OUT
&& ISWORD(lastc
)) &&
819 (flagch
== EOL
|| (c
!= OUT
&& !ISWORD(c
)))) {
822 if (flagch
== BOW
|| flagch
== EOW
) {
823 st
= step(m
->g
, startst
, stopst
, st
, flagch
, st
);
828 if (ISSET(st
, stopst
) || p
== stop
|| clen
> stop
- p
)
829 break; /* NOTE BREAK OUT */
831 /* no, we must deal with this character */
835 st
= step(m
->g
, startst
, stopst
, tmp
, c
, st
);
837 assert(EQ(step(m
->g
, startst
, stopst
, st
, NOTHING
, st
), st
));
841 assert(coldp
!= NULL
);
843 if (ISSET(st
, stopst
))
844 return (p
+XMBRTOWC(NULL
, p
, stop
- p
, &m
->mbs
, 0));
850 * slow - step through the string more deliberately
853 slow(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
857 states empty
= m
->empty
;
859 const char *p
= start
;
861 wint_t lastc
; /* previous c */
864 const char *matchp
; /* last p at which a match ended */
867 AT("slow", start
, stop
, startst
, stopst
);
870 SP("sstart", st
, *p
);
871 st
= step(m
->g
, startst
, stopst
, st
, NOTHING
, st
);
873 if (start
== m
->offp
|| (start
== m
->beginp
&& !(m
->eflags
®_NOTBOL
)))
877 * XXX Wrong if the previous character was multi-byte.
878 * Newline never is (in encodings supported by FreeBSD),
879 * so this only breaks the ISWORD tests below.
881 c
= (uch
)*(start
- 1);
890 clen
= XMBRTOWC(&c
, p
, m
->endp
- p
, &m
->mbs
, BADCHAR
);
892 /* is there an EOL and/or BOL between lastc and c? */
895 if ((lastc
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
896 (lastc
== OUT
&& !(m
->eflags
®_NOTBOL
))) {
900 if ((c
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
901 (c
== OUT
&& !(m
->eflags
®_NOTEOL
))) {
902 flagch
= (flagch
== BOL
) ? BOLEOL
: EOL
;
907 st
= step(m
->g
, startst
, stopst
, st
,
909 SP("sboleol", st
, c
);
912 /* how about a word boundary? */
913 if ((flagch
== BOL
|| (lastc
!= OUT
&& !ISWORD(lastc
))) &&
914 (c
!= OUT
&& ISWORD(c
))) {
917 if ((lastc
!= OUT
&& ISWORD(lastc
)) &&
918 (flagch
== EOL
|| (c
!= OUT
&& !ISWORD(c
)))) {
921 if (flagch
== BOW
|| flagch
== EOW
) {
922 st
= step(m
->g
, startst
, stopst
, st
, flagch
, st
);
923 SP("sboweow", st
, c
);
927 if (ISSET(st
, stopst
))
929 if (EQ(st
, empty
) || p
== stop
|| clen
> stop
- p
)
930 break; /* NOTE BREAK OUT */
932 /* no, we must deal with this character */
936 st
= step(m
->g
, startst
, stopst
, tmp
, c
, st
);
938 assert(EQ(step(m
->g
, startst
, stopst
, st
, NOTHING
, st
), st
));
947 * step - map set of states reachable before char to set reachable after
950 step(struct re_guts
*g
,
951 sopno start
, /* start state within strip */
952 sopno stop
, /* state after stop state within strip */
953 states bef
, /* states reachable before */
954 wint_t ch
, /* character or NONCHAR code */
955 states aft
) /* states already known reachable after */
960 onestate here
; /* note, macros know this name */
964 for (pc
= start
, INIT(here
, pc
); pc
!= stop
; pc
++, INC(here
)) {
968 assert(pc
== stop
-1);
971 /* only characters can match */
972 assert(!NONCHAR(ch
) || ch
!= OPND(s
));
977 if (ch
== BOL
|| ch
== BOLEOL
)
981 if (ch
== EOL
|| ch
== BOLEOL
)
997 cs
= &g
->sets
[OPND(s
)];
998 if (!NONCHAR(ch
) && CHIN(cs
, ch
))
1001 case OBACK_
: /* ignored here */
1005 case OPLUS_
: /* forward, this is just an empty */
1008 case O_PLUS
: /* both forward and back */
1010 i
= ISSETBACK(aft
, OPND(s
));
1011 BACK(aft
, aft
, OPND(s
));
1012 if (!i
&& ISSETBACK(aft
, OPND(s
))) {
1013 /* oho, must reconsider loop body */
1018 case OQUEST_
: /* two branches, both forward */
1020 FWD(aft
, aft
, OPND(s
));
1022 case O_QUEST
: /* just an empty */
1025 case OLPAREN
: /* not significant here */
1029 case OCH_
: /* mark the first two branches */
1031 assert(OP(g
->strip
[pc
+OPND(s
)]) == OOR2
);
1032 FWD(aft
, aft
, OPND(s
));
1034 case OOR1
: /* done a branch, find the O_CH */
1035 if (ISSTATEIN(aft
, here
)) {
1037 OP(s
= g
->strip
[pc
+look
]) != O_CH
;
1039 assert(OP(s
) == OOR2
);
1040 FWD(aft
, aft
, look
+ 1);
1043 case OOR2
: /* propagate OCH_'s marking */
1045 if (OP(g
->strip
[pc
+OPND(s
)]) != O_CH
) {
1046 assert(OP(g
->strip
[pc
+OPND(s
)]) == OOR2
);
1047 FWD(aft
, aft
, OPND(s
));
1050 case O_CH
: /* just empty */
1053 default: /* ooooops... */
1064 * print - print a set of states
1067 print(struct match
*m
, const char *caption
, states st
, int ch
, FILE *d
)
1069 struct re_guts
*g
= m
->g
;
1073 if (!(m
->eflags
®_TRACE
))
1076 (void) fprintf(d
, "%s", caption
);
1078 (void) fprintf(d
, " %s", pchar(ch
));
1079 for (i
= 0; i
< g
->nstates
; i
++)
1081 (void) fprintf(d
, "%s%d", (first
) ? "\t" : ", ", i
);
1084 (void) fprintf(d
, "\n");
1088 * at - print current situation
1091 at(struct match
*m
, const char *title
, const char *start
, const char *stop
,
1092 sopno startst
, sopno stopst
)
1094 if (!(m
->eflags
®_TRACE
))
1097 (void) printf("%s %s-", title
, pchar(*start
));
1098 (void) printf("%s ", pchar(*stop
));
1099 (void) printf("%ld-%ld\n", (long)startst
, (long)stopst
);
1103 #define PCHARDONE /* never again */
1105 * pchar - make a character printable
1107 * Is this identical to regchar() over in debug.c? Well, yes. But a
1108 * duplicate here avoids having a debugging-capable regexec.o tied to
1109 * a matching debug.o, and this is convenient. It all disappears in
1110 * the non-debug compilation anyway, so it doesn't matter much.
1115 static char pbuf
[10];
1117 if (isprint((uch
)ch
) || ch
== ' ')
1118 (void) sprintf(pbuf
, "%c", ch
);
1120 (void) sprintf(pbuf
, "\\%o", ch
);