Design a Recursive File-Search API

Problem Statement

You are tasked with building a robust file-search backend service for a multi-tenant cloud environment. The service must allow users to search for files within a given directory while strictly preventing unauthorized access to the underlying host filesystem.

Implement the class FileSearchService with the following interface:

class FileSearchService:
    def __init__(self, allowed_root: str):
        """
        Initializes the service with a restricted root directory.
        No search operation should ever access files outside this root.
        """
        pass

    def search(
        self, 
        start_path: str, 
        query: str, 
        max_depth: int = -1, 
        follow_symlinks: bool = False
    ) -> list[str]:
        """
        Recursively searches for files matching `query` within `start_path`.
        Returns relative paths from `start_path`.
        """
        pass

Requirements and Validation

1. Path Boundary & Security:
   • start_path can be relative or absolute, but its canonical path must resolve within allowed_root. If it escapes allowed_root (e.g., via .. or symlinks), raise a PermissionError("Access denied: path escapes allowed root").
   • If start_path is empty or None, raise ValueError("Path cannot be empty").
   • If start_path does not exist, raise FileNotFoundError("Directory does not exist").
   • If start_path exists but is not a directory, raise NotADirectoryError("Target is not a directory").
2. Search Logic & Matching:
   • A file matches if query.lower() is a substring of the file's name (case-insensitive).
   • max_depth defines how deep recursion can go. max_depth = 0 searches only start_path. If max_depth = -1, search depth is unlimited.
3. Symlink and Permission Handling:
   • If follow_symlinks is False, symbolic links to directories must not be traversed.
   • If follow_symlinks is True, circular symlinks must be detected and skipped without entering infinite loops. Any symlink resolving outside allowed_root must be skipped.
   • If an operating system permission error occurs while reading a subdirectory or file, silently skip that entity and continue searching remaining items.
4. Determinism:
   • The returned list of matching file paths must be relative to start_path, using forward slashes (/), and sorted lexicographically in ascending order.

Example

Allowed root: /var/workspace
Directory structure:
/var/workspace/project/
  ├── notes.txt
  ├── src/
  │   ├── app.py
  │   └── app_test.py
  └── secret_link -> /etc/passwd

service = FileSearchService("/var/workspace")
results = service.search("/var/workspace/project", "app", max_depth=2)
# Returns: ["src/app.py", "src/app_test.py"]

Constraints

• Directory tree depth <= 100 levels.
• Total files in directory tree <= 100,000.
• Query length <= 255 characters.