ツイート本文から、URLっぽい部分を正規表現で抽出する
マッチした箇所の始点と終点を記録する
URLとしてvalidなら、返り値のリストに追加する
- URLとしてvalidかどうかは、正規表現マッチした文字列をprotocol, domain, port, path, query, fragment……などのグループに分けてバリデーションする

Rubyの場合、 String#scan にブロックを渡すことで、マッチした箇所をグループに分けてループを回すことができます。また、マッチした箇所の始点と終点は $~ 特殊変数から取り出すことができます。

text.scan(REGEXP) do |all, before, url, protocol, domain, port, path, query|
  valid_url_match_data = $~
  start_position = valid_url_match_data.char_begin(3)
  end_position = valid_url_match_data.char_end(3)
  ...
end

Perlの場合はどうするかというと、whileループ*1と、正規表現のグループ化と /g フラグを組み合わせることで、同様のループを回すことができます。また、各グループのマッチした始点と終点は、それぞれ @- @+ 特殊変数から取得できます。

while ($text =~ /($REGEXP)/g) {
    my ($before, $url, $protocol, $domain, $port, $path, $query, $fragment) = ($3, $4, $5, $6, $7, $8);
    my $start_position = $-[4];
    my $end_postition = $+[4];
    ...
}

$REGEXP 正規表現全体をグループ化しているので、文字列をキャプチャしたときのインデックスが1つずつずれることに注意しましょう。

他の抽出処理も基本的な流れは同じなので、歯を食いしばって移植していきます。

YAML::Tiny

twitter-textのテストケースや、TLDなどのリストはYAMLで公開されています。また、テストケースはYAMLを読み込んでテストする形にすること・YAMLからテストコードを生成しないこと(?)、と書いてあるので、YAMLのパースが必要です。

Create a test which reads these files and executes the test cases.
1.a. Do not convert these files to test cases statically. These test cases will change over time.

https://github.com/twitter/twitter-text/tree/master/conformance#guidelines-for-use

YAMLのパースに YAML::Tiny を使ったのですが、 ["foo", "bar"] という配列表現を、そのまま文字列としてパースしてしまっていました。配列表現を eval することでArrayRefに変換することでなんとかしました。

また、 expected: true というYAMLのエントリを読み込んだときも "true" という文字列としてパースされてしまいました。これはどうパースするべきか難しい気がしますが、ひとまずテストケースの側で is ..., bool($expected eq 'true') という形でアサーションすることにしました。

いちばん困ったのは、\u0000 のような、YAMLのUnicodeリテラルをうまくパースできないことです*2。これはYAML 1.2の規格を眺めつつ正規表現置換でなんとかしました。ここまでくると、 YAML::Tiny より高機能なYAMLパースライブラリを探す必要がある気がします。誰かよいYAMLパースライブラリについて教えてください。

JSONをパースする必要もあったのですが、これは JSON::XS を使えばよかろうということで、とくに困りませんでした。

2020/10/31 追記

YAML::PP を使うようにしたら、YAMLの真偽値が文字列になるので bool($expected eq 'true') ってしたり、配列をパースするためにevalしたり(！) する必要がなくなって最高便利 https://t.co/YrK3OM8V1x
— うたがわきき (@utgwkk) 2020年10月30日

サロゲートペア

display_offset_end (表示される文字列の終端の位置) や valid_offset_end (ツイートとしてvalidな文字列の終端の位置) が、テストケースと違う値になって、どうすればいいんだ……と頭を抱えることになりました。

Ruby実装のテストを見に行くと、言語実装によって文字数カウントの方法が違うのでテストしない、ということが書いてあって、それでいいのか……と思い、その方針に倣うことにしました。値は返すけどconformanceに従ってるとは限らないよ、というスタンスです。 JavaScript実装などでは、意図した通りの valid_offset_end が取れる? ようです。なんにせよ文字数カウントの方法が違うだけで、何文字削ればvalidになるかは引き算をすれば計算できるので、まあよいのではないでしょうか。

まとめ・感想

twitter-textのPerl実装 Twitter::Text を公開しました。autolinkなどは実装されていませんが、ツイートのバリデーション用途ぐらいにはじゅうぶんな機能が実装されているはずです。もっと効率的に書けるとか、バグってる、などありましたら GitHub - utgwkk/Twitter-Text: Perl implementation of the twitter-text parsing library までお願いします。

今更ですが、Perlの名前空間の規則に従うなら Text::Twitter にしたほうがよい気がしてきました。しかし、https://github.com/djm4/twitter-text-perl と名前がかぶる*3ので悩ましいところですね……。

*1:試してないけど、forループでもできる?

*2:なんかどうしてもテスト通らないけどなんでなのか……と頭を抱えて、printデバッグしたら \u0000 みたいな文字列が目に入って発覚した

