// *****************************************************************************
// Copyright (C) 2024 EclipseSource GmbH.
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License v. 2.0 which is available at
// http://www.eclipse.org/legal/epl-2.0.
//
// This Source Code may also be made available under the following Secondary
// Licenses when the conditions for such availability set forth in the Eclipse
// Public License v. 2.0 are satisfied: GNU General Public License, version 2
// with the GNU Classpath Exception which is available at
// https://www.gnu.org/software/classpath/license.html.
//
// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0
// *****************************************************************************
import { AiConfigurationService, ToolInvocationContext, ToolProvider, ToolRequest } from '@theia/ai-core';
import { CancellationToken, Disposable, OS, PreferenceService, URI, Path } from '@theia/core';
import { EnvVariablesServer } from '@theia/core/lib/common/env-variables';
import { inject, injectable, postConstruct } from '@theia/core/shared/inversify';
import { FileService } from '@theia/filesystem/lib/browser/file-service';
import { FileStat, FileOperationError, FileOperationResult } from '@theia/filesystem/lib/common/files';
import { FileSearchService } from '@theia/file-search/lib/common/file-search-service';
import { WorkspaceService } from '@theia/workspace/lib/browser';
import {
    FILE_CONTENT_FUNCTION_ID, GET_FILE_DIAGNOSTICS_ID,
    GET_WORKSPACE_DIRECTORY_STRUCTURE_FUNCTION_ID,
    GET_WORKSPACE_FILE_LIST_FUNCTION_ID, FIND_FILES_BY_PATTERN_FUNCTION_ID
} from '../common/workspace-functions';
import { extractJsonStringField } from '@theia/ai-chat-ui/lib/browser/chat-response-renderer/toolcall-utils';
import ignore from 'ignore';
import { Minimatch } from 'minimatch';
import {
    ALLOWED_EXTERNAL_PATHS_PREF,
    CONSIDER_GITIGNORE_PREF,
    FILE_CONTENT_MAX_SIZE_KB_PREF,
    USER_EXCLUDE_PATTERN_PREF
} from '../common/workspace-preferences';
import { MonacoWorkspace } from '@theia/monaco/lib/browser/monaco-workspace';
import { MonacoTextModelService } from '@theia/monaco/lib/browser/monaco-text-model-service';
import { ProblemManager } from '@theia/markers/lib/browser';
import { DiagnosticSeverity, Range } from '@theia/core/shared/vscode-languageserver-protocol';

@injectable()
export class WorkspaceFunctionScope {
    protected readonly GITIGNORE_FILE_NAME = '.gitignore';

    @inject(WorkspaceService)
    protected readonly workspaceService: WorkspaceService;

    @inject(FileService)
    protected readonly fileService: FileService;

    @inject(PreferenceService)
    protected readonly preferences: PreferenceService;

    @inject(AiConfigurationService)
    protected readonly aiConfiguration: AiConfigurationService;

    @inject(EnvVariablesServer)
    protected readonly envVariablesServer: EnvVariablesServer;

    private gitignoreMatchers = new Map<string, ReturnType<typeof ignore> | undefined>();
    private gitignoreWatchersInitialized = new Set<string>();

    private _rootMapping: Map<string, URI> | undefined;
    private _allRootUris: URI[] | undefined;

    private homeDirUri: Promise<URI | undefined> | undefined;

    // ── Initialization ──────────────────────────────────────────────────

    @postConstruct()
    protected init(): void {
        this.workspaceService.onWorkspaceChanged(() => {
            this._rootMapping = undefined;
            this._allRootUris = undefined;
        });
    }

    // ── Multi-root workspace structure ──────────────────────────────────

    /**
     * Returns all workspace root URIs (synchronous, cached).
     */
    private getAllRootUris(): URI[] {
        if (!this._allRootUris) {
            this._allRootUris = this.workspaceService.tryGetRoots().map(root => root.resource);
        }
        return this._allRootUris;
    }

    /**
     * Returns a mapping of root names to root URIs.
     *
     * Root names are always the directory basename. When multiple roots share the
     * same basename, only the first (by URI sort order) is addressable by name —
     * the others are still reachable via the `resolveRelativePath` supra-relative
     * check (which examines path segments against all roots).
     *
     * **Known limitation:** duplicate basenames are not disambiguated with synthetic
     * suffixes because agents observe real filesystem paths in terminal output,
     * compiler errors, stack traces, etc. Synthetic names like `app-1` would
     * conflict with those observations and cause more confusion than they solve.
     * A future improvement could let users assign display names to roots.
     */
    getRootMapping(): Map<string, URI> {
        if (this._rootMapping) {
            return this._rootMapping;
        }

        const wsRoots = this.workspaceService.tryGetRoots();
        const sortedRoots = [...wsRoots].sort((a, b) => a.resource.toString().localeCompare(b.resource.toString()));
        const mapping = new Map<string, URI>();

        for (const root of sortedRoots) {
            const basename = root.resource.path.base;
            if (mapping.has(basename)) {
                console.debug(
                    `Multiple workspace roots share the basename '${basename}'. ` +
                    `Only '${mapping.get(basename)!.toString()}' is addressable as '${basename}'. ` +
                    `'${root.resource.toString()}' can still be accessed but may require full paths.`
                );
                continue;
            }
            mapping.set(basename, root.resource);
        }

        this._rootMapping = mapping;
        return mapping;
    }

    /**
     * Returns the root name for a given root URI based on the cached mapping.
     */
    getRootName(rootUri: URI): string | undefined {
        const mapping = this.getRootMapping();
        for (const [name, uri] of mapping) {
            if (uri.toString() === rootUri.toString()) {
                return name;
            }
        }
        return undefined;
    }

    /**
     * Returns the workspace root that contains the given URI.
     * If nested roots exist, returns the most specific (deepest) one.
     */
    getContainingRoot(uri: URI): URI | undefined {
        const roots = this.getAllRootUris();
        const matchingRoots: URI[] = [];

        for (const rootUri of roots) {
            if (rootUri.scheme === uri.scheme && rootUri.isEqualOrParent(uri)) {
                matchingRoots.push(rootUri);
            }
        }

        matchingRoots.sort((a, b) => b.toString().length - a.toString().length);
        return matchingRoots[0];
    }

    /**
     * Converts a URI to a workspace-relative path with root name prefix.
     * Format: <rootName>/<relativePath>
     */
    toWorkspaceRelativePath(uri: URI): string | undefined {
        const containingRoot = this.getContainingRoot(uri);
        if (!containingRoot) {
            return undefined;
        }

        const rootName = this.getRootName(containingRoot);
        if (!rootName) {
            return undefined;
        }

        const relativePath = containingRoot.relative(uri);
        if (!relativePath || relativePath.toString() === '') {
            return rootName; // URI is the root itself
        }

        return `${rootName}/${relativePath.toString()}`;
    }

