xref: /freebsd/contrib/llvm-project/llvm/lib/DebugInfo/LogicalView/Core/LVCompare.cpp (revision 5f757f3ff9144b609b3c433dfd370cc6bdc191ad) 
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 
18 using namespace llvm;
19 using namespace llvm::logicalview;
20 
21 #define DEBUG_TYPE "Compare"
22 
23 namespace {
24 
25 enum class LVCompareItem { Scope, Symbol, Type, Line, Total };
26 enum class LVCompareIndex { Header, Expected, Missing, Added };
27 using LVCompareEntry = std::tuple<const char *, unsigned, unsigned, unsigned>;
28 using LVCompareInfo = std::map<LVCompareItem, LVCompareEntry>;
29 LVCompareInfo 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)}};
35 static LVCompareInfo::iterator IterTotal = Results.end();
36 
37 constexpr unsigned getHeader() {
38   return static_cast<unsigned>(LVCompareIndex::Header);
39 }
40 constexpr unsigned getExpected() {
41   return static_cast<unsigned>(LVCompareIndex::Expected);
42 }
43 constexpr unsigned getMissing() {
44   return static_cast<unsigned>(LVCompareIndex::Missing);
45 }
46 constexpr unsigned getAdded() {
47   return static_cast<unsigned>(LVCompareIndex::Added);
48 }
49 
50 LVCompare *CurrentComparator = nullptr;
51 
52 void 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 
63 LVCompareInfo::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 
80 void 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 
88 void 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 
101 LVCompare &LVCompare::getInstance() {
102   static LVCompare DefaultComparator(outs());
103   return CurrentComparator ? *CurrentComparator : DefaultComparator;
104 }
105 
106 void LVCompare::setInstance(LVCompare *Comparator) {
107   CurrentComparator = Comparator;
108 }
109 
110 LVCompare::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 
118 Error 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 
353 void 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 
361 void 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 
400 void 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 
427 void LVCompare::print(raw_ostream &OS) const { OS << "LVCompare\n"; }
428