注: 5.004_04においてREGALIGNがdefineされてないときの動作を元にしている
実行 regexec
/* Current curly descriptor */
typedef struct curcur CURCUR;
struct curcur {
int parenfloor; /* how far back to strip paren data */
int cur; マッチした走査のインスタンスがいくつあるか
int min; マッチングのための走査回数の最小値
int max; マッチングのための走査回数の最大値
int minmod; /* whether to work our way up or down */
char * scan; マッチングを試すもの
char * next; /* what has to match after it */
char * lastloc; 今回の操作でマッチングがどこでスタートしたか
CURCUR * oldcc; /* current curly before we started this one */
};
regmatchで再帰的な呼び出しが発生したときに、必要な情報を
pushするのに使用する。
static CURCUR* regcc;
保存すべき部分正規表現をプッシュする。
static CHECKPOINT
regcppush(parenfloor)
I32 parenfloor;
regexec.c(95) : regcppush(parenfloor)
static CHECKPOINT
regcppush(parenfloor)
I32 parenfloor;
{
int retval = savestack_ix;
int i = (regsize - parenfloor) * 3;
int p;
SSCHECK(i + 5);
for (p = regsize; p > parenfloor; p--) {
SSPUSHPTR(regendp[p]);
SSPUSHPTR(regstartp[p]);
SSPUSHINT(p);
}
SSPUSHINT(regsize);
SSPUSHINT(*reglastparen);
SSPUSHPTR(reginput);
SSPUSHINT(i + 3);
SSPUSHINT(SAVEt_REGCONTEXT);
return retval;
}
以前にプッシュした部分正規表現を復帰する。
static char *
regcppop()
regexec.c(117) : regcppop()
static char *
regcppop()
{
I32 i = SSPOPINT;
U32 paren = 0;
char *input;
char *tmps;
assert(i == SAVEt_REGCONTEXT);
i = SSPOPINT;
input = (char *) SSPOPPTR;
*reglastparen = SSPOPINT;
regsize = SSPOPINT;
for (i -= 3; i > 0; i -= 3) {
paren = (U32)SSPOPINT;
regstartp[paren] = (char *) SSPOPPTR;
tmps = (char*)SSPOPPTR;
if (paren <= *reglastparen)
regendp[paren] = tmps;
}
for (paren = *reglastparen + 1; paren <= regnpar; paren++) {
if (paren > regsize)
regstartp[paren] = Nullch;
regendp[paren] = Nullch;
}
return input;
}
WHILEMでマッチが成功した後で、その成功に至る過程で失敗したマッチによって
上書きされてしまっているparen matchesをリストアすることが必要である。
これを、regstartp[i]をそれが変更されていない場合であっても常に
リストアすることで行っている。OPENがregendp[]を修正するために
変更されたならば、以下の例にある'== endp' というテストはマッチするように
変更した方が良い。
0 > length [ "foobar" =‾ / ( (foo) | (bar) )* /x ]->[1]
static void
regcppartblow(base)
I32 base;
regexec.c(152) : regcppartblow(base)
scope.h(35): #define SSPOPINT (savestack[--savestack_ix].any_i32)
マッチしている部分正規表現の復帰
static void
regcppartblow(base)
I32 base;
{
I32 i = SSPOPINT;
U32 paren;
char *startp;
char *endp;
assert(i == SAVEt_REGCONTEXT);
i = SSPOPINT;
/* input, lastparen, size */
SSPOPPTR; SSPOPINT; SSPOPINT;
for (i -= 3; i > 0; i -= 3) {
paren = (U32)SSPOPINT;
startp = (char *) SSPOPPTR;
endp = (char *) SSPOPPTR;
if (paren <= *reglastparen && regendp[paren] == endp)
regstartp[paren] = startp;
}
assert(savestack_ix == base);
}
/*
- pregexec - match a regexp against a string
*/
I32
pregexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
register regexp *prog;
char *stringarg;
register char *strend; 文字列の終端にあるナル文字へのポインター
char *strbeg; 文字列の本当の先頭
I32 minend; /* end of match must be at least minend after stringarg */
stringargの後ろにある、最小のminendにマッチすべきものの終端
SV *screamer;
I32 safebase; /* no need to remember string in subbase */
・regprevを設定
・regpregcomにprog->precompを設定
・prog->programが正しいコンパイル済み正規表現を指しているか検査
・regnpar に prog->nparensを設定
・regtainted に FALSEを設定;
・
・/* If there is a "must appear" string, look for it. */
“なければいけない”文字列があれば、それを探す
・/* Simplest case: anchored match need be tried only once. */
単純な場合: 一度だけ試す必要があるアンカー付きの(anchored)マッチ
/* [unless only anchor is BOL and multiline is set] */
[アンカーがBOLで複数行モードでない場合]
・/* Messy cases: unanchored match. */
厄介なケース: アンカーがないマッチ
・if (c = prog->regstclass) {
else
/*
- regtry - 特定の場所でマッチングを試みる
*/
static I32 /* 0 失敗, 1 成功 */
regtry(prog, startpos)
regexp *prog; コンパイル済み正規表現
char *startpos; マッチ対象の位置
・マッチングのための大域変数などの設定
reginput = startpos; 入力位置
regstartp = prog->startp; 部分正規表現の開始位置の配列
regendp = prog->endp; 部分正規表現の終了位置の配列
reglastparen = &prog->lastparen; 最後に登場したカッコの位置
prog-&>lastparen = 0;
regsize = 0;
sp = prog->startp;
ep = prog->endp;
・prog->nparnが0でなければその値に応じて部分正規表現のための格納領域を
NULLでクリアする
regmatch(prog->program + 1)がマッチに成功し、かつ reginput &>= regtill なら
prog->startp[0] = startpos; マッチした部分の先頭
prog->endp[0] = reginput; マッチした部分の終端
1を戻り値としてリターン
else
0を戻り値としてリターン
戻り値:
マッチしなかったら0、マッチしたら1
/*
- regmatch - マッチングのメインルーチン
*
* Conceptually the strategy is simple: check to see whether the current
* node matches, call self recursively to see whether the rest matches,
* and then act accordingly. In practice we make some effort to avoid
* recursion, in particular by going through "ordinary" nodes (that don't
* need to know whether the rest of the match failed) by a loop instead of
* by recursion.
基本的な戦略は単純なものである: カレントのノードがマッチするかどうか
を確かめてから、残りの部分がマッチするかどうかを自分自身を再帰的に呼
び出し、その後も状況に応じて同じように行う。実際には多少の手間を掛け
て再帰を行わないようにしていて、“普通の”(ordinary)ノード(後続のマ
ッチが失敗するかどうかを知る必要のないもの)に対しては再帰ではなくル
ープを使って通り過ぎる。
*/
/* [lwall] I've hoisted the register declarations to the outer block in order to
* maybe save a little bit of pushing and popping on the stack. It also takes
* advantage of machines that use a register save mask on subroutine entry.
[lwall]
スタックにプッシュしたりスタックからポップしたりするのを
節約するために、 レジスター宣言を外側のブロックに移した。
これは、サブルーチンのエントリでregister save maskを使うような
マシンでも効果がある。
*/
static I32 /* 0 失敗, 1 成功 */
regmatch(prog)
char *prog; コンパイル済み正規表現のカレントポイント
ローカル変数
register char *scan; カレントノード
char *next; 次のノード
register I32 nextchar;
register I32 n; /* no or next */
register I32 ln; /* len or last */
register char *s; /* operand or save */
register char *locinput = reginput; 入力位置
register I32 c1, c2; 大小文字無視の検索
int minmod = 0;
・nextchar = UCHARAT(locinput); 検索対象の文字を取り出す
・スキャンポイントにprogを設定 (scan = prog)
・スキャンポイント!=0の間繰り返し
スキャンポイントの次のノードのアドレスをregnext(scan)で取得し、nextにセット
カレントノードのオペコードによってディスパッチ
・EXACTFL, ALNUML, NALNUML, SPACEL, NSPCAEL, REFFLの場合にはregtaintをTRUEにする
BOL
if (locinput == regbol
? regprev == '¥n'
: ((nextchar || locinput < regeol) && locinput[-1] == '¥n') )
locinput == regbolかつregprevが'¥n'であるか、
locinput!=regbolかつ
((nextchar || locinput < regeol) && locinput[-1] == '¥n') )
であれば、scanを更新してループを継続する。
上記の条件を満たさなかった場合には0を戻り値として関数から脱出する。
MBOL
locinput == regbolかつregprevが'¥n'であるか、
locinput!=regbolかつ
((nextchar || locinput < regeol) && locinput[-1] == '¥n') )
であれば、scanを更新してループを継続する。
上記の条件を満たさなかった場合には0を戻り値として関数から脱出する。
SBOL
if (locinput == regbol && regprev == '¥n')
locinput==regbolかつregprev=='¥n'であれば、scanを更新して
ループを継続。
上記の条件を満たさなかった場合には0を戻り値として関数から脱出する。
GPOS
locinput==regbolであれば、scanを更新してループを継続。
上記の条件を満たさなかった場合には0を戻り値として関数から脱出する。
EOL
マルチラインモードであればMEOLへ、そうでなければSEOLへ移行する。
MEOL
if ((nextchar || locinput < regeol) && nextchar != '¥n')
sayNO;
SEOL
if ((nextchar || locinput < regeol) && nextchar != '¥n')
sayNO;
if (regeol - locinput > 1)
sayNO;
SANY
if (!nextchar && locinput >= regeol)
sayNO;
if (KANJI_MODE && iskanji(nextchar) && locinput[1]) ++locinput;
nextchar = UCHARAT(++locinput);
ANY
if (!nextchar && locinput >= regeol || nextchar == '¥n')
sayNO;
if (KANJI_MODE && iskanji(nextchar) && locinput[1]) ++locinput;
nextchar = UCHARAT(++locinput);
EXACT
+→ lnへ
+-------+-----+-----+-------+-------+-------+-----+
| EXACT |next | len | 対象文字列 | ¥0 |
+-------+-----+-----+-------+-------+-------+-----+
↑処理開始前の scan
locinput += ln;
nextchar = UCHARAT(locinput);
EXACTFL
EXACTF
+→ lnへ
+---------+-----+-----+-------+-------+-------+-----+
| EXACTFL | next| len| 対象文字列 | ¥0 |
+---------+-----+-----+-------+-------+-------+-----+
↑処理開始前の scan
+→ lnへ
+--------+-----+-----+-------+-------+-------+-----+
| EXACTF | next | len | 対象文字列 | ¥0 |
+--------+-----+-----+-------+-------+-------+-----+
↑処理開始前の scan
locinput += ln;
nextchar = UCHARAT(locinput);
ANYOF
s = OPERAND(scan); ここで取り出すオペランドはチェック対象のキャラクタクラス
if (nextchar < 0)
nextchar = UCHARAT(locinput);
if (KANJI_MODE && !(*s & ANYOF_LITERAL)
&& iskanji(nextchar) && locinput[1]) {
locinput++;
nextchar = (nextchar << 8) + UCHARAT(locinput);
}
if (!reginclass(s, nextchar))
sayNO;
if (!nextchar && locinput >= regeol)
sayNO;
nextchar = UCHARAT(++locinput);
ALNUML
regtainted = TRUE;して、ALNUMの処理へ移行
ALNUM
if (!nextchar)
sayNO;
if (!(OP(scan) == ALNUM
? isALNUM(nextchar) : isALNUM_LC(nextchar)))
sayNO;
if (KANJI_MODE && iskanji(nextchar) && locinput[1])
++locinput;
nextchar = UCHARAT(++locinput);
break;
NALNUML
regtainted = TRUE;して、NALNUMの処理へ移行
NALNUM
if (!nextchar && locinput >= regeol)
sayNO;
if (OP(scan) == NALNUM
? isALNUM(nextchar) : isALNUM_LC(nextchar))
sayNO;
if (KANJI_MODE && iskanji(nextchar) && locinput[1])
++locinput;
nextchar = UCHARAT(++locinput);
BOUNDL
NBOUNDL
regtainted = TRUE;して、BOUND/NBOUNDの処理へ移行
BOUND
NBOUND
ln = (locinput != regbol) ? UCHARAT(locinput - 1) : regprev;
if (OP(scan) == BOUND || OP(scan) == NBOUND) {
ln = isALNUM(ln);
n = isALNUM(nextchar);
}
else {
ln = isALNUM_LC(ln);
n = isALNUM_LC(nextchar);
}
if (((!ln) == (!n)) == (OP(scan) == BOUND || OP(scan) == BOUNDL))
sayNO;
SPACEL
regtainted = TRUE;して、SPACEの処理へ移行
SPACE
if (!nextchar && locinput >= regeol)
sayNO;
nextcharがなく(空)、locinputがregeol以上であればマッチ失敗
if (!(OP(scan) == SPACE
? isSPACE(nextchar) : isSPACE_LC(nextchar)))
sayNO;
OP(scan)がSPACEのとき
isSPACE(nextchar)が偽ならマッチ失敗
OP(scan)がSPACEでないとき(SPACELのとき)
isSPACE_LC(nextchar)が偽ならマッチ失敗
nextchar = UCHARAT(++locinput);
nextcharにUCHARAT(++locinput)をセット
NSPACEL
regtainted = TRUE;して、NSPACEの処理へ移行
NSPACE
if (!nextchar)
sayNO;
nextcharがなければマッチ失敗
if (OP(scan) == SPACE
? isSPACE(nextchar) : isSPACE_LC(nextchar))
sayNO;
OP(scan)がSPACEのとき
isSPACE(nextchar)が真ならマッチ失敗
OP(scan)がSPACEでないとき(SPACELのとき)
isSPACE_LC(nextchar)が真ならマッチ失敗
if (KANJI_MODE && iskanji(nextchar) && locinput[1])
++locinput;
KANJI_MODEであって、iskanji(nextchar)が真、locinput[1]が存在していれば
locinputを一つインクリメントする
nextchar = UCHARAT(++locinput);
nextcharにUCHARAT(++locinput)をセット
DIGIT
if (!isDIGIT(nextchar))
sayNO;
isDIGIT(nextchar)でなければマッチ失敗
nextchar = UCHARAT(++locinput);
nextcharにUCHARAT(++locinput)をセット
NDIGIT
if (!nextchar && locinput >= regeol)
sayNO;
nextcharが存在しておらず、locinputがregeol以上ならマッチ失敗
if (isDIGIT(nextchar))
sayNO;
isDIGIT(nextchar)であればマッチ失敗
if (KANJI_MODE && iskanji(nextchar) && locinput[1])
++locinput;
KANJI_MODEがonのとき、
nextcharにマルチバイト文字のリードバイト入っていたら
locinputを一つインクリメント
nextchar = UCHARAT(++locinput);
nextcharにUCHARAT(++locinput)をセット
REFFL
regtainted = TRUE; して、REF/REFFの処理へ移行
REF
REFF
n = ARG1(scan); /* which paren pair */
部分正規表現を指定する数値を取り出す
s = regstartp[n];
if (!s)
sayNO;
if (!regendp[n])
sayNO;
該当する部分正規表現がなければマッチ失敗
if (s == regendp[n])
break;
指定された部分正規表現の長さが0なら、scanを更新してループを継続
/* Inline the first character, for speed. */
if (UCHARAT(s) != nextchar &&
(OP(scan) == REF ||
(UCHARAT(s) != ((OP(scan) == REFF
? fold : fold_locale)[nextchar]))))
sayNO;
ln = regendp[n] - s;
if (locinput + ln > regeol)
sayNO;
if (ln > 1 && (OP(scan) == REF
? memNE(s, locinput, ln)
: (OP(scan) == REFF
? ibcmp(s, locinput, ln)
: ibcmp_locale(s, locinput, ln))))
sayNO;
locinput += ln;
nextchar = UCHARAT(locinput);
NOTHING
scanを更新してループを継続
BACK
scanを更新してループを継続
OPEN
n = ARG1(scan); /* which paren pair */
regstartp[n] = locinput;
if (n > regsize)
regsize = n;
CLOSE
n = ARG1(scan); /* which paren pair */
regendp[n] = locinput;
if (n > *reglastparen)
*reglastparen = n;
CURLYX
+----------+
| regcc ───→ +----------+
+----------+ | |
+----------+
| oldcc ───→ +----------+
+----------+ | |
+----------+
| oldcc ───→ ...
+----------+
CURCUR cc;
CHECKPOINT cp = savestack_ix;
cc.oldcc = regcc; ccを保存
regcc = &cc;
cc.parenfloor = *reglastparen; /* ()を何個まで使っているか
cc.cur = -1;
cc.min = ARG1(scan);
cc.max = ARG2(scan);
cc.scan = NEXTOPER(scan) + 4;
cc.next = next;
cc.minmod = minmod;
cc.lastloc = 0;
reginput = locinput;
n = regmatch(PREVOPER(next)); /* start on the WHILEM */
PREVOPER(next)
↓
+-------+-------+-------+-------+-------+-------+-------+---
| CURYX | next |HI(min)|LO(min)|HI(max)|LO(max)| XXXXX
+-------+-------+-------+-------+-------+-------+-------+---
↑ ARG1(scan) ↑ ARG2(scan)
regcpblow(cp); 実体は scope.cにある leave_scope()
CHECKPOINT cp = savestack_ix; に対応か?
regcc = cc.oldcc; ccを復帰
saySAME(n); nを戻り値として返す
WHILEM
これは理解するのが本当に難しい。なぜなら、マッチさせようとしたものを
マッチした後で、我々は正規表現の残りの部分が確実にマッチするようにし
なければならないからだ。また、そのために深い再帰を行って解析木をバッ
クアップしておく必要がある。さらにマッチが失敗した場合には、backing
offした後で再挑戦する可能性のある親のカレントステートをリセットする
必要がある。
CHECKPOINT cp;
CURCUR* cc = regcc;
n = cc->cur + 1; /* how many we know we matched */
reginput = locinput; 現時点での入力ポインターをreginputにセット
/* If degenerate scan matches "", assume scan done. */
if (locinput == cc->lastloc && n >= cc->min) {
regcc = cc->oldcc;
ln = regcc->cur;
if (regmatch(cc->next))
sayYES;
regcc->cur = ln;
regcc = cc;
sayNO;
}
/* First just match a string of min scans. */
if (n < cc->min) { #必要最低限の回数の繰り返しがあるか
cc->cur = n;
cc->lastloc = locinput;
if (regmatch(cc->scan))
sayYES;
cc->cur = n - 1;
sayNO;
}
/* Prefer next over scan for minimal matching. */
if (cc->minmod) { # minimal マッチングのためのスキャン
regcc = cc->oldcc;
ln = regcc->cur;
cp = regcppush(cc->parenfloor);
if (regmatch(cc->next)) {
regcppartblow(cp);
sayYES; /* All done. */
}
regcppop();
regcc->cur = ln;
regcc = cc;
if (n >= cc->max) /* 最大値を越えたか? */
sayNO;
/* Try scanning more and see if it helps. */
reginput = locinput;
cc->cur = n;
cc->lastloc = locinput;
cp = regcppush(cc->parenfloor);
if (regmatch(cc->scan)) {
regcppartblow(cp);
sayYES;
}
regcppop();
cc->cur = n - 1;
sayNO;
}
/* Prefer scan over next for maximal matching. */
# maximal matchingのための処理
if (n < cc->max) { もっとマッチできるか?
cp = regcppush(cc->parenfloor);
cc->cur = n;
cc->lastloc = locinput;
if (regmatch(cc->scan)) {
regcppartblow(cp);
sayYES;
}
regcppop(); /* Restore some previous $&<digit&>s? */
reginput = locinput;
}
/* Failed deeper matches of scan, so see if this one works. */
regcc = cc->oldcc;
ln = regcc->cur;
if (regmatch(cc->next))
sayYES;
regcc->cur = ln;
regcc = cc;
cc->cur = n - 1;
sayNO;
BRANCH
if (OP(next) != BRANCH) /* No choice. */
next = NEXTOPER(scan);/* Avoid recursion. */
“次の”ノードがBRANCHでなければ、nextに NEXTOPER(scan)を
セットしてループをやり直す(再帰の深さを抑えるため)。
#ループの末尾に scan = nextがあるので、辻褄はあう
処理開始時のscan
↓ ┌─────────────────────┐
+--------+--------+--------+-------+-------+-------+-------+----
| BRANCH |“次の”ノードへ |...... |
+--------+--------+--------+-------+-------+-------+-------+----
↑ ↑
NEXTOPER(scan) OP(next)
else {
int lastparen = *reglastparen;
do {
reginput = locinput;
if (regmatch(NEXTOPER(scan)))
sayYES;
regmatch(NEXTOPER(scan))が成功したら、マッチ成功を戻り値として
関数から抜ける。
for (n = *reglastparen; n > lastparen; n--)
regendp[n] = 0;
*reglastparen = n;
scan = regnext(scan);
} while (scan != NULL && OP(scan) == BRANCH);
BRANCHノードのリンクのある限り
sayNO;
BRANCHノードのリンクを最後までたどってもマッチするものが
なかったら、失敗。
/* NOTREACHED */
}
break;
MINMOD
minmodに1を設定(non-greedyモードを有効にする)
CURLY
ln = ARG1(scan); マッチに必要な最小の繰り返し回数
n = ARG2(scan); マッチに必要な最大の繰り返し回数
scan = NEXTOPER(scan) + 4; スキャンポインターの更新
処理開始時のscan
↓
+------+-------+-------+-------+-------+-------+-------+----
| CURY | next |HI(min)|LO(min)|HI(max)|LO(max)| XXXXX
+------+-------+-------+-------+-------+-------+-------+----
↑ ↑
ln n
↑更新後のscan
repeatの処理へ移行
STAR
ln = 0; 繰り返しの最小回数
n = 32767; 繰り返しの最大回数
scan = NEXTOPER(scan); スキャンポインターの更新
処理開始時のscan
↓
+------+-----+-------+-------
| STAR | next| 繰り返しの対象
+------+-----+-------+-------
↑更新後のscan
repeat処理へ移行
PLUS
ln = 1; 繰り返しの最小回数
n = 32767; 繰り返しの最大回数
scan = NEXTOPER(scan);
処理開始時のscan
↓
+------+-----+-----+---------+
| PLUS | next| 繰り返しの対象|
+------+-----+-----+---------+
↑更新後のscan
repeat処理:
SUCCEED
END
reginput = locinput; /* put where regtry can find it */
1を戻り値としてリターンする
IFMATCH
reginput = locinput;
scan = NEXTOPER(scan);
if (!regmatch(scan))
sayNO;
スキャンポイントをNEXTOPER(scan)として、regmatch(scan)を実行。
その戻り値がFALSEであれば、0を戻り値としてreturn。
TRUEなら、scanを更新してループを継続。
scan ┌─→ “次の”ノードへ ─┐regmatch(scan)がTRUEのとき
↓ │ ↓
+---------+-----+-----+-----+-----+-----+---
| IFMATCH | next| IFMATCHの対象 |
+---------+-----+-----+-----+-----+-----+---
↑ NEXTOPER(scan)後のscan
UNLESSM
reginput = locinput;
scan = NEXTOPER(scan);
if (regmatch(scan))
sayNO;
スキャンポイントをNEXTOPER(scan)として、regmatch(scan)を実行。
その戻り値がTRUEであれば、0を戻り値としてreturn。
FALSEなら、scanを更新してループを継続。
scan ┌─→ “次の”ノードへ ─┐regmatch(scan)がFALSEのとき
↓ │ ↓
+---------+-----+-----+-----+-----+-----+---
| UNLESSM | next| UNLESSMの対象 |
+---------+-----+-----+-----+-----+-----+---
↑ NEXTOPER(scan)後のscan
その他
Fatal Error
戻り値:
マッチしなかったら0、マッチしたら1
/*
- regrepeat - 単純な何かに繰り返しマッチし、どのくらいマッチしたかを報告する
*/
このルーチンは現在、長さが1であるものに対してのみマッチすることを
仮定している。これは以前は真であったが、現在ではキャラクター毎に
countを増やすのではなく、scan - reginputがcountであると仮定している。
static I32
regrepeat(p, max)
char *p; 検索に用いるノードのアドレス
I32 max; 繰り返しの最大数 (32767で制限なし)
register char *scan; スキャンポイント
register char *opnd; 検索に用いるノードのオペランド(のアドレス)
register I32 c; スキャンポイントから取りだしたキャラクター
register char *loceol = regeol; スキャンの終端
char *oldscan; ANYOFでスキャンポイントの調整のために使用
・sacn ← reginput (検索対象へのポインター)
・maxが32767でなく、かつ、max < regeol - scanであれば
loceol = scan + max; (スキャンの終端を変更)
・opnd ← pの指すノードのオペランド(EXACT*, ANYOFで使用)
・pの指すノードのオペコードに応じて処理を行う
EXACTFL, ALNUML, NALNUML, SPACEL, NSPCAELの場合にはregtaintをTRUEにする
ANY:
*scanが'¥n'となるか、loceolまでscanをインクリメントする。
(KANJI_MODEのとき、二バイト文字を考慮する)
scan
↓ (loceol)
+---+---+---+---+---+---+---+
| | | | |¥n | | |
+---+---+---+---+---+---+---+
↑
ここまで進める
case SANY:
loceolまでscanを進める
case EXACT:
文字列の長さは1
+-------+-----+-----+--------+----+
| EXACT | next| 1 |対象文字| ¥0 |
+-------+-----+-----+--------+----+
↑ ↑
opnd 検索対象文字c
*opndから文字 cを取りだし、同時にopndをインクリメント。
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
cと違う文字が見つかるまで scan をインクリメント
(ただし、loceolを越えることはない)
case EXACTF:
文字列の長さは1
+--------+-----+-----+---------+----------+----+-----+
| EXACTF | next| 1 |対象文字 | ¥0 |
+--------+-----+-----+---------+----------+----+-----+
↑ ↑
opnd 検索対象文字c
*opndから文字 cを取りだし、同時にopndをインクリメント。
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
(UCHARAT(scan) == c || UCHARAT(scan) == fold[c]))が成り立たなくなるまで
scan をインクリメント(ただし、loceolを越えることはない)
case EXACTFL: 文字列の長さは1
regtainted = TRUE;
*opndから文字 cを取りだし、同時にopndをインクリメント。
文字列の長さは1
+---------+-----+-----+---------+----+----+-----+
| EXACTFL |next | 1 |対象文字 | ¥0 |
+---------+-----+-----+---------+----+----+-----+
↑ ↑
opnd 検索対象文字c
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
(UCHARAT(scan) == c || UCHARAT(scan) == fold_locale[c]))が成り立たなくなるまで
scan をインクリメント(ただし、loceolを越えることはない)
case ANYOF:
opndの指しているクラスに属さないキャラクター cが見つかるか、
scanがloceolより小さい間、
scanをインクリメントする(二バイト文字を考慮。下に示すコード片を参照)。
if (KANJI_MODE && !(*opnd & ANYOF_LITERAL)
&& iskanji(c) && scan < loceol) {
scan++;
c = (c << 8) + UCHARAT(scan);
}
コンパイル済み正規表現
opnd
↓
+-------+-----+-----+-------+------+------+------+------+
| ANYOF |next | flag| bit vectorへのポインター |
+-------+-----+-----+-------+------+------+------+------+
入力文字列
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
reginclass(opnd, c)がFALSEになるまで
scan をインクリメント(ただし、loceolを越えることはない)
注: reginclass(opnd, c)は、キャラクター c がクラスに属するかどうかを判定する。
case ALNUM:
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
!isALNUM(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
case ALNUML:
regtainted = TRUE;
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
!isALNUM_LC(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
case NALNUM:
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
isALNUM(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
・インクリメントの際、KANJI_MODEが真であれば二バイト文字を考慮する
case NALNUML:
regtainted = TRUE;
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
isALNUM_LC(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
・インクリメントの際、KANJI_MODEが真であれば二バイト文字を考慮しない(バグ?)
case SPACE:
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
!isSPACE(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
case SPACEL:
regtainted = TRUE;
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
!isSPACE_LC(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
case NSPACE:
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
isSPACE(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
・インクリメントの際、KANJI_MODEが真であれば二バイト文字を考慮する
break;
case NSPACEL:
regtainted = TRUE;
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
isSPACE_LC(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
・インクリメントの際、KANJI_MODEが真であれば二バイト文字を考慮しない(バグ?)
case DIGIT:
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
!isDIGIT(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
case NDIGIT:
scan
↓
+---+---+---+---+---+---+---+
| | | | | | | |
+---+---+---+---+---+---+---+
↑
!isDIGIT(*scan)となる場所まで scan をインクリメント(ただし、loceolを越えることはない)
・インクリメントの際、KANJI_MODEが真であれば二バイト文字を考慮する
上記のもの以外(長さ0の何かに対して呼び出された)
なにもしない
戻り値を計算(scan - reginput)
戻り値: 繰り返しの回数(scan - reginput)
reginputを更新(reginput ← scan)
/*
- regclass - あるキャラクターがあるキャラクタークラスに属しているか判定する
*/
static bool
reginclass(p, c)
register char *p; ANYOFノードの引数へのポインター
register I32 c; 検査対象のキャラクター
p
↓
+-------+-----+-----+-------+------+------+------+------+
| ANYOF | next| flag| bit vectorへのポインター |
+-------+-----+-----+-------+------+------+------+------+
・キャラクター cに対応するビットが、pが指すビットベクターでonかoffかを検査。
c &= 0xFFFF;
if (0x8000 <= c)
c -= 0x8000 - 0x100;
if (bitvec[c >> 3] & (1 << (c & 7)))
match = TRUE;
・さらにflagの設定にしたがってマッチしたかどうかを判定
戻り値:
cが指定のクラスにマッチしていればTRUE、していなければFALSE
/*
- regnext - あるノードの外への“next”ポインターを取り出す
*
[注意: REGALIGNが定義されているとき、処理速度を稼ぐために
この関数をバイパスしている箇所がregmatch()に二つ存在している。]
*/
char *
regnext(p)
register char *p;