LoginSignup
4
2

More than 5 years have passed since last update.

RubyAdvent Calendar 2017Day 20
@long_long_float

RubyでTraceMatchingを実装した話

Posted at

これは Ruby Advent Calendar 2017 20日目の記事です。少し遅れてすみませんでした。

はじめに

Trace Matchingというものをご存知でしょうか? Trace Matchingとは平たく言うとプログラムの実行時にある操作に対してフックを仕掛け(シンボルという)、シンボルの履歴に対してマッチングをするものです。

これだけだと伝わりにくいと思うので以下の例を用いて説明します。tracematchはJava向けのAspectJの拡張なのでJavaコードで説明します。

tracematch
tracematch() {
  sym f before: call(* f(..));
  sym g before: call(* g(..));

  f g 
  {
    System.out.println("fg!");
  }
}

これは、以下を満たすtracematchです。

  • fというメソッドが呼ばれる時( joinpoint という)、fというシンボルを履歴に追加
  • gも同様
  • 履歴中でfというシンボルの直後にgというシンボルが来たらfg!を出力する

つまり、以下のプログラムに対してコメントの通りに出力をします。

f();
g(); // fg!

f();
f();
g(); // fg!

g();
f();

他にも機能はあるのですがTraceMatchingの記事ではないので省略させていただきます。詳しくは http://www.runtime-verification.org/course09/lecture4/tracematches.pdf をご覧ください。

今回はこのTraceMatchingをRubyで実装してみた際に使用したテクニック等を解説していきます。ただ実装したTraceMatchingは不完全なもので、例えば複数の変数のバインドに対応していないです。あくまでRubyでこういうことができるということを知っていただければと思います。

ソースコードは https://github.com/long-long-float/tracematch-rb に置いておきます。

実行例

1-target-def.rb
def f
  puts "called f"
end

def g
  puts "called g"
end
1-target-code.rb
g
f
g
f
g

以上のコード(以下ターゲットコード)に対してtracematch

1-tm.rb
require './tracematch.rb'

tm = Tracematch.tracematch do
  sym(:f, :before)
    .call(:f, [_.._])

  sym(:g, :after)
    .call(:g, [_.._])

  match("f g") do
    puts "fg!"
  end
end

tm.run(File.read("./1-target-def.rb"), File.read("./1-target-code.rb"))

を書いて実行すると

$ ruby 1-tm.rb
called g
called f
called g
fg!
called f
called g
fg!

ちゃんとトレースされています。諸事情によりターゲットコードが、定義部(クラスやメソッドを定義するコード)と実行部(実際に処理をする部分)に分かれています。

メソッドのフック

まず必要なのが特定のメソッドが呼ばれたかどうか検知する仕組みです。これは対象のメソッドやクラスをこちらが用意したメソッドやクラスでラップすることで実現することができます。ラップしたメソッドやクラス内でフックの処理と本来のメソッドをコールすれば対象のコードの動作を変更することなくトレースすることができます。

具体的な処理を以下に示します。

1. ターゲットプログラムの定義部を実行して定義されているメソッドやクラスを拾う

メソッドやクラスをラップするためには、まずラップする対象を知る必要があります。すぐに思いついた方法としては、

  1. 対象のプログラムのRubyVMのバイトコードからメソッドやクラスの定義を集める
  2. 対象のソースコードをパースしてメソッドやクラスを集める
  3. 定義部のコードをサンドボックスのclass_evalで実行してサンドボックス内のメソッドやクラス(定数)を集める

1について、Rubyは与えられたプログラムを直接実行せずに一旦Ruby専用のVMで実行できる形式にコンパイルしてから実行しているのですが、実行する前にコンパイルしたバイトコードに手を加えるという方法です。これは集めるだけでなくバイトコードを弄ることでフックの処理もできて良さそうですが、どうも昔の知識でバイトコードを取得はできるが実行はできないものと思い込み、見送ってしまいました。この記事を書くときに改めて調べてみると RubyVM::InstructionSequence.load_from_binaryを使えばバイトコードをロードすることができるようです。

ただこれには(言い訳がましいですが)欠点があって、evalのような動的に実行するプログラムに対しては使えないです。(そもそもそういうプログラムはめったに書かないですが…)

2はソースコードを解析することで定義されているメソッドやクラスを集める方法です。解析するためにパースする必要があるのですがこれには、parserやRipperを使うことができます。これも1と同様にevalに対しては無効です。また、定義を取得はできるのですがラップできないので見送りました。

3は対象のコードをサンドボックスのクラスのコンテキストで実行することでメソッドやクラスの定義を取得する方法です。この方法の良いところはメソッドやクラス自体をこちら側で得ることができるのでメソッドを呼び出したりクラスのインスタンスを生成することができる点です。

この方法にも欠点はあってメソッドやクラスの定義とそれを実行する部分を分けないといけません。一緒にしてしまうとclass_evalするときに実行部分も実行してしまうからです。

今回はとりあえず動かしたかったので3の方法を採用しました1。

実際の実装は以下のようになっています。

class BaseSandbox
end

class Sandbox
  def initialize(base_sandbox)
    @@base_sandbox = base_sandbox
  end

  def method_missing(name, *args)
    @@base_sandbox.send(name, *args)
  end

  def self.const_missing(name)
    @@base_sandbox.class.const_get(name)
  end
