miura1729の日記

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

02:56 |

今回は、collect_candidate_typeの説明です。candidateとは候補とかそういった意味です。つまり、そのノードの型になる候補(複数かもしれないし0かもしれない)を収集します。前回説明したとおり、この候補から型を選び出すのが、decide_type_onceです。

collect_candidate_typeは引数にcontextを１つとり*1、contextを返します。 collect_candidate_typeの中で別に何をしてもよいのですが、主に行うのは次の3つです。このうち最初の２つの操作については、すべてのノードのスーパークラスのBaseNodeクラスでメソッドが定義されているのでこれを使います。

• 型候補を加える(add_type)
• 他のノードと同じ型だよということを設定する(same_type)
• 他のノードに対して、 collect_candidate_typeを呼び出す

型候補を加えるのは、リテラルや定数など型が明らかな場合です。たとえば、LiteralNodeではこんな感じで推論するまでもなく型候補を加えてしまいます。

   @type = RubyType::BaseType.from_object(@value) 
   sig = context.to_signature
   add_type(sig, @type)

@valueにはリテラルの値が入ります。add_typeにもシグネチャーを渡さなければなりません。

add_typeは複数の型を設定することもできます。

  add_type(sig, FLOAT)
  add_type(sig, FIXNUM)
  add_type(sig, BIGNUM)

まだ、複数の型をadd_typeで設定する場合はありませんが、nilと本来の値といった複数の型を返すメソッドの型指定で使用する予定です。

次に、同じ型だよということを設定する場合です。これが一番多いと思います。たとえば、次のような場合を考えてみます。

  a = 10

このようなプログラムはローカル変数の代入を表すLocalAssignNodeと10を表すLiteralNodeとに変換されます。

  LocalAssignNode
    @val         -> LitralNode (値は10)
　　@offset   ローカル変数のフレーム上のオフセット
    @depth　　何レベル下のフレームにアクセスするか

LocalAssignNodeの型は@valの型と同じになります。この場合、same_typeというメソッドを使って次のようにします。

   context = @val.collect_candidate_type(context)
   selfsig = context.to_signature
   valsig = context.to_signature
   same_type(self, @val, selfsig, valsig, context)

このプログラムは「selfは@valと同じ型です」という意味になります。ただし、selfはselfsig,@valはvalsigのシグネチャの場合に限ります。シグネチャは現在このノードのあるメソッドやブロックの引数の型ですが、シグネチャでsame_typeを限定する必要があるのでしょうか？たとえば、こんな場合を考えてみます。

  1 << 1
  [] << 1

メソッド<<はselfがfixnumの場合はselfと引数の型は同じです。でも、selfが配列の場合は同じとは限りません。そのため、<<がselfと引数で型が同じと単純に設定してしまうとうまくいきません。でも、シグネチャを指定してselfがFixnumの場合だけ同じであると指定すれば問題ないわけです。

あと、細かい話ですが、

  same_type(self, @val, selfsig, valsig, context)

は、selfが@valと同じ型であると指定していますが、@valとselfが同じ型であるとは言っていません。つまり、selfが別のところでsame_typeやadd_typeで別の型が候補に加わっても@valには影響がありません。相互に影響をもたらしたいなら、

  same_type(self, @val, selfsig, valsig, context)
  same_type(@val, self, valsig, selfsig, context)

と2つsame_typeを書く必要があります。このように片方にしか影響が及ばないことを利用して複数の型の候補が現れて型推論が出来なくなった場合、その影響範囲を小さくすることができます。

最後の他のノードのcollect_candidate_typeを呼び出すのはそれほど説明することはありません。ただし、add_typeもsame_typeも副作用を持ちますのでcollect_candidate_typeを呼び出す順番に注意する必要があります。

次はsame_typeの実装について書きたいと思います。同じ型という情報をどう保持するのか、どう更新するのか。Observerパターンを使っているとかそんな話です。

続く