RubyとC言語における文字列リテラルの違い

こちらのブログ(TECS 開発ブログ ruby のシンボルと文字列)で触れられているrubyのシンボルと文字列の違いについでですが、私はRubyとC言語における文字列リテラルの扱いの違いの影響の方が大きいのではないかと思います。

C言語で

char *a = “ABCEDFG”;

char *b= “ABCEDFG”;

とかくと、「AGCDEFG」がstaticな領域に取られて、aとbが同じアドレスを指すようになります。

#C言語の規格を見ていないので、正確ではないかもしれません。同じなドレスをさすことが多いとしておきます。

しかし、Rubyの場合、単に”ABCDEFG”とすると、これはString.new(“ABCDEFG”)と同じことであり、”ABCDEFG”という文字列を持つStringクラスのインスタンスを生成することになります。

p “ABCDEFG”.object_id

p “ABCDEFG”.object_id

と2回書くと、それぞれ異なる値のオブジェクトIDを返します。

最初に書いたC言語の書き方に近いことをRubyで実現するには、シンボルリテラルを使います。

p :ABCEDFG.to_sym

p :ABCEDFG.to_sym

こちらは、同じシンボルリテラルならば常に同じSymbolオブジェクトを指します。

ただし、Symbolオブジェクトは一致するかしないかぐらいしか比較する手段がありません。

#Ruby 1.9ではメソッドが増えているので事情は違っていますが。

Symbolオブジェクトに対して文字列長の大小の比較とか、アルファベット順のソートなどは出来ません

その点から言うと、文字列というよりはC言語でいうポインタとか配列の添え字を用いた比較に近いです。

C言語でもポインタの値自体の大小比較とか、ソートなどは極めて限定された状況でないと意味のある結果は得られません。

Rubyの中でもSymbolクラスは特殊です。

特筆すべきは、Symbol.newはNoMethodErrorになることです。

Symbolオブジェクトを作るには、シンボルリテラルを記述するかStringクラスのto_symメソッド、internメソッドを用います。

SymbolオブジェクトとStringオブジェクトは1対1対応しています。

またそれぞれのクラスにto_str, to_symが定義されています。

したがって、SymbolオブジェクトとStringオブジェクトの間で同値姓をチェックしたいならば、いったんどちらかに変換してから==で比較するという方法を取ることはできます。

# 本来は、比較する対象があいまいにならないようにするべきでしょうが。

これは私見ですが、Rubyで文字列リテラルが毎回異なるStringオブジェクトを生成すること自体を知らない人の方が多いのではないでしょうか。

もっというと、Stringクラスの非破壊的メソッドを使っているのに、「文字列が変更されていない。おかしい!」という質問がくることの方が多いです。

メソッドの返値が新たに生成されたオブジェクトであることを気にしなくても、Rubyプログラミングは出来てしまう、というか、トレードオフとして「安全である」と強調されます。

多分、Symbolがあることを知らない人の方が多いのでは。

また、初級者のレベルでは、「何故Symbolを使う必要があるか分からない」はずです。

結局、Symbolを使おうという人は、Ruby使いの中では明らかに初心者ではないです。

(上級者でない)多くの人にとって、Symbolは知らないし、知っても、使い道が分からない、有難味が分からないがため、使わないのが現状ではないでしょうか。

#ライブラリとか、フレームワークをつくる側になると、無視できない無駄に感じるようになると思います。

JRubyでもtecsgenのテストケースが通るのを確認しました

raccのparser.rbへのとりあえずのパッチ作成に載せた試作パッチを、Linux(Fedora 7)とcgywin(1.5.25)上でJRubyで実行し、tecsgenの配布物に含まれるテストケースが通ることを確認しました。

Javaは、JDK 1.6 update14、JRubyは1.3.1を使用しました。

ただし、それぞれの箇所でいささか工夫が必要でした。

