OSDN Git Service

Bring in collected bug fixes from mainline.
[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 (Gogo::is_sink_name(p->field_name()))
592                 continue;
593
594               if (!p->type()->is_comparable())
595                 {
596                   if (reason != NULL)
597                     *reason = _("invalid comparison of non-comparable struct");
598                   return false;
599                 }
600             }
601         }
602       else if (t1->array_type() != NULL)
603         {
604           if (t1->array_type()->length()->is_nil_expression()
605               || !t1->array_type()->element_type()->is_comparable())
606             {
607               if (reason != NULL)
608                 *reason = _("invalid comparison of non-comparable array");
609               return false;
610             }
611         }
612     }
613
614   return true;
615 }
616
617 // Return true if a value with type RHS may be assigned to a variable
618 // with type LHS.  If CHECK_HIDDEN_FIELDS is true, check whether any
619 // hidden fields are modified.  If REASON is not NULL, set *REASON to
620 // the reason the types are not assignable.
621
622 bool
623 Type::are_assignable_check_hidden(const Type* lhs, const Type* rhs,
624                                   bool check_hidden_fields,
625                                   std::string* reason)
626 {
627   // Do some checks first.  Make sure the types are defined.
628   if (rhs != NULL && !rhs->is_undefined())
629     {
630       if (rhs->is_void_type())
631         {
632           if (reason != NULL)
633             *reason = "non-value used as value";
634           return false;
635         }
636       if (rhs->is_call_multiple_result_type())
637         {
638           if (reason != NULL)
639             reason->assign(_("multiple value function call in "
640                              "single value context"));
641           return false;
642         }
643     }
644
645   if (lhs != NULL && !lhs->is_undefined())
646     {
647       // Any value may be assigned to the blank identifier.
648       if (lhs->is_sink_type())
649         return true;
650
651       // All fields of a struct must be exported, or the assignment
652       // must be in the same package.
653       if (check_hidden_fields && rhs != NULL && !rhs->is_undefined())
654         {
655           if (lhs->has_hidden_fields(NULL, reason)
656               || rhs->has_hidden_fields(NULL, reason))
657             return false;
658         }
659     }
660
661   // Identical types are assignable.
662   if (Type::are_identical(lhs, rhs, true, reason))
663     return true;
664
665   // The types are assignable if they have identical underlying types
666   // and either LHS or RHS is not a named type.
667   if (((lhs->named_type() != NULL && rhs->named_type() == NULL)
668        || (rhs->named_type() != NULL && lhs->named_type() == NULL))
669       && Type::are_identical(lhs->base(), rhs->base(), true, reason))
670     return true;
671
672   // The types are assignable if LHS is an interface type and RHS
673   // implements the required methods.
674   const Interface_type* lhs_interface_type = lhs->interface_type();
675   if (lhs_interface_type != NULL)
676     {
677       if (lhs_interface_type->implements_interface(rhs, reason))
678         return true;
679       const Interface_type* rhs_interface_type = rhs->interface_type();
680       if (rhs_interface_type != NULL
681           && lhs_interface_type->is_compatible_for_assign(rhs_interface_type,
682                                                           reason))
683         return true;
684     }
685
686   // The type are assignable if RHS is a bidirectional channel type,
687   // LHS is a channel type, they have identical element types, and
688   // either LHS or RHS is not a named type.
689   if (lhs->channel_type() != NULL
690       && rhs->channel_type() != NULL
691       && rhs->channel_type()->may_send()
692       && rhs->channel_type()->may_receive()
693       && (lhs->named_type() == NULL || rhs->named_type() == NULL)
694       && Type::are_identical(lhs->channel_type()->element_type(),
695                              rhs->channel_type()->element_type(),
696                              true,
697                              reason))
698     return true;
699
700   // The nil type may be assigned to a pointer, function, slice, map,
701   // channel, or interface type.
702   if (rhs->is_nil_type()
703       && (lhs->points_to() != NULL
704           || lhs->function_type() != NULL
705           || lhs->is_slice_type()
706           || lhs->map_type() != NULL
707           || lhs->channel_type() != NULL
708           || lhs->interface_type() != NULL))
709     return true;
710
711   // An untyped numeric constant may be assigned to a numeric type if
712   // it is representable in that type.
713   if ((rhs->is_abstract()
714        && (rhs->integer_type() != NULL
715            || rhs->float_type() != NULL
716            || rhs->complex_type() != NULL))
717       && (lhs->integer_type() != NULL
718           || lhs->float_type() != NULL
719           || lhs->complex_type() != NULL))
720     return true;
721
722   // Give some better error messages.
723   if (reason != NULL && reason->empty())
724     {
725       if (rhs->interface_type() != NULL)
726         reason->assign(_("need explicit conversion"));
727       else if (lhs->named_type() != NULL && rhs->named_type() != NULL)
728         {
729           size_t len = (lhs->named_type()->name().length()
730                         + rhs->named_type()->name().length()
731                         + 100);
732           char* buf = new char[len];
733           snprintf(buf, len, _("cannot use type %s as type %s"),
734                    rhs->named_type()->message_name().c_str(),
735                    lhs->named_type()->message_name().c_str());
736           reason->assign(buf);
737           delete[] buf;
738         }
739     }
740
741   return false;
742 }
743
744 // Return true if a value with type RHS may be assigned to a variable
745 // with type LHS.  If REASON is not NULL, set *REASON to the reason
746 // the types are not assignable.
747
748 bool
749 Type::are_assignable(const Type* lhs, const Type* rhs, std::string* reason)
750 {
751   return Type::are_assignable_check_hidden(lhs, rhs, false, reason);
752 }
753
754 // Like are_assignable but don't check for hidden fields.
755
756 bool
757 Type::are_assignable_hidden_ok(const Type* lhs, const Type* rhs,
758                                std::string* reason)
759 {
760   return Type::are_assignable_check_hidden(lhs, rhs, false, reason);
761 }
762
763 // Return true if a value with type RHS may be converted to type LHS.
764 // If REASON is not NULL, set *REASON to the reason the types are not
765 // convertible.
766
767 bool
768 Type::are_convertible(const Type* lhs, const Type* rhs, std::string* reason)
769 {
770   // The types are convertible if they are assignable.
771   if (Type::are_assignable(lhs, rhs, reason))
772     return true;
773
774   // The types are convertible if they have identical underlying
775   // types.
776   if ((lhs->named_type() != NULL || rhs->named_type() != NULL)
777       && Type::are_identical(lhs->base(), rhs->base(), true, reason))
778     return true;
779
780   // The types are convertible if they are both unnamed pointer types
781   // and their pointer base types have identical underlying types.
782   if (lhs->named_type() == NULL
783       && rhs->named_type() == NULL
784       && lhs->points_to() != NULL
785       && rhs->points_to() != NULL
786       && (lhs->points_to()->named_type() != NULL
787           || rhs->points_to()->named_type() != NULL)
788       && Type::are_identical(lhs->points_to()->base(),
789                              rhs->points_to()->base(),
790                              true,
791                              reason))
792     return true;
793
794   // Integer and floating point types are convertible to each other.
795   if ((lhs->integer_type() != NULL || lhs->float_type() != NULL)
796       && (rhs->integer_type() != NULL || rhs->float_type() != NULL))
797     return true;
798
799   // Complex types are convertible to each other.
800   if (lhs->complex_type() != NULL && rhs->complex_type() != NULL)
801     return true;
802
803   // An integer, or []byte, or []rune, may be converted to a string.
804   if (lhs->is_string_type())
805     {
806       if (rhs->integer_type() != NULL)
807         return true;
808       if (rhs->is_slice_type())
809         {
810           const Type* e = rhs->array_type()->element_type()->forwarded();
811           if (e->integer_type() != NULL
812               && (e->integer_type()->is_byte()
813                   || e->integer_type()->is_rune()))
814             return true;
815         }
816     }
817
818   // A string may be converted to []byte or []rune.
819   if (rhs->is_string_type() && lhs->is_slice_type())
820     {
821       const Type* e = lhs->array_type()->element_type()->forwarded();
822       if (e->integer_type() != NULL
823           && (e->integer_type()->is_byte() || e->integer_type()->is_rune()))
824         return true;
825     }
826
827   // An unsafe.Pointer type may be converted to any pointer type or to
828   // uintptr, and vice-versa.
829   if (lhs->is_unsafe_pointer_type()
830       && (rhs->points_to() != NULL
831           || (rhs->integer_type() != NULL
832               && rhs->forwarded() == Type::lookup_integer_type("uintptr"))))
833     return true;
834   if (rhs->is_unsafe_pointer_type()
835       && (lhs->points_to() != NULL
836           || (lhs->integer_type() != NULL
837               && lhs->forwarded() == Type::lookup_integer_type("uintptr"))))
838     return true;
839
840   // Give a better error message.
841   if (reason != NULL)
842     {
843       if (reason->empty())
844         *reason = "invalid type conversion";
845       else
846         {
847           std::string s = "invalid type conversion (";
848           s += *reason;
849           s += ')';
850           *reason = s;
851         }
852     }
853
854   return false;
855 }
856
857 // Return whether this type has any hidden fields.  This is only a
858 // possibility for a few types.
859
860 bool
861 Type::has_hidden_fields(const Named_type* within, std::string* reason) const
862 {
863   switch (this->forwarded()->classification_)
864     {
865     case TYPE_NAMED:
866       return this->named_type()->named_type_has_hidden_fields(reason);
867     case TYPE_STRUCT:
868       return this->struct_type()->struct_has_hidden_fields(within, reason);
869     case TYPE_ARRAY:
870       return this->array_type()->array_has_hidden_fields(within, reason);
871     default:
872       return false;
873     }
874 }
875
876 // Return a hash code for the type to be used for method lookup.
877
878 unsigned int
879 Type::hash_for_method(Gogo* gogo) const
880 {
881   unsigned int ret = 0;
882   if (this->classification_ != TYPE_FORWARD)
883     ret += this->classification_;
884   return ret + this->do_hash_for_method(gogo);
885 }
886
887 // Default implementation of do_hash_for_method.  This is appropriate
888 // for types with no subfields.
889
890 unsigned int
891 Type::do_hash_for_method(Gogo*) const
892 {
893   return 0;
894 }
895
896 // Return a hash code for a string, given a starting hash.
897
898 unsigned int
899 Type::hash_string(const std::string& s, unsigned int h)
900 {
901   const char* p = s.data();
902   size_t len = s.length();
903   for (; len > 0; --len)
904     {
905       h ^= *p++;
906       h*= 16777619;
907     }
908   return h;
909 }
910
911 // A hash table mapping unnamed types to the backend representation of
912 // those types.
913
914 Type::Type_btypes Type::type_btypes;
915
916 // Return a tree representing this type.
917
918 Btype*
919 Type::get_backend(Gogo* gogo)
920 {
921   if (this->btype_ != NULL)
922     {
923       if (this->btype_is_placeholder_ && gogo->named_types_are_converted())
924         this->finish_backend(gogo);
925       return this->btype_;
926     }
927
928   if (this->forward_declaration_type() != NULL
929       || this->named_type() != NULL)
930     return this->get_btype_without_hash(gogo);
931
932   if (this->is_error_type())
933     return gogo->backend()->error_type();
934
935   // To avoid confusing the backend, translate all identical Go types
936   // to the same backend representation.  We use a hash table to do
937   // that.  There is no need to use the hash table for named types, as
938   // named types are only identical to themselves.
939
940   std::pair<Type*, Btype*> val(this, NULL);
941   std::pair<Type_btypes::iterator, bool> ins =
942     Type::type_btypes.insert(val);
943   if (!ins.second && ins.first->second != NULL)
944     {
945       if (gogo != NULL && gogo->named_types_are_converted())
946         this->btype_ = ins.first->second;
947       return ins.first->second;
948     }
949
950   Btype* bt = this->get_btype_without_hash(gogo);
951
952   if (ins.first->second == NULL)
953     ins.first->second = bt;
954   else
955     {
956       // We have already created a backend representation for this
957       // type.  This can happen when an unnamed type is defined using
958       // a named type which in turns uses an identical unnamed type.
959       // Use the tree we created earlier and ignore the one we just
960       // built.
961       bt = ins.first->second;
962       if (gogo == NULL || !gogo->named_types_are_converted())
963         return bt;
964       this->btype_ = bt;
965     }
966
967   return bt;
968 }
969
970 // Return the backend representation for a type without looking in the
971 // hash table for identical types.  This is used for named types,
972 // since a named type is never identical to any other type.
973
974 Btype*
975 Type::get_btype_without_hash(Gogo* gogo)
976 {
977   if (this->btype_ == NULL)
978     {
979       Btype* bt = this->do_get_backend(gogo);
980
981       // For a recursive function or pointer type, we will temporarily
982       // return a circular pointer type during the recursion.  We
983       // don't want to record that for a forwarding type, as it may
984       // confuse us later.
985       if (this->forward_declaration_type() != NULL
986           && gogo->backend()->is_circular_pointer_type(bt))
987         return bt;
988
989       if (gogo == NULL || !gogo->named_types_are_converted())
990         return bt;
991
992       this->btype_ = bt;
993     }
994   return this->btype_;
995 }
996
997 // Get the backend representation of a type without forcing the
998 // creation of the backend representation of all supporting types.
999 // This will return a backend type that has the correct size but may
1000 // be incomplete.  E.g., a pointer will just be a placeholder pointer,
1001 // and will not contain the final representation of the type to which
1002 // it points.  This is used while converting all named types to the
1003 // backend representation, to avoid problems with indirect references
1004 // to types which are not yet complete.  When this is called, the
1005 // sizes of all direct references (e.g., a struct field) should be
1006 // known, but the sizes of indirect references (e.g., the type to
1007 // which a pointer points) may not.
1008
1009 Btype*
1010 Type::get_backend_placeholder(Gogo* gogo)
1011 {
1012   if (gogo->named_types_are_converted())
1013     return this->get_backend(gogo);
1014   if (this->btype_ != NULL)
1015     return this->btype_;
1016
1017   Btype* bt;
1018   switch (this->classification_)
1019     {
1020     case TYPE_ERROR:
1021     case TYPE_VOID:
1022     case TYPE_BOOLEAN:
1023     case TYPE_INTEGER:
1024     case TYPE_FLOAT:
1025     case TYPE_COMPLEX:
1026     case TYPE_STRING:
1027     case TYPE_NIL:
1028       // These are simple types that can just be created directly.
1029       return this->get_backend(gogo);
1030
1031     case TYPE_FUNCTION:
1032       {
1033         Location loc = this->function_type()->location();
1034         bt = gogo->backend()->placeholder_pointer_type("", loc, true);
1035       }
1036       break;
1037
1038     case TYPE_POINTER:
1039       {
1040         Location loc = Linemap::unknown_location();
1041         bt = gogo->backend()->placeholder_pointer_type("", loc, false);
1042       }
1043       break;
1044
1045     case TYPE_STRUCT:
1046       // We don't have to make the struct itself be a placeholder.  We
1047       // are promised that we know the sizes of the struct fields.
1048       // But we may have to use a placeholder for any particular
1049       // struct field.
1050       {
1051         std::vector<Backend::Btyped_identifier> bfields;
1052         get_backend_struct_fields(gogo, this->struct_type()->fields(),
1053                                   true, &bfields);
1054         bt = gogo->backend()->struct_type(bfields);
1055       }
1056       break;
1057
1058     case TYPE_ARRAY:
1059       if (this->is_slice_type())
1060         {
1061           std::vector<Backend::Btyped_identifier> bfields;
1062           get_backend_slice_fields(gogo, this->array_type(), true, &bfields);
1063           bt = gogo->backend()->struct_type(bfields);
1064         }
1065       else
1066         {
1067           Btype* element = this->array_type()->get_backend_element(gogo, true);
1068           Bexpression* len = this->array_type()->get_backend_length(gogo);
1069           bt = gogo->backend()->array_type(element, len);
1070         }
1071       break;
1072         
1073     case TYPE_MAP:
1074     case TYPE_CHANNEL:
1075       // All maps and channels have the same backend representation.
1076       return this->get_backend(gogo);
1077
1078     case TYPE_INTERFACE:
1079       if (this->interface_type()->is_empty())
1080         return Interface_type::get_backend_empty_interface_type(gogo);
1081       else
1082         {
1083           std::vector<Backend::Btyped_identifier> bfields;
1084           get_backend_interface_fields(gogo, this->interface_type(), true,
1085                                        &bfields);
1086           bt = gogo->backend()->struct_type(bfields);
1087         }
1088       break;
1089
1090     case TYPE_NAMED:
1091     case TYPE_FORWARD:
1092       // Named types keep track of their own dependencies and manage
1093       // their own placeholders.
1094       return this->get_backend(gogo);
1095
1096     case TYPE_SINK:
1097     case TYPE_CALL_MULTIPLE_RESULT:
1098     default:
1099       go_unreachable();
1100     }
1101
1102   this->btype_ = bt;
1103   this->btype_is_placeholder_ = true;
1104   return bt;
1105 }
1106
1107 // Complete the backend representation.  This is called for a type
1108 // using a placeholder type.
1109
1110 void
1111 Type::finish_backend(Gogo* gogo)
1112 {
1113   go_assert(this->btype_ != NULL);
1114   if (!this->btype_is_placeholder_)
1115     return;
1116
1117   switch (this->classification_)
1118     {
1119     case TYPE_ERROR:
1120     case TYPE_VOID:
1121     case TYPE_BOOLEAN:
1122     case TYPE_INTEGER:
1123     case TYPE_FLOAT:
1124     case TYPE_COMPLEX:
1125     case TYPE_STRING:
1126     case TYPE_NIL:
1127       go_unreachable();
1128
1129     case TYPE_FUNCTION:
1130       {
1131         Btype* bt = this->do_get_backend(gogo);
1132         if (!gogo->backend()->set_placeholder_function_type(this->btype_, bt))
1133           go_assert(saw_errors());
1134       }
1135       break;
1136
1137     case TYPE_POINTER:
1138       {
1139         Btype* bt = this->do_get_backend(gogo);
1140         if (!gogo->backend()->set_placeholder_pointer_type(this->btype_, bt))
1141           go_assert(saw_errors());
1142       }
1143       break;
1144
1145     case TYPE_STRUCT:
1146       // The struct type itself is done, but we have to make sure that
1147       // all the field types are converted.
1148       this->struct_type()->finish_backend_fields(gogo);
1149       break;
1150
1151     case TYPE_ARRAY:
1152       // The array type itself is done, but make sure the element type
1153       // is converted.
1154       this->array_type()->finish_backend_element(gogo);
1155       break;
1156         
1157     case TYPE_MAP:
1158     case TYPE_CHANNEL:
1159       go_unreachable();
1160
1161     case TYPE_INTERFACE:
1162       // The interface type itself is done, but make sure the method
1163       // types are converted.
1164       this->interface_type()->finish_backend_methods(gogo);
1165       break;
1166
1167     case TYPE_NAMED:
1168     case TYPE_FORWARD:
1169       go_unreachable();
1170
1171     case TYPE_SINK:
1172     case TYPE_CALL_MULTIPLE_RESULT:
1173     default:
1174       go_unreachable();
1175     }
1176
1177   this->btype_is_placeholder_ = false;
1178 }
1179
1180 // Return a pointer to the type descriptor for this type.
1181
1182 tree
1183 Type::type_descriptor_pointer(Gogo* gogo, Location location)
1184 {
1185   Type* t = this->forwarded();
1186   if (t->named_type() != NULL && t->named_type()->is_alias())
1187     t = t->named_type()->real_type();
1188   if (t->type_descriptor_var_ == NULL)
1189     {
1190       t->make_type_descriptor_var(gogo);
1191       go_assert(t->type_descriptor_var_ != NULL);
1192     }
1193   tree var_tree = var_to_tree(t->type_descriptor_var_);
1194   if (var_tree == error_mark_node)
1195     return error_mark_node;
1196   return build_fold_addr_expr_loc(location.gcc_location(), var_tree);
1197 }
1198
1199 // A mapping from unnamed types to type descriptor variables.
1200
1201 Type::Type_descriptor_vars Type::type_descriptor_vars;
1202
1203 // Build the type descriptor for this type.
1204
1205 void
1206 Type::make_type_descriptor_var(Gogo* gogo)
1207 {
1208   go_assert(this->type_descriptor_var_ == NULL);
1209
1210   Named_type* nt = this->named_type();
1211
1212   // We can have multiple instances of unnamed types, but we only want
1213   // to emit the type descriptor once.  We use a hash table.  This is
1214   // not necessary for named types, as they are unique, and we store
1215   // the type descriptor in the type itself.
1216   Bvariable** phash = NULL;
1217   if (nt == NULL)
1218     {
1219       Bvariable* bvnull = NULL;
1220       std::pair<Type_descriptor_vars::iterator, bool> ins =
1221         Type::type_descriptor_vars.insert(std::make_pair(this, bvnull));
1222       if (!ins.second)
1223         {
1224           // We've already build a type descriptor for this type.
1225           this->type_descriptor_var_ = ins.first->second;
1226           return;
1227         }
1228       phash = &ins.first->second;
1229     }
1230
1231   std::string var_name = this->type_descriptor_var_name(gogo, nt);
1232
1233   // Build the contents of the type descriptor.
1234   Expression* initializer = this->do_type_descriptor(gogo, NULL);
1235
1236   Btype* initializer_btype = initializer->type()->get_backend(gogo);
1237
1238   Location loc = nt == NULL ? Linemap::predeclared_location() : nt->location();
1239
1240   const Package* dummy;
1241   if (this->type_descriptor_defined_elsewhere(nt, &dummy))
1242     {
1243       this->type_descriptor_var_ =
1244         gogo->backend()->immutable_struct_reference(var_name,
1245                                                     initializer_btype,
1246                                                     loc);
1247       if (phash != NULL)
1248         *phash = this->type_descriptor_var_;
1249       return;
1250     }
1251
1252   // See if this type descriptor can appear in multiple packages.
1253   bool is_common = false;
1254   if (nt != NULL)
1255     {
1256       // We create the descriptor for a builtin type whenever we need
1257       // it.
1258       is_common = nt->is_builtin();
1259     }
1260   else
1261     {
1262       // This is an unnamed type.  The descriptor could be defined in
1263       // any package where it is needed, and the linker will pick one
1264       // descriptor to keep.
1265       is_common = true;
1266     }
1267
1268   // We are going to build the type descriptor in this package.  We
1269   // must create the variable before we convert the initializer to the
1270   // backend representation, because the initializer may refer to the
1271   // type descriptor of this type.  By setting type_descriptor_var_ we
1272   // ensure that type_descriptor_pointer will work if called while
1273   // converting INITIALIZER.
1274
1275   this->type_descriptor_var_ =
1276     gogo->backend()->immutable_struct(var_name, is_common, initializer_btype,
1277                                       loc);
1278   if (phash != NULL)
1279     *phash = this->type_descriptor_var_;
1280
1281   Translate_context context(gogo, NULL, NULL, NULL);
1282   context.set_is_const();
1283   Bexpression* binitializer = tree_to_expr(initializer->get_tree(&context));
1284
1285   gogo->backend()->immutable_struct_set_init(this->type_descriptor_var_,
1286                                              var_name, is_common,
1287                                              initializer_btype, loc,
1288                                              binitializer);
1289 }
1290
1291 // Return the name of the type descriptor variable.  If NT is not
1292 // NULL, use it to get the name.  Otherwise this is an unnamed type.
1293
1294 std::string
1295 Type::type_descriptor_var_name(Gogo* gogo, Named_type* nt)
1296 {
1297   if (nt == NULL)
1298     return "__go_td_" + this->mangled_name(gogo);
1299
1300   Named_object* no = nt->named_object();
1301   unsigned int index;
1302   const Named_object* in_function = nt->in_function(&index);
1303   std::string ret = "__go_tdn_";
1304   if (nt->is_builtin())
1305     go_assert(in_function == NULL);
1306   else
1307     {
1308       const std::string& pkgpath(no->package() == NULL
1309                                  ? gogo->pkgpath_symbol()
1310                                  : no->package()->pkgpath_symbol());
1311       ret.append(pkgpath);
1312       ret.append(1, '.');
1313       if (in_function != NULL)
1314         {
1315           ret.append(Gogo::unpack_hidden_name(in_function->name()));
1316           ret.append(1, '.');
1317           if (index > 0)
1318             {
1319               char buf[30];
1320               snprintf(buf, sizeof buf, "%u", index);
1321               ret.append(buf);
1322               ret.append(1, '.');
1323             }
1324         }
1325     }
1326
1327   // FIXME: This adds in pkgpath twice for hidden symbols, which is
1328   // pointless.
1329   const std::string& name(no->name());
1330   if (!Gogo::is_hidden_name(name))
1331     ret.append(name);
1332   else
1333     {
1334       ret.append(1, '.');
1335       ret.append(Gogo::pkgpath_for_symbol(Gogo::hidden_name_pkgpath(name)));
1336       ret.append(1, '.');
1337       ret.append(Gogo::unpack_hidden_name(name));
1338     }
1339
1340   return ret;
1341 }
1342
1343 // Return true if this type descriptor is defined in a different
1344 // package.  If this returns true it sets *PACKAGE to the package.
1345
1346 bool
1347 Type::type_descriptor_defined_elsewhere(Named_type* nt,
1348                                         const Package** package)
1349 {
1350   if (nt != NULL)
1351     {
1352       if (nt->named_object()->package() != NULL)
1353         {
1354           // This is a named type defined in a different package.  The
1355           // type descriptor should be defined in that package.
1356           *package = nt->named_object()->package();
1357           return true;
1358         }
1359     }
1360   else
1361     {
1362       if (this->points_to() != NULL
1363           && this->points_to()->named_type() != NULL
1364           && this->points_to()->named_type()->named_object()->package() != NULL)
1365         {
1366           // This is an unnamed pointer to a named type defined in a
1367           // different package.  The descriptor should be defined in
1368           // that package.
1369           *package = this->points_to()->named_type()->named_object()->package();
1370           return true;
1371         }
1372     }
1373   return false;
1374 }
1375
1376 // Return a composite literal for a type descriptor.
1377
1378 Expression*
1379 Type::type_descriptor(Gogo* gogo, Type* type)
1380 {
1381   return type->do_type_descriptor(gogo, NULL);
1382 }
1383
1384 // Return a composite literal for a type descriptor with a name.
1385
1386 Expression*
1387 Type::named_type_descriptor(Gogo* gogo, Type* type, Named_type* name)
1388 {
1389   go_assert(name != NULL && type->named_type() != name);
1390   return type->do_type_descriptor(gogo, name);
1391 }
1392
1393 // Make a builtin struct type from a list of fields.  The fields are
1394 // pairs of a name and a type.
1395
1396 Struct_type*
1397 Type::make_builtin_struct_type(int nfields, ...)
1398 {
1399   va_list ap;
1400   va_start(ap, nfields);
1401
1402   Location bloc = Linemap::predeclared_location();
1403   Struct_field_list* sfl = new Struct_field_list();
1404   for (int i = 0; i < nfields; i++)
1405     {
1406       const char* field_name = va_arg(ap, const char *);
1407       Type* type = va_arg(ap, Type*);
1408       sfl->push_back(Struct_field(Typed_identifier(field_name, type, bloc)));
1409     }
1410
1411   va_end(ap);
1412
1413   return Type::make_struct_type(sfl, bloc);
1414 }
1415
1416 // A list of builtin named types.
1417
1418 std::vector<Named_type*> Type::named_builtin_types;
1419
1420 // Make a builtin named type.
1421
1422 Named_type*
1423 Type::make_builtin_named_type(const char* name, Type* type)
1424 {
1425   Location bloc = Linemap::predeclared_location();
1426   Named_object* no = Named_object::make_type(name, NULL, type, bloc);
1427   Named_type* ret = no->type_value();
1428   Type::named_builtin_types.push_back(ret);
1429   return ret;
1430 }
1431
1432 // Convert the named builtin types.
1433
1434 void
1435 Type::convert_builtin_named_types(Gogo* gogo)
1436 {
1437   for (std::vector<Named_type*>::const_iterator p =
1438          Type::named_builtin_types.begin();
1439        p != Type::named_builtin_types.end();
1440        ++p)
1441     {
1442       bool r = (*p)->verify();
1443       go_assert(r);
1444       (*p)->convert(gogo);
1445     }
1446 }
1447
1448 // Return the type of a type descriptor.  We should really tie this to
1449 // runtime.Type rather than copying it.  This must match commonType in
1450 // libgo/go/runtime/type.go.
1451
1452 Type*
1453 Type::make_type_descriptor_type()
1454 {
1455   static Type* ret;
1456   if (ret == NULL)
1457     {
1458       Location bloc = Linemap::predeclared_location();
1459
1460       Type* uint8_type = Type::lookup_integer_type("uint8");
1461       Type* uint32_type = Type::lookup_integer_type("uint32");
1462       Type* uintptr_type = Type::lookup_integer_type("uintptr");
1463       Type* string_type = Type::lookup_string_type();
1464       Type* pointer_string_type = Type::make_pointer_type(string_type);
1465
1466       // This is an unnamed version of unsafe.Pointer.  Perhaps we
1467       // should use the named version instead, although that would
1468       // require us to create the unsafe package if it has not been
1469       // imported.  It probably doesn't matter.
1470       Type* void_type = Type::make_void_type();
1471       Type* unsafe_pointer_type = Type::make_pointer_type(void_type);
1472
1473       // Forward declaration for the type descriptor type.
1474       Named_object* named_type_descriptor_type =
1475         Named_object::make_type_declaration("commonType", NULL, bloc);
1476       Type* ft = Type::make_forward_declaration(named_type_descriptor_type);
1477       Type* pointer_type_descriptor_type = Type::make_pointer_type(ft);
1478
1479       // The type of a method on a concrete type.
1480       Struct_type* method_type =
1481         Type::make_builtin_struct_type(5,
1482                                        "name", pointer_string_type,
1483                                        "pkgPath", pointer_string_type,
1484                                        "mtyp", pointer_type_descriptor_type,
1485                                        "typ", pointer_type_descriptor_type,
1486                                        "tfn", unsafe_pointer_type);
1487       Named_type* named_method_type =
1488         Type::make_builtin_named_type("method", method_type);
1489
1490       // Information for types with a name or methods.
1491       Type* slice_named_method_type =
1492         Type::make_array_type(named_method_type, NULL);
1493       Struct_type* uncommon_type =
1494         Type::make_builtin_struct_type(3,
1495                                        "name", pointer_string_type,
1496                                        "pkgPath", pointer_string_type,
1497                                        "methods", slice_named_method_type);
1498       Named_type* named_uncommon_type =
1499         Type::make_builtin_named_type("uncommonType", uncommon_type);
1500
1501       Type* pointer_uncommon_type =
1502         Type::make_pointer_type(named_uncommon_type);
1503
1504       // The type descriptor type.
1505
1506       Typed_identifier_list* params = new Typed_identifier_list();
1507       params->push_back(Typed_identifier("key", unsafe_pointer_type, bloc));
1508       params->push_back(Typed_identifier("key_size", uintptr_type, bloc));
1509
1510       Typed_identifier_list* results = new Typed_identifier_list();
1511       results->push_back(Typed_identifier("", uintptr_type, bloc));
1512
1513       Type* hashfn_type = Type::make_function_type(NULL, params, results, bloc);
1514
1515       params = new Typed_identifier_list();
1516       params->push_back(Typed_identifier("key1", unsafe_pointer_type, bloc));
1517       params->push_back(Typed_identifier("key2", unsafe_pointer_type, bloc));
1518       params->push_back(Typed_identifier("key_size", uintptr_type, bloc));
1519
1520       results = new Typed_identifier_list();
1521       results->push_back(Typed_identifier("", Type::lookup_bool_type(), bloc));
1522
1523       Type* equalfn_type = Type::make_function_type(NULL, params, results,
1524                                                     bloc);
1525
1526       Struct_type* type_descriptor_type =
1527         Type::make_builtin_struct_type(10,
1528                                        "Kind", uint8_type,
1529                                        "align", uint8_type,
1530                                        "fieldAlign", uint8_type,
1531                                        "size", uintptr_type,
1532                                        "hash", uint32_type,
1533                                        "hashfn", hashfn_type,
1534                                        "equalfn", equalfn_type,
1535                                        "string", pointer_string_type,
1536                                        "", pointer_uncommon_type,
1537                                        "ptrToThis",
1538                                        pointer_type_descriptor_type);
1539
1540       Named_type* named = Type::make_builtin_named_type("commonType",
1541                                                         type_descriptor_type);
1542
1543       named_type_descriptor_type->set_type_value(named);
1544
1545       ret = named;
1546     }
1547
1548   return ret;
1549 }
1550
1551 // Make the type of a pointer to a type descriptor as represented in
1552 // Go.
1553
1554 Type*
1555 Type::make_type_descriptor_ptr_type()
1556 {
1557   static Type* ret;
1558   if (ret == NULL)
1559     ret = Type::make_pointer_type(Type::make_type_descriptor_type());
1560   return ret;
1561 }
1562
1563 // Set *HASH_FN and *EQUAL_FN to the runtime functions which compute a
1564 // hash code for this type and which compare whether two values of
1565 // this type are equal.  If NAME is not NULL it is the name of this
1566 // type.  HASH_FNTYPE and EQUAL_FNTYPE are the types of these
1567 // functions, for convenience; they may be NULL.
1568
1569 void
1570 Type::type_functions(Gogo* gogo, Named_type* name, Function_type* hash_fntype,
1571                      Function_type* equal_fntype, Named_object** hash_fn,
1572                      Named_object** equal_fn)
1573 {
1574   if (hash_fntype == NULL || equal_fntype == NULL)
1575     {
1576       Location bloc = Linemap::predeclared_location();
1577
1578       Type* uintptr_type = Type::lookup_integer_type("uintptr");
1579       Type* void_type = Type::make_void_type();
1580       Type* unsafe_pointer_type = Type::make_pointer_type(void_type);
1581
1582       if (hash_fntype == NULL)
1583         {
1584           Typed_identifier_list* params = new Typed_identifier_list();
1585           params->push_back(Typed_identifier("key", unsafe_pointer_type,
1586                                              bloc));
1587           params->push_back(Typed_identifier("key_size", uintptr_type, bloc));
1588
1589           Typed_identifier_list* results = new Typed_identifier_list();
1590           results->push_back(Typed_identifier("", uintptr_type, bloc));
1591
1592           hash_fntype = Type::make_function_type(NULL, params, results, bloc);
1593         }
1594       if (equal_fntype == NULL)
1595         {
1596           Typed_identifier_list* params = new Typed_identifier_list();
1597           params->push_back(Typed_identifier("key1", unsafe_pointer_type,
1598                                              bloc));
1599           params->push_back(Typed_identifier("key2", unsafe_pointer_type,
1600                                              bloc));
1601           params->push_back(Typed_identifier("key_size", uintptr_type, bloc));
1602
1603           Typed_identifier_list* results = new Typed_identifier_list();
1604           results->push_back(Typed_identifier("", Type::lookup_bool_type(),
1605                                               bloc));
1606
1607           equal_fntype = Type::make_function_type(NULL, params, results, bloc);
1608         }
1609     }
1610
1611   const char* hash_fnname;
1612   const char* equal_fnname;
1613   if (this->compare_is_identity(gogo))
1614     {
1615       hash_fnname = "__go_type_hash_identity";
1616       equal_fnname = "__go_type_equal_identity";
1617     }
1618   else if (!this->is_comparable())
1619     {
1620       hash_fnname = "__go_type_hash_error";
1621       equal_fnname = "__go_type_equal_error";
1622     }
1623   else
1624     {
1625       switch (this->base()->classification())
1626         {
1627         case Type::TYPE_ERROR:
1628         case Type::TYPE_VOID:
1629         case Type::TYPE_NIL:
1630         case Type::TYPE_FUNCTION:
1631         case Type::TYPE_MAP:
1632           // For these types is_comparable should have returned false.
1633           go_unreachable();
1634
1635         case Type::TYPE_BOOLEAN:
1636         case Type::TYPE_INTEGER:
1637         case Type::TYPE_POINTER:
1638         case Type::TYPE_CHANNEL:
1639           // For these types compare_is_identity should have returned true.
1640           go_unreachable();
1641
1642         case Type::TYPE_FLOAT:
1643           hash_fnname = "__go_type_hash_float";
1644           equal_fnname = "__go_type_equal_float";
1645           break;
1646
1647         case Type::TYPE_COMPLEX:
1648           hash_fnname = "__go_type_hash_complex";
1649           equal_fnname = "__go_type_equal_complex";
1650           break;
1651
1652         case Type::TYPE_STRING:
1653           hash_fnname = "__go_type_hash_string";
1654           equal_fnname = "__go_type_equal_string";
1655           break;
1656
1657         case Type::TYPE_STRUCT:
1658           {
1659             // This is a struct which can not be compared using a
1660             // simple identity function.  We need to build a function
1661             // for comparison.
1662             this->specific_type_functions(gogo, name, hash_fntype,
1663                                           equal_fntype, hash_fn, equal_fn);
1664             return;
1665           }
1666
1667         case Type::TYPE_ARRAY:
1668           if (this->is_slice_type())
1669             {
1670               // Type::is_compatible_for_comparison should have
1671               // returned false.
1672               go_unreachable();
1673             }
1674           else
1675             {
1676               // This is an array which can not be compared using a
1677               // simple identity function.  We need to build a
1678               // function for comparison.
1679               this->specific_type_functions(gogo, name, hash_fntype,
1680                                             equal_fntype, hash_fn, equal_fn);
1681               return;
1682             }
1683           break;
1684
1685         case Type::TYPE_INTERFACE:
1686           if (this->interface_type()->is_empty())
1687             {
1688               hash_fnname = "__go_type_hash_empty_interface";
1689               equal_fnname = "__go_type_equal_empty_interface";
1690             }
1691           else
1692             {
1693               hash_fnname = "__go_type_hash_interface";
1694               equal_fnname = "__go_type_equal_interface";
1695             }
1696           break;
1697
1698         case Type::TYPE_NAMED:
1699         case Type::TYPE_FORWARD:
1700           go_unreachable();
1701
1702         default:
1703           go_unreachable();
1704         }
1705     }
1706
1707
1708   Location bloc = Linemap::predeclared_location();
1709   *hash_fn = Named_object::make_function_declaration(hash_fnname, NULL,
1710                                                      hash_fntype, bloc);
1711   (*hash_fn)->func_declaration_value()->set_asm_name(hash_fnname);
1712   *equal_fn = Named_object::make_function_declaration(equal_fnname, NULL,
1713                                                       equal_fntype, bloc);
1714   (*equal_fn)->func_declaration_value()->set_asm_name(equal_fnname);
1715 }
1716
1717 // A hash table mapping types to the specific hash functions.
1718
1719 Type::Type_functions Type::type_functions_table;
1720
1721 // Handle a type function which is specific to a type: a struct or
1722 // array which can not use an identity comparison.
1723
1724 void
1725 Type::specific_type_functions(Gogo* gogo, Named_type* name,
1726                               Function_type* hash_fntype,
1727                               Function_type* equal_fntype,
1728                               Named_object** hash_fn,
1729                               Named_object** equal_fn)
1730 {
1731   Hash_equal_fn fnull(NULL, NULL);
1732   std::pair<Type*, Hash_equal_fn> val(name != NULL ? name : this, fnull);
1733   std::pair<Type_functions::iterator, bool> ins =
1734     Type::type_functions_table.insert(val);
1735   if (!ins.second)
1736     {
1737       // We already have functions for this type
1738       *hash_fn = ins.first->second.first;
1739       *equal_fn = ins.first->second.second;
1740       return;
1741     }
1742
1743   std::string base_name;
1744   if (name == NULL)
1745     {
1746       // Mangled names can have '.' if they happen to refer to named
1747       // types in some way.  That's fine if this is simply a named
1748       // type, but otherwise it will confuse the code that builds
1749       // function identifiers.  Remove '.' when necessary.
1750       base_name = this->mangled_name(gogo);
1751       size_t i;
1752       while ((i = base_name.find('.')) != std::string::npos)
1753         base_name[i] = '$';
1754       base_name = gogo->pack_hidden_name(base_name, false);
1755     }
1756   else
1757     {
1758       // This name is already hidden or not as appropriate.
1759       base_name = name->name();
1760       unsigned int index;
1761       const Named_object* in_function = name->in_function(&index);
1762       if (in_function != NULL)
1763         {
1764           base_name += '$' + Gogo::unpack_hidden_name(in_function->name());
1765           if (index > 0)
1766             {
1767               char buf[30];
1768               snprintf(buf, sizeof buf, "%u", index);
1769               base_name += '$';
1770               base_name += buf;
1771             }
1772         }
1773     }
1774   std::string hash_name = base_name + "$hash";
1775   std::string equal_name = base_name + "$equal";
1776
1777   Location bloc = Linemap::predeclared_location();
1778
1779   const Package* package = NULL;
1780   bool is_defined_elsewhere =
1781     this->type_descriptor_defined_elsewhere(name, &package);
1782   if (is_defined_elsewhere)
1783     {
1784       *hash_fn = Named_object::make_function_declaration(hash_name, package,
1785                                                          hash_fntype, bloc);
1786       *equal_fn = Named_object::make_function_declaration(equal_name, package,
1787                                                           equal_fntype, bloc);
1788     }
1789   else
1790     {
1791       *hash_fn = gogo->declare_package_function(hash_name, hash_fntype, bloc);
1792       *equal_fn = gogo->declare_package_function(equal_name, equal_fntype,
1793                                                  bloc);
1794     }
1795
1796   ins.first->second.first = *hash_fn;
1797   ins.first->second.second = *equal_fn;
1798
1799   if (!is_defined_elsewhere)
1800     {
1801       if (gogo->in_global_scope())
1802         this->write_specific_type_functions(gogo, name, hash_name, hash_fntype,
1803                                             equal_name, equal_fntype);
1804       else
1805         gogo->queue_specific_type_function(this, name, hash_name, hash_fntype,
1806                                            equal_name, equal_fntype);
1807     }
1808 }
1809
1810 // Write the hash and equality functions for a type which needs to be
1811 // written specially.
1812
1813 void
1814 Type::write_specific_type_functions(Gogo* gogo, Named_type* name,
1815                                     const std::string& hash_name,
1816                                     Function_type* hash_fntype,
1817                                     const std::string& equal_name,
1818                                     Function_type* equal_fntype)
1819 {
1820   Location bloc = Linemap::predeclared_location();
1821
1822   if (gogo->specific_type_functions_are_written())
1823     {
1824       go_assert(saw_errors());
1825       return;
1826     }
1827
1828   Named_object* hash_fn = gogo->start_function(hash_name, hash_fntype, false,
1829                                                bloc);
1830   gogo->start_block(bloc);
1831
1832   if (this->struct_type() != NULL)
1833     this->struct_type()->write_hash_function(gogo, name, hash_fntype,
1834                                              equal_fntype);
1835   else if (this->array_type() != NULL)
1836     this->array_type()->write_hash_function(gogo, name, hash_fntype,
1837                                             equal_fntype);
1838   else
1839     go_unreachable();
1840
1841   Block* b = gogo->finish_block(bloc);
1842   gogo->add_block(b, bloc);
1843   gogo->lower_block(hash_fn, b);
1844   gogo->finish_function(bloc);
1845
1846   Named_object *equal_fn = gogo->start_function(equal_name, equal_fntype,
1847                                                 false, bloc);
1848   gogo->start_block(bloc);
1849
1850   if (this->struct_type() != NULL)
1851     this->struct_type()->write_equal_function(gogo, name);
1852   else if (this->array_type() != NULL)
1853     this->array_type()->write_equal_function(gogo, name);
1854   else
1855     go_unreachable();
1856
1857   b = gogo->finish_block(bloc);
1858   gogo->add_block(b, bloc);
1859   gogo->lower_block(equal_fn, b);
1860   gogo->finish_function(bloc);
1861 }
1862
1863 // Return a composite literal for the type descriptor for a plain type
1864 // of kind RUNTIME_TYPE_KIND named NAME.
1865
1866 Expression*
1867 Type::type_descriptor_constructor(Gogo* gogo, int runtime_type_kind,
1868                                   Named_type* name, const Methods* methods,
1869                                   bool only_value_methods)
1870 {
1871   Location bloc = Linemap::predeclared_location();
1872
1873   Type* td_type = Type::make_type_descriptor_type();
1874   const Struct_field_list* fields = td_type->struct_type()->fields();
1875
1876   Expression_list* vals = new Expression_list();
1877   vals->reserve(9);
1878
1879   if (!this->has_pointer())
1880     runtime_type_kind |= RUNTIME_TYPE_KIND_NO_POINTERS;
1881   Struct_field_list::const_iterator p = fields->begin();
1882   go_assert(p->is_field_name("Kind"));
1883   mpz_t iv;
1884   mpz_init_set_ui(iv, runtime_type_kind);
1885   vals->push_back(Expression::make_integer(&iv, p->type(), bloc));
1886
1887   ++p;
1888   go_assert(p->is_field_name("align"));
1889   Expression::Type_info type_info = Expression::TYPE_INFO_ALIGNMENT;
1890   vals->push_back(Expression::make_type_info(this, type_info));
1891
1892   ++p;
1893   go_assert(p->is_field_name("fieldAlign"));
1894   type_info = Expression::TYPE_INFO_FIELD_ALIGNMENT;
1895   vals->push_back(Expression::make_type_info(this, type_info));
1896
1897   ++p;
1898   go_assert(p->is_field_name("size"));
1899   type_info = Expression::TYPE_INFO_SIZE;
1900   vals->push_back(Expression::make_type_info(this, type_info));
1901
1902   ++p;
1903   go_assert(p->is_field_name("hash"));
1904   unsigned int h;
1905   if (name != NULL)
1906     h = name->hash_for_method(gogo);
1907   else
1908     h = this->hash_for_method(gogo);
1909   mpz_set_ui(iv, h);
1910   vals->push_back(Expression::make_integer(&iv, p->type(), bloc));
1911
1912   ++p;
1913   go_assert(p->is_field_name("hashfn"));
1914   Function_type* hash_fntype = p->type()->function_type();
1915
1916   ++p;
1917   go_assert(p->is_field_name("equalfn"));
1918   Function_type* equal_fntype = p->type()->function_type();
1919
1920   Named_object* hash_fn;
1921   Named_object* equal_fn;
1922   this->type_functions(gogo, name, hash_fntype, equal_fntype, &hash_fn,
1923                        &equal_fn);
1924   vals->push_back(Expression::make_func_reference(hash_fn, NULL, bloc));
1925   vals->push_back(Expression::make_func_reference(equal_fn, NULL, bloc));
1926
1927   ++p;
1928   go_assert(p->is_field_name("string"));
1929   Expression* s = Expression::make_string((name != NULL
1930                                            ? name->reflection(gogo)
1931                                            : this->reflection(gogo)),
1932                                           bloc);
1933   vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
1934
1935   ++p;
1936   go_assert(p->is_field_name("uncommonType"));
1937   if (name == NULL && methods == NULL)
1938     vals->push_back(Expression::make_nil(bloc));
1939   else
1940     {
1941       if (methods == NULL)
1942         methods = name->methods();
1943       vals->push_back(this->uncommon_type_constructor(gogo,
1944                                                       p->type()->deref(),
1945                                                       name, methods,
1946                                                       only_value_methods));
1947     }
1948
1949   ++p;
1950   go_assert(p->is_field_name("ptrToThis"));
1951   if (name == NULL)
1952     vals->push_back(Expression::make_nil(bloc));
1953   else
1954     {
1955       Type* pt = Type::make_pointer_type(name);
1956       vals->push_back(Expression::make_type_descriptor(pt, bloc));
1957     }
1958
1959   ++p;
1960   go_assert(p == fields->end());
1961
1962   mpz_clear(iv);
1963
1964   return Expression::make_struct_composite_literal(td_type, vals, bloc);
1965 }
1966
1967 // Return a composite literal for the uncommon type information for
1968 // this type.  UNCOMMON_STRUCT_TYPE is the type of the uncommon type
1969 // struct.  If name is not NULL, it is the name of the type.  If
1970 // METHODS is not NULL, it is the list of methods.  ONLY_VALUE_METHODS
1971 // is true if only value methods should be included.  At least one of
1972 // NAME and METHODS must not be NULL.
1973
1974 Expression*
1975 Type::uncommon_type_constructor(Gogo* gogo, Type* uncommon_type,
1976                                 Named_type* name, const Methods* methods,
1977                                 bool only_value_methods) const
1978 {
1979   Location bloc = Linemap::predeclared_location();
1980
1981   const Struct_field_list* fields = uncommon_type->struct_type()->fields();
1982
1983   Expression_list* vals = new Expression_list();
1984   vals->reserve(3);
1985
1986   Struct_field_list::const_iterator p = fields->begin();
1987   go_assert(p->is_field_name("name"));
1988
1989   ++p;
1990   go_assert(p->is_field_name("pkgPath"));
1991
1992   if (name == NULL)
1993     {
1994       vals->push_back(Expression::make_nil(bloc));
1995       vals->push_back(Expression::make_nil(bloc));
1996     }
1997   else
1998     {
1999       Named_object* no = name->named_object();
2000       std::string n = Gogo::unpack_hidden_name(no->name());
2001       Expression* s = Expression::make_string(n, bloc);
2002       vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
2003
2004       if (name->is_builtin())
2005         vals->push_back(Expression::make_nil(bloc));
2006       else
2007         {
2008           const Package* package = no->package();
2009           const std::string& pkgpath(package == NULL
2010                                      ? gogo->pkgpath()
2011                                      : package->pkgpath());
2012           n.assign(pkgpath);
2013           unsigned int index;
2014           const Named_object* in_function = name->in_function(&index);
2015           if (in_function != NULL)
2016             {
2017               n.append(1, '.');
2018               n.append(Gogo::unpack_hidden_name(in_function->name()));
2019               if (index > 0)
2020                 {
2021                   char buf[30];
2022                   snprintf(buf, sizeof buf, "%u", index);
2023                   n.append(1, '.');
2024                   n.append(buf);
2025                 }
2026             }
2027           s = Expression::make_string(n, bloc);
2028           vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
2029         }
2030     }
2031
2032   ++p;
2033   go_assert(p->is_field_name("methods"));
2034   vals->push_back(this->methods_constructor(gogo, p->type(), methods,
2035                                             only_value_methods));
2036
2037   ++p;
2038   go_assert(p == fields->end());
2039
2040   Expression* r = Expression::make_struct_composite_literal(uncommon_type,
2041                                                             vals, bloc);
2042   return Expression::make_unary(OPERATOR_AND, r, bloc);
2043 }
2044
2045 // Sort methods by name.
2046
2047 class Sort_methods
2048 {
2049  public:
2050   bool
2051   operator()(const std::pair<std::string, const Method*>& m1,
2052              const std::pair<std::string, const Method*>& m2) const
2053   { return m1.first < m2.first; }
2054 };
2055
2056 // Return a composite literal for the type method table for this type.
2057 // METHODS_TYPE is the type of the table, and is a slice type.
2058 // METHODS is the list of methods.  If ONLY_VALUE_METHODS is true,
2059 // then only value methods are used.
2060
2061 Expression*
2062 Type::methods_constructor(Gogo* gogo, Type* methods_type,
2063                           const Methods* methods,
2064                           bool only_value_methods) const
2065 {
2066   Location bloc = Linemap::predeclared_location();
2067
2068   std::vector<std::pair<std::string, const Method*> > smethods;
2069   if (methods != NULL)
2070     {
2071       smethods.reserve(methods->count());
2072       for (Methods::const_iterator p = methods->begin();
2073            p != methods->end();
2074            ++p)
2075         {
2076           if (p->second->is_ambiguous())
2077             continue;
2078           if (only_value_methods && !p->second->is_value_method())
2079             continue;
2080           smethods.push_back(std::make_pair(p->first, p->second));
2081         }
2082     }
2083
2084   if (smethods.empty())
2085     return Expression::make_slice_composite_literal(methods_type, NULL, bloc);
2086
2087   std::sort(smethods.begin(), smethods.end(), Sort_methods());
2088
2089   Type* method_type = methods_type->array_type()->element_type();
2090
2091   Expression_list* vals = new Expression_list();
2092   vals->reserve(smethods.size());
2093   for (std::vector<std::pair<std::string, const Method*> >::const_iterator p
2094          = smethods.begin();
2095        p != smethods.end();
2096        ++p)
2097     vals->push_back(this->method_constructor(gogo, method_type, p->first,
2098                                              p->second, only_value_methods));
2099
2100   return Expression::make_slice_composite_literal(methods_type, vals, bloc);
2101 }
2102
2103 // Return a composite literal for a single method.  METHOD_TYPE is the
2104 // type of the entry.  METHOD_NAME is the name of the method and M is
2105 // the method information.
2106
2107 Expression*
2108 Type::method_constructor(Gogo*, Type* method_type,
2109                          const std::string& method_name,
2110                          const Method* m,
2111                          bool only_value_methods) const
2112 {
2113   Location bloc = Linemap::predeclared_location();
2114
2115   const Struct_field_list* fields = method_type->struct_type()->fields();
2116
2117   Expression_list* vals = new Expression_list();
2118   vals->reserve(5);
2119
2120   Struct_field_list::const_iterator p = fields->begin();
2121   go_assert(p->is_field_name("name"));
2122   const std::string n = Gogo::unpack_hidden_name(method_name);
2123   Expression* s = Expression::make_string(n, bloc);
2124   vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
2125
2126   ++p;
2127   go_assert(p->is_field_name("pkgPath"));
2128   if (!Gogo::is_hidden_name(method_name))
2129     vals->push_back(Expression::make_nil(bloc));
2130   else
2131     {
2132       s = Expression::make_string(Gogo::hidden_name_pkgpath(method_name),
2133                                   bloc);
2134       vals->push_back(Expression::make_unary(OPERATOR_AND, s, bloc));
2135     }
2136
2137   Named_object* no = (m->needs_stub_method()
2138                       ? m->stub_object()
2139                       : m->named_object());
2140
2141   Function_type* mtype;
2142   if (no->is_function())
2143     mtype = no->func_value()->type();
2144   else
2145     mtype = no->func_declaration_value()->type();
2146   go_assert(mtype->is_method());
2147   Type* nonmethod_type = mtype->copy_without_receiver();
2148
2149   ++p;
2150   go_assert(p->is_field_name("mtyp"));
2151   vals->push_back(Expression::make_type_descriptor(nonmethod_type, bloc));
2152
2153   ++p;
2154   go_assert(p->is_field_name("typ"));
2155   if (!only_value_methods && m->is_value_method())
2156     {
2157       // This is a value method on a pointer type.  Change the type of
2158       // the method to use a pointer receiver.  The implementation
2159       // always uses a pointer receiver anyhow.
2160       Type* rtype = mtype->receiver()->type();
2161       Type* prtype = Type::make_pointer_type(rtype);
2162       Typed_identifier* receiver =
2163         new Typed_identifier(mtype->receiver()->name(), prtype,
2164                              mtype->receiver()->location());
2165       mtype = Type::make_function_type(receiver,
2166                                        (mtype->parameters() == NULL
2167                                         ? NULL
2168                                         : mtype->parameters()->copy()),
2169                                        (mtype->results() == NULL
2170                                         ? NULL
2171                                         : mtype->results()->copy()),
2172                                        mtype->location());
2173     }
2174   vals->push_back(Expression::make_type_descriptor(mtype, bloc));
2175
2176   ++p;
2177   go_assert(p->is_field_name("tfn"));
2178   vals->push_back(Expression::make_func_reference(no, NULL, bloc));
2179
2180   ++p;
2181   go_assert(p == fields->end());
2182
2183   return Expression::make_struct_composite_literal(method_type, vals, bloc);
2184 }
2185
2186 // Return a composite literal for the type descriptor of a plain type.
2187 // RUNTIME_TYPE_KIND is the value of the kind field.  If NAME is not
2188 // NULL, it is the name to use as well as the list of methods.
2189
2190 Expression*
2191 Type::plain_type_descriptor(Gogo* gogo, int runtime_type_kind,
2192                             Named_type* name)
2193 {
2194   return this->type_descriptor_constructor(gogo, runtime_type_kind,
2195                                            name, NULL, true);
2196 }
2197
2198 // Return the type reflection string for this type.
2199
2200 std::string
2201 Type::reflection(Gogo* gogo) const
2202 {
2203   std::string ret;
2204
2205   // The do_reflection virtual function should set RET to the
2206   // reflection string.
2207   this->do_reflection(gogo, &ret);
2208
2209   return ret;
2210 }
2211
2212 // Return a mangled name for the type.
2213
2214 std::string
2215 Type::mangled_name(Gogo* gogo) const
2216 {
2217   std::string ret;
2218
2219   // The do_mangled_name virtual function should set RET to the
2220   // mangled name.  For a composite type it should append a code for
2221   // the composition and then call do_mangled_name on the components.
2222   this->do_mangled_name(gogo, &ret);
2223
2224   return ret;
2225 }
2226
2227 // Return whether the backend size of the type is known.
2228
2229 bool
2230 Type::is_backend_type_size_known(Gogo* gogo)
2231 {
2232   switch (this->classification_)
2233     {
2234     case TYPE_ERROR:
2235     case TYPE_VOID:
2236     case TYPE_BOOLEAN:
2237     case TYPE_INTEGER:
2238     case TYPE_FLOAT:
2239     case TYPE_COMPLEX:
2240     case TYPE_STRING:
2241     case TYPE_FUNCTION:
2242     case TYPE_POINTER:
2243     case TYPE_NIL:
2244     case TYPE_MAP:
2245     case TYPE_CHANNEL:
2246     case TYPE_INTERFACE:
2247       return true;
2248
2249     case TYPE_STRUCT:
2250       {
2251         const Struct_field_list* fields = this->struct_type()->fields();
2252         for (Struct_field_list::const_iterator pf = fields->begin();
2253              pf != fields->end();
2254              ++pf)
2255           if (!pf->type()->is_backend_type_size_known(gogo))
2256             return false;
2257         return true;
2258       }
2259
2260     case TYPE_ARRAY:
2261       {
2262         const Array_type* at = this->array_type();
2263         if (at->length() == NULL)
2264           return true;
2265         else
2266           {
2267             Numeric_constant nc;
2268             if (!at->length()->numeric_constant_value(&nc))
2269               return false;
2270             mpz_t ival;
2271             if (!nc.to_int(&ival))
2272               return false;
2273             mpz_clear(ival);
2274             return at->element_type()->is_backend_type_size_known(gogo);
2275           }
2276       }
2277
2278     case TYPE_NAMED:
2279       // Begin converting this type to the backend representation.
2280       // This will create a placeholder if necessary.
2281       this->get_backend(gogo);
2282       return this->named_type()->is_named_backend_type_size_known();
2283
2284     case TYPE_FORWARD:
2285       {
2286         Forward_declaration_type* fdt = this->forward_declaration_type();
2287         return fdt->real_type()->is_backend_type_size_known(gogo);
2288       }
2289
2290     case TYPE_SINK:
2291     case TYPE_CALL_MULTIPLE_RESULT:
2292       go_unreachable();
2293
2294     default:
2295       go_unreachable();
2296     }
2297 }
2298
2299 // If the size of the type can be determined, set *PSIZE to the size
2300 // in bytes and return true.  Otherwise, return false.  This queries
2301 // the backend.
2302
2303 bool
2304 Type::backend_type_size(Gogo* gogo, unsigned int *psize)
2305 {
2306   if (!this->is_backend_type_size_known(gogo))
2307     return false;
2308   Btype* bt = this->get_backend_placeholder(gogo);
2309   size_t size = gogo->backend()->type_size(bt);
2310   *psize = static_cast<unsigned int>(size);
2311   if (*psize != size)
2312     return false;
2313   return true;
2314 }
2315
2316 // If the alignment of the type can be determined, set *PALIGN to
2317 // the alignment in bytes and return true.  Otherwise, return false.
2318
2319 bool
2320 Type::backend_type_align(Gogo* gogo, unsigned int *palign)
2321 {
2322   if (!this->is_backend_type_size_known(gogo))
2323     return false;
2324   Btype* bt = this->get_backend_placeholder(gogo);
2325   size_t align = gogo->backend()->type_alignment(bt);
2326   *palign = static_cast<unsigned int>(align);
2327   if (*palign != align)
2328     return false;
2329   return true;
2330 }
2331
2332 // Like backend_type_align, but return the alignment when used as a
2333 // field.
2334
2335 bool
2336 Type::backend_type_field_align(Gogo* gogo, unsigned int *palign)
2337 {
2338   if (!this->is_backend_type_size_known(gogo))
2339     return false;
2340   Btype* bt = this->get_backend_placeholder(gogo);
2341   size_t a = gogo->backend()->type_field_alignment(bt);
2342   *palign = static_cast<unsigned int>(a);
2343   if (*palign != a)
2344     return false;
2345   return true;
2346 }
2347
2348 // Default function to export a type.
2349
2350 void
2351 Type::do_export(Export*) const
2352 {
2353   go_unreachable();
2354 }
2355
2356 // Import a type.
2357
2358 Type*
2359 Type::import_type(Import* imp)
2360 {
2361   if (imp->match_c_string("("))
2362     return Function_type::do_import(imp);
2363   else if (imp->match_c_string("*"))
2364     return Pointer_type::do_import(imp);
2365   else if (imp->match_c_string("struct "))
2366     return Struct_type::do_import(imp);
2367   else if (imp->match_c_string("["))
2368     return Array_type::do_import(imp);
2369   else if (imp->match_c_string("map "))
2370     return Map_type::do_import(imp);
2371   else if (imp->match_c_string("chan "))
2372     return Channel_type::do_import(imp);
2373   else if (imp->match_c_string("interface"))
2374     return Interface_type::do_import(imp);
2375   else
2376     {
2377       error_at(imp->location(), "import error: expected type");
2378       return Type::make_error_type();
2379     }
2380 }
2381
2382 // A type used to indicate a parsing error.  This exists to simplify
2383 // later error detection.
2384
2385 class Error_type : public Type
2386 {
2387  public:
2388   Error_type()
2389     : Type(TYPE_ERROR)
2390   { }
2391
2392  protected:
2393   bool
2394   do_compare_is_identity(Gogo*) const
2395   { return false; }
2396
2397   Btype*
2398   do_get_backend(Gogo* gogo)
2399   { return gogo->backend()->error_type(); }
2400
2401   Expression*
2402   do_type_descriptor(Gogo*, Named_type*)
2403   { return Expression::make_error(Linemap::predeclared_location()); }
2404
2405   void
2406   do_reflection(Gogo*, std::string*) const
2407   { go_assert(saw_errors()); }
2408
2409   void
2410   do_mangled_name(Gogo*, std::string* ret) const
2411   { ret->push_back('E'); }
2412 };
2413
2414 Type*
2415 Type::make_error_type()
2416 {
2417   static Error_type singleton_error_type;
2418   return &singleton_error_type;
2419 }
2420
2421 // The void type.
2422
2423 class Void_type : public Type
2424 {
2425  public:
2426   Void_type()
2427     : Type(TYPE_VOID)
2428   { }
2429
2430  protected:
2431   bool
2432   do_compare_is_identity(Gogo*) const
2433   { return false; }
2434
2435   Btype*
2436   do_get_backend(Gogo* gogo)
2437   { return gogo->backend()->void_type(); }
2438
2439   Expression*
2440   do_type_descriptor(Gogo*, Named_type*)
2441   { go_unreachable(); }
2442
2443   void
2444   do_reflection(Gogo*, std::string*) const
2445   { }
2446
2447   void
2448   do_mangled_name(Gogo*, std::string* ret) const
2449   { ret->push_back('v'); }
2450 };
2451
2452 Type*
2453 Type::make_void_type()
2454 {
2455   static Void_type singleton_void_type;
2456   return &singleton_void_type;
2457 }
2458
2459 // The boolean type.
2460
2461 class Boolean_type : public Type
2462 {
2463  public:
2464   Boolean_type()
2465     : Type(TYPE_BOOLEAN)
2466   { }
2467
2468  protected:
2469   bool
2470   do_compare_is_identity(Gogo*) const
2471   { return true; }
2472
2473   Btype*
2474   do_get_backend(Gogo* gogo)
2475   { return gogo->backend()->bool_type(); }
2476
2477   Expression*
2478   do_type_descriptor(Gogo*, Named_type* name);
2479
2480   // We should not be asked for the reflection string of a basic type.
2481   void
2482   do_reflection(Gogo*, std::string* ret) const
2483   { ret->append("bool"); }
2484
2485   void
2486   do_mangled_name(Gogo*, std::string* ret) const
2487   { ret->push_back('b'); }
2488 };
2489
2490 // Make the type descriptor.
2491
2492 Expression*
2493 Boolean_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2494 {
2495   if (name != NULL)
2496     return this->plain_type_descriptor(gogo, RUNTIME_TYPE_KIND_BOOL, name);
2497   else
2498     {
2499       Named_object* no = gogo->lookup_global("bool");
2500       go_assert(no != NULL);
2501       return Type::type_descriptor(gogo, no->type_value());
2502     }
2503 }
2504
2505 Type*
2506 Type::make_boolean_type()
2507 {
2508   static Boolean_type boolean_type;
2509   return &boolean_type;
2510 }
2511
2512 // The named type "bool".
2513
2514 static Named_type* named_bool_type;
2515
2516 // Get the named type "bool".
2517
2518 Named_type*
2519 Type::lookup_bool_type()
2520 {
2521   return named_bool_type;
2522 }
2523
2524 // Make the named type "bool".
2525
2526 Named_type*
2527 Type::make_named_bool_type()
2528 {
2529   Type* bool_type = Type::make_boolean_type();
2530   Named_object* named_object =
2531     Named_object::make_type("bool", NULL, bool_type,
2532                             Linemap::predeclared_location());
2533   Named_type* named_type = named_object->type_value();
2534   named_bool_type = named_type;
2535   return named_type;
2536 }
2537
2538 // Class Integer_type.
2539
2540 Integer_type::Named_integer_types Integer_type::named_integer_types;
2541
2542 // Create a new integer type.  Non-abstract integer types always have
2543 // names.
2544
2545 Named_type*
2546 Integer_type::create_integer_type(const char* name, bool is_unsigned,
2547                                   int bits, int runtime_type_kind)
2548 {
2549   Integer_type* integer_type = new Integer_type(false, is_unsigned, bits,
2550                                                 runtime_type_kind);
2551   std::string sname(name);
2552   Named_object* named_object =
2553     Named_object::make_type(sname, NULL, integer_type,
2554                             Linemap::predeclared_location());
2555   Named_type* named_type = named_object->type_value();
2556   std::pair<Named_integer_types::iterator, bool> ins =
2557     Integer_type::named_integer_types.insert(std::make_pair(sname, named_type));
2558   go_assert(ins.second);
2559   return named_type;
2560 }
2561
2562 // Look up an existing integer type.
2563
2564 Named_type*
2565 Integer_type::lookup_integer_type(const char* name)
2566 {
2567   Named_integer_types::const_iterator p =
2568     Integer_type::named_integer_types.find(name);
2569   go_assert(p != Integer_type::named_integer_types.end());
2570   return p->second;
2571 }
2572
2573 // Create a new abstract integer type.
2574
2575 Integer_type*
2576 Integer_type::create_abstract_integer_type()
2577 {
2578   static Integer_type* abstract_type;
2579   if (abstract_type == NULL)
2580     abstract_type = new Integer_type(true, false, INT_TYPE_SIZE,
2581                                      RUNTIME_TYPE_KIND_INT);
2582   return abstract_type;
2583 }
2584
2585 // Create a new abstract character type.
2586
2587 Integer_type*
2588 Integer_type::create_abstract_character_type()
2589 {
2590   static Integer_type* abstract_type;
2591   if (abstract_type == NULL)
2592     {
2593       abstract_type = new Integer_type(true, false, 32,
2594                                        RUNTIME_TYPE_KIND_INT32);
2595       abstract_type->set_is_rune();
2596     }
2597   return abstract_type;
2598 }
2599
2600 // Integer type compatibility.
2601
2602 bool
2603 Integer_type::is_identical(const Integer_type* t) const
2604 {
2605   if (this->is_unsigned_ != t->is_unsigned_ || this->bits_ != t->bits_)
2606     return false;
2607   return this->is_abstract_ == t->is_abstract_;
2608 }
2609
2610 // Hash code.
2611
2612 unsigned int
2613 Integer_type::do_hash_for_method(Gogo*) const
2614 {
2615   return ((this->bits_ << 4)
2616           + ((this->is_unsigned_ ? 1 : 0) << 8)
2617           + ((this->is_abstract_ ? 1 : 0) << 9));
2618 }
2619
2620 // Convert an Integer_type to the backend representation.
2621
2622 Btype*
2623 Integer_type::do_get_backend(Gogo* gogo)
2624 {
2625   if (this->is_abstract_)
2626     {
2627       go_assert(saw_errors());
2628       return gogo->backend()->error_type();
2629     }
2630   return gogo->backend()->integer_type(this->is_unsigned_, this->bits_);
2631 }
2632
2633 // The type descriptor for an integer type.  Integer types are always
2634 // named.
2635
2636 Expression*
2637 Integer_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2638 {
2639   go_assert(name != NULL || saw_errors());
2640   return this->plain_type_descriptor(gogo, this->runtime_type_kind_, name);
2641 }
2642
2643 // We should not be asked for the reflection string of a basic type.
2644
2645 void
2646 Integer_type::do_reflection(Gogo*, std::string*) const
2647 {
2648   go_assert(saw_errors());
2649 }
2650
2651 // Mangled name.
2652
2653 void
2654 Integer_type::do_mangled_name(Gogo*, std::string* ret) const
2655 {
2656   char buf[100];
2657   snprintf(buf, sizeof buf, "i%s%s%de",
2658            this->is_abstract_ ? "a" : "",
2659            this->is_unsigned_ ? "u" : "",
2660            this->bits_);
2661   ret->append(buf);
2662 }
2663
2664 // Make an integer type.
2665
2666 Named_type*
2667 Type::make_integer_type(const char* name, bool is_unsigned, int bits,
2668                         int runtime_type_kind)
2669 {
2670   return Integer_type::create_integer_type(name, is_unsigned, bits,
2671                                            runtime_type_kind);
2672 }
2673
2674 // Make an abstract integer type.
2675
2676 Integer_type*
2677 Type::make_abstract_integer_type()
2678 {
2679   return Integer_type::create_abstract_integer_type();
2680 }
2681
2682 // Make an abstract character type.
2683
2684 Integer_type*
2685 Type::make_abstract_character_type()
2686 {
2687   return Integer_type::create_abstract_character_type();
2688 }
2689
2690 // Look up an integer type.
2691
2692 Named_type*
2693 Type::lookup_integer_type(const char* name)
2694 {
2695   return Integer_type::lookup_integer_type(name);
2696 }
2697
2698 // Class Float_type.
2699
2700 Float_type::Named_float_types Float_type::named_float_types;
2701
2702 // Create a new float type.  Non-abstract float types always have
2703 // names.
2704
2705 Named_type*
2706 Float_type::create_float_type(const char* name, int bits,
2707                               int runtime_type_kind)
2708 {
2709   Float_type* float_type = new Float_type(false, bits, runtime_type_kind);
2710   std::string sname(name);
2711   Named_object* named_object =
2712     Named_object::make_type(sname, NULL, float_type,
2713                             Linemap::predeclared_location());
2714   Named_type* named_type = named_object->type_value();
2715   std::pair<Named_float_types::iterator, bool> ins =
2716     Float_type::named_float_types.insert(std::make_pair(sname, named_type));
2717   go_assert(ins.second);
2718   return named_type;
2719 }
2720
2721 // Look up an existing float type.
2722
2723 Named_type*
2724 Float_type::lookup_float_type(const char* name)
2725 {
2726   Named_float_types::const_iterator p =
2727     Float_type::named_float_types.find(name);
2728   go_assert(p != Float_type::named_float_types.end());
2729   return p->second;
2730 }
2731
2732 // Create a new abstract float type.
2733
2734 Float_type*
2735 Float_type::create_abstract_float_type()
2736 {
2737   static Float_type* abstract_type;
2738   if (abstract_type == NULL)
2739     abstract_type = new Float_type(true, 64, RUNTIME_TYPE_KIND_FLOAT64);
2740   return abstract_type;
2741 }
2742
2743 // Whether this type is identical with T.
2744
2745 bool
2746 Float_type::is_identical(const Float_type* t) const
2747 {
2748   if (this->bits_ != t->bits_)
2749     return false;
2750   return this->is_abstract_ == t->is_abstract_;
2751 }
2752
2753 // Hash code.
2754
2755 unsigned int
2756 Float_type::do_hash_for_method(Gogo*) const
2757 {
2758   return (this->bits_ << 4) + ((this->is_abstract_ ? 1 : 0) << 8);
2759 }
2760
2761 // Convert to the backend representation.
2762
2763 Btype*
2764 Float_type::do_get_backend(Gogo* gogo)
2765 {
2766   return gogo->backend()->float_type(this->bits_);
2767 }
2768
2769 // The type descriptor for a float type.  Float types are always named.
2770
2771 Expression*
2772 Float_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2773 {
2774   go_assert(name != NULL || saw_errors());
2775   return this->plain_type_descriptor(gogo, this->runtime_type_kind_, name);
2776 }
2777
2778 // We should not be asked for the reflection string of a basic type.
2779
2780 void
2781 Float_type::do_reflection(Gogo*, std::string*) const
2782 {
2783   go_assert(saw_errors());
2784 }
2785
2786 // Mangled name.
2787
2788 void
2789 Float_type::do_mangled_name(Gogo*, std::string* ret) const
2790 {
2791   char buf[100];
2792   snprintf(buf, sizeof buf, "f%s%de",
2793            this->is_abstract_ ? "a" : "",
2794            this->bits_);
2795   ret->append(buf);
2796 }
2797
2798 // Make a floating point type.
2799
2800 Named_type*
2801 Type::make_float_type(const char* name, int bits, int runtime_type_kind)
2802 {
2803   return Float_type::create_float_type(name, bits, runtime_type_kind);
2804 }
2805
2806 // Make an abstract float type.
2807
2808 Float_type*
2809 Type::make_abstract_float_type()
2810 {
2811   return Float_type::create_abstract_float_type();
2812 }
2813
2814 // Look up a float type.
2815
2816 Named_type*
2817 Type::lookup_float_type(const char* name)
2818 {
2819   return Float_type::lookup_float_type(name);
2820 }
2821
2822 // Class Complex_type.
2823
2824 Complex_type::Named_complex_types Complex_type::named_complex_types;
2825
2826 // Create a new complex type.  Non-abstract complex types always have
2827 // names.
2828
2829 Named_type*
2830 Complex_type::create_complex_type(const char* name, int bits,
2831                                   int runtime_type_kind)
2832 {
2833   Complex_type* complex_type = new Complex_type(false, bits,
2834                                                 runtime_type_kind);
2835   std::string sname(name);
2836   Named_object* named_object =
2837     Named_object::make_type(sname, NULL, complex_type,
2838                             Linemap::predeclared_location());
2839   Named_type* named_type = named_object->type_value();
2840   std::pair<Named_complex_types::iterator, bool> ins =
2841     Complex_type::named_complex_types.insert(std::make_pair(sname,
2842                                                             named_type));
2843   go_assert(ins.second);
2844   return named_type;
2845 }
2846
2847 // Look up an existing complex type.
2848
2849 Named_type*
2850 Complex_type::lookup_complex_type(const char* name)
2851 {
2852   Named_complex_types::const_iterator p =
2853     Complex_type::named_complex_types.find(name);
2854   go_assert(p != Complex_type::named_complex_types.end());
2855   return p->second;
2856 }
2857
2858 // Create a new abstract complex type.
2859
2860 Complex_type*
2861 Complex_type::create_abstract_complex_type()
2862 {
2863   static Complex_type* abstract_type;
2864   if (abstract_type == NULL)
2865     abstract_type = new Complex_type(true, 128, RUNTIME_TYPE_KIND_COMPLEX128);
2866   return abstract_type;
2867 }
2868
2869 // Whether this type is identical with T.
2870
2871 bool
2872 Complex_type::is_identical(const Complex_type *t) const
2873 {
2874   if (this->bits_ != t->bits_)
2875     return false;
2876   return this->is_abstract_ == t->is_abstract_;
2877 }
2878
2879 // Hash code.
2880
2881 unsigned int
2882 Complex_type::do_hash_for_method(Gogo*) const
2883 {
2884   return (this->bits_ << 4) + ((this->is_abstract_ ? 1 : 0) << 8);
2885 }
2886
2887 // Convert to the backend representation.
2888
2889 Btype*
2890 Complex_type::do_get_backend(Gogo* gogo)
2891 {
2892   return gogo->backend()->complex_type(this->bits_);
2893 }
2894
2895 // The type descriptor for a complex type.  Complex types are always
2896 // named.
2897
2898 Expression*
2899 Complex_type::do_type_descriptor(Gogo* gogo, Named_type* name)
2900 {
2901   go_assert(name != NULL || saw_errors());
2902   return this->plain_type_descriptor(gogo, this->runtime_type_kind_, name);
2903 }
2904
2905 // We should not be asked for the reflection string of a basic type.
2906
2907 void
2908 Complex_type::do_reflection(Gogo*, std::string*) const
2909 {
2910   go_assert(saw_errors());
2911 }
2912
2913 // Mangled name.
2914
2915 void
2916 Complex_type::do_mangled_name(Gogo*, std::string* ret) const
2917 {
2918   char buf[100];
2919   snprintf(buf, sizeof buf, "c%s%de",
2920            this->is_abstract_ ? "a" : "",
2921            this->bits_);
2922   ret->append(buf);
2923 }
2924
2925 // Make a complex type.
2926
2927 Named_type*
2928 Type::make_complex_type(const char* name, int bits, int runtime_type_kind)
2929 {
2930   return Complex_type::create_complex_type(name, bits, runtime_type_kind);
2931 }
2932
2933 // Make an abstract complex type.
2934
2935 Complex_type*
2936 Type::make_abstract_complex_type()
2937 {
2938   return Complex_type::create_abstract_complex_type();
2939 }
2940
2941 // Look up a complex type.
2942
2943 Named_type*
2944 Type::lookup_complex_type(const char* name)
2945 {
2946   return Complex_type::lookup_complex_type(name);
2947 }
2948
2949 // Class String_type.
2950
2951 // Convert String_type to the backend representation.  A string is a
2952 // struct with two fields: a pointer to the characters and a length.
2953
2954 Btype*
2955 String_type::do_get_backend(Gogo* gogo)
2956 {
2957   static Btype* backend_string_type;
2958   if (backend_string_type == NULL)
2959     {
2960       std::vector<Backend::Btyped_identifier> fields(2);
2961
2962       Type* b = gogo->lookup_global("byte")->type_value();
2963       Type* pb = Type::make_pointer_type(b);
2964
2965       // We aren't going to get back to this field to finish the
2966       // backend representation, so force it to be finished now.
2967       if (!gogo->named_types_are_converted())
2968         {
2969           pb->get_backend_placeholder(gogo);
2970           pb->finish_backend(gogo);
2971         }
2972
2973       fields[0].name = "__data";
2974       fields[0].btype = pb->get_backend(gogo);
2975       fields[0].location = Linemap::predeclared_location();
2976
2977       Type* int_type = Type::lookup_integer_type("int");
2978       fields[1].name = "__length";
2979       fields[1].btype = int_type->get_backend(gogo);
2980       fields[1].location = fields[0].location;
2981
2982       backend_string_type = gogo->backend()->struct_type(fields);
2983     }
2984   return backend_string_type;
2985 }
2986
2987 // Return a tree for the length of STRING.
2988
2989 tree
2990 String_type::length_tree(Gogo*, tree string)
2991 {
2992   tree string_type = TREE_TYPE(string);
2993   go_assert(TREE_CODE(string_type) == RECORD_TYPE);
2994   tree length_field = DECL_CHAIN(TYPE_FIELDS(string_type));
2995   go_assert(strcmp(IDENTIFIER_POINTER(DECL_NAME(length_field)),
2996                     "__length") == 0);
2997   return fold_build3(COMPONENT_REF, integer_type_node, string,
2998                      length_field, NULL_TREE);
2999 }
3000
3001 // Return a tree for a pointer to the bytes of STRING.
3002
3003 tree
3004 String_type::bytes_tree(Gogo*, tree string)
3005 {
3006   tree string_type = TREE_TYPE(string);
3007   go_assert(TREE_CODE(string_type) == RECORD_TYPE);
3008   tree bytes_field = TYPE_FIELDS(string_type);
3009   go_assert(strcmp(IDENTIFIER_POINTER(DECL_NAME(bytes_field)),
3010                     "__data") == 0);
3011   return fold_build3(COMPONENT_REF, TREE_TYPE(bytes_field), string,
3012                      bytes_field, NULL_TREE);
3013 }
3014
3015 // The type descriptor for the string type.
3016
3017 Expression*
3018 String_type::do_type_descriptor(Gogo* gogo, Named_type* name)
3019 {
3020   if (name != NULL)
3021     return this->plain_type_descriptor(gogo, RUNTIME_TYPE_KIND_STRING, name);
3022   else
3023     {
3024       Named_object* no = gogo->lookup_global("string");
3025       go_assert(no != NULL);
3026       return Type::type_descriptor(gogo, no->type_value());
3027     }
3028 }
3029
3030 // We should not be asked for the reflection string of a basic type.
3031
3032 void
3033 String_type::do_reflection(Gogo*, std::string* ret) const
3034 {
3035   ret->append("string");
3036 }
3037
3038 // Mangled name of a string type.
3039
3040 void
3041 String_type::do_mangled_name(Gogo*, std::string* ret) const
3042 {
3043   ret->push_back('z');
3044 }
3045
3046 // Make a string type.
3047
3048 Type*
3049 Type::make_string_type()
3050 {
3051   static String_type string_type;
3052   return &string_type;
3053 }
3054
3055 // The named type "string".
3056
3057 static Named_type* named_string_type;
3058
3059 // Get the named type "string".
3060
3061 Named_type*
3062 Type::lookup_string_type()
3063 {
3064   return named_string_type;
3065 }
3066
3067 // Make the named type string.
3068
3069 Named_type*
3070 Type::make_named_string_type()
3071 {
3072   Type* string_type = Type::make_string_type();
3073   Named_object* named_object =
3074     Named_object::make_type("string", NULL, string_type,
3075                             Linemap::predeclared_location());
3076   Named_type* named_type = named_object->type_value();
3077   named_string_type = named_type;
3078   return named_type;
3079 }
3080
3081 // The sink type.  This is the type of the blank identifier _.  Any
3082 // type may be assigned to it.
3083
3084 class Sink_type : public Type
3085 {
3086  public:
3087   Sink_type()
3088     : Type(TYPE_SINK)
3089   { }
3090
3091  protected:
3092   bool
3093   do_compare_is_identity(Gogo*) const
3094   { return false; }
3095
3096   Btype*
3097   do_get_backend(Gogo*)
3098   { go_unreachable(); }
3099
3100   Expression*
3101   do_type_descriptor(Gogo*, Named_type*)
3102   { go_unreachable(); }
3103
3104   void
3105   do_reflection(Gogo*, std::string*) const
3106   { go_unreachable(); }
3107
3108   void
3109   do_mangled_name(Gogo*, std::string*) const
3110   { go_unreachable(); }
3111 };
3112
3113 // Make the sink type.
3114
3115 Type*
3116 Type::make_sink_type()
3117 {
3118   static Sink_type sink_type;
3119   return &sink_type;
3120 }
3121
3122 // Class Function_type.
3123
3124 // Traversal.
3125
3126 int
3127 Function_type::do_traverse(Traverse* traverse)
3128 {
3129   if (this->receiver_ != NULL
3130       && Type::traverse(this->receiver_->type(), traverse) == TRAVERSE_EXIT)
3131     return TRAVERSE_EXIT;
3132   if (this->parameters_ != NULL
3133       && this->parameters_->traverse(traverse) == TRAVERSE_EXIT)
3134     return TRAVERSE_EXIT;
3135   if (this->results_ != NULL
3136       && this->results_->traverse(traverse) == TRAVERSE_EXIT)
3137     return TRAVERSE_EXIT;
3138   return TRAVERSE_CONTINUE;
3139 }
3140
3141 // Returns whether T is a valid redeclaration of this type.  If this
3142 // returns false, and REASON is not NULL, *REASON may be set to a
3143 // brief explanation of why it returned false.
3144
3145 bool
3146 Function_type::is_valid_redeclaration(const Function_type* t,
3147                                       std::string* reason) const
3148 {
3149   if (!this->is_identical(t, false, true, reason))
3150     return false;
3151
3152   // A redeclaration of a function is required to use the same names
3153   // for the receiver and parameters.
3154   if (this->receiver() != NULL
3155       && this->receiver()->name() != t->receiver()->name())
3156     {
3157       if (reason != NULL)
3158         *reason = "receiver name changed";
3159       return false;
3160     }
3161
3162   const Typed_identifier_list* parms1 = this->parameters();
3163   const Typed_identifier_list* parms2 = t->parameters();
3164   if (parms1 != NULL)
3165     {
3166       Typed_identifier_list::const_iterator p1 = parms1->begin();
3167       for (Typed_identifier_list::const_iterator p2 = parms2->begin();
3168            p2 != parms2->end();
3169            ++p2, ++p1)
3170         {
3171           if (p1->name() != p2->name())
3172             {
3173               if (reason != NULL)
3174                 *reason = "parameter name changed";
3175               return false;
3176             }
3177
3178           // This is called at parse time, so we may have unknown
3179           // types.
3180           Type* t1 = p1->type()->forwarded();
3181           Type* t2 = p2->type()->forwarded();
3182           if (t1 != t2
3183               && t1->forward_declaration_type() != NULL
3184               && (t2->forward_declaration_type() == NULL
3185                   || (t1->forward_declaration_type()->named_object()
3186                       != t2->forward_declaration_type()->named_object())))
3187             return false;
3188         }
3189     }
3190
3191   const Typed_identifier_list* results1 = this->results();
3192   const Typed_identifier_list* results2 = t->results();
3193   if (results1 != NULL)
3194     {
3195       Typed_identifier_list::const_iterator res1 = results1->begin();
3196       for (Typed_identifier_list::const_iterator res2 = results2->begin();
3197            res2 != results2->end();
3198            ++res2, ++res1)
3199         {
3200           if (res1->name() != res2->name())
3201             {
3202               if (reason != NULL)
3203                 *reason = "result name changed";
3204               return false;
3205             }
3206
3207           // This is called at parse time, so we may have unknown
3208           // types.
3209           Type* t1 = res1->type()->forwarded();
3210           Type* t2 = res2->type()->forwarded();
3211           if (t1 != t2
3212               && t1->forward_declaration_type() != NULL
3213               && (t2->forward_declaration_type() == NULL
3214                   || (t1->forward_declaration_type()->named_object()
3215                       != t2->forward_declaration_type()->named_object())))
3216             return false;
3217         }
3218     }
3219
3220   return true;
3221 }
3222
3223 // Check whether T is the same as this type.
3224
3225 bool
3226 Function_type::is_identical(const Function_type* t, bool ignore_receiver,
3227                             bool errors_are_identical,
3228                             std::string* reason) const
3229 {
3230   if (!ignore_receiver)
3231     {
3232       const Typed_identifier* r1 = this->receiver();
3233       const Typed_identifier* r2 = t->receiver();
3234       if ((r1 != NULL) != (r2 != NULL))
3235         {
3236           if (reason != NULL)
3237             *reason = _("different receiver types");
3238           return false;
3239         }
3240       if (r1 != NULL)
3241         {
3242           if (!Type::are_identical(r1->type(), r2->type(), errors_are_identical,
3243                                    reason))
3244             {
3245               if (reason != NULL && !reason->empty())
3246                 *reason = "receiver: " + *reason;
3247               return false;
3248             }
3249         }
3250     }
3251
3252   const Typed_identifier_list* parms1 = this->parameters();
3253   const Typed_identifier_list* parms2 = t->parameters();
3254   if ((parms1 != NULL) != (parms2 != NULL))
3255     {
3256       if (reason != NULL)
3257         *reason = _("different number of parameters");
3258       return false;
3259     }
3260   if (parms1 != NULL)
3261     {
3262       Typed_identifier_list::const_iterator p1 = parms1->begin();
3263       for (Typed_identifier_list::const_iterator p2 = parms2->begin();
3264            p2 != parms2->end();
3265            ++p2, ++p1)
3266         {
3267           if (p1 == parms1->end())
3268             {
3269               if (reason != NULL)
3270                 *reason = _("different number of parameters");
3271               return false;
3272             }
3273
3274           if (!Type::are_identical(p1->type(), p2->type(),
3275                                    errors_are_identical, NULL))
3276             {
3277               if (reason != NULL)
3278                 *reason = _("different parameter types");
3279               return false;
3280             }
3281         }
3282       if (p1 != parms1->end())
3283         {
3284           if (reason != NULL)
3285             *reason = _("different number of parameters");
3286         return false;
3287         }
3288     }
3289
3290   if (this->is_varargs() != t->is_varargs())
3291     {
3292       if (reason != NULL)
3293         *reason = _("different varargs");
3294       return false;
3295     }
3296
3297   const Typed_identifier_list* results1 = this->results();
3298   const Typed_identifier_list* results2 = t->results();
3299   if ((results1 != NULL) != (results2 != NULL))
3300     {
3301       if (reason != NULL)
3302         *reason = _("different number of results");
3303       return false;
3304     }
3305   if (results1 != NULL)
3306     {
3307       Typed_identifier_list::const_iterator res1 = results1->begin();
3308       for (Typed_identifier_list::const_iterator res2 = results2->begin();
3309            res2 != results2->end();
3310            ++res2, ++res1)
3311         {
3312           if (res1 == results1->end())
3313             {
3314               if (reason != NULL)
3315                 *reason = _("different number of results");
3316               return false;
3317             }
3318
3319           if (!Type::are_identical(res1->type(), res2->type(),
3320                                    errors_are_identical, NULL))
3321             {
3322               if (reason != NULL)
3323                 *reason = _("different result types");
3324               return false;
3325             }
3326         }
3327       if (res1 != results1->end())
3328         {
3329           if (reason != NULL)
3330             *reason = _("different number of results");
3331           return false;
3332         }
3333     }
3334
3335   return true;
3336 }
3337
3338 // Hash code.
3339
3340 unsigned int
3341 Function_type::do_hash_for_method(Gogo* gogo) const
3342 {
3343   unsigned int ret = 0;
3344   // We ignore the receiver type for hash codes, because we need to
3345   // get the same hash code for a method in an interface and a method
3346   // declared for a type.  The former will not have a receiver.
3347   if (this->parameters_ != NULL)
3348     {
3349       int shift = 1;
3350       for (Typed_identifier_list::const_iterator p = this->parameters_->begin();
3351            p != this->parameters_->end();
3352            ++p, ++shift)
3353         ret += p->type()->hash_for_method(gogo) << shift;
3354     }
3355   if (this->results_ != NULL)
3356     {
3357       int shift = 2;
3358       for (Typed_identifier_list::const_iterator p = this->results_->begin();
3359            p != this->results_->end();
3360            ++p, ++shift)
3361         ret += p->type()->hash_for_method(gogo) << shift;
3362     }
3363   if (this->is_varargs_)
3364     ret += 1;
3365   ret <<= 4;
3366   return ret;
3367 }
3368
3369 // Get the backend representation for a function type.
3370
3371 Btype*
3372 Function_type::do_get_backend(Gogo* gogo)
3373 {
3374   Backend::Btyped_identifier breceiver;
3375   if (this->receiver_ != NULL)
3376     {
3377       breceiver.name = Gogo::unpack_hidden_name(this->receiver_->name());
3378
3379       // We always pass the address of the receiver parameter, in
3380       // order to make interface calls work with unknown types.
3381       Type* rtype = this->receiver_->type();
3382       if (rtype->points_to() == NULL)
3383         rtype = Type::make_pointer_type(rtype);
3384       breceiver.btype = rtype->get_backend(gogo);
3385       breceiver.location = this->receiver_->location();
3386     }
3387
3388   std::vector<Backend::Btyped_identifier> bparameters;
3389   if (this->parameters_ != NULL)
3390     {
3391       bparameters.resize(this->parameters_->size());
3392       size_t i = 0;
3393       for (Typed_identifier_list::const_iterator p = this->parameters_->begin();
3394            p != this->parameters_->end();
3395            ++p, ++i)
3396         {
3397           bparameters[i].name = Gogo::unpack_hidden_name(p->name());
3398           bparameters[i].btype = p->type()->get_backend(gogo);
3399           bparameters[i].location = p->location();
3400         }
3401       go_assert(i == bparameters.size());
3402     }
3403
3404   std::vector<Backend::Btyped_identifier> bresults;
3405   if (this->results_ != NULL)
3406     {
3407       bresults.resize(this->results_->size());
3408       size_t i = 0;
3409       for (Typed_identifier_list::const_iterator p = this->results_->begin();
3410            p != this->results_->end();
3411            ++p, ++i)
3412         {
3413           bresults[i].name = Gogo::unpack_hidden_name(p->name());
3414           bresults[i].btype = p->type()->get_backend(gogo);
3415           bresults[i].location = p->location();
3416         }
3417       go_assert(i == bresults.size());
3418     }
3419
3420   return gogo->backend()->function_type(breceiver, bparameters, bresults,
3421                                         this->location());
3422 }
3423
3424 // The type of a function type descriptor.
3425
3426 Type*
3427 Function_type::make_function_type_descriptor_type()
3428 {
3429   static Type* ret;
3430   if (ret == NULL)
3431     {
3432       Type* tdt = Type::make_type_descriptor_type();
3433       Type* ptdt = Type::make_type_descriptor_ptr_type();
3434
3435       Type* bool_type = Type::lookup_bool_type();
3436
3437       Type* slice_type = Type::make_array_type(ptdt, NULL);
3438
3439       Struct_type* s = Type::make_builtin_struct_type(4,
3440                                                       "", tdt,
3441                                                       "dotdotdot", bool_type,
3442                                                       "in", slice_type,
3443                                                       "out", slice_type);
3444
3445       ret = Type::make_builtin_named_type("FuncType", s);
3446     }
3447
3448   return ret;
3449 }
3450
3451 // The type descriptor for a function type.
3452
3453 Expression*
3454 Function_type::do_type_descriptor(Gogo* gogo, Named_type* name)
3455 {
3456   Location bloc = Linemap::predeclared_location();
3457
3458   Type* ftdt = Function_type::make_function_type_descriptor_type();
3459
3460   const Struct_field_list* fields = ftdt->struct_type()->fields();
3461
3462   Expression_list* vals = new Expression_list();
3463   vals->reserve(4);
3464
3465   Struct_field_list::const_iterator p = fields->begin();
3466   go_assert(p->is_field_name("commonType"));
3467   vals->push_back(this->type_descriptor_constructor(gogo,
3468                                                     RUNTIME_TYPE_KIND_FUNC,
3469                                                     name, NULL, true));
3470
3471   ++p;
3472   go_assert(p->is_field_name("dotdotdot"));
3473   vals->push_back(Expression::make_boolean(this->is_varargs(), bloc));
3474
3475   ++p;
3476   go_assert(p->is_field_name("in"));
3477   vals->push_back(this->type_descriptor_params(p->type(), this->receiver(),
3478                                                this->parameters()));
3479
3480   ++p;
3481   go_assert(p->is_field_name("out"));
3482   vals->push_back(this->type_descriptor_params(p->type(), NULL,
3483                                                this->results()));
3484
3485   ++p;
3486   go_assert(p == fields->end());
3487
3488   return Expression::make_struct_composite_literal(ftdt, vals, bloc);
3489 }
3490
3491 // Return a composite literal for the parameters or results of a type
3492 // descriptor.
3493
3494 Expression*
3495 Function_type::type_descriptor_params(Type* params_type,
3496                                       const Typed_identifier* receiver,
3497                                       const Typed_identifier_list* params)
3498 {
3499   Location bloc = Linemap::predeclared_location();
3500
3501   if (receiver == NULL && params == NULL)
3502     return Expression::make_slice_composite_literal(params_type, NULL, bloc);
3503
3504   Expression_list* vals = new Expression_list();
3505   vals->reserve((params == NULL ? 0 : params->size())
3506                 + (receiver != NULL ? 1 : 0));
3507
3508   if (receiver != NULL)
3509     vals->push_back(Expression::make_type_descriptor(receiver->type(), bloc));
3510
3511   if (params != NULL)
3512     {
3513       for (Typed_identifier_list::const_iterator p = params->begin();
3514            p != params->end();
3515            ++p)
3516         vals->push_back(Expression::make_type_descriptor(p->type(), bloc));
3517     }
3518
3519   return Expression::make_slice_composite_literal(params_type, vals, bloc);
3520 }
3521
3522 // The reflection string.
3523
3524 void
3525 Function_type::do_reflection(Gogo* gogo, std::string* ret) const
3526 {
3527   // FIXME: Turn this off until we straighten out the type of the
3528   // struct field used in a go statement which calls a method.