compiler: Handle recursive interfaces.

	* go-gcc.cc (Gcc_backend::placeholder_struct_type): Permit name to
	be empty.
	(Gcc_backend::set_placeholder_struct_type): Likewise.

From-SVN: r183340

12 files changed, 396 insertions, 232 deletions

diff --git a/gcc/go/ChangeLog b/gcc/go/ChangeLog
index 662b50e..0f7eb27 100644
--- a/gcc/go/ChangeLog
+++ b/gcc/go/ChangeLog
@@ -1,3 +1,9 @@
+2012-01-20  Ian Lance Taylor  <iant@google.com>
+
+	* go-gcc.cc (Gcc_backend::placeholder_struct_type): Permit name to
+	be empty.
+	(Gcc_backend::set_placeholder_struct_type): Likewise.
+
 2012-01-17  Ian Lance Taylor  <iant@google.com>
 
 	* gospec.c (lang_specific_driver): If we see -S without -o, add -o
diff --git a/gcc/go/go-gcc.cc b/gcc/go/go-gcc.cc
index bfa0ec7..ca0d626b 100644
--- a/gcc/go/go-gcc.cc
+++ b/gcc/go/go-gcc.cc
@@ -656,10 +656,13 @@ Gcc_backend::placeholder_struct_type(const std::string& name,
 				     Location location)
 {
   tree ret = make_node(RECORD_TYPE);
-  tree decl = build_decl(location.gcc_location(), TYPE_DECL,
-			 get_identifier_from_string(name),
-			 ret);
-  TYPE_NAME(ret) = decl;
+  if (!name.empty())
+    {
+      tree decl = build_decl(location.gcc_location(), TYPE_DECL,
+			     get_identifier_from_string(name),
+			     ret);
+      TYPE_NAME(ret) = decl;
+    }
   return this->make_type(ret);
 }
 
@@ -674,10 +677,13 @@ Gcc_backend::set_placeholder_struct_type(
   gcc_assert(TREE_CODE(t) == RECORD_TYPE && TYPE_FIELDS(t) == NULL_TREE);
   Btype* r = this->fill_in_struct(placeholder, fields);
 
-  // Build the data structure gcc wants to see for a typedef.
-  tree copy = build_distinct_type_copy(t);
-  TYPE_NAME(copy) = NULL_TREE;
-  DECL_ORIGINAL_TYPE(TYPE_NAME(t)) = copy;
+  if (TYPE_NAME(t) != NULL_TREE)
+    {
+      // Build the data structure gcc wants to see for a typedef.
+      tree copy = build_distinct_type_copy(t);
+      TYPE_NAME(copy) = NULL_TREE;
+      DECL_ORIGINAL_TYPE(TYPE_NAME(t)) = copy;
+    }
 
   return r->get_tree() != error_mark_node;
 }
diff --git a/gcc/go/gofrontend/backend.h b/gcc/go/gofrontend/backend.h
index 9777acc..2605ffe 100644
--- a/gcc/go/gofrontend/backend.h
+++ b/gcc/go/gofrontend/backend.h
@@ -139,7 +139,8 @@ class Backend
   set_placeholder_function_type(Btype* placeholder, Btype* ft) = 0;
 
   // Create a placeholder struct type.  This is used for a named
-  // struct type, as with placeholder_pointer_type.
+  // struct type, as with placeholder_pointer_type.  It is also used
+  // for interface types, in which case NAME will be the empty string.
   virtual Btype*
   placeholder_struct_type(const std::string& name, Location) = 0;
 
