[ADT] Add a sum type abstraction for pointer-like types.

[chandlerc]

Summary

This is a much more general and powerful form of PointerUnion. It
provides a reasonably complete sum type (from type theory) for
pointer-like types. It has several significant advantages over the
existing PointerUnion infrastructure:

1. It allows more than two pointer types to participate without awkward nesting structures.
2. It directly exposes the tag so that it is convenient to write switches over the possible members.
3. It can re-use the same type for multiple tag values, something that has been worked around by either abusing PointerIntPair or defining nonce types and doing unsafe pointer casting.
4. It supports customization of the PointerLikeTypeTraits used for specific member types. This means it could (in theory) be used even with types that are over-aligned on allocation to expose larger numbers of bits to the tag.

All in all, I think it is at least complimentary to the existing
infrastructure, and a strict improvement for some use cases.

[chandlerc]

You can see an example usage in http://reviews.llvm.org/D15845

[chandlerc]

Ping...

[craig.topper]

include/llvm/ADT/PointerSumType.h

176 ↗

(On Diff #43844)

Should this say PointerSumType instead of PointerUnion?

[chandlerc]

Er, canceling ping as Justin already replied with delightful comments and I
just missed it. =D

[chandlerc]

include/llvm/ADT/PointerSumType.h

176 ↗

(On Diff #43844)

Yep, good catch, will fix before i land it.

llvm/trunk/include/llvm/ADT/PointerSumType.h

+//===- llvm/ADT/PointerSumType.h --------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_POINTERSUMTYPE_H
+#define LLVM_ADT_POINTERSUMTYPE_H
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/PointerLikeTypeTraits.h"
+
+namespace llvm {
+
+/// A compile time pair of an integer tag and the pointer-like type which it
+/// indexes within a sum type. Also allows the user to specify a particular
+/// traits class for pointer types with custom behavior such as over-aligned
+/// allocation.
+template <uintptr_t N, typename PointerArgT,
+          typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
+struct PointerSumTypeMember {
+  enum { Tag = N };
+  typedef PointerArgT PointerT;
+  typedef TraitsArgT TraitsT;
+};
+
+namespace detail {
+
+template <typename TagT, typename... MemberTs>
+struct PointerSumTypeHelper;
+
+}
+
+/// A sum type over pointer-like types.
+///
+/// This is a normal tagged union across pointer-like types that uses the low
+/// bits of the pointers to store the tag.
+///
+/// Each member of the sum type is specified by passing a \c
+/// PointerSumTypeMember specialization in the variadic member argument list.
+/// This allows the user to control the particular tag value associated with
+/// a particular type, use the same type for multiple different tags, and
+/// customize the pointer-like traits used for a particular member. Note that
+/// these *must* be specializations of \c PointerSumTypeMember, no other type
+/// will suffice, even if it provides a compatible interface.
+///
+/// This type implements all of the comparison operators and even hash table
+/// support by comparing the underlying storage of the pointer values. It
+/// doesn't support delegating to particular members for comparisons.
+///
+/// It also default constructs to a zero tag with a null pointer, whatever that
+/// would be. This means that the zero value for the tag type is significant
+/// and may be desireable to set to a state that is particularly desirable to
+/// default construct.
+///
+/// There is no support for constructing or accessing with a dynamic tag as
+/// that would fundamentally violate the type safety provided by the sum type.
+template <typename TagT, typename... MemberTs> class PointerSumType {
+  uintptr_t Value;
+
+  typedef detail::PointerSumTypeHelper<TagT, MemberTs...> HelperT;
+
+public:
+  PointerSumType() : Value(0) {}
+
+  /// A typed constructor for a specific tagged member of the sum type.
+  template <TagT N>
+  static PointerSumType
+  create(typename HelperT::template Lookup<N>::PointerT Pointer) {
+    PointerSumType Result;
+    void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
+    assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
+           "Pointer is insufficiently aligned to store the discriminant!");
+    Result.Value = reinterpret_cast<uintptr_t>(V) | N;
+    return Result;
+  }
+
+  TagT getTag() const { return static_cast<TagT>(Value & HelperT::TagMask); }
+
+  template <TagT N> bool is() const { return N == getTag(); }
+
+  template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
+    void *P = is<N>() ? getImpl() : nullptr;
+    return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
+  }
+
+  template <TagT N>
+  typename HelperT::template Lookup<N>::PointerT cast() const {
+    assert(is<N>() && "This instance has a different active member.");
+    return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(getImpl());
+  }
+
+  operator bool() const { return Value & HelperT::PointerMask; }
+  bool operator==(const PointerSumType &R) const { return Value == R.Value; }
+  bool operator!=(const PointerSumType &R) const { return Value != R.Value; }
+  bool operator<(const PointerSumType &R) const { return Value < R.Value; }
+  bool operator>(const PointerSumType &R) const { return Value > R.Value; }
+  bool operator<=(const PointerSumType &R) const { return Value <= R.Value; }
+  bool operator>=(const PointerSumType &R) const { return Value >= R.Value; }
+
+  uintptr_t getOpaqueValue() const { return Value; }
+
+protected:
+  void *getImpl() const {
+    return reinterpret_cast<void *>(Value & HelperT::PointerMask);
+  }
+};
+
+namespace detail {
+
+/// A helper template for implementing \c PointerSumType. It provides fast
+/// compile-time lookup of the member from a particular tag value, along with
+/// useful constants and compile time checking infrastructure..
+template <typename TagT, typename... MemberTs>
+struct PointerSumTypeHelper : MemberTs... {
+  // First we use a trick to allow quickly looking up information about
+  // a particular member of the sum type. This works because we arranged to
+  // have this type derive from all of the member type templates. We can select
+  // the matching member for a tag using type deduction during overload
+  // resolution.
+  template <TagT N, typename PointerT, typename TraitsT>
+  static PointerSumTypeMember<N, PointerT, TraitsT>
+  LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
+  template <TagT N> static void LookupOverload(...);
+  template <TagT N> struct Lookup {
+    // Compute a particular member type by resolving the lookup helper ovorload.
+    typedef decltype(LookupOverload<N>(
+        static_cast<PointerSumTypeHelper *>(nullptr))) MemberT;
+
+    /// The Nth member's pointer type.
+    typedef typename MemberT::PointerT PointerT;
+
+    /// The Nth member's traits type.
+    typedef typename MemberT::TraitsT TraitsT;
+  };
+
+  // Next we need to compute the number of bits available for the discriminant
+  // by taking the min of the bits available for each member. Much of this
+  // would be amazingly easier with good constexpr support.
+  template <uintptr_t V, uintptr_t... Vs>
+  struct Min : std::integral_constant<
+                   uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
+  };
+  template <uintptr_t V>
+  struct Min<V> : std::integral_constant<uintptr_t, V> {};
+  enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
+
+  // Also compute the smallest discriminant and various masks for convenience.
+  enum : uint64_t {
+    MinTag = Min<MemberTs::Tag...>::value,
+    PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
+    TagMask = ~PointerMask
+  };
+
+  // Finally we need a recursive template to do static checks of each
+  // member.
+  template <typename MemberT, typename... InnerMemberTs>
+  struct Checker : Checker<InnerMemberTs...> {
+    static_assert(MemberT::Tag < (1 << NumTagBits),
+                  "This discriminant value requires too many bits!");
+  };
+  template <typename MemberT> struct Checker<MemberT> : std::true_type {
+    static_assert(MemberT::Tag < (1 << NumTagBits),
+                  "This discriminant value requires too many bits!");
+  };
+  static_assert(Checker<MemberTs...>::value,
+                "Each member must pass the checker.");
+};
+
+}
+
+// Teach DenseMap how to use PointerSumTypes as keys.
+template <typename TagT, typename... MemberTs>
+struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
+  typedef PointerSumType<TagT, MemberTs...> SumType;
+
+  typedef detail::PointerSumTypeHelper<TagT, MemberTs...> HelperT;
+  enum { SomeTag = HelperT::MinTag };
+  typedef typename HelperT::template Lookup<HelperT::MinTag>::PointerT
+      SomePointerT;
+  typedef DenseMapInfo<SomePointerT> SomePointerInfo;
+
+  static inline SumType getEmptyKey() {
+    return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
+  }
+  static inline SumType getTombstoneKey() {
+    return SumType::create<SomeTag>(
+        SomePointerInfo::getTombstoneKey());
+  }
+  static unsigned getHashValue(const SumType &Arg) {
+    uintptr_t OpaqueValue = Arg.getOpaqueValue();
+    return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
+  }
+  static bool isEqual(const SumType &LHS, const SumType &RHS) {
+    return LHS == RHS;
+  }
+};
+
+}
+
+#endif

