Find the Folder Python Imports a Package From

You run import mypkg and want to know which folder on sys.path it comes from. Write a small model of the search Python runs. It works on a pretend filesystem made of dictionaries, because the grader runs one file of code and cannot create real folders.

def resolve_module(
    sys_path: Sequence[str],
    filesystem: Mapping[str, frozenset[str]],
    module: str,
) -> str | None:

For example, with sys_path = ["", "/venv/site-packages"], a mypkg package in the current folder and another in site-packages, the answer is "". The current folder comes first, so its copy wins.

The pretend filesystem

• sys_path lists folders in search order.
• filesystem maps each folder's path to the names directly inside it. A name is a subfolder when its joined path is also a key in filesystem. Otherwise it is a file.
• Join a folder and a name with f"{parent}/{name}". Keys never end in /.
• The key "" stands for the current folder, so its subfolder mypkg has the key "/mypkg".
• module is one plain name such as mypkg, never a dotted name.
• Names ending in .py, and __init__.py, are always files.

The search rules

For each entry in sys_path, in order:

1. Skip the entry if it is not a key in filesystem.
2. If the entry lists module and its joined path is a folder, look inside. If the folder holds __init__.py, it is a regular package, so return the entry now. If not, remember the entry as a namespace portion and go on to step 3.
3. If the entry lists module + ".py", return the entry. A module file beats a namespace portion in the same folder, and a regular package from step 2 beats the module file.
4. Otherwise move on to the next entry.

When the loop ends, return the first namespace portion you remembered. If there was none, return None. "" is a real answer, the current folder, so test for a remembered portion with is None.

A regular package or module found later wins over a namespace portion found earlier. If /a/pkg has no __init__.py and /b/pkg has one, searching ["/a", "/b"] for pkg returns "/b". If both are namespace portions, the answer is "/a". Real Python would combine both portions into one namespace package, and returning the first one is how this exercise reports that.

The model leaves out the module cache, compiled extension modules, zip files and import hooks. Do not change the inputs. Your code must pass mypy --strict, so check that filesystem.get(entry) is not None before you look inside it.