516 lines
18 KiB
TypeScript
516 lines
18 KiB
TypeScript
/// <reference lib="es2019" />
|
|
|
|
/* @internal */
|
|
namespace Debug {
|
|
interface Node {
|
|
kind: number;
|
|
}
|
|
|
|
type FunctionExpression = Node;
|
|
type ArrowFunction = Node;
|
|
type MethodDeclaration = Node;
|
|
type Expression = Node;
|
|
type SourceFile = Node;
|
|
type VariableDeclaration = Node;
|
|
type BindingElement = Node;
|
|
type CallExpression = Node;
|
|
type BinaryExpression = Node;
|
|
|
|
interface SwitchStatement extends Node {
|
|
caseBlock: CaseBlock;
|
|
}
|
|
|
|
interface CaseBlock extends Node {
|
|
clauses: (CaseClause | DefaultClause)[];
|
|
}
|
|
|
|
interface CaseClause extends Node {
|
|
_caseclauseBrand: any;
|
|
expression: Expression;
|
|
}
|
|
|
|
interface DefaultClause extends Node {
|
|
_defaultClauseBrand: any;
|
|
}
|
|
|
|
interface TypeScriptModule {
|
|
readonly SyntaxKind: {
|
|
readonly CaseClause: number;
|
|
readonly DefaultClause: number;
|
|
};
|
|
|
|
readonly FlowFlags: {
|
|
readonly Unreachable: number,
|
|
readonly Start: number,
|
|
readonly BranchLabel: number,
|
|
readonly LoopLabel: number,
|
|
readonly Assignment: number,
|
|
readonly TrueCondition: number,
|
|
readonly FalseCondition: number,
|
|
readonly SwitchClause: number,
|
|
readonly ArrayMutation: number,
|
|
readonly Call: number,
|
|
readonly ReduceLabel: number,
|
|
readonly Referenced: number,
|
|
readonly Shared: number,
|
|
readonly Label: number,
|
|
readonly Condition: number,
|
|
};
|
|
|
|
getSourceFileOfNode(node: Node): SourceFile;
|
|
getSourceTextOfNodeFromSourceFile(sourceFile: SourceFile, node: Node, includeTrivia?: boolean): string;
|
|
isDefaultClause(node: Node): node is DefaultClause;
|
|
}
|
|
|
|
type FlowNode =
|
|
| FlowStart
|
|
| FlowLabel
|
|
| FlowAssignment
|
|
| FlowCall
|
|
| FlowCondition
|
|
| FlowSwitchClause
|
|
| FlowArrayMutation
|
|
| FlowReduceLabel
|
|
;
|
|
|
|
interface FlowNodeBase {
|
|
flags: FlowFlags;
|
|
id?: number;
|
|
}
|
|
|
|
interface FlowStart extends FlowNodeBase {
|
|
node?: FunctionExpression | ArrowFunction | MethodDeclaration;
|
|
}
|
|
|
|
interface FlowLabel extends FlowNodeBase {
|
|
antecedents: FlowNode[] | undefined;
|
|
}
|
|
|
|
interface FlowAssignment extends FlowNodeBase {
|
|
node: Expression | VariableDeclaration | BindingElement;
|
|
antecedent: FlowNode;
|
|
}
|
|
|
|
interface FlowCall extends FlowNodeBase {
|
|
node: CallExpression;
|
|
antecedent: FlowNode;
|
|
}
|
|
|
|
interface FlowCondition extends FlowNodeBase {
|
|
node: Expression;
|
|
antecedent: FlowNode;
|
|
}
|
|
|
|
interface FlowSwitchClause extends FlowNodeBase {
|
|
switchStatement: SwitchStatement;
|
|
clauseStart: number;
|
|
clauseEnd: number;
|
|
antecedent: FlowNode;
|
|
}
|
|
|
|
interface FlowArrayMutation extends FlowNodeBase {
|
|
node: CallExpression | BinaryExpression;
|
|
antecedent: FlowNode;
|
|
}
|
|
|
|
export interface FlowReduceLabel extends FlowNodeBase {
|
|
target: FlowLabel;
|
|
antecedents: FlowNode[];
|
|
antecedent: FlowNode;
|
|
}
|
|
|
|
type FlowFlags = number;
|
|
let FlowFlags: TypeScriptModule["FlowFlags"];
|
|
let getSourceFileOfNode: TypeScriptModule["getSourceFileOfNode"];
|
|
let getSourceTextOfNodeFromSourceFile: TypeScriptModule["getSourceTextOfNodeFromSourceFile"];
|
|
let isDefaultClause: TypeScriptModule["isDefaultClause"];
|
|
|
|
export function init(ts: TypeScriptModule) {
|
|
FlowFlags = ts.FlowFlags;
|
|
getSourceFileOfNode = ts.getSourceFileOfNode;
|
|
getSourceTextOfNodeFromSourceFile = ts.getSourceTextOfNodeFromSourceFile;
|
|
isDefaultClause = ts.isDefaultClause;
|
|
}
|
|
|
|
let nextDebugFlowId = -1;
|
|
|
|
function getDebugFlowNodeId(f: FlowNode) {
|
|
if (!f.id) {
|
|
f.id = nextDebugFlowId;
|
|
nextDebugFlowId--;
|
|
}
|
|
return f.id;
|
|
}
|
|
|
|
export function formatControlFlowGraph(flowNode: FlowNode) {
|
|
const enum BoxCharacter {
|
|
lr = "─",
|
|
ud = "│",
|
|
dr = "╭",
|
|
dl = "╮",
|
|
ul = "╯",
|
|
ur = "╰",
|
|
udr = "├",
|
|
udl = "┤",
|
|
dlr = "┬",
|
|
ulr = "┴",
|
|
udlr = "╫",
|
|
}
|
|
|
|
const enum Connection {
|
|
Up = 1 << 0,
|
|
Down = 1 << 1,
|
|
Left = 1 << 2,
|
|
Right = 1 << 3,
|
|
|
|
UpDown = Up | Down,
|
|
LeftRight = Left | Right,
|
|
UpLeft = Up | Left,
|
|
UpRight = Up | Right,
|
|
DownLeft = Down | Left,
|
|
DownRight = Down | Right,
|
|
UpDownLeft = UpDown | Left,
|
|
UpDownRight = UpDown | Right,
|
|
UpLeftRight = Up | LeftRight,
|
|
DownLeftRight = Down | LeftRight,
|
|
UpDownLeftRight = UpDown | LeftRight,
|
|
|
|
NoChildren = 1 << 4,
|
|
}
|
|
|
|
interface FlowGraphNode {
|
|
id: number;
|
|
flowNode: FlowNode;
|
|
edges: FlowGraphEdge[];
|
|
text: string;
|
|
lane: number;
|
|
endLane: number;
|
|
level: number;
|
|
circular: boolean | "circularity";
|
|
}
|
|
|
|
interface FlowGraphEdge {
|
|
source: FlowGraphNode;
|
|
target: FlowGraphNode;
|
|
}
|
|
|
|
const hasAntecedentFlags =
|
|
FlowFlags.Assignment |
|
|
FlowFlags.Condition |
|
|
FlowFlags.SwitchClause |
|
|
FlowFlags.ArrayMutation |
|
|
FlowFlags.Call |
|
|
FlowFlags.ReduceLabel;
|
|
|
|
const hasNodeFlags =
|
|
FlowFlags.Start |
|
|
FlowFlags.Assignment |
|
|
FlowFlags.Call |
|
|
FlowFlags.Condition |
|
|
FlowFlags.ArrayMutation;
|
|
|
|
const links: Record<number, FlowGraphNode> = Object.create(/*o*/ null); // eslint-disable-line no-null/no-null
|
|
const nodes: FlowGraphNode[] = [];
|
|
const edges: FlowGraphEdge[] = [];
|
|
const root = buildGraphNode(flowNode, new Set());
|
|
for (const node of nodes) {
|
|
node.text = renderFlowNode(node.flowNode, node.circular);
|
|
computeLevel(node);
|
|
}
|
|
|
|
const height = computeHeight(root);
|
|
const columnWidths = computeColumnWidths(height);
|
|
computeLanes(root, 0);
|
|
return renderGraph();
|
|
|
|
function isFlowSwitchClause(f: FlowNode): f is FlowSwitchClause {
|
|
return !!(f.flags & FlowFlags.SwitchClause);
|
|
}
|
|
|
|
function hasAntecedents(f: FlowNode): f is FlowLabel & { antecedents: FlowNode[] } {
|
|
return !!(f.flags & FlowFlags.Label) && !!(f as FlowLabel).antecedents;
|
|
}
|
|
|
|
function hasAntecedent(f: FlowNode): f is Extract<FlowNode, { antecedent: FlowNode }> {
|
|
return !!(f.flags & hasAntecedentFlags);
|
|
}
|
|
|
|
function hasNode(f: FlowNode): f is Extract<FlowNode, { node?: Node }> {
|
|
return !!(f.flags & hasNodeFlags);
|
|
}
|
|
|
|
function getChildren(node: FlowGraphNode) {
|
|
const children: FlowGraphNode[] = [];
|
|
for (const edge of node.edges) {
|
|
if (edge.source === node) {
|
|
children.push(edge.target);
|
|
}
|
|
}
|
|
return children;
|
|
}
|
|
|
|
function getParents(node: FlowGraphNode) {
|
|
const parents: FlowGraphNode[] = [];
|
|
for (const edge of node.edges) {
|
|
if (edge.target === node) {
|
|
parents.push(edge.source);
|
|
}
|
|
}
|
|
return parents;
|
|
}
|
|
|
|
function buildGraphNode(flowNode: FlowNode, seen: Set<FlowNode>): FlowGraphNode {
|
|
const id = getDebugFlowNodeId(flowNode);
|
|
let graphNode = links[id];
|
|
if (graphNode && seen.has(flowNode)) {
|
|
graphNode.circular = true;
|
|
graphNode = {
|
|
id: -1,
|
|
flowNode,
|
|
edges: [],
|
|
text: "",
|
|
lane: -1,
|
|
endLane: -1,
|
|
level: -1,
|
|
circular: "circularity"
|
|
};
|
|
nodes.push(graphNode);
|
|
return graphNode;
|
|
}
|
|
seen.add(flowNode);
|
|
if (!graphNode) {
|
|
links[id] = graphNode = { id, flowNode, edges: [], text: "", lane: -1, endLane: -1, level: -1, circular: false };
|
|
nodes.push(graphNode);
|
|
if (hasAntecedents(flowNode)) {
|
|
for (const antecedent of flowNode.antecedents) {
|
|
buildGraphEdge(graphNode, antecedent, seen);
|
|
}
|
|
}
|
|
else if (hasAntecedent(flowNode)) {
|
|
buildGraphEdge(graphNode, flowNode.antecedent, seen);
|
|
}
|
|
}
|
|
seen.delete(flowNode);
|
|
return graphNode;
|
|
}
|
|
|
|
function buildGraphEdge(source: FlowGraphNode, antecedent: FlowNode, seen: Set<FlowNode>) {
|
|
const target = buildGraphNode(antecedent, seen);
|
|
const edge: FlowGraphEdge = { source, target };
|
|
edges.push(edge);
|
|
source.edges.push(edge);
|
|
target.edges.push(edge);
|
|
}
|
|
|
|
function computeLevel(node: FlowGraphNode): number {
|
|
if (node.level !== -1) {
|
|
return node.level;
|
|
}
|
|
let level = 0;
|
|
for (const parent of getParents(node)) {
|
|
level = Math.max(level, computeLevel(parent) + 1);
|
|
}
|
|
return node.level = level;
|
|
}
|
|
|
|
function computeHeight(node: FlowGraphNode): number {
|
|
let height = 0;
|
|
for (const child of getChildren(node)) {
|
|
height = Math.max(height, computeHeight(child));
|
|
}
|
|
return height + 1;
|
|
}
|
|
|
|
function computeColumnWidths(height: number) {
|
|
const columns: number[] = fill(Array(height), 0);
|
|
for (const node of nodes) {
|
|
columns[node.level] = Math.max(columns[node.level], node.text.length);
|
|
}
|
|
return columns;
|
|
}
|
|
|
|
function computeLanes(node: FlowGraphNode, lane: number) {
|
|
if (node.lane === -1) {
|
|
node.lane = lane;
|
|
node.endLane = lane;
|
|
const children = getChildren(node);
|
|
for (let i = 0; i < children.length; i++) {
|
|
if (i > 0) lane++;
|
|
const child = children[i];
|
|
computeLanes(child, lane);
|
|
if (child.endLane > node.endLane) {
|
|
lane = child.endLane;
|
|
}
|
|
}
|
|
node.endLane = lane;
|
|
}
|
|
}
|
|
|
|
function getHeader(flags: FlowFlags) {
|
|
if (flags & FlowFlags.Start) return "Start";
|
|
if (flags & FlowFlags.BranchLabel) return "Branch";
|
|
if (flags & FlowFlags.LoopLabel) return "Loop";
|
|
if (flags & FlowFlags.Assignment) return "Assignment";
|
|
if (flags & FlowFlags.TrueCondition) return "True";
|
|
if (flags & FlowFlags.FalseCondition) return "False";
|
|
if (flags & FlowFlags.SwitchClause) return "SwitchClause";
|
|
if (flags & FlowFlags.ArrayMutation) return "ArrayMutation";
|
|
if (flags & FlowFlags.Call) return "Call";
|
|
if (flags & FlowFlags.ReduceLabel) return "ReduceLabel";
|
|
if (flags & FlowFlags.Unreachable) return "Unreachable";
|
|
throw new Error();
|
|
}
|
|
|
|
function getNodeText(node: Node) {
|
|
const sourceFile = getSourceFileOfNode(node);
|
|
return getSourceTextOfNodeFromSourceFile(sourceFile, node, /*includeTrivia*/ false);
|
|
}
|
|
|
|
function renderFlowNode(flowNode: FlowNode, circular: boolean | "circularity") {
|
|
let text = getHeader(flowNode.flags);
|
|
if (circular) {
|
|
text = `${text}#${getDebugFlowNodeId(flowNode)}`;
|
|
}
|
|
if (hasNode(flowNode)) {
|
|
if (flowNode.node) {
|
|
text += ` (${getNodeText(flowNode.node)})`;
|
|
}
|
|
}
|
|
else if (isFlowSwitchClause(flowNode)) {
|
|
const clauses: string[] = [];
|
|
for (let i = flowNode.clauseStart; i < flowNode.clauseEnd; i++) {
|
|
const clause = flowNode.switchStatement.caseBlock.clauses[i];
|
|
if (isDefaultClause(clause)) {
|
|
clauses.push("default");
|
|
}
|
|
else {
|
|
clauses.push(getNodeText(clause.expression));
|
|
}
|
|
}
|
|
text += ` (${clauses.join(", ")})`;
|
|
}
|
|
return circular === "circularity" ? `Circular(${text})` : text;
|
|
}
|
|
|
|
function renderGraph() {
|
|
const columnCount = columnWidths.length;
|
|
const laneCount = nodes.reduce((x, n) => Math.max(x, n.lane), 0) + 1;
|
|
const lanes: string[] = fill(Array(laneCount), "");
|
|
const grid: (FlowGraphNode | undefined)[][] = columnWidths.map(() => Array(laneCount));
|
|
const connectors: Connection[][] = columnWidths.map(() => fill(Array(laneCount), 0));
|
|
|
|
// build connectors
|
|
for (const node of nodes) {
|
|
grid[node.level][node.lane] = node;
|
|
const children = getChildren(node);
|
|
for (let i = 0; i < children.length; i++) {
|
|
const child = children[i];
|
|
let connector: Connection = Connection.Right;
|
|
if (child.lane === node.lane) connector |= Connection.Left;
|
|
if (i > 0) connector |= Connection.Up;
|
|
if (i < children.length - 1) connector |= Connection.Down;
|
|
connectors[node.level][child.lane] |= connector;
|
|
}
|
|
if (children.length === 0) {
|
|
connectors[node.level][node.lane] |= Connection.NoChildren;
|
|
}
|
|
const parents = getParents(node);
|
|
for (let i = 0; i < parents.length; i++) {
|
|
const parent = parents[i];
|
|
let connector: Connection = Connection.Left;
|
|
if (i > 0) connector |= Connection.Up;
|
|
if (i < parents.length - 1) connector |= Connection.Down;
|
|
connectors[node.level - 1][parent.lane] |= connector;
|
|
}
|
|
}
|
|
|
|
// fill in missing connectors
|
|
for (let column = 0; column < columnCount; column++) {
|
|
for (let lane = 0; lane < laneCount; lane++) {
|
|
const left = column > 0 ? connectors[column - 1][lane] : 0;
|
|
const above = lane > 0 ? connectors[column][lane - 1] : 0;
|
|
let connector = connectors[column][lane];
|
|
if (!connector) {
|
|
if (left & Connection.Right) connector |= Connection.LeftRight;
|
|
if (above & Connection.Down) connector |= Connection.UpDown;
|
|
connectors[column][lane] = connector;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (let column = 0; column < columnCount; column++) {
|
|
for (let lane = 0; lane < lanes.length; lane++) {
|
|
const connector = connectors[column][lane];
|
|
const fill = connector & Connection.Left ? BoxCharacter.lr : " ";
|
|
const node = grid[column][lane];
|
|
if (!node) {
|
|
if (column < columnCount - 1) {
|
|
writeLane(lane, repeat(fill, columnWidths[column] + 1));
|
|
}
|
|
}
|
|
else {
|
|
writeLane(lane, node.text);
|
|
if (column < columnCount - 1) {
|
|
writeLane(lane, " ");
|
|
writeLane(lane, repeat(fill, columnWidths[column] - node.text.length));
|
|
}
|
|
}
|
|
writeLane(lane, getBoxCharacter(connector));
|
|
writeLane(lane, connector & Connection.Right && column < columnCount - 1 && !grid[column + 1][lane] ? BoxCharacter.lr : " ");
|
|
}
|
|
}
|
|
|
|
return `\n${lanes.join("\n")}\n`;
|
|
|
|
function writeLane(lane: number, text: string) {
|
|
lanes[lane] += text;
|
|
}
|
|
}
|
|
|
|
function getBoxCharacter(connector: Connection) {
|
|
switch (connector) {
|
|
case Connection.UpDown: return BoxCharacter.ud;
|
|
case Connection.LeftRight: return BoxCharacter.lr;
|
|
case Connection.UpLeft: return BoxCharacter.ul;
|
|
case Connection.UpRight: return BoxCharacter.ur;
|
|
case Connection.DownLeft: return BoxCharacter.dl;
|
|
case Connection.DownRight: return BoxCharacter.dr;
|
|
case Connection.UpDownLeft: return BoxCharacter.udl;
|
|
case Connection.UpDownRight: return BoxCharacter.udr;
|
|
case Connection.UpLeftRight: return BoxCharacter.ulr;
|
|
case Connection.DownLeftRight: return BoxCharacter.dlr;
|
|
case Connection.UpDownLeftRight: return BoxCharacter.udlr;
|
|
}
|
|
return " ";
|
|
}
|
|
|
|
function fill<T>(array: T[], value: T) {
|
|
if (array.fill) {
|
|
array.fill(value);
|
|
}
|
|
else {
|
|
for (let i = 0; i < array.length; i++) {
|
|
array[i] = value;
|
|
}
|
|
}
|
|
return array;
|
|
}
|
|
|
|
function repeat(ch: string, length: number) {
|
|
if (ch.repeat) {
|
|
return length > 0 ? ch.repeat(length) : "";
|
|
}
|
|
let s = "";
|
|
while (s.length < length) {
|
|
s += ch;
|
|
}
|
|
return s;
|
|
}
|
|
}
|
|
|
|
// Export as a module. NOTE: Can't use module exports as this is built using --outFile
|
|
declare const module: { exports: {} };
|
|
if (typeof module !== "undefined" && module.exports) {
|
|
module.exports = Debug;
|
|
}
|
|
} |