[Serialization] Fix that ASTDeclContextNameLookupTrait::data_type_builder never checks the first 4 DeclIDs for uniqueness

[teemperor]

Summary

The insert function is supposed to check for uniqueness of any newly added DeclID, but the uniqueness
check for small result sets is always searching the empty Found set (which is always empty in this branch)
instead of the actual list of DeclIDs. This lead to Clang often adding identical NamespaceDecls to a DeclContext
lookup result.

See also D84827 for the assert that found this issue.

[vsapsai]

Was the assertion triggered on existing test suite or on some other code?

The change looks correct to me, just want to make sure we have it tested.

[teemperor]

All the patches here are just fixes for the test suite. This patch fixes those tests:

Clang :: Modules/stress1.cpp                                                  
Clang :: Modules/cxx-templates.cpp                                            
Clang :: Modules/pr27513.cpp                                                  
Clang :: Modules/merge-template-members.cpp                                   
Clang :: Modules/templates.mm                                                 
Clang :: Modules/cxx-lookup.cpp                                               
Clang :: Modules/exponential-paths.cpp                                        
Clang :: Modules/odr_hash-Friend.cpp

[vsapsai]

I believe the fix isn't controversial and doesn't require Richard's attention.

As aside, it would be nice for static analyzer to be able to detect

if (container.empty()) {
  // iterate through container
}

[dexonsmith]

Agreed the fix is correct, and that a unit test would be nice (although annoying since the type isn't currently in include/clang).

I wonder if this should just use a SmallDenseSet and be done with it though?

[dexonsmith]

In D84834#2365311, @dexonsmith wrote:

Agreed the fix is correct, and that a unit test would be nice (although annoying since the type isn't currently in include/clang).

I wonder if this should just use a SmallDenseSet and be done with it though?

Note, I don't feel strongly about the unit test if that'll hold up landing the fix (given that the assertion is going in fairly promptly anyway) -- feel free to commit -- but it might be worth considering in a follow-up.

clang/lib/Serialization/ASTReaderInternals.h

struct data_type_builder {
     llvm::DenseSet<DeclID> Found;
 
     data_type_builder(data_type &D) : Data(D) {}
 
     void insert(DeclID ID) {
       // Just use a linear scan unless we have more than a few IDs.
       if (Found.empty() && !Data.empty()) {
         if (Data.size() <= 4) {
-          for (auto I : Found)
-            if (I == ID)
-              return;
+          if (llvm::is_contained(Data, ID))
           Data.push_back(ID);
           return;
         }
 
         // Switch to tracking found IDs in the set.
         Found.insert(Data.begin(), Data.end());
       }