LNK1248: イメージ サイズが最大許容サイズ (80000000) を超えています

ゼルコバの木の基本データはカードリンクテーブルと結婚リンクテーブルという2つの固定サイズのテーブルとして管理されている.その管理方式はゼルコバの木の長い開発史の中でなんども変遷してきた.テーブルにはデータオブジェクトへのリンクが格納され,「参照番号」と呼ぶフィールドでレコードを一意に識別している.当初はテーブルを全スキャンする方法でレコードの検索を行っていたが,レコードの追加・削除によってたびたび穴あきの状態になるのでテーブルの前詰めを行うようになった.現在は「テーブルの前詰め」は廃止され,代わりに「ルックアップテーブル」を使った管理に変更されている.これにはUNDOの導入・整備が進んだことなども関係しているのではないかと思われる.

参照番号=レコード番号という関係が維持できれば,テーブルにもっとも効率的にアクセスできるので,その方向に向かっていた時期もあったが,従来方式との互換性などの問題もあり,徹底することはできなかった.参照番号をシステムが任意に決定できていたころはそれでもなんとかなったのだが,コラッツ特注版で「隣接リストのインポート」という機能を導入したことで,大幅な見直しが必要になってきた.通常はオブジェクトが生成された時点ですでに「参照番号」の割当てが決まっているが,隣接リストのデータは「参照番号」を持っていないので,すべての関係を「名前」の参照関係から割り出さなくてはならない.

この問題に対処するために,「ハッシュ」という技法が導入された.「ハッシュ関数」はテキストをある固定長の配列インデックスに変換する関数で,生成される「ハッシュ値」が適当に分散するようなものである必要がある.ハッシュはデータを「辞書的に管理する技法」として広く用いられている.「隣接リスト」は任意のラベル付きグラフを扱うことができるが,ノードに番号を割り当てるというのがもっとも一般的なので,「名前」を「整数」に変換し,その下位ビットを固定長の2進数として切り出すことでハッシュ値の代用としている.ハッシュ値がテーブルサイズより小さいものであれば,それをそのままレコード番号(配列インデックス)として採用することができる.

その位置がすでに使われている場合(ハッシュ衝突)には,テーブルを上方に検索して空き位置を見つけて,それをレコード番号とし,その値を「参照番号」として割り当てる.この方式では,「参照番号=レコード番号」という理想型をつねに実現することができる.ただし,その参照番号がテーブル上に存在しないことを確認するためには,全テーブルをスキャンする以外ない※.この意味では「最善」ではないかもしれないが,「最適」であるとは言えるのではないだろうか?細部を残して実装はほぼ完了しているが,デスクトップ上にある「CollatzTest.G.ADL」というサンプルの描画には疑問がある.

※もし,「参照番号=レコード番号」がつねに成立しているのであれば,全スキャンするまでもなく一発で判定できる.「全スキャン」が必要となるのは,「参照番号=レコード番号」がまだシステム的に確立していないか,ないし,過去データとの互換性の問題と考えられる.

このサンプルが「木」というよりは「ブッシュ」のようなものになってしまうのは,このファイルに含まれるカードの一部が表示しきれていないためではないかと考えられる.これを確認するために,テーブルサイズを0x2000から0x4000に拡大してみたところ,「LNK1248: イメージ サイズ(82390000) が最大許容サイズ (80000000) を超えています」のエラーになった.⇒カードテーブルサイズを12000, 結婚テーブルサイズを9000に設定して読み取りは可能になったが,まだテーブルオーバーフローが163件発生している.すべてカードデータで,結婚リンクはカバーできているが,CARDLINK::SortMarriagePageで「兄弟順位子ども数オーバー 」という「データ不整合エラー」が8件発生している.

そのまま続行して,MainExperiment→ FoldingChannelsでスタックオーバーフローが発生する.コラッツ特注版ではノード対オブジェクトは扱わないので,この関数をパスするように暫定修正して,今度はTreeView::MakeAbsolute→ ResetAbsoluteでスタックオーバーフローが起きた.ゼルコバの木ではすべてのオブジェクトはTREEVIEWをルートとする「木」を構成している.系図木の本体を構成するTRIBEBOX, NAMEBOX, MARGBOXなど通常の描画オブジェクトは高さで最大2168の範囲に収まっているが,その後ろに世代枠オブジェクトが直列に接続して長いチェーンになっていた.このチェーンの長さは6899を超えるもので,これがスタックオーバーフローの原因となっている.

世代枠オブジェクトは各世代ごとに配置され,その世代に属するオブジェクトが占める矩形領域を計算するために用いる.世代枠を世代順につないで管理するための世代枠リストには,①基本世代枠リストと②系列世代枠リストの二種があり,それぞれ,それらを管轄するTREEVIEWとTRIBEBOXに接続している.すべての描画オブジェクトは描画リストに接続することによって相対的な位置決めを行っているので,世代枠リストは座標計算には関わりがない.世代枠自体は計算結果を受け取るだけの完全に受動的な立場なので,計算自体はその世代枠がどこに接続されているかには影響しないため,世代枠がこのような変則的な状態にあることがまったく認識されていなかった.

いずれにしても,初歩的な欠陥と考えられるので仕立て直ししなくてはならない.不審なのは,このチェーンの先頭世代枠がNAMEBOXに接続しているように見えることだ.サンプルがちょっと大き過ぎて持て余すところだが,不良の要因は単純なので(極小反例サンプルを求めることなく)このまま続けることにしよう.先頭世代枠は系列先祖ノードの#424347 4549(0)に接続している.これは始系列の先祖ノードだ.とりあえず,これをTREEVIEWに繋ぎ変えてみよう.系列枠はTREEVIEWの右枝に接続しているはずだから,左枝は空いているはずだ.かなり初期のバージョンでは世代コンテキストという描画オブジェクトがあってその下に世代枠を接続するようになっていたが,現在は省かれている.

世代枠リストは系統並び替えのたびに再構築されているので,多分系統並び替えの冒頭でやっているはずだ.TRIBELIST::BuildGeneListでは,基本世代枠リストの先頭世代枠はTREEVIEWに接続されている.このオブジェクトは#804687で,問題の世代枠#805131とは異なる.おそらく,この世代枠は基本世代枠ではなくて,系列世代枠なのだろう.⇒現行方式には明らかに大きな欠陥がある.たとえば,

  • 系列枠がNAMEBOX(優先実ノード)に繋がっているため,描画リストが「木」というより,一本のチェーンのように数珠つなぎになっている
  • すべての世代枠が途切れのない一本のチェーンになっている

