Select impacted tests through reverse dependencies

Advanced60 min

Implement select_impacted_tests(changed, imports, test_imports). Imports maps each module to modules it imports. Test_imports maps each test name to modules it directly imports. Return sorted test names whose imports intersect the transitive set of affected modules.

Your task

Treat changed as module names already affected. A module becomes affected if it imports any affected module, directly or transitively.
Handle cycles and diamonds without repeated traversal. Changed modules need not appear as keys in imports.
Select each test once when any of its direct imported modules is affected. Return a lexicographically sorted list.
Do not mutate the provided sets, lists, or dictionaries. Empty changes return an empty list.
Assume all names are nonempty strings and input mappings are well formed. Do not attempt dynamic import resolution.
Document that static test selection is an optimization with incomplete dependency information, not a guarantee that omitted tests are irrelevant.

Examples

EXAMPLE 1

Inputselect_impacted_tests({"units"}, {"api":{"units"}}, {"test_api":{"api"}})

Output["test_api"]

Impact flows from the changed dependency toward its importer.

def select_impacted_tests(changed, imports, test_imports):
    raise NotImplementedError