<commit_before>//===--- ConstraintSystem.cpp - Constraint-based Type Checking ------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file implements the constraint-based type checker, anchored by the
// \c ConstraintSystem class, which provides type checking and type
// inference for expressions.
//
//===----------------------------------------------------------------------===//
#include "ConstraintSystem.h"
#include "ConstraintGraph.h"
#include "swift/AST/ArchetypeBuilder.h"

using namespace swift;
using namespace constraints;

ConstraintSystem::ConstraintSystem(TypeChecker &tc, DeclContext *dc)
  : TC(tc), DC(dc), Arena(tc.Context, Allocator),
    CG(*new ConstraintGraph(*this))
{
  assert(DC && "context required");
}

ConstraintSystem::~ConstraintSystem() {
  delete &CG;
}

bool ConstraintSystem::hasFreeTypeVariables() {
  // Look for any free type variables.
  for (auto tv : TypeVariables) {
    if (!tv->getImpl().hasRepresentativeOrFixed()) {
      return true;
    }
  }
  
  return false;
}

void ConstraintSystem::addTypeVariable(TypeVariableType *typeVar) {
  TypeVariables.push_back(typeVar);
  
  // Notify the constraint graph.
  (void)CG[typeVar];
}

void ConstraintSystem::mergeEquivalenceClasses(TypeVariableType *typeVar1,
                                               TypeVariableType *typeVar2) {
  assert(typeVar1 == getRepresentative(typeVar1) &&
         "typeVar1 is not the representative");
  assert(typeVar2 == getRepresentative(typeVar2) &&
         "typeVar2 is not the representative");
  assert(typeVar1 != typeVar2 && "cannot merge type with itself");
  typeVar1->getImpl().mergeEquivalenceClasses(typeVar2, getSavedBindings());

  // Merge nodes in the constraint graph.
  CG.mergeNodes(typeVar1, typeVar2);
  addTypeVariableConstraintsToWorkList(typeVar1);
}

void ConstraintSystem::assignFixedType(TypeVariableType *typeVar, Type type,
                                       bool updateState) {
  typeVar->getImpl().assignFixedType(type, getSavedBindings());

  if (!updateState)
    return;

  if (!type->is<TypeVariableType>()) {
    // If this type variable represents a literal, check whether we picked the
    // default literal type. First, find the corresponding protocol.
    ProtocolDecl *literalProtocol = nullptr;
    // If we have the constraint graph, we can check all type variables in
    // the equivalence class. This is the More Correct path.
    // FIXME: Eliminate the less-correct path.
    auto typeVarRep = getRepresentative(typeVar);
    for (auto tv : CG[typeVarRep].getEquivalenceClass()) {
      auto locator = tv->getImpl().getLocator();
      if (!locator || !locator->getPath().empty())
        continue;

      auto anchor = locator->getAnchor();
      if (!anchor)
        continue;

      literalProtocol = TC.getLiteralProtocol(anchor);
      if (literalProtocol)
        break;
    }

    // If the protocol has a default type, check it.
    if (literalProtocol) {
      if (auto defaultType = TC.getDefaultType(literalProtocol, DC)) {
        // Check whether the nominal types match. This makes sure that we
        // properly handle Slice vs. Slice<T>.
        if (defaultType->getAnyNominal() != type->getAnyNominal())
          increaseScore(SK_NonDefaultLiteral);
      }
    }
  }

  // Notify the constraint graph.
  CG.bindTypeVariable(typeVar, type);
  addTypeVariableConstraintsToWorkList(typeVar);
}

void ConstraintSystem::addTypeVariableConstraintsToWorkList(
       TypeVariableType *typeVar) {
  // Gather the constraints affected by a change to this type variable.
  SmallVector<Constraint *, 8> constraints;
  CG.gatherConstraints(typeVar, constraints);

  // Add any constraints that aren't already active to the worklist.
  for (auto constraint : constraints) {
    if (!constraint->isActive()) {
      ActiveConstraints.splice(ActiveConstraints.end(),
                               InactiveConstraints, constraint);
      constraint->setActive(true);
    }
  }
}

/// Retrieve a uniqued selector ID for the given declaration.
static std::pair<unsigned, CanType>
getDynamicResultSignature(ValueDecl *decl,
                          llvm::StringMap<unsigned> &selectors) {
  llvm::SmallString<32> buffer;

  StringRef selector;
  Type type;
  if (auto func = dyn_cast<FuncDecl>(decl)) {
    // Handle functions.
    selector = func->getObjCSelector(buffer);
    type = decl->getType()->castTo<AnyFunctionType>()->getResult();

    // Append a '+' for static methods, '-' for instance methods. This
    // distinguishes methods with a given name from properties that
    // might have the same name.
    if (func->isStatic()) {
      buffer += '+';
    } else {
      buffer += '-';
    }
    selector = buffer.str();
  } else if (auto var = dyn_cast<VarDecl>(decl)) {
    // Handle properties. Only the getter matters.
    selector = var->getObjCGetterSelector(buffer);
    type = decl->getType();
  } else if (auto ctor = dyn_cast<ConstructorDecl>(decl)) {
    // Handle constructors.
    selector = ctor->getObjCSelector(buffer);
    type = decl->getType()->castTo<AnyFunctionType>()->getResult();
  } else if (auto subscript = dyn_cast<SubscriptDecl>(decl)) {
    selector = subscript->getObjCGetterSelector();
    type = subscript->getType();
  } else {
    llvm_unreachable("Dynamic lookup found a non-[objc] result");
  }

  // Look for this selector in the table. If we find it, we're done.
  auto known = selectors.find(selector);
  if (known != selectors.end())
    return { known->second, type->getCanonicalType() };

  // Add this selector to the table.
  unsigned result = selectors.size();
  selectors[selector] = result;
  return { result, type->getCanonicalType() };
}

