Keep a path inside its root through symlinks

A static file server maps request paths onto a directory that contains symbolic links. Normalising .. and then checking a prefix is not enough once links are involved, so resolve each path the way the operating system would and check where it really lands.

root is the served directory: an absolute path such as /srv/site, without a trailing slash, never / itself, and with no symbolic link at or above it. request is the untrusted path, always taken relative to root (leading slashes are ignored). links maps the absolute path of every symbolic link (single slashes, no trailing slash) to its target. A target starting with / is absolute, resolved from the filesystem root / (not from root); any other target is relative to the directory that contains the link. Every path that is not a key of links is an ordinary file or directory, whether or not it exists.

Start at root and take the components of request (split on /) one at a time, from the left:

• An empty component or . is skipped.
• .. moves to the parent of the current path. The parent of / is /.
• Any other name is appended to the current path. If the result is a key of links, the link is expanded instead: the current path becomes / for an absolute target, or stays at the link's directory for a relative one, and the target's components go in front of the components still waiting.

More than 40 expansions in one resolution means a loop, and the answer is null (None in Python). Otherwise return the resolved path, written with single slashes and no trailing slash, when it is root or inside it, and null when it is anywhere else. Inside means below root as a path, so /srv/site2 is not inside /srv/site.

Examples:

• resolve_in_root("/srv/site", "img/logo.png", {}) returns "/srv/site/img/logo.png".
• resolve_in_root("/srv/site", "/../site/./css//main.css", {}) returns "/srv/site/css/main.css": it leaves root and comes back, which is fine.
• resolve_in_root("/srv/site", "docs/../index.html", {"/srv/site/docs": "/etc"}) returns None: docs is a link to /etc, so .. from there is / and the file is /index.html. A lexical check would have said /srv/site/index.html.