[ADT] Add STLForwardCompat.h and llvm::disjunction

[scott.linder]

Summary

Move some types in STLExtras.h which are named and behave identically to
STL types from future standards into a dedicated header. This keeps them
organized (they are not "extras" in the same sense as most types in
STLExtras.h are) and fixes circular dependencies in future patches.

[scott.linder]

Remove SHIM macro; it wasn't actually doing anything (there was a typo in the
lint identifier), it seems like clang-tidy just ignored the identifier when it
was wrapped in a macro.

[dblaikie]

I don't think "shim" is the right term here - if anything I'd think things like our range-based adapters to standard algorithms (llvm::sort(R, C) -> std::sort(R.begin(), R.end(), C)) is a "shim" in the sense of the word that I know of - a thin adapter ( https://en.wikipedia.org/wiki/Shim_(computing) - "a shim is a library that transparently intercepts API calls and changes the arguments passed, handles the operation itself or redirects the operation elsewhere.").

These are STL reimplementations, though that's a bit of a mouthful. STLCompat.h, perhaps?

llvm/include/llvm/ADT/STLShims.h

23

I'm not sure this macro is adding value - what's the motivation for it compared to a comment pointing out that a given thing is intended to be equivalent to the standard entity of the same name?

[dblaikie]

Oh, and the patch description specifically calls out "STL types" - but presumably we might put STL variables in here too (like the _v variants of various traits)

[scott.linder]

In D100668#2695927, @dblaikie wrote:

I don't think "shim" is the right term here - if anything I'd think things like our range-based adapters to standard algorithms (llvm::sort(R, C) -> std::sort(R.begin(), R.end(), C)) is a "shim" in the sense of the word that I know of - a thin adapter ( https://en.wikipedia.org/wiki/Shim_(computing) - "a shim is a library that transparently intercepts API calls and changes the arguments passed, handles the operation itself or redirects the operation elsewhere.").

These are STL reimplementations, though that's a bit of a mouthful. STLCompat.h, perhaps?

Sure, I'm amenable to other names. I originally planned to use "polyfill" (https://en.wikipedia.org/wiki/Polyfill_(programming)) but landed on shim because:

• It is shorter
• It is an older term (I hoped more people would understand the use in this context)
• The term "polyfill" seems to almost universally apply to javascript (see e.g. http://speakingjs.com/es5/ch30.html#shim_vs_polyfill)

The definition of "shim" I was going for is the one from that speakingjs book: "A shim is a library that brings a new API to an older environment, using only the means of that environment."

I don't like just "reimplementation", even though it is accurate, because it doesn't really convey the intent; we will be deleting our version ASAP. We really don't care about the implementation per-se, we just want to code to a future specification. If we were dissatisfied with the standard implementations then "reimplementation" would seem more apt.

I also feel like just "Compat" is a bit ambiguous, but maybe I just think of "backwards" compat first. What do you think about STLForwardCompat.h ? That also brings up the questionof what happens when someone compiles LLVM with a newer standard than C++14, i.e. is this really "compatible" with the newer standards if we don't detect whether they are present? I am not sure how best to approach doing that in general.

[dblaikie]

In D100668#2695979, @scott.linder wrote:

In D100668#2695927, @dblaikie wrote:

I don't think "shim" is the right term here - if anything I'd think things like our range-based adapters to standard algorithms (llvm::sort(R, C) -> std::sort(R.begin(), R.end(), C)) is a "shim" in the sense of the word that I know of - a thin adapter ( https://en.wikipedia.org/wiki/Shim_(computing) - "a shim is a library that transparently intercepts API calls and changes the arguments passed, handles the operation itself or redirects the operation elsewhere.").

These are STL reimplementations, though that's a bit of a mouthful. STLCompat.h, perhaps?

Sure, I'm amenable to other names. I originally planned to use "polyfill" (https://en.wikipedia.org/wiki/Polyfill_(programming)) but landed on shim because:

• It is shorter
• It is an older term (I hoped more people would understand the use in this context)
• The term "polyfill" seems to almost universally apply to javascript (see e.g. http://speakingjs.com/es5/ch30.html#shim_vs_polyfill)

Ah, yeah, that's not one I've come across personally.

The definition of "shim" I was going for is the one from that speakingjs book: "A shim is a library that brings a new API to an older environment, using only the means of that environment."

Yeah, it's certainly got some related use.

I don't like just "reimplementation", even though it is accurate, because it doesn't really convey the intent; we will be deleting our version ASAP. We really don't care about the implementation per-se, we just want to code to a future specification. If we were dissatisfied with the standard implementations then "reimplementation" would seem more apt.

I also feel like just "Compat" is a bit ambiguous, but maybe I just think of "backwards" compat first. What do you think about STLForwardCompat.h ? That also brings up the questionof what happens when someone compiles LLVM with a newer standard than C++14, i.e. is this really "compatible" with the newer standards if we don't detect whether they are present? I am not sure how best to approach doing that in general.

ForwardCompat sounds OK to me, but given the other definition of shim, I'm probably OK-ish with that too.

Re: Newer standards. I think it's still compatible/doesn't make the name wrong if people are compiling in C++14 mode. But if we really wanted to, probably the closer we get to migrating to building with C++>14 by default, we might change these shims/whatever they are to be defined as aliases for the real implementations when compiling with a version that supports the implementation to help align things if they happen to be divergent in any way. Then eventually when the newer version is adopted as an LLVM requirement, we'd remove the fallback (so the llvm::* would only be an alias for the std:: version at that point) and then eventually remove the aliases.

[scott.linder]

• Rename STLShims -> STLForwardCompat
• Change "STL types" -> "STL features"

[scott.linder]

Fix a typo in the description

[dblaikie]

llvm/include/llvm/ADT/STLForwardCompat.h

36–37 ↗

(On Diff #338254)

Hmm, seems this isn't actually conforming implementation (the standard one says that it short-circuits - doesn't try to evaluate later expressions if an early one is true/false - and that the type returned by std::conditional is the type of that last condition that proved the rule, I think?). But probably close enough since it's already committed.

llvm/unittests/ADT/STLForwardCompatTest.cpp

22–30 ↗

(On Diff #338254)

Was there no existing testing of conjunction? (ie: something that should be deleted as the testing is added/moved here?)

[scott.linder]

llvm/include/llvm/ADT/STLForwardCompat.h

36–37 ↗

(On Diff #338254)

My understanding of the definition of std::conditional led me to believe this definition does satisfy the "short-circuiting" property, and I tried to include at least a (potentially incomplete?) trivial test of that using an incomplete_type following an element that proves the rule of the predicate (i.e. false for conjunction, true for disjunction)

llvm/unittests/ADT/STLForwardCompatTest.cpp

22–30 ↗

(On Diff #338254)

Not sure, I assume it just wasn't noticed in review? There are tests of it indirectly via Any, see https://reviews.llvm.org/D48807

[dblaikie]

(good enough to commit - but happy to also keep discussing the finer nuances of spec conformance here if you like)

llvm/include/llvm/ADT/STLForwardCompat.h

36–37 ↗

(On Diff #338254)

Oh, right you are!

Is it worth testing the exact type of disjunction/conjunction, rather than only their boolean value? To test that aspect of the spec conformance? Hmm - wonder what the spec says about whether the type parameters must be able to be derived from?

llvm/unittests/ADT/STLForwardCompatTest.cpp

22–30 ↗

(On Diff #338254)

Yep, my bad. Thanks for adding in testing now

llvm/include/llvm/ADT/STLExtras.h

 // No library is required when using these functions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STLEXTRAS_H
 #define LLVM_ADT_STLEXTRAS_H
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLShims.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
using ValueOfRange = typename std::remove_reference<decltype(
     *std::begin(std::declval<RangeT &>()))>::type;
 
 } // end namespace detail
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <type_traits>
 //===----------------------------------------------------------------------===//
 
-template <typename T>
-struct negation : std::integral_constant<bool, !bool(T::value)> {};
-
-template <typename...> struct conjunction : std::true_type {};
-template <typename B1> struct conjunction<B1> : B1 {};
-template <typename B1, typename... Bn>
-struct conjunction<B1, Bn...>
-    : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
-
 template <typename T> struct make_const_ptr {
   using type =
       typename std::add_pointer<typename std::add_const<T>::type>::type;
 };
 
 template <typename T> struct make_const_ref {
   using type = typename std::add_lvalue_reference<
       typename std::add_const<T>::type>::type;

 
 /// Utility type to build an inheritance chain that makes it easy to rank
 /// overload candidates.
 template <int N> struct rank : rank<N - 1> {};
 template <> struct rank<0> {};
 
 /// traits class for checking whether type T is one of any of the given
 /// types in the variadic list.
-template <typename T, typename... Ts> struct is_one_of {
-  static const bool value = false;
-};
-
-template <typename T, typename U, typename... Ts>
-struct is_one_of<T, U, Ts...> {
-  static const bool value =
-      std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
-};
+template <typename T, typename... Ts>
+using is_one_of = disjunction<std::is_same<T, Ts>...>;
 
 /// traits class for checking whether type T is a base class for all
 ///  the given types in the variadic list.
-template <typename T, typename... Ts> struct are_base_of {
-  static const bool value = true;
-};
-
-template <typename T, typename U, typename... Ts>
-struct are_base_of<T, U, Ts...> {
-  static const bool value =
-      std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
-};
+template <typename T, typename... Ts>
+using are_base_of = conjunction<std::is_base_of<T, Ts>...>;
 
 //===----------------------------------------------------------------------===//
 //     Extra additions for arrays
 //===----------------------------------------------------------------------===//
 
 // We have a copy here so that LLVM behaves the same when using different
 // standard libraries.
 template <class Iterator, class RNG>

llvm/include/llvm/ADT/STLShims.h

+//===- STLShims.h - Shims for future STL features ---------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Shims for simple, self-contained types included in future STL versions.
+//
+// These should be replaced with their STL counterparts as the C++ version LLVM
+// is compiled with is updated.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_STLSHIMS_H
+#define LLVM_ADT_STLSHIMS_H
+
+#include <cstddef>
+#include <type_traits>
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+//     Shims for C++17
+//===----------------------------------------------------------------------===//
+
+template <typename T>
+struct negation // NOLINT(readability-identifier-naming)
+    : std::integral_constant<bool, !bool(T::value)> {};
+
+template <typename...>
+struct conjunction // NOLINT(readability-identifier-naming)
+    : std::true_type {};
+template <typename B1> struct conjunction<B1> : B1 {};
+template <typename B1, typename... Bn>
+struct conjunction<B1, Bn...>
+    : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
+
+template <typename...>
+struct disjunction // NOLINT(readability-identifier-naming)
+    : std::false_type {};
+template <typename B1> struct disjunction<B1> : B1 {};
+template <typename B1, typename... Bn>
+struct disjunction<B1, Bn...>
+    : std::conditional<bool(B1::value), B1, disjunction<Bn...>>::type {};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_STLSHIMS_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp
   PointerUnionTest.cpp
   PostOrderIteratorTest.cpp
   PriorityWorklistTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
   STLExtrasTest.cpp
+  STLShimsTest.cpp
   ScopeExitTest.cpp
   SequenceTest.cpp
   SetVectorTest.cpp
   SimpleIListTest.cpp
   SmallPtrSetTest.cpp
   SmallSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp

llvm/unittests/ADT/STLShimsTest.cpp

+//===- STLShimsTest.cpp - Unit tests for STL shims ------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/STLShims.h"
+#include "gtest/gtest.h"
+
+namespace {
+
+TEST(STLShims, NegationTest) {
+  EXPECT_TRUE((llvm::negation<std::false_type>::value));
+  EXPECT_FALSE((llvm::negation<std::true_type>::value));
+}
+
+struct incomplete_type;
+
+TEST(STLShims, ConjunctionTest) {
+  EXPECT_TRUE((llvm::conjunction<>::value));
+  EXPECT_FALSE((llvm::conjunction<std::false_type>::value));
+  EXPECT_TRUE((llvm::conjunction<std::true_type>::value));
+  EXPECT_FALSE((llvm::conjunction<std::false_type, incomplete_type>::value));
+  EXPECT_FALSE((llvm::conjunction<std::false_type, std::true_type>::value));
+  EXPECT_FALSE((llvm::conjunction<std::true_type, std::false_type>::value));
+  EXPECT_TRUE((llvm::conjunction<std::true_type, std::true_type>::value));
+  EXPECT_TRUE((llvm::conjunction<std::true_type, std::true_type,
+                                 std::true_type>::value));
+}
+
+TEST(STLShims, DisjunctionTest) {
+  EXPECT_FALSE((llvm::disjunction<>::value));
+  EXPECT_FALSE((llvm::disjunction<std::false_type>::value));
+  EXPECT_TRUE((llvm::disjunction<std::true_type>::value));
+  EXPECT_TRUE((llvm::disjunction<std::true_type, incomplete_type>::value));
+  EXPECT_TRUE((llvm::disjunction<std::false_type, std::true_type>::value));
+  EXPECT_TRUE((llvm::disjunction<std::true_type, std::false_type>::value));
+  EXPECT_TRUE((llvm::disjunction<std::true_type, std::true_type>::value));
+  EXPECT_TRUE((llvm::disjunction<std::true_type, std::true_type,
+                                 std::true_type>::value));
+}
+
+} // namespace