llvm/lib/DebugInfo/LogicalView/Core/LVCompare.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-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"; }