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