[ASTImporter] Reorder fields after structure import is finished

[martong]

Summary

There are multiple reasons why field structures can be imported in wrong way. The simplest is the ability of field initializers and method bodies to refer fields not in order they are listed in. Unfortunately, there is no clean solution for that currently so I'm leaving a FIXME.

[xazax.hun]

Hi Aleksei!

Just a minor high level note. If https://reviews.llvm.org/D32947 will be accepted once, we will need to reorder friends as well. Or alternatively, we have to omit the check of friends in structural equivalence in https://reviews.llvm.org/D32947.

[a.sidorin]

Hi Gabor,

Just a minor high level note. If https://reviews.llvm.org/D32947 will be accepted once, we will need to reorder friends as well. Or alternatively, we have to omit the check of friends in structural equivalence in https://reviews.llvm.org/D32947.

I'd prefer to land D32947 before the fix for friend decls reordering so we will have a subject for testing. And the fix for friend decls can become a separate patch. Do you already have such patch or a test for the issue?

[martong]

Aleksei,

We should definitely try to synchronize our work between Samsung (?) and Ericsson much much more.
Unfortunately, it is often we work on the same issue and this can cause delays for both of us.
Actually, we solved the same issue in our branch a year ago, see
https://github.com/Ericsson/clang/blob/ctu-clang5/lib/AST/ASTImporter.cpp#L1087 and the related test:
https://github.com/Ericsson/clang/blob/ctu-clang5/unittests/AST/ASTImporterTest.cpp#L1365

Gabor

[a.sidorin]

Ping.

[martong]

Hi Aleksei,

I am OK with this, I just have a little concern about friend declarations. Since D32947 ( [ASTImporter] FriendDecl importing improvements ) records' structural equivalency depends on the order of their friend declarations.
Anyway, I think friend related issues can be addressed in a separate patch.

What is a bit more concerning is that *ToField can be null and we should handle that.
This could happen if lookup finds the type of the field, but for some reason (e.g. there is an error in structural eq, or the redecl chain is incorrect) it turns out to be non-equivalent with the type of the FromField:

for (auto *FoundDecl : FoundDecls) {
  if (auto *FoundField = dyn_cast<FieldDecl>(FoundDecl)) {
    // For anonymous fields, match up by index.
    if (!Name && getFieldIndex(D) != getFieldIndex(FoundField))
      continue;

    if (Importer.IsStructurallyEquivalent(D->getType(),
                                          FoundField->getType())) {
      Importer.Imported(D, FoundField);
      return FoundField;
    }

    Importer.ToDiag(Loc, diag::err_odr_field_type_inconsistent)
      << Name << D->getType() << FoundField->getType();
    Importer.ToDiag(FoundField->getLocation(), diag::note_odr_value_here)
      << FoundField->getType();
    return nullptr;
  }
}

lib/AST/ASTImporter.cpp

1025 ↗

