-
Notifications
You must be signed in to change notification settings - Fork 0
Bug3276
sinfu edited this page Nov 3, 2010
·
8 revisions
アウチ．すでに報告されてた． 以下はこのページで前提とする再現コード．
再帰的テンプレートがエイリアス経由で実体化されると，DMDはそれを"recursive alias declaration"と誤判定してしまう．
template NoStar(T)
{
static if (is(T U == U*))
alias NoStar!U NoStar; // (4)
else
alias T NoStar;
}
alias NoStar NoStarAlias;
alias NoStarAlias!(int***) R; % dmd -o- -c test.d
test.d(4): Error: alias test.NoStarAlias!(int***).NoStar recursive alias declarationエイリアス経由でなく，NoStarを直接実体化すればこの再現コードはうまく動く．
パッチを投稿するには，この問題についてちょっと説明しないといけない．その下書き兼まとめ．
問題は TemplateInstance::findTemplateDeclaration() (template.c 4304) のif文． テンプレートの再帰を検知して，対応するTemplateDeclarationを探している部分．
if (
(ti->name == id ||
ti->toAlias()->ident == id) // <-- this is the cause
&&
ti->tempdecl)tiは再帰している文 (alias Bug3276!(false) Bug3276;) を包み込むテンプレートインスタンス．
この中で，id="Bug3276" がそのテンプレートと一致するかどうか調べている．
しかしtiはエイリアス経由で実体化されて ti->name="W" になっているので，最初のコンディションは満たされない．
すると次のコンディションの ti->toAlias() が実行される． TemplateInstance::toAlias() の中では:
if (aliasdecl)
{
return aliasdecl->toAlias();
}という処理がされている．aliasdeclはeponymous templateの「戻り値」を表すalias文である．
すなわちそれは今処理している alias Bug3276!(false) であり，AliasDeclaration::toAlias()では…
if (inSemantic)
{ error("recursive alias declaration");
aliassym = new TypedefDeclaration(loc, ident, Type::terror, NULL);
}こんなエラーを投げるようになっているため，例のバグが発現する．
--- src/template.c
+++ src/template.c
@@ -4304,11 +4304,7 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
if (s->parent &&
(ti = s->parent->isTemplateInstance()) != NULL)
{
- if (
- (ti->name == id ||
- ti->toAlias()->ident == id)
- &&
- ti->tempdecl)
+ if (ti->tempdecl && ti->tempdecl->ident == id)
{
/* This is so that one can refer to the enclosing
* template, even if it has the same name as a memberこの部分のテストは，id が再帰的テンプレートの「再帰」を表すかどうか確かめている． idの親がTemplateInstanceかどうか調べてtiを得るのは良いのだが，再帰かどうか調べるなら識別子はTemplateDeclarationと比較するべき． 今回のバグのようにTemplateInstanceがエイリアス名で作られた場合，ti->nameは再帰の検査をするのに適当ではない．
パッチで削除された部分のテストではti->toAlias()を使っているが，エイリアスを剥がすのにTemplateInstance::toAlias()は使えない． 実装を見ると，こいつは自分自身のエイリアスを解決するのではなく，テンプレートの「戻り値」を返す． 正しくは，ti->tempdecl から取ってきたTemplateDeclarationの識別子と比較すべき．
エイリアス経由で再帰するようなケースにif文のコンディションが満たされないが，それでもこのパッチは有効 (パッチ前も同じだった)．
このすぐ後で s = s->toAlias(); が実行されているので，エイリアスの解決はちゃんとされる．
パッチはdmd, druntime, phobosのテストをパスした． ただしdmdテストのrunnable/interpret.dは元々壊れてるので通らなかった．
ここから後ろは単なる日記．何が悪いのかさぐってみやう．
- 再帰判定がエイリアスを勘定に入れてない? むしろ逆の結果になりそうなもんだけど．
- DMDのソースをエラーメッセージで検索．
:vim /recursive alias/ *.c - AliasDeclaration::toAlias()から出てる (declaration.c):
if (inSemantic)
{ error("recursive alias declaration");
aliassym = new TypedefDeclaration(loc, ident, Type::terror, NULL);
}- んー，AliasDeclarationのsemantic()処理中に，自分自身にぶつかったと．
- 直接NoStar!(int***)した場合はTemplateDeclaration::toAlias()が呼ばれるから良いのか?
めどが立ってきた．
- NoStarAlias!… のTemplateInstance::semantic()がエイリアスを剥がしてなかったり?
- エイリアスのまま NoStar 内部に突入して，AliasDeclarationの再帰判定に引っかかってるとか．
- template.cを読まないとなぁ．
あまりよく分からない．エイリアス剥がす作業はどこでやるんだ?
- まずはTemplateInstanceの出自から洗おう．
- Parser::parseBasicType() (parse.c) の中で作られてる:
if (token.value == TOKnot)
{ // ident!(template_arguments)
TemplateInstance *tempinst = new TemplateInstance(loc, id);- コンストラクタにジャンプ．この識別子はメンバ変数TemplateInstance::nameにセットされるのね．
- 再現コードの例だと，name="NoStarAlias" ということになる．
- これがTemplateInstance::semantic()でどう解決されてる?
- nameを触ってるのは… semantic()の頭の方で呼び出してるTemplateInstance::findTemplateDeclaration()．
- あんまわからんなぁ．
いろいろいじって確かめよう．
- バグ研究用ブランチに移動してmasterに同期．
% git sw -b invest-bug # * master
% git rebase master- AliasDeclaration::toAlias()にトラップかけて，デバッガでコールツリー出すのが楽．トラップ…
--- src/declaration.c
+++ src/declaration.c
@@ -592,6 +592,7 @@ Dsymbol *AliasDeclaration::toAlias()
//static int count; if (++count == 10) *(char*)0=0;
if (inSemantic)
{ error("recursive alias declaration");
+ assert(0);
aliassym = new TypedefDeclaration(loc, ident, Type::terror, NULL);
}
else if (!aliassym && scope)- ビルド．あー，このmakefileはいじってあって，-gオプション付くようになってる．
% gmake -j4 -f freebsd.mak- tmuxで別ウィンドウへ移動．さてさて…
% gdb dmd
...
(gdb) run -o- -c test.d
...
(gdb) bt
...
#3 0x2832ec76 in __assert () from /lib/libc.so.7
#4 0x080963f4 in AliasDeclaration::toAlias (this=0x285685e0) at declaration.c:595
#5 0x081388d5 in TemplateInstance::findTemplateDeclaration (this=0x28564e00, sc=0x28565040) at template.c:4307
#6 0x0813e4e4 in TemplateInstance::semantic (this=0x28564e00, sc=0x28565040, fargs=0x0) at template.c:3753
#7 0x0813ea30 in TemplateInstance::semantic (this=0x28564e00, sc=0x28565040) at template.c:3683
#8 0x08104833 in TypeInstance::resolve (this=0x28568580, loc={filename = 0x2851d078 "test.d", linnum = 4}, sc=0x28565040, pe=0xbfbfe858, pt=0xbfbfe85c, ps=0xbfbfe854) at mtype.c:5877
#9 0x080fb987 in TypeInstance::toDsymbol (this=0x28568580, sc=0x28565040) at mtype.c:5943
#10 0x08096b8a in AliasDeclaration::semantic (this=0x285685e0, sc=0x28565040) at declaration.c:462
#11 0x0804b005 in StaticIfDeclaration::semantic (this=0x28558f40, sc=0x28565040) at attrib.c:1379
#12 0x0813e7e4 in TemplateInstance::semantic (this=0x28507600, sc=0x28507780, fargs=0x0) at template.c:4012
#13 0x0813ea30 in TemplateInstance::semantic (this=0x28507600, sc=0x28507780) at template.c:3683
#14 0x08104833 in TypeInstance::resolve (this=0x2851e400, loc={filename = 0x2851d078 "test.d", linnum = 10}, sc=0x28507780, pe=0xbfbfe9f8, pt=0xbfbfe9fc, ps=0xbfbfe9f4) at mtype.c:5877
#15 0x080fb987 in TypeInstance::toDsymbol (this=0x2851e400, sc=0x28507780) at mtype.c:5943
#16 0x08096b8a in AliasDeclaration::semantic (this=0x2851e460, sc=0x28507780) at declaration.c:462
#17 0x080f86d5 in Module::semantic (this=0x28501280) at module.c:787
...- へー? #4，#10 のAliasDeclaration::semantic()でthisの値が同じ． このペアが再帰判定 (inSemantic) をトリガーしてるのね．
-
StaticIfDeclaration::semantic()から呼ばれているということは，
再現コードだとNoStarの中にある
alias NoStar!U NoStar;こいつか．
まだ直接 NoStar!(int***) でうまくいく理由が分からない．printfでいくか…．
- assert(0) を消す．
% git co declaration.c - こんなのを仕込む．このコードは，nameが解決されて対応する Dsymbol* s が得られる場面．
--- src/template.c
+++ src/template.c
@@ -4269,6 +4269,7 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
error("template '%s' is not defined", id->toChars());
return NULL;
}
+ printf("** %s: s=%s <%s>\n", toChars(), s->toChars(), s->kind());
/* If an OverloadSet, look for a unique member that is a template declaration
*/- ビルドして検証．
% dmd -o- -c test.d
** NoStarAlias!(int***): s=NoStarAlias <alias>
** NoStar!(int**): s=NoStar <alias>
test.d(4): Error: alias test.NoStarAlias!(int***).NoStar recursive alias declaration- おおっと!? s=NoStarがaliasになっている．これが原因だ．
- まだ何が悪いのか知らないけど，誤って「テンプレートの戻り値」であるalias NoStarに解決されてしまってる． 本当はテンプレート自身template NoStarのほうに解決されないとおかしい．
- その証拠に，再現コードをこう書き換えればバグが発現しなくなる!
template NoStar(T)
{
static if (is(T U == U*))
alias .NoStar!U NoStar; // ドット付けて明示
else
alias T NoStar;
}
alias NoStar NoStarAlias;
alias NoStarAlias!(int***) R; // OK!!- あとは何でNoStarAlias経由だとalias NoStarに解決されてしまうのか調べるだけだ!
- 寝る!
- ふつうのNoStar!(int***)でも同様にalias．これは問題じゃない．
- ドット付けるとバグが抑えられたのは，パーサ段階で (厳密に言えばTypeInstance段階で) tempdeclが解決されてるから． 解決済みなので，findTemplateDeclaration()の問題のあるコードパスに到達しない．
じゃあ何が悪いのよ．
- そもそもどこで問題起こってるかというと…
#5 0x081388d5 in TemplateInstance::findTemplateDeclaration (this=0x28564e00, sc=0x28565040) at template.c:4307
ここ．4307行め．そこにあるのは，まさに「再帰テンプレートで自分自身を参照してるケースの対処」．これがバグってるんだろうなぁ．
/* We might have found an alias within a template when
* we really want the template.
*/
TemplateInstance *ti;
if (s->parent &&
(ti = s->parent->isTemplateInstance()) != NULL)
{
if (
(ti->name == id ||
ti->toAlias()->ident == id) // <--- これ! ここのtoAlias()がトリガーしてる!
&&
ti->tempdecl)
{
/* This is so that one can refer to the enclosing
* template, even if it has the same name as a member
* of the template, if it has a !(arguments)
*/
tempdecl = ti->tempdecl;
if (tempdecl->overroot) // if not start of overloaded list of TemplateDeclaration's
tempdecl = tempdecl->overroot; // then get the start
s = tempdecl;
}
}- tiはAliasDeclarationじゃないから良いだろと思うけど，TemplateInstante::toAlias()にはこんな記述が:
Dsymbol *TemplateInstance::toAlias()
{
...
if (aliasdecl)
{
return aliasdecl->toAlias();
}
...
}aliasdeclというのは，いわゆるeponymous templateの「戻り値」エイリアス．
- どうする? たぶん4307行まわりの再帰判定がエイリアスを勘定に入れられてないのが問題．
問題がはっきりしてきた．
- NoStarAlias!(int***)で生成されるTemplateInstanceには，name="NoStarAlias" がセットされている．
- 例のeponymous判定部分はそれを考慮してない．直接NoStarなら
ti->name == idに引っかかるんだけど，NoStarAlias経由だと撥ねられる． そして次のテストti->toAlias()で自分自身のtoAlias()を呼び出してしまい，aliasdecl->toAlias()に飛んであれよあれよというまに… バグ発現．
TemplateInstance *ti;
if (s->parent &&
(ti = s->parent->isTemplateInstance()) != NULL)
{
// id にはeponymous戻り値の id="NoStar" (再現コード4行目) が入っている．
if (
(ti->name == id ||
ti->toAlias()->ident == id)
&&
ti->tempdecl)
...- この
ti->toAlias()テスト不要じゃないか? 要るかな? - だめだ，消しても直らん．ちゃんと判定するように直さないと．
この部分，色々あった結果ti=thisがセットされている．これはinvariant?
- eponymous再帰しようとしてるなら，必ずthisになるんじゃないかなぁ．
- toAlias()取るの間違ってる気がする．だってTemplateInstance::toAlias()は中身のeponymous aliasdeclを取りに行くでしょ? ここで欲しいのは包み込んでいるtemplate declarationなわけで，ロジックとして間違っている．
- TemplateInstanceが自分自身の本名を知らないとダメだ．親スコープでthis->nameが表すシンボルをsearchすれば良いのか? [←誤]
- 4260行めあたり，ワーキングスコープでnameに相当するシンボルを探す部分:
id = name;
s = sc->search(loc, id, &scopesym);NoStarAlias!(int***)のパスで得られるんは，alias NoStar NoStarAlias; のAliasDeclaration．
だからこの時点でtoAlias()してしまえば，モノホンのTemplateDeclaration (NoStar)が得られる．
id = name;
s = sc->search(loc, id, &scopesym);
if (!s)
{
...
}
printf("search(%s) --> %s <%s>\n", id->toChars(), s->toChars(), s->kind());
s = s->toAlias();
printf(" ==> %s <%s>\n", s->toChars(), s->kind());- でもこれだと動かない…．
search(NoStarAlias) --> NoStarAlias <alias>
==> NoStar(T) <template>
search(NoStar) --> NoStar <alias>
==> NoStar <typedef>
test.d(6): Error: alias test.NoStarAlias!(int**).NoStar recursive alias declaration1度目のsearchは完全にうまくいってる．思い通り． 2度目はエラー… typedefになってるのはDMDの都合．AliasDeclaration::toAlias()で再帰を検出してエラりましたという意味．
- 再帰2段目で，対象スコープscがNoStar内部に変わってしまっている．よって見つかるのはNoStar内部で定義されたeponymous用NoStar．まさにこれはmutual recursionなので例のエラーが出る．
ややこしい．
- 一番最初の実体化
NoStarAlias!(int***)ではsearchの結果が別名定義 (8行目)． - 再帰の実体化
NoStar!Uではsearchの結果が自分自身 (4行目)． - こいつら両方をうまく扱わないといけない．今のDMDの実装では生ぬるい対応しかできてない．
TemplateInstance内部から自分自身の名前を解決しようとするのが間違ってるんでないかなぁ．
- パーサ段階でTypeInstanceに入れといて，名前解決はTypeInstanceに任せれば良いんじゃないか?
- やってみるか．
- んあー，TypeInstanceはちょっと思ってるのと違った．Scratch it!
- どうすっかなぁ．
ti->toAlias()を取るというロジックが間違ってたのなら，そこを直せば良い． 当然じゃないの!
- eponymousの「テンプレート宣言と同名のエイリアス」が問題になっている．
- 例のロジックでやってた処理は「親インスタンスと同名のエイリアス」かどうか調べていた．これは間違っとる．
- 親インスタンスの種になったTemplateDeclarationと同名かどうか調べんといかんのだ．
- というわけでこう修正してみる．diffでかいけど，ほとんど確認用のprintf．
--- src/template.c
+++ src/template.c
@@ -4249,6 +4249,8 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
//printf("TemplateInstance::findTemplateDeclaration() %s\n", toChars());
if (!tempdecl)
{
+ printf("== find tempdecl for %s (%u)\n", toChars(), loc.linnum);
+
/* Given:
* foo!( ... )
* figure out which TemplateDeclaration foo refers to.
@@ -4269,6 +4271,7 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
error("template '%s' is not defined", id->toChars());
return NULL;
}
+ printf("search(%s) --> %s <%s>\n", id->toChars(), s->toChars(), s->kind());
/* If an OverloadSet, look for a unique member that is a template declaration
*/
@@ -4304,11 +4307,9 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
if (s->parent &&
(ti = s->parent->isTemplateInstance()) != NULL)
{
- if (
- (ti->name == id ||
- ti->toAlias()->ident == id)
- &&
- ti->tempdecl)
+ printf(" __ inside template: %s (%u)\n", ti->toChars(), ti->loc.linnum);
+
+ if (ti->tempdecl && ti->tempdecl->ident == id)
{
/* This is so that one can refer to the enclosing
* template, even if it has the same name as a member
@@ -4318,11 +4319,14 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
if (tempdecl->overroot) // if not start of overloaded list of TemplateDeclaration's
tempdecl = tempdecl->overroot; // then get the start
s = tempdecl;
+ printf(" !! got: %s <%s>\n", s->toChars(), s->kind());
}
}
s = s->toAlias();
+ printf(" resolved? --> %s <%s>\n", s->toChars(), s->kind());
+
/* It should be a TemplateDeclaration, not some other symbol
*/
tempdecl = s->isTemplateDeclaration();- 再現コードでテスト!
% dmd -o- -c test.d
== find tempdecl for NoStarAlias!(int**) (14)
search(NoStarAlias) --> NoStarAlias <alias>
resolved? --> NoStar(T) <template>
== find tempdecl for NoStar!(int*) (6)
search(NoStar) --> NoStar <alias>
__ inside template: NoStarAlias!(int**) (14)
!! got: NoStar(T) <template>
resolved? --> NoStar(T) <template>
== find tempdecl for NoStar!(int) (6)
search(NoStar) --> NoStar <alias>
__ inside template: NoStar!(int*) (6)
!! got: NoStar(T) <template>
resolved? --> NoStar(T) <template>- おお! なんかメッセージで埋もれてるけど，エラーは一発も出てない．やったぜ．
- パッチにおしませ．
パッチを作ってみる． なんのこたーない，今の変更からprintfを抜けば良いんだ．
- printfを抜いて…．
% git diff --no-prefix > indirectly-instantiated-recursive-template.patch
% < indirectly-instantiated-recursive-template.patch
diff --git src/template.c src/template.c
index dc83e96..92dbd0f 100644
--- src/template.c
+++ src/template.c
@@ -4304,11 +4304,7 @@ TemplateDeclaration *TemplateInstance::findTemplateDeclaration(Scope *sc)
if (s->parent &&
(ti = s->parent->isTemplateInstance()) != NULL)
{
- if (
- (ti->name == id ||
- ti->toAlias()->ident == id)
- &&
- ti->tempdecl)
+ if (ti->tempdecl && ti->tempdecl->ident == id)
{
/* This is so that one can refer to the enclosing
* template, even if it has the same name as a member- でもこれで終わりじゃーない．
いちばん大事なregressionテスト． このパッチは確かに報告された再現コードを直すけど，動いていたコードを破壊したり，ほかのバグを誘発したりしないか? それをチェックしないとまずい．
- まずは提案中のstd.meta．tmuxでサンドボックス作業してるターミナルに移動…
% dmd -o- -c -unittest std/internal/meta/meta
% _- 通った! std.metaみたいに大量の再帰を含んだTMPコードが通るんだから結構安心な気がする．
既存のテストケースでも試そう．
- dmd，druntime，phobosには (完全ではないけど) それなりにテストケースが揃っている．
- 特にdmdのテストスイートはでかいので，通ればけっこうな安心感がある．TDD教徒のBradに感謝!
- dmdのテストはbashに依存してるから，FreeBSDでは動かんのよ…．
仮想マシンのGentooへ移動．
- FreeBSDから今回のパッチを転送．
% scp -r -P50022 indirectly-instantiated-recursive-template.patch sinfu@localhost:/home/sinfu/dev/dmd/
Password:
indirectly-instantiated-recursive-template.patc 100% 668 0.7KB/s 00:00- こっからはGentoo．
- 今回のパッチをあててDMDをビルド．
$ cd ~/dev/dmd
$ svn up
$ patch -p0 < indirectly-instantiated-recursive-template.patch
$ cd src
$ make -f linux.mak -j4- 新しいDMDを使ってdruntime, phobosもビルド．テストも走らせる．
$ cd ~/dev/druntime
$ svn up
$ make -f posix.mak -j4
$ make -f posix.mak -j4 unittest- つぎはphobos．
$ cd ~/dev/phobos/phobos
$ svn up
$ make -f posix.mak -j4
$ make -f posix.mak -j4 unittest- よーし全部パス!
- あとはDMDのテストスイート．これは順列までテストするので非常に重たい． quick引数をつければ速くなるけど，どうせ暇だし完全テストしとく．
$ cd ~/dev/dmd/test
$ make -j8 # 順列テストが超絶ボトルネックになる．コア数足りなくても-j8は効果的．
...- runnable/interpret でコケた．これはdmd-internalsですでに知られているバグで，今回のパッチは関係ない． touchして問題のテストを飛ばし，続行．
$ touch test_results/runnable/interpret.d.out
$ make -j8
...
... runnable/test44.sh
$ _- 通った! これでかなり自信が付いた．
あとは説明を考えてBugzillaにパッチを投げる． パッチを受け取る側はまっさらで何も知らないのだから，以下の4点は必ず埋めないといけない． これはプレゼン!
- 何が原因で起こった問題なのか
- どうすれば直せるのか
- パッチはどうやって実現したか
- パッチのテストはしたのか
あとは上の方のFixに書こう．