Rのオブジェクト指向について調べていて、S3はlistだという表現が比喩なのかlistを使って実装されているのか気になった。ついでにS4クラスなどの実装も軽く調べておく。

1. R本体コードのダウンロード

https://cran.r-project.org/から普通にダウンロードする。githubにホストされているわけではなさそうなのでブラウザで見るだけ、というのは難しそう。

2. doxygenでコールグラフを生成する

今回は.Rファイルがインタプリタで評価され、Cの関数が呼び出されるまでの流れを知れば理解したことと考えて作業していく。ソースを眺めていると、RのオブジェクトはSEXPという型のポインタで管理されていることが分かる。関数の呼び出しを見ると全てSEXP型だったりするので変数の命名を分かっておくと便利。R's C interface · Advanced R.が分かりやすい。grep -r --include='*.[ch]' \"class\"などとして検索すると、

Rmain.cのRf_mainloopが実行されるが、defineマクロでmainloopから定義されている。
src/main.cでmainloopは定義されていて、setup_Rmainloopとrun_Rmainloopを実行する。
…
src/names.cのR_FunTabという配列で組み込みのキーワード類とCの実装は対応付けられている(例えばclass(a)<-だとR_do_set_class)

ことが分かる。do_set_classなどの関数がmainから順序だって呼び出されることでRは実行されると考えられる。include/Defn.hに#define PRIMFUN(x) (R_FunTab[PRIMOFFSET(x)].cfun)とある。表現は正しくないかもしれないが、このマクロを呼び出す関数とmainまでのコールグラフを見れば良いだろう。これ以降は手作業だとつらそうなので以前使ったことのあるdoxygenで可視化して作業する。

マクロのままだとコールグラフに含まれないので、#define PRIMFUN(x) (R_FunTab[PRIMOFFSET(x)].cfun)をSEXP PRIMFUN(SEXP x) {return R_FunTab[PRIMOFFSET(x)].cfun}に書き換える。

Doxyfileを書いてdoxygenを実行するとdoxygen/htmlの中にdotファイルが生成される。

参考
- ソースコードを読むための技術
- cflowとかbisonを利用するのもありかも

3. dotファイルの解析

cgraph.dotとicgraph.dotに出てくるノードをたどる(参考: Doxygenで生成されるdotファイルの種類 - tak0kadaの何でもノート)。グラフ用のライブラリとしてigraphとnetworkxが有名らしい。networkxは全体がpython実装、igraphは半分がcで実装されている。networkxの方が実行速度が遅そうだったがドキュメントが良かったので実行してみた。

3.1 解析コード

pydotplusにバグがあるのでpydotplus.__file__でディレクトリを確認したらhttps://github.com/CantemoInternal/pydot/commit/8adab7bac6d42dee0bd7caebca4f2870741d104aを参考にpydotplus/parser.pyを修正する。

import glob
import pydotplus as pdp
import networkx as nx
import matplotlib.pyplot as plt

dot_paths = glob.glob('*.dot')
dot_paths_c = [] # 呼び出し
dot_paths_ic = [] # 呼びだされ
for p in dot_paths:
    if 'cgraph' in p:
        if 'icgraph' in p:
            dot_paths_ic.append(p)
        else:
            dot_paths_c.append(p)

#if len(dot_paths_c) != len(dot_paths_ic):
#    raise ValueError("dot_paths_c and dot_paths_ic must be the same length")

def read(dot_paths):
    data = []
    for p in dot_paths:
        with open(p) as f:
            data.append(f.read())
    return data

def parse_dot(DG, data):
    add_edge = DG.add_edge
    for d in data:
        rawG = pdp.parser.parse_dot_data(d)
        # get_label=>'Node1', get_name=>'main'のような対応付けがある
        node_dict = {}
        for n in rawG.get_nodes():
            if n.get_name() != 'node' and n.get_name() != 'edge':
                node_dict[n.get_name()] = n.get_label()[1:-1]
        for e in rawG.get_edges():
            # get.source()では名前'Node1'が返るのでラベルに変換して登録する
            add_edge(node_dict[e.get_source()], node_dict[e.get_destination()])

# 有向グラフ
DG_c = nx.DiGraph()
data_c = read(dot_paths_c)
parse_dot(DG_c, data_c)

DG_ic = nx.DiGraph()
data_ic = read(dot_paths_ic)
parse_dot(DG_ic, data_ic)

# 無向グラフに変換する
G_c = DG_c.to_undirected()
G_ic = DG_ic.to_undirected()
if sorted(G_c) != sorted(G_ic):
    raise ValueError("G_c and G_ic must have same nodes and edges")

# テスト用コード
# fig = plt.figure()
# ax = fig.add_subplot(121)
# nx.draw(DG_c, ax=ax)
# ax = fig.add_subplot(122)
# nx.draw(DG_ic, ax=ax)
# plt.show()

