Subzero: Remove IceString.

src/IceStringPool.h

Index: src/IceStringPool.h
diff --git a/src/IceStringPool.h b/src/IceStringPool.h
new file mode 100644
index 0000000000000000000000000000000000000000..bd1c76b6da69da6a3a2a19294aa359b54c0faaca
--- /dev/null
+++ b/src/IceStringPool.h
@@ -0,0 +1,164 @@
+//===- subzero/src/IceStringPool.h - String pooling -------------*- C++ -*-===//
+//
+//                        The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief Defines unique pooled strings with short unique IDs.  This makes
+/// hashing, equality testing, and ordered comparison faster, and avoids a lot
+/// of memory allocation compared to directly using std::string.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICESTRINGPOOL_H
+#define SUBZERO_SRC_ICESTRINGPOOL_H
+
+#include <cstdint> // uintptr_t
+#include <string>
+
+namespace Ice {
+
+class StringPool {
+  StringPool(const StringPool &) = delete;
+  StringPool &operator=(const StringPool &) = delete;
+
+public:
+  using IDType = uintptr_t;
+
+  StringPool() = default;
+  ~StringPool() = default;
+  IDType getNewID() {
+    // TODO(stichnot): Make it so that the GlobalString ctor doesn't have to
+    // grab the lock, and instead does an atomic increment of NextID.
+    auto NewID = NextID;
+    NextID += IDIncrement;
+    return NewID;
+  }
+  IDType getOrAddString(const std::string &Value) {
+    auto Iter = StringToId.find(Value);
+    if (Iter == StringToId.end()) {
+      auto *NewStr = new std::string(Value);
+      auto ID = reinterpret_cast<IDType>(NewStr);
+      assert(StringToId.find(Value) == StringToId.end());

[John, 2016/03/29 14:23:16]

why the assert?

[Jim Stichnoth, 2016/03/29 21:40:50]

I think this was left over from an earlier implementation where the expression
wasn't guaranteed to be true.  Removed.

+      StringToId[Value].reset(NewStr);
+      return ID;
+    }
+    return reinterpret_cast<IDType>(Iter->second.get());
+  }
+  void dump(Ostream &Str) {

[John, 2016/03/29 14:23:16]

const

[Jim Stichnoth, 2016/03/29 21:40:50]

Done.

+    if (StringToId.empty())
+      return;
+    Str << "String pool (NumStrings=" << StringToId.size()
+        << " NumIDs=" << ((NextID - FirstID) / IDIncrement) << "):";
+    for (auto &Tuple : StringToId) {

[John, 2016/03/29 14:23:16]

const auto &

[Jim Stichnoth, 2016/03/29 21:40:50]

Done.

+      Str << " " << Tuple.first;
+    }
+    Str << "\n";
+  }
+
+private:
+  static constexpr IDType FirstID = 1;
+  static constexpr IDType IDIncrement = 2;
+  IDType NextID = FirstID;
+  std::unordered_map<std::string, std::unique_ptr<std::string>> StringToId;
+};
+
+template <typename Traits> class StringID {
+public:
+  using IDType = StringPool::IDType;
+
+  StringID(const StringID &) = default;
+  StringID &operator=(const StringID &) = default;
+  // Create a default, invalid StringID.
+  StringID() = default;

[John, 2016/03/29 14:23:16]

I would declare ctors/assignment opers in the following order

StringID()
StringID(const StringID &) = default;
StringID &operator=(const StringID &) = default;

[Jim Stichnoth, 2016/03/29 21:40:50]

Done.

+  /// Create a unique StringID without an actual string, by grabbing the next
+  /// unique integral ID from the Owner.

[John, 2016/03/29 14:23:16]

The comment you added explain what the ctor does, but then, when you use the
class, we will see

StringID str(Ctx);

which is kinda meaningless, unless you're familiar with this code.

Consider using named constructors:

static StringID createUnbound(Owner) {}
static StringID createBound(Owner, Value) {}

sure, Bounc/Unbound are definitively not the best option, so feel free to rename
to something else. :)

[Jim Stichnoth, 2016/03/29 21:40:50]

Nice, done.

+  explicit StringID(const typename Traits::OwnerType *Owner)
+      : ID(Traits::getStrings(Owner)->getNewID()) {}
+  /// Create a unique StringID that holds an actual string, by fetching or
+  /// adding the string from the Owner's pool.
+  StringID(const typename Traits::OwnerType *Owner, const std::string &Value)
+      : ID(Traits::getStrings(Owner)->getOrAddString(Value)) {
+    assert(hasString());
+  }
+
+  static bool hasString(IDType ID) { return isValid(ID) && ((ID & 0x1) == 0); }

[John, 2016/03/29 14:23:16]

I am suspicious of static methods as they are often a sign of code smell. In
this case, there are two issues with this static:
1) There's a non-static version of it; and
2) the non-static version is the only caller of it.

