OSDN Git Service

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