モジュール間の依存関係を解決してみる実験

dependencyResolution.ts

/*
 * MIT License
 * (c) 2019 marihachi.
*/

interface Edge {
	src: number;
	dest: number;
}

interface GraphNode {
	incomingCount: number;
	outgoingNodes: number[];
}

class Graph {
	nodes: GraphNode[];

	constructor(nodeCount: number, edges: Edge[]) {
		this.nodes = [];
		for (let i = 0; i < nodeCount; i++) {
			const node: GraphNode = {
				incomingCount: 0,
				outgoingNodes: []
			};
			this.nodes.push(node);
		}
		for (const edge of edges) {
			this.nodes[edge.src].outgoingNodes.push(edge.dest);
			this.nodes[edge.dest].incomingCount++;
		}
	}

	/**
	 * apply kahn's topological sort
	 * @returns the indexes of the sorted nodes
	*/
	sort(): number[] {
		const L: number[] = [];
		const S: number[] = [];

		for (let i = 0; i < this.nodes.length; i++) {
			if (this.nodes[i].incomingCount == 0) {
				S.push(i);
			}
		}

		while (S.length > 0) {
			const n = S[0];
			S.splice(0, 1);
			L.push(n);

			for (const m of this.nodes[n].outgoingNodes) {
				this.nodes[m].incomingCount--;
				if (this.nodes[m].incomingCount == 0) {
					S.push(m);
				}
			}
		}

		if (this.nodes.some(node => node.incomingCount != 0)) {
			throw new Error('failed to sort');
		}

		return L;
	}
}

interface DepModule {
	name: string;
	dependencies: string[];
}

function resolveDependency(modules: DepModule[]): DepModule[] {
	const nameResolutionTable: {[x: string]: number} = { };
	for (let i = 0; i < modules.length; i++) {
		nameResolutionTable[modules[i].name] = i;
	}

	const edges: Edge[] = [];
	for (let mi = 0; mi < modules.length; mi++) {
		for (const dependency of modules[mi].dependencies) {
			const moduleIndex = nameResolutionTable[dependency];
			if (moduleIndex == undefined) {
				throw new Error('unknown module name');
			}
			edges.push({ src: mi, dest: moduleIndex });
		}
	}

	const graph = new Graph(modules.length, edges);

	const indexes = graph.sort().reverse();

	return indexes.map(i => modules[i]);
}

function dependencyResolution() {
	const moduleA: DepModule = {
		name: 'module-a',
		dependencies: []
	};

	const moduleB: DepModule = {
		name: 'module-b',
		dependencies: ['module-a']
	};

	const moduleC: DepModule = {
		name: 'module-c',
		dependencies: ['module-a', 'module-b']
	};

	const moduleD: DepModule = {
		name: 'module-d',
		dependencies: ['module-b', 'module-c']
	};

	try {
		let modules: DepModule[] = [moduleB, moduleD, moduleA, moduleC];
		console.log('modules:', modules);
		console.log('sorting...');
		const result = resolveDependency(modules);
		console.log('result:', result);
	}
	catch (err) {
		console.log('error:', err.message);
	}
}
dependencyResolution();