Index: libobjc/init.c
===================================================================
--- libobjc/init.c	(revision 168250)
+++ libobjc/init.c	(working copy)
@@ -109,9 +109,9 @@ BOOL __objc_dangling_categories = NO;           /*
 static void objc_send_load (void);
 
 /* Inserts all the classes defined in module in a tree of classes that
-   resembles the class hierarchy. This tree is traversed in preorder
+   resembles the class hierarchy.  This tree is traversed in preorder
    and the classes in its nodes receive the +load message if these
-   methods were not executed before. The algorithm ensures that when
+   methods were not executed before.  The algorithm ensures that when
    the +load method of a class is executed all the superclasses have
    been already received the +load message.  */
 static void __objc_create_classes_tree (struct objc_module *module);
@@ -124,15 +124,22 @@ static void __objc_call_load_callback (struct objc
    installed in the runtime.  */
 static BOOL class_is_subclass_of_class (Class class, Class superclass);
 
+/* This is a node in the class tree hierarchy used to send +load
+   messages.  */
 typedef struct objc_class_tree
 {
+  /* The class corresponding to the node.  */
   Class class;
-  struct objc_list *subclasses; /* `head' is a pointer to an
-				   objc_class_tree.  */
+
+  /* This is a linked list of all the direct subclasses of this class.
+     'head' points to a subclass node; 'tail' points to the next
+     objc_list node (whose 'head' points to another subclass node,
+     etc).  */
+  struct objc_list *subclasses;
 } objc_class_tree;
 
-/* This is a linked list of objc_class_tree trees. The head of these
-   trees are root classes (their super class is Nil). These different
+/* This is a linked list of objc_class_tree trees.  The head of these
+   trees are root classes (their super class is Nil).  These different
    trees represent different class hierarchies.  */
 static struct objc_list *__objc_class_tree_list = NULL;
 
@@ -145,7 +152,7 @@ static cache_ptr __objc_load_methods = NULL;
    is really needed so that superclasses will get the message before
    subclasses.
 
-   This tree will contain classes which are being loaded (or have just
+   This tree may contain classes which are being loaded (or have just
    being loaded), and whose super_class pointers have not yet been
    resolved.  This implies that their super_class pointers point to a
    string with the name of the superclass; when the first message is
@@ -184,29 +191,30 @@ static Class  class_superclass_of_class (Class cla
 
 
 /* Creates a tree of classes whose topmost class is directly inherited
-   from `upper' and the bottom class in this tree is
-   `bottom_class'. The classes in this tree are super classes of
-   `bottom_class'. `subclasses' member of each tree node point to the
-   next subclass tree node.  */
+   from `upper' and the bottom class in this tree is `bottom_class'.
+   If `upper' is Nil, creates a class hierarchy up to a root class.
+   The classes in this tree are super classes of `bottom_class'.  The
+   `subclasses' member of each tree node point to the list of
+   subclasses for the node.  */
 static objc_class_tree *
 create_tree_of_subclasses_inherited_from (Class bottom_class, Class upper)
 {
   Class superclass;
   objc_class_tree *tree, *prev;
 
-  if (bottom_class->super_class)
-    superclass = objc_getClass ((char *) bottom_class->super_class);
-  else
-    superclass = Nil;
-
   DEBUG_PRINTF ("create_tree_of_subclasses_inherited_from:");
   DEBUG_PRINTF (" bottom_class = %s, upper = %s\n",
 		(bottom_class ? bottom_class->name : NULL),
 		(upper ? upper->name : NULL));
 
-  tree = prev = objc_calloc (1, sizeof (objc_class_tree));
+  superclass = class_superclass_of_class (bottom_class);
+
+  prev = objc_calloc (1, sizeof (objc_class_tree));
   prev->class = bottom_class;
 
+  if (superclass == upper)
+    return prev;
+
   while (superclass != upper)
     {
       tree = objc_calloc (1, sizeof (objc_class_tree));
@@ -220,16 +228,16 @@ create_tree_of_subclasses_inherited_from (Class bo
 }
 
 /* Insert the `class' into the proper place in the `tree' class
-   hierarchy. This function returns a new tree if the class has been
+   hierarchy.  This function returns a new tree if the class has been
    successfully inserted into the tree or NULL if the class is not
-   part of the classes hierarchy described by `tree'. This function is
-   private to objc_tree_insert_class (), you should not call it
+   part of the classes hierarchy described by `tree'.  This function
+   is private to objc_tree_insert_class (), you should not call it
    directly.  */
 static objc_class_tree *
 __objc_tree_insert_class (objc_class_tree *tree, Class class)
 {
-  DEBUG_PRINTF ("__objc_tree_insert_class: tree = %p, class = %s\n",
-		tree, class->name);
+  DEBUG_PRINTF ("__objc_tree_insert_class: tree = %p (root: %s), class = %s\n",
+		tree, ((tree && tree->class) ? tree->class->name : "Nil"), class->name);
 
   if (tree == NULL)
     return create_tree_of_subclasses_inherited_from (class, NULL);
@@ -315,27 +323,26 @@ objc_tree_insert_class (Class class)
 {
   struct objc_list *list_node;
   objc_class_tree *tree;
-
+  
   list_node = __objc_class_tree_list;
   while (list_node)
     {
+      /* Try to insert the class in this class hierarchy.  */
       tree = __objc_tree_insert_class (list_node->head, class);
       if (tree)
 	{
 	  list_node->head = tree;
-	  break;
+	  return;
 	}
       else
 	list_node = list_node->tail;
     }
-
-  /* If the list was finished but the class hasn't been inserted,
-     insert it here.  */
-  if (! list_node)
-    {
-      __objc_class_tree_list = list_cons (NULL, __objc_class_tree_list);
-      __objc_class_tree_list->head = __objc_tree_insert_class (NULL, class);
-    }
+  
+  /* If the list was finished but the class hasn't been inserted, we
+     don't have an existing class hierarchy that can accomodate it.
+     Create a new one.  */
+  __objc_class_tree_list = list_cons (NULL, __objc_class_tree_list);
+  __objc_class_tree_list->head = __objc_tree_insert_class (NULL, class);
 }
 
 /* Traverse tree in preorder. Used to send +load.  */
@@ -603,7 +610,6 @@ __objc_exec_class (struct objc_module *module)
       duplicate_classes = objc_hash_new (8,
 					 (hash_func_type)objc_hash_ptr,
 					 objc_compare_ptrs);
-      __objc_class_tree_list = list_cons (NULL, __objc_class_tree_list);
       __objc_load_methods = objc_hash_new (128, 
 					   (hash_func_type)objc_hash_ptr,
 					   objc_compare_ptrs);
Index: libobjc/ChangeLog
===================================================================
--- libobjc/ChangeLog	(revision 168250)
+++ libobjc/ChangeLog	(working copy)
@@ -1,3 +1,14 @@
+2010-12-26  Nicola Pero  <nicola.pero@meta-innovation.com>
+
+	* init.c (create_tree_of_subclasses_inherited_from): Use
+	class_superclass_of_class instead of assuming a class is
+	unresolved when it could be resolved.  Tidied up assignment and
+	check.
+	(__objc_tree_insert_class): Enhanced DEBUG_PRINTF.
+	(objc_tree_insert_class): Tidied up loop; return immediately upon
+	inserting a class.
+	(__objc_exec_class): Do not set __objc_class_tree_list.
+	
 2010-12-24  Nicola Pero  <nicola.pero@meta-innovation.com>
 
 	* selector.c (sel_getTypedSelector): Return NULL if given a NULL
Index: gcc/testsuite/ChangeLog
===================================================================
--- gcc/testsuite/ChangeLog	(revision 168250)
+++ gcc/testsuite/ChangeLog	(working copy)
@@ -1,3 +1,14 @@
+2010-12-26  Nicola Pero  <nicola.pero@meta-innovation.com>
+
+	* objc.dg/special/special.exp: Added load-category-2 and
+	load-category-3 tests.
+	* objc.dg/special/load-category-2.h: New.
+	* objc.dg/special/load-category-2.m: New.
+	* objc.dg/special/load-category-2a.m: New.
+	* objc.dg/special/load-category-3.h: New.
+	* objc.dg/special/load-category-3.m: New.
+	* objc.dg/special/load-category-3a.m: New.
+
 2010-12-25  Ira Rosen  <irar@il.ibm.com>
 
 	PR testsuite/47057
Index: gcc/testsuite/objc.dg/special/load-category-2.h
===================================================================
--- gcc/testsuite/objc.dg/special/load-category-2.h	(revision 0)
+++ gcc/testsuite/objc.dg/special/load-category-2.h	(revision 0)
@@ -0,0 +1,19 @@
+/* Contributed by Nicola Pero <nicola.pero@meta-innovation.com>, December 2010.  */
+
+/* Test the order of calling +load between classes and categories.  */
+
+void complete_load_step (int load_step);
+void check_that_load_step_was_completed (int load_step);
+void check_that_load_step_was_not_completed (int load_step);
+
+@interface TestClass1
+{
+  id isa;
+}
+@end
+
+@interface TestClass2 : TestClass1
+@end
+
+@interface TestClass3 : TestClass2
+@end
Index: gcc/testsuite/objc.dg/special/load-category-3.h
===================================================================
--- gcc/testsuite/objc.dg/special/load-category-3.h	(revision 0)
+++ gcc/testsuite/objc.dg/special/load-category-3.h	(revision 0)
@@ -0,0 +1,17 @@
+/* Contributed by Nicola Pero <nicola.pero@meta-innovation.com>, December 2010.  */
+
+void complete_load_step (int load_step);
+void check_that_load_step_was_completed (int load_step);
+void check_that_load_step_was_not_completed (int load_step);
+
+@interface TestClass1
+{
+  id isa;
+}
+@end
+
+@interface TestClass2 : TestClass1
+@end
+
+@interface TestClass3 : TestClass2
+@end
Index: gcc/testsuite/objc.dg/special/load-category-2.m
===================================================================
--- gcc/testsuite/objc.dg/special/load-category-2.m	(revision 0)
+++ gcc/testsuite/objc.dg/special/load-category-2.m	(revision 0)
@@ -0,0 +1,106 @@
+/* Contributed by Nicola Pero <nicola.pero@meta-innovation.com>, December 2010.  */
+/* { dg-do run } */
+/* { dg-xfail-run-if "Needs OBJC2 ABI" { *-*-darwin* && { lp64 && { ! objc2 } } } { "-fnext-runtime" } { "" } } */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <objc/objc.h>
+#include <objc/runtime.h>
+
+#include "load-category-2.h"
+
+/* This test tests that +load is called in the correct order for
+   classes and categories.  +load needs to be called in superclasses
+   before subclasses, and in the main class before categories.  */
+
+/* Compile the classes in random order to prevent the runtime from
+   sending +load in the correct order just because the classes happen
+   to have been compiled in that order.  */
+@implementation TestClass2
++ load
+{
+  printf ("[TestClass2 +load]\n");
+  /* Check superclasses/subclasses +load order.  */
+  check_that_load_step_was_completed (0);
+  check_that_load_step_was_not_completed (1);
+  check_that_load_step_was_not_completed (2);
+
+  /* Check that the corresponding category's +load was not done.  */
+  check_that_load_step_was_not_completed (4);
+
+  complete_load_step (1);
+}
+@end
+
+@implementation TestClass3
++ load
+{
+  printf ("[TestClass3 +load]\n");
+
+  /* Check superclasses/subclasses +load order.  */
+  check_that_load_step_was_completed (0);
+  check_that_load_step_was_completed (1);
+  check_that_load_step_was_not_completed (2);
+
+  /* Check that the corresponding category's +load was not done.  */
+  check_that_load_step_was_not_completed (5);
+
+  complete_load_step (2);
+}
+@end
+
+@implementation TestClass1
++ initialize { return self; }
++ load
+{
+  printf ("[TestClass1 +load]\n");
+
+  /* Check superclasses/subclasses +load order.  */
+  check_that_load_step_was_not_completed (0);
+  check_that_load_step_was_not_completed (1);
+  check_that_load_step_was_not_completed (2);
+
+  /* Check that the corresponding category's +load was not done.  */
+  check_that_load_step_was_not_completed (3);
+
+  complete_load_step (0);
+}
+@end
+
+
+static BOOL load_step_completed[6] = { NO, NO, NO, NO, NO, NO };
+
+void complete_load_step (int load_step)
+{
+  load_step_completed[load_step] = YES;
+}
+
+void check_that_load_step_was_completed (int load_step)
+{
+  if (load_step_completed[load_step] == NO)
+    {
+      printf ("Load step %d was not completed but should have been\n", load_step);
+      abort ();
+    }
+}
+
+void check_that_load_step_was_not_completed (int load_step)
+{
+  if (load_step_completed[load_step] == YES)
+    {
+      printf ("Load step %d was completed but shouldn't have been\n", load_step);
+      abort ();
+    }
+}
+
+int main (void)
+{
+  check_that_load_step_was_completed (0);
+  check_that_load_step_was_completed (1);
+  check_that_load_step_was_completed (2);
+  check_that_load_step_was_completed (3);
+  check_that_load_step_was_completed (4);
+  check_that_load_step_was_completed (5);
+
+  return 0;
+}
Index: gcc/testsuite/objc.dg/special/load-category-2a.m
===================================================================
--- gcc/testsuite/objc.dg/special/load-category-2a.m	(revision 0)
+++ gcc/testsuite/objc.dg/special/load-category-2a.m	(revision 0)
@@ -0,0 +1,47 @@
+/* Contributed by Nicola Pero <nicola.pero@meta-innovation.com>, December 2010.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <objc/objc.h>
+#include <objc/runtime.h>
+
+#include "load-category-2.h"
+
+/* Compile the categories in random order to prevent the runtime from
+   sending +load in the correct order just because the classes happen
+   to have been compiled in that order.  */
+@implementation TestClass2 (Category)
++ load
+{
+  printf ("[TestClass2(Category) +load]\n");
+
+  /* Check that the corresponding class's +load was done.  */
+  check_that_load_step_was_completed (1);
+
+  complete_load_step (4);
+}
+@end
+
+@implementation TestClass3 (Category)
++ load
+{
+  printf ("[TestClass3(Category) +load]\n");
+
+  /* Check that the corresponding class's +load was done.  */
+  check_that_load_step_was_completed (2);
+
+  complete_load_step (5);
+}
+@end
+
+@implementation TestClass1 (Category)
++ load
+{
+  printf ("[TestClass1(Category) +load]\n");
+
+  /* Check that the corresponding class's +load was done.  */
+  check_that_load_step_was_completed (0);
+
+  complete_load_step (3);
+}
+@end
Index: gcc/testsuite/objc.dg/special/load-category-3.m
===================================================================
--- gcc/testsuite/objc.dg/special/load-category-3.m	(revision 0)
+++ gcc/testsuite/objc.dg/special/load-category-3.m	(revision 0)
@@ -0,0 +1,88 @@
+/* Contributed by Nicola Pero <nicola.pero@meta-innovation.com>, December 2010.  */
+/* { dg-do run } */
+/* { dg-xfail-run-if "Needs OBJC2 ABI" { *-*-darwin* && { lp64 && { ! objc2 } } } { "-fnext-runtime" } { "" } } */
+
+/* This test is identical to load-category-2, but the classes and
+   categories are created in inverted order in the modules, to test
+   that you can load classes first, or categories first, and it all
+   still works in both cases.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <objc/objc.h>
+#include <objc/runtime.h>
+
+#include "load-category-3.h"
+
+@implementation TestClass2 (Category)
++ load
+{
+  printf ("[TestClass2(Category) +load]\n");
+
+  /* Check that the corresponding class's +load was done.  */
+  check_that_load_step_was_completed (1);
+
+  complete_load_step (4);
+}
+@end
+
+@implementation TestClass3 (Category)
++ load
+{
+  printf ("[TestClass3(Category) +load]\n");
+
+  /* Check that the corresponding class's +load was done.  */
+  check_that_load_step_was_completed (2);
+
+  complete_load_step (5);
+}
+@end
+
+@implementation TestClass1 (Category)
++ load
+{
+  printf ("[TestClass1(Category) +load]\n");
+
+  /* Check that the corresponding class's +load was done.  */
+  check_that_load_step_was_completed (0);
+
+  complete_load_step (3);
+}
+@end
+
+static BOOL load_step_completed[6] = { NO, NO, NO, NO, NO, NO };
+
+void complete_load_step (int load_step)
+{
+  load_step_completed[load_step] = YES;
+}
+
+void check_that_load_step_was_completed (int load_step)
+{
+  if (load_step_completed[load_step] == NO)
+    {
+      printf ("Load step %d was not completed but should have been\n", load_step);
+      abort ();
+    }
+}
+
+void check_that_load_step_was_not_completed (int load_step)
+{
+  if (load_step_completed[load_step] == YES)
+    {
+      printf ("Load step %d was completed but shouldn't have been\n", load_step);
+      abort ();
+    }
+}
+
+int main (void)
+{
+  check_that_load_step_was_completed (0);
+  check_that_load_step_was_completed (1);
+  check_that_load_step_was_completed (2);
+  check_that_load_step_was_completed (3);
+  check_that_load_step_was_completed (4);
+  check_that_load_step_was_completed (5);
+
+  return 0;
+}
Index: gcc/testsuite/objc.dg/special/load-category-3a.m
===================================================================
--- gcc/testsuite/objc.dg/special/load-category-3a.m	(revision 0)
+++ gcc/testsuite/objc.dg/special/load-category-3a.m	(revision 0)
@@ -0,0 +1,66 @@
+/* Contributed by Nicola Pero <nicola.pero@meta-innovation.com>, December 2010.  */
+
+/* This test is identical to load-category-2, but the classes and
+   categories are created in inverted order in the modules, to test
+   that you can load classes first, or categories first, and it all
+   still works.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <objc/objc.h>
+#include <objc/runtime.h>
+
+#include "load-category-3.h"
+
+@implementation TestClass2
++ load
+{
+  printf ("[TestClass2 +load]\n");
+  /* Check superclasses/subclasses +load order.  */
+  check_that_load_step_was_completed (0);
+  check_that_load_step_was_not_completed (1);
+  check_that_load_step_was_not_completed (2);
+
+  /* Check that the corresponding category's +load was not done.  */
+  check_that_load_step_was_not_completed (4);
+
+  complete_load_step (1);
+}
+@end
+
+@implementation TestClass3
++ load
+{
+  printf ("[TestClass3 +load]\n");
+
+  /* Check superclasses/subclasses +load order.  */
+  check_that_load_step_was_completed (0);
+  check_that_load_step_was_completed (1);
+  check_that_load_step_was_not_completed (2);
+
+  /* Check that the corresponding category's +load was not done.  */
+  check_that_load_step_was_not_completed (5);
+
+  complete_load_step (2);
+}
+@end
+
+@implementation TestClass1
++ initialize { return self; }
++ load
+{
+  printf ("[TestClass1 +load]\n");
+
+  /* Check superclasses/subclasses +load order.  */
+  check_that_load_step_was_not_completed (0);
+  check_that_load_step_was_not_completed (1);
+  check_that_load_step_was_not_completed (2);
+
+  /* Check that the corresponding category's +load was not done.  */
+  check_that_load_step_was_not_completed (3);
+
+  complete_load_step (0);
+}
+@end
+
+
Index: gcc/testsuite/objc.dg/special/special.exp
===================================================================
--- gcc/testsuite/objc.dg/special/special.exp	(revision 168250)
+++ gcc/testsuite/objc.dg/special/special.exp	(working copy)
@@ -27,6 +27,9 @@ if ![info exists DEFAULT_CFLAGS] then {
 # Initialize `dg'.
 dg-init
 
+# TODO: All these testcases compile and link two Objective-C modules.
+# Remove code duplication and factor the common code out.
+
 #
 # unclaimed-category-1 test
 #
@@ -83,6 +86,60 @@ if ![string match "" $lines] then {
 }
 }
 
+#
+# load-category-2 test
+#
+# This test is similar to the one above.  We compile load-category-2.m
+# and load-category-2a.m, link them together, and execute the result.
+set add_flags "additional_flags=-I${srcdir}/../../libobjc"
+lappend add_flags "additional_flags=-fgnu-runtime"
+set lines [objc_target_compile "$srcdir/$subdir/load-category-2a.m" "load-category-2a.o" object $add_flags ]
+if ![string match "" $lines] then {
+    fail "load-category-2a.o"
+} else {
+    dg-runtest "$srcdir/$subdir/load-category-2.m" "load-category-2a.o" "-I${srcdir}/../../libobjc -fgnu-runtime"
+    file delete load-category-2a.o
+}
+
+if [istarget "*-*-darwin*" ] {
+set add_flags ""
+lappend add_flags "additional_flags=-fnext-runtime"
+set lines [objc_target_compile "$srcdir/$subdir/load-category-2a.m" "load-category-2a.o" object $add_flags ]
+if ![string match "" $lines] then {
+    fail "load-category-2a.o"
+} else {
+    dg-runtest "$srcdir/$subdir/load-category-2.m" "load-category-2a.o" "-fnext-runtime"
+    file delete load-category-2a.o
+}
+}
+
+#
+# load-category-3 test
+#
+# This test is similar to the one above.  We compile load-category-3.m
+# and load-category-3a.m, link them together, and execute the result.
+set add_flags "additional_flags=-I${srcdir}/../../libobjc"
+lappend add_flags "additional_flags=-fgnu-runtime"
+set lines [objc_target_compile "$srcdir/$subdir/load-category-3a.m" "load-category-3a.o" object $add_flags ]
+if ![string match "" $lines] then {
+    fail "load-category-3a.o"
+} else {
+    dg-runtest "$srcdir/$subdir/load-category-3.m" "load-category-3a.o" "-I${srcdir}/../../libobjc -fgnu-runtime"
+    file delete load-category-3a.o
+}
+
+if [istarget "*-*-darwin*" ] {
+set add_flags ""
+lappend add_flags "additional_flags=-fnext-runtime"
+set lines [objc_target_compile "$srcdir/$subdir/load-category-3a.m" "load-category-3a.o" object $add_flags ]
+if ![string match "" $lines] then {
+    fail "load-category-3a.o"
+} else {
+    dg-runtest "$srcdir/$subdir/load-category-3.m" "load-category-3a.o" "-fnext-runtime"
+    file delete load-category-3a.o
+}
+}
+
 # All done.
 dg-finish
 