*Linux
tecsgenがCのヘッダファイルを読み込む(typedefで定義された型名や構造体タグ名を認識するため)時に、C処理系の独自の予約語が存在すると、tecsgenはそれを認識で来ません。
これによるパース失敗を避けるため、独自の予約語を読み込み前に削除しています。
具体的にはtecsgenの内部でCプリプロセッサ(あるいはC処理系のCプリプロセス処理機能)を呼び出し、空文字列に置換してから、ヘッダファイルを読み込みます。
具体的にはtecsgenのコマンドラインオプション-Dで空文字列に置き換える文字を指定します。
ただし、この指定が”-D__extension__”とされていたため、Linuxのgcc(4.1.3)では”1″に置き換えられて、コンパイルエラーになりました。
#cygwinではこの指定でも問題が起きませんでした。
#現在公開されているtecsgenは、主にcygwinで動作確認されています。

Linuxでは”-D__extension__=”とする必要がありました。

*cygwin
cygwinでJRubyを実行する場合、環境変数RUBYLIBへのパス名の設定方法に工夫が必要でした。
この工夫は、Rubyの場合は必要ありませんでした。

cygwinでフルパスで指定する場合、/cygdrive/c/のように
ドライブ名を/cygdrive/ドライブ名という指定をすることが
可能です。
しかし、この形式で指定した場合、rubyのスクリプトで
クラスFileのexpand_pathメソッドでフルパスに変換した
場合、
C:/cygdrive/c
と、先頭にドライブ名をつけたにも関わらず、/cygdrive/c
もつけたままであるため、存在しないパスになってしまいました。
これは、cygwinの標準のrubyとか、cygwin中から呼び出した
mswin32版rubyでは、経験しなかったことです。
どこが原因かまでは調べていませんが、cygwin上で、JRubyを
使ってtecsgen.rbを実行して、”ファイルが見つからない”
というようなエラーが発生した場合は、環境変数RUBYLIBの値を
確認してください。
もし、”/cygdrive/c”のような形式であれば、この部分をとり
さったパス名を指定してください。
以下をコマンドラインで実行してもよいと思います。

export RUBYLIB=`echo $PWD | sed ‘s/^\/cygdrive\/.//’`

raccのparser.rbへのとりあえずのパッチ作成

racc 1.2.6のcparseで無限ループ発生せずで、parser.rbとcparseの参照するテーブルの内容が異なるのではないかという予想を立てていましたが、またしてもこの予想は外れていました.
cparseはC言語によるrubyの拡張ライブラリとして実装されてており、参照するテーブルは同一でした.
拡張ライブラリ側で参照する際に、参照する位置がずれたりしないかとも考えましたが、拡張ライブラリのデバッグ用出力を有効にして、parse.rbとcparser.cの両者の出力内容を比較した結果、文法エラーになるトークンを読み込んで、エラーと判定し、エラー回復モードに入るまではまったく同じでした。
違いは、cparse.cがエラー処理として、(仮想的な)エラートークンをシフトするのに対し、parser.rbは文法エラーになるトークンをそのままシフトすることでした。

振り出しに戻ってしまったのですが、よくよくcparse.cを調べてみると、エラー回復モード中に、エラートークンを読み込む処理をする処理がか書かれていました。
それに対して、parser.rbには、該当する処理が存在しませんでした.

そこで、parser.rbに必要な処理を追加すのが、以下に示すパッチです.

ただし、cparse.cでは、(エラー回復モード中のエラー処理には)goto文で飛んできて、(エラー処理が終われば)goto文で(飛んできた所の次の行に)戻っているため、parser.rbにどう書くのが適切かは自信がないです。
また、tecsgenに同梱されているテストケースを実行すると、@racc_state(パーサ内部の状態遷移を管理する配列)がnilになる場合があり、とりあえず動作させるために、@racc_stateがnliの場合には、処理を打ちきるという修正を加えました.

上記の事情を踏まえた上での、ruby 1.8.7に同梱されたraccのparser.rbに対するパッチを以下に示します.

これにより、cparseでなくparser.rbで実行した時でも、テストケースを全て実行できました。
すくなくとも無限ループにはなりませんでした。
#Linuxのruby1.8.7での実行結果です.
#もともとの発端になったJRubyではまだ試していません.

