LCOV - code coverage report
Current view: top level - include/llvm/ADT - PointerSumType.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 11 11 100.0 %
Date: 2017-09-14 15:23:50 Functions: 0 0 -
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/PointerSumType.h --------------------------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #ifndef LLVM_ADT_POINTERSUMTYPE_H
      11             : #define LLVM_ADT_POINTERSUMTYPE_H
      12             : 
      13             : #include "llvm/ADT/DenseMapInfo.h"
      14             : #include "llvm/Support/Compiler.h"
      15             : #include "llvm/Support/PointerLikeTypeTraits.h"
      16             : 
      17             : namespace llvm {
      18             : 
      19             : /// A compile time pair of an integer tag and the pointer-like type which it
      20             : /// indexes within a sum type. Also allows the user to specify a particular
      21             : /// traits class for pointer types with custom behavior such as over-aligned
      22             : /// allocation.
      23             : template <uintptr_t N, typename PointerArgT,
      24             :           typename TraitsArgT = PointerLikeTypeTraits<PointerArgT>>
      25             : struct PointerSumTypeMember {
      26             :   enum { Tag = N };
      27             :   typedef PointerArgT PointerT;
      28             :   typedef TraitsArgT TraitsT;
      29             : };
      30             : 
      31             : namespace detail {
      32             : 
      33             : template <typename TagT, typename... MemberTs>
      34             : struct PointerSumTypeHelper;
      35             : 
      36             : }
      37             : 
      38             : /// A sum type over pointer-like types.
      39             : ///
      40             : /// This is a normal tagged union across pointer-like types that uses the low
      41             : /// bits of the pointers to store the tag.
      42             : ///
      43             : /// Each member of the sum type is specified by passing a \c
      44             : /// PointerSumTypeMember specialization in the variadic member argument list.
      45             : /// This allows the user to control the particular tag value associated with
      46             : /// a particular type, use the same type for multiple different tags, and
      47             : /// customize the pointer-like traits used for a particular member. Note that
      48             : /// these *must* be specializations of \c PointerSumTypeMember, no other type
      49             : /// will suffice, even if it provides a compatible interface.
      50             : ///
      51             : /// This type implements all of the comparison operators and even hash table
      52             : /// support by comparing the underlying storage of the pointer values. It
      53             : /// doesn't support delegating to particular members for comparisons.
      54             : ///
      55             : /// It also default constructs to a zero tag with a null pointer, whatever that
      56             : /// would be. This means that the zero value for the tag type is significant
      57             : /// and may be desirable to set to a state that is particularly desirable to
      58             : /// default construct.
      59             : ///
      60             : /// There is no support for constructing or accessing with a dynamic tag as
      61             : /// that would fundamentally violate the type safety provided by the sum type.
      62             : template <typename TagT, typename... MemberTs> class PointerSumType {
      63             :   uintptr_t Value;
      64             : 
      65             :   typedef detail::PointerSumTypeHelper<TagT, MemberTs...> HelperT;
      66             : 
      67             : public:
      68     7745359 :   PointerSumType() : Value(0) {}
      69             : 
      70             :   /// A typed constructor for a specific tagged member of the sum type.
      71             :   template <TagT N>
      72             :   static PointerSumType
      73             :   create(typename HelperT::template Lookup<N>::PointerT Pointer) {
      74     5210630 :     PointerSumType Result;
      75     5210630 :     void *V = HelperT::template Lookup<N>::TraitsT::getAsVoidPointer(Pointer);
      76             :     assert((reinterpret_cast<uintptr_t>(V) & HelperT::TagMask) == 0 &&
      77             :            "Pointer is insufficiently aligned to store the discriminant!");
      78     5210630 :     Result.Value = reinterpret_cast<uintptr_t>(V) | N;
      79             :     return Result;
      80             :   }
      81             : 
      82    12555413 :   TagT getTag() const { return static_cast<TagT>(Value & HelperT::TagMask); }
      83             : 
      84    14104305 :   template <TagT N> bool is() const { return N == getTag(); }
      85             : 
      86             :   template <TagT N> typename HelperT::template Lookup<N>::PointerT get() const {
      87          35 :     void *P = is<N>() ? getImpl() : nullptr;
      88          27 :     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(P);
      89             :   }
      90             : 
      91             :   template <TagT N>
      92             :   typename HelperT::template Lookup<N>::PointerT cast() const {
      93             :     assert(is<N>() && "This instance has a different active member.");
      94    10050987 :     return HelperT::template Lookup<N>::TraitsT::getFromVoidPointer(getImpl());
      95             :   }
      96             : 
      97           5 :   explicit operator bool() const { return Value & HelperT::PointerMask; }
      98             :   bool operator==(const PointerSumType &R) const { return Value == R.Value; }
      99             :   bool operator!=(const PointerSumType &R) const { return Value != R.Value; }
     100             :   bool operator<(const PointerSumType &R) const { return Value < R.Value; }
     101             :   bool operator>(const PointerSumType &R) const { return Value > R.Value; }
     102             :   bool operator<=(const PointerSumType &R) const { return Value <= R.Value; }
     103             :   bool operator>=(const PointerSumType &R) const { return Value >= R.Value; }
     104             : 
     105             :   uintptr_t getOpaqueValue() const { return Value; }
     106             : 
     107             : protected:
     108             :   void *getImpl() const {
     109     4264929 :     return reinterpret_cast<void *>(Value & HelperT::PointerMask);
     110             :   }
     111             : };
     112             : 
     113             : namespace detail {
     114             : 
     115             : /// A helper template for implementing \c PointerSumType. It provides fast
     116             : /// compile-time lookup of the member from a particular tag value, along with
     117             : /// useful constants and compile time checking infrastructure..
     118             : template <typename TagT, typename... MemberTs>
     119             : struct PointerSumTypeHelper : MemberTs... {
     120             :   // First we use a trick to allow quickly looking up information about
     121             :   // a particular member of the sum type. This works because we arranged to
     122             :   // have this type derive from all of the member type templates. We can select
     123             :   // the matching member for a tag using type deduction during overload
     124             :   // resolution.
     125             :   template <TagT N, typename PointerT, typename TraitsT>
     126             :   static PointerSumTypeMember<N, PointerT, TraitsT>
     127             :   LookupOverload(PointerSumTypeMember<N, PointerT, TraitsT> *);
     128             :   template <TagT N> static void LookupOverload(...);
     129             :   template <TagT N> struct Lookup {
     130             :     // Compute a particular member type by resolving the lookup helper ovorload.
     131             :     typedef decltype(LookupOverload<N>(
     132             :         static_cast<PointerSumTypeHelper *>(nullptr))) MemberT;
     133             : 
     134             :     /// The Nth member's pointer type.
     135             :     typedef typename MemberT::PointerT PointerT;
     136             : 
     137             :     /// The Nth member's traits type.
     138             :     typedef typename MemberT::TraitsT TraitsT;
     139             :   };
     140             : 
     141             :   // Next we need to compute the number of bits available for the discriminant
     142             :   // by taking the min of the bits available for each member. Much of this
     143             :   // would be amazingly easier with good constexpr support.
     144             :   template <uintptr_t V, uintptr_t... Vs>
     145             :   struct Min : std::integral_constant<
     146             :                    uintptr_t, (V < Min<Vs...>::value ? V : Min<Vs...>::value)> {
     147             :   };
     148             :   template <uintptr_t V>
     149             :   struct Min<V> : std::integral_constant<uintptr_t, V> {};
     150             :   enum { NumTagBits = Min<MemberTs::TraitsT::NumLowBitsAvailable...>::value };
     151             : 
     152             :   // Also compute the smallest discriminant and various masks for convenience.
     153             :   enum : uint64_t {
     154             :     MinTag = Min<MemberTs::Tag...>::value,
     155             :     PointerMask = static_cast<uint64_t>(-1) << NumTagBits,
     156             :     TagMask = ~PointerMask
     157             :   };
     158             : 
     159             :   // Finally we need a recursive template to do static checks of each
     160             :   // member.
     161             :   template <typename MemberT, typename... InnerMemberTs>
     162             :   struct Checker : Checker<InnerMemberTs...> {
     163             :     static_assert(MemberT::Tag < (1 << NumTagBits),
     164             :                   "This discriminant value requires too many bits!");
     165             :   };
     166             :   template <typename MemberT> struct Checker<MemberT> : std::true_type {
     167             :     static_assert(MemberT::Tag < (1 << NumTagBits),
     168             :                   "This discriminant value requires too many bits!");
     169             :   };
     170             :   static_assert(Checker<MemberTs...>::value,
     171             :                 "Each member must pass the checker.");
     172             : };
     173             : 
     174             : }
     175             : 
     176             : // Teach DenseMap how to use PointerSumTypes as keys.
     177             : template <typename TagT, typename... MemberTs>
     178             : struct DenseMapInfo<PointerSumType<TagT, MemberTs...>> {
     179             :   typedef PointerSumType<TagT, MemberTs...> SumType;
     180             : 
     181             :   typedef detail::PointerSumTypeHelper<TagT, MemberTs...> HelperT;
     182             :   enum { SomeTag = HelperT::MinTag };
     183             :   typedef typename HelperT::template Lookup<HelperT::MinTag>::PointerT
     184             :       SomePointerT;
     185             :   typedef DenseMapInfo<SomePointerT> SomePointerInfo;
     186             : 
     187             :   static inline SumType getEmptyKey() {
     188             :     return SumType::create<SomeTag>(SomePointerInfo::getEmptyKey());
     189             :   }
     190             :   static inline SumType getTombstoneKey() {
     191             :     return SumType::create<SomeTag>(
     192             :         SomePointerInfo::getTombstoneKey());
     193             :   }
     194             :   static unsigned getHashValue(const SumType &Arg) {
     195             :     uintptr_t OpaqueValue = Arg.getOpaqueValue();
     196             :     return DenseMapInfo<uintptr_t>::getHashValue(OpaqueValue);
     197             :   }
     198             :   static bool isEqual(const SumType &LHS, const SumType &RHS) {
     199             :     return LHS == RHS;
     200             :   }
     201             : };
     202             : 
     203             : }
     204             : 
     205             : #endif

Generated by: LCOV version 1.13