Intelligent Jest Test Ordering

You're working on a large Jest test suite where the order of test execution can significantly impact performance and lead to flaky tests. This challenge focuses on implementing a system that intelligently orders tests based on their dependencies, ensuring critical tests run first and potentially improving overall execution time by grouping related tests.

Problem Description

You need to develop a mechanism to dynamically order Jest tests within a describe block. This ordering should be based on a provided dependency graph. Tests that have no dependencies should run first. If test A depends on test B, test B must complete successfully before test A can start. The system should handle circular dependencies and ensure all tests are eventually executed.

Key Requirements:

• Dependency Resolution: Implement a function that accepts a list of tests and a dependency graph, returning an array of tests in a valid execution order.
• Topological Sort: The core logic should resemble a topological sort, prioritizing tests with no incoming dependencies.
• Handling Circular Dependencies: If a circular dependency is detected, the tests involved in the cycle should be grouped together and executed, but the overall order should still prioritize non-cyclic dependencies.
• Jest Integration: The solution should be designed to be integrable with Jest's describe and test functions, potentially by providing a custom test runner or by transforming test definitions. For this challenge, focus on the core ordering logic.
• Output Format: The output should be an array of test identifiers (e.g., strings representing test names) in the order they should be executed.

Expected Behavior:

Tests without dependencies should appear earliest in the output array. If test A depends on B, B should appear before A. If A depends on B and B depends on C, the order should be C, B, A (assuming no other dependencies).

Edge Cases:

• Empty test suite.
• Tests with no dependencies.
• Tests with multiple dependencies.
• Circular dependencies (e.g., A depends on B, B depends on A).
• Dependencies on tests that do not exist.

Examples

Example 1:

Tests: ['test_A', 'test_B', 'test_C', 'test_D']
Dependencies: {
  'test_A': ['test_B'],
  'test_B': [],
  'test_C': ['test_A', 'test_D'],
  'test_D': []
}

Output: ['test_B', 'test_D', 'test_A', 'test_C']

Explanation: test_B and test_D have no dependencies and can run first. test_A depends on test_B, so test_B must precede test_A. test_C depends on test_A and test_D, so it must run after both. The output respects these constraints.

Example 2:

Tests: ['init', 'login', 'logout', 'cleanup']
Dependencies: {
  'init': [],
  'login': ['init'],
  'logout': ['login'],
  'cleanup': ['logout']
}

Output: ['init', 'login', 'logout', 'cleanup']

Explanation: This is a simple sequential dependency. init runs first, then login (which depends on init), then logout (depends on login), and finally cleanup (depends on logout).

Example 3: (Circular Dependency)

Tests: ['feature_1', 'feature_2', 'utility_a', 'utility_b']
Dependencies: {
  'feature_1': ['utility_a'],
  'feature_2': ['feature_1', 'utility_b'],
  'utility_a': ['utility_b'],
  'utility_b': ['utility_a'] // Circular dependency between utility_a and utility_b
}

Output: ['utility_a', 'utility_b', 'feature_1', 'feature_2'] or ['utility_b', 'utility_a', 'feature_1', 'feature_2']

Explanation: utility_a and utility_b have a circular dependency. The algorithm should detect this and group them together. Since feature_1 depends on utility_a and feature_2 depends on feature_1 and utility_b, the utilities must run before feature_1, which must run before feature_2. The order within the utility_a/utility_b cycle can vary.

Constraints

• The number of tests will be between 0 and 1000.
• The dependency graph will be represented as a Record<string, string[]>, where keys are test names and values are arrays of test names they depend on.
• Test names are unique strings.
• Dependencies will only refer to other test names within the provided list of tests.
• The solution should aim for an efficient ordering algorithm, ideally with a time complexity close to O(V + E), where V is the number of tests and E is the number of dependencies.

Notes

• Consider how you might represent the dependencies internally to facilitate efficient traversal.
• Think about how to detect and handle cycles in the dependency graph.
• While the ultimate goal is Jest integration, for this challenge, focus on producing the correctly ordered array of test names. You can simulate this by creating a function that takes your test definitions and dependency map and returns the ordered list.
• A robust solution might involve a depth-first search (DFS) based approach for topological sorting.