repos/tabletprog: cbackend.js comparison

comparison 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

comparison

equal deleted inserted replaced

-:c1fad3d93861
+:eef8a5cea812
 	return this.ast.toCModuleInstance();
 };
 function processUsedToplevel(toplevel)
 {
-	var alwaysused = ['list', 'true', 'false'];
+	var alwaysused = ['true', 'false', 'list'];
 	var ret = '';
 	var modulenum = 0;
 	var visited = {};
-	var newused = [];
+	var newused = alwaysused;//Object.keys(toplevel.used);
-	for (var i in alwaysused) {
-		delete toplevel.used[alwaysused[i]];
-		visited[alwaysused[i]] = true;
-	}
-	var addedAlways = false;
-	var newused = 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');
 			forwarddec += 'object * ' + toplevel.moduleVar(newused[i]) + ';\n';
 			toplevel.names[newused[i]].populateSymbols(toplevel);
 				debugprint('//found new usage of module', symbol);
 				newused.push(symbol);
 				allused.push(symbol);
 			}
 		}
-		if (!newused.length && !addedAlways) {
+	}
-			addedAlways = true;
+	var compiled = {};
-			for (var i in alwaysused) {
+	//true and false depend on each other, but not at module init time
-				toplevel.used[alwaysused[i]] = true;
+	//force them to have no dependencies
-				newused.push(alwaysused[i]);
+	toplevel.names['true'].dependencies = {};
-				allused.push(alwaysused[i]);
+	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 = {};
-	for (var i = allused.length-1; i >= 0; i--) {
+	while (allused.length) {
-		var symbol = allused[i];
+		var nextused = [];
-		debugprint('//---module', symbol, '(' + i +')--- compile');
+		var minUnmet = allused.length;
-		assignNames.push(symbol);
+		var minUnmetIdx = -1;
-		ret += '\t' + toplevel.moduleVar(symbol) + ' = ' + toplevel.names[symbol].toC() + ';\n';
+		for (var i = 0; i < allused.length; i++) {
-		assignNames.pop();
+			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;
+			}
+		}
+		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;
 }
 function makeCProg(obj)