third_party/wasm2c/src/generate-names.cc

   1 /*
   2  * Copyright 2016 WebAssembly Community Group participants
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "wabt/generate-names.h"
  18
  19 #include <cassert>
  20 #include <cstdio>
  21 #include <string>
  22 #include <vector>
  23
  24 #include "wabt/cast.h"
  25 #include "wabt/expr-visitor.h"
  26 #include "wabt/ir.h"
  27
  28 namespace wabt {
  29
  30 namespace {
  31
  32 class NameGenerator : public ExprVisitor::DelegateNop {
  33  public:
  34   NameGenerator(NameOpts opts);
  35
  36   Result VisitModule(Module* module);
  37
  38   // Implementation of ExprVisitor::DelegateNop.
  39   Result BeginBlockExpr(BlockExpr* expr) override;
  40   Result BeginTryExpr(TryExpr* expr) override;
  41   Result BeginLoopExpr(LoopExpr* expr) override;
  42   Result BeginIfExpr(IfExpr* expr) override;
  43
  44  private:
  45   static bool HasName(const std::string& str);
  46
  47   // Generate a name with the given prefix, followed by the index and
  48   // optionally a disambiguating number. If index == kInvalidIndex, the index
  49   // is not appended.
  50   void GenerateName(const char* prefix,
  51                     Index index,
  52                     unsigned disambiguator,
  53                     std::string* out_str);
  54
  55   // Like GenerateName, but only generates a name if |out_str| is empty.
  56   void MaybeGenerateName(const char* prefix, Index index, std::string* out_str);
  57
  58   // Generate a name via GenerateName and bind it to the given binding hash. If
  59   // the name already exists, the name will be disambiguated until it can be
  60   // added.
  61   void GenerateAndBindName(BindingHash* bindings,
  62                            const char* prefix,
  63                            Index index,
  64                            std::string* out_str);
  65
  66   // Like GenerateAndBindName, but only  generates a name if |out_str| is empty.
  67   void MaybeGenerateAndBindName(BindingHash* bindings,
  68                                 const char* prefix,
  69                                 Index index,
  70                                 std::string* out_str);
  71
  72   // Like MaybeGenerateAndBindName but uses the name directly, without
  73   // appending the index. If the name already exists, a disambiguating suffix
  74   // is added.
  75   void MaybeUseAndBindName(BindingHash* bindings,
  76                            const char* name,
  77                            Index index,
  78                            std::string* out_str);
  79
  80   void GenerateAndBindLocalNames(Func* func);
  81
  82   template <typename T>
  83   Result VisitAll(const std::vector<T*>& items,
  84                   Result (NameGenerator::*func)(Index, T*));
  85
  86   Result VisitFunc(Index func_index, Func* func);
  87   Result VisitGlobal(Index global_index, Global* global);
  88   Result VisitType(Index func_type_index, TypeEntry* type);
  89   Result VisitTable(Index table_index, Table* table);
  90   Result VisitMemory(Index memory_index, Memory* memory);
  91   Result VisitTag(Index tag_index, Tag* tag);
  92   Result VisitDataSegment(Index data_segment_index, DataSegment* data_segment);
  93   Result VisitElemSegment(Index elem_segment_index, ElemSegment* elem_segment);
  94   Result VisitImport(Import* import);
  95   Result VisitExport(Export* export_);
  96
  97   Module* module_ = nullptr;
  98   ExprVisitor visitor_;
  99   Index label_count_ = 0;
 100
 101   Index num_func_imports_ = 0;
 102   Index num_table_imports_ = 0;
 103   Index num_memory_imports_ = 0;
 104   Index num_global_imports_ = 0;
 105   Index num_tag_imports_ = 0;
 106
 107   NameOpts opts_;
 108 };
 109
 110 NameGenerator::NameGenerator(NameOpts opts) : visitor_(this), opts_(opts) {}
 111
 112 // static
 113 bool NameGenerator::HasName(const std::string& str) {
 114   return !str.empty();
 115 }
 116
 117 void NameGenerator::GenerateName(const char* prefix,
 118                                  Index index,
 119                                  unsigned disambiguator,
 120                                  std::string* str) {
 121   *str = "$";
 122   *str += prefix;
 123   if (index != kInvalidIndex) {
 124     if (opts_ & NameOpts::AlphaNames) {
 125       // For params and locals, do not use a prefix char.
 126       if (!strcmp(prefix, "p") || !strcmp(prefix, "l")) {
 127         str->pop_back();
 128       } else {
 129         *str += '_';
 130       }
 131       *str += IndexToAlphaName(index);
 132     } else {
 133       *str += std::to_string(index);
 134     }
 135   }
 136   if (disambiguator != 0) {
 137     *str += '_' + std::to_string(disambiguator);
 138   }
 139 }
 140
 141 void NameGenerator::MaybeGenerateName(const char* prefix,
 142                                       Index index,
 143                                       std::string* str) {
 144   if (!HasName(*str)) {
 145     // There's no bindings hash, so the name can't be a duplicate. Therefore it
 146     // doesn't need a disambiguating number.
 147     GenerateName(prefix, index, 0, str);
 148   }
 149 }
 150
 151 void NameGenerator::GenerateAndBindName(BindingHash* bindings,
 152                                         const char* prefix,
 153                                         Index index,
 154                                         std::string* str) {
 155   unsigned disambiguator = 0;
 156   while (true) {
 157     GenerateName(prefix, index, disambiguator, str);
 158     if (bindings->find(*str) == bindings->end()) {
 159       bindings->emplace(*str, Binding(index));
 160       break;
 161     }
 162
 163     disambiguator++;
 164   }
 165 }
 166
 167 void NameGenerator::MaybeGenerateAndBindName(BindingHash* bindings,
 168                                              const char* prefix,
 169                                              Index index,
 170                                              std::string* str) {
 171   if (!HasName(*str)) {
 172     GenerateAndBindName(bindings, prefix, index, str);
 173   }
 174 }
 175
 176 void NameGenerator::MaybeUseAndBindName(BindingHash* bindings,
 177                                         const char* name,
 178                                         Index index,
 179                                         std::string* str) {
 180   if (!HasName(*str)) {
 181     unsigned disambiguator = 0;
 182     while (true) {
 183       GenerateName(name, kInvalidIndex, disambiguator, str);
 184       if (bindings->find(*str) == bindings->end()) {
 185         bindings->emplace(*str, Binding(index));
 186         break;
 187       }
 188
 189       disambiguator++;
 190     }
 191   }
 192 }
 193
 194 void NameGenerator::GenerateAndBindLocalNames(Func* func) {
 195   std::vector<std::string> index_to_name;
 196   MakeTypeBindingReverseMapping(func->GetNumParamsAndLocals(), func->bindings,
 197                                 &index_to_name);
 198   for (size_t i = 0; i < index_to_name.size(); ++i) {
 199     const std::string& old_name = index_to_name[i];
 200     if (!old_name.empty()) {
 201       continue;
 202     }
 203
 204     const char* prefix = i < func->GetNumParams() ? "p" : "l";
 205     std::string new_name;
 206     GenerateAndBindName(&func->bindings, prefix, i, &new_name);
 207     index_to_name[i] = new_name;
 208   }
 209 }
 210
 211 Result NameGenerator::BeginBlockExpr(BlockExpr* expr) {
 212   MaybeGenerateName("B", label_count_++, &expr->block.label);
 213   return Result::Ok;
 214 }
 215
 216 Result NameGenerator::BeginTryExpr(TryExpr* expr) {
 217   MaybeGenerateName("T", label_count_++, &expr->block.label);
 218   return Result::Ok;
 219 }
 220
 221 Result NameGenerator::BeginLoopExpr(LoopExpr* expr) {
 222   MaybeGenerateName("L", label_count_++, &expr->block.label);
 223   return Result::Ok;
 224 }
 225
 226 Result NameGenerator::BeginIfExpr(IfExpr* expr) {
 227   MaybeGenerateName("I", label_count_++, &expr->true_.label);
 228   return Result::Ok;
 229 }
 230
 231 Result NameGenerator::VisitFunc(Index func_index, Func* func) {
 232   MaybeGenerateAndBindName(&module_->func_bindings, "f", func_index,
 233                            &func->name);
 234   GenerateAndBindLocalNames(func);
 235
 236   label_count_ = 0;
 237   CHECK_RESULT(visitor_.VisitFunc(func));
 238   return Result::Ok;
 239 }
 240
 241 Result NameGenerator::VisitGlobal(Index global_index, Global* global) {
 242   MaybeGenerateAndBindName(&module_->global_bindings, "g", global_index,
 243                            &global->name);
 244   return Result::Ok;
 245 }
 246
 247 Result NameGenerator::VisitType(Index type_index, TypeEntry* type) {
 248   MaybeGenerateAndBindName(&module_->type_bindings, "t", type_index,
 249                            &type->name);
 250   return Result::Ok;
 251 }
 252
 253 Result NameGenerator::VisitTable(Index table_index, Table* table) {
 254   MaybeGenerateAndBindName(&module_->table_bindings, "T", table_index,
 255                            &table->name);
 256   return Result::Ok;
 257 }
 258
 259 Result NameGenerator::VisitMemory(Index memory_index, Memory* memory) {
 260   MaybeGenerateAndBindName(&module_->memory_bindings, "M", memory_index,
 261                            &memory->name);
 262   return Result::Ok;
 263 }
 264
 265 Result NameGenerator::VisitTag(Index tag_index, Tag* tag) {
 266   MaybeGenerateAndBindName(&module_->tag_bindings, "e", tag_index, &tag->name);
 267   return Result::Ok;
 268 }
 269
 270 Result NameGenerator::VisitDataSegment(Index data_segment_index,
 271                                        DataSegment* data_segment) {
 272   MaybeGenerateAndBindName(&module_->data_segment_bindings, "d",
 273                            data_segment_index, &data_segment->name);
 274   return Result::Ok;
 275 }
 276
 277 Result NameGenerator::VisitElemSegment(Index elem_segment_index,
 278                                        ElemSegment* elem_segment) {
 279   MaybeGenerateAndBindName(&module_->elem_segment_bindings, "e",
 280                            elem_segment_index, &elem_segment->name);
 281   return Result::Ok;
 282 }
 283
 284 Result NameGenerator::VisitImport(Import* import) {
 285   BindingHash* bindings = nullptr;
 286   std::string* name = nullptr;
 287   Index index = kInvalidIndex;
 288
 289   switch (import->kind()) {
 290     case ExternalKind::Func:
 291       if (auto* func_import = cast<FuncImport>(import)) {
 292         bindings = &module_->func_bindings;
 293         name = &func_import->func.name;
 294         index = num_func_imports_++;
 295       }
 296       break;
 297
 298     case ExternalKind::Table:
 299       if (auto* table_import = cast<TableImport>(import)) {
 300         bindings = &module_->table_bindings;
 301         name = &table_import->table.name;
 302         index = num_table_imports_++;
 303       }
 304       break;
 305
 306     case ExternalKind::Memory:
 307       if (auto* memory_import = cast<MemoryImport>(import)) {
 308         bindings = &module_->memory_bindings;
 309         name = &memory_import->memory.name;
 310         index = num_memory_imports_++;
 311       }
 312       break;
 313
 314     case ExternalKind::Global:
 315       if (auto* global_import = cast<GlobalImport>(import)) {
 316         bindings = &module_->global_bindings;
 317         name = &global_import->global.name;
 318         index = num_global_imports_++;
 319       }
 320       break;
 321
 322     case ExternalKind::Tag:
 323       if (auto* tag_import = cast<TagImport>(import)) {
 324         bindings = &module_->tag_bindings;
 325         name = &tag_import->tag.name;
 326         index = num_tag_imports_++;
 327       }
 328       break;
 329   }
 330
 331   if (bindings && name) {
 332     assert(index != kInvalidIndex);
 333     std::string new_name = import->module_name + '.' + import->field_name;
 334     MaybeUseAndBindName(bindings, new_name.c_str(), index, name);
 335   }
 336
 337   return Result::Ok;
 338 }
 339
 340 Result NameGenerator::VisitExport(Export* export_) {
 341   BindingHash* bindings = nullptr;
 342   std::string* name = nullptr;
 343   Index index = kInvalidIndex;
 344
 345   switch (export_->kind) {
 346     case ExternalKind::Func:
 347       if (Func* func = module_->GetFunc(export_->var)) {
 348         index = module_->GetFuncIndex(export_->var);
 349         bindings = &module_->func_bindings;
 350         name = &func->name;
 351       }
 352       break;
 353
 354     case ExternalKind::Table:
 355       if (Table* table = module_->GetTable(export_->var)) {
 356         index = module_->GetTableIndex(export_->var);
 357         bindings = &module_->table_bindings;
 358         name = &table->name;
 359       }
 360       break;
 361
 362     case ExternalKind::Memory:
 363       if (Memory* memory = module_->GetMemory(export_->var)) {
 364         index = module_->GetMemoryIndex(export_->var);
 365         bindings = &module_->memory_bindings;
 366         name = &memory->name;
 367       }
 368       break;
 369
 370     case ExternalKind::Global:
 371       if (Global* global = module_->GetGlobal(export_->var)) {
 372         index = module_->GetGlobalIndex(export_->var);
 373         bindings = &module_->global_bindings;
 374         name = &global->name;
 375       }
 376       break;
 377
 378     case ExternalKind::Tag:
 379       if (Tag* tag = module_->GetTag(export_->var)) {
 380         index = module_->GetTagIndex(export_->var);
 381         bindings = &module_->tag_bindings;
 382         name = &tag->name;
 383       }
 384       break;
 385   }
 386
 387   if (bindings && name) {
 388     MaybeUseAndBindName(bindings, export_->name.c_str(), index, name);
 389   }
 390
 391   return Result::Ok;
 392 }
 393
 394 template <typename T>
 395 Result NameGenerator::VisitAll(const std::vector<T*>& items,
 396                                Result (NameGenerator::*func)(Index, T*)) {
 397   for (Index i = 0; i < items.size(); ++i) {
 398     CHECK_RESULT((this->*func)(i, items[i]));
 399   }
 400   return Result::Ok;
 401 }
 402
 403 Result NameGenerator::VisitModule(Module* module) {
 404   module_ = module;
 405   // Visit imports and exports first to give better names, derived from the
 406   // import/export name.
 407   for (auto* import : module->imports) {
 408     CHECK_RESULT(VisitImport(import));
 409   }
 410   for (auto* export_ : module->exports) {
 411     CHECK_RESULT(VisitExport(export_));
 412   }
 413
 414   VisitAll(module->globals, &NameGenerator::VisitGlobal);
 415   VisitAll(module->types, &NameGenerator::VisitType);
 416   VisitAll(module->funcs, &NameGenerator::VisitFunc);
 417   VisitAll(module->tables, &NameGenerator::VisitTable);
 418   VisitAll(module->memories, &NameGenerator::VisitMemory);
 419   VisitAll(module->tags, &NameGenerator::VisitTag);
 420   VisitAll(module->data_segments, &NameGenerator::VisitDataSegment);
 421   VisitAll(module->elem_segments, &NameGenerator::VisitElemSegment);
 422   module_ = nullptr;
 423   return Result::Ok;
 424 }
 425
 426 }  // end anonymous namespace
 427
 428 Result GenerateNames(Module* module, NameOpts opts) {
 429   NameGenerator generator(opts);
 430   return generator.VisitModule(module);
 431 }
 432
 433 }  // namespace wabt