text: //===--- ProtocolConformance.cpp - Swift protocol conformance checking ----===//
  //
  // This source file is part of the Swift.org open source project
  //
  // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
  // Licensed under Apache License v2.0 with Runtime Library Exception
  //
  // See https://swift.org/LICENSE.txt for license information
  // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
  //
  //===----------------------------------------------------------------------===//
  //
  // Checking and caching of Swift protocol conformances.
  //
  //===----------------------------------------------------------------------===//
  
  #include "swift/Basic/LLVM.h"
  #include "swift/Basic/Lazy.h"
  #include "swift/Runtime/Casting.h"
  #include "swift/Runtime/Concurrent.h"
  #include "swift/Runtime/Metadata.h"
  #include "swift/Runtime/Mutex.h"
  #include "swift/Runtime/Unreachable.h"
  #include "ImageInspection.h"
  #include "Private.h"
  
  #include <vector>
  
  using namespace swift;
  
  #if !defined(NDEBUG) && SWIFT_OBJC_INTEROP
  #include <objc/runtime.h>
  
  static const char *class_getName(const ClassMetadata* type) {
    return class_getName(
      reinterpret_cast<Class>(const_cast<ClassMetadata*>(type)));
  }
  
  template<> void ProtocolConformanceRecord::dump() const {
    auto symbolName = [&](const void *addr) -> const char * {
      SymbolInfo info;
      int ok = lookupSymbol(addr, &info);
      if (!ok)
        return "<unknown addr>";
      return info.symbolName;
    };
  
    switch (auto kind = getTypeKind()) {
      case TypeMetadataRecordKind::Universal:
        printf("universal");
        break;
      case TypeMetadataRecordKind::UniqueDirectType:
      case TypeMetadataRecordKind::NonuniqueDirectType:
        printf("%s direct type ",
               kind == TypeMetadataRecordKind::UniqueDirectType
               ? "unique" : "nonunique");
        if (auto &ntd = getDirectType()->getNominalTypeDescriptor()) {
          printf("%s", ntd->Name.get());
        } else {
          printf("<structural type>");
        }
        break;
      case TypeMetadataRecordKind::UniqueDirectClass:
        printf("unique direct class %s",
               class_getName(getDirectClass()));
        break;
      case TypeMetadataRecordKind::UniqueIndirectClass:
        printf("unique indirect class %s",
               class_getName(*getIndirectClass()));
        break;
        
      case TypeMetadataRecordKind::UniqueNominalTypeDescriptor:
        printf("unique nominal type descriptor %s", symbolName(getNominalTypeDescriptor()));
        break;
    }
    
    printf(" => ");
    
    switch (getConformanceKind()) {
      case ProtocolConformanceReferenceKind::WitnessTable:
        printf("witness table %s\n", symbolName(getStaticWitnessTable()));
        break;
      case ProtocolConformanceReferenceKind::WitnessTableAccessor:
        printf("witness table accessor %s\n",
               symbolName((const void *)(uintptr_t)getWitnessTableAccessor()));
        break;
    }
  }
  #endif
  
  /// Take the type reference inside a protocol conformance record and fetch the
  /// canonical metadata pointer for the type it refers to.
  /// Returns nil for universal or generic type references.
  template <>
  const Metadata *ProtocolConformanceRecord::getCanonicalTypeMetadata() const {
    switch (getTypeKind()) {
    case TypeMetadataRecordKind::UniqueDirectType:
      // Already unique.
      return getDirectType();
    case TypeMetadataRecordKind::NonuniqueDirectType: {
      // Ask the runtime for the unique metadata record we've canonized.
      const ForeignTypeMetadata *FMD =
          static_cast<const ForeignTypeMetadata *>(getDirectType());
      return swift_getForeignTypeMetadata(const_cast<ForeignTypeMetadata *>(FMD));
    }
    case TypeMetadataRecordKind::UniqueIndirectClass:
      // The class may be ObjC, in which case we need to instantiate its Swift
      // metadata. The class additionally may be weak-linked, so we have to check
      // for null.
      if (auto *ClassMetadata = *getIndirectClass())
        return swift_getObjCClassMetadata(ClassMetadata);
      return nullptr;
        
    case TypeMetadataRecordKind::UniqueDirectClass:
      // The class may be ObjC, in which case we need to instantiate its Swift
      // metadata.
      if (auto *ClassMetadata = getDirectClass())
        return swift_getObjCClassMetadata(ClassMetadata);
      return nullptr;
        
    case TypeMetadataRecordKind::UniqueNominalTypeDescriptor:
    case TypeMetadataRecordKind::Universal:
      // The record does not apply to a single type.
      return nullptr;
    }
  
    swift_runtime_unreachable("Unhandled TypeMetadataRecordKind in switch.");
  }
  
  template<>
  const WitnessTable *
  ProtocolConformanceRecord::getWitnessTable(const Metadata *type)
  const {
    switch (getConformanceKind()) {
    case ProtocolConformanceReferenceKind::WitnessTable:
      return getStaticWitnessTable();
  
    case ProtocolConformanceReferenceKind::WitnessTableAccessor:
      return getWitnessTableAccessor()(type);
    }
  
    swift_runtime_unreachable(
        "Unhandled ProtocolConformanceReferenceKind in switch.");
  }
  
  namespace {
    struct ConformanceSection {
      const ProtocolConformanceRecord *Begin, *End;
      const ProtocolConformanceRecord *begin() const {
        return Begin;
      }
      const ProtocolConformanceRecord *end() const {
        return End;
      }
    };
  
    struct ConformanceCacheKey {
      /// Either a Metadata* or a NominalTypeDescriptor*.
      const void *Type;
      const ProtocolDescriptor *Proto;
  
      ConformanceCacheKey(const void *type, const ProtocolDescriptor *proto)
        : Type(type), Proto(proto) {}
    };
  
    struct ConformanceCacheEntry {
    private:
      const void *Type; 
      const ProtocolDescriptor *Proto;
      std::atomic<const WitnessTable *> Table;
      std::atomic<uintptr_t> FailureGeneration;
  
    public:
      ConformanceCacheEntry(ConformanceCacheKey key,
                            const WitnessTable *table,
                            uintptr_t failureGeneration)
        : Type(key.Type), Proto(key.Proto), Table(table),
          FailureGeneration(failureGeneration) {
      }
  
      int compareWithKey(const ConformanceCacheKey &key) const {
        if (key.Type != Type) {
          return (uintptr_t(key.Type) < uintptr_t(Type) ? -1 : 1);
        } else if (key.Proto != Proto) {
          return (uintptr_t(key.Proto) < uintptr_t(Proto) ? -1 : 1);
        } else {
          return 0;
        }
      }
  
      template <class... Args>
      static size_t getExtraAllocationSize(Args &&... ignored) {
        return 0;
      }
  
      bool isSuccessful() const {
        return Table.load(std::memory_order_relaxed) != nullptr;
      }
  
      void makeSuccessful(const WitnessTable *table) {
        Table.store(table, std::memory_order_release);
      }
  
      void updateFailureGeneration(uintptr_t failureGeneration) {
        assert(!isSuccessful());
        FailureGeneration.store(failureGeneration, std::memory_order_relaxed);
      }
      
      /// Get the cached witness table, if successful.
      const WitnessTable *getWitnessTable() const {
        assert(isSuccessful());
        return Table.load(std::memory_order_acquire);
      }
      
      /// Get the generation number under which this lookup failed.
      unsigned getFailureGeneration() const {
        assert(!isSuccessful());
        return FailureGeneration.load(std::memory_order_relaxed);
      }
    };
  } // end anonymous namespace
  
  // Conformance Cache.
  struct ConformanceState {
    ConcurrentMap<ConformanceCacheEntry> Cache;
    std::vector<ConformanceSection> SectionsToScan;
    Mutex SectionsToScanLock;
    
    ConformanceState() {
      SectionsToScan.reserve(16);
      initializeProtocolConformanceLookup();
    }
  
    void cacheSuccess(const void *type, const ProtocolDescriptor *proto,
                      const WitnessTable *witness) {
      auto result = Cache.getOrInsert(ConformanceCacheKey(type, proto),
                                      witness, uintptr_t(0));
  
      // If the entry was already present, we may need to update it.
      if (!result.second) {
        result.first->makeSuccessful(witness);
      }
    }
  
    void cacheFailure(const void *type, const ProtocolDescriptor *proto) {
      uintptr_t failureGeneration = SectionsToScan.size();
      auto result = Cache.getOrInsert(ConformanceCacheKey(type, proto),
                                      (const WitnessTable *) nullptr,
                                      failureGeneration);
  
      // If the entry was already present, we may need to update it.
      if (!result.second) {
        result.first->updateFailureGeneration(failureGeneration);
      }
    }
  
    ConformanceCacheEntry *findCached(const void *type,
                                      const ProtocolDescriptor *proto) {
      return Cache.find(ConformanceCacheKey(type, proto));
    }
  };
  
  static Lazy<ConformanceState> Conformances;
  
  static void
  _registerProtocolConformances(ConformanceState &C,
                                const ProtocolConformanceRecord *begin,
                                const ProtocolConformanceRecord *end) {
    ScopedLock guard(C.SectionsToScanLock);
    C.SectionsToScan.push_back(ConformanceSection{begin, end});
  }
  
  void swift::addImageProtocolConformanceBlockCallback(const void *conformances,
                                                     uintptr_t conformancesSize) {
    assert(conformancesSize % sizeof(ProtocolConformanceRecord) == 0
           && "weird-sized conformances section?!");
  
    // If we have a section, enqueue the conformances for lookup.
    auto conformanceBytes = reinterpret_cast<const char *>(conformances);
    auto recordsBegin
      = reinterpret_cast<const ProtocolConformanceRecord*>(conformances);
    auto recordsEnd
      = reinterpret_cast<const ProtocolConformanceRecord*>
                                            (conformanceBytes + conformancesSize);
    
    // Conformance cache should always be sufficiently initialized by this point.
    _registerProtocolConformances(Conformances.unsafeGetAlreadyInitialized(),
                                  recordsBegin, recordsEnd);
  }
  
  void
  swift::swift_registerProtocolConformances(const ProtocolConformanceRecord *begin,
                                            const ProtocolConformanceRecord *end){
    auto &C = Conformances.get();
    _registerProtocolConformances(C, begin, end);
  }
  
  
  struct ConformanceCacheResult {
    // true if witnessTable is an authoritative result as-is.
    // false if more searching is required (for example, because a cached
    // failure was returned in failureEntry but it is out-of-date.
    bool isAuthoritative;
  
    // The matching witness table, or null if no cached conformance was found.
    const WitnessTable *witnessTable;
  
    // If the search fails, this may be the negative cache entry for the
    // queried type itself. This entry may be null or out-of-date.
    ConformanceCacheEntry *failureEntry;
  
    static ConformanceCacheResult
    cachedSuccess(const WitnessTable *table) {
      return ConformanceCacheResult { true, table, nullptr };
    }
  
    static ConformanceCacheResult
    cachedFailure(ConformanceCacheEntry *entry, bool auth) {
      return ConformanceCacheResult { auth, nullptr, entry };
    }
  
    static ConformanceCacheResult
    cacheMiss() {
      return ConformanceCacheResult { false, nullptr, nullptr };
    }
  };
  
  /// Search for a witness table in the ConformanceCache.
  static
  ConformanceCacheResult
  searchInConformanceCache(const Metadata *type,
                           const ProtocolDescriptor *protocol) {
    auto &C = Conformances.get();
    auto origType = type;
    ConformanceCacheEntry *failureEntry = nullptr;
  
  recur:
    {
      // Try the specific type first.
      if (auto *Value = C.findCached(type, protocol)) {
        if (Value->isSuccessful()) {
          // Found a conformance on the type or some superclass. Return it.
          return ConformanceCacheResult::cachedSuccess(Value->getWitnessTable());
        }
  
        // Found a negative cache entry.
  
        bool isAuthoritative;
        if (type == origType) {
          // This negative cache entry is for the original query type.
          // Remember it so it can be returned later.
          failureEntry = Value;
          // An up-to-date entry for the original type is authoritative.
          isAuthoritative = true;
        } else {
          // An up-to-date cached failure for a superclass of the type is not
          // authoritative: there may be a still-undiscovered conformance
          // for the original query type.
          isAuthoritative = false;
        }
  
        // Check if the negative cache entry is up-to-date.
        // FIXME: Using SectionsToScan.size() outside SectionsToScanLock
        // is undefined.
        if (Value->getFailureGeneration() == C.SectionsToScan.size()) {
          // Negative cache entry is up-to-date. Return failure along with
          // the original query type's own cache entry, if we found one.
          // (That entry may be out of date but the caller still has use for it.)
          return ConformanceCacheResult::cachedFailure(failureEntry,
                                                       isAuthoritative);
        }
  
        // Negative cache entry is out-of-date.
        // Continue searching for a better result.
      }
    }
  
    {
      // For generic and resilient types, nondependent conformances
      // are keyed by the nominal type descriptor rather than the
      // metadata, so try that.
      const auto description = type->getNominalTypeDescriptor().get();
  
      // Hash and lookup the type-protocol pair in the cache.
      if (auto *Value = C.findCached(description, protocol)) {
        if (Value->isSuccessful())
          return ConformanceCacheResult::cachedSuccess(Value->getWitnessTable());
  
        // We don't try to cache negative responses for generic
        // patterns.
      }
    }
  
    // If the type is a class, try its superclass.
    if (const ClassMetadata *classType = type->getClassObject()) {
      if (classHasSuperclass(classType)) {
        type = swift_getObjCClassMetadata(classType->SuperClass);
        goto recur;
      }
    }
  
    // We did not find an up-to-date cache entry.
    // If we found an out-of-date entry for the original query type then
    // return it (non-authoritatively). Otherwise return a cache miss.
    if (failureEntry)
      return ConformanceCacheResult::cachedFailure(failureEntry, false);
    else
      return ConformanceCacheResult::cacheMiss();
  }
  
  /// Checks if a given candidate is a type itself, one of its
  /// superclasses or a related generic type.
  ///
  /// This check is supposed to use the same logic that is used
  /// by searchInConformanceCache.
  ///
  /// \param candidate Pointer to a Metadata or a NominalTypeDescriptor.
  ///
  static
  bool isRelatedType(const Metadata *type, const void *candidate,
                     bool candidateIsMetadata) {
  
    while (true) {
      if (type == candidate && candidateIsMetadata)
        return true;
  
      // If the type is resilient or generic, see if there's a witness table
      // keyed off the nominal type descriptor.
      const auto description = type->getNominalTypeDescriptor().get();
      if (description == candidate && !candidateIsMetadata)
        return true;
  
      // If the type is a class, try its superclass.
      if (const ClassMetadata *classType = type->getClassObject()) {
        if (classHasSuperclass(classType)) {
          type = swift_getObjCClassMetadata(classType->SuperClass);
          continue;
        }
      }
  
      break;
    }
  
    return false;
  }
  
  const WitnessTable *
  swift::swift_conformsToProtocol(const Metadata * const type,
                                  const ProtocolDescriptor *protocol) {
    auto &C = Conformances.get();
  
    // See if we have a cached conformance. The ConcurrentMap data structure
    // allows us to insert and search the map concurrently without locking.
    // We do lock the slow path because the SectionsToScan data structure is not
    // concurrent.
    auto FoundConformance = searchInConformanceCache(type, protocol);
    // If the result (positive or negative) is authoritative, return it.
    if (FoundConformance.isAuthoritative)
      return FoundConformance.witnessTable;
  
    auto failureEntry = FoundConformance.failureEntry;
  
    // No up-to-date cache entry found.
    // Acquire the lock so we can scan conformance records.
    ScopedLock guard(C.SectionsToScanLock);
  
    // The world may have changed while we waited for the lock.
    // If we found an out-of-date negative cache entry before
    // acquiring the lock, make sure the entry is still negative and out of date.
    // If we found no entry before acquiring the lock, search the cache again.
    if (failureEntry) {
      if (failureEntry->isSuccessful()) {
        // Somebody else found a conformance.
        return failureEntry->getWitnessTable();
      }
      if (failureEntry->getFailureGeneration() == C.SectionsToScan.size()) {
        // Somebody else brought the negative cache entry up to date.
        return nullptr;
      }
    }
    else {
      FoundConformance = searchInConformanceCache(type, protocol);
      if (FoundConformance.isAuthoritative) {
        // Somebody else found a conformance or cached an up-to-date failure.
        return FoundConformance.witnessTable;
      }
      failureEntry = FoundConformance.failureEntry;
    }
  
    // We are now caught up after acquiring the lock.
    // Prepare to scan conformance records.
  
    // Scan only sections that were not scanned yet.
    // If we found an out-of-date negative cache entry,
    // we need not to re-scan the sections that it covers.
    unsigned startSectionIdx =
      failureEntry ? failureEntry->getFailureGeneration() : 0;
  
    unsigned endSectionIdx = C.SectionsToScan.size();
  
    // If there are no unscanned sections outstanding
    // then we can cache failure and give up now.
    if (startSectionIdx == endSectionIdx) {
      C.cacheFailure(type, protocol);
      return nullptr;
    }
  
    // Really scan conformance records.
  
    for (unsigned sectionIdx = startSectionIdx;
         sectionIdx < endSectionIdx;
         ++sectionIdx) {
      auto &section = C.SectionsToScan[sectionIdx];
      // Eagerly pull records for nondependent witnesses into our cache.
      for (const auto &record : section) {
        // If the record applies to a specific type, cache it.
        if (auto metadata = record.getCanonicalTypeMetadata()) {
          auto P = record.getProtocol();
  
          // Look for an exact match.
          if (protocol != P)
            continue;
  
          if (!isRelatedType(type, metadata, /*candidateIsMetadata=*/true))
            continue;
  
          // Store the type-protocol pair in the cache.
          auto witness = record.getWitnessTable(metadata);
          if (witness) {
            C.cacheSuccess(metadata, P, witness);
          } else {
            C.cacheFailure(metadata, P);
          }
  
        // TODO: "Nondependent witness table" probably deserves its own flag.
        // An accessor function might still be necessary even if the witness table
        // can be shared.
        } else if (record.getTypeKind()
                     == TypeMetadataRecordKind::UniqueNominalTypeDescriptor) {
  
          auto R = record.getNominalTypeDescriptor();
          auto P = record.getProtocol();
  
          // Look for an exact match.
          if (protocol != P)
            continue;
  
          if (!isRelatedType(type, R, /*candidateIsMetadata=*/false))
            continue;
  
          // Store the type-protocol pair in the cache.
          switch (record.getConformanceKind()) {
          case ProtocolConformanceReferenceKind::WitnessTable:
            // If the record provides a nondependent witness table for all
            // instances of a generic type, cache it for the generic pattern.
            C.cacheSuccess(R, P, record.getStaticWitnessTable());
            break;
  
          case ProtocolConformanceReferenceKind::WitnessTableAccessor:
            // If the record provides a dependent witness table accessor,
            // cache the result for the instantiated type metadata.
            C.cacheSuccess(type, P, record.getWitnessTable(type));
            break;
  
          }
        }
      }
    }
  
    // Conformance scan is complete.
    // Search the cache once more, and this time update the cache if necessary.
  
    FoundConformance = searchInConformanceCache(type, protocol);
    if (FoundConformance.isAuthoritative) {
      return FoundConformance.witnessTable;
    } else {
      C.cacheFailure(type, protocol);
      return nullptr;
    }
  }
  
  const Metadata *
  swift::_searchConformancesByMangledTypeName(const llvm::StringRef typeName) {
    auto &C = Conformances.get();
    const Metadata *foundMetadata = nullptr;
  
    ScopedLock guard(C.SectionsToScanLock);
  
    unsigned sectionIdx = 0;
    unsigned endSectionIdx = C.SectionsToScan.size();
  
    for (; sectionIdx < endSectionIdx; ++sectionIdx) {
      auto &section = C.SectionsToScan[sectionIdx];
      for (const auto &record : section) {
        if (auto metadata = record.getCanonicalTypeMetadata())
          foundMetadata = _matchMetadataByMangledTypeName(typeName, metadata, nullptr);
        else if (auto ntd = record.getNominalTypeDescriptor())
          foundMetadata = _matchMetadataByMangledTypeName(typeName, nullptr, ntd);
  
        if (foundMetadata != nullptr)
          break;
      }
      if (foundMetadata != nullptr)
        break;
    }
  
    return foundMetadata;
  }
  