packages/core/src/utils/bfsFileSearch.test.ts

/**
 * @license
 * Copyright 2025 Google LLC
 * SPDX-License-Identifier: Apache-2.0
 */

import { describe, it, expect, beforeEach, afterEach } from 'vitest';
import * as fsPromises from 'node:fs/promises';
import * as path from 'node:path';
import * as os from 'node:os';
import { bfsFileSearch, bfsFileSearchSync } from './bfsFileSearch.js';
import { FileDiscoveryService } from '../services/fileDiscoveryService.js';
import { GEMINI_IGNORE_FILE_NAME } from 'src/config/constants.js';

describe('bfsFileSearch', () => {
  let testRootDir: string;

  async function createEmptyDir(...pathSegments: string[]) {
    const fullPath = path.join(testRootDir, ...pathSegments);
    await fsPromises.mkdir(fullPath, { recursive: true });
    return fullPath;
  }

  async function createTestFile(content: string, ...pathSegments: string[]) {
    const fullPath = path.join(testRootDir, ...pathSegments);
    await fsPromises.mkdir(path.dirname(fullPath), { recursive: true });
    await fsPromises.writeFile(fullPath, content);
    return fullPath;
  }

  beforeEach(async () => {
    testRootDir = await fsPromises.mkdtemp(
      path.join(os.tmpdir(), 'bfs-file-search-test-'),
    );
  });

  afterEach(async () => {
    await fsPromises.rm(testRootDir, { recursive: true, force: true });
  });

  it('should find a file in the root directory', async () => {
    const targetFilePath = await createTestFile('content', 'target.txt');
    const result = await bfsFileSearch(testRootDir, { fileName: 'target.txt' });
    expect(result).toEqual([targetFilePath]);
  });

  it('should find a file in a nested directory', async () => {
    const targetFilePath = await createTestFile(
      'content',
      'a',
      'b',
      'target.txt',
    );
    const result = await bfsFileSearch(testRootDir, { fileName: 'target.txt' });
    expect(result).toEqual([targetFilePath]);
  });

  it('should find multiple files with the same name', async () => {
    const targetFilePath1 = await createTestFile('content1', 'a', 'target.txt');
    const targetFilePath2 = await createTestFile('content2', 'b', 'target.txt');
    const result = await bfsFileSearch(testRootDir, { fileName: 'target.txt' });
    result.sort();
    expect(result).toEqual([targetFilePath1, targetFilePath2].sort());
  });

  it('should return an empty array if no file is found', async () => {
    await createTestFile('content', 'other.txt');
    const result = await bfsFileSearch(testRootDir, { fileName: 'target.txt' });
    expect(result).toEqual([]);
  });

  it('should ignore directories specified in ignoreDirs', async () => {
    await createTestFile('content', 'ignored', 'target.txt');
    const targetFilePath = await createTestFile(
      'content',
      'not-ignored',
      'target.txt',
    );
    const result = await bfsFileSearch(testRootDir, {
      fileName: 'target.txt',
      ignoreDirs: ['ignored'],
    });
    expect(result).toEqual([targetFilePath]);
  });

  it('should respect the maxDirs limit and not find the file', async () => {
    await createTestFile('content', 'a', 'b', 'c', 'target.txt');
    const result = await bfsFileSearch(testRootDir, {
      fileName: 'target.txt',
      maxDirs: 3,
    });
    expect(result).toEqual([]);
  });

  it('should respect the maxDirs limit and find the file', async () => {
    const targetFilePath = await createTestFile(
      'content',
      'a',
      'b',
      'c',
      'target.txt',
    );
    const result = await bfsFileSearch(testRootDir, {
      fileName: 'target.txt',
      maxDirs: 4,
    });
    expect(result).toEqual([targetFilePath]);
  });

  describe('with FileDiscoveryService', () => {
    let projectRoot: string;

    beforeEach(async () => {
      projectRoot = await createEmptyDir('project');
    });

    it('should ignore gitignored files', async () => {
      await createEmptyDir('project', '.git');
      await createTestFile('node_modules/', 'project', '.gitignore');
      await createTestFile('content', 'project', 'node_modules', 'target.txt');
      const targetFilePath = await createTestFile(
        'content',
        'project',
        'not-ignored',
        'target.txt',
      );

      const fileService = new FileDiscoveryService(projectRoot);
      const result = await bfsFileSearch(projectRoot, {
        fileName: 'target.txt',
        fileService,
        fileFilteringOptions: {
          respectGitIgnore: true,
          respectGeminiIgnore: true,
          customIgnoreFilePaths: [],
        },
      });

      expect(result).toEqual([targetFilePath]);
    });

    it('should ignore geminiignored files', async () => {
      await createTestFile('node_modules/', 'project', GEMINI_IGNORE_FILE_NAME);
      await createTestFile('content', 'project', 'node_modules', 'target.txt');
      const targetFilePath = await createTestFile(
        'content',
        'project',
        'not-ignored',
        'target.txt',
      );

      const fileService = new FileDiscoveryService(projectRoot);
      const result = await bfsFileSearch(projectRoot, {
        fileName: 'target.txt',
        fileService,
        fileFilteringOptions: {
          respectGitIgnore: false,
          respectGeminiIgnore: true,
          customIgnoreFilePaths: [],
        },
      });

      expect(result).toEqual([targetFilePath]);
    });

    it('should not ignore files if respect flags are false', async () => {
      await createEmptyDir('project', '.git');
      await createTestFile('node_modules/', 'project', '.gitignore');
      const target1 = await createTestFile(
        'content',
        'project',
        'node_modules',
        'target.txt',
      );
      const target2 = await createTestFile(
        'content',
        'project',
        'not-ignored',
        'target.txt',
      );

      const fileService = new FileDiscoveryService(projectRoot);
      const result = await bfsFileSearch(projectRoot, {
        fileName: 'target.txt',
        fileService,
        fileFilteringOptions: {
          respectGitIgnore: false,
          respectGeminiIgnore: false,
          customIgnoreFilePaths: [],
        },
      });

      expect(result.sort()).toEqual([target1, target2].sort());
    });
  });

  it('should find all files in a complex directory structure', async () => {
    // Create a complex directory structure to test correctness at scale
    // without flaky performance checks.
    const numDirs = 50;
    const numFilesPerDir = 2;
    const numTargetDirs = 10;

    const dirCreationPromises: Array<Promise<unknown>> = [];
    for (let i = 0; i < numDirs; i++) {
      dirCreationPromises.push(createEmptyDir(`dir${i}`));
      dirCreationPromises.push(createEmptyDir(`dir${i}`, 'subdir1'));
      dirCreationPromises.push(createEmptyDir(`dir${i}`, 'subdir2'));
      dirCreationPromises.push(createEmptyDir(`dir${i}`, 'subdir1', 'deep'));
    }
    await Promise.all(dirCreationPromises);

    const fileCreationPromises: Array<Promise<string>> = [];
    for (let i = 0; i < numTargetDirs; i++) {
      // Add target files in some directories
      fileCreationPromises.push(
        createTestFile('content', `dir${i}`, 'GEMINI.md'),
      );
      fileCreationPromises.push(
        createTestFile('content', `dir${i}`, 'subdir1', 'GEMINI.md'),
      );
    }
    const expectedFiles = await Promise.all(fileCreationPromises);

    const result = await bfsFileSearch(testRootDir, {
      fileName: 'GEMINI.md',
      // Provide a generous maxDirs limit to ensure it doesn't prematurely stop
      // in this large test case. Total dirs created is 200.
      maxDirs: 250,
    });

    // Verify we found the exact files we created
    expect(result.length).toBe(numTargetDirs * numFilesPerDir);
    expect(result.sort()).toEqual(expectedFiles.sort());
  });
});

