[randstruct] Check final randomized layout ordering

[void]

Summary

This uses "llvm::shuffle" to stop differences in shuffle ordering on
different platforms.

[MaskRay]

clang/lib/AST/Randstruct.cpp

153

This was my original fix and your reland dropped it :(

clang/unittests/AST/RandstructTest.cpp

359

We haven't used c++17 yet.

[void]

clang/lib/AST/Randstruct.cpp

153

I think you reverted your change along with my patch. I don't remember intentionally changing this.

[void]

Fixed "std::vector" mishap

[thakis]

Looks like this breaks tests on windows: http://45.33.8.238/win/56771/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[void]

Maskray?

[MaskRay]

In D124199#3466653, @void wrote:

Maskray?

I think this is likely the failure I saw when I tried fix forward in 46b2a463bdef1bd1d80abee869b09f95ca5a4fc2 .
I was/am puzzled. Someone with a MSVC environment may check what's wrong with the random number generator.

[thakis]

Reverted in 8dbc6b560055ff5068ff45b550482ba62c36b5a5 for now.

[DavidSpickett]

We (Linaro) also got the same failure: https://lab.llvm.org/buildbot/#/builders/186/builds/5626

clang/lib/AST/Randstruct.cpp

void randomizeStructureLayoutImpl(const ASTContext &Context,
   // If we were filling a bucket, tie it off.
   if (CurrentBucket)
     Buckets.push_back(std::move(CurrentBucket));
 
   // If we were processing a bitfield run bucket, tie it off.
   if (CurrentBitfieldRun)
     Buckets.push_back(std::move(CurrentBitfieldRun));
 
-  std::shuffle(std::begin(Buckets), std::end(Buckets), RNG);
+  llvm::shuffle(std::begin(Buckets), std::end(Buckets), RNG);
 
   // Produce the new ordering of the elements from the Buckets.
   SmallVector<FieldDecl *, 16> FinalOrder;
   for (const std::unique_ptr<Bucket> &B : Buckets) {
     llvm::SmallVectorImpl<FieldDecl *> &RandFields = B->fields();
     if (!B->isBitfieldRun())
-      std::shuffle(std::begin(RandFields), std::end(RandFields), RNG);
+      llvm::shuffle(std::begin(RandFields), std::end(RandFields), RNG);
 
     FinalOrder.insert(FinalOrder.end(), RandFields.begin(), RandFields.end());
   }
 
   FieldsOut = FinalOrder;
 }
 
 } // anonymous namespace

clang/unittests/AST/RandstructTest.cpp

struct test {
         long long tomato;
         float mayonnaise;
     };
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"bacon", "lettuce", "tomato", "mayonnaise"};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_FALSE(RD->hasAttr<RandomizeLayoutAttr>());
   EXPECT_FALSE(RD->isRandomized());
 }
 
 TEST(RANDSTRUCT_TEST, MarkedNoRandomize) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test {
         int bacon;
         long lettuce;
         long long tomato;
         float mayonnaise;
     } __attribute__((no_randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"bacon", "lettuce", "tomato", "mayonnaise"};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_TRUE(RD->hasAttr<NoRandomizeLayoutAttr>());
   EXPECT_FALSE(RD->isRandomized());
 }
 
 TEST(RANDSTRUCT_TEST, MarkedRandomize) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test {
         int bacon;
         long lettuce;
         long long tomato;
         float mayonnaise;
     } __attribute__((randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"lettuce", "bacon", "mayonnaise", "tomato"};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_TRUE(RD->hasAttr<RandomizeLayoutAttr>());
   EXPECT_TRUE(RD->isRandomized());
 }
 
 TEST(RANDSTRUCT_TEST, MismatchedAttrsDeclVsDef) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test __attribute__((randomize_layout));
     struct test {
         int bacon;
         long lettuce;
         long long tomato;
         float mayonnaise;
     } __attribute__((no_randomize_layout));
-  )c",
-                                         true);
+  )c", true);
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const DiagnosticsEngine &Diags = AST->getDiagnostics();
 
   EXPECT_FALSE(Diags.hasFatalErrorOccurred());
   EXPECT_FALSE(Diags.hasUncompilableErrorOccurred());
   EXPECT_FALSE(Diags.hasUnrecoverableErrorOccurred());
   EXPECT_EQ(Diags.getNumWarnings(), 1u);
   EXPECT_EQ(Diags.getNumErrors(), 0u);
 }
 
 TEST(RANDSTRUCT_TEST, MismatchedAttrsRandomizeVsNoRandomize) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test {
         int bacon;
         long lettuce;
         long long tomato;
         float mayonnaise;
     } __attribute__((randomize_layout)) __attribute__((no_randomize_layout));
-  )c",
-                                         true);
+  )c", true);
 
   EXPECT_TRUE(AST->getDiagnostics().hasErrorOccurred());
 
   const DiagnosticsEngine &Diags = AST->getDiagnostics();
 
   EXPECT_TRUE(Diags.hasUncompilableErrorOccurred());
   EXPECT_TRUE(Diags.hasUnrecoverableErrorOccurred());
   EXPECT_EQ(Diags.getNumWarnings(), 0u);
   EXPECT_EQ(Diags.getNumErrors(), 1u);
 }
 
 TEST(RANDSTRUCT_TEST, MismatchedAttrsNoRandomizeVsRandomize) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test3 {
         int bacon;
         long lettuce;
         long long tomato;
         float mayonnaise;
     } __attribute__((no_randomize_layout)) __attribute__((randomize_layout));
