libcxxabi [PR58117][NFC]: Open code lower bound

[urnathan]

Summary

This open codes the use of lower-bound when looking for an operator
encoding. Using std::lower_bound can result in symbol references to
the C++ library and that breaks the ABI demangler, which mandates no
such dependency.

[arichardson]

Commit message should include Fixes: https://github.com/llvm/llvm-project/issues/58117, otherwise LGTM.

[ldionne]

I think it would actually be better to define #define _LIBCPP_ENABLE_ASSERTIONS 0 at the top of the file. That way, we (1) retain the ability to use std algorithms, and we don't risk someone else breaking this in the future. WDYT?

[urnathan]

In D135799#3855419, @ldionne wrote:

I think it would actually be better to define #define _LIBCPP_ENABLE_ASSERTIONS 0 at the top of the file. That way, we (1) retain the ability to use std algorithms, and we don't risk someone else breaking this in the future. WDYT?

I thought you disliked that solution -- have you changed your mind? (the define would work for me too)

[urnathan]

In D135799#3855483, @urnathan wrote:

In D135799#3855419, @ldionne wrote:

I think it would actually be better to define #define _LIBCPP_ENABLE_ASSERTIONS 0 at the top of the file. That way, we (1) retain the ability to use std algorithms, and we don't risk someone else breaking this in the future. WDYT?

I thought you disliked that solution -- have you changed your mind? (the define would work for me too)

I've realized the #define solution is unfriendly to header-units/clang-modules, and introduces an ODR problem -- the definitions for templates etc will not be the same.

[ldionne]

I thought you disliked that solution -- have you changed your mind? (the define would work for me too)

Did I mention that in another review? I don't remember. Either way, this LGTM too, but I think the code may break in the future in a similar way if someone unsuspecting adds a use of a stdlib algorithm, or even worse, if we add new assertions to existing stdlib algorithms.

libcxxabi/src/demangle/ItaniumDemangle.h

 // 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

 // 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) {