    // ── Path resolution ─────────────────────────────────────────────────

    /**
     * Resolves a relative path to a URI using a deterministic, synchronous algorithm.
     * No filesystem I/O is performed — the agent is expected to use `<rootName>/<relativePath>`
     * format. If the path cannot be resolved deterministically, an error is thrown.
     *
     * Resolution order:
     * 1. Root+relative: first segment matches a root name → resolve rest relative to that root.
     * 2. Supra-relative: a root's basename appears as a segment, and any preceding material
     *    matches the preceding path components of the root → resolve the trailing portion.
     * 3. Single-root fallback: if exactly one workspace root, resolve relative to it.
     * 4. Error: tell the agent how to format the path.
     */
    resolveRelativePath(relativePath: string): URI {
        const normalizedPath = new Path(Path.normalizePathSeparator(relativePath)).normalize().toString();
        const mapping = this.getRootMapping();
        const roots = this.getAllRootUris();
        const segments = normalizedPath.split('/');

        // Phase 1 — Root+relative check:
        if (segments.length > 0) {
            const potentialRootName = segments[0];
            const rootUri = mapping.get(potentialRootName);
            if (rootUri) {
                const restOfPath = segments.slice(1).join('/');
                return restOfPath ? rootUri.resolve(restOfPath) : rootUri;
            }
        }

        // Phase 2 — Supra-relative check:
        for (const rootUri of roots) {
            const rootBasename = rootUri.path.base;
            for (let i = 0; i < segments.length; i++) {
                if (segments[i] !== rootBasename) {
                    continue;
                }
                const rootPathSegments = rootUri.path.toString().split('/').filter(s => s.length > 0);
                const rootPrecedingSegments = rootPathSegments.slice(0, rootPathSegments.length - 1);
                const pathPrecedingSegments = segments.slice(0, i);

                let matches = true;
                if (pathPrecedingSegments.length > rootPrecedingSegments.length) {
                    matches = false;
                } else {
                    const rootTail = rootPrecedingSegments.slice(rootPrecedingSegments.length - pathPrecedingSegments.length);
                    for (let j = 0; j < pathPrecedingSegments.length; j++) {
                        if (pathPrecedingSegments[j] !== rootTail[j]) {
                            matches = false;
                            break;
                        }
                    }
                }

                if (matches) {
                    const restOfPath = segments.slice(i + 1).join('/');
                    return restOfPath ? rootUri.resolve(restOfPath) : rootUri;
                }
            }
        }

        // Phase 3 — Single-root fallback:
        if (roots.length === 1) {
            return roots[0].resolve(normalizedPath);
        }

        // Phase 4 — Error:
        const rootNames = Array.from(mapping.keys());
        throw new Error(
            `Could not resolve path '${relativePath}'. In a multi-root workspace, prefix paths with the workspace root name ` +
            `(e.g., 'rootName/path/to/file'). Available roots: ${rootNames.join(', ')}`
        );
    }

    async resolveToUri(pathOrUri: string | URI): Promise<URI | undefined> {
        if (pathOrUri instanceof URI) {
            return pathOrUri;
        }

        if (!pathOrUri) {
            return undefined;
        }

        if (pathOrUri.includes('://')) {
            try {
                const uri = new URI(pathOrUri);
                return uri;
            } catch (error) {
            }
        }

        const normalizedPath = Path.normalizePathSeparator(pathOrUri);

        // Reject `..` only when it appears as a path SEGMENT. A filename like
        // `my..file.json` is a legitimate name. `ensureAccessible` normalizes
        // URI-form inputs separately as defense-in-depth (e.g. against
        // percent-encoded `%2e%2e` that bypasses the string-form check).
        if (WorkspaceFunctionScope.hasParentSegment(normalizedPath)) {
            return undefined;
        }

        const tilde = await this.resolveTildePath(normalizedPath);
        if (tilde) {
            return tilde;
        }

        if (WorkspaceFunctionScope.isAbsolutePath(normalizedPath)) {
            return URI.fromFilePath(normalizedPath);
        }

        return this.resolveRelativePath(normalizedPath);
    }

    // ── Access control ──────────────────────────────────────────────────

    ensureWithinWorkspace(targetUri: URI, workspaceRootUri: URI): void {
        const normalized = targetUri.normalizePath();
        if (workspaceRootUri.scheme !== normalized.scheme
            || !workspaceRootUri.isEqualOrParent(normalized, WorkspaceFunctionScope.pathCaseSensitive)) {
            throw new Error('Access outside of the workspace is not allowed');
        }
    }

    /**
     * Asserts the target URI is reachable by AI tools that honor the external
     * allow-list. Allowed when the URI is inside any workspace root, or when it
     * is covered by an entry of the `ai-features.workspaceFunctions.allowedExternalPaths`
     * preference. Workspace-scoped overrides of that preference are dropped when
     * the workspace is not trusted.
     *
     * The target URI is normalized before the check so that literal `..`
     * segments and percent-encoded equivalents (e.g. `%2e%2e`) are resolved
     * away — otherwise the path-prefix comparison would admit traversals.
     *
     * Note: symlinks within allow-listed directories are NOT canonicalized
     * before the check. Only allow-list directories whose contents you trust.
     */
    async ensureAccessible(targetUri: URI): Promise<void> {
        const normalized = targetUri.normalizePath();
        const caseSensitive = WorkspaceFunctionScope.pathCaseSensitive;
        const roots = this.getAllRootUris();
        for (const rootUri of roots) {
            if (rootUri.scheme === normalized.scheme && rootUri.isEqualOrParent(normalized, caseSensitive)) {
                return;
            }
        }
        const allowed = await this.getAllowedExternalUris();
        if (allowed.some(allowedUri => allowedUri.scheme === normalized.scheme && allowedUri.isEqualOrParent(normalized, caseSensitive))) {
            return;
        }
        throw new Error(
            `Access to '${normalized.path.toString()}' is not allowed. ` +
            `Path is outside the workspace and not covered by the '${ALLOWED_EXTERNAL_PATHS_PREF}' preference.`
        );
    }

    isInWorkspace(uri: URI): boolean {
        try {
            const roots = this.getAllRootUris();

            if (roots.length === 0) {
                return false;
            }

            for (const rootUri of roots) {
                if (rootUri.scheme === uri.scheme && rootUri.isEqualOrParent(uri)) {
                    return true;
                }
            }

            return false;
        } catch {
            return false;
        }
    }

    isInPrimaryWorkspace(uri: URI): boolean {
        try {
            const wsRoots = this.workspaceService.tryGetRoots();

            if (wsRoots.length === 0) {
                return false;
            }

            const primaryRoot = wsRoots[0].resource;
            return primaryRoot.scheme === uri.scheme && primaryRoot.isEqualOrParent(uri);
        } catch {
            return false;
        }
    }

    // ── External path support ───────────────────────────────────────────

    /**
     * Resolves the configured external allow-list to URIs. Reads via the
     * trust-aware {@link AiConfigurationService} so workspace-scoped overrides are
     * dropped when the workspace is untrusted. Awaits the service's `ready` promise
     * so that the trust state is resolved before the first preference read.
     * Non-string entries, blanks, and entries that don't parse to a `file://`
     * URI are filtered out; URIs are returned in normalized form.
     */
    async getAllowedExternalUris(resourceUri?: string): Promise<URI[]> {
        await this.aiConfiguration.ready;
        const raw = this.aiConfiguration.get<string[]>(ALLOWED_EXTERNAL_PATHS_PREF, [], resourceUri) ?? [];
        const result: URI[] = [];
        for (const entry of raw) {
            if (typeof entry !== 'string') {
                continue;
            }
            const trimmed = entry.trim();
            if (!trimmed) {
                continue;
            }
            const uri = await this.toExternalUri(trimmed);
            if (uri && uri.scheme === 'file') {
                // Strip a trailing separator so an entry like `/foo/` still matches the
                // directory `/foo` itself (URI.isEqualOrParent compares the last segment exactly).
                result.push(WorkspaceFunctionScope.withoutTrailingSeparator(uri.normalizePath()));
            }
        }
        return result;
    }

    /**
     * Whether path comparisons should be case-sensitive on the current
     * backend. Windows and macOS default to case-insensitive file systems
     * (NTFS, HFS+, APFS); Linux is treated as case-sensitive. This is a
     * heuristic — a case-sensitive APFS volume on macOS or a case-insensitive
     * volume mounted on Linux will be misclassified, but querying the actual
     * file system would require a backend round-trip.
     */
    static get pathCaseSensitive(): boolean {
        return !OS.backend.isWindows && !OS.backend.isOSX;
    }

    /**
     * Converts a user-supplied allow-list entry (absolute POSIX path, Windows
     * drive path, `~`-prefixed path, or `file://` URI) into a normalized URI.
     * Returns undefined for invalid input (relative paths, malformed URIs).
     */
    protected async toExternalUri(entry: string): Promise<URI | undefined> {
        if (entry.includes('://')) {
            try {
                return new URI(entry);
            } catch {
                return undefined;
            }
        }
        const normalized = Path.normalizePathSeparator(entry);
        const tilde = await this.resolveTildePath(normalized);
        if (tilde) {
            return tilde;
        }
        if (!WorkspaceFunctionScope.isAbsolutePath(normalized)) {
            return undefined;
        }
        return URI.fromFilePath(normalized);
    }

    /**
     * If the given separator-normalized path is `~` or starts with `~/`,
     * expands the leading `~` against the user's home directory and returns
     * the resulting URI. Returns undefined if the path does not start with
     * `~` or the home directory cannot be resolved. The remainder is
     * resolved in URI space to avoid Windows drive-letter round-tripping
     * issues with `URI.fromFilePath`.
     */
    protected async resolveTildePath(normalizedPath: string): Promise<URI | undefined> {
        if (normalizedPath !== '~' && !normalizedPath.startsWith('~/')) {
            return undefined;
        }
        const home = await this.getHomeDirUri();
        if (!home) {
            return undefined;
        }
        if (normalizedPath === '~') {
            return home;
        }
        return home.resolve(normalizedPath.substring(2));
    }

    /**
     * Whether an already-separator-normalized path is absolute on either
     * platform: POSIX `/foo`, UNC `//host/share`, or Windows drive `C:/foo`.
     */
    static isAbsolutePath(normalized: string): boolean {
        if (normalized.startsWith('/')) {
            return true;
        }
        return /^[A-Za-z]:\//.test(normalized);
    }

    /**
     * Returns the URI without a trailing path separator (except for a root path). This makes
     * directory comparisons via {@link URI.isEqualOrParent} insensitive to a trailing slash, so
     * an allow-list entry such as `/foo/` matches the directory `/foo` itself, not only its
     * children.
     */
    static withoutTrailingSeparator(uri: URI): URI {
        const path = uri.path.toString();
        if (path.length > 1 && path.endsWith('/')) {
            return uri.withPath(path.substring(0, path.length - 1));
        }
        return uri;
    }

    protected getHomeDirUri(): Promise<URI | undefined> {
        if (!this.homeDirUri) {
            this.homeDirUri = this.envVariablesServer.getHomeDirUri()
                .then(value => value ? new URI(value) : undefined)
                .catch(() => undefined);
        }
        return this.homeDirUri;
    }

    /**
     * Whether the already-separator-normalized path contains `..` as a path
     * segment (not merely as a substring of a filename like `my..file.json`).
     */
    static hasParentSegment(normalizedPath: string): boolean {
        return normalizedPath.split('/').some(segment => segment === '..');
    }

    // ── Gitignore / exclusion ───────────────────────────────────────────

    private async initializeGitignoreWatcher(workspaceRoot: URI): Promise<void> {
        const rootKey = workspaceRoot.toString();
        if (this.gitignoreWatchersInitialized.has(rootKey)) {
            return;
        }

        const gitignoreUri = workspaceRoot.resolve(this.GITIGNORE_FILE_NAME);
        this.fileService.watch(gitignoreUri);

        this.fileService.onDidFilesChange(async event => {
            if (event.contains(gitignoreUri)) {
                this.gitignoreMatchers.delete(rootKey);
            }
        });

        this.gitignoreWatchersInitialized.add(rootKey);
    }

    async shouldExclude(stat: FileStat): Promise<boolean> {
        const shouldConsiderGitIgnore = this.preferences.get(CONSIDER_GITIGNORE_PREF, false);
        const userExcludePatterns = this.preferences.get<string[]>(USER_EXCLUDE_PATTERN_PREF, []);

        if (this.isUserExcluded(stat.resource.path.base, userExcludePatterns)) {
            return true;
        }

        const containingRoot = this.getContainingRoot(stat.resource);
        // If the file is outside all workspace roots, we skip gitignore checks
        // since gitignore rules are relative to their root directory.
        if (shouldConsiderGitIgnore && containingRoot && (await this.isGitIgnored(stat, containingRoot))) {
            return true;
        }

        return false;
    }

    protected isUserExcluded(fileName: string, userExcludePatterns: string[]): boolean {
        return userExcludePatterns.some(pattern => new Minimatch(pattern, { dot: true }).match(fileName));
    }

    protected async isGitIgnored(stat: FileStat, workspaceRoot: URI): Promise<boolean> {
        const matcher = await this.getGitignoreMatcher(workspaceRoot);
        if (!matcher) {
            return false;
        }
        const relativePath = workspaceRoot.relative(stat.resource);
        if (!relativePath) {
            return false;
        }
        const relativePathStr = relativePath.toString() + (stat.isDirectory ? '/' : '');
        return matcher.ignores(relativePathStr);
    }

