lib/AST/GenericEnvironment.cpp - third_party/swift - Git at Google

 //===--- GenericEnvironment.cpp - GenericEnvironment AST ------------------===//
 //
 // 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 the GenericEnvironment class.
 //
 //===----------------------------------------------------------------------===//

 #include "swift/AST/GenericEnvironment.h"
 #include "swift/AST/ASTContext.h"
 #include "swift/AST/GenericSignatureBuilder.h"
 #include "swift/AST/ProtocolConformance.h"

 using namespace swift;

 GenericEnvironment::GenericEnvironment(GenericSignature *signature,
                                        GenericSignatureBuilder *builder)
   : Signature(signature), Builder(builder)
 {
   NumMappingsRecorded = 0;
   NumArchetypeToInterfaceMappings = 0;

   // Clear out the memory that holds the context types.
   std::uninitialized_fill(getContextTypes().begin(), getContextTypes().end(),
                           Type());
 }

 /// Compute the depth of the \c DeclContext chain.
 static unsigned declContextDepth(const DeclContext *dc) {
   unsigned depth = 0;
   while (auto parentDC = dc->getParent()) {
     ++depth;
     dc = parentDC;
   }

   return depth;
 }

 void GenericEnvironment::setOwningDeclContext(DeclContext *newOwningDC) {
   if (!OwningDC) {
     OwningDC = newOwningDC;
     return;
   }

   if (!newOwningDC || OwningDC == newOwningDC)
     return;

   // Find the least common ancestor context to be the owner.
   unsigned oldDepth = declContextDepth(OwningDC);
   unsigned newDepth = declContextDepth(newOwningDC);

   while (oldDepth > newDepth) {
     OwningDC = OwningDC->getParent();
     --oldDepth;
   }

   while (newDepth > oldDepth) {
     newOwningDC = newOwningDC->getParent();
     --newDepth;
   }

   while (OwningDC != newOwningDC) {
     OwningDC = OwningDC->getParent();
     newOwningDC = newOwningDC->getParent();
   }
 }

 void GenericEnvironment::addMapping(GenericParamKey key,
                                     Type contextType) {
   // Find the index into the parallel arrays of generic parameters and
   // context types.
   auto genericParams = Signature->getGenericParams();
   unsigned index = key.findIndexIn(genericParams);
   assert(genericParams[index] == key && "Bad generic parameter");

   // Add the mapping from the generic parameter to the context type.
   assert(getContextTypes()[index].isNull() && "Already recoded this mapping");
   getContextTypes()[index] = contextType;

   // If we mapped the generic parameter to an archetype, add it to the
   // reverse mapping.
   if (auto *archetype = contextType->getAs<ArchetypeType>()) {
     auto genericParam = genericParams[index];

     // Check whether we've already recorded a generic parameter for this
     // archetype. Note that we always perform a linear search, because we
     // won't have sorted the list yet.
     bool found = false;
     for (auto &mapping : getActiveArchetypeToInterfaceMappings()) {
       if (mapping.first != archetype) continue;

       // Multiple generic parameters map to the same archetype. If the
       // existing entry comes from a later generic parameter, replace it with
       // the earlier generic parameter. This gives us a deterministic reverse
       // mapping.
       auto otherGP = mapping.second->castTo<GenericTypeParamType>();
       if (GenericParamKey(genericParam) < GenericParamKey(otherGP))
         mapping.second = genericParam;
       found = true;
       break;
     }

     // If we haven't recorded a generic parameter for this archetype, do so now.
     if (!found) {
       void *ptr = getArchetypeToInterfaceMappingsBuffer().data()
                 + NumArchetypeToInterfaceMappings;
       new (ptr) ArchetypeToInterfaceMapping(archetype, genericParam);
       ++NumArchetypeToInterfaceMappings;
     }
   }

   // Note that we've recorded this mapping.
   ++NumMappingsRecorded;

   // If we've recorded all of the mappings, go ahead and sort the array of
   // archetype-to-interface-type mappings.
   if (NumMappingsRecorded == genericParams.size()) {
     llvm::array_pod_sort(getActiveArchetypeToInterfaceMappings().begin(),
                          getActiveArchetypeToInterfaceMappings().end(),
                          [](const ArchetypeToInterfaceMapping *lhs,
                             const ArchetypeToInterfaceMapping *rhs) -> int {
                            std::less<ArchetypeType *> compare;
                            if (compare(lhs->first, rhs->first)) return -1;
                            if (compare(rhs->first, lhs->first)) return 1;
                            return 0;
                          });
   }
 }

 Optional<Type> GenericEnvironment::getMappingIfPresent(
                                                     GenericParamKey key) const {
   // Find the index into the parallel arrays of generic parameters and
   // context types.
   auto genericParams = Signature->getGenericParams();
   unsigned index = key.findIndexIn(genericParams);
   assert(genericParams[index] == key && "Bad generic parameter");

   if (auto type = getContextTypes()[index])
     return type;

   return None;
 }

 bool GenericEnvironment::containsPrimaryArchetype(
                                               ArchetypeType *archetype) const {
   return static_cast<bool>(
                        QueryArchetypeToInterfaceSubstitutions(this)(archetype));
 }

 Type GenericEnvironment::mapTypeIntoContext(GenericEnvironment *env,
                                             Type type) {
   assert(!type->hasArchetype() && "already have a contextual type");

   if (!env)
     return type.substDependentTypesWithErrorTypes();

   return env->mapTypeIntoContext(type);
 }

 Type
 GenericEnvironment::mapTypeOutOfContext(GenericEnvironment *env,
                                         Type type) {
   assert(!type->hasTypeParameter() && "already have an interface type");

   if (!env)
     return type.substDependentTypesWithErrorTypes();

   return env->mapTypeOutOfContext(type);
 }

 Type GenericEnvironment::mapTypeOutOfContext(Type type) const {
   type = type.subst(QueryArchetypeToInterfaceSubstitutions(this),
                     MakeAbstractConformanceForGenericType(),
                     SubstFlags::AllowLoweredTypes);
   assert(!type->hasArchetype() && "not fully substituted");
   return type;
 }

 Type GenericEnvironment::QueryInterfaceTypeSubstitutions::operator()(
                                                 SubstitutableType *type) const {
   if (auto gp = type->getAs<GenericTypeParamType>()) {
     // Find the index into the parallel arrays of generic parameters and
     // context types.
     auto genericParams = self->Signature->getGenericParams();
     GenericParamKey key(gp);

     // Make sure that this generic parameter is from this environment.
     unsigned index = key.findIndexIn(genericParams);
     if (index == genericParams.size() || genericParams[index] != key)
       return Type();

     // If the context type isn't already known, lazily create it.
     Type contextType = self->getContextTypes()[index];
     if (!contextType) {
       assert(self->Builder && "Missing generic signature builder for lazy query");
       auto potentialArchetype = self->Builder->resolveArchetype(type);

       auto mutableSelf = const_cast<GenericEnvironment *>(self);
       contextType =
         potentialArchetype->getTypeInContext(*mutableSelf->Builder,
                                              mutableSelf);

       // FIXME: Redundant mapping from key -> index.
       if (self->getContextTypes()[index].isNull())
         mutableSelf->addMapping(key, contextType);
     }

     return contextType;
   }

   return Type();
 }

 Type GenericEnvironment::QueryArchetypeToInterfaceSubstitutions::operator()(
                                                 SubstitutableType *type) const {
   auto archetype = type->getAs<ArchetypeType>();
   if (!archetype) return Type();

   // If not all generic parameters have had their context types recorded,
   // perform a linear search.
   auto genericParams = self->Signature->getGenericParams();
   unsigned numGenericParams = genericParams.size();
   if (self->NumMappingsRecorded < numGenericParams) {
     // Search through all of the active archetype-to-interface mappings.
     for (auto &mapping : self->getActiveArchetypeToInterfaceMappings())
       if (mapping.first == archetype) return mapping.second;

     // We don't know if the archetype is from a different context or if we
     // simply haven't recorded it yet. Spin through all of the generic
     // parameters looking for one that provides this mapping.
     for (auto gp : genericParams) {
       // Map the generic parameter into our context. If we get back an
       // archetype that matches, we're done.
       auto gpArchetype = self->mapTypeIntoContext(gp)->getAs<ArchetypeType>();
       if (gpArchetype == archetype) return gp;
     }

     // We have checked all of the generic parameters and not found anything;
     // there is no substitution.
     return Type();
   }

   // All generic parameters have ad their context types recorded, which means
   // that the archetypes-to-interface-types array is sorted by address. Use a
   // binary search.
   struct MappingComparison {
     bool operator()(const ArchetypeToInterfaceMapping &lhs,
                     const ArchetypeType *rhs) const {
       std::less<const ArchetypeType *> compare;

       return compare(lhs.first, rhs);
     }

     bool operator()(const ArchetypeType *lhs,
                     const ArchetypeToInterfaceMapping &rhs) const {
       std::less<const ArchetypeType *> compare;

       return compare(lhs, rhs.first);
     }

     bool operator()(const ArchetypeToInterfaceMapping &lhs,
                     const ArchetypeToInterfaceMapping &rhs) const {
       std::less<const ArchetypeType *> compare;

       return compare(lhs.first, rhs.first);
     }
   } mappingComparison;

   auto mappings = self->getActiveArchetypeToInterfaceMappings();
   auto known = std::lower_bound(mappings.begin(), mappings.end(), archetype,
                                 mappingComparison);
   if (known != mappings.end() && known->first == archetype)
     return known->second;

   return Type();
 }

 Type GenericEnvironment::mapTypeIntoContext(
                                 Type type,
                                 LookupConformanceFn lookupConformance) const {
   assert(!type->hasOpenedExistential() &&
          "Opened existentials are special and so are you");

   Type result = type.subst(QueryInterfaceTypeSubstitutions(this),
                            lookupConformance,
                            (SubstFlags::AllowLoweredTypes|
                             SubstFlags::UseErrorType));
   assert((!result->hasTypeParameter() || result->hasError()) &&
          "not fully substituted");
   return result;

 }

 Type GenericEnvironment::mapTypeIntoContext(Type type) const {
   auto *sig = getGenericSignature();
   return mapTypeIntoContext(type, LookUpConformanceInSignature(*sig));
 }

 Type GenericEnvironment::mapTypeIntoContext(GenericTypeParamType *type) const {
   auto self = const_cast<GenericEnvironment *>(this);
   Type result = QueryInterfaceTypeSubstitutions(self)(type);
   if (!result)
     return ErrorType::get(type);
   return result;
 }

 GenericTypeParamType *GenericEnvironment::getSugaredType(
     GenericTypeParamType *type) const {
   for (auto *sugaredType : getGenericParams())
     if (sugaredType->isEqual(type))
       return sugaredType;

   llvm_unreachable("missing generic parameter");
 }

 Type GenericEnvironment::getSugaredType(Type type) const {
   if (!type->hasTypeParameter())
     return type;

   return type.transform([this](Type Ty) -> Type {
     if (auto GP = dyn_cast<GenericTypeParamType>(Ty.getPointer())) {
       return Type(getSugaredType(GP));
     }
     return Ty;
   });
 }

 SubstitutionList
 GenericEnvironment::getForwardingSubstitutions() const {
   SmallVector<Substitution, 4> result;
   getGenericSignature()->getSubstitutions(QueryInterfaceTypeSubstitutions(this),
                                           MakeAbstractConformanceForGenericType(),
                                           result);
   return getGenericSignature()->getASTContext().AllocateCopy(result);
 }

 void GenericEnvironment::populateParentMap(SubstitutionMap &subMap) const {
   for (auto reqt : getGenericSignature()->getRequirements()) {
     if (reqt.getKind() != RequirementKind::SameType)
       continue;

     auto first = reqt.getFirstType();
     auto second = reqt.getSecondType();

     auto archetype = first.subst(
         QueryInterfaceTypeSubstitutions(this),
         MakeAbstractConformanceForGenericType())
       ->getAs<ArchetypeType>();
     if (!archetype)
       continue;

 #ifndef NDEBUG
     auto secondArchetype = second.subst(
         QueryInterfaceTypeSubstitutions(this),
         MakeAbstractConformanceForGenericType())
       ->getAs<ArchetypeType>();
     assert(secondArchetype == archetype);
 #endif

     if (auto *firstMemTy = first->getAs<DependentMemberType>()) {
       auto parent = firstMemTy->getBase().subst(
         QueryInterfaceTypeSubstitutions(this),
         MakeAbstractConformanceForGenericType())
           ->getAs<ArchetypeType>();
       if (parent && archetype->getParent() != parent) {
         subMap.addParent(CanType(archetype),
                          CanType(parent),
                          firstMemTy->getAssocType());
       }
     }

     if (auto *secondMemTy = second->getAs<DependentMemberType>()) {
       auto parent = secondMemTy->getBase().subst(
         QueryInterfaceTypeSubstitutions(this),
         MakeAbstractConformanceForGenericType())
           ->getAs<ArchetypeType>();
       if (parent && archetype->getParent() != parent) {
         subMap.addParent(CanType(archetype),
                          CanType(parent),
                          secondMemTy->getAssocType());
       }
     }
   }
 }

 SubstitutionMap GenericEnvironment::
 getSubstitutionMap(SubstitutionList subs) const {
   SubstitutionMap result;

   getGenericSignature()->enumeratePairedRequirements(
     [&](Type depTy, ArrayRef<Requirement> reqts) -> bool {
       // Map the interface type to a context type.
       auto contextTy = depTy.subst(QueryInterfaceTypeSubstitutions(this),
                                    MakeAbstractConformanceForGenericType());

       auto sub = subs.front();
       subs = subs.slice(1);

       // Record the replacement type and its conformances.
       if (auto *archetype = contextTy->getAs<ArchetypeType>()) {
         result.addSubstitution(CanArchetypeType(archetype), sub.getReplacement());
         assert(reqts.size() == sub.getConformances().size());
         for (auto conformance : sub.getConformances())
           result.addConformance(CanType(archetype), conformance);
         return false;
       }

       assert(contextTy->hasError());
       return false;
     });

   assert(subs.empty() && "did not use all substitutions?!");

   populateParentMap(result);
   return result;
 }

 SubstitutionMap
 GenericEnvironment::
 getSubstitutionMap(TypeSubstitutionFn subs,
                    GenericSignature::LookupConformanceFn lookupConformance) const {
   SubstitutionMap subMap;

   getGenericSignature()->enumeratePairedRequirements(
     [&](Type depTy, ArrayRef<Requirement> reqs) -> bool {

       // Map the interface type to a context type.
       auto contextTy = depTy.subst(QueryInterfaceTypeSubstitutions(this),
                                    MakeAbstractConformanceForGenericType());

       // Compute the replacement type.
       Type currentReplacement = contextTy.subst(subs, lookupConformance,
                                                 SubstFlags::UseErrorType);
       if (auto archetypeTy = contextTy->getAs<ArchetypeType>()) {
         subMap.addSubstitution(CanArchetypeType(archetypeTy),
                                currentReplacement);

         // Collect the conformances.
         for (auto req: reqs) {
           assert(req.getKind() == RequirementKind::Conformance);
           auto protoType = req.getSecondType()->castTo<ProtocolType>();
           auto conformance = lookupConformance(CanArchetypeType(archetypeTy),
                                                currentReplacement,
                                                protoType);
           if (conformance)
             subMap.addConformance(CanArchetypeType(archetypeTy), *conformance);
         }
       }

       return false;
     });

   populateParentMap(subMap);
   return subMap;
 }
	//===--- GenericEnvironment.cpp - GenericEnvironment AST ------------------===//
	//
	// 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 the GenericEnvironment class.
	//
	//===----------------------------------------------------------------------===//

	#include "swift/AST/GenericEnvironment.h"
	#include "swift/AST/ASTContext.h"
	#include "swift/AST/GenericSignatureBuilder.h"
	#include "swift/AST/ProtocolConformance.h"

	using namespace swift;

	GenericEnvironment::GenericEnvironment(GenericSignature *signature,
	GenericSignatureBuilder *builder)
	: Signature(signature), Builder(builder)
	{
	NumMappingsRecorded = 0;
	NumArchetypeToInterfaceMappings = 0;

	// Clear out the memory that holds the context types.
	std::uninitialized_fill(getContextTypes().begin(), getContextTypes().end(),
	Type());
	}

	/// Compute the depth of the \c DeclContext chain.
	static unsigned declContextDepth(const DeclContext *dc) {
	unsigned depth = 0;
	while (auto parentDC = dc->getParent()) {
	++depth;
	dc = parentDC;
	}

	return depth;
	}

	void GenericEnvironment::setOwningDeclContext(DeclContext *newOwningDC) {
	if (!OwningDC) {
	OwningDC = newOwningDC;
	return;
	}

	if (!newOwningDC \|\| OwningDC == newOwningDC)
	return;

	// Find the least common ancestor context to be the owner.
	unsigned oldDepth = declContextDepth(OwningDC);
	unsigned newDepth = declContextDepth(newOwningDC);

	while (oldDepth > newDepth) {
	OwningDC = OwningDC->getParent();
	--oldDepth;
	}

	while (newDepth > oldDepth) {
	newOwningDC = newOwningDC->getParent();
	--newDepth;
	}

	while (OwningDC != newOwningDC) {
	OwningDC = OwningDC->getParent();
	newOwningDC = newOwningDC->getParent();
	}
	}

	void GenericEnvironment::addMapping(GenericParamKey key,
	Type contextType) {
	// Find the index into the parallel arrays of generic parameters and
	// context types.
	auto genericParams = Signature->getGenericParams();
	unsigned index = key.findIndexIn(genericParams);
	assert(genericParams[index] == key && "Bad generic parameter");

	// Add the mapping from the generic parameter to the context type.
	assert(getContextTypes()[index].isNull() && "Already recoded this mapping");
	getContextTypes()[index] = contextType;

	// If we mapped the generic parameter to an archetype, add it to the
	// reverse mapping.
	if (auto *archetype = contextType->getAs<ArchetypeType>()) {
	auto genericParam = genericParams[index];

	// Check whether we've already recorded a generic parameter for this
	// archetype. Note that we always perform a linear search, because we
	// won't have sorted the list yet.
	bool found = false;
	for (auto &mapping : getActiveArchetypeToInterfaceMappings()) {
	if (mapping.first != archetype) continue;

	// Multiple generic parameters map to the same archetype. If the
	// existing entry comes from a later generic parameter, replace it with
	// the earlier generic parameter. This gives us a deterministic reverse
	// mapping.
	auto otherGP = mapping.second->castTo<GenericTypeParamType>();
	if (GenericParamKey(genericParam) < GenericParamKey(otherGP))
	mapping.second = genericParam;
	found = true;
	break;
	}

	// If we haven't recorded a generic parameter for this archetype, do so now.
	if (!found) {
	void *ptr = getArchetypeToInterfaceMappingsBuffer().data()
	+ NumArchetypeToInterfaceMappings;
	new (ptr) ArchetypeToInterfaceMapping(archetype, genericParam);
	++NumArchetypeToInterfaceMappings;
	}
	}

	// Note that we've recorded this mapping.
	++NumMappingsRecorded;

	// If we've recorded all of the mappings, go ahead and sort the array of
	// archetype-to-interface-type mappings.
	if (NumMappingsRecorded == genericParams.size()) {
	llvm::array_pod_sort(getActiveArchetypeToInterfaceMappings().begin(),
	getActiveArchetypeToInterfaceMappings().end(),
	[](const ArchetypeToInterfaceMapping *lhs,
	const ArchetypeToInterfaceMapping *rhs) -> int {
	std::less<ArchetypeType *> compare;
	if (compare(lhs->first, rhs->first)) return -1;
	if (compare(rhs->first, lhs->first)) return 1;
	return 0;
	});
	}
	}

	Optional<Type> GenericEnvironment::getMappingIfPresent(
	GenericParamKey key) const {
	// Find the index into the parallel arrays of generic parameters and
	// context types.
	auto genericParams = Signature->getGenericParams();
	unsigned index = key.findIndexIn(genericParams);
	assert(genericParams[index] == key && "Bad generic parameter");

	if (auto type = getContextTypes()[index])
	return type;

	return None;
	}

	bool GenericEnvironment::containsPrimaryArchetype(
	ArchetypeType *archetype) const {
	return static_cast<bool>(
	QueryArchetypeToInterfaceSubstitutions(this)(archetype));
	}

	Type GenericEnvironment::mapTypeIntoContext(GenericEnvironment *env,
	Type type) {
	assert(!type->hasArchetype() && "already have a contextual type");

	if (!env)
	return type.substDependentTypesWithErrorTypes();

	return env->mapTypeIntoContext(type);
	}

	Type
	GenericEnvironment::mapTypeOutOfContext(GenericEnvironment *env,
	Type type) {
	assert(!type->hasTypeParameter() && "already have an interface type");

	if (!env)
	return type.substDependentTypesWithErrorTypes();

	return env->mapTypeOutOfContext(type);
	}

	Type GenericEnvironment::mapTypeOutOfContext(Type type) const {
	type = type.subst(QueryArchetypeToInterfaceSubstitutions(this),
	MakeAbstractConformanceForGenericType(),
	SubstFlags::AllowLoweredTypes);
	assert(!type->hasArchetype() && "not fully substituted");
	return type;
	}

	Type GenericEnvironment::QueryInterfaceTypeSubstitutions::operator()(
	SubstitutableType *type) const {
	if (auto gp = type->getAs<GenericTypeParamType>()) {
	// Find the index into the parallel arrays of generic parameters and
	// context types.
	auto genericParams = self->Signature->getGenericParams();
	GenericParamKey key(gp);

	// Make sure that this generic parameter is from this environment.
	unsigned index = key.findIndexIn(genericParams);
	if (index == genericParams.size() \|\| genericParams[index] != key)
	return Type();

	// If the context type isn't already known, lazily create it.
	Type contextType = self->getContextTypes()[index];
	if (!contextType) {
	assert(self->Builder && "Missing generic signature builder for lazy query");
	auto potentialArchetype = self->Builder->resolveArchetype(type);

	auto mutableSelf = const_cast<GenericEnvironment *>(self);
	contextType =
	potentialArchetype->getTypeInContext(*mutableSelf->Builder,
	mutableSelf);

	// FIXME: Redundant mapping from key -> index.
	if (self->getContextTypes()[index].isNull())
	mutableSelf->addMapping(key, contextType);
	}

	return contextType;
	}

	return Type();
	}

	Type GenericEnvironment::QueryArchetypeToInterfaceSubstitutions::operator()(
	SubstitutableType *type) const {
	auto archetype = type->getAs<ArchetypeType>();
	if (!archetype) return Type();

	// If not all generic parameters have had their context types recorded,
	// perform a linear search.
	auto genericParams = self->Signature->getGenericParams();
	unsigned numGenericParams = genericParams.size();
	if (self->NumMappingsRecorded < numGenericParams) {
	// Search through all of the active archetype-to-interface mappings.
	for (auto &mapping : self->getActiveArchetypeToInterfaceMappings())
	if (mapping.first == archetype) return mapping.second;

	// We don't know if the archetype is from a different context or if we
	// simply haven't recorded it yet. Spin through all of the generic
	// parameters looking for one that provides this mapping.
	for (auto gp : genericParams) {
	// Map the generic parameter into our context. If we get back an
	// archetype that matches, we're done.
	auto gpArchetype = self->mapTypeIntoContext(gp)->getAs<ArchetypeType>();
	if (gpArchetype == archetype) return gp;
	}

	// We have checked all of the generic parameters and not found anything;
	// there is no substitution.
	return Type();
	}

	// All generic parameters have ad their context types recorded, which means
	// that the archetypes-to-interface-types array is sorted by address. Use a
	// binary search.
	struct MappingComparison {
	bool operator()(const ArchetypeToInterfaceMapping &lhs,
	const ArchetypeType *rhs) const {
	std::less<const ArchetypeType *> compare;

	return compare(lhs.first, rhs);
	}

	bool operator()(const ArchetypeType *lhs,
	const ArchetypeToInterfaceMapping &rhs) const {
	std::less<const ArchetypeType *> compare;

	return compare(lhs, rhs.first);
	}

	bool operator()(const ArchetypeToInterfaceMapping &lhs,
	const ArchetypeToInterfaceMapping &rhs) const {
	std::less<const ArchetypeType *> compare;

	return compare(lhs.first, rhs.first);
	}
	} mappingComparison;

	auto mappings = self->getActiveArchetypeToInterfaceMappings();
	auto known = std::lower_bound(mappings.begin(), mappings.end(), archetype,
	mappingComparison);
	if (known != mappings.end() && known->first == archetype)
	return known->second;

	return Type();
	}

	Type GenericEnvironment::mapTypeIntoContext(
	Type type,
	LookupConformanceFn lookupConformance) const {
	assert(!type->hasOpenedExistential() &&
	"Opened existentials are special and so are you");

	Type result = type.subst(QueryInterfaceTypeSubstitutions(this),
	lookupConformance,
	(SubstFlags::AllowLoweredTypes\|
	SubstFlags::UseErrorType));
	assert((!result->hasTypeParameter() \|\| result->hasError()) &&
	"not fully substituted");
	return result;

	}

	Type GenericEnvironment::mapTypeIntoContext(Type type) const {
	auto *sig = getGenericSignature();
	return mapTypeIntoContext(type, LookUpConformanceInSignature(*sig));
	}

	Type GenericEnvironment::mapTypeIntoContext(GenericTypeParamType *type) const {
	auto self = const_cast<GenericEnvironment *>(this);
	Type result = QueryInterfaceTypeSubstitutions(self)(type);
	if (!result)
	return ErrorType::get(type);
	return result;
	}

	GenericTypeParamType *GenericEnvironment::getSugaredType(
	GenericTypeParamType *type) const {
	for (auto *sugaredType : getGenericParams())
	if (sugaredType->isEqual(type))
	return sugaredType;

	llvm_unreachable("missing generic parameter");
	}

	Type GenericEnvironment::getSugaredType(Type type) const {
	if (!type->hasTypeParameter())
	return type;

	return type.transform([this](Type Ty) -> Type {
	if (auto GP = dyn_cast<GenericTypeParamType>(Ty.getPointer())) {
	return Type(getSugaredType(GP));
	}
	return Ty;
	});
	}

	SubstitutionList
	GenericEnvironment::getForwardingSubstitutions() const {
	SmallVector<Substitution, 4> result;
	getGenericSignature()->getSubstitutions(QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType(),
	result);
	return getGenericSignature()->getASTContext().AllocateCopy(result);
	}

	void GenericEnvironment::populateParentMap(SubstitutionMap &subMap) const {
	for (auto reqt : getGenericSignature()->getRequirements()) {
	if (reqt.getKind() != RequirementKind::SameType)
	continue;

	auto first = reqt.getFirstType();
	auto second = reqt.getSecondType();

	auto archetype = first.subst(
	QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType())
	->getAs<ArchetypeType>();
	if (!archetype)
	continue;

	#ifndef NDEBUG
	auto secondArchetype = second.subst(
	QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType())
	->getAs<ArchetypeType>();
	assert(secondArchetype == archetype);
	#endif

	if (auto *firstMemTy = first->getAs<DependentMemberType>()) {
	auto parent = firstMemTy->getBase().subst(
	QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType())
	->getAs<ArchetypeType>();
	if (parent && archetype->getParent() != parent) {
	subMap.addParent(CanType(archetype),
	CanType(parent),
	firstMemTy->getAssocType());
	}
	}

	if (auto *secondMemTy = second->getAs<DependentMemberType>()) {
	auto parent = secondMemTy->getBase().subst(
	QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType())
	->getAs<ArchetypeType>();
	if (parent && archetype->getParent() != parent) {
	subMap.addParent(CanType(archetype),
	CanType(parent),
	secondMemTy->getAssocType());
	}
	}
	}
	}

	SubstitutionMap GenericEnvironment::
	getSubstitutionMap(SubstitutionList subs) const {
	SubstitutionMap result;

	getGenericSignature()->enumeratePairedRequirements(
	[&](Type depTy, ArrayRef<Requirement> reqts) -> bool {
	// Map the interface type to a context type.
	auto contextTy = depTy.subst(QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType());

	auto sub = subs.front();
	subs = subs.slice(1);

	// Record the replacement type and its conformances.
	if (auto *archetype = contextTy->getAs<ArchetypeType>()) {
	result.addSubstitution(CanArchetypeType(archetype), sub.getReplacement());
	assert(reqts.size() == sub.getConformances().size());
	for (auto conformance : sub.getConformances())
	result.addConformance(CanType(archetype), conformance);
	return false;
	}

	assert(contextTy->hasError());
	return false;
	});

	assert(subs.empty() && "did not use all substitutions?!");

	populateParentMap(result);
	return result;
	}

	SubstitutionMap
	GenericEnvironment::
	getSubstitutionMap(TypeSubstitutionFn subs,
	GenericSignature::LookupConformanceFn lookupConformance) const {
	SubstitutionMap subMap;

	getGenericSignature()->enumeratePairedRequirements(
	[&](Type depTy, ArrayRef<Requirement> reqs) -> bool {

	// Map the interface type to a context type.
	auto contextTy = depTy.subst(QueryInterfaceTypeSubstitutions(this),
	MakeAbstractConformanceForGenericType());

	// Compute the replacement type.
	Type currentReplacement = contextTy.subst(subs, lookupConformance,
	SubstFlags::UseErrorType);
	if (auto archetypeTy = contextTy->getAs<ArchetypeType>()) {
	subMap.addSubstitution(CanArchetypeType(archetypeTy),
	currentReplacement);

	// Collect the conformances.
	for (auto req: reqs) {
	assert(req.getKind() == RequirementKind::Conformance);
	auto protoType = req.getSecondType()->castTo<ProtocolType>();
	auto conformance = lookupConformance(CanArchetypeType(archetypeTy),
	currentReplacement,
	protoType);
	if (conformance)
	subMap.addConformance(CanArchetypeType(archetypeTy), *conformance);
	}
	}

	return false;
	});

	populateParentMap(subMap);
	return subMap;
	}