(On Diff #137034)

Could use auto here, to avoid redundant type specification.

1029 ↗

(On Diff #137034)

Can't we just import the FromRD, why we need that cast at the end?
auto *ToRD = cast<RecordDecl>(Importer.Import(FromRD)));

1032 ↗

(On Diff #137034)

I think ToField can be a nullptr, and if so, then ToField->getDeclContext() is UB.
Same could happen at line 1040.
Perhaps we should have and explicit check about the nullptr value:
if (!ToField) continue;

unittests/AST/ASTImporterTest.cpp

1022 ↗

(On Diff #137034)

The hasFieldOrder matcher is already existing.

1034 ↗

(On Diff #137034)

We already have this test, we just have to enable it.
DISABLED_CXXRecordDeclFieldOrderShouldNotDependOnImportOrder

[martong]

Ping

[a_sidorin]

All declarations are reordered now, not only fields. Also some review comments were addressed.

[a_sidorin]

lib/AST/ASTImporter.cpp

1029 ↗

(On Diff #137034)

We need to cast it to DeclContext anyway, so I don't think that a narrower type will be worse

1032 ↗

(On Diff #137034)

I have added a check for the return result into the import loop. So, after the import is finished, all nested decls should be non-null.

[martong]

lib/AST/ASTImporter.cpp

1317 ↗

(On Diff #160477)

Is it sure that ToD will never be a nullptr?
I think, removeDecl or addDeclInternal below may crash if we call it with a nullptr.
Also in the assert, ToD->getDeclContext() seems achy if ToD is a nullptr.

[a_sidorin]

lib/AST/ASTImporter.cpp

1317 ↗

(On Diff #160477)

We have an early return if such import failed before (line 1300).

[martong]

lib/AST/ASTImporter.cpp

1317 ↗

(On Diff #160477)

Okay, that line did not catch my attention. Could you please provide a comment which describes that at this point we expect ToD to be non-null, or even better, we could have an explicit assert(ToD) .

[martong]

Ping. This is still not committed, however, essential for ctu analyse any C++ project. Aleksei, I am happy to commit it for you if you don't have time, just let me know.

[a_sidorin]

Hi Gabor,
I have tried to rebase it last week but there were some test failures. I hope to fix them this weekend and finally commit the patch.

[davide]

This patch broke lldb, at least on MacOS.
You can reproduce the issue building lldb, applying your patch and then running

$ ./lldb-dotest -p TestCModules

I'm going to revert this to unblock folks, but don't hesitate to ping me in case you need any help reproducing the issue.
cc: @shafik

[a_sidorin]

Oops. Thank you Davide!

[martong]

Hi Davide,

I'd like to draw your attention to an important relation of this patch to a bug in LLDB which manifests as incorrect vtable layouts for LLDB expression code.
Please see the conversation started with this message: https://lists.llvm.org/pipermail/cfe-dev/2018-August/058842.html
I think that the solution to that problem would be exactly this patch, i.e. to put the methods in the proper order during import.

Are the failing lldb tests related to ObjC code?

[a.sidorin]

Hello everyone.
@martong : this version of patch reorders only fields and friends. No method reordering is done (I can check if it works, though, and add the feature).
@davide: Unfortunately, I was not able to reproduce the problem on Linux. Could you please provide a link to a buildbot failure or some environment description so I can reproduce the issue or, at least, take a look?

[davide]

No worries :) l

In D44100#1282148, @martong wrote:

Hi Davide,

I'd like to draw your attention to an important relation of this patch to a bug in LLDB which manifests as incorrect vtable layouts for LLDB expression code.
Please see the conversation started with this message: https://lists.llvm.org/pipermail/cfe-dev/2018-August/058842.html
I think that the solution to that problem would be exactly this patch, i.e. to put the methods in the proper order during import.

Are the failing lldb tests related to ObjC code?

Some of them are, see e.g. http://lab.llvm.org:8080/green/view/LLDB/job/lldb-cmake/11972/console
@shafik is the person who's driving better lldb C++ support on our side, so you might consider chatting with him about this.
I just got the bots in a greener state again.

[davide]

In D44100#1282157, @a.sidorin wrote:

Hello everyone.
@martong : this version of patch reorders only fields and friends. No method reordering is done (I can check if it works, though, and add the feature).
@davide: Unfortunately, I was not able to reproduce the problem on Linux. Could you please provide a link to a buildbot failure or some environment description so I can reproduce the issue or, at least, take a look?

http://lab.llvm.org:8080/green/view/LLDB/job/lldb-cmake/11972/console
It's unfortunate because this doesn't show a backtrace. I'm afraid at this point the easiest way to reproduce this is on MacOS directly.

[shafik]

I am happy to discuss and review a revised version of this change.

[a_sidorin]

Hi @davide and @shafik,
Could you please check the updated version of the patch?

[davide]

Alexsei, I'm afraid I'm not qualified to review this patch. I would really recommend you to find somebody who's familiar with clang to review it, as it already seems to have broken lldb in the past.

[a_sidorin]

Hi Davide,

I don't mean only review. As I guess, you guys have MacOS machines so you can check if the problem is still present in the updated version.
There is no need to remind me about the problem with LLDB since I tried to resolve it.

[aprantl]

In D44100#1302478, @a_sidorin wrote:

I don't mean only review. As I guess, you guys have MacOS machines so you can check if the problem is still present in the updated version.

FYI, typically problems with ASTImporter in LLDB are not macOS-specific at all and also reproduce when building LLDB for Linux. You can just check out LLDB into the llvm/tools directory and run ninja && ninja check-lldb

[a_sidorin]

Hi Adrian,
I've already done check-all (this includes LLDB) with this patch. As you can see in this thread, I didn't manage to reproduce some issues on Linux. Luckily, one test still failed on Linux so I could find the problem. However , it will be good to ensure that this is the same problem that caused failures on MacOS and the commit will be safe. That's why I asked for an additional check.

[martong]

Alexei,

I had a chance to have a quick look into this on a borrowed Mac Book. Seems like the assertion which was related to the revert is not existent anymore, but a new assertion came in. Next week I'll have time to debug that and I'll come back to you with what I find.

[a_sidorin]

Hi Gabor,
Thank you for digging into this! Unfortunately, I don't have any MacOS device and I cannot check my code for the compatibility.

[martong]

Hey Alexey,

Here is what I found so far:
The new assertion is this:

Assertion failed: (ToRD == ToD->getDeclContext() && ToRD->containsDecl(ToD)), function ImportDeclContext

ToRD looks like this in code:

typedef struct __sFILE {
   // several fields here ...
} FILE;

And the AST:

CXXRecordDecl 0x7f87ce97d488 </Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk/usr/include/_stdio.h:126:9, col:16> col:16 struct __sFILE definition
|-DefinitionData pass_in_registers aggregate standard_layout trivially_copyable pod trivial literal
| |-DefaultConstructor exists trivial needs_implicit
| |-CopyConstructor simple trivial has_const_param needs_implicit implicit_has_const_param
| |-MoveConstructor exists simple trivial needs_implicit
| |-CopyAssignment trivial has_const_param needs_implicit implicit_has_const_param
| |-MoveAssignment exists simple trivial needs_implicit
| `-Destructor simple irrelevant trivial needs_implicit
|-CXXRecordDecl 0x7f87d1886000 <col:9, col:16> col:16 implicit struct __sFILE
| `-<undeserialized declarations>
`-<undeserialized declarations>

I dug deeper and this is because ToRD is not equal with ToD->getDeclContext().
However, if I load the fields of ToRD and then dump it seems to be structurally equivalent with ToD->getDeclContext().
Both ToRD and ToD->getDeclContext() are part of a Decl chain with one element, this is true for FromRD and D->getDeclContext(). So I suspect some sort of lookup problem here: first we import the declContext during the import of a field, then when we do auto ImportedDC = import(cast<Decl>(FromDC)); where we fail to find the first imported DeclContext. I suspect that this is because typedef hides the real struct, I mean __sFILE seems to be not find-able by normal C lookup (ie. it is hidden).

Here is one workaround (I did not try it yet):
We could lazy initialize ToRD inside the for loop to be equal to the first 'ToD`'s decl context.

RecordDecl *ToRD = nullptr;
for (auto *D : FromRD->decls()) {
  if (isa<FieldDecl>(D) || isa<FriendDecl>(D)) {
    Decl *ToD = Importer.GetAlreadyImportedOrNull(D);
    if (!ToRD)
        ToRD = ToD->getDeclContext();
    ToRD->removeDecl(ToD);
  }
}

I am afraid I can continue with the debug only next week.

[a_sidorin]

Hi Gabor,
Thank you for the investigation! I'll try to take a look.

[martong]

@a_sidorin

The below diff on top of your patch successfully handles the failure with the TestCModules.py LLDB testcase:

diff --git a/lib/AST/ASTImporter.cpp b/lib/AST/ASTImporter.cpp
index 05fec7f943..e6fb590025 100644
--- a/lib/AST/ASTImporter.cpp
+++ b/lib/AST/ASTImporter.cpp
@@ -1695,15 +1695,22 @@ ASTNodeImporter::ImportDeclContext(DeclContext *FromDC, bool ForceImport) {
   // LoadFieldsFromExternalStorage().
   auto ImportedDC = import(cast<Decl>(FromDC));
   assert(ImportedDC);
-  auto *ToRD = cast<RecordDecl>(*ImportedDC);
+  RecordDecl *ToRD = nullptr;
   for (auto *D : FromRD->decls()) {
     if (isa<FieldDecl>(D) || isa<FriendDecl>(D)) {
       Decl *ToD = Importer.GetAlreadyImportedOrNull(D);
-      assert(ToRD == ToD->getDeclContext() && ToRD->containsDecl(ToD));
-      ToRD->removeDecl(ToD);
+      if (!ToRD)
+        ToRD = cast<RecordDecl>(ToD->getDeclContext());
+      else
+        assert(ToRD == ToD->getDeclContext());
+      if(ToRD->containsDecl(ToD))
+        ToRD->removeDecl(ToD);
     }
   }

+  if (!ToRD)
+    return Error::success();
+
   if (!ToRD->hasExternalLexicalStorage())
     assert(ToRD->field_empty());

[martong]

This comment was removed by martong.

[martong]

Alexey, good news! I have finished the testing of the above patch applied on top of 174545. Neither is a regression on Linux nor on macOS. (ASTTests, check-clang-astmerge, check-clang-import, check-clang-analysis, check-lldb).

[a_sidorin]

Hi Gabor, thank you a lot!
I have to say that even having your patch, I still don't understand why the patch fixes the problem (and what the problem is). As I see, the patch handles the cases where some fields or friends have DeclContext different from ToRD. Could you please provide examples so I can add them to the test suite or, at least, just investigate?

[martong]

Alexey, simply put, the crux of the problem is this:
The imported decl context is different than what we get by calling the getDeclContext() on an imported field/friend of the "from" decl context.

With other words:
import(cast<Decl>(FromDC) gives us a different value than what we get from ToD->getDeclContext() inside the for loop which iterates over the fields/friends of FromDC.

This seems abnormal, because we would expect the two to be equal. This is why I suspect something related to an LLDB specific use case (and what's worse it happens only on macOS). In LLDB, I have seen they first do a minimal import then they require the definition with ASTImporter::importDefinition (but I am not sure if this is the real root cause here). I guess this is a scenario we don't have any unittest neither lit tests for in Clang. In an ideal world we should fix this inequivalence first and then could we apply this patch.

The workaround I provided is to use the decl context of the first imported field and use that as target decl context (and not use the decl context given by import(FromDC)).

Hope this helps

[aprantl]

lib/AST/ASTImporter.cpp

1672 ↗

(On Diff #174545)

this else is redundant.

1696 ↗

(On Diff #174545)

Can you add a comment explaining why this function named ...OrNull never returns a nullptr?

1703 ↗

(On Diff #174545)

assert(ToRD->hasExternalLexicalStorage() || ToRD->field_empty());

1708 ↗

(On Diff #174545)

This is redundant with the next assertion.

1712 ↗

(On Diff #174545)

ditto

[martong]

Rebase to master.
There was a conflict in the tests, in ASTImporterTest.cpp.

[martong]

@a_sidorin Aleksei, If you don't mind, I am going to investigate this further with macOS/LLDB and try to answer Adrian's comments too.

[a_sidorin]

Thank you for digging into this! Feel free to ask me if you encounter any problems with the patch.

[shafik]

Done with first round.

lib/AST/ASTImporter.cpp

1643 ↗

(On Diff #189830)

What cases are failed import of a field ok? Is that because we will get the field later on by another path?

1655 ↗

(On Diff #189830)

vitable?

1663 ↗

(On Diff #189830)

Maybe a comment here explaining the purpose of the loops below. IIUC removing fields since they may have been imported in the wrong order and then adding them back in what should be the correct order now.

1674 ↗

(On Diff #189830)

Are we sure ToD is never a nullptr b/c you are unconditionally derefenecing it here.

1679 ↗

(On Diff #189830)

Can you add a comment explaining why if the Decl has ExternalLexicalStorage the fields might not be empty even though we just removed them?

[martong]

• Address Shafik's comments and update assertions

[martong]

lib/AST/ASTImporter.cpp

1643 ↗

(On Diff #189830)

The decl context of which we import the contained decls (FromDC) may be a namespace, it is not necessarily a RecordDecl.
I guess it would be too drastic if a whole namespace is rendered as erroneous if just one contained decl import failed.

1655 ↗

(On Diff #189830)

My guess is vital.

1674 ↗

(On Diff #189830)

Yes, I agree. Added assert(ToD) because we had imported all contained decls previously without errors.

1674 ↗

(On Diff #189830)

assert(ToRD == ToD->getDeclContext() is not correct here, because friends semantic decl context may not be the befriending class. Changed to compare against the lexical DC.

1679 ↗

(On Diff #189830)

We removed only those fields which we have imported from the FromDC. We did not remove all the decls of ToRD. And we don't want to remove any fields which may be loaded from an external storage.
The reason is that field_empty would call field_begin which would call LoadFieldsFromExternalStorage which in turn would call ASTImporter::Import. This is because the ExternalASTSource interface in LLDB is implemented by the means of the ASTImporter. However, calling an import at this point would result in an uncontrolled import, we must avoid that.

1686 ↗

(On Diff #189830)

I removed this assert, because friends most usually have a different semantic context than the befriending class.

[martong]

• Rebase to master
• Some refactor is done mostly because since D63603 ([ASTImporter] Propagate

error from ImportDeclContext) we may not imported successfully all decls of a
DC.

• Made the code simpler and shorter by adding a local vector to hold the decls

of the "from" DC in the original order.

[martong]

• Further simplify by removing the last for loop

[martong]

@a_sidorin, @shafik This is a polite Ping.

[a_sidorin]

Hi Gabor,
Thank you again for working on this patch. I think it can be committed after minor stylish issues are fixed.

clang/lib/AST/ASTImporter.cpp

1677

Two spaces after dot.

1685

Could you please add a newline after return?

1696

"DC contains a null decl"?

clang/unittests/AST/ASTImporterTest.cpp

5254

A redundant newline?

[martong]

• Address Alexei's comments

clang/unittests/AST/ASTImporterTest.cpp

5254

Yes, I deleted that. And moved the test case closer the the last ImportDecl test case.

[shafik]

LGTM

[martong]

Jenkins is green: http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/31743/

The previous build caught up the change, but
http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/31742/ was stopped, perhaps a test got stucked.

clang/lib/AST/ASTImporter.cpp

ASTNodeImporter::ImportDeclContext(DeclContext *FromDC, bool ForceImport) {
   // appropriate error handling strategy for their needs.  For instance,
   // they may not want to mark an entire namespace as erroneous merely
   // because there is an ODR error with two typedefs.  As another example,
   // the client may allow EnumConstantDecls with same names but with
   // different values in two distinct translation units.
   bool AccumulateChildErrors = isa<TagDecl>(FromDC);
 
   Error ChildErrors = Error::success();
-  llvm::SmallVector<Decl *, 8> ImportedDecls;
   for (auto *From : FromDC->decls()) {
     ExpectedDecl ImportedOrErr = import(From);
     if (!ImportedOrErr) {
       if (AccumulateChildErrors)
         ChildErrors =
             joinErrors(std::move(ChildErrors), ImportedOrErr.takeError());
       else
         consumeError(ImportedOrErr.takeError());
     }
   }
 
+  // We reorder declarations in RecordDecls because they may have another order
+  // in the "to" context than they have in the "from" context. This may happen
+  // e.g when we import a class like this:
+  //    struct declToImport {
+  //        int a = c + b;
+  //        int b = 1;
+  //        int c = 2;
+  //    };
+  // During the import of `a` we import first the dependencies in sequence,
+  // thus the order would be `c`, `b`, `a`. We will get the normal order by
+  // first removing the already imported members and then adding them in the
+  // order as they apper in the "from" context.
+  //
+  // Keeping field order is vital because it determines structure layout.
+  //
+  // Here and below, we cannot call field_begin() method and its callers on
+  // ToDC if it has an external storage. Calling field_begin() will
+  // automatically load all the fields by calling
+  // LoadFieldsFromExternalStorage(). LoadFieldsFromExternalStorage() would
+  // call ASTImporter::Import(). This is because the ExternalASTSource
+  // interface in LLDB is implemented by the means of the ASTImporter. However,
+  // calling an import at this point would result in an uncontrolled import, we
+  // must avoid that.
+  const auto *FromRD = dyn_cast<RecordDecl>(FromDC);
+  if (!FromRD)
+    return ChildErrors;
+
+  auto ToDCOrErr = Importer.ImportContext(FromDC);
+  if (!ToDCOrErr) {
+    consumeError(std::move(ChildErrors));
+    return ToDCOrErr.takeError();
+  }
+
+  DeclContext *ToDC = *ToDCOrErr;
+  // Remove all declarations, which may be in wrong order in the
+  // lexical DeclContext and then add them in the proper order.
+  for (auto *D : FromRD->decls()) {
+    if (isa<FieldDecl>(D) || isa<FriendDecl>(D)) {
+      assert(D && "DC contains a null decl");
+      Decl *ToD = Importer.GetAlreadyImportedOrNull(D);
+      // Remove only the decls which we successfully imported.
+      if (ToD) {
+        assert(ToDC == ToD->getLexicalDeclContext() && ToDC->containsDecl(ToD));
+        // Remove the decl from its wrong place in the linked list.
+        ToDC->removeDecl(ToD);
+        // Add the decl to the end of the linked list.
+        // This time it will be at the proper place because the enclosing for
+        // loop iterates in the original (good) order of the decls.
+        ToDC->addDeclInternal(ToD);
+      }
+    }
+  }
+
   return ChildErrors;
 }
 
 Error ASTNodeImporter::ImportDeclContext(
     Decl *FromD, DeclContext *&ToDC, DeclContext *&ToLexicalDC) {
   auto ToDCOrErr = Importer.ImportContext(FromD->getDeclContext());
   if (!ToDCOrErr)
     return ToDCOrErr.takeError();

clang/unittests/AST/ASTImporterTest.cpp

std::tie(From, To) =
                       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"}))));
 }
 
 TEST_P(ASTImporterOptionSpecificTestBase,
-       DISABLED_CXXRecordDeclFieldOrderShouldNotDependOnImportOrder) {
+       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;
TEST_P(ImportDecl, ImportEnumSequential) {
 
   // For different import order, result should be the same.
   testImportSequence(
       Samples, {ImportMoo, ImportFoo}, // "moo", them "foo".
       // Check that there is only one enum decl in the result AST.
       "main.c", enumDecl(), VerificationMatcher);
 }
 
+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"})));
+}
+
 const internal::VariadicDynCastAllOfMatcher<Expr, DependentScopeDeclRefExpr>
     dependentScopeDeclRefExpr;
 
 TEST_P(ImportExpr, DependentScopeDeclRefExpr) {
   MatchVerifier<Decl> Verifier;
   testImport("template <typename T> struct S { static T foo; };"
              "template <typename T> void declToImport() {"
              "  (void) S<T>::foo;"

 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportVariables,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, LLDBLookupTest,
                         DefaultTestValuesForRunOptions, );
 
 } // end namespace ast_matchers
 } // end namespace clang