アペフチ

Rustのライフタイムが(やっぱり)分からない

ずっと何もしてなかったのだけどなんかフラストレーション溜まってきたのでRustを何でもいいからやろうかあ! って気分になって、ダイクストラ法を実装してみようかと思った。

取り合えず、Rust 2018のモジュールの仕組みを思い出しながら(Rustのモジュールの使い方 2018 Edition版 | κeenのHappy Hacκing Blog)モジュールとしてダイクストラ法をやる場所を作って、それから部品としてのグラフ、ノード、エッジを作ろうと思った。

のだけど、それがもううまくいかない。現行のソースコードは src/dijkstra.rs なんだけど、 cargo clippy で怒られてしまう。

struct Edge<'a> {
    dest: &'a Node<'a>,
    cost: usize,
}

struct Node<'a> {
    edges: Vec<&'a Edge<'a>>,
    solved: bool,
    label: &'a str,
}

impl Node<'_> {
    fn new<'a>(label: &'a str) -> Node<'a> {
        Node {
            edges: Vec::new(),
            solved: false,
            label,
        }
    }

    fn add_edge_to<'a>(&self, dest: &'a Node, cost: usize) {
        let edge = &Edge {dest, cost};
        self.edges.push(&edge);
    }
}

struct Graph<'a> {
    nodes: Vec<&'a Node<'a>>,
}

pub fn run() -> Result<(), ()> {
    Ok(())
}
% cargo clippy
    Checking rust-algorithm v0.1.0 (/home/kitaitimakoto/src/gitlab.com/KitaitiMakoto/rust-algorithm)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
  --> src/dijkstra.rs:22:21
   |
22 |         let edge = &Edge {dest, cost};
   |                     ^^^^
   |
note: first, the lifetime cannot outlive the lifetime 'a as defined on the method body at 21:20...
  --> src/dijkstra.rs:21:20
   |
