0853: リロード順序とトポロジカルソート¶

問題¶

importlib.reload() は指定した 1 つのモジュールだけをリロードし、そのモジュールがインポートするモジュールを再帰的にはリロードしません。複数のモジュールをまとめてリロードするには、依存されるモジュールを先にリロードする順序を自分で決める必要があります。

関数 reload_order(deps) を実装してください。

deps は、モジュール名から、そのモジュールがインポートするモジュール名のリストへの辞書です。
対象となるモジュールは、deps のキーと値のリストに現れるすべての名前です。
戻り値は対象モジュール全体を一列に並べたリストで、どのモジュールも、自分がインポートするモジュールより後に現れなければなりません。
この条件を満たす順序は一般に複数あります。結果を一意にするため、次に選べるモジュールが複数あるときは名前が辞書式順序で最小のものを選ぶ、と定めます。
依存関係に閉路がある場合は ValueError を送出します。メッセージは dependency cycle detected です。

制約¶

deps は dict[str, list[str]] で、値のリストに重複はありません。
値に現れる名前が deps のキーに存在しないことがあります（その場合、そのモジュールは何もインポートしないとみなします）。
モジュール数と依存関係の総数は高々 \(10^4\) とします。

例¶

>>> reload_order({
...     "web": ["app", "config"],
...     "app": ["config", "utils"],
...     "utils": ["config"],
...     "config": [],
... })
['config', 'utils', 'app', 'web']
>>> reload_order({"plot2d": ["lines", "text"]})
['lines', 'text', 'plot2d']
>>> reload_order({"moda": ["modb"], "modb": ["moda"]})
Traceback (most recent call last):
  ...
ValueError: dependency cycle detected

発展¶

1 つのモジュール target を変更したとき、リロードが必要なのは target 自身と、target に直接または間接に依存するモジュールだけです。この最小の集合を求め、その集合内のモジュールだけを同じ規則で並べる reload_order_for(target, deps) を実装してください。

参考¶

『Python Distilled』第8章「モジュールのリロードとアンロード」