[ASTImporter] Re-odering by lexical order for all imported decls within record

[danix800]

Summary

Revision https://reviews.llvm.org/D154764 is still not complete. An extra reordering is
needed for lexical order of all imported decls within a record. The final algorithm could
be summarized as the following:

1. Import all fields that'll be part of the layout;
2. Sort these fields to ensure correct layout;
3. Import everything else;
4. Final re-ordering by lexical order.

Fixes https://github.com/llvm/llvm-project/issues/64165

[shafik]

clang/lib/AST/ASTImporter.cpp

1950

If ToDC does not contain the decl is that a problem, what case do we expect this to happen? Do we test that case?

[danix800]

After thought a little bit more I'm doubting whether this lexical ordering is of any practical usage or any meanfullness at all,
especially when imported into existing (non-empty) context, reordering by From context can not be correct after merging
occured.

I need more comment on this before I close it.

clang/lib/AST/ASTImporter.cpp

       continue;
 
     ExpectedDecl ImportedOrErr = import(From);
     if (!ImportedOrErr)
       HandleChildErrors.handleChildImportResult(ChildErrors,
                                                 ImportedOrErr.takeError());
   }
 
+  // Finally re-order everything by lexical order.
+  for (auto *D : FromDC->decls()) {
+    assert(D && "DC contains a null decl");
+    if (Decl *ToD = Importer.GetAlreadyImportedOrNull(D);
+        ToD && ToDC == ToD->getLexicalDeclContext() &&
+        ToDC->containsDecl(ToD)) {
+      ToDC->removeDecl(ToD);
+      ToDC->addDeclInternal(ToD);
+    }
+  }
+
   return ChildErrors;
 }
 
 Error ASTNodeImporter::ImportFieldDeclDefinition(const FieldDecl *From,
                                                  const FieldDecl *To) {
   RecordDecl *FromRecordDecl = nullptr;
   RecordDecl *ToRecordDecl = nullptr;
   // If we have a field that is an ArrayType we need to check if the array

clang/unittests/AST/ASTImporterTest.cpp

   Pattern = translationUnitDecl(has(classTemplateDecl(
       hasName("Base"), has(classTemplateSpecializationDecl()))));
   ASSERT_TRUE(
       MatchVerifier<Decl>{}.match(From->getTranslationUnitDecl(), Pattern));
   EXPECT_TRUE(
       MatchVerifier<Decl>{}.match(To->getTranslationUnitDecl(), Pattern));
 }
 
-AST_MATCHER_P(RecordDecl, hasFieldOrder, std::vector<StringRef>, Order) {
+AST_MATCHER_P(RecordDecl, hasLexicalOrder, std::vector<StringRef>, Order) {
   size_t Index = 0;
   for (Decl *D : Node.decls()) {
-    if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) {
-      auto *ND = cast<NamedDecl>(D);
+    if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D) || !D->isImplicit()) {
+      NamedDecl *ND = nullptr;
+      if (isa<NamedDecl>(D))
+        ND = cast<NamedDecl>(D);
+      else if (auto *Friend = dyn_cast<FriendDecl>(D);
+               Friend && !(ND = Friend->getFriendDecl()))
+        ND = Friend->getFriendType()->getType()->getAsRecordDecl();
+      if (!ND)
+        return false;
       if (Index == Order.size())
         return false;
       if (ND->getName() != Order[Index])
         return false;
       ++Index;
     }
   }
   return Index == Order.size();

        CXXRecordDeclFieldsShouldBeInCorrectOrder) {
   Decl *From, *To;
   std::tie(From, To) =
       getImportedDecl(
           "struct declToImport { int a; int b; };",
                       Lang_CXX11, "", Lang_CXX11);
 
   MatchVerifier<Decl> Verifier;
-  ASSERT_TRUE(Verifier.match(From, cxxRecordDecl(hasFieldOrder({"a", "b"}))));
-  EXPECT_TRUE(Verifier.match(To, cxxRecordDecl(hasFieldOrder({"a", "b"}))));
+  ASSERT_TRUE(Verifier.match(From, cxxRecordDecl(hasLexicalOrder({"a", "b"}))));
+  EXPECT_TRUE(Verifier.match(To, cxxRecordDecl(hasLexicalOrder({"a", "b"}))));
 }
 
 TEST_P(ASTImporterOptionSpecificTestBase,
        CXXRecordDeclFieldOrderShouldNotDependOnImportOrder) {
   Decl *From, *To;
   std::tie(From, To) = getImportedDecl(
       // The original recursive algorithm of ASTImporter first imports 'c' then
       // 'b' and lastly 'a'.  Therefore we must restore the order somehow.
       R"s(
       struct declToImport {
           int a = c + b;
           int b = 1;
           int c = 2;
       };
       )s",
       Lang_CXX11, "", Lang_CXX11);
 