21 |     fn add_edge_to<'a>(&self, dest: &'a Node, cost: usize) {
   |                    ^^
note: ...so that reference does not outlive borrowed content
  --> src/dijkstra.rs:22:27
   |
22 |         let edge = &Edge {dest, cost};
   |                           ^^^^
note: but, the lifetime must be valid for the lifetime '_ as defined on the impl at 12:11...
  --> src/dijkstra.rs:12:11
   |
12 | impl Node<'_> {
   |           ^^
note: ...so that reference does not outlive borrowed content
  --> src/dijkstra.rs:23:25
   |
23 |         self.edges.push(&edge);
   |                         ^^^^^

error: aborting due to previous error

error: could not compile `rust-algorithm`.

To learn more, run the command again with --verbose.

こういう所でハマるのは、まさにそのために勉強しているわけなので歓迎なんだけど、それにしても分からん。なんでなんだろう……。

何か教えてくださるという親切な方がいらしたらこちらまでお願いします…… https://gitlab.com/KitaitiMakoto/rust-algorithm/issues
あと、実はこっそりSlackのrust-jpチームにもいます。

Ruby 2.6のRefinementsが使いやすい

EPUB Parser 0.4.1をリリースした( https://kitaitimakoto.gitlab.io/epub-parser/file.CHANGELOG.html#_0_4_1 )。XMLライブラリーを切り替え可能にしているのだけど、そこでOgaも使えるようにしたというリリース。

Ruby 2.7の足音も近付いている昨今ですが、このOga対応中に2.6のRefinementsの使いやすさをすごく実感したので今日はそのことを話したい。

Refinementの用途 - ライブラリー間の差を吸収するアダプター

EPUB ParserではXMLライブラリーをREXMLOgaNokogiriから選べるようになっている。こういうのの実現は、多く、 XMLDocument::REXML のようなアダプターを作ってその中にライブラリーの詳細を隠蔽する。EPUB Parserの方からは共通の XMLDocument のAPIを使って、内部でアダプターがREXMLならREXMLのメソッド呼び出しに変換する、という方法だ。

が、EPUB Parserではそういうラッパーは用意しなかった。直接 REXML::Document とか Oga::XML::Document とかのメソッドを呼び出している。とは言っても、勿論、一々

doc =
  case @adapter
  when :Oga
    Oga.parse_xml(xml)
  when :Nokogiri
    Nokogiri.XML(xml)
  else
    REXML::Document.new(xml)
  end
xpath = "/container/rootfiles/rootfile"
rootfiles =
  case @adapter
  when :Oga
    doc.xpath(xpath)
  when :Nokogiri
    doc.xpath(xpath)
  else
    doc.each(xpath)
  end

などと条件分岐するわけではない。その代わりに用いたのがRefinement、というわけだ。

例えばEPUB Parser内でXPath式に基づいて要素を取得する場合には each_element_by_xpath というメソッドを呼び出すことにしているが、ご存じの通りどのXMLライブラリーにもこういう名前のメソッドは備わっていない。だから各ライブラリーのクラスにこのメソッドを新しく定義するのだけど、それをオープンクラスでやったり prependinclude でやると、EPUB Parserで読み込んだ状態では各XMLライブラリーに未知のメソッドが生えることになってしまう。EPUB Parserを使ってHTMLコンテンツを読み込んで、それを自分の好きなXMLライブラリーでパースすることも割とあると思うのだけど、その時に意図しないメソッドが生えているのは嫌だ。そこで活躍するのがRefinement。 prepend みたいにメソッドを定義したモジュールを読み込ませるんだけど、その読み込みは明示的に using した範囲に限られる。EPUB Parserの内部処理で using EPUB::Parser::XMLDocuemnt::Refinements とかして、そのモジュール内で each_element_by_xpath とか定義してても、ユーザーが自分のXMLライブラリーを使う時にはそんなメソッドは無くなっている。

REXMLとNokogiriの両方を使えるようにする際にこういう仕組みを導入した。今回、0.4.1のリリースでOga対応する時にもこれに則って必要な書くライブラリーを定義していった。特に困ることなく普通にRefinementを使って実装した後GitLabにプッシュするとCIが動く。そしてテストの失敗を報告してくる。手元の開発はRuby 2.6だけでやっていて、2.6用のCIでは当然成功しているんだけど、2.3 - 2.5では失敗していて、これを修正する間に「ああ、Ruby 2.6のRefinementは過去のバージョンと比べて自然に使えるようになってるんだなあ、便利だなあ」と実感した次第だ。

モジュールをrefineできるようになっている。

2.4、2.5と違い、2.3のCIではテストを開始する以前にエラーが発生している。Ruby 2.3のRefinementは、どうやらクラスしか refine できず、 refine Oga::XML::Traversal でエラーになっていた。

今ではモジュールも refine できて便利、と言うか、開発中はできることを疑わなかった。

シンボルをブロック化する時にRefinementが適用される

見出しだけだと何を言っているか分からないと思う。僕も分からない。こういうことだ。

[::Oga::XML::Document, ::Oga::XML::Node].each do |klass|
  refine klass do
    [
      [:document, ::Oga::XML::Document],
      [:element, ::Oga::XML::Element],
      [:text, ::Oga::XML::Text]
    ].each do |(type, klass)|
      define_method "#{type}?" do
        kind_of? klass
      end
    end
  end
end

こうすると、 using すると Oga.parse_xml(xml).element? とかができるようになる。のだけど、Ruby 2.6未満では次のメソッド呼び出しが失敗してしまっていた。

def root
  root_node.children.find(&:element?)
end

children がイテレートするXMLノードに element? なんてメソッドは無い」と言われてしまう。定義しているのになんで? 次のようにするとちゃんと element? メソッドでフィルタリングできる。

def root
  root_node.children.find {|child| child.element?}
end

こういうことができるのか調べようという発想すらなく、自然と

root_node.children.find(&:element?)

って書いていたので、この時にRefinementが適用されるのはRubyistにとって自然なことなんだと思う[1]。2.6はすごく自然だ。

respond_to?でもRefinementが考慮される

上の例で引き続き、

node.respond_to? :root

respond_to? を呼び出すと、2.5までは false が返って来てしまう。2.6はちゃん[2]true が返って来る。素晴らしい。


Refinementはリリースノートをざっと見るだけだとどういう意味を持つのか分からない改善とかあるけど、Ruby 2.6ではRefinementがより自然に使えるようになっていたんだなあ。2.7ではもっとよくなっているのか知ら。楽しみですね。


1. 主語がでかい。僕にとっては、です。
2. 僕にとって、ちゃんと。

Ogaへのパッチが取り込まれた、OgaはXPath評価時にRubyコードへコンパイルしていて興奮した

雑多にプログラミング、集中力の衰えで書いたようにRubyのXMLライブラリーOgaにパッチを投げていたんだけど、製作者のYorick Peterseさんとの幾つかのやり取りの上、マージされた:Improve XPath namespace support。やったあ、と思ってたら、バージョン2.16としてリリースされた。早い。

Rubyコードへのコンパイル

OgaのXPath実装は面白くて、

  1. XPathをパースしてXPathのASTを作る(中ではトークナイズとパースがあるけどここではまとめてパースと呼ぶ)

  2. XPathのASTを元に RubyのASTを作る

  3. RubyのASTを元にRubyコードの文字列を作る

  4. Rubyコードを評価(ざっくり言うと eval)して実行する

となっている。えっ、Rubyコードを作るの!? とびっくりしたけど、まじで作ってる。

OgaではXPathを使う時にはこうやって使う。

require "oga"

xml = DATA.read
doc = Oga.parse_xml(xml)

puts doc.xpath("//foo[@bar]")[0].to_xml
# <foo bar="baz">
#     <qux />
#   </foo>

__END__
<root>
  <foo bar="baz">
    <qux />
  </foo>
</root>

//foo[@bar] というXPath式は「ドキュメント中のどこにあってもいいから foo という要素名で、 bar という属性を持っている(値は問わない)要素全部」を意味する。CSSセレクターだと foo[bar] に相当する。

この doc.xpath の所で、上に書いたステップを踏んでいる。

まず、与えられたXPath式をパースする:

ast = Oga::XPath::Parser.parse_with_cache("//foo[@bar]")
pp ast
# s(:absolute_path,
#   s(:axis, "descendant-or-self",
#     s(:type_test, "node"),
#     s(:predicate,
#       s(:axis, "child",
#         s(:test, nil, "foo")),
#       s(:axis, "attribute",
#         s(:test, nil, "bar")))))

これは抽象構文木になっていて、具体的にはこうなってる。

dc59592524cf10369330e071808fba80

absolute_path はXPathの最初の / で、次の /axis になる。その axis の子ノードが三つあってそれぞれ文字列 "descendant-or-self"type_testpredicate ……という風に読んでいく。

そしてこれを今度は、RubyのASTに変換する。これは Oga::XPath::Compiler.compile_with_cache メソッドの中で行われるんだけど、ASTを組み立てる独立したメソッドがないので、メソッドに中に print を仕込んだ結果がこう。

(block (lit "lambda") [(lit "node"), (assign (lit "variables") (lit "nil"))] (followed_by (assign (lit "original_input") (lit "node")) (followed_by (followed_by (assign (lit "matched") (send (lit "Oga::XML::NodeSet") "new")) (if (or (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Document")) (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Node"))) (followed_by (if (or (or (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Document")) (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Node"))) (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Attribute"))) (followed_by (assign (lit "index2") (lit "1")) (if (or (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Document")) (send (send (lit "node") "root_node") "is_a?" (lit "Oga::XML::Node"))) (block (send (send (send (lit "node") "root_node") "children") "each") [(lit "child4")] (if (and (or (send (lit "child4") "is_a?" (lit "Oga::XML::Element")) (send (lit "child4") "is_a?" (lit "Oga::XML::Attribute"))) (or (eq (send (lit "child4") "name") (string "foo")) (eq (send (send (lit "child4") "name") "casecmp" (string "foo")) (lit "0")))) (followed_by (followed_by (followed_by (assign (lit "pred_var3") (block (send nil "catch" (symbol :predicate_matched)) [] (followed_by (if (send (lit "child4") "is_a?" (lit "Oga::XML::Element")) (block (send (send (lit "child4") "attributes") "each") [(lit "attribute5")] (if (or (eq (send (lit "attribute5") "name") (string "bar")) (eq (send (send (lit "attribute5") "name") "casecmp" (string "bar")) (lit "0"))) (send nil "throw" (symbol :predicate_matched) (lit "true"))))) (lit "nil")))) (if (send (lit "pred_var3") "is_a?" (lit "Numeric")) (assign (lit "pred_var3") (eq (send (lit "pred_var3") "to_i") (lit "index2"))))) (if (send (lit "Oga::XPath::Conversion") "to_boolean" (lit "pred_var3")) (send (lit "matched") "push" (lit "child4")))) (assign (lit "index2") (send (lit "index2") "+" (lit "1"))))))))) (block (send (send (lit "node") "root_node") "each_node") [(lit "descendant1")] (if (or (or (send (lit "descendant1") "is_a?" (lit "Oga::XML::Document")) (send (lit "descendant1") "is_a?" (lit "Oga::XML::Node"))) (send (lit "descendant1") "is_a?" (lit "Oga::XML::Attribute"))) (followed_by (assign (lit "index6") (lit "1")) (if (or (send (lit "descendant1") "is_a?" (lit "Oga::XML::Document")) (send (lit "descendant1") "is_a?" (lit "Oga::XML::Node"))) (block (send (send (lit "descendant1") "children") "each") [(lit "child8")] (if (and (or (send (lit "child8") "is_a?" (lit "Oga::XML::Element")) (send (lit "child8") "is_a?" (lit "Oga::XML::Attribute"))) (or (eq (send (lit "child8") "name") (string "foo")) (eq (send (send (lit "child8") "name") "casecmp" (string "foo")) (lit "0")))) (followed_by (followed_by (followed_by (assign (lit "pred_var7") (block (send nil "catch" (symbol :predicate_matched)) [] (followed_by (if (send (lit "child8") "is_a?" (lit "Oga::XML::Element")) (block (send (send (lit "child8") "attributes") "each") [(lit "attribute9")] (if (or (eq (send (lit "attribute9") "name") (string "bar")) (eq (send (send (lit "attribute9") "name") "casecmp" (string "bar")) (lit "0"))) (send nil "throw" (symbol :predicate_matched) (lit "true"))))) (lit "nil")))) (if (send (lit "pred_var7") "is_a?" (lit "Numeric")) (assign (lit "pred_var7") (eq (send (lit "pred_var7") "to_i") (lit "index6"))))) (if (send (lit "Oga::XPath::Conversion") "to_boolean" (lit "pred_var7")) (send (lit "matched") "push" (lit "child8")))) (assign (lit "index6") (send (lit "index6") "+" (lit "1"))))))))))))) (lit "matched"))))