Index: parser.rb
===================================================================
--- parser.rb   (リビジョン 23907)
+++ parser.rb   (作業コピー)
@@ -115,6 +115,10 @@
 
       catch(:racc_end_parse) {
         while true
+#addeb by komianmi
+          break unless @racc_state[-1]
+          break if @racc_state.length < 1
+#end
           if i = action_pointer[@racc_state[-1]]
             if @racc_read_next
               if @racc_t != 0   # not EOF
@@ -294,6 +298,47 @@
             racc_e_pop @racc_state, @racc_tstack, @racc_vstack
           end
         end
+#added by kominami
+        # shiftreduce error token 
+        if act > 0 and act < shift_n
+          #
+          # shift
+          #
+          @racc_vstack.push @racc_val
+          @racc_state.push act
+          @racc_read_next = true
+          if @yydebug
+            @racc_tstack.push @racc_t
+            racc_shift 1, @racc_tstack, @racc_vstack
+          end
+        elsif (act < 0 && act > -(reduce_n)) 
+          #
+          # reduce
+          #
+          code = catch(:racc_jump) {
+            @racc_state.push _racc_do_reduce(arg, act)
+            false
+          }
+          if code
+            case code
+            when 1 # yyerror
+              @racc_user_yyerror = true   # user_yyerror
+              return -reduce_n
+            when 2 # yyaccept
+              return shift_n
+            else
+            raise '[Racc Bug] unknown jump code'
+            end
+          end
+
+        elsif (act == shift_n)
+          racc_accept if yydebug
+          return vstack[0]
+
+        else 
+            rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act);
+        end
+#end
         return act
 
       else

racc 1.2.6のcparseで無限ループ発生せず

<a href=”http://www.northern-cross.info/wordpress/index.php/archives/26″>racc 1.3のcparseで無限ループ発生</a>で、cparseでもエラー回復モードからエラー回復できず、無限ループに陥ったことを報告しました。

1.3.0以外の(別のことが原因で実行できなかった1.3.1, 1.3.を除いて)1.3.*では無限ループになりませんでした.

また、1.3.0の一つ前のバージョンの、1.2.6では無限ループが発生しませんでした.

1.3.0と1.2.6は構造体のメンバに直接アクセスするか、構造体へのポインタを介してアクセスすか程度の違いしかなく、無限ループになるかならないかは、参照するテーブルの違いの可能性が大きいです。

より具体的に言えば、テーブルを作成するメソッドの違いではないかということです。

複数のテーブル間の参照がからんでくるので、テーブルの内容の一がずれていたり指している先がどこか一ヶ所でもずれてたら、その後の参照内容が間違ってしまいます。

実際、1.3.0では、文法エラーとなるトークンを読み込んだとき、文法エラーであるとは判定しています。

しかし、それに対するアクションが定義済みと判断し、エラーとなるトークンをそのままシフト、還元して、最終的に無限ループになってしまいます。

もしアクションを示すテーブルの一つ前の要素をさしていたら、アクションは未定義と判定され、状態を一つ前に戻し、$endを読みこむことになり、エラー回復につながるのですが。

次は、テーブル作成の部分を調べてみます。

racc 1.3のcparseで無限ループ発生

raccのparser.rbとcparseの実装上の違いで、「振る舞いが異なる原因となるところを見つけました」と書きました.
その後、この予想を確かめるべくraccのリポジトリから、どの時点でcparseとparser.rbの処理が異なるようになったか、を

調べたのはhttp://i.loveruby.net/svn/public/racc/trunkです。
以前はcvsのリポジトリを使っていたようでしたが、現在はCVSのリポジトリにはアクセスで来ませんでした。
SVNのリポジトリでは、以下が最も古いログです。
r1611 | 1999-06-30 11:52:10 +0900 (水, 30 6月 1999) | 1 line

ただし、ディレクトリ構成も過去からずいぶん変更されているようで、あるリビジョン以前では、目的とするcparse.cの過去のリビジョンとのdiffをとるのが面倒になりました。

