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(Record.FunctionName, Record.FunctionHash);
226      return Error::success();
227    } else if (IPE != instrprof_error::unknown_function)
228      return make_error<InstrProfError>(IPE);
229    Counts.assign(Record.MappingRegions.size(), 0);
230  }
231  Ctx.setCounts(Counts);
232
233  assert(!Record.MappingRegions.empty() && "Function has no regions");
234
235  // This coverage record is a zero region for a function that's unused in
236  // some TU, but used in a different TU. Ignore it. The coverage maps from the
237  // the other TU will either be loaded (providing full region counts) or they
238  // won't (in which case we don't unintuitively report functions as uncovered
239  // when they have non-zero counts in the profile).
240  if (Record.MappingRegions.size() == 1 &&
241      Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
242    return Error::success();
243
244  FunctionRecord Function(OrigFuncName, Record.Filenames);
245  for (const auto &Region : Record.MappingRegions) {
246    Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
247    if (auto E = ExecutionCount.takeError()) {
248      consumeError(std::move(E));
249      return Error::success();
250    }
251    Function.pushRegion(Region, *ExecutionCount);
252  }
253
254  // Don't create records for (filenames, function) pairs we've already seen.
255  auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),
256                                          Record.Filenames.end());
257  if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)
258    return Error::success();
259
260  Functions.push_back(std::move(Function));
261
262  // Performance optimization: keep track of the indices of the function records
263  // which correspond to each filename. This can be used to substantially speed
264  // up queries for coverage info in a file.
265  unsigned RecordIndex = Functions.size() - 1;
266  for (StringRef Filename : Record.Filenames) {
267    auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)];
268    // Note that there may be duplicates in the filename set for a function
269    // record, because of e.g. macro expansions in the function in which both
270    // the macro and the function are defined in the same file.
271    if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)
272      RecordIndices.push_back(RecordIndex);
273  }
274
275  return Error::success();
276}
277
278Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
279    ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
280    IndexedInstrProfReader &ProfileReader) {
281  auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
282
283  for (const auto &CoverageReader : CoverageReaders) {
284    for (auto RecordOrErr : *CoverageReader) {
285      if (Error E = RecordOrErr.takeError())
286        return std::move(E);
287      const auto &Record = *RecordOrErr;
288      if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader))
289        return std::move(E);
290    }
291  }
292
293  return std::move(Coverage);
294}
295
296// If E is a no_data_found error, returns success. Otherwise returns E.
297static Error handleMaybeNoDataFoundError(Error E) {
298  return handleErrors(
299      std::move(E), [](const CoverageMapError &CME) {
300        if (CME.get() == coveragemap_error::no_data_found)
301          return static_cast<Error>(Error::success());
302        return make_error<CoverageMapError>(CME.get());
303      });
304}
305
306Expected<std::unique_ptr<CoverageMapping>>
307CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames,
308                      StringRef ProfileFilename, ArrayRef<StringRef> Arches) {
309  auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
310  if (Error E = ProfileReaderOrErr.takeError())
311    return std::move(E);
312  auto ProfileReader = std::move(ProfileReaderOrErr.get());
313
314  SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;
315  SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;
316  for (const auto &File : llvm::enumerate(ObjectFilenames)) {
317    auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value());
318    if (std::error_code EC = CovMappingBufOrErr.getError())
319      return errorCodeToError(EC);
320    StringRef Arch = Arches.empty() ? StringRef() : Arches[File.index()];
321    MemoryBufferRef CovMappingBufRef =
322        CovMappingBufOrErr.get()->getMemBufferRef();
323    auto CoverageReadersOrErr =
324        BinaryCoverageReader::create(CovMappingBufRef, Arch, Buffers);
325    if (Error E = CoverageReadersOrErr.takeError()) {
326      E = handleMaybeNoDataFoundError(std::move(E));
327      if (E)
328        return std::move(E);
329      // E == success (originally a no_data_found error).
330      continue;
331    }
332    for (auto &Reader : CoverageReadersOrErr.get())
333      Readers.push_back(std::move(Reader));
334    Buffers.push_back(std::move(CovMappingBufOrErr.get()));
335  }
336  // If no readers were created, either no objects were provided or none of them
337  // had coverage data. Return an error in the latter case.
338  if (Readers.empty() && !ObjectFilenames.empty())
339    return make_error<CoverageMapError>(coveragemap_error::no_data_found);
340  return load(Readers, *ProfileReader);
341}
342
343namespace {
344
345/// Distributes functions into instantiation sets.
346///
347/// An instantiation set is a collection of functions that have the same source
348/// code, ie, template functions specializations.
349class FunctionInstantiationSetCollector {
350  using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
351  MapT InstantiatedFunctions;
352
353public:
354  void insert(const FunctionRecord &Function, unsigned FileID) {
355    auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
356    while (I != E && I->FileID != FileID)
357      ++I;
358    assert(I != E && "function does not cover the given file");
359    auto &Functions = InstantiatedFunctions[I->startLoc()];
360    Functions.push_back(&Function);
361  }
362
363  MapT::iterator begin() { return InstantiatedFunctions.begin(); }
364  MapT::iterator end() { return InstantiatedFunctions.end(); }
365};
366
367class SegmentBuilder {
368  std::vector<CoverageSegment> &Segments;
369  SmallVector<const CountedRegion *, 8> ActiveRegions;
370
371  SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
372
373  /// Emit a segment with the count from \p Region starting at \p StartLoc.
374  //
375  /// \p IsRegionEntry: The segment is at the start of a new non-gap region.
376  /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
377  void startSegment(const CountedRegion &Region, LineColPair StartLoc,
378                    bool IsRegionEntry, bool EmitSkippedRegion = false) {
379    bool HasCount = !EmitSkippedRegion &&
380                    (Region.Kind != CounterMappingRegion::SkippedRegion);
381
382    // If the new segment wouldn't affect coverage rendering, skip it.
383    if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
384      const auto &Last = Segments.back();
385      if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
386          !Last.IsRegionEntry)
387        return;
388    }
389
390    if (HasCount)
391      Segments.emplace_back(StartLoc.first, StartLoc.second,
392                            Region.ExecutionCount, IsRegionEntry,
393                            Region.Kind == CounterMappingRegion::GapRegion);
394    else
395      Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);
396
397    LLVM_DEBUG({
398      const auto &Last = Segments.back();
399      dbgs() << "Segment at " << Last.Line << ":" << Last.Col
400             << " (count = " << Last.Count << ")"
401             << (Last.IsRegionEntry ? ", RegionEntry" : "")
402             << (!Last.HasCount ? ", Skipped" : "")
403             << (Last.IsGapRegion ? ", Gap" : "") << "\n";
404    });
405  }
406
407  /// Emit segments for active regions which end before \p Loc.
408  ///
409  /// \p Loc: The start location of the next region. If None, all active
410  /// regions are completed.
411  /// \p FirstCompletedRegion: Index of the first completed region.
412  void completeRegionsUntil(Optional<LineColPair> Loc,
413                            unsigned FirstCompletedRegion) {
414    // Sort the completed regions by end location. This makes it simple to
415    // emit closing segments in sorted order.
416    auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
417    std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
418                      [](const CountedRegion *L, const CountedRegion *R) {
419                        return L->endLoc() < R->endLoc();
420                      });
421
422    // Emit segments for all completed regions.
423    for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
424         ++I) {
425      const auto *CompletedRegion = ActiveRegions[I];
426      assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
427             "Completed region ends after start of new region");
428
429      const auto *PrevCompletedRegion = ActiveRegions[I - 1];
430      auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
431
432      // Don't emit any more segments if they start where the new region begins.
433      if (Loc && CompletedSegmentLoc == *Loc)
434        break;
435
436      // Don't emit a segment if the next completed region ends at the same
437      // location as this one.
438      if (CompletedSegmentLoc == CompletedRegion->endLoc())
439        continue;
440
441      // Use the count from the last completed region which ends at this loc.
442      for (unsigned J = I + 1; J < E; ++J)
443        if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
444          CompletedRegion = ActiveRegions[J];
445
446      startSegment(*CompletedRegion, CompletedSegmentLoc, false);
447    }
448
449    auto Last = ActiveRegions.back();
450    if (FirstCompletedRegion && Last->endLoc() != *Loc) {
451      // If there's a gap after the end of the last completed region and the
452      // start of the new region, use the last active region to fill the gap.
453      startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
454                   false);
455    } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
456      // Emit a skipped segment if there are no more active regions. This
457      // ensures that gaps between functions are marked correctly.
458      startSegment(*Last, Last->endLoc(), false, true);
459    }
460
461    // Pop the completed regions.
462    ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
463  }
464
465  void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
466    for (const auto &CR : enumerate(Regions)) {
467      auto CurStartLoc = CR.value().startLoc();
468
469      // Active regions which end before the current region need to be popped.
470      auto CompletedRegions =
471          std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
472                                [&](const CountedRegion *Region) {
473                                  return !(Region->endLoc() <= CurStartLoc);
474                                });
475      if (CompletedRegions != ActiveRegions.end()) {
476        unsigned FirstCompletedRegion =
477            std::distance(ActiveRegions.begin(), CompletedRegions);
478        completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
479      }
480
481      bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;
482
483      // Try to emit a segment for the current region.
484      if (CurStartLoc == CR.value().endLoc()) {
485        // Avoid making zero-length regions active. If it's the last region,
486        // emit a skipped segment. Otherwise use its predecessor's count.
487        const bool Skipped = (CR.index() + 1) == Regions.size();
488        startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
489                     CurStartLoc, !GapRegion, Skipped);
490        continue;
491      }
492      if (CR.index() + 1 == Regions.size() ||
493          CurStartLoc != Regions[CR.index() + 1].startLoc()) {
494        // Emit a segment if the next region doesn't start at the same location
495        // as this one.
496        startSegment(CR.value(), CurStartLoc, !GapRegion);
497      }
498
499      // This region is active (i.e not completed).
500      ActiveRegions.push_back(&CR.value());
501    }
502
503    // Complete any remaining active regions.
504    if (!ActiveRegions.empty())
505      completeRegionsUntil(None, 0);
506  }
507
508  /// Sort a nested sequence of regions from a single file.
509  static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
510    llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {
511      if (LHS.startLoc() != RHS.startLoc())
512        return LHS.startLoc() < RHS.startLoc();
513      if (LHS.endLoc() != RHS.endLoc())
514        // When LHS completely contains RHS, we sort LHS first.
515        return RHS.endLoc() < LHS.endLoc();
516      // If LHS and RHS cover the same area, we need to sort them according
517      // to their kinds so that the most suitable region will become "active"
518      // in combineRegions(). Because we accumulate counter values only from
519      // regions of the same kind as the first region of the area, prefer
520      // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
521      static_assert(CounterMappingRegion::CodeRegion <
522                            CounterMappingRegion::ExpansionRegion &&
523                        CounterMappingRegion::ExpansionRegion <
524                            CounterMappingRegion::SkippedRegion,
525                    "Unexpected order of region kind values");
526      return LHS.Kind < RHS.Kind;
527    });
528  }
529
530  /// Combine counts of regions which cover the same area.
531  static ArrayRef<CountedRegion>
532  combineRegions(MutableArrayRef<CountedRegion> Regions) {
533    if (Regions.empty())
534      return Regions;
535    auto Active = Regions.begin();
536    auto End = Regions.end();
537    for (auto I = Regions.begin() + 1; I != End; ++I) {
538      if (Active->startLoc() != I->startLoc() ||
539          Active->endLoc() != I->endLoc()) {
540        // Shift to the next region.
541        ++Active;
542        if (Active != I)
543          *Active = *I;
544        continue;
545      }
546      // Merge duplicate region.
547      // If CodeRegions and ExpansionRegions cover the same area, it's probably
548      // a macro which is fully expanded to another macro. In that case, we need
549      // to accumulate counts only from CodeRegions, or else the area will be
550      // counted twice.
551      // On the other hand, a macro may have a nested macro in its body. If the
552      // outer macro is used several times, the ExpansionRegion for the nested
553      // macro will also be added several times. These ExpansionRegions cover
554      // the same source locations and have to be combined to reach the correct
555      // value for that area.
556      // We add counts of the regions of the same kind as the active region
557      // to handle the both situations.
558      if (I->Kind == Active->Kind)
559        Active->ExecutionCount += I->ExecutionCount;
560    }
561    return Regions.drop_back(std::distance(++Active, End));
562  }
563
564public:
565  /// Build a sorted list of CoverageSegments from a list of Regions.
566  static std::vector<CoverageSegment>
567  buildSegments(MutableArrayRef<CountedRegion> Regions) {
568    std::vector<CoverageSegment> Segments;
569    SegmentBuilder Builder(Segments);
570
571    sortNestedRegions(Regions);
572    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
573
574    LLVM_DEBUG({
575      dbgs() << "Combined regions:\n";
576      for (const auto &CR : CombinedRegions)
577        dbgs() << "  " << CR.LineStart << ":" << CR.ColumnStart << " -> "
578               << CR.LineEnd << ":" << CR.ColumnEnd
579               << " (count=" << CR.ExecutionCount << ")\n";
580    });
581
582    Builder.buildSegmentsImpl(CombinedRegions);
583
584#ifndef NDEBUG
585    for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
586      const auto &L = Segments[I - 1];
587      const auto &R = Segments[I];
588      if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
589        LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
590                          << " followed by " << R.Line << ":" << R.Col << "\n");
591        assert(false && "Coverage segments not unique or sorted");
592      }
593    }
594#endif
595
596    return Segments;
597  }
598};
599
600} // end anonymous namespace
601
602std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
603  std::vector<StringRef> Filenames;
604  for (const auto &Function : getCoveredFunctions())
605    Filenames.insert(Filenames.end(), Function.Filenames.begin(),
606                     Function.Filenames.end());
607  llvm::sort(Filenames);
608  auto Last = std::unique(Filenames.begin(), Filenames.end());
609  Filenames.erase(Last, Filenames.end());
610  return Filenames;
611}
612
613static SmallBitVector gatherFileIDs(StringRef SourceFile,
614                                    const FunctionRecord &Function) {
615  SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
616  for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
617    if (SourceFile == Function.Filenames[I])
618      FilenameEquivalence[I] = true;
619  return FilenameEquivalence;
620}
621
622/// Return the ID of the file where the definition of the function is located.
623static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
624  SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
625  for (const auto &CR : Function.CountedRegions)
626    if (CR.Kind == CounterMappingRegion::ExpansionRegion)
627      IsNotExpandedFile[CR.ExpandedFileID] = false;
628  int I = IsNotExpandedFile.find_first();
629  if (I == -1)
630    return None;
631  return I;
632}
633
634/// Check if SourceFile is the file that contains the definition of
635/// the Function. Return the ID of the file in that case or None otherwise.
636static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
637                                             const FunctionRecord &Function) {
638  Optional<unsigned> I = findMainViewFileID(Function);
639  if (I && SourceFile == Function.Filenames[*I])
640    return I;
641  return None;
642}
643
644static bool isExpansion(const CountedRegion &R, unsigned FileID) {
645  return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
646}
647
648CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
649  CoverageData FileCoverage(Filename);
650  std::vector<CountedRegion> Regions;
651
652  // Look up the function records in the given file. Due to hash collisions on
653  // the filename, we may get back some records that are not in the file.
654  ArrayRef<unsigned> RecordIndices =
655      getImpreciseRecordIndicesForFilename(Filename);
656  for (unsigned RecordIndex : RecordIndices) {
657    const FunctionRecord &Function = Functions[RecordIndex];
658    auto MainFileID = findMainViewFileID(Filename, Function);
659    auto FileIDs = gatherFileIDs(Filename, Function);
660    for (const auto &CR : Function.CountedRegions)
661      if (FileIDs.test(CR.FileID)) {
662        Regions.push_back(CR);
663        if (MainFileID && isExpansion(CR, *MainFileID))
664          FileCoverage.Expansions.emplace_back(CR, Function);
665      }
666  }
667
668  LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
669  FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
670
671  return FileCoverage;
672}
673
674std::vector<InstantiationGroup>
675CoverageMapping::getInstantiationGroups(StringRef Filename) const {
676  FunctionInstantiationSetCollector InstantiationSetCollector;
677  // Look up the function records in the given file. Due to hash collisions on
678  // the filename, we may get back some records that are not in the file.
679  ArrayRef<unsigned> RecordIndices =
680      getImpreciseRecordIndicesForFilename(Filename);
681  for (unsigned RecordIndex : RecordIndices) {
682    const FunctionRecord &Function = Functions[RecordIndex];
683    auto MainFileID = findMainViewFileID(Filename, Function);
684    if (!MainFileID)
685      continue;
686    InstantiationSetCollector.insert(Function, *MainFileID);
687  }
688
689  std::vector<InstantiationGroup> Result;
690  for (auto &InstantiationSet : InstantiationSetCollector) {
691    InstantiationGroup IG{InstantiationSet.first.first,
692                          InstantiationSet.first.second,
693                          std::move(InstantiationSet.second)};
694    Result.emplace_back(std::move(IG));
695  }
696  return Result;
697}
698
699CoverageData
700CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
701  auto MainFileID = findMainViewFileID(Function);
702  if (!MainFileID)
703    return CoverageData();
704
705  CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
706  std::vector<CountedRegion> Regions;
707  for (const auto &CR : Function.CountedRegions)
708    if (CR.FileID == *MainFileID) {
709      Regions.push_back(CR);
710      if (isExpansion(CR, *MainFileID))
711        FunctionCoverage.Expansions.emplace_back(CR, Function);
712    }
713
714  LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name
715                    << "\n");
716  FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
717
718  return FunctionCoverage;
719}
720
721CoverageData CoverageMapping::getCoverageForExpansion(
722    const ExpansionRecord &Expansion) const {
723  CoverageData ExpansionCoverage(
724      Expansion.Function.Filenames[Expansion.FileID]);
725  std::vector<CountedRegion> Regions;
726  for (const auto &CR : Expansion.Function.CountedRegions)
727    if (CR.FileID == Expansion.FileID) {
728      Regions.push_back(CR);
729      if (isExpansion(CR, Expansion.FileID))
730        ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
731    }
732
733  LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "
734                    << Expansion.FileID << "\n");
735  ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
736
737  return ExpansionCoverage;
738}
739
740LineCoverageStats::LineCoverageStats(
741    ArrayRef<const CoverageSegment *> LineSegments,
742    const CoverageSegment *WrappedSegment, unsigned Line)
743    : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
744      LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
745  // Find the minimum number of regions which start in this line.
746  unsigned MinRegionCount = 0;
747  auto isStartOfRegion = [](const CoverageSegment *S) {
748    return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;
749  };
750  for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)
751    if (isStartOfRegion(LineSegments[I]))
752      ++MinRegionCount;
753
754  bool StartOfSkippedRegion = !LineSegments.empty() &&
755                              !LineSegments.front()->HasCount &&
756                              LineSegments.front()->IsRegionEntry;
757
758  HasMultipleRegions = MinRegionCount > 1;
759  Mapped =
760      !StartOfSkippedRegion &&
761      ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));
762
763  if (!Mapped)
764    return;
765
766  // Pick the max count from the non-gap, region entry segments and the
767  // wrapped count.
768  if (WrappedSegment)
769    ExecutionCount = WrappedSegment->Count;
770  if (!MinRegionCount)
771    return;
772  for (const auto *LS : LineSegments)
773    if (isStartOfRegion(LS))
774      ExecutionCount = std::max(ExecutionCount, LS->Count);
775}
776
777LineCoverageIterator &LineCoverageIterator::operator++() {
778  if (Next == CD.end()) {
779    Stats = LineCoverageStats();
780    Ended = true;
781    return *this;
782  }
783  if (Segments.size())
784    WrappedSegment = Segments.back();
785  Segments.clear();
786  while (Next != CD.end() && Next->Line == Line)
787    Segments.push_back(&*Next++);
788  Stats = LineCoverageStats(Segments, WrappedSegment, Line);
789  ++Line;
790  return *this;
791}
792
793static std::string getCoverageMapErrString(coveragemap_error Err) {
794  switch (Err) {
795  case coveragemap_error::success:
796    return "Success";
797  case coveragemap_error::eof:
798    return "End of File";
799  case coveragemap_error::no_data_found:
800    return "No coverage data found";
801  case coveragemap_error::unsupported_version:
802    return "Unsupported coverage format version";
803  case coveragemap_error::truncated:
804    return "Truncated coverage data";
805  case coveragemap_error::malformed:
806    return "Malformed coverage data";
807  }
808  llvm_unreachable("A value of coveragemap_error has no message.");
809}
810
811namespace {
812
813// FIXME: This class is only here to support the transition to llvm::Error. It
814// will be removed once this transition is complete. Clients should prefer to
815// deal with the Error value directly, rather than converting to error_code.
816class CoverageMappingErrorCategoryType : public std::error_category {
817  const char *name() const noexcept override { return "llvm.coveragemap"; }
818  std::string message(int IE) const override {
819    return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
820  }
821};
822
823} // end anonymous namespace
824
825std::string CoverageMapError::message() const {
826  return getCoverageMapErrString(Err);
827}
828
829static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory;
830
831const std::error_category &llvm::coverage::coveragemap_category() {
832  return *ErrorCategory;
833}
834
835char CoverageMapError::ID = 0;
836