Maybe remove the static instance?

hasString() also fails to convey (to me) what the method really does. how about
s/hasString/representsStdString/?

[Jim Stichnoth, 2016/03/29 21:40:50]

Done - using hasStdString().

+  bool hasString() const { return hasString(ID); }
+
+  IDType getID() const {
+    assert(isValid());
+    return ID;
+  }
+  const std::string &toString() const {
+    assert(hasString());

[John, 2016/03/29 14:23:16]

an assert here looks wrong -- if somehow toString() is invoked without a string
the program will silently cast an odd number to a pointer.

[Jim Stichnoth, 2016/03/29 21:40:50]

Done.

+    return *reinterpret_cast<std::string *>(ID);
+  }
+  std::string toStringOrEmpty() const {
+    if (hasString())
+      return toString();
+    return "";
+  }
+
+  bool operator==(const StringID &Other) const { return ID == Other.ID; }
+  bool operator!=(const StringID &Other) const { return !(*this == Other); }
+  bool operator<(const StringID &Other) const {
+    const bool ThisHasString = hasString();
+    const bool OtherHasString = Other.hasString();
+    // Do a normal string comparison if both have strings.
+    if (ThisHasString && OtherHasString)
+      return this->toString() < Other.toString();
+    // Use the ID as a tiebreaker if neither has a string.
+    if (!ThisHasString && !OtherHasString)
+      return ID < Other.ID;
+    // If exactly one has a string, then that one comes first.
+    assert(!OtherHasString);
+    return ThisHasString;
+  }
+
+private:
+  static constexpr IDType InvalidID = 0;
+  IDType ID = InvalidID;
+
+  static bool isValid(IDType ID) { return ID != InvalidID; }

[John, 2016/03/29 14:23:16]

same thing for the static method here.

[Jim Stichnoth, 2016/03/29 21:40:50]

Done.

+  bool isValid() const { return isValid(ID); }
+};
+
+struct GlobalStringPoolTraits {

[John, 2016/03/29 14:23:16]

I got to move this to IceDefs.h, but not to IceGlobalContext.h -- yet another
proof that IceDefs.h needs some **serious** refactoring. Ideally, IceDefs.h
would either die, or simply contain using foo = bar statements -- plus the llvm/
includes (and those should not appear anywhere else), and nothing else.

To accomplish this, you need to

/// IceDefs.h

#include "IceStringPool.h"

/* move the GlobalStringPoolTraits stuff there */

/// IceStringPool.h
#include "llvm/Support/raw_ostream.h"

#include <unordered_map> // please add this anyway -- include what you use!

and the s/Ostream/llvm::raw_ostream/g on this file (leave a TODO behind to
s/llvm::raw_ostream/Ostream/g once someone fixes IceDefs.h)

[Jim Stichnoth, 2016/03/29 21:40:49]

Left this alone, but added a TODO.

+  using OwnerType = GlobalContext;
+  static LockedPtr<StringPool> getStrings(const OwnerType *Owner);
+};
+
+using GlobalString = StringID<struct GlobalStringPoolTraits>;
+
+template <typename T>
+Ostream &operator<<(Ostream &Str, const StringID<T> &Name) {
+  return Str << Name.toString();
+}
+
+template <typename T>
+std::string operator+(const std::string &A, const StringID<T> &B) {
+  return A + B.toString();
+}
+
+template <typename T>
+std::string operator+(const StringID<T> &A, const std::string &B) {
+  return A.toString() + B;
+}
+
+} // end of namespace Ice
+
+namespace std {
+template <typename T> struct hash<Ice::StringID<T>> {
+  size_t operator()(const Ice::StringID<T> &Key) const {
+    if (Key.hasString())
+      return hash<std::string>()(Key.toString());
+    return hash<Ice::StringPool::IDType>()(Key.getID());
+  }
+};
+} // end of namespace std
+
+#endif // SUBZERO_SRC_ICESTRINGPOOL_H