llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

   1 //===- CoverageMapping.cpp - Code coverage mapping support ----------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains support for clang's and llvm's instrumentation based
  10 // code coverage.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ProfileData/Coverage/CoverageMapping.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/SmallBitVector.h"
  18 #include "llvm/ADT/SmallString.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/ADT/StringExtras.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/Object/BuildID.h"
  23 #include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
  24 #include "llvm/ProfileData/InstrProfReader.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/Errc.h"
  27 #include "llvm/Support/Error.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/MemoryBuffer.h"
  30 #include "llvm/Support/VirtualFileSystem.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include <algorithm>
  33 #include <cassert>
  34 #include <cstdint>
  35 #include <iterator>
  36 #include <map>
  37 #include <memory>
  38 #include <optional>
  39 #include <string>
  40 #include <system_error>
  41 #include <utility>
  42 #include <vector>
  43
  44 using namespace llvm;
  45 using namespace coverage;
  46
  47 #define DEBUG_TYPE "coverage-mapping"
  48
  49 Counter CounterExpressionBuilder::get(const CounterExpression &E) {
  50   auto It = ExpressionIndices.find(E);
  51   if (It != ExpressionIndices.end())
  52     return Counter::getExpression(It->second);
  53   unsigned I = Expressions.size();
  54   Expressions.push_back(E);
  55   ExpressionIndices[E] = I;
  56   return Counter::getExpression(I);
  57 }
  58
  59 void CounterExpressionBuilder::extractTerms(Counter C, int Factor,
  60                                             SmallVectorImpl<Term> &Terms) {
  61   switch (C.getKind()) {
  62   case Counter::Zero:
  63     break;
  64   case Counter::CounterValueReference:
  65     Terms.emplace_back(C.getCounterID(), Factor);
  66     break;
  67   case Counter::Expression:
  68     const auto &E = Expressions[C.getExpressionID()];
  69     extractTerms(E.LHS, Factor, Terms);
  70     extractTerms(
  71         E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms);
  72     break;
  73   }
  74 }
  75
  76 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
  77   // Gather constant terms.
  78   SmallVector<Term, 32> Terms;
  79   extractTerms(ExpressionTree, +1, Terms);
  80
  81   // If there are no terms, this is just a zero. The algorithm below assumes at
  82   // least one term.
  83   if (Terms.size() == 0)
  84     return Counter::getZero();
  85
  86   // Group the terms by counter ID.
  87   llvm::sort(Terms, [](const Term &LHS, const Term &RHS) {
  88     return LHS.CounterID < RHS.CounterID;
  89   });
  90
  91   // Combine terms by counter ID to eliminate counters that sum to zero.
  92   auto Prev = Terms.begin();
  93   for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
  94     if (I->CounterID == Prev->CounterID) {
  95       Prev->Factor += I->Factor;
  96       continue;
  97     }
  98     ++Prev;
  99     *Prev = *I;
 100   }
 101   Terms.erase(++Prev, Terms.end());
 102
 103   Counter C;
 104   // Create additions. We do this before subtractions to avoid constructs like
 105   // ((0 - X) + Y), as opposed to (Y - X).
 106   for (auto T : Terms) {
 107     if (T.Factor <= 0)
 108       continue;
 109     for (int I = 0; I < T.Factor; ++I)
 110       if (C.isZero())
 111         C = Counter::getCounter(T.CounterID);
 112       else
 113         C = get(CounterExpression(CounterExpression::Add, C,
 114                                   Counter::getCounter(T.CounterID)));
 115   }
 116
 117   // Create subtractions.
 118   for (auto T : Terms) {
 119     if (T.Factor >= 0)
 120       continue;
 121     for (int I = 0; I < -T.Factor; ++I)
 122       C = get(CounterExpression(CounterExpression::Subtract, C,
 123                                 Counter::getCounter(T.CounterID)));
 124   }
 125   return C;
 126 }
 127
 128 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) {
 129   auto Cnt = get(CounterExpression(CounterExpression::Add, LHS, RHS));
 130   return Simplify ? simplify(Cnt) : Cnt;
 131 }
 132
 133 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS,
 134                                            bool Simplify) {
 135   auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS));
 136   return Simplify ? simplify(Cnt) : Cnt;
 137 }
 138
 139 void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
 140   switch (C.getKind()) {
 141   case Counter::Zero:
 142     OS << '0';
 143     return;
 144   case Counter::CounterValueReference:
 145     OS << '#' << C.getCounterID();
 146     break;
 147   case Counter::Expression: {
 148     if (C.getExpressionID() >= Expressions.size())
 149       return;
 150     const auto &E = Expressions[C.getExpressionID()];
 151     OS << '(';
 152     dump(E.LHS, OS);
 153     OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
 154     dump(E.RHS, OS);
 155     OS << ')';
 156     break;
 157   }
 158   }
 159   if (CounterValues.empty())
 160     return;
 161   Expected<int64_t> Value = evaluate(C);
 162   if (auto E = Value.takeError()) {
 163     consumeError(std::move(E));
 164     return;
 165   }
 166   OS << '[' << *Value << ']';
 167 }
 168
 169 Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
 170   struct StackElem {
 171     Counter ICounter;
 172     int64_t LHS = 0;
 173     enum {
 174       KNeverVisited = 0,
 175       KVisitedOnce = 1,
 176       KVisitedTwice = 2,
 177     } VisitCount = KNeverVisited;
 178   };
 179
 180   std::stack<StackElem> CounterStack;
 181   CounterStack.push({C});
 182
 183   int64_t LastPoppedValue;
 184
 185   while (!CounterStack.empty()) {
 186     StackElem &Current = CounterStack.top();
 187
 188     switch (Current.ICounter.getKind()) {
 189     case Counter::Zero:
 190       LastPoppedValue = 0;
 191       CounterStack.pop();
 192       break;
 193     case Counter::CounterValueReference:
 194       if (Current.ICounter.getCounterID() >= CounterValues.size())
 195         return errorCodeToError(errc::argument_out_of_domain);
 196       LastPoppedValue = CounterValues[Current.ICounter.getCounterID()];
 197       CounterStack.pop();
 198       break;
 199     case Counter::Expression: {
 200       if (Current.ICounter.getExpressionID() >= Expressions.size())
 201         return errorCodeToError(errc::argument_out_of_domain);
 202       const auto &E = Expressions[Current.ICounter.getExpressionID()];
 203       if (Current.VisitCount == StackElem::KNeverVisited) {
 204         CounterStack.push(StackElem{E.LHS});
 205         Current.VisitCount = StackElem::KVisitedOnce;
 206       } else if (Current.VisitCount == StackElem::KVisitedOnce) {
 207         Current.LHS = LastPoppedValue;
 208         CounterStack.push(StackElem{E.RHS});
 209         Current.VisitCount = StackElem::KVisitedTwice;
 210       } else {
 211         int64_t LHS = Current.LHS;
 212         int64_t RHS = LastPoppedValue;
 213         LastPoppedValue =
 214             E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS;
 215         CounterStack.pop();
 216       }
 217       break;
 218     }
 219     }
 220   }
 221
 222   return LastPoppedValue;
 223 }
 224
 225 unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {
 226   switch (C.getKind()) {
 227   case Counter::Zero:
 228     return 0;
 229   case Counter::CounterValueReference:
 230     return C.getCounterID();
 231   case Counter::Expression: {
 232     if (C.getExpressionID() >= Expressions.size())
 233       return 0;
 234     const auto &E = Expressions[C.getExpressionID()];
 235     return std::max(getMaxCounterID(E.LHS), getMaxCounterID(E.RHS));
 236   }
 237   }
 238   llvm_unreachable("Unhandled CounterKind");
 239 }
 240
 241 void FunctionRecordIterator::skipOtherFiles() {
 242   while (Current != Records.end() && !Filename.empty() &&
 243          Filename != Current->Filenames[0])
 244     ++Current;
 245   if (Current == Records.end())
 246     *this = FunctionRecordIterator();
 247 }
 248
 249 ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename(
 250     StringRef Filename) const {
 251   size_t FilenameHash = hash_value(Filename);
 252   auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash);
 253   if (RecordIt == FilenameHash2RecordIndices.end())
 254     return {};
 255   return RecordIt->second;
 256 }
 257
 258 static unsigned getMaxCounterID(const CounterMappingContext &Ctx,
 259                                 const CoverageMappingRecord &Record) {
 260   unsigned MaxCounterID = 0;
 261   for (const auto &Region : Record.MappingRegions) {
 262     MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count));
 263   }
 264   return MaxCounterID;
 265 }
 266
 267 Error CoverageMapping::loadFunctionRecord(
 268     const CoverageMappingRecord &Record,
 269     IndexedInstrProfReader &ProfileReader) {
 270   StringRef OrigFuncName = Record.FunctionName;
 271   if (OrigFuncName.empty())
 272     return make_error<CoverageMapError>(coveragemap_error::malformed,
 273                                         "record function name is empty");
 274
 275   if (Record.Filenames.empty())
 276     OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
 277   else
 278     OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
 279
 280   CounterMappingContext Ctx(Record.Expressions);
 281
 282   std::vector<uint64_t> Counts;
 283   if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName,
 284                                                 Record.FunctionHash, Counts)) {
 285     instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E)));
 286     if (IPE == instrprof_error::hash_mismatch) {
 287       FuncHashMismatches.emplace_back(std::string(Record.FunctionName),
 288                                       Record.FunctionHash);
 289       return Error::success();
 290     } else if (IPE != instrprof_error::unknown_function)
 291       return make_error<InstrProfError>(IPE);
 292     Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0);
 293   }
 294   Ctx.setCounts(Counts);
 295
 296   assert(!Record.MappingRegions.empty() && "Function has no regions");
 297
 298   // This coverage record is a zero region for a function that's unused in
 299   // some TU, but used in a different TU. Ignore it. The coverage maps from the
 300   // the other TU will either be loaded (providing full region counts) or they
 301   // won't (in which case we don't unintuitively report functions as uncovered
 302   // when they have non-zero counts in the profile).
 303   if (Record.MappingRegions.size() == 1 &&
 304       Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
 305     return Error::success();
 306
 307   FunctionRecord Function(OrigFuncName, Record.Filenames);
 308   for (const auto &Region : Record.MappingRegions) {
 309     Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
 310     if (auto E = ExecutionCount.takeError()) {
 311       consumeError(std::move(E));
 312       return Error::success();
 313     }
 314     Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount);
 315     if (auto E = AltExecutionCount.takeError()) {
 316       consumeError(std::move(E));
 317       return Error::success();
 318     }
 319     Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount);
 320   }
 321
 322   // Don't create records for (filenames, function) pairs we've already seen.
 323   auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),
 324                                           Record.Filenames.end());
 325   if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)
 326     return Error::success();
 327
 328   Functions.push_back(std::move(Function));
 329
 330   // Performance optimization: keep track of the indices of the function records
 331   // which correspond to each filename. This can be used to substantially speed
 332   // up queries for coverage info in a file.
 333   unsigned RecordIndex = Functions.size() - 1;
 334   for (StringRef Filename : Record.Filenames) {
 335     auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)];
 336     // Note that there may be duplicates in the filename set for a function
 337     // record, because of e.g. macro expansions in the function in which both
 338     // the macro and the function are defined in the same file.
 339     if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)
 340       RecordIndices.push_back(RecordIndex);
 341   }
 342
 343   return Error::success();
 344 }
 345
 346 // This function is for memory optimization by shortening the lifetimes
 347 // of CoverageMappingReader instances.
 348 Error CoverageMapping::loadFromReaders(
 349     ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
 350     IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) {
 351   for (const auto &CoverageReader : CoverageReaders) {
 352     for (auto RecordOrErr : *CoverageReader) {
 353       if (Error E = RecordOrErr.takeError())
 354         return E;
 355       const auto &Record = *RecordOrErr;
 356       if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader))
 357         return E;
 358     }
 359   }
 360   return Error::success();
 361 }
 362
 363 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
 364     ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
 365     IndexedInstrProfReader &ProfileReader) {
 366   auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
 367   if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage))
 368     return std::move(E);
 369   return std::move(Coverage);
 370 }
 371
 372 // If E is a no_data_found error, returns success. Otherwise returns E.
 373 static Error handleMaybeNoDataFoundError(Error E) {
 374   return handleErrors(
 375       std::move(E), [](const CoverageMapError &CME) {
 376         if (CME.get() == coveragemap_error::no_data_found)
 377           return static_cast<Error>(Error::success());
 378         return make_error<CoverageMapError>(CME.get(), CME.getMessage());
 379       });
 380 }
 381
 382 Error CoverageMapping::loadFromFile(
 383     StringRef Filename, StringRef Arch, StringRef CompilationDir,
 384     IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage,
 385     bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) {
 386   auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(
 387       Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false);
 388   if (std::error_code EC = CovMappingBufOrErr.getError())
 389     return createFileError(Filename, errorCodeToError(EC));
 390   MemoryBufferRef CovMappingBufRef =
 391       CovMappingBufOrErr.get()->getMemBufferRef();
 392   SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;
 393
 394   SmallVector<object::BuildIDRef> BinaryIDs;
 395   auto CoverageReadersOrErr = BinaryCoverageReader::create(
 396       CovMappingBufRef, Arch, Buffers, CompilationDir,
 397       FoundBinaryIDs ? &BinaryIDs : nullptr);
 398   if (Error E = CoverageReadersOrErr.takeError()) {
 399     E = handleMaybeNoDataFoundError(std::move(E));
 400     if (E)
 401       return createFileError(Filename, std::move(E));
 402     return E;
 403   }
 404
 405   SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;
 406   for (auto &Reader : CoverageReadersOrErr.get())
 407     Readers.push_back(std::move(Reader));
 408   if (FoundBinaryIDs && !Readers.empty()) {
 409     llvm::append_range(*FoundBinaryIDs,
 410                        llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) {
 411                          return object::BuildID(BID);
 412                        }));
 413   }
 414   DataFound |= !Readers.empty();
 415   if (Error E = loadFromReaders(Readers, ProfileReader, Coverage))
 416     return createFileError(Filename, std::move(E));
 417   return Error::success();
 418 }
 419
 420 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
 421     ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename,
 422     vfs::FileSystem &FS, ArrayRef<StringRef> Arches, StringRef CompilationDir,
 423     const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) {
 424   auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename, FS);
 425   if (Error E = ProfileReaderOrErr.takeError())
 426     return createFileError(ProfileFilename, std::move(E));
 427   auto ProfileReader = std::move(ProfileReaderOrErr.get());
 428   auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
 429   bool DataFound = false;
 430
 431   auto GetArch = [&](size_t Idx) {
 432     if (Arches.empty())
 433       return StringRef();
 434     if (Arches.size() == 1)
 435       return Arches.front();
 436     return Arches[Idx];
 437   };
 438
 439   SmallVector<object::BuildID> FoundBinaryIDs;
 440   for (const auto &File : llvm::enumerate(ObjectFilenames)) {
 441     if (Error E =
 442             loadFromFile(File.value(), GetArch(File.index()), CompilationDir,
 443                          *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs))
 444       return std::move(E);
 445   }
 446
 447   if (BIDFetcher) {
 448     std::vector<object::BuildID> ProfileBinaryIDs;
 449     if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs))
 450       return createFileError(ProfileFilename, std::move(E));
 451
 452     SmallVector<object::BuildIDRef> BinaryIDsToFetch;
 453     if (!ProfileBinaryIDs.empty()) {
 454       const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) {
 455         return std::lexicographical_compare(A.begin(), A.end(), B.begin(),
 456                                             B.end());
 457       };
 458       llvm::sort(FoundBinaryIDs, Compare);
 459       std::set_difference(
 460           ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(),
 461           FoundBinaryIDs.begin(), FoundBinaryIDs.end(),
 462           std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare);
 463     }
 464
 465     for (object::BuildIDRef BinaryID : BinaryIDsToFetch) {
 466       std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID);
 467       if (PathOpt) {
 468         std::string Path = std::move(*PathOpt);
 469         StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef();
 470         if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader,
 471                                   *Coverage, DataFound))
 472           return std::move(E);
 473       } else if (CheckBinaryIDs) {
 474         return createFileError(
 475             ProfileFilename,
 476             createStringError(errc::no_such_file_or_directory,
 477                               "Missing binary ID: " +
 478                                   llvm::toHex(BinaryID, /*LowerCase=*/true)));
 479       }
 480     }
 481   }
 482
 483   if (!DataFound)
 484     return createFileError(
 485         join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "),
 486         make_error<CoverageMapError>(coveragemap_error::no_data_found));
 487   return std::move(Coverage);
 488 }
 489
 490 namespace {
 491
 492 /// Distributes functions into instantiation sets.
 493 ///
 494 /// An instantiation set is a collection of functions that have the same source
 495 /// code, ie, template functions specializations.
 496 class FunctionInstantiationSetCollector {
 497   using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
 498   MapT InstantiatedFunctions;
 499
 500 public:
 501   void insert(const FunctionRecord &Function, unsigned FileID) {
 502     auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
 503     while (I != E && I->FileID != FileID)
 504       ++I;
 505     assert(I != E && "function does not cover the given file");
 506     auto &Functions = InstantiatedFunctions[I->startLoc()];
 507     Functions.push_back(&Function);
 508   }
 509
 510   MapT::iterator begin() { return InstantiatedFunctions.begin(); }
 511   MapT::iterator end() { return InstantiatedFunctions.end(); }
 512 };
 513
 514 class SegmentBuilder {
 515   std::vector<CoverageSegment> &Segments;
 516   SmallVector<const CountedRegion *, 8> ActiveRegions;
 517
 518   SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
 519
 520   /// Emit a segment with the count from \p Region starting at \p StartLoc.
 521   //
 522   /// \p IsRegionEntry: The segment is at the start of a new non-gap region.
 523   /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
 524   void startSegment(const CountedRegion &Region, LineColPair StartLoc,
 525                     bool IsRegionEntry, bool EmitSkippedRegion = false) {
 526     bool HasCount = !EmitSkippedRegion &&
 527                     (Region.Kind != CounterMappingRegion::SkippedRegion);
 528
 529     // If the new segment wouldn't affect coverage rendering, skip it.
 530     if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
 531       const auto &Last = Segments.back();
 532       if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
 533           !Last.IsRegionEntry)
 534         return;
 535     }
 536
 537     if (HasCount)
 538       Segments.emplace_back(StartLoc.first, StartLoc.second,
 539                             Region.ExecutionCount, IsRegionEntry,
 540                             Region.Kind == CounterMappingRegion::GapRegion);
 541     else
 542       Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);
 543
 544     LLVM_DEBUG({
 545       const auto &Last = Segments.back();
 546       dbgs() << "Segment at " << Last.Line << ":" << Last.Col
 547              << " (count = " << Last.Count << ")"
 548              << (Last.IsRegionEntry ? ", RegionEntry" : "")
 549              << (!Last.HasCount ? ", Skipped" : "")
 550              << (Last.IsGapRegion ? ", Gap" : "") << "\n";
 551     });
 552   }
 553
 554   /// Emit segments for active regions which end before \p Loc.
 555   ///
 556   /// \p Loc: The start location of the next region. If std::nullopt, all active
 557   /// regions are completed.
 558   /// \p FirstCompletedRegion: Index of the first completed region.
 559   void completeRegionsUntil(std::optional<LineColPair> Loc,
 560                             unsigned FirstCompletedRegion) {
 561     // Sort the completed regions by end location. This makes it simple to
 562     // emit closing segments in sorted order.
 563     auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
 564     std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
 565                       [](const CountedRegion *L, const CountedRegion *R) {
 566                         return L->endLoc() < R->endLoc();
 567                       });
 568
 569     // Emit segments for all completed regions.
 570     for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
 571          ++I) {
 572       const auto *CompletedRegion = ActiveRegions[I];
 573       assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
 574              "Completed region ends after start of new region");
 575
 576       const auto *PrevCompletedRegion = ActiveRegions[I - 1];
 577       auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
 578
 579       // Don't emit any more segments if they start where the new region begins.
 580       if (Loc && CompletedSegmentLoc == *Loc)
 581         break;
 582
 583       // Don't emit a segment if the next completed region ends at the same
 584       // location as this one.
 585       if (CompletedSegmentLoc == CompletedRegion->endLoc())
 586         continue;
 587
 588       // Use the count from the last completed region which ends at this loc.
 589       for (unsigned J = I + 1; J < E; ++J)
 590         if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
 591           CompletedRegion = ActiveRegions[J];
 592
 593       startSegment(*CompletedRegion, CompletedSegmentLoc, false);
 594     }
 595
 596     auto Last = ActiveRegions.back();
 597     if (FirstCompletedRegion && Last->endLoc() != *Loc) {
 598       // If there's a gap after the end of the last completed region and the
 599       // start of the new region, use the last active region to fill the gap.
 600       startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
 601                    false);
 602     } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
 603       // Emit a skipped segment if there are no more active regions. This
 604       // ensures that gaps between functions are marked correctly.
 605       startSegment(*Last, Last->endLoc(), false, true);
 606     }
 607
 608     // Pop the completed regions.
 609     ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
 610   }
 611
 612   void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
 613     for (const auto &CR : enumerate(Regions)) {
 614       auto CurStartLoc = CR.value().startLoc();
 615
 616       // Active regions which end before the current region need to be popped.
 617       auto CompletedRegions =
 618           std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
 619                                 [&](const CountedRegion *Region) {
 620                                   return !(Region->endLoc() <= CurStartLoc);
 621                                 });
 622       if (CompletedRegions != ActiveRegions.end()) {
 623         unsigned FirstCompletedRegion =
 624             std::distance(ActiveRegions.begin(), CompletedRegions);
 625         completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
 626       }
 627
 628       bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;
 629
 630       // Try to emit a segment for the current region.
 631       if (CurStartLoc == CR.value().endLoc()) {
 632         // Avoid making zero-length regions active. If it's the last region,
 633         // emit a skipped segment. Otherwise use its predecessor's count.
 634         const bool Skipped =
 635             (CR.index() + 1) == Regions.size() ||
 636             CR.value().Kind == CounterMappingRegion::SkippedRegion;
 637         startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
 638                      CurStartLoc, !GapRegion, Skipped);
 639         // If it is skipped segment, create a segment with last pushed
 640         // regions's count at CurStartLoc.
 641         if (Skipped && !ActiveRegions.empty())
 642           startSegment(*ActiveRegions.back(), CurStartLoc, false);
 643         continue;
 644       }
 645       if (CR.index() + 1 == Regions.size() ||
 646           CurStartLoc != Regions[CR.index() + 1].startLoc()) {
 647         // Emit a segment if the next region doesn't start at the same location
 648         // as this one.
 649         startSegment(CR.value(), CurStartLoc, !GapRegion);
 650       }
 651
 652       // This region is active (i.e not completed).
 653       ActiveRegions.push_back(&CR.value());
 654     }
 655
 656     // Complete any remaining active regions.
 657     if (!ActiveRegions.empty())
 658       completeRegionsUntil(std::nullopt, 0);
 659   }
 660
 661   /// Sort a nested sequence of regions from a single file.
 662   static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
 663     llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {
 664       if (LHS.startLoc() != RHS.startLoc())
 665         return LHS.startLoc() < RHS.startLoc();
 666       if (LHS.endLoc() != RHS.endLoc())
 667         // When LHS completely contains RHS, we sort LHS first.
 668         return RHS.endLoc() < LHS.endLoc();
 669       // If LHS and RHS cover the same area, we need to sort them according
 670       // to their kinds so that the most suitable region will become "active"
 671       // in combineRegions(). Because we accumulate counter values only from
 672       // regions of the same kind as the first region of the area, prefer
 673       // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
 674       static_assert(CounterMappingRegion::CodeRegion <
 675                             CounterMappingRegion::ExpansionRegion &&
 676                         CounterMappingRegion::ExpansionRegion <
 677                             CounterMappingRegion::SkippedRegion,
 678                     "Unexpected order of region kind values");
 679       return LHS.Kind < RHS.Kind;
 680     });
 681   }
 682
 683   /// Combine counts of regions which cover the same area.
 684   static ArrayRef<CountedRegion>
 685   combineRegions(MutableArrayRef<CountedRegion> Regions) {
 686     if (Regions.empty())
 687       return Regions;
 688     auto Active = Regions.begin();
 689     auto End = Regions.end();
 690     for (auto I = Regions.begin() + 1; I != End; ++I) {
 691       if (Active->startLoc() != I->startLoc() ||
 692           Active->endLoc() != I->endLoc()) {
 693         // Shift to the next region.
 694         ++Active;
 695         if (Active != I)
 696           *Active = *I;
 697         continue;
 698       }
 699       // Merge duplicate region.
 700       // If CodeRegions and ExpansionRegions cover the same area, it's probably
 701       // a macro which is fully expanded to another macro. In that case, we need
 702       // to accumulate counts only from CodeRegions, or else the area will be
 703       // counted twice.
 704       // On the other hand, a macro may have a nested macro in its body. If the
 705       // outer macro is used several times, the ExpansionRegion for the nested
 706       // macro will also be added several times. These ExpansionRegions cover
 707       // the same source locations and have to be combined to reach the correct
 708       // value for that area.
 709       // We add counts of the regions of the same kind as the active region
 710       // to handle the both situations.
 711       if (I->Kind == Active->Kind)
 712         Active->ExecutionCount += I->ExecutionCount;
 713     }
 714     return Regions.drop_back(std::distance(++Active, End));
 715   }
 716
 717 public:
 718   /// Build a sorted list of CoverageSegments from a list of Regions.
 719   static std::vector<CoverageSegment>
 720   buildSegments(MutableArrayRef<CountedRegion> Regions) {
 721     std::vector<CoverageSegment> Segments;
 722     SegmentBuilder Builder(Segments);
 723
 724     sortNestedRegions(Regions);
 725     ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
 726
 727     LLVM_DEBUG({
 728       dbgs() << "Combined regions:\n";
 729       for (const auto &CR : CombinedRegions)
 730         dbgs() << "  " << CR.LineStart << ":" << CR.ColumnStart << " -> "
 731                << CR.LineEnd << ":" << CR.ColumnEnd
 732                << " (count=" << CR.ExecutionCount << ")\n";
 733     });
 734
 735     Builder.buildSegmentsImpl(CombinedRegions);
 736
 737 #ifndef NDEBUG
 738     for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
 739       const auto &L = Segments[I - 1];
 740       const auto &R = Segments[I];
 741       if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
 742         if (L.Line == R.Line && L.Col == R.Col && !L.HasCount)
 743           continue;
 744         LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
 745                           << " followed by " << R.Line << ":" << R.Col << "\n");
 746         assert(false && "Coverage segments not unique or sorted");
 747       }
 748     }
 749 #endif
 750
 751     return Segments;
 752   }
 753 };
 754
 755 } // end anonymous namespace
 756
 757 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
 758   std::vector<StringRef> Filenames;
 759   for (const auto &Function : getCoveredFunctions())
 760     llvm::append_range(Filenames, Function.Filenames);
 761   llvm::sort(Filenames);
 762   auto Last = std::unique(Filenames.begin(), Filenames.end());
 763   Filenames.erase(Last, Filenames.end());
 764   return Filenames;
 765 }
 766
 767 static SmallBitVector gatherFileIDs(StringRef SourceFile,
 768                                     const FunctionRecord &Function) {
 769   SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
 770   for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
 771     if (SourceFile == Function.Filenames[I])
 772       FilenameEquivalence[I] = true;
 773   return FilenameEquivalence;
 774 }
 775
 776 /// Return the ID of the file where the definition of the function is located.
 777 static std::optional<unsigned>
 778 findMainViewFileID(const FunctionRecord &Function) {
 779   SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
 780   for (const auto &CR : Function.CountedRegions)
 781     if (CR.Kind == CounterMappingRegion::ExpansionRegion)
 782       IsNotExpandedFile[CR.ExpandedFileID] = false;
 783   int I = IsNotExpandedFile.find_first();
 784   if (I == -1)
 785     return std::nullopt;
 786   return I;
 787 }
 788
 789 /// Check if SourceFile is the file that contains the definition of
 790 /// the Function. Return the ID of the file in that case or std::nullopt
 791 /// otherwise.
 792 static std::optional<unsigned>
 793 findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) {
 794   std::optional<unsigned> I = findMainViewFileID(Function);
 795   if (I && SourceFile == Function.Filenames[*I])
 796     return I;
 797   return std::nullopt;
 798 }
 799
 800 static bool isExpansion(const CountedRegion &R, unsigned FileID) {
 801   return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
 802 }
 803
 804 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
 805   CoverageData FileCoverage(Filename);
 806   std::vector<CountedRegion> Regions;
 807
 808   // Look up the function records in the given file. Due to hash collisions on
 809   // the filename, we may get back some records that are not in the file.
 810   ArrayRef<unsigned> RecordIndices =
 811       getImpreciseRecordIndicesForFilename(Filename);
 812   for (unsigned RecordIndex : RecordIndices) {
 813     const FunctionRecord &Function = Functions[RecordIndex];
 814     auto MainFileID = findMainViewFileID(Filename, Function);
 815     auto FileIDs = gatherFileIDs(Filename, Function);
 816     for (const auto &CR : Function.CountedRegions)
 817       if (FileIDs.test(CR.FileID)) {
 818         Regions.push_back(CR);
 819         if (MainFileID && isExpansion(CR, *MainFileID))
 820           FileCoverage.Expansions.emplace_back(CR, Function);
 821       }
 822     // Capture branch regions specific to the function (excluding expansions).
 823     for (const auto &CR : Function.CountedBranchRegions)
 824       if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID))
 825         FileCoverage.BranchRegions.push_back(CR);
 826   }
 827
 828   LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
 829   FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
 830
 831   return FileCoverage;
 832 }
 833
 834 std::vector<InstantiationGroup>
 835 CoverageMapping::getInstantiationGroups(StringRef Filename) const {
 836   FunctionInstantiationSetCollector InstantiationSetCollector;
 837   // Look up the function records in the given file. Due to hash collisions on
 838   // the filename, we may get back some records that are not in the file.
 839   ArrayRef<unsigned> RecordIndices =
 840       getImpreciseRecordIndicesForFilename(Filename);
 841   for (unsigned RecordIndex : RecordIndices) {
 842     const FunctionRecord &Function = Functions[RecordIndex];
 843     auto MainFileID = findMainViewFileID(Filename, Function);
 844     if (!MainFileID)
 845       continue;
 846     InstantiationSetCollector.insert(Function, *MainFileID);
 847   }
 848
 849   std::vector<InstantiationGroup> Result;
 850   for (auto &InstantiationSet : InstantiationSetCollector) {
 851     InstantiationGroup IG{InstantiationSet.first.first,
 852                           InstantiationSet.first.second,
 853                           std::move(InstantiationSet.second)};
 854     Result.emplace_back(std::move(IG));
 855   }
 856   return Result;
 857 }
 858
 859 CoverageData
 860 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
 861   auto MainFileID = findMainViewFileID(Function);
 862   if (!MainFileID)
 863     return CoverageData();
 864
 865   CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
 866   std::vector<CountedRegion> Regions;
 867   for (const auto &CR : Function.CountedRegions)
 868     if (CR.FileID == *MainFileID) {
 869       Regions.push_back(CR);
 870       if (isExpansion(CR, *MainFileID))
 871         FunctionCoverage.Expansions.emplace_back(CR, Function);
 872     }
 873   // Capture branch regions specific to the function (excluding expansions).
 874   for (const auto &CR : Function.CountedBranchRegions)
 875     if (CR.FileID == *MainFileID)
 876       FunctionCoverage.BranchRegions.push_back(CR);
 877
 878   LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name
 879                     << "\n");
 880   FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
 881
 882   return FunctionCoverage;
 883 }
 884
 885 CoverageData CoverageMapping::getCoverageForExpansion(
 886     const ExpansionRecord &Expansion) const {
 887   CoverageData ExpansionCoverage(
 888       Expansion.Function.Filenames[Expansion.FileID]);
 889   std::vector<CountedRegion> Regions;
 890   for (const auto &CR : Expansion.Function.CountedRegions)
 891     if (CR.FileID == Expansion.FileID) {
 892       Regions.push_back(CR);
 893       if (isExpansion(CR, Expansion.FileID))
 894         ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
 895     }
 896   for (const auto &CR : Expansion.Function.CountedBranchRegions)
 897     // Capture branch regions that only pertain to the corresponding expansion.
 898     if (CR.FileID == Expansion.FileID)
 899       ExpansionCoverage.BranchRegions.push_back(CR);
 900
 901   LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "
 902                     << Expansion.FileID << "\n");
 903   ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
 904
 905   return ExpansionCoverage;
 906 }
 907
 908 LineCoverageStats::LineCoverageStats(
 909     ArrayRef<const CoverageSegment *> LineSegments,
 910     const CoverageSegment *WrappedSegment, unsigned Line)
 911     : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
 912       LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
 913   // Find the minimum number of regions which start in this line.
 914   unsigned MinRegionCount = 0;
 915   auto isStartOfRegion = [](const CoverageSegment *S) {
 916     return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;
 917   };
 918   for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)
 919     if (isStartOfRegion(LineSegments[I]))
 920       ++MinRegionCount;
 921
 922   bool StartOfSkippedRegion = !LineSegments.empty() &&
 923                               !LineSegments.front()->HasCount &&
 924                               LineSegments.front()->IsRegionEntry;
 925
 926   HasMultipleRegions = MinRegionCount > 1;
 927   Mapped =
 928       !StartOfSkippedRegion &&
 929       ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));
 930
 931   if (!Mapped)
 932     return;
 933
 934   // Pick the max count from the non-gap, region entry segments and the
 935   // wrapped count.
 936   if (WrappedSegment)
 937     ExecutionCount = WrappedSegment->Count;
 938   if (!MinRegionCount)
 939     return;
 940   for (const auto *LS : LineSegments)
 941     if (isStartOfRegion(LS))
 942       ExecutionCount = std::max(ExecutionCount, LS->Count);
 943 }
 944
 945 LineCoverageIterator &LineCoverageIterator::operator++() {
 946   if (Next == CD.end()) {
 947     Stats = LineCoverageStats();
 948     Ended = true;
 949     return *this;
 950   }
 951   if (Segments.size())
 952     WrappedSegment = Segments.back();
 953   Segments.clear();
 954   while (Next != CD.end() && Next->Line == Line)
 955     Segments.push_back(&*Next++);
 956   Stats = LineCoverageStats(Segments, WrappedSegment, Line);
 957   ++Line;
 958   return *this;
 959 }
 960
 961 static std::string getCoverageMapErrString(coveragemap_error Err,
 962                                            const std::string &ErrMsg = "") {
 963   std::string Msg;
 964   raw_string_ostream OS(Msg);
 965
 966   switch (Err) {
 967   case coveragemap_error::success:
 968     OS << "success";
 969     break;
 970   case coveragemap_error::eof:
 971     OS << "end of File";
 972     break;
 973   case coveragemap_error::no_data_found:
 974     OS << "no coverage data found";
 975     break;
 976   case coveragemap_error::unsupported_version:
 977     OS << "unsupported coverage format version";
 978     break;
 979   case coveragemap_error::truncated:
 980     OS << "truncated coverage data";
 981     break;
 982   case coveragemap_error::malformed:
 983     OS << "malformed coverage data";
 984     break;
 985   case coveragemap_error::decompression_failed:
 986     OS << "failed to decompress coverage data (zlib)";
 987     break;
 988   case coveragemap_error::invalid_or_missing_arch_specifier:
 989     OS << "`-arch` specifier is invalid or missing for universal binary";
 990     break;
 991   }
 992
 993   // If optional error message is not empty, append it to the message.
 994   if (!ErrMsg.empty())
 995     OS << ": " << ErrMsg;
 996
 997   return Msg;
 998 }
 999
1000 namespace {
1001
1002 // FIXME: This class is only here to support the transition to llvm::Error. It
1003 // will be removed once this transition is complete. Clients should prefer to
1004 // deal with the Error value directly, rather than converting to error_code.
1005 class CoverageMappingErrorCategoryType : public std::error_category {
1006   const char *name() const noexcept override { return "llvm.coveragemap"; }
1007   std::string message(int IE) const override {
1008     return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
1009   }
1010 };
1011
1012 } // end anonymous namespace
1013
1014 std::string CoverageMapError::message() const {
1015   return getCoverageMapErrString(Err, Msg);
1016 }
1017
1018 const std::error_category &llvm::coverage::coveragemap_category() {
1019   static CoverageMappingErrorCategoryType ErrorCategory;
1020   return ErrorCategory;
1021 }
1022
1023 char CoverageMapError::ID = 0;