LookupResult &ConstraintSystem::lookupMember(Type base, Identifier name) {
  base = base->getCanonicalType();

  // Check whether we've already performed this lookup.
  auto knownMember = MemberLookups.find({base, name});
  if (knownMember != MemberLookups.end())
    return *knownMember->second;

  // Lookup the member.
  MemberLookups[{base, name}] = Nothing;
  auto lookup = TC.lookupMember(base, name, DC);
  auto &result = MemberLookups[{base, name}];
  result = std::move(lookup);

  // If we aren't performing dynamic lookup, we're done.
  auto instanceTy = base->getRValueType();
  if (auto metaTy = instanceTy->getAs<MetatypeType>())
    instanceTy = metaTy->getInstanceType();
  auto protoTy = instanceTy->getAs<ProtocolType>();
  if (!*result ||
      !protoTy ||
      !protoTy->getDecl()->isSpecificProtocol(
                             KnownProtocolKind::DynamicLookup))
    return *result;

  // We are performing dynamic lookup. Filter out redundant results early.
  llvm::DenseSet<std::pair<unsigned, CanType>> known;
  llvm::StringMap<unsigned> selectors;
  result->filter([&](ValueDecl *decl) -> bool {
    return known.insert(getDynamicResultSignature(decl, selectors)).second;
  });

  return *result;
}

ArrayRef<Type> ConstraintSystem::getAlternativeLiteralTypes(
                  KnownProtocolKind kind) {
  unsigned index;

  switch (kind) {
#define PROTOCOL(Protocol) \
  case KnownProtocolKind::Protocol: llvm_unreachable("Not a literal protocol");
#define LITERAL_CONVERTIBLE_PROTOCOL(Protocol)
#include "swift/AST/KnownProtocols.def"

  case KnownProtocolKind::ArrayLiteralConvertible:
    index = 0;
    break;

  case KnownProtocolKind::CharacterLiteralConvertible:
    index = 1;
    break;

  case KnownProtocolKind::DictionaryLiteralConvertible:
    index = 2;
    break;

  case KnownProtocolKind::FloatLiteralConvertible:
    index = 3;
    break;

  case KnownProtocolKind::IntegerLiteralConvertible:
    index = 4;
    break;

  case KnownProtocolKind::StringInterpolationConvertible:
    index = 5;
    break;

  case KnownProtocolKind::StringLiteralConvertible:
    index = 6;
    break;
  }

  // If we already looked for alternative literal types, return those results.
  if (AlternativeLiteralTypes[index])
    return *AlternativeLiteralTypes[index];

  // Collect all of the types that conform to the given literal protocol.
  SmallVector<Type, 4> types;
  for (auto decl : TC.Context.getTypesThatConformTo(kind)) {
    Type type;
    if (auto nominal = dyn_cast<NominalTypeDecl>(decl))
      type = nominal->getDeclaredTypeOfContext();
    else
      type = cast<ExtensionDecl>(decl)->getDeclaredTypeOfContext();

    types.push_back(type);
  }

  AlternativeLiteralTypes[index] = allocateCopy(types);
  return *AlternativeLiteralTypes[index];
}

ConstraintLocator *ConstraintSystem::getConstraintLocator(
                     Expr *anchor,
                     ArrayRef<ConstraintLocator::PathElement> path) {
  // Check whether a locator with this anchor + path already exists.
  llvm::FoldingSetNodeID id;
  ConstraintLocator::Profile(id, anchor, path);
  void *insertPos = nullptr;
  auto locator = ConstraintLocators.FindNodeOrInsertPos(id, insertPos);
  if (locator)
    return locator;

  // Allocate a new locator and add it to the set.
  locator = ConstraintLocator::create(getAllocator(), anchor, path);
  ConstraintLocators.InsertNode(locator, insertPos);
  return locator;
}

ConstraintLocator *ConstraintSystem::getConstraintLocator(
                     const ConstraintLocatorBuilder &builder) {
  // If the builder has an empty path, just extract its base locator.
  if (builder.hasEmptyPath()) {
    return builder.getBaseLocator();
  }

  // We have to build a new locator. Extract the paths from the builder.
  SmallVector<LocatorPathElt, 4> path;
  Expr *anchor = builder.getLocatorParts(path);
  if (!anchor)
    return nullptr;

  return getConstraintLocator(anchor, path);
}

bool ConstraintSystem::addConstraint(Constraint *constraint,
                                     bool isExternallySolved,
                                     bool simplifyExisting) {
  switch (simplifyConstraint(*constraint)) {
  case SolutionKind::Error:
    if (!failedConstraint) {
      failedConstraint = constraint;
    }

    if (solverState) {
      solverState->retiredConstraints.push_front(constraint);
      if (!simplifyExisting) {
        solverState->generatedConstraints.push_back(constraint);
      }
    }

    return false;

  case SolutionKind::Solved:
    // This constraint has already been solved; there is nothing more
    // to do.
    // Record solved constraint.
    if (solverState) {
      solverState->retiredConstraints.push_front(constraint);
      if (!simplifyExisting)
        solverState->generatedConstraints.push_back(constraint);
    }

    // Remove the constraint from the constraint graph.
    if (simplifyExisting)
      CG.removeConstraint(constraint);
    
    return true;

  case SolutionKind::Unsolved:
    // We couldn't solve this constraint; add it to the pile.
    if (!isExternallySolved) {
      InactiveConstraints.push_back(constraint);        
    }

    // Add this constraint to the constraint graph.
    if (!simplifyExisting)
      CG.addConstraint(constraint);

    if (!simplifyExisting && solverState) {
      solverState->generatedConstraints.push_back(constraint);
    }

    return false;
  }
}

/// Check whether this is the depth 0, index 0 generic parameter, which is
/// used for the 'Self' type of a protocol.
static bool isProtocolSelfType(Type type) {
  auto gp = type->getAs<GenericTypeParamType>();
  if (!gp)
    return false;

  return gp->getDepth() == 0 && gp->getIndex() == 0;
}

namespace {
  /// Function object that retrieves a type variable corresponding to the
  /// given dependent type.
  class GetTypeVariable {
    ConstraintSystem &CS;
    DependentTypeOpener *Opener;

    /// The type variables introduced for (base type, associated type) pairs.
    llvm::DenseMap<std::pair<CanType, AssociatedTypeDecl *>, TypeVariableType *>
      MemberReplacements;

  public:
    GetTypeVariable(ConstraintSystem &cs, DependentTypeOpener *opener)
      : CS(cs), Opener(opener) { }