llvm/trunk/unittests/ADT/CMakeLists.txt

set(ADTSources
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   MakeUniqueTest.cpp
   MapVectorTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerIntPairTest.cpp
+  PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp

llvm/trunk/unittests/ADT/PointerSumTypeTest.cpp

+//===- llvm/unittest/ADT/PointerSumTypeTest.cpp ---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/PointerSumType.h"
+using namespace llvm;
+
+namespace {
+
+struct PointerSumTypeTest : public testing::Test {
+  enum Kinds { Float, Int1, Int2 };
+  float f;
+  int i1, i2;
+
+  typedef PointerSumType<Kinds, PointerSumTypeMember<Float, float *>,
+                         PointerSumTypeMember<Int1, int *>,
+                         PointerSumTypeMember<Int2, int *>>
+      SumType;
+  SumType a, b, c, n;
+
+  PointerSumTypeTest()
+      : f(3.14f), i1(42), i2(-1), a(SumType::create<Float>(&f)),
+        b(SumType::create<Int1>(&i1)), c(SumType::create<Int2>(&i2)), n() {}
+};
+
+TEST_F(PointerSumTypeTest, NullTest) {
+  EXPECT_TRUE(a);
+  EXPECT_TRUE(b);
+  EXPECT_TRUE(c);
+  EXPECT_FALSE(n);
+}
+
+TEST_F(PointerSumTypeTest, GetTag) {
+  EXPECT_EQ(Float, a.getTag());
+  EXPECT_EQ(Int1, b.getTag());
+  EXPECT_EQ(Int2, c.getTag());
+  EXPECT_EQ((Kinds)0, n.getTag());
+}
+
+TEST_F(PointerSumTypeTest, Is) {
+  EXPECT_TRUE(a.is<Float>());
+  EXPECT_FALSE(a.is<Int1>());
+  EXPECT_FALSE(a.is<Int2>());
+  EXPECT_FALSE(b.is<Float>());
+  EXPECT_TRUE(b.is<Int1>());
+  EXPECT_FALSE(b.is<Int2>());
+  EXPECT_FALSE(c.is<Float>());
+  EXPECT_FALSE(c.is<Int1>());
+  EXPECT_TRUE(c.is<Int2>());
+}
+
+TEST_F(PointerSumTypeTest, Get) {
+  EXPECT_EQ(&f, a.get<Float>());
+  EXPECT_EQ(nullptr, a.get<Int1>());
+  EXPECT_EQ(nullptr, a.get<Int2>());
+  EXPECT_EQ(nullptr, b.get<Float>());
+  EXPECT_EQ(&i1, b.get<Int1>());
+  EXPECT_EQ(nullptr, b.get<Int2>());
+  EXPECT_EQ(nullptr, c.get<Float>());
+  EXPECT_EQ(nullptr, c.get<Int1>());
+  EXPECT_EQ(&i2, c.get<Int2>());
+
+  // Note that we can use .get even on a null sum type. It just always produces
+  // a null pointer, even if one of the discriminants is null.
+  EXPECT_EQ(nullptr, n.get<Float>());
+  EXPECT_EQ(nullptr, n.get<Int1>());
+  EXPECT_EQ(nullptr, n.get<Int2>());
+}
+
+TEST_F(PointerSumTypeTest, Cast) {
+  EXPECT_EQ(&f, a.cast<Float>());
+  EXPECT_EQ(&i1, b.cast<Int1>());
+  EXPECT_EQ(&i2, c.cast<Int2>());
+}
+
+TEST_F(PointerSumTypeTest, Assignment) {
+  b = SumType::create<Int2>(&i2);
+  EXPECT_EQ(nullptr, b.get<Float>());
+  EXPECT_EQ(nullptr, b.get<Int1>());
+  EXPECT_EQ(&i2, b.get<Int2>());
+
+  b = SumType::create<Int2>(&i1);
+  EXPECT_EQ(nullptr, b.get<Float>());
+  EXPECT_EQ(nullptr, b.get<Int1>());
+  EXPECT_EQ(&i1, b.get<Int2>());
+
+  float Local = 1.616f;
+  b = SumType::create<Float>(&Local);
+  EXPECT_EQ(&Local, b.get<Float>());
+  EXPECT_EQ(nullptr, b.get<Int1>());
+  EXPECT_EQ(nullptr, b.get<Int2>());
+
+  n = SumType::create<Int1>(&i2);
+  EXPECT_TRUE(n);
+  EXPECT_EQ(nullptr, n.get<Float>());
+  EXPECT_EQ(&i2, n.get<Int1>());
+  EXPECT_EQ(nullptr, n.get<Int2>());
+
+  n = SumType::create<Float>(nullptr);
+  EXPECT_FALSE(n);
+  EXPECT_EQ(nullptr, n.get<Float>());
+  EXPECT_EQ(nullptr, n.get<Int1>());
+  EXPECT_EQ(nullptr, n.get<Int2>());
+}
+
+
+} // end anonymous namespace