From 92b0cbdd9e2747c5cf6ecc546718d0ec0b1bc64b Mon Sep 17 00:00:00 2001
From: Thomas Lively <7121787+tlively@users.noreply.github.com>
Date: Tue, 18 May 2021 15:58:31 -0700
Subject: Remove Type ordering (#3793)

As found in #3682, the current implementation of type ordering is not correct,
and although the immediate issue would be easy to fix, I don't think the current
intended comparison algorithm is correct in the first place. Rather than try to
switch to using a correct algorithm (which I am not sure I know how to
implement, although I have an idea) this PR removes Type ordering entirely. In
places that used Type ordering with std::set or std::map because they require
deterministic iteration order, this PR uses InsertOrdered{Set,Map} instead.
---
 src/support/insert_ordered.h | 56 +++++++++++++++++++++++++++++++-------------
 1 file changed, 40 insertions(+), 16 deletions(-)

(limited to 'src/support/insert_ordered.h')

diff --git a/src/support/insert_ordered.h b/src/support/insert_ordered.h
index 5e3dec96b..d4905b945 100644
--- a/src/support/insert_ordered.h
+++ b/src/support/insert_ordered.h
@@ -83,24 +83,43 @@ template<typename T> struct InsertOrderedSet {
 // order that elements were added to the map (not in the order
 // of operator<(Key, Key))
 template<typename Key, typename T> struct InsertOrderedMap {
-  std::unordered_map<Key, typename std::list<std::pair<Key, T>>::iterator> Map;
-  std::list<std::pair<Key, T>> List;
+  std::unordered_map<Key, typename std::list<std::pair<const Key, T>>::iterator>
+    Map;
+  std::list<std::pair<const Key, T>> List;
+
+  typedef typename std::list<std::pair<const Key, T>>::iterator iterator;
+  iterator begin() { return List.begin(); }
+  iterator end() { return List.end(); }
+
+  typedef
+    typename std::list<std::pair<const Key, T>>::const_iterator const_iterator;
+  const_iterator begin() const { return List.begin(); }
+  const_iterator end() const { return List.end(); }
+
+  std::pair<iterator, bool> insert(std::pair<const Key, T>& kv) {
+    // Try inserting with a placeholder list iterator.
+    auto inserted = Map.insert({kv.first, List.end()});
+    if (inserted.second) {
+      // This is a new item; insert it in the list and update the iterator.
+      List.push_back(kv);
+      inserted.first->second = std::prev(List.end());
+    }
+    return {inserted.first->second, inserted.second};
+  }
 
   T& operator[](const Key& k) {
+    std::pair<const Key, T> kv = {k, {}};
+    return insert(kv).first->second;
+  }
+
+  iterator find(const Key& k) {
     auto it = Map.find(k);
     if (it == Map.end()) {
-      List.push_back(std::make_pair(k, T()));
-      auto e = --List.end();
-      Map.insert(std::make_pair(k, e));
-      return e->second;
+      return end();
     }
-    return it->second->second;
+    return it->second;
   }
 
-  typedef typename std::list<std::pair<Key, T>>::iterator iterator;
-  iterator begin() { return List.begin(); }
-  iterator end() { return List.end(); }
-
   void erase(const Key& k) {
     auto it = Map.find(k);
     if (it != Map.end()) {
@@ -126,14 +145,19 @@ template<typename Key, typename T> struct InsertOrderedMap {
   size_t count(const Key& k) const { return Map.count(k); }
 
   InsertOrderedMap() = default;
-  InsertOrderedMap(InsertOrderedMap& other) {
-    // TODO, watch out for iterators.
-    WASM_UNREACHABLE("unimp");
+  InsertOrderedMap(const InsertOrderedMap& other) {
+    for (auto kv : other) {
+      insert(kv);
+    }
   }
   InsertOrderedMap& operator=(const InsertOrderedMap& other) {
-    // TODO, watch out for iterators.
-    WASM_UNREACHABLE("unimp");
+    if (this != &other) {
+      this->~InsertOrderedMap();
+      new (this) InsertOrderedMap<Key, T>(other);
+    }
+    return *this;
   }
+
   bool operator==(const InsertOrderedMap& other) {
     return Map == other.Map && List == other.List;
   }
-- 
cgit v1.2.3