diff --git a/gcc/go/gofrontend/expressions.cc b/gcc/go/gofrontend/expressions.cc
index 5cada3a..7550a56 100644
--- a/gcc/go/gofrontend/expressions.cc
+++ b/gcc/go/gofrontend/expressions.cc
@@ -7566,7 +7566,7 @@ Builtin_call_expression::do_lower(Gogo* gogo, Named_object* function,
 	{
 	  // Calling recover outside of a function always returns the
 	  // nil empty interface.
-	  Type* eface = Type::make_interface_type(NULL, loc);
+	  Type* eface = Type::make_empty_interface_type(loc);
 	  return Expression::make_cast(eface, Expression::make_nil(loc), loc);
 	}
       break;
@@ -8189,7 +8189,7 @@ Builtin_call_expression::do_type()
       return Type::make_void_type();
 
     case BUILTIN_RECOVER:
-      return Type::make_interface_type(NULL, Linemap::predeclared_location());
+      return Type::make_empty_interface_type(Linemap::predeclared_location());
 
     case BUILTIN_APPEND:
       {
@@ -8883,7 +8883,7 @@ Builtin_call_expression::do_get_tree(Translate_context* context)
 	if (arg_tree == error_mark_node)
 	  return error_mark_node;
 	Type *empty =
-	  Type::make_interface_type(NULL, Linemap::predeclared_location());
+	  Type::make_empty_interface_type(Linemap::predeclared_location());
 	arg_tree = Expression::convert_for_assignment(context, empty,
 						      arg->type(),
 						      arg_tree, location);
@@ -8916,7 +8916,7 @@ Builtin_call_expression::do_get_tree(Translate_context* context)
 	  return error_mark_node;
 
 	Type *empty =
-	  Type::make_interface_type(NULL, Linemap::predeclared_location());
+	  Type::make_empty_interface_type(Linemap::predeclared_location());
 	tree empty_tree = type_to_tree(empty->get_backend(context->gogo()));
 
 	Type* nil_type = Type::make_nil_type();
diff --git a/gcc/go/gofrontend/gogo.cc b/gcc/go/gofrontend/gogo.cc
index a5de175..59a61bf 100644
--- a/gcc/go/gofrontend/gogo.cc
+++ b/gcc/go/gofrontend/gogo.cc
@@ -110,7 +110,8 @@ Gogo::Gogo(Backend* backend, Linemap* linemap, int int_type_size,
     results->push_back(Typed_identifier("", Type::lookup_string_type(), loc));
     Type *method_type = Type::make_function_type(NULL, NULL, results, loc);
     methods->push_back(Typed_identifier("Error", method_type, loc));
-    Type *error_iface = Type::make_interface_type(methods, loc);
+    Interface_type *error_iface = Type::make_interface_type(methods, loc);
+    error_iface->finalize_methods();
     Named_type *error_type = Named_object::make_type("error", NULL, error_iface, loc)->type_value();
     this->add_named_type(error_type);
   }
@@ -175,7 +176,7 @@ Gogo::Gogo(Backend* backend, Linemap* linemap, int int_type_size,
   print_type->set_is_builtin();
   this->globals_->add_function_declaration("println", NULL, print_type, loc);
 
-  Type *empty = Type::make_interface_type(NULL, loc);
+  Type *empty = Type::make_empty_interface_type(loc);
   Typed_identifier_list* panic_parms = new Typed_identifier_list();
   panic_parms->push_back(Typed_identifier("e", empty, loc));
   Function_type *panic_type = Type::make_function_type(NULL, panic_parms,
@@ -1564,7 +1565,8 @@ Finalize_methods::type(Type* t)
 	// finalize the methods of the field types, not of the struct
 	// type itself.  We don't want to add methods to the struct,
 	// since it has a name.
-	Type* rt = t->named_type()->real_type();
+	Named_type* nt = t->named_type();
+	Type* rt = nt->real_type();
 	if (rt->classification() != Type::TYPE_STRUCT)
 	  {
 	    if (Type::traverse(rt, this) == TRAVERSE_EXIT)
@@ -1576,7 +1578,21 @@ Finalize_methods::type(Type* t)
 	      return TRAVERSE_EXIT;
 	  }
 
-	t->named_type()->finalize_methods(this->gogo_);
+	nt->finalize_methods(this->gogo_);
+
+	// If this type is defined in a different package, then finalize the
+	// types of all the methods, since we won't see them otherwise.
+	if (nt->named_object()->package() != NULL && nt->has_any_methods())
+	  {
+	    const Methods* methods = nt->methods();
+	    for (Methods::const_iterator p = methods->begin();
+		 p != methods->end();
+		 ++p)
+	      {
+		if (Type::traverse(p->second->type(), this) == TRAVERSE_EXIT)
+		  return TRAVERSE_EXIT;
+	      }
+	  }
 
 	return TRAVERSE_SKIP_COMPONENTS;
       }
@@ -2622,6 +2638,9 @@ class Build_method_tables : public Traverse
 void
 Gogo::build_interface_method_tables()
 {
+  if (saw_errors())
+    return;
+
   std::vector<Interface_type*> hidden_interfaces;
   hidden_interfaces.reserve(this->interface_types_.size());
   for (std::vector<Interface_type*>::const_iterator pi =
@@ -4922,10 +4941,7 @@ Bindings::traverse(Traverse* traverse, bool is_global)
 		     | Traverse::traverse_statements
 		     | Traverse::traverse_expressions
 		     | Traverse::traverse_types)) != 0)
-	    {
-	      if (p->func_value()->traverse(traverse) == TRAVERSE_EXIT)
-		return TRAVERSE_EXIT;
-	    }
+	    t = p->func_value()->traverse(traverse);
 	  break;
 
 	case Named_object::NAMED_OBJECT_PACKAGE:
@@ -4952,6 +4968,26 @@ Bindings::traverse(Traverse* traverse, bool is_global)
 	return TRAVERSE_EXIT;
     }
 
+  // If we need to traverse types, check the function declarations,
+  // which have types.  We don't need to check the type declarations,
+  // as those are just names.
+  if ((traverse_mask & e_or_t) != 0)
+    {
+      for (Bindings::const_declarations_iterator p =
+	     this->begin_declarations();
+	   p != this->end_declarations();
+	   ++p)
+	{
+	  if (p->second->is_function_declaration())
+	    {
+	      if (Type::traverse(p->second->func_declaration_value()->type(),
+				 traverse)
+		  == TRAVERSE_EXIT)
+		return TRAVERSE_EXIT;
+	    }
+	}
+    }
+
   return TRAVERSE_CONTINUE;
 }
 
@@ -5090,9 +5126,12 @@ Traverse::remember_type(const Type* type)
     return true;
   go_assert((this->traverse_mask() & traverse_types) != 0
 	     || (this->traverse_mask() & traverse_expressions) != 0);
-  // We only have to remember named types, as they are the only ones
-  // we can see multiple times in a traversal.
-  if (type->classification() != Type::TYPE_NAMED)
+  // We mostly only have to remember named types.  But it turns out
+  // that an interface type can refer to itself without using a name
+  // by relying on interface inheritance, as in
+  // type I interface { F() interface{I} }
+  if (type->classification() != Type::TYPE_NAMED
+      && type->classification() != Type::TYPE_INTERFACE)
     return false;
   if (this->types_seen_ == NULL)
     this->types_seen_ = new Types_seen();
diff --git a/gcc/go/gofrontend/gogo.h b/gcc/go/gofrontend/gogo.h
index ac1707a..1042f03 100644
--- a/gcc/go/gofrontend/gogo.h
+++ b/gcc/go/gofrontend/gogo.h
@@ -2578,8 +2578,13 @@ class Traverse
   type(Type*);
 
  private:
-  typedef Unordered_set_hash(const Type*, Type_hash_identical,
-			     Type_identical) Types_seen;
+  // A hash table for types we have seen during this traversal.  Note
+  // that this uses the default hash functions for pointers rather
+  // than Type_hash_identical and Type_identical.  This is because for
+  // traversal we care about seeing a specific type structure.  If
+  // there are two separate instances of identical types, we want to
+  // traverse both.
+  typedef Unordered_set(const Type*) Types_seen;
 
   typedef Unordered_set(const Expression*) Expressions_seen;
 
diff --git a/gcc/go/gofrontend/runtime.cc b/gcc/go/gofrontend/runtime.cc
index bffefbb..7893d45 100644
--- a/gcc/go/gofrontend/runtime.cc
+++ b/gcc/go/gofrontend/runtime.cc
@@ -151,12 +151,14 @@ runtime_function_type(Runtime_function_type bft)
 	    Typed_identifier_list* methods = new Typed_identifier_list();
 	    Type* mtype = Type::make_function_type(NULL, NULL, NULL, bloc);
 	    methods->push_back(Typed_identifier("x", mtype, bloc));
-	    t = Type::make_interface_type(methods, bloc);
+	    Interface_type* it = Type::make_interface_type(methods, bloc);
+	    it->finalize_methods();
+	    t = it;
 	  }
 	  break;
 
 	case RFT_EFACE:
-	  t = Type::make_interface_type(NULL, bloc);
+	  t = Type::make_empty_interface_type(bloc);
 	  break;
 
 	case RFT_FUNC_PTR:
diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc
index 055bd67..3572e1d 100644
--- a/gcc/go/gofrontend/types.cc
+++ b/gcc/go/gofrontend/types.cc
@@ -6148,9 +6148,12 @@ Type::make_channel_type(bool send, bool receive, Type* element_type)
 int
 Interface_type::do_traverse(Traverse* traverse)
 {
-  if (this->methods_ == NULL)
+  Typed_identifier_list* methods = (this->methods_are_finalized_
+				    ? this->all_methods_
+				    : this->parse_methods_);
+  if (methods == NULL)
     return TRAVERSE_CONTINUE;
-  return this->methods_->traverse(traverse);
+  return methods->traverse(traverse);
 }
 
 // Finalize the methods.  This handles interface inheritance.
@@ -6158,56 +6161,57 @@ Interface_type::do_traverse(Traverse* traverse)
 void
 Interface_type::finalize_methods()
 {
-  if (this->methods_ == NULL)
+  if (this->methods_are_finalized_)
+    return;
+  this->methods_are_finalized_ = true;
+  if (this->parse_methods_ == NULL)
     return;
+
+  this->all_methods_ = new Typed_identifier_list();
+  this->all_methods_->reserve(this->parse_methods_->size());
+  Typed_identifier_list inherit;
+  for (Typed_identifier_list::const_iterator pm =
+	 this->parse_methods_->begin();
+       pm != this->parse_methods_->end();
+       ++pm)
+    {
+      const Typed_identifier* p = &*pm;
+      if (p->name().empty())
+	inherit.push_back(*p);
+      else if (this->find_method(p->name()) == NULL)
+	this->all_methods_->push_back(*p);
+      else
+	error_at(p->location(), "duplicate method %qs",
+		 Gogo::message_name(p->name()).c_str());
+    }
+
   std::vector<Named_type*> seen;
-  bool is_recursive = false;
-  size_t from = 0;
-  size_t to = 0;
-  while (from < this->methods_->size())
+  seen.reserve(inherit.size());
+  bool issued_recursive_error = false;
+  while (!inherit.empty())
     {
-      const Typed_identifier* p = &this->methods_->at(from);
-      if (!p->name().empty())
-	{
-	  size_t i;
-	  for (i = 0; i < to; ++i)
-	    {
-	      if (this->methods_->at(i).name() == p->name())
-		{
-		  error_at(p->location(), "duplicate method %qs",
-			   Gogo::message_name(p->name()).c_str());
-		  break;
-		}
-	    }
-	  if (i == to)
-	    {
-	      if (from != to)
-		this->methods_->set(to, *p);
-	      ++to;
-	    }
-	  ++from;
-	  continue;
-	}
+      Type* t = inherit.back().type();
+      Location tl = inherit.back().location();
+      inherit.pop_back();
 
-      Interface_type* it = p->type()->interface_type();
+      Interface_type* it = t->interface_type();
       if (it == NULL)
 	{
-	  error_at(p->location(), "interface contains embedded non-interface");
-	  ++from;
+	  if (!t->is_error())
+	    error_at(tl, "interface contains embedded non-interface");
 	  continue;
 	}
       if (it == this)
 	{
-	  if (!is_recursive)
+	  if (!issued_recursive_error)
 	    {
-	      error_at(p->location(), "invalid recursive interface");
-	      is_recursive = true;
+	      error_at(tl, "invalid recursive interface");
+	      issued_recursive_error = true;
 	    }
-	  ++from;
 	  continue;
 	}
 
-      Named_type* nt = p->type()->named_type();
+      Named_type* nt = t->named_type();
       if (nt != NULL)
 	{
 	  std::vector<Named_type*>::const_iterator q;
@@ -6215,73 +6219,39 @@ Interface_type::finalize_methods()
 	    {
 	      if (*q == nt)
 		{
-		  error_at(p->location(), "inherited interface loop");
+		  error_at(tl, "inherited interface loop");
 		  break;
 		}
 	    }
 	  if (q != seen.end())
-	    {
-	      ++from;
-	      continue;
-	    }
+	    continue;
 	  seen.push_back(nt);
 	}
 
-      const Typed_identifier_list* methods = it->methods();
-      if (methods == NULL)
-	{
-	  ++from;
-	  continue;
-	}
-      for (Typed_identifier_list::const_iterator q = methods->begin();
-	   q != methods->end();
+      const Typed_identifier_list* imethods = it->parse_methods_;
+      if (imethods == NULL)
+	continue;
+      for (Typed_identifier_list::const_iterator q = imethods->begin();
+	   q != imethods->end();
 	   ++q)
 	{
 	  if (q->name().empty())
-	    {
-	      if (q->type()->forwarded() == p->type()->forwarded())
-		error_at(p->location(), "interface inheritance loop");
-	      else
-		{
-		  size_t i;
-		  for (i = from + 1; i < this->methods_->size(); ++i)
-		    {
-		      const Typed_identifier* r = &this->methods_->at(i);
-		      if (r->name().empty()
-			  && r->type()->forwarded() == q->type()->forwarded())
-			{
-			  error_at(p->location(),
-				   "inherited interface listed twice");
-			  break;
-			}
-		    }
-		  if (i == this->methods_->size())
-		    this->methods_->push_back(Typed_identifier(q->name(),
-							       q->type(),
-							       p->location()));
-		}
-	    }
+	    inherit.push_back(*q);
 	  else if (this->find_method(q->name()) == NULL)
-	    this->methods_->push_back(Typed_identifier(q->name(), q->type(),
-						       p->location()));
+	    this->all_methods_->push_back(Typed_identifier(q->name(),
+							   q->type(), tl));
 	  else
-	    {
-	      if (!is_recursive)
-		error_at(p->location(), "inherited method %qs is ambiguous",
-			 Gogo::message_name(q->name()).c_str());
-	    }
+	    error_at(tl, "inherited method %qs is ambiguous",
+		     Gogo::message_name(q->name()).c_str());
 	}
-      ++from;
-    }
-  if (to == 0)
-    {
-      delete this->methods_;
-      this->methods_ = NULL;
     }
+
+  if (!this->all_methods_->empty())
+    this->all_methods_->sort_by_name();
   else
     {
-      this->methods_->resize(to);
-      this->methods_->sort_by_name();
+      delete this->all_methods_;
+      this->all_methods_ = NULL;
     }
 }
 
@@ -6290,10 +6260,11 @@ Interface_type::finalize_methods()
 const Typed_identifier*
 Interface_type::find_method(const std::string& name) const
 {
-  if (this->methods_ == NULL)
+  go_assert(this->methods_are_finalized_);
+  if (this->all_methods_ == NULL)
     return NULL;
-  for (Typed_identifier_list::const_iterator p = this->methods_->begin();
-       p != this->methods_->end();
+  for (Typed_identifier_list::const_iterator p = this->all_methods_->begin();
+       p != this->all_methods_->end();
        ++p)
     if (p->name() == name)
       return &*p;
@@ -6305,10 +6276,10 @@ Interface_type::find_method(const std::string& name) const
 size_t
 Interface_type::method_index(const std::string& name) const
 {
-  go_assert(this->methods_ != NULL);
+  go_assert(this->methods_are_finalized_ && this->all_methods_ != NULL);
   size_t ret = 0;
-  for (Typed_identifier_list::const_iterator p = this->methods_->begin();
-       p != this->methods_->end();
+  for (Typed_identifier_list::const_iterator p = this->all_methods_->begin();
+       p != this->all_methods_->end();
        ++p, ++ret)
     if (p->name() == name)
       return ret;
@@ -6321,10 +6292,11 @@ Interface_type::method_index(const std::string& name) const
 bool
 Interface_type::is_unexported_method(Gogo* gogo, const std::string& name) const
 {
-  if (this->methods_ == NULL)
+  go_assert(this->methods_are_finalized_);
+  if (this->all_methods_ == NULL)
     return false;
-  for (Typed_identifier_list::const_iterator p = this->methods_->begin();
-       p != this->methods_->end();
+  for (Typed_identifier_list::const_iterator p = this->all_methods_->begin();
+       p != this->all_methods_->end();
        ++p)
     {
       const std::string& method_name(p->name());
@@ -6342,26 +6314,53 @@ bool
 Interface_type::is_identical(const Interface_type* t,
 			     bool errors_are_identical) const
 {
+  go_assert(this->methods_are_finalized_ && t->methods_are_finalized_);
+
   // We require the same methods with the same types.  The methods
   // have already been sorted.
-  if (this->methods() == NULL || t->methods() == NULL)
-    return this->methods() == t->methods();
+  if (this->all_methods_ == NULL || t->all_methods_ == NULL)
+    return this->all_methods_ == t->all_methods_;
+
+  if (this->assume_identical(this, t) || t->assume_identical(t, this))
+    return true;
 
-  Typed_identifier_list::const_iterator p1 = this->methods()->begin();
-  for (Typed_identifier_list::const_iterator p2 = t->methods()->begin();
-       p2 != t->methods()->end();
-       ++p1, ++p2)
+  Assume_identical* hold_ai = this->assume_identical_;
+  Assume_identical ai;
+  ai.t1 = this;
+  ai.t2 = t;
+  ai.next = hold_ai;
+  this->assume_identical_ = &ai;
+
+  Typed_identifier_list::const_iterator p1 = this->all_methods_->begin();
+  Typed_identifier_list::const_iterator p2;
+  for (p2 = t->all_methods_->begin(); p2 != t->all_methods_->end(); ++p1, ++p2)
     {
-      if (p1 == this->methods()->end())
-	return false;
+      if (p1 == this->all_methods_->end())
+	break;
       if (p1->name() != p2->name()
 	  || !Type::are_identical(p1->type(), p2->type(),
 				  errors_are_identical, NULL))
-	return false;
+	break;
     }
-  if (p1 != this->methods()->end())
-    return false;
-  return true;
+
+  this->assume_identical_ = hold_ai;
+
+  return p1 == this->all_methods_->end() && p2 == t->all_methods_->end();
+}
+
+// Return true if T1 and T2 are assumed to be identical during a type
+// comparison.
+
+bool
+Interface_type::assume_identical(const Interface_type* t1,
+				 const Interface_type* t2) const
+{
+  for (Assume_identical* p = this->assume_identical_;
+       p != NULL;
+       p = p->next)
+    if ((p->t1 == t1 && p->t2 == t2) || (p->t1 == t2 && p->t2 == t1))
+      return true;
+  return false;
 }
 
 // Whether we can assign the interface type T to this type.  The types
@@ -6373,10 +6372,11 @@ bool
 Interface_type::is_compatible_for_assign(const Interface_type* t,
 					 std::string* reason) const
 {
-  if (this->methods() == NULL)
+  go_assert(this->methods_are_finalized_ && t->methods_are_finalized_);
+  if (this->all_methods_ == NULL)
     return true;
-  for (Typed_identifier_list::const_iterator p = this->methods()->begin();
-       p != this->methods()->end();
+  for (Typed_identifier_list::const_iterator p = this->all_methods_->begin();
+       p != this->all_methods_->end();
        ++p)
     {
       const Typed_identifier* m = t->find_method(p->name());
@@ -6423,17 +6423,23 @@ Interface_type::is_compatible_for_assign(const Interface_type* t,
 // Hash code.
 
 unsigned int
-Interface_type::do_hash_for_method(Gogo* gogo) const
+Interface_type::do_hash_for_method(Gogo*) const
 {
+  go_assert(this->methods_are_finalized_);
   unsigned int ret = 0;
-  if (this->methods_ != NULL)
+  if (this->all_methods_ != NULL)
     {
-      for (Typed_identifier_list::const_iterator p = this->methods_->begin();
-	   p != this->methods_->end();
+      for (Typed_identifier_list::const_iterator p =
+	     this->all_methods_->begin();
+	   p != this->all_methods_->end();
 	   ++p)
 	{
 	  ret = Type::hash_string(p->name(), ret);
-	  ret += p->type()->hash_for_method(gogo);
+	  // We don't use the method type in the hash, to avoid
+	  // infinite recursion if an interface method uses a type
+	  // which is an interface which inherits from the interface
+	  // itself.
+	  // type T interface { F() interface {T}}
 	  ret <<= 1;
 	}
     }
@@ -6446,7 +6452,8 @@ Interface_type::do_hash_for_method(Gogo* gogo) const
 bool
 Interface_type::implements_interface(const Type* t, std::string* reason) const
 {
-  if (this->methods_ == NULL)
+  go_assert(this->methods_are_finalized_);
+  if (this->all_methods_ == NULL)
     return true;
 
   bool is_pointer = false;
@@ -6499,8 +6506,8 @@ Interface_type::implements_interface(const Type* t, std::string* reason) const
       return false;
     }
 
-  for (Typed_identifier_list::const_iterator p = this->methods_->begin();
-       p != this->methods_->end();
+  for (Typed_identifier_list::const_iterator p = this->all_methods_->begin();
+       p != this->all_methods_->end();
        ++p)
     {
       bool is_ambiguous = false;
@@ -6653,13 +6660,20 @@ get_backend_interface_fields(Gogo* gogo, Interface_type* type,
 Btype*
 Interface_type::do_get_backend(Gogo* gogo)
 {
-  if (this->methods_ == NULL)
+  if (this->is_empty())
     return Interface_type::get_backend_empty_interface_type(gogo);
   else
     {
+      if (this->interface_btype_ != NULL)
+	return this->interface_btype_;
+      this->interface_btype_ =
+	gogo->backend()->placeholder_struct_type("", this->location_);
       std::vector<Backend::Btyped_identifier> bfields;
       get_backend_interface_fields(gogo, this, &bfields);
-      return gogo->backend()->struct_type(bfields);
+      if (!gogo->backend()->set_placeholder_struct_type(this->interface_btype_,
+							bfields))
+	this->interface_btype_ = gogo->backend()->error_type();
+      return this->interface_btype_;
     }
 }
 
@@ -6721,13 +6735,14 @@ Interface_type::do_type_descriptor(Gogo* gogo, Named_type* name)
   go_assert(pif->is_field_name("methods"));
 
   Expression_list* methods = new Expression_list();
-  if (this->methods_ != NULL && !this->methods_->empty())
+  if (this->all_methods_ != NULL)
     {
       Type* elemtype = pif->type()->array_type()->element_type();
 
-      methods->reserve(this->methods_->size());
-      for (Typed_identifier_list::const_iterator pm = this->methods_->begin();
-	   pm != this->methods_->end();
+      methods->reserve(this->all_methods_->size());
+      for (Typed_identifier_list::const_iterator pm =
+	     this->all_methods_->begin();
+	   pm != this->all_methods_->end();
 	   ++pm)
 	{
 	  const Struct_field_list* mfields = elemtype->struct_type()->fields();
@@ -6780,29 +6795,35 @@ void
 Interface_type::do_reflection(Gogo* gogo, std::string* ret) const
 {
   ret->append("interface {");
-  if (this->methods_ != NULL)
+  const Typed_identifier_list* methods = this->parse_methods_;
+  if (methods != NULL)
     {
       ret->push_back(' ');
-      for (Typed_identifier_list::const_iterator p = this->methods_->begin();
-	   p != this->methods_->end();
+      for (Typed_identifier_list::const_iterator p = methods->begin();
+	   p != methods->end();
 	   ++p)
 	{
-	  if (p != this->methods_->begin())
+	  if (p != methods->begin())
 	    ret->append("; ");
-	  if (!Gogo::is_hidden_name(p->name()))
-	    ret->append(p->name());
+	  if (p->name().empty())
+	    this->append_reflection(p->type(), gogo, ret);
 	  else
 	    {
-	      // This matches what the gc compiler does.
-	      std::string prefix = Gogo::hidden_name_prefix(p->name());
-	      ret->append(prefix.substr(prefix.find('.') + 1));
-	      ret->push_back('.');
-	      ret->append(Gogo::unpack_hidden_name(p->name()));
+	      if (!Gogo::is_hidden_name(p->name()))
+		ret->append(p->name());
+	      else
+		{
+		  // This matches what the gc compiler does.
+		  std::string prefix = Gogo::hidden_name_prefix(p->name());
+		  ret->append(prefix.substr(prefix.find('.') + 1));
+		  ret->push_back('.');
+		  ret->append(Gogo::unpack_hidden_name(p->name()));
+		}
+	      std::string sub = p->type()->reflection(gogo);
+	      go_assert(sub.compare(0, 4, "func") == 0);
+	      sub = sub.substr(4);
+	      ret->append(sub);
 	    }
-	  std::string sub = p->type()->reflection(gogo);
-	  go_assert(sub.compare(0, 4, "func") == 0);
-	  sub = sub.substr(4);
-	  ret->append(sub);
 	}
       ret->push_back(' ');
     }
@@ -6814,23 +6835,30 @@ Interface_type::do_reflection(Gogo* gogo, std::string* ret) const
 void
 Interface_type::do_mangled_name(Gogo* gogo, std::string* ret) const
 {
+  go_assert(this->methods_are_finalized_);
+
   ret->push_back('I');
 
-  const Typed_identifier_list* methods = this->methods_;
-  if (methods != NULL)
+  const Typed_identifier_list* methods = this->all_methods_;
+  if (methods != NULL && !this->seen_)
     {
+      this->seen_ = true;
       for (Typed_identifier_list::const_iterator p = methods->begin();
 	   p != methods->end();
 	   ++p)
 	{
-	  std::string n = Gogo::unpack_hidden_name(p->name());
-	  char buf[20];
-	  snprintf(buf, sizeof buf, "%u_",
-		   static_cast<unsigned int>(n.length()));
-	  ret->append(buf);
-	  ret->append(n);
+	  if (!p->name().empty())
+	    {
+	      std::string n = Gogo::unpack_hidden_name(p->name());
+	      char buf[20];
+	      snprintf(buf, sizeof buf, "%u_",
+		       static_cast<unsigned int>(n.length()));
+	      ret->append(buf);
+	      ret->append(n);
+	    }
 	  this->append_mangled_name(p->type(), gogo, ret);
 	}
+      this->seen_ = false;
     }
 
   ret->push_back('e');
@@ -6843,67 +6871,75 @@ Interface_type::do_export(Export* exp) const
 {
   exp->write_c_string("interface { ");
 
-  const Typed_identifier_list* methods = this->methods_;
+  const Typed_identifier_list* methods = this->parse_methods_;
   if (methods != NULL)
     {
       for (Typed_identifier_list::const_iterator pm = methods->begin();
 	   pm != methods->end();
 	   ++pm)
 	{
-	  exp->write_string(pm->name());
-	  exp->write_c_string(" (");
-
-	  const Function_type* fntype = pm->type()->function_type();
-
-	  bool first = true;
-	  const Typed_identifier_list* parameters = fntype->parameters();
-	  if (parameters != NULL)
+	  if (pm->name().empty())
 	    {
-	      bool is_varargs = fntype->is_varargs();
-	      for (Typed_identifier_list::const_iterator pp =
-		     parameters->begin();
-		   pp != parameters->end();
-		   ++pp)
-		{
-		  if (first)
-		    first = false;
-		  else
-		    exp->write_c_string(", ");
-		  if (!is_varargs || pp + 1 != parameters->end())
-		    exp->write_type(pp->type());
-		  else
-		    {
-		      exp->write_c_string("...");
-		      Type *pptype = pp->type();
-		      exp->write_type(pptype->array_type()->element_type());
-		    }
-		}
+	      exp->write_c_string("$ ");
+	      exp->write_type(pm->type());
 	    }
+	  else
+	    {
+	      exp->write_string(pm->name());
+	      exp->write_c_string(" (");
 
-	  exp->write_c_string(")");
+	      const Function_type* fntype = pm->type()->function_type();
 
-	  const Typed_identifier_list* results = fntype->results();
-	  if (results != NULL)
-	    {
-	      exp->write_c_string(" ");
-	      if (results->size() == 1)
-		exp->write_type(results->begin()->type());
-	      else
+	      bool first = true;
+	      const Typed_identifier_list* parameters = fntype->parameters();
+	      if (parameters != NULL)
 		{
-		  first = true;
-		  exp->write_c_string("(");
-		  for (Typed_identifier_list::const_iterator p =
-			 results->begin();
-		       p != results->end();
-		       ++p)
+		  bool is_varargs = fntype->is_varargs();
+		  for (Typed_identifier_list::const_iterator pp =
+			 parameters->begin();
+		       pp != parameters->end();
+		       ++pp)
 		    {
 		      if (first)
 			first = false;
 		      else
 			exp->write_c_string(", ");
-		      exp->write_type(p->type());
+		      if (!is_varargs || pp + 1 != parameters->end())
+			exp->write_type(pp->type());
+		      else
+			{
+			  exp->write_c_string("...");
+			  Type *pptype = pp->type();
+			  exp->write_type(pptype->array_type()->element_type());
+			}
+		    }
+		}
+
+	      exp->write_c_string(")");
+
+	      const Typed_identifier_list* results = fntype->results();
+	      if (results != NULL)
+		{
+		  exp->write_c_string(" ");
+		  if (results->size() == 1)
+		    exp->write_type(results->begin()->type());
+		  else
+		    {
+		      first = true;
+		      exp->write_c_string("(");
+		      for (Typed_identifier_list::const_iterator p =
+			     results->begin();
+			   p != results->end();
+			   ++p)
+			{
+			  if (first)
+			    first = false;
+			  else
+			    exp->write_c_string(", ");
+			  exp->write_type(p->type());
+			}
+		      exp->write_c_string(")");
 		    }
-		  exp->write_c_string(")");
 		}
 	    }
 
@@ -6925,6 +6961,16 @@ Interface_type::do_import(Import* imp)
   while (imp->peek_char() != '}')
     {
       std::string name = imp->read_identifier();
+
+      if (name == "$")
+	{
+	  imp->require_c_string(" ");
+	  Type* t = imp->read_type();
+	  methods->push_back(Typed_identifier("", t, imp->location()));
+	  imp->require_c_string("; ");
+	  continue;
+	}
+
       imp->require_c_string(" (");
 
       Typed_identifier_list* parameters;
@@ -7014,6 +7060,16 @@ Type::make_interface_type(Typed_identifier_list* methods,
   return new Interface_type(methods, location);
 }
 
+// Make an empty interface type.
+
+Interface_type*
+Type::make_empty_interface_type(Location location)
+{
+  Interface_type* ret = new Interface_type(NULL, location);
+  ret->finalize_methods();
+  return ret;
+}
+
 // Class Method.
 
 // Bind a method to an object.
diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h
index afb8a41..b167451 100644
--- a/gcc/go/gofrontend/types.h
+++ b/gcc/go/gofrontend/types.h
@@ -485,6 +485,9 @@ class Type
   static Interface_type*
   make_interface_type(Typed_identifier_list* methods, Location);
 
+  static Interface_type*
+  make_empty_interface_type(Location);
+
   static Type*
   make_type_descriptor_type();
 
@@ -1319,6 +1322,10 @@ class Typed_identifier_list
                                               Linemap::unknown_location()));
   }
 
+  void
+  reserve(size_t c)
+  { this->entries_.reserve(c); }
+
   // Iterators.
 
   typedef std::vector<Typed_identifier>::iterator iterator;
@@ -2429,7 +2436,9 @@ class Interface_type : public Type
  public:
   Interface_type(Typed_identifier_list* methods, Location location)
     : Type(TYPE_INTERFACE),
-      methods_(methods), location_(location)
+      parse_methods_(methods), all_methods_(NULL), location_(location),
+      interface_btype_(NULL), assume_identical_(NULL),
+      methods_are_finalized_(false), seen_(false)
   { go_assert(methods == NULL || !methods->empty()); }
 
   // The location where the interface type was defined.
@@ -2440,18 +2449,27 @@ class Interface_type : public Type
   // Return whether this is an empty interface.
   bool
   is_empty() const
-  { return this->methods_ == NULL; }
+  {
+    go_assert(this->methods_are_finalized_);
+    return this->all_methods_ == NULL;
+  }
 
   // Return the list of methods.  This will return NULL for an empty
   // interface.
   const Typed_identifier_list*
   methods() const
-  { return this->methods_; }
+  {
+    go_assert(this->methods_are_finalized_);
+    return this->all_methods_;
+  }
 
   // Return the number of methods.
   size_t
   method_count() const
-  { return this->methods_ == NULL ? 0 : this->methods_->size(); }
+  {
+    go_assert(this->methods_are_finalized_);
+    return this->all_methods_ == NULL ? 0 : this->all_methods_->size();
+  }
 
   // Return the method NAME, or NULL.
   const Typed_identifier*
@@ -2461,7 +2479,8 @@ class Interface_type : public Type
   size_t
   method_index(const std::string& name) const;
 
-  // Finalize the methods.  This handles interface inheritance.
+  // Finalize the methods.  This sets all_methods_.  This handles
+  // interface inheritance.
   void
   finalize_methods();
 
@@ -2528,11 +2547,41 @@ class Interface_type : public Type
   do_export(Export*) const;
 
  private:
-  // The list of methods associated with the interface.  This will be
-  // NULL for the empty interface.
-  Typed_identifier_list* methods_;
+  // This type guards against infinite recursion when comparing
+  // interface types.  We keep a list of interface types assumed to be
+  // identical during comparison.  We just keep the list on the stack.
+  // This permits us to compare cases like
+  // type I1 interface { F() interface{I1} }
+  // type I2 interface { F() interface{I2} }
+  struct Assume_identical
+  {
+    Assume_identical* next;
+    const Interface_type* t1;
+    const Interface_type* t2;
+  };
+
+  bool
+  assume_identical(const Interface_type*, const Interface_type*) const;
+
+  // The list of methods associated with the interface from the
+  // parser.  This will be NULL for the empty interface.  This may
+  // include unnamed interface types.
+  Typed_identifier_list* parse_methods_;
+  // The list of all methods associated with the interface.  This
+  // expands any interface types listed in methods_.  It is set by
+  // finalize_methods.  This will be NULL for the empty interface.
+  Typed_identifier_list* all_methods_;
   // The location where the interface was defined.
   Location location_;
+  // The backend representation of this type during backend conversion.
+  Btype* interface_btype_;
+  // A list of interface types assumed to be identical during
+  // interface comparison.
+  mutable Assume_identical* assume_identical_;
+  // Whether the methods have been finalized.
+  bool methods_are_finalized_;
+  // Used to avoid endless recursion in do_mangled_name.
+  mutable bool seen_;
 };
 
 // The value we keep for a named type.  This lets us get the right
diff --git a/gcc/go/gofrontend/unsafe.cc b/gcc/go/gofrontend/unsafe.cc
index eb9462e..6e8a404 100644
--- a/gcc/go/gofrontend/unsafe.cc
+++ b/gcc/go/gofrontend/unsafe.cc
@@ -87,7 +87,7 @@ Gogo::import_unsafe(const std::string& local_name, bool is_local_name_exported,
     this->add_named_object(no);
 
   // Typeof.
-  Type* empty_interface = Type::make_interface_type(NULL, bloc);
+  Type* empty_interface = Type::make_empty_interface_type(bloc);
   Typed_identifier_list* parameters = new Typed_identifier_list;
   parameters->push_back(Typed_identifier("i", empty_interface, bloc));
   results = new Typed_identifier_list;
diff --git a/gcc/testsuite/go.test/test/fixedbugs/bug195.go b/gcc/testsuite/go.test/test/fixedbugs/bug195.go
index 65ab02a..d8e112a 100644
--- a/gcc/testsuite/go.test/test/fixedbugs/bug195.go
+++ b/gcc/testsuite/go.test/test/fixedbugs/bug195.go
@@ -23,5 +23,5 @@ type I5 interface {
 }
 
 type I6 interface {
-	I5	// GC_ERROR "interface"
+	I5	// ERROR "interface"
 }
diff --git a/gcc/testsuite/go.test/test/fixedbugs/bug251.go b/gcc/testsuite/go.test/test/fixedbugs/bug251.go
index c94ad2a..fb7b98a 100644
--- a/gcc/testsuite/go.test/test/fixedbugs/bug251.go
+++ b/gcc/testsuite/go.test/test/fixedbugs/bug251.go
@@ -12,7 +12,7 @@ type I1 interface {
 }
 
 type I2 interface {
-	I1 // GC_ERROR "loop|interface"
+	I1 // ERROR "loop|interface"
 }