循環しうる依存グラフの連鎖自動補正は、位相ソートでなく「1ノード最大1回補正」のwave収束+最終再検証で解く
設計判断
アルゴリズム
依存関係解決
判断
原則
ある値の変更が依存グラフ(親→子、条件→ターゲット)を伝播して他の値を自動補正する必要がある場面(フォームの選択肢連動、設定の継承、スプレッドシート的な参照更新など)で、依存グラフが循環しうる、あるいは事前に非循環であることを保証できない場合の設計判断。
問題
素直に実装すると、(1) 位相ソートやトポロジカル順序で依存を1周回で解決しようとし循環の検出・特別扱いが必要になる、(2) 伝播の途中(各ノードを触るたび)に正しさを検証しようとして、まだ後続ノードが確定していない中間状態を誤って違反判定してしまう、(3) 再帰やループの終了条件を「値が変化しなくなるまで」のような曖昧な収束条件にして無限ループのリスクを抱える、といった問題が起きやすい。
判断基準
- 収束保証は「循環検出」ではなく「1ノードにつき補正は最大1回」で担保する。あるノードを一度補正したら、以後のどの周回でもそのノードを再訪しない(既に補正済み、またはユーザーが明示指定した値は保護対象とし、以後の自動補正から除外する)。この制約だけで、依存グラフが循環していても補正処理は必ず有限回(ノード数を超えない回数)で停止することが構造的に保証でき、事前の循環検出や位相ソートが不要になる。
- 伝播は「dirty フラグ付きの反復(wave)」で行う: 1周回で処理可能なノードを一括処理し、1つでも新規補正が発生したら次の周回へ進み、新規補正がゼロになった時点で打ち切る。周回内の処理順序に依存グラフの深さ分の遅延が生じても、複数周回を回すことで多段カスケードは自然に収束する(順序を厳密に依存の深さ順に並べ替える必要はない)。
- 妥当性の最終判定は、伝播が収束した後の状態に対して一括で1回だけ行う(最終再検証)。伝播の途中経過に対して都度検証すると、まだ後続の補正が反映されていない中間状態を誤検出することがある(あるノードの補正が別ノードの補正によって後から正当化されるケースなど)。最終状態にのみ検証を集約すると、この種の誤検出を構造的に避けられる。
- 明示的にユーザー/呼び出し側が指定した値は、自動補正の対象から常に除外する(保護集合)。保護集合はグラフの変化伝播の起点(「この値は変わった」という信号)には使うが、値そのものを上書きする対象には含めない。
なぜ
位相ソート方式は、循環グラフを扱うために循環検出・特殊分岐が別途必要になり実装が複雑化する。また依存関係が動的(設定データ由来)で事前に非循環性を保証できないシステムでは、位相ソートの前提自体が成立しない。「1ノード最大1回」という補正回数の上限だけで停止性を証明できる設計は、循環の有無を問わず同じロジックで扱えるため、循環検出のための特別なコードパスが丸ごと不要になる。
適用条件・限界
- 「補正は1ノード1回まで」で正しく収束するのは、各ノードの補正結果が「その時点で分かっている依存元の値」から一意に決まり、後から別の依存元が変わっても同じノードを再度補正する必要がない設計になっている場合に限る。もし補正ロジックが「全依存元が確定するまで複数回に分けて値を調整する」必要がある場合(例: 複数の入力の合議で値を決める)は、この制約は適用できない。
- 保護集合(ユーザー明示値)を补正対象から除く設計は、「暗黙の自動補正より明示指定を優先する」というUX上の要請がある場合に特に重要。明示指定まで自動書き換えの対象にすると、ユーザーが直接設定した値が知らないうちに上書きされる。
検証
- 循環する依存関係(AがBに依存し、BがAにも依存する等)を意図的に構築し、無限ループにならず有限回で停止すること、かつ結果が意図した値に収束することを確認する。
- 多段カスケード(3階層以上の依存チェーン)を構築し、1周回の処理順序を入れ替えても(依存グラフの定義順を逆にする等)、複数周回を経て同じ最終結果に収束することを確認する(順序非依存性の確認)。
- 「値は変わらないが検証だけ必要」なケースと「値が変わって後続に伝播する」ケースを分け、値が実際に変化した場合のみ次周回の対象に含める(変化なしを補正済み扱いにしない)実装になっているかを確認する。