end

# def_src: 定義部分
# code_src: 実行部分
def run(def_src, code_src)
  BaseSandbox.class_eval(def_src)
  base_sandbox = BaseSandbox.new

  sandbox = Sandbox.new(base_sandbox)

  # snip...
end

まず定義部のソースコードをBaseSandbox.class_evalで実行しています。ある程度Rubyに馴染んでいる方はなぜinstance_evalではないのかと思われるかもしれませんが、instance_evalだと実行後のインスタンスからメソッドは取れるのですがクラス(というか定数)は取れなかったのでclass_evalの方を使用しました。

BaseSandboxに対象のコードのメソッドやクラスが定義されているのでこれを次で定義するメソッドやクラスで上書きしないようにSandboxクラスでラップします。上書きしなければ何でも良いのでalias等を用いて別名にしてしまうのも手です。

2. 1で拾ったメソッドやクラスをラップする

メソッドやクラスの定義を取得出来たらそれを利用してラップします。まずメソッドの方の実装を示します。

that = self # class_eval内でこのselfを参照したい

@definition.syms.each do |sym|
  sym.calls.each do |call|
    klass_name, method_, args = call
    if klass_name == nil # メソッドの場合
      Sandbox.class_eval do
        base_sandbox = class_variable_get(:@@base_sandbox)
        define_method(method_) do |*args|
          that.before_apply(nil, nil, method_, args) # before処理
          base_sandbox.send(method_, *args)          # 元のメソッドを呼ぶ
          that.after_apply(nil, nil, method_, args)  # after処理
        end
      end
    end
  end
end

symsはtracematch内で書いたシンボルです(例でいうところのfやg)。callは対象のメソッド名や引数の情報が格納されています。つまり、tracematchで書いたシンボルのcallのメソッドをラップするようになっています。

ラップの部分は先ほどのSandboxクラスに対象のメソッドと同名のメソッドを定義します。そのメソッドの中でフックの処理と元のメソッドを呼ぶ処理をしています。

次はクラスです。

@definition.variables.each do |name, klass_name|
  Sandbox.class_eval do
    base_sandbox = class_variable_get(:@@base_sandbox)
    # 元のクラスをラップした新たなクラスを定義する
    klass_body = Class.new do

      @@klass_name = klass_name
      @@base_sandbox = base_sandbox
      @@that = that

      def initialize(*args)
        @@that.before_apply(nil, @@klass_name, :new, args)
        # 対象のクラスのインスタンスを保持する
        @base_inst = @@base_sandbox.class.const_get(@@klass_name).new(*args) 
        @@that.after_apply(@base_inst, @@klass_name, :new, args)
      end

      def method_missing(name, *args)
        @@that.before_apply(@base_inst, @@klass_name, name, args)
        @base_inst.send(name, *args)
        @@that.after_apply(@base_inst, @@klass_name, name, args)
      end
    end

    const_set(klass_name, klass_body)
  end
end

これはデザインパターンでいうところのProxyパターンを忠実に実装したものとなっています。Rubyではmethod_missingというものがあるのでかなりシンプルに書けてしまいます。

3. 2の環境でターゲットプログラムの処理部を実行する

上記で準備したsandboxのコンテキストでプログラムを実行するだけです。

sandbox.instance_eval(code_src)

正規表現エンジンの実装

実はtracematchのmatchには正規表現を書くことが出来ます。なのでシンボルの履歴がマッチするかどうかどうかを調べるために正規表現のエンジンを実装しました。

正規表現エンジンは大別して2種類あります。

  • DFA型
    • 正規表現からNFAに変換しそれをDFAに変換し実行
  • VM型
    • 正規表現を専用のVMのコードに変換しVMで実行

今回は実装が容易そうなVM型で実装しました。実装にあたってはRegular Expression Matching: the Virtual Machine Approachを参考にしました。

実装について、基本的には上のページにある通りに実装すればいいのでポイントだけ列挙します。

  • 字句解析、構文解析
    • 論文にあった正規表現の文法を左再帰のない形に置き換えた
  • コンパイル
    • REGEX [n]に対応する命令が正規表現の論文になかったのでn回REGEXをコンパイルすることにした
  • 実行
    • 1つのVMを1つのスレッドとすることにした
    • 生成されたすべてのスレッドの終了を待ち、一番大きいSPを処理結果とする(最長マッチ)
      • マッチした or していないが分かればいいのであるスレッドがマッチした時点で終了したほうが高速かも…

さて、このままではTraceMathingに組み込めないです。それは上の(というか普通の)正規表現は先頭を基点にマッチングを行うのですが、TraceMathingでは最後を基点にマッチングを行います(Rubyなどの正規表現での$相当)。なのでパターンと入力シンボル列をそれぞれ逆にしてそれを使うことにしました。ここでパターンの逆とは「再帰的にASTを見ていき、連接の前後を逆にする。それ以外はそのまま。」としたものです。

まとめ

RubyでTraceMathingを実装し、それに使用したテクニックを解説しました。

次は @TomoProg さんの 一攫千金プログラミングpaizajackを自動化して１位を目指すです。

  1. 恐らく今実装するのだったら1を採用しますが ↩

4
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
2