放射線耐性Quineの読解

「放射線耐性 Quine (1 文字消しても動く Quine) - まめめも」という頭のおかしい（ほめことば）コードがリリースされていました。

以前「The Qlobe - まめめも」がリリースされた時は、Pythonに移植したら「難読コードを読んでみよう(Python初心者向け解説) - DT戦記(zonu_exeの日記)」という読解エントリーが上がって、書いた本人としても興味深く読ませていただきました。

最近「理解ってなんだろう」ということが気になっていて、人間が理解できていない状態から理解できている状態に変わる過程で何が起きているのかに興味があります。なので自分自身がこの変態コードを理解する過程で何を考えているかを記録してみることにしました。

ちなみに筆者のRubyスキルがどの程度かというと…さっき仕事に使っているVMでyohasebe/wp2txtを使おうとしたらRubyが入っていなくて、apt-get install rubyして再度挑戦したら今度はgemとかいうものが入ってないと言われてapt-getで入らないのでインストール方法をググってましたね。gemは今回初めてインストールしました。(その後ruby1.8を入れてしまってたせいでまたコケた)

        • -

さて、まずはざっと眺めます。いくつか目につくキーワードがあります。

at_exit

at_exitはPythonにもatexitってモジュールがあって、これは「終了時に実行する」って機能なので多分似たようなもんなんだろうな。

rescue

rescueはPythonやJavaでいうところのfinallyだという知識があります(注：後でコレが勘違いだと気づきます）

なるほど、

try:
  do_X()
finally:
  do_X()

という形にすれば「エラーは1箇所」というルールからどっちか片方のdo_Xが壊れててもdo_Xは1回確実に実行されるというわけですかね。だけどもtryなどの周辺部が壊れたり、do_Xが構文上おかしい形に壊れてパースの段階で構文エラーになったら実行どころの話じゃないですねぇ。そこんところどうするんだろう。

##

##と二重にしておくことで、どっちか片方が消えても確実にコメントになるというわけですね。

##'

'abc'##'と言う形にすれば、cの後の閉じ引用符が消えた場合でもコメントの後の引用符までが文字列になることで構文エラーを避けられるのだな。でもこれだけじゃaの前が壊れたらダメだなぁ。どうやって回避しているんだろう。

eval eval

うーわ、メソッドのevalと変数のevalは別の名前空間ということですか。

「eval eval if eval==instance_eval」の行は「文字列evalも文字列instance_evalも書き換わっていなければ文字列evalを評価する」ってことね。このコード自体が壊れていた場合にrescueに入るのかな。

その文字列の中身もあんまりRubyコードっぽくない顔をしているなぁ。

gsub

なるほど、gsubで置換して元のコードを復元するのかな。

python> [(chr(n + 65), chr(92 if n < 1 else n+33)) for n in range(7)]
[('A', '\\'),
 ('B', '"'),
 ('C', '#'),
 ('D', '$'),
 ('E', '%'),
 ('F', '&'),
 ('G', "'")]

文字列リテラル

irb> %\aaa\
=> "aaa"

ひえー、こんな文字列リテラルがあるのか。

  • "%\aaa\"" → バックスラッシュが2つ目の引用符をエスケープするのでvalid
  • %\aaa\"" → バックスラッシュが引用符として使われるので"aaa"と""の結合になりvalid

こうやって開き引用符が消えても死なないようにしているんだな。閉じ引用符が壊れた時は先に説明した##'で守っている。

文字列の中身が壊れた場合は？

rescue

よく見ると"aaa".rescue x rescue 42という形になっているから一つ目のrescueは文字列のメソッドだなぁ。調べよう。Class: String (Ruby 1.9.2)にはrescueの記述がないからObjectに生えているのか？おや、Class: Object (Ruby 1.9.2)にもないぞ？

irb> "".rescue
NoMethodError: undefined method `rescue' for "":String

これはわざとNoMethodErrorを起こして次のrescueで捕まえるのか？

（この辺を調べる過程でrescue==finallyではなくrescue==catchだと気づきました。）

irb> "".rescue x rescue 42
42

しかしそれだと「eval eval if eval==instance_eval」がうまく行かなかった時のセーフティネットはどうやって実現するんだ？てっきり文字列のrescueメソッドを呼ぶと文字列がevalされるのかと思ったがそうではないようだ。

セーフティネット探し

eval != instance_evalの時には後半は実行されないからeval=...以降（以下、この部分を「後半」と呼ぶ）を全部削って実行してみよう。おっと、これでも出力される。

ははー、なるほど。文字列リテラル内へのコードの埋め込みか。

irb> "#{1+1}"
=> "2"

それでat_exitなわけか。このコードに突然変異が入っている場合、ここで実行されてエラーになっては困る。一方、ここに突然変異が入っているということは後半には入っていないわけだから「eval eval if eval==instance_eval」は確実に成功する。だからexit!0が入ってるのか。at_exitの仕様は知らないけど、exit!0したらat_exitで登録されたものが実行されないで即座に終了するんだろう。

rescue

irb> "#{abc}"
NameError: undefined local variable or method `abc' for main:Object

なるほど。前半部のコードに突然変異が入った場合にはat_exitがa_exitになるとか起こりえるので、そこでrescueで握りつぶしていあるんだな。42ってのは単に片方消えて4でも2でもvalidなリテラルになるってことで整数リテラルの都合が良かったんだろうな。

と、ここまでで昼休み1時間を使い切ってしまったので続きは仕事が終わってから。「Pythonでできるのかどうか」に関しては「任意引用符での文字列リテラル」がないところがかなり辛そう。

続き：目的の明確化

「だいたいわかった」ような気になってきたので、ここらで目的を明確にしておきましょう。いままで目的を明確化できていませんでしたが、いくつかそれらしきものがあります。

  • Pythonに移植できるかどうか判断する
  • 「人間が理解できていない状態から理解できている状態に変わる過程で何が起きているのか」の情報収集

前者は「できない」という結論が濃厚。後者はよく考えてみると「どこまでやれば終わりか」が明確でない「悪い目標設定」ですね。「理解できている状態」に変わったことを確認するためには、やっぱ何かを作って検証するのがよいのですけど、少なくともPython実装を作るのはあんまり現実的ではなさそう。じゃあ「解説」を作るのを目標にしようかな。今のところ「だいたいどこが壊れてもエラーにはならない」ぐらいのモヤッとした説明だけど、「どこが壊れてもエラーにならず、必ず壊れる前のソースコードを出力する」を、場合分けしてQEDするのを目標にするかな〜。

あと、ひと通り終わってからこのログを見なおして、僕が理解の過程で何をしているかを検証する感想戦的エントリーも書こう。

eval evalの動作の確認

eval evalが実行されればこのコードが再現されることを念のため確認しておきましょう。

まずはsがこうやって決まります。

s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]