……これを図にしても読めないと思うのでしないけど、さっきのASTが読めれば「RubyのコードがASTとして表現されてるんだなー」という雰囲気は伝わると思う。あると便利かなと思う知識は、 (lit "lambda") みたいな lit ノードは、Rubyに於けるリテラル、つまりRubyコードとしてはベタで lambda と書かれる物。あと、 (lit "node") とか (list "child4") とかはOgaが用意する変数で、 Oga::XML::Node が入ってる。因みにこのASTを組み立てるところが、パッチを書く上で一番苦労した。

まあそもそもこれを頑張って細部まで読む必要がなくて、このASTを組み立てた直後にRubyコードの文字列にする処理があるので、その結果を貼り付けよう(インデントの調整だけ僕がしてある)。

lambda do |node, variables = nil|
  original_input = node

  matched = Oga::XML::NodeSet.new

  if (node.root_node.is_a?(Oga::XML::Document) || node.root_node.is_a?(Oga::XML::Node))
    if ((node.root_node.is_a?(Oga::XML::Document) || node.root_node.is_a?(Oga::XML::Node)) || node.root_node.is_a?(Oga::XML::Attribute))
      index2 = 1

      if (node.root_node.is_a?(Oga::XML::Document) || node.root_node.is_a?(Oga::XML::Node))
        node.root_node.children.each do |child4|
          if (child4.is_a?(Oga::XML::Element) || child4.is_a?(Oga::XML::Attribute)) && (child4.name == "foo" || child4.name.casecmp("foo") == 0)
            pred_var3 = catch(:predicate_matched) do ||
                                                     if child4.is_a?(Oga::XML::Element)
                                                       child4.attributes.each do |attribute5|
                                                         if (attribute5.name == "bar" || attribute5.name.casecmp("bar") == 0)
                                                           throw(:predicate_matched, true)
                                                         end

                                                       end

                                                     end


              nil
            end


            if pred_var3.is_a?(Numeric)
              pred_var3 = pred_var3.to_i == index2
            end


            if Oga::XPath::Conversion.to_boolean(pred_var3)
              matched.push(child4)
            end


            index2 = index2.+(1)
          end

        end

      end

    end


    node.root_node.each_node do |descendant1|
      if ((descendant1.is_a?(Oga::XML::Document) || descendant1.is_a?(Oga::XML::Node)) || descendant1.is_a?(Oga::XML::Attribute))
        index6 = 1

        if (descendant1.is_a?(Oga::XML::Document) || descendant1.is_a?(Oga::XML::Node))
          descendant1.children.each do |child8|
            if (child8.is_a?(Oga::XML::Element) || child8.is_a?(Oga::XML::Attribute)) && (child8.name == "foo" || child8.name.casecmp("foo") == 0)
              pred_var7 = catch(:predicate_matched) do ||
                                                       if child8.is_a?(Oga::XML::Element)
                                                         child8.attributes.each do |attribute9|
                                                           if (attribute9.name == "bar" || attribute9.name.casecmp("bar") == 0)
                                                             throw(:predicate_matched, true)
                                                           end

                                                         end

                                                       end


                nil
              end


              if pred_var7.is_a?(Numeric)
                pred_var7 = pred_var7.to_i == index6
              end


              if Oga::XPath::Conversion.to_boolean(pred_var7)
                matched.push(child8)
              end


              index6 = index6.+(1)
            end

          end

        end

      end

    end

  end


  matched
end

最後にこれをRubyのブロックでラップして、XMLドキュメントの文脈で実行したら結果が返ってくるという次第。

block = Oga::XPath::Compiler.compile_with_cache(ast)

puts block.call(doc)[0].to_xml
# <foo bar="baz">
#     <qux />
#   </foo>

実行時にXMLドキュメントのDOMツリーを辿りながら、並行してXPath式のASTを辿る(インタープリター型)のかなあと思い込んでいたんだけど、いったん文字列にしてそれを評価するとは……確かに「コンパイル」だな、と驚いたし興奮した。

新たな問題

書いたパッチはこの xpath メソッドにキーワード引数 namespaces を足して、XMLのパース時ではなくてXPathでクエリーする時に任意の名前空間を使えるようにする、という物で、その追加についてREADMEにコメントを書こうと思ったら新たな問題を掘り起こしてしまった。それがこちら:XPath queries using the default XML namespace do not appear to work (any more)

XPathの扱いが、なんと四年も前から間違っていたとのこと……まじか。EPUB ParserでOgaを使えるようにしたいと思っていたのだけど、このバグあると取り入れられないので、この問題も引き続き調べていくことにしよう。

Yorick Peterse

余談だけどYorickさん、RubiniusとかPryとかの作者だったのね。個人的に好きだったウェブアプリケーションフレームワークRamazeの作者でもある(これは知ってた)。パーサージェネレーターを作ったりもしてる。そう思うと「RubyコードをRubyコードで扱う」っていうアプローチも慣れたもんなんだろうな。