OSDN Git Service

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