В одной из своих предыдущих статей я уже рассказывал о том, что иногда мы даже не замечаем окружающих нас алгоритмов. При использовании инструмента или библиотеки мы потребляем их как данность, даже не понимая, как они работают за кулисами. Сегодня я собираюсь перепроектировать алгоритм, который Jest использует для поиска связанных тестов, когда мы запускаем jest --findRelatedTests.

Что такое Jest и как я могу его использовать?

Jest — популярный фреймворк для тестирования JavaScript, который в настоящее время используется практически в каждом проекте. Вы можете начать с него, просто создав любой тестовый файл с расширением test.js и запустив команду jest в своем терминале. Jest также предоставляет широкие возможности конфигурации, которые разработчики могут использовать для определения того, какие тесты включать/исключать, какое покрытие генерировать в каком формате, как транспилировать исходные файлы и т. д. — все это можно найти в официальной документации. Самый захватывающий вариант — запустить jest с --findRelatedTests и передать список файлов, которые вы хотите протестировать:

jest --findRelatedTests /path/to/file1, /path/to/file2

Таким образом, Jest будет запускать не только прямые тесты, связанные с этими файлами, но и тест на транзитивные зависимости. Это становится очень удобным, когда дело доходит до оптимизации выполнения команды git перед фиксацией. Вместо того, чтобы запускать весь набор тестов каждый раз, когда вы собираетесь внести новое изменение, Jest будет запускать только набор тестов, на которые действительно влияют соответствующие изменения, что экономит разработчикам много времени и обеспечивает точность результатов.

Файловая система Jest

Jest использует специальную систему модулей ускорения для оптимизации метаданных о файлах и зависимостях между ними. Этот компонент определенно заслуживает отдельной статьи Под капотом. А пока давайте упростим то, что он предоставляет API для получения коллекции всех файлов в проекте и его зависимостей в следующей форме:

Array<{ 
// absolute file path 
file: string; 

// list of depedencies (modules imported in current file)
dependencies: Array<string>; 
}>

Глядя под капот

Что мы знаем:

  • набор файлов, которые были добавлены/изменены/удалены и размещены в Git
  • и метаданные всей файловой системы

Теперь нам нужно найти алгоритм для обнаружения и запуска только тестовых файлов, на которые повлияло это изменение.

И Jest предоставляет resolveInverse API для решения этой проблемы:

resolveInverse(
paths: Set<string>, 
filter: (file: string) => boolean, 
options?: ResolveModuleConfig, ): Array<string> { 
   return this.resolveInverseModuleMap(paths, filter, options)
          .map( module => module.file, ); 
}

где:

  • paths — это набор путей к файлам, которые изменились
  • filter — предикатная функция для определения того, является ли текущий файл тестовым файлом.
  • options объект (не имеет значения для алгоритма, пока игнорируйте его)

resolveInverseModuleMap использует очень простой подход к решению этой проблемы, основанный на поиске в ширину (BFS). Прежде всего, он инициализирует следующие наборы:

  • changed - набор затронутых файлов. По сути, это временный набор, который изменяется после каждой итерации BFS и служит индикатором завершения — алгоритм останавливается, когда он пуст. На первой итерации этот набор заполняется из paths, предоставленных в качестве входных данных.
  • relatedPaths — набор затронутых тестовых файлов. По умолчанию этот набор заполняется из входных данных paths, но с условием, что файл на самом деле является тестовым файлом. При каждой итерации BFS каждый соответствующий тестовый файл удаляется из этого файла. В конце алгоритма оставшиеся пути к файлам в этом наборе объединяются с результатами выполнения BFS. Это для обработки простого варианта использования, когда изменение было внесено в тестовый файл, а не в исходный.
  • visitedModules - файлы, которые уже были просмотрены и могут быть исключены из дальнейшей обработки.

Итак, давайте визуализируем наш алгоритм. Прежде всего, давайте определим файловую систему нашего примера:

Блоки красного цвета обозначают измененные модули (прямоугольники — тестовые файлы, кружки — исходные файлы). Стрелки начинаются от родителя к дочернему (это означает, что модуль a импортируется модулями a.test и a1). Изначально наши структуры данных будут выглядеть так:

Наш измененный набор не пуст. Это означает, что нам нужно просмотреть все файлы в нашей файловой системе, чтобы получить список зависимостей для каждого модуля в наборе changed. После первой итерации мы уже обнаружили, что как минимум b.test и a1.test нужно запускать как зависимости от a.test и a1 соответственно:

Делаем очередной обход. Теперь мы видим, что b2 импортировано и в a.test, и в b2.test, но у нас уже есть .test в исходно измененных файлах. В этом случае нам нужно удалить его из набора relatedPaths и добавить в результаты. В случае, если a.test не имеет никакой зависимости, Jest просто объединит его с результатами при возврате вышестоящему вызывающему объекту.

В итоге у нас в наборе changed всего 2 тестовых модуля и мы уже видим, что a.test есть в нашем наборе посещений и у b2.test нет зависимых. По сути, здесь нет операции — после этой итерации набор changed станет пустым, и мы выйдем из нашего цикла BFS.

В результате мы смогли сузить область тестирования с 5 тестовых файлов до 4. Это не так впечатляет, но имейте в виду, что для простоты я выбрал очень маленький набор данных для этого примера — в реальных проектах их может быть несколько тысяч. файлов, и улучшение может быть действительно радикальным.

Вы можете найти оригинальную реализацию здесь.

Последние мысли

Как вы думаете, можно ли улучшить этот алгоритм? Что, если бы мы могли иметь обратные ссылки на зависимые модули как часть метаданных файла (аналогично элементам DOM, которые имеют ссылку на родителя)? В этом случае нам не пришлось бы просматривать всю файловую систему и сосредоточиться только на ее подмножестве.

Первоначально опубликовано на https://thesametech.com 22 декабря 2022 г.

Вы также можете подписаться на меня в Twitter и подключиться к LinkedIn, чтобы получать уведомления о новых сообщениях!

Дополнительные материалы на PlainEnglish.io.

Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .

Заинтересованы в масштабировании запуска вашего программного обеспечения? Ознакомьтесь с разделом Схема.