1//===-- LVCompare.cpp -----------------------------------------------------===//
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 implements the LVCompare class.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/DebugInfo/LogicalView/Core/LVCompare.h"
14#include "llvm/DebugInfo/LogicalView/Core/LVOptions.h"
15#include "llvm/DebugInfo/LogicalView/Core/LVReader.h"
16#include <tuple>
17
18using namespace llvm;
19using namespace llvm::logicalview;
20
21#define DEBUG_TYPE "Compare"
22
23namespace {
24
25enum class LVCompareItem { Scope, Symbol, Type, Line, Total };
26enum class LVCompareIndex { Header, Expected, Missing, Added };
27using LVCompareEntry = std::tuple<const char *, unsigned, unsigned, unsigned>;
28using LVCompareInfo = std::map<LVCompareItem, LVCompareEntry>;
29LVCompareInfo Results = {
30    {LVCompareItem::Line, LVCompareEntry("Lines", 0, 0, 0)},
31    {LVCompareItem::Scope, LVCompareEntry("Scopes", 0, 0, 0)},
32    {LVCompareItem::Symbol, LVCompareEntry("Symbols", 0, 0, 0)},
33    {LVCompareItem::Type, LVCompareEntry("Types", 0, 0, 0)},
34    {LVCompareItem::Total, LVCompareEntry("Total", 0, 0, 0)}};
35static LVCompareInfo::iterator IterTotal = Results.end();
36
37constexpr unsigned getHeader() {
38  return static_cast<unsigned>(LVCompareIndex::Header);
39}
40constexpr unsigned getExpected() {
41  return static_cast<unsigned>(LVCompareIndex::Expected);
42}
43constexpr unsigned getMissing() {
44  return static_cast<unsigned>(LVCompareIndex::Missing);
45}
46constexpr unsigned getAdded() {
47  return static_cast<unsigned>(LVCompareIndex::Added);
48}
49
50LVCompare *CurrentComparator = nullptr;
51
52void zeroResults() {
53  // In case the same reader instance is used.
54  for (LVCompareInfo::reference Entry : Results) {
55    std::get<getExpected()>(Entry.second) = 0;
56    std::get<getMissing()>(Entry.second) = 0;
57    std::get<getAdded()>(Entry.second) = 0;
58  }
59  IterTotal = Results.find(LVCompareItem::Total);
60  assert(IterTotal != Results.end());
61}
62
63LVCompareInfo::iterator getResultsEntry(LVElement *Element) {
64  LVCompareItem Kind;
65  if (Element->getIsLine())
66    Kind = LVCompareItem::Line;
67  else if (Element->getIsScope())
68    Kind = LVCompareItem::Scope;
69  else if (Element->getIsSymbol())
70    Kind = LVCompareItem::Symbol;
71  else
72    Kind = LVCompareItem::Type;
73
74  // Used to update the expected, missing or added entry for the given kind.
75  LVCompareInfo::iterator Iter = Results.find(Kind);
76  assert(Iter != Results.end());
77  return Iter;
78}
79
80void updateExpected(LVElement *Element) {
81  LVCompareInfo::iterator Iter = getResultsEntry(Element);
82  // Update total for expected.
83  ++std::get<getExpected()>(IterTotal->second);
84  // Update total for specific element kind.
85  ++std::get<getExpected()>(Iter->second);
86}
87
88void updateMissingOrAdded(LVElement *Element, LVComparePass Pass) {
89  LVCompareInfo::iterator Iter = getResultsEntry(Element);
90  if (Pass == LVComparePass::Missing) {
91    ++std::get<getMissing()>(IterTotal->second);
92    ++std::get<getMissing()>(Iter->second);
93  } else {
94    ++std::get<getAdded()>(IterTotal->second);
95    ++std::get<getAdded()>(Iter->second);
96  }
97}
98
99} // namespace
100
101LVCompare &LVCompare::getInstance() {
102  static LVCompare DefaultComparator(outs());
103  return CurrentComparator ? *CurrentComparator : DefaultComparator;
104}
105
106void LVCompare::setInstance(LVCompare *Comparator) {
107  CurrentComparator = Comparator;
108}
109
110LVCompare::LVCompare(raw_ostream &OS) : OS(OS) {
111  PrintLines = options().getPrintLines();
112  PrintSymbols = options().getPrintSymbols();
113  PrintTypes = options().getPrintTypes();
114  PrintScopes =
115      options().getPrintScopes() || PrintLines || PrintSymbols || PrintTypes;
116}
117
118Error LVCompare::execute(LVReader *ReferenceReader, LVReader *TargetReader) {
119  setInstance(this);
120  // In the case of added elements, the 'Reference' reader will be modified;
121  // those elements will be added to it. Update the current reader instance.
122  LVReader::setInstance(ReferenceReader);
123
124  auto PrintHeader = [this](LVScopeRoot *LHS, LVScopeRoot *RHS) {
125    LLVM_DEBUG({
126      dbgs() << "[Reference] " << LHS->getName() << "\n"
127             << "[Target] " << RHS->getName() << "\n";
128    });
129    OS << "\nReference: " << formattedName(LHS->getName()) << "\n"
130       << "Target:    " << formattedName(RHS->getName()) << "\n";
131  };
132
133  // We traverse the given scopes tree ('Reference' and 'Target') twice.
134  // The first time we look for missing items from the 'Reference' and the
135  // second time we look for items added to the 'Target'.
136  // The comparison test includes the name, lexical level, type, source
137  // location, etc.
138  LVScopeRoot *ReferenceRoot = ReferenceReader->getScopesRoot();
139  LVScopeRoot *TargetRoot = TargetReader->getScopesRoot();
140  ReferenceRoot->setIsInCompare();
141  TargetRoot->setIsInCompare();
142
143  // Reset possible previous results.
144  zeroResults();
145
146  if (options().getCompareContext()) {
147    // Perform a logical view comparison as a whole unit. We start at the
148    // root reference; at each scope an equal test is applied to its children.
149    // If a difference is found, the current path is marked as missing.
150    auto CompareViews = [this](LVScopeRoot *LHS, LVScopeRoot *RHS) -> Error {
151      LHS->markMissingParents(RHS, /*TraverseChildren=*/true);
152      if (LHS->getIsMissingLink() && options().getReportAnyView()) {
153        // As we are printing a missing tree, enable formatting.
154        options().setPrintFormatting();
155        OS << "\nMissing Tree:\n";
156        if (Error Err = LHS->doPrint(/*Split=*/false, /*Match=*/false,
157                                     /*Print=*/true, OS))
158          return Err;
159        options().resetPrintFormatting();
160      }
161
162      return Error::success();
163    };
164
165    // If the user has requested printing details for the comparison, we
166    // disable the indentation and the added/missing tags ('+'/'-'), as the
167    // details are just a list of elements.
168    options().resetPrintFormatting();
169
170    PrintHeader(ReferenceRoot, TargetRoot);
171    Reader = ReferenceReader;
172    if (Error Err = CompareViews(ReferenceRoot, TargetRoot))
173      return Err;
174    FirstMissing = true;
175    ReferenceRoot->report(LVComparePass::Missing);
176
177    PrintHeader(TargetRoot, ReferenceRoot);
178    Reader = TargetReader;
179    if (Error Err = CompareViews(TargetRoot, ReferenceRoot))
180      return Err;
181    FirstMissing = true;
182    TargetRoot->report(LVComparePass::Added);
183
184    options().setPrintFormatting();
185
186    // Display a summary with the elements missing and/or added.
187    printSummary();
188  } else {
189    // Perform logical elements comparison. An equal test is apply to each
190    // element. If a difference is found, the reference element is marked as
191    // 'missing'.
192    // The final comparison result will show the 'Reference' scopes tree,
193    // having both missing and added elements.
194    using LVScopeLink = std::map<LVScope *, LVScope *>;
195    LVScopeLink ScopeLinks;
196    auto CompareReaders = [&](LVReader *LHS, LVReader *RHS, LVElements &Set,
197                              LVComparePass Pass) -> Error {
198      auto FindMatch = [&](auto &References, auto &Targets,
199                           const char *Category) -> Error {
200        LVElements Elements;
201        for (LVElement *Reference : References) {
202          // Report elements that can be printed; ignore logical elements that
203          // have qualifiers.
204          if (Reference->getIncludeInPrint()) {
205            if (Pass == LVComparePass::Missing)
206              updateExpected(Reference);
207            Reference->setIsInCompare();
208            LVElement *CurrentTarget = nullptr;
209            if (llvm::any_of(Targets, [&](auto Target) -> bool {
210                  CurrentTarget = Target;
211                  return Reference->equals(Target);
212                })) {
213              if (Pass == LVComparePass::Missing && Reference->getIsScope()) {
214                // If the elements being compared are scopes and are a match,
215                // they are recorded, to be used when creating the augmented
216                // tree, as insertion points for the "added" items.
217                ScopeLinks.emplace(static_cast<LVScope *>(CurrentTarget),
218                                   static_cast<LVScope *>(Reference));
219              }
220            } else {
221              // Element is missing or added.
222              Pass == LVComparePass::Missing ? Reference->setIsMissing()
223                                             : Reference->setIsAdded();
224              Elements.push_back(Reference);
225              updateMissingOrAdded(Reference, Pass);
226              // Record missing/added element.
227              addPassEntry(Reader, Reference, Pass);
228            }
229          }
230        }
231        if (Pass == LVComparePass::Added)
232          // Record all the current missing elements for this category.
233          Set.insert(Set.end(), Elements.begin(), Elements.end());
234        if (options().getReportList()) {
235          if (Elements.size()) {
236            OS << "\n(" << Elements.size() << ") "
237               << (Pass == LVComparePass::Missing ? "Missing" : "Added") << " "
238               << Category << ":\n";
239            for (const LVElement *Element : Elements) {
240              if (Error Err = Element->doPrint(/*Split=*/false, /*Match=*/false,
241                                               /*Print=*/true, OS))
242                return Err;
243            }
244          }
245        }
246
247        return Error::success();
248      };
249
250      // First compare the scopes, so they will be inserted at the front of
251      // the missing elements list. When they are moved, their children are
252      // moved as well and no additional work is required.
253      if (options().getCompareScopes())
254        if (Error Err = FindMatch(LHS->getScopes(), RHS->getScopes(), "Scopes"))
255          return Err;
256      if (options().getCompareSymbols())
257        if (Error Err =
258                FindMatch(LHS->getSymbols(), RHS->getSymbols(), "Symbols"))
259          return Err;
260      if (options().getCompareTypes())
261        if (Error Err = FindMatch(LHS->getTypes(), RHS->getTypes(), "Types"))
262          return Err;
263      if (options().getCompareLines())
264        if (Error Err = FindMatch(LHS->getLines(), RHS->getLines(), "Lines"))
265          return Err;
266
267      return Error::success();
268    };
269
270    // If the user has requested printing details for the comparison, we
271    // disable the indentation and the added/missing tags ('+'/'-'), as the
272    // details are just a list of elements.
273    options().resetPrintFormatting();
274
275    PrintHeader(ReferenceRoot, TargetRoot);
276    // Include the root in the expected count.
277    updateExpected(ReferenceRoot);
278
279    LVElements ElementsToAdd;
280    Reader = ReferenceReader;
281    if (Error Err = CompareReaders(ReferenceReader, TargetReader, ElementsToAdd,
282                                   LVComparePass::Missing))
283      return Err;
284    Reader = TargetReader;
285    if (Error Err = CompareReaders(TargetReader, ReferenceReader, ElementsToAdd,
286                                   LVComparePass::Added))
287      return Err;
288
289    LLVM_DEBUG({
290      dbgs() << "\nReference/Target Scope links:\n";
291      for (LVScopeLink::const_reference Entry : ScopeLinks)
292        dbgs() << "Source: " << hexSquareString(Entry.first->getOffset()) << " "
293               << "Destination: " << hexSquareString(Entry.second->getOffset())
294               << "\n";
295      dbgs() << "\n";
296    });
297
298    // Add the 'missing' elements from the 'Target' into the 'Reference'.
299    // First insert the missing scopes, as they include any missing children.
300    LVScope *Parent = nullptr;
301    for (LVElement *Element : ElementsToAdd) {
302      LLVM_DEBUG({
303        dbgs() << "Element to Insert: " << hexSquareString(Element->getOffset())
304               << ", Parent: "
305               << hexSquareString(Element->getParentScope()->getOffset())
306               << "\n";
307      });
308      // Skip already inserted elements. They were inserted, if their parents
309      // were missing. When inserting them, all the children are moved.
310      if (Element->getHasMoved())
311        continue;
312
313      // We need to find an insertion point in the reference scopes tree.
314      Parent = Element->getParentScope();
315      if (ScopeLinks.find(Parent) != ScopeLinks.end()) {
316        LVScope *InsertionPoint = ScopeLinks[Parent];
317        LLVM_DEBUG({
318          dbgs() << "Inserted at: "
319                 << hexSquareString(InsertionPoint->getOffset()) << "\n";
320        });
321        if (Parent->removeElement(Element)) {
322          // Be sure we have a current compile unit.
323          getReader().setCompileUnit(InsertionPoint->getCompileUnitParent());
324          InsertionPoint->addElement(Element);
325          Element->updateLevel(InsertionPoint, /*Moved=*/true);
326        }
327      }
328    }
329
330    options().setPrintFormatting();
331
332    // Display the augmented reference scopes tree.
333    if (options().getReportAnyView())
334      if (Error Err = ReferenceReader->doPrint())
335        return Err;
336
337    LLVM_DEBUG({
338      dbgs() << "\nModified Reference Reader";
339      if (Error Err = ReferenceReader->doPrint())
340        return Err;
341      dbgs() << "\nModified Target Reader";
342      if (Error Err = TargetReader->doPrint())
343        return Err;
344    });
345
346    // Display a summary with the elements missing and/or added.
347    printSummary();
348  }
349
350  return Error::success();
351}
352
353void LVCompare::printCurrentStack() {
354  for (const LVScope *Scope : ScopeStack) {
355    Scope->printAttributes(OS);
356    OS << Scope->lineNumberAsString(/*ShowZero=*/true) << " " << Scope->kind()
357       << " " << formattedName(Scope->getName()) << "\n";
358  }
359}
360
361void LVCompare::printItem(LVElement *Element, LVComparePass Pass) {
362  // Record expected, missing, added.
363  updateExpected(Element);
364  updateMissingOrAdded(Element, Pass);
365
366  // Record missing/added element.
367  if (Element->getIsMissing())
368    addPassEntry(Reader, Element, Pass);
369
370  if ((!PrintLines && Element->getIsLine()) ||
371      (!PrintScopes && Element->getIsScope()) ||
372      (!PrintSymbols && Element->getIsSymbol()) ||
373      (!PrintTypes && Element->getIsType()))
374    return;
375
376  if (Element->getIsMissing()) {
377    if (FirstMissing) {
378      OS << "\n";
379      FirstMissing = false;
380    }
381
382    StringRef Kind = Element->kind();
383    StringRef Name =
384        Element->getIsLine() ? Element->getPathname() : Element->getName();
385    StringRef Status = (Pass == LVComparePass::Missing) ? "Missing" : "Added";
386    OS << Status << " " << Kind << " '" << Name << "'";
387    if (Element->getLineNumber() > 0)
388      OS << " at line " << Element->getLineNumber();
389    OS << "\n";
390
391    if (options().getReportList()) {
392      printCurrentStack();
393      Element->printAttributes(OS);
394      OS << Element->lineNumberAsString(/*ShowZero=*/true) << " " << Kind << " "
395         << Name << "\n";
396    }
397  }
398}
399
400void LVCompare::printSummary() const {
401  if (!options().getPrintSummary())
402    return;
403  std::string Separator = std::string(40, '-');
404  auto PrintSeparator = [&]() { OS << Separator << "\n"; };
405  auto PrintHeadingRow = [&](const char *T, const char *U, const char *V,
406                             const char *W) {
407    OS << format("%-9s%9s  %9s  %9s\n", T, U, V, W);
408  };
409  auto PrintDataRow = [&](const char *T, unsigned U, unsigned V, unsigned W) {
410    OS << format("%-9s%9d  %9d  %9d\n", T, U, V, W);
411  };
412
413  OS << "\n";
414  PrintSeparator();
415  PrintHeadingRow("Element", "Expected", "Missing", "Added");
416  PrintSeparator();
417  for (LVCompareInfo::reference Entry : Results) {
418    if (Entry.first == LVCompareItem::Total)
419      PrintSeparator();
420    PrintDataRow(std::get<getHeader()>(Entry.second),
421                 std::get<getExpected()>(Entry.second),
422                 std::get<getMissing()>(Entry.second),
423                 std::get<getAdded()>(Entry.second));
424  }
425}
426
427void LVCompare::print(raw_ostream &OS) const { OS << "LVCompare\n"; }
428