[Coverage] Add an expensive test for the segment builder

[vsk]

Summary

Add an exhaustive test for the segment builder. It is only enabled when
-DEXPENSIVE_CHECKS is passed.

The test lists all regions within a window of source code, picks all
combinations of K regions within the window, and runs the segment
builder.

Depends on D36813.

[ikudrin]

LGTM

unittests/ProfileData/CoverageMappingTest.cpp

612

Strictly speaking, it should be something like I < N - R + C.size() + 1, but taking into account the volume of N it doesn't matter.

unittests/ProfileData/CoverageMappingTest.cpp

TEST_P(CoverageMappingTest, handle_sandwiched_zero_length_region) {
   // Handle the zero-length region by creating a segment with its predecessor's
   // count (i.e the count from 1:5 -> 4:4).
   EXPECT_EQ(CoverageSegment(4, 4, false), Segments[7]);
   // The area between 4:4 and 4:12 is skipped.
   EXPECT_EQ(CoverageSegment(4, 12, 1, true), Segments[8]);
   EXPECT_EQ(CoverageSegment(4, 17, false), Segments[9]);
 }
 
+#if !defined(NDEBUG) && defined(EXPENSIVE_CHECKS)
+TEST_P(CoverageMappingTest, exhaustive_segment_builder_test) {
+  // With these constants, the test creates roughly $\binom{(2^2)(3^2)}{5}$ (or
+  // 376K) functions.
+  const unsigned MaxLine = 2;
+  const unsigned MaxCol = 3;
+  const unsigned Choose = 5;
+
+  // Generate all possible regions within a MaxLine-by-MaxCol area.
+  struct Region {
+    unsigned LS, CS, LE, CE;
+  };
+  std::vector<Region> Regions;
+  for (unsigned LS = 1; LS <= MaxLine; ++LS)
+    for (unsigned CS = 1; CS <= MaxCol; ++CS)
+      for (unsigned LE = LS; LE <= MaxLine; ++LE)
+        for (unsigned CE = (LS == LE) ? CS : 1; CE <= MaxCol; ++CE)
+          Regions.push_back({LS, CS, LE, CE});
+
+  // Next, for a fixed number of regions \p Choose, find all ways of choosing
+  // \p Choose regions from the pre-built list.
+
+  /// Map a function over all $\binom{N}{R}$ choices of indices in [0, N).
+  class CombinationMapper {
+  public:
+    using Combination = std::vector<unsigned>;
+    using Mapper = std::function<void (const Combination &)>;
+
+    CombinationMapper(unsigned N, unsigned R, const Mapper &F)
+        : N(N), R(R), F(F), C() {
+      assert((N >= R) && (R > 0) && "Invalid combination parameters");
+    }
+
+    /// Start mapping \p F over all R-length combinations of indices in [0, N).
+    void map() { generate(0); }
+
+  private:
+    void generate(unsigned StartingIdx) {
+      for (unsigned I = StartingIdx; I < N; ++I) {
+        C.push_back(I);
+        if (C.size() == R)
+          F(C);
+        else
+          generate(I + 1);
+        C.pop_back();
+      }
+    }
+
+    unsigned N, R;
+    const Mapper &F;
+    Combination C;
+  };
+
+  // Create a function which uses the regions given by the list of indices.
+  unsigned TestNo = 1;
+  auto CreateFunction = [&](const CombinationMapper::Combination &C) {
+    std::string FuncName;
+    {
+      raw_string_ostream OS(FuncName);
+      OS << "func" << TestNo;
+    }
+    ProfileWriter.addRecord({FuncName, TestNo, {0}}, Err);
+    startFunction(FuncName, TestNo);
+    unsigned LineShift = (TestNo - 1) * (MaxLine + 1);
+    for (unsigned Idx : C) {
+      const Region &R = Regions[Idx];
+      addCMR(Counter::getCounter(0), "file1", R.LS + LineShift, R.CS,
+             R.LE + LineShift, R.CE);
+    }
+    ++TestNo;
+  };
+
+  // Create all functions which use \p Choose regions from the pre-built list.
+  CombinationMapper(Regions.size(), Choose, CreateFunction).map();
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  (void)LoadedCoverage->getCoverageForFile("file1");
+
+  // The assertions in SegmentBuilder should catch the issues we care about.
+}
+#endif
+
 TEST_P(CoverageMappingTest, expansion_gets_first_counter) {
   startFunction("func", 0x1234);
   addCMR(Counter::getCounter(1), "foo", 10, 1, 10, 2);
   // This starts earlier in "foo", so the expansion should get its counter.
   addCMR(Counter::getCounter(2), "foo", 1, 1, 20, 1);
   addExpansionCMR("bar", "foo", 3, 3, 3, 3);
 
   writeAndReadCoverageRegions();