[llvm] Enable specifying the order of Registry entries

[njames93]

Summary

Adds support for specifying the order that items appear in llvm::Registry instances.
Currently they appear in the Registry linked list in an undefined order due to the 'static initialization order fiasco'.
For most registries this doesn't pose a problem as there is no observable difference in behaviour, however for a select few there is.
Take the CompilationDatabasePlugins as example. Usages of this is to load a database from a directory with each plugin, breaking out of the loop once a plugin is successful.
In the case where 2 plugins both can load from the same directory, the database you will get will depend on which plugin entry was initialized first. A bug for this has been reported here - https://github.com/clangd/clangd/issues/578.

This patch adds an optional paramater to the Registry::Add function to specify the order of the plugins in the list, lower orders appear near the start. Any plugins that dont specify an order will be placed at the end using the same SIOF behaviour that currently exists.

[njames93]

• Fix some lint warnings, can't fix the include order as the fix disagrees with clang-format.
• Add missing new line at end of test file.

[njames93]

Use __LINE__ instead of __COUNTER__ macro as its standardized.

clang/lib/Tooling/JSONCompilationDatabase.cpp

return Base ? inferTargetAndDriverMode(
                 : nullptr;
   }
 };
 
 } // namespace
 
 // Register the JSONCompilationDatabasePlugin with the
 // CompilationDatabasePluginRegistry using this statically initialized variable.
+// Using 10 as the priority is a little arbitary, but it ensures this will
+// register before the FixedCompilationDatabasePlugin.
 static CompilationDatabasePluginRegistry::Add<JSONCompilationDatabasePlugin>
