429 lines · cpp
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-exception6//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 else72 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} // namespace100 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 the135 // second time we look for items added to the 'Target'.136 // The comparison test includes the name, lexical level, type, source137 // 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 the148 // 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, we166 // disable the indentation and the added/missing tags ('+'/'-'), as the167 // 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 each190 // element. If a difference is found, the reference element is marked as191 // '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 that203 // 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 augmented216 // 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 llvm::append_range(Set, 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 of251 // the missing elements list. When they are moved, their children are252 // 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, we271 // disable the indentation and the added/missing tags ('+'/'-'), as the272 // 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 parents309 // 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(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(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(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("%-9s%9s %9s %9s\n", T, U, V, W);409 };410 auto PrintDataRow = [&](const char *T, unsigned U, unsigned V, unsigned W) {411 OS << format("%-9s%9d %9d %9d\n", T, U, V, 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()>(Entry.second),422 std::get<getExpected()>(Entry.second),423 std::get<getMissing()>(Entry.second),424 std::get<getAdded()>(Entry.second));425 }426}427 428void LVCompare::print(raw_ostream &OS) const { OS << "LVCompare\n"; }429