2 * Copyright 2010 Nexenta Systems, Inc. All rights reserved.
3 * Copyright 2012 Milan Jurik. All rights reserved.
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.
8 * This code is derived from software contributed to Berkeley by
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
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 * 4. 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.
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
37 * The matching engine and friends. This file is #included by regexec.c
38 * after suitable #defines of a variety of macros used herein, so that
39 * different state representations can be used without duplicating masses
44 #define matcher smatcher
47 #define dissect sdissect
48 #define backref sbackref
55 #define matcher lmatcher
58 #define dissect ldissect
59 #define backref lbackref
66 #define matcher mmatcher
69 #define dissect mdissect
70 #define backref mbackref
77 /* another structure passed up and down to avoid zillions of parameters */
81 regmatch_t
*pmatch
; /* [nsub+1] (0 element unused) */
82 const char *offp
; /* offsets work from here */
83 const char *beginp
; /* start of string -- virtual NUL precedes */
84 const char *endp
; /* end of string -- virtual NUL here */
85 const char *coldp
; /* can be no match starting before here */
86 const char **lastpos
; /* [nplus+1] */
88 states st
; /* current states */
89 states fresh
; /* states for a fresh start */
90 states tmp
; /* temporary */
91 states empty
; /* empty set of states */
92 mbstate_t mbs
; /* multibyte conversion state */
95 /* ========= begin header generated by ./mkh ========= */
100 /* === engine.c === */
101 static int matcher(struct re_guts
*, const char *, size_t, regmatch_t
[], int);
102 static const char *dissect(struct match
*, const char *, const char *,
104 static const char *backref(struct match
*, const char *, const char *, sopno
,
106 static const char *fast(struct match
*, const char *, const char *, sopno
,
108 static const char *slow(struct match
*, const char *, const char *, sopno
,
110 static states
step(struct re_guts
*, sopno
, sopno
, states
, wint_t, states
);
111 #define MAX_RECURSION 100
114 #define BOLEOL (BOL-2)
115 #define NOTHING (BOL-3)
118 #define BADCHAR (BOL-6)
119 #define NONCHAR(c) ((c) <= OUT)
121 static void print(struct match
*, const char *, states
, int, FILE *);
124 static void at(struct match
*, const char *, const char *, const char *,
128 static const char *pchar(int ch
);
134 /* ========= end header generated by ./mkh ========= */
137 #define SP(t, s, c) print(m, t, s, c, stdout)
138 #define AT(t, p1, p2, s1, s2) at(m, t, p1, p2, s1, s2)
139 #define NOTE(str) { if (m->eflags®_TRACE) printf("=%s\n", (str)); }
141 #define SP(t, s, c) /* nothing */
142 #define AT(t, p1, p2, s1, s2) /* nothing */
143 #define NOTE(s) /* nothing */
147 * matcher - the actual matching engine
149 static int /* 0 success, REG_NOMATCH failure */
150 matcher(struct re_guts
*g
,
159 struct match
*m
= &mv
;
161 const sopno gf
= g
->firststate
+1; /* +1 for OEND */
162 const sopno gl
= g
->laststate
;
165 /* Boyer-Moore algorithms variables */
168 const char *mustfirst
;
169 const char *mustlast
;
173 /* simplify the situation where possible */
174 if (g
->cflags
®_NOSUB
)
177 if (eflags
®_STARTEND
) {
178 start
= string
+ pmatch
[0].rm_so
;
179 stop
= string
+ pmatch
[0].rm_eo
;
182 stop
= start
+ strlen(start
);
188 /* prescreening; this does wonders for this rather slow code */
189 if (g
->must
!= NULL
) {
190 if (g
->charjump
!= NULL
&& g
->matchjump
!= NULL
) {
192 mustlast
= g
->must
+ g
->mlen
- 1;
193 charjump
= g
->charjump
;
194 matchjump
= g
->matchjump
;
196 for (dp
= start
+g
->mlen
-1; dp
< stop
; ) {
197 /* Fast skip non-matches */
198 while (dp
< stop
&& charjump
[(int)*dp
])
199 dp
+= charjump
[(int)*dp
];
206 * We depend on not being used for
207 * for strings of length 1
209 while (*--dp
== *--pp
&& pp
!= mustfirst
)
215 /* Jump to next possible match */
216 mj
= matchjump
[pp
- mustfirst
];
217 cj
= charjump
[(int)*dp
];
218 dp
+= (cj
< mj
? mj
: cj
);
222 return (REG_NOMATCH
);
224 for (dp
= start
; dp
< stop
; dp
++)
225 if (*dp
== g
->must
[0] &&
226 stop
- dp
>= g
->mlen
&&
227 memcmp(dp
, g
->must
, (size_t)g
->mlen
) == 0)
229 if (dp
== stop
) /* we didn't find g->must */
230 return (REG_NOMATCH
);
234 /* match struct setup */
250 /* Adjust start according to moffset, to speed things up */
252 start
= ((dp
- g
->moffset
) < start
) ? start
: dp
- g
->moffset
;
254 SP("mloop", m
->st
, *start
);
256 /* this loop does only one repetition except for backrefs */
258 endp
= fast(m
, start
, stop
, gf
, gl
);
259 if (endp
== NULL
) { /* a miss */
260 if (m
->pmatch
!= NULL
)
261 free((char *)m
->pmatch
);
262 if (m
->lastpos
!= NULL
)
263 free((char *)m
->lastpos
);
265 return (REG_NOMATCH
);
267 if (nmatch
== 0 && !g
->backrefs
)
268 break; /* no further info needed */
271 assert(m
->coldp
!= NULL
);
273 NOTE("finding start");
274 endp
= slow(m
, m
->coldp
, stop
, gf
, gl
);
277 assert(m
->coldp
< m
->endp
);
278 m
->coldp
+= XMBRTOWC(NULL
, m
->coldp
,
279 m
->endp
- m
->coldp
, &m
->mbs
, 0);
281 if (nmatch
== 1 && !g
->backrefs
)
282 break; /* no further info needed */
284 /* oh my, he wants the subexpressions... */
285 if (m
->pmatch
== NULL
)
286 m
->pmatch
= (regmatch_t
*)malloc((m
->g
->nsub
+ 1) *
287 sizeof (regmatch_t
));
288 if (m
->pmatch
== NULL
) {
292 for (i
= 1; i
<= m
->g
->nsub
; i
++)
293 m
->pmatch
[i
].rm_so
= m
->pmatch
[i
].rm_eo
= -1;
294 /* NB: FreeBSD has REG_BACKR, we do not */
295 if (!g
->backrefs
/* && !(m->eflags®_BACKR) */) {
297 dp
= dissect(m
, m
->coldp
, endp
, gf
, gl
);
299 if (g
->nplus
> 0 && m
->lastpos
== NULL
)
300 m
->lastpos
= malloc((g
->nplus
+1) *
301 sizeof (const char *));
302 if (g
->nplus
> 0 && m
->lastpos
== NULL
) {
307 NOTE("backref dissect");
308 dp
= backref(m
, m
->coldp
, endp
, gf
, gl
, (sopno
)0, 0);
313 /* uh-oh... we couldn't find a subexpression-level match */
314 assert(g
->backrefs
); /* must be back references doing it */
315 assert(g
->nplus
== 0 || m
->lastpos
!= NULL
);
317 if (dp
!= NULL
|| endp
<= m
->coldp
)
320 endp
= slow(m
, m
->coldp
, endp
-1, gf
, gl
);
323 /* try it on a shorter possibility */
325 for (i
= 1; i
<= m
->g
->nsub
; i
++) {
326 assert(m
->pmatch
[i
].rm_so
== -1);
327 assert(m
->pmatch
[i
].rm_eo
== -1);
330 NOTE("backoff dissect");
331 dp
= backref(m
, m
->coldp
, endp
, gf
, gl
, (sopno
)0, 0);
333 assert(dp
== NULL
|| dp
== endp
);
334 if (dp
!= NULL
) /* found a shorter one */
337 /* despite initial appearances, there is no match here */
339 /* recycle starting later */
340 start
= m
->coldp
+ XMBRTOWC(NULL
, m
->coldp
,
341 stop
- m
->coldp
, &m
->mbs
, 0);
342 assert(start
<= stop
);
345 /* fill in the details if requested */
347 pmatch
[0].rm_so
= m
->coldp
- m
->offp
;
348 pmatch
[0].rm_eo
= endp
- m
->offp
;
351 assert(m
->pmatch
!= NULL
);
352 for (i
= 1; i
< nmatch
; i
++)
354 pmatch
[i
] = m
->pmatch
[i
];
356 pmatch
[i
].rm_so
= -1;
357 pmatch
[i
].rm_eo
= -1;
361 if (m
->pmatch
!= NULL
)
362 free((char *)m
->pmatch
);
363 if (m
->lastpos
!= NULL
)
364 free((char *)m
->lastpos
);
370 * dissect - figure out what matched what, no back references
373 dissect(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
377 sopno ss
; /* start sop of current subRE */
378 sopno es
; /* end sop of current subRE */
379 const char *sp
; /* start of string matched by it */
380 const char *stp
; /* string matched by it cannot pass here */
381 const char *rest
; /* start of rest of string */
382 const char *tail
; /* string unmatched by rest of RE */
383 sopno ssub
; /* start sop of subsubRE */
384 sopno esub
; /* end sop of subsubRE */
385 const char *ssp
; /* start of string matched by subsubRE */
386 const char *sep
; /* end of string matched by subsubRE */
387 const char *oldssp
; /* previous ssp */
390 AT("diss", start
, stop
, startst
, stopst
);
392 for (ss
= startst
; ss
< stopst
; ss
= es
) {
393 /* identify end of subRE */
395 switch (OP(m
->g
->strip
[es
])) {
398 es
+= OPND(m
->g
->strip
[es
]);
401 while (OP(m
->g
->strip
[es
]) != O_CH
)
402 es
+= OPND(m
->g
->strip
[es
]);
407 /* figure out what it matched */
408 switch (OP(m
->g
->strip
[ss
])) {
413 sp
+= XMBRTOWC(NULL
, sp
, stop
- start
, &m
->mbs
, 0);
422 sp
+= XMBRTOWC(NULL
, sp
, stop
- start
, &m
->mbs
, 0);
428 /* cases where length of match is hard to find */
432 /* how long could this one be? */
433 rest
= slow(m
, sp
, stp
, ss
, es
);
434 assert(rest
!= NULL
); /* it did match */
435 /* could the rest match the rest? */
436 tail
= slow(m
, rest
, stop
, es
, stopst
);
439 /* no -- try a shorter match for this one */
441 assert(stp
>= sp
); /* it did work */
445 /* did innards match? */
446 if (slow(m
, sp
, rest
, ssub
, esub
) != NULL
) {
447 dp
= dissect(m
, sp
, rest
, ssub
, esub
);
459 /* how long could this one be? */
460 rest
= slow(m
, sp
, stp
, ss
, es
);
461 assert(rest
!= NULL
); /* it did match */
462 /* could the rest match the rest? */
463 tail
= slow(m
, rest
, stop
, es
, stopst
);
466 /* no -- try a shorter match for this one */
468 assert(stp
>= sp
); /* it did work */
474 for (;;) { /* find last match of innards */
475 sep
= slow(m
, ssp
, rest
, ssub
, esub
);
476 if (sep
== NULL
|| sep
== ssp
)
477 break; /* failed or matched null */
478 oldssp
= ssp
; /* on to next try */
482 /* last successful match */
486 assert(sep
== rest
); /* must exhaust substring */
487 assert(slow(m
, ssp
, sep
, ssub
, esub
) == rest
);
488 dp
= dissect(m
, ssp
, sep
, ssub
, esub
);
495 /* how long could this one be? */
496 rest
= slow(m
, sp
, stp
, ss
, es
);
497 assert(rest
!= NULL
); /* it did match */
498 /* could the rest match the rest? */
499 tail
= slow(m
, rest
, stop
, es
, stopst
);
502 /* no -- try a shorter match for this one */
504 assert(stp
>= sp
); /* it did work */
507 esub
= ss
+ OPND(m
->g
->strip
[ss
]) - 1;
508 assert(OP(m
->g
->strip
[esub
]) == OOR1
);
509 for (;;) { /* find first matching branch */
510 if (slow(m
, sp
, rest
, ssub
, esub
) == rest
)
511 break; /* it matched all of it */
512 /* that one missed, try next one */
513 assert(OP(m
->g
->strip
[esub
]) == OOR1
);
515 assert(OP(m
->g
->strip
[esub
]) == OOR2
);
517 esub
+= OPND(m
->g
->strip
[esub
]);
518 if (OP(m
->g
->strip
[esub
]) == OOR2
)
521 assert(OP(m
->g
->strip
[esub
]) == O_CH
);
523 dp
= dissect(m
, sp
, rest
, ssub
, esub
);
535 i
= OPND(m
->g
->strip
[ss
]);
536 assert(0 < i
&& i
<= m
->g
->nsub
);
537 m
->pmatch
[i
].rm_so
= sp
- m
->offp
;
540 i
= OPND(m
->g
->strip
[ss
]);
541 assert(0 < i
&& i
<= m
->g
->nsub
);
542 m
->pmatch
[i
].rm_eo
= sp
- m
->offp
;
555 * backref - figure out what matched what, figuring in back references
558 backref(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
559 sopno stopst
, sopno lev
, /* PLUS nesting level */
563 sopno ss
; /* start sop of current subRE */
564 const char *sp
; /* start of string matched by it */
565 sopno ssub
; /* start sop of subsubRE */
566 sopno esub
; /* end sop of subsubRE */
567 const char *ssp
; /* start of string matched by subsubRE */
576 AT("back", start
, stop
, startst
, stopst
);
579 /* get as far as we can with easy stuff */
581 for (ss
= startst
; !hard
&& ss
< stopst
; ss
++)
582 switch (OP(s
= m
->g
->strip
[ss
])) {
586 sp
+= XMBRTOWC(&wc
, sp
, stop
- sp
, &m
->mbs
, BADCHAR
);
593 sp
+= XMBRTOWC(&wc
, sp
, stop
- sp
, &m
->mbs
, BADCHAR
);
600 cs
= &m
->g
->sets
[OPND(s
)];
601 sp
+= XMBRTOWC(&wc
, sp
, stop
- sp
, &m
->mbs
, BADCHAR
);
602 if (wc
== BADCHAR
|| !CHIN(cs
, wc
))
606 if ((sp
== m
->beginp
&& !(m
->eflags
®_NOTBOL
)) ||
607 (sp
< m
->endp
&& *(sp
-1) == '\n' &&
608 (m
->g
->cflags
®_NEWLINE
))) {
613 if ((sp
== m
->endp
&& !(m
->eflags
®_NOTEOL
)) ||
614 (sp
< m
->endp
&& *sp
== '\n' &&
615 (m
->g
->cflags
®_NEWLINE
))) {
620 if (((sp
== m
->beginp
&& !(m
->eflags
®_NOTBOL
)) ||
621 (sp
< m
->endp
&& *(sp
-1) == '\n' &&
622 (m
->g
->cflags
®_NEWLINE
)) ||
623 (sp
> m
->beginp
&& !ISWORD(*(sp
-1)))) &&
624 (sp
< m
->endp
&& ISWORD(*sp
))) {
629 if (((sp
== m
->endp
&& !(m
->eflags
®_NOTEOL
)) ||
630 (sp
< m
->endp
&& *sp
== '\n' &&
631 (m
->g
->cflags
®_NEWLINE
)) ||
632 (sp
< m
->endp
&& !ISWORD(*sp
))) &&
633 (sp
> m
->beginp
&& ISWORD(*(sp
-1)))) {
639 case OOR1
: /* matches null but needs to skip */
643 assert(OP(s
) == OOR2
);
645 } while (OP(s
= m
->g
->strip
[ss
]) != O_CH
);
646 /* note that the ss++ gets us past the O_CH */
648 default: /* have to make a choice */
652 if (!hard
) { /* that was it! */
657 ss
--; /* adjust for the for's final increment */
660 AT("hard", sp
, stop
, ss
, stopst
);
663 case OBACK_
: /* the vilest depths */
665 assert(0 < i
&& i
<= m
->g
->nsub
);
666 if (m
->pmatch
[i
].rm_eo
== -1)
668 assert(m
->pmatch
[i
].rm_so
!= -1);
669 len
= m
->pmatch
[i
].rm_eo
- m
->pmatch
[i
].rm_so
;
670 if (len
== 0 && rec
++ > MAX_RECURSION
)
672 assert(stop
- m
->beginp
>= len
);
674 return (NULL
); /* not enough left to match */
675 ssp
= m
->offp
+ m
->pmatch
[i
].rm_so
;
676 if (memcmp(sp
, ssp
, len
) != 0)
678 while (m
->g
->strip
[ss
] != SOP(O_BACK
, i
))
680 return (backref(m
, sp
+len
, stop
, ss
+1, stopst
, lev
, rec
));
681 case OQUEST_
: /* to null or not */
682 dp
= backref(m
, sp
, stop
, ss
+1, stopst
, lev
, rec
);
684 return (dp
); /* not */
685 return (backref(m
, sp
, stop
, ss
+OPND(s
)+1, stopst
, lev
, rec
));
687 assert(m
->lastpos
!= NULL
);
688 assert(lev
+1 <= m
->g
->nplus
);
689 m
->lastpos
[lev
+1] = sp
;
690 return (backref(m
, sp
, stop
, ss
+1, stopst
, lev
+1, rec
));
692 if (sp
== m
->lastpos
[lev
]) /* last pass matched null */
693 return (backref(m
, sp
, stop
, ss
+1, stopst
, lev
-1, rec
));
694 /* try another pass */
695 m
->lastpos
[lev
] = sp
;
696 dp
= backref(m
, sp
, stop
, ss
-OPND(s
)+1, stopst
, lev
, rec
);
698 return (backref(m
, sp
, stop
, ss
+1, stopst
, lev
-1, rec
));
700 case OCH_
: /* find the right one, if any */
702 esub
= ss
+ OPND(s
) - 1;
703 assert(OP(m
->g
->strip
[esub
]) == OOR1
);
704 for (;;) { /* find first matching branch */
705 dp
= backref(m
, sp
, stop
, ssub
, esub
, lev
, rec
);
708 /* that one missed, try next one */
709 if (OP(m
->g
->strip
[esub
]) == O_CH
)
710 return (NULL
); /* there is none */
712 assert(OP(m
->g
->strip
[esub
]) == OOR2
);
714 esub
+= OPND(m
->g
->strip
[esub
]);
715 if (OP(m
->g
->strip
[esub
]) == OOR2
)
718 assert(OP(m
->g
->strip
[esub
]) == O_CH
);
722 case OLPAREN
: /* must undo assignment if rest fails */
724 assert(0 < i
&& i
<= m
->g
->nsub
);
725 offsave
= m
->pmatch
[i
].rm_so
;
726 m
->pmatch
[i
].rm_so
= sp
- m
->offp
;
727 dp
= backref(m
, sp
, stop
, ss
+1, stopst
, lev
, rec
);
730 m
->pmatch
[i
].rm_so
= offsave
;
732 case ORPAREN
: /* must undo assignment if rest fails */
734 assert(0 < i
&& i
<= m
->g
->nsub
);
735 offsave
= m
->pmatch
[i
].rm_eo
;
736 m
->pmatch
[i
].rm_eo
= sp
- m
->offp
;
737 dp
= backref(m
, sp
, stop
, ss
+1, stopst
, lev
, rec
);
740 m
->pmatch
[i
].rm_eo
= offsave
;
753 * fast - step through the string at top speed
756 fast(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
760 states fresh
= m
->fresh
;
762 const char *p
= start
;
764 wint_t lastc
; /* previous c */
767 const char *coldp
; /* last p after which no match was underway */
773 st
= step(m
->g
, startst
, stopst
, st
, NOTHING
, st
);
777 if (start
== m
->beginp
)
781 * XXX Wrong if the previous character was multi-byte.
782 * Newline never is (in encodings supported by FreeBSD),
783 * so this only breaks the ISWORD tests below.
785 c
= (uch
)*(start
- 1);
794 clen
= XMBRTOWC(&c
, p
, m
->endp
- p
, &m
->mbs
, BADCHAR
);
798 /* is there an EOL and/or BOL between lastc and c? */
801 if ((lastc
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
802 (lastc
== OUT
&& !(m
->eflags
®_NOTBOL
))) {
806 if ((c
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
807 (c
== OUT
&& !(m
->eflags
®_NOTEOL
))) {
808 flagch
= (flagch
== BOL
) ? BOLEOL
: EOL
;
813 st
= step(m
->g
, startst
, stopst
, st
,
818 /* how about a word boundary? */
819 if ((flagch
== BOL
|| (lastc
!= OUT
&& !ISWORD(lastc
))) &&
820 (c
!= OUT
&& ISWORD(c
))) {
823 if ((lastc
!= OUT
&& ISWORD(lastc
)) &&
824 (flagch
== EOL
|| (c
!= OUT
&& !ISWORD(c
)))) {
827 if (flagch
== BOW
|| flagch
== EOW
) {
828 st
= step(m
->g
, startst
, stopst
, st
, flagch
, st
);
833 if (ISSET(st
, stopst
) || p
== stop
|| clen
> stop
- p
)
834 break; /* NOTE BREAK OUT */
836 /* no, we must deal with this character */
840 st
= step(m
->g
, startst
, stopst
, tmp
, c
, st
);
842 assert(EQ(step(m
->g
, startst
, stopst
, st
, NOTHING
, st
), st
));
846 assert(coldp
!= NULL
);
848 if (ISSET(st
, stopst
))
849 return (p
+XMBRTOWC(NULL
, p
, stop
- p
, &m
->mbs
, 0));
855 * slow - step through the string more deliberately
858 slow(struct match
*m
, const char *start
, const char *stop
, sopno startst
,
862 states empty
= m
->empty
;
864 const char *p
= start
;
866 wint_t lastc
; /* previous c */
869 const char *matchp
; /* last p at which a match ended */
872 AT("slow", start
, stop
, startst
, stopst
);
875 SP("sstart", st
, *p
);
876 st
= step(m
->g
, startst
, stopst
, st
, NOTHING
, st
);
878 if (start
== m
->beginp
)
882 * XXX Wrong if the previous character was multi-byte.
883 * Newline never is (in encodings supported by FreeBSD),
884 * so this only breaks the ISWORD tests below.
886 c
= (uch
)*(start
- 1);
895 clen
= XMBRTOWC(&c
, p
, m
->endp
- p
, &m
->mbs
, BADCHAR
);
897 /* is there an EOL and/or BOL between lastc and c? */
900 if ((lastc
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
901 (lastc
== OUT
&& !(m
->eflags
®_NOTBOL
))) {
905 if ((c
== '\n' && m
->g
->cflags
®_NEWLINE
) ||
906 (c
== OUT
&& !(m
->eflags
®_NOTEOL
))) {
907 flagch
= (flagch
== BOL
) ? BOLEOL
: EOL
;
912 st
= step(m
->g
, startst
, stopst
, st
,
914 SP("sboleol", st
, c
);
917 /* how about a word boundary? */
918 if ((flagch
== BOL
|| (lastc
!= OUT
&& !ISWORD(lastc
))) &&
919 (c
!= OUT
&& ISWORD(c
))) {
922 if ((lastc
!= OUT
&& ISWORD(lastc
)) &&
923 (flagch
== EOL
|| (c
!= OUT
&& !ISWORD(c
)))) {
926 if (flagch
== BOW
|| flagch
== EOW
) {
927 st
= step(m
->g
, startst
, stopst
, st
, flagch
, st
);
928 SP("sboweow", st
, c
);
932 if (ISSET(st
, stopst
))
934 if (EQ(st
, empty
) || p
== stop
|| clen
> stop
- p
)
935 break; /* NOTE BREAK OUT */
937 /* no, we must deal with this character */
941 st
= step(m
->g
, startst
, stopst
, tmp
, c
, st
);
943 assert(EQ(step(m
->g
, startst
, stopst
, st
, NOTHING
, st
), st
));
952 * step - map set of states reachable before char to set reachable after
955 step(struct re_guts
*g
,
956 sopno start
, /* start state within strip */
957 sopno stop
, /* state after stop state within strip */
958 states bef
, /* states reachable before */
959 wint_t ch
, /* character or NONCHAR code */
960 states aft
) /* states already known reachable after */
965 onestate here
; /* note, macros know this name */
969 for (pc
= start
, INIT(here
, pc
); pc
!= stop
; pc
++, INC(here
)) {
973 assert(pc
== stop
-1);
976 /* only characters can match */
977 assert(!NONCHAR(ch
) || ch
!= OPND(s
));
982 if (ch
== BOL
|| ch
== BOLEOL
)
986 if (ch
== EOL
|| ch
== BOLEOL
)
1002 cs
= &g
->sets
[OPND(s
)];
1003 if (!NONCHAR(ch
) && CHIN(cs
, ch
))
1006 case OBACK_
: /* ignored here */
1010 case OPLUS_
: /* forward, this is just an empty */
1013 case O_PLUS
: /* both forward and back */
1015 i
= ISSETBACK(aft
, OPND(s
));
1016 BACK(aft
, aft
, OPND(s
));
1017 if (!i
&& ISSETBACK(aft
, OPND(s
))) {
1018 /* oho, must reconsider loop body */
1023 case OQUEST_
: /* two branches, both forward */
1025 FWD(aft
, aft
, OPND(s
));
1027 case O_QUEST
: /* just an empty */
1030 case OLPAREN
: /* not significant here */
1034 case OCH_
: /* mark the first two branches */
1036 assert(OP(g
->strip
[pc
+OPND(s
)]) == OOR2
);
1037 FWD(aft
, aft
, OPND(s
));
1039 case OOR1
: /* done a branch, find the O_CH */
1040 if (ISSTATEIN(aft
, here
)) {
1042 OP(s
= g
->strip
[pc
+look
]) != O_CH
;
1044 assert(OP(s
) == OOR2
);
1045 FWD(aft
, aft
, look
+ 1);
1048 case OOR2
: /* propagate OCH_'s marking */
1050 if (OP(g
->strip
[pc
+OPND(s
)]) != O_CH
) {
1051 assert(OP(g
->strip
[pc
+OPND(s
)]) == OOR2
);
1052 FWD(aft
, aft
, OPND(s
));
1055 case O_CH
: /* just empty */
1058 default: /* ooooops... */
1069 * print - print a set of states
1072 print(struct match
*m
, const char *caption
, states st
, int ch
, FILE *d
)
1074 struct re_guts
*g
= m
->g
;
1078 if (!(m
->eflags
®_TRACE
))
1081 (void) fprintf(d
, "%s", caption
);
1083 (void) fprintf(d
, " %s", pchar(ch
));
1084 for (i
= 0; i
< g
->nstates
; i
++)
1086 (void) fprintf(d
, "%s%d", (first
) ? "\t" : ", ", i
);
1089 (void) fprintf(d
, "\n");
1093 * at - print current situation
1096 at(struct match
*m
, const char *title
, const char *start
, const char *stop
,
1097 sopno startst
, sopno stopst
)
1099 if (!(m
->eflags
®_TRACE
))
1102 (void) printf("%s %s-", title
, pchar(*start
));
1103 (void) printf("%s ", pchar(*stop
));
1104 (void) printf("%ld-%ld\n", (long)startst
, (long)stopst
);
1108 #define PCHARDONE /* never again */
1110 * pchar - make a character printable
1112 * Is this identical to regchar() over in debug.c? Well, yes. But a
1113 * duplicate here avoids having a debugging-capable regexec.o tied to
1114 * a matching debug.o, and this is convenient. It all disappears in
1115 * the non-debug compilation anyway, so it doesn't matter much.
1120 static char pbuf
[10];
1122 if (isprint((uch
)ch
) || ch
== ' ')
1123 (void) sprintf(pbuf
, "%c", ch
);
1125 (void) sprintf(pbuf
, "\\%o", ch
);