Convert Streaming Call-Stack Samples into Function Events

Problem Description

Software profilers periodically take snapshots of an application's call stack. Given a sequence of timestamped call-stack samples and a final termination time end_time, convert these snapshots into an ordered list of function lifecycle events ("START" and "END").

Each sample is represented as a tuple (timestamp, stack), where stack is a list of strings representing the active call stack from the root caller (index 0) to the innermost active function (last index). Note that recursive calls may appear, meaning the same function name can appear multiple times at different depths.

To reconstruct the execution sequence:

1. The system starts with an empty stack before the first sample.
2. When transitioning between the previous stack and the current stack at timestamp, identify the longest common prefix (LCP) of both stacks (matching both function name and depth index).
3. Any frames in the previous stack above the common prefix have exited. They must emit "END" events in inside-out order (from the top of the previous stack down to the LCP boundary) at the current timestamp.
4. Any frames in the current stack above the common prefix have started. They must emit "START" events in outside-in order (from the LCP boundary up to the top of the current stack) at the current timestamp.
5. At end_time, any frames remaining on the stack must be closed by emitting "END" events in inside-out order.

Return the list of events. Each event is a tuple: (timestamp, event_type, function_name, depth), where depth is the 0-indexed position of the function frame in the stack.

Function Signature

def generate_call_events(
    samples: list[tuple[int, list[str]]],
    end_time: int
) -> list[tuple[int, str, str, int]]:
    pass

Constraints

• 0 samples[-1][0] if samples is non-empty.
• Function names consist of non-empty alphanumeric strings.

Examples

Example 1

Input:
samples = [
    (10, ["main", "foo"]),
    (20, ["main", "bar"])
]
end_time = 30

Output:
[
    (10, "START", "main", 0),
    (10, "START", "foo", 1),
    (20, "END", "foo", 1),
    (20, "START", "bar", 1),
    (30, "END", "bar", 1),
    (30, "END", "main", 0)
]

Explanation: At t=10, both main and foo start. At t=20, foo has exited and bar has begun. At t=30 (end_time), bar and main exit.

Example 2 (Recursion)

Input:
samples = [
    (100, ["eval", "eval", "eval"]),
    (150, ["eval"])
]
end_time = 200

Output:
[
    (100, "START", "eval", 0),
    (100, "START", "eval", 1),
    (100, "START", "eval", 2),
    (150, "END", "eval", 2),
    (150, "END", "eval", 1),
    (200, "END", "eval", 0)
]