%(...)が文字列リテラルで、それをgsubしてZをevalに置き換えています。置き換えた結果はこう

B%A  C{at_exit{evalGQG##G

}}}ABB.rescue x rescue 42##B

eval=GQG##G

instance_eval=GQG##G

eval eval if eval==instance_eval

次に7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}でA〜Gを置換します。置換テーブルを再掲

[('A', '\\'),
 ('B', '"'),
 ('C', '#'),
 ('D', '$'),
 ('E', '%'),
 ('F', '&'),
 ('G', "'")]

置換結果はこう

"%\  #{at_exit{eval'Q'##'

}}}\"".rescue x rescue 42##"

eval='Q'##'

instance_eval='Q'##'

eval eval if eval==instance_eval

なんでこんなことをしたかというと、特殊な意味を持つ#{...}だの%\...\の2つ目のバックスラッシュだのが発動してしまうのを避けたかったからですね。

最後にQを置換します。s.gsub ?Q,%[(eval q=%(]+q+%[))#]。あれ？このqはどこから…

あ、そうか。Rubyの文字列は破壊的変更ができるんだった。（追記：これは脇道にそれています）

irb> x=y="aaa"
=> "aaa"
irb> y[1] = ?A
=> "A"
irb> x
=> "aAa"

時系列での処理の流れでは、まずq=%(s=%(...))でqに文字列が入り、それからeval qでそれが評価される。

qの中身はこちら

s=%(...).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0

qの中身では同一の文字列の一部をsと名づける。ここでgsub!ではなくgsubが呼ばれることで、新しい文字列インスタンスができている。(追記：これは勘違いです。元から別インスタンス)それからsに対して置換を行っているけど、qとは別のインスタンスになっているからsへの破壊的変更の影響はqには及ばない。最後にQと書かれている部分にqの内容を埋め込んで出力、標準出力をフラッシュしてexitする、と。

後半部破壊調査

さて、まず前半部at_exitの前の#を削って、セーフティネットが動かないようにして、後半部がどう壊れたらどうなるかを見てみましょう。

まずこの条件比較が壊れたらNameError

eval eval if eval==instance_eva
↓
quine.rb:48:in `<main>': undefined local variable or method `instance_eva' for main:Object (NameError)

==が=になっちゃったらtrueになるけど、この場合他の場所はこわれてないのでeval evalで期待通りの挙動をする。

ifやその周辺の空白が壊れてもNameError。evalや周辺の空白が壊れてもNameError。

文字列の中身が壊れても問題ないことは確認済み。

閉じ引用符が壊れたら文字列末尾のコメントが増えてeval==instance_evalが不成立になってセーフティネット行き。

ここの文字列の開き引用符が壊れたら？

instance_eval='(eval ...)#'##'

なんということでしょう。その瞬間evalが発動するので比較を待つまでもなく正常に出力してexitする。

ここの代入が壊れたら？エラーになってセーフティネット…かと思ったら違うや。instance_evalが文字列を引数として受け取ってevalするのでやはり比較を待つまでもなく正常に出力してexit。

変数名が壊れたら比較のタイミングでミスマッチになってセーフティネット行き。

セーフティネット調査

残るはここの部分

"%\  #{at_exit{eval'(eval q=%(s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0))#'##'

}}}\"".rescue x rescue 42##"

