diff --git a/lib/Sema/CMakeLists.txt b/lib/Sema/CMakeLists.txt
index 202218c..1e29351 100644
--- a/lib/Sema/CMakeLists.txt
+++ b/lib/Sema/CMakeLists.txt
@@ -48,6 +48,7 @@
   TypeCheckNameLookup.cpp
   TypeCheckPattern.cpp
   TypeCheckProtocol.cpp
+  TypeCheckProtocolInference.cpp
   TypeCheckREPL.cpp
   TypeCheckRequest.cpp
   TypeCheckStmt.cpp
diff --git a/lib/Sema/DerivedConformances.h b/lib/Sema/DerivedConformances.h
index 2457971..bac3342 100644
--- a/lib/Sema/DerivedConformances.h
+++ b/lib/Sema/DerivedConformances.h
@@ -22,11 +22,14 @@
 
 namespace swift {
   class Decl;
+  class DeclRefExpr;
   class FuncDecl;
   class NominalTypeDecl;
+  class PatternBindingDecl;
   class Type;
   class TypeChecker;
   class ValueDecl;
+  class VarDecl;
   
 namespace DerivedConformance {
 
diff --git a/lib/Sema/TypeCheckProtocol.cpp b/lib/Sema/TypeCheckProtocol.cpp
index df08596..baa636b 100644
--- a/lib/Sema/TypeCheckProtocol.cpp
+++ b/lib/Sema/TypeCheckProtocol.cpp
@@ -14,6 +14,7 @@
 // whether a given type conforms to a given protocol.
 //===----------------------------------------------------------------------===//
 
+#include "TypeCheckProtocol.h"
 #include "ConstraintSystem.h"
 #include "DerivedConformances.h"
 #include "MiscDiagnostics.h"
@@ -39,7 +40,6 @@
 #include "swift/ClangImporter/ClangModule.h"
 #include "swift/Sema/IDETypeChecking.h"
 #include "swift/Serialization/SerializedModuleLoader.h"
-#include "llvm/ADT/ScopedHashTable.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/Compiler.h"
@@ -54,9 +54,6 @@
 using namespace swift;
 
 namespace {
-  struct RequirementMatch;
-  struct RequirementCheck;
-
   /// Describes the environment of a requirement that will be used when
   /// matching witnesses against the requirement and to form the resulting
   /// \c Witness value.
@@ -155,69 +152,6 @@
     }
   };
 
-  class WitnessChecker {
-  protected:
-    TypeChecker &TC;
-    ProtocolDecl *Proto;
-    Type Adoptee;
-    // The conforming context, either a nominal type or extension.
-    DeclContext *DC;
-
-    // An auxiliary lookup table to be used for witnesses remapped via
-    // @_implements(Protocol, DeclName)
-    llvm::DenseMap<DeclName, llvm::TinyPtrVector<ValueDecl *>> ImplementsTable;
-
-    WitnessChecker(TypeChecker &tc, ProtocolDecl *proto,
-                   Type adoptee, DeclContext *dc)
-      : TC(tc), Proto(proto), Adoptee(adoptee), DC(dc) {
-      if (auto N = DC->getAsNominalTypeOrNominalTypeExtensionContext()) {
-        for (auto D : N->getMembers()) {
-          if (auto V = dyn_cast<ValueDecl>(D)) {
-            if (!V->hasName())
-              continue;
-            if (auto A = V->getAttrs().getAttribute<ImplementsAttr>()) {
-              A->getMemberName().addToLookupTable(ImplementsTable, V);
-            }
-          }
-        }
-      }
-    }
-
-    /// Gather the value witnesses for the given requirement.
-    ///
-    /// \param ignoringNames If non-null and there are no value
-    /// witnesses with the correct full name, the results will reflect
-    /// lookup for just the base name and the pointee will be set to
-    /// \c true.
-    SmallVector<ValueDecl *, 4> lookupValueWitnesses(ValueDecl *req,
-                                                     bool *ignoringNames);
-
-    void lookupValueWitnessesViaImplementsAttr(ValueDecl *req,
-                                               SmallVector<ValueDecl *, 4>
-                                               &witnesses);
-
-    bool findBestWitness(ValueDecl *requirement,
-                         bool *ignoringNames,
-                         NormalProtocolConformance *conformance,
-                         SmallVectorImpl<RequirementMatch> &matches,
-                         unsigned &numViable,
-                         unsigned &bestIdx,
-                         bool &doNotDiagnoseMatches);
-
-    bool checkWitnessAccess(AccessScope &requiredAccessScope,
-                            ValueDecl *requirement,
-                            ValueDecl *witness,
-                            bool *isSetter);
-
-    bool checkWitnessAvailability(ValueDecl *requirement,
-                                  ValueDecl *witness,
-                                  AvailabilityContext *requirementInfo);
-
-    RequirementCheck checkWitness(AccessScope requiredAccessScope,
-                                  ValueDecl *requirement,
-                                  const RequirementMatch &match);
-  };
-
   /// \brief The result of matching a particular declaration to a given
   /// requirement.
   enum class MatchKind : unsigned char {
@@ -412,136 +346,136 @@
 
     return false;
   }
+}
 
-  /// \brief Describes a match between a requirement and a witness.
-  struct RequirementMatch {
-    RequirementMatch(ValueDecl *witness, MatchKind kind,
-                     Optional<RequirementEnvironment> &&env = None)
-      : Witness(witness), Kind(kind), WitnessType(), ReqEnv(std::move(env)) {
-      assert(!hasWitnessType() && "Should have witness type");
+/// \brief Describes a match between a requirement and a witness.
+struct swift::RequirementMatch {
+  RequirementMatch(ValueDecl *witness, MatchKind kind,
+                   Optional<RequirementEnvironment> &&env = None)
+    : Witness(witness), Kind(kind), WitnessType(), ReqEnv(std::move(env)) {
+    assert(!hasWitnessType() && "Should have witness type");
+  }
+
+  RequirementMatch(ValueDecl *witness, MatchKind kind,
+                   Type witnessType,
+                   Optional<RequirementEnvironment> &&env = None,
+                   ArrayRef<OptionalAdjustment> optionalAdjustments = {})
+    : Witness(witness), Kind(kind), WitnessType(witnessType),
+      ReqEnv(std::move(env)),
+      OptionalAdjustments(optionalAdjustments.begin(),
+                          optionalAdjustments.end())
+  {
+    assert(hasWitnessType() == !witnessType.isNull() &&
+           "Should (or should not) have witness type");
+  }
+
+  /// \brief The witness that matches the (implied) requirement.
+  ValueDecl *Witness;
+
+  /// \brief The kind of match.
+  MatchKind Kind;
+
+  /// \brief The type of the witness when it is referenced.
+  Type WitnessType;
+
+  /// \brief The requirement environment to use for the witness thunk.
+  Optional<RequirementEnvironment> ReqEnv;
+
+  /// The set of optional adjustments performed on the witness.
+  SmallVector<OptionalAdjustment, 2> OptionalAdjustments;
+
+  /// \brief Determine whether this match is viable.
+  bool isViable() const {
+    switch(Kind) {
+    case MatchKind::ExactMatch:
+    case MatchKind::OptionalityConflict:
+    case MatchKind::RenamedMatch:
+      return true;
+
+    case MatchKind::WitnessInvalid:
+    case MatchKind::KindConflict:
+    case MatchKind::TypeConflict:
+    case MatchKind::StaticNonStaticConflict:
+    case MatchKind::SettableConflict:
+    case MatchKind::PrefixNonPrefixConflict:
+    case MatchKind::PostfixNonPostfixConflict:
+    case MatchKind::MutatingConflict:
+    case MatchKind::NonMutatingConflict:
+    case MatchKind::ConsumingConflict:
+    case MatchKind::RethrowsConflict:
+    case MatchKind::ThrowsConflict:
+    case MatchKind::NonObjC:
+      return false;
     }
 
-    RequirementMatch(ValueDecl *witness, MatchKind kind,
-                     Type witnessType,
-                     Optional<RequirementEnvironment> &&env = None,
-                     ArrayRef<OptionalAdjustment> optionalAdjustments = {})
-      : Witness(witness), Kind(kind), WitnessType(witnessType),
-        ReqEnv(std::move(env)),
-        OptionalAdjustments(optionalAdjustments.begin(),
-                            optionalAdjustments.end())
-    {
-      assert(hasWitnessType() == !witnessType.isNull() &&
-             "Should (or should not) have witness type");
+    llvm_unreachable("Unhandled MatchKind in switch.");
+  }
+
+  /// \brief Determine whether this requirement match has a witness type.
+  bool hasWitnessType() const {
+    switch(Kind) {
+    case MatchKind::ExactMatch:
+    case MatchKind::RenamedMatch:
+    case MatchKind::TypeConflict:
+    case MatchKind::OptionalityConflict:
+      return true;
+
+    case MatchKind::WitnessInvalid:
+    case MatchKind::KindConflict:
+    case MatchKind::StaticNonStaticConflict:
+    case MatchKind::SettableConflict:
+    case MatchKind::PrefixNonPrefixConflict:
+    case MatchKind::PostfixNonPostfixConflict:
+    case MatchKind::MutatingConflict:
+    case MatchKind::NonMutatingConflict:
+    case MatchKind::ConsumingConflict:
+    case MatchKind::RethrowsConflict:
+    case MatchKind::ThrowsConflict:
+    case MatchKind::NonObjC:
+      return false;
     }
 
-    /// \brief The witness that matches the (implied) requirement.
-    ValueDecl *Witness;
-    
-    /// \brief The kind of match.
-    MatchKind Kind;
+    llvm_unreachable("Unhandled MatchKind in switch.");
+  }
 
-    /// \brief The type of the witness when it is referenced.
-    Type WitnessType;
+  SmallVector<Substitution, 2> WitnessSubstitutions;
 
-    /// \brief The requirement environment to use for the witness thunk.
-    Optional<RequirementEnvironment> ReqEnv;
+  swift::Witness getWitness(ASTContext &ctx) const {
+    SmallVector<Substitution, 2> syntheticSubs;
+    auto syntheticEnv = ReqEnv->getSyntheticEnvironment();
+    ReqEnv->getRequirementSignature()->getSubstitutions(
+        ReqEnv->getRequirementToSyntheticMap(),
+        syntheticSubs);
+    return swift::Witness(this->Witness, WitnessSubstitutions,
+                          syntheticEnv, syntheticSubs);
+  }
+};
 
-    /// The set of optional adjustments performed on the witness.
-    SmallVector<OptionalAdjustment, 2> OptionalAdjustments;
+/// \brief Describes the suitability of the chosen witness for
+/// the requirement.
+struct swift::RequirementCheck {
+  CheckKind Kind;
 
-    /// \brief Determine whether this match is viable.
-    bool isViable() const {
-      switch(Kind) {
-      case MatchKind::ExactMatch:
-      case MatchKind::OptionalityConflict:
-      case MatchKind::RenamedMatch:
-        return true;
+  /// The required access scope, if the check failed due to the
+  /// witness being less accessible than the requirement.
+  AccessScope RequiredAccessScope;
 
-      case MatchKind::WitnessInvalid:
-      case MatchKind::KindConflict:
-      case MatchKind::TypeConflict:
-      case MatchKind::StaticNonStaticConflict:
-      case MatchKind::SettableConflict:
-      case MatchKind::PrefixNonPrefixConflict:
-      case MatchKind::PostfixNonPostfixConflict:
-      case MatchKind::MutatingConflict:
-      case MatchKind::NonMutatingConflict:
-      case MatchKind::ConsumingConflict:
-      case MatchKind::RethrowsConflict:
-      case MatchKind::ThrowsConflict:
-      case MatchKind::NonObjC:
-        return false;
-      }
+  /// The required availability, if the check failed due to the
+  /// witness being less available than the requirement.
+  AvailabilityContext RequiredAvailability;
 
-      llvm_unreachable("Unhandled MatchKind in switch.");
-    }
+  RequirementCheck(CheckKind kind)
+    : Kind(kind), RequiredAccessScope(AccessScope::getPublic()),
+      RequiredAvailability(AvailabilityContext::alwaysAvailable()) { }
 
-    /// \brief Determine whether this requirement match has a witness type.
-    bool hasWitnessType() const {
-      switch(Kind) {
-      case MatchKind::ExactMatch:
-      case MatchKind::RenamedMatch:
-      case MatchKind::TypeConflict:
-      case MatchKind::OptionalityConflict:
-        return true;
+  RequirementCheck(CheckKind kind, AccessScope requiredAccessScope)
+    : Kind(kind), RequiredAccessScope(requiredAccessScope),
+      RequiredAvailability(AvailabilityContext::alwaysAvailable()) { }
 
-      case MatchKind::WitnessInvalid:
-      case MatchKind::KindConflict:
-      case MatchKind::StaticNonStaticConflict:
-      case MatchKind::SettableConflict:
-      case MatchKind::PrefixNonPrefixConflict:
-      case MatchKind::PostfixNonPostfixConflict:
-      case MatchKind::MutatingConflict:
-      case MatchKind::NonMutatingConflict:
-      case MatchKind::ConsumingConflict:
-      case MatchKind::RethrowsConflict:
-      case MatchKind::ThrowsConflict:
-      case MatchKind::NonObjC:
-        return false;
-      }
-
-      llvm_unreachable("Unhandled MatchKind in switch.");
-    }
-
-    SmallVector<Substitution, 2> WitnessSubstitutions;
-
-    swift::Witness getWitness(ASTContext &ctx) const {
-      SmallVector<Substitution, 2> syntheticSubs;
-      auto syntheticEnv = ReqEnv->getSyntheticEnvironment();
-      ReqEnv->getRequirementSignature()->getSubstitutions(
-          ReqEnv->getRequirementToSyntheticMap(),
-          syntheticSubs);
-      return swift::Witness(this->Witness, WitnessSubstitutions,
-                            syntheticEnv, syntheticSubs);
-    }
-  };
-
-  /// \brief Describes the suitability of the chosen witness for
-  /// the requirement.
-  struct RequirementCheck {
-    CheckKind Kind;
-
-    /// The required access scope, if the check failed due to the
-    /// witness being less accessible than the requirement.
-    AccessScope RequiredAccessScope;
-
-    /// The required availability, if the check failed due to the
-    /// witness being less available than the requirement.
-    AvailabilityContext RequiredAvailability;
-
-    RequirementCheck(CheckKind kind)
-      : Kind(kind), RequiredAccessScope(AccessScope::getPublic()),
-        RequiredAvailability(AvailabilityContext::alwaysAvailable()) { }
-
-    RequirementCheck(CheckKind kind, AccessScope requiredAccessScope)
-      : Kind(kind), RequiredAccessScope(requiredAccessScope),
-        RequiredAvailability(AvailabilityContext::alwaysAvailable()) { }
-
-    RequirementCheck(CheckKind kind, AvailabilityContext requiredAvailability)
-      : Kind(kind), RequiredAccessScope(AccessScope::getPublic()),
-        RequiredAvailability(requiredAvailability) { }
-  };
-} // end anonymous namespace
+  RequirementCheck(CheckKind kind, AvailabilityContext requiredAvailability)
+    : Kind(kind), RequiredAccessScope(AccessScope::getPublic()),
+      RequiredAvailability(requiredAvailability) { }
+};
 
 /// If the given type is a direct reference to an associated type of
 /// the given protocol, return the referenced associated type.
@@ -1437,6 +1371,22 @@
   return false;
 }
 