    TypeVariableType *operator()(Type base, AssociatedTypeDecl *member) {
      auto known = MemberReplacements.find({base->getCanonicalType(), member});
      if (known != MemberReplacements.end())
        return known->second;

      auto baseTypeVar = base->castTo<TypeVariableType>();
      auto archetype = baseTypeVar->getImpl().getArchetype()
                         ->getNestedType(member->getName());
      auto tv = CS.createTypeVariable(CS.getConstraintLocator(
                                        (Expr *)nullptr,
                                        LocatorPathElt(archetype)),
                                      TVO_PrefersSubtypeBinding);
      MemberReplacements[{base->getCanonicalType(), member}] = tv;

      // Determine whether we should bind the new type variable as a
      // member of the base type variable, or let it float.
      Type replacementType;
      bool shouldBindMember = true;
      if (Opener) {
        shouldBindMember = Opener->shouldBindAssociatedType(base, baseTypeVar,
                                                            member, tv,
                                                            replacementType);
      }

      // Bind the member's type variable as a type member of the base,
      // if needed.
      if (shouldBindMember)
        CS.addTypeMemberConstraint(base, member->getName(), tv);

      // If we have a replacement type, bind the member's type
      // variable to it.
      if (replacementType)
        CS.addConstraint(ConstraintKind::Bind, tv, replacementType);

      // Add associated type constraints.
      // FIXME: Would be better to walk the requirements of the protocol
      // of which the associated type is a member.
      if (auto superclass = member->getSuperclass()) {
        CS.addConstraint(ConstraintKind::Subtype, tv, superclass);
      }

      for (auto proto : member->getArchetype()->getConformsTo()) {
        CS.addConstraint(ConstraintKind::ConformsTo, tv,
                         proto->getDeclaredType());
      }
      return tv;
    }
  };

  /// Function object that replaces all occurrences of archetypes and
  /// dependent types with type variables.
  class ReplaceDependentTypes {
    ConstraintSystem &cs;
    DeclContext *dc;
    bool skipProtocolSelfConstraint;
    DependentTypeOpener *opener;
    llvm::DenseMap<CanType, TypeVariableType *> &replacements;
    GetTypeVariable &getTypeVariable;

  public:
    ReplaceDependentTypes(
        ConstraintSystem &cs,
        DeclContext *dc,
        bool skipProtocolSelfConstraint,
        DependentTypeOpener *opener,
        llvm::DenseMap<CanType, TypeVariableType *> &replacements,
        GetTypeVariable &getTypeVariable)
      : cs(cs), dc(dc), skipProtocolSelfConstraint(skipProtocolSelfConstraint),
        opener(opener), replacements(replacements), 
        getTypeVariable(getTypeVariable) { }

    Type operator()(Type type) {
      assert(!type->is<PolymorphicFunctionType>() && "Shouldn't get here");

      // Replace archetypes with fresh type variables.
      if (auto archetype = type->getAs<ArchetypeType>()) {
        auto known = replacements.find(archetype->getCanonicalType());
        if (known != replacements.end())
          return known->second;

        return archetype;
      }

      // Replace a generic type parameter with its corresponding type variable.
      if (auto genericParam = type->getAs<GenericTypeParamType>()) {
        auto known = replacements.find(genericParam->getCanonicalType());
        assert(known != replacements.end());
        return known->second;
      }

      // Replace a dependent member with a fresh type variable and make it a
      // member of its base type.
      if (auto dependentMember = type->getAs<DependentMemberType>()) {
        // Check whether we've already dealt with this dependent member.
        auto known = replacements.find(dependentMember->getCanonicalType());
        if (known != replacements.end())
          return known->second;

        // Replace archetypes in the base type.
        auto base = (*this)(dependentMember->getBase());
        auto result = getTypeVariable(base, dependentMember->getAssocType());
        replacements[dependentMember->getCanonicalType()] = result;
        return result;
      }

      // Create type variables for all of the parameters in a generic function
      // type.
      if (auto genericFn = type->getAs<GenericFunctionType>()) {
        // Open up the generic parameters and requirements.
        cs.openGeneric(dc,
                       genericFn->getGenericParams(),
                       genericFn->getRequirements(),
                       skipProtocolSelfConstraint,
                       opener,
                       replacements);

        // Transform the input and output types.
        Type inputTy = genericFn->getInput().transform(*this);
        if (!inputTy)
          return Type();

        Type resultTy = genericFn->getResult().transform(*this);
        if (!resultTy)
          return Type();

        // Build the resulting (non-generic) function type.
        return FunctionType::get(inputTy, resultTy);
      }

      // Open up unbound generic types, turning them into bound generic
      // types with type variables for each parameter.
      if (auto unbound = type->getAs<UnboundGenericType>()) {
        auto parentTy = unbound->getParent();
        if (parentTy)
          parentTy = parentTy.transform(*this);

        auto unboundDecl = unbound->getDecl();

        // Open up the generic type.
        cs.openGeneric(unboundDecl,
                       unboundDecl->getGenericParamTypes(),
                       unboundDecl->getGenericRequirements(),
                       /*skipProtocolSelfConstraint=*/false,
                       opener,
                       replacements);

        // Map the generic parameters to their corresponding type variables.
        llvm::SmallVector<Type, 4> arguments;
        for (auto gp : unboundDecl->getGenericParamTypes()) {
          assert(replacements.count(gp->getCanonicalType()) && 
                 "Missing generic parameter?");
          arguments.push_back(replacements[gp->getCanonicalType()]);
        }
        return BoundGenericType::get(unboundDecl, parentTy, arguments);
      }
      
      return type;
    }
  };
}

Type ConstraintSystem::openType(
       Type startingType,
       llvm::DenseMap<CanType, TypeVariableType *> &replacements,
       DeclContext *dc,
       bool skipProtocolSelfConstraint,
       DependentTypeOpener *opener) {
  GetTypeVariable getTypeVariable{*this, opener};

  ReplaceDependentTypes replaceDependentTypes(*this, dc,
                                              skipProtocolSelfConstraint,
                                              opener,
                                              replacements, getTypeVariable);
  return startingType.transform(replaceDependentTypes);
}

