Merge changes to ItaniumDemangle over to libcxxabi.

ItaniumDemangle had a small NFC refactor to make some of its
code reusable by the newly added Microsoft demangler.  To keep
the libcxxabi demangler as close as possible to the master copy
this refactor is being merged over.

Differential Revision: https://reviews.llvm.org/D49575

4 files changed, 343 insertions, 155 deletions

diff --git a/libcxxabi/src/cxa_demangle.cpp b/libcxxabi/src/cxa_demangle.cpp
index 901db66b270..78d667117fd 100644
--- a/libcxxabi/src/cxa_demangle.cpp
+++ b/libcxxabi/src/cxa_demangle.cpp
@@ -15,150 +15,27 @@
 
 #include "__cxxabi_config.h"
 
-#include <vector>
-#include <algorithm>
-#include <numeric>
+#include "demangle/Compiler.h"
+#include "demangle/StringView.h"
+#include "demangle/Utility.h"
+
 #include <cassert>
+#include <cctype>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
-#include <cctype>
-
-#ifdef _MSC_VER
-// snprintf is implemented in VS 2015
-#if _MSC_VER < 1900
-#define snprintf _snprintf_s
-#endif
-#endif
+#include <numeric>
+#include <vector>
 
-#ifndef NDEBUG
-#if __has_attribute(noinline) && __has_attribute(used)
-#define DUMP_METHOD __attribute__((noinline,used))
-#else
-#define DUMP_METHOD
-#endif
-#endif
 
 namespace {
 
-class StringView {
-  const char *First;
-  const char *Last;
-
-public:
-  template <size_t N>
-  StringView(const char (&Str)[N]) : First(Str), Last(Str + N - 1) {}
-  StringView(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
-  StringView() : First(nullptr), Last(nullptr) {}
-
-  StringView substr(size_t From, size_t To) {
-    if (To >= size())
-      To = size() - 1;
-    if (From >= size())
-      From = size() - 1;
-    return StringView(First + From, First + To);
-  }
-
-  StringView dropFront(size_t N) const {
-    if (N >= size())
-      N = size() - 1;
-    return StringView(First + N, Last);
-  }
-
-  bool startsWith(StringView Str) const {
-    if (Str.size() > size())
-      return false;
-    return std::equal(Str.begin(), Str.end(), begin());
-  }
-
-  const char &operator[](size_t Idx) const { return *(begin() + Idx); }
-
-  const char *begin() const { return First; }
-  const char *end() const { return Last; }
-  size_t size() const { return static_cast<size_t>(Last - First); }
-  bool empty() const { return First == Last; }
-};
-
-bool operator==(const StringView &LHS, const StringView &RHS) {
-  return LHS.size() == RHS.size() &&
-         std::equal(LHS.begin(), LHS.end(), RHS.begin());
-}
-
-// Stream that AST nodes write their string representation into after the AST
-// has been parsed.
-class OutputStream {
-  char *Buffer;
-  size_t CurrentPosition;
-  size_t BufferCapacity;
-
-  // Ensure there is at least n more positions in buffer.
-  void grow(size_t N) {
-    if (N + CurrentPosition >= BufferCapacity) {
-      BufferCapacity *= 2;
-      if (BufferCapacity < N + CurrentPosition)
-        BufferCapacity = N + CurrentPosition;
-      Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
-    }
-  }
-
-public:
-  OutputStream(char *StartBuf, size_t Size)
-      : Buffer(StartBuf), CurrentPosition(0), BufferCapacity(Size) {}
-  OutputStream() = default;
-  void reset(char *Buffer_, size_t BufferCapacity_) {
-    CurrentPosition = 0;
-    Buffer = Buffer_;
-    BufferCapacity = BufferCapacity_;
-  }
-
-  /// If a ParameterPackExpansion (or similar type) is encountered, the offset
-  /// into the pack that we're currently printing.
-  unsigned CurrentPackIndex = std::numeric_limits<unsigned>::max();
-  unsigned CurrentPackMax = std::numeric_limits<unsigned>::max();
-
-  OutputStream &operator+=(StringView R) {
-    size_t Size = R.size();
-    if (Size == 0)
-      return *this;
-    grow(Size);
-    memmove(Buffer + CurrentPosition, R.begin(), Size);
-    CurrentPosition += Size;
-    return *this;
-  }
-
-  OutputStream &operator+=(char C) {
-    grow(1);
-    Buffer[CurrentPosition++] = C;
-    return *this;
-  }
-
-  size_t getCurrentPosition() const { return CurrentPosition; }
-  void setCurrentPosition(size_t NewPos) { CurrentPosition = NewPos; }
-
-  char back() const {
-    return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
-  }
-
-  bool empty() const { return CurrentPosition == 0; }
-
-  char *getBuffer() { return Buffer; }
-  char *getBufferEnd() { return Buffer + CurrentPosition - 1; }
-  size_t getBufferCapacity() { return BufferCapacity; }
-};
-
-template <class T>
-class SwapAndRestore {
-  T &Restore;
-  T OriginalValue;
-public:
-  SwapAndRestore(T& Restore_, T NewVal)
-      : Restore(Restore_), OriginalValue(Restore) {
-    Restore = std::move(NewVal);
-  }
-  ~SwapAndRestore() { Restore = std::move(OriginalValue); }
-
-  SwapAndRestore(const SwapAndRestore &) = delete;
-  SwapAndRestore &operator=(const SwapAndRestore &) = delete;
+enum : int {
+  demangle_unknown_error = -4,
+  demangle_invalid_args = -3,
+  demangle_invalid_mangled_name = -2,
+  demangle_memory_alloc_failure = -1,
+  demangle_success = 0,
 };
 
 // Base class of all AST nodes. The AST is built by the parser, then is
@@ -272,7 +149,7 @@ public:
   // Print the "right". This distinction is necessary to represent C++ types
   // that appear on the RHS of their subtype, such as arrays or functions.
   // Since most types don't have such a component, provide a default
-  // implemenation.
+  // implementation.
   virtual void printRight(OutputStream &) const {}
 
   virtual StringView getBaseName() const { return StringView(); }
@@ -748,7 +625,7 @@ public:
   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
   bool hasFunctionSlow(OutputStream &) const override { return true; }
 
-  // Handle C++'s ... quirky decl grammer by using the left & right
+  // Handle C++'s ... quirky decl grammar by using the left & right
   // distinction. Consider:
   //   int (*f(float))(char) {}
   // f is a function that takes a float and returns a pointer to a function
@@ -1057,7 +934,7 @@ public:
   }
 };
 
-/// A variadic template argument. This node represents an occurance of
+/// A variadic template argument. This node represents an occurrence of
 /// J<something>E in some <template-args>. It isn't itself unexpanded, unless
 /// one of it's Elements is. The parser inserts a ParameterPack into the
 /// TemplateParams table if the <template-args> this pack belongs to apply to an
@@ -2053,7 +1930,7 @@ struct Db {
   const char *Last;
 
   // Name stack, this is used by the parser to hold temporary names that were
-  // parsed. The parser colapses multiple names into new nodes to construct
+  // parsed. The parser collapses multiple names into new nodes to construct
   // the AST. Once the parser is finished, names.size() == 1.
   PODSmallVector<Node *, 32> Names;
 
@@ -2927,7 +2804,7 @@ Node *Db::parseBaseUnresolvedName() {
 // <unresolved-name>
 //  extension        ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
 //                   ::= [gs] <base-unresolved-name>                     # x or (with "gs") ::x
-//                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>  
+//                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
 //                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
 //                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
 //  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
@@ -2977,7 +2854,7 @@ Node *Db::parseUnresolvedName() {
     return SoFar;
   }
 
-  // [gs] sr <unresolved-qualifier-level>+ E   <base-unresolved-name>  
+  // [gs] sr <unresolved-qualifier-level>+ E   <base-unresolved-name>
   if (std::isdigit(look())) {
     do {
       Node *Qual = parseSimpleId();
@@ -5058,33 +4935,25 @@ bool initializeOutputStream(char *Buf, size_t *N, OutputStream &S,
 
 }  // unnamed namespace
 
-enum {
-  unknown_error = -4,
-  invalid_args = -3,
-  invalid_mangled_name = -2,
-  memory_alloc_failure = -1,
-  success = 0,
-};
-
 namespace __cxxabiv1 {
 extern "C" _LIBCXXABI_FUNC_VIS char *
 __cxa_demangle(const char *MangledName, char *Buf, size_t *N, int *Status) {
   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
     if (Status)
-      *Status = invalid_args;
+      *Status = demangle_invalid_args;
     return nullptr;
   }
 
-  int InternalStatus = success;
+  int InternalStatus = demangle_success;
   Db Parser(MangledName, MangledName + std::strlen(MangledName));
   OutputStream S;
 
   Node *AST = Parser.parse();
 
   if (AST == nullptr)
-    InternalStatus = invalid_mangled_name;
+    InternalStatus = demangle_invalid_mangled_name;
   else if (initializeOutputStream(Buf, N, S, 1024))
-    InternalStatus = memory_alloc_failure;
+    InternalStatus = demangle_memory_alloc_failure;
   else {
     assert(Parser.ForwardTemplateRefs.empty());
     AST->print(S);
@@ -5096,6 +4965,6 @@ __cxa_demangle(const char *MangledName, char *Buf, size_t *N, int *Status) {
 
   if (Status)
     *Status = InternalStatus;
-  return InternalStatus == success ? Buf : nullptr;
+  return InternalStatus == demangle_success ? Buf : nullptr;
 }
 }  // __cxxabiv1
diff --git a/libcxxabi/src/demangle/Compiler.h b/libcxxabi/src/demangle/Compiler.h
new file mode 100644
index 00000000000..e5f3c72a451
--- /dev/null
+++ b/libcxxabi/src/demangle/Compiler.h
@@ -0,0 +1,34 @@
+//===--- Compiler.h ---------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+// This file is contains a subset of macros copied from
+// llvm/lib/Demangle/Compiler.h.
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBCXX_DEMANGLE_COMPILER_H
+#define LIBCXX_DEMANGLE_COMPILER_H
+
+#ifdef _MSC_VER
+// snprintf is implemented in VS 2015
+#if _MSC_VER < 1900
+#define snprintf _snprintf_s
+#endif
+#endif
+
+#ifndef __has_attribute
+#define __has_attribute(x) 0
+#endif
+
+#ifndef NDEBUG
+#if __has_attribute(noinline) && __has_attribute(used)
+#define DUMP_METHOD __attribute__((noinline, used))
+#else
+#define DUMP_METHOD
+#endif
+#endif
+
+#endif
diff --git a/libcxxabi/src/demangle/StringView.h b/libcxxabi/src/demangle/StringView.h
new file mode 100644
index 00000000000..986f2defc08
--- /dev/null
+++ b/libcxxabi/src/demangle/StringView.h
@@ -0,0 +1,98 @@
+//===--- StringView.h -------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//
+// This file is copied from llvm/lib/Demangle/StringView.h.
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBCXX_DEMANGLE_STRINGVIEW_H
+#define LIBCXX_DEMANGLE_STRINGVIEW_H
+
+#include <algorithm>
+#include <cassert>
+#include <cstring>
+
+namespace {
+class StringView {
+  const char *First;
+  const char *Last;
+
+public:
+  template <size_t N>
+  StringView(const char (&Str)[N]) : First(Str), Last(Str + N - 1) {}
+  StringView(const char *First_, const char *Last_)
+      : First(First_), Last(Last_) {}
+  StringView(const char *First_, size_t Len)
+      : First(First_), Last(First_ + Len) {}
+  StringView(const char *Str) : First(Str), Last(Str + std::strlen(Str)) {}
+  StringView() : First(nullptr), Last(nullptr) {}
+
+  StringView substr(size_t From) const {
+    return StringView(begin() + From, size() - From);
+  }
+
+  StringView substr(size_t From, size_t To) const {
+    if (To >= size())
+      To = size() - 1;
+    if (From >= size())
+      From = size() - 1;
+    return StringView(First + From, First + To);
+  }
+
+  StringView dropFront(size_t N = 1) const {
+    if (N >= size())
+      N = size() - 1;
+    return StringView(First + N, Last);
+  }
+
+  char front() const {
+    assert(!empty());
+    return *begin();
+  }
+
+  char popFront() {
+    assert(!empty());
+    return *First++;
+  }
+
+  bool consumeFront(char C) {
+    if (!startsWith(C))
+      return false;
+    *this = dropFront(1);
+    return true;
+  }
+
+  bool consumeFront(StringView S) {
+    if (!startsWith(S))
+      return false;
+    *this = dropFront(S.size());
+    return true;
+  }
+
+  bool startsWith(char C) const { return !empty() && *begin() == C; }
+
+  bool startsWith(StringView Str) const {
+    if (Str.size() > size())
+      return false;
+    return std::equal(Str.begin(), Str.end(), begin());
+  }
+
+  const char &operator[](size_t Idx) const { return *(begin() + Idx); }
+
+  const char *begin() const { return First; }
+  const char *end() const { return Last; }
+  size_t size() const { return static_cast<size_t>(Last - First); }
+  bool empty() const { return First == Last; }
+};
+
+inline bool operator==(const StringView &LHS, const StringView &RHS) {
+  return LHS.size() == RHS.size() &&
+         std::equal(LHS.begin(), LHS.end(), RHS.begin());
+}
+} // namespace
+
+#endif
diff --git a/libcxxabi/src/demangle/Utility.h b/libcxxabi/src/demangle/Utility.h
new file mode 100644
index 00000000000..a424c23b8ad
--- /dev/null
+++ b/libcxxabi/src/demangle/Utility.h
@@ -0,0 +1,187 @@
+//===--- Utility.h ----------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//
+// This file is copied from llvm/lib/Demangle/Utility.h.
+//===----------------------------------------------------------------------===//
+
+#ifndef LIBCXX_DEMANGLE_UTILITY_H
+#define LIBCXX_DEMANGLE_UTILITY_H
+
+#include "StringView.h"
+
+#include <cstdint>
+#include <cstdlib>
+#include <cstring>
+#include <iterator>
+#include <limits>
+
+namespace {
+// Stream that AST nodes write their string representation into after the AST
+// has been parsed.
+class OutputStream {
+  char *Buffer;
+  size_t CurrentPosition;
+  size_t BufferCapacity;
+
+  // Ensure there is at least n more positions in buffer.
+  void grow(size_t N) {
+    if (N + CurrentPosition >= BufferCapacity) {
+      BufferCapacity *= 2;
+      if (BufferCapacity < N + CurrentPosition)
+        BufferCapacity = N + CurrentPosition;
+      Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
+    }
+  }
+
+  void writeUnsigned(uint64_t N, bool isNeg = false) {
+    // Handle special case...
+    if (N == 0) {
+      *this << '0';
+      return;
+    }
+
+    char Temp[21];
+    char *TempPtr = std::end(Temp);
+
+    while (N) {
+      *--TempPtr = '0' + char(N % 10);
+      N /= 10;
+    }
+
+    // Add negative sign...
+    if (isNeg)
+      *--TempPtr = '-';
+    this->operator<<(StringView(TempPtr, std::end(Temp)));
+  }
+
+public:
+  OutputStream(char *StartBuf, size_t Size)
+      : Buffer(StartBuf), CurrentPosition(0), BufferCapacity(Size) {}
+  OutputStream() = default;
+  void reset(char *Buffer_, size_t BufferCapacity_) {
+    CurrentPosition = 0;
+    Buffer = Buffer_;
+    BufferCapacity = BufferCapacity_;
+  }
+
+  /// Create an OutputStream from a buffer and a size.  If either of these are
+  /// null a buffer is allocated.
+  static OutputStream create(char *StartBuf, size_t *Size, size_t AllocSize) {
+    OutputStream Result;
+
+    if (!StartBuf || !Size) {
+      StartBuf = static_cast<char *>(std::malloc(AllocSize));
+      Size = &AllocSize;
+    }
+
+    Result.reset(StartBuf, *Size);
+    return Result;
+  }
+
+  /// If a ParameterPackExpansion (or similar type) is encountered, the offset
+  /// into the pack that we're currently printing.
+  unsigned CurrentPackIndex = std::numeric_limits<unsigned>::max();
+  unsigned CurrentPackMax = std::numeric_limits<unsigned>::max();
+
+  OutputStream &operator+=(StringView R) {
+    size_t Size = R.size();
+    if (Size == 0)
+      return *this;
+    grow(Size);
+    std::memmove(Buffer + CurrentPosition, R.begin(), Size);
+    CurrentPosition += Size;
+    return *this;
+  }
+
+  OutputStream &operator+=(char C) {
+    grow(1);
+    Buffer[CurrentPosition++] = C;
+    return *this;
+  }
+
+  OutputStream &operator<<(StringView R) { return (*this += R); }
+
+  OutputStream &operator<<(char C) { return (*this += C); }
+
+  OutputStream &operator<<(long long N) {
+    if (N < 0)
+      writeUnsigned(static_cast<unsigned long long>(-N), true);
+    else
+      writeUnsigned(static_cast<unsigned long long>(N));
+    return *this;
+  }
+
+  OutputStream &operator<<(unsigned long long N) {
+    writeUnsigned(N, false);
+    return *this;
+  }
+
+  OutputStream &operator<<(long N) {
+    return this->operator<<(static_cast<long long>(N));
+  }
+
+  OutputStream &operator<<(unsigned long N) {
+    return this->operator<<(static_cast<unsigned long long>(N));
+  }
+
+  OutputStream &operator<<(int N) {
+    return this->operator<<(static_cast<long long>(N));
+  }
+
+  OutputStream &operator<<(unsigned int N) {
+    return this->operator<<(static_cast<unsigned long long>(N));
+  }
+
+  size_t getCurrentPosition() const { return CurrentPosition; }
+  void setCurrentPosition(size_t NewPos) { CurrentPosition = NewPos; }
+
+  char back() const {
+    return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
+  }
+
+  bool empty() const { return CurrentPosition == 0; }
+
+  char *getBuffer() { return Buffer; }
+  char *getBufferEnd() { return Buffer + CurrentPosition - 1; }
+  size_t getBufferCapacity() { return BufferCapacity; }
+};
+
+template <class T> class SwapAndRestore {
+  T &Restore;
+  T OriginalValue;
+  bool ShouldRestore = true;
+
+public:
+  SwapAndRestore(T &Restore_) : SwapAndRestore(Restore_, Restore_) {}
+
+  SwapAndRestore(T &Restore_, T NewVal)
+      : Restore(Restore_), OriginalValue(Restore) {
+    Restore = std::move(NewVal);
+  }
+  ~SwapAndRestore() {
+    if (ShouldRestore)
+      Restore = std::move(OriginalValue);
+  }
+
+  void shouldRestore(bool ShouldRestore_) { ShouldRestore = ShouldRestore_; }
+
+  void restoreNow(bool Force) {
+    if (!Force && !ShouldRestore)
+      return;
+
+    Restore = std::move(OriginalValue);
+    ShouldRestore = false;
+  }
+
+  SwapAndRestore(const SwapAndRestore &) = delete;
+  SwapAndRestore &operator=(const SwapAndRestore &) = delete;
+};
+
+} // namespace
+
+#endif