    /**
     * Returns the cached `.gitignore` matcher for the given root, reading the file at most
     * once per root. A root with no (or unreadable) `.gitignore` is cached as `undefined`.
     * The cache is invalidated by {@link initializeGitignoreWatcher} when the `.gitignore` is
     * created, changed, or deleted, so individual exclusion checks need no filesystem RPC.
     */
    protected async getGitignoreMatcher(workspaceRoot: URI): Promise<ReturnType<typeof ignore> | undefined> {
        await this.initializeGitignoreWatcher(workspaceRoot);

        const rootKey = workspaceRoot.toString();
        if (this.gitignoreMatchers.has(rootKey)) {
            return this.gitignoreMatchers.get(rootKey);
        }

        let matcher: ReturnType<typeof ignore> | undefined;
        try {
            const gitignoreUri = workspaceRoot.resolve(this.GITIGNORE_FILE_NAME);
            const gitignoreContent = await this.fileService.read(gitignoreUri);
            matcher = ignore().add(gitignoreContent.value);
        } catch {
            // No .gitignore (or it cannot be read): cache the absence so we don't retry on every check.
            matcher = undefined;
        }
        this.gitignoreMatchers.set(rootKey, matcher);
        return matcher;
    }
}

@injectable()
export class GetWorkspaceDirectoryStructure implements ToolProvider {
    static ID = GET_WORKSPACE_DIRECTORY_STRUCTURE_FUNCTION_ID;

    getTool(): ToolRequest {
        return {
            id: GetWorkspaceDirectoryStructure.ID,
            name: GetWorkspaceDirectoryStructure.ID,
            description: 'Retrieves the directory tree structure as a nested JSON object. ' +
                'By default returns all workspace roots with root names as keys. ' +
                'Pass `root` to inspect a specific directory listed in the ' +
                '`ai-features.workspaceFunctions.allowedExternalPaths` preference instead. ' +
                'Lists only directories (no files), excluding common non-essential directories (node_modules, hidden files, etc.). ' +
                'Useful for getting a high-level overview of project organization. ' +
                'For listing files within a specific directory, use getWorkspaceFileList instead. ' +
                'For finding specific files, use findFilesByPattern.',
            parameters: {
                type: 'object',
                properties: {
                    root: {
                        type: 'string',
                        description: 'Optional absolute path or `file://` URI to inspect instead of the workspace. ' +
                            'Must be inside, or equal to, an entry of the `allowedExternalPaths` preference. ' +
                            'When omitted, all workspace roots are returned.'
                    }
                },
            },
            handler: (arg_string: string, ctx?: ToolInvocationContext) => {
                let root: string | undefined;
                if (arg_string) {
                    try {
                        root = JSON.parse(arg_string).root;
                    } catch {
                        // tolerate empty or non-JSON input — keep prior behavior
                    }
                }
                return this.getDirectoryStructure(root, ctx?.cancellationToken);
            },
        };
    }

    @inject(FileService)
    protected readonly fileService: FileService;

    @inject(WorkspaceFunctionScope)
    protected workspaceScope: WorkspaceFunctionScope;

    private async getDirectoryStructure(root?: string, cancellationToken?: CancellationToken): Promise<Record<string, unknown>> {
        if (cancellationToken?.isCancellationRequested) {
            return { error: 'Operation cancelled by user' };
        }

        try {
            if (root) {
                const resolved = await this.workspaceScope.resolveToUri(root);
                if (!resolved) {
                    return { error: `Invalid root: '${root}'` };
                }
                await this.workspaceScope.ensureAccessible(resolved);
                return this.buildDirectoryStructure(resolved, cancellationToken);
            } else {
                const rootMapping = this.workspaceScope.getRootMapping();
                if (rootMapping.size === 0) {
                    return { error: 'No workspace has been opened yet' };
                }

                const result: Record<string, unknown> = {};
                for (const [rootName, rootUri] of rootMapping) {
                    if (cancellationToken?.isCancellationRequested) {
                        return { error: 'Operation cancelled by user' };
                    }
                    result[rootName] = await this.buildDirectoryStructure(rootUri, cancellationToken);
                }

                return result;
            }
        } catch (error) {
            return { error: error.message };
        }
    }

    private async buildDirectoryStructure(uri: URI, cancellationToken?: CancellationToken): Promise<Record<string, unknown>> {
        if (cancellationToken?.isCancellationRequested) {
            return { error: 'Operation cancelled by user' };
        }

        const stat = await this.fileService.resolve(uri);
        const result: Record<string, unknown> = {};

        if (stat && stat.isDirectory && stat.children) {
            // Determine which child directories to include (the exclusion check may be async)...
            const childDirs: URI[] = [];
            for (const child of stat.children) {
                if (cancellationToken?.isCancellationRequested) {
                    return { error: 'Operation cancelled by user' };
                }
                if (child.isDirectory && !(await this.workspaceScope.shouldExclude(child))) {
                    childDirs.push(child.resource);
                }
            }
            // ...then resolve their subtrees concurrently, so the traversal costs O(depth)
            // round-trips instead of one serial round-trip per directory. Empty directories
            // are preserved (they resolve to an empty object).
            const subtrees = await Promise.all(
                childDirs.map(childUri => this.buildDirectoryStructure(childUri, cancellationToken))
            );
            childDirs.forEach((childUri, index) => {
                result[childUri.path.base] = subtrees[index];
            });
        }

        return result;
    }
}

@injectable()
export class FileContentFunction implements ToolProvider {
    static ID = FILE_CONTENT_FUNCTION_ID;

    getTool(): ToolRequest {
        return {
            id: FileContentFunction.ID,
            name: FileContentFunction.ID,
            description: 'Returns the content of a specified file as a raw string. ' +
                'File paths use the same format returned by other workspace tools ' +
                '(e.g., "my-project/src/index.ts"). ' +
                'Absolute paths and `file://` URIs are accepted when the target is inside the workspace ' +
                'or covered by the `ai-features.workspaceFunctions.allowedExternalPaths` preference. ' +
                'If the file is currently open in an editor with unsaved changes, returns the editor\'s current content (not the saved file on disk). ' +
                'Binary files may not be readable and will return an error. ' +
                'Use this tool to read file contents before making any edits with replacement functions. ' +
                'Do NOT use this for files you haven\'t located yet - use findFilesByPattern or searchInWorkspace first. ' +
                'Files exceeding the configured size limit will return an error. ' +
                'It is recommended to read the whole file by not providing offset or limit parameters, ' +
                'unless you expect it to be very large. ' +
                'If the size limit is hit, do NOT attempt to read the full file in chunks using offset and limit — ' +
                'this wastes context window. Use searchInWorkspace to find the specific content you need instead.',
            parameters: {
                type: 'object',
                properties: {
                    file: {
                        type: 'string',
                        description: 'Path to the target file. May be workspace-relative ' +
                            '(e.g., "my-project/src/index.ts"), an absolute path, or a `file://` URI. ' +
                            'Absolute / URI forms must point inside the workspace ' +
                            'or inside a directory listed in the `allowedExternalPaths` preference.',
                    },
                    offset: {
                        type: 'number',
                        description: 'Zero-based line offset to start reading from (default: 0). ' +
                            'Use together with limit to page through large files.'
                    },
                    limit: {
                        type: 'number',
                        description: 'Maximum number of lines to return. Defaults to the rest of the file.'
                    }
                },
                required: ['file']
            },
            handler: (arg_string: string, ctx?: ToolInvocationContext) => {
                const { file, offset, limit } = this.parseArg(arg_string);
                return this.getFileContent(file, ctx?.cancellationToken, offset, limit);
            },
            providerName: undefined,
            getArgumentsShortLabel: (args: string): { label: string; hasMore: boolean } | undefined => {
                try {
                    const parsed = JSON.parse(args);
                    if (parsed && typeof parsed === 'object' && 'file' in parsed) {
                        const hasMore = 'offset' in parsed || 'limit' in parsed;
                        return { label: String(parsed.file), hasMore };
                    }
                } catch {
                    const file = extractJsonStringField(args, 'file');
                    if (file) {
                        return { label: file, hasMore: false };
                    }
                }
                return undefined;
            },
        };
    }

    @inject(FileService)
    protected readonly fileService: FileService;

    @inject(WorkspaceFunctionScope)
    protected readonly workspaceScope: WorkspaceFunctionScope;

    @inject(MonacoWorkspace)
    protected readonly monacoWorkspace: MonacoWorkspace;

    @inject(PreferenceService)
    protected readonly preferences: PreferenceService;

    private parseArg(arg_string: string): { file: string; offset?: number; limit?: number } {
        const result = JSON.parse(arg_string);
        return { file: result.file, offset: result.offset, limit: result.limit };
    }

    private async getFileContent(file: string, cancellationToken?: CancellationToken, offset?: number, limit?: number): Promise<string> {
        if (cancellationToken?.isCancellationRequested) {
            return JSON.stringify({ error: 'Operation cancelled by user' });
        }

        if (offset !== undefined && (!Number.isInteger(offset) || offset < 0)) {
            return JSON.stringify({ error: 'offset must be a non-negative integer.' });
        }
        if (limit !== undefined && (!Number.isInteger(limit) || limit <= 0)) {
            return JSON.stringify({ error: 'limit must be a positive integer.' });
        }

        let targetUri: URI | undefined;
        try {
            const resolved = await this.workspaceScope.resolveToUri(file);
            if (!resolved) {
                return JSON.stringify({ error: `Invalid file path: '${file}'` });
            }
            targetUri = resolved;
            await this.workspaceScope.ensureAccessible(targetUri);
        } catch (error) {
            return JSON.stringify({ error: error.message });
        }

        if (cancellationToken?.isCancellationRequested) {
            return JSON.stringify({ error: 'Operation cancelled by user' });
        }

        const openEditorValue = this.monacoWorkspace.getTextDocument(targetUri.toString())?.getText();
        const maxSizeKB = this.preferences.get<number>(FILE_CONTENT_MAX_SIZE_KB_PREF, 256);
        const isEditorOpen = openEditorValue !== undefined;
        const isPaginated = offset !== undefined || limit !== undefined;

        if (isEditorOpen) {
            return this.handleEditorContent(openEditorValue!, maxSizeKB, offset, limit);
        } else if (isPaginated) {
            return this.readStreamedSlice(targetUri, maxSizeKB, offset, limit);
        } else {
            return this.handleFullDiskRead(targetUri, maxSizeKB);
        }
    }

    private handleEditorContent(content: string, maxSizeKB: number, offset?: number, limit?: number): string {
        if (offset === undefined && limit === undefined) {
            const sizeKB = this.sizeInKB(content);
            if (sizeKB > maxSizeKB) {
                return this.buildFileSizeLimitError(sizeKB, maxSizeKB);
            }
            return content;
        }

        const lines = content.split('\n');
        const startOffset = offset ?? 0;
        const sliced = limit !== undefined ? lines.slice(startOffset, startOffset + limit) : lines.slice(startOffset);
        const result = sliced.join('\n');
        const resultSizeKB = this.sizeInKB(result);
        if (resultSizeKB > maxSizeKB) {
            return this.buildSliceSizeLimitError(resultSizeKB, maxSizeKB);
        }
        const startLine = startOffset + 1;
        const endLine = startOffset + sliced.length;
        const header = `[Lines ${startLine}\u2013${endLine} of ${lines.length} total. Use offset and limit to read other ranges.]`;
        return `${header}\n${result}`;
    }

    private async handleFullDiskRead(targetUri: URI, maxSizeKB: number): Promise<string> {
        try {
            const stat = await this.fileService.resolve(targetUri);
            if (stat.size !== undefined) {
                const statSizeKB = Math.round(stat.size / 1024);
                if (statSizeKB > maxSizeKB) {
                    return this.buildFileSizeLimitError(statSizeKB, maxSizeKB);
                }
            } else {
                // Size is unknown from stat; use the streaming path to avoid loading
                // an arbitrarily large file into memory, with a post-read size check.
                return this.readStreamedSlice(targetUri, maxSizeKB);
            }

            const rawContent = (await this.fileService.read(targetUri)).value;
            const sizeKB = this.sizeInKB(rawContent);
            if (sizeKB > maxSizeKB) {
                return this.buildFileSizeLimitError(sizeKB, maxSizeKB);
            }
            return rawContent;
        } catch (error) {
            if (error instanceof FileOperationError) {
                if (error.fileOperationResult === FileOperationResult.FILE_TOO_LARGE ||
                    error.fileOperationResult === FileOperationResult.FILE_EXCEEDS_MEMORY_LIMIT) {
                    return this.buildFileSizeLimitError(undefined, maxSizeKB);
                }
            }
            return JSON.stringify({ error: 'File not found' });
        }
    }

