Parse and Reconstruct Stack Trace

Extract the valid stack-frame lines from the **outermost (first) exception section** of a multi-line stack trace. ## Function ```python def solution(trace): ... ``` - **Input:** `trace` — a single string containing the whole stack trace, with lines separated by newlines. It may be empty. - **Output:** a **list of strings**, one per valid frame, in the same order they appear in the input (**most recent call first, oldest call last**). ## Line format Read the trace line by line. Before testing a line, **trim leading/trailing whitespace**. A line is a **valid frame** if, after trimming, it has the form: ``` at Module::Function(file:line) ``` Concretely, a trimmed line qualifies only when **all** of the following hold: - It starts with the prefix `at ` (the word `at` followed by a space). - Let **body** be the text after that prefix, with its own surrounding whitespace trimmed (e.g. `Module::Function(file:line)`). - **body** ends with a closing parenthesis `)`. - **body** contains an opening parenthesis `(` and, after it, a colon `:` (use the **last** `(` and the **last** `:`); the `(` must come before the `:`, and the `:` must not be the final character (so a line number follows it). - The text between that `:` and the closing `)` is the **line number**: it must be **non-empty and consist only of digits** (a non-negative integer). - The text before the `(` (the `Module::Function` part) must be **non-empty**. ## What to return for each frame For a valid frame, append the **body** — that is, the frame **without** the leading `at ` prefix and with surrounding whitespace removed (e.g. `App::run(app.py:10)`). Do not include `at ` in the output. ## Section boundary Scan the lines top to bottom. As soon as you reach a line whose **trimmed** form starts with `Caused by:`, **stop immediately** — that line and everything after it belongs to a nested cause and must be ignored. Only the first (outermost) exception section is parsed. ## Other rules - **Skip** any line that is blank, malformed, or does not match the valid-frame format (e.g. header lines like `RuntimeError: boom` or `random text`, or a frame whose body has no `(...:...)` shape such as `at BadLine(nope)`). - If `trace` is empty, or if a `Caused by:` line appears before any valid frame, return an **empty list**. - Preserve the original order of the valid frames you keep (most recent to oldest). ## Constraints - `0 <= len(trace) <= 200000` - The trace contains at most `10000` lines. - A valid frame line must start with `at ` after trimming and must end with `(file:line)`, where `line` is a non-negative integer. - Only the first exception section is parsed; later `Caused by:` sections are ignored. ## Examples **Input** ``` RuntimeError: boom at App::run(app.py:10) at Main::main(main.py:20) ``` **Output:** `['App::run(app.py:10)', 'Main::main(main.py:20)']` --- **Input** ``` ValueError random text at Parser::parse(parser.py:7) at BadLine(nope) Caused by: IOError at IO::read(io.py:3) ``` **Output:** `['Parser::parse(parser.py:7)']` (`ValueError` and `random text` are not frames; `at BadLine(nope)` has no `:` after its `(`, so it fails the `(file:line)` format; parsing stops at `Caused by:`, so `at IO::read(io.py:3)` is ignored.) --- **Input** ``` TopError Caused by: Inner at X::f(x.py:1) ``` **Output:** `[]` (the `Caused by:` line ends the section before any frame is collected.)

Reconstruct the merged call hierarchy of a single thread's stack trace and return it as a **forest of nested dictionaries**. ## Function ```python def solution(trace): ... ``` `trace` is a single string containing the full multi-line stack trace (lines separated by `\n`). Return a nested dictionary of the form `{frame: child_subtree}` (see **Output** below). ## Background A stack trace may contain several **exception sections** chained by `Caused by:` lines, and a section may abbreviate its repeated tail using a `... N more` line. Your job is to rebuild every section's full call stack and merge them all into one tree. ## Frame lines After trimming surrounding whitespace, a **valid frame line** has the form: ``` at Module::Function(file:line) ``` A line is a valid frame **only if** the trimmed line: - starts with `at ` (the literal `at` followed by a space), and - ends with `)`, and - contains an opening `(` that comes before the final `:`, and - has a non-empty part before that `(`, and - has a **line number** (the text between the final `:` and the closing `)`) consisting only of digits (a non-negative integer). The **frame** you record is the part of the line **after** `at ` (for example, the line `at B::b(b.py:2)` yields the frame `B::b(b.py:2)`). Lines that do not satisfy every rule above are **malformed** and must be ignored. ## Sections - The **first section** begins at the start of the trace. - Each line whose trimmed form starts with `Caused by:` ends the current section and begins a **new section** (the `Caused by:` line itself is not a frame). - Within a section, valid frame lines are collected **in the order they appear**, which is most recent call first down to oldest call. ## The `... N more` abbreviation A line whose trimmed form starts with `... ` and ends with ` more`, with a digit-only number `N` in between, is an **abbreviation line**. Each section contains **at most one** such line. When a section (other than the first) has an abbreviation `... N more`, append the **last N frames of the previous section's fully reconstructed stack** to this section's collected frames: - "Previous" means the section immediately before this one, **after** that section has itself been fully reconstructed (so abbreviations chain transitively through `Caused by:` sections). - If `N` is larger than the number of frames in the previous reconstructed stack, append **all** of them. - An abbreviation line in the first section (which has no previous section) contributes nothing. ## Output Insert every fully reconstructed stack into a single tree, walking each stack from its **oldest call to its most recent call**. The tree is represented by nested dictionaries: each frame maps to the dictionary of its child frames, e.g. `{frame: {childFrame: {...}}}`. A leaf frame maps to an empty dictionary `{}`. - Stacks that share a common prefix of oldest calls share those nodes in the tree. - If multiple disconnected roots exist, they all appear at the **top level** of the returned dictionary. - An empty reconstructed stack (for example, a section with only malformed lines) contributes nothing. ## Edge cases - An empty `trace` returns `{}`. - Malformed lines, blank lines, and exception-description lines are silently skipped. ## Example Input: ``` Outer at Service::run(s.py:30) at Controller::handle(c.py:20) at Main::main(m.py:10) Caused by: ParseError at Parser::parse(p.py:5) ... 2 more ``` The first section's stack (most recent → oldest) is `Service::run`, `Controller::handle`, `Main::main`. The second section starts with `Parser::parse`, then `... 2 more` appends the last 2 frames of the previous reconstructed stack (`Controller::handle`, `Main::main`), giving `Parser::parse`, `Controller::handle`, `Main::main`. Inserting both stacks oldest-first and merging the shared `Main::main → Controller::handle` prefix produces: ```python {"Main::main(m.py:10)": {"Controller::handle(c.py:20)": {"Service::run(s.py:30)": {}, "Parser::parse(p.py:5)": {}}}} ``` ## Constraints - `0 <= len(trace) <= 200000` - The trace contains at most 10000 lines. - Each section contains at most one abbreviation line of the form `... N more`. - A valid frame line must start with `at ` after trimming and must end with `(file:line)` where `line` is a non-negative integer.

