OSDN Git Service

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