Jest Timer Simulation: Mastering runAllTimers

Jest provides powerful tools for testing asynchronous code, especially when dealing with timers like setTimeout and setInterval. This challenge focuses on implementing a core timer utility that mimics Jest's runAllTimers functionality, allowing you to precisely control and advance time in your tests. Understanding how to simulate timer execution is crucial for writing reliable and deterministic tests for time-dependent logic.

Problem Description

Your task is to implement a function named runAllTimers that simulates the execution of all pending timers (created by setTimeout and setInterval) in a JavaScript environment. This function should advance the virtual clock by the minimum amount necessary to trigger the next pending timer, execute it, and repeat this process until no timers are left.

Key Requirements:

1. Timer Execution: The function must execute timers in the order they are scheduled.
2. setTimeout and setInterval: Support both setTimeout and setInterval.
3. Timer Cancellation: Correctly handle timers that are cleared using clearTimeout or clearInterval before their scheduled execution.
4. Re-scheduling: If a timer callback re-schedules itself or schedules new timers, these new timers should be considered for execution in subsequent steps.
5. Infinite Loops: Implement a mechanism to detect and break out of potential infinite loops caused by timers that continuously re-schedule themselves without advancing the clock.

Expected Behavior:

The runAllTimers function will take no arguments. It should internally manage a queue of pending timers. When called, it will repeatedly: a. Find the timer with the earliest scheduled execution time. b. Advance the virtual clock to that execution time. c. Execute the timer's callback function. d. Remove the executed timer from the queue. e. If the callback re-scheduled or scheduled new timers, add them to the queue. f. Repeat until the timer queue is empty.

Edge Cases:

• No timers are scheduled.
• Timers are scheduled with zero delay (setTimeout(fn, 0)).
• Timers are cleared before they execute.
• Timers that reschedule themselves indefinitely.
• setInterval timers that are cleared after a certain number of executions.

Examples

Example 1:

// Assume a global timer management system exists where
// timers are registered and their execution times can be manipulated.

// Simple setTimeout
const timer1 = setTimeout(() => console.log('Timer 1 executed'), 100);
const timer2 = setTimeout(() => console.log('Timer 2 executed'), 50);

// In a test scenario, we would call runAllTimers() here.
// After runAllTimers() is called:
// Expected output (console logs):
// Timer 2 executed
// Timer 1 executed

Explanation: timer2 is scheduled for 50ms, timer1 for 100ms. runAllTimers will first execute timer2 at 50ms, then timer1 at 100ms.

Example 2:

// setInterval and clearInterval
let count = 0;
const intervalTimer = setInterval(() => {
    count++;
    console.log(`Interval ${count}`);
    if (count === 3) {
        clearInterval(intervalTimer);
    }
}, 75);

// In a test scenario, we would call runAllTimers() here.
// After runAllTimers() is called:
// Expected output (console logs):
// Interval 1
// Interval 2
// Interval 3

Explanation: The setInterval will execute every 75ms. runAllTimers will simulate these executions. The clearInterval within the callback will stop the interval after the third execution.

Example 3:

// Timer cancellation and re-scheduling
let value = 0;
const timerA = setTimeout(() => {
    value = 10;
    console.log('Timer A executed');
    const timerB = setTimeout(() => {
        value = 20;
        console.log('Timer B executed');
    }, 30);
}, 50);

const timerC = setTimeout(() => {
    console.log('Timer C executed');
    clearTimeout(timerA); // Cancel timerA
}, 40);

// In a test scenario, we would call runAllTimers() here.
// After runAllTimers() is called:
// Expected output (console logs):
// Timer C executed
// Timer A executed (but its inner timer B is NOT scheduled because timer A was cleared)
// Final value of 'value' should be 10.

Explanation: timerC is scheduled for 40ms. timerA is scheduled for 50ms. runAllTimers executes timerC first. timerC clears timerA. Then runAllTimers advances to 50ms, but finds timerA has been cleared, so it's not executed. The inner timerB scheduled by timerA is never added to the pending queue because timerA itself was cleared.

Constraints

• The simulation should be able to handle up to 1000 pending timers at any given time.
• Timer delays will be non-negative integers representing milliseconds.
• Callback functions will be valid JavaScript functions.
• The simulation should complete within a reasonable time for testing purposes, avoiding excessive computational complexity.

Notes

• You will need to create a mechanism to track pending timers, their scheduled execution times, and their callback functions. A priority queue or a sorted array would be suitable data structures.
• Consider how to mock or intercept the native setTimeout and setInterval functions to register timers into your system.
• Think about how to represent the "current time" in your simulation.
• The challenge is to implement the logic of runAllTimers, not necessarily to replace the global setTimeout and setInterval entirely. You might assume these functions add timers to your internal queue.