    private async readStreamedSlice(
        targetUri: URI, maxSizeKB: number, startLine?: number, limit?: number
    ): Promise<string> {
        const isPaginated = startLine !== undefined || limit !== undefined;
        const effectiveStartLine = startLine ?? 0;

        let streamValue: Awaited<ReturnType<typeof this.fileService.readStream>>['value'];
        try {
            // Bypass the files.maxFileSizeMB preference: the streaming path never loads the
            // full file into memory, so the OS-level size cap is not appropriate here.
            // Our own per-result maxSizeKB check still applies to the collected slice.
            streamValue = (await this.fileService.readStream(targetUri, { limits: { size: Number.MAX_SAFE_INTEGER } })).value;
        } catch (e) {
            if (e instanceof FileOperationError &&
                (e.fileOperationResult === FileOperationResult.FILE_TOO_LARGE ||
                    e.fileOperationResult === FileOperationResult.FILE_EXCEEDS_MEMORY_LIMIT)) {
                return JSON.stringify({
                    error: 'File exceeds the configured ' + maxSizeKB + 'KB size limit. ' +
                        'Use the \'offset\' (0-based) and \'limit\' parameters to read specific line ranges, ' +
                        'or use searchInWorkspace to find specific content.',
                    maxSizeKB
                });
            }
            return JSON.stringify({ error: 'File not found' });
        }

        return new Promise<string>(resolve => {
            let pending = '';
            let lineIndex = 0;
            const sliceLines: string[] = [];

            streamValue.on('data', (chunk: string) => {
                const parts = (pending + chunk).split('\n');
                pending = parts.pop()!;
                for (const line of parts) {
                    if (lineIndex >= effectiveStartLine && (limit === undefined || lineIndex < effectiveStartLine + limit)) {
                        sliceLines.push(line);
                    }
                    lineIndex++;
                }
            });

            streamValue.on('end', () => {
                if (pending.length > 0) {
                    if (lineIndex >= effectiveStartLine && (limit === undefined || lineIndex < effectiveStartLine + limit)) {
                        sliceLines.push(pending);
                    }
                    lineIndex++;
                }
                const result = sliceLines.join('\n');
                const resultSizeKB = this.sizeInKB(result);
                if (resultSizeKB > maxSizeKB) {
                    const sizeError = isPaginated
                        ? this.buildSliceSizeLimitError(resultSizeKB, maxSizeKB)
                        : this.buildFileSizeLimitError(resultSizeKB, maxSizeKB);
                    resolve(sizeError);
                    return;
                }
                if (isPaginated) {
                    const header =
                        `[Lines ${effectiveStartLine + 1}\u2013${effectiveStartLine + sliceLines.length} of ${lineIndex} total. ` +
                        'Use offset and limit to read other ranges.]';
                    resolve(`${header}\n${result}`);
                } else {
                    resolve(result);
                }
            });

            streamValue.on('error', () => resolve(JSON.stringify({ error: 'File not found' })));
        });
    }

    private sizeInKB(content: string): number {
        return Math.round(Buffer.byteLength(content, 'utf8') / 1024);
    }

    private buildFileSizeLimitError(sizeKB: number | undefined, maxSizeKB: number): string {
        const sizeInfo = sizeKB !== undefined ? ` (${sizeKB}KB)` : '';
        const result: Record<string, unknown> = {
            error: `File exceeds the configured ${maxSizeKB}KB size limit${sizeInfo}. ` +
                'Use the \'offset\' (0-based) and \'limit\' parameters to read specific line ranges, or use searchInWorkspace to find specific content.',
            maxSizeKB
        };
        if (sizeKB !== undefined) {
            result.sizeKB = sizeKB;
        }
        return JSON.stringify(result);
    }

    private buildSliceSizeLimitError(resultSizeKB: number, maxSizeKB: number): string {
        return JSON.stringify({
            error: 'Requested range exceeds the configured ' + maxSizeKB + 'KB size limit (' + resultSizeKB + 'KB). ' +
                'Use a smaller limit to read fewer lines at a time.',
            resultSizeKB,
            maxSizeKB
        });
    }
}

@injectable()
export class GetWorkspaceFileList implements ToolProvider {
    static ID = GET_WORKSPACE_FILE_LIST_FUNCTION_ID;

    getTool(): ToolRequest {
        return {
            id: GetWorkspaceFileList.ID,
            name: GetWorkspaceFileList.ID,
            parameters: {
                type: 'object',
                properties: {
                    path: {
                        type: 'string',
                        description: 'Path to a directory. Workspace-relative paths use the format \'rootName/path\' ' +
                            '(e.g., \'my-project/src\', \'backend/src/components\'). ' +
                            'Use \'\' or \'.\' to list the workspace top-level directories. ' +
                            'Absolute paths and `file://` URIs are accepted when covered by the `allowedExternalPaths` preference.'
                    }
                },
                required: ['path']
            },
            description: 'Lists files and directories within a specified directory. ' +
                'Returns a JSON object mapping each immediate child name to its type ("directory" or "file"). ' +
                'Use "" or "." to list the workspace top-level directories. ' +
                'Use this to explore directory structure step by step. ' +
                'For finding specific files by pattern, use findFilesByPattern instead. ' +
                'For searching file contents, use searchInWorkspace instead.',
            handler: (arg_string: string, ctx?: ToolInvocationContext) => {
                const args = JSON.parse(arg_string);
                return this.getProjectFileList(args.path, ctx?.cancellationToken);
            },
        };
    }

    @inject(FileService)
    protected readonly fileService: FileService;

    @inject(WorkspaceFunctionScope)
    protected workspaceScope: WorkspaceFunctionScope;

    async getProjectFileList(path?: string, cancellationToken?: CancellationToken): Promise<string> {
        if (cancellationToken?.isCancellationRequested) {
            return JSON.stringify({ error: 'Operation cancelled by user' });
        }

        try {
            const rootMapping = this.workspaceScope.getRootMapping();
            if (rootMapping.size === 0) {
                return JSON.stringify({ error: 'No workspace has been opened yet' });
            }

            if (!path || path === '.' || path === '') {
                const roots: Record<string, 'directory'> = {};
                for (const name of rootMapping.keys()) {
                    roots[name] = 'directory';
                }
                return JSON.stringify(roots);
            }

            let targetUri: URI;
            try {
                const resolved = await this.workspaceScope.resolveToUri(path);
                if (!resolved) {
                    return JSON.stringify({ error: `Invalid path: '${path}'` });
                }
                targetUri = resolved;
                await this.workspaceScope.ensureAccessible(targetUri);
            } catch (error) {
                return JSON.stringify({ error: error.message });
            }

            if (cancellationToken?.isCancellationRequested) {
                return JSON.stringify({ error: 'Operation cancelled by user' });
            }

            const stat = await this.fileService.resolve(targetUri);
            if (!stat || !stat.isDirectory) {
                return JSON.stringify({ error: 'Directory not found' });
            }
            return await this.listFilesDirectly(stat, cancellationToken);
        } catch (error) {
            return JSON.stringify({ error: 'Directory not found' });
        }
    }