結局、raccの過去のアーカイブから調べたいバージョンを取ってきて、ローカルで展開して比較することにしました。
ログを元に推測が出来る分、当てずっぽうよりはずいぶんマシです.

さて私の予想で、今回も外れた部分があります。
私が注目していたのは、エラー回復モードに入ってから、エラーとなった場合のトークンに、対応するアクションが存在するかしないかを、いろいろ調べて、なければラベルerror_popに飛んでいたところでした。

しかし、racc 1.4まで遡っても、cparse.cでは無限ループになりませんでした.

racc1.4は、エラー判定はするものの、それ以降のバージョンのコードと比較して、判定方法はとてもあっさりしていました。

私としては、あんなにしつこくチェックしているから、エラーの判定漏れがないのかなと思っていましたが、文法エラーの時に、(エラー時のアクションが定義されていなければ)ひとつ前の状態にもどるという方針が(今回のようなエラーに対しては)有効のようです。

バージョンを遡って試してみたところ、racc1.3になってやっとcparseでもエラーになることを発見しました.

ただし、1.3といっても1.3.*すべてを試したわけではないので、もっと絞り込む必要があります.

raccのparser.rbとcparseの実装上の違い

raccのparser.rbとcparseの違いでは、入力に対する振る舞いの違いについてのべました。
その後、両者を比較して、振る舞いが異なる原因となるところを見つけました.

ソースは、ruby 1.8.7のsvnのtrunkの最新版です。

パス: .
URL: http://svn.ruby-lang.org/repos/ruby/branches/ruby_1_8
リポジトリのルート: http://svn.ruby-lang.org/repos/ruby
リポジトリ UUID: b2dd03c8-39d4-4d8f-98ff-823fe69b080e
リビジョン: 23875
ノード種別: ディレクトリ
準備中の処理: 特になし
最終変更者: svn
最終変更リビジョン: 23875
最終変更日時: 2009-06-28 05:11:49 +0900 (日, 28 6月 2009)

なお以下から入手したracc 1.4.6でもparser.rbの該当個所は変更されていませんでした.
http://rubyforge.org/projects/racc/

違いはcparse.cの452行目から始まる以下の関数内での処理にあります。

   452	static void
   453	parse_main(struct cparse_params *v, VALUE tok, VALUE val, int resume)

  (略)

(ここに来るまでに、エラー回復モードになっています)

   591	    /* check if we can shift/reduce error token */
   592	    D_printf("(err) k1=%ld\n", v->curstate);
   593	    D_printf("(err) k2=%d (error)\n", ERROR_TOKEN);
   594	    while (1) {
   595	        tmp = AREF(v->action_pointer, v->curstate);
   596	        if (NIL_P(tmp)) goto error_pop;
   597	        D_puts("(err) pointer[k1] ok");
   598	
   599	        i = NUM2LONG(tmp) + ERROR_TOKEN;
   600	        D_printf("(err) i=%ld\n", i);
   601	        if (i < 0) goto error_pop;
   602	
   603	        act_value = AREF(v->action_table, i);
   604	        if (NIL_P(act_value)) {
   605	            D_puts("(err) table[i] == nil");
   606	            goto error_pop;
   607	        }
   608	        act = NUM2LONG(act_value);
   609	        D_printf("(err) table[i]=%ld\n", act);
   610	
   611	        tmp = AREF(v->action_check, i);
   612	        if (NIL_P(tmp)) {
   613	            D_puts("(err) check[i] == nil");
   614	            goto error_pop;
   615	        }
   616	        if (NUM2LONG(tmp) != v->curstate) {
   617	            D_puts("(err) check[i] != k1");
   618	            goto error_pop;
   619	        }
   620	
   621	        D_puts("(err) found: can handle error token");
   622	        break;
   623	          
   624	      error_pop:
   625	        D_puts("(err) act not found: can't handle error token; pop");
   626	
   627	        if (RARRAY(v->state)->len < = 1) {
   628	            v->retval = Qnil;
   629	            v->fin = CP_FIN_CANTPOP;
   630	            return;
   631	        }
   632	        POP(v->state);
   633	        POP(v->vstack);
   634	        v->curstate = num_to_long(LAST_I(v->state));
   635	        if (v->debug) {
   636	            POP(v->tstack);
   637	            rb_funcall(v->parser, id_d_e_pop,
   638	                       3, v->state, v->tstack, v->vstack);
   639	        }
   640	    }

