EntityLinker.cpp

Go to the documentation of this file.

//===- EntityLinker.cpp ---------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
 
#include "clang/ScalableStaticAnalysis/Core/EntityLinker/EntityLinker.h"
#include "clang/ScalableStaticAnalysis/Core/EntityLinker/EntitySummaryEncoding.h"
#include "clang/ScalableStaticAnalysis/Core/EntityLinker/MultiArchStaticLibrary.h"
#include "clang/ScalableStaticAnalysis/Core/EntityLinker/StaticLibrary.h"
#include "clang/ScalableStaticAnalysis/Core/EntityLinker/TUSummaryEncoding.h"
#include "clang/ScalableStaticAnalysis/Core/Model/EntityLinkage.h"
#include "clang/ScalableStaticAnalysis/Core/Model/EntityName.h"
#include "clang/ScalableStaticAnalysis/Core/Support/ErrorBuilder.h"
#include "clang/ScalableStaticAnalysis/Core/Support/FormatProviders.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"
#include <cassert>
 
using namespace clang::ssaf;
 
//===----------------------------------------------------------------------===//
// Error Message Constants
//===----------------------------------------------------------------------===//
 
namespace ErrorMessages {
 
static constexpr const char *EntityLinkerFatalErrorPrefix =
    "EntityLinker: Corrupted TUSummary or logic bug";
 
static constexpr const char *EntityAlreadyExistsInLinkageTable =
    "{0} - {1} with {2} already exists in LUSummary";
 
static constexpr const char *MissingLinkageInformation =
    "{0} - {1} missing linkage information in TUSummary";
 
static constexpr const char *DuplicateEntityIdInTUSummary =
    "{0} - Duplicate {1} in EntityResolutionTable";
 
static constexpr const char *EntityNotFoundInResolutionTable =
    "{0} - {1} not found in EntityResolutionTable";
 
static constexpr const char *FailedToInsertEntityIntoOutputSummary =
    "{0} - Failed to insert data for {1} with {2} against {3} to LUSummary";
 
static constexpr const char *DuplicateTUNamespace =
    "failed to link TU summary: duplicate {0}";
 
static constexpr const char *LinkingStaticLibraryMember =
    "failed to link member {0} of static library {1}";
 
static constexpr const char *MismatchedTargetTriple =
    "target triple '{0}' of {1} does not match link unit target triple '{2}'";
 
static constexpr const char *NoMemberForTargetTriple =
    "multi-arch static library {0} has no member for target triple '{1}' "
    "(available: {2})";
 
} // namespace ErrorMessages
 
static NestedBuildNamespace
resolveNamespace(const NestedBuildNamespace &LUNamespace,
                 const NestedBuildNamespace &TUNamespace,
                 const NestedBuildNamespace &EntityNamespace,
                 EntityLinkageType Linkage) {
  switch (Linkage) {
  case EntityLinkageType::None:
  case EntityLinkageType::Internal:
    // Qualify with the TU namespace first (to disambiguate across TUs),
    // then with the LU namespace.
    return EntityNamespace.makeQualified(TUNamespace)
        .makeQualified(LUNamespace);
  case EntityLinkageType::External:
    return NestedBuildNamespace(LUNamespace);
  }
 
  llvm_unreachable("Unhandled EntityLinkageType variant");
}
 
EntityId EntityLinker::resolveEntity(const EntityName &OldName,
                                     const EntityLinkage &Linkage,
                                     const NestedBuildNamespace &TUNamespace) {
  NestedBuildNamespace NewNamespace = resolveNamespace(
      Output.LUNamespace, TUNamespace, OldName.Namespace, Linkage.getLinkage());
 
  EntityName NewName(OldName.USR, OldName.Suffix, NewNamespace);
 
  // NewId construction will always return a fresh id for `None` and `Internal`
  // linkage entities since their namespaces will be different even if their
  // names clash. For `External` linkage entities with identical names this
  // function will return the id assigned at the first insertion.
  EntityId NewId = Output.IdTable.getId(NewName);
 
  auto [_, Inserted] = Output.LinkageTable.try_emplace(NewId, Linkage);
  if (!Inserted) {
    // Insertion failure for `None` and `Internal` linkage is a fatal error
    // because these entities have unique namespaces and should never collide.
    // `External` linkage entities may collide.
    if (Linkage.getLinkage() == EntityLinkageType::None ||
        Linkage.getLinkage() == EntityLinkageType::Internal) {
      ErrorBuilder::fatal(ErrorMessages::EntityAlreadyExistsInLinkageTable,
                          ErrorMessages::EntityLinkerFatalErrorPrefix, NewId,
                          Linkage);
    }
  }
 
  return NewId;
}
 
std::map<EntityId, EntityId>
EntityLinker::resolve(const TUSummaryEncoding &Summary) {
  std::map<EntityId, EntityId> EntityResolutionTable;
 
  Summary.IdTable.forEach([&](const EntityName &OldName, const EntityId OldId) {
    auto Iter = Summary.LinkageTable.find(OldId);
    if (Iter == Summary.LinkageTable.end()) {
      ErrorBuilder::fatal(ErrorMessages::MissingLinkageInformation,
                          ErrorMessages::EntityLinkerFatalErrorPrefix, OldId);
    }
 
    const EntityLinkage &Linkage = Iter->second;
 
    EntityId NewId = resolveEntity(OldName, Linkage,
                                   NestedBuildNamespace(Summary.TUNamespace));
 
    auto [_, Inserted] = EntityResolutionTable.insert({OldId, NewId});
    if (!Inserted) {
      ErrorBuilder::fatal(ErrorMessages::DuplicateEntityIdInTUSummary,
                          ErrorMessages::EntityLinkerFatalErrorPrefix, OldId);
    }
  });
 
  return EntityResolutionTable;
}
 
