In one of my previous articles, I already talked about how sometimes we don’t even notice the algorithms around us. When using a tool or library, we consume it as a given without even understanding how it works behind the scenes. Today I am going to reverse-engineer the algorithm Jest uses to find related tests when we run . jest --findRelatedTests What is Jest and how I can use it? is a popular JavaScript testing framework used in almost every project nowadays. You can start with it simply by creating any test file with a extension and running the jest command in your terminal. Jest also provides extensive configuration options that developers can use to define what tests to include/exclude, what coverage output to generate in which format, and how to transpile source files, etc. - you can find all of this in the . Jest test.js official docs The most exciting option is to run jest with and passing list of the files you want to test: --findRelatedTests jest --findRelatedTests /path/to/file1, /path/to/file2 This way, Jest will run not only direct tests associated with these files but also the test for transitive dependencies. It becomes super handy when it comes to optimizing git pre-commit command execution. Instead of running an entire set of tests every time you are about to commit a new change, Jest will run only a set of tests that are actually impacted by corresponding change saving developers a great amount of time while being accurate with results. Jest file system Jest uses a custom for building metadata about the files and dependencies between them in an optimized way. This component definitely deserves its own “Under the hood” article. For now, let’s simplify that it provides API to get a collection of all files in the project and its dependencies in the following shape: haste module system Array<{ 
// absolute file path 
file: string; 

// list of depedencies (modules imported in current file)
dependencies: Array<string>; 
}> Looking under the hood What do we know: set of files that have been added/modified/deleted and staged in Git and entire file system metadata Now we need to find an algorithm to detect and run only test files that have been impacted by this change. And Jest provides API to solve this problem: resolveInverse resolveInverse(
paths: Set<string>, 
filter: (file: string) => boolean, 
options?: ResolveModuleConfig, ): Array<string> { 
   return this.resolveInverseModuleMap(paths, filter, options)
          .map( module => module.file, ); 
} where: is a set of file paths that have changed paths is a predicate to detect whether the current file is a test file filter function object (not relevant for the algorithm, ignore it for now) options uses a very straightforward approach to solve this problem that is based on (BFS). First of all, it initializes the following sets: resolveInverseModuleMap Breadth First Search - set of files that have been affected. Basically, it is a temporary set that is mutated after every iteration of BFS, and serves as a termination indicator - the algorithm stops when it's empty. On the first iteration, this set is populated from provided as input. changed paths - set of files that have been affected. By default, this set is populated from input but with the condition that the file is actually a test file. On every iteration of BFS, every matched test file is removed from this file. At the end of the algorithm, the remaining file paths in this set are concatenated with the results of BFS execution. This is to handle a simple use case when the change was made in the test file and not in the source. relatedPaths test paths - files that have been already traversed and can be skipped from further processing. visitedModules So let’s visualize our algorithm. First of all, let’s define our example file system: Blocks in red represent changed modules (rectangles are test files, and circles are source files). Arrows start from parent to child (meaning that module is imported by and ). Initially, our data structures will look like this: a a.test a1 Our set is not empty. changed That means we need to traverse all files in our filesystem to get a list of dependencies for every module in set. After the first iteration, we already discovered that at least and needs to be run as dependencies of and respectively: changed b.test a1.test a.test a1 Carrying out another traversal. Now we see that is imported into both and but we already have in our originally changed files. In this case, we need to remove it from set and add it to the results. In case if didn't have any dependency, Jest would simply merge it into results when returning it to the upstream caller. b2 a.test b2.test a.test relatedPaths a.test In the end, we have only 2 test modules in our set and we already see that is in our visited set and does not have any dependents. Basically, no-op here - after this iteration changed set will become empty, and we will break out of our BFS loop. changed a.test b2.test As a result, we can narrow down our test scope from 5 test files down to 4. It’s not so impressive but keep in mind that I have picked a very small dataset for this example for simplicity — in real-world projects, there would be thousands of files, and improvement can be really drastic. You can find the original implementation . here Final thoughts Do you think this algorithm can be improved? What if we could have inverse links to the dependent modules as part of file metadata (similar to DOM elements that have reference to the parent)? In this case, we would not have to traverse the entire file system and focus only on a subset of it.

Check out my blog

Read My Stories

Too Long; Didn't Read

Discover Saakuru: Web3 Mass-Adoption with 0-FEES

Taking a Look under the Hood to See How Jest Finds Related Tests

Too Long; Didn't Read

Ildar Sharafeev

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Taking a Look under the Hood to See How Jest Finds Related Tests

Too Long; Didn't Read

Ildar Sharafeev

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES