OSDN Git Service

compiler: Don't check for hidden fields on struct assignments.
[pf3gnuchains/gcc-fork.git] / gcc / go / gofrontend / types.cc
1 // types.cc -- Go frontend types.
2
3 // Copyright 2009 The Go Authors. All rights reserved.
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file.
6
7 #include "go-system.h"
8
9 #include <gmp.h>
10
11 #ifndef ENABLE_BUILD_WITH_CXX
12 extern "C"
13 {
14 #endif
15
16 #include "toplev.h"
17 #include "intl.h"
18 #include "tree.h"
19 #include "gimple.h"
20 #include "real.h"
21 #include "convert.h"
22
23 #ifndef ENABLE_BUILD_WITH_CXX
24 }
25 #endif
26
27 #include "go-c.h"
28 #include "gogo.h"
29 #include "operator.h"
30 #include "expressions.h"
31 #include "statements.h"
32 #include "export.h"
33 #include "import.h"
34 #include "backend.h"
35 #include "types.h"
36
37 // Class Type.
38
39 Type::Type(Type_classification classification)
40   : classification_(classification), btype_(NULL), type_descriptor_var_(NULL)
41 {
42 }
43
44 Type::~Type()
45 {
46 }
47
48 // Get the base type for a type--skip names and forward declarations.
49
50 Type*
51 Type::base()
52 {
53   switch (this->classification_)
54     {
55     case TYPE_NAMED:
56       return this->named_type()->named_base();
57     case TYPE_FORWARD:
58       return this->forward_declaration_type()->real_type()->base();
59     default:
60       return this;
61     }
62 }
63
64 const Type*
65 Type::base() const
66 {
67   switch (this->classification_)
68     {
69     case TYPE_NAMED:
70       return this->named_type()->named_base();
71     case TYPE_FORWARD:
72       return this->forward_declaration_type()->real_type()->base();
73     default:
74       return this;
75     }
76 }
77
78 // Skip defined forward declarations.
79
80 Type*
81 Type::forwarded()
82 {
83   Type* t = this;
84   Forward_declaration_type* ftype = t->forward_declaration_type();
85   while (ftype != NULL && ftype->is_defined())
86     {
87       t = ftype->real_type();
88       ftype = t->forward_declaration_type();
89     }
90   return t;
91 }
92
93 const Type*
94 Type::forwarded() const
95 {
96   const Type* t = this;
97   const Forward_declaration_type* ftype = t->forward_declaration_type();
98   while (ftype != NULL && ftype->is_defined())
99     {
100       t = ftype->real_type();
101       ftype = t->forward_declaration_type();
102     }
103   return t;
104 }
105
106 // If this is a named type, return it.  Otherwise, return NULL.
107
108 Named_type*
109 Type::named_type()
110 {
111   return this->forwarded()->convert_no_base<Named_type, TYPE_NAMED>();
112 }
113
114 const Named_type*
115 Type::named_type() const
116 {
117   return this->forwarded()->convert_no_base<const Named_type, TYPE_NAMED>();
118 }
119
120 // Return true if this type is not defined.
121
122 bool
123 Type::is_undefined() const
124 {
125   return this->forwarded()->forward_declaration_type() != NULL;
126 }
127
128 // Return true if this is a basic type: a type which is not composed
129 // of other types, and is not void.
130
131 bool
132 Type::is_basic_type() const
133 {
134   switch (this->classification_)
135     {
136     case TYPE_INTEGER:
137     case TYPE_FLOAT:
138     case TYPE_COMPLEX:
139     case TYPE_BOOLEAN:
140     case TYPE_STRING:
141     case TYPE_NIL:
142       return true;
143
144     case TYPE_ERROR:
145     case TYPE_VOID:
146     case TYPE_FUNCTION:
147     case TYPE_POINTER:
148     case TYPE_STRUCT:
149     case TYPE_ARRAY:
150     case TYPE_MAP:
151     case TYPE_CHANNEL:
152     case TYPE_INTERFACE:
153       return false;
154
155     case TYPE_NAMED:
156     case TYPE_FORWARD:
157       return this->base()->is_basic_type();
158
159     default:
160       go_unreachable();
161     }
162 }
163
164 // Return true if this is an abstract type.
165
166 bool
167 Type::is_abstract() const
168 {
169   switch (this->classification())
170     {
171     case TYPE_INTEGER:
172       return this->integer_type()->is_abstract();
173     case TYPE_FLOAT:
174       return this->float_type()->is_abstract();
175     case TYPE_COMPLEX:
176       return this->complex_type()->is_abstract();
177     case TYPE_STRING:
178       return this->is_abstract_string_type();
179     case TYPE_BOOLEAN:
180       return this->is_abstract_boolean_type();
181     default:
182       return false;
183     }
184 }
185
186 // Return a non-abstract version of an abstract type.
187
188 Type*
189 Type::make_non_abstract_type()
190 {
191   go_assert(this->is_abstract());
192   switch (this->classification())
193     {
194     case TYPE_INTEGER:
195       return Type::lookup_integer_type("int");
196     case TYPE_FLOAT:
197       return Type::lookup_float_type("float64");
198     case TYPE_COMPLEX:
199       return Type::lookup_complex_type("complex128");
200     case TYPE_STRING:
201       return Type::lookup_string_type();
202     case TYPE_BOOLEAN:
203       return Type::lookup_bool_type();
204     default:
205       go_unreachable();
206     }
207 }
208
209 // Return true if this is an error type.  Don't give an error if we
210 // try to dereference an undefined forwarding type, as this is called
211 // in the parser when the type may legitimately be undefined.
212
213 bool
214 Type::is_error_type() const
215 {
216   const Type* t = this->forwarded();
217   // Note that we return false for an undefined forward type.
218   switch (t->classification_)
219     {
220     case TYPE_ERROR:
221       return true;
222     case TYPE_NAMED:
223       return t->named_type()->is_named_error_type();
224     default:
225       return false;
226     }
227 }
228
229 // If this is a pointer type, return the type to which it points.
230 // Otherwise, return NULL.
231
232 Type*
233 Type::points_to() const
234 {
235   const Pointer_type* ptype = this->convert<const Pointer_type,
236                                             TYPE_POINTER>();
237   return ptype == NULL ? NULL : ptype->points_to();
238 }
239
240 // Return whether this is an open array type.
241
242 bool
243 Type::is_slice_type() const
244 {
245   return this->array_type() != NULL && this->array_type()->length() == NULL;
246 }
247
248 // Return whether this is the predeclared constant nil being used as a
249 // type.
250
251 bool
252 Type::is_nil_constant_as_type() const
253 {
254   const Type* t = this->forwarded();
255   if (t->forward_declaration_type() != NULL)
256     {
257       const Named_object* no = t->forward_declaration_type()->named_object();
258       if (no->is_unknown())
259         no = no->unknown_value()->real_named_object();
260       if (no != NULL
261           && no->is_const()
262           && no->const_value()->expr()->is_nil_expression())
263         return true;
264     }
265   return false;
266 }
267
268 // Traverse a type.
269
270 int
271 Type::traverse(Type* type, Traverse* traverse)
272 {
273   go_assert((traverse->traverse_mask() & Traverse::traverse_types) != 0
274              || (traverse->traverse_mask()
275                  & Traverse::traverse_expressions) != 0);
276   if (traverse->remember_type(type))
277     {
278       // We have already traversed this type.
279       return TRAVERSE_CONTINUE;
280     }
281   if ((traverse->traverse_mask() & Traverse::traverse_types) != 0)
282     {
283       int t = traverse->type(type);
284       if (t == TRAVERSE_EXIT)
285         return TRAVERSE_EXIT;
286       else if (t == TRAVERSE_SKIP_COMPONENTS)
287         return TRAVERSE_CONTINUE;
288     }
289   // An array type has an expression which we need to traverse if
290   // traverse_expressions is set.
291   if (type->do_traverse(traverse) == TRAVERSE_EXIT)
292     return TRAVERSE_EXIT;
293   return TRAVERSE_CONTINUE;
294 }
295
296 // Default implementation for do_traverse for child class.
297
298 int
299 Type::do_traverse(Traverse*)
300 {
301   return TRAVERSE_CONTINUE;
302 }
303
304 // Return whether two types are identical.  If ERRORS_ARE_IDENTICAL,
305 // then return true for all erroneous types; this is used to avoid
306 // cascading errors.  If REASON is not NULL, optionally set *REASON to
307 // the reason the types are not identical.
308
309 bool
310 Type::are_identical(const Type* t1, const Type* t2, bool errors_are_identical,
311                     std::string* reason)
312 {
313   if (t1 == NULL || t2 == NULL)
314     {
315       // Something is wrong.
316       return errors_are_identical ? true : t1 == t2;
317     }
318
319   // Skip defined forward declarations.
320   t1 = t1->forwarded();
321   t2 = t2->forwarded();
322
323   if (t1 == t2)
324     return true;
325
326   // An undefined forward declaration is an error.
327   if (t1->forward_declaration_type() != NULL
328       || t2->forward_declaration_type() != NULL)
329     return errors_are_identical;
330
331   // Avoid cascading errors with error types.
332   if (t1->is_error_type() || t2->is_error_type())
333     {
334       if (errors_are_identical)
335         return true;
336       return t1->is_error_type() && t2->is_error_type();
337     }
338
339   // Get a good reason for the sink type.  Note that the sink type on
340   // the left hand side of an assignment is handled in are_assignable.
341   if (t1->is_sink_type() || t2->is_sink_type())
342     {
343       if (reason != NULL)
344         *reason = "invalid use of _";
345       return false;
346     }
347
348   // A named type is only identical to itself.
349   if (t1->named_type() != NULL || t2->named_type() != NULL)
350     return false;
351
352   // Check type shapes.
353   if (t1->classification() != t2->classification())
354     return false;
355
356   switch (t1->classification())
357     {
358     case TYPE_VOID:
359     case TYPE_BOOLEAN:
360     case TYPE_STRING:
361     case TYPE_NIL:
362       // These types are always identical.
363       return true;
364
365     case TYPE_INTEGER:
366       return t1->integer_type()->is_identical(t2->integer_type());
367
368     case TYPE_FLOAT:
369       return t1->float_type()->is_identical(t2->float_type());
370
371     case TYPE_COMPLEX:
372       return t1->complex_type()->is_identical(t2->complex_type());
373
374     case TYPE_FUNCTION:
375       return t1->function_type()->is_identical(t2->function_type(),
376                                                false,
377                                                errors_are_identical,
378                                                reason);
379
380     case TYPE_POINTER:
381       return Type::are_identical(t1->points_to(), t2->points_to(),
382                                  errors_are_identical, reason);
383
384     case TYPE_STRUCT:
385       return t1->struct_type()->is_identical(t2->struct_type(),
386                                              errors_are_identical);
387
388     case TYPE_ARRAY:
389       return t1->array_type()->is_identical(t2->array_type(),
390                                             errors_are_identical);
391
392     case TYPE_MAP:
393       return t1->map_type()->is_identical(t2->map_type(),
394                                           errors_are_identical);
395
396     case TYPE_CHANNEL:
397       return t1->channel_type()->is_identical(t2->channel_type(),
398                                               errors_are_identical);
399
400     case TYPE_INTERFACE:
401       return t1->interface_type()->is_identical(t2->interface_type(),
402                                                 errors_are_identical);
403
404     case TYPE_CALL_MULTIPLE_RESULT:
405       if (reason != NULL)
406         *reason = "invalid use of multiple value function call";
407       return false;
408
409     default:
410       go_unreachable();
411     }
412 }
413
414 // Return true if it's OK to have a binary operation with types LHS
415 // and RHS.  This is not used for shifts or comparisons.
416
417 bool
418 Type::are_compatible_for_binop(const Type* lhs, const Type* rhs)
419 {
420   if (Type::are_identical(lhs, rhs, true, NULL))
421     return true;
422
423   // A constant of abstract bool type may be mixed with any bool type.
424   if ((rhs->is_abstract_boolean_type() && lhs->is_boolean_type())
425       || (lhs->is_abstract_boolean_type() && rhs->is_boolean_type()))
426     return true;
427
428   // A constant of abstract string type may be mixed with any string
429   // type.
430   if ((rhs->is_abstract_string_type() && lhs->is_string_type())
431       || (lhs->is_abstract_string_type() && rhs->is_string_type()))
432     return true;
433
434   lhs = lhs->base();
435   rhs = rhs->base();
436
437   // A constant of abstract integer, float, or complex type may be
438   // mixed with an integer, float, or complex type.
439   if ((rhs->is_abstract()
440        && (rhs->integer_type() != NULL
441            || rhs->float_type() != NULL
442            || rhs->complex_type() != NULL)
443        && (lhs->integer_type() != NULL
444            || lhs->float_type() != NULL
445            || lhs->complex_type() != NULL))
446       || (lhs->is_abstract()
447           && (lhs->integer_type() != NULL
448               || lhs->float_type() != NULL
449               || lhs->complex_type() != NULL)
450           && (rhs->integer_type() != NULL
451               || rhs->float_type() != NULL
452               || rhs->complex_type() != NULL)))
453     return true;
454
455   // The nil type may be compared to a pointer, an interface type, a
456   // slice type, a channel type, a map type, or a function type.
457   if (lhs->is_nil_type()
458       && (rhs->points_to() != NULL
459           || rhs->interface_type() != NULL
460           || rhs->is_slice_type()
461           || rhs->map_type() != NULL
462           || rhs->channel_type() != NULL
463           || rhs->function_type() != NULL))
464     return true;
465   if (rhs->is_nil_type()
466       && (lhs->points_to() != NULL
467           || lhs->interface_type() != NULL
468           || lhs->is_slice_type()
469           || lhs->map_type() != NULL
470           || lhs->channel_type() != NULL
471           || lhs->function_type() != NULL))
472     return true;
473
474   return false;
475 }
476
477 // Return true if a value with type RHS may be assigned to a variable
478 // with type LHS.  If CHECK_HIDDEN_FIELDS is true, check whether any
479 // hidden fields are modified.  If REASON is not NULL, set *REASON to
480 // the reason the types are not assignable.
481
482 bool
483 Type::are_assignable_check_hidden(const Type* lhs, const Type* rhs,
484                                   bool check_hidden_fields,
485                                   std::string* reason)
486 {
487   // Do some checks first.  Make sure the types are defined.
488   if (rhs != NULL
489       && rhs->forwarded()->forward_declaration_type() == NULL
490       && rhs->is_void_type())
491     {
492       if (reason != NULL)
493         *reason = "non-value used as value";
494       return false;
495     }
496
497   if (lhs != NULL && lhs->forwarded()->forward_declaration_type() == NULL)
498     {
499       // Any value may be assigned to the blank identifier.
500       if (lhs->is_sink_type())
501         return true;
502
503       // All fields of a struct must be exported, or the assignment
504       // must be in the same package.
505       if (check_hidden_fields
506           && rhs != NULL
507           && rhs->forwarded()->forward_declaration_type() == NULL)
508         {
509           if (lhs->has_hidden_fields(NULL, reason)
510               || rhs->has_hidden_fields(NULL, reason))
511             return false;
512         }
513     }
514
515   // Identical types are assignable.
516   if (Type::are_identical(lhs, rhs, true, reason))
517     return true;
518
519   // The types are assignable if they have identical underlying types
520   // and either LHS or RHS is not a named type.
521   if (((lhs->named_type() != NULL && rhs->named_type() == NULL)
522        || (rhs->named_type() != NULL && lhs->named_type() == NULL))
523       && Type::are_identical(lhs->base(), rhs->base(), true, reason))
524     return true;
525
526   // The types are assignable if LHS is an interface type and RHS
527   // implements the required methods.
528   const Interface_type* lhs_interface_type = lhs->interface_type();
529   if (lhs_interface_type != NULL)
530     {
531       if (lhs_interface_type->implements_interface(rhs, reason))
532         return true;
533       const Interface_type* rhs_interface_type = rhs->interface_type();
534       if (rhs_interface_type != NULL
535           && lhs_interface_type->is_compatible_for_assign(rhs_interface_type,
536                                                           reason))
537         return true;
538     }
539
540   // The type are assignable if RHS is a bidirectional channel type,
541   // LHS is a channel type, they have identical element types, and
542   // either LHS or RHS is not a named type.
543   if (lhs->channel_type() != NULL
544       && rhs->channel_type() != NULL
545       && rhs->channel_type()->may_send()
546       && rhs->channel_type()->may_receive()
547       && (lhs->named_type() == NULL || rhs->named_type() == NULL)
548       && Type::are_identical(lhs->channel_type()->element_type(),
549                              rhs->channel_type()->element_type(),
550                              true,
551                              reason))
552     return true;
553
554   // The nil type may be assigned to a pointer, function, slice, map,
555   // channel, or interface type.
556   if (rhs->is_nil_type()
557       && (lhs->points_to() != NULL
558           || lhs->function_type() != NULL
559           || lhs->is_slice_type()
560           || lhs->map_type() != NULL
561           || lhs->channel_type() != NULL
562           || lhs->interface_type() != NULL))
563     return true;
564
565   // An untyped numeric constant may be assigned to a numeric type if
566   // it is representable in that type.
567   if ((rhs->is_abstract()
568        && (rhs->integer_type() != NULL
569            || rhs->float_type() != NULL
570            || rhs->complex_type() != NULL))
571       && (lhs->integer_type() != NULL
572           || lhs->float_type() != NULL
573           || lhs->complex_type() != NULL))
574     return true;
575
576   // Give some better error messages.
577   if (reason != NULL && reason->empty())
578     {
579       if (rhs->interface_type() != NULL)
580         reason->assign(_("need explicit conversion"));
581       else if (rhs->is_call_multiple_result_type())
582         reason->assign(_("multiple value function call in "
583                          "single value context"));
584       else if (lhs->named_type() != NULL && rhs->named_type() != NULL)
585         {
586           size_t len = (lhs->named_type()->name().length()
587                         + rhs->named_type()->name().length()
588                         + 100);
589           char* buf = new char[len];
590           snprintf(buf, len, _("cannot use type %s as type %s"),
591                    rhs->named_type()->message_name().c_str(),
592                    lhs->named_type()->message_name().c_str());
593           reason->assign(buf);
594           delete[] buf;
595         }
596     }
597
598   return false;
599 }
600
601 // Return true if a value with type RHS may be assigned to a variable
602 // with type LHS.  If REASON is not NULL, set *REASON to the reason
603 // the types are not assignable.
604
605 bool
606 Type::are_assignable(const Type* lhs, const Type* rhs, std::string* reason)
607 {
608   return Type::are_assignable_check_hidden(lhs, rhs, false, reason);
609 }
610
611 // Like are_assignable but don't check for hidden fields.
612
613 bool
614 Type::are_assignable_hidden_ok(const Type* lhs, const Type* rhs,
615                                std::string* reason)
616 {
617   return Type::are_assignable_check_hidden(lhs, rhs, false, reason);
618 }
619
620 // Return true if a value with type RHS may be converted to type LHS.
621 // If REASON is not NULL, set *REASON to the reason the types are not
622 // convertible.
623
624 bool
625 Type::are_convertible(const Type* lhs, const Type* rhs, std::string* reason)
626 {
627   // The types are convertible if they are assignable.
628   if (Type::are_assignable(lhs, rhs, reason))
629     return true;
630
631   // The types are convertible if they have identical underlying
632   // types.
633   if ((lhs->named_type() != NULL || rhs->named_type() != NULL)
634       && Type::are_identical(lhs->base(), rhs->base(), true, reason))
635     return true;
636
637   // The types are convertible if they are both unnamed pointer types
638   // and their pointer base types have identical underlying types.
639   if (lhs->named_type() == NULL
640       && rhs->named_type() == NULL
641       && lhs->points_to() != NULL
642       && rhs->points_to() != NULL
643       && (lhs->points_to()->named_type() != NULL
644           || rhs->points_to()->named_type() != NULL)
645       && Type::are_identical(lhs->points_to()->base(),
646                              rhs->points_to()->base(),
647                              true,
648                              reason))
649     return true;
650
651   // Integer and floating point types are convertible to each other.
652   if ((lhs->integer_type() != NULL || lhs->float_type() != NULL)
653       && (rhs->integer_type() != NULL || rhs->float_type() != NULL))
654     return true;
655
656   // Complex types are convertible to each other.
657   if (lhs->complex_type() != NULL && rhs->complex_type() != NULL)
658     return true;
659
660   // An integer, or []byte, or []int, may be converted to a string.
661   if (lhs->is_string_type())
662     {
663       if (rhs->integer_type() != NULL)
664         return true;
665       if (rhs->is_slice_type() && rhs->named_type() == NULL)
666         {
667           const Type* e = rhs->array_type()->element_type()->forwarded();
668           if (e->integer_type() != NULL
669               && (e == Type::lookup_integer_type("uint8")
670                   || e == Type::lookup_integer_type("int")))
671             return true;
672         }
673     }
674
675   // A string may be converted to []byte or []int.
676   if (rhs->is_string_type()
677       && lhs->is_slice_type()
678       && lhs->named_type() == NULL)
679     {
680       const Type* e = lhs->array_type()->element_type()->forwarded();
681       if (e->integer_type() != NULL
682           && (e == Type::lookup_integer_type("uint8")
683               || e == Type::lookup_integer_type("int")))
684         return true;
685     }
686
687   // An unsafe.Pointer type may be converted to any pointer type or to
688   // uintptr, and vice-versa.
689   if (lhs->is_unsafe_pointer_type()
690       && (rhs->points_to() != NULL
691           || (rhs->integer_type() != NULL
692               && rhs->forwarded() == Type::lookup_integer_type("uintptr"))))
693     return true;
694   if (rhs->is_unsafe_pointer_type()
695       && (lhs->points_to() != NULL
696           || (lhs->integer_type() != NULL
697               && lhs->forwarded() == Type::lookup_integer_type("uintptr"))))
698     return true;
699
700   // Give a better error message.
701   if (reason != NULL)
702     {
703       if (reason->empty())
704         *reason = "invalid type conversion";
705       else
706         {
707           std::string s = "invalid type conversion (";
708           s += *reason;
709           s += ')';
710           *reason = s;
711         }
712     }
713
714   return false;
715 }
716
717 // Return whether this type has any hidden fields.  This is only a
718 // possibility for a few types.
719
720 bool
721 Type::has_hidden_fields(const Named_type* within, std::string* reason) const
722 {
723   switch (this->forwarded()->classification_)
724     {
725     case TYPE_NAMED:
726       return this->named_type()->named_type_has_hidden_fields(reason);
727     case TYPE_STRUCT:
728       return this->struct_type()->struct_has_hidden_fields(within, reason);
729     case TYPE_ARRAY:
730       return this->array_type()->array_has_hidden_fields(within, reason);
731     default:
732       return false;
733     }
734 }
735
736 // Return a hash code for the type to be used for method lookup.
737
738 unsigned int
739 Type::hash_for_method(Gogo* gogo) const
740 {
741   unsigned int ret = 0;
742   if (this->classification_ != TYPE_FORWARD)
743     ret += this->classification_;
744   return ret + this->do_hash_for_method(gogo);
745 }
746
747 // Default implementation of do_hash_for_method.  This is appropriate
748 // for types with no subfields.
749
750 unsigned int
751 Type::do_hash_for_method(Gogo*) const
752 {
753   return 0;
754 }
755
756 // Return a hash code for a string, given a starting hash.
757
758 unsigned int
759 Type::hash_string(const std::string& s, unsigned int h)
760 {
761   const char* p = s.data();
762   size_t len = s.length();
763   for (; len > 0; --len)
764     {
765       h ^= *p++;
766       h*= 16777619;
767     }
768   return h;
769 }
770
771 // A hash table mapping unnamed types to the backend representation of
772 // those types.
773
774 Type::Type_btypes Type::type_btypes;
775
776 // Return a tree representing this type.
777
778 Btype*
779 Type::get_backend(Gogo* gogo)
780 {
781   if (this->btype_ != NULL)
782     return this->btype_;
783
784   if (this->forward_declaration_type() != NULL
785       || this->named_type() != NULL)
786     return this->get_btype_without_hash(gogo);
787
788   if (this->is_error_type())
789     return gogo->backend()->error_type();
790
791   // To avoid confusing the backend, translate all identical Go types
792   // to the same backend representation.  We use a hash table to do
793   // that.  There is no need to use the hash table for named types, as
794   // named types are only identical to themselves.
795
796   std::pair<Type*, Btype*> val(this, NULL);
797   std::pair<Type_btypes::iterator, bool> ins =
798     Type::type_btypes.insert(val);
799   if (!ins.second && ins.first->second != NULL)
800     {
801       if (gogo != NULL && gogo->named_types_are_converted())
802         this->btype_ = ins.first->second;
803       return ins.first->second;
804     }
805
806   Btype* bt = this->get_btype_without_hash(gogo);
807
808   if (ins.first->second == NULL)
809     ins.first->second = bt;
810   else
811     {
812       // We have already created a backend representation for this
813       // type.  This can happen when an unnamed type is defined using
814       // a named type which in turns uses an identical unnamed type.
815       // Use the tree we created earlier and ignore the one we just
816       // built.
817       bt = ins.first->second;
818       if (gogo == NULL || !gogo->named_types_are_converted())
819         return bt;
820       this->btype_ = bt;
821     }
822
823   return bt;
824 }
825
826 // Return the backend representation for a type without looking in the
827 // hash table for identical types.  This is used for named types,
828 // since a named type is never identical to any other type.
829
830 Btype*
831 Type::get_btype_without_hash(Gogo* gogo)
832 {
833   if (this->btype_ == NULL)
834     {
835       Btype* bt = this->do_get_backend(gogo);
836
837       // For a recursive function or pointer type, we will temporarily
838       // return a circular pointer type during the recursion.  We
839       // don't want to record that for a forwarding type, as it may
840       // confuse us later.
841       if (this->forward_declaration_type() != NULL
842           && gogo->backend()->is_circular_pointer_type(bt))
843         return bt;
844
845       if (gogo == NULL || !gogo->named_types_are_converted())
846         return bt;
847
848       this->btype_ = bt;
849     }
850   return this->btype_;
851 }
852
853 // Return a pointer to the type descriptor for this type.
854
855 tree
856 Type::type_descriptor_pointer(Gogo* gogo, Location location)
857 {
858   Type* t = this->forwarded();
859   if (t->type_descriptor_var_ == NULL)
860     {
861       t->make_type_descriptor_var(gogo);
862       go_assert(t->type_descriptor_var_ != NULL);
863     }
864   tree var_tree = var_to_tree(t->type_descriptor_var_);
865   if (var_tree == error_mark_node)
866     return error_mark_node;
867   return build_fold_addr_expr_loc(location.gcc_location(), var_tree);
868 }
869
870 // A mapping from unnamed types to type descriptor variables.
871
872 Type::Type_descriptor_vars Type::type_descriptor_vars;
873
874 // Build the type descriptor for this type.
875
876 void
877 Type::make_type_descriptor_var(Gogo* gogo)
878 {
879   go_assert(this->type_descriptor_var_ == NULL);
880
881   Named_type* nt = this->named_type();
882
883   // We can have multiple instances of unnamed types, but we only want
884   // to emit the type descriptor once.  We use a hash table.  This is
885   // not necessary for named types, as they are unique, and we store
886   // the type descriptor in the type itself.
887   Bvariable** phash = NULL;
888   if (nt == NULL)
889     {
890       Bvariable* bvnull = NULL;
891       std::pair<Type_descriptor_vars::iterator, bool> ins =
892         Type::type_descriptor_vars.insert(std::make_pair(this, bvnull));
893       if (!ins.second)
894         {
895           // We've already build a type descriptor for this type.
896           this->type_descriptor_var_ = ins.first->second;
897           return;
898         }
899       phash = &ins.first->second;
900     }
901
902   std::string var_name;
903   if (nt == NULL)
904     var_name = this->unnamed_type_descriptor_var_name(gogo);
905   else
906     var_name = this->type_descriptor_var_name(gogo);
907
908   // Build the contents of the type descriptor.
909   Expression* initializer = this->do_type_descriptor(gogo, NULL);
910
911   Btype* initializer_btype = initializer->type()->get_backend(gogo);
912
913   // See if this type descriptor is defined in a different package.
914   bool is_defined_elsewhere = false;
915   if (nt != NULL)
916     {
917       if (nt->named_object()->package() != NULL)
918         {
919           // This is a named type defined in a different package.  The
920           // type descriptor should be defined in that package.
921           is_defined_elsewhere = true;
922         }
923     }
924   else
925     {
926       if (this->points_to() != NULL
927           && this->points_to()->named_type() != NULL
928           && this->points_to()->named_type()->named_object()->package() != NULL)
929         {
930           // This is an unnamed pointer to a named type defined in a
931           // different package.  The descriptor should be defined in
932           // that package.
933           is_defined_elsewhere = true;
934         }
935     }
936
937   Location loc = nt == NULL ? Linemap::predeclared_location() : nt->location();
938
939   if (is_defined_elsewhere)
940     {
941       this->type_descriptor_var_ =
942         gogo->backend()->immutable_struct_reference(var_name,
943                                                     initializer_btype,
944                                                     loc);
945       if (phash != NULL)
946         *phash = this->type_descriptor_var_;
947       return;
948     }
949
950   // See if this type descriptor can appear in multiple packages.
951   bool is_common = false;
952   if (nt != NULL)
953     {
954       // We create the descriptor for a builtin type whenever we need
955       // it.
956       is_common = nt->is_builtin();
957     }
958   else
959     {
960       // This is an unnamed type.  The descriptor could be defined in
961       // any package where it is needed, and the linker will pick one
962       // descriptor to keep.
963       is_common = true;
964     }
965
966   // We are going to build the type descriptor in this package.  We
967   // must create the variable before we convert the initializer to the
968   // backend representation, because the initializer may refer to the
969   // type descriptor of this type.  By setting type_descriptor_var_ we
970   // ensure that type_descriptor_pointer will work if called while
971   // converting INITIALIZER.
972
973   this->type_descriptor_var_ =
974     gogo->backend()->immutable_struct(var_name, is_common, initializer_btype,
975                                       loc);
976   if (phash != NULL)
977     *phash = this->type_descriptor_var_;
978
979   Translate_context context(gogo, NULL, NULL, NULL);
980   context.set_is_const();
981   Bexpression* binitializer = tree_to_expr(initializer->get_tree(&context));
982
983   gogo->backend()->immutable_struct_set_init(this->type_descriptor_var_,
984                                              var_name, is_common,
985                                              initializer_btype, loc,
986                                              binitializer);
987 }
988
989 // Return the name of the type descriptor variable for an unnamed
990 // type.
991
992 std::string
993 Type::unnamed_type_descriptor_var_name(Gogo* gogo)
994 {
995   return "__go_td_" + this->mangled_name(gogo);
996 }
997
998 // Return the name of the type descriptor variable for a named type.
999
1000 std::string
1001 Type::type_descriptor_var_name(Gogo* gogo)
1002 {
1003   Named_type* nt = this->named_type();
1004   Named_object* no = nt->named_object();
1005   const Named_object* in_function = nt->in_function();
1006   std::string ret = "__go_tdn_";
1007   if (nt->is_builtin())
1008     go_assert(in_function == NULL);
1009   else
1010     {
1011       const std::string& unique_prefix(no->package() == NULL
1012                                        ? gogo->unique_prefix()
1013                                        : no->package()->unique_prefix());
1014       const std::string& package_name(no->package() == NULL
1015                                       ? gogo->package_name()
1016                                       : no->package()->name());
1017       ret.append(unique_prefix);
1018       ret.append(1, '.');
1019       ret.append(package_name);
1020       ret.append(1, '.');
1021       if (in_function != NULL)
1022         {
1023           ret.append(Gogo::unpack_hidden_name(in_function->name()));
1024           ret.append(1, '.');
1025         }
1026     }
1027   ret.append(no->name());
1028   return ret;
1029 }
1030
1031 // Return a composite literal for a type descriptor.
1032
1033 Expression*
1034 Type::type_descriptor(Gogo* gogo, Type* type)
1035 {
1036   return type->do_type_descriptor(gogo, NULL);
1037 }
1038
1039 // Return a composite literal for a type descriptor with a name.
1040
1041 Expression*
1042 Type::named_type_descriptor(Gogo* gogo, Type* type, Named_type* name)
1043 {
1044   go_assert(name != NULL && type->named_type() != name);
1045   return type->do_type_descriptor(gogo, name);
1046 }
1047
1048 // Make a builtin struct type from a list of fields.  The fields are
1049 // pairs of a name and a type.
1050
1051 Struct_type*
1052 Type::make_builtin_struct_type(int nfields, ...)
1053 {
1054   va_list ap;
1055   va_start(ap, nfields);
1056
1057   Location bloc = Linemap::predeclared_location();
1058   Struct_field_list* sfl = new Struct_field_list();
1059   for (int i = 0; i < nfields; i++)
1060     {
1061       const char* field_name = va_arg(ap, const char *);
1062       Type* type = va_arg(ap, Type*);
1063       sfl->push_back(Struct_field(Typed_identifier(field_name, type, bloc)));
1064     }
1065
1066   va_end(ap);
1067
1068   return Type::make_struct_type(sfl, bloc);
1069 }
1070
1071 // A list of builtin named types.
1072
1073 std::vector<Named_type*> Type::named_builtin_types;
1074
1075 // Make a builtin named type.
1076
1077 Named_type*
1078 Type::make_builtin_named_type(const char* name, Type* type)
1079 {
1080   Location bloc = Linemap::predeclared_location();
1081   Named_object* no = Named_object::make_type(name, NULL, type, bloc);
1082   Named_type* ret = no->type_value();
1083   Type::named_builtin_types.push_back(ret);
1084   return ret;
1085 }
1086
1087 // Convert the named builtin types.
1088
1089 void
1090 Type::convert_builtin_named_types(Gogo* gogo)
1091 {
1092   for (std::vector<Named_type*>::const_iterator p =
1093          Type::named_builtin_types.begin();
1094        p != Type::named_builtin_types.end();
1095        ++p)
1096     {
1097       bool r = (*p)->verify();
1098       go_assert(r);
1099       (*p)->convert(gogo);
1100     }
1101 }
1102
1103 // Return the type of a type descriptor.  We should really tie this to
1104 // runtime.Type rather than copying it.  This must match commonType in
1105 // libgo/go/runtime/type.go.
1106
1107 Type*
1108 Type::make_type_descriptor_type()
1109 {
1110   static Type* ret;
1111   if (ret == NULL)
1112     {
1113       Location bloc = Linemap::predeclared_location();
1114
1115       Type* uint8_type = Type::lookup_integer_type("uint8");
1116       Type* uint32_type = Type::lookup_integer_type("uint32");
1117       Type* uintptr_type = Type::lookup_integer_type("uintptr");
1118       Type* string_type = Type::lookup_string_type();
1119       Type* pointer_string_type = Type::make_pointer_type(string_type);
1120
1121       // This is an unnamed version of unsafe.Pointer.  Perhaps we
1122       // should use the named version instead, although that would
1123       // require us to create the unsafe package if it has not been
1124       // imported.  It probably doesn't matter.
1125       Type* void_type = Type::make_void_type();
1126       Type* unsafe_pointer_type = Type::make_pointer_type(void_type);
1127
1128       // Forward declaration for the type descriptor type.
1129       Named_object* named_type_descriptor_type =
1130         Named_object::make_type_declaration("commonType", NULL, bloc);
1131       Type* ft = Type::make_forward_declaration(named_type_descriptor_type);
1132       Type* pointer_type_descriptor_type = Type::make_pointer_type(ft);
1133
1134       // The type of a method on a concrete type.
1135       Struct_type* method_type =
1136         Type::make_builtin_struct_type(5,
1137                                        "name", pointer_string_type,
1138                                        "pkgPath", pointer_string_type,
1139                                        "mtyp", pointer_type_descriptor_type,
1140                                        "typ", pointer_type_descriptor_type,
1141                                        "tfn", unsafe_pointer_type);
1142       Named_type* named_method_type =
1143         Type::make_builtin_named_type("method", method_type);
1144
1145       // Information for types with a name or methods.
1146       Type* slice_named_method_type =
1147         Type::make_array_type(named_method_type, NULL);
1148       Struct_type* uncommon_type =
1149         Type::make_builtin_struct_type(3,
1150                                        "name", pointer_string_type,
1151                                        "pkgPath", pointer_string_type,
1152                                        "methods", slice_named_method_type);
1153       Named_type* named_uncommon_type =
1154         Type::make_builtin_named_type("uncommonType", uncommon_type);
1155
1156       Type* pointer_uncommon_type =
1157         Type::make_pointer_type(named_uncommon_type);
1158
1159       // The type descriptor type.
1160
1161       Typed_identifier_list* params = new Typed_identifier_list();
1162       params->push_back(Typed_identifier("", unsafe_pointer_type, bloc));
1163       params->push_back(Typed_identifier("", uintptr_type, bloc));
1164
1165       Typed_identifier_list* results = new Typed_identifier_list();
1166       results->push_back(Typed_identifier("", uintptr_type, bloc));
1167
1168       Type* hashfn_type = Type::make_function_type(NULL, params, results, bloc);
1169
1170       params = new Typed_identifier_list();
1171       params->push_back(Typed_identifier("", unsafe_pointer_type, bloc));
1172       params->push_back(Typed_identifier("", unsafe_pointer_type, bloc));
1173       params->push_back(Typed_identifier("", uintptr_type, bloc));
1174
1175       results = new Typed_identifier_list();
1176       results->push_back(Typed_identifier("", Type::lookup_bool_type(), bloc));
1177
1178       Type* equalfn_type = Type::make_function_type(NULL, params, results,
1179                                                     bloc);
1180
1181       Struct_type* type_descriptor_type =
1182         Type::make_builtin_struct_type(10,
1183                                        "Kind", uint8_type,
1184                                        "align", uint8_type,
1185                                        "fieldAlign", uint8_type,
1186                                        "size", uintptr_type,
1187                                        "hash", uint32_type,
1188                                        "hashfn", hashfn_type,
1189                                        "equalfn", equalfn_type,
1190                                        "string", pointer_string_type,
1191                                        "", pointer_uncommon_type,
1192                                        "ptrToThis",
1193                                        pointer_type_descriptor_type);
1194
1195       Named_type* named = Type::make_builtin_named_type("commonType",
1196                                                         type_descriptor_type);
1197
1198       named_type_descriptor_type->set_type_value(named);
1199
1200       ret = named;
1201     }
1202
1203   return ret;
1204 }
1205
1206 // Make the type of a pointer to a type descriptor as represented in
1207 // Go.
1208
1209 Type*
1210 Type::make_type_descriptor_ptr_type()
1211 {
1212   static Type* ret;
1213   if (ret == NULL)
1214     ret = Type::make_pointer_type(Type::make_type_descriptor_type());
1215   return ret;
1216 }
1217
1218 // Return the names of runtime functions which compute a hash code for
1219 // this type and which compare whether two values of this type are
1220 // equal.
1221
1222 void
1223 Type::type_functions(const char** hash_fn, const char** equal_fn) const
1224 {
1225   switch (this->base()->classification())
1226     {
1227     case Type::TYPE_ERROR:
1228     case Type::TYPE_VOID:
1229     case Type::TYPE_NIL:
1230       // These types can not be hashed or compared.
1231       *hash_fn = "__go_type_hash_error";
1232       *equal_fn = "__go_type_equal_error";
1233       break;
1234
1235     case Type::TYPE_BOOLEAN:
1236     case Type::TYPE_INTEGER:
1237     case Type::TYPE_FLOAT:
1238     case Type::TYPE_COMPLEX:
1239     case Type::TYPE_POINTER:
1240     case Type::TYPE_FUNCTION:
1241     case Type::TYPE_MAP:
1242     case Type::TYPE_CHANNEL:
1243       *hash_fn = "__go_type_hash_identity";
1244       *equal_fn = "__go_type_equal_identity";
1245       break;
1246
1247     case Type::TYPE_STRING:
1248       *hash_fn = "__go_type_hash_string";
1249       *equal_fn = "__go_type_equal_string";
1250       break;
1251
1252     case Type::TYPE_STRUCT:
1253     case Type::TYPE_ARRAY:
1254       // These types can not be hashed or compared.
1255       *hash_fn = "__go_type_hash_error";
1256       *equal_fn = "__go_type_equal_error";
1257       break;
1258
1259     case Type::TYPE_INTERFACE:
1260       if (this->interface_type()->is_empty())
1261         {
1262           *hash_fn = "__go_type_hash_empty_interface";
1263           *equal_fn = "__go_type_equal_empty_interface";
1264         }
1265       else
1266         {
1267           *hash_fn = "__go_type_hash_interface";
1268           *equal_fn = "__go_type_equal_interface";
1269         }
1270       break;
1271
1272     case Type::TYPE_NAMED:
1273     case Type::TYPE_FORWARD:
1274       go_unreachable();
1275
1276     default:
1277       go_unreachable();
1278     }
1279 }
1280
1281 // Return a composite literal for the type descriptor for a plain type
1282 // of kind RUNTIME_TYPE_KIND named NAME.
1283
1284 Expression*
1285 Type::type_descriptor_constructor(Gogo* gogo, int runtime_type_kind,
1286                                   Named_type* name, const Methods* methods,
1287                                   bool only_value_methods)
1288 {
1289   Location bloc = Linemap::predeclared_location();
1290
1291   Type* td_type = Type::make_type_descriptor_type();
1292   const Struct_field_list* fields = td_type->struct_type()->fields();
1293
1294   Expression_list* vals = new Expression_list();
1295   vals->reserve(9);
1296
1297   if (!this->has_pointer())
1298     runtime_type_kind |= RUNTIME_TYPE_KIND_NO_POINTERS;
1299   Struct_field_list::const_iterator p = fields->begin();
1300   go_assert(p->is_field_name("Kind"));
1301   mpz_t iv;
1302   mpz_init_set_ui(iv, runtime_type_kind);
1303   vals->push_back(Expression::make_integer(&iv, p->type(), bloc));
1304
1305   ++p;
1306   go_assert(p->is_field_name("align"));
1307   Expression::Type_info type_info = Expression::TYPE_INFO_ALIGNMENT;
1308   vals->push_back(Expression::make_type_info(this, type_info));
1309
1310   ++p;
1311   go_assert(p->is_field_name("fieldAlign"));
1312   type_info = Expression::TYPE_INFO_FIELD_ALIGNMENT;
1313   vals->push_back(Expression::make_type_info(this, type_info));
1314
1315   ++p;
1316   go_assert(p->is_field_name("size"));
1317   type_info = Expression::TYPE_INFO_SIZE;
1318   vals->push_back(Expression::make_type_info(this, type_info));
1319
1320   ++p;
1321   go_assert(p->is_field_name("hash"));
1322   mpz_set_ui(iv, this->hash_for_method(gogo));
1323   vals->push_back(Expression::make_integer(&iv, p->type(), bloc));
1324
1325   const char* hash_fn;
1326   const char* equal_fn;
1327   this->type_functions(&hash_fn, &equal_fn);
1328
1329   ++p;
1330   go_assert(p->is_field_name("hashfn"));
1331   Function_type* fntype = p->type()->function_type();
1332   Named_object* no = Named_object::make_function_declaration(hash_fn, NULL,
1333                                                              fntype,
1334                                                              bloc);
1335   no->func_declaration_value()->set_asm_name(hash_fn);
1336   vals->push_back(Expression::make_func_reference(no, NULL, bloc));
1337
1338   ++p;
1339   go_assert(p->is_field_name("equalfn"));
1340   fntype = p->type()->function_type();
1341   no = Named_object::make_function_declaration(equal_fn, NULL, fntype, bloc);
1342   no->func_declaration_value()->set_asm_name(equal_fn);
1343   vals->push_back(Expression::make_func_reference(no, NULL, bloc));
1344
1345   ++p;
1346   go_assert(p->is_field_name("string"));
1347   Expression* s = Expression::make_string((name != NULL
1348                                            ? name->reflection(gogo)
1349                                            : this->reflection(gogo)),
1350                                           bloc);
1351   vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
1352
1353   ++p;
1354   go_assert(p->is_field_name("uncommonType"));
1355   if (name == NULL && methods == NULL)
1356     vals->push_back(Expression::make_nil(bloc));
1357   else
1358     {
1359       if (methods == NULL)
1360         methods = name->methods();
1361       vals->push_back(this->uncommon_type_constructor(gogo,
1362                                                       p->type()->deref(),
1363                                                       name, methods,
1364                                                       only_value_methods));
1365     }
1366
1367   ++p;
1368   go_assert(p->is_field_name("ptrToThis"));
1369   if (name == NULL)
1370     vals->push_back(Expression::make_nil(bloc));
1371   else
1372     {
1373       Type* pt = Type::make_pointer_type(name);
1374       vals->push_back(Expression::make_type_descriptor(pt, bloc));
1375     }
1376
1377   ++p;
1378   go_assert(p == fields->end());
1379
1380   mpz_clear(iv);
1381
1382   return Expression::make_struct_composite_literal(td_type, vals, bloc);
1383 }
1384
1385 // Return a composite literal for the uncommon type information for
1386 // this type.  UNCOMMON_STRUCT_TYPE is the type of the uncommon type
1387 // struct.  If name is not NULL, it is the name of the type.  If
1388 // METHODS is not NULL, it is the list of methods.  ONLY_VALUE_METHODS
1389 // is true if only value methods should be included.  At least one of
1390 // NAME and METHODS must not be NULL.
1391
1392 Expression*
1393 Type::uncommon_type_constructor(Gogo* gogo, Type* uncommon_type,
1394                                 Named_type* name, const Methods* methods,
1395                                 bool only_value_methods) const
1396 {
1397   Location bloc = Linemap::predeclared_location();
1398
1399   const Struct_field_list* fields = uncommon_type->struct_type()->fields();
1400
1401   Expression_list* vals = new Expression_list();
1402   vals->reserve(3);
1403
1404   Struct_field_list::const_iterator p = fields->begin();
1405   go_assert(p->is_field_name("name"));
1406
1407   ++p;
1408   go_assert(p->is_field_name("pkgPath"));
1409
1410   if (name == NULL)
1411     {
1412       vals->push_back(Expression::make_nil(bloc));
1413       vals->push_back(Expression::make_nil(bloc));
1414     }
1415   else
1416     {
1417       Named_object* no = name->named_object();
1418       std::string n = Gogo::unpack_hidden_name(no->name());
1419       Expression* s = Expression::make_string(n, bloc);
1420       vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
1421
1422       if (name->is_builtin())
1423         vals->push_back(Expression::make_nil(bloc));
1424       else
1425         {
1426           const Package* package = no->package();
1427           const std::string& unique_prefix(package == NULL
1428                                            ? gogo->unique_prefix()
1429                                            : package->unique_prefix());
1430           const std::string& package_name(package == NULL
1431                                           ? gogo->package_name()
1432                                           : package->name());
1433           n.assign(unique_prefix);
1434           n.append(1, '.');
1435           n.append(package_name);
1436           if (name->in_function() != NULL)
1437             {
1438               n.append(1, '.');
1439               n.append(Gogo::unpack_hidden_name(name->in_function()->name()));
1440             }
1441           s = Expression::make_string(n, bloc);
1442           vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
1443         }
1444     }
1445
1446   ++p;
1447   go_assert(p->is_field_name("methods"));
1448   vals->push_back(this->methods_constructor(gogo, p->type(), methods,
1449                                             only_value_methods));
1450
1451   ++p;
1452   go_assert(p == fields->end());
1453
1454   Expression* r = Expression::make_struct_composite_literal(uncommon_type,
1455                                                             vals, bloc);
1456   return Expression::make_unary(OPERATOR_AND, r, bloc);
1457 }
1458
1459 // Sort methods by name.
1460
1461 class Sort_methods
1462 {
1463  public:
1464   bool
1465   operator()(const std::pair<std::string, const Method*>& m1,
1466              const std::pair<std::string, const Method*>& m2) const
1467   { return m1.first < m2.first; }
1468 };
1469
1470 // Return a composite literal for the type method table for this type.
1471 // METHODS_TYPE is the type of the table, and is a slice type.
1472 // METHODS is the list of methods.  If ONLY_VALUE_METHODS is true,
1473 // then only value methods are used.
1474
1475 Expression*
1476 Type::methods_constructor(Gogo* gogo, Type* methods_type,
1477                           const Methods* methods,
1478                           bool only_value_methods) const
1479 {
1480   Location bloc = Linemap::predeclared_location();
1481
1482   std::vector<std::pair<std::string, const Method*> > smethods;
1483   if (methods != NULL)
1484     {
1485       smethods.reserve(methods->count());
1486       for (Methods::const_iterator p = methods->begin();
1487            p != methods->end();
1488            ++p)
1489         {
1490           if (p->second->is_ambiguous())
1491             continue;
1492           if (only_value_methods && !p->second->is_value_method())
1493             continue;
1494           smethods.push_back(std::make_pair(p->first, p->second));
1495         }
1496     }
1497
1498   if (smethods.empty())
1499     return Expression::make_slice_composite_literal(methods_type, NULL, bloc);
1500
1501   std::sort(smethods.begin(), smethods.end(), Sort_methods());
1502
1503   Type* method_type = methods_type->array_type()->element_type();
1504
1505   Expression_list* vals = new Expression_list();
1506   vals->reserve(smethods.size());
1507   for (std::vector<std::pair<std::string, const Method*> >::const_iterator p
1508          = smethods.begin();
1509        p != smethods.end();
1510        ++p)
1511     vals->push_back(this->method_constructor(gogo, method_type, p->first,
1512                                              p->second, only_value_methods));
1513
1514   return Expression::make_slice_composite_literal(methods_type, vals, bloc);
1515 }
1516
1517 // Return a composite literal for a single method.  METHOD_TYPE is the
1518 // type of the entry.  METHOD_NAME is the name of the method and M is
1519 // the method information.
1520
1521 Expression*
1522 Type::method_constructor(Gogo*, Type* method_type,
1523                          const std::string& method_name,
1524                          const Method* m,
1525                          bool only_value_methods) const
1526 {
1527   Location bloc = Linemap::predeclared_location();
1528
1529   const Struct_field_list* fields = method_type->struct_type()->fields();
1530
1531   Expression_list* vals = new Expression_list();
1532   vals->reserve(5);
1533
1534   Struct_field_list::const_iterator p = fields->begin();
1535   go_assert(p->is_field_name("name"));
1536   const std::string n = Gogo::unpack_hidden_name(method_name);
1537   Expression* s = Expression::make_string(n, bloc);
1538   vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
1539
1540   ++p;
1541   go_assert(p->is_field_name("pkgPath"));
1542   if (!Gogo::is_hidden_name(method_name))
1543     vals->push_back(Expression::make_nil(bloc));
1544   else
1545     {
1546       s = Expression::make_string(Gogo::hidden_name_prefix(method_name), bloc);
1547       vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
1548     }
1549
1550   Named_object* no = (m->needs_stub_method()
1551                       ? m->stub_object()
1552                       : m->named_object());
1553
1554   Function_type* mtype;
1555   if (no->is_function())
1556     mtype = no->func_value()->type();
1557   else
1558     mtype = no->func_declaration_value()->type();
1559   go_assert(mtype->is_method());
1560   Type* nonmethod_type = mtype->copy_without_receiver();
1561
1562   ++p;
1563   go_assert(p->is_field_name("mtyp"));
1564   vals->push_back(Expression::make_type_descriptor(nonmethod_type, bloc));
1565
1566   ++p;
1567   go_assert(p->is_field_name("typ"));
1568   if (!only_value_methods && m->is_value_method())
1569     {
1570       // This is a value method on a pointer type.  Change the type of
1571       // the method to use a pointer receiver.  The implementation
1572       // always uses a pointer receiver anyhow.
1573       Type* rtype = mtype->receiver()->type();
1574       Type* prtype = Type::make_pointer_type(rtype);
1575       Typed_identifier* receiver =
1576         new Typed_identifier(mtype->receiver()->name(), prtype,
1577                              mtype->receiver()->location());
1578       mtype = Type::make_function_type(receiver,
1579                                        (mtype->parameters() == NULL
1580                                         ? NULL
1581                                         : mtype->parameters()->copy()),
1582                                        (mtype->results() == NULL
1583                                         ? NULL
1584                                         : mtype->results()->copy()),
1585                                        mtype->location());
1586     }
1587   vals->push_back(Expression::make_type_descriptor(mtype, bloc));
1588
1589   ++p;
1590   go_assert(p->is_field_name("tfn"));
1591   vals->push_back(Expression::make_func_reference(no, NULL, bloc));
1592
1593   ++p;
1594   go_assert(p == fields->end());
1595
1596   return Expression::make_struct_composite_literal(method_type, vals, bloc);
1597 }
1598
1599 // Return a composite literal for the type descriptor of a plain type.
1600 // RUNTIME_TYPE_KIND is the value of the kind field.  If NAME is not
1601 // NULL, it is the name to use as well as the list of methods.
1602
1603 Expression*
1604 Type::plain_type_descriptor(Gogo* gogo, int runtime_type_kind,
1605                             Named_type* name)
1606 {
1607   return this->type_descriptor_constructor(gogo, runtime_type_kind,
1608                                            name, NULL, true);
1609 }
1610
1611 // Return the type reflection string for this type.
1612
1613 std::string
1614 Type::reflection(Gogo* gogo) const
1615 {
1616   std::string ret;
1617
1618   // The do_reflection virtual function should set RET to the
1619   // reflection string.
1620   this->do_reflection(gogo, &ret);
1621
1622   return ret;
1623 }
1624
1625 // Return a mangled name for the type.
1626
1627 std::string
1628 Type::mangled_name(Gogo* gogo) const
1629 {
1630   std::string ret;
1631
1632   // The do_mangled_name virtual function should set RET to the
1633   // mangled name.  For a composite type it should append a code for
1634   // the composition and then call do_mangled_name on the components.
1635   this->do_mangled_name(gogo, &ret);
1636
1637   return ret;
1638 }
1639
1640 // Default function to export a type.
1641
1642 void
1643 Type::do_export(Export*) const
1644 {
1645   go_unreachable();
1646 }
1647
1648 // Import a type.
1649
1650 Type*
1651 Type::import_type(Import* imp)
1652 {
1653   if (imp->match_c_string("("))
1654     return Function_type::do_import(imp);
1655   else if (imp->match_c_string("*"))
1656     return Pointer_type::do_import(imp);
1657   else if (imp->match_c_string("struct "))
1658     return Struct_type::do_import(imp);
1659   else if (imp->match_c_string("["))
1660     return Array_type::do_import(imp);
1661   else if (imp->match_c_string("map "))
1662     return Map_type::do_import(imp);
1663   else if (imp->match_c_string("chan "))
1664     return Channel_type::do_import(imp);
1665   else if (imp->match_c_string("interface"))
1666     return Interface_type::do_import(imp);
1667   else
1668     {
1669       error_at(imp->location(), "import error: expected type");
1670       return Type::make_error_type();
1671     }
1672 }
1673
1674 // A type used to indicate a parsing error.  This exists to simplify
1675 // later error detection.
1676
1677 class Error_type : public Type
1678 {
1679  public:
1680   Error_type()
1681     : Type(TYPE_ERROR)
1682   { }
1683
1684  protected:
1685   Btype*
1686   do_get_backend(Gogo* gogo)
1687   { return gogo->backend()->error_type(); }
1688
1689   Expression*
1690   do_type_descriptor(Gogo*, Named_type*)
1691   { return Expression::make_error(Linemap::predeclared_location()); }
1692
1693   void
1694   do_reflection(Gogo*, std::string*) const
1695   { go_assert(saw_errors()); }
1696
1697   void
1698   do_mangled_name(Gogo*, std::string* ret) const
1699   { ret->push_back('E'); }
1700 };
1701
1702 Type*
1703 Type::make_error_type()
1704 {
1705   static Error_type singleton_error_type;
1706   return &singleton_error_type;
1707 }
1708
1709 // The void type.
1710
1711 class Void_type : public Type
1712 {
1713  public:
1714   Void_type()
1715     : Type(TYPE_VOID)
1716   { }
1717
1718  protected:
1719   Btype*
1720   do_get_backend(Gogo* gogo)
1721   { return gogo->backend()->void_type(); }
1722
1723   Expression*
1724   do_type_descriptor(Gogo*, Named_type*)
1725   { go_unreachable(); }
1726
1727   void
1728   do_reflection(Gogo*, std::string*) const
1729   { }
1730
1731   void
1732   do_mangled_name(Gogo*, std::string* ret) const
1733   { ret->push_back('v'); }
1734 };
1735
1736 Type*
1737 Type::make_void_type()
1738 {
1739   static Void_type singleton_void_type;
1740   return &singleton_void_type;
1741 }
1742
1743 // The boolean type.
1744
1745 class Boolean_type : public Type
1746 {
1747  public:
1748   Boolean_type()
1749     : Type(TYPE_BOOLEAN)
1750   { }
1751
1752  protected:
1753   Btype*
1754   do_get_backend(Gogo* gogo)
1755   { return gogo->backend()->bool_type(); }
1756
1757   Expression*
1758   do_type_descriptor(Gogo*, Named_type* name);
1759
1760   // We should not be asked for the reflection string of a basic type.
1761   void
1762   do_reflection(Gogo*, std::string* ret) const
1763   { ret->append("bool"); }
1764
1765   void
1766   do_mangled_name(Gogo*, std::string* ret) const
1767   { ret->push_back('b'); }
1768 };
1769
1770 // Make the type descriptor.
1771
1772 Expression*
1773 Boolean_type::do_type_descriptor(Gogo* gogo, Named_type* name)
1774 {
1775   if (name != NULL)
1776     return this->plain_type_descriptor(gogo, RUNTIME_TYPE_KIND_BOOL, name);
1777   else
1778     {
1779       Named_object* no = gogo->lookup_global("bool");
1780       go_assert(no != NULL);
1781       return Type::type_descriptor(gogo, no->type_value());
1782     }
1783 }
1784
1785 Type*
1786 Type::make_boolean_type()
1787 {
1788   static Boolean_type boolean_type;
1789   return &boolean_type;
1790 }
1791
1792 // The named type "bool".
1793
1794 static Named_type* named_bool_type;
1795
1796 // Get the named type "bool".
1797
1798 Named_type*
1799 Type::lookup_bool_type()
1800 {
1801   return named_bool_type;
1802 }
1803
1804 // Make the named type "bool".
1805
1806 Named_type*
1807 Type::make_named_bool_type()
1808 {
1809   Type* bool_type = Type::make_boolean_type();
1810   Named_object* named_object =
1811     Named_object::make_type("bool", NULL, bool_type,
1812                             Linemap::predeclared_location());
1813   Named_type* named_type = named_object->type_value();
1814   named_bool_type = named_type;
1815   return named_type;
1816 }
1817
1818 // Class Integer_type.
1819
1820 Integer_type::Named_integer_types Integer_type::named_integer_types;
1821
1822 // Create a new integer type.  Non-abstract integer types always have
1823 // names.
1824
1825 Named_type*
1826 Integer_type::create_integer_type(const char* name, bool is_unsigned,
1827                                   int bits, int runtime_type_kind)
1828 {
1829   Integer_type* integer_type = new Integer_type(false, is_unsigned, bits,
1830                                                 runtime_type_kind);
1831   std::string sname(name);
1832   Named_object* named_object =
1833     Named_object::make_type(sname, NULL, integer_type,
1834                             Linemap::predeclared_location());
1835   Named_type* named_type = named_object->type_value();
1836   std::pair<Named_integer_types::iterator, bool> ins =
1837     Integer_type::named_integer_types.insert(std::make_pair(sname, named_type));
1838   go_assert(ins.second);
1839   return named_type;
1840 }
1841
1842 // Look up an existing integer type.
1843
1844 Named_type*
1845 Integer_type::lookup_integer_type(const char* name)
1846 {
1847   Named_integer_types::const_iterator p =
1848     Integer_type::named_integer_types.find(name);
1849   go_assert(p != Integer_type::named_integer_types.end());
1850   return p->second;
1851 }
1852
1853 // Create a new abstract integer type.
1854
1855 Integer_type*
1856 Integer_type::create_abstract_integer_type()
1857 {
1858   static Integer_type* abstract_type;
1859   if (abstract_type == NULL)
1860     abstract_type = new Integer_type(true, false, INT_TYPE_SIZE,
1861                                      RUNTIME_TYPE_KIND_INT);
1862   return abstract_type;
1863 }
1864
1865 // Integer type compatibility.
1866
1867 bool
1868 Integer_type::is_identical(const Integer_type* t) const
1869 {
1870   if (this->is_unsigned_ != t->is_unsigned_ || this->bits_ != t->bits_)
1871     return false;
1872   return this->is_abstract_ == t->is_abstract_;
1873 }
1874
1875 // Hash code.
1876
1877 unsigned int
1878 Integer_type::do_hash_for_method(Gogo*) const
1879 {
1880   return ((this->bits_ << 4)
1881           + ((this->is_unsigned_ ? 1 : 0) << 8)
1882           + ((this->is_abstract_ ? 1 : 0) << 9));
1883 }
1884
1885 // Convert an Integer_type to the backend representation.
1886
1887 Btype*
1888 Integer_type::do_get_backend(Gogo* gogo)
1889 {
1890   if (this->is_abstract_)
1891     {
1892       go_assert(saw_errors());
1893       return gogo->backend()->error_type();
1894     }
1895   return gogo->backend()->integer_type(this->is_unsigned_, this->bits_);
1896 }
1897
1898 // The type descriptor for an integer type.  Integer types are always
1899 // named.
1900
1901 Expression*
1902 Integer_type::do_type_descriptor(Gogo* gogo, Named_type* name)
1903 {
1904   go_assert(name != NULL);
1905   return this->plain_type_descriptor(gogo, this->runtime_type_kind_, name);
1906 }
1907
1908 // We should not be asked for the reflection string of a basic type.
1909
1910 void
1911 Integer_type::do_reflection(Gogo*, std::string*) const
1912 {
1913   go_assert(saw_errors());
1914 }
1915
1916 // Mangled name.
1917
1918 void
1919 Integer_type::do_mangled_name(Gogo*, std::string* ret) const
1920 {
1921   char buf[100];
1922   snprintf(buf, sizeof buf, "i%s%s%de",
1923            this->is_abstract_ ? "a" : "",
1924            this->is_unsigned_ ? "u" : "",
1925            this->bits_);
1926   ret->append(buf);
1927 }
1928
1929 // Make an integer type.
1930
1931 Named_type*
1932 Type::make_integer_type(const char* name, bool is_unsigned, int bits,
1933                         int runtime_type_kind)
1934 {
1935   return Integer_type::create_integer_type(name, is_unsigned, bits,
1936                                            runtime_type_kind);
1937 }
1938
1939 // Make an abstract integer type.
1940
1941 Integer_type*
1942 Type::make_abstract_integer_type()
1943 {
1944   return Integer_type::create_abstract_integer_type();
1945 }
1946
1947 // Look up an integer type.
1948
1949 Named_type*
1950 Type::lookup_integer_type(const char* name)
1951 {
1952   return Integer_type::lookup_integer_type(name);
1953 }
1954
1955 // Class Float_type.
1956
1957 Float_type::Named_float_types Float_type::named_float_types;
1958
1959 // Create a new float type.  Non-abstract float types always have
1960 // names.
1961
1962 Named_type*
1963 Float_type::create_float_type(const char* name, int bits,
1964                               int runtime_type_kind)
1965 {
1966   Float_type* float_type = new Float_type(false, bits, runtime_type_kind);
1967   std::string sname(name);
1968   Named_object* named_object =
1969     Named_object::make_type(sname, NULL, float_type,
1970                             Linemap::predeclared_location());
1971   Named_type* named_type = named_object->type_value();
1972   std::pair<Named_float_types::iterator, bool> ins =
1973     Float_type::named_float_types.insert(std::make_pair(sname, named_type));
1974   go_assert(ins.second);
1975   return named_type;
1976 }
1977
1978 // Look up an existing float type.
1979
1980 Named_type*
1981 Float_type::lookup_float_type(const char* name)
1982 {
1983   Named_float_types::const_iterator p =
1984     Float_type::named_float_types.find(name);
1985   go_assert(p != Float_type::named_float_types.end());
1986   return p->second;
1987 }
1988
1989 // Create a new abstract float type.
1990
1991 Float_type*
1992 Float_type::create_abstract_float_type()
1993 {
1994   static Float_type* abstract_type;
1995   if (abstract_type == NULL)
1996     abstract_type = new Float_type(true, 64, RUNTIME_TYPE_KIND_FLOAT64);
1997   return abstract_type;
1998 }
1999
2000 // Whether this type is identical with T.
2001
2002 bool
2003 Float_type::is_identical(const Float_type* t) const
2004 {
2005   if (this->bits_ != t->bits_)
2006     return false;
2007   return this->is_abstract_ == t->is_abstract_;
2008 }
2009
2010 // Hash code.
2011
2012 unsigned int
2013 Float_type::do_hash_for_method(Gogo*) const
2014 {
2015   return (this->bits_ << 4) + ((this->is_abstract_ ? 1 : 0) << 8);
2016 }
2017
2018 // Convert to the backend representation.
2019
2020 Btype*
2021 Float_type::do_get_backend(Gogo* gogo)
2022 {
2023   return gogo->backend()->float_type(this->bits_);
2024 }
2025
2026 // The type descriptor for a float type.  Float types are always named.
2027
2028 Expression*
2029 Float_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2030 {
2031   go_assert(name != NULL);
2032   return this->plain_type_descriptor(gogo, this->runtime_type_kind_, name);
2033 }
2034
2035 // We should not be asked for the reflection string of a basic type.
2036
2037 void
2038 Float_type::do_reflection(Gogo*, std::string*) const
2039 {
2040   go_assert(saw_errors());
2041 }
2042
2043 // Mangled name.
2044
2045 void
2046 Float_type::do_mangled_name(Gogo*, std::string* ret) const
2047 {
2048   char buf[100];
2049   snprintf(buf, sizeof buf, "f%s%de",
2050            this->is_abstract_ ? "a" : "",
2051            this->bits_);
2052   ret->append(buf);
2053 }
2054
2055 // Make a floating point type.
2056
2057 Named_type*
2058 Type::make_float_type(const char* name, int bits, int runtime_type_kind)
2059 {
2060   return Float_type::create_float_type(name, bits, runtime_type_kind);
2061 }
2062
2063 // Make an abstract float type.
2064
2065 Float_type*
2066 Type::make_abstract_float_type()
2067 {
2068   return Float_type::create_abstract_float_type();
2069 }
2070
2071 // Look up a float type.
2072
2073 Named_type*
2074 Type::lookup_float_type(const char* name)
2075 {
2076   return Float_type::lookup_float_type(name);
2077 }
2078
2079 // Class Complex_type.
2080
2081 Complex_type::Named_complex_types Complex_type::named_complex_types;
2082
2083 // Create a new complex type.  Non-abstract complex types always have
2084 // names.
2085
2086 Named_type*
2087 Complex_type::create_complex_type(const char* name, int bits,
2088                                   int runtime_type_kind)
2089 {
2090   Complex_type* complex_type = new Complex_type(false, bits,
2091                                                 runtime_type_kind);
2092   std::string sname(name);
2093   Named_object* named_object =
2094     Named_object::make_type(sname, NULL, complex_type,
2095                             Linemap::predeclared_location());
2096   Named_type* named_type = named_object->type_value();
2097   std::pair<Named_complex_types::iterator, bool> ins =
2098     Complex_type::named_complex_types.insert(std::make_pair(sname,
2099                                                             named_type));
2100   go_assert(ins.second);
2101   return named_type;
2102 }
2103
2104 // Look up an existing complex type.
2105
2106 Named_type*
2107 Complex_type::lookup_complex_type(const char* name)
2108 {
2109   Named_complex_types::const_iterator p =
2110     Complex_type::named_complex_types.find(name);
2111   go_assert(p != Complex_type::named_complex_types.end());
2112   return p->second;
2113 }
2114
2115 // Create a new abstract complex type.
2116
2117 Complex_type*
2118 Complex_type::create_abstract_complex_type()
2119 {
2120   static Complex_type* abstract_type;
2121   if (abstract_type == NULL)
2122     abstract_type = new Complex_type(true, 128, RUNTIME_TYPE_KIND_COMPLEX128);
2123   return abstract_type;
2124 }
2125
2126 // Whether this type is identical with T.
2127
2128 bool
2129 Complex_type::is_identical(const Complex_type *t) const
2130 {
2131   if (this->bits_ != t->bits_)
2132     return false;
2133   return this->is_abstract_ == t->is_abstract_;
2134 }
2135
2136 // Hash code.
2137
2138 unsigned int
2139 Complex_type::do_hash_for_method(Gogo*) const
2140 {
2141   return (this->bits_ << 4) + ((this->is_abstract_ ? 1 : 0) << 8);
2142 }
2143
2144 // Convert to the backend representation.
2145
2146 Btype*
2147 Complex_type::do_get_backend(Gogo* gogo)
2148 {
2149   return gogo->backend()->complex_type(this->bits_);
2150 }
2151
2152 // The type descriptor for a complex type.  Complex types are always
2153 // named.
2154
2155 Expression*
2156 Complex_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2157 {
2158   go_assert(name != NULL);
2159   return this->plain_type_descriptor(gogo, this->runtime_type_kind_, name);
2160 }
2161
2162 // We should not be asked for the reflection string of a basic type.
2163
2164 void
2165 Complex_type::do_reflection(Gogo*, std::string*) const
2166 {
2167   go_assert(saw_errors());
2168 }
2169
2170 // Mangled name.
2171
2172 void
2173 Complex_type::do_mangled_name(Gogo*, std::string* ret) const
2174 {
2175   char buf[100];
2176   snprintf(buf, sizeof buf, "c%s%de",
2177            this->is_abstract_ ? "a" : "",
2178            this->bits_);
2179   ret->append(buf);
2180 }
2181
2182 // Make a complex type.
2183
2184 Named_type*
2185 Type::make_complex_type(const char* name, int bits, int runtime_type_kind)
2186 {
2187   return Complex_type::create_complex_type(name, bits, runtime_type_kind);
2188 }
2189
2190 // Make an abstract complex type.
2191
2192 Complex_type*
2193 Type::make_abstract_complex_type()
2194 {
2195   return Complex_type::create_abstract_complex_type();
2196 }
2197
2198 // Look up a complex type.
2199
2200 Named_type*
2201 Type::lookup_complex_type(const char* name)
2202 {
2203   return Complex_type::lookup_complex_type(name);
2204 }
2205
2206 // Class String_type.
2207
2208 // Convert String_type to the backend representation.  A string is a
2209 // struct with two fields: a pointer to the characters and a length.
2210
2211 Btype*
2212 String_type::do_get_backend(Gogo* gogo)
2213 {
2214   static Btype* backend_string_type;
2215   if (backend_string_type == NULL)
2216     {
2217       std::vector<Backend::Btyped_identifier> fields(2);
2218
2219       Type* b = gogo->lookup_global("byte")->type_value();
2220       Type* pb = Type::make_pointer_type(b);
2221       fields[0].name = "__data";
2222       fields[0].btype = pb->get_backend(gogo);
2223       fields[0].location = Linemap::predeclared_location();
2224
2225       Type* int_type = Type::lookup_integer_type("int");
2226       fields[1].name = "__length";
2227       fields[1].btype = int_type->get_backend(gogo);
2228       fields[1].location = fields[0].location;
2229
2230       backend_string_type = gogo->backend()->struct_type(fields);
2231     }
2232   return backend_string_type;
2233 }
2234
2235 // Return a tree for the length of STRING.
2236
2237 tree
2238 String_type::length_tree(Gogo*, tree string)
2239 {
2240   tree string_type = TREE_TYPE(string);
2241   go_assert(TREE_CODE(string_type) == RECORD_TYPE);
2242   tree length_field = DECL_CHAIN(TYPE_FIELDS(string_type));
2243   go_assert(strcmp(IDENTIFIER_POINTER(DECL_NAME(length_field)),
2244                     "__length") == 0);
2245   return fold_build3(COMPONENT_REF, integer_type_node, string,
2246                      length_field, NULL_TREE);
2247 }
2248
2249 // Return a tree for a pointer to the bytes of STRING.
2250
2251 tree
2252 String_type::bytes_tree(Gogo*, tree string)
2253 {
2254   tree string_type = TREE_TYPE(string);
2255   go_assert(TREE_CODE(string_type) == RECORD_TYPE);
2256   tree bytes_field = TYPE_FIELDS(string_type);
2257   go_assert(strcmp(IDENTIFIER_POINTER(DECL_NAME(bytes_field)),
2258                     "__data") == 0);
2259   return fold_build3(COMPONENT_REF, TREE_TYPE(bytes_field), string,
2260                      bytes_field, NULL_TREE);
2261 }
2262
2263 // The type descriptor for the string type.
2264
2265 Expression*
2266 String_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2267 {
2268   if (name != NULL)
2269     return this->plain_type_descriptor(gogo, RUNTIME_TYPE_KIND_STRING, name);
2270   else
2271     {
2272       Named_object* no = gogo->lookup_global("string");
2273       go_assert(no != NULL);
2274       return Type::type_descriptor(gogo, no->type_value());
2275     }
2276 }
2277
2278 // We should not be asked for the reflection string of a basic type.
2279
2280 void
2281 String_type::do_reflection(Gogo*, std::string* ret) const
2282 {
2283   ret->append("string");
2284 }
2285
2286 // Mangled name of a string type.
2287
2288 void
2289 String_type::do_mangled_name(Gogo*, std::string* ret) const
2290 {
2291   ret->push_back('z');
2292 }
2293
2294 // Make a string type.
2295
2296 Type*
2297 Type::make_string_type()
2298 {
2299   static String_type string_type;
2300   return &string_type;
2301 }
2302
2303 // The named type "string".
2304
2305 static Named_type* named_string_type;
2306
2307 // Get the named type "string".
2308
2309 Named_type*
2310 Type::lookup_string_type()
2311 {
2312   return named_string_type;
2313 }
2314
2315 // Make the named type string.
2316
2317 Named_type*
2318 Type::make_named_string_type()
2319 {
2320   Type* string_type = Type::make_string_type();
2321   Named_object* named_object =
2322     Named_object::make_type("string", NULL, string_type,
2323                             Linemap::predeclared_location());
2324   Named_type* named_type = named_object->type_value();
2325   named_string_type = named_type;
2326   return named_type;
2327 }
2328
2329 // The sink type.  This is the type of the blank identifier _.  Any
2330 // type may be assigned to it.
2331
2332 class Sink_type : public Type
2333 {
2334  public:
2335   Sink_type()
2336     : Type(TYPE_SINK)
2337   { }
2338
2339  protected:
2340   Btype*
2341   do_get_backend(Gogo*)
2342   { go_unreachable(); }
2343
2344   Expression*
2345   do_type_descriptor(Gogo*, Named_type*)
2346   { go_unreachable(); }
2347
2348   void
2349   do_reflection(Gogo*, std::string*) const
2350   { go_unreachable(); }
2351
2352   void
2353   do_mangled_name(Gogo*, std::string*) const
2354   { go_unreachable(); }
2355 };
2356
2357 // Make the sink type.
2358
2359 Type*
2360 Type::make_sink_type()
2361 {
2362   static Sink_type sink_type;
2363   return &sink_type;
2364 }
2365
2366 // Class Function_type.
2367
2368 // Traversal.
2369
2370 int
2371 Function_type::do_traverse(Traverse* traverse)
2372 {
2373   if (this->receiver_ != NULL
2374       && Type::traverse(this->receiver_->type(), traverse) == TRAVERSE_EXIT)
2375     return TRAVERSE_EXIT;
2376   if (this->parameters_ != NULL
2377       && this->parameters_->traverse(traverse) == TRAVERSE_EXIT)
2378     return TRAVERSE_EXIT;
2379   if (this->results_ != NULL
2380       && this->results_->traverse(traverse) == TRAVERSE_EXIT)
2381     return TRAVERSE_EXIT;
2382   return TRAVERSE_CONTINUE;
2383 }
2384
2385 // Returns whether T is a valid redeclaration of this type.  If this
2386 // returns false, and REASON is not NULL, *REASON may be set to a
2387 // brief explanation of why it returned false.
2388
2389 bool
2390 Function_type::is_valid_redeclaration(const Function_type* t,
2391                                       std::string* reason) const
2392 {
2393   if (!this->is_identical(t, false, true, reason))
2394     return false;
2395
2396   // A redeclaration of a function is required to use the same names
2397   // for the receiver and parameters.
2398   if (this->receiver() != NULL
2399       && this->receiver()->name() != t->receiver()->name()
2400       && this->receiver()->name() != Import::import_marker
2401       && t->receiver()->name() != Import::import_marker)
2402     {
2403       if (reason != NULL)
2404         *reason = "receiver name changed";
2405       return false;
2406     }
2407
2408   const Typed_identifier_list* parms1 = this->parameters();
2409   const Typed_identifier_list* parms2 = t->parameters();
2410   if (parms1 != NULL)
2411     {
2412       Typed_identifier_list::const_iterator p1 = parms1->begin();
2413       for (Typed_identifier_list::const_iterator p2 = parms2->begin();
2414            p2 != parms2->end();
2415            ++p2, ++p1)
2416         {
2417           if (p1->name() != p2->name()
2418               && p1->name() != Import::import_marker
2419               && p2->name() != Import::import_marker)
2420             {
2421               if (reason != NULL)
2422                 *reason = "parameter name changed";
2423               return false;
2424             }
2425
2426           // This is called at parse time, so we may have unknown
2427           // types.
2428           Type* t1 = p1->type()->forwarded();
2429           Type* t2 = p2->type()->forwarded();
2430           if (t1 != t2
2431               && t1->forward_declaration_type() != NULL
2432               && (t2->forward_declaration_type() == NULL
2433                   || (t1->forward_declaration_type()->named_object()
2434                       != t2->forward_declaration_type()->named_object())))
2435             return false;
2436         }
2437     }
2438
2439   const Typed_identifier_list* results1 = this->results();
2440   const Typed_identifier_list* results2 = t->results();
2441   if (results1 != NULL)
2442     {
2443       Typed_identifier_list::const_iterator res1 = results1->begin();
2444       for (Typed_identifier_list::const_iterator res2 = results2->begin();
2445            res2 != results2->end();
2446            ++res2, ++res1)
2447         {
2448           if (res1->name() != res2->name()
2449               && res1->name() != Import::import_marker
2450               && res2->name() != Import::import_marker)
2451             {
2452               if (reason != NULL)
2453                 *reason = "result name changed";
2454               return false;
2455             }
2456
2457           // This is called at parse time, so we may have unknown
2458           // types.
2459           Type* t1 = res1->type()->forwarded();
2460           Type* t2 = res2->type()->forwarded();
2461           if (t1 != t2
2462               && t1->forward_declaration_type() != NULL
2463               && (t2->forward_declaration_type() == NULL
2464                   || (t1->forward_declaration_type()->named_object()
2465                       != t2->forward_declaration_type()->named_object())))
2466             return false;
2467         }
2468     }
2469
2470   return true;
2471 }
2472
2473 // Check whether T is the same as this type.
2474
2475 bool
2476 Function_type::is_identical(const Function_type* t, bool ignore_receiver,
2477                             bool errors_are_identical,
2478                             std::string* reason) const
2479 {
2480   if (!ignore_receiver)
2481     {
2482       const Typed_identifier* r1 = this->receiver();
2483       const Typed_identifier* r2 = t->receiver();
2484       if ((r1 != NULL) != (r2 != NULL))
2485         {
2486           if (reason != NULL)
2487             *reason = _("different receiver types");
2488           return false;
2489         }
2490       if (r1 != NULL)
2491         {
2492           if (!Type::are_identical(r1->type(), r2->type(), errors_are_identical,
2493                                    reason))
2494             {
2495               if (reason != NULL && !reason->empty())
2496                 *reason = "receiver: " + *reason;
2497               return false;
2498             }
2499         }
2500     }
2501
2502   const Typed_identifier_list* parms1 = this->parameters();
2503   const Typed_identifier_list* parms2 = t->parameters();
2504   if ((parms1 != NULL) != (parms2 != NULL))
2505     {
2506       if (reason != NULL)
2507         *reason = _("different number of parameters");
2508       return false;
2509     }
2510   if (parms1 != NULL)
2511     {
2512       Typed_identifier_list::const_iterator p1 = parms1->begin();
2513       for (Typed_identifier_list::const_iterator p2 = parms2->begin();
2514            p2 != parms2->end();
2515            ++p2, ++p1)
2516         {
2517           if (p1 == parms1->end())
2518             {
2519               if (reason != NULL)
2520                 *reason = _("different number of parameters");
2521               return false;
2522             }
2523
2524           if (!Type::are_identical(p1->type(), p2->type(),
2525                                    errors_are_identical, NULL))
2526             {
2527               if (reason != NULL)
2528                 *reason = _("different parameter types");
2529               return false;
2530             }
2531         }
2532       if (p1 != parms1->end())
2533         {
2534           if (reason != NULL)
2535             *reason = _("different number of parameters");
2536         return false;
2537         }
2538     }
2539
2540   if (this->is_varargs() != t->is_varargs())
2541     {
2542       if (reason != NULL)
2543         *reason = _("different varargs");
2544       return false;
2545     }
2546
2547   const Typed_identifier_list* results1 = this->results();
2548   const Typed_identifier_list* results2 = t->results();
2549   if ((results1 != NULL) != (results2 != NULL))
2550     {
2551       if (reason != NULL)
2552         *reason = _("different number of results");
2553       return false;
2554     }
2555   if (results1 != NULL)
2556     {
2557       Typed_identifier_list::const_iterator res1 = results1->begin();
2558       for (Typed_identifier_list::const_iterator res2 = results2->begin();
2559            res2 != results2->end();
2560            ++res2, ++res1)
2561         {
2562           if (res1 == results1->end())
2563             {
2564               if (reason != NULL)
2565                 *reason = _("different number of results");
2566               return false;
2567             }
2568
2569           if (!Type::are_identical(res1->type(), res2->type(),
2570                                    errors_are_identical, NULL))
2571             {
2572               if (reason != NULL)
2573                 *reason = _("different result types");
2574               return false;
2575             }
2576         }
2577       if (res1 != results1->end())
2578         {
2579           if (reason != NULL)
2580             *reason = _("different number of results");
2581           return false;
2582         }
2583     }
2584
2585   return true;
2586 }
2587
2588 // Hash code.
2589
2590 unsigned int
2591 Function_type::do_hash_for_method(Gogo* gogo) const
2592 {
2593   unsigned int ret = 0;
2594   // We ignore the receiver type for hash codes, because we need to
2595   // get the same hash code for a method in an interface and a method
2596   // declared for a type.  The former will not have a receiver.
2597   if (this->parameters_ != NULL)
2598     {
2599       int shift = 1;
2600       for (Typed_identifier_list::const_iterator p = this->parameters_->begin();
2601            p != this->parameters_->end();
2602            ++p, ++shift)
2603         ret += p->type()->hash_for_method(gogo) << shift;
2604     }
2605   if (this->results_ != NULL)
2606     {
2607       int shift = 2;
2608       for (Typed_identifier_list::const_iterator p = this->results_->begin();
2609            p != this->results_->end();
2610            ++p, ++shift)
2611         ret += p->type()->hash_for_method(gogo) << shift;
2612     }
2613   if (this->is_varargs_)
2614     ret += 1;
2615   ret <<= 4;
2616   return ret;
2617 }
2618
2619 // Get the backend representation for a function type.
2620
2621 Btype*
2622 Function_type::get_function_backend(Gogo* gogo)
2623 {
2624   Backend::Btyped_identifier breceiver;
2625   if (this->receiver_ != NULL)
2626     {
2627       breceiver.name = Gogo::unpack_hidden_name(this->receiver_->name());
2628
2629       // We always pass the address of the receiver parameter, in
2630       // order to make interface calls work with unknown types.
2631       Type* rtype = this->receiver_->type();
2632       if (rtype->points_to() == NULL)
2633         rtype = Type::make_pointer_type(rtype);
2634       breceiver.btype = rtype->get_backend(gogo);
2635       breceiver.location = this->receiver_->location();
2636     }
2637
2638   std::vector<Backend::Btyped_identifier> bparameters;
2639   if (this->parameters_ != NULL)
2640     {
2641       bparameters.resize(this->parameters_->size());
2642       size_t i = 0;
2643       for (Typed_identifier_list::const_iterator p = this->parameters_->begin();
2644            p != this->parameters_->end();
2645            ++p, ++i)
2646         {
2647           bparameters[i].name = Gogo::unpack_hidden_name(p->name());
2648           bparameters[i].btype = p->type()->get_backend(gogo);
2649           bparameters[i].location = p->location();
2650         }
2651       go_assert(i == bparameters.size());
2652     }
2653
2654   std::vector<Backend::Btyped_identifier> bresults;
2655   if (this->results_ != NULL)
2656     {
2657       bresults.resize(this->results_->size());
2658       size_t i = 0;
2659       for (Typed_identifier_list::const_iterator p = this->results_->begin();
2660            p != this->results_->end();
2661            ++p, ++i)
2662         {
2663           bresults[i].name = Gogo::unpack_hidden_name(p->name());
2664           bresults[i].btype = p->type()->get_backend(gogo);
2665           bresults[i].location = p->location();
2666         }
2667       go_assert(i == bresults.size());
2668     }
2669
2670   return gogo->backend()->function_type(breceiver, bparameters, bresults,
2671                                         this->location());
2672 }
2673
2674 // A hash table mapping function types to their backend placeholders.
2675
2676 Function_type::Placeholders Function_type::placeholders;
2677
2678 // Get the backend representation for a function type.  If we are
2679 // still converting types, and this types has multiple results, return
2680 // a placeholder instead.  We do this because for multiple results we
2681 // build a struct, and we need to make sure that all the types in the
2682 // struct are valid before we create the struct.
2683
2684 Btype*
2685 Function_type::do_get_backend(Gogo* gogo)
2686 {
2687   if (!gogo->named_types_are_converted()
2688       && this->results_ != NULL
2689       && this->results_->size() > 1)
2690     {
2691       Btype* placeholder =
2692         gogo->backend()->placeholder_pointer_type("", this->location(), true);
2693       Function_type::placeholders.push_back(std::make_pair(this, placeholder));
2694       return placeholder;
2695     }
2696   return this->get_function_backend(gogo);
2697 }
2698
2699 // Convert function types after all named types are converted.
2700
2701 void
2702 Function_type::convert_types(Gogo* gogo)
2703 {
2704   for (Placeholders::const_iterator p = Function_type::placeholders.begin();
2705        p != Function_type::placeholders.end();
2706        ++p)
2707     {
2708       Btype* bt = p->first->get_function_backend(gogo);
2709       if (!gogo->backend()->set_placeholder_function_type(p->second, bt))
2710         go_assert(saw_errors());
2711     }
2712 }
2713
2714 // The type of a function type descriptor.
2715
2716 Type*
2717 Function_type::make_function_type_descriptor_type()
2718 {
2719   static Type* ret;
2720   if (ret == NULL)
2721     {
2722       Type* tdt = Type::make_type_descriptor_type();
2723       Type* ptdt = Type::make_type_descriptor_ptr_type();
2724
2725       Type* bool_type = Type::lookup_bool_type();
2726
2727       Type* slice_type = Type::make_array_type(ptdt, NULL);
2728
2729       Struct_type* s = Type::make_builtin_struct_type(4,
2730                                                       "", tdt,
2731                                                       "dotdotdot", bool_type,
2732                                                       "in", slice_type,
2733                                                       "out", slice_type);
2734
2735       ret = Type::make_builtin_named_type("FuncType", s);
2736     }
2737
2738   return ret;
2739 }
2740
2741 // The type descriptor for a function type.
2742
2743 Expression*
2744 Function_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2745 {
2746   Location bloc = Linemap::predeclared_location();
2747
2748   Type* ftdt = Function_type::make_function_type_descriptor_type();
2749
2750   const Struct_field_list* fields = ftdt->struct_type()->fields();
2751
2752   Expression_list* vals = new Expression_list();
2753   vals->reserve(4);
2754
2755   Struct_field_list::const_iterator p = fields->begin();
2756   go_assert(p->is_field_name("commonType"));
2757   vals->push_back(this->type_descriptor_constructor(gogo,
2758                                                     RUNTIME_TYPE_KIND_FUNC,
2759                                                     name, NULL, true));
2760
2761   ++p;
2762   go_assert(p->is_field_name("dotdotdot"));
2763   vals->push_back(Expression::make_boolean(this->is_varargs(), bloc));
2764
2765   ++p;
2766   go_assert(p->is_field_name("in"));
2767   vals->push_back(this->type_descriptor_params(p->type(), this->receiver(),
2768                                                this->parameters()));
2769
2770   ++p;
2771   go_assert(p->is_field_name("out"));
2772   vals->push_back(this->type_descriptor_params(p->type(), NULL,
2773                                                this->results()));
2774
2775   ++p;
2776   go_assert(p == fields->end());
2777
2778   return Expression::make_struct_composite_literal(ftdt, vals, bloc);
2779 }
2780
2781 // Return a composite literal for the parameters or results of a type
2782 // descriptor.
2783
2784 Expression*
2785 Function_type::type_descriptor_params(Type* params_type,
2786                                       const Typed_identifier* receiver,
2787                                       const Typed_identifier_list* params)
2788 {
2789   Location bloc = Linemap::predeclared_location();
2790
2791   if (receiver == NULL && params == NULL)
2792     return Expression::make_slice_composite_literal(params_type, NULL, bloc);
2793
2794   Expression_list* vals = new Expression_list();
2795   vals->reserve((params == NULL ? 0 : params->size())
2796                 + (receiver != NULL ? 1 : 0));
2797
2798   if (receiver != NULL)
2799     vals->push_back(Expression::make_type_descriptor(receiver->type(), bloc));
2800
2801   if (params != NULL)
2802     {
2803       for (Typed_identifier_list::const_iterator p = params->begin();
2804            p != params->end();
2805            ++p)
2806         vals->push_back(Expression::make_type_descriptor(p->type(), bloc));
2807     }
2808
2809   return Expression::make_slice_composite_literal(params_type, vals, bloc);
2810 }
2811
2812 // The reflection string.
2813
2814 void
2815 Function_type::do_reflection(Gogo* gogo, std::string* ret) const
2816 {
2817   // FIXME: Turn this off until we straighten out the type of the
2818   // struct field used in a go statement which calls a method.
2819   // go_assert(this->receiver_ == NULL);
2820
2821   ret->append("func");
2822
2823   if (this->receiver_ != NULL)
2824     {
2825       ret->push_back('(');
2826       this->append_reflection(this->receiver_->type(), gogo, ret);
2827       ret->push_back(')');
2828     }
2829
2830   ret->push_back('(');
2831   const Typed_identifier_list* params = this->parameters();
2832   if (params != NULL)
2833     {
2834       bool is_varargs = this->is_varargs_;
2835       for (Typed_identifier_list::const_iterator p = params->begin();
2836            p != params->end();
2837            ++p)
2838         {
2839           if (p != params->begin())
2840             ret->append(", ");
2841           if (!is_varargs || p + 1 != params->end())
2842             this->append_reflection(p->type(), gogo, ret);
2843           else
2844             {
2845               ret->append("...");
2846               this->append_reflection(p->type()->array_type()->element_type(),
2847                                       gogo, ret);
2848             }
2849         }
2850     }
2851   ret->push_back(')');
2852
2853   const Typed_identifier_list* results = this->results();
2854   if (results != NULL && !results->empty())
2855     {
2856       if (results->size() == 1)
2857         ret->push_back(' ');
2858       else
2859         ret->append(" (");
2860       for (Typed_identifier_list::const_iterator p = results->begin();
2861            p != results->end();
2862            ++p)
2863         {
2864           if (p != results->begin())
2865             ret->append(", ");
2866           this->append_reflection(p->type(), gogo, ret);
2867         }
2868       if (results->size() > 1)
2869         ret->push_back(')');
2870     }
2871 }
2872
2873 // Mangled name.
2874
2875 void
2876 Function_type::do_mangled_name(Gogo* gogo, std::string* ret) const
2877 {
2878   ret->push_back('F');
2879
2880   if (this->receiver_ != NULL)
2881     {
2882       ret->push_back('m');
2883       this->append_mangled_name(this->receiver_->type(), gogo, ret);
2884     }
2885
2886   const Typed_identifier_list* params = this->parameters();
2887   if (params != NULL)
2888     {
2889       ret->push_back('p');
2890       for (Typed_identifier_list::const_iterator p = params->begin();
2891            p != params->end();
2892            ++p)
2893         this->append_mangled_name(p->type(), gogo, ret);
2894       if (this->is_varargs_)
2895         ret->push_back('V');
2896       ret->push_back('e');
2897     }
2898
2899   const Typed_identifier_list* results = this->results();
2900   if (results != NULL)
2901     {
2902       ret->push_back('r');
2903       for (Typed_identifier_list::const_iterator p = results->begin();
2904            p != results->end();
2905            ++p)
2906         this->append_mangled_name(p->type(), gogo, ret);
2907       ret->push_back('e');
2908     }
2909
2910   ret->push_back('e');
2911 }
2912
2913 // Export a function type.
2914
2915 void
2916 Function_type::do_export(Export* exp) const
2917 {
2918   // We don't write out the receiver.  The only function types which
2919   // should have a receiver are the ones associated with explicitly
2920   // defined methods.  For those the receiver type is written out by
2921   // Function::export_func.
2922
2923   exp->write_c_string("(");
2924   bool first = true;
2925   if (this->parameters_ != NULL)
2926     {
2927       bool is_varargs = this->is_varargs_;
2928       for (Typed_identifier_list::const_iterator p =
2929              this->parameters_->begin();
2930            p != this->parameters_->end();
2931            ++p)
2932         {
2933           if (first)
2934             first = false;
2935           else
2936             exp->write_c_string(", ");
2937           if (!is_varargs || p + 1 != this->parameters_->end())
2938             exp->write_type(p->type());
2939           else
2940             {
2941               exp->write_c_string("...");
2942               exp->write_type(p->type()->array_type()->element_type());
2943             }
2944         }
2945     }
2946   exp->write_c_string(")");
2947
2948   const Typed_identifier_list* results = this->results_;
2949   if (results != NULL)
2950     {
2951       exp->write_c_string(" ");
2952       if (results->size() == 1)
2953         exp->write_type(results->begin()->type());
2954       else
2955         {
2956           first = true;
2957           exp->write_c_string("(");
2958           for (Typed_identifier_list::const_iterator p = results->begin();
2959                p != results->end();
2960                ++p)
2961             {
2962               if (first)
2963                 first = false;
2964               else
2965                 exp->write_c_string(", ");
2966               exp->write_type(p->type());
2967             }
2968           exp->write_c_string(")");
2969         }
2970     }
2971 }
2972
2973 // Import a function type.
2974
2975 Function_type*
2976 Function_type::do_import(Import* imp)
2977 {
2978   imp->require_c_string("(");
2979   Typed_identifier_list* parameters;
2980   bool is_varargs = false;
2981   if (imp->peek_char() == ')')
2982     parameters = NULL;
2983   else
2984     {
2985       parameters = new Typed_identifier_list();
2986       while (true)
2987         {
2988           if (imp->match_c_string("..."))
2989             {
2990               imp->advance(3);
2991               is_varargs = true;
2992             }
2993
2994           Type* ptype = imp->read_type();
2995           if (is_varargs)
2996             ptype = Type::make_array_type(ptype, NULL);
2997           parameters->push_back(Typed_identifier(Import::import_marker,
2998                                                  ptype, imp->location()));
2999           if (imp->peek_char() != ',')
3000             break;
3001           go_assert(!is_varargs);
3002           imp->require_c_string(", ");
3003         }
3004     }
3005   imp->require_c_string(")");
3006
3007   Typed_identifier_list* results;
3008   if (imp->peek_char() != ' ')
3009     results = NULL;
3010   else
3011     {
3012       imp->advance(1);
3013       results = new Typed_identifier_list;
3014       if (imp->peek_char() != '(')
3015         {
3016           Type* rtype = imp->read_type();
3017           results->push_back(Typed_identifier(Import::import_marker, rtype,
3018                                               imp->location()));
3019         }
3020       else
3021         {
3022           imp->advance(1);
3023           while (true)
3024             {
3025               Type* rtype = imp->read_type();
3026               results->push_back(Typed_identifier(Import::import_marker,
3027                                                   rtype, imp->location()));
3028               if (imp->peek_char() != ',')
3029                 break;
3030               imp->require_c_string(", ");
3031             }
3032           imp->require_c_string(")");
3033         }
3034     }
3035
3036   Function_type* ret = Type::make_function_type(NULL, parameters, results,
3037                                                 imp->location());
3038   if (is_varargs)
3039     ret->set_is_varargs();
3040   return ret;
3041 }
3042
3043 // Make a copy of a function type without a receiver.
3044
3045 Function_type*
3046 Function_type::copy_without_receiver() const
3047 {
3048   go_assert(this->is_method());
3049   Function_type *ret = Type::make_function_type(NULL, this->parameters_,
3050                                                 this->results_,
3051                                                 this->location_);
3052   if (this->is_varargs())
3053     ret->set_is_varargs();
3054   if (this->is_builtin())
3055     ret->set_is_builtin();
3056   return ret;
3057 }
3058
3059 // Make a copy of a function type with a receiver.
3060
3061 Function_type*
3062 Function_type::copy_with_receiver(Type* receiver_type) const
3063 {
3064   go_assert(!this->is_method());
3065   Typed_identifier* receiver = new Typed_identifier("", receiver_type,
3066                                                     this->location_);
3067   return Type::make_function_type(receiver, this->parameters_,
3068                                   this->results_, this->location_);
3069 }
3070
3071 // Make a function type.
3072
3073 Function_type*
3074 Type::make_function_type(Typed_identifier* receiver,
3075                          Typed_identifier_list* parameters,
3076                          Typed_identifier_list* results,
3077                          Location location)
3078 {
3079   return new Function_type(receiver, parameters, results, location);
3080 }
3081
3082 // Class Pointer_type.
3083
3084 // Traversal.
3085
3086 int
3087 Pointer_type::do_traverse(Traverse* traverse)
3088 {
3089   return Type::traverse(this->to_type_, traverse);
3090 }
3091
3092 // Hash code.
3093
3094 unsigned int
3095 Pointer_type::do_hash_for_method(Gogo* gogo) const
3096 {
3097   return this->to_type_->hash_for_method(gogo) << 4;
3098 }
3099
3100 // The tree for a pointer type.
3101
3102 Btype*
3103 Pointer_type::do_get_backend(Gogo* gogo)
3104 {
3105   Btype* to_btype = this->to_type_->get_backend(gogo);
3106   return gogo->backend()->pointer_type(to_btype);
3107 }
3108
3109 // The type of a pointer type descriptor.
3110
3111 Type*
3112 Pointer_type::make_pointer_type_descriptor_type()
3113 {
3114   static Type* ret;
3115   if (ret == NULL)
3116     {
3117       Type* tdt = Type::make_type_descriptor_type();
3118       Type* ptdt = Type::make_type_descriptor_ptr_type();
3119
3120       Struct_type* s = Type::make_builtin_struct_type(2,
3121                                                       "", tdt,
3122                                                       "elem", ptdt);
3123
3124       ret = Type::make_builtin_named_type("PtrType", s);
3125     }
3126
3127   return ret;
3128 }
3129
3130 // The type descriptor for a pointer type.
3131
3132 Expression*
3133 Pointer_type::do_type_descriptor(Gogo* gogo, Named_type* name)
3134 {
3135   if (this->is_unsafe_pointer_type())
3136     {
3137       go_assert(name != NULL);
3138       return this->plain_type_descriptor(gogo,
3139                                          RUNTIME_TYPE_KIND_UNSAFE_POINTER,
3140                                          name);
3141     }
3142   else
3143     {
3144       Location bloc = Linemap::predeclared_location();
3145
3146       const Methods* methods;
3147       Type* deref = this->points_to();
3148       if (deref->named_type() != NULL)
3149         methods = deref->named_type()->methods();
3150       else if (deref->struct_type() != NULL)
3151         methods = deref->struct_type()->methods();
3152       else
3153         methods = NULL;
3154
3155       Type* ptr_tdt = Pointer_type::make_pointer_type_descriptor_type();
3156
3157       const Struct_field_list* fields = ptr_tdt->struct_type()->fields();
3158
3159       Expression_list* vals = new Expression_list();
3160       vals->reserve(2);
3161
3162       Struct_field_list::const_iterator p = fields->begin();
3163       go_assert(p->is_field_name("commonType"));
3164       vals->push_back(this->type_descriptor_constructor(gogo,
3165                                                         RUNTIME_TYPE_KIND_PTR,
3166                                                         name, methods, false));
3167
3168       ++p;
3169       go_assert(p->is_field_name("elem"));
3170       vals->push_back(Expression::make_type_descriptor(deref, bloc));
3171
3172       return Expression::make_struct_composite_literal(ptr_tdt, vals, bloc);
3173     }
3174 }
3175
3176 // Reflection string.
3177
3178 void
3179 Pointer_type::do_reflection(Gogo* gogo, std::string* ret) const
3180 {
3181   ret->push_back('*');
3182   this->append_reflection(this->to_type_, gogo, ret);
3183 }
3184
3185 // Mangled name.
3186
3187 void
3188 Pointer_type::do_mangled_name(Gogo* gogo, std::string* ret) const
3189 {
3190   ret->push_back('p');
3191   this->append_mangled_name(this->to_type_, gogo, ret);
3192 }
3193
3194 // Export.
3195
3196 void
3197 Pointer_type::do_export(Export* exp) const
3198 {
3199   exp->write_c_string("*");
3200   if (this->is_unsafe_pointer_type())
3201     exp->write_c_string("any");
3202   else
3203     exp->write_type(this->to_type_);
3204 }
3205
3206 // Import.
3207
3208 Pointer_type*
3209 Pointer_type::do_import(Import* imp)
3210 {
3211   imp->require_c_string("*");
3212   if (imp->match_c_string("any"))
3213     {
3214       imp->advance(3);
3215       return Type::make_pointer_type(Type::make_void_type());
3216     }
3217   Type* to = imp->read_type();
3218   return Type::make_pointer_type(to);
3219 }
3220
3221 // Make a pointer type.
3222
3223 Pointer_type*
3224 Type::make_pointer_type(Type* to_type)
3225 {
3226   typedef Unordered_map(Type*, Pointer_type*) Hashtable;
3227   static Hashtable pointer_types;
3228   Hashtable::const_iterator p = pointer_types.find(to_type);
3229   if (p != pointer_types.end())
3230     return p->second;
3231   Pointer_type* ret = new Pointer_type(to_type);
3232   pointer_types[to_type] = ret;
3233   return ret;
3234 }
3235
3236 // The nil type.  We use a special type for nil because it is not the
3237 // same as any other type.  In C term nil has type void*, but there is
3238 // no such type in Go.
3239
3240 class Nil_type : public Type
3241 {
3242  public:
3243   Nil_type()
3244     : Type(TYPE_NIL)
3245   { }
3246
3247  protected:
3248   Btype*
3249   do_get_backend(Gogo* gogo)
3250   { return gogo->backend()->pointer_type(gogo->backend()->void_type()); }
3251
3252   Expression*
3253   do_type_descriptor(Gogo*, Named_type*)
3254   { go_unreachable(); }
3255
3256   void
3257   do_reflection(Gogo*, std::string*) const
3258   { go_unreachable(); }
3259
3260   void
3261   do_mangled_name(Gogo*, std::string* ret) const
3262   { ret->push_back('n'); }
3263 };
3264
3265 // Make the nil type.
3266
3267 Type*
3268 Type::make_nil_type()
3269 {
3270   static Nil_type singleton_nil_type;
3271   return &singleton_nil_type;
3272 }
3273
3274 // The type of a function call which returns multiple values.  This is
3275 // really a struct, but we don't want to confuse a function call which
3276 // returns a struct with a function call which returns multiple
3277 // values.
3278
3279 class Call_multiple_result_type : public Type
3280 {
3281  public:
3282   Call_multiple_result_type(Call_expression* call)
3283     : Type(TYPE_CALL_MULTIPLE_RESULT),
3284       call_(call)
3285   { }
3286
3287  protected:
3288   bool
3289   do_has_pointer() const
3290   {
3291     go_assert(saw_errors());
3292     return false;
3293   }
3294
3295   Btype*
3296   do_get_backend(Gogo* gogo)
3297   {
3298     go_assert(saw_errors());
3299     return gogo->backend()->error_type();
3300   }
3301
3302   Expression*
3303   do_type_descriptor(Gogo*, Named_type*)
3304   {
3305     go_assert(saw_errors());
3306     return Expression::make_error(Linemap::unknown_location());
3307   }
3308
3309   void
3310   do_reflection(Gogo*, std::string*) const
3311   { go_assert(saw_errors()); }
3312
3313   void
3314   do_mangled_name(Gogo*, std::string*) const
3315   { go_assert(saw_errors()); }
3316
3317  private:
3318   // The expression being called.
3319   Call_expression* call_;
3320 };
3321
3322 // Make a call result type.
3323
3324 Type*
3325 Type::make_call_multiple_result_type(Call_expression* call)
3326 {
3327   return new Call_multiple_result_type(call);
3328 }
3329
3330 // Class Struct_field.
3331
3332 // Get the name of a field.
3333
3334 const std::string&
3335 Struct_field::field_name() const
3336 {
3337   const std::string& name(this->typed_identifier_.name());
3338   if (!name.empty())
3339     return name;
3340   else
3341     {
3342       // This is called during parsing, before anything is lowered, so
3343       // we have to be pretty careful to avoid dereferencing an
3344       // unknown type name.
3345       Type* t = this->typed_identifier_.type();
3346       Type* dt = t;
3347       if (t->classification() == Type::TYPE_POINTER)
3348         {
3349           // Very ugly.
3350           Pointer_type* ptype = static_cast<Pointer_type*>(t);
3351           dt = ptype->points_to();
3352         }
3353       if (dt->forward_declaration_type() != NULL)
3354         return dt->forward_declaration_type()->name();
3355       else if (dt->named_type() != NULL)
3356         return dt->named_type()->name();
3357       else if (t->is_error_type() || dt->is_error_type())
3358         {
3359           static const std::string error_string = "*error*";
3360           return error_string;
3361         }
3362       else
3363         {
3364           // Avoid crashing in the erroneous case where T is named but
3365           // DT is not.
3366           go_assert(t != dt);
3367           if (t->forward_declaration_type() != NULL)
3368             return t->forward_declaration_type()->name();
3369           else if (t->named_type() != NULL)
3370             return t->named_type()->name();
3371           else
3372             go_unreachable();
3373         }
3374     }
3375 }
3376
3377 // Return whether this field is named NAME.
3378
3379 bool
3380 Struct_field::is_field_name(const std::string& name) const
3381 {
3382   const std::string& me(this->typed_identifier_.name());
3383   if (!me.empty())
3384     return me == name;
3385   else
3386     {
3387       Type* t = this->typed_identifier_.type();
3388       if (t->points_to() != NULL)
3389         t = t->points_to();
3390       Named_type* nt = t->named_type();
3391       if (nt != NULL && nt->name() == name)
3392         return true;
3393
3394       // This is a horrible hack caused by the fact that we don't pack
3395       // the names of builtin types.  FIXME.
3396       if (nt != NULL
3397           && nt->is_builtin()
3398           && nt->name() == Gogo::unpack_hidden_name(name))
3399         return true;
3400
3401       return false;
3402     }
3403 }
3404
3405 // Class Struct_type.
3406
3407 // Traversal.
3408
3409 int
3410 Struct_type::do_traverse(Traverse* traverse)
3411 {
3412   Struct_field_list* fields = this->fields_;
3413   if (fields != NULL)
3414     {
3415       for (Struct_field_list::iterator p = fields->begin();
3416            p != fields->end();
3417            ++p)
3418         {
3419           if (Type::traverse(p->type(), traverse) == TRAVERSE_EXIT)
3420             return TRAVERSE_EXIT;
3421         }
3422     }
3423   return TRAVERSE_CONTINUE;
3424 }
3425
3426 // Verify that the struct type is complete and valid.
3427
3428 bool
3429 Struct_type::do_verify()
3430 {
3431   Struct_field_list* fields = this->fields_;
3432   if (fields == NULL)
3433     return true;
3434   bool ret = true;
3435   for (Struct_field_list::iterator p = fields->begin();
3436        p != fields->end();
3437        ++p)
3438     {
3439       Type* t = p->type();
3440       if (t->is_undefined())
3441         {
3442           error_at(p->location(), "struct field type is incomplete");
3443           p->set_type(Type::make_error_type());
3444           ret = false;
3445         }
3446       else if (p->is_anonymous())
3447         {
3448           if (t->named_type() != NULL && t->points_to() != NULL)
3449             {
3450               error_at(p->location(), "embedded type may not be a pointer");
3451               p->set_type(Type::make_error_type());
3452               return false;
3453             }
3454           if (t->points_to() != NULL
3455               && t->points_to()->interface_type() != NULL)
3456             {
3457               error_at(p->location(),
3458                        "embedded type may not be pointer to interface");
3459               p->set_type(Type::make_error_type());
3460               return false;
3461             }
3462         }
3463     }
3464   return ret;
3465 }
3466
3467 // Whether this contains a pointer.
3468
3469 bool
3470 Struct_type::do_has_pointer() const
3471 {
3472   const Struct_field_list* fields = this->fields();
3473   if (fields == NULL)
3474     return false;
3475   for (Struct_field_list::const_iterator p = fields->begin();
3476        p != fields->end();
3477        ++p)
3478     {
3479       if (p->type()->has_pointer())
3480         return true;
3481     }
3482   return false;
3483 }
3484
3485 // Whether this type is identical to T.
3486
3487 bool
3488 Struct_type::is_identical(const Struct_type* t,
3489                           bool errors_are_identical) const
3490 {
3491   const Struct_field_list* fields1 = this->fields();
3492   const Struct_field_list* fields2 = t->fields();
3493   if (fields1 == NULL || fields2 == NULL)
3494     return fields1 == fields2;
3495   Struct_field_list::const_iterator pf2 = fields2->begin();
3496   for (Struct_field_list::const_iterator pf1 = fields1->begin();
3497        pf1 != fields1->end();
3498        ++pf1, ++pf2)
3499     {
3500       if (pf2 == fields2->end())
3501         return false;
3502       if (pf1->field_name() != pf2->field_name())
3503         return false;
3504       if (pf1->is_anonymous() != pf2->is_anonymous()
3505           || !Type::are_identical(pf1->type(), pf2->type(),
3506                                   errors_are_identical, NULL))
3507         return false;
3508       if (!pf1->has_tag())
3509         {
3510           if (pf2->has_tag())
3511             return false;
3512         }
3513       else
3514         {
3515           if (!pf2->has_tag())
3516             return false;
3517           if (pf1->tag() != pf2->tag())
3518             return false;
3519         }
3520     }
3521   if (pf2 != fields2->end())
3522     return false;
3523   return true;
3524 }
3525
3526 // Whether this struct type has any hidden fields.
3527
3528 bool
3529 Struct_type::struct_has_hidden_fields(const Named_type* within,
3530                                       std::string* reason) const
3531 {
3532   const Struct_field_list* fields = this->fields();
3533   if (fields == NULL)
3534     return false;
3535   const Package* within_package = (within == NULL
3536                                    ? NULL
3537                                    : within->named_object()->package());
3538   for (Struct_field_list::const_iterator pf = fields->begin();
3539        pf != fields->end();
3540        ++pf)
3541     {
3542       if (within_package != NULL
3543           && !pf->is_anonymous()
3544           && Gogo::is_hidden_name(pf->field_name()))
3545         {
3546           if (reason != NULL)
3547             {
3548               std::string within_name = within->named_object()->message_name();
3549               std::string name = Gogo::message_name(pf->field_name());
3550               size_t bufsize = 200 + within_name.length() + name.length();
3551               char* buf = new char[bufsize];
3552               snprintf(buf, bufsize,
3553                        _("implicit assignment of %s%s%s hidden field %s%s%s"),
3554                        open_quote, within_name.c_str(), close_quote,
3555                        open_quote, name.c_str(), close_quote);
3556               reason->assign(buf);
3557               delete[] buf;
3558             }
3559           return true;
3560         }
3561
3562       if (pf->type()->has_hidden_fields(within, reason))</