am 31195f0b: Merge "Update aosp/master llvm for rebase to r233350"

* commit '31195f0bdca6ee2a5e72d07edf13e1d81206d949':
  Update aosp/master llvm for rebase to r233350

1 files changed, 74 insertions, 96 deletions

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 3c6f58c..87026f0 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -142,13 +142,13 @@ public:
     iterator RItr = RHS.begin(), REnd = RHS.end();
 
     while (LItr != LEnd && RItr != REnd) {
-      if (*LItr == *RItr) {
+      if (&*LItr == &*RItr) {
         LItr.skipSubTree();
         RItr.skipSubTree();
         continue;
       }
 
-      if (!LItr->isElementEqual(*RItr))
+      if (!LItr->isElementEqual(&*RItr))
         return false;
 
       ++LItr;
@@ -293,8 +293,8 @@ private:
     height = h;
   }
 
-  static inline
-  uint32_t computeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
+  static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
+                                value_type_ref V) {
     uint32_t digest = 0;
 
     if (L)
@@ -311,7 +311,7 @@ private:
     return digest;
   }
 
-  inline uint32_t computeDigest() {
+  uint32_t computeDigest() {
     // Check the lowest bit to determine if digest has actually been
     // pre-computed.
     if (hasCachedDigest())
@@ -429,9 +429,7 @@ protected:
   value_type_ref  getValue(TreeTy* T) const { return T->value; }
 
   // Make sure the index is not the Tombstone or Entry key of the DenseMap.
-  static inline unsigned maskCacheIndex(unsigned I) {
-    return (I & ~0x02);
-  }
+  static unsigned maskCacheIndex(unsigned I) { return (I & ~0x02); }
 
   unsigned incrementHeight(TreeTy* L, TreeTy* R) const {
     unsigned hl = getHeight(L);
@@ -444,7 +442,7 @@ protected:
                                      typename TreeTy::iterator& TE) {
     typename TreeTy::iterator I = T->begin(), E = T->end();
     for ( ; I!=E ; ++I, ++TI) {
-      if (TI == TE || !I->isElementEqual(*TI))
+      if (TI == TE || !I->isElementEqual(&*TI))
         return false;
     }
     return true;
@@ -647,24 +645,26 @@ public:
 //===----------------------------------------------------------------------===//
 
 template <typename ImutInfo>
-class ImutAVLTreeGenericIterator {
+class ImutAVLTreeGenericIterator
+    : public std::iterator<std::bidirectional_iterator_tag,
+                           ImutAVLTree<ImutInfo>> {
   SmallVector<uintptr_t,20> stack;
 public:
   enum VisitFlag { VisitedNone=0x0, VisitedLeft=0x1, VisitedRight=0x3,
                    Flags=0x3 };
 
   typedef ImutAVLTree<ImutInfo> TreeTy;
-  typedef ImutAVLTreeGenericIterator<ImutInfo> _Self;
 
-  inline ImutAVLTreeGenericIterator() {}
-  inline ImutAVLTreeGenericIterator(const TreeTy* Root) {
+  ImutAVLTreeGenericIterator() {}
+  ImutAVLTreeGenericIterator(const TreeTy *Root) {
     if (Root) stack.push_back(reinterpret_cast<uintptr_t>(Root));
   }
 
-  TreeTy* operator*() const {
+  TreeTy &operator*() const {
     assert(!stack.empty());
-    return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
+    return *reinterpret_cast<TreeTy *>(stack.back() & ~Flags);
   }
+  TreeTy *operator->() const { return &*this; }
 
   uintptr_t getVisitState() const {
     assert(!stack.empty());
@@ -695,13 +695,15 @@ public:
     }
   }
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const ImutAVLTreeGenericIterator &x) const {
     return stack == x.stack;
   }
 
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const ImutAVLTreeGenericIterator &x) const {
+    return !(*this == x);
+  }
 
-  _Self& operator++() {
+  ImutAVLTreeGenericIterator &operator++() {
     assert(!stack.empty());
     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     assert(Current);
@@ -727,7 +729,7 @@ public:
     return *this;
   }
 
-  _Self& operator--() {
+  ImutAVLTreeGenericIterator &operator--() {
     assert(!stack.empty());
     TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
     assert(Current);
@@ -754,30 +756,34 @@ public:
 };
 
 template <typename ImutInfo>
-class ImutAVLTreeInOrderIterator {
+class ImutAVLTreeInOrderIterator
+    : public std::iterator<std::bidirectional_iterator_tag,
+                           ImutAVLTree<ImutInfo>> {
   typedef ImutAVLTreeGenericIterator<ImutInfo> InternalIteratorTy;
   InternalIteratorTy InternalItr;
 
 public:
   typedef ImutAVLTree<ImutInfo> TreeTy;
-  typedef ImutAVLTreeInOrderIterator<ImutInfo> _Self;
 
   ImutAVLTreeInOrderIterator(const TreeTy* Root) : InternalItr(Root) {
-    if (Root) operator++(); // Advance to first element.
+    if (Root)
+      ++*this; // Advance to first element.
   }
 
   ImutAVLTreeInOrderIterator() : InternalItr() {}
 
-  inline bool operator==(const _Self& x) const {
+  bool operator==(const ImutAVLTreeInOrderIterator &x) const {
     return InternalItr == x.InternalItr;
   }
 
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+  bool operator!=(const ImutAVLTreeInOrderIterator &x) const {
+    return !(*this == x);
+  }
 
-  inline TreeTy* operator*() const { return *InternalItr; }
-  inline TreeTy* operator->() const { return *InternalItr; }
+  TreeTy &operator*() const { return *InternalItr; }
+  TreeTy *operator->() const { return &*InternalItr; }
 
-  inline _Self& operator++() {
+  ImutAVLTreeInOrderIterator &operator++() {
     do ++InternalItr;
     while (!InternalItr.atEnd() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -785,7 +791,7 @@ public:
     return *this;
   }
 
-  inline _Self& operator--() {
+  ImutAVLTreeInOrderIterator &operator--() {
     do --InternalItr;
     while (!InternalItr.atBeginning() &&
            InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
@@ -793,7 +799,7 @@ public:
     return *this;
   }
 
-  inline void skipSubTree() {
+  void skipSubTree() {
     InternalItr.skipToParent();
 
     while (!InternalItr.atEnd() &&
@@ -802,6 +808,24 @@ public:
   }
 };
 
+/// Generic iterator that wraps a T::TreeTy::iterator and exposes
+/// iterator::getValue() on dereference.
+template <typename T>
+struct ImutAVLValueIterator
+    : iterator_adaptor_base<
+          ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
+          typename std::iterator_traits<
+              typename T::TreeTy::iterator>::iterator_category,
+          const typename T::value_type> {
+  ImutAVLValueIterator() = default;
+  explicit ImutAVLValueIterator(typename T::TreeTy *Tree)
+      : ImutAVLValueIterator::iterator_adaptor_base(Tree) {}
+
+  typename ImutAVLValueIterator::reference operator*() const {
+    return this->I->getValue();
+  }
+};
+
 //===----------------------------------------------------------------------===//
 // Trait classes for Profile information.
 //===----------------------------------------------------------------------===//
@@ -814,7 +838,7 @@ struct ImutProfileInfo {
   typedef const T  value_type;
   typedef const T& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     FoldingSetTrait<T>::Profile(X,ID);
   }
 };
@@ -825,7 +849,7 @@ struct ImutProfileInteger {
   typedef const T  value_type;
   typedef const T& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddInteger(X);
   }
 };
@@ -852,7 +876,7 @@ struct ImutProfileInfo<bool> {
   typedef const bool  value_type;
   typedef const bool& value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID& ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddBoolean(X);
   }
 };
@@ -865,7 +889,7 @@ struct ImutProfileInfo<T*> {
   typedef const T*   value_type;
   typedef value_type value_type_ref;
 
-  static inline void Profile(FoldingSetNodeID &ID, value_type_ref X) {
+  static void Profile(FoldingSetNodeID &ID, value_type_ref X) {
     ID.AddPointer(X);
   }
 };
@@ -890,18 +914,18 @@ struct ImutContainerInfo : public ImutProfileInfo<T> {
   typedef bool            data_type;
   typedef bool            data_type_ref;
 
-  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
-  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
+  static key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static data_type_ref DataOfValue(value_type_ref) { return true; }
 
-  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
+  static bool isEqual(key_type_ref LHS, key_type_ref RHS) {
     return std::equal_to<key_type>()(LHS,RHS);
   }
 
-  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
+  static bool isLess(key_type_ref LHS, key_type_ref RHS) {
     return std::less<key_type>()(LHS,RHS);
   }
 
-  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
+  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
 };
 
 /// ImutContainerInfo - Specialization for pointer values to treat pointers
@@ -916,18 +940,14 @@ struct ImutContainerInfo<T*> : public ImutProfileInfo<T*> {
   typedef bool            data_type;
   typedef bool            data_type_ref;
 
-  static inline key_type_ref KeyOfValue(value_type_ref D) { return D; }
-  static inline data_type_ref DataOfValue(value_type_ref) { return true; }
+  static key_type_ref KeyOfValue(value_type_ref D) { return D; }
+  static data_type_ref DataOfValue(value_type_ref) { return true; }
 
-  static inline bool isEqual(key_type_ref LHS, key_type_ref RHS) {
-    return LHS == RHS;
-  }
+  static bool isEqual(key_type_ref LHS, key_type_ref RHS) { return LHS == RHS; }
 
-  static inline bool isLess(key_type_ref LHS, key_type_ref RHS) {
-    return LHS < RHS;
-  }
+  static bool isLess(key_type_ref LHS, key_type_ref RHS) { return LHS < RHS; }
 
-  static inline bool isDataEqual(data_type_ref,data_type_ref) { return true; }
+  static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
 };
 
 //===----------------------------------------------------------------------===//
@@ -1059,31 +1079,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-
-    iterator() {}
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSet<ValT,ValInfo>;
-
-  public:
-    typedef ptrdiff_t difference_type;
-    typedef typename ImmutableSet<ValT,ValInfo>::value_type value_type;
-    typedef typename ImmutableSet<ValT,ValInfo>::value_type_ref reference;
-    typedef typename iterator::value_type *pointer;
-    typedef std::bidirectional_iterator_tag iterator_category;
-
-    typename iterator::reference operator*() const { return itr->getValue(); }
-    typename iterator::pointer   operator->() const { return &(operator*()); }
-
-    iterator& operator++() { ++itr; return *this; }
-    iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    iterator& operator--() { --itr; return *this; }
-    iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-
-    bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-  };
+  typedef ImutAVLValueIterator<ImmutableSet> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
@@ -1094,13 +1090,11 @@ public:
 
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
 
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
+  static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S) {
     ID.AddPointer(S.Root);
   }
 
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID,*this);
-  }
+  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
 
   //===--------------------------------------------------===//
   // For testing.
@@ -1150,7 +1144,7 @@ public:
     if (Root) { Root->release(); }
   }
 
-  static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
+  static ImmutableSetRef getEmptySet(FactoryTy *F) {
     return ImmutableSetRef(0, F);
   }
 
@@ -1195,21 +1189,7 @@ public:
   // Iterators.
   //===--------------------------------------------------===//
 
-  class iterator {
-    typename TreeTy::iterator itr;
-    iterator(TreeTy* t) : itr(t) {}
-    friend class ImmutableSetRef<ValT,ValInfo>;
-  public:
-    iterator() {}
-    inline value_type_ref operator*() const { return itr->getValue(); }
-    inline iterator& operator++() { ++itr; return *this; }
-    inline iterator  operator++(int) { iterator tmp(*this); ++itr; return tmp; }
-    inline iterator& operator--() { --itr; return *this; }
-    inline iterator  operator--(int) { iterator tmp(*this); --itr; return tmp; }
-    inline bool operator==(const iterator& RHS) const { return RHS.itr == itr; }
-    inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
-    inline value_type *operator->() const { return &(operator*()); }
-  };
+  typedef ImutAVLValueIterator<ImmutableSetRef> iterator;
 
   iterator begin() const { return iterator(Root); }
   iterator end() const { return iterator(); }
@@ -1220,13 +1200,11 @@ public:
 
   unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
 
-  static inline void Profile(FoldingSetNodeID& ID, const ImmutableSetRef& S) {
+  static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S) {
     ID.AddPointer(S.Root);
   }
 
-  inline void Profile(FoldingSetNodeID& ID) const {
-    return Profile(ID,*this);
-  }
+  void Profile(FoldingSetNodeID &ID) const { return Profile(ID, *this); }
 
   //===--------------------------------------------------===//
   // For testing.