[Modules] Fix decl order for DeclsInPrototype

[bruno]

Summary

When a declarator is constructed for a function prototype in
Parser::ParseFunctionDeclarator, it calls getCurScope()->decls()
in order to populate DeclsInPrototype.

getCurScope()->decls() return a range from a llvm::SmallPtrSet, which
doesn't guarantee any order. Later on, DeclsInPrototype are used to
populate decl contexts that end up being serialized when PCH or modules
are used. This causes non-determinism in module serialization, which
is bad for lots of reason, including that when a PCH used Modules, it
can't rebuild the module if there's a signature mismatch.

This patch fixes that by sorting out the result getCurScope()->decls()
before populating DeclsInPrototype. I don't believe we can change this
data structure because it can be used for any type of scope (not only
function prototypes).

There are no testcases for this change, since you have to run the
problematic non-reducible testcase multiple times to get a mismatch.
However, one can try to reproduce it on macOS using:

echo '@import Foundation;' > test.m
clang -fmodules test.m -o test.o -c \
      -fmodules-cache-path=/tmp/cache \
      -isysroot
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk
mv /tmp/cache /tmp/cache1

clang -fmodules test.m -o test.o -c \
      -fmodules-cache-path=/tmp/cache \
      -isysroot
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk
mv /tmp/cache /tmp/cache2

HASH=`ls /tmp/cache1`
for i in `find /tmp/cache1 -type f -iname "*.pcm"`; do
  F=`basename $i`;
  diff /tmp/cache1/$HASH/$F /tmp/cache2/$HASH/$F;
done

rdar://problem/43442957

[bruno]

This fixes the same problem previously addressed in https://reviews.llvm.org/D54923

[bruno]

Ping!

[bruno]

Ping

[rsmith]

lib/Parse/ParseDecl.cpp

6237

I would prefer that we use getID only for debug dumping purposes. Can we change Scope::DeclsInContext to be a SetVector instead? (How much does that cost us memory-wise?)

lib/Parse/ParseDecl.cpp

void Parser::ParseFunctionDeclarator(Declarator &D,
 
   // Collect non-parameter declarations from the prototype if this is a function
   // declaration. They will be moved into the scope of the function. Only do
   // this in C and not C++, where the decls will continue to live in the
   // surrounding context.
   SmallVector<NamedDecl *, 0> DeclsInPrototype;
   if (getCurScope()->getFlags() & Scope::FunctionDeclarationScope &&
       !getLangOpts().CPlusPlus) {
-    for (Decl *D : getCurScope()->decls()) {
+    // The decls in the scope are in arbitrary order. Add them in sorted order
+    // now and allow for the declarator chunk to always contain the decls in
+    // deterministic order. This is necessary because ActOnFunctionDeclarator
+    // copies the declarator chunk as is when populating the decl context,
+    // which could be later serialized for modules or PCHs.
+    SmallVector<Decl *, 8> SortedDecls(getCurScope()->decls());
+    llvm::sort(SortedDecls, [](const Decl *L, const Decl *R) {
+      return L->getID() < R->getID();
+    });
+    for (Decl *D : SortedDecls) {
       NamedDecl *ND = dyn_cast<NamedDecl>(D);
       if (!ND || isa<ParmVarDecl>(ND))
         continue;
       DeclsInPrototype.push_back(ND);
     }
   }
 
   // Remember that we parsed a function type, and remember the attributes.