Symlink Loop Detector in Recursive Directory Walk
Recursive directory traversals following symbolic links can enter infinite recursion when symlinks point back to parent directories. Tracking visited file system inode and device identifiers (st_dev, st_ino) halts cycles instantly and avoids recursion depth crashes.
# Tracking visited filesystem inodes:
st = os.stat(path)
inode_key = (st.st_dev, st.st_ino)
if inode_key in visited_inodes:
return # Cycle detected!
visited_inodes.add(inode_key)
# Symlink Loop Detector in Recursive Directory Walk Calling `os.walk(followlinks=True)` on a directory tree containing a circular symlink (e.g. `repo/sub -> repo`) will loop until Python throws `RecursionError: maximum recursion depth exceeded` or runs out of memory. 🛑🔄 Checking canonical path strings with `os.path.realpath` helps, but the POSIX standard provides an absolute guarantee: every file or directory on a system is uniquely identified by its **Device ID (`st_dev`)** and **Inode Number (`st_ino`)**. By maintaining a `set` of `(st_dev, st_ino)` tuples visited during the walk, any recursive re-entry into an already-visited directory is immediately detected and skipped. ```python import os visited = set() stat = os.stat(path) inode_id = (stat.st_dev, stat.st_ino) if inode_id in visited: # Circular reference detected! pass ``` ## Pop Quiz Why is comparing `(stat.st_dev, stat.st_ino)` superior to comparing file path strings for cycle detection? - [ ] Path strings change depending on relative references and symlink names, whereas (st_dev, st_ino) uniquely identifies the physical disk inode. - [ ] The st_dev tuple automatically encrypts directory names using SHA-256. - [ ] Path string comparisons raise RecursionError after 100 iterations. - [ ] Because Linux filesystems allow duplicate path strings on the same partition. ## Real-World Challenge Implement `safe_directory_walk(root_node)` on a simulated filesystem tree. Each node has `name: str`, `inode: int`, `is_dir: bool`, and `children: list`. The walker must traverse all directories, record node names in a list, track visited inode IDs, and avoid infinite loops when circular references exist. <details> <summary>Solution</summary> ```python class MockFSNode: def __init__(self, name: str, inode: int, is_dir: bool = False, children: list = None): self.name = name self.inode = inode self.is_dir = is_dir self.children = children or [] def safe_directory_walk(root: MockFSNode) -> list[str]: visited_inodes = set() traversed_names = [] def _walk(node: MockFSNode): if node.inode in visited_inodes: return # Skip cycle visited_inodes.add(node.inode) traversed_names.append(node.name) if node.is_dir: for child in node.children: _walk(child) _walk(root) return traversed_names # Verification # Build tree with circular symlink: Root -> Lib -> Vendor -> Root root = MockFSNode("root", inode=101, is_dir=True) lib = MockFSNode("lib", inode=102, is_dir=True) vendor = MockFSNode("vendor", inode=103, is_dir=True) readme = MockFSNode("README.md", inode=104, is_dir=False) root.children = [lib, readme] lib.children = [vendor] vendor.children = [root] # Circular link back to root! traversed = safe_directory_walk(root) assert traversed == ["root", "lib", "vendor", "README.md"] ``` </details>