[libc++] Fix std::type_info comparison

[ldionne]

Summary

As noted by Richard Smith in https://reviews.llvm.org/D97802#2675067, the
current implementation of std::type_info less-than comparison was not an
ordering relation. This commit fixes that.

It's technically a behavior change, however anyone relying on the ordering
as given by the previous implementation was relying on something extremely
brittle, so I think it's safe to fix this.

[ldionne]

libcxx/test/std/language.support/support.rtti/type.info/type_info.order.sh.cpp

1

This is my best attempt at trying to test this, but TBH I'm not sure how good it is.

[rjmccall]

Patch functionally LGTM. Not sure what you're asking about the test script, but I don't know the libc++ test suite.

[Mordante]

Seems the Windows build fails, can you look why the XFAIL doesn't work.

libcxx/include/typeinfo

269

I love this kind of comment, however it's now duplicated here and in the implementation. Would it make sense to move this comment in the implementation so we have only one copy?

libcxx/test/std/language.support/support.rtti/type.info/type_info.order.sh.cpp

1

Also not to sure how good it is. Can we test whether the order is different in the TUs? Would it help to run the test with different linker orders for TU1 and TU2? e.g. TU1 TU2 MAIN and TU2 TU1 MAIN.

36

Is there a reason to put this function here instead of in MAIN?

libcxx/include/typeinfo

static bool __eq(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
       if (__is_type_name_unique(__lhs) || __is_type_name_unique(__rhs))
         // Either both are unique and have a different address, or one of them
         // is unique and the other one isn't. In both cases they are unequal.
         return false;
       return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) == 0;
     }
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
     static bool __lt(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
-      if (__is_type_name_unique(__lhs) || __is_type_name_unique(__rhs))
+      // We order all unique type_infos before the non-unique ones. Then,
+      // unique type_infos are ordered by their address amongst themselves,
+      // and non-unique type_infos are ordered by their string comparison
+      // amongst themselves.
+      bool __lhs_unique = __is_type_name_unique(__lhs);
+      bool __rhs_unique = __is_type_name_unique(__rhs);
+      if (__lhs_unique != __rhs_unique) // unique < non-unique
+        return __lhs_unique;
+      if (__lhs_unique) // use address amongst unique ones
         return __lhs < __rhs;
+      // use string comparison amongst non-unique ones
       return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) < 0;
     }
 
    private:
     // The unique bit is the top bit. It is expected that __type_name_t is 64 bits when
     // this implementation is actually used.
     typedef integral_constant<__type_name_t,
       (1ULL << ((__CHAR_BIT__ * sizeof(__type_name_t)) - 1))> __non_unique_rtti_bit;

libcxx/test/std/language.support/support.rtti/type.info/type_info.order.sh.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: no-rtti
+// UNSUPPORTED: c++03
+// XFAIL: LIBCXX-WINDOWS-FIXME
+
+// Make sure that operator< on std::type_info is an ordering relation.
+// We do this by defining a bunch of classes in different TUs with RTTIs
+// having various names and visibilities (which can have an impact on how
+// they are ordered depending on the ABI), and making sure that that set
+// indeed ordered totally by operator<. We do this very naively based on
+// the text book definition of a total order.
+
+// RUN: %{cxx} %s %{flags} %{compile_flags} -c -o %t.tu1.o -DTU1
+// RUN: %{cxx} %s %{flags} %{compile_flags} -c -o %t.tu2.o -DTU2
+// RUN: %{cxx} %s %{flags} %{compile_flags} -c -o %t.main.o -DMAIN
+// RUN: %{cxx} %t.tu1.o %t.tu2.o %t.main.o %{flags} %{link_flags} -o %t.exe
+// RUN: %{exec} %t.exe
+
+#include <cassert>
+#include <typeindex>
+#include <vector>
+
+extern std::vector<std::type_index> registry;
+
+void register1();
+void register2();
+
+template <typename Container>
+void check_total_order(Container const& elements) {
+  for (auto const& a : elements) {
+    for (auto const& b: elements) {
+      for (auto const& c: elements) {
+        // Antisymmetry
+        if (a <= b && b <= a)
+          assert(a == b);
+
+        // Transitivity
+        if (a <= b && b <= c)
+          assert(a <= c);
+
+        // Connexivity
+        assert(a <= b || b <= a);
+      }
+    }
+  }
+}
+
+struct __attribute__((visibility("default"))) KeyFunction {
+  virtual ~KeyFunction();
+};
+
+struct __attribute__((visibility("default"))) NoKeyFunction {
+  virtual void foo() { }
+};
+
+#if defined(TU1)
+
+struct __attribute__((visibility("hidden"))) SameNameHidden { };
+
+KeyFunction::~KeyFunction() { }
+
+void register1() {
+  registry.push_back(std::type_index(typeid(NoKeyFunction)));
+  registry.push_back(std::type_index(typeid(KeyFunction)));
+  registry.push_back(std::type_index(typeid(SameNameHidden)));
+}
+
+#elif defined(TU2)
+
+struct __attribute__((visibility("hidden"))) SameNameHidden { };
+
+void register2() {
+  registry.push_back(std::type_index(typeid(NoKeyFunction)));
+  registry.push_back(std::type_index(typeid(KeyFunction)));
+  registry.push_back(std::type_index(typeid(SameNameHidden)));
+}
+
+#elif defined(MAIN)
+
+std::vector<std::type_index> registry;
+
+int main(int, char**) {
+  register1();
+  register2();
+
+  check_total_order(registry);
+  return 0;
+}
+
+#endif