# Find the Deepest Frame of the Thrown Exception Given a Java-style stack trace as a single string `trace`, return the **deepest frame of the actually-thrown exception**, or `None` if no such frame can be recovered. Implement: ```python def solution(trace): ... ``` ## Background A stack trace is divided into **sections**. The first section is the original error; each subsequent section is introduced by a line whose trimmed text begins with `Caused by:`. These sections form a *cause chain*, and the **last section in the chain is the actually-thrown exception** — the one whose deepest frame you must report. Within a section, frames are listed **most-recent first** (top) to **oldest last** (bottom). The call hierarchy is rooted at the oldest call, so the **deepest frame is the most-recent frame** — i.e. the **first** valid frame listed in the last section after expansion. ## Line types Parse the trace **line by line** (split on newlines). Each line, after trimming surrounding whitespace, is one of: - **Section header** — starts with `Caused by:`. Closes the current section and begins a new one. - **Frame line** — a valid frame has the trimmed form `at Module::Function(file:line)`. Specifically, after trimming it must: - start with `at ` (then take the remaining text as the **frame body**, e.g. `Module::Function(file:line)`), - end with `)`, - contain a `(` such that the text before the last `(` is **non-empty**, and - have, between the last `(` and the closing `)`, a `file:line` part whose portion **after the last `:` is a non-negative integer** (all digits). The value you ultimately return is this **frame body** (the text after `at `), e.g. `B::work(b.py:2)`. - **Abbreviation line** — the form `... N more` (trimmed text starts with `... ` and ends with ` more`, with `N` a non-negative integer in between). It means: this section's stack continues with the **last `N` frames of the previous section's fully reconstructed stack**. Each section contains **at most one** abbreviation line. - **Anything else** (including the leading exception-message line of a section, and any malformed frame) is **ignored**. ## Reconstruction Process sections in order. For each section, its reconstructed frame list is its own explicit valid frames followed by, **if it has a `... N more` and a previous section exists**, the last `k = min(N, len(previous_reconstructed))` frames of the **previous *fully reconstructed*** section (so inheritance composes across multiple nested causes). Inherited frames are appended **after** the section's own frames. ## Return value Return the **first frame** (index `0`, the most-recent / deepest) of the **last** section's reconstructed frame list. Return `None` when: - the trace is empty, or - the last section has **no** recoverable frame (no valid explicit frame and nothing recovered via `... N more`). Note: if the deepest section has no explicit valid frames, you may still recover its frames purely from `... N more`. ## Constraints - `0 <= len(trace) <= 200000` - The trace contains at most `10000` lines. - Each section contains at most one abbreviation line of the form `... N more`. - A valid frame line must start with `at ` after trimming and must end with `(file:line)` where `line` is a non-negative integer. ## Examples **Example 1** ``` Error at B::work(b.py:2) at A::main(a.py:1) ``` Single section; first valid frame is the deepest. Returns `B::work(b.py:2)`. **Example 2** ``` Outer at Service::run(s.py:3) at Main::main(m.py:1) Caused by: Inner at Parser::parse(p.py:2) ... 1 more ``` The last (thrown) section's first frame is `Parser::parse(p.py:2)`. Returns `Parser::parse(p.py:2)`. **Example 3** ``` Outer at X::x(x.py:2) at Main::main(m.py:1) Caused by: Inner bad line ... 2 more ``` The last section has no valid explicit frame; its frames are recovered from `... 2 more` (the last 2 frames of the reconstructed parent). The deepest is `X::x(x.py:2)`. Returns `X::x(x.py:2)`. **Example 4** ``` (empty string) ``` Returns `None`.