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