+WitnessChecker::WitnessChecker(TypeChecker &tc, ProtocolDecl *proto,
+                               Type adoptee, DeclContext *dc)
+    : TC(tc), Proto(proto), Adoptee(adoptee), DC(dc) {
+  if (auto N = DC->getAsNominalTypeOrNominalTypeExtensionContext()) {
+    for (auto D : N->getMembers()) {
+      if (auto V = dyn_cast<ValueDecl>(D)) {
+        if (!V->hasName())
+          continue;
+        if (auto A = V->getAttrs().getAttribute<ImplementsAttr>()) {
+          A->getMemberName().addToLookupTable(ImplementsTable, V);
+        }
+      }
+    }
+  }
+}
+
 void
 WitnessChecker::lookupValueWitnessesViaImplementsAttr(
     ValueDecl *req, SmallVector<ValueDecl *, 4> &witnesses) {
@@ -1750,554 +1700,250 @@
 
 # pragma mark Witness resolution
 
-namespace {
-  /// The result of attempting to resolve a witness.
-  enum class ResolveWitnessResult {
-    /// The resolution succeeded.
-    Success,
-    /// There was an explicit witness available, but it failed some
-    /// criteria.
-    ExplicitFailed,
-    /// There was no witness available.
-    Missing
-  };
+/// This is a wrapper of multiple instances of ConformanceChecker to allow us
+/// to diagnose and fix code from a more global perspective; for instance,
+/// having this wrapper can help issue a fixit that inserts protocol stubs from
+/// multiple protocols under checking.
+class swift::MultiConformanceChecker {
+  TypeChecker &TC;
+  llvm::SmallVector<ValueDecl*, 16> UnsatisfiedReqs;
+  llvm::SmallVector<ConformanceChecker, 4> AllUsedCheckers;
+  llvm::SmallVector<NormalProtocolConformance*, 4> AllConformances;
+  llvm::SetVector<ValueDecl*> MissingWitnesses;
+  llvm::SmallPtrSet<ValueDecl *, 8> CoveredMembers;
 
-  /// Describes the result of checking a type witness.
-  ///
-  /// This class evaluates true if an error occurred.
-  class CheckTypeWitnessResult {
-    Type Requirement;
+  /// Check one conformance.
+  ProtocolConformance * checkIndividualConformance(
+    NormalProtocolConformance *conformance, bool issueFixit);
 
-  public:
-    CheckTypeWitnessResult() { }
-    CheckTypeWitnessResult(Type reqt) : Requirement(reqt) {}
+  /// Determine whether the given requirement was left unsatisfied.
+  bool isUnsatisfiedReq(NormalProtocolConformance *conformance, ValueDecl *req);
+public:
+  MultiConformanceChecker(TypeChecker &TC): TC(TC){}
 
-    Type getRequirement() const { return Requirement; }
-    bool isConformanceRequirement() const {
-      return Requirement->isExistentialType();
-    }
-
-    explicit operator bool() const { return !Requirement.isNull(); }
-  };
-
-  /// The set of associated types that have been inferred by matching
-  /// the given value witness to its corresponding requirement.
-  struct InferredAssociatedTypesByWitness {
-    /// The witness we matched.
-    ValueDecl *Witness = nullptr;
-
-    /// The associated types inferred from matching this witness.
-    SmallVector<std::pair<AssociatedTypeDecl *, Type>, 4> Inferred;
-
-    /// Inferred associated types that don't meet the associated type
-    /// requirements.
-    SmallVector<std::tuple<AssociatedTypeDecl *, Type, CheckTypeWitnessResult>,
-                2> NonViable;
-
-    void dump(llvm::raw_ostream &out, unsigned indent) const {
-      out << "\n";
-      out.indent(indent) << "(";
-      if (Witness) {
-        Witness->dumpRef(out);
-      }
-
-      for (const auto &inferred : Inferred) {
-        out << "\n";
-        out.indent(indent + 2);
-        out << inferred.first->getName() << " := "
-            << inferred.second.getString();
-      }
-
-      for (const auto &inferred : NonViable) {
-        out << "\n";
-        out.indent(indent + 2);
-        out << std::get<0>(inferred)->getName() << " := "
-            << std::get<1>(inferred).getString();
-        auto type = std::get<2>(inferred).getRequirement();
-        out << " [failed constraint " << type.getString() << "]";
-      }
-
-      out << ")";
-    }
-
-    LLVM_ATTRIBUTE_DEPRECATED(void dump() const,
-                              "only for use in the debugger");
-  };
-
-  void InferredAssociatedTypesByWitness::dump() const {
-    dump(llvm::errs(), 0);
+  /// Add a conformance into the batched checker.
+  void addConformance(NormalProtocolConformance *conformance) {
+    AllConformances.push_back(conformance);
   }
 
-  /// The set of witnesses that were considered when attempting to
-  /// infer associated types.
-  typedef SmallVector<InferredAssociatedTypesByWitness, 2>
-    InferredAssociatedTypesByWitnesses;
-
-  void dumpInferredAssociatedTypesByWitnesses(
-        const InferredAssociatedTypesByWitnesses &inferred,
-        llvm::raw_ostream &out,
-        unsigned indent) {
-    for (const auto &value : inferred) {
-      value.dump(out, indent);
-    }
+  /// Peek the unsatisfied requirements collected during conformance checking.
+  ArrayRef<ValueDecl*> getUnsatisfiedRequirements() {
+    return llvm::makeArrayRef(UnsatisfiedReqs);
   }
 
-  void dumpInferredAssociatedTypesByWitnesses(
-        const InferredAssociatedTypesByWitnesses &inferred) LLVM_ATTRIBUTE_USED;
-
-  void dumpInferredAssociatedTypesByWitnesses(
-                          const InferredAssociatedTypesByWitnesses &inferred) {
-    dumpInferredAssociatedTypesByWitnesses(inferred, llvm::errs(), 0);
+  /// Whether this member is "covered" by one of the conformances.
+  bool isCoveredMember(ValueDecl *member) const {
+    return CoveredMembers.count(member) > 0;
   }
 
-  /// A mapping from requirements to the set of matches with witnesses.
-  typedef SmallVector<std::pair<ValueDecl *,
-                                InferredAssociatedTypesByWitnesses>, 4>
-    InferredAssociatedTypes;
+  /// Check all conformances and emit diagnosis globally.
+  void checkAllConformances();
+};
 
-  void dumpInferredAssociatedTypes(const InferredAssociatedTypes &inferred,
-                                   llvm::raw_ostream &out,
-                                   unsigned indent) {
-    for (const auto &value : inferred) {
-      out << "\n";
-      out.indent(indent) << "(";
-      value.first->dumpRef(out);
-      dumpInferredAssociatedTypesByWitnesses(value.second, out, indent + 2);
-      out << ")";
-    }
-    out << "\n";
-  }
+bool MultiConformanceChecker::
+isUnsatisfiedReq(NormalProtocolConformance *conformance, ValueDecl *req) {
+  if (conformance->isInvalid()) return false;
+  if (isa<TypeDecl>(req)) return false;
 
-  void dumpInferredAssociatedTypes(
-         const InferredAssociatedTypes &inferred) LLVM_ATTRIBUTE_USED;
+  auto witness = conformance->hasWitness(req)
+    ? conformance->getWitness(req, nullptr).getDecl()
+    : nullptr;
 
-  void dumpInferredAssociatedTypes(const InferredAssociatedTypes &inferred) {
-    dumpInferredAssociatedTypes(inferred, llvm::errs(), 0);
-  }
+  // An optional requirement might not have a witness...
+  if (!witness)
+    return req->getAttrs().hasAttribute<OptionalAttr>();
 
-  enum class MissingWitnessDiagnosisKind {
-    FixItOnly,
-    ErrorOnly,
-    ErrorFixIt,
-  };
+  // If the witness lands within the declaration context of the conformance,
+  // record it as a "covered" member.
+  if (witness->getDeclContext() == conformance->getDeclContext())
+    CoveredMembers.insert(witness);
 
-  /// The protocol conformance checker.
-  ///
-  /// This helper class handles most of the details of checking whether a
-  /// given type (\c Adoptee) conforms to a protocol (\c Proto).
-  class ConformanceChecker : public WitnessChecker {
-    friend class MultiConformanceChecker;
-    NormalProtocolConformance *Conformance;
-    SourceLoc Loc;
-    
-    /// Witnesses that are currently being resolved.
-    llvm::SmallPtrSet<ValueDecl *, 4> ResolvingWitnesses;
+  // The witness might come from a protocol or protocol extension.
+  if (witness->getDeclContext()
+        ->getAsProtocolOrProtocolExtensionContext())
+    return true;
 
-    /// Caches the set of associated types that are referenced in each
-    /// requirement.
-    llvm::DenseMap<ValueDecl *, llvm::SmallVector<AssociatedTypeDecl *, 2>>
-      ReferencedAssociatedTypes;
+  return false;
+}
 
-    /// Keep track of missing witnesses, either type or value, for later
-    /// diagnosis emits. This may contain witnesses that are external to the
-    /// protocol under checking.
-    llvm::SetVector<ValueDecl*> &GlobalMissingWitnesses;
+void MultiConformanceChecker::checkAllConformances() {
+  bool anyInvalid = false;
+  for (unsigned I = 0, N = AllConformances.size(); I < N; I ++) {
+    auto *conformance = AllConformances[I];
+    // Check this conformance and emit fixits if this is the last one in the pool.
+    checkIndividualConformance(conformance, I == N - 1);
+    anyInvalid |= conformance->isInvalid();
+    if (anyInvalid)
+      continue;
+    // Check whether there are any unsatisfied requirements.
+    auto proto = conformance->getProtocol();
+    for (auto member : proto->getMembers()) {
+      auto req = dyn_cast<ValueDecl>(member);
+      if (!req || !req->isProtocolRequirement()) continue;
 
-    /// Keep track of the slice in GlobalMissingWitnesses that is local to
-    /// this protocol under checking.
-    unsigned LocalMissingWitnessesStartIndex;
-
-    /// True if we shouldn't complain about problems with this conformance
-    /// right now, i.e. if methods are being called outside
-    /// checkConformance().
-    bool SuppressDiagnostics;
-
-    /// Whether we've already complained about problems with this conformance.
-    bool AlreadyComplained = false;
-
-    /// Whether we checked the requirement signature already.
-    bool CheckedRequirementSignature = false;
-
-    /// Retrieve the associated types that are referenced by the given
-    /// requirement with a base of 'Self'.
-    ArrayRef<AssociatedTypeDecl *> getReferencedAssociatedTypes(ValueDecl *req);
-
-    /// Record a (non-type) witness for the given requirement.
-    void recordWitness(ValueDecl *requirement, const RequirementMatch &match);
-
-    /// Record that the given optional requirement has no witness.
-    void recordOptionalWitness(ValueDecl *requirement);
-
-    /// Record that the given requirement has no valid witness.
-    void recordInvalidWitness(ValueDecl *requirement);
-
-    /// Record a type witness.
-    ///
-    /// \param assocType The associated type whose witness is being recorded.
-    ///
-    /// \param type The witness type.
-    ///
-    /// \param typeDecl The decl the witness type came from; can be null.
-    void recordTypeWitness(AssociatedTypeDecl *assocType, Type type,
-                           TypeDecl *typeDecl, bool performRedeclarationCheck);
-
-    /// Enforce restrictions on non-final classes witnessing requirements
-    /// involving the protocol 'Self' type.
-    void checkNonFinalClassWitness(ValueDecl *requirement,
-                                   ValueDecl *witness);
-
-    /// Resolve a (non-type) witness via name lookup.
-    ResolveWitnessResult resolveWitnessViaLookup(ValueDecl *requirement);
-
-    /// Resolve a (non-type) witness via derivation.
-    ResolveWitnessResult resolveWitnessViaDerivation(ValueDecl *requirement);
-
-    /// Resolve a (non-type) witness via default definition or optional.
-    ResolveWitnessResult resolveWitnessViaDefault(ValueDecl *requirement);
-
-    /// Attempt to resolve a type witness via member name lookup.
-    ResolveWitnessResult resolveTypeWitnessViaLookup(
-                           AssociatedTypeDecl *assocType);
-
-    /// Infer associated type witnesses for the given tentative
-    /// requirement/witness match.
-    InferredAssociatedTypesByWitness inferTypeWitnessesViaValueWitness(
-                                       ValueDecl *req,
-                                       ValueDecl *witness);
-
-    /// Infer associated type witnesses for the given value requirement.
-    InferredAssociatedTypesByWitnesses inferTypeWitnessesViaValueWitnesses(
-                     const llvm::SetVector<AssociatedTypeDecl *> &allUnresolved,
-                     ValueDecl *req);
-
-    /// Infer associated type witnesses for all relevant value requirements.
-    ///
-    /// \param assocTypes The set of associated types we're interested in.
-    InferredAssociatedTypes
-    inferTypeWitnessesViaValueWitnesses(
-      const llvm::SetVector<AssociatedTypeDecl *> &assocTypes);
-
-    /// Diagnose or defer a diagnostic, as appropriate.
-    ///
-    /// \param requirement The requirement with which this diagnostic is
-    /// associated, if any.
-    ///
-    /// \param isError Whether this diagnostic is an error.
-    ///
-    /// \param fn A function to call to emit the actual diagnostic. If
-    /// diagnostics are being deferred,
-    void diagnoseOrDefer(
-           ValueDecl *requirement, bool isError,
-           std::function<void(NormalProtocolConformance *)> fn);
-
-    void
-    addUsedConformances(ProtocolConformance *conformance,
-                        llvm::SmallPtrSetImpl<ProtocolConformance *> &visited);
-    void addUsedConformances(ProtocolConformance *conformance);
-
-    ArrayRef<ValueDecl*> getLocalMissingWitness() {
-      return GlobalMissingWitnesses.getArrayRef().
-        slice(LocalMissingWitnessesStartIndex,
-              GlobalMissingWitnesses.size() - LocalMissingWitnessesStartIndex);
-    }
-
-    void clearGlobalMissingWitnesses() {
-      GlobalMissingWitnesses.clear();
-      LocalMissingWitnessesStartIndex = GlobalMissingWitnesses.size();
-    }
-
-  public:
-    /// Call this to diagnose currently known missing witnesses.
-    void diagnoseMissingWitnesses(MissingWitnessDiagnosisKind Kind);
-    /// Emit any diagnostics that have been delayed.
-    void emitDelayedDiags();
-
-    ConformanceChecker(TypeChecker &tc, NormalProtocolConformance *conformance,
-                       llvm::SetVector<ValueDecl*> &GlobalMissingWitnesses,
-                       bool suppressDiagnostics = true)
-        : WitnessChecker(tc, conformance->getProtocol(),
-                         conformance->getType(),
-                         conformance->getDeclContext()),
-          Conformance(conformance), Loc(conformance->getLoc()),
-          GlobalMissingWitnesses(GlobalMissingWitnesses),
-          LocalMissingWitnessesStartIndex(GlobalMissingWitnesses.size()),
-          SuppressDiagnostics(suppressDiagnostics) {
-      // The protocol may have only been validatedDeclForNameLookup'd until
-      // here, so fill in any information that's missing.
-      tc.validateDecl(conformance->getProtocol());
-    }
-
-    /// Resolve all of the type witnesses.
-    void resolveTypeWitnesses();
-
-    /// Resolve the witness for the given non-type requirement as
-    /// directly as possible, only resolving other witnesses if
-    /// needed, e.g., to determine type witnesses used within the
-    /// requirement.
-    ///
-    /// This entry point is designed to be used when the witness for a
-    /// particular requirement and adoptee is required, before the
-    /// conformance has been completed checked.
-    void resolveSingleWitness(ValueDecl *requirement);
-
-    /// Resolve the type witness for the given associated type as
-    /// directly as possible.
-    void resolveSingleTypeWitness(AssociatedTypeDecl *assocType);
-
-    /// Check all of the protocols requirements are actually satisfied by a
-    /// the chosen type witnesses.
-    void ensureRequirementsAreSatisfied();
-
-    /// Check the entire protocol conformance, ensuring that all
-    /// witnesses are resolved and emitting any diagnostics.
-    void checkConformance(MissingWitnessDiagnosisKind Kind);
-  };
-
-  /// This is a wrapper of multiple instances of ConformanceChecker to allow us
-  /// to diagnose and fix code from a more global perspective; for instance,
-  /// having this wrapper can help issue a fixit that inserts protocol stubs from
-  /// multiple protocols under checking.
-  class MultiConformanceChecker {
-    TypeChecker &TC;
-    llvm::SmallVector<ValueDecl*, 16> UnsatisfiedReqs;
-    llvm::SmallVector<ConformanceChecker, 4> AllUsedCheckers;
-    llvm::SmallVector<NormalProtocolConformance*, 4> AllConformances;
-    llvm::SetVector<ValueDecl*> MissingWitnesses;
-    llvm::SmallPtrSet<ValueDecl *, 8> CoveredMembers;
-
-    /// Check one conformance.
-    ProtocolConformance * checkIndividualConformance(
-      NormalProtocolConformance *conformance, bool issueFixit);
-
-    /// Determine whether the given requirement was left unsatisfied.
-    bool isUnsatisfiedReq(NormalProtocolConformance *conformance, ValueDecl *req);
-  public:
-    MultiConformanceChecker(TypeChecker &TC): TC(TC){}
-
-    /// Add a conformance into the batched checker.
-    void addConformance(NormalProtocolConformance *conformance) {
-      AllConformances.push_back(conformance);
-    }
-
-    /// Peek the unsatisfied requirements collected during conformance checking.
-    ArrayRef<ValueDecl*> getUnsatisfiedRequirements() {
-      return llvm::makeArrayRef(UnsatisfiedReqs);
-    }
-
-    /// Whether this member is "covered" by one of the conformances.
-    bool isCoveredMember(ValueDecl *member) const {
-      return CoveredMembers.count(member) > 0;
-    }
-
-    /// Check all conformances and emit diagnosis globally.
-    void checkAllConformances();
-  };
-
-  bool MultiConformanceChecker::
-  isUnsatisfiedReq(NormalProtocolConformance *conformance, ValueDecl *req) {
-    if (conformance->isInvalid()) return false;
-    if (isa<TypeDecl>(req)) return false;
-
-    auto witness = conformance->hasWitness(req)
-      ? conformance->getWitness(req, nullptr).getDecl()
-      : nullptr;
-
-    // An optional requirement might not have a witness...
-    if (!witness)
-      return req->getAttrs().hasAttribute<OptionalAttr>();
-
-    // If the witness lands within the declaration context of the conformance,
-    // record it as a "covered" member.
-    if (witness->getDeclContext() == conformance->getDeclContext())
-      CoveredMembers.insert(witness);
-
-    // The witness might come from a protocol or protocol extension.
-    if (witness->getDeclContext()
-          ->getAsProtocolOrProtocolExtensionContext())
-      return true;
-
-    return false;
-  }
-
-  void MultiConformanceChecker::checkAllConformances() {
-    bool anyInvalid = false;
-    for (unsigned I = 0, N = AllConformances.size(); I < N; I ++) {
-      auto *conformance = AllConformances[I];
-      // Check this conformance and emit fixits if this is the last one in the pool.
-      checkIndividualConformance(conformance, I == N - 1);
-      anyInvalid |= conformance->isInvalid();
-      if (anyInvalid)
+      // If the requirement is unsatisfied, we might want to warn
+      // about near misses; record it.
+      if (isUnsatisfiedReq(conformance, req)) {
+        UnsatisfiedReqs.push_back(req);
         continue;
-      // Check whether there are any unsatisfied requirements.
-      auto proto = conformance->getProtocol();
-      for (auto member : proto->getMembers()) {
-        auto req = dyn_cast<ValueDecl>(member);
-        if (!req || !req->isProtocolRequirement()) continue;
-
-        // If the requirement is unsatisfied, we might want to warn
-        // about near misses; record it.
-        if (isUnsatisfiedReq(conformance, req)) {
-          UnsatisfiedReqs.push_back(req);
-          continue;
-        }
-      }
-    }
-    // If all missing witnesses are issued with fixits, we are done.
-    if (MissingWitnesses.empty())
-      return;
-
-    // Otherwise, backtrack to the last checker that has missing witnesses
-    // and diagnose missing witnesses from there.
-    for (auto It = AllUsedCheckers.rbegin(); It != AllUsedCheckers.rend();
-         It ++) {
-      if (!It->getLocalMissingWitness().empty()) {
-        It->diagnoseMissingWitnesses(MissingWitnessDiagnosisKind::FixItOnly);
       }
     }
   }
+  // If all missing witnesses are issued with fixits, we are done.
+  if (MissingWitnesses.empty())
+    return;
 
-  /// \brief Determine whether the type \c T conforms to the protocol \c Proto,
-  /// recording the complete witness table if it does.
-  ProtocolConformance *MultiConformanceChecker::
-  checkIndividualConformance(NormalProtocolConformance *conformance,
-                             bool issueFixit) {
-    std::vector<ValueDecl*> revivedMissingWitnesses;
-    switch (conformance->getState()) {
-      case ProtocolConformanceState::Incomplete:
-        if (conformance->isInvalid()) {
-          // Revive registered missing witnesses to handle it below.
-          revivedMissingWitnesses = TC.Context.
-            takeDelayedMissingWitnesses(conformance);
-
-          // If we have no missing witnesses for this invalid conformance, the
-          // conformance is invalid for other reasons, so emit diagnosis now.
-          if (revivedMissingWitnesses.empty()) {
-            // Emit any delayed diagnostics.
-            ConformanceChecker(TC, conformance, MissingWitnesses, false).
-              emitDelayedDiags();
-          }
-        }
-
-        // Check the rest of the conformance below.
-        break;
-
-      case ProtocolConformanceState::CheckingTypeWitnesses:
-      case ProtocolConformanceState::Checking:
-      case ProtocolConformanceState::Complete:
-        // Nothing to do.
-        return conformance;
+  // Otherwise, backtrack to the last checker that has missing witnesses
+  // and diagnose missing witnesses from there.
+  for (auto It = AllUsedCheckers.rbegin(); It != AllUsedCheckers.rend();
+       It ++) {
+    if (!It->getLocalMissingWitness().empty()) {
+      It->diagnoseMissingWitnesses(MissingWitnessDiagnosisKind::FixItOnly);
     }
+  }
+}
 
-    // Dig out some of the fields from the conformance.
-    Type T = conformance->getType();
-    auto canT = T->getCanonicalType();
-    DeclContext *DC = conformance->getDeclContext();
-    auto Proto = conformance->getProtocol();
-    SourceLoc ComplainLoc = conformance->getLoc();
+/// \brief Determine whether the type \c T conforms to the protocol \c Proto,
+/// recording the complete witness table if it does.
+ProtocolConformance *MultiConformanceChecker::
+checkIndividualConformance(NormalProtocolConformance *conformance,
+                           bool issueFixit) {
+  std::vector<ValueDecl*> revivedMissingWitnesses;
+  switch (conformance->getState()) {
+    case ProtocolConformanceState::Incomplete:
+      if (conformance->isInvalid()) {
+        // Revive registered missing witnesses to handle it below.
+        revivedMissingWitnesses = TC.Context.
+          takeDelayedMissingWitnesses(conformance);
 
-    // Note that we are checking this conformance now.
-    conformance->setState(ProtocolConformanceState::Checking);
-    SWIFT_DEFER { conformance->setState(ProtocolConformanceState::Complete); };
-
-    TC.validateDecl(Proto);
-
-    // If the protocol itself is invalid, there's nothing we can do.
-    if (Proto->isInvalid()) {
-      conformance->setInvalid();
-      return conformance;
-    }
-
-    // If the protocol requires a class, non-classes are a non-starter.
-    if (Proto->requiresClass() && !canT->getClassOrBoundGenericClass()) {
-      TC.diagnose(ComplainLoc, diag::non_class_cannot_conform_to_class_protocol,
-                  T, Proto->getDeclaredType());
-      conformance->setInvalid();
-      return conformance;
-    }
-
-    // Foreign classes cannot conform to objc protocols.
-    if (Proto->isObjC()) {
-      if (auto clas = canT->getClassOrBoundGenericClass()) {
-        Optional<decltype(diag::cf_class_cannot_conform_to_objc_protocol)>
-        diagKind;
-        switch (clas->getForeignClassKind()) {
-          case ClassDecl::ForeignKind::Normal:
-            break;
-          case ClassDecl::ForeignKind::CFType:
-            diagKind = diag::cf_class_cannot_conform_to_objc_protocol;
-            break;
-          case ClassDecl::ForeignKind::RuntimeOnly:
-            diagKind = diag::objc_runtime_visible_cannot_conform_to_objc_protocol;
-            break;
-        }
-        if (diagKind) {
-          TC.diagnose(ComplainLoc, diagKind.getValue(),
-                      T, Proto->getDeclaredType());
-          conformance->setInvalid();
-          return conformance;
+        // If we have no missing witnesses for this invalid conformance, the
+        // conformance is invalid for other reasons, so emit diagnosis now.
+        if (revivedMissingWitnesses.empty()) {
+          // Emit any delayed diagnostics.
+          ConformanceChecker(TC, conformance, MissingWitnesses, false).
+            emitDelayedDiags();
         }
       }
-    }
 
-    // If the protocol contains missing requirements, it can't be conformed to
-    // at all.
-    if (Proto->hasMissingRequirements()) {
-      bool hasDiagnosed = false;
-      auto *protoFile = Proto->getModuleScopeContext();
-      if (auto *serialized = dyn_cast<SerializedASTFile>(protoFile)) {
-        if (serialized->getLanguageVersionBuiltWith() !=
-            TC.getLangOpts().EffectiveLanguageVersion) {
-          TC.diagnose(ComplainLoc,
-                      diag::protocol_has_missing_requirements_versioned,
-                      T, Proto->getDeclaredType(),
-                      serialized->getLanguageVersionBuiltWith(),
-                      TC.getLangOpts().EffectiveLanguageVersion);
-          hasDiagnosed = true;
-        }
+      // Check the rest of the conformance below.
+      break;
+
+    case ProtocolConformanceState::CheckingTypeWitnesses:
+    case ProtocolConformanceState::Checking:
+    case ProtocolConformanceState::Complete:
+      // Nothing to do.
+      return conformance;
+  }
+
+  // Dig out some of the fields from the conformance.
+  Type T = conformance->getType();
+  auto canT = T->getCanonicalType();
+  DeclContext *DC = conformance->getDeclContext();
+  auto Proto = conformance->getProtocol();
+  SourceLoc ComplainLoc = conformance->getLoc();
+
+  // Note that we are checking this conformance now.
+  conformance->setState(ProtocolConformanceState::Checking);
+  SWIFT_DEFER { conformance->setState(ProtocolConformanceState::Complete); };
+
+  TC.validateDecl(Proto);
+
+  // If the protocol itself is invalid, there's nothing we can do.
+  if (Proto->isInvalid()) {
+    conformance->setInvalid();
+    return conformance;
+  }
+
+  // If the protocol requires a class, non-classes are a non-starter.
+  if (Proto->requiresClass() && !canT->getClassOrBoundGenericClass()) {
+    TC.diagnose(ComplainLoc, diag::non_class_cannot_conform_to_class_protocol,
+                T, Proto->getDeclaredType());
+    conformance->setInvalid();
+    return conformance;
+  }
+
+  // Foreign classes cannot conform to objc protocols.
+  if (Proto->isObjC()) {
+    if (auto clas = canT->getClassOrBoundGenericClass()) {
+      Optional<decltype(diag::cf_class_cannot_conform_to_objc_protocol)>
+      diagKind;
+      switch (clas->getForeignClassKind()) {
+        case ClassDecl::ForeignKind::Normal:
+          break;
+        case ClassDecl::ForeignKind::CFType:
+          diagKind = diag::cf_class_cannot_conform_to_objc_protocol;
+          break;
+        case ClassDecl::ForeignKind::RuntimeOnly:
+          diagKind = diag::objc_runtime_visible_cannot_conform_to_objc_protocol;
+          break;
       }
-      if (!hasDiagnosed) {
-        TC.diagnose(ComplainLoc, diag::protocol_has_missing_requirements,
+      if (diagKind) {
+        TC.diagnose(ComplainLoc, diagKind.getValue(),
                     T, Proto->getDeclaredType());
-      }
-      conformance->setInvalid();
-      return conformance;
-    }
-
-    // Check that T conforms to all inherited protocols.
-    for (auto InheritedProto : Proto->getInheritedProtocols()) {
-      auto InheritedConformance =
-      TC.conformsToProtocol(
-                          T, InheritedProto, DC,
-                          (ConformanceCheckFlags::Used|
-                           ConformanceCheckFlags::SkipConditionalRequirements),
-                          ComplainLoc);
-      if (!InheritedConformance || !InheritedConformance->isConcrete()) {
-        // Recursive call already diagnosed this problem, but tack on a note
-        // to establish the relationship.
-        if (ComplainLoc.isValid()) {
-          TC.diagnose(Proto,
-                      diag::inherited_protocol_does_not_conform, T,
-                      InheritedProto->getDeclaredType());
-        }
-
         conformance->setInvalid();
         return conformance;
       }
     }
+  }
 
-    if (conformance->isComplete())
-      return conformance;
-
-    // The conformance checker we're using.
-    AllUsedCheckers.emplace_back(TC, conformance, MissingWitnesses);
-    MissingWitnesses.insert(revivedMissingWitnesses.begin(),
-                            revivedMissingWitnesses.end());
-    AllUsedCheckers.back().checkConformance(issueFixit ?
-                                      MissingWitnessDiagnosisKind::ErrorFixIt :
-                                      MissingWitnessDiagnosisKind::ErrorOnly);
+  // If the protocol contains missing requirements, it can't be conformed to
+  // at all.
+  if (Proto->hasMissingRequirements()) {
+    bool hasDiagnosed = false;
+    auto *protoFile = Proto->getModuleScopeContext();
+    if (auto *serialized = dyn_cast<SerializedASTFile>(protoFile)) {
+      if (serialized->getLanguageVersionBuiltWith() !=
+          TC.getLangOpts().EffectiveLanguageVersion) {
+        TC.diagnose(ComplainLoc,
+                    diag::protocol_has_missing_requirements_versioned,
+                    T, Proto->getDeclaredType(),
+                    serialized->getLanguageVersionBuiltWith(),
+                    TC.getLangOpts().EffectiveLanguageVersion);
+        hasDiagnosed = true;
+      }
+    }
+    if (!hasDiagnosed) {
+      TC.diagnose(ComplainLoc, diag::protocol_has_missing_requirements,
+                  T, Proto->getDeclaredType());
+    }
+    conformance->setInvalid();
     return conformance;
   }
-} // end anonymous namespace
+
+  // Check that T conforms to all inherited protocols.
+  for (auto InheritedProto : Proto->getInheritedProtocols()) {
+    auto InheritedConformance =
+    TC.conformsToProtocol(
+                        T, InheritedProto, DC,
+                        (ConformanceCheckFlags::Used|
+                         ConformanceCheckFlags::SkipConditionalRequirements),
+                        ComplainLoc);
+    if (!InheritedConformance || !InheritedConformance->isConcrete()) {
+      // Recursive call already diagnosed this problem, but tack on a note
+      // to establish the relationship.
+      if (ComplainLoc.isValid()) {
+        TC.diagnose(Proto,
+                    diag::inherited_protocol_does_not_conform, T,
+                    InheritedProto->getDeclaredType());
+      }
+
+      conformance->setInvalid();
+      return conformance;
+    }
+  }
+
+  if (conformance->isComplete())
+    return conformance;
+
+  // The conformance checker we're using.
+  AllUsedCheckers.emplace_back(TC, conformance, MissingWitnesses);
+  MissingWitnesses.insert(revivedMissingWitnesses.begin(),
+                          revivedMissingWitnesses.end());
+  AllUsedCheckers.back().checkConformance(issueFixit ?
+                                    MissingWitnessDiagnosisKind::ErrorFixIt :
+                                    MissingWitnessDiagnosisKind::ErrorOnly);
+  return conformance;
+}
 
 /// \brief Add the next associated type deduction to the string representation
 /// of the deductions, used in diagnostics.
@@ -2638,6 +2284,22 @@
   }
 }
 
+ConformanceChecker::ConformanceChecker(
+                   TypeChecker &tc, NormalProtocolConformance *conformance,
+                   llvm::SetVector<ValueDecl*> &GlobalMissingWitnesses,
+                   bool suppressDiagnostics)
+    : WitnessChecker(tc, conformance->getProtocol(),
+                     conformance->getType(),
+                     conformance->getDeclContext()),
+      Conformance(conformance), Loc(conformance->getLoc()),
+      GlobalMissingWitnesses(GlobalMissingWitnesses),
+      LocalMissingWitnessesStartIndex(GlobalMissingWitnesses.size()),
+      SuppressDiagnostics(suppressDiagnostics) {
+  // The protocol may have only been validatedDeclForNameLookup'd until
+  // here, so fill in any information that's missing.
+  tc.validateDecl(conformance->getProtocol());
+}
+
 ArrayRef<AssociatedTypeDecl *>
 ConformanceChecker::getReferencedAssociatedTypes(ValueDecl *req) {
   // Check whether we've already cached this information.
@@ -3539,11 +3201,7 @@
 
 # pragma mark Type witness resolution
 
-/// Check whether the given type witness can be used for the given
-/// associated type.
-///
-/// \returns an empty result on success, or a description of the error.
-static CheckTypeWitnessResult checkTypeWitness(TypeChecker &tc, DeclContext *dc,
+CheckTypeWitnessResult swift::checkTypeWitness(TypeChecker &tc, DeclContext *dc,
                                                ProtocolDecl *proto,
                                                AssociatedTypeDecl *assocType, 
                                                Type type) {
@@ -4190,1173 +3848,6 @@
   return inferred;
 }
 
-namespace {
-  /// A potential solution to the set of inferred type witnesses.
-  struct InferredTypeWitnessesSolution {
-    /// The set of type witnesses inferred by this solution, along
-    /// with the index into the value witnesses where the type was
-    /// inferred.
-    llvm::SmallDenseMap<AssociatedTypeDecl *, std::pair<Type, unsigned>, 4>
-      TypeWitnesses;
-
-    /// The value witnesses selected by this step of the solution.
-    SmallVector<std::pair<ValueDecl *, ValueDecl *>, 4> ValueWitnesses;
-
-    /// The number of value witnesses that occur in protocol
-    /// extensions.
-    unsigned NumValueWitnessesInProtocolExtensions;
-    
-#ifndef NDEBUG
-    LLVM_ATTRIBUTE_USED
-#endif
-    void dump() {
-      llvm::errs() << "Type Witnesses:\n";
-      for (auto &typeWitness : TypeWitnesses) {
-        llvm::errs() << "  " << typeWitness.first->getName() << " := ";
-        typeWitness.second.first->print(llvm::errs());
-        llvm::errs() << " value " << typeWitness.second.second << '\n';
-      }
-      llvm::errs() << "Value Witnesses:\n";
-      for (unsigned i : indices(ValueWitnesses)) {
-        auto &valueWitness = ValueWitnesses[i];
-        llvm::errs() << i << ":  " << (Decl*)valueWitness.first
-                     << ' ' << valueWitness.first->getBaseName() << '\n';
-        valueWitness.first->getDeclContext()->dumpContext();
-        llvm::errs() << "    for " << (Decl*)valueWitness.second
-                     << ' ' << valueWitness.second->getBaseName() << '\n';
-        valueWitness.second->getDeclContext()->dumpContext();
-      }
-    }
-  };
-
-  /// A failed type witness binding.
-  struct FailedTypeWitness {
-    /// The value requirement that triggered inference.
-    ValueDecl *Requirement;
-
-    /// The corresponding value witness from which the type witness
-    /// was inferred.
-    ValueDecl *Witness;
-
-    /// The actual type witness that was inferred.
-    Type TypeWitness;
-
-    /// The failed type witness result.
-    CheckTypeWitnessResult Result;
-  };
-
-  /// A conflict between two inferred type witnesses for the same
-  /// associated type.
-  struct TypeWitnessConflict {
-    /// The associated type.
-    AssociatedTypeDecl *AssocType;
-
-    /// The first type.
-    Type FirstType;
-
-    /// The requirement to which the first witness was matched.
-    ValueDecl *FirstRequirement;
-
-    /// The witness from which the first type witness was inferred.
-    ValueDecl *FirstWitness;
-
-    /// The second type.
-    Type SecondType;
-
-    /// The requirement to which the second witness was matched.
-    ValueDecl *SecondRequirement;
-
-    /// The witness from which the second type witness was inferred.
-    ValueDecl *SecondWitness;
-  };
-} // end anonymous namespace
-
-static Comparison
-compareDeclsForInference(TypeChecker &TC, DeclContext *DC,
-                         ValueDecl *decl1, ValueDecl *decl2) {
-  // TC.compareDeclarations assumes that it's comparing two decls that
-  // apply equally well to a call site. We haven't yet inferred the
-  // associated types for a type, so the ranking algorithm used by
-  // compareDeclarations to score protocol extensions is inappropriate,
-  // since we may have potential witnesses from extensions with mutually
-  // exclusive associated type constraints, and compareDeclarations will
-  // consider these unordered since neither extension's generic signature
-  // is a superset of the other.
-  
-  // If the witnesses come from the same decl context, score normally.
-  auto dc1 = decl1->getDeclContext();
-  auto dc2 = decl2->getDeclContext();
-  
-  if (dc1 == dc2)
-    return TC.compareDeclarations(DC, decl1, decl2);
-  
-  auto isProtocolExt1 =
-    (bool)dc1->getAsProtocolExtensionContext();
-  auto isProtocolExt2 =
-    (bool)dc2->getAsProtocolExtensionContext();
-  
-  // If one witness comes from a protocol extension, favor the one
-  // from a concrete context.
-  if (isProtocolExt1 != isProtocolExt2) {
-    return isProtocolExt1 ? Comparison::Worse : Comparison::Better;
-  }
-  
-  // If both witnesses came from concrete contexts, score normally.
-  // Associated type inference shouldn't impact the result.
-  // FIXME: It could, if someone constrained to ConcreteType.AssocType...
-  if (!isProtocolExt1)
-    return TC.compareDeclarations(DC, decl1, decl2);
-  
-  // Compare protocol extensions by which protocols they require Self to
-  // conform to. If one extension requires a superset of the other's
-  // constraints, it wins.
-  auto sig1 = dc1->getGenericSignatureOfContext();
-  auto sig2 = dc2->getGenericSignatureOfContext();
-
-  // FIXME: Extensions sometimes have null generic signatures while
-  // checking the standard library...
-  if (!sig1 || !sig2)
-    return TC.compareDeclarations(DC, decl1, decl2);
-  
-  auto selfParam = GenericTypeParamType::get(0, 0, TC.Context);
-  
-  // Collect the protocols required by extension 1.
-  Type class1;
-  SmallPtrSet<ProtocolDecl*, 4> protos1;
-  
-  std::function<void (ProtocolDecl*)> insertProtocol;
-  insertProtocol = [&](ProtocolDecl *p) {
-    if (!protos1.insert(p).second)
-      return;
-
-    for (auto parent : p->getInheritedProtocols())
-      insertProtocol(parent);
-  };
-  
-  for (auto &reqt : sig1->getRequirements()) {
-    if (!reqt.getFirstType()->isEqual(selfParam))
-      continue;
-    switch (reqt.getKind()) {
-    case RequirementKind::Conformance: {
-      auto *proto = reqt.getSecondType()->castTo<ProtocolType>()->getDecl();
-      insertProtocol(proto);
-      break;
-    }
-    case RequirementKind::Superclass:
-      class1 = reqt.getSecondType();
-      break;
-    
-    case RequirementKind::SameType:
-    case RequirementKind::Layout:
-      break;
-    }
-  }
-
-  // Compare with the protocols required by extension 2.
-  Type class2;
-  SmallPtrSet<ProtocolDecl*, 4> protos2;
-  bool protos2AreSubsetOf1 = true;
-  std::function<void (ProtocolDecl*)> removeProtocol;
-  removeProtocol = [&](ProtocolDecl *p) {
-    if (!protos2.insert(p).second)
-      return;
-
-    protos2AreSubsetOf1 &= protos1.erase(p);
-    for (auto parent : p->getInheritedProtocols())
-      removeProtocol(parent);
-  };
-
-  for (auto &reqt : sig2->getRequirements()) {
-    if (!reqt.getFirstType()->isEqual(selfParam))
-      continue;
-    switch (reqt.getKind()) {
-    case RequirementKind::Conformance: {
-      auto *proto = reqt.getSecondType()->castTo<ProtocolType>()->getDecl();
-      removeProtocol(proto);
-      break;
-    }
-    case RequirementKind::Superclass:
-      class2 = reqt.getSecondType();
-      break;
-    
-    case RequirementKind::SameType:
-    case RequirementKind::Layout:
-      break;
-    }
-  }
-  
-  auto isClassConstraintAsStrict = [&](Type t1, Type t2) -> bool {
-    if (!t1)
-      return !t2;
-    
-    if (!t2)
-      return true;
-    
-    return TC.isSubclassOf(t1, t2, DC);
-  };
-  
-  bool protos1AreSubsetOf2 = protos1.empty();
-  // If the second extension requires strictly more protocols than the
-  // first, it's better.
-  if (protos1AreSubsetOf2 > protos2AreSubsetOf1
-      && isClassConstraintAsStrict(class2, class1)) {
-    return Comparison::Worse;
-  // If the first extension requires strictly more protocols than the
-  // second, it's better.
-  } else if (protos2AreSubsetOf1 > protos1AreSubsetOf2
-             && isClassConstraintAsStrict(class1, class2)) {
-    return Comparison::Better;
-  }
-  
-  // If they require the same set of protocols, or non-overlapping
-  // sets, judge them normally.
-  return TC.compareDeclarations(DC, decl1, decl2);
-}
-
-/// "Sanitize" requirements for conformance checking, removing any requirements
-/// that unnecessarily refer to associated types of other protocols.
-static void sanitizeProtocolRequirements(
-                                     ProtocolDecl *proto,
-                                     ArrayRef<Requirement> requirements,
-                                     SmallVectorImpl<Requirement> &sanitized) {
-  std::function<Type(Type)> sanitizeType;
-  sanitizeType = [&](Type outerType) {
-    return outerType.transformRec([&] (TypeBase *type) -> Optional<Type> {
-      if (auto depMemTy = dyn_cast<DependentMemberType>(type)) {
-        if (!depMemTy->getAssocType() ||
-            depMemTy->getAssocType()->getProtocol() != proto) {
-          for (auto member : proto->lookupDirect(depMemTy->getName())) {
-            if (auto assocType = dyn_cast<AssociatedTypeDecl>(member)) {
-              return Type(DependentMemberType::get(
-                                           sanitizeType(depMemTy->getBase()),
-                                           assocType));
-            }
-          }
-
-          if (depMemTy->getBase()->is<GenericTypeParamType>())
-            return Type();
-        }
-      }
-
-      return None;
-    });
-  };
-
-  for (const auto &req : requirements) {
-    switch (req.getKind()) {
-    case RequirementKind::Conformance:
-    case RequirementKind::SameType:
-    case RequirementKind::Superclass: {
-      Type firstType = sanitizeType(req.getFirstType());
-      Type secondType = sanitizeType(req.getSecondType());
-      if (firstType && secondType) {
-        sanitized.push_back({req.getKind(), firstType, secondType});
-      }
-      break;
-    }
-
-    case RequirementKind::Layout: {
-      Type firstType = sanitizeType(req.getFirstType());
-      if (firstType) {
-        sanitized.push_back({req.getKind(), firstType,
-                             req.getLayoutConstraint()});
-      }
-      break;
-    }
-    }
-  }
-}
-
-void ConformanceChecker::resolveTypeWitnesses() {
-  llvm::SetVector<AssociatedTypeDecl *> unresolvedAssocTypes;
-
-  SWIFT_DEFER {
-    // Resolution attempts to have the witnesses be correct by construction, but
-    // this isn't guaranteed, so let's double check.
-    ensureRequirementsAreSatisfied();
-  };
-
-  // Track when we are checking type witnesses.
-  ProtocolConformanceState initialState = Conformance->getState();
-  Conformance->setState(ProtocolConformanceState::CheckingTypeWitnesses);
-  SWIFT_DEFER { Conformance->setState(initialState); };
-
-  for (auto assocType : Proto->getAssociatedTypeMembers()) {
-    // If we already have a type witness, do nothing.
-    if (Conformance->hasTypeWitness(assocType))
-      continue;
-    
-    // Try to resolve this type witness via name lookup, which is the
-    // most direct mechanism, overriding all others.
-    switch (resolveTypeWitnessViaLookup(assocType)) {
-    case ResolveWitnessResult::Success:
-      // Success. Move on to the next.
-      continue;
-
-    case ResolveWitnessResult::ExplicitFailed:
-      continue;
-
-    case ResolveWitnessResult::Missing:
-      // Note that we haven't resolved this associated type yet.
-      unresolvedAssocTypes.insert(assocType);
-      break;
-    }
-  }
-
-  // If we resolved everything, we're done.
-  if (unresolvedAssocTypes.empty())
-    return;
-
-  // Infer type witnesses from value witnesses.
-  auto inferred = inferTypeWitnessesViaValueWitnesses(unresolvedAssocTypes);
-  DEBUG(llvm::dbgs() << "Candidates for inference:\n";
-        dumpInferredAssociatedTypes(inferred));
-
-  // Compute the set of solutions.
-  SmallVector<std::pair<ValueDecl *, ValueDecl *>, 4> valueWitnesses;
-  unsigned numValueWitnessesInProtocolExtensions = 0;
-  llvm::ScopedHashTable<AssociatedTypeDecl *, std::pair<Type, unsigned>>
-    typeWitnesses;
-  typedef decltype(typeWitnesses)::ScopeTy TypeWitnessesScope;
-  unsigned numTypeWitnesses = 0;
-  SmallVector<InferredTypeWitnessesSolution, 4> solutions;
-  SmallVector<InferredTypeWitnessesSolution, 4> nonViableSolutions;
-
-  // Information to use for diagnosing failures when we don't have
-  // something more specific.
-
-  // Which type witness was missing?
-  AssociatedTypeDecl *missingTypeWitness = nullptr;
-
-  // Was there a conflict in type witness deduction?
-  Optional<TypeWitnessConflict> typeWitnessConflict;
-  unsigned numTypeWitnessesBeforeConflict;
-
-  // Did an associated type default fail?
-  AssociatedTypeDecl *failedDefaultedAssocType = nullptr;
-  Type failedDefaultedWitness;
-  CheckTypeWitnessResult failedDefaultedResult;
-
-  // Local function to compute the default type of an associated type.
-  auto computeDefaultTypeWitness = [&](AssociatedTypeDecl *assocType) -> Type {
-    // If we don't have a default definition, we're done.
-    if (assocType->getDefaultDefinitionLoc().isNull())
-      return Type();
-
-    auto selfType = Proto->getSelfInterfaceType();
-
-    // Create a set of type substitutions for all known associated type.
-    // FIXME: Base this on dependent types rather than archetypes?
-    TypeSubstitutionMap substitutions;
-    substitutions[Proto->mapTypeIntoContext(selfType)
-        ->castTo<ArchetypeType>()] = DC->mapTypeIntoContext(Adoptee);
-    for (auto assocType : Proto->getAssociatedTypeMembers()) {
-      auto archetype = Proto->mapTypeIntoContext(
-        assocType->getDeclaredInterfaceType())
-        ->getAs<ArchetypeType>();
-      if (!archetype)
-        continue;
-      if (Conformance->hasTypeWitness(assocType)) {
-        substitutions[archetype] =
-          DC->mapTypeIntoContext(
-            Conformance->getTypeWitness(assocType, nullptr));
-      } else {
-        auto known = typeWitnesses.begin(assocType);
-        if (known != typeWitnesses.end())
-          substitutions[archetype] = known->first;
-        else
-          substitutions[archetype] = ErrorType::get(archetype);
-      }
-    }
-
-    TC.validateDecl(assocType);
-    Type defaultType = assocType->getDefaultDefinitionLoc().getType();
-
-    // FIXME: Circularity
-    if (!defaultType)
-      return Type();
-
-    defaultType = defaultType.subst(
-        QueryTypeSubstitutionMap{substitutions},
-        LookUpConformanceInModule(DC->getParentModule()));
-
-    if (!defaultType)
-      return Type();
-
-    if (auto failed = checkTypeWitness(TC, DC, Proto, assocType, defaultType)) {
-      // Record the failure, if we haven't seen one already.
-      if (!failedDefaultedAssocType) {
-        failedDefaultedAssocType = assocType;
-        failedDefaultedWitness = defaultType;
-        failedDefaultedResult = failed;
-      }
-
-      return Type();
-    }
-
-    return defaultType;
-  };
-
-  // Local function to compute the derived type of an associated type,
-  // for protocols known to the compiler.
-  auto computeDerivedTypeWitness = [&](AssociatedTypeDecl *assocType) -> Type {
-    if (Adoptee->hasError())
-      return Type();
-
-    // UnresolvedTypes propagated their unresolvedness to any witnesses.
-    if (Adoptee->is<UnresolvedType>())
-      return Adoptee;
-
-    // Can we derive conformances for this protocol and adoptee?
-    NominalTypeDecl *derivingTypeDecl = Adoptee->getAnyNominal();
-    if (!DerivedConformance::derivesProtocolConformance(TC, derivingTypeDecl,
-                                                        Proto))
-      return Type();
-
-    // Try to derive the type witness.
-    Type derivedType = TC.deriveTypeWitness(DC, derivingTypeDecl, assocType);
-    if (!derivedType)
-      return Type();
-
-    // Make sure that the derived type is sane.
-    if (checkTypeWitness(TC, DC, Proto, assocType, derivedType)) {
-      diagnoseOrDefer(assocType, true,
-        [derivedType](NormalProtocolConformance *conformance) {
-          // FIXME: give more detail here?
-          auto &diags = derivedType->getASTContext().Diags;
-          diags.diagnose(conformance->getLoc(),
-                         diag::protocol_derivation_is_broken,
-                         conformance->getProtocol()->getDeclaredType(),
-                         derivedType);
-      });
-
-      return Type();
-    }
-
-    return derivedType;
-  };
-
-  // Local function that folds dependent member types with non-dependent
-  // bases into actual member references.
-  std::function<Type(Type)> foldDependentMemberTypes;
-  llvm::DenseSet<AssociatedTypeDecl *> recursionCheck;
-  foldDependentMemberTypes = [&](Type type) -> Type {
-    if (auto depMemTy = type->getAs<DependentMemberType>()) {
-      auto baseTy = depMemTy->getBase().transform(foldDependentMemberTypes);
-      if (baseTy.isNull() || baseTy->hasTypeParameter())
-        return nullptr;
-
-      auto assocType = depMemTy->getAssocType();
-      if (!assocType)
-        return nullptr;
-
-      if (!recursionCheck.insert(assocType).second)
-        return nullptr;
-
-      SWIFT_DEFER { recursionCheck.erase(assocType); };
-
-      // Try to substitute into the base type.
-      if (Type result = depMemTy->substBaseType(DC->getParentModule(), baseTy)){
-        return result;
-      }
-
-      // If that failed, check whether it's because of the conformance we're
-      // evaluating.
-      auto localConformance
-        = TC.conformsToProtocol(
-                          baseTy, assocType->getProtocol(), DC,
-                          ConformanceCheckFlags::SkipConditionalRequirements);
-      if (!localConformance || localConformance->isAbstract() ||
-          (localConformance->getConcrete()->getRootNormalConformance()
-             != Conformance)) {
-        return nullptr;
-      }
-
-      // Find the tentative type witness for this associated type.
-      auto known = typeWitnesses.begin(assocType);
-      if (known == typeWitnesses.end())
-        return nullptr;
-
-      return known->first.transform(foldDependentMemberTypes);
-    }
-
-    // The presence of a generic type parameter indicates that we
-    // cannot use this type binding.
-    if (type->is<GenericTypeParamType>()) {
-      return nullptr;
-    }
-
-    return type;
-
-  };
-
-  auto typeInContext =
-    Conformance->getDeclContext()->mapTypeIntoContext(Conformance->getType());
-
-  // Local function that checks the current (complete) set of type witnesses
-  // to determine whether they meet all of the requirements and to deal with
-  // substitution of type witness bindings into other type witness bindings.
-  auto checkCurrentTypeWitnesses = [&]() -> bool {
-    // Fold the dependent member types within this type.
-    for (auto assocType : Proto->getAssociatedTypeMembers()) {
-      if (Conformance->hasTypeWitness(assocType))
-        continue;
-
-      // If the type binding does not have a type parameter, there's nothing
-      // to do.
-      auto known = typeWitnesses.begin(assocType);
-      assert(known != typeWitnesses.end());
-      if (!known->first->hasTypeParameter() &&
-          !known->first->hasDependentMember())
-        continue;
-
-      Type replaced = known->first.transform(foldDependentMemberTypes);
-      if (replaced.isNull())
-        return true;
-
-      known->first = replaced;
-    }
-
-    // Check any same-type requirements in the protocol's requirement signature.
-    if (Proto->isRequirementSignatureComputed()) {
-      SubstOptions options(None);
-      options.getTentativeTypeWitness =
-        [&](const NormalProtocolConformance *conformance,
-            AssociatedTypeDecl *assocType) -> TypeBase * {
-          if (conformance != Conformance) return nullptr;
-
-          auto type = typeWitnesses.begin(assocType)->first;
-          return type->mapTypeOutOfContext().getPointer();
-        };
-
-      auto substitutions =
-      SubstitutionMap::getProtocolSubstitutions(
-        Proto, typeInContext,
-                                          ProtocolConformanceRef(Conformance));
-
-      SmallVector<Requirement, 4> sanitizedRequirements;
-      sanitizeProtocolRequirements(Proto, Proto->getRequirementSignature(),
-                                   sanitizedRequirements);
-      auto result =
-        TC.checkGenericArguments(DC, SourceLoc(), SourceLoc(),
-                                 typeInContext,
-                                 { Proto->getProtocolSelfType() },
-                                 sanitizedRequirements,
-                                 QuerySubstitutionMap{substitutions},
-                                 TypeChecker::LookUpConformance(
-                                   TC, Conformance->getDeclContext()),
-                                 nullptr, None, nullptr, options);
-      switch (result) {
-      case RequirementCheckResult::Failure:
-      case RequirementCheckResult::UnsatisfiedDependency:
-        return true;
-
-      case RequirementCheckResult::Success:
-      case RequirementCheckResult::SubstitutionFailure:
-        return false;
-      }
-    }
-    return false;
-  };
-
-  // Local function to perform the depth-first search of the solution
-  // space.
-  std::function<void(unsigned)> findSolutions;
-  findSolutions = [&](unsigned reqDepth) {
-    // If we hit the last requirement, record and check this solution.
-    if (reqDepth == inferred.size()) {
-      // Introduce a hash table scope; we may add type witnesses here.
-      TypeWitnessesScope typeWitnessesScope(typeWitnesses);
-
-      // Check for completeness of the solution
-      for (auto assocType : unresolvedAssocTypes) {
-        // Local function to record a missing associated type.
-        auto recordMissing = [&] {
-          if (!missingTypeWitness)
-            missingTypeWitness = assocType;
-        };
-
-        auto typeWitness = typeWitnesses.begin(assocType);
-        if (typeWitness != typeWitnesses.end()) {
-          // The solution contains an error.
-          if (typeWitness->first->hasError()) {
-            recordMissing();
-            return;
-          }
-
-          continue;
-        }
-
-        // We don't have a type witness for this associated type.
-
-        // If we can form a default type, do so.
-        if (Type defaultType = computeDefaultTypeWitness(assocType)) {
-          if (defaultType->hasError()) {
-            recordMissing();
-            return;
-          }
-
-          typeWitnesses.insert(assocType, {defaultType, reqDepth});
-          continue;
-        }
-
-        // If we can derive a type witness, do so.
-        if (Type derivedType = computeDerivedTypeWitness(assocType)) {
-          if (derivedType->hasError()) {
-            recordMissing();
-            return;
-          }
-
-          typeWitnesses.insert(assocType, {derivedType, reqDepth});
-          continue;
-        }
-
-        // If there is a generic parameter of the named type, use that.
-        if (auto gpList = DC->getGenericParamsOfContext()) {
-          GenericTypeParamDecl *foundGP = nullptr;
-          for (auto gp : *gpList) {
-            if (gp->getName() == assocType->getName()) {
-              foundGP = gp;
-              break;
-            }
-          }
-
-          if (foundGP) {
-            auto gpType = DC->mapTypeIntoContext(
-                            foundGP->getDeclaredInterfaceType());
-            typeWitnesses.insert(assocType, {gpType, reqDepth});
-            continue;
-          }
-        }
-
-        // The solution is incomplete.
-        recordMissing();
-        return;
-      }
-
-      /// Check the current set of type witnesses.
-      bool invalid = checkCurrentTypeWitnesses();
-
-      // Determine whether there is already a solution with the same
-      // bindings.
-      for (const auto &solution : solutions) {
-        bool sameSolution = true;
-        for (const auto &existingTypeWitness : solution.TypeWitnesses) {
-          auto typeWitness = typeWitnesses.begin(existingTypeWitness.first);
-          if (!typeWitness->first->isEqual(existingTypeWitness.second.first)) {
-            sameSolution = false;
-            break;
-          }
-        }
-
-        // We found the same solution. There is no point in recording
-        // a new one.
-        if (sameSolution)
-          return;
-      }
-
-      auto &solutionList = invalid ? nonViableSolutions : solutions;
-      solutionList.push_back(InferredTypeWitnessesSolution());
-      auto &solution = solutionList.back();
-
-      // Copy the type witnesses.
-      for (auto assocType : unresolvedAssocTypes) {
-        auto typeWitness = typeWitnesses.begin(assocType);
-        solution.TypeWitnesses.insert({assocType, *typeWitness});
-      }
-
-      // Copy the value witnesses.
-      solution.ValueWitnesses = valueWitnesses;
-      solution.NumValueWitnessesInProtocolExtensions
-        = numValueWitnessesInProtocolExtensions;
-
-      // We're done recording the solution.
-      return;
-    }
-
-    // Iterate over the potential witnesses for this requirement,
-    // looking for solutions involving each one.
-    const auto &inferredReq = inferred[reqDepth];
-    for (const auto &witnessReq : inferredReq.second) {
-      // Enter a new scope for the type witnesses hash table.
-      TypeWitnessesScope typeWitnessesScope(typeWitnesses);
-      llvm::SaveAndRestore<unsigned> savedNumTypeWitnesses(numTypeWitnesses);
-
-      // Record this value witness, popping it when we exit the current scope.
-      valueWitnesses.push_back({inferredReq.first, witnessReq.Witness});
-      if (witnessReq.Witness->getDeclContext()->getAsProtocolExtensionContext())
-        ++numValueWitnessesInProtocolExtensions;
-      SWIFT_DEFER {
-        if (witnessReq.Witness->getDeclContext()->getAsProtocolExtensionContext())
-          --numValueWitnessesInProtocolExtensions;
-        valueWitnesses.pop_back();
-      };
-
-      // Introduce each of the type witnesses into the hash table.
-      bool failed = false;
-      for (const auto &typeWitness : witnessReq.Inferred) {
-        // If we've seen a type witness for this associated type that
-        // conflicts, there is no solution.
-        auto known = typeWitnesses.begin(typeWitness.first);
-        if (known != typeWitnesses.end()) {
-          // If witnesses for two difference requirements inferred the same
-          // type, we're okay.
-          if (known->first->isEqual(typeWitness.second))
-            continue;
-
-          // If one has a type parameter remaining but the other does not,
-          // drop the one with the type parameter.
-          if ((known->first->hasTypeParameter() ||
-               known->first->hasDependentMember())
-              != (typeWitness.second->hasTypeParameter() ||
-                  typeWitness.second->hasDependentMember())) {
-            if (typeWitness.second->hasTypeParameter() ||
-                typeWitness.second->hasDependentMember())
-              continue;
-
-            known->first = typeWitness.second;
-            continue;
-          }
-
-          if (!typeWitnessConflict ||
-              numTypeWitnesses > numTypeWitnessesBeforeConflict) {
-            typeWitnessConflict = {typeWitness.first,
-                                   typeWitness.second,
-                                   inferredReq.first,
-                                   witnessReq.Witness,
-                                   known->first,
-                                   valueWitnesses[known->second].first,
-                                   valueWitnesses[known->second].second};
-            numTypeWitnessesBeforeConflict = numTypeWitnesses;
-          }
-
-          failed = true;
-          break;
-        }
-
-        // Record the type witness.
-        ++numTypeWitnesses;
-        typeWitnesses.insert(typeWitness.first, {typeWitness.second, reqDepth});
-      }
-
-      if (failed)
-        continue;
-
-      // Recurse
-      findSolutions(reqDepth + 1);
-    }
-  };
-  findSolutions(0);
-
-  // Go make sure that type declarations that would act as witnesses
-  // did not get injected while we were performing checks above. This
-  // can happen when two associated types in different protocols have
-  // the same name, and validating a declaration (above) triggers the
-  // type-witness generation for that second protocol, introducing a
-  // new type declaration.
-  for (auto assocType : unresolvedAssocTypes) {
-      switch (resolveTypeWitnessViaLookup(assocType)) {
-      case ResolveWitnessResult::Success:
-      case ResolveWitnessResult::ExplicitFailed:
-        // A declaration that can become a witness has shown up. Go
-        // perform the resolution again now that we have more
-        // information.
-        return resolveTypeWitnesses();
-
-      case ResolveWitnessResult::Missing:
-        // The type witness is still missing. Keep going.
-        break;
-      }
-  }
-
-  // If we have more than one solution, do some simple ranking.
-  if (solutions.size() > 1) {
-    // Find the smallest number of value witnesses found in protocol extensions.
-    unsigned bestNumValueWitnessesInProtocolExtensions
-      = solutions.front().NumValueWitnessesInProtocolExtensions;
-    for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
-      bestNumValueWitnessesInProtocolExtensions
-        = std::min(bestNumValueWitnessesInProtocolExtensions,
-                   solutions[i].NumValueWitnessesInProtocolExtensions);
-    }
-
-    // Erase any solutions with more value witnesses in protocol
-    // extensions than the best.
-    solutions.erase(
-      std::remove_if(solutions.begin(), solutions.end(),
-                     [&](const InferredTypeWitnessesSolution &solution) {
-                       return solution.NumValueWitnessesInProtocolExtensions >
-                                bestNumValueWitnessesInProtocolExtensions;
-                     }),
-      solutions.end());
-  }
-
-  // If we (still) have more than one solution, find the one with
-  // more-specialized witnesses.
-  if (solutions.size() > 1) {
-    // Local function to compare two solutions.
-    auto compareSolutions = [&](const InferredTypeWitnessesSolution &first,
-                                const InferredTypeWitnessesSolution &second) {
-      assert(first.ValueWitnesses.size() == second.ValueWitnesses.size());
-      bool firstBetter = false;
-      bool secondBetter = false;
-      for (unsigned i = 0, n = first.ValueWitnesses.size(); i != n; ++i) {
-        assert(first.ValueWitnesses[i].first == second.ValueWitnesses[i].first);
-        auto firstWitness = first.ValueWitnesses[i].second;
-        auto secondWitness = second.ValueWitnesses[i].second;
-        if (firstWitness == secondWitness)
-          continue;
-
-        switch (compareDeclsForInference(TC, DC, firstWitness, secondWitness)) {
-        case Comparison::Better:
-          if (secondBetter)
-            return false;
-
-          firstBetter = true;
-          break;
-
-        case Comparison::Worse:
-          if (firstBetter)
-            return false;
-
-          secondBetter = true;
-          break;
-
-        case Comparison::Unordered:
-          break;
-        }
-      }
-
-      return firstBetter;
-    };
-
-    // Find a solution that's at least as good as the solutions that follow it.
-    unsigned bestIdx = 0;
-    for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
-      if (compareSolutions(solutions[i], solutions[bestIdx]))
-        bestIdx = i;
-    }
-    
-    // Make sure that solution is better than any of the other solutions.
-    bool ambiguous = false;
-    for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
-      if (i != bestIdx && !compareSolutions(solutions[bestIdx], solutions[i])) {
-        ambiguous = true;
-        break;
-      }
-    }
-    
-    // If we had a best solution, keep just that solution.
-    if (!ambiguous) {
-      if (bestIdx != 0)
-        solutions[0] = std::move(solutions[bestIdx]);
-      solutions.erase(solutions.begin() + 1, solutions.end());
-    }
-  }
-
-  // If we have no solution, but we did find something that is nonviable,
-  // use the first nonviable one to improve error reporting.
-  if (solutions.empty() && !nonViableSolutions.empty()) {
-    solutions.push_back(std::move(nonViableSolutions.front()));
-  }
-
-  // If we found a single solution, take it.
-  if (solutions.size() == 1) {
-    // Record each of the deduced witnesses.
-    auto &typeWitnesses = solutions.front().TypeWitnesses;
-    for (auto assocType : unresolvedAssocTypes) {
-      assert(typeWitnesses.count(assocType) == 1 && "missing witness");
-      auto replacement = typeWitnesses[assocType].first;
-      // FIXME: We can end up here with dependent types that were not folded
-      // away for some reason.
-      if (replacement->hasDependentMember())
-        replacement = ErrorType::get(TC.Context);
-      else if (replacement->hasArchetype())
-        replacement = replacement->mapTypeOutOfContext();
-      recordTypeWitness(assocType, replacement, nullptr, true);
-    }
-
-    return;
-  }
-
-  // Error cases follow.
-  Conformance->setInvalid();
-
-  // We're going to produce an error below. Mark each unresolved
-  // associated type witness as erroneous.
-  for (auto assocType : unresolvedAssocTypes) {
-    recordTypeWitness(assocType, ErrorType::get(TC.Context), nullptr, true);
-  }
-
-  // No solutions. Diagnose the first associated type for which we
-  // could not determine a witness.
-  if (solutions.empty()) {
-    // If a defaulted type witness failed, diagnose it.
-    if (failedDefaultedAssocType) {
-      diagnoseOrDefer(failedDefaultedAssocType, true,
-        [failedDefaultedAssocType, failedDefaultedWitness,
-         failedDefaultedResult](NormalProtocolConformance *conformance) {
-          auto proto = conformance->getProtocol();
-          auto &diags = proto->getASTContext().Diags;
-          diags.diagnose(failedDefaultedAssocType,
-                         diag::default_associated_type_req_fail,
-                         failedDefaultedWitness,
-                         failedDefaultedAssocType->getFullName(),
-                         proto->getDeclaredType(),
-                         failedDefaultedResult.getRequirement(),
-                         failedDefaultedResult.isConformanceRequirement());
-        });
-      return;
-    }
-
-    // Form a mapping from associated type declarations to failed type
-    // witnesses.
-    llvm::DenseMap<AssociatedTypeDecl *, SmallVector<FailedTypeWitness, 2>>
-      failedTypeWitnesses;
-    for (const auto &inferredReq : inferred) {
-      for (const auto &inferredWitness : inferredReq.second) {
-        for (const auto &nonViable : inferredWitness.NonViable) {
-          failedTypeWitnesses[std::get<0>(nonViable)]
-            .push_back({inferredReq.first, inferredWitness.Witness,
-                        std::get<1>(nonViable), std::get<2>(nonViable)});
-        }
-      }
-    }
-
-    // Local function to attempt to diagnose potential type witnesses
-    // that failed requirements.
-    auto tryDiagnoseTypeWitness = [&](AssociatedTypeDecl *assocType) -> bool {
-      auto known = failedTypeWitnesses.find(assocType);
-      if (known == failedTypeWitnesses.end())
-        return false;
-
-      auto failedSet = std::move(known->second);
-      diagnoseOrDefer(assocType, true,
-        [assocType, failedSet](NormalProtocolConformance *conformance) {
-          auto proto = conformance->getProtocol();
-          auto &diags = proto->getASTContext().Diags;
-          diags.diagnose(assocType, diag::bad_associated_type_deduction,
-                         assocType->getFullName(), proto->getFullName());
-          for (const auto &failed : failedSet) {
-            diags.diagnose(failed.Witness,
-                           diag::associated_type_deduction_witness_failed,
-                           failed.Requirement->getFullName(),
-                           failed.TypeWitness,
-                           failed.Result.getRequirement(),
-                           failed.Result.isConformanceRequirement());
-          }
-        });
-
-      return true;
-    };
-
-    // Try to diagnose the first missing type witness we encountered.
-    if (missingTypeWitness && tryDiagnoseTypeWitness(missingTypeWitness))
-      return;
-
-    // Failing that, try to diagnose any type witness that failed a
-    // requirement.
-    for (auto assocType : unresolvedAssocTypes) {
-      if (tryDiagnoseTypeWitness(assocType))
-        return;
-    }
-
-    // If we saw a conflict, complain about it.
-    if (typeWitnessConflict) {
-      diagnoseOrDefer(typeWitnessConflict->AssocType, true,
-        [typeWitnessConflict](NormalProtocolConformance *conformance) {
-          auto &diags = conformance->getDeclContext()->getASTContext().Diags;
-          diags.diagnose(typeWitnessConflict->AssocType,
-                         diag::ambiguous_associated_type_deduction,
-                         typeWitnessConflict->AssocType->getFullName(),
-                         typeWitnessConflict->FirstType,
-                         typeWitnessConflict->SecondType);
-        
-          diags.diagnose(typeWitnessConflict->FirstWitness,
-                         diag::associated_type_deduction_witness,
-                         typeWitnessConflict->FirstRequirement->getFullName(),
-                         typeWitnessConflict->FirstType);
-          diags.diagnose(typeWitnessConflict->SecondWitness,
-                         diag::associated_type_deduction_witness,
-                         typeWitnessConflict->SecondRequirement->getFullName(),
-                         typeWitnessConflict->SecondType);
-        });
-
-      return;
-    }
-
-    // Save the missing type witnesses for later diagnosis.
-    GlobalMissingWitnesses.insert(unresolvedAssocTypes.begin(),
-                            unresolvedAssocTypes.end());
-
-    return;
-  }
-
-  // Multiple solutions. Diagnose the ambiguity.
-  for (auto assocType : unresolvedAssocTypes) {
-    // Find two types that conflict.
-    auto &firstSolution = solutions.front();
-
-    // Local function to retrieve the value witness for the current associated
-    // type within the given solution.
-    auto getValueWitness = [&](InferredTypeWitnessesSolution &solution) {
-      unsigned witnessIdx = solution.TypeWitnesses[assocType].second;
-      if (witnessIdx < solution.ValueWitnesses.size())
-        return solution.ValueWitnesses[witnessIdx];
-
-      return std::pair<ValueDecl *, ValueDecl *>(nullptr, nullptr);
-    };
-
-    Type firstType = firstSolution.TypeWitnesses[assocType].first;
-
-    // Extract the value witness used to deduce this associated type, if any.
-    auto firstMatch = getValueWitness(firstSolution);
-
-    Type secondType;
-    std::pair<ValueDecl *, ValueDecl *> secondMatch;
-    for (auto &solution : solutions) {
-      Type typeWitness = solution.TypeWitnesses[assocType].first;
-      if (!typeWitness->isEqual(firstType)) {
-        secondType = typeWitness;
-        secondMatch = getValueWitness(solution);
-        break;
-      }
-    }
-
-    if (!secondType)
-      continue;
-
-    // We found an ambiguity. diagnose it.
-    diagnoseOrDefer(assocType, true,
-      [assocType, firstType, firstMatch, secondType, secondMatch](
-        NormalProtocolConformance *conformance) {
-        auto &diags = assocType->getASTContext().Diags;
-        diags.diagnose(assocType, diag::ambiguous_associated_type_deduction,
-                       assocType->getFullName(), firstType, secondType);
-
-        auto diagnoseWitness = [&](std::pair<ValueDecl *, ValueDecl *> match,
-                                   Type type){
-          // If we have a requirement/witness pair, diagnose it.
-          if (match.first && match.second) {
-            diags.diagnose(match.second,
-                           diag::associated_type_deduction_witness,
-                           match.first->getFullName(), type);
-
-            return;
-          }
-
-          // Otherwise, we have a default.
-          diags.diagnose(assocType, diag::associated_type_deduction_default,
-                         type)
-            .highlight(assocType->getDefaultDefinitionLoc().getSourceRange());
-        };
-
-        diagnoseWitness(firstMatch, firstType);
-        diagnoseWitness(secondMatch, secondType);
-      });
-
-    return;
-  }
-}
-
-void ConformanceChecker::resolveSingleTypeWitness(
-       AssociatedTypeDecl *assocType) {
-  // Ensure we diagnose if the witness is missing.
-  SWIFT_DEFER {
-    diagnoseMissingWitnesses(MissingWitnessDiagnosisKind::ErrorFixIt);
-  };
-  switch (resolveTypeWitnessViaLookup(assocType)) {
-  case ResolveWitnessResult::Success:
-  case ResolveWitnessResult::ExplicitFailed:
-    // We resolved this type witness one way or another.
-    return;
-
-  case ResolveWitnessResult::Missing:
-    // The type witness is still missing. Resolve all of the type witnesses.
-    resolveTypeWitnesses();
-    return;
-  }
-}
-
-void ConformanceChecker::resolveSingleWitness(ValueDecl *requirement) {
-  assert(!isa<AssociatedTypeDecl>(requirement) && "Not a value witness");
-  assert(!Conformance->hasWitness(requirement) && "Already resolved");
-
-  // Note that we're resolving this witness.
-  assert(ResolvingWitnesses.count(requirement) == 0 && "Currently resolving");
-  ResolvingWitnesses.insert(requirement);
-  SWIFT_DEFER { ResolvingWitnesses.erase(requirement); };
-
-  // Make sure we've validated the requirement.
-  if (!requirement->hasInterfaceType())
-    TC.validateDecl(requirement);
-
-  if (requirement->isInvalid() || !requirement->hasValidSignature()) {
-    Conformance->setInvalid();
-    return;
-  }
-
-  if (!requirement->isProtocolRequirement())
-    return;
-
-  // Resolve all associated types before trying to resolve this witness.
-  resolveTypeWitnesses();
-
-  // If any of the type witnesses was erroneous, don't bother to check
-  // this value witness: it will fail.
-  for (auto assocType : getReferencedAssociatedTypes(requirement)) {
-    if (Conformance->getTypeWitness(assocType, nullptr)->hasError()) {
-      Conformance->setInvalid();
-      return;
-    }
-  }
-
-  // Try to resolve the witness via explicit definitions.
-  switch (resolveWitnessViaLookup(requirement)) {
-  case ResolveWitnessResult::Success:
-    return;
-  
-  case ResolveWitnessResult::ExplicitFailed:
-    Conformance->setInvalid();
-    recordInvalidWitness(requirement);
-    return;
-
-  case ResolveWitnessResult::Missing:
-    // Continue trying below.
-    break;
-  }
-
-  // Try to resolve the witness via derivation.
-  switch (resolveWitnessViaDerivation(requirement)) {
-  case ResolveWitnessResult::Success:
-    return;
-
-  case ResolveWitnessResult::ExplicitFailed:
-    Conformance->setInvalid();
-    recordInvalidWitness(requirement);
-    return;
-
-  case ResolveWitnessResult::Missing:
-    // Continue trying below.
-    break;
-  }
-
-  // Try to resolve the witness via defaults.
-  switch (resolveWitnessViaDefault(requirement)) {
-  case ResolveWitnessResult::Success:
-    return;
-
-  case ResolveWitnessResult::ExplicitFailed:
-    Conformance->setInvalid();
-    recordInvalidWitness(requirement);
-    return;
-
-  case ResolveWitnessResult::Missing:
-    llvm_unreachable("Should have failed");
-    break;
-  }
-}
-
 static void recordConformanceDependency(DeclContext *DC,
                                         NominalTypeDecl *Adoptee,
                                         ProtocolConformance *Conformance,
diff --git a/lib/Sema/TypeCheckProtocol.h b/lib/Sema/TypeCheckProtocol.h
new file mode 100644
index 0000000..e84fac6
--- /dev/null
+++ b/lib/Sema/TypeCheckProtocol.h
@@ -0,0 +1,500 @@
+//===--- ConstraintSystem.h - Constraint-based Type Checking ----*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides the constraint-based type checker, anchored by the
+// \c ConstraintSystem class, which provides type checking and type
+// inference for expressions.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SWIFT_SEMA_PROTOCOL_H
+#define SWIFT_SEMA_PROTOCOL_H
+
+#include "swift/AST/Type.h"
+#include "swift/AST/Types.h"
+#include "llvm/ADT/ScopedHashTable.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace swift {
+
+class AccessScope;
+class AssociatedTypeDecl;
+class AvailabilityContext;
+class DeclContext;
+class NormalProtocolConformance;
+class ProtocolDecl;
+class TypeChecker;
+class ValueDecl;
+
+/// A conflict between two inferred type witnesses for the same
+/// associated type.
+struct TypeWitnessConflict {
+  /// The associated type.
+  AssociatedTypeDecl *AssocType;
+
+  /// The first type.
+  Type FirstType;
+
+  /// The requirement to which the first witness was matched.
+  ValueDecl *FirstRequirement;
+
+  /// The witness from which the first type witness was inferred.
+  ValueDecl *FirstWitness;
+
+  /// The second type.
+  Type SecondType;
+
+  /// The requirement to which the second witness was matched.
+  ValueDecl *SecondRequirement;
+
+  /// The witness from which the second type witness was inferred.
+  ValueDecl *SecondWitness;
+};
+
+/// Describes the result of checking a type witness.
+///
+/// This class evaluates true if an error occurred.
+class CheckTypeWitnessResult {
+  Type Requirement;
+
+public:
+  CheckTypeWitnessResult() { }
+  CheckTypeWitnessResult(Type reqt) : Requirement(reqt) {}
+
+  Type getRequirement() const { return Requirement; }
+  bool isConformanceRequirement() const {
+    return Requirement->isExistentialType();
+  }
+
+  explicit operator bool() const { return !Requirement.isNull(); }
+};
+
+/// Check whether the given type witness can be used for the given
+/// associated type.
+///
+/// \returns an empty result on success, or a description of the error.
+CheckTypeWitnessResult checkTypeWitness(TypeChecker &tc, DeclContext *dc,
+                                        ProtocolDecl *proto,
+                                        AssociatedTypeDecl *assocType,
+                                        Type type);
+
+/// The set of associated types that have been inferred by matching
+/// the given value witness to its corresponding requirement.
+struct InferredAssociatedTypesByWitness {
+  /// The witness we matched.
+  ValueDecl *Witness = nullptr;
+
+  /// The associated types inferred from matching this witness.
+  SmallVector<std::pair<AssociatedTypeDecl *, Type>, 4> Inferred;
+
+  /// Inferred associated types that don't meet the associated type
+  /// requirements.
+  SmallVector<std::tuple<AssociatedTypeDecl *, Type, CheckTypeWitnessResult>,
+              2> NonViable;
+
+  void dump(llvm::raw_ostream &out, unsigned indent) const;
+
+  LLVM_ATTRIBUTE_DEPRECATED(void dump() const,
+                            "only for use in the debugger");
+};
+
+/// The set of witnesses that were considered when attempting to
+/// infer associated types.
+typedef SmallVector<InferredAssociatedTypesByWitness, 2>
+  InferredAssociatedTypesByWitnesses;
+
+/// A mapping from requirements to the set of matches with witnesses.
+typedef SmallVector<std::pair<ValueDecl *,
+                              InferredAssociatedTypesByWitnesses>, 4>
+  InferredAssociatedTypes;
+
+/// A potential solution to the set of inferred type witnesses.
+struct InferredTypeWitnessesSolution {
+  /// The set of type witnesses inferred by this solution, along
+  /// with the index into the value witnesses where the type was
+  /// inferred.
+  llvm::SmallDenseMap<AssociatedTypeDecl *, std::pair<Type, unsigned>, 4>
+    TypeWitnesses;
+
+  /// The value witnesses selected by this step of the solution.
+  SmallVector<std::pair<ValueDecl *, ValueDecl *>, 4> ValueWitnesses;
+
+  /// The number of value witnesses that occur in protocol
+  /// extensions.
+  unsigned NumValueWitnessesInProtocolExtensions;
+
+#ifndef NDEBUG
+  LLVM_ATTRIBUTE_USED
+#endif
+  void dump();
+};
+
+struct RequirementMatch;
+struct RequirementCheck;
+
+class WitnessChecker {
+protected:
+  TypeChecker &TC;
+  ProtocolDecl *Proto;
+  Type Adoptee;
+  // The conforming context, either a nominal type or extension.
+  DeclContext *DC;
+
+  // An auxiliary lookup table to be used for witnesses remapped via
+  // @_implements(Protocol, DeclName)
+  llvm::DenseMap<DeclName, llvm::TinyPtrVector<ValueDecl *>> ImplementsTable;
+
+  WitnessChecker(TypeChecker &tc, ProtocolDecl *proto,
+                 Type adoptee, DeclContext *dc);
+
+  /// Gather the value witnesses for the given requirement.
+  ///
+  /// \param ignoringNames If non-null and there are no value
+  /// witnesses with the correct full name, the results will reflect
+  /// lookup for just the base name and the pointee will be set to
+  /// \c true.
+  SmallVector<ValueDecl *, 4> lookupValueWitnesses(ValueDecl *req,
+                                                   bool *ignoringNames);
+
+  void lookupValueWitnessesViaImplementsAttr(ValueDecl *req,
+                                             SmallVector<ValueDecl *, 4>
+                                             &witnesses);
+
+  bool findBestWitness(ValueDecl *requirement,
+                       bool *ignoringNames,
+                       NormalProtocolConformance *conformance,
+                       SmallVectorImpl<RequirementMatch> &matches,
+                       unsigned &numViable,
+                       unsigned &bestIdx,
+                       bool &doNotDiagnoseMatches);
+
+  bool checkWitnessAccess(AccessScope &requiredAccessScope,
+                          ValueDecl *requirement,
+                          ValueDecl *witness,
+                          bool *isSetter);
+
+  bool checkWitnessAvailability(ValueDecl *requirement,
+                                ValueDecl *witness,
+                                AvailabilityContext *requirementInfo);
+
+  RequirementCheck checkWitness(AccessScope requiredAccessScope,
+                                ValueDecl *requirement,
+                                const RequirementMatch &match);
+};
+
+/// The result of attempting to resolve a witness.
+enum class ResolveWitnessResult {
+  /// The resolution succeeded.
+  Success,
+  /// There was an explicit witness available, but it failed some
+  /// criteria.
+  ExplicitFailed,
+  /// There was no witness available.
+  Missing
+};
+
+enum class MissingWitnessDiagnosisKind {
+  FixItOnly,
+  ErrorOnly,
+  ErrorFixIt,
+};
+
+class AssociatedTypeInference;
+class MultiConformanceChecker;
+
+/// The protocol conformance checker.
+///
+/// This helper class handles most of the details of checking whether a
+/// given type (\c Adoptee) conforms to a protocol (\c Proto).
+class ConformanceChecker : public WitnessChecker {
+  friend class MultiConformanceChecker;
+  friend class AssociatedTypeInference;
+
+  NormalProtocolConformance *Conformance;
+  SourceLoc Loc;
+
+  /// Witnesses that are currently being resolved.
+  llvm::SmallPtrSet<ValueDecl *, 4> ResolvingWitnesses;
+
+  /// Caches the set of associated types that are referenced in each
+  /// requirement.
+  llvm::DenseMap<ValueDecl *, llvm::SmallVector<AssociatedTypeDecl *, 2>>
+    ReferencedAssociatedTypes;
+
+  /// Keep track of missing witnesses, either type or value, for later
+  /// diagnosis emits. This may contain witnesses that are external to the
+  /// protocol under checking.
+  llvm::SetVector<ValueDecl*> &GlobalMissingWitnesses;
+
+  /// Keep track of the slice in GlobalMissingWitnesses that is local to
+  /// this protocol under checking.
+  unsigned LocalMissingWitnessesStartIndex;
+
+  /// True if we shouldn't complain about problems with this conformance
+  /// right now, i.e. if methods are being called outside
+  /// checkConformance().
+  bool SuppressDiagnostics;
+
+  /// Whether we've already complained about problems with this conformance.
+  bool AlreadyComplained = false;
+
+  /// Whether we checked the requirement signature already.
+  bool CheckedRequirementSignature = false;
+
+  /// Retrieve the associated types that are referenced by the given
+  /// requirement with a base of 'Self'.
+  ArrayRef<AssociatedTypeDecl *> getReferencedAssociatedTypes(ValueDecl *req);
+
+  /// Record a (non-type) witness for the given requirement.
+  void recordWitness(ValueDecl *requirement, const RequirementMatch &match);
+
+  /// Record that the given optional requirement has no witness.
+  void recordOptionalWitness(ValueDecl *requirement);
+
+  /// Record that the given requirement has no valid witness.
+  void recordInvalidWitness(ValueDecl *requirement);
+
+  /// Record a type witness.
+  ///
+  /// \param assocType The associated type whose witness is being recorded.
+  ///
+  /// \param type The witness type.
+  ///
+  /// \param typeDecl The decl the witness type came from; can be null.
+  void recordTypeWitness(AssociatedTypeDecl *assocType, Type type,
+                         TypeDecl *typeDecl, bool performRedeclarationCheck);
+
+  /// Enforce restrictions on non-final classes witnessing requirements
+  /// involving the protocol 'Self' type.
+  void checkNonFinalClassWitness(ValueDecl *requirement,
+                                 ValueDecl *witness);
+
+  /// Resolve a (non-type) witness via name lookup.
+  ResolveWitnessResult resolveWitnessViaLookup(ValueDecl *requirement);
+
+  /// Resolve a (non-type) witness via derivation.
+  ResolveWitnessResult resolveWitnessViaDerivation(ValueDecl *requirement);
+
+  /// Resolve a (non-type) witness via default definition or optional.
+  ResolveWitnessResult resolveWitnessViaDefault(ValueDecl *requirement);
+
+  /// Attempt to resolve a type witness via member name lookup.
+  ResolveWitnessResult resolveTypeWitnessViaLookup(
+                         AssociatedTypeDecl *assocType);
+
+  /// Infer associated type witnesses for the given tentative
+  /// requirement/witness match.
+  InferredAssociatedTypesByWitness inferTypeWitnessesViaValueWitness(
+                                     ValueDecl *req,
+                                     ValueDecl *witness);
+
+  /// Infer associated type witnesses for the given value requirement.
+  InferredAssociatedTypesByWitnesses inferTypeWitnessesViaValueWitnesses(
+                   const llvm::SetVector<AssociatedTypeDecl *> &allUnresolved,
+                   ValueDecl *req);
+
+  /// Infer associated type witnesses for all relevant value requirements.
+  ///
+  /// \param assocTypes The set of associated types we're interested in.
+  InferredAssociatedTypes
+  inferTypeWitnessesViaValueWitnesses(
+    const llvm::SetVector<AssociatedTypeDecl *> &assocTypes);
+
+  /// Diagnose or defer a diagnostic, as appropriate.
+  ///
+  /// \param requirement The requirement with which this diagnostic is
+  /// associated, if any.
+  ///
+  /// \param isError Whether this diagnostic is an error.
+  ///
+  /// \param fn A function to call to emit the actual diagnostic. If
+  /// diagnostics are being deferred,
+  void diagnoseOrDefer(
+         ValueDecl *requirement, bool isError,
+         std::function<void(NormalProtocolConformance *)> fn);
+
+  void
+  addUsedConformances(ProtocolConformance *conformance,
+                      llvm::SmallPtrSetImpl<ProtocolConformance *> &visited);
+  void addUsedConformances(ProtocolConformance *conformance);
+
+  ArrayRef<ValueDecl*> getLocalMissingWitness() {
+    return GlobalMissingWitnesses.getArrayRef().
+      slice(LocalMissingWitnessesStartIndex,
+            GlobalMissingWitnesses.size() - LocalMissingWitnessesStartIndex);
+  }
+
+  void clearGlobalMissingWitnesses() {
+    GlobalMissingWitnesses.clear();
+    LocalMissingWitnessesStartIndex = GlobalMissingWitnesses.size();
+  }
+
+public:
+  /// Call this to diagnose currently known missing witnesses.
+  void diagnoseMissingWitnesses(MissingWitnessDiagnosisKind Kind);
+  /// Emit any diagnostics that have been delayed.
+  void emitDelayedDiags();
+
+  ConformanceChecker(TypeChecker &tc, NormalProtocolConformance *conformance,
+                     llvm::SetVector<ValueDecl*> &GlobalMissingWitnesses,
+                     bool suppressDiagnostics = true);
+
+  /// Resolve all of the type witnesses.
+  void resolveTypeWitnesses();
+
+  /// Resolve the witness for the given non-type requirement as
+  /// directly as possible, only resolving other witnesses if
+  /// needed, e.g., to determine type witnesses used within the
+  /// requirement.
+  ///
+  /// This entry point is designed to be used when the witness for a
+  /// particular requirement and adoptee is required, before the
+  /// conformance has been completed checked.
+  void resolveSingleWitness(ValueDecl *requirement);
+
+  /// Resolve the type witness for the given associated type as
+  /// directly as possible.
+  void resolveSingleTypeWitness(AssociatedTypeDecl *assocType);
+
+  /// Check all of the protocols requirements are actually satisfied by a
+  /// the chosen type witnesses.
+  void ensureRequirementsAreSatisfied();
+
+  /// Check the entire protocol conformance, ensuring that all
+  /// witnesses are resolved and emitting any diagnostics.
+  void checkConformance(MissingWitnessDiagnosisKind Kind);
+};
+/// Captures the state needed to infer associated types.
+class AssociatedTypeInference {
+  /// The type checker we'll need to validate declarations etc.
+  TypeChecker &tc;
+
+  /// The conformance for which we are inferring associated types.
+  NormalProtocolConformance *conformance;
+
+  /// The protocol for which we are inferring associated types.
+  ProtocolDecl *proto;
+
+  /// The declaration context in which conformance to the protocol is
+  /// declared.
+  DeclContext *dc;
+
+  /// The type that is adopting the protocol.
+  Type adoptee;
+
+  /// The set of type witnesses inferred from value witnesses.
+  InferredAssociatedTypes inferred;
+
+  /// Hash table containing the type witnesses that we've inferred for
+  /// each associated type, as well as an indication of how we inferred them.
+  llvm::ScopedHashTable<AssociatedTypeDecl *, std::pair<Type, unsigned>>
+    typeWitnesses;
+
+  /// Information about a failed, defaulted associated type.
+  AssociatedTypeDecl *failedDefaultedAssocType = nullptr;
+  Type failedDefaultedWitness;
+  CheckTypeWitnessResult failedDefaultedResult;
+
+  /// Information about a failed, derived associated type.
+  AssociatedTypeDecl *failedDerivedAssocType = nullptr;
+  Type failedDerivedWitness;
+
+  // Which type witness was missing?
+  AssociatedTypeDecl *missingTypeWitness = nullptr;
+
+  // Was there a conflict in type witness deduction?
+  Optional<TypeWitnessConflict> typeWitnessConflict;
+  unsigned numTypeWitnessesBeforeConflict = 0;
+
+public:
+  AssociatedTypeInference(TypeChecker &tc,
+                          NormalProtocolConformance *conformance);
+
+private:
+  /// Compute the default type witness from an associated type default,
+  /// if there is one.
+  Type computeDefaultTypeWitness(AssociatedTypeDecl *assocType);
+
+  /// Compute the "derived" type witness for an associated type that is
+  /// known to the compiler.
+  Type computeDerivedTypeWitness(AssociatedTypeDecl *assocType);
+
+  /// Substitute the current type witnesses into the given interface type.
+  Type substCurrentTypeWitnesses(Type type);
+
+  /// Check whether the current set of type witnesses meets the
+  /// requirements of the protocol.
+  bool checkCurrentTypeWitnesses();
+
+  /// Top-level operation to find solutions for the given unresolved
+  /// associated types.
+  void findSolutions(
+                 ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+                 SmallVectorImpl<InferredTypeWitnessesSolution> &solutions);
+
+  /// Explore the solution space to find both viable and non-viable solutions.
+  void findSolutionsRec(
+         ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+         SmallVectorImpl<InferredTypeWitnessesSolution> &solutions,
+         SmallVectorImpl<InferredTypeWitnessesSolution> &nonViableSolutions,
+         SmallVector<std::pair<ValueDecl *, ValueDecl *>, 4> &valueWitnesses,
+         unsigned numTypeWitnesses,
+         unsigned numValueWitnessesInProtocolExtensions,
+         unsigned reqDepth);
+
+  /// Determine whether the first solution is better than the second
+  /// solution.
+  bool isBetterSolution(const InferredTypeWitnessesSolution &first,
+                        const InferredTypeWitnessesSolution &second);
+
+  /// Find the best solution.
+  ///
+  /// \param solutions All of the solutions to consider. On success,
+  /// this will contain only the best solution.
+  ///
+  /// \returns \c false if there was a single best solution,
+  /// \c true if no single best solution exists.
+  bool findBestSolution(
+                SmallVectorImpl<InferredTypeWitnessesSolution> &solutions);
+
+  /// Emit a diagnostic for the case where there are no solutions at all
+  /// to consider.
+  ///
+  /// \returns true if a diagnostic was emitted, false otherwise.
+  bool diagnoseNoSolutions(
+                     ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+                     ConformanceChecker &checker);
+
+  /// Emit a diagnostic when there are multiple solutions.
+  ///
+  /// \returns true if a diagnostic was emitted, false otherwise.
+  bool diagnoseAmbiguousSolutions(
+                ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+                ConformanceChecker &checker,
+                SmallVectorImpl<InferredTypeWitnessesSolution> &solutions);
+
+public:
+  /// Describes a mapping from associated type declarations to their
+  /// type witnesses (as interface types).
+  typedef std::vector<std::pair<AssociatedTypeDecl *, Type>>
+    InferredTypeWitnesses;
+
+  /// Perform associated type inference.
+  ///
+  /// \returns \c true if an error occurred, \c false otherwise
+  Optional<InferredTypeWitnesses> solve(ConformanceChecker &checker);
+};
+
+}
+
+#endif // SWIFT_SEMA_PROTOCOL_H
diff --git a/lib/Sema/TypeCheckProtocolInference.cpp b/lib/Sema/TypeCheckProtocolInference.cpp
new file mode 100644
index 0000000..74b7e29
--- /dev/null
+++ b/lib/Sema/TypeCheckProtocolInference.cpp
@@ -0,0 +1,1275 @@
+//===--- TypeCheckProtocolInference.cpp - Associated Type Inference -------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements semantic analysis for protocols, in particular, checking
+// whether a given type conforms to a given protocol.
+//===----------------------------------------------------------------------===//
+#include "TypeCheckProtocol.h"
+#include "DerivedConformances.h"
+#include "TypeChecker.h"
+
+#include "swift/AST/Decl.h"
+#include "swift/AST/GenericSignature.h"
+#include "swift/AST/ProtocolConformance.h"
+#include "swift/AST/SubstitutionMap.h"
+#include "swift/AST/Types.h"
+#include "swift/Basic/Defer.h"
+#include "llvm/ADT/TinyPtrVector.h"
+
+#define DEBUG_TYPE "Associated type inference"
+#include "llvm/Support/Debug.h"
+
+using namespace swift;
+
+void InferredAssociatedTypesByWitness::dump() const {
+  dump(llvm::errs(), 0);
+}
+
+void InferredAssociatedTypesByWitness::dump(llvm::raw_ostream &out,
+                                            unsigned indent) const {
+  out << "\n";
+  out.indent(indent) << "(";
+  if (Witness) {
+    Witness->dumpRef(out);
+  }
+
+  for (const auto &inferred : Inferred) {
+    out << "\n";
+    out.indent(indent + 2);
+    out << inferred.first->getName() << " := "
+        << inferred.second.getString();
+  }
+
+  for (const auto &inferred : NonViable) {
+    out << "\n";
+    out.indent(indent + 2);
+    out << std::get<0>(inferred)->getName() << " := "
+        << std::get<1>(inferred).getString();
+    auto type = std::get<2>(inferred).getRequirement();
+    out << " [failed constraint " << type.getString() << "]";
+  }
+
+  out << ")";
+}
+
+void InferredTypeWitnessesSolution::dump() {
+  llvm::errs() << "Type Witnesses:\n";
+  for (auto &typeWitness : TypeWitnesses) {
+    llvm::errs() << "  " << typeWitness.first->getName() << " := ";
+    typeWitness.second.first->print(llvm::errs());
+    llvm::errs() << " value " << typeWitness.second.second << '\n';
+  }
+  llvm::errs() << "Value Witnesses:\n";
+  for (unsigned i : indices(ValueWitnesses)) {
+    auto &valueWitness = ValueWitnesses[i];
+    llvm::errs() << i << ":  " << (Decl*)valueWitness.first
+    << ' ' << valueWitness.first->getBaseName() << '\n';
+    valueWitness.first->getDeclContext()->dumpContext();
+    llvm::errs() << "    for " << (Decl*)valueWitness.second
+    << ' ' << valueWitness.second->getBaseName() << '\n';
+    valueWitness.second->getDeclContext()->dumpContext();
+  }
+}
+
+namespace {
+  void dumpInferredAssociatedTypesByWitnesses(
+        const InferredAssociatedTypesByWitnesses &inferred,
+        llvm::raw_ostream &out,
+        unsigned indent) {
+    for (const auto &value : inferred) {
+      value.dump(out, indent);
+    }
+  }
+
+  void dumpInferredAssociatedTypesByWitnesses(
+        const InferredAssociatedTypesByWitnesses &inferred) LLVM_ATTRIBUTE_USED;
+
+  void dumpInferredAssociatedTypesByWitnesses(
+                          const InferredAssociatedTypesByWitnesses &inferred) {
+    dumpInferredAssociatedTypesByWitnesses(inferred, llvm::errs(), 0);
+  }
+
+  void dumpInferredAssociatedTypes(const InferredAssociatedTypes &inferred,
+                                   llvm::raw_ostream &out,
+                                   unsigned indent) {
+    for (const auto &value : inferred) {
+      out << "\n";
+      out.indent(indent) << "(";
+      value.first->dumpRef(out);
+      dumpInferredAssociatedTypesByWitnesses(value.second, out, indent + 2);
+      out << ")";
+    }
+    out << "\n";
+  }
+
+  void dumpInferredAssociatedTypes(
+         const InferredAssociatedTypes &inferred) LLVM_ATTRIBUTE_USED;
+
+  void dumpInferredAssociatedTypes(const InferredAssociatedTypes &inferred) {
+    dumpInferredAssociatedTypes(inferred, llvm::errs(), 0);
+  }
+}
+
+AssociatedTypeInference::AssociatedTypeInference(
+                                       TypeChecker &tc,
+                                       NormalProtocolConformance *conformance)
+  : tc(tc), conformance(conformance), proto(conformance->getProtocol()),
+    dc(conformance->getDeclContext()),
+    adoptee(conformance->getType()) { }
+
+Type AssociatedTypeInference::computeDefaultTypeWitness(
+                                              AssociatedTypeDecl *assocType) {
+  // If we don't have a default definition, we're done.
+  if (assocType->getDefaultDefinitionLoc().isNull())
+    return Type();
+
+  auto selfType = proto->getSelfInterfaceType();
+
+  // Create a set of type substitutions for all known associated type.
+  // FIXME: Base this on dependent types rather than archetypes?
+  TypeSubstitutionMap substitutions;
+  substitutions[proto->mapTypeIntoContext(selfType)
+                  ->castTo<ArchetypeType>()] = dc->mapTypeIntoContext(adoptee);
+  for (auto assocType : proto->getAssociatedTypeMembers()) {
+    auto archetype = proto->mapTypeIntoContext(
+                       assocType->getDeclaredInterfaceType())
+                         ->getAs<ArchetypeType>();
+    if (!archetype)
+      continue;
+    if (conformance->hasTypeWitness(assocType)) {
+      substitutions[archetype] =
+        dc->mapTypeIntoContext(
+                        conformance->getTypeWitness(assocType, nullptr));
+    } else {
+      auto known = typeWitnesses.begin(assocType);
+      if (known != typeWitnesses.end())
+        substitutions[archetype] = known->first;
+      else
+        substitutions[archetype] = ErrorType::get(archetype);
+    }
+  }
+
+  tc.validateDecl(assocType);
+  Type defaultType = assocType->getDefaultDefinitionLoc().getType();
+
+  // FIXME: Circularity
+  if (!defaultType)
+    return Type();
+
+  defaultType = defaultType.subst(
+                          QueryTypeSubstitutionMap{substitutions},
+                          LookUpConformanceInModule(dc->getParentModule()));
+
+  if (!defaultType)
+    return Type();
+
+  if (auto failed = checkTypeWitness(tc, dc, proto, assocType, defaultType)) {
+    // Record the failure, if we haven't seen one already.
+    if (!failedDefaultedAssocType) {
+      failedDefaultedAssocType = assocType;
+      failedDefaultedWitness = defaultType;
+      failedDefaultedResult = failed;
+    }
+
+    return Type();
+  }
+
+  return defaultType;
+}
+
+Type AssociatedTypeInference::computeDerivedTypeWitness(
+                                              AssociatedTypeDecl *assocType) {
+  if (adoptee->hasError())
+    return Type();
+
+  // Can we derive conformances for this protocol and adoptee?
+  NominalTypeDecl *derivingTypeDecl = adoptee->getAnyNominal();
+  if (!DerivedConformance::derivesProtocolConformance(tc, derivingTypeDecl,
+                                                      proto))
+    return Type();
+
+  // Try to derive the type witness.
+  Type derivedType = tc.deriveTypeWitness(dc, derivingTypeDecl, assocType);
+  if (!derivedType)
+    return Type();
+
+  // Make sure that the derived type is sane.
+  if (checkTypeWitness(tc, dc, proto, assocType, derivedType)) {
+    /// FIXME: Diagnose based on this.
+    failedDerivedAssocType = assocType;
+    failedDerivedWitness = derivedType;
+    return Type();
+  }
+
+  return derivedType;
+}
+
+Type AssociatedTypeInference::substCurrentTypeWitnesses(Type type) {
+  // Local function that folds dependent member types with non-dependent
+  // bases into actual member references.
+  std::function<Type(Type)> foldDependentMemberTypes;
+  llvm::DenseSet<AssociatedTypeDecl *> recursionCheck;
+  foldDependentMemberTypes = [&](Type type) -> Type {
+    if (auto depMemTy = type->getAs<DependentMemberType>()) {
+      auto baseTy = depMemTy->getBase().transform(foldDependentMemberTypes);
+      if (baseTy.isNull() || baseTy->hasTypeParameter())
+        return nullptr;
+
+      auto assocType = depMemTy->getAssocType();
+      if (!assocType)
+        return nullptr;
+
+      if (!recursionCheck.insert(assocType).second)
+        return nullptr;
+
+      SWIFT_DEFER { recursionCheck.erase(assocType); };
+
+      // Try to substitute into the base type.
+      if (Type result = depMemTy->substBaseType(dc->getParentModule(), baseTy)){
+        return result;
+      }
+
+      // If that failed, check whether it's because of the conformance we're
+      // evaluating.
+      auto localConformance
+        = tc.conformsToProtocol(
+                          baseTy, assocType->getProtocol(), dc,
+                          ConformanceCheckFlags::SkipConditionalRequirements);
+      if (!localConformance || localConformance->isAbstract() ||
+          (localConformance->getConcrete()->getRootNormalConformance()
+             != conformance)) {
+        return nullptr;
+      }
+
+      // Find the tentative type witness for this associated type.
+      auto known = typeWitnesses.begin(assocType);
+      if (known == typeWitnesses.end())
+        return nullptr;
+
+      return known->first.transform(foldDependentMemberTypes);
+    }
+
+    // The presence of a generic type parameter indicates that we
+    // cannot use this type binding.
+    if (type->is<GenericTypeParamType>()) {
+      return nullptr;
+    }
+
+    return type;
+  };
+
+  return type.transform(foldDependentMemberTypes);
+}
+
+/// "Sanitize" requirements for conformance checking, removing any requirements
+/// that unnecessarily refer to associated types of other protocols.
+static void sanitizeProtocolRequirements(
+                                     ProtocolDecl *proto,
+                                     ArrayRef<Requirement> requirements,
+                                     SmallVectorImpl<Requirement> &sanitized) {
+  std::function<Type(Type)> sanitizeType;
+  sanitizeType = [&](Type outerType) {
+    return outerType.transformRec([&] (TypeBase *type) -> Optional<Type> {
+      if (auto depMemTy = dyn_cast<DependentMemberType>(type)) {
+        if (!depMemTy->getAssocType() ||
+            depMemTy->getAssocType()->getProtocol() != proto) {
+          for (auto member : proto->lookupDirect(depMemTy->getName())) {
+            if (auto assocType = dyn_cast<AssociatedTypeDecl>(member)) {
+              return Type(DependentMemberType::get(
+                                           sanitizeType(depMemTy->getBase()),
+                                           assocType));
+            }
+          }
+
+          if (depMemTy->getBase()->is<GenericTypeParamType>())
+            return Type();
+        }
+      }
+
+      return None;
+    });
+  };
+
+  for (const auto &req : requirements) {
+    switch (req.getKind()) {
+    case RequirementKind::Conformance:
+    case RequirementKind::SameType:
+    case RequirementKind::Superclass: {
+      Type firstType = sanitizeType(req.getFirstType());
+      Type secondType = sanitizeType(req.getSecondType());
+      if (firstType && secondType) {
+        sanitized.push_back({req.getKind(), firstType, secondType});
+      }
+      break;
+    }
+
+    case RequirementKind::Layout: {
+      Type firstType = sanitizeType(req.getFirstType());
+      if (firstType) {
+        sanitized.push_back({req.getKind(), firstType,
+                             req.getLayoutConstraint()});
+      }
+      break;
+    }
+    }
+  }
+}
+
+bool AssociatedTypeInference::checkCurrentTypeWitnesses() {
+  // Fold the dependent member types within this type.
+  for (auto assocType : proto->getAssociatedTypeMembers()) {
+    if (conformance->hasTypeWitness(assocType))
+      continue;
+
+    // If the type binding does not have a type parameter, there's nothing
+    // to do.
+    auto known = typeWitnesses.begin(assocType);
+    assert(known != typeWitnesses.end());
+    if (!known->first->hasTypeParameter() &&
+        !known->first->hasDependentMember())
+      continue;
+
+    Type replaced = substCurrentTypeWitnesses(known->first);
+    if (replaced.isNull())
+      return true;
+
+    known->first = replaced;
+  }
+
+  // If we don't have a requirement signature for this protocol, bail out.
+  // FIXME: We should never get to this point. Or we should always fail.
+  if (!proto->isRequirementSignatureComputed()) return false;
+
+  // Check any same-type requirements in the protocol's requirement signature.
+  SubstOptions options(None);
+  options.getTentativeTypeWitness =
+    [&](const NormalProtocolConformance *conformance,
+        AssociatedTypeDecl *assocType) -> TypeBase * {
+      if (conformance != this->conformance) return nullptr;
+
+      auto type = typeWitnesses.begin(assocType)->first;
+      return type->mapTypeOutOfContext().getPointer();
+    };
+
+  auto typeInContext = dc->mapTypeIntoContext(adoptee);
+
+  auto substitutions =
+    SubstitutionMap::getProtocolSubstitutions(
+                                    proto, typeInContext,
+                                    ProtocolConformanceRef(conformance));
+
+  SmallVector<Requirement, 4> sanitizedRequirements;
+  sanitizeProtocolRequirements(proto, proto->getRequirementSignature(),
+                               sanitizedRequirements);
+  auto result =
+    tc.checkGenericArguments(dc, SourceLoc(), SourceLoc(),
+                             typeInContext,
+                             { proto->getProtocolSelfType() },
+                             sanitizedRequirements,
+                             QuerySubstitutionMap{substitutions},
+                             TypeChecker::LookUpConformance(tc, dc),
+                             nullptr, None, nullptr, options);
+  switch (result) {
+  case RequirementCheckResult::Failure:
+  case RequirementCheckResult::UnsatisfiedDependency:
+    return true;
+
+  case RequirementCheckResult::Success:
+  case RequirementCheckResult::SubstitutionFailure:
+    return false;
+  }
+
+  return false;
+}
+
+void AssociatedTypeInference::findSolutions(
+                   ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+                   SmallVectorImpl<InferredTypeWitnessesSolution> &solutions) {
+  SmallVector<InferredTypeWitnessesSolution, 4> nonViableSolutions;
+  SmallVector<std::pair<ValueDecl *, ValueDecl *>, 4> valueWitnesses;
+  findSolutionsRec(unresolvedAssocTypes, solutions, nonViableSolutions,
+                   valueWitnesses, 0, 0, 0);
+}
+
+void AssociatedTypeInference::findSolutionsRec(
+          ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+          SmallVectorImpl<InferredTypeWitnessesSolution> &solutions,
+          SmallVectorImpl<InferredTypeWitnessesSolution> &nonViableSolutions,
+          SmallVector<std::pair<ValueDecl *, ValueDecl *>, 4> &valueWitnesses,
+          unsigned numTypeWitnesses,
+          unsigned numValueWitnessesInProtocolExtensions,
+          unsigned reqDepth) {
+  typedef decltype(typeWitnesses)::ScopeTy TypeWitnessesScope;
+
+  // If we hit the last requirement, record and check this solution.
+  if (reqDepth == inferred.size()) {
+    // Introduce a hash table scope; we may add type witnesses here.
+    TypeWitnessesScope typeWitnessesScope(typeWitnesses);
+
+    // Check for completeness of the solution
+    for (auto assocType : unresolvedAssocTypes) {
+      // Local function to record a missing associated type.
+      auto recordMissing = [&] {
+        if (!missingTypeWitness)
+          missingTypeWitness = assocType;
+      };
+
+      auto typeWitness = typeWitnesses.begin(assocType);
+      if (typeWitness != typeWitnesses.end()) {
+        // The solution contains an error.
+        if (typeWitness->first->hasError()) {
+          recordMissing();
+          return;
+        }
+
+        continue;
+      }
+
+      // We don't have a type witness for this associated type.
+
+      // If we can form a default type, do so.
+      if (Type defaultType = computeDefaultTypeWitness(assocType)) {
+        if (defaultType->hasError()) {
+          recordMissing();
+          return;
+        }
+
+        typeWitnesses.insert(assocType, {defaultType, reqDepth});
+        continue;
+      }
+
+      // If we can derive a type witness, do so.
+      if (Type derivedType = computeDerivedTypeWitness(assocType)) {
+        if (derivedType->hasError()) {
+          recordMissing();
+          return;
+        }
+
+        typeWitnesses.insert(assocType, {derivedType, reqDepth});
+        continue;
+      }
+
+      // If there is a generic parameter of the named type, use that.
+      if (auto gpList = dc->getGenericParamsOfContext()) {
+        GenericTypeParamDecl *foundGP = nullptr;
+        for (auto gp : *gpList) {
+          if (gp->getName() == assocType->getName()) {
+            foundGP = gp;
+            break;
+          }
+        }
+
+        if (foundGP) {
+          auto gpType = dc->mapTypeIntoContext(
+                          foundGP->getDeclaredInterfaceType());
+          typeWitnesses.insert(assocType, {gpType, reqDepth});
+          continue;
+        }
+      }
+
+      // The solution is incomplete.
+      recordMissing();
+      return;
+    }
+
+    /// Check the current set of type witnesses.
+    bool invalid = checkCurrentTypeWitnesses();
+
+    // Determine whether there is already a solution with the same
+    // bindings.
+    for (const auto &solution : solutions) {
+      bool sameSolution = true;
+      for (const auto &existingTypeWitness : solution.TypeWitnesses) {
+        auto typeWitness = typeWitnesses.begin(existingTypeWitness.first);
+        if (!typeWitness->first->isEqual(existingTypeWitness.second.first)) {
+          sameSolution = false;
+          break;
+        }
+      }
+
+      // We found the same solution. There is no point in recording
+      // a new one.
+      if (sameSolution)
+        return;
+    }
+
+    auto &solutionList = invalid ? nonViableSolutions : solutions;
+    solutionList.push_back(InferredTypeWitnessesSolution());
+    auto &solution = solutionList.back();
+
+    // Copy the type witnesses.
+    for (auto assocType : unresolvedAssocTypes) {
+      auto typeWitness = typeWitnesses.begin(assocType);
+      solution.TypeWitnesses.insert({assocType, *typeWitness});
+    }
+
+    // Copy the value witnesses.
+    solution.ValueWitnesses = valueWitnesses;
+    solution.NumValueWitnessesInProtocolExtensions
+      = numValueWitnessesInProtocolExtensions;
+
+    // We're done recording the solution.
+    return;
+  }
+
+  // Iterate over the potential witnesses for this requirement,
+  // looking for solutions involving each one.
+  const auto &inferredReq = inferred[reqDepth];
+  for (const auto &witnessReq : inferredReq.second) {
+    // Enter a new scope for the type witnesses hash table.
+    TypeWitnessesScope typeWitnessesScope(typeWitnesses);
+    llvm::SaveAndRestore<unsigned> savedNumTypeWitnesses(numTypeWitnesses);
+
+    // Record this value witness, popping it when we exit the current scope.
+    valueWitnesses.push_back({inferredReq.first, witnessReq.Witness});
+    if (witnessReq.Witness->getDeclContext()->getAsProtocolExtensionContext())
+      ++numValueWitnessesInProtocolExtensions;
+    SWIFT_DEFER {
+      if (witnessReq.Witness->getDeclContext()->getAsProtocolExtensionContext())
+        --numValueWitnessesInProtocolExtensions;
+      valueWitnesses.pop_back();
+    };
+
+    // Introduce each of the type witnesses into the hash table.
+    bool failed = false;
+    for (const auto &typeWitness : witnessReq.Inferred) {
+      // If we've seen a type witness for this associated type that
+      // conflicts, there is no solution.
+      auto known = typeWitnesses.begin(typeWitness.first);
+      if (known != typeWitnesses.end()) {
+        // If witnesses for two difference requirements inferred the same
+        // type, we're okay.
+        if (known->first->isEqual(typeWitness.second))
+          continue;
+
+        // If one has a type parameter remaining but the other does not,
+        // drop the one with the type parameter.
+        if ((known->first->hasTypeParameter() ||
+             known->first->hasDependentMember())
+            != (typeWitness.second->hasTypeParameter() ||
+                typeWitness.second->hasDependentMember())) {
+          if (typeWitness.second->hasTypeParameter() ||
+              typeWitness.second->hasDependentMember())
+            continue;
+
+          known->first = typeWitness.second;
+          continue;
+        }
+
+        if (!typeWitnessConflict ||
+            numTypeWitnesses > numTypeWitnessesBeforeConflict) {
+          typeWitnessConflict = {typeWitness.first,
+                                 typeWitness.second,
+                                 inferredReq.first,
+                                 witnessReq.Witness,
+                                 known->first,
+                                 valueWitnesses[known->second].first,
+                                 valueWitnesses[known->second].second};
+          numTypeWitnessesBeforeConflict = numTypeWitnesses;
+        }
+
+        failed = true;
+        break;
+      }
+
+      // Record the type witness.
+      ++numTypeWitnesses;
+      typeWitnesses.insert(typeWitness.first, {typeWitness.second, reqDepth});
+    }
+
+    if (failed)
+      continue;
+
+    // Recurse
+    findSolutionsRec(unresolvedAssocTypes, solutions, nonViableSolutions,
+                     valueWitnesses, numTypeWitnesses,
+                     numValueWitnessesInProtocolExtensions, reqDepth + 1);
+  }
+}
+
+static Comparison
+compareDeclsForInference(TypeChecker &TC, DeclContext *DC,
+                         ValueDecl *decl1, ValueDecl *decl2) {
+  // TC.compareDeclarations assumes that it's comparing two decls that
+  // apply equally well to a call site. We haven't yet inferred the
+  // associated types for a type, so the ranking algorithm used by
+  // compareDeclarations to score protocol extensions is inappropriate,
+  // since we may have potential witnesses from extensions with mutually
+  // exclusive associated type constraints, and compareDeclarations will
+  // consider these unordered since neither extension's generic signature
+  // is a superset of the other.
+
+  // If the witnesses come from the same decl context, score normally.
+  auto dc1 = decl1->getDeclContext();
+  auto dc2 = decl2->getDeclContext();
+
+  if (dc1 == dc2)
+    return TC.compareDeclarations(DC, decl1, decl2);
+
+  auto isProtocolExt1 =
+    (bool)dc1->getAsProtocolExtensionContext();
+  auto isProtocolExt2 =
+    (bool)dc2->getAsProtocolExtensionContext();
+
+  // If one witness comes from a protocol extension, favor the one
+  // from a concrete context.
+  if (isProtocolExt1 != isProtocolExt2) {
+    return isProtocolExt1 ? Comparison::Worse : Comparison::Better;
+  }
+
+  // If both witnesses came from concrete contexts, score normally.
+  // Associated type inference shouldn't impact the result.
+  // FIXME: It could, if someone constrained to ConcreteType.AssocType...
+  if (!isProtocolExt1)
+    return TC.compareDeclarations(DC, decl1, decl2);
+
+  // Compare protocol extensions by which protocols they require Self to
+  // conform to. If one extension requires a superset of the other's
+  // constraints, it wins.
+  auto sig1 = dc1->getGenericSignatureOfContext();
+  auto sig2 = dc2->getGenericSignatureOfContext();
+
+  // FIXME: Extensions sometimes have null generic signatures while
+  // checking the standard library...
+  if (!sig1 || !sig2)
+    return TC.compareDeclarations(DC, decl1, decl2);
+
+  auto selfParam = GenericTypeParamType::get(0, 0, TC.Context);
+
+  // Collect the protocols required by extension 1.
+  Type class1;
+  SmallPtrSet<ProtocolDecl*, 4> protos1;
+
+  std::function<void (ProtocolDecl*)> insertProtocol;
+  insertProtocol = [&](ProtocolDecl *p) {
+    if (!protos1.insert(p).second)
+      return;
+
+    for (auto parent : p->getInheritedProtocols())
+      insertProtocol(parent);
+  };
+
+  for (auto &reqt : sig1->getRequirements()) {
+    if (!reqt.getFirstType()->isEqual(selfParam))
+      continue;
+    switch (reqt.getKind()) {
+    case RequirementKind::Conformance: {
+      auto *proto = reqt.getSecondType()->castTo<ProtocolType>()->getDecl();
+      insertProtocol(proto);
+      break;
+    }
+    case RequirementKind::Superclass:
+      class1 = reqt.getSecondType();
+      break;
+
+    case RequirementKind::SameType:
+    case RequirementKind::Layout:
+      break;
+    }
+  }
+
+  // Compare with the protocols required by extension 2.
+  Type class2;
+  SmallPtrSet<ProtocolDecl*, 4> protos2;
+  bool protos2AreSubsetOf1 = true;
+  std::function<void (ProtocolDecl*)> removeProtocol;
+  removeProtocol = [&](ProtocolDecl *p) {
+    if (!protos2.insert(p).second)
+      return;
+
+    protos2AreSubsetOf1 &= protos1.erase(p);
+    for (auto parent : p->getInheritedProtocols())
+      removeProtocol(parent);
+  };
+
+  for (auto &reqt : sig2->getRequirements()) {
+    if (!reqt.getFirstType()->isEqual(selfParam))
+      continue;
+    switch (reqt.getKind()) {
+    case RequirementKind::Conformance: {
+      auto *proto = reqt.getSecondType()->castTo<ProtocolType>()->getDecl();
+      removeProtocol(proto);
+      break;
+    }
+    case RequirementKind::Superclass:
+      class2 = reqt.getSecondType();
+      break;
+
+    case RequirementKind::SameType:
+    case RequirementKind::Layout:
+      break;
+    }
+  }
+
+  auto isClassConstraintAsStrict = [&](Type t1, Type t2) -> bool {
+    if (!t1)
+      return !t2;
+
+    if (!t2)
+      return true;
+
+    return TC.isSubclassOf(t1, t2, DC);
+  };
+
+  bool protos1AreSubsetOf2 = protos1.empty();
+  // If the second extension requires strictly more protocols than the
+  // first, it's better.
+  if (protos1AreSubsetOf2 > protos2AreSubsetOf1
+      && isClassConstraintAsStrict(class2, class1)) {
+    return Comparison::Worse;
+  // If the first extension requires strictly more protocols than the
+  // second, it's better.
+  } else if (protos2AreSubsetOf1 > protos1AreSubsetOf2
+             && isClassConstraintAsStrict(class1, class2)) {
+    return Comparison::Better;
+  }
+
+  // If they require the same set of protocols, or non-overlapping
+  // sets, judge them normally.
+  return TC.compareDeclarations(DC, decl1, decl2);
+}
+
+bool AssociatedTypeInference::isBetterSolution(
+                      const InferredTypeWitnessesSolution &first,
+                      const InferredTypeWitnessesSolution &second) {
+  assert(first.ValueWitnesses.size() == second.ValueWitnesses.size());
+  bool firstBetter = false;
+  bool secondBetter = false;
+  for (unsigned i = 0, n = first.ValueWitnesses.size(); i != n; ++i) {
+    assert(first.ValueWitnesses[i].first == second.ValueWitnesses[i].first);
+    auto firstWitness = first.ValueWitnesses[i].second;
+    auto secondWitness = second.ValueWitnesses[i].second;
+    if (firstWitness == secondWitness)
+      continue;
+
+    switch (compareDeclsForInference(tc, dc, firstWitness, secondWitness)) {
+    case Comparison::Better:
+      if (secondBetter)
+        return false;
+
+      firstBetter = true;
+      break;
+
+    case Comparison::Worse:
+      if (firstBetter)
+        return false;
+
+      secondBetter = true;
+      break;
+
+    case Comparison::Unordered:
+      break;
+    }
+  }
+
+  return firstBetter;
+}
+
+bool AssociatedTypeInference::findBestSolution(
+                   SmallVectorImpl<InferredTypeWitnessesSolution> &solutions) {
+  if (solutions.empty()) return true;
+  if (solutions.size() == 1) return false;
+
+  // Find the smallest number of value witnesses found in protocol extensions.
+  // FIXME: This is a silly heuristic that should go away.
+  unsigned bestNumValueWitnessesInProtocolExtensions
+    = solutions.front().NumValueWitnessesInProtocolExtensions;
+  for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
+    bestNumValueWitnessesInProtocolExtensions
+      = std::min(bestNumValueWitnessesInProtocolExtensions,
+                 solutions[i].NumValueWitnessesInProtocolExtensions);
+  }
+
+  // Erase any solutions with more value witnesses in protocol
+  // extensions than the best.
+  solutions.erase(
+    std::remove_if(solutions.begin(), solutions.end(),
+                   [&](const InferredTypeWitnessesSolution &solution) {
+                     return solution.NumValueWitnessesInProtocolExtensions >
+                              bestNumValueWitnessesInProtocolExtensions;
+                   }),
+    solutions.end());
+
+  // If we're down to one solution, success!
+  if (solutions.size() == 1) return false;
+
+  // Find a solution that's at least as good as the solutions that follow it.
+  unsigned bestIdx = 0;
+  for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
+    if (isBetterSolution(solutions[i], solutions[bestIdx]))
+      bestIdx = i;
+  }
+
+  // Make sure that solution is better than any of the other solutions.
+  bool ambiguous = false;
+  for (unsigned i = 1, n = solutions.size(); i != n; ++i) {
+    if (i != bestIdx && !isBetterSolution(solutions[bestIdx], solutions[i])) {
+      ambiguous = true;
+      break;
+    }
+  }
+
+  // If the result was ambiguous, fail.
+  if (ambiguous) {
+    assert(solutions.size() != 1 && "should have succeeded somewhere above?");
+    return true;
+
+  }
+  // Keep the best solution, erasing all others.
+  if (bestIdx != 0)
+    solutions[0] = std::move(solutions[bestIdx]);
+  solutions.erase(solutions.begin() + 1, solutions.end());
+  return false;
+}
+
+namespace {
+  /// A failed type witness binding.
+  struct FailedTypeWitness {
+    /// The value requirement that triggered inference.
+    ValueDecl *Requirement;
+
+    /// The corresponding value witness from which the type witness
+    /// was inferred.
+    ValueDecl *Witness;
+
+    /// The actual type witness that was inferred.
+    Type TypeWitness;
+
+    /// The failed type witness result.
+    CheckTypeWitnessResult Result;
+  };
+} // end anonymous namespace
+
+bool AssociatedTypeInference::diagnoseNoSolutions(
+                         ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+                         ConformanceChecker &checker) {
+  // If a defaulted type witness failed, diagnose it.
+  if (failedDefaultedAssocType) {
+    auto failedDefaultedAssocType = this->failedDefaultedAssocType;
+    auto failedDefaultedWitness = this->failedDefaultedWitness;
+    auto failedDefaultedResult = this->failedDefaultedResult;
+
+    checker.diagnoseOrDefer(failedDefaultedAssocType, true,
+      [failedDefaultedAssocType, failedDefaultedWitness,
+       failedDefaultedResult](NormalProtocolConformance *conformance) {
+        auto proto = conformance->getProtocol();
+        auto &diags = proto->getASTContext().Diags;
+        diags.diagnose(failedDefaultedAssocType,
+                       diag::default_associated_type_req_fail,
+                       failedDefaultedWitness,
+                       failedDefaultedAssocType->getFullName(),
+                       proto->getDeclaredType(),
+                       failedDefaultedResult.getRequirement(),
+                       failedDefaultedResult.isConformanceRequirement());
+      });
+
+    return true;
+  }
+
+  // Form a mapping from associated type declarations to failed type
+  // witnesses.
+  llvm::DenseMap<AssociatedTypeDecl *, SmallVector<FailedTypeWitness, 2>>
+    failedTypeWitnesses;
+  for (const auto &inferredReq : inferred) {
+    for (const auto &inferredWitness : inferredReq.second) {
+      for (const auto &nonViable : inferredWitness.NonViable) {
+        failedTypeWitnesses[std::get<0>(nonViable)]
+          .push_back({inferredReq.first, inferredWitness.Witness,
+                      std::get<1>(nonViable), std::get<2>(nonViable)});
+      }
+    }
+  }
+
+  // Local function to attempt to diagnose potential type witnesses
+  // that failed requirements.
+  auto tryDiagnoseTypeWitness = [&](AssociatedTypeDecl *assocType) -> bool {
+    auto known = failedTypeWitnesses.find(assocType);
+    if (known == failedTypeWitnesses.end())
+      return false;
+
+    auto failedSet = std::move(known->second);
+    checker.diagnoseOrDefer(assocType, true,
+      [assocType, failedSet](NormalProtocolConformance *conformance) {
+        auto proto = conformance->getProtocol();
+        auto &diags = proto->getASTContext().Diags;
+        diags.diagnose(assocType, diag::bad_associated_type_deduction,
+                       assocType->getFullName(), proto->getFullName());
+        for (const auto &failed : failedSet) {
+          diags.diagnose(failed.Witness,
+                         diag::associated_type_deduction_witness_failed,
+                         failed.Requirement->getFullName(),
+                         failed.TypeWitness,
+                         failed.Result.getRequirement(),
+                         failed.Result.isConformanceRequirement());
+        }
+      });
+
+    return true;
+  };
+
+  // Try to diagnose the first missing type witness we encountered.
+  if (missingTypeWitness && tryDiagnoseTypeWitness(missingTypeWitness))
+    return true;
+
+  // Failing that, try to diagnose any type witness that failed a
+  // requirement.
+  for (auto assocType : unresolvedAssocTypes) {
+    if (tryDiagnoseTypeWitness(assocType))
+      return true;
+  }
+
+  // If we saw a conflict, complain about it.
+  if (typeWitnessConflict) {
+    auto typeWitnessConflict = this->typeWitnessConflict;
+
+    checker.diagnoseOrDefer(typeWitnessConflict->AssocType, true,
+      [typeWitnessConflict](NormalProtocolConformance *conformance) {
+        auto &diags = conformance->getDeclContext()->getASTContext().Diags;
+        diags.diagnose(typeWitnessConflict->AssocType,
+                       diag::ambiguous_associated_type_deduction,
+                       typeWitnessConflict->AssocType->getFullName(),
+                       typeWitnessConflict->FirstType,
+                       typeWitnessConflict->SecondType);
+
+        diags.diagnose(typeWitnessConflict->FirstWitness,
+                       diag::associated_type_deduction_witness,
+                       typeWitnessConflict->FirstRequirement->getFullName(),
+                       typeWitnessConflict->FirstType);
+        diags.diagnose(typeWitnessConflict->SecondWitness,
+                       diag::associated_type_deduction_witness,
+                       typeWitnessConflict->SecondRequirement->getFullName(),
+                       typeWitnessConflict->SecondType);
+      });
+
+    return true;
+  }
+
+  return false;
+}
+
+bool AssociatedTypeInference::diagnoseAmbiguousSolutions(
+                  ArrayRef<AssociatedTypeDecl *> unresolvedAssocTypes,
+                  ConformanceChecker &checker,
+                  SmallVectorImpl<InferredTypeWitnessesSolution> &solutions) {
+  for (auto assocType : unresolvedAssocTypes) {
+    // Find two types that conflict.
+    auto &firstSolution = solutions.front();
+
+    // Local function to retrieve the value witness for the current associated
+    // type within the given solution.
+    auto getValueWitness = [&](InferredTypeWitnessesSolution &solution) {
+      unsigned witnessIdx = solution.TypeWitnesses[assocType].second;
+      if (witnessIdx < solution.ValueWitnesses.size())
+        return solution.ValueWitnesses[witnessIdx];
+
+      return std::pair<ValueDecl *, ValueDecl *>(nullptr, nullptr);
+    };
+
+    Type firstType = firstSolution.TypeWitnesses[assocType].first;
+
+    // Extract the value witness used to deduce this associated type, if any.
+    auto firstMatch = getValueWitness(firstSolution);
+
+    Type secondType;
+    std::pair<ValueDecl *, ValueDecl *> secondMatch;
+    for (auto &solution : solutions) {
+      Type typeWitness = solution.TypeWitnesses[assocType].first;
+      if (!typeWitness->isEqual(firstType)) {
+        secondType = typeWitness;
+        secondMatch = getValueWitness(solution);
+        break;
+      }
+    }
+
+    if (!secondType)
+      continue;
+
+    // We found an ambiguity. diagnose it.
+    checker.diagnoseOrDefer(assocType, true,
+      [assocType, firstType, firstMatch, secondType, secondMatch](
+        NormalProtocolConformance *conformance) {
+        auto &diags = assocType->getASTContext().Diags;
+        diags.diagnose(assocType, diag::ambiguous_associated_type_deduction,
+                       assocType->getFullName(), firstType, secondType);
+
+        auto diagnoseWitness = [&](std::pair<ValueDecl *, ValueDecl *> match,
+                                   Type type){
+          // If we have a requirement/witness pair, diagnose it.
+          if (match.first && match.second) {
+            diags.diagnose(match.second,
+                           diag::associated_type_deduction_witness,
+                           match.first->getFullName(), type);
+
+            return;
+          }
+
+          // Otherwise, we have a default.
+          diags.diagnose(assocType, diag::associated_type_deduction_default,
+                         type)
+            .highlight(assocType->getDefaultDefinitionLoc().getSourceRange());
+        };
+
+        diagnoseWitness(firstMatch, firstType);
+        diagnoseWitness(secondMatch, secondType);
+      });
+
+    return true;
+  }
+
+  return false;
+}
+
+auto AssociatedTypeInference::solve(ConformanceChecker &checker)
+    -> Optional<InferredTypeWitnesses> {
+  // Track when we are checking type witnesses.
+  ProtocolConformanceState initialState = conformance->getState();
+  conformance->setState(ProtocolConformanceState::CheckingTypeWitnesses);
+  SWIFT_DEFER { conformance->setState(initialState); };
+
+  // Try to resolve type witnesses via name lookup.
+  llvm::SetVector<AssociatedTypeDecl *> unresolvedAssocTypes;
+  for (auto assocType : proto->getAssociatedTypeMembers()) {
+    // If we already have a type witness, do nothing.
+    if (conformance->hasTypeWitness(assocType))
+      continue;
+
+    // Try to resolve this type witness via name lookup, which is the
+    // most direct mechanism, overriding all others.
+    switch (checker.resolveTypeWitnessViaLookup(assocType)) {
+    case ResolveWitnessResult::Success:
+      // Success. Move on to the next.
+      continue;
+
+    case ResolveWitnessResult::ExplicitFailed:
+      continue;
+
+    case ResolveWitnessResult::Missing:
+      // Note that we haven't resolved this associated type yet.
+      unresolvedAssocTypes.insert(assocType);
+      break;
+    }
+  }
+
+  // Result variable to use for returns so that we get NRVO.
+  Optional<InferredTypeWitnesses> result;
+  result = { };
+
+  // If we resolved everything, we're done.
+  if (unresolvedAssocTypes.empty())
+    return result;
+
+  // Infer potential type witnesses from value witnesses.
+  inferred = checker.inferTypeWitnessesViaValueWitnesses(unresolvedAssocTypes);
+  DEBUG(llvm::dbgs() << "Candidates for inference:\n";
+        dumpInferredAssociatedTypes(inferred));
+
+  // Compute the set of solutions.
+  SmallVector<InferredTypeWitnessesSolution, 4> solutions;
+  findSolutions(unresolvedAssocTypes.getArrayRef(), solutions);
+
+  // Go make sure that type declarations that would act as witnesses
+  // did not get injected while we were performing checks above. This
+  // can happen when two associated types in different protocols have
+  // the same name, and validating a declaration (above) triggers the
+  // type-witness generation for that second protocol, introducing a
+  // new type declaration.
+  // FIXME: This is ridiculous.
+  for (auto assocType : unresolvedAssocTypes) {
+    switch (checker.resolveTypeWitnessViaLookup(assocType)) {
+    case ResolveWitnessResult::Success:
+    case ResolveWitnessResult::ExplicitFailed:
+      // A declaration that can become a witness has shown up. Go
+      // perform the resolution again now that we have more
+      // information.
+      return solve(checker);
+
+    case ResolveWitnessResult::Missing:
+      // The type witness is still missing. Keep going.
+      break;
+    }
+  }
+
+  // Find the best solution.
+  if (!findBestSolution(solutions)) {
+    assert(solutions.size() == 1 && "Not a unique best solution?");
+    // Form the resulting solution.
+    auto &typeWitnesses = solutions.front().TypeWitnesses;
+    for (auto assocType : unresolvedAssocTypes) {
+      assert(typeWitnesses.count(assocType) == 1 && "missing witness");
+      auto replacement = typeWitnesses[assocType].first;
+      // FIXME: We can end up here with dependent types that were not folded
+      // away for some reason.
+      if (replacement->hasDependentMember())
+        return None;
+
+      if (replacement->hasArchetype())
+        replacement = replacement->mapTypeOutOfContext();
+
+      result->push_back({assocType, replacement});
+    }
+
+    return result;
+  }
+
+  // Diagnose the complete lack of solutions.
+  if (solutions.empty() &&
+      diagnoseNoSolutions(unresolvedAssocTypes.getArrayRef(), checker))
+    return None;
+
+  // Diagnose ambiguous solutions.
+  if (!solutions.empty() &&
+      diagnoseAmbiguousSolutions(unresolvedAssocTypes.getArrayRef(), checker,
+                                 solutions))
+    return None;
+
+  // Save the missing type witnesses for later diagnosis.
+  checker.GlobalMissingWitnesses.insert(unresolvedAssocTypes.begin(),
+                                        unresolvedAssocTypes.end());
+  return None;
+}
+
+void ConformanceChecker::resolveTypeWitnesses() {
+  SWIFT_DEFER {
+    // Resolution attempts to have the witnesses be correct by construction, but
+    // this isn't guaranteed, so let's double check.
+    ensureRequirementsAreSatisfied();
+  };
+
+  // Attempt to infer associated type witnesses.
+  AssociatedTypeInference inference(TC, Conformance);
+  if (auto inferred = inference.solve(*this)) {
+    for (const auto &inferredWitness : *inferred) {
+      recordTypeWitness(inferredWitness.first, inferredWitness.second,
+                        /*typeDecl=*/nullptr,
+      /*performRedeclarationCheck=*/true);
+    }
+
+    ensureRequirementsAreSatisfied();
+    return;
+  }
+
+  // Conformance failed. Record errors for each of the witnesses.
+  Conformance->setInvalid();
+
+  // We're going to produce an error below. Mark each unresolved
+  // associated type witness as erroneous.
+  for (auto assocType : Proto->getAssociatedTypeMembers()) {
+    // If we already have a type witness, do nothing.
+    if (Conformance->hasTypeWitness(assocType))
+      continue;
+
+    recordTypeWitness(assocType, ErrorType::get(TC.Context), nullptr, true);
+  }
+
+  return;
+
+  // Multiple solutions. Diagnose the ambiguity.
+
+}
+
+void ConformanceChecker::resolveSingleTypeWitness(
+       AssociatedTypeDecl *assocType) {
+  // Ensure we diagnose if the witness is missing.
+  SWIFT_DEFER {
+    diagnoseMissingWitnesses(MissingWitnessDiagnosisKind::ErrorFixIt);
+  };
+  switch (resolveTypeWitnessViaLookup(assocType)) {
+  case ResolveWitnessResult::Success:
+  case ResolveWitnessResult::ExplicitFailed:
+    // We resolved this type witness one way or another.
+    return;
+
+  case ResolveWitnessResult::Missing:
+    // The type witness is still missing. Resolve all of the type witnesses.
+    resolveTypeWitnesses();
+    return;
+  }
+}
+
+void ConformanceChecker::resolveSingleWitness(ValueDecl *requirement) {
+  assert(!isa<AssociatedTypeDecl>(requirement) && "Not a value witness");
+  assert(!Conformance->hasWitness(requirement) && "Already resolved");
+
+  // Note that we're resolving this witness.
+  assert(ResolvingWitnesses.count(requirement) == 0 && "Currently resolving");
+  ResolvingWitnesses.insert(requirement);
+  SWIFT_DEFER { ResolvingWitnesses.erase(requirement); };
+
+  // Make sure we've validated the requirement.
+  if (!requirement->hasInterfaceType())
+    TC.validateDecl(requirement);
+
+  if (requirement->isInvalid() || !requirement->hasValidSignature()) {
+    Conformance->setInvalid();
+    return;
+  }
+
+  if (!requirement->isProtocolRequirement())
+    return;
+
+  // Resolve all associated types before trying to resolve this witness.
+  resolveTypeWitnesses();
+
+  // If any of the type witnesses was erroneous, don't bother to check
+  // this value witness: it will fail.
+  for (auto assocType : getReferencedAssociatedTypes(requirement)) {
+    if (Conformance->getTypeWitness(assocType, nullptr)->hasError()) {
+      Conformance->setInvalid();
+      return;
+    }
+  }
+
+  // Try to resolve the witness via explicit definitions.
+  switch (resolveWitnessViaLookup(requirement)) {
+  case ResolveWitnessResult::Success:
+    return;
+
+  case ResolveWitnessResult::ExplicitFailed:
+    Conformance->setInvalid();
+    recordInvalidWitness(requirement);
+    return;
+
+  case ResolveWitnessResult::Missing:
+    // Continue trying below.
+    break;
+  }
+
+  // Try to resolve the witness via derivation.
+  switch (resolveWitnessViaDerivation(requirement)) {
+  case ResolveWitnessResult::Success:
+    return;
+
+  case ResolveWitnessResult::ExplicitFailed:
+    Conformance->setInvalid();
+    recordInvalidWitness(requirement);
+    return;
+
+  case ResolveWitnessResult::Missing:
+    // Continue trying below.
+    break;
+  }
+
+  // Try to resolve the witness via defaults.
+  switch (resolveWitnessViaDefault(requirement)) {
+  case ResolveWitnessResult::Success:
+    return;
+
+  case ResolveWitnessResult::ExplicitFailed:
+    Conformance->setInvalid();
+    recordInvalidWitness(requirement);
+    return;
+
+  case ResolveWitnessResult::Missing:
+    llvm_unreachable("Should have failed");
+    break;
+  }
+}
diff --git a/test/Constraints/associated_types.swift b/test/Constraints/associated_types.swift
index fda2568..74af9b6 100644
--- a/test/Constraints/associated_types.swift
+++ b/test/Constraints/associated_types.swift
@@ -62,8 +62,8 @@
 protocol YReqt {}
 
 protocol SameTypedDefaultWithReqts {
-    associatedtype X: XReqt
-    associatedtype Y: YReqt
+    associatedtype X: XReqt // expected-note{{protocol requires nested type 'X'; do you want to add it?}}
+    associatedtype Y: YReqt // expected-note{{protocol requires nested type 'Y'; do you want to add it?}}
     static var x: X { get }
     static var y: Y { get }
 }
@@ -86,7 +86,7 @@
 }
 
 protocol SameTypedDefaultBaseWithReqts {
-    associatedtype X: XReqt
+    associatedtype X: XReqt // expected-note{{protocol requires nested type 'X'; do you want to add it?}}
     static var x: X { get }
 }
 protocol SameTypedDefaultDerivedWithReqts: SameTypedDefaultBaseWithReqts {
diff --git a/test/Generics/associated_type_where_clause.swift b/test/Generics/associated_type_where_clause.swift
index a342e62..04435c4 100644
--- a/test/Generics/associated_type_where_clause.swift
+++ b/test/Generics/associated_type_where_clause.swift
@@ -22,7 +22,7 @@
 struct ConcreteConformsNonFoo2: Conforms { typealias T = Float }
 
 protocol NestedConforms {
-    associatedtype U where U: Conforms, U.T: Foo2
+    associatedtype U where U: Conforms, U.T: Foo2 // expected-note{{protocol requires nested type 'U'; do you want to add it?}}
 
     func foo(_: U)
 }
@@ -43,7 +43,7 @@
     typealias U = ConcreteConformsNonFoo2
 }
 struct BadConcreteNestedConformsInfer: NestedConforms {
-    // expected-error@-1 {{type 'ConcreteConformsNonFoo2.T' (aka 'Float') does not conform to protocol 'Foo2'}}
+    // expected-error@-1 {{type 'BadConcreteNestedConformsInfer' does not conform to protocol 'NestedConforms'}}
     func foo(_: ConcreteConformsNonFoo2) {}
 }
 
@@ -61,7 +61,7 @@
 }
 
 protocol NestedSameType {
-    associatedtype U: Conforms where U.T == Int
+    associatedtype U: Conforms where U.T == Int // expected-note{{protocol requires nested type 'U'; do you want to add it?}}
 
     func foo(_: U)
 }
@@ -76,8 +76,7 @@
     typealias U = ConcreteConformsNonFoo2
 }
 struct BadConcreteNestedSameTypeInfer: NestedSameType {
-    // expected-error@-1 {{'NestedSameType' requires the types 'ConcreteConformsNonFoo2.T' (aka 'Float') and 'Int' be equivalent}}
-    // expected-note@-2 {{requirement specified as 'Self.U.T' == 'Int' [with Self = BadConcreteNestedSameTypeInfer]}}
+    // expected-error@-1 {{type 'BadConcreteNestedSameTypeInfer' does not conform to protocol 'NestedSameType'}}
     func foo(_: ConcreteConformsNonFoo2) {}
 }
 
diff --git a/test/decl/protocol/conforms/failure.swift b/test/decl/protocol/conforms/failure.swift
index a669f55..e9b1d3c 100644
--- a/test/decl/protocol/conforms/failure.swift
+++ b/test/decl/protocol/conforms/failure.swift
@@ -75,7 +75,7 @@
 
 
 protocol P6Base {
-  associatedtype Foo
+  associatedtype Foo // expected-note{{protocol requires nested type 'Foo'; do you want to add it?}}
   func foo()
   func bar() -> Foo
 }
@@ -88,7 +88,7 @@
   func bar() -> Bar? { return nil }
 }
 
-struct P6Conformer : P6 { // expected-error {{does not conform}}
+struct P6Conformer : P6 { // expected-error 2 {{does not conform}}
   func foo() {}
 }