std::vector<EntitySummaryEncoding *>
EntityLinker::merge(TUSummaryEncoding &Summary,
                    const std::map<EntityId, EntityId> &EntityResolutionTable) {
  std::vector<EntitySummaryEncoding *> PatchTargets;
 
  for (auto &[SN, DataMap] : Summary.Data) {
    auto &OutputSummaryData = Output.Data[SN];
 
    for (auto &[OldId, ES] : DataMap) {
      auto Iter = EntityResolutionTable.find(OldId);
      if (Iter == EntityResolutionTable.end()) {
        ErrorBuilder::fatal(ErrorMessages::EntityNotFoundInResolutionTable,
                            ErrorMessages::EntityLinkerFatalErrorPrefix, OldId);
      }
 
      const auto NewId = Iter->second;
 
      auto [It, Inserted] = OutputSummaryData.try_emplace(NewId, std::move(ES));
 
      if (Inserted) {
        PatchTargets.push_back(It->second.get());
      } else {
        // Safe to retrieve linkage using .at since the resolve step ensures
        // linkage information is always present for every OldId.
        auto Linkage = Summary.LinkageTable.at(OldId);
 
        // Insertion should never fail for `None` and `Internal` linkage
        // entities because these entities will have different namespaces across
        // TUs even if their names match.
        if (Linkage.getLinkage() == EntityLinkageType::None ||
            Linkage.getLinkage() == EntityLinkageType::Internal) {
          ErrorBuilder::fatal(
              ErrorMessages::FailedToInsertEntityIntoOutputSummary,
              ErrorMessages::EntityLinkerFatalErrorPrefix, NewId, Linkage, SN);
        }
 
        // TODO: Insertion is expected to fail for duplicate occurrences of
        // `External` linkage entities. Report these cases in a "debug" mode to
        // help debug potential ODR violations.
      }
    }
  }
 
  return PatchTargets;
}
 
llvm::Error
EntityLinker::patch(const std::vector<EntitySummaryEncoding *> &PatchTargets,
                    const std::map<EntityId, EntityId> &EntityResolutionTable) {
  for (auto *PatchTarget : PatchTargets) {
    assert(PatchTarget && "EntityLinker::patch: Patch target cannot be null");
 
    if (auto Err = PatchTarget->patch(EntityResolutionTable)) {
      return Err;
    }
  }
  return llvm::Error::success();
}
 
llvm::Error
EntityLinker::checkTargetTriple(const llvm::Triple &TargetTriple,
                                const BuildNamespace &InputNamespace) const {
  if (TargetTriple != Output.TargetTriple) {
    return ErrorBuilder::create(std::errc::invalid_argument,
                                ErrorMessages::MismatchedTargetTriple,
                                TargetTriple, InputNamespace,
                                Output.TargetTriple)
        .build();
  }
  return llvm::Error::success();
}
 
llvm::Error EntityLinker::link(std::unique_ptr<TUSummaryEncoding> Summary) {
  if (auto Err =
          checkTargetTriple(Summary->TargetTriple, Summary->TUNamespace)) {
    return Err;
  }
 
  auto [_, Inserted] = ProcessedTUNamespaces.insert(Summary->TUNamespace);
  if (!Inserted) {
    return ErrorBuilder::create(std::errc::invalid_argument,
                                ErrorMessages::DuplicateTUNamespace,
                                Summary->TUNamespace)
        .build();
  }
 
  TUSummaryEncoding &SummaryRef = *Summary;
 
  auto EntityResolutionTable = resolve(SummaryRef);
  auto PatchTargets = merge(SummaryRef, EntityResolutionTable);
  return patch(PatchTargets, EntityResolutionTable);
}
 
llvm::Error EntityLinker::link(std::unique_ptr<StaticLibrary> Library) {
  if (auto Err = checkTargetTriple(Library->TargetTriple, Library->Namespace)) {
    return Err;
  }
 
  while (!Library->Members.empty()) {
    auto Node = Library->Members.extract(Library->Members.begin());
    const BuildNamespace MemberNamespace = Node.value()->TUNamespace;
 
    if (auto Err = link(std::move(Node.value()))) {
      return ErrorBuilder::wrap(std::move(Err))
          .context(ErrorMessages::LinkingStaticLibraryMember, MemberNamespace,
                   Library->Namespace)
          .build();
    }
  }
 
  return llvm::Error::success();
}
 
llvm::Error
EntityLinker::link(std::unique_ptr<MultiArchStaticLibrary> Library) {
  auto MatchingMember = llvm::find_if(
      Library->Members, [this](const std::unique_ptr<StaticLibrary> &Member) {
        return Member->TargetTriple == Output.TargetTriple;
      });
 
  if (MatchingMember == Library->Members.end()) {
    auto TargetTriples = llvm::map_range(
        Library->Members, [](const std::unique_ptr<StaticLibrary> &Member) {
          return llvm::Triple::normalize(Member->TargetTriple.str());
        });
    std::string Available = Library->Members.empty()
                                ? std::string("none")
                                : llvm::join(TargetTriples, ", ");
 
    return ErrorBuilder::create(std::errc::invalid_argument,
                                ErrorMessages::NoMemberForTargetTriple,
                                Library->Namespace, Output.TargetTriple,
                                Available)
        .build();
  }
 
  return link(std::move(Library->Members.extract(MatchingMember).value()));
}