Type ConstraintSystem::openBindingType(Type type, DeclContext *dc) {
  Type result = openType(type, dc);
  // FIXME: Better way to identify Slice<T>.
  if (auto boundStruct
        = dyn_cast<BoundGenericStructType>(result.getPointer())) {
    if (!boundStruct->getParent() &&
        boundStruct->getDecl()->getName().str() == "Array" &&
        boundStruct->getGenericArgs().size() == 1) {
      if (auto replacement = getTypeChecker().getArraySliceType(
                               SourceLoc(), boundStruct->getGenericArgs()[0])) {
        return replacement;
      }
    }
  }

  return result;
}

static Type getFixedTypeRecursiveHelper(ConstraintSystem &cs,
                                        TypeVariableType *typeVar,
                                        bool wantRValue) {
  while (auto fixed = cs.getFixedType(typeVar)) {
    if (wantRValue)
      fixed = fixed->getRValueType();

    typeVar = fixed->getAs<TypeVariableType>();
    if (!typeVar)
      return fixed;
  }
  return nullptr;
}

Type ConstraintSystem::getFixedTypeRecursive(Type type, 
                                             TypeVariableType *&typeVar,
                                             bool wantRValue) {
  if (wantRValue)
    type = type->getRValueType();

  auto desugar = type->getDesugaredType();
  typeVar = desugar->getAs<TypeVariableType>();
  if (typeVar) {
    if (auto fixed = getFixedTypeRecursiveHelper(*this, typeVar, wantRValue)) {
      type = fixed;
      typeVar = nullptr;
    }
  }
  return type;
}

std::pair<Type, Type>
ConstraintSystem::getTypeOfReference(ValueDecl *value,
                                     bool isTypeReference,
                                     bool isSpecialized,
                                     DependentTypeOpener *opener) {
  if (value->getDeclContext()->isTypeContext() && isa<FuncDecl>(value)) {
    // Unqualified lookup can find operator names within nominal types.
    auto func = cast<FuncDecl>(value);
    assert(func->isOperator() && "Lookup should only find operators");

    auto openedType = openType(func->getInterfaceType(), func, false, opener);
    auto openedFnType = openedType->castTo<FunctionType>();

    // The 'Self' type must be bound to an archetype.
    // FIXME: We eventually want to loosen this constraint, to allow us
    // to find operator functions both in classes and in protocols to which
    // a class conforms (if there's a default implementation).
    addArchetypeConstraint(openedFnType->getInput()->getRValueInstanceType());

    // The reference implicitly binds 'self'.
    return { openedType, openedFnType->getResult() };
  }

  // If we have a type declaration, resolve it within the current context.
  if (auto typeDecl = dyn_cast<TypeDecl>(value)) {
    // Resolve the reference to this type declaration in our current context.
    auto type = getTypeChecker().resolveTypeInContext(typeDecl, DC,
                                                      isSpecialized);
    if (!type)
      return { nullptr, nullptr };

    // Open the type.
    type = openType(type, value->getInnermostDeclContext(), false, opener);

    // If it's a type reference, we're done.
    if (isTypeReference)
      return { type, type };

    // If it's a value reference, refer to the metatype.
    type = MetatypeType::get(type, getASTContext());
    return { type, type };
  }

  // Determine the type of the value, opening up that type if necessary.
  Type valueType = TC.getUnopenedTypeOfReference(value, Type(), DC,
                                                 /*wantInterfaceType=*/true);

  // Adjust the type of the reference.
  valueType = openType(valueType,
                       value->getPotentialGenericDeclContext(),
                       /*skipProtocolSelfConstraint=*/false,
                       opener);
  return { valueType, valueType };
}

