[runtime] Handle circular references in SRE types

We previously recursed through the entire directed cyclic graph
of the type passed to SRE. When given a (legal) circular type reference,
we encountered stack overflows. This was particularly easy to trigger
with fsharpi and with FAKE.

By creating everything about the type before searching for the parent,
and by defering all type hierarchy establishment until the type must be
surfaced to manage code, we tease out the data dependencies caught up in
the cycle.

Note the bounded lifetime of the unmanaged object hidden in the SRE
module, which acts as a global reference for all types reachable from
the TypeBuilder passed to the runtime through the icall.

4 files changed, 149 insertions, 56 deletions

diff --git a/mcs/class/corlib/System.Reflection.Emit/ModuleBuilder.cs b/mcs/class/corlib/System.Reflection.Emit/ModuleBuilder.cs
index b055797bd86..c000b1eadc1 100644
--- a/mcs/class/corlib/System.Reflection.Emit/ModuleBuilder.cs
+++ b/mcs/class/corlib/System.Reflection.Emit/ModuleBuilder.cs
@@ -62,6 +62,7 @@ namespace System.Reflection.Emit {
 		private FieldBuilder[] global_fields;
 		bool is_main;
 		private MonoResource[] resources;
+		private IntPtr unparented_classes;
 		#endregion
 #pragma warning restore 169, 414
 		
diff --git a/mcs/class/corlib/System.Reflection.Emit/TypeBuilder.cs b/mcs/class/corlib/System.Reflection.Emit/TypeBuilder.cs
index 30ae09cdf16..b1cc9727d5a 100644
--- a/mcs/class/corlib/System.Reflection.Emit/TypeBuilder.cs
+++ b/mcs/class/corlib/System.Reflection.Emit/TypeBuilder.cs
@@ -79,6 +79,7 @@ namespace System.Reflection.Emit
 		private GenericTypeParameterBuilder[] generic_params;
 		private RefEmitPermissionSet[] permissions;
 		private TypeInfo created;
+		private int state;
 		#endregion
 #pragma warning restore 169		
 		
diff --git a/mono/metadata/object-internals.h b/mono/metadata/object-internals.h
index 48bf20f157e..cffe997a667 100644
--- a/mono/metadata/object-internals.h
+++ b/mono/metadata/object-internals.h
@@ -1186,11 +1186,18 @@ typedef struct {
 	MonoArray *global_fields;
 	gboolean is_main;
 	MonoArray *resources;
+	GHashTable *unparented_classes;
 } MonoReflectionModuleBuilder;
 
 /* Safely acess System.Reflection.Emit.ModuleBuidler from native code */
 TYPED_HANDLE_DECL (MonoReflectionModuleBuilder);
 
+typedef enum {
+	MonoTypeBuilderNew = 0,
+	MonoTypeBuilderEntered = 1,
+	MonoTypeBuilderFinished = 2
+} MonoTypeBuilderState;
+
 typedef struct {
 	MonoReflectionType type;
 	MonoString *name;
@@ -1216,6 +1223,7 @@ typedef struct {
 	MonoArray *generic_params;
 	MonoArray *permissions;
 	MonoReflectionType *created;
+	gint32 state;
 } MonoReflectionTypeBuilder;
 
 /* Safely access System.Reflection.Emit.TypeBuilder from native code */
diff --git a/mono/metadata/sre.c b/mono/metadata/sre.c
index 9e66d2486d9..f4e5f5ddab9 100644
--- a/mono/metadata/sre.c
+++ b/mono/metadata/sre.c
@@ -47,7 +47,8 @@ static guint32 mono_image_get_sighelper_token (MonoDynamicImage *assembly, MonoR
 static gboolean ensure_runtime_vtable (MonoClass *klass, MonoError  *error);
 static void reflection_methodbuilder_from_dynamic_method (ReflectionMethodBuilder *rmb, MonoReflectionDynamicMethod *mb);
 static gboolean reflection_setup_internal_class (MonoReflectionTypeBuilderHandle tb, MonoError *error);
-static gboolean reflection_create_generic_class (MonoReflectionTypeBuilderHandle tb, MonoError *error);
+static gboolean reflection_init_generic_class (MonoReflectionTypeBuilderHandle tb, MonoError *error);
+static gboolean reflection_setup_class_hierarchy (GHashTable *unparented, MonoError *error);
 
 
 static gpointer register_assembly (MonoDomain *domain, MonoReflectionAssembly *res, MonoAssembly *assembly);
@@ -1527,7 +1528,7 @@ reflection_instance_handle_mono_type (MonoReflectionGenericClassHandle ref_gclas
 	}
 	MonoClass *gtd_klass = mono_class_from_mono_type (gtd);
 	if (is_sre_type_builder (mono_handle_class (ref_gtd))) {
-		reflection_create_generic_class (MONO_HANDLE_CAST (MonoReflectionTypeBuilder, ref_gtd), error);
+		reflection_setup_internal_class (MONO_HANDLE_CAST (MonoReflectionTypeBuilder, ref_gtd), error);
 		if (!is_ok (error)) {
 			goto leave;
 		}
@@ -2342,52 +2343,65 @@ leave:
 	return result;
 }
 
-/**
- * reflection_setup_internal_class:
- * @tb: a TypeBuilder object
- * @error: set on error
- *
- * Creates a MonoClass that represents the TypeBuilder.
- * This is a trick that lets us simplify a lot of reflection code
- * (and will allow us to support Build and Run assemblies easier).
- *
- * Returns TRUE on success. On failure, returns FALSE and sets @error.
- */
 static gboolean
-reflection_setup_internal_class (MonoReflectionTypeBuilderHandle ref_tb, MonoError *error)
+reflection_setup_class_hierarchy (GHashTable *unparented, MonoError *error)
 {
-	HANDLE_FUNCTION_ENTER ();
 	error_init (error);
 
 	mono_loader_lock ();
 
-	MonoReflectionTypeHandle ref_parent = MONO_HANDLE_NEW_GET (MonoReflectionType, ref_tb, parent);
-	MonoClass *parent = NULL;
-	if (!MONO_HANDLE_IS_NULL (ref_parent)) {
-		MonoType *parent_type = mono_reflection_type_handle_mono_type (ref_parent, error);
-		if (!is_ok (error))
-			goto leave;
-		/* check so we can compile corlib correctly */
-		if (strcmp (mono_handle_class (ref_parent)->name, "TypeBuilder") == 0) {
-			/* mono_class_setup_mono_type () guaranteess type->data.klass is valid */
-			parent = parent_type->data.klass;
-		} else {
-			parent = mono_class_from_mono_type (parent_type);
+	MonoType *parent_type;
+	MonoType *child_type;
+	GHashTableIter iter;
+
+	g_hash_table_iter_init (&iter, unparented);
+
+	while (g_hash_table_iter_next (&iter, (gpointer *) &child_type, (gpointer *) &parent_type)) {
+		MonoClass *child_class = mono_class_from_mono_type (child_type);
+		if (parent_type != NULL) {
+			MonoClass *parent_class = mono_class_from_mono_type (parent_type);
+			child_class->parent = NULL;
+			/* fool mono_class_setup_parent */
+			child_class->supertypes = NULL;
+			mono_class_setup_parent (child_class, parent_class);
+		} else if (strcmp (child_class->name, "Object") == 0 && strcmp (child_class->name_space, "System") == 0) {
+			const char *old_n = child_class->name;
+			/* trick to get relative numbering right when compiling corlib */
+			child_class->name = "BuildingObject";
+			mono_class_setup_parent (child_class, mono_defaults.object_class);
+			child_class->name = old_n;
 		}
+		mono_class_setup_mono_type (child_class);
+		mono_class_setup_supertypes (child_class);
 	}
-	
-	/* the type has already being created: it means we just have to change the parent */
-	MonoType *type = MONO_HANDLE_GETVAL (MONO_HANDLE_CAST (MonoReflectionType, ref_tb), type);
-	if (type != NULL) {
-		MonoClass *klass = mono_class_from_mono_type (type);
-		klass->parent = NULL;
-		/* fool mono_class_setup_parent */
-		klass->supertypes = NULL;
-		mono_class_setup_parent (klass, parent);
-		mono_class_setup_mono_type (klass);
+
+	mono_loader_unlock ();
+	return is_ok (error);
+}
+
+static gboolean
+reflection_setup_internal_class_internal (MonoReflectionTypeBuilderHandle ref_tb, MonoError *error)
+{
+	HANDLE_FUNCTION_ENTER ();
+	error_init (error);
+
+	mono_loader_lock ();
+
+	gint32 entering_state = MONO_HANDLE_GETVAL (MONO_HANDLE_CAST (MonoReflectionTypeBuilder, ref_tb), state);
+	if (entering_state != MonoTypeBuilderNew) {
+		g_assert (MONO_HANDLE_GETVAL (MONO_HANDLE_CAST (MonoReflectionType, ref_tb), type));
 		goto leave;
 	}
 
+	MONO_HANDLE_SETVAL (ref_tb, state, MonoTypeBuilderState, MonoTypeBuilderEntered);
+	MonoReflectionModuleBuilderHandle module_ref = MONO_HANDLE_NEW_GET (MonoReflectionModuleBuilder, ref_tb, module);
+	GHashTable *unparented_classes = MONO_HANDLE_GETVAL(module_ref, unparented_classes);
+
+	// If this type is already setup, exit. We'll fix the parenting later
+	MonoType *type = MONO_HANDLE_GETVAL (MONO_HANDLE_CAST (MonoReflectionType, ref_tb), type);
+	if (type)
+		goto leave;
+
 	MonoReflectionModuleBuilderHandle ref_module = MONO_HANDLE_NEW_GET (MonoReflectionModuleBuilder, ref_tb, module);
 	MonoDynamicImage *dynamic_image = MONO_HANDLE_GETVAL (ref_module, dynamic_image);
 
@@ -2438,16 +2452,6 @@ reflection_setup_internal_class (MonoReflectionTypeBuilderHandle ref_tb, MonoErr
 
 	mono_dynamic_image_register_token (dynamic_image, MONO_TOKEN_TYPE_DEF | table_idx, MONO_HANDLE_CAST (MonoObject, ref_tb));
 
-	if (parent != NULL) {
-		mono_class_setup_parent (klass, parent);
-	} else if (strcmp (klass->name, "Object") == 0 && strcmp (klass->name_space, "System") == 0) {
-		const char *old_n = klass->name;
-		/* trick to get relative numbering right when compiling corlib */
-		klass->name = "BuildingObject";
-		mono_class_setup_parent (klass, mono_defaults.object_class);
-		klass->name = old_n;
-	}
-
 	if ((!strcmp (klass->name, "ValueType") && !strcmp (klass->name_space, "System")) ||
 			(!strcmp (klass->name, "Object") && !strcmp (klass->name_space, "System")) ||
 			(!strcmp (klass->name, "Enum") && !strcmp (klass->name_space, "System"))) {
@@ -2458,14 +2462,52 @@ reflection_setup_internal_class (MonoReflectionTypeBuilderHandle ref_tb, MonoErr
 
 	mono_class_setup_mono_type (klass);
 
-	mono_class_setup_supertypes (klass);
-
 	/*
 	 * FIXME: handle interfaces.
 	 */
-
 	MonoReflectionTypeHandle ref_tb_type = MONO_HANDLE_CAST (MonoReflectionType, ref_tb);
 	MONO_HANDLE_SETVAL (ref_tb_type, type, MonoType*, &klass->byval_arg);
+	MONO_HANDLE_SETVAL (ref_tb, state, gint32, MonoTypeBuilderFinished);
+
+	reflection_init_generic_class (ref_tb, error);
+	if (!is_ok (error))
+		goto leave;
+
+	// Do here so that the search inside of the parent can see the above type that's been set.
+	MonoReflectionTypeHandle ref_parent = MONO_HANDLE_NEW_GET (MonoReflectionType, ref_tb, parent);
+	MonoType *parent_type = NULL;
+	if (!MONO_HANDLE_IS_NULL (ref_parent)) {
+		MonoClass *parent_klass = mono_handle_class (ref_parent);
+		gboolean recursive_init = TRUE;
+
+		if (is_sre_type_builder (parent_klass)) {
+			MonoTypeBuilderState parent_state = MONO_HANDLE_GETVAL (MONO_HANDLE_CAST (MonoReflectionTypeBuilder, ref_parent), state);
+
+			if (parent_state != MonoTypeBuilderNew) {
+				// Initialize types reachable from parent recursively
+				// We'll fix the type hierarchy later
+				recursive_init = FALSE;
+			}
+		}
+
+		if (recursive_init) {
+			// If we haven't encountered a cycle, force the creation of ref_parent's type
+			mono_reflection_type_handle_mono_type (ref_parent, error);
+			if (!is_ok (error))
+				goto leave;
+		}
+
+		parent_type = MONO_HANDLE_GETVAL (ref_parent, type);
+
+		// If we failed to create the parent, fail the child
+		if (!parent_type)
+			goto leave;
+	}
+
+	// Push the child type and parent type to process later
+	// Note: parent_type may be null.
+	g_assert (!g_hash_table_lookup (unparented_classes, &klass->byval_arg));
+	g_hash_table_insert (unparented_classes, &klass->byval_arg, parent_type);
 
 	if (!MONO_HANDLE_IS_NULL (ref_nesting_type)) {
 		if (!reflection_setup_internal_class (MONO_HANDLE_CAST (MonoReflectionTypeBuilder, ref_nesting_type), error))
@@ -2487,23 +2529,25 @@ leave:
 }
 
 /**
- * reflection_create_generic_class:
+ * reflection_init_generic_class:
  * @tb: a TypeBuilder object
  * @error: set on error
  *
  * Creates the generic class after all generic parameters have been added.
  * On success returns TRUE, on failure returns FALSE and sets @error.
+ *
+ * This assumes that reflection_setup_internal_class has already set up
+ * ref_tb
  */
 static gboolean
-reflection_create_generic_class (MonoReflectionTypeBuilderHandle ref_tb, MonoError *error)
+reflection_init_generic_class (MonoReflectionTypeBuilderHandle ref_tb, MonoError *error)
 {
 	HANDLE_FUNCTION_ENTER ();
 
 	error_init (error);
 
-	reflection_setup_internal_class (ref_tb, error);
-	if (!is_ok (error))
-		goto leave;
+	MonoTypeBuilderState ref_state = MONO_HANDLE_GETVAL (ref_tb, state);
+	g_assert (ref_state == MonoTypeBuilderFinished);
 
 	MonoType *type = MONO_HANDLE_GETVAL (MONO_HANDLE_CAST (MonoReflectionType, ref_tb), type);
 	MonoClass *klass = mono_class_from_mono_type (type);
@@ -3532,12 +3576,51 @@ remove_instantiations_of_and_ensure_contents (gpointer key,
 		return FALSE;
 }
 
+/**
+ * reflection_setup_internal_class:
+ * @tb: a TypeBuilder object
+ * @error: set on error
+ *
+ * Creates a MonoClass that represents the TypeBuilder.
+ * This is a trick that lets us simplify a lot of reflection code
+ * (and will allow us to support Build and Run assemblies easier).
+ *
+ * Returns TRUE on success. On failure, returns FALSE and sets @error.
+ */
+static gboolean
+reflection_setup_internal_class (MonoReflectionTypeBuilderHandle ref_tb, MonoError *error)
+{
+	MonoReflectionModuleBuilderHandle module_ref = MONO_HANDLE_NEW_GET (MonoReflectionModuleBuilder, ref_tb, module);
+	GHashTable *unparented_classes = MONO_HANDLE_GETVAL(module_ref, unparented_classes);
+
+	if (unparented_classes) {
+		return reflection_setup_internal_class_internal (ref_tb, error);
+	} else {
+		// If we're not being called recursively
+		unparented_classes = g_hash_table_new (NULL, NULL);
+		MONO_HANDLE_SETVAL (module_ref, unparented_classes, GHashTable *, unparented_classes);
+
+		gboolean ret_val = reflection_setup_internal_class_internal (ref_tb, error);
+		mono_error_assert_ok (error);
+
+		// Fix the relationship between the created classes and their parents
+		reflection_setup_class_hierarchy (unparented_classes, error);
+		mono_error_assert_ok (error);
+
+		g_hash_table_destroy (unparented_classes);
+		MONO_HANDLE_SETVAL (module_ref, unparented_classes, GHashTable *, NULL);
+
+		return ret_val;
+	}
+}
+
+
 MonoReflectionTypeHandle
 ves_icall_TypeBuilder_create_runtime_class (MonoReflectionTypeBuilderHandle ref_tb, MonoError *error)
 {
 	error_init (error);
 
-	reflection_create_generic_class (ref_tb, error);
+	reflection_setup_internal_class (ref_tb, error);
 	mono_error_assert_ok (error);
 
 	MonoDomain *domain = MONO_HANDLE_DOMAIN (ref_tb);