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()>(t&: Entry.second) = 0;
56 std::get<getMissing()>(t&: Entry.second) = 0;
57 std::get<getAdded()>(t&: Entry.second) = 0;
58 }
59 IterTotal = Results.find(x: 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(x: 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()>(t&: IterTotal->second);
84 // Update total for specific element kind.
85 ++std::get<getExpected()>(t&: 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()>(t&: IterTotal->second);
92 ++std::get<getMissing()>(t&: Iter->second);
93 } else {
94 ++std::get<getAdded()>(t&: IterTotal->second);
95 ++std::get<getAdded()>(t&: 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(Name: LHS->getName()) << "\n"
130 << "Target: " << formattedName(Name: 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(Target: 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(Pass: 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(Pass: 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(Element: Reference);
207 Reference->setIsInCompare();
208 LVElement *CurrentTarget = nullptr;
209 if (llvm::any_of(Targets, [&](auto Target) -> bool {
210 CurrentTarget = Target;
211 return Reference->equals(Element: 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(args: static_cast<LVScope *>(CurrentTarget),
218 args: 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(Elt: Reference);
225 updateMissingOrAdded(Element: Reference, Pass);
226 // Record missing/added element.
227 addPassEntry(Reader, Element: Reference, Pass);
228 }
229 }
230 }
231 if (Pass == LVComparePass::Added)
232 // Record all the current missing elements for this category.
233 llvm::append_range(C&: Set, R&: Elements);
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(Element: 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 auto It = ScopeLinks.find(x: Parent);
316 if (It != ScopeLinks.end()) {
317 LVScope *InsertionPoint = It->second;
318 LLVM_DEBUG({
319 dbgs() << "Inserted at: "
320 << hexSquareString(InsertionPoint->getOffset()) << "\n";
321 });
322 if (Parent->removeElement(Element)) {
323 // Be sure we have a current compile unit.
324 getReader().setCompileUnit(InsertionPoint->getCompileUnitParent());
325 InsertionPoint->addElement(Element);
326 Element->updateLevel(Parent: InsertionPoint, /*Moved=*/true);
327 }
328 }
329 }
330
331 options().setPrintFormatting();
332
333 // Display the augmented reference scopes tree.
334 if (options().getReportAnyView())
335 if (Error Err = ReferenceReader->doPrint())
336 return Err;
337
338 LLVM_DEBUG({
339 dbgs() << "\nModified Reference Reader";
340 if (Error Err = ReferenceReader->doPrint())
341 return Err;
342 dbgs() << "\nModified Target Reader";
343 if (Error Err = TargetReader->doPrint())
344 return Err;
345 });
346
347 // Display a summary with the elements missing and/or added.
348 printSummary();
349 }
350
351 return Error::success();
352}
353
354void LVCompare::printCurrentStack() {
355 for (const LVScope *Scope : ScopeStack) {
356 Scope->printAttributes(OS);
357 OS << Scope->lineNumberAsString(/*ShowZero=*/true) << " " << Scope->kind()
358 << " " << formattedName(Name: Scope->getName()) << "\n";
359 }
360}
361
362void LVCompare::printItem(LVElement *Element, LVComparePass Pass) {
363 // Record expected, missing, added.
364 updateExpected(Element);
365 updateMissingOrAdded(Element, Pass);
366
367 // Record missing/added element.
368 if (Element->getIsMissing())
369 addPassEntry(Reader, Element, Pass);
370
371 if ((!PrintLines && Element->getIsLine()) ||
372 (!PrintScopes && Element->getIsScope()) ||
373 (!PrintSymbols && Element->getIsSymbol()) ||
374 (!PrintTypes && Element->getIsType()))
375 return;
376
377 if (Element->getIsMissing()) {
378 if (FirstMissing) {
379 OS << "\n";
380 FirstMissing = false;
381 }
382
383 StringRef Kind = Element->kind();
384 StringRef Name =
385 Element->getIsLine() ? Element->getPathname() : Element->getName();
386 StringRef Status = (Pass == LVComparePass::Missing) ? "Missing" : "Added";
387 OS << Status << " " << Kind << " '" << Name << "'";
388 if (Element->getLineNumber() > 0)
389 OS << " at line " << Element->getLineNumber();
390 OS << "\n";
391
392 if (options().getReportList()) {
393 printCurrentStack();
394 Element->printAttributes(OS);
395 OS << Element->lineNumberAsString(/*ShowZero=*/true) << " " << Kind << " "
396 << Name << "\n";
397 }
398 }
399}
400
401void LVCompare::printSummary() const {
402 if (!options().getPrintSummary())
403 return;
404 std::string Separator = std::string(40, '-');
405 auto PrintSeparator = [&]() { OS << Separator << "\n"; };
406 auto PrintHeadingRow = [&](const char *T, const char *U, const char *V,
407 const char *W) {
408 OS << format(Fmt: "%-9s%9s %9s %9s\n", Vals: T, Vals: U, Vals: V, Vals: W);
409 };
410 auto PrintDataRow = [&](const char *T, unsigned U, unsigned V, unsigned W) {
411 OS << format(Fmt: "%-9s%9d %9d %9d\n", Vals: T, Vals: U, Vals: V, Vals: W);
412 };
413
414 OS << "\n";
415 PrintSeparator();
416 PrintHeadingRow("Element", "Expected", "Missing", "Added");
417 PrintSeparator();
418 for (LVCompareInfo::reference Entry : Results) {
419 if (Entry.first == LVCompareItem::Total)
420 PrintSeparator();
421 PrintDataRow(std::get<getHeader()>(t&: Entry.second),
422 std::get<getExpected()>(t&: Entry.second),
423 std::get<getMissing()>(t&: Entry.second),
424 std::get<getAdded()>(t&: Entry.second));
425 }
426}
427
428void LVCompare::print(raw_ostream &OS) const { OS << "LVCompare\n"; }
429