    private async listFilesDirectly(stat: FileStat, cancellationToken?: CancellationToken): Promise<string> {
        if (cancellationToken?.isCancellationRequested) {
            return JSON.stringify({ error: 'Operation cancelled by user' });
        }

        const result: Record<string, 'directory' | 'file'> = {};

        if (await this.workspaceScope.shouldExclude(stat)) {
            return JSON.stringify(result);
        }
        // `stat` already carries one level of children from the caller's resolve, so no extra RPC.
        for (const child of stat.children ?? []) {
            if (cancellationToken?.isCancellationRequested) {
                return JSON.stringify({ error: 'Operation cancelled by user' });
            }

            if (await this.workspaceScope.shouldExclude(child)) {
                continue;
            }
            result[child.resource.path.base] = child.isDirectory ? 'directory' : 'file';
        }

        return JSON.stringify(result);
    }
}

@injectable()
export class FileDiagnosticProvider implements ToolProvider {
    static ID = GET_FILE_DIAGNOSTICS_ID;

    @inject(WorkspaceFunctionScope)
    protected readonly workspaceScope: WorkspaceFunctionScope;

    @inject(ProblemManager)
    protected readonly problemManager: ProblemManager;

    @inject(MonacoTextModelService)
    protected readonly modelService: MonacoTextModelService;

    getTool(): ToolRequest {
        return {
            id: FileDiagnosticProvider.ID,
            name: FileDiagnosticProvider.ID,
            description:
                'Retrieves Error and Warning level diagnostics for a specific file in the workspace (Info and Hint level are filtered out). ' +
                'Returns a list of problems including: surrounding source code context (at least 3 lines), the error/warning message, ' +
                'and optionally a diagnostic code with description. ' +
                'Note: If the file was not recently opened, diagnostics may take a few seconds to appear as language services initialize. ' +
                'If no diagnostics are returned, the file may be error-free OR language services may not be active for this file type. ' +
                'Use this after making code changes to verify they compile correctly.',
            parameters: {
                type: 'object',
                properties: {
                    file: {
                        type: 'string',
                        description: 'The path to the target file within the workspace ' +
                            '(e.g., "my-project/src/index.ts", "backend/src/main.ts").'
                    }
                },
                required: ['file']
            },
            handler: async (arg: string, ctx?: ToolInvocationContext) => {
                try {
                    const { file } = JSON.parse(arg);
                    const targetUri = await this.workspaceScope.resolveRelativePath(file);
                    const containingRoot = this.workspaceScope.getContainingRoot(targetUri);
                    if (!containingRoot) {
                        return JSON.stringify({ error: 'Access outside of the workspace is not allowed' });
                    }
                    this.workspaceScope.ensureWithinWorkspace(targetUri, containingRoot);

                    return this.getDiagnosticsForFile(targetUri, ctx?.cancellationToken);
                } catch (error) {
                    return JSON.stringify({ error: error instanceof Error ? error.message : 'Unknown error.' });
                }
            }
        };
    }

    protected async getDiagnosticsForFile(uri: URI, cancellationToken?: CancellationToken): Promise<string> {
        const toDispose: Disposable[] = [];
        try {
            // Check for early cancellation
            if (cancellationToken?.isCancellationRequested) {
                return JSON.stringify({ error: 'Operation cancelled by user' });
            }

            let markers = this.problemManager.findMarkers({ uri });
            if (markers.length === 0) {
                // Create a model reference to ensure that the language services are active.
                const modelRef = await this.modelService.createModelReference(uri);
                modelRef.object.suppressOpenEditorWhenDirty = true;
                toDispose.push(modelRef);

                // Give some time to fetch problems in a newly opened editor.
                await new Promise<void>((res, rej) => {
                    const timeout = setTimeout(res, 5000);

                    // Give another moment for additional markers to come in from different sources.
                    const listener = this.problemManager.onDidChangeMarkers(changed => changed.isEqual(uri) && setTimeout(res, 500));
                    toDispose.push(listener);

                    // Handle cancellation
                    if (cancellationToken) {
                        const cancelListener =
                            cancellationToken.onCancellationRequested(() => {
                                clearTimeout(timeout);
                                listener.dispose();
                                rej(new Error('Operation cancelled by user'));
                            });
                        toDispose.push(cancelListener);
                    }
                });

                markers = this.problemManager.findMarkers({ uri });
            }

            if (cancellationToken?.isCancellationRequested) {
                return JSON.stringify({ error: 'Operation cancelled by user' });
            }

            if (markers.length) {
                const editor = await this.modelService.createModelReference(uri);
                editor.object.suppressOpenEditorWhenDirty = true;
                toDispose.push(editor);
                return JSON.stringify(markers.filter(marker => marker.data.severity !== DiagnosticSeverity.Information && marker.data.severity !== DiagnosticSeverity.Hint)
                    .map(marker => {
                        const contextRange = this.atLeastNLines(3, marker.data.range, editor.object.lineCount);
                        const text = editor.object.getText(contextRange);
                        const message = marker.data.message;
                        const code = marker.data.code;
                        const codeDescription = marker.data.codeDescription;
                        return { text, message, code, codeDescription };
                    })
                );
            }
            return JSON.stringify({
                error: 'No diagnostics were found. The file may contain no problems, or language services may not be available. Retrying may return fresh results.'
            });
        } catch (err) {
            if (err.message === 'Operation cancelled by user') {
                return JSON.stringify({ error: 'Operation cancelled by user' });
            }
            console.warn('Error when fetching markers for', uri.toString(), err);
            return JSON.stringify({ error: err instanceof Error ? err.message : 'Unknown error when fetching for problems for ' + uri.toString() });
        } finally {
            toDispose.forEach(disposable => disposable.dispose());
        }
    }

    /**
     * Expands the range provided until it contains at least {@link desiredLines} lines or reaches the end of the document
     *  to attempt to provide the agent sufficient context to understand the diagnostic.
     */
    protected atLeastNLines(desiredLines: number, range: Range, documentLineCount: number): Range {
        let startLine = range.start.line;
        let endLine = range.end.line;
        const desiredDifference = desiredLines - 1;

        while (endLine - startLine < desiredDifference && (startLine > 0 || endLine < documentLineCount - 1)) {
            if (startLine > 0) {
                startLine--;
            } else if (endLine < documentLineCount - 1) {
                endLine++;
            }
            if (endLine < documentLineCount - 1) {
                endLine++;
            } else if (startLine > 0) {
                startLine--;
            }
        }
        return { end: { character: Number.MAX_SAFE_INTEGER, line: endLine }, start: { character: 0, line: startLine } };
    }
}

@injectable()
export class FindFilesByPattern implements ToolProvider {
    static ID = FIND_FILES_BY_PATTERN_FUNCTION_ID;

    @inject(WorkspaceFunctionScope)
    protected readonly workspaceScope: WorkspaceFunctionScope;