このゾーンに突然変異が入ったら、#{at_exit...}で登録された終了時命令が実行される前に、突然変異の入っていないはずの後半部が正常に出力してプログラムを終了させるはず。そうならない例外はこのゾーンに入った突然変異のせいで構文エラーが起きて実行フェーズが始まらない場合と、このゾーンの実行でエラーが起きてat_exitの登録が完了する前に死んでしまう場合。どちらも存在しないことを確認しよう。

まず、qの中身はどうなってもただの文字列だから問題ない。以下のコードで正常にat_exitが登録される。

"%\  #{at_exit{p 12345}}}\"".rescue x rescue 42##"

頭の引用符が消えた時、先に確認したように%\...\が文字列リテラルに化けるので問題なし。

#より前の文字が消えた時、単に文字列の変化だから問題なし。

#や{が消えた時、at_exitが実行されなくなるが、文字列に変わるだけだからエラーは起こらず、後半部が正常に働く。

at_exit{...}が壊れた時、実行時エラーや構文エラーが発生する。しかしこれは先に見たように2つ目のrescueが握りつぶすので問題ない。

irb> "#{at_exi}"
NameError: undefined local variable or method `at_exi' for main:Object
irb> "#{at_exit{}"
SyntaxError: (irb):33: syntax error, unexpected tSTRING_BEG, expecting '}'

at_exit{...}のとじかっこが壊れた時のために1つ余計に付けてある。これは "#{" だと2つ目の引用符が文字列の終了ではなく#{}の中身だと思ってパースを続けてしまい、rescueなどを突き破って構文エラーになるから。

引用符前のバックスラッシュが壊れたら？

"%\  #{at_exit{p 12345}}}"".rescue x rescue 42##"

この場合、".rescue x rescue 42##"が文字列リテラルに化ける。エラーが起こらず後半部が正常に稼働する。閉じ引用符が1個消えた時も同じ。行末まで文字列に化けるだけ。

.rescueのピリオドが消えたら？この場合「エラーを起こす存在しないメソッド呼び出し」だった.rescueが、制御構文のrescueに化ける。結果 "aaa" rescue x となるので文字列リテラルはエラーを吐かないからrescue xが実行されない。

rescueが壊れた場合はNameErrorになって2つ目のrescueが握りつぶす。

xと2つ目のrescueの間の空白が死んだ時には握りつぶせないNameErrorが出るが、その際には正常に登録されているat_exitが先に発動してexitさせるので問題ない。rescueと42の間の空白が消えた時も同様。

"%\  #{at_exit{p 12345}}}\"".rescue xrescue 42##"
↓
12345
quine.rb:1:in `<main>': undefined method `xrescue' for main:Object (NoMethodError)
# at_exitの処理の後に未キャッチ例外によるスタックトレース表示が起きている

42の片方が消えても数値リテラルであることは変わらない。##の片方が消えてもコメントが始まることに変わりない。#の後の"が消えてもコメントだから問題ない。

説明完了。ふー、疲れた。

まとめ

  • しょっぱなからrescueの意味を勘違いしていて普段Rubyに全然触れていないことを如実に表していますね。gem初めて入れた話なんかなくても良かったのではｗ
  • 実はエントリーを書く前はデバッガとか構文木を表示することが必要になるだろうと思ってたんだけども、ならなかった。
  • 1〜2時間で終わらせるつもりだったけど、結局4時間掛かってしまった。あ、確定申告の準備しなきゃいけないんだった…。

追記

ここでgsub!ではなくgsubが呼ばれることで、新しい文字列インスタンスができている。(追記：これは勘違いです。元から別インスタンス)

irb(main):038:0> eval x="y=%[hoge];y[1]=?a"
=> "a"
irb(main):039:0> x
=> "y=%[hoge];y[1]=?a"
irb(main):040:0> y
=> "hage"

gsubに!がついてたりついてなかったりするのは関係なかった。