この中で、ラベルerror_popを指定したgoto文がありますが、これに該当する処理がparser.rbには存在しません。
ラベルerror_popでは、エラーとなったトークンにに対するアクションが見つからない場合、そのエラートークンを読み込まなかったことにして(スタックからpopして)います。

parser.rbではこの処理に飛ぶかどうかの判定をするところがありません。
また、判定できるように参照するテーブルなどがつくられているかどうかも、不明です。
#まだそこまで調べれていません。
#今回の調査のきっかけとなったケースでは、はエラートークンに対するアクションが得られるのですが、そのアクションをとると、最終的に無限ループにおちいってしまいました。

raccのparser.rbとcparseの違い

さらに引き続き(raccのエラー回復モードは頑張りすぎ?tecsgen の Exerb版, Jruby 版の障害について)、raccのparser.rbとcparseの動作の違いを調べています.

昨日は、parser.rbがエラー回復モードで、定義された文法を満たすトークンの並びを得ようとして、(入力が終わっているのに)延々と次のトークンを得ようとして、無限ループに陥っているようだと書きました。
このことを指して「頑張りすぎ」と評していました。

そして、同じ不完全な内容の入力(不完全故に文法エラーになる)に対して、正常終了して文法エラーを報告するcparseは「頑張らない」ようにしているのではないかと予想していました.

今回、cparseを用いて、同じくtecsgen -yを指定してデバッグ表示させて見たところ、以外な結果になりました。

celltype tTaskMain {};

に対して、’}’を読み込むと文法エラーになります。
そしてエラー回復モードに入ります。

ここでcparseの場合、いったん読み込んだトークンを
捨てて、$endというトークンを読み込みます。
その次のトークンとして「}」を読み込みます。
後は、入力の通りにトークンを読み込みます。

エラー回復モードに入ったときに(入力には存在しない)仮想的なトークンを読み込んでいます。

この影響で、必要なトークンが不足しているために発生した文法エラーから回復することができていました。

先日以下の入力なら、parser.rbでも無限ループにはいらないと書きました.

celltype tTaskMain {}};

cparseの場合、エラー回復モード時に、あたかも上記のような入力がされていたかのように振る舞います。

$endが追加されるのは、他の文法エラーになる入力でも確かめてみました。

最初の私の予想(入力の終わりを特別扱いして、頑張らない)は外れていました。
cparseが採用しているエラー回復処理の方針は、どこかで聞いた覚えがあるのですが、思い出せません。またちょっとググってみても分かりませんでした。

(追記)
上の書き方ですと、parser.rbとcparse.soがまるっきりエラー回復モードのやりかたが違っているように受け取られるかも知れません。
しかし、rubyとC言語の違いはありますが、アルゴリズムとしては、(私が今まで調べて、理解した範囲では)どちらも同じに見えます。
動作の違いは、微妙な判定条件の違いとか、参照するテール(テーブルはそれぞれ用に作成されます)の内容の違いによるのではないかと感じています。

Reblog this post [with Zemanta]

tecsgen の Exerb版, Jruby 版の障害について

TECS 開発ブログの記事「tecsgen の Exerb版, Jruby 版の障害 (06/21)」、「tecsgen の Exerb版, Jruby 版の障害(続き) (06/24) 」 において、TECSジェネレータの障害が報告されています.

TECSジェネレータとは、TECSにおいてコンポーネントの定義、組み合わせを指定したファイルであるCDLファイル(拡張子が「.cdl」であるテキストファイル)から、コンポーネントを実現する部分のCソースコードを自動生成します.また、コンポーネントが提供する機能(これは個々のコンポーネントの作成者がコーディングする必要があります)のCソースの雛形も生成します.