    @inject(PreferenceService)
    protected readonly preferences: PreferenceService;

    @inject(FileSearchService)
    protected readonly fileSearchService: FileSearchService;

    getTool(): ToolRequest {
        return {
            id: FindFilesByPattern.ID,
            name: FindFilesByPattern.ID,
            description: 'Find files matching a given glob pattern. ' +
                'By default searches across all workspace roots. ' +
                'Pass `searchRoot` to search a directory listed in the ' +
                '`ai-features.workspaceFunctions.allowedExternalPaths` preference instead. ' +
                'This function allows efficient discovery of files using patterns like \'**/*.ts\' for all TypeScript files or ' +
                '\'src/**/*.js\' for JavaScript files in the src directory. The function respects gitignore patterns and user exclusions, ' +
                'returns workspace-relative paths (e.g., "my-project/src/index.ts") or absolute paths for external roots, ' +
                'and limits results to 200 files maximum. ' +
                'Use this to find files by name/extension. Do NOT use this for searching file contents - use searchInWorkspace instead.',
            parameters: {
                type: 'object',
                properties: {
                    pattern: {
                        type: 'string',
                        description: 'Glob pattern to match files against. ' +
                            'Examples: \'**/*.ts\' (all TypeScript files), \'src/**/*.js\' (JS files in src), ' +
                            '\'**/*.{js,ts}\' (JS or TS files), \'**/test/**/*.spec.ts\' (test files).'
                    },
                    exclude: {
                        type: 'array',
                        items: { type: 'string' },
                        description: 'Optional glob patterns to exclude. ' +
                            'Examples: [\'**/*.spec.ts\', \'**/node_modules/**\']. ' +
                            'Common exclusions (node_modules, .git) are applied automatically via gitignore.'
                    },
                    searchRoot: {
                        type: 'string',
                        description: 'Optional absolute path or `file://` URI to search instead of the workspace. ' +
                            'Must be inside, or equal to, an entry of the `allowedExternalPaths` preference. ' +
                            'When set, results are returned as absolute paths so they can be passed back to getFileContent. ' +
                            'When omitted (default), all workspace roots are searched and results are workspace-relative.'
                    }
                },
                required: ['pattern']
            },
            handler: (arg_string: string, ctx?: ToolInvocationContext) => {
                const args = JSON.parse(arg_string);
                return this.findFiles(args.pattern, args.exclude, args.searchRoot, ctx?.cancellationToken);
            },
            providerName: undefined,
            getArgumentsShortLabel: (args: string): { label: string; hasMore: boolean } | undefined => {
                try {
                    const parsed = JSON.parse(args);
                    if (parsed && typeof parsed === 'object' && 'pattern' in parsed) {
                        const keys = Object.keys(parsed);
                        return { label: String(parsed.pattern), hasMore: keys.length > 1 };
                    }
                } catch {
                    const pattern = extractJsonStringField(args, 'pattern');
                    if (pattern) {
                        return { label: pattern, hasMore: false };
                    }
                }
                return undefined;
            },
        };
    }

    private async findFiles(
        pattern: string,
        excludePatterns?: string[],
        searchRoot?: string,
        cancellationToken?: CancellationToken
    ): Promise<string> {
        if (cancellationToken?.isCancellationRequested) {
            return JSON.stringify({ error: 'Operation cancelled by user' });
        }

        try {
            const maxResults = 200;
            const useGitIgnore = this.preferences.get(CONSIDER_GITIGNORE_PREF, true);
            const userExcludes = this.preferences.get<string[]>(USER_EXCLUDE_PATTERN_PREF, []);
            const excludes = [...userExcludes, ...(excludePatterns ?? [])];

            // Resolve the set of roots to search and how each root's results should be rendered.
            const targets: { rootUri: URI; rootName?: string; external: boolean }[] = [];
            if (searchRoot) {
                const resolved = await this.workspaceScope.resolveToUri(searchRoot);
                if (!resolved) {
                    return JSON.stringify({ error: `Invalid searchRoot: '${searchRoot}'` });
                }
                await this.workspaceScope.ensureAccessible(resolved);
                targets.push({ rootUri: resolved, external: !this.workspaceScope.isInWorkspace(resolved) });
            } else {
                const rootMapping = this.workspaceScope.getRootMapping();
                if (rootMapping.size === 0) {
                    return JSON.stringify({ error: 'No workspace has been opened yet' });
                }
                for (const [rootName, rootUri] of rootMapping) {
                    targets.push({ rootUri, rootName, external: false });
                }
            }

            // Delegate the actual traversal to the backend ripgrep-based file search.
            // It runs natively on the backend filesystem (no per-directory RPC) and applies
            // include/exclude globs.
            const files: string[] = [];
            for (const target of targets) {
                if (cancellationToken?.isCancellationRequested) {
                    return JSON.stringify({ error: 'Operation cancelled by user' });
                }
                if (files.length > maxResults) {
                    break;
                }
                // `considerGitIgnore` is scoped to workspace roots (see its preference description),
                // so external allow-listed roots are searched with user/caller excludes only (plus
                // `.git`). Applying gitignore there would also leak the user's *global* gitignore
                // into an explicitly allow-listed directory and silently hide files.
                // Request one extra result across all roots so we can detect truncation.
                const matches = await this.fileSearchService.find('', {
                    rootUris: [target.rootUri.toString()],
                    includePatterns: [pattern],
                    excludePatterns: target.external ? [...excludes, '.git'] : excludes,
                    useGitIgnore: target.external ? false : useGitIgnore,
                    fuzzyMatch: false,
                    limit: maxResults - files.length + 1
                }, cancellationToken);
                for (const match of matches) {
                    const display = this.toDisplayPath(new URI(match), target);
                    if (display !== undefined) {
                        files.push(display);
                    }
                }
            }

            if (cancellationToken?.isCancellationRequested) {
                return JSON.stringify({ error: 'Operation cancelled by user' });
            }

            const result: { files: string[]; truncated?: boolean } = {
                files: files.slice(0, maxResults)
            };
            if (files.length > maxResults) {
                result.truncated = true;
            }

            return JSON.stringify(result);

        } catch (error) {
            return JSON.stringify({ error: `Failed to find files: ${error.message}` });
        }
    }

    /**
     * Renders a search-result URI in the format expected by the caller: an absolute
     * path for external roots, or a `<rootName>/<relativePath>` (or bare relative
     * path when no root name is available) for workspace roots.
     */
    protected toDisplayPath(match: URI, target: { rootUri: URI; rootName?: string; external: boolean }): string | undefined {
        if (target.external) {
            return match.path.toString();
        }
        const relativePath = target.rootUri.relative(match)?.toString();
        if (relativePath === undefined) {
            return undefined;
        }
        return target.rootName ? `${target.rootName}/${relativePath}` : relativePath;
    }
}
