[libcxxabi] Resync llvm & libcxxabi's demangler

[urnathan]

Summary

I noticed this when addressing pr58117

Sadly the demangler copies have diverged. This resyncs them by
a) pulling the meaningful llvm changes into libcxxabi's gold copy.
b) rerunning the sync script

Please be aware of the syncing (having a single version and teaching cmake about that was beyond my abilities)

It turns out the new include is needed, but highlights another problem -- the placement new uses presume the allocator succeeds. That;s not true in general. Currently the allocator calls std::terminat on failre, but that means it isn't an ABI-compliant demangler. That should return an error code on memory exhaustion. https://github.com/llvm/llvm-project/issues/58289 captures that problem

[bader]

@urnathan, sorry, we didn't notice that https://reviews.llvm.org/D130909 introduces divergence. @steffenlarsen, @jcranmer-intel, FYI.
Regarding dropping LLVM_ prefix from header guards, it looks like these were removed with some automatic tool (https://github.com/intel/llvm/commit/c13a09a462807936f9eb17cc64f53ad7c9e8ddec), so I would expect someone else will run the tool again and add them back. Any ideas how to prevent this type of changes in the future? Maybe we can keep LLVM_ prefix for sources in llvm/ directory and just ignore this difference. What do you think?

[ldionne]

The libcxxabi copy is the canonical version, right? If so, we could add a test inside LLVM that ensures that re-syncing the files does not produce any difference in output.

[urnathan]

In D135446#3852105, @bader wrote:

@urnathan, sorry, we didn't notice that https://reviews.llvm.org/D130909 introduces divergence. @steffenlarsen, @jcranmer-intel, FYI.
Regarding dropping LLVM_ prefix from header guards, it looks like these were removed with some automatic tool (https://github.com/intel/llvm/commit/c13a09a462807936f9eb17cc64f53ad7c9e8ddec), so I would expect someone else will run the tool again and add them back. Any ideas how to prevent this type of changes in the future? Maybe we can keep LLVM_ prefix for sources in llvm/ directory and just ignore this difference. What do you think?

yeah, that;s annoying, the src and dst are not identical anyway, because we insert DO NOT EDIT comments via sed.

I'm sure I can tweak that to modify the idempotency macros. then one can apply the script, and if there's no change in the src version there will also be no change in the dst version.

[jcranmer-intel]

In D135446#3852407, @ldionne wrote:

The libcxxabi copy is the canonical version, right? If so, we could add a test inside LLVM that ensures that re-syncing the files does not produce any difference in output.

Given that we now have a monorepo, it should be possible to have one single source of truth and use relative source paths from either the llvm/ or the libcxxabi/ implementation to include the right files, right? Or do we intend for it to be possible to build LLVM projects with only a subset of the top-level directories checked out?

libcxxabi/src/demangle/ItaniumDemangle.h

class VendorExtQualType final : public Node {
   const Node *Ty;
   StringView Ext;
   const Node *TA;
 
 public:
   VendorExtQualType(const Node *Ty_, StringView Ext_, const Node *TA_)
       : Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_), TA(TA_) {}
 
+  const Node *getTy() const { return Ty; }
+  StringView getExt() const { return Ext; }
+  const Node *getTA() const { return TA; }
+
   template <typename Fn> void match(Fn F) const { F(Ty, Ext, TA); }
 
   void printLeft(OutputBuffer &OB) const override {
     Ty->print(OB);
     OB += " ";
     OB += Ext;
     if (TA != nullptr)
       TA->print(OB);
protected:
   }
 
 public:
   QualType(const Node *Child_, Qualifiers Quals_)
       : Node(KQualType, Child_->RHSComponentCache,
              Child_->ArrayCache, Child_->FunctionCache),
         Quals(Quals_), Child(Child_) {}
 
+  Qualifiers getQuals() const { return Quals; }
+  const Node *getChild() const { return Child; }
+
   template<typename Fn> void match(Fn F) const { F(Child, Quals); }
 
   bool hasRHSComponentSlow(OutputBuffer &OB) const override {
     return Child->hasRHSComponent(OB);
   }
   bool hasArraySlow(OutputBuffer &OB) const override {
     return Child->hasArray(OB);
   }

 class PointerType final : public Node {
   const Node *Pointee;
 
 public:
   PointerType(const Node *Pointee_)
       : Node(KPointerType, Pointee_->RHSComponentCache),
         Pointee(Pointee_) {}
 
+  const Node *getPointee() const { return Pointee; }
+
   template<typename Fn> void match(Fn F) const { F(Pointee); }
 
   bool hasRHSComponentSlow(OutputBuffer &OB) const override {
     return Pointee->hasRHSComponent(OB);
   }
 
   void printLeft(OutputBuffer &OB) const override {
     // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.

 class VectorType final : public Node {
   const Node *BaseType;
   const Node *Dimension;
 
 public:
   VectorType(const Node *BaseType_, const Node *Dimension_)
       : Node(KVectorType), BaseType(BaseType_), Dimension(Dimension_) {}
 
+  const Node *getBaseType() const { return BaseType; }
+  const Node *getDimension() const { return Dimension; }
+
   template<typename Fn> void match(Fn F) const { F(BaseType, Dimension); }
 
   void printLeft(OutputBuffer &OB) const override {
     BaseType->print(OB);
     OB += " vector[";
     if (Dimension)
       Dimension->print(OB);
     OB += "]";

 // If the next 2 chars are an operator encoding, consume them and return their
 // OperatorInfo.  Otherwise return nullptr.
 template <typename Derived, typename Alloc>
 const typename AbstractManglingParser<Derived, Alloc>::OperatorInfo *
 AbstractManglingParser<Derived, Alloc>::parseOperatorEncoding() {
   if (numLeft() < 2)
     return nullptr;
 
-  auto Op = std::lower_bound(
-      &Ops[0], &Ops[NumOps], First,
-      [](const OperatorInfo &Op_, const char *Enc_) { return Op_ < Enc_; });
-  if (Op == &Ops[NumOps] || *Op != First)
+  // We can't use lower_bound as that can link to symbols in the C++ library,
+  // and this must remain independant of that.
+  size_t lower = 0u, upper = NumOps - 1; // Inclusive bounds.
+  while (upper != lower) {
+    size_t middle = (upper + lower) / 2;
+    if (Ops[middle] < First)
+      lower = middle + 1;
+    else
+      upper = middle;
+  }
+  if (Ops[lower] != First)
     return nullptr;
 
   First += 2;
-  return Op;
+  return &Ops[lower];
 }
 
 //   <operator-name> ::= See parseOperatorEncoding()
 //                   ::= li <source-name>  # operator ""
 //                   ::= v <digit> <source-name>  # vendor extended operator
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseOperatorName(NameState *State) {

llvm/include/llvm/Demangle/ItaniumDemangle.h

 //===--- ItaniumDemangle.h -----------*- mode:c++;eval:(read-only-mode) -*-===//
 //       Do not edit! See README.txt.
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Generic itanium demangler library.
 // There are two copies of this file in the source tree.  The one under
 // libcxxabi is the original and the one under llvm is the copy.  Use
 // cp-to-llvm.sh to update the copy.  See README.txt for more details.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_DEMANGLE_ITANIUMDEMANGLE_H
-#define LLVM_DEMANGLE_ITANIUMDEMANGLE_H
+#ifndef DEMANGLE_ITANIUMDEMANGLE_H
+#define DEMANGLE_ITANIUMDEMANGLE_H
 
 #include "DemangleConfig.h"
 #include "StringView.h"
 #include "Utility.h"
 #include <algorithm>
 #include <cassert>
 #include <cctype>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <limits>
+#include <new>
 #include <utility>
 
 DEMANGLE_NAMESPACE_BEGIN
 
 template <class T, size_t N> class PODSmallVector {
   static_assert(std::is_pod<T>::value,
                 "T is required to be a plain old data type");
 

 // If the next 2 chars are an operator encoding, consume them and return their
 // OperatorInfo.  Otherwise return nullptr.
 template <typename Derived, typename Alloc>
 const typename AbstractManglingParser<Derived, Alloc>::OperatorInfo *
 AbstractManglingParser<Derived, Alloc>::parseOperatorEncoding() {
   if (numLeft() < 2)
     return nullptr;
 
-  auto Op = std::lower_bound(
-      &Ops[0], &Ops[NumOps], First,
-      [](const OperatorInfo &Op_, const char *Enc_) { return Op_ < Enc_; });
-  if (Op == &Ops[NumOps] || *Op != First)
+  // We can't use lower_bound as that can link to symbols in the C++ library,
+  // and this must remain independant of that.
+  size_t lower = 0u, upper = NumOps - 1; // Inclusive bounds.
+  while (upper != lower) {
+    size_t middle = (upper + lower) / 2;
+    if (Ops[middle] < First)
+      lower = middle + 1;
+    else
+      upper = middle;
+  }
+  if (Ops[lower] != First)
     return nullptr;
 
   First += 2;
-  return Op;
+  return &Ops[lower];
 }
 
 //   <operator-name> ::= See parseOperatorEncoding()
 //                   ::= li <source-name>  # operator ""
 //                   ::= v <digit> <source-name>  # vendor extended operator
 template <typename Derived, typename Alloc>
 Node *
 AbstractManglingParser<Derived, Alloc>::parseOperatorName(NameState *State) {

 template <typename Alloc>
 struct ManglingParser : AbstractManglingParser<ManglingParser<Alloc>, Alloc> {
   using AbstractManglingParser<ManglingParser<Alloc>,
                                Alloc>::AbstractManglingParser;
 };
 
 DEMANGLE_NAMESPACE_END
 
-#endif // LLVM_DEMANGLE_ITANIUMDEMANGLE_H
+#endif // DEMANGLE_ITANIUMDEMANGLE_H

llvm/include/llvm/Demangle/StringView.h

 //===--- StringView.h ----------------*- mode:c++;eval:(read-only-mode) -*-===//
 //       Do not edit! See README.txt.
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // FIXME: Use std::string_view instead when we support C++17.
 // There are two copies of this file in the source tree.  The one under
 // libcxxabi is the original and the one under llvm is the copy.  Use
 // cp-to-llvm.sh to update the copy.  See README.txt for more details.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_DEMANGLE_STRINGVIEW_H
-#define LLVM_DEMANGLE_STRINGVIEW_H
+#ifndef DEMANGLE_STRINGVIEW_H
+#define DEMANGLE_STRINGVIEW_H
 
 #include "DemangleConfig.h"
 #include <cassert>
 #include <cstring>
 
 DEMANGLE_NAMESPACE_BEGIN
 
 class StringView {

llvm/include/llvm/Demangle/Utility.h

 //===--- Utility.h -------------------*- mode:c++;eval:(read-only-mode) -*-===//
 //       Do not edit! See README.txt.
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Provide some utility classes for use in the demangler.
 // There are two copies of this file in the source tree.  The one in libcxxabi
 // is the original and the one in llvm is the copy.  Use cp-to-llvm.sh to update
 // the copy.  See README.txt for more details.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_DEMANGLE_UTILITY_H
-#define LLVM_DEMANGLE_UTILITY_H
+#ifndef DEMANGLE_UTILITY_H
+#define DEMANGLE_UTILITY_H
 
 #include "StringView.h"
 #include <array>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <exception>
 #include <limits>