This is an archive of the discontinued LLVM Phabricator instance.

[ASTImporter] Add importer specific lookup
ClosedPublic

Authored by martong on Oct 25 2018, 8:57 AM.

Details

Summary

There are certain cases when normal C/C++ lookup (localUncachedLookup)
does not find AST nodes. E.g.:

Example 1:

template <class T>
struct X {
  friend void foo(); // this is never found in the DC of the TU.
};

Example 2:

// The fwd decl to Foo is not found in the lookupPtr of the DC of the
// translation unit decl.
struct A { struct Foo *p; };

In these cases we create a new node instead of returning with the old one.
To fix it we create a new lookup table which holds every node and we are
not interested in any C++ specific visibility considerations.
Simply, we must know if there is an existing Decl in a given DC.

Diff Detail

Repository
rL LLVM

Event Timeline

martong created this revision.Oct 25 2018, 8:57 AM

Gentle Ping.

Constructs like struct A { struct Foo *p; }; are very common in C projects. Since Foo as a forward decl cannot be found by normal lookup we need this patch in order to properly CTU analyze even a simple C project like tmux.

Hi Gabor,

I think it is a good patch with a nice test set. There are some mine comments inline. I'd also like to have LLDB guys opinion on it.

lib/AST/ASTImporter.cpp
7605 ↗(On Diff #171114)

It's better to make LookupTable an optional parameter of the previous ctor and remove this one.

7657 ↗(On Diff #171114)

@shafik @jingham Could you please address this question?

lib/AST/ASTImporterLookupTable.cpp
52 ↗(On Diff #171114)

// anonymous namespace or just // namespace.

84 ↗(On Diff #171114)

Should we remove DC-related entry if it is empty after deletion?

95 ↗(On Diff #171114)

Could you please add newlines after ifs?

121 ↗(On Diff #171114)
  1. StringRef
  2. Do we need a space before newline?
122 ↗(On Diff #171114)

Two spaces before "\n".

lib/CrossTU/CrossTranslationUnit.cpp
258 ↗(On Diff #171114)
if (!LookupTable)
  LookupTable = llvm::make_unique<ASTImporterLookupTable>(*ToTU);

?

unittests/AST/ASTImporterTest.cpp
346 ↗(On Diff #171114)

if (!LookupTablePtr) ...

3843 ↗(On Diff #171114)

Redundant space after paren.

3845 ↗(On Diff #171114)

Could you please explain what does this test do?

3889 ↗(On Diff #171114)

Do we need break/early return here?

3930 ↗(On Diff #171114)

This lambda is the same as in previous func so it's better to extract it into a helper.

4020 ↗(On Diff #171114)

This line exceeds 80 chars.

martong marked 18 inline comments as done.Nov 27 2018, 8:37 AM
martong added inline comments.
lib/AST/ASTImporter.cpp
7605 ↗(On Diff #171114)

Okay, I have changed it to be a default initalized to nullptr parameter.

lib/AST/ASTImporterLookupTable.cpp
84 ↗(On Diff #171114)

I don't think so.
The only place where we are going to use remove is in case we had an error during import (upcoming patch). Even if we had an error before, subsequent successfully imported Decls could be part of the same DC (so, chances are we would superfluously do a ping-pong of delete/create).

unittests/AST/ASTImporterTest.cpp
3845 ↗(On Diff #171114)

Well, it makes sure that we can build a lookup table for an empty file without any *assertion*. We may have an assertion in the ctor during traversing the AST. I consider this the most basic use case as it tests only the constructor.
However, if you find it weird I can remove it.

3889 ↗(On Diff #171114)

Yes, that's better to have.

3930 ↗(On Diff #171114)

Good catch, thanks.

martong updated this revision to Diff 175495.Nov 27 2018, 8:38 AM
martong marked 5 inline comments as done.
  • Address Alexei's comments

Hi Gabor,
Here are some new comments.

lib/AST/ASTImporter.cpp
7658 ↗(On Diff #175495)

Naming conventions require method names to start with a small letter.

lib/AST/ASTImporterLookupTable.cpp
121 ↗(On Diff #171114)

Point 2 is still not addressed. We print a string ending with a space and then print a newline. I think we can remove the trailing space from both string literals.

tools/clang-import-test/clang-import-test.cpp
12 ↗(On Diff #175495)

It looks like the only change done to this file is including a header. Are there any related changes that should be added?

unittests/AST/ASTImporterTest.cpp
3933 ↗(On Diff #175495)

return nullptr, Found is actually unused.

3845 ↗(On Diff #171114)

Yes, I think it's better to remove it or check some invariants of an empty lookup table.

martong marked 8 inline comments as done.Nov 30 2018, 5:41 AM
martong added inline comments.
lib/AST/ASTImporter.cpp
7658 ↗(On Diff #175495)

Okay, I changed it. Unfortunately ASTImporter does not really follow the conventions. Most of the functions start with a capital letter, and some with a small case.
E.g.:

/// Retrieve the file manager that AST nodes are being imported from.
FileManager &getFromFileManager() const { return FromFileManager; }

/// Report a diagnostic in the "to" context.
DiagnosticBuilder ToDiag(SourceLocation Loc, unsigned DiagID);
tools/clang-import-test/clang-import-test.cpp
12 ↗(On Diff #175495)

Thank you, this is a good catch, I removed it.

unittests/AST/ASTImporterTest.cpp
3845 ↗(On Diff #171114)

Ok, I removed it.

martong updated this revision to Diff 176100.Nov 30 2018, 5:42 AM
martong marked 3 inline comments as done.
  • Address Alexei's comments
  • Rename FindDeclsInToCtx to findDeclsInToCtx
  • Remove superfluous spaces from stringliterals
  • Remove unused header
  • Remove empty test
  • Return nullptr and FindInDeclListOfDC -> findInDeclListOfDC
  • Use SmallSetVector instead of SmallPtrSet
martong added a comment.EditedNov 30 2018, 5:47 AM

Hey Alexei,

Thank you again for your comments. I changed the code accordingly.

Also, I recognized that we should use a SmallSetVector instead of a SmallPtrSet, because the latter results unpredictable iteration (pointers may have different values with each run). Though SmallPtrSet is more powerful than SmallSetVector it makes it really hard to debug false positive ODR warnings from the ASTImporter, because the warning may appear in one run but may not appear in the subsequent run. We need an iteration order in the order of insertions and that is produced by SmallSetVector.

a_sidorin accepted this revision.Dec 1 2018, 11:42 AM

Hi Gabor,
I think the code looks good. Thank you!

This revision is now accepted and ready to land.Dec 1 2018, 11:42 AM
martong updated this revision to Diff 178452.Dec 17 2018, 5:06 AM
  • Rebase to master (trunk)

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This revision was automatically updated to reflect the committed changes.
martong added a comment.EditedDec 17 2018, 6:06 AM

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This is not a naive question. I was wondering myself on the very same thing when I started working on the ASTImporter at 2017.
I think when noload_lookup was introduced the author of that function tried to replace localUncachedLookup in ASTImporter, but that broke some tests. The major difference between the two functions is that the latter can find declarations even if they are not stored in the LookupPtr. This is rather unusual from the C/C++ point of view of lookup, and not working in all cases (see the introduction of this patch). Ironically, I can't just get rid of localUncachedLookup because it would break some LLDB test cases.

riccibruno added a comment.EditedDec 17 2018, 6:40 AM

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This is not a naive question. I was wondering myself on the very same thing when I started working on the ASTImporter at 2017.
I think when noload_lookup was introduced the author of that function tried to replace localUncachedLookup in ASTImporter, but that broke some tests. The major difference between the two functions is that the latter can find declarations even if they are not stored in the LookupPtr. This is rather unusual from the C/C++ point of view of lookup, and not working in all cases (see the introduction of this patch). Ironically, I can't just get rid of localUncachedLookup because it would break some LLDB test cases.

Ah I think I understand. For my understanding (and please correct me if I am wrong here):

localUncachedLookup will first try to do a normal lookup, and if that fails it will try to look in the declarations in the declaration context.
Now some declarations (including declarations which are not NamedDecl and declarations which matches shouldBeHidden)
will not be added to the LookupPtr (via makeDeclVisibleInContextWithFlags) and so will not be found though the normal lookup mechanism. You therefore need to use localUncachedLookup to find these.

Does this make sense ?

This is a perhaps a naive comment, but why is localUncachedLookup used
instead of noload_lookup ? There is a fixme dating from 2013 stating
that noload_lookup should be used instead.

This is not a naive question. I was wondering myself on the very same thing when I started working on the ASTImporter at 2017.
I think when noload_lookup was introduced the author of that function tried to replace localUncachedLookup in ASTImporter, but that broke some tests. The major difference between the two functions is that the latter can find declarations even if they are not stored in the LookupPtr. This is rather unusual from the C/C++ point of view of lookup, and not working in all cases (see the introduction of this patch). Ironically, I can't just get rid of localUncachedLookup because it would break some LLDB test cases.

Ah I think I understand. For my understanding (and please correct me if I am wrong here):

localUncachedLookup will first try to do a normal lookup, and if that fails it will try to look in the declarations in the declaration context.
Now some declarations (including declarations which are not NamedDecl and declarations which matches shouldBeHidden)
will not be added to the LookupPtr (via makeDeclVisibleInContextWithFlags) and so will not be found though the normal lookup mechanism. You therefore need to use localUncachedLookup to find these.

Does this make sense ?

Exactly. And this seems to be an important feature in ASTImporter, because this makes it possible that we can chain into the redecl chain a newly imported AST node to existing and structurally equivalent nodes. (The existing nodes are found by the lookup and then we iterate over the lookup results searching for structurally equivalent ones.)

Exactly. And this seems to be an important feature in ASTImporter, because this makes it possible that we can chain into the redecl chain a newly imported AST node to existing and structurally equivalent > nodes. (The existing nodes are found by the lookup and then we iterate over the lookup results searching for structurally equivalent ones.)

I see. I am unfortunately not familiar at all with the ASTImporter, but thanks for clearing this up.