-X("json-compilation-database", "Reads JSON formatted compilation databases");
+    X("json-compilation-database", "Reads JSON formatted compilation databases",
+      10);
 
 namespace clang {
 namespace tooling {
 
 // This anchor is used to force the linker to link in the generated object file
 // and thus register the JSONCompilationDatabasePlugin.
 volatile int JSONAnchorSource = 0;
 

llvm/include/llvm/Support/Registry.h

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/DynamicLibrary.h"
 #include <memory>
 
 namespace llvm {
-  /// A simple registry entry which provides only a name, description, and
-  /// no-argument constructor.
-  template <typename T>
-  class SimpleRegistryEntry {
-    StringRef Name, Desc;
-    std::unique_ptr<T> (*Ctor)();
+
+template <typename T> class Registry;
+
+template <typename T> class SimpleRegistryEntry {
+  unsigned Order;
+  friend class Registry<T>;
 
-  public:
-    SimpleRegistryEntry(StringRef N, StringRef D, std::unique_ptr<T> (*C)())
-        : Name(N), Desc(D), Ctor(C) {}
+  SimpleRegistryEntry(StringRef N, StringRef D, unsigned O,
+                      std::unique_ptr<T> (*C)())
+      : Name(N), Desc(D), Order(O), Ctor(C) {}
+      : SimpleRegistryEntry(N, D, ~0U, C) {}
 
-    StringRef getName() const { return Name; }
-    StringRef getDesc() const { return Desc; }
-    std::unique_ptr<T> instantiate() const { return Ctor(); }
-  };
 
   /// A global registry used in conjunction with static constructors to make
   /// pluggable components (like targets or garbage collectors) "just work" when
   /// linked with an executable.
   template <typename T>
   class Registry {
   public:
     typedef T type;
class Add {
 
       static std::unique_ptr<T> CtorFn() { return std::make_unique<V>(); }
 
     public:
       Add(StringRef Name, StringRef Desc)
           : Entry(Name, Desc, CtorFn), Node(Entry) {
         add_node(&Node);
       }
+      Add(StringRef Name, StringRef Desc, unsigned Order)
+          : Entry(Name, Desc, Order, CtorFn), Node(Entry) {
+        add_node(&Node);
+      }
     };
   };
 } // end namespace llvm
 
-/// Instantiate a registry class.
-///
-/// This provides template definitions of add_node, begin, and the Head and Tail
-/// pointers, then explicitly instantiates them. We could explicitly specialize
-/// them, instead of the two-step process of define then instantiate, but
-/// strictly speaking that's not allowed by the C++ standard (we would need to
-/// have explicit specialization declarations in all translation units where the
-/// specialization is used) so we don't.
-#define LLVM_INSTANTIATE_REGISTRY(REGISTRY_CLASS) \
-  namespace llvm { \
-  template<typename T> typename Registry<T>::node *Registry<T>::Head = nullptr;\
-  template<typename T> typename Registry<T>::node *Registry<T>::Tail = nullptr;\
-  template<typename T> \
-  void Registry<T>::add_node(typename Registry<T>::node *N) { \
-    if (Tail) \
-      Tail->Next = N; \
-    else \
-      Head = N; \
-    Tail = N; \
-  } \
-  template<typename T> typename Registry<T>::iterator Registry<T>::begin() { \
-    return iterator(Head); \
-  } \
-  template REGISTRY_CLASS::node *Registry<REGISTRY_CLASS::type>::Head; \
-  template REGISTRY_CLASS::node *Registry<REGISTRY_CLASS::type>::Tail; \
-  template \
-  void Registry<REGISTRY_CLASS::type>::add_node(REGISTRY_CLASS::node*); \
-  template REGISTRY_CLASS::iterator Registry<REGISTRY_CLASS::type>::begin(); \
+// Strictly a testing aid, do not use outside tests.
+#define LLVM_INSTANTIATE_REGISTRY_BASE()                                       \
+  namespace llvm {                                                             \
+  template <typename T>                                                        \
+  typename Registry<T>::node *Registry<T>::Head = nullptr;                     \
+  template <typename T>                                                        \
+  typename Registry<T>::node *Registry<T>::Tail = nullptr;                     \
+  template <typename T>                                                        \
+  void Registry<T>::add_node(typename Registry<T>::node *N) {                  \
+    if (N->Val.Order == ~0U) {                                                 \
+      if (Tail)                                                                \
+        Tail->Next = N;                                                        \
+      else                                                                     \
+        Head = N;                                                              \
+      Tail = N;                                                                \
+      return;                                                                  \
+    }                                                                          \
+    auto Ptr = &Head;                                                          \
+    while (*Ptr) {                                                             \
+      if ((*Ptr)->Val.Order > N->Val.Order)                                    \
+        break;                                                                 \
+      Ptr = &(*Ptr)->Next;                                                     \
+    }                                                                          \
+    N->Next = *Ptr;                                                            \
+    if (*Ptr == Tail)                                                          \
+      Tail = N;                                                                \
+    *Ptr = N;                                                                  \
+  }                                                                            \
+  template <typename T> typename Registry<T>::iterator Registry<T>::begin() {  \
+    return iterator(Head);                                                     \
+  }                                                                            \
+  }
+
+// Strictly a testing aid, do not use outside tests.
+#define LLVM_INSTANTIATE_REGISTRY_IMPL(REGISTRY_CLASS)                         \
+  namespace llvm {                                                             \
+  template REGISTRY_CLASS::node *Registry<REGISTRY_CLASS::type>::Head;         \
+  template REGISTRY_CLASS::node *Registry<REGISTRY_CLASS::type>::Tail;         \
+  template void                                                                \
+  Registry<REGISTRY_CLASS::type>::add_node(REGISTRY_CLASS::node *);            \
+  template REGISTRY_CLASS::iterator Registry<REGISTRY_CLASS::type>::begin();   \
   }
 
+/// Instantiate a registry class.
+///
+/// This provides template definitions of add_node, begin, and the Head and Tail
+/// pointers, then explicitly instantiates them. We could explicitly specialize
+/// them, instead of the two-step process of define then instantiate, but
+/// strictly speaking that's not allowed by the C++ standard (we would need to
+/// have explicit specialization declarations in all translation units where the
+/// specialization is used) so we don't.
+#define LLVM_INSTANTIATE_REGISTRY(REGISTRY_CLASS)                              \
+  LLVM_INSTANTIATE_REGISTRY_BASE()                                             \
+  LLVM_INSTANTIATE_REGISTRY_IMPL(REGISTRY_CLASS)
+
 #endif // LLVM_SUPPORT_REGISTRY_H

llvm/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   MemoryTest.cpp
   NativeFormatTests.cpp
   OptimizedStructLayoutTest.cpp
   ParallelTest.cpp
   Path.cpp
   ProcessTest.cpp
   ProgramTest.cpp
   RegexTest.cpp
+  RegistryTest.cpp
   ReverseIterationTest.cpp
   ReplaceFileTest.cpp
   RISCVAttributeParserTest.cpp
   ScaledNumberTest.cpp
   SourceMgrTest.cpp
   SpecialCaseListTest.cpp
   SuffixTreeTest.cpp
   SwapByteOrderTest.cpp

llvm/unittests/Support/RegistryTest.cpp

+//===- llvm/unittest/Support/RegistryTest.cpp - Registry tests ------------===//
+//
+// 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/Support/Registry.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/SmallVector.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using ::testing::ElementsAre;
+using ::testing::UnorderedElementsAre;
+
+LLVM_INSTANTIATE_REGISTRY_BASE()
+
+#define CREATE_TEST_PLUGIN_AND_REGISTRY(Name)                                  \
+  struct Name##Plugin {                                                        \
+    unsigned Value;                                                            \
+    Name##Plugin(unsigned Value) : Value(Value) {}                             \
+  };                                                                           \
+  using Name##PluginRegistry = llvm::Registry<Name##Plugin>;                   \
+  LLVM_INSTANTIATE_REGISTRY_IMPL(Name##PluginRegistry)
+
+// Preprocessor hack to ensure the counter macro is handled correctly
+#define JOIN(X, Y) X##Y
+
+#define ORDERED_PLUGIN_IMPL(Name, Value, UniqID)                               \
+  struct JOIN(OrderedPlugin, UniqID) : Name##Plugin {                          \
+    JOIN(OrderedPlugin, UniqID)() : Name##Plugin(Value) {}                     \
+  };                                                                           \
+  Name##PluginRegistry::Add<JOIN(OrderedPlugin, UniqID)> JOIN(                 \
+      Instance, UniqID)("OrderedPlugin", "OrderedPlugin", Value);
+
+#define UNORDERED_PLUGIN_IMPL(Name, Value, UniqID)                             \
+  struct JOIN(UnorderedPlugin, UniqID) : Name##Plugin {                        \
+    JOIN(UnorderedPlugin, UniqID)() : Name##Plugin(Value) {}                   \
+  };                                                                           \
+  Name##PluginRegistry::Add<JOIN(UnorderedPlugin, UniqID)> JOIN(               \
+      Instance, UniqID)("UnorderedPlugin", "UnorderedPlugin");
+
+#define ORDERED_PLUGIN(Name, Value)                                            \
+  ORDERED_PLUGIN_IMPL(Name, Value, __COUNTER__)
+
+#define UNORDERED_PLUGIN_WITH_VALUE(Name, Value)                               \
+  UNORDERED_PLUGIN_IMPL(Name, Value, __COUNTER__)
+
+#define UNORDERED_PLUGIN(Name) UNORDERED_PLUGIN_WITH_VALUE(Name, 0)
+
+CREATE_TEST_PLUGIN_AND_REGISTRY(AllUnordered)
+
+UNORDERED_PLUGIN_WITH_VALUE(AllUnordered, 34)
+UNORDERED_PLUGIN_WITH_VALUE(AllUnordered, 99)
+UNORDERED_PLUGIN_WITH_VALUE(AllUnordered, 52)
+UNORDERED_PLUGIN_WITH_VALUE(AllUnordered, 81)
+UNORDERED_PLUGIN(AllUnordered)
+
+TEST(RegistryTest, AllUnordered) {
+  llvm::SmallVector<unsigned, 5> Values;
+  for (auto &Entry : AllUnorderedPluginRegistry::entries())
+    Values.push_back(Entry.instantiate()->Value);
+  EXPECT_THAT(Values, UnorderedElementsAre(0, 34, 52, 81, 99));
+}
+
+CREATE_TEST_PLUGIN_AND_REGISTRY(Ordered)
+ORDERED_PLUGIN(Ordered, 10)
+ORDERED_PLUGIN(Ordered, 25)
+ORDERED_PLUGIN(Ordered, 5)
+ORDERED_PLUGIN(Ordered, 3)
+ORDERED_PLUGIN(Ordered, 9)
+
+TEST(RegistryTest, Ordered) {
+  llvm::SmallVector<unsigned, 5> Values;
+  for (auto &Entry : OrderedPluginRegistry::entries())
+    Values.push_back(Entry.instantiate()->Value);
+  EXPECT_THAT(Values, ElementsAre(3, 5, 9, 10, 25));
+}
+
+/// When a plugin registry mixes its ordering across entries. All entries that
+/// specify an order should be registered first, all others will have an
+/// undefined order at the end of the registry.
+/// \code
+///   Registry<...>::Add<...> Foo("Name", "Desc")
+///   Registry<...>::Add<...> Bar("Name", "Desc", 10)
+/// \endcode
+/// In this example Bar will appear first
+
+CREATE_TEST_PLUGIN_AND_REGISTRY(MixedUnorderedStart)
+UNORDERED_PLUGIN_WITH_VALUE(MixedUnorderedStart, 43)
+UNORDERED_PLUGIN_WITH_VALUE(MixedUnorderedStart, 86)
+ORDERED_PLUGIN(MixedUnorderedStart, 44)
+ORDERED_PLUGIN(MixedUnorderedStart, 85)
+UNORDERED_PLUGIN_WITH_VALUE(MixedUnorderedStart, 64)
+ORDERED_PLUGIN(MixedUnorderedStart, 20)
+
+TEST(RegistryTest, MixedUnorderedStart) {
+  llvm::SmallVector<unsigned, 6> Values;
+  for (auto &Entry : MixedUnorderedStartPluginRegistry::entries())
+    Values.push_back(Entry.instantiate()->Value);
+  EXPECT_THAT(makeArrayRef(Values).take_front(3), ElementsAre(20, 44, 85));
+  EXPECT_THAT(makeArrayRef(Values).take_back(3),
+              UnorderedElementsAre(43, 86, 64));
+}
+
+CREATE_TEST_PLUGIN_AND_REGISTRY(MixedOrderedStart)
+ORDERED_PLUGIN(MixedOrderedStart, 44)
+UNORDERED_PLUGIN_WITH_VALUE(MixedOrderedStart, 43)
+UNORDERED_PLUGIN_WITH_VALUE(MixedOrderedStart, 86)
+ORDERED_PLUGIN(MixedOrderedStart, 85)
+UNORDERED_PLUGIN_WITH_VALUE(MixedOrderedStart, 64)
+ORDERED_PLUGIN(MixedOrderedStart, 20)
+
+TEST(RegistryTest, MixedOrderedStart) {
+  llvm::SmallVector<unsigned, 6> Values;
+  for (auto &Entry : MixedOrderedStartPluginRegistry::entries())
+    Values.push_back(Entry.instantiate()->Value);
+  EXPECT_THAT(makeArrayRef(Values).take_front(3), ElementsAre(20, 44, 85));
+  EXPECT_THAT(makeArrayRef(Values).take_back(3),
+              UnorderedElementsAre(43, 86, 64));
+}
 No newline at end of file