# HG changeset patch
# User Michael Pavone <pavone@retrodev.com>
# Date 1427574363 25200
# Node ID eef8a5cea8121d086cebf43310c6efd559cae8df
# Parent  c1fad3d9386193b472fb9e116b078d363a464a85
Use a smarter algorithm for calculating module init order and break some circular module dependencies in the standard library

diff -r c1fad3d93861 -r eef8a5cea812 cbackend.js
--- 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;
 }
diff -r c1fad3d93861 -r eef8a5cea812 compiler.js
--- a/compiler.js	Wed Mar 25 00:16:37 2015 -0700
+++ b/compiler.js	Sat Mar 28 13:26:03 2015 -0700
@@ -5,16 +5,20 @@
 	return str.split('\n').join('\n\t');
 }
 
+var currentModule = null;
 function modulefile(path, file)
 {
 	this.path = path;
 	this.file = file;
+	this.dependencies = {};
 }
 
 modulefile.prototype.populateSymbols = function (toplevel) {
 	if (!this.ast) {
+		currentModule = this;
 		this.ast = parseFile(this.path + '/' + this.file).macroexpand(toplevel.topenv);
 		this.ast.populateSymbols(toplevel);
+		currentModule = null;
 	}
 };
 
@@ -23,8 +27,10 @@
 		var self = this;
 		get(this.path + '/' + this.file, function(data) {
       //TODO: macro expand in the async case
+			currentModule = this;
 			self.ast = parser.parse(data.responseText);
 			self.ast.populateSymbols(toplevel);
+			currentModule = null;
 			whenDone();
 		});
 	} else {
@@ -93,6 +99,9 @@
 		throw new Error('data not ready');
 	}
 	if (name in this.names) {
+		if (currentModule) {
+			currentModule.dependencies[name] = true;
+		}
 		this.used[name] = true;
 		return {
 			type: 'toplevel',
diff -r c1fad3d93861 -r eef8a5cea812 modules/array.tp
--- a/modules/array.tp	Wed Mar 25 00:16:37 2015 -0700
+++ b/modules/array.tp	Sat Mar 28 13:26:03 2015 -0700
@@ -207,7 +207,7 @@
 	}
 
 	jsonEncode <- {
-		parts <- map: :el { json encode: el }
+		parts <- map: :el { jsonEncoder encode: el }
 		"[" . (parts join: ",") . "]"
 	}
 }
diff -r c1fad3d93861 -r eef8a5cea812 modules/dict.tp
--- a/modules/dict.tp	Wed Mar 25 00:16:37 2015 -0700
+++ b/modules/dict.tp	Sat Mar 28 13:26:03 2015 -0700
@@ -3,7 +3,7 @@
 		parts <- #[]
 		foreach: dict :key val {
 			//TODO: escape field names
-			parts append: (key jsonEncode) . ":" . (json encode: val)
+			parts append: (key jsonEncode) . ":" . (jsonEncoder encode: val)
 		}
 		"{" . (parts join: ",") . "}"
 	}
diff -r c1fad3d93861 -r eef8a5cea812 modules/json.tp
--- a/modules/json.tp	Wed Mar 25 00:16:37 2015 -0700
+++ b/modules/json.tp	Sat Mar 28 13:26:03 2015 -0700
@@ -165,22 +165,7 @@
 		}
 
 		encode <- :value {
-			if: (object does: value understand?: "jsonEncode") {
-				value jsonEncode
-			} else: {
-				toEncode <- #[]
-				if: (object does: value understand?: "serializeFields") {
-					toEncode <- value serializeFields
-				} else: {
-					toEncode <- object propertiesOf: value
-				}
-				parts <- #[]
-				foreach: toEncode :idx field {
-					fieldVal <- object sendMessage: field to: value
-					parts append: (field jsonEncode) . ":" . (encode: fieldVal)
-				}
-				"{" . (parts join: ",") . "}"
-			}
+			jsonEncoder encode: value
 		}
 
 		main <- {
diff -r c1fad3d93861 -r eef8a5cea812 modules/jsonEncoder.tp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/modules/jsonEncoder.tp	Sat Mar 28 13:26:03 2015 -0700
@@ -0,0 +1,22 @@
+#{
+	//this module exists to break a circular dependency between the json module
+	//and container types like dictionaries
+	encode <- :value {
+		if: (object does: value understand?: "jsonEncode") {
+			value jsonEncode
+		} else: {
+			toEncode <- #[]
+			if: (object does: value understand?: "serializeFields") {
+				toEncode <- value serializeFields
+			} else: {
+				toEncode <- object propertiesOf: value
+			}
+			parts <- #[]
+			foreach: toEncode :idx field {
+				fieldVal <- object sendMessage: field to: value
+				parts append: (field jsonEncode) . ":" . (encode: fieldVal)
+			}
+			"{" . (parts join: ",") . "}"
+		}
+	}
+}
\ No newline at end of file
diff -r c1fad3d93861 -r eef8a5cea812 modules/list.tp
--- a/modules/list.tp	Wed Mar 25 00:16:37 2015 -0700
+++ b/modules/list.tp	Sat Mar 28 13:26:03 2015 -0700
@@ -103,7 +103,7 @@
 				}
 
 				jsonEncode <- {
-					parts <- map: :el { json encode: el }
+					parts <- map: :el { jsonEncoder encode: el }
 					"[" . (parts join: ",") . "]"
 				}
 			}