+  auto Pattern = cxxRecordDecl(hasLexicalOrder({"a", "b", "c"}));
   MatchVerifier<Decl> Verifier;
-  ASSERT_TRUE(
-      Verifier.match(From, cxxRecordDecl(hasFieldOrder({"a", "b", "c"}))));
-  EXPECT_TRUE(
-      Verifier.match(To, cxxRecordDecl(hasFieldOrder({"a", "b", "c"}))));
+  ASSERT_TRUE(Verifier.match(From, Pattern));
+  EXPECT_TRUE(Verifier.match(To, Pattern));
+}
+
+TEST_P(ASTImporterOptionSpecificTestBase, CXXRecordDeclCorrectLexicalOrder) {
+  Decl *From, *To;
+  std::tie(From, To) = getImportedDecl(
+      R"s(
+      struct declToImport {
+        int a = c;
+        void b() { d(); }
+        int c = 1;
+        void d();
+        friend class e;
+        int f = 2;
+        enum {
+          g, h
+        };
+        class I {};
+        enum J {
+          k, l
+        };
+        template<class T> class M;
+      };
+      )s",
+      Lang_CXX11, "", Lang_CXX11);
+
+  auto Pattern = cxxRecordDecl(
+      hasLexicalOrder({"a", "b", "c", "d", "e", "f", "", "I", "J", "M"}));
+  MatchVerifier<Decl> Verifier;
+  ASSERT_TRUE(Verifier.match(From, Pattern));
+  EXPECT_TRUE(Verifier.match(To, Pattern));
 }
 
 TEST_P(ASTImporterOptionSpecificTestBase,
        CXXRecordDeclFieldAndIndirectFieldOrder) {
   Decl *From, *To;
   std::tie(From, To) = getImportedDecl(
-      // First field is "a", then the field for unnamed union, then "b" and "c"
-      // from it (indirect fields), then "d".
       R"s(
       struct declToImport {
         int a = d;
         union { 
           int b;
           int c;
         };
         int d;
       };
       )s",
       Lang_CXX11, "", Lang_CXX11);
 
+  auto Pattern = cxxRecordDecl(hasLexicalOrder({"a", "", /* anonymous union */
+                                                "",      /* implicit field */
+                                                "b",     /* indirect field */
+                                                "c",     /* indirect field */
+                                                "d"}));
   MatchVerifier<Decl> Verifier;
-  ASSERT_TRUE(Verifier.match(
-      From, cxxRecordDecl(hasFieldOrder({"a", "", "b", "c", "d"}))));
-  EXPECT_TRUE(Verifier.match(
-      To, cxxRecordDecl(hasFieldOrder({"a", "", "b", "c", "d"}))));
+  ASSERT_TRUE(Verifier.match(From, Pattern));
+  EXPECT_TRUE(Verifier.match(To, Pattern));
 }
 
 TEST_P(ASTImporterOptionSpecificTestBase, ShouldImportImplicitCXXRecordDecl) {
   Decl *From, *To;
   std::tie(From, To) = getImportedDecl(
       R"(
       struct declToImport {
       };

 
 TEST_P(ImportDecl, ImportFieldOrder) {
   MatchVerifier<Decl> Verifier;
   testImport("struct declToImport {"
              "  int b = a + 2;"
              "  int a = 5;"
              "};",
              Lang_CXX11, "", Lang_CXX11, Verifier,
-             recordDecl(hasFieldOrder({"b", "a"})));
+             recordDecl(hasLexicalOrder({"b", "a"})));
 }
 
 const internal::VariadicDynCastAllOfMatcher<Expr, DependentScopeDeclRefExpr>
     dependentScopeDeclRefExpr;
 
 TEST_P(ImportExpr, DependentScopeDeclRefExpr) {
   MatchVerifier<Decl> Verifier;
   testImport("template <typename T> struct S { static T foo; };"