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 Set.insert(I: Set.end(), From: Elements.begin(), To: 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(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 if (ScopeLinks.find(x: 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(Parent: 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(Name: 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(Fmt: "%-9s%9s %9s %9s\n", Vals: T, Vals: U, Vals: V, Vals: W);
408 };
409 auto PrintDataRow = [&](const char *T, unsigned U, unsigned V, unsigned W) {
410 OS << format(Fmt: "%-9s%9d %9d %9d\n", Vals: T, Vals: U, Vals: V, Vals: 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()>(t&: Entry.second),
421 std::get<getExpected()>(t&: Entry.second),
422 std::get<getMissing()>(t&: Entry.second),
423 std::get<getAdded()>(t&: Entry.second));
424 }
425}
426
427void LVCompare::print(raw_ostream &OS) const { OS << "LVCompare\n"; }
428