src/vs/base/test/common/executionGraph.ts
543 LOC · 415 covered · 128 uncovered · 21 ranges · 6 concepts · 6 introducers · 6 tests
File neighbourhood
The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.
Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file
In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.
Graph controls are ready.
Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.
1
>
/*---------------------------------------------------------------------------------------------
executionGraph.ts ×4
2
>
* Copyright (c) Microsoft Corporation. All rights reserved.
3
>
* Licensed under the MIT License. See License.txt in the project root for license information.
4
>
*--------------------------------------------------------------------------------------------*/
5
>
6
>
/**
7
>
* Plain, renderer-friendly description of an execution history produced by a
8
>
* traced scheduler. These types have no dependency on the tracing or
9
>
* scheduling implementation — they can be built by hand in tests or by the
10
>
* `buildHistoryFromTasks` adapter below.
11
>
*/
12
>
13
>
export interface ExecutionRoot {
14
>
readonly label: string;
15
>
}
16
>
17
>
export interface ExecutionEvent {
18
>
/** Relative time (e.g. ms since startTime). Must be >= 0 and non-decreasing in history order. */
19
>
readonly time: number;
20
>
readonly label: string;
21
>
readonly root: ExecutionRoot;
22
>
/** `undefined` means this event is a direct child of its root. */
23
>
readonly parent: ExecutionEvent | undefined;
24
>
/** Caller frame extracted from the scheduling stack trace. */
25
>
readonly detail?: string;
26
>
}
27
>
28
>
export interface ExecutionHistory {
29
>
/** Roots in first-appearance order (column order for renderers). */
30
>
readonly roots: readonly ExecutionRoot[];
31
>
/** Events in time order. */
32
>
readonly events: readonly ExecutionEvent[];
33
>
}
34
>
35
>
// -----------------------------------------------------------------------------
36
>
// Adapter: ScheduledTask[] -> ExecutionHistory
37
>
// -----------------------------------------------------------------------------
38
>
39
>
interface TraceLike {
40
>
readonly parent: TraceLike | undefined;
41
>
readonly root: { readonly label: string };
42
>
}
43
>
44
>
interface ScheduledTaskLike {
45
>
readonly time: number;
46
>
readonly source: { toString(): string; readonly stackTrace?: string };
47
>
readonly trace?: TraceLike;
48
>
}
49
>
50
>
/**
51
>
* A log entry to weave into the history alongside scheduled tasks. Each log is
52
>
* tagged with the trace that was current when it was emitted.
53
>
*/
54
>
export interface LogEntryLike {
55
>
readonly trace: TraceLike;
56
>
readonly message: string;
57
>
}
58
>
59
>
/**
60
>
* Convert a list of scheduled tasks (each carrying a causal `trace`) into a
61
>
* plain `ExecutionHistory`. Untraced tasks are dropped. A task's parent event
62
>
* is the most recent earlier task whose `trace` is `task.trace.parent`; if
63
>
* `task.trace.parent` is the trace root itself, the event has no parent event
64
>
* (it is a direct child of the root).
65
>
*
66
>
* `logs` (if given) are interleaved as synthetic events: each log's parent is
67
>
* the task event whose trace matches the log's current trace at emission
68
>
* time (or the nearest ancestor task event), and its time is inherited from
69
>
* that parent. Within a single parent task, logs are kept in emission order
70
>
* and inserted directly after the parent event.
71
>
*/
72
>
export function buildHistoryFromTasks(
73
tasks: readonly ScheduledTaskLike[],
74
startTime: number,
75
logs: readonly LogEntryLike[] = [],
76
): ExecutionHistory {
77
const rootByTrace = new Map<unknown, ExecutionRoot>();
78
const roots: ExecutionRoot[] = [];
79
const eventByTrace = new Map<unknown, ExecutionEvent>();
80
const taskEvents: ExecutionEvent[] = [];
81
82
for (const task of tasks) {
83
const trace = task.trace;
84
if (!trace) { continue; }
85
86
let root = rootByTrace.get(trace.root);
87
if (!root) {
88
root = { label: trace.root.label };
89
rootByTrace.set(trace.root, root);
90
roots.push(root);
91
}
92
93
// Find the parent event by walking up the trace chain until we hit
94
// either a trace whose event we know, or the trace root.
95
let parentEvent: ExecutionEvent | undefined;
96
for (let p = trace.parent; p; p = p.parent) {
97
const e = eventByTrace.get(p);
98
if (e) { parentEvent = e; break; }
99
}
100
101
const event: ExecutionEvent = {
102
time: task.time - startTime,
103
label: `${task.source}`,
104
root,
105
parent: parentEvent,
106
detail: extractCallerFrame(task.source.stackTrace),
107
};
108
eventByTrace.set(trace, event);
109
taskEvents.push(event);
110
}
111
112
// Group log entries by their parent task event, preserving emission
113
// order within each group. A log without an enclosing task event is
114
// dropped (e.g. logs emitted at root before any task ran).
115
const logsByParent = new Map<ExecutionEvent, ExecutionEvent[]>();
116
for (const entry of logs) {
117
let parentEvent: ExecutionEvent | undefined;
118
for (let p: TraceLike | undefined = entry.trace; p; p = p.parent) {
119
const e = eventByTrace.get(p);
120
if (e) { parentEvent = e; break; }
121
}
122
if (!parentEvent) { continue; }
123
124
const logEvent: ExecutionEvent = {
125
time: parentEvent.time,
126
label: `log: ${entry.message}`,
127
root: parentEvent.root,
128
parent: parentEvent,
129
};
130
const bucket = logsByParent.get(parentEvent);
131
if (bucket) { bucket.push(logEvent); }
132
else { logsByParent.set(parentEvent, [logEvent]); }
133
}
134
135
// Interleave: each task event followed by its logs in emission order.
136
const events: ExecutionEvent[] = [];
137
for (const e of taskEvents) {
138
events.push(e);
139
const ls = logsByParent.get(e);
140
if (ls) { events.push(...ls); }
141
}
142
143
return { roots, events };
144
}
146
>
/**
147
>
* Extract up to {@link MAX_DETAIL_FRAMES} stack frames that are not from
148
>
* the scheduler/tracing infrastructure. Returns the frames joined by
149
>
* newline (callers may render them stacked) or `undefined` when none.
150
>
*/
151
>
const _skipFramePatterns = [
152
>
/[\\/]virtualScheduling[\\/]/,
153
>
/[\\/]vs[\\/]base[\\/]common[\\/]async\./,
154
>
/timeTravelScheduler|traceableTimeApi/,
155
>
/RunOnceScheduler\.schedule/,
156
>
/scheduleAtNextAnimationFrame/,
157
>
/TimeoutTimer\.cancelAndSet/,
158
>
/TimeoutTimer\.setIfNotSet/,
159
>
/timeoutDeferred/,
160
>
/createTimeout/,
161
>
];
162
>
163
>
const MAX_DETAIL_FRAMES = 5;
164
>
165
function extractCallerFrame(stackTrace: string | undefined): string | undefined {
166
if (!stackTrace) { return undefined; }
167
const frames: string[] = [];
168
for (const line of stackTrace.split('\n')) {
169
const trimmed = line.trim();
170
if (!trimmed.startsWith('at ')) { continue; }
171
if (_skipFramePatterns.some(p => p.test(trimmed))) { continue; }
172
frames.push(trimmed.slice(3));
173
if (frames.length >= MAX_DETAIL_FRAMES) { break; }
174
}
175
return frames.length === 0 ? undefined : frames.join('\n');
176
}
178
>
// -----------------------------------------------------------------------------
179
>
// Renderer: swimlane (one column per root)
180
>
// -----------------------------------------------------------------------------
181
>
182
>
/**
183
>
* Render `history` as a swimlane diagram: one column per root, events in the
184
>
* column of their root, parent→child shown via `├─`/`└─` indentation, active
185
>
* ancestors shown via `│` continuation lines.
186
>
*
187
>
* Example:
188
>
* ```
189
>
* A B
190
>
* +0ms ├─ setTimeout
191
>
* +10ms │ ├─ setTimeout
192
>
* +16ms ├─ rAF │
193
>
* +50ms └─ setTimeout
194
>
* ```
195
>
*/
196
>
export function renderSwimlanes(history: ExecutionHistory): string {
198
>
if (events.length === 0) { return '(empty history)'; }
200
return events.map(e => `[+${e.time}ms] ${e.label}`).join('\n');
201
}
203
>
const n = events.length;
204
>
205
>
// Parent index per event (-1 = direct child of root).
206
>
const parentOf = new Array<number>(n).fill(-1);
207
>
const childrenOf: number[][] = Array.from({ length: n }, () => []);
208
>
const indexOfEvent = new Map<ExecutionEvent, number>();
209
>
for (let i = 0; i < n; i++) { indexOfEvent.set(events[i], i); }
210
>
for (let i = 0; i < n; i++) {
211
>
const p = events[i].parent;
212
>
if (p) {
213
>
const pi = indexOfEvent.get(p);
214
>
if (pi !== undefined) {
215
>
parentOf[i] = pi;
216
>
childrenOf[pi].push(i);
217
>
}
218
>
}
219
>
}
220
>
221
>
// Is this event the last child of its parent event?
222
>
const isLastChild = new Array<boolean>(n).fill(false);
223
>
for (let i = 0; i < n; i++) {
224
>
const p = parentOf[i];
225
>
if (p >= 0 && childrenOf[p][childrenOf[p].length - 1] === i) { isLastChild[i] = true; }
226
>
}
227
>
228
>
// Slot = visual column index for indentation. By default every child
229
>
// gets its own column (slot = parent.slot + 1) so pure last-child chains
230
>
// still show their depth structure. Once we pass the depth threshold,
231
>
// last-children collapse into their parent's slot to keep deeply nested
232
>
// traces from walking off the screen.
233
>
const COLLAPSE_DEPTH_THRESHOLD = 6;
234
>
const depthOf = new Array<number>(n).fill(0);
235
>
const slotOf = new Array<number>(n).fill(0);
236
>
for (let i = 0; i < n; i++) {
237
>
const p = parentOf[i];
238
>
if (p >= 0) {
239
>
depthOf[i] = depthOf[p] + 1;
240
>
const collapse = isLastChild[i] && depthOf[i] >= COLLAPSE_DEPTH_THRESHOLD;
241
>
slotOf[i] = slotOf[p] + (collapse ? 0 : 1);
242
>
}
243
>
}
244
>
245
>
// Display label = label plus the caller stack frame when present,
246
>
// e.g. `setTimeout · MyClass.foo (file.ts:42)`. Computed once so width
247
>
// math and the per-row render agree. `detailLines` holds any additional
248
>
// stack frames beyond the first; they are rendered as continuation rows.
249
>
const displayLabelOf = new Array<string>(n);
250
>
const detailLinesOf = new Array<readonly string[]>(n);
251
>
for (let i = 0; i < n; i++) {
252
>
const e = events[i];
253
>
const frames = e.detail ? e.detail.split('\n') : [];
254
>
displayLabelOf[i] = frames.length > 0 ? `${e.label} · ${frames[0]}` : e.label;
255
>
detailLinesOf[i] = frames.slice(1);
256
>
}
257
>
258
>
// Column width per root: indentation uses slots (last-children collapse
259
>
// into their parent's slot), so width must be slot-based to avoid
260
>
// reserving empty space for degenerate last-child chains.
261
>
const widthOf = new Map<ExecutionRoot, number>();
262
>
for (const r of roots) { widthOf.set(r, r.label.length); }
263
>
for (let i = 0; i < n; i++) {
264
>
const baseIndent = slotOf[i] * 3 + 3;
265
>
const maxLen = Math.max(displayLabelOf[i].length, ...detailLinesOf[i].map(l => l.length + 2));
266
>
const w = baseIndent + maxLen;
267
>
const cur = widthOf.get(events[i].root) ?? 0;
268
>
if (w > cur) { widthOf.set(events[i].root, w); }
269
>
}
270
>
271
>
// Compute time column width based on max time (rounded).
272
>
const maxTime = n > 0 ? Math.max(...events.map(e => Math.round(e.time))) : 0;
executionGraph.ts ×2
273
>
const timeColWidth = `+${maxTime}ms`.length;
274
>
275
>
const lines: string[] = [];
276
>
277
>
// Header: root labels centered in their columns.
278
>
const header: string[] = [];
279
>
for (const r of roots) {
281
>
header.push(r.label.padStart(Math.ceil((w + r.label.length) / 2)).padEnd(w));
282
>
}
283
>
lines.push(`${' '.repeat(timeColWidth)} ${header.join(' ')}`.trimEnd());
284
>
285
>
// Compute lastChild index for each event (for drawing continuation lines).
286
>
const lastChildOf = new Array<number>(n).fill(-1);
287
>
for (let i = 0; i < n; i++) {
288
>
const kids = childrenOf[i];
289
>
if (kids.length > 0) { lastChildOf[i] = kids[kids.length - 1]; }
290
>
}
291
>
292
>
// Per-root: set of "active ancestor" event indices (events with children
293
>
// whose last child has not yet been rendered, i.e. lastChildOf[a] > i).
294
>
const laneStacks = new Map<ExecutionRoot, Set<number>>();
295
>
for (const r of roots) { laneStacks.set(r, new Set()); }
296
>
297
>
for (let i = 0; i < n; i++) {
298
>
const event = events[i];
299
>
const timeStr = `+${Math.round(event.time)}ms`.padStart(timeColWidth);
300
>
301
>
const parts: string[] = [];
302
>
for (const r of roots) {
303
>
const w = widthOf.get(r)!;
304
>
const stack = laneStacks.get(r)!;
305
>
306
>
if (r === event.root) {
307
>
// Event line: slot-based indentation, then `├─`/`└─` + label.
308
>
// For each slot s in 0..(slot-1), show `│ ` if an ancestor
309
>
// at slot s is still active (lastChild > current), else ` `.
310
>
const slot = slotOf[i];
311
>
const indent: string[] = [];
312
>
for (let s = 0; s < slot; s++) {
313
>
let hasActive = false;
314
>
for (const a of stack) {
315
>
if (slotOf[a] === s && lastChildOf[a] > i) { hasActive = true; break; }
316
>
}
317
>
indent.push(hasActive ? '│ ' : ' ');
318
>
}
319
>
const prefix = isLastChild[i] ? '└─ ' : '├─ ';
320
>
parts.push(`${indent.join('')}${prefix}${displayLabelOf[i]}`.padEnd(w));
321
>
} else {
323
>
// an active ancestor (lastChild > i). Also show a `|` placeholder
324
>
// at the slot of the next upcoming event if it's a non-last child.
325
>
const activeSlots: number[] = [];
326
>
for (const a of stack) {
327
>
if (lastChildOf[a] > i) { activeSlots.push(slotOf[a]); }
328
>
}
329
>
const maxSlot = Math.max(...activeSlots, -1);
330
>
const chars: string[] = new Array(Math.max(maxSlot + 1, 0)).fill(' ');
331
>
for (const s of activeSlots) { chars[s] = '│ '; }
332
>
333
>
// Find the next event in root r strictly after i.
334
>
let nextJ = -1;
335
>
for (let j = i + 1; j < n; j++) {
336
>
if (events[j].root === r) { nextJ = j; break; }
337
>
}
338
>
if (nextJ >= 0 && parentOf[nextJ] >= 0) {
339
>
const s = slotOf[nextJ];
340
>
// Reserve slot if next event will open a new branch (├─).
341
>
if (!isLastChild[nextJ]) {
342
>
while (chars.length <= s) { chars.push(' '); }
343
>
if (chars[s] === ' ') { chars[s] = '| '; }
344
>
}
345
>
}
346
>
347
>
// Trim trailing empty cells.
348
>
while (chars.length > 0 && chars[chars.length - 1] === ' ') { chars.pop(); }
349
>
parts.push(chars.join('').padEnd(w));
350
>
}
352
>
353
>
lines.push(`${timeStr} ${parts.join(' ')}`.trimEnd());
354
>
355
>
// Continuation lines for any extra stack frames. Indented under the
356
>
// label, with no time column, no `├─`/`└─` glyph, and `│ `
357
>
// continuations for active ancestor lanes (including this event itself
358
>
// when it has children that haven't been rendered yet).
359
>
const extras = detailLinesOf[i];
360
>
if (extras.length > 0) {
361
const slot = slotOf[i];
362
const stackForExtras = laneStacks.get(event.root)!;
363
// Pretend this event is already on the lane stack so its column
364
// gets a continuation glyph beneath the `├─`/`└─`.
365
const hasOpenChildren = childrenOf[i].length > 0;
366
const extraIndent: string[] = [];
367
for (let s = 0; s < slot; s++) {
368
let hasActive = false;
369
for (const a of stackForExtras) {
370
if (slotOf[a] === s && lastChildOf[a] > i) { hasActive = true; break; }
371
}
372
extraIndent.push(hasActive ? '│ ' : ' ');
373
}
374
extraIndent.push(hasOpenChildren ? '│ ' : ' ');
375
for (const extra of extras) {
376
const extrasParts: string[] = [];
377
for (const r of roots) {
378
const w = widthOf.get(r)!;
379
if (r === event.root) {
380
extrasParts.push(`${extraIndent.join('')}${extra}`.padEnd(w));
381
} else {
382
// Reuse the same continuation logic: any active lane on
383
// other roots needs `│` glyphs.
384
const otherStack = laneStacks.get(r)!;
385
const activeSlots: number[] = [];
386
for (const a of otherStack) {
387
if (lastChildOf[a] > i) { activeSlots.push(slotOf[a]); }
388
}
389
const maxSlot = Math.max(...activeSlots, -1);
390
const chars: string[] = new Array(Math.max(maxSlot + 1, 0)).fill(' ');
391
for (const s of activeSlots) { chars[s] = '│ '; }
392
while (chars.length > 0 && chars[chars.length - 1] === ' ') { chars.pop(); }
393
extrasParts.push(chars.join('').padEnd(w));
394
}
395
}
396
const timePad = ' '.repeat(timeColWidth);
397
lines.push(`${timePad} ${extrasParts.join(' ')}`.trimEnd());
398
}
399
}
401
>
// Stack maintenance: push this event if it has children, then pop
402
>
// any ancestors whose last child was just rendered (propagating up).
403
>
const stack = laneStacks.get(event.root)!;
404
>
if (childrenOf[i].length > 0) { stack.add(i); }
405
>
let cur = i;
406
>
while (isLastChild[cur]) {
407
>
const p = parentOf[cur];
408
>
if (p < 0) { break; }
409
>
stack.delete(p);
410
>
cur = p;
411
>
}
412
>
}
413
>
414
>
return lines.join('\n');
415
>
}
417
>
// -----------------------------------------------------------------------------
418
>
// Renderer: interleaved lane graph (git-log style)
419
>
// -----------------------------------------------------------------------------
420
>
421
>
/**
422
>
* Render `history` as an interleaved-lane "git log" style graph. Each parent
423
>
* event gets a column; columns are laid out left-to-right in event order.
424
>
* Trace roots with at least one direct child become synthetic `+label` rows
425
>
* inserted before their first child.
426
>
*
427
>
* Glyphs:
428
>
* `╷` lane origin (this node is a parent)
429
>
* `│` lane passes through
430
>
* `├─` child connects; lane continues
431
>
* `└─` last child connects; lane closes
432
>
* `┼─` horizontal connector crosses an active lane
433
>
* `──` horizontal connector crosses an empty column
434
>
*/
435
>
export function renderLaneGraph(history: ExecutionHistory): string {
437
>
if (events.length === 0) { return ''; }
438
>
439
>
interface Node {
440
>
readonly label: string;
441
>
readonly parent: Node | undefined;
442
>
readonly isSynthetic: boolean;
443
>
}
444
>
445
>
// Insert synthetic root nodes before their first child.
446
>
const nodes: Node[] = [];
447
>
const syntheticForRoot = new Map<ExecutionRoot, Node>();
448
>
const nodeByEvent = new Map<ExecutionEvent, Node>();
449
>
450
>
// Which roots have at least one direct child event?
451
>
const rootsWithChildren = new Set<ExecutionRoot>();
452
>
for (const e of events) { if (!e.parent) { rootsWithChildren.add(e.root); } }
453
>
454
>
for (const e of events) {
455
>
if (rootsWithChildren.has(e.root) && !syntheticForRoot.has(e.root)) {
456
>
const syn: Node = { label: `+${e.root.label}`, parent: undefined, isSynthetic: true };
457
>
syntheticForRoot.set(e.root, syn);
458
>
nodes.push(syn);
459
>
}
460
>
const timeStr = `+${e.time}ms`.padStart(7);
461
>
const parent = e.parent ? nodeByEvent.get(e.parent)! : syntheticForRoot.get(e.root);
462
>
const node: Node = { label: `[${timeStr}] ${e.label}`, parent, isSynthetic: false };
463
>
nodeByEvent.set(e, node);
464
>
nodes.push(node);
465
>
}
466
>
467
>
const n = nodes.length;
468
>
const parentOf = new Array<number>(n).fill(-1);
469
>
const childrenOf: number[][] = Array.from({ length: n }, () => []);
470
>
const indexOfNode = new Map<Node, number>();
471
>
for (let i = 0; i < n; i++) { indexOfNode.set(nodes[i], i); }
472
>
for (let i = 0; i < n; i++) {
473
>
const p = nodes[i].parent;
474
>
if (p) {
475
>
const pi = indexOfNode.get(p);
476
>
if (pi !== undefined) { parentOf[i] = pi; childrenOf[pi].push(i); }
477
>
}
478
>
}
479
>
480
>
// Assign columns: every node with children gets its own column.
481
>
const colOf = new Array<number>(n).fill(-1);
482
>
let totalCols = 0;
483
>
for (let i = 0; i < n; i++) {
484
>
if (childrenOf[i].length > 0) { colOf[i] = totalCols++; }
485
>
}
486
>
487
>
if (totalCols === 0) {
488
return events.map(e => `[+${`${e.time}ms`.padStart(5)}] ${e.label}`).join('\n');
489
}
491
>
const active = new Array<number>(totalCols).fill(-1);
492
>
const lines: string[] = [];
493
>
494
>
for (let i = 0; i < n; i++) {
495
>
const node = nodes[i];
496
>
const pIdx = parentOf[i];
497
>
const connectCol = pIdx >= 0 ? colOf[pIdx] : -1;
498
>
const last = pIdx >= 0 && childrenOf[pIdx][childrenOf[pIdx].length - 1] === i;
499
>
const opensCol = childrenOf[i].length > 0 ? colOf[i] : -1;
500
>
const horizEnd = pIdx >= 0 ? (opensCol >= 0 ? opensCol : totalCols) : -1;
501
>
502
>
const chars: string[] = [];
503
>
for (let c = 0; c < totalCols; c++) {
504
>
const isActive = active[c] >= 0;
505
>
const isConnect = c === connectCol;
506
>
const isOpen = c === opensCol && !isConnect;
507
>
const inHoriz = connectCol >= 0 && c > connectCol && c < horizEnd;
508
>
509
>
let g: string, s: string;
510
>
if (isConnect) {
511
>
g = last ? '└' : '├';
512
>
s = '─';
513
>
} else if (isOpen && node.isSynthetic) {
514
>
g = '+';
515
>
s = node.label.slice(1, 2) || '?';
516
>
} else if (isOpen && connectCol >= 0) {
517
>
g = '╷'; s = '─';
518
>
} else if (isOpen) {
519
g = '╷'; s = ' ';
527
>
g = ' '; s = ' ';
528
>
}
529
>
chars.push(g, s);
530
>
}
531
>
532
>
if (last) { active[colOf[pIdx]] = -1; }
533
>
if (opensCol >= 0) { active[opensCol] = i; }
534
>
535
>
if (node.isSynthetic) {
536
>
lines.push(chars.join('').trimEnd());
537
>
} else {
538
>
lines.push(`${chars.join('')}${node.label}`);
539
>
}
540
>
}
541
>
542
>
return lines.join('\n');
543
>
}