Hello, re::engine!

Shibuya.pm Technical Talk #16 夏の正規表現祭り

id:gfx / @__gfx__ <Fuji.Goro at DeNA.jp>

自己紹介

Fuji Goro (gfx)

A programmer working at DeNA, Co., Ltd.
Products: Xslate

正規表現との付き合い

HTML::FillInForm::Lite - 正規表現で実装し、HTML::ParserベースのHTML::FillInFormより高速に

Text::Xslate - tokenizerを正規表現で実装

re::engineとは

Perlの正規表現演算をオーバーロードできるようにする仕組み

Use Perl; - Perl5 Regex Engine Abstracted

Perl5の正規表現をプラガブルにしたよーという記事(2006)

Perlコアと正規表現エンジンを独立させた

Perl6への布石だったと思われる

Example 1


#!/usr/bin/env perl
use 5.10.0;
use strict;
use warnings;

use re::engine::RE2;

('1' x $_) !~ /^(11+?)\1+$/ and say for 2 .. 100;

ありがたみが見えにくい…

コードを修正しなくてもエンジンを差し替えられるのがメリット

CレベルのAPIなので高速なのもポイント

m//だけでなくs//, split // でも使われる

How it works

関数ポインタを格納したregexp_engineをvirtual tableにして関数をディスパッチする手法。

Cでpolymophic methodを実現するよくあるやりかた。Perlでは他にもMAGIC変数やPerlIOなどでもこの手法が使われている。

Virutal Table in regexp.h


typedef struct regexp_engine {
  REGEXP* (*comp) (pTHX_ SV * const pattern, U32 flags);
  I32     (*exec) (pTHX_ REGEXP * const rx, char* stringarg, char* strend,
  char* strbeg, I32 minend, SV* screamer,
  void* data, U32 flags);
  char*   (*intuit) (pTHX_ REGEXP * const rx, SV *sv, char *strpos,
  char *strend, const U32 flags,
  re_scream_pos_data *data);
  SV*     (*checkstr) (pTHX_ REGEXP * const rx);
  void    (*free) (pTHX_ REGEXP * const rx);
  void    (*numbered_buff_FETCH) (pTHX_ REGEXP * const rx, const I32 paren,
  SV * const sv);
  void    (*numbered_buff_STORE) (pTHX_ REGEXP * const rx, const I32 paren,
  SV const * const value);
  I32     (*numbered_buff_LENGTH) (pTHX_ REGEXP * const rx, const SV * const sv,
  const I32 paren);
  SV*     (*named_buff) (pTHX_ REGEXP * const rx, SV * const key,
  SV * const value, const U32 flags);
  SV*     (*named_buff_iter) (pTHX_ REGEXP * const rx, const SV * const lastkey,
  const U32 flags);
  SV*     (*qr_package)(pTHX_ REGEXP * const rx);
#ifdef USE_ITHREADS
  void*   (*dupe) (pTHX_ REGEXP * const rx, CLONE_PARAMS *param);
#endif
} regexp_engine;

Compile & Execute


  REGEXP* (*comp) (pTHX_ SV * const pattern, U32 flags);

  I32     (*exec) (pTHX_ REGEXP * const rx, char* stringarg, char* strend,
                      char* strbeg, I32 minend, SV* screamer,
                      void* data, U32 flags);

Hints for optimization


  char*   (*intuit) (pTHX_ REGEXP * const rx, SV *sv, char *strpos,
                      char *strend, const U32 flags,
                      re_scream_pos_data *data);

  SV*     (*checkstr) (pTHX_ REGEXP * const rx);

Captured variables ($1, %+, etc)


  void    (*numbered_buff_FETCH) (pTHX_ REGEXP * const rx, const I32 paren,
                          SV * const sv);

  void    (*numbered_buff_STORE) (pTHX_ REGEXP * const rx, const I32 paren,
                          SV const * const value);

  I32     (*numbered_buff_LENGTH) (pTHX_ REGEXP * const rx, const SV * const sv,
                          const I32 paren);

  SV*     (*named_buff) (pTHX_ REGEXP * const rx, SV * const key,
                          SV * const value, const U32 flags);

  SV*     (*named_buff_iter) (pTHX_ REGEXP * const rx, const SV * const lastkey,
                          const U32 flags);

各種正規表現エンジンそろってます

re::engine::PCRE
re::engine::Oniguruma
re::engine::RE2

re::engine::PCRE

PCRE: Perl Compatible Regular Expressions
Perlと互換性のある正規表現がつかえる！！１１１
速度・機能はPerl組み込みとほぼ同等

re::engine::Oniguruma

鬼車: Ruby 1.9で採用された正規表現エンジン
マルチエンコーディング対応 ※ 意味なし
バックトラックに強い(参考：正規表現の限界を突破する)

re::engine::RE2

RE2: Googleが開発した高速・省メモリの正規表現エンジン
複雑な正規表現だとPerl組み込みのものより高速
やや低機能で、処理しきれないとPerl組み込みのものにフォールバックする

re::engine::boost

boost::regex: boostの正規表現エンジン
遅すぎて話にならない
Perl mode / JavaScript modeなど揃っているが…

re::engine::Plugin

pure Perlで正規表現エンジンを拡張できるようにしたVPIT ware

これからの展望

別の正規表現エンジンを簡単に試せるのがすごい
世界最速grepの正規表現エンジンのバインディングも！