*3:その上、READMEにhttp://search.cpan.org/dist/Text-Twitter/へのリンクがある!!

2020-10-26

■

厳しい夢を見た気がするけど、二度寝を繰り返していたら内容を忘れた。

2020-10-24

(デフォルトでは無効にしました) perl-insert-packageにパッケージ名の補完機能を追加した

技術

VSCodeでPerlのパッケージ名を入力できる拡張機能 perl-insert-package に、パッケージ名の補完機能を追加した新バージョン 1.10.0 をリリースしました。どうぞご活用ください。どういうことかと言うと、以下の動画をご覧ください。

gyazo.com

この拡張機能を世に出してからもう1年が経過しようとしています。最初は package 宣言を補完したいという素朴な問題を解決する拡張機能として作っていたのですが、だんだん壮大な感じになってきました。変数の補完とかもしたくなってきたけど、Perlなしで満足に動くものを作るのは難しそうな気がします。

blog.utgw.net

追記

Plackのリポジトリで試していたら package 宣言の補完がうまく動かなくなっていたので、条件を調整して動くようにしました。

packa まで見なくても補完される
- 1行目にいきなり pack って書きたい人はいないだろう、という想定
最初の3行までは補完される
- ファイルに対応するpackage宣言を書きたくなるのは高々3行目ぐらいまでだろう、という想定
既にファイルに対応する package 宣言があったら補完されない
- 2回 package 宣言を書きたくなることはよほどのことがない限りはないだろう、という想定

追記2

パッケージ名の補完を有効にすると、これまで動いていた単語単位の補完まで動かなくなり、体験を大きく変えることが分かってきました。そのため、デフォルトではパッケージ名の補完を行わず、設定で有効できるようにする形にしました。なんかもうちょっと考えたい。

2020-10-24

MySQLのEXPLAIN結果がどんどん変わっていく例

技術

MySQLのEXPLAINが直感とは異なっていた事例の続き。ふと実験中にEXPLAINを打っていたら、 rows が減っていることに気づいたのでさらに追試をした。

実験

MySQLのEXPLAINが直感とは異なっていた事例の実験で、SELECT文にかかった秒数に加えて、EXPLAINの rows の値も測定する。MySQL 8.0で実験した。

結果

f:id:utgwkk:20201024083607p:plain *1

mysql explain test rows - Google スプレッドシート

考察

インデックスなしの場合、常に rows は50
インデックスありの場合
- done = TRUE な行数が14万を超えるまでは、 rows は一定
- 14万を超えたあたりから、振動しつつも減少傾向になる
- 全ての行が done = TRUE になったら rows は1になる
(Cardinality低, Cardinality高) というインデックスを貼るとこういうことが起こりうるのだろうか

`SHOW INDEXES` を見る

mysql> SHOW INDEXES FROM tbl_with_index;
+----------------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| Table          | Non_unique | Key_name    | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | Visible | Expression |
+----------------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+
| tbl_with_index |          0 | PRIMARY     |            1 | id          | A         |      998568 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| tbl_with_index |          1 | done_and_id |            1 | done        | A         |           1 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
| tbl_with_index |          1 | done_and_id |            2 | id          | A         |      998568 |     NULL |   NULL |      | BTREE      |         |               | YES     | NULL       |
+----------------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+---------+------------+

998568 / 2 = 499284 で、この値は done = TRUE な行数が14万を超えたあたりのEXPLAINの rows の値に一致する
- done は BOOLEAN なので、EXPLAINすると最悪ケースでテーブルの行数のおよそ半分ぐらいをなめることになる、と予測されている？

*1:縦軸のスケール感をうまく調整したい

2020-10-23

MySQLのEXPLAINが直感とは異なっていた事例

技術

おもしろかったのでメモ。

CREATE TABLE `tbl` (
    `id` BIGINT UNSIGNED NOT NULL,
    `done` BOOLEAN NOT NULL DEFAULT FALSE,

    PRIMARY KEY (`id`),
    KEY `done_and_id` (`done`, `id`)
);

tbl テーブルに done = FALSE で100万行INSERTしておく
SELECT id FROM tbl WHERE done = FALSE ORDER BY id ASC LIMIT 50 でidを順に集める
処理する
UPDATE tbl SET done = TRUE WHERE id IN (...) で処理済にする
これを done = FALSE な行がなくなるまで繰り返す

KEY `done_and_id (`done`, `id`) ありでEXPLAINする

mysql> EXPLAIN SELECT * FROM tbl_with_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+------+-------------+----------------+------+---------------+-------------+---------+-------+--------+--------------------------+
| id   | select_type | table          | type | possible_keys | key         | key_len | ref   | rows   | Extra                    |
+------+-------------+----------------+------+---------------+-------------+---------+-------+--------+--------------------------+
|    1 | SIMPLE      | tbl_with_index | ref  | done_and_id   | done_and_id | 1       | const | 499284 | Using where; Using index |
+------+-------------+----------------+------+---------------+-------------+---------+-------+--------+--------------------------+
1 row in set (0.01 sec)

明らかに効くインデックスのはずなのに rows がめっちゃ大きくてやばそう。

KEY `done_and_id (`done`, `id`) を消してからEXPLAINする

