All files / src/compiler/phases/2-analyze/utils check_graph_for_cycles.js

100% Statements 46/46
100% Branches 12/12
100% Functions 2/2
100% Lines 46/46

Press n or j to go to the next uncovered block, b, p or k for the previous block.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 472x 2x 2x 2x 2x 2x 4055x 4055x 402x 402x 402x 402x 402x 4055x 4055x 4055x 4055x 4055x 4055x 4055x 4055x 4055x 4055x 4055x 594x 594x 594x 594x 402x 305x 399x 2x 2x 594x 594x 594x 594x 4055x 4055x 594x 289x 289x 4055x 4055x 4055x 4055x  
/**
 * @template T
 * @param {Array<[T, T]>} edges
 * @returns {Array<T>|undefined}
 */
export default function check_graph_for_cycles(edges) {
	/** @type {Map<T, T[]>} */
	const graph = edges.reduce((g, edge) => {
		const [u, v] = edge;
		if (!g.has(u)) g.set(u, []);
		if (!g.has(v)) g.set(v, []);
		g.get(u).push(v);
		return g;
	}, new Map());
 
	const visited = new Set();
	const on_stack = new Set();
	/** @type {Array<Array<T>>} */
	const cycles = [];
 
	/**
	 * @param {T} v
	 */
	function visit(v) {
		visited.add(v);
		on_stack.add(v);
 
		graph.get(v)?.forEach((w) => {
			if (!visited.has(w)) {
				visit(w);
			} else if (on_stack.has(w)) {
				cycles.push([...on_stack, w]);
			}
		});
 
		on_stack.delete(v);
	}
 
	graph.forEach((_, v) => {
		if (!visited.has(v)) {
			visit(v);
		}
	});
 
	return cycles[0];
}