diff cbackend.js @ 329:eef8a5cea812

Use a smarter algorithm for calculating module init order and break some circular module dependencies in the standard library
author Michael Pavone <pavone@retrodev.com>
date Sat, 28 Mar 2015 13:26:03 -0700
parents 4a79311dbd29
children 61f5b794d939
line wrap: on
line diff
--- a/cbackend.js	Wed Mar 25 00:16:37 2015 -0700
+++ b/cbackend.js	Sat Mar 28 13:26:03 2015 -0700
@@ -1008,18 +1008,13 @@
 
 function processUsedToplevel(toplevel)
 {
-	var alwaysused = ['list', 'true', 'false'];
+	var alwaysused = ['true', 'false', 'list'];
 	var ret = '';
 	var modulenum = 0;
 	var visited = {};
-	var newused = [];
-	for (var i in alwaysused) {
-		delete toplevel.used[alwaysused[i]];
-		visited[alwaysused[i]] = true;
-	}
-	var addedAlways = false;
-	var newused = Object.keys(toplevel.used);
+	var newused = alwaysused;//Object.keys(toplevel.used);
 	var allused = newused;
+	print('//newused = ' + newused.join(', '));
 	while (newused.length) {
 		for (var i in newused) {
 			debugprint('//---module', newused[i], '--- populate symbols');
@@ -1035,22 +1030,57 @@
 				allused.push(symbol);
 			}
 		}
-		if (!newused.length && !addedAlways) {
-			addedAlways = true;
-			for (var i in alwaysused) {
-				toplevel.used[alwaysused[i]] = true;
-				newused.push(alwaysused[i]);
-				allused.push(alwaysused[i]);
+	}
+	var compiled = {};
+	//true and false depend on each other, but not at module init time
+	//force them to have no dependencies
+	toplevel.names['true'].dependencies = {};
+	toplevel.names['false'].dependencies = {};
+	//string and object can be a problem as well and is safe to init them before other things
+	toplevel.names['string'].dependencies = {};
+	toplevel.names['object'].dependencies = {};
+
+	while (allused.length) {
+		var nextused = [];
+		var minUnmet = allused.length;
+		var minUnmetIdx = -1;
+		for (var i = 0; i < allused.length; i++) {
+			var symbol = allused[i];
+			var module = toplevel.names[symbol];
+			var unmet = 0;
+			for (var dependency in module.dependencies) {
+				if (!(dependency in compiled) && dependency != symbol) {
+					unmet++;
+				}
+			}
+			if (unmet) {
+				nextused.push(symbol);
+				if (unmet < minUnmet) {
+					minUnmet = unmet;
+					minUnmetIdx = i;
+				}
+			} else {
+				debugprint('//---module', symbol, '(' + i +')--- compile');
+				debugprint('//    dependencies: ' + Object.keys(toplevel.names[symbol].dependencies).join(', '));
+				assignNames.push(symbol);
+				ret += '\t' + toplevel.moduleVar(symbol) + ' = ' + toplevel.names[symbol].toC() + ';\n';
+				assignNames.pop();
+				compiled[symbol] = true;
 			}
 		}
-	}
-
-	for (var i = allused.length-1; i >= 0; i--) {
-		var symbol = allused[i];
-		debugprint('//---module', symbol, '(' + i +')--- compile');
-		assignNames.push(symbol);
-		ret += '\t' + toplevel.moduleVar(symbol) + ' = ' + toplevel.names[symbol].toC() + ';\n';
-		assignNames.pop();
+		if (nextused.length == allused.length) {
+			var symbol = nextused[minUnmetIdx];
+			print('//WARNING: circular module dependency detected, compiling ' + symbol + ' with dependencies ' + Object.keys(toplevel.names[symbol].dependencies).join(', '));
+			print('//         but only these dependencies are met: ' + Object.keys(compiled).join(', '));
+			debugprint('//---module', symbol, '(' + i +')--- compile');
+			assignNames.push(symbol);
+			ret += '\t' + toplevel.moduleVar(symbol) + ' = ' + toplevel.names[symbol].toC() + ';\n';
+			assignNames.pop();
+			compiled[symbol] = true;
+			nextused[minUnmetIdx] = nextused[nextused.length-1];
+			nextused.pop();
+		}
+		allused = nextused;
 	}
 	return ret;
 }