-  )c",
-                                         true);
+  )c", true);
 
   EXPECT_TRUE(AST->getDiagnostics().hasErrorOccurred());
 
   const DiagnosticsEngine &Diags = AST->getDiagnostics();
 
   EXPECT_TRUE(Diags.hasUncompilableErrorOccurred());
   EXPECT_TRUE(Diags.hasUnrecoverableErrorOccurred());
   EXPECT_EQ(Diags.getNumWarnings(), 0u);
struct test {
         int z : 1;
         int c;
     } __attribute__((randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
-  const field_names Actual = getFieldNamesFromRecord(RD);
-  const field_names Subseq = {"x", "y", "z"};
+  const field_names Expected = {
+      "a", "b", "c", "x", "y", "z" // x, y, z needs to be a subsequnce.
+  };
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_TRUE(RD->isRandomized());
-  EXPECT_TRUE(isSubsequence(Actual, Subseq));
 }
 
-TEST(RANDSTRUCT_TEST, CheckVariableLengthArrayMemberRemainsAtEndOfStructure) {
+// FIXME: Enable when fix for flexible arrays is submitted.
+TEST(RANDSTRUCT_TEST, DISABLED_CheckVariableLengthArrayMemberRemainsAtEndOfStructure) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test {
         int a;
         double b;
         short c;
         char name[];
     } __attribute__((randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"c", "a", "b", "name"};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_TRUE(RD->isRandomized());
 }
 
 TEST(RANDSTRUCT_TEST, RandstructDoesNotOverrideThePackedAttr) {
   std::unique_ptr<ASTUnit> AST =
       makeAST(R"c(
     struct test_struct {
         char a;
         float b[3];
         short c;
         int d;
     } __attribute__((packed, randomize_layout));
 
     struct another_struct {
         char a;
         char b[5];
         int c;
     } __attribute__((packed, randomize_layout));
 
     struct last_struct {
         char a;
         long long b;
         int c[];
     } __attribute__((packed, randomize_layout));
-  )c",
-              false,
-              std::vector<std::string>(
-                  {"test_struct", "another_struct", "last_struct"}));
+  )c", false, field_names({"test_struct", "another_struct", "last_struct"}));
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   // FIXME (?): calling getASTRecordLayout is probably a necessary evil so that
   // Clang's RecordBuilders can actually flesh out the information like
   // alignment, etc.
   {
     const RecordDecl *RD =
         getRecordDeclFromAST(AST->getASTContext(), "test_struct");
     const ASTRecordLayout *Layout =
         &AST->getASTContext().getASTRecordLayout(RD);
+    const field_names Expected = {"b", "a", "c", "d"};
 
+    EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
     EXPECT_TRUE(RD->isRandomized());
     EXPECT_EQ(19, Layout->getSize().getQuantity());
   }
 
   {
     const RecordDecl *RD =
         getRecordDeclFromAST(AST->getASTContext(), "another_struct");
     const ASTRecordLayout *Layout =
         &AST->getASTContext().getASTRecordLayout(RD);
+    const field_names Expected = {"c", "b", "a"};
 
+    EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
     EXPECT_TRUE(RD->isRandomized());
     EXPECT_EQ(10, Layout->getSize().getQuantity());
   }
 
   {
     const RecordDecl *RD =
         getRecordDeclFromAST(AST->getASTContext(), "last_struct");
     const ASTRecordLayout *Layout =
         &AST->getASTContext().getASTRecordLayout(RD);
+    const field_names Expected = {"a", "c", "b"};
 
+    EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
     EXPECT_TRUE(RD->isRandomized());
     EXPECT_EQ(9, Layout->getSize().getQuantity());
   }
 }
 
 TEST(RANDSTRUCT_TEST, ZeroWidthBitfieldsSeparateAllocationUnits) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test {
         int a : 1;
         int   : 0;
         int b : 1;
     } __attribute__((randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"a", "b", ""};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_TRUE(RD->isRandomized());
 }
 
 TEST(RANDSTRUCT_TEST, RandstructDoesNotRandomizeUnionFieldOrder) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     union test {
         int a;
         int b;
         int c;
         int d;
         int e;
         int f;
     } __attribute__((randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
-  const RecordDecl *RD =
-      getRecordDeclFromAST(AST->getASTContext(), "test");
+  const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"a", "b", "c", "d", "e", "f"};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_FALSE(RD->isRandomized());
 }
 
 TEST(RANDSTRUCT_TEST, AnonymousStructsAndUnionsRetainFieldOrder) {
   std::unique_ptr<ASTUnit> AST = makeAST(R"c(
     struct test {
         int a;
         struct sub_struct {
struct test {
         };
         int r;
     } __attribute__((randomize_layout));
   )c");
 
   EXPECT_FALSE(AST->getDiagnostics().hasErrorOccurred());
 
   const RecordDecl *RD = getRecordDeclFromAST(AST->getASTContext(), "test");
+  const field_names Expected = {"", "l", "", "r", "s", "a", "f"};
 
+  EXPECT_EQ(Expected, getFieldNamesFromRecord(RD));
   EXPECT_TRUE(RD->isRandomized());
 
   bool AnonStructTested = false;
   bool AnonUnionTested = false;
 
   for (const Decl *D : RD->decls())
     if (const FieldDecl *FD = dyn_cast<FieldDecl>(D)) {
       if (const auto *Record = FD->getType()->getAs<RecordType>()) {