OSDN Git Service

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