mysql> EXPLAIN SELECT * FROM tbl_without_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+------+-------------+-------------------+-------+---------------+---------+---------+------+------+-------------+
| id   | select_type | table             | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+------+-------------+-------------------+-------+---------------+---------+---------+------+------+-------------+
|    1 | SIMPLE      | tbl_without_index | index | NULL          | PRIMARY | 8       | NULL |   50 | Using where |
+------+-------------+-------------------+-------+---------------+---------+---------+------+------+-------------+
1 row in set (0.01 sec)

rows はLIMITぶんしかないので安心？

実験

ConoHaのDBサーバー*1 (Server version: 5.5.5-10.0.19-MariaDB-log MariaDB Server) に向けて以下のようなクエリにかかる時間を、 done = TRUE な行を1000行ずつ増やしながら測定した。

SELECT * FROM tbl WHERE done = FALSE ORDER BY id ASC LIMIT 50

実験に使ったコード: GitHub - utgwkk/20201023-sketch-mysql-query-exam

実験結果: mysql explain test - Google スプレッドシート

f:id:utgwkk:20201023205014p:plain — インデックスなし (without_index) とインデックスあり (with_index) のSELECTにかかる時間

考察

インデックスなしだと、done = TRUE な行が増えるにつれてSELECTの速度が低下している
インデックスありの場合は、 done = TRUE な行の数に関係なく、ほぼ一定時間でSELECTできている
done = TRUE な行が少ないうちは、インデックスなしのほうがSELECTが速い
- インデックスのオーバーヘッドがありそう

まとめ

MySQLのEXPLAINが~~そのまま信用できるとは限らない~~直感とは異なる結果になることがある
- 効くでしょうと思って貼ったインデックスが裏目に出るようなEXPLAIN結果になることもある
- 逆に、EXPLAINのrowsが小さいのでいけるかと思ってもうまくいかないこともある
自信がなかったら実験する
- データ量が増えたときにどうなるか
- done = TRUE な行が増えたときにどうなるか
MySQLのバージョンが上がるとEXPLAINが正確になるのかな

追記

EXPLAIN EXTENDED も見た。

mysql> EXPLAIN EXTENDED SELECT * FROM tbl_with_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+------+-------------+----------------+------+---------------+-------------+---------+-------+--------+----------+--------------------------+
| id   | select_type | table          | type | possible_keys | key         | key_len | ref   | rows   | filtered | Extra                    |
+------+-------------+----------------+------+---------------+-------------+---------+-------+--------+----------+--------------------------+
|    1 | SIMPLE      | tbl_with_index | ref  | done_and_id   | done_and_id | 1       | const | 499284 |   100.00 | Using where; Using index |
+------+-------------+----------------+------+---------------+-------------+---------+-------+--------+----------+--------------------------+
1 row in set, 1 warning (0.01 sec)

mysql> EXPLAIN EXTENDED SELECT * FROM tbl_without_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+------+-------------+-------------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id   | select_type | table             | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra       |
+------+-------------+-------------------+-------+---------------+---------+---------+------+------+----------+-------------+
|    1 | SIMPLE      | tbl_without_index | index | NULL          | PRIMARY | 8       | NULL |   50 |   100.00 | Using where |
+------+-------------+-------------------+-------+---------------+---------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)

filtered カラムは、テーブル条件によってフィルタ処理されるテーブル行の推定の割合を示します。つまり、rows は調査される推定の行数を示し、rows × filtered / 100 が前のテーブルと結合される行数を示します。EXPLAIN EXTENDED を使用すると、このカラムが表示されます。 MySQL :: MySQL 5.6 リファレンスマニュアル :: 8.8.2 EXPLAIN 出力フォーマット

追記2

バージョンごとのEXPLAIN結果を見比べてみたけど、どれも変わらないようだった。実行時間もいちおう貼っておくけど大して変わらなかった。

mysql explain test for different versions - Google スプレッドシート

MySQL 5.6 (5.6.47)

mysql> EXPLAIN SELECT * FROM tbl_without_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+----+-------------+-------------------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table             | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+-------------------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | tbl_without_index | index | NULL          | PRIMARY | 8       | NULL |   50 | Using where |
+----+-------------+-------------------+-------+---------------+---------+---------+------+------+-------------+
1 row in set (0.01 sec)

