gcc/go/gofrontend/gogo.cc

   1 // gogo.cc -- Go frontend parsed representation.
   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 "go-c.h"
  10 #include "go-dump.h"
  11 #include "lex.h"
  12 #include "types.h"
  13 #include "statements.h"
  14 #include "expressions.h"
  15 #include "dataflow.h"
  16 #include "import.h"
  17 #include "export.h"
  18 #include "gogo.h"
  19
  20 // Class Gogo.
  21
  22 Gogo::Gogo(int int_type_size, int float_type_size, int pointer_size)
  23   : package_(NULL),
  24     functions_(),
  25     globals_(new Bindings(NULL)),
  26     imports_(),
  27     imported_unsafe_(false),
  28     packages_(),
  29     map_descriptors_(NULL),
  30     type_descriptor_decls_(NULL),
  31     init_functions_(),
  32     need_init_fn_(false),
  33     init_fn_name_(),
  34     imported_init_fns_(),
  35     unique_prefix_(),
  36     interface_types_()
  37 {
  38   const source_location loc = BUILTINS_LOCATION;
  39
  40   Named_type* uint8_type = Type::make_integer_type("uint8", true, 8,
  41                                                    RUNTIME_TYPE_KIND_UINT8);
  42   this->add_named_type(uint8_type);
  43   this->add_named_type(Type::make_integer_type("uint16", true,  16,
  44                                                RUNTIME_TYPE_KIND_UINT16));
  45   this->add_named_type(Type::make_integer_type("uint32", true,  32,
  46                                                RUNTIME_TYPE_KIND_UINT32));
  47   this->add_named_type(Type::make_integer_type("uint64", true,  64,
  48                                                RUNTIME_TYPE_KIND_UINT64));
  49
  50   this->add_named_type(Type::make_integer_type("int8",  false,   8,
  51                                                RUNTIME_TYPE_KIND_INT8));
  52   this->add_named_type(Type::make_integer_type("int16", false,  16,
  53                                                RUNTIME_TYPE_KIND_INT16));
  54   this->add_named_type(Type::make_integer_type("int32", false,  32,
  55                                                RUNTIME_TYPE_KIND_INT32));
  56   this->add_named_type(Type::make_integer_type("int64", false,  64,
  57                                                RUNTIME_TYPE_KIND_INT64));
  58
  59   this->add_named_type(Type::make_float_type("float32", 32,
  60                                              RUNTIME_TYPE_KIND_FLOAT32));
  61   this->add_named_type(Type::make_float_type("float64", 64,
  62                                              RUNTIME_TYPE_KIND_FLOAT64));
  63
  64   this->add_named_type(Type::make_complex_type("complex64", 64,
  65                                                RUNTIME_TYPE_KIND_COMPLEX64));
  66   this->add_named_type(Type::make_complex_type("complex128", 128,
  67                                                RUNTIME_TYPE_KIND_COMPLEX128));
  68
  69   if (int_type_size < 32)
  70     int_type_size = 32;
  71   this->add_named_type(Type::make_integer_type("uint", true,
  72                                                int_type_size,
  73                                                RUNTIME_TYPE_KIND_UINT));
  74   Named_type* int_type = Type::make_integer_type("int", false, int_type_size,
  75                                                  RUNTIME_TYPE_KIND_INT);
  76   this->add_named_type(int_type);
  77
  78   // "byte" is an alias for "uint8".  Construct a Named_object which
  79   // points to UINT8_TYPE.  Note that this breaks the normal pairing
  80   // in which a Named_object points to a Named_type which points back
  81   // to the same Named_object.
  82   Named_object* byte_type = this->declare_type("byte", loc);
  83   byte_type->set_type_value(uint8_type);
  84
  85   this->add_named_type(Type::make_integer_type("uintptr", true,
  86                                                pointer_size,
  87                                                RUNTIME_TYPE_KIND_UINTPTR));
  88
  89   this->add_named_type(Type::make_float_type("float", float_type_size,
  90                                              RUNTIME_TYPE_KIND_FLOAT));
  91
  92   this->add_named_type(Type::make_complex_type("complex", float_type_size * 2,
  93                                                RUNTIME_TYPE_KIND_COMPLEX));
  94
  95   this->add_named_type(Type::make_named_bool_type());
  96
  97   this->add_named_type(Type::make_named_string_type());
  98
  99   this->globals_->add_constant(Typed_identifier("true",
 100                                                 Type::make_boolean_type(),
 101                                                 loc),
 102                                NULL,
 103                                Expression::make_boolean(true, loc),
 104                                0);
 105   this->globals_->add_constant(Typed_identifier("false",
 106                                                 Type::make_boolean_type(),
 107                                                 loc),
 108                                NULL,
 109                                Expression::make_boolean(false, loc),
 110                                0);
 111
 112   this->globals_->add_constant(Typed_identifier("nil", Type::make_nil_type(),
 113                                                 loc),
 114                                NULL,
 115                                Expression::make_nil(loc),
 116                                0);
 117
 118   Type* abstract_int_type = Type::make_abstract_integer_type();
 119   this->globals_->add_constant(Typed_identifier("iota", abstract_int_type,
 120                                                 loc),
 121                                NULL,
 122                                Expression::make_iota(),
 123                                0);
 124
 125   Function_type* new_type = Type::make_function_type(NULL, NULL, NULL, loc);
 126   new_type->set_is_varargs();
 127   new_type->set_is_builtin();
 128   this->globals_->add_function_declaration("new", NULL, new_type, loc);
 129
 130   Function_type* make_type = Type::make_function_type(NULL, NULL, NULL, loc);
 131   make_type->set_is_varargs();
 132   make_type->set_is_builtin();
 133   this->globals_->add_function_declaration("make", NULL, make_type, loc);
 134
 135   Typed_identifier_list* len_result = new Typed_identifier_list();
 136   len_result->push_back(Typed_identifier("", int_type, loc));
 137   Function_type* len_type = Type::make_function_type(NULL, NULL, len_result,
 138                                                      loc);
 139   len_type->set_is_builtin();
 140   this->globals_->add_function_declaration("len", NULL, len_type, loc);
 141
 142   Typed_identifier_list* cap_result = new Typed_identifier_list();
 143   cap_result->push_back(Typed_identifier("", int_type, loc));
 144   Function_type* cap_type = Type::make_function_type(NULL, NULL, len_result,
 145                                                      loc);
 146   cap_type->set_is_builtin();
 147   this->globals_->add_function_declaration("cap", NULL, cap_type, loc);
 148
 149   Function_type* print_type = Type::make_function_type(NULL, NULL, NULL, loc);
 150   print_type->set_is_varargs();
 151   print_type->set_is_builtin();
 152   this->globals_->add_function_declaration("print", NULL, print_type, loc);
 153
 154   print_type = Type::make_function_type(NULL, NULL, NULL, loc);
 155   print_type->set_is_varargs();
 156   print_type->set_is_builtin();
 157   this->globals_->add_function_declaration("println", NULL, print_type, loc);
 158
 159   Type *empty = Type::make_interface_type(NULL, loc);
 160   Typed_identifier_list* panic_parms = new Typed_identifier_list();
 161   panic_parms->push_back(Typed_identifier("e", empty, loc));
 162   Function_type *panic_type = Type::make_function_type(NULL, panic_parms,
 163                                                        NULL, loc);
 164   panic_type->set_is_builtin();
 165   this->globals_->add_function_declaration("panic", NULL, panic_type, loc);
 166
 167   Typed_identifier_list* recover_result = new Typed_identifier_list();
 168   recover_result->push_back(Typed_identifier("", empty, loc));
 169   Function_type* recover_type = Type::make_function_type(NULL, NULL,
 170                                                          recover_result,
 171                                                          loc);
 172   recover_type->set_is_builtin();
 173   this->globals_->add_function_declaration("recover", NULL, recover_type, loc);
 174
 175   Function_type* close_type = Type::make_function_type(NULL, NULL, NULL, loc);
 176   close_type->set_is_varargs();
 177   close_type->set_is_builtin();
 178   this->globals_->add_function_declaration("close", NULL, close_type, loc);
 179
 180   Typed_identifier_list* closed_result = new Typed_identifier_list();
 181   closed_result->push_back(Typed_identifier("", Type::lookup_bool_type(),
 182                                             loc));
 183   Function_type* closed_type = Type::make_function_type(NULL, NULL,
 184                                                         closed_result, loc);
 185   closed_type->set_is_varargs();
 186   closed_type->set_is_builtin();
 187   this->globals_->add_function_declaration("closed", NULL, closed_type, loc);
 188
 189   Typed_identifier_list* copy_result = new Typed_identifier_list();
 190   copy_result->push_back(Typed_identifier("", int_type, loc));
 191   Function_type* copy_type = Type::make_function_type(NULL, NULL,
 192                                                       copy_result, loc);
 193   copy_type->set_is_varargs();
 194   copy_type->set_is_builtin();
 195   this->globals_->add_function_declaration("copy", NULL, copy_type, loc);
 196
 197   Function_type* append_type = Type::make_function_type(NULL, NULL, NULL, loc);
 198   append_type->set_is_varargs();
 199   append_type->set_is_builtin();
 200   this->globals_->add_function_declaration("append", NULL, append_type, loc);
 201
 202   Function_type* cmplx_type = Type::make_function_type(NULL, NULL, NULL, loc);
 203   cmplx_type->set_is_varargs();
 204   cmplx_type->set_is_builtin();
 205   this->globals_->add_function_declaration("cmplx", NULL, cmplx_type, loc);
 206
 207   Function_type* real_type = Type::make_function_type(NULL, NULL, NULL, loc);
 208   real_type->set_is_varargs();
 209   real_type->set_is_builtin();
 210   this->globals_->add_function_declaration("real", NULL, real_type, loc);
 211
 212   Function_type* imag_type = Type::make_function_type(NULL, NULL, NULL, loc);
 213   imag_type->set_is_varargs();
 214   imag_type->set_is_builtin();
 215   this->globals_->add_function_declaration("imag", NULL, cmplx_type, loc);
 216
 217   this->define_builtin_function_trees();
 218
 219   // Declare "init", to ensure that it is not defined with parameters
 220   // or return values.
 221   this->declare_function("init",
 222                          Type::make_function_type(NULL, NULL, NULL, loc),
 223                          loc);
 224 }
 225
 226 // Munge name for use in an error message.
 227
 228 std::string
 229 Gogo::message_name(const std::string& name)
 230 {
 231   return go_localize_identifier(Gogo::unpack_hidden_name(name).c_str());
 232 }
 233
 234 // Get the package name.
 235
 236 const std::string&
 237 Gogo::package_name() const
 238 {
 239   gcc_assert(this->package_ != NULL);
 240   return this->package_->name();
 241 }
 242
 243 // Set the package name.
 244
 245 void
 246 Gogo::set_package_name(const std::string& package_name,
 247                        source_location location)
 248 {
 249   if (this->package_ != NULL && this->package_->name() != package_name)
 250     {
 251       error_at(location, "expected package %<%s%>",
 252                Gogo::message_name(this->package_->name()).c_str());
 253       return;
 254     }
 255
 256   // If the user did not specify a unique prefix, we always use "go".
 257   // This in effect requires that the package name be unique.
 258   if (this->unique_prefix_.empty())
 259     this->unique_prefix_ = "go";
 260
 261   this->package_ = this->register_package(package_name, this->unique_prefix_,
 262                                           location);
 263
 264   // We used to permit people to qualify symbols with the current
 265   // package name (e.g., P.x), but we no longer do.
 266   // this->globals_->add_package(package_name, this->package_);
 267
 268   if (package_name == "main")
 269     {
 270       // Declare "main" as a function which takes no parameters and
 271       // returns no value.
 272       this->declare_function("main",
 273                              Type::make_function_type(NULL, NULL, NULL,
 274                                                       BUILTINS_LOCATION),
 275                              BUILTINS_LOCATION);
 276     }
 277 }
 278
 279 // Import a package.
 280
 281 void
 282 Gogo::import_package(const std::string& filename,
 283                      const std::string& local_name,
 284                      bool is_local_name_exported,
 285                      source_location location)
 286 {
 287   if (filename == "unsafe")
 288     {
 289       this->import_unsafe(local_name, is_local_name_exported, location);
 290       return;
 291     }
 292
 293   Imports::const_iterator p = this->imports_.find(filename);
 294   if (p != this->imports_.end())
 295     {
 296       Package* package = p->second;
 297       package->set_location(location);
 298       package->set_is_imported();
 299       std::string ln = local_name;
 300       bool is_ln_exported = is_local_name_exported;
 301       if (ln.empty())
 302         {
 303           ln = package->name();
 304           is_ln_exported = Lex::is_exported_name(ln);
 305         }
 306       if (ln != ".")
 307         {
 308           ln = this->pack_hidden_name(ln, is_ln_exported);
 309           this->package_->bindings()->add_package(ln, package);
 310         }
 311       else
 312         {
 313           Bindings* bindings = package->bindings();
 314           for (Bindings::const_declarations_iterator p =
 315                  bindings->begin_declarations();
 316                p != bindings->end_declarations();
 317                ++p)
 318             this->add_named_object(p->second);
 319         }
 320       return;
 321     }
 322
 323   Import::Stream* stream = Import::open_package(filename, location);
 324   if (stream == NULL)
 325     {
 326       error_at(location, "import file %qs not found", filename.c_str());
 327       return;
 328     }
 329
 330   Import imp(stream, location);
 331   imp.register_builtin_types(this);
 332   Package* package = imp.import(this, local_name, is_local_name_exported);
 333   this->imports_.insert(std::make_pair(filename, package));
 334   package->set_is_imported();
 335
 336   delete stream;
 337 }
 338
 339 // Add an import control function for an imported package to the list.
 340
 341 void
 342 Gogo::add_import_init_fn(const std::string& package_name,
 343                          const std::string& init_name, int prio)
 344 {
 345   for (std::set<Import_init>::const_iterator p =
 346          this->imported_init_fns_.begin();
 347        p != this->imported_init_fns_.end();
 348        ++p)
 349     {
 350       if (p->init_name() == init_name
 351           && (p->package_name() != package_name || p->priority() != prio))
 352         {
 353           error("duplicate package initialization name %qs",
 354                 Gogo::message_name(init_name).c_str());
 355           inform(UNKNOWN_LOCATION, "used by package %qs at priority %d",
 356                  Gogo::message_name(p->package_name()).c_str(),
 357                  p->priority());
 358           inform(UNKNOWN_LOCATION, " and by package %qs at priority %d",
 359                  Gogo::message_name(package_name).c_str(), prio);
 360           return;
 361         }
 362     }
 363
 364   this->imported_init_fns_.insert(Import_init(package_name, init_name,
 365                                               prio));
 366 }
 367
 368 // Return whether we are at the global binding level.
 369
 370 bool
 371 Gogo::in_global_scope() const
 372 {
 373   return this->functions_.empty();
 374 }
 375
 376 // Return the current binding contour.
 377
 378 Bindings*
 379 Gogo::current_bindings()
 380 {
 381   if (!this->functions_.empty())
 382     return this->functions_.back().blocks.back()->bindings();
 383   else if (this->package_ != NULL)
 384     return this->package_->bindings();
 385   else
 386     return this->globals_;
 387 }
 388
 389 const Bindings*
 390 Gogo::current_bindings() const
 391 {
 392   if (!this->functions_.empty())
 393     return this->functions_.back().blocks.back()->bindings();
 394   else if (this->package_ != NULL)
 395     return this->package_->bindings();
 396   else
 397     return this->globals_;
 398 }
 399
 400 // Return the current block.
 401
 402 Block*
 403 Gogo::current_block()
 404 {
 405   if (this->functions_.empty())
 406     return NULL;
 407   else
 408     return this->functions_.back().blocks.back();
 409 }
 410
 411 // Look up a name in the current binding contour.  If PFUNCTION is not
 412 // NULL, set it to the function in which the name is defined, or NULL
 413 // if the name is defined in global scope.
 414
 415 Named_object*
 416 Gogo::lookup(const std::string& name, Named_object** pfunction) const
 417 {
 418   if (Gogo::is_sink_name(name))
 419     return Named_object::make_sink();
 420
 421   for (Open_functions::const_reverse_iterator p = this->functions_.rbegin();
 422        p != this->functions_.rend();
 423        ++p)
 424     {
 425       Named_object* ret = p->blocks.back()->bindings()->lookup(name);
 426       if (ret != NULL)
 427         {
 428           if (pfunction != NULL)
 429             *pfunction = p->function;
 430           return ret;
 431         }
 432     }
 433
 434   if (pfunction != NULL)
 435     *pfunction = NULL;
 436
 437   if (this->package_ != NULL)
 438     {
 439       Named_object* ret = this->package_->bindings()->lookup(name);
 440       if (ret != NULL)
 441         {
 442           if (ret->package() != NULL)
 443             ret->package()->set_used();
 444           return ret;
 445         }
 446     }
 447
 448   // We do not look in the global namespace.  If we did, the global
 449   // namespace would effectively hide names which were defined in
 450   // package scope which we have not yet seen.  Instead,
 451   // define_global_names is called after parsing is over to connect
 452   // undefined names at package scope with names defined at global
 453   // scope.
 454
 455   return NULL;
 456 }
 457
 458 // Look up a name in the current block, without searching enclosing
 459 // blocks.
 460
 461 Named_object*
 462 Gogo::lookup_in_block(const std::string& name) const
 463 {
 464   gcc_assert(!this->functions_.empty());
 465   gcc_assert(!this->functions_.back().blocks.empty());
 466   return this->functions_.back().blocks.back()->bindings()->lookup_local(name);
 467 }
 468
 469 // Look up a name in the global namespace.
 470
 471 Named_object*
 472 Gogo::lookup_global(const char* name) const
 473 {
 474   return this->globals_->lookup(name);
 475 }
 476
 477 // Add an imported package.
 478
 479 Package*
 480 Gogo::add_imported_package(const std::string& real_name,
 481                            const std::string& alias_arg,
 482                            bool is_alias_exported,
 483                            const std::string& unique_prefix,
 484                            source_location location,
 485                            bool* padd_to_globals)
 486 {
 487   // FIXME: Now that we compile packages as a whole, should we permit
 488   // importing the current package?
 489   if (this->package_name() == real_name
 490       && this->unique_prefix() == unique_prefix)
 491     {
 492       *padd_to_globals = false;
 493       if (!alias_arg.empty() && alias_arg != ".")
 494         {
 495           std::string alias = this->pack_hidden_name(alias_arg,
 496                                                      is_alias_exported);
 497           this->package_->bindings()->add_package(alias, this->package_);
 498         }
 499       return this->package_;
 500     }
 501   else if (alias_arg == ".")
 502     {
 503       *padd_to_globals = true;
 504       return this->register_package(real_name, unique_prefix, location);
 505     }
 506   else if (alias_arg == "_")
 507     {
 508       Package* ret = this->register_package(real_name, unique_prefix, location);
 509       ret->set_uses_sink_alias();
 510       return ret;
 511     }
 512   else
 513     {
 514       *padd_to_globals = false;
 515       std::string alias = alias_arg;
 516       if (alias.empty())
 517         {
 518           alias = real_name;
 519           is_alias_exported = Lex::is_exported_name(alias);
 520         }
 521       alias = this->pack_hidden_name(alias, is_alias_exported);
 522       Named_object* no = this->add_package(real_name, alias, unique_prefix,
 523                                            location);
 524       if (!no->is_package())
 525         return NULL;
 526       return no->package_value();
 527     }
 528 }
 529
 530 // Add a package.
 531
 532 Named_object*
 533 Gogo::add_package(const std::string& real_name, const std::string& alias,
 534                   const std::string& unique_prefix, source_location location)
 535 {
 536   gcc_assert(this->in_global_scope());
 537
 538   // Register the package.  Note that we might have already seen it in
 539   // an earlier import.
 540   Package* package = this->register_package(real_name, unique_prefix, location);
 541
 542   return this->package_->bindings()->add_package(alias, package);
 543 }
 544
 545 // Register a package.  This package may or may not be imported.  This
 546 // returns the Package structure for the package, creating if it
 547 // necessary.
 548
 549 Package*
 550 Gogo::register_package(const std::string& package_name,
 551                        const std::string& unique_prefix,
 552                        source_location location)
 553 {
 554   gcc_assert(!unique_prefix.empty() && !package_name.empty());
 555   std::string name = unique_prefix + '.' + package_name;
 556   Package* package = NULL;
 557   std::pair<Packages::iterator, bool> ins =
 558     this->packages_.insert(std::make_pair(name, package));
 559   if (!ins.second)
 560     {
 561       // We have seen this package name before.
 562       package = ins.first->second;
 563       gcc_assert(package != NULL);
 564       gcc_assert(package->name() == package_name
 565                  && package->unique_prefix() == unique_prefix);
 566       if (package->location() == UNKNOWN_LOCATION)
 567         package->set_location(location);
 568     }
 569   else
 570     {
 571       // First time we have seen this package name.
 572       package = new Package(package_name, unique_prefix, location);
 573       gcc_assert(ins.first->second == NULL);
 574       ins.first->second = package;
 575     }
 576
 577   return package;
 578 }
 579
 580 // Start compiling a function.
 581
 582 Named_object*
 583 Gogo::start_function(const std::string& name, Function_type* type,
 584                      bool add_method_to_type, source_location location)
 585 {
 586   bool at_top_level = this->functions_.empty();
 587
 588   Block* block = new Block(NULL, location);
 589
 590   Function* enclosing = (at_top_level
 591                          ? NULL
 592                          : this->functions_.back().function->func_value());
 593
 594   Function* function = new Function(type, enclosing, block, location);
 595
 596   if (type->is_method())
 597     {
 598       const Typed_identifier* receiver = type->receiver();
 599       Variable* this_param = new Variable(receiver->type(), NULL, false,
 600                                           true, true, location);
 601       std::string name = receiver->name();
 602       if (name.empty())
 603         {
 604           // We need to give receivers a name since they wind up in
 605           // DECL_ARGUMENTS.  FIXME.
 606           static unsigned int count;
 607           char buf[50];
 608           snprintf(buf, sizeof buf, "r.%u", count);
 609           ++count;
 610           name = buf;
 611         }
 612       block->bindings()->add_variable(name, NULL, this_param);
 613     }
 614
 615   const Typed_identifier_list* parameters = type->parameters();
 616   bool is_varargs = type->is_varargs();
 617   if (parameters != NULL)
 618     {
 619       for (Typed_identifier_list::const_iterator p = parameters->begin();
 620            p != parameters->end();
 621            ++p)
 622         {
 623           Variable* param = new Variable(p->type(), NULL, false, true, false,
 624                                          location);
 625           if (is_varargs && p + 1 == parameters->end())
 626             param->set_is_varargs_parameter();
 627
 628           std::string name = p->name();
 629           if (name.empty() || Gogo::is_sink_name(name))
 630             {
 631               // We need to give parameters a name since they wind up
 632               // in DECL_ARGUMENTS.  FIXME.
 633               static unsigned int count;
 634               char buf[50];
 635               snprintf(buf, sizeof buf, "p.%u", count);
 636               ++count;
 637               name = buf;
 638             }
 639           block->bindings()->add_variable(name, NULL, param);
 640         }
 641     }
 642
 643   function->create_named_result_variables();
 644
 645   const std::string* pname;
 646   std::string nested_name;
 647   if (!name.empty())
 648     pname = &name;
 649   else
 650     {
 651       // Invent a name for a nested function.
 652       static int nested_count;
 653       char buf[30];
 654       snprintf(buf, sizeof buf, ".$nested%d", nested_count);
 655       ++nested_count;
 656       nested_name = buf;
 657       pname = &nested_name;
 658     }
 659
 660   Named_object* ret;
 661   if (Gogo::is_sink_name(*pname))
 662     ret = Named_object::make_sink();
 663   else if (!type->is_method())
 664     {
 665       ret = this->package_->bindings()->add_function(*pname, NULL, function);
 666       if (!ret->is_function())
 667         {
 668           // Redefinition error.
 669           ret = Named_object::make_function(name, NULL, function);
 670         }
 671     }
 672   else
 673     {
 674       if (!add_method_to_type)
 675         ret = Named_object::make_function(name, NULL, function);
 676       else
 677         {
 678           gcc_assert(at_top_level);
 679           Type* rtype = type->receiver()->type();
 680
 681           // We want to look through the pointer created by the
 682           // parser, without getting an error if the type is not yet
 683           // defined.
 684           if (rtype->classification() == Type::TYPE_POINTER)
 685             rtype = rtype->points_to();
 686
 687           if (rtype->is_error_type())
 688             ret = Named_object::make_function(name, NULL, function);
 689           else if (rtype->named_type() != NULL)
 690             {
 691               ret = rtype->named_type()->add_method(name, function);
 692               if (!ret->is_function())
 693                 {
 694                   // Redefinition error.
 695                   ret = Named_object::make_function(name, NULL, function);
 696                 }
 697             }
 698           else if (rtype->forward_declaration_type() != NULL)
 699             {
 700               Named_object* type_no =
 701                 rtype->forward_declaration_type()->named_object();
 702               if (type_no->is_unknown())
 703                 {
 704                   // If we are seeing methods it really must be a
 705                   // type.  Declare it as such.  An alternative would
 706                   // be to support lists of methods for unknown
 707                   // expressions.  Either way the error messages if
 708                   // this is not a type are going to get confusing.
 709                   Named_object* declared =
 710                     this->declare_package_type(type_no->name(),
 711                                                type_no->location());
 712                   gcc_assert(declared
 713                              == type_no->unknown_value()->real_named_object());
 714                 }
 715               ret = rtype->forward_declaration_type()->add_method(name,
 716                                                                   function);
 717             }
 718           else
 719             gcc_unreachable();
 720         }
 721       this->package_->bindings()->add_method(ret);
 722     }
 723
 724   this->functions_.resize(this->functions_.size() + 1);
 725   Open_function& of(this->functions_.back());
 726   of.function = ret;
 727   of.blocks.push_back(block);
 728
 729   if (!type->is_method() && Gogo::unpack_hidden_name(name) == "init")
 730     {
 731       this->init_functions_.push_back(ret);
 732       this->need_init_fn_ = true;
 733     }
 734
 735   return ret;
 736 }
 737
 738 // Finish compiling a function.
 739
 740 void
 741 Gogo::finish_function(source_location location)
 742 {
 743   this->finish_block(location);
 744   gcc_assert(this->functions_.back().blocks.empty());
 745   this->functions_.pop_back();
 746 }
 747
 748 // Return the current function.
 749
 750 Named_object*
 751 Gogo::current_function() const
 752 {
 753   gcc_assert(!this->functions_.empty());
 754   return this->functions_.back().function;
 755 }
 756
 757 // Start a new block.
 758
 759 void
 760 Gogo::start_block(source_location location)
 761 {
 762   gcc_assert(!this->functions_.empty());
 763   Block* block = new Block(this->current_block(), location);
 764   this->functions_.back().blocks.push_back(block);
 765 }
 766
 767 // Finish a block.
 768
 769 Block*
 770 Gogo::finish_block(source_location location)
 771 {
 772   gcc_assert(!this->functions_.empty());
 773   gcc_assert(!this->functions_.back().blocks.empty());
 774   Block* block = this->functions_.back().blocks.back();
 775   this->functions_.back().blocks.pop_back();
 776   block->set_end_location(location);
 777   return block;
 778 }
 779
 780 // Add an unknown name.
 781
 782 Named_object*
 783 Gogo::add_unknown_name(const std::string& name, source_location location)
 784 {
 785   return this->package_->bindings()->add_unknown_name(name, location);
 786 }
 787
 788 // Declare a function.
 789
 790 Named_object*
 791 Gogo::declare_function(const std::string& name, Function_type* type,
 792                        source_location location)
 793 {
 794   if (!type->is_method())
 795     return this->current_bindings()->add_function_declaration(name, NULL, type,
 796                                                               location);
 797   else
 798     {
 799       // We don't bother to add this to the list of global
 800       // declarations.
 801       Type* rtype = type->receiver()->type();
 802
 803       // We want to look through the pointer created by the
 804       // parser, without getting an error if the type is not yet
 805       // defined.
 806       if (rtype->classification() == Type::TYPE_POINTER)
 807         rtype = rtype->points_to();
 808
 809       if (rtype->is_error_type())
 810         return NULL;
 811       else if (rtype->named_type() != NULL)
 812         return rtype->named_type()->add_method_declaration(name, NULL, type,
 813                                                            location);
 814       else if (rtype->forward_declaration_type() != NULL)
 815         {
 816           Forward_declaration_type* ftype = rtype->forward_declaration_type();
 817           return ftype->add_method_declaration(name, type, location);
 818         }
 819       else
 820         gcc_unreachable();
 821     }
 822 }
 823
 824 // Add a label definition.
 825
 826 Label*
 827 Gogo::add_label_definition(const std::string& label_name,
 828                            source_location location)
 829 {
 830   gcc_assert(!this->functions_.empty());
 831   Function* func = this->functions_.back().function->func_value();
 832   Label* label = func->add_label_definition(label_name, location);
 833   this->add_statement(Statement::make_label_statement(label, location));
 834   return label;
 835 }
 836
 837 // Add a label reference.
 838
 839 Label*
 840 Gogo::add_label_reference(const std::string& label_name)
 841 {
 842   gcc_assert(!this->functions_.empty());
 843   Function* func = this->functions_.back().function->func_value();
 844   return func->add_label_reference(label_name);
 845 }
 846
 847 // Add a statement.
 848
 849 void
 850 Gogo::add_statement(Statement* statement)
 851 {
 852   gcc_assert(!this->functions_.empty()
 853              && !this->functions_.back().blocks.empty());
 854   this->functions_.back().blocks.back()->add_statement(statement);
 855 }
 856
 857 // Add a block.
 858
 859 void
 860 Gogo::add_block(Block* block, source_location location)
 861 {
 862   gcc_assert(!this->functions_.empty()
 863              && !this->functions_.back().blocks.empty());
 864   Statement* statement = Statement::make_block_statement(block, location);
 865   this->functions_.back().blocks.back()->add_statement(statement);
 866 }
 867
 868 // Add a constant.
 869
 870 Named_object*
 871 Gogo::add_constant(const Typed_identifier& tid, Expression* expr,
 872                    int iota_value)
 873 {
 874   return this->current_bindings()->add_constant(tid, NULL, expr, iota_value);
 875 }
 876
 877 // Add a type.
 878
 879 void
 880 Gogo::add_type(const std::string& name, Type* type, source_location location)
 881 {
 882   Named_object* no = this->current_bindings()->add_type(name, NULL, type,
 883                                                         location);
 884   if (!this->in_global_scope())
 885     no->type_value()->set_in_function(this->functions_.back().function);
 886 }
 887
 888 // Add a named type.
 889
 890 void
 891 Gogo::add_named_type(Named_type* type)
 892 {
 893   gcc_assert(this->in_global_scope());
 894   this->current_bindings()->add_named_type(type);
 895 }
 896
 897 // Declare a type.
 898
 899 Named_object*
 900 Gogo::declare_type(const std::string& name, source_location location)
 901 {
 902   Bindings* bindings = this->current_bindings();
 903   Named_object* no = bindings->add_type_declaration(name, NULL, location);
 904   if (!this->in_global_scope())
 905     {
 906       Named_object* f = this->functions_.back().function;
 907       no->type_declaration_value()->set_in_function(f);
 908     }
 909   return no;
 910 }
 911
 912 // Declare a type at the package level.
 913
 914 Named_object*
 915 Gogo::declare_package_type(const std::string& name, source_location location)
 916 {
 917   return this->package_->bindings()->add_type_declaration(name, NULL, location);
 918 }
 919
 920 // Define a type which was already declared.
 921
 922 void
 923 Gogo::define_type(Named_object* no, Named_type* type)
 924 {
 925   this->current_bindings()->define_type(no, type);
 926 }
 927
 928 // Add a variable.
 929
 930 Named_object*
 931 Gogo::add_variable(const std::string& name, Variable* variable)
 932 {
 933   Named_object* no = this->current_bindings()->add_variable(name, NULL,
 934                                                             variable);
 935
 936   // In a function the middle-end wants to see a DECL_EXPR node.
 937   if (no != NULL
 938       && no->is_variable()
 939       && !no->var_value()->is_parameter()
 940       && !this->functions_.empty())
 941     this->add_statement(Statement::make_variable_declaration(no));
 942
 943   return no;
 944 }
 945
 946 // Add a sink--a reference to the blank identifier _.
 947
 948 Named_object*
 949 Gogo::add_sink()
 950 {
 951   return Named_object::make_sink();
 952 }
 953
 954 // Add a named object.
 955
 956 void
 957 Gogo::add_named_object(Named_object* no)
 958 {
 959   this->current_bindings()->add_named_object(no);
 960 }
 961
 962 // Record that we've seen an interface type.
 963
 964 void
 965 Gogo::record_interface_type(Interface_type* itype)
 966 {
 967   this->interface_types_.push_back(itype);
 968 }
 969
 970 // Return a name for a thunk object.
 971
 972 std::string
 973 Gogo::thunk_name()
 974 {
 975   static int thunk_count;
 976   char thunk_name[50];
 977   snprintf(thunk_name, sizeof thunk_name, "$thunk%d", thunk_count);
 978   ++thunk_count;
 979   return thunk_name;
 980 }
 981
 982 // Return whether a function is a thunk.
 983
 984 bool
 985 Gogo::is_thunk(const Named_object* no)
 986 {
 987   return no->name().compare(0, 6, "$thunk") == 0;
 988 }
 989
 990 // Define the global names.  We do this only after parsing all the
 991 // input files, because the program might define the global names
 992 // itself.
 993
 994 void
 995 Gogo::define_global_names()
 996 {
 997   for (Bindings::const_declarations_iterator p =
 998          this->globals_->begin_declarations();
 999        p != this->globals_->end_declarations();
1000        ++p)
1001     {
1002       Named_object* global_no = p->second;
1003       std::string name(Gogo::pack_hidden_name(global_no->name(), false));
1004       Named_object* no = this->package_->bindings()->lookup(name);
1005       if (no == NULL)
1006         continue;
1007       no = no->resolve();
1008       if (no->is_type_declaration())
1009         {
1010           if (global_no->is_type())
1011             {
1012               if (no->type_declaration_value()->has_methods())
1013                 error_at(no->location(),
1014                          "may not define methods for global type");
1015               no->set_type_value(global_no->type_value());
1016             }
1017           else
1018             {
1019               error_at(no->location(), "expected type");
1020               Type* errtype = Type::make_error_type();
1021               Named_object* err = Named_object::make_type("error", NULL,
1022                                                           errtype,
1023                                                           BUILTINS_LOCATION);
1024               no->set_type_value(err->type_value());
1025             }
1026         }
1027       else if (no->is_unknown())
1028         no->unknown_value()->set_real_named_object(global_no);
1029     }
1030 }
1031
1032 // Clear out names in file scope.
1033
1034 void
1035 Gogo::clear_file_scope()
1036 {
1037   this->package_->bindings()->clear_file_scope();
1038
1039   // Warn about packages which were imported but not used.
1040   for (Packages::iterator p = this->packages_.begin();
1041        p != this->packages_.end();
1042        ++p)
1043     {
1044       Package* package = p->second;
1045       if (package != this->package_
1046           && package->is_imported()
1047           && !package->used()
1048           && !package->uses_sink_alias()
1049           && !saw_errors())
1050         error_at(package->location(), "imported and not used: %s",
1051                  Gogo::message_name(package->name()).c_str());
1052       package->clear_is_imported();
1053       package->clear_uses_sink_alias();
1054       package->clear_used();
1055     }
1056 }
1057
1058 // Traverse the tree.
1059
1060 void
1061 Gogo::traverse(Traverse* traverse)
1062 {
1063   // Traverse the current package first for consistency.  The other
1064   // packages will only contain imported types, constants, and
1065   // declarations.
1066   if (this->package_->bindings()->traverse(traverse, true) == TRAVERSE_EXIT)
1067     return;
1068   for (Packages::const_iterator p = this->packages_.begin();
1069        p != this->packages_.end();
1070        ++p)
1071     {
1072       if (p->second != this->package_)
1073         {
1074           if (p->second->bindings()->traverse(traverse, true) == TRAVERSE_EXIT)
1075             break;
1076         }
1077     }
1078 }
1079
1080 // Traversal class used to verify types.
1081
1082 class Verify_types : public Traverse
1083 {
1084  public:
1085   Verify_types()
1086     : Traverse(traverse_types)
1087   { }
1088
1089   int
1090   type(Type*);
1091 };
1092
1093 // Verify that a type is correct.
1094
1095 int
1096 Verify_types::type(Type* t)
1097 {
1098   // Don't verify types defined in other packages.
1099   Named_type* nt = t->named_type();
1100   if (nt != NULL && nt->named_object()->package() != NULL)
1101     return TRAVERSE_SKIP_COMPONENTS;
1102
1103   if (!t->verify())
1104     return TRAVERSE_SKIP_COMPONENTS;
1105   return TRAVERSE_CONTINUE;
1106 }
1107
1108 // Verify that all types are correct.
1109
1110 void
1111 Gogo::verify_types()
1112 {
1113   Verify_types traverse;
1114   this->traverse(&traverse);
1115 }
1116
1117 // Traversal class used to lower parse tree.
1118
1119 class Lower_parse_tree : public Traverse
1120 {
1121  public:
1122   Lower_parse_tree(Gogo* gogo, Named_object* function)
1123     : Traverse(traverse_constants
1124                | traverse_functions
1125                | traverse_statements
1126                | traverse_expressions),
1127       gogo_(gogo), function_(function), iota_value_(-1)
1128   { }
1129
1130   int
1131   constant(Named_object*, bool);
1132
1133   int
1134   function(Named_object*);
1135
1136   int
1137   statement(Block*, size_t* pindex, Statement*);
1138
1139   int
1140   expression(Expression**);
1141
1142  private:
1143   // General IR.
1144   Gogo* gogo_;
1145   // The function we are traversing.
1146   Named_object* function_;
1147   // Value to use for the predeclared constant iota.
1148   int iota_value_;
1149 };
1150
1151 // Lower constants.  We handle constants specially so that we can set
1152 // the right value for the predeclared constant iota.  This works in
1153 // conjunction with the way we lower Const_expression objects.
1154
1155 int
1156 Lower_parse_tree::constant(Named_object* no, bool)
1157 {
1158   Named_constant* nc = no->const_value();
1159
1160   // We can recursively a constant if the initializer expression
1161   // manages to refer to itself.
1162   if (nc->lowering())
1163     return TRAVERSE_CONTINUE;
1164   nc->set_lowering();
1165
1166   gcc_assert(this->iota_value_ == -1);
1167   this->iota_value_ = nc->iota_value();
1168   nc->traverse_expression(this);
1169   this->iota_value_ = -1;
1170
1171   nc->clear_lowering();
1172
1173   // We will traverse the expression a second time, but that will be
1174   // fast.
1175
1176   return TRAVERSE_CONTINUE;
1177 }
1178
1179 // Lower function closure types.  Record the function while lowering
1180 // it, so that we can pass it down when lowering an expression.
1181
1182 int
1183 Lower_parse_tree::function(Named_object* no)
1184 {
1185   no->func_value()->set_closure_type();
1186
1187   gcc_assert(this->function_ == NULL);
1188   this->function_ = no;
1189   int t = no->func_value()->traverse(this);
1190   this->function_ = NULL;
1191
1192   if (t == TRAVERSE_EXIT)
1193     return t;
1194   return TRAVERSE_SKIP_COMPONENTS;
1195 }
1196
1197 // Lower statement parse trees.
1198
1199 int
1200 Lower_parse_tree::statement(Block* block, size_t* pindex, Statement* sorig)
1201 {
1202   // Lower the expressions first.
1203   int t = sorig->traverse_contents(this);
1204   if (t == TRAVERSE_EXIT)
1205     return t;
1206
1207   // Keep lowering until nothing changes.
1208   Statement* s = sorig;
1209   while (true)
1210     {
1211       Statement* snew = s->lower(this->gogo_, block);
1212       if (snew == s)
1213         break;
1214       s = snew;
1215       t = s->traverse_contents(this);
1216       if (t == TRAVERSE_EXIT)
1217         return t;
1218     }
1219
1220   if (s != sorig)
1221     block->replace_statement(*pindex, s);
1222
1223   return TRAVERSE_SKIP_COMPONENTS;
1224 }
1225
1226 // Lower expression parse trees.
1227
1228 int
1229 Lower_parse_tree::expression(Expression** pexpr)
1230 {
1231   // We have to lower all subexpressions first, so that we can get
1232   // their type if necessary.  This is awkward, because we don't have
1233   // a postorder traversal pass.
1234   if ((*pexpr)->traverse_subexpressions(this) == TRAVERSE_EXIT)
1235     return TRAVERSE_EXIT;
1236   // Keep lowering until nothing changes.
1237   while (true)
1238     {
1239       Expression* e = *pexpr;
1240       Expression* enew = e->lower(this->gogo_, this->function_,
1241                                   this->iota_value_);
1242       if (enew == e)
1243         break;
1244       *pexpr = enew;
1245     }
1246   return TRAVERSE_SKIP_COMPONENTS;
1247 }
1248
1249 // Lower the parse tree.  This is called after the parse is complete,
1250 // when all names should be resolved.
1251
1252 void
1253 Gogo::lower_parse_tree()
1254 {
1255   Lower_parse_tree lower_parse_tree(this, NULL);
1256   this->traverse(&lower_parse_tree);
1257 }
1258
1259 // Lower an expression.
1260
1261 void
1262 Gogo::lower_expression(Named_object* function, Expression** pexpr)
1263 {
1264   Lower_parse_tree lower_parse_tree(this, function);
1265   lower_parse_tree.expression(pexpr);
1266 }
1267
1268 // Lower a constant.  This is called when lowering a reference to a
1269 // constant.  We have to make sure that the constant has already been
1270 // lowered.
1271
1272 void
1273 Gogo::lower_constant(Named_object* no)
1274 {
1275   gcc_assert(no->is_const());
1276   Lower_parse_tree lower(this, NULL);
1277   lower.constant(no, false);
1278 }
1279
1280 // Look for interface types to finalize methods of inherited
1281 // interfaces.
1282
1283 class Finalize_methods : public Traverse
1284 {
1285  public:
1286   Finalize_methods(Gogo* gogo)
1287     : Traverse(traverse_types),
1288       gogo_(gogo)
1289   { }
1290
1291   int
1292   type(Type*);
1293
1294  private:
1295   Gogo* gogo_;
1296 };
1297
1298 // Finalize the methods of an interface type.
1299
1300 int
1301 Finalize_methods::type(Type* t)
1302 {
1303   // Check the classification so that we don't finalize the methods
1304   // twice for a named interface type.
1305   switch (t->classification())
1306     {
1307     case Type::TYPE_INTERFACE:
1308       t->interface_type()->finalize_methods();
1309       break;
1310
1311     case Type::TYPE_NAMED:
1312       {
1313         // We have to finalize the methods of the real type first.
1314         // But if the real type is a struct type, then we only want to
1315         // finalize the methods of the field types, not of the struct
1316         // type itself.  We don't want to add methods to the struct,
1317         // since it has a name.
1318         Type* rt = t->named_type()->real_type();
1319         if (rt->classification() != Type::TYPE_STRUCT)
1320           {
1321             if (Type::traverse(rt, this) == TRAVERSE_EXIT)
1322               return TRAVERSE_EXIT;
1323           }
1324         else
1325           {
1326             if (rt->struct_type()->traverse_field_types(this) == TRAVERSE_EXIT)
1327               return TRAVERSE_EXIT;
1328           }
1329
1330         t->named_type()->finalize_methods(this->gogo_);
1331
1332         return TRAVERSE_SKIP_COMPONENTS;
1333       }
1334
1335     case Type::TYPE_STRUCT:
1336       t->struct_type()->finalize_methods(this->gogo_);
1337       break;
1338
1339     default:
1340       break;
1341     }
1342
1343   return TRAVERSE_CONTINUE;
1344 }
1345
1346 // Finalize method lists and build stub methods for types.
1347
1348 void
1349 Gogo::finalize_methods()
1350 {
1351   Finalize_methods finalize(this);
1352   this->traverse(&finalize);
1353 }
1354
1355 // Set types for unspecified variables and constants.
1356
1357 void
1358 Gogo::determine_types()
1359 {
1360   Bindings* bindings = this->current_bindings();
1361   for (Bindings::const_definitions_iterator p = bindings->begin_definitions();
1362        p != bindings->end_definitions();
1363        ++p)
1364     {
1365       if ((*p)->is_function())
1366         (*p)->func_value()->determine_types();
1367       else if ((*p)->is_variable())
1368         (*p)->var_value()->determine_type();
1369       else if ((*p)->is_const())
1370         (*p)->const_value()->determine_type();
1371
1372       // See if a variable requires us to build an initialization
1373       // function.  We know that we will see all global variables
1374       // here.
1375       if (!this->need_init_fn_ && (*p)->is_variable())
1376         {
1377           Variable* variable = (*p)->var_value();
1378
1379           // If this is a global variable which requires runtime
1380           // initialization, we need an initialization function.
1381           if (!variable->is_global() || variable->init() == NULL)
1382             ;
1383           else if (variable->type()->interface_type() != NULL)
1384             this->need_init_fn_ = true;
1385           else if (variable->init()->is_constant())
1386             ;
1387           else if (!variable->init()->is_composite_literal())
1388             this->need_init_fn_ = true;
1389           else if (variable->init()->is_nonconstant_composite_literal())
1390             this->need_init_fn_ = true;
1391
1392           // If this is a global variable which holds a pointer value,
1393           // then we need an initialization function to register it as a
1394           // GC root.
1395           if (variable->is_global() && variable->type()->has_pointer())
1396             this->need_init_fn_ = true;
1397         }
1398     }
1399
1400   // Determine the types of constants in packages.
1401   for (Packages::const_iterator p = this->packages_.begin();
1402        p != this->packages_.end();
1403        ++p)
1404     p->second->determine_types();
1405 }
1406
1407 // Traversal class used for type checking.
1408
1409 class Check_types_traverse : public Traverse
1410 {
1411  public:
1412   Check_types_traverse(Gogo* gogo)
1413     : Traverse(traverse_variables
1414                | traverse_constants
1415                | traverse_statements
1416                | traverse_expressions),
1417       gogo_(gogo)
1418   { }
1419
1420   int
1421   variable(Named_object*);
1422
1423   int
1424   constant(Named_object*, bool);
1425
1426   int
1427   statement(Block*, size_t* pindex, Statement*);
1428
1429   int
1430   expression(Expression**);
1431
1432  private:
1433   // General IR.
1434   Gogo* gogo_;
1435 };
1436
1437 // Check that a variable initializer has the right type.
1438
1439 int
1440 Check_types_traverse::variable(Named_object* named_object)
1441 {
1442   if (named_object->is_variable())
1443     {
1444       Variable* var = named_object->var_value();
1445       Expression* init = var->init();
1446       std::string reason;
1447       if (init != NULL
1448           && !Type::are_assignable(var->type(), init->type(), &reason))
1449         {
1450           if (reason.empty())
1451             error_at(var->location(), "incompatible type in initialization");
1452           else
1453             error_at(var->location(),
1454                      "incompatible type in initialization (%s)",
1455                      reason.c_str());
1456           var->clear_init();
1457         }
1458     }
1459   return TRAVERSE_CONTINUE;
1460 }
1461
1462 // Check that a constant initializer has the right type.
1463
1464 int
1465 Check_types_traverse::constant(Named_object* named_object, bool)
1466 {
1467   Named_constant* constant = named_object->const_value();
1468   Type* ctype = constant->type();
1469   if (ctype->integer_type() == NULL
1470       && ctype->float_type() == NULL
1471       && ctype->complex_type() == NULL
1472       && !ctype->is_boolean_type()
1473       && !ctype->is_string_type())
1474     {
1475       error_at(constant->location(), "invalid constant type");
1476       constant->set_error();
1477     }
1478   else if (!constant->expr()->is_constant())
1479     {
1480       error_at(constant->expr()->location(), "expression is not constant");
1481       constant->set_error();
1482     }
1483   else if (!Type::are_assignable(constant->type(), constant->expr()->type(),
1484                                  NULL))
1485     {
1486       error_at(constant->location(),
1487                "initialization expression has wrong type");
1488       constant->set_error();
1489     }
1490   return TRAVERSE_CONTINUE;
1491 }
1492
1493 // Check that types are valid in a statement.
1494
1495 int
1496 Check_types_traverse::statement(Block*, size_t*, Statement* s)
1497 {
1498   s->check_types(this->gogo_);
1499   return TRAVERSE_CONTINUE;
1500 }
1501
1502 // Check that types are valid in an expression.
1503
1504 int
1505 Check_types_traverse::expression(Expression** expr)
1506 {
1507   (*expr)->check_types(this->gogo_);
1508   return TRAVERSE_CONTINUE;
1509 }
1510
1511 // Check that types are valid.
1512
1513 void
1514 Gogo::check_types()
1515 {
1516   Check_types_traverse traverse(this);
1517   this->traverse(&traverse);
1518 }
1519
1520 // Check the types in a single block.
1521
1522 void
1523 Gogo::check_types_in_block(Block* block)
1524 {
1525   Check_types_traverse traverse(this);
1526   block->traverse(&traverse);
1527 }
1528
1529 // A traversal class used to find a single shortcut operator within an
1530 // expression.
1531
1532 class Find_shortcut : public Traverse
1533 {
1534  public:
1535   Find_shortcut()
1536     : Traverse(traverse_blocks
1537                | traverse_statements
1538                | traverse_expressions),
1539       found_(NULL)
1540   { }
1541
1542   // A pointer to the expression which was found, or NULL if none was
1543   // found.
1544   Expression**
1545   found() const
1546   { return this->found_; }
1547
1548  protected:
1549   int
1550   block(Block*)
1551   { return TRAVERSE_SKIP_COMPONENTS; }
1552
1553   int
1554   statement(Block*, size_t*, Statement*)
1555   { return TRAVERSE_SKIP_COMPONENTS; }
1556
1557   int
1558   expression(Expression**);
1559
1560  private:
1561   Expression** found_;
1562 };
1563
1564 // Find a shortcut expression.
1565
1566 int
1567 Find_shortcut::expression(Expression** pexpr)
1568 {
1569   Expression* expr = *pexpr;
1570   Binary_expression* be = expr->binary_expression();
1571   if (be == NULL)
1572     return TRAVERSE_CONTINUE;
1573   Operator op = be->op();
1574   if (op != OPERATOR_OROR && op != OPERATOR_ANDAND)
1575     return TRAVERSE_CONTINUE;
1576   gcc_assert(this->found_ == NULL);
1577   this->found_ = pexpr;
1578   return TRAVERSE_EXIT;
1579 }
1580
1581 // A traversal class used to turn shortcut operators into explicit if
1582 // statements.
1583
1584 class Shortcuts : public Traverse
1585 {
1586  public:
1587   Shortcuts()
1588     : Traverse(traverse_variables
1589                | traverse_statements)
1590   { }
1591
1592  protected:
1593   int
1594   variable(Named_object*);
1595
1596   int
1597   statement(Block*, size_t*, Statement*);
1598
1599  private:
1600   // Convert a shortcut operator.
1601   Statement*
1602   convert_shortcut(Block* enclosing, Expression** pshortcut);
1603 };
1604
1605 // Remove shortcut operators in a single statement.
1606
1607 int
1608 Shortcuts::statement(Block* block, size_t* pindex, Statement* s)
1609 {
1610   // FIXME: This approach doesn't work for switch statements, because
1611   // we add the new statements before the whole switch when we need to
1612   // instead add them just before the switch expression.  The right
1613   // fix is probably to lower switch statements with nonconstant cases
1614   // to a series of conditionals.
1615   if (s->switch_statement() != NULL)
1616     return TRAVERSE_CONTINUE;
1617
1618   while (true)
1619     {
1620       Find_shortcut find_shortcut;
1621
1622       // If S is a variable declaration, then ordinary traversal won't
1623       // do anything.  We want to explicitly traverse the
1624       // initialization expression if there is one.
1625       Variable_declaration_statement* vds = s->variable_declaration_statement();
1626       Expression* init = NULL;
1627       if (vds == NULL)
1628         s->traverse_contents(&find_shortcut);
1629       else
1630         {
1631           init = vds->var()->var_value()->init();
1632           if (init == NULL)
1633             return TRAVERSE_CONTINUE;
1634           init->traverse(&init, &find_shortcut);
1635         }
1636       Expression** pshortcut = find_shortcut.found();
1637       if (pshortcut == NULL)
1638         return TRAVERSE_CONTINUE;
1639
1640       Statement* snew = this->convert_shortcut(block, pshortcut);
1641       block->insert_statement_before(*pindex, snew);
1642       ++*pindex;
1643
1644       if (pshortcut == &init)
1645         vds->var()->var_value()->set_init(init);
1646     }
1647 }
1648
1649 // Remove shortcut operators in the initializer of a global variable.
1650
1651 int
1652 Shortcuts::variable(Named_object* no)
1653 {
1654   if (no->is_result_variable())
1655     return TRAVERSE_CONTINUE;
1656   Variable* var = no->var_value();
1657   Expression* init = var->init();
1658   if (!var->is_global() || init == NULL)
1659     return TRAVERSE_CONTINUE;
1660
1661   while (true)
1662     {
1663       Find_shortcut find_shortcut;
1664       init->traverse(&init, &find_shortcut);
1665       Expression** pshortcut = find_shortcut.found();
1666       if (pshortcut == NULL)
1667         return TRAVERSE_CONTINUE;
1668
1669       Statement* snew = this->convert_shortcut(NULL, pshortcut);
1670       var->add_preinit_statement(snew);
1671       if (pshortcut == &init)
1672         var->set_init(init);
1673     }
1674 }
1675
1676 // Given an expression which uses a shortcut operator, return a
1677 // statement which implements it, and update *PSHORTCUT accordingly.
1678
1679 Statement*
1680 Shortcuts::convert_shortcut(Block* enclosing, Expression** pshortcut)
1681 {
1682   Binary_expression* shortcut = (*pshortcut)->binary_expression();
1683   Expression* left = shortcut->left();
1684   Expression* right = shortcut->right();
1685   source_location loc = shortcut->location();
1686
1687   Block* retblock = new Block(enclosing, loc);
1688   retblock->set_end_location(loc);
1689
1690   Temporary_statement* ts = Statement::make_temporary(Type::make_boolean_type(),
1691                                                       left, loc);
1692   retblock->add_statement(ts);
1693
1694   Block* block = new Block(retblock, loc);
1695   block->set_end_location(loc);
1696   Expression* tmpref = Expression::make_temporary_reference(ts, loc);
1697   Statement* assign = Statement::make_assignment(tmpref, right, loc);
1698   block->add_statement(assign);
1699
1700   Expression* cond = Expression::make_temporary_reference(ts, loc);
1701   if (shortcut->binary_expression()->op() == OPERATOR_OROR)
1702     cond = Expression::make_unary(OPERATOR_NOT, cond, loc);
1703
1704   Statement* if_statement = Statement::make_if_statement(cond, block, NULL,
1705                                                          loc);
1706   retblock->add_statement(if_statement);
1707
1708   *pshortcut = Expression::make_temporary_reference(ts, loc);
1709
1710   delete shortcut;
1711
1712   // Now convert any shortcut operators in LEFT and RIGHT.
1713   Shortcuts shortcuts;
1714   retblock->traverse(&shortcuts);
1715
1716   return Statement::make_block_statement(retblock, loc);
1717 }
1718
1719 // Turn shortcut operators into explicit if statements.  Doing this
1720 // considerably simplifies the order of evaluation rules.
1721
1722 void
1723 Gogo::remove_shortcuts()
1724 {
1725   Shortcuts shortcuts;
1726   this->traverse(&shortcuts);
1727 }
1728
1729 // A traversal class which finds all the expressions which must be
1730 // evaluated in order within a statement or larger expression.  This
1731 // is used to implement the rules about order of evaluation.
1732
1733 class Find_eval_ordering : public Traverse
1734 {
1735  private:
1736   typedef std::vector<Expression**> Expression_pointers;
1737
1738  public:
1739   Find_eval_ordering()
1740     : Traverse(traverse_blocks
1741                | traverse_statements
1742                | traverse_expressions),
1743       exprs_()
1744   { }
1745
1746   size_t
1747   size() const
1748   { return this->exprs_.size(); }
1749
1750   typedef Expression_pointers::const_iterator const_iterator;
1751
1752   const_iterator
1753   begin() const
1754   { return this->exprs_.begin(); }
1755
1756   const_iterator
1757   end() const
1758   { return this->exprs_.end(); }
1759
1760  protected:
1761   int
1762   block(Block*)
1763   { return TRAVERSE_SKIP_COMPONENTS; }
1764
1765   int
1766   statement(Block*, size_t*, Statement*)
1767   { return TRAVERSE_SKIP_COMPONENTS; }
1768
1769   int
1770   expression(Expression**);
1771
1772  private:
1773   // A list of pointers to expressions with side-effects.
1774   Expression_pointers exprs_;
1775 };
1776
1777 // If an expression must be evaluated in order, put it on the list.
1778
1779 int
1780 Find_eval_ordering::expression(Expression** expression_pointer)
1781 {
1782   // We have to look at subexpressions before this one.
1783   if ((*expression_pointer)->traverse_subexpressions(this) == TRAVERSE_EXIT)
1784     return TRAVERSE_EXIT;
1785   if ((*expression_pointer)->must_eval_in_order())
1786     this->exprs_.push_back(expression_pointer);
1787   return TRAVERSE_SKIP_COMPONENTS;
1788 }
1789
1790 // A traversal class for ordering evaluations.
1791
1792 class Order_eval : public Traverse
1793 {
1794  public:
1795   Order_eval()
1796     : Traverse(traverse_variables
1797                | traverse_statements)
1798   { }
1799
1800   int
1801   variable(Named_object*);
1802
1803   int
1804   statement(Block*, size_t*, Statement*);
1805 };
1806
1807 // Implement the order of evaluation rules for a statement.
1808
1809 int
1810 Order_eval::statement(Block* block, size_t* pindex, Statement* s)
1811 {
1812   // FIXME: This approach doesn't work for switch statements, because
1813   // we add the new statements before the whole switch when we need to
1814   // instead add them just before the switch expression.  The right
1815   // fix is probably to lower switch statements with nonconstant cases
1816   // to a series of conditionals.
1817   if (s->switch_statement() != NULL)
1818     return TRAVERSE_CONTINUE;
1819
1820   Find_eval_ordering find_eval_ordering;
1821
1822   // If S is a variable declaration, then ordinary traversal won't do
1823   // anything.  We want to explicitly traverse the initialization
1824   // expression if there is one.
1825   Variable_declaration_statement* vds = s->variable_declaration_statement();
1826   Expression* init = NULL;
1827   Expression* orig_init = NULL;
1828   if (vds == NULL)
1829     s->traverse_contents(&find_eval_ordering);
1830   else
1831     {
1832       init = vds->var()->var_value()->init();
1833       if (init == NULL)
1834         return TRAVERSE_CONTINUE;
1835       orig_init = init;
1836
1837       // It might seem that this could be
1838       // init->traverse_subexpressions.  Unfortunately that can fail
1839       // in a case like
1840       //   var err os.Error
1841       //   newvar, err := call(arg())
1842       // Here newvar will have an init of call result 0 of
1843       // call(arg()).  If we only traverse subexpressions, we will
1844       // only find arg(), and we won't bother to move anything out.
1845       // Then we get to the assignment to err, we will traverse the
1846       // whole statement, and this time we will find both call() and
1847       // arg(), and so we will move them out.  This will cause them to
1848       // be put into temporary variables before the assignment to err
1849       // but after the declaration of newvar.  To avoid that problem,
1850       // we traverse the entire expression here.
1851       Expression::traverse(&init, &find_eval_ordering);
1852     }
1853
1854   if (find_eval_ordering.size() <= 1)
1855     {
1856       // If there is only one expression with a side-effect, we can
1857       // leave it in place.
1858       return TRAVERSE_CONTINUE;
1859     }
1860
1861   bool is_thunk = s->thunk_statement() != NULL;
1862   for (Find_eval_ordering::const_iterator p = find_eval_ordering.begin();
1863        p != find_eval_ordering.end();
1864        ++p)
1865     {
1866       Expression** pexpr = *p;
1867
1868       // If the last expression is a send or receive expression, we
1869       // may be ignoring the value; we don't want to evaluate it
1870       // early.
1871       if (p + 1 == find_eval_ordering.end()
1872           && ((*pexpr)->classification() == Expression::EXPRESSION_SEND
1873               || (*pexpr)->classification() == Expression::EXPRESSION_RECEIVE))
1874         break;
1875
1876       // The last expression in a thunk will be the call passed to go
1877       // or defer, which we must not evaluate early.
1878       if (is_thunk && p + 1 == find_eval_ordering.end())
1879         break;
1880
1881       source_location loc = (*pexpr)->location();
1882       Temporary_statement* ts = Statement::make_temporary(NULL, *pexpr, loc);
1883       block->insert_statement_before(*pindex, ts);
1884       ++*pindex;
1885
1886       *pexpr = Expression::make_temporary_reference(ts, loc);
1887     }
1888
1889   if (init != orig_init)
1890     vds->var()->var_value()->set_init(init);
1891
1892   return TRAVERSE_CONTINUE;
1893 }
1894
1895 // Implement the order of evaluation rules for the initializer of a
1896 // global variable.
1897
1898 int
1899 Order_eval::variable(Named_object* no)
1900 {
1901   if (no->is_result_variable())
1902     return TRAVERSE_CONTINUE;
1903   Variable* var = no->var_value();
1904   Expression* init = var->init();
1905   if (!var->is_global() || init == NULL)
1906     return TRAVERSE_CONTINUE;
1907
1908   Find_eval_ordering find_eval_ordering;
1909   init->traverse_subexpressions(&find_eval_ordering);
1910
1911   if (find_eval_ordering.size() <= 1)
1912     {
1913       // If there is only one expression with a side-effect, we can
1914       // leave it in place.
1915       return TRAVERSE_SKIP_COMPONENTS;
1916     }
1917
1918   for (Find_eval_ordering::const_iterator p = find_eval_ordering.begin();
1919        p != find_eval_ordering.end();
1920        ++p)
1921     {
1922       Expression** pexpr = *p;
1923       source_location loc = (*pexpr)->location();
1924       Temporary_statement* ts = Statement::make_temporary(NULL, *pexpr, loc);
1925       var->add_preinit_statement(ts);
1926       *pexpr = Expression::make_temporary_reference(ts, loc);
1927     }
1928
1929   return TRAVERSE_SKIP_COMPONENTS;
1930 }
1931
1932 // Use temporary variables to implement the order of evaluation rules.
1933
1934 void
1935 Gogo::order_evaluations()
1936 {
1937   Order_eval order_eval;
1938   this->traverse(&order_eval);
1939 }
1940
1941 // Traversal to convert calls to the predeclared recover function to
1942 // pass in an argument indicating whether it can recover from a panic
1943 // or not.
1944
1945 class Convert_recover : public Traverse
1946 {
1947  public:
1948   Convert_recover(Named_object* arg)
1949     : Traverse(traverse_expressions),
1950       arg_(arg)
1951   { }
1952
1953  protected:
1954   int
1955   expression(Expression**);
1956
1957  private:
1958   // The argument to pass to the function.
1959   Named_object* arg_;
1960 };
1961
1962 // Convert calls to recover.
1963
1964 int
1965 Convert_recover::expression(Expression** pp)
1966 {
1967   Call_expression* ce = (*pp)->call_expression();
1968   if (ce != NULL && ce->is_recover_call())
1969     ce->set_recover_arg(Expression::make_var_reference(this->arg_,
1970                                                        ce->location()));
1971   return TRAVERSE_CONTINUE;
1972 }
1973
1974 // Traversal for build_recover_thunks.
1975
1976 class Build_recover_thunks : public Traverse
1977 {
1978  public:
1979   Build_recover_thunks(Gogo* gogo)
1980     : Traverse(traverse_functions),
1981       gogo_(gogo)
1982   { }
1983
1984   int
1985   function(Named_object*);
1986
1987  private:
1988   Expression*
1989   can_recover_arg(source_location);
1990
1991   // General IR.
1992   Gogo* gogo_;
1993 };
1994
1995 // If this function calls recover, turn it into a thunk.
1996
1997 int
1998 Build_recover_thunks::function(Named_object* orig_no)
1999 {
2000   Function* orig_func = orig_no->func_value();
2001   if (!orig_func->calls_recover()
2002       || orig_func->is_recover_thunk()
2003       || orig_func->has_recover_thunk())
2004     return TRAVERSE_CONTINUE;
2005
2006   Gogo* gogo = this->gogo_;
2007   source_location location = orig_func->location();
2008
2009   static int count;
2010   char buf[50];
2011
2012   Function_type* orig_fntype = orig_func->type();
2013   Typed_identifier_list* new_params = new Typed_identifier_list();
2014   std::string receiver_name;
2015   if (orig_fntype->is_method())
2016     {
2017       const Typed_identifier* receiver = orig_fntype->receiver();
2018       snprintf(buf, sizeof buf, "rt.%u", count);
2019       ++count;
2020       receiver_name = buf;
2021       new_params->push_back(Typed_identifier(receiver_name, receiver->type(),
2022                                              receiver->location()));
2023     }
2024   const Typed_identifier_list* orig_params = orig_fntype->parameters();
2025   if (orig_params != NULL && !orig_params->empty())
2026     {
2027       for (Typed_identifier_list::const_iterator p = orig_params->begin();
2028            p != orig_params->end();
2029            ++p)
2030         {
2031           snprintf(buf, sizeof buf, "pt.%u", count);
2032           ++count;
2033           new_params->push_back(Typed_identifier(buf, p->type(),
2034                                                  p->location()));
2035         }
2036     }
2037   snprintf(buf, sizeof buf, "pr.%u", count);
2038   ++count;
2039   std::string can_recover_name = buf;
2040   new_params->push_back(Typed_identifier(can_recover_name,
2041                                          Type::make_boolean_type(),
2042                                          orig_fntype->location()));
2043
2044   const Typed_identifier_list* orig_results = orig_fntype->results();
2045   Typed_identifier_list* new_results;
2046   if (orig_results == NULL || orig_results->empty())
2047     new_results = NULL;
2048   else
2049     {
2050       new_results = new Typed_identifier_list();
2051       for (Typed_identifier_list::const_iterator p = orig_results->begin();
2052            p != orig_results->end();
2053            ++p)
2054         new_results->push_back(*p);
2055     }
2056
2057   Function_type *new_fntype = Type::make_function_type(NULL, new_params,
2058                                                        new_results,
2059                                                        orig_fntype->location());
2060   if (orig_fntype->is_varargs())
2061     new_fntype->set_is_varargs();
2062
2063   std::string name = orig_no->name() + "$recover";
2064   Named_object *new_no = gogo->start_function(name, new_fntype, false,
2065                                               location);
2066   Function *new_func = new_no->func_value();
2067   if (orig_func->enclosing() != NULL)
2068     new_func->set_enclosing(orig_func->enclosing());
2069
2070   // We build the code for the original function attached to the new
2071   // function, and then swap the original and new function bodies.
2072   // This means that existing references to the original function will
2073   // then refer to the new function.  That makes this code a little
2074   // confusing, in that the reference to NEW_NO really refers to the
2075   // other function, not the one we are building.
2076
2077   Expression* closure = NULL;
2078   if (orig_func->needs_closure())
2079     {
2080       Named_object* orig_closure_no = orig_func->closure_var();
2081       Variable* orig_closure_var = orig_closure_no->var_value();
2082       Variable* new_var = new Variable(orig_closure_var->type(), NULL, false,
2083                                        true, false, location);
2084       snprintf(buf, sizeof buf, "closure.%u", count);
2085       ++count;
2086       Named_object* new_closure_no = Named_object::make_variable(buf, NULL,
2087                                                                  new_var);
2088       new_func->set_closure_var(new_closure_no);
2089       closure = Expression::make_var_reference(new_closure_no, location);
2090     }
2091
2092   Expression* fn = Expression::make_func_reference(new_no, closure, location);
2093
2094   Expression_list* args = new Expression_list();
2095   if (orig_fntype->is_method())
2096     {
2097       Named_object* rec_no = gogo->lookup(receiver_name, NULL);
2098       gcc_assert(rec_no != NULL
2099                  && rec_no->is_variable()
2100                  && rec_no->var_value()->is_parameter());
2101       args->push_back(Expression::make_var_reference(rec_no, location));
2102     }
2103   if (new_params != NULL)
2104     {
2105       // Note that we skip the last parameter, which is the boolean
2106       // indicating whether recover can succed.
2107       for (Typed_identifier_list::const_iterator p = new_params->begin();
2108            p + 1 != new_params->end();
2109            ++p)
2110         {
2111           Named_object* p_no = gogo->lookup(p->name(), NULL);
2112           gcc_assert(p_no != NULL
2113                      && p_no->is_variable()
2114                      && p_no->var_value()->is_parameter());
2115           args->push_back(Expression::make_var_reference(p_no, location));
2116         }
2117     }
2118   args->push_back(this->can_recover_arg(location));
2119
2120   Expression* call = Expression::make_call(fn, args, false, location);
2121
2122   Statement* s;
2123   if (orig_fntype->results() == NULL || orig_fntype->results()->empty())
2124     s = Statement::make_statement(call);
2125   else
2126     {
2127       Expression_list* vals = new Expression_list();
2128       vals->push_back(call);
2129       s = Statement::make_return_statement(new_func->type()->results(),
2130                                            vals, location);
2131     }
2132   s->determine_types();
2133   gogo->add_statement(s);
2134
2135   gogo->finish_function(location);
2136
2137   // Swap the function bodies and types.
2138   new_func->swap_for_recover(orig_func);
2139   orig_func->set_is_recover_thunk();
2140   new_func->set_calls_recover();
2141   new_func->set_has_recover_thunk();
2142
2143   Bindings* orig_bindings = orig_func->block()->bindings();
2144   Bindings* new_bindings = new_func->block()->bindings();
2145   if (orig_fntype->is_method())
2146     {
2147       // We changed the receiver to be a regular parameter.  We have
2148       // to update the binding accordingly in both functions.
2149       Named_object* orig_rec_no = orig_bindings->lookup_local(receiver_name);
2150       gcc_assert(orig_rec_no != NULL
2151                  && orig_rec_no->is_variable()
2152                  && !orig_rec_no->var_value()->is_receiver());
2153       orig_rec_no->var_value()->set_is_receiver();
2154
2155       Named_object* new_rec_no = new_bindings->lookup_local(receiver_name);
2156       gcc_assert(new_rec_no != NULL
2157                  && new_rec_no->is_variable()
2158                  && !new_rec_no->var_value()->is_receiver());
2159       new_rec_no->var_value()->set_is_not_receiver();
2160     }
2161
2162   // Because we flipped blocks but not types, the can_recover
2163   // parameter appears in the (now) old bindings as a parameter.
2164   // Change it to a local variable, whereupon it will be discarded.
2165   Named_object* can_recover_no = orig_bindings->lookup_local(can_recover_name);
2166   gcc_assert(can_recover_no != NULL
2167              && can_recover_no->is_variable()
2168              && can_recover_no->var_value()->is_parameter());
2169   orig_bindings->remove_binding(can_recover_no);
2170
2171   // Add the can_recover argument to the (now) new bindings, and
2172   // attach it to any recover statements.
2173   Variable* can_recover_var = new Variable(Type::make_boolean_type(), NULL,
2174                                            false, true, false, location);
2175   can_recover_no = new_bindings->add_variable(can_recover_name, NULL,
2176                                               can_recover_var);
2177   Convert_recover convert_recover(can_recover_no);
2178   new_func->traverse(&convert_recover);
2179
2180   return TRAVERSE_CONTINUE;
2181 }
2182
2183 // Return the expression to pass for the .can_recover parameter to the
2184 // new function.  This indicates whether a call to recover may return
2185 // non-nil.  The expression is
2186 // __go_can_recover(__builtin_return_address()).
2187
2188 Expression*
2189 Build_recover_thunks::can_recover_arg(source_location location)
2190 {
2191   static Named_object* builtin_return_address;
2192   if (builtin_return_address == NULL)
2193     {
2194       const source_location bloc = BUILTINS_LOCATION;
2195
2196       Typed_identifier_list* param_types = new Typed_identifier_list();
2197       Type* uint_type = Type::lookup_integer_type("uint");
2198       param_types->push_back(Typed_identifier("l", uint_type, bloc));
2199
2200       Typed_identifier_list* return_types = new Typed_identifier_list();
2201       Type* voidptr_type = Type::make_pointer_type(Type::make_void_type());
2202       return_types->push_back(Typed_identifier("", voidptr_type, bloc));
2203
2204       Function_type* fntype = Type::make_function_type(NULL, param_types,
2205                                                        return_types, bloc);
2206       builtin_return_address =
2207         Named_object::make_function_declaration("__builtin_return_address",
2208                                                 NULL, fntype, bloc);
2209       const char* n = "__builtin_return_address";
2210       builtin_return_address->func_declaration_value()->set_asm_name(n);
2211     }
2212
2213   static Named_object* can_recover;
2214   if (can_recover == NULL)
2215     {
2216       const source_location bloc = BUILTINS_LOCATION;
2217       Typed_identifier_list* param_types = new Typed_identifier_list();
2218       Type* voidptr_type = Type::make_pointer_type(Type::make_void_type());
2219       param_types->push_back(Typed_identifier("a", voidptr_type, bloc));
2220       Type* boolean_type = Type::make_boolean_type();
2221       Typed_identifier_list* results = new Typed_identifier_list();
2222       results->push_back(Typed_identifier("", boolean_type, bloc));
2223       Function_type* fntype = Type::make_function_type(NULL, param_types,
2224                                                        results, bloc);
2225       can_recover = Named_object::make_function_declaration("__go_can_recover",
2226                                                             NULL, fntype,
2227                                                             bloc);
2228       can_recover->func_declaration_value()->set_asm_name("__go_can_recover");
2229     }
2230
2231   Expression* fn = Expression::make_func_reference(builtin_return_address,
2232                                                    NULL, location);
2233
2234   mpz_t zval;
2235   mpz_init_set_ui(zval, 0UL);
2236   Expression* zexpr = Expression::make_integer(&zval, NULL, location);
2237   mpz_clear(zval);
2238   Expression_list *args = new Expression_list();
2239   args->push_back(zexpr);
2240
2241   Expression* call = Expression::make_call(fn, args, false, location);
2242
2243   args = new Expression_list();
2244   args->push_back(call);
2245
2246   fn = Expression::make_func_reference(can_recover, NULL, location);
2247   return Expression::make_call(fn, args, false, location);
2248 }
2249
2250 // Build thunks for functions which call recover.  We build a new
2251 // function with an extra parameter, which is whether a call to
2252 // recover can succeed.  We then move the body of this function to
2253 // that one.  We then turn this function into a thunk which calls the
2254 // new one, passing the value of
2255 // __go_can_recover(__builtin_return_address()).  The function will be
2256 // marked as not splitting the stack.  This will cooperate with the
2257 // implementation of defer to make recover do the right thing.
2258
2259 void
2260 Gogo::build_recover_thunks()
2261 {
2262   Build_recover_thunks build_recover_thunks(this);
2263   this->traverse(&build_recover_thunks);
2264 }
2265
2266 // Look for named types to see whether we need to create an interface
2267 // method table.
2268
2269 class Build_method_tables : public Traverse
2270 {
2271  public:
2272   Build_method_tables(Gogo* gogo,
2273                       const std::vector<Interface_type*>& interfaces)
2274     : Traverse(traverse_types),
2275       gogo_(gogo), interfaces_(interfaces)
2276   { }
2277
2278   int
2279   type(Type*);
2280
2281  private:
2282   // The IR.
2283   Gogo* gogo_;
2284   // A list of locally defined interfaces which have hidden methods.
2285   const std::vector<Interface_type*>& interfaces_;
2286 };
2287
2288 // Build all required interface method tables for types.  We need to
2289 // ensure that we have an interface method table for every interface
2290 // which has a hidden method, for every named type which implements
2291 // that interface.  Normally we can just build interface method tables
2292 // as we need them.  However, in some cases we can require an
2293 // interface method table for an interface defined in a different
2294 // package for a type defined in that package.  If that interface and
2295 // type both use a hidden method, that is OK.  However, we will not be
2296 // able to build that interface method table when we need it, because
2297 // the type's hidden method will be static.  So we have to build it
2298 // here, and just refer it from other packages as needed.
2299
2300 void
2301 Gogo::build_interface_method_tables()
2302 {
2303   std::vector<Interface_type*> hidden_interfaces;
2304   hidden_interfaces.reserve(this->interface_types_.size());
2305   for (std::vector<Interface_type*>::const_iterator pi =
2306          this->interface_types_.begin();
2307        pi != this->interface_types_.end();
2308        ++pi)
2309     {
2310       const Typed_identifier_list* methods = (*pi)->methods();
2311       if (methods == NULL)
2312         continue;
2313       for (Typed_identifier_list::const_iterator pm = methods->begin();
2314            pm != methods->end();
2315            ++pm)
2316         {
2317           if (Gogo::is_hidden_name(pm->name()))
2318             {
2319               hidden_interfaces.push_back(*pi);
2320               break;
2321             }
2322         }
2323     }
2324
2325   if (!hidden_interfaces.empty())
2326     {
2327       // Now traverse the tree looking for all named types.
2328       Build_method_tables bmt(this, hidden_interfaces);
2329       this->traverse(&bmt);
2330     }
2331
2332   // We no longer need the list of interfaces.
2333
2334   this->interface_types_.clear();
2335 }
2336
2337 // This is called for each type.  For a named type, for each of the
2338 // interfaces with hidden methods that it implements, create the
2339 // method table.
2340
2341 int
2342 Build_method_tables::type(Type* type)
2343 {
2344   Named_type* nt = type->named_type();
2345   if (nt != NULL)
2346     {
2347       for (std::vector<Interface_type*>::const_iterator p =
2348              this->interfaces_.begin();
2349            p != this->interfaces_.end();
2350            ++p)
2351         {
2352           // We ask whether a pointer to the named type implements the
2353           // interface, because a pointer can implement more methods
2354           // than a value.
2355           if ((*p)->implements_interface(Type::make_pointer_type(nt), NULL))
2356             {
2357               nt->interface_method_table(this->gogo_, *p, false);
2358               nt->interface_method_table(this->gogo_, *p, true);
2359             }
2360         }
2361     }
2362   return TRAVERSE_CONTINUE;
2363 }
2364
2365 // Traversal class used to check for return statements.
2366
2367 class Check_return_statements_traverse : public Traverse
2368 {
2369  public:
2370   Check_return_statements_traverse()
2371     : Traverse(traverse_functions)
2372   { }
2373
2374   int
2375   function(Named_object*);
2376 };
2377
2378 // Check that a function has a return statement if it needs one.
2379
2380 int
2381 Check_return_statements_traverse::function(Named_object* no)
2382 {
2383   Function* func = no->func_value();
2384   const Function_type* fntype = func->type();
2385   const Typed_identifier_list* results = fntype->results();
2386
2387   // We only need a return statement if there is a return value.
2388   if (results == NULL || results->empty())
2389     return TRAVERSE_CONTINUE;
2390
2391   if (func->block()->may_fall_through())
2392     error_at(func->location(), "control reaches end of non-void function");
2393
2394   return TRAVERSE_CONTINUE;
2395 }
2396
2397 // Check return statements.
2398
2399 void
2400 Gogo::check_return_statements()
2401 {
2402   Check_return_statements_traverse traverse;
2403   this->traverse(&traverse);
2404 }
2405
2406 // Get the unique prefix to use before all exported symbols.  This
2407 // must be unique across the entire link.
2408
2409 const std::string&
2410 Gogo::unique_prefix() const
2411 {
2412   gcc_assert(!this->unique_prefix_.empty());
2413   return this->unique_prefix_;
2414 }
2415
2416 // Set the unique prefix to use before all exported symbols.  This
2417 // comes from the command line option -fgo-prefix=XXX.
2418
2419 void
2420 Gogo::set_unique_prefix(const std::string& arg)
2421 {
2422   gcc_assert(this->unique_prefix_.empty());
2423   this->unique_prefix_ = arg;
2424 }
2425
2426 // Work out the package priority.  It is one more than the maximum
2427 // priority of an imported package.
2428
2429 int
2430 Gogo::package_priority() const
2431 {
2432   int priority = 0;
2433   for (Packages::const_iterator p = this->packages_.begin();
2434        p != this->packages_.end();
2435        ++p)
2436     if (p->second->priority() > priority)
2437       priority = p->second->priority();
2438   return priority + 1;
2439 }
2440
2441 // Export identifiers as requested.
2442
2443 void
2444 Gogo::do_exports()
2445 {
2446   // For now we always stream to a section.  Later we may want to
2447   // support streaming to a separate file.
2448   Stream_to_section stream;
2449
2450   Export exp(&stream);
2451   exp.register_builtin_types(this);
2452   exp.export_globals(this->package_name(),
2453                      this->unique_prefix(),
2454                      this->package_priority(),
2455                      (this->need_init_fn_ && this->package_name() != "main"
2456                       ? this->get_init_fn_name()
2457                       : ""),
2458                      this->imported_init_fns_,
2459                      this->package_->bindings());
2460 }
2461
2462 // Class Function.
2463
2464 Function::Function(Function_type* type, Function* enclosing, Block* block,
2465                    source_location location)
2466   : type_(type), enclosing_(enclosing), named_results_(NULL),
2467     closure_var_(NULL), block_(block), location_(location), fndecl_(NULL),
2468     defer_stack_(NULL), calls_recover_(false), is_recover_thunk_(false),
2469     has_recover_thunk_(false)
2470 {
2471 }
2472
2473 // Create the named result variables.
2474
2475 void
2476 Function::create_named_result_variables()
2477 {
2478   const Typed_identifier_list* results = this->type_->results();
2479   if (results == NULL
2480       || results->empty()
2481       || results->front().name().empty())
2482     return;
2483
2484   this->named_results_ = new Named_results();
2485   this->named_results_->reserve(results->size());
2486
2487   Block* block = this->block_;
2488   int index = 0;
2489   for (Typed_identifier_list::const_iterator p = results->begin();
2490        p != results->end();
2491        ++p, ++index)
2492     {
2493       Result_variable* result = new Result_variable(p->type(), this,
2494                                                     index);
2495       Named_object* no = block->bindings()->add_result_variable(p->name(),
2496                                                                 result);
2497       this->named_results_->push_back(no);
2498     }
2499 }
2500
2501 // Return the closure variable, creating it if necessary.
2502
2503 Named_object*
2504 Function::closure_var()
2505 {
2506   if (this->closure_var_ == NULL)
2507     {
2508       // We don't know the type of the variable yet.  We add fields as
2509       // we find them.
2510       source_location loc = this->type_->location();
2511       Struct_field_list* sfl = new Struct_field_list;
2512       Type* struct_type = Type::make_struct_type(sfl, loc);
2513       Variable* var = new Variable(Type::make_pointer_type(struct_type),
2514                                    NULL, false, true, false, loc);
2515       this->closure_var_ = Named_object::make_variable("closure", NULL, var);
2516       // Note that the new variable is not in any binding contour.
2517     }
2518   return this->closure_var_;
2519 }
2520
2521 // Set the type of the closure variable.
2522
2523 void
2524 Function::set_closure_type()
2525 {
2526   if (this->closure_var_ == NULL)
2527     return;
2528   Named_object* closure = this->closure_var_;
2529   Struct_type* st = closure->var_value()->type()->deref()->struct_type();
2530   unsigned int index = 0;
2531   for (Closure_fields::const_iterator p = this->closure_fields_.begin();
2532        p != this->closure_fields_.end();
2533        ++p, ++index)
2534     {
2535       Named_object* no = p->first;
2536       char buf[20];
2537       snprintf(buf, sizeof buf, "%u", index);
2538       std::string n = no->name() + buf;
2539       Type* var_type;
2540       if (no->is_variable())
2541         var_type = no->var_value()->type();
2542       else
2543         var_type = no->result_var_value()->type();
2544       Type* field_type = Type::make_pointer_type(var_type);
2545       st->push_field(Struct_field(Typed_identifier(n, field_type, p->second)));
2546     }
2547 }
2548
2549 // Return whether this function is a method.
2550
2551 bool
2552 Function::is_method() const
2553 {
2554   return this->type_->is_method();
2555 }
2556
2557 // Add a label definition.
2558
2559 Label*
2560 Function::add_label_definition(const std::string& label_name,
2561                                source_location location)
2562 {
2563   Label* lnull = NULL;
2564   std::pair<Labels::iterator, bool> ins =
2565     this->labels_.insert(std::make_pair(label_name, lnull));
2566   if (ins.second)
2567     {
2568       // This is a new label.
2569       Label* label = new Label(label_name);
2570       label->define(location);
2571       ins.first->second = label;
2572       return label;
2573     }
2574   else
2575     {
2576       // The label was already in the hash table.
2577       Label* label = ins.first->second;
2578       if (!label->is_defined())
2579         {
2580           label->define(location);
2581           return label;
2582         }
2583       else
2584         {
2585           error_at(location, "redefinition of label %qs",
2586                    Gogo::message_name(label_name).c_str());
2587           inform(label->location(), "previous definition of %qs was here",
2588                  Gogo::message_name(label_name).c_str());
2589           return new Label(label_name);
2590         }
2591     }
2592 }
2593
2594 // Add a reference to a label.
2595
2596 Label*
2597 Function::add_label_reference(const std::string& label_name)
2598 {
2599   Label* lnull = NULL;
2600   std::pair<Labels::iterator, bool> ins =
2601     this->labels_.insert(std::make_pair(label_name, lnull));
2602   if (!ins.second)
2603     {
2604       // The label was already in the hash table.
2605       return ins.first->second;
2606     }
2607   else
2608     {
2609       gcc_assert(ins.first->second == NULL);
2610       Label* label = new Label(label_name);
2611       ins.first->second = label;
2612       return label;
2613     }
2614 }
2615
2616 // Swap one function with another.  This is used when building the
2617 // thunk we use to call a function which calls recover.  It may not
2618 // work for any other case.
2619
2620 void
2621 Function::swap_for_recover(Function *x)
2622 {
2623   gcc_assert(this->enclosing_ == x->enclosing_);
2624   gcc_assert(this->named_results_ == x->named_results_);
2625   std::swap(this->closure_var_, x->closure_var_);
2626   std::swap(this->block_, x->block_);
2627   gcc_assert(this->location_ == x->location_);
2628   gcc_assert(this->fndecl_ == NULL && x->fndecl_ == NULL);
2629   gcc_assert(this->defer_stack_ == NULL && x->defer_stack_ == NULL);
2630 }
2631
2632 // Traverse the tree.
2633
2634 int
2635 Function::traverse(Traverse* traverse)
2636 {
2637   unsigned int traverse_mask = traverse->traverse_mask();
2638
2639   // FIXME: We should check traverse_functions here if nested
2640   // functions are stored in block bindings.
2641   if (this->block_ != NULL
2642       && (traverse_mask
2643           & (Traverse::traverse_variables
2644              | Traverse::traverse_constants
2645              | Traverse::traverse_blocks
2646              | Traverse::traverse_statements
2647              | Traverse::traverse_expressions
2648              | Traverse::traverse_types)) != 0)
2649     {
2650       if (this->block_->traverse(traverse) == TRAVERSE_EXIT)
2651         return TRAVERSE_EXIT;
2652     }
2653
2654   return TRAVERSE_CONTINUE;
2655 }
2656
2657 // Work out types for unspecified variables and constants.
2658
2659 void
2660 Function::determine_types()
2661 {
2662   if (this->block_ != NULL)
2663     this->block_->determine_types();
2664 }
2665
2666 // Export the function.
2667
2668 void
2669 Function::export_func(Export* exp, const std::string& name) const
2670 {
2671   Function::export_func_with_type(exp, name, this->type_);
2672 }
2673
2674 // Export a function with a type.
2675
2676 void
2677 Function::export_func_with_type(Export* exp, const std::string& name,
2678                                 const Function_type* fntype)
2679 {
2680   exp->write_c_string("func ");
2681
2682   if (fntype->is_method())
2683     {
2684       exp->write_c_string("(");
2685       exp->write_type(fntype->receiver()->type());
2686       exp->write_c_string(") ");
2687     }
2688
2689   exp->write_string(name);
2690
2691   exp->write_c_string(" (");
2692   const Typed_identifier_list* parameters = fntype->parameters();
2693   if (parameters != NULL)
2694     {
2695       bool is_varargs = fntype->is_varargs();
2696       bool first = true;
2697       for (Typed_identifier_list::const_iterator p = parameters->begin();
2698            p != parameters->end();
2699            ++p)
2700         {
2701           if (first)
2702             first = false;
2703           else
2704             exp->write_c_string(", ");
2705           if (!is_varargs || p + 1 != parameters->end())
2706             exp->write_type(p->type());
2707           else
2708             {
2709               exp->write_c_string("...");
2710               exp->write_type(p->type()->array_type()->element_type());
2711             }
2712         }
2713     }
2714   exp->write_c_string(")");
2715
2716   const Typed_identifier_list* results = fntype->results();
2717   if (results != NULL)
2718     {
2719       if (results->size() == 1)
2720         {
2721           exp->write_c_string(" ");
2722           exp->write_type(results->begin()->type());
2723         }
2724       else
2725         {
2726           exp->write_c_string(" (");
2727           bool first = true;
2728           for (Typed_identifier_list::const_iterator p = results->begin();
2729                p != results->end();
2730                ++p)
2731             {
2732               if (first)
2733                 first = false;
2734               else
2735                 exp->write_c_string(", ");
2736               exp->write_type(p->type());
2737             }
2738           exp->write_c_string(")");
2739         }
2740     }
2741   exp->write_c_string(";\n");
2742 }
2743
2744 // Import a function.
2745
2746 void
2747 Function::import_func(Import* imp, std::string* pname,
2748                       Typed_identifier** preceiver,
2749                       Typed_identifier_list** pparameters,
2750                       Typed_identifier_list** presults,
2751                       bool* is_varargs)
2752 {
2753   imp->require_c_string("func ");
2754
2755   *preceiver = NULL;
2756   if (imp->peek_char() == '(')
2757     {
2758       imp->require_c_string("(");
2759       Type* rtype = imp->read_type();
2760       *preceiver = new Typed_identifier(Import::import_marker, rtype,
2761                                         imp->location());
2762       imp->require_c_string(") ");
2763     }
2764
2765   *pname = imp->read_identifier();
2766
2767   Typed_identifier_list* parameters;
2768   *is_varargs = false;
2769   imp->require_c_string(" (");
2770   if (imp->peek_char() == ')')
2771     parameters = NULL;
2772   else
2773     {
2774       parameters = new Typed_identifier_list();
2775       while (true)
2776         {
2777           if (imp->match_c_string("..."))
2778             {
2779               imp->advance(3);
2780               *is_varargs = true;
2781             }
2782
2783           Type* ptype = imp->read_type();
2784           if (*is_varargs)
2785             ptype = Type::make_array_type(ptype, NULL);
2786           parameters->push_back(Typed_identifier(Import::import_marker,
2787                                                  ptype, imp->location()));
2788           if (imp->peek_char() != ',')
2789             break;
2790           gcc_assert(!*is_varargs);
2791           imp->require_c_string(", ");
2792         }
2793     }
2794   imp->require_c_string(")");
2795   *pparameters = parameters;
2796
2797   Typed_identifier_list* results;
2798   if (imp->peek_char() != ' ')
2799     results = NULL;
2800   else
2801     {
2802       results = new Typed_identifier_list();
2803       imp->require_c_string(" ");
2804       if (imp->peek_char() != '(')
2805         {
2806           Type* rtype = imp->read_type();
2807           results->push_back(Typed_identifier(Import::import_marker, rtype,
2808                                               imp->location()));
2809         }
2810       else
2811         {
2812           imp->require_c_string("(");
2813           while (true)
2814             {
2815               Type* rtype = imp->read_type();
2816               results->push_back(Typed_identifier(Import::import_marker,
2817                                                   rtype, imp->location()));
2818               if (imp->peek_char() != ',')
2819                 break;
2820               imp->require_c_string(", ");
2821             }
2822           imp->require_c_string(")");
2823         }
2824     }
2825   imp->require_c_string(";\n");
2826   *presults = results;
2827 }
2828
2829 // Class Block.
2830
2831 Block::Block(Block* enclosing, source_location location)
2832   : enclosing_(enclosing), statements_(),
2833     bindings_(new Bindings(enclosing == NULL
2834                            ? NULL
2835                            : enclosing->bindings())),
2836     start_location_(location),
2837     end_location_(UNKNOWN_LOCATION)
2838 {
2839 }
2840
2841 // Add a statement to a block.
2842
2843 void
2844 Block::add_statement(Statement* statement)
2845 {
2846   this->statements_.push_back(statement);
2847 }
2848
2849 // Add a statement to the front of a block.  This is slow but is only
2850 // used for reference counts of parameters.
2851
2852 void
2853 Block::add_statement_at_front(Statement* statement)
2854 {
2855   this->statements_.insert(this->statements_.begin(), statement);
2856 }
2857
2858 // Replace a statement in a block.
2859
2860 void
2861 Block::replace_statement(size_t index, Statement* s)
2862 {
2863   gcc_assert(index < this->statements_.size());
2864   this->statements_[index] = s;
2865 }
2866
2867 // Add a statement before another statement.
2868
2869 void
2870 Block::insert_statement_before(size_t index, Statement* s)
2871 {
2872   gcc_assert(index < this->statements_.size());
2873   this->statements_.insert(this->statements_.begin() + index, s);
2874 }
2875
2876 // Add a statement after another statement.
2877
2878 void
2879 Block::insert_statement_after(size_t index, Statement* s)
2880 {
2881   gcc_assert(index < this->statements_.size());
2882   this->statements_.insert(this->statements_.begin() + index + 1, s);
2883 }
2884
2885 // Traverse the tree.
2886
2887 int
2888 Block::traverse(Traverse* traverse)
2889 {
2890   unsigned int traverse_mask = traverse->traverse_mask();
2891
2892   if ((traverse_mask & Traverse::traverse_blocks) != 0)
2893     {
2894       int t = traverse->block(this);
2895       if (t == TRAVERSE_EXIT)
2896         return TRAVERSE_EXIT;
2897       else if (t == TRAVERSE_SKIP_COMPONENTS)
2898         return TRAVERSE_CONTINUE;
2899     }
2900
2901   if ((traverse_mask
2902        & (Traverse::traverse_variables
2903           | Traverse::traverse_constants
2904           | Traverse::traverse_expressions
2905           | Traverse::traverse_types)) != 0)
2906     {
2907       for (Bindings::const_definitions_iterator pb =
2908              this->bindings_->begin_definitions();
2909            pb != this->bindings_->end_definitions();
2910            ++pb)
2911         {
2912           switch ((*pb)->classification())
2913             {
2914             case Named_object::NAMED_OBJECT_CONST:
2915               if ((traverse_mask & Traverse::traverse_constants) != 0)
2916                 {
2917                   if (traverse->constant(*pb, false) == TRAVERSE_EXIT)
2918                     return TRAVERSE_EXIT;
2919                 }
2920               if ((traverse_mask & Traverse::traverse_types) != 0
2921                   || (traverse_mask & Traverse::traverse_expressions) != 0)
2922                 {
2923                   Type* t = (*pb)->const_value()->type();
2924                   if (t != NULL
2925                       && Type::traverse(t, traverse) == TRAVERSE_EXIT)
2926                     return TRAVERSE_EXIT;
2927                 }
2928               if ((traverse_mask & Traverse::traverse_expressions) != 0
2929                   || (traverse_mask & Traverse::traverse_types) != 0)
2930                 {
2931                   if ((*pb)->const_value()->traverse_expression(traverse)
2932                       == TRAVERSE_EXIT)
2933                     return TRAVERSE_EXIT;
2934                 }
2935               break;
2936
2937             case Named_object::NAMED_OBJECT_VAR:
2938             case Named_object::NAMED_OBJECT_RESULT_VAR:
2939               if ((traverse_mask & Traverse::traverse_variables) != 0)
2940                 {
2941                   if (traverse->variable(*pb) == TRAVERSE_EXIT)
2942                     return TRAVERSE_EXIT;
2943                 }
2944               if (((traverse_mask & Traverse::traverse_types) != 0
2945                    || (traverse_mask & Traverse::traverse_expressions) != 0)
2946                   && ((*pb)->is_result_variable()
2947                       || (*pb)->var_value()->has_type()))
2948                 {
2949                   Type* t = ((*pb)->is_variable()
2950                              ? (*pb)->var_value()->type()
2951                              : (*pb)->result_var_value()->type());
2952                   if (t != NULL
2953                       && Type::traverse(t, traverse) == TRAVERSE_EXIT)
2954                     return TRAVERSE_EXIT;
2955                 }
2956               if ((*pb)->is_variable()
2957                   && ((traverse_mask & Traverse::traverse_expressions) != 0
2958                       || (traverse_mask & Traverse::traverse_types) != 0))
2959                 {
2960                   if ((*pb)->var_value()->traverse_expression(traverse)
2961                       == TRAVERSE_EXIT)
2962                     return TRAVERSE_EXIT;
2963                 }
2964               break;
2965
2966             case Named_object::NAMED_OBJECT_FUNC:
2967             case Named_object::NAMED_OBJECT_FUNC_DECLARATION:
2968               // FIXME: Where will nested functions be found?
2969               gcc_unreachable();
2970
2971             case Named_object::NAMED_OBJECT_TYPE:
2972               if ((traverse_mask & Traverse::traverse_types) != 0
2973                   || (traverse_mask & Traverse::traverse_expressions) != 0)
2974                 {
2975                   if (Type::traverse((*pb)->type_value(), traverse)
2976                       == TRAVERSE_EXIT)
2977                     return TRAVERSE_EXIT;
2978                 }
2979               break;
2980
2981             case Named_object::NAMED_OBJECT_TYPE_DECLARATION:
2982             case Named_object::NAMED_OBJECT_UNKNOWN:
2983               break;
2984
2985             case Named_object::NAMED_OBJECT_PACKAGE:
2986             case Named_object::NAMED_OBJECT_SINK:
2987               gcc_unreachable();
2988
2989             default:
2990               gcc_unreachable();
2991             }
2992         }
2993     }
2994
2995   // No point in checking traverse_mask here--if we got here we always
2996   // want to walk the statements.  The traversal can insert new
2997   // statements before or after the current statement.  Inserting
2998   // statements before the current statement requires updating I via
2999   // the pointer; those statements will not be traversed.  Any new
3000   // statements inserted after the current statement will be traversed
3001   // in their turn.
3002   for (size_t i = 0; i < this->statements_.size(); ++i)
3003     {
3004       if (this->statements_[i]->traverse(this, &i, traverse) == TRAVERSE_EXIT)
3005         return TRAVERSE_EXIT;
3006     }
3007
3008   return TRAVERSE_CONTINUE;
3009 }
3010
3011 // Work out types for unspecified variables and constants.
3012
3013 void
3014 Block::determine_types()
3015 {
3016   for (Bindings::const_definitions_iterator pb =
3017          this->bindings_->begin_definitions();
3018        pb != this->bindings_->end_definitions();
3019        ++pb)
3020     {
3021       if ((*pb)->is_variable())
3022         (*pb)->var_value()->determine_type();
3023       else if ((*pb)->is_const())
3024         (*pb)->const_value()->determine_type();
3025     }
3026
3027   for (std::vector<Statement*>::const_iterator ps = this->statements_.begin();
3028        ps != this->statements_.end();
3029        ++ps)
3030     (*ps)->determine_types();
3031 }
3032
3033 // Return true if the statements in this block may fall through.
3034
3035 bool
3036 Block::may_fall_through() const
3037 {
3038   if (this->statements_.empty())
3039     return true;
3040   return this->statements_.back()->may_fall_through();
3041 }
3042
3043 // Class Variable.
3044
3045 Variable::Variable(Type* type, Expression* init, bool is_global,
3046                    bool is_parameter, bool is_receiver,
3047                    source_location location)
3048   : type_(type), init_(init), preinit_(NULL), location_(location),
3049     is_global_(is_global), is_parameter_(is_parameter),
3050     is_receiver_(is_receiver), is_varargs_parameter_(false),
3051     is_address_taken_(false), init_is_lowered_(false),
3052     type_from_init_tuple_(false), type_from_range_index_(false),
3053     type_from_range_value_(false), type_from_chan_element_(false),
3054     is_type_switch_var_(false)
3055 {
3056   gcc_assert(type != NULL || init != NULL);
3057   gcc_assert(!is_parameter || init == NULL);
3058 }
3059
3060 // Traverse the initializer expression.
3061
3062 int
3063 Variable::traverse_expression(Traverse* traverse)
3064 {
3065   if (this->preinit_ != NULL)
3066     {
3067       if (this->preinit_->traverse(traverse) == TRAVERSE_EXIT)
3068         return TRAVERSE_EXIT;
3069     }
3070   if (this->init_ != NULL)
3071     {
3072       if (Expression::traverse(&this->init_, traverse) == TRAVERSE_EXIT)
3073         return TRAVERSE_EXIT;
3074     }
3075   return TRAVERSE_CONTINUE;
3076 }
3077
3078 // Lower the initialization expression after parsing is complete.
3079
3080 void
3081 Variable::lower_init_expression(Gogo* gogo, Named_object* function)
3082 {
3083   if (this->init_ != NULL && !this->init_is_lowered_)
3084     {
3085       gogo->lower_expression(function, &this->init_);
3086       this->init_is_lowered_ = true;
3087     }
3088 }
3089
3090 // Get the preinit block.
3091
3092 Block*
3093 Variable::preinit_block()
3094 {
3095   gcc_assert(this->is_global_);
3096   if (this->preinit_ == NULL)
3097     this->preinit_ = new Block(NULL, this->location());
3098   return this->preinit_;
3099 }
3100
3101 // Add a statement to be run before the initialization expression.
3102
3103 void
3104 Variable::add_preinit_statement(Statement* s)
3105 {
3106   Block* b = this->preinit_block();
3107   b->add_statement(s);
3108   b->set_end_location(s->location());
3109 }
3110
3111 // In an assignment which sets a variable to a tuple of EXPR, return
3112 // the type of the first element of the tuple.
3113
3114 Type*
3115 Variable::type_from_tuple(Expression* expr, bool report_error) const
3116 {
3117   if (expr->map_index_expression() != NULL)
3118     return expr->map_index_expression()->get_map_type()->val_type();
3119   else if (expr->receive_expression() != NULL)
3120     {
3121       Expression* channel = expr->receive_expression()->channel();
3122       return channel->type()->channel_type()->element_type();
3123     }
3124   else
3125     {
3126       if (report_error)
3127         error_at(this->location(), "invalid tuple definition");
3128       return Type::make_error_type();
3129     }
3130 }
3131
3132 // Given EXPR used in a range clause, return either the index type or
3133 // the value type of the range, depending upon GET_INDEX_TYPE.
3134
3135 Type*
3136 Variable::type_from_range(Expression* expr, bool get_index_type,
3137                           bool report_error) const
3138 {
3139   Type* t = expr->type();
3140   if (t->array_type() != NULL
3141       || (t->points_to() != NULL
3142           && t->points_to()->array_type() != NULL
3143           && !t->points_to()->is_open_array_type()))
3144     {
3145       if (get_index_type)
3146         return Type::lookup_integer_type("int");
3147       else
3148         return t->deref()->array_type()->element_type();
3149     }
3150   else if (t->is_string_type())
3151     return Type::lookup_integer_type("int");
3152   else if (t->map_type() != NULL)
3153     {
3154       if (get_index_type)
3155         return t->map_type()->key_type();
3156       else
3157         return t->map_type()->val_type();
3158     }
3159   else if (t->channel_type() != NULL)
3160     {
3161       if (get_index_type)
3162         return t->channel_type()->element_type();
3163       else
3164         {
3165           if (report_error)
3166             error_at(this->location(),
3167                      "invalid definition of value variable for channel range");
3168           return Type::make_error_type();
3169         }
3170     }
3171   else
3172     {
3173       if (report_error)
3174         error_at(this->location(), "invalid type for range clause");
3175       return Type::make_error_type();
3176     }
3177 }
3178
3179 // EXPR should be a channel.  Return the channel's element type.
3180
3181 Type*
3182 Variable::type_from_chan_element(Expression* expr, bool report_error) const
3183 {
3184   Type* t = expr->type();
3185   if (t->channel_type() != NULL)
3186     return t->channel_type()->element_type();
3187   else
3188     {
3189       if (report_error)
3190         error_at(this->location(), "expected channel");
3191       return Type::make_error_type();
3192     }
3193 }
3194
3195 // Return the type of the Variable.  This may be called before
3196 // Variable::determine_type is called, which means that we may need to
3197 // get the type from the initializer.  FIXME: If we combine lowering
3198 // with type determination, then this should be unnecessary.
3199
3200 Type*
3201 Variable::type() const
3202 {
3203   // A variable in a type switch with a nil case will have the wrong
3204   // type here.  This gets fixed up in determine_type, below.
3205   Type* type = this->type_;
3206   Expression* init = this->init_;
3207   if (this->is_type_switch_var_
3208       && this->type_->is_nil_constant_as_type())
3209     {
3210       Type_guard_expression* tge = this->init_->type_guard_expression();
3211       gcc_assert(tge != NULL);
3212       init = tge->expr();
3213       type = NULL;
3214     }
3215
3216   if (type != NULL)
3217     return type;
3218   else if (this->type_from_init_tuple_)
3219     return this->type_from_tuple(init, false);
3220   else if (this->type_from_range_index_ || this->type_from_range_value_)
3221     return this->type_from_range(init, this->type_from_range_index_, false);
3222   else if (this->type_from_chan_element_)
3223     return this->type_from_chan_element(init, false);
3224   else
3225     {
3226       gcc_assert(init != NULL);
3227       type = init->type();
3228       gcc_assert(type != NULL);
3229
3230       // Variables should not have abstract types.
3231       if (type->is_abstract())
3232         type = type->make_non_abstract_type();
3233
3234       if (type->is_void_type())
3235         type = Type::make_error_type();
3236
3237       return type;
3238     }
3239 }
3240
3241 // Set the type if necessary.
3242
3243 void
3244 Variable::determine_type()
3245 {
3246   // A variable in a type switch with a nil case will have the wrong
3247   // type here.  It will have an initializer which is a type guard.
3248   // We want to initialize it to the value without the type guard, and
3249   // use the type of that value as well.
3250   if (this->is_type_switch_var_ && this->type_->is_nil_constant_as_type())
3251     {
3252       Type_guard_expression* tge = this->init_->type_guard_expression();
3253       gcc_assert(tge != NULL);
3254       this->type_ = NULL;
3255       this->init_ = tge->expr();
3256     }
3257
3258   if (this->init_ == NULL)
3259     gcc_assert(this->type_ != NULL && !this->type_->is_abstract());
3260   else if (this->type_from_init_tuple_)
3261     {
3262       Expression *init = this->init_;
3263       init->determine_type_no_context();
3264       this->type_ = this->type_from_tuple(init, true);
3265       this->init_ = NULL;
3266     }
3267   else if (this->type_from_range_index_ || this->type_from_range_value_)
3268     {
3269       Expression* init = this->init_;
3270       init->determine_type_no_context();
3271       this->type_ = this->type_from_range(init, this->type_from_range_index_,
3272                                           true);
3273       this->init_ = NULL;
3274     }
3275   else
3276     {
3277       // type_from_chan_element_ should have been cleared during
3278       // lowering.
3279       gcc_assert(!this->type_from_chan_element_);
3280
3281       Type_context context(this->type_, false);
3282       this->init_->determine_type(&context);
3283       if (this->type_ == NULL)
3284         {
3285           Type* type = this->init_->type();
3286           gcc_assert(type != NULL);
3287           if (type->is_abstract())
3288             type = type->make_non_abstract_type();
3289
3290           if (type->is_void_type())
3291             {
3292               error_at(this->location_, "variable has no type");
3293               type = Type::make_error_type();
3294             }
3295           else if (type->is_nil_type())
3296             {
3297               error_at(this->location_, "variable defined to nil type");
3298               type = Type::make_error_type();
3299             }
3300           else if (type->is_call_multiple_result_type())
3301             {
3302               error_at(this->location_,
3303                        "single variable set to multiple value function call");
3304               type = Type::make_error_type();
3305             }
3306
3307           this->type_ = type;
3308         }
3309     }
3310 }
3311
3312 // Export the variable
3313
3314 void
3315 Variable::export_var(Export* exp, const std::string& name) const
3316 {
3317   gcc_assert(this->is_global_);
3318   exp->write_c_string("var ");
3319   exp->write_string(name);
3320   exp->write_c_string(" ");
3321   exp->write_type(this->type());
3322   exp->write_c_string(";\n");
3323 }
3324
3325 // Import a variable.
3326
3327 void
3328 Variable::import_var(Import* imp, std::string* pname, Type** ptype)
3329 {
3330   imp->require_c_string("var ");
3331   *pname = imp->read_identifier();
3332   imp->require_c_string(" ");
3333   *ptype = imp->read_type();
3334   imp->require_c_string(";\n");
3335 }
3336
3337 // Class Named_constant.
3338
3339 // Traverse the initializer expression.
3340
3341 int
3342 Named_constant::traverse_expression(Traverse* traverse)
3343 {
3344   return Expression::traverse(&this->expr_, traverse);
3345 }
3346
3347 // Determine the type of the constant.
3348
3349 void
3350 Named_constant::determine_type()
3351 {
3352   if (this->type_ != NULL)
3353     {
3354       Type_context context(this->type_, false);
3355       this->expr_->determine_type(&context);
3356     }
3357   else
3358     {
3359       // A constant may have an abstract type.
3360       Type_context context(NULL, true);
3361       this->expr_->determine_type(&context);
3362       this->type_ = this->expr_->type();
3363       gcc_assert(this->type_ != NULL);
3364     }
3365 }
3366
3367 // Indicate that we found and reported an error for this constant.
3368
3369 void
3370 Named_constant::set_error()
3371 {
3372   this->type_ = Type::make_error_type();
3373   this->expr_ = Expression::make_error(this->location_);
3374 }
3375
3376 // Export a constant.
3377
3378 void
3379 Named_constant::export_const(Export* exp, const std::string& name) const
3380 {
3381   exp->write_c_string("const ");
3382   exp->write_string(name);
3383   exp->write_c_string(" ");
3384   if (!this->type_->is_abstract())
3385     {
3386       exp->write_type(this->type_);
3387       exp->write_c_string(" ");
3388     }
3389   exp->write_c_string("= ");
3390   this->expr()->export_expression(exp);
3391   exp->write_c_string(";\n");
3392 }
3393
3394 // Import a constant.
3395
3396 void
3397 Named_constant::import_const(Import* imp, std::string* pname, Type** ptype,
3398                              Expression** pexpr)
3399 {
3400   imp->require_c_string("const ");
3401   *pname = imp->read_identifier();
3402   imp->require_c_string(" ");
3403   if (imp->peek_char() == '=')
3404     *ptype = NULL;
3405   else
3406     {
3407       *ptype = imp->read_type();
3408       imp->require_c_string(" ");
3409     }
3410   imp->require_c_string("= ");
3411   *pexpr = Expression::import_expression(imp);
3412   imp->require_c_string(";\n");
3413 }
3414
3415 // Add a method.
3416
3417 Named_object*
3418 Type_declaration::add_method(const std::string& name, Function* function)
3419 {
3420   Named_object* ret = Named_object::make_function(name, NULL, function);
3421   this->methods_.push_back(ret);
3422   return ret;
3423 }
3424
3425 // Add a method declaration.
3426
3427 Named_object*
3428 Type_declaration::add_method_declaration(const std::string&  name,
3429                                          Function_type* type,
3430                                          source_location location)
3431 {
3432   Named_object* ret = Named_object::make_function_declaration(name, NULL, type,
3433                                                               location);
3434   this->methods_.push_back(ret);
3435   return ret;
3436 }
3437
3438 // Return whether any methods ere defined.
3439
3440 bool
3441 Type_declaration::has_methods() const
3442 {
3443   return !this->methods_.empty();
3444 }
3445
3446 // Define methods for the real type.
3447
3448 void
3449 Type_declaration::define_methods(Named_type* nt)
3450 {
3451   for (Methods::const_iterator p = this->methods_.begin();
3452        p != this->methods_.end();
3453        ++p)
3454     nt->add_existing_method(*p);
3455 }
3456
3457 // We are using the type.  Return true if we should issue a warning.
3458
3459 bool
3460 Type_declaration::using_type()
3461 {
3462   bool ret = !this->issued_warning_;
3463   this->issued_warning_ = true;
3464   return ret;
3465 }
3466
3467 // Class Unknown_name.
3468
3469 // Set the real named object.
3470
3471 void
3472 Unknown_name::set_real_named_object(Named_object* no)
3473 {
3474   gcc_assert(this->real_named_object_ == NULL);
3475   gcc_assert(!no->is_unknown());
3476   this->real_named_object_ = no;
3477 }
3478
3479 // Class Named_object.
3480
3481 Named_object::Named_object(const std::string& name,
3482                            const Package* package,
3483                            Classification classification)
3484   : name_(name), package_(package), classification_(classification),
3485     tree_(NULL)
3486 {
3487   if (Gogo::is_sink_name(name))
3488     gcc_assert(classification == NAMED_OBJECT_SINK);
3489 }
3490
3491 // Make an unknown name.  This is used by the parser.  The name must
3492 // be resolved later.  Unknown names are only added in the current
3493 // package.
3494
3495 Named_object*
3496 Named_object::make_unknown_name(const std::string& name,
3497                                 source_location location)
3498 {
3499   Named_object* named_object = new Named_object(name, NULL,
3500                                                 NAMED_OBJECT_UNKNOWN);
3501   Unknown_name* value = new Unknown_name(location);
3502   named_object->u_.unknown_value = value;
3503   return named_object;
3504 }
3505
3506 // Make a constant.
3507
3508 Named_object*
3509 Named_object::make_constant(const Typed_identifier& tid,
3510                             const Package* package, Expression* expr,
3511                             int iota_value)
3512 {
3513   Named_object* named_object = new Named_object(tid.name(), package,
3514                                                 NAMED_OBJECT_CONST);
3515   Named_constant* named_constant = new Named_constant(tid.type(), expr,
3516                                                       iota_value,
3517                                                       tid.location());
3518   named_object->u_.const_value = named_constant;
3519   return named_object;
3520 }
3521
3522 // Make a named type.
3523
3524 Named_object*
3525 Named_object::make_type(const std::string& name, const Package* package,
3526                         Type* type, source_location location)
3527 {
3528   Named_object* named_object = new Named_object(name, package,
3529                                                 NAMED_OBJECT_TYPE);
3530   Named_type* named_type = Type::make_named_type(named_object, type, location);
3531   named_object->u_.type_value = named_type;
3532   return named_object;
3533 }
3534
3535 // Make a type declaration.
3536
3537 Named_object*
3538 Named_object::make_type_declaration(const std::string& name,
3539                                     const Package* package,
3540                                     source_location location)
3541 {
3542   Named_object* named_object = new Named_object(name, package,
3543                                                 NAMED_OBJECT_TYPE_DECLARATION);
3544   Type_declaration* type_declaration = new Type_declaration(location);
3545   named_object->u_.type_declaration = type_declaration;
3546   return named_object;
3547 }
3548
3549 // Make a variable.
3550
3551 Named_object*
3552 Named_object::make_variable(const std::string& name, const Package* package,
3553                             Variable* variable)
3554 {
3555   Named_object* named_object = new Named_object(name, package,
3556                                                 NAMED_OBJECT_VAR);
3557   named_object->u_.var_value = variable;
3558   return named_object;
3559 }
3560
3561 // Make a result variable.
3562
3563 Named_object*
3564 Named_object::make_result_variable(const std::string& name,
3565                                    Result_variable* result)
3566 {
3567   Named_object* named_object = new Named_object(name, NULL,
3568                                                 NAMED_OBJECT_RESULT_VAR);
3569   named_object->u_.result_var_value = result;
3570   return named_object;
3571 }
3572
3573 // Make a sink.  This is used for the special blank identifier _.
3574
3575 Named_object*
3576 Named_object::make_sink()
3577 {
3578   return new Named_object("_", NULL, NAMED_OBJECT_SINK);
3579 }
3580
3581 // Make a named function.
3582
3583 Named_object*
3584 Named_object::make_function(const std::string& name, const Package* package,
3585                             Function* function)
3586 {
3587   Named_object* named_object = new Named_object(name, package,
3588                                                 NAMED_OBJECT_FUNC);
3589   named_object->u_.func_value = function;
3590   return named_object;
3591 }
3592
3593 // Make a function declaration.
3594
3595 Named_object*
3596 Named_object::make_function_declaration(const std::string& name,
3597                                         const Package* package,
3598                                         Function_type* fntype,
3599                                         source_location location)
3600 {
3601   Named_object* named_object = new Named_object(name, package,
3602                                                 NAMED_OBJECT_FUNC_DECLARATION);
3603   Function_declaration *func_decl = new Function_declaration(fntype, location);
3604   named_object->u_.func_declaration_value = func_decl;
3605   return named_object;
3606 }
3607
3608 // Make a package.
3609
3610 Named_object*
3611 Named_object::make_package(const std::string& alias, Package* package)
3612 {
3613   Named_object* named_object = new Named_object(alias, NULL,
3614                                                 NAMED_OBJECT_PACKAGE);
3615   named_object->u_.package_value = package;
3616   return named_object;
3617 }
3618
3619 // Return the name to use in an error message.
3620
3621 std::string
3622 Named_object::message_name() const
3623 {
3624   if (this->package_ == NULL)
3625     return Gogo::message_name(this->name_);
3626   std::string ret = Gogo::message_name(this->package_->name());
3627   ret += '.';
3628   ret += Gogo::message_name(this->name_);
3629   return ret;
3630 }
3631
3632 // Set the type when a declaration is defined.
3633
3634 void
3635 Named_object::set_type_value(Named_type* named_type)
3636 {
3637   gcc_assert(this->classification_ == NAMED_OBJECT_TYPE_DECLARATION);
3638   Type_declaration* td = this->u_.type_declaration;
3639   td->define_methods(named_type);
3640   Named_object* in_function = td->in_function();
3641   if (in_function != NULL)
3642     named_type->set_in_function(in_function);
3643   delete td;
3644   this->classification_ = NAMED_OBJECT_TYPE;
3645   this->u_.type_value = named_type;
3646 }
3647
3648 // Define a function which was previously declared.
3649
3650 void
3651 Named_object::set_function_value(Function* function)
3652 {
3653   gcc_assert(this->classification_ == NAMED_OBJECT_FUNC_DECLARATION);
3654   this->classification_ = NAMED_OBJECT_FUNC;
3655   // FIXME: We should free the old value.
3656   this->u_.func_value = function;
3657 }
3658
3659 // Return the location of a named object.
3660
3661 source_location
3662 Named_object::location() const
3663 {
3664   switch (this->classification_)
3665     {
3666     default:
3667     case NAMED_OBJECT_UNINITIALIZED:
3668       gcc_unreachable();
3669
3670     case NAMED_OBJECT_UNKNOWN:
3671       return this->unknown_value()->location();
3672
3673     case NAMED_OBJECT_CONST:
3674       return this->const_value()->location();
3675
3676     case NAMED_OBJECT_TYPE:
3677       return this->type_value()->location();
3678
3679     case NAMED_OBJECT_TYPE_DECLARATION:
3680       return this->type_declaration_value()->location();
3681
3682     case NAMED_OBJECT_VAR:
3683       return this->var_value()->location();
3684
3685     case NAMED_OBJECT_RESULT_VAR:
3686       return this->result_var_value()->function()->location();
3687
3688     case NAMED_OBJECT_SINK:
3689       gcc_unreachable();
3690
3691     case NAMED_OBJECT_FUNC:
3692       return this->func_value()->location();
3693
3694     case NAMED_OBJECT_FUNC_DECLARATION:
3695       return this->func_declaration_value()->location();
3696
3697     case NAMED_OBJECT_PACKAGE:
3698       return this->package_value()->location();
3699     }
3700 }
3701
3702 // Export a named object.
3703
3704 void
3705 Named_object::export_named_object(Export* exp) const
3706 {
3707   switch (this->classification_)
3708     {
3709     default:
3710     case NAMED_OBJECT_UNINITIALIZED:
3711     case NAMED_OBJECT_UNKNOWN:
3712       gcc_unreachable();
3713
3714     case NAMED_OBJECT_CONST:
3715       this->const_value()->export_const(exp, this->name_);
3716       break;
3717
3718     case NAMED_OBJECT_TYPE:
3719       this->type_value()->export_named_type(exp, this->name_);
3720       break;
3721
3722     case NAMED_OBJECT_TYPE_DECLARATION:
3723       error_at(this->type_declaration_value()->location(),
3724                "attempt to export %<%s%> which was declared but not defined",
3725                this->message_name().c_str());
3726       break;
3727
3728     case NAMED_OBJECT_FUNC_DECLARATION:
3729       this->func_declaration_value()->export_func(exp, this->name_);
3730       break;
3731
3732     case NAMED_OBJECT_VAR:
3733       this->var_value()->export_var(exp, this->name_);
3734       break;
3735
3736     case NAMED_OBJECT_RESULT_VAR:
3737     case NAMED_OBJECT_SINK:
3738       gcc_unreachable();
3739
3740     case NAMED_OBJECT_FUNC:
3741       this->func_value()->export_func(exp, this->name_);
3742       break;
3743     }
3744 }
3745
3746 // Class Bindings.
3747
3748 Bindings::Bindings(Bindings* enclosing)
3749   : enclosing_(enclosing), named_objects_(), bindings_()
3750 {
3751 }
3752
3753 // Clear imports.
3754
3755 void
3756 Bindings::clear_file_scope()
3757 {
3758   Contour::iterator p = this->bindings_.begin();
3759   while (p != this->bindings_.end())
3760     {
3761       bool keep;
3762       if (p->second->package() != NULL)
3763         keep = false;
3764       else if (p->second->is_package())
3765         keep = false;
3766       else if (p->second->is_function()
3767                && !p->second->func_value()->type()->is_method()
3768                && Gogo::unpack_hidden_name(p->second->name()) == "init")
3769         keep = false;
3770       else
3771         keep = true;
3772
3773       if (keep)
3774         ++p;
3775       else
3776         p = this->bindings_.erase(p);
3777     }
3778 }
3779
3780 // Look up a symbol.
3781
3782 Named_object*
3783 Bindings::lookup(const std::string& name) const
3784 {
3785   Contour::const_iterator p = this->bindings_.find(name);
3786   if (p != this->bindings_.end())
3787     return p->second->resolve();
3788   else if (this->enclosing_ != NULL)
3789     return this->enclosing_->lookup(name);
3790   else
3791     return NULL;
3792 }
3793
3794 // Look up a symbol locally.
3795
3796 Named_object*
3797 Bindings::lookup_local(const std::string& name) const
3798 {
3799   Contour::const_iterator p = this->bindings_.find(name);
3800   if (p == this->bindings_.end())
3801     return NULL;
3802   return p->second;
3803 }
3804
3805 // Remove an object from a set of bindings.  This is used for a
3806 // special case in thunks for functions which call recover.
3807
3808 void
3809 Bindings::remove_binding(Named_object* no)
3810 {
3811   Contour::iterator pb = this->bindings_.find(no->name());
3812   gcc_assert(pb != this->bindings_.end());
3813   this->bindings_.erase(pb);
3814   for (std::vector<Named_object*>::iterator pn = this->named_objects_.begin();
3815        pn != this->named_objects_.end();
3816        ++pn)
3817     {
3818       if (*pn == no)
3819         {
3820           this->named_objects_.erase(pn);
3821           return;
3822         }
3823     }
3824   gcc_unreachable();
3825 }
3826
3827 // Add a method to the list of objects.  This is not added to the
3828 // lookup table.  This is so that we have a single list of objects
3829 // declared at the top level, which we walk through when it's time to
3830 // convert to trees.
3831
3832 void
3833 Bindings::add_method(Named_object* method)
3834 {
3835   this->named_objects_.push_back(method);
3836 }
3837
3838 // Add a generic Named_object to a Contour.
3839
3840 Named_object*
3841 Bindings::add_named_object_to_contour(Contour* contour,
3842                                       Named_object* named_object)
3843 {
3844   gcc_assert(named_object == named_object->resolve());
3845   const std::string& name(named_object->name());
3846   gcc_assert(!Gogo::is_sink_name(name));
3847
3848   std::pair<Contour::iterator, bool> ins =
3849     contour->insert(std::make_pair(name, named_object));
3850   if (!ins.second)
3851     {
3852       // The name was already there.
3853       if (named_object->package() != NULL
3854           && ins.first->second->package() == named_object->package()
3855           && (ins.first->second->classification()
3856               == named_object->classification()))
3857         {
3858           // This is a second import of the same object.
3859           return ins.first->second;
3860         }
3861       ins.first->second = this->new_definition(ins.first->second,
3862                                                named_object);
3863       return ins.first->second;
3864     }
3865   else
3866     {
3867       // Don't push declarations on the list.  We push them on when
3868       // and if we find the definitions.  That way we genericize the
3869       // functions in order.
3870       if (!named_object->is_type_declaration()
3871           && !named_object->is_function_declaration()
3872           && !named_object->is_unknown())
3873         this->named_objects_.push_back(named_object);
3874       return named_object;
3875     }
3876 }
3877
3878 // We had an existing named object OLD_OBJECT, and we've seen a new
3879 // one NEW_OBJECT with the same name.  FIXME: This does not free the
3880 // new object when we don't need it.
3881
3882 Named_object*
3883 Bindings::new_definition(Named_object* old_object, Named_object* new_object)
3884 {
3885   std::string reason;
3886   switch (old_object->classification())
3887     {
3888     default:
3889     case Named_object::NAMED_OBJECT_UNINITIALIZED:
3890       gcc_unreachable();
3891
3892     case Named_object::NAMED_OBJECT_UNKNOWN:
3893       {
3894         Named_object* real = old_object->unknown_value()->real_named_object();
3895         if (real != NULL)
3896           return this->new_definition(real, new_object);
3897         gcc_assert(!new_object->is_unknown());
3898         old_object->unknown_value()->set_real_named_object(new_object);
3899         if (!new_object->is_type_declaration()
3900             && !new_object->is_function_declaration())
3901           this->named_objects_.push_back(new_object);
3902         return new_object;
3903       }
3904
3905     case Named_object::NAMED_OBJECT_CONST:
3906       break;
3907
3908     case Named_object::NAMED_OBJECT_TYPE:
3909       if (new_object->is_type_declaration())
3910         return old_object;
3911       break;
3912
3913     case Named_object::NAMED_OBJECT_TYPE_DECLARATION:
3914       if (new_object->is_type_declaration())
3915         return old_object;
3916       if (new_object->is_type())
3917         {
3918           old_object->set_type_value(new_object->type_value());
3919           new_object->type_value()->set_named_object(old_object);
3920           this->named_objects_.push_back(old_object);
3921           return old_object;
3922         }
3923       break;
3924
3925     case Named_object::NAMED_OBJECT_VAR:
3926     case Named_object::NAMED_OBJECT_RESULT_VAR:
3927       break;
3928
3929     case Named_object::NAMED_OBJECT_SINK:
3930       gcc_unreachable();
3931
3932     case Named_object::NAMED_OBJECT_FUNC:
3933       if (new_object->is_function_declaration())
3934         {
3935           if (!new_object->func_declaration_value()->asm_name().empty())
3936             sorry("__asm__ for function definitions");
3937           Function_type* old_type = old_object->func_value()->type();
3938           Function_type* new_type =
3939             new_object->func_declaration_value()->type();
3940           if (old_type->is_valid_redeclaration(new_type, &reason))
3941             return old_object;
3942         }
3943       break;
3944
3945     case Named_object::NAMED_OBJECT_FUNC_DECLARATION:
3946       {
3947         Function_type* old_type = old_object->func_declaration_value()->type();
3948         if (new_object->is_function_declaration())
3949           {
3950             Function_type* new_type =
3951               new_object->func_declaration_value()->type();
3952             if (old_type->is_valid_redeclaration(new_type, &reason))
3953               return old_object;
3954           }
3955         if (new_object->is_function())
3956           {
3957             Function_type* new_type = new_object->func_value()->type();
3958             if (old_type->is_valid_redeclaration(new_type, &reason))
3959               {
3960                 if (!old_object->func_declaration_value()->asm_name().empty())
3961                   sorry("__asm__ for function definitions");
3962                 old_object->set_function_value(new_object->func_value());
3963                 this->named_objects_.push_back(old_object);
3964                 return old_object;
3965               }
3966           }
3967       }
3968       break;
3969
3970     case Named_object::NAMED_OBJECT_PACKAGE:
3971       if (new_object->is_package()
3972           && (old_object->package_value()->name()
3973               == new_object->package_value()->name()))
3974         return old_object;
3975
3976       break;
3977     }
3978
3979   std::string n = old_object->message_name();
3980   if (reason.empty())
3981     error_at(new_object->location(), "redefinition of %qs", n.c_str());
3982   else
3983     error_at(new_object->location(), "redefinition of %qs: %s", n.c_str(),
3984              reason.c_str());
3985
3986   inform(old_object->location(), "previous definition of %qs was here",
3987          n.c_str());
3988
3989   return old_object;
3990 }
3991
3992 // Add a named type.
3993
3994 Named_object*
3995 Bindings::add_named_type(Named_type* named_type)
3996 {
3997   return this->add_named_object(named_type->named_object());
3998 }
3999
4000 // Add a function.
4001
4002 Named_object*
4003 Bindings::add_function(const std::string& name, const Package* package,
4004                        Function* function)
4005 {
4006   return this->add_named_object(Named_object::make_function(name, package,
4007                                                             function));
4008 }
4009
4010 // Add a function declaration.
4011
4012 Named_object*
4013 Bindings::add_function_declaration(const std::string& name,
4014                                    const Package* package,
4015                                    Function_type* type,
4016                                    source_location location)
4017 {
4018   Named_object* no = Named_object::make_function_declaration(name, package,
4019                                                              type, location);
4020   return this->add_named_object(no);
4021 }
4022
4023 // Define a type which was previously declared.
4024
4025 void
4026 Bindings::define_type(Named_object* no, Named_type* type)
4027 {
4028   no->set_type_value(type);
4029   this->named_objects_.push_back(no);
4030 }
4031
4032 // Traverse bindings.
4033
4034 int
4035 Bindings::traverse(Traverse* traverse, bool is_global)
4036 {
4037   unsigned int traverse_mask = traverse->traverse_mask();
4038
4039   // We don't use an iterator because we permit the traversal to add
4040   // new global objects.
4041   for (size_t i = 0; i < this->named_objects_.size(); ++i)
4042     {
4043       Named_object* p = this->named_objects_[i];
4044       switch (p->classification())
4045         {
4046         case Named_object::NAMED_OBJECT_CONST:
4047           if ((traverse_mask & Traverse::traverse_constants) != 0)
4048             {
4049               if (traverse->constant(p, is_global) == TRAVERSE_EXIT)
4050                 return TRAVERSE_EXIT;
4051             }
4052           if ((traverse_mask & Traverse::traverse_types) != 0
4053               || (traverse_mask & Traverse::traverse_expressions) != 0)
4054             {
4055               Type* t = p->const_value()->type();
4056               if (t != NULL
4057                   && Type::traverse(t, traverse) == TRAVERSE_EXIT)
4058                 return TRAVERSE_EXIT;
4059             }
4060           if ((traverse_mask & Traverse::traverse_expressions) != 0)
4061             {
4062               if (p->const_value()->traverse_expression(traverse)
4063                   == TRAVERSE_EXIT)
4064                 return TRAVERSE_EXIT;
4065             }
4066           break;
4067
4068         case Named_object::NAMED_OBJECT_VAR:
4069         case Named_object::NAMED_OBJECT_RESULT_VAR:
4070           if ((traverse_mask & Traverse::traverse_variables) != 0)
4071             {
4072               if (traverse->variable(p) == TRAVERSE_EXIT)
4073                 return TRAVERSE_EXIT;
4074             }
4075           if (((traverse_mask & Traverse::traverse_types) != 0
4076                || (traverse_mask & Traverse::traverse_expressions) != 0)
4077               && (p->is_result_variable()
4078                   || p->var_value()->has_type()))
4079             {
4080               Type* t = (p->is_variable()
4081                          ? p->var_value()->type()
4082                          : p->result_var_value()->type());
4083               if (t != NULL
4084                   && Type::traverse(t, traverse) == TRAVERSE_EXIT)
4085                 return TRAVERSE_EXIT;
4086             }
4087           if (p->is_variable()
4088               && (traverse_mask & Traverse::traverse_expressions) != 0)
4089             {
4090               if (p->var_value()->traverse_expression(traverse)
4091                   == TRAVERSE_EXIT)
4092                 return TRAVERSE_EXIT;
4093             }
4094           break;
4095
4096         case Named_object::NAMED_OBJECT_FUNC:
4097           if ((traverse_mask & Traverse::traverse_functions) != 0)
4098             {
4099               int t = traverse->function(p);
4100               if (t == TRAVERSE_EXIT)
4101                 return TRAVERSE_EXIT;
4102               else if (t == TRAVERSE_SKIP_COMPONENTS)
4103                 break;
4104             }
4105
4106           if ((traverse_mask
4107                & (Traverse::traverse_variables
4108                   | Traverse::traverse_constants
4109                   | Traverse::traverse_functions
4110                   | Traverse::traverse_blocks
4111                   | Traverse::traverse_statements
4112                   | Traverse::traverse_expressions
4113                   | Traverse::traverse_types)) != 0)
4114             {
4115               if (p->func_value()->traverse(traverse) == TRAVERSE_EXIT)
4116                 return TRAVERSE_EXIT;
4117             }
4118           break;
4119
4120         case Named_object::NAMED_OBJECT_PACKAGE:
4121           // These are traversed in Gogo::traverse.
4122           gcc_assert(is_global);
4123           break;
4124
4125         case Named_object::NAMED_OBJECT_TYPE:
4126           if ((traverse_mask & Traverse::traverse_types) != 0
4127               || (traverse_mask & Traverse::traverse_expressions) != 0)
4128             {
4129               if (Type::traverse(p->type_value(), traverse) == TRAVERSE_EXIT)
4130                 return TRAVERSE_EXIT;
4131             }
4132           break;
4133
4134         case Named_object::NAMED_OBJECT_TYPE_DECLARATION:
4135         case Named_object::NAMED_OBJECT_FUNC_DECLARATION:
4136         case Named_object::NAMED_OBJECT_UNKNOWN:
4137           break;
4138
4139         case Named_object::NAMED_OBJECT_SINK:
4140         default:
4141           gcc_unreachable();
4142         }
4143     }
4144
4145   return TRAVERSE_CONTINUE;
4146 }
4147
4148 // Class Package.
4149
4150 Package::Package(const std::string& name, const std::string& unique_prefix,
4151                  source_location location)
4152   : name_(name), unique_prefix_(unique_prefix), bindings_(new Bindings(NULL)),
4153     priority_(0), location_(location), used_(false), is_imported_(false),
4154     uses_sink_alias_(false)
4155 {
4156   gcc_assert(!name.empty() && !unique_prefix.empty());
4157 }
4158
4159 // Set the priority.  We may see multiple priorities for an imported
4160 // package; we want to use the largest one.
4161
4162 void
4163 Package::set_priority(int priority)
4164 {
4165   if (priority > this->priority_)
4166     this->priority_ = priority;
4167 }
4168
4169 // Determine types of constants.  Everything else in a package
4170 // (variables, function declarations) should already have a fixed
4171 // type.  Constants may have abstract types.
4172
4173 void
4174 Package::determine_types()
4175 {
4176   Bindings* bindings = this->bindings_;
4177   for (Bindings::const_definitions_iterator p = bindings->begin_definitions();
4178        p != bindings->end_definitions();
4179        ++p)
4180     {
4181       if ((*p)->is_const())
4182         (*p)->const_value()->determine_type();
4183     }
4184 }
4185
4186 // Class Traverse.
4187
4188 // Destructor.
4189
4190 Traverse::~Traverse()
4191 {
4192   if (this->types_seen_ != NULL)
4193     delete this->types_seen_;
4194   if (this->expressions_seen_ != NULL)
4195     delete this->expressions_seen_;
4196 }
4197
4198 // Record that we are looking at a type, and return true if we have
4199 // already seen it.
4200
4201 bool
4202 Traverse::remember_type(const Type* type)
4203 {
4204   gcc_assert((this->traverse_mask() & traverse_types) != 0
4205              || (this->traverse_mask() & traverse_expressions) != 0);
4206   // We only have to remember named types, as they are the only ones
4207   // we can see multiple times in a traversal.
4208   if (type->classification() != Type::TYPE_NAMED)
4209     return false;
4210   if (this->types_seen_ == NULL)
4211     this->types_seen_ = new Types_seen();
4212   std::pair<Types_seen::iterator, bool> ins = this->types_seen_->insert(type);
4213   return !ins.second;
4214 }
4215
4216 // Record that we are looking at an expression, and return true if we
4217 // have already seen it.
4218
4219 bool
4220 Traverse::remember_expression(const Expression* expression)
4221 {
4222   gcc_assert((this->traverse_mask() & traverse_types) != 0
4223              || (this->traverse_mask() & traverse_expressions) != 0);
4224   if (this->expressions_seen_ == NULL)
4225     this->expressions_seen_ = new Expressions_seen();
4226   std::pair<Expressions_seen::iterator, bool> ins =
4227     this->expressions_seen_->insert(expression);
4228   return !ins.second;
4229 }
4230
4231 // The default versions of these functions should never be called: the
4232 // traversal mask indicates which functions may be called.
4233
4234 int
4235 Traverse::variable(Named_object*)
4236 {
4237   gcc_unreachable();
4238 }
4239
4240 int
4241 Traverse::constant(Named_object*, bool)
4242 {
4243   gcc_unreachable();
4244 }
4245
4246 int
4247 Traverse::function(Named_object*)
4248 {
4249   gcc_unreachable();
4250 }
4251
4252 int
4253 Traverse::block(Block*)
4254 {
4255   gcc_unreachable();
4256 }
4257
4258 int
4259 Traverse::statement(Block*, size_t*, Statement*)
4260 {
4261   gcc_unreachable();
4262 }
4263
4264 int
4265 Traverse::expression(Expression**)
4266 {
4267   gcc_unreachable();
4268 }
4269
4270 int
4271 Traverse::type(Type*)
4272 {
4273   gcc_unreachable();
4274 }