これまでは高々数百点のサンプルしか扱って来なかったため,これらの欠陥が表面化することはなかったが,一万点を超えるようなサンプルでは隠せない.描画リストは内部的にはYリストと呼ばれているが,その名の通り右枝と左枝の二方向に分岐した二元木を構成する.系図木を構成するために二元木というプリミティブな構成を選択した理由は,右枝をそのノードの内部構造(部分木)とし,左枝には同位ノードを接続するようにすると,二元木を使ってごく自然に多元木を表象することができるからである.最大枝数が固定した多元木よりフレキシブルに任意の木を構成できると考えられた.(とは言え,Yリストは隠蔽リスト呼ばれるもうひとつの分岐を持っているので,実際には三元木である

当初の系図木には世代枠という要素は含まれておらず,主に結婚枠と人名枠のみから構成され,頂点に特殊オブジェクトとして系図木(TREEVIEW)というオブジェクトがあるという単純な構成だった.系図木上で結婚枠と人名枠は,人名枠→ 結婚枠→ 人名枠→ のように交互に現れるから,系図木は2色で色分けすることのできる二部グラフと考えることもできる.画面上では人名枠は結婚枠内の要素となるから,図式的には系図木は結婚枠という要素のみからなる「結婚木」であると見ることもできる.先祖ノード(とその配偶者)だけは例外的に結婚枠の中に入っていないが,これはいま考えると敗因だったような気もする.⇒おそらく,この「コラッツ特注版」の挑戦が完結した時点でここに戻ることになると思う.「コラッツ特注版」は「単純な木」であり,「結婚木」も「単純な木」と考えられるから,「系統並び替え」を「もっとも単純なトポロジーソート」として再編成できるはずだ.

世代枠は基本的に計算結果を記録する場所でしかないので,描画リスト(という名前の木)から世代枠を完全に外してしまうということも考えられなくもない.ゼルコバの木ではすべての描画要素は描画リスト上にあり,また描画リスト上にある任意のオブジェクトは描画可能だが,「世代枠を描画する」こともあるというのが問題をややこしくしている.描画リスト上にあるノードを「無視する」ということは可能だろうか?もし,それが可能なら,現状で対処できるということにもなるのだが…⇒そういうことはありそうな気がする.やってみよう.⇒できた!

image

ただし,最後にメモリ不足が発生している(バックアップ中).⇒バックアップを止めても状況は変わらない.少し拡大してみよう.

image

このADLは生成時のテーブル上限までの行数を持っているが,実際にはそれを上回るデータを抱えている.コラッツ木生成ツールでは行数で管理できると思っていたようだが,そういう訳にはゆかないようだ.しかし,検証テストで生成される隣接リストに含まれるノード数を正確に数えるのはかなり難しい.検証テストでは,ルート1→奇数Nまでの経路に含まれる枝を拾い出しているので,大量の重複が発生し,それを整理してまとめたものを出力しているが,基準となっているのは最左列のノード番号だけで,それ以外の右側の列に含まれるノードに関してはどのような統計も取っていないためだ.それをやろうとすれば,ほとんどグラフを実際に生成するのと同等のコストが掛かってしまうので,実際的ではない.⇒このサンプルの出所だけは突き止めておこう.1~1000では1595点のグラフが生成される.1~3000では4720点サンプルだ.1~4000では…エラーが出た.

image

CollatzTree.G.ADLをインポート→アプリ終了でエラーが出た.CollatzTree.G.ADLで「絶対座標系で不正原点」というエラーが起きている.障害が起きているのは世代枠オブジェクトだ.

#19939 g GENEBOX 19939 Bobject::getorigin route=#19932 ▲【103 GENEBOX 19932】

これは仕方ないのではないだろうか?上記の1~4000の隣接リストを開発環境で開いて,エラーなしで描画できた.コラッツ木ツールから起動されるZTアプリはバージョンが古いためだろう.「世代枠は絶対座標系変換から除外@22020428」でエラーの出力を止めた.

1~4000では登録カード数11999点,結婚数8999点というファイルが生成されたが,テーブルオーバーフローが232件発生している.従って,本来なら12231点のカードが出力されたものと思われる.結婚テーブルのオーバーフローも大量に発生し,データ不整合が起きている.⇒カードテーブルサイズを13000,結婚テーブルサイズを10000にしてみよう.⇒起動時にEEFileLoadException 例外が発生する.おそらくメモリ不足と思われる.⇒カードテーブルサイズを12500,結婚テーブルサイズを10200に設定して完成図を出力できた.カード数12243,結婚数10170.⇒いや,ダメだ.崩れている.

image

ループカウントオーバーが発生しているのだろうか?⇒確かに「三極検定レッドラインオーバー」が起きている.少し延長してみよう.⇒ループカウント上限を100まで上げてみたが,抜けられない.まだ,どこかにバグが残っているのだろうか?⇒Collatz4000-12243.ZELとして保存した.⇒ZELファイルを取って,また,「極小反例サンプル」に仕掛けてみよう.⇒ダメだ.メモリ不足が起きてしまった.

image

この問題は64ビットに移行すれば解決するのかもしれないが,そればかりはちょっと今日明日の仕事ではない.スタックサイズはまだ削れる可能性があるのでそれをやるしかなさそうだ.

コントロールキー+マウスホイールでズーム

一段落付いたところで,修正をフィックスしておこう.⇒まず,UNDOに関する修正をフィックスしてしまおう.まだ,全面的な動作確認を行ってはいないが,今回の修正を不可逆的なものとして確定する.

  1. 「UndoNumberを設置する@20220418」7箇所
  2. 「UNDOのShadowをfreeblock化@20220423」2箇所
  3. 「UndoEndでコマンドを追加しない@20220424」→廃止
  4. 「ShadowチェーンからUNDOノードを検出する@20220423」1箇所
  5. 「UNDOTYPEを新設する@20220424」4箇所
  6. 「CommandStartで現コマンドを全クリア@20220425」3箇所
  7. 「CheckMaximalCompaction呼び出しを抑制@20220426」1箇所
  8. 「仮修正」27箇所

まだ,あれこれ対処する必要がある箇所はあると思われるが,一応完了したことにして,また,コラッツ木生成ツールに戻ることにしよう.どこいら辺から脇道に逸れて来たのか?ログで確認しておこう.⇒2022/04/12に「検証テストカウント3200のADLサンプルでハングする」という記事がある.おそらくこの辺りだろう.「TC3000という呪われたサンプル」は2022/04/15だ.

コラッツ木生成ツールの方は,A面とB面の3機能(コラッツ数列,アドレス変換,幹線木)の動作チェックが終わって,検証テストに入ったところだ.A面とB面3機能に関しては,一般木と仮想木の両サイドをチェックしているが,検証テストはまだ一般木のテスト中だ.今回修正で一般木のテストはパスできたと思われるので,仮想木の動作チェックに移行するところだが,コラッツ木生成ツールに移る前に懸案をいくつか片付けておきたい.

  1. コラッツ特注版のための例外措置としての「中吊りを強制」をオプションとして切り替え可能にする
  2. 系図画面のモードで「縦書き」と「横書き」をオプションとして切り替えできるようにする
  3. MAXIMALGRAPH::MergeUpperSegmentで結婚点一致の条件を緩和しているが,許容値上限の是非を確認する
  4. スケールの大きいファイルを開いたとき,メモリ不足のため「生描画に切り替えます」という動作になっているが,ズーム倍率を調整して回避できるのではないか?
  5. コントロールキー+ホイールでズームできるようにする また,ズームボタンを押したときのタイマーの初期値をもっと小さくする

項目5から片付けよう.現行でも,ホイール操作によるスクロールはサポートされているし,ズーム動作はズームイン,ズームアウトボタンとして実装されている.問題は,ホイール操作はOCXの受けるイベント,ボタン操作はVBのイベントになっているという点だ.いや,ホイールイベント自体はVBで取っているようだ.FramePositionというメソッドで受渡ししている.⇒いや,その前にCtrl+リールというのはすでに「水平スクロール」として使われている.「Ctrl+ホイール」でズームというのはかなり一般化しているので,仕様変更した方がよい.ホイールスクロールは,ALTキーで受けることにしよう.⇒実装した.ZOOMINTERVALを200(ms),ZOOMRATEを0.95に設定した.

項目4は現状とする.

▲ADLファイルをダブルクリックで起動できるが,データ数が上限を超えていますのエラーが反復表示される.サンプルはCollatzTest.G.ADL.しかし,ファイルメニュー→隣接リストのインポートでは問題なく読み込める.実際データは4720点しか入っていない.⇒おかしい.隣接リストのインポートとコマンドライン起動で異なる動作になっている.どちらもまったく同じコードを実行しているように見えるのだが…

Dim NewFileName As String = MakeAdjacencyList(.FileName)
OpenFileProc(NewFileName, OPENMOD.FULLIMPORT)

BASETABLE::emptyrecnでは,maxrecn < tablesizeで上限オーバーを検査している.maxrecn=tablesizeという状態になっているため,上限オーバーと判定されている.このmaxrecnという数は「有効なレコード数」となっているが,ややあいまいなところがある.おそらく,有効なデータの最大レコード番号という意味で使われているのではないかという気がする.maxrecnのアクセス関数として_maxrecnが使われている.レコード番号とデータカウントの混乱を避けるために,maxrecnではなく,dataCountという変数を用いることにする.アクセス関数はDataCountとしておこう.

どうもこの修正は野火のように際限なく拡がりそうな気配だ.ある時期に,効率的な観点から「参照番号とレコード番号を一致させる」ということを試みた時期があり,その残滓が残っていると見られる.つまり,参照番号をインデックスとしてテーブルに直接アクセスできるという設計で,このためには参照番号はテーブルサイズより必ず小さくなくてはならない.これはUNDOでカードを元の位置に戻さなくてはならないという辺りからの発想ではないかと思われるが,本来的にはその必要はなかったのではないだろうか?つまり,UNDOはカードのリンクがテーブル上のどこに配置されていたとしても,動作可能であるはずだ.

コラッツ特注版では原則として参照番号と名前は一致することを建前としているが,実際にはハッシュ衝突が多発するため,番号と位置が一致しない場合が発生し得る.一度修正を戻して,バックアップを取ってから始めた方が賢明かもしれない.リリース版のバックアップはあるが,リール・ズームを導入しているので,そこまで戻してから出直すことにする.実際のデータがどうなっているのかは分からないが,参照番号<テーブルサイズというのは悪い設計ではないと思われる.参照番号の位置にそのカードが存在しない場合は,つねに前方を検索するという探索法はそれほど効率の悪いものではないと考えられる.ただし,テーブルの上端に達した場合には下端に戻って検索を続ける必要がある.

現行論理はほぼそれに沿ったものになっているはずだが,ハッシュで衝突が起きた場合でかつテーブル上限を超えた場合の始末が入っていない.この修正をまず入れておく必要がある.⇒LINKTABLE::GetRefnumに修正をいれたところ,この関数内ですでにオーバーフローが発生している.確かに,ADL.CSVファイルを見ると8192点のレコードが入っている.MAXPDB=0x2000=8192だから上限に達している.テーブルは1発進なので(MAXPDB-1)個までしか収納できない.ハッシュ関数には0x1FFFを使っているので,生成される参照番号は8191までだ.⇒tablesizeは内部変数なので,実際のテーブルサイズより1小さく設定しておくことにしよう.

テーブルオーバーフローを無視して処理を進めることで系統並び替えまでは進んだが,絶対座標変換で例外が発生してしまった.Bobject::ResetAbsoluteでスタックオーバーフローが発生している.なぜだろう?NAMEBOX::DrawNameText→ PrintParameter→ getGenerationでエラーが出るようになった.getGenerationでは絶対座標系から呼び出されることを禁止している.しかし,これまでは何の問題もなく動作していたのだが… 暫定的にPRINTPARAMETERを止めてみよう.→描画できた.親子関係がぶつぶつに途切れているため,「木」というよりは「ヤブ」と言うより,ほとんど「草原」に近いものになっている.「横幅に合わせてズーム」しても,19%以上には拡大できない.「メモリ描画環境を使わない」ときは,ズーム倍率の制限は不用なのではなかったろうか?

いずれにせよ,ほとんど「手が付けられない」レベルに悪い.ファイル上のデータは8192点なので,テーブルオーバーフローになるのは高々1件に留まるはずなのに,ぼろぼろオーバーフローが発生している.いや,実際に登録に失敗しているカード数はそれほど多くはない.7331964,7326588の2点だけのように思われる.コマンドライン起動ではなく,隣接リストのインポートでも結果は同じだ.上記で「ファイルメニュー→隣接リストのインポートでは問題なく読み込める」としているのは,おそらくサンプルを取り違えたのだと思う.

テスト中のサンプルはCollatzTest.G.ADLだが,似た名前のCollatzTree.G.ADLというのがデスクトップにある.リリース版の動作をチェックしてみたが同じ結果になった.このサンプルが「ブッシュ」のようになってしまうのは,オリジナルのADLがそのようなファイルになっているためだろう.つまり,このサンプルは上限を遥かに超えたサンプルを生成して,大量の足切りが発生していたのだと思う.従って,現行の仕掛り版は基本的なところでは正しく動作していると言ってよいと思う.

極小反例を探す長いジャーニーが終わった

UNDOには大分てこずったが,なんとか落ち着いたようだ.極小反例サンプルは307点まで縮小することができたが,サンプル生成中にスタックオーバーフローが発生する.スタックオーバーフローが発生する時点はまだ特定できていないが,極小反例307.ZELから開始すると,単点削除検査を24回繰り返したところで発生することは確実なので,シューティングは時間の問題と思われる.障害はUNDOBASE::CommandEnd sc=478の後に発生しているので,まず,ここで停止してみよう.⇒i=20から開始してもスタックオーバーフローが起きる.多分,i=24から一発で再現できると思うのでやってみる.⇒再現する.

障害はカード@233をFAMILYTREE::DeleteCardDataで削除→ UNDOBASE::CommandEndの出口→ TopologicalSortを実行で起きている.TRIBEBOX::StackTribeGene→ TRIBEBOX::CompleteTribeBox→ HorizontalSegmentで起きる.⇒TightenUpLooseで起きているようだ.⇒MAXIMALGRAPH::tightenUpLoose→ TightenLowerBoxのようだ.⇒どうも,かなり筋の悪い障害だ.障害の発生する時点が刻々と変化してしまう.エラートラップにも落ちないようになって,最後はスタックオーバーフローも発生せず,Access violationで終了になってしまった.⇒NAMEBOX::TightenLowerBoxでGP例外が発生している.

どうも,このTightenLowerBoxで循環が発生しているように思われる.⇒以下のような三つ巴の再入呼び出しが実行されている.

MAXIMALGRAPH::IsMargBoxFixed→ MAXIMALGRAPH::IsNameBoxFixed→ NAMEBOX::TightenLowerBox→ MAXIMALGRAPH::IsMargBoxFixed

また,IsNameBoxFixedは自分自身を再帰的に呼び出しているが,この呼出では深いネストは発生していないように思われる.⇒いや,入っている.むしろこれが原因かもしれない.基本的にこれらの呼び出しは垂直に下降する方向に進むようなフローになっているはずなので,循環するというのはかなり奇妙だ.再入経路にはいろいろなパターンがある.

TightenLowerBox→ IsMargBoxFixed→ TightenLooseBox→ TightenUpLoose→ CheckMaximalCompaction→ MaximalCompaction→ TightenUpLoose→ TightenLowerBox→

これは,かなり無茶な仕掛けと言ってよいのではないだろうか?⇒MAXIMALGRAPH::TightenUpLooseの中からTRIBEBOX::CheckMaximalCompactionを呼び出すという動作を抑制するようにした.⇒これで問題は解けてしまった.すでに問題は解決しているので,この件に関してはもはや「極小反例サンプル」というものも存在しない.⇒試しに,CollatzTest 3000-4619.ZELを開いてみよう.これはコラッツ検証テストが出力した4619点サンプルだ.⇒問題なく開けた(と言ってもループカウント43でギリギリだが).計算完了までに2分近く掛かっている.

image

長いジャーニーになったが,収穫は大きい.UNDOを見直す機会が得られたこと,また古い年老いた蛇をついに捕らえることができたことなど…この不良はバグというよりは,設計ミスと呼ぶべきだろう.今回確立された「極小反例サンプル抽出の自動化」という技法は応用が効くので,今後のシューティングの決め手になるだろう.実際,今回は「極小反例サンプル」に到達する以前の段階で,不良をあぶり出すことができた.数千点というような大規模なサンプルで起きている障害をこれまでのような方法で追いかけていてもおそらく埒が明かなかったのではないかと思う.4600点から300点くらいまで縮小できれば自ずと見えてくるものがある.⇒リリース版を起こしておこう.「Version 2.2.2.008 Release 2022-04-26」とした.

インストールしようとしたら,また,何か分からないことを言い始めた.確かにどこかで見た記憶はあるが,通常は発生しない…

image

アンインストールしようとしても,同じメッセージが出てくる.⇒2.2.2.003.msiの場所を探してアンインストールした.コラッツ木生成ツール→VerifyでTest count:5000を指定して,Open Zelkova Treeで開くことができた.生成されたサンプルは7925点で,現在設定されている最大カード数=8192=0x2000のほぼ上限に近い.とりあえず,このくらいまでできればよいのではないかと思う.

UNDOに関していくつか重要な修正を行った

UNDOに関していくつか重要な修正を行った.①UndoNumberを設置する,②ShadowチェーンからUNDOノードを検出する,③UNDOのShadowをfreeblock化など.①はUNDOノードの重複を避けるために,コマンド発行ごとにインクリメントされる値で,保全対象のオブジェクトにはこの値が格納され,すでに格納済であるか否かを判断する材料とする.②は従来方式ではコマンドに連結されたUNDOノードリングをスキャンしていたのを,オブジェクトのShadowチェーンを直接操作する方式に変更した.この方がスキャンの範囲を狭めることができる.③は②を実現するために必要となった措置で,これまではヒープから直接切り出していたバックアップイメージ領域をfreeblockのオブジェクトとして管理できるようにするものである.

昨日のログではこれらの修正後,ある程度改善されたとしているが,実質的にはまったく変化していない.つまり,依然としてUNDOノードの増殖は続いている.これに対処するために,UNDOノードリング上に同じタイプで完全に同内容のイメージが存在するためには,リングに追加しないようにしたところ,一昨日の障害が再発してしまった.

▲UNDOBASE::UndoProcess→ TOPOLOGY::RebuildCardList→ NAMESORT::NameSort→ NAMESORT::SortNameSub→ compnode のコールバックでcard2の参照番号が0になっている.⇒この障害は,2022-04-23に初発したもので,「オブジェクトのコピーにUndoNumberを格納していたことが誤動作の原因」として廃止しているが,その後の修正で,オブジェクトのコピーの前にUndoNumberを設定しているので,シャドーにもそれがコピーされている.

前回はこの障害をカードテーブル上のカードの参照番号がゼロとなるタイミングをSWOで追いかけて突き止めているので,試してみよう.⇒UNDOSYSTEM::RestoreShadowで完全に白紙のシャドーがリストアされている.このUNDOのノードのSSNは#614867.どこでこのノードが生成されたかを見る必要がある.このノードはCARDLINK#2246のバックアップだ.CARDLINK#2246はカード番号@479の「479」というカードで,カード削除の対象カードだ.

UNDOチェーンには#2246のバックアップは「削除」コマンド分しか残っていない.BackupPointDataでは保全されているので,上書きされてしまったのではないだろうか?⇒UNDOBASE::SetUndoListの修正にミスがあった.ただしこれを訂正後,COUPLING::TopologicalSort→ TOPOLOGY::SortAncestorTableで「先祖ノード数がゼロ」という別の障害が出てきた.カードテーブルには分散しているが,カードは入っている.maxrecn=361でtablesizeは8192,基準ノードは@23だ.

senzosu=1となっているが,Senzolist配列には何も入っていない.TOPOLOGY::SortAncestorTableで先祖リストを生成している.⇒カードテーブルにアクセスできていない.getmaxrecnが返す値がカードテーブルの範囲をカバーしていない.⇒BASETABLE::getmaxrenはmin(maxrefnum, tablesize)を返しているが,テーブルはmaxrefnumよりも拡がっている.⇒暫定的にtablesizeを返すようにした.むしろ最大レコード番号を返せるようにした方がよいのだが… ⇒これで収まるかと思われたが,まだ(max < 1)が起きる.

▲極小反例 361.zelでカード@479を単点削除した後のUndo出口→ 系統並び替え→ TribeDecomposition→ SortAncestorTableで(max < 1) で停止する.基準ノードは@479.これは,UNDOがよく機能していないことを示すものではないか?対象ノードの親がQに入っていないため離脱している.Qへの登録はTOPOLOGY::InitializeDecompositionとTOPOLOGY::GetkinshipDegreeで実行されている.InitializeDecompositionはTOPOLOGY::TribeDecompositionで実行される.TOPOLOGY::TribeDecompositionはTOPOLOGY::FilteringKinshipから呼び出される.FilteringKinshipはTribeDecompositionに先行する.

@479の親は#1841@35で,InitializeDecompositionではQに登録されている.⇒@ 35はQに入っている.先祖ノードであることも確認されている.問題は優先ノードが一致しないという点だ.これは,InitializeDecompositionではやっていない.⇒少し混乱している.Undo後の系統並び替えの基準ノードは@23で,先祖ノードは@35だ.@479を削除した後,Undoしているのだから,元の原木に戻っているはずだ.それが,実際は@479を削除して4系列に分解したままの状態になっているということだろう.おそらく,@479の事前バックアップデータが上書きされてしまっているのだろう.つまり,事後データは別途保存されなくてはならないというところが崩れているのだろう.⇒UNDONODEクラスにUNDOTYPE undotypeを新設し,createを廃止して,SetUndoListの引数のcopymodeと統合してundotypeに吸収した.UNDOTYPE は「SetUndoListのノード生成時の動作種別」で,以下のように類別される.

  1. UNDO_DEL = -2, オブジェクトの削除コマンド
  2. UNDO_NEW,         オブジェクトの新規生成コマンド
  3. UNDO_NORMAL,   オブジェクトが保全されている場合は上書きしない
  4. UNDO_COPY,        オブジェクトが保全されている場合は上書きする
  5. UNDO_MAKE,        つねにUNDOノードを新規生成する

この修正によって動作はかなり改善されたが,まだ時間経過とともにUNDOノードが増殖するという傾向は残っている.以前は等比級数的に増加していたところが,等差級数的に近くなっている.現行論理では,一つのオブジェクトに対して,undotypeが同じUNDOノードは生成されないようになっているから,オブジェクト1個につき,最大でも5個以上のリングにはならないはずなのだが…また,1個につき上限が5個で,かつ毎回Undoしているのだから,単調増加することはあり得ないように思われるのだが…少しランニングさせて様子を見ることにしよう.やはり,各回につき10個くらいづつ増加している…

どうも,UNDOBASE::CommandEndでコマンドオブジェクトを一つ追加しているというのが敗因であるように思われる.このコマンドは完全にダミーの役割しか果たしていないのだが,これがあると,UndoとRedoの状態の管理がかなりシンプルなものになるという理由から導入されたものだ.しかし,これを廃止するということは本質的な改善にはならないのではないか?というのは,この位置にはリングノードはまったく追加されていないからだ.

コマンドを実行するときには,最初に現在のUndo位置のコマンドリングを完全に削除してからコマンドの実行に入る.従って,つねに白紙状態から実行に移ることになる.これならリングノードの増殖が起こる余地はないと考えられるのだが…もし,それで差し支えないのなら,現行論理のまま,UNDOの現在位置の一つ前の位置まで戻して,そこをクリーンアップすればよいのではないか?いや,むしろ,CommandEndで書き込みしている部分を前方に移動すべきなのではないか?

UNDOのShadowをfreeblock化

極小反例サンプル抽出ツールで全選択が2回入った後,UNDO処理が遅くなるという事象が発生している.バックアップされるオブジェクトの個数が急速に増加しているためだが,その原因はどうも,UndoRedoの動作不良によるものらしい.カード#485を削除すると系図木は3系統に分裂する.このうち始系列を除く2系列は先祖ノードだけの孤立系列で,先祖ノードはそれぞれ,#1294と#5174だ.この時点ではUNDOのコマンドチェーンは,{17, 6, 6, 1}のようになっている.ここで{n1, n2,…}はコマンドのバックアップオブジェクトの個数の並びである.

このあと,カード#497を削除すると,コマンドチェーンは{17, 6, 6, 16, 1}のように変化する.しかし,このあと実行されるUndoでは,チェーンは変化せず,{17, 6, 6, 16, 1}のままになっている.そのまま続行すると,チェーンは{17, 6, 6, 37, 1}のように変化し,チェーンの4番目のコマンドのオブジェクト数は1→ 16→ 37→ 79→ 160→ 366→… のように単調に増加を続けるようになる.そもそも,Undoしているのにコマンドチェーンの長さが短くならないというのがおかしい.⇒いや,勘違いしている.UndoRedoで変化するのはUNDOの現在位置UndoCurptrだけで,コマンドチェーンは不変だ.

従って,カード#497の削除後のUndoで,コマンドチェーンが{17, 6, 6, 16, 1}→ {17, 6, 6, 16, 1}のように変化していないという動作は正しい.実際,UndoCurptrの位置を[]で示すと,{17, 6, 6, 16, [1]}→ {17, 6, 6, [16], 1}のように移動している.この後,カード削除を実行すると,[16]の位置に新たなバックアップが書き込まれるため,その分だけUndoノードが増加する.この辺りの論理は書き換えていないつもりだが,だとすれば以前からこのような動作になっていたことになる…確認してみよう.⇒2022-03-03という版を見てみよう.この版ではUNDO処理はコンパイルオプションで止めてある.⇒… なんということだろう!この版では極小反例 461.zelが何の苦もなく開けてしまった…

image

ということは,これらの反例が開けなくなったのは比較的最近の修正によるということになってしまう.⇒いや,少なくとも「BUG3000-1906.ZEL」は解けない.⇒やはり,解けていないようだ.371点の反例までは解けるが,550点反例では解けなくなる.この事象は計算誤差をどの程度に見込むかなどによって微妙に動作が変化するため,最新版で解けないサンプルが古い版で解けるということもあり得るだろう.

ようやく,なぜこういう事象が起きているのか?という理由がわかった.UNDOでバックアップを取るときのロジックの穴を塞ぐためにUndoCounterというグローバル変数を設け,コマンドを生成するたびにインクリメントするようにして,対象オブジェクトを保全するときにはこの値をオブジェクトに記録し,重複バックアップを回避するように修正しているが,これが却って裏目に出ているということのようだ.UndoCounterはインクリメントするだけの値なので,Undoでコマンドチェーンを遡った状態で新たなコマンドが実行されたときには,前に保全されているオブジェクトであってもUndoCounter値が小さいためにバックアップが再実行されることになる.これを避けるためにはUndoCounterの値をUndoRedoの動作に合わせなくてはならない.

類似パラメータとして,UndoCountというのがある.これはコマンドを生成するたびにインクリメントされるが,ある定数MAXUNDOCOUNTに達したときには,それ以上のコマンド生成を停止し,UndoChainを一つ前に進める.UndoCounterは現状ではMAXUNDOCOUNTに関わりなく,つねに1インクリメントするようになっている.必要な修正はUndoCounterの値をUndoでは1デクリメントし,Redoでは1インクリメントするようにすることだろう.それでよいのかどうか?確認してみよう.⇒ダメだ.さっぱり作動していない.

チェック用のコードなどを入れて,358点まで縮小したサンプルから開始したところ,何点か単点削除検査の後,スタックオーバーフローが発生した.また別の障害が出てきた可能性があるので,元のサンプルでテストし直してみる.⇒コマンドにも時点のUndoCounterを記入するように修正してみたが,全削除2回のあとの単点削除でUndoCounterの不一致が発生した.UndoCurptr->UndoCounterの値は98で,UndoCounterの値は99だ.DumpUndoChainでUndoCounterの値も表示するようにしてみよう.

UndoCounterとUndoCurptrは完全に同期している必要がある.つまり,UndoCurptrが更新される場所ではつねにUndoCounterも更新されなくてはならない.UndoCurptrがリセットされるときには,UndoCounterもゼロリセットされなくてはならないだろう.⇒対処した.UndoCounterはUndoNumberにリネームした.3回目の単点削除→Undo中に発生している.

▲UNDOBASE::UndoProcess→ TOPOLOGY::RebuildCardList→ NAMESORT::NameSort→ NAMESORT::SortNameSub→ compnode のコールバックでcard2の参照番号が0になっている.これまではこのようなことは起きていなかった… 参照番号の入っていないオブジェクトはSWOでもトレースできない.カードテーブルのインデックスが3であるという手掛かりしかない.PDBのsnumは8だ.⇒おかしい.サンプルファイルをロードした時点でこのカードがヒットしない.いや,この[3]というインデックスはカードテーブルではなく,そのルックアップテーブルのインデックスだ.カードテーブルは1発進だが,ルックアップテーブルはゼロ発進になっている.

ルックアップテーブルは毎回作り直ししているので,障害が起きたときのインデックスを参照しても情報がつかめない.⇒これは,参照番号が消えたのではなく,リンクだけが残った状態ではないか?検定では,#23削除→ Undo→ #32削除→ Undo→ #41削除→ Undo で障害が発生している.直近の修正が影響していることは間違いない… ⇒一つ余分なことをしていた.オブジェクトのコピーにUndoNumberを格納していたことが誤動作の原因と思われる.これは不用な動作だった.しかし,依然としてバックアップが増殖してしまう状況は変わらない.

▲nodule::setShadowでエラーが発生した.この関数はShadowチェーンの更新用関数で,オブジェクトのShadowチェーンの末尾に新たに生成されたShadowを繋ぎ込むものだが,対象Shadowイメージにリンクが残っている.このリンクは不正リンクでおそらく,ゴミと思われる.⇒いや,違う.Shadowというのは,オブジェクトの時点におけるコピーだから,その時点でそのオブジェクトがすでにShadowを持っていれば,当然shadow->Shadowには値が入っていると考えられる.

修正した.しかし,いままで一度もここで停止しなかったという点に関しては不審が残る.大分まともな動作になってきたが,まだ検定が進んだ段階でバックアップ個数が再び増加し始める.このまましばらく走らせてどうなるか見てみることにしよう.


バックアップがネズミ講的に増大する

ある特定のサンプルでループカウントオーバーが発生する.この問題に対処するために,「極小反例サンプル」を自動抽出するという試みに取り組んでいるところだ.すでに実稼働する状態になっているが,1232点まで圧縮したところで例外が発生している.UNDOBASE::CommandEndでエラーが発生している模様だが,そのままアボートしている.⇒同じサンプルから開始したつもりだが,再現しない.まだそのポイントまで進んでいないのだろうか?

▲TribeRelocation→ StackTribeGene→ setcompleteで (!OnCompleteTribeBox && val && CheckMaximalSegment(funcname) > 1)で停止した.レッドラインオーバーで抜けているためだが,なぜ,これまで停止していなかったのか?という方がむしろ疑問だ.⇒ループカウントオーバーではつねに偽を返すように修正した.

まだ多少不具合は残っているが,走行中の極小反例サンプル生成ツールは550点の反例サンプルを出力した.

image

だいぶイメージに近付いてきた.修正を入れたあと検定再開して371点まで削減したところで,カード削除が空振りのときのUNDO処理でやけに時間が掛かるようになった.理由はわからない.nodule::ReferenceControlで時間が掛かっているのかもしれない.⇒UNDOオブジェクトの大量発生が再発しているのではないだろうか?

極小反例 371.zelをツールに仕掛けて,#32のカードを削除して,CARDLINK #1905 のデストラクタの中で「被参照カウントの残留」が発生した.45個も残っている.参照元はMARGBOXだ.⇒この「被参照カウントの残留」はUNDOの不良にも関係しているかもしれない.⇒いや,UNDOの不良はその次に削除された#41のカードについて発生している.確かに,UNDOのどこかが壊れてしまったことは確かであるように思われる.⇒UNDOの事象が発生するのはずっと後の#809のカードだ.このノードは1204個ものバックアップオブジェクトを抱えている.なぜこんなことが起きているのだろう?そのほとんどはCARDLINKだが,MARGLINKも一定程度混ざっている.これらは,UNDOCOMMAND #16923301にぶら下がっている.コマンドはDELALLCARDだ.しかし,このカードは単点削除されているように見えるのだが…

▲#809のカードを削除→UNDOでDELALLCARDが復元されている.このコマンドは1204個のバックアップオブジェクトを持っている.コマンドオブジェクトはUNDOCOMMAND #16923301.その前に,#804カードの削除でも類似の事象が発生している.UNDOCOMMAND #16923301.これもおかしい.UNDOCOMMAND が同じ番号を持っている.その前にもう一つ.#791カードというのがある.⇒いや,そもそもシステムの動き自体おかしい.デバッガのダンプテキストをコピーしてテキストエディタに貼り付けようとしたら,テキストエディタがフリーズしてしまった.⇒いや,違う.これはテキストがあまりに文字数が多いためだ.3781154行もある.

いずれにしてもかなりおかしい.「全カード削除」が実行されているのなら「全削除」というテキストがダンプに現れなくてはならないはずだが,まったく見当たらない.「DELALLCARD」というUNDOのコマンド名はあちこちに出てくる… ※「全削除」という用語は使われていない.

まず,先に「被参照カウントの残留」を片付けてしまうことにしよう.MARGBOX(22)というのは,「所属系列の先祖ノード人名リンクへの参照」だが,先祖ノードの系列に属する結婚枠はすべてこのノードを参照しているから,#1905の系列には45個の結婚が属していたと見られる.この系列は#1905の直系血族図を出力するために生成されたと考えられるが,そのあと,この系列に属するすべてのカードが削除された時点で消滅している.通常はこのような操作を行うときには,系統並び替えが実施され,その冒頭のClearTableで始末されているはずだが,極小反例ツールでは極力系統並び替えを実施しないようにしているので,いわば,「放置」状態になっていると考えられる.

系列枠リストを再生成するときには,系列枠はすべてパージされるので描画リストからは切断されているはずだが,結婚リンクが存続する限りは結婚枠は残存することになると思われる.しかし,系列に属するすべての人名リンクが削除された場合,結婚はすべて無効となって結婚リンクも同時に削除されているはずではないだろうか?だとすれば,結婚枠も削除されたと考えてよいのではないかと思う.結婚枠にはたとえば,#654009や#654265などがある.これらが削除されていることを確認しておこう.いや,#1905自体その系列に属しているのだから,その時点ではまだ存続している可能性がある.

先祖ノードからグループ内の結婚枠にアクセスするための経路としては,先祖ノードの人名枠に接続する描画リストをたどるという方法がある.また,別の方法として,もし,その時点で系列枠が存在しているとすれば,先祖ノードの人名枠のグループ,つまり系列枠ノードからグループメンバーを割り出すことも可能と思われる.まず,CARDLINKのデストラクタで人名枠が存続していること,またそのオブジェクトのグループも存続していることを確認しておこう.CARDLINKが系列先祖であることを知るにはどうすればよいか?

CARDLINKのDisposeの中から,CARDLINK->NAMEBOX->TRIBEBOX->CleanSansyo(CARDLINK)が実行されているので,これを見ておこう.⇒TRIBEBOX::CleanSansyoにはすでに描画リストを辿って結婚枠からの先祖ノード参照を削除する処理は入っているが,これに追加して,グループリストから結婚枠を特定して参照解除する処理を組み込んだ.ただし,これは空振りに終わった.⇒これらの点から見て,この障害は先祖ノードを含むブロックを一括削除したときにはつねに起こりそうな感じがするが,発生しない.

この障害には,計算量を軽減するための「UndoRedoで一時的に系統並び替えを停止@20220419」オプションが作用している.このオプションが立っているときにはエラーを無視することにする.正規のコードでも,undoredoがオンのときには警告パネルを出さないようになっている.従って,このオプション中は「非参照カウントの残留」は無視するというのが妥当である.「CHECKREMAINSANSYO」というオプション自体をオフにしておく必要がある.⇒対処した.

本線のUNDOに時間が掛かるようになるという問題に戻ろう.2, 3件の全削除が掛かって,カード数が361まで削減された後に事象が発現し,保全されるオブジェクト数が鰻登りに増加するようになる.⇒どうも,バックアップがネズミ講的に増大しているのではないか?という気がする.「極小反例 361.zel」から始めた場合,20個くらいの「カード削除」の後,単点の「カード全削除」が2回続き,その後の「カード削除」からバックアップの個数が増加し始める. 「UndoRedoで一時的に系統並び替えを停止@20220419」は動作に影響していない.明らかに現行論理ではかなりの重複バックアップが生じているが,これは一般的な動作で「増加」と直接結びつくものではない.PARTIALMAP, longtableのダブりも見受けられる.⇒カードの単点削除はそのつどUNDOされるので残っていないが,全削除された場合はそのまま残されているので,累積する.それが影響しているのだろう.

UNDOノードには①更新,②生成,③削除の3つのタイプがある.Undo/Redoでは②ないし③については生成/削除,ないしその逆操作を行い,①の更新では内容を上書きする.②と③は排他的だが,①の更新は一つのコマンドの中で複数発生する場合もあり得る.UndoとRedoではコマンドリングを逆向きに処理しているので,同じノード群でも結果は異なるものになると考えられる.このような実際のフローから見て,UNDOノードの重複を回避して単一のUNDOノードに集約するのは難しいように思われる.従って,UNDOノードを生成するときに可能な限り重複を避けるという方策しかないのではないだろうか?うまく,すれば①のみ,②→①ないし,①→③という組み合わせに極小化することは不可能ではないような気もするが…このためには,②ないし③のUNDOノードに初期/末期情報を掲載しておく必要がある.そこまでやるしかないのかどうかをまず見極める必要がある.


UNDOで膨大な数の無用なバックアップ発生

UNDOで膨大な数の無用なバックアップが生成される問題を解決するために,UndoCounterというパラメータを追加した後,極小反例ツールがまったく動作しなくなってしまった.FAMILYTREE::RestoreBaseCardではBaseLink空というエラーも起きている.なぜだろう?というか,上記修正がまだ収束していないことは明らかだろう.CommandStartからCommandEndの間に更新されたオブジェクトはすでに保全されている場合でも,更新しなくてはならないのに,まだその部分に関しては手当されていない.しかし,これは極小反例ツールの動作には関わってこないような気もするのだが…

BaseLinkはFAMILYTREEのメンバ変数で,UNDOのたびに別途バックアップされているはずなのだが…これらの値は,UNDOCOMMAND本体に保全されている.この値は,FAMILYTREE::SetUndoBaseで格納され,UNDOSYSTEM::UndoProcessでリストアされる.また,アプリ側にはUNDOBASE::GetUndoStatでこの値が引き渡される.⇒CommandEndでUndoCurptrが空となっているのが問題だ.UNDOBASE:CommandEndの論理はかなり難解だ.というか,奇妙だ.

CommandEndの後半部冒頭で,MakeNewCommandを実行している理由がよく分からない.また,これを実行するとUndoCurptrは一つ前に進み,(!UndoCurptr->topUndo)となるので,必ずPergeZenpoChainが実行されることになる.PergeZenpoChainを実行することにより,UndoCurptrが空になっている.⇒MakeNewCommandが実行されているのは,オブジェクトが削除されていたり,UNDO中に更新されている場合の保全のためと推定されるが,preiviousに書き込みしているので,新しく生成されたコマンドの先頭ノードはつねに空になっている.従って,つねにPergeZenpoChainが実行されることになるように思われる.コマンドが実行されたときには前方のコマンドチェーンをパージするという動作は正当であると思われるが…

PergeZenpoChainでUndoCurptrが空になるという動作が一番おかしいところだが,この辺りの論理は修正していないはずなのだが… UNDOは結構手強いところがある.SetUndoListの論理をオリジナルに沿って修正して動作するようになった.迂闊には修正できないところだ.これでようやく極小反例サンプルの生成に戻ることができるが,動作はまだ収束には遠いところにある.「3」を削除して反例を生成しているはずだが,保存されたファイルは1点しか減じていない上,反例になっていない.画面で見ると4系列に分裂しているように見える.意図したものとまったく異なる出力になっている.

image

先祖リストには{ 35, 5463, 8178 }が入っている.35は始系列の先祖ノードなので,5463系列と3178系列を削除するという操作が必要だ.⇒おかしい.動作が変化している.今度は先祖リストに2点しか入っていない.{ 35, 5463 }.なぜだろう?削除対象カードは「3」ではなく,#3だ.#3は「8195」で親ノードは「12293」,子どもは「5463」一人しかいない.このノードは3倍数なので,ここで止まりだ.従って,{ 35, 5463 } は正しい.⇒おかしい.デスクトップに「極小反例サンプル.ZEL」で保存しているはずなのに残っていない.⇒「\」が入っていなかった.⇒見つかった.「極小反例サンプル.ZEL」の中に「5463 」が孤立カードとして残っている.

削除モードは,全削除でZ.mDeleteCard(-1, True)を実行しているのだが…mDeleteCardは第一引数が負で,第二引数が真なら,DeleteAllCardを実行するようになっている.DeleteAllCardは,Z.DeleteTableの内容ではなく,TREEVIEWの選択カードリスト selectcardlist をベースに動作するようになっている.しかし,これはかなりバランスが悪いような気がする.同じmDeleteCardは,単点削除に関してはDeleteTableを使っているからだ.全削除するためには,まず「選択」を実行しなくてはならないということのようだが,多分これは,mPutSelectListで実行できると思う.

DeleteAllCardは-503という値を返している.-503はERR_NOVALIDCARDEXISTというエラーだ.このエラーコードはtreeview->selectcardlistが返している値だ.指定レコード番号の前方ないし後方を探索して有効レコードの参照番号を返す.いまの場合,カードテーブルには#5463しか入っていないので,有効レコードが存在しないで正しい.⇒今度はうまくいったようだ.1470点から2点減じて,1468点サンプルになった.ツールをオープンするときの開始サンプルを「極小反例サンプル.ZEL」としたので,何段かの縮約が入り,すでに1433点まで縮小している.

image

おかしい.まだ,どこか不備があるようだ.カード削除を実行してレッドラインオーバーが出ているのにブレークが掛かってこない.エラーコードが通っていないのだろうか?⇒いや,違う.UNDOで戻されているため,元の状態に戻っている.UNDOでは必ず系統並び替えを実行しているので,レッドラインになる.UndoRedoの出口で一時的に系統並び替えしないようにしてもよいのではないか?

▲スタックオーバーフローで異常終了してしまった.総点数1433点から開始して,カード削除10点で空振りして,11点目の#56でヒットした,極小反例サンプルを更新したあと,2点削除してスタックオーバーフローになった.DLLで障害が起きている.DLLはスタックサイズを2147483648まで増量してあるので,十分ではないかという気がするのだが…デフォルトは1MBなので,その128倍だ.⇒再現テストを可能にするため,開始サンプルを「極小反例 1305.ZEL」として保全した.⇒スタックの絶対量が不足していたのだろうか?「極小反例 1305.ZEL」から開始した検定は順調に進んでいる.

▲カード削除中,DeleteCard→RestoreBaseCardでBaseLink空で停止した.参照番号に-503という値が入っている.無視して続行したところ,処理から抜けてしまった.→「極小反例サンプル.ZEL」が空になってしまった.参照番号#815という無名のカードがあるだけだ.

▲「極小反例 1296.ZEL」を開始サンプルとして#5295を削除してBaseLink空が再現した.このケースでは全1296点中1295点を削除してループに戻り,残り1点を削除しようとしてエラーが発生する.すべてのカードを削除したのだから,このエラーが起きるのは当然だ.#5295を削除して,系図木は2つの系列に分解しているが,大きい方をつかんでしまったということになる.これを避けるには,先祖ノードで「1」を避けるようにするしかない.⇒対処したが,エラーは解消しない.これは,親族図で全削除したため,基準ノードとなるカードが存在しなくなったためと考えられる.しかし,異常終了してしまうのはおかしい.部分図ではカードゼロの状態を認めているのだから,親族図でもそうすべきなのではないか?ないし,全体図に戻ることも考えられるが,特にいまの場合は直系血族図で連続的に処理を続けたいので,全体図に強制的に戻るというのはよろしくない.

新規カードを親族図に表示するという考え方もあり得るが,ややこしくなるのではないか?⇒新規カードというのは名前を持たないだけでれっきとした登録カードであり,不用なら削除すればよいというだけなのだから,それでもよいのでは?⇒それでもよいが,いまの場合はそれでは都合が悪い.やはり,親族図では新規カードを自動生成しない方がよい.部分図でこの辺りをどう対処しているのかを参考にして,親族図でもカードなしの状態を認めるようにした方がよいと思う.実際問題としては,全体図であってもカードなしの状態を認めても差し支えはないとは思うのだが…⇒先祖ノードが「1」と思いこんでいた.このサンプルでは先祖ノードは「35」だ.



Windows 11をダウングレードしてWindows 10に戻す

UNDOでエラーが出ている.UNDOBASE::CommandStartで (!UndoCurptr->topUndo)のエラーが出ている.このエラーはリリースモードでは発生しない.⇒_ASSERT_NEVERはデバッグ専用のアサーションだ.⇒UNDOBASE::MakeNewCommandでは出口で明示的にtopUndoにNULLを代入している.その後実行されるBackupPointDataでバックアップが実行された場合にのみ値が入る.UPDATETBLでは更新されるカードデータがバックアップされるが,インポートの場合にはオブジェクトが不在の場合があり,このようなときにはtopUndoは空のままになる.⇒オブジェクトが空の場合は停止しないようにした.

VS2017の開発環境でゼルコバの木を起動してほとんど止まってしまう.リリースモードでは動いていたのだが,どこか壊してしまったのかと思って少し古いパッケージに戻って試してみたところ,リリースモードでも立ち上がらなくなってしまった.リリースモードでは起動時に表示しているスプラッシュウィンドウのところでフリーズしてしまう.デバッグモードの場合はほとんどどこでハングしているかわからない状態だ.ブレークを掛けてみるとほとんどつねにコンストラクタのマクロの中で止まっている.昨日まではほとんど問題なく動作していたように思われるのだが…まったく心当たりがないので,とりあえずWindows 11をダウングレードしてWindows 10に戻してみた.

ダウングレードはWindows 11にアップグレードしてから10日以内に行わないと手遅れになる.アプリケーションの再インストールなどは必要ない.VS2017を起動して,ゼルコバの木を実行してみる.⇒何事もなかったかのようにあっさり立ち上がってきた.リリースモードでもデバッグモードでもまったく問題なく走っている.Windows 11では何かひどいデグレード(劣化)が内部で起きているように思われる.リフォームの志向する方向(ポリシー)はそれほど悪くないので,残念だ.

バックアップから元の仕掛り版に戻して実行しようとしたところ,障害が再発してしまった.プログラムのコードに何か致命的な不良があるのだろうか?⇒リリース版は立ち上がってくる.デバッグモードではコマンドライン引数で起動するようになっているので,リリースモードと同じノーマルモードで起動するようにしてみた.⇒これなら,リリースモードと同等に実行できる.ADLのインポート処理に何か問題が起きているのだろうか?⇒UNDOを復活させたのが過負荷になっているのではないか?⇒どうも,そういうことのようだ.ということは,Windows 11でも動作していたということだろうか?

確かに,それは言えるかもしれないが,「遅くなっている」というのは事実なのではないか?単純なファイルコピーでもWindows 10より遅くなったという印象がある.そのため,重いサンプルを読み込むときには,それが隠しきれなくなるのではないか?少なくともリリースモードでは(UNDOが入っていたとしても)開けないとおかしい.⇒リリースモードでチェックしているとき,スプラッシュウィンドウが開いたままになっていたという事象があったが,開発環境ではスプラッシュウィンドウは表示されないのではなかったろうか?⇒確かに,それはおかしいね.何か勘違いしていたかな?しかし,通常,スプラッシュウィンドウは2, 3秒で閉じることになっているのに,開きっぱなしというのはやはり動作不良と見るしかない.

いずれにしても,動作するようになったので作業を再開できる.UNDOが入るとほとんど止まってしまうという問題は別途考えることにしよう.というか,インポートはUNDOの対象外なのではないか?ファイルのオープンではUNDOのバックアップを取っていない.原理的にはそれと同じはずだ.インポートは一覧表のレコードの更新機能を使って実現している.レコード更新はUNDOの対象なので,それに合わせているが,これは廃止すべきではないか?⇒それが妥当だと思う.インポートでUNDOしないことにすれば,UNDOを復活させても支障ないはずだ.

インポートはSendUpdateDataという関数を反復呼び出すことで実現している.この関数ではインポートから呼び出されているのか,そうでないのかを判別できない.インポートでは処理を開始する前に,Z.mImportStartという通知を送り,Z.mImportEndで閉じるようになっている.これで状態を判別できるのではないか?LINKTABLE::ImportStartでは,ImportFileNameにファイル名をコピーしているだけで,フラグは立てていない.⇒ImportFlagというフラグを作っておこう.⇒これでようやく,懸案の「難問」に戻れる.

呪われたサンプルTC3000(4720点)を1353点まで圧縮した「極小サンプルファイル」を作ってあったはずだが,見つからない.残っているのはCT 3000-1906.ZELまでだ.「GOO3000-1303.ZEL」というのはあるが,これは反例ではない.間違えてゴミ箱に入れてしまった可能性はあるが,空にしてしまったので取り戻すことはできない.「BUG3000-1906.ZEL」というファイルもある.「CT 3000-1906.ZEL」とどう違うのだろう?「53直系血族図.ZEL」というのもある.1931点で最小という訳ではないが,最後に扱っていたサンプルだ.⇒これを継承したのが「CT 3000-1906.ZEL」で「BUG3000-1906.ZEL」はそれと同じだ.「BUG3000-1906.ZEL」は下図のようなファイルで,先祖ノードの「35」は画面の下の方に隠れている.

image

明らかにまだ,かなり削れる余地は残っている.この際なので,完全に「極小」な反例サンプル,つまり,どの1点を取り除いても解けてしまうようなサンプルを追求してみることにしよう.UNDOが使えるようになっているので,それほど厄介な作業ではない.ノードを削って,解けてしまった場合にはUNDOで戻せばよいだけだ.先祖ノードの「35」には{ 1493, 23, 373 }の子ども3人がいる.多分2系統残せば十分と思われる.前回は「23」と「373」の2人を残している.最大系統は「23」だ.「1493」は6点しかない.

image

「373」はもう少し大きく,49点ある.

image

まず,この系統を全削除してみよう.やはり,この系統を外すと再現できなくなってしまうようだ.とりあえず,「1493」の直系血族図を取って全削除.⇒失敗した.親族図に切り替えてからソートすればよかった.親族図なら短時間に描画完了できるが,全体図ではループカウントオーバーするまで待たなくてはならない.⇒おかしい.先祖ノードの「35」の子どもがいなくなってしまった.

▲BUG3000-1906.ZELで1493の系統を全削除して,先祖ノード35とその子どもの23, 373のリンクが切れてしまった.⇒全削除ではなく,1個づつの削除でも同じだ.

全削除のバグと思われるが,「35」に「23」と「373」を接続して先に進むことにしよう.⇒かなり,まずい.35→{23,373}の接続ができない.登録ボタンを押しても子ども欄が空欄になってしまう.

どうも,この辺りは全面的な見直しが必要なようだ.UNDOで初期状態まで戻れるだろうか?ちょっと心もとない気がするが…⇒ダメなようだ.もう一度読み直そう.

▲氏名並び替えを実行しただけで,系統並び替えが発動されている.⇒カード並び替えはUNDOの対象になっている.UNDOではつねに系統並び替えを実施するようになっていたのではないか?

▲35の子ども欄に23と373を入力→登録で名前が消えてしまう.23の父欄に35を入力→登録でも名前が消えてしまう.つまり,親子関係の登録が完全に壊れている.⇒UNDOで復元はできた.⇒全体図上で全削除を実行したら,正しく動作した.カードの登録・削除の動作が開いている画面のモードに影響されるなどということがあるのだろうか?

終端ノードは事象に関わりがない可能性があるので,一括除去してみよう.3倍数は女子として登録されているので,まとめて削除できる.438点ある.削除はできたが,解けてしまった.昨日の手順で裾刈りをしてみよう.昨日のメモに「1335」を含むとあるので,それより下の世代をカットしてみる.⇒1473点まで削除したので,一旦保存しておこう.BUG3000-1473.ZELとしておく.⇒少し欲張って,あと2世代裾刈りしてみよう.いや,ダメだ.だめということは昨日確認されている.

「23」は5人子どもをもっている.{15, 245, 3925, 61, 981}だ.「373」の子どもは2人で{1989, 497}だ.これらのいずれかの子どもの系統を切断できるかどうかやってみよう.まず,「373」の子どもから見てみる.2人の子どものうち,1人は女子なので,おそらく削れるだろう.もう一人の子どもは残すしかないことは間違いない.「23」の子どものうち,2人(15, 981)は女子なので,まずこれからカットしてみる.⇒OKのようだ.残り3人を試してみる.まず,「245」⇒loopcnt=25で解けてしまった.⇒他の2つも同じだ.この手順を自動化することは不可能ではない.たとえば,以下が考えられる.

  1. 対象グラフをTとする
  2. TのすべてのノードNについて,以下を行う
  3. ノードNをTから削除して,検定がカウントオーバーするか否かを検査
  4. カウントオーバー→Nの下流系を除去したTの部分グラフをT’とする
  5. 検査に合格したT’のうちの最小のものを選んで,Tとする
  6. これをどの1点を除去してもカウントオーバーしなくなるまで繰り返す

このアルゴリズムによって,最適ないし最小であるか否かは別として,「極小な反例サンプル」が得られることは間違いないと考えられる.問題は計算コストだが,実効的には多項式時間で可能なのではないかと思われる.ステップ4で1点除去するたびにグラフは確実に小さくなってゆくからだ.前回は1353点まで圧縮したので,まだまだ削れることは確実だが,手操作で「極小な反例サンプル」を獲得するのはかなり難しい.「極小な反例サンプルを自動生成」するプログラムを書くのはそれほど難しくないとは思われるが,デバッグのコストも考慮しなくてはならないので,ここでは保留して,もう少し考えてみることにする.

▲BUG3000-1471.ZELに孤立カード「1989」が残っている.⇒どこかで手順に手抜かりがあったのだろう.※このカードを削除して,BUG3000-1470.ZELとして保存した.

Windows 10にダウングレードしてから,VS2017を管理者権限で起動できなくなった.2022/04/14で「Windows 11にアップグレードした」ときと同じ事象だ.ただし,今度は①タスクバー上のアイコンを右クリック→Visual Studio 2017を右クリック→管理者として起動では起動できる.②Visual Studio 2017のショートカットのプロパティ→詳細設定→管理者として実行はオンになっている.前回は,①では起動できなかったが,②を設定して起動できるようになった.今回はその逆で,②では起動できないのに,①では起動できる.タスクマネージャが開いていると起動できるという事象は共通だ.⇒とりあえず,①の方法で起動できることがわかったので,このまま進むことにする.

あれこれやってきたが,呪われたCT3000反例の難問を解くためには,どうしても「極小な反例サンプル」を作るしかないという雰囲気に傾いている.原理的にはそれほど難しくはないが…実際に構築する際の難易度を考えてみよう.外部アプリとして完全に外に出すというのも少し無理がある.現在コラッツツールから直接ゼルコバの木を起動→インポートはできているが,極小反例サンプルを作るためには,少なくとも,①任意のカードNを指定して削除,②系統並び替えの実行,③カウントオーバーしたら処理を中断して結果を返す,④Nの部分木を削除,⑤残りの部分木をファイルに出力…などのことができなくてはならない.

これらのことをすべて外部でやると言うのは現実的ではないので,DLLに作り付けで組み込むしかない.DLL上であれば,ゼルコバの木データのすべてのデータにアクセスして,任意の操作を実行することが可能だから,できない話ではないだろう.VBに組み込むということはあり得るだろうか?現在手操作で行っている反例サンプルの圧縮はすべてゼルコバの木というVBアプリ上でやっているのだから,原理的には実装可能なのではないか?どういうストーリーになるか,書いてみよう.

  1. VBアプリに以下のような処理Pを組み込む
  2. 反例サンプルファイルFをロードする
  3. カードテーブル上のカード数をNとし,反例カウントを0とする
  4. カードテーブルのすべてのレコードRについて以下を実施する
  5. カードRを削除する
  6. 系統並び替えでループカウントオーバーが発生したという結果を何らかの方法で受理して,事象Aとする
  7. 事象Aが発生していないときは,UNDOを実行して,ステップ2に戻る
  8. 事象Aが発生したとき
  9. (1)反例カウントをインクリメントする
  10. (2)Rを基準ノードとして系統並び替えを実施する
  11. (3)Rの直系血族を選択して全削除する
  12. (4)残ったカード数Mをカウントして(R, M)の対をテーブルTに記録
  13. (5)UNDOを実行して,ステップ2に戻る
  14. すべてのレコードを処理するまでステップ4から繰り返す
  15. テーブルTの記録をスキャンして最小のCを与えるRを決定する
  16. カードRを対象にステップ5~11までを実行する
  17. 反例カウント>0ならばステップ3に戻る
  18. ファイルFは極小な反例サンプルである:処理P完了

基本的にステップ6を除けば,すべての手順は現行コードを使って実装可能と考えられる.「カード削除」の戻り値で「ループカウントオーバー」を返すという処理は現行には存在しないが,不可能ではない.現行では「カード削除」の戻り値は次の(主選択)カードの参照番号になっているが,エラーが発生した場合には負値を返すようになっているはずだから,何か適当なエラーコードを決めて,それを返すようにすればよい.ただし,エラー発生の地点から「カード削除」処理の出口までそのエラーコードを受け渡しするのは難しいかもしれないが,グローバル変数に入れておいて,「カード削除」の出口でチェックすればよい.

この処理全体をDLLに組み込むことは難しくないし,その方が効率的でもあるが,あえてVBに独立の処理として組み込む方がベターだと思う.そうすれば,DLL側の既存コードはまったくいじらなくて済むので,既存コードのデバッグとツールのデバッグを完全に切り離すことができる.これが実装できるとかなりおもしろいことになる.「極小な反例サンプル」はいろいろな場面で必要になるが,これまでは手操作でしこしこと作ってきたところが完全に自動化できる可能性がある.「障害」の種別はさまざまだが,ある特定の「障害」が発生しているとき,そのエラーコードを受け渡すだけで,その障害を再現する「極小反例サンプル」が作れるとしたら,これはかなりすごいことではないかと思う.これはやってもやらなくてもよいことではなくて,「MUST」だと思う.

実装に移ることにしよう.VBにはすでにこの種のテスト用ツールのセットが「包括自動テスト」として確立している.たとえばその中には,全体図テスト,親族図テスト,完全木テスト,パックマン全点/単点テスト,ハーレム全点/単点テスト,ランダムインポートテスト,ファイルオープンテストなどがある.「極小反例サンプル」生成ツールはテストツールではないが,ある意味でそれらよりも強力なツールになるだろう.VBアプリは通常の使い方もできなくてはならないので,やはり最初からメニューで起動するようにしておく必要がある.

エラーコードとしては,ERR_COMPLETETRIBEというのがあるので,これを使うことにしよう.TRIBEBOX::CompleteTribeBoxはブール値を返す関数なので,戻り値には代入できない.ここで例外をスローしたらどうなるのか動作を見てみよう.これまで見た限りではノーマルに描画できるときにはループカウントが50を超えることはなかったと思われるので,REDLINEも50にしておこう.⇒StackTribeGeneのトラップでエラーコードがERR_STACKTRIBEGENEに切り替わっている.また,TOPOLOGY::SetPhaseでフェーズ遷移エラーが起きる.⇒例外をスローすると,「検定に失敗しました」でアプリ終了してしまう.やはり,グローバル変数で渡すしかなさそうだ.⇒fatalerrorという変数があるので,流用してみよう.(わたしはミニマリストなのでできるだけ変数の数は増やしたくない…)

UNDOBASE::CommandStartでエラーコードをリセットし,CommandEndで渡すようにしようとしたが,UNDOBASE::CommandEndではまだ系統並び替えが実行されていない.それを行っているのはUNDOSYSTEM::CommandEndだ.fatalerrorではダメなようだ.どこかでリセットしているのだろう.KAKEIZU::closeFamilyBaseでゼロを代入している.ERR_COMPLETETRIBE=-3051だ.⇒mZelkova::mDeleteCardで戻り値を書き換えている.⇒いや,違う.FAMILYTREE::DeleteCardDataはCommandEndの戻り値を無視している.⇒いや,ほとんどのコマンドがそうだ.⇒Z.mDeleteCardまではエラーコードが通った.

カード削除を実行しているVBのDeleteFuncでは,Z.mDeleteCardの戻り値をCurrefnumに格納し,Z.DeleteCountを返している.極小反例ツールではZ.DeleteCountを直接呼び出す作りになると思われるので,ここまででよいことにしよう.次に,メニューコマンドを整備しておこう.包括自動テストの下に,「極小反例サンプル生成」というコマンドを新設しておく.この実行メソッドはOpenFileTest.vbにおくことにする.メソッド名はBuildMinimalCounterSampleとし,現在開いているファイルを対象とすることにする.

VBが持っているカードテーブルは実際には一覧表のことだが,カードを削除したり,それをUNDOで復元したりしたとき,カードの並びが保存されているかどうか?ということは当てにできないので,別にカード番号だけを集めた配列を作った方がよい.これを2次元配列として残留カード数を格納できるようにしておけばよいのではないか?

ステップ11で「Rの直系血族を選択して全削除する」としているが,Rの直系血族に属するカード数をカウントするだけでよい.残留カードが最小となるのは,直系血族最大の場合だからだ.ただし,直系血族のすべてのカードではなく,Rの下流系のみをカウントしなくてはならない.つまり,Rの親との関係を切断した上でその直系血族をカウントするようになる.ちょっと厄介だ.親子関係を切断するためにはカードRの個人情報を読み出した上,カード登録操作を行わなくてはならない.(VB上には直接親子関係を切断するようなコマンドはない)

カードRの下流系に含まれるカード数をカウントする手続き:

  1. カードRのカード情報を取得する
  2. Rのカードの父母欄を空欄にして登録する
  3. 図面種別:親族図,親族範囲:直系血族に設定する
  4. Rを基準ノードとして系統並び替えを実行する
  5. 一覧表:表示範囲:系図画面上のカードを一覧表にロードする
  6. 一覧表のレコード数を取得する

これを実装する前に前段の動作を確認してみる.つまり,カード単点を削除してカウントオーバーが,最初のループでどの程度発生するかを見てみることにする.どうも,この方法は非現実的なものであるような気がする.1400点余りの反例サンプルを一度描画するだけで少なくとも1分近くは掛かっている.検定が一周するのに1400回系統並び替えを実行するとすると,それだけで1400分,24時間掛かってしまう.実際には1点を処理するのに3回程度系統並び替えをやり直すので,おそらく,2日ないしそれ以上掛かることになりそうだ.最後の極小解を得るまでにそれを何段繰り返せばよいのか分からないが,少なくとも2, 300日,おそらく1年以上掛かってしまうのではないかという気がする.

必ずしも最適解が得られるとは限らないが,もう少し効率的なアルゴリズムも考えられる.カード単点を削除して,それが反例だと判定された時点でそのカードセットを開始点に切り替えればよい.現行でも,すでに「3」と「22」は反例を生成するという結果が出ているので,それを使えばもっと急速に収束するような動きになるはずだ.「3」ないし「22」が削除できるということを手操作で確認してみよう.⇒1400点もあって,「3」を目視で見つけることができない.メニューバーの検索ボックスはあいまい検索なので,同名カードが663件も出てくる.「検索パネル」では「姓名の完全一致」検索ができるが,悲しいことに,「検索条件にマッチングするカードはありません」.

どうにもならないので,氏名でソートしたものを保存しておこう.mmm…確かに「3」というカードは載っていない.「22」も同様だ.⇒間違えていた.現在行っているテストでは,参照番号ではなく,「氏名」のうちの「姓」を読まなくてはならなかった.作り直しが必要だ.

UNDOSYSTEM::CommandEndで,UNDOBASE::CommandEndを呼び出した後,UndoCurptrが空で停止した.これまでこのようなエラーは出たことがない.⇒修正を誤っている.確かに「姓」には「ノード番号」が入っているが,カード操作では「参照番号」を使わなくてはならない.つまり,「3」ないし「22」のカードではなく,#3ないし,#22のカードでなくてはならない.

#3は「8195」,#22は「8213」,いずれも単身の子どもを1人持つカードだ.確かに,このようなカードは削除できる.これを進めれば,高々Nステップで極小解に達することができるだろう.これなら丸一日で完了する可能性はある.しかし,子孫系をカットする手順が問題だ.要は始系列に属さないノードセットを構成すればよいのだが… この操作をDLL側でやっているのなら方法はいくらでもあるのだが…

VBには先祖並び替えというのがあるから,先祖リストを取ることはできる.先祖リストの先頭を除いて,それに続くノードを対象に,直系血族図を作ってそれを全削除でよいのではないだろうか?この方法の利点は,全体木の先祖ノードを削除して反例になる場合にも対処できるという点だ.(通常はこういうことは起こらないが…)

先祖リストの取得関数 mGetSortList を呼び出すのに,引数に参照番号を入れて渡しているが,これは何に使っているのだろう?⇒この関数は先祖リストだけでなく,子ども並び替えや配偶者並び替えなどにも使う汎用関数だ.先祖リスト取得の場合にはこの値は参照されていない.リストはSortListに格納され,バックアップを指定すると,InitialListにも同じ値が保全される.

どうもUNDOが壊れてしまっているようだ.初回2枚のカードを削除したあと,新たに開始したテーブルで12番目ノードを処理中にUNDOで無限ループしている.まとめて大量削除したものをUNDOしているとすればそのようなことも起こり得るが…いや,これはUNDO動作ではなく,UNDOBASE::CommandEndの中で「今回保全したノードの値が更新されているときには今回リストに追記する」ということをやっているところだ.何が起きているのかさっぱり見当も付かない…この処理はUNDOに全面的に依存しているので,UNDOが動かないことには始まらない.UNDOをリセットするというコマンドはあったろうか?AutoMergeTestではresetUndoChainを実行しているが,VBから直接リセットするコードは存在しない.AutoMergeTestでは今回と同様UNDOを使って処理を組み立てている.

UNDONODEやUNDOCOMMANDは,noduleから直接派生したプリミティブなオブジェクトでLISTなどのような要素管理の仕組みは持っていない.DumpUndoChainという関数がある.これであるUNDOコマンドの下にあるチェーンをダンプできる.この関数はUndoProcessから呼び出されている.UNDOBASE::CommandEndにも仕掛けてあった.⇒なぜだろう?確かにむちゃくちゃ長いチェーンが生成されている.コマンドはDELALLCARDだが,完全に無限ループしているように思われる.チェーンには主にCARDLINKとMARGLINKのコピーが保全されているが,カード数は1500より少ないのだから,すべてのカードを削除したとしても,3000を超えるはずはないはずなのに,30000を超えている.一つのカードを削除するとその周辺もバックアップされるから,この数倍,いや,10倍とすれば30000というのは不思議な数ではない.

単点を削除したときのバックアップが14点くらいあるので,確かにそのくらいにはなるかもしれない….当然その大半は重複とみられる.どうすればよいか?保全の対象ノードに何か目印を付けるしかないのではないか?しかし,UNDOで保全されていると言っても,時間経過によって変化するから,そのときの「現時点」においてすでにバックアップされているか否かを判定できるようになっていなくてはならない.従って,フラグのようなものではなく,何か計数的なものが必要だ.UNDO開始のときにNOを決定し,開始から終了までの間に保全されたオブジェクトにはそのマークNOを書き込んでおくというのはどうか?

これはシステムに1個だから,UNDOBASEないし,UNDOSYSTEMの静的変数とすべきだろう.グローバル変数でもよいかもしれない.UndoCounterというファイル内の静的変数を定義してみた.初期化はUNDOリセットでよいだろう.いや,現行でもUNDOBASE:etUndoListでは,「Undoリスト上にobjectの複製がすでに存在する場合はFalseを返す」ということになっているのだが…SetUndoListには正・負・ゼロの3モードがあり,正がオブジェクトの生成,負がオブジェクトの削除,ゼロがオブジェクトの更新に割り当てられている.SetUndoListでは更新の場合以外は,無条件ですべてのオブジェクトを保全している.これは見落としを避けるためという理由ではないかと考えられるが,一つのコマンドチェーン上に同じオブジェクトが複数存在する意味はないと考えられるので,すべて弾くということにしてみたい.

「部分図オブジェクトは更新する@20180207」というコメントもある.これはSetUndoListの第3引数がUNDO_COPYの場合には上書き更新するというものだ.よくわからないが,ちょっと無視しておこう.

▲上記エラーが再発した.UNDOSYSTEM::CommandEndで,UndoCurptrが空で停止.

確かに,事後にオブジェクトを更新するということはやっている.なぜこういうことが必要なのか調べる必要がある.UndoCurptr->topUndoが空のときには,PergeZenpoChainで「前方コマンドチェーンをカット」している.このケースでは初回のUNDO処理であり,かつtopUndoが空であるため,UndoCurptrまで削除されているものと思われる.つまり,このような状態はあり得ると見るべきではないか?

▲BaseLink空により,FAMILYTREE::RestoreBaseCardで停止した.その後,バックアップタイマーでファイルをバックアップ中(!topology->SenzoOffList->count)で停止した.

 

TC3000という呪われたサンプル

TC3000という呪われたサンプルの呪縛をなんとかして解かなくてはならない.TC3000の内容をまるごと包含しているTC4000などのもっと大きいサンプルは容易に描画できているのに,このサンプルだけは収束しないという理由を是が非でも突き止めなくてはならない.さもなければこのソフトは永遠に陽の目を見ることはないだろう.いや,むしろ,このようなサンプルを与えられたことは法外な幸運であったと考えるべきかも知れない.⇒多少の進展はあった.

TC3000は4720点のカードを含むゼルコバの木的には巨大系図だ.三極検定では系図図面上のすべての描画要素の座標を調整して「最適配置」を実現しようとする処理だが,下流での調整は上流にも影響を与え,上流での調整は下流にも影響する.さらに,「計算上の誤差」という問題があるため,完全な厳密値を用いると収束できない場合がある.この問題は系図木の規模が大きくなればそれだけ累積的なものになる.

TC3000サンプルの出力するADLファイルをテキストエディタで直接編集して,5461という終端ノードを除去してやれば,有限時間内(loopcnt=67)に描画することができる.テスト回数3000という設定ではその2倍の5999までの奇数がテストされるから,5461という奇数はテスト対象に含まれる.このノードは子どもを持たないので,ルートノード1の直下の子ども枠の中で配置上の制約を持たないいわば,フロート状態にあると言える.ただし,このTC3000-1サンプルを読み出すためには,MAXIMALGRAPH::MergeUpperSegmentで同一セグメントと認定されるための条件を緩和する必要があった.

MergeUpperSegmentでは,対象結婚枠の「結婚点一致」という条件が成立すれば,結婚枠とその吊元である親ノードを同一セグメントと認定する.正確には,「誤差の範囲で結婚点が一致し,かつ吊り位置の子ノードの人名枠と親ノードの人名枠が水平座標でみて交差していること」という条件だ.現行では「誤差の範囲」として3という数が採用されている.これを12まで緩和することでようやく解に収束した.

image

このサンプルにもう一度5461を1の子ノードとして追加すると,再び収束不能状態に戻ってしまう.ただし,ゼルコバの木では子ノードは兄弟ノードの末尾にしか追加できないので,末弟の85の後ろに続くことになる.この図式はオリジナルのTC3000よりは容易に解けそうに見えるのだが,なぜか失敗している.どのような機序でこのような無限ループが発生しているのかを解析したいのだが,何せサンプルが大き過ぎて手も足もでない.というか,途方もなく時間コストばかり浪費するものになってしまう.「手に負えない問題 (intractable problem)」の典型だ.

このような場合には「事象を再現する最小サンプル」を作成するというのが定石だ.そこで,手始めにまず,TC3000-1上で末弟ノードの85とルート1の親子関係を切断してみた.この図式はloopcount=42で描画できる.この図式にノード1の子どもとして「5461」を追加する.これをTC3000-1+1とする.これで,この系図の登録カード数は4720点に戻った.末弟ノードの「85」は1との親子関係は切断されているが,系統としては残っているので,もう一度1の子どもとして復活させると事象が再現してしまうことは明らかなので,別のカードとして性別が女子のカード「85」を追加してみる.これで登録カード数は4721点になるが,問題なく描画できた.この図面をTC3000-4722としておこう.

▲アプリ終了しようとして,下記のエラーが出た.このエラーは前にも見たことがある… メニューバーの「名前検索」に関係するものだ.

image

TC3000-4722の女子カードの「85」に子ども「X」を追加したところ,事象が発生した.つまり,事象を再現するためには,かならずしも「85」の長い子孫系は不要ということになる.⇒試してみよう.TC3000-1+1を開いて,「85」の直系血族を全削除してみる.⇒ハングしてしまったようだ.「85」はこの図面では別系統(孤立した系列)になっているので,描画には影響ないはずなのだが…制御を失っている.⇒1点づつ削除ですべてのカードを削除することはできた.カード数は4618点.このファイルをTC3000-4618.ZELとして保全しておこう.

▲TC3000-1+1から「85」の系統を全削除しようとしてハングした.

ルート1の子ども枠にもう一度「85」を追加して4619点とする.これをTC3000-4619.ZELとして保全しておこう.

image

この図面では「5461」と「85」はともに子どもを持たないので,前方の「5」に隣接するところまで前方配置されている.

image

この状態で「85」に子どもを一人追加してやれば事象が発生することは明らかだ.「5461」と「85」が並んでいる必要はないと推定されるので,「5461」を削除し,その上で「85」に子ども「X」を追加してみる.⇒確かに事象が発生する.TC3000-4618.ZELの「5461」に子ども「X」を追加しても同じことが起こるはずだ.⇒再発する.元の図面の裾の方をカットしてみた.かなり大きい部分をカットしているが,今回は問題なく削除できた.3637点になったので,これも保全しておく.

image

▲全削除したあとの画面下部のステータスバーで表示カード数の値が変化していない.全カード数は変化している.⇒TC3000-3637.ZELを開いてみたら,カード数は3638/3638になっている.つまり,全カード数の表示も間違っている.

TC3000-3637.ZELは実際には3638点なので,TC3000-3638.ZELとリネームしておこう.このサンプルの「5461」に子ども「X」を追加しても,事象は発生しなかった.つまり,このサンプルの裾刈りは少し過剰だったようだ.もう一度,TC3000-4618.ZELに戻ってカットし直してみよう.今回は少し控え目にしてみたがどうだろう?点数は4382と出ている.⇒ダメだ.やはり描画できてしまう.

image

少なくとも結婚枠が接触しているポイントはすべて残す必要がある.

▲拡張選択でマウスをウィンドウ枠外までドラッグしてスクロールしているように見えるが,実際には同じ場所に留まっている.

!とんでもないことが起こってしまった!ノードを削除してより簡略なグラフを作っている途中で事象が発生してしまった.少なくとも4165点より小さな木だ.この作業の途中で孤立点が2点発生していたので,何か操作を誤っていた可能性はある.せめて,そのノード番号だけでも控えておけばよかったのだが… いずれにしても,この事象はグラフの大小にはよらないということだけは確実だ.だとすれば,もっとずっと小さい反例サンプルを作れる可能性もあるということだが…

!助かった!タイムアウトでブレークしてくれた.

image

いや,三極検定にはタイムアウトはない.ループカウントオーバーだ.デフォルトではかなり大きい数になっているが,放置しておいたので,最後に脱出できた.⇒これで少しだけ小さい反例サンプルを手に入れることができた.カード数は4154だ.CT 3000-4154.ZELとして保存した.このサンプルではルート1が孤立ノードになっている.

image

「5461」の子どもとして追加した「X」は入っていない.1の子どもは5人で末尾の子ども「5461」は子なしだ.このカードを削除してみよう.⇒カウントオーバーになった.つまり,このカードは障害の原因ではない.しかし,出てきた図面には1しか表示されていない.⇒もう一度試してみよう.⇒今度は1枚だけカード数が減った図面になった.一応これも保存しておこう.CT 3000-4153.ZELだ.それにしても,なぜ1しか表示されなかったのか?⇒親族図だった可能性がある.実際,親族図(直系血族図)としたらそういう図面が出てきた.

image

ただし,実際には1にはまだ4人子どもが残っているので,図面としては間違っている.ループカウントオーバーで強制ブレークしているためとも考えられるが…それでも,おかしい.⇒全選択すると一覧表上では全選択状態になる.⇒倍率が100%だったためだ.倍率100%では1の周辺には何もない状態になる.兄弟連結線が描画されていないのはおかしいが,それはバグということかもしれない.「画面に合わせてズーム」で全体が見えるようになる.1の水平線は消えているが,それ以外は表示されているので,配置上の問題かもしれない.

「5」と「1」を切断したら,ノーマルに描画できた.ただし,親族図から全体図に切り替えて,下記のエラーになった.

image

これは単なる偶然だ. (snum == 96423)で停止するというパッチが入っていた.しかし,「1」→「5」を切断するだけでここまで形状が変わるのはなぜだろう?

image

「5」の系統を全削除してみよう.⇒またレッドラインオーバーになった.どうもなんだか訳がわからないことになってきた.「5」の全系統を削除したつもりなのだが,まだ「5」の子どもたちが残っている.削除操作は系統並び替えに先行して実施されているはずだから,系統並び替えでエラーになる動作の影響を受けていないはずだが…しかも,「5」自体残って,遠いところで孤立点になっている.前にも「全削除」でハングしたことがあるので,「5」とその下流(の一部)が残っているのは,「全削除」のバグである可能性はある.

image

このグラフは4017点だ.これも保存しておこう.⇒何か操作を間違えたのだろうか?「5」の系統を削除したつもりだったが,「1」が消えてしまっている.この4017点のノードはすべて「5」の子孫だ.おそらく「全選択」の誤動作と思われるが,図面を縮小表示しているので,「誤操作」の可能性もある.いずれにしても,この図面の先祖ノードが「5」であることは間違いない.「5」には子どもが6人いる.{ 13, 213, 3, 3413, 53, 853 }だ.5→853の関係を切断してみよう.

▲全削除ではなく,1点づつ削除するようにしてみたが,どうも一部やり残しが出ている模様だ.

▲ステータスバーの基準カード,現参照カードの値が実際と一致していない.⇒上記,表示カード数の更新の問題と同根だ.

3997点まで縮小したが,まだレッドラインは止まらない.先祖ノードは「5」に変わっている.一旦これを保存しておこう.「5」にはまだ,子どもが5人いる.末弟の53の系統を削除してみよう.⇒「53」の系統には1931点のノードが含まれるが,その血統図自体壊れている.これ自体が反例サンプルなので,「画面上のカードを保存」で保全しておく.ファイル名は53直系血族図.ZELとする.

他の系統も調べてみることにする.その前に「53」の系統を削除してしまおう.⇒SeriaiizeHeaderエラーが起きた.

image

緊急退避ファイルに保存できないというメッセージが出ていたが.そのあと,SaveFamilyTreeのエラーが出始めて,止まらなくなった.

image

image

このエラーは切りなく出てくるので,やむを得ずアプリを強制終了した.デスクトップには反例サンプルファイルが生成されているので,多分最後の状態を復元できるだろう.⇒いや,反例サンプルは大量生産されているが,どれも3997点で55系統削除後のファイルになっていない.「53直系血族図.ZEL」を調理してみることにしよう.このサンプルは1931点だ.このサンプルには「5」が残っていて,その子どもが「53」だ.「53」には子どもが4人{ 141, 2261, 35, 565 } あるが,末子の「565」を切断してみる.⇒この系統はかなり小さく,4人しか入っていない.全削除してみよう.

53→35のリンクを切断して,MargTakeChildのエラーになった.

image

このエラーは繰り返し出てきたが,なんとか収まった.どうも「35」の兄弟2人を除いたカードはすべて「35」の血統のようだ.「2261」の系統というのも残っている.これも削除しておこう.⇒これで1908点になったが,まだ崩れたままだ.

image

このサンプルをCT 3000-1908.ZELとする.先祖ノードの「35」には,子どもが5人いる.末子の「93」系統を抹消してみる.このノードは3倍数だ.その上の「5973」も同様だ.第3子の「373」を抹消する.この系統の部分図を取ろうとして下記エラーになった.

image

部分図が動作していないので,全体図に戻って「373」の直系血族図を取ることにする.「373」の直系血族図は描画可能なようだ.一応これを保存しておこう.いや,「373」ではなくて,「35」の直系図になっていた.おかしい.いつの間にが描画可能になっている.「93」と「5973」を削除した時点で障害は解消していたのではないか?現在,1906点なので,確かに2点しか削除されていない.もう一度やり直してみよう.このサンプルも一応CT 3000-1906.ZELとして保存しておく.

2点削除してもレッドラインオーバーになる.⇒多分,35→373の切断で解けたのだろう.⇒確かにそのようだ.いまのところ,この1906点が最小反例サンプルということになる.これをBUG3000-1906.ZELとして確保しておこう.「23」の切断でも不良が起こる.ただし,これを復元して兄弟順位が1493→ 373→ 23のように変化すると,収まってしまう.子ども並び替えで元の順序に戻すと,再発するようになる.しかし,長子の1493の切断では不良は解消せず,むしろもっと甚だしいものになる.この系統はおそらく削除できるのでやってみよう.

これで先祖ノード「35」の子どもは「23」と「373」の2人だけになった.おそらく,そのどちらを切断しても収まるようになっていると思われるが,一応確かめてみよう.いや,その前にこのサンプルを保全しておいた方がよい.現在1900点なので,BUG3000-1900.ZELとして保存する.この図面は信じられないレベルでひどいものになっている.

image

予想通り,上記2点の切断では不良は解消する.また,兄弟順序を逆転した場合には,下図のような図面が出力される.それぞれの系統を比較するために,先祖ノードの「35」を抹消した図面を作ってみよう.

image

2つの系統を分離したときの図面も見ておこう.ただし,この図面には少し疑問がある.

image

左側の図面は系統並び替えを実施していないように見える.確かにそのようだ.左の系統の先祖ノード「373」で系統並び替えすると,下図のようになり,しぼんでいた風船に空気を入れたように急膨張する.

image

系統並び替えは始系列だけが対象となるのではなく,すべての系列を対象としているので,独立系統だから系統並び替えが掛からないということはあり得ないと思われるのだが… これについては別途調べなくてはならないが,いまのところは三極検定が収束しない問題に集中することにする.BUG3000-1900.ZELは横に広がった図面になっているので,縦書きで表示してみることにしよう.縦方向なら多少寸法を大きくすることができる.人名枠高も少し増加させてみた.

image

中吊りにしたらどう見えるのかも試してみよう.⇒大勢には影響しない.「23」と「373」の2系統は世代高さに大きな差がある.もし,この2系統の干渉による現象であるとすれば,下の方の世代をカットしても事象は再現できるのではないかとも思われるのだが,やってみたところそのようなことはなかった.⇒いや,中吊りの設定ではあるが,ある程度までカットはできる.ただし,それを過ぎるとやはり解けてしまう.

image

この図面は1303点だが,一応取っておこう.GOO3000-1303.ZELとしておいた.下図を見ても分かる通り,23と373の系統的な(水平的な)干渉などではないことは明らかだ.

image

かなりひどい図面が出たので保存しておこう.UNDOが機能しているかどうかを確認してみよう.⇒問題なさそうだ.ただし,一度以下のようなエラーが発生した.

image

反例サンプルは1353点まで圧縮したが,そろそろ限界に近い.BUG3000-1353.ZELを極小な反例サンプルとして保全した.

Windows 11 にアップグレードした

いきなりだが,面倒くさいのでWindows 11に移行することにした.画面の外観は,けばけばしたところが一掃されてわたし好みに近いものになった上,とりあえず通常の作業で支障を来たすようなこともなさそうだという見極めも付いたので,ともかくしばらくこれで運用することにした.大量のファイルコピーで以前より少し遅くなったような感じはする.エクスプローラで詳細モードで表示したときの行間が広くなっているのは気に入らないが,まぁ,しばらく使っていれば慣れるだろう.え,もちろん「ウィジェット」はオフになってますよ.

三極検定は個別系列内の要素の配置を決定する処理で,①結婚枠の吊り位置の調整,②結婚枠の衝突の回避,③要素間の距離を詰めてコンパクト化の3つの処理から構成される.水平セグメント検定と呼んでいるのは,この3番目のコンパクト化に関わるものだが,レイアウトを崩さずにコンパクト化するためにはあるまとまった要素のグループを同時に移動する必要があり,かなり技巧的なものにならざるを得ない.テスト回数3000のサンプルで起きている不良は水平セグメント検定の誤動作によるものと考えられるが,これを追跡するのはかなり難しい.

これまで使えていたSUW(ShowUnderWear)というデバッグ用のツールが使えない状態になっている上,巨大サンプルに対応してメモリ使用量を削減するために,水平セグメント検定で個別系列ごとに確保していた作業域をシステム全体で1個にしてしまっているため,セグメント番号による色分け表示というのもできない状態になっている.SUWというのはある種の例外処理で,プログラム実行中のどのタイミングでも(書きかけの)図面を画面に描画することができるという強力なツールだったのだが…SUWでは特定の系列を描画対象に指定することができるようになっていたはずなので,まだ工夫すれば何とかなる可能性がある.まず,それを追求してみよう.

コラッツ特注版ではメモリを節約するために,MAXIMALGRAPHのsegments配列とloosebox配列を外部に追い出して静的変数としているが,MAXIMALGRAPH自体は個別系列で保持するようになっている.しかし,MAXIMALGRAPHオブジェクトはセグメント検定中しか参照されていないはずだから,システムに1個あれば十分なのではないだろうか?少なくとも当面はセグメント検定を広域化するという構想は持っていないので,徹底してしまった方がわかり易いと思う.修正してみよう.⇒いや,やはりそこまでやるのはやり過ぎかもしれない.事後にsegmentcntなどを参照する場合がある.これらは個別系列で保持するしかない.⇒いや,そういう箇所は多くはない.というより,むしろ積極的にそうした方がよい.この修正に関わる箇所には以下がある.

  1. TRIBELIST::IsTribeComplete
  2. NAMEBOX::Group
  3. NAMEBOX::Group
  4. MARGBOX::clear
  5. NAMEBOX::Clear
  6. NAMEBOX::CLEAR
  7. TOPOLOGY::checkRIG
  8. Bobject::initialize
  9. Bobject::SetBranch

これらの箇所でセグメントを操作するのはむしろ危険だ.MAXIMALGRAPHを共有した上で,ReleaseSegmentを実行しないようにすれば描画時にもアクセスすることができるだろう.ReleaseSegmentの呼び出しは,①TRIBEBOX::HorizontalSegmentの出口,②TRIBEBOX::CheckMaximalSegmentの出口(単独で呼ばれた場合),③TRIBEBOX::CheckMaximalCompaction,④MAXIMALGRAPH::clearSegmentの4箇所ある.④は必須だが,①,②,③は止めることができる.

この修正をやってみて気付いたことがある.MAXIMALGRAPHを共有するということは,広域検定を実装するという方向に向かっているのではないかという点だ.三極検定は基本的に系列単位の処理なので,いきなりそれを広域化するというのは現実的ではないが,「共有」という語が「広域」を含意していることは明らかである.これで,セグメントのカラー表示はできるようになったが,SUWが動かないのでは始まらない.

どうも,どこか壊してしまったようだ.急に動かなくなってしまった.⇒TableSort.cppを差し替えて動作するようになった.TOPOLOGY::MakeLeastWindowで実行しているTRIBELIST::HeapTribeBoxesを関数の冒頭で実行するようにして,画面が表示できるようになった.理由はよく分からないが,これで良しとしておこう.SUWとセグメントのカラー表示が復活したので,デバッグを再開する.さて,どうやって追いかけたらいいだろう?

少し動作がおかしい.VS2027を管理者モードで起動しても立ち上がってこない.管理者モードでなければ起動できる.おかしなことに,タスクマネージャを開いているときには,管理者モードでも起動できるという動作になっている.管理者モードでないと不都合な場面というのはそれほどないので,運用的にはさほど不便ということもないような気はするが,管理者モードでないとデバッグ中にゼルコバの木のテーマを登録したりなどのこともできなくなる.タスクバーのアイコン→ 右クリック→ Visual Studio 2017→ 右クリック → プロパティ→ 詳細設定→ 管理者として実行をオンにして,ワンクリックで起動できるようになった.

SUWはまだ動いていない.HeapTribeBoxesの前にstackTribeGeneを実行することで描画できるようになった.stackTribeGeneは系列内部の描画要素を系列世代枠の集約する関数,HeapTribeBoxesはその計算を元に系列枠全体の矩形領域を計算し,それを集約して系図枠全体の矩形領域を計算するものだ.これで見ると,どんなことになっているのかをはっきりつかむことができる.

image

左端の孤立点は1だと思っていたが,違う.5, 5461,  85の3人兄弟だ.

image

1にはこの他に,1365, 21, 341 の合わせて6人の子どもがいる.このうち,1365,21 は3倍数なので,子孫につながるのは,341,5,5461,85の4つだけだ.このうちの3つは左端で孤立しているので,右側には1系統しかないことになる.上の図でおかしいのは,3人兄弟のうちの真ん中の5461の下に垂線がないことだ.実際,カード画面で見ても5461は子どもを持っていない.しかし,上記したように5461は3倍数ではないので,子孫がいなくてはならない.

ADLファイルで見ると,そもそも 5461 というカードの登録がない.15461というカードはある.⇒見落としていた.1の子どもの位置にある.ただし,5461を親とするレコードがない.これはかなりおかしい.つまり,ADLの出力自体に誤りがある.5には13,213,3,3413,53,853 の 6人の子どもがいる.85は,113,1813,453,7253 の4人の子がある.このADL出力の誤りを見つけなくてはならない.

明らかにGetTheNumberの論理には誤りがある.⇒いや,違う.5461はテストの対象となる奇数そのものだ.従って,5461が終端ノードであることは間違いない.もし,5461→1というパスがあるのなら,1に5461が直結しているのは間違いではない.実際,5461*3+1 = 16384 = 2^14だ.従って,ADLデータは間違っていない.確かにこの不良は結婚枠を一律中吊りにしていることに関係していることは間違いない.⇒中吊りを強制しないモードで走らせてみたが収束しない.

TC(Test Count)4000のサンプルでは中吊りの場合と同等の回数(loopcnt=32)で収束している.どうもこのTC3000というのは何か特殊なサンプルになっているのだろうか?この計算自体が収束しないある種の散逸構造的なトラップに陥っているのだろうか?