mysql> EXPLAIN SELECT * FROM tbl_with_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+----+-------------+----------------+------+---------------+-------------+---------+-------+--------+--------------------------+
| id | select_type | table          | type | possible_keys | key         | key_len | ref   | rows   | Extra                    |
+----+-------------+----------------+------+---------------+-------------+---------+-------+--------+--------------------------+
|  1 | SIMPLE      | tbl_with_index | ref  | done_and_id   | done_and_id | 1       | const | 499284 | Using where; Using index |
+----+-------------+----------------+------+---------------+-------------+---------+-------+--------+--------------------------+
1 row in set (0.00 sec)

MySQL 5.7 (5.7.25)

mysql> EXPLAIN SELECT * FROM tbl_without_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+----+-------------+-------------------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id | select_type | table             | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------------------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | tbl_without_index | NULL       | index | NULL          | PRIMARY | 8       | NULL |   50 |    10.00 | Using where |
+----+-------------+-------------------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)

mysql> EXPLAIN SELECT * FROM tbl_with_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+----+-------------+----------------+------------+------+---------------+-------------+---------+-------+--------+----------+--------------------------+
| id | select_type | table          | partitions | type | possible_keys | key         | key_len | ref   | rows   | filtered | Extra                    |
+----+-------------+----------------+------------+------+---------------+-------------+---------+-------+--------+----------+--------------------------+
|  1 | SIMPLE      | tbl_with_index | NULL       | ref  | done_and_id   | done_and_id | 1       | const | 499284 |   100.00 | Using where; Using index |
+----+-------------+----------------+------------+------+---------------+-------------+---------+-------+--------+----------+--------------------------+
1 row in set, 1 warning (0.02 sec)

MySQL 8.0 (8.0.18)

mysql> EXPLAIN SELECT * FROM tbl_without_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+----+-------------+-------------------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
| id | select_type | table             | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------------------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | tbl_without_index | NULL       | index | NULL          | PRIMARY | 8       | NULL |   50 |    10.00 | Using where |
+----+-------------+-------------------+------------+-------+---------------+---------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.01 sec)

mysql> EXPLAIN SELECT * FROM tbl_with_index WHERE done = FALSE ORDER BY id ASC LIMIT 50;
+----+-------------+----------------+------------+------+---------------+-------------+---------+-------+--------+----------+-------------+
| id | select_type | table          | partitions | type | possible_keys | key         | key_len | ref   | rows   | filtered | Extra       |
+----+-------------+----------------+------------+------+---------------+-------------+---------+-------+--------+----------+-------------+
|  1 | SIMPLE      | tbl_with_index | NULL       | ref  | done_and_id   | done_and_id | 1       | const | 499572 |   100.00 | Using index |
+----+-------------+----------------+------------+------+---------------+-------------+---------+-------+--------+----------+-------------+
1 row in set, 1 warning (0.02 sec)

追試はGoogle Could SQLで行った。

Google Cloud SQL、高速にオープンインターネット大公開のMySQLをこしらえることができて便利すぎる https://t.co/D6GILHLFcH pic.twitter.com/YqwJBQESVs
— うたがわきき (@utgwkk) 2020年10月23日

追記3

MySQL 8.0でしか確認してないが、tbl_with_index テーブルについて、 done = TRUE な行が増えるにつれてEXPLAINの rows が減少した。この現象については MySQLのEXPLAIN結果がどんどん変わっていく例 - 私が歌川ですで挙動を確かめた。

追記4

もともと「MySQLのEXPLAINがそのまま信用できるとは限らない事例」という記事タイトルだったが、信用できる・できないという言い方は正確ではなかったのでタイトルを変更した。

EXPLAINは嘘をつかない
統計情報がちゃんと更新されているかを確認するべき
なぜこの実行計画が選ばれたかを確認したいならオプティマイザトレースを確認するとよさそう

という指摘をいただいた。オプティマイザトレースについてはあとで確認してみる。

*1:RDSを使おうとしたけど、外から接続する方法が分からず断念した

2020-10-21

SQLなら分かる

技術

スプレッドシート、QUERY関数を通すとSQLっぽいやつが書けるようで、SQLなら分かる!!! と SELECT B, COUNT(B) WHERE B IS NOT NULL GROUP BY B ORDER BY COUNT(B) DESC とか書けておもしろかった https://t.co/1WM9omXaT0
— うたがわきき (@utgwkk) 2020年10月20日

スプレッドシートにどんな関数があるとか、文法はどうなっているのか、みたいなのはググらないと分からないけど、SELECT文が書けることに気づいて、やりたいことは一瞬で達成できた。共通言語があればなんとなく読めるし書けるみたいな状態。

QUERY - ドキュメントエディタヘルプ

Query Language Reference (Version 0.7) | Charts | Google Developers

動機

実装方針・ハマりどころ

Ruby実装をもとにする

正規表現地獄

正規表現マッチングの移植と特殊変数