# mainとPRIMFUNの最小経路を調べる
# ['mainloop', 'setup_Rmainloop', 'eval', 'PRIMFUN']
print(nx.shortest_path(DG_c, source='mainloop', target='PRIMFUN')) 

# 他の道を探してみる
# 結果は次のセクション
for path in nx.all_simple_paths(DG_c, source='mainloop', target='PRIMFUN', cutoff=6):
    print(path)

# 一応プロットしてみる
# nx.draw_spectral() # 収束せず
pos = nx.spring_layout(DG_c)
nx.draw_networkx_nodes(DG_c, pos, node_size=9,node_color='r')
nx.draw_networkx_edges(DG_c, pos, width=0.05)
plt.show()

# 今後このスクリプトを実行したくないので結果を書き出す
import json
from networkx.readwrite import json_graph
data = json_graph.node_link_data(DG_c)
with open('R_callgraph.json', 'w') as f:
    json.dump(data, f)

(追記: 作成したjsonファイルをhttps://github.com/tak0kada/playground/tree/master/R_callgraphアップロードした)

テスト用の小さいソースコードでは1秒もかからなかったが、Rのソースコードは大きいため遅い。グラフの可視化もこのサイズのネットワークだと厳しい。(Doxygenの方でコールグラフの深さを制限したらもう少し改善するかも)結局mainloopからPRIMFUNまでは最短たったの2ホップで、mainloop→setup_Rmainloop→eval→PRIMFUNと呼ばれることが明らかになった。

3.2 呼び出し関係の追跡続き

上のnx.all_simple_paths(DG_c, source='mainloop', target='PRIMFUN', cutoff=6)を実行した結果、

['mainloop', 'setup_Rmainloop', 'init_signal_handlers', 'onsigusr1', 'R_run_onexits', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_LoadProfile', 'R_ReplFile', 'PrintValueEnv', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_LoadProfile', 'R_ReplFile', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_LoadProfile', 'R_ReplFile', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'PrintWarnings', 'endcontext', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'PrintWarnings', 'endcontext', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_ReplFile', 'PrintValueEnv', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_ReplFile', 'PrintValueEnv', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_ReplFile', 'PrintValueEnv', 'R_FindNamespace', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_ReplFile', 'PrintWarnings', 'endcontext', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_ReplFile', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_ReplFile', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'warning', 'warningcall', 'vsignalWarning', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_InitialData', 'R_RestoreGlobalEnv', 'R_RestoreGlobalEnvFromFile', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'InitNames', 'installFunTab', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'InitNames', 'installFunTab', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'InitNames', 'R_initialize_bcode', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'InitNames', 'R_initialize_bcode', 'bcEval', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'check_session_exit', 'R_CleanUp', 'R_dot_Last', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_init_jit_enabled', 'loadCompilerNamespace', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_init_jit_enabled', 'loadCompilerNamespace', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_init_jit_enabled', 'checkCompilerOptions', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_init_jit_enabled', 'checkCompilerOptions', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_init_jit_enabled', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_init_jit_enabled', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'InitTempDir', 'errorcall', 'vsignalError', 'eval', 'PRIMFUN']
['mainloop', 'setup_Rmainloop', 'R_Suicide', 'R_CleanUp', 'R_dot_Last', 'eval', 'PRIMFUN']
['mainloop', 'run_Rmainloop', 'check_session_exit', 'R_CleanUp', 'R_dot_Last', 'eval', 'PRIMFUN']
['mainloop', 'run_Rmainloop', 'R_ReplConsole', 'Rf_ReplIteration', 'PrintValueEnv', 'eval', 'PRIMFUN']
['mainloop', 'run_Rmainloop', 'R_ReplConsole', 'Rf_ReplIteration', 'eval', 'bcEval', 'PRIMFUN']
['mainloop', 'run_Rmainloop', 'R_ReplConsole', 'Rf_ReplIteration', 'eval', 'PRIMFUN']
['mainloop', 'run_Rmainloop', 'end_Rmainloop', 'R_CleanUp', 'R_dot_Last', 'eval', 'PRIMFUN']

PRIMFUNはevalかbcEvalのあとに呼ばれること、mainloopとPRIMFUNの間ではevalが直接呼ばれる場合とREPL経由で呼ばれる場合、その他の場合に分けられることが分かる。

4. さらに調べるには

大きいコードで構造体の意味などをコードだけで把握するのは今の自分には厳しい。R Internalsは公式のドキュメントなのでこちらに目を通す。(http://www.slideshare.net/Nikoriks/r-5065138を眺めてからの方が良いかもしれない)

tak0kadaの何でもノート

発声練習、生存確認用。

Rの関数コールグラフ