RubyVM::AST に関するメモ書き

hkdnet.hatenablog.com

作ったけど微妙ですわこれ(手のひら返し
使い始めたら、 children にアクセスするのに node_type とかそんなに意識したくないんだよなーということに気づきました

いまやろうとしてるのは RubyVM::AST を使って Ruby インタプリタRuby で書くことなんですけど。
例えば puts 1 という文字列をみて、「あーノード的にはFCALL呼び出しで、メソッドがこれなのね、はいはい」という気持ちで処理したいわけです。
なんだけども、実はメソッド名(= mid, ここでは puts ) って NODE としては情報持ってないんですよね。

$ ruby -v
ruby 2.6.0preview2 (2018-05-31 trunk 63539) [x86_64-darwin17]
$ ruby --dump=pa -e 'puts 1'
###########################################################
## Do NOT use this node dump for any purpose other than  ##
## debug and research.  Compatibility is not guaranteed. ##
###########################################################

# @ NODE_SCOPE (line: 1, location: (1,0)-(1,6))
# +- nd_tbl: (empty)
# +- nd_args:
# |   (null node)
# +- nd_body:
#     @ NODE_FCALL (line: 1, location: (1,0)-(1,6))*
#     +- nd_mid: :puts
#     +- nd_args:
#         @ NODE_ARRAY (line: 1, location: (1,5)-(1,6))
#         +- nd_alen: 1
#         +- nd_head:
#         |   @ NODE_LIT (line: 1, location: (1,5)-(1,6))
#         |   +- nd_lit: 1
#         +- nd_next:
#             (null node)

puts(1,0)-(1,4) のはずなんだけどそうした位置情報を持つ NODE はありません。一方で nd_mid という情報で :puts はもっています。ここでいきなりメソッド名がシンボルになっていますが、Ruby は内部的なメソッド名などはシンボルとしてもっているので(たしか)そうなっています。

位置のほうに話をもどすと、引き算をしたりすればたぶんなんとかなるんですが puts 1 とか puts(1) の差異とか考えたくないし AST っていうなら NODE_FCALL にまつわる mid もくださいよ!という気持ちになったのでした。そうすると c コード書く必要がありますね。

とゆーわけでとりあえず積んでるのがこのへん。これによって extrainfo とかやると Hash で情報が返ってきます。

$ ./miniruby -e 'p RubyVM::AST.parse("puts 1").children[1].extrainfo'
{:mid=>:puts}

https://github.com/hkdnet/ruby/compare/b7595f2c2ec14389170808dfb36b1d99c9d0e899...814746725cbb26d139feb9f3a5cc74b22b200dd0?expand=1

RubyVM::AST::Node の children を作成するときにいい感じに switch 文があったので拝借して、必要な情報を足すようにしました。extrainfo とかいう名前は仮置きだからまあ……。そして node type のあまりの多さにおののいています。

ちなみに、この辺の #define によって「 nd_mid って結局 RNode 構造体のどこにあるんだっけ?」という疑問が解消されます。これめちゃくちゃ便利。見つけられてなかったら死んでた。最高!

ruby/node.h at trunk · ruby/ruby · GitHub

RubyVM::AST を便利に使いたいので gem を作った

github.com

さっと作りました。 rubygems には登録してません(名前が重複してるかすら調べてないや)

経緯

Ruby 2.6.0preview2 から RubyVM::AST モジュールが使えるようになりました。

Ruby 2.6.0-preview2 Released

RubyVM::AST [Experimental] Ruby 2.6 introduces RubyVM::AST module.

This module has parse method which parses a given ruby code of string and returns AST (Abstract Syntax Tree) nodes, and parse_file method which parses a given ruby code file and returns AST nodes.

RubyVM::AST::Node class is also introduced you can get location information and children nodes from Node objects. This feature is experimental. Compatibility of the structure of AST nodes are not guaranteed.

要約:

  • Experimental だよ。互換性とか全然まるっきり全く担保する気がないよ
  • parse, parse_file というメソッドがあって AST を返すよ

こいつは parse すると RubyVM::AST::Node を返します。tree なので子供がいるのですが children と呼ぶと RubyVM::AST::Node | NilClass の配列が返ります。

なんですけど、ちょっとわかりにくいんですよね。children の数は node_type によって固定なんですが覚えられないし、何番目が何かわからないし。ちなみに具体的な対応はこの辺を参照してください

なので雑に node_type 文字列を key にした Hash を返すようにしてみました。わーべんり(べんり?)

RubyVM::AST.parse("1 + 2").children
# => [nil, #<RubyVM::AST::Node(NODE_OPCALL(36) 1:0, 1:5): >]
require 'ast_tools/hash'
RubyVM::AST.parse("1 + 2").children
# => {"node_opcall"=>#<RubyVM::AST::Node(NODE_OPCALL(36) 1:0, 1:5): >}

他にももう少し RubyVM::AST を用いて遊ぶ予定があるのでそのときに使おうと思います


追記

ハイパーそうですねという感じなので使い方を変えました

https://github.com/hkdnet/ast_tools/pull/2

RubyVM::AST.parse("1 + 2").children
# => [nil, #<RubyVM::AST::Node(NODE_OPCALL(36) 1:0, 1:5): >]

AstTools::Hash.convert(RubyVM::AST.parse("1 + 2").children)
# => {"node_opcall"=>#<RubyVM::AST::Node(NODE_OPCALL(36) 1:0, 1:5): >}

# or refinement

module Foo
  using AstTools::Hash
  def self.foo
    RubyVM::AST.parse("1 + 2").children
    # => {"node_opcall"=>#<RubyVM::AST::Node(NODE_OPCALL(36) 1:0, 1:5): >}
  end
end

オフラインリアルタイムどう書く E24 の回答

負けました。ほっとんどのテストケースは通るが4つほど通らない、というのがあるというのが時間内の回答です。

が、終わったあとの懇親会でぼーっと考えてたらあそこじゃね?というところに気づいて解けました。そしてその diff がしょーもない。

とりあえず方針はこんな感じです。

単調増加数は各桁に一定の大小関係があるので、桁間で「いくつプラスになるか」というのを割り振るものだと思えばよい。
この捉え方だとある桁数・進数における単調増加数のパターン数をよくある場合の数に落とせる。具体的には、 b-1個のボール(増加分)をr人(桁数)で分けるような何かである。

↓こんな感じ。

5個のボールを2つの仕切りでわける = 4進数2桁における単調増加数のパターン数

こういうマッピングができる
○|○|○○○ -> 12 (5)
○|○○|○○ -> 13 (5)
○○|○○|○ -> 24 (5)

これは nCk で表わせる場合の数である。

これを使うと b 進数 r 桁で表せる単調増加数のパターン数がわかるので m を超えないような最大の r で桁数が確定。次は r 桁のうち idx 番目を num にしたときの単調増加数のパターン数を調べていって桁を確定させると求める数がわかる。

実行速度はたぶんかなりはやい気がします。

$ ruby test.rb
(略)
ruby test.rb  0.43s user 0.18s system 74% cpu 0.818 total

回答のコードは以下

class Solver
  def solve(input)
    @b, @m = input.split(',').map(&:to_i)
    rank = 1
    count = 0


    loop do
      return '-' if rank > (@b - 1)
      # rank 個の仕切りを n - 1 箇所にいれればよい
      # rank 末尾と n の末尾になんか変なのいれてることに注意
      # → nCrankでよい
      tmp = count_for(n: @b - 1, k: rank)
      break if count + tmp >= @m
      count += tmp
      rank += 1
    end
    # 桁数確定

    idx = 1
    num = 1
    nums = []

    loop do
      t_n = @b - 1 - num
      t_k = rank - idx
      tmp = count_for(n: t_n, k: t_k)
      if count + tmp >= @m
        nums << num
        num += 1
        idx += 1
        break if nums.size == rank
        next
      end
      count += tmp
      num += 1
    end

    nums.map { |e| e.to_s(36) }.join('')
  end

  def count_for(n:, k:)
    raise ArgumentError if k > n

    ret = 1
    k.times do |i|
      ret = ret * (n - i)
    end
    k.times do |i|
      ret = ret / (k - i)
    end
    ret.to_i
  end

  def incr?(num)
    tmp = num.to_s(@b).chars
    return true if tmp.size == 1
    tmp.each_cons(2).all? do |c1, c2|
      c1 < c2
    end
  end
end

なお最終コミットはこちらです ↓

fix · hkdnet/misc@2efdfd7 · GitHub

ほんとしょうもない……。

Swift製webアプリケーションフレームワーク Vapor を読むやつ #3

hkdnet.hatenablog.com

boot 以降にいくか、と思っていたのですが boot 以降よりも middleware まわりのほうがよさそうなのでそちらを読むことにします。

さて、 middleware ですが、とりあえず既存の middleware を読めばいいでしょう。 ErrorMiddleware を読みます。

vapor/ErrorMiddleware.swift at 3.0.2 · vapor/vapor · GitHub

superclass あるいは adopted protocols1 として Middleware, ServiceType を宣言しているようです。Swift は Vapor でしか読んでないので文法事項が普通にわからなくて困りますね。 すげー雑に見ると、 public static func makeService(for worker: Container) throws -> ErrorMiddleware でサービスとしての ErrorMiddleware を返しているようです。その実態は public func respond(to req: Request, chainingTo next: Responder) throws -> Future<Response> として実装されているように見えますね。つまり以下のようになってればよさそうです。

  • スタティックメソッド makeService でサービスをつくる
  • インスタンスメソッド responsd で実リクエストを捌く

では早速適当に middleware をつくりましょう。特定のヘッダがあったときに特定のヘッダを返す、という実リクエスト/レスポンスにあんまり影響を与えないような何かにしておきます。クラス名は適当に MyMiddleware とかにしておきましょう。

/// Sources/App/mymiddleware.swift
import Vapor

public final class MyMiddleware: Middleware, ServiceType {
    /// See `ServiceType`.
    public static func makeService(for worker: Container) throws -> MyMiddleware {
        return try .default(environment: worker.environment, log: worker.make())
    }
    
    /// Create a default `MyMiddleware`.
    ///
    /// - parameters:
    ///     - environment: The environment to respect when presenting errors.
    ///     - log: Log destination.
    public static func `default`(environment: Environment, log: Logger) -> MyMiddleware {
        return .init()
    }

    public init() {
    }
    
    /// See `Middleware`.
    public func respond(to req: Request, chainingTo next: Responder) throws -> Future<Response> {
        return try next.respond(to: req).map { res in
            if req.http.headers.contains(name: "X-NYA-N") {
                res.http.headers.add(name: "X-NYA-N", value: "RESPONSE")
            }
            return res
        }
    }
}

respond 内では req.http.headers を見て分岐しています。X-NYA-N ヘッダがあれば X-NYA-N: RESPONSE というヘッダを返すようにしています。

これを早速使いましょう。 configure.swift の middlewares に追加すればよさそうです。

/// Sources/App/configure.swift
    /// Register middleware
    var middlewares = MiddlewareConfig() // Create _empty_ middleware config
    /// middlewares.use(FileMiddleware.self) // Serves files from `Public/` directory
    middlewares.use(ErrorMiddleware.self) // Catches errors and converts to HTTP response
    middlewares.use(MyMiddleware.self) // 追加

しかしこれだけではエラーになってしまいます。

Run[81340:13566121] Fatal error: Error raised at top level: ⚠️ Service Error: No services are available for 'MyMiddleware'.
- id: ServiceError.make

対応するサービスがねーぞと言われてますね。うーん。DIする機構として Service というのがありそうなのはわかっているのですがいまいち把握できてません。とりあえず ErrorMiddleware は使えているので vapor/vapor 内で ErrorMiddleware に関して検索してみるとこんなんが出てきました。

vapor/Services+Default.swift at 3.0.2 · vapor/vapor · GitHub

services.register(ErrorMiddleware.self) とやってサービスとしても登録していますね。おそらくDIのほうでサービスクラスのリストをもっておいて、ミドルウェアが必要になったときに該当のサービスをリストから探索 → makeService を呼んでサービスのインスタンスを取得、としているのでしょう。MyMiddleware クラスもサービスとして登録してやります2

/// Sources/App/configure.swift
    /// Register middleware
    var middlewares = MiddlewareConfig() // Create _empty_ middleware config
    /// middlewares.use(FileMiddleware.self) // Serves files from `Public/` directory
    middlewares.use(ErrorMiddleware.self) // Catches errors and converts to HTTP response
    middlewares.use(MyMiddleware.self)
    services.register(middlewares)
    services.register(MyMiddleware.self) // これを追加

これで無事立ち上がりました。レスポンスもいい感じです。

~/.g/g/h/HelloVapor ❯❯❯ curl -i localhost:8080/todos
HTTP/1.1 200 OK
content-type: application/json; charset=utf-8
content-length: 2
date: Sun, 13 May 2018 18:57:43 GMT

[]%
~/.g/g/h/HelloVapor ❯❯❯ curl -i -H "X-NYA-N: REQUEST" localhost:8080/todos
HTTP/1.1 200 OK
content-type: application/json; charset=utf-8
content-length: 2
X-NYA-N: RESPONSE
date: Sun, 13 May 2018 18:57:46 GMT

[]% 

service の lookup とかはたぶんこっちのレポジトリなんですがちゃんと追えてないです。また次回かな。

github.com


  1. これまとめてなんていうんだろ。 ref: https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Declarations.html#//apple_ref/swift/grammar/class-declaration

  2. これミドルウェアに登録したときに該当する Service がなかったら asyncRun よりも前で落ちてほしいんだけどなあ

Re: Rubyのdefの後に何を書けるか調べる実験

sinsoku.hatenablog.com

最後のHashが印象的。以下引用。

# no error
def ({}).foo
  puts "foo"
end

# 別インスタンスなのでメソッドは呼べない
{}.foo
#=> (NoMethodError)

引用終了。

さて、別インスタンスなので呼べないというが、まあ呼びたいじゃん?オブジェクト作ってるんだから ObjectSpace から引っ張ってくればええやん?

def show_hash(h)
  if h
    p h
    p (h.methods - ({}.methods))
  else
    puts "nil"
  end
end

def search_object_with_method(name:)
  ObjectSpace.each_object.find { |e| e.methods.include?(name) }
end

def ({}).foo
  $a = self
end

h = search_object_with_method(name: :foo)
show_hash(h)

試してみまして。

$ ruby foo.rb
{}
[:foo]

ok

ついでだから初期化されたやつも試してみまして。

def show_hash(h)
  if h
    p h
    p (h.methods - ({}.methods))
  else
    puts "nil"
  end
end

def search_object_with_method(name:)
  ObjectSpace.each_object.find { |e| e.methods.include?(name) }
end

def ({}).foo
  $a = self
end

h = search_object_with_method(name: :foo)
show_hash(h)

# ここから追記

puts '-' * 20

def ({a: 1}).bar
end

h = search_object_with_method(name: :bar)
show_hash(h)

まあ、出るっしょ。

$ ruby foo.rb
{}
[:foo]
--------------------
nil

nil !?!?!?!?

え、初期化するかどうかで振る舞い違うの!?ヤバくない?って思ったらGCのせいでした。どこにもバインドしてないからしょうがないね。

GC.disable # これを追加

def show_hash(h)
  if h
    p h
    p (h.methods - ({}.methods))
  else
    puts "nil"
  end
end

def search_object_with_method(name:)
  ObjectSpace.each_object.find { |e| e.methods.include?(name) }
end

def ({}).foo
  $a = self
end

h = search_object_with_method(name: :foo)
show_hash(h)

puts '-' * 20

def ({a: 1}).bar
end

h = search_object_with_method(name: :bar)
show_hash(h)
$ ruby foo.rb
{}
[:foo]
--------------------
{:a=>1}
[:bar]

hanachin さんが調べてくれてたけど NODE_HASH が載ってないですね。わざとなのかしら。

Swift製webアプリケーションフレームワーク Vapor を読むやつ #2

hkdnet.hatenablog.com

前回テンプレートの configure まで読んだので boot 以降を読もうかと思いましたが、routesのところを読み損ねていたことに気づいた ので読みます。

https://github.com/vapor/api-template/blob/3df9b5518b510f5959c75ad04c1b51996a75e367/Sources/App/configure.swift#L11

/// Sources/App/routes.swift
import Vapor

/// Register your application's routes here.
public func routes(_ router: Router) throws {
    // Basic "Hello, world!" example
    router.get("hello") { req in
        return "Hello, world!"
    }

    // Example of configuring a controller
    let todoController = TodoController()
    router.get("todos", use: todoController.index)
    router.post("todos", use: todoController.create)
    router.delete("todos", Todo.parameter, use: todoController.delete)
}

まあなんとなく各 path + method の組み合わせについて関数的ななにか(型的には closure: @escaping (Request) throws -> T where T: ResponseEncodable っぽい)を渡していけばいいんだな、と予想ができます。気になるのは Todo.parameter ですね。Todo はモデルのクラスです。Todo.parameter は何を返すのでしょうか。まずは router.deleteシグネチャから確認しましょう。

    @discardableResult
    public func delete<T>(_ path: PathComponentsRepresentable..., use closure: @escaping (Request) throws -> T) -> Route<Responder>
        where T: ResponseEncodable
    {
        return _on(.DELETE, at: path.convertToPathComponents(), use: closure)
    }

path が可変長引数ですね。なので ["todos", Todo.parameter] が path であることがわかります。

convertToPathComponents() の実態をさぐりにいくと / 区切りで flatmap してそれぞれを path の一部として見ていることがわかります。

extension String: PathComponentsRepresentable {
    /// See `PathComponentsRepresentable`.
    public func convertToPathComponents() -> [PathComponent] {
        return split(separator: "/").map { .constant(.init($0)) }
    }
}

extension Array: PathComponentsRepresentable where Element == PathComponentsRepresentable {
    /// Converts self to an array of `PathComponent`.
    public func convertToPathComponents() -> [PathComponent] {
        return flatMap { $0.convertToPathComponents() }
    }
}

だからたぶん router.delete("foo", "bar")router.delete("foo/bar") は同じ。 翻りまして DELETE の形式はおそらく DELETE /todos/:id なので Todo.parameter:id に相当する何かであろうという予想が立ちます。まあ :id のところはただのプレースホルダーというか名前なので実際に使うほうをみてみましょう。

    /// Deletes a parameterized `Todo`.
    func delete(_ req: Request) throws -> Future<HTTPStatus> {
        return try req.parameters.next(Todo.self).flatMap { todo in
            return todo.delete(on: req)
        }.transform(to: .ok)
    }

next...?

    /// Grabs the next parameter from the parameter bag.
    ///
    ///     let id = try req.parameters.next(Int.self)
    ///
    /// - note: the parameters _must_ be fetched in the order they appear in the path.
    ///
    /// For example GET /posts/:post_id/comments/:comment_id must be fetched in this order:
    ///
    ///     let post = try req.parameters.next(Post.self)
    ///     let comment = try req.parameters.next(Comment.self)
    ///
    public func next<P>(_ parameter: P.Type) throws -> P.ResolvedParameter
        where P: Parameter
    {
        return try request._parameters.next(P.self, on: request)
    }

あ、これ parameter の name でとらない形式のやつじゃん……1 request._parameters.next の実際の実装はこんな感じ。

    public mutating func next<P>(_ parameter: P.Type, on container: Container) throws -> P.ResolvedParameter
        where P: Parameter
    {
        guard values.count > 0 else {
            throw RoutingError(identifier: "next", reason: "Insufficient parameters.")
        }

        let current = values[0]
        guard current.slug == P.routingSlug else {
            throw RoutingError(identifier: "nextType", reason: "Invalid parameter type: \(P.routingSlug) != \(current.slug)")
        }

        let item = try P.resolveParameter(current.value, on: container)
        values = Array(values.dropFirst())
        return item
    }

なんかパラメータだけ取りたいんだけど、ってときは resolveParameter のIFを満たす型であればよさそうですね。String とかは Vapor 内で定義されていました。雑に検証すると以下。

    router.get("echo", String.parameter) { req in
        return try req.parameters.next(String.self)
    }
~/.g/g/h/HelloVapor ❯❯❯ curl localhost:8080/echo/foo
foo%
~/.g/g/h/HelloVapor ❯❯❯ curl localhost:8080/echo/foo-dayo-n
foo-dayo-n% 

ちなみに自分で /echo/:foo とか書いても Not Found です。これは String をかいても PathComponent 内では constant 扱いになるから。

    router.get("echo/:content") { req in
        return try req.parameters.next(String.self)
    }
~/.g/g/h/HelloVapor ❯❯❯ curl localhost:8080/echo/foo
Not found% 

routes に関しては 3.0.1 から .catchall とかが入ってるっぽいんですが、これは .anything の後ろにpathがあったときにぶっ壊れてたのをなおすためにいれたようです。

github.com

今日はここまで。


  1. 予想が外れるのもまたコードリーディングの楽しみではありますが