[C++20] [Modules] Merging of lambda types in deserialization

[ChuanqiXu]

Summary

Close https://github.com/llvm/llvm-project/issues/57222

The previous deserialization code wouldn't try to merge lambdas since every lambda has a unique type before C++20. In C++20 and later, lambdas can have the same type under certain condition. See the issue link or the comment for example.

This is a workaround for the problem but the cost is the inefficiency. And if we want to fix the problem properly, it looks like we need to touch something very fundamentally and it may affect a lot of things beyond the C++20 modules or even modules.

See my inline comments for details.

The bug/defect has a strong impact. I feel like fixing bug is more important so I prefer to land this one first and file an issue for this to record it.

[ChuanqiXu]

clang/lib/Serialization/ASTReaderDecl.cpp

2161–2198

The comment tells why this is a workaround and what we need to do to fix the problem properly.

[vsapsai]

This is my first and pretty shallow review pass. Need to read the standard more thoroughly to be more useful. Others are welcome to chime in (and as I'll be on vacation are encouraged to chime in).

What do you mean by

Due to we don't care about merging unnamed entities before, now it is pretty problematic to fix it in a well formed.

In ASTReaderDecl.cpp we have a bunch of code to deal with anonymous decls, that's why I'm asking. Though I haven't tried to use any of that for your current problem.

Few stylistic nits:

• most of tests in "clang/test/Modules" start with a lowercase and use kebab-naming-style (sometimes with underscores);
• can you please use more descriptive names in tests? Currently hunting for 1-character difference isn't fun and doesn't convey the purpose and intention of the test;
• is it possible to reuse some of the testing code because trying to find differences and what they mean is time-consuming.

Looks like not all branches in the added code are covered by tests but I need more time to play with the code.

clang/lib/Serialization/ASTReaderDecl.cpp

2222

How does this mergeRedeclarable work with other mergeRedeclarable calls in ASTDeclReader::VisitCXXRecordDeclImpl? Are multiple calls OK, do you expect it never to happen or something else?

[vsapsai]

Test case MergeLambdas3.cppm is unstable. Sometimes it passes but usually it fails.

clang/lib/Serialization/ASTReaderDecl.cpp

2161–2198

Is there are a test covering this workaround? I've removed it and see no new test failures.

[ChuanqiXu]

In D140002#4000113, @vsapsai wrote:

This is my first and pretty shallow review pass. Need to read the standard more thoroughly to be more useful. Others are welcome to chime in (and as I'll be on vacation are encouraged to chime in).

Thanks for reviewing this!

What do you mean by

Due to we don't care about merging unnamed entities before, now it is pretty problematic to fix it in a well formed.

In ASTReaderDecl.cpp we have a bunch of code to deal with anonymous decls, that's why I'm asking. Though I haven't tried to use any of that for your current problem.

Oh, this is not accurate. I wanted to say lambdas instead of anonymous decls. In ASTDeclReader::findExisting, lambdas will fall in the block: https://github.com/llvm/llvm-project/blob/bcd0bf9284db0d5d4697611ff9bf3243504aab07/clang/lib/Serialization/ASTReaderDecl.cpp#L3269-L3276. Since lambdas has no name and
serialization::needsAnonymousDeclarationNumber(NamedDecl*) will return false for lambdas which are no defined in functions: https://github.com/llvm/llvm-project/blob/bcd0bf9284db0d5d4697611ff9bf3243504aab07/clang/lib/Serialization/ASTCommon.cpp#L470-L485

So we can't find existing decls for lambdas so we can't merge them. This is what I wanted to say. And now I delete it since it may be confusing.

Few stylistic nits:

• most of tests in "clang/test/Modules" start with a lowercase and use kebab-naming-style (sometimes with underscores);
• can you please use more descriptive names in tests? Currently hunting for 1-character difference isn't fun and doesn't convey the purpose and intention of the test;
• is it possible to reuse some of the testing code because trying to find differences and what they mean is time-consuming.

Thanks for this. Let's do it after we get a consensus in the higher level.

Looks like not all branches in the added code are covered by tests but I need more time to play with the code.

Oh, I didn't test the coverage when developing. I'll check it when I look at this again.

Test case MergeLambdas3.cppm is unstable. Sometimes it passes but usually it fails.

Weird. What is the error message if it fails?

clang/lib/Serialization/ASTReaderDecl.cpp

2161–2198

Weird. MergeLambdas3.cppm should cover this. Let me try a double check.

2222

The original mergeRedeclarable in ASTDeclReader::VisitCXXRecordDeclImpl are the mergeRedeclarable with two parameters and it will call the mergeRedeclarable with 3 parameters if it found an existing declaration. So the relationship of the mergeLambda here and the mergeRedeclarable in ASTDeclReader::VisitCXXRecordDeclImpl is that they find different things and they will call the same method.

The original mergeRedeclarable in ASTDeclReader::VisitCXXRecordDeclImpl can't find existing lambdas for the reason I explained in the main thread.

And mergeLambda is called after we read the definition about lambdas and the original mergeRedeclarable in ASTDeclReader::VisitCXXRecordDeclImpl is called before we read the definitions since it mainly cares about the declaration instead of the definition.

[vsapsai]

In D140002#4000233, @ChuanqiXu wrote:

Test case MergeLambdas3.cppm is unstable. Sometimes it passes but usually it fails.

Weird. What is the error message if it fails?

error: 'error' diagnostics seen but not expected: 
  File /path/to/llvm/build/clang/relwithdebinfo/tools/clang/test/Modules/Output/MergeLambdas3.cppm.tmp/Use2.cpp Line 4: static assertion failed due to requirement '__is_same((lambda at /path/to/llvm/build/clang/relwithdebinfo/tools/clang/test/Modules/Output/MergeLambdas3.cppm.tmp/lambda.h:4:13), (lambda at /path/to/llvm/build/clang/relwithdebinfo/tools/clang/test/Modules/Output/MergeLambdas3.cppm.tmp/lambda.h:1:12))'

Also looks like this test fails in pre-commit checks too.

[ChuanqiXu]

In D140002#4000252, @vsapsai wrote:

In D140002#4000233, @ChuanqiXu wrote:

Test case MergeLambdas3.cppm is unstable. Sometimes it passes but usually it fails.

Weird. What is the error message if it fails?

error: 'error' diagnostics seen but not expected: 
  File /path/to/llvm/build/clang/relwithdebinfo/tools/clang/test/Modules/Output/MergeLambdas3.cppm.tmp/Use2.cpp Line 4: static assertion failed due to requirement '__is_same((lambda at /path/to/llvm/build/clang/relwithdebinfo/tools/clang/test/Modules/Output/MergeLambdas3.cppm.tmp/lambda.h:4:13), (lambda at /path/to/llvm/build/clang/relwithdebinfo/tools/clang/test/Modules/Output/MergeLambdas3.cppm.tmp/lambda.h:1:12))'

Also looks like this test fails in pre-commit checks too.

I reproduced it after I rebase onto main. Let me check what happened..

clang/lib/Serialization/ASTReaderDecl.cpp

public:
 
       template<typename T>
       operator T*() const { return dyn_cast_or_null<T>(Existing); }
     };
 
     static DeclContext *getPrimaryContextForMerging(ASTReader &Reader,
                                                     DeclContext *DC);
     FindExistingResult findExisting(NamedDecl *D);
+    FindExistingResult findExistingLambda(CXXRecordDecl *D);
 
   public:
     ASTDeclReader(ASTReader &Reader, ASTRecordReader &Record,
                   ASTReader::RecordLocation Loc,
                   DeclID thisDeclID, SourceLocation ThisDeclLoc)
         : Reader(Reader), Record(Record), Loc(Loc), ThisDeclID(thisDeclID),
           ThisDeclLoc(ThisDeclLoc) {}
 
public:
     void VisitEmptyDecl(EmptyDecl *D);
     void VisitLifetimeExtendedTemporaryDecl(LifetimeExtendedTemporaryDecl *D);
 
     std::pair<uint64_t, uint64_t> VisitDeclContext(DeclContext *DC);
 
     template<typename T>
     RedeclarableResult VisitRedeclarable(Redeclarable<T> *D);
 
+    void mergeLambda(CXXRecordDecl *D, RedeclarableResult &Redecl);
+
     template <typename T>
     void mergeRedeclarable(Redeclarable<T> *D, RedeclarableResult &Redecl);
 
     void mergeRedeclarableTemplate(RedeclarableTemplateDecl *D,
                                    RedeclarableResult &Redecl);
 
     template <typename T>
     void mergeRedeclarable(Redeclarable<T> *D, T *Existing,
void ASTDeclReader::ReadCXXRecordDefinition(CXXRecordDecl *D, bool Update) {
 
   // If this is not the first declaration or is an update record, we can have
   // other redeclarations already. Make a note that we need to propagate the
   // DefinitionData pointer onto them.
   if (Update || Canon != D)
     Reader.PendingDefinitions.insert(D);
 }
 
+/// In C++20, lambdas can have the same type conditionally.
+///
+/// [basic.def.odr]p14:
+///   For any definable item D with definitions in multiple translation units,
+///   - if the definitions in different translation units do not satisfy the
+///   following requirements,
+///     the program is ill-formed; ...
+///   - Each such definition shall not be attached to a named module.
+///   - Each such definition shall consist of the same sequence of tokens, where
+///   the definition of a closure type is considered to consist of the sequence
+///   of tokens of the corresponding lambda-expression.
+///   - In each such definition, except within the default arguments and default
+///   template arguments of D, corresponding lambda-expressions shall have the
+///   same closure type (see below).
+///   ...
+///
+/// This function checks if the two lambdas:
+/// - Lives in the same declaration context.
+/// - Have the same definition. We check this by ODR hash code.
+/// - If either of them is attached to a named module.
+/// - If they lives in the same TU.
+static bool IsMergeableLambda(ASTContext &C, CXXRecordDecl *X,
+                              CXXRecordDecl *Y) {
+  assert(X->isLambda() && Y->isLambda());
+  // ASTContext::isSameEntity will check the DeclContext while
+  // CXXRecordDecl::getODRHash will only calculate the hash value based on the
+  // declaration itself. So the check here is not redundant.
+  if (!C.isSameEntity(X, Y))
+    return false;
+
+  if (X->getODRHash() != Y->getODRHash())
+    return false;
+
+  // Check X and Y comes from different TU and neither of them comes from module
+  // purview.
+  Module *XM = X->getOwningModule();
+  Module *YM = Y->getOwningModule();
+
+  // In this context, when we talk about modules, we only talk about named
+  // modules. So ignore header like modules here.
+  if (XM && XM->isHeaderLikeModule())
+    XM = nullptr;
+  if (YM && YM->isHeaderLikeModule())
+    YM = nullptr;
+
+  // If either of them comes from module purview, we can't treat these lambdas
+  // as the same type.
+  if ((XM && XM->isModulePurview()) || (YM && YM->isModulePurview()))
+    return false;
+
+  // The left module should be global module only.
+  assert(!XM || XM->isGlobalModule());
+  assert(!YM || YM->isGlobalModule());
+
+  // We can treat them as the same type if they are not in the same TU.
+  return XM != YM;
+}
+
+ASTDeclReader::FindExistingResult
+ASTDeclReader::findExistingLambda(CXXRecordDecl *D) {
+  assert(D && D->isLambda());
+  assert(!TypedefNameForLinkage);
+
+  DeclContext *DC = D->getDeclContext()->getRedeclContext();
+  DeclContext *MergeDC = getPrimaryContextForMerging(Reader, DC);
+  // Not in a mergeable context.
+  if (!MergeDC)
+    return FindExistingResult(Reader);
+
+  /// FIXME: The `DeclContext::noload_lookup()` wouldn't load local lexical
+  /// lookups since unnamed declarations are skipped. We can find this in
+  /// `DeclContext::buildLookupImpl` and `shouldBeHidden(NamedDecl*)` in
+  /// DeclBase.cpp. So the `DeclContext::noload_lookup()` here can only find
+  /// decls during the deserilizations. For example:
+  ///
+  /// ```
+  /// import A; // contains a lambda definition in GMF.
+  /// import B; // contains a same lambda in GMF with the above one.
+  /// ```
+  ///
+  /// Assume we've read A and we are reading the lambda definition of B.
+  /// The lambda definition in A can be found by
+  /// `DeclContext::noload_lookup()` since we've already load the lambda
+  /// in A into the lookup cache of the corresponding declaration
+  /// context. We can find this one in `ASTDeclReader::VisitDecl`.
+  ///
+  /// However, it doesn't work for the following case:
+  ///
+  /// ```
+  /// auto l = [](){};
+  /// import B; // contains a same lambda in GMF with the above one.
+  /// ```
+  ///
+  /// Now the reader don't load the lambda into the lookup cache so the
+  /// reader don't know about it. So that we can't find the lambda
+  /// definition in the current TU now. So we misses the oppptunity to
+  /// merge the lambda definition.
+  /// To merge the lambda definition in the current TU, we have to iterate
+  /// the declaration in the current TU manually, which is not so efficiency.
+  /// If we can make `DeclContext::noload_lookup()` support unnamed untities
+  /// someday, we can remove `DeclContext::noload_decls()` here simply.
+  llvm::DenseSet<Decl *> PossibleRedecls;
+  for (Decl *NL : MergeDC->noload_lookup(D->getDeclName()))
+    PossibleRedecls.insert(NL);
+
+  for (Decl *ND : MergeDC->noload_decls())
+    PossibleRedecls.insert(ND);
+
+  for (Decl *Candidate : PossibleRedecls)
+    if (CXXRecordDecl *Existing = dyn_cast<CXXRecordDecl>(Candidate))
+      if (Existing->isLambda() &&
+          IsMergeableLambda(Reader.getContext(), Existing, D))
+        return FindExistingResult(Reader, D, Existing, AnonymousDeclNumber,
+                                  TypedefNameForLinkage);
+
+  return FindExistingResult(Reader, D, /*Existing=*/nullptr,
+                            AnonymousDeclNumber, TypedefNameForLinkage);
+}
+
+void ASTDeclReader::mergeLambda(CXXRecordDecl *D, RedeclarableResult &Redecl) {
+  // If C++20 modules are not available, there is no reason to perform this
+  // merge.
+  if (!Reader.getContext().getLangOpts().CPlusPlusModules)
+    return;
+
+  // If we're not the canonical declaration, we don't need to merge.
+  if (!D->isFirstDecl())
+    return;
+
+  if (TagDecl *Existing = findExistingLambda(D))
+    mergeRedeclarable(D, Existing, Redecl);
+}
+
 ASTDeclReader::RedeclarableResult
 ASTDeclReader::VisitCXXRecordDeclImpl(CXXRecordDecl *D) {
   RedeclarableResult Redecl = VisitRecordDeclImpl(D);
 
   ASTContext &C = Reader.getContext();
 
   enum CXXRecKind {
     CXXRecNotTemplate = 0, CXXRecTemplate, CXXRecMemberSpecialization
if (WasDefinition) {
     DeclID KeyFn = readDeclID();
     if (KeyFn && D->isCompleteDefinition())
       // FIXME: This is wrong for the ARM ABI, where some other module may have
       // made this function no longer be a key function. We need an update
       // record or similar for that case.
       C.KeyFunctions[D] = KeyFn;
   }
 
+  if (D->isLambda()) {
+    /// Lambdas shouldn't be templates.
+    /// Note that the record type of the generic lambdas are not templates.
+    /// The generic thing is the operator functions.
+    assert(!D->getDescribedClassTemplate() &&
+           !D->getMemberSpecializationInfo());
+    mergeLambda(D, Redecl);
+  }
+
   return Redecl;
 }
 
 void ASTDeclReader::VisitCXXDeductionGuideDecl(CXXDeductionGuideDecl *D) {
   D->setExplicitSpecifier(Record.readExplicitSpec());
   D->Ctor = readDeclAs<CXXConstructorDecl>();
   VisitFunctionDecl(D);
   D->setIsCopyDeductionCandidate(Record.readInt());

clang/test/Modules/MergeLambdas.cppm

+// RUN: rm -rf %t
+// RUN: mkdir -p %t
+// RUN: split-file %s %t
+//
+// RUN: %clang_cc1 -std=c++20 %t/A.cppm -emit-module-interface -o %t/A.pcm
+// RUN: %clang_cc1 -std=c++20 %t/B.cppm -emit-module-interface -o %t/B.pcm
+// RUN: %clang_cc1 -std=c++20 -fprebuilt-module-path=%t %t/Use.cpp \
+// RUN:     -fsyntax-only -verify
+
+//--- lambda.h
+auto cmp = [](auto l, auto r) {
+  return l < r;
+};
+
+//--- A.cppm
+module;
+#include "lambda.h"
+
+export module A;
+export auto c1 = cmp;
+export using ::cmp;
+
+//--- B.cppm
+module;
+#include "lambda.h"
+
+export module B;
+export auto c2 = cmp;
+export using ::cmp;
+
+//--- Use.cpp
+// expected-no-diagnostics
+import A;
+import B;
+
+static_assert(__is_same(decltype(c1), decltype(c2)));
+auto use() {
+    return cmp(4, 6); // cmp shouldn't ambiguous.
+}

clang/test/Modules/MergeLambdas2.cppm

+// RUN: rm -rf %t
+// RUN: mkdir -p %t
+// RUN: split-file %s %t
+//
+// RUN: %clang_cc1 -std=c++20 %t/A.cppm -emit-module-interface -o %t/A.pcm
+// RUN: %clang_cc1 -std=c++20 %t/B.cppm -emit-module-interface -o %t/B.pcm
+// RUN: %clang_cc1 -std=c++20 -fprebuilt-module-path=%t %t/Use.cpp \
+// RUN:     -fsyntax-only -verify
+
+//--- lambda_A.h
+auto cmp = [](auto l, auto r) {
+  return l < r;
+};
+
+//--- lambda_B.h
+auto cmp = [](auto l, auto r) {
+  return l > r;
+};
+
+//--- A.cppm
+module;
+#include "lambda_A.h"
+
+export module A;
+export auto c1 = cmp;
+export using ::cmp;
+
+//--- B.cppm
+module;
+#include "lambda_B.h"
+
+export module B;
+export auto c2 = cmp;
+export using ::cmp;
+
+//--- Use.cpp
+import A;
+import B;
+
+static_assert(!__is_same(decltype(c1), decltype(c2)));
+auto use() {
+    return cmp(4, 6); // expected-error {{reference to 'cmp' is ambiguous}}
+                      // expected-note@* 1+{{candidate found by name lookup is 'cmp'}}
+}

clang/test/Modules/MergeLambdas3.cppm

+// RUN: rm -rf %t
+// RUN: mkdir -p %t
+// RUN: split-file %s %t
+//
+// RUN: %clang_cc1 -std=c++20 %t/A.cppm -emit-module-interface -o %t/A.pcm
+// RUN: %clang_cc1 -std=c++20 %t/B.cppm -emit-module-interface -o %t/B.pcm
+// RUN: %clang_cc1 -std=c++20 -fprebuilt-module-path=%t %t/Use.cpp \
+// RUN:     -fsyntax-only -verify
+//
+// RUN: %clang_cc1 -std=c++20 %t/C.cppm -emit-module-interface -o %t/C.pcm
+// RUN: %clang_cc1 -std=c++20 -fprebuilt-module-path=%t %t/Use2.cpp \
+// RUN:     -fsyntax-only -verify
+//
+// FIXME: We need to handle the Use3 case in Sema part.
+// RUNX: %clang_cc1 -std=c++20 -fprebuilt-module-path=%t %t/Use3.cpp \
+// RUNX:     -fsyntax-only -verify
+
+//--- lambda.h
+auto cmp = [](auto l, auto r) {
+  return l < r;
+};
+auto cmp2 = [](auto l, auto r) {
+  return l < r;
+};
+
+//--- A.cppm
+module;
+#include "lambda.h"
+export module A;
+export auto a1 = [](auto l, auto r) {
+  return l < r;
+};
+
+export auto a2 = [](auto l, auto r) {
+  return l < r;
+};
+// export using ::cmp;
+export using ::cmp2;
+
+//--- B.cppm
+module;
+#include "lambda.h"
+export module B;
+export auto b1 = [](auto l, auto r) {
+  return l < r;
+};
+export auto b2 = [](auto l, auto r) {
+  return l < r;
+};
+// export using ::cmp;
+export using ::cmp2;
+
+//--- Use.cpp
+// expected-no-diagnostics
+import A;
+import B;
+
+static_assert(!__is_same(decltype(a1), decltype(b1)));
+// static_assert(!__is_same(decltype(a1), decltype(cmp)));
+// static_assert(!__is_same(decltype(b1), decltype(cmp)));
+static_assert(!__is_same(decltype(a1), decltype(a2)));
+static_assert(!__is_same(decltype(b1), decltype(b2)));
+// static_assert(!__is_same(decltype(cmp), decltype(cmp2)));
+
+//--- C.cppm
+module;
+#include "lambda.h"
+export module C;
+export auto c = cmp;
+
+//--- Use2.cpp
+// expected-no-diagnostics
+#include "lambda.h"
+import C;
+static_assert(__is_same(decltype(c), decltype(cmp)));
+
+//--- Use3.cpp
+// FIXME: This is not handled now. We need to handle the case in
+// Sema part.
+// expected-no-diagnostics
+// import C;
+// #include "lambda.h"
+// static_assert(__is_same(decltype(c), decltype(cmp)));
+// auto use() {
+//     return cmp(4, 6); // cmp shouldn't ambiguous.
+// }