void ConstraintSystem::openGeneric(
       DeclContext *dc,
       ArrayRef<GenericTypeParamType *> params,
       ArrayRef<Requirement> requirements,
       bool skipProtocolSelfConstraint,
       DependentTypeOpener *opener,
       llvm::DenseMap<CanType, TypeVariableType *> &replacements) {

  // Create the type variables for the generic parameters.
  for (auto gp : params) {
    ArchetypeType *archetype = ArchetypeBuilder::mapTypeIntoContext(dc, gp)
                                 ->castTo<ArchetypeType>();
    auto typeVar = createTypeVariable(getConstraintLocator(
                                        (Expr *)nullptr,
                                        LocatorPathElt(archetype)),
                                      TVO_PrefersSubtypeBinding);
    replacements[gp->getCanonicalType()] = typeVar;

    // Note that we opened a generic parameter to a type variable.
    if (opener) {
      Type replacementType;
      opener->openedGenericParameter(gp, typeVar, replacementType);

      if (replacementType)
        addConstraint(ConstraintKind::Bind, typeVar, replacementType);
    }
  }

  GetTypeVariable getTypeVariable{*this, opener};
  ReplaceDependentTypes replaceDependentTypes(*this, dc,
                                              skipProtocolSelfConstraint,
                                              opener, replacements, 
                                              getTypeVariable);

  // Add the requirements as constraints.
  for (auto req : requirements) {
  switch (req.getKind()) {
    case RequirementKind::Conformance: {
      auto subjectTy = req.getFirstType().transform(replaceDependentTypes);
      if (auto proto = req.getSecondType()->getAs<ProtocolType>()) {
        if (!skipProtocolSelfConstraint ||
            !(isa<ProtocolDecl>(dc) || isa<ProtocolDecl>(dc->getParent())) ||
            !isProtocolSelfType(req.getFirstType())) {
          addConstraint(ConstraintKind::ConformsTo, subjectTy,
                        proto);
        }
      } else {
        addConstraint(ConstraintKind::Subtype, subjectTy,
                      req.getSecondType());
      }
      break;
    }

    case RequirementKind::SameType: {
      auto firstTy = req.getFirstType().transform(replaceDependentTypes);
      auto secondTy = req.getSecondType().transform(replaceDependentTypes);<commit_msg>Replace dependent types in constraints with their type variables.<commit_after>//===--- ConstraintSystem.cpp - Constraint-based Type Checking ------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file implements the constraint-based type checker, anchored by the
// \c ConstraintSystem class, which provides type checking and type
// inference for expressions.
//
//===----------------------------------------------------------------------===//
#include "ConstraintSystem.h"
#include "ConstraintGraph.h"
#include "swift/AST/ArchetypeBuilder.h"

using namespace swift;
using namespace constraints;

ConstraintSystem::ConstraintSystem(TypeChecker &tc, DeclContext *dc)
  : TC(tc), DC(dc), Arena(tc.Context, Allocator),
    CG(*new ConstraintGraph(*this))
{
  assert(DC && "context required");
}

ConstraintSystem::~ConstraintSystem() {
  delete &CG;
}

bool ConstraintSystem::hasFreeTypeVariables() {
  // Look for any free type variables.
  for (auto tv : TypeVariables) {
    if (!tv->getImpl().hasRepresentativeOrFixed()) {
      return true;
    }
  }
  
  return false;
}

void ConstraintSystem::addTypeVariable(TypeVariableType *typeVar) {
  TypeVariables.push_back(typeVar);
  
  // Notify the constraint graph.
  (void)CG[typeVar];
}

void ConstraintSystem::mergeEquivalenceClasses(TypeVariableType *typeVar1,
                                               TypeVariableType *typeVar2) {
  assert(typeVar1 == getRepresentative(typeVar1) &&
         "typeVar1 is not the representative");
  assert(typeVar2 == getRepresentative(typeVar2) &&
         "typeVar2 is not the representative");
  assert(typeVar1 != typeVar2 && "cannot merge type with itself");
  typeVar1->getImpl().mergeEquivalenceClasses(typeVar2, getSavedBindings());

  // Merge nodes in the constraint graph.
  CG.mergeNodes(typeVar1, typeVar2);
  addTypeVariableConstraintsToWorkList(typeVar1);
}

void ConstraintSystem::assignFixedType(TypeVariableType *typeVar, Type type,
                                       bool updateState) {
  typeVar->getImpl().assignFixedType(type, getSavedBindings());

  if (!updateState)
    return;

  if (!type->is<TypeVariableType>()) {
    // If this type variable represents a literal, check whether we picked the
    // default literal type. First, find the corresponding protocol.
    ProtocolDecl *literalProtocol = nullptr;
    // If we have the constraint graph, we can check all type variables in
    // the equivalence class. This is the More Correct path.
    // FIXME: Eliminate the less-correct path.
    auto typeVarRep = getRepresentative(typeVar);
    for (auto tv : CG[typeVarRep].getEquivalenceClass()) {
      auto locator = tv->getImpl().getLocator();
      if (!locator || !locator->getPath().empty())
        continue;

      auto anchor = locator->getAnchor();
      if (!anchor)
        continue;

      literalProtocol = TC.getLiteralProtocol(anchor);
      if (literalProtocol)
        break;
    }

    // If the protocol has a default type, check it.
    if (literalProtocol) {
      if (auto defaultType = TC.getDefaultType(literalProtocol, DC)) {
        // Check whether the nominal types match. This makes sure that we
        // properly handle Slice vs. Slice<T>.
        if (defaultType->getAnyNominal() != type->getAnyNominal())
          increaseScore(SK_NonDefaultLiteral);
      }
    }
  }

  // Notify the constraint graph.
  CG.bindTypeVariable(typeVar, type);
  addTypeVariableConstraintsToWorkList(typeVar);
}

void ConstraintSystem::addTypeVariableConstraintsToWorkList(
       TypeVariableType *typeVar) {
  // Gather the constraints affected by a change to this type variable.
  SmallVector<Constraint *, 8> constraints;
  CG.gatherConstraints(typeVar, constraints);

  // Add any constraints that aren't already active to the worklist.
  for (auto constraint : constraints) {
    if (!constraint->isActive()) {
      ActiveConstraints.splice(ActiveConstraints.end(),
                               InactiveConstraints, constraint);
      constraint->setActive(true);
    }
  }
}

/// Retrieve a uniqued selector ID for the given declaration.
static std::pair<unsigned, CanType>
getDynamicResultSignature(ValueDecl *decl,
                          llvm::StringMap<unsigned> &selectors) {
  llvm::SmallString<32> buffer;

  StringRef selector;
  Type type;
  if (auto func = dyn_cast<FuncDecl>(decl)) {
    // Handle functions.
    selector = func->getObjCSelector(buffer);
    type = decl->getType()->castTo<AnyFunctionType>()->getResult();

    // Append a '+' for static methods, '-' for instance methods. This
    // distinguishes methods with a given name from properties that
    // might have the same name.
    if (func->isStatic()) {
      buffer += '+';
    } else {
      buffer += '-';
    }
    selector = buffer.str();
  } else if (auto var = dyn_cast<VarDecl>(decl)) {
    // Handle properties. Only the getter matters.
    selector = var->getObjCGetterSelector(buffer);
    type = decl->getType();
  } else if (auto ctor = dyn_cast<ConstructorDecl>(decl)) {
    // Handle constructors.
    selector = ctor->getObjCSelector(buffer);
    type = decl->getType()->castTo<AnyFunctionType>()->getResult();
  } else if (auto subscript = dyn_cast<SubscriptDecl>(decl)) {
    selector = subscript->getObjCGetterSelector();
    type = subscript->getType();
  } else {
    llvm_unreachable("Dynamic lookup found a non-[objc] result");
  }

  // Look for this selector in the table. If we find it, we're done.
  auto known = selectors.find(selector);
  if (known != selectors.end())
    return { known->second, type->getCanonicalType() };

  // Add this selector to the table.
  unsigned result = selectors.size();
  selectors[selector] = result;
  return { result, type->getCanonicalType() };
}

LookupResult &ConstraintSystem::lookupMember(Type base, Identifier name) {
  base = base->getCanonicalType();

  // Check whether we've already performed this lookup.
  auto knownMember = MemberLookups.find({base, name});
  if (knownMember != MemberLookups.end())
    return *knownMember->second;

  // Lookup the member.
  MemberLookups[{base, name}] = Nothing;
  auto lookup = TC.lookupMember(base, name, DC);
  auto &result = MemberLookups[{base, name}];
  result = std::move(lookup);

  // If we aren't performing dynamic lookup, we're done.
  auto instanceTy = base->getRValueType();
  if (auto metaTy = instanceTy->getAs<MetatypeType>())
    instanceTy = metaTy->getInstanceType();
  auto protoTy = instanceTy->getAs<ProtocolType>();
  if (!*result ||
      !protoTy ||
      !protoTy->getDecl()->isSpecificProtocol(
                             KnownProtocolKind::DynamicLookup))
    return *result;

  // We are performing dynamic lookup. Filter out redundant results early.
  llvm::DenseSet<std::pair<unsigned, CanType>> known;
  llvm::StringMap<unsigned> selectors;
  result->filter([&](ValueDecl *decl) -> bool {
    return known.insert(getDynamicResultSignature(decl, selectors)).second;
  });

  return *result;
}

ArrayRef<Type> ConstraintSystem::getAlternativeLiteralTypes(
                  KnownProtocolKind kind) {
  unsigned index;

  switch (kind) {
#define PROTOCOL(Protocol) \
  case KnownProtocolKind::Protocol: llvm_unreachable("Not a literal protocol");
#define LITERAL_CONVERTIBLE_PROTOCOL(Protocol)
#include "swift/AST/KnownProtocols.def"

  case KnownProtocolKind::ArrayLiteralConvertible:
    index = 0;
    break;

  case KnownProtocolKind::CharacterLiteralConvertible:
    index = 1;
    break;

  case KnownProtocolKind::DictionaryLiteralConvertible:
    index = 2;
    break;

  case KnownProtocolKind::FloatLiteralConvertible:
    index = 3;
    break;

  case KnownProtocolKind::IntegerLiteralConvertible:
    index = 4;
    break;

  case KnownProtocolKind::StringInterpolationConvertible:
    index = 5;
    break;

  case KnownProtocolKind::StringLiteralConvertible:
    index = 6;
    break;
  }

  // If we already looked for alternative literal types, return those results.
  if (AlternativeLiteralTypes[index])
    return *AlternativeLiteralTypes[index];

  // Collect all of the types that conform to the given literal protocol.
  SmallVector<Type, 4> types;
  for (auto decl : TC.Context.getTypesThatConformTo(kind)) {
    Type type;
    if (auto nominal = dyn_cast<NominalTypeDecl>(decl))
      type = nominal->getDeclaredTypeOfContext();
    else
      type = cast<ExtensionDecl>(decl)->getDeclaredTypeOfContext();

    types.push_back(type);
  }

  AlternativeLiteralTypes[index] = allocateCopy(types);
  return *AlternativeLiteralTypes[index];
}

ConstraintLocator *ConstraintSystem::getConstraintLocator(
                     Expr *anchor,
                     ArrayRef<ConstraintLocator::PathElement> path) {
  // Check whether a locator with this anchor + path already exists.
  llvm::FoldingSetNodeID id;
  ConstraintLocator::Profile(id, anchor, path);
  void *insertPos = nullptr;
  auto locator = ConstraintLocators.FindNodeOrInsertPos(id, insertPos);
  if (locator)
    return locator;

  // Allocate a new locator and add it to the set.
  locator = ConstraintLocator::create(getAllocator(), anchor, path);
  ConstraintLocators.InsertNode(locator, insertPos);
  return locator;
}

ConstraintLocator *ConstraintSystem::getConstraintLocator(
                     const ConstraintLocatorBuilder &builder) {
  // If the builder has an empty path, just extract its base locator.
  if (builder.hasEmptyPath()) {
    return builder.getBaseLocator();
  }

  // We have to build a new locator. Extract the paths from the builder.
  SmallVector<LocatorPathElt, 4> path;
  Expr *anchor = builder.getLocatorParts(path);
  if (!anchor)
    return nullptr;

  return getConstraintLocator(anchor, path);
}

bool ConstraintSystem::addConstraint(Constraint *constraint,
                                     bool isExternallySolved,
                                     bool simplifyExisting) {
  switch (simplifyConstraint(*constraint)) {
  case SolutionKind::Error:
    if (!failedConstraint) {
      failedConstraint = constraint;
    }

    if (solverState) {
      solverState->retiredConstraints.push_front(constraint);
      if (!simplifyExisting) {
        solverState->generatedConstraints.push_back(constraint);
      }
    }

    return false;

  case SolutionKind::Solved:
    // This constraint has already been solved; there is nothing more
    // to do.
    // Record solved constraint.
    if (solverState) {
      solverState->retiredConstraints.push_front(constraint);
      if (!simplifyExisting)
        solverState->generatedConstraints.push_back(constraint);
    }

    // Remove the constraint from the constraint graph.
    if (simplifyExisting)
      CG.removeConstraint(constraint);
    
    return true;

  case SolutionKind::Unsolved:
    // We couldn't solve this constraint; add it to the pile.
    if (!isExternallySolved) {
      InactiveConstraints.push_back(constraint);        
    }

    // Add this constraint to the constraint graph.
    if (!simplifyExisting)
      CG.addConstraint(constraint);

    if (!simplifyExisting && solverState) {
      solverState->generatedConstraints.push_back(constraint);
    }

    return false;
  }
}

/// Check whether this is the depth 0, index 0 generic parameter, which is
/// used for the 'Self' type of a protocol.
static bool isProtocolSelfType(Type type) {
  auto gp = type->getAs<GenericTypeParamType>();
  if (!gp)
    return false;

  return gp->getDepth() == 0 && gp->getIndex() == 0;
}

namespace {
  /// Function object that retrieves a type variable corresponding to the
  /// given dependent type.
  class GetTypeVariable {
    ConstraintSystem &CS;
    DependentTypeOpener *Opener;

    /// The type variables introduced for (base type, associated type) pairs.
    llvm::DenseMap<std::pair<CanType, AssociatedTypeDecl *>, TypeVariableType *>
      MemberReplacements;

  public:
    GetTypeVariable(ConstraintSystem &cs, DependentTypeOpener *opener)
      : CS(cs), Opener(opener) { }

    TypeVariableType *operator()(Type base, AssociatedTypeDecl *member) {
      auto known = MemberReplacements.find({base->getCanonicalType(), member});
      if (known != MemberReplacements.end())
        return known->second;

      auto baseTypeVar = base->castTo<TypeVariableType>();
      auto archetype = baseTypeVar->getImpl().getArchetype()
                         ->getNestedType(member->getName());
      auto tv = CS.createTypeVariable(CS.getConstraintLocator(
                                        (Expr *)nullptr,
                                        LocatorPathElt(archetype)),
                                      TVO_PrefersSubtypeBinding);
      MemberReplacements[{base->getCanonicalType(), member}] = tv;

      // Determine whether we should bind the new type variable as a
      // member of the base type variable, or let it float.
      Type replacementType;
      bool shouldBindMember = true;
      if (Opener) {
        shouldBindMember = Opener->shouldBindAssociatedType(base, baseTypeVar,
                                                            member, tv,
                                                            replacementType);
      }

      // Bind the member's type variable as a type member of the base,
      // if needed.
      if (shouldBindMember)
        CS.addTypeMemberConstraint(base, member->getName(), tv);

      // If we have a replacement type, bind the member's type
      // variable to it.
      if (replacementType)
        CS.addConstraint(ConstraintKind::Bind, tv, replacementType);

      // Add associated type constraints.
      // FIXME: Would be better to walk the requirements of the protocol
      // of which the associated type is a member.
      if (auto superclass = member->getSuperclass()) {
        CS.addConstraint(ConstraintKind::Subtype, tv, superclass);
      }

      for (auto proto : member->getArchetype()->getConformsTo()) {
        CS.addConstraint(ConstraintKind::ConformsTo, tv,
                         proto->getDeclaredType());
      }
      return tv;
    }
  };

  /// Function object that replaces all occurrences of archetypes and
  /// dependent types with type variables.
  class ReplaceDependentTypes {
    ConstraintSystem &cs;
    DeclContext *dc;
    bool skipProtocolSelfConstraint;
    DependentTypeOpener *opener;
    llvm::DenseMap<CanType, TypeVariableType *> &replacements;
    GetTypeVariable &getTypeVariable;

  public:
    ReplaceDependentTypes(
        ConstraintSystem &cs,
        DeclContext *dc,
        bool skipProtocolSelfConstraint,
        DependentTypeOpener *opener,
        llvm::DenseMap<CanType, TypeVariableType *> &replacements,
        GetTypeVariable &getTypeVariable)
      : cs(cs), dc(dc), skipProtocolSelfConstraint(skipProtocolSelfConstraint),
        opener(opener), replacements(replacements), 
        getTypeVariable(getTypeVariable) { }

    Type operator()(Type type) {
      assert(!type->is<PolymorphicFunctionType>() && "Shouldn't get here");

      // Replace archetypes with fresh type variables.
      if (auto archetype = type->getAs<ArchetypeType>()) {
        auto known = replacements.find(archetype->getCanonicalType());
        if (known != replacements.end())
          return known->second;

        return archetype;
      }

      // Replace a generic type parameter with its corresponding type variable.
      if (auto genericParam = type->getAs<GenericTypeParamType>()) {
        auto known = replacements.find(genericParam->getCanonicalType());
        assert(known != replacements.end());
        return known->second;
      }

      // Replace a dependent member with a fresh type variable and make it a
      // member of its base type.
      if (auto dependentMember = type->getAs<DependentMemberType>()) {
        // Check whether we've already dealt with this dependent member.
        auto known = replacements.find(dependentMember->getCanonicalType());
        if (known != replacements.end())
          return known->second;

        // Replace archetypes in the base type.
        auto base = (*this)(dependentMember->getBase());
        auto result = getTypeVariable(base, dependentMember->getAssocType());
        replacements[dependentMember->getCanonicalType()] = result;
        return result;
      }

      // Create type variables for all of the parameters in a generic function
      // type.
      if (auto genericFn = type->getAs<GenericFunctionType>()) {
        // Open up the generic parameters and requirements.
        cs.openGeneric(dc,
                       genericFn->getGenericParams(),
                       genericFn->getRequirements(),
                       skipProtocolSelfConstraint,
                       opener,
                       replacements);

        // Transform the input and output types.
        Type inputTy = genericFn->getInput().transform(*this);
        if (!inputTy)
          return Type();

        Type resultTy = genericFn->getResult().transform(*this);
        if (!resultTy)
          return Type();

        // Build the resulting (non-generic) function type.
        return FunctionType::get(inputTy, resultTy);
      }

      // Open up unbound generic types, turning them into bound generic
      // types with type variables for each parameter.
      if (auto unbound = type->getAs<UnboundGenericType>()) {
        auto parentTy = unbound->getParent();
        if (parentTy)
          parentTy = parentTy.transform(*this);

        auto unboundDecl = unbound->getDecl();

        // Open up the generic type.
        cs.openGeneric(unboundDecl,
                       unboundDecl->getGenericParamTypes(),
                       unboundDecl->getGenericRequirements(),
                       /*skipProtocolSelfConstraint=*/false,
                       opener,
                       replacements);

        // Map the generic parameters to their corresponding type variables.
        llvm::SmallVector<Type, 4> arguments;
        for (auto gp : unboundDecl->getGenericParamTypes()) {
          assert(replacements.count(gp->getCanonicalType()) && 
                 "Missing generic parameter?");
          arguments.push_back(replacements[gp->getCanonicalType()]);
        }
        return BoundGenericType::get(unboundDecl, parentTy, arguments);
      }
      
      return type;
    }
  };
}

Type ConstraintSystem::openType(
       Type startingType,
       llvm::DenseMap<CanType, TypeVariableType *> &replacements,
       DeclContext *dc,
       bool skipProtocolSelfConstraint,
       DependentTypeOpener *opener) {
  GetTypeVariable getTypeVariable{*this, opener};

  ReplaceDependentTypes replaceDependentTypes(*this, dc,
                                              skipProtocolSelfConstraint,
                                              opener,
                                              replacements, getTypeVariable);
  return startingType.transform(replaceDependentTypes);
}

Type ConstraintSystem::openBindingType(Type type, DeclContext *dc) {
  Type result = openType(type, dc);
  // FIXME: Better way to identify Slice<T>.
  if (auto boundStruct
        = dyn_cast<BoundGenericStructType>(result.getPointer())) {
    if (!boundStruct->getParent() &&
        boundStruct->getDecl()->getName().str() == "Array" &&
        boundStruct->getGenericArgs().size() == 1) {
      if (auto replacement = getTypeChecker().getArraySliceType(
                               SourceLoc(), boundStruct->getGenericArgs()[0])) {
        return replacement;
      }
    }
  }

  return result;
}

static Type getFixedTypeRecursiveHelper(ConstraintSystem &cs,
                                        TypeVariableType *typeVar,
                                        bool wantRValue) {
  while (auto fixed = cs.getFixedType(typeVar)) {
    if (wantRValue)
      fixed = fixed->getRValueType();

    typeVar = fixed->getAs<TypeVariableType>();
    if (!typeVar)
      return fixed;
  }
  return nullptr;
}

Type ConstraintSystem::getFixedTypeRecursive(Type type, 
                                             TypeVariableType *&typeVar,
                                             bool wantRValue) {
  if (wantRValue)
    type = type->getRValueType();

  auto desugar = type->getDesugaredType();
  typeVar = desugar->getAs<TypeVariableType>();
  if (typeVar) {
    if (auto fixed = getFixedTypeRecursiveHelper(*this, typeVar, wantRValue)) {
      type = fixed;
      typeVar = nullptr;
    }
  }
  return type;
}

std::pair<Type, Type>
ConstraintSystem::getTypeOfReference(ValueDecl *value,
                                     bool isTypeReference,
                                     bool isSpecialized,
                                     DependentTypeOpener *opener) {
  if (value->getDeclContext()->isTypeContext() && isa<FuncDecl>(value)) {
    // Unqualified lookup can find operator names within nominal types.
    auto func = cast<FuncDecl>(value);
    assert(func->isOperator() && "Lookup should only find operators");

    auto openedType = openType(func->getInterfaceType(), func, false, opener);
    auto openedFnType = openedType->castTo<FunctionType>();

    // The 'Self' type must be bound to an archetype.
    // FIXME: We eventually want to loosen this constraint, to allow us
    // to find operator functions both in classes and in protocols to which
    // a class conforms (if there's a default implementation).
    addArchetypeConstraint(openedFnType->getInput()->getRValueInstanceType());

    // The reference implicitly binds 'self'.
    return { openedType, openedFnType->getResult() };
  }

  // If we have a type declaration, resolve it within the current context.
  if (auto typeDecl = dyn_cast<TypeDecl>(value)) {
    // Resolve the reference to this type declaration in our current context.
    auto type = getTypeChecker().resolveTypeInContext(typeDecl, DC,
                                                      isSpecialized);
    if (!type)
      return { nullptr, nullptr };

    // Open the type.
    type = openType(type, value->getInnermostDeclContext(), false, opener);

    // If it's a type reference, we're done.
    if (isTypeReference)
      return { type, type };

    // If it's a value reference, refer to the metatype.
    type = MetatypeType::get(type, getASTContext());
    return { type, type };
  }

  // Determine the type of the value, opening up that type if necessary.
  Type valueType = TC.getUnopenedTypeOfReference(value, Type(), DC,
                                                 /*wantInterfaceType=*/true);

  // Adjust the type of the reference.
  valueType = openType(valueType,
                       value->getPotentialGenericDeclContext(),
                       /*skipProtocolSelfConstraint=*/false,
                       opener);
  return { valueType, valueType };
}

void ConstraintSystem::openGeneric(
       DeclContext *dc,
       ArrayRef<GenericTypeParamType *> params,
       ArrayRef<Requirement> requirements,
       bool skipProtocolSelfConstraint,
       DependentTypeOpener *opener,
       llvm::DenseMap<CanType, TypeVariableType *> &replacements) {

  // Create the type variables for the generic parameters.
  for (auto gp : params) {
    ArchetypeType *archetype = ArchetypeBuilder::mapTypeIntoContext(dc, gp)
                                 ->castTo<ArchetypeType>();
    auto typeVar = createTypeVariable(getConstraintLocator(
                                        (Expr *)nullptr,
                                        LocatorPathElt(archetype)),
                                      TVO_PrefersSubtypeBinding);
    replacements[gp->getCanonicalType()] = typeVar;

    // Note that we opened a generic parameter to a type variable.
    if (opener) {
      Type replacementType;
      opener->openedGenericParameter(gp, typeVar, replacementType);

      if (replacementType)
        addConstraint(ConstraintKind::Bind, typeVar, replacementType);
    }
  }

  GetTypeVariable getTypeVariable{*this, opener};
  ReplaceDependentTypes replaceDependentTypes(*this, dc,
                                              skipProtocolSelfConstraint,
                                              opener, replacements, 
                                              getTypeVariable);

  // Add the requirements as constraints.
  for (auto req : requirements) {
  switch (req.getKind()) {
    case RequirementKind::Conformance: {
      auto subjectTy = req.getFirstType().transform(replaceDependentTypes);
      if (auto proto = req.getSecondType()->getAs<ProtocolType>()) {
        if (!skipProtocolSelfConstraint ||
            !(isa<ProtocolDecl>(dc) || isa<ProtocolDecl>(dc->getParent())) ||
            !isProtocolSelfType(req.getFirstType())) {
          addConstraint(ConstraintKind::ConformsTo, subjectTy,
                        proto);
        }
      } else {
        auto boundTy = req.getSecondType().transform(replaceDependentTypes);
        addConstraint(ConstraintKind::Subtype, subjectTy, boundTy);
      }
      break;
    }

    case RequirementKind::SameType: {
      auto firstTy = req.getFirstType().transform(replaceDependentTypes);
      auto secondTy = req.getSecondType().transform(replaceDependentTypes);
{'fraction_non_alphanumeric': 0.10928211265671291, 'fraction_numerical': 0.0017265396613627892, 'mean_word_length': 2.6321527827264304, 'pattern_counts': {'":': 0, '<': 109, '<?xml version=': 0, '>': 331, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 94, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7294003', 'n_tokens_mistral': 13684, 'n_tokens_neox': 13140, 'n_words': 3572}