icssify/src/sort-dependencies.js

"use strict";

const kahn = require("./kahn");
const CycleError = require("./cycle-error");
const findCycleSets = require("./find-cycle-sets");

function printNodes(nodes) {
	return nodes
		.map((node) => node.id)
		.map((id) => ` - ${id}`)
		.join("\n");
}

function mergeRemovedEdges(a, b) {
	let newObject = {};

	function addEdges(key, values) {
		if (newObject[key] == null) {
			newObject[key] = values;
		} else {
			newObject[key] = newObject[key].concat(values);
		}
	}

	for (let [ key, value ] of Object.entries(a)) {
		addEdges(key, value);
	}

	for (let [ key, value ] of Object.entries(b)) {
		addEdges(key, value);
	}

	return newObject;
}

function findEdgesToRemove(affectedNodes) {
	let { cycleSets } = findCycleSets(affectedNodes);
	let edgesToRemove = {};

	function addEdge(key, value) {
		if (edgesToRemove[key] == null) {
			edgesToRemove[key] = [];
		}

		edgesToRemove[key].push(value);
	}

	for (let cycle of cycleSets) {
		let firstModule = cycle[0];
		let firstConflictingModule = cycle.find((module_) => firstModule.parents.includes(module_));

		addEdge(firstModule.id, firstConflictingModule.id);
	}

	return edgesToRemove;
}

function createDependencyCycleError(affectedNodes) {
	let { cycleSets, innocentNodes } = findCycleSets(affectedNodes);
			
	let cycleSetStrings = cycleSets.map((set) => printNodes(set));

	let innocentNodeString = (innocentNodes.length === 0)
		? " (none)"
		: printNodes(innocentNodes);

	let message = [
		`At least ${cycleSets.length} circular dependency chain(s) were detected, involving the following modules:`,
		"",
		cycleSetStrings.join("\n\n"),
		"",
		"Additionally, the following modules could not be processed as a result:",
		"",
		innocentNodeString,
		"",
		"Please read the icssify documentation for the 'ignoreCycles' option to understand how to deal with this."
	].join("\n");

	return new CycleError(message);
}

module.exports = function sortDependencies(items, removedEdges, options = {}) {
	let { ignoreCycles } = options;

	let dependencyMap = new Map();
	let nodeMap = new Map();
	
	// The below code 1) inverts child-specifying nodes to parent-specifying nodes, and 2) ensures that nodes reference in-memory objects rather than IDs, so they work with the implementation of Kahn's algorithm. TODO: This should probably be made nicer at some point...

	items.forEach((item) => {
		dependencyMap.set(item.id, item);
		nodeMap.set(item.id, { id: item.id, children: [] });
	});

	items.forEach((item) => {
		let removedEdgesForItem = new Set(removedEdges[item.id]);

		Object.values(item.deps)
			.filter((dep => dep !== item.id))
			.forEach((dep) => {
				let parent = nodeMap.get(dep);

				if (removedEdgesForItem == null || !removedEdgesForItem.has(parent.id)) {
					parent.children.push(nodeMap.get(item.id));
				}
			});

		nodeMap.get(item.id).parents = Object.values(item.deps)
			.filter((id => id !== item.id))
			.map((id) => nodeMap.get(id))
			.filter((node) => !removedEdgesForItem.has(node.id));
	});
	
	try {
		let sortedNodes = kahn(Array.from(nodeMap.values()));

		return sortedNodes.map((node) => {
			return dependencyMap.get(node.id);
		});
	} catch (error) {
		if (error instanceof CycleError) {
			if (ignoreCycles) {
				// TODO: Disallow cycles for extensions processed by icssify, *even* when this option is active, because cycles just aren't (sensibly) possible in ICSS
				let newRemovedEdges = findEdgesToRemove(error.affectedNodes);

				// TODO: Debug-log removed edges here, and the full cycle, to debug potential future infinite recursion bugs

				// We will keep throwing out more (deterministically) random edges until we're left with no cycles. If there are enough cycles to cause an exceeded stack size here, you probably have bigger issues to worry about...
				return sortDependencies(items, mergeRemovedEdges(removedEdges, newRemovedEdges), options);
			} else {
				throw createDependencyCycleError(error.affectedNodes);
			}
		} else {
			throw error;
		}
	}
};