# CallTrace, CallStack and RecursionTree

> CallTrace records a recursion: every call and every return takes a step.

Page: https://fframes-kit.pages.dev/docs/computer-science/call-trace-call-stack-and-recursion-tree/
Cargo feature: `cs` (`fframes-kit = { version = "..", features = ["cs"] }`)

`CallTrace` records a recursion: every call and every return takes a step. A returning call
stays on the stack for its step, showing its result, and leaves at the next. Each `Call`
keeps its label, its caller, the calls it made, its result and the steps where it is called
and returns. The tree of calls is laid out once with `layout::tidy_tree`.

- `CallTrace::recurse(name, arg, f)` runs `f` and records every call it makes through
  `r.call(arg)`, labelled `name(arg)`. The calls really run, so keep the input small: a tree
  of more than about 30 calls does not fit on the canvas.
- `CallTrace::fib(n)` and `CallTrace::factorial(n)` are two ready ones.
- `CallTrace::record()` records by hand: `call(label)`, `ret(result)`, `note`, `finish`.

`CallStack` piles a frame for each open call into a column as tall as the deepest stack (or
`capacity`). A call drops its frame on top, the innermost frame lights up, and a returning
frame shows `fact(2) = 2` in `colors.found`, then rises out. `RecursionTree` draws the call
tree: each node drops in under its caller, the open calls are outlined in `path_color`, the
innermost is lit, and each call's result appears beside it as it returns. Both play the same
trace, so they can run side by side in step. Gallery scenes: `CallStack` (`fact(5)`),
`RecursionTree` (`fib(4)` with its stack).

Gallery clip of `CallStack`: https://fframes-kit.pages.dev/media/scenes/CallStack-7c28482c.mp4

Gallery clip of `RecursionTree`: https://fframes-kit.pages.dev/media/scenes/RecursionTree-49c6f064.mp4

```rust
use fframes_kit::prelude::*;

let sum = CallTrace::recurse("sum", 3_u32, |r, n| if n == 0 { 0 } else { n + r.call(n - 1) });
assert_eq!(sum.calls().len(), 4);
assert_eq!(sum.max_stack(), 4);
assert_eq!(sum.steps().last().unwrap().note, "sum(3) = 6");

fn recursion<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a CallTrace) -> Svgr<'a> {
    let tree = ui.show(RecursionTree {
        trace: Some(trace),
        center: (1.6, 0.0),
        ..ui.defaults()
    });
    let stack = ui.show(CallStack {
        trace: Some(trace),
        center: (-4.6, 0.0),
        notes: false,
        ..ui.defaults()
    });
    fframes::svgr!(<g>{stack}{tree}</g>)
}
```

## API

Components are plain structs. Set the fields you need and fill the rest with `..ui.defaults()`: the defaults below come from the current theme (`theme.` values are fields of `Theme`).

### CallStack

The call stack of a recursion: a frame for each open call, `height` pixels tall and wide enough for the longest label, piled up from the bottom of a column `capacity` frames tall (or as tall as the trace needs), centred on `center` (units of `ui.space`). It plays a `CallTrace`, one step every `step_time` seconds from `delay`: a call drops a frame on top, the innermost frame lights up, a returning frame shows its result in `colors.found` and then rises out. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | `Option<&CallTrace>` | `None` | The recorded calls to play (`CallTrace`); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.6` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the column, in units of `ui.space`. |
| `height` | `f32` | `64.0` | Height of a frame in pixels. |
| `gap` | `f32` | `10.0` | Space between neighbouring frames in pixels. |
| `capacity` | `usize` | `0` | How many frames tall the column is; 0 uses the deepest the trace gets. |
| `notes` | `bool` | `true` | Whether the step's note is written under the stack. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the frames in each state (`colors.found` for a returning call). |
| `frame_color` | `Color` | `theme.colors.muted` | Colour of the column's outline. |
| `value_style` | `TextStyle` | `value_style` | The font of the call labels. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/recursion.rs#L366)

### RecursionTree

The tree of a recursion's calls: a node for each call, wide enough for the longest label and `height` pixels tall, `spacing` pixels between slots and `level` pixels between depths, centred on `center` (units of `ui.space`). It plays a `CallTrace`, one step every `step_time` seconds from `delay`: each call's node drops in under its caller, the open calls are outlined in `path_color` with the innermost lit, a returning call shows its result beside it in `colors.found`, and finished calls keep their result in `colors.sorted`. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | `Option<&CallTrace>` | `None` | The recorded calls to play (`CallTrace`); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.6` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the tree, in units of `ui.space`. |
| `spacing` | `f32` | `190.0` | Pixels between neighbouring node slots in a depth. |
| `level` | `f32` | `130.0` | Pixels between depths. |
| `height` | `f32` | `60.0` | Height of a node in pixels. |
| `notes` | `bool` | `true` | Whether the step's note is written under the tree. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the nodes in each state (`colors.found` for a returning call, `colors.sorted` for a finished one). |
| `edge_color` | `Color` | `theme.colors.muted` | Colour of the edges between a call and its callees. |
| `path_color` | `Color` | `theme.colors.accent` | Colour of the outline of the open calls. |
| `value_style` | `TextStyle` | `value_style` | The font of the call labels. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the results and notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/recursion.rs#L544)