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