ytljitの型推論の説明(その6)

なんだかんだで、2か月以上さぼってました。その6です。
今回はsame_typeの実装の話です。
same_typeはdstというノードがdsigというシグネチャでノードが存在するメソッドやブロックを実行している時、srcというノードのssigというシグネチャでの型と同じになると設定します。same_typeの実際のコードを見てみましょう。

def same_type(dst, src, dsig, ssig, context)
 if dst.is_a?(BaseNode) then
   src.ti_add_observer(dst, dsig, ssig, context)
  end

  ti_update(dst, src, dsig, ssig, context)
end

• ti_add_observer
• ti_update

の2つのメソッドが出てきました。この2つを順に説明します。

ti_add_observer

ti_add_observerはすべてのノードが持っている@ti_observerというインスタンス変数を設定するメソッドです。@ti_observer(tiはtype inferenceの略)は、そのノードの型が変わったら、その変化に応じて型が変化するノード(dstノード)のリストです。@ti_observerはハッシュテーブルになっていてdstノードがキーです。値は、"[srcのシグネチャ, dstのシグネチャ, srcの型が変化したら呼び出すProcオブジェクト]という配列"の配列です。通常、このProcでti_updateを呼び出します。

ti_add_observerのコードを見てみましょう。

def ti_add_observer(dst, dsig, ssig, context)
  if @ti_observer[dst] == nil then
    @ti_observer[dst] = []
    dst.ti_observee.push self
  end
          
  if @ti_observer[dst].all? {|edsig, essig, eprc| 
      (edsig != dsig) or (essig != ssig)
     } then
    prc = lambda { send(:ti_update, dst, self, dsig, ssig, context) }
    @ti_observer[dst].push [dsig, ssig, prc]
  end
 end

やっていることは、@ti_observerにdstのエントリがなければ、空の配列でエントリを作成します。
次に、まだエントリがなければ@ti_observerに追加します。src/dstとも同じシグネチャのエントリが既にあれば、追加されません。

ti_update

次に、ti_updateを見てみます。ti_update(dst, src, dsig, ssig, context)でdstのdsigというシグネチャでの型の候補リストにsrcのssigでの型の候補リストをマージします。マージの結果、型の候補リストが大きくなったら、dstに対して、ti_changedというメソッドを呼び出します。ti_changedは@ti_observerのProcオブジェクトを順番に呼び出します。結果的にdstが変化して影響の受けるノードについて、ti_updateが呼び出され、型情報の拡散が実現できます。

ti_updateのコードを見てみましょう。

def ti_update(dst, src, dsig, ssig, context)
  dtlistorg = dst.type_list(dsig)       # (1)
  dtlist = dtlistorg.flatten            # (1')
  stlist = src.type_list(ssig).flatten  # (2)

  orgsize = dtlist.size                      # (3)
  newdt = merge_type(dtlistorg[1], stlist)   # (4)
  dst.set_type_list(dsig, newdt)             # (5)
  dtsize = dtlistorg[0].size + newdt.size    # (6)

  if orgsize != dtsize then                  # (7)
    dst.type = nil                           # (8)
    dst.ti_changed                           # (9)
    context.convergent = false               # (10)
  end

  dtlist = dst.element_node_list
  stlist = src.element_node_list
  orgsize = dtlist.size
  dst.element_node_list = merge_type(dtlist, stlist)
  if orgsize != dtlist.size then
    dst.ti_changed
    context.convergent = false
  end

 if src.is_escape then
    if dst.is_escape != true then
       dst.is_escape = src.is_escape
    end
  end
end

はじめにdst(影響を受ける側)とsrc(影響を与える側)の型候補リストを得ます。型候補リストはシグネチャ毎にあるのでシグネチャがパラメータで必要です(1), (2)。flattenの意味はかなり特殊な場合の対策なのであまり気にしないでください。
(3)でdstの型候補リストのサイズを求めておきます。(4)でsrcとdstの型候補リストをマージして、(5)でdstに設定します。(6)で新しい型候補リストのサイズを求めます。
もし、(3)と(6)が違う場合次のことをします(7)。

• dst.type(型候補リストから型を1つに決めたもののキャッシュ)をnilにします。型候補リストそのものが変わったのでdst.typeは無意味になります。(8)
• dst.ti_changedを呼び出す。これは前に説明した通り、dstから影響の受けるノードの型候補リストのアップデートを行います。
• context.convergentをfalseにする。これは、型推論が収束したかのフラグでfalseだと推論を繰り返します。型候補リストが変わるような場合だとまだまだ型が変わっていく可能性があるので型推論を終えるわけにはいかないのです。

と、こんな感じです。まだ、続きがありますが、これを説明するためには新たな概念の説明が必要になります。これはelement_node_listです。次回はこれについて説明したいと思います。

みんなが寒いといっているうちに続きを書きたいですがどうなることやら。続く