describe('bfsFileSearchSync', () => {
  let testRootDir: string;

  async function createEmptyDir(...pathSegments: string[]) {
    const fullPath = path.join(testRootDir, ...pathSegments);
    await fsPromises.mkdir(fullPath, { recursive: true });
    return fullPath;
  }

  async function createTestFile(content: string, ...pathSegments: string[]) {
    const fullPath = path.join(testRootDir, ...pathSegments);
    await fsPromises.mkdir(path.dirname(fullPath), { recursive: true });
    await fsPromises.writeFile(fullPath, content);
    return fullPath;
  }

  beforeEach(async () => {
    testRootDir = await fsPromises.mkdtemp(
      path.join(os.tmpdir(), 'bfs-file-search-sync-test-'),
    );
  });

  afterEach(async () => {
    await fsPromises.rm(testRootDir, { recursive: true, force: true });
  });

  it('should find a file in the root directory synchronously', async () => {
    const targetFilePath = await createTestFile('content', 'target.txt');
    const result = bfsFileSearchSync(testRootDir, { fileName: 'target.txt' });
    expect(result).toEqual([targetFilePath]);
  });

  it('should find a file in a nested directory synchronously', async () => {
    const targetFilePath = await createTestFile(
      'content',
      'a',
      'b',
      'target.txt',
    );
    const result = bfsFileSearchSync(testRootDir, { fileName: 'target.txt' });
    expect(result).toEqual([targetFilePath]);
  });

  it('should respect the maxDirs limit and not find the file synchronously', async () => {
    await createTestFile('content', 'a', 'b', 'c', 'target.txt');
    const result = bfsFileSearchSync(testRootDir, {
      fileName: 'target.txt',
      maxDirs: 3,
    });
    expect(result).toEqual([]);
  });

  it('should ignore directories synchronously', async () => {
    await createTestFile('content', 'ignored', 'target.txt');
    const targetFilePath = await createTestFile(
      'content',
      'not-ignored',
      'target.txt',
    );
    const result = bfsFileSearchSync(testRootDir, {
      fileName: 'target.txt',
      ignoreDirs: ['ignored'],
    });
    expect(result).toEqual([targetFilePath]);
  });

  it('should work with FileDiscoveryService synchronously', async () => {
    const projectRoot = await createEmptyDir('project');
    await createEmptyDir('project', '.git');
    await createTestFile('node_modules/', 'project', '.gitignore');
    await createTestFile('content', 'project', 'node_modules', 'target.txt');
    const targetFilePath = await createTestFile(
      'content',
      'project',
      'not-ignored',
      'target.txt',
    );

    const fileService = new FileDiscoveryService(projectRoot);
    const result = bfsFileSearchSync(projectRoot, {
      fileName: 'target.txt',
      fileService,
      fileFilteringOptions: {
        respectGitIgnore: true,
        respectGeminiIgnore: true,
        customIgnoreFilePaths: [],
      },
    });

    expect(result).toEqual([targetFilePath]);
  });
});