Not only is the Internet dead, it's starting to smell really bad.:2021年05月17日分

2021/05/17(Mon)

[オレオレN6] わからない俺は雰囲気でregex(3)のコードを弄っている(その2)

頭が悪いので(このチラシの裏の初期のタイトル、Keep It Simple, i'm Stupidを思い出せ)BM法という字面だけでBL同人誌とPM法の掛け算かなと脳内で解釈されるのだが、このカップリングはアリですかね想定読者層であるシティポップ好きのゆるふわカメラ女子さん(脳内にしか存在しない存在)。

いまのHenry Spencer改造版multibyte regexではBM法はシングルバイトなlocaleとマルチバイトの先頭が自明であるUTF-8 localeでしか有効になってない、まぁそらそうか。 まぁいつも思うけどUTF-8はほんとよくできてるよ、文字集合としてのUnicodeはゴミだけどな!やっぱり文字集合はISO2022かつ符号化手法だけUTF-8な文字コードが人類には必要なのではないか、ちゃんと薬は飲んだか!

後ろに戻ってマルチバイトの途中でマッチしてないかはチェックできないことも無いだろうけど最悪先頭まで戻るし、そもそも可変翼と共に大空を翔る男のロマンであるstateful encodingだと使えんわなこれ。 でもすでに別件で検索開始位置を探すstepbackという関数が増えてて、そこで同じようなことやってるのでja_JP.ISO-2022-JP localeなんかでは動かんコードであるのは確定なのだから別にいいんじゃねという気にもなる。 そもそもja_JP.ISO-2022-JP localeなんて実装すること自体がドダイYS無理なのである。

一点気づいたのがなぜかN HEADでは非UTF-8なmultibyte locaeでも有効になってるのだよな、たとえばEUC-JPやShift_JISなテキストファイルをsed(1)なんかで置換するとぶっ壊れる可能性がある、ご愁傷さまです。 まぁそもそも今時EUC-JPやShift_JISなんか使わん時代だしそもそも自前の正規表現エンジン抱え込んでるLLでテキスト処理するだろうし、そもそもNならlogin:でたら満足して電源落とすから実害はないな。

#ifdef notyet
	/*
	 * It's not generally safe to do a ``char'' substring search on
	 * multibyte character strings, but it's safe for at least
	 * UTF-8 (see RFC 3629).
	 */
	if (MB_CUR_MAX > 1 &&
	    strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0)
		return;
#endif

ここFのコード直接rune(3)触りに行ってて、ここの実装がFとNで違うから談話室滝川先生が理解を諦めた感じか、ちゃんと読めばこれだけの差分なんですけどね。

$ diff -upN regcomp.c.orig regcomp.c
--- regcomp.c.orig      2021-03-12 00:00:29.000000000 +0900
+++ regcomp.c   2021-05-17 03:05:41.000000000 +0900
@@ -2021,16 +2021,14 @@ findmust(struct parse *p, struct re_guts
 	if (p->error != 0)
 		return;
 
-#ifdef notyet
 	/*
 	 * It's not generally safe to do a ``char'' substring search on
 	 * multibyte character strings, but it's safe for at least
 	 * UTF-8 (see RFC 3629).
 	 */
 	if (MB_CUR_MAX > 1 &&
-	    strcmp(_CurrentRuneLocale->__encoding, "UTF-8") != 0)
+	    strcmp(_CurrentRuneLocale->rl_codeset, "UTF-8") != 0)
 		return;
-#endif
 
 	/* find the longest OCHAR sequence in strip */
 	newlen = 0;

まぁ例のアレがlocale周り手を入れてるだろうから変わってるかもしれんがそこまで調べる気にはならん。

つーかこんな移植性の無いコードでなくとも現在の文字コードなんてnl_langinfo(CODESET)なりsetlocale(LC_CTYPE, NULL)でクエリできる *1んだけどな。

$ cat >unko.c
#include <langinfo.h>
#include <stdio.h>
#include <locale.h>
int
main(void)
{
	setlocale(LC_ALL, "");
	printf("%s\n", nl_langinfo(CODESET));
	printf("%s\n", setlocale(LC_CTYPE, NULL));
}
^D
$ make unko
cc -O2   -o unko unko.c
$ LANG=ja_JP.UTF-8 ./unko
UTF-8
ja_JP.UTF-8

ここで俄然と関数呼ぶオーバーヘッドガーさんが脳内で戦いを挑んでくるのだが、そういわれましてもここ通るのregexec(3)呼ばれた時ただ一回なんすよね…

んでwide string regexの場合なんだけど、理論上これらの制限は無いはずだけど、いまの実装だとcharjumpテーブルサイズがCHAR_MIN~CHAR_MAXサイズなのでsingle byte localeにしか使えずmultibyte regexより制限きついな、そこの実装を考えないとならない感じかな。 まぁワイの縮退した脳では実装考えるのめんどくさいのでMB_LEN_MAX=1チェックだけで放置するかのう、しょせんnviなので検索や置換に速度が必要な巨大なファイルサイズなんて正規表現エンジンより先にエディタ側が死ぬしな。

*1:まぁ戻り値がポータブルであるかには議論の余地はある

[オレオレN6] わからない俺は雰囲気でregex(3)のコードを弄っている(その3)

前記事でちょっと触れたワイド文字列に対するBM法実装で、リストで持つとかにすると複雑になるし性能アレやなと思ったのだが、そもそも検索文字列に例えばUnicodeの文字全部羅列したものとか指定するとヒープ枯渇DoSが成立しちゃうので、せいぜい256文字とかで十分な気がしてきた。

そもそもエディタで検索する文字列なんてほんの数文字なわけで、検索文字列に含まれる文字種が256を超過したらBM法キャンセルされて速度が低下するって制限仕込んだとこで大した問題じゃねえよな…

これまではL'\0'~L'\xff'の範囲の文字だけのスキップテーブルを作ってたけど、それ以外のワイド文字は検索文字列中に発見した順に配列に放り込んでqsortして、マッチかけるときはbsearchで探すみたいな実装ね。

まぁその分性能は低下するわけだけど、それでもナイーブ法すなわり愚直なマッチングよりは速いんじゃねえかなぁという希望的観測。

ということでクッソ適当に実装してみた、すでにwide string regexにはFによるBM法のコードの部分は マージ済なので、それに対して差分がなるべく小さくなるよう実装した。

diff --git a/dist/nvi/regex/engine.c b/dist/nvi/regex/engine.c
index a6d1d8d6ce..edea43895f 100644
--- a/dist/nvi/regex/engine.c
+++ b/dist/nvi/regex/engine.c
@@ -49,6 +49,7 @@
 #define	at	sat
 #define	match	smat
 #define	nope	snope
+#define	getcharjump	sgetcharjump
 #endif
 #ifdef LNAMES
 #define	matcher	lmatcher
@@ -60,6 +61,7 @@
 #define	at	lat
 #define	match	lmat
 #define	nope	lnope
+#define	getcharjump	lgetcharjump
 #endif
 
 /* another structure passed up and down to avoid zillions of parameters */
@@ -89,6 +91,7 @@ static const RCHAR_T *walk(struct match *, const RCHAR_T *, const RCHAR_T *,
     sopno, sopno, int);
 static states step(struct re_guts *, sopno, sopno, states, int, RCHAR_T,
     states);
+static size_t getcharjump(struct re_guts *, UCHAR_T);
 #define MAX_RECURSION	100
 #define	BOL	(1)
 #define	EOL	(BOL+1)
@@ -159,8 +162,8 @@ matcher(struct re_guts *g, const RCHAR_T *string, size_t nmatch,
 			pp = mustlast;
 			for (dp = start+g->mlen-1; dp < stop;) {
 				/* Fast skip non-matches */
-				while (dp < stop && charjump[(int)*dp])
-					dp += charjump[(int)*dp];
+				while (dp < stop && (cj = getcharjump(g, (UCHAR_T)*dp)))
+					dp += cj;
 
 				if (dp >= stop)
 					break;
@@ -176,7 +179,7 @@ matcher(struct re_guts *g, const RCHAR_T *string, size_t nmatch,
 
 				/* Jump to next possible match */
 				mj = matchjump[pp - mustfirst];
-				cj = charjump[(int)*dp];
+				cj = getcharjump(g, (UCHAR_T)*dp);
 				dp += (cj < mj ? mj : cj);
 				pp = mustlast;
 			}
@@ -941,6 +944,24 @@ step(struct re_guts *g,
 	return(aft);
 }
 
+static size_t
+getcharjump(struct re_guts *g, UCHAR_T c)
+{
+	size_t ret;
+	struct re_bmext key, *bme;
+
+	if (ISCACHED(c)) {
+		ret = g->charjump[(size_t)c];
+	} else {
+		key.c = c;
+		key.n = 0;
+		bme = bsearch(&key, g->charjumpext, g->ncharjumpext,
+		    sizeof(g->charjumpext[0]), re_bmext_cmp);
+		ret = (bme != NULL) ? bme->n : g->mlen;
+	}
+	return ret;
+}
+
 #ifdef REDEBUG
 /*
  - print - print a set of states
@@ -1013,3 +1034,4 @@ pchar(RCHAR_T ch)
 #undef	at
 #undef	match
 #undef	nope
+#undef	getcharjump
diff --git a/dist/nvi/regex/regcomp.c b/dist/nvi/regex/regcomp.c
index e0a736fb58..125896bf88 100644
--- a/dist/nvi/regex/regcomp.c
+++ b/dist/nvi/regex/regcomp.c
@@ -236,10 +236,8 @@ regcomp(regex_t *preg, const RCHAR_T *pattern, int cflags)
 	if (g->mlen > 3) {
 		computejumps(p, g);
 		computematchjumps(p, g);
-		if (g->matchjump == NULL) {
-			free(g->charjump);
+		if (g->matchjump == NULL)
 			g->charjump = NULL;
-		}
 	}
 	g->nplus = pluscount(p, g);
 	g->magic = MAGIC2;
@@ -1697,6 +1695,21 @@ altoffset(sop *scans, RCHAR_T *scand, int offset)
 	return largest+offset;
 }
 
+int
+re_bmext_cmp(const void *a, const void *b)
+{
+	UCHAR_T ac, bc;
+
+	ac = ((const struct re_bmext *)a)->c;
+	bc = ((const struct re_bmext *)b)->c;
+
+	if (ac == bc)
+		return 0;
+	else if (ac < bc)
+		return -1;
+	return 1;
+}
+
 /*
  - computejumps - compute char jumps for BM scan
  *
@@ -1710,33 +1723,51 @@ altoffset(sop *scans, RCHAR_T *scand, int offset)
 static void
 computejumps(struct parse *p, struct re_guts *g)
 {
-	int ch;
-	size_t mindex;
+	size_t i, j, n;
+	UCHAR_T c;
+	struct re_bmext *bme;
 
 	/* Avoid making errors worse */
 	if (p->error != 0)
 		return;
 
-	assert(NC < MEMLIMIT(*g->charjump));
-	g->charjump = malloc((NC + 1) * sizeof(*g->charjump));
-	if (g->charjump == NULL)	/* Not a fatal error */
-		return;
-	/* Adjust for signed chars, if necessary */
-	g->charjump = &g->charjump[-(CHAR_MIN)];
-
 	/* If the character does not exist in the pattern, the jump
 	 * is equal to the number of characters in the pattern.
 	 */
-	for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++)
-		g->charjump[ch] = g->mlen;
+	for (i = 0; i < __arraycount(g->charjumpbuf); ++i)
+		g->charjumpbuf[i] = g->mlen;
 
 	/* If the character does exist, compute the jump that would
 	 * take us to the last character in the pattern equal to it
 	 * (notice that we match right to left, so that last character
 	 * is the first one that would be matched).
 	 */
-	for (mindex = 0; mindex < g->mlen; mindex++)
-		g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1;
+	for (i = 0; i < g->mlen; ++i) {
+		c = (UCHAR_T)g->must[i];
+		n = g->mlen - i - 1;
+		if (ISCACHED(c)) {
+			g->charjumpbuf[(size_t)c] = n;
+			continue;
+		}
+		bme = NULL;
+		for (j = 0; j < g->ncharjumpext; ++j) {
+			if (g->charjumpext[j].c == c) {
+				bme = &g->charjumpext[j];
+				break;
+			}
+		}
+		if (bme == NULL) {
+			if (g->ncharjumpext >= __arraycount(g->charjumpext))
+				return;
+			bme = &g->charjumpext[g->ncharjumpext++];
+			bme->c = c;
+		}
+		bme->n = n;
+	}
+	qsort(g->charjumpext, g->ncharjumpext,
+	    sizeof(g->charjumpext[0]), re_bmext_cmp);
+
+	g->charjump = g->charjumpbuf;
 }
 
 /*
diff --git a/dist/nvi/regex/regex2.h b/dist/nvi/regex/regex2.h
index 91b0ec682a..c1d1d27243 100644
--- a/dist/nvi/regex/regex2.h
+++ b/dist/nvi/regex/regex2.h
@@ -119,6 +119,16 @@ CHIN(const cset *cs, char c)
 	return (cs->ptr[(uch)c] & cs->mask) != 0;
 }
 
+#define CACHE_SIZE	(UCHAR_MAX+1)
+#define ISCACHED(c)	(((c) & ~UCHAR_MAX) == 0)
+
+struct re_bmext {
+	UCHAR_T c;
+	size_t n;
+};
+
+int re_bmext_cmp(const void *a, const void *b);
+
 /*
  * main compiled-expression structure
  */
@@ -144,6 +154,9 @@ struct re_guts {
 	RCHAR_T *must;		/* match must contain this string */
 	int moffset;		/* latest point at which must may be located */
 	size_t *charjump;	/* Boyer-Moore char jump table */
+	size_t charjumpbuf[CACHE_SIZE];
+	struct re_bmext charjumpext[CACHE_SIZE];
+	size_t ncharjumpext;
 	size_t *matchjump;	/* Boyer-Moore match jump table */
 	size_t mlen;		/* length of must */
 	size_t nsub;		/* copy of re_nsub */
diff --git a/dist/nvi/regex/regfree.c b/dist/nvi/regex/regfree.c
index 0c2d122816..7e16b653f8 100644
--- a/dist/nvi/regex/regfree.c
+++ b/dist/nvi/regex/regfree.c
@@ -33,6 +33,7 @@
  */
 
 #include <sys/types.h>
+#include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <regex.h>

つーかFの実装が酷いんだよなぁ、アルゴリズムだけ汎用的なコード書けるだろうに、引数にstruct parserとかstruct re_gutsとか要求するクソI/Fなので使い回しの効かないコードになってる、どうせだから切り出して汎用的なコードにしますかね。

これでどのくらい性能劣化するかなんだが、測定するために別途ライブラリとして切り出してさらにテストケース書くのがめんどくさいので当面は放置すると思われる、もう全部来世に先送りしていいですか?

というかstrstr(3)とかwcswcs(3)ってナイーブ法で実装されてるけど、BM法な実装ってありなんだっけ?C++17だとstd::boyer_moore_searcherなんて生えたそうだけど。