[wasm] Check for duplicate export names

src/wasm/module-decoder.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/wasm/module-decoder.h"
 
 #include "src/base/functional.h"
 #include "src/base/platform/platform.h"
 #include "src/macro-assembler.h"
 #include "src/objects.h"
@@ skipping 340 matching lines @@
 
             module->export_table.push_back({0,    // func_index
                                             0,    // name_offset
                                             0});  // name_length
             WasmExport* exp = &module->export_table.back();
 
             WasmFunction* func;
             exp->func_index = consume_func_index(module, &func);
             exp->name_offset = consume_string(&exp->name_length, true);
           }
+          // Check for duplicate exports.
+          if (ok() && module->export_table.size() > 1) {
+            std::vector<WasmExport> sorted_exports(module->export_table);

[titzer, 2016/06/14 22:52:06]

Can't we just do that when creating the exports object itself? After all, JS
objects are just hashtables...

[Clemens Hammacher, 2016/06/15 07:48:09]

We cannot report a validation error at that stage, right?
We could ignore duplicate exports though. Is this what you want?
I think in the design docs it's not defined currently what should happen on
multiple exports with the same name.

[rossberg, 2016/06/15 08:37:16]

Yes, validation is required to flag it. You cannot defer it until instantiation.

+            const byte* base = start_;
+            auto cmp = [base](const WasmExport& a, const WasmExport& b) {
+              // Return true if a < b.
+              uint32_t len = a.name_length;
+              if (len != b.name_length) return len < b.name_length;
+              return memcmp(base + a.name_offset, base + b.name_offset, len) <
+                     0;
+            };
+            std::stable_sort(sorted_exports.begin(), sorted_exports.end(), cmp);

[rossberg, 2016/06/15 08:53:58]

Instead of sorting the whole thing, would it be faster to just put the names in
a multiset and check whether any has a count > 1?

[Clemens Hammacher, 2016/06/15 09:20:29]

AFAIK sorting and scanning is the fastest way to check for duplicates. Any
solution with set/map/multiset is also O(n*log(n)), but with a bigger constant
factor. Plus we need a hash function, and it's harder to report the *first*
duplicate export.
So is this really worth discussing? How many exports do we expect?

+            auto it = sorted_exports.begin();
+            WasmExport* last = &*it++;
+            for (auto end = sorted_exports.end(); it != end;
+                 last = &*it, ++it) {

[rossberg, 2016/06/15 08:53:58]

Nit: superfluous newline?

[Clemens Hammacher, 2016/06/15 09:20:29]

Nope, does not fit :)
But I will change it to "last = &*it++" before committing, so that it fits.

+              DCHECK(!cmp(*it, *last));
+              if (!cmp(*last, *it)) {
+                const byte* pc = start_ + it->name_offset;
+                error(pc, pc,
+                      "Duplicate export name '%.*s' for functions %d and %d",
+                      it->name_length, pc, last->func_index, it->func_index);
+                break;
+              }
+            }
+          }
           break;
         }
         case WasmSection::Code::Max:
           // Skip unknown sections.
           TRACE("Unknown section: '");
           for (uint32_t i = 0; i != string_length; ++i) {
             TRACE("%c", *(section_name_start + i));
           }
           TRACE("'\n");
           consume_bytes(section_length);
@@ skipping 387 matching lines @@
     return FunctionError("size > maximum function size");
   isolate->counters()->wasm_function_size_bytes()->AddSample(
       static_cast<int>(size));
   WasmFunction* function = new WasmFunction();
   ModuleDecoder decoder(zone, function_start, function_end, kWasmOrigin);
   return decoder.DecodeSingleFunction(module_env, function);
 }
 }  // namespace wasm
 }  // namespace internal
 }  // namespace v8