このTECSジェネレータは、Rubyで書かれています。

より具体的に言うと、CDL(Component Description Language)という言語をパースするためにRubyでかかれたパーザジェネレータRaccを用いています.

これがJavaで実装されたRuby、JRubyで期待した動作をしない(Out Of Memoryが発生する)という報告があったことが発端でした。

この問題に対して、私も調べて見ました。

今回は、Linux(Fedora 7)で行いました。

1.まず、問題を再現させるために、Rubyの標準ライブラリのRaccそのままではなく、一部手を加えたものを用いま す。

cp /usr/lib/ruby/1.8/racc/parser.rb ~/lib/ruby/racc

export RUBYLIB=~/lib/ruby/racc:$RUBYLIB

~/lib/ruby/racc/parser.rbの40行め、モジュールRaccの中のクラスParserに対する機能追加の部分で、以下が四杯するように変更する

require ‘racc/cparse’ -> require ‘xracc/cparse’

2.Raccのデバッグ機能を用いるため、デバッグ用の出力を行う、デバッグ用パーザを生成します。

TECSジェネレータのMakefileにはデバッグ用パーザを生成する定義がありますが、通常のターゲットでは生成されません。そのため、以下のようにターゲットを指定します。

make yydebug

3.問題が発生するテストケースのCDLファイルが存在するディレクトリに移動し、TECSジェネレータ(tecsgen)のオプション-yを指定して実行する。

tecsgen -y error-7.idl  2>&1 | tee  error-7-2.txt

オプション-yはTECSジェネレータにRaccのデバッグ用パーザを読み込むことを指定します。

また、デバッグがしやすいように、~/lib/ruby/racc/parser.rbにデバッグ用出力を追加しておきます.

このようしてTECSジェネレータを実行させて見ました.

結果は以下のとおりです.

1) tok=CELLTYPE
[ 0 45 ]
2) tok=IDENTIFIER
[ 0 45 101 ]
reduce  IDENTIFIER(2) –> celltype_name(214)
[ 0 45 102 ]
3) tok={
[ 0 45 102 149 ]
4) tok=}
[ 0 45 102 149 214 ]
reduce  “}”(76) –> celltype_statement(219)
[ 0 45 102 149 229 ]
reduce  celltype_statement(219) –> specified_celltype_statement(218)
[ 0 45 102 149 228 ]
reduce  specified_celltype_statement(218) –> celltype_statement_list(215)
[ 0 45 102 149 223 ]
6) tok=;
[ 0 45 102 149 223 214 ]
7) tok=nil
[ 0 45 102 149 223 214 ]

(これ以降、以下の部分の繰り返し)

reduce  $end(0) –> celltype_statement(219)
[ 0 45 102 149 223 229 ]
reduce  celltype_statement(219) –> specified_celltype_statement(218)
[ 0 45 102 149 223 347 ]
reduce  celltype_statement_list(215) specified_celltype_statement(218) –> celltype_statement_list(215)
[ 0 45 102 149 223 ]
shift   $end
[ 0 45 102 149 223 214 ]
error-7.cdlは文法エラーの場合のテストケースです。

本来トークン3とトークン4の間にセルタイプの定義が存在すべきですが、それがない場合のテストをするものです。

ですから、トークン3の次にトークン4が来た時点で構文エラーになるべきはずです。

しかし、逆にトークン4をセルタイプの定義と(パーザが)判断しているため、その後のトークン(また、ファイルの終わりに到達しても)が来ても無限ルールに陥ってしまっているのではないでしょうか。

racc/parserとrac/cparseの違いは、まだ調べていません。

同じ文法テーブルを使用しているなら、racc/cparseでも無限ルールに陥っても不思議ではありません.

現段階の仮説の一つは、racc/cparseが(パーザの)入力の終わりを特別扱いして、処理を打ちきっているのではないかいうことです。

でもこの仮説が真の場合でも、racc/cparseの方がが予期せぬ入力に対して柔軟な対応をしてくれるということでしかありません。

私の見る限り、racc/parserは、文法テーブルの指定通りに動作してると思います。